计算机应用 ›› 2017, Vol. 37 ›› Issue (7): 1888-1892.DOI: 10.11772/j.issn.1001-9081.2017.07.1888

• 先进计算 • 上一篇    下一篇

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

韩虎1,2, 王鹏3, 程琨1,2, 李波1,2   

  1. 1. 中国科学院 成都计算机应用研究所, 成都 610041;
    2. 中国科学院大学, 北京 100049;
    3. 西南民族大学 计算机科学与技术学院, 成都 610225
  • 收稿日期:2016-12-08 修回日期:2017-02-26 出版日期:2017-07-10 发布日期:2017-07-18
  • 通讯作者: 王鹏
  • 作者简介:韩虎(1992-),男,湖北黄冈人,硕士研究生,主要研究方向:云计算、分布式计算;王鹏(1975-),男,四川乐山人,教授,博士,CCF会员,主要研究方向:云计算、并行计算、量子算法;程琨(1987-),女,山东泰安人,博士研究生,主要研究方向:云计算、量子算法;李波(1980-),男,山东泰安人,博士研究生,主要研究方向:云计算、量子算法。
  • 基金资助:
    国家自然科学基金资助项目(60702075);西南民族大学中央高校基本科研业务费专项(2017NZYQN27);四川省青年科学基金资助项目(09ZQ026-068)。

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

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

  1. 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).

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

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

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

中图分类号: