資源描述：
《基于量子粒子群優(yōu)化的dag并行任務(wù)調(diào)度探討論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、基于量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度探討論文.freelbasedon?quantum-behavedparticlesoptimizationZHANGCong,SHENHui-zhang(AntaiCollegeofEconomicsManagement,ShanghaiJiaotongUniversity,Shanghai200052,China)Abstract:Taskschedulingisoneoftheimportantproblemsinparallelputingsystem.Th
2、ispaperproposedaquantum-?behavedparticlesoptimizationalgorithmfortaskschedulingbasedondirectedacyclicgraph.Firstredefinedtheparalleltaskschedulingproblemanditsaim.Thendiscussedtherepresentationoftheencoding,theprocedureofthedecoding,theputationalmethodof
3、positionvector,thecontinuativeofthediscreteproblemandthestructureofthealgorithmrespectively.Intheend,.freelsimulation,experimentresultanalysisandtheconclusions.Thesimulationresultsshohasbetterglobaloptimizingabilityandmorerapidconvergence,anditissuperior
4、togeicalgorithmandparticlesoptimizationalgorithm.Key-behavedparticlesoptimization(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)度
5、任務(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)算法是由Kenned
6、y等人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)位置信息。QP
7、SO具有調(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í)行。該模
8、型的調(diào)度目標(biāo)就是要使得整個(gè)DAG圖的調(diào)度長(zhǎng)度最短。為了便于分析問題,可以用下列五元組表述:Π=(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),
