Homework 10: Performance of Concurrent Programs

In this homework, we'll study the relative performance of several synchronization methods, first through a basic counter, and then in a concurrent hash table. Your template is available in svn://bits.cs.uic.edu/cs361/pub/homeworks/hw10

Counter Synchronization

For this part, we revisit our old go-to problem of counting. The template contains a basic multi-threaded application counter.c, without synchronization, which produces an incorrect final count. Your job is to create several alternative implementations of the functions init() and increment(), using different techniques to ensure properly synchronized access to the counter. Copy nosync.c to create each of the implementations below.

• pthread_mutex.c - use the standard pthread mutex operations to synchronize access.
• semaphores.c - use standard pthread mutexes to synchronize access
• futex.c - use the Linux futex system call, together with the CMPXCHG assembly instruction, as shown in class to synchronize access
• atomicincrement.c - use the LOCK INCL assembly instruction to ensure atomic counter increments

For each implementation, note the mean runtime in a file called counter_runtime.txt.

Concurrent Data Structure

In this part, we study the performance impact of different synchronization strategies on a concurrent datastructure. The file hashmap.c contains a basic hash table implementation without synchronization, and hashmain.c contains an application that uses the hash table. Copy hashmap.c to new files named as below, and create concurrent hashtables using several synchronization methods.

• globallock.c - synchronize the basic hash table using a single global lock held for both the get() and put() operations.
• optimistic.c - use atomic increments to track a global version number, implement get() with optimistic concurrency (no locking)
• finegrained.c - synchronize the basic hash table using 64 locks, distributed evenly over the 1024 hash buckets.

For each implementation, note the mean runtime in a file called hashmap_runtime.txt.

Turn-in instructions

Don't forget to svn add your files and svn commit, including the runtime files described above.