基于元啟發(fā)式算法的異構(gòu)計算系統(tǒng)靜態(tài)任務調(diào)度的研究.pdf

1、異構(gòu)計算系統(tǒng)將不同體系結(jié)構(gòu)的處理單元組合起來，各個處理器選擇適合自己的子任務進行處理，可以使系統(tǒng)的整體運算性能得到大幅提升。任務的分配調(diào)度需要依靠調(diào)度算法來支撐，高效的任務調(diào)度算法是提升異構(gòu)系統(tǒng)整體性能的關(guān)鍵所在。異構(gòu)多處理器環(huán)境下的任務調(diào)度問題被證明是 NP完全問題，無法在多項式時間內(nèi)得到最優(yōu)解，針對該問題進行的廣泛深入的研究，旨在提出更加高效的任務調(diào)度算法來升系統(tǒng)性能。啟發(fā)式算法或元啟發(fā)式算法被認為是解決該問題的有效方法。
　

2、　本文針對現(xiàn)有元啟發(fā)式算法容易陷入局部最優(yōu)，并且未充分利用處理器空閑時間等問題，在化學反應優(yōu)化算法和遺傳算法的基礎(chǔ)上，將局部搜索和全局搜索相結(jié)合，并使用區(qū)間插入技術(shù)和任務復制技術(shù)，對異構(gòu)計算環(huán)境下的任務調(diào)度問題進行研究，從而達到縮短調(diào)度長度的目的。論文具體工作如下：
　　針對現(xiàn)有元啟發(fā)式算法缺乏全局搜索能力的問題，本文在化學反應優(yōu)化算法的基礎(chǔ)上，對算法中的基本反應進行設(shè)計，提出了一種基于化學反應優(yōu)化的元啟發(fā)式任務調(diào)度算法。該算法首

3、先反復利用拓撲排序?qū)θ蝿照{(diào)度順序進行排序，得到若干隨機地滿足拓撲結(jié)構(gòu)的初始任務序列，然后利用化學反應優(yōu)化算法的四種基本反應對初始任務序列進行重新地排列組合，目的是找出解空間內(nèi)的最優(yōu)解。任務到處理器的映射策略使用最早結(jié)束時間EFT，每個任務依次被分配到EFT最小的處理器上執(zhí)行。為了驗證算法的可行性和高效性，本文設(shè)計了一個用于驗證和測試算法性能的仿真系統(tǒng)。實驗結(jié)果表明，本文提出的算法與LSA算法和CPOP算法相比，具有更短的調(diào)度長度。

4、>　　針對現(xiàn)有調(diào)度算法在調(diào)度 CCR較大的任務圖時處理器利用率較低的問題，本文將區(qū)間插入技術(shù)和任務復制技術(shù)運用于遺傳算法中，設(shè)計了一種基于遺傳和任務復制的啟發(fā)式任務調(diào)度算法。該算法首先記錄所有任務的關(guān)鍵直接前驅(qū)任務，然后在遺傳算法的每一輪迭代中，試探性地將當前任務的關(guān)鍵直接前驅(qū)任務冗余地復制到當前任務所對應的處理器上，如果能夠使當前任務的AFT提前，那么確認該次復制有效，否則丟棄該冗余的前驅(qū)任務。通過這樣的復制策略，能夠有效地減少由于前