基于并行度最大化的多目標(biāo)優(yōu)化任務(wù)劃分算法

袁開堅，張興明，高彥釗

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002) (*通信作者電子郵箱kaijian_yuan@163.com)

基于并行度最大化的多目標(biāo)優(yōu)化任務(wù)劃分算法

袁開堅*，張興明，高彥釗

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002) (*通信作者電子郵箱kaijian_yuan@163.com)

針對可重構(gòu)系統(tǒng)硬件任務(wù)劃分并行度最大問題，提出一種基于并行度最大的多目標(biāo)優(yōu)化任務(wù)劃分算法。首先，該算法在滿足可重構(gòu)硬件面積資源和合理依賴關(guān)系的約束下，按廣度優(yōu)先的遍歷方式搜索待劃分的操作節(jié)點(diǎn)；然后，著重考慮執(zhí)行延遲對于系統(tǒng)完成時間的影響，將塊內(nèi)操作節(jié)點(diǎn)的并行度最大化；最后，在減少碎片面積和不增加塊間連接邊數(shù)的原則下接受新的節(jié)點(diǎn)，否則就結(jié)束一個塊劃分。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的基于層劃分(LBP)和基于簇劃分(CBP)兩種算法相比，提出的算法獲得了最大的塊內(nèi)操作并行度，同時還減少了劃分塊數(shù)和塊間的連接邊數(shù)。

可重構(gòu)系統(tǒng)；任務(wù)劃分；并行度最大化；多目標(biāo)優(yōu)化；廣度優(yōu)先搜索

0 引言

現(xiàn)如今隨著可編程邏輯器件的快速發(fā)展，可重構(gòu)計算(Reconfigurable Computing, RC)成為了一種新的計算方式[1]，這種方式可以通過軟件配置結(jié)構(gòu)可變的硬件，故其既具備了軟件的通用性、靈活性，又兼具了專用集成電路(Application Specific Integrated Circuit, ASIC)的高性能低功耗的優(yōu)點(diǎn)?？芍貥?gòu)計算憑借其優(yōu)越性在解決數(shù)字信號處理[2]、多媒體處理[3]、加解密算法[4]等資源密集型計算上，成為了一種理想的選擇。

在可重構(gòu)計算的任務(wù)編譯過程中，由核心循環(huán)轉(zhuǎn)換來的數(shù)據(jù)流圖(Data Flow Graph, DFG)如何被映射到可重構(gòu)處理單元(Reconfigurable Processing Unit, RPU)是實(shí)現(xiàn)可重構(gòu)系統(tǒng)高性能的關(guān)鍵所在[5]。其中轉(zhuǎn)換來的數(shù)據(jù)流圖的節(jié)點(diǎn)表示計算任務(wù)，如加法、減法、乘法等，有向邊表示節(jié)點(diǎn)之間的數(shù)據(jù)依賴關(guān)系[6]。對于一個計算密集型應(yīng)用而言，需要的硬件資源往往大于可重構(gòu)處理單元所能提供的資源。此時需要對任務(wù)劃分成若干個子任務(wù)，分時復(fù)用處理單元上提供的硬件資源，這個過程叫作任務(wù)的時域劃分[7]。

可重構(gòu)計算硬件任務(wù)的時域劃分問題實(shí)質(zhì)就是圖的分割問題，已經(jīng)被證明是一個NP完全問題[8-9]。目前的研究在并行度、塊間通信量、劃分塊數(shù)等影響因素中，往往追求其中一個最優(yōu)解，而忽略了其他因素的優(yōu)化對系統(tǒng)的影響[10]。文獻(xiàn)[11]首次針對可重構(gòu)計算提出了兩種任務(wù)劃分的方法，層劃分和簇劃分?；趯觿澐?Level Based Partitioning, LBP)是采用ASAP(As Soon As Possible)策略分層，根據(jù)貪心算法來提高各個劃分塊中節(jié)點(diǎn)的并行度，但忽略了操作節(jié)點(diǎn)之間的依賴關(guān)系，造成劃分塊之間的通信量增大，并且還產(chǎn)生大量硬件碎片?；诖氐膭澐?Cluster Based Partitioning, CBP)是基于列表的啟發(fā)式算法，將數(shù)據(jù)依賴關(guān)系緊密的操作盡可能地劃分到同一個塊中，以減少劃分塊之間的通信量，復(fù)雜度較低，但是仍然會產(chǎn)生大量的碎片。這兩種方法都是針對單一目標(biāo)的算法，并沒有統(tǒng)籌考慮多個因素的影響。文獻(xiàn)[12]針對簇劃分產(chǎn)生面積碎片問題改進(jìn)，充分利用硬件面積資源減少了劃分塊數(shù)，但又忽略了塊間的通信量。文獻(xiàn)[13]提出了一種劃分塊數(shù)最小化的硬件任務(wù)劃分算法，還考慮了執(zhí)行總延遲、劃分塊之間邊數(shù)等多個因素，有效地減少了可重構(gòu)系統(tǒng)的配置時間，但隨著RPU增大，劃分塊間的邊數(shù)增加，延長了通信延遲。文獻(xiàn)[14-15]利用基因算法雖然獲得較好的劃分結(jié)果，但是以犧牲執(zhí)行延遲為代價，不能很好地滿足可重構(gòu)系統(tǒng)的快速劃分要求。文獻(xiàn)[16]提出了一種并行度最大化的貪婪算法，獲得較大并行度，但此算法假設(shè)資源沒有限制，并沒有考慮實(shí)際存在的硬件碎片問題。

本文針對執(zhí)行延遲最小化的任務(wù)劃分需求，提出了一種基于并行度最大化的多目標(biāo)優(yōu)化(Parallelism Maximization with Multi-objective Optimization, PMMO)可重構(gòu)任務(wù)劃分算法。采用廣度優(yōu)先的遍歷方式，在保證任務(wù)劃分獲得最大的塊內(nèi)并行度下，采取了多種劃分策略，提高資源面積的利用率，綜合優(yōu)化了劃分塊數(shù)和塊間通信量等因素的影響，在實(shí)現(xiàn)并行最大的同時達(dá)到一種多目標(biāo)優(yōu)化的效果。

1 模型的描述與定義

為了研究任務(wù)劃分問題，這里給出數(shù)據(jù)流圖和劃分問題相關(guān)的形式化模型定義。

定義1 一個數(shù)據(jù)流圖可以用G=(V,E,S,L)來表示。節(jié)點(diǎn)vi∈V(1≤i≤n)表示某一具體的運(yùn)算操作符，有向邊eij=〈vi,vj〉,eij∈E表示節(jié)點(diǎn)vi與vj存在依賴關(guān)系，vi是vj先驅(qū)節(jié)點(diǎn)，vj是vi的后繼節(jié)點(diǎn)。在操作符vj運(yùn)算之前，操作符vi必須要先完成運(yùn)算。當(dāng)每一個運(yùn)算符映射到可重構(gòu)處理單元上時，都要有相應(yīng)的所需資源面積和執(zhí)行延遲。用si∈S來表示節(jié)點(diǎn)vi的硬件資源面積，SRPU表示一塊可重構(gòu)處理單元的面積。用li∈L來表示節(jié)點(diǎn)vi的執(zhí)行延遲。

定義2 采用某種劃分方法可以得到一種具有k個模塊的劃分,表示為P={p1,p2,…,pk}。其中第i個劃分塊pi由任務(wù)中的若干個節(jié)點(diǎn)組成。

定義3 一個任務(wù)節(jié)點(diǎn)vi被劃分到某一模塊時，其所有前驅(qū)節(jié)點(diǎn)必須已經(jīng)劃分到已完成執(zhí)行的模塊中，否則就會產(chǎn)生不合理的依賴關(guān)系。當(dāng)兩個劃分模塊之間存在著不合理的依賴關(guān)系，就是一個不合理的劃分。圖1給出了一種劃分示例。假設(shè)每一個節(jié)點(diǎn)操作所需資源相同，即可以用節(jié)點(diǎn)數(shù)表示所需面積資源。設(shè)SRPU=2，限定圖1(a)的每一個劃分塊的節(jié)點(diǎn)數(shù)不能超過2。圖1(b)中的劃分塊p2中的有一個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)在p3中，同時劃分塊p3中的有一個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)也在p2中。無論是按照p1p2p3的順序執(zhí)行，還是按照p1p3p2的順序執(zhí)行，p2和p3之間都產(chǎn)生了不合理的依賴關(guān)系，此劃分是一個不合理的劃分。而圖1(c)中的劃分塊之間都滿足依賴關(guān)系，是一個合理的劃分，可以按照p1p2p3的順序執(zhí)行。

定義4 設(shè)Bi是可重構(gòu)系統(tǒng)對劃分模塊pi配置的時間，Ci是pi與其他模塊進(jìn)行數(shù)據(jù)通信的時間，Di是模塊pi內(nèi)部節(jié)點(diǎn)的執(zhí)行延遲。設(shè)劃分成k個模塊的一個任務(wù)在系統(tǒng)中執(zhí)行所需的總時間記為：

(1)

由式(1)可知，為了使執(zhí)行總時間最少，就要使模塊的配置時間、模塊間的通信時間、模塊內(nèi)的執(zhí)行延遲最小，對應(yīng)地就要減少劃分的模塊數(shù)、減少模塊間的連接邊數(shù)、增大模塊內(nèi)部節(jié)點(diǎn)的執(zhí)行并行性。

圖1 劃分示例

定義5 一個可重構(gòu)系統(tǒng)的時域劃分模型可以描述如下。

輸入：G=(V,E,S,L)，SRPU。

輸出：一種劃分P={p1,p2,…,pk}。

約束條件：

4)待劃分節(jié)點(diǎn)的所有前驅(qū)節(jié)點(diǎn)必須已經(jīng)劃分到已完成執(zhí)行的模塊中。

目標(biāo)：1)執(zhí)行并行度最大化；2)劃分的塊數(shù)較小化；3)盡可能減少劃分塊之間的連接邊數(shù)。

2 算法設(shè)計及分析

2.1 PMMO算法設(shè)計

為了保證一個DFG的任務(wù)劃分獲得最小的執(zhí)行延遲，盡量減少劃分塊數(shù)與塊之間的連接邊數(shù)，PMMO算法在滿足RPU硬件面積資源和合理依賴關(guān)系的約束下，按廣度優(yōu)先的遍歷方式，著重考慮了執(zhí)行延遲對于系統(tǒng)完成時間的影響，最大化劃分塊內(nèi)的并行性，并且優(yōu)化了資源面積的利用。PMMO算法采取以下策略來進(jìn)行算法設(shè)計。

策略1 保證劃分塊內(nèi)的操作并行度最大化。

在滿足資源面積和依賴關(guān)系的前提下，采用廣度優(yōu)先的原則，優(yōu)先選擇當(dāng)前層的操作節(jié)點(diǎn)進(jìn)行劃分。當(dāng)遇到不能滿足約束條件的節(jié)點(diǎn)時跳過，繼續(xù)查找其后處于就緒狀態(tài)的節(jié)點(diǎn)，當(dāng)遍歷搜索到了滿足條件的節(jié)點(diǎn)時，還要考慮加入此節(jié)點(diǎn)之后的塊內(nèi)執(zhí)行延遲不能大于當(dāng)前的塊內(nèi)延遲，這樣才能將節(jié)點(diǎn)添加到當(dāng)前的劃分塊中。當(dāng)本層的就緒節(jié)點(diǎn)搜索完畢時，接著優(yōu)先考慮所屬層號較小的就緒節(jié)點(diǎn)。此策略的目的就是使塊內(nèi)操作并行最大化，從而使整個任務(wù)的執(zhí)行延遲最小化。

策略2 在保證策略1的情況下，充分利用可重構(gòu)處理單元的面積資源。

當(dāng)有多個節(jié)點(diǎn)處于就緒狀態(tài)且執(zhí)行延遲相同時，在保證合理劃分的要求下，優(yōu)先選擇占用硬件面積資源大的操作節(jié)點(diǎn)，使得剩余硬件碎片較小，提高資源的利用率。此外對于隊(duì)首之后的節(jié)點(diǎn)，在滿足剩余硬件資源碎片和不增加執(zhí)行延遲的條件下，貪婪搜索可以將其加入到當(dāng)前塊中，進(jìn)一步減少硬件碎片。此策略的目的是在塊內(nèi)操作并行性最大化下，充分利用處理單元面積資源，減少硬件碎片，盡可能減少劃分的塊數(shù)。

策略3 在保證策略1的情況下，盡量減少劃分塊之間的連接邊數(shù)。

每次將一個節(jié)點(diǎn)劃分到塊中，都要更新當(dāng)前劃分塊與就緒節(jié)點(diǎn)之間的連接邊數(shù)，邊數(shù)越多說明節(jié)點(diǎn)與劃分塊聯(lián)系越緊密，在滿足執(zhí)行延遲的條件下，盡可能將其劃入到塊中。此外當(dāng)有多個就緒節(jié)點(diǎn)都滿足約束要求時且加入節(jié)點(diǎn)后塊間的連接邊數(shù)不大于當(dāng)前的邊數(shù)時，優(yōu)先選擇當(dāng)前塊內(nèi)的后繼節(jié)點(diǎn)，這樣可以使緊密型的操作節(jié)點(diǎn)更多地處于同一劃分塊中。此策略的目的是在操作并行性最大化下，減少劃分塊之間的邊數(shù)，降低塊間的通信時間。

基于以上3個策略，PMMO算法描述如下。

輸入：一個任務(wù)的DFG。 輸出：一個劃分后的DFG、所有劃分塊的執(zhí)行延遲總和、劃分塊數(shù)、塊間的連接邊數(shù)總和。 約束：SRPU、待劃分節(jié)點(diǎn)的所有前驅(qū)節(jié)點(diǎn)必須已經(jīng)劃分到已完成執(zhí)行的模塊中。 init();

//初始化節(jié)點(diǎn)

level();

//計算每個節(jié)點(diǎn)所在層

ready_list();

//就緒節(jié)點(diǎn)列表

采用廣度優(yōu)先遍歷；

while(rList!=NULL) if

((Area_Used+node[vi].area)<=SRPU) 更新使用面積； 更新塊間的邊數(shù)； 更新塊內(nèi)的延遲； quickSort();

//選擇所屬層號較小的節(jié)點(diǎn) End if;

if

((area_used+node[vi].area)>SRPU) 跳過該點(diǎn)，搜索后面滿足條件的節(jié)點(diǎn)； End if;

End while;

while(pList!=NULL) if ((area_used+node[vi].area)<=SRPU)quickSort();

//選擇滿足條件且所用面積最大的節(jié)點(diǎn) 分別計算當(dāng)前塊和加入新節(jié)點(diǎn)之后的邊數(shù)和延遲；if(edges_delt<=0 && delays_delt<=0) 將該點(diǎn)加入塊中，優(yōu)先選擇當(dāng)前塊內(nèi)的后繼節(jié)點(diǎn)； End if;

End if;

End while;

得出劃分塊數(shù);

cal_edges();

//求出劃分塊間的連接邊數(shù)

cal_delays();

//求出劃分塊執(zhí)行延遲總和

2.2 算法時間復(fù)雜度分析

對于一個n個節(jié)點(diǎn)的DFG，已知每個運(yùn)算節(jié)點(diǎn)的類型、執(zhí)行延遲和所用資源數(shù)。時間復(fù)雜度主要分析算法中使用的函數(shù)，初始階段的init()、level()、ready_list()，過程中的quickSort()，結(jié)束階段的cal_edges()、cal_delays()，綜合分析這些函數(shù)即可得到整個算法的時間復(fù)雜度。

初始化函數(shù)init()求得每個節(jié)點(diǎn)入度和出度個數(shù)、前驅(qū)與后繼列表，該函數(shù)的時間復(fù)雜度為O(n2)。level()求得每個運(yùn)算節(jié)點(diǎn)層數(shù)，時間復(fù)雜度為O(n2)。ready_list()就緒節(jié)點(diǎn)列表實(shí)現(xiàn)過程是對每個操作節(jié)點(diǎn)，考察它的所有前驅(qū)節(jié)點(diǎn)，如果所有的前驅(qū)都已經(jīng)過劃分被分配到相應(yīng)模塊中，就將此節(jié)點(diǎn)加入列表，時間復(fù)雜度為O(n)。

當(dāng)節(jié)點(diǎn)未被劃分完全時，要對待劃分節(jié)點(diǎn)重新排序,每次通過快速排序quickSort()求出所屬層號較小的節(jié)點(diǎn)和可以劃入當(dāng)前塊占用硬件資源最大的節(jié)點(diǎn)。大家知道快速排序算法最壞情況下的時間復(fù)雜度為O(n2)，又因?yàn)檫\(yùn)用到快速排序是在節(jié)點(diǎn)未被劃分完全時，所以是在一層循環(huán)下O(n)進(jìn)行的，因此該處理過程的時間復(fù)雜度為O(n3)。

cal_edges()通過掃描n個運(yùn)算節(jié)點(diǎn)及其后繼列表來求出劃分塊間的連接邊數(shù)總和,其時間復(fù)雜度為O(n2)；假設(shè)一個任務(wù)DFG被劃分為k塊，函數(shù)cal_delays()用遞歸調(diào)用求得劃分后所有塊執(zhí)行總延遲，時間復(fù)雜度為O(n·k)。綜上，PMMO算法的時間復(fù)雜度約為O(n3)。

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

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

采用C語言實(shí)現(xiàn)算法，并且與兩種效果較好的單一目標(biāo)算法LBP、CBP作對比。為了便于實(shí)驗(yàn)對比，本文采用了文獻(xiàn)[13]相同的幾類操作運(yùn)算所占用的硬件資源數(shù)(單位用可配置邏輯模塊(Configurable Logic Block， CLB)個數(shù)表示)和時鐘周期數(shù)，即加法、減法、乘法所占的硬件面積資源分別為5 CLB、13 CLB、27 CLB，時鐘周期分別為1，1，2。

本文從數(shù)字信號處理領(lǐng)域選取了6種常用的標(biāo)準(zhǔn)程序集用來驗(yàn)證劃分算法，分別是基- 4、基- 8、基- 16快速傅里葉變換，8×8離散余弦變換，4階矩陣乘法，6×6快速離散余弦變換，所用操作單元數(shù)量如表1所示，操作單元總數(shù)依次增加。實(shí)驗(yàn)硬件環(huán)境為Intel Core i3 CPU,2.53 GHz,RAM 4 GB的筆記本電腦，程序運(yùn)行環(huán)境為Windows 7。SRPU隨機(jī)選取54 CLB、67 CLB、78 CLB。

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

3.2 算法比較

3.2.1 PMMO算法與LBP算法比較

PMMO算法與LBP算法的劃分結(jié)果對比數(shù)據(jù)見表2，其中：D代表執(zhí)行延遲時鐘周期數(shù)，B代表劃分塊數(shù)，E代表塊間的連接邊數(shù)。相比LBP算法，在SRPU為54 CLB時PMMO算法對于執(zhí)行延遲平均減少10.3%，對于劃分塊數(shù)平均減少12.1%，對于塊間連接邊數(shù)平均減少4.6%。在SRPU為67 CLB時PMMO算法對于執(zhí)行延遲平均減少13.1%，對于劃分塊數(shù)平均減少13.7%，對于塊間連接邊數(shù)平均減少7.5%。在SRPU為78 CLB時PMMO算法對于執(zhí)行延遲平均減少17.4%，對于劃分塊數(shù)平均減少15.3%，對于塊間連接邊數(shù)平均減少10.8%。將以上說明的在不同可重構(gòu)硬件資源下各參數(shù)的平均減少率整合在圖2中。LBP算法是減少執(zhí)行延遲較為有效的算法，而提出的PMMO算法在執(zhí)行延遲方面進(jìn)一步改進(jìn)，獲得了較大的操作并行度，并且對于劃分塊數(shù)和連接邊數(shù)也有明顯的減少，具有較好的劃分性能。

表2 不同SRPU值時LBP與PMMO劃分結(jié)果對比

圖2 相比LBP各指標(biāo)的平均減少率

3.2.2 PMMO算法與CBP算法比較

PMMO算法與CBP算法的劃分結(jié)果對比數(shù)據(jù)見表3。相比CBP算法，在SRPU為54 CLB時PMMO算法對于執(zhí)行延遲平均減少25.3%，對于劃分塊數(shù)平均減少14.1%，對于連接邊數(shù)平均減少1.2%。在SRPU為67 CLB時PMMO算法對于執(zhí)行延遲平均減少26.5%，對于劃分塊數(shù)平均減少10.8%，對于連接邊數(shù)平均減少1.7%。在SRPU為78 CLB時PMMO算法對于執(zhí)行延遲平均減少28.2%，對于劃分塊數(shù)平均減少13.1%，對于連接邊數(shù)平均減少2.5%。將以上說明的在不同可重構(gòu)硬件資源下各參數(shù)的平均減少量整合在圖3中。在執(zhí)行延遲和劃分塊數(shù)方面相比CBP算法，提出的算法均有顯著改善，但由于CBP是減少塊間通信量的較好的算法，所以對于連接邊數(shù)的改進(jìn)不是非常明顯。

通過以上實(shí)驗(yàn)對比結(jié)果可以看出，PMMO算法相比LBP、CBP算法，對于減少執(zhí)行延遲有顯著的效果，對于減少劃分塊數(shù)也有明顯的效果，因?yàn)長BP、CBP算法一遇到不滿足的節(jié)點(diǎn)就結(jié)束一個塊的劃分，而PMMO則采用貪婪策略，搜索到更多的節(jié)點(diǎn)劃分到塊中，盡可能地減少劃分塊數(shù)。然而在保證塊內(nèi)并行度最大和較少的劃分塊數(shù)的情況下，再降低塊間通信量的空間就較為有限，因而算法的塊間通信量的降低幅度小于其他兩種目標(biāo)參數(shù)的改進(jìn)幅度。并且通過圖2～3可以看出，相比LBP、CBP，提出的算法在總的可重構(gòu)硬件資源數(shù)增加時，執(zhí)行延遲、劃分塊數(shù)和連接邊數(shù)的平均減少率都有所提高，這說明PMMO算法在硬件資源較大時，表現(xiàn)出的劃分性能更好，所以更適用于大數(shù)據(jù)量應(yīng)用的任務(wù)劃分場景。

表3 不同SRPU值時CBP與PMMO劃分結(jié)果對比

圖3 相比CBP各指標(biāo)的平均減少率

4 結(jié)語

本文針對可重構(gòu)任務(wù)劃分問題，提出了一種PMMO算法。該算法采用廣度優(yōu)先的遍歷方式，綜合考慮多種影響因素，采取了多種劃分策略，利用數(shù)字信號處理領(lǐng)域標(biāo)準(zhǔn)程序集轉(zhuǎn)化來的DFG進(jìn)行實(shí)驗(yàn)，與LBP、CBP算法比較，獲得了最大的塊內(nèi)操作并行度，同時還能減少劃分塊數(shù)和塊間連接邊數(shù)，得到的劃分結(jié)果具有明顯改善。

References)

[1] DEHON A. Fundamental underpinnings of reconfigurable computing architectures [J]. Proceedings of the IEEE, 2015, 103(3): 355-378.

[2] ROSSI D, CAMPI F, DELEDDA A, et al. A heterogeneous digital signal processor implementation for dynamically reconfigurable computing [C]// CICC ’09: Proceedings of the 2009 Custom Integrated Circuits Conference. Piscataway, NJ: IEEE, 2009: 641-644.

[3] GENG T, LIU L, YIN S, et al. Parallelization of computing-intensive tasks of the H.264 high profile decoding algorithm on a reconfigurable multimedia system [J]. IEICE Transactions on Information & Systems, 2010, 93-D(12): 3223-3231.

[4] 陳韜,羅興國,李校南,等.一種基于流處理框架的可重構(gòu)分簇式分組密碼處理結(jié)構(gòu)模型[J].電子與信息學(xué)報,2014,36(12):3027-3034.(CHEN T, LUO X G, LI X N, et al. An architecture of stream based reconfigurable clustered block cipher processing array [J]. Journal of Electronics & Information Technology, 2014, 36(12): 3027-3034.)

[5] HUANG M, NARAYANA V, BAKHOUYA M, et al. Efficient mapping of task graphs onto reconfigurable hardware using architectural variants [J]. IEEE Transactions on Computers, 2012, 61(9): 1354-1360.

[6] JIAN 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.

[7] OUNI B, AYADI R, MTIBAA A. Temporal partitioning of data flow graph for dynamically reconfigurable architecture [J]. Journal of Systems Architecture, 2011, 57(8): 790-798.

[8] OU C W, RANKA S. Parallel incremental graph partitioning [J]. IEEE Transactions on Parallel & Distributed Systems, 1997, 8(8): 884-896.

[9] CARDOSO J, P O M, DINIZ P C, et al. Compiling for reconfigurable computing: a survey [J]. ACM Computing Surveys, 2010, 42(4): 1301-1365.

[10] YIN C, YIN S, LIU L, et al. Temporal partitioning algorithm for a coarse-grained reconfigurable computing architecture [C]// Proceedings of the 2009 IEEE International Symposium on Integrated Circuits. Piscataway, NJ: IEEE, 2009: 659-662.

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

[12] 周博,邱衛(wèi)東,諶勇輝,等.基于簇的層次敏感的可重構(gòu)系統(tǒng)任務(wù)劃分算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,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.)

[13] 陳乃金,江建慧.融合面積估算和多目標(biāo)優(yōu)化的硬件任務(wù)劃分算法[J].通信學(xué)報,2013,34(2):40-55.(CHEN N J, JIANG J H. Hardware-task partitioning algorithm merged area estimation with multi-objective optimization [J]. Journal on Communications, 2013, 34(2): 40-55.)

[14] SHENG W, HE W, JIANG J, et al. Pareto optimal temporal partition methodology for reconfigurable architectures based on multi-objective genetic algorithm [C]// Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum. Piscataway, NJ: IEEE, 2012: 425-430.

[15] ZHOU Y, SHENG W, LIU X, et al. Efficient temporal task partition for coarse-grain reconfigurable systems based on simulated annealing genetic algorithm [C]// Proceedings of the 2011 IEEE 9th International Conference on ASIC. Piscataway, NJ:IEEE, 2011: 941-944.

[16] KAO C C. Performance-oriented partitioning for task scheduling of parallel reconfigurable architectures [J]. IEEE Transactions on Parallel & Distributed Systems, 2015, 26(3): 858-867.

This work is partially supported by the National Science and Technology Major Project (2016ZX01012101), the National Natural Science Foundation of China (61572520, 61521003).

YUANKaijian, born in 1993, M. S. candidate. His research interests include chip system design, reconfigurable computing.

ZHANGXingming, born in 1963, M. S., professor. His research interests include broadband information network, high performance computing.

GAOYanzhao, born in 1984, Ph. D., assistant research fellow. His research interests include high performance computing.

Taskpartitioningalgorithmbasedonparallelismmaximizationwithmulti-objectiveoptimization

YUAN Kaijian*, ZHANG Xingming, GAO Yanzhao

(NationalDigitalSwitchingSystemEngineering&TechnologicalResearchCenter,ZhengzhouHenan450002,China)

Concerning the parallelism maximization of hardware task partitioning in reconfigurable system, a task partitioning algorithm based on parallelism maximization for multi-objective optimization was proposed. Firstly, the operating nodes to be partitioned were discovered according to the breadth first search under the constraints of hardware area resource and reasonable dependency relation. Then, considering the effect of execution delay on system completion time, the parallelism of intra-block operations was maximized. Finally, the new nodes were accepted under the principle of reducing the fragment area without increasing the number of connections between blocks. Otherwise, a block partitioning was ended. The experimental results show that the proposed algorithm achieves the maximum intra-block parallelism and reduces the number of blocks and connecting edges compared with the existing Level Based Partitioning (LBP) and Cluster Based Partitioning (CBP) algorithms.

reconfigurable system; task partitioning; parallelism maximization; multi-objective optimization; breadth first search

TP316

:A

2017- 01- 24;

:2017- 03- 08。

國家科技重大專項(xiàng)(2016ZX01012101)；國家自然科學(xué)基金資助項(xiàng)目(61572520, 61521003)。

袁開堅(1993—)，男，江蘇淮安人，碩士研究生，主要研究方向：芯片系統(tǒng)設(shè)計、可重構(gòu)計算； 張興明(1963—)，男，河南新鄉(xiāng)人，教授，碩士，主要研究方向：寬帶信息網(wǎng)絡(luò)、高性能計算； 高彥釗(1984—)，男，河北平山人，助理研究員，博士，主要研究方向：高性能計算。

1001- 9081(2017)07- 1916- 05

10.11772/j.issn.1001- 9081.2017.07.1916