Spring 2019.
The purpose of this assignment is to give you some general experience
in writing shared memory programs using the standard threads of C++.
These are based, on most platforms, on the older
pthreads
library.
For an overview of the language mechanisms, consult any of the various
online tutorials (this
one is pretty good).
For a more formal reference, consult
cplusplus.com
or
cppreference.com.
If you’re curious about pthreads, the
tutorial
from Lawrence Livermore National Lab is very good.
Your task for this assignment is to create a “microbenchmark” that compares the performance (and in some cases correctness) of several versions of a tiny code fragment that represents an operation of potential interest in larger programs. Specifically, your program should take as input two optional parameters t and i, and output the time required for each of t threads, running concurrently, to increment a shared counter i times (a total of t * i increments).
To simplify testing of your code, please name your program
parcount
, and arrange for it 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 = 10000.
Please also employ a Makefile
to compile and link your
code. We are providing a default
Makefile
that should be all you need.
If you do modify it, please be sure that “make
clean
” and “make parcount
”
continue to work.
Your program should create t threads and should execute five phases:
mutex
with explicit lock
and unlock
operations
mutex
acquired and released via
declaration of a local lock_guard
atomic_int
and accessed with fetch_add
operations
fetch_add
); alternatively, the main thread could add the
local counters together.
For the purposes of this assignment,
you will want to make sure that threads start working on each
phase at pretty much the same time, so they really are competing with
each other. (Your performance results might be very different if,
say, thread 1 finished all its increments before thread 2 did any at
all.)
Perhaps the easiest way to ensure this is to have the “master”
thread (the one that the system created to execute main
)
create a bunch of worker threads, wait for them to finish the
current phase, join
them all, and then
create a new set of threads for the next phase.
(You could also use barrier synchronization among a single set
of threads, used for all phases, but for some mysterious
reason barriers aren't provided as a built-in in C++.)
To “synch up” thread start times in each phase,
I suggest using a global atomic_bool start
flag that is
initialized to false
before launching the threads, and then
set to true
after the last thread is launched. If
each thread waits for the flag to become true before starting its
increments,
while (!start.load()); // spinyou maximize the odds of them actually running in parallel. You will also, of course, want to reset the counter to zero at the beginning of each phase, before launching any the new threads.
According to the C++ language manual, the first phase will have undefined behavior, because of the data race. While the compiler is allowed to do absolutely anything in the face of such a race, in practice it won’t do anything crazy: it will just generate code that gives you incorrect results. The point is to see how wrong the output can be, and to have a performance baseline against which to compare the other versions. (At the end of each phase except the first, the counter should have value t * i.)
Try your program with varying numbers of C++ threads, both greater and fewer than the number of hardware threads (“cpu”s) in the machine. Pick values of i that cause each phase to run for a few seconds. Run your program multiple times to make sure that there isn’t too much variation in timing across runs (throw out any large outliers: they probably indicate interference by another user or a system daemon). Report final counter values and throughput (measured in increments per millisecond) for each phase. Try any other tests that occur to you. Explain your results (in writing) in a README.pdf file (do not submit Word, OpenOffice, dvi, or other formats). Include a performance graph that shows increments per millisecond as a function of thread count for each of the synchronization strategies (phases). We will be grading the assignment on a roughly equal mixture of (a) completeness and correctness, (b) programming style, and (c) quality of write-up.
To time your code, read the documentation for
std::chrono::high_resolution_clock::now
.
To find out how many processors there are on the machine, use the
function std::thread::hardware_concurrency
.
Alternatively, inspect the bookkeeping file /proc/cpuinfo
on the machine where you run the experiments, or run lscpu
at the command-line prompt. The latter will also tell you which
hardware threads (cpus) are on which cores and
sockets. This leads us to the topic of:
By default, the operating system is free to run your C++ threads on whichever hardware threads it wants. In practice, it will generally try to run them on different cpus, and it will generally try to scatter these across cores and sockets. That isn’t always good for performance, especially when threads share data, because it takes much longer to move new values between sockets than it does between cores on the same socket.
If you are in CSC 458 you are required to experiment with
processor affinity—the mapping of software threads to
hardware threads—and its impact on performance.
Specifically, use the lscpu
command and the Linux
pthread_setaffinity_np
library function to run each of your
experiments twice: once with all C++ threads restricted to cores of a
single socket and once with them explicitly scattered 50/50 across the
two sockets of a two-socket machine. Discuss the impact on
performance in your README.pdf file.
If you are in CSC 258, you may undertake this part of the assignment for extra credit.
For a good introduction to hyperthreads, cores, sockets, and thread affinity, see the blog post by Eli Bendersky.
To get accurate timings you’ll need to run when no one else is
running. I suggest that you do code development on one of the
standard cycle servers (or your own laptop, if you prefer).
When you’re happy with your code,
ssh
to one of the available multiprocessors, and run
uptime
to make sure the machine is mostly idle. Then
collect your results. For later assignments, when your code will
have longer run times, we’ll create a sign-up sheet for exclusive
access to the servers.
A variety of multiprocessors are available
on both the cs
and csug
networks
(list here).
On both networks, the machine
with the highest core count is currently named
node2x18a.cs.rochester.edu
.
Please be careful not to place unreasonable burdens on these machines.
You won’t get reliable timing information if anyone else if
running an experiment concurrently. And on the research network,
the various multiprocessors are being actively used for real
research.
Before you log out, you should always run ps -Af
(and, if necessary, kill -9
)
to make sure you don’t leave any run-away processes behind.
To turn in your code, follow the turnin directions. If you have questions, post to the discussion board.
Note that if you leave this assignment to the last minute, you’re unlikely to be able to get solo time on the machine, so plan to run your experiments well ahead of the deadline and spend the last few days on write-up.