CS111 - Project 2B: Lock Granularity and Performance


In Project-2A, Part-2, the mutex and spin-lock proved to be bottlenecks, preventing parallel access to the list. In this project, you will do additional performance instrumentation to confirm this, and extend your previous solution to deal with this problem. Project 2B (this part!) can be broken up into a few major steps:


Partitioned lists and finer granularity locking are discussed in sections 29.2-4



A single tarball (.tar.gz) containing:


To perform this assignment, you will need to research, choose, install and master a multi-threaded execution profiling tool.  Execution profiling is a combination of compile-time and run-time tools that analyze a program’s execution to determine how much time is being spent in which routines.  There are three standard Linux profiling tools:

This project is about scalable parallelism, which is only possible on a processor with many cores.  You can do most of your development and testing on any Linux system, but if your personal computer does not have more than a few cores, you will not be able to do real multi-threaded performance testing on it.  Lab servers are available if you need access to a larger machine for your final testing.


Review your results from Lab 2 Parts 1 (lab2_add-5.png)  and 2 (lab2_list-4.png).  In Part-1, for Compare-and-Swap and Mutex throughput (total operations per second), we saw that adding threads took us from tens of ns per operation to small hundreds of ns per operation. Looking at the analogous results in Part-2, we see the (un-adjusted for length) time per operation go from a few microseconds, to tens of microseconds.  For the adds, moderate contention added ~100ns to each synchronization operation.  For the list operations, moderate contention added ~10us to each synchronization operation.  This represents a 100x difference in the per operation price of lock contention.

Go back to your lab1 and lab2 data, and create a new plotting script that will graph the same data, but plotting the throughput (operations per second) rather than the time per operation:

In the previous lab, we gave you all of the necessary data reduction scripts.  In this lab, you will have to create your own … but you can use the scripts provided in the previous lab as a starter:

The most obvious differences, which we already knew:

But these throughput graphs show us something that was not as obvious in the cost per operation graphs:

The obvious conclusions (from both the cost-per-operation graphs you produced last week, and the throughput graphs you have just produced) are:

Since the code inside the critical section does not change with the number of threads, it seems reasonable to assume that the added execution time is being spent getting the locks.

QUESTION 2.3.1 - Cycles in the basic implementation:

Where do you believe most of the cycles are spent in the 1 and 2-thread tests (for both add and list)?  Why do you believe these to be the most expensive parts of the code?

Where do you believe most of the time/cycles are being spent in the high-thread spin-lock tests?

Where do you believe most of the time/cycles are being spent in the high-thread mutex tests?

It should be clear why the spin-lock implementation performs so badly with a large number of threads.  But the mutex implementation should not have this problem.  Now you have some theories about why these algorithms scale so poorly.  But theories are only theories.  We need some data to confirm our theories.

Execution Profiling

Build your program with debug symbols, choose your execution profiling package, install it, run the spin-lock list test (1,000 iterations 12 threads) under the profiler, and analyze the results to determine where the cycles are being spent.

The default output from google-pprof will show you which routine is consuming most of the cycles.  If you then re-run google-pprof with the --list option (specifying that routine), it will give you a source-level breakdown of how much time is being spent on each instruction.  You should get a very clear answer to the question of where the program is spending its time.  Update your Makefile to run this test and generate the results automatically (make profile), include your profiling report in your submitted tarball, and identify it in your README file.

QUESTION 2.3.2 - Execution Profiling:

Where (what lines of code) are consuming most of the cycles when the spin-lock version of the list exerciser is run with a large number of threads?

Why does this operation become so expensive with large numbers of threads?

Timing Mutex Waits

In the mutex case, we are not spinning.  A thread that cannot get the lock is blocked, and not consuming any cycles.  How could we confirm that, in the mutex case, most threads are spending most of their time waiting for a lock?  

Update your mutex implementation to:

Run the list mutex test again for 1,000 iterations and 1, 2, 4, 8, 16, 24 threads, and plot the wait-for-lock time, and the average time per operation against the number of competing threads.  Call this graph lab2b_2.png.  

QUESTION 2.3.3 - Mutex Wait Time:

Look at the average time per operation (vs # threads) and the average wait-for-mutex time (vs #threads).  

Why does the average lock-wait time rise so dramatically with the number of contending threads?

Why does the completion time per operation rise (less dramatically) with the

number of contending threads?

How is it possible for the wait time per operation to go up faster (or higher) than the completion time per operation?

Addressing the Underlying Problem

While the details of how contention degrades throughput are different for these two mechanisms, all of the degradation is the result of increased contention.  This is the fundamental problem with coarse-grained synchronization.  The classic solution to this problem is to partition the single resource (in this case a linked list) into multiple independent resources, and divide the requests among those sub-resources.

Add a new --lists=# option to your lab2_list program:

The supported command line options and expected output are illustrated below:

% ./lab2_list --threads=10 --iterations=1000 --lists=5 --yield=id --sync=m



Confirm the correctness of your new implementation:

Now that we believe the partitioned lists implementation works, we can measure its performance.  Rerun both synchronized versions without yields for 1000 iterations, 1,2,4,8,12 threads, and 1,4,8,16 lists.  For each synchronization mechanism, graph the aggregated throughput (total operations per second, as you did for lab2a_1.png) vs the number of threads, with a separate line for each number of lists.  Call these graphs lab2b_4.png and lab2b_5.png

QUESTION 2.3.4 - Performance of Partitioned Lists

Explain the change in performance of the synchronized methods as a function of the number of lists.

Should the throughput continue increasing as the number of lists is further increased?  If not, explain why not.

It seems reasonable to suggest the throughput of an N-way partitioned list should be equivalent to the throughput of a single list with fewer (1/N) threads.  Does this appear to be true in the above curves?  If not, explain why not.


Your tarball should have a name of the form lab2b-studentID.tar.gz and should be submitted via CCLE.

We will test it on a SEASnet GNU/Linux server running RHEL 7 (this is on lnxsrv09). You would be well advised to test your submission on that platform before submitting it.


Value        Feature

        Packaging and build (10%)

2%        untars expected contents

3%        clean build w/default action (no warnings)

3%        Makefile produces csv output, graphs, profiling reports, tarball

2%        reasonableness of README contents

        Code review (20%)

4%        overall readability and reasonableness

4%        multi-list implementation

4%        thread correctly sums up the length across sublists

4%        mutex use on multi-lists

4%        spin-lock use on multi-lists


        Results (40%) ... produces correct output

5%        lists

5%        correct mutex

5%        correct spin

5%        reasonable time per operation reporting

5%        reasonable wait for mutex reporting

5%        graphs (showed what we asked for)

10%        profiling report (clearly shows where the cycles wwent)

Note: if your program does not accept the correct options or produce the correct output, you are likely to receive a zero for the results portion of your grade.  Look carefully at the sample commands and output.  If you have questions, ask your TA.

        Analysis (30%) … (reasonably explained all results in README)

2%        General clarity of thought and understanding

7%        2.3.1 where the cycles go

7%        2.3.2 profiling

7%        2.3.3 wait time

7%        2.3.4 list partitioning