Research

High-Performance Synchronization for Shared-Memory Parallel Programs

Synchronization serves to constrain the interleaving of actions performed by multiple threads of control (e.g., on a multicore processor), allowing only correct executions.  Over the years, this ongoing project has developed some of the most efficient and widely used algorithms for locking, concurrent data structures, transactional memory, and persistence.

Available on GitHub:

• URCS Sync repository, including Ralloc, Montage, and Interval-Based Memory Reclamation (IBR).
• Release 7 of the Reconfigurable Software Transactional Memory System (RSTM) for C++ pthreads programs.

Publications (separate page)

Overview

With the explosion in multicore processors, performance and ease of programming for shared-memory multithreaded code have become critical to the future of computing. In the early 1990s, our work helped pioneer the field of scalable synchronization, developing locking mechanisms that scale well to very large numbers of processors/cores. Over the years we have also explored a variety of related topics, including (1) mechanisms for cooperative synchronization and scheduling, which minimize unnecessary spinning, maximize processor locality, and avoid contention for both lock and non-lock data; (2) comparative evaluation of alternative mechanisms for atomic update of shared data structures, including locks, nonblocking synchronization, and function shipping; (3) implementation of atomic hardware primitives on scalable architectures; (4) evaluation of the interaction of synchronization with coherence; (5) timeout-capable spin locks for user-level code; and (6) nonblocking “dual” data structures, which combine lock freedom with condition synchronization. Much of our recent work has focused on (7) software transactional memory, including conflict detection and validation mechanisms, contention management, privatization, language and compiler support, formal semantics, and hardware acceleration; and (8) data structures, locking mechanisms, transactions, and proof techniques for live update of persistent data intended to survive program executions and system crashes.

Work stemming originally from “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors,” by John M. Mellor-Crummey and Michael L. Scott, [ACM TOCS, Feb. 1991], winner of the 2006 Edsger W. Dijkstra Prize in Distributed Computing. Supported by NSF grants CCR-9319445 (4/94 – 9/97), CCR-0204344 (6/2002 – 5/2005), CNS-0615139 (9/06 – 8/09), CCF-0702505 (9/07 – 8/10), CSR-0720796 (9/07 – 8/10), CCR-0963759 (7/10 – 6/14), CCF-1116055 (8/11 – 7/14), CNS-1116109 (8/11 – 7/13), CCF-1337224 (9/13 – 8/16), CCF-1422649 (9/14 – 8/17), and CCF-1717712 (9/17 – 8/20); by equipment grants from IBM and Oracle (Sun), and by financial support from Oracle, Intel, Microsoft, IBM, and Google.

People

Principal Investigator

• Michael L. Scott
• in collaboration with Sandhya Dwarkadas
• and Chen Ding
• early work with John M. Mellor-Crummey

Graduate Students

• Spyridoula Gravani (Advised by John Criswell)
• H. Alan Beadle
• Mingzhe Du

Alumni

Ph.D.

• Maged Michael (Long at IBM and Meta; now at Monad Labs)
• Leonidas Kontothanassis (Now at Boston University)
• Bob Wisniewski (Advised by Chris Brown; long at IBM and Intel; now at Samsung)
• Galen Hunt (Now at Microsoft Research)
• Srinivasan Parthasarathy (Advised by Sandhya Dwarkadas; now at the Ohio State University)
• Bill Scherer (Now at HPE, Houston)
• Virendra Marathe (Now at Oracle Labs)
• Mike Spear (Now on faculty at Lehigh University)
• Gökçen Kestor (supervised by Osman Unsal, Adrian Cristal, and Mateo Valero at UPC; now at PNNL)
• Hemayet Hossain (Advised by Sandhya Dwarkadas; now at NVIDIA)
• Arrvindh Shriraman (Advised by Sandhya Dwarkadas; now at Simon Fraser University)
• Luke D'Alessandro (Now at Indiana University)
• Li Lu (Now at Meta)
• Lingxiang Xiang (Now at Intel Santa Clara)
• Joe Izraelevitz (Now on faculty at the University of Colorado–Boulder)
• Ryan Yates (Now at Groq)
• Haosen Wen (Now at Huawei Canada)
• Wentao Cai (Now at Nvidia)

M.S.

• Bijun He (Now at Google)
• Mohammad Hedayati-Goudarzi (Co-advised with Kai Shen; Now at Google)
• Louis Jenkins

B.S.

• Athul Acharya
• Eric Bluestein
• David Eisenstat
• Matthew Graichen
• Julian Herwitz
• Chris Heriot
• Jake Pershing
• Corey Proscia
• Aaron Rolett
• Kyle Sabo
• Michael Silverman 
• Andrew Sveikauskas 
• Nicholas Wrem
• Matthew Graichen
• Chris Kjellqvist
• Jack Yu
• Beakal Lemeneh

Postdocs and visiting scholars

• Roberto Gioiosa (now at PNNL)
• Weixing Ji (now back at BIT)
• Hammurabi Mendes (now at Davidson College)

Pseudocode 

• Scalable spinlocks and barriers. Includes test-and-set and ticket locks; queue locks; and centralized, tree-based, and fft-style (“butterfly”) barriers. From the 1991 TOCS paper, with later additions due to (a) Craig, Landin, and Hagersten, and (b) Auslander, Edelsohn, Krieger, Rosenburg, and Wisniewski.
• Scalable busy-wait reader-writer locks. Includes reader-preference, writer-preference, and fair locks. From the 1991 PPoPP paper.
• Scalable adaptive combining tree barriers. Combine local-only spinning, logarithmic critical paths, amortization of overhead for skewed arrival, and “fuzziness”. From the 1994 IJPP paper.
• Variations on Lamport’s fast mutual exclusion lock. Use no atomic instructions other than read and write. From UR TR 460 (1993).
• Preemption-safe and scheduler-conscious synchronization algorithms. Includes two queue-based mutual exclusion locks; test-and-set and ticket locks; a fair, scalable, queue-based reader-writer lock; competitive and optimal-time small-scale barriers; and a scalable barrier. All algorithms avoid busy-waiting for action by preempted processes, including those waiting in line for a FIFO queue or ticket lock. Most employ a widened kernel-user interface. From the 1997 TOCS paper.
• A highly-concurrent multi-lock concurrent priority queue. Uses bottom-up insertions and “bit-reversal” choice among fringe nodes. From the 1996 IPL paper.
• Fast concurrent queue algorithms. We believe these algorithms to be the best concurrent queues available, for almost any application. The lock-free queue has been adopted by the java.util.concurrent package of JSR 166, incorporated into the standard Java library as of JDK 1.5.0. From the 1996 PODC and 1998 JPDC papers.
• Timeout-capable queue-based locks
  • Scalable Queue-Based Spin Locks with Timeout. Combine fairness and scalability (from queueing and local-only spinning) with the ability to time out and abandon an attempt to acquire a lock. Make it safe to use queue-based locks in user-level code without OS modifications. From the 2001 PPoPP paper.
  • Non-Blocking Timeout in Scalable Queue-Based Spin Locks. Improve upon the PPoPP 2001 results by making timeout a nonblocking operation, at the expense of worst-case (but extremely unlikely) unbounded space requirements. Guaranteed to complete in a bounded number of time steps even in the face of preemption of other threads. From the 2002 PODC paper.
  • Non-Blocking Timeout in a NUMA-Aware Queue-Based Lock. Settles, in the affirmative, an open question posed (in Feb. 2000) by Mike O’Donnell and colleagues at Mercury Computer Systems: namely, whether it is possible to build a fair, contention-free, timeout-capable lock on a non-cache-coherent machine without a universal atomic primitive (e.g. compare-and-swap or load-linked/store-conditional).
  • Time-Published Queue-Based Spin Locks. Combine fairness, scalability, timeout, and preemption tolerance. Make it feasible, for the first time, to use queue-based spin locks on multiprogrammed systems with a standard kernel interface. To accompany the 2005 HiPC paper.
• Lock-free dualstack and dualqueue. Nonblocking data structures that can hold either data or reservations. Pop and dequeue operations spin if no data is available. While spinning they cause no contention. Furthermore, pending requests are guaranteed to be fulfilled in LIFO (for the dualstack) or FIFO (for the dualqueue) order. From the 2004 DISC paper.
• Generic dual structures and fast dual queues.  From "Generality and Speed in Nonblocking Dual Containers,"ACM TOPC, March 2017.  These (1) allow any nonblocking container for data to be paired with almost any nonblocking container for requests, and (2) leverage the LCRQ of Morrison & Afek to provide very high throughput on machines with fetch-and-increment.

Legacy Executables

• Basic and scalable spinlocks and barriers. Code to run on the Sequent Symmetry, BBN Butterfly 1, and BBN TC2000.
• Scalable busy-wait reader-writer locks. Code to run on the BBN TC2000.
• Scalable adaptive combining tree barriers. Code to run on the BBN Butterfly 1, BBN TC2000, and Kendall Square KSR 1
• Variations on Lamport’s fast mutual exclusion lock. Code to run on the Silicon Graphics Iris.
• Preemption-safe and scheduler-conscious synchronization algorithms. Code to run on the Kendall Square KSR 1 and Silicon Graphics Challenge.
• A highly-concurrent multi-lock concurrent priority queue. Code to run on the SGI Challenge.
• Fast concurrent queue algorithms. Includes SGI Challenge code for our two-lock and nonblocking queues, and for previous algorithms by other researchers.
• Queue-Based Spin Locks with Timeout. Code to run on a multiprocessor (V9) Sun.
• Non-Blocking Timeout in Queue-Based Spin Locks. Code to run on a multiprocessor (V9) Sun.
• Fair and unfair versions of the SynchronousQueue class, implemented with our dual data structure methodology. Java source code; added to the standard library as of Java 6.
• The Reconfigurable Software Transactional Memory System. Fast, nonblocking memory transactions for C++ pthreads programs.
• Generic dual structures and fast dual queues.  From "Generality and Speed in Nonblocking Dual Containers," ACM TOPC, March 2017.