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.

M.S.

B.S.

Postdocs and visiting scholars

Pseudocode 

Executable Code