遺傳優(yōu)化的混合網(wǎng)格計算調(diào)度模型SCE部署研究

楚志剛，陶永才

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

1 引言

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

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

網(wǎng)格計算的系統(tǒng)結(jié)構(gòu)包括User、路由器、Portal和JobScheduler。系統(tǒng)中含有數(shù)據(jù)和計算兩種密集Job[8]，它們對應(yīng)的概率分別表示成p和1-p。在數(shù)據(jù)Job中，按照數(shù)據(jù)的大小進一步劃分成大小兩種Job，它們對應(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)是計算Job時，不涉及IO數(shù)據(jù)，參數(shù)fSize=0。系統(tǒng)中關(guān)于資源描述為r(speed，bw，free)。Job和資源的各項參數(shù)描述如表1所示。

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

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

(5)

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

(6)

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

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

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

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

(7)

(8)

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

(9)

(10)

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

(11)

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

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

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

圖1 部署模型

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

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

5.1 實驗設(shè)置

基于SCE部署網(wǎng)格作業(yè)調(diào)度平臺，計算Node采用的是小型集群，Node集群部署五個隊列，用于將資源接入SCE?；旌暇W(wǎng)格的實驗參數(shù)設(shè)置如表2所示，其中設(shè)置了作業(yè)和資源的相關(guān)參數(shù)。初始化改進GA算法種群大小是100；最大進化代數(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é)果分析

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

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

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

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

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

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

6 結(jié)束語

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