Balancing number of points in a 2D grid

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 Ntot be this number, then we have to keep Nx * Ny = Ntot for any valid (Nx, Ny) solution.
• 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 Gy.
• 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.

• If I read your question right, you insist on a cartesian decomposition of the domain (though not necessarily uniformly in each coordinate direction). Why? – Wolfgang Bangerth Dec 8 '15 at 13:54
• @WolfgangBangerth Well, actually it was because I thought the MPI-IO part of the code would become a nightmare otherwise. However, some further thinking following the quick reading of some documentation from Zoltan (slide 21) let me think that slicing in X first, and then re-slicing each one independently in Y might be the way to go. This looks both simple enough to implement, and keeping a sufficiently regular arrangement for the MPI-IO part to stay easily manageable. – Gilles Dec 8 '15 at 15:37
• That would actually be a rather simple approach indeed because you can exactly subdivide 1d partitions into equally sized chunks. – Wolfgang Bangerth Dec 8 '15 at 22:57