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:

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

Graduate Students

Alumni

Ph.D.

M.S.

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

Postdocs and visiting scholars

Pseudocode 

Legacy Executables