【摘要】：為了在并行程序的單次執(zhí)行中找到更多的數(shù)據(jù)競爭,提出了用可行序關系替代傳統(tǒng)的"happens-before"序關系來動態(tài)地實現(xiàn)數(shù)據(jù)競爭預測的算法。該算法認為:從技術上講,如果在觀測到的執(zhí)行軌跡中,兩個臨界區(qū)之間沒有可行序的關系,那么這兩個臨界區(qū)的順序可以被顛倒以構造出其他的執(zhí)行軌跡;通過判斷可行序關系來分析這些構造出來的執(zhí)行軌跡,就可以找到單次執(zhí)行中未暴露出來的可能的數(shù)據(jù)競爭;所有構造出來的執(zhí)行軌跡中的數(shù)據(jù)競爭,可以在O(an)的時間內全部檢測出來,其中n為程序中所有訪存操作的個數(shù),a為每個共享地址上的最大鎖集合數(shù)。在Java Grande測試程序集上的實驗結果說明,上述算法可以找到其他動態(tài)檢測數(shù)據(jù)競爭的方法找不到的數(shù)據(jù)競爭,而且算法時間也完全符合理論上的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