蒲 汛，何 為，盧顯良

(1. 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 610054; 2. 西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院 重慶 北培區(qū) 400716;3. 四川美術(shù)學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)中心 重慶 九龍坡區(qū) 400053)

基于改進(jìn)遺傳算法的多QoS約束網(wǎng)格任務(wù)調(diào)度

蒲 汛1,2，何 為3，盧顯良1

(1. 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 610054; 2. 西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院 重慶 北培區(qū) 400716;3. 四川美術(shù)學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)中心 重慶 九龍坡區(qū) 400053)

解決好網(wǎng)格環(huán)境中多QoS約束條件下的獨(dú)立任務(wù)調(diào)度問(wèn)題是提高網(wǎng)格系統(tǒng)關(guān)鍵技術(shù)之一。將該類(lèi)問(wèn)題規(guī)約為多目標(biāo)組合問(wèn)題優(yōu)化，以NSGA-II算法為基礎(chǔ)，通過(guò)優(yōu)化其初始種群的生成算法以及變異算子的更新算法，以期在網(wǎng)格多目標(biāo)約束條件下尋找到較優(yōu)任務(wù)調(diào)度方案。仿真實(shí)驗(yàn)表明，該算法的有效性和實(shí)用性。

遺傳算法; 任務(wù)分配; Pareto最優(yōu); QoS約束

網(wǎng)格計(jì)算[1]作為并行計(jì)算與分布式計(jì)算的一個(gè)發(fā)展方向，已逐漸從實(shí)驗(yàn)室走向了商業(yè)應(yīng)用。它作為一種整合網(wǎng)絡(luò)異構(gòu)資源的系統(tǒng)，在動(dòng)態(tài)、多制度的虛擬組織中協(xié)調(diào)各種資源的共享，可以解決大規(guī)模挑戰(zhàn)性計(jì)算問(wèn)題?；诖耍W(wǎng)格服務(wù)需要有靈活的面向用戶QoS的資源管理策略和調(diào)度策略。然而，網(wǎng)格環(huán)境涉及網(wǎng)格用戶、虛擬組織管理者、網(wǎng)格資源管理者等多個(gè)實(shí)體；不同實(shí)體間對(duì)管理機(jī)制、安全策略等用戶QoS的目標(biāo)都不盡相同，甚至相互矛盾。如資源管理者希望資源集群以可控的方式安全、高效地工作，而網(wǎng)格用戶希望盡可能低價(jià)地利用所有資源；資源管理者希望系統(tǒng)可以最大化吞吐量，而網(wǎng)格用戶僅期望自己本身的應(yīng)用執(zhí)行時(shí)間較短，自身的作業(yè)集吞吐量較高?；谶@種多用戶QoS約束的網(wǎng)格環(huán)境中，網(wǎng)格任務(wù)調(diào)度的實(shí)質(zhì)是將任務(wù)分配到合適的資源上，使得在滿足用戶QoS需求的前提下，任務(wù)完成時(shí)間盡量小且資源利用率盡量高。由于網(wǎng)格環(huán)境中任務(wù)調(diào)度算法面臨的是一個(gè)NP完全問(wèn)題[2]，它引起了眾多學(xué)者的關(guān)注，成為目前網(wǎng)格計(jì)算研究領(lǐng)域的一個(gè)焦點(diǎn)。

目前，在網(wǎng)格環(huán)境滿足多用戶QoS需求的任務(wù)分配解決算法一般分為兩類(lèi)：1) 將多個(gè)QoS的目標(biāo)函數(shù)聚合成單一目標(biāo)函數(shù)。這類(lèi)算法具有時(shí)間復(fù)雜度低、便于實(shí)現(xiàn)的特點(diǎn)，如Min-min、GA和GENITOR-style GA等調(diào)度策略。文獻(xiàn)[3]采用具有依賴關(guān)系、優(yōu)先級(jí)、最遲完成時(shí)間等QoS需求的作業(yè)模型。比較上述調(diào)度策略可得，GENITOR-style GA能夠獲得最好的結(jié)果，而時(shí)間開(kāi)銷(xiāo)最小的 Min-min也能獲得較好的結(jié)果。2) 采用多目標(biāo)優(yōu)化算法，使用Pareto占優(yōu)指導(dǎo)搜索，并且返回一組非占優(yōu)解作為資源分配結(jié)果，以滿足用戶QoS需求。文獻(xiàn)[4]使用了多種策略和方法解決多目標(biāo)進(jìn)化算法的兩個(gè)目標(biāo)：(1) 靠近Pareto最優(yōu)前沿。(2) 保持種群多樣性。多目標(biāo)優(yōu)化算法雖然在某些方面取得了很好的結(jié)果，但是該算法的低效率和高復(fù)雜性是一個(gè)普遍的問(wèn)題。

本文將網(wǎng)格環(huán)境中多QoS約束的網(wǎng)格獨(dú)立作業(yè)調(diào)度問(wèn)題規(guī)約為多目標(biāo)組合最優(yōu)化問(wèn)題，在NSGA-II[5]的算法基礎(chǔ)上提出一種面向多QoS約束網(wǎng)格作業(yè)調(diào)度問(wèn)題的多目標(biāo)演化算法(MQoS-GA)，盡可能協(xié)調(diào)同用戶的QoS要求，保障網(wǎng)格用戶在多個(gè)QoS維度下的效用值最大化。

1 多QoS參數(shù)約束的網(wǎng)格任務(wù)調(diào)度相關(guān)定義

本文涉及的網(wǎng)格環(huán)境將采用集中式任務(wù)分配方式，即在任務(wù)積累到一定數(shù)值時(shí)再分配，或者在上次任務(wù)分配完成后，開(kāi)始分配新到的任務(wù)。本文還假設(shè)系統(tǒng)所分配的任務(wù)就是網(wǎng)格調(diào)度器進(jìn)行任務(wù)分配的最小單位，而且所分配的將是獨(dú)立的任務(wù)，不考慮計(jì)算任務(wù)的跨節(jié)點(diǎn)執(zhí)行，并且大型計(jì)算任務(wù)的分解由用戶來(lái)完成。因此有如下的符號(hào)定義：

定義 4 集 MAP={ map1, map2,…, mapn}表示由映射方案產(chǎn)生的映射集合，每一個(gè)映射方案為一個(gè)三元組map={a,s,c}。其中a:T→R表示資源分配的映射； a(ti)=rj表示將任務(wù)ti分配到資源rj上執(zhí)行；s表示任務(wù)ti在資源rj上的執(zhí)行次序；c表示任務(wù)ti在資源rj上的預(yù)計(jì)完成時(shí)間。

本文引用文獻(xiàn)[6]中定義的多目標(biāo)優(yōu)化問(wèn)題和部分相關(guān)概念，包括以下的定義：

定義 5 Pareto占優(yōu)：如果向量U=(u1,u2,…,um)Pareto占優(yōu)V=(v1,v2,…,vm)，則記為U＜V，即U＜V,當(dāng)且僅當(dāng)?i∈{1,2,…,m}，ui≤vi∧?i∈{1,2,…,m}，ui＜vi。決策向量xu∈?是Pareto最優(yōu)的，當(dāng)且僅當(dāng)不存在 xv∈?滿足F(xv)≤F(xu)。Pareto最優(yōu)決策向量的集合被稱(chēng)為問(wèn)題的Pareto最優(yōu)集，對(duì)應(yīng)的目標(biāo)向量集合被稱(chēng)為非占優(yōu)集或者Pareto前沿。為了簡(jiǎn)化，本文也使用占優(yōu)代替Pareto占優(yōu)。

2 多QoS參數(shù)約束的網(wǎng)格任務(wù)調(diào)度算法的設(shè)計(jì)

2.1 染色體編碼

傳統(tǒng)的遺傳算法染色體編碼形式一般是將決策空間的備選方案編碼成一個(gè)0,1代碼。這種編碼方式對(duì)于類(lèi)似網(wǎng)格環(huán)境的作業(yè)調(diào)度問(wèn)題顯然不太適合，因?yàn)檎{(diào)度的結(jié)果既要表示作業(yè)的分配情況(即一個(gè)作業(yè)被分配到某計(jì)算資源上執(zhí)行)，又要表示在該計(jì)算資源上對(duì)作業(yè)的執(zhí)行順序。

上述采用0,1編碼的方式很難包含映射的全部信息。對(duì)于這類(lèi)問(wèn)題一般采用直接編碼的方式來(lái)完成，即：

式中 每一列表示一個(gè)資源Ri，每個(gè)資源從第一行開(kāi)始向下并行執(zhí)行所分配任務(wù)，網(wǎng)格中的任務(wù)被賦予唯一的編號(hào)，這樣的調(diào)度方案稱(chēng)為map1。所有染色體集合MAP={map1,map2,…,mapi}即為種群。

2.2 選擇算子

根據(jù)當(dāng)前種群所有個(gè)體在各個(gè)QoS維度的效用函數(shù)值，采用快速非劣排序算法對(duì)當(dāng)前種群進(jìn)行非劣排序，得到每個(gè)個(gè)體mapi的非劣次序maprank，該值即為該個(gè)體的偽適應(yīng)度值。根據(jù)該偽適應(yīng)度值分別為每個(gè)個(gè)體賦予一個(gè)擁擠距離。采用基于擁擠比較的二元錦標(biāo)賽選擇來(lái)選擇參與交叉的個(gè)體。由以上方法選擇N對(duì)個(gè)體，通過(guò)交叉和變異產(chǎn)生大小為N的新種群，將父代與子代群體結(jié)合組成2N的臨時(shí)種群，而排序靠前的N個(gè)個(gè)體，非支配程度較強(qiáng)，認(rèn)為是較為優(yōu)良的個(gè)體，采用精英保留策略，作為優(yōu)秀的非支配解，保存在一個(gè)外部存儲(chǔ)空間中。然后將排序后的群體進(jìn)行新一輪遺傳操作，產(chǎn)生的新種群與外部存儲(chǔ)空間中的N個(gè)優(yōu)秀個(gè)體結(jié)合，作為下一步遺傳操作的新群體。

2.3 交叉算子

采用兩點(diǎn)交叉，對(duì)由選擇算子選出的兩個(gè)父?jìng)€(gè)體p1和p2隨機(jī)生成兩個(gè)交叉點(diǎn)c1和c2。在交叉生成的子個(gè)體中，在c1和c2之間的資源的作業(yè)隊(duì)列由p1和p2隨機(jī)選擇一個(gè)繼承得到，其余部分從另一個(gè)父?jìng)€(gè)體繼承獲得。由于不限制個(gè)體參與交叉的次數(shù)，并且交叉位置是隨機(jī)選擇的，因此無(wú)法保證交叉產(chǎn)生的子個(gè)體代表的調(diào)度方案的有效性?？赡艹霈F(xiàn)同一作業(yè)ti被分配到多個(gè)資源上或者沒(méi)有被分配的情況，因此需要采用作業(yè)狀態(tài)檢測(cè)算法Job-Check恢復(fù)調(diào)度方案的有效性。

作業(yè)狀態(tài)檢測(cè)算法(Job-Check)如下：

2.4 變異算子

當(dāng)父本性狀趨于一致時(shí)，交叉操作的探測(cè)能力有限，易產(chǎn)生“早熟”現(xiàn)象。變異算子的引入可在一定程度上解決這一問(wèn)題。本文將交叉算子產(chǎn)生的子個(gè)體分別對(duì)自變量在其解空間進(jìn)行非均勻變異后，再隨機(jī)取一組合作為變異結(jié)果。在該算子中，變異步長(zhǎng)隨世代數(shù)增加自適應(yīng)減小。在迭代初期，以大變異步長(zhǎng)提高搜索效率；在迭代后期，種群趨于穩(wěn)定時(shí)，以小變異步長(zhǎng)搜索保證解的最優(yōu)性：

由于在變異過(guò)程中沒(méi)有QoS約束計(jì)算資源與作業(yè)的關(guān)系，因此變異后的新個(gè)體可能出現(xiàn)無(wú)效的情況。如在新個(gè)體中計(jì)算資源r1和r2對(duì)應(yīng)的新作業(yè)隊(duì)列中可能存在作業(yè)x，它的最小QoS需求qmin不能被滿足。不只是被交換的兩個(gè)作業(yè)可能出現(xiàn)這種情況，在此后的作業(yè)也可能由于完成時(shí)間被推遲而導(dǎo)致某些維度上的最小QoS需求不能被滿足。需要掃描這兩個(gè)隊(duì)列，去掉這些作業(yè)。

2.5 MQoS-GA算法描述

初始化時(shí)用貪心算法，先把QoS要求最多任務(wù)選出來(lái)，分給能滿足要求的第一個(gè)資源的隊(duì)列；以最快速度，產(chǎn)生一個(gè)相對(duì)較優(yōu)的初始種群；同時(shí)需要輸入作業(yè)和資源信息、初始種群的大小、變異概率以及最大迭代次數(shù)，得到一個(gè)由Pareto調(diào)度方案組成的集合。

3 性能評(píng)估

本文通過(guò)仿真實(shí)驗(yàn)考察了40～200個(gè)獨(dú)立作業(yè)在20個(gè)計(jì)算資源組成的網(wǎng)格系統(tǒng)的調(diào)度性能，并假設(shè)每個(gè)任務(wù)在所有計(jì)算資源上的執(zhí)行時(shí)間是可精確預(yù)測(cè)的。

圖1 任務(wù)分配算法執(zhí)行時(shí)間

圖1所示為任務(wù)調(diào)度算子執(zhí)行的時(shí)間。從圖中可以看出，本文提出的算法在執(zhí)行時(shí)間上略微高于NSGA-II算法的執(zhí)行時(shí)間，主要是初始化種群和變異算子的生成占用了一定的時(shí)間。

任務(wù)完成時(shí)間比較如圖2所示，MQoS-GA產(chǎn)生的任務(wù)分配時(shí)間跨度明顯優(yōu)于NSGA-II產(chǎn)生任務(wù)分配情況。

圖2 任務(wù)完成時(shí)間比較

4 結(jié) 論

本文改進(jìn)了NSGA-II在網(wǎng)格環(huán)境中任務(wù)調(diào)度的應(yīng)用算法，優(yōu)化了其種群初始化的方法以及變異算子的計(jì)算方法。仿真實(shí)驗(yàn)表明，MQoS-GA算法在計(jì)算復(fù)雜性上雖然有所增加，但能達(dá)到很高的性能，在目前機(jī)器性能飛速發(fā)展的情況下，完全能適應(yīng)網(wǎng)格環(huán)境中任務(wù)分配的多QoS用戶需求。

[1] FOSTER I. The grid: a new inf rast ructure for 21st century science[J]. Physics Today, 2002 , 55(2): 42-47.

[2] ANDRONIKOS T, KOZIRIS N. Optima scheduling for UET-UCT grids into fixed number of processors[C]//8th Euromicro Workshop on Parallel and Distributed Processing 2000 Proceedings. [S.l.]: [s.n.], 2000.

[3] BRAUN T D, SIEGEL H J. A Maciejewski static mapping heuristics for tasks with dependencies, priorities, deadlines,and multiple versions in heterogeneous environments[C]//The 16th Int’1 Parallel and Distributed Processing Symposium. Fort Lauderdale, FL: [s.n.], 2002.

[4] VELDHUIZEN D A V, LAMONT G B. Multi-objective evolutionary algorithms: Analyzing the state-of-the-art[J].IEEE Trans on Evolutionary Computation, 2000, 18(2):125-147.

[5] KALYANMOY D, AMRITT P, SAMEER A, et al. A fast and elitist multi objective genetic algorithm[J]. NSGA-II IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197

[6] GEILEN M, BASTEN T, THEELEN B, et al. An algebra of Pareto points[C]//Proc of Application of Concurrency to Sys-tem Design, 5th Int Conf, ACSD. LosAlamitos, CA,USA: IEEE Computer Society Press, 2005.

Improved Genetic Algorithm for Grid Job Scheduling of Multi-QoS Constraints

PU Xun1,2, HE Wei3, and LU Xian-liang1

(1. School of Computer Science and Engineering , University of Electronic Science and Technology of China Chengdu 610054;
2. College of Computer and Information Science, South-West University Beipei Chongqing 400716;
3. Computer Network Information Center, Sichuan Fine Arts Institute Jiulongpo Chongqing 400053)

The key to improve the efficiency of grid computing is to solve an independent task scheduling problem under the QoS constraints. In this paper, such a problem is described as the issue of multi-objective portfolio optimization. As a result, an advanced Pareto multi-objective optimization with genetic algorithm is developed based on NSGA-II algorithm. Simulation results show that this algorithm is effective and practical.

genetic algorithm; job scheduling; Pareto optimal; QoS constrains

TP918.91

A

10.3969/j.issn.1001-0548.2010.z1.013

2009 ? 11 ? 15

國(guó)家自然科學(xué)基金(70871061)

蒲 汛(1973 ? )，男，博士生，主要從事分布式系統(tǒng)和網(wǎng)格計(jì)算方面的研究.

編 輯 黃 莘