Hypergraph-based Dynamic Load Balancing for Adaptive Scientific Computations

TLDR

Adaptive scientific computations require dynamic load balancing to maintain balance, and hypergraph partitioning is a proven method for minimizing communication volume in static cases. The paper introduces a new hypergraph model for dynamic load balancing that minimizes communication plus migration cost to reduce execution time. The model is solved via hypergraph partitioning with faced vertices, implemented as a parallel multilevel repartitioning algorithm in the Zoltan toolkit—the first such dynamic load‑balancing code. Experiments on a Linux cluster up to 64 processors show the algorithm outperforms ParMETIS in quality and would reduce execution time in most test cases.

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.