Skip to main content

Research

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, and transactional memory.

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

Publications

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.

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), and CCF-1422649 (9/14 – 8/17); 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.

  • 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 Intel)
  • Galen Hunt (Now at Microsoft Research)
  • Srinivasan Parthasarathy (Advised by Sandhya Dwarkadas; now at the Ohio State University)
  • Bill Scherer (Now at HP, Houston)
  • Virendra Marathe (Now at Oracle Labs)
  • Mike Spear (Now at Lehigh University)
  • Gökçen Kestor (supervised by Osman Unsal, Adrian Cristal, and Mateo Valero at UPC; now at PNNL)
  • Hemayet Hossain (Advised by Sandhya Dwarkadas; now at NVIDIA)
  • Arrvindh Shriraman (Advised by Sandhya Dwarkadas; now at Simon Fraser University)
  • Luke Dalessandro (Now at Indiana University)
  • Li Lu (Now at Hortonworks)
  • Lingxiang Xiang (Now at Intel Santa Clara)

M.S.

  • Bijun He (Now at Google Boston)

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

Postdocs and visiting scholars

Pseudocode 

Executable Code