基于VOO方法的云計(jì)算平臺(tái)多目標(biāo)任務(wù)調(diào)度算法

朱麗玲，楊智應(yīng)

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

基于VOO方法的云計(jì)算平臺(tái)多目標(biāo)任務(wù)調(diào)度算法

朱麗玲，楊智應(yīng)

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

目前，云計(jì)算正不斷興起和發(fā)展,它作為一種新的技術(shù)和商業(yè)模式受到國(guó)內(nèi)外學(xué)者的重視。而任務(wù)調(diào)度問題是云計(jì)算的核心問題之一，也是研究熱點(diǎn)。針對(duì)云計(jì)算中的任務(wù)調(diào)度問題，以完成時(shí)間和貨幣成本作為任務(wù)調(diào)度的兩個(gè)性能指標(biāo)，基于POSH算法，主要采用序優(yōu)化的方法對(duì)任務(wù)調(diào)度問題的解集進(jìn)行優(yōu)化，獲得一個(gè)相對(duì)最優(yōu)的解。實(shí)驗(yàn)中將多HEFT算法和POSH算法進(jìn)行了對(duì)比，結(jié)果表明，提出的方法在完成時(shí)間波動(dòng)相對(duì)小的情況下，能夠降低貨幣成本。因此，所提出的算法是有效的。

云計(jì)算；向量序優(yōu)化；任務(wù)調(diào)度；多目標(biāo)；完成時(shí)間；貨幣成本

0 引 言

云計(jì)算是在分布式計(jì)算、并行計(jì)算、網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展起來(lái)的，其最大的特點(diǎn)就在于“按需使用，按量付費(fèi)”[1]。云計(jì)算通過大規(guī)模的數(shù)據(jù)中心，為用戶提供強(qiáng)大的計(jì)算能力、海量的數(shù)據(jù)存儲(chǔ)能力，并且比一般的數(shù)據(jù)中心更加節(jié)能、經(jīng)濟(jì)和高效。而如何合理分配計(jì)算資源，現(xiàn)已成為云計(jì)算領(lǐng)域的熱點(diǎn)研究?jī)?nèi)容之一。任務(wù)調(diào)度作為云計(jì)算中的核心技術(shù)，如何在網(wǎng)絡(luò)帶寬、CPU、存儲(chǔ)受到限制的情況下高效使用有限的資源，是云計(jì)算系統(tǒng)中亟須解決的一個(gè)關(guān)鍵性技術(shù)難題。

目前，云計(jì)算平臺(tái)下的工作流調(diào)度問題是一個(gè)眾所周知的NP-難問題，難點(diǎn)就在于如何適應(yīng)多個(gè)目標(biāo)，而且這些目標(biāo)之間可能存在相互競(jìng)爭(zhēng)關(guān)系。例如，如何在任務(wù)完成時(shí)間最小化的前提下，使得資源花費(fèi)最小，保證容錯(cuò)率或是服務(wù)質(zhì)量(QoS)。國(guó)內(nèi)外學(xué)者就這方面作了大量研究。李劍鋒等[2]提出了一種具有雙適應(yīng)度的遺傳算法，主要運(yùn)用于云計(jì)算的編程模型框架MapReduce，該算法是基于任務(wù)總完成時(shí)間和任務(wù)的平均完成時(shí)間這兩個(gè)性能指標(biāo)進(jìn)行優(yōu)化的。華夏渝等[3]通過分析帶寬、響應(yīng)時(shí)間等影響因素，提出了一種基于種群優(yōu)化的計(jì)算資源分配方式，能夠使其獲得更短的響應(yīng)時(shí)間和更好的運(yùn)行質(zhì)量。He等[4]針對(duì)Min-Min算法進(jìn)行改進(jìn)，根據(jù)用戶是否有QoS的需求對(duì)系統(tǒng)吞吐量進(jìn)行優(yōu)化。Johan T等[5]提出了一種基于粒子群優(yōu)化的調(diào)度算法，充分考慮了任務(wù)調(diào)度的總完成時(shí)間和成本。Kong等[6]以時(shí)間和可靠性為性能指標(biāo)，以模糊規(guī)則為預(yù)測(cè)模型，提出了基于模糊預(yù)測(cè)的有效的任務(wù)調(diào)度方法。Su等[7]提出POSH算法，將完成時(shí)間和成本這兩個(gè)目標(biāo)轉(zhuǎn)換成單目標(biāo)，獲得一個(gè)滿足完成時(shí)間與成本相對(duì)滿意的策略，但往往可能會(huì)陷入局部最優(yōu)的問題。

以上提出的方法，在執(zhí)行大程序的情況下，任務(wù)調(diào)度的策略空間集合將會(huì)變得非常龐大，那么想要獲得一個(gè)相對(duì)滿意的任務(wù)調(diào)度策略，其計(jì)算的成本也會(huì)隨之上升。因此，文中在對(duì)云計(jì)算環(huán)境下的任務(wù)調(diào)度的新特性以及任務(wù)調(diào)度算法的研究現(xiàn)狀和相關(guān)研究成果進(jìn)行歸納總結(jié)的基礎(chǔ)上，基于文獻(xiàn)[7]中的啟發(fā)式算法POSH，采用序優(yōu)化方法對(duì)任務(wù)調(diào)度策略集進(jìn)行優(yōu)化，并基于該集合獲得一個(gè)相對(duì)最優(yōu)解。

1 問題模型

假設(shè)一個(gè)工作流調(diào)度系統(tǒng)有S個(gè)虛擬集群，虛擬集群中的虛擬節(jié)點(diǎn)數(shù)可以由mi(i=1,2,…,S)表示，使用W個(gè)工作流管理者將任務(wù)分配到各個(gè)集群的相應(yīng)隊(duì)列，控制作業(yè)的進(jìn)程，如圖1所示。每個(gè)集群對(duì)應(yīng)一個(gè)隊(duì)列，W個(gè)控制管理器管理S個(gè)隊(duì)列。

圖1 云平臺(tái)虛擬機(jī)資源分配模型

總結(jié)了基本標(biāo)識(shí)及其含義，i表示虛擬集群i，k表示存在k任務(wù)集。簡(jiǎn)單來(lái)說，描述的是一個(gè)雙目標(biāo)模型，該模型是為了最小化任務(wù)的執(zhí)行時(shí)間和資源操作成本。最優(yōu)化指標(biāo)J1和J2分別表示每個(gè)任務(wù)集時(shí)間tk的總和的最小值和資源總耗費(fèi)的最小值。這兩個(gè)目標(biāo)函數(shù)和約束條件將在下文定義，共同構(gòu)成調(diào)度模型[8]。

目標(biāo)函數(shù)：

(1)

類似地，如果存在N個(gè)優(yōu)化指標(biāo)，那么就需要定義N個(gè)目標(biāo)函數(shù)。

2 VOO仿真優(yōu)化方法

序優(yōu)化[9](Ordinal Optimization,OO)方法是解決仿真優(yōu)化的一個(gè)重要工具，該方法經(jīng)常用于類似多工作流調(diào)度的問題，且任務(wù)調(diào)度策略空間異常龐大的情況下。序優(yōu)化最重要的原則是“序與值”，通俗來(lái)講就是序的比較往往比值的比較容易得多。序優(yōu)化的方法是建立在粗糙模型的基礎(chǔ)上，不足以精確地判斷出任意兩個(gè)解之間性能差別是多少，但是能夠精確地判斷出兩個(gè)解到底孰優(yōu)孰劣。

文中研究的任務(wù)調(diào)度算法是基于兩個(gè)性能指標(biāo)，分別是完成時(shí)間和貨幣成本。解決多目標(biāo)的優(yōu)化問題，需要采用向量序優(yōu)化(Vectorized Ordinal Optimization,VOO)方法，即序優(yōu)化方法的延伸，也就是將標(biāo)量的情形推廣到向量的情形。向量序優(yōu)化方法與序優(yōu)化之間存在一定的差異，主要體現(xiàn)在以下幾個(gè)方面：

(3)足夠好的解。真實(shí)模型下的前g層可作為足夠好的解的集合G。

(5)向量性能曲線圖(VectorOrderedPerformanceCurve,VOPC)。這個(gè)概念主要是用于描述由粗略模型產(chǎn)生的解的排列情況。具體如圖2所示,一般分為平坦型、中間型和陡峭型，顯然陡峭型更能獲得最優(yōu)解。

(6)噪聲級(jí)別(NoiseLevel)。該概念的提出主要是為了描述粗略模型與真實(shí)模型之間的誤差，可以通過計(jì)算粗略模型估計(jì)出真實(shí)模型。

圖2 雙目標(biāo)優(yōu)化問題的策略排列以

云平臺(tái)上的多目標(biāo)調(diào)度問題是一個(gè)眾所周知的NP難問題。基于以上論述，可以了解到向量序優(yōu)化的方法適用于文中的雙目標(biāo)調(diào)度問題，根據(jù)傳統(tǒng)調(diào)度算法一次只能獲得一個(gè)任務(wù)調(diào)度策略，而無(wú)法預(yù)知策略是否最優(yōu)，那么可以進(jìn)行多次試驗(yàn)獲得大量的任務(wù)調(diào)度策略，并在此基礎(chǔ)上采用向量序優(yōu)化的方法在任務(wù)調(diào)度策略集中獲得一個(gè)相對(duì)最優(yōu)的解，這樣不僅可以避免陷入局部最優(yōu)的問題，而且也能大大提高任務(wù)調(diào)度的效率。

下面總結(jié)向量序優(yōu)化的一般步驟：

(1)根據(jù)平均采樣的方式抽取調(diào)度策略的N個(gè)解，其中N的值必須非常大(例如1 000個(gè))，并根據(jù)用戶要求給出最終要得到的足夠好的解的個(gè)數(shù)k、基準(zhǔn)概率α。

(2)對(duì)這N個(gè)解分別做n次試驗(yàn)(n?N)，例如對(duì)N個(gè)解做10次實(shí)驗(yàn)，獲得n次實(shí)驗(yàn)的完成時(shí)間(J1(θ))和貨幣成本(J2(θ))的平均值作為其真實(shí)性能。

(3)建立二維坐標(biāo)系，以完成時(shí)間J1(θ)為x軸，貨幣成本J2(θ)為y軸。根據(jù)分層算法獲得策略的布局情況，可計(jì)算出層數(shù)(m)以及相應(yīng)的向量性能曲線圖(VOPC)，判斷出是屬于平坦型、中間型還是陡峭型，并根據(jù)式(2)、式(3)調(diào)整k和g的值。

(2)

(3)

(4)根據(jù)VOPC的類型，噪聲級(jí)別，對(duì)應(yīng)線性回歸函數(shù)表得出Z0、ρ、β、η相應(yīng)的值，并根據(jù)公式s'(k',g')=eZ0(k')ρ(g')β+η計(jì)算出被選中的解的集合。該集合相對(duì)于實(shí)驗(yàn)初選取的N個(gè)解的范圍至少減少了一個(gè)數(shù)量級(jí)，那么在此基礎(chǔ)上能夠找到一個(gè)或一組相對(duì)更好的解，提高了任務(wù)調(diào)度的性能。最終根據(jù)s=「(m/100)×s'?對(duì)結(jié)果進(jìn)行調(diào)整。

以上公式均參考文獻(xiàn)[10]。

3 問題解決

3.1 DAG模型

3.2 價(jià)格模型

基于Google的定價(jià)模型，假設(shè)出一種細(xì)粒度的定價(jià)模型。通常，云提供者針對(duì)不同的工作流提供不同類型的虛擬機(jī)，而每種類型的虛擬機(jī)都存在不同的處理能力和價(jià)格模型。文中主要使用兩種定價(jià)模型，分別是線性定價(jià)模型和指數(shù)定價(jià)模型。其中，線性定價(jià)模型中虛擬機(jī)的貨幣成本與CPU周期線性相關(guān)，則任務(wù)vi在虛擬機(jī)mj上執(zhí)行的貨幣成本可表示為：

(4)

其中，σ是一個(gè)隨機(jī)變量，用于表示虛擬機(jī)價(jià)格和處理能力之間的關(guān)系，即虛擬機(jī)的處理能力越高，則貨幣成本就越高；camslow表示處理速度最慢的虛擬機(jī)mslow所占用的CPU周期；Vcbase則用于標(biāo)記虛擬機(jī)mslow的基價(jià)。

在指數(shù)定價(jià)模型中，虛擬機(jī)的貨幣成本與CPU周期呈指數(shù)關(guān)系，則任務(wù)vi在虛擬機(jī)mj上執(zhí)行的貨幣成本可表示為：

(5)

那么，任務(wù)調(diào)度完成需要的總貨幣成本可表示為：

(6)

在該模型中，忽略了內(nèi)存空間、網(wǎng)絡(luò)帶寬等因素，這可以作為以后研究的方向。

3.3 調(diào)度算法

文中主要考慮兩個(gè)目標(biāo)函數(shù)，即總貨幣成本和總完成時(shí)間。目標(biāo)是希望找出一種任務(wù)調(diào)度方法，使得任務(wù)調(diào)度最終的總貨幣成本和總完成時(shí)間可以達(dá)到最小。然而，貨幣成本和完成時(shí)間本身就是兩個(gè)相互沖突的目標(biāo)。因此，基于文獻(xiàn)[7]，選取相應(yīng)數(shù)量的任務(wù)調(diào)度結(jié)果集，并基于此采用向量序優(yōu)化的方法縮小任務(wù)調(diào)度集，獲得一個(gè)相對(duì)最優(yōu)解。

具體的算法過程如下:

算法：基于VOO的雙目標(biāo)算法。

Input：一個(gè)DAG圖，G=(V,E)；

Output：策略集PolicyList。

Procedure：計(jì)算每一個(gè)任務(wù)vi優(yōu)先級(jí)，并降序排列

Foreachvi∈Vdo

Foreachmj∈Mdo

計(jì)算目標(biāo)函數(shù)α×T(i,j)+(1-α)×C(i,j)

End

End

Whilei

Foreachvido

將vi分配給目標(biāo)函數(shù)最小的VM

End

Endwhile

采用序優(yōu)化方法將所有的解重新布局

計(jì)算出VOPC，并得到Z0、ρ、β、η對(duì)應(yīng)的值

計(jì)算出最優(yōu)解集，并從中獲得相對(duì)最優(yōu)解

基于以上算法，可以獲得一個(gè)相對(duì)最優(yōu)解，避免在使用該調(diào)度算法時(shí)陷入局部最優(yōu)問題，對(duì)于任務(wù)調(diào)度的完成時(shí)間和貨幣成本都有很大的影響，大大提高了任務(wù)調(diào)度的效率。此外，在實(shí)驗(yàn)中會(huì)進(jìn)一步驗(yàn)證該算法的性能優(yōu)劣。

4 實(shí)驗(yàn)仿真

基于WorkflowSim，實(shí)現(xiàn)云計(jì)算任務(wù)調(diào)度仿真實(shí)驗(yàn)，并與HEFT進(jìn)行比較。

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)中所采用的硬件環(huán)境是臺(tái)式機(jī)，其具體配置為：Pentium(R)Dual -Core CPUE5500@2.80 GHz，內(nèi)存為2 GB；軟件環(huán)境是Windows操作系統(tǒng)、Eclipse集成開發(fā)環(huán)境，并在Eclipse環(huán)境下搭建云平臺(tái)仿真框架WorkflowSim。為了更加合理地測(cè)試實(shí)驗(yàn)結(jié)果，所運(yùn)用的數(shù)據(jù)來(lái)源于程序。

WorkflowSim[12]是由南加州大學(xué)的Pegasus WMS研究小組開發(fā)的工作流仿真軟件，是一種基于分布式環(huán)境模擬科學(xué)工作流的工具包。它在CloudSim[13]仿真軟件的基礎(chǔ)上，提供了工作流層次的仿真方法，工作流可以以DAG圖的形式表示。

4.2 實(shí)驗(yàn)結(jié)果

以DAG圖作為任務(wù)調(diào)度的輸入流，將文中的任務(wù)調(diào)度算法進(jìn)行1 000次實(shí)驗(yàn)，取其中的100個(gè)解，以貨幣成本(cost)為x軸，完成時(shí)間(makespan)為y軸，即任務(wù)調(diào)度問題的兩個(gè)性能指標(biāo)。然后，根據(jù)分層算法將這100個(gè)解重新布局，得到相應(yīng)的VOPC，如圖3所示。

圖3 向量性能曲線圖

顯然，該向量性能曲線圖屬于陡峭型，更利于尋找所需的任務(wù)調(diào)度策略的最優(yōu)解。對(duì)應(yīng)回歸系數(shù)表,可以分別求出Z0、ρ、β、η，對(duì)應(yīng)公式則可以求出相對(duì)于之前的解集小很多的一個(gè)解集，可以得到s=1，即重新布局后的第一層中有所需要的最優(yōu)解，從第一層選中一個(gè)相對(duì)最優(yōu)解，因此可以得到最優(yōu)解的調(diào)度策略，如圖4所示。

最后，將提出的算法所得到的最優(yōu)解與HEFT[14]算法進(jìn)行比較，HEFT算法得到的解如圖5所示。

通過對(duì)比可以發(fā)現(xiàn)，文中提出的算法所得到的策略任務(wù)調(diào)度的完成時(shí)間在盡可能小的情況下，在貨幣成本方面得到了改善，但是結(jié)果不是最優(yōu)的；而使用了VOO方法后，基于策略集進(jìn)行優(yōu)化得到的結(jié)果會(huì)更優(yōu)，也避免了局部最優(yōu)的問題。因此，文中提出的方法是有效的。

圖4 計(jì)算后得到的最優(yōu)解

圖5 HEFT算法得到的解

5 結(jié)束語(yǔ)

文中主要研究了云計(jì)算中的任務(wù)調(diào)度問題，從完成時(shí)間和貨幣成本兩個(gè)方面出發(fā)，在如何平衡完成時(shí)間和貨幣成本方面有了一定的進(jìn)展。實(shí)驗(yàn)結(jié)果表明，采用序優(yōu)化方法得到的結(jié)果能夠在完成時(shí)間盡可能小的情況下，使貨幣成本有所下降，并且可以避免任務(wù)調(diào)度問題陷入局部最優(yōu)的情況，對(duì)于大大提高任務(wù)調(diào)度的效率具有重要的意義。

[1]ShenaiS.Surveyonschedulingissuesincloudcomputing[J].ProcediaEngineering,2012,38:2881-2888.

[2] 李建鋒,彭 艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用,2011,31(1):184-186.

[3] 華夏渝,鄭 駿,胡文心.基于云計(jì)算環(huán)境的蟻群優(yōu)化計(jì)算資源分配算法[J].華東師范大學(xué)學(xué)報(bào):自然科學(xué)版,2010(1):127-134.

[4]HeXiaoshan,SumXianhe,vonLaseewskiG．QoSguidedminminheuristicforgridtaskscheduling[J]．JournalofComputerScienceandTechnology,2003,18(4):442-451．

[5]TordssonJ，MonteroRS，Moreno-VozmedianoR,etal.Cloudbrokeringmechanismsforoptimizedplacementofvirtualmachinesacrossmultipleproviders[J].FutureGenerationComputerSystems,2012,28(2):358-367.

[6]KongXiangzhen，LinChuang，JiangYixin，etal．Efficientdynamictaskschedulinginvirtualizeddatacenterswithfuzzyprediction[J]．JournalofNetworkandComputerApplications，2011，34(4):1068-1077．

[7]SuS，LiJ，HuangQ,etal.Cost-efficienttaskschedulingforexecutinglargeprogramsinthecloud[J].ParallelComputing,2013,39(4-5)：177-188.

[8] 賈慶山.增強(qiáng)序優(yōu)化理論研究及應(yīng)用[D].北京:清華大學(xué),2006.

[9]HoYC,SreenivasRS,VakiliP.OrdinaloptimizationofDEDS[J].DiscreteEventDynamicSystems，1992,2(1):61-88.

[10]ZhangF,CaoJ,LiK,etal.Multi-objectiveschedulingofmanytasksincloudplatforms[J].FutureGenerationComputerSystems,2014,37(7):309-320.

[11]IsardM,BudiuM,YuY,etal.Dryad:distributeddata-parallelprogramsfromsequentialbuildingblocks[J].ACMSIGOPSOperatingSystemsReview,2007,41(3):59-72.

[12]ChenWeiwei,DeelmanE.WorkflowSim:atoolkitforsimulatingscientificworkflowsindistributedenvironments[C]//IEEEinternationalconferenceone-science.Chicago,IL:IEEE,2012:1-8.

[13]KumarR,SahooG.CloudcomputingsimulationusingCloudSim[J]．InternationalJournalofEngineeringTrendsandTechnology，2014，8(2):82-86.

[14]TopcuogluH,HaririS,WuM.Performance-effectiveandlow-complexitytaskschedulingforheterogeneouscomputing[J].IEEETransactionsonParallelandDistributedSystems,2002,13(3):260-274.

A Multi-objective Scheduling Algorithm of Many Tasks in Cloud Platforms Based on Method of VOO

ZHU Li-ling,YANG Zhi-ying

(College of Information Engineering,Shanghai Maritime University, Shanghai 201306,China)

Nowadays,cloud computing,as a new technology and business mode,is constantly rising and developing.Scholars at home and abroad have paid great attention to it.However,the problem of task scheduling in cloud platforms is one of the core issues and it’s the hot spot in the area of research on cloud computing.For the scheduling of many tasks in cloud platforms that makespan and monetary costs as two performance metric,an improved algorithm is proposed based on POSH.The algorithm mainly uses method of VOO to optimize the set of task scheduling solution,then can get a semi-optimal good-enough solution from that.In the experiments,compared with HEFT and POSH,it is concluded the proposed method can reduce the monetary cost of the scheduling under the fluctuation of makespan relatively small,which is effective.

cloud computing;VOO;task scheduling;multi-objective;makespan;cost

2016-03-08

2016-06-22

時(shí)間：2017-01-04

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202021)

朱麗玲(1991-)，女，碩士研究生，研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析；楊智應(yīng)，教授，博士，CCF會(huì)員，研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析、在線算法、計(jì)算經(jīng)濟(jì)學(xué)。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1028.048.html

TP301.6

A

1673-629X(2017)01-0011-05

10.3969/j.issn.1673-629X.2017.01.003