CSC352 Game of Life in Java, N Threads
--D. Thiebaut (talk) 23:18, 25 March 2017 (EDT)
Execution Times
Source
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
/*
Game of life
D. Thiebaut
Heavily adapted from code found in java section at this
URL: https://rosettacode.org/wiki/Conway%27s_Game_of_Life#Java
This code works in console mode, displaying successive generations
of the game of life on the screen, and clearing the screen between
each one.
The initial pattern is defined in the array dish (as in petri dish).
To compile and run:
javac GameOfLife.java
java GameOfLife
On MacBook Pro Laptop, for a dish of 2048 lines of 80 chars:
N Elapsed time
-------------------
2 22.827331 sec
4 17.957002 sec
8 17.381802 sec
16 18.270803 sec
20 17.070311 sec
32 17.137246 sec
64 17.647612 sec
128 11.504745 sec
256 19.692425 sec
512 20.288968 sec
1024 40.007107 sec
On 8-Core AMD Athlon
2 60.485946303 sec
4 51.65474993 sec
8 42.047212035 sec
16 44.17635592 sec
32 45.441912974 sec
64 46.638623376 sec
128 47.330744925 sec
256 49.344784618 sec
512 54.747102675 sec
1024 63.997888804 sec
*/
/*
_ _ _ _
__| | __ _| |_ __ _| \ | |
/ _` |/ _` | __/ _` | \| |
| (_| | (_| | || (_| | |\ |
\__,_|\__,_|\__\__,_|_| \_|
*/
class dataN {
static String[] newGen;
static String[] dish = {
" ",
" # ",
" # # ### ",
" ## ",
" ",
" # ",
" # # ",
" ## ",
" ",
" " };
static String[] dish2 = {
" ",
" # ",
" # # ### ",
" ## ",
" ",
" # ",
" # # ",
" ## ",
" ",
" ",
" ",
" ",
" # ",
" # # ",
" ## ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" ",
" " };
static void init() {
String fileName = "/Users/thiebaut/Desktop/Dropbox/352Workplace/Multithreading/src/life2048.dat";
Scanner sc = null;
try {
sc = new Scanner(new File(fileName));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
List<String> lines = new ArrayList<String>();
while (sc.hasNextLine())
lines.add(sc.nextLine());
dish = lines.toArray(new String[0]);
newGen = new String[ dish.length ];
for ( int i=0; i<dish.length; i++ )
newGen[i] = new String();
}
static void init2() {
dish = dish2;
newGen = new String[ dish.length ];
for ( int i=0; i<dish.length; i++ )
newGen[i] = new String();
}
}
/*
__ __ _____ _ _ _ _
| \/ |_ |_ _| |__ _ __ ___ __ _ __| | \ | |
| |\/| | | | || | | '_ \| '__/ _ \/ _` |/ _` | \| |
| | | | |_| || | | | | | | | __/ (_| | (_| | |\ |
|_| |_|\__, ||_| |_| |_|_| \___|\__,_|\__,_|_| \_|
|___/
*
* This is the thread class that will work on 1/2 of the dish array. If Id == 0,
* then work on low rows, if Id == 1, then work on high rows.
*/
class MyThreadN extends Thread {
int Id; // the Id of the thread, 0, 1, 2, ...N-1.
int N; // the number of threads
int gens = 3000;
BlockingQueue<Integer> toManager;
BlockingQueue<Integer> fromManager;
MyThreadN( int Id, int N, int gens,
BlockingQueue<Integer> fromManager,
BlockingQueue<Integer> toManager ) {
this.Id = Id;
this.N = N;
this.gens = gens;
this.toManager = toManager;
this.fromManager = fromManager;
}
/*
* This will apply life repeatedly to the half of the dish array that
* belongs to this thread.
*
* @see java.lang.Thread#run()
*/
public void run() {
int noRows = dataN.dish.length; // number of rows in dish
int startRow = Id * noRows / N; // where thread starts computing life
int endRow = ((Id+1) * noRows / N) ; // where thread stop computing life
if ( Id == N-1 ) endRow = noRows; // if last thread, make sure include last
int command = 1;
while ( command != 0 ) {
life( startRow, endRow );
//System.out.println( " Thread " + Id + " done with life..." );
// send a token, wait for token
try {
toManager.put( Id );
//System.out.println( " Thread " + Id + " sent Id... " );
//System.out.println( " Thread " + Id + " waiting for Manager... " );
command = fromManager.take();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
private void copyDish(String[] newGen, int startRow, int endRow) {
// copy newGen into dish
for (int row = startRow; row < endRow; row++) {
dataN.dish[row] = newGen[row];
}
}
private void life(int startRow, int endRow) {
/*
* Given an array of string representing the current population of cells
* in a petri dish, computes the new generation of cells according to
* the rules of the game. A new array of strings is returned.
*/
//newGen = new String[dataN.dish.length];
for (int row = startRow; row < endRow; row++) {// each row
dataN.newGen[row] = "";
for (int i = 0; i < dataN.dish[row].length(); i++) {// each char in the row
int neighbors = 0;
char current = dataN.dish[row].charAt(i);
// loop in a block that is 3x3 around the current cell
// and count the number of '#' cells.
for (int r = row - 1; r <= row + 1; r++) {
// make sure we wrap around from bottom to top
int realr = r;
if (r == -1)
realr = dataN.dish.length - 1;
if (r == dataN.dish.length)
realr = 0;
for (int j = i - 1; j <= i + 1; j++) {
// make sure we wrap around from left to right
int realj = j;
if (j == -1)
realj = dataN.dish[row].length() - 1;
if (j == dataN.dish[row].length())
realj = 0;
if (r == row && j == i)
continue; // current cell is not its
// neighbor
if (dataN.dish[realr].charAt(realj) == '#')
neighbors++;
}
}
if (current == '#')
if (neighbors < 2 || neighbors > 3)
dataN.newGen[row] += " ";
else
dataN.newGen[row] += "#";
else if (current == ' ')
if (neighbors == 3)
dataN.newGen[row] += "#";
else
dataN.newGen[row] += " ";
else
System.out.println( "Thread " + this.Id + " found char " + current + " at Index " + i );
}
}
}
}
/*
____ ___ __ _ _ __
/ ___| __ _ _ __ ___ ___ / _ \ / _| | (_)/ _| ___
| | _ / _` | '_ ` _ \ / _ \ | | | |_| | | | |_ / _ \
| |_| | (_| | | | | | | __/ |_| | _| |___| | _| __/
\____|\__,_|_| |_| |_|\___|\___/|_| |_____|_|_| \___|
*/
public class GameOfLifeNThreads {
// static variables are global to all objects instanciated from the class.
public static void main(String[] args) {
int N = 2; // # of threads
int gens = 3000; // # of generations
boolean verbose = false;
//--- get N from command line ---
if (args.length > 0) {
try {
N = Integer.parseInt( args[0] );
} catch (NumberFormatException e) {
System.err.println("Argument" + args[0] + " must be an integer.");
System.exit(1);
}
}
//--- check if verbose mode is on ---
for ( int i=0; i<args.length; i++ )
if ( args[0].equalsIgnoreCase( "-v" ) )
verbose = true;
if (verbose) System.out.println( "N = " + N );
if (verbose) System.out.println( "gens = " + gens );
// init the dish
dataN.init();
// display original generation
if (verbose) System.out.println( "dish initialized with " + dataN.dish.length + " rows." );
if (verbose) print(dataN.dish);
// get ready to measure elapsed time
long startTime = System.nanoTime();
// create array of queues from Manager to N
BlockingQueue<Integer>[] QToThreads = new ArrayBlockingQueue[N];
for (int i=0; i<QToThreads.length; i++ )
QToThreads[i] = new ArrayBlockingQueue<Integer>( 2 );
// create queue from N threads to manager
BlockingQueue<Integer> QFromThreads = new ArrayBlockingQueue<Integer>(2*N);
//System.out.println( "Queues created" );
// create N workers
MyThreadN[] threads = new MyThreadN[N];
// compute amount of lines per thread
int noLinesPerThread = dataN.dish.length/N;
// create and start N threads
for ( int i=0; i< N; i++ ) {
threads[i] = new MyThreadN( i, N, gens,
QToThreads[i],
QFromThreads );
threads[i].start();
if ( verbose ) System.out.println( "Thread #" + i + " started..." );
}
// go through generations
for ( int i = 0; i < gens; i++ ) {
if ( verbose ) System.out.println( "generation " + i );
// wait for N threads to finish their computation of
// life
for ( int t=0; t<N; t++ ) {
try {
if ( verbose ) System.out.println( " Waiting for a thread to send message..." );
int c = QFromThreads.take();
if ( verbose ) System.out.println( " Received \"Done\" message from Thread " + c );
} catch (InterruptedException e) {
}
}
if ( verbose ) System.out.println( " Heard from all threads..." );
// copy newGen to dish
for ( int row=0; row < dataN.dish.length; row++ )
dataN.dish[row] = dataN.newGen[row];
if ( verbose ) System.out.println( " dish copied" );
//print( dataN.dish );
// tell N threads to resume computation
for ( int t=0; t<N; t++ ) {
int command = 1;
if (i==gens-1)
command = 0;
try {
QToThreads[t].put( command );
} catch (InterruptedException e) {
}
}
if ( verbose ) System.out.println( " all threads alerted to continue..." );
}
// wait for all threads to be done
try {
for ( int i=0; i < N; i++ )
threads[i].join();
} catch (InterruptedException ie) {
}
// display final generation
long estimatedTime = System.nanoTime() - startTime;
if ( verbose ) print(dataN.dish);
System.out.println( N + " " + estimatedTime / 1E09 + " sec" );
}
public static void clearScreen() {
/*
* brings the cursor home (top-left), so that the next generation will
* be printed over the current one.
*/
final String ANSI_CLS = "\u001b[2J";
final String ANSI_HOME = "\u001b[H";
System.out.print(ANSI_HOME);
System.out.flush();
}
public static void print(String[] dish) {
/*
* just display all the lines of the array of strings.
*/
clearScreen();
System.out.println(new String(new char[dish[0].length()]).replace('\0',
'-'));
for (String s : dish)
System.out.println("|" + s + "|" );
}
}
