Title :
Dynamic Load Balancing for Parallel Numerical Simulations Based on Repartitioning with Disturbed Diffusion
Author :
Meyerhenke, Henning
Author_Institution :
Dept. of Comput. Sci., Univ. of Paderborn, Paderborn, Germany
Abstract :
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 diffusion-based graph partitioning algorithm DIBAP 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 :
graph theory; numerical analysis; parallel processing; resource allocation; DIBAP; PARMETIS; adaptive graph sequences; average migration volume; boundary nodes; diffusion-based graph partitioning algorithm; disturbed diffusion; disturbed diffusive repartitioning algorithm; dynamic load balancing; graph repartitioning; heuristic Kernighan-Lin repartitioning; libraries; parallel JOSTLE; parallel numerical simulations; Application software; Computational modeling; Computer science; Concurrent computing; Finite element methods; Libraries; Load management; Numerical simulation; Partial differential equations; Partitioning algorithms; Load balancing; disturbed diffusion; graph partitioning; parallel adaptive numerical simulations;
Conference_Titel :
Parallel and Distributed Systems (ICPADS), 2009 15th International Conference on
Conference_Location :
Shenzhen
Print_ISBN :
978-1-4244-5788-5
DOI :
10.1109/ICPADS.2009.114