Effiziente parallele Implementierung von hierarchischen N-Body-Algorithmen auf Multicore-Systemen mit GPU-Beschleunigung

Abstract

Mit Hilfe der Simulation von N-Body-Problemen lassen sich in verschiedenen naturwissenschaftlichen Disziplinen, wie der Astrophysik oder der Biochemie, Erkenntnisse gewinnen, die allein durch Theorie und Experiment nicht zugänglich wären. In der vorliegenden Diplomarbeit wird eine effiziente parallele Implementierung des Barnes-Hut-Verfahrens zur näherungsweisen Berechnung von N-Body-Problemen beschrieben. Als Einführung in die Thematik werden zunächst die physikalischen Grundlagen der N-Body-Probleme vorgestellt. Es folgt ein Überblick über verschiedene algorithmische Lösungsansätze für N-Body-Probleme, in dem auch der Barnes-Hut-Algorithmus vorgestellt wird. Um den Übergang von der sequentiellen Beschreibung zur parallelen Implementierung zu ermöglichen, werden anschließend unterschiedliche Klassifikationen von Parallelrechnerarchitekturen eingeführt und Aufbau sowie Programmierung von Multicore-Systemen und Graphikkarten beschrieben. Zur Implementierung des Barnes-Hut-Verfahrens wird dieses zunächst in mehrere Teilprobleme zerlegt, deren Lösungen sich getrennt voneinander als Module umsetzen lassen. Für jedes Modul werden anschließend unterschiedliche sequentielle und parallele CPU-Implementierungen und GPU-Implementierungen beschrieben und jeweils miteinander verglichen. Es zeigt sich dabei, dass sich insbesondere das zeitaufwändigste Teilproblem, die Kraftauswertung, sehr gut für eine Parallelisierung sowohl auf CPU als auch auf GPU eignet, wobei die Wahl der eingesetzten Datenstrukturen einen maßgeblichen Anteil an der effizienten Umsetzung hat. Zudem kann demonstriert werden, dass sich die Berechnungsgeschwindigkeit durch eine gemeinsame Berechnung der Kräfte auf dem Hauptprozessor und der Graphikkarte noch weiter steigern lässt. Nach der Vorstellung der Implementierungen der verschiedenen Module werden schließlich durch Kombination einzelner Implementierungen unterschiedliche Gesamtprogramme zusammengestellt und miteinander verglichen. Es stellt sich dabei heraus, dass das optimale Gesamtprogramm aus den jeweils besten Implementierungen der Teilproblemlösungen besteht. Anhand verschiedener Gesamtprogramme kann zuletzt auch nachgewiesen werden, dass sich Speicherlatenzen sehr gut verstecken lassen, wobei diese auch ohne Verstecken nur einen kleinen Bruchteil des Gesamtaufwands ausmachen und somit zu vernachlässigen sind.