基于改進高斯過程回歸的云工作流調(diào)度算法

鐘積海 ，崔得龍 ，2

（1.廣東石油化工學院計算機與電子信息學院，廣東茂名525000；2.廣東省云機器人（石油化工）工程技術(shù)研究中心廣東茂名525000）

云工作流（科學工作流、多層Web服務工作流、MapReduce工作流和Dryad工作流等）是工作流在云計算環(huán)境下的一種新應用模式[1]，其在共享異構(gòu)分布式資源（公有云、私有云或混合云等）下的調(diào)度問題近年來引起了科研工作者們的廣泛關注，并已在執(zhí)行時間最小化、公平性最大化、吞吐量最大化以及資源優(yōu)化分配等方面取得了重要進展。

但目前云工作流調(diào)度研究通常建模為多約束條件下的單/多目標優(yōu)化問題，該問題或側(cè)重于固定虛擬化資源下的工作流任務分配[2]，或側(cè)重于工作流負載變化下的彈性資源供給，或側(cè)重于如何將現(xiàn)有的工作流管理系統(tǒng)融入云平臺之中[3，4]，同時當云工作流任務規(guī)模變大時，該優(yōu)化問題變得異常復雜，往往無法及時得到最優(yōu)任務分配策略，也易陷入局部最優(yōu)。

1 相關工作

云工作流，尤其是科學工作流具有業(yè)務流程復雜、計算任務耗時和數(shù)據(jù)量大等特征，工作流任務之間的依賴約束關通常采用有向無環(huán)圖（DAG）進行描述。

Shojafar等人[5]提出一種基于模糊理論和遺傳算法的混合優(yōu)化任務調(diào)度算法，在完成時間和租用費用的約束下優(yōu)化虛擬機間負載均衡。Abrishami等人[6]在其網(wǎng)格工作流調(diào)度的研究基礎上，分別設計了基于IaaS云的單向IC-PCP和帶截止時間約束的雙向IC-PCP任務分配算法，并指出兩種算法的時間復雜度都僅為多項式時間。清華大學張范等人[7]設計了一種基于擴展序優(yōu)化多目標多任務調(diào)度算法，大幅度降低了時間開銷，并證明了該算法具有次優(yōu)性。大連理工大學郭禾等人[8]提出帶通信開銷的工作流費用優(yōu)化模型，并在模型的基礎上提出了分層調(diào)度算法。Szabo等人[9]針對數(shù)據(jù)密集型科學工作流應用，考慮了網(wǎng)絡傳輸和執(zhí)行時間的約束，設計了一種基于進化方法的任務動態(tài)分配算法。Chen等人[10]針對多工作流任務公平分配問題，設計了一種優(yōu)先級約束下的動態(tài)任務重排和調(diào)度算法。東南大學李小平團隊在動態(tài)任務調(diào)度方面進行了大量的研究，近期發(fā)表了一種帶準備時間和截止期約束的云服務工作流費用優(yōu)化算法[11]。該算法建立了相應的整數(shù)規(guī)劃數(shù)學模型，引入個體向全局最優(yōu)解學習的策略提高算法的全局搜索和局部優(yōu)化能力。安徽大學李學俊等人[12]針對傳統(tǒng)數(shù)據(jù)布局方法的不足并結(jié)合混合云中數(shù)據(jù)布局的特點，設計一種基于數(shù)據(jù)依賴破壞度的矩陣劃分模型，提出一種面向數(shù)據(jù)中心的工作流任務布局方法，將依賴度高的工作流任務盡量放在同一數(shù)據(jù)中心，從而減少數(shù)據(jù)集跨數(shù)據(jù)中心的傳輸時間。針對不同時間提交的不同QoS需求的多工作流調(diào)度問題，設計了一種基于強化學習和DAG關鍵路徑的混合任務公平調(diào)度算法[13]，算法采用狀態(tài)聚類大幅度降低了狀態(tài)空間的維度，提高了算法的收斂速度。通過分析工作流任務在云平臺的執(zhí)行過程，設計了一種多目標優(yōu)化任務調(diào)度算法[14]。針對計算密集型和數(shù)據(jù)密集型混合任務，綜合采用多agent并行學習、知識復用和遷移等技術(shù)加速最優(yōu)策略的搜索[15]。Fard等人針對異構(gòu)云計算環(huán)境設計了一種多目標優(yōu)化算法。算法將全局任務分配問題劃分為多個子分配問題，每個子問題分別采用元啟發(fā)式算法求解[16]。謝國琪等人在多工作流混合調(diào)度領域進行了長期深入的研究，近期針對云計算環(huán)境中多工作流的可靠調(diào)度問題，提出一種考慮虛擬機之間鏈路通信競爭的動態(tài)多DAG調(diào)度策略[17]，有效解決了當多個DAG中任務的權(quán)值相差較大時的公平調(diào)度問題。田國忠等人首先提出了衡量DAG期限緊急水平的“相對嚴格程度”指標，能夠合理處理多個DAG之間調(diào)度的緊急水平關系，從而達到DAG吞吐量最大化調(diào)度目標[18]。

綜述所述，目前大部分工作是網(wǎng)格工作流任務分配策略在計算資源“按需付費”特性上的擴展，忽略了云計算環(huán)境最根本的“彈性資源供給”特征，因此缺乏新穎性和通用性，也不符合真實的云計算應用場景。同時，該問題通常建模為多約束條件下的單/多目標優(yōu)化問題，但當任務規(guī)模變大時，該優(yōu)化問題變得異常復雜，往往無法及時得到最優(yōu)任務分配策略，也易陷入局部最優(yōu)。

2 在線自適應高斯過程建模

2.1 高斯過程回歸

式（1）和式（2）中，y=[y1,y2,...,yn]T為訓練樣本輸出構(gòu)成的向量；k(x*)=[C(xi,x*)]n×1為測試輸入和訓練樣本輸入間的協(xié)方差向量；K=[C(xi,xj)]n×n為訓練樣本輸入間的n×n協(xié)方差矩陣；C(xi,xj)為測試輸入與其自身的協(xié)方差。

徑向基函數(shù)是最常用的協(xié)方差函數(shù)，其正定表達式如下：

式（3）所示的協(xié)方差函數(shù)由2部分的和組成，前一部分表示相鄰輸入有著高度相關的輸出，且對于每一個輸入，參數(shù)wt允許使用不同的距離測度，參數(shù)vij用于控制局部相關性的程度；后一部分表示數(shù)據(jù)中的噪聲，其中vi表示噪聲的方差。協(xié)方差函數(shù)中的超參數(shù)通常使用貝葉斯法、最大似然法或交叉驗證法等進行迭代優(yōu)化。當采用最大最大似然法求超參數(shù)，GPR的似然函數(shù)可表示為：

2.2 在線自適應GPR模型

直接利用式（4）求解GPR的超參數(shù)，CN矩陣會隨著數(shù)據(jù)集的不斷加入變得異常龐大，因此必須在迭代過程中進行數(shù)據(jù)的更新替換，以確保數(shù)據(jù)集的大小和計算的速度。本文利用Adaptive Nature Gradient（ANG）的迭代運算求解超參數(shù)的最優(yōu)值，ANG可表示為：

式（4）對超參數(shù)求導，得：

G的迭代估計式[19]如下：

3 云工作流調(diào)度算法

云工作流系統(tǒng)是建立在云計算平臺上的工作流系統(tǒng)，其功能需求仍滿足云計算模式的特點.它的功能組件包括了一般工作流系統(tǒng)組件和與工作流系統(tǒng)相協(xié)調(diào)云計算平臺。此外，云計算平臺的管理非常復雜和龐大，如何高效提高服務質(zhì)量QoS（Quality of Serivice）的管理和任務部署是一個極大的挑戰(zhàn).因此，云工作流系統(tǒng)同樣面臨同樣的問題。為了在云環(huán)境中如何高效調(diào)度任務及數(shù)據(jù)。本文提出了一個云工作流系統(tǒng)模型如圖1所示。

圖1 云工作流系統(tǒng)模型

3.1 云工作流模型組件介紹

云工作流接口：云工作流通過這個接口導入到云工作流系統(tǒng)中，這個組件提供了對科學工作流，電子商務等的接口，以便后續(xù)組件根據(jù)其工作流的主要特點進行分類處理。

云工作流解析器：這個組件對工作流整體進行解析，生成工作流的任務集，任務之間的約束關系，以及任務之間的數(shù)據(jù)和傳輸路徑。

云工作流引擎：獲取了云工作流解析器生成工作流任務集，任務之間的約束關系，以及任務之間的數(shù)據(jù)和傳輸路徑。云工作流引擎的主要作用在于根據(jù)任務間的約束關系，確保當前任務在父任務成功完成或數(shù)據(jù)到達當前任務時，當前任務才可以執(zhí)行。這個組件只提交未處理的任務給云工作流調(diào)度器。

云工作流調(diào)度器：這個組件是整個系統(tǒng)的核心，主要的任務調(diào)度算法是通過這個組件實現(xiàn)，首先云工作流調(diào)度器通過加載上一層組件生成的云工作流，生成一個全局隊列，其次在作業(yè)分配器中根據(jù)調(diào)度算法對任務進行分配，生成作業(yè)的調(diào)度的子隊列，然后從子隊列中按照先來先服務的順序把任務分配給虛擬機進行處理，最后輸出執(zhí)行結(jié)果。

3.2 云工作流調(diào)度算法

根據(jù)圖1云平臺模型和經(jīng)典隊列理論，在每個調(diào)度時刻系統(tǒng)狀態(tài)轉(zhuǎn)移滿足馬爾科夫性，則基于強化學習的云作業(yè)調(diào)度相關概念可描述如下：

狀態(tài)空間：用五元組S=(WR,RA,AW,IM,PJ)表示狀態(tài)空間，其中WR表示待調(diào)度任務的工作量；RA表示資源可用時間；AW表示等待隊列中的總工作量；IM表示空閑容器資源數(shù)；PJ表示隊列中各用戶提交任務的比例。

動作空間：用三元組J=(TJ,WS,ET)表示動作空間，其中TJ表示任務類型；WS表示用戶標識符；ET表示任務執(zhí)行時間。

獎賞函數(shù):本文采用式（9）作為多工作流公平分配的獎賞函數(shù)：

式（4）中，λs∈[0,1]為控制系數(shù)；W為工作流任務響應率；F為公平性指標。

任務vi響應率Wvi定義為：

任務vi公平性指標Fvi定義為：

算法偽代碼如算法1所示。

算法1改進的云工作流調(diào)度算法

4 實驗驗證與分析

4.1 云工作流仿真器WorkflowSim

WorkflowSim是由南加州大學的Pegasus WMS組開發(fā)的一套開源工作流仿真軟件，其工作原理是在暨有的CloudSim仿真軟件基礎上，提供workflow層次的仿真。WorkflowSim可用于驗證圖算法（Graph algorithm）、分布式研究（distributed computing）、工作流調(diào)度算法（scheduling）、資源調(diào)度算法（resource provisioning）等問題的研究。

4.2 實驗驗證

本文實驗模擬平臺Workflowsim的參數(shù)設置如表1所示。

選用基本強化學習和文獻[20]進行比較，實驗結(jié)果如圖2和圖3所示。

圖2所示為基本強化學習和本文設計算法下Q值表收斂情況比較。從圖2的實驗結(jié)果可見，基本強化學習下圖2（a）由于部分狀態(tài)訪問次數(shù)較少，導致Q值表更新較慢，對比算法1圖2（b）采用了高斯過程回歸，有效提高了Q值表的收斂速度，但本文算法圖2（c）在速度和精度上，都優(yōu)于基本強化學習和對比算法1。

表1 實驗模擬平臺的參數(shù)

圖2 Q值表收斂比較

圖3 累計回報比較

圖3所示為完成相同工作流任務下的累計回報比較情況，實驗結(jié)果表明本文算法優(yōu)于基本強化學習和對比算法1。

5 結(jié)束語

文中設計了一種基于改進Q-learning的云資源調(diào)度算法，針對原始Q-learning算法存在的不足，結(jié)合高斯過程回歸加速最優(yōu)策略的收斂，實驗結(jié)果證明本文算法的有效性。今后的工作將在高斯過程回歸的參數(shù)優(yōu)化，預測更新步長等方面展開。