一種針對(duì)大規(guī)模CGRA的編譯器后端設(shè)計(jì)

葉鵬飛

（上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240）

0 引言

在面向計(jì)算密集型應(yīng)用時(shí)，粗粒度可重構(gòu)架構(gòu)（CGRA）具有高加速比、高能效比和高靈活性，受到了學(xué)術(shù)界和工業(yè)界的廣泛認(rèn)可，并成為了近年來(lái)國(guó)內(nèi)外的研究熱點(diǎn)[1-8]。將一個(gè)應(yīng)用程序的循環(huán)體數(shù)據(jù)流圖（DFG）映射到CGRA的處理單元陣列（PEA）上，通過(guò)多個(gè)處理單元（PE）并行計(jì)算，即可實(shí)現(xiàn)更高的應(yīng)用加速性能。隨著半導(dǎo)體工藝的飛速的發(fā)展，CGRA上的PE數(shù)量已經(jīng)越來(lái)越多，相比GReP[1]可重構(gòu)處理器上4個(gè)4×4大小的PEA，大規(guī)模CGRA中一個(gè)PEA就可以包含64個(gè)PE。同時(shí)，CGRA面向的應(yīng)用也越來(lái)越復(fù)雜，應(yīng)用循環(huán)體內(nèi)的DFG變得越來(lái)越大，對(duì)CGRA編譯器的后端設(shè)計(jì)帶來(lái)了更大的挑戰(zhàn)[2-3]。編譯器后端負(fù)責(zé)把前端生成的程序中間表示（IR）轉(zhuǎn)化為最終目標(biāo)CGRA指令集系統(tǒng)的配置包，并盡可能保證應(yīng)用在CGRA上的高效運(yùn)行。針對(duì)大規(guī)模CGRA的諸多架構(gòu)新特性，需要設(shè)計(jì)一套新的編譯器后端流程。

1 大規(guī)模粗粒度可重構(gòu)架構(gòu)

通過(guò)RTL實(shí)現(xiàn)和測(cè)試，實(shí)驗(yàn)證明8×8是目前28nm半導(dǎo)體工藝下較合適的PEA規(guī)模。同時(shí)，為了進(jìn)一步提高CGRA的算力，PEA的數(shù)量也將進(jìn)一步擴(kuò)大。本文所針對(duì)的大規(guī)模CGRA共包含16個(gè)8×8大小的PEA，共1024個(gè)PEA，具體架構(gòu)如圖1所示。其中每4個(gè)PEA和一個(gè)協(xié)處理器組織構(gòu)成1個(gè)RPU，協(xié)處理器負(fù)責(zé)多個(gè)PEA的啟動(dòng)順序、PEA指令和數(shù)據(jù)的預(yù)取等并行計(jì)算以外的準(zhǔn)備工作，全局寄存器由同一PEA共享且支持同時(shí)讀取，主控核負(fù)責(zé)四個(gè)協(xié)處理器程序的搬運(yùn)和RPU的啟動(dòng)順序。通過(guò)RTL實(shí)現(xiàn)驗(yàn)證了該CGRA可以工作在500MHz的頻率，由此可以在8比特整型數(shù)下實(shí)現(xiàn)至少2TOPS的算力。當(dāng)CGRA上PEA的數(shù)量和規(guī)模增加后，算力提升的同時(shí)出現(xiàn)了一些大規(guī)模CGRA特有的架構(gòu)設(shè)計(jì)特點(diǎn)，接下來(lái)詳細(xì)介紹。

1.1 異構(gòu)訪存結(jié)構(gòu)

當(dāng)CGRA的規(guī)模較小時(shí)，所有的PE都是同構(gòu)的，同時(shí)支持?jǐn)?shù)據(jù)訪存和邏輯運(yùn)算[1]，但在大規(guī)模CGRA中，為同一個(gè)PEA的64個(gè)PE都設(shè)計(jì)數(shù)據(jù)訪存功能不僅給PE帶來(lái)更大的面積開銷，也給片上共享數(shù)據(jù)存儲(chǔ)器帶來(lái)更大的帶寬壓力，由此選擇部分PE設(shè)計(jì)訪存功能是較為合理的設(shè)計(jì)方案。同時(shí)綜合考慮芯片最終布局布線時(shí)的拓?fù)浣Y(jié)構(gòu)，該大規(guī)模CGRA選擇給8×8 PEA的外圍一圈PE增加了訪存功能，共28個(gè)訪存型處理單元（LSU），即圖2中的深色PE。而邏輯運(yùn)算單元由于不需要和片上共享數(shù)據(jù)存儲(chǔ)器通信，帶寬限制較小，因此所有PE都被賦予了邏輯運(yùn)算能力（ALU）。LSU和ALU功能不同，對(duì)應(yīng)有兩套不同的64位精簡(jiǎn)指令集系統(tǒng)，故在設(shè)計(jì)編譯器后端的時(shí)候不僅需要考慮到異構(gòu)訪存單元的映射限制，還需要在生成配置包時(shí)為每個(gè)PE根據(jù)其操作類型生成對(duì)應(yīng)的指令。

圖1 大規(guī)模CGRA架構(gòu)

圖2 異構(gòu)訪存結(jié)構(gòu)和PE互連方案

1.2 有限的PE互連資源

為了提供更靈活的配置方式保證應(yīng)用的通用性，CGRA上的PE可以通過(guò)一個(gè)多路選擇電路訪問(wèn)相鄰PE在上一個(gè)周期的計(jì)算結(jié)果，因此PEA上存在非常多PE間的互連線。在傳統(tǒng)CGRA中由于PEA的規(guī)模比較小，因此PE間的互連可以實(shí)現(xiàn)得非常豐富，例如GReP可重構(gòu)處理器中，每個(gè)PE可以訪問(wèn)相鄰的11個(gè)PE[4]。但是當(dāng)PE數(shù)量變多后，這樣豐富的互連資源設(shè)計(jì)必然會(huì)使PEA整體工作頻率下降，因此大規(guī)模CGRA只能實(shí)現(xiàn)相對(duì)有限的PE互連資源，再加上異構(gòu)訪存結(jié)構(gòu)的存在，不同PE的互連能力的也應(yīng)有所區(qū)別。最終，本文所針對(duì)的大規(guī)模CGRA的PE互連方案如圖2所示，主要是對(duì)經(jīng)典2D-Mesh互連結(jié)構(gòu)的改進(jìn)，其PE來(lái)源主要有以下三種：

（1）上、下、左、右四個(gè)PE

（2）上端、下端、左端、右端四個(gè)PE

（3）同行或同列距離為1、2、3、7的PE（只對(duì)LSU有效）

上述三種PE來(lái)源互相也會(huì)有所重疊，互連能力最強(qiáng)的PE在四個(gè)頂角（PE0，PE7，PE56，PE63），可以訪問(wèn)包括自身的相鄰共9個(gè)PE，互連能力最弱的PE在內(nèi)部區(qū)域的四個(gè)頂角（PE9，PE14，PE49，PE54），可以訪問(wèn)包括自身的相鄰共5個(gè)PE，64個(gè)PE的平均互連能力為7，相比GReP可重構(gòu)處理器下降了36%。

2 編譯器設(shè)計(jì)

2.1 編譯器整體流程

本文實(shí)現(xiàn)的編譯器基于LLVM開源編譯器框架，該框架對(duì)編譯過(guò)程中的不同步驟和優(yōu)化拆分為獨(dú)立的編譯路徑，編譯路徑之間可以自由組合，也可自定義新的編譯路徑，由此提高了編譯器開發(fā)的靈活性。本文的編譯器前端基于一種面向CGRA的ANSIC擴(kuò)展語(yǔ)言——GR-C，后端基于自定義編譯路徑的opt和llc工具，通過(guò)解析前端生成的中間表示，最終生成不同目標(biāo)指令集系統(tǒng)的十六進(jìn)制可執(zhí)行文件和配置包文件，具體流程如圖3所示。其中波浪框表示文本文件，矩形框表示編譯器工具，rocket和pico分別表示大規(guī)模CGRA的主控核和協(xié)處理器，由于這兩個(gè)處理器都基于RISC-V指令集系統(tǒng)，目前LLVM對(duì)RISC-V指令集系統(tǒng)的支持還不完善，因此匯編器和鏈接器用到了gcc中的現(xiàn)成工具as和ld。

編譯器前端基于LLVM的clang工具，接受以GRC語(yǔ)言描述的程序代碼作為輸入，經(jīng)過(guò)預(yù)處理、詞法分析、語(yǔ)法分析、語(yǔ)義分析等步驟，生成LLVM編譯器框架的中間表示，后端接受中間表示以后需要先分離出循環(huán)體程序代碼；再根據(jù)LLVM提供的類層次結(jié)構(gòu)解析出循環(huán)信息，包括循環(huán)深度、迭代空間、索引變量等，以及循環(huán)體內(nèi)的操作運(yùn)算集合，以ConfigIR的形式保存下來(lái)[5]；根據(jù)ConfigIR中保存的信息，建立出循環(huán)體內(nèi)程序的DFG，經(jīng)過(guò)一系列的預(yù)處理、調(diào)度和映射生成DFG在PEA上執(zhí)行的調(diào)度映射方案；再通過(guò)目標(biāo)CGRA指令集系統(tǒng)的定制代碼生成器處理，最后生成目標(biāo)CGRA的配置包。

圖3 編譯器完整流程

2.2 后端流程設(shè)計(jì)

對(duì)于CGRA這種并行計(jì)算架構(gòu)，編譯器后端流程的優(yōu)劣直接決定了應(yīng)用最終的性能，因此后端流程設(shè)計(jì)一直是CGRA研究領(lǐng)域的熱點(diǎn)。目前主流的后端流程大多基于模調(diào)度算法[6]。模調(diào)度通過(guò)將PEA在時(shí)間域上展開，使得PE可以在運(yùn)行時(shí)在多個(gè)操作之間動(dòng)態(tài)切換，有效緩解了映射DFG的壓力，由此提升了映射成功率和映射性能。本文設(shè)計(jì)的編譯器后端同樣基于模調(diào)度，具體流程如圖4所示。

寄存器分配是為了解決PE互連資源有限而增加的單獨(dú)編譯路徑，該編譯路徑通過(guò)分析DFG中的特殊節(jié)點(diǎn)，將某些原本通過(guò)PE互連實(shí)現(xiàn)的數(shù)據(jù)依賴，改用全局寄存器的讀寫來(lái)實(shí)現(xiàn)，這些特殊節(jié)點(diǎn)包括DFG中高扇入扇出的節(jié)點(diǎn)、訪問(wèn)臨時(shí)變量的節(jié)點(diǎn)，以及具有長(zhǎng)數(shù)據(jù)依賴邊的節(jié)點(diǎn)等。

在模調(diào)度之前，還需要額外對(duì)算子進(jìn)行一系列的預(yù)處理操作，包括算子平衡、路由共享[7]和存儲(chǔ)器感知優(yōu)化，這些操作基本都是對(duì)DFG進(jìn)行有效的剪枝處理，在保證DFG功能不變的前提下減少節(jié)點(diǎn)和依賴邊數(shù)量，降低了后續(xù)映射算法的難度。

圖4 編譯器后端流程

通過(guò)對(duì)DFG上的算子根據(jù)其發(fā)射時(shí)間取模PEA大小（64）的計(jì)算結(jié)果，得到算子的實(shí)際模調(diào)度發(fā)射時(shí)間后，需要構(gòu)建出DFG的映射對(duì)象PEA。由于目標(biāo)大規(guī)模CGRA采用了異構(gòu)訪存結(jié)構(gòu)和不同位置不同的PE互連方案，此時(shí)應(yīng)通過(guò)額外的描述文件作為構(gòu)建PEA的輸入，這樣才能使本文所實(shí)現(xiàn)的編譯器后端流程對(duì)大規(guī)模CGRA具備通用性和擴(kuò)展能力。

異構(gòu)映射算法基于一種前向貪心和反向回溯的啟發(fā)式算法[8]，通過(guò)改進(jìn)映射時(shí)的PE優(yōu)先級(jí)計(jì)算方法，實(shí)現(xiàn)了對(duì)異構(gòu)訪存結(jié)構(gòu)的支持，該計(jì)算公式如下:

當(dāng)DFG上的某一算子D被映射到陣列上的某一處理單元R時(shí)，首先需要先檢查沒(méi)有發(fā)生訪存型算子被映射到ALU型PE的情況，再去根據(jù)R相鄰PE的空閑程度依次映射算子。公式中NR表示該P(yáng)E通過(guò)連接其它空閑PE能訪問(wèn)到的PE數(shù)量，ND表示當(dāng)前算子D還沒(méi)有被映射的前驅(qū)和后驅(qū)節(jié)點(diǎn)的數(shù)量。當(dāng)ND小于NR時(shí)，才能滿足映射D之后，繼續(xù)映射D的前驅(qū)和后驅(qū)節(jié)點(diǎn)不會(huì)映射失敗，且NR越接近ND，該P(yáng)E的映射優(yōu)先級(jí)越高，由此間接提升后續(xù)算子的映射成功率。

得到調(diào)度映射方案后，本文實(shí)現(xiàn)的編譯器后端工具定制了一個(gè)目標(biāo)CGRA指令集系統(tǒng)的代碼生成器，通過(guò)遍歷分析映射在每個(gè)PE上的不同操作，結(jié)合其調(diào)度時(shí)間，根據(jù)其是ALU型操作還是LSU型操作生成對(duì)應(yīng)的64位指令，按PE為單位組織成配置包文件。

3 實(shí)驗(yàn)結(jié)果與分析

本文通過(guò)vcs搭建了包含目標(biāo)大規(guī)模CGRA的RTL仿真環(huán)境，該仿真環(huán)境通過(guò)讀取本文所實(shí)現(xiàn)編譯器生成的rocket、pico和PEA三層異構(gòu)架構(gòu)的可執(zhí)行文件和配置包程序，可以仿真得到應(yīng)用正確運(yùn)行的波形，由此證明了本文編譯器后端流程的正確性。

為了進(jìn)一步說(shuō)明本文編譯器后端流程設(shè)計(jì)的高效性，針對(duì)幾個(gè)典型計(jì)算密集型應(yīng)用的循環(huán)體，本文將在CGRA仿真環(huán)境得到的運(yùn)行時(shí)間和在Intel Core i5-4590傳統(tǒng)CPU平臺(tái)下的運(yùn)行時(shí)間作了比較，具體結(jié)果如表1所示。

表1 典型應(yīng)用在CGRA和CPU上的運(yùn)行時(shí)間比較

統(tǒng)計(jì)上表結(jié)果發(fā)現(xiàn)，在典型計(jì)算密集型應(yīng)用中，本文編譯器可以使得大規(guī)模CGRA相對(duì)傳統(tǒng)CPU架構(gòu)獲得平均76倍的應(yīng)用加速比，充分利用了大規(guī)模CGRA的并行計(jì)算資源，此結(jié)果驗(yàn)證了在大規(guī)模CGRA背景下本文所提出編譯器后端流程的合理性和高效性。

4 結(jié)語(yǔ)

本文針對(duì)大規(guī)模CGRA的異構(gòu)訪存結(jié)構(gòu)和有限PE互連資源的架構(gòu)特點(diǎn)，基于LLVM設(shè)計(jì)并實(shí)現(xiàn)了一套新的編譯器后端流程，該后端流程可以較容易地被集成到現(xiàn)有的編譯器工具鏈中。本文搭建了目標(biāo)CGRA的RTL仿真環(huán)境，驗(yàn)證了該編譯器后端流程所生成配置包的正確性。綜合比較典型計(jì)算密集型應(yīng)用在CGRA和CPU上的運(yùn)行時(shí)間，本文的編譯器后端流程可以實(shí)現(xiàn)平均76倍的應(yīng)用加速比，由此驗(yàn)證了本文設(shè)計(jì)的高效性。