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. To run this code as an applet, CLICK HERE. There are three buttons at the bottom of the screen, to run, stop, or clear the game. There is also a text field that indicates the amount of time that has elapsed between a START-STOP pair of clicks. 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 second.
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
computation.
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
with the -s command-line argument (see below).
Starting source code is available in
Life.java, which you can
view in, and save from, your browser.
The web page in which the program runs when executing as an applet can be
found by selecting “view source” in your browser while running the
program. It’s a trivial HTML file that identifies
the location of the Java byte code. That code lies in several
.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 Oracle appletviewer program, or (3)
stand-alone, with the java JIT compiler.
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
javac and java on the CSUG niagara machines (see
below).
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/6/7
With N
rows of board to be updated, I suggest you allocate N/T contiguous
rows to each of T threads in the Java 2 version of the
code (taking appropriate care to handle round-off
errors cleanly).
In the Java 5 version, you can use
newFixedThreadPool(T) to create an Executor with exactly
T threads behind it.
You can then experiment with varying numbers of tasks
K >= T.
Do you get better performance with
K = T
or
K >> T?
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 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.
The code we are giving you, when run from the command line (rather than as an applet in a browser), accepts two optional command-line arguments:
-s num
-t num
You can run your application remotely, with X
forwarding over ssh. You will
probably get better results with -Y (insecure) forwarding
rather than -X.
You will be running this assignment on
niagara1.csug.rochester.edu and
niagara2.csug.rochester.edu.
Each of these machines has a single processor chip containing 8 cores,
each of which has 4 hardware contexts (what Intel
would call hyperthreads). This means the machine can execute 32 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 or
memory contention. You will also find that sequential code, running on
a single niagara thread, is pretty slow. That’s because the machine is
optimized for 8-core throughput rather than single-core performance (and is
also a few years old). Each core has a single, in-order, 8-stage, 1GHz
pipeline, and all 8 cores share a single floating-point ALU. (The second
generation processor, of which we have a two-chip version on the research
network, has 8 hardware contexts, two pipelines, and a separate FPU per
core.)
For the moment, feel free to use either of the CSUG niagara
machines. As the due date approaches, we will reserve
niagara2 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
well in advance of the due date.
Note that to use the Executor framework you need a Java 5 or 6
implementation; Java 2 won’t do.
You can find the version of your implementation by running java -version.
On the CSUG niagara machines, /bin/java,
/usr/bin/java, and /usr/java/bin/java are all
Java 5, but /usr/staff/bin/java is Java 2.
Your README file has an extra requirement
for this assignment.
In addition to parallelizing the code and describing what you did, you
must evaluate the success of your parallelization. Using the
niagara machines, create a graph that plots, for numbers of threads from 1 to
30, the time required for a glider (see above) to travel from one corner of
the game board to the diagonally opposite corner.
(Be sure to use -s to specify a fixed spin count for all
experiments.)
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 T with T threads. How
close do you come? What bottleneck(s) keep you from doing
better?
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.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.
Before the beginning of class on Tuesday, November 15, send
e-mail to to cs254 containing answers to the following
questions:
A, B,
and T in class LifeBoard specify the number of
elements in the arrays?
LifeBoard there are two calls to
repaint(). Where is this function defined?
Flag object has
synchronized methods. Does this mean the code is concurrent?
Explain.
