CSC352 Game of Life in Java, N Threads
--D. Thiebaut (talk) 23:18, 25 March 2017 (EDT)
Execution Times
The execution times are measured on a MacBook Pro, Retina, mid 2014, 2.8 GHz, Intel Core i7, 4 cores. The data size is fixed for across all measurements: a dish of 2048 lines, each line with 80 characters. The number of threads varies between 2 and 1024. With 2 threads, each works on a size of the dish equal to 1024 lines. With 1024 threads, each works on just 2 lines of the dish.
# Times 2 23.457615 sec 4 19.296118 sec 8 18.217899 sec 16 10.362582 sec 32 10.626956 sec 64 17.699931 sec 128 21.393852 sec 256 13.251387 sec 512 22.777201 sec 1024 41.176413 sec
SpeedUp
For the serial program we use the C version from this page.
Its average execution time for 3000 generations on the dish of 2048 lines is 21 seconds.
Taken the numbers from the previous section, we get this raw speedup:
# Speedup 2 0.895231676 4 1.088301802 8 1.152712505 16 2.026521961 32 1.976106799 64 1.186445303 128 0.981590412 256 1.584739771 512 0.921974566 1024 0.510000713
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 a 2014 4-core 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 an 8-Core 3.7 GHz 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 { String fileName = ""; static String[] newGen; static String[] dish = { " ", " # ", " # # ### ", " ## ", " ", " # ", " # # ", " ## ", " ", " " }; static String[] dish2 = { " ", " # ", " # # ### ", " ## ", " ", " # ", " # # ", " ## ", " ", " ", " ", " ", " # ", " # # ", " ## ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " " }; /** * Initializes the dish by reading its contents from a * file provided. * @param fname: name of the text file containing the dish */ static void init( String fname ) { String fileName = fname; 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]); //--- initialize the newGen array with strings --- newGen = new String[ dish.length ]; for ( int i=0; i<dish.length; i++ ) newGen[i] = new String(); } /** * used for debugging purpose */ 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 ( realj > 79 ) // System.out.println( " Thread " + this.Id // + "realr = " + realr + " realj = " + realj // + " row-length = " + dataN.dish[realr].length() ); 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; String fileName = ""; //--- check syntax --- if (args.length < 0) { System.err.println( "Syntax java GameOfLifeNThreads N dishFileName [-v]" ); System.exit( 1 ); } //--- get N from command line --- try { N = Integer.parseInt( args[0] ); } catch (NumberFormatException e) { System.err.println("Argument" + args[0] + " must be an integer."); System.exit(1); } //--- get fileName from the command line --- fileName = args[1]; //--- check if verbose mode is on --- for ( int i=0; i<args.length; i++ ) if ( args[i].equalsIgnoreCase( "-v" ) ) verbose = true; if (verbose) System.out.println( "N = " + N ); if (verbose) System.out.println( "gens = " + gens ); // init the dish dataN.init( fileName ); // 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 + "|" ); } }
