Day & Night is a cellular automaton that is a variant of Conway's classic Game of Life. Unlike Conway's game, Day & Night is symmetric: if you invert all the "on" and "off" cells the inverted game acts just like the original, except for the inversion.
In this assignment, the current state of a Day & Night automaton is a square array of cells. Each cell is either "on" or "off". The next state of a cell is "on" if (1) the cell has exactly 3, 6, 7, or 8 neighbors that are currently "on", or (2) the current cell is currently "on" and has exactly 4 neighbors that are currently "on". If neither condition is met, the next state of the cell is "off". The current state of all cells is used to compute the next state of all cells; once this is done, the next state replaces the current state and computation continues with the next generation.
For simplicity's sake, assume that the cells are located on the surface of a torus, so that the top row of cells is adjacent to the bottom row, and the leftmost row is adjacent to the rightmost.
Like most cellular automata, Day & Night is easily parallelizable: a program that is computing the next state of part of the automaton can do so locally, by examining only that part (along with neighboring cells), without worrying about the states of faraway parts. The goal of this assignment is to see how well a particular way of executing the simulation works, when we try to do it on a machine with multiple CPUs.
The basic idea of the simulation is to partition the automaton into smaller squares, each N cells on a side, where N is a positive number that is fixed for the entire simulation. Each partition has 8 neighboring partitions (counting the diagonals). A thread works on one partition at a time. It receives information from the partition's neighbors about states of adjacent cells, computes the next state of each cell in the partition, and then informs its neighbors about the new states of its edge cells.
Write a Java program DayNight that simulates the game of Day & Night, and is invoked as follows:
java DayNight N P G
where:
You may assume that all three numbers are positive integers. The program should read from standard input, which will contain a text file specifying the initial state of the automaton. The text file looks like this:
.OO..... O.OO.... OOOOOOOO O.OO.... .OO.....
Each "O" represents a cell that is on, and each "." represents one that is off. You may assume that the total number of rows and columns is no greater than NP. The input may have fewer than NP rows or columns. If the input has R rows, your automaton shouuld assume that there are floor((NP−R) / 2) rows of "off" cells preceding the input and ceil((NP−R) / 2) rows of "off" cells following the input, and similarly for columns; that way, the input file will be approximately centered in the automaton. If some input lines are shorter than others, act as if the shorter lines were extended on the right with "off" cells.
Your program should output the state of the automaton after G iterations have been executed. The output should omit all leading and trailing rows and columns that contain only "off" cells.
Measure the performance of your program with various values of the numeric parameters, on the host lindbrook.seas.ucla.edu. One way to do this is on SEASnet is to use the Unix time command, e.g., time java DayNight 10 4 100. The Unix command psrinfo -v will tell you some of the physical characteristics of that host. To avoid overloading your machine, please do not specify computations that require more than 16 worker threads (in other words, please do not specify P values greater than 4). Your simulator can use a small fixed number of threads for coordination, e.g., to set up the worker threads.
Assess your work by writing an after-action report that summarizes why you solved the problem the way you did, alternative approaches that you considered and rejected (and why you rejected them), and any weaknesses in the code that you submitted. Focus in particular on any problems you foresee as the problem scales in size. This report should be a simple ASCII text file that consumes at most three pages.
Your implementation should operate correctly under Java Standard Edition 6 Update 3. There is no need to run on older Java versions. Your program should compile cleanly, without any warnings.
To run Java SE 6u3 on SEASnet, you can prepend /usr/local/cs/bin to your PATH, using the same technique you used for the previous homeworks. The command java -version should output the following text:
java version "1.6.0_03" Java(TM) SE Runtime Environment (build 1.6.0_03-b05) Java HotSpot(TM) 64-Bit Server VM (build 1.6.0_03-b05, mixed mode)
To turn in your assignment, submit a single jar file hw3.jar that contains both your Java source code and a plain text file README.txt that holds your assessment. Do not submit class files. Also, please do not put your name, student ID, or other personally identifying information in your files. Before submitting hw3.jar you should test it using the following shell commands on SEASnet:
# Make a fresh directory and change into it. mkdir testdir cd testdir # Extract your program. jar xf ../hw3.jar # Make sure you have a README.txt file. ls -l README.txt # Build your modified version. javac `find . -name '*.java'` # Run your modified version echo 'OOOOO' | java DayNight 10 2 1
The output of the last command should be:
OOO ... OOO
Use CyclicBarrier. For an introduction to CyclicBarrier, see Core Java Technologies Tech Tips (2005-02-16).