PPoPP 2019
Sat 16 - Wed 20 February 2019 Washington, DC, United States
Wed 20 Feb 2019 10:25 - 10:50 at Salon 12/13 - Session 9: Synchronization Chair(s): Erez Petrank

This paper addresses the problem of provably efficient and practically good on-the-fly determinacy race detection in task parallel programs that use futures. Prior works on determinacy race detection have mostly focused on either task parallel programs that follow a series-parallel dependence structure or ones with unrestricted use of futures that generate arbitrary dependences. In this work, we consider a restricted use of futures and show that we can detect races more efficiently than with general use of futures.

Specifically, we present two algorithms: \MultiBags and \MultiBagsPlus. \MultiBags targets programs that use futures in a restricted fashion and runs in time $O(T_1 \alpha(m,n))$, where $T_1$ is the sequential running time of the program, $\alpha$ is the inverse Ackermann’s function, $m$ is the total number of memory accesses, $n$ is the dynamic count of places at which parallelism is created. Since $\alpha$ is a very slowly growing function (upper bounded by $4$ for all practical purposes), it can be treated as a close-to-constant overhead. \MultiBagsPlus is an extension of \MultiBags that target programs with general use of futures. It runs in time $O((T_1+k^2)\alpha(m,n))$ where $T_1$, $\alpha$, $m$ and $n$ are defined as before, and $k$ is the number of future operations in the computation. We implemented both algorithms and empirically demonstrate their efficiency.

#### Wed 20 FebDisplayed time zone: Guadalajara, Mexico City, Monterrey change

 09:35 - 10:50 Session 9: SynchronizationMain Conference at Salon 12/13 Chair(s): Erez Petrank Technion 09:3525mTalk Encapsulated Open Nesting for STM: Fine-Grained Higher-Level Conflict DetectionMain ConferenceMartin Bättig Department of Computer Science, ETH Zurich, Thomas Gross ETH Zurich DOI 10:0025mTalk A Specialized B-Tree for Concurrent Datalog EvaluationMain ConferenceHerbert Jordan University of Innsbruck, Pavle Subotic University College London, David Zhao The University of Sydney, Bernhard Scholz University of Sydney, Australia DOI 10:2525mTalk Efficient Race Detection with FuturesMain ConferenceRobert Utterback Monmouth College, Kunal Agrawal Washington University in St. Louis, Jeremy Fineman , I-Ting Angelina Lee Washington University in St. Louis DOI