宋 三 華

(黃淮學院 信息工程學院， 河南 駐馬店 463000)

0 引 言

云計算旨在以服務形式通過互聯(lián)網按需向用戶提供軟硬件和各類IT資源[1]。其主要特點包括：更大規(guī)模的數據應用、基于硬件的虛擬化技術、資源提供的可擴展性以及資源提供的按需性[2]。在大數據背景下，云計算將面臨更大規(guī)模和計算復雜性應用場景，科學工作流調度問題即是該場景下一種主要且熱門的研究領域。工作流通常體現為擁有數據依賴關系連接而成的有序任務集合。工作流調度問題即是通過優(yōu)化具體的調度目標實現可用云資源與工作流各任務間的映射與執(zhí)行，同時滿足用戶對時間和費用上的QoS需求[3-4]。

相關研究中，文獻[5]中提出的HEFT是一種異構最快完成時間工作流調度算法，旨在通過賦予任務不同的優(yōu)先級，最小化工作流的總調度時間。文獻[6]中提出基于預算約束的異構最快完成時間算法BHEFT，該算法是HEFT的擴展，考慮了任務調度時的最優(yōu)預算約束問題。然而，以上工作忽略了：由于云的市場化特征，為了優(yōu)化經濟收益，必須尋找有效可行解的同時得到代價和時間均衡的調度解。文獻[7]中提出動態(tài)工作流調度算法，算法目標是尋找最經濟和實用的資源，并利用任務合并的方式將其調度至單一資源。然而，算法找到的是低代價解而不是最優(yōu)均衡解。文獻[8]中雖然可以得到滿足用戶QoS的調度解，但僅考慮了單一類型云資源，忽略了云資源的異質性和彈性。

智能搜索算法是工作流調度的另一種求解方法。文獻[9]中提出基于PSO的工作流調度算法。算法目標與本文目標相同，但該算法的問題在于：① 粒子編碼中，以資源索引表示粒子位置。然而，資源索引本身是無法體現云資源特征的，這會導致粒子朝個體最優(yōu)和全局最優(yōu)的進化過程可以無法得到更優(yōu)解；② 在調度規(guī)模變大時，該算法可能很快收斂于局部最優(yōu)解；③ 當截止時間約束較緊密時，PSO可能無法找到可行解。

為了解決緊密截止時間約束下智能算法無法得到可行解的問題，設計基于動態(tài)目標的改進粒子群調度算法：當種群染色體無法找到可行解時，以執(zhí)行時間為優(yōu)化目標直到一個染色體找到可行解。如果至少有一個染色體找到可行解，則設置執(zhí)行代價為優(yōu)化目標，并讓染色體進一步進化尋找全局最優(yōu)解。

1 問題描述

1.1 調度模型

以有向無循環(huán)圖DAG表示工作流W=(T,D)，T={T0,T1,…,Tn}表示工作流任務集合，D={(Ti,Tj)|Ti,Tj∈T}表示有向圖的邊，即依賴關系。如圖1所示為一種工作流示例，圖的邊上的數值表示有向邊的權重，在工作流任務調度環(huán)境中，可定義為運行于不同的資源上的父任務(前驅任務)與子任務(后繼任務)間的數據傳輸時間。同時，在圖1所示工作流結構中，t1表示工作流的入口任務，t9表示工作流的出口任務。執(zhí)行工作流任務的資源集合定義為Rini，可以被租用進行任務執(zhí)行。

圖1 工作流示例圖

定義工作流總執(zhí)行代價TEC和總執(zhí)行時間TET分別為：

TET=max{ETti:ti?T}

(1)

(2)

式中：ETti表示任務ti終止執(zhí)行的時間；Crj表示任務租用資源rj的單位時間代價；LSTrj表示資源rj的租用開始時間；LETrj表示資源rj的租用結束時間。LET可以計算為最遲完成任務的結束時間，TEC為每個資源的租用代價之和，而單個資源的租用代價則為資源單位時間代價與租用時間的乘積。

工作流的調度目標是尋找滿足截止時間約束的代價最小化調度方案，即尋找最小化TET，同時TET必須滿足截止時間約束，該模型可形式化為：

(3)

1.2 PSO算法

粒子群優(yōu)化算法(Paticle Swarm Optimization, PSO)是一種基于動物成群行為的進化計算技術，其核心是基于粒子概念的隨機最優(yōu)化方法，已廣泛應用于最優(yōu)化問題求解中[10]。在PSO中，一個粒子表示一個個體，可以在問題空間中移動，代表一個最優(yōu)化問題的候選解。在給定的時間點，粒子的運動通過矢量速度定義。每個粒子由其位置與速度表示，以pbest表示粒子找到歷史最優(yōu)解，gbest表示整個種群找到的歷史最優(yōu)解，每個粒子有一個適應度，在算法的每一步，粒子通過速度和位置的改變朝著pbest和gbest位置進行進化，算法不斷迭代直到滿足預定的最大迭代次數為止。在每次迭代中，粒子的位置與速度通過以下公式更新：

xi(t+1)=xi(t)+vi(t)

(4)

c2r2(x*(t)-xi(t))

(5)

2 TDO-PSO算法設計

本文設計的TDO-PSO算法具有與傳統(tǒng)PSO相似的算法結構，不同之處在于進化過程中，TDO-PSO使用了一種動態(tài)目標策略以自適應的評估染色體。算法流程如圖2所示。

2.1 問題編碼

通過PSO求解問題包括兩個關鍵步驟：一是定義問題的編碼方式，即如何表示種群；二是定義粒子優(yōu)劣的度量方式，即適應度函數。為了定義問題的編碼方式，需要建立粒子的含義和維度。對于本文的調度場

圖2 TDO-PSO算法流程

維度等同于工作流任務的數量。粒子的維度決定了用來定義空間中粒子的坐標系統(tǒng)，如：一個二維粒子的位置可以二維坐標標明，三維粒子的位置由三維坐標標明。如圖3中，粒子代表擁有9個任務的工作流，粒子的維度為9，其位置由9個坐標決定，即1～9。

圖3 粒子位置編碼

粒子的移動范圍由執(zhí)行任務的可用資源量決定，因此，坐標值的變化范圍處于0至初始狀態(tài)時資源數量之間?；诖?，在粒子位置中每個坐標值的整數部分則對應于資源索引，即表示以特定坐標定義的分配至任務的計算資源。通過這種方式，粒子位置可編碼為任務與資源間的映射。以圖3為例，資源池中有3個資源，則每個坐標值的取值范圍為[0,3]，坐標1對應任務1，其值1.2表明任務分配至資源1；坐標2對應任務2，其值1.0表明任務2分配至資源1；依次類推。

由于適應度函數用來評價潛在解的質量，故需要反映調度問題的目標?；诖耍m應度函數應被最小化，且其值為在由粒子位置導出的調度方案時的總執(zhí)行代價TEC。

2.2 個體選擇策略

TDO-PSO算法中，利用輪盤賭策略選擇染色體進入下一種群世代中?；静呗允牵哼m應度越大的染色體被選擇的概率越大。由于本文的工作流調度目標是最小化工作流執(zhí)行代價，利用1/TEC評估染色體的適應度，可形式化為：

fitness=1/TECi

(6)

(7)

2.3 個體交叉操作

每個染色體進化交叉的概率設置為Pc，如果算法產生隨機數Random(0,1)

圖4 染色體交叉

2.4 個體變異操作

染色體的每個坐標均擁有Pm的概率進行變異。變異通過產生兩個隨機數m和v，然后，對應于坐標m上的值將變異為v。變異操作同樣可以豐富種群個體多樣性。如圖5所示為變異操作示例。

圖5 染色體變異

2.5 Keep-the-Best策略

為了避免交叉和變異操作過程中丟失最優(yōu)染色體，算法使用了一種個體選取之前的最優(yōu)解保存策略。TDO-PSO算法中，定義一個變量保存全局最優(yōu)染色體，在每一代中，如果最優(yōu)染色體優(yōu)于當前的全局最優(yōu)解，則更新全局最優(yōu)染色體；否則，全局最優(yōu)染色體將取代當前世代中的最差染色體。該策略可以實現對TDO-PSO算法的加速收斂。

2.6 動態(tài)目標策略

工作流調度過程中，當截止時間約束較緊密時，算法可能在第一代中就無法找到一個可行解，且如果利用式(3)評估個體的適應度，算法可能很難找到可行解。而該問題在傳統(tǒng)PSO中顯得更為嚴重，因為第一代無法找到可行解直接導致不存在gbest和pbest，PSO算法此時是無法運行的。而當找到的解均不是可行解時，擁有更低的全局約束違例的解將選取為最終解，這意味著如果獲得的解不滿足截止時間約束，擁有更小TET的解會選取為最終解。

與傳統(tǒng)PSO的處理方式不同，本文設計了一種基于動態(tài)目標的調度策略。如果得到的染色體無法滿足截止時間約束，則將其適應度定義為1/1 000 000，該值遠遠小于可行染色體個體的適應度。如果種群中所有染色體的適應度均為1/1 000 000，則表明沒有染色體能找到可行解，TDO-PSO算法將TET設置為最優(yōu)目標直到一個染色體找到可行解。然后，TDO-PSO利用式(3)評估染色體適應度。通過這種多目標調度，可以使TDO-PSO更可能滿足緊密的截止時間約束。并且，TDO-PSO能夠通過設置不同的優(yōu)化目標，利用不同的Pc和Pm值使得算法獲得更好的自適應性。找到可行解之后，算法運行至4 000代，找到最終的最優(yōu)解。

2.7 TEC與TET計算

由于以式(3)作為粒子適應度的評估標準，因此，需要從粒子位置中得到TET和TEC，并計算適應度函數。為了得到TEC和TET，需要知道任務在每個資源上的執(zhí)行時間，令該時間存儲于數組exetime中，exetime[i][j]則代表任務ti在資源rj上的執(zhí)行時間。然而，當父任務與其子任務在不同資源上執(zhí)行時，兩者之間的數據傳輸同樣需要花費時間。令該時間存儲于數組transfertime中，transfertime[i][j]代表任務ti與tj間的數據傳輸時間。如圖6所示給出了對應于圖1的傳輸時間transfertime和exetime。

(a) 執(zhí)行時間矩陣 (b) 數據傳輸時間矩陣

圖6 傳輸時間和執(zhí)行時間矩陣

基于以上的傳輸時間和執(zhí)行時間矩陣，并依據圖3和圖6，可以得到圖1中的工作流任務調度示意圖，如圖7所示。

圖7 工作流調度示例

算法1給出了TEC和TET的計算過程。算法首先初始化TET、TEC和R，其中，R表示租用的資源集合，初始化為空。然后，算法將迭代訪問每個坐標i。對于每個任務ti，根據pos[i]得到其運行的資源，ti的開始時間STti由兩個因子決定，在rpos[i]可用之前需要等待，標記為LETrpos[i]。而如果ti擁有父任務ta，則ti需要等待直到ta完成為止。執(zhí)行時間exe與ti傳輸數據至其子任務的時間transfer之和，即為ti的處理時間PTti。ETti為ti的結束時間，等于STti與PTti之差。如果rpos[i]未被租用，其租用開始時間即為LSTrpos[i]，而租用結束時間LETrpos[i]即為任務ti的結束時間。最后，算法可以式(1)和(2)計算工作流調度的TET和TEC。

算法1TEC與TET計算

1. input: array pos[|T|] represents a solution

2. output: TEC and TET

3. calculating_TEC_TET()

4.R=NULL,TEC=0,TET=0

5. for eachi=0 toi=|T|-1

6. iftihas no parents

7.STti=LETrpos[i]

8. else

9.STti=max(max{ETtp:tp∈parents(ti)},LETrpos[i]

10. end if

11. exe=exetime[i][pos[i]],transfer=0

12. for each child tasktcofti

13. iftcis mapped torpos[i]

14. transfer+=transfertime[i][c]

15. end if

16. end for each

19. ifrpos[i]?R

20. LSTrpos[i]=STti

21.R=R∪{rpos[i]}

22. end if

23. LETrpos[i]=ETti

24. calculate TEC according to equation (1)

25. calculate TET according to equation (2)

3 仿真實驗

利用WorkFlowSim[11]進行仿真實驗，實驗中，資源rj的價格Cj隨機產生于[1,5]中，如式(8)所示。對于任務ti，執(zhí)行時間exetime[i][j]由兩個因素決定。由于擁有高代價的資源執(zhí)行任務時效率更高，利用6-Cj表示該因子。設置exetime[i][j]為式(9)，設置transfertime[i][child(i)]為random(0,1)，分別表示為：

Cj=Random(1,5)

(8)

exetime[i][j]=(6-Cj)×0.5+

Random(0,1)×0.5

(9)

transfertime[i][child(i)]=Random(0,1)

(10)

算法2給出了工作流任務拓撲結構的隨機式產生算法過程，考慮到任務執(zhí)行的順序性，對于任務ti的拓撲層次，child(i)>i。對于ti，設置Pchild表示任務tk作為ti子任務的概率。為了產生相對均衡的任務拓撲結構，Pchild會隨著i增加而增加。

算法2工作流任務拓撲結構形成

1. Fori=0 to |T|-1

2.Pchild=0.1+0.4×(i/|T|)

3. fork=ito |T|

4. if random(0,1)

5. settkas the child ofti

6. end if

7. end for

8. end for

實驗中，設置3種不同規(guī)模的數據集。首先比較傳統(tǒng)PSO與使用動態(tài)目標策略的TDO-PSO算法的性能。然后，比較不同數據規(guī)模場景下同為智能算法的GA與TDO-PSO的性能。

由于TDO-PSO和GA均需要進化多代數才可以找到可行解，將其命名為搜索代數(FGEN)，并且，如果FGEN>100 000，則認為算法無法找到可行解，否則，如果算法運行未超過4 000代，則選取最小TEC為最優(yōu)解。定義Time為兩種算法的計算時間，單位為s。筆者設置了不同等級的截止時間約束對GA和TDO-PSO的FGEN和TEC進行比較。

PSO的相關參數設置如下：c1=c2=2，w=0.5，種群規(guī)模為100。TDO-PSO的種群規(guī)模也設置為100，對于TDO-PSO的交叉與變異概率，由于在不同階段使用了動態(tài)目標策略，如果算法處于尋找可行解階段，則設置式(3)為最優(yōu)化目標，Pc=0.15，Pm=0.008；否則，算法就處于4 000代內的尋找最小TET階段，此時，設置TET為最優(yōu)化目標，Pc=0.8，Pm=0.002。而且，由于隨機化的原因，TDO-PSO和PSO算法均在給定的實例上運行30次并取平均值作為性能評估依據。

(1) PSO與TDO-PSO比較。如前所述，TDO-PSO中的動態(tài)目標策略可滿足緊密截止時間約束，本部分將比較PSO與TDO-PSO可滿足的最緊密截止時間大小關系，以顯示該策略對性能的影響。

如表1所示，可以看出，動態(tài)目標策略在截止時間約束下的代價最小化場景下，可以使TDO-PSO算法更好的適應于更緊密的截止時間約束，并且，隨著調度規(guī)模的增加，從最后一列的(PSO-TDO-PSO)/PSO的值可以看出，TDO-PSO的優(yōu)勢將體現得更加明顯。

表1 算法的最緊密截止時間比較

(2) GA與TDO-PSO比較。

實驗1小規(guī)模數據測試。小規(guī)模數據場景下，設置工作流擁有50個任務，可租用資源數為15種，設置3種截止時間約束，分別為80、100和120。實驗結果如表2和圖10所示。

表2 小規(guī)模數據場景下的FGEN與TEC

圖10 小規(guī)模數據場景下Deadline=120時的TEC

可以看出，在不同的截止時間約束下，TDO-PSO始終可以得到小于GA的TEC，而且，TDO-PSO的計算時間也始終小于GA。FGEN數值表明GA和TDO-PSO兩種算法至少找到一個可行解的運行代數。當截止時間約束較大時，在FGEN=0時，GA和TDO-PSO均可以在初始時得到可行解。當截止時間為100時，GA在得到可行解時可能擁有比TDO-PSO更快的收斂速度。然而，當截止時間變得更緊密時(80)，GA將無法找到可行解，但TDO-PSO依然可以在743代時找到可行解。

實驗2中規(guī)模數據測試。中規(guī)模數據場景下，設置工作流擁有75個任務，可租用資源數為25種，設置3種截止時間約束，分別為120、200和280。實驗結果如表3和圖11所示。

表3 中規(guī)模數據場景下的FGEN與TEC

可以看出，在不同的截止時間約束下，TDO-PSO性能優(yōu)于GA，不僅擁有更低的TEC，而且TDO-PSO的計算時間也小于GA。同時，圖11中的TDO-PSO的曲線彎度表明其擁有比GA更快的收斂速度。

圖11 中規(guī)模數據場景下Deadline=280時的TEC

(3) 大規(guī)模數據測試。大規(guī)模數據場景下，設置工作流擁有100個任務，可租用資源數為30種，設置3種截止時間約束，分別為200、300和400。實驗結果如表4和圖12所示。

表4 大規(guī)模數據場景下的FGEN與TEC

圖12 大規(guī)模數據場景下Deadline=400時的TEC

可以看出，在不同的截止時間約束下，TDO-PSO在獲得可行解和計算時間等性能方面，同樣是優(yōu)于GA算法的。

綜合以上結果，在小規(guī)模數據測試場景下，GA的收斂可能優(yōu)于TDO-PSO，但隨著數據規(guī)模的增加，TDO-PSO的收斂速度將更快。在三種不同的數據規(guī)模下，TDO-PSO均可以得到比GA更小的TEC，而且隨著數據規(guī)模的增大，兩者性能的差距將更加明顯。在三種不同的數據規(guī)模下，TDO-PSO比GA更能滿足緊密截止時間約束，因此，TDO-PSO在滿足不同用戶需求的情況下，將具有更好的應用性。

4 結 語

為了解決云環(huán)境中的工作流調度代價優(yōu)化問題，提出基于兩階段動態(tài)目標的調度算法TDO-PSO。算法基于截止時間約束的工作流執(zhí)行代價最優(yōu)化模型，設計了一種遺傳進化調度方案求解算法。算法通過兩階段的動態(tài)目標設置，不僅可以保證無法找到可行解時滿足載止時間約束的最優(yōu)執(zhí)行時間方案，而且可以保證擁有可行解時滿足截止時間約束的最優(yōu)執(zhí)行代價方案，這使得TDO-PSO算法可以適應于不同目標的優(yōu)化環(huán)境。

參考文獻(References)：

[1] BUYYA R, YEO S, VENUGOPAL S,etal. Cloud computing and emerging IT platforms: Vision,hype,and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems,2011,25(6):599-616.

[2] LIFKA D, FOSTER I, Mehringer S,etal. XSEDE cloud survey report[R]. Technical report, National Science Foundation, USA, Tech. Rep., 2013.

[3] WU F, WU Q, TAN Y. Workflow scheduling in cloud: a survey[J]. The Journal of Supercomputing, 2015,4(3):1-46.

[4] 張秋明.基于改進蟻群算法的云計算任務調度[J].電子技術應用,2015,41(2):120-123.

[5] TOPCUOGLU H, HARIRI S, WU M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Trans Parallel Distr Syst, 2012,13(3):260-274.

[6] ZHENG W, SAKELLARIOU R. Budget-deadline constrained workflow planning for admission control[J]. J of Grid Comput.,2013,11(4):633-651.

[7] MAO M, HUMPHREY M. Auto-scaling to minimize cost and meet application deadlines in cloud workflows[C]∥in Proc Int Conf High Perform Comput. Netw: Storage Anal, 2011:1-12.

[8] MALAWSKI M, JUVE G, Deelman E,etal. Cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[C]∥in Proc Int Conf High Perform Comput. Storage Anal, 2012:1-11.

[9] RODRIGUEZ M A, BUYYA R. Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J]. IEEE Trans Cloud Computing. 2014,2(2):222-235.

[10] LI Y H, ZHAN Z H. Competitive and cooperative particle swarm optimization with information sharing mechanism for global optimization problems[J].Information Sciences, 2015,293(1):370-382.

[11] CHEN W, DEELMAN E. WorkflowSim: A toolkit for simulating scientific workflows in distributed environments[C]∥In E-Science (e-Science), IEEE 8th International Conference on. IEEE, 2012:1-8.

[12] 陳 超.改進CS算法結合決策樹的云工作流調度[J],電子科技大學學報,2016,45(6):974-980.

[13] 張 鵬,王桂玲,徐學輝.云計算環(huán)境下適于工作流的數據布局方法[J].計算機研究與發(fā)展,2013,50(3):636-647

[14] 吳國華，馬艷偉.粒子群優(yōu)化的異構多處理器任務調度算法[J].杭州電子科技大學學報，2009(6):4-44.

[15] LI W, WU J, ZHANG Q,etal. Trust-driven and Qo S demand clustering analysis based cloud workflow scheduling strategies[J].Cluster Computing,2014,17(3): 1-18.