Before 17 Feburary 2019 at 9am, the skeleton code had the wrong version of life.h. You can download an updated version here or modify to declare simulate_life_parallel (instead of two versions of simulate_life_parallel).

changelog:

Your Task

  1. Examine our supplied skeleton code (last updated 17 Feb 2019) which implements Conway’s Game of Life. See below for a summary of our skeleton code does and how to use it. (Note that there is life directory on some old versions the VM which you should delete and ignore; make sure you don’t confuse it with this skeleton code.)

  2. Create a parallel version that uses pthreads. We recommend using pthreads barriers to synchronize between the threads, but you may also do something else that does not involve busy-waiting if you prefer. You must reuse the existing LifeBoard class. Your implementation must have the prototype

    void simulate_life_parallel(int threads, LifeBoard &state, int steps)

    like the unimplemented version you should find life-parallel.cc (though you can implement it in other files, so long as you modify the Makefile accordingly). Your implementation can (and should!) span across multiple functions. You can look in life-serial.cc to see a reference, single-threaded implementation, which you are welcome to borrow from in producing your implementation.

    The function you need to implement take a number of threads that should do the computation. Your code should create the appropriate number of threads, then do as many iterations of the simulation as requested, then let the threads finish. You may not create new threads for each iteration of the simulation.

    It must be possible to call your implementation on different LifeBoards simulatenously from multiple threads and have the results on each of the LifeBoards computed in parallel. This means that, generally, your implementation should not use global varibales.

    One way you can test your version is by uncommenting the corresponding entries in the test_functions table in main.cc and running script time-examples.sh. When you are first developing, you may wish to simply run some of the ./life commands from time-examples.sh with a smaller iteration count.

    If you downloaded the life template before 17 Feb 2019, you may need a new version of life.h or to modify life.h to declare simulate_life_parallel as described above.

    When running on a machine with multiple cores (if your VM only has one virtual CPU, it doesn’t count), you should notice speedup when running your barrier implementation with more threads.

    We may test your code by substituting our own versions of main.cc, so please do not add anything to main.cc that would prevent this from working.

  3. Submit your code as a .tar.gz archive. You may find the supplied make submit target helpful for this. (If you created any new source files for your solution, please verify that they are included in this .tar.gz archive.)

On the skeleton code

Running the supplied code

  1. Conway’s Game of Life is a simulation over a grid of cells, each of which is “dead” or “alive”. The simulation is done in “generations”, with a simple rule (see the wikipedia article or our code) determining what state a cell is in in the next iteration, based on the state of the cells around it in the current iteration. Our supplied code has a working serial implementation, except that the grid is fixed size and cells at the edge of the grid are always dead to avoid simulating an arbitrarily large grid.

  2. If you download the skeleton code and run make this will produce a binary called ./life. If you run ./life you will receive a usage message.

  3. We also produce a binary called ./life-asan, which is compiled with AddressSanitizer to help you detect and debug memory errors. Since AddressSanitizer substantially slows down the prorgam, you should not trust performance results from this version of the program, but we strongly recommend testing with it.

  4. We have some example input files in the input directory. You can open these up in a text editor. The first line of these files consists of the size of the pattern grid and the following lines consist of its contents, where . or ` ` represents a “dead” cell and anything else represents a “live” cell.

    This input format is parsed by the operator<< and operator>> (for iostreams) in life.cc.

  5. When run in serial-result mode the ./life binary runs the serial implementation and produces the result, for example:

    ./life 0 input/make-a serial-result

    outputs input/make-a after 0 generations, which will be the same as the original input.

    ./life 1 input/make-a serial-result

    outputs input/make-a after 1 generations, and you can supply larger numbers to see later. For the make-a pattern, generations numbers around 120 are interesting.

The Serial Implementation

  1. The class LifeBoard, defined life.h, represents the grid of cells as a one-dimensional array. The at member function of this class can be used to access the cell at a given x and y coordinate. In this representation rows are stored together.

  2. life-serial.cc contains simulate_life_serial, our serial implementation, which looks in at 3x3 “window” around each cell to determine the next state. This update code works by making two life boards, one representing the next state, and one representing the current state. After each generation, these boards are swapped. The implementation of swapping for LifeBoard allows swapping to occur without actually copying the cell values (the pointers in the corresponding vectors are swapped), so this is efficient.

  3. simulate_life_serial takes a LifeBoard reference and modifies the referred-to LifeBoard to return its result.

  4. The swap function for LifeBoard is specialized to avoid copying all the cells of the board — instead pointers internal to the vector inside the LifeBoard will be swapped.

Running and Timing Parallel Implementations

  1. ./life does not run your parallel code until you change main.cc and run something like ./life input/SOME-FILENAME time (not serial-result).

  2. main.cc has an array of functions test_functions that you should change to include the parallel implementation you are implementing. We have supplied commented-out definitions you can use.

  3. After changing the array of test_functions in main.cc,

    ./life 10 input/make-a time

    will time all the versions of the life simulation listed in test_functions and verify that they have the correct result. When running an implementation, first each version is run once and the result is checked for correctness. The implementation is not timed if this produces an error. Then, timing runs each implementation many times in attempt to obtain a result that does not have “noise” from the machine. Each result is checked for correctness versus the reference implementation.

    To avoid errors where you neglect to edit test_functions or where your parallel implementation terminates the program/thread, make sure you check for a line of output with the timing of your parallel version.

  4. If you run with time-and-result instead of time, the main function will print out the final results of your parallel versions whenever they fail to match the serial implemnetation.

  5. The list of test functions in main.cc expects each test function to have the prototype

    void single_threaded_function(LifeBoard &board, int num_iterations)

    but your multithreaded versions will have the prototype

    void multithreaded_function(int num_threads, LifeBoard &board, int num_iterations)

    to accomodate this the commented out code uses the C++ standard library’s std::bind to create wrapper functions for multithreaded_function for various numbers of threads. For example:

    function = std::bind(&foo, 42, _1, _2);
function(a, b);

    is equivalent to doing

    foo(42, a, b);

Scripts to Assist Testing

  1. time-examples.sh runs several ./life timing commands which may be useful for testing.

  2. convert_from_rle.py is a program converts from the popular “RLE” format for life patterns you may be able to find online into the input format our code expects.

Hints

Pthreads documentation

  1. The official POSIX documentation is available at http://pubs.opengroup.org/onlinepubs/9699919799/.

    You can make this official documentation available through commands like man pthread_cond_wait on your VM (or any sufficiently Ubuntu-like system) by running sudo apt install manpages-posix-dev.

  2. This tutorial from LLNL is one, perhaps friendlier source of information (though it does not cover barriers, see the next section for that.)

  3. Another reference source is Chapter 27 of Operating Systems: Three Easy Pieces along surrounding chapters

Understanding POSIX’s barriers

  1. POSIX barriers have the following API:

    • int pthread_barrier_init(pthread_barrier_t *barrier, const pthread_barrierattr_t *attr, unsigned count).

      Initialize the barrier. count is the number of threads that will use the barrier. attr are “attributes” to configure how the barrier works. For this assignment, you can pass “NULL” for attr.

    • int pthread_barrier_destroy(pthread_barrier_t *barrier)

      Deallocate any resources allocated for a barrier.

    • int pthread_barrier_wait(pthread_barrier_t *barrier)

      Wait for exactly count (set by init) threads to call wait() before returning. After count threads have called wait, wait will returns for all threads and the state of the barrier is reset. These threads can then immediately use the barrier again to wait for all threads to reach a certain place.

    • All these functions return an int that can, among other things, be used to know if an error occurred.

Parallelizing Life

  1. You should choose some way to split up the grid between threads. You will get best performance if each thread works on a part of the grid that is contiguous in memory, so you get better locality within a thread. This also will avoid performance problems associated with two processors trying to modify data in different parts of the same cache block.

  2. To compute the value of a cell in generation i, one needs the value of its neighbors in generation i-1. Barriers are one way to make sure that the values from generation i-1 are available before any thread starts computing generation i.

  3. The supplied code calls swap() to exchange boards. If one uses that code as is, one must ensure that all threads stop accessing the boards before the swap happens and don’t start accessing the boards again until the swap finishes.

    An alternative, which calls wait on barriers fewer times each iteration, is to avoid swapping by having an “even” state and “odd” state and choose which board to write to based on the generation number. (In even iterations, threads would use the “odd” version of the state to write to the “even” state; and in odd iterations, threads would use the “even” version of the state to write to the “odd” state.) In this way, rather than waiting for the swap to finish before starting the next generation, threads just need to wait for all other threads to have finished the current generation.

  4. You should be able to reuse almost all of the simulate_life_serial code. You will probably need to split it into at least two functions — one that represents the work done in seperate threads and one that spawns the threads and waits for them to finish.

On testing in a way where you can see speedup

  1. If you are using a VM and the VM settings only provide one CPU, multiple threads won’t provide speedup. You can adjust your VM settings to have multiple CPUs (assuming you are running on a multicore machine), which will probably require rebooting.

    Alternately, if you are section 001, you should have a department account, which you can use via the instructions here which should access a shared Linux machine with multiple cores. You will need to use module load gcc before trying to compile or run your program on these machines.

    Alternately, you can run “natively” outside a VM on your machine, assuming you have a machine with pthreads. (OS X has this natively, on Windows, the Windows Subsystem for Linux probably gives access to it.)