3.3 Space-filling curves

We give a very brief introduction to space-filling curves (SFCs) and refer the interested reader to [Sag94] for more information on SFCs. These SFCs were motivated by Cantor’s discovery of an equivilant cardinality of higher-dimensional manifolds and a one-dimensional interval. However, the higher-dimensional curve generated by the one-dimensional interval was not continuous. Peano then searched for such a continuous curve parametrized with the one-dimensional form and touching every point in the higher-dimensional manifold and discovered the SFCs, yielding these properties. For a long time, SFCs were only considered from a theoretical point of view to show that there is a mapping between [0;1]² and [0;1]. Nowadays, their discrete form based on iterations play an increasing role in multiple areas such as databases [FR89], computer graphics [GE04], adaptive mesh refinement [BZ00] and performance optimized computations of linear algebra operations [HT12]. Hence, space-filling curves (SFC) provide beneficial properties which can provide an efficient solution to the memory hierarchy and load balancing challenges. Using scaling and translation of our simulation domain, we assume our simulation space being enclosed by a unit-hypercube Ω_d := [0;1]^d. The SFCs considered in this work then provide a surjective mapping from a one-dimensional interval Ω₁ := [0;1] to each point in the simulation domain Ω_d.

Frequently used SFCs for higher dimensions are Hilbert and Peano curves for a 2^d- and 3^d-section of each cell on Cartesian grids. For two-dimensional grids, the Sierpiński curve on triangular grids offers bi-section of triangular cells.

Further considering cache-oblivious communication structures, stack- and stream-based communications structures [GMPZ06] yield cache-oblivious communications. With our simulation based on two-dimensional triangular grids, this leads us to the bi-secting Sierpiński curve with a stack-based communication which was initially presented for a serial traversal in [BSVB08] and is further described in Section 4.

We can use SFCs to optimize for spatial and temporal data access locality and to enumerate the cell primitives on Ω₁, yielding beneficial properties:

(a)

Spatial local data access:
Spatial locality refers to data access which is close to the previously accessed data. Storing the simulation data consecutively ordered along the one-dimensional mapping of the multi-dimensional SFC coordinates hence improves the spatial local access.

(b)

Temporal locality:
This refers to the same data being accessed again after a short time interval. If accessing adjacent data such as conserved quantities computed on edges, the probability of this data being already stored in cache can be increased due to the recursively structured domain.

(c)

Load balancing:
SFCs furthermore provide an efficient way of partitioning simulation domains, see Section 3.4.1. This is due to their capability of enumerating all available grid cells, hence reducing the complexity to a one-dimensional partitioning problem.