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.  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 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 and Coordinator.java, which you can view in, and save from, your browser.  After you compile these with javac, you can run the result as java Life.  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 node2x14a.csug.rochester.edu

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/8. 

With N rows of board to be updated, I suggest you allocate N/T contiguous rows to each of T threads in the initial (Thread-based) version of the code (taking appropriate care to handle round-off errors cleanly).  In the Executor 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 among true threads is to have them share an instance of java.util.concurrent.CyclicBarrier.  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: 

-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 0.5 seconds per full-board update.  This is only approximate, however, and will vary a bit from run to run, 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.  Alternatively, sit down at a workstation in one of the CSUG labs. 

Machine resources

You will be running this assignment on node2x14a.csug.rochester.edu.  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. 

Note that node2x14a is visible only inside the csug firewall.  Only cycle1, cycle2, and cycle3 are visible from outside.  Thus to run timing experiments from outside the firewall you must first ssh to one of the cycle machines and then ssh from there to node2x14a.  If you’re already in the majors lab or the Hylan lab, you can ssh directly from your desktop to node2x14a

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. 

Analyzing speedup

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 node2x14a, 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 suffice.  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 k with k 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 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. 

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 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 end of the day on Friday, December 2, send e-mail to to cs254@csug.rochester.edu 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 version of the code, explain the purpose of the KilledException class.  Where is it thrown?  Where is it caught? 

MAIN DUE DATE:

Wednesday December 14, at 11:59 pm; no extensions. 
Last Change: 29 November 2016 / Michael Scott's email address