CMSC 818S- Grid Computing

Spring 2004 - Programming Assignment

Due Tuesday, February 24, 2004 @ 6:00PM

The purpose of this programming assignment is to gain experience in parallel programming on a cluster and MPI. For this assignment you are to write a parallel implementation of a program to simulate the game of Life.

The game of life simulates simple cellular automata. The game is played on a rectangular board containing cells. At the start, some of the cells are occupied, the rest are empty. The game consists of constructing successive generations of the board. The rules for constructing the next generation from the previous one are:

    1. death: cells with 0,1,4,5,6,7, or 8 neighbors die (0,1 of loneliness and 4-8 of over population)
    2. survival: cells with 2 or 3 neighbors survive to the next generation.
    3. birth: an unoccupied cell with 3 neighbors becomes occupied in the next generation.

For this project the game board has finite size. The x-axis starts at 0 and ends at X_limit-1 (supplied on the command line). Likewise, the y-axis start at 0 and ends at Y_limit-1 (supplied on the command line).

INPUT

Your program should read in a file containing the coordinates of the initial cells. Sample files are located here and here. You can also find many other sample patterns on the web (use your favorite search engine on "game of life" and/or "Conway").

Your program should take four command line arguments: the name of the data file, the number of generations to iterate, X_limit, and Y_limit.

To be more specific, the command line of your program should be:

life <input file name> <# of generations> <X_limit> <Y_limit>

The number of processes the program will run on is specified as part of the mpirun command with the –np switch (you will instead probably use the pbsmpich command to run the MPI job with the Linux cluster scheduler - see the cluster documentation for more details).

OUTPUT

Your program should print out one line (containing the x coordinate, a space, and then the y coordinate) for each occupied cell at the end of the last iteration.

Sample output files are available:

     life.data.1.100.100.100.out is the output of the file life.data.1 runs for 100 generations on a 100x100 board

     life.data.2.100.100.100.out is the output of the file life.data.2 runs for 100 generations on a 100x100 board

HINTS

The goal is not to write the most efficient implementation of Life, but rather to learn parallel programming with MPI.

Figure out how you will decompose the problem for parallel execution. Remember that MPI (at least the mpich implementation) does not have great communication performance and so you will want to make message passing infrequent. Also, you will need to be concerned about load balancing.

One you have decided how to decompose the problem, write the sequential version first.

WHAT TO TURN IN

You must submit both the sequential and parallel versions of your program (please use file names that make it obvious which files correspond to which version) and the times to run the parallel version on the input file final.data (for 1, 2, and 4 processes), running on a 500x500 board for 500 iterations.

You also must submit a short report about the results (1-2 pages) that explains:

RUNNING MPI with MPICH

To run MPI, you need to set a few environment variables:

setenv MPI_ROOT /usr/local/stow/mpich

setenv MPI_LIB  $MPI_ROOT/lib

setenv MPI_INC  $MPI_ROOT/include

setenv MPI_BIN $MPI_ROOT/bin

# add MPICH commands to your path (includes mpirun and mpicc)

set path=($MPI_BIN $path)

# add MPICH man pages to your manpath

if ( $?MANPATH ) then

     setenv MANPATH  $MPI_ROOT/man:$MANPATH

else

     setenv MANPATH  $MPI_ROOT/man

endif

 

ADDITIONAL RESOURCES

For additional MPI information, see http://www.mpi-forum.org (MPI API) and http://www-unix.mcs.anl.gov/mpi (for MPICH)

For more information about using the Maryland cluster PBS scheduler, MPI, etc., see http://www.umiacs.umd.edu/research/parallel/classguide.htm .