James W. Demmel, John R. Gilbert and Xiaoye S. Li

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-97-943
February 1997

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/CSD-97-943.pdf

Although Gaussian elimination with partial pivoting is a robust algorithm to solve unsymmetric sparse linear systems of equations, it is difficult to implement efficiently on parallel machines, because of its dynamic and somewhat unpredictable way of generating work and intermediate results at run time. In this paper, we present an efficient parallel algorithm that overcomes this difficulty. The high performance of our algorithm is achieved through (1) using a graph reduction technique and a supernode-panel computational kernel for high single processor utilization, and (2) scheduling two types of parallel tasks for a high level of concurrency. One such task is factoring the independent panels on the disjoint subtrees in the column elimination tree of A. Another task is updating a panel by previously computed supernodes. A scheduler assigns tasks to free processors dynamically and facilitates the smooth transition between the two types of parallel tasks. No global synchronization is used in the algorithm. The algorithm is well suited for shared memory machines (SMP) with a modest number of processors. We demonstrate 4-7 fold speedups on a range of 8 processor SMPs, and more on larger SMPs. One realistic problem arising from a 3-D flow calculation achieves factorization rates of 1.0, 2.5, 0.8 and 0.8 Gigaflops, on the 12 processor Power Challenge, 8 processor Cray C90, 16 processor Cray J90, and 8 processor AlphaServer 8400 respectively.

BibTeX citation:

@techreport{Demmel:CSD-97-943,
    Author = {Demmel, James W. and Gilbert, John R. and Li, Xiaoye S.},
    Title = {An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1997},
    Month = {Feb},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5622.html},
    Number = {UCB/CSD-97-943},
    Abstract = {Although Gaussian elimination with partial pivoting is a robust algorithm to solve unsymmetric sparse linear systems of equations, it is difficult to implement efficiently on parallel machines, because of its dynamic and somewhat unpredictable way of generating work and intermediate results at run time. In this paper, we present an efficient parallel algorithm that overcomes this difficulty. The high performance of our algorithm is achieved through (1) using a graph reduction technique and a supernode-panel computational kernel for high single processor utilization, and (2) scheduling two types of parallel tasks for a high level of concurrency. One such task is factoring the independent panels on the disjoint subtrees in the column elimination tree of <i>A</i>. Another task is updating a panel by previously computed supernodes. A scheduler assigns tasks to free processors dynamically and facilitates the smooth transition between the two types of parallel tasks. No global synchronization is used in the algorithm. The algorithm is well suited for shared memory machines (SMP) with a modest number of processors. We demonstrate 4-7 fold speedups on a range of 8 processor SMPs, and more on larger SMPs. One realistic problem arising from a 3-D flow calculation achieves factorization rates of 1.0, 2.5, 0.8 and 0.8 Gigaflops, on the 12 processor Power Challenge, 8 processor Cray C90, 16 processor Cray J90, and 8 processor AlphaServer 8400 respectively.}
}

EndNote citation:

%0 Report
%A Demmel, James W.
%A Gilbert, John R.
%A Li, Xiaoye S.
%T An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination
%I EECS Department, University of California, Berkeley
%D 1997
%@ UCB/CSD-97-943
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5622.html
%F Demmel:CSD-97-943