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

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

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

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

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

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