TWiki
>
CS361fall13 Web
>
Homework10
(2013-11-26, Main.jakob)
(raw view)
E
dit
A
ttach
---++ 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.
E
dit
|
A
ttach
|
P
rint version
|
H
istory
: r3
<
r2
<
r1
|
B
acklinks
|
V
iew topic
|
Ra
w
edit
|
M
ore topic actions
Topic revision: r3 - 2013-11-26 - 04:44:40 - Main.jakob
CS361fall13
Syllabus
Homework Schedule
Lecture Notes
Reading List
Additional Material
Piazza Board
EC2 Sign-In Page
ABOUT US
Our Department
Recent News
Contact Us
ACADEMICS
Prospective Students
Undergraduate
CS Minor
Graduate
Courses
RESEARCH
Overview
By Faculty
Labs
PEOPLE
Faculty
Adjuncts
Staff
Students
Alumni
Copyright 2016 The Board of Trustees
of the University of Illinois.
webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF