朱麗玲，楊智應

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

基于VOO方法的云計算平臺多目標任務調度算法

朱麗玲，楊智應

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

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

云計算；向量序優(yōu)化；任務調度；多目標；完成時間；貨幣成本

0 引 言

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

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

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

1 問題模型

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

圖1 云平臺虛擬機資源分配模型

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

目標函數(shù)：

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

(3)

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

以上公式均參考文獻[10]。

3 問題解決

3.1 DAG模型

3.2 價格模型

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

(4)

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

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

(5)

那么，任務調度完成需要的總貨幣成本可表示為：

(6)

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

3.3 調度算法

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

具體的算法過程如下:

算法：基于VOO的雙目標算法。

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

Output：策略集PolicyList。

Procedure：計算每一個任務vi優(yōu)先級，并降序排列

Foreachvi∈Vdo

Foreachmj∈Mdo

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

End

End

Whilei

Foreachvido

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

End

Endwhile

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

計算出VOPC，并得到Z0、ρ、β、η對應的值

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

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

4 實驗仿真

基于WorkflowSim，實現(xiàn)云計算任務調度仿真實驗，并與HEFT進行比較。

4.1 實驗環(huán)境

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

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

4.2 實驗結果

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

圖3 向量性能曲線圖

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

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

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

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

圖5 HEFT算法得到的解

5 結束語

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

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

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

[3] 華夏渝,鄭 駿,胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學學報:自然科學版,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] 賈慶山.增強序優(yōu)化理論研究及應用[D].北京:清華大學,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

時間：2017-01-04

國家自然科學基金資助項目(61202021)

朱麗玲(1991-)，女，碩士研究生，研究方向為算法設計與分析；楊智應，教授，博士，CCF會員，研究方向為算法設計與分析、在線算法、計算經(jīng)濟學。

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