融合面積估算和多目標優化的硬件任務劃分算法

陳乃金，江建慧

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

1 引言

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

2 相關研究

傳統的 DFG時域劃分算法根據電路的抽象層次可大致分為網表級時域劃分和行為級時域劃分 2類算法。網表級時域劃分算法針對的是電路。基于網絡流的網表級時域劃分算法將電路定義為一個網絡流，它可表示為由門和寄存器所組成的節點集、由門和寄存器之間的連接所組成的邊集，以及由門和寄存器的面積所組成的面積等3個集合所構成的三元組。而一個計算密集型任務或程序的關鍵循環可以用 DFG表示，圖中每個節點表示一個操作符（或運算符），對這樣的圖所進行的時域劃分通常稱為行為級時域劃分。

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

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

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

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

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

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

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

3 問題定義

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

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

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

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

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

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

約束條件:

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

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

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

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

4 AEMO算法

4.1 AEMO算法設計

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

策略 1 可重構劃分面積邏輯容量估算和按權值調度劃分同時進行，獲得最小的劃分塊數。

下面給出2種實現方案。

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

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

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

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

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

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

由上可知，策略2側重于同時考慮了硬件碎片利用、硬件劃分的吞吐量、執行延遲大節點的優先響應等因素，其目的是想同時獲得任務 DFG劃分塊數和所有劃分塊總的執行延遲的較小化。

策略 3 優先選擇優先級高的節點和當前層任務節點。

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

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

由上可知，策略3側重于考慮任務DFG劃分塊內運算節點的并行度。

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

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

由上可知，策略4在策略1～策略3的基礎上，側重于減少劃分塊之間I/O邊數。

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

1) 層次大優先級高的節點應優先響應

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

2) 優先劃入出度較大的運算節點

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

3) 防止劃分塊間運算任務節點非法依賴關系的產生

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

由上可知，策略5中的1)側重于考慮任務DFG劃分塊內運算節點的并行度；策略5中的2)側重于優化每次劃分；策略5中的3)側重于防止任務DFG每個劃分塊之間產生非法依賴。

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

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

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

探測函數構造的基本思想如下。

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

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

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

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

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

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

圖5 解釋優先級高且層次較大節點優先響應的例子

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

圖6 解釋出度大的點被優先劃分的例子

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

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

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

表2 劃分基準程序集

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

AEMO算法描述如圖7所示。

4.2 算法時間復雜度分析

AEMO算法在執行前，一個 DFG總的運算節點數、每個運算節點的執行延遲、運算類型和占用的資源數，每個節點前驅與后繼的個數及列表均已知。

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

圖7 AEMO算法

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

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

4.3 一個算術表達式劃分實例分析

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

1) 圖 3(a)入度為 0的就緒節點為 v1～v5，w1=w2=w3=27，w4=w5=5，d1=d2=2，d3= d4= d5=1，就緒節點v1、v2、v3、v4、v5與當前正在劃分的模塊有向邊的數量均為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)所示)，則劃分后剩余節點集合 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的劃分結果

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

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

2) 由于v6為v1的入度已經更新為0的后繼，在滿足ARPU前提下，按DFS直接預劃入(如圖8(b)所示)，劃分后剩余節點集合 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和其前驅v4一并劃入，則w9+w4=18＞area1，由于area1=11大于閾值value，故本次按DFS劃分不成功，把劃入的節點退回去，相關節點的信息復原。

3) 從v1開始，按權值進行BFS層貪婪劃分。由圖8(a)可知，就緒節點為v2、v3、v4、v5、v6分別計算其權值prior_assigned(v2)=prior_assigned(v3) ≈ 0.0037，prior_assigned(v4)=prior_assigned(v5)≈0.0159，prior_assigned (v6)=0.0072，由于v2、v3具有相同的優先級，因此按FIFO原則先劃入v2，劃分后剩余節點集合 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，節點調度序列依次為 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)可知，就緒節點為 v3、v6、v7、v8，分別計算其權值，prior_assigned (v3)的值小，優先級高，在ARPU約束下，以v3為起點按DFS依次劃入v8、v11、v13，因為 area_filled=42，area1=65?42=23＞value，故以v3為起點按權值進行BFS層貪婪劃分，劃分P2節點調度序列依次為 v3、v6、v8、v11，劃分后剩余節點集合 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以優先級最高v7為起點，依次劃入v7、v10，因為v12的前驅可以劃入，故v9、v12一并劃入，而v12、v14不能同時劃入，故計算area1=ARPU?(w7+w10+w9+w12)=65?(27+13+13+5)=7＜value，更新v13、v14的入度為1，故本次劃分按DFS進行，更新就緒點的探測函數值，發現v12可以貪婪劃入，綜上，劃分 P3節點調度序列依次為 v7、v10、v9、v12、v13，劃分后剩余節點集合 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以優先級最高v14為起點，其節點調度序列依次為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執行。需要說明的是，在選取v18和v17時，正在劃分的模塊與就緒節點之間的邊數s起了重要的作用，α=1/9，γ=β=1，level(v17)= level(v18)=6，就緒節點 v17、v18與當前正在劃分的模塊有向邊的數量分別為 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相比劃分塊間的邊數少了一條。

7) 同理，按DFS貪婪劃分得到P5如圖10所示，其節點調度序列依次為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={Φ}，劃分結束。

5 實驗及其分析

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

5.1 AEMO算法與LBP算法的比較

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

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

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

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

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

5.2 AEMO算法與CBP算法的比較

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

5.3 AEMO算法與ESL算法的比較

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

5.4 AEMO算法與MOTP算法的比較

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

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

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

5.5 AEMO算法與LSCBP算法的比較

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

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

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

從上述實驗比較結果可以看出，AEMO算法與LBP、ESL、CBP、MOTP、LSCBP等 5種算法相比，AEMO算法獲得的M是最小的；除LBP算法之外，AEMO算法的SD均值是最小的，但N值完全優于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 結束語

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

[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]王大偉,竇勇,李思昆.核心循環到粗粒度可重構體系結構的流水化映射[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]于蘇東,劉雷波,尹首一等.嵌入式粗粒度可重構處理器的軟硬件協同設計流程[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]周博, 邱衛東, 諶勇輝等.基于簇的層次敏感的可重構系統任務劃分算法[J].計算機輔助設計與圖形學學報, 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]潘雪增, 孫康, 陸魁軍等.動態可重構系統任務時域劃分算法[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]陳乃金,江建慧,陳昕等.一種考慮執行延遲最小化和資源約束的改進層劃分算法[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.