Efficient Access History for Race Detection
Efficient Access History for Race Detection
复制标题
用于种族检测的高效访问历史记录
DOI：
10.1145/3409964.3461825
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Schardl, Tao B.
中科院分区：
文献类型：
--
作者：
Xu, Yifan;Zhou, Anchengcheng;Yin, Grace Q.;Agrawal, Kunal;Lee, I-Ting Angelina;Schardl, Tao B.
虽然对任务并行程序的竞争检测算法进行了广泛的研究，但大多数研究都集中在优化特定组件，即可达性分析，它检查两条指令在逻辑上是否并行。很少有人关注另一个重要组件，即访问历史记录，它存储先前指令访问过的所有内存位置。理论上，访问历史组件不会增加渐近开销；然而，在实践中，它通常是竞争检测中最昂贵的组件，因为它在每次内存访问时都会被查询和（可能）更新。我们根据以下观察来优化该组件：通常，并行程序中的线程会访问连续的内存块。因此，我们不是以单个内存位置的粒度来维护访问历史记录，而是以这些（不同大小）间隔的粒度来维护它。为了启用此访问历史记录，我们提出（1）编译器和运行时机制，使我们能够有效地收集这些间隔，以及（2）基于树的访问历史数据结构，允许按间隔粒度进行更新和查询。假设间隔的数量与计算的总工作相比很小，生成的工具可以以摊销的恒定开销对分叉连接代码进行竞态检测。
While there has been extensive research on race-detection algorithms for task-parallel programs, most of this research has focused on optimizing a particular component, namely, reachability analysis, which checks whether two instructions are logically in parallel. Little attention has been paid to the other important component, the access history, which stores all memory locations previous instructions have accessed. In theory, the access-history component adds no asymptotic overhead; however, in practice, it is often the most expensive component of race detection since it is queried and (possibly) updated at each memory access. We optimize this component based on the observation that, typically, strands within parallel programs access contiguous blocks of memory. Therefore, instead of maintaining the access history at the granularity of individual memory locations, we maintain it at the granularity of these (varying size) intervals. To enable this access history, we propose (1) compiler and runtime mechanisms that allow us to efficiently collect these intervals and (2) a tree-based access-history data structure that allows updates and queries at interval granularity. The resulting tool can race-detect fork-join code with amortized constant overhead, assuming the number of intervals is small compared to the total work of the computation.
登录
查看更多内容
已证明良好且实用高效的 Fork-Join 程序并行竞争检测
DOI：
10.1145/2935764.2935801
发表时间：
2016
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Utterback, Robert;Agrawal, Kunal;Fineman, Jeremy T.;Lee, I-Ting Angelina
通讯作者：
Lee, I-Ting Angelina
DOI：
10.1145/3178487.3178515
发表时间：
2018-02
期刊：
Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Yifan Xu;I. Lee;Kunal Agrawal
通讯作者：
Yifan Xu;I. Lee;Kunal Agrawal
通过 future 进行高效种族检测
DOI：
10.1145/3293883.3295732
发表时间：
2019
期刊：
Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Utterback, Robert;Agrawal, Kunal;Fineman, Jeremy;Lee, I-Ting Angelina
通讯作者：
Lee, I-Ting Angelina
DOI：
--
发表时间：
1978
期刊：
影响因子：
--
作者：
Jacobo Valdes Ayesta
通讯作者：
Jacobo Valdes Ayesta
Umbra：高效且可扩展的内存阴影
DOI：
10.1145/1772954.1772960
发表时间：
2010
期刊：
2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)
影响因子：
--
作者：
Qin Zhao;Derek Bruening;Saman P. Amarasinghe
通讯作者：
Saman P. Amarasinghe