石文強(qiáng)，倪曉強(qiáng)，金作霖，張民選

（國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長沙410073）

1 引言

近年來，微處理器體系結(jié)構(gòu)已從單核發(fā)展為多核。與單核相比，多核的計(jì)算能力雖得到極大的提升，但多核中每個(gè)計(jì)算核心所能得到的存儲(chǔ)帶寬、存儲(chǔ)容量卻顯著降低，多核的“存儲(chǔ)墻”問題變得更加突出。目前，多核處理器普遍采用大容量、高相聯(lián)度的末級(jí)Cache LLC（Last Level Cache）以減少片下訪存次數(shù)，提升系統(tǒng)整體性能。

多核下，訪存序列多樣，末級(jí)Cache容量、組相聯(lián)數(shù)不斷增大，傳統(tǒng)的Cache替換算法LRU（Least Recently Used）對(duì) LLC逐漸失效，主要有以下幾方面的原因：（1）Cache死塊變多：對(duì)于某些訪存重用性差的程序，部分?jǐn)?shù)據(jù)塊進(jìn)入Cache后不會(huì)再重用，這樣的塊稱為死塊。當(dāng)組相聯(lián)度增大后，死塊被替換出Cache的時(shí)間變長，整個(gè)Cache中死塊比例增加，Cache的有效利用率變低。Cache預(yù)取技術(shù)中，也存在類似的死塊問題。（2）局部性變差：訪存序列經(jīng)過L1Cache后，到達(dá)LLC的訪存序列時(shí)間局部性降低，而LRU算法利用的就是訪存的時(shí)間局部性，所以LRU對(duì)LLC的效果往往不佳。

針對(duì)以上問題，已有大量的相關(guān)研究［1～3］，解決以上問題的一種思路是改變替換策略的插入策略，即把失效后取回的數(shù)據(jù)塊插入到組內(nèi)的非MRU（Most Recently Used）位置，這樣死塊的逐出時(shí)間變短，可以提升Cache的有效利用率。但是，目前對(duì)插入策略的研究基本都停留在啟發(fā)式策略的水平上［1～3］，缺乏定量的分析及相應(yīng)的理論優(yōu)化方法。

針對(duì)以上問題，本文提出了一個(gè)Cache插入策略的解析模型，該模型以應(yīng)用的循環(huán)序列分布及歷史重用信息為輸入，使用概率模型迭代計(jì)算指定插入策略的失效率，可對(duì)不同插入策略的性能進(jìn)行有效的預(yù)測(cè)。最后的驗(yàn)證結(jié)果表明，模型的精度較高，最大絕對(duì)誤差為15.6%，平均絕對(duì)誤差為3.1%。

2 模型定義及假設(shè)

首先對(duì)Cache中的位置做以下約定。設(shè)Cache的組相聯(lián)度為A，組內(nèi)A個(gè)數(shù)據(jù)塊按物理順序可依次標(biāo)記為位置1～位置A，MRU位置在本文中認(rèn)為是位置1，LRU位置為位置A。組內(nèi)數(shù)據(jù)塊i是指位于位置i的數(shù)據(jù)塊；數(shù)據(jù)塊i位于數(shù)據(jù)塊j之前是指兩者位置有關(guān)系i＜j。

目前替換策略已具體細(xì)化為了三部分［1］：逐出策略、插入策略以及提升策略。逐出策略是指在Cache失效時(shí)，如何選擇被替換出的塊；插入策略即將取回的塊置于組內(nèi)的什么位置；提升策略即命中Cache塊后，該塊在組內(nèi)的位置如何變化。本文主要研究Cache插入策略，故假設(shè)替換策略中的逐出、提升策略與LRU策略相同，即失效時(shí)會(huì)將LRU塊逐出，命中時(shí)會(huì)將命中塊提升到MRU位置。

為建立Cache插入策略模型，本文引入以下概念［4，5］：

（1）循環(huán)序列cseq（Circular Sequence）：一個(gè)Cache組的訪存序列中，數(shù)據(jù)塊B的本次訪存與下次訪存之間的訪存序列（包括B）稱為以B為目標(biāo)塊的循環(huán)序列。若該序列長度為n，其中不同地址數(shù)目為d，則該序列可用cseq（d，n）表示。對(duì)于循環(huán)序列，由于首尾兩次訪存必然為B，所以肯定有n≥d＋1成立。

（2）子 循 環(huán) 序 列 scseq（Sub Circular Sequence）：子循環(huán)序列是指循環(huán)序列cseq（d′，n′）經(jīng)過n′－n（n＜n′）次訪存之后剩余的子串，該子串的長度為n，包括d個(gè)不同的數(shù)據(jù)訪存，用scseq（d，n）表示。

（3）首次訪存 Dis（Distinct）：對(duì)于cseq（d′，n′）中的某次數(shù)據(jù)訪存，若該地址在cseq（d′，n′）之前的訪存中沒有出現(xiàn)過，則稱本次訪存為首次，否則稱為非首次 NoDis（None Distinct），cseq（d′，n′）中的d′即循環(huán)序列中首次訪存的個(gè)數(shù)。

（4）重用距離（棧距離）：若某cseq（d，n）的目標(biāo)塊為B，則B的重用距離為d。若B在整個(gè)訪存序列中只有一次訪存，那么其重用距離為∞。

（5）狀 態(tài)s（d′，n′，d，n，p）：對(duì) 于 某cseq（d′，n′），經(jīng)過一定次數(shù)的訪存后子循環(huán)序列為scseq（d，n），且目標(biāo)塊在組內(nèi)的位置為p，目標(biāo)塊的當(dāng)前狀態(tài)可用s（d′，n′，d，n，p）表示。當(dāng)只考慮一個(gè)cseq（d′，n′）的狀態(tài)時(shí)，s（d′，n′，d，n，p）可簡(jiǎn)寫為s（d，n，p）。

（6）循環(huán)序列分布圖 CSH（Circular Sequence Histogram）：某段時(shí)間內(nèi)應(yīng)用中所有循環(huán)序列出現(xiàn)的頻數(shù)分布。某些cseq（d，n）中的d值與n值可能會(huì)很大，實(shí)際統(tǒng)計(jì)時(shí)，將所有d值大于閾值dmax的歸為一類；對(duì)于每個(gè)d，將n值大于閾值nmax的歸為一類。所以，CSH可表示為一個(gè)（nmax＋1）×（dmax＋1）的二維矩陣，CSH（n，d）表示循環(huán)序列cseq（n，d）出現(xiàn)的次數(shù)。

由于數(shù)據(jù)訪存具有較強(qiáng)的局部性，當(dāng)dmax與nmax足夠大時(shí)，處在兩閾值之外的循環(huán)序列很少，不會(huì)對(duì)模型的精度產(chǎn)生很大的影響。一般情況下，若Cache組相聯(lián)度為A，可取dmax＝2A，nmax＝2dmax。

（7）歷史棧距離分布圖 HSH（History Stack Histogram）：HSH統(tǒng)計(jì)了同一塊兩次訪存重用距離之間的轉(zhuǎn)化關(guān)系，HSH（d0，d1）表示本次訪存棧距離為d1的數(shù)據(jù)塊中上次訪存棧距離為d0的比例。HSH與CSH 有相同的最大重用距離閾值dmax，故 HSH 為一個(gè)（dmax＋1）×（dmax＋1）的矩陣。

本文中提升流（Promotion Stream）是指訪存命中的數(shù)據(jù)塊組成的數(shù)據(jù)流；插入流（Insertion Stream）是指訪存失效后進(jìn)入Cache的數(shù)據(jù)流；動(dòng)態(tài)插入策略是指對(duì)于不同的應(yīng)用，選擇不同的插入位置以提高應(yīng)用性能的替換策略。

3 Cache動(dòng)態(tài)插入模型

本節(jié)對(duì)Cache的插入策略進(jìn)行了建模，其中使用了以下符號(hào)定義：PP（cseq（d，n））表示提升流循環(huán)序列cseq（d，n）的失效率，PI（cseq（d，n））表示插入流循環(huán)序列cseq（d，n）的失效率，Pmiss表示插入策略的整體失效率，p0表示插入策略的插入位置，hi表示所有重用距離為i的數(shù)據(jù)塊的命中率，h＝［h1，h2，…，hdmax］表示各重用距離命中率的集合，CSHP、CSHI為提升流與插入流的循環(huán)序列分布圖。

3.1 建模基本步驟

Guo F［4］首次對(duì) Cache的逐出策略進(jìn)行了理論建模，該模型以訪存序列的循環(huán)序列分布CSH與替換策略函數(shù)為輸入，通過遞歸概率模型來計(jì)算各循環(huán)序列的失效率，經(jīng)多次迭代整體失效率Pmiss計(jì)算出給定逐出策略的Cache失效率。

插入策略模型與逐出策略模型［4］最主要的不同是：在逐出策略模型下提升流與插入流行為相同，所以只需考慮整體數(shù)據(jù)流即可；動(dòng)態(tài)插入策略下，提升流與插入流的行為不同，插入策略模型需要分別考慮提升與插入兩種數(shù)據(jù)流。具體而言，有以下兩個(gè)方面的問題需要解決：

（1）輸入獲取問題：在逐出策略模型中，其輸入與逐出策略無關(guān)，所以對(duì)于不同的逐出策略可由統(tǒng)一的硬件采樣其輸入分布情況；而動(dòng)態(tài)插入策略需要掌握不同插入策略下提升流與插入流的重用分布情況，以對(duì)相同應(yīng)用的不同插入策略的性能做出評(píng)價(jià)，目前已有的采樣方法卻不能同時(shí)獲得多種插入策略下輸入的分布情況。

（2）兩個(gè)數(shù)據(jù)流的相互作用問題：提升流與插入流單個(gè)數(shù)據(jù)流的建?？梢圆捎门c逐出策略相似的遞歸概率計(jì)算的方法，但兩者之間不是獨(dú)立的，如何對(duì)兩者的作用進(jìn)行建模是本模型需要解決的一個(gè)問題。

本文主要通過以下幾步對(duì)Cache的訪存序列進(jìn)行建模，通過多次迭代計(jì)算指定策略的失效率：

（1）獲取應(yīng)用的CSH、HSH分布。

一種應(yīng)用的CSH與HSH可以通過編譯、模擬或在硬件中增加計(jì)數(shù)器來獲得［4，5］，本文不對(duì)此進(jìn)行詳細(xì)討論。

（2）輸入循環(huán)序列分布的計(jì)算。

在逐出策略模型輸入CSH的基礎(chǔ)上，本文引入歷史棧距離分布HSH、第i次迭代中各重用距離的命中率h（i）來計(jì)算不同插入策略下提升流與插入流的循環(huán)序列分布。其中，CSH、HSH只與應(yīng)用相關(guān)，可通過硬件采樣獲得；h（i）與當(dāng)前插入策略相關(guān)，需要通過多次迭代來不斷提升其精度。

（3）循環(huán)序列失效率的計(jì)算。

與逐出模型［4］相似，本文使用了遞歸概率計(jì)算循環(huán)序列的失效率。但是，插入模型不僅需要考慮提升流與插入流單個(gè)數(shù)據(jù)流的行為，建模時(shí)還需考慮提升流與插入流在Cache中的相互作用。

（4）整體失效率的計(jì)算及迭代返回。

計(jì)算出整體失效率 Pmiss及h（i＋1），判斷其是否達(dá)到精度要求或達(dá)到最大迭代次數(shù)，是則停止迭代，否則將h（i＋1）返回第（2）步進(jìn)行下一輪迭代。

3.2 輸入訪存序列分布的計(jì)算

針對(duì)不能獲得不同插入策略下提升流與插入流重用分布的問題，本文提出可使用循環(huán)序列分布CSH、歷史棧距離重用分布HSH、動(dòng)態(tài)插入策略下各重用距離的命中率h三種數(shù)據(jù)來計(jì)算各插入點(diǎn)的輸入分布情況。

提升流分布可以認(rèn)為是訪存命中的數(shù)據(jù)塊被提升至MRU位置后下次重用時(shí)的循環(huán)序列分布。若令HSH （d′，d）表示本次重用距離為d′的數(shù)據(jù)塊中上次重用距離為d的數(shù)據(jù)塊的比例，hd為重用距離為d 的數(shù)據(jù)塊的命中率，則hd′·HSH（d′，d）為重用距離為d的數(shù)據(jù)塊中由上次重用距離為d′的數(shù)據(jù)塊在本次轉(zhuǎn)化為提升流的比例。若令rd表示重用距離為d的數(shù)據(jù)塊轉(zhuǎn)化為提升流的比例，則有：

得到rd后，假設(shè)對(duì)相同的d各個(gè)n的命中率相同，CSHP（d，n）為提升流中cseq（d，n）的頻數(shù)分布情況，則有：得出提升流的分布后，由于CSH對(duì)所有策略都不變，只與應(yīng)用相關(guān)，則插入流的重用分布為：

CSHI（d，n）＝CSH （d，n）－CSHP（d，n）（3）至此，可以根據(jù)CSH、HSH及h得出提升流與插入流的分布情況。

3.3 提升流循環(huán)序列的失效模型

單個(gè)提升流循環(huán)序列PP（cseq（d′，n′））可采用遞歸概率的方法進(jìn)行計(jì)算，該方法主要由一組狀態(tài)與相應(yīng)的狀態(tài)之間的轉(zhuǎn)化概率組成，從對(duì)目標(biāo)塊的第一次訪存開始，每次計(jì)算一次訪存所造成的狀態(tài)轉(zhuǎn)換及相應(yīng)的概率，直至構(gòu)造出完整的cseq（d′，n′），這個(gè)構(gòu)造過程也即數(shù)據(jù)的訪存過程［4］。對(duì)于cseq（d′，n′），第i次訪存結(jié)束后設(shè)其狀態(tài)為s（d，n，p），下次將考慮第i＋1次數(shù)據(jù)訪存可能造成的狀態(tài)轉(zhuǎn)化情況及相應(yīng)的概率，如圖1所示。

Figure 1 State transition of the promote stream圖1 提升流的狀態(tài)轉(zhuǎn)換圖

圖1 中s（d，n，p）為當(dāng)前狀態(tài)，其它狀態(tài)為下次訪存后的狀態(tài)，狀態(tài)之間的連線上標(biāo)記狀態(tài)轉(zhuǎn)化的條件。圖1中共有七種轉(zhuǎn)化情況，可產(chǎn)生四種新的狀態(tài)。其中，Dis表示訪存為首次訪存，NoDis表示非首次訪存；p＜p0表示目標(biāo)塊位置在p0之前，p≥p0表示目標(biāo)塊的位置在p0之后；Miss表示訪存失效，Hit表示訪存命中；Hit≥p表示命中位置大于或等于p，Hit＜p表示命中位置小于p。

圖1中，對(duì)于狀態(tài)參數(shù)n，每次訪存后，子循環(huán)序列的長度n必然會(huì)減1。對(duì)于d，如果此次訪存為首次出現(xiàn)，則d減1（情況5、6、7），否則d保持。對(duì)于參數(shù)p，若目標(biāo)塊位于插入點(diǎn)位置之前（p＜p0）時(shí)，失效不會(huì)使目標(biāo)塊的位置后移，p值不變（情況1、6）；NoDis時(shí)，若訪存命中位于目標(biāo)塊之前時(shí)（Hit＜p），則目標(biāo)塊的位置也不會(huì)受到影響（情況2）；除此三種情況外，目標(biāo)塊的位置都會(huì)向后移，p值加1。七種情況中，p0的影響體現(xiàn)了插入流與提升流的相互作用，表1給出了各種情況下的狀態(tài)轉(zhuǎn)移概率。

表1中，PDis表示此次訪存為首次的概率，PNoDis，Hit＜p表示訪存為非首次命中且命中位置在目標(biāo)塊p之前的概率，PNoDis，Hit≥p表示其在p 之后的概率。PDis，Hit表示訪存為首次命中的概率。為簡(jiǎn)化以上四個(gè)概率的計(jì)算，本文假設(shè)循環(huán)序列中首次與非首次訪存為均勻分布，組內(nèi)各個(gè)位置的訪存次數(shù)及命中率相同，具體四個(gè)概率的計(jì)算在此不詳細(xì)列出。

Table 1 Transition probability in each state表1 各種情況的狀態(tài)轉(zhuǎn)移概率

在提升流的狀態(tài)轉(zhuǎn)換圖中，存在一些邊界情況需要特別考慮。主要有兩種：當(dāng)p＞A時(shí)，這時(shí)表示目標(biāo)塊已經(jīng)被移出，所以目標(biāo)塊下次訪存時(shí)其必然失效，若計(jì)算其失效率，可直接返回1。當(dāng)p＋d≤A時(shí)，此時(shí)目標(biāo)塊位于p位置，后繼序列中還有d個(gè)首次訪存，最壞情況下目標(biāo)塊被后移d個(gè)位置，但由于p＋d≤A，所以目標(biāo)塊仍在組內(nèi)，此時(shí)不會(huì)失效，若計(jì)算其失效率可直接返回0，表示其肯定命中。

將狀態(tài)轉(zhuǎn)換圖及狀態(tài)轉(zhuǎn)移概率結(jié)合起來，便可以計(jì)算某個(gè)cseq（d，n）中目標(biāo)塊的失效概率。若S（d，n，p）為scseq（d，n，p）下目標(biāo)塊的失效概率，由圖1及表1所示，S（d，n，p）可采用以下遞歸函數(shù)進(jìn)行計(jì)算：

若要計(jì)算提升流中某個(gè)cseq（d，n）中目標(biāo)塊的失效率，由于該序列的第一個(gè)數(shù)據(jù)地址肯定為目標(biāo)塊且位于1位置，cseq（d，n）中目標(biāo)塊的失效率就等于scseq（d－1，n－1，1）的失效率［4］，即：

給定cseq（d，n）后，S（d－1，n－1，1）的計(jì)算過程中只有Pmiss為未知量，遞歸過程中每遞歸一步，計(jì)算中引入Pmiss的階都為一階，S（d－1，n－1，1）的最大遞歸深度為n－1，所以PP（cseq（d，n））是一個(gè)以Pmiss為變量的n－1階多項(xiàng)式［4］。

對(duì)于插入流PI（cseq（d，n））的計(jì)算，其模型推導(dǎo)過程與PP（cseq（d，n））完全相同，在此不詳細(xì)列出。

3.4 整體失效率的計(jì)算

當(dāng)獲得了每個(gè)循環(huán)序列的失效率之后，各個(gè)重用距離的命中率為：

3.5 使用迭代法求出整體失效率

在模型的第一、二步中，由CSH、HSH及h計(jì)算出了提升流分布CSHP與插入流分布CSHI；在模型的第三、四步中以CSHP、CSHI及P（i）miss為輸入，使用遞歸概率模型計(jì)算出P（i＋1）miss及h（i＋1）。而整體失效率Pmiss又可由h、CSH計(jì)算得出，所以第三、四步相當(dāng)于只求出了h（i＋1）。綜上，模型第一步到第四步相當(dāng)于以CSH、HSH及h為輸入求出了h，可由下式表示：

式（11）構(gòu)成了以h為未知量的dmax元非線性方程組，對(duì)于此類非線性方程組，有多種解法，但是這些方法需要求出F的一階偏導(dǎo)，計(jì)算復(fù)雜。在本問題中，F(xiàn)為多項(xiàng)式方程組，具有較好的求解性質(zhì)，可直接采用迭代法求解：

式（12）中，h（i）為第i次迭代求出的解。當(dāng)?shù)_(dá)到最大迭代次數(shù)或Pmiss達(dá)到以下精度要求時(shí)，則停止迭代：

式（13）中ε為精度要求，本文取ε＝10－4。模型的初始迭代解使用LRU策略下各重用距離的命中率hlru，即：

實(shí)際計(jì)算表明，模型的收斂速度很快，一般迭代三次以內(nèi)便可以達(dá)到所需精度要求。

4 模型驗(yàn)證

4.1 驗(yàn)證方法

為了對(duì)動(dòng)態(tài)插入策略模型的準(zhǔn)確度進(jìn)行驗(yàn)證，本文對(duì)全系統(tǒng)模擬器Simics的Cache模塊進(jìn)行了修改，在其中的末級(jí)Cache L2上驗(yàn)證了動(dòng)態(tài)插入策略，測(cè)試程序采用SPEC2006標(biāo)準(zhǔn)測(cè)試集。

對(duì)于Cache替換策略模型的評(píng)價(jià)，一般都采用真實(shí)失效率與預(yù)測(cè)失效率之間的差值作為評(píng)價(jià)指標(biāo)，稱為絕對(duì)誤差［4，5］。

對(duì)于同一應(yīng)用，相鄰插入點(diǎn)下插入策略的性能相差不大，可以一定的間隔選擇插入點(diǎn)位置。本文中，對(duì)于不同的組相聯(lián)度A，選擇了1、A／4、A／2、A3／4、A共五個(gè)插入點(diǎn)作為插入策略的驗(yàn)證位置。本文在8路512KB與16路1MB兩種Cache配置下對(duì)五種插入策略進(jìn)行了驗(yàn)證。

4.2 結(jié)果及誤差分析

驗(yàn)證結(jié)果表明，8路時(shí)，平均絕對(duì)誤差為1.2%，最大絕對(duì)誤差為10.9%；16路時(shí)，平均絕對(duì)誤差為3.1%，最大絕對(duì)誤差為15.6%。整體而言，當(dāng)相聯(lián)度增大時(shí)，預(yù)測(cè)誤差增大。表2為16路配置下SPEC2006各測(cè)試程序五種插入策略中預(yù)測(cè)誤差最大的情況，p0表示插入策略的插入位置。

表2中，大部分測(cè)試程序最大絕對(duì)誤差的絕對(duì)值小于3%，模型絕對(duì)誤差較大的情況一般出現(xiàn)在插入點(diǎn)位置靠后的情況。圖2為預(yù)測(cè)誤差最大的459.GemsFDTD的預(yù)測(cè)情況。從圖2中可以看出，當(dāng)插入位置為1、A／4、A／2、A3／4時(shí)，模型的預(yù)測(cè)誤差較小。當(dāng)插入點(diǎn)位置為A時(shí)，預(yù)測(cè)誤差達(dá)到15.6%，此時(shí)誤差主要出現(xiàn)在插入點(diǎn)位置后移使應(yīng)用失效率急劇上升的情況。雖然絕對(duì)誤差較大，但是模型也能很好地預(yù)測(cè)出其失效率的迅速增長，說明此插入策略性能較差，但對(duì)于指導(dǎo)插入策略的選擇已經(jīng)足夠。

Table 2 Max error of insertion policy in SPEC2006表2 SPEC2006測(cè)試集插入策略最大預(yù)測(cè)誤差表

Figure 2 Miss rate prediction of GemesFDTD in different insertion policy圖2 GemesFDTD測(cè)試程序下不同插入策略失效預(yù)測(cè)情況

表2中，誤差絕對(duì)值大于3%的預(yù)測(cè)失效率都小于實(shí)際預(yù)測(cè)失效率，且此時(shí)應(yīng)用本身的失效率也較大。對(duì)模型誤差的進(jìn)一步分析表明，誤差較大時(shí)其誤差主要集中在PP（cseq（dmax＋1，nmax＋1））上，cseq（dmax＋1，nmax＋1）表示重用距離大于dmax且長度大于nmax的序列，這部分序列重用距離較大、失效率較高。但是，模型在計(jì)算時(shí)是按重用距離為dmax＋1、長度為nmax＋1的循環(huán)序列對(duì)其進(jìn)行失效率計(jì)算，所以失效率估計(jì)會(huì)偏低。當(dāng)dmax、nmax很大時(shí)，這部分序列的數(shù)量很小，不會(huì)對(duì)模型誤差有較大的影響，但對(duì)某些應(yīng)用，其局部性較差，其CSHP（dmax＋1，nmax＋1）的數(shù)量會(huì)很大，此時(shí)這部分的影響會(huì)比較大。該問題出現(xiàn)的根本原因是dmax、nmax的取值偏小，但是dmax、nmax太大會(huì)增加計(jì)算復(fù)雜性，模型需要在精確度與計(jì)算復(fù)雜性之間進(jìn)行折衷。

5 結(jié)束語

本文提出了一個(gè)Cache插入策略模型，該模型以較簡(jiǎn)單的方法對(duì)Cache訪存數(shù)據(jù)流的行為特性、Cache插入策略的內(nèi)部作用過程進(jìn)行了有效的數(shù)學(xué)描述，可對(duì)不同配置下Cache插入策略的性能進(jìn)行較為準(zhǔn)確的預(yù)測(cè)，最后的驗(yàn)證結(jié)果表明，模型的精度較高，最大絕對(duì)誤差為15.6%，平均絕對(duì)誤差為3.1%。

本模型不僅可以直接用于Cache動(dòng)態(tài)插入、預(yù)取數(shù)據(jù)塊放置等策略的優(yōu)化，可避免單純某種插入策略的盲目性，還可加深Cache設(shè)計(jì)人員對(duì)影響Cache性能因素的把握以及指導(dǎo)Cache結(jié)構(gòu)設(shè)計(jì)的優(yōu)化。

［1］ Xie Y，Loh G H.PIPP：Promotion／insertion pseudo-partitioning of multi-core shared caches［C］∥Proc of the 36th Annual International Symposium on Computer Architecture，2009：174-183.

［2］ Jaleel A，Theobald K B，Steely S C，et al.High performance cache replacement using re-reference interval prediction（RRIP）［C］∥Proc of the 37th Annual International Symposium on Computer Architecture，2010：60-71.

［3］ Jaleel A，Hasenplaugh W，Qureshi M，et al.Adaptive insertion policies for managing shared caches［C］∥Proc of the 17th International Conference on Parallel Architectures and Compilation Techniques，2008：208-219.

［4］ Guo F，Solihin Y.An analytical model for cache replacement policy performance［C］∥Proc of the Joint International Conference on Measurement and Modeling of Computer Systems，2006：228-239.

［5］ Grund D，Reineke J.Estimating the performance of cache replacement policies［C］∥Proc of the 6th ACM／IEEE International Conference on Formal Methods and Models for Co-design，2008：101-112.

［6］ Belady L A.A study of replacement algorithms for a virtualstorage computer［J］.IBM Systems Journal，1966，5（2）：78-101.