Dynamically adapting the space discretization during the runtime of a simulation can contribute to significantly reduce the time to solution. This thesis presents a novel approach for block-structured adaptive mesh refinement (AMR) that is suitable for extreme-scale parallelism. A central component of this approach are data structures that are designed such that the size of the meta data of each process remains bounded independent of the total number of processes. Moreover, all stages of the AMR algorithm only use distributed algorithms, meaning no data replication or central resources such as a master process are required. For the dynamic load balancing in particular, the thesis proposes to exploit the hierarchical nature of the block-structured domain partitioning by creating a lightweight, temporary copy of the distributed core data structure. This copy, however, does not contain any simulation data, but only acts as a proxy that provides topological information about the domain partitioning into blocks. Ultimately, this approach enables inexpensive, diffusion-based dynamic load balancing schemes.

All proposed algorithms operate on the blocks that result from the domain partitioning. This concept and its realization enable the storage of arbitrary data. In consequence, the resulting software framework can be used for different simulation methods, including mesh-based and meshfree methods. In this thesis, fluid simulations based on the lattice Boltzmann method (LBM) are presented. To that end, the thesis introduces a novel parallelization scheme for the LBM on nonuniform grids. Because of its applicability for massively parallel simulations, the LBM has increasingly become an alternative method for large-scale non-stationary flow simulations.

Using such LBM-based flow simulations, the excellent performance and scalability of the AMR implementation are demonstrated for two architecturally different petascale supercomputers. Benchmarks on an IBM Blue Gene/Q system with a mesh containing 3.7 trillion unknowns distributed to 458,752 processes confirm the applicability for future extreme-scale parallel machines. On the same system, the implementation of the LBM on nonuniform grids demonstrates an absolute performance of close to a trillion lattice cell updates per second when executed with almost two million threads. On an Intel Xeon-based supercomputer, LBM-based simulations on nonuniform grids that span the entire machine are shown to be capable of reaching a performance of less than one millisecond per time step. With 65,536 processor cores, one complete AMR cycle, including adaptive refinement and dynamic load balancing, is demonstrated to be executed in half a second for a mesh that consists of a total of 13.8 billion cells.

Das dynamische Anpassen der räumlichen Diskretisierung zur Laufzeit einer Simulation kann dazu beitragen, die Dauer der Simulation deutlich zu verkürzen. Die vorliegende Arbeit stellt einen neuen Ansatz zur blockstrukturierten adaptiven Gitterverfeinerung (AMR) vor, der für hochparallele Simulationen geeignet ist. Ein zentraler Bestandteil dieses Ansatzes sind Datenstrukturen, die so konzipiert sind, dass die Menge der Meta-Daten jedes Prozesses unabhängig von der Gesamtzahl der Prozesse begrenzt bleibt. Darüber hinaus verwenden alle Stufen des AMR-Algorithmus nur verteilte Algorithmen, so dass keine replizierten Daten oder zentrale Ressourcen wie ein Master-Prozess benötigt werden. Insbesondere für die dynamische Lastverteilung schlägt die vorliegende Arbeit vor, den hierarchischen Charakter der blockstrukturierten Raumaufteilung auszunutzen und eine leichtgewichtige, temporäre Kopie der verteilten Kerndatenstruktur zu erstellen. Diese Kopie enthält jedoch keine Simulationsdaten, sondern fungiert ausschließlich als Proxy, der topologische Informationen über die blockstrukturierte Raumaufteilung zur Verfügung stellt. Unter anderem ermöglicht dieser Ansatz die Verwendung kostengünstiger, diffusionsbasierter Verfahren zur dynamischen Lastverteilung.

Alle vorgestellten Algorithmen arbeiten auf Ebene der Blöcke, die aus der Raumaufteilung hervorgehen. Dieses Konzept und seine Umsetzung ermöglichen die Speicherung beliebig gearteter Daten. Das resultierende Software-Framework kann somit für verschiedene Simulationsmethoden genutzt werden, insbesondere sowohl für gitterbasierte als auch gitterfreie Methoden. In der vorliegenden Arbeit werden Strömungssimulationen auf Basis der Lattice-Boltzmann-Method (LBM) behandelt. Hierzu stellt die Arbeit ein neues Parallelisierungsverfahren für die LBM auf nicht-uniformen Gittern vor. Aufgrund ihrer Eignung für hochparallele Simulationen hat sich die LBM zunehmend zu einer alternativen Methode für groß angelegte instationäre Strömungssimulationen entwickelt.

Anhand derartiger Strömungssimulationen auf Basis der LBM wird die ausgezeichnete Leistung und Skalierbarkeit der AMR-Implementierung für zwei architektonisch unterschiedliche Petascale-Supercomputer demonstriert. Benchmarks auf einem Blue Gene/Q-System von IBM mit einem Gitter aus 3,7 Billionen Unbekannten, verteilt auf 458.752 Prozesse, bestätigen die Eignung für zukünftige, massiv-parallele Rechensysteme. Auf dem gleichen System ist es der Implementierung der LBM für nicht-uniforme Gitter mit knapp zwei Millionen Threads möglich, fast eine Billion Gitterzellen pro Sekunde zu aktualisieren. Auf einem Supercomputer auf Basis von Intel Xeon-Prozessoren sind Simulationen mit der LBM auf nicht-uniformen Gittern, die gleichzeitig auf allen Knoten des Supercomputers laufen, in der Lage, einen Durchsatz von über eintausend Zeitschritten pro Sekunde zu erreichen. Mit 65.536 Prozessorkernen wird gezeigt, dass es für ein Gitter mit insgesamt 13,8 Milliarden Zellen möglich ist, einen kompletten AMR-Zyklus, einschließlich adaptiver Verfeinerung und dynamischer Lastverteilung, in einer halben Sekunde durchzuführen.