网格计算环境中的动态任务分配和调度算法的研究
摘要
网格的出现是在近些年计算机科学技术的长足发展与网络技术的广泛应用的背景下出现的，怎样利用现有资源解决大规模复杂计算问题成为计算机领域的研究重点，而网格技术就是解决这个问题的一种技术。二十世纪九十年代，围绕网格的相关研究和项目开始展开。这一技术结合并行与分布式处理技术，通过高速网络连接并集成广域网上丰富的计算机资源，利用分布、异构的各种高性能计算机、大型数据库系统、科学仪器和各种软件系统等，实现跨地域的、并行分布式联合计算，共同完成重大科学领域的大规模计算问题。
网格计算环境是一种异构计算环境，在此环境下的任务调度的决策直接影响应用程序的运行性能。而并行任务调度的一个主要目标是达到负载平衡，在执行过程中充分利用并行系统的资源。在网格环境中，并行系统本身非对称带来的复杂性、多用户环境以及并行任务粒度较粗等因素给负载平衡问题的解决带来了新的困难。本文围绕如何在网格环境中平衡负载这一目标，对进程级并行任务的动态调度问题进行了的研究，设计并实现了一个基于PVM的动态负载平衡调度系统。该系统采用了静态程序分析、自适应数据采集与交换算法，以及多用户共享等技术，改善应用程序在网格环境中的执行性能，该系统具有较高的透明性、较好的可扩展性和移植性等特点。
Go with rapid development of computing science and broad application of network technology, Grid appears in the last few years. How to solve the large scale and complex computing problems utilizing resources in existence became a hot topic in computing field. Grid just is a technology to solve this problem. In twenty century 90's, a series of research and works spread. The grid combines parallel and distributed proceeding technology, and connects with and integrates the abundant resource in WAN passing through the high-speed network. The grid utilizes kinds of distributed and heterogeneous computers, large scale databases, scientific instruments and software systems, and it realizes distributed, parallel and alliance computing, achieving large scale computing problems in science field.
The grid computing environment is a kind of heterogeneous computing environment, the dispatch for tasks in the environment can straightly influence performance of applications. A primary aim to parallel dispatch for tasks is to reach load balance, and take full advantage of the parallel systems' resource in running. In grid environment, the parallel systems inherent complexity, the mult-user environment and the large granularity of parallel tasks and so on, bring new difficulty to load balance. This article is absorbed in the aim how to balance load in grid environment and explore the dynamic dispatch to the parallel tasks in the process level, at last designs and realizes a dynamic dispatch system with PVM to load balance. This system adopts quiescent program analysis, self-adaptive data gathering and exchanging algorithm, and mult-users sharing and so on technologies. This system can improve the performance of applications running in grid environment, it have a better transparency, expansibility and portab
ility and other wise features.
网格计算环境是一种异构计算环境，在此环境下的任务调度的决策直接影响应用程序的运行性能。而并行任务调度的一个主要目标是达到负载平衡，在执行过程中充分利用并行系统的资源。在网格环境中，并行系统本身非对称带来的复杂性、多用户环境以及并行任务粒度较粗等因素给负载平衡问题的解决带来了新的困难。本文围绕如何在网格环境中平衡负载这一目标，对进程级并行任务的动态调度问题进行了的研究，设计并实现了一个基于PVM的动态负载平衡调度系统。该系统采用了静态程序分析、自适应数据采集与交换算法，以及多用户共享等技术，改善应用程序在网格环境中的执行性能，该系统具有较高的透明性、较好的可扩展性和移植性等特点。
Go with rapid development of computing science and broad application of network technology, Grid appears in the last few years. How to solve the large scale and complex computing problems utilizing resources in existence became a hot topic in computing field. Grid just is a technology to solve this problem. In twenty century 90's, a series of research and works spread. The grid combines parallel and distributed proceeding technology, and connects with and integrates the abundant resource in WAN passing through the high-speed network. The grid utilizes kinds of distributed and heterogeneous computers, large scale databases, scientific instruments and software systems, and it realizes distributed, parallel and alliance computing, achieving large scale computing problems in science field.
The grid computing environment is a kind of heterogeneous computing environment, the dispatch for tasks in the environment can straightly influence performance of applications. A primary aim to parallel dispatch for tasks is to reach load balance, and take full advantage of the parallel systems' resource in running. In grid environment, the parallel systems inherent complexity, the mult-user environment and the large granularity of parallel tasks and so on, bring new difficulty to load balance. This article is absorbed in the aim how to balance load in grid environment and explore the dynamic dispatch to the parallel tasks in the process level, at last designs and realizes a dynamic dispatch system with PVM to load balance. This system adopts quiescent program analysis, self-adaptive data gathering and exchanging algorithm, and mult-users sharing and so on technologies. This system can improve the performance of applications running in grid environment, it have a better transparency, expansibility and portab
ility and other wise features.
引文
1 Jack B. Dennis. Machines and Models for Parallel Computing. Intemational Journal of Parallel Programming. 1994,22(1): 47-77
2 Gordon Bell. Scalable, Parallel Computers: Alternatives, Issues, and Challenges. International Journal of Parallel Programming. 1994, 22(1): 3-45
3 Thomas E. Anderson, David E.Culler, David A. Patterson. A case for NOW (Networks of Workstations). IEEE Mico. 1995,15 (1)
4 Mark A. Baker, Geoffrey C. Fox. Distributed Cluster Computing Environments. Technical Report, Northeast Patroller Architectures Center, Syracuse University. 1996
5 Robert D. Blumofe, Philip A. Lisiecki. Adaptive and Reliable Parallel Computing on Networks of Workstations. In Proceeding of the USENIX 1997 Annual Technical Symposium. USENIX Association, 1997:133-148
6 IBM Corporation. Using and Administering Load Leveler Release 3.0. New York: IBM Corporation, 1996
7 Songnian Zhou, Jingwen Wang, Xiaohu Zheng, et al. Utopia: A load sharing facility for large, heterogeneous distributed computer systems. Software-Practice and Experience, 1993, 23(12): 1305-1336
8 Platform Computing Corporation. LSF Administrator's Guide. 1995
9 Arash Baratloo, Partha Dasgupta, Zvi M. Kedem. CALYPSO:A Novel Software System for Fault-Tolerant Parallel Processing on Distributed Platforms. In Proceedings of 4th IEEE International Symposium on High Performance Distributed Computing 1995. Washington D.C.: IEEE Computer Society, 1995,122-129
10 Jim Pruyne, Miron Livny. Parallel Processing on Dynamic Resources with CARMI. In: D.G. Feitelson and L. Rudolph, Eds. Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science. Springer-Verlag,
1995, 949(1): 259-278
11 Jim Pruyne, Miron Livny. Interfacing Condor and PVM to harness the cycles of workstation clusters. Journal on Future Generations of Computer Systems, 1996, 12
12 A, Bricker, M, J, Litzkow, M.Livn. Condor Technical Summary. Technical Report, Computer Sciences Department, University of Wisconsin-madison, 1992
13 D.H.J. Epema, M.Livny, R, van Dantzig, et al. A worldwide flock of Condors: load sharing among workstation clusters. Journal on Future Generations of Computer Systems. 1996,12
14 Domenico Ferrari, SongNIan Zhou. An Empirical Investigation of Load Indices for Load Balancing Applications. Technical Report, Computer Systems Research Group, Computer Science Division, UC Berkeley, 1987
15 Jonathan M. Smith. A Survey of Process Migration Mechanisms ACM Operating System Review, 1988,22(3): 28-40
16 Matt Bishop, Mark Valence, Leonard F. Wisniewski. Process Migration for Heterogeneous Distributed Systems. Technical Report, Department of Computer Science, University of California at Davis, 1995
17 John A. Stankovic, Krithivasan Ramamritham, Shengchang Cheng. Evaluation of a Flexile Task Scheduling Algorithm for Distributed Hard Real-Time Systems. IEEE Transactions on Computers, 1985, 34 (12): 1130-1142
18 Almut Burchard, Jorg Lidbeherr, Yingfeng Oh, et al. New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems. IEEE Transactions on Computers. 1995,44(12): 1429-1442
19 Kang G. Shin, Yi-Chieh Chang. Load Sharing in Distributed Real-Time Systems with State-Change Broadcasts. IEEE Transactions on Computers, 1989,38(8): 1124-1142
20 Wei Shu, Min-You Wu. Runtime Incremental Parallel Scheduling (RIPS) on Distributed Memory Computers. IEEE Transactions on Parallel and Distributed Systems, 1996,7(6): 637-649
21 Min-You Wu. On Runtime Parallel Scheduling for Processor Load Balancing. IEEE Transactions on Parallel and Distributed Systems, 1997,8(2): 173-186
22 Hesham El-Rewini, Hesham H.Ali. Task Scheduling in Multiprocessing Systems.Computer. 1995, 28(12): 27-37
23 Shen Shen Wu, David Sweeting. Heuristic algorithms for task assignment and scheduling in a processor network. Parallel Computing, 1994, 20:1-14
24 Yei Chang Kim, Young Sik Hong. A task allocation using a genetic algorithm in multicomputers systems. IEEE TENCON'93. Beijing: IAP, 1993,1:258-261
25 M. H. Willebeek-Lemair, A.E Reeves. Strategies for Dynamic Load Balancing on Highly Parallel Computers. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(9)
26 Evangelos P. Markatos, Thoms J. LeBlance. Load Balancing vs. Locality Management in Shared-Memory Multiprocessors. In Proceedings of ICPP 1992.1992,1:258-267
27 A1 Geist, Adam Beguelin, Jack Dongara, et al. PVM: Parallel Virtual Machine Massachusetts: The MIT Press, 1994
28 Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. Tennessee: University of Tennessee, Knoxville, 1995
29 Message Passing Interface Forum. MPI-2: Extensions to the Message-Passing interface. Thnessee: University of Tenessee, Knoxville, 1996
30 Anand R. Tripathi, Neeran M. Karnik. Tends in Multiprocessor and Distributed Operating Systems Designs. The Journal of Supercomputing, 1995, 9:23-49
31 Jerrell Watts, M. Rieffel, Taylor. A load balancing technique for multiphase computations. In Proceedings of High Performance Computing '97. Society for Computer Simulation, 1997,15-20
32 IBM Corporation. Using and Administering LoadLeveler Release 3.0. New York: IVM Corporation, 1996
33 Thomas P.Green. DQS User Interface Preliminary Design Document Technical report,Supercomputer Computations Research Institute, Flrida State University, 1993
34 Scott T.Leutenegger. Issues in multiprogrammed multiprocessor scheduling: [P.D.Dissertation]. Wisconsin: Department of Computer Sciences, University of Wisconsin-madison, 1990
35 Honbo Zhou, A1 Geist. "Receiver Makes Right" Date Conversion in PVM. In Proceedings of the IEEE annual international phoenix conference on computers and communications 1995. IEEE. Publisher, 1995.14:458-464
36 Honghui Lu. Message Passing Versus Distributed Shared Memory on Networks of Workstations. In Proceedings of th 8th Supercomputing Conference '95, IEEE, 1995,1:865-906
37 G.A.Geist, J.A. Kohl. PVM and MPI: s Comparison for Features. Calculateurs Paralleles, 1996, 8(2): 137-150
2 Gordon Bell. Scalable, Parallel Computers: Alternatives, Issues, and Challenges. International Journal of Parallel Programming. 1994, 22(1): 3-45
3 Thomas E. Anderson, David E.Culler, David A. Patterson. A case for NOW (Networks of Workstations). IEEE Mico. 1995,15 (1)
4 Mark A. Baker, Geoffrey C. Fox. Distributed Cluster Computing Environments. Technical Report, Northeast Patroller Architectures Center, Syracuse University. 1996
5 Robert D. Blumofe, Philip A. Lisiecki. Adaptive and Reliable Parallel Computing on Networks of Workstations. In Proceeding of the USENIX 1997 Annual Technical Symposium. USENIX Association, 1997:133-148
6 IBM Corporation. Using and Administering Load Leveler Release 3.0. New York: IBM Corporation, 1996
7 Songnian Zhou, Jingwen Wang, Xiaohu Zheng, et al. Utopia: A load sharing facility for large, heterogeneous distributed computer systems. Software-Practice and Experience, 1993, 23(12): 1305-1336
8 Platform Computing Corporation. LSF Administrator's Guide. 1995
9 Arash Baratloo, Partha Dasgupta, Zvi M. Kedem. CALYPSO:A Novel Software System for Fault-Tolerant Parallel Processing on Distributed Platforms. In Proceedings of 4th IEEE International Symposium on High Performance Distributed Computing 1995. Washington D.C.: IEEE Computer Society, 1995,122-129
10 Jim Pruyne, Miron Livny. Parallel Processing on Dynamic Resources with CARMI. In: D.G. Feitelson and L. Rudolph, Eds. Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science. Springer-Verlag,
1995, 949(1): 259-278
11 Jim Pruyne, Miron Livny. Interfacing Condor and PVM to harness the cycles of workstation clusters. Journal on Future Generations of Computer Systems, 1996, 12
12 A, Bricker, M, J, Litzkow, M.Livn. Condor Technical Summary. Technical Report, Computer Sciences Department, University of Wisconsin-madison, 1992
13 D.H.J. Epema, M.Livny, R, van Dantzig, et al. A worldwide flock of Condors: load sharing among workstation clusters. Journal on Future Generations of Computer Systems. 1996,12
14 Domenico Ferrari, SongNIan Zhou. An Empirical Investigation of Load Indices for Load Balancing Applications. Technical Report, Computer Systems Research Group, Computer Science Division, UC Berkeley, 1987
15 Jonathan M. Smith. A Survey of Process Migration Mechanisms ACM Operating System Review, 1988,22(3): 28-40
16 Matt Bishop, Mark Valence, Leonard F. Wisniewski. Process Migration for Heterogeneous Distributed Systems. Technical Report, Department of Computer Science, University of California at Davis, 1995
17 John A. Stankovic, Krithivasan Ramamritham, Shengchang Cheng. Evaluation of a Flexile Task Scheduling Algorithm for Distributed Hard Real-Time Systems. IEEE Transactions on Computers, 1985, 34 (12): 1130-1142
18 Almut Burchard, Jorg Lidbeherr, Yingfeng Oh, et al. New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems. IEEE Transactions on Computers. 1995,44(12): 1429-1442
19 Kang G. Shin, Yi-Chieh Chang. Load Sharing in Distributed Real-Time Systems with State-Change Broadcasts. IEEE Transactions on Computers, 1989,38(8): 1124-1142
20 Wei Shu, Min-You Wu. Runtime Incremental Parallel Scheduling (RIPS) on Distributed Memory Computers. IEEE Transactions on Parallel and Distributed Systems, 1996,7(6): 637-649
21 Min-You Wu. On Runtime Parallel Scheduling for Processor Load Balancing. IEEE Transactions on Parallel and Distributed Systems, 1997,8(2): 173-186
22 Hesham El-Rewini, Hesham H.Ali. Task Scheduling in Multiprocessing Systems.Computer. 1995, 28(12): 27-37
23 Shen Shen Wu, David Sweeting. Heuristic algorithms for task assignment and scheduling in a processor network. Parallel Computing, 1994, 20:1-14
24 Yei Chang Kim, Young Sik Hong. A task allocation using a genetic algorithm in multicomputers systems. IEEE TENCON'93. Beijing: IAP, 1993,1:258-261
25 M. H. Willebeek-Lemair, A.E Reeves. Strategies for Dynamic Load Balancing on Highly Parallel Computers. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(9)
26 Evangelos P. Markatos, Thoms J. LeBlance. Load Balancing vs. Locality Management in Shared-Memory Multiprocessors. In Proceedings of ICPP 1992.1992,1:258-267
27 A1 Geist, Adam Beguelin, Jack Dongara, et al. PVM: Parallel Virtual Machine Massachusetts: The MIT Press, 1994
28 Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. Tennessee: University of Tennessee, Knoxville, 1995
29 Message Passing Interface Forum. MPI-2: Extensions to the Message-Passing interface. Thnessee: University of Tenessee, Knoxville, 1996
30 Anand R. Tripathi, Neeran M. Karnik. Tends in Multiprocessor and Distributed Operating Systems Designs. The Journal of Supercomputing, 1995, 9:23-49
31 Jerrell Watts, M. Rieffel, Taylor. A load balancing technique for multiphase computations. In Proceedings of High Performance Computing '97. Society for Computer Simulation, 1997,15-20
32 IBM Corporation. Using and Administering LoadLeveler Release 3.0. New York: IVM Corporation, 1996
33 Thomas P.Green. DQS User Interface Preliminary Design Document Technical report,Supercomputer Computations Research Institute, Flrida State University, 1993
34 Scott T.Leutenegger. Issues in multiprogrammed multiprocessor scheduling: [P.D.Dissertation]. Wisconsin: Department of Computer Sciences, University of Wisconsin-madison, 1990
35 Honbo Zhou, A1 Geist. "Receiver Makes Right" Date Conversion in PVM. In Proceedings of the IEEE annual international phoenix conference on computers and communications 1995. IEEE. Publisher, 1995.14:458-464
36 Honghui Lu. Message Passing Versus Distributed Shared Memory on Networks of Workstations. In Proceedings of th 8th Supercomputing Conference '95, IEEE, 1995,1:865-906
37 G.A.Geist, J.A. Kohl. PVM and MPI: s Comparison for Features. Calculateurs Paralleles, 1996, 8(2): 137-150