面向非寫分配高速緩存的一致性協(xié)議及實(shí)現(xiàn)

修思文，黃 凱，余 慜，謝天藝，葛海通，嚴(yán)曉浪

（1.浙江大學(xué) 超大規(guī)模集成電路研究所，浙江 杭州310027；2.杭州中天微系統(tǒng)有限公司，浙江 杭州310027）

隨著性能和功耗需求的不斷增長(zhǎng)，多核處理器系統(tǒng)已被業(yè)界廣泛使用.其中，基于對(duì)稱式共享存儲(chǔ)器的多核處理器架構(gòu)具有較低的通信延遲、易懂的編程模型、高效的代碼和數(shù)據(jù)共享等特點(diǎn)因而備受歡迎，也最為常用［1］.由于共享數(shù)據(jù)的存在，可能出現(xiàn)一個(gè)數(shù)據(jù)的多個(gè)版本同時(shí)存在于共享存儲(chǔ)器和多個(gè)處理器的高速緩存（cache）中的情況.如果此時(shí)有多于一個(gè)的處理器對(duì)該數(shù)據(jù)進(jìn)行寫操作，則可能出現(xiàn)數(shù)據(jù)不一致的問題，導(dǎo)致程序執(zhí)行發(fā)生錯(cuò)誤.緩存一致性協(xié)議是一種用于保證多核處理器系統(tǒng)各處理器緩存中數(shù)據(jù)一致的機(jī)制，可由軟件或硬件方式來實(shí)現(xiàn)［2］.采用硬件方式維護(hù)一致性非常方便高效而且對(duì)軟件透明，因此被廣泛采用［3］.其中，基于監(jiān)聽式的寫無效協(xié)議具有對(duì)互連帶寬占用小、硬件實(shí)現(xiàn)簡(jiǎn)單、資源占用較少等優(yōu)點(diǎn)，被大多數(shù)多核處理器所采用［4］.

寫無效協(xié)議和處理器所采用的緩存的類型相關(guān)，如更新內(nèi)存的方式是寫回（write back）還是寫透（write through）；寫缺失時(shí)的策略是寫分配（write allocate）還是非寫分配（no-write allocate）.一些面向特殊應(yīng)用的多核處理器會(huì)經(jīng)常處理一些有大量數(shù)據(jù)重用的、輸入和輸出的數(shù)據(jù)流地址不相關(guān)的并行化應(yīng)用（如圖像處理等），適合采用基于寫回、非寫分配的緩存［5］，避免不必要的緩存分配，減小對(duì)存儲(chǔ)器帶寬的壓力.然而，現(xiàn)有的一致性協(xié)議及一些優(yōu)化措施［6-9］都是針對(duì)寫回、寫分配的緩存.雖然傳統(tǒng)的寫無效協(xié)議可以應(yīng)用在非寫分配的緩存上，但發(fā)生寫缺失時(shí)，不僅要發(fā)起對(duì)共享存儲(chǔ)器的寫操作，而且系統(tǒng)中不再存在有效的該緩存行，對(duì)性能和功耗的損失很大，亟待改進(jìn).

針對(duì)基于寫回、非寫分配緩存的特點(diǎn)，本文提出一種新型的高速緩存一致性協(xié)議——寫干涉協(xié)議及其硬件架構(gòu).采用寫干涉協(xié)議，可以減少對(duì)共享存儲(chǔ)器的讀寫操作，降低了功耗，提升了系統(tǒng)的性能.

1 現(xiàn)有的寫無效協(xié)議

現(xiàn)有的寫無效協(xié)議主要包括MESI（Modified／Exclusive／Shared／Invalid）及其變種協(xié)議.MESI協(xié)議應(yīng)用比較廣泛，其缺點(diǎn)是只能共享干凈的緩存行——緩存行從修改狀態(tài)（M）轉(zhuǎn)移到其他狀態(tài)時(shí)，一定要引起 寫 回 操 作.MOESI（Modified／Owner／Exclusive／Shared／Invalid）協(xié)議解決了這個(gè)問題，它引入了所有者狀態(tài)（O），支持了臟數(shù)據(jù)的共享，減少了寫回操作，是目前最為流行的MESI類協(xié)議［4］，被AMD、ARM等公司所采用.Intel公司提出的MESIF（Modified／Exclusive／Shared／Invalid／Forward）協(xié)議是另外一種MESI協(xié)議的另外一個(gè)變種，但其旨在解決ccNUMA（Cache Coherence Non Uniform Memory Access）架構(gòu)中處理器子系統(tǒng)間的一致性問題［10］.然而，現(xiàn)有的MESI和MOESI等協(xié)議在應(yīng)用到寫回、非寫分配的緩存時(shí)，都會(huì)引起性能和功耗上的損失，這里以MESI為典型例子加以說明.基于寫回、非寫分配的緩存的MESI協(xié)議的狀態(tài)轉(zhuǎn)換如圖1所示.

圖1 基于寫回、非寫分配緩存的MESI協(xié)議狀態(tài)轉(zhuǎn)換圖Fig.1 Write-back and no-write-allocate cache based MESI protocol state transition

處理器發(fā)生寫缺失時(shí)，先發(fā)出一個(gè)寫缺失請(qǐng)求，使其他處理器中該緩存行的副本無效，然后再把數(shù)據(jù)寫到共享存儲(chǔ)器中.其他處理器若監(jiān)聽到有處理器對(duì)處于獨(dú)占（E）、共享（S）或修改狀態(tài)（M）的緩存行進(jìn)行寫操作，都將該緩存行的狀態(tài)轉(zhuǎn)換為無效狀態(tài)（I），處于修改狀態(tài)（M）的緩存行還要搶先寫回共享存儲(chǔ)器中.可見，由于采用非寫分配的高速緩存，當(dāng)有處理器對(duì)某個(gè)高速緩存行產(chǎn)生一次寫缺失時(shí)，需要發(fā)起對(duì)共享存儲(chǔ)器的寫更新操作，且所有處理器均不存在該高速緩存行的有效副本.緊接著，任何處理器下一次對(duì)該緩存行的讀操作也必定是缺失的，且需要發(fā)起對(duì)共享存儲(chǔ)器中該行的讀操作.更差的情況，如果沒有處理器發(fā)起過對(duì)該緩存行的讀操作，之后對(duì)該緩存行的寫操作都是缺失的，處理器會(huì)頻繁地發(fā)起對(duì)共享存儲(chǔ)器的訪問.由于外部共享存儲(chǔ)器一般由容量較大的DRAM 實(shí)現(xiàn)，需要不斷的刷新，不僅功耗較大，而且訪問延時(shí)遠(yuǎn)大于處理器內(nèi)部時(shí)鐘，因此，以上情況極大地影響了性能和功耗.

2 寫干涉協(xié)議

針對(duì)現(xiàn)有MOESI等協(xié)議運(yùn)用于寫回、非寫分配緩存的缺點(diǎn)，提出了寫干涉協(xié)議，該協(xié)議利用以下5種狀態(tài)的一種來標(biāo)記各緩存行：

無效狀態(tài)（I）：指示該緩存行無效.

獨(dú)占干凈狀態(tài)（EC）：指示該緩存行只存在于當(dāng)前的緩存中，并且是干凈的（和共享存儲(chǔ)器中該行中的數(shù)據(jù)一致）.當(dāng)監(jiān)聽到數(shù)據(jù)請(qǐng)求時(shí)，處于EC 狀態(tài)的緩存行必須提供數(shù)據(jù).

獨(dú)占修改狀態(tài)（ED）：指示該緩存行只存在于當(dāng)前的緩存中，但它已被修改過，是臟的（在共享存儲(chǔ)器中的該行中的數(shù)據(jù)不再有效）.當(dāng)監(jiān)聽到數(shù)據(jù)請(qǐng)求時(shí)，處于ED 狀態(tài)的緩存行必須提供數(shù)據(jù).

共享干凈狀態(tài)（SC）：指示該緩存行存在于當(dāng)前的緩存中，而且其他處理器也可能擁有該緩存行.處于SC狀態(tài)的緩存行在被替換時(shí)不負(fù)責(zé)更新共享存儲(chǔ)器；當(dāng)監(jiān)聽到數(shù)據(jù)請(qǐng)求時(shí)，如果被仲裁選中，它必須提供數(shù)據(jù).

共享修改狀態(tài)（SD）：指示該緩存行存在于當(dāng)前的緩存中，而且其他處理器也可能擁有該緩存行.處于SD 狀態(tài)的緩存行在被替換時(shí)負(fù)責(zé)更新共享存儲(chǔ)器；當(dāng)監(jiān)聽到數(shù)據(jù)請(qǐng)求時(shí)，如果被仲裁選中，它必須提供數(shù)據(jù).

本協(xié)議定義了2個(gè)標(biāo)記：“修改者標(biāo)記”和“所有者標(biāo)記”.擁有修改者標(biāo)記的緩存行要負(fù)責(zé)把被修改過的數(shù)據(jù)寫回到共享存儲(chǔ)器中.因此，處于ED 狀態(tài)和SD狀態(tài)的緩存行擁有修改者標(biāo)記.擁有所有者標(biāo)記的緩存行既要負(fù)責(zé)給請(qǐng)求該緩存行的處理器提供數(shù)據(jù)，也要承擔(dān)對(duì)該緩存行的寫干涉.顯然，處于ED狀態(tài)和EC狀態(tài)的緩存行擁有所有者標(biāo)記.當(dāng)緩存行在系統(tǒng)中僅存在SD狀態(tài)或SC狀態(tài)時(shí)，由核間互連負(fù)責(zé)仲裁、賦予所有者標(biāo)記.根據(jù)時(shí)間局部性原理，當(dāng)發(fā)生緩存間的數(shù)據(jù)拷貝時(shí)，修改者標(biāo)記將隨之遷移，請(qǐng)求該緩存行的處理將在下次所有者標(biāo)記仲裁時(shí)擁有最高的優(yōu)先級(jí).

如圖2所示列出了本協(xié)議的狀態(tài)轉(zhuǎn)換圖.當(dāng)某個(gè)處理器對(duì)某個(gè)緩存行中的某個(gè)地址產(chǎn)生寫缺失操作時(shí)：若其他所有處理器中均不存在有效的該緩存行，則把數(shù)據(jù)寫到共享存儲(chǔ)器的該地址中.若其他處理器中存在有效的該緩存行，則把數(shù)據(jù)直接寫入到其他處理器中擁有所有者標(biāo)記的該緩存行中（定義為“寫干涉”操作），并將其狀態(tài)轉(zhuǎn)換為ED 狀態(tài)；同時(shí)，把其他處理器的該緩存行無效掉（定義為“寫無效”操作），即狀態(tài)轉(zhuǎn)換為I狀態(tài).

當(dāng)某個(gè)處理器對(duì)某個(gè)緩存行中的某個(gè)地址產(chǎn)生讀缺失操作時(shí)：若其他所有處理器中均不存在有效的該緩存行，則將共享存儲(chǔ)器中的該地址行分配到該處理器的緩存中，狀態(tài)設(shè)為EC狀態(tài).若其他處理器中存在有效的該緩存行，則擁有所有者標(biāo)記的該緩存行負(fù)責(zé)提供數(shù)據(jù)，并將其狀態(tài)轉(zhuǎn)化為SC 狀態(tài).同時(shí)，提供數(shù)據(jù)的緩存行將其修改者標(biāo)記轉(zhuǎn)移給請(qǐng)求數(shù)據(jù)的緩存行.

圖2 寫干涉協(xié)議狀態(tài)轉(zhuǎn)換圖Fig.2 Write intervention protocol state transition

當(dāng)某個(gè)處理器對(duì)某個(gè)處于SD 或SC 狀態(tài)的緩存行中的某個(gè)地址產(chǎn)生寫命中操作時(shí)：若不存在其他有效的該緩存行，則可以執(zhí)行該寫操作，且狀態(tài)轉(zhuǎn)換為ED 狀態(tài)；若存在有效的該緩存行，則須將它們均無效掉，然后發(fā)起該寫命中操作的處理器才可以執(zhí)行該寫操作，狀態(tài)轉(zhuǎn)換為ED 狀態(tài).

當(dāng)某個(gè)處理器對(duì)某個(gè)處于EC 狀態(tài)的緩存行的某個(gè)地址產(chǎn)生寫命中操作時(shí)，可以直接執(zhí)行該寫操作，狀態(tài)轉(zhuǎn)換為ED 狀態(tài).其他情況下，狀態(tài)不變.

3 協(xié)議正確性

利用符號(hào)模型狀態(tài)法［11］（symbolic state model，SSM），定義如下表示符：

0：表示有0個(gè)實(shí)例，表示時(shí)可以省略；

1：表示有且只有1個(gè)實(shí)例；

＋：表示1個(gè)或多個(gè)實(shí)例；

＊：表示0個(gè)、1個(gè)或多個(gè)實(shí)例.

通過這些符號(hào)，可以構(gòu)建復(fù)雜狀態(tài)的簡(jiǎn)明表示，例如可以用（SD1，SC＋，I＊）來表示：對(duì)于某個(gè)緩存行，一個(gè)或者多個(gè)緩存處于SC 狀態(tài)，僅有1個(gè)緩存處于SD 狀態(tài)，0個(gè)、1個(gè)或多個(gè)緩存是無效的.對(duì)于寫干涉協(xié)議，從初始的（I＋）狀態(tài)開始擴(kuò)張，每個(gè)狀態(tài)轉(zhuǎn)換的條件要覆蓋寫／讀操作和替換操作，最后形成的狀態(tài)轉(zhuǎn)換圖如圖3所示.共產(chǎn)生了另外7種狀態(tài)，在這些狀態(tài)中，一致性都得到了保證，從而驗(yàn)證了寫干涉協(xié)議的正確性.

圖3 寫干涉協(xié)議的SSM 狀態(tài)轉(zhuǎn)換Fig.3 SSM state transition of write intervention protocol

4 協(xié)議分析

4.1 寫缺失

對(duì)于現(xiàn)有MOESI等協(xié)議，需要把系統(tǒng)中有效的該緩存行無效掉，如果系統(tǒng)中存在被修改過的緩存行，還要先把該緩存行寫回到共享存儲(chǔ)器中，最后把寫缺失的數(shù)據(jù)寫到共享存儲(chǔ)器中.耗時(shí)（單位：處理器周期數(shù)）為

功耗為

式中：耗時(shí)和功耗從處理器發(fā)出一致性請(qǐng)求開始算起，下同；c為指示系統(tǒng)中緩存行是否都是干凈的布爾型變量，c＝1代表系統(tǒng)中該緩存行都是干凈的；n為表存在有效的該緩存行的處理器的個(gè)數(shù)；Tf和Wf分別為一致性操作固定的耗時(shí)和功耗；Tmb和Wmb分別為寫回一個(gè)緩存行的耗時(shí)和功耗，有Tf?Tmb；Wt為一致性命令更新一個(gè)處理器Tag RAM的功耗；Wmw為向共享存儲(chǔ)器某地址寫1個(gè)數(shù)據(jù)的功耗.設(shè)處理器每個(gè)緩存行包含k（一般k≥4）個(gè)寫數(shù)據(jù)寬度大小的數(shù)據(jù)，則有2Wmw＜Wmb≤kWmw.由于寫緩沖區(qū)的廣泛應(yīng)用，對(duì)共享存儲(chǔ)器的寫操作對(duì)系統(tǒng)性能的影響很小.假設(shè)寫緩沖區(qū)足夠大，從處理器角度看，認(rèn)為向共享存儲(chǔ)器寫一個(gè)數(shù)據(jù)沒有耗時(shí).

對(duì)于寫干涉協(xié)議，只需把數(shù)據(jù)直接寫到擁有所有者標(biāo)記的緩存行，并更新緩存狀態(tài)，同時(shí)把其他有效的緩存行無效掉.耗時(shí)為

功耗為

式中：Wcw為向處理器的某緩存行中寫一個(gè)數(shù)據(jù)的功耗，有Wt＜Wcw＜Wf?Wmw.

則寫干涉協(xié)議相對(duì)于現(xiàn)有MOESI等協(xié)議的耗時(shí)節(jié)省比例為

功耗節(jié)省比例為

根據(jù)前面對(duì)各系數(shù)的分析可知，當(dāng)c＝1時(shí)，βwm趨近于1，αwm＝0；當(dāng)c＝0時(shí)，βwm更趨近于1，αwm趨近于1.對(duì)比可見，采用寫干涉協(xié)議，發(fā)生寫缺失時(shí)，可以顯著降低系統(tǒng)功耗；當(dāng)存在臟緩存行時(shí)，可以顯著提高系統(tǒng)性能；當(dāng)不存在臟緩存行時(shí)，雖然性能沒有提升，但由于緩存中保留了有效的該緩存行，對(duì)寫缺失后再讀和寫缺失后再寫影響很大.

4.2 寫缺失后再讀

對(duì)于現(xiàn)有MOESI等協(xié)議，系統(tǒng)中已不存在有效的緩存行，從共享存儲(chǔ)器中讀取數(shù)據(jù)，并更新該緩存行狀態(tài).耗時(shí)為

功耗為

式中：Tmr和Wmr分別為從共享存儲(chǔ)器中讀取一個(gè)緩存行到緩存中的耗時(shí)和功耗.

對(duì)于寫干涉協(xié)議，如果發(fā)起讀請(qǐng)求的是處于ED 狀態(tài)的緩存行，直接命中；否則，產(chǎn)生讀缺失，由處于ED 狀態(tài)的緩存行提供數(shù)據(jù)，并更新雙方的緩存行狀態(tài).耗時(shí)為

功耗為

式中：e為指示發(fā)起讀請(qǐng)求的是否處于ED 狀態(tài)的緩存行的布爾型變量，e＝1時(shí)代表發(fā)起讀請(qǐng)求的是處于ED 狀態(tài)的緩存行；Tcr和Wcr分別為緩存間數(shù)據(jù)拷貝的耗時(shí)和功耗，有Tcr≤Tf?Tmr和Wt＜Wcr≤Wf?Wmr.

則寫干涉協(xié)議相對(duì)于現(xiàn)有MOESI等協(xié)議的耗時(shí)節(jié)省比例為

功耗節(jié)省比例為

根據(jù)前面對(duì)各系數(shù)的分析可知，當(dāng)e＝1 時(shí)，αwmr＝1，βwmr＝1；當(dāng)e＝0時(shí)，αwmr和βwmr均趨近于1.對(duì)比可見，采用寫干涉協(xié)議，發(fā)生寫缺失后再讀時(shí)，可以顯著降低系統(tǒng)功耗、提升系統(tǒng)性能.

4.3 寫缺失后再寫

如果寫缺失后還沒有處理器對(duì)該緩存行進(jìn)行過讀操作，對(duì)于現(xiàn)有MOESI等協(xié)議，系統(tǒng)中已不存在有效的該緩存行，直接把數(shù)據(jù)寫到共享存儲(chǔ)器中，耗時(shí)為

功耗為

對(duì)于寫干涉協(xié)議，如果發(fā)起讀請(qǐng)求的是處于ED 狀態(tài)的緩存行，直接命中；否則，直接把數(shù)據(jù)寫到出于ED 狀態(tài)的緩存行.耗時(shí)為

功耗為

則寫干涉協(xié)議相對(duì)于現(xiàn)有MOESI等協(xié)議的耗時(shí)節(jié)省比例為

功耗節(jié)省比例為

根據(jù)前面對(duì)各系數(shù)的分析可知，當(dāng)e＝0 時(shí)，αwmw＝0，βwmw均趨近于1；當(dāng)e＝1時(shí)，αwmw＝1，βwmw更趨近于1；可見，采用寫干涉協(xié)議，發(fā)生寫缺失后再寫時(shí)，可以顯著降低系統(tǒng)功耗；當(dāng)發(fā)起寫操作的是被寫干涉的處理器時(shí)，可以顯著提升系統(tǒng)性能.更重要的是，如果寫缺失之后沒有對(duì)該緩存行的讀操作，之后的寫操作仍然存在這些優(yōu)勢(shì).

5 硬件實(shí)現(xiàn)

5.1 總體架構(gòu)

圖4 CK610MP總體架構(gòu)Fig.4 Architecture of CK610MP

采用寫干涉協(xié)議，設(shè)計(jì)出如圖4所示的CK610MP多核處理器，由修改后的CK610處理器［12］、核間互連以及AMBA AXI總線接口單元組成，并支持2～8個(gè)處理器的配置.修改了CK610處理器的讀寫單元（LSU）部分的邏輯，使其支持一致性請(qǐng)求的發(fā)起和一致性命令的響應(yīng).定制了核間互連模塊，它不僅負(fù)責(zé)維護(hù)寫干涉協(xié)議，還負(fù)責(zé)處理對(duì)共享存儲(chǔ)器的請(qǐng)求；為了提高帶寬，把數(shù)據(jù)和指令的通道分開.由于指令不存在一致性的問題，以下只討論數(shù)據(jù)通道.

5.2 核間互連設(shè)計(jì)

如圖5所示，核間互連由請(qǐng)求單元、一致性處理單元、存儲(chǔ)器接口單元和應(yīng)答單元組成.

請(qǐng)求單元負(fù)責(zé)串行化各個(gè)處理器的訪問，并把一致性訪問轉(zhuǎn)發(fā)到一致性處理單元，把非一致性訪問轉(zhuǎn)發(fā)到存儲(chǔ)器接口單元.

圖5 核間互連架構(gòu)Fig.5 Architecture of interconnect

一致性處理單元是核間互連的核心模塊.一致性處理單元收到訪問請(qǐng)求后，首先把信息壓入一致性請(qǐng)求隊(duì)列，同時(shí)查詢Snoop Tag.下一個(gè)周期結(jié)果出來后進(jìn)行比較，并根據(jù)查詢的結(jié)果產(chǎn)生相應(yīng)的一致性命令.由于Tag 比較后的時(shí)序已經(jīng)非常緊張了，一致性命令會(huì)進(jìn)入一致性命令緩沖區(qū)，下一個(gè)周期再發(fā)往相應(yīng)的處理器，同時(shí)請(qǐng)求更新Snoop Tag.當(dāng)一致性操作是讀缺失時(shí)，如果Snoop Tag查詢結(jié)果指示系統(tǒng)中存在有效的該緩存行，通過緩存間數(shù)據(jù)拷貝獲取數(shù)據(jù)并發(fā)送給應(yīng)答單元；否則把讀請(qǐng)求發(fā)給存儲(chǔ)器接口單元.當(dāng)一致性操作是寫缺失時(shí)，如果Snoop Tag查詢結(jié)果指示系統(tǒng)中存在有效的該緩存行，則通過寫干涉命令把缺失的數(shù)據(jù)寫到擁有所有者標(biāo)記的緩存中；否則把數(shù)據(jù)發(fā)送給存儲(chǔ)器接口單元，寫到共享存儲(chǔ)器中.

存儲(chǔ)器接口單元由寫緩沖區(qū)、讀緩沖區(qū)及總線接口組成，負(fù)責(zé)接收并發(fā)起對(duì)共享存儲(chǔ)器的訪問.

應(yīng)答單元接收到一致性處理單元或存儲(chǔ)器接口單元的響應(yīng)后，按照相應(yīng)的順序答復(fù)發(fā)起訪問的處理器.同一個(gè)處理器的操作，在核間互連中可以亂序執(zhí)行，但需要按照請(qǐng)求單元記錄的順序按序應(yīng)答；對(duì)于不同處理器的操作，如果沒有地址依賴關(guān)系，可以亂序執(zhí)行、亂序應(yīng)答，極大地提高了性能.

5.3 處理器Tag和Snoop Tag

單核處理器Tag 一般由Tag RAM 和Dirty RAM 組 成.Tag RAM 中 保 存 相 應(yīng) 索 引 字 段（index）的有效狀態(tài)位（V）和標(biāo)志字段（tag），Dirty RAM 用來保存臟狀態(tài)位（D）.對(duì)于寫干涉協(xié)議，只需在Tag RAM 中擴(kuò)充一個(gè)Exclusive（E）狀態(tài)位，即可表示協(xié)議的5種狀態(tài).但是這里臟狀態(tài)位的意義發(fā)生了改變，它不僅代表緩存中的數(shù)據(jù)和存儲(chǔ)器中不一致，還代表更新共享存儲(chǔ)器的責(zé)任，即擁有修改者標(biāo)記.

在一致性處理單元中，利用Snoop Tag 來減少對(duì)其他處理器的不必要的干擾.Snoop Tag 可以看作是對(duì)每個(gè)處理器內(nèi)部Tag 的拷貝，但由于Snoop Tag 只用來查詢各處理器中是否存在被訪問的緩存行，所以只需要一個(gè)有效狀態(tài)位（V）即可，如表1所示.

如圖5所示，Snoop Tag有3個(gè)訪問源：查詢請(qǐng)求、更新請(qǐng)求和維護(hù)請(qǐng)求（處理器的緩存清空或緩存同步操作）.為確保功能正確，把維護(hù)請(qǐng)求的優(yōu)先級(jí)設(shè)為最高.為了提高性能，避免一致性訪問的堵塞，設(shè)置查詢的優(yōu)先級(jí)高于更新的優(yōu)先級(jí).如果出現(xiàn)查詢與更新的競(jìng)爭(zhēng)，更新請(qǐng)求將在一致性命令緩沖區(qū)等待，并且被視為Snoop Tag中的內(nèi)容，會(huì)被隨后的一致性訪問所查詢.然而，一致性命令緩沖區(qū)的大小終歸有限，如果被填滿仍會(huì)阻塞一致性訪問.為了進(jìn)一步提高性能，按照索引字段的低2位模4運(yùn)算的結(jié)果把每個(gè)處理器的Snoop Tag 分為4 個(gè)塊（bank），不同的塊可以被同時(shí)訪問，從而降低了查詢請(qǐng)求與更新請(qǐng)求沖突的概率.至于處理器Tag，由于對(duì)Tag的訪問處于時(shí)序的關(guān)鍵路徑，所以不能進(jìn)行分塊.

表1 處理器Tag和Snoop Tag各狀態(tài)位與寫干涉協(xié)議各狀態(tài)的對(duì)應(yīng)關(guān)系Tab.1 Corresponding relation between the states of processor Tag and Snoop Tag and the states of write intervention protocol

5.4 處理器設(shè)計(jì)

處理器部分的設(shè)計(jì)是基于CK610單核的擴(kuò)展.如圖6所示，新增了一致性命令接口、緩存間數(shù)據(jù)拷貝接口、緩存仲裁邏輯、一致性判斷邏輯、請(qǐng)求接口和應(yīng)答接口.

圖6 處理器部分的架構(gòu)Fig.6 Architecture of processor

利用可反轉(zhuǎn)固定優(yōu)先級(jí)的緩存仲裁邏輯來選擇請(qǐng)求緩存操作的源.為了減少處理器的阻塞，提高性能，定義處理器讀請(qǐng)求的優(yōu)先級(jí)最高，其中，Tag查詢請(qǐng)求也是讀請(qǐng)求的一種.但是，如果處理器一直發(fā)起讀請(qǐng)求，將會(huì)堵塞一致性命令，造成整個(gè)系統(tǒng)的堵塞.因此，設(shè)計(jì)規(guī)定：如果N 個(gè)處理器時(shí)鐘周期后一致性命令還沒有搶到緩存資源，處理器讀請(qǐng)求和一致性命令的優(yōu)先級(jí)將臨時(shí)反轉(zhuǎn)一次.由于核間互連保證了能夠發(fā)往處理器的一致性命令的順序一定是先于處理器未完成的一致性請(qǐng)求的順序，所以定義處理器對(duì)緩存寫請(qǐng)求的優(yōu)先級(jí)為最低.

一致性命令接口用來把接收到的一致性命令譯碼成相應(yīng)的對(duì)各個(gè)RAM 的操作，如表2所示，根據(jù)寫干涉協(xié)議，定義了4種一致性命令，這里以“讀數(shù)據(jù)命令”為例簡(jiǎn)要說明.當(dāng)某個(gè)處理器發(fā)起讀缺失請(qǐng)求時(shí)，核間互連向擁有所有者標(biāo)記的處理器發(fā)送讀數(shù)據(jù)命令，把處理器Tag RAM 相應(yīng)index的E 位寫為0，Dirty RAM 的D 位寫為0，同時(shí)讀取Data RAM 中的數(shù)據(jù).這里利用了SRAM 的特性，把Dirty RAM 的數(shù)據(jù)輸入端置0的同時(shí)，在數(shù)據(jù)輸出端同時(shí)讀出之前的D 狀態(tài)位，和數(shù)據(jù)一起通過緩存間數(shù)據(jù)拷貝接口答復(fù)給核間互連，完成了修改者標(biāo)記的轉(zhuǎn)移.

表2 一致性命令與對(duì)處理器緩存操作的對(duì)應(yīng)關(guān)系Tab.2 Relation between coherence commands and operations on processor cache

一致性判斷邏輯會(huì)根據(jù)一致性協(xié)議、緩存命中判斷的結(jié)果和地址區(qū)間的屬性來判斷發(fā)起的請(qǐng)求是否為一致性請(qǐng)求，然后通過請(qǐng)求接口把信息發(fā)給核間互連.核間互連通過一致性處理后，通過應(yīng)答接口發(fā)送應(yīng)答、讀數(shù)據(jù)、協(xié)議狀態(tài)位、臟狀態(tài)位等給處理器，完成整個(gè)操作.

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

圖7 實(shí)驗(yàn)所用的系統(tǒng)環(huán)境Fig.7 Experiment environment

在實(shí)驗(yàn)中，CK610MP 被集成到一個(gè)小型系統(tǒng)中，如圖7 所示，該系統(tǒng)還包括AXI總線、APB 總線、中 斷 控 制 器（INTC）、定 時(shí) 器（TIM）、看 門 狗（WDT）、存儲(chǔ)器控制器（MMC）及共享存儲(chǔ)器（SDR）.其中，各處理器一級(jí)數(shù)據(jù)／指令緩存大小為16KB，每個(gè)緩存行大小為4個(gè)字，采用SMIC65nmLL工藝的單端口SRAM；處理器時(shí)鐘頻率為480 MHz，AXI和SDR 時(shí)鐘頻率為120 MHz；SDR 選取的型號(hào) 為美光半導(dǎo)體（Micron）的MT48LC32M16A2［13］，大小為128 MB.選取EEMBC Multi-bench［14］中有代表性的md5、rgbcmy和rotate程序進(jìn)行性能測(cè)試和功耗評(píng)估.這3 個(gè)程序各有特點(diǎn)，md5 程序計(jì)算多數(shù)據(jù)流的MD5校驗(yàn)和，數(shù)據(jù)并行度較高，通信相對(duì)較少；rgbcmy程序把RGB 色彩模式的圖像轉(zhuǎn)換成CMYK 印刷色彩模式的圖像，通信計(jì)算比高于md5；rotate程序處理一系列二進(jìn)制圖像，將其旋轉(zhuǎn)90°、180°和270°，計(jì)算量很少，由于輸入和輸出的數(shù)據(jù)流地址相關(guān)性較低，會(huì)產(chǎn)生較多的寫缺失，對(duì)共享存儲(chǔ)器帶寬帶來壓力.在服務(wù)器中進(jìn)行ASIC仿真，通過統(tǒng)計(jì)程序運(yùn)行時(shí)間以及對(duì)SDR 的訪問次數(shù)來評(píng) 估 性 能；通 過Synopsys Prime Power 統(tǒng) 計(jì)CK610MP、AXI、MMC 和SDR 部分的動(dòng)態(tài)功耗來評(píng)估功耗.其中，對(duì)共享存儲(chǔ)器訪問的統(tǒng)計(jì)是通過硬件性能計(jì)數(shù)器實(shí)現(xiàn)的.

實(shí)驗(yàn)中，用寫無效協(xié)議中性能最好的MOESI協(xié)議作為參考和寫干涉協(xié)議進(jìn)行對(duì)比，分別比較2、4、6和8核配置下對(duì)相同任務(wù)的運(yùn)行情況.為便于進(jìn)行橫向?qū)Ρ?，CK610MP實(shí)現(xiàn)了2個(gè)版本：支持緩存間數(shù)據(jù)拷貝的MOESI協(xié)議版本和寫干涉協(xié)議版本.

6.1 共享存儲(chǔ)器訪問次數(shù)測(cè)試結(jié)果及分析

如圖8所示，在各種處理器核數(shù)N 配置下，寫干涉協(xié)議（WI）對(duì)共享存儲(chǔ)器的訪問次數(shù)M 比MOESI協(xié)議對(duì)共享存儲(chǔ)器的訪問次數(shù)都有顯著減少，其中，通信相對(duì)較少的md5 程序平均減少了6%；通信相對(duì)較多的rgbcmyk 程序平局減少了11%；寫缺失較多的rotate程序平均減少了27%.

圖8 共享存儲(chǔ)器訪問次數(shù)統(tǒng)計(jì)Fig.8 Statistics of shared memory access

圖9 歸一化的共享存儲(chǔ)器訪問次數(shù)統(tǒng)計(jì)Fig.9 Normalized statistics of shared memory access

如圖9所示 顯示了寫干涉協(xié)議對(duì)共享存儲(chǔ)器訪問次數(shù)（Mwi）占MOESI協(xié)議對(duì)共享存儲(chǔ)器訪問次數(shù)（Mmoesi）的百分比隨處理器核數(shù)變化的情況.進(jìn)一步發(fā)現(xiàn)，隨著處理器核數(shù)的增多，核間通信隨之增加，寫干涉協(xié)議減少共享存儲(chǔ)器訪問次數(shù)的優(yōu)勢(shì)變得更明顯.

6.2 性能測(cè)試結(jié)果及分析

如圖10所示，寫干涉協(xié)議減少了程序執(zhí)行時(shí)間T，對(duì)性能有所提升，其中，md5程序平均減少了1%；rgbcmyk程序平均減少了2%，rotate程序平均減少了3%.從以上統(tǒng)計(jì)可以看出，寫干涉協(xié)議可以減少共享存儲(chǔ)器的訪問次數(shù)，提升系統(tǒng)的性能，而且在處理器核數(shù)固定的情況下，隨著核間通信比例的增加、寫缺失比例的增加，這些提升變得更明顯.

如圖11所示顯示了寫干涉協(xié)議的程序執(zhí)行時(shí)間（Twi）占MOESI協(xié)議的程序執(zhí)行時(shí)間（Tmoesi）的百分比隨處理器核數(shù)變化的情況.隨著處理器核數(shù)的增多，核間通信及寫缺失將增多.因此，在2、4、6核的配置下，寫干涉協(xié)議對(duì)性能的提升逐漸變得明顯.但是，隨著處理器核數(shù)的增多，寫干涉操作的時(shí)間、空間局部性將變差，被寫干涉的緩存行極有可能被迅速替換掉，導(dǎo)致在8核配置下，寫缺失比例少于rotate的md5 和rgbcmyk 程序?qū)π阅艿奶嵘潭扔兴档?

圖10 執(zhí)行時(shí)間統(tǒng)計(jì)Fig.10 Statistics of execution time

圖11 歸一化執(zhí)行時(shí)間統(tǒng)計(jì)Fig.11 Normalized statistics of execution time

6.3 功耗測(cè)試結(jié)果及分析

CMOS電路中的功耗由2部分功耗組成，一部分是漏電流引起的靜態(tài)功耗，另一部分是由信號(hào)翻轉(zhuǎn)造成的動(dòng)態(tài)功耗.這里討論的功耗均為動(dòng)態(tài)功耗.把整個(gè)系統(tǒng)的功耗分為3個(gè)部分：

式中：ECORES為處理器內(nèi)核的功耗，EIC為核間互連的功耗，EOUT為AXI、MMC和SDR 部分的功耗.顯然CK610MP部分的功耗為ECORES＋EIC.根據(jù)第4 章分析可知，對(duì)比MOESI協(xié)議，寫干涉協(xié)議大幅減少了對(duì)共享存儲(chǔ)器的訪問，因此降低了EOUT；增加了緩存命中率，因此降低了EIC；增加了緩存間的數(shù)據(jù)拷貝，將增加ECORES.而從如圖12顯示的實(shí)驗(yàn)結(jié)果來看，寫干涉協(xié)議對(duì)EOUT的降低更為明顯，因此總體的功耗（P）還是大幅下降的.其中，md5程序平均下降了3%；rgbcmyk程序平均下降了10%，rotate程序平均下降了13%.

如圖13 所示顯示了寫干涉協(xié)議的總體功耗（Pwi）占MOESI協(xié)議的總體功能（Pmoesi）的百分比隨處理器核數(shù)變化的情況.隨著處理器核數(shù)的增多，數(shù)據(jù)部分的緩存間共享將增多，而指令部分無法進(jìn)行緩存共享，導(dǎo)致處理器指令部分的功耗所占的比例將越來越大，是一致性協(xié)議無法解決的，因此ECORES占系統(tǒng)功耗的比例將越來越大，寫干涉協(xié)議對(duì)功耗節(jié)省的優(yōu)勢(shì)將趨近飽和.

圖12 動(dòng)態(tài)功耗統(tǒng)計(jì)Fig.12 Statistics of dynamic power dissipation

圖13 歸一化動(dòng)態(tài)功耗統(tǒng)計(jì)Fig.13 Normalized statistics of dynamic power dissipation

7 結(jié) 語

本文提出了一種基于寫干涉的高速緩存一致性協(xié)議，用于采用寫回、非寫分配緩存的多核處理器系統(tǒng)，并在32位嵌入式多核處理器設(shè)計(jì)中加以實(shí)現(xiàn).實(shí)驗(yàn)結(jié)果表明，和MOESI協(xié)議相比，寫干涉協(xié)議減少了共享存儲(chǔ)器的訪問量，提升了系統(tǒng)的性能，同時(shí)也降低了動(dòng)態(tài)功耗.

利用仿真的方法進(jìn)行性能和功耗的評(píng)估，雖然結(jié)果精確，但速度很慢.今后，將對(duì)寫干涉協(xié)議在更高的抽象層次進(jìn)行快速評(píng)估，并將進(jìn)一步考慮不同緩存大小和不同處理器體系結(jié)構(gòu)等對(duì)協(xié)議的影響.

（

）：

［1］ZHOU X，YU C，DASH A，et al.Application-aware snoop filtering for low-power cache coherence in embedded multiprocessors［J］.ACM Transactions on Design Automation of Electronic Systems（TODAES），2008，13（1）：16：1-16：25.

［2］CRAWFORD S E，DEMARA R F.Cache coherence in a multiport memory environment［C］∥Proceedings of the First International Conference on Massively Parallel Computing Systems.Ischia：IEEE，1994：632-642.

［3］STENSTROM P.A survey of cache coherence schemes for multiprocessors ［J］.Computer，1990，23（6）：12-24.

［4］HENNESSY J L，PATTERSON D A.Computer architecture：aquantitative approach，F(xiàn)ourth Edition ［M］.Amsterdam：Elsevier，2007：208-284.

［5］LEVERICH J，ARAKIDA H，SOLOMATNIKOV A，et al.Comparing memory systems for chip multiprocessors［J］.ACM SIGARCH Computer Architecture News，2007，35（2）：358-368.

［6］JANG Y J，RO W W.Evaluation of cache coherence protocols on multi-core systems with linear workloads［C］∥ISECS International Colloquium on Computing，Communication， Control，and Managemen. Sanya：IEEE，2009：342-345.

［7］YI K，RO W，GAUDIOT J.Importance of coherence protocols with network applications on multi-Core processors［J］.IEEE Transactions on Computers，2013，62（1）：6-15.

［8］LI J M，LIU W J，JIAO P.A new kind of cache coherence protocol with sc-cache for multiprocessor［C］∥2010 2nd International Workshop on Intelligent Systems and Applications（ISA）.Wuhan：IEEE，2010：1-5.

［9］KAXIRAS S，ROS A.Efficient，snoopless，system-onchip coherence［C］∥SOC Conference（SOCC）.Niagara Falls，NY：IEEE，2012：230-235.

［10］HACKENBERG D，MOLKA D，NAGEL W E.Comparing cache architectures and coherency protocols on x86-64 multicore SMP systems［C］∥Proceedings of the 42Nd Annual IEEE／ACM International Symposium on microarchitecture. New York： IEEE， 2009：413-422.

［11］PONG F，DUBOIS M.Formal automatic verification of cache coherence in multiprocessors with relaxed memory models［J］.IEEE Transactions on Parallel and Distributed Systems，2000，11（9）：989-1006.

［12］C-SKY Microsystems Co.，Ltd.CK600Introduction［EB／OL］.［2014-01-11］.http：∥www.c-sky.com／downdisp.php？aid＝72

［13］Micron Technology，Inc.MT48LC32M16A2datasheet［EB／OL］.［2014-01-11］.http：∥www.micron.com／～／media／Documents／Products／Data%20Sheet／DRAM／512Mb＿sdr.pdf

［14］Embedded Microprocessor Benchmark Consortium.MultiBenchTM1.0 Benchmark Software ［EB／OL］.［2014-01-11］.http：∥www.eembc.org／benchmark／multi＿sl.php