Comparison of initial partitioning methods for multilevel direct k-way graph partitioning with fixed vertices

Abstract : In scientific computing, load balancing is a crucial step conditioning the performance of large-scale applications. In this case, an efficient decomposition of the workload to a number of processors is highly necessary. A common approach to solve this problem is to use graph representation and perform a graph partitioning in k parts using the multilevel framework and the recursive bisection (RB) paradigm. However, in graph instances where fixed vertices are used to model additional constraints, RB often produces partitions of poor quality.In this paper, we investigate the difficulties of RB to handle fixed vertices and we compare its results with two different alternatives. The first one, called KGGGP is a direct k-way greedy graph growing partitioning that properly handles fixed vertices while the second one, introduced in kPaToH, uses RB and a post-processing technique to correct the obtained partition. Finally, experimental results on graphs that represent real-life numerical simulations show that both alternative methods provide improved partitions compared to RB.
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01538600
Contributeur : Aurélien Esnard <>
Soumis le : mercredi 14 juin 2017 - 10:20:01
Dernière modification le : jeudi 11 janvier 2018 - 06:22:35
Document(s) archivé(s) le : mardi 12 décembre 2017 - 14:16:55

Fichier

parco16.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales 4.0 International License

Identifiants

Collections

Citation

Maria Predari, Aurélien Esnard, Jean Roman. Comparison of initial partitioning methods for multilevel direct k-way graph partitioning with fixed vertices. Parallel Computing, Elsevier, 2017, 〈10.1016/j.parco.2017.05.002〉. 〈hal-01538600〉

Partager

Métriques

Consultations de la notice

268

Téléchargements de fichiers

125