CMP中Cache私有方式下副本容量的動態(tài)控制

摘要：CMP中二級Cache多采用分布式結(jié)構(gòu)，其中有兩種基本管理方式：共享方式和私有方式。共享方式能最大程度利用二級Cache容量空間但卻有高的平均訪問延遲；私有方式能提供低訪問延遲，但由于數(shù)據(jù)塊副本的存在減少了Cache有效容量，因而增加了Cache缺失率。本文提出了基于私有方式的副本動態(tài)控制策略，能根據(jù)實際應用程序的執(zhí)行程序情況動態(tài)控制副本數(shù)據(jù)塊的數(shù)量，從而提高二級Cache性能。

關鍵詞：Cache；副本；動態(tài)控制

中圖分類號：TP311.52 文獻標識碼：A 文章編號：1007-9599 (2012) 10-0000-02

一、引言

隨著開發(fā)指令級并行的空間正在減少，再加上對功耗關注程度的增加，單處理器發(fā)展的速度日漸緩慢，片上多處理器成為時代的主流。片上多處理器與存儲器之間性能差距依然較大，因而有效的組織和管理Cache系統(tǒng)至關重要。目前片上多處理器中最外層cache（大多為二級Cache）有兩種組織方式：私有和共享。對于私有的組織方式，由于核主要訪問靠近自身的私有cache，因而訪問cache延遲小，但允許存在數(shù)據(jù)塊副本導致cache容量的浪費，從而致使訪問cache命中率降低，造成了大量的片外訪問存儲。對于共享的組織方式，由于數(shù)據(jù)塊均勻分布在各cache中，因而核要經(jīng)常訪問遠處cache。致使核平均訪問chche延遲較大，但命中率卻高。

針對這個問題，國外大學已作了些研究，提出了很多混合私有和共享組織方式的結(jié)構(gòu)。Cooperative Caching[1]、CMP-NuRAPID[2]都是以私有cache組織方式為基礎，解決私有方式中命中率低的問題。Cooperative Caching將二級cache數(shù)據(jù)塊分為兩種：唯一存在的數(shù)據(jù)塊和有副本的數(shù)據(jù)塊。在替換數(shù)據(jù)時，優(yōu)先考慮無效的數(shù)據(jù)塊和有副本的數(shù)據(jù)塊，這樣就可減少大量的數(shù)據(jù)塊副本。但Cooperative Caching也明顯存在著一些不足。首先，Cooperative Caching受到集中式目錄表的限制不便于擴大，隨著核的數(shù)量增長，這種機制將變得不適應。再次，集中式目錄表的硬件花費太大。最后，Cooperative Caching的替換機制是先將有副本的數(shù)據(jù)塊替換出去，而保留唯一存在的數(shù)據(jù)塊。這種機制比較盲目，因為好多存在副本的數(shù)據(jù)塊是要經(jīng)常被訪問的，而某些唯一存在的數(shù)據(jù)塊，卻只被訪問一次。CMP-NuRAPID有效的控制共享數(shù)據(jù)塊副本的個數(shù)，并通過集中式目錄有效的利用整個二級cache空間。動態(tài)數(shù)據(jù)塊的遷移、改變共享度、Cache片的動態(tài)分配等是基Cache共享方式的，主要改善共享方式中訪問延遲長。

基于私有方式策略的共同點是合理的減少副本數(shù)量，上述策略均是靜態(tài)按照某種策略去控制數(shù)據(jù)副本數(shù)量，不能根據(jù)實際執(zhí)行程序情況動態(tài)控制數(shù)據(jù)副本數(shù)量。本文通過動態(tài)監(jiān)測程序執(zhí)行情況，從而判斷是否需要控制副本數(shù)量，進而通過監(jiān)測信息的判斷，是否有必要減少數(shù)據(jù)塊副本。

二、CMP中工作集的分析

私有方式下多個核對共享數(shù)據(jù)的訪問則會產(chǎn)生數(shù)據(jù)塊副本，數(shù)據(jù)塊副本用來減少訪問共享數(shù)據(jù)延遲，然而數(shù)據(jù)塊副本對cache空間造成浪費。針對不同大小的工作集，本文分析數(shù)據(jù)塊副本對cache性能影響的大小，從而探究有效控制數(shù)據(jù)塊副本容量的必要性。分析是基于多個商用和科學計算的測試程序在8個核上的Solaris10系統(tǒng)中的測試，實驗部分會詳述實驗的具體設計。

為分析數(shù)據(jù)塊副本所占空間對cache性能的影響，本文設計一種極端情況：給每個二級cache添加一個數(shù)據(jù)塊副本區(qū)，數(shù)據(jù)塊副本區(qū)是用來專門存儲數(shù)據(jù)塊副本，從其他二級cache讀入的數(shù)據(jù)塊副本將保存在副本區(qū)中，副本區(qū)容量為無限大。如此數(shù)據(jù)塊副本將不會影響cache的命中率。本文模擬私有方式和副本區(qū)方式兩種情況，分析比對不同的測試程序在這兩種情況的命中率。

從實驗數(shù)據(jù)可以看出：lu、radix、fft、ocean這些測試程序的缺失率的比率基本趨于1，這說明副本區(qū)提高不了這些測試程序的命中率。如fft這類測試程序的工作集比較小，二級cache空間已足夠使用，故無需副本區(qū)。如ocean這類測試程序，其工作集較大，但是線程之間的共享變量少，從而使得副本很少，故副本區(qū)也不能提高命中率。所以，在上述兩種情況下，在測試程序執(zhí)行中控制副本容量對提高cache命中率基本起步到任何作用。Clonesky、water、bares、apache這些測試程序的缺失比率都相當高，特別是apache，其工作集比較大，又有大量的副本，執(zhí)行過程中副本被存儲在副本區(qū)中，從而不去替換cache中的數(shù)據(jù)，可明顯減少cache的缺失率。在這種情況下若能有效的控制副本容量，將能明顯提高cache的命中率。綜上可以看出，是否需要控制副本針對不同的測試程序是不同的，故要動態(tài)的根據(jù)執(zhí)行情況去采取相應的控制策略。

三、副本數(shù)據(jù)塊與獨占數(shù)據(jù)塊分析

當發(fā)生一級cache缺失時，二級cache的平均訪問延遲時間可用如下公式表示：

其中p本地L2、p其他L2、p主存分別表示數(shù)據(jù)塊在本地L2、其他L2、主存中的概率。

本地二級cache中包含兩種數(shù)據(jù)塊，一種是從其他二級cache讀入保存在本地L2中的數(shù)據(jù)塊，稱其為副本數(shù)據(jù)塊。另一種是從主存中讀入的數(shù)據(jù)塊，該數(shù)據(jù)塊是片上唯一在本地二級cache中存在的數(shù)據(jù)塊，稱其為獨占數(shù)據(jù)塊。由公式可看出，通過在本地二級cache中保存副本數(shù)據(jù)塊，在發(fā)生一級cache缺失時，從而避免去其他L2訪問，可減少p其他L2概率，進而降低L1缺失延遲。但由于保存了大量副本數(shù)據(jù)塊，致使獨占數(shù)據(jù)塊的容量減少，從而增加p主存概率，使得L1缺失延遲增長。所以只有使副本數(shù)據(jù)塊容量合適，才能使二級cache的訪問延遲最小。

多核中私有二級cache中的副本數(shù)據(jù)塊和獨占數(shù)據(jù)塊的容量是根據(jù)請求去通過替換算法動態(tài)分配的，這種分配方法是將副本數(shù)據(jù)塊和獨占數(shù)據(jù)塊的作用效果等同起來，然而副本數(shù)據(jù)塊和獨占數(shù)據(jù)塊的缺失代價是不同的。當發(fā)生副本數(shù)據(jù)塊缺失時，缺失代價為其他L2的延遲，其時延為幾十個時鐘周期。而獨占數(shù)據(jù)塊發(fā)生缺失時，則只能去主存訪問，其時延為幾百個時鐘周期。所以應當優(yōu)先考慮獨占數(shù)據(jù)塊，因為其缺失代價更大。如當程序工作集比較大時，則要優(yōu)先替換副本數(shù)據(jù)塊，從而減少獨占數(shù)據(jù)塊的缺失。本文將根據(jù)動態(tài)執(zhí)行情況去協(xié)調(diào)副本數(shù)據(jù)塊和獨占數(shù)據(jù)塊容量。

四、副本容量的控制策略

（一）策略

將程序的工作集分成四類：工作集為一級cache容量大小、工作集為二級cache容量、工作集為片上二級cache總?cè)萘?、工作集為主存容量。對于前兩類程序，則無需控制副本容量，因為本地私有二級cache空間足夠容納工作集，保存副本數(shù)據(jù)塊不會造成p主存概率的增加。對于第四類程序，控制副本容量也無必要。這時p主存概率將會很大，由于副本造成的p主存概率增加對于二級cache的性能影響不大。對于第三類程序，合適控制副本數(shù)據(jù)塊和獨占數(shù)據(jù)塊的容量分配可有效提高私有情況cache性能。本文通過對獨占數(shù)據(jù)塊使用情況的檢測來判斷程序?qū)儆谀念?，從而實現(xiàn)在那種情況實施副本容量的控制策略。

在實施副本容量的控制時，通過合理的減少副本容量，則可降低p主存概率，使獨占數(shù)據(jù)塊的缺失率變小。同時這也會造成p其他L2概率的增加，從而造成副本數(shù)據(jù)塊缺失率的增加。所以，要使得性能提高必須保證如下公式成立：

其中 表示p其他L2概率的增加， 表示p主存概率的減少。

（二）實現(xiàn)

二級cache中每個組中添加一個Shadow Tag、Shadow Tag計數(shù)器和副本LRU計數(shù)器。當一個獨占數(shù)據(jù)塊從二級cache中被替換時，該數(shù)據(jù)塊的Tag信息則保存在Shadow Tag中。當二級發(fā)生獨占數(shù)據(jù)塊缺失時，若缺失數(shù)據(jù)塊的Tag信息與Shadow Tag中的一致，則說明在該組中若給獨占數(shù)據(jù)塊多增加一個數(shù)據(jù)的分配，則可避免此次缺失。Shadow Tag計數(shù)器用來記錄這種情況，該計數(shù)器的值說明增加一個空間保存獨占數(shù)據(jù)塊所能減少的獨占數(shù)據(jù)塊缺失次數(shù)。副本LRU計數(shù)器用來記錄副本數(shù)據(jù)塊中最久沒有被訪問的數(shù)據(jù)命中的次數(shù)。該計數(shù)器的值可以說明替換一個副本數(shù)據(jù)塊所造成的副本數(shù)據(jù)的缺失次數(shù)。

通過Shadow Tag計數(shù)器的值可以監(jiān)測目前程序工作集的類型，若一段時間內(nèi)該值為零或很小，則說明程序為前兩種類型。若值非常大，則為最后一種類型。當Shadow Tag計數(shù)器的值處在一定范圍內(nèi)時，將認為程序為第三類，需對副本容量進行控制。當如下公式成立成立時，則優(yōu)先替換副本，從而降低副本容量。

每隔2000個主存訪問，Shadow Tag計數(shù)器和副本LRU計數(shù)器清零。

（三）硬件代價

Shadow Tag、Shadow Tag計數(shù)器和副本LRU計數(shù)器所占的容量。

五、實驗方法

基于simics[3]和gems[4]，本文設計實現(xiàn)多核全模擬系統(tǒng)，對動態(tài)副本控制策略進行分析評價。該部分主要說明私有cache系統(tǒng)體系架構(gòu)、系統(tǒng)參數(shù)以及基準測試集。

（一）私有cache系統(tǒng)體系架構(gòu)

私有cache的多核體系架構(gòu)中，每個核將自己本地的cache作為私有，這類似于Intel的Pentium D[5]的結(jié)構(gòu)。這種結(jié)構(gòu)可看作將多處理器系統(tǒng)集成在一個片子上。由于總線監(jiān)聽方式可擴展性比價差，故本文采用基于目錄的一致性處理方式。

（二）系統(tǒng)參數(shù)和測試集

L1、L2均采用寫回、寫分配。L2采用MOSI一致性模型，存儲器連貫性模型采用的是順序連貫性模型。片上互聯(lián)網(wǎng)絡為2D環(huán)網(wǎng)。模擬器上的操作系統(tǒng)用的是Solaris10。

測試集包含apache商業(yè)測試集和來自SPLASH2工作集的一些科學計算測試程序。

六、結(jié)果分析

通過實驗數(shù)據(jù)可以看出：radix、raytrace、apache的性能都得到了改善。從第二部分可以得知，Apache最具有提升空間，理論上可以提高60%，這里動態(tài)控制副本容量的情況下，取得4.5%的性能提高。圖中顯示FFT的性能沒有變化。這與第二部分所測的結(jié)果是吻合的，因為控制副本對FFT的性能不產(chǎn)生影響。

參考文獻

[1]Chang J， Sohi G. Cooperative caching for chip multiprocessors[C]: IEEE Computer Society， 2006: 276.

[2]Chishti Z， Powell M， Vijaykumar T. Optimizing replication， communication， and capacity allocation in CMPs[C]， 2005: 357-368.

[3]Magnusson P， Christensson M， Eskilson J， et al. Simics: A full system simulation platform[J]. Computer， 2002: 50-58.

[4]Martin M， Sorin D， Beckmann B， et al. Multifacet''s general execution-driven multiprocessor simulator (GEMS) toolset[J]. ACM SIGARCH Computer Architecture News， 2005， 33 (4): 99.

[5]Peng L， Peir J， Prakash T， et al. Memory performance and scalability of Intel''s and AMD''s dual-core processors: a case study[C]， 2007: 55-64.

[作者簡介]文敏華（1985.5-），男，陜西省旬邑縣、2010年畢業(yè)于西安交通大學計算機科學與技術(shù)專業(yè)，現(xiàn)供職中航工業(yè)計算所、碩士學歷、研究方向為嵌入式計算。