Toward a scalable refinement strategy for multilevel graph repartitioning
Résumé
Dynamic load balancing is a mandatory feature for parallel software whose workload evolves with time, such as solvers implementing adaptive mesh refinement. In such solvers, problem space is most often represented as an unstructured mesh, and graph partitioning is used to distribute data and their associated computations across processes. The purpose of this paper is to study the sequential version of a set of graph repartitioning methods and to propose a scalable strategy for parallel graph repartitioning. As the repartitioning methods have been adapted from existing algorithms that are used for parallel partitioning, we will also be able to discuss their parallel behaviors. These methods can be combined in several ways, leading to either multilevel diffusion-based or biased scratch-remap frameworks. The proposed repartitioning framework uses a global diffusion-based algorithm for partition refinement, which may prove a good replacement for Fiduccia-Mattheyses type algorithms as it is inherently parallel. This algorithm yields best results when used in a multilevel framework. To validate our approach, we compare our sequential graph repartitioning implementation within the Scotch software to the ParMeTiS graph repartitioning tool.
L'équilibrage dynamique de la charge est une fonctionnalité indispensable aux applications parallèles dont la quantité de calcul évolue en fonction du temps, tels les solveurs utilisant du raffinement de maillage. Dans le cas de ces solveurs, l'espace du problème est le plus souvent représenté par un maillage non structuré et l'on utilise le partitionnement de graphes afin de distribuer sur les processeurs les données et les calculs associés. L'objectif de cet article est d'étudier la version séquentielle d'un ensemble de méthodes de repartitionnement de graphes et de proposer une stratégie scalable pour le repartitionnement parallèle de graphes. Étant donné que ces méthodes de repartitionnement ont été adaptées à partir d'algorithmes existants utilisés pour le partitionnement parallèle, nous aborderons aussi leur comportement parallèle. Ces méthodes peuvent être combinées de plusieurs manières, aboutissant à des plateformes de repartitionnement basées soit sur une diffusion multi-niveaux, soit sur une méthode de type scratch-remap biaisée. La plateforme de repartitionnement que nous proposons utilise un algorithme de diffusion global pour le raffinement de partitions. Celui-ci, du fait qu'il est intrinséquement parallèle, pourrait constituer un bon remplaçant des algorithmes de type Fiduccia-Mattheyses. Cet algorithme donne de meilleurs résultats lorsqu'il est utilisé au sein d'un schéma multi-niveaux. Afin de valider notre approche, nous comparons notre implémentation d'algorithmes de repartitionnement séquentiel de graphes, réalisée au sein du logiciel Scotch, au logiciel de repartitionnement de graphes ParMeTiS.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...