Sample Project3: AppendixB

Appendix B: What does the given code do?

The code models various Life-like cellular automata specified by the input file. It takes as command line arguments of number of threads to use, the number of generations to model, as well as an input file and an output file.

Rules for cell state changes are stated in the first two lines of the input file. The first line specifies S(urvival) conditions and the second line specifies B(irth) conditions. Each line first specifies, the number of elements in the S list, followed by that many elements of the S list. The second line provides B rules in the same format.

The third line of the input file specifies the size of the universe (game board) as two numbers, first the x-size then the y-size, followed by the number of cells that are ON in the initial generation. The rest of the file simply lists the coordinates of cells that are ON in the initial generation, one per line.

The main() function in main.c parses the input file and calls the dogame() function (in game.c). The prototype (which parameters it takes and their types) of the dogame() function is specified in game.h (and you should not change it). The dogame() function is expected to perform the steps of the game until it either completes the specified number of generations or until all cells are OFF. If the game ended by all cells dying, the value returned from dogame() is the number of the generation in which all cells were OFF. If the game ended by completing the requested number of generations, the return value from dogame() is 0 (note that generation 0 is the initial generation, which is required to have at least one ON cell so the game cannot end in the initial generation).

In addition to the parameters of the game read from the input file, the main() function passes pointers to several additional vectors to dogame(), and dogame() is expected to fill these vectors out with per-row and per-column statistics as follows:

  • x_died should contain, for each column, how many times there was a cell in that column that died (went from ON to OFF). In other words, element x_died[i] of this array should be the number of all ON-to-OFF transitions that happened during the entire game for cells that have i as their x-coordinate.
  • y_died is similar to x_died, but each element y_died[i] in that vector contains the number of ON-to-OFF transitions that occurred in the i-th row.
  • x_born is similar to x_died, but it counts OFF-to-ON transitions instead of ON-to-OFF
  • y_born is similar to y_died, but it counts OFF-to-ON transitions instead of ON-to-OFF

After dogame() returns, the main() function uses the four statistics vectors to compute the average and standard deviation of their elements, and writes those aggregate statistics to the output file. If the game ended by all cells dying, the first line of the output file is a message indicating the generation in which all cells were OFF.

Here is a sample input file (Conway’s game of life S23/B3, 5 initial cells):

Screen Shot 2014-03-26 at 8.49.51 AM.png

Here is how this game progresses (showing only part of the game board):

Screen Shot 2014-03-26 at 8.50.28 AM.png

Because all cells are dead in the fourth generation, if four or more generations are requested the game will end when the fourth generation is computed, and the output file will be:

Screen Shot 2014-03-26 at 8.50.41 AM.png

Before we briefly describe what the dogame() function does, first note that you can change its code as long as it still has the same prototype (takes the same parameters) and provides the same results. Therefore, the following is a description of how the given code works, not how your code should work:

In dogame(), we first copy parameters into shared variables that will be read by all threads. We then create two arrays that will be used to keep the “previous” and the “current” generation, initialize a barrier synchronization variable that will be used to synchronize threads, and create new threads. Some of these read-only parameters are pointers to arrays, and these themselves arrays may not be read-only, so be careful if you are changing how these parameters and shared arrays are passed to threads. Note that a call to the pthread_create() supplies the name of the function the thread will start in, and this function can only take a single pointer parameter. We “cheat” a bit here and use type casting to pass to each thread its number (main thread is thread 0, additional threads are numbered 1, 2, etc.).

As indicated in the comments in the code, we already have one thread (the main thread), so for a given value of nthreads we can only create nthreads-1 new threads. Once we have created the additional threads (and they are already in the runThread() function), we make the main thread call the same function so we can have all of our threads doing the work). The runThread() function is supposed to really do everything – dogame() is there mainly to set things up, create threads, clean up, and return to main(). Each thread that “returns” from runThread is destroyed (runThread() is to a created thread what main() is to the main thread), except for the main thread which simply returns. After the main thread returns from runThread(), it waits for each of the other threads to terminate, checks if the game ended by all cells dying (allDead is 1), returning allDeadGeneration if that is the case or 0 if the game ended by completing all requested generations. Note that allDead and allDeadGeneration are global shared variables that are initialized and updated by the parallel execution in runThread().

The real parallel execution occurs in runThread(). Each of the threads goes through its own execution of runThread(), but uses shared variables and synchronization to ensure that the overall parallel execution is correct. The shared variables are the two arrays (pointers to these two arrays are passed to each thread), the statistics vectors (x_died, x_born, y_died, y_born), the rules, the global (not local to a C function) variables that contain parameters passed from main() to dogame() and then from dogame() to each runThread(), the global allDead and allDeadGeneration variables, and of course the global synchronization variables.

The barrier variable is initialized before the threads are created, but the remaining synchronization variables are initialized in runThread() before they are used. This initialization is done by the main thread, and is followed by a barrier so all other threads wait for the main thread to complete this initialization. We also initialize the cell grid (first set all cells to OFF and then turn on the cells specified in the input file) and the statistics vectors (all their elements are initialized to zero) here.

Next, we process generations one by one. In each generation, we must determine if all cells are OFF. Since each thread computes its own set of cells, we use a shared variable that is initialized to 1 (i.e. we assume all cells will be dead). After a barrier synchronization (to ensure that the allDead variable is initialized before it can be updated by any thread), we compute cells and, if a cell is found to be ON and the allDead variable is still 1, we set allDead to 0. When the entire generation is computed, allDead will remain equal to 1 only if no cell is found to be ON.

The way we have assigned cells to threads is according to the sum of the cell’s x and y coordinates, e.g. in a two-threaded execution (with threads 0 and 1) the cell at (x=4,y=3) will be computed by thread 1 (3+4=7, 7 mod 2 = 1), cell at (x=5,y=3) is computed by thread 0 (5+3=8, 8 mod 2 = 0), etc. This ensures that computing of cells is split close to fairly among threads.

For each cell, we first look at each of its eight neighbors from the previous generation (prevArray) and count how many of those neighbors are ON. For a cell that was ON in the previous generation, we check if the rules allow the cell to stay ON (survive) or become OFF (die). For a cell that was OFF, we check if it is becomes ON (born) or stay OFF (dead). When the new state (ON or OFF) for a cell is computed, it is written to the currArray. We use locks to ensure mutual exclusion when a thread reads neighbor elements (which may have been updated by another thread in a previous generation, and may be read by other threads in the current generation) and updates its own elements of the array (which may be read by other threads in the next generation).

All threads process the same generation as described. Then they synchronize on a barrier to ensure that all updates to allDead are done, decide whether the game has ended (allDead is still 1), and move on to the next generation if the game continues. But before moving on to the next generation, each cell swaps it two array pointers to exchange the two generations – the array that was used for the “current” generation now becomes the “previous” generation, and the array that held the old “previous” generation will be used to store the new “current” generation.