URCS logo

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

People

Principal Investigator
Michael L. Scott  <Michael Scott's email address>  585-275-7745
in collaboration with  Sandhya Dwarkadas  <Sandhya Dwarkadas's email address>  585-275-5647
                          and  Chen Ding  <Chen Ding's email address>  585-275-1373
early work with  John M. Mellor-Crummey  <John Mellor-Crummey's email address>
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

Publications

Pseudocode

Executable Code


Last Change: 01 October 2008 / Michael Scott's email address