CSE Seminar

Practical Statically-checked Deterministic Parallelism

Ryan NewtonAssistant ProfessorIndiana University

Reproducibility is important in computing, whether reproducing bug reports or
scientific results. After obvious sources of irreproducibility are addressed by
containerization and hermetic build systems, a fundamental remaining challenge
is preventing unintended nondeterminism due to parallelism and concurrency.

In this talk I present languages and libraries that provide strict deterministic
parallelism by construction. Starting with a foundation that disallows writable
shared memory between parallel computations, we add support for structured
communication patterns that preserve the determinism guarantee, irrespective of
the underlying architecture, thread count, and nondeterministic scheduling.
Building an application with these patterns also clarifies its structure and
supports formal reasoning about effect composition.

While the constraint of determinism may seem harsh, in this talk I argue that
the future is bright: we can already build programs mixing lock-free concurrent
data structures, blocking data-flow, callbacks, and GPU-based data-parallelism,
without ever compromising determinism or referential transparency.

Ryan Newton received his Ph.D. in computer science from MIT in 2009, advised by
Arvind and Samuel Madden. His thesis introduced techniques for efficiently
distributing a single logical program over a sensor network. From 2009 through
2011, Ryan was an engineer in the developer products division at Intel, where he
worked on parallel programming tools, including Cilk and CnC. Since 2011, Ryan
leads a group of programming languages researchers interested in increasing the
safety and parallel performance of high-level, declarative programs.

Sponsored by