婁冕， 肖建青， 張洵穎， 吳龍勝， 關(guān)剛強(qiáng)

(1.西安微電子技術(shù)研究所， 陜西，西安 710075；2.國(guó)防科技大學(xué) 電子科學(xué)與工程學(xué)院， 湖南，長(zhǎng)沙 410073)

?

一種面向包含式緩存的共享末級(jí)緩存管理策略

婁冕1， 肖建青1， 張洵穎1， 吳龍勝1， 關(guān)剛強(qiáng)2

(1.西安微電子技術(shù)研究所， 陜西，西安 710075；2.國(guó)防科技大學(xué) 電子科學(xué)與工程學(xué)院， 湖南，長(zhǎng)沙 410073)

針對(duì)傳統(tǒng)LRU替換策略無(wú)法感知包含式緩存時(shí)間局部性的問(wèn)題，提出一種適用于包含式緩存的共享末級(jí)緩存(SLLC)管理策略. 通過(guò)提前將無(wú)用數(shù)據(jù)存儲(chǔ)于一個(gè)開(kāi)銷較小的旁路緩存，可以避免其與復(fù)用頻率較高數(shù)據(jù)對(duì)SLLC的資源競(jìng)爭(zhēng)，同時(shí)維護(hù)了包含屬性. 為進(jìn)一步尋找復(fù)用性最低的數(shù)據(jù)作為替換對(duì)象，構(gòu)建一種局部性檢測(cè)電路，有助于將此類數(shù)據(jù)盡早驅(qū)逐出SLLC，文中提出一種統(tǒng)一的管理算法，受益于兩種預(yù)測(cè)器的相互校準(zhǔn)，從而達(dá)到無(wú)用塊旁路和低重用塊替換的目的. 實(shí)驗(yàn)結(jié)果表明，所提策略將SLLC缺失率平均降低21.67%，預(yù)測(cè)精度提升至72%，而硬件開(kāi)銷不到SLLC的1%.

包含式緩存；管理策略；共享末級(jí)緩存；多核

現(xiàn)今，航天及空間應(yīng)用領(lǐng)域明確提出未來(lái)片上多核處理器必須具備在輻照環(huán)境下較強(qiáng)的生存能力，而包含式(inclusive)共享末級(jí)緩存(shared last-level cache， SLLC)憑借其系統(tǒng)級(jí)的冗余特性以及對(duì)訪問(wèn)延遲的不敏感性[1]，可以與差錯(cuò)控制編碼自然結(jié)合，因而有效提高了多核處理器的可靠性.然而，包含式緩存存在強(qiáng)制維護(hù)緩存層次間包含屬性的局限性，以致緩存系統(tǒng)出現(xiàn)嚴(yán)重的抖動(dòng)現(xiàn)象[2]，使得原本在非包含體系下眾多行之有效的緩存優(yōu)化策略難以為繼.

分配策略和替換策略作為緩存設(shè)計(jì)優(yōu)化領(lǐng)域的兩大研究熱點(diǎn)，其目的在于識(shí)別無(wú)用的緩存數(shù)據(jù)以及替換局部性較低的緩存數(shù)據(jù).基于此，設(shè)計(jì)將著力解決旁路策略與包含式緩存的融合、替換策略對(duì)不同層次緩存數(shù)據(jù)局部性的預(yù)測(cè)、以及兩種策略的相互校準(zhǔn)與協(xié)同管理等問(wèn)題，以求通過(guò)較小的硬件開(kāi)銷獲得較高的性能提升.

1 動(dòng)機(jī)與背景

1.1 動(dòng) 機(jī)

多級(jí)緩存架構(gòu)類型分為包含式、非包含式(non-inclusive)和獨(dú)占式(exclusive)[3].相對(duì)于其它兩種結(jié)構(gòu)，包含式緩存并不具備容量?jī)?yōu)勢(shì)，但卻能夠簡(jiǎn)化緩存一致性設(shè)計(jì)并提供天然的錯(cuò)誤容忍性，因而廣泛用于CMP系統(tǒng)[4-5].然而，包含式緩存同樣存在性能瓶頸，其并非實(shí)際可用緩存容量的減少，而是由于SLLC的包含屬性對(duì)于高層緩存時(shí)間局部性的干擾，使得高層緩存命中率較高的數(shù)據(jù)塊反而成為SLLC的候選替換塊[6].

為尋求有效的包含式緩存管理策略，本文將SLLC中數(shù)據(jù)塊分為3類：① TLH-H塊：在一級(jí)緩存中具有較高時(shí)間局部性特征的塊；② TLH-L塊：在SLLC中具有較高時(shí)間局部性特征的塊；③ TLH-N塊：在兩級(jí)緩存中均具有較低時(shí)間局部性特征的塊.

圖1是本文實(shí)驗(yàn)所用測(cè)試負(fù)載在LRU管理的包含式SLLC中，不同類別數(shù)據(jù)塊的分布情況.可以看出，大約75.03%和14.12%的數(shù)據(jù)塊是兩類具有較好局部性特征的TLH-H和TLH-L塊，剩余11.58%的塊直至在一級(jí)緩存中替換也未被再次訪問(wèn)，這類塊即為T(mén)LH-N塊，成為本文重點(diǎn)優(yōu)化的對(duì)象.

1.2 相關(guān)工作

當(dāng)前，圍繞包含式SLLC性能優(yōu)化的工作集中在分配策略和替換策略設(shè)計(jì)實(shí)現(xiàn)上.分配策略中最具代表性的是旁路算法[7]，它可以將使用頻率較低的數(shù)據(jù)直接旁路到上級(jí)緩存，從而減少與SLLC有用數(shù)據(jù)的競(jìng)爭(zhēng).然而，這類算法要求缺失數(shù)據(jù)不能分配到SLLC中，因此并不適用于包含式緩存.適用于包含式緩存的旁路算法BBA是在最近的文獻(xiàn)[8]中提出，然而它僅能與LRU替換策略配合使用，使得SLLC無(wú)法通過(guò)正確感知高層緩存的局部性而減少SLLC的抖動(dòng).

替換策略目的是替換復(fù)用性最低的數(shù)據(jù)塊.文獻(xiàn)[9]中提出一種基于二叉樹(shù)的偽LRU替換策略，它通過(guò)窮舉算法搜索整個(gè)矢量空間，從而確定每路數(shù)據(jù)在葉子節(jié)點(diǎn)的替換順序；然而該算法需要預(yù)先對(duì)目標(biāo)程序集進(jìn)行行為感知，因而可操作性低.文獻(xiàn)[10]中通過(guò)在SLLC替換時(shí)預(yù)先失效一個(gè)上級(jí)緩存塊，并在時(shí)間窗內(nèi)判斷其是否活躍來(lái)感知時(shí)間局部性，然而該技術(shù)仍舊基于LRU優(yōu)先排序，無(wú)法擺脫上級(jí)緩存對(duì)局部性的過(guò)濾效應(yīng).Tian和Khan等[11]對(duì)每個(gè)SLLC請(qǐng)求數(shù)據(jù)的歷史局部性信息進(jìn)行統(tǒng)計(jì)，提出了能夠感知兩級(jí)緩存局部性特征的TMC算法，但它要求缺失塊插入SLLC，從而導(dǎo)致一個(gè)潛在的活躍數(shù)據(jù)塊被強(qiáng)制反向無(wú)效.

2 包含式SLLC管理策略

2.1 旁路策略

為了能夠在數(shù)據(jù)插入到SLLC之前確定缺失塊的使用頻率，本文提出了適用于包含式SLLC的旁路概率預(yù)測(cè)器BPP，如圖2所示.

BPP基于歷史數(shù)據(jù)生命周期的概率統(tǒng)計(jì)對(duì)SLLC缺失數(shù)據(jù)進(jìn)行預(yù)測(cè)，如果認(rèn)定其相對(duì)SLLC內(nèi)數(shù)據(jù)具有較低的重用性，則暫存于旁路緩存(bypass buffer，BB)中；否則替換插入SLLC.當(dāng)BB中的旁路數(shù)據(jù)被替換時(shí)，上級(jí)緩存的副本同時(shí)被無(wú)效，以維護(hù)包含性.為了有效追蹤并動(dòng)態(tài)調(diào)整旁路算法的精度，SLLC的每個(gè)Cache行均可映射至BB的一個(gè)表項(xiàng).該表項(xiàng)位域分為7段：valid表示該表項(xiàng)是否有效，virtual bypass表示該表項(xiàng)是否為虛擬旁路，competitor pointer指向原始替換塊位置，BB-tag存儲(chǔ)被旁路(或虛擬旁路)數(shù)據(jù)的tag信息，segment和inclusive分別指示該表項(xiàng)映射至SLLC的區(qū)域段號(hào)和該旁路塊的包含性.

當(dāng)一個(gè)數(shù)據(jù)被轉(zhuǎn)存至BB時(shí)，對(duì)應(yīng)的競(jìng)爭(zhēng)者指針將指向替換算法原本選擇的路號(hào). 之后若競(jìng)爭(zhēng)塊先于旁路塊被訪問(wèn)，意味著旁路塊為T(mén)LH-N塊，旁路有效且旁路概率增加，反之無(wú)效且旁路概率降低. 為了逆向評(píng)估旁路算法的有效性，一些新分配的塊被隨機(jī)地進(jìn)行虛擬旁路. 在這種情況下，旁路塊與競(jìng)爭(zhēng)塊進(jìn)行位置調(diào)換，同時(shí)置virtual bypass有效，而旁路概率的調(diào)整則與前者相反.

為了減少BB的硬件開(kāi)銷，BPP并不增加旁路塊的數(shù)據(jù)段，這是由于性能穩(wěn)定后的旁路算法能夠較準(zhǔn)確的預(yù)測(cè)壽命短的BB塊. 為進(jìn)一步減少開(kāi)銷，本文采用文獻(xiàn)[8]對(duì)典型負(fù)載的剖析結(jié)果，即set數(shù)為16的4路相聯(lián)結(jié)構(gòu)就能保證足夠的精度. 此外，為了直接判定SLLC命中塊是否在BB中被指向，所提算法增設(shè)了7位segment段，從而以set為單位將SLLC按照BB大小虛擬重映射為27個(gè)分區(qū). 這樣當(dāng)SLLC某一分區(qū)命中時(shí)，BB將在對(duì)應(yīng)行中搜索segment段匹配的旁路塊，若競(jìng)爭(zhēng)者指針的指向匹配，則證明旁路有效且旁路概率提升. 本方案還為BB表項(xiàng)增設(shè)inclusive位，目的是使得BB同樣具有簡(jiǎn)化一致性設(shè)計(jì)和容錯(cuò)的能力.

2.2 替換機(jī)制

旁路算法雖有較高的預(yù)測(cè)性能，仍無(wú)法過(guò)濾所有TLH-N塊.本文提出的包含式緩存替換策略能夠?qū)Σ迦氲臄?shù)據(jù)塊進(jìn)行二次識(shí)別，從而過(guò)濾出TLH-N塊作為候選替換者.

該策略第一步需要在SLLC層面分離出TLH-L塊. 根據(jù)文獻(xiàn)[12]中的觀察：基于已執(zhí)行程序的部分PC可以動(dòng)態(tài)預(yù)測(cè)所要發(fā)生的事件，且不同緩存分區(qū)所對(duì)應(yīng)的訪存行為大致相同. 這意味著，相同的PC可能對(duì)應(yīng)類別相同的數(shù)據(jù)塊. 因此，本文使用圖3所示的局部性檢測(cè)電路，主要包括預(yù)測(cè)表和采樣集兩部分結(jié)構(gòu). 預(yù)測(cè)表由一組飽和計(jì)數(shù)器陣列構(gòu)成，通過(guò)哈希后的PC索引計(jì)數(shù)值，以此在TLH-L和非TLH-L(即為T(mén)LH-H與TLH-N，簡(jiǎn)記為T(mén)LH-P)中確定訪問(wèn)塊的類型. 采樣集通過(guò)追蹤一小部分SLLC塊的使用情況來(lái)更新預(yù)測(cè)表，每個(gè)采樣塊內(nèi)容包括部分tag、部分PC以及塊類型. 若訪問(wèn)與采樣集中tag匹配，則使用采樣塊關(guān)聯(lián)PC以及程序PC分別檢索預(yù)測(cè)表，前者用以自減預(yù)測(cè)計(jì)數(shù)值，后者用于重新對(duì)采樣塊分類. 若采樣集缺失，需按照TLH-N、TLH-P、偽LRU的順序選擇替換塊，并同樣檢索兩次預(yù)測(cè)表，但需要自增計(jì)數(shù)值. 類似的，SLLC塊使用哈希后的程序PC檢索預(yù)測(cè)表，并在TLH-L和TLH-P中選擇對(duì)應(yīng)的分類.

第二步需要從TLH-P塊中進(jìn)一步分離出TLH-N塊. 當(dāng)SLLC發(fā)生替換時(shí)，算法將按照TLH-N、TLH-P、偽LRU的順序選擇候選替換者，同時(shí)額外選擇同行中一個(gè)TLH-P塊提前進(jìn)行反向無(wú)效. 若處理器立即發(fā)起對(duì)其訪問(wèn)，則其為T(mén)LH-H塊，否則為T(mén)LH-N塊. 與文獻(xiàn)[10]中策略不同的是，考慮到LRU算法已經(jīng)不能有效識(shí)別SLLC的局部性特征，本文將使用硬件開(kāi)銷更小的偽LRU算法作為備用算法，使得資源消耗下降76.6%.

此外，圖3中的旁路塊地址恢復(fù)機(jī)制，根據(jù)旁路命中塊中存儲(chǔ)的tag段和segment段，配合當(dāng)前地址的sub-index段，可還原旁路塊地址以檢索采樣集，使得旁路算法能夠指導(dǎo)替換算法進(jìn)一步提高預(yù)測(cè)精度.

2.3 管理算法

本文進(jìn)一步挖掘了所提局部性預(yù)測(cè)器和旁路概率預(yù)測(cè)器相互校準(zhǔn)的能力，提出了管理算法如下.

1.若訪問(wèn)SLLC的Cache塊x命中：

使用x.hashedPC索引預(yù)測(cè)表PTable，并更新x.type；

若x被BB中旁路塊y指向：

if BB(y).vb=0

PBB++;

else

PBB--;

2.若訪問(wèn)SLLC的Cache塊x缺失：

2a.若x在BB中命中：

if BB(x).vb = 0

PBB- - ;

else

PBB++;

2b.若額外向L1 Cache無(wú)效的TLH-P塊z被再次訪問(wèn)：

z.type= TLH-H;

若z被BB中旁路塊y指向:

if BB(y).vb = 0

PBB++;

else

PBB- -;

2c.若額外向L1 cache無(wú)效的TLH-P塊z沒(méi)有再次被訪問(wèn)：

z.type=TLH-L;

若z被BB中旁路塊y指向：

if BB(y).vb = 0

PBB- -;

else

PBB++;

3.若x在LLC命中時(shí)在BB中有旁路塊指向，且還原后的

該旁路塊地址與采樣集中塊k命中：

使用k.storedPC索引PTable，并得到索引值Creplace：

k.set.type=TLH-L;

Creplace++;

兩種算法的相互校準(zhǔn)發(fā)生在3種情況：

① SLLC或BB命中. 當(dāng)SLLC命中，根據(jù)命中塊所處虛擬分區(qū)位置與BB表項(xiàng)中的各segment段進(jìn)行對(duì)比，確認(rèn)該塊是否被BB指向. 若被真實(shí)指向，說(shuō)明旁路算法有效且旁路概率自增；若被虛擬指向，說(shuō)明旁路算法失效，旁路概率自減. 當(dāng)BB命中時(shí)，旁路概率的調(diào)整方向則與SLLC命中時(shí)相反(參見(jiàn)算法1和2a).

② TLH-P塊的2次分類. TLH-P塊的預(yù)先無(wú)效不僅可以動(dòng)態(tài)調(diào)整替換算法的精度，也可提高旁路算法的精度. 如果該塊被二次確認(rèn)為T(mén)LH-H塊，并且被一個(gè)旁路塊真實(shí)指向，那么將證明旁路有效且提高旁路概率，虛擬旁路則降低旁路概率；若為T(mén)LH-N塊，則旁路概率的調(diào)整方向相反(參見(jiàn)算法2b和2c).

③ 采樣集的更新. 旁路算法的預(yù)測(cè)結(jié)果同樣可以提高采樣集的預(yù)測(cè)精度. 如果SLLC中命中數(shù)據(jù)被旁路塊指向，則該旁路塊為T(mén)LH-N. 利用圖3的旁路塊地址恢復(fù)機(jī)制，可還原該旁路塊的地址并對(duì)采樣集進(jìn)行虛擬查詢. 如果該地址在采樣集中命中，則可按照TLH-N塊對(duì)采樣集和預(yù)測(cè)表進(jìn)行更新(參見(jiàn)算法3).

3 性能評(píng)價(jià)方法

3.1 配 置

本文使用基于Simics[13]的全系統(tǒng)模擬平臺(tái)模擬UltraSPARC結(jié)構(gòu)的4核處理器. 每個(gè)處理器都有獨(dú)立的一級(jí)指令Cache和數(shù)據(jù)Cache，片上的4個(gè)核共享二級(jí)Cache. 仿真系統(tǒng)的配置如下. 片上核數(shù)為4；主頻為1.2 GHz；微結(jié)構(gòu)為順序結(jié)構(gòu)，每條指令的執(zhí)行時(shí)間為1周期.① 一級(jí)指令和數(shù)據(jù)Cache:私有；指令Cache 32 kB，4路組相聯(lián)，塊大小16字節(jié)；數(shù)據(jù)Cache 16 kB，4路組相聯(lián)，塊大小16字節(jié)，寫(xiě)直達(dá)；均采用LRU替換策略，訪問(wèn)命中開(kāi)銷為1個(gè)周期.② 二級(jí)Cache:共享；2 MB混合結(jié)構(gòu)，16路組相聯(lián)，塊大小32字節(jié)；訪問(wèn)命中為20個(gè)周期；兩級(jí)緩存采用包含性策略，寫(xiě)直達(dá).③ 主存:數(shù)據(jù)寬度8字節(jié)，大小1 GB，訪問(wèn)延遲100個(gè)周期.系統(tǒng)的其他配置采用模擬器的默認(rèn)配置.

3.2 測(cè)試負(fù)載

本文采用由SPEC 2006與SPEC 2000中部分應(yīng)用組合而成的多道負(fù)載來(lái)評(píng)測(cè)所提管理策略的性能. 根據(jù)應(yīng)用程序在兩級(jí)緩存缺失率的高低程度，本文進(jìn)行如下分類：① 私有緩存密集型：在私有緩存中缺失率較低的應(yīng)用，包括deal2，h264ref，perlbench，povray，sjeng；② 共享緩存密集型：在共享緩存中缺失率較低的應(yīng)用，包括astar，bzip2，calculix，vortex，xalancbmk；③ 非存儲(chǔ)密集型：在共享緩存中缺失率較高的應(yīng)用，包括gobmk，art，mcf，equake，ammp. 這其中，測(cè)試程序ammp，mcf，art，equake，vortex的旁路塊比例較高. 表1列出了本文所使用的全部負(fù)載組合.

表1 4核多道程序測(cè)試程序集

4 實(shí)驗(yàn)結(jié)果及分析

4.1 SLLC缺失率

圖4給出了在包含式體系下TMC、BBA、本文所提策略(記為HMP)以及非包含式體系下LRU策略各自產(chǎn)生的SLLC缺失率，所有數(shù)據(jù)均以包含式緩存下LRU策略作為基準(zhǔn).

結(jié)果顯示，旁路策略BBA在mix04與mix07的效果優(yōu)于替換策略TMC，這是因?yàn)樗鼈兙话谴鎯?chǔ)密集型程序，但因擁有旁路概率較大的mcf和vortex，使得旁路操作多于替換操作. 相比之下，mix03不包含旁路概率較大的程序，因此旁路效果與非包含式結(jié)構(gòu)差距不大. 所有程序集中，mix01使用TMC與BBA效果差距不大，這是因?yàn)殡m然含有旁路概率較大的程序art與ammp，但其中ammp數(shù)據(jù)的復(fù)用距離較大，使得容量有限的旁路緩存難以發(fā)揮作用. 相對(duì)于TMC和BBA，HMP策略明顯優(yōu)于包含式LRU策略，其SLLC平均缺失率降低21.67%；同時(shí)與TMC和BBA策略相比， SLLC缺失率平均降低7.40%和3.75%. 這種性能的提升不僅源自HMP對(duì)兩種技術(shù)的綜合運(yùn)用，也得益于其對(duì)兩種技術(shù)互補(bǔ)性的挖掘.

4.2 預(yù)測(cè)精度分析

HMP算法的有效實(shí)施依賴于其對(duì)旁路塊和替換塊的預(yù)測(cè)精度. 圖5給出了HMP算法對(duì)于表1中所有多道程序負(fù)載的預(yù)測(cè)分析. 從圖中可以看出，替換塊和旁路塊的平均預(yù)測(cè)精度分別高達(dá)72%和60%. 算法之所以具有較高的預(yù)測(cè)精度，一方面是因?yàn)榕月凡呗栽黾恿颂摂M旁路的假設(shè)，而替換算法使用數(shù)據(jù)塊地址和導(dǎo)致數(shù)據(jù)失效的指令PC來(lái)定位TLH-N型數(shù)據(jù)；另一方面則是HMP算法增加了兩種策略的相互學(xué)習(xí)，進(jìn)一步提高各自的預(yù)測(cè)精度. 這其中，替換塊的預(yù)測(cè)精度略高的原因在于，進(jìn)入Cache的數(shù)據(jù)塊已經(jīng)經(jīng)過(guò)了旁路策略的初步篩選，從而降低了無(wú)用塊對(duì)采樣集和預(yù)測(cè)表性能的干擾.

4.3 硬件開(kāi)銷

HMP策略的存儲(chǔ)開(kāi)銷主要來(lái)源于3方面：SLLC各Cache塊的局部性分類標(biāo)識(shí)；旁路緩存；采樣集和預(yù)測(cè)表.

表2給出了HMP策略的存儲(chǔ)開(kāi)銷，僅有14.51 kB，不到SLLC面積的1%.

由表2可知，SLLC增加的分類標(biāo)識(shí)占整個(gè)額外開(kāi)銷的55%，這反映出以SLLC緩存塊為單位進(jìn)行優(yōu)化將產(chǎn)生較大的開(kāi)銷. 相反地，旁路緩存采用行數(shù)為16的4路相聯(lián)結(jié)構(gòu)，而采樣集采用行數(shù)為64的12路相聯(lián)結(jié)構(gòu)，預(yù)測(cè)表為3套4 096個(gè)兩位計(jì)數(shù)器，這些開(kāi)銷較小的輔助結(jié)構(gòu)均不受SLLC容量影響，因而適用于對(duì)開(kāi)銷和可靠性要求較高的空間處理器.

表2 HMP策略硬件電路的存儲(chǔ)開(kāi)銷

5 結(jié) 論

包含式緩存有助于簡(jiǎn)化多核處理器一致性設(shè)計(jì)復(fù)雜度和提高可靠性，但相關(guān)的管理策略卻依舊存在性能瓶頸. 本文提出的SLLC管理策略，圍繞分配策略和替換策略兩方面進(jìn)行性能優(yōu)化. 分配策略通過(guò)使用開(kāi)銷較小的旁路緩存，首先將使用頻率較低的無(wú)用數(shù)據(jù)直接旁路到上級(jí)緩存，不僅避免對(duì)SLLC復(fù)用頻率較高數(shù)據(jù)的競(jìng)爭(zhēng)，同時(shí)也維護(hù)了緩存的包含屬性. 替換策略基于預(yù)測(cè)表和采樣集，利用缺失數(shù)據(jù)的地址和PC進(jìn)行局部性特征的分析，從而在SLLC的數(shù)據(jù)中選擇復(fù)用性最低的數(shù)據(jù)作為替換對(duì)象. 兩種策略通過(guò)相互學(xué)習(xí)和完善，在有效降低SLLC缺失率的同時(shí)，更進(jìn)一步提高了管理策略的預(yù)測(cè)精度，而其較低的硬件開(kāi)銷同樣符合未來(lái)空間應(yīng)用對(duì)資源消耗的苛刻要求.

[1] Jianwei D， Lei W. An energy-efficient L2 cache architecture using way tag information under write-through policy[J]. IEEE Trans on VLSI systems， 2013，21(1):102-111.

[2] Jorge A， Pablo I， Victor V， et al. Exploiting reuse locality on inclusive shared last-level caches[J]. ACM Trans on ACO， 2013，9(4):38.1-39.19.

[3] Jue W， Xiangyu D， Yuan X. Preventing STT-RAM last-level caches from port obstruction[J]. ACM Trans on ACO， 2014，11(3):23.1-23.19.

[4] Viacheslav V F， Sheng Q， Narasimha R， et al. ARI: adaptive LLC-memory traffic management[J]. ACM Trans on ACO， 2013，10(4):46.1-46.19.

[5] Pierfrancesco F， Marco S. Exploiting to improve performance of NUCA-based CMP systems[J]. ACM Trans on Embedded Computing Systems， 2014，13(3):117.1-117.23.

[6] Geng T， Michael L. An effectiveness-based adaptive cache replacement policy[J]. Microprocessors and Microsystems， 2014，38(1):98-111.

[7] Eom Y S， Kwak J W， Jhang S T， et al. Bypass extended stack processing for anti-thrashing replacement in shared last level cache of chip multiprocessors[J]. IEICE Trans on Information and Systems， 2013，96(2):370-374.

[8] Saurabh G， Hongliang G， Huiyang Z. Adaptive cache bypassing for inclusive last level caches[C]∥IEEE 27th international Symposium on IPDPS. Boston， USA: [s.n.]， 2013:1243-1253.

[9] Ni Y L， Zhou X F. A novel pseudo-LRU based shared cache partitioning mechanism[J]. Acta Electronica Sinica， 2013，41(4):68-684.

[10] Aamer J， Eric B， Malini B， et al. Achieving non-inclusive cache performance with inclusive caches[C]∥43rd Annual IEEE/ACM International Symposium on MICRO. Atlanta， USA: [s.n.]， 2010:151-162.

[11] Yingying T， Samira M K， Daniel A J. Temporal-based multilevel correlating inclusive cache replacement[J]. ACM Trans on ACO， 2013，10(4):1544-3566.

[12] Yoav E， Dror G F. Exploiting core working sets to filter the L1 cache with random sampling[J]. IEEE Trans on Computers， 2012，61(11):1535-1550.

[13] Huang Z B， Zhu M F， Xia L M. A cache dynamic power analysis tool in full-system Simics[J]. Journal of Shanghai Jiaotong University， 2013:47(1):103-107.

(責(zé)任編輯：劉芳)

A Shared Last-Level Cache Management Policy for Inclusive Cache

LOU Mian1， XIAO Jian-qing1， ZHANG Xun-ying1， WU Long-sheng1， GUAN Gang-qiang2

(1.Xi’an Micro-Electronics Technique Institute， Xi’an， Shannxi 710075，China； 2.School of Electronic Science and Engineering， National University of Defense Technology， Changsha， Hunan 410073， China)

For the problem that the traditional LRU replacement is unaware of the temporal locality in inclusive cache, a shared last-level cache (SLLC) management policy was presented for inclusive cache. With a cost-less bypass buffer stored the useless data beforehand, the policy could avoid the resource competition in SLLC between these data and highly reused data, while it still maintains the inclusion property. To further find out the least reused blocks to replace, a temporal locality detector applied was helpful to evict these blocks from SLLC as early as possible. Finally, benefited from adjustment mutually between two predictors, a unified management algorithm was proposed to bypass the useless blocks and replace the less reused blocks. Test results show that the approach reduces miss rate by 21.67% on average and improves the prediction accuracy up to 72%, while requiring less than 1% overhead of SLLC.

inclusive cache; management policy; shared last-level cache; multiprocessors

2014-09-08

國(guó)家“八六三”計(jì)劃項(xiàng)目(2011AA120204)；航天創(chuàng)新計(jì)劃項(xiàng)目(YY2011-012)

婁冕(1987—)，男，博士生，E-mail：citydremer@163.com.

吳龍勝(1968—)，男，研究員，博士生導(dǎo)師，E-mail：wls771@163.com.

TN 47

A

1001-0645(2016)01-0075-06

10.15918/j.tbit1001-0645.2016.01.014