楚志剛，陶永才

(1. 鄭州師范學(xué)院信息科學(xué)與技術(shù)學(xué)院，河南 鄭州 450044 ;2. 鄭州大學(xué)信息工程學(xué)院，河南 鄭州 450001)

1 引言

在基因科學(xué)、生物醫(yī)藥、金融分析、仿真模擬等科研領(lǐng)域中，往往涉及高通量、密集型數(shù)據(jù)的計(jì)算。要完成這類計(jì)算依賴于高性能服務(wù)器，由此增加了很多科研與分析機(jī)構(gòu)的成本投入，甚至成為了一些實(shí)驗(yàn)室的研究障礙。為了實(shí)現(xiàn)高通密集數(shù)據(jù)的處理，網(wǎng)格計(jì)算成為了解決方案中的熱點(diǎn)[1-2]。該技術(shù)可以將分布式計(jì)算資源采取整合，使其達(dá)到高性能計(jì)算要求[3]。在整合過程中，通常對(duì)于物理位置、異構(gòu)資源沒有特殊要求。網(wǎng)格計(jì)算的出現(xiàn)降低了高通密集數(shù)據(jù)處理的成本，也因?yàn)槠淙蝿?wù)的可拆分性，提高了數(shù)據(jù)處理的效率。當(dāng)前對(duì)于網(wǎng)格計(jì)算的的研究主要集中在中間件和作業(yè)調(diào)度算法方面[4-5]。常用的中間件有Legion與Globus，目的都是提供資源訪問的接口。它們具有信息傳輸、數(shù)據(jù)管理、定位和訪問等功能，改善了網(wǎng)格計(jì)算的使用性。但是仍然存在不易拓展、不易部署，以及不支持作業(yè)調(diào)度等問題。而SCE[6]則是針對(duì)當(dāng)前中間件應(yīng)用缺陷設(shè)計(jì)的高性能計(jì)算網(wǎng)格軟件。SCE基于OGSA架構(gòu)，涵蓋了網(wǎng)絡(luò)、存儲(chǔ)、數(shù)據(jù)庫(kù)，以及作業(yè)編譯、調(diào)試、查詢等一系列功能。現(xiàn)有網(wǎng)格計(jì)算作業(yè)調(diào)度研究，大多基于單一型作業(yè)，不僅缺乏通用性，而且難以采用作業(yè)時(shí)間作為約束條件。本文研究則兼顧了數(shù)據(jù)與計(jì)算兩類作業(yè)，建立混合網(wǎng)格模型，并對(duì)模型中作業(yè)與資源的時(shí)間約束進(jìn)行分析，從而將調(diào)度轉(zhuǎn)化為最優(yōu)解問題。由于遺傳算法的全局搜索性能突出，因此本文將其引入調(diào)度算法，并針對(duì)存在的無反饋、過早收斂[7]等問題進(jìn)行了改進(jìn)優(yōu)化。

2 混合網(wǎng)格計(jì)算模型

網(wǎng)格計(jì)算的系統(tǒng)結(jié)構(gòu)包括User、路由器、Portal和JobScheduler。系統(tǒng)中含有數(shù)據(jù)和計(jì)算兩種密集Job[8]，它們對(duì)應(yīng)的概率分別表示成p和1-p。在數(shù)據(jù)Job中，按照數(shù)據(jù)的大小進(jìn)一步劃分成大小兩種Job，它們對(duì)應(yīng)的概率分別表示成p′和1-p′。從整體來看，大、小Job的概率分別為pp′和p(1-p′)。本文中，將1500MB作為大、小Job的區(qū)分門限，數(shù)據(jù)大小在門限值以下的為小Job，數(shù)據(jù)大小在門限值以上(包含門限)的為大Job。系統(tǒng)中關(guān)于作業(yè)的描述是job(iniCount，fSize，deadline，arrive)，當(dāng)是計(jì)算Job時(shí)，不涉及IO數(shù)據(jù)，參數(shù)fSize=0。系統(tǒng)中關(guān)于資源描述為r(speed，bw，free)。Job和資源的各項(xiàng)參數(shù)描述如表1所示。

表1 Job與資源參數(shù)描述

網(wǎng)格對(duì)作業(yè)進(jìn)行調(diào)度過程中，在任意時(shí)間點(diǎn)，作業(yè)對(duì)資源的占用具有原子性。假定jobi占用了資源rj，則jobi對(duì)rj的操作時(shí)間表示為

(1)

根據(jù)操作時(shí)間Toperation(i，j)和free參數(shù)，得到j(luò)obi對(duì)rj的完成時(shí)間如下

Tfinish(i，j)=Toperation(i，j)+rj.free

(2)

考慮到作業(yè)時(shí)間不能超過deadline參數(shù)，所以對(duì)作業(yè)和資源的操作采取如下限定

(3)

當(dāng)作業(yè)完成時(shí)間不超過期限參數(shù)時(shí)，jobi能夠正常處理；反之jobi不被處理。當(dāng)資源rj已經(jīng)被jobi占用過，則rj下一次能夠被使用的時(shí)間應(yīng)為

rj.free=Toperation(i，j)+rj.free

(4)

假定網(wǎng)格系統(tǒng)中的作業(yè)集是J={job1，job2，…，jobn}，其中任意元素均由k個(gè)屬性構(gòu)成。于是，作業(yè)集對(duì)應(yīng)的屬性描述如下

(5)

網(wǎng)格中的資源集是R={r1，r2，…，rm}，與作業(yè)一致，也包含k個(gè)屬性。其對(duì)應(yīng)的屬性描述如下

(6)

根據(jù)作業(yè)和資源的屬性集描述可知，它們的集合之積RJ為k×k階矩陣。如果rj中全部屬性都符合jobi需求，便令RJ(j，i)=1；否則令RJ(j，i)=0。此時(shí)，也可以得到作業(yè)與資源的關(guān)系RJ(j，i)=f(jobi，rj)。

3 改進(jìn)遺傳算法作業(yè)調(diào)度

根據(jù)混合網(wǎng)格計(jì)算模型的分析，可以將混合網(wǎng)格作業(yè)調(diào)度看做是如何最優(yōu)化的利用m數(shù)量的資源完成n數(shù)量的作業(yè)，其中還要考慮作業(yè)與資源之間的各種關(guān)系約束。由于可以轉(zhuǎn)化成最優(yōu)解問題，所以本文引入改進(jìn)遺傳算法來實(shí)現(xiàn)混合網(wǎng)格作業(yè)的調(diào)度。

在遺傳算法的編碼階段，考慮到網(wǎng)格作業(yè)調(diào)度需要把作業(yè)集J={job1，job2，…，jobn}映射至資源集R={r1，r2，…，rm}中，同時(shí)還要保證資源屬性與作業(yè)的符合程度，以及時(shí)間約束，這里選擇實(shí)數(shù)編碼[9]，讓每一個(gè)資源對(duì)應(yīng)一個(gè)染色體，每一個(gè)染色體對(duì)應(yīng)一個(gè)作業(yè)。在初始化種群時(shí)，為提高初始種群的有效性，利用隨機(jī)方式得到2m數(shù)量的樣本，用于保證種群樣本的多樣性。同時(shí)利用Min-min得到單個(gè)樣本，并通過該單個(gè)樣本的變異得到l-1個(gè)樣本，用于保證種群中部分樣本的質(zhì)量。從這2m+l數(shù)量的種群內(nèi)經(jīng)過適應(yīng)性篩選出m數(shù)量樣本構(gòu)成初始種群。這樣獲得的初始種群能夠更好的利用高質(zhì)量樣本啟發(fā)尋優(yōu)，降低迭代數(shù)量，加速尋優(yōu)過程。假定進(jìn)化過程種群中有ns個(gè)樣本，作業(yè)總數(shù)是nt，基因數(shù)量受限于資源數(shù)量，范圍是[1，m]，染色體i對(duì)應(yīng)的資源j表示是rij，染色體i作業(yè)執(zhí)行時(shí)間是Tfinish(rij)。在適應(yīng)性篩選時(shí)，需要確保作業(yè)的完成速度快，時(shí)間短。于是，將適應(yīng)度函數(shù)設(shè)計(jì)為

(7)

(8)

其中，fo表示樣本的最佳適應(yīng)性。每次迭代進(jìn)化應(yīng)保證δ值盡可能小，這樣表明樣本的相似性較高。在每輪迭代對(duì)樣本進(jìn)行選擇時(shí)，采用如下規(guī)則為樣本分配選中概率

(9)

(10)

其中，α1和α2為交叉因子，它們的取值過大，會(huì)引發(fā)局部最優(yōu)解；取值過小，會(huì)引發(fā)進(jìn)化速度降低。假定待變異樣本適應(yīng)值為f，則樣本執(zhí)行變異處理的概率如下

(11)

其中，β1和β2為變異因子。與交叉操作一致，當(dāng)變異因子取值過大，會(huì)陷入局部收斂；當(dāng)變異因子取值過小，會(huì)導(dǎo)致進(jìn)化速度變慢。

4 SCE作業(yè)調(diào)度模型

基于SCE實(shí)現(xiàn)作業(yè)調(diào)度時(shí)，為辨別網(wǎng)格服務(wù)身份，將SaltStack獨(dú)立部署于Master上，將Client、CenterServer、FrontServer部署于Minion上，部署模型如圖1所示。根據(jù)SCE部署模型，將網(wǎng)格作業(yè)的調(diào)度過程分成四個(gè)階段。第一階段是Client處理Request，由Client解析作業(yè)，并對(duì)解析后的變量采取校驗(yàn)。校驗(yàn)通過的作業(yè)將被執(zhí)行XML_Make，輸出具有JobName、AppName、RunName、等信息的XML文件。第二階段利用提交函數(shù)獲取全局作業(yè)的gid，由CenterServer服務(wù)器接收gid，并將其持久化至SCEDB中，同時(shí)根據(jù)gid建立用戶作業(yè)的ujid。第三階段通過執(zhí)行do_upload，將作業(yè)相關(guān)文件集合由Client向CenterServer、CenterServer向FrontServer、FrontServer向計(jì)算Node，一級(jí)一級(jí)傳輸。第四階段CenterServer會(huì)從SCEDB中查找XML，解析出Job有關(guān)的信息與資源情況，經(jīng)過FrontServer通知Node，由Node完成計(jì)算。

圖1 部署模型

圖2 網(wǎng)格作業(yè)執(zhí)行模型

5 混合網(wǎng)格作業(yè)調(diào)度性能驗(yàn)證

5.1 實(shí)驗(yàn)設(shè)置

基于SCE部署網(wǎng)格作業(yè)調(diào)度平臺(tái)，計(jì)算Node采用的是小型集群，Node集群部署五個(gè)隊(duì)列，用于將資源接入SCE?；旌暇W(wǎng)格的實(shí)驗(yàn)參數(shù)設(shè)置如表2所示，其中設(shè)置了作業(yè)和資源的相關(guān)參數(shù)。初始化改進(jìn)GA算法種群大小是100；最大進(jìn)化代數(shù)是100；適應(yīng)度加權(quán)系數(shù)λ1=λ2=0.5；交叉因子α1=0.25，α2=0.91；變異因子β2=0.035，β2=0.015。

表2 混合網(wǎng)格參數(shù)設(shè)置

5.2 結(jié)果分析

首先對(duì)本文設(shè)計(jì)的改進(jìn)遺傳算法性能進(jìn)行分析。通過仿真得到進(jìn)化過程中，遺傳算法的收斂曲線，結(jié)果如圖3所示，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為適應(yīng)值。經(jīng)過與經(jīng)典遺傳算法性能對(duì)比，改進(jìn)算法明顯降低了進(jìn)化迭代次數(shù)，且收斂曲線整體平滑，沒有明顯振蕩，大約在70代時(shí)適應(yīng)值便趨于穩(wěn)定，近似收斂，而經(jīng)典遺傳算法在100代的時(shí)候還未達(dá)到收斂。同時(shí)，改進(jìn)算法的適應(yīng)值也明顯優(yōu)于經(jīng)典算法，具有更優(yōu)的作業(yè)執(zhí)行時(shí)間。說明改進(jìn)算法在種群初始化時(shí)采取適應(yīng)性篩選出一部分樣本作為初始種群，利用高質(zhì)量樣本啟發(fā)尋優(yōu)，降低了迭代數(shù)量。在適應(yīng)性計(jì)算時(shí)，分別對(duì)每個(gè)染色體的作業(yè)執(zhí)行速度和染色體內(nèi)每個(gè)作業(yè)的執(zhí)行速度進(jìn)行考慮，加快了收斂速度。另外，適應(yīng)性修正、交叉和變異操作，有效防止了種群出現(xiàn)過早或者局部收斂。

圖3 遺傳算法優(yōu)化性能對(duì)比

然后對(duì)整體算法的響應(yīng)性能進(jìn)行驗(yàn)證，實(shí)驗(yàn)中10000個(gè)作業(yè)調(diào)度的響應(yīng)時(shí)間結(jié)果如圖4所示。過程中沒有發(fā)現(xiàn)作業(yè)提交出現(xiàn)錯(cuò)誤的情況。根據(jù)響應(yīng)時(shí)間結(jié)果統(tǒng)計(jì)，所有Job中，有3894個(gè)Job的響應(yīng)時(shí)間低于100ms，占比為38.49%；9164個(gè)Job的響應(yīng)時(shí)間低于110ms，占比為91.64%。從結(jié)果可以看出，本文調(diào)度算法對(duì)混合網(wǎng)格具有良好的適應(yīng)性和響應(yīng)時(shí)間。

圖4 作業(yè)響應(yīng)時(shí)間結(jié)果

最后，考慮到作業(yè)調(diào)度出現(xiàn)問題時(shí)帶來的影響。這里通過調(diào)整故障間隔來模擬異常情況的影響程度，在故障間隔改變的過程中，得到Job響應(yīng)時(shí)間曲線，如圖5所示。實(shí)驗(yàn)中引入文獻(xiàn)[4]的算法進(jìn)行對(duì)比。故障間隔變大，表明故障出現(xiàn)的頻率降低，固定時(shí)間內(nèi)出現(xiàn)的故障次數(shù)變少。根據(jù)結(jié)果曲線分析，故障的出現(xiàn)會(huì)令作業(yè)服務(wù)斷開，從而拖延平均響應(yīng)速度，故障出現(xiàn)的頻次越高，對(duì)響應(yīng)時(shí)間的拖延越嚴(yán)重，如果作業(yè)量較大，還可能導(dǎo)致計(jì)算服務(wù)阻塞，所以可以看到，隨著故障間隔的變大，各方法的響應(yīng)時(shí)間都在下降。而本文算法顯然受故障影響較小，表明具有比文獻(xiàn)方法更好的網(wǎng)格計(jì)算效率。

圖5 作業(yè)響應(yīng)時(shí)間受故障間隔的影響

6 結(jié)束語(yǔ)

為提高混合網(wǎng)格作業(yè)調(diào)度的效能，本文提出了基于SCE的遺傳優(yōu)化調(diào)度算法。在對(duì)混合網(wǎng)格計(jì)算模型分析的基礎(chǔ)上，得到網(wǎng)格作業(yè)集與資源集的屬性描述，同時(shí)得到作業(yè)與資源間的約束關(guān)系?？紤]到作業(yè)調(diào)度可以轉(zhuǎn)化成最優(yōu)解搜索，于是針對(duì)混合網(wǎng)格作業(yè)調(diào)度設(shè)計(jì)了改進(jìn)遺傳算法，從初始化種群、適應(yīng)性計(jì)算、適應(yīng)性修正、樣本選擇、交叉和變異多方面進(jìn)行了優(yōu)化?？紤]到拓展、部署和對(duì)作業(yè)調(diào)度的支持，引入SCE中間件提供完善的訪問接口，并基于SCE作業(yè)調(diào)度的部署進(jìn)行算法性能驗(yàn)證。結(jié)果表明本文改進(jìn)的遺傳算法具有良好的啟發(fā)尋優(yōu)效果，降低了迭代次數(shù)與進(jìn)化時(shí)間，有效防止了種群出現(xiàn)過早或者局部收斂；經(jīng)過10000次Job執(zhí)行沒有出現(xiàn)故障情況，顯著提高了混合網(wǎng)格計(jì)算作業(yè)調(diào)度的穩(wěn)定性與響應(yīng)速度；通過人為調(diào)整故障間隔發(fā)現(xiàn)，即便在出現(xiàn)異常情況時(shí)，本文所提的作業(yè)調(diào)度方法也能獲得較好的響應(yīng)時(shí)間。