License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2023.13
URN: urn:nbn:de:0030-drops-182060
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18206/
Jin, Feiyang ;
Yu, Lechen ;
Cogumbreiro, Tiago ;
Shirako, Jun ;
Sarkar, Vivek
Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises
Abstract
Much of the past work on dynamic data-race and determinacy-race detection algorithms for task parallelism has focused on structured parallelism with fork-join constructs and, more recently, with future constructs. This paper addresses the problem of dynamic detection of data-races and determinacy-races in task-parallel programs with promises, which are more general than fork-join constructs and futures. The motivation for our work is twofold. First, promises have now become a mainstream synchronization construct, with their inclusion in multiple languages, including C++, JavaScript, and Java. Second, past work on dynamic data-race and determinacy-race detection for task-parallel programs does not apply to programs with promises, thereby identifying a vital need for this work.
This paper makes multiple contributions. First, we introduce a featherweight programming language that captures the semantics of task-parallel programs with promises and provides a basis for formally defining determinacy using our semantics. This definition subsumes functional determinacy (same output for same input) and structural determinacy (same computation graph for same input). The main theoretical result shows that the absence of data races is sufficient to guarantee determinacy with both properties. We are unaware of any prior work that established this result for task-parallel programs with promises. Next, we introduce a new Dynamic Race Detector for Promises that we call DRDP. DRDP is the first known race detection algorithm that executes a task-parallel program sequentially without requiring the serial-projection property; this is a critical requirement since programs with promises do not satisfy the serial-projection property in general. Finally, the paper includes experimental results obtained from an implementation of DRDP. The results show that, with some important optimizations introduced in our work, the space and time overheads of DRDP are comparable to those of more restrictive race detection algorithms from past work. To the best of our knowledge, DRDP is the first determinacy race detector for task-parallel programs with promises.
BibTeX - Entry
@InProceedings{jin_et_al:LIPIcs.ECOOP.2023.13,
author = {Jin, Feiyang and Yu, Lechen and Cogumbreiro, Tiago and Shirako, Jun and Sarkar, Vivek},
title = {{Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises}},
booktitle = {37th European Conference on Object-Oriented Programming (ECOOP 2023)},
pages = {13:1--13:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-281-5},
ISSN = {1868-8969},
year = {2023},
volume = {263},
editor = {Ali, Karim and Salvaneschi, Guido},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18206},
URN = {urn:nbn:de:0030-drops-182060},
doi = {10.4230/LIPIcs.ECOOP.2023.13},
annote = {Keywords: Race detection, Promise, Determinism, Determinacy-race, Serial projection}
}
|
Keywords: |
|
Race detection, Promise, Determinism, Determinacy-race, Serial projection |
|
Collection: |
|
37th European Conference on Object-Oriented Programming (ECOOP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
11.07.2023 |
|
Supplementary Material: |
|
Software (ECOOP 2023 Artifact Evaluation approved artifact): https://doi.org/10.4230/DARTS.9.2.24 |
