Exploiting thread-level parallelism in the iterative solution of sparse linear systems

José I. Aliaga; Matthias Bollhöfer; Alberto F. Martín; Enrique S. Quintana-Ortí

doi:10.1016/j.parco.2010.11.002

Exploiting thread-level parallelism in the iterative solution of sparse linear systems

José I. Aliaga, Matthias Bollhöfer, Alberto F. Martín, Enrique S. Quintana-Ortí

Research output: Contribution to journal › Article › peer-review

38 Citations (Scopus)

Abstract

We investigate the efficient iterative solution of large-scale sparse linear systems on shared-memory multiprocessors. Our parallel approach is based on a multilevel ILU preconditioner which preserves the mathematical semantics of the sequential method in ILUPACK. We exploit the parallelism exposed by the task tree corresponding to the nested dissection hierarchy (task parallelism), employ dynamic scheduling of tasks to processors to improve load balance, and formulate all stages of the parallel PCG method conformal with the computation of the preconditioner to increase data reuse. Results on a CC-NUMA platform with 16 processors reveal the parallel efficiency of this solution.

Original language	English
Pages (from-to)	183-202
Number of pages	20
Journal	Parallel Computing
Volume	37
Issue number	3
DOIs	https://doi.org/10.1016/j.parco.2010.11.002
Publication status	Published - Mar 2011
Externally published	Yes

Access to Document

10.1016/j.parco.2010.11.002

Cite this

@article{576a5758cc9b46c6ad4884bc90dda304,

title = "Exploiting thread-level parallelism in the iterative solution of sparse linear systems",

abstract = "We investigate the efficient iterative solution of large-scale sparse linear systems on shared-memory multiprocessors. Our parallel approach is based on a multilevel ILU preconditioner which preserves the mathematical semantics of the sequential method in ILUPACK. We exploit the parallelism exposed by the task tree corresponding to the nested dissection hierarchy (task parallelism), employ dynamic scheduling of tasks to processors to improve load balance, and formulate all stages of the parallel PCG method conformal with the computation of the preconditioner to increase data reuse. Results on a CC-NUMA platform with 16 processors reveal the parallel efficiency of this solution.",

keywords = "Factorization-based preconditioning, Large sparse linear systems, Preconditioned conjugate gradients, Shared-memory multiprocessors, Task-level parallelism",

author = "Aliaga, {Jos{\'e} I.} and Matthias Bollh{\"o}fer and Mart{\'i}n, {Alberto F.} and Quintana-Ort{\'i}, {Enrique S.}",

year = "2011",

month = mar,

doi = "10.1016/j.parco.2010.11.002",

language = "English",

volume = "37",

pages = "183--202",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Exploiting thread-level parallelism in the iterative solution of sparse linear systems

AU - Aliaga, José I.

AU - Bollhöfer, Matthias

AU - Martín, Alberto F.

AU - Quintana-Ortí, Enrique S.

PY - 2011/3

Y1 - 2011/3

N2 - We investigate the efficient iterative solution of large-scale sparse linear systems on shared-memory multiprocessors. Our parallel approach is based on a multilevel ILU preconditioner which preserves the mathematical semantics of the sequential method in ILUPACK. We exploit the parallelism exposed by the task tree corresponding to the nested dissection hierarchy (task parallelism), employ dynamic scheduling of tasks to processors to improve load balance, and formulate all stages of the parallel PCG method conformal with the computation of the preconditioner to increase data reuse. Results on a CC-NUMA platform with 16 processors reveal the parallel efficiency of this solution.

AB - We investigate the efficient iterative solution of large-scale sparse linear systems on shared-memory multiprocessors. Our parallel approach is based on a multilevel ILU preconditioner which preserves the mathematical semantics of the sequential method in ILUPACK. We exploit the parallelism exposed by the task tree corresponding to the nested dissection hierarchy (task parallelism), employ dynamic scheduling of tasks to processors to improve load balance, and formulate all stages of the parallel PCG method conformal with the computation of the preconditioner to increase data reuse. Results on a CC-NUMA platform with 16 processors reveal the parallel efficiency of this solution.

KW - Factorization-based preconditioning

KW - Large sparse linear systems

KW - Preconditioned conjugate gradients

KW - Shared-memory multiprocessors

KW - Task-level parallelism

UR - http://www.scopus.com/inward/record.url?scp=79953295121&partnerID=8YFLogxK

U2 - 10.1016/j.parco.2010.11.002

DO - 10.1016/j.parco.2010.11.002

M3 - Article

SN - 0167-8191

VL - 37

SP - 183

EP - 202

JO - Parallel Computing

JF - Parallel Computing

IS - 3

ER -

Exploiting thread-level parallelism in the iterative solution of sparse linear systems

Abstract

Access to Document

Other files and links

Fingerprint

Cite this