基于離散粒子群優(yōu)化的可重構(gòu)系統(tǒng)任務(wù)調(diào)度算法

祁曉峰,張興明,高彥釗

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,鄭州 450002)

1 引 言

可重構(gòu)系統(tǒng)由通用處理器和可重構(gòu)計(jì)算器件組成,支持不同應(yīng)用程序靈活地配置和執(zhí)行.可重構(gòu)計(jì)算處理器在功能靈活性上類似通用處理器,在功耗能效上接近專用計(jì)算電路,兼具軟硬件計(jì)算資源的優(yōu)點(diǎn),是高效能計(jì)算處理器研究的重要方向.在執(zhí)行應(yīng)用程序的過程中,可重構(gòu)系統(tǒng)編譯器將應(yīng)用劃分,按一定順序配置和執(zhí)行任務(wù).由于可重構(gòu)計(jì)算資源有限,為充分利用資源,劃分到可重構(gòu)器件上的任務(wù)需要動態(tài)配置.如何靈活地調(diào)度硬件任務(wù),保持較高的資源利用率,以及如何通過調(diào)度策略保證軟硬件任務(wù)合理配合,縮短任務(wù)完成時間是可重構(gòu)系統(tǒng)任務(wù)編譯的關(guān)鍵問題.

為解決可重構(gòu)系統(tǒng)的任務(wù)調(diào)度問題,國內(nèi)外學(xué)者已經(jīng)做出豐富的研究.可重構(gòu)系統(tǒng)任務(wù)調(diào)度問題屬于NP(Non-Deterministic Polynomial)問題[1],需要優(yōu)化算法的運(yùn)行時間,同時保證算法解的質(zhì)量.研究學(xué)者將啟發(fā)式方法,尤其是智能種群算法和仿生算法[2-4],引入到可重構(gòu)系統(tǒng)任務(wù)調(diào)度模型中,求解任務(wù)調(diào)度問題時間快并且能夠得到較高質(zhì)量的任務(wù)調(diào)度方案.評價啟發(fā)式方法的性能主要從以下四個方面:求解質(zhì)量、運(yùn)行時間、可靠性和擴(kuò)展性.大多數(shù)基于啟發(fā)式方法的調(diào)度策略能夠滿足第一個因素,生成高質(zhì)量的近似最優(yōu)解.通過優(yōu)化和調(diào)整,其中一些算法能夠在較短運(yùn)行時間內(nèi)產(chǎn)生調(diào)度方案.但是由于啟發(fā)式方法的結(jié)果是隨機(jī)產(chǎn)生的近似解,因此缺少可靠性.此外,由于缺少擴(kuò)展性,算法隨任務(wù)規(guī)模增加而求解質(zhì)量下降,運(yùn)行時間增加.

另一方面,由于算法針對特定功能和特征的系統(tǒng),新功能特征的出現(xiàn)導(dǎo)致以前方法不再適用.例如配置預(yù)取功能允許配置提前進(jìn)行.下一個任務(wù)配置操作與當(dāng)前任務(wù)的執(zhí)行操作同時進(jìn)行,因此配置時間能夠有效隱藏在其他任務(wù)的執(zhí)行過程中[5].文獻(xiàn)[6]基于配置預(yù)取功能設(shè)計(jì)可重構(gòu)任務(wù)調(diào)度策略,能夠大幅降低任務(wù)調(diào)度時間,但是該調(diào)度策略的算法復(fù)雜度較高.文獻(xiàn)[7]在帶有配置預(yù)取的可重構(gòu)系統(tǒng)中,使用蟻群算法求解調(diào)度策略,極大降低了算法運(yùn)行時間,但該方法忽略了最優(yōu)解的可靠性,并且解質(zhì)量還有待進(jìn)一步提高.針對以上問題,本文提出一種帶有預(yù)生成策略的離散粒子群優(yōu)化算法,充分利用算法優(yōu)勢設(shè)計(jì)適用于可配置預(yù)取的可重構(gòu)系統(tǒng)的任務(wù)調(diào)度方案求解策略.

為使用粒子群優(yōu)化算法解決任務(wù)調(diào)度問題,本文在第二節(jié)介紹可重構(gòu)系統(tǒng)軟硬件任務(wù)并行協(xié)同調(diào)度模型;第三節(jié)設(shè)計(jì)調(diào)度方案的編解碼策略和離散粒子群算法,根據(jù)系統(tǒng)約束設(shè)計(jì)算法的評價機(jī)制,并且提出預(yù)處理策略提高算法求解質(zhì)量和可靠性;第四節(jié)進(jìn)行實(shí)驗(yàn)仿真,比較多個數(shù)據(jù)集下的算法性能;在第五節(jié)對全文進(jìn)行總結(jié).

2 問題描述

2.1 問題模型

任務(wù)調(diào)度策略面向異構(gòu)動態(tài)部分可重構(gòu)系統(tǒng),系統(tǒng)組成架構(gòu)如圖1所示.可重構(gòu)系統(tǒng)主要由主CPU控制器、通用處理器和可重構(gòu)計(jì)算器件組成.主CPU生成任務(wù)調(diào)度策略的控制信息和配置信息,控制用于執(zhí)行軟件任務(wù)的通用處理器和用于執(zhí)行硬件任務(wù)的可重構(gòu)計(jì)算處理單元(RPU Reconfigurable Processing Unit)進(jìn)行協(xié)同計(jì)算.RPU由若干個可以重復(fù)配置的可重構(gòu)單元陣列(RCA Reconfigurable Cell Array)組成,每個RCA都由若干個運(yùn)算單元(PE Processing Element)排列組合而成.

圖1 可重構(gòu)系統(tǒng)組成架構(gòu)Fig.1 Framework of reconfigurable system

圖2 可重構(gòu)系統(tǒng)任務(wù)調(diào)度模型Fig.2 Task scheduling model of reconfigurable system

圖2是可重構(gòu)系統(tǒng)的任務(wù)調(diào)度模型.系統(tǒng)首先將應(yīng)用程序代碼劃分為由可重構(gòu)器件執(zhí)行的硬件任務(wù)和由通用處理器執(zhí)行的軟件任務(wù).調(diào)度器將硬件任務(wù)和軟件任務(wù)協(xié)同調(diào)度生成調(diào)度方案.調(diào)度方案包括預(yù)配置隊(duì)列、硬件任務(wù)隊(duì)列和軟件任務(wù)隊(duì)列三組調(diào)度控制信息.預(yù)配置隊(duì)列的控制信息加載到配置器中為硬件任務(wù)配置可重構(gòu)計(jì)算資源.布局器按照硬件任務(wù)隊(duì)列控制信息將硬件任務(wù)布局到運(yùn)算單元陣列執(zhí)行.軟件任務(wù)按照軟件任務(wù)隊(duì)列控制信息依次在通用處理器執(zhí)行.在可重構(gòu)器件上執(zhí)行的硬件任務(wù)需要配置完成后才能運(yùn)行.配置預(yù)取操作指在任務(wù)模塊運(yùn)行的同時,同步進(jìn)行下一個任務(wù)的配置,從而達(dá)到隱藏配置時間的目的.由于任務(wù)模塊配置信息從配置資源池中調(diào)用,故稱該操作為配置預(yù)取.配置時間指對可重構(gòu)器件進(jìn)行配置編程花費(fèi)的時間,執(zhí)行時間是計(jì)算任務(wù)花費(fèi)的時間.由于配置時間相對執(zhí)行時間不可忽略,因此對配置時間進(jìn)行加速或隱藏是提高可重構(gòu)系統(tǒng)調(diào)度性能的關(guān)鍵.

圖3 任務(wù)圖描述的應(yīng)用實(shí)例

圖3是使用有向無環(huán)圖(Directed Acyclic Graph,DAG)描述的應(yīng)用任務(wù)圖實(shí)例.設(shè)任務(wù)圖G={T,E}.T={T1,T2,…,Tn}表示任務(wù)模塊.任務(wù)模塊有兩種類型,S表示軟件任務(wù),H表示硬件任務(wù),即T=S∪H.對于任意Si∈S,Si可描述為二元組{tSi,texcute,Si},tSi是任務(wù)Si的執(zhí)行開始時間,texcute,Si是任務(wù)Si的執(zhí)行持續(xù)時間.對于任意Hi∈H,Hi可描述為六元組{wHi,hHi,tHi,texcute,Hi,cHi,cexcute,Hi},其中wHi和hHi是硬件任務(wù)Hi占用可重構(gòu)資源的寬度和長度,tHi是任務(wù)Hi執(zhí)行開始時間,texcute,Hi是任務(wù)Hi的執(zhí)行持續(xù)時間,cHi是任務(wù)Hi的配置開始時間,cexcute,Hi是硬件任務(wù)Hi的配置持續(xù)時間.E={eij}表示任務(wù)Ti和Tj之間的數(shù)據(jù)依賴關(guān)系,|eij|是任務(wù)Ti和Tj的通信功耗.|eij|≠0時,任務(wù)Ti和Tj之間不存在數(shù)據(jù)依賴.|eij|≠0時,Ti執(zhí)行完后才能執(zhí)行Tj.

為簡化表示任務(wù)模塊在系統(tǒng)中的配置和執(zhí)行時間,定義任務(wù)周期概念如下.

定義1.任務(wù)周期Δt是任務(wù)配置和執(zhí)行的最小時間單位.任務(wù)配置或執(zhí)行的時間通過任務(wù)周期的規(guī)整得到,是整數(shù)倍的任務(wù)周期.不妨假設(shè)任務(wù)的配置或執(zhí)行時間為t,如果(n-1)·Δt

可重構(gòu)系統(tǒng)采用配置預(yù)取隱藏任務(wù)配置時間.為用任務(wù)圖描述配置預(yù)取功能,本文采用改進(jìn)的有向無環(huán)圖表示任務(wù)圖.改進(jìn)的任務(wù)圖如圖4所示.硬件任務(wù)的配置操作是一種新的任務(wù)模塊C(m,n).C(m,n)表示任務(wù)Hm在RPUn中進(jìn)行配置.C(m,n)可描述為二元組C(m,n)=(tc(m,n),texcute,c(m,n)),其中配置任務(wù)執(zhí)行開始時間是任務(wù)Hm的配置開始時間,即tc(m,n)=cHm.配置任務(wù)的執(zhí)行持續(xù)時間是任務(wù)Hm的配置持續(xù)時間,即texcute,c(m,n)=cexcute,Hm.配置信息從系統(tǒng)配置資源池中直接調(diào)用,配置任務(wù)執(zhí)行持續(xù)時間無顯著差異,可將配置任務(wù)的執(zhí)行持續(xù)時間texcute,c(m,n)統(tǒng)一設(shè)置為一個任務(wù)周期,即texcute,c(m,n)=Δt.任務(wù)調(diào)度受到任務(wù)時間依賴關(guān)系和硬件資源面積的約束.系統(tǒng)基本約束如下:

圖4 改進(jìn)的任務(wù)圖描述的應(yīng)用實(shí)例Fig.4 An application represented by improved task graph

1)對于任意兩個任務(wù)Ti和Tj,如果Ti和Tj之間存在數(shù)據(jù)依賴關(guān)系,Ti執(zhí)行結(jié)束的時間不能超過Tj執(zhí)行開始的時間.

?eij≠0,tTi+texcute,Ti≤tTj

(1)

2)對于任意硬件任務(wù)Hi,Hi配置結(jié)束的時間不能超過Hi執(zhí)行開始的時間.

?Hi,cHi+cexcute,Hi≤tTi

(2)

3)?RPUi,在同一時刻,RPUi只能配置或執(zhí)行一個硬件任務(wù).

4)?Hi,配置或執(zhí)行Hi時不能超出系統(tǒng)RPU個數(shù)的限制.

圖5 可重構(gòu)系統(tǒng)任務(wù)調(diào)度時序?qū)嵗鼺ig.5 An example of reconfigurable system task scheduling solution

圖5是圖4所示應(yīng)用的一個任務(wù)調(diào)度方案實(shí)例.調(diào)度方案不同,應(yīng)用執(zhí)行所花費(fèi)的時間不同.任務(wù)調(diào)度問題的目標(biāo)是生成一個合理的調(diào)度方案,最小化任務(wù)執(zhí)行時間.該調(diào)度方案既要滿足系統(tǒng)基本約束,又要充分利用空閑計(jì)算資源將任務(wù)配置過程隱藏.因此本文將任務(wù)調(diào)度問題看成一個多目標(biāo)優(yōu)化(Multi-objective Optimization,MOP)的NP問題,并使用粒子群優(yōu)化算法解決該問題.

2.2 粒子群優(yōu)化算法

任務(wù)調(diào)度問題是一個復(fù)雜的組合優(yōu)化問題,其可能的任務(wù)調(diào)度方案隨任務(wù)個數(shù)的增加呈指數(shù)型增長[8],并且由于任務(wù)之間受依賴關(guān)系和系統(tǒng)資源的約束,難以求出精確的最優(yōu)解.因此,在較短時間內(nèi)找到問題的近似最優(yōu)解具有重要意義.粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是解決該類問題的有效方法,使用PSO算法解決任務(wù)調(diào)度問題具有以下優(yōu)勢:1)參數(shù)簡單,易于實(shí)現(xiàn);2)解決指數(shù)爆炸問題;3)算法收斂速度快.

使用粒子群優(yōu)化算法解決最優(yōu)化問題,問題的解對應(yīng)搜索空間中的粒子,每個粒子有一個速度決定他們進(jìn)化的方向和距離.算法通過適應(yīng)函數(shù)(fitness function)評價的每個粒子的適應(yīng)值.粒子通過適應(yīng)值評價機(jī)制追隨當(dāng)前的最優(yōu)粒子,在解空間中逐代更新自身的速度搜索最優(yōu)解.

圖6 粒子群優(yōu)化算法Fig.6 Particle swarm optimization algorithm

粒子群算法基本概念如下.一個由m個粒子(Particle)組成的群體(Swarm)在D維搜索空間中以一定的速度飛行,每個粒子在搜索時,比較自己搜索到的歷史最好點(diǎn)和群體內(nèi)其它粒子的最好點(diǎn),在此基礎(chǔ)上進(jìn)行位置的變化.第i個粒子的位置表示為xi=(xi1,xi2,…,xiD);其速度為vi=(vi1,vi2,…,viD),1≤d≤D;其個體歷史最優(yōu)點(diǎn)為pi=(pi1,pi2,…,piD),1≤i≤m;群體粒子最優(yōu)點(diǎn)pg=(pg1,pg2,…,pgD).粒子群優(yōu)化算法的步驟見圖6.

一般來說,粒子的位置和速度都是在連續(xù)的實(shí)數(shù)空間內(nèi)進(jìn)行取值,粒子的位置和速度根據(jù)如下方程進(jìn)行變化:

(3)

(4)

其中,ω為慣性權(quán)重,c1和c2為學(xué)習(xí)因子,一般為正常數(shù).學(xué)習(xí)因子使粒子進(jìn)行自我學(xué)習(xí)并向群體中優(yōu)秀個體學(xué)習(xí),朝個體最優(yōu)值和群體最優(yōu)值靠近.ξ,η∈U[0,1],是在[0,1]區(qū)間內(nèi)均勻分布的隨機(jī)數(shù).粒子的速度被限制在一個最大Vmax的范圍內(nèi).

3 離散粒子群優(yōu)化任務(wù)調(diào)度算法

3.1 任務(wù)編碼

為使用PSO算法解決任務(wù)調(diào)度問題,首先需要將任務(wù)調(diào)度方案進(jìn)行編碼作為PSO算法的粒子.不妨假設(shè)待調(diào)度的任務(wù)個數(shù)為N,按照任務(wù)執(zhí)行時間順序和可重構(gòu)單元陣列序號由小到大的順序,列出描述調(diào)度方案的任務(wù)序列P:

P={Ti|i∈N}

(5)

以圖5表示的調(diào)度方案為例,按照時間順序,其編碼的任務(wù)序列為:

P={S1,H1,H3,H2,H5,H4,H6,H7,S2}

(6)

該序列即任務(wù)調(diào)度問題的一個解.通過以下步驟將該序列表示的調(diào)度方案解碼.

針對Step 3,具體操作如下:依次從第一個任務(wù)周期的第一塊RCA開始檢查是否有可配置空間.對于已經(jīng)被占用的配置空間,從該任務(wù)配置開始直至任務(wù)執(zhí)行結(jié)束是配置空間被占用的時間,該期間根據(jù)系統(tǒng)限制不能配置其他任務(wù),任務(wù)執(zhí)行結(jié)束后自動清除配置信息并釋放配置空間資源.待執(zhí)行任務(wù)一旦定位到空閑資源空間,判斷空閑空間資源是否滿足任務(wù)配置需求,配置需求根據(jù)任務(wù)的大小決定.若不能滿足需求,則等待配置空間釋放后配置任務(wù).

表1 調(diào)度方案解碼步驟
Table 1 Steps for solution decoding

輸入：經(jīng)編碼的調(diào)度方案輸出：解碼后的調(diào)度結(jié)果Step1．載入待執(zhí)行任務(wù)．Step2．判斷是否是硬件任務(wù)．是，則跳轉(zhuǎn)到Step3；否則，跳轉(zhuǎn)到Step5．Step3．配置任務(wù)．Step4．判斷是否滿足依賴關(guān)系．是，則跳轉(zhuǎn)到Step5；否則跳轉(zhuǎn)到Step7．Step5．執(zhí)行任務(wù)．Step6．判斷是否是最后一個任務(wù)．是，則調(diào)轉(zhuǎn)到Step8；否則跳轉(zhuǎn)到Step1．Step7．輸出調(diào)度結(jié)果花費(fèi)時間．

針對Step 4,依賴關(guān)系指任務(wù)相關(guān)時間依賴關(guān)系,是系統(tǒng)的基本約束,包括任務(wù)之間的依賴關(guān)系和同一個任務(wù)配置時間和執(zhí)行時間的依賴關(guān)系.任務(wù)調(diào)度算法按位依次循環(huán)判斷該編碼能否滿足系統(tǒng)的約束條件.

對式(6)中的編碼任務(wù)序列解碼,得到調(diào)度方案為:

P:S1→{H1,C1,0,C1,1,C1,2}→{H3,C3,3}→
{H2,C2,0,C2,1}→{H5,C5,2},→{H4,C4,3}→
{H6,C6,0}→{H7,C7,1}→S2

(7)

綜上可知,該解碼策略保證了任務(wù)調(diào)度方案與PSO算法的粒子一一對應(yīng),構(gòu)造出任務(wù)調(diào)度方案的解空間.可使用PSO算法在解空間求解任務(wù)調(diào)度問題的最優(yōu)解.

3.2 離散粒子群優(yōu)化算法

傳統(tǒng)PSO算法適用于連續(xù)空間的優(yōu)化問題,而任務(wù)調(diào)度問題的解是離散的.因此本文對PSO算法的運(yùn)算符號和規(guī)則進(jìn)行改進(jìn)以適用任務(wù)調(diào)度問題.

定義2.交換子SF(i,j).設(shè)任務(wù)個數(shù)為N,任務(wù)序列P={Ti|i∈N},交換子SF(i1,i2),i1∈N,i2∈N.Ti1和Ti2是P中的元素,交換子SF的作用是交換任務(wù)序列P中任務(wù)Ti1和任務(wù)Ti2的位置,產(chǎn)生新的任務(wù)序列P′.即P′=P+SF(i1,i2).

定義3.交換序SS.交換序SS是多個交換子SF(i,j)的集合,即SS={SF1,SF2,…,SFn},表示按照交換子SFi在集合中的順序依次進(jìn)行交換操作.若干個交換序可以合并成一個新的交換序.不同的交換序作用于同一任務(wù)序列P上可能產(chǎn)生相同的任務(wù)序列,能產(chǎn)生相同效果的交換序的集合是交換序的等價集.在交換序等價集中,擁有最少交換子的交換序是該等價集的基本交換序.

可重構(gòu)系統(tǒng)任務(wù)調(diào)度問題的優(yōu)化目標(biāo)是最小化應(yīng)用執(zhí)行時間,PSO算法的適應(yīng)函數(shù)根據(jù)該優(yōu)化目標(biāo),通過計(jì)算調(diào)度方案的執(zhí)行時間得到每個調(diào)度方案的適應(yīng)值.在解碼過程中記錄最后一個任務(wù)的執(zhí)行開始時間,并加上其執(zhí)行持續(xù)時間即整個調(diào)度方案實(shí)現(xiàn)的所花費(fèi)的時間,即可得到任務(wù)調(diào)度粒子群優(yōu)化算法的適應(yīng)值.當(dāng)不同任務(wù)調(diào)度方案的歷史最優(yōu)或全局最優(yōu)值出現(xiàn)相同的情況時,算法默認(rèn)該子代粒子的任務(wù)調(diào)度方案為最優(yōu).

3.3 預(yù)生成策略

由于任務(wù)調(diào)度問題受到的系統(tǒng)約束復(fù)雜,按照PSO算法的隨機(jī)初始化策略存在一定概率不能產(chǎn)生滿足系統(tǒng)約束的調(diào)度方案,PSO算法初期因搜索盲目而效率降低.本文提出預(yù)生成策略解決該問題,提高PSO算法求解任務(wù)調(diào)度方案的效率.

根據(jù)任務(wù)圖中任務(wù)的編號規(guī)律可知,任意兩個任務(wù)Ti和Tj,若i

表2 預(yù)生成策略步驟
Table 2 Steps for pre-generation algorithm

輸入：按任務(wù)序列編號的任務(wù)調(diào)度方案輸出：預(yù)生成任務(wù)編碼調(diào)度方案Step1．按照任務(wù)編號順序，載入待執(zhí)行任務(wù)，并標(biāo)記下一個任務(wù)為待執(zhí)行任務(wù)．Step2．判斷是否是硬件任務(wù)．是，則跳轉(zhuǎn)到Step3；否則跳轉(zhuǎn)到Step5．Step3．判斷是否有資源空間滿足任務(wù)配置．是，則跳轉(zhuǎn)至Step6；否則跳轉(zhuǎn)至Step4．Step4．將當(dāng)前任務(wù)與待執(zhí)行任務(wù)交換，并重新標(biāo)記為待執(zhí)行任務(wù)．Step5．判斷是否滿足系統(tǒng)約束條件．是，則跳轉(zhuǎn)至Step6；否則跳轉(zhuǎn)至Step4．Step6．配置執(zhí)行當(dāng)前任務(wù)，更新資源空間．Step7．判斷是否是最后一個任務(wù)．是，則調(diào)轉(zhuǎn)到Step8；否則跳轉(zhuǎn)到Step1．Step8．輸出調(diào)度任務(wù)編碼．

經(jīng)預(yù)生成策略,算法可以產(chǎn)生至少一個滿足系統(tǒng)約束的解,該初始解引導(dǎo)粒子群體進(jìn)化的方向.預(yù)生成策略可以產(chǎn)生至少一個初始解,能夠避免粒子群算法不能產(chǎn)生滿足系統(tǒng)條件的解的問題,同時提高算法收斂的速度.

4 實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)建立

本文選取隨機(jī)測試用例和實(shí)際應(yīng)用數(shù)據(jù)集評估算法性能.隨機(jī)測試用例的任務(wù)圖由TGFF[9]隨機(jī)生成,參考文獻(xiàn)中設(shè)計(jì)的綜合應(yīng)用數(shù)據(jù)集[10],生成規(guī)模分別為20、50、80個任務(wù)的集合;實(shí)際應(yīng)用數(shù)據(jù)集采用不同任務(wù)個數(shù)的LU分解[11]和Gauss-Jordan消元[12]作為待調(diào)度的應(yīng)用算法任務(wù)集合.對比算法選取自適應(yīng)蟻群算法(AACO)[7]、混合遺傳算法(HPSO-GA)[13]和線性規(guī)劃方法(MILP)[14],在不同任務(wù)規(guī)模下對算法求解質(zhì)量、可靠性和運(yùn)行時間進(jìn)行比較.其中,在實(shí)驗(yàn)中采用MILP方法作為評價其他算法的基準(zhǔn).實(shí)驗(yàn)仿真在MATLAB中進(jìn)行,操作系統(tǒng)為Windows7,4GB內(nèi)存、2.5GHz Intel Xeon.

實(shí)驗(yàn)面向的可重構(gòu)器件按照Xilinx Virtex XCV1000 規(guī)模定義,采用96*64 個RCU,分成四塊RCA[15].異構(gòu)架構(gòu)的可重構(gòu)系統(tǒng)在進(jìn)行任務(wù)時域調(diào)度前需要對任務(wù)圖進(jìn)行軟硬件劃分,該劃分操作以及隨機(jī)生成的任務(wù)執(zhí)行時間、配置時間和任務(wù)占用硬件面積資源等屬性參數(shù)參考文獻(xiàn)[7，13，16].

4.2 實(shí)驗(yàn)分析

4.2.1 求解質(zhì)量

給定系統(tǒng)資源限制時,任務(wù)規(guī)模對算法的求解質(zhì)量影響較大.實(shí)驗(yàn)采用不同任務(wù)規(guī)模的隨機(jī)任務(wù)、LU分解和Gauss-Jordan消元數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集,比較幾種不同算法的求解質(zhì)量.在任務(wù)調(diào)度中,調(diào)度方案的適應(yīng)值越小,求解質(zhì)量越優(yōu)秀.不同數(shù)據(jù)集中的任務(wù)執(zhí)行時間和任務(wù)配置時間以各自數(shù)據(jù)集的任務(wù)周期大小為基準(zhǔn),因此不同的數(shù)據(jù)集產(chǎn)生的調(diào)度方案時間相互沒有影響,本實(shí)驗(yàn)關(guān)注同一數(shù)據(jù)集下不同算法的性能.

圖7-圖9是不同算法使用三類數(shù)據(jù)集產(chǎn)生的調(diào)度方案用時的條形圖.MILP算法是規(guī)劃類的方法,可以求出精確的全局最優(yōu)解.本文算法與AACO和HPSO-GA算法屬于啟發(fā)式方法,啟發(fā)式方法在解空間中搜索收斂,具有較快的執(zhí)行時間,但是只能求出近似最優(yōu)解,解的質(zhì)量低于MILP算法.表3是調(diào)度方案用時的具體數(shù)據(jù),由實(shí)驗(yàn)數(shù)據(jù)可知,本文算法的求解質(zhì)量同MILP算法的結(jié)果相近,即近似最優(yōu)解收斂程度較高,求解質(zhì)量較高.同屬于啟發(fā)類的三種算法相比較,本文算法的求解質(zhì)量優(yōu)于AACO算法和HPSO-GA算法,求解質(zhì)量平均分別提高13.2%和32.3%.

圖7 隨機(jī)任務(wù)的調(diào)度方案用時Fig.7 Quality of random tasks scheduling solutions

圖8 Gauss-Jordan消元任務(wù)調(diào)度方案用時Fig.8 Quality of gauss-jordan elimination scheduling solutions

圖9 LU分解任務(wù)圖的調(diào)度方案用時Fig.9 Quality of LU-decomposition scheduling solutions

表3 調(diào)度方案用時(單位:Δt)
Table 3 Scheduling solutions of algorithms(Δt)

隨機(jī)任務(wù)8205080MILP8112240PPSO8132341AACO9152745HPSO?GA10183050LU分解14202735MILP17222535PPSO17242636AACO19242839HPSO?GA21273445Gauss?Jordan消元15212836MILP6142126PPSO6142126AACO8142530HPSO?GA10173033

4.2.2 算法可靠性

啟發(fā)式方法能求出近似最優(yōu)解,其結(jié)果具有一定隨機(jī)性.如果算法產(chǎn)生的結(jié)果不穩(wěn)定,調(diào)度結(jié)果甚至可能出現(xiàn)未能滿足系統(tǒng)約束的情況.當(dāng)解的變化范圍趨于穩(wěn)定時,可認(rèn)為該算法是可靠的.為驗(yàn)證算法可靠性,對于隨機(jī)任務(wù)個數(shù)為80的數(shù)據(jù)集,進(jìn)行百次實(shí)驗(yàn)并記錄算法的調(diào)度結(jié)果,統(tǒng)計(jì)算法產(chǎn)生滿足系統(tǒng)約束的調(diào)度方案的次數(shù),如圖10所示.MILP可以得出全局最優(yōu)解,其可靠性達(dá)100%,PPSO算法由于使用了預(yù)處理策略,也具有較高的穩(wěn)定性和可靠性.AACO算法和HPSO-GA算法由于缺少預(yù)處理策略,在收斂過程中依賴初始化的程度較高,因此可靠性低于本文算法.

圖10 算法可靠性Fig.10 Reliability of algorithms

4.2.3 算法運(yùn)行時間

由以上實(shí)驗(yàn)可以看出,規(guī)劃類方法MILP算法具有較好的求解質(zhì)量和可靠性.本文算法的調(diào)度結(jié)果接近于MILP算法的實(shí)驗(yàn)結(jié)果,并優(yōu)于AACO算法和HPSO-GA算法的實(shí)驗(yàn)結(jié)果.對比算法的執(zhí)行時間,結(jié)果如表4所示.由表4可以看出,本文算法和AACO算法、HPSO-GA算法均具有較快的執(zhí)行時間.盡管MILP算法在求解質(zhì)量上具有優(yōu)勢,但其執(zhí)行時間相比于三種啟發(fā)式方法差距一個甚至數(shù)個數(shù)量級.其中,本文算法兼具高求解質(zhì)量和可靠性,并且具有較快的執(zhí)行時間,在時間和性能評價標(biāo)準(zhǔn)中取得了較好的綜合效果.

表4 算法執(zhí)行時間(單位:秒)
Table 4 Execution time of algorithms(s)

隨機(jī)任務(wù)8205080MILP7．6>10>10>10PPSO0．730．891．372．00AACO0．730．891．31．82HPSO?GA0．861．051．622．31LU分解14202735MILP>10>10>10>10PPSO0．750．840．921．03AACO0．750．810．890．99HPSO?GA0．820．981．121．27Gauss?Jordan消元15212836MILP>10>10>10>10PPSO0．750．90．890．98AACO0．740．90．80．96HPSO?GA0．821．110．981．2

5 結(jié) 論

本文面向異構(gòu)動態(tài)部分可重構(gòu)系統(tǒng),對帶有配置預(yù)取的可重構(gòu)系統(tǒng)任務(wù)調(diào)度問題進(jìn)行研究,提出了帶有預(yù)處理機(jī)制的離散粒子群優(yōu)化算法解決任務(wù)調(diào)度問題.針對可重構(gòu)系統(tǒng)的任務(wù)調(diào)度問題模型,設(shè)計(jì)適用于該模型的任務(wù)編解碼策略,并提出預(yù)生成初始解的策略,提高算法的可靠性并降低執(zhí)行時間.實(shí)驗(yàn)結(jié)果表明,對比MILP算法、AACO算法和HPSO-GA算法,本文算法執(zhí)行時間短,可有效提高調(diào)度方案質(zhì)量,并且具有較高的可靠性.本文尚有不足之處,在調(diào)度過程中以任務(wù)配置執(zhí)行的時間作為調(diào)度策略優(yōu)劣的評價標(biāo)準(zhǔn),忽略了任務(wù)之間的線長和通信時間,即沒有考慮任務(wù)配置的布局策略.在今后工作中,有待對可重構(gòu)系統(tǒng)任務(wù)布局策略做進(jìn)一步研究.

[1] Pan Z,Wells B E.Hardware supported task scheduling on dynamically reconfigurable SoC architectures[J].Very Large Scale Integration Systems IEEE Transactions on,2008,16(11):1465-1474.

[2] Ferrandi F,Lanzi P L,Pilato C,et al.Ant colony optimization for mapping,scheduling and placing in reconfigurable systems[C].Adaptive Hardware and Systems,IEEE,2013:47-54.

[3] Kumar N,Vidyarthi D P.A novel hybrid PSO-GA meta-heuristic for scheduling of DAG with communication on multiprocessor systems[J].Engineering with Computers,2016,32(1):35-47.

[4] Al-Wattar A,Areibi S,Grewal G.An efficient evolutionary task scheduling/binding framework for reconfigurable systems[J].International Journal of Reconfigurable Computing,2016,2016(2):1-24.

[5] Li Z,Hauck S.Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation[C].Acm/sigda Tenth International Symposium on Field-Programmable Gate Arrays,DBLP,2002:187-195.

[6] Liang Liang,Zhou Xue-gong,Wang Ying,et al.Pre-configuration based hybrid tasks scheduling in reconfigurable systems[J].Journal of Computer-Aided Design & Computer Graphics,2007,19(5):635-641.

[7] Mollajafari M,Shahhoseini H S.An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph[J].Applied Intelligence,2016,45(3):695-712.

[8] Sun Kang.Research on reconfigurable computing technologies[D].Hangzhou:Zhejiang University College of Computer Science and Technology,2007.

[9] ]Dick R P,Rhodes D L,Wolf W.TGFF task graphs for free[C].Hardware/Software Codesign,(CODES/CASHE ′98) Proceedings of the Sixth International Workshop on.IEEE Xplore,1998:97-101.

[10] Filho J G,Strum M,Chau W J.Using genetic algorithms for hardware core placement and mapping in NoC-based reconfigurable systems[J].International Journal of Reconfigurable Computing,2015，2015:1-13.

[11] Jin S,Schiavone G,Turgut D.A performance study of multiprocessor task scheduling algorithms[J].The Journal of Supercomputing,2008,43(1):77-97.

[12] Gerasoulis A,Yang T.Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods[J].Applied Numerical Mathematics,1994,16(1-2):283-297.

[13] Bonyadi M R,Moghaddam M E.A bipartite genetic algorithm for multi-processor task scheduling[J].International Journal of Parallel Programming,2009,37(5):462-487.

[14] Deiana E A,Rabozzi M,Cattaneo R,et al.A multiobjective reconfiguration-aware scheduler for fpga-based heterogeneous architectures[C].ReConFigurable Computing and FPGAs (ReConFig),2015 International Conference on.IEEE,2015:1-6.

[15] Yang Zhi-hua,Wu Wei-guo,Wang Tao,et al.A double-arbiter time-sliced tasks scheduling algorithm for reconfigurable system[J].Chinese Journal of Computers,2013,36(9):1850-1867.

[16] Qi X,Zhang X,Yuan K.RLDRPSO:an efficient heuristic algorithm for task partitioning[M].Advanced Computer Architecture,Springer Singapore,2016.

附中文參考文獻(xiàn)：

[6] 梁 樑,周學(xué)功,王 穎,等.采用預(yù)配置策略的可重構(gòu)混合任務(wù)調(diào)度算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報,2007,19(5):635-641.

[8] 孫 康.可重構(gòu)計(jì)算相關(guān)技術(shù)研究[D].杭州:浙江大學(xué),2007.

[15] 楊志華,伍衛(wèi)國,王 濤,等.一種基于雙仲裁時間片策略的可重構(gòu)硬件任務(wù)調(diào)度算法[J].計(jì)算機(jī)學(xué)報,2013,36(9):1850-1867.