Abstract: Dynamic Octree Load Balancing Using Space-Filling Curves

Dynamic Octree Load Balancing Using Space-Filling Curves

Paul C. Campbell, Karen D. Devine, Joseph E. Flaherty, Luis G. Gervasio, James D. Teresco,
Williams College Department of Computer Science Technical Report CS-03-01, 2003.

The Zoltan dynamic load balancing library provides applications with a reusable object oriented interface to several load balancing techniques, including coordinate bisection, octree/space filling curve methods, and multilevel graph partitioners. We describe enhancements to Zoltan's octree load balancing procedure and its distributed structures that improve performance of the space filling curve (SFC) traversals by exploiting similarities between the octree and SFC construction. The SFC implementation includes efficient Morton, Gray code, and Hilbert tree traversals. We present the results of a number of scalability and partition quality studies utilizing the new octree structures and orderings.

Citation (BIBTEX)  Paper (PS; 1.1MB)  Paper (PDF; 268KB)