何留杰

(黃河科技學(xué)院 現(xiàn)代教育技術(shù)中心， 鄭州 450063)

0 引 言

關(guān)聯(lián)式云任務(wù)即為工作流任務(wù)形式，是科學(xué)研究領(lǐng)域中最常用的應(yīng)用模型。由于云計算可以即付即用的形式提供高性能的計算能力，利用云資源執(zhí)行工作流任務(wù)正成為時下的研究熱點問題。作為數(shù)據(jù)密集型科學(xué)實驗的發(fā)展，工作流調(diào)度問題是應(yīng)用領(lǐng)域中必須面臨的難題。原因在于：工作流的任務(wù)規(guī)模動態(tài)可變，且特征異構(gòu)，對于資源的需求和依賴性也顯示出不確定性。云可以按需提供大范圍實例類型，顯然比傳統(tǒng)的一般分布式計算環(huán)境具有更好的執(zhí)行效率[1]。與傳統(tǒng)工作流不同，科學(xué)工作流規(guī)模更大，任務(wù)的數(shù)據(jù)計算與通信代價更高，其本質(zhì)是實現(xiàn)相互依賴的任務(wù)至資源間的映射，同時要求滿足用戶定義的服務(wù)質(zhì)量(Quality of Service, QoS)約束(截止時間或預(yù)算)。傳統(tǒng)的工作流調(diào)度算法僅側(cè)重于考慮優(yōu)化執(zhí)行效率(執(zhí)行時間)，未考慮資源代價，而云計算是商業(yè)化環(huán)境，其資源使用是有償付費的，資源能力越高，價格越高，此時，使用不同資源及不同調(diào)度方案得到的執(zhí)行代價和時間是不同的[2]。因此，云環(huán)境中的工作流調(diào)度需要同步考慮用時間和代價問題。本文將重點研究用戶預(yù)算約束下的任務(wù)調(diào)度優(yōu)化問題，并側(cè)重于從滿足約束的同時，提高調(diào)度效率和調(diào)度成功率的角度，實現(xiàn)工作流任務(wù)與資源實例間的有效映射。

1 相關(guān)研究

云計算環(huán)境中，截止期限和預(yù)算等QoS約束下的工作流調(diào)度問題是研究熱點問題。多數(shù)截止期限約束的調(diào)度算法主要思想是如何將用戶定義的期限在工作流任務(wù)或?qū)哟伍g進行分布[3-4]，更多強調(diào)調(diào)度效率，忽略調(diào)度成本。而云環(huán)境是即付即用的資源提供環(huán)境，相比而言，預(yù)算約束是其更應(yīng)該考慮的約束條件。該領(lǐng)域中的相關(guān)研究大致可分為兩類：代價優(yōu)化和預(yù)算約束。

(1) 代價優(yōu)化。文獻[5]中在經(jīng)典異構(gòu)最早完成時間算法[6]的基礎(chǔ)上改進設(shè)計了一種代價感知啟發(fā)式調(diào)度算法，該算法首先構(gòu)建了任務(wù)優(yōu)先級列表，然后按優(yōu)先級將任務(wù)調(diào)度至代價效率最高的資源上。然而，算法僅考慮了一種資源類型和價格模型，顯然不符合云資源的牲。文獻[7]中提出一種安全與預(yù)算感知的工作流調(diào)度算法，試圖最小化工作流執(zhí)行時間。然而，算法在超過預(yù)算時無法做到有效控制，因此，應(yīng)屬于代價優(yōu)化一類策略。文獻[8]中提出一種優(yōu)化有效的啟發(fā)式調(diào)度算法，然而，算法所考慮的代價模型僅考慮了CPU周期的利用數(shù)量，該模型中總代價為所有任務(wù)的代價之和，而這與常規(guī)的云資源提供環(huán)境(如Amazon)是完全不一致的，云資源是按最小周期時間索取費用，即使實例僅使用最小周期的一部分時間。

(2) 預(yù)算約束。文獻[9-10]中在HEFT基礎(chǔ)上設(shè)計了預(yù)算約束異構(gòu)最早完成時間算法(Budget Heterogenous Earliest Finish Time, BHEFT)，算法引入當(dāng)前任務(wù)預(yù)算因子在未調(diào)度任務(wù)間進行剩余預(yù)算的分布，該分配方式不同于本文，BHEFT是逐個任務(wù)的進行剩余預(yù)算的分布。而文獻[10]中的任務(wù)選擇則是基于升秩排序。本文中，由一組任務(wù)組成的約束關(guān)鍵路徑(Constrainted Critical Path,CCP)被選擇同時調(diào)度以降低通信與數(shù)據(jù)傳輸代價。文獻[11]中提出一種預(yù)算約束的包任務(wù)調(diào)度算法，并使用了任務(wù)間存在優(yōu)先性的假設(shè)，這可能導(dǎo)致任務(wù)間的干擾、延遲及重分配問題。本文模型不同于文獻[11]，所使用的任務(wù)模型為工作流模型，且對約束有更少的依賴性。文獻[12]中提出一種預(yù)算感知的工作流回溯調(diào)度算法，其資源利用了可分解的資源模型。然而，實際的云資源通過會使用至少一小時的帳單周期模型，過小的資源利用周期不利于資源方的經(jīng)濟收益。文獻[13]中提出一種預(yù)算約束的多工作流調(diào)度算法，其預(yù)算是以正比例的方式在不同工作流間進行分配，同樣不同于本文的工作。文獻[14-15]中提出預(yù)算約束的端到端最小延時調(diào)度算法，在進行任務(wù)的初始調(diào)度后，算法將所有關(guān)鍵任務(wù)利用關(guān)鍵貪婪算法進行了重新調(diào)度，與本文研究有些類似，但在資源選擇方面并未作出優(yōu)化。

2 系統(tǒng)模型

2.1 工作流模型

有向無循環(huán)圖(Directed Aclyce Graph,DAG)是工作流結(jié)構(gòu)的常用表示模型，將工作流定義為圖G=(T,E)，T={t0,t1,…,tn}為圖頂點代表的任務(wù)集合，E={ei,j|ti,tj∈T}為圖的有向邊集合，代表任務(wù)ti與tj間的數(shù)據(jù)或控制依賴。邊ei,j∈E表示兩個任務(wù)ti與tj間的有向邊，ti,tj∈T，代表兩個任務(wù)間的優(yōu)先順序約束，其具體含義是：僅當(dāng)任務(wù)ti執(zhí)行完成后并收到ti的所有數(shù)據(jù)后，任務(wù)tj才可以開始執(zhí)行。換言之，任務(wù)ti是tj的父任務(wù)，tj是ti的后繼或子任務(wù)。單個任務(wù)可擁有一個或多個父任務(wù)和子任務(wù)。直到其所有父任務(wù)完成后，子任務(wù)ti才可以開始執(zhí)行。

2.2 相關(guān)定義

任務(wù)ti在執(zhí)行時間最短的實例上的最早開始時間(Earliest Start Time, EST)定義為：

(1)

式中，wtj表示任務(wù)tj在速度最快的實例上的執(zhí)行時間。

ECT(ti)為作務(wù)ti在所有實例上最早完成時間ECT，定義為：

ECT(ti)=EST(ti)+wti

(2)

在實例pj上執(zhí)行任務(wù)ti的代價為：

(3)

執(zhí)行工作流的所有任務(wù)的總代價為：

(4)

約束關(guān)鍵路徑CCP：關(guān)鍵路徑(Critical Path,CP)為工作流結(jié)構(gòu)中從入口任務(wù)至出口任務(wù)間的最長路徑。關(guān)鍵路徑的長度|CP|為任務(wù)的計算代價與通信代價之和，可考慮為工作流調(diào)度的下界。而僅包含就緒任務(wù)的任務(wù)集合構(gòu)成一個約束關(guān)鍵路徑CCP[16]。當(dāng)所有前驅(qū)任務(wù)已完成且任務(wù)要求的數(shù)據(jù)已到達時，視任務(wù)為就緒任務(wù)。

2.3 云服務(wù)模型

假設(shè)云供應(yīng)商可提供無上限的異構(gòu)實例數(shù)量：

P={p0,p1,…,pn}

式中，n為實例類型的索引。

3 WTSBC算法設(shè)計

基于預(yù)算約束的工作流任務(wù)調(diào)度算法(Workflow Tasks Scheduling Based on Budget Constraint,WTSBC)的目標(biāo)是在滿足預(yù)算約束的前提下最小化執(zhí)行時間。同時，由于任務(wù)調(diào)度中任務(wù)層次的重要性，算法需要將預(yù)算在不同層次中進行重新分配。具體來說，WTSBC算法包括以下4個階段：

(1) 工作流劃分。工作流根據(jù)任務(wù)間的依賴性進行層次劃分。

(2) 預(yù)算分配。用戶定義的工作流執(zhí)行預(yù)算在每個工作流層次間進行分配。

(3) 任務(wù)選擇。根據(jù)任務(wù)優(yōu)先級，選擇約束關(guān)鍵路徑上的任務(wù)集，作為執(zhí)行的就緒隊列。

(4) 實例選擇。選擇滿足可用預(yù)算的實例執(zhí)行任務(wù)。

3.1 工作流劃分

工作流劃分過程是通過分配任務(wù)至不同層次最大化任務(wù)并行執(zhí)行的程度，同一層次中的任務(wù)相互之間不存在依賴性，可并行執(zhí)行。因此，每一層次中任務(wù)可考慮為包含獨立任務(wù)集的包任務(wù)。

定義任務(wù)ti的層次為一個整數(shù)，代表任務(wù)ti至工作流出口任務(wù)間所有路徑的邊的最大值。令NL為包任務(wù)中一個任務(wù)的層次值，可表示為：

(5)

式中，succ(ti)為任務(wù)ti的直接后繼任務(wù)集合。以自底向上的方式將所有任務(wù)劃分至不同的層次，如圖1中層次1～5。對于出口任務(wù)而言，其層次值則恒為1。

然后，所有任務(wù)依據(jù)其層次值可歸于任務(wù)層次集TLS中，并表示為：

TLS(l)={ti|NL(ti)=l}

(6)

式中，l為整數(shù)層次值，且l∈[1,…,NL(tentry)]。

3.2 預(yù)算分割

預(yù)算分割的主要思想是將用戶定義的工作流預(yù)算在工作流層次間進行重新分配，并在考慮該層次所分配的可用子預(yù)算的前提下將第個任務(wù)調(diào)度至實例。本文提出兩種預(yù)算分割的方法，包括：

(1) 區(qū)域分割法Area。由于工作流的結(jié)構(gòu)會對調(diào)度結(jié)果產(chǎn)生實質(zhì)影響，該方法聯(lián)合考慮工作流的高度和寬度。Area法重點考慮。①工作流的高度：即每個層次的預(yù)算分割正比于所在層次與入口任務(wù)間的距離；②工作流的寬度：即每個層次的預(yù)算分割正比于所有層次中包含的任務(wù)數(shù)量。

(2) 漏斗分割法All in。該方法將全部預(yù)算賦予工作流入口任務(wù)，減去相應(yīng)調(diào)度費用后，依漏斗模式依次將剩余預(yù)算傳遞至下一層次。

3.3 任務(wù)選擇

工作流基于約束關(guān)鍵路徑CCP選擇執(zhí)行任務(wù)。為了搜索工作流中所有的約束關(guān)鍵路徑，利用文獻[4]中的介紹的升秩排序upward rank和降秩排序downward rank方法，并分別對兩種方法作如下改進：

改進升秩排序

(7)

改進降秩排序

(8)

式中，AETi和ACTi分別為任務(wù)ti的平均執(zhí)行時間和平均通信時間。

改進的升秩和降秩排序方法整合了任務(wù)前驅(qū)或后繼的通信時間，替代原始方法僅選擇最大值的做法。在改進方法中，擁有越高出度或入度的任務(wù)，將擁有更高的優(yōu)先級，具有更大概率被優(yōu)先執(zhí)行，而在下一約束關(guān)鍵路徑上的更多任務(wù)也將被考慮為就緒任務(wù)。WTSBC算法根據(jù)Mrankup(ti)+Mrankdown(ti)定義任務(wù)優(yōu)先級，所有任務(wù)首先根據(jù)該值進行排序，擁有最高值的任務(wù)被選擇為第一個關(guān)鍵路徑。關(guān)鍵路徑搜索算法如下：

算法1關(guān)鍵路徑搜索

1. procedure FindCP(DAG G)

2. For all taskti∈G do//遍歷工作流的所有任務(wù)

3. calculate rankup, rankdownand ranksum//計算各個任務(wù)的升秩和降低值及其和

4. end for

5. CPlist←?//初始化關(guān)鍵路徑列表為空

6. while there is an univisited task in G do//尋找未訪問任務(wù)

7.ti←biggest ranksum//尋找最大秩值和

8. CP←?//置關(guān)鍵路徑為空

9. whiletiis not null do

10. addtito CP//添加任務(wù)ti至關(guān)鍵路徑

11.ti←maxtj∈pred(ti)(ranksumtj)//尋找最大父任務(wù)秩值和

12. end while

13. add CP to CPlist//添加關(guān)鍵路徑至CP列表

14. end while

15. end procedure

3.4 實例選擇

實例選擇階段的目標(biāo)是選擇最合適的實例執(zhí)行CCPs。由于CCP上所有任務(wù)執(zhí)行于同一實例上，可以避免任務(wù)間的通信代價。該階段首先根據(jù)以下公式計算每個任務(wù)在每個實例類型上的執(zhí)行時間和執(zhí)行代價，并形成兩個集合Cost和Time：

(9)

(10)

式中，Cbest為在所有實例上執(zhí)行當(dāng)前CCP的最小代價。

在實例pj上執(zhí)行當(dāng)前CCP的代價為C(CCPi,pj)。式(10)中，subBudgetCCPi為對于一個CCP中在不同層次上所有任務(wù)所分配的子預(yù)算subBudget之和，定義為

(11)

在Time集合中，在實例pj上執(zhí)行當(dāng)前CCP需要的時間為ECT(CCPi,pj)的函數(shù)(式(11))。ECT為一個CCP在單個實例上完成執(zhí)行的最早時間(單個任務(wù)的ECT定義為式(2))。在所有實例上執(zhí)行CCPi的最大與最小時間分別為ECT(max)和ECT(min)。

為了尋找最佳實例，算法利用如下式的Time-Cost調(diào)整因子：

(12)

擁有最高TCAF值的實例將作為執(zhí)行當(dāng)前CCP的最佳實例侯選。當(dāng)分配于層次l的總預(yù)算已經(jīng)花費完(即subBudgetCCPi=0時)但仍然有未調(diào)度任務(wù)時，對于式(9)，有：

(13)

因此，由于沒有預(yù)算盈余，無法開戶一個新的實例。此時，式(12)也等于0。并且，如果式(10)變?yōu)樨撝担瑒t表明在所選實例上的執(zhí)行代價高于可用子預(yù)算subBudgetCCPi。

實例提供后，用戶需要支付整個帳單周期的費用，即使任務(wù)在周期結(jié)束前完成。一種降低任務(wù)執(zhí)行代價的方法是繼續(xù)利用已支付實例的剩余能力執(zhí)行任務(wù)，如此，這類任務(wù)的執(zhí)行代價即為0。WTSBC算法將利用這類已支付的剩余能力執(zhí)行就緒任務(wù)，以零代價方式降低任務(wù)執(zhí)行時間。

將單個CCP分配至一個實例后(代價為C(CCPi,pj))，需要更新每個層次的剩余預(yù)算。在工作流為最早任務(wù)分配更高的預(yù)算通?？梢缘玫礁〉膱?zhí)行跨度。算法2給出了預(yù)算的更新過程。

算法2更新剩余預(yù)算

1. procedure UPDATE BUDGET(CCP,cost)

2. while |CCP| and cost>0 do

3.ti←last task in CCP

4. removetifrom CCP

5. LB←subBudget(l)ti∈TLS(l)

6. if LB>cost then

7. LB←LB-cost

8. cost←0

9. end if

10. end while

11. end procedure

WTSBC算法的一個重要步驟是將未使用的剩余預(yù)算傳遞至下一層次繼續(xù)使用。定義剩余層次預(yù)算SLB為層次l的所有任務(wù)調(diào)度后剩余的費用預(yù)算，表示為：

(14)

剩余預(yù)算將傳遞至下一層次l+1。

3.5 預(yù)算分割算例

本節(jié)以一個實例展示預(yù)算在不同層次的分割情況。圖1所示為一個包括10個任務(wù)的工作流結(jié)構(gòu)圖。圖中左欄信息為通過式(5)計算的層次值，右欄信息為以出口任務(wù)為起始點在每個層次中包含的任務(wù)編號。該算例中，最大層次數(shù)Nmax=5，預(yù)算為165。

(1) 高度。每個層次分配一個相對其工作流高度的加權(quán)預(yù)算值，計算為

預(yù)算因子BF計算為

圖1 工作流示例

舉例層次4包含任務(wù)B和C，分配的預(yù)算值為

4×BF=4×11=44

(2) 寬度。每個層次依據(jù)對應(yīng)層次中任務(wù)數(shù)量得到其預(yù)算分配：

舉例包含兩個任務(wù)的層次4分配的預(yù)算為

2×BF=4×16.5=33

(3) 區(qū)域。該方法中，每個層次的預(yù)算分配為高度和寬度方法之和，計算為

預(yù)算因子BF計算為

預(yù)算根據(jù)圖1中右欄數(shù)字之和進行分配。

舉例層次3的預(yù)算分配為

(4+5+6+7)×BF=22×3=66

(4) 漏斗分配Allin?？傤A(yù)算分配至層次5，調(diào)度該層次的所有任務(wù)后，剩余預(yù)算傳遞至下一層次。

表1是圖1所示工作流所有層次的預(yù)算分配。

表1 不同分割方法的層次預(yù)算

4 仿真實驗

4.1 實驗配置

云可以不同的價格提供不同能力的CPU、內(nèi)存、存儲和網(wǎng)絡(luò)帶寬實例。本文利用Amazon彈性計算云的資源模型，其實例可按需提供。價格模型利用即付即用的最小帳單周期模型。該價格模型下，如果實例僅被利用1 min，用戶同樣支付1 h的帳單費用。該實例的代價和類型如表2所示。

表2 實例類型

仿真場景為包含6個不同實例類型構(gòu)建的一個數(shù)據(jù)中心模型，實例特征基于Amazon EC2(見表2)。實例間的平均帶寬固定設(shè)置為20 MB/s。EC2單元處理能力以每秒進行的百萬浮點運算次數(shù)MFLOPS衡量。理想云環(huán)境中，資源提供不存在延時，但是，某些因素可能導(dǎo)致時間上的延時，如：操作系統(tǒng)、實例類型、數(shù)據(jù)中心的區(qū)域地點和同時請求的資源數(shù)量等因素，均可能導(dǎo)致資源啟動時間上的延時。因此，仿真為了貼近實際云場景，基于EC2中的測試數(shù)量設(shè)置97sec的實例啟動時間。

利用3種常見的數(shù)據(jù)密集型科學(xué)工作流應(yīng)用：CyberShake、Montage和LIGO，真實負載狀況評估算法性能。實驗中將預(yù)算由松至緊進行設(shè)置，同時統(tǒng)計調(diào)度成本和成功率情況。另外，令最快調(diào)度FS為基準(zhǔn)調(diào)度方案，基準(zhǔn)調(diào)度為忽略代價得到的最快可能執(zhí)行時間，計算為

(15)

定義預(yù)算為最快調(diào)度的函數(shù)，表示為

budget=α×FS, 1<α<6

(16)

預(yù)算因子α的取值從1開始(考慮為最緊約束，對應(yīng)于最快調(diào)度)，遞增至6(考慮為最松約束)。

Amazon EC2實例在提供時間內(nèi)按1 h的帳單周期支付費用。同時，為了比較不同規(guī)模工作流下的性能，為工作流分別配置50、100、200、500和1 000個任務(wù)。利用Pegasus工作流發(fā)生器創(chuàng)建前文的三種科學(xué)工作流結(jié)構(gòu)，并利用CloudSim實現(xiàn)調(diào)度算法，完成算法仿真。

4.2 結(jié)果分析

本節(jié)實現(xiàn)了預(yù)算分割方法分別為Area和All in時的任務(wù)調(diào)度算法，分別命名為WTSBC-Area和WTSBC-All in。并且選擇預(yù)算約束異構(gòu)最早完成時間算法BHEFT[10]和基于關(guān)鍵任務(wù)的貪婪算法(Modified Critical Tasks Scheduling,MED-CC)[15]作為比較算法，兩種算法均是考慮預(yù)算約束的眾多代表性云工作流調(diào)度算法之一。圖2和圖3分別為不同算法在3種數(shù)據(jù)密集型工作流中的得到的執(zhí)行跨度makespan和調(diào)度成功率。預(yù)算和執(zhí)行跨度是評估算法性能的最重要基準(zhǔn)。增加預(yù)算允許調(diào)度系統(tǒng)釋放出擁有更好CPU、內(nèi)存和網(wǎng)絡(luò)帶寬性能的更高性能實例，因此，全局工作流執(zhí)行時間隨著預(yù)算的增加而降低是顯而易見的。

對于執(zhí)行跨度，WTSBC-All in算法在所有測試工作流中均有最好的性能。BHEFT算法以逐個任務(wù)的方式進行剩余預(yù)算的分布，未考慮任務(wù)間的相關(guān)性，這樣勢必會增加個體任務(wù)的執(zhí)行時間，因此其執(zhí)行跨度是最差的。MED-CC算法試圖以重調(diào)度的方法進行任務(wù)的重新分配，直到滿足預(yù)算約束，這種做法會增加算法的時間復(fù)雜度。WTSBC算法以任務(wù)和預(yù)算層次間分割的方式可以最大化任務(wù)的并行執(zhí)行程度，降低全局工作流任務(wù)的執(zhí)行跨度。

(a) CyberShake工作流

(b) LIGO工作流

(c) Montage工作流

同時，當(dāng)預(yù)算極其受限時(預(yù)算因子相比更小)，BHEFT算法擁有最差的性能。例如：在3種工作流類型的前兩個預(yù)算因子中，BHEFT算法的執(zhí)行跨度幾乎是其他算法的3倍。利用Area和Allin方法進行預(yù)算分割的WTSBC算法均擁有比MED-CC和BHEFT更低的執(zhí)行跨度，且多數(shù)情況下，兩種預(yù)算分割方法間的差異并不大?？傮w來說，WTSBC算法在執(zhí)行跨度性能上全面優(yōu)于MED-CC和BHEFT算法。

調(diào)度成功率可以反應(yīng)算法是否能夠在滿足預(yù)算約束的情況下完成工作流調(diào)度?？梢钥闯觯瑢捤上碌念A(yù)算可以增加調(diào)度成功率，這是由于預(yù)算越多，算法得到的調(diào)度方案滿足預(yù)算的概率將越高。WTSBC-Area算法在Montage工作流的第1個預(yù)算因子中擁有100%失效率，表明該算法此時無法得到調(diào)度方案。搜索合理調(diào)度方案的最差性能發(fā)生在LIGO工作流中，此時MED-CC算法在前3個預(yù)算因子中擁有20%～30%的失效率。

(a) CyberShake工作流

(b) LIGO工作流

(c) Montage工作流

5 結(jié) 語

為了解決關(guān)聯(lián)式云工作流任務(wù)的調(diào)度優(yōu)化問題，本文提出了一種基于預(yù)算約束的調(diào)度算法。算法以一種四階段的方式求解了工作流任務(wù)與實例間的調(diào)度映射解，包括：工作流層次劃分、預(yù)算分割、任務(wù)選擇及實例選擇。重點在預(yù)算分割方法考慮了工作流的結(jié)構(gòu)特征，任務(wù)選擇中則使用了改進的升秩排序與降秩排序之和的任務(wù)優(yōu)先級定義，實例選擇中則考慮將約束關(guān)鍵路徑的任務(wù)調(diào)度至同一實例以降低通信代價。通過3種工作流類型下的仿真實驗測試，結(jié)果表明，所提算法在多數(shù)測試數(shù)據(jù)中，其執(zhí)行效率和調(diào)度成功率均高于同類型算法。