粗粒度可重構(gòu)陣列分支指令的優(yōu)化設(shè)計與實現(xiàn)

汪翔

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

0 引言

粗粒度可重構(gòu)陣列（Coarse-Grained Reconfigurable Array，CGRA）[1-4]是一種由運算處理單元，訪存單元，控制單元等組成的字級可重構(gòu)體系結(jié)構(gòu)。它具有較高的執(zhí)行能效，又能滿足靈活性要求，是一種具有前景的異構(gòu)加速器解決方案。CGRA 在運行時通過重新配置陣列結(jié)構(gòu)來執(zhí)行各種應(yīng)用程序，相比于現(xiàn)場可編程門陣列（FP?GA），其字級可重構(gòu)粒度降低了功耗和面積。通過并行化和深流水化陣列運算[5]，達(dá)到提升計算能力的效果。

然而，由于基于動態(tài)數(shù)據(jù)流驅(qū)動的CGRA 缺乏傳統(tǒng)CPU 的程序計數(shù)器機(jī)制和分支預(yù)測機(jī)制，CGRA 針對分支語句的優(yōu)化有限。而相對于ASIC 來說，CGRA 在執(zhí)行分支操作時往往激活多條路徑，產(chǎn)生了較高的功耗。

當(dāng)前的CGRA 在進(jìn)行設(shè)計時通過加入SIMD 特性[6-9]以提高執(zhí)行效率和性能功耗比，而如何在數(shù)據(jù)級并行的CGRA 上實現(xiàn)分支指令的執(zhí)行也成為了CGRA研究中的一個關(guān)鍵問題。目前CGRA 的分支指令執(zhí)行技術(shù)可以分為以下三種：部分?jǐn)嘌约夹g(shù)（PP）[10]、完全斷言技術(shù)（FP）[11-12]以及雙發(fā)射單執(zhí)行技術(shù)（DISE）[13]。

針對圖1（a）所示的基本分支語句，使用部分?jǐn)嘌约夹g(shù)進(jìn)行映射的偽代碼如圖1（b）所示，針對兩條分支語句分別進(jìn)行函數(shù)計算，最后通過sel 操作選出運算結(jié)果，并存儲到對應(yīng)的數(shù)據(jù)地址上。將該代碼映射在CGRA 上的數(shù)據(jù)流圖如圖1（c）所示，該方法同時執(zhí)行兩條路徑，最后通過多選器選出結(jié)果操作數(shù)，優(yōu)點在于架構(gòu)修改小，適合執(zhí)行分支路徑較短的語句，缺點在于需要同時執(zhí)行兩條路徑，造成不必要的功耗和性能開銷，傳統(tǒng)的靜態(tài)配置CGRA 便是基于這一技術(shù)進(jìn)行分支執(zhí)行。完全斷言技術(shù)（FP）要求在指令字中加入額外的條件操作指令位或者引入額外的AWAKE、SLEEP狀態(tài)控制PE 對于特定的指令是否進(jìn)行執(zhí)行，但該技術(shù)要求每個PE 內(nèi)部添加一個計數(shù)器和一個狀態(tài)寄存器。雙發(fā)射單執(zhí)行技術(shù)（DISE）要求PE 一次取來兩條分支指令，但是只執(zhí)行其中的一條指令，但這要求了PE 需要具有執(zhí)行兩條不同類型指令的能力，并且提高了指令帶寬的需求。

圖1 CGRA部分?jǐn)嘌苑种в成浞桨?/p>

為實現(xiàn)在CGRA 上執(zhí)行分支指令時功耗、性能以及資源量的優(yōu)化，本文提出一種針對CGRA 的分支實現(xiàn)優(yōu)化方法，通過控制實際運算是否執(zhí)行大幅減少實際運算資源的開銷，實現(xiàn)性能和功耗的優(yōu)化，另外，該技術(shù)能有效簡明地支持嵌套分支結(jié)構(gòu)。

1 CGRA分支執(zhí)行方案設(shè)計

為了解決當(dāng)前CGRA 中的分支實現(xiàn)仍然存在著難以實現(xiàn)嵌套分支，分支實現(xiàn)功耗較高和分支實現(xiàn)性能較低的問題。本文在基于部分?jǐn)嘌约夹g(shù)的基礎(chǔ)上提出了一種優(yōu)化分支實現(xiàn)技術(shù)，該技術(shù)綁定分支位使能或禁用運算訪存操作，利用自定義的sc_if、sc_else、merge等指令修改分支位，有效簡明地支持單層分支和嵌套分支結(jié)構(gòu)。相比于部分?jǐn)嘌约夹g(shù)，該技術(shù)禁用了未選中分支的運算操作，降低了功耗；通過消除sel 操作需要兩路輸入帶來的緊耦合性，降低了單分支語句映射的資源量；另外，該技術(shù)禁用了未選中分支的訪存操作，從而降低了片外存儲器的帶寬需求，有效提高了分支執(zhí)行效率。

1.1 單層分支執(zhí)行方案

針對圖1（a）所示的基本分支語句，本文可實現(xiàn)兩種分支映射方案，緊耦合類型的分支映射偽代碼如圖2（a）所示，分支映射數(shù)據(jù)流圖結(jié)構(gòu)如圖2（b）所示，松耦合類型的分支映射偽代碼如圖2（c）所示，分支映射數(shù)據(jù)流圖結(jié)構(gòu)如圖2（d）所示，為了使運算和訪存的執(zhí)行受到控制，在圖2（b）和圖2（d）數(shù)據(jù)流圖的數(shù)據(jù)位上加入分支位部分，進(jìn)行實際運算的PE 用空白背景標(biāo)注，可能進(jìn)行運算的PE 用陰影背景標(biāo)注，D_C 為分支判斷結(jié)果，h、hˉ分別表示if 和else 進(jìn)行sc_if、sc_else 操作后的輸出結(jié)果，符號“|”右邊表示分支位的當(dāng)前狀態(tài)，T（true）表示分支位有效，F(xiàn)（false）表示分支位無效，圖2（b）中，merge 節(jié)點進(jìn)行分支匯聚操作，選出分支位有效的數(shù)據(jù)流以供后級PE 做進(jìn)一步運算。

執(zhí)行分支判斷的PE 的輸出結(jié)果由一對操作sc_if和sc_else 綁定到分支位上，sc_if、sc_else、merge 節(jié)點的行為可見表1（分支位簡寫為b，數(shù)據(jù)位簡寫為d），由于D_IF 路徑和D_ELSE 路徑輸出數(shù)據(jù)由具體運算結(jié)果決定，因此除D_C 外，數(shù)據(jù)位不在輸出信號表中作標(biāo)注。在圖2（b）和圖2（d）的數(shù)據(jù)流圖中，分支位h 和hˉ控制使能運算和訪存，只有分支位有效時才會進(jìn)行實際運算和訪存，因此圖2（a）和圖2（c）中的3、4 行不會同時進(jìn)行運算操作，另外，分支位通過數(shù)據(jù)流路徑繼續(xù)向下傳輸，直到遇到merge 節(jié)點時進(jìn)行分支匯合，該節(jié)點內(nèi)部配置為一個多選器，選擇分支位有效路徑的數(shù)據(jù)輸出，從而完成一個分支指令。

圖2 映射案例

表1 路徑輸出信號表

為了去除采用merge 操作帶來的耦合性，進(jìn)一步設(shè)計了分支松耦合的映射方案，兩者區(qū)別在于：在緊耦合映射方案中，存儲目標(biāo)操作數(shù)時使用了與部分?jǐn)嘌约夹g(shù)類似的方案，利用merge 節(jié)點進(jìn)行分支合并，在store 節(jié)點中存儲目標(biāo)操作數(shù)，在松耦合映射方案中，考慮到兩路分支不會同時進(jìn)行訪存，因此可以兩路同時進(jìn)行存儲操作的映射。在單分支指令下，由于松耦合方式兩路運算無匯聚節(jié)點，可以直接去除另一路，從而進(jìn)一步簡化了映射結(jié)構(gòu)，降低了資源數(shù)量，由于部分?jǐn)嘌约夹g(shù)需要sel 操作進(jìn)行數(shù)據(jù)匹配，只能提供緊耦合式的映射方式，仍然需要另一條偽分支路徑進(jìn)行sel 操作和存儲操作，帶來了后文所述的路徑不平衡問題，大幅度提高了對帶寬的需求和對節(jié)點數(shù)量的要求。

對于分支控制位無效的數(shù)據(jù)流，PE 和訪存單元不進(jìn)行實際的計算和訪存，從而降低了ALU 運算和不必要的訪存導(dǎo)致的功耗開銷。

靜態(tài)CGRA 的缺點之一在于不平衡路徑會造成流水線的堵塞從而影響性能。由于兩條分支數(shù)據(jù)通路延時不同，并共享一個數(shù)據(jù)來源和數(shù)據(jù)匯聚點，此時便會在長路徑產(chǎn)生數(shù)據(jù)流氣泡，導(dǎo)致數(shù)據(jù)吞吐率降低。本文借鑒文獻(xiàn)[14]的做法，在短路徑上加入NOP 節(jié)點進(jìn)行路徑平衡，從而優(yōu)化了整體執(zhí)行時間。

1.2 嵌套分支優(yōu)化

針對代碼1 所示的嵌套分支進(jìn)行分支設(shè)計時，可以僅僅在圖2（b）的DFG 中進(jìn)行重復(fù)的單分支實現(xiàn)方式的擴(kuò)展，如圖3（a）所示，兩路均需要進(jìn)行嵌套分支判斷的擴(kuò)展，每個分支判斷都需要一對sc_if 和sc_else 單元，但這種方式關(guān)鍵路徑上存在著多個串行化的分支判斷，sc_if、sc_else、merge 操作，延長了嵌套分支整體執(zhí)行時間。

代碼1 嵌套分支執(zhí)行程序

為了解決嵌套分支執(zhí)行中的性能損耗問題，本文針對嵌套分支提出了優(yōu)化的執(zhí)行策略，在單分支的執(zhí)行基礎(chǔ)上增加了concat、sc_sw 操作，以代碼1 所示的嵌套分支程序為例，優(yōu)化映射方式如圖3（b）所示，使用concat 操作把兩個分支判斷結(jié)果綁定到數(shù)據(jù)位上。例如當(dāng)左路徑判斷結(jié)果為false，右路徑判斷結(jié)果為true，concat 操作綁定的數(shù)據(jù)位為1，則只有sc_sw（1）操作將數(shù)據(jù)位轉(zhuǎn)化為分支位有效的數(shù)據(jù)流，而其他路徑則置分支位無效，避免了后級繼續(xù)對該數(shù)據(jù)流進(jìn)行運算和訪存，從而降低了功耗和資源開銷。

圖3 嵌套分支映射對比

圖3（b）的設(shè)計針對資源使用進(jìn)行了優(yōu)化，對于優(yōu)化之前的圖3（a）版本，若嵌套分支層數(shù)為n(n>1)，則進(jìn)行分支判斷的PE 個數(shù)為2n-1，sc_if 和sc_else 的數(shù)量為2n+1-2，而對于優(yōu)化之后的圖3（b）版本，若PE輸入端口數(shù)為m，則concat 數(shù)量為，sc_sw 數(shù)量為2n，分支判斷PE 數(shù)量為n，兩種設(shè)計方法merge 節(jié)點數(shù)量相等，均為2n-1，可以計算出圖3（a）PE 資源數(shù)量PEs_A 與圖3（b）PE 資源數(shù)量PEs_B 及差值如下所示：可以證明ΔPEs>0 ，且隨n增大呈指數(shù)級增大趨勢。

圖3（b）的設(shè)計針對路徑延時進(jìn)行了優(yōu)化，圖3（a）映射方法的分支控制單元關(guān)鍵路徑包括n層分支判斷節(jié)點，n層sc_if 或者sc_else 節(jié)點，n層merge 節(jié)點，圖3（b）映射方法的分支控制單元關(guān)鍵路徑包括一層分支判斷PE，層CONCAT，一層SC_SW 單元，n層MERGE 節(jié)點?？梢杂嬎愠鰣D3（a）實現(xiàn)方式的路徑延時pd_A 與圖3（b）實現(xiàn)方式的路徑延時pd_B 數(shù)值及差值如下所示：可以證明Δdelay>0，且隨n 增大而增大。

從以上公式可見，優(yōu)化后的圖3（b）的設(shè)計在資源使用和性能上均優(yōu)于圖3（a）的設(shè)計。

2 硬件實現(xiàn)

2.1 陣列架構(gòu)

CGRA 陣列的整體架構(gòu)設(shè)計如圖4 所示，該陣列包括配置控制器，PE 陣列，片上緩存，執(zhí)行控制器單元。配置控制器在CGRA 運行期間提供配置信息，PE陣列進(jìn)行實際運算，片上緩存進(jìn)行片上數(shù)據(jù)存取操作，執(zhí)行控制器負(fù)責(zé)進(jìn)行陣列與CPU 和DMA 的交互。

在PE 陣列中，PE 單元負(fù)責(zé)進(jìn)行運算以及分支控制，LSE（Load Store Element）單元負(fù)責(zé)進(jìn)行訪存任務(wù)，包括為PE 提供操作數(shù)以及將數(shù)據(jù)存入存儲單元。對于分支位無效的數(shù)據(jù)流，PE 不執(zhí)行實際運算，LSE 不進(jìn)行實際的訪存，當(dāng)進(jìn)行取數(shù)操作時，LSE 將分支位無效的數(shù)據(jù)流直接返回給目標(biāo)PE，不會占用讀數(shù)所需的帶寬。當(dāng)進(jìn)行存數(shù)操作時，LSE 不執(zhí)行分支位無效數(shù)據(jù)流的訪存，從而降低了功耗和帶寬需求。

圖4 CGRA整體結(jié)構(gòu)圖

2.2 實現(xiàn)細(xì)節(jié)

在如圖4 所示的PE 和LSE 硬件結(jié)構(gòu)中，灰實線包括數(shù)據(jù)位及有效位，黑實線包括數(shù)據(jù)位和控制位，虛線表示分支位。

在PE 內(nèi)部，輸入數(shù)據(jù)通過輸入寄存器進(jìn)入控制位生成單元中，在該單元中進(jìn)行sc_if 和sc_else 指令的硬件實現(xiàn)，即將數(shù)據(jù)位的比較結(jié)果綁定到分支位上，若分支位無效，則通過旁路路徑進(jìn)入輸出寄存器。在ALU內(nèi)部，僅對分支位有效的數(shù)據(jù)流進(jìn)行真實的運算，并在ALU 的輸出端口上重新綁定輸出數(shù)據(jù)位和控制位，通過輸出寄存器在陣列中繼續(xù)驅(qū)動下級PE，借助該分支位繼續(xù)控制下級PE 和LSE 的執(zhí)行動作。

本文中的LSE 負(fù)責(zé)使用地址輸入進(jìn)行片外存儲器訪存請求，對于分支位無效的數(shù)據(jù)流，通過多選器和switch 單元形成旁路通路進(jìn)入存儲空間，而對于分支位有效的數(shù)據(jù)流，則選通到總線上進(jìn)行實際訪存請求，從而實現(xiàn)了相對于部分?jǐn)嘌约夹g(shù)的有效帶寬的降低。

3 實驗結(jié)果與分析

3.1 實驗平臺

本文基于C++搭建了一款周期精確的系統(tǒng)級行為模擬器，并借鑒了文獻(xiàn)[15]的設(shè)計方法替換了基于分支執(zhí)行優(yōu)化的PE 和LSE 結(jié)構(gòu)來進(jìn)行分支執(zhí)行性能與功耗的測試。該模擬器中包含周期精確建模的8×8PE 陣列，訪存單元和其他控制單元，片外存儲模型使用周期精確的存儲器模擬器DRAMSim2[16]以確保內(nèi)存仿真準(zhǔn)確性，在仿真參數(shù)上選擇DDR3 單元DDR3_micron_16M_8B_x8_sg15。片上功耗模型借鑒了哈佛大學(xué)研究小組提出的加速器模擬器Aladdin[17]的設(shè)計思路，借助其在40nm 標(biāo)準(zhǔn)庫上仿真得到的功耗數(shù)據(jù)構(gòu)建了功耗模型，用以評估PE 陣列運算和寄存器傳輸功耗。SRAM 功耗則借助掛載在系統(tǒng)模擬器上的CACTI 模擬器[18]進(jìn)行功耗仿真，CACTI 提供了配置文件的接口，包括SRAM 的物理組數(shù)量、塊大小等參數(shù)以準(zhǔn)確地建立訪存的功耗數(shù)據(jù)。

3.2 測試應(yīng)用選擇

本文從測試集MachSuite[19]中選擇了具有分支指令的應(yīng)用，以及一些具有典型分支行為的算法映射到PE陣列上進(jìn)行測試。其中廣度優(yōu)先搜索（BFS）包括了多層分支語句?；蛐蛄衅ヅ洌∟W）的循環(huán)間具有一定依賴性，且包含嵌套分支語句。蝶形傅里葉變換（FFT）中包括一個短單分支語句，雙調(diào)排序（BNCS）[20]包含多層循環(huán)，內(nèi)存循環(huán)由分支語句使能，二分查找（BS）主要由嵌套分支語句構(gòu)成，分支內(nèi)語句較短。

3.3 實驗結(jié)果分析

實驗設(shè)置了使用部分?jǐn)嘌苑种Ъ夹g(shù)的CGRA 作為基準(zhǔn)組，使用了分支優(yōu)化的CGRA 性能與功耗數(shù)據(jù)作為性能對照組。

本文以使用部分?jǐn)嘌苑种Ъ夹g(shù)的CGRA 的性能作為資源數(shù)量，性能，功耗基準(zhǔn)，性能和功耗對比圖進(jìn)行了歸一化處理。資源數(shù)量實驗結(jié)果如圖5（a）所示，其中BFS、FFT、BNCS 主體為單分支語句，如果使用部分?jǐn)嘌约夹g(shù)，則需要構(gòu)造一條針對else 語句的偽分支來進(jìn)行偽存取，為了進(jìn)行路徑平衡，需要加入更多的NOP節(jié)點，而在使用本文所述的分支實現(xiàn)方法時，由于在線上加入了分支位控制是否對數(shù)據(jù)流進(jìn)行實際的存取，可以僅對單分支進(jìn)行處理，因此在以上應(yīng)用中可以使用盡量少的資源數(shù)量。另外，NW、BS 算法的各分支語句的目標(biāo)操作數(shù)相對一致，對特定的目標(biāo)操作數(shù)的單分支語句較少，而本文的方法則增加了SC_SW、SC_IF、SC_ELSE 等操作帶來的資源開銷，因此資源數(shù)量相對于部分?jǐn)嘌苑种Ъ夹g(shù)相差不大。在這5 個算法上的測試結(jié)果顯示本文的設(shè)計方法能達(dá)到平均12%的資源降低。

性能和功耗實驗結(jié)果如圖5（b）和圖5（c）所示，由于基于部分?jǐn)嘌苑种Ъ夹g(shù)實現(xiàn)的BFS、FFT、BNCS 包含更多的偽存取操作，占用了更多的DRAM 帶寬，而本文所述分支實現(xiàn)技術(shù)則去除了這些偽存取操作，提高了性能和降低了功耗，而基于本文的分支實現(xiàn)技術(shù)實現(xiàn)的NW、BS 算法分支路徑相對平衡，針對單個目標(biāo)操作數(shù)的特殊運算路徑較短，由于增加了sc_sw 等操作的開銷，導(dǎo)致性能略差，而在功耗表現(xiàn)上，由于false 分支進(jìn)行的是偽運算，因此仍然可以降低一定功耗。在采用了本文的設(shè)計方法后，性能平均提高31%，功耗平均降低21%。

圖5 結(jié)果對比圖

4 結(jié)語

根據(jù)粗粒度可重構(gòu)陣列的分支實現(xiàn)問題以及現(xiàn)有解決方案的不足之處，本文提出了基于分支發(fā)散匯聚的CGRA 分支實現(xiàn)方法。對于單層分支，使用自定義的sc_if、sc_else 進(jìn)行分支發(fā)散，使用merge 操作進(jìn)行分支匯聚，通過設(shè)置分支控制位控制數(shù)據(jù)流的實際運算與訪存，從而實現(xiàn)了功耗優(yōu)化。對于嵌套分支，使用自定義的sc_sw、concat 操作進(jìn)行分支發(fā)散，同樣地使用merge 操作進(jìn)行分支匯聚，進(jìn)一步優(yōu)化了嵌套分支的實現(xiàn)效率。實驗結(jié)果也證明了基于發(fā)散匯聚的分支實現(xiàn)方式的性能與功耗優(yōu)化效果。