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

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

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

?

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

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

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

摘要內(nèi)存競爭記錄是解決多核程序執(zhí)行不確定性的關(guān)鍵技術(shù)，然而現(xiàn)有點到點的內(nèi)存競爭記錄機制帶來的硬件開銷大，難以應(yīng)用到實際的片上多核處理器系統(tǒng)中.以降低點到點內(nèi)存競爭記錄方式的硬件開銷為出發(fā)點，為采用監(jiān)聽一致性協(xié)議的片上多核處理器(chip multiprocessor, CMP)系統(tǒng)設(shè)計了基于并發(fā)記錄策略的點到點內(nèi)存競爭記錄算法.該記錄算法將兩兩線程間點到點的內(nèi)存競爭關(guān)系擴展到所有線程，采用分布式記錄方法為每個線程記錄一個由內(nèi)存競爭關(guān)系的一方構(gòu)成的內(nèi)存競爭日志；重演時采用簡化的生產(chǎn)者消費者模型，確保了確定性重演的實現(xiàn)，有效降低了硬件消耗和帶寬開銷.在8核處理器系統(tǒng)中的仿真結(jié)果表明，該并發(fā)式點到點內(nèi)存競爭記錄算法為每個處理器核添加硬件資源約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)試、容錯[1]和安全[2]等都變得異常困難.內(nèi)存競爭記錄和重演是解決這一問題的有效手段.內(nèi)存競爭記錄和重演機制通過在多核程序原始執(zhí)行階段記錄下線程間的內(nèi)存競爭順序，在重演階段依據(jù)所記錄的內(nèi)存競爭順序復(fù)現(xiàn)原始的執(zhí)行順序，從而輔助實現(xiàn)多核程序的確定性重演.截至目前為止，研究者們已經(jīng)提出了眾多軟件[3-4]和硬件[2,5-13]實現(xiàn)的內(nèi)存競爭記錄機制.硬件實現(xiàn)方案通過為原有CMP系統(tǒng)增加新的硬件資源實現(xiàn)內(nèi)存競爭的記錄和重演，具有效率高、開銷低等優(yōu)點，應(yīng)用前景廣闊.硬件實現(xiàn)的內(nèi)存競爭記錄方案中，主要有點到點記錄方式[2,5,9-12]和chunk記錄方式[6-8,13]2大類.點到點的記錄方式以指令為粒度，記錄線程間內(nèi)存沖突對應(yīng)的依賴關(guān)系，無論是記錄還是重演，都具有良好的并行性，但硬件資源消耗較大，影響了它在實際CMP系統(tǒng)中的應(yīng)用.chunk記錄方式使用較少的硬件資源記錄線程間無沖突的指令塊，按照chunk時戳的順序?qū)崿F(xiàn)確定性重演.目前這2種記錄方式針對基于目錄一致性協(xié)議的CMP系統(tǒng)已經(jīng)取得了豐富的研究成果[2,5-6,8-12]，但是針對采用監(jiān)聽一致性協(xié)議系統(tǒng)的研究還有待進一步挖掘，因為實際的CMP系統(tǒng)大都采用了基于監(jiān)聽的cache一致性協(xié)議.因此，研究支持監(jiān)聽一致性協(xié)議的內(nèi)存競爭記錄和重演機制更具現(xiàn)實意義.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

檢測到內(nèi)存沖突消息在實現(xiàn)時無需改變監(jiān)聽一致性協(xié)議的結(jié)構(gòu)，而是僅在現(xiàn)有協(xié)議基礎(chǔ)上增加了1個新型的請求類消息，取名為record.因為采用分布式日志記錄策略記錄內(nèi)存競爭，無需傳送內(nèi)存操作指令的時戳，該消息會帶來較小的帶寬開銷.

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

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

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

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

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

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

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

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

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

4.1記錄算法

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

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

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

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

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

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

RF-讀簽名;

WF-寫簽名;

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

在內(nèi)存指令提交時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時 {

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一致性消息時 {

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

WF.clear();

RF.clear();

IC.clear();

}

該記錄算法中每個處理器核做4個動作：

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

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

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

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

4.2重演算法

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

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

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

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

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

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

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

Type-日志類型;

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

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

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;

}

}

該重演算法中每個處理器核所做的動作具體描述如下：

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

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

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

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

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

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

因為本文采用的并發(fā)式記錄策略所記錄的后發(fā)生方可能會被重復(fù)記錄多次，如圖4(c)所示，點d會被記錄2次，因此，在重演階段引入計數(shù)信號量對這種特殊情況進行了處理，提高了重演效率.

4.3重演速度分析

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

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

借助有向無環(huán)圖(DAG)，本文對并發(fā)點到點內(nèi)存競爭記錄策略的重演速度進行進一步地分析.對于CPMRR記錄的內(nèi)存競爭日志，可以映射成1個DAG：每個頂點代表日志的記錄點，即先發(fā)生方或后發(fā)生方；連接2個頂點的邊的權(quán)值表示2個頂點間的內(nèi)存操作指令的數(shù)目.對于IMRR，映射的DAG中每個頂點表示日志中記錄的chunk，因為后續(xù)chunk需要等到上一時戳的所有chunk都執(zhí)行結(jié)束后才能開始執(zhí)行.因此，在所映射的DAG中，相同時戳的chunk可以映射到同一個頂點；連接2個頂點的邊的權(quán)重表示chunk的大小，即chunk中包含的內(nèi)存操作指令的數(shù)目.如此，可以通過計算DAG的關(guān)鍵路徑來比較兩者的重演速度，關(guān)鍵路徑越短，重演速度就更快.圖5給出了將內(nèi)存競爭日志映射成DAG的1個示例.該示例中，線程i,j,k各執(zhí)行30條內(nèi)存操作指令；圖5(a)和圖5(b)對應(yīng)CPMRR，圖5(c)和5(d)對應(yīng)IMRR；在映射后的DAG中，均增加1個起始頂點s和1個結(jié)束頂點e.CPMRR中，線程i,j,k分別記錄了10,12,5共3個記錄點，線程i同線程j和k之間存在先后順序關(guān)系.IMRR中每個線程分別記錄了時戳為1(LC=1)和2(LC=2)的2個chunk，3個線程中LC=1的chunk分別含10,12,5條內(nèi)存操作指令.由DAG圖可以計算出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個線程，CPMRR中所有后發(fā)生方都僅需要等待1個喚醒消息，各線程執(zhí)行到上一記錄點所需要的時間分別是{t11,t21,…,tm1}，各線程中上一記錄點到當(dāng)前記錄點的時間間隔是{t12,t22,…,tm2}.則在CPMRR中，DAG的關(guān)鍵路徑為ti1+tj2，其中i,j∈{1,2,…,m}，而IMRR對應(yīng)DAG的關(guān)鍵路徑為max{t11,t21,…,tm1}+max{t12,t22,…,tm2}.因此，相比IMRR，該并發(fā)式點到點內(nèi)存競爭記錄重演算法在重演階段等待的時間更短，在重演速度方面要優(yōu)于IMRR.

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

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

5仿真結(jié)果

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

Table 1　Key Parameters in GEMS Configuration

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

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

2) 日志記錄.圖7給出了CPMRR同IMRR之間內(nèi)存競爭記錄次數(shù)和內(nèi)存競爭日志的比較結(jié)果.從圖7(a)可以看出，雖然CPMRR的記錄次數(shù)平均約是IMRR的2倍，但其記錄的日志總體上卻與IMRR相當(dāng)，如圖7(b)所示.這是因為：IMRR中不僅要記錄chunk的大小，為了實現(xiàn)并行重演還需要記錄chunk的時戳；而CPMRR采用分布式策略對日志進行了精簡，僅記錄了沖突雙方的指令計數(shù)值，該計數(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%.這是因為并發(fā)式內(nèi)存競爭記錄機制在檢測到內(nèi)存沖突后僅廣播record消息，而該消息內(nèi)容簡單，無需添加指令時戳.

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

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

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

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

6結(jié)束語

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

參考文獻

[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]. 電子學(xué)報, 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]. 計算機研究與發(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

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

中圖法分類號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).