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

Abstract

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.