淺論量子粒子群優化的DAG并行任務調度

淺論量子粒子群優化的DAG并行任務調度

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

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

　　1 問題描述

　　本模型的計算系統由一系列異構的處理機組成,需要處理的總任務已分解成一系列子任務。模型的約束條件為:任務執行具有非搶占性,即處理機只有在執行完某個任務之后才能處理另外一個任務;另外這些任務之間具有前驅后繼的數據依賴關系,某個子任務只有在其所有的前驅任務處理完畢后才能開始執行。該模型的調度目標就是要使得整個DAG圖的調度長度最短。

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

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

　　其中:

　　P={P?1,P?2,…,P?n}為n個處理機的集合。

　　G是子任務集T的依賴關系圖,它通過DAG來表示各個子任務間的調度約束關系。G=(T,E),其中T={T?1,T?2,…,T?m}為m個子任務的集合,一個子任務T?i就是圖G中的一個節點,E是任務依賴關系圖中的有向邊集。〈T?i,T?j〉∈E(i,j=1,2,…,m),則表示在子任務T?i沒有完成之前,任務T?j不能執行。這時稱T?i為T?j的一個前驅,T?j為T?i的一個后繼,E可用鄰接矩陣存儲。

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

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

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

　　要實現的目標是尋找一個分配調度策略,將m個子任務分配到n個處理機上,合理調度各個子任務的執行次序,使得各子任務在滿足依賴關系圖G的約束下,整個任務的完成時間最短。現假設某一合法的分配調度S,將T中的m個子任務分配到n個處理機上,其中子任務T?i被分配到處理機P?j上執行,那么子任務T?i在處理機P?j上的執行時間滿足以下兩式:

　　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)分別表示子任務T?i在處理機P?j上的開始執行時刻和結束執行時刻;Pred(T?i)表示子任務T?i的前驅節點集合,假設子任務T?k∈Pred(T?i)被分配到處理機?P?r上。

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

　　任務調度目標就是min(Γ(S))?S,即尋找一個分配調度S,使得Γ(S)最小。

　　鑒于本文主要考慮任務調度問題,在不失問題一般性的情況下,可忽略數據傳輸延時,即在下文中可假設所有的ψij=0。

　　2 算法

　　2.1 PSO算法

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

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

　　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是慣性權重,動態調整慣性權重以平衡收斂的全局性和收斂速度;c?1和c?2為加速常數,通常在0～2取值,c?1調節粒子飛向自身最好位置方向的步長,c?2調節粒子飛向全局最好位置方向的步長;r1,d(t),r2,d(t)～U(0,1),且d =1,2,…,n。為了減少在進化過程中粒子離開搜索空間的可能性,粒子的每一維速度被限定在[-Vmax,Vmax]內。

　　2.2 QPSO算法

　　`Sun等人從量子力學的角度,通過對粒子收斂行為的研究,基于粒子群算法提出了一種新的算法模型——量子粒子群(QPSO)算法。在該算法中,由于粒子滿足聚集態的性質完全不同,使粒子在整個可行解空間中進行搜索尋求全局最優解,因而QPSO算法在搜索能力上遠遠優于所有已開發的PSO算法。

　　QPSO算法參數個數少,進化方程的形式更加簡單,更容易控制。在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為粒子本身所找到的最優解pbest;Pgj為整個粒子群目前找到的最優解gbest; PPij為Pij與Pgj之間的隨機點;a為QPSO的收縮擴張系數,它是QPSO收斂的一個重要參數,第t次迭代時一般可取

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

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

　　a)迭代次數t=0,對種群的每個粒子的位置向量進行初始化。

　　b)根據目標函數計算每個粒子的目標函數值。

　　c)更新每個粒子的新局部最優位置P?i。

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

　　e)根據式(5)計算mbest。

　　f)根據式(6)計算每個粒子隨機點PP?i。

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

　　h)令t=t+1,返回到b),重新計算,直到終止條件滿足。

　　3 基于QPSO的DAG并行任務調度

　　3.1 編碼與解碼

　　任務調度的常見編碼包括基于任務的編碼、基于操作的編碼和基于優先規則的編碼等。由于DAG并行任務調度的復雜性,采用任一種上述編碼形式均無法保證所有解的合法性,這將浪費大量的求解時間。本文設計了一種復合的編碼方案:編碼長度為2 m,可描述為兩個向量,第一個向量采用基于優先規則的編碼方式,為一個包含m維的向量(R?1,R?2,…,R?m)。其中R?i表示在算法迭代過程中第i次迭代時發生的沖突利用優先規則R?i消除。本文選擇了五種優先規則,包括最短執行時間(SPT)、最長執行時間(LPT)、最早開工時間(EST)、最早完工時間(EFT)、最晚完工時間(LFT),數字0、1、2、3、4分別對應優先規則SPT、LPT、EST、EFT、LFT。第二個向量是處理機分配向量,即一個包含m維的向量(M?1,M?2,…,M?m)。其中M?i表示編號為i的子任務被分配到編號為(M?i)的處理機上執行(所有處理機編號為0,1,…,n-1)。

　　在解碼過程中,設t為調度的時間步,PS為調度列表。其中PS?t為第t步調度執行的子任務;TS為所有前驅已經被調度的子任務所構成的集合。解碼算法如下:

　　a)令t=1,PS為空,TS由所有無前驅的子任務構成。

　　b)由TS中所有子任務編碼,在處理機分配向量(M?1,?M?2,…,M?m)中找到分配給每個子任務的處理機,并在Θ中找到具體執行時間。

　　c)依據約束條件和執行時間,得到TS中每個子任務對應的指標時間(開工、完工或執行時間),由編碼R?t所對應的優先規則選出一個子任務(如優先規則為最短執行時間,則選TS中執行時間最短的子任務,如果有多個子任務符合優先規則,則任選一個),該子任務就是PS?t,從TS中刪除它,并將其加入PS的尾部。

　　d)逐個考察PS?t的后繼子任務,如果該子任務無其他前驅,或其他前驅都已被調度執行,則將其加入TS中。

　　e)令t=t+1,若t

　　通過下面示例說明解碼過程:

　　優先規則向量:

　　(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號子任務在對應處理機上的執行時間。

　　根據示例數據得到的調度列表PS為(T?1 T?2 T?4 T?6 T?3 T?5),甘特圖如圖2所示。

　　由上述編碼方式和解碼過程可知,本文編碼能保證調度的可行性,且碼長較短,無冗余,解碼復雜性不高。

　　3.2 QPSO中向量的計算方法

　　對每個粒子,它的優先規則向量和處理機分配向量可以表示為Xpriority(1..m)和Xmachine(1..m),按式(5)~(7)計算這兩個向量。由于前面所述的QPSO為連續空間算法,而DAG并行任務調度問題為整數規劃問題,將離散優化轉變成對實數向量的連續優化,具體過程如下:

　　a)將每個向量切斷分成若干個子串,各段子串的長度可以相等,也可以不相等,子串形如(q?1,q?2,…,q?k)。

　　b)從整數組成的子串到實數作一個映射,可表示為

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

　　其中:r為映射的實數;c是常數,一般取足夠小的實數,本文取值為0.01;b為基數,對于Xpriority,b取值為5,對于Xmachine,b取值為n。

　　c)在計算任務執行總時間前,需將r轉換為子串,即式(9)的逆映射:

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

　　其中:div為整除,得到的商q?i為整數,在實際運算時,可用一個循環,i從1~k得到子串中所有分量。

　　例如9個子任務的情況,Xpriority=(2 4 2 1 4 3 4 1 0),分為三段,各子串長度均為3。

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

　　變換后得到

　　r0.720.481.05

　　經過迭代后的情況:

　　逆變換后得到

　　r0.531.120.91

　　子串(203)(422)(331)

　　在初始化時,可省掉式(9)的轉換過程,直接給粒子位置賦實數。

　　解決了連續化問題之后,還有一個邊界問題,如上例r的取值為[0,1.24],如迭代過程中z的運算結果超出范圍時,將r值取在邊界上。若r<0,取值0;r>1.24,取值1.24。

　　通過上述映射和逆映射,整數規劃問題轉換為連續優化問題,從而可以利用QPSO優化獲得高質量的解。

　　3.3 算法流程

　　a)初始化粒子群,根據編碼方案設定各粒子的隨機位置。

　　b)根據式(10)將每個粒子的實數向量轉換為整數向量。

　　c)對每個粒子的整數向量解碼后,計算每個粒子的目標函數值。

　　d)更新每個粒子的局部最優值P?i。

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

　　f)根據式(5)計算mbest。

　　g)根據式(6)計算每個粒子隨機點PP?i。

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

　　i)返回b)步,直到滿足迭代的次數。

　　4 仿真實驗與結果分析

　　4.1 實驗參數選取

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

　　4.2 計算結果與分析

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

　　處理機?個數子任務?個數

　　完成時間/s

　　文獻[3]?算法文獻[4]?算法PSO?算法本文?算法

　　收斂時的進化代數

　　2528527127926539312529

　　250565543551538166131108125

　　1001 5481 4291 4271 416418339285323

　　2519318618817953463338

　　450457429428417194168135157

　　1001 1981 1361 1391 073516468323339

　　2515214113813473544952

　　850341297292281336217163212

　　1001 106911923875727621538601

　　各算法子任務個數25子任務個數50子任務個數100

　　文獻[3]算法876448

　　文獻[4]算法969281

　　PSO算法928967

　　本文算法1009996

　　a)在任務數較多、處理機較多的情況下,PSO與本文QPSO算法的收斂速度比文獻[3]算法快很多,但與文獻[4]算法比較時,PSO算法的收斂速度明顯比文獻[4]算法快,本文QPSO算法則與文獻[4]算法相當;而在任務數少的情況下,除文獻[3]算法稍慢,其他算法相差不大。

　　b)本文QPSO算法能找到的最優解比文獻[3,4]算法有明顯的提高,尤其是子任務數較多、處理機數較多時。

　　c)PSO與本文QPSO算法比較時,發現QPSO算法的收斂速度比PSO算法慢,但得到的最優解比PSO算法好。

　　這是因為:首先,本文對問題的編碼能夠覆蓋整個解空間,相對來說文獻[3,4]的算法只能從一個相對較小的空間內搜索;其次,本文采用了離散空間到連續空間的轉換過程,它不僅滿足了QPSO算法對待解問題的取值要求,還在一定程度上能更好地保護與遺傳優良的解片段。另外,PSO算法收斂過快,而QPSO的量子搜索方式對傳統的PSO算法有了很大的改進,實驗證明可防止早熟。

　　5 結束語

　　基于DAG的并行任務調度問題是NP難問題,傳統的優化算法很難求得全局最優解,雖然已有人將遺傳算法應用于此問題,但結果有待進一步改善。本文給出了新的問題定義,對QPSO算法作出調整與改進,編碼表示采用了適合于任務調度問題的優先規則與處理機分配相結合的形式,并將離散空間優化問題轉換為連續空間優化問題,使得QPSO有較好的搜索能力。最后通過仿真實驗得到的一系列數據,表明了本文的改進QPSO算法比遺傳算法和PSO算法有更好的性能,并有理由認為,合理的編碼表示與高效的搜索策略相結合是任務分配調度問題全局尋優的有效途徑。