New graph partitioning techniques for load balancing of coupled simulation

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 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 minimizing communication costs. Unfortunately, graph partitioning is known to be NP-hard, so finding a partition of a given graph is usually based on heuristic techniques or approximating algorithms, integrated in widely used tools, such as Metis or Scotch. However, applications that emerge nowadays in real-life problems have more complex structure and may consist of numerous component simulations, coupled together, representing different models (coupled simulations). In this context, classic graph partitioning algorithms fail shortly to embody dependencies between different component models, thus reaching high performance can be a great challenge. In this work, we propose a new graph partitioning technique, called {\em co-partitioning}, that address the problem of load balancing for coupled simulations. The key idea here is to perform a ``coupling-aware'' partitioning, instead of partitioning these graphs independently, as it is usually done nowadays. More precisely, given a graph G that represents a component model, our first goal is to detect the subgraph G' whose vertices exchange information with other component graphs and then generate a balanced partition P' of G'. Following, we aim to extend the partition of the initial subgraph P' to a new partition P that accounts for the whole graph G. It is essential that the vertices of the initial partition P' should not be moved to other parts. However vertices may be added to parts in P' or to new parts that belong only to partition P. The above constraint helps producing a final partition that is balanced during the whole execution of a coupled simulation, even when component models exchange information. In order to formulate the partitioning of coupled simulations, we introduce here some graph operators that describe our algorithms as a sequence of partitioning steps. Finally, we present a preliminary experimental study which compares our methods against the classic approach used in legacy coupled simulations. In order to evaluate the partitioning quality of graph operators, we use synthetically generated graphs and graphs from popular data collections such as DIMACS'10. Our results are quite promising and our algorithms succeed to balance the computational load through out the whole execution of coupled simulations with only a small increase on the communication costs among different parts.
Type de document :
womENcourage 2015, Sep 2015, Uppsala University,Uppsala, Sweden
Liste complète des métadonnées
Contributeur : Maria Predari <>
Soumis le : lundi 18 janvier 2016 - 15:26:40
Dernière modification le : jeudi 11 janvier 2018 - 06:22:35
Document(s) archivé(s) le : vendredi 11 novembre 2016 - 10:02:09


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


  • HAL Id : hal-01258036, version 1



Maria Predari, Aurélien Esnard. New graph partitioning techniques for load balancing of coupled simulation. womENcourage 2015, Sep 2015, Uppsala University,Uppsala, Sweden. 〈hal-01258036〉



Consultations de la notice


Téléchargements de fichiers