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:

Project Contact:
Kai Shen (kshen@cs.rochester.edu)
Tao Yang (tyang@cs.ucsb.edu)

The mirror project site at University of California, Santa Barbara.