Solving dense symmetric indefinite systems using GPUs

Abstract : This paper studies the performance of different algorithms for solving a dense symmetric indefinite linear system of equations on multicore CPUs with a Graphics Processing Unit (GPU). To ensure the numerical stability of the factorization, pivoting is required. Obtaining high performance of such algorithms on the GPU is difficult because all the existing pivoting strategies lead to frequent synchronizations and irregular data accesses. Until recently, there has not been any implementation of these algorithms on a hybrid CPU/GPU architecture. To improve their performance on the hybrid architecture, we explore different techniques to reduce the expensive data transfer and synchronization between the CPU and GPU, or on the GPU (e.g., factorizing the matrix entirely on the GPU or in a communication-avoiding fashion). We also study the performance of the solver using iterative refinements along with the factorization without pivoting combined with the preprocessing technique based on Random Butterfly Transformations, or with the mixed-precision algorithm where the matrix is factorized in single precision. This randomization algorithm only has a probabilistic proof on the numerical stability, and for this paper, we only focused on the mixed-precision algorithm without pivoting. However, they demonstrate that we can obtain good performance on the GPU by avoiding the pivoting and using the lower precision arithmetics, respectively. As illustrated with the application in acoustics studied in this paper, in many practical cases, the matrices can be factorized without pivoting. Since the componentwise backward error computed in the iterative refinement signals when the algorithm failed to obtain the desired accuracy, the user can use these potentially-unstable but efficient algorithms in most of the cases, and fall back to a more stable algorithm with pivoting only in the case of the failure.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2017, 29 (9), pp.1 - 17. 〈10.1002/cpe.4055〉
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger
Contributeur : Marc Baboulin <>
Soumis le : samedi 20 janvier 2018 - 09:27:54
Dernière modification le : mardi 24 avril 2018 - 13:34:14
Document(s) archivé(s) le : jeudi 24 mai 2018 - 01:40:07


Fichiers produits par l'(les) auteur(s)



Marc Baboulin, Jack Dongarra, Adrien Rémy, Stanimire Tomov, Ichitaro Yamazaki. Solving dense symmetric indefinite systems using GPUs. Concurrency and Computation: Practice and Experience, Wiley, 2017, 29 (9), pp.1 - 17. 〈10.1002/cpe.4055〉. 〈hal-01662358〉



Consultations de la notice


Téléchargements de fichiers