基于移动Agent的网格资源调度研究
|
摘要
网格技术能够将分散在网络上的各种资源进行有机的整合,形成一个统一的整体,为用户提供强大的计算能力和信息服务,被认为是继Internet之后一次重大的科技进步。网格中的资源与传统的分布式系统资源相比具有分布性、动态性和异构性的特征,这使得网格环境下的资源管理与分配变得相当复杂。
移动Agent是一类特殊的软件Agent,它可以让程序在网络上从一台主机自主地移动到另一台主机,代表用户完成指定的任务。我们将移动Agent技术引入到网格中,设计了一个基于移动Agent的网格资源体系结构,构造了基于移动Agent的网格层次资源监控模型,解决异构环境下的资源数据收集问题。
本文从网格资源的特点出发,探索一种更加合理的网格资源调度模型和更加有效的调度策略。在分析了传统的调度模型的基础上,提出了基于Agent的改进的层次调度模型。调度模型分为全局调度层和局部调度层,不同的层次使用不同的调度策略,从而使整个调度模型更加灵活有效。
好的资源调度算法能有效地协调和分配网格资源,并优化网格系统的性能。本文根据网格环境下任务的时间相关性特点,对传统蚁群算法进行了改进,设计了一种快速网格任务调度算法。该算法不仅解决了网格调度中多目标优化问题,而且依据任务调度历史信息可以进行快速资源匹配。
使用网格模拟器GridSim对FACO算法进行了仿真模拟。仿真结果表明FACO算法具有较高的求解速度,并且可以缩短任务的执行时间。
We can integrate all kinds of the resources across the Internet into a uniform system called grid system, which can provide the gird users with powerful services such as the sharing of information and computational ability. The gird technology has been seen as an important innovation since the popularity of Internet. Comparing with traditional distributed system's resource, the resource of the gird has the characteristic of distribution, dynamic, heterogeneity, so the resource management and distribution in gird system is more complex.
After analyzed the technology of mobile agent that could move from one host to the other freely in Internet, we proposed a hierarchical model of grid resources monitoring based on mobile agent, that solve the problem of collecting resource parameter in heterogeneous environment.
The thesis is looking for a more reasonable grid resource scheduling model and more efficient scheduling policy based on the characteristics of grid resources.After discussed the traditional scheduling, proposed an improved heterogeneous grid resource scheduling model, which was based on mobile agent. This model composed of global scheduling layer and local scheduling layer. The different layers used different scheduling policies that made this model more flexible and more efficient.
One good resource scheduling algorithm could effectively assign the grid resource and improve the grid system performance. In this paper, we proposed a grid scheduler using Fast Ant Colony Algorithm, which satisfied the mutually conflicting goals of the users and the resource provider, as well as improved the velocity of the scheduler, by taking advantage of historical information on scheduling to match resource for tasks quickly.
Finally, simulated the FACO scheduling algorithm in GridSim.The simulation result indicated the FACO scheduling algorithm was the best one. It enhanced the speed of the algorithm astringency and reduced the Makespan of finishing the tasks.
移动Agent是一类特殊的软件Agent,它可以让程序在网络上从一台主机自主地移动到另一台主机,代表用户完成指定的任务。我们将移动Agent技术引入到网格中,设计了一个基于移动Agent的网格资源体系结构,构造了基于移动Agent的网格层次资源监控模型,解决异构环境下的资源数据收集问题。
本文从网格资源的特点出发,探索一种更加合理的网格资源调度模型和更加有效的调度策略。在分析了传统的调度模型的基础上,提出了基于Agent的改进的层次调度模型。调度模型分为全局调度层和局部调度层,不同的层次使用不同的调度策略,从而使整个调度模型更加灵活有效。
好的资源调度算法能有效地协调和分配网格资源,并优化网格系统的性能。本文根据网格环境下任务的时间相关性特点,对传统蚁群算法进行了改进,设计了一种快速网格任务调度算法。该算法不仅解决了网格调度中多目标优化问题,而且依据任务调度历史信息可以进行快速资源匹配。
使用网格模拟器GridSim对FACO算法进行了仿真模拟。仿真结果表明FACO算法具有较高的求解速度,并且可以缩短任务的执行时间。
We can integrate all kinds of the resources across the Internet into a uniform system called grid system, which can provide the gird users with powerful services such as the sharing of information and computational ability. The gird technology has been seen as an important innovation since the popularity of Internet. Comparing with traditional distributed system's resource, the resource of the gird has the characteristic of distribution, dynamic, heterogeneity, so the resource management and distribution in gird system is more complex.
After analyzed the technology of mobile agent that could move from one host to the other freely in Internet, we proposed a hierarchical model of grid resources monitoring based on mobile agent, that solve the problem of collecting resource parameter in heterogeneous environment.
The thesis is looking for a more reasonable grid resource scheduling model and more efficient scheduling policy based on the characteristics of grid resources.After discussed the traditional scheduling, proposed an improved heterogeneous grid resource scheduling model, which was based on mobile agent. This model composed of global scheduling layer and local scheduling layer. The different layers used different scheduling policies that made this model more flexible and more efficient.
One good resource scheduling algorithm could effectively assign the grid resource and improve the grid system performance. In this paper, we proposed a grid scheduler using Fast Ant Colony Algorithm, which satisfied the mutually conflicting goals of the users and the resource provider, as well as improved the velocity of the scheduler, by taking advantage of historical information on scheduling to match resource for tasks quickly.
Finally, simulated the FACO scheduling algorithm in GridSim.The simulation result indicated the FACO scheduling algorithm was the best one. It enhanced the speed of the algorithm astringency and reduced the Makespan of finishing the tasks.
引文
[1]I.Foster,C.Kesselman.The Grid:Blueprint for a New Computing Infrastructure.San Francisco:Morgan Kaufmann Publishers Inc.1998,279-309.
[2]I.Foster,C.Kesselman,S.Tuecke.The Anatomy of the Grid:Enabling Scalable Virtual Organizations[J].Supercomputer Applications.2001,15(3):200-222.
[3]K.Czajkowski,D.Ferguson I.Foster and et al.From Open Grid Resources Infrastructure to WS-Resource Framework:Refactoring&Evolution,Version 1.0.February,2004.http://www-106.ibm.com/developmentworksAibrary/ws-resource/gr-ogsitowsrf.html.
[4]V.Subramani.Distributed Task Scheduling on Computational Grid Using Multiple Simultaneous Requests.In:Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing.Edinburgh,Scotland:July,2002,359-366.
[5]K.Czajkowski,I.Foster,N.Karonis and et al.A Resource Management Architecture for Metacomputing Systems.Proc.IPPS/SPDP'98 Workshop on Job Scheduling Strategies for Parallel Processing,1998.
[6]Fran Berman and Rich Wolski.The AppLeS Project:A Status Report.From Proceedings of the 8th NEC Research Symposium,Berlin,Germany,May,1997.
[7]H.Casanova and J.Dongarra.NetSolve:A Network Server for Solving Computational Science Problems[J]Intl.Journal of Supercomputing Applications and High Performance Computing,Vol.11,Number 3,1997.
[8]R.Buyya,D.Abramson and J.Giddy.A Case for Economy Grid Architecture for Service-Oriented Grid Computing[C].Proceedings of the International Parallel and Distributed Processing Symposium:10~(th)IEEE International Heterogeneous Computing Workshop,San Francisco,California,USA,IEEE CS Press,USA,2001.
[9]都志辉,陈渝,刘鹏.网格计算.清华大学出版社.2002,11.
[10]马永征.科学数据网格资源调度技术研究[D].中国科学院研究生院.2005,6.
[11]I.Foster,C.Kesselman,J.M Nick,S.Tuecke.Grid Services for Distributed System Integration[J].IEEE Computer,Vol.35(6):37-46,2002.
[12]Tracy D.Braun,Howard Jay Siegel,Noah Beck.A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing System[J].Journal of Parallel and Distributed Computing,2001,61(6):810-837.
[13]Vincenzo Di Martino.Scheduling in a Grid Computing Enviroment Using Genetic Algorithm[C].Macro Mililoti the 16~(th)Int'l Parallel and Distributed Proceeding Symposium,USA,2002.
[14]唐立山等.非数值并行算法(第一册)——模拟退火算法.北京:科学出版社,2000.
[15]R.Butler,D.Engert,I.Foster,C.Kesselman et al.A National-Scale Authentication Infrastructure[J].IEEE Computer,33(12):60-66,2000.
[16]R.Buyya,D.Abramson,J.Giddy.An Economy Driven Resource Management Architecture for Global Computational Power Grids.In:Proceeding of the 2000International Conference on Parallel and Distributed Processing Techniques and Applications.USA,2000.
[17]H.Casanova,G.Obertelli,F.Berm and R.Wolski.The AppLeS Parameter Sweep Template:Use-Level Middleware for the Grid.In Proceedings of SC00,November 2000.
[18]曹鸿强.基于多经济智能主体的计算网格资源管理[D].国防科学技术大学.2000,10.
[19]V.Hamscher,U.Schwiegelshohn,A.Streitand V.Yahyapour.Evaluation of Job-Scheduling Strategies for Grid Computing[J].Grid 2000,Bangalore,India.Lecture Notes in Computer Science,Springer-Verlag,191-202,2000.
[20]C.Leangsuksun,J.Potter and S.Scott.Dynamic Task Mapping Algorithms for a Distributed Heterogeneous Computing Environment.4~(th)IEEE Heterogeneous Computing Workshop,Apr,30-34,1995.
[21]F.Berman and R.Wolski.The AppLeS Project:A Status Report[C],In:Proceedings of the 8~(th)NEC Research Symposium,Berlin,Germany,May 1997.
[22]D.Hensgen,T.Kidd,et al.An Overview of MSHN:The Management System for Heterogeneous Networks[C].8~(th)Workshop on Heterogeneous Computing Systems,San Juan,Puerto Rico,1999.
[23]R.Buyya,D.Abramson,J.Giddy.Nimrod/G:An Architecture for a Resource Management and Scheduling System in a Global Computational Grid[C].International Conference on High Performance Computing in Asia-Pacific Region,Beijing,China.IEEE Computer Society Press,USA,2000.
[24]W.Hoschek,J.Jaen-Martinez,A.Samar and et al.Data Management in an International Data Grid Project.Proceedings of the First IEEE/ACM International Workshop on Grid Computing,(Springer Verlag Press,Germany),India,2000.
[25]S.Chapin,J.Karpovich,A.Grimshaw.The Legion Resource Management System [C].Proceedings of the 5~(th)Workshop on Job Scheduling Strategies for Parallel Processing,April 1999.
[26]IBM Mobile Agent Facility Specification.http://www.omg.org/library/issuerpt.html,2000.1.
[27]N.Kapadia,R.Figueiredo and J.Fortes.PUNCH:Web Portal for Running Tools,IEEE Micro,May-June,2000.
[28]W.Allcock.GridFTP Protocol Specification(Global Grid Forum Recommendation GFD).March 2003.
[29]M.Neary,A.Phipps,S.Richman,P.Cappello.Javelin2.0:Java-Based Parallel Computing on the Internet[C].Proceedings of European Parallel Computing Conference,Germany,2000.
[30]陈国春.基于移动Agent的网格资源监控和发现的研究[D].安徽大学.2007,4.
[31]丁永生.计算机智能——理论、技术与应用.科学出版社,2004,8.
[32]张军,常艳,谢向辉等.负载平衡的多级并行对等计算在新药研发网格中的实现[J].计算机研究与发展,2004,41(12):2047-2053.
[33]张云勇,刘锦德.移动Agent技术[M].北京:清华大学出版社,2003.
[34]S.Ishohn,R.Yahyapour.Grid Scheduling Architecture[J].Global Grid Forum Draft Recommendation,2002,26(4):21-31.
[35]W.Zhang,S.Jin,Wu Quanyuan.Liuux Virtual Server:Server Clustering for Scalable Network Services[C].Beijing:Proceeding of World Congress Conference 2000,2000,9(7):21-25.
[36]周集良,彭小宁,王正华.基于集群的负载平衡调度算法研究与实现[J].计算机工程,2005,31(12):108-110.
[37]赵新宇,林作铨.合同网协议中的Agent可信度模型[J].计算机科学 2006,33(6)150-153.
[38]F.Azzedin,M.Maheswaran.Integrating Trust into Grid Resource Management Systems[C].Canada:Proc.of International Conference on Parallel Processing.2002.47-54.
[39]S.Song,K.Hwang,Y.K.Kwok.Trusted grid computing with security binding and trust integration.[J]Journal of Grid Computing,2005,3(1):53-73.
[40]M.Dorigo,E.Bonabea,G.Theraulaz Ant Algorithms and Stigmergy[J].Future Generation Computer Systems,2000,16:851-871.
[41]宋晓江,卢俊宇,隋明磊.基于免疫蚁群算法的Job-shop调度问题[J].计算机应用,2007,27(5):1183-1186.
[42]O.H.Ibarra,C.E.Kim.Heuristic Algorithms for Scheduling Independent Tasks on Non-identical Processors[J].Journal of the ACM,1977,24(2):280-289.
[43]M.Maheswaran,S.Ali,H.J.Siegel and et al.Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems[J].Journal of Parallel and Distributed Computing,1999,59(2):107-121.
[44]A.Abraham,R.Buyya.Nature's Heuristics for Scheduling Jobs on Computational Grids[C].In:The 8~(th)Intel Conf.on Advanced Computing and Communications,Cochin,India,2000.
[45]M.Pinedo.Scheduling:Theory,Algorithms and Systems[M].Prentice Hall,Englewood Cliffs,NJ,1995.
[46]王莉,窦旻,刘宗田,黄美丽.一种快速网格任务调度策略[J].计算机科学,2007,34(6):128-130.
[47]GR.Nudd,D.J.Kerbyson,E.Papaefstathiou,et al.PACE-A Toolset for the Performance Prediction of Parallel and Distributed Systems[J].International Journal of High Performance Computing Applications,2000,14(3):228-251.
[2]I.Foster,C.Kesselman,S.Tuecke.The Anatomy of the Grid:Enabling Scalable Virtual Organizations[J].Supercomputer Applications.2001,15(3):200-222.
[3]K.Czajkowski,D.Ferguson I.Foster and et al.From Open Grid Resources Infrastructure to WS-Resource Framework:Refactoring&Evolution,Version 1.0.February,2004.http://www-106.ibm.com/developmentworksAibrary/ws-resource/gr-ogsitowsrf.html.
[4]V.Subramani.Distributed Task Scheduling on Computational Grid Using Multiple Simultaneous Requests.In:Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing.Edinburgh,Scotland:July,2002,359-366.
[5]K.Czajkowski,I.Foster,N.Karonis and et al.A Resource Management Architecture for Metacomputing Systems.Proc.IPPS/SPDP'98 Workshop on Job Scheduling Strategies for Parallel Processing,1998.
[6]Fran Berman and Rich Wolski.The AppLeS Project:A Status Report.From Proceedings of the 8th NEC Research Symposium,Berlin,Germany,May,1997.
[7]H.Casanova and J.Dongarra.NetSolve:A Network Server for Solving Computational Science Problems[J]Intl.Journal of Supercomputing Applications and High Performance Computing,Vol.11,Number 3,1997.
[8]R.Buyya,D.Abramson and J.Giddy.A Case for Economy Grid Architecture for Service-Oriented Grid Computing[C].Proceedings of the International Parallel and Distributed Processing Symposium:10~(th)IEEE International Heterogeneous Computing Workshop,San Francisco,California,USA,IEEE CS Press,USA,2001.
[9]都志辉,陈渝,刘鹏.网格计算.清华大学出版社.2002,11.
[10]马永征.科学数据网格资源调度技术研究[D].中国科学院研究生院.2005,6.
[11]I.Foster,C.Kesselman,J.M Nick,S.Tuecke.Grid Services for Distributed System Integration[J].IEEE Computer,Vol.35(6):37-46,2002.
[12]Tracy D.Braun,Howard Jay Siegel,Noah Beck.A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing System[J].Journal of Parallel and Distributed Computing,2001,61(6):810-837.
[13]Vincenzo Di Martino.Scheduling in a Grid Computing Enviroment Using Genetic Algorithm[C].Macro Mililoti the 16~(th)Int'l Parallel and Distributed Proceeding Symposium,USA,2002.
[14]唐立山等.非数值并行算法(第一册)——模拟退火算法.北京:科学出版社,2000.
[15]R.Butler,D.Engert,I.Foster,C.Kesselman et al.A National-Scale Authentication Infrastructure[J].IEEE Computer,33(12):60-66,2000.
[16]R.Buyya,D.Abramson,J.Giddy.An Economy Driven Resource Management Architecture for Global Computational Power Grids.In:Proceeding of the 2000International Conference on Parallel and Distributed Processing Techniques and Applications.USA,2000.
[17]H.Casanova,G.Obertelli,F.Berm and R.Wolski.The AppLeS Parameter Sweep Template:Use-Level Middleware for the Grid.In Proceedings of SC00,November 2000.
[18]曹鸿强.基于多经济智能主体的计算网格资源管理[D].国防科学技术大学.2000,10.
[19]V.Hamscher,U.Schwiegelshohn,A.Streitand V.Yahyapour.Evaluation of Job-Scheduling Strategies for Grid Computing[J].Grid 2000,Bangalore,India.Lecture Notes in Computer Science,Springer-Verlag,191-202,2000.
[20]C.Leangsuksun,J.Potter and S.Scott.Dynamic Task Mapping Algorithms for a Distributed Heterogeneous Computing Environment.4~(th)IEEE Heterogeneous Computing Workshop,Apr,30-34,1995.
[21]F.Berman and R.Wolski.The AppLeS Project:A Status Report[C],In:Proceedings of the 8~(th)NEC Research Symposium,Berlin,Germany,May 1997.
[22]D.Hensgen,T.Kidd,et al.An Overview of MSHN:The Management System for Heterogeneous Networks[C].8~(th)Workshop on Heterogeneous Computing Systems,San Juan,Puerto Rico,1999.
[23]R.Buyya,D.Abramson,J.Giddy.Nimrod/G:An Architecture for a Resource Management and Scheduling System in a Global Computational Grid[C].International Conference on High Performance Computing in Asia-Pacific Region,Beijing,China.IEEE Computer Society Press,USA,2000.
[24]W.Hoschek,J.Jaen-Martinez,A.Samar and et al.Data Management in an International Data Grid Project.Proceedings of the First IEEE/ACM International Workshop on Grid Computing,(Springer Verlag Press,Germany),India,2000.
[25]S.Chapin,J.Karpovich,A.Grimshaw.The Legion Resource Management System [C].Proceedings of the 5~(th)Workshop on Job Scheduling Strategies for Parallel Processing,April 1999.
[26]IBM Mobile Agent Facility Specification.http://www.omg.org/library/issuerpt.html,2000.1.
[27]N.Kapadia,R.Figueiredo and J.Fortes.PUNCH:Web Portal for Running Tools,IEEE Micro,May-June,2000.
[28]W.Allcock.GridFTP Protocol Specification(Global Grid Forum Recommendation GFD).March 2003.
[29]M.Neary,A.Phipps,S.Richman,P.Cappello.Javelin2.0:Java-Based Parallel Computing on the Internet[C].Proceedings of European Parallel Computing Conference,Germany,2000.
[30]陈国春.基于移动Agent的网格资源监控和发现的研究[D].安徽大学.2007,4.
[31]丁永生.计算机智能——理论、技术与应用.科学出版社,2004,8.
[32]张军,常艳,谢向辉等.负载平衡的多级并行对等计算在新药研发网格中的实现[J].计算机研究与发展,2004,41(12):2047-2053.
[33]张云勇,刘锦德.移动Agent技术[M].北京:清华大学出版社,2003.
[34]S.Ishohn,R.Yahyapour.Grid Scheduling Architecture[J].Global Grid Forum Draft Recommendation,2002,26(4):21-31.
[35]W.Zhang,S.Jin,Wu Quanyuan.Liuux Virtual Server:Server Clustering for Scalable Network Services[C].Beijing:Proceeding of World Congress Conference 2000,2000,9(7):21-25.
[36]周集良,彭小宁,王正华.基于集群的负载平衡调度算法研究与实现[J].计算机工程,2005,31(12):108-110.
[37]赵新宇,林作铨.合同网协议中的Agent可信度模型[J].计算机科学 2006,33(6)150-153.
[38]F.Azzedin,M.Maheswaran.Integrating Trust into Grid Resource Management Systems[C].Canada:Proc.of International Conference on Parallel Processing.2002.47-54.
[39]S.Song,K.Hwang,Y.K.Kwok.Trusted grid computing with security binding and trust integration.[J]Journal of Grid Computing,2005,3(1):53-73.
[40]M.Dorigo,E.Bonabea,G.Theraulaz Ant Algorithms and Stigmergy[J].Future Generation Computer Systems,2000,16:851-871.
[41]宋晓江,卢俊宇,隋明磊.基于免疫蚁群算法的Job-shop调度问题[J].计算机应用,2007,27(5):1183-1186.
[42]O.H.Ibarra,C.E.Kim.Heuristic Algorithms for Scheduling Independent Tasks on Non-identical Processors[J].Journal of the ACM,1977,24(2):280-289.
[43]M.Maheswaran,S.Ali,H.J.Siegel and et al.Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems[J].Journal of Parallel and Distributed Computing,1999,59(2):107-121.
[44]A.Abraham,R.Buyya.Nature's Heuristics for Scheduling Jobs on Computational Grids[C].In:The 8~(th)Intel Conf.on Advanced Computing and Communications,Cochin,India,2000.
[45]M.Pinedo.Scheduling:Theory,Algorithms and Systems[M].Prentice Hall,Englewood Cliffs,NJ,1995.
[46]王莉,窦旻,刘宗田,黄美丽.一种快速网格任务调度策略[J].计算机科学,2007,34(6):128-130.
[47]GR.Nudd,D.J.Kerbyson,E.Papaefstathiou,et al.PACE-A Toolset for the Performance Prediction of Parallel and Distributed Systems[J].International Journal of High Performance Computing Applications,2000,14(3):228-251.