Metric多核子方法劃分編譯算法設(shè)計(jì)與實(shí)現(xiàn)

傅忠傳，高 洋，李 東，張澤旭，，崔平遠(yuǎn)，李馨梅

(1.哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱，fuzhongchuan@gmail.com; 2.哈爾濱工業(yè)大學(xué)航天學(xué)院，150001哈爾濱;3.東北農(nóng)業(yè)大學(xué)理學(xué)院，150030哈爾濱)

編程模型嚴(yán)重阻礙了多核處理器性能的進(jìn)一步提升，為解決編程模型瓶頸，嘗試將編程單位即函數(shù)或方法(procedure)，引入到多核處理器設(shè)計(jì)中并提出Metric(Method Centric)以方法為中心多核架構(gòu).由于函數(shù)大小不同，不便于處理器微結(jié)構(gòu)設(shè)計(jì)，為此，采用編譯技術(shù)將方法劃分為大小相近的子方法(slice).子方法內(nèi)部指令按數(shù)據(jù)流方式執(zhí)行，以最大程度地發(fā)掘應(yīng)用的并行性.以子方法為粒度執(zhí)行，將為以方法為粒度的高層優(yōu)化機(jī)制的發(fā)掘奠定基礎(chǔ).

本文基于GCC編譯工具鏈，對(duì)子方法劃分方法進(jìn)行深入研究.首先對(duì)子方法劃分原則進(jìn)行深入探討;在此基礎(chǔ)上，對(duì)算法進(jìn)行詳細(xì)設(shè)計(jì)與描述;最后，通過(guò)測(cè)試驗(yàn)證了本算法的有效性.

1 相關(guān)背景

工藝與處理器結(jié)構(gòu)設(shè)計(jì)的矛盾已引起國(guó)際學(xué)術(shù)界的密切關(guān)注，RAW等［1－2］進(jìn)行了初步嘗試.近年，在面向高性能計(jì)算的瓦式(Tiled Architecture)多核領(lǐng)域國(guó)際上競(jìng)相展開研究，其中以美國(guó)的WaveScalar和TRIPS模型、歐洲航天計(jì)劃自適應(yīng)計(jì)算組的微線程模型(Microthread)最具代表性.

得克薩斯大學(xué)奧斯汀分校的 TRIPS項(xiàng)目(Tera-op，Reliable，Intelligently adaptive Processing System)［3］和華盛頓大學(xué)的WaveScalar［4］是學(xué)術(shù)界面向高性能計(jì)算的瓦式多核的代表，其目標(biāo)為可升級(jí)的、具有萬(wàn)億次計(jì)算能力的通用單片超級(jí)計(jì)算機(jī)(Single Chip Supercomputer).

TRIPS結(jié)合了數(shù)據(jù)流和超標(biāo)量的優(yōu)點(diǎn)，以編譯器劃分的超塊(Hyper block)為單位進(jìn)行調(diào)度和執(zhí)行.TRIPS采用 EDGE(Explicit Dataflow Graph Execution)指令集來(lái)直接表達(dá)數(shù)據(jù)相關(guān)性，即在超塊內(nèi)部為數(shù)據(jù)流驅(qū)動(dòng)執(zhí)行［5］.

WaveScalar是一個(gè)更加單純的數(shù)據(jù)流瓦式多核，以編譯器劃分的Wave為單位調(diào)度和執(zhí)行.WaveScalar通過(guò)簡(jiǎn)單流水提高性能，沒(méi)有采用任何前瞻技術(shù)［6］.

TRIPS和WaveScalar均基于現(xiàn)有的編程模型，在編譯器的支持下實(shí)現(xiàn).

阿姆斯特丹大學(xué)提出了 MicroGrid計(jì)劃［7］——基于微線程模型的瓦式多核結(jié)構(gòu)，并已成為歐洲AETHER航天計(jì)劃中自適應(yīng)計(jì)算重要組成部分［8］.MicroGrid對(duì)現(xiàn)有編程模型進(jìn)行了豐富和擴(kuò)展，以C語(yǔ)言為基礎(chǔ)提出了μTC，增加了并行編程要素，使程序員在源碼級(jí)直接(explicitly)表達(dá)并行性，并以微線程(Microthread)為手段動(dòng)態(tài)調(diào)度和執(zhí)行.微線程內(nèi)部指令仍采用數(shù)據(jù)流方式執(zhí)行，即其本質(zhì)仍然是數(shù)據(jù)流.

綜上，面向高性能計(jì)算瓦式多核研究特點(diǎn)為:

1)無(wú)論是 TRIPS、WaveScalar，還是 Micro-Grid，均采用軟硬協(xié)同的設(shè)計(jì)方式，在編譯支持下將應(yīng)用劃分成為粗粒度的指令塊——超塊、Wave或者微線程，并以指令塊為單位調(diào)度和執(zhí)行.

2)為最大程度地挖掘應(yīng)用的并行性，在指令塊內(nèi)部，無(wú)論是超塊、Wave或者微線程，均按照數(shù)據(jù)流驅(qū)動(dòng)方式執(zhí)行，即從本質(zhì)上來(lái)說(shuō)都采用數(shù)據(jù)流執(zhí)行模型來(lái)解決并行度問(wèn)題.

3)在編譯支持下將應(yīng)用劃分成粗粒度的指令塊，使處理器微結(jié)構(gòu)部件的設(shè)計(jì)不依賴于全局性信息，為核心部件的分布式設(shè)計(jì)，突破可升級(jí)瓶頸提供可能.

近年來(lái)，多核在航空、航天和國(guó)防武器系統(tǒng)中的應(yīng)用，引起了國(guó)際學(xué)術(shù)界和廠商的高度關(guān)注.總之，無(wú)論在商業(yè)、航空、航天，以及國(guó)防領(lǐng)域，多核的應(yīng)用已成為歷史必然.

2 Metric多核架構(gòu)

縱觀國(guó)際上各種流行的處理器結(jié)構(gòu)，大都以指令為單位執(zhí)行，TRIPS以超塊為單位執(zhí)行，WaveS-calar以其專用的數(shù)據(jù)流指令為單位執(zhí)行、以Wave為單位調(diào)度，MicroGrid則以微線程為調(diào)度單位.但在編程模型中，函數(shù)或方法(Function/Method)卻是程序員編寫代碼的基本單位，這種編程模型與執(zhí)行模型的不一致性稱之為“方法缺陷”.

多核時(shí)代memory wall和scaling wall產(chǎn)生的根本原因在于編程模型與執(zhí)行模型的不一致性.為實(shí)現(xiàn)編程模型與執(zhí)行模型的統(tǒng)一，將編程模型中的函數(shù)，稱之為方法，引入到多核處理器結(jié)構(gòu)、微結(jié)構(gòu)設(shè)計(jì)中，提出以方法為中心多核架構(gòu)，試圖使執(zhí)行模型與編程模型相統(tǒng)一.

由于方法——即函數(shù)大小不同，不便于處理器微結(jié)構(gòu)設(shè)計(jì)，采用編譯技術(shù)將其劃分為大小相當(dāng)?shù)淖臃椒?slice).該版本的以方法為中心多核處理器稱為 Metric，也就是說(shuō) Metric特指是以slice子方法為單位執(zhí)行的多核處理器.

圖1 Metric多核架構(gòu)示意圖

3 Slice子方法劃分編譯技術(shù)研究

通過(guò)對(duì)GCC的修改，為Metric提供編譯支持，為以方法為中心模擬器的建立與驗(yàn)證奠定基礎(chǔ).編譯工具鏈整體方案如圖2所示.

設(shè)計(jì)中應(yīng)將GCC中原有的集中式寄存器文件替換為分布式寄存器文件，且編譯中無(wú)需un-SSA.基于函數(shù)的cfg圖，將函數(shù)劃分成能大小相當(dāng)?shù)募?xì)粒度的slice子方法，slice由多個(gè)基本塊組成.

如圖2中陰影所示，編譯鏈完成為:函數(shù)識(shí)別與cfg調(diào)整、訪存指令收集、slice劃分、訪存指令局部性年齡編碼建立、slice數(shù)據(jù)流化與優(yōu)化，以及slice管理等功能.

函數(shù)識(shí)別將函數(shù)區(qū)分為庫(kù)函數(shù)與用戶自定義函數(shù)2種，并分別進(jìn)行不同處理.之后，生成函數(shù)調(diào)用圖(call graph)，并根據(jù)函數(shù)調(diào)用圖進(jìn)一步將用戶定義函數(shù)分為2種情況:被庫(kù)調(diào)用和不被庫(kù)調(diào)用.被庫(kù)調(diào)用的用戶自定義函數(shù)，仍然被標(biāo)記為“系統(tǒng)”，采用系統(tǒng)庫(kù)的處理方式;不被庫(kù)調(diào)用的用戶定義函數(shù)則被標(biāo)記為“用戶”，進(jìn)行函數(shù)內(nèi)聯(lián)inline與優(yōu)化等處理.

圖2 Metric多核編譯工具鏈總體方案

編譯鏈以函數(shù)為單位對(duì)訪存指令進(jìn)行搜集，為訪存指令局部性年齡編碼建立奠定基礎(chǔ).

Metric多核處理器以編譯劃分的slice子方法為單位執(zhí)行和調(diào)度，1個(gè)slice就如同1條粗粒度的指令一樣.slice劃分將函數(shù)劃分成細(xì)粒度的子方法、slice數(shù)據(jù)流化，保證了slice內(nèi)部指令按照數(shù)據(jù)流方式執(zhí)行，以解決并行度問(wèn)題.優(yōu)化用以降低編譯代價(jià).其中，子方法劃分已成為本文討論的重點(diǎn).

3.1 slice劃分原理

編譯鏈基于函數(shù)cfg將函數(shù)劃分成細(xì)粒度的slice子方法，slice是一串連續(xù)不包含循環(huán)且具有單一入口的相關(guān)指令的序列.

子方法類似于 WaveScalar中的 Wave或TRIPS中的超塊，從形式上來(lái)說(shuō)它是函數(shù)中互聯(lián)的、單入口、非循環(huán)的有向流圖的一部分.子方法中包括多個(gè)基本塊，基本塊包括多條指令.slice劃分原則為:

1)單入口控制流;

2)slice最多包含SLICE－MAX條指令;

3)slice中的每條指令最多只能執(zhí)行1次;

4)slice從函數(shù)入口基本塊開始劃分;

5)函數(shù)中的循環(huán)結(jié)構(gòu)與函數(shù)調(diào)用，被分成獨(dú)立的slice;

6)slice劃分以函數(shù)為單位，不能跨越函數(shù)，單個(gè)slice最大為1個(gè)函數(shù)的所有指令;

從本質(zhì)上來(lái)說(shuō)，slice子方法劃分的目的是抽取數(shù)據(jù)相關(guān)鏈的最小集合，即使slice在關(guān)鍵路徑上.

3.2 slice劃分算法

以函數(shù)為單位抽取cfg流圖后，以基本塊為單位進(jìn)行slice劃分.slice劃分過(guò)程為:算法首先先深遍歷函數(shù)的CFG圖，遇到循環(huán)開始、函數(shù)調(diào)用、函數(shù)出口基本塊停止遍歷.之后，遍歷結(jié)果集中除slice頭基本塊(slice header block)之外的所有基本塊，判斷其前驅(qū)基本塊是否全部在先深遍歷結(jié)果集中，并刪除前驅(qū)不全在結(jié)果集合中的基本塊.循環(huán)開始、函數(shù)調(diào)用、函數(shù)出口基本塊做為slice頭節(jié)點(diǎn)開始新的劃分.算法具體描述為:

1)將函數(shù)入口基本塊壓入workList棧;

2)如果workList棧不為空，彈出棧頂基本塊，轉(zhuǎn)向步驟2);如果workList棧為空，本函數(shù)slice劃分完成，結(jié)束;

3)如已經(jīng)對(duì)基本塊basicblock完成劃分，轉(zhuǎn)向步驟2)，否則轉(zhuǎn)向步驟4);

4)標(biāo)志basicblock為slice頭節(jié)點(diǎn)，將其壓入slice－edge－stack棧中;

5)如果slice－edge－stack不為空，彈出棧頂基本塊Pblock鏈，轉(zhuǎn)向步驟6);如果slice－edgestack為空，轉(zhuǎn)向步驟11);

6)判斷該基本塊是否為:

條件1:函數(shù)調(diào)用基本塊

條件2:函數(shù)結(jié)束基本塊

條件3:已經(jīng)被劃分為slice

條件4:循環(huán)開始

上述條件中的任1條件成立則轉(zhuǎn)到步驟5)，否則轉(zhuǎn)向步驟7);

7)標(biāo)記Pblock是以basicblock為頭節(jié)點(diǎn)的slice劃分的一個(gè)成員，轉(zhuǎn)向步驟8);

8)遍歷Pblock基本塊的出口基本塊鏈表，將所有既不是循環(huán)開始也不是循環(huán)結(jié)束的出口基本塊壓入slice－edge－stack;

9)將Pblock鏈接到以basicblock為頭節(jié)點(diǎn)的slice鏈表的尾部，跳轉(zhuǎn)至步驟5);

10)遍歷slice鏈表中的所有基本塊，如某基本塊有多個(gè)入口基本塊，且這幾個(gè)入口基本塊并不是完全都包含在該slice鏈表中，則從slice鏈表中刪除基本塊B及其后的所有基本塊;

11)完成slice劃分，將slice鏈表指針存入頭節(jié)點(diǎn)基本塊basicblock中;

12)遍歷slice鏈表，如出口基本塊多于1個(gè)，將不包含在該slice鏈表里的所有出口基本塊壓入workList棧，跳轉(zhuǎn)至步驟2);

slice劃分使用了workList和slice－edge－stack 2個(gè)棧結(jié)構(gòu).函數(shù)中的所有基本塊形成1個(gè)雙向鏈表，并對(duì)函數(shù)入口基本塊和出口基本塊進(jìn)行標(biāo)記.

基本塊是構(gòu)成slice的基本單位，同一slice中的基本塊形成雙向鏈表.數(shù)據(jù)結(jié)構(gòu)包括相應(yīng)標(biāo)記，標(biāo)識(shí)是否為slice首基本塊，基本塊屬于哪個(gè)slice等信息.屬于某基本塊的所有指令構(gòu)成雙向鏈表.

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

本文硬件測(cè)試平臺(tái)配置為酷睿2.0 GHz、內(nèi)存2 GB，硬盤20 GB，軟件環(huán)境為Red Hat Linux 7.3.

采用6個(gè)測(cè)試程序，包括Mibench測(cè)試集中的dijkstra和susan，自編寫4個(gè)測(cè)試基準(zhǔn)為:maxscore、score-sort、lcs和math.Maxscore和score-sort針對(duì)數(shù)組操作完成最大值超找和排序，LCS完成字符串操作，math為數(shù)學(xué)運(yùn)算的代表，dijkstra和susan等針對(duì)網(wǎng)絡(luò)應(yīng)用，采用小輸入集.

sice劃分算法初步實(shí)驗(yàn)結(jié)果如表1所示，顯示了slice中平均指令數(shù)和slice內(nèi)的基本塊數(shù).可見(jiàn)，當(dāng)程序中函數(shù)數(shù)較少時(shí)，slice劃分的基本塊個(gè)數(shù)較少(≤3)，這造成slice中指令數(shù)較少，因此無(wú)法充分發(fā)揮處理器的性能.程序中函數(shù)個(gè)數(shù)較多時(shí)，slice劃分效果更好.

表1 slice中基本塊分布

4 結(jié)論

1)為解決編程模型瓶頸，嘗試將編程模型中的函數(shù)引入到多核處理器設(shè)計(jì)中，提出 Metric (Method Centric)以方法為中心多核架構(gòu).

2)由于函數(shù)大小不同，不便于處理器微結(jié)構(gòu)設(shè)計(jì)，為此采用編譯將方法劃分大小相近的子方法(slice).給出Metric編譯工具鏈設(shè)計(jì)方案.

3)對(duì)子方法劃分方法進(jìn)行深入探討，并給出算法描述.

4)采用典型測(cè)試基準(zhǔn)對(duì)算法劃分效果進(jìn)行初步實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明算法的有效性.

［1］WAINGOLD E，TAYLOR M，SARKAR V，et al.Baring it all to software:RAW machines［J］.IEEE Computer，1997，30(9):86－93.

［2］MAI K，PAASKE T，JAYASENA N，et al.Smart memories:A modular reconfigurable architecture［C］//Proceedings of the 27th Annual International Symposium on Computer Architecture.New York，NY:ACM，2000: 161－171.

［3］University of TEXAS at Austin.Fera-op Reliable Intelligently adaptive processing system ［EB/OL］.［2010－04－19］.www.cs.utexas.edu/～TRIPS/.

［4］ University of Washingon.WaveScalar［EB/OL］.［2010-04-19］.http://wavescalar.cs.washington.edu.

［5］SANKARALINGAM K，NAGARAJAN R，McDONAID R，et al.Distributed microarchitectural protocols in the trips prototype processor［C］//Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture.Washington，DC:IEEE，2006:480－491.

［6］SWANSON S，PUTNAM A，MERCALDI M，et al.Area-performance trade-offs in tiled dataflow architectures［C］//Proceedings of the 33rd Annual International Symposium on Computer Architecture.Washington，DC:IEEE，2006:314－326.

［7］University of Amsterdam.MultiProcessor System-on-Chip(MP-SoC)Design［EB/OL］.［2010－04－19］.http://www.science.uva.nl/research/csa/.

［8］BELL I，HASAASNEH N，JESSHOPE C.Supporting microthread scheduling and synchronisation in CMPs［J］.Intl J Parallel Processing，2006，34(4):1－9.