<figure><img src="image_1.png" /></figure>

HAL
open science

# New graph partitioning techniques for load balancing of coupled simulation

Maria Predari, Aurélien Esnard

<figure><img src="image_2.png" /></figure>

## To cite this version:

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

HAL Id: hal-01258036

https://inria.hal.science/hal-01258036

Submitted on 18 Jan 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# New graph partitioning techniques for load balancing of coupled simulation

Maria Predari<sub>1</sub>, Esnard Aurelien<sub>2</sub>

1. Inria, University of Bordeaux, France (maria.predari@inria.fr), 2. Inria, University of Bordeaux, France (aurelien.esnard@inria.fr).

## Introduction

### Load balancing in scientific computing

In the field of scientific computing, the load balancing is a crucial issue which determines the performance of parallel applications. A very common approach to solve the load-balancing problem is based on graph model. To equilibrate the load between N processors, one performs a (N-way) graph partitioning in N parts, each part being assigned to a given processor.

**Graph Partitioning Steps**

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

**Graph Model:**

* vertex represents computation task

* edge represents communication cost

**Objectives:**

* balance computational load (nb vertices per part)

* minimize communication costs (nb edgecut)

**Unfortunately: NP-hard problem!**

**Multi-physics, Multi-scale, Coupled Simulations**

Applications that emerge nowadays in real-life problems often have more complex structure and may consist of numerous component simulations, coupled together representing different models.

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

**Problem during coupling phase:**

* computations highly imbalanced

* bad data distribution among components

<figure><img src="image_14.png" /></figure>

**Solution:**

Find a coupling-aware partitioning that takes into account the coupling phase explicitly as a trade off to the partitioning during the regular phase.

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

## Results

### Experimental results of KGGGP algorithm on Dimacs graph dataset

**Experiment1:** no initial fixed vertices

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

* 3 experimental cases

* 2 implementations KGGGP_G, KGGGP_L (global and local)

* comparison with SCOTCH, kMETIS, PaToH, Zoltan

* evaluate partitioning quality, time performance

<table><thead><tr><th>group</th><th>graph</th><th># vtx</th><th># edges</th><th>avg d°</th><th>min d°</th><th>max d°</th></tr></thead><tbody><tr><td>walshaw</td><td>fe ROTOR</td><td>99 617</td><td>662 431</td><td>13.30</td><td>5</td><td>125</td></tr><tr><td>walshaw</td><td>144</td><td>144 649</td><td>1 074 393</td><td>14.86</td><td>4</td><td>26</td></tr><tr><td>walshaw</td><td>wave</td><td>156 317</td><td>1 059 331</td><td>13.55</td><td>3</td><td>44</td></tr><tr><td>walshaw</td><td>m14b</td><td>214 765</td><td>1 679 018</td><td>15.64</td><td>4</td><td>40</td></tr><tr><td>matrix</td><td>audikw1</td><td>943 695</td><td>38 354 076</td><td>81.28</td><td>20</td><td>344</td></tr><tr><td>matrix</td><td>ecology1</td><td>1 000 000</td><td>1 998 000</td><td>4.00</td><td>2</td><td>4</td></tr><tr><td>matrix</td><td>thermal2</td><td>1 227 087</td><td>3 676 134</td><td>5.99</td><td>2</td><td>10</td></tr><tr><td>matrix</td><td>af SHELL10</td><td>1 508 065</td><td>25 582 130</td><td>33.93</td><td>14</td><td>34</td></tr><tr><td>numerical</td><td>NACA0015</td><td>1 039 183</td><td>3 114 818</td><td>5.99</td><td>3</td><td>10</td></tr><tr><td>numerical</td><td>333SP</td><td>3 712 815</td><td>11 108 633</td><td>5.98</td><td>2</td><td>28</td></tr><tr><td>numerical</td><td>NLR</td><td>4 163 763</td><td>12 487 976</td><td>6.00</td><td>3</td><td>20</td></tr><tr><td>numerical</td><td>adaptive</td><td>6 815 744</td><td>13 624 320</td><td>4</td><td>2</td><td>4</td></tr></tbody></table>

<figure><img src="image_21.png" /></figure>

**Experiment2:** initial fixed vertices (bubble scheme)

**Experiment3:** initial fixed vertices (repartition scheme)

<figure><img src="image_22.png" /></figure>

**Experimental results of copartitioning algorithms AWARE and PROJREPART**

* synthetically generated mesh structures

* use of KGGGP implementation as partitioning algorithm

* dependencies on the surface of mesh structures

* comparison with NAIVE method

* imbalance tolerance up to 5% of total weight

<table><thead><tr><th>Exp.</th><th>Graph A</th><th>Graph B</th></tr></thead><tbody><tr><td>exp1</td><td>cube-hexa-25x25x25</td><td>cube-hexa-100x100x100</td></tr><tr><td>exp2</td><td>cube-hexa-25x25x25</td><td>cube-hexa-70x70x70</td></tr><tr><td>exp3</td><td>cube-tetra-40630</td><td>cube-hexa-100x100x100</td></tr><tr><td>exp4</td><td>cube-tetra-40630</td><td>cube-tetra-486719</td></tr></tbody></table>

**Results on coupling imbalance during coupling interface**

**Results on global edgecut**

**Results on total number of messages exchanged during coupling interface**

<figure><img src="image_23.png" /></figure>

**Types of messages for components with different discretization alignment**

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

Major messages are preferred since with one communication cost we exchange more information!

## Methods

**NAIVE:** each component model is partitioned independently

Example of coupled simulation with 2 components A, B (cubic structures) and coupling intersection on the surface.

Each structure has different discretization (hexaedric and tetraedric).

<figure><img src="image_26.png" /></figure>

**Step1: Partition**

**Coupling interfaces**

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

* NAIVE is used as the state-of-the-art for copartitioning

* components are not aware of their coupling interfaces

<figure><img src="image_31.png" /></figure>

**Imbalance during coupling phase!**

Graph A

Graph B

**Graph Operators**

**Restriction**

**Projection**

**Partition**

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

**Repartition**

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /></figure>

* **Restriction:** returns a subgraph of a graph induced to a set of edges.

* **Partition:** returns a balanced partition of a graph or subgraph with respect to an imbalance factor.

* **Projection:** returns a N-way partition on a graph similar to a N-way partition on another graph.

* **Repartition:** returns a M-way balanced partition using a former N-way partition on the same graph.

* **Extension:** returns a balanced partition using an existing partition on a subgraph of the graph.

**Attention: some operators need to handle fixed vertices**

**Repartition example from 5 to 7 parts**

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>

<figure><img src="image_39.png" /></figure>

Additional "square" vertices should remain in place after the partitioning

**Copartitioning Algorithms**

To describe our co-partitioning algorithms, we use sequences of graph operators that may be implemented with any known partitioning algorithm, such as recursive bisection, spectral based partitioning, etc

**AWARE:** each component model is aware of its coupling interface

**Step1: Restriction**

**Step2: Partition**

**Step3: Extension**

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>

**PROJREPART:** components are also aware of other component's coupling interface

**Step1: Restriction**

**Step2: Partition**

**Step4: Extension**

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

Graph A

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>

**Step5: Extension**

<figure><img src="image_54.png" /></figure>

**Which algorithm we use for the actual partitioning and why?**

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. The partition is then projected back to the original graph structure applying local refinement algorithms.

**Why RB paradigm is not good for the copartitioning**

Extension, Projection and Repartition operators need to handle vertices that must remain in place during the partitioning procedure (fixed vertices)

**Motivating example**

Partition of square graph with fixed vertices using RB based algorithm (in 4 parts)

<figure><img src="image_55.png" /></figure>

**Vertices on the corners of the square graph are initially fixed to parts**

RB based algorithm can not successfully respect both the inherent numbering constraint and the additional constraint of fixed vertices. This problem mainly appears when the part numbering of fixed vertices opposes to those of RB.

<figure><img src="image_56.png" /></figure>

after refinements

<figure><img src="image_57.png" /></figure>

**Recursive Bisection fails to partition the graph!!**

* Large number of edgecut

* Disconnected components

before refinements

<figure><img src="image_58.png" /></figure>

after refinements

<figure><img src="image_59.png" /></figure>

KGGGP successfully partition the graph with initial fixed vertices in 4 parts as opposed to RB!

## Conclusions

**Algorithmic conclusions**

* a new algorithm for graph partitioning KGGGP that handles initial fixed vertices

* two new copartitioning algorithms, AWARE and PROJREPART for coupled simulations

**Copartitioning conclusions**

* good load balancing during the coupling phase for both methods at a slight increase of edgecut

* in simple experiments the number of messages exchanged between components is minimized

**Future Work**

* test copartitioning algorithms with real life coupled simulations

* implement parallel version of KGGGP algorithm

**Example**

In the field of aeronautic propulsion the behavior of hot components is impacted by complex interactions between different physics such as turbulent combustion, radiation and heat conduction. To predict such thermal environments, coupling of these different heat transfer models is necessary.

* 2 codes: fluid flow solver, heat transfer solver for solids

* fluid solver: hexaedric discretization

* heat solver: hexaedric and prism discretization

* coupling in the surfaces

<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /></figure>

graph structure of fluid and heat solver with their coupling interfaces (red regions)

**Copartitioning overview**

<figure><img src="image_62.png" /></figure>