位置信息與替換概率相結(jié)合的多核共享Cache管理機(jī)制*

徐金波，龐征斌,2，李 琰

(1.國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長(zhǎng)沙 410073；2.國(guó)防科技大學(xué) 并行與分布式計(jì)算重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙 410073)

?

位置信息與替換概率相結(jié)合的多核共享Cache管理機(jī)制*

徐金波1，龐征斌1,2，李 琰1

(1.國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長(zhǎng)沙 410073；2.國(guó)防科技大學(xué) 并行與分布式計(jì)算重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙 410073)

多核系統(tǒng)中末級(jí)Cache是影響整體性能的關(guān)鍵。為了提出一種細(xì)粒度、低延遲、低代價(jià)的末級(jí)共享Cache資源管理機(jī)制，將系統(tǒng)性能目標(biāo)轉(zhuǎn)換為每個(gè)內(nèi)核當(dāng)前占用Cache資源的替換概率，以決定每個(gè)內(nèi)核能夠提供的被替換資源的數(shù)量；對(duì)某個(gè)需要增加Cache資源的內(nèi)核，從可提供被替換資源的候選內(nèi)核中選出距離較近且替換概率較高的一個(gè)內(nèi)核，并以Cache塊為粒度進(jìn)行替換，從而實(shí)現(xiàn)Cache資源在不同內(nèi)核間的動(dòng)態(tài)劃分。與傳統(tǒng)以相聯(lián)度為粒度的粗粒度替換機(jī)制相比，以Cache塊為單位的替換機(jī)制具有更細(xì)的替換粒度，靈活性更高。另外，通過(guò)將位置信息和替換概率結(jié)合，保證了Cache資源與相應(yīng)內(nèi)核在物理布局上的收斂，降低了訪問(wèn)延遲。同時(shí)，所提出的方法只需要增加極少的硬件代價(jià)。實(shí)驗(yàn)結(jié)果表明，根據(jù)實(shí)驗(yàn)場(chǎng)景和對(duì)比對(duì)象的不同，所提方法與其他已有研究成果相比，可以實(shí)現(xiàn)從6.8%到22.7%的性能提升。

多核系統(tǒng)；末級(jí)Cache；動(dòng)態(tài)劃分；替換策略

細(xì)粒度、低延遲、低代價(jià)是多核系統(tǒng)中末級(jí)共享Cache資源管理機(jī)制多年來(lái)的研究重點(diǎn)[1-9]。例如，Zhang等基于page coloring進(jìn)行Cache資源管理[1]，但該方法在應(yīng)用程序獲得存儲(chǔ)資源時(shí)靈活性不足，而且在進(jìn)行動(dòng)態(tài)Cache劃分時(shí)需要進(jìn)行大量的頁(yè)拷貝(page copying)，實(shí)現(xiàn)代價(jià)較大；劉勝等通過(guò)在Cache劃分時(shí)采取一些可配置策略進(jìn)行優(yōu)化[2]，但配置靈活性有待提高；El-Moursy等提出了V-set Cache[3]，但Cache劃分粒度仍不夠精細(xì)；Chen等通過(guò)硬件卸載的方式進(jìn)行Cache劃分[4]，性能優(yōu)于操作系統(tǒng)(Operating System, OS)層的劃分策略，但該方法仍是way-partitioning，屬于粗粒度劃分。

已有的Cache劃分策略可分為粗粒度劃分[4,6]和細(xì)粒度劃分[7,10]兩類。例如，way-partitioning劃分策略通過(guò)為每個(gè)內(nèi)核各分配一部分相聯(lián)度來(lái)實(shí)現(xiàn)劃分，屬粗粒度劃分，雖易于實(shí)現(xiàn)，但其劃分粒度反比于相聯(lián)度，當(dāng)內(nèi)核數(shù)與相聯(lián)度較接近時(shí)，系統(tǒng)性能會(huì)急劇惡化。Vantage[7]策略屬于細(xì)粒度劃分，但只能對(duì)大部分區(qū)域而不是全部Cache資源進(jìn)行資源管理，且對(duì)Cache基礎(chǔ)框架改動(dòng)較大，并對(duì)替換算法提出了較高的要求，因此實(shí)現(xiàn)代價(jià)偏高。為了使用更低代價(jià)實(shí)現(xiàn)細(xì)粒度Cache劃分，Manikantan等提出了PriSM策略[10]，通過(guò)動(dòng)態(tài)計(jì)算Cache資源的替換概率實(shí)現(xiàn)以Cache塊為單位的細(xì)粒度劃分，且硬件代價(jià)較低，但該方法沒(méi)有充分考慮對(duì)Cache訪問(wèn)延遲的優(yōu)化，可能會(huì)出現(xiàn)內(nèi)核距離待訪問(wèn)的Cache資源較遠(yuǎn)從而導(dǎo)致延遲較大的問(wèn)題。

本文提出一種基于位置信息與替換概率的多核共享Cache管理機(jī)制，以期滿足細(xì)粒度、低延遲、低代價(jià)的需求，在綜合性能上優(yōu)于已有研究成果。該方法首先將系統(tǒng)性能目標(biāo)轉(zhuǎn)換為每個(gè)內(nèi)核當(dāng)前占用Cache資源的替換概率，以決定每個(gè)內(nèi)核能夠提供的Victim Line數(shù)量；然后，對(duì)某個(gè)需要增加Cache的內(nèi)核，從可提供Victim Line的候選內(nèi)核中選出距離較近且替換概率較高的一個(gè)內(nèi)核，并以Cache塊為粒度進(jìn)行替換，實(shí)現(xiàn)Cache在不同內(nèi)核間的動(dòng)態(tài)劃分。與傳統(tǒng)way-partitioning等粗粒度替換機(jī)制相比，以Cache塊為單位的替換機(jī)制具有更細(xì)的替換粒度，靈活性更高。另外，通過(guò)將位置信息和替換概率相結(jié)合，保證了Cache資源與相應(yīng)內(nèi)核在物理布局上的收斂，降低了訪問(wèn)延遲。同時(shí)，所提出的方法只需增加極少的硬件代價(jià)。模擬器實(shí)驗(yàn)結(jié)果表明，所提出的方法與已有研究成果相比，根據(jù)實(shí)驗(yàn)場(chǎng)景、性能衡量標(biāo)準(zhǔn)和對(duì)比對(duì)象的不同，可實(shí)現(xiàn)從6.8%到22.7%的性能提升。本文工作與最近最少使用算法(Least Recently Used, LRU)相比可以在32核片上多處理器(Chip Multi-Processor, CMP)上實(shí)現(xiàn)約21%的性能提升，與PriSM相比在整體性能上可提高約6.8%。

1 動(dòng)機(jī)

粗粒度劃分策略對(duì)Cache資源的調(diào)整幅度過(guò)大，理論上的最優(yōu)劃分邊界很難與粗粒度劃分的劃分邊界重合，因此有必要研究使用更細(xì)粒度的Cache劃分策略來(lái)提升性能的可能性。way-partitioning方法對(duì)所有Cache組統(tǒng)一以一個(gè)相聯(lián)度為粒度進(jìn)行調(diào)整，如16路組相聯(lián)Cache每次調(diào)整會(huì)將6.25%的Cache從一個(gè)內(nèi)核重新分配給另一個(gè)內(nèi)核。類似地，64路和256路組相聯(lián)Cache的調(diào)整幅度分別是1.6%和0.39%的Cache資源。已有研究工作發(fā)現(xiàn)更細(xì)粒度的Cache劃分策略有利于提高系統(tǒng)性能[11]，但是通過(guò)提高相聯(lián)度所實(shí)現(xiàn)的細(xì)粒度劃分策略是以非常復(fù)雜的控制邏輯和過(guò)多的硬件開(kāi)銷為代價(jià)的，因此需要考慮實(shí)現(xiàn)更簡(jiǎn)單、粒度更精細(xì)的Cache劃分。以Cache塊為單位的Cache劃分可以實(shí)現(xiàn)比高相聯(lián)度方法更精細(xì)的調(diào)整粒度。當(dāng)Cache塊總數(shù)為N時(shí)，每個(gè)內(nèi)核可以以1/N的調(diào)整幅度對(duì)Cache資源進(jìn)行增減。

以Cache塊為粒度進(jìn)行劃分需要考慮的關(guān)鍵問(wèn)題是資源分配和劃分機(jī)制的設(shè)計(jì)，只有能夠動(dòng)態(tài)及時(shí)地對(duì)Cache資源進(jìn)行科學(xué)分配和劃分，才能使得理論上的最優(yōu)劃分邊界盡可能地與實(shí)際劃分邊界重合，從而充分發(fā)揮所有Cache資源的作用。Cache分配機(jī)制要保證每個(gè)Cache塊都得到管理并被分配給其中一個(gè)內(nèi)核，盡量避免出現(xiàn)Vantage[7]方法中“unmanaged”區(qū)域內(nèi)Cache塊不屬于任何一個(gè)內(nèi)核的情況。基于這種分配原則，以Cache塊為粒度的Cache劃分機(jī)制本質(zhì)上是將Cache塊在不同的內(nèi)核之間進(jìn)行“轉(zhuǎn)移”的問(wèn)題。根據(jù)每個(gè)內(nèi)核的負(fù)載情況以及系統(tǒng)希望達(dá)到的性能目標(biāo)，如果能夠算出每個(gè)內(nèi)核除滿足自身需求外能夠貢獻(xiàn)給別的內(nèi)核的Cache資源份額，那么對(duì)于某個(gè)需要增加Cache的內(nèi)核，就可以從具有空閑資源的候選內(nèi)核中選擇一個(gè)內(nèi)核為其提供Cache塊。因此，每個(gè)內(nèi)核能夠貢獻(xiàn)給別的內(nèi)核的Cache資源份額可以反映該內(nèi)核中的Cache被替換的可能性，即替換概率。不同內(nèi)核替換概率的差異可以作為Victim Line的選取依據(jù)。另一方面，Victim Line的選取還需要考慮內(nèi)核到Cache塊的訪問(wèn)延遲問(wèn)題，當(dāng)內(nèi)核到不同候選Victim Line的訪問(wèn)延遲不同時(shí)，顯然應(yīng)該選擇較近的Cache塊。因此，位置信息也可作為Victim Line的選取依據(jù)。

基于以上動(dòng)機(jī)，所提出的多核共享Cache管理機(jī)制既考慮了替換概率，又考慮了內(nèi)核與Cache之間的位置信息，希望在實(shí)現(xiàn)細(xì)粒度劃分的同時(shí)，也能夠保證內(nèi)核對(duì)Cache的較低的訪問(wèn)延遲。

2 基于位置信息與替換概率的多核共享Cache管理機(jī)制

為便于說(shuō)明，使用N表示所有Cache塊的數(shù)量。W表示對(duì)Cache替換概率進(jìn)行重新計(jì)算的時(shí)間間隔，通常采用發(fā)生特定次數(shù)的Cache失效的時(shí)間長(zhǎng)度來(lái)衡量。當(dāng)某次重新計(jì)算的時(shí)間點(diǎn)到來(lái)時(shí)，每個(gè)內(nèi)核所期望的Cache資源百分比將被重新計(jì)算。Ci是每段時(shí)間間隔開(kāi)始時(shí)Corei所占用的Cache資源百分比。Mi則是每段時(shí)間間隔內(nèi)Corei所發(fā)生的失效次數(shù)占所有失效次數(shù)的百分比。Ti為Corei為了達(dá)到一定的性能目標(biāo)所期望占有的Cache資源百分比。τi為重新劃分之后Corei實(shí)際所能夠占有的Cache資源百分比。Ei為Corei所占有的Cache塊被替換出去的概率。本文假定程序數(shù)量與內(nèi)核數(shù)量相同，且不存在程序遷移。

2.1 替換概率的計(jì)算

本文工作的基礎(chǔ)之一是對(duì)每個(gè)內(nèi)核所占用的Cache資源計(jì)算出一個(gè)替換概率。替換概率每隔一定時(shí)間間隔重新計(jì)算一次，計(jì)算過(guò)程參考文獻(xiàn)[10]。在以失效次數(shù)W衡量的時(shí)間間隔內(nèi)，Corei所導(dǎo)致的失效次數(shù)百分比為Mi，因此失效次數(shù)為Mi×W。假設(shè)在時(shí)間間隔內(nèi)Corei的Cache資源沒(méi)有被替換出去，那么Corei所占用的Cache資源將會(huì)從Ci增加到[Ci+(Mi×W/N)]。如果將替換概率Ei考慮進(jìn)去，該時(shí)間間隔內(nèi)Ei×W個(gè)Cache塊將會(huì)被替換出去，因此調(diào)整之后Corei實(shí)際占有的Cache資源百分比將會(huì)變?yōu)棣觟=Ci+[(Mi-Ei)×W/N]。如果要達(dá)到期望的性能目標(biāo)，就需要使得τi盡快地接近期望值Ti。當(dāng)在單個(gè)時(shí)間間隔內(nèi)τi無(wú)法達(dá)到Ti時(shí)，如果CiTi，則將Ei設(shè)為1。反之，如果在單個(gè)時(shí)間間隔內(nèi)τi可以達(dá)到Ti，Ei可以通過(guò)公式Ti=τi=Ci+[(Mi-Ei)×W/N]計(jì)算得到。綜上，Ei的計(jì)算公式如式(1)所示。

(1)

從式(1)中可以看出，計(jì)算Ei首先需要確定Ci，Mi和Ti。Ci和Mi可以通過(guò)為每個(gè)內(nèi)核設(shè)置相應(yīng)的計(jì)數(shù)器分別對(duì)所占用的Cache塊數(shù)量和W時(shí)間間隔內(nèi)的失效次數(shù)進(jìn)行統(tǒng)計(jì)來(lái)得到。Ti的計(jì)算則需要與系統(tǒng)所期望達(dá)到的性能目標(biāo)進(jìn)行關(guān)聯(lián)，本文主要研究命中率最大化的性能目標(biāo)。命中率最大化的性能目標(biāo)試圖為更容易獲得較高命中率的內(nèi)核分配更多的Cache資源。通常，通過(guò)假設(shè)將所有Cache資源都分配給某個(gè)內(nèi)核Corei時(shí)，該內(nèi)核所能夠得到的命中率StandAloneHits[i]與所有內(nèi)核共享Cache時(shí)Corei所得到的Cache命中率SharedHits[i]之間的差異來(lái)衡量該內(nèi)核對(duì)Cache資源的依賴程度。在每個(gè)時(shí)間間隔內(nèi)，StandAloneHits[i]與SharedHits[i]采用不同的實(shí)現(xiàn)機(jī)制并行獲得：在每個(gè)內(nèi)核中，使用計(jì)數(shù)器對(duì)SharedHits[i]進(jìn)行記錄；而對(duì)于StandAloneHits[i]，則使用文獻(xiàn)[6]中的方法進(jìn)行估計(jì)，具體處理過(guò)程是使用輔助標(biāo)簽?zāi)夸?Auxiliary Tag Directory, ATD)和命中率計(jì)數(shù)器對(duì)Cache資源的利用情況進(jìn)行分析，并通過(guò)將命中率進(jìn)行累加的方法得到StandAloneHits[i]。對(duì)Cache資源依賴程度高的內(nèi)核將期望得到更多的Cache資源，基于這種相關(guān)性，可以計(jì)算出每個(gè)內(nèi)核i所期望得到的Cache資源百分比Ti，進(jìn)而計(jì)算出每個(gè)內(nèi)核的替換概率Ei。算法描述如圖1所示。

圖1 Ti和Ei的計(jì)算Fig.1 Calculation of Ti and Ei

對(duì)于某個(gè)需要增加Cache資源的內(nèi)核，就可以根據(jù)其他內(nèi)核的替換概率確定一個(gè)Victim Core，該Victim Core從它所擁有的Cache資源中選取部分Cache塊，將數(shù)據(jù)進(jìn)行替換，貢獻(xiàn)給需要增加Cache資源的內(nèi)核。

Victim Core的選擇以及Victim Core內(nèi)Cache塊的選擇是接下來(lái)需要考慮的另一個(gè)關(guān)鍵問(wèn)題。對(duì)于Victim Core的選擇，可以選擇替換概率最高的內(nèi)核或者從替換概率分布中隨機(jī)選取內(nèi)核。對(duì)于已選定Victim Core內(nèi)Cache塊的選擇，可以采用各種已有研究中所提出的Cache替換策略進(jìn)行選擇，如LRU，動(dòng)態(tài)插入策略(Dynamic Insertion Policy, DIP)[12]等。但是上述方法沒(méi)有考慮對(duì)訪問(wèn)延遲的優(yōu)化，當(dāng)被選中的Cache塊與內(nèi)核之間距離較遠(yuǎn)時(shí)，較大的訪問(wèn)延遲導(dǎo)致Cache效率降低。本文在Victim Core以及Cache塊的選擇過(guò)程中將內(nèi)核和Cache的相對(duì)位置信息與替換概率融合起來(lái)，目的是實(shí)現(xiàn)訪問(wèn)延遲的優(yōu)化。

2.2 位置信息的融合

圖2 采用2D Mesh網(wǎng)絡(luò)的瓦片結(jié)構(gòu)多核處理器Fig.2 Tile-structured multi-core processor with 2D mesh network

多核處理器中內(nèi)核與Cache體的布局方式是多種多樣的，如Cache居中方式、內(nèi)核居中方式、分組布局方式、瓦片結(jié)構(gòu)布局方式等。限于篇幅，本文僅以應(yīng)用較廣泛的瓦片結(jié)構(gòu)為基礎(chǔ)進(jìn)行闡述。瓦片結(jié)構(gòu)多核處理器基本結(jié)構(gòu)示意圖如圖2所示。每個(gè)瓦片由一個(gè)(或多個(gè))內(nèi)核、私有L1指令和數(shù)據(jù)Cache、共享L2 Cache、用于維護(hù)Cache一致性的目錄結(jié)構(gòu)、瓦片間互聯(lián)的路由部件組成。L2 Cache雖然分布布局在每個(gè)瓦片中，但是這些Cache由所有瓦片中的內(nèi)核共享，某個(gè)瓦片內(nèi)的內(nèi)核可能會(huì)對(duì)其他瓦片內(nèi)的L2 Cache進(jìn)行訪問(wèn)。顯然，內(nèi)核到Cache的網(wǎng)絡(luò)距離越遠(yuǎn)，訪問(wèn)延遲越大。因此，為了盡量減少Cache訪問(wèn)延遲，在進(jìn)行Cache劃分時(shí)需要盡量使得內(nèi)核與相應(yīng)Cache資源的相對(duì)位置較近。

基于替換概率的細(xì)粒度Cache劃分策略基本思想是從其他替換概率非零的內(nèi)核擁有的Cache資源中選擇合適的Cache塊，將其替換為當(dāng)前內(nèi)核需要的數(shù)據(jù)，實(shí)現(xiàn)Cache塊從其他內(nèi)核向當(dāng)前內(nèi)核的轉(zhuǎn)移。當(dāng)內(nèi)核訪問(wèn)Cache命中時(shí)，工作模式與傳統(tǒng)Cache一樣；當(dāng)內(nèi)核訪問(wèn)Cache失效時(shí)，通過(guò)兩步操作實(shí)現(xiàn)替換，第一步是選擇合適的Victim Core，第二步是從Victim Core擁有的Cache資源中選擇合適的Victim Line。

將內(nèi)核和Cache的相對(duì)位置信息加入到基于替換概率的細(xì)粒度Cache劃分策略設(shè)計(jì)思想中，以優(yōu)化內(nèi)核對(duì)共享Cache的訪問(wèn)延遲。為了實(shí)現(xiàn)這種方法，在每個(gè)瓦片內(nèi)設(shè)置一個(gè)查找表E-Table，查找表可采用寄存器隊(duì)列方式進(jìn)行組織，隊(duì)列中每個(gè)寄存器項(xiàng)設(shè)兩個(gè)字段，分別保存當(dāng)前瓦片內(nèi)共享Cache所屬的所有內(nèi)核的ID以及這些內(nèi)核的替換概率。對(duì)于位于第i行第j列瓦片Tile(i,j)中的內(nèi)核Core(i,j)，如果該內(nèi)核需要增加Cache，首先根據(jù)當(dāng)前瓦片的E-Table內(nèi)的信息選出其中一個(gè)替換概率非零的內(nèi)核作為Victim Core，選擇時(shí)可采用隨機(jī)原則或者選擇替換概率最大的內(nèi)核。然后，對(duì)于被選中的Victim Core，從該Victim Core所占有的當(dāng)前瓦片內(nèi)的Cache資源中選擇一個(gè)Cache塊進(jìn)行替換，替換策略可以使用傳統(tǒng)Cache中普遍使用的任何一種替換策略。如果從當(dāng)前瓦片E-Table中可以查到的內(nèi)核中至少有一個(gè)可以提供可替換的Victim Line，就可以將該Cache塊通過(guò)替換操作從該Victim Core轉(zhuǎn)移給當(dāng)前瓦片的內(nèi)核；否則，如果在當(dāng)前瓦片內(nèi)無(wú)法找到可替換的Cache塊，就考慮擴(kuò)大范圍，從該瓦片Tile(i,j)周圍的其他瓦片Tile(i±1,j±1)的E-Table中進(jìn)行查找，當(dāng)找到某個(gè)內(nèi)核的替換概率非零，且存在該內(nèi)核的一個(gè)Cache塊可以替換為Core(i,j)的Cache數(shù)據(jù)時(shí)，就可以實(shí)現(xiàn)該Victim Core向Core(i,j)的Cache塊轉(zhuǎn)移。圖3給出了基于位置信息和替換概率的多核共享Cache劃分策略示例，當(dāng)Tile(i,j)中的Core(i,j)發(fā)生訪問(wèn)Cache失效并需要增加Cache時(shí)，通過(guò)查找E-Table發(fā)現(xiàn)當(dāng)前瓦片內(nèi)還有Core(i-1,j)，Core(i-1,j+1)，Core(i,j+1)的Cache資源，且替換概率均非零，通過(guò)隨機(jī)方式從中選擇一個(gè)Victim Core(假定為Core(i,j+1))，然后使用替換策略(如DIP[12])從Core(i,j+1)在Tile(i,j)中的Cache中選擇Victim Line；如果無(wú)法為失效的Cache組找到可替換的Cache塊，則重新選擇Victim Core和Victim Line；如果Core(i-1,j)，Core(i-1,j+1)，Core(i,j+1)在Tile(i,j)中的Cache都無(wú)法滿足需求，則從Tile(i,j)周圍的8個(gè)Tile中選擇，直到找到可替換的Cache塊。這種方法能夠盡量保證Cache資源與相應(yīng)內(nèi)核之間在物理布局上的收斂，使每個(gè)內(nèi)核所訪問(wèn)的Cache資源都位于當(dāng)前瓦片及其周圍相鄰的瓦片中，實(shí)驗(yàn)數(shù)據(jù)也驗(yàn)證了這種局部性。相應(yīng)地，正是由于這種局部性，也保證了Core(i,j)在Tile(i±1,j±1)所組成的瓦片組中一般都可找到可替換的Cache，在較小的Cache劃分探索空間內(nèi)實(shí)現(xiàn)了較低的訪問(wèn)延遲。

圖3 本文工作的硬件結(jié)構(gòu)設(shè)計(jì)Fig.3 Hardware structure design of the proposal

本文提出的Cache劃分策略僅需要增加少量硬件代價(jià)。所有Cache訪問(wèn)都需要在Tag信息中記錄進(jìn)行此次訪問(wèn)的內(nèi)核ID，以對(duì)Cache資源占用情況進(jìn)行跟蹤。由于其他相關(guān)工作中的Cache劃分策略也都需要這一信息，因此這一硬件代價(jià)不屬于本文工作的額外代價(jià)。替換概率的計(jì)算過(guò)程僅需要幾個(gè)計(jì)數(shù)器對(duì)Ci和Mi進(jìn)行統(tǒng)計(jì)，且這些計(jì)數(shù)器在傳統(tǒng)Cache設(shè)計(jì)中通常是已有的[13]。另外，只要N和W是2的冪，并將圖1中的TotalProfit舍入為2的冪，Ti和Ei的計(jì)算就可通過(guò)簡(jiǎn)單的整數(shù)加法和移位操作實(shí)現(xiàn)。當(dāng)核數(shù)為4時(shí)，圖1中的算術(shù)操作個(gè)數(shù)為20，當(dāng)核數(shù)為32時(shí)，算術(shù)操作個(gè)數(shù)為160。另外需要增加一部分存儲(chǔ)空間用來(lái)保存E-Table，每個(gè)E-Table表項(xiàng)保存某個(gè)內(nèi)核的ID以及對(duì)應(yīng)的替換概率。為降低硬件開(kāi)銷，本文使用整數(shù)來(lái)記錄替換概率的近似值。實(shí)驗(yàn)表明，使用6位或8位整數(shù)記錄替換概率已經(jīng)可以達(dá)到與使用浮點(diǎn)數(shù)進(jìn)行記錄時(shí)幾乎相同的性能。

3 實(shí)驗(yàn)結(jié)果

與PriSM相比，本文對(duì)局部性能進(jìn)行了優(yōu)化。為了驗(yàn)證這種優(yōu)化對(duì)性能的影響，本文使用M5模擬器[14]對(duì)所提出的Cache管理策略進(jìn)行模擬，并與PriSM[10]，Vantage[7]，基于利用率的Cache劃分(Utility-based Cache Partitioning, UCP)[6]，提升/插入偽劃分方法(Promotion/Insertion Pseudo Partitioning, PIPP)[9]等方法進(jìn)行比較。模擬器的參數(shù)配置如表1所示，其中L2 Cache為末級(jí)Cache，采用LRU替換策略，為4核和8核系統(tǒng)配置16路組相聯(lián)4MB的L2 Cache，為16核系統(tǒng)配置32路組相聯(lián)8MB的L2 Cache，為32核系統(tǒng)配置64路組相聯(lián)16MB的L2 Cache。為了更好地與已有相關(guān)工作進(jìn)行比較，本文的實(shí)驗(yàn)方法盡量與這些相關(guān)工作保持一致[6-7,9-10]，共采用了71個(gè)測(cè)試程序進(jìn)行測(cè)試，包含21個(gè)4核程序、16個(gè)8核程序、20個(gè)16核程序、14個(gè)32核程序。這些測(cè)試程序取自SPEC CPU2000和SPEC CPU2006，首先將SPEC CPU2000和SPEC CPU2006中的程序按照類似于文獻(xiàn)[15]中的方法分為4類：insensitive，cache-friendly，cache-fitting，thrashing/streaming；然后從每一類程序組中同時(shí)隨機(jī)選取1/2/4/8個(gè)測(cè)試程序進(jìn)行混合，形成前述的71個(gè)4/8/16/32核測(cè)試程序。每個(gè)測(cè)試程序執(zhí)行200M個(gè)時(shí)鐘周期。本文使用平均歸一化周轉(zhuǎn)時(shí)間(Average Normalized Turnaround Time， ANTT)[11]作為性能測(cè)試指標(biāo)：

(2)

表1 M5模擬器參數(shù)配置

圖4(a)給出了本文與PriSM，UCP，PIPP的性能比較結(jié)果，采用歸一化到LRU的ANTT作為性能指標(biāo)。實(shí)驗(yàn)結(jié)果表明，對(duì)于4/8/16/32核CPU，本文與LRU相比可以分別得到19%，16%，21%，15%的性能提升；與UCP，PIPP相比在核數(shù)較多的情況下也得到了較明顯的性能提升，與已有工作中性能較好的PriSM相比，本文在16核和32核的情況下也得到了4.9%和6.8%的性能提升。

(a) 平均結(jié)果 (a) Mean results

(b) 4核詳細(xì)結(jié)果 (b) Results of 4-core CMP

(c) 32核詳細(xì)結(jié)果 (c) Results of 32-core CMP圖4 本文與PriSM，UCP，PIPP的性能比較Fig.4 Performance comparison among the proposed work and PriSM, UCP, PIPP

本文能夠?qū)崿F(xiàn)性能提升的主要原因是通過(guò)更細(xì)粒度的Cache資源劃分使得不同內(nèi)核之間的實(shí)際劃分邊界可以與理論上的最優(yōu)劃分邊界盡可能地重合，從而充分發(fā)揮所有Cache資源的作用；同時(shí)，由于在Cache劃分策略中融合了內(nèi)核與Cache資源的相對(duì)位置信息，優(yōu)化了內(nèi)核對(duì)所擁有Cache資源的訪問(wèn)延遲，提高了IPC，從而提高了系統(tǒng)性能。這種方法在內(nèi)核數(shù)較多的情況下對(duì)系統(tǒng)性能提升的效果更為明顯，這是由于本文中的Cache劃分探索空間在內(nèi)核越多的系統(tǒng)中所占的比重越小，Cache資源距離相應(yīng)內(nèi)核的物理位置收斂性越好，延遲優(yōu)化的效果也就越好。圖4(b)和圖4(c)分別給出了本文與PriSM，UCP，PIPP使用4核和32核測(cè)試程序進(jìn)行測(cè)試時(shí)的詳細(xì)性能比較結(jié)果。結(jié)果表明，本文可以在多數(shù)程序中獲得優(yōu)于其他相關(guān)工作的性能，有些測(cè)試程序性能提升明顯(如Q7，Q11，T5，T7，T8等)。

除了性能測(cè)試，本文也對(duì)Victim Line定位的迭代次數(shù)進(jìn)行了分析。對(duì)Victim Line進(jìn)行選擇和定位的迭代次數(shù)會(huì)直接影響Cache劃分的效果和效率。如果Victim Line可以在當(dāng)前瓦片內(nèi)定位成功，就可以較快地完成Cache塊轉(zhuǎn)移；反之，如果Victim Line在當(dāng)前瓦片內(nèi)的候選Victim Core中無(wú)法找到可替換的Cache塊，則繼續(xù)到其他瓦片中進(jìn)行選擇，這將影響Cache劃分的效率，并導(dǎo)致較高的Cache訪問(wèn)延遲。本文通過(guò)為每個(gè)瓦片的E-Table增加計(jì)數(shù)器來(lái)統(tǒng)計(jì)每個(gè)E-Table表項(xiàng)被訪問(wèn)的次數(shù)，然后與相應(yīng)的失效次數(shù)進(jìn)行比較，使用E-Table訪問(wèn)次數(shù)與失效次數(shù)的比值R來(lái)衡量Victim Line定位迭代次數(shù)的多少。圖5給出了所提方法在4核、8核、16核、32核處理器上的迭代次數(shù)衡量參數(shù)R的結(jié)果，圖中縱坐標(biāo)為所有內(nèi)核上多個(gè)時(shí)間間隔內(nèi)R值的平均值。結(jié)果表明，隨著核數(shù)的增加，Victim Line定位迭代次數(shù)略有增加，雖然增加了少量復(fù)雜性，但是由于本文方法能夠?qū)ache訪問(wèn)約束在距離內(nèi)核較近的范圍內(nèi)，優(yōu)化了訪問(wèn)延遲，因此可以獲得優(yōu)于其他相關(guān)工作的整體性能，具有較大的實(shí)用性。

(a) 4核(a) 4-core (b) 8核(b) 8-core

(c) 16核(c) 16-core (d) 32核(d) 32-core圖5 Victim Line定位迭代次數(shù)分析Fig.5 Iteration analysis of locating victim lines

4 結(jié)論

本文提出了一種基于位置信息與替換概率的多核共享Cache管理機(jī)制，實(shí)現(xiàn)了細(xì)粒度、低延遲、低代價(jià)的末級(jí)共享Cache劃分，在綜合性能上優(yōu)于已有研究成果。通過(guò)將系統(tǒng)的性能目標(biāo)轉(zhuǎn)換為每個(gè)內(nèi)核當(dāng)前所占用的Cache資源的替換概率，并基于替換概率分布以Cache塊為粒度進(jìn)行實(shí)時(shí)替換，實(shí)現(xiàn)了Cache資源在不同內(nèi)核之間的細(xì)粒度劃分。另外，通過(guò)將位置信息和替換概率相結(jié)合，保證了Cache資源與相應(yīng)內(nèi)核之間的物理布局上的收斂，有效降低了訪問(wèn)延遲。同時(shí)，所提方法只需增加極少的硬件代價(jià)。通過(guò)實(shí)驗(yàn)驗(yàn)證了所提出的方法與其他已有研究成果相比具有更高的整體性能。

References)

[1] Zhang L D, Liu Y, Wang R, et al. Light-weight dynamic partitioning for last-level Cache of multicore processor on real system [J]. Journal of Supercomputing, 2014, 69(2): 547-560.

[2] 劉勝, 陳海燕, 葛磊磊, 等. 面向訪問(wèn)模式的多核末級(jí)Cache優(yōu)化方法 [J]. 國(guó)防科技大學(xué)學(xué)報(bào), 2015, 37(2): 79-85.

LIU Sheng, CHEN Haiyan, GE Leilei, et al. Optimization method for multi-core last level Cache considering the memory access modes [J]. Journal of National University of Defense Technology, 2015, 37(2): 79-85. (in Chinese)

[3] El-Moursy A A, Sibai F N. V-set Cache: an efficient adaptive shared Cache for multi-core processors [J]. Journal of Circuits, Systems and Computers, 2014, 23(7): 815-822.

[4] Chen G, Hu B, Huang K, et al. Shared L2 Cache management in multicore real-time system [C]//Proceedings of IEEE 22nd International Symposium on Field-Programmable Custom Computing Machines(FCCM), 2014: 170.

[5] Tang Y X, Wu J M, Chen G L, et al. A utility based Cache optimization mechanism for multi-thread workloads [J]. Journal of Computer Research and Development, 2013, 50(1): 170-180.

[6] Qureshi M K, Patt Y N. Utility-based Cache partitioning: a low-overhead, high-performance, runtime mechanism to partition shared Caches [C]//Proceedings of the 39th Annual IEEE/ACM International Symposium on Micro-architecture, 2006: 423-432.

[7] Sanchez D, Kozyrakis C. Vantage: scalable and efficient fine-grain Cache partitioning [C]//Proceedings of the 38th Annual International Symposium on Computer Architecture, 2011: 57-68.

[8] Zhu D, Chen L Z, Yue S Y, et al. Balancing on-chip network latency in multi-application mapping for chip-multiprocessors [C]// Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium, 2014: 872-881.

[9] Xie Y J, Loh G H. PIPP: promotion/insertion pseudo partitioning of multi-core shared Caches [C]//Proceedings of the 36th Annual International Symposium on Computer Architecture, 2009: 174-183.

[10] Manikantan R, Rajan K, Govindarajan R. Probabilistic shared cache management (PriSM) [C]//Proceedings of the 39th Annual International Symposium on Computer Architecture, 2012: 428-439.

[11] Eyerman S, Eeckhout L. System-level performance metrics for multi-program workloads [J].IEEE Micro, 2008, 28(3): 42-53.

[12] Qureshi M K, Jaleel A, Patt Y N, et al. Adaptive insertion policies for high performance caching [C]// Proceedings of the 34th Annual International Symposium on Computer Architecture, 2007: 381-391.

[13] Eyerman S, Eeckhout L, Karkhanis T, et al. A performance counter architecture for computing accurate CPI components [C]//Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, 2006: 175-184.

[14] Binkert N L, Dreslinski R G, Hsu L R, et al. The M5 simulator: modeling networked systems [J]. IEEE Micro, 2006, 26(4): 52-60.

[15] Jaleel A, Hasenplaugh W, Qureshi M, et al. Adaptive insertion policies for managing shared Caches[C]//Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, 2008: 208-219.

Shared Cache management scheme with location information and eviction probability in multi-core system

XU Jinbo1, PANG Zhengbin1,2, LI Yan1

(1. College of Computer, National University of Defense Technology, Changsha 410073, China；2. Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China)

LLC (last level Cache) plays an important role in multi-core systems. A shared LLC management scheme with fine granularity, low latency and simple hardware complexity was proposed. The performance goal was translated into eviction probabilities of each core. Then, a victim core, which was near the current core and had higher eviction probability was chosen to provide the victim block for replacement. In this way, LLC was dynamically partitioned among all cores at finer granularity of Cache blocks. This proposal is more flexible than traditional way-partitioning scheme. In addition, the combination of location information and eviction probability improves the locality between Cache resources and the corresponding cores, which can reduce the Cache access latency. The proposed scheme requires only little additional hardware changes to traditional Cache structure. Results on M5 simulator suggest that the performance can improve from 6.8% to 22.7% when comparing with the related works.

multi-core system; last-level Cache; dynamic partitioning; replacement policy

10.11887/j.cn.201605006

http://journal.nudt.edu.cn

2015-11-19

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202126)；國(guó)家863計(jì)劃資助項(xiàng)目(2012AA01A301，2013AA01A208)；國(guó)家部委基金資助項(xiàng)目(2011CB309705-1)

徐金波(1981—)，男，山東高唐人，助理研究員，博士，E-mail：xujinbo@nudt.edu.cn

TP391.41

A

1001-2486(2016)05-032-07