基于滑動(dòng)窗口的多核程序數(shù)據(jù)競(jìng)爭(zhēng)硬件檢測(cè)算法

朱素霞，陳德運(yùn)，季振洲，孫廣路

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

基于滑動(dòng)窗口的多核程序數(shù)據(jù)競(jìng)爭(zhēng)硬件檢測(cè)算法

朱素霞1,2，陳德運(yùn)1,2，季振洲3，孫廣路1

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

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

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

1 引言

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

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

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

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

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

2 研究動(dòng)機(jī)

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

1) happens-before算法代價(jià)昂貴

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

2) 數(shù)據(jù)競(jìng)爭(zhēng)是否會(huì)引起并發(fā)錯(cuò)誤受距離影響

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

3) 糾正錯(cuò)誤不一定要檢測(cè)出所有的數(shù)據(jù)競(jìng)爭(zhēng)

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

圖1 數(shù)據(jù)競(jìng)爭(zhēng)示意

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

3 競(jìng)爭(zhēng)距離

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

圖2 競(jìng)爭(zhēng)距離

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

4 并發(fā)競(jìng)爭(zhēng)域

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

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

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

圖4 并發(fā)競(jìng)爭(zhēng)域

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

圖5 檢測(cè)到的數(shù)據(jù)競(jìng)爭(zhēng)類型

5 基于滑動(dòng)窗口的動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)

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

5.1 未加鎖并發(fā)競(jìng)爭(zhēng)域

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

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

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

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

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

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

圖6 指令在滑動(dòng)窗口的流動(dòng)示意

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

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

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

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

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

5.2 加鎖并發(fā)競(jìng)爭(zhēng)域

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

6 硬件實(shí)現(xiàn)

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

圖8 加鎖并發(fā)競(jìng)爭(zhēng)域競(jìng)爭(zhēng)示例

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

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

表1 新增機(jī)器指令

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

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

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

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

該算法中每個(gè)處理器核做如下動(dòng)作。

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

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

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

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

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

7 性能評(píng)價(jià)

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

表3 仿真配置

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

7.1 參數(shù)選取

1) 滑動(dòng)窗口

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

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

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

2) 簽名寄存器

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

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

7.2 硬件開銷

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

7.3 檢測(cè)到的數(shù)據(jù)競(jìng)爭(zhēng)數(shù)量

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

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

7.4 帶寬開銷

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

圖13 數(shù)據(jù)競(jìng)爭(zhēng)數(shù)量比較

8 結(jié)束語

本文針對(duì)基于硬件的happens-before內(nèi)存競(jìng)爭(zhēng)檢測(cè)方法硬件開銷大的問題，提出了基于滑動(dòng)窗口的動(dòng)態(tài)數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)算法，該算法從遠(yuǎn)距離的內(nèi)存競(jìng)爭(zhēng)引起并發(fā)錯(cuò)誤的概率較小這一特點(diǎn)出發(fā)，將并發(fā)的線程片段細(xì)分為由線程近期執(zhí)行的內(nèi)存操作構(gòu)成的未加鎖并發(fā)競(jìng)爭(zhēng)域和位于臨界區(qū)內(nèi)的加鎖并發(fā)競(jìng)爭(zhēng)域，并采用滑動(dòng)窗口技術(shù)，用一對(duì)交替移動(dòng)的可重寫滑動(dòng)窗口保存未加鎖并發(fā)競(jìng)爭(zhēng)域內(nèi)的內(nèi)存操作，用可變大小的滑動(dòng)窗口保存加鎖并發(fā)競(jìng)爭(zhēng)域內(nèi)的內(nèi)存操作。硬件實(shí)現(xiàn)結(jié)構(gòu)中，滑動(dòng)窗口內(nèi)的數(shù)據(jù)地址自動(dòng)添加到小尺寸的簽名寄存器中，當(dāng)有來自其他處理器核的一致性共享請(qǐng)求消息時(shí)，通過查找簽名檢測(cè)到距離較近的、更易引發(fā)并發(fā)錯(cuò)誤的內(nèi)存競(jìng)爭(zhēng)。基于8核的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ìng)爭(zhēng)檢測(cè)方法[J]. 軟件學(xué)報(bào), 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] 王文文, 武成崗. 動(dòng)態(tài)容忍和檢測(cè)非對(duì)稱數(shù)據(jù)競(jìng)爭(zhēng)[J]. 計(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

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

朱素霞（1978-），女，山東壽光人，博士，哈爾濱理工大學(xué)副教授，主要研究方向?yàn)楦咝阅荏w系結(jié)構(gòu)、并行計(jì)算。

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

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

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