Dense symmetric indefinite factorization on GPU accelerated architectures

Marc Baboulin; Jack Dongarra; Adrien Rémy; Stanimire Tomov; Ichitaro Yamazaki

doi:10.1007/978-3-319-32149-3_9

Dense symmetric indefinite factorization on GPU accelerated architectures

Marc Baboulin, Jack Dongarra, Adrien Rémy, Stanimire Tomov, Ichitaro Yamazaki

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

5 Scopus citations

Abstract

We study the performance of dense symmetric indefinite factorizations (Bunch-Kaufman and Aasen’s algorithms) on multicore CPUs with a Graphics Processing Unit (GPU). Though such algorithms are needed in many scientific and engineering simulations, obtaining high performance of the factorization on the GPU is difficult because the pivoting that is required to ensure the numerical stability of the factorization leads to frequent synchronizations and irregular data accesses. As a result, until recently, there has not been any implementation of these algorithms on hybrid CPU/GPU architectures. To improve their performance on the hybrid architecture, we explore different techniques to reduce the expensive communication and synchronization between the CPU and GPU, or on the GPU. We also study the performance of an LDLT factorization with no pivoting combined with the preprocessing technique based on Random Butterfly Transformations. Though such transformations only have probabilistic results on the numerical stability, they avoid the pivoting and obtain a great performance on the GPU.

Original language	English
Title of host publication	Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers
Editors	Ewa Deelman, Jack Dongarra, Konrad Karczewski, Roman Wyrzykowski, Jacek Kitowski, Kazimierz Wiatr
Publisher	Springer Verlag
Pages	86-95
Number of pages	10
ISBN (Print)	9783319321486
DOIs	https://doi.org/10.1007/978-3-319-32149-3_9
State	Published - 2016
Externally published	Yes
Event	11th International Conference on Parallel Processing and Applied Mathematics, PPAM 2015 - Krakow, Poland Duration: Sep 6 2015 → Sep 9 2015

Publication series

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

Conference

Conference	11th International Conference on Parallel Processing and Applied Mathematics, PPAM 2015
Country/Territory	Poland
City	Krakow
Period	09/6/15 → 09/9/15

Funding

The authors would like to thank the NSF grant #ACI-1339822, NVIDIA, and MathWorks for supporting this research effort. The authors are also grateful to Nicolas Zerbib (ESI Group) for his help in using test matrices from acoustics.

Keywords

Communicationavoiding
Dense symmetric indefinite factorization
GPU computation
Randomization

Access to Document

10.1007/978-3-319-32149-3_9

Cite this

Baboulin, M., Dongarra, J., Rémy, A., Tomov, S., & Yamazaki, I. (2016). Dense symmetric indefinite factorization on GPU accelerated architectures. In E. Deelman, J. Dongarra, K. Karczewski, R. Wyrzykowski, J. Kitowski, & K. Wiatr (Eds.), Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers (pp. 86-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9573). Springer Verlag. https://doi.org/10.1007/978-3-319-32149-3_9

Baboulin, Marc ; Dongarra, Jack ; Rémy, Adrien et al. / Dense symmetric indefinite factorization on GPU accelerated architectures. Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers. editor / Ewa Deelman ; Jack Dongarra ; Konrad Karczewski ; Roman Wyrzykowski ; Jacek Kitowski ; Kazimierz Wiatr. Springer Verlag, 2016. pp. 86-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{747c713428fa45e2ab724b7a206eb945,

title = "Dense symmetric indefinite factorization on GPU accelerated architectures",

abstract = "We study the performance of dense symmetric indefinite factorizations (Bunch-Kaufman and Aasen{\textquoteright}s algorithms) on multicore CPUs with a Graphics Processing Unit (GPU). Though such algorithms are needed in many scientific and engineering simulations, obtaining high performance of the factorization on the GPU is difficult because the pivoting that is required to ensure the numerical stability of the factorization leads to frequent synchronizations and irregular data accesses. As a result, until recently, there has not been any implementation of these algorithms on hybrid CPU/GPU architectures. To improve their performance on the hybrid architecture, we explore different techniques to reduce the expensive communication and synchronization between the CPU and GPU, or on the GPU. We also study the performance of an LDLT factorization with no pivoting combined with the preprocessing technique based on Random Butterfly Transformations. Though such transformations only have probabilistic results on the numerical stability, they avoid the pivoting and obtain a great performance on the GPU.",

keywords = "Communicationavoiding, Dense symmetric indefinite factorization, GPU computation, Randomization",

author = "Marc Baboulin and Jack Dongarra and Adrien R{\'e}my and Stanimire Tomov and Ichitaro Yamazaki",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 11th International Conference on Parallel Processing and Applied Mathematics, PPAM 2015 ; Conference date: 06-09-2015 Through 09-09-2015",

year = "2016",

doi = "10.1007/978-3-319-32149-3_9",

language = "English",

isbn = "9783319321486",

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

publisher = "Springer Verlag",

pages = "86--95",

editor = "Ewa Deelman and Jack Dongarra and Konrad Karczewski and Roman Wyrzykowski and Jacek Kitowski and Kazimierz Wiatr",

booktitle = "Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers",

}

Baboulin, M, Dongarra, J, Rémy, A, Tomov, S & Yamazaki, I 2016, Dense symmetric indefinite factorization on GPU accelerated architectures. in E Deelman, J Dongarra, K Karczewski, R Wyrzykowski, J Kitowski & K Wiatr (eds), Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9573, Springer Verlag, pp. 86-95, 11th International Conference on Parallel Processing and Applied Mathematics, PPAM 2015, Krakow, Poland, 09/6/15. https://doi.org/10.1007/978-3-319-32149-3_9

Dense symmetric indefinite factorization on GPU accelerated architectures. / Baboulin, Marc; Dongarra, Jack; Rémy, Adrien et al.
Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers. ed. / Ewa Deelman; Jack Dongarra; Konrad Karczewski; Roman Wyrzykowski; Jacek Kitowski; Kazimierz Wiatr. Springer Verlag, 2016. p. 86-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9573).

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

TY - GEN

T1 - Dense symmetric indefinite factorization on GPU accelerated architectures

AU - Baboulin, Marc

AU - Dongarra, Jack

AU - Rémy, Adrien

AU - Tomov, Stanimire

AU - Yamazaki, Ichitaro

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - We study the performance of dense symmetric indefinite factorizations (Bunch-Kaufman and Aasen’s algorithms) on multicore CPUs with a Graphics Processing Unit (GPU). Though such algorithms are needed in many scientific and engineering simulations, obtaining high performance of the factorization on the GPU is difficult because the pivoting that is required to ensure the numerical stability of the factorization leads to frequent synchronizations and irregular data accesses. As a result, until recently, there has not been any implementation of these algorithms on hybrid CPU/GPU architectures. To improve their performance on the hybrid architecture, we explore different techniques to reduce the expensive communication and synchronization between the CPU and GPU, or on the GPU. We also study the performance of an LDLT factorization with no pivoting combined with the preprocessing technique based on Random Butterfly Transformations. Though such transformations only have probabilistic results on the numerical stability, they avoid the pivoting and obtain a great performance on the GPU.

AB - We study the performance of dense symmetric indefinite factorizations (Bunch-Kaufman and Aasen’s algorithms) on multicore CPUs with a Graphics Processing Unit (GPU). Though such algorithms are needed in many scientific and engineering simulations, obtaining high performance of the factorization on the GPU is difficult because the pivoting that is required to ensure the numerical stability of the factorization leads to frequent synchronizations and irregular data accesses. As a result, until recently, there has not been any implementation of these algorithms on hybrid CPU/GPU architectures. To improve their performance on the hybrid architecture, we explore different techniques to reduce the expensive communication and synchronization between the CPU and GPU, or on the GPU. We also study the performance of an LDLT factorization with no pivoting combined with the preprocessing technique based on Random Butterfly Transformations. Though such transformations only have probabilistic results on the numerical stability, they avoid the pivoting and obtain a great performance on the GPU.

KW - Communicationavoiding

KW - Dense symmetric indefinite factorization

KW - GPU computation

KW - Randomization

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

U2 - 10.1007/978-3-319-32149-3_9

DO - 10.1007/978-3-319-32149-3_9

M3 - Conference contribution

AN - SCOPUS:84968538231

SN - 9783319321486

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

SP - 86

EP - 95

BT - Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers

A2 - Deelman, Ewa

A2 - Dongarra, Jack

A2 - Karczewski, Konrad

A2 - Wyrzykowski, Roman

A2 - Kitowski, Jacek

A2 - Wiatr, Kazimierz

PB - Springer Verlag

T2 - 11th International Conference on Parallel Processing and Applied Mathematics, PPAM 2015

Y2 - 6 September 2015 through 9 September 2015

ER -

Baboulin M, Dongarra J, Rémy A, Tomov S, Yamazaki I. Dense symmetric indefinite factorization on GPU accelerated architectures. In Deelman E, Dongarra J, Karczewski K, Wyrzykowski R, Kitowski J, Wiatr K, editors, Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015, Revised Selected Papers. Springer Verlag. 2016. p. 86-95. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-32149-3_9

Dense symmetric indefinite factorization on GPU accelerated architectures

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this