CS31 Lab 7: 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 5.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 is from runs on basil on a 4000x4000 board for 500 iterations 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 of basil), 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 torus 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.

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 function-ize that functionality and call it 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 is 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.

Look at the Lab 5 page for lots of tips related to sequential 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 and to comment out the call to system("clear") so you can examine the results of every intermediate iteration.

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

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("mallocing big buffer failed");
}

You will need to use some synchronization in your solution. You may use any of the pthread synchronization primitives: mutexes, condition variables, and/or barriers. Remember that before using any of these, you need to initialize them and that all threads need to 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);
}

// threads than can 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 piazza 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