基于遺傳算法的網(wǎng)格任務(wù)調(diào)度研究及實現(xiàn).pdf

1、隨著科學(xué)的日新月異，網(wǎng)絡(luò)技術(shù)的發(fā)展正向著網(wǎng)格邁進(jìn)。網(wǎng)格是地理上分布的異構(gòu)的動態(tài)的各種高性能計算資源，它將高速互聯(lián)網(wǎng)、計算機、大型數(shù)據(jù)庫、傳感器、遠(yuǎn)程設(shè)備等融為一體，為人們提供更多的資源、功能和服務(wù)。網(wǎng)格的最終目的就是給用戶提供一種與地理位置無關(guān)、與具體計算設(shè)施無關(guān)的透明的計算能力。網(wǎng)格是要將合適的資源分配給用戶使用，基于該問題的求解稱為網(wǎng)格計算，它是近年興起的一種重要的并行分布式計算技術(shù)，在統(tǒng)一的框架下把廣域分布的資源互連、解決日益增長

2、的計算需求以及飛速發(fā)展的互聯(lián)網(wǎng)通訊技術(shù)。但是由于網(wǎng)格計算具有擴(kuò)展性、異構(gòu)性、不可預(yù)測性，使得其資源管理及任務(wù)調(diào)度策略面臨了很大的挑戰(zhàn)。 本文介紹了網(wǎng)格的基本概念，著重討論了網(wǎng)格環(huán)境下計算任務(wù)在地理分布的各種資源之間的動態(tài)調(diào)度。這類問題可描述為將n個相互獨立的任務(wù)分配到m 個異構(gòu)可用資源上以獲取最小的完成時間和最大的資源利用率<'[13]>，這是一個NP完全問題<'[3]>。本文采用啟發(fā)式遺傳算法<'[6]>來解決該問題，通過設(shè)計

3、染色體編碼、解碼方式獲得初始種群，依據(jù)有向無環(huán)圖(DAG)圖定義任務(wù)執(zhí)行的邏輯關(guān)系，選取適應(yīng)值函數(shù)計算每一代的適應(yīng)值，制定復(fù)制、交叉、變異算子的取得方式，并根據(jù)網(wǎng)格調(diào)度必須解決異構(gòu)計算系統(tǒng)以及多處理器之間的通信延遲問題這一特殊性，設(shè)計并實現(xiàn)基于遺傳算法的任務(wù)調(diào)度算法(純遺傳調(diào)度算法,PGSA)。另外，為了更好縮短網(wǎng)格任務(wù)調(diào)度的執(zhí)行時間，減少通信延遲，在該算法基礎(chǔ)上進(jìn)行改進(jìn)，得到本文提出的基于重要路徑(Major Path)任務(wù)復(fù)制的遺傳

4、調(diào)度算法(MPGSA)。 本文算法采用C語言實現(xiàn)。無論是PGSA還是MPGSA都由三個模塊構(gòu)成，分別是SIM模塊、Chromo模塊以及GA模塊。其中SIM模塊用來構(gòu)建網(wǎng)格仿真及計算任務(wù)調(diào)度完成時間，在獲得Chromo模塊傳來的染色體后，經(jīng)過仿真器內(nèi)部運算獲得其調(diào)度完成時間并將該值傳給GA模塊；Chromo模塊用來實現(xiàn)有關(guān)染色體的操作，并將隨機生成的染色體傳給 SIM 模塊；GA模塊用來對任務(wù)調(diào)度進(jìn)行優(yōu)化，通過調(diào)度Chromo模

5、塊和SIM模塊，計算適應(yīng)度函數(shù)值，實現(xiàn)當(dāng)代染色體的遺傳操作從而產(chǎn)生新一代優(yōu)化的染色體，并傳給SIM模塊以獲取優(yōu)化后的完成時間再準(zhǔn)備進(jìn)行又一次優(yōu)化，最后返回一定遺傳代數(shù)范圍內(nèi)最優(yōu)解的完成時間和迭代次數(shù)。 在網(wǎng)格任務(wù)調(diào)度算法中通常采用仿真器獲取調(diào)度完成時間，比較算法之間的性能。因而本文在衡量各種網(wǎng)格模擬器利弊后，最終基于Simgrid模擬器構(gòu)建網(wǎng)格仿真環(huán)境。本文依據(jù)Simgrid實驗?zāi)M出PGSA與MPGSA算法中任務(wù)調(diào)度最優(yōu)解的