3-dimensional cellular automata have been proposed as fundamental building blocks for understanding many physical processes. You're working for a small research lab that is investigating how well this works, and which is running some big simulations of automata. The simulations are Java-based, but none of the developers has had the time yet to parallelize them. You've been asked to estimate how much performance advantage you'll actually get on your lab's hardware (which is kind of old and slow, unfortunately; in this early stage of research they haven't received enough money yet to get good hardware). You decide to do a quick-and-dirty estimate based on the simplest simulator your lab uses. It's called ALife and it does just 3D Life. It's a bit of a toy but it does illustrate the principles. It currently runs only as an applet; you'll need to modify it so that it can also run as a standalone program, so that we can test it.
3D Life is a cellular automaton that is a variant of Conway's classic Game of Life. Unlike Conway's game, 3D Life is in three dimensions, so that each cell has 26 neighbors rather than 8; also, its rules are somewhat programmable.
In this assignment, the current state of a 3D Life automaton is a 3-dimensional array of cells. Each cell is either "on" or "off". The next state of a cell is "on" if and only if (1) the cell was formerly "off" and it has no less than R1 and no more than R2 neighbors who are "on", or (2) the cell was formerly "on" and it has no more than R3 and no less than R4 neighbors. The values R1 through R4 are the "program" for the 3D Life game. 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.
If the game is nonperiodic, cells adjacent to the edge of the 3D array are adjacent to imaginary cells that are always "off". If the game is periodic, cells are located on the surface of a 4-dimensional torus, so that the top surface of cells is adjacent to the bottom surface, the left surface is adjacent to the right surface, and the bottom surface is adjacent to the top.
Like most cellular automata, 3D Life 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 cubes, each N cells on a side, where N is a positive number that is fixed for the entire simulation. Each partition has 26 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.
Modify the ALife program described in Kaleidoscope of 3D Life (source code zip file). Turn it into a Java program TDLife that simulates the game of 3D Life, and is invoked as follows:
java TDLife N P G R1 R2 R3 R4 B
where:
You may assume that all input numbers are nonnegative 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. O.OOO O.OO. .OO.. .OO.. O.OO. OOOOO O.OO. .OO.O .OO.. O.OO. O.... O.OO. .OO.. .OO.. O.OO. ....O O.OO. .OO.. .OO.. O..O. OO... O.OO. .OO..
Each "O" represents a cell that is on, and each "." represents one that is off. The first group of O and . represents the first plane of cells, and so forth for each plane. Report an error and exit immediately if any line contains more than NP columns, and similarly for the number of lines and the number of planes. If some input lines are shorter than others, act as if the shorter lines were extended on the right with "off" cells; similarly, if some input planes have fewer rows than others, assume that the shorter planes were extedned on the bottom with "off" cells. After this adjustment, the input may still have fewer than NP rows, columns, or planes. If the input has R rows, your automaton should assume that there are ⌊(NP−R) / 2⌋ rows of "off" cells preceding the input and ⌈(NP−R) / 2⌉ rows of "off" cells following the input, and similarly for columns and planes; that way, the input file will be approximately centered in the automaton.
Your program should output the state of the automaton after G iterations have been executed, using the same format as the input. The output should omit all leading and trailing rows, columns, and planes that contain only "off" cells.
It will be helpful for debugging if your program also acts as an applet. It needs one more input element (for P) than ALife does. You should be able to use this applet by creating a web page www/index.html in your home directory on SEASnet, with contents that look something like this:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>Multithreaded 3D Life</title>
</head>
<body>
<h1>Multithreaded 3D Life</h1>
<applet code="TDLife.class" width=600 height=600>
<param name=n value="5">
<param name=p value="2">
<param name=rules value="3 4 3 2">
</applet>
<p>(Useful information about running your applet goes here.)</p>
</body>
</html>
You can then visit the URL http://www.seas.ucla.edu/~yourlogin/ with a Java-enabled web browser to try your applet out.
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. 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 27 worker threads (in other words, please do not specify P values greater than 3). 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 11. There is no need to run on older Java versions. Your program should compile cleanly, without any warnings.
To run Java SE 6u11 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_11" Java(TM) SE Runtime Environment (build 1.6.0_11-b03) Java HotSpot(TM) 64-Bit Server VM (build 11.0-b16, 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 'OOO' | java TDLife 10 2 3 3 4 3 2 0
The output of the last command should be:
..... ..... ..O.. ..O.. ..O.. ..... ..... ..... ..O.. .O.O. O...O .O.O. ..O.. ..... ..O.. .O.O. O...O O...O O...O .O.O. ..O.. ..O.. O...O O...O O...O O...O O...O ..O.. ..O.. .O.O. O...O O...O O...O .O.O. ..O.. ..... ..O.. .O.O. O...O .O.O. ..O.. ..... ..... ..... ..O.. ..O.. ..O.. ..... .....
Use CyclicBarrier. For an introduction to CyclicBarrier, see Core Java Technologies Tech Tips (2005-02-16).