Entry Date:
January 25, 2017

Run-Time Support for Scalable Concurrent Programming

Principal Investigator Nir Shavit

Project Start Date September 2016

Project End Date
 August 2019


Highly-concurrent data structures lie at the heart of modern multicore software. This project will provide systematic run-time system support for several techniques that that have proved essential for constructing highly-concurrent data structures. The intellectual merits are to provide a new basis for thinking about how to scale future generations of both hardware and software, and in particular to develop novel uses of operating system kernel functionality, as well as transactional hardware and software techniques. The project's broader significance and importance is the benefit to society provided by higher performing, less expensive, and more reliable software.

The specific techniques addressed are unsynchronized traversals, in which a thread navigates through a linked data structure without writing to memory, and atomic sequences of memory operations, where race conditions are eliminated by making a sequence of individual memory operations appear to take place instantaneously. Although these techniques have been successfully deployed in many ad-hoc instances, they have never been packaged as general-purpose mechanisms because they can have complex and dangerous interactions with standard memory management schemes. This project will exploit recent developments in hardware architectures and operating system structures to develop automated, systematic run-time support, making these techniques accessible to non-specialists.