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

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

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

?

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

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

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

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

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

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

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

1 動機與背景

1.1 動 機

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

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

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

1.2 相關(guān)工作

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

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

2 包含式SLLC管理策略

2.1 旁路策略

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

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

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

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

2.2 替換機制

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

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

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

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

2.3 管理算法

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

1.若訪問SLLC的Cache塊x命中：

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

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

if BB(y).vb=0

PBB++;

else

PBB--;

2.若訪問SLLC的Cache塊x缺失：

2a.若x在BB中命中：

if BB(x).vb = 0

PBB- - ;

else

PBB++;

2b.若額外向L1 Cache無效的TLH-P塊z被再次訪問：

z.type= TLH-H;

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

if BB(y).vb = 0

PBB++;

else

PBB- -;

2c.若額外向L1 cache無效的TLH-P塊z沒有再次被訪問：

z.type=TLH-L;

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

if BB(y).vb = 0

PBB- -;

else

PBB++;

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

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

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

k.set.type=TLH-L;

Creplace++;

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

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

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

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

3 性能評價方法

3.1 配 置

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

3.2 測試負(fù)載

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

表1 4核多道程序測試程序集

4 實驗結(jié)果及分析

4.1 SLLC缺失率

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

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

4.2 預(yù)測精度分析

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

4.3 硬件開銷

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

表2給出了HMP策略的存儲開銷，僅有14.51 kB，不到SLLC面積的1%.

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

表2 HMP策略硬件電路的存儲開銷

5 結(jié) 論

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

[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

國家“八六三”計劃項目(2011AA120204)；航天創(chuà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