Achieving numerical accuracy and high performance using recursive tile LU factorization with partial pivoting

摘要

The LU factorization is an important numerical algorithm for solving systems of linear equations in sciencernand engineering and is a characteristic of many dense linear algebra computations. For example, it hasrnbecome the de facto numerical algorithm implemented within the LINPACK benchmark to rank the mostrnpowerful supercomputers in the world, collected by the TOP500 website. Multicore processors continue tornpresent challenges to the development of fast and robust numerical software due to the increasing levelsrnof hardware parallelism and widening gap between core and memory speeds. In this context, the difficultyrnin developing new algorithms for the scientific community resides in the combination of two goals:rnachieving high performance while maintaining the accuracy of the numerical algorithm. This paper proposesrna new approach for computing the LU factorization in parallel on multicore architectures, which not onlyrnimproves the overall performance but also sustains the numerical quality of the standard LU factorizationrnalgorithm with partial pivoting. While the update of the trailing submatrix is computationally intensive andrnhighly parallel, the inherently problematic portion of the LU factorization is the panel factorization due tornits memory-bound characteristic as well as the atomicity of selecting the appropriate pivots. Our approachrnuses a parallel fine-grained recursive formulation of the panel factorization step and implements the updaternof the trailing submatrix with the tile algorithm. Based on conflict-free partitioning of the data and locklessrnsynchronization mechanisms, our implementation lets the overall computation flow naturally withoutrncontention. The dynamic runtime system called QUARK is then able to schedule tasks with heterogeneousrngranularities and to transparently introduce algorithmic lookahead. The performance results of our implementationrnare competitive compared to the currently available software packages and libraries. For example,rnit is up to 40% faster when compared to the equivalent Intel MKL routine and up to threefold faster thanrnLAPACK with multithreaded Intel MKL BLAS.