Graph partitioning techniques for load balancing of coupled simulations

The execution of scientific applications on parallel architectures often dictates an efficient decomposi- tion of the computational load in order to ensure high performance. In literature, such applications often use graph theory to describe and solve the problem of distributing computations to a number of available processors . More precisely each vertex of a graph rep- resents a computation (related to a mesh ele- ment), while an edge represents data dependen- cies between computations. Under this context, to equally distribute the computations of a paral- lel application, one may perform a graph partition- ing in k parts and assign each resulting part to a processor of the parallel machine. In other words, the objective of graph partitioning is to divide the given graph into k smaller parts of roughly equal size such that the number of edges between differ- ent parts is minimised. Unfortunately, graph partitioning is known to be NP-hard [2], so finding a partition of a given graph is usually based on heuristic techniques. Nowadays, the most common approaches to solve the graph partitioning problem are based on the multilevel approach to compress the problem and on the recursive-bisection heuristic to solve it on a smaller instance. Mature software for graph partitioning exist, such as Metis or Scotch. Recent challenges emerging in scientific com- puting involve the deep understanding of more complex physical phenomena. In an attempt to efficiently address the above issue, modern simu- lations have been developed that combine differ- ent component models, plugged in together under a coupling environment (coupled simulations). Examples of coupled simulations follow the multi-physics or multi-scale paradigm. For in- stance to simulate real-word conditions under the multi-physics model, one must consider the impact of a number of different physics that occur con- currently and correspond to different component simulations. In this context, modeling approaches should take into consideration the existence of dif- ferent computational domains but also their poten- tial overlapping invoked due to data dependencies between different components. Nowadays, to solve the load balancing problem of coupled simulations, one simply treats each component as a completely independent simulation and thus a classic graph partitioning algorithms is applied to each of the N components separately. As far as we know, the above approach to partition coupled simulations, which we call naive approach, is the most commonly used method and little work has been done to address the problem in a more sophisticated way. While naive approach is evidently easy to use and solves the partitioning problem for each com- ponent separately, it fails to address the real chal- lenges of coupled simulations, that is, balancing the load during the overlapping of computational do- mains and minimise the additional communication costs between parts that belong to different com- ponents.More precisely even though the partition of each component corresponds to a balanced dis- tribution of the load on its entire computational domain, if we focus just on the overlapping inter- face, we observe that the load is not necessarily balanced. In this work, we propose graph partitioning techniques that address the problem of load bal- ancing for coupled simulation, which we refer to as co-partitioning. The main idea here is to perform a “coupling-aware” partitioning, instead of partition- ing each component independently. Here, we present an experimental study on real- life coupled simulations. More precisely, we test our algorithms on applications coming from the field of aeronautic propulsion where the behavior of hot components is impacted by complex interac- tions between different physics. To predict such thermal environments, coupling of different heat transfer models, such as turbulent combustion, ra- diation and heat conduction, is necessary. Note that previous tests on synthetically generated cases aspire promising results for the graph partitioning of coupled applications when the proposed algo- rithms are used. New results on the real-life test cases are presented and evaluated in this work.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.