陳乃金，江建慧

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

1 引言

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

2 相關(guān)研究

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

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

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

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

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

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

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

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

3 問(wèn)題定義

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

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

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

定義2 一個(gè)DFG的劃分問(wèn)題可以描述如下。

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

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

約束條件:

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

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

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

圖2 一個(gè)不合理劃分的例子

4 AEMO算法

4.1 AEMO算法設(shè)計(jì)

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

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

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

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

例1 假設(shè)算術(shù)表達(dá)式中允許包含2種括號(hào):圓括號(hào)和方括號(hào)，其嵌套的順序合理，則一個(gè)算術(shù)表達(dá)式可表示為: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ù)表達(dá)式的 DFG如圖 3(a)所示，其層次為 9，原始輸入邊有17條，原始輸出邊有 1條，非原始輸入輸出邊數(shù)為29條，有23個(gè)運(yùn)算任務(wù)節(jié)點(diǎn)，其集合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)所示)進(jìn)行預(yù)劃分獲得的硬件碎片均為area1= area2=65?54=11，雖然v3、v4均有劃入的可能，但是卻不能劃入。為此引入第2種方案。

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

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

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

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

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

策略 3 優(yōu)先選擇優(yōu)先級(jí)高的節(jié)點(diǎn)和當(dāng)前層任務(wù)節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 各類(lèi)運(yùn)算的時(shí)延和占用資源量

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

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

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

例 2 圖 4(a)給出了一個(gè)正在劃分的部分DFG，假設(shè)v1和v2點(diǎn)已經(jīng)被劃入到P1中(如圖4(b)所示)?，F(xiàn)考察就緒節(jié)點(diǎn)v3和v4，設(shè)v3和v4運(yùn)算類(lèi)型相同且位于同一層，在 ARPU的約束下，P1還可以劃入 v3或 v4點(diǎn)中一個(gè)，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。

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

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

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

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

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

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

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

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

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

表2 劃分基準(zhǔn)程序集

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

AEMO算法描述如圖7所示。

4.2 算法時(shí)間復(fù)雜度分析

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

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

圖7 AEMO算法

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

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

4.3 一個(gè)算術(shù)表達(dá)式劃分實(shí)例分析

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

1) 圖 3(a)入度為 0的就緒節(jié)點(diǎn)為 v1～v5，w1=w2=w3=27，w4=w5=5，d1=d2=2，d3= d4= d5=1，就緒節(jié)點(diǎn)v1、v2、v3、v4、v5與當(dāng)前正在劃分的模塊有向邊的數(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作為起點(diǎn)進(jìn)行DFS貪婪劃分，v1被劃入P1(如圖8(a)所示)，則劃分后剩余節(jié)點(diǎn)集合 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時(shí)AEMO1與AEMO的劃分結(jié)果

圖8 圖3(a)算術(shù)表達(dá)式DFG的第一個(gè)劃分過(guò)程

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

2) 由于v6為v1的入度已經(jīng)更新為0的后繼，在滿(mǎn)足ARPU前提下，按DFS直接預(yù)劃入(如圖8(b)所示)，劃分后剩余節(jié)點(diǎn)集合 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é)點(diǎn)退回去，相關(guān)節(jié)點(diǎn)的信息復(fù)原。

3) 從v1開(kāi)始，按權(quán)值進(jìn)行BFS層貪婪劃分。由圖8(a)可知，就緒節(jié)點(diǎn)為v2、v3、v4、v5、v6分別計(jì)算其權(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)先級(jí)，因此按FIFO原則先劃入v2，劃分后剩余節(jié)點(diǎn)集合 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ǎn)調(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é)點(diǎn)為 v3、v6、v7、v8，分別計(jì)算其權(quán)值，prior_assigned (v3)的值小，優(yōu)先級(jí)高，在ARPU約束下，以v3為起點(diǎn)按DFS依次劃入v8、v11、v13，因?yàn)?area_filled=42，area1=65?42=23＞value，故以v3為起點(diǎn)按權(quán)值進(jìn)行BFS層貪婪劃分，劃分P2節(jié)點(diǎn)調(diào)度序列依次為 v3、v6、v8、v11，劃分后剩余節(jié)點(diǎn)集合 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以?xún)?yōu)先級(jí)最高v7為起點(diǎn)，依次劃入v7、v10，因?yàn)関12的前驅(qū)可以劃入，故v9、v12一并劃入，而v12、v14不能同時(shí)劃入，故計(jì)算area1=ARPU?(w7+w10+w9+w12)=65?(27+13+13+5)=7＜value，更新v13、v14的入度為1，故本次劃分按DFS進(jìn)行，更新就緒點(diǎn)的探測(cè)函數(shù)值，發(fā)現(xiàn)v12可以貪婪劃入，綜上，劃分 P3節(jié)點(diǎn)調(diào)度序列依次為 v7、v10、v9、v12、v13，劃分后剩余節(jié)點(diǎn)集合 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以?xún)?yōu)先級(jí)最高v14為起點(diǎn)，其節(jié)點(diǎn)調(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í)行。需要說(shuō)明的是，在選取v18和v17時(shí)，正在劃分的模塊與就緒節(jié)點(diǎn)之間的邊數(shù)s起了重要的作用，α=1/9，γ=β=1，level(v17)= level(v18)=6，就緒節(jié)點(diǎn) v17、v18與當(dāng)前正在劃分的模塊有向邊的數(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ǎn)調(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 實(shí)驗(yàn)及其分析

本文采用 C語(yǔ)言實(shí)現(xiàn)了 ESL、CBP、LSCBP、MOTP、LBP、AEMO 6種時(shí)域劃分算法，所用的劃分基準(zhǔn)程序集，統(tǒng)計(jì)劃分塊間輸出邊的數(shù)量方式，ARPU的3種取值，參數(shù)α、β、γ的選取等均同4.1節(jié)所述。CBP和LBP、LSCBP算法的模塊計(jì)數(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。

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

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

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

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

5.2 AEMO算法與CBP算法的比較

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

5.3 AEMO算法與ESL算法的比較

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

5.4 AEMO算法與MOTP算法的比較

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

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

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

5.5 AEMO算法與LSCBP算法的比較

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

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

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

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

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

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

本文提出了一個(gè) AEMO算法，該算法考察了待劃分就緒運(yùn)算節(jié)點(diǎn)的實(shí)際情況，實(shí)現(xiàn)動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的調(diào)度次序，而且綜合考慮了 DFG劃分塊數(shù)和執(zhí)行總延遲、劃分塊之間非I/O邊數(shù)等多個(gè)因素，實(shí)驗(yàn)結(jié)果表明，與LBP、ELS、CBP、MOTP和LSCBP等5種算法相比較，AEMO算法具有最小的M值，即劃分模塊數(shù)少，這意味著配置次數(shù)就少，這是影響計(jì)算密集型任務(wù)關(guān)鍵循環(huán)加速的主要因素之一。AEMO算法對(duì)N值做了一定程度的優(yōu)化，比LBP算法少了很多，并且隨著 ARPU面積的增大，相比ELS、CBP、MOTP、LSCBP等算法，AEMO算法所獲得的SD均值也是最小的，而且它還可以對(duì)α、β、γ進(jìn)行動(dòng)態(tài)調(diào)整，以獲得單一目標(biā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].計(jì)算機(jī)學(xué)報(bào), 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ì)流程[J].電子學(xué)報(bào), 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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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]潘雪增, 孫康, 陸魁軍等.動(dòng)態(tài)可重構(gòu)系統(tǒng)任務(wù)時(shí)域劃分算法[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版), 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ìn)層劃分算法[J].電子學(xué)報(bào), 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.