Doctorat
Equipe : Parallélisme
Methods and algorithms for solving linear systems of equations on massively parallel computers
Début le 09/01/2008
Direction : GRIGORI, Laura
Ecole doctorale :
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LRI
Soutenue le 07/03/2012 devant le jury composé de :
Examinateurs:
Yannis Manoussakis, Professeur, Université de paris 11 Orsay France
Jack Dongarra, Professeur, Université de Tennessee USA
Thomas Guignon, Ingénieur, IFP France
Rapporteurs:
Raymond Namyst, Professeur, LaBRI Université de bordeaux I France
Frédéric Desprez, Directeur de recherche, LIP, ENS Lyon France
Directeur de thèse:
Laura Grigori, Chargé de recherche, Université de paris 11 Orsay France
Activités de recherche :
Résumé :
Les processeurs multi-cœurs sont considérés de nos jours comme l'avenir des calculateurs et auront un impact important dans le calcul scientifique. Cette thèse présente une nouvelle approche de résolution des grands systèmes linéaires creux et denses, qui soit adaptée à l'exécution sur les futures machines pétaflopiques. Compte tenu du coût croissant des communications comparé au temps dont les processeurs mettent pour effectuer les opérations arithmétiques, notre approche adopte le principe de minimisation des communications au prix de quelques calculs redondants et utilise plusieurs adaptations pour atteindre de meilleures performances sur les machines multi-cœurs.
Nous décomposons le problème à résoudre en plusieurs phases qui sont ensuite mises en œuvre séparément. Dans la première partie, nous présentons un algorithme basé sur le partitionnement d'hypergraphe qui réduit considérablement le remplissage ("fill-in") induit lors de la factorisation LU des matrices creuses non symétriques. Dans la deuxième partie, nous présentons deux algorithmes de réduction de communications pour les factorisations LU et QR qui sont adaptés aux environnements multi-cœurs. La principale contribution de cette partie est de réorganiser les opérations de la factorisation de manière à réduire la sollicitation du bus tout en utilisant de façon optimale les ressources. Nous étendons ensuite ce travail aux clusters de processeurs multi-cœurs. Dans la troisième partie, Nous présentons l'utilisation d'une stratégie d'ordonnancement et d'optimisation qui utilise une approche combinant un ordonnancement statique et dynamique du graphe de dépendance de tâches. Cette stratégie établit un équilibre de la localité de données, l'équilibrage de charges et peut s'adapter aux changements dynamiques dans le système.
Nos résultats obtenus sur plusieurs architectures montrent que tous nos algorithmes sont efficaces et conduisent à des gains de performances significatifs. Nous pouvons atteindre des améliorations de l'ordre de 30 à 110% par rapport aux correspondants de nos algorithmes dans les bibliothèques numériques bien connues de la littérature.
