CSC 2/458: Parallel and Distributed Systems

Scalable Synchronization Algorithms



Due Date: Midnight, Monday, February 18th, 2013.


The purpose of this assignment is to analyze the tradeoffs among different synchronization algorithms in terms of their latency, fairness, scalability, traffic, and storage requirements. The performance levels of the algorithms used varies widely due to interaction between multiple factors, including the length of the critical section and the latency of communication. Your mission is to reason about the performance of these locks in terms of: latency, scaling behavior, effects of preemption (i.e., saturated CPU resources), and fairness.

Create a program that launches t threads and have them all work on a shared counter.  Try experiments where each thread increments the counter a total of i times, and where each thread increments the counter i times (for a total of t*i).

Test the scalability of several global barrier implementations. Create a program that launches t threads and have them arrive i times at a barrier implemented using

Try each option 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, run psrinfo -v) on the sparcs, or examine /proc/cpuinfo on x86/Linux machines.  Report final counter values, execution times, and the number of times each thread incremented the counter in the case of the first experiment.  Try any other tests that occur to you.  Explain your results (in writing). 

To simplify testing of your code, please write your program 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. 

Be sure to include a README.pdf file that explains what you did and what you learned.  It should include your timing results and analysis of the various locks.  We will be grading the assignment on a roughly equal mixture of completeness and correctness; programming style; and quality of write-up. 

Notes