Erweitern des Vergleichs verschiedener N-Körper-Algorithmen auf diversen Hardwareplattformen unter Verwendung von SYCL

Abstract

N-Körper Beschleunigungsberechnungen werden in diversen Bereichen der Wissenschaft durchgeführt, zum Beispiel bei der Simulation von Sonnensystemen in der Astronomie oder auch beim Simulieren von Teilchensystemen im Molekularbereich. Da diese Simulationen eine große Anzahl an Körpern enthalten können, gibt es bereits Algorithmen, die die notwendige Anzahl an Berechnungen während der Simulation mit möglichst geringer Auswirkung auf die Genauigkeit verringern. Ein Beispiel hierfür ist der baumbasierte Barnes-Hut Algorithmus. Im Vorfeld dieser Arbeit wurde bereits gezeigt, dass der Barnes-Hut Algorithmus auf GPUs mithilfe von SYCL erfolgreich implementiert werden kann. Da Barnes-Hut jedoch per Definition mit Bäumen arbeitet, ist er nicht optimal für die Ausführung auf GPUs geeignet. In dieser Arbeit soll der normale Barnes-Hut Algorithmus, bei dem der Baum im Top-Down Verfahren aufgebaut wird, so abgeändert werden, dass der Baum von den Blattknoten aufwärts erstellt wird, und dabei möglichst viele Operationen parallel ausgeführt werden können. Die Erstellung der Baumstruktur kann durch die Verwendung des Bottom-Up Ansatzes beschleunigt werden. Außerdem können GPUs nun mehr Knoten des Baumes in der gleichen Zeit abarbeiten als beim Top-Down Verfahren. Durch die Umstruktierung des Baumes ist die Vereinfachung der Beschleunigungsberechnung mit dem Barnes-Hut Algorithmus jedoch nicht mehr so effektiv. Die Gesamtlaufzeit ist nun deutlich höher, da bei gleichem Theta mehr Körper in der Beschleunigungsberechnung einzeln bearbeitet werden. Die Laufzeit kann verbessert werden, indem für größere Datensätze die Anzahl an Kindknoten pro innerem Knoten im Baum erhöht wird, jedoch skaliert der Top-Down Barnes-Hut Algorithmus trotz dieser Optimierung besser. Der Bottom-Up Ansatz hat jedoch Potential für weitere Optimierungen, die ihn in Zukunft auf GPUs konkurrenzfähig zum Top-Down Verfahren machen könnten.