基于可行序的数据竞争检测

摘要：

为了在并行程序的单次执行中找到更多的数据竞争，提出了用可行序关系替代传统的“happens before”序关系来动态地实现数据竞争预测的算法。该算法认为：从技术上讲，如果在观测到的执行轨迹中，两个临界区之间没有可行序的关系，那么这两个临界区的顺序可以被颠倒以构造出其他的执行轨迹；通过判断可行序关系来分析这些构造出来的执行轨迹，就可以找到单次执行中未暴露出来的可能的数据竞争；所有构造出来的执行轨迹中的数据竞争，可以在O(an)的时间内全部检测出来，其中n为程序中所有访存操作的个数，a为每个共享地址上的最大锁集合数。在Java Grande测试程序集上的实验结果说明，上述算法可以找到其他动态检测数据竞争的方法找不到的数据竞争，而且算法时间也完全符合理论上的O(an)时间复杂度。

关键词：数据竞争、并行程序调试、发生前(HB)、可行序

分类号：TP3;TN9

资助基金：国家“核高基”科技重大专项课题2009ZX01028002003，2009ZX01029001003，2010ZX01036001002，2012ZX01029001002002;国家自然科学基金61221062，61100163，61133004，61173001，61232009，61222204;863计划2012AA010901，2012AA011002，2012AA012202，2013AA014301资助项目。

在线出版日期：2014-12-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：669-676