SC²S Colloquium - December 01, 2017
|Date:||December 1, 2017|
|Time:||3:00 pm, s.t.|
Fabio Gratl: Task Based Parallelization of the Fast Multipole Method implementation of ls1-mardyn via QuickSched
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. 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 implemen- tation of the Fast Multipole Method in the large-scale molecular dynamics code ls1- mardyn. 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. 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.