Toward a scalable refinement strategy for multilevel graph repartitioning

Sébastien Fourestier 1, 2 François Pellegrini 1, 2
2 BACCHUS - Parallel tools for Numerical Algorithms and Resolution of essentially Hyperbolic problems
Inria Bordeaux - Sud-Ouest, UB - Université de Bordeaux, CNRS - Centre National de la Recherche Scientifique : UMR5800
Résumé : 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.
Type de document :
Rapport
[Research Report] RR-8246, INRIA. 2013, pp.22
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00790378
Contributeur : Sébastien Fourestier <>
Soumis le : vendredi 22 février 2013 - 11:35:18
Dernière modification le : jeudi 11 janvier 2018 - 06:22:35
Document(s) archivé(s) le : dimanche 2 avril 2017 - 02:46:18

Fichier

RR-8246.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00790378, version 1

Collections

Citation

Sébastien Fourestier, François Pellegrini. Toward a scalable refinement strategy for multilevel graph repartitioning. [Research Report] RR-8246, INRIA. 2013, pp.22. 〈hal-00790378〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

228