Open access
Author
Date
2019-09-23Type
- Doctoral Thesis
ETH Bibliography
yes
Altmetrics
Abstract
Deterministic parallel programming models are a beacon of hope in the stormy, concurrency-bug-ridden seas of parallel programming. These models guarantee that any parallel execution of a program produces the same results as a sequential execution, implying the absence of any kind of concurrency bugs. However, most existing deterministic models rely on compile-time techniques and on complex program annotations to achieve this goal. While such an approach ensures high performance, it negatively affects the simplicity of a language, making it unsuitable for non-expert programmers.
This dissertation explores a relatively uncharted area in the design space of parallel programming models and presents an approach that is deterministic, but relies primarily on runtime checking to guarantee this property. In this programming model, every object plays a role in every concurrent task, for example, the readwrite role or the readonly role. When an object is shared with a new task, it adapts to the new sharing pattern by changing its roles and therefore its behavior, namely, by changing the set of permitted operations that can be performed with this object. This mechanism can be leveraged to prevent interfering accesses from concurrently executing tasks and makes parallel execution deterministic.
To this end, the dissertation presents a role-based programming language that includes several novel concepts (role transitions, guarding, slicing) to enable practical deterministic parallel programming. Unlike previous deterministic languages, this language can express a variety of parallel patterns without relying on complex language constructs or rigorous restrictions.
A prototype implementation demonstrates that this dynamic approach yields high performance for a range of programs, despite the overhead that stems from the necessary runtime checks. In particular, the implementations of 8 widely used programming problems achieve substantial parallel speedups, as a result of a combination of optimizations specifically tailored towards this programming model.
In summary, this dissertation demonstrates that deterministic parallel programming can be realized with a dynamic instead of a static approach, yielding vastly different—and much simpler—language designs. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000404823Publication status
publishedExternal links
Search print copy at ETH Library
Publisher
ETH ZurichSubject
Determinism; Parallel computing; Parallel programming; Concurrency; Language Design and Implementation; Programming languagesOrganisational unit
03422 - Gross, Thomas (emeritus) / Gross, Thomas (emeritus)
More
Show all metadata
ETH Bibliography
yes
Altmetrics