Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs

Hartwig Anzt; Jack Dongarra; Goran Flegar; Enrique S. Quintana-Ortí

doi:10.1145/3026937.3026940

Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs

Hartwig Anzt, Jack Dongarra, Goran Flegar, Enrique S. Quintana-Ortí

Computer Science and Mathematics Div

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

25 Scopus citations

Abstract

In this paper, we design and evaluate a routine for the efficient generation of block-Jacobi preconditioners on graphics processing units (GPUs). Concretely, to exploit the architecture of the graphics accelerator, we develop a batched Gauss-Jordan elimination CUDA kernel for matrix inversion that embeds an implicit pivoting technique and handles the entire inversion process in the GPU registers. In addition, we integrate extraction and insertion CUDA kernels to rapidly set up the block-Jacobi preconditioner. Our experiments compare the performance of our implementation against a sequence of batched routines from the MAGMA library realizing the inversion via the LU factorization with partial pivoting. Furthermore, we evaluate the costs of different strategies for the block-Jacobi extraction and insertion steps, using a variety of sparse matrices from the SuiteSparse matrix collection. Finally, we assess the efficiency of the complete block-Jacobi preconditioner generation in the context of an iterative solver applied to a set of computational science problems, and quantify its benefits over a scalar Jacobi preconditioner.

Original language	English
Title of host publication	Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017
Editors	Quan Chen, Zhiyi Huang
Publisher	Association for Computing Machinery, Inc
Pages	1-10
Number of pages	10
ISBN (Electronic)	9781450348836
DOIs	https://doi.org/10.1145/3026937.3026940
State	Published - Feb 4 2017
Event	8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017 - Austin, United States Duration: Feb 5 2017 → …

Publication series

Name	Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017

Conference

Conference	8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017
Country/Territory	United States
City	Austin
Period	02/5/17 → …

Funding

This material is based upon work supported by the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under Award Number DE-SC-0010042. G. Flegar and E. S. Quintana- Ortí were supported by project TIN2014-53495-R of the MINECO and FEDER.

Keywords

Block-Jacobi preconditioner
Gauss-Jordan elimination
Graphics processing units (GPUs)
Iterative methods
Matrix inversion
Sparse linear systems

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1145/3026937.3026940

Cite this

Anzt, H., Dongarra, J., Flegar, G., & Quintana-Ortí, E. S. (2017). Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs. In Q. Chen, & Z. Huang (Eds.), Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017 (pp. 1-10). Article 3026940 (Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017). Association for Computing Machinery, Inc. https://doi.org/10.1145/3026937.3026940

Anzt, Hartwig ; Dongarra, Jack ; Flegar, Goran et al. / Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs. Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017. editor / Quan Chen ; Zhiyi Huang. Association for Computing Machinery, Inc, 2017. pp. 1-10 (Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017).

@inproceedings{0b44b771227e4d30b6d0762441144cd3,

title = "Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs",

abstract = "In this paper, we design and evaluate a routine for the efficient generation of block-Jacobi preconditioners on graphics processing units (GPUs). Concretely, to exploit the architecture of the graphics accelerator, we develop a batched Gauss-Jordan elimination CUDA kernel for matrix inversion that embeds an implicit pivoting technique and handles the entire inversion process in the GPU registers. In addition, we integrate extraction and insertion CUDA kernels to rapidly set up the block-Jacobi preconditioner. Our experiments compare the performance of our implementation against a sequence of batched routines from the MAGMA library realizing the inversion via the LU factorization with partial pivoting. Furthermore, we evaluate the costs of different strategies for the block-Jacobi extraction and insertion steps, using a variety of sparse matrices from the SuiteSparse matrix collection. Finally, we assess the efficiency of the complete block-Jacobi preconditioner generation in the context of an iterative solver applied to a set of computational science problems, and quantify its benefits over a scalar Jacobi preconditioner.",

keywords = "Block-Jacobi preconditioner, Gauss-Jordan elimination, Graphics processing units (GPUs), Iterative methods, Matrix inversion, Sparse linear systems",

author = "Hartwig Anzt and Jack Dongarra and Goran Flegar and Quintana-Ort{\'i}, {Enrique S.}",

note = "Publisher Copyright: Copyright {\textcopyright} 2017 ACM.; 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017 ; Conference date: 05-02-2017",

year = "2017",

month = feb,

day = "4",

doi = "10.1145/3026937.3026940",

language = "English",

series = "Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017",

publisher = "Association for Computing Machinery, Inc",

pages = "1--10",

editor = "Quan Chen and Zhiyi Huang",

booktitle = "Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017",

}

Anzt, H, Dongarra, J, Flegar, G & Quintana-Ortí, ES 2017, Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs. in Q Chen & Z Huang (eds), Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017., 3026940, Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017, Association for Computing Machinery, Inc, pp. 1-10, 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017, Austin, United States, 02/5/17. https://doi.org/10.1145/3026937.3026940

Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs. / Anzt, Hartwig; Dongarra, Jack; Flegar, Goran et al.
Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017. ed. / Quan Chen; Zhiyi Huang. Association for Computing Machinery, Inc, 2017. p. 1-10 3026940 (Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017).

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

TY - GEN

T1 - Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs

AU - Anzt, Hartwig

AU - Dongarra, Jack

AU - Flegar, Goran

AU - Quintana-Ortí, Enrique S.

PY - 2017/2/4

Y1 - 2017/2/4

N2 - In this paper, we design and evaluate a routine for the efficient generation of block-Jacobi preconditioners on graphics processing units (GPUs). Concretely, to exploit the architecture of the graphics accelerator, we develop a batched Gauss-Jordan elimination CUDA kernel for matrix inversion that embeds an implicit pivoting technique and handles the entire inversion process in the GPU registers. In addition, we integrate extraction and insertion CUDA kernels to rapidly set up the block-Jacobi preconditioner. Our experiments compare the performance of our implementation against a sequence of batched routines from the MAGMA library realizing the inversion via the LU factorization with partial pivoting. Furthermore, we evaluate the costs of different strategies for the block-Jacobi extraction and insertion steps, using a variety of sparse matrices from the SuiteSparse matrix collection. Finally, we assess the efficiency of the complete block-Jacobi preconditioner generation in the context of an iterative solver applied to a set of computational science problems, and quantify its benefits over a scalar Jacobi preconditioner.

AB - In this paper, we design and evaluate a routine for the efficient generation of block-Jacobi preconditioners on graphics processing units (GPUs). Concretely, to exploit the architecture of the graphics accelerator, we develop a batched Gauss-Jordan elimination CUDA kernel for matrix inversion that embeds an implicit pivoting technique and handles the entire inversion process in the GPU registers. In addition, we integrate extraction and insertion CUDA kernels to rapidly set up the block-Jacobi preconditioner. Our experiments compare the performance of our implementation against a sequence of batched routines from the MAGMA library realizing the inversion via the LU factorization with partial pivoting. Furthermore, we evaluate the costs of different strategies for the block-Jacobi extraction and insertion steps, using a variety of sparse matrices from the SuiteSparse matrix collection. Finally, we assess the efficiency of the complete block-Jacobi preconditioner generation in the context of an iterative solver applied to a set of computational science problems, and quantify its benefits over a scalar Jacobi preconditioner.

KW - Block-Jacobi preconditioner

KW - Gauss-Jordan elimination

KW - Graphics processing units (GPUs)

KW - Iterative methods

KW - Matrix inversion

KW - Sparse linear systems

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

U2 - 10.1145/3026937.3026940

DO - 10.1145/3026937.3026940

M3 - Conference contribution

AN - SCOPUS:85015196391

T3 - Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017

SP - 1

EP - 10

BT - Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017

A2 - Chen, Quan

A2 - Huang, Zhiyi

PB - Association for Computing Machinery, Inc

T2 - 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017

Y2 - 5 February 2017

ER -

Anzt H, Dongarra J, Flegar G, Quintana-Ortí ES. Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs. In Chen Q, Huang Z, editors, Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017. Association for Computing Machinery, Inc. 2017. p. 1-10. 3026940. (Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2017). doi: 10.1145/3026937.3026940

Batched gauss-jordan elimination for block-jacobi preconditioner generation on GPUs

Abstract

Publication series

Conference

Funding

Keywords

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this