Hypergraph-based Dynamic Load Balancing for Adaptive Scientific Computations
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 1-11
Abstract
Adaptive scientific computations require that periodic repartitioning (load balancing) occur dynamically to maintain load balance. Hypergraph partitioning is a successful model for minimizing communication volume in scientific computations, and partitioning software for the static case is widely available. In this paper, we present a new hypergraph model for the dynamic case, where we minimize the sum of communication in the application plus the migration cost to move data, thereby reducing total execution time. The new model can be solved using hypergraph partitioning with faced vertices. We describe an implementation of a parallel multilevel repartitioning algorithm within the Zoltan load-balancing toolkit, which to our knowledge is the first code for dynamic load balancing based on hypergraph partitioning. Finally, we present experimental results that demonstrate the effectiveness of our approach on a Linux cluster with up to 64 processors. Our new algorithm compares favorably to the widely used ParMETIS partitioning software in terms of quality, and would have reduced total execution time in most of our test cases.Keywords
This publication has 23 references indexed in Scilit:
- Adaptive decomposition and remapping algorithms for object-space-parallel direct volume rendering of unstructured gridsJournal of Parallel and Distributed Computing, 2007
- Zoltan data management services for parallel dynamic applicationsComputing in Science & Engineering, 2002
- Wavefront diffusion and LMSR: algorithms for dynamic repartitioning of adaptive meshesIEEE Transactions on Parallel and Distributed Systems, 2001
- Graph partitioning models for parallel computingParallel Computing, 2000
- Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplicationIEEE Transactions on Parallel and Distributed Systems, 1999
- PLUM : Parallel Load Balancing for Adaptive Unstructured MeshesJournal of Parallel and Distributed Computing, 1998
- An optimal migration algorithm for dynamic load balancingConcurrency: Practice and Experience, 1998
- Multilevel Diffusion Schemes for Repartitioning of Adaptive MeshesJournal of Parallel and Distributed Computing, 1997
- Load balancing for the parallel adaptive solution of partial differential equationsApplied Numerical Mathematics, 1994
- Performance of dynamic load balancing algorithms for unstructured mesh calculationsConcurrency: Practice and Experience, 1991