Workspace Consistency: A Programming Model for Shared Memory Parallelism

Amittai Aviram, Bryan Ford, and Yu Zhang
Yale University

2nd Workshop on Determinism and Correctness in Parallel Programming (WoDet 11),
March 6, 2011, Newport Beach, California, USA

Abstract

Recent interest in deterministic parallelism has yielded new deterministic programming languages, which offer promising features but require rewriting existing code, and deterministic schedulers, which emulate existing thread APIs but do not eliminate races from the basic programming model. Workspace consistency (WC) is a new synchronization and memory consistency model that offers a “naturally deterministic,” race-free programming model that can be adopted in both new or existing languages. WC's basic semantics are inspired by—and intended to be as easily understood as&mdsah;the “parallel assignment” construct in sequential languages such as Perl and JavaScript, where concurrent threads always read their inputs before writing shared outputs. Prototype implementations of a restricted form of WC already exist, supporting only strictly hierarchical fork/join-style synchronization, but this paper develops and explores the model in more detail and extends it to support non-hierarchical synchronization patterns such as producer/consumer pipelines and futures.

Paper: PDF • Slides: OpenOffice, PDF

This research is sponsored by the National Science Foundation under grant CNS-1017206.