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

鐘積海 ，崔得龍 ，2

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

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

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

1 相關(guān)工作

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

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

綜述所述，目前大部分工作是網(wǎng)格工作流任務(wù)分配策略在計(jì)算資源“按需付費(fèi)”特性上的擴(kuò)展，忽略了云計(jì)算環(huán)境最根本的“彈性資源供給”特征，因此缺乏新穎性和通用性，也不符合真實(shí)的云計(jì)算應(yīng)用場(chǎng)景。同時(shí)，該問題通常建模為多約束條件下的單/多目標(biāo)優(yōu)化問題，但當(dāng)任務(wù)規(guī)模變大時(shí)，該優(yōu)化問題變得異常復(fù)雜，往往無法及時(shí)得到最優(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為測(cè)試輸入和訓(xùn)練樣本輸入間的協(xié)方差向量；K=[C(xi,xj)]n×n為訓(xùn)練樣本輸入間的n×n協(xié)方差矩陣；C(xi,xj)為測(cè)試輸入與其自身的協(xié)方差。

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

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

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

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

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

G的迭代估計(jì)式[19]如下：

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

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

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

3.1 云工作流模型組件介紹

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

云工作流解析器：這個(gè)組件對(duì)工作流整體進(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ù)時(shí)，當(dāng)前任務(wù)才可以執(zhí)行。這個(gè)組件只提交未處理的任務(wù)給云工作流調(diào)度器。

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

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

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

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

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

獎(jiǎng)賞函數(shù):本文采用式（9）作為多工作流公平分配的獎(jiǎng)賞函數(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 實(shí)驗(yàn)驗(yàn)證與分析

4.1 云工作流仿真器WorkflowSim

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

4.2 實(shí)驗(yàn)驗(yàn)證

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

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

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

表1 實(shí)驗(yàn)?zāi)M平臺(tái)的參數(shù)

圖2 Q值表收斂比較

圖3 累計(jì)回報(bào)比較

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

5 結(jié)束語

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