楚志剛，陶永才

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

1 引言

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

2 混合網格計算模型

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

表1 Job與資源參數描述

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

(5)

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

(6)

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

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

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

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

(7)

(8)

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

(9)

(10)

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

(11)

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

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

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

圖1 部署模型

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

5 混合網格作業(yè)調度性能驗證

5.1 實驗設置

基于SCE部署網格作業(yè)調度平臺，計算Node采用的是小型集群，Node集群部署五個隊列，用于將資源接入SCE。混合網格的實驗參數設置如表2所示，其中設置了作業(yè)和資源的相關參數。初始化改進GA算法種群大小是100；最大進化代數是100；適應度加權系數λ1=λ2=0.5；交叉因子α1=0.25，α2=0.91；變異因子β2=0.035，β2=0.015。

表2 混合網格參數設置

5.2 結果分析

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

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

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

圖4 作業(yè)響應時間結果

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

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

6 結束語

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