基于遗传算法的网格任务调度研究
|
摘要
网格计算系统实现了不同地理分布的异构资源的共享、选择和聚合,以解决在科研、工程、经济学等领域大规模的计算问题。网格任务调度问题是网格领域的关键问题之一,它是以某一评价指标为依据,针对如何将提交的任务分配到相应的网格资源上运行的问题,提出一个合理有效的调度方案。调度策略的优劣决定了是否能够高效合理地分配和利用网格资源,减少网格任务的总体计算时间和花费,使得网格的性能达到最佳。网格环境下的任务调度问题是网格计算的研究热点之一。
论文重点研究了以下几方面的内容:
①在综述网格计算的研究背景及意义的基础上,较全面地分析了网格任务调度的特点及其常用的调度算法。
②提出了一种改进的基于遗传算法的网格任务调度算法,在算法的初始化种群产生时引入Min-Min算法和Max-Min算法以及采用Hamming距离来控制个体之间的差异,从而在提高初始种群质量的同时保证了种群的多样性;在算法的迭代过程中提出了一种新的局部收敛判定标准以及相应的变异操作来防止算法的局部收敛。
③在本文的任务调度算法中采用DAG(Directed Acyclic Graph)模型来描述并行任务之间的约束依赖关系,DAG模型更能真实地反映并行任务的实际情况,此外本文中的算法设计还考虑了处理器异构等因素。
④构建现实当中的网格环境不仅花销昂贵,而且时间上也不允许,且网格资源还具有多样性和动态性等特性,因此利用实际网格系统来测试网格任务调度算法的性能和效率是不现实的,也是很困难的。一般地,我们借助网格模拟工具来进行相应的仿真试验。作者利用GridSim网格模拟器对本文改进的网格任务调度算法进行了仿真实验,从最优跨度的角度对实验结果进行详细的对比和分析。
实验结果表明,本文改进后的种群初始化方法不仅能够提高算法的寻优起点,而且能够加快算法的寻优速度;改进后的局部收敛判定标准及相应的局部收敛变异操作在预防早熟局部收敛的同时能够提高算法的全局寻优能力;改进后的基于遗传算法的网格任务调度算法相比于基于自适应遗传算法的调度算法,能够有效地缩短任务的总体执行时间,并且在大规模的网格任务调度环境下具有良好的性能,能够在实际网格环境中加以应用。
Grid computing is becoming a more and more important in the high performance computing due to the fact that it enables the sharing, selection, and aggregation of geographically distributed heterogeneous resources for solving large-scale problems in the field of science, engineering, and commerce. Task scheduling is an important part of grid computing. Grid task scheduling resolves how to reasonably assign grid resources to tasks, and how to schedule every task to the assigned grid resources. A good scheduling policy can improve the rational allocation and efficient use of grid resources and reduces the overall grid task computing time and cost, making the best performance of the grid. So task scheduling under grid environments is one of the key research fields of grid systems.
The main research works of this paper are listed as follows:
①The features and common scheduling algorithms of grid task scheduling are analyzed through summarizing the research background and significance of grid computing.
②An improved grid task scheduling algorithm based on genetic algorithm is proposed. In the process of population initialization, a new method which combines the Min-Min algorithm and the Max-Min algorithm is addressed, and it uses hamming distance to control the difference among the individuals. Therefore, the new method can not only improve the quality of initial population, but also ensure the diversity of population. In the evolution of the population, a new criterion predicting the premature convergence is presented and the corresponding improved mutation is designed to avoid premature convergence.
③The DAG (Directed Acycle Graph) model is adopted to describe the relation among parallel tasks in the genetic algorithm. This kind of model has better capacity to illuminate the actual state of parallel job than the other model. The factor of different processing capacity of CPU is also considered in our algorithm.
④Building an actual grid environment is not only expensive but also time-consuming, moreover considering the diversity and dynamic of grid resources, it is quite difficult to confirm the performance and validity of grid task scheduling algorithm through actual grid system. Generally, we use grid simulators to handle with the simulation work. The author does a prototype exeriment of the algorithms on the GridSim simulation platform, and analyzes the exerimental results in detail from the point of view about the makespan.
The experimental results are analyzed in detail, and the simulation shows that the improved population initialization method can not only improve the starting point of the algorithm optimization, but also accelerate the speed of algorithm optimization. The improved premature convergence judgement criterion and the corresponding improved mutation can predicte the premature convergence and improve the ability of global optimization. In the grid task scheduling, the proposed algorithm is better than the adaptive genetic algorithm, it can effectively reduce the overall execution time of the total tasks, and have good performance in large-scale grid task scheduling environment, so it can be used in the real grid environment.
论文重点研究了以下几方面的内容:
①在综述网格计算的研究背景及意义的基础上,较全面地分析了网格任务调度的特点及其常用的调度算法。
②提出了一种改进的基于遗传算法的网格任务调度算法,在算法的初始化种群产生时引入Min-Min算法和Max-Min算法以及采用Hamming距离来控制个体之间的差异,从而在提高初始种群质量的同时保证了种群的多样性;在算法的迭代过程中提出了一种新的局部收敛判定标准以及相应的变异操作来防止算法的局部收敛。
③在本文的任务调度算法中采用DAG(Directed Acyclic Graph)模型来描述并行任务之间的约束依赖关系,DAG模型更能真实地反映并行任务的实际情况,此外本文中的算法设计还考虑了处理器异构等因素。
④构建现实当中的网格环境不仅花销昂贵,而且时间上也不允许,且网格资源还具有多样性和动态性等特性,因此利用实际网格系统来测试网格任务调度算法的性能和效率是不现实的,也是很困难的。一般地,我们借助网格模拟工具来进行相应的仿真试验。作者利用GridSim网格模拟器对本文改进的网格任务调度算法进行了仿真实验,从最优跨度的角度对实验结果进行详细的对比和分析。
实验结果表明,本文改进后的种群初始化方法不仅能够提高算法的寻优起点,而且能够加快算法的寻优速度;改进后的局部收敛判定标准及相应的局部收敛变异操作在预防早熟局部收敛的同时能够提高算法的全局寻优能力;改进后的基于遗传算法的网格任务调度算法相比于基于自适应遗传算法的调度算法,能够有效地缩短任务的总体执行时间,并且在大规模的网格任务调度环境下具有良好的性能,能够在实际网格环境中加以应用。
Grid computing is becoming a more and more important in the high performance computing due to the fact that it enables the sharing, selection, and aggregation of geographically distributed heterogeneous resources for solving large-scale problems in the field of science, engineering, and commerce. Task scheduling is an important part of grid computing. Grid task scheduling resolves how to reasonably assign grid resources to tasks, and how to schedule every task to the assigned grid resources. A good scheduling policy can improve the rational allocation and efficient use of grid resources and reduces the overall grid task computing time and cost, making the best performance of the grid. So task scheduling under grid environments is one of the key research fields of grid systems.
The main research works of this paper are listed as follows:
①The features and common scheduling algorithms of grid task scheduling are analyzed through summarizing the research background and significance of grid computing.
②An improved grid task scheduling algorithm based on genetic algorithm is proposed. In the process of population initialization, a new method which combines the Min-Min algorithm and the Max-Min algorithm is addressed, and it uses hamming distance to control the difference among the individuals. Therefore, the new method can not only improve the quality of initial population, but also ensure the diversity of population. In the evolution of the population, a new criterion predicting the premature convergence is presented and the corresponding improved mutation is designed to avoid premature convergence.
③The DAG (Directed Acycle Graph) model is adopted to describe the relation among parallel tasks in the genetic algorithm. This kind of model has better capacity to illuminate the actual state of parallel job than the other model. The factor of different processing capacity of CPU is also considered in our algorithm.
④Building an actual grid environment is not only expensive but also time-consuming, moreover considering the diversity and dynamic of grid resources, it is quite difficult to confirm the performance and validity of grid task scheduling algorithm through actual grid system. Generally, we use grid simulators to handle with the simulation work. The author does a prototype exeriment of the algorithms on the GridSim simulation platform, and analyzes the exerimental results in detail from the point of view about the makespan.
The experimental results are analyzed in detail, and the simulation shows that the improved population initialization method can not only improve the starting point of the algorithm optimization, but also accelerate the speed of algorithm optimization. The improved premature convergence judgement criterion and the corresponding improved mutation can predicte the premature convergence and improve the ability of global optimization. In the grid task scheduling, the proposed algorithm is better than the adaptive genetic algorithm, it can effectively reduce the overall execution time of the total tasks, and have good performance in large-scale grid task scheduling environment, so it can be used in the real grid environment.
引文
[1]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社, 2002: 27-35.
[2]房向明,杨寿保,郭磊涛,张蕾.网格计算系统的安全体系结构模型研究[M].北京:清华大学出版社, 2003: 36-43.
[3] Foster I, Kesselman M. The Grid: Blueprint for a Future Computing Infrastructure[M]. USA: Morgan Kaufmann Publishers, 1999: 326-332.
[4] Beman F, Fox G, Tony H. Grid Computing-making the Global Infrastructure a Reality[M]. USA: John Wiley and Sons Ltd, 2003: 65-100.
[5] Andronikos T, Koziris N. Optimal Scheduling for UET-UCT Grids Into Fixed Number of Processors[C]. In: Proceedings of 8th Euromicro Workshop on Parallel and Distributed Processing. IEEE Press, 2000: 237-243.
[6]罗红,慕德俊,邓智群等.网格计算中任务调度研究综述[J].计算机应用研究, 2005, 22(5): 16-19.
[7]许智宏,孙竞,孙济洲.一种基于组件的安全网格环境[J].计算机工程, 2004, (21): 111-112.
[8] Foster I, Geisler J, Nickless W, et al. Software Infrastructure for the I-WAY High Performance Distributed Computing Experiment[C]. Proceedings of the 5th IEEE Symposium on High Performance Distributed Computing, 1997: 562-571.
[9] Foster I, Kesselman C. The Grid: Blueprint for a New Computing Infrastructure[M]. San Francisco: Morgan Kaufmann Publishers, 1998: 279-309.
[10]徐志伟,李伟.织女星网格的体系结构研究[J].计算机研究与发展, 2002, 39 (8): 37-39.
[11] A. S. Tanenbaun著,陆丽娜等译. Distributed Operating Systems[M].北京:电子工业出版社, 1999: 77-82.
[12] Beman F, Fox G, Tony H. Grid Computing-making the Global Infrastructure a Reality[M]. USA: John Wiley and Sons Ltd, 2003: 65-80.
[13] Foster I, Kesselman C. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration[EB/OL]. Http//www.globus.org/research/papers.html, 2002: 77-83.
[14]吴高锋,蒋玉明等.基于QoS改进的Min-Min网格调度算法[J].微计算机信息, 2009, 9(3): 110-112.
[15]马满福,吴健,陈丁剑等.网格经济模型中基于信誉度的资源选择[J].计算机工程, 2006, 32(17): 175-177.
[16]杨博,陈志刚.一种基于双层进化结构的网格任务调度算法[J].计算机工程与应用, 2006, 42(15): 8-10.
[17]李向荣.网格资源管理与调度算法的研究与实现[D].南京航空航天大学硕士学位论文, 2006: 56-63.
[18] Spooner D P, Jarvis S A. Local Grid Scheduling Techniques using Performance Predition[J], IEEE Proceedings-Computers and Digital Techniques, 2003, 150(2): 87-96.
[19]熊平华.基于网格计算平台的智能优化算法应用与研究[D].浙江大学硕士学位论文, 2004: 6-13.
[20]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社, 2002: 89-93.
[21] Zhihong Xu, Xiangdan Hou, Jizhou Sun. Ant algorithm-based task scheduling in grid computing[C]. In: Proceedings of 2003-Canadian Conf on Electrical and Computer Engineering. USA: IEEE Computer Society Press, 2003, 2: 1107-1110.
[22]杨浩.模型与算法[M].北京:北京交通大学出版社, 2002: 57-63.
[23]陈国良等著.遗传算法及其应用[M].北京:人民邮电出版社, 1996: 124-129.
[24]李敏强,寇纪松,林丹等.遗传算法的基本原理与应用[M].北京:科学出版社, 2002: 77-81.
[25] Ervin Laszlo,阂家撒等.进化一广义综合理论[M].北京:社会科学文献出版社, 1988: 42-45.
[26]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社, 2000: 33-47.
[27] Xiong ZH, Li SK, Chen JH. Hardware/Soflware partitioning based on dynamic combination of genetic algorithm and ant algorithm. Journal of Software, 2005, 16(4): 503-512.
[28]郝翔.遗传算法及其在规则优化中的应用研究[D].西安交通大学博士论文, 1997: 63-66.
[29]黄宝边,曾文华.网格计算中基于信任机制的动态任务调度[J].计算机应用, 2006, 26(1): 65-69.
[30]梁鸿,田世峰.基于改进蚂蚁算法的网格任务调度策略研究[J].计算机技术, 2006(11): 42-44.
[31] Jelodar M S, Fakhraie S N, Montazeri F, et al. A Representation for Genetic Alogorithm Based Multiprocessor Task Scheduling[C]. 2006 IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada, July, 2006: 16-21.
[32] Spooner D P, Jarvis S A. Local Grid Scheduling Techniques using Performance Predition[J], IEEE Proceedings-Computers and Digital Techniques, 2003, 150(2): 87-96.
[33]袁禄来,曾国荪,姜黎立等.网格环境下基于信任模型的动态级调度[J].计算机学报, 2006, 29(7): 1217-1224.
[34]黄金贵,陈建二,陈松乔.网络集群计算系统中的并行任务调度[J].计算机学报, 2004, 27(6): 765 -771.
[35]邹德清,金海.网格自适应遗传算法调度模型[J].小型微型计算机系统, 2004, 25(11): 889-893.
[36] Sinnen O, Sousa L A, Member S, et al. Toward a Realistic Task Scheduling Model[J]. IEEE Transactions On Parallel And Distributed Systems, 2006, 17(3): 263-275.
[37]周远晖,陆玉昌,石纯一.基于克服过早收敛的自适应并行遗传算法[J].清华大学学报, 1998, 38(3): 93-95.
[38]刘东华,徐志伟,李伟.基于有向无环图的两层网格监测系统[J].计算机研究与发展, 2002, 39 (8) : 937-942.
[39]李波,石冰心.网格资源管理和调度仿真工具研究进展[J].微型机与应用, 2005(3): 4-7.
[40] Karonls NT, Tonnen B, Foster I. MPICH-G2: A Grid Enabled Implementation of the Message Passing Interface[J]. In Journal of Parallel(JPDC), 2003, 163(5): 551-563.
[41]查礼,徐志伟,林国璋等.基于GridSim的网格任务调度模拟[J].计算机工程与应用, 2003. 14: 90-92.
[42]刘祥瑞,朱建勇,樊孝忠.基于GridSim的网格调度模拟[J].计算机工程, 2006, 1(2): 42-45.
[2]房向明,杨寿保,郭磊涛,张蕾.网格计算系统的安全体系结构模型研究[M].北京:清华大学出版社, 2003: 36-43.
[3] Foster I, Kesselman M. The Grid: Blueprint for a Future Computing Infrastructure[M]. USA: Morgan Kaufmann Publishers, 1999: 326-332.
[4] Beman F, Fox G, Tony H. Grid Computing-making the Global Infrastructure a Reality[M]. USA: John Wiley and Sons Ltd, 2003: 65-100.
[5] Andronikos T, Koziris N. Optimal Scheduling for UET-UCT Grids Into Fixed Number of Processors[C]. In: Proceedings of 8th Euromicro Workshop on Parallel and Distributed Processing. IEEE Press, 2000: 237-243.
[6]罗红,慕德俊,邓智群等.网格计算中任务调度研究综述[J].计算机应用研究, 2005, 22(5): 16-19.
[7]许智宏,孙竞,孙济洲.一种基于组件的安全网格环境[J].计算机工程, 2004, (21): 111-112.
[8] Foster I, Geisler J, Nickless W, et al. Software Infrastructure for the I-WAY High Performance Distributed Computing Experiment[C]. Proceedings of the 5th IEEE Symposium on High Performance Distributed Computing, 1997: 562-571.
[9] Foster I, Kesselman C. The Grid: Blueprint for a New Computing Infrastructure[M]. San Francisco: Morgan Kaufmann Publishers, 1998: 279-309.
[10]徐志伟,李伟.织女星网格的体系结构研究[J].计算机研究与发展, 2002, 39 (8): 37-39.
[11] A. S. Tanenbaun著,陆丽娜等译. Distributed Operating Systems[M].北京:电子工业出版社, 1999: 77-82.
[12] Beman F, Fox G, Tony H. Grid Computing-making the Global Infrastructure a Reality[M]. USA: John Wiley and Sons Ltd, 2003: 65-80.
[13] Foster I, Kesselman C. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration[EB/OL]. Http//www.globus.org/research/papers.html, 2002: 77-83.
[14]吴高锋,蒋玉明等.基于QoS改进的Min-Min网格调度算法[J].微计算机信息, 2009, 9(3): 110-112.
[15]马满福,吴健,陈丁剑等.网格经济模型中基于信誉度的资源选择[J].计算机工程, 2006, 32(17): 175-177.
[16]杨博,陈志刚.一种基于双层进化结构的网格任务调度算法[J].计算机工程与应用, 2006, 42(15): 8-10.
[17]李向荣.网格资源管理与调度算法的研究与实现[D].南京航空航天大学硕士学位论文, 2006: 56-63.
[18] Spooner D P, Jarvis S A. Local Grid Scheduling Techniques using Performance Predition[J], IEEE Proceedings-Computers and Digital Techniques, 2003, 150(2): 87-96.
[19]熊平华.基于网格计算平台的智能优化算法应用与研究[D].浙江大学硕士学位论文, 2004: 6-13.
[20]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社, 2002: 89-93.
[21] Zhihong Xu, Xiangdan Hou, Jizhou Sun. Ant algorithm-based task scheduling in grid computing[C]. In: Proceedings of 2003-Canadian Conf on Electrical and Computer Engineering. USA: IEEE Computer Society Press, 2003, 2: 1107-1110.
[22]杨浩.模型与算法[M].北京:北京交通大学出版社, 2002: 57-63.
[23]陈国良等著.遗传算法及其应用[M].北京:人民邮电出版社, 1996: 124-129.
[24]李敏强,寇纪松,林丹等.遗传算法的基本原理与应用[M].北京:科学出版社, 2002: 77-81.
[25] Ervin Laszlo,阂家撒等.进化一广义综合理论[M].北京:社会科学文献出版社, 1988: 42-45.
[26]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社, 2000: 33-47.
[27] Xiong ZH, Li SK, Chen JH. Hardware/Soflware partitioning based on dynamic combination of genetic algorithm and ant algorithm. Journal of Software, 2005, 16(4): 503-512.
[28]郝翔.遗传算法及其在规则优化中的应用研究[D].西安交通大学博士论文, 1997: 63-66.
[29]黄宝边,曾文华.网格计算中基于信任机制的动态任务调度[J].计算机应用, 2006, 26(1): 65-69.
[30]梁鸿,田世峰.基于改进蚂蚁算法的网格任务调度策略研究[J].计算机技术, 2006(11): 42-44.
[31] Jelodar M S, Fakhraie S N, Montazeri F, et al. A Representation for Genetic Alogorithm Based Multiprocessor Task Scheduling[C]. 2006 IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada, July, 2006: 16-21.
[32] Spooner D P, Jarvis S A. Local Grid Scheduling Techniques using Performance Predition[J], IEEE Proceedings-Computers and Digital Techniques, 2003, 150(2): 87-96.
[33]袁禄来,曾国荪,姜黎立等.网格环境下基于信任模型的动态级调度[J].计算机学报, 2006, 29(7): 1217-1224.
[34]黄金贵,陈建二,陈松乔.网络集群计算系统中的并行任务调度[J].计算机学报, 2004, 27(6): 765 -771.
[35]邹德清,金海.网格自适应遗传算法调度模型[J].小型微型计算机系统, 2004, 25(11): 889-893.
[36] Sinnen O, Sousa L A, Member S, et al. Toward a Realistic Task Scheduling Model[J]. IEEE Transactions On Parallel And Distributed Systems, 2006, 17(3): 263-275.
[37]周远晖,陆玉昌,石纯一.基于克服过早收敛的自适应并行遗传算法[J].清华大学学报, 1998, 38(3): 93-95.
[38]刘东华,徐志伟,李伟.基于有向无环图的两层网格监测系统[J].计算机研究与发展, 2002, 39 (8) : 937-942.
[39]李波,石冰心.网格资源管理和调度仿真工具研究进展[J].微型机与应用, 2005(3): 4-7.
[40] Karonls NT, Tonnen B, Foster I. MPICH-G2: A Grid Enabled Implementation of the Message Passing Interface[J]. In Journal of Parallel(JPDC), 2003, 163(5): 551-563.
[41]查礼,徐志伟,林国璋等.基于GridSim的网格任务调度模拟[J].计算机工程与应用, 2003. 14: 90-92.
[42]刘祥瑞,朱建勇,樊孝忠.基于GridSim的网格调度模拟[J].计算机工程, 2006, 1(2): 42-45.