吳建宇,彭蔓蔓

(湖南大學(xué)信息科學(xué)與工程學(xué)院,長(zhǎng)沙410082)

面向多線程應(yīng)用的片上多核處理器私有LLC優(yōu)化

吳建宇,彭蔓蔓

(湖南大學(xué)信息科學(xué)與工程學(xué)院,長(zhǎng)沙410082)

片上多核處理器已逐漸取代傳統(tǒng)超標(biāo)量處理器成為集成電路設(shè)計(jì)的主流結(jié)構(gòu),但芯片的存儲(chǔ)墻問題依舊是設(shè)計(jì)的一個(gè)難題。CMP通過大容量的末級(jí)高速緩存來緩解訪存壓力。在軟件編程模式向多線程并行方式轉(zhuǎn)變的背景下,針對(duì)多線程應(yīng)用在多核處理器上的Cache訪問特征,提出一種面向私有末級(jí)Cache的優(yōu)化算法,通過硬件緩沖器記錄處理器訪存地址,從而實(shí)現(xiàn)共享數(shù)據(jù)在Cache間的傳遞機(jī)制,有效降低Cache失效開銷。實(shí)驗(yàn)結(jié)果表明,在硬件開銷不超過Cache部件0.1%的情況下,測(cè)試用例平均加速比為1.13。

片上多核處理器;存儲(chǔ)墻;末級(jí)Cache;失效開銷;緩沖器

1 概述

隨著集成電路工藝的不斷發(fā)展,晶體管的尺寸越來越小,傳統(tǒng)處理器以提高頻率、增加流水線深度和增加功能部件的方式來提高性能將無法持續(xù),片上多核處理器以功耗效率高、復(fù)雜度更低和高性價(jià)比等優(yōu)勢(shì),成為學(xué)術(shù)或工業(yè)界的主流處理器體系結(jié)構(gòu)[1-2]。當(dāng)芯片上集成的處理器核心增多,處理器對(duì)存儲(chǔ)器訪問速度、帶寬的要求隨之變高,但受主存訪問周期長(zhǎng)和片外引腳數(shù)目受限等因素的影響,存儲(chǔ)墻問題日趨嚴(yán)重。為了有效緩解處理器片外訪存的壓力,當(dāng)代處理器設(shè)計(jì)已經(jīng)將一半以上的片上晶體管資源用于最后一級(jí)高速緩存,Intel Xeon E5-2600[2]處理器僅末級(jí)Cache(Last Level Cache,LLC)容量就高達(dá)20 MB。

另一方面,軟件開發(fā)技術(shù)也在發(fā)生巨大改變,以往的并行技術(shù)只是應(yīng)用于少數(shù)的科學(xué)計(jì)算、大數(shù)據(jù)處理等專業(yè)應(yīng)用領(lǐng)域。隨著芯片內(nèi)集成處理器核數(shù)目的飛速發(fā)展,計(jì)算機(jī)編程模型正在由傳統(tǒng)串行編程向并行編程轉(zhuǎn)變,如任務(wù)并行編程模型[3-5]以開發(fā)難度低、執(zhí)行效率高等優(yōu)點(diǎn)受到廣泛研究和應(yīng)用。

本文基于LLC為私有架構(gòu),針對(duì)并行多線程應(yīng)用的訪存特點(diǎn),提出一種縮短Cache失效開銷的MAOPL (Multi-threaded Applications-oriented Approach toOptimize Private LLC)算法,其基本思想是在多線程應(yīng)用程序運(yùn)行時(shí),如果一個(gè)線程需要對(duì)共享數(shù)據(jù)進(jìn)行訪問,則將相鄰處理器私有Cache體存儲(chǔ)的有效數(shù)據(jù)通過總線調(diào)入數(shù)據(jù)請(qǐng)求處理器的本地Cache,從而降低Cache失效后的開銷。

2 研究背景

2.1 CMP存儲(chǔ)結(jié)構(gòu)

目前,多核處理器Cache通常具有多級(jí)結(jié)構(gòu)(通常為2級(jí)至3級(jí)),從L1 Cache到LLC結(jié)構(gòu)越來越復(fù)雜、速度越來越慢、容量越來越大。絕大多數(shù)的L1 Cache是私有的,但LLC存在共享和私有2種基本方式。在共享設(shè)計(jì)中,LLC統(tǒng)一編址,供所有處理器使用,因此,空間利用率高,但速度受到最大線延遲影響,訪問周期長(zhǎng)。在私有設(shè)計(jì)中,LLC被分成相互獨(dú)立的Cache塊,放置在各自處理器附近,供處理器單獨(dú)使用。在本文中稱各自處理器私有的LLC為本地Cache體,否則稱為相鄰Cache體。所有私有LLC通過一條高速總線進(jìn)行通信。因?yàn)樗接蠰LC設(shè)計(jì)簡(jiǎn)單,所以具有較快的訪問速度。但當(dāng)運(yùn)行的程序集較大時(shí),私有設(shè)計(jì)可能引發(fā)失效率增加。片上多核處理器LLC的優(yōu)化技術(shù)實(shí)質(zhì)上就是汲取2種不同設(shè)計(jì)的優(yōu)點(diǎn),減少各自的不足。

2.2 相關(guān)工作

私有LLC由于結(jié)構(gòu)相對(duì)簡(jiǎn)單,可以與處理器更緊密結(jié)合,相對(duì)共享方式,具有訪問延遲小、性能隔離等優(yōu)勢(shì),但私有LLC只能被各個(gè)處理器核單獨(dú)使用,無法根據(jù)應(yīng)用動(dòng)態(tài)調(diào)整,私有LLC結(jié)構(gòu)空間利用率相對(duì)較低。有研究表明,對(duì)大多數(shù)應(yīng)用而言,私有LLC設(shè)計(jì)具有更高的性價(jià)比[6]。

為了提高空間利用率,文獻(xiàn)[7]提出了合作式Cache(Cooperative Cache,CC)算法,通過增加一個(gè)一致性引擎(CCE)將各私有Cache連接,聚合成一個(gè)邏輯上的共享體,將本地Cache體中替換出來的塊以一定的概率放入相鄰Cache體中,稱為溢出(spilling),當(dāng)再次訪問該塊時(shí)可以直接訪問,從而降低了Cache的失效率。但CC算法只是簡(jiǎn)單地以概率控制溢出流向[8],沒有考慮應(yīng)用的行為特征,實(shí)際上合作機(jī)制效率取決于應(yīng)用的Cache行為特征。文獻(xiàn)[8]提出了一種動(dòng)態(tài)溢出(Dynamic Spill Receive, DSR)算法,通過感知上層應(yīng)用的效能來決定犧牲塊溢出的流向。文獻(xiàn)[9]認(rèn)為DSR算法是以單個(gè)應(yīng)用為單位來劃分效能,粗粒度劃分不適用于低層次溢出流向控制,進(jìn)一步提出了面向 Cache組層次的SNUG(Set-level Non-Uniformity identifier and Grouper)算法,針對(duì)Cache組不同的容量要求,實(shí)現(xiàn)犧牲塊在Cache組間的溢出機(jī)制。

文獻(xiàn)[10]考慮了處理器負(fù)載均衡和犧牲塊的可重用性問題,通過Cache總線將重用性高的犧牲塊保存至同層的其他私有LLC中,提高了Cache命中率。文獻(xiàn)[11]提出了基于應(yīng)用行為識(shí)別(BICS)的私有LLC溢出技術(shù),該技術(shù)可以在線確定應(yīng)用的Cache訪問特性,從而決策是否將犧牲塊溢出至同層的其他私有Cache體。

已有工作的重點(diǎn)在于私有LLC的合作或是多道單線程應(yīng)用的Cache行為研究,本文是針對(duì)多線程應(yīng)用在私有LLC上的行為特點(diǎn),通過降低Cache失效開銷,實(shí)現(xiàn)私有LLC優(yōu)化機(jī)制。

2.3 多線程應(yīng)用訪存分析

目前并行程序開發(fā)常用的方法是調(diào)用系統(tǒng)函數(shù)(pthread)啟動(dòng)多線程或利用并行編程語言(MPI, OpenMP,TBB[5],CILK++[4])。不同編程語言面向的環(huán)境各不相同,下面分別使用 Pthread和OpenMP環(huán)境下實(shí)現(xiàn)矩陣相乘算法來分析多線程應(yīng)用的訪存特征。原始串行實(shí)現(xiàn)部分代碼如下,本文將共享數(shù)據(jù)定義為2個(gè)或以上線程對(duì)同一地址塊進(jìn)行讀寫操作。

OpenMP是面向共享內(nèi)存的多處理器并行編程語言,適用于劃分力度較小的并行開發(fā),主要通過編譯指導(dǎo)語言來指導(dǎo)并行化,代碼如下所示。# program omp parallel for shared為編譯指導(dǎo)語句,通過該語句指導(dǎo)編譯器實(shí)現(xiàn)for循環(huán)的并行化,shared (A,B,C)表示A,B,C數(shù)組為子線程共享數(shù)據(jù)。

Pthread是由POSIX提出的一套通用線程庫(kù),通常的執(zhí)行模式采用Fork-Join形式。在開始執(zhí)行的時(shí)候,只有一個(gè)主線程存在,主線程在運(yùn)行過程中,如果碰到需要并行計(jì)算的時(shí)候,派生出子線程執(zhí)行并行任務(wù),在并行代碼結(jié)束執(zhí)行后,派生線程退出,并將執(zhí)行結(jié)果傳遞給主線程。代碼如下所示,pthread_creat(),pthread_join()函數(shù)分別用于創(chuàng)建和合并函數(shù),func指針函數(shù)用于給每個(gè)子線程分配任務(wù)。數(shù)組matrixA,matrix,matrixC作為共享數(shù)據(jù)劃分給子線程使用。

由上文的分析可知,在多線程應(yīng)用中存在共享數(shù)據(jù)用于線程間的通信、同步等操作。圖1選取了PARSEC[12]測(cè)試集中部分程序的共享數(shù)據(jù)分布圖,圖中B16～B128分別表示Cache行Block為16 Byte～128 Byte大小。從圖可知,bodytrack,x264等程序中共享數(shù)據(jù)的比例高達(dá)50%。

圖1 PARSEC部分用例共享數(shù)據(jù)分布

3 MAOPL算法

在并行應(yīng)用中,共享數(shù)據(jù)塊被多個(gè)進(jìn)程進(jìn)行讀寫操作。基于Cache的工作機(jī)制,當(dāng)任意一個(gè)處理器在讀寫共享數(shù)據(jù)發(fā)生Cache失效時(shí),會(huì)向下一級(jí)存儲(chǔ)器請(qǐng)求缺失數(shù)據(jù),每個(gè)私有Cache會(huì)在本地存儲(chǔ)一份共享數(shù)據(jù)的拷貝。由于主存與Cache的訪問開銷不在一個(gè)數(shù)量級(jí),往往LLC失效后需要上百個(gè)時(shí)鐘周期從主存讀取數(shù)據(jù)。因此MAOPL算法采用緩沖器的形式,記錄近期處理器訪問的地址。當(dāng)某個(gè)處理器訪問共享數(shù)據(jù),但本地Cache體發(fā)生失效時(shí),可以在緩存器中查找該數(shù)據(jù)所在處理器的ID,通過總線將共享數(shù)據(jù)調(diào)入本地Cache體,實(shí)現(xiàn)Cache間共享數(shù)據(jù)傳輸,極大地減少了失效開銷。

3.1 MESI一致性協(xié)議

當(dāng)系統(tǒng)中有多個(gè)處理器時(shí),同一份內(nèi)存可能會(huì)被拷貝到多個(gè)處理器的本地緩存中。為了防止多個(gè)拷貝之間的不一致,必須維護(hù)多個(gè)緩存的一致性。MESI是一種被廣泛采用的緩存一致性協(xié)議,MESI協(xié)議為每個(gè)Cache行維護(hù)2個(gè)狀態(tài)位,使得每個(gè)Cache行處于4個(gè)狀態(tài)(M,E,S,I)之一,各個(gè)狀態(tài)的含義如下:

(1)M:被修改的。處于這一狀態(tài)的數(shù)據(jù)只在本CPU中有緩存,且其數(shù)據(jù)已被修改,沒有更新到內(nèi)存中。

(2)E:獨(dú)占的。處于這一狀態(tài)的數(shù)據(jù)只在本CPU中有緩存,且其數(shù)據(jù)沒有被修改,與內(nèi)存一致。

(3)S:共享的。處于這一狀態(tài)的數(shù)據(jù)在多個(gè)CPU中有緩存。

(4)I:無效的。本CPU中的這份緩存已經(jīng)無效了。

處理器對(duì)Cache進(jìn)行讀寫操作時(shí),會(huì)觸發(fā)總線事務(wù)(BusRd:總線讀,BusRdx:總線寫)廣播給其他處理器。處理器對(duì)總線進(jìn)行偵聽,在需要時(shí)進(jìn)行相應(yīng)Cache行的狀態(tài)轉(zhuǎn)化。圖2為MESI協(xié)議狀態(tài)轉(zhuǎn)換圖,例如當(dāng)CORE0和CORE1分別保存A地址數(shù)據(jù)時(shí),當(dāng)CORE0對(duì)A地址數(shù)據(jù)進(jìn)行修改后,會(huì)引起總線事務(wù)BusRdX A,CORE1本地Cache將Tag值為 A的 Cache行的狀態(tài)由共享態(tài)變成無效態(tài)。

圖2 MESI協(xié)議狀態(tài)轉(zhuǎn)換

3.2 MAOPL總體結(jié)構(gòu)

為了記錄處理器近期的訪問地址,本文設(shè)計(jì)了一個(gè)N組的緩沖器(Buffer),與總線相連并實(shí)時(shí)偵聽總線事務(wù)。如當(dāng)CORE0讀取A地址數(shù)據(jù)時(shí),引起總線事務(wù)BusRd A,緩沖器偵聽到該事件后,分別將數(shù)據(jù)地址A、處理器ID存入緩沖器中;如果是對(duì)A地址數(shù)據(jù)進(jìn)行寫,那么在偵聽到BusRdx A后,將最新數(shù)據(jù)所在處理器ID存入地址項(xiàng)為A的緩沖器中。緩沖器采用Cache中LRU替換算法對(duì)N組數(shù)據(jù)進(jìn)行插入、提升和替換選擇等操作。在查找緩沖器項(xiàng)時(shí),采用硬件并行的查找方式。以4核CMP結(jié)構(gòu)為例,圖3表示算法的硬件拓?fù)浣Y(jié)構(gòu),表1為緩沖器中每一項(xiàng)所包含的數(shù)據(jù)。

圖3 算法總體結(jié)構(gòu)

表1 緩沖器長(zhǎng)度參數(shù)說明

3.3 算法處理步驟

MAOPL算法的基本思想是每當(dāng)發(fā)生本地Cache體失效時(shí),盡量從速度更快的相鄰Cache體中調(diào)入數(shù)據(jù),而不是訪問下一級(jí)存儲(chǔ)器。圖4為MAOPL算法流程。

圖4 MAOPL算法流程

處理器訪問LLC,如果命中則返回請(qǐng)求數(shù)據(jù);否則,LLC失效后,處理器按照訪問地址首先在緩沖器中查找是否存在該地址項(xiàng),如果緩沖器命中,命中項(xiàng)PID值(假設(shè)為CORE0)指示最新數(shù)據(jù)所在的處理器。本文引入文獻(xiàn)[7]中提出的Cache總線數(shù)據(jù)傳輸機(jī)制,將CORE0中相應(yīng)數(shù)據(jù)調(diào)入本地Cache,并將數(shù)據(jù)返回給處理器;如緩沖器失效,則從下一級(jí)存儲(chǔ)器調(diào)入數(shù)據(jù)到本地Cache,并返回給處理器。

下面以處理器COREj對(duì)A數(shù)據(jù)寫命中后引發(fā)COREi讀A數(shù)據(jù)失效的處理過程為例,進(jìn)一步闡述該算法思想,其余情況處理過程類似。圖5為算法步驟示意圖,步驟中省略了緩沖器硬件并行查找、Cache總線的數(shù)據(jù)傳輸?shù)燃?xì)節(jié)。

圖5 算法步驟示意圖

算法各模塊說明如下:

(1)Write to A:處理器COREj對(duì)A地址數(shù)據(jù)進(jìn)行寫操作。

(2)BusRdx A:為了保持?jǐn)?shù)據(jù)一致性,MESI協(xié)議引發(fā)總線BusRdx事件,使其他保存 A數(shù)據(jù)的Cache行狀態(tài)轉(zhuǎn)為無效態(tài)。同時(shí),在本文中,在緩沖器中建立相應(yīng)信息。

(3)Read miss A:處理器COREi對(duì)A地址數(shù)據(jù)進(jìn)行讀操作,因?yàn)锳被COREj修改,導(dǎo)致Cache讀失效。

(4)Detect hit A:當(dāng)Cache失效時(shí),先在緩沖器中查詢是否存在A的信息。

(5)Transport A:緩沖器命中后,根據(jù)PID值及數(shù)據(jù)的物理地址A,可在相應(yīng)的Cache塊中迅速找到數(shù)據(jù),并傳入本地Cache中。

4 實(shí)驗(yàn)平臺(tái)及結(jié)果

4.1 實(shí)驗(yàn)平臺(tái)及方法

本文所提出的算法是基于片上多核體系,末級(jí)Cache為私有結(jié)構(gòu)。實(shí)驗(yàn)采用MARSS[13]模擬器,測(cè)試集程序?yàn)镻ARSEC,操作系統(tǒng)為L(zhǎng)inux 2.6內(nèi)核,通過仿真平臺(tái)上的運(yùn)行時(shí)間來測(cè)試算法性能。MAOPL算法中緩沖器硬件及數(shù)據(jù)訪問流程通過修改模擬器的存儲(chǔ)部分實(shí)現(xiàn)。MARSS是由SUNY大學(xué)開發(fā)的一款基于X86體系結(jié)構(gòu)的全系統(tǒng)多核精確模擬器,由ptlsim和qemu 2個(gè)仿真器耦合而成,可以運(yùn)行不經(jīng)修改的操作系統(tǒng)。表2為模擬器具體的參數(shù)配置。

表2 處理器配置

PARSEC(The Princeton Application Repository for Shared-Memory Computers)由普林斯頓大學(xué)2008年開發(fā),是一個(gè)多線程應(yīng)用程序組成的測(cè)試程序集,代表了未來運(yùn)行在片上多核系統(tǒng)中的共享內(nèi)存應(yīng)用程序的發(fā)展趨勢(shì),主要包括視頻編碼技術(shù)、金融分析和圖像處理等應(yīng)用程序。本文從PARSEC測(cè)試集中選取了blackschole,bodytrack,dedup,ferret, freqmine,swaptions,vips,x264等8個(gè)測(cè)試用例,程序運(yùn)算規(guī)模采用輸入中等(simmedium)數(shù)據(jù)包。

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

在實(shí)驗(yàn)中,基于對(duì)緩沖器硬件性能的估計(jì),將Cache失效后訪問緩沖器查找時(shí)間設(shè)置為10個(gè)時(shí)鐘周期,相鄰Cache體傳輸數(shù)據(jù)到私有Cache體的時(shí)間為20個(gè)時(shí)鐘周期,即從緩沖器中查找到完成Cache間數(shù)據(jù)傳輸總開銷時(shí)間為30個(gè)時(shí)鐘周期,緩沖器組間替換策略采用LRU替換算法。考慮到測(cè)試程序工作集大小、并發(fā)線程數(shù)目等多種因素,通過實(shí)驗(yàn)發(fā)現(xiàn),緩沖器數(shù)目N取256～512較為適中。實(shí)驗(yàn)中,在緩沖器上設(shè)置了訪問和命中計(jì)數(shù)器,圖6為緩沖器的命中概率百分比。

圖6 緩沖器命中率分布

在測(cè)試程序運(yùn)行完后,取原運(yùn)行時(shí)間與本次運(yùn)行時(shí)間比值為算法的加速比,圖7為不同條件下相對(duì)于未修改前的加速比。

圖7 測(cè)試用例性能加速比

4.3 實(shí)驗(yàn)分析

4.3.1 算法性能分析及硬件開銷

有如下公式:

在式(1)中,Ttotal表示每條指令平均執(zhí)行時(shí)間;Tclock表示CPU的時(shí)鐘周期;Tmem表示訪問存儲(chǔ)器周期;CPI為平均每條指令執(zhí)行的周期數(shù)。在式(2)中,TL1,TL2分別表示第1級(jí)和第2級(jí)Cache的命中時(shí)間;HL1,HL2分別表示第1級(jí)和第2級(jí)Cache的命中率;TL2miss表示二級(jí)Cache的失效開銷。假設(shè)主存平均訪問時(shí)間為200個(gè)周期,不考慮地址轉(zhuǎn)換等其他因素,那么TL2miss為200個(gè)周期。在本文中引入緩沖器,當(dāng)L2發(fā)生miss時(shí),先查找緩沖器,若緩沖器命中,則從相應(yīng)的附近Cache讀入數(shù)據(jù),否則從主存中讀取數(shù)據(jù)。緩沖器命中總開銷TBufferHit為30周期;而緩沖器失效開銷TBufferMiss為緩沖器查找時(shí)間與訪主存時(shí)間之和,即210個(gè)周期。

若命中率Hpredict為50%,則二級(jí)Cache失效開銷由式(3)可知,TL2miss為120,與原始相比,可以較大地減少訪存時(shí)間。

令處理器核數(shù)為P個(gè),主存地址為A位,每一個(gè)Cache塊大小為B,則緩沖表中每一項(xiàng)大小M=lbP+A+1-lbB,緩沖表硬件總開銷為M×N。設(shè)處理器數(shù)目P為8,地址為A為32 bit,Cache塊大小B為64 Byte,當(dāng)緩沖器組數(shù)N為256或512,緩沖器硬件開銷分別為960 B和1 920 B,若私有Cache為2 MB大小,則緩沖器硬件開銷比例分別占整個(gè)私有

Private LLC Optimization of Chip Multi-processors Oriented to Multi-threaded Application

WU Jianyu,PENG Manman
(College of Information Science and Engineering,Hunan University,Changsha 410082,China)

The design of processors changes from traditional superscalar ones to Chip Multi-processors(CMP).CMP becomes the mainstream of computer architecture.But the memory wall problem is still one of the design challenges.With the help of large volume last level Cache,CMP succeeds to relieve memory pressure.The pattern of software programming changes toward the parallel mode.This paper presents an algorithm about Last Level Cache(LLC)optimization on CMP, based on characteristic of Cache access.By the use of the hardware buffer recording processors’access address,the algorithm enables the transfer mechanism of shared data between Caches,and reduces Cache miss penalty effectively. Experimental results show that,average speedup of test is 1.13 when the cost of hardware is less than 0.1%of Cache.

Chip Multi-processors(CMP);memory wall;Last Level Cache(LLC);failure overhead;buffer

1000-3428(2015)01-0316-06

A

TP303

10.3969/j.issn.1000-3428.2015.01.059

國(guó)家自然科學(xué)基金資助項(xiàng)目(61173037)。

吳建宇(1987-),男,碩士研究生,主研方向:計(jì)算機(jī)體系結(jié)構(gòu);彭蔓蔓,教授、博士生導(dǎo)師。

2013-12-23

2014-02-17 E-mail:jianyu_wu@yeah.net

中文引用格式:吳建宇,彭蔓蔓.面向多線程應(yīng)用的片上多核處理器私有LLC優(yōu)化[J].計(jì)算機(jī)工程,2015,41(1): 316-321.

英文引用格式:Wu Jianyu,Peng Manman.Private LLC Optimization of Chip Multi-processors Oriented to Multi-threaded Application[J].Computer Engineering,2015,41(1):316-321.