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

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

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

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

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

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

數(shù)據(jù)競爭；滑動窗口；硬件簽名；并發(fā)錯誤；多核程序

1 引言

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

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

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

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

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

2 研究動機

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

1) happens-before算法代價昂貴

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

2) 數(shù)據(jù)競爭是否會引起并發(fā)錯誤受距離影響

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

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

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

圖1 數(shù)據(jù)競爭示意

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

3 競爭距離

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

圖2 競爭距離

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

4 并發(fā)競爭域

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

圖3 并發(fā)線程片段與數(shù)據(jù)競爭

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

圖4 并發(fā)競爭域

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

圖5 檢測到的數(shù)據(jù)競爭類型

5 基于滑動窗口的動態(tài)數(shù)據(jù)競爭檢測

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

5.1 未加鎖并發(fā)競爭域

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

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

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

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

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

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

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

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

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

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

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

圖7 未加鎖并發(fā)競爭域內(nèi)的競爭示例

5.2 加鎖并發(fā)競爭域

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

6 硬件實現(xiàn)

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

圖8 加鎖并發(fā)競爭域競爭示例

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

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

表1 新增機器指令

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

圖9 硬件實現(xiàn)結(jié)構(gòu)

表2 對庫函數(shù)的修改

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

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

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

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

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

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

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

7 性能評價

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

表3 仿真配置

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

7.1 參數(shù)選取

1) 滑動窗口

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

圖10 不同大小臨界區(qū)所占比例統(tǒng)計

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

2) 簽名寄存器

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

圖11 簽名寄存器大小測試結(jié)果

7.2 硬件開銷

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

7.3 檢測到的數(shù)據(jù)競爭數(shù)量

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

圖12 數(shù)據(jù)競爭數(shù)量統(tǒng)計

7.4 帶寬開銷

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

圖13 數(shù)據(jù)競爭數(shù)量比較

8 結(jié)束語

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

[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] 陳睿, 楊孟飛, 郭向英. 基于變量訪問序模式的中斷數(shù)據(jù)競爭檢測方法[J]. 軟件學(xué)報, 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] 王文文, 武成崗. 動態(tài)容忍和檢測非對稱數(shù)據(jù)競爭[J]. 計算機研究與發(fā)展, 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

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

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

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

季振洲（1965-），男，黑龍江哈爾濱人，哈爾濱工業(yè)大學(xué)教授、博士生導(dǎo)師，主要研究方向為并行體系結(jié)構(gòu)、并行計算和網(wǎng)絡(luò)安全。

孫廣路（1979-），男，黑龍江哈爾濱人，哈爾濱理工大學(xué)教授，主要研究方向為網(wǎng)絡(luò)安全、模式識別和機器學(xué)習(xí)。