Design Frontiers in Parallel Languages: The Role of Determinism

Event details

  • When: 12th June 2014 14:00 - 15:00
  • Where: Cole 1.33a
  • Series: School Seminar Series
  • Format: Seminar

Constraints can be a source of inspiration; their role in creative art forms is well-recognized, with poetry as the quintessential example.  We argue that the requirement of determinism can play the same role in the design of parallel programming languages. This talk describes a series of design explorations that begin with determinism as the constraint, introduce the concept of monotonically-changing concurrent data structures (LVars), and end in some interesting places—flirting with the boundaries to yield quasideterminism, and revealing synergies between parallel effects, such as cancelation and memoization, when used in a deterministic context.

Our goal is for guaranteed-deterministic parallel programming to be practical and efficient for a wide range of applications. One challenge is simply to integrate the known forms of deterministic-by-construction parallelism, which we overview in this talk: Kahn process networks, pure data-parallelism, single assignment languages, functional programming, and type-effect systems that enforce limited access to state by threads. My group, together with many others around the world, are developing libraries such as LVish and Accelerate that add these capabilities to the programming language Haskell. It is early days yet, but already possible to build programs that mix concurrent, lock-free data structures, blocking data-flow, callbacks, and GPU-based data-parallelism, without ever compromising determinism or referential transparency.