View source for CSC352 Game of Life Lab 2017

--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 17:02, 8 February 2017 (EST)
----
=Game of Life=
<br />
<bluebox>
In this lab you will write a multithreaded version of Conway's Game of Life.  
</bluebox>
<br />
=Serial Game of Life=
<br />
[https://en.wikipedia.org/wiki/Conway's_Game_of_Life Wikipedia] has a good page on Conway's game of life.  Please read the first section containing the rules.
<br />
The program below is a serial version of the game of life taken from [https://rosettacode.org/wiki/Conway%27s_Game_of_Life 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.
<br />
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.

<br />
::<source lang="java">
/*  
 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);

	}
}

</source>
<br />

=Exploring the Serial Version=
<br />
* 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.
<br />

=Part 1:  Class discussion=
<br />
{| style="width:100%; background:limegreen"
|-
|
==Question #1:==
|}
[[Image:QuestionMark1.jpg|right|120px]]
<br />
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.
<br />
<br />
<br />
<br />
{| style="width:100%; background:limegreen"
|-
|
==Question #2:==
|}
[[Image:QuestionMark3.jpg|right|120px]]
<br />
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?

<br />
<br />
<br />
<br />

{| style="width:100%; background:limegreen"
|-
|

==Question #3:==
|}
[[Image:QuestionMark2.jpg|right|120px]]
<br /> 
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? 
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
{| style="width:100%; background:limegreen"
|-
|

==Question #4:==
|}
[[Image:QuestionMark4.jpg|right|120px]]
<br />
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.
<br />
<!-- See blocking queue example here: http://tutorials.jenkov.com/java-util-concurrent/blockingqueue.html
-->
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />

=Part 2: Coding=
<br />
Go for it and code a multithreaded version of the Game of Life!
<br />
* 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.
<br />

=Part 2: Measuring Performance=
<br />
==Example Java Program==
<br />
::<source lang="java">
class PrintN {
 
    public static void main( String[] args ) {
 
	int N = Integer.parseInt( args[0] );
	System.out.println( "I got " + N );
    }
 
}

</source>
<br />

==Bash Script==
<br />
::<source lang="bash">
#! /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
</source>
<br />
Don't forget to make the script executable:
 
 chmod +x runPrintN.sh
 
<br />
==Capture the Timing to a Data File==
<br />
 ./runPrintN.sh  2>&1 | grep "got\|real" > timing.data
<br />
==Python Filter==
<br />
::<source lang="python">
#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 )


</source>
<br />
==R Script to Display Graph==
<br />
::<source lang="text">
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)")
</source>
<br />
<br />
[[Image:RGraphExample.png|600px|center]]
<br /><br /><br /><br /><br /><br /><br /><br />

[[Category:CSC352]][[Category:Java]][[Category:Threads]]