基于多尺度量子諧振子算法的云計算任務調(diào)度

韓 虎，王 鵬，程 琨，李 波

(1.中國科學院 成都計算機應用研究所，成都 610041； 2.中國科學院大學，北京 100049；3.西南民族大學 計算機科學與技術(shù)學院，成都 610225) (*通信作者電子郵箱wp002005@163.com)

基于多尺度量子諧振子算法的云計算任務調(diào)度

韓 虎1,2，王 鵬3*，程 琨1,2，李 波1,2

(1.中國科學院 成都計算機應用研究所，成都 610041； 2.中國科學院大學，北京 100049；3.西南民族大學 計算機科學與技術(shù)學院，成都 610225) (*通信作者電子郵箱wp002005@163.com)

合理地分配虛擬計算資源以進行有效的任務調(diào)度是云計算中的一個核心問題。為了更好地利用虛擬計算資源，高效地完成服務需求，提出了一種基于多尺度量子諧振子算法(MQHOA)的任務調(diào)度算法。首先，該算法將每一個調(diào)度方案當成一個采樣位置，利用高斯采樣的隨機性在當前尺度下搜索局部最優(yōu)解；其次，判斷算法是否處于能級穩(wěn)定狀態(tài)，如果穩(wěn)定，則進入能級降低過程，最壞的調(diào)度方案將被替換；最后，算法進入尺度下降的過程，算法由全局搜索過渡到局部搜索，迭代多次之后，算法停止并輸出找到的最優(yōu)結(jié)果。通過在CloudSim平臺上進行仿真實驗，與現(xiàn)有的先來先服務(FCFS)算法和粒子群優(yōu)化(PSO) 算法對比，MQHOA總?cè)蝿胀瓿蓵r間減少10%以上，負載不均值下降0.4以上。實驗結(jié)果表明，基于MQHOA的任務調(diào)度算法能夠快速收斂，有良好的全局收斂性和自適應能力，在云計算任務調(diào)度過程中，能夠起到減少總?cè)蝿胀瓿蓵r間和均衡負載的作用。

多尺度量子諧振子算法；云計算；任務調(diào)度；快速收斂；負載均衡

0 引言

云計算作為一種基于互聯(lián)網(wǎng)的計算服務模式，受到了工業(yè)界、學術(shù)界的廣泛關(guān)注。云計算有三大特征：資源池化、快速彈性、按需分配的自主服務。云計算通過資源虛擬化為用戶提供了基礎設施即服務(Infrastructure as a Service, IaaS)，平臺即服務(Platform as a Service, PaaS)和軟件即服務(Software as a Service, SaaS)。隨著云計算技術(shù)的快速發(fā)展，其在能源、制造、金融、教育科研、電子政務、醫(yī)藥醫(yī)療、電信通信等主要領(lǐng)域都有很好的應用前景。由于云計算中用戶群體規(guī)模很大，提交的任務數(shù)量很多，如何快速響應用戶需求，高效地進行云計算任務調(diào)度成為云計算領(lǐng)域中重要的研究課題。

云計算任務調(diào)度屬于NP完全問題[1]，目前，云計算任務調(diào)度方法大都采用了靜態(tài)資源調(diào)度算法。各大云計算公司如Google、IBM采用的調(diào)度算法和Hadoop一樣，先來先服務(First Come First Serviced, FCFS)算法是Hadoop的默認調(diào)度算法，但是對于短作業(yè)可能存在等待時間過長的問題。雅虎和Facebook提出了計算能力調(diào)度和公平份額調(diào)度算法，但是這兩種算法都不能根據(jù)集群中的節(jié)點生成較優(yōu)的調(diào)度方案[2-3]。智能優(yōu)化算法如：模擬退火算法、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[4]、蟻群算法[5]、遺傳算法[6]等在求解NP類問題上非常適合，在云計算任務調(diào)度中，這類啟發(fā)式算法相比傳統(tǒng)的任務調(diào)度算法，能夠顯著降低總?cè)蝿胀瓿蓵r間，但是存在參數(shù)設置不合適、調(diào)度目標單一、迭代時間過長等問題。

針對以上分析，本文首次提出一種基于多尺度量子諧振子算法(Multi-scale Quantum Harmonic Oscillator Algorithm, MQHOA)的云計算任務調(diào)度算法以克服上述算法存在的弊端，MQHOA是2009年提出的一種模仿量子諧振子波函數(shù)能級模型的優(yōu)化算法[7]。文獻[8]給出了MQHOA的實現(xiàn)，該算法數(shù)學原理簡單物理含義明確且無需任何先驗知識。完備的解空間搜索能力和精確的聚焦能力使MQHOA能夠較準確地在高維空間中實現(xiàn)對解的搜索定位。文獻[9]給出了算法最新的改進模型，引入能級穩(wěn)定過程，使MQHOA在高能級的亞穩(wěn)態(tài)進行充分的搜索，從而避免過早地陷入到解空間中的某一區(qū)域，無法充分搜索整個解空間。文獻[10]將模擬諧振子算法應用于多項目調(diào)度問題，驗證了算法的有效性，表明了模擬諧振子算法的改進算法MQHOA應用在云計算任務調(diào)度的可行性。文獻[11]分析了MQHOA在求解整數(shù)非線性規(guī)劃問題上的性能，得到MQHOA在求解精度和收斂速度上均優(yōu)于文中對比算法。云計算調(diào)度問題本身就是一個整數(shù)規(guī)劃問題，這體現(xiàn)了MQHOA在解決這類問題的良好性能。MQHOA在解決云計算調(diào)度問題中，由于算法本身的特點，克服了粒子群算法局部搜索能力不足并且需要較多先驗知識的缺點，面對多樣化的任務調(diào)度需求，適應性更強。基于MQHOA的任務調(diào)度算法利用高斯采樣的隨機性處理云計算任務調(diào)度，解決傳統(tǒng)調(diào)度算法存在的短作業(yè)等待時間過長問題，而且相比蟻群算法、粒子群算法、遺傳算法，該算法也具有MQHOA收斂速度快、參數(shù)設置少、數(shù)學結(jié)構(gòu)簡單的優(yōu)點，能夠較好平衡局部搜索和全局搜索這兩個過程。仿真實驗結(jié)果表明，基于MQHOA的任務調(diào)度算法可以取得較優(yōu)的任務調(diào)度方案和負載均衡。

1 云計算任務調(diào)度與MQHOA物理模型

1.1 云計算任務調(diào)度問題描述

云計算任務調(diào)度問題的實質(zhì)是將用戶提交的任務交給合適的資源上運行，通過對任務的合理分配，使總的任務完成時間達到最小。為了深入研究云計算調(diào)度問題，本文假設用戶提交的任務之間相互獨立，并且執(zhí)行沒有先后順序；各個任務的計算成本和數(shù)據(jù)中心中資源的計算能力已知；分配之后任務將一直對應虛擬機上運行，不會中斷。

用戶提交的任務可以用T表示，則n個相互獨立的任務可以集合T={T1,T2,…,Tn}表示，數(shù)據(jù)中心上虛擬機資源用VM表示，則m個虛擬機資源組成的集合表示為VM={VM1,VM2,…,VMm}，將n個相互獨立的任務分配到m個虛擬機資源上運行，這種分配關(guān)系可以用矩陣A的形式表示：

(1)

eij=Lengthi/MIPSj

(2)

分配矩陣A對應的運行時間矩陣可以用E表示：

(3)

對于分配矩陣對應的所有任務運行時間用C表示：

(4)

云計算任務調(diào)度的優(yōu)化目標是使C最小，一個好的分配方案應該是平衡各個虛擬機上面的任務，在多個虛擬機中，找到運行任務時間最長的虛擬機，優(yōu)化這個虛擬機上的任務負載。

1.2 MQHOA物理模型描述

量子力學中的定態(tài)薛定諤方程描述了在勢阱V(x)約束下粒子的概率分布情況，MQHOA引入定態(tài)薛定諤方程，將優(yōu)化問題中的目標函數(shù)的f(x)作為定態(tài)薛定諤方程中的勢阱V(x)=f(x)，在這一對應條件下，函數(shù)優(yōu)化問題就轉(zhuǎn)化為求粒子在勢阱V(x)=f(x)約束條件下的基態(tài)波函數(shù)ψ0(x)問題[12]。在量子系統(tǒng)中，粒子處于基態(tài)時將在勢阱最低點附近以最大的概率出現(xiàn)，目標函數(shù)的概率分布與基態(tài)波函數(shù)的概率分布一樣。薛定諤方程無法求出復雜勢阱的波函數(shù)，而函數(shù)在最優(yōu)解附近的尋優(yōu)過程類似于物理中諧振子勢在平衡位置的簡諧振動，所以復雜的目標函數(shù)f(x)可以在最優(yōu)解位置用泰勒展開式展開:

(5)

(6)

根據(jù)量子理論，在勢阱V(x)=f(x)約束條件下可以準確獲得波函數(shù)，不同能級的波函數(shù)如圖1所示。

圖1 諧振子波函數(shù)概率密度隨能級變化示意圖

2 云計算任務調(diào)度設計

2.1 MQHOA的3個迭代過程

1)能級穩(wěn)定過程。

2)能級降低過程。

3)尺度降低過程。

單一尺度是無法對目標函數(shù)的最小值點進行逼近的，MQHOA中存在尺度降低過程，當2)中能級降低過程達到能量基態(tài)時，尺度減半σs=σs/2，直到σs小于等于設定的最小搜索尺度σmin跳出，最終算法停止得到最優(yōu)解。

2.2 MQHOA求解云計算任務調(diào)度問題

云計算任務調(diào)度是一個離散優(yōu)化問題，在云計算任務調(diào)度問題中，基于MQHOA的任務調(diào)度算法將每一個調(diào)度方案看成一個采樣位置，目標函數(shù)是總?cè)蝿照{(diào)度時間。將每一個任務看成一個維度，每個任務有n個虛擬機可以選擇，其范圍為{0,1,…,n-1}，則可得σs=n-1，對每一維度進行高斯采樣都需要取整，在尺度降低過程中，尺度每次迭代降低至原來的1/λ，即σs=σs/λ，而且算法在尺度降低到σmin=1時停止。在能級降低的過程中，通常將函數(shù)優(yōu)化中的最壞值點替換成平均值在離散優(yōu)化中沒有意義，這里直接替換成最優(yōu)值點。

MQHOA求解云計算任務調(diào)度問題的偽代碼為：

為了方便理解，假設有3個虛擬機、5個任務，則生成的調(diào)度方案的分配矩陣可能是：

(7)

在調(diào)度方案形成的分配矩陣中，列代表每一個維度，第一個任務選擇了第二個虛擬機，則分配矩陣中第二行第一列為1，同一列其他行為0，對于這一維度的初始高斯采樣按照N(1,22)進行，生成的新的值然后取整，各個維度高斯采樣完成之后就生成了新的調(diào)度方案。

3 實驗結(jié)果及分析

CloudSim[13]是澳大利亞墨爾本大學Rajkumar Buyya博士領(lǐng)導團隊開發(fā)的云計算仿真平臺，主要用于模擬云環(huán)境，對不同的應用和服務模型的調(diào)度策略進行性能測試。在CloudSim中，DatacenterBroker類模擬了一個代理，負責根據(jù)服務質(zhì)量需求在線協(xié)商服務與資源的分配策略。對于一個新的任務調(diào)度算法，用戶可以通過在DatacenterBroker中加入新的方法實現(xiàn)任務調(diào)度策略，從而完成該算法的模擬，本文中的算法都是通過修改DatacenterBroker類實現(xiàn)。

在基于MQHOA的任務調(diào)度算法的尺度降低過程中，尺度每次迭代降低至原來的1/λ。λ可以看作一個可調(diào)節(jié)收斂速度的參數(shù)，這并不是函數(shù)優(yōu)化中每次迭代后尺度減半，這是因為尺度減半在處理類似云計算調(diào)度的離散優(yōu)化問題過程中，每次搜索后收斂的速度過快，在還沒有找到一個相對最優(yōu)解的情況下，采樣點的活動區(qū)域大大減小，這對于依賴于隨機搜索的算法來說，很難跳出局部最優(yōu)，尋找最優(yōu)解的概率變得很低。文獻[14]中用MQHOA求解旅行商問題時，設定λ值為1.1，旅行商問題與云計算調(diào)度問題類似，在本文實驗中，設定基于MQHOA的任務調(diào)度算法的λ值為1.1，使收斂的速度變緩，迭代次數(shù)相對增加，尋優(yōu)能力更強。

在5個虛擬計算資源、200個任務和5個虛擬計算資源、500個任務兩種調(diào)度規(guī)模下，通過算法迭代次數(shù)與總?cè)蝿胀瓿蓵r間之間的關(guān)系對MQHOA與粒子群優(yōu)化算法進行比較。實驗中虛擬計算資源的處理能力分別是[1 700,2 800,3 600,500,1 200] MIPS(Million Instructions Per Second)，任務的長度在范圍[1 000,4 000] MI(Million Instructions)中均勻分布。所比較的粒子群算法參數(shù)設置為群體規(guī)模size為10，局部權(quán)重c1與全局權(quán)重c2都為2，慣性權(quán)重w根據(jù)經(jīng)驗值設為0.728，最大迭代次數(shù)設置為300，實驗結(jié)果如圖2所示。

從圖2可以看出，MQHOA與PSO算法在前期10次迭代之內(nèi)都有很快的收斂速度，PSO算法的下降速度明顯小于MQHOA的下降速度，在50次迭代之后，PSO算法有一段時間趨于平衡，這是因為PSO算法前期收斂速度快，后期局部搜索能力不足，但是MQHOA直到滿足條件退出迭代之前都有很強的局部搜索能力，所以在MQHOA的執(zhí)行期間內(nèi)，總?cè)蝿胀瓿蓵r間都有下降。

MQHOA的迭代次數(shù)一般在100以內(nèi)，PSO算法在迭代次數(shù)大于150后，總?cè)蝿胀瓿蓵r間還有下降，設定最大的迭代次數(shù)為250，分別利用前面的條件隨機生成{100,200,300,400,500}個任務，得到FCFS算法、PSO算法和MQHOA在各個虛擬計算資源上的運行時間(保留兩位小數(shù))如表1所示。

分析表1得到，基于MQHOA的任務調(diào)度算法在不同的任務集上總?cè)蝿胀瓿蓵r間與3號虛擬計算資源的執(zhí)行時間一致，這是因為3號虛擬計算資源的計算能力最差，而MQHOA是利用高斯采樣隨機尋解的智能算法，無法避免地將一定規(guī)模的任務分配給3號虛擬計算資源。在不同規(guī)模的任務集中，可以看出MQHOA總?cè)蝿胀瓿蓵r間最短，分別為{40.35,89.74,147.23,185.12,268.07}，相比FCFS算法，能夠減少50%～60%，相比PSO算法，能夠減少10%～20%。

圖2 完成時間與迭代次數(shù)關(guān)系

表1 算法在不同任務數(shù)量下虛擬計算資源的執(zhí)行時間 s

定義任務負載不均值(Degree of Imbalance， DI)為：

DI=(Cmax-Cmin)/Cavg

(8)

其中：Cmax為虛擬計算資源執(zhí)行任務時間最長的時間，也就是總?cè)蝿胀瓿蓵r間；Cmin是虛擬計算資源執(zhí)行任務時間最短的時間；Cavg是所有虛擬計算資源執(zhí)行任務時間的平均時間，通過對任務負載不均值的計算，可以對完成任務調(diào)度后的虛擬機負載情況進行測量，對比三種算法在不同任務集上的負載情況，可以得到圖3。由圖3可以看出，F(xiàn)CFS算法的DI在不同的任務集上都維持一個相對穩(wěn)定的狀態(tài)，但是PSO算法和MQHOA在任務數(shù)量增多的情況下DI的趨勢是上升，MQHOA上升的幅度比較緩慢，在任務數(shù)量達到一定量后，總體上趨于平衡，這表明MQHOA在適用于不同任務集上穩(wěn)定性強于PSO算法。在不同的實驗任務集上，MQHOA的DI保持在0.3～1.1的范圍，比FCFS算法降低了1～1.5，比PSO算法降低了0.4～0.8。在云計算任務調(diào)度中，基于MQHOA的任務調(diào)度算法在總?cè)蝿者\行時間最短的情況下，也能有效地實現(xiàn)負載均衡，相比其他算法的優(yōu)勢明顯。

4 結(jié)語

本文首次提出一種基于多尺度量子諧振子算法的云計算任務調(diào)度算法，該算法將任務分配到虛擬機的調(diào)度方案看成一個采樣位置，利用高斯采樣產(chǎn)生新的相對最優(yōu)解，利用尺度下降來精確聚焦最優(yōu)解的位置。基于MQHOA的任務調(diào)度算法具有數(shù)學結(jié)構(gòu)簡單、參數(shù)控制少的特點，在多樣化的任務調(diào)度需求中適應能力更強。通過CloudSim模擬實驗，得到MQHOA相比PSO算法和FCFS算法能夠快速收斂，顯著降低任務執(zhí)行時間。在要求快速響應和負載均衡的云計算環(huán)境中，MQHOA性能明顯優(yōu)于FCFS算法和PSO算法。

圖3 3種算法的DI值

在下一步的工作中，有兩點還需進一步研究：第一，本文中基于MQHOA的任務調(diào)度算法在能級降低過程中，替換成最優(yōu)點的操作會丟失解空間信息，可能導致陷入局部最優(yōu)，可改進算法以增強全局搜索能力。第二，本文中只考慮了任務調(diào)度的時間因素和負載均衡，后續(xù)還將考慮任務之間的通信、任務優(yōu)先級、計算成本、能耗，綜合各種因素，使云計算任務調(diào)度在綜合性能上達到最優(yōu)。

References)

[1] MAHESH R, VINOD A P. A new common subexpression elimination algorithm for realizing low-complexity higher order digital filters [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(2): 217-229.

[2] KLLAPI H, SITARIDI E, TSANGARIS M M, et al. Schedule optimization for data processing flows on the cloud [C]// SIGMOD 2011: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2011: 289-300.

[4] GUO L, ZHAO S, SHEN S, et al. Task scheduling optimization in cloud computing based on heuristic algorithm [J]. Journal of Networks, 2012, 7(3): 1-4.

[5] LI J F, PENG J, CAO X, et al. A task scheduling algorithm based on improved ant colony optimization in cloud computing environment [J]. Energy Procedia, 2011, 13: 6833-6840.

[6] ZHAO C, ZHANG S, LIU Q, et al. Independent tasks scheduling based on genetic algorithm in cloud computing [C]// WiCom ’09: Proceedings of the 5th International Conference on Wireless Communications, Networking and Mobile Computing. Piscataway: IEEE, 2009: 1-4.

[7] 王鵬.云計算的關(guān)鍵技術(shù)與應用實例[M].北京:人民郵電出版社,2010:168-194.(WANG P. The Key Technology and Application Examples of Cloud Computing [M]. Beijing: Posts and Telecom Press, 2010: 168-194.)

[8] 王鵬,黃焱,任超,等.多尺度量子諧振子高維函數(shù)全局優(yōu)化算法[J].電子學報,2013,41(12):2468-2473.(WANG P, HUANG Y, REN C, et al. Multi-scale quantum harmonic oscillator for high dimensional function global optimization algorithm [J]. Acta Electronica Sinica, 2013, 41(12): 2468-2473.)

[9] 王鵬,黃焱.具有能級穩(wěn)定過程的MQHOA優(yōu)化算法[J].通信學報,2016,37(7):79-86.(WANG P, HUANG Y. MQHOA algorithm with energy level stabilizing process [J]. Journal on Communications, 2016, 37(7): 79-86.)

[10] 倪霖,段超,鐘輝.基于模擬諧振子算法的多項目調(diào)度[J].計算機應用,2011,31(9):2559-2562.(NI L, DUAN C, ZHONG H. Multi-project scheduling based on simulated harmonic oscillator algorithm [J]. Journal of Computer Applications, 2011, 31(9): 2559-2562.)

[11] 袁亞男,王鵬,劉峰.多尺度量子諧振子算法性能分析[J].計算機應用,2015,35(6):1600-1604.(YUAN Y N, WANG P, LIU F. Performance analysis of multi-scale quantum harmonic oscillator algorithm [J]. Journal of Computer Applications, 2015, 35(6): 1600-1604.)

[12] 王鵬,黃焱.多尺度量子諧振子優(yōu)化算法物理模型[J].計算機科學與探索,2015,9(10):1271-1280.(WANG P, HUANG Y. Physical model of multi-scale quantum harmonic oscillator optimization algorithm [J]. Journal of Frontiers of Computer Science & Technology, 2015, 9(10): 1271-1280.)

[13] CALHEIROS R N, RANJAN R, BELOGLAZOV A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software Practice & Experience, 2011, 41(1):23-50.

[14] 王鵬,黃焱,安俊秀,等.多尺度量子諧振子算法在組合優(yōu)化問題中的性能分析[J].電子科技大學學報,2016,45(3):469-474.(WANG P, HUANG Y, AN J X, et al. Performance analysis of multi-scale quantum harmonic oscillator global optimization algorithm in combinatorial optimization problems [J]. Journal of University of Electronic Science and Technology of China, 2016, 45(3): 469-474.)

This work is partially supported by the National Natural Science Foundation of China (60702075), the Fundamental Research Funds for the Central Universities of Southwest University for Nationalities (2017NZYQN27), the Sichuan Province Science Foundation for Youths (09ZQ026- 068).

HANHu, born in 1992, M. S. candidate. His research interests include cloud computing, distributed computing.

WANGPeng, born in 1975, Ph. D., professor. His research interests include cloud computing, parallel computing, quantum computing.

CHENGKun, born in 1987, Ph. D. candidate. Her research interests include cloud computing, quantum computing.

LIBo, born in 1980, Ph. D. candidate. His research interests include cloud computing, quantum computing.

Taskschedulingalgorithmforcloudcomputingbasedonmulti-scalequantumharmonicoscillatoralgorithm

HAN Hu1,2, WANG Peng3*, CHENG Kun1,2, LI Bo1,2

(1.ChengduInstituteofComputerApplication,ChineseAcademyofSciences,ChengduSichuan610041,China;2.UniversityofChineseAcademyofSciences,Beijing100049,China;3.SchoolofComputerScienceandTechnology,SouthwestUniversityforNationalities,ChengduSichuan610225,China)

Reasonable virtual machine allocating and efficient task scheduling is a key problem in the cloud computing. In order to better use virtual machine and make the system meet the service requests efficiently, a task scheduling algorithm based on Multi-scale Quantum Harmonic Oscillator Algorithm (MQHOA) was proposed. Firstly, each scheduling scheme was regarded as a sampling position, and then the randomness of Gaussian sampling was used to search the local optimal solution at the current scale. Then, whether the energy level was stable was judged. If the energy level was stable, it would enter the descent process and the worst scheduling scheme would be replaced. Finally, when the algorithm entered the process of scale reduction, the algorithm transitioned from global search to local search, eventually terminated and delivered the optimal result after several iterations. The simulation experiment results on CloudSim platform show that the makespan of task scheduling of MQHOA decreased by more than 10% and the degree of imbalance fell more than 0.4 in comparison with First Come First Serviced (FCFS) algorithm and Particle Swarm Optimization (PSO) algorithm. The experimental results show that the proposed algorithm has fast convergence rate and good characteristics of global convergence and adaptability. The task scheduling algorithm based on MQHOA can reduce the makespan of task scheduling and maintain the load balance of virtual machines in cloud computing.

Multi-scale Quantum Harmonic Oscillator Algorithm (MQHOA); cloud computing; task scheduling; fast convergence; load balancing

TP301.6

:A

2016- 12- 08;

:2017- 02- 26。

國家自然科學基金資助項目(60702075);西南民族大學中央高校基本科研業(yè)務費專項(2017NZYQN27);四川省青年科學基金資助項目(09ZQ026- 068)。

韓虎(1992—)，男，湖北黃岡人，碩士研究生，主要研究方向：云計算、分布式計算； 王鵬(1975—)，男，四川樂山人，教授，博士，CCF會員，主要研究方向：云計算、并行計算、量子算法； 程琨(1987—)，女，山東泰安人，博士研究生，主要研究方向：云計算、量子算法；李波(1980—)，男，山東泰安人，博士研究生，主要研究方向：云計算、量子算法。

1001- 9081(2017)07- 1888- 05

10.11772/j.issn.1001- 9081.2017.07.1888