A CPU–GPU Hybrid Implementation and Model-Driven Scheduling of the Fast Multipole Method

This paper presents an optimized CPU–GPU hybrid imple-mentation and a GPU performance model for the kernel-independent fast multipole method (FMM). We implement an optimized kernel-independent FMM for GPUs, and com-bine it with our previous CPU implementation to create a hybrid CPU+GPU FMM kernel. When compared to an-other highly optimized GPU implementation, our implemen-tation achieves as much as a 1.9 × speedup. We then extend our previous lower bound analyses of FMM for CPUs to include GPUs. This yields a model for predicting the ex-ecution times of the different phases of FMM. Using this information, we estimate the execution times of a set of static hybrid schedules on a given system, which allows us to automatically choose the schedule that yields the best performance. In the best case, we achieve a speedup of 1.5 × compared to our GPU-only implementation, despite the large difference in computational powers of CPUs and GPUs. We comment on one consequence of having such per-formance models, which is to enable speculative predictions about FMM scalability on future systems