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

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

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

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

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