The present work attempts to integrate the independent efforts in the fast N-body community to create the fastest N-body library for many-core and heterogenous architectures. Focus is placed on low accuracy optimizations, in response to the recent interest to use FMM as a preconditioner for sparse linear solvers. A direct comparison with other state-of-the-art fast N-body codes demonstrates that orders of magnitude increase in performance can be achieved by careful selection of the optimal algorithm and low-level optimization of the code. The current N-body solver uses a fast multipole method with an efficient strategy for finding the list of cell-cell interactions by a dual tree traversal. A task-based threading model is used to maximize thread-level parallelism and intra-node load-balancing. In order to extract the full potential of the SIMD units on the latest CPUs, the inner kernels are optimized using AVX instructions. Our code -- exaFMM -- is an order of magnitude faster than the current state-of-the-art FMM codes, which are themselves an order of magnitude faster than the average FMM code.
@cite_30: Algorithms designed to efficiently solve the classical N-body problem of mechanics fit well on GPU hardware and exhibit excellent scalability on many GPUs. Their computational intensity makes them a promising approach for other applications amenable to an N-body formulation. Adding features such as autotuning makes multipole-type algorithms ideal for heterogeneous computing environments.
@cite_28: A novel code for the approximate computation of long-range forces between N mutually interacting bodies is presented. The code is based on a hierarchical tree of cubic cells and features mutual cell–cell interactions which are calculated via a Cartesian Taylor expansion in a symmetric way, such that total momentum is conserved. The code benefits from an improved and simple multipole acceptance criterion that reduces the force error and the computational effort. For N≳104, the computational costs are found empirically to rise sublinearly with N. For applications in stellar dynamics, this is the first competitive code with complexity O(N); it is faster than the standard tree code by a factor of 10 or more.
An example of auto-tuning efforts in FMMs is given by Yokota & Barba @cite_30 , where the dual tree traversal approach by Dehnen @cite_28 was combined with an auto-tuning mechanism by selecting between M2L and M2P kernels to produce a treecode-FMM hybrid code, and by selecting between M2L and P2P kernels to optimize the number of particles at the leaf at which P2P is performed. This is an advantage when developing a black-box library that runs on both CPUs and GPUs without having to worry about selecting the optimal number of particles per leaf for each architecture. This code -- exaFMM https: bitbucket.org rioyokota exafmm-dev -- inherits all the techniques of falcON such as the dual tree traversal, mutual interaction, error aware local optimization of the opening angle @math , and a multipole acceptance criterion based on @math and @math @cite_28 . At the same time, it adds features such as arbitrary order of expansion by using template metaprogramming, periodic boundary conditions, CUDA version of all FMM kernels, and a scalable MPI implementation. The present work is a further extension of this code to thread-level and SIMD parallelism.