CSC 2/458: Parallel and Distributed Systems

Spring 2019.

Assignment 3: Spin Locks

Your next programming assignment is an extension of the first.  For that earlier assignment, you compared the performance of several ways to increment a global counter (a surrogate for the statistics collecting that many applications do in conjunction with their “real” work).  In this current assignment you will focus on locks.  Rewrite your code from the earlier assignment to perform its counter increments under protection of Pseudocode for all of these (other than the first) 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.  (I’m pretty sure that I have the right specifications in the book, but they were all figured out on paper, and haven’t been tested “in the field,” so it’s at least possible you’ll find a bug; if so, please let me know immediately!) 

Students in CSC 258 are required to collect and analyze results on an x86 machine (node2x18a.csug or node2x18a.cs).  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).  As with the x86, there are identical machines on the teaching and research networks—node-ibm-822.cs and node-ibm-822.csug.  Students in CSC 458 should develop and debug their 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. 

As in the earlier assignment, your microbenchmark should take as input two optional parameters t and i, specified as command-line arguments.  For each program phase (each lock algorithm listed above), you should output the time required for each of t threads, running concurrently, to increment a shared counter i times (a total of t * i increments).  Please use the same program name and Makefile that you used in that assignment.  Try your program with varying numbers of threads, both greater and fewer than the number of hardware threads in the machine.  Powers of two and the values halfway in-between (1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128) are often good choices.  See the earlier assignment for further methodological advice. 

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 mix of completeness and correctness, programming style, and quality of write-up, with an emphasis on the latter.  Note that explaining your results entails more than a detailed report of what happened: it entails a convincing discussion of why it happened. 

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 x86 timing experiments on node2x18a.csug or node2x18a.cs.  You can also develop on node2x14a.csug if you like.  Before you log out, be sure to run ps -Af (and, if necessary, kill -9) to make sure you don’t leave any run-away processes behind.  And be sure to get your code working early: if you leave this assignment to the last minute, you’re unlikely to be able to get solo time on the machine, or to have time to adequately explain your results. 

Extra Credit Suggestions

Due Date: Friday, March 8, 5:00 pm.


Last Change: 21 February 2019 / Michael Scott's email address