CSE 160 Homework Assignment #5
High Performance game of Life

Part I Due: Tuesday 11/7 in class

Completed assignment: Tuesday 11/21 in class

Changelog

Introduction

In this assignment you'll implement a high performance application with graphical capabilities: Conway's game of Life. The assignment is divided into two parts. You must complete the first part by the first deadline, the entire assignment by the second deadline. This will help keep you on track. The requirements for each part are described below.

Conway's Game of Life

Conway's game of life is a cellular automaton, in which cells living on a 2-dimensional world live, are born, and die over successive generations. The world is defined as a binary-valued array, and each generation evolves according to the following rules, where World^t[i,j] is point i,j in the current generation (t), and World^t+1[i,j] is point i,j in the next generation.

Serial Code

We are providing you with a working serial program that implements Conway's Game of Life. The provided code creates a random world, distributing cells uniformly according to a specified probability. It then runs the game of life for a given number of generations, sending output to the gnuplot plotting program. You'll modify the code to run the game of life and the plotter within two separate MPI processes. Message passing will enable the processes to communicate in a producer-consumer relationship. In the second part you will implement data parallelism, e.g. parallelize, the game of Life. Your program will run on P+1 processes, where 1 process handles the graphics, and the others the simulation.

The code we are providing is found in a public directory which you may access from /export/home/cs160x-public, hereafter known as $PUB. The game of life code is found in $PUB/Life. As with the Ring, the Makefile includes an "arch" file that defines appropriate command line flags for the compiler.

The program may be run from the command prompt as follows:

With the arguments interpreted as follows:

The default parameters are described in cmdLine.C.

And, the command line

will initialize a 100 × 100 world and run the simulation for 200 generations.

NOTE: If a gnuplot window does not appear on your screen, then your SSH display settings are not set correctly. If you are using a Linux based machine and are connecting to Valkyrie using SSH, use the -X option:

If you are using a Windows based machine, and are using a 'secure shell client' AND 'exceed' (or xwin32) to log into Valkyrie, you must ensure that 'X11 tunneling' is set. [If you have problems with this, first read our webboard on this issue. If you still have the problem, send email to Han.]

To access gnuplot, set the following paths in your .bash_profile:
export LD_LIBRARY_PATH=/home/cs160x1/gd-2.0.33/lib
export LD_RUN_PATH=/home/cs160x1/gd-2.0.33/lib

The Assignment

You'll make 3 modifications to the code: handle wrap around boundary conditions, support functional parallelism to handle display, and implement data parallelism to enable you to run on multiple processors so you can simulate larger worlds. The computation will now be divided among several processors while the display will be handled by one processor. The first two parts are due by the first deadline. The data parallelism part is due by the 2nd deadline.

1. Wrap around

When cells move to the edge of the world, they do not have neighbors on the wall itself. This will cause some cells to die out. To eliminate this artifact, modify the code to employ periodic boundary conditions, where neighbors are defined to wrap around to the opposite edge (what about corners?). This will cause a cells to migrate through an edge onto the opposite side, and achieve the effect of an infinite world.

2. Functional Parallelism

The game of life generates intriguing displays as well as insight into the population dynamics. In this part you'll modify the provided serial life simulator to run as two MPI processes. One process (rank = 0) should handle the display (via gnuplot), and the other process (rank=1) should perform the cell updates. Data should be transferred between the processes via messages, and a gnuplot display mesh plot must appear for each iteration.

Setup for gnuplot

To use gnuplot in an mpi program,, instantiate it on the appropriate compute node. This can be done in two steps. First, make sure that the compute node listed as the first entry in the machine-file matches the compute node listed on the first line in the config file. This ensures that this compute node is the one which will be assigned rank=0. Second, in your code, let the process with rank = 0 be the one that runs gnuplot and does the plotting.

To ensure correct X11 forwarding, you need to set up ~/.ssh/config file with the following lines:

Host compute-0-0
  ForwardX11 yes
Host *
  ForwardX11 no

3. Data Parallelism (due 11/21)

This part consists of 2 stages. In Stage A you will implement data parallelism—with the display turned off— and measure parallel speedups. In Stage B you will implement the parallel display functionality.

Stage A

In this stage you will need to turn OFF plotting as it may interfere with your debugging. To implement data parallelism, use a one-dimensional decomposition where the computational domain is be divided (approximately) equally between all processors involved in the computation. You can configure the processors in a way similar to what the Ring program does. There are two options for initializing the game board.

1. Have the root process generate the entire board and distribute to the others.
2. Generate the game board locally on each processor.

If you choose option 2, you will need to carry out a statistics-based performance analysis (see below). You will receive 15% extra credit for completing this options. Although option 1 isn't scalable, if your runs are long enough the impact on performance won't be noticed.

In each iteration, the updates made at each point on the mesh depend on neighboring mesh values. At the boundaries of each processor's part of the mesh, you will have to create and use ghost cells that properly handle periodic boundary conditions. At each iteration, message passing between adjacent processors must be used to populate these ghost cells with appropriate values from neighboring processors. To implement this functionality, You may want to use MPI's topology capabilities discussed in class.

To collecting timing information use the MPI_Wtime() function. The Ring program will show you how to do this. Place the timers around the main computational loop in the code. Collected the running time on each processor separately. Use this information to determine the global maximum, which will give you the overall running time of the entire program.

Determine appropriate values of the the -nx -ny and -nt so that your runs last about 10 to 20 seconds. Measure running times on 1,2,4 and 8 processors, scaling the workload as you increase the number of processors; workload varies as nt × nx × ny. Remember to turn OFF display when collecting this information. Plot the observed running times as a function of the number of processors, which vary together with nx × ny. Also include the data in tabular form. You might notice a difference depending on whether you use rectangular or a square game board, but from here on we'll assume a square game board with defining N= nx = ny = N.

Experimentation

The program allows you to input a random seed via the -s parameter. If you don't specify this parameter, you obtain a seed based on the time of day. The program outputs the seed so that you will be able to reproduce a given run.

Specifying a seed removes some of the variability you notice when you collect timings. When debugging, you'll want to use a fixed seed so that your input will be the same on each run. Depending on which option you chose to initialize the game board, you may or may not want to use a fixed seed.

If you choose option (1), that is, you create the game board on the root, work with a single value of the seed for each value of N. You should repeat each run 3 times, and report the minimum time. But note any outliers that vary, say, by more than 10% above the mean. If necessary, repeat the runs until you can reproduce a minimum timing. When collecting timings, 'warm up' the machine. To do this, run your program a few times in succession and discard the timings obtained from the first run or two.

This strategy will not allow you to measure weakly scaled speedups, where you vary N with P. You must use option (2) for this, where you use a distributed algorithm to initialize the game board.

If you chose option (2), then you will need to collect enough data to smooth out any variability due to the effects of random initializations. In particular, you'll need to make several runs for each combination of N and P. The will enable you to obtain accurate statistical information using the following procedure.

1. First perform 5 runs, letting the program automatically establish different random seeds.
2. Repeat each of these 5 runs 3 times, fixing the reported seed value for each set of 3. That way you will be able to see if there was much variability in timings for a given seed value. This is different from variability due to different random numbers.
3. Take the minimum time over each of the 3 runs for the given seed value. As noted above, you may need to carry out more runs in order to reproduce the minimal timing.
4. You will now have 5 timings representing runs for different seeds. Take the average of these times.
5. Now, repeat the procedure for another 5 runs, but take the average of the full set of 10 runs. Repeat this process until the average no longer varies by more than 5%.

Stage B

In this stage, reinstall and enhance the display functionality, thus combining data and functional parallelism. Since there is only one display server, all computation processors must send their part of the updated mesh to the display processor. The display processor will accumulate the data from all the computation processors before displaying it. You may use the MPI_Gather function to do this (Why isn't this scalable?). Measure the cost of collecting the data for plotting. Do this on 4 and 8 processors, and make plots ranging over a few different values of N. Run with 4 processors for this experiment.

In the previous Part you must have noticed that plotting takes a lot of time. Along with data parallelization, this corresponds to a large 'serial section' which cannot be parallelized, and this will limit the speedups you can get. So in this part, allow your plotter to display only once every 20 iterations.

Your timings will reflect interference from other jobs. On a dedicated run, such interference will be minimal; running times will be shorter and reproducible. We aren't able to make dedicated runs, however. So run the program several times until you see consistent results. If you are still having difficulties getting consistent results, try running on other nodes, working around your classmates. You can find out which nodes are free by consulting the cluster-ps command. Learn how to read the output so you can determine which nodes are free. Then, specify a machine file using those nodes. This is also explained in the Valkyrie document

NOTE: Please don't delay, as when the deadline approaches you may find it difficult to get reliable timings! Be sure to use the randMach.py script to generate random list of compute nodes for your machine-file list.

A new version of Life has been installed called LifeNew. Among other things, this code may be built to use the SPRNG random number generator. Although LifeNew is a serial program, it contains some hooks to help get you started with the MPI implementation, for example, broadcasting command line arguments. The hooks may be enabled by uncommenting the definition of MPI_ON within the Makefile. The code may be configured to use the built in random number generator, or to use SPRNG, a random number generator installed on Valkyrie in PUB/lib/sprng2.0. SPRNG may also be used in parallel mode to ensure multiple independent random number streams, and there are two examples of serial and parallel (MPI) invocations of SPRNG in PUB/examples/sprng_ex. If you are using SPRNG together with MPI, you must assert USE_MPI. If you want to use SPRNG, uncomment the definition of USE_SPRNG in the Makefile.

Things you should turn in

Document your work in a well-written report which discusses your findings carefully. Your report should present a clear evaluation of the design of your code, including bottlenecks of the implementation, and describe any special coding or tuned parameters. Furthermore, it should present your timing and speedup observations, with an analysis that describes your understanding of how the speedups (or any other effect you observe) were obtained. Provide code listings for files you wrote, or that you modified based on versions we gave to you. There is no need to provide listings of code we provided, that you did not modify.

Your report should cite any written works or software as appropriate in the text of the report. Citations should include any software you used that was written by someone else, or that was written by you for purposes other than this class.

Provide hard copy by the due date. Also transmit the report electronically along with your code and your plots. Transmit a single archive file, e.g. .zip, .tgz, containing your writeup, plots, and source code. Email your turnin to hskim AT cs DOT ucsd DOT edu with cse160:hw5-a in the subject line. For the 2nd part of the assignment use the Subject: header cse160:hw5-b.

The name of your tar file should be your Login ID.tar. Your archive file should create a directory with the name of your login ID. Be sure and delete all .o files and executables before creating the tar file. The directory should contain two subdirectories README file):

src:     All source code including your makefile
report: Your report including any separate plot files or output.

If you like, put an html file called index.html at the top level. From there you can then link to a README file as well as the src and report directories.

Sources of information about Conway's game of Life