Design, tuning and evaluation of parallel multilevel ILU preconditioners

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

doi:10.1007/978-3-540-92859-1_28

Design, tuning and evaluation of parallel multilevel ILU preconditioners

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

5 Citations (Scopus)

Abstract

In this paper, we present a parallel multilevel ILU preconditioner implemented with OpenMP. We employ METIS partitioning algorithms to decompose the computation into concurrent tasks, which are then scheduled to threads. Concretely, we combine decompositions which obtain significantly more tasks than processors, and the use of dynamic scheduling strategies in order to reduce the thread's idle time, which it is shown to be the main source of overhead in our parallel algorithm. Experimental results on a shared-memory platform consisting of 16 processors report remarkable performance for our approach.

Original language	English
Title of host publication	High Performance Computing for Computational Science - VECPAR 2008 - 8th International Conference, Revised Selected Papers
Pages	314-327
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-540-92859-1_28
Publication status	Published - 1 Dec 2008
Externally published	Yes
Event	International Conference on High Performance Computing for Computational Science, 2008 - Toulouse, France Duration: 24 Jun 2008 → 27 Jun 2008 Conference number: 8th

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5336 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on High Performance Computing for Computational Science, 2008
Abbreviated title	VECPAR 2008
Country	France
City	Toulouse
Period	24/06/08 → 27/06/08

Keywords

Incomplete LU factorization
OpenMP
Parallel algorithm
Shared-memory multiprocessor
Sparse linear system

Access to Document

10.1007/978-3-540-92859-1_28

Link to publication in Scopus

Cite this

Aliaga, J. I., Bollhöfer, M., Martín, A. F., & Quintana-Ortí, E. S. (2008). Design, tuning and evaluation of parallel multilevel ILU preconditioners. In High Performance Computing for Computational Science - VECPAR 2008 - 8th International Conference, Revised Selected Papers (pp. 314-327). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5336 LNCS). https://doi.org/10.1007/978-3-540-92859-1_28

Aliaga, José I. ; Bollhöfer, Matthias ; Martín, Alberto F. ; Quintana-Ortí, Enrique S. / Design, tuning and evaluation of parallel multilevel ILU preconditioners. High Performance Computing for Computational Science - VECPAR 2008 - 8th International Conference, Revised Selected Papers. 2008. pp. 314-327 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1e8e3c01d48446ceb4570ff30736550b,

title = "Design, tuning and evaluation of parallel multilevel ILU preconditioners",

abstract = "In this paper, we present a parallel multilevel ILU preconditioner implemented with OpenMP. We employ METIS partitioning algorithms to decompose the computation into concurrent tasks, which are then scheduled to threads. Concretely, we combine decompositions which obtain significantly more tasks than processors, and the use of dynamic scheduling strategies in order to reduce the thread's idle time, which it is shown to be the main source of overhead in our parallel algorithm. Experimental results on a shared-memory platform consisting of 16 processors report remarkable performance for our approach.",

keywords = "Incomplete LU factorization, OpenMP, Parallel algorithm, Shared-memory multiprocessor, Sparse linear system",

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

year = "2008",

month = dec,

day = "1",

doi = "10.1007/978-3-540-92859-1_28",

language = "English",

isbn = "3540928588",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "314--327",

booktitle = "High Performance Computing for Computational Science - VECPAR 2008 - 8th International Conference, Revised Selected Papers",

note = "International Conference on High Performance Computing for Computational Science, 2008, VECPAR 2008 ; Conference date: 24-06-2008 Through 27-06-2008",

}

Aliaga, JI, Bollhöfer, M, Martín, AF & Quintana-Ortí, ES 2008, Design, tuning and evaluation of parallel multilevel ILU preconditioners. in High Performance Computing for Computational Science - VECPAR 2008 - 8th International Conference, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5336 LNCS, pp. 314-327, International Conference on High Performance Computing for Computational Science, 2008, Toulouse, France, 24/06/08. https://doi.org/10.1007/978-3-540-92859-1_28

Design, tuning and evaluation of parallel multilevel ILU preconditioners. / Aliaga, José I.; Bollhöfer, Matthias; Martín, Alberto F.; Quintana-Ortí, Enrique S.

High Performance Computing for Computational Science - VECPAR 2008 - 8th International Conference, Revised Selected Papers. 2008. p. 314-327 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5336 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Design, tuning and evaluation of parallel multilevel ILU preconditioners

AU - Aliaga, José I.

AU - Bollhöfer, Matthias

AU - Martín, Alberto F.

AU - Quintana-Ortí, Enrique S.

N1 - Conference code: 8th

PY - 2008/12/1

Y1 - 2008/12/1

N2 - In this paper, we present a parallel multilevel ILU preconditioner implemented with OpenMP. We employ METIS partitioning algorithms to decompose the computation into concurrent tasks, which are then scheduled to threads. Concretely, we combine decompositions which obtain significantly more tasks than processors, and the use of dynamic scheduling strategies in order to reduce the thread's idle time, which it is shown to be the main source of overhead in our parallel algorithm. Experimental results on a shared-memory platform consisting of 16 processors report remarkable performance for our approach.

AB - In this paper, we present a parallel multilevel ILU preconditioner implemented with OpenMP. We employ METIS partitioning algorithms to decompose the computation into concurrent tasks, which are then scheduled to threads. Concretely, we combine decompositions which obtain significantly more tasks than processors, and the use of dynamic scheduling strategies in order to reduce the thread's idle time, which it is shown to be the main source of overhead in our parallel algorithm. Experimental results on a shared-memory platform consisting of 16 processors report remarkable performance for our approach.

KW - Incomplete LU factorization

KW - OpenMP

KW - Parallel algorithm

KW - Shared-memory multiprocessor

KW - Sparse linear system

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

U2 - 10.1007/978-3-540-92859-1_28

DO - 10.1007/978-3-540-92859-1_28

M3 - Conference Paper

AN - SCOPUS:58349093301

SN - 3540928588

SN - 9783540928584

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 314

EP - 327

BT - High Performance Computing for Computational Science - VECPAR 2008 - 8th International Conference, Revised Selected Papers

T2 - International Conference on High Performance Computing for Computational Science, 2008

Y2 - 24 June 2008 through 27 June 2008

ER -

Aliaga JI, Bollhöfer M, Martín AF, Quintana-Ortí ES. Design, tuning and evaluation of parallel multilevel ILU preconditioners. In High Performance Computing for Computational Science - VECPAR 2008 - 8th International Conference, Revised Selected Papers. 2008. p. 314-327. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-92859-1_28