網(wǎng)格環(huán)境下任務(wù)調(diào)度機制的研究與仿真.pdf

1、網(wǎng)格技術(shù)將所有可用于共享的資源(例如，計算機、高性能設(shè)備、昂貴儀器、存儲設(shè)備、科學(xué)數(shù)據(jù)、軟件、數(shù)據(jù)庫等)通過網(wǎng)絡(luò)連接起來，并將它們轉(zhuǎn)化成一種隨處可得的、可靠的、標準的、經(jīng)濟的計算能力。用戶將任務(wù)提交給網(wǎng)格后，需要對任務(wù)進行合理的分配和調(diào)度，即將任務(wù)分配給網(wǎng)格資源去執(zhí)行。 由于網(wǎng)格中任務(wù)調(diào)度直接影響到整個系統(tǒng)的計算性能，因此調(diào)度成為網(wǎng)格計算中的一項關(guān)鍵技術(shù)。任務(wù)調(diào)度問題是一類NPC問題，經(jīng)典調(diào)度理論一般僅能獲得問題的近似最優(yōu)解。

2、 本文采用理論分析與仿真實驗相結(jié)合的方法，研究網(wǎng)格計算中具有依賴關(guān)系的多任務(wù)分配與調(diào)度的遺傳算法。遺傳算法是一種有導(dǎo)向性的隨機搜索算法，它以適應(yīng)度函數(shù)為導(dǎo)向，模擬自然界生物進化和遺傳過程，搜索全局最優(yōu)解。 本文針對網(wǎng)格系統(tǒng)中任務(wù)調(diào)度問題提出一個適用的遺傳算法框架。算法中染色體的編碼采用二維0-1矩陣，即文中的“資源-任務(wù)”匹配矩陣。在此基礎(chǔ)上采用三類遺傳算子，即外部交叉算子、內(nèi)部交叉算子和可變的變異算子。外部交叉算子和內(nèi)部

3、交叉算子具有生成最優(yōu)解的能力；變異算子有效的保存了種群的多樣性。為了保證遺傳算法的全局搜索能力，采用任務(wù)最大深度值與最小深度值來共同確定任務(wù)的深度值；為了防止早熟，算法自適應(yīng)的加大變異概率。 遺傳算法中主要控制參數(shù)的取值通過仿真實驗確定，而任務(wù)DAG圖、任務(wù)數(shù)、任務(wù)工作量、資源數(shù)、資源計算能力、資源間通信延遲均可在仿真系統(tǒng)初始化時手動或隨機生成。經(jīng)仿真試驗的結(jié)果數(shù)據(jù)比較，本文算法具有較好的解全局搜索能力，以及較快的收斂速度，能夠