School of Informatics and Computing

Technical Report TR702:
A Lattice-Theoretical Approach to Deterministic Parallelism with Shared State

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:

• PDF (551 KBytes)

There is help available if you want further information about the available file formats and software to display and print these files.