傅忠傳，高 洋，李 東，張澤旭，，崔平遠，李馨梅

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

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

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

1 相關(guān)背景

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

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

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

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

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

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

綜上，面向高性能計算瓦式多核研究特點為:

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

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

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

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

2 Metric多核架構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

3.1 slice劃分原理

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

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

1)單入口控制流;

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

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

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

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

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

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

3.2 slice劃分算法

以函數(shù)為單位抽取cfg流圖后，以基本塊為單位進行slice劃分.slice劃分過程為:算法首先先深遍歷函數(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é)點開始新的劃分.算法具體描述為:

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

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

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

4)標志basicblock為slice頭節(jié)點，將其壓入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)標記Pblock是以basicblock為頭節(jié)點的slice劃分的一個成員，轉(zhuǎn)向步驟8);

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

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

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

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

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

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

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

3.3 實驗結(jié)果

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

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

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

表1 slice中基本塊分布

4 結(jié)論

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

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

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

4)采用典型測試基準對算法劃分效果進行初步實驗，實驗結(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.