Cache動態(tài)插入策略模型研究＊

石文強，倪曉強，金作霖，張民選

（國防科學技術大學計算機學院，湖南 長沙410073）

1 引言

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

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

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

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

2 模型定義及假設

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

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

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

（1）循環(huán)序列cseq（Circular Sequence）：一個Cache組的訪存序列中，數(shù)據(jù)塊B的本次訪存與下次訪存之間的訪存序列（包括B）稱為以B為目標塊的循環(huán)序列。若該序列長度為n，其中不同地址數(shù)目為d，則該序列可用cseq（d，n）表示。對于循環(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個不同的數(shù)據(jù)訪存，用scseq（d，n）表示。

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

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

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

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

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

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

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

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

本節(jié)對Cache的插入策略進行了建模，其中使用了以下符號定義：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 建?；静襟E

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

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

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

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

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

（1）獲取應用的CSH、HSH分布。

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

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

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

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

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

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

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

3.2 輸入訪存序列分布的計算

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

提升流分布可以認為是訪存命中的數(shù)據(jù)塊被提升至MRU位置后下次重用時的循環(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ù)塊在本次轉化為提升流的比例。若令rd表示重用距離為d的數(shù)據(jù)塊轉化為提升流的比例，則有：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 整體失效率的計算

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

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

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

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

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

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

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

4 模型驗證

4.1 驗證方法

為了對動態(tài)插入策略模型的準確度進行驗證，本文對全系統(tǒng)模擬器Simics的Cache模塊進行了修改，在其中的末級Cache L2上驗證了動態(tài)插入策略，測試程序采用SPEC2006標準測試集。

對于Cache替換策略模型的評價，一般都采用真實失效率與預測失效率之間的差值作為評價指標，稱為絕對誤差［4，5］。

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

4.2 結果及誤差分析

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

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

Table 2 Max error of insertion policy in SPEC2006表2 SPEC2006測試集插入策略最大預測誤差表

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

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

5 結束語

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

本模型不僅可以直接用于Cache動態(tài)插入、預取數(shù)據(jù)塊放置等策略的優(yōu)化，可避免單純某種插入策略的盲目性，還可加深Cache設計人員對影響Cache性能因素的把握以及指導Cache結構設計的優(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.