Hilbert Curve Based Flexible Dynamic Partitioning Scheme for Adaptive Scientific Computations
Student: Milinda Fernando (University of Utah)
Supervisor: Hari Sundar (University of Utah)
Abstract: Space Filling Curves (SFC) are commonly used by the HPC community for partitioning data[3, 4, 6] and for resource allocations[2, 5]. Amongst the various SFCs, Hilbert curves have been found to be in general superior to the more ubiquitous Morton or Z-Curve . However, their adoption in large-scale HPC codes, especially for partitioning applications, has not been as common as Morton curves due to the computational complexity associated with the Hilbert ordering. In this work, we present an alternative algorithm for computing the Hilbert ordering that can be implemented almost as efficiently as the Morton ordering. Additionally, being based on the concept of the nearest common ancestor—a fundamental property of all SFCs—the algorithm can be applied to all SFCs. We also present comparisons of Morton and Hilbert curve based partitions for adaptive meshes using two partitioning schemes demonstrating the superiority
of Hilbert ordering.
Two-page extended abstract: pdf