萬 虎,徐遠超,2,孫鳳蕓,閆俊峰

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

2.中國科學院計算技術研究所計算機體系結(jié)構國家重點實驗室，北京 100190)

面向大數(shù)據(jù)應用的眾核處理器緩存結(jié)構設計*

萬 虎1,徐遠超1,2,孫鳳蕓1,閆俊峰1

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

2.中國科學院計算技術研究所計算機體系結(jié)構國家重點實驗室，北京 100190)

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

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

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

1 引言

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

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

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

2 相關研究

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

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

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

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

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

3.1 大數(shù)據(jù)應用的特點

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

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

傳統(tǒng)的以計算為中心的緩存結(jié)構延長了數(shù)據(jù)通路，難以應對大數(shù)據(jù)應用的訪存行為特點。

3.2 緩存容量敏感性分析

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

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

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

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

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

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

3.3 緩存命中率分析

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

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

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

Table 1 Cache hit rate over the number of threads

大數(shù)據(jù)應用處理的數(shù)據(jù)集巨大，為此，我們評估了數(shù)據(jù)集大小對緩存命中率的影響，結(jié)果如圖3所示。

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

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

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

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

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

4 眾核處理器緩存結(jié)構設計

4.1 基于SMT的緩存結(jié)構設計

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

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

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

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ā)出請求后到從L1緩存取得數(shù)據(jù)是四個cycles，主要是查找。查找L2緩存的延遲是八個cycles，查找L3緩存的延遲是33個cycles，向內(nèi)存控制器發(fā)出訪存請求到取回數(shù)據(jù)的時間延遲是155個cycles，LLC缺失時的平均延遲由各級緩存查找延遲和訪存延遲構成，共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%?？梢?，平均訪存延遲并沒有明顯增加，部分程序甚至還略有下降，原因在于減少了很多無效的緩存查找，縮短了訪存路徑。大容量的LLC去掉以后，節(jié)省的芯片面積可用于部署更多的處理器核以提高線程級并行度。延遲往往影響單個線程的性能，但大數(shù)據(jù)應用追求的是整體吞吐率的提升，不僅如此，緩存層次的減少避免了很多無效的緩存查找開銷，縮短了訪存路徑。

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

Figure 5 SMT-based processor core structure

4.2 讀寫策略與緩存一致性

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

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

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

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

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

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

5 實驗與分析

5.1 實驗平臺

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

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

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

Table 4 Percentage of inter-thread shared memory address access

5.2 實驗結(jié)果

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

通過自主開發(fā)的緩存模擬器，我們評估了硬件線程數(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可以看到，當緩存容量為8 KB時，Partition結(jié)構的緩存命中率普遍好于Share結(jié)構，由于一級緩存命中率大多都在90%以上，繼續(xù)提高的幅度有限。當緩存容量逐漸增大時，Partition結(jié)構的優(yōu)勢不再明顯，甚至要差于Share結(jié)構。原因在于，緩存容量增大后，沖突失效減少，線程間發(fā)生數(shù)據(jù)替換的概率降低，而Partition結(jié)構中的私有緩存空間無法得到充分利用，因為它是線程私有的。

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

5.3 分析討論

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

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

6 結(jié)束語

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

[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.

附中文參考文獻：

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

[6] 賈耀倉,武成崗,張兆慶. 指導Cache靜態(tài)劃分的程序性能profiling優(yōu)化技術[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.

徐遠超(1975-),男，湖北武漢人，博士，講師，CCF會員(E200007824M)，研究方向為面向大數(shù)據(jù)的計算機體系結(jié)構。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會員(E200041151G)，研究方向為面向大數(shù)據(jù)的計算機體系結(jié)構。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-),女，山東濰坊人，碩士生，研究方向為面向大數(shù)據(jù)的計算機體系結(jié)構。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基金項目：北京市自然科學基金資助項目(4143060)；北京市教委科技發(fā)展面上資助項目(KM201210028004)；計算機體系結(jié)構國家重點實驗室開放課題(CARCH201203)；“高可靠嵌入式系統(tǒng)技術”北京市工程研究中心；北京市屬高等學校人才強教項目-國外訪學(135300100)

TP316

A

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

萬虎(1991-),男，安徽宿州人，碩士生，CCF會員(E200041112G)，研究方向為面向大數(shù)據(jù)的計算機體系結(jié)構。E-mail:wanhu@cnu.edu.cn

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

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