一種基于模擬退火的動態發射型CGRA編譯方法

楊偉東

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

0 引言

可重構架構因為其相較于ASIC的靈活性和相較于CPU的高能效比，在Dennard縮放定律逐漸失效的現在[1]，獲得了學術界和工業界的廣泛關注[2-6]。相比于FPGA（Field Programmable Gate Array），粗粒度可重構架 構（Coarse-Grained Reconfigurable Architectures，CGRA）因為其粗粒度的重構粒度，降低了重構代價，帶來更高的能效比。

傳統的CGRA屬于靜態放置靜態發射（Static Issue,Static Placement，SISP）型CGRA[7-8]，該類型的CGRA一般由指令進行驅動，需要編譯器顯式指明每條指令的執行時間和對應的處理單元，給編譯器開發帶來了較多約束，例如：計算資源的約束、存儲資源的約束、互連約束，等等。這些約束可能導致編譯器用調度效率來交換調度正確性，將優化壓力集中到編譯器上，給編譯器開發帶來了嚴峻的挑戰。而且，如果CGRA內部存在同步機制，每個處理單元（Processing Element，PE）需要等待執行時間最久的PE的任務完成，使得其他處理單元處于閑置狀態，從而導致CGRA性能降低。

針對以上問題，Zhao在文獻[9]提出一種靜態放置動態發射（Static-Placement,Dynamic-Issue，SPDI）型CGRA，通過硬件機制減少編譯器在時間域上的約束，對編譯器的開發更加友好，同時通過算子的動態執行來減小同步機制帶來的性能損失。

本文面向以上SPDI型CGRA開展編譯技術研究，充分發揮其硬件性能。

1 SPDI型CGRA架構

SPDI型CGRA主要加速程序中計算密集型循環。該類型CGRA不需要配置信息顯式指明算子的執行時間，其內部的Token Buffer機制可以根據算子的輸入操作數是否就緒以及CGRA內部的資源情況動態地決定算子的發射時間，該類型的CGRA架構如圖1所示。

圖1 SPDI型CGRA架構[9]

2 問題定義

CGRA的編譯是將需要加速的代碼編譯成CGRA配置信息的過程，該過程不僅要保證結果的正確性，還要進行調度空間探索，尋求性能最優的調度（又稱映射）方案。完整的編譯流程如圖2所示。

圖2 完整的編譯流程

調度空間探索主要研究循環映射技術，探索如何更充分地利用硬件的計算資源。SISP型CGRA循環映射方法主要借鑒軟件流水[10]的思想，通過模調度算法[11]充分利用硬件資源?；谀Ｕ{度的編譯技術[12-16]主要研究如何在更小的迭代間隔（Initiation Interval，II）下完成數據流圖（Data Flow Graph，DFG）的映射，一旦映射完成，II就是對其性能的表達（不考慮訪存沖突）。

SPDI型CGRA由于其更為寬松的約束機制，更有利于編譯器進行DFG的映射，更容易產生調度方案。但是由于其缺乏對性能的有效監督，導致不同調度方案會有著不同的性能，圖3展示了一些應用在不同的調度方案下性能的差距。

圖3 不同調度方案的性能對比

基于以上分析，和SISP的編譯技術解決的問題不同，SPDI型CGRA的編譯技術的重點和難點在于如何去進行調度空間的探索，如何從大量的調度方案中選擇正確且最優的一種調度方案。

本文設計的面向SPDI型CGRA的編譯器前端主要用來提取源代碼中的循環部分，這部分代碼會被標記，以供編譯器識別用于CGRA加速。這部分代碼在轉化成IR后會被編譯器提取出DFG，以DFG的形式作為源代碼和CGRA的媒介。DFG中的每個節點對應CGRA中每個PE所執行的一個運算，DFG中的邊（表示節點間的依賴性）對應CGRA中的互連部分，由此引出了面向CGRA的有效映射的定義，如定義1所示：

定義1（有效映射）：給定一個DFG D=（VD,ED），以及一個PE陣列G=（VG,EG），其中VD表示DFG中的節點集合，ED表示DFG中的邊的集合，VG表示PE集合，EG表示PE間支持的互連方式的集合，f（u）表示節點u映射的目標PE，f（l）表示DFG的邊l映射的互連方式。因此，一個有效映射D->G需滿足以下要求：

滿足定義1的映射，即為面向SPDI型CGRA的有效映射，可以將該映射轉換成CGRA的配置信息，從而使用CGRA來對應用進行加速。SPDI型CGRA由于缺少了時間軸上的約束，帶來了比傳統SISP型CGRA更為寬松的互連映射條件。

調度的高效性問題體現在不同的調度方案會產生不同的性能，需要選擇其中最優的方案。這是一個典型的組合優化問題，即從有限個可行解的集合中找出最優解的過程，其數學表示如式（3）所示。

式中D表示所有滿足定義1的調度映射的集合即可行解的結合，f（x）表示當前調度映射方案x下硬件的執行時間。面向SPDI型CGRA的編譯器后端的主要工作就是解決上述這個組合優化問題。

3 問題求解

基于第2節中定義的問題，基于SPDI型CGRA的編譯主要關注以下兩個問題：

（1）確定可行解的集合，即調度空間的產生；

（2）從可行解的集合中尋找最優解，即調度空間的探索。由于可行解集合的規模隨著DFG和PE規模的擴大而迅速增長，無法通過窮舉來找出最優解。

3.1 調度空間產生

調度空間的產生要求正確且盡可能全面地覆蓋所有可能的調度方案，從而更好地進行調度空間的探索。另外，由于調度空間產生和探索屬于編譯器的一部分，從利于程序員編程的角度考慮，需要自動化地產生調度空間，盡量少地需要人為干預。

進行調度空間探索要求迅速產生調度方案，基于以上考慮，采用文獻[16]中的前向貪婪和反向回溯的方法來作為本文中產生調度方案的算法。將調度方案的產生分為兩個子問題：算子的排序以及算子的放置。

對于前者，可以采用廣度優先搜索（Breadth First Search，BFS）和深度優先搜索（Depth First Search，DFS）來對DFG進行遍歷，從而得到一個一維的算子序列。在算子放置的過程中，可以采用貪婪算法，按照算子序列的順序進行放置，在放置過程中要考慮互連約束，如果出現違背定義1約束的情況，則進行回溯，直到滿足定義的1要求為止。同時，在算子放置的過程中，加入一個啟發式策略：每個處理單元所執行的算子數目盡量均衡，這樣一般會比不均衡的情況的性能更高。通過這樣的方式，可以迅速得到定義1約束的調度映射。但是貪婪算法容易陷入局部最優解，無法得到全局最優解，所以只通過此方式來得到可行解，尋找最優解的過程依賴于后續其他的算法。

上述算法可以正確地產生一個可行解，但是確定可行解的集合的問題和調度空間的探索問題有一定的耦合性，將于3.2小節中進行介紹。

3.2 調度空間探索

調度問題轉化為了一個組合優化問題，可以使用模擬退火算法進行調度空間探索，該算法主要需要考慮兩個問題：代價函數的制定和鄰域的選擇。

針對代價函數的制定有兩種方案，一種是直接在仿真器上運行，另一種是對仿真器進行建模，用表達式來對仿真器的運行結果進行近似，前者結果準確但是需要耗費大量時間，后者花費時間少，但動態發射的執行模式以及編譯時難以預知的訪存沖突，導致建模的方案較難實現，所以本文采用直接在仿真器上運行的方案。

另一個問題是鄰域的選擇，該問題也可以認為是3.1小節中調度空間的產生問題。之前的研究主要采用交換算子分配的PE的方式[17]。SPDI型架構因為不涉及時間軸的約束，不用因為DFG上兩個節點相鄰時間不為1而添加路由操作，路由開銷較小。而交換PE的方式會帶來額外的路由算子開銷，一定程度上抵消了SPDI型架構的優勢，而且直接交換PE會產生大量的不滿足定義1的非法解，不適合本文中的調度空間探索。所以本文提出通過在算子排序階段對算子順序進行交換的方式來進行鄰域的選擇，然后通過貪婪算法進行放置，以此方式來保證每次鄰域交換幾乎都能產生有效解。兩個步驟共同作為模擬退火算法中的一次迭代（算法1中的NeighborTran函數和ScheduleGen函數），以此來進行調度空間的探索。

同時，在執行模擬退火算法的過程中，記錄曾經出現過的最優解。最終的算法如下所示。

算法1：基于模擬退火的調度空間探索

輸入：經過編譯器前端得到的中間表示IR

輸出：尋優后的調度方案及其性能

4 實驗結果與分析

4.1 實驗方法

本文基于LLVM8.0.0實現了面向SPDI型CGRA的編譯器，可以將C語言編寫的應用程序轉化成SPDI型CGRA的配置信息，并通過C++編寫的SPDI型CGRA架構仿真器評估本文提出的編譯算法的效果。

表1展示了實驗所采取的CGRA的硬件參數，其中Torus的互連方式如圖1中紅色線條所示。

表1 CGRA硬件參數配置

benchmark選用來自EEMBC、MediaBench、Mach-Suit和Polybench等的循環核心。

本文將當前執行時間與理論最優執行時間的比值作為評估編譯算法性能的標準，并將文獻[9]中的編譯算法作為baseline，驗證本文編譯算法的有效性。理論最優執行時間的計算如公式（4）所示。

式中，Tbest表示理論最優執行時間，op_num表示應用中算子數量，pe_num表示陣列中PE的數目，ls_num表示應用中訪存（load和store）算子的數量，line_num表示陣列中列的數量，Niter表示循環的總迭代次數。

4.2 實驗結果

圖4展示了本文的編譯算法下不同應用的性能和文獻[9]中編譯算法下相應性能的對比。其中縱坐標為當前執行時間與理論最優執行時間的比值，即縱坐標為1時，性能為理論最大值。

圖4 不同編譯算法下性能比較

統計圖4結果發現，本文的編譯算法相比文獻[9]的算法，可獲得最高33.40%，平均19.80%的性能提升，體現了本文提出的編譯算法的有效性。

本算法導致性能提高的原因主要在于：

（1）更廣泛的調度空間。之前的調度空間的產生有其局限性，有些應用即使完全窮舉，依然無法搜索到本文算法得到的最優解。

（2）更為有效的尋優算法。

5 結語

本文針對SPDI型CGRA架構的編譯問題進行分析，將問題抽象為一個組合優化問題，并通過使用模擬退火算法解決這個組合優化問題。實驗結果顯示，本文提出的算法比之前的算法獲得了平均19.80%的性能提升。