一種針對大規模CGRA的編譯器后端設計

葉鵬飛

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

0 引言

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

1 大規模粗粒度可重構架構

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

1.1 異構訪存結構

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

圖1 大規模CGRA架構

圖2 異構訪存結構和PE互連方案

1.2 有限的PE互連資源

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

（1）上、下、左、右四個PE

（2）上端、下端、左端、右端四個PE

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

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

2 編譯器設計

2.1 編譯器整體流程

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

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

圖3 編譯器完整流程

2.2 后端流程設計

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

寄存器分配是為了解決PE互連資源有限而增加的單獨編譯路徑，該編譯路徑通過分析DFG中的特殊節點，將某些原本通過PE互連實現的數據依賴，改用全局寄存器的讀寫來實現，這些特殊節點包括DFG中高扇入扇出的節點、訪問臨時變量的節點，以及具有長數據依賴邊的節點等。

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

圖4 編譯器后端流程

通過對DFG上的算子根據其發射時間取模PEA大?。?4）的計算結果，得到算子的實際模調度發射時間后，需要構建出DFG的映射對象PEA。由于目標大規模CGRA采用了異構訪存結構和不同位置不同的PE互連方案，此時應通過額外的描述文件作為構建PEA的輸入，這樣才能使本文所實現的編譯器后端流程對大規模CGRA具備通用性和擴展能力。

異構映射算法基于一種前向貪心和反向回溯的啟發式算法[8]，通過改進映射時的PE優先級計算方法，實現了對異構訪存結構的支持，該計算公式如下:

當DFG上的某一算子D被映射到陣列上的某一處理單元R時，首先需要先檢查沒有發生訪存型算子被映射到ALU型PE的情況，再去根據R相鄰PE的空閑程度依次映射算子。公式中NR表示該PE通過連接其它空閑PE能訪問到的PE數量，ND表示當前算子D還沒有被映射的前驅和后驅節點的數量。當ND小于NR時，才能滿足映射D之后，繼續映射D的前驅和后驅節點不會映射失敗，且NR越接近ND，該PE的映射優先級越高，由此間接提升后續算子的映射成功率。

得到調度映射方案后，本文實現的編譯器后端工具定制了一個目標CGRA指令集系統的代碼生成器，通過遍歷分析映射在每個PE上的不同操作，結合其調度時間，根據其是ALU型操作還是LSU型操作生成對應的64位指令，按PE為單位組織成配置包文件。

3 實驗結果與分析

本文通過vcs搭建了包含目標大規模CGRA的RTL仿真環境，該仿真環境通過讀取本文所實現編譯器生成的rocket、pico和PEA三層異構架構的可執行文件和配置包程序，可以仿真得到應用正確運行的波形，由此證明了本文編譯器后端流程的正確性。

為了進一步說明本文編譯器后端流程設計的高效性，針對幾個典型計算密集型應用的循環體，本文將在CGRA仿真環境得到的運行時間和在Intel Core i5-4590傳統CPU平臺下的運行時間作了比較，具體結果如表1所示。

表1 典型應用在CGRA和CPU上的運行時間比較

統計上表結果發現，在典型計算密集型應用中，本文編譯器可以使得大規模CGRA相對傳統CPU架構獲得平均76倍的應用加速比，充分利用了大規模CGRA的并行計算資源，此結果驗證了在大規模CGRA背景下本文所提出編譯器后端流程的合理性和高效性。

4 結語

本文針對大規模CGRA的異構訪存結構和有限PE互連資源的架構特點，基于LLVM設計并實現了一套新的編譯器后端流程，該后端流程可以較容易地被集成到現有的編譯器工具鏈中。本文搭建了目標CGRA的RTL仿真環境，驗證了該編譯器后端流程所生成配置包的正確性。綜合比較典型計算密集型應用在CGRA和CPU上的運行時間，本文的編譯器后端流程可以實現平均76倍的應用加速比，由此驗證了本文設計的高效性。