CellularAutomata.java added a CyclicBarrier and worker threads to print the same result as GameOfLife.java no GUI version, with better performance from better concurrency.
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
public class CellularAutomata {
/**
* Monitor of the data model for mainBoard and its subBoards
* */
private final Board mainBoard;
/**
* The boardGrid is partitioned into Ncpu parts, and assign each part to a thread.
* At each step, the worker threads calculate new values for all the cells in their part of the board with
* a reference to the global board.
* When all worker threads have reached the barrier, one of the thread run the barrier action to combines/commits
* the subBoards' new values to the boardGrid.
* After the barrier action runs, the worker threads are released to compute the next step of the calculation.
* */
private final CyclicBarrier barrier;
private final Worker[] workers;
public static final int TOTALGENERATIONS = 25;
/**
* boardGrid is shared among worker threads, however only the one running the barrier action should update the
* value of boardGrid.
* The worker threads should always treat this array as read only unless it is running the barrier action.
*
* Java memory models consider each array element as a separate variable.
*
* JVM memoery model guarantee initialization safety with static or final keyword.
*
* Happens-before relationship is established by the barrier.await() -- when a thread is running the barrier action,
* all data model before barrier.await() is happens-before to that thread;
* when the thread finish running the barrier action, the data model modified is happens-before for next threads calling
* barrier.await().
*
* We don't need update atomicity, only one thread is update boardGrid in barrier action, while the
* updating is happening, the worker threads are not reading it.
* **/
static final int[][] boardGrid = new int[10][10]; //default 0
public static void main(String...args) {
//initialBoard[0][1] = initialBoard[0][2] = initialBoard[0][3] = initialBoard[0][4] = 1; //seeds
boardGrid[0][0] = boardGrid[0][1] = boardGrid[0][2] = boardGrid[0][3] = boardGrid[0][4] = 1; //seeds
CellularAutomata cells = new CellularAutomata(boardGrid);
cells.start();
}
public CellularAutomata(int[][] boardGrid) {
visualizeBoard(boardGrid);
this.mainBoard = new GameBoard(boardGrid);
int count = Runtime.getRuntime().availableProcessors();
System.out.println("total processor: " + count);
this.barrier = new CyclicBarrier(count,
new Runnable() {
public void run() {
mainBoard.commitNewValues();
}});
this.workers = new Worker[count];
for (int i = 0; i < count; i++)
workers[i] = new Worker(boardGrid, mainBoard.getSubBoard(count, i));
}
//suppose to be called by a single thread (main thread, or swing event dispatch thread later)
public final static void visualizeBoard(int[][] board) {
for (int row[] : board) {
for (int cell : row) {
System.out.print(cell == 1 ? "#" : ".");
}
System.out.println();
}
System.out.println();
}
private class Worker implements Runnable {
private final int[][] mainBoardView; //suppose to be used as an unmodifiable view of the latest mainBoard
private final Board board;
public Worker(int[][] mainBoardView, Board board) {
this.mainBoardView = mainBoardView;
this.board = board;
}
public void run() {
while (!board.hasConverged()) {
for (int x = 0; x < board.getMaxX(); x++)
for (int y = 0; y < board.getMaxY(); y++)
board.setNewValue(x, y, computeValue(x, y));
System.out.println(Thread.currentThread().getName() + " finished one turn");
try {
barrier.await();
} catch (InterruptedException ex) {
return;
} catch (BrokenBarrierException ex) {
return;
}
}
}
private int computeValue(int x, int y) {
// Compute the new value that goes in (x,y)
return nextCellState(mainBoardView, x, y);
}
private final int nextCellState(int[][] board, int i, int j) {
int count = countSurrounding(board, i, j);
if (board[i][j] == 1 && (count == 2 || count == 3)) { // stay alive rule
return 1;
}
if (board[i][j] == 0 && count == 3) { // birth new rule
return 1;
}
return 0;
}
private final int countSurrounding(int[][] board, int a, int b) {
int count = 0;
int[][] surroundings = { { a - 1, b - 1 }, { a - 1, b },
{ a - 1, b + 1 }, { a, b - 1 }, { a, b + 1 }, { a + 1, b - 1 },
{ a + 1, b }, { a + 1, b + 1 } };
for (int surrounding[] : surroundings) {
try {
if (board[surrounding[0]][surrounding[1]] == 1) {
count++;
}
} catch (ArrayIndexOutOfBoundsException e) {
}
}
return count;
}
}
public void start() {
for (int i = 0; i < workers.length; i++)
new Thread(workers[i]).start();
mainBoard.waitForConvergence();
}
interface Board {
int getMaxX();
int getMaxY();
int getValue(int x, int y);
int setNewValue(int x, int y, int value);
void commitNewValues();
boolean hasConverged();
void waitForConvergence();
Board getSubBoard(int numPartitions, int index);
}
/** mainBoard stores the global data model and the data models of all the subBoards
* A subBoard only stores the data model of its own
*
* Of course, in elastic computation environment, a subBoard can further be spit into 2nd level subBoards and acts
* as 2nd level mainBoard.
* **/
final class GameBoard implements Board{
private final int[][] board;
/**
* the mainBoard have a non-empty map, which stores the data models of all the subBoards
* mainBoard retains a reference to the data model for each of the subBoards,
* so that they can be combined to update the mainBoard's data model when all threads reaches the barrier.
* The data model of the subBoard are not really accessed concurrently at any moment.
* Indexed subBoard is one per worker thread.
* After barrier.await() reaches, only one of the threads can read these data models in the barrier action.
* -- only after all worker threads have finished modifying their own data models and happens-before relationship
* established by barrier.await().
* **/
private final Map<Integer, int[][]> subBoards = new HashMap<>();
private volatile int nthGeneration = 0;
public GameBoard(int[][] mainboardView) {
this.board = mainboardView;
}
@Override
public int getMaxX() {
return this.board.length;
}
@Override
public int getMaxY() {
return this.board[0].length;
}
@Override
public int getValue(int x, int y) {
return this.board[x][y];
}
@Override
/**
* subBoard calls this method to update its own data model, the mainBoard's data model remain unchanged,
* however, mainBoard kept a reference to the subBoard's data model, so these update is visible to the mainBoard.
* */
public int setNewValue(int x, int y, int value) {
this.board[x][y] = value;
return this.board[x][y];
}
@Override
/**only mainBoard should call this method.
* The data models of the subBoards are combined to update the data model of the mainBoard*/
public void commitNewValues() {
for(int index : subBoards.keySet()) {
int rowsCopied = 0;
int[][] subBoard = subBoards.get(index);
for (int i = 0; i < subBoard.length; i++) {
for (int j = 0; j < subBoard[0].length; j++) {
board[rowsCopied + i][j] = subBoard[i][j];
}
}
rowsCopied += subBoard.length;
}
System.out.println("\nGeneration " + nthGeneration++);
CellularAutomata.visualizeBoard(board);
}
@Override
/**
* subBoard can not tell when the game converged without global knowledge of the mainBoard.
* So it assuming converge after TOTALGENERATIONS.
* */
public boolean hasConverged() {
if(nthGeneration++ <= CellularAutomata.TOTALGENERATIONS) {
return false;
}
return true;
}
@Override
/**
* only mainBoard should call this method.
* one way to tell convergence is to
* */
public void waitForConvergence() {
while(nthGeneration<=25) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("wait for convergence");
}
}
@Override
/**
* only mainBoard should call this method. It create a new array as the data model for the subBoard.
* mainBoard retains a reference to the data model of the subBoard.
* the data model of the subBoard are not suppose to be accessed concurrently.
* Indexed subBoard is one per worker thread.
* After barrier.await() reaches, only one of the threads can read these data models in the barrier action.
* -- only after all worker threads have finished modifying their own data models and happens-before relationship
* established by barrier.await().
* */
public Board getSubBoard(int numPartitions, int index) {
int count = board.length;
int rows = count / numPartitions;
int residue = count % numPartitions;
int[][] subBoard = null;
if(index == 0) {
subBoard = new int[rows + residue][board[0].length];
} else {
subBoard = new int[rows][board[0].length];
}
this.subBoards.put(index, subBoard);
return new GameBoard(subBoard);
}
}
}
