A parallel solution to the N-body problemFall 2001
Background:This was the Final project for CS 471: Scientific computing taught by Dr. Don Morton. There were a few options for final projects but I was (and still am) interested in parallel computing. This program is the solution to a physics problem. This problem and PHYS 221,222: Calculus based Physics taught by Dr. James Jacobs, are the reason I decided to get a Computational Physics degree on top of the combined CS/MATH degree. This program is especially significant because all I was given was the problem and the equations. I had to come up with all of the algorithms and how the data would be passed between processors. In 1-D heat diffusion project I was given more information about how to pass the data.
The Problem:Every particle exerts a gravitational force on every other particle. If we know where every particle is and how massive that particle is, the resultant force on every particle can be calculated. This is the N-body problem: given N particles' position and mass, calculate the force on each particle due to the other particles.
The solution:The Force due to gravity is given by the equation
In order to use parallel processors I split the set of particles into n equal subsets (n=number of processors). Then, in round-robin fasion, each processor's particle position and mass is sent to each processor. Each processor, in turn, then sums the gravitational force vectors. When the program is finished, the data about every point is returned to the main processor for output (if wanted).
Here is the code that I created
The timings from several runs of the program with different numbers of processors and points are in the following table.
What I learned:This was a great project because I had to come up with the algorithms and methods to use. I strengthened my FORTRAN skills and greatly increased my knowledge of MPI. This project also showed that using n processors does not divide the processing time by n. I also learned how to better use the CS department's parallel cluster.
page last updated May 2003
[In the works]
[TV mount] [Diffusion] [N-body] [Vote Montana] [Climate Model] [Portfolio]
[Quantum Computers] [Poker] [Triviabot] [Website Creator] [Movies]
Site Last Updated February 02, 2010