Dynamic Load Balancing Using Space-Filling Curves

by
Justin Luitjens

Advised by
Martin Berzins

C-SAFE has begun to use Adaptive Mesh Refinement for solving many of its problems. AMR causes problems with load balancing because the amount and location of work to changes throughout the computation. Work needs to be repartitioned as the mesh changes. Ideally the partitions should be of equal size and the amount of communication between the partitions should be minimized. Unfortunately creating an optimal partition is a known to be NP-Hard.

Our research is attempting to solve the dynamic load-balancing problem by investigating Space-Filling Curves. A SFC is a mapping of N-dimensional space into a 1-dimensional space. The Hilbert-Peano SFC is a curve that preserves locality within the original space. Once a mapping is created it can be used to quickly create new partitions in linear time. The partitioning speed is the main advantage of SFCs. Traditional methods involve complicated calculations that can dominate the execution time in some situations. However, SFCs are not perfect. The partitions they create may not be as good as traditional methods. But studies have shown SFCs can produce good meshes for applications similar to C-SAFE.