基于滑動窗口的多核程序數據競爭硬件檢測算法

朱素霞，陳德運，季振洲，孫廣路

(1. 哈爾濱理工大學計算機科學與技術學院，黑龍江 哈爾濱 150080；2. 哈爾濱理工大學計算機科學與技術學院博士后流動站，黑龍江 哈爾濱 150080；3. 哈爾濱工業大學計算機科學與技術學院，黑龍江 哈爾濱 150001)

基于滑動窗口的多核程序數據競爭硬件檢測算法

朱素霞1,2，陳德運1,2，季振洲3，孫廣路1

(1. 哈爾濱理工大學計算機科學與技術學院，黑龍江 哈爾濱 150080；2. 哈爾濱理工大學計算機科學與技術學院博士后流動站，黑龍江 哈爾濱 150080；3. 哈爾濱工業大學計算機科學與技術學院，黑龍江 哈爾濱 150001)

數據競爭是引起多核程序發生并發錯誤的主要原因。針對現有基于硬件的happens-before數據競爭檢測方法硬件開銷大的問題，提出了一種輕量級的內存競爭硬件檢測算法，該算法利用滑動窗口技術動態檢測程序執行過程中發生的距離較近、更易引發并發錯誤的數據競爭。考慮競爭距離的大小，將并發線程片段細分為加鎖并發競爭域和包含線程近期執行序列的未加鎖并發競爭域，用一對交替移動的可重寫滑動窗口保存未加鎖并發競爭域內的內存操作指令，用一個大小可變的可重寫滑動窗口保存加鎖并發競爭域內的內存操作指令，當來自遠程的共享訪問與窗口內的內存訪問發生沖突時，檢測到數據競爭。在硬件實現結構中，僅為每個處理器核添加3對較小尺寸的硬件簽名寄存器來保存并發競爭域內的數據地址，無需更改原有的cache一致性協議，帶來的帶寬開銷低，能夠快速地檢測多核程序并發執行過程中發生的動態數據競爭，為多核程序開發和生產運行階段的并發錯誤診斷提供有效的指導信息。

數據競爭；滑動窗口；硬件簽名；并發錯誤；多核程序

1 引言

隨著多核處理器的廣泛應用，多核編程也變得越來越普遍。然而，多核程序執行時因為線程間共享內存訪問交互順序的不確定性，導致并發錯誤頻現，限制了多核程序的應用。多核程序運行時，當2個或多個線程并發訪問同一個共享變量，沒有采取正確的同步措施，并且至少有一個是寫操作時，就可能引起數據競爭。數據競爭是一種常見的并發錯誤，檢測數據競爭是多核程序開發、調試和診斷的重要手段，也是多核程序生產運行階段的重要分析手段。因此，研究者們提出了一系列的數據競爭檢測方法，有軟件實現的[1～7]，有硬件實現的[8～13]，也有軟硬結合的[14～16]，甚至還出現了商用的數據競爭檢測工具[17]。本文針對基于硬件的數據競爭動態檢測方法展開研究。

通常有2大類方法來檢測數據競爭，一種是基于鎖集合的，如文獻[1]；一種是基于happens-before關系的，如文獻[17]。基于鎖集合的方法是依據所有訪問同一個共享變量應該使用相同鎖的思想，跟蹤訪問共享變量的鎖集合，當2個訪問同一個共享變量使用的鎖集合的交集為空時，則認為存在數據競爭。Happens-before方法基于線程片段，每個處理器核使用一個邏輯時鐘來標記當前正在執行的線程片段，此外每個變量都有一個時戳記錄它在處理器訪問的哪個片段中，當另一個處理器訪問這個變量時，將變量的時戳同自身的時鐘進行比較，來決定這 2個相應的片段是否存在邏輯上的happens-before關系，還是存在邏輯上的重疊，如果存在邏輯上的重疊，則認為存在競爭。

軟件實現的數據競爭檢測算法通常會以 10～200倍降低程序運行的速度[10]，如此降速會影響程序運行的順序或競爭發生的時間，使生產運行時出現的數據競爭更是難以發現。因此，有研究者提出了基于硬件的數據競爭檢測方法。基于硬件的檢測方法對程序的性能影響較小，對發現程序生產運行時的數據競爭比較有效，然而它們往往添加較多的硬件資源。比如文獻[8]需要為cache塊添加額外的時戳或鎖信息，文獻[9]改變cache一致性協議狀態機，文獻[10]采用了基于硬件簽名的方式實現數據競爭的檢測，但需要添加簽名隊列，硬件開銷仍然過大，并且采用代價較高的回滾機制來定位競爭的位置。而且，大多數基于鎖集合和 happens-before的硬件檢測方法需要在現有的cache一致性協議基礎之上添加新的消息。然而，cache和一致性協議部件都是處理器的關鍵部件，如果需要增加過多硬件資源或更改cache，需要重新評估其對處理器性能的影響，不利于應用到實際中。雖然近期也有研究者提出的其他類型的數據競爭硬件檢測方法硬件的開銷較小[11～13]，但均只能檢測某特定類型的數據競爭。

本文針對現有基于happens-before數據競爭檢測方法硬件開銷大的問題，鑒于線程的并發執行是導致競爭發生的主要原因，結合競爭距離大小，將并發的線程片段細分為加鎖并發競爭域和未加鎖并發競爭域，提出了一種輕量級的動態數據競爭檢測方法。該方法基于在線數據流處理中常用的滑動窗口技術，保存線程近期執行的內存操作指令序列，動態地檢測競爭距離較近的、更易引發并發錯誤的數據競爭。該方法無需更改cache和一致性協議機構，僅添加少量的硬件簽名寄存器，帶來的帶寬開銷小。

本文的研究針對采用鎖同步方式的多核程序展開。

2 研究動機

數據競爭的檢測是NP困難問題，已往的數據競爭檢測方法大多旨在檢測盡可能多的數據競爭。然而，現實情況存在以下問題。

1) happens-before算法代價昂貴

基于happens-before的內存競爭檢測方法需要考慮所有的同步操作，還需要使用向量時鐘對不同線程中的內存訪問進行標記和排序，無論是已有的軟件實現方法還是硬件實現方法，都在內存或硬件開銷方面付出了較大代價。

2) 數據競爭是否會引起并發錯誤受距離影響

數據競爭是引發并發錯誤的主要原因，但并不是所有的數據競爭都會引發并發錯誤，尤其是那些競爭雙方距離較遠的數據競爭。因為距離較遠的數據競爭執行順序發生反轉的概率小，從而引發錯誤的可能性就小[10]。如圖1(a)所示，線程j訪問共享變量x后，線程i過了很久才訪問x，這2個訪問在時間上相隔很遠，雖然線程j未添加同步操作，但該數據競爭執行順序發生反轉是一個小概率事件，引起錯誤的概率小，在一定條件下，可以不予以檢測。

3) 糾正錯誤不一定要檢測出所有的數據競爭

檢測數據競爭可以有效地幫助多核程序的診斷和調試，然而，有時一個同步操作的錯誤使用或漏掉，可能會引發多個數據競爭，但只要檢測出其中的部分競爭，就可以幫助用戶找出同步錯誤的所在，從而修正程序。如圖1(b)所示，因線程j漏掉了一個同步操作，會引發①和②共2個數據競爭，而只要檢測到①這一個數據競爭就可以修復程序。

圖1 數據競爭示意

鑒于以上3點的分析，為了減小基于happensbefore的硬件數據競爭檢測方法帶來的硬件開銷，進一步降低檢測算法的復雜度，并且能給用戶或程序員提供診斷信息，尤其是提供生產運行階段的診斷信息，本文提出了一種輕量級的數據競爭檢測算法。該方法引入并發競爭域，用滑動窗口保存線程近期執行的內存操作，能夠檢測打斷臨界區操作的數據競爭和其他距離較近的數據競爭，對于距離較遠、不易引起并發錯誤的數據競爭不予檢測。

3 競爭距離

距離較遠的數據競爭因其執行順序發生反轉的概率小，引起錯誤的可能性小，因此，在進行數據競爭檢測時，可以更多地關注距離較近的數據競爭，從而為檢測并發錯誤提供更加有效的診斷信息。為了描述數據競爭雙方間的距離大小，本文提出競爭距離（race distance），并約定競爭距離表示：數據競爭的后發生方執行時，數據競爭的先發生方所在線程在執行完先發生方后又執行的內存操作指令數。如圖2所示，圓圈表示內存操作，線程i、j間存在數據競爭在線程j執行先發生方rd(x)后，直到線程i執行后發生方wr(x)時，線程j又執行了3條內存操作指令，稱該數據競爭的競爭距離(rl)為3。

圖2 競爭距離

針對競爭距離在多大的情況下，數據競爭執行順序發生反轉的概率小，可以不需要檢測的問題，本文對競爭距離和臨界區的關系及其大小進行了分析和測試。通常情況下，若有共享變量訪問，為避免發生競爭需要為其添加加鎖和解鎖操作。而且，臨界區不應太大，因為臨界區太大會降低程序的性能，這不是一種良好的編程習慣。如果某線程執行完加解鎖操作合圍的臨界區后，其他線程再來訪問由該臨界區保護的共享變量就不會引起競爭，否則很可能會引起競爭。同理，如果漏掉加解鎖操作，則在其原本應該有的臨界區范圍內有遠程訪問就可能會引發數據競爭，超出臨界區范圍則不會引起競爭。鑒于以上分析，可以發現數據競爭與臨界區的大小有一定關系：如果競爭距離大于臨界區，則發生數據競爭的可能性就變小。因此，競爭距離可以依據臨界區的大小為依據來設定。本文對測試負載進行了臨界區大小統計，詳見7.1節，并給出了本方案中合理的競爭距離范圍。

4 并發競爭域

基于 happens-before的數據競爭檢測方法通常將線程的執行序列依據同步操作劃分為一個個的線程片段，通過比較向量時戳，可以找到不存在happens-before關系、可能并發執行的線程片段，如圖3（中括號內給出了線程片段的向量時戳）所示的Si1和 Sj1、Si2和 Sj1、Si3和 Sj1、Si3和 Sj2、Si3和 Sj3均不存在happens-before關系，在程序執行過程中可能會發生數據競爭。因此，可以通過監測程序執行過程中并發執行的線程片段來監測動態的數據競爭。如圖3所示的執行順序中，并發的線程片段Si2和Sj1之間存在數據競爭并發的線程片段 Si3和 Sj1之間存在數據競爭和而且數據競爭的競爭距離較近，更易引發并發錯誤；并發的線程片段Si3和Sj2之間存在數據競爭

圖3 并發線程片段與數據競爭

為了降低happens-before算法的復雜度，本文結合上述分析僅檢測程序執行過程中并發線程片段間距離較近、更易引發并發錯誤的數據競爭，并把可能引起數據競爭的、近期訪問的一段線程片段稱為并發競爭域(CRR, concurrent race region)。根據線程片段是否由加解鎖操作合圍，將并發競爭域又細分為2大類：一類是加鎖并發競爭域，該域被加解鎖操作合圍起來，對應加鎖線程片段；另一類是未加鎖并發競爭域，該區域沒有被加解鎖操作包圍，是未加鎖線程片段的子集，僅包含未加鎖線程片段中近期訪問的指令執行序列。如圖4所示，線程i中存在一個加鎖并發競爭域CRRi，線程j中存在一個未加鎖并發競爭域CRRj，2個屬于并發執行的程序片段，因為都訪問了共享變量 x，因此存在數據競爭。為了能夠定位檢測到的數據競爭對應的內存地址，本文將來自遠程的共享訪問與并發競爭域中的訪問有沖突時，認定存在數據競爭，如圖 4中存在數據競爭

圖4 并發競爭域

引入并發競爭域，可以有效地檢測引發并發錯誤的2類主要競爭類型。一類是來自遠程并發競爭域的共享訪問與加鎖的并發競爭域內的訪問存在沖突，則對該地址的訪問存在競爭，這類競爭至少有一方進行了加解鎖保護，通常被稱為非對稱競爭[11]，如圖5(a)和圖5(b)所示。此類競爭打斷了臨界區操作，是程序執行中堅決不允許出現的，本文記該類競爭為LRace。另一類是來自遠程并發競爭域的共享訪問與未加鎖并發競爭域內的訪問發生沖突，則對該地址的訪問存在競爭，而且競爭距離越小，越容易引發并發錯誤。如圖5(c)和圖5(d)所示，本文記為 ULRace，該類中也存在打斷臨界區的情況，如圖5(d)所示。

圖5 檢測到的數據競爭類型

5 基于滑動窗口的動態數據競爭檢測

對于第1類數據競爭，因其先發生方位于臨界區內，而臨界區的執行是不能被打斷的，因此不管競爭距離遠近都要檢測。對于第2類數據競爭，因為其先發生方位于未加鎖并發競爭域內，遠距離的數據競爭可以不予考慮。因此對于這2類競爭的檢測方法要區別對待。下面分別給出2類競爭的檢測方法的具體描述。

5.1 未加鎖并發競爭域

針對未加鎖并發競爭域，為確保能夠保存近期訪問的執行序列，以便檢測到競爭距離較近的數據競爭，本文借鑒在線數據流處理中常用的滑動窗口技術，引入一對交替移動的可重寫滑動窗口：窗口1和窗口 2，用來存放未加鎖并發競爭域內的內存操作指令，每個窗口最多能夠容納有限數量個內存操作。隨著程序的執行，窗口可以不斷交替下移，線程內的執行序列便不斷加入到了滑動窗口中；當窗口1、窗口2都滿時，則清空并下移窗口1用來存放新的內存操作；再次全滿后，則清空并下移窗口2用來存放新的內存操作。

指令在滑動窗口中流動的過程如圖6所示，箭頭表示程序執行的順序，矩形框分別表示窗口1和窗口 2，2個窗口均只能存放有限數量的內存操作指令，未加粗實線矩形框表示工作窗口，加粗實線矩形表示已滿工作窗口，虛線矩形框表示已清空并下移的窗口，加粗虛線矩形框表示待工作窗口。具體流動過程描述如下。

初始情況下，窗口1在前，窗口2在后，內存操作指令依次加入到窗口1中，如圖6(a)所示。

當窗口1滿，則將后續內存操作指令依次加入到至窗口2中，如圖6(b)所示。

如果窗口1和窗口2全滿，則窗口1清空并下移，用來存放后續內存操作，此時窗口2在前，窗口1在后，如圖6(c)所示。

當窗口2、窗口1全滿，則窗口2清空并下移，用來存放后續內存操作指令，此時窗口1在前，窗口2在后，如圖6(d)所示。

圖6 指令在滑動窗口的流動示意

設每個窗口最多可容納m個內存操作，如此交替移動，便可存放線程最近執行的至少m個內存操作（初始情況除外）。這樣，如果來自其他線程的遠程訪問同滑動窗口內的內存操作發生沖突，則認為存在競爭。從而能夠檢測到所有競爭距離在0～m的數據競爭，還可以檢測部分m～2m的內存競爭，距離大于2m的不予以檢測。如此，通過一對滑動窗口的交替移動和重寫，有效地檢測到先發生方位于未加鎖并發競爭域、競爭距離較近的數據競爭。

該檢測方法中距離較遠的數據競爭不會被檢測到，如圖7中虛線指出的競爭。當該數據競爭后發生方執行時，線程i已經在執行完wr(x)后至少又執行了m個內存操作，因為此時窗口1、窗口2的前后順序已經交替移動過，位于前面的窗口是滿的。線程j的wr(x)操作距離線程i的wr(x)操作的距離大于 m，相對較遠。假設存在臨界區的話，wr(x)執行時，線程i的關于wr(x)的臨界區已經執行完畢，不會破壞線程i中wr(x)操作相關的臨界區。

圖7中可以檢測到線程i窗口1中的rd(x)與線程j的wr(x)之間的競爭。雖然該競爭距離大于m且接近 2m，但其仍在滑動窗口內，競爭的距離未超過2m，仍然能夠檢測到。

滑動窗口的大小決定了所能檢測到的數據競爭的距離，在后面的仿真測試中，本文給出了滑動窗口的合理尺寸。

圖7 未加鎖并發競爭域內的競爭示例

5.2 加鎖并發競爭域

臨界區的執行是不允許被打斷的，因此，如果臨界區內有來自其他線程的訪問沖突，則必引發競爭，此競爭必須要檢測到。因此，本文將加鎖競爭域內的內存操作指令用一個大小可擴展的滑動窗口來保存，該滑動窗口可以容納不同大小臨界區內的所有內存操作，窗口隨著臨界區內內存操作數量的增加而增大。一旦來自遠程線程的共享訪問與窗口內的訪問發生沖突，則檢測到了數據競爭。如圖8所示，線程j訪問執行wr(x)時，線程i還未執行完保護共享變量操作wr(x)的臨界區，則會檢測到數據競爭

6 硬件實現

基于上述滑動窗口的數據競爭檢測方法，實現了基于CMP（chip multiprocessor）系統的數據競爭硬件檢測算法。該檢測算法對應的硬件結構中需要為每個處理器核添加一個內存競爭檢測模塊RaceSW，如圖9所示。其中包括3對讀寫簽名寄存器：RF0/WF0、RF1/WF1、RF2/WF2。RF0/WF0和RF1/WF1這2對簽名分別用于存放未加鎖并發競爭域中滑動窗口1和窗口2存放的讀寫操作的數據地址，且每對讀寫簽名最多能存放m個內存操作的數據地址。RF2/WF2用來存放未加鎖并發競爭域中滑動窗口3存放的內存操作的數據地址，存放數量不限。當窗口1下移時，簽名對RF0/WF0清空，用來存放窗口1后續存放的內存操作的數據地址，當窗口2下移時，簽名對RF1/WF1清空，用來存放窗口 2后續存放的內存操作指令的數據地址。RF2/WF2用來存放加鎖并發競爭域中窗口3存放的內存操作的數據地址，并且存放的地址數量不受限制。在簽名寄存器大小固定的情況下，滑動窗口設置越大，能夠檢測到具有更大競爭距離的數據競爭，但因更多的地址加入到簽名寄存器中，帶來誤報也會增加。因此在第7節中對滑動窗口和簽名寄存器的大小進行了仿真測試，選取了合適的參數。

圖8 加鎖并發競爭域競爭示例

除了3對讀寫簽名寄存器外，RaceSW還包括指令計數器 IC，用來記錄窗口 1和窗口 2中的內存操作數量，以及一系列的標識觸發器：Order(窗口順序標識)、Full0（窗口 1滿標識）、Full1（窗口2滿標識）、Lock（加鎖標識）、Filter（過濾標識）。

同時，為了識別程序中的加鎖、解鎖操作，以及在檢測競爭時過濾掉鎖操作本身帶來的競爭，還需要為處理器增加新的機器指令。機器指令的實現形式多樣，可以為每個同步操作分別引入2條指令，一個是打開地址過濾功能，一個是關閉地址過濾功能；還可以綜合應用更少數量的機器指令來識別不同操作。鑒于盡可能引入較少的機器指令，降低硬件復雜度，該硬件實現中僅增加了 Lock_on、Lock_off、Filter_off 3個新的機器指令，如表1所示。這3條指令相當于硬件開關，Lock_on指令既能結束一個未加鎖并發競爭域又可以開啟一個新的加鎖并發競爭域，同時還開啟了鎖競爭過濾功能，即將鎖操作自身帶來的內存地址不添加到簽名中。Lock_off指令既能結束一個加鎖并發競爭域又可以開啟一個新的未加鎖并發競爭域，同時開啟鎖競爭過濾功能。Lock_on、Lock_off分別和Filter_off配合，可以對鎖操作實施過濾功能，不將它們加入到滑動窗口中，從而過濾掉鎖操作本身帶來的數據競爭，使數據競爭檢測的結果更加有意義。

表1 新增機器指令

雖然增加了 3條新的機器指令，但并不需修改用戶程序，只要修改庫函數即可。如表2所示，給出了針對 M4 macros[18]庫的修改。其中對于barrier操作，成對使用Lock_off和Filter_off，將其帶來的內存地址給過濾掉。而且，還可以靈活應用這幾條指令，將不想進行數據競爭檢測的區域過濾掉。

圖9 硬件實現結構

表2 對庫函數的修改

本文提出的基于滑動窗口的數據競爭檢測算法基于硬件的描述如下。它詳細描述了每個處理器核的動作。

該算法中每個處理器核做如下動作。

1) 每當處理器核執行內存操作指令時，首先判斷當前是處于未加鎖并發競爭域還是加鎖并發競爭域，如果是未加鎖并發競爭域，則將內存操作指令的數據地址按照滑動窗口1和窗口2的前后順序分別加入到窗口對應的簽名對中，如果是加鎖并發競爭域，則將內存操作指令的數據地址加入到滑動窗口3對應的簽名對中。

2) 根據滑動窗口1和窗口2的空滿狀況交替清空并移動對應的簽名對。

3) 如果遇到加解鎖操作，則清空窗口1和窗口2對應的簽名對。

4) 當收到來自其他處理器核的共享內存訪問請求時，處理器核查找簽名來檢測是否有數據競爭發生，若檢測到，則記錄競爭地址到競爭日志。

如果要區分檢測到的數據競爭屬于雙方均未加鎖、僅發生方加鎖、僅后發生方加鎖、雙方均未加鎖這4類中的哪一類，還需要在cache一致性協議發送gets或getx請求消息時添加該地址是否在加解鎖范圍內的標識信息。如此，程序員可以更加方便地查找錯誤和修改程序。

7 性能評價

本文采用 GEMS[19]對基于滑動窗口的數據競爭檢測算法進行了仿真，仿真配置如表3所示。測試負載選取典型的應用于多線程科學計算的SPLASH2[20]。

表3 仿真配置

下面給出該數據競爭檢測算法（RaceSW）在參數選取、硬件開銷、檢測性能和帶寬開銷方面的仿真結果。

7.1 參數選取

1) 滑動窗口

選取滑動窗口的大小決定了所能檢測到的內存競爭距離的大小。為了選取合適窗口，對臨界區內的內存操作數量進行了統計，結果如圖10所示。所有測試負載中，內存操作個數小于8的臨界區占的比例最大，比如 ocean、fft的臨界區均小于 8；小于256的臨界區約占為95%；大于512的臨界區占的比例非常少。雖然，cholesky、fmm中大于1 024的臨界區所占比例相對較多，但實際數量均不超過10個。

圖10 不同大小臨界區所占比例統計

滑動窗口如果設置過大，不易于去除距離較遠的數據競爭，而且會浪費硬件資源，如果過小則又會漏掉數據競爭。因此，本方案中，根據臨界區大小的結果統計，將未加鎖并發競爭域內引入的滑動窗口大小設置為 256，能夠包含占絕大多數的小于256的臨界區。如此，對于未加鎖并發競爭域，采用滑動窗口技術，除初始情況外，均至少能保存每個線程內近期執行的256個內存操作，完全可以檢測所有競爭距離在0～256范圍內的數據競爭，可以檢測部分競爭距離在256～512范圍內的競爭，距離超過512不予檢測。相應地，WF0/RF0、WF1/RF1這2對簽名均最多只能容納256個內存操作的數據地址。對于加鎖并發競爭域，滑動窗口大小不設限制，對應簽名寄存器存放的地址數目也不做限制，從而可以檢測所有打斷臨界區的操作。

2) 簽名寄存器

選取的簽名寄存器如果太小，則誤報（false positive）會增多，如果過大，則浪費硬件資源。在本算法中分別用 WF0/RF0、WF1/RF1來存儲最多256個內存操作的數據地址；用WF2/RF2存放臨界區中所有的內存操作對應地址，存放數據無上限要求，但大于1 024的臨界區所占比例不到2%。考慮較好的資源利用率，本文針對常用的H3散列簽名寄存器的多個尺寸進行了測試，測試結果如圖 11所示，發現簽名寄存器大于128 bit后，對檢測到的數據競爭數量影響不太大，因此本文選用 128 bit的讀寫簽名寄存器。

圖11 簽名寄存器大小測試結果

7.2 硬件開銷

該算法需要為每個處理器核添加一個 RaceSW模塊，對于8核的CMP系統，配置參數如表3所示，若不考慮運算器部分，該模塊共添加3對128 bit的硬件簽名寄存器，共768 bit，外加1個16 bit的指令計數器（IC）和5個觸發器，共添加789 bit的硬件資源，而文獻[10]中為每個處理器核添加 4 kbit，RaceSW硬件開銷減小了約80%，相比其他不使用簽名的硬件檢測算法[8,9]，RaceSW在更大程度上降低了硬件開銷。

7.3 檢測到的數據競爭數量

圖12分別給出了RaceSW在4核、8核和16核 CMP系統上檢測到的數據競爭數量及其檢測到的兩大類型數據競爭所占的比例情況。可以看出，先發生方在未加鎖并發域的數據競爭占絕大多數；不存在超長臨界區的測試負載（如water、volrend 、ocean、fft），沒有檢測到打斷臨界區的數據競爭，而存在超長臨界區的測試負載都檢測到了打斷臨界區的數據競爭，如barnes、fmm等。這同時也為編程人員針對臨界區大小設置不合理提出了提示信息。因為RaceSW采用滑動窗口策略，僅檢測競爭距離較近、更易引發并發錯誤的數據競爭，在降低硬件復雜度和硬件開銷的前提下，相比文獻[10]等，數據競爭檢測效果有所下降。本文在相同8核環境下采用大尺寸簽名寄存器代替簽名隊列針對文獻[10]提出的 SigRace檢測方法進行了測試，并考慮到庫文件帶來的競爭，檢測到的競爭數量比較結果如圖13所示，RaceSW可以檢測到近期發生的約21%的數據競爭。

圖12 數據競爭數量統計

7.4 帶寬開銷

如果不提示競爭類型，則本方法不需要為cache一致性協議添加新的消息字段，帶來的帶寬開銷為0。如果要指出競爭的類型，則只需要在一致性消息getx和gets中添加1 bit的附加信息，用來指出后發生方來自未加鎖并發競爭域還是加鎖并發競爭域，此時，帶寬開銷不到1%。

圖13 數據競爭數量比較

8 結束語

本文針對基于硬件的happens-before內存競爭檢測方法硬件開銷大的問題，提出了基于滑動窗口的動態數據競爭檢測算法，該算法從遠距離的內存競爭引起并發錯誤的概率較小這一特點出發，將并發的線程片段細分為由線程近期執行的內存操作構成的未加鎖并發競爭域和位于臨界區內的加鎖并發競爭域，并采用滑動窗口技術，用一對交替移動的可重寫滑動窗口保存未加鎖并發競爭域內的內存操作，用可變大小的滑動窗口保存加鎖并發競爭域內的內存操作。硬件實現結構中，滑動窗口內的數據地址自動添加到小尺寸的簽名寄存器中，當有來自其他處理器核的一致性共享請求消息時，通過查找簽名檢測到距離較近的、更易引發并發錯誤的內存競爭。基于8核的CMP系統下的仿真結果指出，該算法硬件開銷小、帶寬開銷低。

[1] SAVAGE S, BURROWS M, NELSON G, et al. Eraser: a dynamic data race detector for multithreaded programs[J]. ACM Transactions on Computer Systems (TOCS), 1997, 15(4): 391-411.

[2] DI P, SUI Y. Accelerating dynamic data race detection using static thread interference analysis[C]//The 7th International Workshop on Programming Models and Applications for Multicores and Manycores.ACM, 2016: 30-39.

[3] WU Z, LU K, WANG X, et al. Collaborative technique for concurrency bug detection[J]. International Journal of Parallel Programming,2015, 43(2): 260-285.

[4] 陳睿, 楊孟飛, 郭向英. 基于變量訪問序模式的中斷數據競爭檢測方法[J]. 軟件學報, 2016, 27(3): 547-561.CHEN R, YANG M F, GUO X Y. Interrupt data race detection based on shared variable access order pattern[J]. Journal of Software, 2016,27(3): 547-561.

[5] 王文文, 武成崗. 動態容忍和檢測非對稱數據競爭[J]. 計算機研究與發展, 2014, 51(8): 1748-1763.WANG W W, WU C G. Dynamically tolerating and detecting asymmetric race[J]. Journal of Computer Research and Development, 2014,51(8): 1748-1763.

[6] LU K, WU Z, WANG X, et al. RaceChecker: efficient identification of harmful data races[C]//2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing. IEEE, 2015:78-85.

[7] WESTER B, DEVECSERY D, CHEN P M, et al. Parallelizing data race detection[J]. ACM Sigplan Notices, 2013, 48(4): 27-38.

[8] PRVULOVIC M. CORD: cost-effective (and nearly overhead-free)order-recording and data race detection[C]//The Twelfth International Symposium on High-Performance Computer Architecture. IEEE, 2006:232-243.

[9] ZHOU P, TEODORESCU R, ZHOU Y. HARD: hardware-assisted lockset-based race detection[C]//2007 IEEE 13th International Symposium on High Performance Computer Architecture. IEEE, 2007:121-132.

[10] MUZAHID A, SUáREZ D, QI S, et al. SigRace: signature-based data race detection[J]. ACM Sigarch Computer Architecture News, 2009,37(3):337-348.

[11] QI S, OTSUKI N, NOGUEIRA L O, et al. Pacman: tolerating asymmetric data races with unintrusive hardware[C]//High Performance Computer Architecture (HPCA), 2012 IEEE 18th International Symposium. IEEE, 2012: 1-12.

[12] QI S, MUZAHID A A, AHN W, et al. Dynamically detecting and tolerating if-condition data races[C]//The 20th IEEE International Symposium on High Performance Computer Architecture (HPCA).IEEE Computer Society, 2014: 120-131.

[13] OROSA L. A hardware approach to detect, expose and tolerate high level data races[C]//The 24th Euromicro International Conference on Parallel,Distributed, and Network-Based Processing (PDP). IEEE, 2016: 159-167.

[14] DEVIETTI J, WOOD B P, STRAUSS K, et al. RADISH: always-on sound and complete race detection in software and hardware[C]//IEEE Computer Architecture (ISCA), 2012 39th Annual International Symposium. IEEE, 2012: 201-212.

[15] ARULRAJ J, CHANG P C, JIN G, et al. Production-run software failure diagnosis via hardware performance counters[J]. ACM Sigarch Computer Architecture News, 2013, 41(1): 101-112.

[16] SHENG T, VACHHARAJANI N, ERANIAN S, et al. RACEZ: a lightweight and non-invasive race detection tool for production applications[C]//The International Conference on Software Engineering.2011: 401-410.

[17] Intel Corporation. Intel thread checker[EB/OL]. http://www.intel.com,2008.

[18] LUSK E, BOYLE J, BUTLER R, et al. Portable programs for parallel processors[M]. Holt, Rinehart amp; Winston, 1988.

[19] MARTIN M M K, SORIN D J, BECKMANN B M, et al. Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset[J].ACM SIGARCH Computer Architecture News, 2005, 33(4): 92-99.

[20] WOO S C, OHARA M, TORRIE E, et al. The SPLASH-2 programs:characterization and methodological considerations[J]. ACM SIGARCH Computer Architecture News, ACM, 1995, 23(2): 24-36.

Hardware data race detection algorithm based on sliding windows

ZHU Su-xia1,2, CHEN De-yun1,2, JI Zhen-zhou3, SUN Guang-lu1
(1. School of Computer Science and Technology, Harbin University of Technology, Harbin 150080, China;2. Postdoctoral Research Station, School of Computer Science and Technology, Harbin University of Technology, Harbin 150080, China;3. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)

Data race is a major factor which causes multi-core programs to produce concurrent bugs. To address the high hardware cost in happens-before detection proposals, a light-weight hardware data race detection approach based on sliding window technology was proposed. It used sliding windows to save recent memory instructions in thread execution and dynamically detected data races with small race distance which more easily lead to concurrent bugs. Considering the race distance, parallel thread segments were subdivided into concurrent race regions with lock and concurrent race regions without lock. A pair of alternate rewritable sliding windows was used to store the memory instructions in concurrent race region without lock, and a sliding window with variable size was used to store the memory instructions in concurrent race region with lock. When there was a conflict between a remote sharing access and memory accesses in sliding windows, a data race was detected. In the hardware implementation, the addresses of the data in sliding windows were automatically encoded into three hardware signatures with small size. Data races can be detected quickly without modifying the L1 cache and cache coherence protocol messages. This approach supplies efficient guidance to help users to diagnose concurrency bugs occurred in the development and production run of multi-core programs, achieving smaller hardware and bandwidth overhead.

data race, sliding window, hardware signature, concurrency bug, multi-core program

s: The National Natural Science Foundation of China for Youths(No.61502123), Heilongjiang Province Science Foundation for Youths(No.QC2015084), The China Postdoctoral Science Foundation(No.2015M571429), The National Natural Science Foundation of China(No.61472100), The National Basic Research Program of China(973 Program)(No.2011CB302501)

TP303

A

10.11959/j.issn.1000-436x.2016173

2016-04-05；

2016-07-14

國家自然科學青年基金資助項目(No.61502123)；黑龍江省青年科學基金資助項目(No.QC2015084)；中國博士后科學基金資助項目(No.2015M571429)；國家自然科學基金資助項目(No.61472100)；國家重點基礎研究發展計劃（“973”計劃）基金資助項目(No.2011CB302501)

朱素霞（1978-），女，山東壽光人，博士，哈爾濱理工大學副教授，主要研究方向為高性能體系結構、并行計算。

陳德運（1962-），男，黑龍江哈爾濱人，哈爾濱理工大學教授、博士生導師，主要研究方向為圖像處理、探測和成像技術。

季振洲（1965-），男，黑龍江哈爾濱人，哈爾濱工業大學教授、博士生導師，主要研究方向為并行體系結構、并行計算和網絡安全。

孫廣路（1979-），男，黑龍江哈爾濱人，哈爾濱理工大學教授，主要研究方向為網絡安全、模式識別和機器學習。