吳建宇,彭蔓蔓

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

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

吳建宇,彭蔓蔓

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

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

片上多核處理器;存儲墻;末級Cache;失效開銷;緩沖器

1 概述

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

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

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

2 研究背景

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

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

2.2 相關(guān)工作

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

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

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

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

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

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

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

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

由上文的分析可知,在多線程應(yīng)用中存在共享數(shù)據(jù)用于線程間的通信、同步等操作。圖1選取了PARSEC[12]測試集中部分程序的共享數(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ù)塊被多個進(jìn)程進(jìn)行讀寫操作?；贑ache的工作機(jī)制,當(dāng)任意一個處理器在讀寫共享數(shù)據(jù)發(fā)生Cache失效時,會向下一級存儲器請求缺失數(shù)據(jù),每個私有Cache會在本地存儲一份共享數(shù)據(jù)的拷貝。由于主存與Cache的訪問開銷不在一個數(shù)量級,往往LLC失效后需要上百個時鐘周期從主存讀取數(shù)據(jù)。因此MAOPL算法采用緩沖器的形式,記錄近期處理器訪問的地址。當(dāng)某個處理器訪問共享數(shù)據(jù),但本地Cache體發(fā)生失效時,可以在緩存器中查找該數(shù)據(jù)所在處理器的ID,通過總線將共享數(shù)據(jù)調(diào)入本地Cache體,實現(xiàn)Cache間共享數(shù)據(jù)傳輸,極大地減少了失效開銷。

3.1 MESI一致性協(xié)議

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

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

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

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

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

處理器對Cache進(jìn)行讀寫操作時,會觸發(fā)總線事務(wù)(BusRd:總線讀,BusRdx:總線寫)廣播給其他處理器。處理器對總線進(jìn)行偵聽,在需要時進(jìn)行相應(yīng)Cache行的狀態(tài)轉(zhuǎn)化。圖2為MESI協(xié)議狀態(tài)轉(zhuǎn)換圖,例如當(dāng)CORE0和CORE1分別保存A地址數(shù)據(jù)時,當(dāng)CORE0對A地址數(shù)據(jù)進(jìn)行修改后,會引起總線事務(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è)計了一個N組的緩沖器(Buffer),與總線相連并實時偵聽總線事務(wù)。如當(dāng)CORE0讀取A地址數(shù)據(jù)時,引起總線事務(wù)BusRd A,緩沖器偵聽到該事件后,分別將數(shù)據(jù)地址A、處理器ID存入緩沖器中;如果是對A地址數(shù)據(jù)進(jìn)行寫,那么在偵聽到BusRdx A后,將最新數(shù)據(jù)所在處理器ID存入地址項為A的緩沖器中。緩沖器采用Cache中LRU替換算法對N組數(shù)據(jù)進(jìn)行插入、提升和替換選擇等操作。在查找緩沖器項時,采用硬件并行的查找方式。以4核CMP結(jié)構(gòu)為例,圖3表示算法的硬件拓?fù)浣Y(jié)構(gòu),表1為緩沖器中每一項所包含的數(shù)據(jù)。

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

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

3.3 算法處理步驟

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

圖4 MAOPL算法流程

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

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

圖5 算法步驟示意圖

算法各模塊說明如下:

(1)Write to A:處理器COREj對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)。同時,在本文中,在緩沖器中建立相應(yīng)信息。

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

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

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

4 實驗平臺及結(jié)果

4.1 實驗平臺及方法

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

表2 處理器配置

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

4.2 實驗結(jié)果

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

圖6 緩沖器命中率分布

在測試程序運行完后,取原運行時間與本次運行時間比值為算法的加速比,圖7為不同條件下相對于未修改前的加速比。

圖7 測試用例性能加速比

4.3 實驗分析

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

有如下公式:

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

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

令處理器核數(shù)為P個,主存地址為A位,每一個Cache塊大小為B,則緩沖表中每一項大小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大小,則緩沖器硬件開銷比例分別占整個私有

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

國家自然科學(xué)基金資助項目(61173037)。

吳建宇(1987-),男,碩士研究生,主研方向:計算機(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ī)工程,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.