Your task in this, the last assignment of the semester, is to parallelize an existing implementation (in Java) of Conway’s game of Life. The game is described briefly in section 7.4.2 of the textbook. It’s a cellular automaton. The board consists of a conceptually infinite rectangular array of cells, each of which potentially contains an “organism” (in the version I’ll be giving you the board is a finite torus). The organisms move through a series of “generations.” If an organism has two or three neighbors (counting diagonals), it survives to the next generation. If it has fewer than two neighbors it dies of loneliness. If it has more than three neighbors it dies of overcrowding. If an empty cell has exactly three neighbors a new organism is born in that cell in the next generation. The potential patterns on the board are surprisingly rich. In fact, it has been shown that the game is Turing equivalent: one can build self-replicating and evolving structures capable of computing. Additional detail can be found in Martin Gardner’s “Mathematical Games” column in the October 1970 issue of Scientific American.
The code you have been given creates an appropriate (if primitive) graphical display. To run this code as an applet, CLICK HERE. There are five buttons at the bottom of the screen, to run, pause, clear, stop, or quit the game. You can also click the mouse anywhere on the board (when the game is stopped) to toggle cells on and off. Create some initial patterns and see what sort of results you get. Suggested examples:
o o
o o
o o o
o o o o o o o
(Life enthusiasts call these the glider and the spaceship.)
Warning: the code contains artificial delays that make it very
slow; be prepared to wait about 4–5 seconds per generation.
Source code for the applet is in file
Life.java, which you can
view in, and save from, your browser.
The page itself, which you can see by selecting “view
source” in your
browser while running the program, is a trivial HTML file that identifies
the location of Java byte code. That code lies in 15
.class files, most of which are for the user interface.
They are generated by running Life.java through
the Java compiler, javac.
Once you have created your own copy of the program, you can run it (1) in
a browser, (2) with the Sun appletviewer program, or (3)
stand-alone, with the java interpreter / just-in-time
compiler.
Feel free to develop and run on any machine you like, but please make
sure your final code will compiler and run successfully with the
javac and java on the CSUG Linux machines.
(Warning: if you choose to run the code in your browser, you will probably
have to do something special [and browser-specific] to flush its applet
cache; otherwise you won’t see the effect of changes you make to the
code.)
Your assigned task is to create two new versions of the game in which
the board is updated by
a collection of T threads, rather than a single thread.
One version will use threads directly, as was standard in Java 2;
the second version will use the Executor facilities of
Java 5; see the textbook for details.
On a multiprocessor, your new versions of the program would update the
board much more quickly. (Imagine running the game in a window that
fills your entire screen, where every cell is a single
pixel—you might want the parallelism.) Since the machines
we have available are only modestly parallel (the CSUG
cycle machines have 2 cores each, each of which is 2-way
multithreaded), I have built artificial delays into the program that
limit the rate at which any one thread can update cells of the board.
By creating additional threads, you will be able to make the delays
overlap, and the program will run much faster. (This is reminiscent of
the speedup one sees when multithreading a program that needs
to communicate with several other programs over the Internet.)
With N
rows of board to be updated, I suggest you allocate N/T contiguous
rows to each thread or task (taking appropriate care to handle round-off
errors cleanly). The only real trick is to make sure that the threads
move through time generations in lock step—you don’t want
to have one thread updating the cells in row i while some other
thread is trying simultaneously to read them. The easiest way to
achieve the needed synchronization in Java 2 is to create a
barrier object. In Java 5 you can use built-in
Executor methods to force all extant tasks to complete
before starting the next generation.
Note that it is not acceptable to serialize the program: it must
be possible (on a parallel machine) for multiple threads to be working
simultaneously.
As in previous assignments, you may work alone or in teams of two. If you choose to work in pairs, one possible division of labor is for one partner to write Java 2 version and one to write the Java 5 version. If you do this, you’ll want to consult with one another frequently to avoid duplication of effort.
Be sure to follow all the rules on the Grading page. As with all assignments,
use the turn-in script:
~cs254/bin/TURN_IN. Put your write-up in a
README.txt or README.pdf file in the directory in
which you run the script. Be sure to describe any
features of your code that the TA might not immediately notice.
Trivia questions for this assignment can be found in Blackboard. They are due before the beginning of class on Thursday, November 29.
