SFCGen
swMATH ID:  852 
Software Authors:  Jin, Guohua; MellorCrummey, John 
Description:  SFCGen: A framework for efficient generation of multidimensional spacefilling curves by recursion. Because they are continuous and selfsimilar, spacefilling curves have been widely used in mathematics to transform multidimensional problems into onedimensional forms. For scientific applications, reordering computation by certain spacefilling curves can significantly improve data reuse because of the locality properties of these curves. However, when spacefilling 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 tabledriven framework SFCGen to efficiently generate multidimensional spacefilling 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 spacefilling curve, a tablebased 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 highdimensional Hilbert, Morton, and Peano curves and a twodimensional 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 microprocessorbased platforms show that SFCGen performs up to 63 
Homepage:  http://dl.acm.org/citation.cfm?doid=1055531.1055537 
Keywords:  multidimensional spacefilling curves; universal turtle algorithm; tablebased 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 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

SFCGen: A framework for efficient generation of multidimensional spacefilling curves by recursion. Zbl 1073.65017 Jin, Guohua; MellorCrummey, John 
2005

all
top 5
Cited by 13 Authors
Cited in 4 Serials
1  Information Processing Letters 
1  ACM Transactions on Mathematical Software 
1  Parallel Computing 
1  SIAM Journal on Scientific Computing 
all
top 5