论文标题
动态数据竞赛预测的复杂性
The Complexity of Dynamic Data Race Prediction
论文作者
论文摘要
众所周知，由于安排非确定性，编写并发程序很难。最常见的并发错误是数据竞赛，它们可以访问可以同时执行的共享资源。动态数据竞赛预测是检测数据竞赛的最标准技术：鉴于观察到的，无数据量的跟踪$ t $，其任务是确定是否可以将$ t $重新排序到trace $ t^*$暴露数据率的trace $ t^*$。尽管这个问题已在三十年中受到了极大的实际关注，但其复杂性仍然难以捉摸。在这项工作中，我们解决了这一问题，确定了问题可有效解决的难治性和条件的来源。鉴于$ k $ threads上的跟踪$ t $ $ n $，我们的主要结果如下。 首先，我们建立了一个常规$ O（K \ CDOT n^{2 \ cdot（k-1）}）$上限，以及当$ t $的某些参数是恒定的时，$ O（n^k）$上限是恒定的。此外，我们证明了问题是NP-HARD，甚至是W [1] hard通过$ K $进行了参数，因此不可能是固定参数可进行的。其次，我们研究了无环通信拓扑（例如服务器客户层层次结构）的问题。我们建立了一个$ o（k^2 \ cdot d \ cdot n^2 \ cdot \ log n）$上限，其中$ d $是$ t $中访问的共享变量的数量。此外，我们表明，即使对于$ k = 2 $螺纹的痕迹，问题也没有$ o（n^{2-ε}）$算法在正交矢量下。由于带有2个线程的任何迹线都定义了一个无环拓扑，因此我们的上限是最佳的WRT多项式改进，最多可在$ k $和$ d $的中等值。最后，我们研究了该问题的距离版本，该任务是通过类似于$ t $的证人跟踪来暴露数据竞赛。当$ t $的某些参数恒定时，我们开发了一种在$ o（n）$时间中起作用的算法。
Writing concurrent programs is notoriously hard due to scheduling non-determinism. The most common concurrency bugs are data races, which are accesses to a shared resource that can be executed concurrently. Dynamic data-race prediction is the most standard technique for detecting data races: given an observed, data-race-free trace $t$, the task is to determine whether $t$ can be reordered to a trace $t^*$ that exposes a data-race. Although the problem has received significant practical attention for over three decades, its complexity has remained elusive. In this work, we address this lacuna, identifying sources of intractability and conditions under which the problem is efficiently solvable. Given a trace $t$ of size $n$ over $k$ threads, our main results are as follows. First, we establish a general $O(k\cdot n^{2\cdot (k-1)})$ upper-bound, as well as an $O(n^k)$ upper-bound when certain parameters of $t$ are constant. In addition, we show that the problem is NP-hard and even W[1]-hard parameterized by $k$, and thus unlikely to be fixed-parameter tractable. Second, we study the problem over acyclic communication topologies, such as server-clients hierarchies. We establish an $O(k^2\cdot d\cdot n^2\cdot \log n)$ upper-bound, where $d$ is the number of shared variables accessed in $t$. In addition, we show that even for traces with $k=2$ threads, the problem has no $O(n^{2-ε})$ algorithm under Orthogonal Vectors. Since any trace with 2 threads defines an acyclic topology, our upper-bound for this case is optimal wrt polynomial improvements for up to moderate values of $k$ and $d$. Finally, we study a distance-bounded version of the problem, where the task is to expose a data race by a witness trace that is similar to $t$. We develop an algorithm that works in $O(n)$ time when certain parameters of $t$ are constant.
