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

(國防科技大學計算機學院 長沙 410073)

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

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

2011年Cuesta 等人[2]利用數(shù)據(jù)劃分的方法對協(xié)議進行優(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ù)塊的信息，有效地提高了目錄的利用率.實驗結(jié)果表明：在相同的目錄大小情況下，他們的方案獲得15%的性能提高.然而他們這種針對于目錄利用率的優(yōu)化并沒有真正地解決協(xié)議中的目錄開銷、大量的一致性狀態(tài)和間接訪問等問題.2012年Ros 等人[12]利用劃分私有和共享數(shù)據(jù)的方法，進行動態(tài)的寫策略切換.這種寫策略對私有數(shù)據(jù)進行寫回，對共享數(shù)據(jù)進行寫直達，簡化了一致性狀態(tài).利用并行程序的數(shù)據(jù)無競爭(data race free, DRF)模型[13]，在同步點進行共享數(shù)據(jù)自失效的方法完全避免了目錄的存儲開銷.相對于目錄協(xié)議，他們的設(shè)計平均減少了14.2%的系統(tǒng)能耗.但是寫直達方式以及同步點自失效的方法大大增加了系統(tǒng)cache的缺失率，影響系統(tǒng)性能.

針對上述問題，本文主要研究共享存儲一致性協(xié)議的簡化.在滿足DRF的模型下，設(shè)計了一種基于自更新操作(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ù)的共享特性，進行私有共享數(shù)據(jù)塊的動態(tài)劃分.在共享數(shù)據(jù)方面，VISU協(xié)議采用了寫直達和自更新操作，LLC(last level cache)始終保持著最新的共享數(shù)據(jù)，同時自更新操作及時地更新過期的備份.在私有數(shù)據(jù)方面，VISU協(xié)議采用寫回方式，在協(xié)議中不需要目錄記錄信息，不進行一致性的維護(類似于單核訪問).因此整個協(xié)議消除了目錄和間接事務(wù).

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

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

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

1.1 一致性的定義

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

1.2 VISU協(xié)議的描述

本文設(shè)計一種基于自更新操作只包含2個穩(wěn)定狀的簡單高效VISU協(xié)議.協(xié)議可分成私有和共享2個獨立的部分.首先我們介紹數(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ù)競爭，即當2個不同的線程同時訪問相同的存儲單元且至少有一個是寫操作時，必然存在同步語句把它們分開.數(shù)據(jù)競爭經(jīng)常導(dǎo)致程序的錯誤.DRF編程模型是C++和Java高級編程語言存儲模型的基礎(chǔ)，絕大部分并行程序都滿足DRF編程模型.因此VISU協(xié)議利用了程序的DRF特性進行一致性的設(shè)計.

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

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

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

① 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)圖

當發(fā)生讀(Rd)缺失時，如圖1(a)，L1 cache發(fā)送GetS到LLC，然后獲取Data數(shù)據(jù)；當發(fā)生寫(Wrt)缺失時，如圖1(b)所示，L1發(fā)送GetX到LLC中，LLC返回Data數(shù)據(jù).由于數(shù)據(jù)為私有數(shù)據(jù)，其他核不存在數(shù)據(jù)的備份，所以讀缺失和寫缺失不需要向其他核發(fā)送間接事務(wù).當L1 cache發(fā)生驅(qū)逐時采用寫回策略(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消息，然后進行I→IV→V(LLC無數(shù)據(jù)時，從內(nèi)存中讀取并返回Mem_data數(shù)據(jù))或者V→V的狀態(tài)轉(zhuǎn)換.圖2(b)右半部分則是LLC發(fā)生驅(qū)逐時，把臟的數(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ù).因為沒有了目錄記錄數(shù)據(jù)的共享者和擁有者，VISU協(xié)議對于共享數(shù)據(jù)的處理就要確定最近寫入數(shù)據(jù)的位置并失效過期的備份，所以VISU協(xié)議添加了一個額外的自更新操作，用以自動更新過期的備份.相比于私有數(shù)據(jù)協(xié)議，共享數(shù)據(jù)協(xié)議用寫直達操作代替寫回操作，保證在LLC中始終存放最新的數(shù)據(jù)，從而使得共享數(shù)據(jù)協(xié)議與私有數(shù)據(jù)協(xié)議一樣的簡單，沒有目錄和間接事務(wù).

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

Fig. 3 VISU:Rd, Wrt, WT-timeout and Sync transactions of shared data圖3 VISU共享數(shù)據(jù)讀(Rd)、寫(Wrt)、寫直達(WT-timeout)、同步點(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é)議要進行寫直達(WT)操作，把寫入的數(shù)據(jù)及時地寫直達(WT)到LLC中，這樣保證LLC一直擁有最新的數(shù)據(jù).為了降低寫直達產(chǎn)生的大量報文，如圖3(c)所示，協(xié)議采用了延時寫直達(WT-timeout)的方式.最后為了更新過期的備份，協(xié)議利用DRF編程模型識別同步點，在同步點(Sync)進行自更新操作(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ù)據(jù).

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

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

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

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

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

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

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

Fig. 5 Format of TLB entry and page table entry圖5 TLB entry和頁表項的組成

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

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

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

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

2.2 私有到共享的切換機制

TLB缺失就進行頁面的訪問，當某個核首次訪問一個頁面時，頁面被置為私有頁面且訪問的核作為頁面的擁有者(Keeper).整個頁面里的數(shù)據(jù)為私有數(shù)據(jù)，這些數(shù)據(jù)在L1 cache中采用寫回的方式.第2個核訪問這個頁面，發(fā)現(xiàn)頁面被Keeper設(shè)置為私有(P域為1)，這時觸發(fā)切換機制，向Keeper核發(fā)送中斷，完成中斷后設(shè)置頁表項中的頁面為共享(P域設(shè)為0).Keeper核接收到中斷就更新這個頁面的TLB 表項(設(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é)議中同步原語的支持

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

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

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

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

實驗過程中通過識別操作系統(tǒng)和并行程序中的同步點(旋轉(zhuǎn)鎖、柵欄、中斷)進行自更新操作.利用GEM5全系統(tǒng)模擬器，仿真整個并行程序，統(tǒng)計程序并行階段的數(shù)據(jù).實驗中仿真了3種一致性協(xié)議：1)MESI目錄協(xié)議，該協(xié)議由2級cache組成，實時存儲著目錄信息.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è)計中的VISU設(shè)計類似，但VIPS協(xié)議在同步點上采用的是自失效操作.采用同步點自失效的方法保證了協(xié)議的一致性，但一定程度上增加了L1 cache的缺失率.3)本文提出的VISU協(xié)議.該協(xié)議在同步點采用自更新的方式，即在同步點對共享數(shù)據(jù)進行自更新，提高cache的命中率，從而提高系統(tǒng)性能.

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

3.2 程序請求的分類

VISU協(xié)議動態(tài)識別程序中的私有和共享數(shù)據(jù)，采用2種不同的方法進行處理.實驗中運行了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é)議中采用寫回的方式進行處理，不進行私有和共享的劃分.從圖7可以看出，私有數(shù)據(jù)請求比例在FFT中最大，占程序總請求的5.1%.若把私有數(shù)據(jù)請求和取指請求均作為私有請求處理(二者采用相同的私有數(shù)據(jù)協(xié)議)，則私有請求數(shù)量占有比例高達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é)議運行性能

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

Fig. 8 Normalized execution time圖8 歸一化的運行時間

實驗結(jié)果以MESI協(xié)議的運行時間進行歸一化.平均來看，無目錄、有2個穩(wěn)定狀態(tài)的VISU協(xié)議獲得了與有目錄、3個穩(wěn)定狀態(tài)的MESI協(xié)議幾乎一樣的性能.從FFT程序中可以看出，VISU性能較之MESI協(xié)議有11%的性能提升，一方面來源于私有數(shù)據(jù)占有比例高；另一方面來源于同步操作，在VISU(VIPS)協(xié)議中對于同步操作進行自更新(自失效)，這是一類為了保證正確性但開銷大的操作，但在FFT中所占比例很少.Water-Nsp的同步操作占有的比例較大，同時私有請求比例較少，所以VISU協(xié)議的整體性能相比于MESI協(xié)議有了8%的性能損失.在同步點比例大時，VISU協(xié)議相對VIPS協(xié)議能夠降低由于同步點導(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é)點系統(tǒng)的MESI協(xié)議基本的目錄表項，其中2個主要的存儲開銷：每個數(shù)據(jù)block的擁有者(owner)和數(shù)據(jù)block的共享列表(sharer list)，每個表項都需要增加lbN位和N位.這些存儲開銷嚴重地影響目錄協(xié)議的可擴展性.在MESI目錄協(xié)議中，目錄信息存儲在LLC的tag中，實驗中測試了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é)點系統(tǒng)中block的目錄表項

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

此外目錄協(xié)議通過目錄向數(shù)據(jù)擁有者(owner)發(fā)送數(shù)據(jù)請求，增加了額外的間接事務(wù)，而VISU和VIPS協(xié)議沒有間接訪問.VISU協(xié)議利用私有和共享數(shù)據(jù)的劃分，把協(xié)議分成了獨立的2個部分，可分別進行驗證.同時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ōu)勢.

3.5 VISU中延時寫直達的影響

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

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

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

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

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

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

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

4 結(jié)束語

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

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