%0 Conference Paper
%A Lengvenis, Arijus
%A Dachsel, Holger
%A Morgenstern, Laura
%A Kabadshow, Ivo
%T A New Spin on the Fast Multipole Method for GPUS: Rethinking the Far-Field Operators
%M FZJ-2025-05345
%D 2025
%X The Fast Multipole Method (FMM) is an optimally efficient algorithm for solving N -body problems: a fundamental challenge in fields like astrophysics, plasma physics and molecular dynamics. It is particularly suited for computing 1/r potentials present in Coulomb and gravitational particle systems. Despite the near-field phase being trivially parallelisable, the far-field phase of the 1/r FMM currently lacks an efficient, massively parallel GPU algorithm fitting for the era of Exascale computing. Current state-of-the-art approaches either favor highly parallel but inefficient expansion shift operators or asymptotically efficient but poorly parallelisable rotation-based ones. Recently, a breakthrough was made with the re-evaluation of a rotation operator variant called fast rotation, which dramatically increases caching effectiveness and marries the advantages of both methods. Thus, this paper incorporates this approach to create fast rotation-based operators that facilitate an efficient far-field algorithm for the FMM on GPUs. Additionally, a warpcentric data access scheme is co-developed alongside a matching octree design, which yields coalesced memory access patterns for the bottleneck operators of the far-field phase. The fast rotation algorithm is enhanced with a cache-tiling mechanism, maximising GPU cache utilisation. Compared to the state-of-theart GPU FMM far-field implementation, our algorithm achieves lower running times across the board and a 2.47 x speedup for an increased precision simulation, with the performance improvement growing as precision increases, providing concrete proof of efficacy for dense particle systems.
%B 2025 IEEE International Parallel and Distributed Processing Symposium
%C 3 Jun 2025 - 7 Jun 2025, Milano (Italy)
Y2 3 Jun 2025 - 7 Jun 2025
M2 Milano, Italy
%F PUB:(DE-HGF)6
%9 Conference Presentation
%U https://juser.fz-juelich.de/record/1049541