Abstract | ||
---|---|---|
A program is said to have a determinacy race if logically parallel parts of a program access the same memory location and one of the accesses is a write. These races are generally bugs in the program since they lead to non-deterministic program behavior --- different schedules of the program can lead to different results. Most prior work on detecting these races focuses on a subclass of programs with series-parallel or nested parallelism.
This paper presents a race-detection algorithm for detecting races in a more general class of programs, namely programs that include arbitrary ordering constraints in additional to the series-parallel constructs. The algorithm performs a serial execution of the program, augmented to detect races, in O(T1 + k2) time, where T1 is the sequential running time of the original program and k is the number of non series-parallel constraints.
The main technical novelty of this paper is a new data structure, R-Sketch, for answering reachability queries in nearly series-parallel (SP) directed acyclic graphs (DAGs). Given as input a graph comprising an n-node series parallel graph and k additional non-SP edges, the total construction time of the data structure is O(n + k2), and each reachability query can be answered in O(1) time. The data structure is traversally incremental, meaning that it supports the insertion of nodes/edges, but only as they are discovered through a graph traversal.
|
Year | DOI | Venue |
---|---|---|
2018 | 10.5555/3174304.3175277 | SODA '18: Symposium on Discrete Algorithms
New Orleans
Louisiana
January, 2018 |
Field | DocType | ISBN |
Data structure,Generating function,Discrete mathematics,Graph traversal,Computer science,Series-parallel graph,Theoretical computer science,Reachability,Directed acyclic graph,Schedule,Series and parallel circuits | Conference | 978-1-61197-503-1 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kunal Agrawal | 1 | 687 | 50.08 |
Joseph Devietti | 2 | 9 | 2.79 |
Jeremy T. Fineman | 3 | 587 | 36.10 |
I-Ting Angelina Lee | 4 | 123 | 12.17 |
robert utterback | 5 | 16 | 1.92 |
Changming Xu | 6 | 1 | 0.35 |