基于量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度探討

基于量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度探討

摘要:任務(wù)調(diào)度是網(wǎng)絡(luò)并行計(jì)算系統(tǒng)的核心問題之一。在有向無環(huán)圖(DAG)描述問題的基礎(chǔ)上，提出了一種進(jìn)行并行任務(wù)調(diào)度的量子粒子群優(yōu)化算法。首先對(duì)DAG并行任務(wù)調(diào)度問題作出定義，并給出了優(yōu)化問題的目標(biāo);然后分別探討了問題的編碼表示、解碼方案、位置向量的計(jì)算方法、離散問題連續(xù)化、算法的總體流程等;最后給出算法的仿真實(shí)驗(yàn)情況與研究，實(shí)驗(yàn)結(jié)果表明，該算法有良好的全局尋優(yōu)性能和快捷的收斂速度，調(diào)度效果優(yōu)于遺傳算法和粒子群優(yōu)化算法。

關(guān)鍵詞:任務(wù)調(diào)度;量子粒子群優(yōu)化;有向無環(huán)圖?

ResearchonDAGparalleltaskschedulingproblembasedon?quantum-behavedparticleswarmoptimization

ZHANGCong，SHENHui-zhang

(AntaiCollegeofEconomics&Management，ShanghaiJiaotongUniversity，Shanghai200052，China)

Abstract:Taskschedulingisoneoftheimportantproblemsinparallelcomputingsystem.Thispaperproposedaquantum-?behavedparticleswarmoptimizationalgorithmfortaskschedulingbasedondirectedacyclicgraph.Firstredefinedtheparalleltaskschedulingproblemanditsaim.Thendiscussedtherepresentationoftheencoding，theprocedureofthedecoding，thecomputationalmethodofpositionvector，thecontinuativeofthediscreteproblemandthestructureofthealgorithmrespectively.Intheend，presentedthealgorithmsimulation，experimentresultanalysisandtheconclusions.Thesimulationresultsshowthatthisalgorithmhasbetterglobaloptimizingabilityandmorerapidconvergence，anditissuperiortogeneticalgorithmandparticleswarmoptimizationalgorithm.

Keywords:taskscheduling;quantum-behavedparticleswarmoptimization(QPSO);directedacyclicgraph(DAG)

網(wǎng)絡(luò)并行計(jì)算環(huán)境下的任務(wù)調(diào)度問題是指在一定約束條件下，如何將一組任務(wù)分配到多臺(tái)處理機(jī)上執(zhí)行的組合優(yōu)化問題，其已被證明是NP完全問題，不可能在多項(xiàng)式時(shí)間內(nèi)找到問題的最優(yōu)解[1，2]。目前常見的并行任務(wù)調(diào)度問題按照任務(wù)之間有無數(shù)據(jù)依賴關(guān)系可以劃分為獨(dú)立任務(wù)調(diào)度和依賴關(guān)系任務(wù)調(diào)度。前者在調(diào)度任務(wù)時(shí)不需要考慮任務(wù)之間的數(shù)據(jù)依賴關(guān)系;而后者通常用有向無環(huán)圖(DAG)表示任務(wù)之間的數(shù)據(jù)依賴關(guān)系，在調(diào)度過程中滿足任務(wù)之間的數(shù)據(jù)依賴關(guān)系。依賴關(guān)系任務(wù)調(diào)度的求解優(yōu)化過程比獨(dú)立任務(wù)調(diào)度的要復(fù)雜許多，且其適用范圍也更廣。以DAG表示的并行任務(wù)模型的研究得到了廣泛關(guān)注和迅速發(fā)展。近年出現(xiàn)的一些啟發(fā)式算法(如模擬退火算法、遺傳算法等)為求解此類NP完全問題提供了新的途徑[3~5]，但是這些算法有些復(fù)雜性太高難以實(shí)現(xiàn)，有些實(shí)現(xiàn)起來太費(fèi)時(shí)，所以有必要尋求更好的算法來解決此問題。

粒子群優(yōu)化(PSO)算法是由Kennedy等人[6]提出的一種源于對(duì)鳥群捕食行為模擬的進(jìn)化計(jì)算技術(shù)，已成為進(jìn)化計(jì)算的一個(gè)最吸引人的分支。與遺傳算法類似，PSO是一種基于迭代的優(yōu)化方法，系統(tǒng)初始化為一組隨機(jī)解，通過迭代搜尋最優(yōu)值，但是在許多實(shí)際應(yīng)用領(lǐng)域，更勝于遺傳算法，尤其是在非線性優(yōu)化問題上。量子粒子群優(yōu)化(QPSO)算法是在傳統(tǒng)的PSO基礎(chǔ)上提出的一種新型的具有高效率全局搜索能力的進(jìn)化算法[7，8]。它主要是引入量子物理的思想改進(jìn)了PSO的進(jìn)化方法，即更新粒子位置的方法;在更新粒子位置時(shí)重點(diǎn)考慮各個(gè)粒子的當(dāng)前局部最優(yōu)位置信息和全局最優(yōu)位置信息。QPSO具有調(diào)整參數(shù)少、容易實(shí)現(xiàn)、收斂能力強(qiáng)等優(yōu)勢(shì)。為適應(yīng)任務(wù)分配問題的求解，本文設(shè)計(jì)出合適的粒子編碼，利用改進(jìn)的量子粒子群算法求解任務(wù)分配問題，并與其他算法相比較。實(shí)驗(yàn)結(jié)果表明，本文提出的算法可以獲得質(zhì)量更高的解職稱論文。

1問題描述

本模型的計(jì)算系統(tǒng)由一系列異構(gòu)的處理機(jī)組成，需要處理的總?cè)蝿?wù)已分解成一系列子任務(wù)。模型的約束條件為:任務(wù)執(zhí)行具有非搶占性，即處理機(jī)只有在執(zhí)行完某個(gè)任務(wù)之后才能處理另外一個(gè)任務(wù);另外這些任務(wù)之間具有前驅(qū)后繼的數(shù)據(jù)依賴關(guān)系，某個(gè)子任務(wù)只有在其所有的前驅(qū)任務(wù)處理完畢后才能開始執(zhí)行。該模型的調(diào)度目標(biāo)就是要使得整個(gè)DAG圖的調(diào)度長度最短。

為了便于分析問題，可以用下列五元組表述:

Π=(P，G，Θ，Ψ，Ω)

其中:

P={P?1，P?2，…，P?n}為n個(gè)處理機(jī)的集合。

G是子任務(wù)集T的依賴關(guān)系圖，它通過DAG來表示各個(gè)子任務(wù)間的調(diào)度約束關(guān)系。G=(T，E)，其中T={T?1，T?2，…，T?m}為m個(gè)子任務(wù)的集合，一個(gè)子任務(wù)T?i就是圖G中的一個(gè)節(jié)點(diǎn)，E是任務(wù)依賴關(guān)系圖中的有向邊集。〈T?i，T?j〉∈E(i，j=1，2，…，m)，則表示在子任務(wù)T?i沒有完成之前，任務(wù)T?j不能執(zhí)行。這時(shí)稱T?i為T?j的一個(gè)前驅(qū)，T?j為T?i的一個(gè)后繼，E可用鄰接矩陣存儲(chǔ)。

Θ是一個(gè)m×n矩陣，其元素θij表示任務(wù)T?i在處理機(jī)P?j上的執(zhí)行時(shí)間，假設(shè)每個(gè)任務(wù)的執(zhí)行時(shí)間預(yù)知(i=1，2，…，m;?j=1，2，…，n)。

Ψ是一個(gè)m×m矩陣，其元素ψij表示任務(wù)T?i與T?j之間的數(shù)據(jù)傳輸延時(shí)(i，j=1，2，…，m)，同時(shí)假設(shè)各處理機(jī)間的通信能力是相同的，且忽略網(wǎng)絡(luò)擁塞，即傳輸?shù)臄?shù)據(jù)量是惟一影響ψij大小的因素。

Ω是一個(gè)m×n的任務(wù)分配矩陣，其中ωij=1表示T?i分配到處理機(jī)P?j上執(zhí)行;否則ωij=0(i=1，2，…，m;j=1，2，…，n)。

要實(shí)現(xiàn)的目標(biāo)是尋找一個(gè)分配調(diào)度策略，將m個(gè)子任務(wù)分配到n個(gè)處理機(jī)上，合理調(diào)度各個(gè)子任務(wù)的執(zhí)行次序，使得各子任務(wù)在滿足依賴關(guān)系圖G的約束下，整個(gè)任務(wù)的完成時(shí)間最短。現(xiàn)假設(shè)某一合法的分配調(diào)度S，將T中的m個(gè)子任務(wù)分配到n個(gè)處理機(jī)上，其中子任務(wù)T?i被分配到處理機(jī)P?j上執(zhí)行，那么子任務(wù)T?i在處理機(jī)P?j上的執(zhí)行時(shí)間滿足以下兩式:

St(T?i，P?j)=maxT?k∈Pred(T?i)(Ft(T?k，P?r)+(1-ωkj)ψki)(1)

Ft(T?i，P?j)=St(T?i，P?j)+θij;i，k=1，2，…，m;j，r=1，2，…，n

(2)

其中:St(T?i，P?j)和Ft(T?i，P?j)分別表示子任務(wù)T?i在處理機(jī)P?j上的開始執(zhí)行時(shí)刻和結(jié)束執(zhí)行時(shí)刻;Pred(T?i)表示子任務(wù)T?i的前驅(qū)節(jié)點(diǎn)集合，假設(shè)子任務(wù)T?k∈Pred(T?i)被分配到處理機(jī)?P?r上。

根據(jù)式(1)(2)迭代計(jì)算，可得到所有子任務(wù)的結(jié)束執(zhí)行時(shí)刻。設(shè)Γ(S)為在調(diào)度策略S下完成任務(wù)所使用的總時(shí)間，那么:Γ(S)=max(Ft(T?i，P?j));?i=1，2，…，m;j=1，2，…，n。

任務(wù)調(diào)度目標(biāo)就是min(Γ(S))?S，即尋找一個(gè)分配調(diào)度S，使得Γ(S)最小。

鑒于本文主要考慮任務(wù)調(diào)度問題，在不失問題一般性的情況下，可忽略數(shù)據(jù)傳輸延時(shí)，即在下文中可假設(shè)所有的ψij=0。

2算法

2.1PSO算法

粒子群優(yōu)化(PSO)算法是一種進(jìn)化計(jì)算方法，是一種基于迭代的優(yōu)化工具。該算法通過群體中各粒子間的合作與競爭來搜索全局最優(yōu)點(diǎn)。

系統(tǒng)初始化為一組共n個(gè)隨機(jī)解，通過迭代搜尋整個(gè)群體的最優(yōu)值。粒子i的當(dāng)前位置為x?i=(xi1，xi2，…，xid)，其飛行速度記為v?i=(vi1，vi2，…，vid)，在解空間中追隨適應(yīng)度最優(yōu)的粒子進(jìn)行搜索。在每一次迭代中，粒子通過跟蹤兩個(gè)“極值”來更新自己:a)每個(gè)粒子本身所找到的最優(yōu)解pbest。如果粒子當(dāng)前位置對(duì)應(yīng)的適應(yīng)度小于pbest的適應(yīng)度，則pbest更新為當(dāng)前位置。b)整個(gè)種群從起始到目前所找到的最優(yōu)解gbest。每個(gè)粒子按以下兩個(gè)公式進(jìn)行動(dòng)態(tài)進(jìn)化，調(diào)整粒子的位置:

vi，d(t+1)=wvi，d(t)+c?1r1，d(t)(pbest?i，d-xi，d(t))+?c?2r2，d(t)(gbest?d(t)-xi，d(t))(3)

x?i(t+1)=x?i(t)+v?i(t+1)(4)

其中:w是慣性權(quán)重，動(dòng)態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度;c?1和c?2為加速常數(shù)，通常在0～2取值，c?1調(diào)節(jié)粒子飛向自身最好位置方向的步長，c?2調(diào)節(jié)粒子飛向全局最好位置方向的步長;r1，d(t)，r2，d(t)～U(0，1)，且d=1，2，…，n。為了減少在進(jìn)化過程中粒子離開搜索空間的可能性，粒子的每一維速度被限定在[-Vmax，Vmax]內(nèi)。

2.2QPSO算法

`Sun等人從量子力學(xué)的角度，通過對(duì)粒子收斂行為的研究，基于粒子群算法提出了一種新的算法模型——量子粒子群(QPSO)算法。在該算法中，由于粒子滿足聚集態(tài)的性質(zhì)完全不同，使粒子在整個(gè)可行解空間中進(jìn)行搜索尋求全局最優(yōu)解，因而QPSO算法在搜索能力上遠(yuǎn)遠(yuǎn)優(yōu)于所有已開發(fā)的PSO算法。

QPSO算法參數(shù)個(gè)數(shù)少，進(jìn)化方程的形式更加簡單，更容易控制。在QPSO算法中，每一個(gè)粒子必須收斂于各自的隨機(jī)點(diǎn)P?i，粒子按照下面的三式移動(dòng):

mbest=1m?mi=1P?i=(1m?mi=1Pi1，…，1m?mi=1Pij)(5)

PPij=fPij+(1-f)Pgj，f=rand(6)

xij=PPij±a|mbest?j-xij|ln(1/u)，u=rand(7)

其中:mbest是粒子群pbest的中間位置;Pij為粒子本身所找到的最優(yōu)解pbest;Pgj為整個(gè)粒子群目前找到的最優(yōu)解gbest;PPij為Pij與Pgj之間的隨機(jī)點(diǎn);a為QPSO的收縮擴(kuò)張系數(shù)，它是QPSO收斂的一個(gè)重要參數(shù)，第t次迭代時(shí)一般可取

a=amax-t(amax-amin)/tmax(8)

其中:tmax是迭代的最大次數(shù)，amax與amin分別是最大和最小系數(shù)。QPSO的算法流程如下:

a)迭代次數(shù)t=0，對(duì)種群的每個(gè)粒子的位置向量進(jìn)行初始化。

b)根據(jù)目標(biāo)函數(shù)計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值。

c)更新每個(gè)粒子的新局部最優(yōu)位置P?i。

d)更新粒子群的全局最優(yōu)位置P?g。

e)根據(jù)式(5)計(jì)算mbest。

f)根據(jù)式(6)計(jì)算每個(gè)粒子隨機(jī)點(diǎn)PP?i。

g)根據(jù)式(7)(以一定的概率取加或減)更新每個(gè)粒子的新位置。

h)令t=t+1，返回到b)，重新計(jì)算，直到終止條件滿足。a)將每個(gè)向量切斷分成若干個(gè)子串，各段子串的長度可以相等，也可以不相等，子串形如(q?1，q?2，…，q?k)。

b)從整數(shù)組成的子串到實(shí)數(shù)作一個(gè)映射，可表示為

r=c×?ki=1q?i×b??k-i(9)

其中:r為映射的實(shí)數(shù);c是常數(shù)，一般取足夠小的實(shí)數(shù)，本文取值為0.01;b為基數(shù)，對(duì)于Xpriority，b取值為5，對(duì)于Xmachine，b取值為n。

c)在計(jì)算任務(wù)執(zhí)行總時(shí)間前，需將r轉(zhuǎn)換為子串，即式(9)的逆映射:

q?i=(rc-?i-1j=1q?j×b??k-j)pb??k-i(10)

其中:p為整除，得到的商q?i為整數(shù)，在實(shí)際運(yùn)算時(shí)，可用一個(gè)循環(huán)，i從1~k得到子串中所有分量。

例如9個(gè)子任務(wù)的情況，Xpriority=(242143410)，分為三段，各子串長度均為3。

子串(242);(143);(410)

變換后得到

r0.720.481.05

經(jīng)過迭代后的情況:

逆變換后得到

r0.531.120.91

子串(203)(422)(331)

在初始化時(shí)，可省掉式(9)的轉(zhuǎn)換過程，直接給粒子位置賦實(shí)數(shù)。

解決了連續(xù)化問題之后，還有一個(gè)邊界問題，如上例r的取值為[0，1.24]，如迭代過程中z的運(yùn)算結(jié)果超出范圍時(shí)，將r值取在邊界上。若r<0，取值0;r>1.24，取值1.24。

通過上述映射和逆映射，整數(shù)規(guī)劃問題轉(zhuǎn)換為連續(xù)優(yōu)化問題，從而可以利用QPSO優(yōu)化獲得高質(zhì)量的解。

3.3算法流程

a)初始化粒子群，根據(jù)編碼方案設(shè)定各粒子的隨機(jī)位置。

b)根據(jù)式(10)將每個(gè)粒子的實(shí)數(shù)向量轉(zhuǎn)換為整數(shù)向量。

c)對(duì)每個(gè)粒子的整數(shù)向量解碼后，計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值。

d)更新每個(gè)粒子的局部最優(yōu)值P?i。

e)更新粒子群的全局最優(yōu)值P?g。

f)根據(jù)式(5)計(jì)算mbest。

g)根據(jù)式(6)計(jì)算每個(gè)粒子隨機(jī)點(diǎn)PP?i。

h)根據(jù)式(7)更新每個(gè)粒子的新位置。

i)返回b)步，直到滿足迭代的次數(shù)。

4仿真實(shí)驗(yàn)與結(jié)果分析

4.1實(shí)驗(yàn)參數(shù)選取

本文的仿真實(shí)驗(yàn)是在MATLAB軟件上實(shí)現(xiàn)的。實(shí)驗(yàn)所用DAG圖隨機(jī)生成，每個(gè)任務(wù)節(jié)點(diǎn)有1～4個(gè)前驅(qū)與后繼，估計(jì)運(yùn)行時(shí)間θij為1～50s的隨機(jī)數(shù)。實(shí)驗(yàn)計(jì)算了文獻(xiàn)[3，4]的算法、PSO與本文的QPSO共四種情況，算法中主要參數(shù):種群大小為80，終止代數(shù)為1500，amax取值1，amin取值0.5;PSO的慣性權(quán)重w與QPSO中的收縮擴(kuò)張系數(shù)a取值相同，c?1和c?2均為2，編碼、解碼、連續(xù)化與邊界問題均使用本文的方案;文獻(xiàn)[3]算法的雜交概率為1.0，變異概率為0.05;文獻(xiàn)[4]算法的內(nèi)部雜交概率為0.8，遷移概率為0.2，演化策略中的參數(shù)為μ/λ=5。

4.2計(jì)算結(jié)果與分析

對(duì)于隨機(jī)生成的同一個(gè)DAG圖，分別用上述四種算法進(jìn)行計(jì)算，記錄各算法收斂時(shí)得到的最優(yōu)解的完成時(shí)間和收斂時(shí)的進(jìn)化代數(shù)。計(jì)算結(jié)果如表1所示。為了消除數(shù)據(jù)隨機(jī)性的影響，更好地反映算法的性能，表1中的進(jìn)化代數(shù)是100次進(jìn)化的平均收斂代數(shù)，完成時(shí)間是所有100次進(jìn)化中得到的最優(yōu)解的平均完成時(shí)間。圖3為四個(gè)處理機(jī)100個(gè)子任務(wù)情況下四種算法分別進(jìn)化的靜態(tài)性能曲線，列出了各算法在不同進(jìn)化代數(shù)時(shí)所找到的最優(yōu)解。表2為四種算法在進(jìn)化中能收斂到其最優(yōu)解的次數(shù)占實(shí)驗(yàn)總次數(shù)的百分比。

表1仿真實(shí)驗(yàn)結(jié)果

處理機(jī)?個(gè)數(shù)子任務(wù)?個(gè)數(shù)

完成時(shí)間/s

文獻(xiàn)[3]?算法文獻(xiàn)[4]?算法PSO?算法本文?算法

收斂時(shí)的進(jìn)化代數(shù)

2528527127926539312529

250565543551538166131108125

1001548142914271416418339285323

2519318618817953463338

450457429428417194168135157

1001198113611391073516468323339

2515214113813473544952

850341297292281336217163212

1001106911923875727621538601

表2收斂到其已知最優(yōu)解的次數(shù)占進(jìn)化總次數(shù)的百分比%

各算法子任務(wù)個(gè)數(shù)25子任務(wù)個(gè)數(shù)50子任務(wù)個(gè)數(shù)100

文獻(xiàn)[3]算法876448

文獻(xiàn)