Name
Abstract | ||
|---|---|---|
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 MultiBags+. MultiBags targets programs that use futures in a restricted fashion and runs in time O(T1α(m, n)), where T1 is the sequential running time of the program, α 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 α is a very slowly growing function (upper bounded by 4 for all practical purposes), it can be treated as a close-to-constant overhead. MultiBags+ is an extension of MultiBags that target programs with general use of futures. It runs in time O((T1 + k2)α(m, n)) where T1, α, 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.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3293883.3295732 | Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming |
Keywords | DocType | Volume |
determinacy race, dynamic program analysis, race detection, series-parallel maintenance | Conference | abs/1901.00622 |
ISBN | Citations | PageRank |
978-1-4503-6225-2 | 1 | 0.36 |
References | Authors | |
37 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| robert utterback | 1 | 16 | 1.92 |
| Kunal Agrawal | 2 | 687 | 50.08 |
| Jeremy T. Fineman | 3 | 587 | 36.10 |
| I-Ting Angelina Lee | 4 | 123 | 12.17 |