Chapter 5
Parallelization

The parallelization of inherently serial code as it is the case for the Sierpiński SFC grid traversal with its stack- and stream-based data management is a challenging task. This chapter is on the extension of the so far serial grid traversal to a cluster-based parallelization approach.

• Section 5.1: SFC-based parallelization methods for DAMR
  We start with an overview of common parallelization methods with dynamic adaptive mesh refinement to show differences, but also common aspects of our approach.
• Section 5.2: Inter-partition communication and dynamic meta information
  To offer efficient data exchange between our partitions, we developed communication meta information which is represented by a run-length encoding. We present the concept of this encoding, its applicability to edge- and vertex-based communication and how to use it for the dynamically changing grids.
• Section 5.3: Parallelization with clusters
  Despite the parallelization of a serial code, the abstraction layers introduced for the serial simulation should be maintained for usability reasons. Also the parallelization should be hidden from the application developer with an appropriate software design. We account for both issues with a cluster-based software solution.
• Section 5.4: Base domain triangulation and initialization of meta information
  For the simulation domain itself, a typical requirement is a flexible assemblation of simulation domains of different kind of shapes.
• Section 5.5: Dynamic cluster generation
  With the dynamically changing grids, we have to cope with load imbalances. This is accomplished by dynamically generating clusters. With our clusters based on tree-splits, we use tree-splits and -joins and show implicit handling of the communication meta information for these splits and joins.
• Section 5.6: Shared-memory parallelization
  The shared-memory parallelization describes the cluster-to-thread scheduling, the dynamic cluster generation strategies and the used threading libraries.
• Section 5.7: Results: Shared-memory parallelization
  Results on the shared-memory parallelization with different cluster generation strategies on different platforms are presented in this section.
• Section 5.8: Cluster-based optimization
  With clustering at hand, we present different optimization possibilities.
• Section 5.9: Results: Long-term simulations and optimizations on shared-memory
  Scalability tests of parallelization concepts are typically executed only for a few time steps of the simulation. Here, we present the impact of long-term simulation runs on the scalability, resulting in a different optimal choice of cluster generation and scheduling compared to the short-term simulations.
• Section 5.10: Distributed-memory parallelization
  The extension to distributed memory parallelization is presented in this section. Whereas the RLE meta information solves the efficiency issues of our distributed-memory communication scheme, the cluster-based software design allows straightforward cluster migration.
• Section 5.12: Results: Distributed-memory parallelization
  With the distributed-memory parallelization introduced in the previous section, here we present small- and large-scale scalability studies.
• Section 5.13: Summary and Outlook
  The last section concludes and highlights the new contributions developed in this thesis.