A Survey on Parallelism and Determinism
Open Access
- 2 February 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 55 (10) , 1-28
Abstract
Parallelism is often required for performance. In these situations an excess of non-determinism is harmful as it means the program can have several different behaviours or even different results. Even in domains such as high-performance computing where parallelism is crucial for performance, the computed value should be deterministic. Unfortunately, non-determinism in programs also allows dynamic scheduling of tasks, reacting to the first task that succeeds, cancelling tasks that cannot lead to a result, and so on. Non-determinism is thus both a desired asset or an undesired property depending on the situation. In practice, it is often necessary to limit non-determinism and to identify precisely the sources of non-determinism to control what parts of a program are deterministic or not. This survey takes the perspective of programming languages, and studies how programming models can ensure the determinism of parallel programs. This survey studies not only deterministic languages but also programming models that prevent one particularly demanding source of non-determinism: data races. Our objective is to compare existing solutions to the following questions: How programming languages can help programmers write programs that run in a parallel manner without visible non-determinism? What programming paradigms ensure this kind of properties? We study these questions and discuss the merits and limitations of different approaches.Keywords
All Related Versions
Funding Information
- French ANR CODAS (ANR-17-CE23-0004-01)
This publication has 93 references indexed in Scilit:
- Integrating discrete controller synthesis into a reactive programming language compilerDiscrete Event Dynamic Systems, 2013
- Scala Actors: Unifying thread-based and event-based programmingTheoretical Computer Science, 2009
- An Asynchronous Communication Model for Distributed Concurrent ObjectsSoftware and Systems Modeling, 2006
- Book review: Term Rewriting and all that by Franz Baader and Tobias Nipkow (Cambridge Univ . Press, 313 pages)ACM SIGACT News, 2000
- Models and languages for parallel computationACM Computing Surveys, 1998
- OpenMP: an industry standard API for shared-memory programmingIEEE Computational Science and Engineering, 1998
- Uniqueness type inferenceLecture Notes in Computer Science, 1995
- Some efficient solutions to the affine scheduling problem. Part II. Multidimensional timeInternational Journal of Parallel Programming, 1992
- MULTILISP: a language for concurrent symbolic computationACM Transactions on Programming Languages and Systems, 1985
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967