Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs
Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs
复制标题
已证明良好且实用高效的 Fork-Join 程序并行竞争检测
DOI：
10.1145/2935764.2935801
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Lee, I-Ting Angelina
中科院分区：
文献类型：
--
作者：
Utterback, Robert;Agrawal, Kunal;Fineman, Jeremy T.;Lee, I-Ting Angelina
如果一个并行程序具有确定性竞争，不同的调度会导致内存访问观察到不同的值-各种竞争检测工具已经被设计用来发现这样的错误。竞争检测器的一个关键组件是用于串并行（SP）维护的算法，该算法识别两个访问在逻辑上是否并行。本文描述了一种渐进最优算法，称为WSP-Order，用于在具有fork-join（或嵌套）并行性的程序中执行SP维护。给定一个工作时间为T1，跨度为T∞的fork-join程序，WSP-Order在P个处理器上执行该程序，同时保持SP关系，时间复杂度为O（T1/P + T∞），是渐近最优的. WSP-Order的核心是一个专为SP维护而设计的工作窃取调度器。我们还在Cilk Plus运行时系统中实现了一个基于WSP-Order的竞争检测器C-RACER，并在五个基准测试中评估了其性能。实验结果表明，当运行顺序，它执行几乎以及以前最好的顺序竞争检测器。更重要的是，当并行运行时，它实现了几乎与没有竞争检测的原始程序一样多的加速。
If a parallel program has determinacy race(s), different schedules can result in memory accesses that observe different values --- various race-detection tools have been designed to find such bugs. A key component of race detectors is an algorithm for series-parallel (SP) maintenance, which identifies whether two accesses are logically parallel. This paper describes an asymptotically optimal algorithm, called WSP-Order, for performing SP maintenance in programs with fork-join (or nested) parallelism. Given a fork-join program with T1work and T∞span, WSP-Order executes it while also maintaining SP relationships in O(T1/P + T∞) time on P processors, which is asymptotically optimal. At the heart of WSP-Order is a work-stealing scheduler designed specifically for SP maintenance.We also implemented C-RACER, a race-detector based on WSP-Order within the Cilk Plus runtime system, and evaluated its performance on five benchmarks. Empirical results demonstrate that when run sequentially, it performs almost as well as previous best sequential race detectors. More importantly, when run in parallel, it achieves almost as much speedup as the original program without race-detection.
登录
查看更多内容
并发计算：实践 2005；00:1–7 使用 cpeauth.cls 编写 [版本：2002/09/19 v2.02]
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
Y. Zhou;P. Laybourn;J. Magill;Richard M. De La Rue
通讯作者：
Richard M. De La Rue
Cilkprof 可扩展性分析器
DOI：
--
发表时间：
2015
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
T. Schardl;Bradley C. Kuszmaul;I. Lee;W. Leiserson;C. Leiserson
通讯作者：
C. Leiserson
动态维护 fork-join 多线程程序中的串并关系
DOI：
10.1145/1007912.1007933
发表时间：
2004
期刊：
2012 Design, Automation & Test in Europe Conference & Exhibition (DATE)
影响因子：
--
作者：
M. A. Bender;Jeremy T. Fineman;Seth Gilbert;C. Leiserson
通讯作者：
C. Leiserson
针对异步完成并行性的高效数据竞争检测
影响因子：
0.8
作者：
Raghavan Raman;Jisheng Zhao;Vivek Sarkar;Martin T. Vechev;Eran Yahav
通讯作者：
Eran Yahav
DOI：
10.1145/2594291.2594300
发表时间：
2014
期刊：
Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Li Lu;Weixing Ji;M. Scott
通讯作者：
M. Scott