CMSC 483/691P, Parallel Programming

Project 3: The N-body Problem with MPI

(c) 2001, Howard E. Motteler
Assigned Tuesday May 1
Due Tuesday May 22
100 points

Project Goals

The purpose of this project is to get hands-on experience with the MPI (Message Passing Interface) library, and to provide an introduction to distributed "particle computations".

The Project

You are to write a C or C++ program using MPI that reads an array specifying the mass, position, and velocity of a large number of objects, computes their motion under the effects of mutual (Newtonian) gravitation, and then writes an array in the same format, representing their positions after a specified number of time steps. Your program should have the option of writing a sequence of bitmap images to the standard output, representing a projection of the successive positions of the objects.

Specifications

Your program should work for up to 64 processes and 65536 bodies. You can assume that there will be at least two processes, and at least as many bodies as processes. Your program should accept the following parameters, and be able to perform the described functions.

Basic parameters

  -t n   set delta-t (the time increment) to n  (default 1)
  -g c   specify a gravitational constant of c  (default 1)
  -q m   write output and quit after m steps    (default 1)

Input and output files

  -i fin    read input object file fin (default nbodyin.dat)
  -o fout   write output object file fout (default nbodyout.dat)
The input and output files are k x 7 arrays of ascii (%g) format floating point numbers, in which each row or line represents a single object. The seven columns are: 

                     (position)   (velocity)
              mass    x   y   z    x   y   z

Graphic representation of bodies

  -b n   produce an n by n bitmap projection of the x-y 
         plane at every dt step, for values of n up to 512
When selected by the "-b n" flag, a projection of the x-y plane is written as a simple image to standard output at every dt step. (Note that since you are sending data to stdout, any error messages or other printing should be done to sdterr.) Each projection is an n by n bitmap array of 8-bit pixels, written as a row-order stream of bytes with one pixel per byte.

This image region should be a square approximately twice as big as the greatest initial x or y distance. This initial image square should be used for all successive dt steps even though ojects may leave the square or condense to a smaller subregion.

The image should show the distribution of mass in the x-y plane. Each of the n by n pixels corresponds to a small sub-square or tile of the x-y plane. If the x-y coordinates of an object's position fall within a particular pixel's region, we can think of the object as being ``in'' that pixel. A given pixel might have zero, one, or many objects.

A 0-valued pixel represents no mass, i.e., no bodies in that pixel. The value of non-zero pixels represent total mass of bodies ``in'' the pixel. If M is the largest mass (of all the masses, not just those currently in the image square) and S is the non-zero sum of masses in a particular pixel, then that pixel should have the value 

         min(floor(log(S+1) * 255/log(M+1)), 255)
This scales the pixels to integers 0 to 255, and can be plotted directly with a simple greyscale colormap, or rescaled or remapped for fancier plots.

Getting Started

In addition to the n-body examples from your text, a simple Matlab implementation nbody.m is available. This particular implementation is not very efficient, but it may be useful for testing. A MatLab program mkbod.m to generate an initial set of bodies is also available. Some thoughts concerning realistic values for the various parameters of n-body problems, courtesey of Jim Scott, are also available.

Test data

Test data is available as a tar file which includes input and output data for one dT step of 100, 4096, 8192, and 16384 body problems, generated using dT=1 and G=1. You can generate your own test data sets for small numbers of bodies (up to a few hundred) with the MatLab programs mkbod.m and nbody.m. Beware that because of the inherently chaotic nature of the n-body problem, two different but correct implementations may diverge after a sufficiently long sequence of dT steps.

Submitting Your Project

Make a tar file containing the project files, that is, your *.c, *.h, and Makefile, and submit this as an email attachment, with subject "project 3". Make sure that your name and "project 3" are at the top of your main files. At the beginning of your comments you should also mention: (1) how well your project works, including any missing or extra features, and (2) your time for 10 iterations of the in8192.dat test data, excluding read and write time.

Grading

Make sure you read the page concerning general information on programming projects. About 60% of your grade is based on how well your code works, with the remainder of the points divided between design and documentation. Projects are due by midnight of the assigned date; there is a 5% bonus for each day a project is turned in early (for up to two days early), and a 5% penalty for each day the project is turned in late. Extra credit may be given for interesting extra features, including masses with adjustable thrust and improving the bitmap viewer.