M.I.T. DEPARTMENT OF EECS
| 6.033 - Computer System Engineering | Valgrind Assignment |
Complete the following hands-on assignment. Do the activities described, and submit your solutions using the online submission site by 11:59p.
This assignment relates to the Eraser paper, and exposes you to parallel programming with Pthreads, and understanding and fixing concurrency errors. You might find it helpful to skim the Eraser paper, which is assigned for the next section. You also might want to refresh your memory on what race conditions are and the troubles that they can cause by revisiting sections 5.2.2, 5.2.3, and 5.2.4 of the textbook.
This assignment involves a small amount of programming.
no-knife:~> add 6.033; add gccDownload the program ph.c and store it in a file
ph.c. On a linux system, you might do:
no-knife:~> wget http://web.mit.edu/6.033/www/assignments/ph.cThen compile and run it with one thread:
$ gcc -g -o ph ph.c -pthread $ ./ph 1 completion time for put phase = 2.758351 0: 0 keys missing completion time for get phase = 2.270119
The 1 specifies the number of threads that execute put and get operations on
the the hash table. The program inserts NKEYS into a hash table in
the put phase and then looks them all up in the get phase.
Let's run with 2 threads. Then each thread does NKEYS/2 puts in
the put phase and NKEYS/2 lookups in the get phase. The program is
written in C, the default language for low-level systems programming, and uses
pthreads for creating
several threads that can run in parallel if our machine has several cores
(most processors today have at least 2 cores).
If we achieve perfect parallelism, then the two phases complete in half the time. Here is the output:
~/classes/6033-2013.git/wwwdocs/assignments$ ./ph 2 completion time for put phase = 1.688109 0: 27 keys missing 1: 39 keys missing completion time for get phase = 3.215020
We see that put phase is faster now, so we were able to exploit 2 cores (but it didn't get twice as fast). The get phase, however, is slower with 2 cores, which is disappointing: using more cores, the program ran slower. More on that later, because there is a bigger problem.
You will likely observe that the code is incorrect. The application inserted 27+39 keys in phase 1 that phase 2 couldn't find. In your runs, there may be more or fewer keys missing. There may be even 0 keys missing in some runs. If you run with 1 thread, there will never be any keys missing.
Run the application with 4 threads:
~/classes/6033-2013.git/wwwdocs/assignments$ ./ph 4 completion time for put phase = 1.113811 0: 39 keys missing 2: 31 keys missing 3: 15 keys missing 1: 37 keys missing completion time for get phase = 3.436008
Three points: 1) the put runs faster with 4 cores than 2 cores, but not 4 times as fast as a single core; 2) the get phase ran even slower; 3) more keys are missing.
The ph.c program is simple, and you may be able to spot the
mistake immediately, but we will use a tool, helgrind that helps
us find such errors automatically. helgrind is similar in spirit to
the Eraser system that you are reading about, and is part of a suite of tools
collectively called valgrind.
Run helgrind with ph. You will see output as follows:
$ valgrind --tool=helgrind ./ph 2 ==8945== Helgrind, a thread error detector ==8945== Copyright (C) 2007-2009, and GNU GPL'd, by OpenWorks LLP et al. ==8945== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info ==8945== Command: ./ph 2 ==8945== ==8945== Thread #2 was created ==8945== at 0x513612E: clone (clone.S:77) ==8945== by 0x4E37172: pthread_create@@GLIBC_2.2.5 (createthread.c:75) ==8945== by 0x4C2C42C: pthread_create_WRK (hg_intercepts.c:230) ==8945== by 0x4C2C4CF: pthread_create@* (hg_intercepts.c:257) ==8945== by 0x4010B8: main (ph.c:148) ==8945== ==8945== Thread #1 is the program's root thread ==8945== ==8945== Possible data race during write of size 8 at 0x7ff000440 by thread #2 ==8945== at 0x4C2C54C: mythread_wrapper (hg_intercepts.c:200) ==8945== This conflicts with a previous read of size 8 by thread #1 ==8945== at 0x4C2C440: pthread_create_WRK (hg_intercepts.c:235) ==8945== by 0x4C2C4CF: pthread_create@* (hg_intercepts.c:257) ==8945== by 0x4010B8: main (ph.c:148) ==8945== ==8945== Thread #3 was created ==8945== at 0x513612E: clone (clone.S:77) ==8945== by 0x4E37172: pthread_create@@GLIBC_2.2.5 (createthread.c:75) ==8945== by 0x4C2C42C: pthread_create_WRK (hg_intercepts.c:230) ==8945== by 0x4C2C4CF: pthread_create@* (hg_intercepts.c:257) ==8945== by 0x4010B8: main (ph.c:148) ==8945== ==8945== Possible data race during read of size 4 at 0x1d47168 by thread #3 ==8945== at 0x400C24: put (ph.c:61) ==8945== by 0x400EA1: put_thread (ph.c:98) ==8945== by 0x4C2C558: mythread_wrapper (hg_intercepts.c:202) ==8945== by 0x4E369C9: start_thread (pthread_create.c:300) ==8945== by 0x67D46FF: ??? ==8945== This conflicts with a previous write of size 4 by thread #2 ==8945== at 0x400CC6: put (ph.c:64) ==8945== by 0x400EA1: put_thread (ph.c:98) ==8945== by 0x4C2C558: mythread_wrapper (hg_intercepts.c:202) ==8945== by 0x4E369C9: start_thread (pthread_create.c:300) ==8945== by 0x5FD36FF: ??? ==8945== ==8945== ==8945== More than 10000000 total errors detected. I'm not reporting any more. ==8945== Final error counts will be inaccurate. Go fix your program! ==8945== Rerun with --error-limit=no to disable this cutoff. Note ==8945== that errors may occur in your program without prior warning from ==8945== Valgrind, because errors are no longer being displayed. ==8945==
Question 1: Study helgrind's output and the
ph.c program. Clearly something is wrong with put()
on line 61. Why are there missing keys with 2 or more threads, but not with 1
thread? Identify a sequence of events that can lead to keys missing for 2
threads.
To avoid this sequence of events, insert lock and unlock statements in
put so that the number keys missing is always 0. The relevant
pthread calls are (for more see the manual pages, man pthread):
pthread_mutex_t lock; // declare a lock pthread_mutex_init(&lock, NULL); // initialize the lock pthread_mutex_lock(&lock); // acquire lock pthread_mutex_unlock(&lock); // release lock
The function get() has an example use of locks, and
main initializes it.
Modify ph.c to make it correct and recompile with gcc. Test your
code first with 1 thread, then test it with 2 threads. Is it correct (i.e. have
you eliminated missing keys)? Check the correctness using helgrind.
(Note that valgrind slows down ph a lot, so you may want to modify
NKEYS to be some small number.)
Question 2: Describe your changes and argue why these changes ensure correctness.
Question 3: Is the two-threaded version faster than the single-threaded version in the put phase? Report the running times for the two-threaded version and the single-threaded version. (Make sure to undo your NKEYS change.)
Question 4: Most likely (depending on your exact changes)
ph won't achieve any speedup. Why is that?
Remove the locks from get() in ph.c, recompile, and
rerun the program.
Question 5: You should observe speedup on several cores for the
get phase of ph. Why is that?
Question 6: Why does valgrind report no errors for get()?
Question 7: Can you think of a way of modifying ph.c so that you get speedup
for both phases and valgrind won't report race conditions? (If you
have time, implement that plan and check.)
Go to 6.033 Home Page