Etude et implémentation de la parallélisation de la méthode de Jacobi sur machines parallèles à mémoire distribuée

Abstract

Les travaux présentés dans cette thèse sont consacrés à l’étude et à l’implémentation, sur machine parallèles à mémoire distribuée, de la méthode de Jacobi pour le calcul des valeurs et des vecteurs propres d’une matrice carrée, réelle et symétrique. Ce travail est essentiellement axé sur le problème de recouvrement calcul/communication, qui est un problème crucial pour les machines à mémoire distribuée, et sur l’exploitation de la symétrie dans cette méthode afin de réduire le temps d’exécution Tout d’abord, nous avons fait une étude théorique de la parallélisation de la méthode de Jacobi dite méthode à deux faces dans cette étude, nous avons proposé un nouvel algorithme parallèle et général qui permet l’exploitation de la symétrie. Avec ce nouvel algorithme parallèle, nous avons pu réduire le temps des communications entre les processeurs en éliminant la phase d’ajustement des données lors de la phase de commérage des rotations qui est la phase la plus coûteuse en terme de communication dans l’algorithme Ensuite, nous avons étudié la parallélisation de la méthode de Jacobi dite méthode à une seule face nous avons développé des algorithmes parallèles, dans le cas par points et dans le cas par blocs pour diminuer les surcoûts dus aux communications entre les processeurs, nous avons utilisé deux stratégies qui permettent de recouvrir les communications par les calculs. La première stratégie consiste à effectuer des mises à jour lors des translations des données (colonnes ou blocs de colonnes), tandis que la deuxième stratégie consiste à utiliser la technique de découpage en paquets de tailles optimales. Les implémentations des algorithmes développés dans cette thèse ont été faites sous l’environnement de programmation parallèles C/MPI, sur le i-Cluster de PCs installé à l’IMAG-Grenoble en France, et sous l’environnement de programmation parallèle C/PVM, sur la TN310 installé dans notre laboratoire LarRI-Oujda.