Name
Title | ||
|---|---|---|
Effects of Ordering Strategies and Programming Paradigms on Sparse Matrix Computations. |
Abstract | ||
|---|---|---|
The conjugate gradient (CG) algorithm is perhaps the best-known iterative technique for solving sparse linear systems that are symmetric and positive definite. For systems that are ill conditioned, it is often necessary to use a preconditioning technique. In this paper, we investigate the effects of various ordering and partitioning strategies on the performance of parallel CG and ILU(0) preconditioned CG (PCG) using different programming paradigms and architectures. Results show that for this class of applications, ordering significantly improves overall performance on both distributed and distributed shared-memory systems, cache reuse may be more important than reducing communication, it is possible to achieve message-passing performance using shared-memory constructs through careful data ordering and distribution, and a hybrid MPI + OpenMP paradigm increases programming complexity with little performance gain. A multithreaded implementation of CG on the Cray MTA does not require special ordering or partitioning to obtain high efficiency and scalability, giving it a distinct advantage for adaptive applications; however, it shows limited scalability for PCG due to a lack of thread-level parallelism. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1137/S00361445003820 | SIAM Review |
Keywords | Field | DocType |
parallel cg,ordering strategies,performance gain,sparse matrix computations,best-known iterative technique,partitioning strategy,preconditioned cg,different programming paradigm,message-passing performance,hybrid programming,programming paradigms,openmp paradigm increases programming,multi- threading,shared-memory directives,overall performance,preconditioned conjugate gradient,self- avoiding walks,message passing,graph partitioning,limited scalability,reverse cuthill-mckee,graph,algorithm,distributed memory,positive definite,thread level parallelism,distributed shared memory,programming,shared memory,threads,hybrid,algorithms,multithreading,matrix calculus,linear systems,partition,programming paradigm,conjugate gradient method,sparse matrix,preconditioning,conjugate gradient,self avoiding walk,computer simulation | Conjugate gradient method,Programming paradigm,Cache,Computer science,Parallel computing,Distributed memory,Theoretical computer science,Graph partition,Sparse matrix,Message passing,Scalability | Journal |
Volume | Issue | ISSN |
44 | 3 | 0036-1445 |
Citations | PageRank | References |
34 | 2.16 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| leonid oliker | 1 | 1358 | 145.15 |
| Xiaoye Li | 2 | 65 | 9.03 |
| Parry Husbands | 3 | 561 | 56.37 |
| Rupak Biswas | 4 | 922 | 109.66 |