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

被引：31

作者：

Aliaga, Jose I. ^{[1
]}

Bollhoefer, Matthias ^{[2
]}

Martin, Alberto F. ^{[1
]}

Quintana-Orti, Enrique S. ^{[1
]}

机构：

[1] Univ Jaime I, Dpto Ingn & Ciencia Comp, Castellon de La Plana 12071, Spain

[2] Tech Univ Carolo Wilhelmina Braunschweig, Inst Computat Math, D-38106 Braunschweig, Germany

来源：

PARALLEL COMPUTING | 2011年 / 37卷 / 03期

关键词：

Large sparse linear systems; Factorization-based preconditioning; Preconditioned conjugate gradients; Task-level parallelism; Shared-memory multiprocessors; MULTILEVEL; SOLVER;

D O I：

10.1016/j.parco.2010.11.002

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 ILU-PACK. 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. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：183 / 202

页数：20

共 28 条

[1]

ALIAGA JI, 2007, ADV PARALLEL COMPUTI, V38, P287

[2]

ALIAGA JI, 2008, P PARA 2008 9 UNPUB

[3]

Aliaga JI, 2008, LECT NOTES COMPUT SC, V5336, P314, DOI 10.1007/978-3-540-92859-1_28

[4] A fully asynchronous multifrontal solver using distributed dynamic scheduling [J].

Amestoy, PR ;

Duff, IS ;

L'Excellent, JY ;

Koster, J .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2001, 23 (01) :15-41

[5]

[Anonymous], STAT MAPP GRAPH PART

[6]

[Anonymous], 2003, ITERATIVE METHODS SP, DOI DOI 10.1137/1.9780898718003

[7] ALGEBRAIC MULTILEVEL PRECONDITIONER FOR THE HELMHOLTZ EQUATION IN HETEROGENEOUS MEDIA [J].

Bollhoefer, Matthias ;

Grote, Marcus J. ;

Schenk, Olaf .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2009, 31 (05) :3781-3805

[8] Multilevel preconditioners constructed from inverse-based ILUs [J].

Bollhöfer, M ;

Saad, Y .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2006, 27 (05) :1627-1650

[9] On the relations between ILUs and factored approximate inverses [J].

Bollhöfer, M ;

Saad, Y .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2002, 24 (01) :219-237

[10] ESTIMATE FOR THE CONDITION NUMBER OF A MATRIX [J].

CLINE, AK ;

MOLER, CB ;

STEWART, GW ;

WILKINSON, JH .

SIAM JOURNAL ON NUMERICAL ANALYSIS, 1979, 16 (02) :368-375

← 1 2 3 →