一種基于自更新的簡(jiǎn)單高效Cache一致性協(xié)議

何錫明 馬 勝 黃立波 陳 微 王志英

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

共享存儲(chǔ)是當(dāng)前使用最為廣泛的并行編程模型，然而復(fù)雜的一致性協(xié)議使設(shè)計(jì)高效、低功耗、可擴(kuò)展的多核共享存儲(chǔ)系統(tǒng)變得十分困難.為了滿足一致性的定義，一致性協(xié)議必須對(duì)寫操作立即響應(yīng)，失效其他核cache備份.這就要求目錄協(xié)議實(shí)時(shí)地記錄cache的備份并發(fā)送間接消息，或者要求監(jiān)聽協(xié)議廣播消息去失效備份.除此之外，當(dāng)前的協(xié)議還會(huì)增加各種穩(wěn)定狀態(tài)(獨(dú)占E或者擁有O)來提高性能，增加眾多中間狀態(tài)以處理各種情況下出現(xiàn)的競(jìng)爭(zhēng).例如GEM5[1]中實(shí)現(xiàn)的MESI(modified exclusive shared or invalid)目錄協(xié)議在L1中就有15個(gè)狀態(tài).一直以來，大多數(shù)的共享存儲(chǔ)多處理器實(shí)現(xiàn)cache一致性都是基于目錄協(xié)議.在國(guó)際上，針對(duì)cache一致性協(xié)議的存儲(chǔ)開銷和驗(yàn)證開銷的優(yōu)化設(shè)計(jì)層出不窮[2-7].而在國(guó)內(nèi)，研究者們?cè)谝恢滦詤f(xié)議功能擴(kuò)展和性能優(yōu)化等方面取得了一系列的成果[8-10].

而實(shí)際上，在多核程序運(yùn)行過程中，大部分的數(shù)據(jù)都只被一個(gè)處理器訪問(甚至在程序并行階段)，我們稱之為私有數(shù)據(jù).私有數(shù)據(jù)僅由一個(gè)處理器訪問，不存在cache一致性的問題，不需要一致性的維護(hù).這種數(shù)據(jù)特性被越來越多的研究者關(guān)注，有的研究者利用這種共享特性過濾監(jiān)聽協(xié)議中多余的消息來降低監(jiān)聽協(xié)議的網(wǎng)絡(luò)開銷[11]，有的研究者利用這種共享特性對(duì)目錄協(xié)議的存儲(chǔ)開銷進(jìn)行優(yōu)化，以提高目錄的利用率[2,5].

2011年Cuesta 等人[2]利用數(shù)據(jù)劃分的方法對(duì)協(xié)議進(jìn)行優(yōu)化.他們通過測(cè)試并行測(cè)試集SPLASH-2(Stanford parallel applications for shared memory)中的8個(gè)程序、 scientific benchmarks中的2個(gè)程序、ALPBench(all levels of parallelism benchmark for multimedia)中的4個(gè)程序、PARSEC(Princeton application repository for shared-memory computers)中的4個(gè)程序，發(fā)現(xiàn)平均有75%的數(shù)據(jù)塊(64 B)是私有的.他們?cè)谀夸浿泻雎赃@些私有數(shù)據(jù)塊的信息，有效地提高了目錄的利用率.實(shí)驗(yàn)結(jié)果表明：在相同的目錄大小情況下，他們的方案獲得15%的性能提高.然而他們這種針對(duì)于目錄利用率的優(yōu)化并沒有真正地解決協(xié)議中的目錄開銷、大量的一致性狀態(tài)和間接訪問等問題.2012年Ros 等人[12]利用劃分私有和共享數(shù)據(jù)的方法，進(jìn)行動(dòng)態(tài)的寫策略切換.這種寫策略對(duì)私有數(shù)據(jù)進(jìn)行寫回，對(duì)共享數(shù)據(jù)進(jìn)行寫直達(dá)，簡(jiǎn)化了一致性狀態(tài).利用并行程序的數(shù)據(jù)無競(jìng)爭(zhēng)(data race free, DRF)模型[13]，在同步點(diǎn)進(jìn)行共享數(shù)據(jù)自失效的方法完全避免了目錄的存儲(chǔ)開銷.相對(duì)于目錄協(xié)議，他們的設(shè)計(jì)平均減少了14.2%的系統(tǒng)能耗.但是寫直達(dá)方式以及同步點(diǎn)自失效的方法大大增加了系統(tǒng)cache的缺失率，影響系統(tǒng)性能.

針對(duì)上述問題，本文主要研究共享存儲(chǔ)一致性協(xié)議的簡(jiǎn)化.在滿足DRF的模型下，設(shè)計(jì)了一種基于自更新操作(self-updating)只包含2個(gè)穩(wěn)定狀態(tài)(valid/invalid)的簡(jiǎn)單高效一致性協(xié)議，簡(jiǎn)稱VISU(valid/invalid states based on self-updating)協(xié)議.協(xié)議的簡(jiǎn)化主要體現(xiàn)在2個(gè)部分：

1) 完全消除目錄和間接事務(wù).在目錄協(xié)議中，目錄的主要功能是記錄每個(gè)共享備份的位置以便獲取最新的數(shù)據(jù)和失效過期的備份(間接事務(wù)).VISU協(xié)議利用數(shù)據(jù)的共享特性，進(jìn)行私有共享數(shù)據(jù)塊的動(dòng)態(tài)劃分.在共享數(shù)據(jù)方面，VISU協(xié)議采用了寫直達(dá)和自更新操作，LLC(last level cache)始終保持著最新的共享數(shù)據(jù)，同時(shí)自更新操作及時(shí)地更新過期的備份.在私有數(shù)據(jù)方面，VISU協(xié)議采用寫回方式，在協(xié)議中不需要目錄記錄信息，不進(jìn)行一致性的維護(hù)(類似于單核訪問).因此整個(gè)協(xié)議消除了目錄和間接事務(wù).

2) 簡(jiǎn)化成2個(gè)穩(wěn)定狀態(tài).通過TLB表項(xiàng)提供的頁(yè)面粒度的私有共享信息，VISU協(xié)議在cache line中只需要2個(gè)穩(wěn)定的狀態(tài)(valid/invalid)就能正確地滿足一致性，同時(shí)獲得了與2種穩(wěn)定狀態(tài)的MESI協(xié)議相當(dāng)甚至更優(yōu)的性能.

1 VISU一致性協(xié)議正確性論證

為了論證VISU協(xié)議的正確性，首先介紹關(guān)于一致性協(xié)議需要滿足的2個(gè)條件，然后具體描述VISU協(xié)議，最后結(jié)合定義與描述論證VISU協(xié)議的正確性.

1.1 一致性的定義

Sorin 等人[13]定義一致性：1)同一時(shí)刻滿足對(duì)于同一存儲(chǔ)單元只能一個(gè)寫或者多個(gè)讀(single-write multiple-read， SWMR)；2)在每個(gè)時(shí)期開始階段存儲(chǔ)單元的值都必須和最新一次的讀寫時(shí)期結(jié)束階段的值相同(data value invariant)，本文稱之為數(shù)據(jù)最新原則.

1.2 VISU協(xié)議的描述

本文設(shè)計(jì)一種基于自更新操作只包含2個(gè)穩(wěn)定狀的簡(jiǎn)單高效VISU協(xié)議.協(xié)議可分成私有和共享2個(gè)獨(dú)立的部分.首先我們介紹數(shù)據(jù)無競(jìng)爭(zhēng)的編程模型，然后介紹VISU協(xié)議中私有數(shù)據(jù)和共享數(shù)據(jù)的協(xié)議.為了直觀地闡述協(xié)議，假設(shè)系統(tǒng)為2級(jí)cache，L1 cache和LLC(last level cache).

數(shù)據(jù)無競(jìng)爭(zhēng)的編程模型保證在程序中無數(shù)據(jù)競(jìng)爭(zhēng)，即當(dāng)2個(gè)不同的線程同時(shí)訪問相同的存儲(chǔ)單元且至少有一個(gè)是寫操作時(shí)，必然存在同步語(yǔ)句把它們分開.數(shù)據(jù)競(jìng)爭(zhēng)經(jīng)常導(dǎo)致程序的錯(cuò)誤.DRF編程模型是C++和Java高級(jí)編程語(yǔ)言存儲(chǔ)模型的基礎(chǔ)，絕大部分并行程序都滿足DRF編程模型.因此VISU協(xié)議利用了程序的DRF特性進(jìn)行一致性的設(shè)計(jì).

VISU協(xié)議在同步點(diǎn)進(jìn)行自更新操作以簡(jiǎn)化間接事務(wù)，并利用數(shù)據(jù)的共享特性，把協(xié)議分成私有和共享2個(gè)獨(dú)立的部分：

1) 私有數(shù)據(jù)協(xié)議.私有數(shù)據(jù)協(xié)議類似于單核處理器的數(shù)據(jù)訪問，消除了私有數(shù)據(jù)冗余的一致性維護(hù).L1 cache采用了寫回的方式.

2) 共享數(shù)據(jù)協(xié)議.與簡(jiǎn)單的私有數(shù)據(jù)協(xié)議相比，共享數(shù)據(jù)協(xié)議在L1 cache中采用寫直達(dá)的方式代替寫回方式.同時(shí)，共享數(shù)據(jù)在同步點(diǎn)進(jìn)行自更新操作.

① VISU協(xié)議針對(duì)私有數(shù)據(jù)的處理.VISU協(xié)議對(duì)私有數(shù)據(jù)處理類似于單核處理器的處理，采用cache寫回策略.圖1和圖2展示了2級(jí)cache的VISU協(xié)議.圖1展示了協(xié)議中的主要事務(wù)讀(read, Rd)、寫(write, Wrt)、寫回(write-back, WB).圖2為VISU的狀態(tài)轉(zhuǎn)換圖，2種穩(wěn)定狀態(tài)(V，I)和2種中間狀態(tài)(VI, IV)，其中圖2(a)為L(zhǎng)1 cache控制器的狀態(tài)轉(zhuǎn)換圖，圖2(b)為L(zhǎng)LC 控制器的狀態(tài)轉(zhuǎn)換圖.

Fig. 1 VISU:Rd, Wrt and WB transactions of private data圖1 VISU 私有數(shù)據(jù)讀(Rd)、寫(Wrt)、寫回(WB)事務(wù)

Fig. 2 VISU:State transitions of private data圖2 VISU 私有數(shù)據(jù)協(xié)議狀態(tài)圖

當(dāng)發(fā)生讀(Rd)缺失時(shí)，如圖1(a)，L1 cache發(fā)送GetS到LLC，然后獲取Data數(shù)據(jù)；當(dāng)發(fā)生寫(Wrt)缺失時(shí)，如圖1(b)所示，L1發(fā)送GetX到LLC中，LLC返回Data數(shù)據(jù).由于數(shù)據(jù)為私有數(shù)據(jù)，其他核不存在數(shù)據(jù)的備份，所以讀缺失和寫缺失不需要向其他核發(fā)送間接事務(wù).當(dāng)L1 cache發(fā)生驅(qū)逐時(shí)采用寫回策略(WB)，如圖1(c)所示，把臟的數(shù)據(jù)Data寫入到LLC中，并返回Ack消息.圖2(a)(b)分別展示了L1 cache控制器和LLC控制器的狀態(tài)轉(zhuǎn)換圖.圖2(a)左半部分I→IV→V展示了 L1 cache發(fā)生讀寫缺失，發(fā)送了GetS/GetX消息，然后接收到數(shù)據(jù)Data的狀態(tài)轉(zhuǎn)換，V→V展示了讀寫命中的狀態(tài)轉(zhuǎn)換.圖2(a)右半部分V→VI→I展示了L1 cache的驅(qū)逐，L1發(fā)送WB事務(wù)把臟的數(shù)據(jù)寫入到LLC中，然后接收到Ack消息的狀態(tài)轉(zhuǎn)換.圖2(b)左半部分展示了LLC控制器響應(yīng)L1 cache的GetS/GetX消息，然后進(jìn)行I→IV→V(LLC無數(shù)據(jù)時(shí)，從內(nèi)存中讀取并返回Mem_data數(shù)據(jù))或者V→V的狀態(tài)轉(zhuǎn)換.圖2(b)右半部分則是LLC發(fā)生驅(qū)逐時(shí)，把臟的數(shù)據(jù)(Own-put)寫入到內(nèi)存中并返回Ack消息的狀態(tài)轉(zhuǎn)換.整個(gè)協(xié)議只包含2種穩(wěn)定狀態(tài)V和I、2種中間狀態(tài)VI和IV，并且不需要目錄和間接事務(wù).

② VISU協(xié)議針對(duì)共享數(shù)據(jù)的處理.為了滿足一致性的定義，一致性協(xié)議必須對(duì)寫操作立即響應(yīng)，失效其他核cache備份，返回最新的數(shù)據(jù).因?yàn)闆]有了目錄記錄數(shù)據(jù)的共享者和擁有者，VISU協(xié)議對(duì)于共享數(shù)據(jù)的處理就要確定最近寫入數(shù)據(jù)的位置并失效過期的備份，所以VISU協(xié)議添加了一個(gè)額外的自更新操作，用以自動(dòng)更新過期的備份.相比于私有數(shù)據(jù)協(xié)議，共享數(shù)據(jù)協(xié)議用寫直達(dá)操作代替寫回操作，保證在LLC中始終存放最新的數(shù)據(jù)，從而使得共享數(shù)據(jù)協(xié)議與私有數(shù)據(jù)協(xié)議一樣的簡(jiǎn)單，沒有目錄和間接事務(wù).

圖3展示了共享數(shù)據(jù)的讀(Rd)、寫(Wrt)、寫直達(dá)(WT-timeout)、同步點(diǎn)(synchronization, Sync)四種事務(wù).

Fig. 3 VISU:Rd, Wrt, WT-timeout and Sync transactions of shared data圖3 VISU共享數(shù)據(jù)讀(Rd)、寫(Wrt)、寫直達(dá)(WT-timeout)、同步點(diǎn)(Sync)事務(wù)

如圖3(a)，首先對(duì)于讀缺失，L1 cache發(fā)送GetS到LLC中獲取數(shù)據(jù)Data.對(duì)于寫缺失，如圖3(b)，L1 cache發(fā)送GetX到LLC獲取數(shù)據(jù)，這部分與私有數(shù)據(jù)協(xié)議相同.不同的是在寫操作之后，共享數(shù)據(jù)協(xié)議要進(jìn)行寫直達(dá)(WT)操作，把寫入的數(shù)據(jù)及時(shí)地寫直達(dá)(WT)到LLC中，這樣保證LLC一直擁有最新的數(shù)據(jù).為了降低寫直達(dá)產(chǎn)生的大量報(bào)文，如圖3(c)所示，協(xié)議采用了延時(shí)寫直達(dá)(WT-timeout)的方式.最后為了更新過期的備份，協(xié)議利用DRF編程模型識(shí)別同步點(diǎn)，在同步點(diǎn)(Sync)進(jìn)行自更新操作(SelfU).如圖3(d)所示，L1 cache發(fā)送SelfU到LLC中，LLC返回最新的數(shù)據(jù)，主動(dòng)地自更新操作消除了間接的失效.

1.3 VISU協(xié)議正確性論證

本文1.1節(jié)引入了描述cache一致性協(xié)議正確性的2個(gè)條件：?jiǎn)螌懚嘧xSWMR和數(shù)據(jù)最新(data value invariant)，這里我們將論述在DRF編程模型下VISU協(xié)議滿足這2個(gè)條件，即論證協(xié)議的正確性.

首先私有數(shù)據(jù)被單一處理器訪問，這些數(shù)據(jù)不存在cache一致性問題.故VISU對(duì)于私有數(shù)據(jù)采用了類似于單核處理器的cache寫回(write-back)的訪問方式.這滿足單寫多讀和數(shù)據(jù)最新(data value invariant)條件，即滿足cache一致性.

其次對(duì)于共享數(shù)據(jù)的訪問，對(duì)比目錄協(xié)議，VISU協(xié)議需要論證沒有目錄和間接失效事務(wù)的情況下，如何及時(shí)地失效過期的備份和保證讀到最新的數(shù)據(jù).

1) DRF編程模型中不同線程對(duì)同一個(gè)地址的讀寫之間必然存在同步操作，即在每一個(gè)寫時(shí)期(寫操作開始直到遇到同步點(diǎn))不存在其他線程的讀寫操作.例如圖3(b)(c)中LLC的虛線段就不存在其他線程針對(duì)同一地址的讀寫操作.利用寫直達(dá)方式，每次寫操作都能及時(shí)把最新的數(shù)據(jù)寫入到LLC中，滿足了定義中的單寫多讀的條件.

2) 因?yàn)椴煌€程對(duì)同一地址的讀寫操作(包括讀寫、寫寫、寫讀)之間必然存在同步點(diǎn)，每個(gè)同步點(diǎn)都要進(jìn)行自更新操作.這樣就能及時(shí)地更新過期的備份，保證在每個(gè)時(shí)期開始階段存儲(chǔ)單元的值和最近一次讀寫時(shí)期結(jié)束階段的值(最新寫入的值)相同.因此滿足cache一致性定義的數(shù)據(jù)最新原則.

綜上所述，對(duì)比cache一致性定義的2個(gè)條件，VISU協(xié)議在DRF編程模型下滿足一致性.

2 VISU協(xié)議的具體實(shí)現(xiàn)方案

VISU協(xié)議的實(shí)現(xiàn)主要有3個(gè)部分：數(shù)據(jù)的劃分和切換機(jī)制、協(xié)議中同步原語(yǔ)的支持 、同步點(diǎn)共享數(shù)據(jù)的自更新.

具體的設(shè)計(jì)方案如圖4所示，從右半部分可以看出，當(dāng)訪存請(qǐng)求發(fā)生TLB缺失時(shí)，就進(jìn)行頁(yè)面粒度的數(shù)據(jù)私有和共享的劃分(下文將具體描述).圖4左半部分是根據(jù)私有共享的劃分執(zhí)行協(xié)議，然后進(jìn)行寫直達(dá)寫回策略的動(dòng)態(tài)切換.L1 cache發(fā)生缺失，就根據(jù)數(shù)據(jù)的私有和共享分別采用VISU協(xié)議中私有和共享數(shù)據(jù)處理的2個(gè)部分發(fā)送相應(yīng)的請(qǐng)求，最終完成數(shù)據(jù)訪存.下文將具體描述私有共享數(shù)據(jù)的劃分、私有到共享的切換機(jī)制、協(xié)議中同步原語(yǔ)的支持、同步點(diǎn)共享數(shù)據(jù)的自更新4個(gè)部分的實(shí)現(xiàn).

Fig. 4 The block diagram of the action in VISU圖4 VISU協(xié)議實(shí)現(xiàn)框圖

Fig. 5 Format of TLB entry and page table entry圖5 TLB entry和頁(yè)表項(xiàng)的組成

2.1 私有共享數(shù)據(jù)的劃分

數(shù)據(jù)的私有和共享劃分，成為了研究者研究的熱點(diǎn).部分研究工作利用硬件機(jī)制進(jìn)行私有和共享的劃分，這些方案雖然能夠進(jìn)行細(xì)粒度的數(shù)據(jù)劃分，但是造成了大量的存儲(chǔ)開銷.有的研究者利用編譯器進(jìn)行劃分，但由于在編譯階段較難判斷數(shù)據(jù)的私有和共享，這種方案實(shí)現(xiàn)較為復(fù)雜.本文采用操作系統(tǒng)(OS)輔助進(jìn)行私有共享數(shù)據(jù)的劃分，Cuesta 等人[2]也采用了類似的劃分方法.這種方案利用TLB 表項(xiàng)和頁(yè)表項(xiàng)(page table entry)存儲(chǔ)信息.這是一種頁(yè)面粒度的私有共享劃分方案，當(dāng)一個(gè)頁(yè)面中的某一個(gè)數(shù)據(jù)共享時(shí)，整個(gè)頁(yè)面都標(biāo)記為共享.

首先對(duì)于每一個(gè)訪存請(qǐng)求，處理器會(huì)先查找TLB表項(xiàng)，進(jìn)行虛實(shí)地址轉(zhuǎn)換.每一個(gè)TLB表項(xiàng)主要由虛擬地址和物理地址2部分組成，再加上一些頁(yè)面屬性的標(biāo)記位.TLB表項(xiàng)中往往預(yù)留一些標(biāo)志位沒有被使用從而允許在TLB表項(xiàng)中添加一個(gè)私有共享的標(biāo)記位P,因此不需要額外的硬件開銷.同理在頁(yè)表項(xiàng)中添加P域和Keeper域，分別標(biāo)記頁(yè)面是否共享和頁(yè)面的共享者(第1次訪問這個(gè)頁(yè)面的CPU)，如圖5所示.

當(dāng)TLB表項(xiàng)缺失時(shí)，TLB表項(xiàng)和頁(yè)表項(xiàng)中的域就需要進(jìn)行處理.處理方法如圖4中右半部分所示，訪存請(qǐng)求因TLB表項(xiàng)缺失進(jìn)行頁(yè)表的訪問，如果發(fā)生缺頁(yè)，就造成系統(tǒng)異常，操作系統(tǒng)會(huì)進(jìn)行相應(yīng)的缺頁(yè)錯(cuò)誤處理并分配新的頁(yè)面.如果頁(yè)面被首次訪問并且沒有緩存在其他TLB中，操作系統(tǒng)設(shè)置新分配的頁(yè)面為私有(P域設(shè)為1)頁(yè)面且記錄第1個(gè)訪問的核為keeper；否則就判斷頁(yè)面的私有和共享的狀態(tài)，若私有頁(yè)面且其被不同的核訪問，觸發(fā)私有到共享的切換(下文將詳細(xì)說明切換機(jī)制)，切換完成后將頁(yè)面置為共享(P域設(shè)為0)，最后將設(shè)置好標(biāo)志位的表項(xiàng)添加到TLB中.

2.2 私有到共享的切換機(jī)制

TLB缺失就進(jìn)行頁(yè)面的訪問，當(dāng)某個(gè)核首次訪問一個(gè)頁(yè)面時(shí)，頁(yè)面被置為私有頁(yè)面且訪問的核作為頁(yè)面的擁有者(Keeper).整個(gè)頁(yè)面里的數(shù)據(jù)為私有數(shù)據(jù)，這些數(shù)據(jù)在L1 cache中采用寫回的方式.第2個(gè)核訪問這個(gè)頁(yè)面，發(fā)現(xiàn)頁(yè)面被Keeper設(shè)置為私有(P域?yàn)?)，這時(shí)觸發(fā)切換機(jī)制，向Keeper核發(fā)送中斷，完成中斷后設(shè)置頁(yè)表項(xiàng)中的頁(yè)面為共享(P域設(shè)為0).Keeper核接收到中斷就更新這個(gè)頁(yè)面的TLB 表項(xiàng)(設(shè)置為共享，P域設(shè)為0)，把L1 cache中臟的數(shù)據(jù)寫入到LLC中.完成切換后，所有核訪問這個(gè)頁(yè)面都會(huì)發(fā)現(xiàn)頁(yè)面共享且Keeper核已經(jīng)將最新的數(shù)據(jù)寫入到LLC中，這樣頁(yè)面的數(shù)據(jù)就切換成了共享數(shù)據(jù).

2.3 協(xié)議中同步原語(yǔ)的支持

同步機(jī)制通常是以用戶級(jí)軟件例程的方式實(shí)現(xiàn)，這些例程依賴于硬件提供的同步語(yǔ)句.在多處理器中實(shí)施同步所需要的是一組能夠以原子方式讀取修改和寫入存儲(chǔ)單元的硬件原語(yǔ)，例如“Test&Set”或者“Compare&Swap”.如果測(cè)試(test)或者比較(compare)一個(gè)條件滿足，那么核就競(jìng)爭(zhēng)到一個(gè)存儲(chǔ)單元，執(zhí)行原子的讀修改寫操作；否則在L1中對(duì)這個(gè)存儲(chǔ)單元的備份進(jìn)行旋轉(zhuǎn)，直到存儲(chǔ)單元的數(shù)據(jù)被其他核修改，即條件被改變.

在VISU協(xié)議中沒有間接的失效操作.一個(gè)核結(jié)束了敏感區(qū)，釋放了一個(gè)條件，在協(xié)議上不會(huì)去通知正在旋轉(zhuǎn)的核條件的改變，從而難以完成同步操作.為此VISU一致性協(xié)議針對(duì)讀-修改-寫(RMW)的原子事務(wù)，采用重新讀取LLC數(shù)據(jù)的方式(因?yàn)榇嬖诙鄠€(gè)核訪問一個(gè)數(shù)據(jù)，所以數(shù)據(jù)必然共享，LLC有最新的數(shù)據(jù))，讓旋轉(zhuǎn)的核能夠感知條件的改變.具體協(xié)議如圖6所示，不妨設(shè)條件滿足時(shí)數(shù)據(jù)為0，條件不滿足時(shí)數(shù)據(jù)為1，L10遇到RMW原子指令，不管當(dāng)前是有效還是無效狀態(tài)(I/V)，都發(fā)送GetX消息到LLC，LLC接收到GetX就阻塞LLC，防止原子指令被打斷.L10獲得數(shù)據(jù)Data(0)即條件滿足(鎖可用)進(jìn)入修改寫入狀態(tài)R(0)W0(1)，發(fā)送WT_lock(1)，寫直達(dá)數(shù)據(jù)1占用這個(gè)鎖，并釋放LLC的阻塞.此時(shí)程序進(jìn)入敏感區(qū)(critical section)工作，直到釋放條件W0(0).L1發(fā)送WT_unlock(0)操作寫入0到LLC中，使條件重新可用.其他核執(zhí)行RMW時(shí)，同樣發(fā)送GetX消息，例如圖6中L11，發(fā)現(xiàn)LLC被阻塞，則進(jìn)入LLC的等待隊(duì)列.當(dāng)LLC不阻塞時(shí)，L11獲得數(shù)據(jù)Data(1)，發(fā)現(xiàn)條件不滿足，L11不斷旋轉(zhuǎn)，直到競(jìng)爭(zhēng)到條件滿足讀到Data(0)，進(jìn)入敏感區(qū).這種繞過L1中的數(shù)據(jù)，直接訪問LLC的方式，造成了一定的性能損失，但同步操作在整個(gè)程序中出現(xiàn)的頻率很小，整體性能損失依然可以被接受，第3節(jié)的實(shí)驗(yàn)評(píng)估也驗(yàn)證了這一點(diǎn).VISU協(xié)議通過這種方式實(shí)現(xiàn)了對(duì)同步原語(yǔ)的支持.

Fig. 6 The atomic RMW transaction of shared data in VISU圖6 VISU中共享數(shù)據(jù)的原子操作(RMW)協(xié)議

2.4 同步點(diǎn)共享數(shù)據(jù)的自更新

在一致性協(xié)議中，監(jiān)聽協(xié)議通過廣播消息作廢所有過期的備份，而目錄協(xié)議通過目錄節(jié)點(diǎn)間接轉(zhuǎn)發(fā)消息失效過期的備份.之前有研究者采用了自失效操作，即每個(gè)核在同步點(diǎn)失效各自L1 cache中過期的備份來保證協(xié)議的一致性，降低協(xié)議的復(fù)雜性.共享數(shù)據(jù)被多個(gè)核使用，很大程度上可能被多次地讀寫.如果每一個(gè)同步點(diǎn)都采用自失效操作來失效所有的共享數(shù)據(jù)，無疑會(huì)大大增加共享數(shù)據(jù)的cache失效率.基于此，本文提出了在同步點(diǎn)進(jìn)行自更新操作.自更新操作不僅能夠有效地降低共享數(shù)據(jù)cache的失效率和提高性能，而且能夠起到和自失效操作相同的作用，保證協(xié)議的正確性.每一個(gè)進(jìn)入L1 cache的數(shù)據(jù)都會(huì)根據(jù)TLB表項(xiàng)中的私有共享標(biāo)志位P在cache line中設(shè)置共享和私有.基于這些私有共享標(biāo)記位，當(dāng)程序識(shí)別到同步點(diǎn)時(shí)，會(huì)完成共享數(shù)據(jù)從LLC到L1 cache的更新.考慮到隨著程序的運(yùn)行，共享數(shù)據(jù)的數(shù)量會(huì)不斷地增加，為此本設(shè)計(jì)中設(shè)置了一個(gè)閾值，當(dāng)共享數(shù)據(jù)數(shù)量大于這個(gè)閾值時(shí)，L1 cache中就采用自失效操作失效共享數(shù)據(jù)以防止共享數(shù)據(jù)的累增.

2.5 實(shí)現(xiàn)中優(yōu)化設(shè)計(jì)

1) 寫直達(dá)的粒度優(yōu)化.VISU是基于數(shù)據(jù)無競(jìng)爭(zhēng)的情況下滿足一致性，但是軟件的DRF并不以cache line為粒度.考慮2個(gè)核在L1中同時(shí)擁有一個(gè)cache line的數(shù)據(jù)，當(dāng)這2個(gè)核同時(shí)對(duì)這個(gè)cache line中不同的字(word)進(jìn)行寫操作時(shí)，在軟件層上這2個(gè)寫操作并不違反DRF原則，因此這2個(gè)并發(fā)的寫操作之間不存在同步語(yǔ)句.如果對(duì)這種情況不加以處理，最終基于cache line粒度的協(xié)議延時(shí)寫直達(dá)就會(huì)交錯(cuò)覆蓋相互的值.考慮到這個(gè)問題，設(shè)計(jì)中采用了基于word粒度的寫直達(dá)方式，在L1 cache line中針對(duì)每一個(gè)word設(shè)置1個(gè)dirty位.在寫直達(dá)到LLC時(shí)，不同的核只寫入其修改的字(word)而不影響其他字.

2) 直接內(nèi)存處理(direct memory access， DMA)協(xié)議設(shè)計(jì).DMA是現(xiàn)代處理器的重要特色，在協(xié)議上也必須對(duì)其有相應(yīng)的支持.DMA直接使用物理地址進(jìn)行數(shù)據(jù)的搬移，不需要經(jīng)過TLB的虛實(shí)地址轉(zhuǎn)換.因此VISU協(xié)議中的私有和共享的劃分對(duì)其并不適用，故此設(shè)計(jì)采用了廣播DMA請(qǐng)求的方式，失效L1中過期的數(shù)據(jù)，寫回臟的數(shù)據(jù)到LLC中.上述操作完成后，DMA訪問LLC，獲取和寫入數(shù)據(jù)，完成讀取和寫入操作.

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

3.1 實(shí)驗(yàn)環(huán)境

為了評(píng)估VISU協(xié)議的性能，實(shí)驗(yàn)采用GEM5[1]全系統(tǒng)模擬器模擬，搭載Linux 2.6.22 操作系統(tǒng)，采用GARNET[14]仿真片上互聯(lián)網(wǎng)絡(luò).同時(shí)利用CACTI 6.5[15]工具采用32 nm的技術(shù)工藝對(duì)cache的開銷進(jìn)行評(píng)估.設(shè)計(jì)中仿真8核的片上多核處理器(chip multiprocessors, CMP)結(jié)構(gòu)，運(yùn)行SPLASH-2中的測(cè)試程序.SPLASH-2程序分成了kernels和apps兩類程序，實(shí)驗(yàn)中分別選取了這2類中的FFT(64 KB complex doubles)，LU(LU-contiguous_block，512×512 matrix)，LU-Non(LU-non_contiguous_block，512×512 matrix)和Water-Nsq(Water-nsquared，512 molecules)并行測(cè)試程序進(jìn)行測(cè)試.模擬器中主要的參數(shù)如表1所示:

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

實(shí)驗(yàn)過程中通過識(shí)別操作系統(tǒng)和并行程序中的同步點(diǎn)(旋轉(zhuǎn)鎖、柵欄、中斷)進(jìn)行自更新操作.利用GEM5全系統(tǒng)模擬器，仿真整個(gè)并行程序，統(tǒng)計(jì)程序并行階段的數(shù)據(jù).實(shí)驗(yàn)中仿真了3種一致性協(xié)議：1)MESI目錄協(xié)議，該協(xié)議由2級(jí)cache組成，實(shí)時(shí)存儲(chǔ)著目錄信息.MESI目錄協(xié)議根據(jù)目錄記錄的信息發(fā)送消息失效所有的共享者(寫缺失)或者發(fā)送消息獲取最新的數(shù)據(jù)并降級(jí)存在的E/M狀態(tài)(讀缺失).2)VIPS協(xié)議，這種協(xié)議由Ros 等人[12]提出.VIPS協(xié)議在L1中也只有2種穩(wěn)定的狀態(tài)，與本設(shè)計(jì)中的VISU設(shè)計(jì)類似，但VIPS協(xié)議在同步點(diǎn)上采用的是自失效操作.采用同步點(diǎn)自失效的方法保證了協(xié)議的一致性，但一定程度上增加了L1 cache的缺失率.3)本文提出的VISU協(xié)議.該協(xié)議在同步點(diǎn)采用自更新的方式，即在同步點(diǎn)對(duì)共享數(shù)據(jù)進(jìn)行自更新，提高cache的命中率，從而提高系統(tǒng)性能.

在實(shí)驗(yàn)過程中，延時(shí)寫直達(dá)(同步點(diǎn)之前)的延時(shí)時(shí)間設(shè)為500 cycle.寫直達(dá)延時(shí)主要是因?yàn)槊看螌懸粋€(gè)數(shù)據(jù)，就很可能會(huì)訪存相應(yīng)cache line的其他字(word)的數(shù)據(jù).延時(shí)寫直達(dá)可以合并寫操作，然后一次性寫直達(dá)到LLC，降低由寫直達(dá)造成的大量報(bào)文.但是延時(shí)寫直達(dá)必須在下一個(gè)同步點(diǎn)之前完成，所以這個(gè)延時(shí)時(shí)間影響著協(xié)議的正確性和系統(tǒng)性能.

3.2 程序請(qǐng)求的分類

VISU協(xié)議動(dòng)態(tài)識(shí)別程序中的私有和共享數(shù)據(jù)，采用2種不同的方法進(jìn)行處理.實(shí)驗(yàn)中運(yùn)行了FFT，LU，LU-Non，Water-Nsq這4個(gè)程序并記錄了并行階段這4個(gè)程序?qū)λ接袛?shù)據(jù)和共享數(shù)據(jù)發(fā)送請(qǐng)求的數(shù)量，把請(qǐng)求分成了4類：取指請(qǐng)求、對(duì)共享數(shù)據(jù)的請(qǐng)求、對(duì)私有數(shù)據(jù)的請(qǐng)求以及同步相關(guān)的請(qǐng)求，如圖7所示:

Fig. 7 Fraction of different requests in parallel programs圖7 并行程序中各類請(qǐng)求的比例

一般情況下，取指請(qǐng)求是一類只讀請(qǐng)求，在VISU協(xié)議中采用寫回的方式進(jìn)行處理，不進(jìn)行私有和共享的劃分.從圖7可以看出，私有數(shù)據(jù)請(qǐng)求比例在FFT中最大，占程序總請(qǐng)求的5.1%.若把私有數(shù)據(jù)請(qǐng)求和取指請(qǐng)求均作為私有請(qǐng)求處理(二者采用相同的私有數(shù)據(jù)協(xié)議)，則私有請(qǐng)求數(shù)量占有比例高達(dá)90.1%.而在LU和Water-Nsq程序中私有請(qǐng)求占比較少(分別占有1.2%和1.8%)、共享請(qǐng)求占比大，這影響著這2個(gè)程序在VISU協(xié)議中的性能.整體上來看，私有請(qǐng)求(包括取指請(qǐng)求)平均占整個(gè)并行階段請(qǐng)求的77.2%.在4個(gè)程序中(FFT，LU，LU-Non，Water-Nsp)同步相關(guān)的請(qǐng)求所占比例依次為0.11%，0.10%，0.08%，0.22%，其中Water-Nsp相對(duì)來說比例較高，4個(gè)程序同步請(qǐng)求平均占比0.14%.

3.3 VISU協(xié)議運(yùn)行性能

為了分析VISU協(xié)議性能，實(shí)驗(yàn)測(cè)試了MESI，VIPS，VISU 這3種協(xié)議，并記錄了程序并行階段的運(yùn)行時(shí)間，如圖8所示.

Fig. 8 Normalized execution time圖8 歸一化的運(yùn)行時(shí)間

實(shí)驗(yàn)結(jié)果以MESI協(xié)議的運(yùn)行時(shí)間進(jìn)行歸一化.平均來看，無目錄、有2個(gè)穩(wěn)定狀態(tài)的VISU協(xié)議獲得了與有目錄、3個(gè)穩(wěn)定狀態(tài)的MESI協(xié)議幾乎一樣的性能.從FFT程序中可以看出，VISU性能較之MESI協(xié)議有11%的性能提升，一方面來源于私有數(shù)據(jù)占有比例高；另一方面來源于同步操作，在VISU(VIPS)協(xié)議中對(duì)于同步操作進(jìn)行自更新(自失效)，這是一類為了保證正確性但開銷大的操作，但在FFT中所占比例很少.Water-Nsp的同步操作占有的比例較大，同時(shí)私有請(qǐng)求比例較少，所以VISU協(xié)議的整體性能相比于MESI協(xié)議有了8%的性能損失.在同步點(diǎn)比例大時(shí)，VISU協(xié)議相對(duì)VIPS協(xié)議能夠降低由于同步點(diǎn)導(dǎo)致的大量cache失效，從Water-Nsp程序上可以看出，相對(duì)VIPS協(xié)議，VISU有了4%的性能提升.整體上來看，簡(jiǎn)單地更新有限共享數(shù)據(jù)的VISU協(xié)議性能略高于VIPS協(xié)議(平均0.2%的性能提高).

3.4 VISU的開銷

在存儲(chǔ)開銷方面，表2為3種協(xié)議的特征對(duì)比， MESI目錄協(xié)議采用全映射(full-map)目錄.圖9展示的是N節(jié)點(diǎn)系統(tǒng)的MESI協(xié)議基本的目錄表項(xiàng)，其中2個(gè)主要的存儲(chǔ)開銷：每個(gè)數(shù)據(jù)block的擁有者(owner)和數(shù)據(jù)block的共享列表(sharer list)，每個(gè)表項(xiàng)都需要增加lbN位和N位.這些存儲(chǔ)開銷嚴(yán)重地影響目錄協(xié)議的可擴(kuò)展性.在MESI目錄協(xié)議中，目錄信息存儲(chǔ)在LLC的tag中，實(shí)驗(yàn)中測(cè)試了3種協(xié)議LLC tag的面積開銷，如表2所示.VIPS和VISU協(xié)議沒有目錄，從而降低了25.4%的面積開銷.

Table 2 Comparison of Three Protocols表2 3種協(xié)議對(duì)比

Fig. 9 Directory entry for a bock in a system with N nodes圖9 N個(gè)節(jié)點(diǎn)系統(tǒng)中block的目錄表項(xiàng)

cache一致性協(xié)議的驗(yàn)證問題是CMP設(shè)計(jì)中的重要課題，在驗(yàn)證開銷方面，VISU與VIPS協(xié)議分別采用自更新和自失效的方式作廢過期的備份，這是2種1對(duì)1的方式，而MESI目錄協(xié)議采用的是利用目錄的共享列表進(jìn)行多播，如表2所示.

此外目錄協(xié)議通過目錄向數(shù)據(jù)擁有者(owner)發(fā)送數(shù)據(jù)請(qǐng)求，增加了額外的間接事務(wù)，而VISU和VIPS協(xié)議沒有間接訪問.VISU協(xié)議利用私有和共享數(shù)據(jù)的劃分，把協(xié)議分成了獨(dú)立的2個(gè)部分，可分別進(jìn)行驗(yàn)證.同時(shí)VISU協(xié)議只有2個(gè)穩(wěn)定狀態(tài)：有效(valid)和無效(invalid)，在L1 cache中只有2個(gè)中間狀態(tài)(IV，VI)，相對(duì)于MESI協(xié)議有4種穩(wěn)定狀態(tài)、在L1 cache中有11種中間狀態(tài)和各種間接事務(wù)，VISU和VIPS協(xié)議在驗(yàn)證方面具有顯著的優(yōu)勢(shì).

3.5 VISU中延時(shí)寫直達(dá)的影響

為了進(jìn)一步說明寫直達(dá)中延時(shí)時(shí)間對(duì)于VISU協(xié)議的影響，實(shí)驗(yàn)中分別測(cè)試了100 cycle，500 cycle，1 000 cycle延時(shí)對(duì)于測(cè)試程序報(bào)文數(shù)量的影響.如圖10所示：

Fig. 10 Number of packects in the VISU and VIPS圖10 VISU和VIPS寫直達(dá)延時(shí)時(shí)間與報(bào)文數(shù)量

采用延時(shí)寫直達(dá)，能夠利用局部性原理，合并多次對(duì)同一個(gè)cache line的寫操作，減少寫直達(dá)的次數(shù)，降低整個(gè)系統(tǒng)的報(bào)文數(shù)量.但延時(shí)寫直達(dá)操作，必須保證VISU協(xié)議的正確性和系統(tǒng)性能，確保寫入的數(shù)據(jù)能夠及時(shí)對(duì)其他核可見.從圖10可以看出，當(dāng)延時(shí)從100 cycles增加到500 cycles時(shí)，報(bào)文數(shù)量顯著減少，平均減少了30.7%.但從500 cycles 增加到1 000 cycles，報(bào)文數(shù)量整體減少了6.8%，其中LU和LU-Non 這2個(gè)程序報(bào)文數(shù)量幾乎沒有減少.因此在VISU協(xié)議中設(shè)置延時(shí)寫直達(dá)的時(shí)間為500 cycle.

3.6 VISU協(xié)議對(duì)cache缺失率的影響

VISU協(xié)議與VIPS協(xié)議的主要區(qū)別在于采用自更新的方式提高L1 cache的命中率.對(duì)于同步點(diǎn)采用自更新還是自失效，主要取決于2個(gè)同步點(diǎn)之間的數(shù)據(jù)是否會(huì)被再一次訪問.圖11描述的是VIPS和VISU協(xié)議的L1 cache失效率，以VIPS協(xié)議的失效率進(jìn)行歸一化.

Fig. 11 Normalized cache miss rate in the VISU and VIPS圖11 自更新VISU協(xié)議與自失效VIPS協(xié)議缺失率

由于協(xié)議中自更新和自失效的數(shù)據(jù)都是共享數(shù)據(jù)，共享數(shù)據(jù)被多個(gè)核訪存，很可能會(huì)被再一次訪問到.同時(shí)為了解決在自更新的過程中共享數(shù)據(jù)不斷增加的問題，在VISU協(xié)議中采用預(yù)設(shè)一個(gè)閾值，當(dāng)共享數(shù)據(jù)的數(shù)量超過這個(gè)閾值時(shí)，超過的部分采用自失效，防止共享數(shù)據(jù)的累增.當(dāng)共享數(shù)據(jù)的數(shù)量少于這個(gè)閾值時(shí)，則采用自更新方式.VISU協(xié)議采用最后訪問的共享數(shù)據(jù)最先被自更新的策略，設(shè)置一個(gè)閾值x，對(duì)最后被訪問的x個(gè)共享數(shù)據(jù)進(jìn)行自更新，對(duì)其他的共享數(shù)據(jù)采用自失效，在本實(shí)驗(yàn)中設(shè)置x=50.利用在同步點(diǎn)進(jìn)行自更新的方式可以明顯地降低cache失效率，自更新的VISU協(xié)議相比VIPS協(xié)議平均降低了5.2%的L1 cache失效率.

4 結(jié)束語(yǔ)

本文針對(duì)于共享存儲(chǔ)中的cache一致性協(xié)議進(jìn)行了簡(jiǎn)化，提出一種沒有目錄和間接訪問、沒有眾多一致性狀態(tài)和競(jìng)爭(zhēng)的cache一致性協(xié)議VISU.VISU協(xié)議的關(guān)鍵：1)區(qū)分私有和共享數(shù)據(jù)，對(duì)私有數(shù)據(jù)采用寫回策略，對(duì)共享數(shù)據(jù)采用寫直達(dá)策略；2)利用DRF編程模型中的同步點(diǎn)進(jìn)行自更新.在VISU協(xié)議中，自更新是一種高效處理過期備份的方式.與一直以來獲得廣泛使用的目錄式和監(jiān)聽式協(xié)議相比，VISU協(xié)議大大簡(jiǎn)化了復(fù)雜性，解決了一直以來困擾目錄協(xié)議可擴(kuò)展性的目錄開銷問題.VISU協(xié)議不僅不需要像監(jiān)聽協(xié)議一樣廣播大量的請(qǐng)求，并且還適用于mesh和torus等無序網(wǎng)絡(luò).

通過仿真與分析，相對(duì)于復(fù)雜的MESI協(xié)議，簡(jiǎn)單的VISU協(xié)議具有與之相當(dāng)甚至更優(yōu)的性能.接下來的工作將會(huì)針對(duì)VISU自更新操作，優(yōu)化共享數(shù)據(jù)，提高自更新操作的效率.并進(jìn)一步將VISU協(xié)議擴(kuò)展到層次集群式的cache結(jié)構(gòu)(hierarchical clustered cache)上，提高VISU協(xié)議的可擴(kuò)展性.