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

關(guān)鍵詞：Cache；副本；動(dòng)態(tài)控制

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

一、引言

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

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

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

二、CMP中工作集的分析

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

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

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

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

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

其中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ù)塊，稱其為獨(dú)占數(shù)據(jù)塊。由公式可看出，通過在本地二級cache中保存副本數(shù)據(jù)塊，在發(fā)生一級cache缺失時(shí)，從而避免去其他L2訪問，可減少p其他L2概率，進(jìn)而降低L1缺失延遲。但由于保存了大量副本數(shù)據(jù)塊，致使獨(dú)占數(shù)據(jù)塊的容量減少，從而增加p主存概率，使得L1缺失延遲增長。所以只有使副本數(shù)據(jù)塊容量合適，才能使二級cache的訪問延遲最小。

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

四、副本容量的控制策略

（一）策略

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

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

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

（二）實(shí)現(xiàn)

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

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

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

（三）硬件代價(jià)

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

五、實(shí)驗(yàn)方法

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

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

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

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

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

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

六、結(jié)果分析

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

參考文獻(xià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è)于西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)，現(xiàn)供職中航工業(yè)計(jì)算所、碩士學(xué)歷、研究方向?yàn)榍度胧接?jì)算。