The CUDA Handbook: A Comprehensive Guide to GPU Programming

Chapter 14. N-Body

N-Body computations are a family of computation that models a set of particles (known as bodies), each of which must consider all the other bodies during the computation. Example applications of N-Body include (but are not limited to) the following.

• Gravitational simulation in which stars exert gravitational forces

• Molecular modeling in which ions exert electrostatic forces

• Particle systems in computer graphics to simulate water and fire

• “Boids,” a technique for computer animation designed to simulate flocking behavior

Typically the paths of the bodies are being simulated per timestep, and computing each timestep costs O(N²) operations for N bodies. In most formulations, the forces quickly decrease with distance, leading ...