en fr Solving dense linear systems on accelerated multicore architectures Résoudre des systèmes linéaires denses sur des architectures composées de processeurs multicœurs et d’accélerateurs Report as inadecuate




en fr Solving dense linear systems on accelerated multicore architectures Résoudre des systèmes linéaires denses sur des architectures composées de processeurs multicœurs et d’accélerateurs - Download this document for free, or read online. Document in PDF available to download.

1 LRI - Laboratoire de Recherche en Informatique 2 POSTALE - Performance Optimization by Software Transformation and Algorithms & Librairies Enhancement LRI - Laboratoire de Recherche en Informatique, Inria Saclay - Ile de France

Abstract : In this PhD thesis, we study algorithms and implementations to accelerate the solution of dense linear systems by using hybrid architectures with multicore processors and accelerators. We focus on methods based on the LU factorization and our code development takes place in the context of the MAGMA library. We study different hybrid CPU-GPU solvers based on the LU factorization which aim at reducing the communication overhead due to pivoting. The first one is based on a communication avoiding strategy of pivoting CALU while the second uses a random preconditioning of the original system to avoid pivoting RBT. We show that both of these methods outperform the solver using LU factorization with partial pivoting when implemented on hybrid multicore-GPUs architectures. We also present new solvers based on randomization for hybrid architectures for Nvidia GPU or Intel Xeon Phi coprocessor. With this method, we can avoid the high cost of pivoting while remaining numerically stable in most cases. The highly parallel architecture of these accelerators allow us to perform the randomization of our linear system at a very low computational cost compared to the time of the factorization. Finally we investigate the impact of non-uniform memory accesses NUMA on the solution of dense general linear systems using an LU factorization algorithm. In particular we illustrate how an appropriate placement of the threads and data on a NUMA architecture can improve the performance of the panel factorization and consequently accelerate the global LU factorization. We show how these placements can improve the performance when applied to hybrid multicore-GPU solvers.

Résumé : Dans cette thèse de doctorat, nous étudions des algorithmes et des implémentations pour accélérer la résolution de systèmes linéaires denses en utilisant des architectures composées de processeurs multicœurs et d-accélérateurs. Nous nous concentrons sur des méthodes basées sur la factorisation LU. Le développement de notre code s-est fait dans le contexte de la bibliothèque MAGMA. Tout d-abord nous étudions différents solveurs CPU-GPU hybrides basés sur la factorisation LU. Ceux-ci visent à réduire le surcoût de communication dû au pivotage. Le premier est basé sur une stratégie de pivotage dite -communication avoiding- CALU alors que le deuxième utilise un préconditionnement aléatoire du système original pour éviter de pivoter RBT. Nous montrons que ces deux méthodes surpassent le solveur utilisant la factorisation LU avec pivotage partiel quand elles sont utilisées sur des architectures hybrides multicœurs-GPUs. Ensuite nous développons des solveurs utilisant des techniques de randomisation appliquées sur des architectures hybrides utilisant des GPU Nvidia ou des coprocesseurs Intel Xeon Phi. Avec cette méthode, nous pouvons éviter l-important surcoût du pivotage tout en restant stable numériquement dans la plupart des cas. L-architecture hautement parallèle de ces accélérateurs nous permet d-effectuer la randomisation de notre système linéaire à un coût de calcul très faible par rapport à la durée de la factorisation. Finalement, nous étudions l-impact d-accès mémoire non uniformes NUMA sur la résolution de systèmes linéaires denses en utilisant un algorithme de factorisation LU. En particulier, nous illustrons comment un placement approprié des processus légers et des données sur une architecture NUMA peut améliorer les performances pour la factorisation du panel et accélérer de manière conséquente la factorisation LU globale. Nous montrons comment ces placements peuvent améliorer les performances quand ils sont appliqués à des solveurs hybrides multicœurs-GPU.

en fr

Keywords : Thread placement Randomization Communication-avoiding algorithms . ccNUMA Intel Xeon Phi Graphics process units Hybrid multicore-GPU computing MAGMA library Dense linear algebra libraries LU factorization Dense linear systems

Mots-clés : Communication-avoiding Processeurs graphiques Calcul hybride multicœur-GPU Bibliothèque MAGMA Bibliothèques logicielles pour l’algèbre linéaire dense Factorisation LU Systèmes linéaires denses Randomisation Placement des processus légers





Author: Adrien Rémy -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents