High-Performance Synchronization for Shared-Memory Parallel Programs

Available for download:  Release 7 of the Reconfigurable Software Transactional Memory System for C++ pthreads programs.


 

Overview

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. 

People

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

Pseudocode

Executable Code