Communication-Optimal Parallel N-body Solvers

We present new analysis, algorithmic techniques, and implementations of the Fast Multipole Method (FMM) for solving N-body problems. Our research specifically addresses two key challenges. The first chal-lenge is how to engineer fast code for today’s plat-forms. We present the first in-depth study of multi-core optimizations and tuning for FMM, along with a systematic approach for transforming a conventionally-parallelized FMM into a highly-tuned one. We in-troduce novel optimizations that significantly improve the within-node scalability of the FMM, thereby en-abling high-performance in the face of multicore and manycore systems. The second challenge is how to understand scalability on future systems. We present a new algorithmic complexity analysis of the FMM that considers both intra- and inter-node communica-tion costs. This analysis yields the surprising predic-tion that although the FMM is largely compute-bound today, and therefore highly scalable on current sys-tems, the trajectory of processor architecture designs— if there are no significant changes—could cause it to be-come communication-bound as early as the year 2020. This prediction suggests the utility of our analysis ap-proach, which directly relates algorithmic and architec-tural characteristics, for enabling a new kind of high-level algorithm-architecture co-design.