Graph Operators for Coupling-aware Graph Partitioning Algorithms

International audienceClassic load balancing is a major issue that determines the performance of parallel applications, aiming to equally distribute the totalcomputational load among processors in order to minimize the totalexecution time.Many applications that arise in scientific computing, circuitdesign or database modelling employ graph representation todescribe and solve the problem of load balancing using graph partitioning techniques. The main objectives of graph partitioning isto divide the vertices of the graph in roughly equal parts, balancingcomputational load and to minimize the number of edges being cutbetween parts, reducing communication costs. In the literature, manygraph partitioning algorithms have been proposed and are widely usedwithin successful tools for load balancing or matrix reordering.However, applications that arise nowadays in real-life problemshave more complex structure and may consist of numerous componentsimulations, coupled together, that represent different models. Inthis context, classic graph partitioning algorithms fail shortly to em-body the coupling procedure between component simulations and leadto 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 werefer 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 asequence of graph operators that produce new graph structures or partitions based on repartitioning techniques or on fixed vertices biasedpartitioning.To conclude, we present results on a large graph collection derivingfrom artificially generated or real-life experiments in order to evaluateseparately the graph operators used in our algorithms in respect to thepartitioning quality, the edgecut minimization or the execution time