Metric多核子方法劃分編譯算法設計與實現

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

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

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

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

1 相關背景

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

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

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

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

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

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

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

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

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

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

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

2 Metric多核架構

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

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

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

圖1 Metric多核架構示意圖

3 Slice子方法劃分編譯技術研究

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

設計中應將GCC中原有的集中式寄存器文件替換為分布式寄存器文件，且編譯中無需un-SSA.基于函數的cfg圖，將函數劃分成能大小相當的細粒度的slice子方法，slice由多個基本塊組成.

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

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

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

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

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

3.1 slice劃分原理

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

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

1)單入口控制流;

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

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

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

5)函數中的循環(huán)結構與函數調用，被分成獨立的slice;

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

從本質上來說，slice子方法劃分的目的是抽取數據相關鏈的最小集合，即使slice在關鍵路徑上.

3.2 slice劃分算法

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

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

2)如果workList棧不為空，彈出棧頂基本塊，轉向步驟2);如果workList棧為空，本函數slice劃分完成，結束;

3)如已經對基本塊basicblock完成劃分，轉向步驟2)，否則轉向步驟4);

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

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

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

條件1:函數調用基本塊

條件2:函數結束基本塊

條件3:已經被劃分為slice

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

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

7)標記Pblock是以basicblock為頭節(jié)點的slice劃分的一個成員，轉向步驟8);

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

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

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

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

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

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

基本塊是構成slice的基本單位，同一slice中的基本塊形成雙向鏈表.數據結構包括相應標記，標識是否為slice首基本塊，基本塊屬于哪個slice等信息.屬于某基本塊的所有指令構成雙向鏈表.

3.3 實驗結果

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

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

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

表1 slice中基本塊分布

4 結論

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

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

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

4)采用典型測試基準對算法劃分效果進行初步實驗，實驗結果表明算法的有效性.

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