网格环境下效用启发式任务调度算法研究
摘要
作为网格计算的一个重要组成部分,任务调度算法的好坏直接影响到网格计算的性能优劣。随着网格应用逐步走向商业化,网格任务调度系统面临着全新的、更高的要求。面向商业应用的网格任务调度系统要求既能最大程度地满足用户需求,获得较高的用户满意度,又能保证网格系统的高吞吐率和稳定性。基于服务质量(QoS)的任务调度算法成为该领域的一个重要研究方向。
本文首先研究了网格技术、网格任务调度相关概念以及网格QoS层次结构模型,在此基础上提出了用户效用的概念。然后针对经典动态任务调度算法的不足,并借鉴MCT和Sufferage算法的调度思想,提出了用户效用启发式网格元任务调度算法:MUU在线调度算法和User USufferage批调度算法。这两种算法只考虑满足用户需求,会严重影响网格系统吞吐率和负载均衡性能。为了改善它们的不足,本文引入负载QoS和全局效用的概念,对MUU算法和User USufferage算法加以改进,从而引出了以全局效用为启发式的网格元任务调度算法:MGU在线调度算法和Global USufferage批调度算法。
本文研究了主流的网格调度算法仿真工具GridSim和SimGrid,针对两工具的不足,设计并实现了轻量级的网格调度模拟器GridSche。使用该模拟器对本文提出的几种算法的性能在各种情况下进行了全面的仿真比较。实验表明,通过调整负载权重参数,MGU算法和Global USufferage算法既能在一定程度上尽量满足用户需求,又保证网格系统在较高的吞吐率状态下稳定工作。
As an important part of the grid computing, task scheduling arithmetic has a direct impact on its performance. And with the commercialization of grid computing, task scheduling system is faced with new and higher demands. A commercialized grid task scheduling system requires to maximize to meet the user demands, to win higher user satisfaction, and meanwhile ensure the system throughput and stability. For this reason, the QoS-oriented task scheduling algorithm becomes an important research direction of this field.
In this text, grid technology, grid task scheduling concept and grid QoS layering model are presented firstly, based on which, the concept of User Utility are put forward. Then, the User Utility heuristic scheduling arithmetics for grid meta-task, MUU online scheduling arithmetic User USufferage batch scheduling arithmetic, are invented, considering the defects of classic dynamic scheduling arithmetics, and borrowing ideas from MCT and Sufferage scheduling arithmetics. The two arithmetics consider only to satisfy user requirements, and would lead to worsen of system throughput and stability. Considering the defects of them, we bring forward concept of load QoS and Global Utility. After that,based on MUU and User Utility arithmetics, the Global Utility heuristic scheduling arithmetics for grid meta-task, MGU online scheduling arithmetic and Global USufferage batch scheduling arithmetic, are invented.
This text researches the popular grid scheduling arithmetic simulation tools, GridSim and SimGrid. And a new lightweight grid scheduling simulation tool is programmed, focused on the defects of the two simulation tools mentioned above. After that, we use this new tool to make comprehensive contrast experiments for the scheduling arithmetics mentioned in this article. The result of these experiments indicate that, MGU and Global USufferage scheduling arithmetics can meet the needs of users to some extent, and meanwhile ensure the system throughput and stability of grid system, by adjusting the load weight parameter.
本文首先研究了网格技术、网格任务调度相关概念以及网格QoS层次结构模型,在此基础上提出了用户效用的概念。然后针对经典动态任务调度算法的不足,并借鉴MCT和Sufferage算法的调度思想,提出了用户效用启发式网格元任务调度算法:MUU在线调度算法和User USufferage批调度算法。这两种算法只考虑满足用户需求,会严重影响网格系统吞吐率和负载均衡性能。为了改善它们的不足,本文引入负载QoS和全局效用的概念,对MUU算法和User USufferage算法加以改进,从而引出了以全局效用为启发式的网格元任务调度算法:MGU在线调度算法和Global USufferage批调度算法。
本文研究了主流的网格调度算法仿真工具GridSim和SimGrid,针对两工具的不足,设计并实现了轻量级的网格调度模拟器GridSche。使用该模拟器对本文提出的几种算法的性能在各种情况下进行了全面的仿真比较。实验表明,通过调整负载权重参数,MGU算法和Global USufferage算法既能在一定程度上尽量满足用户需求,又保证网格系统在较高的吞吐率状态下稳定工作。
As an important part of the grid computing, task scheduling arithmetic has a direct impact on its performance. And with the commercialization of grid computing, task scheduling system is faced with new and higher demands. A commercialized grid task scheduling system requires to maximize to meet the user demands, to win higher user satisfaction, and meanwhile ensure the system throughput and stability. For this reason, the QoS-oriented task scheduling algorithm becomes an important research direction of this field.
In this text, grid technology, grid task scheduling concept and grid QoS layering model are presented firstly, based on which, the concept of User Utility are put forward. Then, the User Utility heuristic scheduling arithmetics for grid meta-task, MUU online scheduling arithmetic User USufferage batch scheduling arithmetic, are invented, considering the defects of classic dynamic scheduling arithmetics, and borrowing ideas from MCT and Sufferage scheduling arithmetics. The two arithmetics consider only to satisfy user requirements, and would lead to worsen of system throughput and stability. Considering the defects of them, we bring forward concept of load QoS and Global Utility. After that,based on MUU and User Utility arithmetics, the Global Utility heuristic scheduling arithmetics for grid meta-task, MGU online scheduling arithmetic and Global USufferage batch scheduling arithmetic, are invented.
This text researches the popular grid scheduling arithmetic simulation tools, GridSim and SimGrid. And a new lightweight grid scheduling simulation tool is programmed, focused on the defects of the two simulation tools mentioned above. After that, we use this new tool to make comprehensive contrast experiments for the scheduling arithmetics mentioned in this article. The result of these experiments indicate that, MGU and Global USufferage scheduling arithmetics can meet the needs of users to some extent, and meanwhile ensure the system throughput and stability of grid system, by adjusting the load weight parameter.
引文
[1] Ajith Abraham, Rajkumar Buyya, Baikunth Nath. Nature’s Heuristics for Scheduling Jobs on Computational Grids.In: Proc. of the 8th Int’l Conf. on Advaneed Computing and Communieation (ADCOM2000). New Delhi: Tata MeGraw-Hill Publishing, 2000: 45~52.
[2]王霓虹,滕志霞.网格技术研究与发展趋势综述.信息技术,2007, 2:117~120.
[3]王莉,窦星,刘宗田,黄美丽.一种快速网格任务调度策略.计算机科学,2007, 34(6): 128~130.
[4]林伟伟,齐德星,李拥军,王振宇,张志立.树型网格计算环境下的独立任务调度.软件学报,2006, 17(11): 2352~2361.
[5]罗红,慕德俊,邓智群,王晓东.网格计算中任务调度研究综述.计算机应用研究,2005, 22(5): 16~19.
[6] X He, X Sun and G V Laszewski. QoS Guided min-min heuristic for grid task scheduling. Journal of Computer Science and Technology. 2003, 18(2): 442~451.
[7] C Weng and X Lu. Heuristic scheduling for bag-of-tasks applications in combination with QoS in the computational grid. Future Generation Computer Systems. 2005, 21(2): 271~280.
[8] T D Braun, H J Siegel, A Maciejewski. Static Mapping Heuristics for tasks with dependencies, priorities, deadlines, and multiple versions in Heterogeneous Environments. The 16th International Parallel and Distributed Processing Symposium, Fort Lauderdale, FL, 2002: 305~312.
[9] I Foster. What is the Grid A Three Point Checklist. 2002, 10(3): 24~27.
[10] IAN FOSTER. Internet Computing and the Emerging Grid. Nature Web Matters, 7 December 2000. http://www.naturen.com/nature/webmatters/grid/grid.htm .
[11] http://www.itg.ibl.gov/～johnston/Grids/DOE_Science_Grid_Plmeeting_Jan.2002.1.ppt
[12] http://doesciencegrid.org/grid/papers/DOE_Science_Grid_Plmeeting_Jan.2002.1.ppt
[13]都志辉,陈渝,刘鹏.网格计算.北京,清华大学出版社,2002: 12~55
[14] ACIGRID. http://www-sop.inria.fr/aci/grid/ .
[15] Foster I. Kesselman C. Tuecke S. The Anatomy of the Grid: Enabling Scalable Vitual Organization. High-Performance Computing Applications, 2001, 15(3): 200~222.
[16]桂小林.网格技术导论.北京,北京邮电大学出版社,2005, 3.
[17]夏靖波,刘颖,汪胜荣.网格原理与开发.西安,西安电子科技大学出版社,2006,4: 33~37.
[18]胡爱娟,吴兵. GLOBUS OGSA网格体系结构探讨.船舶电子工程,2004, 6: 77~79.
[19]吴颖,袁道华,陈光柱.一种基于Globus的网格计算模型实现框架.四川大学学报(自然科学版),2005, 8, 42(4): 720~721.
[20]郎博.基于OGSA的网格服务研究.计算机技术与发展,2006, 4. 16(4): 162~163.
[21]夏靖波,刘颖,汪胜荣.网格原理与开发.西安,西安电子科技大学出版社,2006, 4: 61.
[22]陈萍,余华山,王彬.网格计算环境Globus介绍.计算机应用研究,2003: 96~98.
[23] STREIT A. Self-Tuning Job Scheduling Strategies for the Resource Management of HPC Systems and Computational Grids. 2003, 10.
[24] Allcock W, Bester J, Bresnahan J, et al. GridFTP Protocol Specification. GGF GridFTP Working Group Document, 2002.
[25] Sun X H, Wu M. GHS: A Performance Prediction and Task Scheduling System for Grid Computing. IEEE International Parallel and Distributed Processing Symposium (IPDPS2003). 2003:123~135.
[26] Ranganathan K, Foster I. Decoupling computation and data scheduling in distributed data-intensive applications. Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing. Washington: IEEE Computer society, 2002: 352~258.
[27] Subramani V, Kettimuthu R, Srinivasan S, et al. Distributed job Scheduling on computational grids using multiple simultaneous requests. Proceedings of llth IEEE International Symposium on High Performance Distributed Computing. Washington: IEEE Computer society, 2002: 359~366.
[28] He Ligang, Jarvis S A, Spooner D P, et al. Optimising static workload allocation in multiclusters. Proceedings of the 18th International Parallel and Distributed Processing Symposium. Washington: IEEE Computer Soeiety, 2004: 39~48.
[29] Di Martino V. Sub optimal scheduling in a grid using genetic algorithms. Proceedings of International Parallel and Distributed Processing Symposium. Washington: IEEE Computer Society, 2003: 148~154.
[30] Arora M, Das S K, Biswas R. A de-centralized seheduling and load balancing algorithm for heterogeneous grid environments. Proceedings of 2002 International Conference on Parallel Processing Workshop. Washington: IEEE Computer Soeiety, 2002: 499~505.
[31] Wang Qingjiang, Gui Xiaolin, Zheng Shouqi. De-Centralized Job Scheduling on Computational Grids Using Distributed Backfilling. Proceedings of the 3rd International Conference on Grid and Cooperative Computing. Berlin: Springer-Verlag, 2004: 285~292.
[32] Armstrong R, Hensgen D, Kidd T. The Relative Performance of Various Mapping Algorithm is Independent of Sizable Variance in Run-time Predictions. Proeeedings of the 7th Heterogeneous computing workshop (HCW’95). IEEE computer Society Press, 1998: 79~87.
[33] Fujimoto, N Hagihara. Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid, Parallel and Distributed Computing, 2003. Proceedings of the second International Symposium on 13-14 Oct. 2003: 80~87.
[34]李小平,徐晓飞,战德臣.一种独立任务的同型机调度快速算法团.软件学报. 2002, 13, No.4.1.
[35] M Maheswaran, S Ali, H Siegel. Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, Eighth Heterogeneous Computing Workshop, 1999,4.
[36]张颖峰,李毓麟.基于进化算法的网格计算资源管理调度系统.计算机工程,2003, 29(15): 110~175.
[37] Reeves, C R. Modern heuristic techniques for combinatorial problems. John Wiley&Sons, Mc Graw-Hill International (UK) Limited,1995.
[38] Kavitha S. Golconda, Fusun Ozguner, Atakan Dogan. A Comparison of Static QoS-Based Scheduling Heuristics for a Meta-Task with Multiple QoS Dimensions in Heterogeneous Computing, Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International. 2004, 1: 106.
[39]丁箐,陈国良,顾钧.计算网格环境下一个统一的资源映射策略.软件学报. 2002, 13(7): 1303~1308.
[40] Braun T D, Siegel H J, et al. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems. Proceedings of the 8th IEEE Heterogeneous Computing Workshop ( HCW' 99 ). IEEE Computer Society Press, 1999: 15~29.
[41] I Foster. The grid: A new infrastructure 21st century science. Physics Today, 2002, 55(2): 42~47.
[42] Reynar J C. An automatic method of finding topic boundaries. Proceedings of the 15th International Conference on Computational Linguistics. 1996.
[43]伍之昂,罗军舟,宋爱波.基于QoS的网格资源管理.软件学报,2006, 17(11): 2264~2276.
[44]罗军舟,王小志,宋爱波,朱烨,伍之昂.网格QoS层次结构模型的研究.华中科技大学学报(自然科学版). 2005, 33(9): 51~53.
[45] Rajkumar Buyya, Manzur Murshed. GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing. The journal of Concurrency and Computation: Practice and Experience(CCPE). Wiley Press. 2002, 14: 13~15.
[2]王霓虹,滕志霞.网格技术研究与发展趋势综述.信息技术,2007, 2:117~120.
[3]王莉,窦星,刘宗田,黄美丽.一种快速网格任务调度策略.计算机科学,2007, 34(6): 128~130.
[4]林伟伟,齐德星,李拥军,王振宇,张志立.树型网格计算环境下的独立任务调度.软件学报,2006, 17(11): 2352~2361.
[5]罗红,慕德俊,邓智群,王晓东.网格计算中任务调度研究综述.计算机应用研究,2005, 22(5): 16~19.
[6] X He, X Sun and G V Laszewski. QoS Guided min-min heuristic for grid task scheduling. Journal of Computer Science and Technology. 2003, 18(2): 442~451.
[7] C Weng and X Lu. Heuristic scheduling for bag-of-tasks applications in combination with QoS in the computational grid. Future Generation Computer Systems. 2005, 21(2): 271~280.
[8] T D Braun, H J Siegel, A Maciejewski. Static Mapping Heuristics for tasks with dependencies, priorities, deadlines, and multiple versions in Heterogeneous Environments. The 16th International Parallel and Distributed Processing Symposium, Fort Lauderdale, FL, 2002: 305~312.
[9] I Foster. What is the Grid A Three Point Checklist. 2002, 10(3): 24~27.
[10] IAN FOSTER. Internet Computing and the Emerging Grid. Nature Web Matters, 7 December 2000. http://www.naturen.com/nature/webmatters/grid/grid.htm .
[11] http://www.itg.ibl.gov/～johnston/Grids/DOE_Science_Grid_Plmeeting_Jan.2002.1.ppt
[12] http://doesciencegrid.org/grid/papers/DOE_Science_Grid_Plmeeting_Jan.2002.1.ppt
[13]都志辉,陈渝,刘鹏.网格计算.北京,清华大学出版社,2002: 12~55
[14] ACIGRID. http://www-sop.inria.fr/aci/grid/ .
[15] Foster I. Kesselman C. Tuecke S. The Anatomy of the Grid: Enabling Scalable Vitual Organization. High-Performance Computing Applications, 2001, 15(3): 200~222.
[16]桂小林.网格技术导论.北京,北京邮电大学出版社,2005, 3.
[17]夏靖波,刘颖,汪胜荣.网格原理与开发.西安,西安电子科技大学出版社,2006,4: 33~37.
[18]胡爱娟,吴兵. GLOBUS OGSA网格体系结构探讨.船舶电子工程,2004, 6: 77~79.
[19]吴颖,袁道华,陈光柱.一种基于Globus的网格计算模型实现框架.四川大学学报(自然科学版),2005, 8, 42(4): 720~721.
[20]郎博.基于OGSA的网格服务研究.计算机技术与发展,2006, 4. 16(4): 162~163.
[21]夏靖波,刘颖,汪胜荣.网格原理与开发.西安,西安电子科技大学出版社,2006, 4: 61.
[22]陈萍,余华山,王彬.网格计算环境Globus介绍.计算机应用研究,2003: 96~98.
[23] STREIT A. Self-Tuning Job Scheduling Strategies for the Resource Management of HPC Systems and Computational Grids. 2003, 10.
[24] Allcock W, Bester J, Bresnahan J, et al. GridFTP Protocol Specification. GGF GridFTP Working Group Document, 2002.
[25] Sun X H, Wu M. GHS: A Performance Prediction and Task Scheduling System for Grid Computing. IEEE International Parallel and Distributed Processing Symposium (IPDPS2003). 2003:123~135.
[26] Ranganathan K, Foster I. Decoupling computation and data scheduling in distributed data-intensive applications. Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing. Washington: IEEE Computer society, 2002: 352~258.
[27] Subramani V, Kettimuthu R, Srinivasan S, et al. Distributed job Scheduling on computational grids using multiple simultaneous requests. Proceedings of llth IEEE International Symposium on High Performance Distributed Computing. Washington: IEEE Computer society, 2002: 359~366.
[28] He Ligang, Jarvis S A, Spooner D P, et al. Optimising static workload allocation in multiclusters. Proceedings of the 18th International Parallel and Distributed Processing Symposium. Washington: IEEE Computer Soeiety, 2004: 39~48.
[29] Di Martino V. Sub optimal scheduling in a grid using genetic algorithms. Proceedings of International Parallel and Distributed Processing Symposium. Washington: IEEE Computer Society, 2003: 148~154.
[30] Arora M, Das S K, Biswas R. A de-centralized seheduling and load balancing algorithm for heterogeneous grid environments. Proceedings of 2002 International Conference on Parallel Processing Workshop. Washington: IEEE Computer Soeiety, 2002: 499~505.
[31] Wang Qingjiang, Gui Xiaolin, Zheng Shouqi. De-Centralized Job Scheduling on Computational Grids Using Distributed Backfilling. Proceedings of the 3rd International Conference on Grid and Cooperative Computing. Berlin: Springer-Verlag, 2004: 285~292.
[32] Armstrong R, Hensgen D, Kidd T. The Relative Performance of Various Mapping Algorithm is Independent of Sizable Variance in Run-time Predictions. Proeeedings of the 7th Heterogeneous computing workshop (HCW’95). IEEE computer Society Press, 1998: 79~87.
[33] Fujimoto, N Hagihara. Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid, Parallel and Distributed Computing, 2003. Proceedings of the second International Symposium on 13-14 Oct. 2003: 80~87.
[34]李小平,徐晓飞,战德臣.一种独立任务的同型机调度快速算法团.软件学报. 2002, 13, No.4.1.
[35] M Maheswaran, S Ali, H Siegel. Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, Eighth Heterogeneous Computing Workshop, 1999,4.
[36]张颖峰,李毓麟.基于进化算法的网格计算资源管理调度系统.计算机工程,2003, 29(15): 110~175.
[37] Reeves, C R. Modern heuristic techniques for combinatorial problems. John Wiley&Sons, Mc Graw-Hill International (UK) Limited,1995.
[38] Kavitha S. Golconda, Fusun Ozguner, Atakan Dogan. A Comparison of Static QoS-Based Scheduling Heuristics for a Meta-Task with Multiple QoS Dimensions in Heterogeneous Computing, Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International. 2004, 1: 106.
[39]丁箐,陈国良,顾钧.计算网格环境下一个统一的资源映射策略.软件学报. 2002, 13(7): 1303~1308.
[40] Braun T D, Siegel H J, et al. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems. Proceedings of the 8th IEEE Heterogeneous Computing Workshop ( HCW' 99 ). IEEE Computer Society Press, 1999: 15~29.
[41] I Foster. The grid: A new infrastructure 21st century science. Physics Today, 2002, 55(2): 42~47.
[42] Reynar J C. An automatic method of finding topic boundaries. Proceedings of the 15th International Conference on Computational Linguistics. 1996.
[43]伍之昂,罗军舟,宋爱波.基于QoS的网格资源管理.软件学报,2006, 17(11): 2264~2276.
[44]罗军舟,王小志,宋爱波,朱烨,伍之昂.网格QoS层次结构模型的研究.华中科技大学学报(自然科学版). 2005, 33(9): 51~53.
[45] Rajkumar Buyya, Manzur Murshed. GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing. The journal of Concurrency and Computation: Practice and Experience(CCPE). Wiley Press. 2002, 14: 13~15.