Increasing Parallelism and Reducing Thread Contentions in Mapping Localized N-Body Simulations to GPUs

The use of graphics processors to accelerate N-body simulations has been widely studied. The primary focus of most of these studies has been a class of problems that model the entire system of bodies interacting under Newtonian dynamic laws. A separate class of N-body problems, referred to herein as localized N-body simulations, focus on simulating only a small region of the system, with random state updates in order to find a local optimum. Due to the differences in the problem geometries, the widely applied algorithms and data structures for accelerating N-body simulations are less effective when applied to localized N-body problems. In this chapter, we present techniques for effective parallelization and acceleration of such localized N-body simulations on GPUs. Using energy minimization simulations as a case study, we show the challenges in using the existing data structures in accelerating localized N-body simulations and propose modified data structures and algorithms that enable better parallelism, achieving 7× to 27× speedup over serial code.