Your task in this assignment is to parallelize an existing implementation (in Java) of Conway’s game of Life. The game is 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’m 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 we are giving you displays its output in a graphical window. There are five buttons at the bottom of the main window, to run, pause, stop, clear, or quit the game. When the game is stopped, you can click the mouse anywhere on the board 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.)
You should find that the code runs approximately 2 generations per
It would run much faster, except that I have inserted a spin loop that lingers
on each cell when updating the board. This makes the animation slow
enough to watch. It’s also reminiscent of more ambitious iterative
scientific applications in which each update is a time-consuming mathematical
Note that you are not permitted to remove or modify the spin delays, but you
can adjust the speed of your animation by specifying a specific spin value
-s command-line argument (see below).
Starting source code is available in
Coordinator.java, which you can
view in, and save from, your browser.
After you compile these with
javac, you can run the result
Feel free to develop and run on any machine you like, but please make
sure your final code will compile and run successfully with the
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
rows of board to be updated, I suggest you allocate
rows to each of
T threads in the initial (Thread-based)
version of the code (taking appropriate care to handle round-off
In the Executor version, you can use
to create an
Executor with exactly
T threads behind it.
You can then experiment with varying numbers of tasks
Do you get better performance with
For correctness, you will need to
make sure that your threads or tasks
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 among true threads is to have them
share an instance of
In the Executor framework, you can use built-in
Executor methods to force all extant tasks to complete
before starting the next generation.
The code we are giving you accepts two optional command-line arguments:
You can run your application remotely, with X
ssh. You will
probably get better results with
-Y (insecure) forwarding
Alternatively, sit down at a workstation in one of the CSUG labs.
You will be running this assignment on
This machine has two processor chips, each containing 14 cores,
each of which has 2 hardware contexts (hyperthreads). This means
the machine can execute up to 56 threads in
parallel. You will probably find that your code runs faster with 2, 4, or
even 8 threads, but probably slows down again before it gets to 32, due to
thread creation overhead, lack of available concurrency, and/or bus,
memory, or ALU contention.
node2x14a is visible only inside the
are visible from outside.
Thus to run timing experiments from outside the firewall you must first
ssh to one of the
cycle machines and
ssh from there to
If you’re already in the majors lab or the Hylan lab, you can
ssh directly from your desktop to
As the due date approaches, we will reserve much of the time on
node2x14a for timing experiments, with a sign-up system that
allows you to obtain exclusive access to the machine. Note that you
will almost certainly not be able to get last-minute exclusive access, and
since results of timing experiments are required for full credit on the
assignment, you will need to plan to have your code ready for testing
several days ahead of the due date.
The write-up requirements are more extensive for this assignment.
In addition to parallelizing the code and describing what you did, you
must evaluate the success of your parallelization. Using
create a graph that plots, for numbers of threads from 1 to
48, the time required for a glider (see above) to travel from one corner of
the game board to the diagonally opposite corner.
(You do not necessarily have to plot every possible thread
count—that would take a lot of experimentation time. Thread
counts of, say, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, and 48 should
Be sure to use
-s to specify a fixed spin count for all
Also plot the speedup of your
code: the run time of the original (unmodified!) sequential version
divided by the run time of your parallel version. Ideally,
you’d see a speedup of k with k threads. How
close do you come? What bottleneck(s) keep you from doing
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 the Thread version and one to write the Executor 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.pdf file in the directory in
which you run the script. Be sure to describe any
features of your code that the TAs might not immediately notice.
Before the end of the day on Friday, December 2, send
e-mail to to
firstname.lastname@example.org containing answers to
the following questions:
LifeBoardspecify the number of elements in the arrays?
LifeBoardthere are two calls to
repaint(). Where is this function defined?
KilledExceptionclass. Where is it thrown? Where is it caught?