Re-consider domain decomposition

Pattern addressed: Communication imbalance in MPI

By communication imbalance we refer to the situation where the amount of MPI calls or the message sizes change between processes. Of course the time taken by these communications depends on many factors, of which the number of calls, message sizes are important but also the type of MPI call (blocking or not) or the location of the processes involved in the communication (local within the node or remote). (more...)

Required condition: When the imbalance is caused by a domain decomposition that generates a different number of neighbours per sub-domain

Changing the domain decomposition may improve the communication imbalance of the application. Traditionally, domain decomposition algorithms only take into consideration the number of elements to be computed within the rank. A potentially interesting approach would be to modify the domain decomposition algorithm such that the cost function accounts for the number of elements within a domain, as well as its number of neighbours (appropriately weighted) and the communications the resulting domain must establish with them.

A possible cost function to optimize total balancing by the domain decomposition algorithm could be to compute the Cost Function (CF) as the result of adding the number of elements multiplied by a constant variable (alpha) plus the number of neighbors multiplied by another constant (beta). Computing the Cost Function per potential rank (i), the Cost Function would be:

\[CF_i = Ne_i * \alpha + Nn_i * \beta\]

   Where:
   - Ne: number of elements (in the rank)
   - alpha: corresponding weigh of the computational cost
   - Nn: number of neighbors (in the rank)
   - beta: corresponding weigh of the communication cost

Other variants of the cost function could have into account the size of the border exchanged with the neighbors, or try to modelize the cost function with more elaborated formulas (i.e., a more realistic model). In all these cases the objective, in the end, would be to obtain a similar Cost Function result per rank.

Examples of libraries helping to compute this algorithm include Metis, Scotch, etc.

The original code executed with this new domain decomposition approach should be more overall balanced (at a global level), and the cost of the computational phase will compensate for the cost in the communications. There is, in general, a trade-off between communication imbalance and computation imbalance that a domain decomposition approach must consider.

Recommended in program(s): Communication Imbalance (original) ·

Implemented in program(s): Communication Imbalance (rebalance) ·