Contents (hide)

Welcome to Multiprocessor Synchronization Algorithms homepage

Class Number

202-2-5401

Schedule

Sun. 16:00-18:00, building 34, class 107
Wed. 14:00-16:00, building 34, class 7

General information

The grade of the course is composed of the following two components.

  • Home assignments : three home assignments will be given. It is mandatory to submit at least two assignments. Home assignments weight 30% of the final grade (15% each). If you submit all three assignments, then the two highest grades will be taken into account. Home assignments are algorithmic/theoretical - they are not programming assignments.

  • Take-home final exam : the final exam will be a take-home exam. Its grade weighs 70% of the final grade. The home exam will be given for a duration of one week. Exact dates will be determined by us during the course.

Syllabus

Did you recently buy a PC? If you did, then it is almost certain that it contains a multi-core processor. Multi-core PCs are just one example of a shared-memory multiprocessor. While being used in the past mainly for high-end server machines, shared-memory multiprocessors are now the standard for both desktops and laptops and are also starting to dominate the smartphone market. Algorithms for multiprocessor systems are, in general, more complicated than sequential algorithms. This is because of the need to synchronize and coordinate threads running on different processors.

This course studies multiprocessor algorithms and the rich theory that underlies them. You will gain understanding of the complexity of designing algorithms for multiprocessors, of the strengths of these systems, and also of their inherent limitations. While we will focus on shared-memory multiprocessors, we will also touch upon message-passing systems.

The course will cover the following topics (changes are possible, even probable).

  1. Mutual exclusion using atomic registers: Peterson and Kessels' algorithms, Peterson's tournament tree, Lamport's fast mutual exclusion algorithm, the bakery algorithm, space lower bounds.
  2. Leader election in rings : an (n log n) messages algorithm for asynchronous rings, lower bound on number of messages, non-uniform/uniform algorithms for synchronous rings.
  3. Shared objects, linearizability and wait-freedom : histories, sequential specifications, wait-free & linearizable register simulations.
  4. The consensus problem: wait-free consensus, the relative power of synchronization primitives, Herlihy's wait-free hierarchy, the universality of consensus.
  5. Concurrent data-structures : Treiber's algorithm, the elimination backoff stack, concurrent hash-tables, and more.
  6. Contention in shared memory access : operation valency, a linear lower bound on the number of memory stalls.
  7. Lower bounds : covering and valency arguments.
  8. Local spin algorithms and the RMR complexity measure : the CC and DSM models, Anderson/Yang mutual exclusion algorithm, shared-memory leader election algorithms
  9. Transactional Memory : A novel concurrent programming paradigm, viewed by many as having the potential of becoming a viable alternative to lock-based programming.

Bibliography

  • "Distributed Computing: Fundamentals, Simulations, and Advanced Topics", 2'nd edition, by Hagit Attiay and Jennifer Welch, John Wiley and Sons.

  • "The Art of Multiprocessor Programming", by Maurice Herlihy and Nir Shavit, Morgan Kaufman.

  • "Synchronization Algorithms and Concurrent Programming", by Gadi Taubenfeld, Pearson/Prentice Hall