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

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

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

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

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