TY - GEN
T1 - A Tree Clock Data Structure for Causal Orderings in Concurrent Executions
AU - Mathur, Umang
AU - Pavlogiannis, Andreas
AU - Tunc, Hunkar Can
AU - Viswanathan, Mahesh
N1 - Publisher Copyright:
© 2022 ACM.
PY - 2022/2
Y1 - 2022/2
N2 - 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.
AB - 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.
KW - concurrency
KW - dynamic analyses
KW - happens-before
KW - vector clocks
UR - http://www.scopus.com/inward/record.url?scp=85126392847&partnerID=8YFLogxK
U2 - 10.1145/3503222.3507734
DO - 10.1145/3503222.3507734
M3 - Article in proceedings
AN - SCOPUS:85126392847
T3 - ASPLOS: Architectural Support for Programming Languages and Operating Systems, Proceedings
SP - 710
EP - 725
BT - ASPLOS 2022 - Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems
A2 - Falsafi, Babak
A2 - Ferdman, Michael
A2 - Lu, Shan
A2 - Wenisch, Thomas F.
PB - Association for Computing Machinery
T2 - 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2022
Y2 - 28 February 2022 through 4 March 2022
ER -