異構云系統中預算成本約束下高效的工作流調度算法

張龍信，王 蘭，肖滿生，文志華，李肯立

1(湖南工業大學計算機學院，湖南株洲412007)

2(湖南大學信息科學與工程學院，長沙410082)

1 引 言

萬物互聯時代到來，每日產生的數據量劇增，同時，人工智能、自動駕駛［1］、交通狀態預測、海量數據的處理對云計算等高性能計算中心提出了更高的要求［2］.目前廣泛使用的Spark 框架，在工業界和學術界備受青睞，有力地促進了高性能計算的應用［3］.

在云計算系統中，服務提供商和用戶之間的利益存在一定的沖突，服務等級協議常用來管理協議雙方［4］.金瑜等人系統地分析了云計算中心的信任機制，以提升用戶對云計算的信心［5］.李濤教授等人基于表調度和任務復制的思想，提出了一個低時間復雜度、高效的依賴比綁定的最早完成時間優先算法，這進一步提升了異構分布式系統中并行任務調度的效率［6］.隨著云計算商用模式的成熟，文獻［4］提出了一種面向市場的云工作流多層次調度策略，具體包含任務到服務的服務級調度處理，本地云數據中心中任務到虛擬機(VM)分配的任務級調度，并提出三種復雜度較高的元啟發式算法.對于云服務提供者而言，他們希望在最短的時間內完成用戶提交的計算任務［7-9］.而對用戶而言，他們向云計算中心支付任務計算的成本是其非常關心的重要指標之一.朱亞會等人設計了基于資源利用率的虛擬機調度模型，并為此模型提出了一種自適應的粒子群優化算法進行求解［10］.李薛劍和李凱針對傳統調度靜態優先級的不足，提出了一種動態優先級的作業調度策略，以兼顧任務的優先級和公平性［11］.在云計算環境中，截止期限約束下的并行任務集調度研究引起了學者們的興趣.文獻［12］基于虛擬機同構的云計算中心，提出了截止時間約束下的并行任務集資源消耗最小的調度算法.文獻［13］在考慮通信競爭情況下提出了異構分布式系統中高效的并行任務集可靠性調度算法.文獻［14］基于云計算與移動網絡，提出一種工作流任務集調度性能和能耗聯合優化算法，以提高移動云中的網絡服務質量和效率.

近年來，圍繞預算約束下并行任務集的調度長度最小化目標，國內外的學者們展開了廣泛的研究［15-18］.這些工作中，比較典型的是異構預算成本調度算法(HBCS［17］)和預算等級最小化調度長度算法(MSLBL［18］).HBCS 首先保證并行任務集中的每個任務最小的計算開銷，確保每個任務在最壞的情況下依然能以最低的預算成本分配至處理器上執行.用戶預算與并行任務集中所有任務節點的最低保障執行成本之差，本文中稱之為松弛成本.當候選任務等待執行時，HBCS算法根據價值函數(worthiness)分配處理器，計算成本開銷，任務分配完再更新松弛成本.HBCS 算法較好地解決了預算約束下的并行任務調度問題，然而其基于價值函數分配處理器的規則仍有一定的局限性.文獻［18］基于此，提出了著名的MSLBL 算法，調度性能進一步得到提升.MSLBL 算法首先計算任務的預算等級，從而保證每個任務的預算成本進一步接近任務在并行任務集中的優先等級，然后映射任務至虛擬機時則采用最早時間優先的調度策略［19］.無論是HBCS 在平攤思想的基礎上的貪婪算法，或者是優化后的MSLBL 算法，在減少任務集的調度長度方面均有一定的局限性.本文將根據工作流圖中各任務節點的綜合優先等級，先確定任務的初始預算等級成本，當任務進入候選就緒狀態時，根據當前的松弛成本增加其預算開銷;在選擇虛擬機執行階段，工作流圖中的關鍵節點在不超過任務預算成本的前提下，優先分配至關鍵虛擬機(執行關鍵路徑上的所有任務所需時間最少的虛擬機).基于此思想，可以在滿足用戶指定預算成本的前提下，更大程度地保障工作流圖中每一個任務節點選擇其最佳的執行虛擬機，并可以進一步降低任務集的調度長度.

2 相關知識

2.1 云計算中的工作流任務調度

異構云計算系統中的任務調度模型包含三層:云基礎設施層，云資源管理層，以及工作流任務圖層.云基礎設施層主要包含互聯的計算節點組.資源層主要包含配置不同的VM組，它們之間通過高速網絡連通形成強大的云資源池.工作流任務圖層為用戶提交至云計算中心的各類復雜的具體應用，工作流圖中的任務之間存在著一定優先順序約束.云計算中的工作流任務調度問題，本質上是為提交至云計算中心的具體應用選擇合適的虛擬機資源，將其中的每個任務在滿足一定的約束條件(優先順序約束、預算成本約束等)下分配至選擇的虛擬機，以期在較短的時間內(或者在預算成本約束的條件下等)得到最后的運行結果.

2.2 應用模型描述

本文的目標計算平臺由一組計算能力和計算開銷各異的虛擬機資源池組成，其中的虛擬機節點的計算、存儲、網絡能力各異.虛擬機資源池用 VM={vm1，vm2，…，vmv}表示，其中|v|為虛擬機節點的數量.工作流任務集通常可以用有向無循環圖(DAG)進行描述，用 G(T，E，C，W)表示，其中 T 為節點任務集合，E 為DAG 中直接相連兩任務節點的邊集合，C 為直接相連兩節點之間通信邊的集合，W 為節點任務在不同的虛擬機上的計算開銷集合.對于DAG 中任意直接相連的兩個任務節點τi，τj，當 ei，j∈E，ei，j表示 τj不能先于 τi執行.只有當任務 τi執行完，且任務 τj所依賴的其它數據準備就緒才能被執行.ci，j(ci，j∈C)表示任務τi的數據輸出至τj所在的虛擬機所需要的通信時間，當且僅當 τi，τj在同一個虛擬機上執行時，ci，j才為零.wi，j表示任務τi分配在虛擬機vmj上執行所需要的計算開銷.本文中任務節點τi的直接前驅節點集合記為parent(τi)，直接后繼節點集合記為child(τi).對于一個給定的DAG 工作流任務集，如果節點的直接前驅節點集合為空，則稱該節點為入口節點，記為τentry.如果一個節點的后繼節點集合為空，則稱該節點為出口節點，記為τexit.本文約定，所研究的DAG 工作流任務集中入口節點和出口節點有且僅有一個.當用戶提交的工作流任務集不符合此約定時，可以通過增加零計算開銷的虛擬入口/出口節點，同時增加零通信開銷的虛擬通信邊與已有的DAG 圖相連，以達到上述約定.

如圖1 所示，這是一個典型的工作流任務圖，其中包含了11 個任務節點.表1 為圖1 中各任務節點在3 組不同的虛擬機上的計算開銷表.以τ2為例，只有當其直接父親節點τ0執行完，τ2才可能進入準備就緒狀態.當 τ0與 τ2不在同一個虛擬機上執行時，此時的通信開銷c0，2為 12.在表1 中，w2，1表示 τ2在虛擬機vm1上執行時的計算開銷，大小為12.

圖1 一個典型的工作流圖Fig.1 A classic workflow application

表1 圖1 中各任務節點的計算開銷表Table 1 Computation cost of task nodes in fig.1

為了下文描述方便，現給出以下相關概念的定義.

定義1.數據準備就緒時間:任務τi在虛擬機vmj上的數據準備就緒時間為任務節點τi所依賴于前驅節點數據全部準備就緒的時刻，其計算表達式如式(1)所示.

其中，ACT(τk)表示任務τk的實際執行完成時刻，avai(vmj)表示虛擬機可用的時間.

同理，τi在虛擬機 vmj的最早完成時間 EFT(τi，vmj)如式(2)所示.

定義2.向上優先等級:工作流任務的向上優先等級URank 保證任務在執行過程中的優先依賴關系，自DAG 任務集的出口節點開始遞歸向上進行計算.如式(3)所示，任務τi的 URank 等于其后繼節點(child(τi))與 τi之間的通信開銷之和的最大值加上其在所有虛擬機上的平均計算開銷.

同理，任務τi的向下優先等級DRank 的計算表達式如式(4)所示.

定義3.任務的計算開銷:任務τi在虛擬機上的計算開銷表達式如式(5)所示，其中，wi，k為任務在虛擬機vmk上執行所需的時間，Costunit(vmk)為任務在虛擬機上運行時每單位時間所需要的成本.

定義4.工作流任務集的計算開銷Cost(G):工作流任務集的計算總開銷等于各任務在所分配的虛擬機上執行開銷的總和.Cost(G)的計算表達式如式(6)所示，其中 wi，map(vmk)表示任務τi在所分配的虛擬機vmk上的執行時間.

定義5.工作流任務集的最小計算開銷(Costmin(G)):工作流任務集的Costmin(G)為各任務在所有虛擬機上的最小計算開銷之和.Costmin(G)計算表達式如式(7)所示，其中為工作流任務集中任務的數量.

定義6.工作流任務集的最大計算開銷(Costmax(G)):工作流任務集的Costmax(G)為各任務在所有虛擬機上的最大計算開銷之和.Costmax(G)計算表達式如式(8)所示.

定義7.調度長度(makespan):調度長度又可稱之為SL，為工作流圖中所有的任務節點調度完成時，最后一個任務的實際執行完成時刻，即ACT(τexit)，其表達式如式(9)所示.

2.3 問題描述

對于用戶提交至云計算中心的工作流任務圖，在滿足用戶預算成本的前提下，以最少的時間調度完任務是提高用戶服務質量的關鍵指標.對于一個給定的工作流任務圖G，本文將要解決的問題是在滿足指定預算成本Costbgt(G)的前提下，為G 中的每個任務節點選擇合適的虛擬機，以期G 的調度長度最小.

上述問題的形式化可表示為式(10)和式(11).其中vmAss(τi)代表根據所設計的算法為任務τi所分配的虛擬機.

3 基于預算等級的高效調度算法(ESBL)

異構云計算中的工作流任務集調度問題，屬于組合優化的范疇，是NP 難問題.本文將提出基于預算等級的高效調度算法(ESBL).在ESBL 算法中，首先將根據各節點的優先等級確定任務的預算成本，最大程度保障關鍵任務節點有相對寬松的計算成本;然后為工作流圖中的關鍵路徑確定虛擬機集群中的關鍵虛擬機，即將關鍵路徑上的所有任務分配至同一虛擬機上執行，所需計算時間最少的虛擬機;其它任務節點將根據該節點更新后的預算開銷選擇最早完成時間的虛擬機.相關的定義如下:

定義8.任務的預算等級(BL):預算成本的松弛部分將根據任務的BL 進行分配，任務τi的BL 計算表達式如式(12)所示，在式(12)中，分母為工作流中所有任務節點的URank和DRank 之和.

定義9.任務的預算等級開銷:工作流中的任務τi在本文中初始給定的預算等級開銷CostBL(τi)由其最小開銷Costmin(τi)和對應的預算等級BL(τi)等因素共同決定，計算表達式如式(13)所示.

3.1 滿足預算約束

本文首先需要解決的一個關鍵問題是如何保證在滿足用戶給定的預算成本約束下設計一個可行的調度策略.由式(12)、式(13)不難得出，如果所有的任務均按照任務的預算等級BL(τi)分配計算成本，雖然可以保證不違反預算約束條件，但是將浪費較多的松弛成本(用戶預算成本與工作流圖實際計算開銷之差)，因此調度效果不甚理想.為此，本文針對準備就緒的任務，重新定義其預算開銷.

定義10.數據準備就緒任務的預算開銷:數據準備就緒的任務在準備執行前，為其分配的預算開銷的計算表達式如式(14)所示.其中，第一個求和表達式為已經分配執行的任務實際產生的計算開銷成本，第二個求和表達式為其它尚未執行的任務的預算等級開銷之和.

根據式(14)，在已經保證任務集中后續未執行的任務預留預算等級開銷的前提下，可最大限度為準備就緒任務利用任務集當前的松弛成本，選擇一個最佳執行虛擬機.

每個任務執行完都需要更新任務集最新的開銷，為此，任務的松弛成本定義如下.

定義11.任務的松弛成本:任務τi的松弛成本為其預算開銷Costbgt(τi)與實際開銷Costact(τi)之差，如式(15)所示.

3.2 ESBL 算法

ESBL 算法的偽代碼如算法1 所示.在算法1 中，步驟1和2 分別遞歸計算工作流圖G 中各節點的DRank 和URank值.步驟3 確定G 中的關鍵路徑節點.步驟4 確定關鍵節點虛擬機vmCP，即在所有虛擬機中，關鍵路徑節點計算時間之和最小的虛擬機.

步驟5-步驟8 為每個任務節點計算其最小的計算成本Costmin，最大計算成本Costmax以及節點的預算等級BL.步驟9根據每個節點的優先等級，計算節點的預算開銷CostBL.步驟10 計算工作流圖G 計算成本的最小下限Costmin(G)和寬松下限Costmax(G)，即用戶給定的預算成本不能低于最小下限，否則不可能調度完成.在步驟11 中，根據步驟2 得到每個節點的URank 值，根據URank 值降序排列得到隊列Qr(G)，即為G 中任務的優先調度順序.步驟12-步驟27 為ESBL 算法的核心邏輯部分.步驟13-步驟14，先從優先隊列Qr(G)中取出隊頭節點，再計算該節點的預算開銷.在步驟15 中若判斷出該候選節點為G 中的關鍵路徑節點且其在vmCP上的計算開銷不大于其預算開銷，則將該節點分配至vmCP.對于不滿足步驟15 中條件的關鍵路徑節點和非關鍵路徑上的任務節點，在步驟18-步驟24 中依次遍歷每個虛擬機，首先在步驟19 中計算出該節點在當前虛擬機上的計算成本，然后計算該節點在當前虛擬機上的最早完成時間，再執行步驟21-步驟23，在滿足節點預算開銷的約束下選擇最早完成時間的虛擬機.至此，隊頭節點的調度完成.因此在步驟26 更新實際產生的計算開銷成本，并移除隊頭節點，從而為下一個候選節點做好準備.當所有的節點都完成調度時，在步驟28-步驟29 分別計算出G 的實際開銷成本和調度長度.

3.3 ESBL 算法時間復雜度分析

在算法1 中，對于一個具有|M|個任務節點的工作流圖和|V|個虛擬機的資源池，步驟1 和步驟2 的時間復雜度均為O(|M|×|V|)，步驟9 和步驟10 的時間復雜度也為O(|M|×|V|).步驟18-步驟24 中消耗時間最多的主要是計算節點的最早完成時間，這些步驟時間復雜度為O(|M|×|V|)，所以步驟12-步驟24 的時間復雜度為O(|M|2×|V|).不難得出，算法1 的時間復雜度為O(|M|2×|V|).

3.4 ESBL 算法調度實例

如前文介紹的工作流圖1，由表1 中各任務節點在虛擬機上的計算開銷以及表2所示的虛擬機單位計算成本，根據式(7)可得到工作流圖的最小計算開銷為Costmin(G)=635.當用戶給定的預算成本為650 時，根據算法1 可計算得到如表3 所示的信息，其中包含節點的 DRank，URank，CostBL以及節點執行的優先順序等.不難看出，圖1 中的關鍵任務節點為τ0，τ4，τ7，τ8，τ10，工作流圖的優先任務隊列 Qr(G)中任務的執行順序為{τ0，τ4，τ1，τ2，τ3，τ6，τ7，τ5，τ9，τ8，τ10}.

表2 虛擬機單位計算成本Table 2 Unit price of VM

表3 根據ESBL 算法得到的圖1 中各節點信息Table 3 Information of each node in fig.1 under ESBL

使用ESBL 算法調度圖1 中工作流圖的效果如圖2 所示.工作流圖產生的實際成本為633，調度長度為105.而在同樣的約束下，工作流圖1 采用MSLBL 算法產生的實際成本為639，調度長度為133.不難得出，本文提出的ESBL 算法在調度長度方面降低了28.

圖2 工作流圖1 使用ESBL 算法調度效果圖Fig.2 Scheduling of fig.1 by using ESBL algorithm

4 實驗部分

由于本文中提出的ESBL 算法與著名的MSLBL 算法具有相同的應用模型和系統模型，這部分將與MSLBL 算法進行對比，分析算法的性能.

4.1 實驗環境

本文的實驗環境參考文獻［18］，將使用相同的實驗環境來模擬真實應用場景.實驗中使用的工作站配備了Intel Core i7-9700 @3.6 GHz 八核處理器，32 GB 內存，系統的運行版本為Win 10，并使用Java 作為實驗的開發語言.實驗中模擬的異構云計算系統擁有128 個計算能力和單位計算成本各異的處理器，其中處理器的類型和定價標準參考亞馬遜彈性計算云(EC2［20］).本文中處理器和工作流應用中的主要參數為:處理器單位計算成本0.01 $ /h≤pricek≤1 $ /h;任務在處理器上的計算時間0.01 h≤wi，k≤128 h;工作流任務圖中直接相連的兩個任務之間的通信時間為0.01 h≤ci，j≤30 h.實驗中使用的工作流任務圖中的任務數量在32 至2048 之間.

4.2 實驗評價指標

對于滿足給定預算成本約束下的工作流任務調度問題，實驗中采用工作流任務圖實際的計算成本Cost(G)和最終的調度長度SL(G)這兩個主要指標來評價本文提出的ESBL 算法和與其對比的MSLBL 算法.

為了更好地驗證ESBL 和對比算法的性能，本文將采用兩種典型的具有優先約束關系的并行任務集.一種為快速傅里葉變換(FFT)并行應用，另一種為高斯消元(GE)并行應用.這兩種都是高性能計算領域中廣泛使用的真實應用并行任務集.以下實驗中使用的不同任務數量的工作流圖，其預算成本開銷大小為 1.2×Costmin(G).

4.3 FFT 并行應用

FFT 并行應用中包含大量遞歸調用和蝶形計算操作的任務節點，這類并行應用的并行度較高，在實驗中需要增加一個零計算開銷的偽節點作為FFT 工作流圖的τexit.任務數量隨著工作流圖的層數(λ)增加而增長很快，任務的數量滿足:|M|=Sλ=2λ，其中 λ 為大于 2 的正整數.由表4 可以看出，FFT 并行應用規模增長非常快，數量從32(小規模)到2048(大規模)之間變化.表4 中列出的7 種不同規模的FFT 并行應用，工作流圖的預算成本Costbgt(G)根據任務集的最小開銷Costmin(G)乘以1.2 倍取整進行設置.

以節點數為128 為例，實驗中FFT 任務集的Costmin(G)為 7048，用戶以1.2 倍給出預算成本，即 8458.當使用 MSLBL 算法運行時，FFT 任務集實際產生的開銷為8448，調度長度為652.在同等的條件下，使用本文提出的ESBL 算法，以8247 的成本開銷完成任務集的執行，所需的調度時間為542.調度長度降低了16.87%.由表4 不難看出，與MSLBL 算法相比，ESBL 算法在不增加實際成本開銷的前提下，顯著地減低了FFT 并行應用的調度長度.FFT 并行應用的并行度較高，表4 中的7 種不同規模的測試工作流圖，在減少SL(G)方面，ESBL 算法比MSLBL 算法平均提升了17.22%.

表4 不同任務數量的FFT 并行應用的算法性能對比Table 4 Algorithm performance comparisons for FFT parallel applications with different number of tasks

4.4 GE 并行應用

為了更好地驗證算法的性能，第二類用于測試的數據流圖為現實世界的真實GE 并行應用.高斯消元并行應用節點的數量(|M|)隨著節點層數的增加滿足:|M|=Sλ=(λ2+λ－2)/2，其中λ 為高斯消元矩陣的維數.

表5 不同任務數量的GE 并行應用任務圖的算法性能對比Table 5 Algorithm performance comparisons for GE parallel applications with different number of tasks

如表5 所示，GE 并行應用中任務數量增長較快.以節點數為252 為例，實驗中GE 并行應用的Costmin(G)為10791，用戶以1.2 倍給出預算成本，即 12949.MSLBL 算法測試此GE 并行應用時，產生的成本開銷為12925，調度長度為1041.而使用本文的ESBL 算法，同樣的實驗條件下，產生的成本開銷與調度長度分別為12614 和919.此時，ESBL 算法比MSLBL 算法在減少調度長度方面提升了11.72%.GE 并行應用的并行度沒有FFT 并行應用高.表5 列出了實驗中使用的7種不同規模的GE 并行應用，ESBL 算法在不增加實際成本開銷的前提下，對應的調度長度比同等條件下的MSLBL 算法平均降低了12.11%.

5 總 結

針對成本驅動的云計算服務日趨普遍，本文基于異構的云計算平臺，提出一種時間復雜度低，調度效率高的預算成本約束下的工作流調度算法ESBL.ESBL 算法根據工作流中任務的優先等級，分配預算等級成本，保證任務集滿足優先順序約束及成本約束的同時，最大限度的保障了關鍵節點相對寬松的預算成本，從而達到減低任務集調度長度的目的.

通過FFT 和GE 兩類、多組不同規模真實世界的并行應用對比實驗，與著名的MSLBL 算法相比，ESBL 既有效地減少了工作流任務集的實際計算成本，又使其調度長度平均分別降低了17.22%和12.11%.ESBL 算法較為顯著地提升了異構云計算系統中成本約束下并行任務集的調度效率.