A tree clock data structure for causal orderings in concurrent executions
A tree clock data structure for causal orderings in concurrent executions
复制标题
DOI：
10.1145/3503222.3507734
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Umang Mathur;Andreas Pavlogiannis;Hunkar Can Tuncc;Mahesh Viswanathan
中科院分区：
文献类型：
--
作者：
Umang Mathur;Andreas Pavlogiannis;Hunkar Can Tuncc;Mahesh Viswanathan
动态技术是分析并发程序的一种可扩展和有效的方法。这些技术不是分析程序的所有行为，而是通过关注单个程序执行来检测错误。通常，这些技术中的关键步骤是定义执行中事件之间的因果顺序，然后使用向量时钟（一种存储线程逻辑时间的简单数据结构）计算。向量时钟的两个基本操作，即连接和复制，需要Θ（k）时间，其中k是线程的数量。因此，当k很大时，它们是计算瓶颈。在这项工作中，我们引入树时钟，一种新的数据结构，取代向量时钟计算因果排序程序执行。连接和复制树时钟花费的时间大致与被修改的条目的数量成比例，因此这两个操作不会遭受每个应用的先验Θ（k）成本。我们表明，当用于计算经典的发生之前（HB）的偏序，树时钟是最佳的，在这个意义上说，没有其他的数据结构可以导致更小的渐近运行时间。此外，我们证明了树时钟可以用来计算其他偏序，如可重复发生之前（SHB）和标准Mazurkiewicz（MAZ）偏序，因此是一个通用的数据结构。我们的实验表明，仅仅通过将向量时钟替换为树时钟，每个基准测试的计算速度平均从2.02倍（MAZ）提高到2.66倍（SHB）和2.97倍（HB）。这些结果表明，树时钟有潜力成为一个标准的数据结构，在并发分析中具有广泛的应用。
Dynamic techniques are a scalable and effective way to analyze concurrent programs. Instead of analyzing all behaviors of a program, these techniques detect errors by focusing on a single program execution. Often a crucial step in these techniques is to define a causal ordering between events in the execution, which is then computed using vector clocks, a simple data structure that stores logical times of threads. The two basic operations of vector clocks, namely join and copy, require Θ(k) time, where k is the number of threads. Thus they are a computational bottleneck when k is large. In this work, we introduce tree clocks, a new data structure that replaces vector clocks for computing causal orderings in program executions. Joining and copying tree clocks takes time that is roughly proportional to the number of entries being modified, and hence the two operations do not suffer the a-priori Θ(k) cost per application. We show that when used to compute the classic happens-before (HB) partial order, tree clocks are optimal, in the sense that no other data structure can lead to smaller asymptotic running time. Moreover, we demonstrate that tree clocks can be used to compute other partial orders, such as schedulable-happens-before (SHB) and the standard Mazurkiewicz (MAZ) partial order, and thus are a versatile data structure. Our experiments show that just by replacing vector clocks with tree clocks, the computation becomes from 2.02 × faster (MAZ) to 2.66 × (SHB) and 2.97 × (HB) on average per benchmark. These results illustrate that tree clocks have the potential to become a standard data structure with wide applications in concurrent analyses.