基于虚拟计算环境的元调度器研究
摘要
网格技术的提出为互联网络中资源共享、大规模计算应用的解决提供了很好的支撑平台,但是网格环境本身固有的动态性、异构性等特点,又给网格作业的调度带来了不小的难度,因而网格调度问题研究是当今世界网格技术研究的一个重点和难点。本文依托大规模科学和工程计算,研究设计了适合地震资料处理的网格资源调度平台系统,目的是为用户提供稳定、透明、方便的网格任务提交环境,使网格作业快速、高效的运行在合适的网格资源中。通过对虚拟计算环境理论和网格技术的研究,本文提出了一种自适应的层次型分级调度模型架构,这种模型具有高度可扩展性,能够适应资源动态变化。另外结合网格调度的具体功能需求,设计出了一种网格元调度器,并对其各个组成模块进行了详细的设计和阐述。在调度策略的选取上,针对复杂的地震资料处理流程,专门就关联任务调度进行研究,提出了一种基于DAG图划分的调度算法,可以有效地减少资源选择时间以及作业执行时间,经过实验验证,该算法具有较高的调度性能。
The grid technology has provided a good platform for resources sharing and large-scale computation application, but grid environment is dynamic and isomeric which gave the grid scheduling some difficulty, thus the grid scheduling problem is one key and the difficulty of grid technology in the world. Based on the large-scale science and the engineering calculation, this article designs a grid scheduling platform system which suited the earthquake data processing, The goal is to provide stably, transparent and convenient grid submission environment for the user, to run the tasks in the appropriate grid resources fast and effectively. By researching the virtual computing environment theory (iVCE) and the grid technology, this article proposed a kind of auto-adapted scheduling model construction with level graduation. It has high extendibility, and can adapt the resources dynamic changes. Moreover, based on the demand of grid scheduling function, we designed a kind of grid Meta-scheduler, and has carried on detailed design and elaboration to its each module. While selecting the dispatch strategy, in view of the complex earthquake data processing flow, we specially researched the related tasks scheduling, and presented a related task scheduling algorithm, which based on virtual clusters and the division of task. This algorithm has fully considered the influence of heterogeneous grid environment and obtained better scheduling effects.
The grid technology has provided a good platform for resources sharing and large-scale computation application, but grid environment is dynamic and isomeric which gave the grid scheduling some difficulty, thus the grid scheduling problem is one key and the difficulty of grid technology in the world. Based on the large-scale science and the engineering calculation, this article designs a grid scheduling platform system which suited the earthquake data processing, The goal is to provide stably, transparent and convenient grid submission environment for the user, to run the tasks in the appropriate grid resources fast and effectively. By researching the virtual computing environment theory (iVCE) and the grid technology, this article proposed a kind of auto-adapted scheduling model construction with level graduation. It has high extendibility, and can adapt the resources dynamic changes. Moreover, based on the demand of grid scheduling function, we designed a kind of grid Meta-scheduler, and has carried on detailed design and elaboration to its each module. While selecting the dispatch strategy, in view of the complex earthquake data processing flow, we specially researched the related tasks scheduling, and presented a related task scheduling algorithm, which based on virtual clusters and the division of task. This algorithm has fully considered the influence of heterogeneous grid environment and obtained better scheduling effects.
引文
[1] Berners-Lee T, Hall W, Hendler J, et al. Creating a science of the Web[J]. Science, 2006, 313(11): 769-771.
[2] Gong L. Jota: A network programming environment[J]. IEEE Internet Compute, 2001, 5(3): 88-94.
[3] Licklider J C R. Memorandum for Members and Affiliates of the Intergalactic Computer Network[C]. Advanced Research Projects Agency, 1963, Washington DC, USA.
[4] Andrew S T. Distributed Operating Systems[J]. New Jersey: Prentice Hall, 1999.
[5] Foster I., Carl Kesselman. Grid: Blueprint for a New Computing Infrastructure[C]. Morgan: Morgan-Kaufman, 1998.
[6]卢锡城,王怀民,王戟.虚拟计算环境iVCE:概念与体系结构[J].中国科学,2006.
[7] Zhang Weizhe, Tian Zhihong, ea tl. Multi-Cluster Co-Allocation Scheduling Algorithms in Virtual Computing Environment[J]. Journal of software,2007,18(8):2027-2037.
[8]邓静,王帮海,徐建哲,李振坤.网格实例—Globus的研究与探讨[J].计算机应用,2003.
[9] Foster I., Kesselman C, Nick J, et al. Grid services for distributed system integration[C]. Computer, 2002, 35(6):37-46.
[10] Foster I., Geisler J., Nickless k., et al. Software Infrastructure for the I-WAY High Performance Distributed Computing Experiment[C]. 5th IEEE Symposium on High Performance Distributed Computing,1997:562-571.
[11]亓雪冬,李霞,梁鸿等.一种新型的数据网格动态副本策略[J].北京交通大学学报(自然科学版) ,2008,32(6):111-115.
[12] Alain A., Dave B., Jon G., et al. Issues in Grid Scheduling Report of the workshop[J], E-Science Institute,2003.
[13] K.Czajkowski, I.Foster, N.Karonis, et al. A Resource Management Architecture for Meta computing Systems[C]. IPPS/SPDP'98 Workshop on Job Scheduling Strategies for Parallel Processing,1998,62-82.
[14] Frey, J., et al., Condor-G:A Computation Management Agent for Multi-Institutional Grids[J].Cluster Computing,2002.5(3):p.237-246.
[15] Berman F., Computing W R., Casanova H, et al. Adaptive Computing on the Grid Using AppLeS[C]. IEEE Transactions on Parallel and Distributed Systems, 2003;14(4): 369-382.
[16] Cluster Resources, SILVER Design Specification[Z]. http://www.clusterresources.com/products/mwm/docs/17.0_moab_grid_scheduler.shtml#/docs/2.1.4gridconfig.shtml, 2009.
[17] Gridway, Distributed Architecture Group from Universidad Complutense[Z], http://www.gridway.org/, 2006.
[18] Rajic H., et al. Distributed Resource Management Application API Specification 1.0. Technical report[C], DRMAA Working Group-The Global Grid Forum, 2003.
[19] Eduardo H., Rubens M.. A framework for adaptive execution in grids[J]. Software-practice and experience, 2004, 34:631–651.
[20] Czajkowski K., Fitzgerald S., Foster I., et al. Grid Information Services for Distributed Resource Sharing[C]. Proceedings of the Tenth IEEE International Symposium on High-Performance Distributed Computing(HPDC-10), IEEE Press, August 2001.
[21]丁肈辉.网格元调度系统的研究和CSF4元调度器的设计与实现[D].吉林大学.长春:2009.
[22] Ioan Raicu, Yong Zhao, Catalin Dumitrescu, et al. Falkon: a Fast and Light-weight task execution framework[R]. SC07, 2007:10-16.
[23]董璇,陈进平.网格环境下机群管理系统[J].计算机工程与设计,2007,28(22).
[24]李源,郑全录,曾韵. PBS作业管理系统分析.现代计算机[J],2004.
[25] Bose,B. Wickman, C.Wood. MARS: A Meta_scheduler for Distributed Resources in Campus Grids[C]. 5th International Workshop on Grid Computing(GRID 2004). IEEE Computer Society, 2004.
[26] Abramson D., J. Giddy, L. Kotler. High performance parametric modeling with Nimrod/G: Killer application for the global grid[C], IPDPS. 2000.
[27] R. Buyya, D. Abramson, S. Venugopal, The Grid Economy[C]. Proc. of the IEEE, 2005, 93(3): 698-714.
[28]郑然,李胜利,金海.网格资源管理与调度模型的研究[J].华中科技大学学报(自然科学版), 2001,29(12):87-89.
[29]张燕.网格资源发现关键技术研究[D].国防科技大学研究生院.长沙:2007.
[30]徐志伟,冯百明,李伟.网格计算技术[M].北京:电子工业出版社,2004.
[31]李胜利.基于Web的网格资源管理与调度[D].华中科技大学.武汉:2002.
[32] Eduardo Huedo, Ruben S. Montero, et al. A framework for adaptive execution in grids[J]. Software-practice and experience, 2004, 34:631-651.
[33] FosterI, Kesselman C. Globus: A meta_computing infrastructure toolkit[J]. International Journal of Supercomputer Applications,1997,11(2):115-128.
[34] Eduardo Huedo, Ruben S. Montero, et al. Experiences on Grid Resource SelectionConsidering Resource Proximity [C]. Proc. of 1st European Across Grids Conf.,2003.
[35] Massie M., B. Chun, D. Culler. The Ganglia Distributed Monitoring System. Implementation and Experience[J]. Parallel Computing,2004.30:817-840.
[36]郭东,胡亮.网格中比较CPU计算能力的一种方法[J].吉林大学学报(理学版),2005,43(2):174-178.
[37]亓雪冬.基于地震资料偏移成像的计算网格研究及应用[D].中国石油大学.东营:2009.
[38]蒋廷耀,李庆华.DAG任务图的一种调度算法[J].小型微型计算机系统,2003,24(10):1796-1799.
[39]周佳祥,郑纬民.基于DAG图解-重构的集群系统静态调度算法[J].软件学报,2000,11(8):1097-1104.
[40] Sabuncuoglu I, Bayiz M. Theory and Methodology Analysis of reactive scheduling problems in a job shop environment[J]. European Journal of Operational Research, 2000,126.
[41] CHEN B, VLIET A V. An optimal algorithm for preemptive on-line scheduling[J]. Operations Research Letters, 1995,18(3):127-131.
[42] Chekuri C., Motwani R., Natarajan B., et al. Approximation techniques for average completion time scheduling [M]; SIAM Journal on Computing, 2001.
[43] Carter B R, Watson D W, Freund R F, et al. Generational scheduling for dynamic task management in heterogeneous computing systems[J]. Journal of Information Sciences, 1998,106 : 219-236.
[44]桂小林,钱德沛.元计算环境下的支持依赖任务的OGS算法研究[J].计算机学报,2002,25(6):582-586.
[45] Yang T, Gerasoulis A. DSC: Scheduling parallel tasks on an unbounded number of processors[C]. IEEE Trans. on Parallel and Distributed Systems, 1994,5(9):951-967.
[46] Shi Wei, Zheng Weimin. The B balanced dynamic path scheduling algorithm of dependent task graphs[J]. Chinese J. Computers, 2001,9:991-997.
[47] Kwok Yu-kwong, Ahmad. Dynamic critical-path scheduling an effective technique for allocation task graphs to multiprocessors[J]. IEEE Trans on Parallel and Distributed Systems,1996,7(5):506-521.
[48]高承实,付江柳,戴青.网格计算环境下费用-时间优化i-DAG调度算法[J].计算机工程,2007,33(24):37-40.
[49] Wu M Y, GajskiD D. Hypertool: a programming aid for message-passing systems[J]. IEEE Trans Parallel and Distributed systems, 1990,1(3):330-343.
[50] Ishfaq Ahmad, Kwok Yu-Kwong. On exploiting task duplication in parallel programs scheduling[J]. IEEE Trans on Parallel and Distributed Systems, 1998,9(9):872-892.
[51] Sodhi S, Subhlok J. Skeleton based performance prediction on shared networks[C]. In: Moreira E, ed. Proc. of the 4th IEEE Symp. on Cluster Computing and the Grid (CCGrid 2004). Washington: IEEE Computer Press, 2004. 723-730.
[2] Gong L. Jota: A network programming environment[J]. IEEE Internet Compute, 2001, 5(3): 88-94.
[3] Licklider J C R. Memorandum for Members and Affiliates of the Intergalactic Computer Network[C]. Advanced Research Projects Agency, 1963, Washington DC, USA.
[4] Andrew S T. Distributed Operating Systems[J]. New Jersey: Prentice Hall, 1999.
[5] Foster I., Carl Kesselman. Grid: Blueprint for a New Computing Infrastructure[C]. Morgan: Morgan-Kaufman, 1998.
[6]卢锡城,王怀民,王戟.虚拟计算环境iVCE:概念与体系结构[J].中国科学,2006.
[7] Zhang Weizhe, Tian Zhihong, ea tl. Multi-Cluster Co-Allocation Scheduling Algorithms in Virtual Computing Environment[J]. Journal of software,2007,18(8):2027-2037.
[8]邓静,王帮海,徐建哲,李振坤.网格实例—Globus的研究与探讨[J].计算机应用,2003.
[9] Foster I., Kesselman C, Nick J, et al. Grid services for distributed system integration[C]. Computer, 2002, 35(6):37-46.
[10] Foster I., Geisler J., Nickless k., et al. Software Infrastructure for the I-WAY High Performance Distributed Computing Experiment[C]. 5th IEEE Symposium on High Performance Distributed Computing,1997:562-571.
[11]亓雪冬,李霞,梁鸿等.一种新型的数据网格动态副本策略[J].北京交通大学学报(自然科学版) ,2008,32(6):111-115.
[12] Alain A., Dave B., Jon G., et al. Issues in Grid Scheduling Report of the workshop[J], E-Science Institute,2003.
[13] K.Czajkowski, I.Foster, N.Karonis, et al. A Resource Management Architecture for Meta computing Systems[C]. IPPS/SPDP'98 Workshop on Job Scheduling Strategies for Parallel Processing,1998,62-82.
[14] Frey, J., et al., Condor-G:A Computation Management Agent for Multi-Institutional Grids[J].Cluster Computing,2002.5(3):p.237-246.
[15] Berman F., Computing W R., Casanova H, et al. Adaptive Computing on the Grid Using AppLeS[C]. IEEE Transactions on Parallel and Distributed Systems, 2003;14(4): 369-382.
[16] Cluster Resources, SILVER Design Specification[Z]. http://www.clusterresources.com/products/mwm/docs/17.0_moab_grid_scheduler.shtml#/docs/2.1.4gridconfig.shtml, 2009.
[17] Gridway, Distributed Architecture Group from Universidad Complutense[Z], http://www.gridway.org/, 2006.
[18] Rajic H., et al. Distributed Resource Management Application API Specification 1.0. Technical report[C], DRMAA Working Group-The Global Grid Forum, 2003.
[19] Eduardo H., Rubens M.. A framework for adaptive execution in grids[J]. Software-practice and experience, 2004, 34:631–651.
[20] Czajkowski K., Fitzgerald S., Foster I., et al. Grid Information Services for Distributed Resource Sharing[C]. Proceedings of the Tenth IEEE International Symposium on High-Performance Distributed Computing(HPDC-10), IEEE Press, August 2001.
[21]丁肈辉.网格元调度系统的研究和CSF4元调度器的设计与实现[D].吉林大学.长春:2009.
[22] Ioan Raicu, Yong Zhao, Catalin Dumitrescu, et al. Falkon: a Fast and Light-weight task execution framework[R]. SC07, 2007:10-16.
[23]董璇,陈进平.网格环境下机群管理系统[J].计算机工程与设计,2007,28(22).
[24]李源,郑全录,曾韵. PBS作业管理系统分析.现代计算机[J],2004.
[25] Bose,B. Wickman, C.Wood. MARS: A Meta_scheduler for Distributed Resources in Campus Grids[C]. 5th International Workshop on Grid Computing(GRID 2004). IEEE Computer Society, 2004.
[26] Abramson D., J. Giddy, L. Kotler. High performance parametric modeling with Nimrod/G: Killer application for the global grid[C], IPDPS. 2000.
[27] R. Buyya, D. Abramson, S. Venugopal, The Grid Economy[C]. Proc. of the IEEE, 2005, 93(3): 698-714.
[28]郑然,李胜利,金海.网格资源管理与调度模型的研究[J].华中科技大学学报(自然科学版), 2001,29(12):87-89.
[29]张燕.网格资源发现关键技术研究[D].国防科技大学研究生院.长沙:2007.
[30]徐志伟,冯百明,李伟.网格计算技术[M].北京:电子工业出版社,2004.
[31]李胜利.基于Web的网格资源管理与调度[D].华中科技大学.武汉:2002.
[32] Eduardo Huedo, Ruben S. Montero, et al. A framework for adaptive execution in grids[J]. Software-practice and experience, 2004, 34:631-651.
[33] FosterI, Kesselman C. Globus: A meta_computing infrastructure toolkit[J]. International Journal of Supercomputer Applications,1997,11(2):115-128.
[34] Eduardo Huedo, Ruben S. Montero, et al. Experiences on Grid Resource SelectionConsidering Resource Proximity [C]. Proc. of 1st European Across Grids Conf.,2003.
[35] Massie M., B. Chun, D. Culler. The Ganglia Distributed Monitoring System. Implementation and Experience[J]. Parallel Computing,2004.30:817-840.
[36]郭东,胡亮.网格中比较CPU计算能力的一种方法[J].吉林大学学报(理学版),2005,43(2):174-178.
[37]亓雪冬.基于地震资料偏移成像的计算网格研究及应用[D].中国石油大学.东营:2009.
[38]蒋廷耀,李庆华.DAG任务图的一种调度算法[J].小型微型计算机系统,2003,24(10):1796-1799.
[39]周佳祥,郑纬民.基于DAG图解-重构的集群系统静态调度算法[J].软件学报,2000,11(8):1097-1104.
[40] Sabuncuoglu I, Bayiz M. Theory and Methodology Analysis of reactive scheduling problems in a job shop environment[J]. European Journal of Operational Research, 2000,126.
[41] CHEN B, VLIET A V. An optimal algorithm for preemptive on-line scheduling[J]. Operations Research Letters, 1995,18(3):127-131.
[42] Chekuri C., Motwani R., Natarajan B., et al. Approximation techniques for average completion time scheduling [M]; SIAM Journal on Computing, 2001.
[43] Carter B R, Watson D W, Freund R F, et al. Generational scheduling for dynamic task management in heterogeneous computing systems[J]. Journal of Information Sciences, 1998,106 : 219-236.
[44]桂小林,钱德沛.元计算环境下的支持依赖任务的OGS算法研究[J].计算机学报,2002,25(6):582-586.
[45] Yang T, Gerasoulis A. DSC: Scheduling parallel tasks on an unbounded number of processors[C]. IEEE Trans. on Parallel and Distributed Systems, 1994,5(9):951-967.
[46] Shi Wei, Zheng Weimin. The B balanced dynamic path scheduling algorithm of dependent task graphs[J]. Chinese J. Computers, 2001,9:991-997.
[47] Kwok Yu-kwong, Ahmad. Dynamic critical-path scheduling an effective technique for allocation task graphs to multiprocessors[J]. IEEE Trans on Parallel and Distributed Systems,1996,7(5):506-521.
[48]高承实,付江柳,戴青.网格计算环境下费用-时间优化i-DAG调度算法[J].计算机工程,2007,33(24):37-40.
[49] Wu M Y, GajskiD D. Hypertool: a programming aid for message-passing systems[J]. IEEE Trans Parallel and Distributed systems, 1990,1(3):330-343.
[50] Ishfaq Ahmad, Kwok Yu-Kwong. On exploiting task duplication in parallel programs scheduling[J]. IEEE Trans on Parallel and Distributed Systems, 1998,9(9):872-892.
[51] Sodhi S, Subhlok J. Skeleton based performance prediction on shared networks[C]. In: Moreira E, ed. Proc. of the 4th IEEE Symp. on Cluster Computing and the Grid (CCGrid 2004). Washington: IEEE Computer Press, 2004. 723-730.