一句话：提出树时钟替代向量时钟计算并发执行的因果序，使 join/copy 代价与修改条目数成正比，并证明其在 happens-before 下的渐进最优性。
动态并发分析通常关注单次程序执行来检测错误，其中关键一步是定义事件间的因果序，而经典做法是用向量时钟存储各线程的逻辑时间。向量时钟的 join 与 copy 操作需 Θ(k) 时间（k 为线程数），线程多时成为计算瓶颈。本文提出树时钟这一新数据结构来替代向量时钟，其 join 与 copy 的时间大致正比于实际被修改的条目数，从而避免每次应用的 Θ(k) 固有开销。作者证明：在计算经典 happens-before（HB）偏序时树时钟是渐进最优的，即不存在能带来更小渐进运行时间的数据结构；并展示树时钟还可计算 schedulable-happens-before（SHB）与标准 Mazurkiewicz（MAZ）等偏序，因而具有通用性。实验表明，仅将向量时钟替换为树时钟，即可在基准上平均获得 MAZ 2.02 倍、SHB 2.66 倍、HB 2.97 倍的加速，显示其有望成为并发分析中的标准数据结构。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{0001PT022,
title = {A tree clock data structure for causal orderings in concurrent executions},
author = {Umang Mathur and Andreas Pavlogiannis and Hünkar Can Tunç and Mahesh Viswanathan},
booktitle = {ASPLOS},
year = {2022},
doi = {10.1145/3503222.3507734}
}