×

SFCGen

swMATH ID: 852
Software Authors: Jin, Guohua; Mellor-Crummey, John
Description: SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion. Because they are continuous and self-similar, space-filling curves have been widely used in mathematics to transform multi-dimensional problems into one-dimensional forms. For scientific applications, reordering computation by certain space-filling curves can significantly improve data reuse because of the locality properties of these curves. However, when space-filling curves are used in programs for reordering data, traversal or indexing of the curves must be efficient.par To address this problem, we present the table-driven framework SFCGen to efficiently generate multi-dimensional space-filling curves on the fly. The framework is general and easy enough to be used in any application that can be partitioned recursively in multiple dimensions. We describe a movement specification table, a universal turtle algorithm to enumerate points along a space-filling curve, a table-based indexing algorithm to transform coordinates of a point into its position along the curve and an algorithm to pregenerate the table automatically.par As examples, we show how high-dimensional Hilbert, Morton, and Peano curves and a two-dimensional Sierpiński curve can be generated with our algorithms. We present performance results for Hilbert, Morton, and Peano curves and compare the efficiency of our curve generation algorithm with the most recent work on generating Hilbert curves. Our experimental results on three modern microprocessor-based platforms show that SFCGen performs up to 63
Homepage: http://dl.acm.org/citation.cfm?doid=1055531.1055537
Keywords: multi-dimensional space-filling curves; universal turtle algorithm; table-based indexing algorithm; Peano curves; performance; Hilbert curves; Morton curves; numerical examples; Sierpi\'nski curve
Related Software: Algorithm 781; Intel TBB; AMRCLAW; Peano; GEOCLAW; METIS; Globus Toolkit; Chord
Cited in: 5 Publications

Citations by Year