Race detection and reachability in nearly series-parallel DAGs
Race detection and reachability in nearly series-parallel DAGs
复制标题
近串联并行 DAG 中的竞争检测和可达性
DOI：
10.1137/1.9781611975031.11
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Xu, Changming
中科院分区：
文献类型：
--
作者：
Agrawal, Kunal;Devietti, Joseph;Fineman, Jeremy T.;Lee, I-Ting Angelina;Utterback, Robert;Xu, Changming
如果程序的逻辑并行部分访问相同的内存位置，并且其中一个访问是写操作，则称程序具有确定性竞争。这些竞争通常是程序中的错误，因为它们会导致不确定的程序行为——程序的不同调度可能导致不同的结果。大多数先前检测这些竞争的工作集中在具有串行并行或嵌套并行的程序的子类上。本文提出了一种竞赛检测算法，用于检测更一般的一类程序中的竞赛，即除了串并联结构之外还包括任意顺序约束的程序。该算法对程序进行串行执行，增强以检测赛跑，inO（T1+k2）时间，其中et1为原始程序的串行运行时间，表示非串并联约束的数量。本文的主要技术创新是一种新的数据结构R-Sketch，用于回答近串联并行（SP）有向无环图（dag）中的可达性查询。给定一个由无节点串联并行图和额外的k条非sp边组成的图作为输入，数据结构的总构建时间为isO(n+k2)，每个可达性查询可回答时间为inO(1)。数据结构是横向增量的，这意味着它支持节点/边的插入，但只有当它们是通过图遍历发现的。
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, inO(T1+k2) time, whereT1is the sequential running time of the original program andkis 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 ann-node series parallel graph andkadditional non-SP edges, the total construction time of the data structure isO(n+k2), and each reachability query can be answered inO(1) time. The data structure istraversally incremental, meaning that it supports the insertion of nodes/edges, but only as they are discovered through a graph traversal.