These html pages are based on the PhD thesis "Cluster-Based Parallelization of Simulations on Dynamically Adaptive Grids and Dynamic Resource Management" by Martin Schreiber.

There is also more information and a PDF version available.

There is also more information and a PDF version available.

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]^{2} 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 Ω_{1} := [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 Ω_{1}, 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.