PPoPP 2021
Sat 27 February - Wed 3 March 2021
Wed 3 Mar 2021 11:25 - 11:40 - Session 9. Tasks, Threads, and Fault Tolerance Chair(s): Pascal Felber

Task-parallel programs often enjoy deadlock freedom under certain restrictions, such as the use of structured join operations, as in Cilk and X10, or the use of asynchronous task futures together with deadlock-avoiding policies such as Known Joins or Transitive Joins. However, the \emph{promise}, a popular synchronization primitive for parallel tasks, does not enjoy deadlock-freedom guarantees. Promises can exhibit deadlock-like bugs; however, the concept of a deadlock is not currently well-defined for promises.

To address these challenges, we propose an ownership semantics in which each promise is associated to the task which currently intends to fulfill it. Ownership immediately enables the identification of bugs in which a task fails to fulfill a promise for which it is responsible. Ownership further enables the discussion of deadlock cycles among tasks and promises and allows us to introduce a robust definition of deadlock-like bugs for promises.

Cycle detection in this context is non-trivial because it is concurrent with changes in promise ownership. We provide a lock-free algorithm for precise runtime deadlock detection. We show how to obtain the memory consistency criteria required for the correctness of our algorithm under TSO and the Java and C++ memory models. An evaluation compares the execution time and memory usage overheads of our detection algorithm on benchmark programs relative to an unverified baseline. Our detector exhibits a 12% (1.12$\times$) geometric mean time overhead and a 6% (1.06$\times$) geometric mean memory overhead, which are smaller overheads than in past approaches to deadlock cycle detection.

#### Wed 3 MarDisplayed time zone: Eastern Time (US & Canada) change

 11:10 - 12:10 Session 9. Tasks, Threads, and Fault ToleranceMain Conference Chair(s): Pascal Felber University of Neuchâtel 11:1015mTalk Advanced Synchronization Techniques for Task-based Runtime SystemsMain ConferenceDavid Álvarez Barcelona Supercomputing Center, Kevin Sala Barcelona Supercomputing Center, Marcos Maroñas Barcelona Supercomputing Center, Aleix Roca Barcelona Supercomputing Center, Vicenç Beltran Barcelona Supercomputing Center Link to publication 11:2515mTalk An Ownership Policy and Deadlock Detector for PromisesMain ConferenceCaleb Voss Georgia Institute of Technology, Vivek Sarkar Georgia Institute of Technology Link to publication 11:4015mTalk Understanding a Program's Resiliency Through Error PropagationMain Conferencezhimin li , Harshitha Menon Lawrence Livermore National Laboratory, Kathryn Mohror Lawrence Livermore National Laboratory, Peer-Timo Bremer Lawrence Livermore National Laboratory, Yarden Livant University of Utah, Valerio Pascucci University of Utah Link to publication 11:5515mTalk Lightweight Preemptive User-Level ThreadsMain ConferenceShumpei Shiina The University of Tokyo, Shintaro Iwasaki Argonne National Laboratory, Kenjiro Taura The University of Tokyo, Pavan Balaji Argonne National Laboratory Link to publication