Technical Report TR702:
A Lattice-Theoretical Approach to Deterministic Parallelism with Shared State
Lindsey Kuper, Ryan Newton
(Oct 2012), Pages 60 pages
- Abstract:
-
We present a new model for deterministic-by-construction parallel programming that generalizes existing single-assignment models to allow multiple assignments that are monotonically increasing with respect to a user-specified partial order. Our model achieves determinism by using a novel shared data structure with an API that allows only monotonic writes and "threshold" reads that block until a lower bound is reached. We give a proof of determinism for our model, discuss ways to express existing deterministic parallel models using it, and describe how to extend it to support a limited form of nondeterminism that admits failures but never wrong answers.
- Available as:
-
