Freeze after writing: quasi-deterministic parallel programming with LVars

Lindsey Kuper, Aaron Turon, Neelakantan R. Krishnaswami, Ryan R. Newton

Research output: Contribution to journalConference articlepeer-review

23 Citations (Scopus)

Abstract

Deterministic-by-construction parallel programming models offer the advantages of parallel speedup while avoiding the nondeterministic, hard-to-reproduce bugs that plague fully concurrent code. A principled approach to deterministic-by-construction parallel programming with shared state is offered by LVars: shared memory locations whose semantics are defined in terms of an applicationspecific lattice. Writes to an LVar take the least upper bound of the old and new values with respect to the lattice, while reads from an LVar can observe only that its contents have crossed a specified threshold in the lattice. Although it guarantees determinism, this interface is quite limited. We extend LVars in two ways. First, we add the ability to freeze and then read the contents of an LVar directly. Second, we add the ability to attach event handlers to an LVar, triggering a callback when the LVar's value changes. Together, handlers and freezing enable an expressive and useful style of parallel programming. We prove that in a language where communication takes place through these extended LVars, programs are at worst quasideterministic: on every run, they either produce the same answer or raise an error. We demonstrate the viability of our approach by implementing a library for Haskell supporting a variety of LVarbased data structures, together with a case study that illustrates the programming model and yields promising parallel speedup.
Original languageEnglish
Pages (from-to)257-270
Number of pages14
JournalACM SIGPLAN Notices
Volume49
Issue number1
DOIs
Publication statusPublished - 13 Jan 2014
EventThe 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - California, San Diego, United States
Duration: 1 Jan 20141 Jan 2014

Keywords

  • Deterministic parallelism
  • Lattices
  • Quasi-determinism

Fingerprint

Dive into the research topics of 'Freeze after writing: quasi-deterministic parallel programming with LVars'. Together they form a unique fingerprint.

Cite this