Concurrency Assignment

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
Number of iterations of a spin loop to execute per dot when updating the board.  If unspecified, the program will attempt to self-calibrate to ensure about 2 seconds per full-board update.  This is only approximate, however, so when you’re running experiments, be sure to specify an actual value (and the same one every time). 
-t num
Number of threads (max) that should be running at any given time.  This argument is currently unused; it’s there to support your parallelization efforts. 

You can run your application remotely, with X forwarding over ssh.  You will probably get better results with -Y (insecure) forwarding rather than -X

Machine resources

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. 

Analyzing speedup

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? 

Division of labor and parallelization strategy

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. 

On-line resources

Please don’t print the Java documentation files; they’re big.  You should be able to get along just fine reading them in a browser. 

Extra credit suggestions

  1. Add a button that will step the application exactly one generation. 
  2. Modify the stand-alone version of the program so that it can read start-up configurations from a file or web page.  Can you find a way to write configurations to a file? 
  3. Modify the program so that it performs work at each time step proportional to the number of occupied cells, rather than the total number of cells on the board. 
  4. Instead of assigning a contiguous band of rows to each thread, tile the board into rectangular regions in such a way that the total number of boundary elements is minimized.  (This may improve cache locality, and thus performance.) 
  5. Translate the code into C# and experiment with that language’s concurrency features. 

Trivia assignment

Before the beginning of class on Tuesday, November 15, send e-mail to to cs254 containing answers to the following questions: 

  1. Are you working alone or in a group of two?  If the latter, who is your partner? 
  2. Why don’t the declarations of variables A, B, and T in class LifeBoard specify the number of elements in the arrays? 
  3. Within class LifeBoard there are two calls to repaint().  Where is this function defined? 
  4. In the original stand-alone version of the code, explain what happens when a button is pressed.  Note that the Flag object has synchronized methods.  Does this mean the code is concurrent?  Explain. 

MAIN DUE DATE:

Wednesday November 30, at 11:59 pm; no extensions. 
Last Change: 11 November 2011 / Michael Scott's email address