CS31 Lab 9: pthreads Game of Life

Parallelize a shared-memory application using the pthreads library.

Protect threaded code with synchronization primitives.

Revisit 2D arrays and file I/O in C.

Gain more expertise with C pointers and dynamic memory allocation.

Design input files to test the correctness of your solution.

Practice debugging threaded programs.

Example column-wise and row-wise partitioning output for different numbers of threads is shown in Section 4.5.1. Please follow our output format for your printing partitioning functionality.

Example runs showing the time improvement from the parallelization is shown below. This output was generated on a lab machine with 12 cores, using a configuration file (big.txt) that specified a 4000x4000 board and 500 iterations. The program was run for different numbers of threads (1, 4, 8, 12, and 20). Notice the time improvement with increased parallelization up to the number of cores (from 298 seconds for 1 thread to 50 seconds for 12 threads). Beyond the total number of cores (12, in the case), adding more threads does not help to improve total runtime.

$ ./gol big.txt 0 1 0 0
Total time: 297.943 seconds
After 500 rounds on 4000x4000, number of live cells is 17

$ ./gol big.txt 0 4 0 0
Total time: 78.617 seconds
After 500 rounds on 4000x4000, number of live cells is 17

$ ./gol big.txt 0 8 0 0
Total time: 71.223 seconds
After 500 rounds on 4000x4000, number of live cells is 17

$ ./gol big.txt 0 12 0 0
Total time: 50.128 seconds
After 500 rounds on 4000x4000, number of live cells is 17

$ ./gol big.txt 0 20 0 0
Total time: 53.965 seconds
After 500 rounds on 4000x4000, number of live cells is 17

Your program must satisfy all the requirements of the sequential gol lab, except that if you did not get the edges to work correctly, you do not need to fix that part (i.e. if your edge cells are not quite in your sequential gol, that is okay for your parallel solution).

Your program should handle the new command line arguments in addition to the previous ones.

The total_live global variable that should be updated each round to the number of live cells. Its value should be computed in parallel each round with each thread updating the portion of total_live value for a round from its portion of the grid.

The only other global variables you may add are any needed for pthread synchronization. Any values that threads need should be passed to them via the (void *arg) parameter. Look at the example pthread programs from Week 12, from in class, and in the textbook for some examples of how to do this. You will likely need to add fields to your struct gol_data type that are needed for threads to perform gol on their part of the grid (e.g. which rows and columns this thread is operating on and the logical thread id number).

The control flow in your sequential main function doesn’t need much change. You need to parse the additional command line arguments and make calls to pthread_create. If you find you are adding a lot of code to main, stop and create a function to do this work and call that function from main: main should not get a lot longer, and its main control flow really should not change.

For full credit, your solution should be correct, robust, and free of valgrind errors (when run in modes OUTPUT_ASCII or OUTPUT_NONE). "Still reachable" errors are okay.

You are NOT responsible for running valgrind in the OUTPUT_VISI mode (the ParaVis visualization mode). "Still reachable" errors are okay.

All TODO comments in the starting point code should be removed in your final submission. These are notes to you for what you need to add into the starting point code and where you need to add it.

Use good modular design, and comment your code well.

Last lab! 🎉 Good luck! 🥳

Look at the Lab 06 page for lots of tips related to sequential GOL that may be useful here too.

Implement and test incrementally!

Most of your changes will be to the play_gol function. You should also add helper functions to implement any new functionality. main should not get much longer, so if you need to add alot of code to main, or you are adding the same code to multiple parts, functionize it and call it from main. Plus you can independently test this code by adding debugging calls to this function from main!

You will need to add fields to your struct gol_data type that are needed by threads to perform gol on their part of the grid.

Use gdb as you incrementally implement and test to find and fix bugs as you go. Use valgrind as you go to catch memory access errors as you make them.

As you test and debug, you may find it useful to use config files with small numbers of iterations. You may also want to comment out the call to system("clear") so you can examine the results of every intermediate iteration.

Running in OUTPUT_VISI and OUTPUT_ASCII are helpful for finding and debugging partitioning errors and other correctness errors.

ParaVis with colors.h: If you’d like to use some of the colors I have defined in colors.h you can set an RGB value in the color3 image array to a value in colors like this:

   // assume buff is name of the color3 array:
   buff[buff_i] = colors[3];  // set this pixel to the 3rd color (Yellow)

   if(live) {
     buff[buff_i] = c3_black;  // set live cells to black
   } else {
     // assumes your thread id is stored in your struct as tid;
     // modify the line below if you called it something different.
     buff[buff_i] = colors[((data->tid)%8)]; // dead to my tid color
   }

The man pages for the various pthread functions are very helpful.

You can use the perror() function to print out error messages from failed system and pthread library calls. perror prints out detailed, human-readable information about the error that occurred. You call it passing in a string with program-specific error message. For example:

big_buff = malloc(...);
if (big_buff == NULL) {
  perror("malloc of big buffer failed");
  exit(1);
}

You will need to use some synchronization in your solution. You may use any of the pthread synchronization primitives, including mutexes and barriers. Remember that before using any of these, you need to initialize them. You also need to make sure that all threads have access to the shared synchronization variables (either pass a reference to them at thread creation or declare them as static global variables). Here are some code snippets for using the barrier synchronization primitive:

// declare a global pthread_barrier_t
static pthread_barrier_t barrier;

// initialize it in a function (e.g., main) before using it:
if(pthread_barrier_init(&barrier, NULL, num_threads)){
   perror("pthread_barrier_init");
   exit(1);
}

// each thread can then call pthread_barrier_wait to synchronize:
ret = pthread_barrier_wait(&barrier);
if(ret != 0 && ret != PTHREAD_BARRIER_SERIAL_THREAD) {
  perror("pthread_barrier_wait");
  exit(1);
}

Class EdSTEM page for questions and answers about lab assignment

CS31 github org

Git help and Git for CS31 labs

Some Useful Unix Commands

vi (and vim) quick reference

man and Manual pages documentation for libraries and commands

Week 12 Weekly Lab Examples

Dive into Systems, Chapter 2 on C programming

Dive into Systems, Chapter 3 on gdb

Dive into Systems, Chapter 14 on pthreads

C Programming Resources and Links including I/O in C, cmdline args, arrays

GDB guide

Valgrind Guide,

compiling and running C programs on our system

C code style guide

make and makefiles

some other pthreads documentation and tutorials

Debugging pthreads programs with gdb

Week 8 in-lab examples: ParaVis, and other sequential GOL related examples.