Spring 2008.
The purpose of this assignment is to give you some general experience
in writing shared memory programs using the standard
pthreads library package.
For more information on pthreads, you may want to consult the
pthreads man
page and the tutorial
from Lawrence Livermore National Lab.
On the man page, you will see that Sun provides somewhat more extensive
facilities for its threads package, but these are not
portable across platforms.
Log on to our smaller SunFire machine,
sync.cs.rochester.edu and set up your account. Create a
program that launches t threads that print their thread id and halt.
(Please do not use the larger machine, swym; it’s being
used fairly heavily for research experiments.)
Extend your program to have the threads share a counter. Have each thread increment the counter i times
Try each option with varying numbers of threads, both greater and fewer
than the number of processors in the machine. (To find out how many
processors there are, run psrinfo -v). Report final
counter values and execution times. Try any other tests that occur to
you. Explain your results (in writing).
To simplify testing of your code, please write your program to take
the number of threads t and the number of iterations i as
command-line arguments, specified with “-t
t” and “-i i” (in
either order). If the arguments are not specified, use t = 4
and i = 10,000.
Be sure to include a README.pdf file that explains what you did and what you learned. It should include your timing results and analysis of the various locks. We will be grading the assignment on a roughly equal mixture of completeness and correctness; programming style; and quality of write-up.
Use the infrastructure you built for Part II to test concurrent queue algorithms. Specifically, have each thread run a loop in which it repeatedly enqueues data to, or dequeues from (with 50-50 probability), a shared queue. Implement the queue four different ways:
volatile variable (without the
volatile read, the compiler may “optimize” the
loop away). Experiment with different values for the backoff base
(initial delay) and cap (maximum delay). Pick (and report in your
README file) values that seem to maximize throughput.
As described in the linked sources above, be sure to use “counted
pointers” to avoid the ABA problem.
Also, to avoid “polluting” your results with the overhead of
memory management (the standard malloc and
free don’t scale well), you should have each thread
pre-allocate its own supply of nodes, which it can keep on a private
list when they are not in the queue.
Finally, to avoid pollution from calls to the pseudo-random (the
standard rand isn’t even thread-safe), you should
pre-generate enough random bits to drive the choice between enqueueing
and dequeueing for the entire test run.
Be sure to use a barrier (described in the notes below) to “synch
up” your threads after this setup is complete, and before starting
the timing run.
As in Part II, your README.pdf file should contain a detailed description of the experiments you ran, graphs of the results, and discussion that explains those results—why they look the way they do.
The Gnu C compiler provides a very flexible mechanism to insert
assembly language instructions (e.g. the various atomic primitives)
into your code. Unfortunately it’s a rather confusing mechanism, so
we’ve written the magic incantations for you: atomic_ops.h.
We’ve also written very simple implementations of the (test-and) TAS (tas.h) and ticket (ticket.h)
locks.
Pthreads are not part of the C standard library. To use them you
must link in a separate library explicity. Add
-lpthread to the end of your gcc command line. We
strongly recommend that you create a Makefile for your assignment, even
if you have only a few files. Something like the following is a good
start:
CC = gccThis assumes that your test program is named
# CFLAGS = -msupersparc -Wa,-xarch=v8plus -g
CFLAGS = -msupersparc -Wa,-xarch=v8plus -O3
test: test.c
$(CC) -o test $(CFLAGS) test.c -lpthread
test.s: test.c
$(CC) -S -fverbose-asm $(CFLAGS) test.c
clean:
rm test
test. The test.s
rule allows you to see the SPARC assembly code you’re running, if
you’re curious, or if you need to debug any in-line assembler. To time programs under Solaris, use the gethrtime()
library call. Run your tests multiple times. See which results seem
repeatable, and which vary greatly from one run to the next. (And try
to explain why.) To gain the absolute maximum performance you may
have to resort to techniques such as binding a thread to
processor. Take a look at techniques such as
processor_bind.
In order to see race conditions, you need to persuade your
threads to run at roughly the same time. (If you don’t do anything
special, it’s possible for a newly created worker thread to finish all
its counter increments before the master thread manages to create the
next worker.) The mechanism you want is a barrier.
You can also use it to make sure all your threads are done before you
check results. (You don’t want to use thr_join() for
this; like create_thread it’s so expensive it can hide what you’re
looking for.) If you call the barrier() routine in all
your worker threads, they’ll all wait for each other to “synch up”
before proceeding. If you want to perform multiple timing tests in a
single program execution, you can safely call the barrier multiple
times. Your code should look something like this:
barrier() // threads are all together
if (tid == 0) {
counter = 0
start = gethrtime() // thread 0 checks the time
}
barrier() // other threads wait for 0 to catch up
for (i = 0; i < iters; i++) { // the test itself
counter++
}
barrier() // make sure all threads are done
if (tid == 0) {
end = gethrtime()
print counter, end-start
}
// more tests
Machines:
ps -Af before you log out and make sure
you don’t leave any run-away processes behind. 