一種基于控制流解耦的可重構陣列動態調度方法

尹 琛，彭 飛，景乃鋒

（1.上海交通大學 電子信息與電氣工程學院，上海 200240；2.上海航天電子技術研究所，上海 201109）

0 引言

粗粒度可 重構陣列（Coarse-Grained Reconfigurable Array，CGRA）由于兼具通用計算的靈活性和專用計算的高效性，被廣泛運用在特定領域中。整個陣列由大量執行單元（Processing Element，PE）以數據流驅動的模式執行操作。PE 之間通過軟流水的執行模式實現操作，一旦輸入數據有效，PE 便可以并行執行，這種計算方式極大地提高了陣列的計算吞吐率。

隨著可重構陣列的應用范圍擴大，當采用傳統的直接調度方案，將整個數據流圖（Data Flow Graph，DFG）同時映射時，會因控制流的非一致性導致處于不同控制體的數據流無法同時并行執行，進而引起陣列計算單元利用率下降的問題。常見的非一致性控制流有非完美循環、分支以及循環依賴等。針對非完美循環，可以通過循環交換和循環展開，對內層循環體和外層循環體進行重新組織，但并沒有解決執行外層循環PE 利用率低的問題［1-4］；針對分支，通過將不同分支上的指令合并映射到同一PE 上以提高PE 利用率，但這種方法不適用于路徑長度差異較大的非平衡分支［5-6］；針對循環依賴，通過利用線程間通信挖掘細粒度的數據并行，但是會引入額外的硬件開銷［7-8］。此外，現有的數據流調度方法都只針對其中某一種非一致性控制流進行調度優化，無法同時支持上述3 種情形。

針對上述問題，本文提出了一種基于控制流解耦的可重構陣列映射方法。如圖1 所示，通過將原始DFG 中的數據流按照不同的控制流邊界解耦成若干個相互獨立的數據流子圖（Sub-DFG），各個解耦后的子圖可以獨立執行，因此，可以通過循環完全展開的方式盡可能地利用計算資源。同時通過交替執行不同的子圖，以完成整個應用的操作。借助這種控制流解耦的調度方法，在陣列總面積開銷相同的條件下，相比于靜態調度的CGRA［9］和完全指令驅動的CGRA［10］，本方法可以分別提高35%和18%的執行性能，同時提升27%和45%的計算能效比。

圖1 控制流解耦調度方法的基本示意圖Fig.1 Basic schematic diagram of the control flow decoupling and scheduling method

1 非一致性控制流分析

本章如圖2 所示，將對3 種常見的非一致性控制流的執行特點進行分析，并闡述這種非一致性在軟流水執行模式下對陣列性能的影響。

圖2 3 種典型的非一致性控制流Fig.2 Three typical inconsistent control flows

圖2（a）以通用矩陣乘該應用為例，對非完美循環進行闡述。圖2（a）上方代碼，內層循環體（實線框所示）每執行block_size次，外層循環體（虛線框所示）才執行一次；由于非完美循環中內外層循環的觸發頻率不同，導致執行外層循環的PE（斜線陰影所示）大部分時間處于空閑狀態，因此，會降低PE 利用率。

圖2（b）以稀疏向量乘該應用為例，對分支執行進行闡述。圖2（b）上方代碼，if 分支和else 分支會根據分支的判斷條件選擇性執行，不會同時執行。圖2（b）下圖，執行if 分支的PE（斜線陰影所示）和執行else 分支的PE（格子陰影所示）在任意時刻都必定有一方處于空閑狀態。因此，同樣會降低PE 利用率。

圖2（c）以LU 分解為例，對循環依賴進行闡述。圖2（c）上方代碼，具有數據依賴的執行體（虛線框和實線框所示）無法同時并行執行。圖2（c）下圖，執行這2 塊區域的PE（斜線陰影和格子陰影）會交替處于空閑狀態，進而會降低PE 的利用率。

以上3 種非一致性控制流都會將原始的DFG分割成具有不同控制語義的區域。在軟流水的執行模式下，這些區域內的數據流無法并行執行，因此，會顯著降低陣列中計算單元的利用效率，進而影響陣列的執行性能。

2 基于控制流解耦的調度方案及硬件架構設計

針對以上問題，本文提出了一種基于控制流解耦的調度方案。在軟件調度上，將原始的DFG按照不同的控制流邊界分割成若干個相互獨立的子圖，子圖間可以并行展開執行。在硬件結構上，本文提出了一種動態子圖調度器，可以根據數據流的執行情況，切換陣列當前所執行的子圖配置。同時，本文在傳統的PE 內部增加了一個配置切換單元，以支持軟流水執行模式下子圖配置的動態切換。

2.1 基于子圖分割的控制流解耦

調度方法的整體示意圖如圖1 所示，相比于現有的調度方法，將程序中所有的控制流區域同時映射在整個陣列上，將不同的控制流區域解耦成若干個子圖，并將每個子圖經過充分循環展開后獨立映射在整個陣列上。通過交替執行所有的子圖，以實現子圖間的解耦調度，消除子圖間由于非一致性控制流造成的性能損失。如圖3 所示，將對圖1 中的3 個例子分別進行詳細闡述。

圖3 基于控制流解耦的調度方法Fig.3 Mapping with control flow decoupling

圖3（a）闡述的是針對非完美循環的控制流解耦調度。首先，將外層循環（子圖1）在整個陣列上循環展開2 次并行執行，如圖3（a）兩個虛線框所示，并將中間數據k_row［］和temp［］存入片上緩存的相應區域。當片上緩存的相應區域存滿之后，再切換陣列配置執行內層循環（子圖2），并從緩存中讀出之前存入的中間數據k_row［］和temp［］。通過交替執行子圖1 和子圖2，實現控制流解耦。

圖3（b）闡述的是針對分支的控制流解耦調度。首先，執行所有的分支判斷條件，將執行false 分支的中間變量（i1，i2）和執行true 分支的中間變量（i1，i2）分別存在片上緩存的相應區域。之后將false 分支（子圖1）在陣列上并行展開2 次同時執行，如圖3（b）中2 個虛線框所示；當false 分支全部執行完后，或片上緩存中存放false 分支中間數據的相應區域滿后，再切換陣列配置執行true 分支（子圖2）。同樣，2 個子圖交替執行，實現控制流解耦。

圖3（c）闡述的是循環依賴解耦調度。與上述2種解耦類似，通過分別執行具有數據依賴關系的2 個子圖，實現控制流解耦。同樣，在執行單個子圖時，對其進行充分的循環展開以盡可能利用片上資源。

2.2 子圖動態調度器

為支持上述子圖間的動態調度，本文設計了一個子圖調度器，如圖4 所示。由于每個子圖執行所需要的數據和產生的中間數據都存放在片上緩存相應的子存儲器（bank）內。因此，如果當前子圖已經消耗完對應bank 中所有的數據或者產生的中間數據已經將對應bank 放滿，則需要結束當前子圖，切換為下一個子圖。此時，子圖調度器會根據當前存儲器中bank 的狀態，通過子圖檢測電路判斷出當前每個子圖的狀態，然后，通過優先編碼器從已經準備就緒的子圖中，動態選出一個作為接下來要執行的子圖，并將該子圖的ID 綁定在數據流上，發送給陣列。

圖4 子圖動態調度器硬件結構Fig.4 Structure of the dynamical scheduler of a subgraph

2.3 支持子圖切換的PE 單元設計

為支持上述子圖配置的動態切換，在現有的PE結構中增加一個配置切換單元，如圖5 所示。配置切換單元中會記錄當前子圖ID，并同時監測每個周期攜帶在輸入數據上的子圖ID。當輸入數據上的子圖ID 和記錄的子圖ID 不同時，將觸發配置切換，同時更新當前記錄的子圖ID。配置單元會根據新子圖ID 從配置緩存器中讀出相應的一個新配置，并通過配置更新電路逐級改變PE 的配置信息，其中包括輸入數據選擇器（Mux）、輸出數據選擇器（Demux）和算術邏輯單元（Arithmetic and Logic Unit，ALU）配置。

圖5 支持子圖切換的PE 內部結構Fig.5 Inner structure of PE with subgraph switching

按上述方式，PE 內部的配置信息可以隨數據流逐級切換。對于PE 內部的某一流水級而言，在當前周期完成子圖配置更新后，在下一周期即可執行更新后的子圖所對應的數據流。因此，可以避免現有的動態配置切換技術中，由于在流水線中引入氣泡所導致的流水線停頓現象［11］。

3 實驗結果與分析

3.1 實驗設置

從3 種專用加速器領域廣泛使用的測試集中選擇了多個含非一致性控制流的代表性應用，見表1。

表1 用于進行評估對比的測試應用Tab.1 Workloads for evaluation

為了對比分析，本文選用了2 種典型的CGRA結構，2 種結構分別是完全靜態配置的Plasticine［9］和指令調度的TIA［10］。為了公平比較，本文將通過對3 種架構設定不同的陣列大小，使其具有相同的陣列面積，其中，3 種架構的具體配置參數見表2。

表2 架構參數設定Tab.2 Architecture parameter setting

性能評估方面，采用的試驗平臺是基于C++編寫的系統級模擬器。模擬器含周期精確的PE 陣列和64 kB 片上緩存，同時使用了周期精確的DRAMSim2 仿真器［15］對內存延遲和帶寬進行評估。對于Plasticine［9］和TIA［10］2 種結構，通過提供的開源實例進行了行為級建模。此外，選用了一種靈活的片上存儲模型Buffets［16］作為3 種架構的片上訪存接口。面積評估方面，本文通過Synopsys 的Design Compiler 在40 nm 工藝庫下對3 種架構的硬件實現進行綜合，設定時鐘約束都為800 MHz。同時，通過Synopsys PrimeTime 對3 種架構的功耗進行評估。

3.2 性能和PE 利用率評估

3 種架構的性能和PE 利用率如圖6 所示。其中，當子圖個數為m，第i個子圖執行的周期數為Ti，有效映射PE 數量為Ni，周期t時刻處于激活狀態的PE 數量為nt時，PE 利用率為

圖6 3 種架構間PE 利用率（散點圖）和性能加速比（柱狀圖）的對比（以文獻［9］為基準）Fig.6 Comparison of PE utilization ratio（in marker）and performance acceleration ratio（in bar）among three architectures normalized to Plasticine［9］

式中：r為PE 利用率。

對于包含非完美循環的應用，如GEMM 通用矩陣乘、Viterbi 動態規劃和Gesummv 而言，外層循環所占比例和內層循環相當，完全靜態調度的Plasticine 中幾乎有50%的PE 處于閑置狀態。TIA 和本文提出的設計可以分別通過靈活的指令和子圖級別的調度，將PE 利用率提升到80%左右。本文的設計相比Plasticine 取得了約為1.3 倍的加速比，而TIA 由于指令緩存的面積消耗，因此，陣列規模要小得多，平均性能只有Plasticine 的0.8 倍。

對于包含分支的應用，如Sort 排序算法、FFT傅里葉變換和HotSpot 檢測算法，由于有大量的elseif分支，因 此，Plasticine中的PE 利用率大大降低。而TIA 通過位于不同分支路徑的指令合并映射到同一個PE 上，因此，提高了PE 利用率，并相比Plasticine 性能上取得了1.2 倍的加速比。而本文的設計通過控制流解耦，取得了1.3 倍的加速比。

對于存在循環依賴的應用，如LU 分解、GE 高斯消元和Cholesky 分解，Plasticine 中顯式的數據同步降低PE 利用率到約45%左右。而TIA 和本文的設計通過指令和子圖級的調度方式，取得了75%的PE 利用率。

3.3 執行能效評估

上述3 種架構的執行能效比如圖7 所示。

圖7 3 種架構間的執行能效對比［9］Fig.7 Comparison of energy efficiency among three architectures normalized to Plasticine［9］

圖中，盡管TIA 取得了相對較高的PE 利用率和性能，但是細粒度的指令調度顯著增大了執行的能耗。因此，對于大部分應用，其在能效比方面均要低于Plasticine。而本文的設計，通過高效的子圖粒度的解耦和重調度，在大多數應用中取得了較高的能效比。而對于HotSpot 檢測和CFD 流體動力學這類應用，由于頻繁的子圖切換，各個子圖執行過程中的中間數據需要暫存在片上緩存中，因此，會增加片上緩存的訪問次數，進而導致額外的能耗增加。

4 結束語

針對應用中出現的非一致性控制流，本文提出了一種基于控制流解耦的調度方案。通過將處于不同控制流邊界下的數據流解耦成多個可獨立執行的子圖，每個子圖可以在陣列上充分展開以提高陣列的計算利用率。實驗結果表明：相比于傳統的直接映射方法，本方案可以通過在典型的PE 內部增加輕量化的調度單元，進而提高可重構陣列的資源利用率和執行性能。