Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Modellierung und Analyse komplexer Systeme


Load balancing is an important requirement for the
efficient execution of parallel numerical simulations. In particular
when the simulation domain changes over time, the mapping
of computational tasks to processors needs to be modified
accordingly. State-of-the-art libraries for this problem are based
on graph repartitioning. They have a number of drawbacks,
including the optimized metric and the difficulty of parallelizing
the popular repartitioning heuristic Kernighan-Lin (KL).
In this paper we further explore the very promising diffusionbased
graph partitioning algorithm DIBAP [1] by adapting
DIBAP to the related problem of load balancing and improving
its implementation. The presented experiments with graph
sequences that imitate adaptive numerical simulations are the
first using DIBAP for load balancing. They demonstrate the
applicability and high quality of DIBAP for load balancing by
repartitioning. Compared to the faster state-of-the-art repartitioners
PARMETIS and parallel JOSTLE, DIBAP’s solutions have
partitions with significantly fewer external edges and boundary
nodes and the resulting average migration volume in the important
maximum norm is also the best in most cases.

Keywords: Load balancing, graph partitioning, parallel
adaptive numerical simulations, disturbed diffusion.