Available for download: Release 7 of the Reconfigurable Software Transactional Memory System for C++ pthreads programs.
With the recent 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.
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), and CCR-0963759 (7/10 – 6/14); by equipment grants from IBM and Oracle (Sun), and by financial support from Oracle, Intel, and Microsoft.
-
Principal Investigator
-
-
Graduate Students
-
-
Ph.D. Alumni
-
-
Maged Michael (Now at IBM’s T. J. Watson Research Center)
-
Leonidas Kontothanassis (Now at Google Boston)
-
Bob Wisniewski (Advised by Chris Brown; now at IBM’s T. J. Watson Research Center)
-
Galen Hunt (Now at Microsoft Research)
-
Srinivasan Parthasarathy (Advised by Sandhya Dwarkadas; now at the Ohio State University)
-
Bill Scherer (Now at Rice University)
-
Virendra Marathe (Now at Sun Microsystems Laboratories)
-
Mike Spear (Now at Lehigh University)
-
Hemayet Hossain (Advised by Sandhya Dwardadas; now at NVIDIA)
-
Arrvindh Shriraman (Advised by Sandhya Dwarkadas; now at Simor Fraser University)
-
M.S. Alumni
-
-
Bijun He (Now at Google Boston)
-
B.S. Alumni
-
-
Athul Acharya
-
Eric Bluestein
-
David Eisenstat
-
Chris Heriot
-
Jake Pershing
-
Corey Proscia
-
Aaron Rolett
-
Kyle Sabo
-
Michael Silverman
-
Andrew Sveikauskas
-
Nicholas Wrem
-
Julian Herwitz
-
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-swapor 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.
Popand dequeueoperations spin if no data is avaialble. 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.