Efficient sparse LU factorization with partial pivoting on distributed memory architectures

doi:10.1109/71.663864

Efficient sparse LU factorization with partial pivoting on distributed memory architectures

1998-01-01

16

PRE

AI

DOI：10.1109/71.663864

Original

Original request for help

Save

Abstract

En 中文

A sparse LU factorization based on Gaussian elimination with partial pivoting (GEPP) is important to many scientific applications, but it is still an open problem to develop a high performance GEPP code on distributed memory machines. The main difficulty is that partial pivoting operations dynamically change computation and nonzero fill-in structures during the elimination process. This paper presents an approach called S* for parallelizing this problem on distributed memory machines. The S* approach adopts static symbolic factorization to avoid run-time control overhead, incorporates 2D L/U supermode partitioning and amalgamation strategies to improve caching performance, and exploits irregular task parallelism embedded in sparse LU using asynchronous computation scheduling. The paper discusses and compares the algorithms using 1D and 2D data mapping schemes, and presents experimental studies on Cray-T3D and T3E. The performance results for a set of nonsymmetric benchmark matrices are very encouraging, and S* has achieved up to 6.878 GFLOPS on 128 T3E nodes. To the best of our knowledge, this is the highest performance ever achieved for this challenging problem and the previous record was 2.583 GFLOPS on shared memory machines [8].

Keywords:

sparse LU factorization

Gaussian elimination with partial pivoting

dense structures

asynchronous computation scheduling

irregular parallelism

Efficient sparse LU factorization with partial pivoting on distributed memory architectures

Abstract

AI Summary

Journal

Organization