Adaptation au repartitionnement de graphes d'une méthode d'optimisation globale par diffusion

Sébastien Fourestier (1) , François Pellegrini (2, 1)

1 BACCHUS - Parallel tools for Numerical Algorithms and Resolution of essentially Hyperbolic problems
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

La résolution parallèle efficace de simulations numériques dont les coûts de calcul évoluent au cours du temps (telles que celles mettant en oeuvre un remaillage dynamique) nécessite des méthodes efficaces de redistribution des données attribuées à chaque processeur. L'objet de cet article est d'étudier l'adaptation au repartitionnement de graphes, qui est un modèle courant du problème de redistribution des données, d'un ensemble d'algorithmes utilisés avec succès dans le cadre du partitionnement parallèle de graphes, et tout particulièrement d'un algorithme d'optimisation globale de la forme des partitions par diffusion. Le modèle expérimental exposé ici est séquentiel,mais les algorithmes présentés peuvent facilement être transposés en parallèle. Afin de valider notre approche, nous comparons nos résultats, implémentés au sein du logiciel SCOTCH, à la routine de repartitionnement mise en oeuvre au sein du logiciel ParMETIS.

Mots clés: repartionnement de graphes; raffinement par diffusion; partitionnement biaisé

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Sébastien Fourestier, François Pellegrini. Adaptation au repartitionnement de graphes d'une méthode d'optimisation globale par diffusion. Rencontres Francophones du Parallélisme, May 2011, Saint-Malo, France. 8 p. ⟨hal-00648735⟩