ExaFMM: An open source library for Fast Multipole Methods aimed towards Exascale systems Lorena A Barba1, Rio Yokota2 1 Boston University, 2 KAUST Left — The simulation of homogeneous isotropic turbulence is one of the most challenging benchmarks for computational fluid dynamics. We have matched the current world record in turbulence simulation, computing a 40963 system on 4096 GPUs with our fast multipole vortex method. This simulation achieved 1 petaflop/s on Tsubame 2.0. Below — Scaling on a massively parallel CPU systems is also excellent. The plot shows MPI weak scaling (with SIMD within each core) from 1 to 32,768 processes, and timing breakdown of the different kernels, tree construction and communications. The test uses 10 miilion points per process, and results in 72% parallel efficiency on 32 thousand processes (Kraken system). GPU Technology Conference, May 2012 What’s new? An open source FMM Want more? Papers and software are online P2P M2L M2P 0 50 100 150 200 250 300 350 GFlops N=104 N=105 N=106 N=107 Left — Actual performance on the GPU of three core kernels, for four different values of N. The M2P kernel of the treecode is able to deliver more flop/s on GPU than the M2L kernel of the FMM. M2M multipole to multipole treecode & FMM M2L multipole to local FMM L2L local to local FMM L2P local to particle FMM P2P particle to particle treecode & FMM M2P multipole to particle treecode source particles target particles information moves from red to blue P2M particle to multipole treecode & FMM Results: Parallel, multi-GPU performance Besides the results shown above, strong scaling runs on CPUs for 10 million bodies per core have shown 93% parallel efficiency at 2048 cores without SIMD, and 54% parallel efficiency at 2048 cores with SIMD kernels. Strong scaling runs on GPUs for 100 million bodies show 65% parallel efficiency on 512 GPUs, while weak scaling runs on GPUs with 4 million bodies per GPU show 72% parallel efficiency on 2048 GPUs. The calculation of isotropic turbulence on a 20483 grid (as shown in the figure above) uses 4 million bodies per GPU on 2048 GPUs. The same calculation using FFTW on 2048 CPU cores of the same machine obtains 27% parallel efficinecy on 2048 cfores. The good scalability of FMMs becomes an advantage on massively parallel systems. All the codes developed in our group are free (like free beer) and open source. To download them, follow the links from our group website: http://barbagroup.bu.edu Also on the website are up-to-date bibliographic references, and papers for download. Please visit! pop stack split cell multipole acceptance criterion push to stack calculate interaction calculate interaction target tree source tree push root pair to stack Initial step Iterative step 1 8 64 512 4096 32768 0 10 20 30 40 Nprocs time [s] tree construction mpisendp2p mpisendm2l P2Pkernel P2Mkernel M2Mkernel M2Lkernel L2Lkernel L2Pkernel 1/16 1/8 1/4 1/2 1 2 4 8 16 32 64 128 256 16 32 64 128 256 512 1024 2048 Operational intensity (flop/byte) Attainable flop/s (Gflop/s) no SFU, no FMA +SFU +FMA Fast N-body (particle-particle) Fast N-body (cell-cell) 3-D FFT Stencil SpMV single-precision peak The fast multipole method (FMM) is a numerical engine used in many applications, from acoustics, electrostatics, fluid simulations, wave scattering, and more. Despite its importance, there is a lack of open community code, which arguably has affected its wider adoption. It is also a difficult algorithm to understand and to program, making availability of open-source implementations even more desirable. Method: Multipole-based, hierarchical There are two common variants: treecodes and FMMs. Both use tree data structures to cluster ‘source particles’ into a hierarchy of cells. See Figure to the right. Multipole expansions are used to represent the effect of a cluster of particles, and are built for parent cells by an easy transformation (M2M). Local expansions are used to evaluate the effect of multipole expansions on