Changelog:

  • 5 Apr 2023: correct wrong URL for readings link in tips
  • 6 Apr 2023: update Makefile to actually build life-tsan and have a main.cc that properly processes its arguments
  • 6 Apr 2023 5pm: correct link to main.c to not be broken link
  • 6 Apr 2023: specify to create one fewer thread if the main thread is doing its share of the computations
  • 6 Apr 2023 11pm: add links to copies of sanitizer-test.sh, which was also missing from the skeleton code
  • 7 Apr 2023: add note about restrictions on timing of pthread_barrier_destroy due to libc issue
  • 7 Apr 2023: be more explicit that paralle version needs to match serial one
  • 10 Apr 2023: add information re: using debugger to diagnose hangs to hints

If you downloaded the skeleton code before 6 April around 4pm, then there are some minor issues with that skeleton code:

1 Your Task

1.1 Before you code

Examine the supplied skeleton code [last updated 2023-04-06 3:50pm] which implements Conway’s Game of Life. You should only edit life-parallel.c, but that interacts with many other files in the package.

Make sure you look at input/README.md, as well as life.h and any other files you wish.

The provided code will compile and run. We encourage experimenting with it before adding any code of your own.

Make sure you understand how simulate_life_serial works. You’ll be making a (more complicated) parallel version of this, and are unlikely to be successful if you don’t understand this starting point.

1.2 Implement parallel Life

Create a parallel version (using pthreads) in life-parallel.c. You must use the provided header

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

life-serial.c contains a correct, working single-threaded implementation you are welcome to borrow from. You should write helper functions as appropriate to keep your code well-organized.

Additional constraints:

  1. Your implementation must be correct (result in the expected final board configuration, matching the serial version) for all boards and iteration counts.

  2. You must call pthread_create exactly threads times (assuming you are computing cell values only in new threads you create; if you also compute cell values in the main (initial) thread, call it threads-1 times instead). Do not create more or fewer threads, nor create new threads for each iteration of the simulation.

  3. We must be able to call simulate_life_parallel from multiple threads concurrently. Do not use global variables or other thread-unsafe practices.

  4. You must have no memory leaks or other memory errors. The provided Makefile builds a version with the address sanitizer enabled automatically as life-asan; this must run without errors.

  5. ThreadSanitizer should not detect likely race conditions or other thread API errors in your code. The provided Makefile builds a version with the thread sanitizer enabled automatically as life-tsan.

  6. You must call the appropriate pthread_***_destroy for each pthread_***_init you call to reclaim any pthreads-allocated memory.

    1. On portal/our testing machines, pthread_barrier_destroy won’t work properly unless called after all pthread_barrier_wait calls have returned. (This is a bug in the pthread_barrier implementation on those machines.)

  7. On a multi-core machine, your parallel code must be noticeably faster than the serial code when run on sufficiently large boards for sufficiently many iterations.

  8. On sufficiently large boards (both enough rows and enough columns), you should split up the work roughly evenly between the threads. (With large sizes, no thread should end up doing more than a few percent more computations than another.)

  9. And, of course, you are still bound by all the usual course policies.

  10. You must not use OpenMP (subject of one of our labs) in your solution: we are trying to measure your understanding of the lower-level tools OpenMP uses.

1.3 Test your code.

Uncomment the lines of main.c that are marked as appropriate to uncomment after simulate_life_parallel is written. Then test your code, as e.g. by running

2 Tips

  1. This assignment was designed to be a natural fit for barriers. You are strongly encourage to get a barrier-based solution working first before attempting any other approaches.

  2. 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.

  3. 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.

  4. The supplied code calls LB_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.

  5. 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 separate threads and one that spawns the threads and waits for them to finish.

  6. If you find yourself tempted to use a global variable (such as a global mutex or barrier), you can usually get away with adding it as a field of a struct passed in by reference to your thread function’s void * parameter instead.

  7. If your code hangs, you can run it in a debugger until it hangs, and then interrupt it (like with control-C) and examine where each thread is.

    For doing this in LLDB, see their tutorial on examining thread state.

    In GDB, you can use a command like thread apply all backtrace to get a backtrace from all threads, and thread THREAD-ID to switch to debugging the thread with a particular ID; see also the manual for debugging with threads in GDB.

3 Caveats