In a parallel MPI code, I have load balancing issues. My 2D computational domain is distributed on a 2D MPI Cartesian topology, which leads to equal sized 2D sub-domains per MPI process. However, the amount of work to do per domain is determined by the number of "compute points" belonging to each domain. And the density of these compute points is very uneven, leading to some processes having much much more of them than others. Therefore, the overall parallel efficiency of my code might become quite poor.
To solve this issue, I want to resize my 2D domain decomposition, to re-balance the number of compute points across my MPI processes. I'm therefore looking for an algorithm permitting me to achieve this optimisation process. The constrains are:
- The X and Y dimensions
(Gx, Gy)of the global grid to distribute are fixes (integer representing the number of grid points to distribute across MPI processes in each dimensions)
- The total number of MPI processes is fixed. Let
Ntotbe this number, then we have to keep
Nx * Ny = Ntotfor any valid
- The number of X and Y grid points for each MPI process can be different. The only limit is that the sum of the individual X grid points for all MPI processes should be equal to
Gx. Likewise for
- The density of compute point on the grid is known a priori. Each grid point might have anywhere between zero and a ten such compute points.
Any idea of any method / algorithm to solve this problem? I'm fully aware that there might be no perfect solution, but any mapping of the grid permitting to improve the load balancing would already be good to take.