一種基于控制流解耦的可重構(gòu)陣列動態(tài)調(diào)度方法

尹 琛，彭 飛，景乃鋒

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

0 引言

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

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

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

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

1 非一致性控制流分析

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

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

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

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

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

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

2 基于控制流解耦的調(diào)度方案及硬件架構(gòu)設計

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

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

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

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

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

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

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

2.2 子圖動態(tài)調(diào)度器

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

圖4 子圖動態(tài)調(diào)度器硬件結(jié)構(gòu)Fig.4 Structure of the dynamical scheduler of a subgraph

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

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

圖5 支持子圖切換的PE 內(nèi)部結(jié)構(gòu)Fig.5 Inner structure of PE with subgraph switching

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

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

3.1 實驗設置

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

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

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

表2 架構(gòu)參數(shù)設定Tab.2 Architecture parameter setting

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

3.2 性能和PE 利用率評估

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

圖6 3 種架構(gòu)間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 利用率。

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

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

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

3.3 執(zhí)行能效評估

上述3 種架構(gòu)的執(zhí)行能效比如圖7 所示。

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

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

4 結(jié)束語

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