The computational solution to the N-body problem is quite simple: it is simply a double loop. In C code,
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
F(i, j);
}
}
The parallel solution, is of course, somewhat more difficult. In this
lecture, we present three general approaches to solving the N-body problem
on a parallel machine: a message-passing ring method; several variants
on a data parallel digital orrery; and a force decomposition method.
One MPI strategy is to use a ring processor topology, where each processor keeps a subset of the particles, and sends a copy of this data around to visit all of the other processors. An implementation of this algorithm has been provided as the MPI N-body program.
Since there are a number of files in the MPI N-body program, it is packaged as a compressed tar file. To extract the files, download the previous link to your own account (shift left-mouse does this in Netscape) and extract the file with the command
"zcat mpi_nbody.tar.Z | tar xvf -"Note: depending on your Web browser configuration, the file may be uncompressed while you download it; in that case just use
"tar xvf mpi_nbody.tar"This will put the files in a subdirectory called mpi_nbody. You can then compile the program with "make" and run it with "llsubmit run_sp1". The nbody.out file will contain the output of the program after it runs. It should look a lot like:
{taos} 428 % cat nbody.out
Welcome to the MPI N-body code on 8 procs
Calling ring...
cycle 1 starting
cycle 2 starting
cycle 3 starting
cycle 4 starting
cycle 5 starting
cycle 6 starting
cycle 7 starting
Total nobj is 8192
Total potential energy is -0.60625422
Total kinetic energy is 0.30217558
Wall clock time: 19.16 seconds
Bye.
A suite of programs implenting data parallel analogs of the MPI ring code can be found in the HPF nbody tar file. The codes and associated makefiles, SP-1 run scripts can be unpacked in the same manner described above for the MPI version: "zcat hpf_nbody.tar.Z | tar xvf - ". This command will create a subdirectory called hpf_nbody containing the following programs: (under construction)
The force-decomposition method for molecular dynamics (MD) simulation was developed by Steve Plimpton at the Sandia National Laboratories Massively Parallel Computing Research Laboratory (MPCRL). A copy of the original paper on this method can be downloaded directly from Sandia, along with copies of full-blown MD codes implementing several other techniques (see the links listed under Lennard-Jones molecular dynamics (MD)).
Download MPE_PHYS500.tar.Z for source code described in class. Instructions for running the force_decomp code are also available.
Back to Practical Parallel Computing (Physics 500) Home Page
Last modified: October 13, 1995