融合面積估算和多目標優(yōu)化的硬件任務(wù)劃分算法

陳乃金，江建慧

(1.同濟大學 軟件學院，上海 201804；2.安徽工程大學 計算機與信息學院，安徽 蕪湖 241000)

1 引言

近年來，隨著VLSI技術(shù)的迅速發(fā)展，尤其是大規(guī)模高性能可編程器件的出現(xiàn)，促進了可重用芯片實現(xiàn)的多樣化，從而在很大程度上影響了計算機軟硬件計算平臺的重新定位?？芍貥?gòu)計算 (RC,reconfigurable computing)是一種融軟件的編程靈活性和硬件的高效性于一體的計算方式。根據(jù)應(yīng)用的不同需要對可重構(gòu)硬件進行動態(tài)配置，根據(jù)配置信息來改變其內(nèi)部可重構(gòu)單元的功能和相互之間的連接關(guān)系，并在輔助設(shè)備(包括外圍控制硬件和軟件)的協(xié)同下完成相應(yīng)的計算任務(wù)，這種系統(tǒng)已經(jīng)在很多領(lǐng)域得以廣泛應(yīng)用[1～4]。音、視頻的編解碼等計算密集型任務(wù)的關(guān)鍵循環(huán)占用了大量計算時間，如果將計算密集型任務(wù)經(jīng)過軟硬件劃分，然后提取出其關(guān)鍵循環(huán)的數(shù)據(jù)流圖(DFG, data flow graph)，并將其劃分映射到可重構(gòu)單元陣列(RCA, reconfigurable cell array)上執(zhí)行，這將大大加快計算密集型任務(wù)的執(zhí)行效率，但是RCA的資源有限，所以在動態(tài)可重構(gòu)系統(tǒng)中，當要計算的硬件任務(wù)所需的資源大于硬件能夠提供的資源時，就必須要對其進行劃分，劃分是映射的前提，并且可以直接形成粗粒度可重構(gòu)處理單元(RPU, reconfigurable processing unit)流水化映射[5～8]的裝載調(diào)度隊列，其結(jié)果直接影響從計算密集型任務(wù)提取的核心循環(huán)在RPU上執(zhí)行速度。

2 相關(guān)研究

傳統(tǒng)的 DFG時域劃分算法根據(jù)電路的抽象層次可大致分為網(wǎng)表級時域劃分和行為級時域劃分 2類算法。網(wǎng)表級時域劃分算法針對的是電路?；诰W(wǎng)絡(luò)流的網(wǎng)表級時域劃分算法將電路定義為一個網(wǎng)絡(luò)流，它可表示為由門和寄存器所組成的節(jié)點集、由門和寄存器之間的連接所組成的邊集，以及由門和寄存器的面積所組成的面積等3個集合所構(gòu)成的三元組。而一個計算密集型任務(wù)或程序的關(guān)鍵循環(huán)可以用 DFG表示，圖中每個節(jié)點表示一個操作符（或運算符），對這樣的圖所進行的時域劃分通常稱為行為級時域劃分。

本文研究行為級時域劃分方法。文獻[9]首次直接討論了面向可重構(gòu)計算機系統(tǒng)的硬件任務(wù)劃分問題，并提出了2個經(jīng)典的單目標時域劃分算法，即層劃分(LBP, level based partitioning)和簇劃分(CBP, cluster based partitioning)，LBP算法在某一硬件面積約束基礎(chǔ)上，對計算任務(wù)節(jié)點進行按層劃分。優(yōu)點是試圖獲得較大的并行度，其目的是試圖獲得一個任務(wù) DFG的所有劃分塊執(zhí)行延遲總和的較小化，缺點一是劃分塊間的通信成本較大(表現(xiàn)為一個任務(wù)DFG劃分塊間的非原始I/O邊數(shù)較多)；二是不能根據(jù)實際劃分情況動態(tài)調(diào)整就緒列表隊列，結(jié)果產(chǎn)生了大量硬件碎片；三是把第0層的輸入作為第一個劃分塊，這樣做有可能會使任務(wù)DFG執(zhí)行延遲的增大。CBP算法試圖盡可能地將聯(lián)系緊密的操作放到一個劃分塊中，其目的是想獲得劃分后DFG塊間的較小非原始I/O邊數(shù)。缺點一是任務(wù)DFG的每個劃分塊內(nèi)部計算任務(wù)節(jié)點的并行度較??；二是不能根據(jù)實際劃分情況動態(tài)調(diào)整就緒列表隊列；三是把第0層的輸入作為第一個劃分塊不太合理，理由同LBP算法。

簇層次敏感的劃分(LSCBP, level sensitive cluster based partitioning)算法對CBP算法進行了改進[10]，提高了硬件資源的利用率，效果良好，但是該算法缺點一是劃分塊間的邊數(shù)仍然較大；二是當一個劃分塊間運算節(jié)點的輸出邊數(shù)超過1時，直接按實際邊數(shù)進行統(tǒng)計，這樣做可能導致該運算結(jié)果被多次存儲；三是把第0層的輸入化為第一個劃分塊不太合理，理由同LBP算法。

基于流網(wǎng)絡(luò)的多路任務(wù)劃分(NFMP, network flow?based multiway?task partitioning)算法是追求劃分塊間邊數(shù)較小化的單目標時域劃分算法，NFMP算法首先運用了最大流最小割理論計算獲得待劃分任務(wù) DFG可行的最小割集初始劃分[11]，然后在此基礎(chǔ)上，通過劃分子圖構(gòu)造、廣度優(yōu)先搜索和最短路徑等相融合來獲得劃分塊間通信成本的較小化(表現(xiàn)為一個任務(wù)DFG劃分塊間的非原始I/O邊數(shù)較少)，效果較好。但是該算法缺點一是在某一硬件資源面積約束下，對待劃分任務(wù) DFG所需的劃分塊總數(shù)考慮不足；二是沒有考慮每個劃分塊內(nèi)運算任務(wù)節(jié)點的并行度。

現(xiàn)有的典型多目標時域劃分算法主要有多目標時域劃分(MOTP, multi objective temporal partitioning)[12]、增強的靜態(tài)列表(ESL, enhanced static list)[13]等。

MOTP算法試圖盡可能地考慮劃分塊數(shù)、劃分塊內(nèi)運算節(jié)點的并行度和劃分塊間的通信量等3個指標來進行任務(wù)DFG的時域劃分。優(yōu)點是獲得了較小的劃分塊數(shù)。缺點一是在每次劃分時，沒有進行硬件資源面積的估算，可能產(chǎn)生硬件碎片；二是統(tǒng)計劃分塊間輸出邊的數(shù)量不太合理，理由同LSCBP算法。

ESL算法考慮了任務(wù)DFG塊之間的通信代價和模塊關(guān)鍵路徑等指標。其不足是對并行因素考慮不夠，且沒有考慮任務(wù) DFG劃分中可能產(chǎn)生的硬件碎片問題。

本文在綜合考慮了一個計算任務(wù) DFG劃分塊數(shù)最小化、所有劃分塊執(zhí)行延遲總和、所有劃分塊之間的I/O邊數(shù)的較小化等3個方面的因素，提出了一種融合面積估算和多目標優(yōu)化(AEMO, area estimation with multi?objective optimization)的硬件任務(wù)劃分算法。

3 問題定義

本文的研究有 3個前提條件[14]:1) 待劃分的任務(wù)由 DFG表示，一個計算密集型任務(wù)已經(jīng)轉(zhuǎn)換為一個DFG；2) 劃分塊數(shù)等于RPU中的RCA重復使用的次數(shù)，任一劃分均可按劃分形狀直接映射到一塊RCA上去，并且一個劃分對應(yīng)一塊RCA，如圖1所示；3) 劃分算法只考慮硬件實現(xiàn)的計算延遲，而不考慮互連延遲。

定義 1[14]一個計算任務(wù)或程序的 DFG是一個有向無環(huán)圖，可以表示為G=(V, E, W, D)，頂點集V= {vi|vi是有序運算符，1≤i≤n}，|V|=n表示運算符的個數(shù)；邊集 E={eij|eij=＜vi，vj＞，1≤i，j≤n}，eij表示從vi到vj的有向邊，vi是vj的直接前驅(qū)節(jié)點，vj是vi的直接后繼節(jié)點，其表示了vi和vj2個運算符的先后依賴關(guān)系，vj的執(zhí)行依賴于vi，|E|=m為邊的數(shù)量；權(quán)集W={wi|表示vi所占的硬件資源面積，1≤i≤n}；D代表延遲集，di∈D代表第i個運算節(jié)點的執(zhí)行延遲。

一般而言，RPU中的RCA的面積為一個定值（表示為ARPU），任意一個任務(wù)DFG很難被全部映射上去，這就需要對其進行劃分。

定義2 一個DFG的劃分問題可以描述如下。

輸入:G=(V, E, W, D)；ARPU。

輸出:G的一個劃分P={P1, P2, …, PM}。

約束條件:

目標:1) 劃分塊數(shù)的最小化；2) 所有劃分塊執(zhí)行延遲總和的較小化；3) 盡可能減少劃分塊間I/O邊數(shù)。

定義3 若一個任務(wù)DFG存在一個劃分，劃分塊之間嚴格按時間順序執(zhí)行，它的所有劃分塊之間如有一個產(chǎn)生了非法依賴關(guān)系，則該劃分就稱為不合理的劃分。

設(shè)v是一個計算任務(wù)或程序的DFG的有序運算符中的任一個運算節(jié)點，則v被劃入一個劃分塊的前提是v的所有的前驅(qū)節(jié)點均已經(jīng)被分配到相應(yīng)的劃分塊中。一個合理的劃分要求劃分塊之間均不產(chǎn)生非法依賴關(guān)系。因DFG是一個有向無環(huán)圖，如果一個節(jié)點的前驅(qū)節(jié)點被分配到其后繼模塊中，就會引發(fā)非法依賴關(guān)系現(xiàn)象。圖2給出了這種情況的一個例子，為了簡化問題描述，假設(shè)一個任務(wù)或程序的 DFG中各個節(jié)點的權(quán)值相同，這樣，本文可以將面積的單位等價于節(jié)點的個數(shù)。若ARPU=2，獲得P1、P2、P33個劃分，設(shè)P3總是最后執(zhí)行，但如果劃分塊 P1和 P2的執(zhí)行次序是從 P1→P2，因 P1劃分中運算節(jié)點 v4前驅(qū)v2位于P2劃分，所以劃分塊 P1和P2之間產(chǎn)生了非法依賴關(guān)系。

圖2 一個不合理劃分的例子

4 AEMO算法

4.1 AEMO算法設(shè)計

設(shè)待劃分DFG的運算符節(jié)點列表queuelist={v1,v2, v3,…, vn}，從列表隊列節(jié)點里挑選出優(yōu)先級高的運算節(jié)點構(gòu)成新的就緒列表 readylist={v1′, v2′,v3′,…,vn′}，每次劃分時依次從 readylist中挑選節(jié)點。AEMO算法采用以下5個策略來進行任務(wù)劃分。

策略 1 可重構(gòu)劃分面積邏輯容量估算和按權(quán)值調(diào)度劃分同時進行，獲得最小的劃分塊數(shù)。

下面給出2種實現(xiàn)方案。

1) 方案1 在一個ARPU的約束下，采用的策略是從就緒隊列(由入度為 0的點組成)中選取運算節(jié)點權(quán)值最小(本文約定節(jié)點的權(quán)值越小，則該點優(yōu)先級就越高)的點作為起點，按深度優(yōu)先搜索(DFS,depth first search)進行預(yù)劃分，獲得了一個合理劃分，并計算硬件碎片面積 area1=ARPU?area_filled1(其中 area_filled1表示所有劃入當前塊節(jié)點的面積累加和)；然后再以同樣的起點按廣度優(yōu)先搜索(BFS, breadth first search)進行預(yù)劃分，獲得了一個合理劃分，并計算硬件碎片面積 area2=ARPU?area_filled2；將area1和area2進行大小比較，如果area1小，則本次劃分按DFS方式進行，否則按BFS方式進行，但是這樣做可能有一個缺陷，若 area1=area2，且DFS和BFS一遇到不滿足要求的節(jié)點就停止，則這樣會導致劃分方式的不明確。

例1 假設(shè)算術(shù)表達式中允許包含2種括號:圓括號和方括號，其嵌套的順序合理，則一個算術(shù)表達式可表示為:y=[[[(a×b×k?(g+h))+(c×d×l?m)]%[((a×b)+(e×f+(i+j)))+n]+o]+[[[(a×b+k?(g+h))+(c×d×l?m)]+[((a×b)+(e×f+(i+j)))+n]+p]×[[[(a×b×k?(g+h))+(c×d×l?m)]%[((a×b)+(e×f+(i+j)))+n]]+[[(a×b+k?(g+h))+(c×d×l?m)]+[((a×b)+(e×f+(i+j)))+n]]]]]+[[[(a×b+k?(g+h))+(c×d×l?m)]+[((a×b)+(e×f+(i+j)))+n]+p]+[[[(a×b×k?(g+h))+(c×d×l?m)]%[((a×b)+(e×f+(i+j)))+n]]+[[(a×b+k?(g+h))+(c×d×l?m)]+[((a×b)+(e×f+(i+j)))+n]]]?q]，該算術(shù)表達式的 DFG如圖 3(a)所示，其層次為 9，原始輸入邊有17條，原始輸出邊有 1條，非原始輸入輸出邊數(shù)為29條，有23個運算任務(wù)節(jié)點，其集合V={vi|1≤i≤23}，劃分前P=Φ，劃分后P={P1,P2,…,PM}，設(shè)ARPU=65，則按 DFS (P1={v1，v6}，如圖 3(b)所示 )或者 BFS(P1={v1,v2}，如圖3(c)所示)進行預(yù)劃分獲得的硬件碎片均為area1= area2=65?54=11，雖然v3、v4均有劃入的可能，但是卻不能劃入。為此引入第2種方案。

2) 方案2 在一個ARPU的約束下，從就緒隊列中按權(quán)值選取優(yōu)先級最高的點作為起點，按DFS進行劃分，每劃分一次，就更新該點后繼節(jié)點的入度，如果入度為0就直接預(yù)劃入，如果入度不為0，考察該點的其他沒有劃入當前塊的前驅(qū)能否劃入，如果能，則一并預(yù)劃入，直到?jīng)]有節(jié)點可以填入area_filled1為止，這樣就獲得了一個DFS的合理劃分，計算 area1=ARPU?area_filled1，若 area1＜value(value為一設(shè)定的閾值，其范圍為(0，10]，本文設(shè)為10)，則本次劃分按DFS進行，然后計算沒有劃入就緒點的探測函數(shù)值，再按ARPU和權(quán)值大小貪婪劃入可以劃入的點(詳細的實現(xiàn)細節(jié)見后面的例子說明)，否則按BFS進行權(quán)值層貪婪劃分，即使某個節(jié)點的后繼入度更新為0，也不直接劃入當前塊。這樣做的目的是盡可能保證每次劃分均能最大化利用ARPU，同時增大一個劃分塊內(nèi)的運算節(jié)點的并行度。

由上可知，策略1側(cè)重于要求每次劃分盡可能填滿每一塊RCA，從而使任務(wù)DFG總的劃分塊數(shù)達到最小，而且按BFS進行權(quán)值貪婪劃分時，考慮了劃分塊內(nèi)運算節(jié)點的并行度。

策略 2 執(zhí)行延遲大優(yōu)先(EDTLF, execution delay time long first)和可重構(gòu)運算陣列面積的充分利用相融合。

當有多個節(jié)點處于就緒狀態(tài)時，運用“盡可能早”原則，在保證DFG獲取合理劃分的前提下，優(yōu)先選擇執(zhí)行延遲大和占用硬件面積大的運算節(jié)點。在延遲相同的前提下，占用硬件面積越大的任務(wù)越優(yōu)先，而在占用硬件面積一樣的前提下，延遲越大的任務(wù)越優(yōu)先。在遇到當前點不能劃入當前塊時，還要動態(tài)考察該點之后還有無可以劃入當前塊的點，如有將其貪婪劃入，這樣做的目的是優(yōu)先響應(yīng)執(zhí)行延遲大節(jié)點的同時，又充分利用了可重構(gòu)運算陣列面積。

由上可知，策略2側(cè)重于同時考慮了硬件碎片利用、硬件劃分的吞吐量、執(zhí)行延遲大節(jié)點的優(yōu)先響應(yīng)等因素，其目的是想同時獲得任務(wù) DFG劃分塊數(shù)和所有劃分塊總的執(zhí)行延遲的較小化。

策略 3 優(yōu)先選擇優(yōu)先級高的節(jié)點和當前層任務(wù)節(jié)點。

在滿足資源面積和前后依賴約束的前提下，優(yōu)先選擇優(yōu)先級大的當前層任務(wù)節(jié)點，當前層的下一層節(jié)點滯后選擇；在2個任務(wù)節(jié)點優(yōu)先級相同的情況下，優(yōu)先選擇當前層就緒的節(jié)點，若不存在這樣的點，則按先來先服務(wù)(FIFO, first in first out)原則執(zhí)行；對于同時就緒的任務(wù)節(jié)點，則選擇優(yōu)先級高的任務(wù)節(jié)點。

圖3 解釋方案1不合理的例子

由上可知，策略3側(cè)重于考慮任務(wù)DFG劃分塊內(nèi)運算節(jié)點的并行度。

策略4 盡量減少劃分塊之間的I/O邊數(shù)。

實現(xiàn)策略4的方法有:1)每次劃分首先按DFS的方式選擇當前優(yōu)先級最大的節(jié)點作為起始點劃入當前塊，同時更新該點直接后繼的入度，如后繼的入度為0，在滿足ARPU的前提下，直接預(yù)劃入當前塊；如后繼的入度不為 0，還要考察該點沒有劃入當前塊的前驅(qū)能否劃入，如果能，則一并預(yù)劃入；2)每劃入一個點，就動態(tài)計算正在劃分的模塊與就緒節(jié)點之間的邊數(shù)，邊數(shù)越大就說明該就緒節(jié)點與當前劃分塊聯(lián)系越緊密，盡可能將其劃入將有助于減少劃分塊之間的I/O邊數(shù)。

由上可知，策略4在策略1～策略3的基礎(chǔ)上，側(cè)重于減少劃分塊之間I/O邊數(shù)。

策略5 其他方面因素的考慮。

1) 層次大優(yōu)先級高的節(jié)點應(yīng)優(yōu)先響應(yīng)

對于不同層的任務(wù)節(jié)點要考慮其層號，這樣做的目的一方面是在同等條件下，節(jié)點的層號越小越優(yōu)先，另一方面是為了照顧優(yōu)先級高且層次較大任務(wù)節(jié)點被優(yōu)先響應(yīng)，以便盡可能提高每個劃分塊內(nèi)部運算任務(wù)節(jié)點之間的并行度。

2) 優(yōu)先劃入出度較大的運算節(jié)點

同等條件下，優(yōu)先劃入出度較大的運算節(jié)點，目的是搜索范圍的擴大化使更多的節(jié)點成為就緒點，從而有可能使每次劃分得以進一步優(yōu)化。

3) 防止劃分塊間運算任務(wù)節(jié)點非法依賴關(guān)系的產(chǎn)生

任務(wù)DFG的時域劃分要求入度為0的點或者某點的所有前驅(qū)已經(jīng)被劃入當前塊或上一塊時才能劃入該點，這應(yīng)在程序中用條件語句加以約束，這樣做的目的是防止劃分塊間非法依賴關(guān)系的產(chǎn)生（如圖2所示）。

由上可知，策略5中的1)側(cè)重于考慮任務(wù)DFG劃分塊內(nèi)運算節(jié)點的并行度；策略5中的2)側(cè)重于優(yōu)化每次劃分；策略5中的3)側(cè)重于防止任務(wù)DFG每個劃分塊之間產(chǎn)生非法依賴。

根據(jù)以上策略，AEMO為就緒列表中的任務(wù)構(gòu)造了新的探測函數(shù)(本文約定函數(shù)值越小優(yōu)先級越大)，并且根據(jù)不同參數(shù)指標的貢獻大小而將其設(shè)為分母或分子。

為了便于實驗比較，本文用重構(gòu)硬件資源面積作為約束條件，各類運算所占的重構(gòu)硬件資源數(shù)(單位:CLB)的確定參照了XC4000E系列8bit FPGA(如表1所示)。

表1 各類運算的時延和占用資源量

探測函數(shù)構(gòu)造的基本思想如下。

首先，由表1可知，運算任務(wù)節(jié)點執(zhí)行延遲大，其所占的硬件資源數(shù)也較大，故為了保證其優(yōu)先響應(yīng)，應(yīng)采用第i個運算節(jié)點vi所占的硬件資源面積wi和其執(zhí)行延遲di的累加和作為探測函數(shù)的分母的一部分(1≤i≤n)。

其次，在任務(wù) DFG的劃分過程中，為了盡可能地劃入與正在劃分模塊緊密聯(lián)系的就緒節(jié)點，需要動態(tài)計算當前正在劃分的模塊與就緒節(jié)點之間有向邊的數(shù)量，其目的是盡可能地減少劃分塊間非原始I/O邊數(shù)。

例 2 圖 4(a)給出了一個正在劃分的部分DFG，假設(shè)v1和v2點已經(jīng)被劃入到P1中(如圖4(b)所示)?，F(xiàn)考察就緒節(jié)點v3和v4，設(shè)v3和v4運算類型相同且位于同一層，在 ARPU的約束下，P1還可以劃入 v3或 v4點中一個，P1與 v3的邊數(shù)為 1，與v4的邊數(shù)為2，P1劃入v3的情形如圖4(c)所示，P1劃入v4的情形如圖4(d)所示，但是圖4(d)的方案要優(yōu)于圖 4(c)，原因是圖 4(c)的劃分塊間邊數(shù)為 3，而圖4(d)的劃分塊間邊數(shù)僅為2。

因此，每次在線動態(tài)劃分時可將當前正在劃分的模塊與就緒節(jié)點之間有向邊的數(shù)量(用 s表示)作為探測函數(shù)的分母的一部分。

第三，在任務(wù)DFG的劃分過程中，為了達到當前層任務(wù)節(jié)點和層號小的節(jié)點被優(yōu)先響應(yīng)，可將任務(wù)節(jié)點層次號作為探測函數(shù)分子的一部分。但是這樣做有時會使層次大的優(yōu)先級高任務(wù)節(jié)點得不到及時響應(yīng)。圖 5所示的例子說明，設(shè) v6為加法，v666為乘法，v666的優(yōu)先級本應(yīng)高于v6，但v666所在的層次遠大于 v6，同時就緒時，為了保證 v666先執(zhí)行可以在任務(wù)節(jié)點層次號前面乘以一個修正系數(shù)，其最大值定為1/maxlevel，這樣可以使層次大的優(yōu)先級高節(jié)點優(yōu)先得以響應(yīng)，從而提高劃分塊內(nèi)部的并行度。

圖4 說明計算正在劃分的模塊與就緒節(jié)點之間的邊數(shù)s的例子

圖5 解釋優(yōu)先級高且層次較大節(jié)點優(yōu)先響應(yīng)的例子

最后，在進行任務(wù) DFG時域劃分過程中，待劃的就緒列表節(jié)點的前驅(qū)可被劃入當前塊或已經(jīng)被劃入到上一個劃分中了，所以任務(wù)節(jié)點被調(diào)度時其入度必須為0，這一點可有條件判斷語句來實現(xiàn)。但是出度大的任務(wù)節(jié)點被動態(tài)劃入當前塊時，會使更多的點成為就緒點，選擇節(jié)點的空間增大有可能優(yōu)化劃分。圖6所示例子說明，v1和v2的優(yōu)先級相同，若按FIFO先劃入v1，則只能使v3成為就緒點，但是另外一種可能的方法是先劃入v2，這樣可以使v4～v9同時成為就緒點，從而可能優(yōu)化劃分。所以可以將任務(wù) DFG的每個節(jié)點的出度設(shè)定為探測函數(shù)的分子或分母，同時為了進行動態(tài)調(diào)整可以設(shè)定一修正系數(shù)。

圖6 解釋出度大的點被優(yōu)先劃分的例子

這樣，對于任一個運算節(jié)點 vi，其探測函數(shù)prior_assigned(vi)可以設(shè)定為如下2種形式之一

其中，outdegree(vi)表示節(jié)點 vi的出度，式(1)把outdegree(vi)作為分子并要做減法，因為分母相同的情況下，分子越小函數(shù)值越小，prior_assigned(vi)越小越優(yōu)先；同理，式(2)把 outdegree(vi)作為分母并要做加法，目的是使分母變大。函數(shù)的其他參數(shù)說明如下:maxlevel表示一個 DFG的最大層號；maxoutdegree=max{outdegree(vi), 1≤i≤n}；maxinputoutputside表示一個DFG非原始輸入輸出邊數(shù)之和；level(vi)表示節(jié)點vi的層次數(shù)，α、β和γ為調(diào)整系數(shù)，α取值范圍為[0,1/maxlevel]，β取值范圍為[0, maxoutdegree]，γ取值范圍為[0, maxinputoutputside]。prior_assigned(vi)的值越小表示 vi的優(yōu)先級越高，即被劃入某個劃分的可能性就越大。

為了驗證相關(guān)劃分算法，構(gòu)造了一組劃分基準程序集。它們由2部分構(gòu)成，一是由LBP和CBP算法所用的基準中值濾波器MEDIAN、二叉樹比較器 BTREE32、一維離散余弦變換 8次展開 DCT8和4×4矩陣運算MATRIX4、MOTP算法所用的基準二階差分方程SODE、快速數(shù)據(jù)加密算法FEAL、快速離散余弦變換FDCT、快速離散余弦變換6次展開 FDCT6、橢圓波形濾波器EWF、橢圓波形濾波器6次展開EWF6，此外還增加了快速傅里葉變換4次展開FFT4(fast Fourier transform 4)、快速傅里葉變換8次展開FFT8(fast Fourier transform 8)2個基準，這些基準的操作單元數(shù)量如表2所示。第2部分基準程序采用了文獻[14]中列出的且與 ESL和LSCBP所用基準特征相同的10個隨機圖。程序的開發(fā)環(huán)境是VC++6.0，運行環(huán)境是Windows XP，PC的處理器為Intel(R) Core(TM) i3 CPU, 主頻為2.26GHz, 內(nèi)存為2GB。

表2 劃分基準程序集

隨機選取的ARPU分別為56 CLB、64CLB、75 CLB，取 α=1/maxlevel，β=γ=1，統(tǒng)計劃分塊間輸出邊的數(shù)量時，如塊間一個運算節(jié)點的輸出邊數(shù)超過1，也只算一條邊，這樣做的理由是避免劃分塊間同一個節(jié)點的運算結(jié)果被多次存儲。設(shè)M表示一個DFG的劃分塊數(shù)，SD表示一個DFG所有劃分塊執(zhí)行延遲總和，N表示一個DFG所有劃分塊之間的非原始I/O邊數(shù)。

AEMO算法描述如圖7所示。

4.2 算法時間復雜度分析

AEMO算法在執(zhí)行前，一個 DFG總的運算節(jié)點數(shù)、每個運算節(jié)點的執(zhí)行延遲、運算類型和占用的資源數(shù)，每個節(jié)點前驅(qū)與后繼的個數(shù)及列表均已知。

設(shè)一個DFG有n個運算節(jié)點，assign_level()求出每個運算節(jié)點層次及該DFG的最大層次號，時間復雜度為O(n2)；每次劃分所用到的就緒任務(wù)節(jié)點，在入隊時均要通過探測函數(shù) priority_assigned()計算其優(yōu)先級，其時間復雜度為O(n2)；用快速排序函數(shù)quicksort()對每次計算出的探測函數(shù)值按從小到大排序，其最好情況時間復雜度為 O(n)，最壞情況為 O(n2)，平均時間復雜度為 O(nlog2n)；用函數(shù)edges()求一個劃分后的DFG塊間總的非I/O邊數(shù)，時間復雜度為 O(n2)；假如一個DFG被劃分為M塊，用直接遞歸調(diào)用來求一個劃分后的DFG所有模塊執(zhí)行總延遲函數(shù) delays()的時間復雜度為O(Mn)。

圖7 AEMO算法

AEMO算法在對DFG進行劃分時，首先要找到當前優(yōu)先級最高的待劃分節(jié)點，故每次在劃分前通過探測函數(shù)計算每個就緒節(jié)點優(yōu)先級的值并排序，找到優(yōu)先級最高的待劃分節(jié)點放入當前的劃分中，這是一個循環(huán)迭代的過程，加上判斷 DFG的運算節(jié)點是否全部被劃分完的約束，共耗費的時間復雜度為O(n4log2n)。綜上，AEMO算法的平均時間復雜度為O(n4log2n)。

為了比較2個探測函數(shù)的優(yōu)劣性，AEMO算法分別用式(1)和式(2)實現(xiàn)，再用如表2所示的劃分基準程序集進行了實驗，結(jié)果如表 3所示，其中AEMO1算法采用的探測函數(shù)是式(1)。表3分別給出了ARPU=56、64和75時劃分基準程序采用2個不同劃分算法所得到的劃分結(jié)果，對應(yīng)于每個指標(M、N、SD)下每個劃分算法和改進的百分比(Δ%)所列出的3列內(nèi)容。以SODE為例，當ARPU=56時，采用 AEMO1算法所獲得的 M=5，而采用 AEMO算法所獲得的 M=4，因此，Δ%=?20.0%(負值表示改進)。通過對比可知，用式(2)所獲得的結(jié)果符合本文的目標，即 M 要最小化，同時獲得一個較小SD，且盡可能減少N。因此，本文的后續(xù)工作均基于采用式(2)探測函數(shù)的AEMO算法。

4.3 一個算術(shù)表達式劃分實例分析

針對圖3(a)算術(shù)表達式的DFG，劃分前節(jié)點有23 個，設(shè) ARPU=65，maxlevel=9，α=1/9，β=γ=1，面積填充變量 area_filled=0，硬件碎片面積變量area1= 0(按DFS)，value=10，圖8和圖9給出了根據(jù)AEMO算法每一個步驟的劃分子圖。

1) 圖 3(a)入度為 0的就緒節(jié)點為 v1～v5，w1=w2=w3=27，w4=w5=5，d1=d2=2，d3= d4= d5=1，就緒節(jié)點v1、v2、v3、v4、v5與當前正在劃分的模塊有向邊的數(shù)量均為0，level(v1)= level(v2)= level(v3)= level(v4)=level(v5)= 1，outdegree(v1)=2，outdegree(v2)= outdegree(v3)= outdegree(v4)= outdegree(v5)=1，prior_ assigned(v1)= (α×level(v1))× (1/(w1+ γ×s+d1+ β× outdegree(v1))=((1/9)×1))×(1/(27+1×0+2+1×2))≈0.0036，同理，prior_assigned(v2)= prior_ assigned(v3) ≈0.0037，prior_assigned(v4) =prior_ assigned (v5) ≈ 0.0159。由于prior_assigned(v1)最小，故以v1作為起點進行DFS貪婪劃分，v1被劃入P1(如圖8(a)所示)，則劃分后剩余節(jié)點集合 V={v2，v3，v4，v5，v6，v7，v8，v9，v10，v11，v12，v13，v14，v15，v16，v17，v18，v19，v20，v21，v22，v23}，P={P1}，P1={v1}，area_filled=27，area1= ARPU?area_filled =65?27=38，v6的入度更新為0，v11的入度更新為1。

表3 ARPU=56、64、75時AEMO1與AEMO的劃分結(jié)果

圖8 圖3(a)算術(shù)表達式DFG的第一個劃分過程

圖9 圖3(a)算術(shù)表達式DFG的后續(xù)劃分過程

2) 由于v6為v1的入度已經(jīng)更新為0的后繼，在滿足ARPU前提下，按DFS直接預(yù)劃入(如圖8(b)所示)，劃分后剩余節(jié)點集合 V={v2，v3，v4，v5，v7，v8，v9，v10，v11，v12，v13，v14，v15，v16，v17，v18，v19，v20，v21，v22，v23}，P={P1}，P1={v1，v6}，area_filled=54，area1=11，v9的入度更新為1；如果v9和其前驅(qū)v4一并劃入，則w9+w4=18＞area1，由于area1=11大于閾值value，故本次按DFS劃分不成功，把劃入的節(jié)點退回去，相關(guān)節(jié)點的信息復原。

3) 從v1開始，按權(quán)值進行BFS層貪婪劃分。由圖8(a)可知，就緒節(jié)點為v2、v3、v4、v5、v6分別計算其權(quán)值prior_assigned(v2)=prior_assigned(v3) ≈ 0.0037，prior_assigned(v4)=prior_assigned(v5)≈0.0159，prior_assigned (v6)=0.0072，由于v2、v3具有相同的優(yōu)先級，因此按FIFO原則先劃入v2，劃分后剩余節(jié)點集合 V={v3，v4，v5，v6，v7，v8，v9，v10，v11，v12，v13，v14，v15，v16，v17，v18，v19，v20，v21，v22，v23}，P={P1}，P1={v1，v2}，area_filled=54，area1=11，再依次按層貪婪劃入 v4、v5，area_filled=64，area1=1，節(jié)點調(diào)度序列依次為 v1、v2、v4、v5，則 V={v3，v6，v7，v8，v9，v10，v11，v12，v13，v14，v15，v16，v17，v18，v19，v20，v21，v22，v23}，P={P1}，P1={v1，v2，v4，v5}，其劃分形狀如圖8所示。

4) 由圖 8(c)可知，就緒節(jié)點為 v3、v6、v7、v8，分別計算其權(quán)值，prior_assigned (v3)的值小，優(yōu)先級高，在ARPU約束下，以v3為起點按DFS依次劃入v8、v11、v13，因為 area_filled=42，area1=65?42=23＞value，故以v3為起點按權(quán)值進行BFS層貪婪劃分，劃分P2節(jié)點調(diào)度序列依次為 v3、v6、v8、v11，劃分后剩余節(jié)點集合 V={v7，v9，v10，v12，v13，v14，v15，v16，v17，v18，v19，v20，v21，v22，v23}，則 P={P1，P2}，P1={v1，v2，v4，v5}，P2={ v3，v6，v8，v11}，v7、v9、v13的入度更新為0。P2的劃分形狀如圖9(a)所示。

5) 同理，按DFS以優(yōu)先級最高v7為起點，依次劃入v7、v10，因為v12的前驅(qū)可以劃入，故v9、v12一并劃入，而v12、v14不能同時劃入，故計算area1=ARPU?(w7+w10+w9+w12)=65?(27+13+13+5)=7＜value，更新v13、v14的入度為1，故本次劃分按DFS進行，更新就緒點的探測函數(shù)值，發(fā)現(xiàn)v12可以貪婪劃入，綜上，劃分 P3節(jié)點調(diào)度序列依次為 v7、v10、v9、v12、v13，劃分后剩余節(jié)點集合 V={v14，v15，v16，v17，v18，v19，v20，v21，v22，v23}，則 P={P1，P2，P3}，P1={v1，v2，v4，v5}，P2={v3，v6，v8，v11}，P3={v7，v10，v9，v12，v13}，v14、v15的入度更新為 0。P3的劃分形狀如圖9(b)所示。

6) 同理，按DFS以優(yōu)先級最高v14為起點，其節(jié)點調(diào)度序列依次為v14、v16、v15、v18，則P={P1，P2，P3，P4}，P1={ v1，v2，v4，v5}，P2={ v3，v6，v8，v11}，P3={ v7，v10，v9，v12，v13}，P4={v14，v16，v15，v18}，area_filled=65，area1=0(area1＜10)，故按DFS執(zhí)行。需要說明的是，在選取v18和v17時，正在劃分的模塊與就緒節(jié)點之間的邊數(shù)s起了重要的作用，α=1/9，γ=β=1，level(v17)= level(v18)=6，就緒節(jié)點 v17、v18與當前正在劃分的模塊有向邊的數(shù)量分別為 1 和 2，outdegree(v17)= outdegree(v18)=2，w17=w18=5，d17= d18=1，prior_assigned(v17) =2/27≈0.0741，prior_assigned(v18) =1/15≈0.0667，故劃入 v18，P4的劃分形狀如圖9(c)所示，其中劃入v18與劃入v17相比劃分塊間的邊數(shù)少了一條。

7) 同理，按DFS貪婪劃分得到P5如圖10所示，其節(jié)點調(diào)度序列依次為v17、v20、v22、v19、v21、v23，則 P={P1，P2，P3，P4，P5}，P1={v1，v2，v4，v5}，P2={ v3，v6，v8，v11}，P3={ v7，v10，v9，v12，v13}，P4={ v14，v15，v18，v16}，P5={ v17，v20，v22，v19，v21，v23}，V={Φ}，劃分結(jié)束。

5 實驗及其分析

本文采用 C語言實現(xiàn)了 ESL、CBP、LSCBP、MOTP、LBP、AEMO 6種時域劃分算法，所用的劃分基準程序集，統(tǒng)計劃分塊間輸出邊的數(shù)量方式，ARPU的3種取值，參數(shù)α、β、γ的選取等均同4.1節(jié)所述。CBP和LBP、LSCBP算法的模塊計數(shù)均包括第0層輸入的劃分。下面用AEMO算法分別與LBP、CBP、ELS、MOTP、LSCBP等算法做了比較。

5.1 AEMO算法與LBP算法的比較

用AEMO算法劃分圖3(a)的DFG的結(jié)果如圖10所示(ARPU=65)，所獲得的結(jié)果為 M=5、N=11、SD=20，而用LBP算法劃分的結(jié)果如圖11所示，結(jié)果為M=7、N=13、SD=17。

因為LBP算法在劃分過程中，一遇到不滿足硬件資源約束的運算節(jié)點就開辟新的劃分塊，并且把第0層輸入作為一個劃分塊，這些導致了M較大；LBP算法追求每個劃分塊SD的較小化，但是這將使N較大。AEMO算法消除了LBP算法的缺點，同時對SD進行了折中考慮。其他劃分基準對比實驗的數(shù)據(jù)如表4所示，相對于LBP算法，AEMO算法對M和N均有了一定程度的改進，但是SD不如LBP算法。

圖10 AEMO劃分圖3(a)的結(jié)果

圖11 LBP劃分圖3(a)的結(jié)果

表4 ARPU=56、64、75時AEMO算法與LBP算法的劃分結(jié)果

5.2 AEMO算法與CBP算法的比較

因為 CBP算法盡可能地將聯(lián)系緊密的運算節(jié)點放到一個模塊中，但對每個劃分塊內(nèi)運算節(jié)點的并行度考慮不足，因此N較小，SD較大；M較大的原因同LBP算法。AEMO算法與CBP算法比較的實驗數(shù)據(jù)如表5所示。

5.3 AEMO算法與ESL算法的比較

因為 ESL算法綜合考慮了劃分塊間的通信代價、關(guān)鍵路徑等因素，其劃分路徑多數(shù)是沿著深度優(yōu)先搜索方向延展的，對并行因素考慮不夠，而且沒有考慮任務(wù) DFG劃分中可能產(chǎn)生的硬件碎片問題，因此，相對于 AEMO算法，ESL算法獲得較小的N，但是M、SD均較大。AEMO算法與ESL算法比較的實驗數(shù)據(jù)如表6所示。

5.4 AEMO算法與MOTP算法的比較

因為MOTP算法折中考慮了M、SD和N等3個目標，因此獲得了較小M，但在每次劃分時，沒有進行硬件資源面積的估算，這就有可能會產(chǎn)生硬件碎片，所以相比于AEMO算法，M值仍然較大。AEMO算法與MOTP算法比較的實驗數(shù)據(jù)如表7所示。

表5 ARPU=56、64、75時AEMO算法與CBP算法的劃分結(jié)果

表6 ARPU=56、64、75時AEMO算法與ESL算法的劃分結(jié)果

5.5 AEMO算法與LSCBP算法的比較

LSCBP算法是對CBP算法的改進，消除了任務(wù)DFG劃分過程中產(chǎn)生的硬件碎片問題，在追求劃分塊間的邊數(shù)較小化的同時，簡單考慮了運算任務(wù)的并行性，效果較好。但是，LSCBP算法把第0層輸入作為一個劃分塊，且每次劃分時沒有進行硬件資源面積的估算，因此導致M較大，SD考慮仍然不足，所以相比于AEMO算法，M和SD均較大。AEMO算法與LSCBP算法比較的實驗數(shù)據(jù)如表8所示。

表7 ARPU=56、64、75時AEMO算法與MOTP算法的劃分結(jié)果

表8 ARPU=56、64、75時AEMO算法與LSCBP算法的劃分結(jié)果

從上述實驗比較結(jié)果可以看出，AEMO算法與LBP、ESL、CBP、MOTP、LSCBP等 5種算法相比，AEMO算法獲得的M是最小的；除LBP算法之外，AEMO算法的SD均值是最小的，但N值完全優(yōu)于LBP算法。

采用文獻[14]的 10個隨機圖基準程序，在 ARPU分別為56、64、75的條件下，相比ESL，AEMO算法對 M 改進的相對平均值分別為?5.4%、?6.1%、?8.7%；對N改進的相對平均值分別為+6.7%、+6.8%、+3.0%；對 SD改進的相對平均值分別為?4.6%、?9.3%、?9.3%；相比LSCBP，AEMO算法對M改進的相對平均值分別為?8.2%、?8.7%、?10.7%；對 N改進的相對平均值分別為+4.5%、+4.7%、+3.2%；對SD改進的相對平均值分別為?4.9%、?6.3%、?8.65%。

6 結(jié)束語

本文提出了一個 AEMO算法，該算法考察了待劃分就緒運算節(jié)點的實際情況，實現(xiàn)動態(tài)調(diào)整節(jié)點的調(diào)度次序，而且綜合考慮了 DFG劃分塊數(shù)和執(zhí)行總延遲、劃分塊之間非I/O邊數(shù)等多個因素，實驗結(jié)果表明，與LBP、ELS、CBP、MOTP和LSCBP等5種算法相比較，AEMO算法具有最小的M值，即劃分模塊數(shù)少，這意味著配置次數(shù)就少，這是影響計算密集型任務(wù)關(guān)鍵循環(huán)加速的主要因素之一。AEMO算法對N值做了一定程度的優(yōu)化，比LBP算法少了很多，并且隨著 ARPU面積的增大，相比ELS、CBP、MOTP、LSCBP等算法，AEMO算法所獲得的SD均值也是最小的，而且它還可以對α、β、γ進行動態(tài)調(diào)整，以獲得單一目標的優(yōu)化。

[1]CARDOSO J M P, DINII C D, et al.Compiling for reconf i gurable computing:a survey[J].ACM Computing Surveys, 2010, 42(4):1301-1365.

[2]COMPTON K, HAUCK S.Reconfigurable computing:a survey of systems and software[J].ACM Computing Surveys, 2002, 34(2):171-210.

[3]DASU A, PANCHANATHAN S.Reconfigurable media processing[J].Elsevier’s Parallel Computing, Special Issue on Parallel Computing in Image and Video Processing, 2002, 28(7/8):1111-1139.

[4]CAMPI F, TOMA M, LODI A, et al.A VLIW processor with reconfigurable instruction set for embedded applications[J].IEEE Journal of Solid-State Circuits, 2003, 38(11):1876-1886.

[5]王大偉,竇勇,李思昆.核心循環(huán)到粗粒度可重構(gòu)體系結(jié)構(gòu)的流水化映射[J].計算機學報, 2009, 32(6):1089-1099.WANG D W, DOU Y, LI S K.Loop kernel pipelining mapping onto coarse-grained reconfigurable architectures[J].Chinese Journal of Computers, 2009, 32(6):1089-1099.

[6]于蘇東,劉雷波,尹首一等.嵌入式粗粒度可重構(gòu)處理器的軟硬件協(xié)同設(shè)計流程[J].電子學報, 2009, 37(5):1136-1140.YU S D, LIU L B, YIN S Y, et al.Hardware-software co-design flow for embedded coarse-grained reconfigurable processor[J].Acta Electronica Sinica, 2009, 37(5):1136-1140.

[7]DIMITROULAKOS G, GEORGIOPOULOS S, GALANIS M D, et al.Resource aware mapping on coarse grained reconfigurable arrays[J].Microprocessors and Microsystems, 2009, 33(2):91-105.

[8]LEE G, CHOI K, DUTT N D.Mapping multi-domain applications onto coarse-grained reconfigurable architectures[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2011,30(5):637-650.

[9]GPURNA K M, BHATIA D.Temporal partitioning and scheduling data flow graphs for reconfigurable computers[J].IEEE Transactions on Computers, 1999, 48(6):579-590.

[10]周博, 邱衛(wèi)東, 諶勇輝等.基于簇的層次敏感的可重構(gòu)系統(tǒng)任務(wù)劃分算法[J].計算機輔助設(shè)計與圖形學學報, 2006, 18 (5):667-673.ZHOU B, QIU W D, CHEN Y H , et al.A level sensitive cluster based partitioning algorithms for reconfigurable systems[J].Journal of Computer Aided Design & Computer Graphics, 2006, 18(5):667-673.

[11]JIANG Y C, WANG J F.Temporal partitioning data flow graphs for dynamically reconfigurable computing[J].IEEE Transactions on Very Large Scale Integration Systems, 2007, 15(12):1351-1361.

[12]潘雪增, 孫康, 陸魁軍等.動態(tài)可重構(gòu)系統(tǒng)任務(wù)時域劃分算法[J].浙江大學學報(工學版), 2007, 41(11):1839-1844.PAN X Z, SUN K, LU K J, et al.Temporal task partitioning algorithm for dynamically reconfigurable systems[J].Journal of Zhejiang University (Engineering Science), 2007, 41(11):1839-1844.

[13]CARDOSO J M P, NETO H C.An enhanced static-list scheduling algorithm for temporal partitioning onto RPU[A].Proceedings of 1999 IFIP International Conference on Very Large Scale Integration[C].Lisbon, 1999.485-496.

[14]陳乃金,江建慧,陳昕等.一種考慮執(zhí)行延遲最小化和資源約束的改進層劃分算法[J].電子學報, 2012, 40(5):1055-1066.CHEN N J, JIANG J H, CHEN X, et al.An improved level partitioning algorithm considering minimum execution delay and resource restraints[J].Acta Electronica Sinica, 2012, 40(5):1055-1066.