CMSC 483/691P, Parallel Programming

Project 2: The N-body Problem with MPI

Assigned Monday, April 3
Due Wednesday, April 19
60 points

Project Goals

The purpose of this project is to gain experience with parallel programming by solving a problem that balances computation and communication in a way that allows for significant speedup on a distributed system.

Project Summary

You are to write a parallel program using MPI that (1) reads a file specifying the mass, position, and velocity of a large number of objects, (2) computes their motion under the effects of mutual gravitation, approximated with a series of discrete time-steps, and (3) writes a file, in the same format as the input, representing their positions after a specified number of time-steps.

Specifications

Your program should read a file nbod_init.dat that specifies the mass, initial positions, and velocities of the bodies, and write a file nbod_last.dat in the same format giving their mass and final positions and velocities.

The input and output data is saved in a format that begins with two 32-bit integers specifying the number of rows (this value is always 7) and the number of columns, equal to N. The rest of the values in the file are 32-bit floats, organized in COLUMN-ORDER as follows: 

                        objects
                   1   2   3  ...  N 
                 +----------- ... ---+
        mass     |                   |
     x position  |                   |
     y position  |                   |
     z position  |                   |
     x velocity  |                   |
     y velocity  |                   |
     z velocity  |                   |
                 +----------- ... ---+
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 optional command line parameters. 

  -k m     run for m steps, default value 20
  -t dT    set the time increment to dT, default value 0.005
  -g G     specify a gravitational constant G, default value 1
  -i fin   specify an input file name, default nbod_init.dat
  -o fout  specify an output file name, default nbod_last.dat

Getting Started

You should write a sequential version of the program first. This will resolve basic issues like i/o, managing arrays, and doing the gravitational calculations. Then choose a parallel design, focusing on how you want to distribute data across the cluster and move it during the course of your computations.

A Matlab demo n-body implementation nbody.m is available. It is not very efficient but it may be useful as an example, and it lets you watch the bodies move as the time-steps are calculated.

Test data

A basic set of test data is available as a tar file. This includes input and output data for one dT step of 1024, 4096, and 16384 body problems generated with the default values dT=.005 and G=1.

You can generate your own test data sets for small numbers of bodies (up to a thousand or so) 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 long sequence of dT steps.

Submitting Your Project

Make a tar file with everything necessary to build and run your code, including a Makefile, optional README, and any supporting documentation you think is relevant. Please don't include any ".doc" files, I don't want to have to fire up Open Office. At the beginning of your comments you should (1) say how well your project works, including any missing or extra features, and (2) give your time for 20 iterations of the 16384-element test data set, excluding read and write time.

Make sure that your name and "Project 2" are at the top of your main files. Mail this to me as an email attachment, with subject "Project 2". Do not mail data sets unless they are relatively small and there is a good reason to do so.

Grading

Please read the notes on general information on programming projects. Half your grade will be based on how well your code works, one quarter on design and code sanity, and one quarter on documentation. The documentation should include an honest evaluation of how well your code works, as best you are able to determine. 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.

Return to Course Information