Create a program that launches t threads and have them all work on a shared counter. Try experiments where [1] each thread increments the counter for a total of i times (all threads contend for the counter and execution terminates when the counter value reaches i), and [2] where each thread increments the counter i times (for a total of t*i).
Pseudocode for all of these (other than the first two) can be found in
Chapter 4 of
Shared-Memory Synchronization.
You will need to translate these to C++.
Be sure to declare appropriate fields as atomic
.
In addition, you should specify appropriate memory_order
parameters on load
, store
, and
read-modify-write operations.
For full credit, you should specify the minimum orders necessary for
correctness.
Students in CSC 458 are additionally required to collect and analyze resuts on an IBM Power machine (CSC 258 students may do so for extra credit): node-ibm-822.csug. Using C++ will facilitate portability. You should develop and debug your code on an x86 machine first. Because of its more relaxed memory model, the IBM machine may expose bugs that are hidden on the x86.
Change the loop so that instead of a single shared counter, a random location in an array of 1000 shared integers is incremented. Use separate TAS locks for each location. Extra Credit: Compare this version to using Intel's TSX - either speculative lock elision or transactional memory.
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.
Try each option with varying numbers of threads, both greater and fewer
than the number of processors in the machine: using powers of two and values
halfway in between (e.g., 1, 2, 4, 6, 8, 12, 16, 32, 48, 64, 96, 128)
allows for sufficient coverage. (To find out how many
processors there are,
examine /proc/cpuinfo
on x86/Linux machines. Report final
counter values, execution times, and the number of times each thread
incremented the counter in the case of the first experiment.
Try any other tests that occur to
you. Explain your results (in writing).
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.
pthreads
man
page and the tutorial
from Lawrence Livermore National Lab.
The Gnu C compiler provides a very flexible mechanism to insert
assembly language instructions (e.g. the various atomic primitives)
into your code, which you may choose to use.
Unfortunately it’s a rather confusing mechanism, so
we’ve written the magic incantations for you: atomic_ops.h
.
This file also includes example implementations of all the locks. Since
the primitives are written in barebones assembly they are machine
specific, however, and has not been ported to the IBM machines.
We have used #defines where appropriate. The "__i386"
defines are to be used on 32 bit x86s (cycle1,e series, a
series, "__x86_64__" on the 64bit x86s
and "__sparc__" on the SUN boxes.
The magic incantations for Intel's HLE are in: hle_atomic_ops.h
. Intel's RTM interface specifications
can be found at Intel's TSX Tools.
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 g++ command line. We
strongly recommend that you create a Makefile for your assignment, even
if you have only a few files. Take a look at the Makefiles from
the previous assignement. Start with the machine specific files
where appropriate. Unlike the previous
assignment, the .h files here require the g++ compiler.
clock_gettime
or
the fine-grain gethrtime
timer provided at /u/cs(2or4)58/hrTimer/
.
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 a
processor. In order to see race conditions, you will need to ensure that your
threads 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.) You can use a barrier to accomplish this
(we've provided code for a centralized sense-reversing
barrier).
You should also use it to make sure all your threads are done before you
check results and timing. (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 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
top
to
ensure you have the machine to yourself (and coordinate amongst yourselves
if there is contention). gcc -E -\ dM -x c /dev/null
. This will list
a bunch of #defines in gcc. Search for x86_64 or i386 etc.
ps -Af
before you log out and make sure
you kill any run-away processes.