基于多尺度量子谐振子算法的云计算任务调度
|
摘要
合理地分配虚拟计算资源以进行有效的任务调度是云计算中的一个核心问题。为了更好地利用虚拟计算资源,高效地完成服务需求,提出了一种基于多尺度量子谐振子算法(MQHOA)的任务调度算法。首先,该算法将每一个调度方案当成一个采样位置,利用高斯采样的随机性在当前尺度下搜索局部最优解;其次,判断算法是否处于能级稳定状态,如果稳定,则进入能级降低过程,最坏的调度方案将被替换;最后,算法进入尺度下降的过程,算法由全局搜索过渡到局部搜索,迭代多次之后,算法停止并输出找到的最优结果。通过在Cloud Sim平台上进行仿真实验,与现有的先来先服务(FCFS)算法和粒子群优化(PSO)算法对比,MQHOA总任务完成时间减少10%以上,负载不均值下降0.4以上。实验结果表明,基于MQHOA的任务调度算法能够快速收敛,有良好的全局收敛性和自适应能力,在云计算任务调度过程中,能够起到减少总任务完成时间和均衡负载的作用。
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 Cloud Sim 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.
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 Cloud Sim 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.
引文
[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]//SIGMOD2011:Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data.New York:ACM,2011:289-300.
[3]ASSUNCAO 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 environmen[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]//Wi Com'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,HUANGY,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,LIUF.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.)
[2]KLLAPI H,SITARIDI E,TSANGARIS M M,et al.Schedule optimization for data processing flows on the cloud[C]//SIGMOD2011:Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data.New York:ACM,2011:289-300.
[3]ASSUNCAO 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 environmen[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]//Wi Com'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,HUANGY,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,LIUF.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.)