Abstract FR:

Cette thèse constitue un début d'analyses sur les implantations d'algorithmes parallèles de traitement de graphes. Notre approche est originale dans la mesure où elle consiste d'une part à proposer de nouveaux algorithmes et d'autre part à étudier expérimentalement dans plusieurs environnements parallèles les comportements de ces algorithmes ainsi que d'un certain nombre d'algorithmes déjà connus. Ceci permet de mettre en évidence les possibilités et les limites des algorithmes parallèles de traitement de graphes et de leur implantation. Apres avoir choisi le modelé parallèle à gros grain CGM (coarse grained multicomputer), nous avons étudié et implante les algorithmes CGM de la somme parallèle préfixe, du tri, du classement de liste, du calcul des composantes connexes pour les graphes denses, du calcul du nombre d'arcs entrants pour les graphes de permutation, des calculs de la clique de poids maximum et des composantes connexes pour les graphes d'intervalles. Nous avons proposé de nouveaux algorithmes pour le classement de liste et les deux problèmes sur les graphes d'intervalles. Toutes les implantations ont été réalisées sur deux graphes de PCS et un t3e. Le code utilise le langage c++ et la bibliothèque de communications PVM. Il est basé sur une bibliothèque appelée CGM que nous avons construite lors de cette thèse pour simplifier la mise en œuvre des implantations CGM. Nous montrons pratiquement que les modèles à gros grain comme le modèle CGM permettent d'écrire du code portable, prédictif et en partie efficace pour les problèmes que nous avons traités dans cette thèse. Le seul algorithme problématique est le classement de liste, ce qui nous laisse penser qu'il reste encore beaucoup de travail à réaliser sur le classement de liste, mais aussi sur tous les algorithmes de graphes basés sur le classement de liste.