Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Doctorat de KHABOU Amal
KHABOU Amal
Doctorat
Equipe : Parallélisme

Etude des algorithmes parallèles minimisant les communications

Début le 01/10/2009
Direction : GRIGORI, Laura

Financement : A
Etablissement d'inscription : Université Paris-Sud
Lieu de déroulement : LRI - GRAND LARGE

Soutenue le 11/02/2013 devant le jury composé de :
Nicholas Higham (Rapporteur), Professeur, School of Mathematics, the University of Manchester
Yves Robert (Rapporteur), Professeur, Ecole Normale Supérieure de Lyon

Iain Duff (Examinateur), Professeur, the University of Strathclde
Yannis Manoussakis (Examinateur), Professeur, Université Paris Sud
Jean-Louis Roch (Examinateur), Maître de Conférences, IMAG

Laura Grigori (Directeur de thèse), Directeur de Recherche, INRIA

Activités de recherche :

Résumé :
Cette thèse traite d’une routine d’algèbre linéaire largement utilisée pour la résolution des
systèmes linéaires, il s’agit de la factorisation LU. Habituellement, pour calculer une telle
décomposition, on utilise l’élimination de Gauss avec pivotage partiel (GEPP). La stabilité numérique
de l’élimination de Gauss avec pivotage partiel est caractérisée par un facteur de croissance qui est
reste assez petit en pratique. Toutefois, la version parallèle de cet algorithme ne permet pas d’atteindre
les bornes inférieures qui caractérisent le coût de communication pour un algorithme donné. En effet, la
factorisation d’un bloc de colonnes constitue un goulot d’étranglement en termes de communication.

Pour remédier à ce problème, Grigori et al ont développé une factorisation LU qui minimise la
communication(CALU) au prix de quelques calculs redondants. En théorie la borne supérieure du
facteur de croissance de CALU est plus grande que celle de l’élimination de Gauss avec pivotage
partiel, cependant CALU est stable en pratique. Pour améliorer la borne supérieure du facteur de
croissance, nous étudions une nouvelle stratégie de pivotage utilisant la factorisation QR avec forte
révélation de rang. Ainsi nous développons un nouvel algorithme pour la factorisation LU par blocs. La
borne supérieure du facteur de croissance de cet algorithme est plus petite que celle de l’élimination de
Gauss avec pivotage partiel. Cette stratégie de pivotage est ensuite combinée avec le pivotage basé
sur un tournoi pour produire une factorisation LU qui minimise la communication et qui est plus stable
que CALU. Pour les systèmes hiérarchiques, plusieurs niveaux de parallélisme sont disponibles.
Cependant, aucune des méthodes précédemment citées n’exploite pleinement ces ressources. Nous
proposons et étudions alors deux algorithmes récursifs qui utilisent les mêmes principes que CALU
mais qui sont plus appropriés pour des architectures à plu- sieurs niveaux de parallélisme. Pour
analyser d’une façon précise et réaliste les coûts de ces algorithmes hiérarchiques, nous introduisons
un modèle de performance hiérarchique parallèle qui prend en compte aussi bien l’organisation
hiérarchique des processeurs et la hiérarchie réseau. Cette analyse nous permet de prédire d’une
manière réaliste la performance de ces factorisations hiérarchiques sur une plate-forme exascale.