李亞各+袁萬騰

摘要：存儲延遲通常是提高計算機(jī)系統(tǒng)性能的關(guān)鍵瓶頸。存儲系統(tǒng)，尤其是最后一級高速緩存（LLC）是解決“存儲墻”的有效方法，LLC的管理方法已經(jīng)成為影響處理器性能的關(guān)鍵因素。預(yù)取技術(shù)能夠利用時間局部性和空間局部性來減少流水線阻塞，從而提高計算機(jī)系統(tǒng)的整體性能。該文基于不同工作負(fù)載的特性來研究最先進(jìn)的結(jié)合預(yù)取思想的LLC管理策略。我們實(shí)現(xiàn)了Bimodal Insertion Policy （BIP），該策略能夠適應(yīng)多變的工作負(fù)載。為了進(jìn)一步減少cache的缺失率，我們使用Set Dueling策略在Static Re-Reference Interval Policy（SRRIP）和Bimodal Re-Reference Interval Policy（BRRIP）之間進(jìn)行動態(tài)選擇[13]，原理是基于之前使用替換策略的歷史信息。我們選擇SPLASH-2作為測試基準(zhǔn)來測試這些替換策略的性能。最后我們總結(jié)了不同策略的特性。

關(guān)鍵詞： LLC； 替換策略； CRC

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）04-0089-04

1 介紹

最經(jīng)典的替換策略是最近最少使用策略（LRU），但是在當(dāng)前的多核處理器中， 由于cache的高關(guān)聯(lián)度會引起cache死塊的問題，所以LRU策略逐漸失去了它的優(yōu)勢。同時，許多的工作負(fù)載中一個工作集就遠(yuǎn)遠(yuǎn)大于可用的cache大小。為了提高這些工作負(fù)載的性能，能夠有效彌補(bǔ)LRU策略不足的動態(tài)替換策略引起了廣泛的關(guān)注。

當(dāng)目標(biāo)cache寫滿的時候，替換策略選擇該cache中某一行進(jìn)行替換。在替換中，通常有兩個關(guān)鍵的位置：最近最少使用位置（LRU）和最近最多使用位置（MRU） 。BIP替換策略的主要思想是：大部分情況下將新的cache行替換到LRU位置，剩余的情況替換到MRU位置。BIP策略能夠適應(yīng)工作集的變化并且同時保留了LRU策略的cache沖突保護(hù)機(jī)制。接下來我們使用Set Dueling 機(jī)制在LRU策略和BIP策略之間動態(tài)選擇一種更好地策略應(yīng)用到之后的替換中。為了進(jìn)一步提高系統(tǒng)的性能，我們實(shí)現(xiàn)了Dynamically Re-Reference Interval Policy （DRRIP），該策略使用Set Dueling 機(jī)制在SRRIP策略以及BRRIP策略之間進(jìn)行動態(tài)選擇。DRRIP策略在每一個cache行設(shè)置一個計數(shù)器來存儲這些行的Re-Reference Interval Prediction （RRPV）值[13]。

我們選擇cache替換策略競賽（CRC）提供的仿真環(huán)境來比較不同替換策略的優(yōu)劣[12]。由于LLC的長延遲性以及LLC存取的低訪問率，仿真環(huán)境對替換策略的算法的復(fù)雜性不做限制。我們通過選擇典型的基準(zhǔn)測試程序——SPLASH-2對替換策略進(jìn)行評估，結(jié)果顯示DIP策略能夠提高12.64%的平均性能，DRRIP策略能夠提高11.57% 的平均性能。

2 替換策略

2.1 DIP策略的分析

傳統(tǒng)的LRU策略總是丟棄最近最少使用的數(shù)據(jù)，將新行插入到MRU行，這種做法會導(dǎo)致非LRU行的其他行的優(yōu)先級得不到提高，即使有一些cache行剛被訪問過。因?yàn)槊慨?dāng)一個cache行被訪問一次，所有的cache行優(yōu)先級都會發(fā)生變化。BIP策略能夠通過在低概率下將新行插入LRU位置來緩解這種情況，我們用參數(shù)ε來表示這個概率值[1]。我們設(shè)定ε= 1/32，即在32次插入新行的情況下，有31次插入MRU位置，1次插入LRU位置。

DIP策略通過在LRU策略和BIP策略之間進(jìn)行動態(tài)選擇來提高效率?？紤]到工作負(fù)載的不同，DIP策略選擇在標(biāo)記組中發(fā)生缺失較少的策略來對新行進(jìn)行替換操作。我們使用Set Dueling 機(jī)制在沒有增加顯著硬件開銷的情況下實(shí)現(xiàn)DIP[1]策略。假設(shè)在cache中有N組，每一組有若干行，K表示使用每種策略的組數(shù)（N=2K）。我們將cache分成K個區(qū)域，每個區(qū)域大小都為N/K，總共需要log2N bits，我們使用其中的log2K bits來標(biāo)示選區(qū)，log2N/K bits來標(biāo)示選區(qū)與第一組的偏移量[1]。DIP策略的存儲開銷僅需要2 bits來檢測每組使用的替換策略。

對于本文中的提到的所有實(shí)驗(yàn)，我們設(shè)置一個cache中的組數(shù)N為16，K為4。我們使用2 bits 來標(biāo)示該組使用的替換策略是LRU或者BIP，組號為0以及5的倍數(shù)的組被標(biāo)示為使用LRU策略，組號為3的倍數(shù)的組被標(biāo)示為使用BIP策略。在cache中，輔助變量目錄（ATD）與主變量目錄（MTD）具有相同的關(guān)聯(lián)度，我們將飽和計數(shù)器命名為策略選擇器（PS），PS能夠追蹤ATD-LRU 和ATD-BIP之間哪一個發(fā)生的缺失更少。如果ATD-LRU發(fā)生一次缺失，PS加1，相反地，如果ATD-BIP發(fā)生一次缺失，PS減1[1]。PS的最高有效位（MSB）能夠指示哪一種策略發(fā)生更少的缺失。DIP策略的原理圖如圖1所示。

在MTD中共有16組，從0號組到15號組，我們選擇其中四組來標(biāo)示使用LRU策略：0號、5號、10號、15號；再選擇四組來標(biāo)示使用BIP策略：3號、6號、9號、12號；剩余的組所使用的替換策略是由PS選擇出來的效果較好的一種策略。如上文所述，如果ATD-LRU 發(fā)生一次缺失，PS加1，相反地，如果ATD-BIP 發(fā)生一次缺失，如果PS的MSB等于1，那么MTD使用BIP策略，否則使用LRU策略。

2.2 DRRIP策略的分析

RRIP值代表預(yù)測某一cache塊被重新調(diào)用的次序[13]。在RRIP鏈的前端，表示該cache塊很快會被再次調(diào)用，而在RRIP鏈的后端則表示該cache塊被再次調(diào)用的間隔會很久。DRRIP策略使用Set Dueling 機(jī)制在SRRIP策略和BRRIP策略之間動態(tài)選擇一種更好地策略應(yīng)用到下一次替換中，以此來減少發(fā)生缺失的次數(shù)。

1）SRRIP策略

如果一個cache塊間隔很久才會被調(diào)用，那么就有可能引起cache的高缺失率，低cache的使用率。為了阻止那些再次調(diào)用間隔很久的cache塊污染cache，SRRIP策略在每個cache塊中使用M bits來存儲該塊的RRPV值。RRPV值會隨著每個塊被調(diào)用的頻率動態(tài)變化。對于本文中的提到的所有實(shí)驗(yàn)，我們設(shè)置M的值為2。RRPV值等于‘0，說明該cache塊最近被調(diào)用過，而且預(yù)測處理器很快會再次調(diào)用該cache塊；RRPV值等于‘3，說明該cache塊最近沒有被調(diào)用過，而且處理器在短時間內(nèi)不會再次調(diào)用該cache塊；RRPV值等于‘1或者‘2時，說明該cache塊會有較高的可能性被調(diào)用。

在初始情況下，所有的cache塊的RRPV值都等于‘3。一旦cache命中，該cache塊的RRPV值就被設(shè)置成‘0；相反地，一旦cache發(fā)生缺失，SRRIP策略會選擇再次調(diào)用間隔很久的cache塊進(jìn)行替換，首先查找RRPV值為‘3的cache塊進(jìn)行替換，并將其RRPV值設(shè)置成‘2，如果沒有找到RRPV值為‘3的cache塊，就將所有cache塊的RRPV值加1后再進(jìn)行查找，直到找到RRPV值為‘3的cache塊。圖2表示的是四路初始值為‘I的cache塊，在一系列混合存取模式下的SRRIP策略的工作流程。

2）DRRIP策略

為了避免cache沖突以及適應(yīng)不同種類的工作集，參考文獻(xiàn)[13]提出了BRRIP策略。與上文提到的BIP策略類似，BRRIP策略在低概率下將新cache塊替換到RRPV值為‘2的塊，我們用參數(shù)ε來表示這個概率值，設(shè)定ε = 1/32，即在32次插入新行的情況下，有31次插入RRPV值為‘3的位置，1次插入RRPV值為‘2的位置。

但是對于不存在cache沖突的存取模式，總是使用BRRIP策略是有害無益的。所以我們通過使用Set Dueling機(jī)制在SRRIP策略和BRRIP策略之間進(jìn)行動態(tài)選擇，基于歷史信息選擇發(fā)生較少缺失的策略應(yīng)用到其他cache塊。具體實(shí)現(xiàn)方法類似于上文描述的DIP策略。DRRIP策略的存儲開銷僅需要2 bits來檢測每組使用的替換策略。DRRIP策略的原理圖如圖3所示。

對于本文中的提到的所有實(shí)驗(yàn)，我們設(shè)置一個cache中的組數(shù)N為16，K為4。PS能夠追蹤ATD-SRRIP和ATD-BRRIP之間哪一個發(fā)生的缺失更少。如果ATD-SRRIP發(fā)生一次缺失，PS加1，相反地，如果ATD-BRRIP發(fā)生一次缺失，PS減1。PS的MSB能夠指示哪一種策略發(fā)生更少的缺失。如果PS的MSB等于1，那么MTD使用BRRIP策略，否則使用SRRIP策略。

3 實(shí)驗(yàn)方法

3.1 仿真環(huán)境

為了比較不同替換策略的優(yōu)劣，我們選擇cache替換策略競賽（CRC）提供的仿真器[12]。CRC是基于跟蹤驅(qū)動的仿真器，提供了類結(jié)構(gòu)中的元數(shù)據(jù)和函數(shù)，用來在LLC中選擇被替換的cache行。在仿真過程中，可以選擇單核模式或者多核模式。每一個cache行有8 bits ，全局內(nèi)存為1 Kb。

3.2 CRC配置參數(shù)

CRC中的RADEME.txt文件對存儲結(jié)構(gòu)的具體配置進(jìn)行了詳細(xì)的描述。LLC的配置包括16路的組，64 bytes的行，以及每個核有1 MB的大小。在單核中，LLC大小為1MB，在四核中，有4MB的共享LLC。L1 cache的大小為32KB， L2 cache的大小為256KB。LLC的具體配置參數(shù)如表1所示。

在實(shí)驗(yàn)中，單核以及雙核的配置均為三級cache，我們主要研究LLC的cache缺失率。我們通過選擇典型的基準(zhǔn)測試程序——SPLASH-2來對替換策略進(jìn)行評估。

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

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

Cache缺失率能夠表明存儲系統(tǒng)的性能以及平均內(nèi)存訪問時間，所以cache缺失率是評估一種替換策略優(yōu)劣的重要指標(biāo)。本文基于處理器的單核模式來比較每一種替換策略的優(yōu)缺點(diǎn)。在我們使用的仿真器中，提供兩種基本的替換策略：LRU策略和RANDOM策略。我們基于仿真器CRC實(shí)現(xiàn)了DIP策略和DRRIP策略。實(shí)驗(yàn)結(jié)果如表2所示。

圖4表明我們實(shí)現(xiàn)的DIP策略以及DRRIP策略的cache缺失率比傳統(tǒng)的LRU策略和RANDOM策略有明顯的降低。通過實(shí)驗(yàn)數(shù)據(jù)我們可以得到，在最好的情況下，DIP策略降低了16.85% 的cache缺失率，DRRIP策略降低了14.94%的cache缺失率。能夠減小cache缺失率的根本原因在于，DIP策略和DRRIP策略能夠克服cache空間的無效占用，將預(yù)測到很久不再調(diào)用的cache行替換掉，提高了cache空間的使用率。LRU策略的高cache缺失率主要由兩個原因?qū)е拢菏紫?，如果某一行不存在時間局部性就意味著這一行可能很久都不會再被調(diào)用，如果將這樣的行保留在cache內(nèi)，顯然是毫無意義的；另外，如果某一行再次被調(diào)用的距離大于cache塊的大小，那么LRU策略就會再該行被調(diào)用之前將它替換掉。為了克服LRU策略的缺點(diǎn)，我們實(shí)現(xiàn)了DIP策略和DRRIP策略通過使用Set Dueling機(jī)制來動態(tài)的選擇一種最優(yōu)策略，其中用到了預(yù)測機(jī)制，對某一cache行將來會被調(diào)用的可能性進(jìn)行預(yù)測。

以上的實(shí)驗(yàn)結(jié)果顯示DIP策略能夠提高12.64%的平均性能，DRRIP策略能夠提高11.57% 的平均性能。這些數(shù)據(jù)表明我們實(shí)現(xiàn)的LLC替換策略能夠有效地避免cache污染，適應(yīng)多種不同的工作負(fù)載，顯著地提高了cache性能。同時，結(jié)果表明，對于不同的測試基準(zhǔn)程序每種替換策略得到的cache缺失率也不相同，這主要是因?yàn)槟軌騼?yōu)化的空間與特定測試基準(zhǔn)程序有密切關(guān)系。

4.2 硬件開銷

BIP策略在低概率ε下將新行插入MRU位置，我們設(shè)置ε = 1/32，因此需要5 bits計數(shù)器來控制新的插入行要插入MRU位置或是LRU位置。DIP策略中的PS計數(shù)器需要10 bits來對LRU策略和BIP策略進(jìn)行選擇。實(shí)現(xiàn)Set Dueling機(jī)制僅需一個單飽和計數(shù)器。SRRIP策略的實(shí)現(xiàn)需要對每個cache塊增加一個2 bits的寄存器來存儲RRPV值（‘0，‘1，‘2，和‘3），4個邏輯單元來進(jìn)行查找RRPV值為‘3的cache塊，如果沒有找到，就需要額外的一個邏輯對組中所有RRPV寄存器進(jìn)行加1操作。BRRIP策略所需的存儲開銷在SRRIP策略的基礎(chǔ)上，再加上一個額外的5 bits計數(shù)器用來控制將新cache塊替換到RRPV值為‘2的塊。DRRIP策略是對SRRIP策略和BRRIP策略進(jìn)行動態(tài)選擇，因此需要10 bits的PS計數(shù)器。

從上述的比較中，我們可以考出DRRIP策略比DIP策略需要較多的開銷。然而這些開銷沒有對關(guān)鍵路徑進(jìn)行改變，因此不會對cache的存取時間造成很大的影響。

5 總結(jié)

在本文中，我們實(shí)現(xiàn)了兩種基于預(yù)取思想的LLC替換策略：DIP策略和DRRIP策略。這兩種策略動態(tài)的選擇一種發(fā)生缺失較少的策略來對大部分cache行進(jìn)行替換操作，克服了典型的LRU策略的缺點(diǎn)：總是替換最近最少使用的cache行，即使該行可能很快被再次調(diào)用。我們選擇仿真器CRC來比較不同替換策略的優(yōu)劣，測試基準(zhǔn)為標(biāo)準(zhǔn)測試集為SPLASH-2中的FFT，RADIX和BARNES。從實(shí)驗(yàn)結(jié)果可以看出，DIP策略和DRRIP策略的cache缺失率明顯低于傳統(tǒng)的LRU策略和RANDOM策略。大量的實(shí)驗(yàn)數(shù)據(jù)表明在單核模式下，cache缺失率可以從88.29% 降到69.26%。同時，我們對兩種策略的硬件開銷進(jìn)行了對比，DRRIP策略的開銷略大于DIP策略的開銷，由于對關(guān)鍵路徑?jīng)]有影響因此可以忽略不計。從實(shí)驗(yàn)結(jié)果得出，不同的替換策略針對不同的測試基準(zhǔn)會有不一樣的優(yōu)化，我們可以根據(jù)程序特性，通過選擇平均性能最優(yōu)的替換策略來獲得最高的性能提升。

參考文獻(xiàn)：

[1] Subramanian R.Adaptive Caches： Effective Shaping of Cache Behavior to Workloads[C]. 1995.

[2] Zhao Jianmin， Zhao Jianhua. An Optimal Replacement Policy for a System with Finite Spares[J].Journal of Systems Engineering and Electronics， 1999.

[3] Steven P Vanderwiel， David J Lilja， Data Prefetch Mechanisms[C].ACM Computing Surveys （CSUR）， 2000.

[4] Wong W A， Baer J L. Modified LRU Policies for Improving Second-level Cache Behavior[C].ACHPCA-6， 2000.

[5] Zhuang Weiqiang， Hu min， Wang Dingxing.Replacement Policy for Caching World-Wide Web Documents Based on Site-Graph Model[C].Tsinghua Science and Electronics， 2001.

[6] Lin W， Fide C， Falsafi B. Predicting Last-touch References under Optimal Replacement[R].Technical Report of Michigan University， 2002.

[7] Megiddo N，Modha D S.ARC： A Self-tuning， Low Overhead Replacement Cache[C].Proceeding of the 2nd USENIX Conference on File and Storage Technologies， 2003.

[8] Qureshi M K， Thompson D， Patt Y N. The V-Way Cache： Demand Base Associativity via Global Replacement[J].ISCA， 2005（32）：544-555.

[9] Nai Zhengbian， Hao Chen.A Least Grade Page Replacement Algorithm for Web Cache Optimization[C].Proceedings of the First International Workshop on Knowledge Discovery and Data Mining， 2008.

[10] Wang Deli， Gao Deyuan.A Sharing-Aware Active Pushing Cache Technology on Chip-Multiprocessor [J].Journal of Xian Jiao Tong University， 2010， 44（10）：18-23.

[11] Kahkashan Tabassum， Asia Sultana， Damodaram.A.A Heuristic Cache Replacement Policy for Data Caching[C].Proceeding of 2010 4th International Conference on Intelligent Information Technology Application， 2010.

[12] Yuval Peress， Ian Finlayson， Dr Gary Tyson， CRC： Protected LRU Algorithm[C].JILP Worshop on Computer Architecture Competitions， 2010.

[13] Jaleel A， Theobald K B， Jr Steely S C.High Performance Cache Replacement Using Re-reference Interval Prediction （RRIP） [C].Proceedings of the 38th International Symposium on Computer Architecture， 2010.

[14] Carole Jean Wu， Aamer Jaleel Margaret Martonosi， Simon C Steely.“PACMan： Prefetch-Aware Cache Management for High Performance Caching[C].Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture， 2011.

[15] Li Chongming， Wang Dongshen， Xue Yibo. Enhanced Adaptive Insertion Policy for Shared Caches[C].Proceedings of the 9th international Conference on Advanced Parallel Processing Technologies， 2011.

[16] Tan Lin， Yang Jian， Cheng Zhijun. Optimal Replacement Policy for Cold Standby System[J[. Chinese Journal of Mechanical Engineering， 2011.

[17] Shan Ding，Li Yuanyuan. LRU2_MRU Collaborative Cache Replacement Algorithm on Multi-core System [C].Proceedings of 2012 IEEE International Conference on Computer Science and Automation Engineering， 2012，23（1）：14-17.