High performance matrix inversion based on LU factorization for multicore architectures

Jack Dongarra, Mathieu Faverge, Hatem Ltaief, Piotr Luszczek

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

22 Scopus citations

Abstract

The goal of this paper is to present an efficient implementation of an explicit matrix inversion of general square matrices on multicore computer architecture. The inversion procedure is split into four steps: 1) computing the LU factorization, 2) inverting the upper triangular U factor, 3) solving a linear system, whose solution yields inverse of the original matrix and 4) applying backward column pivoting on the inverted matrix. Using a tile data layout, which represents the matrix in the system memory with an optimized cache-aware format, the computation of the four steps is decomposed into computational tasks. A directed acyclic graph is generated on the fly which represents the program data flow. Its nodes represent tasks and edges the data dependencies between them. Previous implementations of matrix inversions, available in the state-of-the-art numerical libraries, are suffer from unnecessary synchronization points, which are non-existent in our implementation in order to fully exploit the parallelism of the underlying hardware. Our algorithmic approach allows to remove these bottlenecks and to execute the tasks with loose synchronization. A runtime environment system called QUARK is necessary to dynamically schedule our numerical kernels on the available processing units. The reported results from our LU-based matrix inversion implementation significantly outperform the state-of-the-art numerical libraries such as LAPACK (5x), MKL (5x) and ScaLAPACK (2.5x) on a contemporary AMD platform with four sockets and the total of 48 cores for a matrix of size 24000. A power consumption analysis shows that our high performance implementation is also energy efficient and substantially consumes less power than its competitors.

Original languageEnglish
Title of host publicationMTAGS'11 - Proceedings of the 2011 ACM International Workshop on Many Task Computing on Grids and Supercomputers, Co-located with SC'11
Pages33-42
Number of pages10
DOIs
StatePublished - 2011
Event2011 ACM International Workshop on Many Task Computing on Grids and Supercomputers, MTAGS'11, Co-located with SC'11 - Seattle, WA, United States
Duration: Nov 14 2011Nov 14 2011

Publication series

NameMTAGS'11 - Proceedings of the 2011 ACM International Workshop on Many Task Computing on Grids and Supercomputers, Co-located with SC'11

Conference

Conference2011 ACM International Workshop on Many Task Computing on Grids and Supercomputers, MTAGS'11, Co-located with SC'11
Country/TerritoryUnited States
CitySeattle, WA
Period11/14/1111/14/11

Keywords

  • LU factorization
  • multicore parallel performance
  • runtime DAG scheduling

Fingerprint

Dive into the research topics of 'High performance matrix inversion based on LU factorization for multicore architectures'. Together they form a unique fingerprint.

Cite this