网格计算中任务调度算法研究
|
摘要
网格计算是借鉴电力网的概念提出来的。利用网络把分散在不同地理位置的计算机组织成一个“虚拟的超级计算机”,其中每一台参与计算的计算机就是一个“节点”,而整个计算环境是由“节点”组成的一张“网格”。最终目的是希望给用户提供可靠的、协调的、无处不在的和低廉的高端计算能力。网格计算为解决科学和工程领域一些大规模计算问题提供了理想的平台。
资源调度是网格计算中一个关键性的研究课题。在网格环境中,任务从提交给网格系统到任务处理完成,都一直处于网格任务管理系统的管理之下。良好的资源调度能有效地协调和分配网格资源,有效降低网格计算的总执行时间和总耗费量,从而使网格达到最大性能。由于网格具有大规模、异构、动态、分布和自治等特性,如何调度任务以满足用户的需求是一个极具挑战性的问题。
本文基于遗传算法原理提出了适合网格计算环境的网格资源调度策略,并将其作为网格资源调度技术的核心策略来更合理的调度网格资源,本论文主要工作为:
①对当前常用的资源发现和管理模型进行了研究,针对层次模型中的“层层传递”导致的效率低下问题,提出一种基于资源类型的资源发现和管理模型,该模型大大提高了资源查找和更新的速度。
②网格计算系统融合了多种计算资源,一方面这些计算资源可能存在很大的性能差异,另一方面由于它们的工作负载也是动态变化的,因此计算资源能够向用户提供的计算能力也会动态地变化。因此本论文提出了自适应遗传算法、线性变换遗传算法、量子遗传算法三种不同的任务调度算法,根据网格系统各个计算模块的计算能力、负载及网络状态进行自适应调度,从而向用户提供最优的性能。
③对当前国内外比较优秀的静态和动态调度算法进行分析,着重讨论了比较经典的Min-min算法以及QoS guided Min-min算法,在此基础上考虑到任务对服务质量要求的差异对调度算法的影响,提出一个较为合理的改进算法来有效地均衡负载、提高系统吞吐量。
④采用Gridsim工具包对以上提出的算法进行了实验仿真,仿真结果表明改进后的调度算法更加高效。
Grid computing is based on power grid. It organizes distributed computers as a“virtual super computer”by network. Every computer is called a node, and all the nodes form a“Grid”. The target of grid is to make the users feel the use of grid is as convenient as using power grid. Grid computing provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. It provides an ideal platform to solve large-scale computing problems in scientific and engineering area.
Resources scheduling is a key issue in computational grid. In grid environments, from job submission to result processing, all events about jobs are under the control of job management. One good resources scheduling can effectively improve adjusting and assigning grid tasks, and decrease grid computing total time, Grid computing can perform perfectly. Resources scheduling is great important in grid computing. Because grid environments are large-scale, heterogeneous, dynamic, distributed and autonomous, grid job management is complex and challenging.
Based on the principle of genetic algorithms, this paper presented the grid resources scheduling strategy adapted for grid computing environment, which was as as the core strategy of grid resource scheduling technical, to make the resource scheduling more reasonable. There were the main works of this paper:
1. This paper researched into the current common resource discovery and management model and put forward a resource classification based grid resources hierarchical model, which will improve the speed of resource finding and updating greatly.
2. The grid computing systems are consisted of various kinds of different resources, because these resources not only differ greatly in raw performance and also their load balancing is dynamic, their available computing performances to the users vary greatly, too. So this paper proposes three adaptive scheduling algorithms, such as self-adjusted genetic algorithm, linear transformation genetic algorithm, quantum genetic algorithm.
3. This paper analyzed the excellent static and dynamic scheduling algorithms in the world, especially the classical Min-min algorithm and QoS guided Min-min algorithm. Considering the influence of different requirements of task on scheduling algorithm, the author put forward a proper algorithm to balance the charge and increase the throughput efficiently.
Finally, the author used GridSim tools to make simulating experiment to test the algorithms presented before. The result of the simulation showed that the improved scheduling algorithm is more efficient.
资源调度是网格计算中一个关键性的研究课题。在网格环境中,任务从提交给网格系统到任务处理完成,都一直处于网格任务管理系统的管理之下。良好的资源调度能有效地协调和分配网格资源,有效降低网格计算的总执行时间和总耗费量,从而使网格达到最大性能。由于网格具有大规模、异构、动态、分布和自治等特性,如何调度任务以满足用户的需求是一个极具挑战性的问题。
本文基于遗传算法原理提出了适合网格计算环境的网格资源调度策略,并将其作为网格资源调度技术的核心策略来更合理的调度网格资源,本论文主要工作为:
①对当前常用的资源发现和管理模型进行了研究,针对层次模型中的“层层传递”导致的效率低下问题,提出一种基于资源类型的资源发现和管理模型,该模型大大提高了资源查找和更新的速度。
②网格计算系统融合了多种计算资源,一方面这些计算资源可能存在很大的性能差异,另一方面由于它们的工作负载也是动态变化的,因此计算资源能够向用户提供的计算能力也会动态地变化。因此本论文提出了自适应遗传算法、线性变换遗传算法、量子遗传算法三种不同的任务调度算法,根据网格系统各个计算模块的计算能力、负载及网络状态进行自适应调度,从而向用户提供最优的性能。
③对当前国内外比较优秀的静态和动态调度算法进行分析,着重讨论了比较经典的Min-min算法以及QoS guided Min-min算法,在此基础上考虑到任务对服务质量要求的差异对调度算法的影响,提出一个较为合理的改进算法来有效地均衡负载、提高系统吞吐量。
④采用Gridsim工具包对以上提出的算法进行了实验仿真,仿真结果表明改进后的调度算法更加高效。
Grid computing is based on power grid. It organizes distributed computers as a“virtual super computer”by network. Every computer is called a node, and all the nodes form a“Grid”. The target of grid is to make the users feel the use of grid is as convenient as using power grid. Grid computing provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. It provides an ideal platform to solve large-scale computing problems in scientific and engineering area.
Resources scheduling is a key issue in computational grid. In grid environments, from job submission to result processing, all events about jobs are under the control of job management. One good resources scheduling can effectively improve adjusting and assigning grid tasks, and decrease grid computing total time, Grid computing can perform perfectly. Resources scheduling is great important in grid computing. Because grid environments are large-scale, heterogeneous, dynamic, distributed and autonomous, grid job management is complex and challenging.
Based on the principle of genetic algorithms, this paper presented the grid resources scheduling strategy adapted for grid computing environment, which was as as the core strategy of grid resource scheduling technical, to make the resource scheduling more reasonable. There were the main works of this paper:
1. This paper researched into the current common resource discovery and management model and put forward a resource classification based grid resources hierarchical model, which will improve the speed of resource finding and updating greatly.
2. The grid computing systems are consisted of various kinds of different resources, because these resources not only differ greatly in raw performance and also their load balancing is dynamic, their available computing performances to the users vary greatly, too. So this paper proposes three adaptive scheduling algorithms, such as self-adjusted genetic algorithm, linear transformation genetic algorithm, quantum genetic algorithm.
3. This paper analyzed the excellent static and dynamic scheduling algorithms in the world, especially the classical Min-min algorithm and QoS guided Min-min algorithm. Considering the influence of different requirements of task on scheduling algorithm, the author put forward a proper algorithm to balance the charge and increase the throughput efficiently.
Finally, the author used GridSim tools to make simulating experiment to test the algorithms presented before. The result of the simulation showed that the improved scheduling algorithm is more efficient.
引文
[1]桂小林.网格技术导论[M].北京:北京邮电大学出版社,2005.
[2] ARMSTRONG R, HENSGEN D, KIDD T. The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions[C]. In: 7th IEEE Heterogeneous Computing Workshop (HCW'98), Mar, 1998:79-87.
[3] FREUND R, GHERRITY M, AMBROSIUS S. Scheduling Resources in Multi-user Heterogeneous Computing Environments with SmartNet[C].In: 7th IEEE Heterogeneous Computing Workshop (HCW'98), Mar, 1998:184-199.
[4] IBARRA O, KIM C. Heuristic Algorithms for Scheduling Independent Tasks on Non-identical Processors [J].Journal of the ACM, Apr.1977, 77 (2):280-289.
[5]丁警,陈国良,顾钧.计算网格环境下一个统一的资源映射策略[J].软件学报,2002,13(7): 1303-1308.
[6] FOSTER I, KESSELMAN C. The Grid, Blueprint for a New Computing Infrastructure [M]. San Francisco: Morgan Kaufmann Publishers, 1998.
[7] BASNEY J, LIVNY M. Deploying a High Throughput Computing Cluster [J].High Performance Cluster Computing, R. BUYYA (editor).Vol. 1, Chapter 5, Prentice Hall PTR, May, 1999.
[8] LITZKOW M, LIVNY M. Condor-A Hunter of Idle Workstations[C]. Proceedings of the 8th International Conference of Distributed Computing Systems (ICDCS 1988), San Jose, CA, IEEE CS Press USA, Jan, 1988.
[9]沈华,魏斐翡.网格资源计费模型的研究[J].湖北工业大学学报,2006,21(4):45.
[10] BERMAN M, WOLSKI R. The AppGes Project: A Status Report[C], Proceedings of the 8th NEC Research Symposium, Berlin, Germany, May, 1997.
[11] ACI GRID. http://www-sop.inria.fr/aci/grid[EB/OL], 2003-4.
[12] FOSTER I, KESSELMAN C, TUECKE S. The Anatomy of the Grid: Enabling Scalable Virtual Organization [J]. High-Performance Computing Applications, 2001, 15(3):200-222.
[13]桂小林.网格技术导论[M].北京:北京邮电大学出版社,2005.
[14]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002.
[15] BRAUN T, SIEGEL H, Beck N. A Comparison Study of Static Mapping Heuristics for a Class of Meta-tasks on Heterogeneous Computing Systems[C]. In: 8th IEEE Heterogeneous Computing Workshop (HCW'99), Apr, 1999: 1529.
[16] TRACY D. BRAUN, HOWARD JAY SIEGEL, NOAH BECH. A Comparison of ElevenStatic Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems[J]. Journal of Parallel and Distributed Computing, 2001.
[17] ARMSTRONG R, HENSGEN D, and KIDD T. The Relative Performance of Various Mapping Algorithm is Independent of Sizable Variance in Run-time Predictions [J]. In: 7th IEEE Heterogeneous Computing Workshop (HCW'98), 1998:79-87.
[18] FREUND R.F, GHERRITY M, AMBROSIUS S, CAMPBELL M, HALDERMAN M, HENSGEN D, Keith E, KIDD T, KUSSOW M, Lima J.D, MIRABILE F, MOORE L, RUST B, and SIEGEL H.J. Scheduling Resources in Multi-user Heterogeneous Computing Environments with SmartNet[C]. In: 7th IEEE -Heterogeneous Computing Workshop (HCW'98), 1998:184-199.
[19] XU ZHIHONG, HOU XIANGDAN, SUN JIZHOU. Ant Algorithm Based Task Scheduling in Grid Computing [C]. IEEE CCECE, 2003.
[20]陈国良.遗传算法及其应用[M].北京:人民邮电出版社,1996.
[21] YAO WENSHENG. Genetic Scheduling on Minimal Processing Elements in the Grid [M]. Springer-Verlag Heidelberg, 2002.
[22] DI MARTINO V. Scheduling in a Grid Computing Environment using Genetic Algorithms[C].Parallel and Distributed Processing Symposium, Proceedings International IPDPS, 2002.235239.
[23] DI MARTINO V. Sub Optimal Scheduling in A Grid Using Genetic Algorithms[C].Parallel and Distributed Processing Symposium, Proceedings International IPDPS, 2003.148154.
[24] SINGH H, YOUSSEF A. Mapping and Scheduling Heterogeneous Task Graphs using Genetic Algorithms[C]. In: 5th IEEE Heterogeneous Computing Workshop (HCW'96), 1996:8697.
[25] MAHESWARAN M., Ali S, Siegel H. Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems[C]. In: Proceedings of the 8th IEEE Heterogeneous Computing Workshop(HCW'99).IEEE Computer Society Press, 1999:30-44.
[26] BRAUN T, SIEGEL H, BECK N, BOLONI L, MAHESWARAN M., REUTHER A, ROBERTSON J, THEYS M, YAO B, HENSGEN D, and FREUND R. A Comparison Study of Static Mapping Heuristics for a Class of Meta-Tasks on Heterogeneous Computing Systems[J]. In: 8th IEEE Heterogeneous Computing Workshop (HCW '99), Apr.1999:15-29.
[27] CHEN H, FLANN N.S and Watson D.W. Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Approach[C]. IEEE Trans Parallel Distributed Computing, Feb 1998: 126-136.
[28]蔡自兴,徐光褚.人工智能及其应用[M].北京:清华大学出版社,2004.
[29]吴颖,袁道华,陈光柱.一种基于Globus的网格计算模型实现框架[J].四川大学学报自然科学版,2005,42(4): 720-721.
[30]张葛祥,李娜等.一种新量子遗传算法及其应用[J].电子学报,2004, 32(3).
[31]郭海燕.基于混沌优化的量子遗传算法[J].西南科技大学学报,2005,20(3).
[32]李晓磊.一种新型的智能优化方法-人工鱼群算法.[D].杭州:浙江大学,2003.
[33]杜建成.基于最佳并行度的任务依赖图调度[J].软件学报,1999,10(10):1038-1045.
[34]吴惠中等.基于遗传算法的网格资源调度算法[J].计算机研究与发展.2004, 41(12): 2195-2199.
[35]王广芳,钟志伟,赵先武.分布式计算机系统(DCS)负载平衡算法[J].计算机工程与设计,1995,16(5):57-63.
[36]稽鹏.网格计算任务调度算法的研究与实现[D].南京:东南大学,2004.
[37] ZHENG SHIJUE, SHU WANNENG, DAI SHANGPING. Task Scheduling Model Design Using Hybrid Genetic Algorithm[C], In: Proceedings of IEEE 2006 International Conference on Innovative Computing, Information and Control (IEEE ICICIC 2006), 30 Aug. - 1 Sept. 2006, Beijing, China.
[38]穆艳玲,李学武,赵杰修.遗传算法截止代数的判定[J].天津师范大学学报,2005,25(1).
[39]王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报[J],2002,14(1):31-33.
[40]郑世环,舒万能,马卫,杜建华.基于遗传算法的VOD集群负载均衡研究[J].计算机应用研究,2007,1(1).
[41]夏靖波,刘颖,汪胜荣.网格原理与开发[M].西安:西安电子科技大学出版社,2006.
[42] SHU WANNENG, ZHENG SHIJUE. A Parallel Genetic Simulated Annealing Hybrid Algorithm for Task Scheduling[J]. Wuhan University Journal of Natural Sciences, 2006,12 (5).
[2] ARMSTRONG R, HENSGEN D, KIDD T. The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions[C]. In: 7th IEEE Heterogeneous Computing Workshop (HCW'98), Mar, 1998:79-87.
[3] FREUND R, GHERRITY M, AMBROSIUS S. Scheduling Resources in Multi-user Heterogeneous Computing Environments with SmartNet[C].In: 7th IEEE Heterogeneous Computing Workshop (HCW'98), Mar, 1998:184-199.
[4] IBARRA O, KIM C. Heuristic Algorithms for Scheduling Independent Tasks on Non-identical Processors [J].Journal of the ACM, Apr.1977, 77 (2):280-289.
[5]丁警,陈国良,顾钧.计算网格环境下一个统一的资源映射策略[J].软件学报,2002,13(7): 1303-1308.
[6] FOSTER I, KESSELMAN C. The Grid, Blueprint for a New Computing Infrastructure [M]. San Francisco: Morgan Kaufmann Publishers, 1998.
[7] BASNEY J, LIVNY M. Deploying a High Throughput Computing Cluster [J].High Performance Cluster Computing, R. BUYYA (editor).Vol. 1, Chapter 5, Prentice Hall PTR, May, 1999.
[8] LITZKOW M, LIVNY M. Condor-A Hunter of Idle Workstations[C]. Proceedings of the 8th International Conference of Distributed Computing Systems (ICDCS 1988), San Jose, CA, IEEE CS Press USA, Jan, 1988.
[9]沈华,魏斐翡.网格资源计费模型的研究[J].湖北工业大学学报,2006,21(4):45.
[10] BERMAN M, WOLSKI R. The AppGes Project: A Status Report[C], Proceedings of the 8th NEC Research Symposium, Berlin, Germany, May, 1997.
[11] ACI GRID. http://www-sop.inria.fr/aci/grid[EB/OL], 2003-4.
[12] FOSTER I, KESSELMAN C, TUECKE S. The Anatomy of the Grid: Enabling Scalable Virtual Organization [J]. High-Performance Computing Applications, 2001, 15(3):200-222.
[13]桂小林.网格技术导论[M].北京:北京邮电大学出版社,2005.
[14]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002.
[15] BRAUN T, SIEGEL H, Beck N. A Comparison Study of Static Mapping Heuristics for a Class of Meta-tasks on Heterogeneous Computing Systems[C]. In: 8th IEEE Heterogeneous Computing Workshop (HCW'99), Apr, 1999: 1529.
[16] TRACY D. BRAUN, HOWARD JAY SIEGEL, NOAH BECH. A Comparison of ElevenStatic Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems[J]. Journal of Parallel and Distributed Computing, 2001.
[17] ARMSTRONG R, HENSGEN D, and KIDD T. The Relative Performance of Various Mapping Algorithm is Independent of Sizable Variance in Run-time Predictions [J]. In: 7th IEEE Heterogeneous Computing Workshop (HCW'98), 1998:79-87.
[18] FREUND R.F, GHERRITY M, AMBROSIUS S, CAMPBELL M, HALDERMAN M, HENSGEN D, Keith E, KIDD T, KUSSOW M, Lima J.D, MIRABILE F, MOORE L, RUST B, and SIEGEL H.J. Scheduling Resources in Multi-user Heterogeneous Computing Environments with SmartNet[C]. In: 7th IEEE -Heterogeneous Computing Workshop (HCW'98), 1998:184-199.
[19] XU ZHIHONG, HOU XIANGDAN, SUN JIZHOU. Ant Algorithm Based Task Scheduling in Grid Computing [C]. IEEE CCECE, 2003.
[20]陈国良.遗传算法及其应用[M].北京:人民邮电出版社,1996.
[21] YAO WENSHENG. Genetic Scheduling on Minimal Processing Elements in the Grid [M]. Springer-Verlag Heidelberg, 2002.
[22] DI MARTINO V. Scheduling in a Grid Computing Environment using Genetic Algorithms[C].Parallel and Distributed Processing Symposium, Proceedings International IPDPS, 2002.235239.
[23] DI MARTINO V. Sub Optimal Scheduling in A Grid Using Genetic Algorithms[C].Parallel and Distributed Processing Symposium, Proceedings International IPDPS, 2003.148154.
[24] SINGH H, YOUSSEF A. Mapping and Scheduling Heterogeneous Task Graphs using Genetic Algorithms[C]. In: 5th IEEE Heterogeneous Computing Workshop (HCW'96), 1996:8697.
[25] MAHESWARAN M., Ali S, Siegel H. Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems[C]. In: Proceedings of the 8th IEEE Heterogeneous Computing Workshop(HCW'99).IEEE Computer Society Press, 1999:30-44.
[26] BRAUN T, SIEGEL H, BECK N, BOLONI L, MAHESWARAN M., REUTHER A, ROBERTSON J, THEYS M, YAO B, HENSGEN D, and FREUND R. A Comparison Study of Static Mapping Heuristics for a Class of Meta-Tasks on Heterogeneous Computing Systems[J]. In: 8th IEEE Heterogeneous Computing Workshop (HCW '99), Apr.1999:15-29.
[27] CHEN H, FLANN N.S and Watson D.W. Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Approach[C]. IEEE Trans Parallel Distributed Computing, Feb 1998: 126-136.
[28]蔡自兴,徐光褚.人工智能及其应用[M].北京:清华大学出版社,2004.
[29]吴颖,袁道华,陈光柱.一种基于Globus的网格计算模型实现框架[J].四川大学学报自然科学版,2005,42(4): 720-721.
[30]张葛祥,李娜等.一种新量子遗传算法及其应用[J].电子学报,2004, 32(3).
[31]郭海燕.基于混沌优化的量子遗传算法[J].西南科技大学学报,2005,20(3).
[32]李晓磊.一种新型的智能优化方法-人工鱼群算法.[D].杭州:浙江大学,2003.
[33]杜建成.基于最佳并行度的任务依赖图调度[J].软件学报,1999,10(10):1038-1045.
[34]吴惠中等.基于遗传算法的网格资源调度算法[J].计算机研究与发展.2004, 41(12): 2195-2199.
[35]王广芳,钟志伟,赵先武.分布式计算机系统(DCS)负载平衡算法[J].计算机工程与设计,1995,16(5):57-63.
[36]稽鹏.网格计算任务调度算法的研究与实现[D].南京:东南大学,2004.
[37] ZHENG SHIJUE, SHU WANNENG, DAI SHANGPING. Task Scheduling Model Design Using Hybrid Genetic Algorithm[C], In: Proceedings of IEEE 2006 International Conference on Innovative Computing, Information and Control (IEEE ICICIC 2006), 30 Aug. - 1 Sept. 2006, Beijing, China.
[38]穆艳玲,李学武,赵杰修.遗传算法截止代数的判定[J].天津师范大学学报,2005,25(1).
[39]王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报[J],2002,14(1):31-33.
[40]郑世环,舒万能,马卫,杜建华.基于遗传算法的VOD集群负载均衡研究[J].计算机应用研究,2007,1(1).
[41]夏靖波,刘颖,汪胜荣.网格原理与开发[M].西安:西安电子科技大学出版社,2006.
[42] SHU WANNENG, ZHENG SHIJUE. A Parallel Genetic Simulated Annealing Hybrid Algorithm for Task Scheduling[J]. Wuhan University Journal of Natural Sciences, 2006,12 (5).