Assigning Cartesian grid area to processes
Candice Astier, Devan Sohier, Antoine Capra · 2025
A topology-aware implementation reduces communication times for parallel programs. MPI supports the distribution of processes on a virtual Cartesian grid via the MPI_Cart_Create function. In such situation, communications between process mostly occur between those in charge of adjacent cells. Thus, placing such processes close one to another reduces the risk of congestion. Using operations research techniques and tools, we compute process placements that realize this objective. We present two solutions: a mathematical modeling of this problem, that we then linearize to compute an optimal solution with a MILP solver; or a heuristic based on a dynamic programming algorithm that provides either an optimal guillotine solution or a good quality solution depending on the networks. This work is based on fat-tree topologies to validate the methods and hypotheses of this work.