3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ If I read your question right, you insist on a cartesian decomposition of the domain (though not necessarily uniformly in each coordinate direction). Why? $\endgroup$
    – Wolfgang Bangerth
    Dec 8, 2015 at 13:54
  • $\begingroup$ @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. $\endgroup$
    – Gilles
    Dec 8, 2015 at 15:37
  • $\begingroup$ That would actually be a rather simple approach indeed because you can exactly subdivide 1d partitions into equally sized chunks. $\endgroup$
    – Wolfgang Bangerth
    Dec 8, 2015 at 22:57

1 Answer 1

Reset to default
2
$\begingroup$

This is typically done with graph partitioning algorithms, and packages such as METIS and ParMETIS (same link) are often used to do so.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the suggestion. Actually, the licence model of ParMETIS makes it not an option for me. However, starting from there, I found useful method descriptions on the Zoltan web site. And I have the feeling that I can re-implement a simplified method similar to the RCB one which is described there. So I'm kind of optimistic I'll be able to solve this. I'll post my solution if/when it's ready. $\endgroup$
    – Gilles
    Dec 8, 2015 at 15:43
  • $\begingroup$ Dear @Gilles . If the license model of ParMETIS does not suite you, maybe you could look into Scotch and PTScotch. They use a far more premissive license model and, although they use different algorithms, I have found them to be as efficient for the applications I looked into. $\endgroup$
    – BlaB
    May 7, 2018 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.