Difference between revisions of "CSC352 Game of Life Lab 2017"

From dftwiki3
Jump to: navigation, search
(→‎Game of Life)
 
(21 intermediate revisions by the same user not shown)
Line 4: Line 4:
 
<br />
 
<br />
 
<bluebox>
 
<bluebox>
−
In this lab you will write a multithreaded version of Conway's Game of Life.   
+
In this lab you will write a multithreaded version of Conway's Game of Life, in Java.   
 
</bluebox>
 
</bluebox>
 
<br />
 
<br />
 +
For the C version of this program, go to this [[Game of Life in C| page]].
 +
 
=Serial Game of Life=
 
=Serial Game of Life=
 
<br />
 
<br />
Line 50: Line 52:
  
  
−
*/
+
*/
 +
 
 +
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; }
 +
*/
 +
}
  
−
public class GameOfLife{
+
                // display the last generation
−
    public static void main(String[] args){
+
print(dish);
−
String[] dish2 = {
 
−
    "    ",
 
−
    "  #  ",
 
−
    "  #  ",
 
−
    "  #  ",
 
−
    "    "
 
−
};
 
−
String[] dish= {
 
−
    "                                                                                  ",
 
−
    "  #                                                                              ",
 
−
    " # #                                            ###                              ",
 
−
    "  ##                                                                              ",
 
−
    "                                                                                  ",
 
−
    "                                                      #                          ",
 
−
    "                                                    # #                          ",
 
−
    "                                                    ##                          ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "            #                                                                    ",
 
−
    "          # #                                                                    ",
 
−
    "            ##                                                                    ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  ",
 
−
    "                                                                                  "
 
−
};
 
−
int gens= 30000;
 
−
for (int i= 0;i < gens;i++) {
 
−
    //System.out.println("Generation " + i + ":\n\n\n");
 
−
    print(dish);
 
−
    dish= life(dish);
 
−
   
 
−
    clearScreen();
 
−
    // 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;
 
−
    }
 
 
}
 
}
−
    }
 
  
−
    public static void clearScreen(){
+
public static String[] life(String[] dish) {
−
        /*
+
/*
−
        brings the cursor home (top-left), so that the
+
* Given an array of string representing the current population of cells
−
        next generation will be printed over the current one.
+
* in a petri dish, computes the new generation of cells according to
−
        */
+
* the rules of the game. A new array of strings is returned.
−
final String ANSI_CLS    = "\u001b[2J";
+
*/
−
        final String ANSI_HOME = "\u001b[H";
+
 
−
        System.out.print( ANSI_HOME);
+
String[] newGen = new String[dish.length];
−
        System.out.flush();
+
 
−
    }
+
for (int row = 0; row < dish.length; row++) {// each row
−
   
+
 
−
    public static String[] life(String[] dish){
+
newGen[row] = "";
−
        /*
 
−
        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 i = 0; i < dish[row].length(); i++) {// each char in the
 +
// row
  
−
for ( int row= 0; row < dish.length; row++ ) {//each row
+
int neighbors = 0;
 +
char current = dish[row].charAt(i);
  
−
    newGen[row]= "";
+
// 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++) {
  
−
    for ( int i= 0; i < dish[row].length(); i++ ) {//each char in the row
+
// 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;
  
−
int neighbors = 0;
+
for (int j = i - 1; j <= i + 1; j++) {
−
char current = dish[row].charAt(i);
 
  
−
// loop in a block that is 3x3 around the current cell
+
// make sure we wrap around from left to right
−
// and count the number of '#' cells. 
+
int realj = j;
−
for ( int r=row-1; r<=row+1; r++ )  {
+
if (j == -1)
 +
realj = dish[row].length() - 1;
 +
if (j == dish[row].length())
 +
realj = 0;
  
−
    // make sure we wrap around from bottom to top
+
if (r == row && j == i)
−
    int realr = r;
+
continue; // current cell is not its
−
    if ( r==-1 )         realr = dish.length-1;
+
// neighbor
−
    if ( r==dish.length) realr = 0;
+
if (dish[realr].charAt(realj) == '#')
 +
neighbors++;
 +
}
 +
}
  
−
    for ( int j=i-1; j<=i+1; j++ ) {
+
if (current == '#')
−
+
if (neighbors < 2 || neighbors > 3)
−
// make sure we wrap around from left to right
+
newGen[row] += " ";
−
int realj = j;
+
else
−
if ( j==-1 )                 realj = dish[row].length()-1;
+
newGen[row] += "#";
−
if ( j==dish[row].length() ) realj = 0;
 
  
−
if (r==row && j==i ) continue; // current cell is not its
+
if (current == ' ')
−
                              // neighbor
+
if (neighbors == 3)
−
if (dish[realr].charAt(realj) == '#' )
+
newGen[row] += "#";
−
    neighbors++;
+
else
−
    }
+
newGen[row] += " ";
 +
}
 
}
 
}
 +
return newGen;
 +
}
  
−
if ( current=='#' )  
+
public static void clearScreen() {
−
    if (neighbors < 2 || neighbors > 3)  
+
/*
−
newGen[row] +=  " ";  
+
* brings the cursor home (top-left), so that the next generation will
−
    else
+
* be printed over the current one.
−
newGen[row] += "#";
+
*/
 +
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);
  
−
if ( current==' ' )
 
−
    if ( neighbors == 3 )
 
−
newGen[row] += "#";
 
−
    else
 
−
newGen[row] += " ";
 
−
    }
 
 
}
 
}
−
return newGen;
 
−
    }
 
−
       
 
−
    public static void print( String[] dish ) {
 
−
        /*
 
−
        just display all the lines of the array of strings.
 
−
        */
 
−
for ( String s: dish )
 
−
    System.out.println(s);
 
−
 
−
    }
 
 
}
 
}
  
Line 218: Line 250:
 
[[Image:QuestionMark3.jpg|right|120px]]
 
[[Image:QuestionMark3.jpg|right|120px]]
 
<br />
 
<br />
−
Think of what would constitute the contents of the run() method.
+
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 />
Line 228: Line 262:
 
|-
 
|-
 
|
 
|
−
==Question #2:==
+
 
 +
==Question #3:==
 
|}
 
|}
 
[[Image:QuestionMark2.jpg|right|120px]]
 
[[Image:QuestionMark2.jpg|right|120px]]
−
<br /> How should you split the data for the least amount of extra coding.
+
<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 />
 
<br />
 
<br />
−
<br /><br /><br />
 
  
 
=Part 2: Coding=
 
=Part 2: Coding=
 
<br />
 
<br />
−
Go for it!
+
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 />
 
<br />
−
<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><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]]
 
[[Category:CSC352]][[Category:Java]][[Category:Threads]]

Latest revision as of 23:24, 8 March 2017

--D. Thiebaut (talk) 17:02, 8 February 2017 (EST)

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:

QuestionMark1.jpg


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:

QuestionMark3.jpg


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:

QuestionMark2.jpg


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:

QuestionMark4.jpg


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)")



RGraphExample.png









Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC352_Game_of_Life_Lab_2017&oldid=30042"