Die algorithmische Betrachtung und parallele Simulation des N-Körper Problems ist eine treibende Kraft und herausfordernde Aufgabe für das High Performance Computing. Ein schneller Summationsalgorithmus zur Reduktion der Komplexität ist der Barnes-Hut Tree Code mit O(N log(N)), anstatt der üblichen O(N²) Wechselwirkungen. Im Jülich Supercomputing Centre wird auf der Grundlage des Hashed-Oct-Tree-Schemas der multidisziplinäre Code PEPC - der Pretty Efficient Parallel Coulomb Solver - entwickelt.

Für eine sehr große Prozessoranzahl, wie zum Beispiel der des Superrechners JUGENE, einer IBM Blue Gene/P Architektur, wächst der parallele Mehraufwand zur Baumkonstruktion enorm und wirkt sich nachteilig auf das Skalierungsverhalten aus. In der vorliegenden Arbeit werden aus diesem Grund neue Verfahren zur Optimierung wesentlicher Engpässe hergeleitet und umgesetzt. Eine grundsätzliche und beweisbare Minimierung der Organisationsstruktur, die der Parallelität des Algorithmus geschuldet ist, wird vorgestellt. Als entscheidender Vorteil des neuen Ansatzes erweist sich eine präzise a-priori Abschätzung der parallelen Datenstruktur und damit verbunden eine Reduktion des Speicherbedarfs sowie des Kommunikationsaufwandes. Weiterhin wurde zur Verbesserung der Datenlokalität die Hilbert-Kurve implementiert und ihre Auswirkung auf die irreguläre Kommunikationsstruktur untersucht.

Durch die Optimierung des Speicherverbrauchs erlauben die Ergebnisse der neuen Methode eine immense Steigerung der Teilchenanzahl sowie den Einsatz des massiv parallelen Barnes-Hut Tree Code PEPC als noch flexibleres Tool hinsichtlich der Simulation in einem multidisziplinären Kontext.

Vortrag (552KB - englisch)

Masterarbeit (5.8MB - englisch)