基于可行序的数据竞争检测
发布时间：2019-05-26 22:43
【摘要】：为了在并行程序的单次执行中找到更多的数据竞争,提出了用可行序关系替代传统的"happens-before"序关系来动态地实现数据竞争预测的算法。该算法认为:从技术上讲,如果在观测到的执行轨迹中,两个临界区之间没有可行序的关系,那么这两个临界区的顺序可以被颠倒以构造出其他的执行轨迹;通过判断可行序关系来分析这些构造出来的执行轨迹,就可以找到单次执行中未暴露出来的可能的数据竞争;所有构造出来的执行轨迹中的数据竞争,可以在O(an)的时间内全部检测出来,其中n为程序中所有访存操作的个数,a为每个共享地址上的最大锁集合数。在Java Grande测试程序集上的实验结果说明,上述算法可以找到其他动态检测数据竞争的方法找不到的数据竞争,而且算法时间也完全符合理论上的O(an)时间复杂度。
[Abstract]:In order to find more data competition in the single execution of parallel programs, an algorithm to dynamically realize data competition prediction by replacing the traditional "happens-before" order relation with feasible order relation is proposed. The algorithm holds that: technically, if there is no feasible sequence relationship between the two critical regions in the observed execution trajectory, then the order of the two critical regions can be reversed to construct other execution trajectories. By judging the feasible order relation to analyze the execution trajectories of these constructs, we can find the possible data competition that is not exposed in a single execution. All the data competition in the constructed execution trajectory can be detected in the time of O (an), where n is the number of all memory access operations in the program and a is the maximum number of lock sets on each shared address. The experimental results on the Java Grande test assembly show that the above algorithm can find the data competition that can not be found by other dynamic detection methods, and the algorithm time is completely in line with the theoretical O (an) time complexity.
【作者单位】： 计算机体系结构国家重点实验室;中国科学院计算技术研究所;中国科学院大学;龙芯中科技术有限公司;
【基金】：国家“核高基”科技重大专项课题(2009ZX01028-002-003,2009ZX01029-001-003,2010ZX01036-001-002,2012ZX01029-001-002-002) 国家自然科学基金(61221062,61100163,61133004,61173001,61232009,61222204) 863计划(2012AA010901,2012AA011002,2012AA012202,2013AA014301)资助项目
【分类号】：TP332
，
本文编号：2485691
[Abstract]:In order to find more data competition in the single execution of parallel programs, an algorithm to dynamically realize data competition prediction by replacing the traditional "happens-before" order relation with feasible order relation is proposed. The algorithm holds that: technically, if there is no feasible sequence relationship between the two critical regions in the observed execution trajectory, then the order of the two critical regions can be reversed to construct other execution trajectories. By judging the feasible order relation to analyze the execution trajectories of these constructs, we can find the possible data competition that is not exposed in a single execution. All the data competition in the constructed execution trajectory can be detected in the time of O (an), where n is the number of all memory access operations in the program and a is the maximum number of lock sets on each shared address. The experimental results on the Java Grande test assembly show that the above algorithm can find the data competition that can not be found by other dynamic detection methods, and the algorithm time is completely in line with the theoretical O (an) time complexity.
【作者单位】： 计算机体系结构国家重点实验室;中国科学院计算技术研究所;中国科学院大学;龙芯中科技术有限公司;
【基金】：国家“核高基”科技重大专项课题(2009ZX01028-002-003,2009ZX01029-001-003,2010ZX01036-001-002,2012ZX01029-001-002-002) 国家自然科学基金(61221062,61100163,61133004,61173001,61232009,61222204) 863计划(2012AA010901,2012AA011002,2012AA012202,2013AA014301)资助项目
【分类号】：TP332
，
本文编号：2485691
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2485691.html
