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

尹 琛，彭 飛，景乃鋒

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

0 引言

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

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

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

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

1 非一致性控制流分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 支持子圖切換的PE 單元設(shè)計(jì)

為支持上述子圖配置的動(dòng)態(tài)切換，在現(xiàn)有的PE結(jié)構(gòu)中增加一個(gè)配置切換單元，如圖5 所示。配置切換單元中會(huì)記錄當(dāng)前子圖ID，并同時(shí)監(jiān)測(cè)每個(gè)周期攜帶在輸入數(shù)據(jù)上的子圖ID。當(dāng)輸入數(shù)據(jù)上的子圖ID 和記錄的子圖ID 不同時(shí)，將觸發(fā)配置切換，同時(shí)更新當(dāng)前記錄的子圖ID。配置單元會(huì)根據(jù)新子圖ID 從配置緩存器中讀出相應(yīng)的一個(gè)新配置，并通過(guò)配置更新電路逐級(jí)改變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ù)流逐級(jí)切換。對(duì)于PE 內(nèi)部的某一流水級(jí)而言，在當(dāng)前周期完成子圖配置更新后，在下一周期即可執(zhí)行更新后的子圖所對(duì)應(yīng)的數(shù)據(jù)流。因此，可以避免現(xiàn)有的動(dòng)態(tài)配置切換技術(shù)中，由于在流水線中引入氣泡所導(dǎo)致的流水線停頓現(xiàn)象［11］。

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

3.1 實(shí)驗(yàn)設(shè)置

從3 種專(zhuān)用加速器領(lǐng)域廣泛使用的測(cè)試集中選擇了多個(gè)含非一致性控制流的代表性應(yīng)用，見(jiàn)表1。

表1 用于進(jìn)行評(píng)估對(duì)比的測(cè)試應(yīng)用Tab.1 Workloads for evaluation

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

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

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

3.2 性能和PE 利用率評(píng)估

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

圖6 3 種架構(gòu)間PE 利用率（散點(diǎn)圖）和性能加速比（柱狀圖）的對(duì)比（以文獻(xiàn)［9］為基準(zhǔn)）Fig.6 Comparison of PE utilization ratio（in marker）and performance acceleration ratio（in bar）among three architectures normalized to Plasticine［9］

式中：r為PE 利用率。

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

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

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

3.3 執(zhí)行能效評(píng)估

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

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

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

4 結(jié)束語(yǔ)

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