Data race detection on compressed traces
Data race detection on compressed traces
复制标题
压缩痕迹上的数据竞争检测
DOI：
10.1145/3236024.3236025
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Mahesh Viswanathan
中科院分区：
文献类型：
--
作者：
Dileep Kini;Umang Mathur;Mahesh Viswanathan
我们认为，已被压缩使用直线程序（SLP），这是特殊的上下文无关的语法，正好生成一个字符串，即跟踪，他们所代表的程序痕迹检测数据竞赛的问题。我们考虑两种经典的方法来进行竞争检测-使用happens-before关系和锁集规则。我们提出了这两种方法的算法，运行的时间是线性的压缩，SLP表示的大小。典型的程序执行几乎总是表现出导致显著压缩的模式。因此，我们的算法预计会导致大的加速比相比，分析未压缩的痕迹。我们对这些新算法在标准基准上的实验评估证实了这一观察结果。
We consider the problem of detecting data races in program traces that have been compressed using straight line programs (SLP), which are special context-free grammars that generate exactly one string, namely the trace that they represent. We consider two classical approaches to race detection --- using the happens-before relation and the lockset discipline. We present algorithms for both these methods that run in time that is linear in the size of the compressed, SLP representation. Typical program executions almost always exhibit patterns that lead to significant compression. Thus, our algorithms are expected to result in large speedups when compared with analyzing the uncompressed trace. Our experimental evaluation of these new algorithms on standard benchmarks confirms this observation.