面向監(jiān)聽一致性協(xié)議的并發(fā)內(nèi)存競爭記錄算法

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

1(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院博士后流動(dòng)站　哈爾濱　150080)2(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　哈爾濱　150080)3(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　哈爾濱　150001)4　　　(中國科學(xué)院計(jì)算技術(shù)研究所　北京　100190) (zhusuxia@hrbust.edu.cn)

?

面向監(jiān)聽一致性協(xié)議的并發(fā)內(nèi)存競爭記錄算法

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

1(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院博士后流動(dòng)站哈爾濱150080)2(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱150080)3(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈爾濱150001)4(中國科學(xué)院計(jì)算技術(shù)研究所北京100190) (zhusuxia@hrbust.edu.cn)

摘要內(nèi)存競爭記錄是解決多核程序執(zhí)行不確定性的關(guān)鍵技術(shù)，然而現(xiàn)有點(diǎn)到點(diǎn)的內(nèi)存競爭記錄機(jī)制帶來的硬件開銷大，難以應(yīng)用到實(shí)際的片上多核處理器系統(tǒng)中.以降低點(diǎn)到點(diǎn)內(nèi)存競爭記錄方式的硬件開銷為出發(fā)點(diǎn)，為采用監(jiān)聽一致性協(xié)議的片上多核處理器(chip multiprocessor, CMP)系統(tǒng)設(shè)計(jì)了基于并發(fā)記錄策略的點(diǎn)到點(diǎn)內(nèi)存競爭記錄算法.該記錄算法將兩兩線程間點(diǎn)到點(diǎn)的內(nèi)存競爭關(guān)系擴(kuò)展到所有線程，采用分布式記錄方法為每個(gè)線程記錄一個(gè)由內(nèi)存競爭關(guān)系的一方構(gòu)成的內(nèi)存競爭日志；重演時(shí)采用簡化的生產(chǎn)者消費(fèi)者模型，確保了確定性重演的實(shí)現(xiàn)，有效降低了硬件消耗和帶寬開銷.在8核處理器系統(tǒng)中的仿真結(jié)果表明，該并發(fā)式點(diǎn)到點(diǎn)內(nèi)存競爭記錄算法為每個(gè)處理器核添加硬件資源約171 B，每千條內(nèi)存操作指令記錄日志大小約2.3 B，記錄和重演階段均添加不到1.5%的帶寬開銷.

關(guān)鍵詞片上多核處理器；多核程序；確定性重演；內(nèi)存競爭記錄；內(nèi)存沖突檢測；監(jiān)聽一致性協(xié)議

在共享內(nèi)存的片上多核處理器(chip multi-processor, CMP)系統(tǒng)中，線程間內(nèi)存訪問的順序不確定，導(dǎo)致多核程序的編寫、調(diào)試、容錯(cuò)[1]和安全[2]等都變得異常困難.內(nèi)存競爭記錄和重演是解決這一問題的有效手段.內(nèi)存競爭記錄和重演機(jī)制通過在多核程序原始執(zhí)行階段記錄下線程間的內(nèi)存競爭順序，在重演階段依據(jù)所記錄的內(nèi)存競爭順序復(fù)現(xiàn)原始的執(zhí)行順序，從而輔助實(shí)現(xiàn)多核程序的確定性重演.截至目前為止，研究者們已經(jīng)提出了眾多軟件[3-4]和硬件[2,5-13]實(shí)現(xiàn)的內(nèi)存競爭記錄機(jī)制.硬件實(shí)現(xiàn)方案通過為原有CMP系統(tǒng)增加新的硬件資源實(shí)現(xiàn)內(nèi)存競爭的記錄和重演，具有效率高、開銷低等優(yōu)點(diǎn)，應(yīng)用前景廣闊.硬件實(shí)現(xiàn)的內(nèi)存競爭記錄方案中，主要有點(diǎn)到點(diǎn)記錄方式[2,5,9-12]和chunk記錄方式[6-8,13]2大類.點(diǎn)到點(diǎn)的記錄方式以指令為粒度，記錄線程間內(nèi)存沖突對(duì)應(yīng)的依賴關(guān)系，無論是記錄還是重演，都具有良好的并行性，但硬件資源消耗較大，影響了它在實(shí)際CMP系統(tǒng)中的應(yīng)用.chunk記錄方式使用較少的硬件資源記錄線程間無沖突的指令塊，按照chunk時(shí)戳的順序?qū)崿F(xiàn)確定性重演.目前這2種記錄方式針對(duì)基于目錄一致性協(xié)議的CMP系統(tǒng)已經(jīng)取得了豐富的研究成果[2,5-6,8-12]，但是針對(duì)采用監(jiān)聽一致性協(xié)議系統(tǒng)的研究還有待進(jìn)一步挖掘，因?yàn)閷?shí)際的CMP系統(tǒng)大都采用了基于監(jiān)聽的cache一致性協(xié)議.因此，研究支持監(jiān)聽一致性協(xié)議的內(nèi)存競爭記錄和重演機(jī)制更具現(xiàn)實(shí)意義.

IMRR[7]針對(duì)監(jiān)聽一致性協(xié)議的CMP系統(tǒng)提出了一種基于chunk的內(nèi)存競爭記錄機(jī)制，該機(jī)制有效解決了監(jiān)聽協(xié)議下內(nèi)存競爭的記錄和重演，并且針對(duì)chunk方式重演速度受限問題，提出了并發(fā)chunk域來提高重演的速度.但是它在實(shí)現(xiàn)重演時(shí)需要引入同步計(jì)數(shù)器等更新機(jī)制，導(dǎo)致重演結(jié)構(gòu)略顯復(fù)雜，對(duì)原有一致性協(xié)議結(jié)構(gòu)改造較大.文獻(xiàn)[13]依據(jù)IMRR的思想采用FPGA實(shí)現(xiàn)了支持內(nèi)存競爭記錄和重演功能的Intel處理器架構(gòu)原型.LReplay[14]通過記錄指令或指令塊的延遲時(shí)間信息，引入少量的硬件資源，記錄了較小的日志，但它只能應(yīng)用于一款特殊的體系結(jié)構(gòu)Godson-3[15].其他基于chunk的記錄機(jī)制[8]和采用點(diǎn)到點(diǎn)記錄方式的內(nèi)存競爭記錄機(jī)制[2,5]均是針對(duì)基于目錄的一致性協(xié)議提出的，雖然也可以應(yīng)用到采用監(jiān)聽一致性協(xié)議的系統(tǒng)中，但都未給出該協(xié)議下記錄算法的詳細(xì)設(shè)計(jì)描述.而且，因?yàn)樾枰谔幚砥骱碎g傳送指令時(shí)戳等信息，點(diǎn)到點(diǎn)的記錄方式還會(huì)導(dǎo)致監(jiān)聽協(xié)議下較大的帶寬開銷.

為了減小點(diǎn)到點(diǎn)記錄方式的硬件資源消耗、提高其應(yīng)用前景，本文面向采用監(jiān)聽一致性協(xié)議的CMP系統(tǒng)，提出了一種新穎的并發(fā)式點(diǎn)到點(diǎn)內(nèi)存競爭記錄算法(concurrent point-to-point memory race recording algorithm, CPMRR)，相比已有的點(diǎn)到點(diǎn)記錄策略，顯著降低了硬件開銷；相比面向監(jiān)聽一致性協(xié)議的chunk記錄機(jī)制IMRR[7]，該記錄算法在未增大內(nèi)存競爭日志的前提下，提高了重演速度，降低了帶寬開銷.

本文的貢獻(xiàn)有3點(diǎn)：1)針對(duì)基于監(jiān)聽的cache一致性協(xié)議提出了第1個(gè)完整的點(diǎn)到點(diǎn)內(nèi)存競爭記錄算法；2)采用了并發(fā)式點(diǎn)到點(diǎn)記錄策略，帶來的硬件開銷可以同chunk記錄方式相媲美；3)提出了一種基于生產(chǎn)者消費(fèi)者模型的高效的重演機(jī)制，硬件實(shí)現(xiàn)結(jié)構(gòu)簡單，重演速度快，核間互聯(lián)帶寬開銷低.

1記錄內(nèi)存競爭

2個(gè)或多個(gè)線程訪問同一個(gè)內(nèi)存，并且至少有1個(gè)是寫操作，則發(fā)生內(nèi)存沖突.如果沒有正確的使用同步操作，線程間內(nèi)存沖突的順序是不確定的，可能會(huì)引起內(nèi)存競爭.內(nèi)存競爭檢測是個(gè)NP困難問題[16]，因此，點(diǎn)到點(diǎn)的內(nèi)存競爭記錄方式通過記錄線程間內(nèi)存沖突雙方構(gòu)成的依賴關(guān)系為每個(gè)線程記錄1個(gè)內(nèi)存競爭日志，如圖1所示，便可以實(shí)現(xiàn)確定性重演.該記錄方式以指令為粒度，記錄的是兩兩線程間的局部關(guān)系，要記錄所有線程間的這種局部關(guān)系，需要CMP系統(tǒng)中的每個(gè)處理器核為其他所有處理器核都要存儲(chǔ)信息.假設(shè)CMP系統(tǒng)中共有n個(gè)處理器核，文獻(xiàn)[2,5,9]中除了需要增加龐大的cache時(shí)戳外，每個(gè)處理器核還需要存儲(chǔ)對(duì)應(yīng)其他n-1個(gè)處理器核的時(shí)戳.文獻(xiàn)[10-12]中設(shè)計(jì)的內(nèi)存競爭記錄器雖然采用占用較少資源的簽名替換了時(shí)戳，但需要為每個(gè)處理器核添加n-1對(duì)簽名.相比chunk記錄方式，點(diǎn)到點(diǎn)記錄方式帶來的硬件資源消耗較高，這也是點(diǎn)到點(diǎn)記錄方式難以應(yīng)用到實(shí)際CMP系統(tǒng)的主要原因之一.

Fig. 1　Logging point-to-point memory races.圖1　點(diǎn)到點(diǎn)內(nèi)存競爭記錄策略示意圖

為了提高點(diǎn)到點(diǎn)記錄方式的應(yīng)用前景，本文面向監(jiān)聽一致性協(xié)議的CMP系統(tǒng)，提出了基于并發(fā)記錄策略的點(diǎn)到點(diǎn)內(nèi)存競爭記錄算法.該算法在檢測到內(nèi)存沖突后，記錄下所有線程間內(nèi)存操作指令的執(zhí)行順序，將線程間點(diǎn)到點(diǎn)內(nèi)存競爭關(guān)系擴(kuò)展到所有線程，減少了每個(gè)處理器核所需要存儲(chǔ)的信息，降低了硬件資源消耗.

1.1并發(fā)記錄內(nèi)存沖突

2個(gè)線程發(fā)生沖突時(shí)，沖突雙方對(duì)應(yīng)的內(nèi)存操作指令間存在執(zhí)行的先后順序.雖然沖突先發(fā)生方所在線程同其他線程間沒有發(fā)生沖突，但這些線程之間的內(nèi)存操作指令也同樣存在執(zhí)行的先后順序.如圖2所示，帶箭頭的虛線表示沖突雙方的先后執(zhí)行順序，帶箭頭的點(diǎn)劃線表示沖突先發(fā)生方所在線程同其他線程間內(nèi)存操作指令的先后執(zhí)行順序，帶箭頭的實(shí)線表示并發(fā)記錄方式中所要記錄的沖突順序.圖2(a)中線程i,j,k分別運(yùn)行在CMP系統(tǒng)中不同的處理器核上，當(dāng)線程i執(zhí)行到標(biāo)記為③的內(nèi)存操作指令wr(z)后，線程i,j間會(huì)檢測到1個(gè)內(nèi)存沖突j:①′→i:③，此時(shí)，線程k執(zhí)行完標(biāo)記為③″的內(nèi)存操作指令rd(y).此時(shí)，線程j,k間雖然不存在沖突，但可以存在j:①′→k:③″這樣的執(zhí)行順序.如果也記錄下線程j,k間這種執(zhí)行順序，在重演時(shí)不會(huì)影響原有線程間內(nèi)存操作指令執(zhí)行順序的復(fù)現(xiàn)，僅是增加了重演時(shí)檢查點(diǎn)的次數(shù).鑒于此觀察，本文在進(jìn)行內(nèi)存競爭記錄時(shí)，將兩兩線程間的內(nèi)存沖突擴(kuò)展到所有線程，不只記錄沖突雙方的先后順序(如圖2(a)中標(biāo)記出的j:①′→i:③)，也記錄下沖突先發(fā)生方所在線程同其他線程間內(nèi)存操作指令的先后執(zhí)行順序(如圖2(a)中標(biāo)記出的j:①′→k:③″).本文后面部分均稱這2種先后順序?yàn)闆_突依賴關(guān)系.

Fig. 2　An example of logging memory races concurrently.圖2　并發(fā)記錄內(nèi)存競爭示意圖

該記錄方式可以在檢測到?jīng)_突時(shí)，并發(fā)的記錄下所有線程間內(nèi)存操作指令的執(zhí)行順序，即變相的假定沖突先發(fā)生方同其他所有線程間都存在沖突.如果只記錄不能推導(dǎo)的內(nèi)存沖突[17]，則無需再檢測先發(fā)生方所在線程已執(zhí)行完的內(nèi)存操作指令是否還會(huì)與其他線程發(fā)生沖突，因此，也就無需存儲(chǔ)先發(fā)生方所在線程已執(zhí)行完的內(nèi)存操作指令的相關(guān)信息，從而可以在硬件實(shí)現(xiàn)時(shí)減少硬件資源消耗.同時(shí)，為了進(jìn)一步減小硬件開銷，本并發(fā)式記錄策略采用沖突發(fā)生時(shí)沖突雙方當(dāng)前指令計(jì)數(shù)值構(gòu)成的當(dāng)前發(fā)生序[10]表示沖突依賴關(guān)系.如圖2(b)所示，帶箭頭的實(shí)線標(biāo)記出了該并發(fā)記錄方式所要記錄的沖突依賴關(guān)系.

1.2精簡內(nèi)存競爭日志

本文所提出的并發(fā)式內(nèi)存競爭記錄策略雖然通過記錄沖突發(fā)生時(shí)所有線程間內(nèi)存操作指令的先后執(zhí)行順序，減少了每個(gè)線程因檢測內(nèi)存沖突而需要存儲(chǔ)的信息，但會(huì)導(dǎo)致記錄的沖突數(shù)目過多，使得整個(gè)內(nèi)存競爭日志變大.例如，該記錄方式在檢測到1個(gè)內(nèi)存沖突時(shí)，需要記錄n-1個(gè)沖突依賴關(guān)系，所記錄的日志數(shù)目是原有點(diǎn)到點(diǎn)記錄方式的n-1倍.并且，每次檢測到?jīng)_突時(shí)所記錄的n-1個(gè)沖突依賴關(guān)系的先發(fā)生方都對(duì)應(yīng)同一個(gè)內(nèi)存操作指令，即沖突先發(fā)生方會(huì)被重復(fù)記錄n-1次，導(dǎo)致日志冗余過多.同樣，隨著系統(tǒng)中處理器核數(shù)目的增多，記錄的日志也會(huì)成倍地增大.因此，本文采取了一系列措施來精簡內(nèi)存競爭日志.

首先，該并發(fā)式內(nèi)存競爭記錄策略不再記錄沖突依賴關(guān)系的雙方到同一線程的日志中，而是采用分布式的日志記錄策略，每個(gè)線程僅記錄沖突的一方，而且對(duì)于需要重復(fù)記錄的沖突先發(fā)生方也只記錄1次.如此以來，沖突先發(fā)生所在線程只記錄先發(fā)生方，沖突后發(fā)生方所在線程和其他線程僅記錄后發(fā)生方.為了區(qū)別線程記錄的信息是先發(fā)生方還是后發(fā)生方，本文在記錄格式中引入1個(gè)類型標(biāo)志位，即記錄格式包含2個(gè)域：1)類型域，它指出了該記錄是先發(fā)生方還是后發(fā)生方，可以僅用1位來表示，0代表先發(fā)生方，1代表后發(fā)生方；2)大小域，它指出了該內(nèi)存操作對(duì)應(yīng)的指令計(jì)數(shù)值.如圖3所示，帶箭頭的虛線表示沖突雙方的先后執(zhí)行順序，帶箭頭的點(diǎn)劃線表示沖突先發(fā)生方所在線程同其他線程間內(nèi)存操作指令的先后執(zhí)行順序，帶箭頭的實(shí)線表示并發(fā)記錄方式中所要記錄的沖突順序.圖3(b)給出了線程i,j,k所記錄的分布式日志：當(dāng)檢測到內(nèi)存沖突j:①′→i:③時(shí)，線程i,j,k分別記錄1,③,0,②′,1,③″到各自線程的日志中；當(dāng)檢測到內(nèi)存沖突i:1→j:④′時(shí)，線程i,j,k分別記錄0,④,1,④′,1,④″到各自線程的日志中；當(dāng)檢測到內(nèi)存沖突k:②″→j:⑤′時(shí)，線程i,j,k分別記錄1,⑥,1,⑤′,0,⑤″到各自線程的日志中.

為了進(jìn)一步精簡內(nèi)存競爭日志，本并發(fā)式記錄策略在每次記錄下沖突依賴關(guān)系的先發(fā)生方和后發(fā)生方后將指令計(jì)數(shù)器復(fù)位，讓其從0開始重新計(jì)數(shù).同時(shí)，當(dāng)每個(gè)線程的內(nèi)存操作指令計(jì)數(shù)累計(jì)到215-1時(shí)，也假定檢測到內(nèi)存沖突，在記錄下先發(fā)生方和后發(fā)生方后，將指令計(jì)數(shù)器復(fù)位.當(dāng)發(fā)生線程的上下文切換時(shí)，也假定檢測到內(nèi)存沖突，在記錄下先發(fā)生方和后發(fā)生方后，將指令計(jì)數(shù)器復(fù)位.采用如此方法，不僅解決了線程切換帶來的日志記錄問題，還可以有效控制每個(gè)記錄的大小不超過215-1，從而進(jìn)一步減小了內(nèi)存競爭日志.如圖3(b)右側(cè)日志部分指出了精簡后的分布式內(nèi)存競爭日志.

Fig. 3　Reducing memory race log.圖3　精簡內(nèi)存競爭日志

這種分布式的記錄策略，雖然將內(nèi)存沖突的依賴關(guān)系分開記錄，但仍然以指令為粒度記錄線程間指令執(zhí)行的先后順序關(guān)系，沒有改變點(diǎn)到點(diǎn)記錄方式的本質(zhì).該記錄方式不僅能夠有效地減小日志，還可以減小核間互聯(lián)網(wǎng)絡(luò)的帶寬開銷.因?yàn)樵瓉淼狞c(diǎn)到點(diǎn)記錄方式將沖突依賴關(guān)系記錄到某個(gè)線程的日志中，需要處理器核間傳送指令計(jì)數(shù)值，這樣增加了帶寬開銷而分布式的記錄策略卻無需傳送指令計(jì)數(shù)值，僅需在檢測到內(nèi)存沖突時(shí)沖突先發(fā)生方所在處理器核向其他處理器核廣播1個(gè)檢測到?jīng)_突的消息即可，其他處理器核收到此消息后，記錄后發(fā)生方到內(nèi)存競爭日志中.

2檢測內(nèi)存沖突

并發(fā)記錄策略在檢測到內(nèi)存沖突后會(huì)記錄下此刻所有線程的執(zhí)行點(diǎn)，即沖突依賴關(guān)系的先發(fā)生方和后發(fā)生方，先發(fā)生方之前的內(nèi)存操作指令不再參與到后續(xù)的內(nèi)存沖突檢測中.因此，可以將先發(fā)生方所記錄的有關(guān)沖突檢測的所有信息清空.因此，本文采用簽名技術(shù)，且僅需要為每個(gè)處理器核添加1對(duì)讀寫簽名就可以實(shí)現(xiàn)內(nèi)存沖突檢測.當(dāng)有內(nèi)存訪問請求時(shí)，應(yīng)答方所在處理器核通過查找簽名寄存器實(shí)現(xiàn)內(nèi)存沖突檢測，一旦檢測到?jīng)_突，則記錄下先發(fā)生方并廣播1個(gè)檢測到內(nèi)存沖突的消息到所有處理器核，同時(shí)清空讀寫簽名寄存器、復(fù)位指令計(jì)數(shù)器.

檢測到內(nèi)存沖突消息在實(shí)現(xiàn)時(shí)無需改變監(jiān)聽一致性協(xié)議的結(jié)構(gòu)，而是僅在現(xiàn)有協(xié)議基礎(chǔ)上增加了1個(gè)新型的請求類消息，取名為record.因?yàn)椴捎梅植际饺罩居涗洸呗杂涗泝?nèi)存競爭，無需傳送內(nèi)存操作指令的時(shí)戳，該消息會(huì)帶來較小的帶寬開銷.

3重演內(nèi)存沖突

為了能夠依據(jù)所記錄的內(nèi)存競爭日志確定性的重演多核程序，本文采用了基于喚醒消息的重演策略.在重演時(shí)，處理器核所讀取的日志信息只包含2種信息：先發(fā)生方和后發(fā)生方、先發(fā)生方所在處理器核會(huì)在先發(fā)生方對(duì)應(yīng)指令執(zhí)行完畢后向其他處理器核廣播1個(gè)喚醒消息；后發(fā)生方所在處理器核在接收到先發(fā)生方發(fā)送的喚醒消息后才能繼續(xù)執(zhí)行.對(duì)某個(gè)線程來說，它所記錄的后發(fā)生方只需要接收來自其他線程的喚醒消息.假設(shè)消息不會(huì)丟失，則每個(gè)后發(fā)生方都能等到相應(yīng)的喚醒消息，從而可以實(shí)現(xiàn)確定性的重演.

Fig. 4　Simple execution diagrams of a multi-coreprogram.圖4　多核程序執(zhí)行簡單示意圖

同時(shí)，位于同一線程的后發(fā)生方等待喚醒消息的順序與先發(fā)生方所存在的全局的先后執(zhí)行順序也是一致的.在圖4(a)中，位于線程j的后發(fā)生方b會(huì)先等待喚醒消息，e會(huì)后等待喚醒消息，而j線程會(huì)先收到來自先發(fā)生方a的喚醒消息，后收到來自先發(fā)生方b的喚醒消息.對(duì)于其他線程也同樣存在如此順序.

如果1個(gè)后發(fā)生方需要等待多個(gè)來自其他線程的喚醒消息，則喚醒消息到來的先后順序不會(huì)影響重演.如圖4(c)所示，d需要等待來自a和b的喚醒消息，重演時(shí)，只要2個(gè)消息都到達(dá)后d便可執(zhí)行，無論a,b消息到來的先后順序如何.

假設(shè)重演過程中不存在喚醒消息丟失現(xiàn)象，對(duì)于1個(gè)后發(fā)生方只對(duì)應(yīng)1個(gè)先發(fā)生方的情況，重演時(shí)，如果1個(gè)后發(fā)生方(如圖4(a)中的點(diǎn)b)只等到了1個(gè)喚醒消息，則此喚醒肯定是來自于它對(duì)應(yīng)的先發(fā)生方(如點(diǎn)a)，如果1個(gè)后發(fā)生方(如點(diǎn)b)等到了2或多個(gè)喚醒消息，那其中有1個(gè)肯定是它要等待的喚醒消息.對(duì)于1個(gè)后發(fā)生方對(duì)應(yīng)多個(gè)(假設(shè)m個(gè))先發(fā)生方的情況，如圖4(c)中所示，重演時(shí)，若點(diǎn)d等到了m個(gè)或大于m個(gè)喚醒消息，則肯定有m個(gè)喚醒消息是d所要等待的.因此，在重演時(shí)無需關(guān)心喚醒消息來自何方，只需要判斷接收的喚醒消息是否達(dá)到后發(fā)生方所要求的喚醒消息數(shù)量即可.

鑒于此，本文在實(shí)現(xiàn)重演時(shí)，采用了簡化的生產(chǎn)者和消費(fèi)者模型：每個(gè)處理器核既充當(dāng)生產(chǎn)者，又充當(dāng)消費(fèi)者，當(dāng)接收到喚醒消息后將喚醒消息計(jì)數(shù)值加1，當(dāng)執(zhí)行到后發(fā)生方時(shí)將喚醒消息計(jì)數(shù)值減1.為此，本文在實(shí)現(xiàn)重演時(shí)，為每個(gè)處理器核引入1個(gè)簡化的喚醒消息計(jì)數(shù)信號(hào)量，用來記錄接收到喚醒消息的數(shù)量.重演時(shí)，當(dāng)處理器核收到喚醒消息后，喚醒消息計(jì)數(shù)信號(hào)量加1，當(dāng)線程執(zhí)行到后發(fā)生方時(shí)，判斷喚醒消息計(jì)數(shù)器的值是否為空，若不為空，則繼續(xù)向前執(zhí)行后發(fā)生方，執(zhí)行完后發(fā)生方后，喚醒消息計(jì)數(shù)器減1.隨著程序的重放，生產(chǎn)的消息會(huì)不斷地被消費(fèi)，因此可用消息的數(shù)量是有限的，可以給喚醒消息計(jì)數(shù)信號(hào)量設(shè)定1個(gè)最大值，如216-1.

喚醒消息的實(shí)現(xiàn)同記錄階段record消息的實(shí)現(xiàn)機(jī)制一樣，無須改變現(xiàn)有的一致性協(xié)議結(jié)構(gòu)，僅為監(jiān)聽一致性協(xié)議再增加1個(gè)新型的請求操作類型，名為wakeup.當(dāng)處理器核執(zhí)行完先發(fā)生方后，向其他處理器核廣播1個(gè)wakeup消息，同樣因?yàn)闊o需標(biāo)記喚醒消息的來源，該消息會(huì)為核間互聯(lián)網(wǎng)絡(luò)帶來較小的帶寬開銷.

4基于硬件的算法描述及具體實(shí)現(xiàn)結(jié)構(gòu)

4.1記錄算法

本文提出的并發(fā)式點(diǎn)到點(diǎn)記錄算法在檢測到內(nèi)存沖突后為每個(gè)線程記都記錄1個(gè)日志，沖突的先發(fā)生方所在線程記錄沖突對(duì)應(yīng)的先發(fā)生方，其他線程記錄沖突對(duì)應(yīng)的后發(fā)生方.該記錄算法基于硬件的描述如算法1所示，它詳細(xì)描述了每個(gè)處理器核的狀態(tài)和動(dòng)作.

算法1. 內(nèi)存競爭記錄算法.

每個(gè)處理器核的狀態(tài):

IC-指令計(jì)數(shù)器;

Pred-內(nèi)存沖突的先發(fā)生方;

Succ-內(nèi)存沖突的后發(fā)生方;

RF-讀簽名;

WF-寫簽名;

Log-內(nèi)存競爭日志.

在內(nèi)存指令提交時(shí)memop{

IC++;

if (memop是寫指令)

WF.insert(memop.address);

if (memop是讀指令)

RF.insert(memop.address);

if (IC=215-1){

Broadcast(record);

Log.append(0,IC[14:0]);

WF.clear();

RF.clear();

IC.clear();

}

}

當(dāng)收到來自其他處理器核關(guān)于塊b的一致性請求消息request時(shí) {

if (WF.find(b.address)‖(RF.find(b.address) && (request=GETX))){

Broadcast(record);

Log.append(0,IC[14:0]);

WF.clear();

RF.clear();

IC.clear();

}

}

當(dāng)收到來自其他處理器核的record一致性消息時(shí) {

Log.append(1,IC[14:0]);

WF.clear();

RF.clear();

IC.clear();

}

該記錄算法中每個(gè)處理器核做4個(gè)動(dòng)作：

1) 每當(dāng)處理器核執(zhí)行內(nèi)存操作指令時(shí)，指令計(jì)數(shù)器加1；如果是寫內(nèi)存操作則將對(duì)應(yīng)內(nèi)存地址添加到寫簽名中，如果是讀內(nèi)存操作則將對(duì)應(yīng)內(nèi)存地址添加到讀簽名中.

2) 當(dāng)收到來自其他處理器核的共享內(nèi)存訪問請求時(shí)，處理器核查找簽名來檢測是否發(fā)生內(nèi)存沖突.

3) 如果檢測到內(nèi)存沖突或者指令計(jì)數(shù)器的值達(dá)到215-1，則向所有處理器核廣播1個(gè)record消息，記錄沖突對(duì)應(yīng)當(dāng)前發(fā)生序的先發(fā)生方(指令計(jì)數(shù)器的值)到對(duì)應(yīng)線程的日志中，并清空讀寫簽名、復(fù)位指令計(jì)數(shù)器.

4) 當(dāng)處理器核收到來自其他處理器核的record消息后，記錄后發(fā)生方(指令計(jì)數(shù)器的值)到所在線程的日志中，并清空讀寫簽名、復(fù)位指令計(jì)數(shù)器.

4.2重演算法

本文提出的內(nèi)存競爭記錄算法在重演時(shí)采用了簡化的生產(chǎn)者和消費(fèi)者模型，為每個(gè)處理器核增加1個(gè)喚醒消息計(jì)數(shù)信號(hào)量輔助實(shí)現(xiàn)確定性重演.該重演算法基于硬件的描述如算法2所示，它詳細(xì)描述了每個(gè)處理器核的狀態(tài)和動(dòng)作.

算法2. 內(nèi)存競爭重演算法.

每個(gè)處理器核的狀態(tài):

IC-指令計(jì)數(shù)器;

WakeC-喚醒消息計(jì)數(shù)器;

WaitC-等待消息計(jì)數(shù)器;

Rflag-讀標(biāo)志，初值為false;

Type-日志類型;

Log-內(nèi)存競爭日志.

當(dāng)收到來自其他處理器核的wakeup一致性消息時(shí) {

WakeC++;

}

執(zhí)行指令 {

if (!Rflag)

entry_old=Log.read(Type,IC);

if (Type=0){

for (i=1;i≤IC;i++) {

執(zhí)行下一條指令;

}

Broadcast(wakeup);

Rflag=true;

} else if (Type=1) {

WaitC++;

for (i=1;i

執(zhí)行下一條指令;

}

entry_new=Log.read(Type,IC);

while (!(Compare(entry_old,entry_new))){

WaitC++;

entry_old=entry_new;

entry_new=Log.read(Type,IC);

}

if (WakeupC≥WaitC) {

執(zhí)行指令I(lǐng)C;

WakeC=WakeC-WaitC;

IC.clear();

WaitC.clear();

}

Rflag=false;

}

}

該重演算法中每個(gè)處理器核所做的動(dòng)作具體描述如下：

1) 當(dāng)處理器核收到來自其他處理器核的喚醒消息wakeup時(shí)，將喚醒消息計(jì)數(shù)信號(hào)量的值加1.

2) 處理器核在執(zhí)行指令前先讀取Rflag標(biāo)志，判斷是否需要從日志中讀取1條記錄，如果需要，則從日志中讀取1條記錄.其中，Rflag的初始值為false；如果處理器核讀取的上一記錄是后發(fā)生方類型，則Rflag=true，否則Rflag=false.這是因?yàn)樘幚砥骱俗x取到后發(fā)生方類型的記錄后，還需要繼續(xù)從日志中讀取記錄，直到讀到1個(gè)與上一記錄不同的記錄，因此，有些記錄已經(jīng)被提前讀出.

3) 判斷讀出的記錄是先發(fā)生方還是后發(fā)生方，如果是先發(fā)生方，則處理器執(zhí)行指令，直至執(zhí)行完畢先發(fā)生方對(duì)應(yīng)的指令后，廣播wakeup消息；如果是后發(fā)生方，處理器則需要做3項(xiàng)處理.

① 執(zhí)行指令到后發(fā)生方的前1條指令.

② 從日志中讀取1條新記錄，判斷此條記錄是否同上一記錄相同，如果相同，說明此條記錄是后發(fā)生方且對(duì)應(yīng)多個(gè)先發(fā)生方，即它需要等待多個(gè)喚醒消息，這時(shí)，將等待消息計(jì)數(shù)器加1，然后重復(fù)步驟②，直至讀到不同的記錄為止.

③ 比較喚醒消息信號(hào)量的值和等待消息計(jì)數(shù)器的值，如果喚醒消息信號(hào)量的值大于或等于等待消息計(jì)數(shù)器的值，則表明該后發(fā)生方已經(jīng)等到所有的喚醒消息，處理器核繼續(xù)執(zhí)行后發(fā)生方對(duì)應(yīng)的指令，并將喚醒消息信號(hào)量的值減去等待消息計(jì)數(shù)器的值，復(fù)位指令計(jì)數(shù)器和等待消息計(jì)數(shù)器，置Rflag=true.

因?yàn)楸疚牟捎玫牟l(fā)式記錄策略所記錄的后發(fā)生方可能會(huì)被重復(fù)記錄多次，如圖4(c)所示，點(diǎn)d會(huì)被記錄2次，因此，在重演階段引入計(jì)數(shù)信號(hào)量對(duì)這種特殊情況進(jìn)行了處理，提高了重演效率.

4.3重演速度分析

本文提出的并發(fā)式記錄策略，同以往的點(diǎn)到點(diǎn)內(nèi)存競爭記錄方法一樣，能夠?qū)崿F(xiàn)指令級(jí)的重演.但因?yàn)樵撚涗洸呗詫⒃S多的非內(nèi)存沖突也假定為內(nèi)存沖突，會(huì)增加重演時(shí)檢查點(diǎn)的次數(shù)，一定程度上減緩了重演速度.然而，相比采用chunk記錄策略的IMRR[7]在重演速度方面具有一定的優(yōu)勢.首先是因?yàn)镃PMRR是以指令為單位，而IMRR則以指令塊為單位；其次，后發(fā)生方僅在等到它所需要的消息后就會(huì)繼續(xù)執(zhí)行，而IMRR后續(xù)chunk要等到所有處理器核發(fā)出chunk-end消息后才能繼續(xù)向前執(zhí)行.

Fig. 6　The hardware configuration.圖6　硬件結(jié)構(gòu)框圖

借助有向無環(huán)圖(DAG)，本文對(duì)并發(fā)點(diǎn)到點(diǎn)內(nèi)存競爭記錄策略的重演速度進(jìn)行進(jìn)一步地分析.對(duì)于CPMRR記錄的內(nèi)存競爭日志，可以映射成1個(gè)DAG：每個(gè)頂點(diǎn)代表日志的記錄點(diǎn)，即先發(fā)生方或后發(fā)生方；連接2個(gè)頂點(diǎn)的邊的權(quán)值表示2個(gè)頂點(diǎn)間的內(nèi)存操作指令的數(shù)目.對(duì)于IMRR，映射的DAG中每個(gè)頂點(diǎn)表示日志中記錄的chunk，因?yàn)楹罄m(xù)chunk需要等到上一時(shí)戳的所有chunk都執(zhí)行結(jié)束后才能開始執(zhí)行.因此，在所映射的DAG中，相同時(shí)戳的chunk可以映射到同一個(gè)頂點(diǎn)；連接2個(gè)頂點(diǎn)的邊的權(quán)重表示chunk的大小，即chunk中包含的內(nèi)存操作指令的數(shù)目.如此，可以通過計(jì)算DAG的關(guān)鍵路徑來比較兩者的重演速度，關(guān)鍵路徑越短，重演速度就更快.圖5給出了將內(nèi)存競爭日志映射成DAG的1個(gè)示例.該示例中，線程i,j,k各執(zhí)行30條內(nèi)存操作指令；圖5(a)和圖5(b)對(duì)應(yīng)CPMRR，圖5(c)和5(d)對(duì)應(yīng)IMRR；在映射后的DAG中，均增加1個(gè)起始頂點(diǎn)s和1個(gè)結(jié)束頂點(diǎn)e.CPMRR中，線程i,j,k分別記錄了10,12,5共3個(gè)記錄點(diǎn)，線程i同線程j和k之間存在先后順序關(guān)系.IMRR中每個(gè)線程分別記錄了時(shí)戳為1(LC=1)和2(LC=2)的2個(gè)chunk，3個(gè)線程中LC=1的chunk分別含10,12,5條內(nèi)存操作指令.由DAG圖可以計(jì)算出2種記錄策略的關(guān)鍵路徑長度分別是35和37，CPMRR的關(guān)鍵路徑要短于IMRR.

Fig. 5　An example of DAG extracted from memory race log.圖5　內(nèi)存競爭日志映射有向無環(huán)圖示例

假設(shè)有m個(gè)線程，CPMRR中所有后發(fā)生方都僅需要等待1個(gè)喚醒消息，各線程執(zhí)行到上一記錄點(diǎn)所需要的時(shí)間分別是{t11,t21,…,tm1}，各線程中上一記錄點(diǎn)到當(dāng)前記錄點(diǎn)的時(shí)間間隔是{t12,t22,…,tm2}.則在CPMRR中，DAG的關(guān)鍵路徑為ti1+tj2，其中i,j∈{1,2,…,m}，而IMRR對(duì)應(yīng)DAG的關(guān)鍵路徑為max{t11,t21,…,tm1}+max{t12,t22,…,tm2}.因此，相比IMRR，該并發(fā)式點(diǎn)到點(diǎn)內(nèi)存競爭記錄重演算法在重演階段等待的時(shí)間更短，在重演速度方面要優(yōu)于IMRR.

4.4硬件結(jié)構(gòu)

結(jié)合上述基于硬件的算法描述，圖6給出了該并發(fā)式內(nèi)存競爭記錄算法基于8核CMP的硬件實(shí)現(xiàn)結(jié)構(gòu)框圖.它為原有系統(tǒng)中的每個(gè)處理器核增加1個(gè)記錄重演模塊，用來實(shí)現(xiàn)內(nèi)存競爭的記錄和重演功能.該記錄重演模塊共包含以下硬件：讀簽名寄存器1個(gè)(RF，256 b)、寫簽名寄存器1個(gè)(WF，1024 b)、指令計(jì)數(shù)器1個(gè)(IC，16 b)、先發(fā)生方寄存器1個(gè)(Pred，16 b)、后發(fā)生方寄存器1個(gè)(Succ，16 b)、等待消息計(jì)數(shù)器1個(gè)(WaitC，16 b)、喚醒消息信號(hào)量寄存器1個(gè)(WakeC，16 b)、記錄類型寄存器1個(gè)(Type，1 b)、讀取標(biāo)志寄存器1個(gè)(Rflag，1 b).其中RF和WF僅用于記錄功能，IC和Type為記錄和重演功能共用，其他部件僅用在重演階段.若不考慮運(yùn)算器和日志緩沖部分，本記錄算法為每個(gè)處理器核增加約171 B的硬件資源.

5仿真結(jié)果

本文采用GEMS[19]對(duì)該并發(fā)式內(nèi)存競爭記錄算法(CPMRR)進(jìn)行了仿真，并與同一配置下基于chunk記錄策略的IMRR[7]的仿真結(jié)果進(jìn)行了比較，同時(shí)，也給出了在硬件消耗方面CPMRR同已有的點(diǎn)到點(diǎn)記錄算法的比較結(jié)果.仿真配置如表1所示，測試負(fù)載選取典型的應(yīng)用于多線程科學(xué)計(jì)算的SPLASH2[20].

Table 1　Key Parameters in GEMS Configuration

下面給出CPMRR在硬件開銷、日志記錄和帶寬開銷方面的仿真結(jié)果：

1) 硬件開銷.CPMRR需要為每個(gè)處理器核添加1對(duì)讀寫簽名，對(duì)于8核的CMP系統(tǒng)，僅增加約171 B的硬件資源，硬件開銷同IMRR相當(dāng).然而，相比已有采用簽名實(shí)現(xiàn)的點(diǎn)到點(diǎn)內(nèi)存競爭記錄機(jī)制[9-12]，硬件開銷顯著降低，約降低了86%.而且，CPMRR為每個(gè)處理器核添加的硬件資源不再與系統(tǒng)中處理器核的數(shù)目相關(guān)，其硬件開銷不會(huì)隨著處理器核數(shù)目的增加而顯著增加.

2) 日志記錄.圖7給出了CPMRR同IMRR之間內(nèi)存競爭記錄次數(shù)和內(nèi)存競爭日志的比較結(jié)果.從圖7(a)可以看出，雖然CPMRR的記錄次數(shù)平均約是IMRR的2倍，但其記錄的日志總體上卻與IMRR相當(dāng)，如圖7(b)所示.這是因?yàn)椋篒MRR中不僅要記錄chunk的大小，為了實(shí)現(xiàn)并行重演還需要記錄chunk的時(shí)戳；而CPMRR采用分布式策略對(duì)日志進(jìn)行了精簡，僅記錄了沖突雙方的指令計(jì)數(shù)值，該計(jì)數(shù)值相當(dāng)于IMRR中chunk的大小.

3) 帶寬開銷.如圖8(a)所示，CPMRR在記錄階段新增加的record消息僅占總一致性請求消息的2.7%，因此，它為8核CMP系統(tǒng)的核間互聯(lián)網(wǎng)絡(luò)帶來的帶寬開銷也較小，如圖8(b)所示，平均帶寬開銷不到1.5%.這是因?yàn)椴l(fā)式內(nèi)存競爭記錄機(jī)制在檢測到內(nèi)存沖突后僅廣播record消息，而該消息內(nèi)容簡單，無需添加指令時(shí)戳.

Fig. 7　Memory race recording performance in CPMRR.圖7　CPMRR日志記錄性能統(tǒng)計(jì)

Fig. 8　The coherence overhead in CPMRR.圖8　CPMRR在一致性協(xié)議方面的開銷

重演時(shí)，CPMRR因?yàn)椴捎昧擞?jì)數(shù)信號(hào)量機(jī)制，僅在執(zhí)行到發(fā)生方時(shí)廣播喚醒消息，且該消息無需標(biāo)記其對(duì)應(yīng)的先發(fā)生方指令時(shí)戳，帶來的帶寬開銷同記錄階段相當(dāng)，約是IMRR重演階段帶寬開銷的20%，如圖9所示.因?yàn)樵贑PMRR中，只有先發(fā)生方執(zhí)行完畢后才廣播wakeup消息，后發(fā)生方收到對(duì)應(yīng)的wakeup消息后方可繼續(xù)向前執(zhí)行，而IMRR在所有并發(fā)chunk執(zhí)行完畢后都要廣播chunk-end消息，直至來自所有線程的chunk-end消息聚齊后系統(tǒng)才能繼續(xù)向前執(zhí)行，相比IMRR，CPMRR很大程度上減少了重演時(shí)的消息數(shù)量.

Fig. 9　The number of replay messages in CPMRR.圖9　CPMRR在重演階段消息數(shù)量統(tǒng)計(jì)

6結(jié)束語

本文為采用監(jiān)聽一致性協(xié)議的CMP系統(tǒng)設(shè)計(jì)了一種基于并發(fā)式記錄策略的點(diǎn)到點(diǎn)內(nèi)存競爭記錄算法.該算法中將原有的點(diǎn)到點(diǎn)記錄策略擴(kuò)展到了所有線程，解決了點(diǎn)到點(diǎn)記錄方式硬件資源消耗較大的問題.記錄日志時(shí)采用分布式記錄策略，有效降低了帶寬開銷.重演時(shí)采用簡單的生產(chǎn)者消費(fèi)者模型，引入了計(jì)數(shù)信號(hào)量機(jī)制，硬件實(shí)現(xiàn)結(jié)構(gòu)簡單，添加的一致性消息少，重演速度快.針對(duì)該記錄算法在8核CMP系統(tǒng)中的仿真結(jié)果表明：該并發(fā)式記錄算法在未增加日志的前提下，有效降低了點(diǎn)到點(diǎn)記錄方式的硬件資源消耗和帶寬開銷.

參考文獻(xiàn)

[1]Aciicmez O, Seifert J. Cheap hardware parallelism implies cheap security[C] //Proc of the 4th Workshop on FDTC 2007. Los Alamitos, CA: IEEE Computer Society, 2007: 80-91

[2]Xu M, Bodik R, Hill M D. A “flight data recorder” for enabling full-system multiprocessor deterministic replay[C] //Proc of the 30th Int Symp on Computer Architecture (ISCA’03). New York: ACM, 2003: 122-135

[3]Montesinos P, Hicks M, King S T, et al. Capo: A software-hardware interface for practical deterministic multiprocessor replay[C] //Proc of the 14th Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS’09). New York: ACM, 2009: 73-84

[4]Nima H, Josep T. Replay debugging: Leveraging record and replay for program debugging[C] //Proc of the 41st Int Symp on Computer Architecture (ISCA’14). New York: ACM, 2014: 455-456

[5]Xu M, Bodik R, Hill M D. A regulated transitive reduction (RTR) for longer memory race recording[C] //Proc of the 12th Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS’06). New York: ACM, 2006: 49-60

[6]Hower D R, Hill M D. Rerun: Exploiting episodes for lightweight memory race recording[C] //Proc of the 35th Int Symp on Computer Architecture (ISCA’08). New York: ACM, 2008: 265-267

[7]Pokam G, Pereira C, Danne K, et al. Architecting a chunk-based memory race recorder in modern CMPs[C] //Proc of the 42nd Int Symp on Microarchitecture (MICRO’09). New York: ACM, 2009: 576-585

[8]Arkaprava B, Jayaram B, Hill M D. Karma: Scalable deterministic record-replay[C] //Proc of the Int Conf on Supercomputing (ICS’11). New York: ACM, 2011: 359-368

[9]Zhu Suxia, Ji Zhenzhou, Liu Tao, et al. Study on memory race recording mechanism in deterministic multi-core replay [J]. Acta Electronica Sinica, 2011, 39 (12): 2748-2754 (in Chinese)(朱素霞, 季振洲, 劉濤, 等. 面向多核程序確定性重演的內(nèi)存競爭記錄機(jī)制研究[J]. 電子學(xué)報(bào), 2011, 39(12): 2748-2754)

[10]Zhu Suxia, Ji Zhenzhou, Liu Tao, et al. CCTR: An efficient point-to-point memory race recorder implemented in chunks [J]. Microprocessors and Microsystems, 2012, 36(6): 510-519

[11]Zhu Suxia, Ji Zhenzhou, Wang Qing. An efficient deterministic record-replay with separate dependencies [J]. Computers & Electrical Engineering, 2013, 39(2): 175-189

[12]Zhu Suxia, Ji Zhenzhou, Li Dong, et al. A cyclic memory race recording algorithm implemented with hardware signatures [J]. Journal of Computer Research and Development, 2014, 51(5): 1149-1157 (in Chinese)(朱素霞, 季振洲, 李東, 等. 基于硬件簽名的循環(huán)式內(nèi)存競爭記錄算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(5): 1149-1157)

[13]Pokam G, Danne K, Pereira C, et al. QuickRec: Prototyping an Intel architecture extension for record and replay of multithreaded programs[C] //Proc of the 40th Int Symp on Computer Architecture (ISCA’13). New York: ACM, 2013: 643-654

[14]Chen Y, Hu W, Chen T, et al. LReplay: A pending period based deterministic replay scheme[C] //Proc of the 37th Int Symp on Computer Architecture (ISCA'10). New York: ACM, 2010: 187-197

[15]Gao X, Chen Y J, Wang H D, et al. System architecture of Godson-3 multi-core processors [J]. Journal of Computer Science and Technology, 2010, 25(2): 181-191

[16]Netzer R H B, Miller B P. What are race conditions?: Some issues and formalizations [J]. ACM Letters on Programming Languages and Systems (LOPLAS), 1992, 1(1): 74-88

[17]Netzer R H B. Optimal tracing and replay for debugging shared-memory parallel programs[C] //Proc of the ACM/ONR Workshop on Parallel and Distributed Debugging (PADD’93). New York: ACM, 1993: 1-11

[18]Lamport L. Time, clocks, and the ordering of events in a distributed system [J]. Communications of the ACM, 1978, 21(7): 558-565

[19]Martin M M K, Sorin D J, Beckmann B M, et al. Multifacet’s general execution-driven multiprocessor simulator (GEMS) toolset [J]. 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[C] //Proc of the 22nd Int Symp on Computer Architecture (ISCA’95). New York: ACM, 1995: 24-36

Zhu Suxia, born in 1978. PhD. Associate professor in Harbin University of Science and Technology. Her research interests include cache coherence protocol, concurrent bug detection, and parallel computing.

Chen Deyun, born in 1962. Professor and PhD supervisor in Harbin University of Science and Technology. His main research interests include image processing, detection and imaging.

Ji Zhenzhou, born in 1965.Professor and PhD supervisor in Harbin Institute of Technology. His main research interests include parallel architecture, parallel computing and network security.

Sun Guanglu, born in 1979. PhD. Professor in Harbin University of Science and Technology. His main research interests include network security, pattern recognition and machine learning.

Zhang Hao, born in 1981. PhD and associate professor in Institute of Computing Technology, Chinese Academy of Sciences. His research interests include high throughput CPU microarchitectures.

A Concurrent Memory Race Recording Algorithm for Snoop-Based Coherence

Zhu Suxia1,2, Chen Deyun2, Ji Zhenzhou3, Sun Guanglu2, and Zhang Hao4

1(PostdoctoralResearchStation,SchoolofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080)2(SchoolofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080)3(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)4(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190)

AbstractMemory race record-replay is an important technology to resolve the nondeterminism of multi-core programs. Because of high hardware overhead, the existing memory race recorders based on point-to-point logging approach are difficult to be applied to the practical modern chip multiprocessors. In order to reduce the hardware overhead of point-to-point logging approach, a novel memory race recording algorithm implemented in concurrent logging strategy for chip multiprocessors adopting snoop-based cache coherence protocol is proposed. This algorithm records the current execution points of all threads concurrently when detecting a memory conflict. It extends the point-to-point memory race relationship between two threads to all threads in recording phase, reducing hardware overhead significantly. It also uses distributed logging mechanism to record memory races to reduce bandwidth overhead effectively in the premise of not increasing the memory race log. When replaying, this algorithm uses a simplified producer-consumer model and introduces a counting semaphore for each processor core to ensure deterministic replay, improving replay speed and reducing coherence bandwidth overhead. The simulation results on 8-core chip multiprocessor (CMP) system show that this concurrent recording algorithm based on point-to-point logging approach adds about 171 B hardware for each processor, and records about 2.3 B log per thousand memory instructions and adds less than 1.5% additional interconnection bandwidth overhead.

Key wordschip multiprocessor (CMP); multi-core program; deterministic replay; memory race recording; memory conflict detection; snoop-based coherence protocol

收稿日期：2015-02-05；修回日期：2015-07-07

基金項(xiàng)目：國家自然科學(xué)青年基金項(xiàng)目(61502123)；國家自然科學(xué)基金項(xiàng)目(61173024)；國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2011CB302501)；黑龍江省青年科學(xué)基金項(xiàng)目(QC2015084)；中國博士后科學(xué)基金項(xiàng)目(2015M571429)

中圖法分類號(hào)TP303

This work was supported by the National Natural Science Foundation of China for Youths (61502123), the National Natural Science Foundation of China (61173024), and the National Basic Research Program of China (973 Program) (2011CB302501), Heilongjiang Province Science Foundation for Youths (QC2015084), the China Postdoctoral Science Foundation (2015M571429).