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. For this assignment, we will look only at periodic automata, for simplicity's sake.
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 the previous state, without worrying about the next states of other cells. The goal of this assignment is to see how well particular ways 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 work of computing the next state into T smaller pieces, where T is a positive number that is fixed for the entire simulation. T corresponds to the number of threads in your program. 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.
There are several plausible ways to partition the work; this assignment asks you to use one partitioning method. In this method, the S cells of the simulation are sequentially indexed 0, 1, 2, ..., S−1. The Jth of T threads (where J ranges from 0 through T−1) computes the next state of each cell whose index C is such that (J*S)/T <= C && C < ((J+1)*S)/T. Here the / operator denotes integer division, which truncates towards zero.
There are also several plausible ways to coordinate the threads; this assugment asks you to investigate two of them. In the first method, called the join method, the parent process creates and runs T threads to compute the next state, waits for all T threads to finish, and then creates and runs T more threads to compute the next state. In the second method, called the cyclic barrier method, the parent process creates T threads only at the very beginning, and the threads coordinate with each other when they finish computing one state so that they can safely go on to start computing the next state.
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, using a periodic automaton, and is invoked as follows:
java TDLife T N G R1 R2 R3 R4 M
where:
You may assume that all input numbers are nonnegative integers.
The program should begin in an initial state in which the first four cells (numbered 0, 1, 2, 3) are on, and all other cells are off. (If N is 1, then turn on just the zeroth cell.) It should run the simulation for G steps, and then output the resulting to standard output in the form suggested by the following example for N=5, G=4, R1=2, R2=5, R3=3, and R4=4:
O.OO. ...OO ....O ....O O.OOO ...OO ....O ....O ..... ....O ....O ....O ..... ..... ....O ....O ..... ..... ....O O..OO O.OOO ....O ....O O..OO OOOO.
Each "O" represents a cell that is on, and each "." represents one that is off. The first group of O and . represents the zeroth plane of cells, and so forth for each plane.
It may be helpful for debugging if your program also acts as an applet. It needs slightly different input elements (for T and M) 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=t value="1">
<param name=n value="5">
<param name=rules value="3 4 3 2">
<param name=m value="0">
</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 lnxsrv03.seas.ucla.edu. One way to do this is on SEASnet is to use the Unix time command. The file /proc/cpuinfo will tell you some of the physical characteristics of that host. To avoid overloading SEASnet, please do not specify computations that require more than 256 worker threads. 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 the performance that you observed. Which method works better, quotient or modulus? Which number of threads seems to work best? Focus in particular on any problems you foresee as the problem scales in size, and which method you expect to work better in general (even if you couldn't measure the difference on SEASnet). 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 15. There is no need to run on older Java versions. Your program should compile cleanly, without any warnings.
The command java -version should output the following text:
java version "1.6.0_15" Java(TM) SE Runtime Environment (build 1.6.0_15-b03) Java HotSpot(TM) 64-Bit Server VM (build 14.1-b02, 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 java TDLife 10 5 4 2 5 3 4 1
Use CyclicBarrier. For an introduction to CyclicBarrier, see Core Java Technologies Tech Tips (2005-02-16).