粗粒度可重構陣列分支指令的優化設計與實現

汪翔

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

0 引言

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

然而，由于基于動態數據流驅動的CGRA 缺乏傳統CPU 的程序計數器機制和分支預測機制，CGRA 針對分支語句的優化有限。而相對于ASIC 來說，CGRA 在執行分支操作時往往激活多條路徑，產生了較高的功耗。

當前的CGRA 在進行設計時通過加入SIMD 特性[6-9]以提高執行效率和性能功耗比，而如何在數據級并行的CGRA 上實現分支指令的執行也成為了CGRA研究中的一個關鍵問題。目前CGRA 的分支指令執行技術可以分為以下三種：部分斷言技術（PP）[10]、完全斷言技術（FP）[11-12]以及雙發射單執行技術（DISE）[13]。

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

圖1 CGRA部分斷言分支映射方案

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

1 CGRA分支執行方案設計

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

1.1 單層分支執行方案

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

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

圖2 映射案例

表1 路徑輸出信號表

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

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

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

1.2 嵌套分支優化

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

代碼1 嵌套分支執行程序

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

圖3 嵌套分支映射對比

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

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

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

2 硬件實現

2.1 陣列架構

CGRA 陣列的整體架構設計如圖4 所示，該陣列包括配置控制器，PE 陣列，片上緩存，執行控制器單元。配置控制器在CGRA 運行期間提供配置信息，PE陣列進行實際運算，片上緩存進行片上數據存取操作，執行控制器負責進行陣列與CPU 和DMA 的交互。

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

圖4 CGRA整體結構圖

2.2 實現細節

在如圖4 所示的PE 和LSE 硬件結構中，灰實線包括數據位及有效位，黑實線包括數據位和控制位，虛線表示分支位。

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

本文中的LSE 負責使用地址輸入進行片外存儲器訪存請求，對于分支位無效的數據流，通過多選器和switch 單元形成旁路通路進入存儲空間，而對于分支位有效的數據流，則選通到總線上進行實際訪存請求，從而實現了相對于部分斷言技術的有效帶寬的降低。

3 實驗結果與分析

3.1 實驗平臺

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

3.2 測試應用選擇

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

3.3 實驗結果分析

實驗設置了使用部分斷言分支技術的CGRA 作為基準組，使用了分支優化的CGRA 性能與功耗數據作為性能對照組。

本文以使用部分斷言分支技術的CGRA 的性能作為資源數量，性能，功耗基準，性能和功耗對比圖進行了歸一化處理。資源數量實驗結果如圖5（a）所示，其中BFS、FFT、BNCS 主體為單分支語句，如果使用部分斷言技術，則需要構造一條針對else 語句的偽分支來進行偽存取，為了進行路徑平衡，需要加入更多的NOP節點，而在使用本文所述的分支實現方法時，由于在線上加入了分支位控制是否對數據流進行實際的存取，可以僅對單分支進行處理，因此在以上應用中可以使用盡量少的資源數量。另外，NW、BS 算法的各分支語句的目標操作數相對一致，對特定的目標操作數的單分支語句較少，而本文的方法則增加了SC_SW、SC_IF、SC_ELSE 等操作帶來的資源開銷，因此資源數量相對于部分斷言分支技術相差不大。在這5 個算法上的測試結果顯示本文的設計方法能達到平均12%的資源降低。

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

圖5 結果對比圖

4 結語

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