Skip to main navigation Skip to search Skip to main content

Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises

  • Georgia Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original languageEnglish
Title of host publication37th European Conference on Object-Oriented Programming, ECOOP 2023
EditorsKarim Ali, Guido Salvaneschi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772815
DOIs
StatePublished - Jul 2023
Event37th European Conference on Object-Oriented Programming, ECOOP 2023 - Seattle, United States
Duration: Jul 17 2023 → Jul 21 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume263
ISSN (Print)1868-8969

Conference

Conference37th European Conference on Object-Oriented Programming, ECOOP 2023
Country/TerritoryUnited States
CitySeattle
Period7/17/23 → 7/21/23

ASJC Scopus Subject Areas

  • Software

Keywords

  • Determinacy-race
  • Determinism
  • Promise
  • Race detection
  • Serial projection

Fingerprint

Dive into the research topics of 'Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises'. Together they form a unique fingerprint.

Cite this