High-Performance Synchronization
Computer Science Department
University of Rochester
Rochester, NY 14627-0226
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), and
CSR-0720796 (9/07 – 8/10);
by equipment grants
from IBM and Sun; and by financial support from Sun, Intel, and
Microsoft.
NEW: Announcing
Release 5 of the
Rochester Software
Transactional Memory System for C++ pthreads programs. Download
your copy today!
With the coming 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 current work is focused on
(7) software transactional memory, including conflict detection,
contention management, privatization, workload-adaptive algorithms,
language mechanisms, and hardware acceleration.
- Principal Investigator
Michael L. Scott
<
>
585-275-7745
in collaboration with
Sandhya Dwarkadas
<
>
585-275-5647
and
Chen Ding
<
>
585-275-1373
early work with
John M. Mellor-Crummey
<
>
- Graduate Students
- Undergraduate Students
- Alumni
- Ph.D.
- M.S.
- Bijun He
(Now at Google’s Boston lab)
- B.S.
- Athul Acharya
(Now in the Ph.D. program at Purdue University)
- David Eisenstat
- Chris Heriot
- Corey Proscia
- Aaron Rolett
- Michael Silverman (Now in the MFA program in Interactive Media at USC)
- Andrew Sveikauskas
- Nicholas Wrem
-
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 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.
Last Change:
04 October 2009 /
