面向多核處理器的可配置緩存一致性協(xié)議設(shè)計(jì)與實(shí)現(xiàn)

陳志強(qiáng) 周宏偉 馮權(quán)友 鄧讓鈺

(國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073)

(czq19982016＠163.com)

共享主存多核處理器在并行處理中具有很大優(yōu)勢(shì),它維護(hù)1塊完整的地址空間,處理器核通過load和store指令訪問共享主存空間,每個(gè)處理器核有單獨(dú)的私有緩存,都可以緩存數(shù)據(jù),1個(gè)數(shù)據(jù)可以擁有多個(gè)副本,它們之間可能相同,也可能不同.層次化存儲(chǔ)在提高性能的同時(shí)必須保證正確性,通用的方案是通過緩存一致性協(xié)議來解決數(shù)據(jù)不一致[1].

根據(jù)實(shí)現(xiàn)不同,一致性協(xié)議可以分為2類,監(jiān)聽協(xié)議(snoop-based protocol)和基于目錄的協(xié)議(directory-based protocol).監(jiān)聽協(xié)議將一致性事務(wù)直接廣播給最后一級(jí)緩存(last level cache,LLC)和主存,通常是通過總線結(jié)構(gòu).這類協(xié)議受限于總線有限的帶寬以及總線所能掛載的最大負(fù)載數(shù)量,限制了它的可擴(kuò)展性,這種特性使它不適用于核數(shù)較多的處理器.另一種基于目錄的一致性協(xié)議[2],每個(gè)內(nèi)存塊對(duì)應(yīng)1個(gè)目錄項(xiàng),目錄項(xiàng)中記錄狀態(tài)信息和共享信息.操作數(shù)據(jù)時(shí),向擁有數(shù)據(jù)副本的緩存直接發(fā)送請(qǐng)求.當(dāng)下,包含32及以上核心數(shù)目的多核處理器成為主流,相較于基于總線的監(jiān)聽協(xié)議,基于目錄的一致性協(xié)議具有更好的可擴(kuò)展性.隨著處理器核心數(shù)量的進(jìn)一步增加,基于目錄的一致性協(xié)議優(yōu)勢(shì)更加明顯[3].

為了避免廣播操作,需要知道當(dāng)前數(shù)據(jù)副本的位置信息,這些信息記錄在目錄項(xiàng)中.對(duì)數(shù)據(jù)進(jìn)行操作時(shí),可以直接根據(jù)目錄項(xiàng)中的記錄,發(fā)出點(diǎn)對(duì)點(diǎn)的請(qǐng)求通信,避免了低效的廣播操作.代價(jià)是需要額外的空間來存儲(chǔ)目錄項(xiàng),目錄項(xiàng)中記錄緩存副本的共享信息.在共享主存多核處理器中,一個(gè)數(shù)據(jù)最多有N個(gè)副本,N為處理器核數(shù)目,目錄項(xiàng)中最多需要容納N個(gè)地址空間,同時(shí)目錄數(shù)量和N成正比,因此總的空間開銷和N2成正比.這種目錄存儲(chǔ)方式會(huì)造成巨大的存儲(chǔ)空間開銷.在實(shí)際程序運(yùn)行中,根據(jù)程序訪問的局部性原理,一段時(shí)間內(nèi)只有部分處理核心共享1個(gè)數(shù)據(jù)塊,同時(shí)存在N個(gè)副本的情況非常罕見,因此提出了有限目錄,數(shù)據(jù)塊在緩存中存在的副本數(shù)量有限,假設(shè)為T(T＜N).T最終取決于系統(tǒng)架構(gòu),這樣就可以解決目錄空間過大的問題.

在基于目錄的一致性協(xié)議中,根據(jù)目錄的分布方式可以分為集中式目錄和分布式目錄[4-7].集中式目錄用1個(gè)中心目錄存儲(chǔ)所有副本信息,可以提供維持一致性所需的全部信息.這種目錄的容量大,查找時(shí)間較長(zhǎng),查找共享數(shù)據(jù)的過程中會(huì)有較多的沖突.優(yōu)勢(shì)在于架構(gòu)清晰,易于控制.分布式目錄按照一定的分體方式位于多核處理器芯片的不同位置,每個(gè)分體較小,可以實(shí)現(xiàn)更快的查找速度,不足之處為訪問不同目錄體時(shí)根據(jù)片上網(wǎng)絡(luò)延遲的不同而具有一定的延遲差.隨著多核處理器核心數(shù)量增加,芯片的面積越來越大,在芯片上實(shí)現(xiàn)集中式目錄的物理實(shí)現(xiàn)難度越來越大,分布式目錄成為主流.Knights Landing(KNL)是Intel針對(duì)高性能計(jì)算發(fā)布的架構(gòu),使用基于目錄的緩存一致性協(xié)議MESIF.KNL為了緩解集中式目錄的訪問瓶頸,采用了分布式目錄[8-9].

多核處理器研發(fā)周期長(zhǎng)、難度大[10],傳統(tǒng)上,一致性協(xié)議的驗(yàn)證主要通過模擬,通過運(yùn)行基準(zhǔn)測(cè)試程序并檢查輸出結(jié)果以驗(yàn)證一致性是否正確.然而測(cè)試程序無法有效模擬所有情況,之前的工作表明,即使經(jīng)過廣泛的模擬[11-13],一致性協(xié)議仍然可能有缺陷.死鎖問題是緩存一致性協(xié)議設(shè)計(jì)中的難題,與多核處理器的體系結(jié)構(gòu)密切相關(guān),一旦出現(xiàn)死鎖,可能導(dǎo)致整個(gè)芯片設(shè)計(jì)失敗.面向多核處理器的防止緩存一致性協(xié)議死鎖的方法主要是通過構(gòu)建多個(gè)虛網(wǎng)絡(luò),不同類型的報(bào)文通過專有的通道.虛通道可以有效解決一致性協(xié)議死鎖問題,但是會(huì)帶來較高的功耗與面積開銷,在多核處理器中,這種不利影響尤為突出.在DRAIN[14-15]中提出了一種解決這類死鎖的方法,通過周期性的操作使報(bào)文沿著固定路徑前進(jìn)1跳,從而破除已經(jīng)存在或潛在的循環(huán)依賴關(guān)系.這種方法基于死鎖產(chǎn)生的概率低,在犧牲部分性能的情況下,取得了較低的功耗與面積開銷.

本文面向基于分布式目錄的多核處理器體系結(jié)構(gòu),提出一種動(dòng)態(tài)可配置的緩存一致性協(xié)議的設(shè)計(jì)與實(shí)現(xiàn)方案,該方案通過在分體目錄控制器中增加微操作機(jī)制,實(shí)現(xiàn)緩存一致性協(xié)議的動(dòng)態(tài)配置,可以增加多核系統(tǒng)的協(xié)議容錯(cuò)性,并且能夠在芯片流片后解決可能發(fā)生的協(xié)議死鎖問題.

1 動(dòng)態(tài)可配置緩存一致性協(xié)議

MSI,MESI和MOESI是常見的一致性協(xié)議.MESI在MSI的基礎(chǔ)上將獨(dú)占態(tài)E從共享態(tài)S中剝離出來,這樣對(duì)E狀態(tài)進(jìn)行修改就可以避免監(jiān)聽操作.MOESI進(jìn)一步增加了擁有者O狀態(tài),O狀態(tài)是S和修改態(tài)M的混合,明確數(shù)據(jù)的所有權(quán),可以與主存不一致,避免了不必要的寫回操作.3種協(xié)議各有優(yōu)缺點(diǎn):MSI協(xié)議支持緩存塊的多個(gè)副本,將M和S狀態(tài)進(jìn)行了區(qū)分;不足之處在于存在不必要的作廢廣播報(bào)文等.MESI將E狀態(tài)進(jìn)一步區(qū)分出來,可以減少不必要的監(jiān)聽操作;不足之處在于M和E狀態(tài)的沖突等.MOESI進(jìn)一步增加了O狀態(tài),從M轉(zhuǎn)換為S時(shí),避免了不必要的寫回操作;不足之處在于在讀請(qǐng)求時(shí),每個(gè)副本都會(huì)發(fā)回?cái)?shù)據(jù),造成報(bào)文擁擠[16-17].

協(xié)議的狀態(tài)越多,狀態(tài)轉(zhuǎn)換的狀態(tài)機(jī)和協(xié)議的處理流程就越復(fù)雜[18],設(shè)計(jì)與驗(yàn)證的難度越大.為了提高緩存一致性協(xié)議設(shè)計(jì)的靈活性,避免由于協(xié)議與體系結(jié)構(gòu)適配方面的疏漏導(dǎo)致的一致性協(xié)議功能和性能問題,本文提出動(dòng)態(tài)可配置緩存一致性協(xié)議的設(shè)計(jì)思路.核心思想是:協(xié)議的狀態(tài)和一致性處理的流程均可配置,能夠適用于不同的多核處理器體系結(jié)構(gòu).同時(shí),能夠根據(jù)系統(tǒng)結(jié)構(gòu)對(duì)功能和性能的不同需求,實(shí)現(xiàn)功能容錯(cuò)和性能調(diào)優(yōu).

協(xié)議狀態(tài)的轉(zhuǎn)換主要由LLC負(fù)責(zé),狀態(tài)轉(zhuǎn)換的條件除了依賴處理器核的訪存請(qǐng)求外,還依賴于來自根節(jié)點(diǎn)(home node,HN)目錄控制器的監(jiān)聽請(qǐng)求和監(jiān)聽?wèi)?yīng)答報(bào)文.

根據(jù)不同的系統(tǒng)架構(gòu),節(jié)點(diǎn)中緩存行的狀態(tài)轉(zhuǎn)換可以配置,由具體的一致性協(xié)議物理實(shí)現(xiàn)決定.例如,對(duì)于MOESI協(xié)議,當(dāng)M狀態(tài)遇到獲取數(shù)據(jù)請(qǐng)求(GetS)時(shí),通常是轉(zhuǎn)換為O狀態(tài),也可以配置轉(zhuǎn)換為S狀態(tài),協(xié)議退回到MESI協(xié)議:M轉(zhuǎn)換為O,可以避免不必要的寫回操作,但是在讀失效時(shí)需要多個(gè)副本共同響應(yīng),對(duì)片上網(wǎng)絡(luò)(network on chip,NoC)的報(bào)文壓力增加;M轉(zhuǎn)換為S,需要在返回?cái)?shù)據(jù)時(shí)進(jìn)行寫回操作,不過可以僅從1個(gè)副本獲得數(shù)據(jù),對(duì)片上網(wǎng)絡(luò)的報(bào)文壓力小.2種配置對(duì)于訪存的壓力和片上網(wǎng)絡(luò)的壓力各有不同的影響,具體如何配置取決于具體架構(gòu)實(shí)現(xiàn).

除了協(xié)議狀態(tài)的可配置,一致性處理流程可配置能夠進(jìn)一步提高協(xié)議處理的靈活性.優(yōu)勢(shì)在于可以針對(duì)具體操作做出優(yōu)化并且極大增加系統(tǒng)的容錯(cuò)性,甚至可以在CPU流片后進(jìn)行一致性協(xié)議的修改與完善.可配置流程的工作過程說明為:

1)寫回操作協(xié)議流程可配置

圖1表示的是2種HN寫回(WB)從節(jié)點(diǎn)(slave node,SN)操作流程的對(duì)比.圖1(a)為WB事務(wù)處理流程,圖1(b)為WBD(WB_Data)事務(wù)處理流程.

Fig.1 Comparison on protocol flows between WB and WBD圖1 WB和WBD協(xié)議流程對(duì)比

如圖1所示,WB事務(wù)需要SN有接收空間,并返回對(duì)應(yīng)的ID號(hào),HN才會(huì)發(fā)出數(shù)據(jù)報(bào)文,這種協(xié)議適用于HN和SN通過NoC網(wǎng)絡(luò)連接的架構(gòu),如果SN沒有足夠的緩沖空間來容納報(bào)文,多余的報(bào)文留存在片上網(wǎng)絡(luò)中,可能導(dǎo)致死鎖.WBD事務(wù)直接發(fā)出帶有數(shù)據(jù)的報(bào)文,這種協(xié)議適用于HN和SN直接相連的架構(gòu).協(xié)議流程的靈活配置增大了對(duì)不同架構(gòu)的適應(yīng)能力,使其具有良好的可擴(kuò)展性.

2)LLC寫回操作可配置

一致性協(xié)議的驗(yàn)證比較困難,特別對(duì)于采用不維序片上網(wǎng)絡(luò)的多核處理器系統(tǒng).一致性協(xié)議存在的缺陷可能導(dǎo)致整個(gè)CPU設(shè)計(jì)的失敗,圖2展示了Sun公司的可擴(kuò)展共享主存多處理器S3.mp中存在的一個(gè)一致性協(xié)議缺陷[12].

Fig.2 Data inconsistency caused by stale write-back圖2 寫回競(jìng)爭(zhēng)導(dǎo)致的數(shù)據(jù)不一致性

圖2中,P0擁有臟數(shù)據(jù),寫回請(qǐng)求(MEMORY_WB)正在等待根節(jié)點(diǎn)(Home)的完成響應(yīng),因此P0暫時(shí)保留了臟數(shù)據(jù).此時(shí)P1請(qǐng)求獲得緩存行的數(shù)據(jù),向Home節(jié)點(diǎn)發(fā)送請(qǐng)求(Request),Home向P0轉(zhuǎn)發(fā)請(qǐng)求(FW_Request),隨后P1從P0接收到數(shù)據(jù),然后P1重新寫數(shù)據(jù),接著向Home節(jié)點(diǎn)發(fā)出寫回請(qǐng)求.此時(shí)P0和P1發(fā)出的寫請(qǐng)求就會(huì)產(chǎn)生競(jìng)爭(zhēng),如果P1的請(qǐng)求獲勝,P0接下來的寫就會(huì)將P1最新的數(shù)據(jù)覆蓋掉.注意到,一系列合法操作,導(dǎo)致最新數(shù)據(jù)可能被覆蓋.這種一致性協(xié)議設(shè)計(jì)不足導(dǎo)致的缺陷,造成了嚴(yán)重的后果.可配置一致性協(xié)議通過配置協(xié)議處理流程,可以修改為P0具有數(shù)據(jù)的所有權(quán),其他處理器讀取該臟數(shù)據(jù)后僅僅共享使用,不負(fù)責(zé)寫回.這樣就可以避免寫回競(jìng)爭(zhēng),從而解決設(shè)計(jì)缺陷.

3)I/O寫數(shù)據(jù)合并可配置

一般情況下,I/O寫主存時(shí),如果此時(shí)LLC中對(duì)應(yīng)緩存行為臟數(shù)據(jù),需要等待LLC的臟數(shù)據(jù)寫回之后,再將I/O的數(shù)據(jù)寫主存,如圖3所示:

Fig.3 The conflict between I/O and LLC圖3 I/O寫數(shù)據(jù)與LLC臟數(shù)據(jù)的沖突

2次相連的寫主存操作會(huì)帶來較大的訪存開銷[19],考慮到LLC寫入的數(shù)據(jù)馬上被I/O的數(shù)據(jù)覆蓋,如果I/O寫與LLC的寫回均是緩存行對(duì)齊的,那么協(xié)議可以配置為將2次寫操作合并,直接將I/O的數(shù)據(jù)寫回主存,而之前的LLC的寫回操作可以被丟棄,這樣就可以減少1次寫主存操作.

但是,由于I/O寫操作支持對(duì)緩存行的部分字節(jié)寫.因此存在這樣的情況:I/O只修改了緩存行中的部分字節(jié),而LLC中M狀態(tài)下該緩存行保存了I/O部分寫的字節(jié)以外的最新數(shù)據(jù),因此這種情況下LLC的寫回操作不能被丟棄,否則會(huì)導(dǎo)致部分LLC臟數(shù)據(jù)沒能寫回主存,造成數(shù)據(jù)錯(cuò)誤.協(xié)議可配置特性可以配置是否進(jìn)行數(shù)據(jù)合并協(xié)議優(yōu)化,在保證協(xié)議正確前提下提高性能,在協(xié)議處理有漏洞的情況下能夠回退到LLC和I/O依次寫回?cái)?shù)據(jù)到主存,以確保協(xié)議執(zhí)行的正確性.

以上僅列出了3種協(xié)議可配置場(chǎng)景,增強(qiáng)了協(xié)議的容錯(cuò)性以及對(duì)不同架構(gòu)的適應(yīng)能力.

2 可配置協(xié)議分布式目錄控制器

為了實(shí)現(xiàn)可配置協(xié)議,我們?cè)O(shè)計(jì)了可配置協(xié)議分布式目錄控制器(configurable distribute directory unit,CDDU),引入了微操作機(jī)制.CDDU的總體結(jié)構(gòu)如圖4所示.流水線共8級(jí),分別是:目錄查找、目錄讀出、數(shù)據(jù)校驗(yàn)、數(shù)據(jù)糾錯(cuò)、目錄比較、目錄命中、目錄產(chǎn)生和目錄寫入.目錄查找、目錄讀出、數(shù)據(jù)校驗(yàn)、數(shù)據(jù)糾錯(cuò)、目錄比較、目錄命中等流程和常見的基于目錄的一致性協(xié)議大致相同,不同之處在于目錄產(chǎn)生階段.一般情況下,目錄產(chǎn)生由硬件實(shí)現(xiàn),速度較快,不足之處在于難以修改.引入微操作設(shè)計(jì)后,可以通過設(shè)置微程序來改變使能信號(hào),從而改變目錄產(chǎn)生過程,實(shí)現(xiàn)一致性協(xié)議的可配置.這種設(shè)計(jì)帶來的不足在于微程序表帶來的額外開銷以及微程序控制相較于硬布線控制的速度較慢.

Fig.4 The pipeline structure of CDDU圖4 CDDU的總體結(jié)構(gòu)

CDDU的核心功能在于目錄表和微操作表.

1)目錄表記錄緩存中數(shù)據(jù)副本的使用情況,并且根據(jù)當(dāng)前命令和目錄狀態(tài)進(jìn)行跟蹤與修改,維護(hù)LLC的數(shù)據(jù)一致性.由于目錄項(xiàng)空間大小有限,只能存儲(chǔ)部分緩存行信息,這就需要進(jìn)行目錄項(xiàng)替換.LLC由多核共享,多個(gè)核心可能同時(shí)訪問1個(gè)緩存行,這就涉及到目錄項(xiàng)的沖突.目錄表需要提供目錄項(xiàng)的替換和沖突信息,由多路選擇器選擇合適的報(bào)文進(jìn)行處理.

2)微操作表用于實(shí)現(xiàn)微操作機(jī)制.微操作表中保存著用于配置一致性協(xié)議流程的微程序代碼,是實(shí)現(xiàn)微操作設(shè)計(jì)的重要組件,其詳細(xì)結(jié)構(gòu)如圖5所示.微程序地址空間的組織形式類似于鏈表,每段微程序執(zhí)行完畢后,根據(jù)微程序地址確定下一段微程序的起始地址,這樣的優(yōu)勢(shì)在于增加微程序執(zhí)行的靈活性以及增加微程序的尋址空間.不同微程序會(huì)設(shè)置不同的使能信號(hào),動(dòng)態(tài)可配置一致性協(xié)議的實(shí)現(xiàn)就是基于不同使能信號(hào)的組合.例如ACK_en使能信號(hào)可以控制報(bào)文是否需要Ack響應(yīng).TAG_en控制標(biāo)志位的寫;FWGETS_en控制是否發(fā)出FWGETS請(qǐng)求;GETS_en控制是否發(fā)出GETS;DATA_en控制是否返回?cái)?shù)據(jù);MEMACK_en控制是否返回MEMACK;INV_en控制INV信號(hào);INVACK_en控制是否返回INVACK;MEMDATA_en控制是否返回MEMDATA.不同使能信號(hào)的自由組合就是目錄控制器靈活性的來源.

Fig.5 The structure of micro-operation table圖5 微操作表的結(jié)構(gòu)

相較于硬布線控制,微程序便于修改的代價(jià)是會(huì)帶來較慢的執(zhí)行速度.因此我們?cè)贑DDU中設(shè)計(jì)了調(diào)試模式,把微操作機(jī)制作為冗余設(shè)計(jì),希望在保證性能的前提下,實(shí)現(xiàn)以空間代價(jià)換取較高的容錯(cuò)性.一致性事務(wù)在執(zhí)行前會(huì)判斷是否進(jìn)入調(diào)試模式,判斷依據(jù)可以根據(jù)不同架構(gòu)進(jìn)行定制設(shè)計(jì).

3 微操作機(jī)制解決協(xié)議級(jí)死鎖

死鎖問題是多核處理器片上網(wǎng)絡(luò)和一致性協(xié)議設(shè)計(jì)的關(guān)鍵.死鎖的原因是形成了循環(huán)依賴,而一致性協(xié)議的事務(wù)處理流程中本身存在依賴關(guān)系,更容易產(chǎn)生死鎖.由于NoC網(wǎng)絡(luò)的延遲,一致性協(xié)議的報(bào)文并不總能按序到達(dá),這就導(dǎo)致可能請(qǐng)求報(bào)文先于響應(yīng)報(bào)文到達(dá)目錄,從而堵塞響應(yīng)報(bào)文導(dǎo)致死鎖.

微操作機(jī)制為協(xié)議實(shí)現(xiàn)提供了更好的靈活性,能夠用于協(xié)議性能優(yōu)化和容錯(cuò).特別是為解決協(xié)議級(jí)死鎖提供了一種新的方式.下面介紹通過微操作機(jī)制在防死鎖方面的重要功能.

傳統(tǒng)的解決死鎖的方法包括轉(zhuǎn)彎模型(turn model)、逃逸虛通道(escape virtual channel)等[20-21],但是由于一致性報(bào)文之間的依賴關(guān)系,這些方法并不適用于解決協(xié)議級(jí)別的死鎖.目前通用的方法是構(gòu)建多個(gè)虛網(wǎng)絡(luò),從根源上避免了死鎖.虛網(wǎng)絡(luò)由不相交的虛通道組成,每個(gè)虛網(wǎng)絡(luò)只能被一種類型的報(bào)文使用,因此不同類型的報(bào)文不可能形成閉環(huán).構(gòu)建多個(gè)虛網(wǎng)絡(luò)的代價(jià)是需要大量的緩沖區(qū),造成較高的面積與功耗開銷.在DRAIN[14-15]中提出了一種低代價(jià)的死鎖解決方案,該方案基于死鎖產(chǎn)生的概率低,應(yīng)該以較低的代價(jià)來解決小概率問題,因此省去了復(fù)雜的死鎖避免以及死鎖檢測(cè)機(jī)制,而是以周期性的循環(huán)操作來破除潛在的死鎖依賴關(guān)系.動(dòng)態(tài)可配置緩存一致性協(xié)議設(shè)計(jì)可以靈活配置一致性協(xié)議,用于解決死鎖問題.如圖1中WBD是一種優(yōu)化實(shí)現(xiàn),這種優(yōu)化方案可以有效降低延遲,提高性能.這種優(yōu)化方案取得良好效果的同時(shí),也帶來了死鎖隱患.

Fig.6 Deadlock caused by shared response channel圖6 由共享響應(yīng)通道引起的死鎖

圖6為我們?cè)陲w騰64核處理器研發(fā)過程中在芯片流片前驗(yàn)證時(shí)發(fā)現(xiàn)的一種死鎖場(chǎng)景.該處理器的體系結(jié)構(gòu)抽象為:8個(gè)路由器(router,R)、8個(gè)HN,8個(gè)SN.由于布局原因,SN2與SN3均與R3連接,SN4與SN5均與R4連接.H N2訪問SN2以及H N5訪問SN5需要通過片上網(wǎng)絡(luò)的路由器之間的鏈路訪問.根據(jù)第1節(jié)的分析,為了提高替換操作協(xié)議性能,希望能夠采用WBD.由于WBD事務(wù)中寫回請(qǐng)求攜帶數(shù)據(jù),因此必須分配使用能攜帶數(shù)據(jù)的通道,在具體實(shí)現(xiàn)過程中,寫回請(qǐng)求通過HN到SN響應(yīng)(RSP)通道發(fā)送寫回請(qǐng)求.例如,H N2到SN2的寫回請(qǐng)求走RSP通道.由于該處理器支持SN直接將數(shù)據(jù)推送(Forward)到請(qǐng)求節(jié)點(diǎn)(RN),因此存在通道共享情況:例如SN4推送讀響應(yīng)報(bào)文到RN3,也使用R2到R3的(RSP)通道.通道共享存在死鎖可能,在芯片仿真驗(yàn)證時(shí)的確發(fā)現(xiàn)了死鎖.

由于WB事務(wù)流程具有握手與重傳機(jī)制,不會(huì)堵塞鏈路,因此,HN2到SN2以及H N5到SN5應(yīng)該采用WB以避免死鎖.考慮到該死鎖僅與SN3與SN5有關(guān),所有的HN與SN間的寫回采用WB無法獲得WBD的性能,因此可以僅對(duì)H N3與H N5配置為WB.另外,還可以采用全部配置為協(xié)議WBD,同時(shí)利用協(xié)議死鎖檢查與微操作機(jī)制,在發(fā)現(xiàn)死鎖時(shí)進(jìn)行解鎖.我們對(duì)后者也進(jìn)行了設(shè)計(jì)與分析.

使用WBD流程,在如圖6所示的架構(gòu)中,H N2到SN2的WB請(qǐng)求進(jìn)入響應(yīng)通道,需要通過R2和R3,到達(dá)SN2.SN4到H N3的響應(yīng)Response進(jìn)入響應(yīng)通道,經(jīng)過R4,R0,R1,R2,R3,到達(dá)H N3.2種報(bào)文共用了R2和R3之間的物理鏈路,根據(jù)虛網(wǎng)絡(luò)構(gòu)建的原則,不同類型的報(bào)文共享通道會(huì)形成死鎖.死鎖形成的過程分析為:H N2向SN2的多個(gè)請(qǐng)求報(bào)文占滿緩沖區(qū),導(dǎo)致SN4到H N3的響應(yīng)報(bào)文無法通過鏈路1返回H N3,在H N3中響應(yīng)報(bào)文無法返回意味著原有的一致性事務(wù)無法釋放,這就導(dǎo)致了死鎖.

短時(shí)間大量請(qǐng)求報(bào)文堵塞了物理通道,導(dǎo)致響應(yīng)報(bào)文無法返回,一致性事務(wù)得不到釋放導(dǎo)致死鎖.這種短時(shí)間內(nèi)的大量報(bào)文并非程序運(yùn)行的常態(tài),出現(xiàn)概率低.針對(duì)這種出現(xiàn)概率較小的情況,通過配置一致性協(xié)議來實(shí)現(xiàn)一種代價(jià)較小的死鎖解決方案.

我們的防死鎖機(jī)制工作為:通過監(jiān)控HN到SN的讀寫事務(wù)的等待時(shí)間,能夠判斷是否已經(jīng)出現(xiàn)死鎖.HN到SN之間的協(xié)議默認(rèn)為WBD,以實(shí)現(xiàn)更優(yōu)的性能.如果等待時(shí)間超過一定閾值,則說明HN到SN的鏈路已經(jīng)堵死,可能產(chǎn)生了死鎖.目錄控制器會(huì)進(jìn)入調(diào)試模式,將HN到SN的協(xié)議從WBD切換到WB,啟動(dòng)重傳機(jī)制,逐漸排空阻塞的鏈路.經(jīng)過一段時(shí)間,死鎖解除后,再回復(fù)到正常模式和WBD,以高性能方式執(zhí)行.采用2種一致性協(xié)議交替工作的方式,WB采用信用和重傳機(jī)制,不會(huì)導(dǎo)致物理鏈路的堵塞,WBD可以實(shí)現(xiàn)更低的延遲,但有可能堵塞鏈路.2種協(xié)議交替工作,可以在保持性能的同時(shí)避免死鎖.

4 實(shí)驗(yàn)結(jié)果與分析

我們使用Gem5來搭建模擬環(huán)境[22],一些關(guān)鍵參數(shù)如表1所示.Gem5支持對(duì)一致性協(xié)議的修改,在原有的MESI協(xié)議基礎(chǔ)上,我們進(jìn)行了部分修改,在Mesh網(wǎng)絡(luò)不同規(guī)模下(2×2,2×4,3×3)進(jìn)行了系統(tǒng)性能評(píng)估.為了更明顯體現(xiàn)WBD經(jīng)由路由網(wǎng)絡(luò)寫回主存對(duì)系統(tǒng)性能的影響,采用了128 MB共享主存,4個(gè)目錄表分布在Mesh網(wǎng)絡(luò)的4個(gè)頂點(diǎn).采用了XY路由策略,在2×2,2×4,3×3網(wǎng)絡(luò)中,每個(gè)路由節(jié)點(diǎn)到達(dá)目錄控制器的最大跳數(shù)分別為2,4,4.

Table 1 Configuration of System表1 系統(tǒng)參數(shù)配置

圖7展示了2×2 Mesh網(wǎng)絡(luò)的架構(gòu),4個(gè)分布式目錄位于Mesh網(wǎng)絡(luò)的4個(gè)頂點(diǎn),二級(jí)緩存通過路由節(jié)點(diǎn)連接到網(wǎng)絡(luò),DMA控制器連接到0號(hào)路由節(jié)點(diǎn).3×3和2×4網(wǎng)絡(luò)的架構(gòu)和圖7類似.

Fig.7 The structure of 2×2 Mesh圖7 2×2 Mesh網(wǎng)絡(luò)架構(gòu)

實(shí)驗(yàn)分為3部分:1)驗(yàn)證在WB和WBD不同協(xié)議配置下,對(duì)系統(tǒng)性能的影響;2)驗(yàn)證第3節(jié)提出的微操作機(jī)制解決協(xié)議級(jí)死鎖的正確性與性能影響;3)對(duì)微操作機(jī)制的功耗與開銷進(jìn)行分析.

1)WB和WBD的性能比較

圖8為在不同數(shù)據(jù)規(guī)模和網(wǎng)絡(luò)規(guī)模下WB和WBD的性能對(duì)比,橫坐標(biāo)是片上網(wǎng)絡(luò)規(guī)模,分別對(duì)應(yīng)2×2,2×4,3×3 Mesh網(wǎng)絡(luò);縱坐標(biāo)是程序的平均執(zhí)行時(shí)間(運(yùn)行周期數(shù));圖8(a)(d)對(duì)應(yīng)0.64 M數(shù)據(jù)規(guī)模,圖8(b)(e)對(duì)應(yīng)1.28 M數(shù)據(jù)規(guī)模,圖8(c)(f)對(duì)應(yīng)2.56 M數(shù)據(jù)規(guī)模.我們模擬了2種協(xié)議下一致性事務(wù)的平均完成周期數(shù),使用的是類似流拷貝(stream copy)的應(yīng)用負(fù)載,在程序穩(wěn)態(tài)時(shí)該程序?qū)Υ鎯?chǔ)器的訪問特性為兩讀一寫,寫是由緩存替換觸發(fā).圖8(a)～(c)中,在相同數(shù)據(jù)規(guī)模下,隨著網(wǎng)絡(luò)規(guī)模增加,WBD的性能提升更加明顯;在相同網(wǎng)絡(luò)規(guī)模下,隨著數(shù)據(jù)規(guī)模的增加,WBD的性能提升更加明顯.

分析原因如下:WB需要4次通過NoC網(wǎng)絡(luò),包含發(fā)送替換請(qǐng)求(Replacement)、返回ID、發(fā)送數(shù)據(jù)(DATA)和返回Ack共4個(gè)一致性流程;而WBD只需要2次通過NoC網(wǎng)絡(luò),僅包含替換請(qǐng)求與數(shù)據(jù)(ReplacementData)和返回Ack,通過NoC的次數(shù)更少.在2×2,2×4,3×3網(wǎng)絡(luò)中,每個(gè)路由節(jié)點(diǎn)到達(dá)目錄控制器的最大跳數(shù)分別為2,4,4.隨著網(wǎng)絡(luò)規(guī)模的增加,最大跳步數(shù)增加,相應(yīng)延遲也增加.LLC容量不變,數(shù)據(jù)規(guī)模增加,替換請(qǐng)求的次數(shù)也隨之增加,WBD的性能提升更加明顯.圖9為在同一網(wǎng)絡(luò)規(guī)模和不同數(shù)據(jù)規(guī)模下,分別在訪存密集型負(fù)載(即流拷貝(stream copy))和計(jì)算密集型(Leibniz定理求π)負(fù)載下,WBD相較于WB性能提升對(duì)比.結(jié)果表明,隨著負(fù)載規(guī)模的增加,訪存密集型負(fù)載和計(jì)算密集型負(fù)載的性能提升趨勢(shì)相同,說明協(xié)議性能的提升效果適用于多種類型的負(fù)載.

在大規(guī)模網(wǎng)絡(luò)和高負(fù)載下,WBD相較于WB的優(yōu)化效果更加明顯,在實(shí)際運(yùn)行中,性能提升會(huì)隨著網(wǎng)絡(luò)規(guī)模和負(fù)載的增加而增加.

2)微操作機(jī)制正確性與性能影響

微操作機(jī)制在解決死鎖問題的同時(shí),會(huì)對(duì)系統(tǒng)性能產(chǎn)生影響.理論上,不同網(wǎng)絡(luò)和數(shù)據(jù)規(guī)模下,微操作相較于WB都會(huì)有部分性能損失.然而在圖8(d)～(f)中,相對(duì)于WBD對(duì)WB的提升,引入微操作機(jī)制對(duì)于WBD的性能損失非常微小.微操作避免了WB可能導(dǎo)致的協(xié)議死鎖,實(shí)現(xiàn)了以較低的性能損失來解決死鎖問題.

Fig.8 Comparison of execution time under different load and network圖8 不同數(shù)據(jù)和網(wǎng)絡(luò)規(guī)模下程序執(zhí)行時(shí)間對(duì)比

Fig.9 Comparison of performance improvement under two kinds of workload圖9 2類負(fù)載下性能提升對(duì)比

3)功耗與開銷

微操作機(jī)制的硬件開銷主要來源于微操作表和控制邏輯.微操作控制邏輯門數(shù)占比總邏輯門數(shù)約為2%,微操作表的SRAM占整個(gè)目錄SRAM容量的1.54%.目錄控制中主要的面積來源為存放目錄信息的SRAM,微操作機(jī)制額外帶來的面積開銷不到2%.功耗方面,可以通過開關(guān)配置微操作機(jī)制的使用,閑置時(shí)關(guān)閉以降低功耗.在實(shí)際運(yùn)行中,微操作機(jī)制的功耗幾乎可以忽略.微操作機(jī)制作為引入的冗余機(jī)制,在正常情況下并不直接參與一致性協(xié)議的運(yùn)轉(zhuǎn),該機(jī)制在協(xié)議發(fā)生問題,例如死鎖時(shí)介入,等待問題解除后退出,增加協(xié)議的容錯(cuò)性.

根據(jù)以上實(shí)驗(yàn)結(jié)論,我們可以在緩存一致性設(shè)計(jì)中,對(duì)于由于替換操作引發(fā)的寫回事務(wù)的流程,采用WBD以提高性能,而潛在的死鎖風(fēng)險(xiǎn)通過基于微操作的防死鎖機(jī)制來避免,依然獲得比僅采用WB更好的性能.可配置協(xié)議防死鎖沒有引入額外的虛通道,僅僅利用了可配置的微操作機(jī)制,面積和功耗開銷就是微操作表的開銷.其他傳統(tǒng)的防死鎖機(jī)制需要較為復(fù)雜的機(jī)制的硬件資源,如額外的虛通道、全局監(jiān)控和解除死鎖網(wǎng)絡(luò)等.目前我們只在模擬環(huán)境中評(píng)估了相應(yīng)的性能,下一步會(huì)在物理實(shí)現(xiàn)中進(jìn)一步評(píng)估硬件資源和功耗.通過上面的實(shí)驗(yàn),驗(yàn)證了協(xié)議配置的必要性和有效性,以及基于微操作機(jī)制解決協(xié)議級(jí)死鎖的正確性和性能提升效果.下一步將研究在不同核心數(shù)以及不同路由網(wǎng)絡(luò)下的性能情況.對(duì)于防死鎖機(jī)制中HN到SN讀寫事務(wù)的等待時(shí)間的閾值變化對(duì)防死鎖機(jī)制性能影響,也是我們需要在下一步進(jìn)行研究和優(yōu)化的方向.

5 總 結(jié)

本文提出了一種面向多核處理器的可配置緩存一致性協(xié)議,可以通過微操作來實(shí)現(xiàn)一致性協(xié)議的動(dòng)態(tài)配置,包括協(xié)議狀態(tài)轉(zhuǎn)換的配置和協(xié)議流程的配置.這種靈活的設(shè)計(jì)可以極大提升系統(tǒng)的靈活性,能夠針對(duì)不同架構(gòu),提高一致性協(xié)議的執(zhí)行效率,優(yōu)化系統(tǒng)性能;另外,還可以通過微操作機(jī)制解決協(xié)議級(jí)死鎖,提高系統(tǒng)的容錯(cuò)性,以應(yīng)對(duì)CPU設(shè)計(jì)中可能存在的缺陷.通過模擬測(cè)試,結(jié)果表明緩存一致性協(xié)議在不同的配置下的性能不同,死鎖的風(fēng)險(xiǎn)也不同,可配置的緩存一致性協(xié)議以及CDDU模塊能夠在實(shí)現(xiàn)協(xié)議配置靈活性的同時(shí)降低系統(tǒng)死鎖風(fēng)險(xiǎn),在保證一致性協(xié)議正確性的基礎(chǔ)上,提供更多的協(xié)議優(yōu)化和容錯(cuò)的空間,降低了芯片研發(fā)的風(fēng)險(xiǎn).本文思想在自主飛騰64核處理器中進(jìn)行了實(shí)現(xiàn),為確保處理器的協(xié)議正確性發(fā)揮了重要作用,同時(shí)在該芯片的多路擴(kuò)展實(shí)現(xiàn)過程中提高了協(xié)議的魯棒性,消除了潛在的死鎖,具有非常重要的工程實(shí)現(xiàn)意義.