Graph Operators for Coupling-aware Graph Partitioning Algorithms

Abstract : Classic load balancing is a major issue that determines the performance of parallel applications, aiming to equally distribute the total computational load among processors in order to minimize the total execution time. Many applications that arise in scientific computing, circuit design or database modelling employ graph representation to describe and solve the problem of load balancing using graph partitioning techniques. The main objectives of graph partitioning is to divide the vertices of the graph in roughly equal parts, balancing computational load and to minimize the number of edges being cut between parts, reducing communication costs. In the literature, many graph partitioning algorithms have been proposed and are widely used within successful tools for load balancing or matrix reordering. However, applications that arise nowadays in real-life problems have more complex structure and may consist of numerous component simulations, coupled together, that represent different models. In this context, classic graph partitioning algorithms fail shortly to em- body the coupling procedure between component simulations and lead to partitions that are not well balanced throughout the overall execution of the application, namely throughout the coupling phase. In our research, we propose graph partitioning techniques that ad- dress the problem of load balancing for coupled simulation, which we refer to as co-partitioning. The main idea of our algorithms is to per- form a “coupling-aware” partitioning, instead of partitioning the component simulations independently, as it is the currently used approach. To facilitate the description of our algorithms we describe them as a sequence of graph operators that produce new graph structures or partitions based on repartitioning techniques or on fixed vertices biased partitioning. To conclude, we present results on a large graph collection deriving from artificially generated or real-life experiments in order to evaluate separately the graph operators used in our algorithms in respect to the partitioning quality, the edgecut minimization or the execution time.
Keywords : graph partitioning
Type de document :
Communication dans un congrès
CIMI Workshop on Innovative clustering methods for large graphs and block methods, Jul 2015, Toulouse, France. 〈〉
Liste complète des métadonnées
Contributeur : Maria Predari <>
Soumis le : mardi 22 septembre 2015 - 10:30:18
Dernière modification le : jeudi 11 janvier 2018 - 06:22:35
Document(s) archivé(s) le : mardi 29 décembre 2015 - 07:01:45


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01203006, version 1



Maria Predari, Aurélien Esnard. Graph Operators for Coupling-aware Graph Partitioning Algorithms. CIMI Workshop on Innovative clustering methods for large graphs and block methods, Jul 2015, Toulouse, France. 〈〉. 〈hal-01203006〉



Consultations de la notice


Téléchargements de fichiers