Hypergraph partitioning for multiple communication cost metrics: Model and methods

Abstract : We investigate hypergraph partitioning-based methods for efficient paralleliza-tion of communicating tasks. A good partitioning method should divide the load among the processors as evenly as possible and minimize the inter-processor communication overhead. The total communication volume is the most popular communication overhead metric which is reduced by the existing state-of-the-art hypergraph partitioners. However, other metrics such as the total number of messages, the maximum amount of data transferred by a processor, or a combination of them are equally, if not more, important. Existing hypergraph-based solutions use a two phase approach to minimize such metrics where in each phase, they minimize a different metric, sometimes at the expense of others. We propose a one-phase approach where all the communication cost metrics can be effectively minimized in a multi-objective setting and reductions can be achieved for all metrics together. For an accurate modeling of the maximum volume and the number of messages sent and received by a processor, we propose the use of directed hypergraphs. The directions on hyperedges necessitate revisiting the standard partitioning heuristics. We do so and propose a multi-objective, multi-level hypergraph partitioner called UMPa. The partitioner takes various prioritized communication metrics into account, and optimizes all of them together in the same phase. Compared to the state-of-the-art methods which only minimize the total communication volume, we show on a large number of problem instances that UMPa produces better partitions in terms of several communication metrics.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2015, 77, pp.69--83. 〈10.1016/j.jpdc.2014.12.002〉
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-01159676
Contributeur : Equipe Roma <>
Soumis le : mercredi 3 juin 2015 - 15:20:28
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : lundi 24 avril 2017 - 23:29:26

Fichier

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

Identifiants

Collections

Citation

Mehmet Deveci, Kamer Kaya, Bora Uçar, Umit Catalyurek. Hypergraph partitioning for multiple communication cost metrics: Model and methods. Journal of Parallel and Distributed Computing, Elsevier, 2015, 77, pp.69--83. 〈10.1016/j.jpdc.2014.12.002〉. 〈hal-01159676〉

Partager

Métriques

Consultations de la notice

383

Téléchargements de fichiers

214