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:
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.