預算約束下關聯式云任務調度算法

2018-10-30 10:08:30何留杰

實驗室研究與探索 2018年9期

關鍵詞：資源

何留杰

(黃河科技學院現代教育技術中心，鄭州 450063)

0 引言

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

1 相關研究

云計算環境中，截止期限和預算等QoS約束下的工作流調度問題是研究熱點問題。多數截止期限約束的調度算法主要思想是如何將用戶定義的期限在工作流任務或層次間進行分布[3-4]，更多強調調度效率，忽略調度成本。而云環境是即付即用的資源提供環境，相比而言，預算約束是其更應該考慮的約束條件。該領域中的相關研究大致可分為兩類：代價優化和預算約束。

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

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

2 系統模型

2.1 工作流模型

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

2.2 相關定義

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

(1)

式中，wtj表示任務tj在速度最快的實例上的執行時間。

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

ECT(ti)=EST(ti)+wti

(2)

在實例pj上執行任務ti的代價為：

(3)

執行工作流的所有任務的總代價為：

(4)

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

2.3 云服務模型

假設云供應商可提供無上限的異構實例數量：

P={p0,p1,…,pn}

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

3 WTSBC算法設計

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

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

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

(3) 任務選擇。根據任務優先級，選擇約束關鍵路徑上的任務集，作為執行的就緒隊列。

(4) 實例選擇。選擇滿足可用預算的實例執行任務。

3.1 工作流劃分

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

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

(5)

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

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

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

(6)

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

3.2 預算分割

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

(1) 區域分割法Area。由于工作流的結構會對調度結果產生實質影響，該方法聯合考慮工作流的高度和寬度。Area法重點考慮。①工作流的高度：即每個層次的預算分割正比于所在層次與入口任務間的距離；②工作流的寬度：即每個層次的預算分割正比于所有層次中包含的任務數量。

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

3.3 任務選擇

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

改進升秩排序

(7)

改進降秩排序

(8)

式中，AETi和ACTi分別為任務ti的平均執行時間和平均通信時間。

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

算法1關鍵路徑搜索

1. procedure FindCP(DAG G)

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

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

4. end for

5. CPlist←?//初始化關鍵路徑列表為空

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

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

8. CP←?//置關鍵路徑為空

9. whiletiis not null do

10. addtito CP//添加任務ti至關鍵路徑

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

12. end while

13. add CP to CPlist//添加關鍵路徑至CP列表

14. end while

15. end procedure

3.4 實例選擇

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

(9)

(10)

式中，Cbest為在所有實例上執行當前CCP的最小代價。

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

(11)

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

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

(12)

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

(13)

因此，由于沒有預算盈余，無法開戶一個新的實例。此時，式(12)也等于0。并且，如果式(10)變為負值，則表明在所選實例上的執行代價高于可用子預算subBudgetCCPi。

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

將單個CCP分配至一個實例后(代價為C(CCPi,pj))，需要更新每個層次的剩余預算。在工作流為最早任務分配更高的預算通常可以得到更小的執行跨度。算法2給出了預算的更新過程。

算法2更新剩余預算

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算法的一個重要步驟是將未使用的剩余預算傳遞至下一層次繼續使用。定義剩余層次預算SLB為層次l的所有任務調度后剩余的費用預算，表示為：

(14)

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

3.5 預算分割算例

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

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

預算因子BF計算為

圖1 工作流示例

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

4×BF=4×11=44

(2) 寬度。每個層次依據對應層次中任務數量得到其預算分配：

舉例包含兩個任務的層次4分配的預算為

2×BF=4×16.5=33

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

預算因子BF計算為

預算根據圖1中右欄數字之和進行分配。

舉例層次3的預算分配為

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

(4) 漏斗分配Allin。總預算分配至層次5，調度該層次的所有任務后，剩余預算傳遞至下一層次。

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

表1 不同分割方法的層次預算

4 仿真實驗

4.1 實驗配置

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

表2 實例類型

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

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

(15)

定義預算為最快調度的函數，表示為

budget=α×FS, 1<α<6

(16)

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

Amazon EC2實例在提供時間內按1 h的帳單周期支付費用。同時，為了比較不同規模工作流下的性能，為工作流分別配置50、100、200、500和1 000個任務。利用Pegasus工作流發生器創建前文的三種科學工作流結構，并利用CloudSim實現調度算法，完成算法仿真。

4.2 結果分析

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

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

(a) CyberShake工作流

(b) LIGO工作流

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

調度成功率可以反應算法是否能夠在滿足預算約束的情況下完成工作流調度。可以看出，寬松下的預算可以增加調度成功率，這是由于預算越多，算法得到的調度方案滿足預算的概率將越高。WTSBC-Area算法在Montage工作流的第1個預算因子中擁有100%失效率，表明該算法此時無法得到調度方案。搜索合理調度方案的最差性能發生在LIGO工作流中，此時MED-CC算法在前3個預算因子中擁有20%～30%的失效率。