UNC模型上模擬退火遺傳調(diào)度算法研究及并行化.pdf

1、多處理機(jī)調(diào)度問題是并行處理中的一個著名問題.調(diào)度的主要目的是優(yōu)化并行程序在系統(tǒng)中運(yùn)行的一些指標(biāo),本文中調(diào)度的主要目標(biāo)是縮短調(diào)度后并行程序的執(zhí)行時間和提高多處理機(jī)系統(tǒng)的利用效率.在一般情況下調(diào)度問題的復(fù)雜性是NP-complete的.對于規(guī)模比較大的調(diào)度問題,由于任務(wù)圖的規(guī)模太大,一般調(diào)度算法將會由于內(nèi)存的限制而不能勝任.一種途徑是采用動態(tài)調(diào)度算法,但是由于動態(tài)調(diào)度算法是在程序運(yùn)行時進(jìn)行的,并且程序中的一些參數(shù)可以是預(yù)先未知,直到運(yùn)行時才

2、確定的,而且動態(tài)調(diào)度一般要對并行程序加一些前提上的約束,故算法設(shè)計比較復(fù)雜、困難;另一種途徑是將比較好的調(diào)度算法并行化.本文首先介紹了一些背景知識,然后介紹了目前常用的各種調(diào)度模型和一些代表性的調(diào)度算法.再詳細(xì)介紹兩種典型調(diào)度模型BNP和UNC,闡明了設(shè)計UNC模型上的調(diào)度算法的理由.在結(jié)合已有的模擬退火算法和遺傳算法的基礎(chǔ)上,我們改進(jìn)了現(xiàn)有的遺傳調(diào)度算法,自適應(yīng)地保存最優(yōu)個體,并對其進(jìn)行模擬退火,提出了在UNC模型上的自適應(yīng)最優(yōu)保存的

3、模擬退火遺傳調(diào)度算法SAMOAGSA.最后將該算法并行化,并在自強(qiáng)2000上高性能計算機(jī)上實現(xiàn).本文采用香港科技大學(xué)Yu-Kwong Kwok提供的Benchmarks圖集對本文算法和其它算法進(jìn)行了比較分析.算法的比較結(jié)果顯示算法對規(guī)模適中的任務(wù)圖有較好的搜索效果,并且對于不同粒度的任務(wù)圖而言,粗粒度的任務(wù)圖的調(diào)度效果優(yōu)于細(xì)粒度的任務(wù)圖.該論文的主要貢獻(xiàn):1)將遺傳算法與模擬退火相結(jié)合的混合遺傳算法應(yīng)用于調(diào)度問題;2)將其與其它調(diào)度算法