Contribution à l'algorithmique numérique parallèle

Abstract

Dans cette thèse, nous nous intéressons, d’une part à l’étude de la parallélisation de la méthode de Jacobi pour le calcul des valeurs et des vecteurs propres d’une matrice A carrée, réelle et symétrique et d’autre part à la parallélisation des graphes de tâches grilles 2D et 3D. Dans le premier chapitre, nous faisons une introduction générale au parallélisme et aux architectures parallèles. La parallélisation de la méthode de Jacobi fait l’objet des chapitres 2, 3 et 4. Dans le chapitre 2, nous proposons une technique qui permet de recouvrir les communications par le calcul, lors de la parallélisation de la méthode de Jacobi à deux faces. Dans le chapitre 3, nous donnons une nouvelle distribution des données qui permet d’exploiter la symétrie de A et diminue le temps de communication pendant la phase de translation des colonnes. Le chapitre 4, est consacré à l’étude de la parallélisation de la méthode de Jacobi à une seule face où nous donnons une stratégie qui permet le recouvrement des communications par le calcul. Dans le chapitre 5 , nous étudions la complexité de la parallélisation des graphes de tâches grille 2D et 3D. pour les graphes de tâches grille 2D nous donnons une borne inférieure du temps d’exécution parallèle et nous montrons que cette borne peut être atteinte sur un anneau de processeurs. Les résultats que nous obtenons, généralisent ceux obtenus dans la littérature. Pour les graphes de tâches grille 3D, une étude partielle a été faite et nous pensons que les résultats obtenus pour les graphes de tâches grille 2D peuvent être étendues aux graphes de tâches grille 3D.