基于并行度最大化的多目標優化任務劃分算法

袁開堅，張興明，高彥釗

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

基于并行度最大化的多目標優化任務劃分算法

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

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

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

可重構系統；任務劃分；并行度最大化；多目標優化；廣度優先搜索

0 引言

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

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

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

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

1 模型的描述與定義

為了研究任務劃分問題，這里給出數據流圖和劃分問題相關的形式化模型定義。

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

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

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

定義4 設Bi是可重構系統對劃分模塊pi配置的時間，Ci是pi與其他模塊進行數據通信的時間，Di是模塊pi內部節點的執行延遲。設劃分成k個模塊的一個任務在系統中執行所需的總時間記為：

(1)

由式(1)可知，為了使執行總時間最少，就要使模塊的配置時間、模塊間的通信時間、模塊內的執行延遲最小，對應地就要減少劃分的模塊數、減少模塊間的連接邊數、增大模塊內部節點的執行并行性。

圖1 劃分示例

定義5 一個可重構系統的時域劃分模型可以描述如下。

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

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

約束條件：

4)待劃分節點的所有前驅節點必須已經劃分到已完成執行的模塊中。

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

2 算法設計及分析

2.1 PMMO算法設計

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

策略1 保證劃分塊內的操作并行度最大化。

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

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

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

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

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

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

輸入：一個任務的DFG。 輸出：一個劃分后的DFG、所有劃分塊的執行延遲總和、劃分塊數、塊間的連接邊數總和。 約束：SRPU、待劃分節點的所有前驅節點必須已經劃分到已完成執行的模塊中。 init();

//初始化節點

level();

//計算每個節點所在層

ready_list();

//就緒節點列表

采用廣度優先遍歷；

while(rList!=NULL) if

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

//選擇所屬層號較小的節點 End if;

if

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

End while;

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

//選擇滿足條件且所用面積最大的節點 分別計算當前塊和加入新節點之后的邊數和延遲；if(edges_delt<=0 && delays_delt<=0) 將該點加入塊中，優先選擇當前塊內的后繼節點； End if;

End if;

End while;

得出劃分塊數;

cal_edges();

//求出劃分塊間的連接邊數

cal_delays();

//求出劃分塊執行延遲總和

2.2 算法時間復雜度分析

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

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

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

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

3 實驗及結果分析

3.1 實驗設計

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

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

表1 劃分基準程序集

3.2 算法比較

3.2.1 PMMO算法與LBP算法比較

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

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

圖2 相比LBP各指標的平均減少率

3.2.2 PMMO算法與CBP算法比較

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

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

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

圖3 相比CBP各指標的平均減少率

4 結語

本文針對可重構任務劃分問題，提出了一種PMMO算法。該算法采用廣度優先的遍歷方式，綜合考慮多種影響因素，采取了多種劃分策略，利用數字信號處理領域標準程序集轉化來的DFG進行實驗，與LBP、CBP算法比較，獲得了最大的塊內操作并行度，同時還能減少劃分塊數和塊間連接邊數，得到的劃分結果具有明顯改善。

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] 陳韜,羅興國,李校南,等.一種基于流處理框架的可重構分簇式分組密碼處理結構模型[J].電子與信息學報,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] 周博,邱衛東,諶勇輝,等.基于簇的層次敏感的可重構系統任務劃分算法[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.)

[13] 陳乃金,江建慧.融合面積估算和多目標優化的硬件任務劃分算法[J].通信學報,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。

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

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

1001- 9081(2017)07- 1916- 05

10.11772/j.issn.1001- 9081.2017.07.1916