Task scheduling algorithm for cloud computing based on multi-scale quantum harmonic oscillator algorithm

doi:10.11772/j.issn.1001-9081.2017.07.1888

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (7): 1888-1892.DOI: 10.11772/j.issn.1001-9081.2017.07.1888

Previous Articles Next Articles

Task scheduling algorithm for cloud computing based on multi-scale quantum harmonic oscillator algorithm

HAN Hu^1,2, WANG Peng³, CHENG Kun^1,2, LI Bo^1,2

1. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu Sichuan 610041, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China;
3. School of Computer Science and Technology, Southwest University for Nationalities, Chengdu Sichuan 610225, China

Received:2016-12-08 Revised:2017-02-26 Online:2017-07-10 Published:2017-07-18
Supported by:
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).

基于多尺度量子谐振子算法的云计算任务调度

韩虎^1,2, 王鹏³, 程琨^1,2, 李波^1,2

1. 中国科学院成都计算机应用研究所, 成都 610041;
2. 中国科学院大学, 北京 100049;
3. 西南民族大学计算机科学与技术学院, 成都 610225

通讯作者: 王鹏
作者简介:韩虎(1992-),男,湖北黄冈人,硕士研究生,主要研究方向:云计算、分布式计算;王鹏(1975-),男,四川乐山人,教授,博士,CCF会员,主要研究方向:云计算、并行计算、量子算法;程琨(1987-),女,山东泰安人,博士研究生,主要研究方向:云计算、量子算法;李波(1980-),男,山东泰安人,博士研究生,主要研究方向:云计算、量子算法。
基金资助:
国家自然科学基金资助项目（60702075）；西南民族大学中央高校基本科研业务费专项（2017NZYQN27）；四川省青年科学基金资助项目（09ZQ026-068）。

Abstract

Abstract: 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.

Key words: Multi-scale Quantum Harmonic Oscillator Algorithm (MQHOA), cloud computing, task scheduling, fast convergence, load balancing

摘要： 合理地分配虚拟计算资源以进行有效的任务调度是云计算中的一个核心问题。为了更好地利用虚拟计算资源，高效地完成服务需求，提出了一种基于多尺度量子谐振子算法（MQHOA）的任务调度算法。首先，该算法将每一个调度方案当成一个采样位置，利用高斯采样的随机性在当前尺度下搜索局部最优解；其次，判断算法是否处于能级稳定状态，如果稳定，则进入能级降低过程，最坏的调度方案将被替换；最后，算法进入尺度下降的过程，算法由全局搜索过渡到局部搜索，迭代多次之后，算法停止并输出找到的最优结果。通过在CloudSim平台上进行仿真实验，与现有的先来先服务（FCFS）算法和粒子群优化（PSO）算法对比，MQHOA总任务完成时间减少10%以上，负载不均值下降0.4以上。实验结果表明，基于MQHOA的任务调度算法能够快速收敛，有良好的全局收敛性和自适应能力，在云计算任务调度过程中，能够起到减少总任务完成时间和均衡负载的作用。

关键词: 多尺度量子谐振子算法, 云计算, 任务调度, 快速收敛, 负载均衡

CLC Number:

TP301.6

HAN Hu, WANG Peng, CHENG Kun, LI Bo. Task scheduling algorithm for cloud computing based on multi-scale quantum harmonic oscillator algorithm[J]. Journal of Computer Applications, 2017, 37(7): 1888-1892.

韩虎, 王鹏, 程琨, 李波. 基于多尺度量子谐振子算法的云计算任务调度[J]. 计算机应用, 2017, 37(7): 1888-1892.

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.
[3] ASSUNÇÄO M D, COSTANZO A, BUYYA R. A cost-benefit analysis of using cloud computing to extend the capacity of clusters[J]. Cluster Computing, 2010, 13(3):335-347.
[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] 王鹏.云计算的关键技术与应用实例[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] 王鹏,黄焱,任超,等.多尺度量子谐振子高维函数全局优化算法[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] 王鹏,黄焱.具有能级稳定过程的MQHOA优化算法[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] 倪霖,段超,钟辉.基于模拟谐振子算法的多项目调度[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] 王鹏,黄焱.多尺度量子谐振子优化算法物理模型[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] 王鹏,黄焱,安俊秀,等.多尺度量子谐振子算法在组合优化问题中的性能分析[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.)

[1]	ZHAO Quan, TANG Xiaochun, ZHU Ziyu, MAO Anqi, LI Zhanhuai. Low-latency cluster scheduling framework for large-scale short-time tasks [J]. Journal of Computer Applications, 2021, 41(8): 2396-2405.
[2]	CHEN Jiahao, YIN Xinchun. Traceable and revocable ciphertext-policy attribute-based encryption scheme based on cloud-fog computing [J]. Journal of Computer Applications, 2021, 41(6): 1611-1620.
[3]	GE Lina, HU Yugu, ZHANG Guifen, CHEN Yuanyuan. Reverse hybrid access control scheme based on object attribute matching in cloud computing environment [J]. Journal of Computer Applications, 2021, 41(6): 1604-1610.
[4]	XU Hongliang, YANG Guiqin, JIANG Zhanjun. Data center adaptive multi-path load balancing algorithm based on software defined network [J]. Journal of Computer Applications, 2021, 41(4): 1160-1164.
[5]	YANG Ling, JIANG Chunmao. Strategy of energy-aware virtual machine migration based on three-way decision [J]. Journal of Computer Applications, 2021, 41(4): 990-998.
[6]	Fan PING, Xiaochun TANG, Yanyu PAN, Zhanhuai LI. Scheduling strategy of irregular tasks on graphics processing unit cluster [J]. Journal of Computer Applications, 2021, 41(11): 3295-3301.
[7]	Xiaoling SUN, Guang YANG, Yanping SHEN, Qiuge YANG, Tao CHEN. Searchable encryption scheme based on splittable inverted index [J]. Journal of Computer Applications, 2021, 41(11): 3288-3294.
[8]	LYU Jiayu, ZHU Zhirong, YAO Zhiqiang. Two-channel dynamic data encryption strategy in cloud computing environment [J]. Journal of Computer Applications, 2020, 40(8): 2268-2273.
[9]	CHEN Chengjun, MAO Yingchi, WANG Yichao. CNN model compression based on activation-entropy based layer-wise iterative pruning strategy [J]. Journal of Computer Applications, 2020, 40(5): 1260-1265.
[10]	GUO Shujie, LI Zhihua, LIN Kaiqing. Fuzzy membership degree based virtual machine placement algorithmin cloud environment [J]. Journal of Computer Applications, 2020, 40(5): 1374-1381.
[11]	XU Yingxin, SUN Lei, ZHAO Jiancheng, GUO Songhui. Virtual field programmable gate array placement strategy based on ant colony optimization algorithm [J]. Journal of Computer Applications, 2020, 40(3): 747-752.
[12]	LI Cui, CHEN Qingkui. Dynamic monitoring model based on DPDK parallel communication [J]. Journal of Computer Applications, 2020, 40(2): 335-341.
[13]	LIU Zhixiang, LIU Huichao, HUANG Dongmei, ZHOU Liping, SU Cheng. IB-LBM parallel optimization method mixed with multiple task scheduling modes [J]. Journal of Computer Applications, 2020, 40(2): 386-391.
[14]	WANG Qingyong, MAO Yingchi, WANG Yichao, WANG Longbao. Computing task offloading based on multi-cloudlet collaboration [J]. Journal of Computer Applications, 2020, 40(2): 328-334.
[15]	LIU Fuxin, LI Jingwei, WANG Yihong, LI Lin. Design and implementation of cloud native massive data storage system based on Kubernetes [J]. Journal of Computer Applications, 2020, 40(2): 547-552.

Task scheduling algorithm for cloud computing based on multi-scale quantum harmonic oscillator algorithm

基于多尺度量子谐振子算法的云计算任务调度

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics