Java Assignment

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. 

Division of labor and writeup

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. 

Resources

Please don’t print these; 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.  (This is a bit tricky for applets, due to Java’s security features.)  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 full cells, rather than the total number of square 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 would improve cache locality on a parallel machine.) 

Trivia Assignment

Trivia questions for this assignment can be found in Blackboard.  They are due before the beginning of class on Thursday, November 29

MAIN DUE DATE:

Friday December 14, at 5:00 pm; no extensions. 
Last Change: 25 November 2007 / Michael Scott's email address