Download GameOfLife.zip
Introduction
The "Game of Life" is a mathematical representation of human evolution, in which a few patterns develop through time. Each pattern changes the state of the bidimensional orthogonal universe through the evolution of time. It is very cool to see and, with easy rules, it has incredibly complex behaviour.
Rule
The Life universe is very simple. A square grid contains cells, which may be dead or alive. The behaviour of each cell interacts with its eight neighbours, according to the following rules:
- Any live cell with fewer than two live neighbours dies, as if caused by under-population.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by over-population.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
It starts with a pattern on the grid - generation at time t0 - and it apply the rules at the same time, on all cells. This action results in a new pattern (generation at time t1) in which the state of bidimensional universe has been changed.
Afterwards, we apply the rules, again, on all the cells, etcetera.
That’s it. There are no other rules.
Approach
There are differents mode to approach the problem.
There is the Probability that an unskilled developer would depart directly from the rules, without any analysis, implementing maybe the pattern MVC, without taking advantage of a possible concurrent programming style.
Most concurrent applications are organized around the execution of tasks: dividing the work of an application into tasks simplifies program organization, facilitates error recovery by providing natural transaction boundaries, and promotes concurrency by providing a natural structure for parallelizing work, acting in asynchronous mode.
Steps in Design Space
Firstly, we have to analyze the problem of identify exploitable concurrency and, then, a concurrent architecture. We can do it by identifying:
- possible Tasks
- a sequence of instruction that corresponds to some logical part of the algorithm. In practice this is a piece of work required to be done as a assignment (design-oriented definition)
- data decomposition and their dependencies
- mapping tasks in entities
- activate the entities responsible for performing task
- encapsulate the control logic of task execution
Data Decomposition Pattern
Conceptual class
The problem can be easily decomposed into units that can be operated relatively independently; like a divide-et-impera principle, it can be naturally decomposed into a collection of independent tasks:
- tasks must be sufficiently independent so that managing dependencies takes only a small fraction of the program’s overall execution time
- independence facilitates concurrency, as independent tasks can be executed in parallel if there are adequate processing resources
- choosing good task boundaries, coupled with a sensible task execution policy, can help achieve these goals.
More precisely:
- first, data units are identified, then task related so that units can be identified
- in this case, task decomposition follows data decomposition
- the execution proceeds in asynchronous mode: different tasks help to calculate the result and, afterwards, they are synchronized in passive mode through a simple monitor
Caution regarding synchronization: poisoning of the concurrent programming style
- serializations / sequentialization are poison for performances
- but are necessary for correctness (safety properties)
We cannot have everything in life, each story has two faces :-)
Architectures and patterns
In this case I’ll use the Master-Workers pattern.
The architecture is composed by a master entity and a dynamic set of worker entities, interacting through a proper coordination medium functioning as a bag of tasks
- Master
- decompose the global task into subtasks
- assign the subtasks by inserting their assignment in the bag
- collect tasks result
- Worker
- retrieve the task to do from the bag, execute the task
- communicate the results
- the monitor of data structures can be used to aggregate and synchronize the results
Architecture
It has selected an MVC architecture, in which:
- View:
- start the algorithm
- stop the algorithm
- design the cell over the grid
- check the number of cell lives
- Controller:
- setup the Model and View
- implement the start method
- create a Flag for “safe start”
- call the Model for starting the algorithm
- implement the stop method
- Model:
- The Model is the core of all project, that implements the strategy chosen.
- We have chosen the Executor Framework to realize the strategy above: this Executor is based on the producer-consumer pattern, where activities that submit tasks are the producers (producing units of work to be done) and the threads that execute tasks are the consumers (consuming those units of work).
Let’s start!
View:
public GameOfLifeView(Dimension windowsSize, Dimension matrixSize,int blockSize) {
super("Game Of Life Viewer Small Grid");
setSize(windowsSize);
setLocation(
(Toolkit.getDefaultToolkit().getScreenSize().width - getWidth()) / 2,
(Toolkit.getDefaultToolkit().getScreenSize().height - getHeight()) / 2
);
listeners = new ArrayList<inputlistener>();
startButton = new JButton("start");
stopButton = new JButton("stop");
stopButton.setEnabled(false);
JPanel controlPanel = new JPanel();
controlPanel.add(startButton);
controlPanel.add(stopButton);
setPanel = new GameOfLifePanel(matrixSize, blockSize);
setPanel.setSize(matrixSize);
addMouseMotionListener(this);
addMouseListener(this);
JPanel infoPanel = new JPanel();
state = new JTextField(20);
state.setText("Ready...");
state.setEditable(false);
infoPanel.add(new JLabel("State"));
infoPanel.add(state);
JPanel cp = new JPanel();
LayoutManager layout = new BorderLayout();
cp.setLayout(layout);
cp.add(BorderLayout.NORTH, controlPanel);
setPanel.CannoneAliantiGosper();
cp.add(BorderLayout.CENTER, setPanel);
cp.add(BorderLayout.SOUTH, infoPanel);
setContentPane(cp);
startButton.addActionListener(this);
stopButton.addActionListener(this);
setDefaultCloseOperation(EXIT_ON_CLOSE);
setResizable(false);
}
First, I create the View in which I insert:
- Button to start
- Button to stop
- Grid (set Panel is the class that implements the Grid)
- label for check the cells - dead or alive -
Once created the view, the result of the GUI should be this:
Controller:
public class Controller implements InputListener {
private GameOfLifeView view;
private GameOfLifeSet set;
private Flag stopFlag;
public Controller(GameOfLifeSet set, GameOfLifeView view){
this.set = set;
this.view = view;
}
@Override
public void started(ArrayList< point > matrix){
set.setupMatrix(matrix);
stopFlag = new Flag();
new QuadratureService(set,view,stopFlag, matrix).start();
}
@Override
public void stopped() {
stopFlag.set();
}
}
The class Controller is very simple: given the structure of the program, the controller limiteds to linking the model and the view, creating the monitor for the method start and stop.
Model:
The Model of the program is the core the article, in which the architecture explained above comes to life.
First I create the class QuadratureService that:
- create the thread Master that returns the status of all cells "live" or "dead" to the grid.
- Next, it update the grid of the model (GameOfLifeSet) and view (GameOfLifeView)
public QuadratureService(GameOfLifeSet set, GameOfLifeView view, Flag stopFlag, ArrayList< point > matrix) {
this.view = view;
this.set = set;
this.stopFlag = stopFlag;
pointBoardT0 = new boolean[3][3];
}
@Override
public void run() {
try {
if (set.getMatrix().isEmpty()) {
stopFlag.set();
view.changeState("No point in Matrix!");
}
while (!stopFlag.isSet()) {
Thread.sleep(50);
int poolSize = Runtime.getRuntime().availableProcessors() + 1;
Master master = new Master(set, poolSize, stopFlag);
ArrayList< point > result = master.compute();
set.setupMatrix(result);
view.setUpdated(result);
if (stopFlag.isSet()) {
view.changeState("Interrupted. Cell live: " + result.size());
} else
view.changeState(String.valueOf(result.size()));
}
} catch (Exception ex) {
ex.printStackTrace();
}
}
The Thread Master is an Executor, more precisly an Executors.newFixedThreadPool(poolSize);
But, why should I use it?
- newFixedThreadPool. A fixed-size thread pool creates threads as tasks are submitted, up to the maximum pool size, and then attempts to keep the pool size constant (adding new threads if a thread dies due to an unexpected Exception).
- newCachedThreadPool. A cached thread pool has more flexibility to reap idle threads when the current size of the pool exceeds the demand for processing, and to add new threads when demand increases, but places no bounds on the size of the pool.
To keep it simple: I have created one asynchronous task for each cell alive. Statistically the cell alive are a number very high, so I prefered use the method newFixedThreadPool.
public Master(GameOfLifeSet set, int poolSize, Flag stopFlag) {
this.executor = Executors.newFixedThreadPool(poolSize);
this.set = set;
this.stopFlag = stopFlag;
}
public ArrayList< point > compute() throws InterruptedException {
ArrayList< future < point > > pointT1 = new ArrayList< future < point > >();
gameBoard = new boolean[set.getSizeX() + 1][set.getSizeY() + 1];
for (Point current : set.getMatrix()) {
if (current != null)
gameBoard[current.x + 1][current.y + 1] = true;
}
for (int i = 1; i < gameBoard.length - 1; i++) {
for (int j = 1; j < gameBoard[0].length - 1; j++) {
try {
pointBoardT0 = new boolean[3][3];
pointBoardT0[0][0] = gameBoard[i - 1][j - 1];
pointBoardT0[0][1] = gameBoard[i - 1][j];
pointBoardT0[0][2] = gameBoard[i - 1][j + 1];
pointBoardT0[1][0] = gameBoard[i][j - 1];
pointBoardT0[1][2] = gameBoard[i][j + 1];
pointBoardT0[2][0] = gameBoard[i + 1][j - 1];
pointBoardT0[2][1] = gameBoard[i + 1][j];
pointBoardT0[2][2] = gameBoard[i + 1][j + 1];
int check = 0;
for (boolean state[] : pointBoardT0) {
for (boolean b : state) {
if (b)
check++;
}
}
if (check != 0) {
Future< point > res = executor.submit(new ComputeTask(
set, gameBoard[i][j], pointBoardT0, i, j,
stopFlag));
pointT1.add(res);
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
We go down deep! At this point, the program creates an asynchronous task for each alive cell. This means that the concurrency is maximized.
@Override
public Point call() {
Point pointT1 = null;
try {
pointT1 = result.computePoint(pointT0, pointBoard, i, j);
if (stopFlag.isSet()) {
} else {
}
} catch (Exception ex) {
ex.printStackTrace();
}
return pointT1;
}
Finally, computePoint calculates if the cell is alive or dead, implementing the rules of Game Of Life.
public Point computePoint(boolean pointT0, boolean[][] pointBoard, int i, int j) {
int surrounding = 0;
if (pointBoard[0][0]) surrounding++;
if (pointBoard[0][1]) surrounding++;
if (pointBoard[0][2]) surrounding++;
if (pointBoard[1][0]) surrounding++;
if (pointBoard[1][2]) surrounding++;
if (pointBoard[2][0]) surrounding++;
if (pointBoard[2][1]) surrounding++;
if (pointBoard[2][2]) surrounding++;
if (pointT0) {
if ((surrounding == 2) || (surrounding == 3))
return new Point(i - 1, j - 1);
} else {
if (surrounding == 3)
return new Point(i - 1, j - 1);
}
return null;
}
Shutdown
Once the tasks are parallelized, and the concurrency is maximized, how should shutdown the algorithm?
We’ve seen how to create an Executor but not how to shut one down. Because an Executor processes tasks asynchronously, at any given time the state of previously submitted tasks is not immediately obvious.
Some may have completed, some may be currently running, and others may be queued awaiting execution.
In order to shutdown an application, there is a spectrum from:
- graceful shutdown:
- finish what you’ve started but don’t accept any new work
- abrupt shutdown
- turn off the power to the machine room and various points in between.
For this application, I have used:
- monitor
Flag: check with the user that the button start/stop presents in the View - graceful shutdown: initiates an orderly shutdown in which previously submitted tasks are executed, no new tasks will be accepted.
public class Flag {
private boolean isSet;
public Flag(){
isSet = false;
}
public synchronized void set(){
isSet = true;
}
public synchronized boolean isSet(){
return isSet;
}
public synchronized void reset(){
isSet = false;
}
}
Curiosity
The British mathematician John Conway, who is currently at Princeton University, invented the Game of Life in the late 1960s. He chose rules that produced the most unpredictable behaviour.
If you are curious to find out more about the Game of Life, the historical context, there's a recent interview of John Conway about the origins of the Game of Life.
Conclusion
Structuring applications around the Execution of tasks can simplify development and facilitate concurrency. The Executor framework permits you to decouple task submission from execution policy and supports a variety of execution policies.
To maximize the benefit of decomposing an application into tasks, you must identify sensible task boundaries, which you can do through the phases of analyzing the problem.
In some applications, the obvious task boundaries work well, whereas in others some analysis may be required to discover finer-grained exploitable parallelism, maybe like this case study.
Bibliography
- http://www.theguardian.com/science/alexs-adventures-in-numberland/2014/dec/15/the-game-of-life-a-beginners-guide
- https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
- Java Concurrency in Practice - Goetz et al., Addison Wesley, 2006
