Parallel N-Body Simulation Using Problem Space Promotion

by
Brandon Farrell

Abstract:

N-Body simulations predict the motion of N bodies due to gravitational force given their initial positions and velocities. Cosmologists can use an N-Body simulation to gain insight about the formation of galaxies. However, calculating net gravitational force on N bodies requires calculating on all pairs, an O(N^2) computation, and real world applications may involve millions of bodies. In a gravitation simulation, the individual forces on a body are independent and may be computed in parallel. A parallel algorithm for N-Body simulation could provide a speedup over the typical sequential algorithm, but parallel algorithms may be less efficient if they incur significant communication and synchronization costs. I have researched solving the N-Body problem using a parallel algorithm called Problem Space Promotion, which attempts to reduce communication and synchronization overhead. I have found this new approach leads to efficient parallel performance.

Advised by Larry Snyder

CSE 203
Wednesday
May 28, 2008
4:30 - 5:20 pm