Running OpenMPI on CS Lab machines

Some Example MPI Applications to try

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

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