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_15: We present the implementation and performance of a new gravitational N-body tree-code that is specifically designed for the graphics processing unit (GPU).1The code is publicly available at: http: castle.strw.leidenuniv.nl software.html.1 All parts of the tree-code algorithm are executed on the GPU. We present algorithms for parallel construction and traversing of sparse octrees. These algorithms are implemented in CUDA and tested on NVIDIA GPUs, but they are portable to OpenCL and can easily be used on many-core devices from other manufacturers. This portability is achieved by using general parallel-scan and sort methods. The gravitational tree-code outperforms tuned CPU code during the tree-construction and shows a performance improvement of more than a factor 20 overall, resulting in a processing rate of more than 2.8 million particles per second.
For GPU optimization of non-uniform distributions for low accuracy, Bedorf @cite_15 developed a highly optimized treecode bonsai https: github.com treecode Bonsai that runs entirely on GPUs. For three significant digits of accuracy in the force calculation for the Laplace kernel, their code is an order of magnitude faster than any other treecode or FMM on GPUs. Their code takes less than 50 milliseconds to calculate one million particles (including the tree construction) on an NVIDIA Fermi GF110 series GPU for the aforementioned accuracy, whereas other codes take about 500 milliseconds to achieve the same accuracy for one million particles. By using warp unit execution and () functions they have eliminated all synchronization barriers from their CUDA kernel. Furthermore, by using mask operations and prefix sums, they have eliminated all conditional branching from their code. However, an application which requires high accuracy may find this code difficult to use, since the order of expansion is not adjustable past @math . Nonetheless, anyone who has experience optimizing fast N-body codes knows that optimizing for low accuracy is much more challenging than optimizing high accuracy codes, so the impact of this work is remarkable.