Comparison of different n-body algorithms on various hardware platforms using SYCL

Abstract

The n-body problem has various applications in different fields of science such as astrophysics, where it describes the problem of calculating the movements of n different bodies which all interact with each other over time. There exist different algorithms that solve the n-body problem, for example, the naive approach and the Barnes-Hut algorithm. Since applications of the n-body problem can deal with large systems of bodies it is crucial to understand the runtime behavior of theses algorithms. In this thesis the runtime behavior of the naive algorithm and the Barnes-Hut algorithm will be compared on different CPUs as well as on GPUs from different vendors. Both algorithms will be implemented using SYCL which is an abstraction layer that enables parallel programming for various types of devices. With SYCL there is no need to use different languages for parallel programming on CPUs and GPUs and the whole code can be written using standard C++. The results show that one can achieve better performance with both algorithms on GPUs than on CPUs. A projection for the runtime of a simulation of approximately one earth year with a system of over 1.2 million bodies and a Δ𝑡 of one hour shows that an NVIDIA A100 GPU could finish this simulation in under one day with the naive approach. A dual socket AMD EPYC 7543 would take almost twelve days for the same simulation. This shows that the naive algorithm maps extremely well to GPUs. CPUs can keep up better with the Barnes-Hut algorithm. Here the projection of the runtime showed that the NVIDIA A100 would finish the simulation of an earth year in just below an hour whereas the dual socket AMD EPYC 7543 could finish the simulation in 2.59 hours.

Das n-Körper-Problem hat viele Anwendungen in unterschiedlichen Forschungsgebieten, wie zum Beispiel Astrophysik, in denen es das Problem der Berechnung von Bewegungen unterschiedlicher Körper beschreibt, die alle miteinander interagieren. Es existieren verschiedene Algorithmen, die das n-Körperproblem lösen, zum Beispiel der naive Ansatz oder der Barnes-Hut Algorithmus. Da sich Anwendungen des n-Körper-Problems mit großen Systemen von Körpern beschäftigen können, ist es wichtig das Laufzeitverhalten dieser Algorithmen zu verstehen. In dieser Arbeit wird das Laufzeitverhalten des naiven Algorithmus und des Barnes-Hut Algorithmus auf unterschiedlichen CPUs und GPUs von verschiedenen Herstellern verglichen. Beide Algorithmen werden unter der Verwendung von SYCL implementiert, was eine Abstraktionsschicht ist die es ermöglicht verschiedenste Hardware parallel zu programmieren. Mit SYCL besteht nicht die Notwendigkeit verschiedene Sprachen für das parallele Programmieren auf CPUs und GPUs zu verwenden und der gesamte Programmcode kann in Standard C++ geschrieben werden. Die Ergebnisse zeigen, dass man bei beiden Algorithmen bessere Performanz auf GPUs erreichen kann als auf CPUs. Eine Hochrechnung der Laufzeit für eine Simulation von ungefähr einem Erd-Jahr mit einem System von 1,2 Millionen Körpern und einem Delta t von einer Stunde zeigt, dass eine NVIDIA A100 GPU mit dem naiven Ansatz die Simulation in unter einem Tag beenden kann. Ein Dual-Socket AMD EPYC 7543 würde fast zwölf Tage für diese Simulation benötigen. Das zeigt, dass sich der naive Algorithmus enorm gut auf GPUs anwenden lässt. CPUs können beim Barnes-Hut Algorithmus besser mithalten. Hier zeigt die Hochrechnung, dass die NVIDIA A100 die Simulation eines Jahres in knapp unter einer Stunde schaffen würde, während der Dual-Socket AMD EPYC 7543 die Simulation in 2,59 Stunden schaffen könnte.