CS33 -- Laboratory 12

Due: Tuesday, Dec. 7 by 11:59 pm

You are encouraged to work with a partner.

Work in a subdirectory called initslab12, where inits are your initials. Once you have completed the C program, remove any extraneous files so that your directory contains just the .c file(s), the README file and the report. No script files are needed for this lab. Then make a tarball of that directory and send it to me as an attachment to the email whose subject line should be CS33 Lab12. Send the email to cfk@cs.swarthmore.edu.

I will be available for help, if needed, on Thursday, 2 Dec. from 1:15-3:00. Sarah will be available on Thursday, 2 Dec 3-5 and Tuesday, 7 Dec, 2:30-4:30.

For this program, you will implement Conway's Game of Life with and without threads. Once you have your two implementations, you will run some experiments comparing your two solutions varying the number of threads and the size of the grid. You will present your results in a written report. I am indebted to Tia Newhall for suggesting game of life for this lab.

Conway's Game of Life

Conway's Game of Life is an example of discrete event simulation. Here you are simulating a world where entities live, die, or are born based on their surroundings. Each time step simulates another round of living or dying.

Your world is represented by a 2-D array of values (0 or 1). If a grid cell's value is 1, it represents a live object, if it is 0 a dead object. At each discrete time step, every cell in the 2-D grid gets a new value based on the current value of its eight neighbors:

  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 exactly three live neighbors becomes alive.

Your 2-D world should be a TORUS; every cell in the grid has exactly eight neighbors. In the torus world, cells on the edge of the grid have neighbors that wrap around to the opposite edge. For example, the grid locations marked with an 'x' are the eight neighbors of the grid cell whose value is shown as 1. 

x  1  x  0  0  0  0
x  x  x  0  0  0  0 
0  0  0  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  0
x  x  x  0  0  0  0
Conway's Game of Life description from Wikipedia, shows some example patterns you can use to test the correctness of your solution (like Blinker, Toad, Beacon, or a glider).

I will show you in class a way to time sections of code. For now you can get started without the timing code.

If you want a terminal with smaller than usual font size, you can type one of:

xterm -fn 8x13 -rv xterm -fn 6x10 -rv

Machine Info

The Lab Machine specs page contains information about most of the lab machines, including which are dual-core and which are quad-core. Unfortunately it is currently out of date. All of the machines in the main lab have 4 cores. Make sure you run most of your tests on 4-core machines.

As much as possible, it is good to run all your experiements on the same machine, or at least identical machines.

In addition, the department has five 8-core machines, carrot, mushroom, avocado, anise, and pimento. You should run a limited number of experiments on these machines, as you will have to share access to them. Once you are remotely logged into one of those machines, you can find out if there are any other users on it by typing w at the prompt.

Written Report
You should write a short report (no more than 3 pages) that describes the results of your experimentation. It should include the following sections:
  1. A brief description of how you implemented your serial program and how you implemented your threaded program.
  2. A description of the experiments you ran. What did you vary, what machine(s) did you run on, how many runs of each experiment. Also, briefly describe what you thought the expected outcome would be and why? It is fine if your expected outcome was different than what your experimental results show.
  3. Experimental results: present your results AND describe what they show. You can use tables or graphs to present the data. Choose quality over quantity in the data you present. A couple tables with data that show scalability results in terms of number of threads and problem size is fine. It is also okay to present and discuss negative results..."we thought the X experiment would be better because...,but as shown in table 2, the Y experiment performed better. This is (or we think that this is) because ...". There is, however, a difference between negative results (well designed experiments that produce unexpected results) and bad results (results from poorly designed experiments).
  4. Conclusions: what did you learn from your experiments? what do they say about the scalability of your solution? did they match your expectations? if not, do you have an idea of why not?
  5. If you got the serial version but were not able to get a parallel version working, discuss why you think your parallel version was on the right track and why you think it is not working.
  6. If you were not able to get a serial version working, discuss your ideas for the program, why it 'should' work and why you think your serial version is not working.
Submission
Create a tar file containing:
  1. All source,( include, makefiles if you use them) necessary to build and run your programs.
  2. A README file with: (1) you and your partner's names; (2) clear directions on how to run your programs
  3. Your written report (as a pdf) or text file. If you prefer, you may print out your written report and put it in the slot outside my office.

Note: As of 1 Oct, the final exam for CS33 has been scheduled by the registrar for Friday 12/17/2010, 9:00am-12:00pm in SC240. Plan to attend.