李浩，謝倫國(guó)

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

1 引言

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

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

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

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

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

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

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

應(yīng)用程序的執(zhí)行時(shí)間可以用式(1)計(jì)算[7]：

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

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

因?yàn)閷?duì)組相聯(lián)Cache中的每一個(gè)Cache塊進(jìn)行劃分硬件開銷太大，本文只對(duì)組相聯(lián) Cache的路（way）進(jìn)行劃分。

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

3.1 平均失效開銷計(jì)算

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

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

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

算法1 計(jì)算平均失效開銷Caverage

3.2 Cache失效率預(yù)測(cè)

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

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

3.3 OMTP劃分算法

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

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

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

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

算法2 超前算法

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

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

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

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

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

圖1 Cache劃分機(jī)制硬件結(jié)構(gòu)

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

4 測(cè)試與分析

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

4.1 測(cè)試平臺(tái)

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

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

1) 處理器核：2個(gè)，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個(gè)時(shí)鐘周期，MSHR大小為32；

4) 主存：400個(gè)時(shí)鐘周期。

4.2 度量指標(biāo)

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

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

4.3 測(cè)試程序

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

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

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

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

通過比較LRU替換機(jī)制、UCP劃分方法和OMTP劃分方法在吞吐率、失效率以及加權(quán)加速比3個(gè)性能度量指標(biāo)上的變化來評(píng)估OMTP方法的性能。

4.4.1 吞吐率

圖2比較了LRU和2種劃分方法吞吐率的差異，標(biāo)號(hào)1到標(biāo)號(hào)12分別對(duì)應(yīng)測(cè)試用例中的1到12組測(cè)試程序，標(biāo)號(hào)13為所有測(cè)試用例吞吐率平均值。在第7、8、9組中，由于2個(gè)競(jìng)爭(zhēng)應(yīng)用程序的平均失效開銷相差很小，OMTP方法在 UCP方法基礎(chǔ)上性能提升不明顯。在第3組中，因?yàn)槌绦虮旧硇阅芴嵘臻g有限，UCP方法和OMTP方法均無明顯作用。在其他各組測(cè)試中，OMTP方法都取得比較好性能提升。跟 UCP方法相比，OMTP方法的吞吐率平均提高了3.1%。

4.4.2 失效率

圖3給出了LRU和UCP方法及OMTP方法在失效率上測(cè)試結(jié)果。標(biāo)號(hào)1到標(biāo)號(hào)12分別對(duì)應(yīng)測(cè)試用例中的12組測(cè)試程序，標(biāo)號(hào)13為所有12組測(cè)試程序的平均失效率。從圖3可以看出，OMTP方法的失效率比UCP方法要略高。

4.4.3 加權(quán)加速比

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

4.5 硬件開銷

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

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

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

圖2 吞吐率測(cè)試結(jié)果

圖3 失效率測(cè)試結(jié)果

圖4 加權(quán)加速比測(cè)試結(jié)果

除了1）和2）中的開銷以外，L2_MSHR每一項(xiàng)中增加了1bit，共32bit（4byte）。因此實(shí)現(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 結(jié)束語

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

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

[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.