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

鐘積海 ，崔得龍 ，2

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

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

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

1 相關(guān)工作

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

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

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

2 在線自適應(yīng)高斯過程建模

2.1 高斯過程回歸

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

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

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

2.2 在線自適應(yīng)GPR模型

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

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

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

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

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

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

3.1 云工作流模型組件介紹

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

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

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

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

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

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

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

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

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

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

任務(wù)vi響應(yīng)率Wvi定義為：

任務(wù)vi公平性指標(biāo)Fvi定義為：

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

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

4 實驗驗證與分析

4.1 云工作流仿真器WorkflowSim

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

4.2 實驗驗證

本文實驗?zāi)M平臺Workflowsim的參數(shù)設(shè)置如表1所示。

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

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

表1 實驗?zāi)M平臺的參數(shù)

圖2 Q值表收斂比較

圖3 累計回報比較

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

5 結(jié)束語

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