CSE 160 Homework Assignment #2
Adding data parallelism to the Game of Life
TO BE DONE IN TEAMS OF TWO
(15 points)

Due: Tuesday 10/21 at 9PM

Changelog

Introduction

In this assignment you'll add data parallelism to your previous assignment, enabling the code to update the game board on multiple threads.

The Assignment

To implement data parallelism, use a one-dimensional decomposition where the computational domain is to be divided (approximately) equally among all processors involved in the computation. You must handle the case where the number of threads does not divide ny. To ensure reproducible results, have the root thread initialize the game board. (Although this approach isn’t scalable, the impact on this assignment won’t be noticed if you run for enough iterations.)

You’ll notice that the serial program we provided 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 this seed so that you will be able to reproduce a given run. In order to establish correctness, run your program on differing numbers of threads,including a single thread. Be sure to handle the case when the number of threads doesn’t divide ny evenly.

A simple way of checking your results against the single processor implementation is to output the contents of all game board locations in a systematic order (say, row major order), printing a single digit (1 or 0) for each position. You can then use the diff program to compare results. Of course, this assumes that your single processor implementation is correct!

Another approach is to run with a problem that has a known solution. The literature is full of such problems. The simplest test cases are static patterns that don’t change from one iteration to the next. Other examples include "blinkers" and "gliders." You can find several examples on the Wikipedia page for Conway’s Game of Life, and there are plenty of other on-line resources. This approach has obvious limitations, especially if you rely on hand inspection. However, by stepping through successive timesteps, you can watch for changes as the moving patterns cross thread boundaries. These are the places where errors are likely to manifest themselves.

To help you in your testing, a new version of life has been provided, together with some other features you may find useful. This code is found in A2.tgz. A new command line option -g has been added, allowing you to select a game number to initialize the board with. One game (for the value of g=1) has been added to the code. Add more at will. Another command line option -step has been added to allow you to "single step" through the game, one iteration at a time. This is handy for watching moving patterns.

Add a new command line argument -nthreads to enable you to specify the number of threads you wish to use to run the program.

Thus, the command line

will initialize a 100 by 100 world and run the simulation for 200 generations on 10 threads.

You may wish to suppress the output, and run for short durations. Another possibility is to modify the code so that you can single step through the timesteps.

Taking timings

Although this assignment will not address performance, we have provided a timer to allow you to measure the running time of your code. See the source module life.c which invokes the getTime() routine found in timer.c

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. Provide pseudo-code listings for code you wrote, or that are based on provided code that you subsequently modified. There is no need to provide pseudo-code for code we provided which you didn’t 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.

As in the first assignment, run a suite of commands to identify the hardware and the environment you used to develop and run your code.

1. Identify the operating system: uname -a
2. Identify the machine you ran on: hostname
3. Identify your compiler and version number: g++ -v (If you aren’t using the Gnu C++ compiler, determine the command needed to generate the version information.)

Place all output from these commands in a file called config.out, e.g. by using the script command.

As in the previous assignment, your turnin will consist of two parts. Turn in in a hard copy of your report in class on Thursday 10/23. Transmit your report electronically by the 9PM deadline on 10/21. Email a single archive file, e.g. .zip, .tgz, containing your writeup and source code. Be sure and delete all .o files and executables before creating the tar file. Email the archive file as an attachment to the following address:

Be sure to put the string cse160:A2 in the subject line and to use the email address above; not doing so may result in a penalty.

The name of your archive file should start with your login ID, e.g. baden.tgz. When your archive file is extracted, a new directory should be created with the name of your login ID. The directory should contain two subdirectories

At the top level of your directory there should be an ASCII file called README.txt, listing all the parts of your electronic submission. If you like, include a .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.