Search Results

Documents authored by Yu, Lechen

Document
DOI: 10.4230/LIPIcs.ECOOP.2023.13
Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises

Authors: Feiyang Jin, Lechen Yu, Tiago Cogumbreiro, Jun Shirako, and Vivek Sarkar

Published in: LIPIcs, Volume 263, 37th European Conference on Object-Oriented Programming (ECOOP 2023)

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.
Cite as

Feiyang Jin, Lechen Yu, Tiago Cogumbreiro, Jun Shirako, and Vivek Sarkar. Dynamic Determinacy Race Detection for Task-Parallel Programs with Promises. In 37th European Conference on Object-Oriented Programming (ECOOP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 263, pp. 13:1-13:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ECOOP.2023.13},
  URN =		{urn:nbn:de:0030-drops-182060},
  doi =		{10.4230/LIPIcs.ECOOP.2023.13},
  annote =	{Keywords: Race detection, Promise, Determinism, Determinacy-race, Serial projection}
}
Document
Artifact
DOI: 10.4230/DARTS.9.2.24
Determinacy Race Detector for Promises (Artifact)

Authors: Feiyang Jin and Lechen Yu

Published in: DARTS, Volume 9, Issue 2, Special Issue of the 37th European Conference on Object-Oriented Programming (ECOOP 2023)

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. We have introduced a dynamic data race detector, DRDP, to help examine task-parallelism programs with promises. DRDP is designed for the HCLIB parallel programming model and capable of pinpointing data races in a HCLIB program. In this artifact, we provide the race detector implementation and all benchmarks to help reproduce the reported results in the paper.
Cite as

Feiyang Jin and Lechen Yu. Determinacy Race Detector for Promises (Artifact). In Special Issue of the 37th European Conference on Object-Oriented Programming (ECOOP 2023). Dagstuhl Artifacts Series (DARTS), Volume 9, Issue 2, pp. 24:1-24:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{jin_et_al:DARTS.9.2.24,
  author =	{Jin, Feiyang and Yu, Lechen},
  title =	{{Determinacy Race Detector for Promises (Artifact)}},
  pages =	{24:1--24:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2023},
  volume =	{9},
  number =	{2},
  editor =	{Jin, Feiyang and Yu, Lechen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.9.2.24},
  URN =		{urn:nbn:de:0030-drops-182649},
  doi =		{10.4230/DARTS.9.2.24},
  annote =	{Keywords: Race detection, Promise, Determinism, Determinacy-race}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact