CS 85: Distributed Systems, Spring 2008, Swarthmore College, Professor Newhall

Homework 3: MPI programming assignment
Due: Thursday, Feb 28 before 1am (late Wed night)


For this assignment you will write an MPI program, and run and test your program on machines in the CS lab. Once your program works, run some scalability tests of your solutions, and write up a report of your results.

Start by following the instructions below on how to run OpenMPI on the CS lab machines, and then try to run some example MPI programs. After you have some practice setting running these MPI programs, you should implement the Game of Life program as defined below.

Compiling Running MPI applicaitons on our system
Example MPI applications to try out,
The Assignment,
Links to on-line MPI help


Running OpenMPI on CS Lab machines

See my guide for
using OpenMPI on our system for information about how to compile and run OpenMPI applications on our system.

Some Example MPI Applications to try

Before you start coding, try copying over and running some of the sample MPI programs in /home/newhall/public/mpi_examples/

Try running this application with different numbers of processes by modifying the appfile, and login to a node, run top, and watch as processes are spawned and run on that node.


The Assignment

You will implement a solution to the Game of Life Problem in MPI, and you will test your solution for different problem sizes and different numbers of nodes.

The Game of Life is a simple example of a class of problems that can be modeled using cellular automata; some physical and biological systems that evolve over time can be modeled using cellular automata. The problem space is divided into a number of cells each of which is a finite state machine. Each cell's evolution is computed in steps of time; each cell makes one state change, then each cell makes the next state change, and so on.

In the Game of Life, each cell, represented by an (i,j) element in an MxN matrix, contains an organism that is either dead or alive (represented by a 0 or 1). At each step in the game, a cell's state changes based on its current state and the state of its neighbors. The following are rules for a cell's state transition at each step:

  1. A live cell with zero or one live neighbors dies from loneliness.
  2. A live cell with four or more live neighbors dies due to overpopulation.
  3. A dead cell with two or three live neighbors becomes alive.
  4. Otherwise, a cell's state stays unchanged.

Using the OpenMPI implementation of MPI, write a message passing version of the game of life that takes three command line arguments: two dimension values (M and N) for the matrix; and K the number of iterations as input. The easiest way to parallize this program is to have one process for each cell in the MxN matrix. You are welcome to try another way of dividing up the matrix if you'd like (either way is fine). No matter how you decide to distribute the matrix, you should choose one process to be the master (0 is a good choice), and the others to be the slaves. The master should participates as a cell in the MxN matrix (or as a set of cells), but is also responsible for sending slaves their original values and receiving the final result from the slaves and printing it to stdout. I'd recommend using the SPMD model for your program, rather than having separate master and slave executables.

You should also have a debug mode where each slave sends the master its value at the end of a round, and the master after receiving values from all slaves, prints out the MxN matrix of round i values. This will help you debug your solution.

When your program is not running in debug mode, slaves should not send the master their intermediate results.

At each step, each cell needs to exchange information with its neighbors. Keep in mind that a cell in the middle has eight neighbors, and a cell in a corner has only three neighbors, and a cell on an edge has five neighbors. Make sure that at each iteration i, each process gets values from each of its neighbors corresponding to their ith state, and that you solution is deadlock free.

Here is some sample output from a run of my program with a 6x4 matrix for two rounds, with debugging turned on (I just use a compile-time flag, #define DEBUG 1, to turn it on/off):

Start:
------
0 0 0 1 
0 0 0 1 
0 1 0 0 
1 1 1 0 
0 1 0 0 
0 1 0 0 

Round 0:
-------
0 0 1 0 
0 0 1 0 
1 1 0 1 
1 0 1 0 
0 0 0 0 
1 0 1 0 

Round 1:
-------
0 1 0 1 
1 0 1 1 
1 0 0 1 
1 0 1 1 
1 0 1 1 
0 1 0 0 

You will likely want to use buffering to ensure that sends do not block until a corresponding receive has been posted (otherwise you will have to be very very careful about avoiding deadlock). Look at MPI_Buffer_attach and MPI_Buffer_detach routines in section 3.6 of the MPI standard for more information.

Once your program works, you should evaluate its performance when run on different numbers of host machines (for example, 2, 4, 8, 16, ...), for different sized matrices (two or three different sized MxN matrices should be fine). There seems to be a limit to the number of processes OpenMPI will spawn per machine, so depending upon how you allocate processes to cells you may not be able to test all permutations of number of hosts and problem sizes.

Run each game-of-life program for a large number of iterations (make sure your program runs for long enough that you are not just measuring the MPI start-up costs). You can use the time command (% time mpirun -v appfile), to measure total execution time of each run. Also, I suggest writing a script to run all your tests so that you don't have to sit there and run one after the other by hand.

Measure total execution times for each combination, summarize the results, and write a 2-3 paged report describing

  1. how you divided cells up per processes,
  2. your tests,
  3. your results,
  4. and what, if any, conclusions you can draw from your results.
You may want to include one or two tables or graphs that summarize your important results (I don't want to see all your numbers, just a summary of your interesting results).

Look at ~newhall/public/latex_examples, for some Latex document starting points, if you want to use Latex to write up your report. gnuplot and xgraph are graph tools available on our lab machines.

You should run each experiment multiple times (why?). To avoid interference with other uses of the machines, run your experiments when the machines have a low load (i.e. early in the morning, friday or saturday night, ...). To do this you can create a script to execute some large number of timed runs and use cron to initiate execution your script sometime early in the morning. Look at the man page for cron on how to set up jobs to run at a particular time of day (crontab -e to edit a crontab file).

Hand in

Create a tar file with:
  1. your solution source code and appfile(s) and Makefile
  2. and debug output showing the rounds of a run of a 3x4 matrix for 4 iterations:
    % gameoflife 3 4 4    # or 'gameoflife 4 3 4' depending on how you interpret the command line args
    

Send me email with your tar file solution as the attachment.

Either, submit a hardcopy of your report to me (slide it under my office door before the due date), or email me a pdf version of it before the due date.

MPI Links

See my Network and Parallel Programming Links off my unix help pages for MPI FAQs, tutorials, etc.
Except as otherwise noted, the content of this presentation is licensed under the Creative Commons Attribution 2.5 License.