CSC352 Game of Life Lab 2017
--D. Thiebaut (talk) 17:02, 8 February 2017 (EST)
Contents
Game of Life
In this lab you will write a multithreaded version of Conway's Game of Life, in Java.
For the C version of this program, go to this page.
Serial Game of Life
Wikipedia has a good page on Conway's game of life. Please read the first section containing the rules.
The program below is a serial version of the game of life taken from RosettaCode.org.
It displays the generation of cells using simply ascii characters on the console. Get a copy of it with the following command:
getcopy GameOfLife.java
If that doesn't work, just copy/paste it in a file called GameOfLife.java in your 352b-xx account.
Compile and run it as follows:
javac GameOfLife.java java GameOfLife
and adjust the size of your terminal/console to make sure you can see the pattern evolving.
The game is coded so that the array wraps around horizontally, and vertically. So a pattern sliding on the array will reach the bottom and reappear at the top. Similarly, a pattern sliding off the left will reappear on the right.
The generations are stable for a few seconds, then one of the moving patterns (glider) hits the blinker, and the population of cells start growing until it freezes with just a few cells blinking.
/* 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 */ public class GameOfLife { static String[] dish3 = { " ", " # ", " # ", " # ", " " }; static String[] dish = { " ", " # ", " # # ### ", " ## ", " ", " # ", " # # ", " ## ", " ", " " }; static String[] dish2 = { " ", " # ", " # # ### ", " ## ", " ", " # ", " # # ", " ## ", " ", " ", " ", " ", " # ", " # # ", " ## ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " " }; public static void main(String[] args) { int gens = 3000; // # of generations print(dish); // # first generation, in petri dish // iterate over all generations for (int i = 0; i < gens; i++) { // apply the rules of life to the current population and // generate the next generation. dish = life(dish); // display the new generation print(dish); // add a bit of a delay to better see the visualization // remove this part to get full timing. /* * try { Thread.sleep(50); } catch(InterruptedException ex) { * return; } */ } // display the last generation print(dish); } public static String[] life(String[] dish) { /* * 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. */ String[] newGen = new String[dish.length]; for (int row = 0; row < dish.length; row++) {// each row newGen[row] = ""; for (int i = 0; i < dish[row].length(); i++) {// each char in the // row int neighbors = 0; char current = 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 = dish.length - 1; if (r == 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 = dish[row].length() - 1; if (j == dish[row].length()) realj = 0; if (r == row && j == i) continue; // current cell is not its // neighbor if (dish[realr].charAt(realj) == '#') neighbors++; } } if (current == '#') if (neighbors < 2 || neighbors > 3) newGen[row] += " "; else newGen[row] += "#"; if (current == ' ') if (neighbors == 3) newGen[row] += "#"; else newGen[row] += " "; } } return newGen; } 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); } }
Exploring the Serial Version
- Explore the code and make sure you get some reasonable understanding of it.
- Play with the Thread.sleep() delay to see how it influences the display.
- Create new patterns in the petri dish, and see how they evolve.
Part 1: Class discussion
Question #1: |
How could we make this program parallel, and make it work faster with 2 threads? Think of what would constitute the contents of the run() method, and how you would split the data for the least amount of coding.
Question #2: |
What data is going to be shared by the threads?
Assuming that the threads are going to be separate classes, declared outside the GameOfLife class, how can we make the data global?
Question #3: |
How should you split the data between the 2 threads? What is actually shared between the 2 threads? In other words, what part of the data "belonging" to Thread 0 is needed by Thread 1, and conversely?
Question #4: |
Playout your parallel sketch of an algorithm and see if there are some hidden complexity in the way the two threads should proceed so that the generations are computed correctly.
Part 2: Coding
Go for it and code a multithreaded version of the Game of Life!
- Recommendations:
- Do not make the threads display their arrays. They might interleave their System.out.println() outputs and it won't look good. We really should have a 3rd thread to display the different generations, but for now it's easier to have the main program display the final generation only.
- Code an application that just uses 2 threads, and do not worry about synchronizing them. Very likely the generations will not be correct, but, at least, you will have two threads running on computing the evolution of life in their two halves of the petri dish.
- When your code work and stops correctly, without errors, add the synchronization.
- Then, and only then, verify that your parallel program works correctly by comparing the last generation it creates to the last generation output by the serial version.
- Feel free to work in pairs.
Part 2: Measuring Performance
Example Java Program
class PrintN { public static void main( String[] args ) { int N = Integer.parseInt( args[0] ); System.out.println( "I got " + N ); } }
Bash Script
#! /bin/bash # runPrintN.sh # javac PrintN.java for i in 1 2 3 4 5 6 7 8 9 10 ; do for j in 1 2 3 ; do time java PrintN $i done done
Don't forget to make the script executable:
chmod +x runPrintN.sh
Capture the Timing to a Data File
./runPrintN.sh 2>&1 | grep "got\|real" > timing.data
Python Filter
#processTimingData.py # D. Thiebaut from __future__ import print_function file = open( "timing.data", "r" ) lines = file.readlines() file.close() times = [0]*11 # 0-10, hence 11 for line in lines: if len(line) < 2: continue if line.find( "got" ) != -1: n = int( line.split()[-1] ) else: time = line.replace( 'm', ' ' ).replace( 's', '' ).split()[-1] time = float( time ) times[n] += time for i in range( len( times ) ): if times[i] != 0: print( i, times[i]/3.0 )
R Script to Display Graph
noThreads <- c( 1, 2, 4, 8, 16, 20 ) execTimes <- c( 10, 8.5, 7.0, 6.0, 5.5, 7.3 ) jpeg( '/Users/thiebaut/Desktop/executionTimes.jpg' ) plot( noThreads, execTimes, type="b", col="blue", xlab="Number of Threads", ylab="Avg. Execution Time (s)") dev.off() plot( noThreads, execTimes, type="b", col="blue", xlab="Number of Threads", ylab="Avg. Execution Time (s)")
