S+: Message Passing-based Parallel Sparse LU Factorization
Sparse LU factorization with partial pivoting is important for many
scientific applications and delivering high performance for this problem
is difficult on distributed memory machines. This project studies the
properties of elimination forests and uses them to guide supernode
partitioning/amalgamation and execution scheduling. This design with 2D
mapping effectively identifies dense structures without introducing too
many zeros in the BLAS computation and exploits asynchronous parallelism
with low buffer space cost. The implementation of this code, called S+,
uses supernodal matrix multiplication which retains the BLAS-3 level
efficiency and avoids unnecessary arithmetic operations. This project
also studies two space optimization techniques which can greatly improve
the worst-case performance of static symbolic factorization.
Download S+ 1.1.
The code is written in C. It uses MPI for message passing and it uses
BLAS/LAPACK for numerical computation.
S+ has been tested on SGI Origin 2000, Cray T3E, IBM p690 "Regatta",
and Linux PC cluster. You may port it to any other platform which also
supports MPI and has BLAS/LAPACK library.
Deployment and evaluation:
S+ has been tested and packaged by Sun Microsystems and is released
as part of Sun HPC ClusterTools 4 Software.
Publications:
-
Kai Shen,
"Parallel Sparse LU Factorization on Different Message Passing Platforms".
Accepted for publication in Journal of Parallel and Distributed Computing (JPDC).
Abstract.
Postscript version.
PDF version.
-
Kai Shen,
"Parallel Sparse LU Factorization on Second-class Message Passing Platforms".
In Proc. of the 19th ACM International Conference on Supercomputing (ICS'05),
Pages 351-360, Cambridge, MA, June 2005.
Abstract.
Postscript version.
PDF version.
-
Kai Shen, Tao Yang, and Xiangmin Jiao,
"S+: Efficient 2D Sparse LU Factorization on Parallel Machines".
In SIAM Journal on Matrix Analysis and Applications (SIMAX),
Volume 22, Number 1, Pages 282-305, 2000.
Abstract.
Postscript version.
PDF version.
-
Bin Jiang, Steven Richman, Kai Shen, and Tao Yang,
"Efficient Sparse LU Factorization with Lazy Space Allocation".
In SIAM 1999 Parallel Processing Conference on Scientific Computing,
San Antonio TX, March 1999.
Abstract.
Postscript version.
PDF version.
Conference talk slides in Postscript.
-
Kai Shen, Xiangmin Jiao, and Tao Yang,
"Elimination Forest Guided 2D Sparse LU Factorization".
In Proc. of the 10th ACM Symposium on Parallel Architectures and Algorithms (SPAA'98),
Pages 5-15, Puerto Vallarta, Mexico, June 1998.
Abstract.
Postscript version.
PDF version.
Conference talk slides in Postscript.
Project Contact:
Kai Shen
(kshen@cs.rochester.edu)
Tao Yang
(tyang@cs.ucsb.edu)
The mirror project site at University of California, Santa Barbara.