The goal of this assignment is to give you some practice using, writing and running a distributed application program written using a message passing library and running on several nodes in the Sun lab. For this assignment you will write a simple program for playing the game of life. You will run the program on several numbers of pvm hosts and examine the performance characteristics of the program as the number of hosts changes.
I encourage you to work with a partner on this assignment. Also, you should not share code with others, but please help each other out in terms of how to run pvm, how to organize the code for a solution, etc.
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:
Using pvm, or jPVM, write a message passing version of the game of life that takes an input size (M and N) for the matrix and K the number of iterations as input, spawns MxN processes (one for each cell) and plays the Game of Life for K steps. 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. Deadlock is a condition where all or some of an application's processes are stuck waiting for an event that will never occur; deadlock occurs when there is a "waits-for" cycle between two or more processes. For example, if process p1 is waiting to receive a message from process p2, and process p2 is waiting to receive a message from process p3, and process p3 is waiting to receive a message from process p1, then there is deadlock. Depending on how you organize your solution, ensuring these conditions may be trivial.
Your program should take 3 command line arguments (M N #iterations), one master process should spawn MxN child processes (or MxN - 1 if the parent participates in the computation). Randomly generate an assignment of LIVE or DEAD (1 or 0) for each (i,j) element in the initial matrix.
Once you get your program working, you should run it for varying numbers of pvm host machines (like 1, 2, 4, 8), two or three different sized problems MxN (small, medium, and large is fine), and for different numbers of iterations (again, two or three different number of iterations is fine).
Measure total execution times for each combination, summarize the results, and write a 1-3 paged report describing your tests, your results, and what conclusions you can draw from your results. You may want to include one or two graphs that summarize your important results (I don't want to see all your numbers, just a summary of your interesting results).
You should run each case multiple times (why?) and think about which value or values to use (think about what makes the most sense and justify your choice in your report). You may want to run your tests early in the morning when the machines are likely to be idle. To do this you can create a perl or awk script to execute some large number of timed runs and use cron to execution your script in the middle of the night. Look at the man page for cron on how to set up jobs to run at a particular time of day. If you use cron, you may want to send mail to cs97, telling when you plan to run your tests and on which machines, so that others can avoid using those machines at that time.
... Iteration 2: Cell[1,3] = 1 Iteration 2: Cell[2,0] = 0 ...(note: if you use pvm_perror() to print from the spawned processes, then the output is in /tmp/pvml.# on the machine on which you started the application. you can turn in an edited version of this output in your README file)
If you work with a partner, please only one of you turn in your program source and report in ~newhall/public/handin/(one group member)/.
Next, look at the references below to figure out how to use pvm to write the Game of Life program. Both have sample programs. Also look at man pages for pvm_send, pvm_recv, pvm_spawn, pvm_barrier, etc.
A list of the Sun lab machines can be found here. Please do not use cumin, garlic, thyme, ginger, tarragon, or allspice as pvm hosts.
[x] PVM: Parallel Virtual Machine, A Users' Guide and Tutorial for Networked Parallel Computing, Al Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek and Vaidy Sunderam, MIT Press Scientific and Engineering Computation, Janusz Kowalik, Editor, 1994
jPVM home page. Contains information on running jPVM and some example programs.