Task-based Parallelization of the Fast Multipole Method on NVIDIA GPUs and Multicore Processors

International audienceLearn about the fast multipole method (FMM) and its optimization on NVIDIA GPUs. The FMM is a well-known algorithm with a variety of applications in areas like galaxy simulation, electrostatic potential calculations, boundary element methods, integral equations, dislocations dynamics, etc. The FMM offers several difficulties when running on parallel heterogeneous platforms such as multicore processors with GPUs. Some parts of the calculation suffer from limited concurrency, and load-balancing can be very uneven for certain distributions of particles. We will present a new API and runtime system, called StarPU, that allows expressing a calculation as a graph of tasks, with dependencies, and contains a runtime system that can optimally schedule those tasks on a parallel machine. StarPU supports conventional multicore processors as well as NVIDI