UMPA: A Multi-objective, multi-level partitioner for communication minimization

Abstract : We propose a directed hypergraph model and a refinement heuristic to distribute communicating tasks among the processing units in a distributed memory setting. The aim is to achieve load balance and minimize the maximum data sent by a processing unit. We also take two other communication metrics into account with a tie-breaking scheme. With this approach, task distributions causing an excessive use of network or a bottleneck processor which participates to almost all of the communication are avoided. We show on a large number of problem instances that our model improves the maximum data sent by a processor up to 34% for parallel environments with 4, 16, 64 and 256 processing units compared to the state of the art which only minimizes the total communication volume.
Type de document :
Chapitre d'ouvrage
David A. Bader and Henning Meyerhenke and Peters Sanders and Dorothea Wagner. Graph Partitioning and Graph Clustering 2012, 588, AMS, pp.53-66, 2013, Contemporary Mathematics, 〈10.1090/conm/588/11704〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00763563
Contributeur : Equipe Roma <>
Soumis le : mardi 11 décembre 2012 - 10:07:45
Dernière modification le : vendredi 20 avril 2018 - 15:44:27

Lien texte intégral

Identifiants

Collections

Citation

Umit Catalyurek, Mehmet Deveci, Kamer Kaya, Bora Uçar. UMPA: A Multi-objective, multi-level partitioner for communication minimization. David A. Bader and Henning Meyerhenke and Peters Sanders and Dorothea Wagner. Graph Partitioning and Graph Clustering 2012, 588, AMS, pp.53-66, 2013, Contemporary Mathematics, 〈10.1090/conm/588/11704〉. 〈hal-00763563〉

Partager

Métriques

Consultations de la notice

233