Parallel dense gauss-seidel algorithm on many-core processors

Hadrien Courtecuisse 1 Jérémie Allard 1
1 SHACRA - Simulation in Healthcare using Computer Research Advances
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, Inria Nancy - Grand Est
Abstract : The Gauss-Seidel method is very efficient for solving problems such as tightly-coupled constraints with possible redundancies. However, the underlying algorithm is inherently sequential. Previous works have exploited sparsity in the system matrix to extract parallelism. In this paper, we propose to study several parallelization schemes for fully-coupled systems, unable to be parallelized by existing methods, taking advantage of recent many-cores architectures offering fast synchronization primitives. Experimental results on both multi-core CPUs and recent GPUs show that our proposed method is able to fully exploit the available units, whereas trivial parallel algorithms often fail. This method is illustrated by an application in medical intervention planning, where it is used to solve a linear complementary problem (LCP) expressing the contacts applied to a deformable body.
Type de document :
Communication dans un congrès
HPCC'09 - 11th IEEE International Conference on High Performance Computing and Communications - 2009, Jun 2009, Seoul, South Korea. IEEE, pp.139--147, 2009, 〈10.1109/HPCC.2009.51〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00841571
Contributeur : Jeremie Dequidt <>
Soumis le : vendredi 5 juillet 2013 - 10:45:47
Dernière modification le : jeudi 11 janvier 2018 - 06:24:22

Identifiants

Collections

Citation

Hadrien Courtecuisse, Jérémie Allard. Parallel dense gauss-seidel algorithm on many-core processors. HPCC'09 - 11th IEEE International Conference on High Performance Computing and Communications - 2009, Jun 2009, Seoul, South Korea. IEEE, pp.139--147, 2009, 〈10.1109/HPCC.2009.51〉. 〈hal-00841571〉

Partager

Métriques

Consultations de la notice

201