Big-Tent Deterministic Parallelism

  • Ryan R. Newton, Indiana University, USA

Nondeterminism is essential for achieving flexible parallelism: it allows tasks to be scheduled onto cores dynamically, in response to the vagaries of an execution. But if schedule nondeterminism is observable within a program, it becomes much more difficult for programmers to discover and correct bugs by testing, let alone to reason about their programs in the first place. While much work has focused on identifying methods of deterministic parallel programming, guaranteed determinism in real parallel programs remains a lofty and rarely achieved goal. It places stringent constraints on the programming model: concurrent tasks must communicate in restricted ways that prevent them from observing the effects of scheduling, a restriction that must be enforced at the language or runtime level.
This talk will overview the known forms of deterministic-by-construction parallel languages, including: Kahn process networks, pure data-parallelism, single assignment languages, functional programming, and type-effect systems that enforce limited access to state by threads. However, I will argue that existing approaches remain fragmented and under-exploited, and that an effort is called for both to extend the scope of deterministic approaches and to better integrate known approaches. The ultimate target is a full-featured programming environment that enables a practical form of guaranteed-deterministic parallelism not possible today.

I will present our recent work in this area. We have extended Haskell’s Par monad with arbitrary monotonic data structures called LVars. These go beyond single-assignment and include any shared data structures to which information is added but never removed. Specifically, each LVar is associated with a lattice from which its states are drawn; writes become join operations; and reads block on a monotonic threshold functions, preventing observation of the order in which information is added. I will describe a prototype implementation of this model called LVish, and will describe both its facilities for task-parallelism with monotonic shared data, and its ability to support other idioms: for example, parallel in-place update of array locations via a monad-transformer we call VecParT.
Haskell provides an attractive environment for implementing such approaches, because deterministic parallelism constructs can be presented as dischargable effects, and used within ordinary (non-IO) purely functional code. The result is that parallel programming mechanisms can be arbitrarily composed. For example, LVish programs can internally execute GPU code with Accelerate, or use threaded array parallelism with REPA, or do in-place parallel array computations with a VecParT transformer, all while modifying and reading monotonic data structures, and all while retaining a full guarantee of determinism.


Ryan R. Newton grew up in South Florida and received his Ph.D. in computer science from MIT in 2009.  From 2009 through 2011, he was a research scientist at Intel Corporation. In 2011 he joined Indiana University, where his research focuses on language-based approaches to the programming challenges posed by future architectures — ranging from embedded sensor nodes to heterogeneous parallel processors and clusters.  His projects employ novel compilation techniques and domain-specific language designs.  With this approach he has made contributions to the areas of: sensor network programming, stream processing, parallel runtime systems, and automatic program partitioning and distribution.

Language Design, in Theory and Practice

  • Tim Harris, Oracle Labs, Cambridge, UK

The end of the “free lunch” of rising CPU clock rates has led to a resurgence of interest in techniques for parallel programming. Some techniques are well established, coming from fields such as databases and high-performance computing. Other techniques are more recent, such as programming models that target GPUs, or that build on the emerging transactional memory systems. To be effective, many emerging techniques require changes at multiple layers of the stack: a hardware component, support in the operating system, and changes to the language runtime system in addition to the evolution of the language itself.

A common theme is that the role of hardware is becoming more significant. This setting creates new challenges for the programming languages community: how do we reconcile the need for portable programs and well-defined languages with the ability to use specialized hardware where it is available.

I will talk about my experience trying to tackle instances of these problems, and I will try to identify some lessons learned. I will focus on three examples. First, transactional memory, and the tensions that exist between specifying simple language constructs, enabling “transactionalization” of existing code, and enabling efficient implementations in hardware and software. Second, the message passing abstractions exposed by the Barrelfish research OS, and the tension between providing well-defined semantics, while being able to build over diverse forms of communication stack. Finally, I will talk about my current work on supporting multiple parallel applications together on the same machine, and how previous work has influenced the design choices there.


Tim Harris  has recently joined Oracle Labs in Cambridge, UK. His research interests span multiple layers of the stack. He is particularly interested in parallel programming, OS / runtime-system interaction, and opportunities for specialized architecture support for particular workloads. Prior to Oracle, His recent projects have included language support for asynchronous message passing in the Barrelfish research OS, and ideas for architecture support for parts of language runtime systems (e.g., synchronization and GC). Harris has also worked extensively on transactional memory (TM), most recently on applying ideas learnt from STM systems to designing an abstraction for low-cost multi-word atomic updates for use in building shared-memory data structures. He was on the faculty of the University of Cambridge, and completed a PhD on providing application programmers with safe control over low-level features of the JVM (dynamic complication, object placement, thread scheduling).