面向預(yù)取的最優(yōu)替換策略分析

李亞各+袁萬騰

摘要：存儲(chǔ)延遲通常是提高計(jì)算機(jī)系統(tǒng)性能的關(guān)鍵瓶頸。存儲(chǔ)系統(tǒng)，尤其是最后一級(jí)高速緩存（LLC）是解決“存儲(chǔ)墻”的有效方法，LLC的管理方法已經(jīng)成為影響處理器性能的關(guān)鍵因素。預(yù)取技術(shù)能夠利用時(shí)間局部性和空間局部性來減少流水線阻塞，從而提高計(jì)算機(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)行動(dòng)態(tài)選擇[13]，原理是基于之前使用替換策略的歷史信息。我們選擇SPLASH-2作為測(cè)試基準(zhǔn)來測(cè)試這些替換策略的性能。最后我們總結(jié)了不同策略的特性。

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

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

1 介紹

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

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

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

2 替換策略

2.1 DIP策略的分析

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

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

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

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

2.2 DRRIP策略的分析

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

1）SRRIP策略

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

在初始情況下，所有的cache塊的RRPV值都等于‘3。一旦cache命中，該cache塊的RRPV值就被設(shè)置成‘0；相反地，一旦cache發(fā)生缺失，SRRIP策略會(huì)選擇再次調(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ù)ε來表示這個(gè)概率值，設(shè)定ε = 1/32，即在32次插入新行的情況下，有31次插入RRPV值為‘3的位置，1次插入RRPV值為‘2的位置。

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

對(duì)于本文中的提到的所有實(shí)驗(yàn)，我們?cè)O(shè)置一個(gè)cache中的組數(shù)N為16，K為4。PS能夠追蹤ATD-SRRIP和ATD-BRRIP之間哪一個(gè)發(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替換策略競(jìng)賽（CRC）提供的仿真器[12]。CRC是基于跟蹤驅(qū)動(dòng)的仿真器，提供了類結(jié)構(gòu)中的元數(shù)據(jù)和函數(shù)，用來在LLC中選擇被替換的cache行。在仿真過程中，可以選擇單核模式或者多核模式。每一個(gè)cache行有8 bits ，全局內(nèi)存為1 Kb。

3.2 CRC配置參數(shù)

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

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

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

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

Cache缺失率能夠表明存儲(chǔ)系統(tǒng)的性能以及平均內(nèi)存訪問時(shí)間，所以cache缺失率是評(píng)估一種替換策略優(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ù)測(cè)到很久不再調(diào)用的cache行替換掉，提高了cache空間的使用率。LRU策略的高cache缺失率主要由兩個(gè)原因?qū)е拢菏紫?，如果某一行不存在時(shí)間局部性就意味著這一行可能很久都不會(huì)再被調(diào)用，如果將這樣的行保留在cache內(nèi)，顯然是毫無意義的；另外，如果某一行再次被調(diào)用的距離大于cache塊的大小，那么LRU策略就會(huì)再該行被調(diào)用之前將它替換掉。為了克服LRU策略的缺點(diǎn)，我們實(shí)現(xiàn)了DIP策略和DRRIP策略通過使用Set Dueling機(jī)制來動(dòng)態(tài)的選擇一種最優(yōu)策略，其中用到了預(yù)測(cè)機(jī)制，對(duì)某一cache行將來會(huì)被調(diào)用的可能性進(jìn)行預(yù)測(cè)。

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

4.2 硬件開銷

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

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

5 總結(jié)

在本文中，我們實(shí)現(xiàn)了兩種基于預(yù)取思想的LLC替換策略：DIP策略和DRRIP策略。這兩種策略動(dòng)態(tài)的選擇一種發(fā)生缺失較少的策略來對(duì)大部分cache行進(jìn)行替換操作，克服了典型的LRU策略的缺點(diǎn)：總是替換最近最少使用的cache行，即使該行可能很快被再次調(diào)用。我們選擇仿真器CRC來比較不同替換策略的優(yōu)劣，測(cè)試基準(zhǔn)為標(biāo)準(zhǔn)測(cè)試集為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%。同時(shí)，我們對(duì)兩種策略的硬件開銷進(jìn)行了對(duì)比，DRRIP策略的開銷略大于DIP策略的開銷，由于對(duì)關(guān)鍵路徑?jīng)]有影響因此可以忽略不計(jì)。從實(shí)驗(yàn)結(jié)果得出，不同的替換策略針對(duì)不同的測(cè)試基準(zhǔn)會(huì)有不一樣的優(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.