九種智能算法在科學(xué)工作流調(diào)度中的應(yīng)用比較

馬敬敬，閻朝坤, 鄭金格

(河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開封475000)

工作流作為一種面向過程建模和管理的核心技術(shù)，能有效地描述活動及活動間的復(fù)雜約束關(guān)系，已成為大規(guī)?？茖W(xué)應(yīng)用的典型范式.由于涉及大量的數(shù)據(jù)集和復(fù)雜運(yùn)算，對計(jì)算和存儲能力有很高的要求.當(dāng)前，科學(xué)工作流應(yīng)用普遍被部署到一些網(wǎng)格系統(tǒng)中執(zhí)行，如TeraGrid，EGEE，Open ScienceGrid 等.為了管理科學(xué)工作流的執(zhí)行，一些工作流管理系統(tǒng)被構(gòu)建，著名的有Khajemohammadi H[1],GrADS[2],Kepler[3],Pegasus[4],SwinDeW-G.作為科學(xué)工作流管理系統(tǒng)的一個重要組成部分，工作流調(diào)度的目的是為工作流的子任務(wù)選擇最合適的資源執(zhí)行，保障工作流的順利完成并滿足用戶的QoS 要求，調(diào)度策略的優(yōu)劣對系統(tǒng)性能有明顯的影響.工作流執(zhí)行時間通常是用戶最為關(guān)注的QoS指標(biāo)，其中以優(yōu)化工作流執(zhí)行時間為目標(biāo)的研究已經(jīng)很多.典型算法有：列表調(diào)度算法HEFT 和CPOP，基于分層技術(shù)的動態(tài)關(guān)鍵路徑調(diào)度算法DCP和DLS等，這些都屬于啟發(fā)式算法.除此之外，智能算法在工作流調(diào)度中也日益受到關(guān)注，一些實(shí)際的工作流管理系統(tǒng)也開始加入智能算法.比如ASKALON系統(tǒng)，已經(jīng)把遺傳算法這一智能算法應(yīng)用在實(shí)際科學(xué)工作流調(diào)度很多年了.筆者考慮了九種智能算法在工作流調(diào)度中的應(yīng)用，并對其性能進(jìn)行了比較.

1 相關(guān)研究

目前為止，很多智能算法應(yīng)用于工作流調(diào)度中，智能算法在工作流調(diào)度中表現(xiàn)出良好的性能.如美國的J.H.Holland教授提出了基于遺傳算法(GA)的工作流調(diào)度，相對于HEFT或CPOP算法來說，具有良好的全局搜索能力.Pandey S, Wu L[5]等人提出了將基于粒子群優(yōu)化算法的啟發(fā)式算法(PSO)用于云資源調(diào)度中.Yu J和Buyya R[6]等利用遺傳算法解決有最后期限和費(fèi)用約束的工作流調(diào)度問題.還有Chen W N和Zhang J[7]，通過優(yōu)化蟻群算法(ACO)，解決了網(wǎng)格工作流調(diào)度問題上不同的QoS要求.

此外，許多啟發(fā)于自然界和仿生物學(xué)的智能算法，在一些復(fù)雜的實(shí)際工程問題上有廣泛應(yīng)用.混合蛙跳算法(SFLA)[7]以其結(jié)構(gòu)簡單、參數(shù)少、全局搜索能力強(qiáng)，在水資源網(wǎng)絡(luò)優(yōu)化、函數(shù)優(yōu)化、圖像處理等問題方面應(yīng)用良好.布谷鳥搜索算法(CS)[8]具有參數(shù)少、適應(yīng)性好、搜索路徑優(yōu)的特點(diǎn)，多應(yīng)用于工程優(yōu)化問題和智能計(jì)算問題中.蝙蝠算法(BA)[8]以其結(jié)構(gòu)簡單、魯棒性強(qiáng)的特點(diǎn)，則被廣泛應(yīng)用于全局工程優(yōu)化問題、結(jié)構(gòu)優(yōu)化問題中.人工蜂群算法(ABC)[9]具有很強(qiáng)魯棒性、算法靈活、適應(yīng)性強(qiáng)，應(yīng)用到神經(jīng)網(wǎng)絡(luò)訓(xùn)練、多圖像處理、蛋白質(zhì)檢測等許多實(shí)際問題中.筆者對九種智能算法GA,PSO,SFLA,ACO,ABC,CS,BA,CRO以及MA在工作流調(diào)度中的應(yīng)用[10]進(jìn)行了分析和比較.

2 問題描述

2.1 系統(tǒng)模型

用戶由系統(tǒng)接口輸入要執(zhí)行和測試的工作流,系統(tǒng)定義模塊由收到的工作流信息對該工作流進(jìn)行定義，并將定義好的工作流發(fā)送至執(zhí)行引擎.執(zhí)行引擎接收到工作流后，將工作流中的各任務(wù)映射到相應(yīng)的系統(tǒng)資源上，再向調(diào)度引擎發(fā)送調(diào)度請求.調(diào)度引擎接收調(diào)度請求，并從資源管理器獲取資源信息，調(diào)度完成相應(yīng)任務(wù).每次調(diào)度完成后調(diào)度引擎會將調(diào)度過的工作流信息反饋給執(zhí)行引擎，以便執(zhí)行引擎更新當(dāng)前工作流執(zhí)行狀態(tài)，進(jìn)行后續(xù)的調(diào)度請求工作，不斷循環(huán)，直至完成工作流調(diào)度.工作流管理系統(tǒng)的系統(tǒng)模型如圖1所示.

圖1 工作流管理系統(tǒng)模型圖

2.2 應(yīng)用模型

工作流中的各個子任務(wù)和子任務(wù)執(zhí)行次序的約束關(guān)系將轉(zhuǎn)化為一個(有向無環(huán)圖)DAG來表示[8].在DAG中，節(jié)點(diǎn)表示工作流中的各個任務(wù)，而有向邊則用于表示各子任務(wù)間執(zhí)行順序的約束關(guān)系.以有向無環(huán)圖G={V,E}為例，節(jié)點(diǎn)集合V={V1,V2,…,Vn}中，各元素分別表示工作流的每一個任務(wù)，有向邊集合E={e12,e13,…,e(n-1)n}中，各元素分別表示工作流中事務(wù)流程的約束關(guān)系，即對于有向邊eij=(vi,vj)，表示任務(wù)vi先于任務(wù)vj執(zhí)行.對于表示整個工作流的DAG，還會增加兩個虛擬節(jié)點(diǎn)，一個作為在工作流執(zhí)行的起始節(jié)點(diǎn)，連接向入度為0的節(jié)點(diǎn)，另一個作為工作流執(zhí)行的結(jié)束節(jié)點(diǎn)，連接向出度為0的節(jié)點(diǎn).工作流調(diào)度中的虛擬機(jī)資源將轉(zhuǎn)化相應(yīng)的資源節(jié)點(diǎn)，工作流調(diào)度是用于子任務(wù)的映射.

2.3 調(diào)度問題

工作流調(diào)度問題的求解過程，可以描述為：在用戶設(shè)定的QoS約束下，為工作流各子任務(wù)找到合適的資源節(jié)點(diǎn)，即尋找工作流各子任務(wù)到資源節(jié)點(diǎn)的映射方案，可以表示為：

S:{t1,…,tm}×{r1,…,rn}→{0,1}

m為子任務(wù)節(jié)點(diǎn)的個數(shù)，n為資源節(jié)點(diǎn)個數(shù).

本文QoS主要針對工作流調(diào)度的完成時間，即：最小完成時間.

3 智能算法及應(yīng)用

大多數(shù)智能算法啟發(fā)于自然界，來源于仿生物學(xué).人們通過模擬自然界中的生物進(jìn)化過程，將抽象的優(yōu)化思想運(yùn)用到科學(xué)問題的求解中，從而得出了設(shè)計(jì)這樣一類用來解決復(fù)雜優(yōu)化問題的算法.近幾十年來，人們不斷提出了許多智能算法，各種智能算法也不斷被改進(jìn).但智能算法的基本流程通常如上圖2所示. 算法運(yùn)行之初，要先初始化相關(guān)參數(shù)，用以隨機(jī)或按一定規(guī)則產(chǎn)生一個初始種群或位置，即最初的解.然后，在整個解空間上按一定規(guī)則生成新的解，即進(jìn)行解的全局搜索.直到判斷得到更優(yōu)解后，會根據(jù)解的不同情況，利用相應(yīng)算子，在更優(yōu)解附近進(jìn)行局部搜索，進(jìn)一步尋找最優(yōu)解.直到求得最優(yōu)解符合終止條件，則輸出結(jié)束，否則進(jìn)行下一代的搜索.

在工作流調(diào)度問題中，許多智能算法被應(yīng)用，智能算法在工作調(diào)度中也表現(xiàn)出較于傳統(tǒng)工作流調(diào)度算法更好的性能.蟻群優(yōu)化算法靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，模擬螞蟻以信息素獲取較短路徑信息的方法.在工作流調(diào)度中，通過優(yōu)化工作流調(diào)度時的路徑選擇策略，提高了工作流調(diào)度的效率.化學(xué)反應(yīng)算法模擬分子間化學(xué)反應(yīng)而引起的分子間的各種相互作用，不斷迭代和比較，可在工作流調(diào)度中避免搜索過程陷入局部最優(yōu)，優(yōu)化工作流調(diào)度費(fèi)用.智能算法在工作流調(diào)度問題中的應(yīng)用，極大地豐富和優(yōu)化了求解策略，提高了服務(wù)質(zhì)量.

智能算法的工作流調(diào)度與啟發(fā)式不同，涉及解的構(gòu)造，迭代過程,下面針對智能算法解的表示進(jìn)行說明.

圖2 智能算法基本流程圖

任務(wù)的分配串和任務(wù)的調(diào)度串分別用于控制任務(wù)的資源分派和調(diào)度順序,對工作流中的任務(wù)進(jìn)行調(diào)度的求解過程即是對任務(wù)的分配串進(jìn)行編碼的過程.由于任務(wù)的調(diào)度串對任務(wù)的調(diào)度順序進(jìn)行了約束，則在構(gòu)造用于任務(wù)到資源映射、控制任務(wù)資源分派的分配串時，就要保證該分配下對于某一任務(wù)的調(diào)度能夠在其之前的約束任務(wù)全部完成后才可以開始.WorkflowSim工具包中設(shè)置了相關(guān)的組件來控制工作流的調(diào)度條件，如圖3所示，是一個任務(wù)分配串的編碼.

圖3 分配串的編碼方式

4 實(shí)驗(yàn)及分析

4.1 測試科學(xué)工作流模型

Montage是由NASA/IPAC紅外科學(xué)館創(chuàng)造了一個開源工具包，可用于生成自定義的天空鑲嵌圖案，用作輸入圖像在FITS中(Flexible Image Transport System)，如圖4所示.Inspiral模型運(yùn)行Pegasus于LIGO數(shù)據(jù)網(wǎng)格和開放科學(xué)網(wǎng)格，如圖5所示.

CyberShake模型工作流是由南部加利福尼亞地震中心用來表征一個區(qū)域的地震危險性特征,這些工作流程來自2 011個包括了高頻碼生產(chǎn)運(yùn)行，如圖6所示.

圖4 Montage模型圖

圖5 Inspiral模型圖

圖6 CyberShake模型圖

4.2 參數(shù)設(shè)置

4.2.1 系統(tǒng)參數(shù)設(shè)置

實(shí)驗(yàn)中的任務(wù)參數(shù)的設(shè)置默認(rèn)為WorkflowSim工具包下的工作流基本參數(shù),而虛擬資源的數(shù)量為5個，每個資源的計(jì)算能力在400～1 200之間.

4.2.2 算法參數(shù)設(shè)置

實(shí)驗(yàn)中各智能算法的參數(shù)設(shè)置如表1所示.

4.3 實(shí)驗(yàn)結(jié)果分析

4.3.1 Montage工作流調(diào)度實(shí)驗(yàn)結(jié)果分析

表2、表3、表4記錄了在Montage模型下任務(wù)量分別為25，50和100時各算法完成時間的Min、AVG和MAX值.

表1 智能算法參數(shù)設(shè)置表

表2 Montage_25工作流完成時間優(yōu)化結(jié)果

從上面的表格可以看出，當(dāng)任務(wù)數(shù)為25和50時，ABC和ACO的各類完成時間較短.如表3，ABC和ACO的平均完成時間較BA和GA提高40%.然而，當(dāng)任務(wù)量增加時，如表4所示，ABO較所有算法平均完成時間最長，其完成時間明顯增加，時間效率降低.反觀CRO，在任務(wù)數(shù)為25和50時完成時間就比較短.在表4中任務(wù)數(shù)為100時，其平均完成時間更是達(dá)到最短，和其他算法相比，CRO在工作流完成時間上更高效.

表3 Montage_50工作流完成時間優(yōu)化結(jié)果

表4 Montage_100工作流完成時間優(yōu)化結(jié)果

4.3.2 Inspiral工作流調(diào)度實(shí)驗(yàn)結(jié)果及分析

在Inspiral模型下任務(wù)量分別為30，50和100時各算法的完成時間如表5、表6、表7所示.

表5 Inspiral_30工作流完成時間優(yōu)化結(jié)果

從上面的表格可以看出，當(dāng)任務(wù)量為30和50時，ABC,GA和SFLA三種算法的完成時間都相對較短.例如，在表5中，MA的平均完成時間只有PSO的0.6倍.但是，在任務(wù)量為100的情況下，ABC和GA的平均完成時間達(dá)到6 037.07和5 527.5，與除CS外的其他算法相比平均完成時間最長.可見，隨著任務(wù)量的增加，各個算法的運(yùn)行時間也會隨著任務(wù)量的增加而增加.而對于CRO，在任務(wù)量為100時，平均完成時間最短，僅有CS平均完成時間的四分之三.

表6 Inspiral_50工作流完成時間優(yōu)化結(jié)果

表7 Inspiral_100工作流完成時間優(yōu)化結(jié)果

4.3.3 CyberShake工作流調(diào)度實(shí)驗(yàn)結(jié)果及分析

表2、表3、表4記錄了在CyberShake模型下任務(wù)量分別為30，50和100時各算法完成時間的Min、AVG和MAX值.

表8 CyberShake_30工作流完成時間優(yōu)化結(jié)果

表9 CyberShake_50工作流完成時間優(yōu)化結(jié)果

表10 CyberShake_100工作流完成時間優(yōu)化結(jié)果

從上面的表格可以看出,ABC和MA在任務(wù)量為30和50的時候，完成時間都相對較短.例如，在表8中，ABC和MA的最小完成時間和平均完成時間在所有算法中是最短的.在表9中ABC的平均時間性能更是比SFLA提高了25%.而在任務(wù)量變?yōu)?00時，ABC和MA平均完成時間較除BA外其他算法最長，算法時間性能不再突出.只有CRO在各任務(wù)量情況下，其完成時間始終保持相對較短，時間性能穩(wěn)定.

4.3.4 工作流調(diào)度的MinMakespan值結(jié)果及分析

表11對比了不同模型下各算法的MinMakespan值.

表11 任務(wù)數(shù)量100時工作流調(diào)度的MinMakespan值

從上面的表格可以看出,在不同的模型下，ABC和ACO的完成時間始終相對較長.如圖11，在Inspiral模型下，ABC的MinMakespan值更是達(dá)到7 230.14.而SFLA、PSO和CS的在不同模型下的完成時間都比較不穩(wěn)定，例如，SFLA在CyberShake 模型下的完成時間較所有算法除CRO外較短，而在Inspiral模型下，其完成時間達(dá)到了6 500以上.只有CRO，在三種工作流模型條件下，其完成時間較其他算法始終較短，時間性能更為良好和穩(wěn)定.

5 結(jié)論

通過對以上九種算法在Montage,Inspiral和CyberShake三種不同工作流模型和不同任務(wù)量的情況下完成時間的實(shí)驗(yàn)數(shù)據(jù)可以看出：混合蛙跳算法、蟻群優(yōu)化算法和粒子群算法的完成時間相對較小，但卻在不同任務(wù)量和不同工作流模型下表現(xiàn)不穩(wěn)定.只有化學(xué)反應(yīng)算法無論是在不同的任務(wù)量條件下，還是在不同的工作流模型條件下，無論是極端的最值時間，還是平均時間，都相對較短.可以說，在完成時間上，對比其他算法，化學(xué)反應(yīng)算法最為高效和穩(wěn)定.