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

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

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

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

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

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

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

2) 簡化成2個穩(wěn)定狀態(tài).通過TLB表項(xiàng)提供的頁面粒度的私有共享信息，VISU協(xié)議在cache line中只需要2個穩(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個條件，然后具體描述VISU協(xié)議，最后結(jié)合定義與描述論證VISU協(xié)議的正確性.

1.1 一致性的定義

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

1.2 VISU協(xié)議的描述

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

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

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

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

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

① VISU協(xié)議針對私有數(shù)據(jù)的處理.VISU協(xié)議對私有數(shù)據(jù)處理類似于單核處理器的處理，采用cache寫回策略.圖1和圖2展示了2級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)為L1 cache控制器的狀態(tài)轉(zhuǎn)換圖，圖2(b)為LLC 控制器的狀態(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)換.整個協(xié)議只包含2種穩(wěn)定狀態(tài)V和I、2種中間狀態(tài)VI和IV，并且不需要目錄和間接事務(wù).

② VISU協(xié)議針對共享數(shù)據(jù)的處理.為了滿足一致性的定義，一致性協(xié)議必須對寫操作立即響應(yīng)，失效其他核cache備份，返回最新的數(shù)據(jù).因?yàn)闆]有了目錄記錄數(shù)據(jù)的共享者和擁有者，VISU協(xié)議對于共享數(shù)據(jù)的處理就要確定最近寫入數(shù)據(jù)的位置并失效過期的備份，所以VISU協(xié)議添加了一個額外的自更新操作，用以自動更新過期的備份.相比于私有數(shù)據(jù)協(xié)議，共享數(shù)據(jù)協(xié)議用寫直達(dá)操作代替寫回操作，保證在LLC中始終存放最新的數(shù)據(jù)，從而使得共享數(shù)據(jù)協(xié)議與私有數(shù)據(jù)協(xié)議一樣的簡單，沒有目錄和間接事務(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)，首先對于讀缺失，L1 cache發(fā)送GetS到LLC中獲取數(shù)據(jù)Data.對于寫缺失，如圖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編程模型識別同步點(diǎn)，在同步點(diǎn)(Sync)進(jìn)行自更新操作(SelfU).如圖3(d)所示，L1 cache發(fā)送SelfU到LLC中，LLC返回最新的數(shù)據(jù)，主動地自更新操作消除了間接的失效.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在VISU協(xié)議中沒有間接的失效操作.一個核結(jié)束了敏感區(qū)，釋放了一個條件，在協(xié)議上不會去通知正在旋轉(zhuǎn)的核條件的改變，從而難以完成同步操作.為此VISU一致性協(xié)議針對讀-修改-寫(RMW)的原子事務(wù)，采用重新讀取LLC數(shù)據(jù)的方式(因?yàn)榇嬖诙鄠€核訪問一個數(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占用這個鎖，并釋放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)，直到競爭到條件滿足讀到Data(0)，進(jìn)入敏感區(qū).這種繞過L1中的數(shù)據(jù)，直接訪問LLC的方式，造成了一定的性能損失，但同步操作在整個程序中出現(xiàn)的頻率很小，整體性能損失依然可以被接受，第3節(jié)的實(shí)驗(yàn)評估也驗(yàn)證了這一點(diǎn).VISU協(xié)議通過這種方式實(shí)現(xiàn)了對同步原語的支持.

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

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

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

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

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

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

為了評估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ù)工藝對cache的開銷進(jìn)行評估.設(shè)計(jì)中仿真8核的片上多核處理器(chip multiprocessors, CMP)結(jié)構(gòu)，運(yùn)行SPLASH-2中的測試程序.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)并行測試程序進(jìn)行測試.模擬器中主要的參數(shù)如表1所示:

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

實(shí)驗(yàn)過程中通過識別操作系統(tǒng)和并行程序中的同步點(diǎn)(旋轉(zhuǎn)鎖、柵欄、中斷)進(jìn)行自更新操作.利用GEM5全系統(tǒng)模擬器，仿真整個并行程序，統(tǒng)計(jì)程序并行階段的數(shù)據(jù).實(shí)驗(yàn)中仿真了3種一致性協(xié)議：1)MESI目錄協(xié)議，該協(xié)議由2級cache組成，實(shí)時(shí)存儲著目錄信息.MESI目錄協(xié)議根據(jù)目錄記錄的信息發(fā)送消息失效所有的共享者(寫缺失)或者發(fā)送消息獲取最新的數(shù)據(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)對共享數(shù)據(jù)進(jìn)行自更新，提高cache的命中率，從而提高系統(tǒng)性能.

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

3.2 程序請求的分類

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

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

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

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

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

3.4 VISU的開銷

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

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

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

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

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

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

為了進(jìn)一步說明寫直達(dá)中延時(shí)時(shí)間對于VISU協(xié)議的影響，實(shí)驗(yàn)中分別測試了100 cycle，500 cycle，1 000 cycle延時(shí)對于測試程序報(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á)，能夠利用局部性原理，合并多次對同一個cache line的寫操作，減少寫直達(dá)的次數(shù)，降低整個系統(tǒng)的報(bào)文數(shù)量.但延時(shí)寫直達(dá)操作，必須保證VISU協(xié)議的正確性和系統(tǒng)性能，確保寫入的數(shù)據(jù)能夠及時(shí)對其他核可見.從圖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個程序報(bào)文數(shù)量幾乎沒有減少.因此在VISU協(xié)議中設(shè)置延時(shí)寫直達(dá)的時(shí)間為500 cycle.

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

VISU協(xié)議與VIPS協(xié)議的主要區(qū)別在于采用自更新的方式提高L1 cache的命中率.對于同步點(diǎn)采用自更新還是自失效，主要取決于2個同步點(diǎn)之間的數(shù)據(jù)是否會被再一次訪問.圖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ù)被多個核訪存，很可能會被再一次訪問到.同時(shí)為了解決在自更新的過程中共享數(shù)據(jù)不斷增加的問題，在VISU協(xié)議中采用預(yù)設(shè)一個閾值，當(dāng)共享數(shù)據(jù)的數(shù)量超過這個閾值時(shí)，超過的部分采用自失效，防止共享數(shù)據(jù)的累增.當(dāng)共享數(shù)據(jù)的數(shù)量少于這個閾值時(shí)，則采用自更新方式.VISU協(xié)議采用最后訪問的共享數(shù)據(jù)最先被自更新的策略，設(shè)置一個閾值x，對最后被訪問的x個共享數(shù)據(jù)進(jìn)行自更新，對其他的共享數(shù)據(jù)采用自失效，在本實(shí)驗(yàn)中設(shè)置x=50.利用在同步點(diǎn)進(jìn)行自更新的方式可以明顯地降低cache失效率，自更新的VISU協(xié)議相比VIPS協(xié)議平均降低了5.2%的L1 cache失效率.

4 結(jié)束語

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

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