快速了解中文期刊目錄級別、選刊、行業(yè)刊物等解決方案
摘 要:任務(wù)調(diào)度是網(wǎng)絡(luò)并行計算系統(tǒng)的核心問題之一。在有向無環(huán)圖(DAG)描述問題的基礎(chǔ)上,提出了一種進行并行任務(wù)調(diào)度的量子粒子群優(yōu)化算法。首先對DAG并行任務(wù)調(diào)度問題作出定義,并給出了優(yōu)化問題的目標(biāo);然后分別探討了問題的編碼表示、解碼方案、位置向量的計算方法、離散問題連續(xù)化、算法的總體流程等;最后給出算法的仿真實驗情況與研究,實驗結(jié)果表明,該算法有良好的全局尋優(yōu)性能和快捷的收斂速度,調(diào)度效果優(yōu)于遺傳算法和粒子群優(yōu)化算法。
關(guān)鍵詞:任務(wù)調(diào)度,量子粒子群優(yōu)化,有向無環(huán)圖,核心期刊發(fā)表
Research on DAG parallel task scheduling problem based on ?quantum-behaved particle swarm optimization
ZHANG Cong,SHEN Hui-zhang
(Antai College of Economics & Management, Shanghai Jiaotong University, Shanghai 200052, China)
Abstract:Task scheduling is one of the important problems in parallel computing system.This paper proposed a quantum-?behaved particle swarm optimization algorithm for task scheduling based on directed acyclic graph.First redefined the parallel task scheduling problem and its aim.Then discussed the representation of the encoding, the procedure of the decoding, the computational method of position vector, the continuative of the discrete problem and the structure of the algorithm respectively.In the end,presented the algorithm simulation,experiment result analysis and the conclusions.The simulation results show that this algorithm has better global optimizing ability and more rapid convergence, and it is superior to genetic algorithm and particle swarm optimization algorithm.
Key words:task scheduling; quantum-behaved particle swarm optimization(QPSO); directed acyclic graph(DAG)
網(wǎng)絡(luò)并行計算環(huán)境下的任務(wù)調(diào)度問題是指在一定約束條件下,如何將一組任務(wù)分配到多臺處理機上執(zhí)行的組合優(yōu)化問題,其已被證明是NP完全問題,不可能在多項式時間內(nèi)找到問題的最優(yōu)解[1,2]。目前常見的并行任務(wù)調(diào)度問題按照任務(wù)之間有無數(shù)據(jù)依賴關(guān)系可以劃分為獨立任務(wù)調(diào)度和依賴關(guān)系任務(wù)調(diào)度。前者在調(diào)度任務(wù)時不需要考慮任務(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)化過程比獨立任務(wù)調(diào)度的要復(fù)雜許多,且其適用范圍也更廣。以DAG表示的并行任務(wù)模型的研究得到了廣泛關(guān)注和迅速發(fā)展。近年出現(xiàn)的一些啟發(fā)式算法(如模擬退火算法、遺傳算法等)為求解此類NP完全問題提供了新的途徑[3~5],但是這些算法有些復(fù)雜性太高難以實現(xiàn),有些實現(xiàn)起來太費時,所以有必要尋求更好的算法來解決此問題。
粒子群優(yōu)化(PSO)算法是由Kennedy等人提出的一種源于對鳥群捕食行為模擬的進化計算技術(shù),已成為進化計算的一個最吸引人的分支。與遺傳算法類似,PSO是一種基于迭代的優(yōu)化方法,系統(tǒng)初始化為一組隨機解,通過迭代搜尋最優(yōu)值,但是在許多實際應(yīng)用領(lǐng)域,更勝于遺傳算法,尤其是在非線性優(yōu)化問題上。量子粒子群優(yōu)化(QPSO)算法是在傳統(tǒng)的PSO基礎(chǔ)上提出的一種新型的具有高效率全局搜索能力的進化算法[7,8]。它主要是引入量子物理的思想改進了PSO的進化方法,即更新粒子位置的方法;在更新粒子位置時重點考慮各個粒子的當(dāng)前局部最優(yōu)位置信息和全局最優(yōu)位置信息。QPSO具有調(diào)整參數(shù)少、容易實現(xiàn)、收斂能力強等優(yōu)勢。為適應(yīng)任務(wù)分配問題的求解,本文設(shè)計出合適的粒子編碼,利用改進的量子粒子群算法求解任務(wù)分配問題,并與其他算法相比較。實驗結(jié)果表明,本文提出的算法可以獲得質(zhì)量更高的解職稱論文。
1 問題描述
本模型的計算系統(tǒng)由一系列異構(gòu)的處理機組成,需要處理的總?cè)蝿?wù)已分解成一系列子任務(wù)。模型的約束條件為:任務(wù)執(zhí)行具有非搶占性,即處理機只有在執(zhí)行完某個任務(wù)之后才能處理另外一個任務(wù);另外這些任務(wù)之間具有前驅(qū)后繼的數(shù)據(jù)依賴關(guān)系,某個子任務(wù)只有在其所有的前驅(qū)任務(wù)處理完畢后才能開始執(zhí)行。該模型的調(diào)度目標(biāo)就是要使得整個DAG圖的調(diào)度長度最短。
為了便于分析問題,可以用下列五元組表述:
Π=(P,G,Θ,Ψ,Ω)
其中:
P={P?1,P?2,…,P?n}為n個處理機的集合。
G是子任務(wù)集T的依賴關(guān)系圖,它通過DAG來表示各個子任務(wù)間的調(diào)度約束關(guān)系。G=(T,E),其中T={T?1,T?2,…,T?m}為m個子任務(wù)的集合,一個子任務(wù)T?i就是圖G中的一個節(jié)點,E是任務(wù)依賴關(guān)系圖中的有向邊集!碩?i,T?j〉∈E(i,j=1,2,…,m),則表示在子任務(wù)T?i沒有完成之前,任務(wù)T?j不能執(zhí)行。這時稱T?i為T?j的一個前驅(qū),T?j為T?i的一個后繼,E可用鄰接矩陣存儲。
Θ是一個m×n矩陣,其元素θij表示任務(wù)T?i在處理機P?j上的執(zhí)行時間,假設(shè)每個任務(wù)的執(zhí)行時間預(yù)知(i=1,2,…,m;?j=1,2,…,n)。
Ψ是一個m×m矩陣,其元素ψij表示任務(wù)T?i與T?j之間的數(shù)據(jù)傳輸延時(i,j=1,2,…,m),同時假設(shè)各處理機間的通信能力是相同的,且忽略網(wǎng)絡(luò)擁塞,即傳輸?shù)臄?shù)據(jù)量是惟一影響ψij大小的因素。
Ω是一個m×n的任務(wù)分配矩陣,其中ωij=1表示T?i分配到處理機P?j上執(zhí)行;否則ωij=0(i=1,2,…,m;j=1,2,…,n)。
要實現(xiàn)的目標(biāo)是尋找一個分配調(diào)度策略,將m個子任務(wù)分配到n個處理機上,合理調(diào)度各個子任務(wù)的執(zhí)行次序,使得各子任務(wù)在滿足依賴關(guān)系圖G的約束下,整個任務(wù)的完成時間最短,F(xiàn)假設(shè)某一合法的分配調(diào)度S,將T中的m個子任務(wù)分配到n個處理機上,其中子任務(wù)T?i被分配到處理機P?j上執(zhí)行,那么子任務(wù)T?i在處理機P?j上的執(zhí)行時間滿足以下兩式:
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在處理機P?j上的開始執(zhí)行時刻和結(jié)束執(zhí)行時刻;Pred(T?i)表示子任務(wù)T?i的前驅(qū)節(jié)點集合,假設(shè)子任務(wù)T?k∈Pred(T?i)被分配到處理機?P?r上。
根據(jù)式(1)(2)迭代計算,可得到所有子任務(wù)的結(jié)束執(zhí)行時刻。設(shè)Γ(S)為在調(diào)度策略S下完成任務(wù)所使用的總時間,那么:Γ(S)=max(Ft(T?i,P?j));?i=1,2,…,m;j=1,2,…,n。
任務(wù)調(diào)度目標(biāo)就是min(Γ(S))?S,即尋找一個分配調(diào)度S,使得Γ(S)最小。
鑒于本文主要考慮任務(wù)調(diào)度問題,在不失問題一般性的情況下,可忽略數(shù)據(jù)傳輸延時,即在下文中可假設(shè)所有的ψij=0。
2 算法
2.1 PSO算法
粒子群優(yōu)化(PSO)算法是一種進化計算方法,是一種基于迭代的優(yōu)化工具。該算法通過群體中各粒子間的合作與競爭來搜索全局最優(yōu)點。
系統(tǒng)初始化為一組共n個隨機解,通過迭代搜尋整個群體的最優(yōu)值。粒子i的當(dāng)前位置為x?i=(xi1,xi2,…,xid),其飛行速度記為v?i=(vi1,vi2,…,vid),在解空間中追隨適應(yīng)度最優(yōu)的粒子進行搜索。在每一次迭代中, 粒子通過跟蹤兩個“極值”來更新自己:a)每個粒子本身所找到的最優(yōu)解pbest。如果粒子當(dāng)前位置對應(yīng)的適應(yīng)度小于pbest的適應(yīng)度,則pbest更新為當(dāng)前位置。b)整個種群從起始到目前所找到的最優(yōu)解gbest。每個粒子按以下兩個公式進行動態(tài)進化,調(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)重,動態(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。為了減少在進化過程中粒子離開搜索空間的可能性,粒子的每一維速度被限定在[-Vmax,Vmax]內(nèi)。
2.2 QPSO算法
`Sun等人從量子力學(xué)的角度,通過對粒子收斂行為的研究,基于粒子群算法提出了一種新的算法模型——量子粒子群(QPSO)算法。在該算法中,由于粒子滿足聚集態(tài)的性質(zhì)完全不同,使粒子在整個可行解空間中進行搜索尋求全局最優(yōu)解,因而QPSO算法在搜索能力上遠(yuǎn)遠(yuǎn)優(yōu)于所有已開發(fā)的PSO算法。
QPSO算法參數(shù)個數(shù)少,進化方程的形式更加簡單,更容易控制。在QPSO算法中,每一個粒子必須收斂于各自的隨機點P?i,粒子按照下面的三式移動:
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為整個粒子群目前找到的最優(yōu)解gbest; PPij為Pij與Pgj之間的隨機點;a為QPSO的收縮擴張系數(shù),它是QPSO收斂的一個重要參數(shù),第t次迭代時一般可取
a=amax-t(amax-amin)/tmax(8)
其中:tmax是迭代的最大次數(shù),amax與amin分別是最大和最小系數(shù)。QPSO的算法流程如下:
a)迭代次數(shù)t=0,對種群的每個粒子的位置向量進行初始化。
b)根據(jù)目標(biāo)函數(shù)計算每個粒子的目標(biāo)函數(shù)值。
c)更新每個粒子的新局部最優(yōu)位置P?i。
d)更新粒子群的全局最優(yōu)位置P?g。
e)根據(jù)式(5)計算mbest。
f)根據(jù)式(6)計算每個粒子隨機點PP?i。
g)根據(jù)式(7)(以一定的概率取加或減)更新每個粒子的新位置。
h)令t=t+1,返回到b),重新計算,直到終止條件滿足。
3 基于QPSO的DAG并行任務(wù)調(diào)度
3.1 編碼與解碼
任務(wù)調(diào)度的常見編碼包括基于任務(wù)的編碼、基于操作的編碼和基于優(yōu)先規(guī)則的編碼等。由于DAG并行任務(wù)調(diào)度的復(fù)雜性,采用任一種上述編碼形式均無法保證所有解的合法性,這將浪費大量的求解時間。本文設(shè)計了一種復(fù)合的編碼方案:編碼長度為2 m,可描述為兩個向量,第一個向量采用基于優(yōu)先規(guī)則的編碼方式,為一個包含m維的向量(R?1,R?2,…,R?m)。其中R?i表示在算法迭代過程中第i次迭代時發(fā)生的沖突利用優(yōu)先規(guī)則R?i消除。本文選擇了五種優(yōu)先規(guī)則,包括最短執(zhí)行時間(SPT)、最長執(zhí)行時間(LPT)、最早開工時間(EST)、最早完工時間(EFT)、最晚完工時間(LFT),數(shù)字0、1、2、3、4分別對應(yīng)優(yōu)先規(guī)則SPT、LPT、EST、EFT、LFT。第二個向量是處理機分配向量,即一個包含m維的向量(M?1,M?2,…,M?m)。其中M?i表示編號為i的子任務(wù)被分配到編號為(M?i)的處理機上執(zhí)行(所有處理機編號為0,1,…,n-1)。
在解碼過程中,設(shè)t為調(diào)度的時間步,PS為調(diào)度列表。其中PS?t為第t步調(diào)度執(zhí)行的子任務(wù);TS為所有前驅(qū)已經(jīng)被調(diào)度的子任務(wù)所構(gòu)成的集合。解碼算法如下:
a)令t=1,PS為空,TS由所有無前驅(qū)的子任務(wù)構(gòu)成。
b)由TS中所有子任務(wù)編碼,在處理機分配向量(M?1,?M?2,…,M?m)中找到分配給每個子任務(wù)的處理機,并在Θ中找到具體執(zhí)行時間。
c)依據(jù)約束條件和執(zhí)行時間,得到TS中每個子任務(wù)對應(yīng)的指標(biāo)時間(開工、完工或執(zhí)行時間),由編碼R?t所對應(yīng)的優(yōu)先規(guī)則選出一個子任務(wù)(如優(yōu)先規(guī)則為最短執(zhí)行時間,則選TS中執(zhí)行時間最短的子任務(wù),如果有多個子任務(wù)符合優(yōu)先規(guī)則,則任選一個),該子任務(wù)就是PS?t,從TS中刪除它,并將其加入PS的尾部。
d)逐個考察PS?t的后繼子任務(wù),如果該子任務(wù)無其他前驅(qū),或其他前驅(qū)都已被調(diào)度執(zhí)行,則將其加入TS中。
e)令t=t+1,若t 通過下面示例說明解碼過程:
任務(wù)的DAG如圖1所示。
優(yōu)先規(guī)則向量:
(032140)
即:(SPT EFT EST LPT LFT SPT)
處理機分配向量:
(0 1 1 0 1 0)
即(P1 P2 P2 P1 P2 P1)
在Θ中查到的處理時間:
(2 4 6 5 3 7)
處理時間指1~6號子任務(wù)在對應(yīng)處理機上的執(zhí)行時間。
根據(jù)示例數(shù)據(jù)得到的調(diào)度列表PS為(T?1 T?2 T?4 T?6 T?3 T?5),甘特圖如圖2所示。
由上述編碼方式和解碼過程可知,本文編碼能保證調(diào)度的可行性,且碼長較短,無冗余,解碼復(fù)雜性不高。
3.2 QPSO中向量的計算方法
對每個粒子,它的優(yōu)先規(guī)則向量和處理機分配向量可以表示為Xpriority(1..m)和Xmachine(1..m),按式(5)~(7)計算這兩個向量。由于前面所述的QPSO為連續(xù)空間算法,而DAG并行任務(wù)調(diào)度問題為整數(shù)規(guī)劃問題,將離散優(yōu)化轉(zhuǎn)變成對實數(shù)向量的連續(xù)優(yōu)化,具體過程如下:
a)將每個向量切斷分成若干個子串,各段子串的長度可以相等,也可以不相等,子串形如(q?1,q?2,…,q?k)。
b)從整數(shù)組成的子串到實數(shù)作一個映射,可表示為
r=c×?ki=1q?i×bk-i(9)
其中:r為映射的實數(shù);c是常數(shù),一般取足夠小的實數(shù),本文取值為0.01;b為基數(shù),對于Xpriority,b取值為5,對于Xmachine,b取值為n。
c)在計算任務(wù)執(zhí)行總時間前,需將r轉(zhuǎn)換為子串,即式(9)的逆映射:
q?i=(rc-?i-1j=1q?j×bk-j)div bk-i(10)
其中:div為整除,得到的商q?i為整數(shù),在實際運算時,可用一個循環(huán),i從1~k得到子串中所有分量。
例如9個子任務(wù)的情況,Xpriority=(2 4 2 1 4 3 4 1 0),分為三段,各子串長度均為3。
子串 (242); (143); (410)
變換后得到
r0.720.481.05
經(jīng)過迭代后的情況:
逆變換后得到
r0.531.120.91
子串(203)(422)(331)
在初始化時,可省掉式(9)的轉(zhuǎn)換過程,直接給粒子位置賦實數(shù)。
解決了連續(xù)化問題之后,還有一個邊界問題,如上例r的取值為[0,1.24],如迭代過程中z的運算結(jié)果超出范圍時,將r值取在邊界上。若r0,取值0;r1.24,取值1.24。
通過上述映射和逆映射,整數(shù)規(guī)劃問題轉(zhuǎn)換為連續(xù)優(yōu)化問題,從而可以利用QPSO優(yōu)化獲得高質(zhì)量的解。
3.3 算法流程
a)初始化粒子群,根據(jù)編碼方案設(shè)定各粒子的隨機位置。
b)根據(jù)式(10)將每個粒子的實數(shù)向量轉(zhuǎn)換為整數(shù)向量。
c)對每個粒子的整數(shù)向量解碼后,計算每個粒子的目標(biāo)函數(shù)值。
d)更新每個粒子的局部最優(yōu)值P?i。
e)更新粒子群的全局最優(yōu)值P?g。
f)根據(jù)式(5)計算mbest。
g)根據(jù)式(6)計算每個粒子隨機點PP?i。
h)根據(jù)式(7)更新每個粒子的新位置。
i)返回b)步,直到滿足迭代的次數(shù)。
4 仿真實驗與結(jié)果分析
4.1 實驗參數(shù)選取
本文的仿真實驗是在MATLAB軟件上實現(xiàn)的。實驗所用DAG圖隨機生成,每個任務(wù)節(jié)點有1~4個前驅(qū)與后繼,估計運行時間θij為1~50 s的隨機數(shù)。實驗計算了文獻(xiàn)[3,4]的算法、PSO與本文的QPSO共四種情況,算法中主要參數(shù):種群大小為80,終止代數(shù)為1 500,amax取值1,amin取值0.5;PSO的慣性權(quán)重w與QPSO中的收縮擴張系數(shù)a取值相同,c?1和c?2均為2,編碼、解碼、連續(xù)化與邊界問題均使用本文的方案;文獻(xiàn)算法的雜交概率為1.0,變異概率為0.05;文獻(xiàn)算法的內(nèi)部雜交概率為0.8,遷移概率為0.2,演化策略中的參數(shù)為μ/λ=5。
4.2 計算結(jié)果與分析
對于隨機生成的同一個DAG圖,分別用上述四種算法進行計算,記錄各算法收斂時得到的最優(yōu)解的完成時間和收斂時的進化代數(shù)。計算結(jié)果如表1所示。為了消除數(shù)據(jù)隨機性的影響,更好地反映算法的性能,表1中的進化代數(shù)是100次進化的平均收斂代數(shù),完成時間是所有100次進化中得到的最優(yōu)解的平均完成時間。圖3為四個處理機100個子任務(wù)情況下四種算法分別進化的靜態(tài)性能曲線,列出了各算法在不同進化代數(shù)時所找到的最優(yōu)解。表2為四種算法在進化中能收斂到其最優(yōu)解的次數(shù)占實驗總次數(shù)的百分比。
表1 仿真實驗結(jié)果
處理機?個數(shù)子任務(wù)?個數(shù)
完成時間/s
文獻(xiàn)?算法文獻(xiàn)?算法PSO?算法本文?算法
收斂時的進化代數(shù)
2528527127926539312529
250565543551538166131108125
1001 5481 4291 4271 416418339285323
2519318618817953463338
450457429428417194168135157
1001 1981 1361 1391 073516468323339
2515214113813473544952
850341297292281336217163212
1001 106911923875727621538601
表2 收斂到其已知最優(yōu)解的次數(shù)占進化總次數(shù)的百分比%
各算法子任務(wù)個數(shù)25子任務(wù)個數(shù)50子任務(wù)個數(shù)100
文獻(xiàn)算法876448
文獻(xiàn)算法969281
PSO算法928967
本文算法1009996
由表1、2和算法的靜態(tài)性能曲線可以得出:
a)在任務(wù)數(shù)較多、處理機較多的情況下,PSO與本文QPSO算法的收斂速度比文獻(xiàn)算法快很多,但與文獻(xiàn)算法比較時,PSO算法的收斂速度明顯比文獻(xiàn)算法快,本文QPSO算法則與文獻(xiàn)算法相當(dāng);而在任務(wù)數(shù)少的情況下,除文獻(xiàn)算法稍慢,其他算法相差不大。
b)本文QPSO算法能找到的最優(yōu)解比文獻(xiàn)[3,4]算法有明顯的提高,尤其是子任務(wù)數(shù)較多、處理機數(shù)較多時。
c)PSO與本文QPSO算法比較時,發(fā)現(xiàn)QPSO算法的收斂速度比PSO算法慢,但得到的最優(yōu)解比PSO算法好。
這是因為:首先,本文對問題的編碼能夠覆蓋整個解空間,相對來說文獻(xiàn)[3,4]的算法只能從一個相對較小的空間內(nèi)搜索;其次,本文采用了離散空間到連續(xù)空間的轉(zhuǎn)換過程,它不僅滿足了QPSO算法對待解問題的取值要求,還在一定程度上能更好地保護與遺傳優(yōu)良的解片段。另外,PSO算法收斂過快,而QPSO的量子搜索方式對傳統(tǒng)的PSO算法有了很大的改進,實驗證明可防止早熟。
5 結(jié)束語
基于DAG的并行任務(wù)調(diào)度問題是NP難問題,傳統(tǒng)的優(yōu)化算法很難求得全局最優(yōu)解,雖然已有人將遺傳算法應(yīng)用于此問題,但結(jié)果有待進一步改善。本文給出了新的問題定義,對QPSO算法作出調(diào)整與改進,編碼表示采用了適合于任務(wù)調(diào)度問題的優(yōu)先規(guī)則與處理機分配相結(jié)合的形式,并將離散空間優(yōu)化問題轉(zhuǎn)換為連續(xù)空間優(yōu)化問題,使得QPSO有較好的搜索能力。最后通過仿真實驗得到的一系列數(shù)據(jù),表明了本文的改進QPSO算法比遺傳算法和PSO算法有更好的性能,并有理由認(rèn)為,合理的編碼表示與高效的搜索策略相結(jié)合是任務(wù)分配調(diào)度問題全局尋優(yōu)的有效途徑。
上周TOP10
專家解答,全程指導(dǎo)
免費咨詢 >客戶咨詢服務(wù)
論文范文
成功指導(dǎo)
擁有280+公司員工
客戶口碑