Using Space-filling Curves for Computation Reordering

Space-filling curves have been widely used in mathematics and to transform multi-dimensional problems into one-dimensional forms. For scientific applications, ordering data or computation along spacefilling curves can be useful for exploiting locality when partitioning onto parallel systems or when restructuring to exploit memory hierarchy. In this paper, we present an efficient approach for enumerating points or mapping to points along space-filling curves. We introduce a new table specification, position specification, for mapping to points along space-filling curves. We discuss how this framework can be used for reordering computation. Experiments on three modern microprocessor based platforms show that our algorithm is up to a factor of 72 faster for enumerating points along a curve and up to a factor of 11 faster for mapping to points on the curve than a previous byte-oriented, non-recursive implementation.