片上多處理器共享Cache的訪存時間最優(yōu)劃分方法

李浩，謝倫國

（國防科技大學 計算機學院，湖南 長沙 410073）

1 引言

為了保持處理器性能的持續(xù)增長，多核（multicore）處理器或片上多處理器（CMP, chip multiprocessor）已成為現(xiàn)代處理器發(fā)展的主流。片上處理器核數(shù)目的不斷增加，以及芯片管腳數(shù)目的有限使得處理器核片外訪存開銷越來越大，這給本來已經(jīng)很嚴重的存儲墻問題帶來了更大的挑戰(zhàn)。人們不得不在芯片上放置更多層次更大容量的片上存儲系統(tǒng)，以減少處理器對片外存儲器的訪問需求。片上存儲系統(tǒng)性能的好壞已經(jīng)成為決定 CMP系統(tǒng)性能的關鍵因素。為了提高片上存儲系統(tǒng)的性能，很多設計都采用大容量的末級共享 Cache。本文的研究目標旨在有效管理CMP末級共享Cache，優(yōu)化CMP上運行多個應用程序時的整體性能。

當運行在 CMP上的多個應用程序競爭同一個共享Cache空間時，傳統(tǒng)的LRU替換策略會顯式的按照請求的頻率給那些請求頻率高的應用分配更多的Cache空間。但是，給一個請求頻率高的應用分配更多的Cache空間不一定就能給它帶來相應的性能提升。例如，當一個流應用的工作集大于Cache總容積時，由于它訪問過的Cache塊重用性較低，即使給它分配更多的Cache空間，也無法給性能帶來多大的提升。為了提高多程序整體的訪存性能，本文希望能夠把Cache空間分配給那些能通過得到更多Cache空間獲得較大性能提升的應用，以提高多個競爭程序總的執(zhí)行性能。

目前大部分Cache劃分方法，無論是靜態(tài)最優(yōu)劃分方法[1]，還是動態(tài)劃分(DP, dynamic partitioning)[2]方法，還是基于利用率的 Cache劃分（UCP,utility-based Cache partitioning）[3]方法，都是以降低多個程序總的Cache失效率為優(yōu)化目標。在很多情況下，減少Cache失效次數(shù)確實能夠帶來性能的提升，但是在某些情況下，失效次數(shù)的減少并不意味著程序執(zhí)行性能的提升[4]，這是因為：1）應用程序的訪存特性導致它們對Cache失效的敏感度各不相同，相對而言，計算密集型應用對Cache失效的敏感度比訪存密集型應用要小很多；2）非阻塞Cache[5]、亂序執(zhí)行、以及提前執(zhí)行[6]等技術的出現(xiàn)，使得有些 Cache失效引發(fā)的片外訪存能夠重疊執(zhí)行，稱之為存儲級并行（MLP, memory level parallelism）[7]，這種存儲級并行對程序執(zhí)行時間的影響是不同的。由于每個Cache失效帶來的實際性能開銷各不相同，因此不同應用程序之間，Cache失效率的高低變化并不能直接反映程序執(zhí)行性能的高低變化，劃分后總的 Cache失效率最優(yōu)并不能代表總的程序執(zhí)行時間最少。以往的大多數(shù)Cache劃分方法都沒有考慮MLP問題，Zhou等人[8]提出了一種考慮了MLP問題的Cache劃分算法，但是他們主要針對的是Cache的公平性。本文提出一種訪存時間最優(yōu)的Cache劃分(OMTP, optimal memory time Cache partitioning)方法，通過獨立的硬件獲取每個劃分區(qū)間內(nèi)每個應用程序在占用不同大小的Cache空間時失效率的變化情況以及這些失效帶來的平均訪存時間，將兩者用于指導Cache劃分算法的執(zhí)行，使多個競爭程序總的執(zhí)行時間最少。模擬實驗結果表明，OMTP相比UCP吞吐率平均提高了3.1%，加權加速比平均提高了1.3%，取得了較好的性能提升。

2 訪存時間最優(yōu)Cache劃分

目前許多多處理器系統(tǒng)都采用共享 L2 Cache來減少片外訪存，當有多個應用程序同時運行在這樣一個系統(tǒng)上時，有可能會出現(xiàn)某些應用程序占用很多Cache空間卻無法得到相應的性能提升，而某些只需要再獲得很少Cache空間就能大幅提升性能的應用程序則不能獲得所需 Cache空間的情形。Cache劃分（partitioning）的目的就是給每一個應用程序分配適當?shù)腖2 Cache空間，以提高多個應用程序總的執(zhí)行性能。

假設有N個應用程序共享同一個Cache空間，Ci代表分配給應用程序i的Cache塊數(shù)，C為總的Cache塊數(shù)，則Cache劃分可以用集合來定義。Suh等人[2]提出的最優(yōu) Cache劃分是使總失效次數(shù)（ )(iiCM代表應用程序i在占用iC個Cache塊位置時的失效次數(shù)）最小的劃分。把這種最優(yōu)劃分稱作失效率最優(yōu)劃分。在以往的一些研究中，無論是動態(tài)劃分(DP, dynamic partitioning)[1]方法，還是基于利用率的Cache劃分（UCP）[2]方法，都是追求失效率最優(yōu)的劃分方法。

但是，由于每個Cache失效所造成的開銷不同，并且各個應用程序內(nèi)在的訪存特征也各不相同，使得失效率的多少并不能代表 Cache實際性能的高低，失效率最優(yōu)并不能代表訪存時間最優(yōu)。真正的性能最優(yōu)劃分應該是多個應用程序總的執(zhí)行時間表示應用程序i占用iC個Cache塊位置時的執(zhí)行時間）最小的集合

應用程序的執(zhí)行時間可以用式(1)計算[7]：

式中TCPU代表 CPU運算時間，它表明了執(zhí)行應用程序所有操作必須花費的時間（這個時間包括L2 Cache命中延遲），不會隨著存儲系統(tǒng)性能的好壞而改變，在本文的研究中，它是一個常量。TMem_stall代表存儲系統(tǒng)停頓時間，因為本文研究的對象是L2 Cache，因此這個存儲系統(tǒng)停頓時間指的是L2失效導致的系統(tǒng)停頓時間（不包括 L2命中延遲造成的系統(tǒng)停頓時間重疊）。使多個應用程序總的存儲停頓時間最小的集合｛C1,C2,… ,CN｝就是訪存時間最優(yōu)Cache劃分。

式中NMisses代表應用程序失效次數(shù)，Caverage代表每個失效的平均失效開銷。因此，只要能夠知道每個應用程序的失效次數(shù)和對應的每個失效的平均失效開銷，就可以預測出總的存儲停頓時間。

因為對組相聯(lián)Cache中的每一個Cache塊進行劃分硬件開銷太大，本文只對組相聯(lián) Cache的路（way）進行劃分。

3 劃分算法與實現(xiàn)

3.1 平均失效開銷計算

根據(jù)式(2)，每個應用程序的平均失效開銷可以根據(jù)該應用程序在劃分區(qū)間內(nèi)總的存儲停頓時間和總的失效次數(shù)來計算。

通過監(jiān)測每個處理器核流水線的狀態(tài)，可以統(tǒng)計出處理器核上運行應用程序的流水線停頓周期數(shù)，但是流水線停頓周期數(shù)里包含了與L2命中延遲所造成的停頓時間重疊的部分，從所有的停頓周期數(shù)中減去這一重疊部分就可以得到由L2 Cache失效引起的總停頓周期數(shù)。為了判斷一段時間是否屬于重疊時間，給每一個L1指令和數(shù)據(jù)Cache都增加一個計時器，當發(fā)生一次L1Cache失效，向L2發(fā)送一次請求時，該計時器被賦予一個值L2_Latency，L2_Latency的大小為L2 Cache的命中延遲（一般是一個固定值），每過一個時鐘周期，計時器減1。當計時器時間大于0時，說明這段時間還屬于與L2命中延遲時間重疊的部分，不能記入總的存儲停頓時間。

每個劃分區(qū)間內(nèi)各處理器核在 L2 Cache上的失效次數(shù)通過監(jiān)測L2失效狀態(tài)保持寄存器（MSHR,miss status holding register）的狀態(tài)獲得，為了判斷MSHR中的失效屬于哪個處理器核，在MSHR的每一項中添加lbN位用于標識該失效屬于哪個處理器核。平均失效開銷計算的算法如算法1所示。

算法1 計算平均失效開銷Caverage

3.2 Cache失效率預測

為了能夠知道應用程序在占用不同數(shù)目 Cache路時的失效率變化情況，給每個處理器核增加一個額外tag目錄（ATD, auxiliary tag directory）[3]，就像給每個處理器核分配了一個虛擬的私有 L2 Cache。ATD跟目標 L2 Cache（待劃分的共享 L2 Cache）組相聯(lián)結構相同，采用LRU替換策略。每個ATD僅僅包含目錄項，不包含數(shù)據(jù)塊。當L1發(fā)生失效時，請求會同時發(fā)向實體L2 Cache和對應處理器核的ATD。ATD和真正的私有L2 Cache一樣運轉，但它不會返回數(shù)據(jù)，而是用來統(tǒng)計處理器在不同路上的命中信息。由于基本的 LRU替換策略遵循一種堆棧機制，即如果一個數(shù)據(jù)在Cache路數(shù)為N時命中，那么它在Cache路數(shù)大于N時也必然命中，因此根據(jù)應用程序在不同Cache路上的命中次數(shù)分布情況，可以得到應用程序占用Cache路數(shù)目發(fā)生變化時失效率的變化情況。

因為每一個處理器核都要有一個對應的ATD，每個ATD的大小都跟真正的共享L2Cache目錄一樣大，當處理器核數(shù)目增加時，ATD的硬件開銷將會變得不可接受。采用組抽樣技術[3]來減少硬件開銷。ATD以某一個固定間隔選取組（這個策略叫做簡單靜態(tài)策略[4]）來進行統(tǒng)計，最后得到的數(shù)據(jù)近似全局的統(tǒng)計數(shù)據(jù)。Qureshi[3]認為，總共選取 32組作為抽樣進行統(tǒng)計可以很好地近似全局統(tǒng)計數(shù)據(jù)。

3.3 OMTP劃分算法

每個劃分區(qū)間結束時，通過監(jiān)測每一個競爭程序在ATD中各路的命中情況以及計算出來的Caverage，選擇使總訪存時間最少的劃分策略。假設ma和mb分別代表一個應用占用a路Cache和b路Cache時的失效率（a＜b），則該應用程序占用的Cache路數(shù)從a增加到b時所節(jié)省的訪存時間Uab可以如下定義：

假設2個應用程序A和B共用一個 16路的Cache。A和B分別代表2個應用程序節(jié)省的訪存時間，則應用A和B總共節(jié)省的訪存時間Utot可以如下計算：

使2個程序總共節(jié)省的訪存時間值最大的劃分（i,16-i）就是訪存時間最優(yōu)的劃分。

劃分算法的目的是從所有的劃分組合中尋找一個使總的訪存時間最優(yōu)的一種劃分。當應用程序只有2個時，N路Cache的劃分組合只有N+1種。但是當應用程序數(shù)量增加時，劃分組合的數(shù)量會呈指數(shù)值增長，這樣要找出所有組合中訪存時間最優(yōu)的劃分不太現(xiàn)實。例如當有4個應用程序共享一個32路組相連Cache時，劃分組合有6 545種，當應用程序數(shù)目增加到 8個時，劃分組合猛增至15 380 937種。這個尋找最優(yōu)劃分的問題已經(jīng)被證明是一個 NP難（NP-hard）問題[9]。采用 Qureshi等人提出的超前（lookahead）算法[3]來尋找符合條件的劃分，算法偽碼如算法2所示。

算法2 超前算法

U= 當分配的塊從a增加到b時，應用p所節(jié)省的訪存時間

在該算法中，muT代表應用程序在分配的塊數(shù)從a增加到b時的平均每一路節(jié)省的訪存時間，它的定義如下：

超前算法的時間復雜度為O(N2)，對于一個32路組相聯(lián)Cache，采用超前算法只需要512次操作，相對于500萬時鐘周期的劃分區(qū)間來說幾乎可以忽略不計。在本文的研究中，每一個應用都至少要分配1路，并且在每個劃分區(qū)間結束開始一個新的劃分區(qū)間時，將 ATD中所有命中計數(shù)器的值減半，使得ATD得到的命中信息具有局部時間相關特征。

3.4 OMTP方法硬件實現(xiàn)

OMTP方法的硬件結構如圖1所示，每個處理器核都擁有各自的L1指令和數(shù)據(jù)Cache，每個處理器核對應一個Profiler模塊，該模塊的作用主要有2個：1）獲取每一個應用程序的平均MLP失效開銷；2）獲取每個應用程序在占用不同大小 Cache路數(shù)時的失效率變化情況。Profiler模塊獲得信息提供給劃分算法硬件單元。劃分算法硬件單元負責每一個劃分時間區(qū)間內(nèi)劃分算法的實現(xiàn)。

圖1 Cache劃分機制硬件結構

對LRU算法（或者是偽LRU算法）進行擴展。給共享L2Cache中每一個Cache塊的tag中增加lbN（N為處理器核數(shù)目）位用于標識該塊被哪個處理器核占用。每個劃分區(qū)間結束時，通過3.3節(jié)的算法，可以得到每個處理器核所分配的最高占用Cache塊數(shù)值A(i)，用于指導下一個劃分區(qū)間內(nèi)的替換策略。在每一個劃分區(qū)間內(nèi)，當一個Cache失效，替換引擎統(tǒng)計引發(fā)該失效的應用程序i在Cache中占用的路數(shù)，如果不超過A(i)值，則在本應用占用的Cache塊之外選擇一個LRU塊驅逐，如果達到或者是超過了A(i)值，則在本應用占用的 Cache塊中選擇一個LRU塊驅逐。每執(zhí)行5M指令運行一次劃分算法，進行重新劃分。

4 測試與分析

使用全系統(tǒng)模擬器，從吞吐率、失效率以及加速比3個方面評估LRU替換機制、UCP方法以及本文提出的OMTP方法的性能。

4.1 測試平臺

GEMS模擬器[10]是威斯康辛大學在 Virtutech公司開發(fā)的通用并行模擬器simics[11]的基礎上擴展實現(xiàn)的。simics是一個全系統(tǒng)虛擬機，可以進行功能模擬和時序模擬，它支持 3種模擬模式：1）正常模式；2）微體系結構模式；3）暫停(stall)模式。GEMS模擬器在暫停模式下增加了對Cache系統(tǒng)和互聯(lián)網(wǎng)絡的模擬。采用GEMS模擬器對OMTP劃分方法進行模擬測試。

本文模擬實驗平臺為一個雙核 CMP系統(tǒng)，每個處理器核為亂序執(zhí)行的超標量處理器，有自己的L1指令和數(shù)據(jù)Cache，2個處理器核共享一個統(tǒng)一編制的L2 Cache和主存。具體參數(shù)如下：

1) 處理器核：2個，4流出，亂序執(zhí)行指令窗口大小為64，保留站大小為128；

2) L1Cache：ICache DCache為32KB，數(shù)據(jù)塊大小為64，B4路組相聯(lián)；

3) 共享L2Cache：1MB，數(shù)據(jù)塊大小為64byte，16路組相聯(lián)，命中延遲為15個時鐘周期，MSHR大小為32；

4) 主存：400個時鐘周期。

4.2 度量指標

多道程序并行執(zhí)行時的度量指標有很多種，本文選取其中的3種：吞吐率、失效率以及加權加速比。設iI為應用程序i在并行執(zhí)行時的IPC，iS為應用程序i在單獨執(zhí)行（獨享L2 Cache）時的IPC，MRi為應用程序i在并行執(zhí)行時的L2 Cache失效率。則這3種度量指標定義如下：

這三者中，吞吐率反映了處理器單位時間里的處理能力，失效率反映了系統(tǒng)的整體性能，而加權加速比直接反映了執(zhí)行時間的變化。

4.3 測試程序

本文從SPEC CPU2000測試程序里面選擇了一些程序，并將它們兩兩組合起來，構成本文的基本測試用例（如表1所示），表1中第3、4列數(shù)據(jù)分別是2個應用程序獨享L2 Cache時Caverage平均值，第5列給出了2個競爭程序平均失效開銷差異。

表1 基本測試用例及它們的平均失效開銷特征

采用 simics提供的 magic指令控制程序的執(zhí)行，在每個程序完成初始化Cache的過程后，每個程序最少執(zhí)行250M條指令，每5M條指令為一個劃分區(qū)間。

4.4 實驗結果與分析

通過比較LRU替換機制、UCP劃分方法和OMTP劃分方法在吞吐率、失效率以及加權加速比3個性能度量指標上的變化來評估OMTP方法的性能。

4.4.1 吞吐率

圖2比較了LRU和2種劃分方法吞吐率的差異，標號1到標號12分別對應測試用例中的1到12組測試程序，標號13為所有測試用例吞吐率平均值。在第7、8、9組中，由于2個競爭應用程序的平均失效開銷相差很小，OMTP方法在 UCP方法基礎上性能提升不明顯。在第3組中，因為程序本身性能提升空間有限，UCP方法和OMTP方法均無明顯作用。在其他各組測試中，OMTP方法都取得比較好性能提升。跟 UCP方法相比，OMTP方法的吞吐率平均提高了3.1%。

4.4.2 失效率

圖3給出了LRU和UCP方法及OMTP方法在失效率上測試結果。標號1到標號12分別對應測試用例中的12組測試程序，標號13為所有12組測試程序的平均失效率。從圖3可以看出，OMTP方法的失效率比UCP方法要略高。

4.4.3 加權加速比

圖4給出了LRU和2種劃分方法在加權加速比上的差異。標號1到標號12分別對應測試用例中的12組測試程序，標號13為所有12組測試程序的平均加權加速比。在第7、8、9組中，因為同組2個應用程序的平均MLP失效開銷相差不大，因此OMTP方法和UCP方法性能幾乎一樣，而在其他各組中，OMTP方法的性能都要好于 UCP方法。跟 UCP方法相比，OMTP方法的加權加速比平均提高了 1.3%。加權加速比的對比充分說明了OMTP方法能夠提高程序的實際執(zhí)行性能。

4.5 硬件開銷

OMTP方法的硬件開銷主要集中在2個方面：

1）為了劃分算法的執(zhí)行，每個 Cache塊都要增加lbN（N為處理器核數(shù)目）位用于標識所屬處理器核；2）Profiler模塊所用硬件開銷。假設目標系統(tǒng)為雙核、共享1MB L2 Cache、16路組相聯(lián)、塊大小為64byte、L2 MSHR有32項的系統(tǒng)。則第一項開銷如下計算：

Profiler模塊中ATD的硬件開銷統(tǒng)計為：ATD目錄項（1有效比特+24bit tag+4bit LRU）為29bit，每一組ATD項數(shù)為16項，抽樣組數(shù)為32組，ATD目錄開銷（29bit×16路×32組）為1 856byte。Profiler模塊中還有計數(shù)器18個（16個用于統(tǒng)計命中信息，1個用于統(tǒng)計L2失效次數(shù)，1個用于統(tǒng)計存儲停頓周期數(shù)）、計時器 1個，所用硬件開銷合計1 856+4×19=1 932byte。

圖2 吞吐率測試結果

圖3 失效率測試結果

圖4 加權加速比測試結果

除了1）和2）中的開銷以外，L2_MSHR每一項中增加了1bit，共32bit（4byte）。因此實現(xiàn)OMTP方法額外硬件總開銷為2 000byte+1 932byte×2+ 4byte=5 868byte。不采用任何劃分方法的L2 Cache硬件開銷為 1MB+(24+4+1)×(1MB/64byte)=1 488KB。因此 OMTP硬件開銷在不采用任何劃分策略的原始硬件開銷上共增加了5.868KB/1 488KB0.4%≈。

5 結束語

當多個競爭應用程序共用一個共享Cache時，以往的Cache劃分算法都是以減少競爭程序總的失效率為第一目標。但是由于每個應用程序的 Cache失效開銷各不相同，減少總的Cache失效率并不一定能夠提高程序整體執(zhí)行性能，Cache失效率最優(yōu)并不能代表程序實際執(zhí)行時間最優(yōu)。本文提出一種訪存時間最優(yōu)的Cache劃分（OMTP）方法，該方法通過統(tǒng)計計算出每一個應用程序的 MLP失效開銷，通過ATD輔助硬件得到應用程序在各個Cache路上的命中分布情況，并將這2項用于指導劃分算法的執(zhí)行，優(yōu)化了多個競爭程序總的執(zhí)行時間。

模擬實驗結果表明，雖然OMTP方法的Cache失效率比 UCP方法略有增加，但是具有更高的吞吐率和加權加速比，降低了程序實際執(zhí)行時間。但是本文的實驗結果均來自一個雙核系統(tǒng)，當處理器核數(shù)目增加時，算法的可擴展性問題還有待進一步研究。

[1] STONE H S. Optimal partitioning of Cache memory[J]. IEEE Transactions on Computers, 1992, 41(9): 1054-1068.

[2] SUH G E, RUDOLPH L, DEVADAS S. Dynamic partitioning of shared Cache memory[J]. Journal of Supercomputing, 2004, 28(1):7-26.

[3] QURESHI M K, PATT Y N. Utility-based Cache partitioning: a low-overhead, high-performance, runtime mechanism to partition shared Caches[A]. MICRO-39[C]. 2006.423-432.

[4] QURESHI M K, LYNCH D N, MUTLU O,et al. A case for MLP-aware Cache replacement[A]. ISCA-33[C]. 2006. 167–178.

[5] KROFT D. Lockup-free instruction fetch/prefetch Cache organization[A]. Proceedings of the 8th Annual International Symposium on Computer Architecture[C]. 1981.81-88.

[6] MUTLU O, STARK J,WILKERSON C.et al. Runahead execution: an alternative to very large instruction windows for out-of-order processors[A]. Proceedings of the 9th International Symposium on High Performance Computer Architecture[C]. 2003.129-140.

[7] CHOU Y, FAHS B, ABRAHAM S G. Microarchitecture optimizations for exploiting memory-level parallelism[A]. ISCA[C]. 2004. 76-89.

[8] ZHOU X, CHEN W G, ZHENG W M. Cache sharing management for performance fairness in chip multiprocessors[A]. Proc 18th International Conference on Parallel Architectures and Compilation Techniques(PACT 2009)[C]. Raleigh, North Carolina, USA, 2009. 384-393.

[9] RAJKUMAR R. A resource allocation model for QoS management[A].The 18th IEEE Real-time Systems Symposium[C]. 1997.298-307.

[10] MARTIN M M K, SORIN D J, BECKMANN B M,et al.Multifacets general execution-driven multiprocessor simulator (gems) toolset[J].SIGARCH Comput Archit News, 2005,33(4):92-99.

[11] MAGNUSSON P S, CHRISTENSSON M, ESKILSON J,et al. Simics:a full system simulation platform[J]. Computer, 2002, 35(2):50-58.

[12] PATTERSON D A, HENNESSY J L. Computer Architechture: a Quantitative Approach[M]. San Francisco: Morgan Kaufmann Publish,1996.