面向大數(shù)據(jù)應(yīng)用的眾核處理器緩存結(jié)構(gòu)設(shè)計(jì)*

萬(wàn) 虎,徐遠(yuǎn)超,2,孫鳳蕓,閆俊峰

(1.首都師范大學(xué)信息工程學(xué)院,北京 100048;

2.中國(guó)科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190)

面向大數(shù)據(jù)應(yīng)用的眾核處理器緩存結(jié)構(gòu)設(shè)計(jì)*

萬(wàn) 虎1,徐遠(yuǎn)超1,2,孫鳳蕓1,閆俊峰1

(1.首都師范大學(xué)信息工程學(xué)院,北京 100048;

2.中國(guó)科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190)

大規(guī)模數(shù)據(jù)排序、搜索引擎、流媒體等大數(shù)據(jù)應(yīng)用在面向延遲的多核/眾核處理器上運(yùn)行時(shí)資源利用率低下，一級(jí)緩存命中率高，二級(jí)/三級(jí)緩存命中率低，LLC容量的增加對(duì)IPC的提升并不明顯。針對(duì)緩存資源利用率低的問(wèn)題，分析了大數(shù)據(jù)應(yīng)用的訪存行為特點(diǎn)，提出了針對(duì)大數(shù)據(jù)應(yīng)用的兩種眾核處理器緩存結(jié)構(gòu)設(shè)計(jì)方案，兩種結(jié)構(gòu)均只有一級(jí)緩存，Share結(jié)構(gòu)為完全共享緩存，Partition結(jié)構(gòu)為部分共享緩存。評(píng)估結(jié)果表明，兩種方案在訪存延遲增加不多的前提下能大幅節(jié)省芯片面積，其中緩存容量較低時(shí)，Partition結(jié)構(gòu)優(yōu)于Share結(jié)構(gòu)，緩存容量較高時(shí)，Share結(jié)構(gòu)要逐漸優(yōu)于Partition結(jié)構(gòu)。由于眾核處理器中分配到每個(gè)處理器核的容量有限，因此Partition結(jié)構(gòu)有一定的優(yōu)勢(shì)。

眾核處理器；大數(shù)據(jù)應(yīng)用；緩存設(shè)計(jì)；訪存行為；數(shù)據(jù)中心

2.State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences, Beijing 100190,China)

1 引言

處理器是計(jì)算機(jī)系統(tǒng)的最重要部件之一，對(duì)系統(tǒng)的性能和能耗有著重要影響。然而，研究人員發(fā)現(xiàn)，在面向社交網(wǎng)絡(luò)、搜索引擎、網(wǎng)絡(luò)流媒體等一些大數(shù)據(jù)應(yīng)用時(shí)[1]，傳統(tǒng)的多核/眾核處理器能效比較低下[2]，如處理器核邏輯過(guò)于復(fù)雜、共享緩存和訪存帶寬利用率不高等，這是因?yàn)閭鹘y(tǒng)的多核/眾核處理器以提高性能、降低延遲為目標(biāo)，而目前數(shù)據(jù)中心的主流應(yīng)用呈現(xiàn)出小粒度、高并發(fā)特征，期望的是更高的吞吐率，而對(duì)延遲不是太敏感。因此，傳統(tǒng)的多核/眾核處理器設(shè)計(jì)與當(dāng)前的大數(shù)據(jù)應(yīng)用的需求不匹配，導(dǎo)致片內(nèi)資源利用率低，不僅無(wú)法提高應(yīng)用的性能和吞吐率，也浪費(fèi)芯片面積和功耗。

本文對(duì)數(shù)據(jù)中心部分應(yīng)用的訪存行為進(jìn)行了分析，這些應(yīng)用涵蓋了搜索引擎、社會(huì)網(wǎng)絡(luò)、網(wǎng)絡(luò)流媒體等應(yīng)用領(lǐng)域，結(jié)果發(fā)現(xiàn)，這些應(yīng)用在現(xiàn)有多級(jí)緩存結(jié)構(gòu)的處理器上運(yùn)行時(shí)，L1緩存的命中率較高，而L2緩存、L3緩存的命中率相對(duì)較低，這意味著緩存容量大小數(shù)倍于L1緩存的L2緩存和L3緩存只是將整個(gè)緩存的命中率提高了幾個(gè)百分點(diǎn)，平均訪存延遲并沒(méi)有明顯下降。研究人員還發(fā)現(xiàn)[3]，L3緩存增加到6 MB以上時(shí)，IPC不再顯著提高。

眾核處理器在片內(nèi)集成了多個(gè)簡(jiǎn)單處理器核，具備強(qiáng)大的線程級(jí)并行處理能力，可以同時(shí)響應(yīng)成千上萬(wàn)的高并發(fā)用戶請(qǐng)求，非常適合大數(shù)據(jù)應(yīng)用的高并發(fā)請(qǐng)求，是數(shù)據(jù)中心處理器的理想選擇。然而，眾核處理器的核數(shù)多，如果按照傳統(tǒng)的緩存結(jié)構(gòu)設(shè)計(jì)，緩存資源浪費(fèi)嚴(yán)重。本文針對(duì)緩存利用率低的問(wèn)題，結(jié)合大數(shù)據(jù)應(yīng)用的特點(diǎn)設(shè)計(jì)了兩種緩存結(jié)構(gòu)，兩種結(jié)構(gòu)均建議將L2緩存和L3緩存去除，其中一種為完全共享(Share)緩存結(jié)構(gòu)，另一種是私有緩存和共享緩存共存的劃分(Partition)緩存結(jié)構(gòu)。結(jié)果表明，在緩存容量較低時(shí)，劃分緩存結(jié)構(gòu)的命中率高于共享緩存結(jié)構(gòu)，隨著緩存容量的增加，共享緩存結(jié)構(gòu)的命中率要高于劃分緩存結(jié)構(gòu)。

2 相關(guān)研究

緩存是利用局部性原理來(lái)緩解處理器和內(nèi)存之間的速度差異。然而，要利用好緩存需要自頂向下多層次的合理設(shè)計(jì)，避免抖動(dòng)，降低干擾。比如，一個(gè)訪存密集但重用率低的流式應(yīng)用程序不斷將數(shù)據(jù)帶入緩存，替換出其他程序可能重用的數(shù)據(jù)，后者重用數(shù)據(jù)時(shí)產(chǎn)生的大量訪存又和前者競(jìng)爭(zhēng)帶寬資源，從而形成惡性循環(huán)，導(dǎo)致兩個(gè)程序的性能都急劇下降，這就是抖動(dòng)問(wèn)題。再如，從數(shù)據(jù)局部性角度看，不同程序有不同的數(shù)據(jù)訪問(wèn)模式，共享緩存對(duì)同時(shí)運(yùn)行的多道程序的訪存不加以區(qū)分，就產(chǎn)生了程序間的緩存干擾。

提高緩存利用率的方法很多，比如緩存感知的應(yīng)用程序設(shè)計(jì)[4]，通過(guò)合理布局內(nèi)存中的數(shù)據(jù)，提高數(shù)據(jù)的空間局部性；通過(guò)編譯器或操作系統(tǒng)分析程序的行為，預(yù)測(cè)所需要的緩存大小[5]；通過(guò)剖析(Profiling)[6]每個(gè)線程對(duì)緩存的空間需求實(shí)現(xiàn)緩存的靜態(tài)劃分；通過(guò)操作系統(tǒng)預(yù)測(cè)程序執(zhí)行過(guò)程中的緩存需求實(shí)現(xiàn)緩存的動(dòng)態(tài)劃分[7]。

以上研究都是在傳統(tǒng)多級(jí)緩存存儲(chǔ)層次結(jié)構(gòu)上為減少線程之間的相互干擾、減少緩存空間的競(jìng)爭(zhēng)而采取的策略，這些策略也適用于大數(shù)據(jù)應(yīng)用環(huán)境，但仍然無(wú)法從根本上摒除大數(shù)據(jù)應(yīng)用環(huán)境下使用多級(jí)緩存結(jié)構(gòu)存在的資源利用率不高的問(wèn)題，也就是說(shuō)，僅從軟件層面解決是不夠的，必須從結(jié)構(gòu)上進(jìn)行改進(jìn)。

眾核處理器主要有NVIDIA的Fermi、Intel的Phi處理器、Larrabee、Godson-T、Tilera的TILE，這些處理器均為二級(jí)或三級(jí)緩存結(jié)構(gòu)，主要用于加速和高性能計(jì)算。只有L1緩存、基于ARM的簡(jiǎn)單處理器核適宜線程級(jí)并行，已在數(shù)據(jù)中心得到了廣泛應(yīng)用，但不屬于眾核處理器結(jié)構(gòu)，也沒(méi)有評(píng)估私有數(shù)據(jù)和共享數(shù)據(jù)的劃分問(wèn)題。Tullsen D M[8]認(rèn)為在軟件線程數(shù)少于硬件線程數(shù)時(shí)L1緩存采取共享方式效果最佳。但是，在高并發(fā)的大數(shù)據(jù)應(yīng)用環(huán)境下，每個(gè)硬件線程基本上都處于飽和狀態(tài)，隨著軟件線程數(shù)的增加，共享緩存的線程間數(shù)據(jù)干擾加重，吞吐率就會(huì)出現(xiàn)波動(dòng)。

3 大數(shù)據(jù)應(yīng)用訪存行為分析

3.1 大數(shù)據(jù)應(yīng)用的特點(diǎn)

詹劍鋒等[9]把數(shù)據(jù)中心應(yīng)用分為三大類，分別為數(shù)據(jù)密集型服務(wù)、數(shù)據(jù)處理應(yīng)用、交互式實(shí)時(shí)應(yīng)用。比如，文本搜索引擎就是服務(wù)類應(yīng)用，流媒體、VoIP等屬于實(shí)時(shí)交互式應(yīng)用。數(shù)據(jù)處理應(yīng)用特指基于MapReduce或Dryad編程模型的松耦合應(yīng)用，不包括緊耦合數(shù)據(jù)處理應(yīng)用。大數(shù)據(jù)應(yīng)用有幾個(gè)明顯特征。一是負(fù)載特征，服務(wù)請(qǐng)求之間、作業(yè)任務(wù)之間相對(duì)獨(dú)立，沒(méi)有很強(qiáng)的依賴關(guān)系，易于水平擴(kuò)展(Scale Out)。雖然GPU、MIC等眾核處理器的線程級(jí)并行度也很高，但線程之間的耦合度很高，都服務(wù)于一個(gè)特定的任務(wù)，單個(gè)線程的運(yùn)行時(shí)間影響整體性能，而大數(shù)據(jù)應(yīng)用追求高吞吐率，不以提高單個(gè)線程的性能為目標(biāo)。二是體系結(jié)構(gòu)特征，浮點(diǎn)操作少、整型操作比例高，數(shù)據(jù)通道能力主導(dǎo)，即Load/Store指令所占比例高。

海量數(shù)據(jù)工作集、高并發(fā)、數(shù)據(jù)離散、訪存隨機(jī)是這些應(yīng)用的典型特點(diǎn)。比如，微博、推特等社交網(wǎng)站，用戶眾多且相互交織，組成復(fù)雜的圖關(guān)系。線程內(nèi)部訪問(wèn)的數(shù)據(jù)多為非結(jié)構(gòu)化數(shù)據(jù)，比較離散，隨機(jī)性強(qiáng)，空間局部性差，數(shù)據(jù)重用率低。再如，大規(guī)模數(shù)據(jù)排序執(zhí)行步驟明確，流式特征明顯，數(shù)據(jù)的時(shí)間局部性差，導(dǎo)致數(shù)據(jù)的重用距離超過(guò)共享緩存的相聯(lián)度，造成數(shù)據(jù)在片內(nèi)多級(jí)緩存之間冗余流動(dòng)。在類似搜索引擎這樣的大數(shù)據(jù)應(yīng)用中，并發(fā)請(qǐng)求的用戶數(shù)量大，線程相似度高，但請(qǐng)求的數(shù)據(jù)幾乎完全獨(dú)立，而單個(gè)用戶訪問(wèn)的數(shù)據(jù)局部性相對(duì)有限。

傳統(tǒng)的以計(jì)算為中心的緩存結(jié)構(gòu)延長(zhǎng)了數(shù)據(jù)通路，難以應(yīng)對(duì)大數(shù)據(jù)應(yīng)用的訪存行為特點(diǎn)。

3.2 緩存容量敏感性分析

處理器進(jìn)入多核/眾核時(shí)代后，訪存依然是系統(tǒng)性能的瓶頸。為了減少延遲，大部分處理器設(shè)計(jì)為二級(jí)或三級(jí)緩存層次結(jié)構(gòu)，L1為私有緩存，最后一級(jí)緩存(LLC)為共享緩存，LLC容量通常較大。為了緩解不同緩存(如L1緩存與L2緩存、L2緩存與LLC緩存)之間的延遲差距，有些還裝備了緩沖(Buffer)或預(yù)取(Prefetch)部件。

我們首先分析了大數(shù)據(jù)應(yīng)用對(duì)LLC容量的敏感程度，通過(guò)將訪存trace輸入到緩存模擬器中，調(diào)整LLC的容量，得到的結(jié)果如圖1所示，說(shuō)明這些應(yīng)用對(duì)LLC容量并不敏感，當(dāng)容量超過(guò)4 MB以上時(shí)，對(duì)命中率的提高幾乎沒(méi)有貢獻(xiàn)。

Figure 1 Cache hit rate sensitivity to LLC capacity for some big data applications

文獻(xiàn)[3]將數(shù)據(jù)中心的大數(shù)據(jù)應(yīng)用與訪存密集型的桌面應(yīng)用(如SPECInt mcf)進(jìn)行了比較，實(shí)驗(yàn)結(jié)果顯示數(shù)據(jù)中心的大數(shù)據(jù)應(yīng)用對(duì)LLC大小的敏感度在 4 MB～6 MB，隨著LLC容量的增大，IPC并沒(méi)有顯著變化。

傳統(tǒng)緩存結(jié)構(gòu)設(shè)計(jì)以減小延遲為目標(biāo)，層次多、容量大，這種結(jié)構(gòu)適用于數(shù)據(jù)的時(shí)間和空間局部性都非常好的應(yīng)用。對(duì)于大數(shù)據(jù)應(yīng)用而言，處理

的對(duì)象多為半結(jié)構(gòu)或非結(jié)構(gòu)化數(shù)據(jù)，數(shù)據(jù)離散、訪存隨機(jī)、數(shù)據(jù)集大。在一個(gè)時(shí)間區(qū)間內(nèi)，工作集大小往往達(dá)百M(fèi)B以上，而緩存容量通常只有幾MB大小，整個(gè)程序工作集無(wú)法全部放到緩存中，需要反復(fù)替換，數(shù)據(jù)重用率低，不僅發(fā)揮不出緩存的作用，還增加了功耗。

3.3 緩存命中率分析

我們測(cè)試了部分大數(shù)據(jù)應(yīng)用的緩存命中率，在數(shù)據(jù)集均為2 GB、線程數(shù)為8(kmeans和pagerank無(wú)法設(shè)定線程數(shù))時(shí)，實(shí)驗(yàn)結(jié)果如圖2所示。

Figure 2 Three levels cache hit rates of some big data applications

隨著線程數(shù)量的變化，各級(jí)Cache缺失率會(huì)略有不同，但并沒(méi)有改變L1緩存命中率高、L2/LLC緩存命中率低的現(xiàn)象，以wordcount和terasort為例，表1顯示的是線程數(shù)增加時(shí)的緩存命中率。

Table 1 Cache hit rate over the number of threads

大數(shù)據(jù)應(yīng)用處理的數(shù)據(jù)集巨大，為此，我們?cè)u(píng)估了數(shù)據(jù)集大小對(duì)緩存命中率的影響，結(jié)果如圖3所示。

Figure 3 Data sets size’s impact on cache hit rate

以上實(shí)驗(yàn)結(jié)果說(shuō)明，導(dǎo)致L1緩存命中率高、L2/LLC緩存命中率相對(duì)較低的根源不是線程之間的相互干擾，也不是處理的數(shù)據(jù)集大小，而是程序的訪存行為本身。

在一個(gè)時(shí)間區(qū)間內(nèi)，如果一個(gè)線程的工作集可以完全放在L1緩存中且存在一定的空間或時(shí)間局部性，則顯示出L1緩存的命中率高而LLC的命中率低。如果在一個(gè)時(shí)間區(qū)間內(nèi)一個(gè)線程的工作集遠(yuǎn)大于LLC且時(shí)間和空間局部性差，則所有層級(jí)的緩存命中率將很低，因?yàn)橐粋€(gè)線程的數(shù)據(jù)在重用時(shí)已經(jīng)被其它線程替換出去了，需要重新訪存。通過(guò)實(shí)驗(yàn)結(jié)果可以預(yù)測(cè)，雖然整個(gè)程序的工作集很大，但一段時(shí)間內(nèi)每個(gè)線程的工作集較小，可以完全放在L1緩存中，因此L1緩存命中率高，當(dāng)這些數(shù)據(jù)集處理完畢后，重新訪問(wèn)新的數(shù)據(jù)，原來(lái)的數(shù)據(jù)即使緩存在L2或LLC中，也幾乎不再訪問(wèn)，因此多級(jí)緩存結(jié)構(gòu)的作用并沒(méi)有發(fā)揮出來(lái)。

為了比較大數(shù)據(jù)應(yīng)用緩存命中率與其他應(yīng)用的不同，我們從PARSEC[10]測(cè)試集中隨意選擇了幾個(gè)程序，測(cè)量結(jié)果如圖4所示?？梢钥闯?，從PARSEC中選擇的六個(gè)測(cè)試程序中有四個(gè)表現(xiàn)出每級(jí)緩存命中率都很高的現(xiàn)象，說(shuō)明大部分這類應(yīng)用所處理的數(shù)據(jù)局部性好，線程之間數(shù)據(jù)的耦合度高。

Figure 4 Three levels cache hit rates of several PARSEC benchmark applications

4 眾核處理器緩存結(jié)構(gòu)設(shè)計(jì)

4.1 基于SMT的緩存結(jié)構(gòu)設(shè)計(jì)

眾核集成了成百上千個(gè)處理器核，每個(gè)處理器核分配的資源極其有限。本文依托的眾核處理器已確定為采用同時(shí)多線程(SMT)流水線設(shè)計(jì)，每個(gè)硬件線程運(yùn)行一個(gè)軟件線程，取指模塊每拍切換一個(gè)線程，線程發(fā)生緩存失效時(shí)讓出流水線上的所有共享資源，進(jìn)入等待狀態(tài)，不再參與調(diào)度，直到獲取到需要的訪存內(nèi)容。SMT采取的是硬件支持的快速線程切換機(jī)制，可以有效隱藏延遲，與操作系統(tǒng)級(jí)線程切換相比，幾乎可以做到“零時(shí)間開(kāi)銷”。這種設(shè)計(jì)可以讓眾核處理器在單位時(shí)間內(nèi)產(chǎn)生更多的訪存請(qǐng)求，從而充分利用內(nèi)存控制器的訪存帶寬。

首先，我們根據(jù)測(cè)量的緩存命中率實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)平臺(tái)Intel Xeon E5645的延遲參數(shù)(表2)，計(jì)算線程數(shù)為8時(shí)，相對(duì)三級(jí)緩存結(jié)構(gòu)而言，只有一級(jí)緩存結(jié)構(gòu)的平均訪存延遲如表3所示。

其中“命中時(shí)平均延遲”是指CPU發(fā)出請(qǐng)求后到從該級(jí)緩存中獲取數(shù)據(jù)的延遲，L1緩存“缺失時(shí)平均延遲”通過(guò)式(1)計(jì)算得到，L2緩存“缺失時(shí)平均延遲”通過(guò)式(2)計(jì)算得到。

Table 2 Hardware experimental platform

L1_miss_latency=L2_Hit_Rate*12+

(1-L2_Hit_Rate)*L2_miss_latency

(1)

L2_miss_Latency=L3_Hit_Rate*

45+(1-L3_Hit_Rate)*200

(2)

忽略傳輸延遲，CPU發(fā)出請(qǐng)求后到從L1緩存取得數(shù)據(jù)是四個(gè)cycles，主要是查找。查找L2緩存的延遲是八個(gè)cycles，查找L3緩存的延遲是33個(gè)cycles，向內(nèi)存控制器發(fā)出訪存請(qǐng)求到取回?cái)?shù)據(jù)的時(shí)間延遲是155個(gè)cycles，LLC缺失時(shí)的平均延遲由各級(jí)緩存查找延遲和訪存延遲構(gòu)成，共200cycles。

Table 3 Cache hierarchy impact on memory access latency

從表3看出，L2/LLC緩存去掉以后，wordcount、terasort、index、search、pagerank、kmeans的訪存延遲分別下降5.88%、下降13.02%、增加9.92%、下降9.21%、增加4.08%、增加4.70%?？梢?jiàn)，平均訪存延遲并沒(méi)有明顯增加，部分程序甚至還略有下降，原因在于減少了很多無(wú)效的緩存查找，縮短了訪存路徑。大容量的LLC去掉以后，節(jié)省的芯片面積可用于部署更多的處理器核以提高線程級(jí)并行度。延遲往往影響單個(gè)線程的性能，但大數(shù)據(jù)應(yīng)用追求的是整體吞吐率的提升，不僅如此，緩存層次的減少避免了很多無(wú)效的緩存查找開(kāi)銷，縮短了訪存路徑。

經(jīng)過(guò)以上分析，我們?cè)O(shè)計(jì)了兩種緩存結(jié)構(gòu)，兩種結(jié)構(gòu)均設(shè)計(jì)為只有一級(jí)緩存。結(jié)構(gòu)1為完全共享緩存結(jié)構(gòu)(圖5a)，以下簡(jiǎn)稱為Share。結(jié)構(gòu)2為私有緩存和共享緩存共存的劃分緩存結(jié)構(gòu)(圖5b)，以下簡(jiǎn)稱為Partition。Partition結(jié)構(gòu)的設(shè)計(jì)依據(jù)是，大數(shù)據(jù)應(yīng)用處理的數(shù)據(jù)共享度低，為避免各線程之間的數(shù)據(jù)互相干擾，為各線程分配獨(dú)立的緩存以存放私有數(shù)據(jù)，將線程間少量的共享數(shù)據(jù)存放到共享緩存中。

Figure 5 SMT-based processor core structure

4.2 讀寫策略與緩存一致性

Share結(jié)構(gòu)緩存同一個(gè)處理器核的所有數(shù)據(jù)，讀寫策略、替換算法與傳統(tǒng)結(jié)構(gòu)相同。Partition結(jié)構(gòu)將同一級(jí)緩存劃分為私有和共享兩部分，在緩存查找時(shí)需要區(qū)分?jǐn)?shù)據(jù)類型，是線程私有數(shù)據(jù)還是線程間共享數(shù)據(jù)。為此，我們?cè)诘刂非懊婕恿艘粋€(gè)標(biāo)志位(shared_flag)，根據(jù)shared_flag判斷地址指向的區(qū)域是私有數(shù)據(jù)區(qū)域還是共享數(shù)據(jù)區(qū)域，如圖6所示，當(dāng)shared_flag=1時(shí)表示私有數(shù)據(jù)區(qū)域，此時(shí)訪問(wèn)對(duì)應(yīng)的硬件線程的私有緩存，當(dāng)shared_flag=0時(shí)表示共享數(shù)據(jù)區(qū)域，此時(shí)，無(wú)論線程運(yùn)行在哪個(gè)硬件線程上，都訪問(wèn)共享緩存。本文定義的緩存不同于傳統(tǒng)意義上的一級(jí)私有緩存和LLC共享緩存，本文定義的私有緩存和共享緩存位于同一級(jí)，因此，在查找上沒(méi)有先后，而是同時(shí)進(jìn)行的。CPU究竟使用物理地址還是虛擬地址查找緩存與緩存的具體實(shí)現(xiàn)相關(guān)，無(wú)論采取什么地址，用于區(qū)分私有數(shù)據(jù)和共享數(shù)據(jù)的標(biāo)志位都存在于TLB中，訪問(wèn)緩存時(shí)，需要先查詢TLB。當(dāng)CPU訪問(wèn)私有緩存時(shí)，如果是讀不命中，則直接訪問(wèn)片外主存，將取出的數(shù)據(jù)回填到私有緩存中；如果是寫命中，可以設(shè)計(jì)為寫回(Write Back)或?qū)懘┩?Write Through)策略；如果寫不命中，可以設(shè)計(jì)為寫分配(Write Allocate)或非寫分配(Not-Write allocate)策略。由于只有一級(jí)緩存，無(wú)論采取什么算法，相對(duì)于多級(jí)緩存結(jié)構(gòu)都要簡(jiǎn)單很多。當(dāng)訪問(wèn)共享緩存不命中時(shí)，采取與私有緩存同樣的方法處理。

眾核的緩存一致性是一個(gè)經(jīng)典問(wèn)題，由于處理器核眾多，緩存分布較廣，一致性維護(hù)的開(kāi)銷很大。對(duì)于Partition結(jié)構(gòu)而言，省掉了維護(hù)私有緩存一致性的開(kāi)銷，只需要維護(hù)共享緩存一致性。我們?cè)O(shè)計(jì)的眾核處理器劃分了多個(gè)分區(qū)，每一個(gè)分區(qū)對(duì)應(yīng)一個(gè)內(nèi)存控制器，只需要維護(hù)單個(gè)分區(qū)的緩存一致性，不需要維護(hù)整個(gè)眾核處理器的緩存一致性，從而將維護(hù)緩存一致性的空間開(kāi)銷和時(shí)間開(kāi)銷降低了一個(gè)數(shù)量級(jí)，更細(xì)節(jié)的內(nèi)容超出了本文的范圍。

4.3 共享數(shù)據(jù)的識(shí)別

識(shí)別一個(gè)數(shù)據(jù)是私有數(shù)據(jù)還是共享數(shù)據(jù)，是Partition結(jié)構(gòu)的關(guān)鍵。陳渝等人[11]通過(guò)在緩存行(Cache Line)中引入處理器核標(biāo)識(shí)符來(lái)判別是否為共享數(shù)據(jù)，即，當(dāng)一個(gè)處理器核訪問(wèn)某一個(gè)緩存行時(shí)，在緩存行中記錄該處理器核的標(biāo)識(shí)，如果之后被另一個(gè)處理器核訪問(wèn)，說(shuō)明此數(shù)據(jù)被兩個(gè)處理器核同時(shí)訪問(wèn)，即認(rèn)為是共享數(shù)據(jù)。這種通過(guò)學(xué)習(xí)來(lái)識(shí)別共享數(shù)據(jù)的方法適用于運(yùn)行時(shí)間較長(zhǎng)的大規(guī)模程序，不適用于本文所針對(duì)的高并發(fā)、運(yùn)行時(shí)間相對(duì)較短的輕量級(jí)線程和本文設(shè)計(jì)的Partition緩存結(jié)構(gòu)。

Figure 7 Using ignored bits in page table entry to differentiate shared or private data

本文采用編譯制導(dǎo)語(yǔ)句對(duì)多線程程序中的共享數(shù)據(jù)和私有數(shù)據(jù)進(jìn)行手工標(biāo)識(shí)，結(jié)合操作系統(tǒng)分頁(yè)機(jī)制，最終將線程私有數(shù)據(jù)存放在每一個(gè)線程獨(dú)占的頁(yè)框中，將屬于線程間共享數(shù)據(jù)存放在線程共享的頁(yè)框中。操作系統(tǒng)分配內(nèi)存空間是以頁(yè)為單位的，頁(yè)框的基地址寫在頁(yè)表項(xiàng)中，為了對(duì)頁(yè)框指向的是私有數(shù)據(jù)區(qū)域還是共享數(shù)據(jù)區(qū)域，在頁(yè)表項(xiàng)的保留位(如圖7所示的第9～14位)中定義一個(gè)標(biāo)志位，如果是私有數(shù)據(jù)區(qū)域，標(biāo)志位置1，如果是共享數(shù)據(jù)區(qū)域，標(biāo)志位置0。為了減小維護(hù)緩存一致性的開(kāi)銷，眾核運(yùn)行時(shí)系統(tǒng)(Runtime System)將同一個(gè)應(yīng)用的多個(gè)線程盡量聚合到同一個(gè)處理器核上，避免過(guò)于分散。這種編譯制導(dǎo)的方法在Godson-T眾核處理器中已得到運(yùn)用。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)平臺(tái)

緩存缺失率由Intel開(kāi)發(fā)的Vtune工具采集相關(guān)事件后計(jì)算得到的，這些事件都是與體系結(jié)構(gòu)相關(guān)的。為了對(duì)緩存結(jié)構(gòu)進(jìn)行評(píng)估，開(kāi)發(fā)了一個(gè)基于trace驅(qū)動(dòng)的緩存模擬器，訪存trace作為輸入，命中率作為輸出。為了抓取訪存trace，基于Pin[12]工具編寫了一個(gè)支持多線程的PinTool，可以得到每個(gè)線程的訪存行為。

由于緩存設(shè)計(jì)空間巨大，根據(jù)現(xiàn)有處理器的典型配置，選取了幾組參數(shù)，首先是緩存行大小，評(píng)估了64 B和32 B兩種大小，實(shí)驗(yàn)結(jié)果顯示，在同等容量下，64 B行大小要優(yōu)于32 B行大小。容量一定時(shí)，行的數(shù)量與行大小成反比，行數(shù)越少，沖突失效的可能性越大，因此行大小也不能太大。

為了確定私有緩存和共享緩存的比例，我們對(duì)選取的幾個(gè)大數(shù)據(jù)應(yīng)用的線程間共享訪存情況進(jìn)行了統(tǒng)計(jì)，分別截取了幾個(gè)GB大小的trace，得到的數(shù)據(jù)如表4所示，每個(gè)程序共享訪存比例不盡相同，但普遍不高，沒(méi)有超過(guò)20%，為此，我們將私有緩存和共享緩存的大小比例粗略定義為4∶1。

Table 4 Percentage of inter-thread shared memory address access

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

將二級(jí)、三級(jí)緩存去掉以后，帶來(lái)的直接變化是緩存所占芯片面積大幅減小，以本文硬件實(shí)驗(yàn)平臺(tái)Intel Xeon E5645為例，如果只保留L1緩存，則芯片面積減少為原來(lái)的1/73，即32 KB*6/(32 KB*6+256 KB*6+12 MB)，而訪存延遲并沒(méi)有顯著增加(見(jiàn)表3)。

通過(guò)自主開(kāi)發(fā)的緩存模擬器，我們?cè)u(píng)估了硬件線程數(shù)為8的SMT眾核處理器核五種緩存容量大小下的緩存命中率，分別為8 KB、16 KB、32 KB、64 KB和128 KB。

Figure 8 Comparison of cache hit rate under five cache capacities between Share and Partition

從圖8可以看到，當(dāng)緩存容量為8 KB時(shí)，Partition結(jié)構(gòu)的緩存命中率普遍好于Share結(jié)構(gòu)，由于一級(jí)緩存命中率大多都在90%以上，繼續(xù)提高的幅度有限。當(dāng)緩存容量逐漸增大時(shí)，Partition結(jié)構(gòu)的優(yōu)勢(shì)不再明顯，甚至要差于Share結(jié)構(gòu)。原因在于，緩存容量增大后，沖突失效減少，線程間發(fā)生數(shù)據(jù)替換的概率降低，而Partition結(jié)構(gòu)中的私有緩存空間無(wú)法得到充分利用，因?yàn)樗蔷€程私有的。

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，在緩存空間較小時(shí)，Partition結(jié)構(gòu)下的緩存命中率比Share結(jié)構(gòu)都有不同程度的提高。這對(duì)于眾核處理器設(shè)計(jì)來(lái)講非常重要，因?yàn)槠瑑?nèi)集成了上千個(gè)處理器核，而緩存在芯片面積中的比重較大，每一個(gè)處理器核不可能分配太大的緩存空間。

5.3 分析討論

大數(shù)據(jù)應(yīng)用種類繁多，本文只選擇了其中幾個(gè)有代表性的應(yīng)用，包含了CloudSuite[3]中所敘述的主要程序類型和文獻(xiàn)[6]中所定義的全部三類應(yīng)用。雖然無(wú)法確定是否所有的大數(shù)據(jù)應(yīng)用都具有這樣的訪存行為，但基本可以肯定有不小比例的應(yīng)用具有這樣的訪存行為，很多數(shù)據(jù)中心(如Google)往往提供相對(duì)單一的服務(wù)，如搜索引擎，在能效的驅(qū)動(dòng)下，處理器設(shè)計(jì)正在從通用轉(zhuǎn)向?qū)Ｓ谩?/p>

另外，本文提出的兩種緩存結(jié)構(gòu)只是一種建議方案，并非唯一方案。雖然延遲略有增加，但節(jié)省的晶體管可以部署更多的處理器核，1 MB的LLC相當(dāng)于四個(gè)cortex-A8處理器核所占面積[2]，這對(duì)于高并發(fā)、高吞吐的大數(shù)據(jù)應(yīng)用尤為重要。

6 結(jié)束語(yǔ)

當(dāng)前數(shù)據(jù)中心采用的多核/眾核處理器在處理大數(shù)據(jù)應(yīng)用時(shí)緩存資源利用率不高。通過(guò)剖析部分大數(shù)據(jù)應(yīng)用的訪存行為，發(fā)現(xiàn)L1緩存命中率高、L2緩存和LLC命中率低，這是與大數(shù)據(jù)應(yīng)用線程間數(shù)據(jù)共享度低、數(shù)據(jù)離散、訪存隨機(jī)的特點(diǎn)相關(guān)的。本文提出了兩種緩存結(jié)構(gòu)設(shè)計(jì)方案，一種是共享緩存的Share結(jié)構(gòu)，一種是私有緩存和共享緩存分離的Partition結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，在只有一級(jí)緩存的情況下，延遲并沒(méi)有顯著增加，芯片面積大幅減小，當(dāng)緩存容量較低時(shí)，Partition結(jié)構(gòu)要優(yōu)于Share結(jié)構(gòu)。隨著緩存容量的增加Partition結(jié)構(gòu)的優(yōu)勢(shì)不再明顯，采用Share結(jié)構(gòu)會(huì)更好，對(duì)于眾核處理器來(lái)講，由于核數(shù)眾多，分配到每個(gè)處理器核的緩存容量不會(huì)太大，因此，Partition結(jié)構(gòu)在緩存容量較小時(shí)有一定優(yōu)勢(shì)。

[1] Wang Yuan-zhuo,Jin Xiao-long,Cheng Xue-qi.Network big data:Present and future [J]. Chinese Journal of Computers, 2013, 36(6):1-15.(in Chinese)

[2] Lotfi-Kamran P, Grot B, Ferdman M, et al. Scale-out processors[C]∥Proc of the 39th Annual International Symposium on Computer Architecture, 2012:500-511.

[3] Ferdman M,Adileh A,Kocberber O,et al.Clearing the clouds:A study of emerging scale-out workloads on modern hardware [C]∥Proc of the 17th International Conference on ASPLOS, 2012:37-48.

[4] Chilimbi T M,Hill M D,Larus J R. Cache-conscious structure layout[J].ACM SIGPLAN Notices, 1999, 34(5):1-12.

[5] Ding X,Wang K, Zhang X. ULCC:A user-level facility for optimizing shared cache performance on multicores [C]∥Proc of the 16th ACM Symposium on PPoPP, 2011:103-112.

[6] Jia Y, Wu C, Zhang Z. Programs performance profiling optimization for guiding static cache partitioning[J]. Journal of Computer Research and Development, 2012,49(1):93-102.(in Chinese)

[7] Kim S, Chandra D, Solihin Y. Fair cache sharing and partitioning in a chip multiprocessor architecture [C]∥Proc of the 13th International Conference on PACT, 2004:111-122.

[8] Tullsen D M, Eggers S J, Levy H M. Simultaneous multithreading:Maximizing on-chip parallelism [C]∥Proc of the 22nd Annual International Symposium on Computer Architecture,1995:533-544.

[9] Zhan J,Zhang L,Sun N,et al.High volume throughput computing:Identifying and characterizing throughput oriented workloads in data centers[C]∥Proc of the IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, 2012:1712-1721.

[10] Bienia C, Kumar S. The PARSEC benchmark suite:Characterization and architectural implications[C]∥Proc of the 17th ACM International Conference on Parallel Architectures and Compilation Techniques, 2008:1-22.

[11] Chen Y, Li W, Kim C, et al. Efficient shared Cache management through sharing-aware replacement and streaming-aware insertion policy [C]∥Proc of IEEE International Parallel & Distributed Processing Symposium, 2009:1-11.

[12] Luk C K, Cohn R, Muth R, et al, Pin:Building customized program analysis tools with dynamic instrumentation [C]∥Proc of the 2005 ACM SIGPLAN Conference on PLDI,2005:190-200.

附中文參考文獻(xiàn)：

[1] 王元卓,靳小龍,程學(xué)旗. 網(wǎng)絡(luò)大數(shù)據(jù):現(xiàn)狀與展望 [J].計(jì)算機(jī)學(xué)報(bào), 2013,36(6):1-15.

[6] 賈耀倉(cāng),武成崗,張兆慶. 指導(dǎo)Cache靜態(tài)劃分的程序性能profiling優(yōu)化技術(shù)[J]. 計(jì)算機(jī)研究與發(fā)展,2012,49(1):93-102.

WAN Hu,born in 1991,MS candidate,CCF member(E200041112G)，his research interest includes computer architecture for big data.

徐遠(yuǎn)超(1975-),男，湖北武漢人，博士，講師，CCF會(huì)員(E200007824M)，研究方向?yàn)槊嫦虼髷?shù)據(jù)的計(jì)算機(jī)體系結(jié)構(gòu)。E-mail:xuyuanchao@ict.ac.cn

XU Yuan-chao,born in 1975,PhD,lecturer,CCF member(E200007824M)，his research interest includes computer architecture for big data.

孫鳳蕓(1989-),女，河南新鄉(xiāng)人，碩士生，CCF會(huì)員(E200041151G)，研究方向?yàn)槊嫦虼髷?shù)據(jù)的計(jì)算機(jī)體系結(jié)構(gòu)。E-mail:kycg2012@126.com

SUN Feng-yun,born in 1989,MS candidate,CCF member(E200041151G)，her research interest includes computer architecture for big data.

閆俊峰(1991-),女，山東濰坊人，碩士生，研究方向?yàn)槊嫦虼髷?shù)據(jù)的計(jì)算機(jī)體系結(jié)構(gòu)。E-mail:1256834897@qq.com

YAN Jun-feng,born in 1991,MS candidate,her research interest includes computer architecture for big data.

Cache structure design for big data oriented many-core processor

WAN Hu1,XU Yuan-chao1,2,SUN Feng-yun1,YAN Jun-feng1

(1.College of Information Engineering,Capital Normal University,Beijing 100048;

Some big data applications such as data sorting, search engine, streaming media running on the traditional latency-oriented multi/many-core processor are inefficiency. The hit rate of L1 Cache is high while that of L2/L3 Cache is relative low and IPC is not sensitive to LLC capacity. To address the low utilization issue of cache resources, we analyze the memory access patterns of big data applications, and then propose an optimization method of cache structure for many-core processor. Both the two structures only have L1 cache, while one is fully shared cache structure, and the other is partly shared cache partition structure. The evaluation results show that these two schemes can significantly save chip area at the cost of slightly increase of memory access. When cache capacity is low, the partition structure is superior to the share structure. As cache capacity increases, the share structure will gradually become superior to the partition structure. For many-core processors, the capacity assigned to each processor is limited, thus the partition structure has certain advantages.

many-core processor;big data application;cache design;memory access behavior;data center

1007-130X(2015)01-0028-08

2014-05-17;

2014-10-20基金項(xiàng)目：北京市自然科學(xué)基金資助項(xiàng)目(4143060)；北京市教委科技發(fā)展面上資助項(xiàng)目(KM201210028004)；計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題(CARCH201203)；“高可靠嵌入式系統(tǒng)技術(shù)”北京市工程研究中心；北京市屬高等學(xué)校人才強(qiáng)教項(xiàng)目-國(guó)外訪學(xué)(135300100)

TP316

A

10.3969/j.issn.1007-130X.2015.01.005

萬(wàn)虎(1991-),男，安徽宿州人，碩士生，CCF會(huì)員(E200041112G)，研究方向?yàn)槊嫦虼髷?shù)據(jù)的計(jì)算機(jī)體系結(jié)構(gòu)。E-mail:wanhu@cnu.edu.cn

通信地址：100048 北京市海淀區(qū)西三環(huán)北路56號(hào)首都師范大學(xué)信息工程學(xué)院

Address:College of Information & Engineering,Capital Normal University,56 Xisanhuan North Rd,Haidian District,Beijing 100048,P.R.China