Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations

Abstract. Load balancing is important for the efficient execution of numer-ical simulations on parallel computers. In particular when the simulation do-main changes over time, the mapping of computational tasks to processors needs to be modified accordingly. Most state-of-the-art libraries addressing this problem are based on graph repartitioning with a parallel variant of the Kernighan-Lin (KL) heuristic. The KL approach has a number of drawbacks, including the optimized metric and solutions with undesirable properties. Here we further explore the promising diffusion-based multilevel graph partitioning algorithm DibaP. We describe the evolution of the algorithm and report on its MPI implementation PDibaP for parallelism with distributed memory. PDibaP is targeted at small to medium scale parallelism with dozens of processors. The presented experiments use graph sequences that imitate adaptive numerical simulations. They demonstrate the applicability and qual-ity of PDibaP for load balancing by repartitioning on this scale. Compared to the faster ParMETIS, PDibaP’s solutions often have partitions with fewer external edges and a smaller communication volume in an underlying numeri-cal simulation