CSC 2/458: Parallel and Distributed Systems

Spring 2019.

Assignment 1: C++11 threads

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:

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());  // spin
you 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.) 

Experiments

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:

Affinity

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.

Logistics

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. 

Due Date: Sunday, February 3, 11:59 pm.


Last Change: 27 January 2019 / Michael Scott's email address