Parilut - A parallel threshold ILU for GPUS

Hartwig Anzt; Tobias Ribizel; Goran Flegar; Edmond Chow; Jack Dongarra

doi:10.1109/IPDPS.2019.00033

Parilut - A parallel threshold ILU for GPUS

Hartwig Anzt, Tobias Ribizel, Goran Flegar, Edmond Chow, Jack Dongarra

Computer Science and Mathematics Div

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

8 Scopus citations

Abstract

In this paper, we present the first algorithm for computing threshold ILU factorizations on GPU architectures. The proposed ParILUT-GPU algorithm is based on interleaving parallel fixed-point iterations that approximate the incomplete factors for an existing nonzero pattern with a strategy that dynamically adapts the nonzero pattern to the problem characteristics. This requires the efficient selection of thresholds that separate the values to be dropped from the incomplete factors, and we design a novel selection algorithm tailored towards GPUs. All components of the ParILUT-GPU algorithm make heavy use of the features available in the latest NVIDIA GPU generations, and outperform existing multithreaded CPU implementations.

Original language	English
Title of host publication	Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	231-241
Number of pages	11
ISBN (Electronic)	9781728112466
DOIs	https://doi.org/10.1109/IPDPS.2019.00033
State	Published - May 2019
Event	33rd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019 - Rio de Janeiro, Brazil Duration: May 20 2019 → May 24 2019

Publication series

Name	Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019

Conference

Conference	33rd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019
Country/Territory	Brazil
City	Rio de Janeiro
Period	05/20/19 → 05/24/19

Funding

This work was supported by the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under Award Numbers DE-SC0016513, DE-SC-0016564, and DE-SC-0010042. H. Anzt was supported by the “Impuls und Vernet-zungsfond” of the Helmholtz Association under grant VH-NG-1241.

Keywords

GPU
Incomplete factorization preconditioners
ParILUT
Parallel selection
Parallel threshold ILU

Access to Document

10.1109/IPDPS.2019.00033

Cite this

Anzt, H., Ribizel, T., Flegar, G., Chow, E., & Dongarra, J. (2019). Parilut - A parallel threshold ILU for GPUS. In Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019 (pp. 231-241). Article 8820992 (Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPS.2019.00033

Anzt, Hartwig ; Ribizel, Tobias ; Flegar, Goran et al. / Parilut - A parallel threshold ILU for GPUS. Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 231-241 (Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019).

@inproceedings{9903e937da324cb58b6fb082f5a37d75,

title = "Parilut - A parallel threshold ILU for GPUS",

abstract = "In this paper, we present the first algorithm for computing threshold ILU factorizations on GPU architectures. The proposed ParILUT-GPU algorithm is based on interleaving parallel fixed-point iterations that approximate the incomplete factors for an existing nonzero pattern with a strategy that dynamically adapts the nonzero pattern to the problem characteristics. This requires the efficient selection of thresholds that separate the values to be dropped from the incomplete factors, and we design a novel selection algorithm tailored towards GPUs. All components of the ParILUT-GPU algorithm make heavy use of the features available in the latest NVIDIA GPU generations, and outperform existing multithreaded CPU implementations.",

keywords = "GPU, Incomplete factorization preconditioners, ParILUT, Parallel selection, Parallel threshold ILU",

author = "Hartwig Anzt and Tobias Ribizel and Goran Flegar and Edmond Chow and Jack Dongarra",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE; 33rd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019 ; Conference date: 20-05-2019 Through 24-05-2019",

year = "2019",

month = may,

doi = "10.1109/IPDPS.2019.00033",

language = "English",

series = "Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "231--241",

booktitle = "Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019",

}

Anzt, H, Ribizel, T, Flegar, G, Chow, E & Dongarra, J 2019, Parilut - A parallel threshold ILU for GPUS. in Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019., 8820992, Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019, Institute of Electrical and Electronics Engineers Inc., pp. 231-241, 33rd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Rio de Janeiro, Brazil, 05/20/19. https://doi.org/10.1109/IPDPS.2019.00033

Parilut - A parallel threshold ILU for GPUS. / Anzt, Hartwig; Ribizel, Tobias; Flegar, Goran et al.
Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 231-241 8820992 (Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019).

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

TY - GEN

T1 - Parilut - A parallel threshold ILU for GPUS

AU - Anzt, Hartwig

AU - Ribizel, Tobias

AU - Flegar, Goran

AU - Chow, Edmond

AU - Dongarra, Jack

PY - 2019/5

Y1 - 2019/5

N2 - In this paper, we present the first algorithm for computing threshold ILU factorizations on GPU architectures. The proposed ParILUT-GPU algorithm is based on interleaving parallel fixed-point iterations that approximate the incomplete factors for an existing nonzero pattern with a strategy that dynamically adapts the nonzero pattern to the problem characteristics. This requires the efficient selection of thresholds that separate the values to be dropped from the incomplete factors, and we design a novel selection algorithm tailored towards GPUs. All components of the ParILUT-GPU algorithm make heavy use of the features available in the latest NVIDIA GPU generations, and outperform existing multithreaded CPU implementations.

AB - In this paper, we present the first algorithm for computing threshold ILU factorizations on GPU architectures. The proposed ParILUT-GPU algorithm is based on interleaving parallel fixed-point iterations that approximate the incomplete factors for an existing nonzero pattern with a strategy that dynamically adapts the nonzero pattern to the problem characteristics. This requires the efficient selection of thresholds that separate the values to be dropped from the incomplete factors, and we design a novel selection algorithm tailored towards GPUs. All components of the ParILUT-GPU algorithm make heavy use of the features available in the latest NVIDIA GPU generations, and outperform existing multithreaded CPU implementations.

KW - GPU

KW - Incomplete factorization preconditioners

KW - ParILUT

KW - Parallel selection

KW - Parallel threshold ILU

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

U2 - 10.1109/IPDPS.2019.00033

DO - 10.1109/IPDPS.2019.00033

M3 - Conference contribution

AN - SCOPUS:85072838710

T3 - Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019

SP - 231

EP - 241

BT - Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 33rd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019

Y2 - 20 May 2019 through 24 May 2019

ER -

Anzt H, Ribizel T, Flegar G, Chow E, Dongarra J. Parilut - A parallel threshold ILU for GPUS. In Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 231-241. 8820992. (Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019). doi: 10.1109/IPDPS.2019.00033

Parilut - A parallel threshold ILU for GPUS

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this