楊偉東

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

0 引言

可重構(gòu)架構(gòu)因?yàn)槠湎噍^于ASIC的靈活性和相較于CPU的高能效比，在Dennard縮放定律逐漸失效的現(xiàn)在[1]，獲得了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[2-6]。相比于FPGA（Field Programmable Gate Array），粗粒度可重構(gòu)架 構(gòu)（Coarse-Grained Reconfigurable Architectures，CGRA）因?yàn)槠浯至６鹊闹貥?gòu)粒度，降低了重構(gòu)代價(jià)，帶來(lái)更高的能效比。

傳統(tǒng)的CGRA屬于靜態(tài)放置靜態(tài)發(fā)射（Static Issue,Static Placement，SISP）型CGRA[7-8]，該類型的CGRA一般由指令進(jìn)行驅(qū)動(dòng)，需要編譯器顯式指明每條指令的執(zhí)行時(shí)間和對(duì)應(yīng)的處理單元，給編譯器開(kāi)發(fā)帶來(lái)了較多約束，例如：計(jì)算資源的約束、存儲(chǔ)資源的約束、互連約束，等等。這些約束可能導(dǎo)致編譯器用調(diào)度效率來(lái)交換調(diào)度正確性，將優(yōu)化壓力集中到編譯器上，給編譯器開(kāi)發(fā)帶來(lái)了嚴(yán)峻的挑戰(zhàn)。而且，如果CGRA內(nèi)部存在同步機(jī)制，每個(gè)處理單元（Processing Element，PE）需要等待執(zhí)行時(shí)間最久的PE的任務(wù)完成，使得其他處理單元處于閑置狀態(tài)，從而導(dǎo)致CGRA性能降低。

針對(duì)以上問(wèn)題，Zhao在文獻(xiàn)[9]提出一種靜態(tài)放置動(dòng)態(tài)發(fā)射（Static-Placement,Dynamic-Issue，SPDI）型CGRA，通過(guò)硬件機(jī)制減少編譯器在時(shí)間域上的約束，對(duì)編譯器的開(kāi)發(fā)更加友好，同時(shí)通過(guò)算子的動(dòng)態(tài)執(zhí)行來(lái)減小同步機(jī)制帶來(lái)的性能損失。

本文面向以上SPDI型CGRA開(kāi)展編譯技術(shù)研究，充分發(fā)揮其硬件性能。

1 SPDI型CGRA架構(gòu)

SPDI型CGRA主要加速程序中計(jì)算密集型循環(huán)。該類型CGRA不需要配置信息顯式指明算子的執(zhí)行時(shí)間，其內(nèi)部的Token Buffer機(jī)制可以根據(jù)算子的輸入操作數(shù)是否就緒以及CGRA內(nèi)部的資源情況動(dòng)態(tài)地決定算子的發(fā)射時(shí)間，該類型的CGRA架構(gòu)如圖1所示。

圖1 SPDI型CGRA架構(gòu)[9]

2 問(wèn)題定義

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

圖2 完整的編譯流程

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

SPDI型CGRA由于其更為寬松的約束機(jī)制，更有利于編譯器進(jìn)行DFG的映射，更容易產(chǎn)生調(diào)度方案。但是由于其缺乏對(duì)性能的有效監(jiān)督，導(dǎo)致不同調(diào)度方案會(huì)有著不同的性能，圖3展示了一些應(yīng)用在不同的調(diào)度方案下性能的差距。

圖3 不同調(diào)度方案的性能對(duì)比

基于以上分析，和SISP的編譯技術(shù)解決的問(wèn)題不同，SPDI型CGRA的編譯技術(shù)的重點(diǎn)和難點(diǎn)在于如何去進(jìn)行調(diào)度空間的探索，如何從大量的調(diào)度方案中選擇正確且最優(yōu)的一種調(diào)度方案。

本文設(shè)計(jì)的面向SPDI型CGRA的編譯器前端主要用來(lái)提取源代碼中的循環(huán)部分，這部分代碼會(huì)被標(biāo)記，以供編譯器識(shí)別用于CGRA加速。這部分代碼在轉(zhuǎn)化成IR后會(huì)被編譯器提取出DFG，以DFG的形式作為源代碼和CGRA的媒介。DFG中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)CGRA中每個(gè)PE所執(zhí)行的一個(gè)運(yùn)算，DFG中的邊（表示節(jié)點(diǎn)間的依賴性）對(duì)應(yīng)CGRA中的互連部分，由此引出了面向CGRA的有效映射的定義，如定義1所示：

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

滿足定義1的映射，即為面向SPDI型CGRA的有效映射，可以將該映射轉(zhuǎn)換成CGRA的配置信息，從而使用CGRA來(lái)對(duì)應(yīng)用進(jìn)行加速。SPDI型CGRA由于缺少了時(shí)間軸上的約束，帶來(lái)了比傳統(tǒng)SISP型CGRA更為寬松的互連映射條件。

調(diào)度的高效性問(wèn)題體現(xiàn)在不同的調(diào)度方案會(huì)產(chǎn)生不同的性能，需要選擇其中最優(yōu)的方案。這是一個(gè)典型的組合優(yōu)化問(wèn)題，即從有限個(gè)可行解的集合中找出最優(yōu)解的過(guò)程，其數(shù)學(xué)表示如式（3）所示。

式中D表示所有滿足定義1的調(diào)度映射的集合即可行解的結(jié)合，f（x）表示當(dāng)前調(diào)度映射方案x下硬件的執(zhí)行時(shí)間。面向SPDI型CGRA的編譯器后端的主要工作就是解決上述這個(gè)組合優(yōu)化問(wèn)題。

3 問(wèn)題求解

基于第2節(jié)中定義的問(wèn)題，基于SPDI型CGRA的編譯主要關(guān)注以下兩個(gè)問(wèn)題：

（1）確定可行解的集合，即調(diào)度空間的產(chǎn)生；

（2）從可行解的集合中尋找最優(yōu)解，即調(diào)度空間的探索。由于可行解集合的規(guī)模隨著DFG和PE規(guī)模的擴(kuò)大而迅速增長(zhǎng)，無(wú)法通過(guò)窮舉來(lái)找出最優(yōu)解。

3.1 調(diào)度空間產(chǎn)生

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

進(jìn)行調(diào)度空間探索要求迅速產(chǎn)生調(diào)度方案，基于以上考慮，采用文獻(xiàn)[16]中的前向貪婪和反向回溯的方法來(lái)作為本文中產(chǎn)生調(diào)度方案的算法。將調(diào)度方案的產(chǎn)生分為兩個(gè)子問(wèn)題：算子的排序以及算子的放置。

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

上述算法可以正確地產(chǎn)生一個(gè)可行解，但是確定可行解的集合的問(wèn)題和調(diào)度空間的探索問(wèn)題有一定的耦合性，將于3.2小節(jié)中進(jìn)行介紹。

3.2 調(diào)度空間探索

調(diào)度問(wèn)題轉(zhuǎn)化為了一個(gè)組合優(yōu)化問(wèn)題，可以使用模擬退火算法進(jìn)行調(diào)度空間探索，該算法主要需要考慮兩個(gè)問(wèn)題：代價(jià)函數(shù)的制定和鄰域的選擇。

針對(duì)代價(jià)函數(shù)的制定有兩種方案，一種是直接在仿真器上運(yùn)行，另一種是對(duì)仿真器進(jìn)行建模，用表達(dá)式來(lái)對(duì)仿真器的運(yùn)行結(jié)果進(jìn)行近似，前者結(jié)果準(zhǔn)確但是需要耗費(fèi)大量時(shí)間，后者花費(fèi)時(shí)間少，但動(dòng)態(tài)發(fā)射的執(zhí)行模式以及編譯時(shí)難以預(yù)知的訪存沖突，導(dǎo)致建模的方案較難實(shí)現(xiàn)，所以本文采用直接在仿真器上運(yùn)行的方案。

另一個(gè)問(wèn)題是鄰域的選擇，該問(wèn)題也可以認(rèn)為是3.1小節(jié)中調(diào)度空間的產(chǎn)生問(wèn)題。之前的研究主要采用交換算子分配的PE的方式[17]。SPDI型架構(gòu)因?yàn)椴簧婕皶r(shí)間軸的約束，不用因?yàn)镈FG上兩個(gè)節(jié)點(diǎn)相鄰時(shí)間不為1而添加路由操作，路由開(kāi)銷較小。而交換PE的方式會(huì)帶來(lái)額外的路由算子開(kāi)銷，一定程度上抵消了SPDI型架構(gòu)的優(yōu)勢(shì)，而且直接交換PE會(huì)產(chǎn)生大量的不滿足定義1的非法解，不適合本文中的調(diào)度空間探索。所以本文提出通過(guò)在算子排序階段對(duì)算子順序進(jìn)行交換的方式來(lái)進(jìn)行鄰域的選擇，然后通過(guò)貪婪算法進(jìn)行放置，以此方式來(lái)保證每次鄰域交換幾乎都能產(chǎn)生有效解。兩個(gè)步驟共同作為模擬退火算法中的一次迭代（算法1中的NeighborTran函數(shù)和ScheduleGen函數(shù)），以此來(lái)進(jìn)行調(diào)度空間的探索。

同時(shí)，在執(zhí)行模擬退火算法的過(guò)程中，記錄曾經(jīng)出現(xiàn)過(guò)的最優(yōu)解。最終的算法如下所示。

算法1：基于模擬退火的調(diào)度空間探索

輸入：經(jīng)過(guò)編譯器前端得到的中間表示IR

輸出：尋優(yōu)后的調(diào)度方案及其性能

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

4.1 實(shí)驗(yàn)方法

本文基于LLVM8.0.0實(shí)現(xiàn)了面向SPDI型CGRA的編譯器，可以將C語(yǔ)言編寫的應(yīng)用程序轉(zhuǎn)化成SPDI型CGRA的配置信息，并通過(guò)C++編寫的SPDI型CGRA架構(gòu)仿真器評(píng)估本文提出的編譯算法的效果。

表1展示了實(shí)驗(yàn)所采取的CGRA的硬件參數(shù)，其中Torus的互連方式如圖1中紅色線條所示。

表1 CGRA硬件參數(shù)配置

benchmark選用來(lái)自EEMBC、MediaBench、Mach-Suit和Polybench等的循環(huán)核心。

本文將當(dāng)前執(zhí)行時(shí)間與理論最優(yōu)執(zhí)行時(shí)間的比值作為評(píng)估編譯算法性能的標(biāo)準(zhǔn)，并將文獻(xiàn)[9]中的編譯算法作為baseline，驗(yàn)證本文編譯算法的有效性。理論最優(yōu)執(zhí)行時(shí)間的計(jì)算如公式（4）所示。

式中，Tbest表示理論最優(yōu)執(zhí)行時(shí)間，op_num表示應(yīng)用中算子數(shù)量，pe_num表示陣列中PE的數(shù)目，ls_num表示應(yīng)用中訪存（load和store）算子的數(shù)量，line_num表示陣列中列的數(shù)量，Niter表示循環(huán)的總迭代次數(shù)。

4.2 實(shí)驗(yàn)結(jié)果

圖4展示了本文的編譯算法下不同應(yīng)用的性能和文獻(xiàn)[9]中編譯算法下相應(yīng)性能的對(duì)比。其中縱坐標(biāo)為當(dāng)前執(zhí)行時(shí)間與理論最優(yōu)執(zhí)行時(shí)間的比值，即縱坐標(biāo)為1時(shí)，性能為理論最大值。

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

統(tǒng)計(jì)圖4結(jié)果發(fā)現(xiàn)，本文的編譯算法相比文獻(xiàn)[9]的算法，可獲得最高33.40%，平均19.80%的性能提升，體現(xiàn)了本文提出的編譯算法的有效性。

本算法導(dǎo)致性能提高的原因主要在于：

（1）更廣泛的調(diào)度空間。之前的調(diào)度空間的產(chǎn)生有其局限性，有些應(yīng)用即使完全窮舉，依然無(wú)法搜索到本文算法得到的最優(yōu)解。

（2）更為有效的尋優(yōu)算法。

5 結(jié)語(yǔ)

本文針對(duì)SPDI型CGRA架構(gòu)的編譯問(wèn)題進(jìn)行分析，將問(wèn)題抽象為一個(gè)組合優(yōu)化問(wèn)題，并通過(guò)使用模擬退火算法解決這個(gè)組合優(yōu)化問(wèn)題。實(shí)驗(yàn)結(jié)果顯示，本文提出的算法比之前的算法獲得了平均19.80%的性能提升。