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_41: 
@cite_38: Fast multipole methods have O(N) complexity, are compute bound, and require very little synchronization, which makes them a favorable algorithm on next-generation supercomputers. Their most common application is to accelerate N-body problems, but they can also be used to solve boundary integral equations. When the particle distribution is irregular and the tree structure is adaptive, load-balancing becomes a non-trivial question. A common strategy for load-balancing FMMs is to use the work load from the previous step as weights to statically repartition the next step. The authors discuss in the paper another approach based on data-driven execution to efficiently tackle this challenging load-balancing problem. The core idea consists of breaking the most time-consuming stages of the FMMs into smaller tasks. The algorithm can then be represented as a Directed Acyclic Graph (DAG) where nodes represent tasks, and edges represent dependencies among them. The execution of the algorithm is performed by asynchronously scheduling the tasks using the QUARK runtime environment, in a way such that data dependencies are not violated for numerical correctness purposes. This asynchronous scheduling results in an out-of-order execution. The performance results of the data-driven FMM execution outperform the previous strategy and show linear speedup on a quad-socket quad-core Intel Xeon system.
@cite_34: A new O(N) fast multipole formulation is proposed for non-oscillatory kernels. This algorithm is applicable to kernels K(x,y) which are only known numerically, that is their numerical value can be obtained for any (x,y). This is quite different from many fast multipole methods which depend on analytical expansions of the far-field behavior of K, for |x-y| large. Other ''black-box'' or ''kernel-independent'' fast multipole methods have been devised. Our approach has the advantage of requiring a small pre-computation time even for very large systems, and uses the minimal number of coefficients to represent the far-field, for a given L^2 tolerance error in the approximation. This technique can be very useful for problems where the kernel is known analytically but is quite complicated, or for kernels which are defined purely numerically.
Last but not least, there have been a few recent attempts to use event-driven runtime systems for optimizing the data flow of parallel FMM codes. Ltaief & Yokota @cite_38 used QUARK http: icl.cs.utk.edu quark index.html to schedule the threads dynamically according to a directed acyclic graph that represents the data flow of exaFMM 's dual tree traversal. Dekate take a similar approach but using ParalleX http: stellar.cct.lsu.edu tag parallex for the runtime system and a classical Barnes-Hut treecode @cite_41 for the fast @math -body solver. Agullo use StarPU http: runtime.bordeaux.inria.fr StarPU along with the black-box FMM @cite_34 on a CPU+GPU environment. Peric 'as use OmpSs http: pm.bsc.es ompss with exaFMM . These are all preliminary results, and large gains from using runtime systems have yet to be reported.