Homework10 < CS361fall13

CS361fall13 Web>Homework10 (2013-11-26, Main.jakob) (raw view)EditAttach
---++ 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
   * *atomicincrement.c* - use the =LOCK INCL= assembly instruction to ensure atomic counter increments
   * *futex.c* - use the Linux futex system call, together with the =CMPXCHG= assembly instruction, as shown in class to synchronize access

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.
Topic revision: r3 - 2013-11-26 - 04:44:40 - Main.jakob
CS361fall13
WISEST
Helping Women Faculty Advance
Funded by NSF