A parallel solution to the N-body problem

Fall 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

F=(G)(M1)(M2)/(R^2)

In this equation F is the force due to gravity, G is the gravitational constant, M1 and M2 are the masses of the two particles and R is distance between the particles. F is a vector that points from one point to the other. The total force due to gravity on any one particle is the vector sum of all possible F. So if there are 10 points, each point has 9 force vectors due to gravity that must be added together to get the total force due to gravity.

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
nbody.F

The timings from several runs of the program with different numbers of processors and points are in the following table.

1 processor	2 processors	4 processors	8 processors
1000 points	1000 points	1000 points	1000 points
2000 points	2000 points	2000 points	2000 points
4000 points	4000 points	4000 points	4000 points
8000 points	8000 points	8000 points	8000 points
16000 points	16000 points	16000 points	16000 points

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

[Home] [About me] [My projects] [Resume] [In the works] [online diary]
[TV mount] [Diffusion] [N-body] [Vote Montana] [Climate Model] [Portfolio]
[Quantum Computers] [Poker] [Triviabot] [Website Creator] [Movies]