異構(gòu)分布式系統(tǒng)中的負(fù)載均衡調(diào)度算法研究.pdf

1、隨著社會(huì)的發(fā)展，經(jīng)濟(jì)的突飛猛進(jìn)，為了促進(jìn)社會(huì)和諧，地震災(zāi)變的預(yù)測(cè)也就越來越重要了?，F(xiàn)代計(jì)算機(jī)技術(shù)的迅猛發(fā)展，包括地震災(zāi)變預(yù)測(cè)等越來越多的工程計(jì)算問題都依靠于大型高性能超級(jí)計(jì)算機(jī)來解決。而工程計(jì)算從一定程度上又驅(qū)動(dòng)了高性能計(jì)算機(jī)的發(fā)展。目前，并行系統(tǒng)，網(wǎng)格計(jì)算等分布式技術(shù)已經(jīng)成為解決工程問題的重要方法，而在分布式系統(tǒng)中，為了提高分布式系統(tǒng)的性能，調(diào)度問題成為了現(xiàn)代分布式系統(tǒng)中的一個(gè)熱點(diǎn)問題。各種調(diào)度算法被大批的研究人員所提出，它們的調(diào)度優(yōu)

2、化目標(biāo)不盡相同，但是總的來說都是為了改進(jìn)分布式系統(tǒng)的性能。為此本文以任務(wù)調(diào)度的負(fù)載均衡為目標(biāo)，對(duì)任務(wù)調(diào)度問題進(jìn)行了深入的研究。
　　 首先，針對(duì)現(xiàn)在異構(gòu)分布式系統(tǒng)的負(fù)載均衡問題，本文設(shè)計(jì)了一個(gè)改進(jìn)的動(dòng)態(tài)遺傳算法IDGA(Improved Dynamic Genetic Algorithm)應(yīng)用于異構(gòu)分布式系統(tǒng)的調(diào)度器中，以此來優(yōu)化異構(gòu)分布式系統(tǒng)的負(fù)載均衡性能。考慮到傳統(tǒng)的遺傳算法在任務(wù)調(diào)度的應(yīng)用中存在著最大進(jìn)化代數(shù)有限的缺點(diǎn)，本

3、文涉及了IDGA算法，克服了最大進(jìn)化代數(shù)受限的缺點(diǎn)，并且在找到符合負(fù)載均衡標(biāo)準(zhǔn)的解以后，IDGA算法會(huì)按照一定的策略重新設(shè)置系統(tǒng)的負(fù)載均衡標(biāo)準(zhǔn)來試圖找到比當(dāng)前最優(yōu)調(diào)度更好的調(diào)度。
　　 其次，由于IDGA算法可以動(dòng)態(tài)設(shè)置最大進(jìn)化代數(shù)，那么有可能引起遺傳算法時(shí)間復(fù)雜度的增加，為了提高IDGA算法的效率，通過引入MapReduce分布式系統(tǒng)模型，將IDGA算法在MapReduce模型下并行化。
　　 最后，在IDGA算法的并

4、行化過程中，提出了一個(gè)用來表示遺傳算法初始種群的數(shù)據(jù)結(jié)構(gòu)--二叉選擇樹，在利用這個(gè)數(shù)據(jù)結(jié)構(gòu)對(duì)遺傳算法進(jìn)行選擇操作的時(shí)候，可以提高選擇操作的時(shí)間效率。該二叉選擇樹是一個(gè)平衡的二叉樹，所以搜索的平均復(fù)雜度是O(10g n)，其中n代表種群的規(guī)模。而傳統(tǒng)的遺傳算法中，只能通過線性時(shí)間復(fù)雜度O(n)才能成功選擇出一個(gè)個(gè)體。該二叉樹的每個(gè)節(jié)點(diǎn)上都記錄了該節(jié)點(diǎn)左子樹的所有節(jié)點(diǎn)的適應(yīng)度之和與右子樹的所有節(jié)點(diǎn)的適應(yīng)度之和。所以在決定選擇左子樹、右子樹還