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

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

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

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

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

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