[發明專利]并行程序的數據競爭檢測方法、裝置及多核處理系統

有效

• 申請號: 201310400690.5
• 申請日: 2013-09-05
• 公開（公告）號: CN103488563B
• 公開（公告）日: 2017-04-12
• 發明（設計）人: 李磊;陳云霽;孫國慶
• 申請（專利權）人: 龍芯中科技術有限公司
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06F9/46
• 代理公司: 北京同立鈞成知識產權代理有限公司11205
• 代理人: 孟金喆

技術領域

本發明涉及處理器芯片技術，尤其涉及一種并行程序的數據競爭檢測方法、裝置及多核處理系統。

背景技術

隨著多核處理器的發展，需要更好的并行程序來獲取由多核帶來的性能提升。然而，由于并行程序執行結果的不確定性，調試并行程序有著極大的難度。在并行程序的眾多類型的漏洞（bug）中，數據競爭（data?race）是在實際并行程序中最常見的一種。

對于來自不同線程的一對訪存操作，如果它們訪問的地址相同，而且其中至少有一個是寫操作，那么就稱這對操作為一對沖突操作。如果一對沖突操作的執行過程之間沒有同步操作把它們隔開，那么就認為產生一個數據競爭。數據競爭在大多數情況下都認為是一個漏洞，因為它給程序的執行帶來了不確定性。

為了檢測程序里面存在的數據競爭，目前已有的方法可以分為靜態檢測和動態檢測兩種。靜態檢測方法靜態的分析整個并行程序，根據并行程序靜態的構造可能的執行圖，并判斷執行圖中的沖突操作是否被同步操作隔開。雖然靜態檢測方法可以找到所有可能的數據競爭，但是當并行程序規模變大時，靜態檢測方法不可避免的碰到狀態爆炸的問題，使得靜態分析無法進行。此外，靜態檢測方法需要推測并行程序可能的執行路徑，對于含有指針的程序，還要推測訪存操作的訪問地址。因此，所有的靜態檢測方法都有很多的誤報，即很多本來不是數據競爭的沖突操作被認為是數據競爭，極大的影響了檢測的準確性。

與靜態檢測方法不同的是，動態檢測方法通過記錄并分析并行程序一次具體的執行來檢測數據競爭。由于動態方法只用分析一次特定的執行，所以程序的執行流是可以知道的，也不會碰到狀態爆炸的問題。但是，檢測結果過于依賴并行程序的執行。對于一個有數據競爭的并行程序，可能只在很少的執行中才能把數據競爭暴露出來，一旦在某一次執行中沒有暴露出來，已有的動態檢測方法就會檢測不到該數據競爭。并且，一個并行程序可能的執行種數跟指令數是指數關系的，即使重復執行了同一個程序數萬次，也只能覆蓋并行程序中極少一部分的執行種數。在對并行程序進行測試的過程中，即使同一個程序數萬次的執行都沒有數據競爭，我們也無法斷定該并行程序是沒有數據競爭的。

綜上所述，現有技術中的方法在檢測數據競爭中都有著明顯的缺點：靜態檢測方法檢測過程中可能碰到狀態爆炸的問題、誤報率高；現有的動態檢測方法可能漏檢并行程序中存在的數據競爭。

發明內容

本發明提供一種并行程序的數據競爭檢測方法、裝置及多核處理系統，用于解決現有技術中數據競爭檢測方法誤報和漏檢的缺陷。

第一方面，本發明提供一種并行程序的數據競爭檢測方法，在調用多核處理器中的一處理器核執行并行程序的指令之后，還包括：

鎖訪問信息記錄流程：記錄所述處理器核的當前指令的鎖訪問信息，其中，所述鎖訪問信息與鎖操作的鎖地址對應記錄；

訪存信息記錄流程：記錄所述處理器核的當前指令的訪存信息；以及

數據競爭判斷流程：根據所述鎖訪問信息記錄流程記錄的鎖訪問信息以及所述訪存信息記錄流程記錄的訪存信息，判斷存在沖突的兩個指令之間是否存在數據競爭。

結合第一方面，在第一方面的第一種可能的實現方式中，所述數據競爭判斷流程具體包括：

根據記錄的各條指令的訪存信息，判斷指令間是否滿足程序序關系，如果兩條指令在處理器核上被執行，則兩條指令滿足程序序關系；

根據記錄的所述鎖訪問信息，判斷所述鎖操作間是否滿足可行同步序關系，其中，對應于同一地址的先后執行的第一鎖操作以及第二鎖操作，若在所述第一鎖操作的鎖獲取操作以及鎖釋放操作之間存在一個寫操作，使得所述第二鎖操作的鎖獲取和鎖釋放之間存在對與所述寫操作為同一地址的沖突讀操作，則所述鎖操作間滿足可行同步序關系；

當檢測出存在沖突的兩個指令時，判斷存在沖突的兩個指令是否滿足可行序關系；如果兩個指令之間不滿足可行序關系，則確定所述第一鎖操作和所述第二鎖操作間存在數據競爭，其中，所述可行序關系為：若存在沖突的兩條指令之間存在一串指令操作，這一串操作之間至少滿足程序序關系和可行同步序關系之一。

結合第一方面的第一種可能的實現方式，在第一方面的第二種可能的實現方式中，在所述數據競爭判斷流程之前，還包括：

根據記錄的各處理器核的各條指令的訪存信息，判斷當前指令的訪問地址與所述多核處理器中其它處理器核的各條指令的訪問地址是否相同；

如果是，則判斷所述當前指令與具有相同訪問地址的指令中是否存在寫操作；