CSC 2/458: Parallel and Distributed Systems

Spring 2017.

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 (as of 2011) 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 program for this assignment will be 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 = 10,000.  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:

You will want to join and then re-launch the threads for 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 of the 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 anytihng 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 threads, both greater and fewer than the number of processors in the machine.  (To find out how many processors there are, inspect /proc/cpuinfo).  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).  We will be grading the assignment on a roughly equal mixture of completeness and correctness, programming style, and quality of write-up. 

To time your code, read the documentation for std::chrono::high_resolution_clock::now

I strongly recommend (but do not require) that you create a makefile for your project.  (If you don’t know what that is, you should definitely learn :-) 

To turn in your code, follow the turnin directions.  If you have questions, post to the discussion board

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, run timing experiments in person in the Systems lab (CSB 727) or the Hylan Lab (for undergrads and MS students) so you can coordinate with other students and avoid messing up each others’ results.  On the research (cs) network, a variety of multiprocessors are available (list here).  Machine node2x18a.cs.rochester.edu currently has the highest core count.  On the teaching (csug) network, you should collect your final figures on node2x14a.csug.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. 

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: Monday, February 6, 11:59 pm.


Last Change: 25 January 2017 / Michael Scott's email address