The Fast Multipole Method is an algorithm for computing long-range interactions in N −body problems in linear computational complexity. Since it consists of many individual parts per time step, even optimized fork-join approaches using OpenMP carry a significant synchronization overhead [AMP + 13]. However, these parts do not need to be executed completely after each other, instead, an interweaving is possible. Therefore, task based approaches with a dynamic dependency model are good candidates for parallelization. This thesis describes a task based, shared memory parallelization of the implementation of the Fast Multipole Method in the large-scale molecular dynamics code ls1-mardyn [NBB + 14][Eck14]. Since the approach aims for a maximal scheduling flexibility, the QuickSched library was chosen to create and execute tasks as explicit tasks provided by OpenMP 4.5 are not dynamic enough to model the required dependencies [Gal16]. The approach is tested with a range of parameter configurations and on two different architectures, namely Intel Ivy Bridge and the new state-of-the-art Intel Xeon Phi Knights Landing. Through a detailed analysis of the scheduling and scaling behavior it is shown that the here presented approach can achieve good parallel performance, but is highly dependent on a good choice of parameters for the Fast Multipole Method.     «

The Fast Multipole Method is an algorithm for computing long-range interactions in N −body problems in linear computational complexity. Since it consists of many individual parts per time step, even optimized fork-join approaches using OpenMP carry a significant synchronization overhead [AMP + 13]. However, these parts do not need to be executed completely after each other, instead, an interweaving is possible. Therefore, task based approaches with a dynamic dependency model are good candida...     »

Die Fast Multipole Methode ist ein Algorithmus zur Berechnung der Interaktionen innerhalb eines N −Körper-Problems über große Distanzen in linearer Rechenkomplexität. Da der Algorithmus pro Zeitschritt aus vielen Einzelschritten besteht, bringen auch optimierte fork-join Ansätze, welche OpenMP nutzen, einen signifikanten Mehraufwand durch die erforderliche Synchronisation [AMP + 13]. Da diese Einzelschritte jedoch nicht streng nacheinander ausgeführt werden müssen, ist es möglich diese ineinander zu verflechten. Daher sind task-basierte Ansätze mit dynamischen Abhängigkeiten gute Kandidaten für eine Parallelisierung. Die vorliegende Arbeit beschreibt eine task-basierte Parallelisierung mit geteiltem Speicher für die Implementierung der Fast Multipole Methode im Molekulardynamikcode ls1-mardyn [NBB + 14][Eck14]. Weil der Ansatz auf maximale Flexibilität während des Schedulings abzielt, wurde die QuickSched Bibliothek gewählt, da explizite Tasks von OpenMP 4.5 nicht dynamisch genug sind um die erforderlichen Abhängigkeiten abzubilden [Gal16]. Der Ansatz wird mit einer Reihe von Parameterkonfigurationen auf der Intel Ivy Bridge sowie der modernen Intel Xeon Phi Knights Landing Architektur getestet. Durch eine detaillierte Analyse des Scheduling- und Skalierungsverhaltens wird gezeigt, dass der vorgestellte Ansatz gute parallele Leistung erzielen kann, diese aber jedoch stark abhängig ist von einer guten Wahl der Parameter für die Fast Multipole Methode.      «

Die Fast Multipole Methode ist ein Algorithmus zur Berechnung der Interaktionen innerhalb eines N −Körper-Problems über große Distanzen in linearer Rechenkomplexität. Da der Algorithmus pro Zeitschritt aus vielen Einzelschritten besteht, bringen auch optimierte fork-join Ansätze, welche OpenMP nutzen, einen signifikanten Mehraufwand durch die erforderliche Synchronisation [AMP + 13]. Da diese Einzelschritte jedoch nicht streng nacheinander ausgeführt werden müssen, ist es möglich diese ineinande...     »