預(yù)算約束下關(guān)聯(lián)式云任務(wù)調(diào)度算法

何留杰

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

0 引 言

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

1 相關(guān)研究

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

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

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

2 系統(tǒng)模型

2.1 工作流模型

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

2.2 相關(guān)定義

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

(1)

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

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

ECT(ti)=EST(ti)+wti

(2)

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

(3)

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

(4)

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

2.3 云服務(wù)模型

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

P={p0,p1,…,pn}

式中，n為實(shí)例類型的索引。

3 WTSBC算法設(shè)計(jì)

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

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

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

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

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

3.1 工作流劃分

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

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

(5)

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

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

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

(6)

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

3.2 預(yù)算分割

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

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

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

3.3 任務(wù)選擇

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

改進(jìn)升秩排序

(7)

改進(jìn)降秩排序

(8)

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

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

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

1. procedure FindCP(DAG G)

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

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

4. end for

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

6. while there is an univisited task in G do//尋找未訪問(wèn)任務(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 實(shí)例選擇

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

(9)

(10)

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

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

(11)

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

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

(12)

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

(13)

因此，由于沒(méi)有預(yù)算盈余，無(wú)法開(kāi)戶一個(gè)新的實(shí)例。此時(shí)，式(12)也等于0。并且，如果式(10)變?yōu)樨?fù)值，則表明在所選實(shí)例上的執(zhí)行代價(jià)高于可用子預(yù)算subBudgetCCPi。

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

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

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

(14)

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

3.5 預(yù)算分割算例

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

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

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

圖1 工作流示例

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

4×BF=4×11=44

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

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

2×BF=4×16.5=33

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

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

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

舉例層次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 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)配置

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

表2 實(shí)例類型

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

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

(15)

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

budget=α×FS, 1<α<6

(16)

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

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

4.2 結(jié)果分析

本節(jié)實(shí)現(xiàn)了預(yù)算分割方法分別為Area和All in時(shí)的任務(wù)調(diào)度算法，分別命名為WTSBC-Area和WTSBC-All in。并且選擇預(yù)算約束異構(gòu)最早完成時(shí)間算法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í)行跨度是評(píng)估算法性能的最重要基準(zhǔn)。增加預(yù)算允許調(diào)度系統(tǒng)釋放出擁有更好CPU、內(nèi)存和網(wǎng)絡(luò)帶寬性能的更高性能實(shí)例，因此，全局工作流執(zhí)行時(shí)間隨著預(yù)算的增加而降低是顯而易見(jiàn)的。

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

(a) CyberShake工作流

(b) LIGO工作流

(c) Montage工作流

同時(shí)，當(dāng)預(yù)算極其受限時(shí)(預(yù)算因子相比更小)，BHEFT算法擁有最差的性能。例如：在3種工作流類型的前兩個(gè)預(yù)算因子中，BHEFT算法的執(zhí)行跨度幾乎是其他算法的3倍。利用Area和Allin方法進(jìn)行預(yù)算分割的WTSBC算法均擁有比MED-CC和BHEFT更低的執(zhí)行跨度，且多數(shù)情況下，兩種預(yù)算分割方法間的差異并不大?？傮w來(lái)說(shuō)，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個(gè)預(yù)算因子中擁有100%失效率，表明該算法此時(shí)無(wú)法得到調(diào)度方案。搜索合理調(diào)度方案的最差性能發(fā)生在LIGO工作流中，此時(shí)MED-CC算法在前3個(gè)預(yù)算因子中擁有20%～30%的失效率。

(a) CyberShake工作流

(b) LIGO工作流

(c) Montage工作流

5 結(jié) 語(yǔ)

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