科研之友
微信
新浪微博
Facebook
分享链接
摘要
为了在并行程序的单次执行中找到更多的数据竞争,提出了用可行序关系替代传统的"happens-before"序关系来动态地实现数据竞争预测的算法。该算法认为:从技术上讲,如果在观测到的执行轨迹中,两个临界区之间没有可行序的关系,那么这两个临界区的顺序可以被颠倒以构造出其他的执行轨迹;通过判断可行序关系来分析这些构造出来的执行轨迹,就可以找到单次执行中未暴露出来的可能的数据竞争;所有构造出来的执行轨迹中的数据竞争,可以在O(an)的时间内全部检测出来,其中n为程序中所有访存操作的个数,a为每个共享地址上的最大锁集合数。在Java Grande测试程序集上的实验结果说明,上述算法可以找到其他动态检测数据竞争的方法找不到的数据竞争,而且算法时间也完全符合理论上的O(an)时间复杂度。
-
单位中国科学院计算技术研究所; 计算机体系结构国家重点实验室; 中国科学院大学
