CSC 2/458: Parallel and Distributed Systems

Scalable Synchronization Algorithms



Due Date: Midnight, Thursday, February 25th, 2016.


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.
  1. Create a program that launches t threads and have them all work on a shared counter.  Try experiments where [1] each thread increments the counter a total of i times (all threads contend for the counter and execution terminates when the counter value reaches i), and [2] where each thread increments the counter i times (for a total of t*i).

  2. Change the loop so that instead of a single shared counter, a random location in an array of 1000 shared integers is incremented. Use separate TAS locks for each location. Compare this version to using Intel's TSX - either speculative lock elision or transactional memory.

  3. 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