Scheduling divisible loads in the dynamic heterogeneous grid environment

ABSTRACT

According to the special features of the dynamic heterogeneous grid environment, a loose-coupled and scalable resource model is described by a hybrid multi-level tree reflecting actual networks for organizing distributed resources. The resource model is maintained in a distributed way, making it loose-coupled and scalable, which is practical for many grid applications, especially for sequence analysis in Bioinformatics. Algorithms of resource location and job scheduling are discussed. The divisible load theory (DLT) is introduced to grid computing through applying divisible load scheduling on the model, an algorithm called recursively equivalence is presented to overcome difficulties in developing DLT analysis on the dynamic heterogeneous tree. Experiment result is presented to evaluate the model.

REFERENCES

• 1: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 2: Olivier Beaumont , Arnaud Legrand , Yves Robert , Larry Carter , Jeanne Ferrante, Bandwidth-Centric Allocation of Independent Tasks on Heterogeneous Platforms, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.79, April 15-19, 2002
• 3: Introduction to Divisible Tasks, http://www.cs.put.poznan.pl
• 4: Cheng, Y.-C. and Robertazzi, T. G., "Distributed computation with communication delay", IEEE Transactions on Aerospace and Electronic Systems 24, 1988, pp. 700--712.
• 5: Veeravalli Bharadwaj , Thomas G. Robertazzi , Debasish Ghose, Scheduling Divisible Loads in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos, CA, 1996
• 6: M. Drozdowski, "Selected problems of scheduling tasks in multiprocessor computing systems". PhD thesis, Instytut Informatyki Politechnika Poznanska, Poznan, 1997.
• 7: S. Bataineh and T. G. Robertazzi, "Distributed Computation for a Bus Network with Communication Delays," Proc. 1991 Conf. Information Sciences and Systems, Johns Hopkins Univ., Baltimore, Md., Mar. 1991, pp. 709--714.
• 8: Y. C. Cheng and T. G. Robertazzi, "Distributed Computation for a Tree Network with Communication Delays," IEEE Trans. Aerospace and Electronic Systems, Vol. 26, no. 3, May 1990, pp. 511--516.
• 9: J. Błażewicz , M. Drozdowski, Scheduling divisible jobs on hypercubes, Parallel Computing, v.21 n.12, p.1945-1956, Dec. 1995 [doi>10.1016/0167-8191(95)00046-1 ]
• 10: J. Blazewicz and M. Drozdowski, "The Performance Limits of a Two-Dimensional Network of Load-Sharing Processors", Foundations of Computing and Decision Sciences, Vol. 21, no. 1, 1996, pp. 3--15.
• 11: Y. Yang and H. Casanova, "Multi-round algorithm for scheduling divisible workload applications: analysis and experimental evaluation", Technical Report CS2002--0721, Dept. of Computer Science and Engineering, University of California, San Diego, 2002.
• 12: O. Beaumont , A. Legrand , Y. Robert, Optimal Algorithms for Scheduling Divisible Workloads on Heterogeneous Systems, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.98.2, April 22-26, 2003
• 13: J. Sohn and T. G. Robertazzi. "Optimal divisible load sharing for bus networks", IEEE Transactions on Aerospace and Electronic Systems, 32, 1996, 34--40.
• 14: Globus project, http://www.globus.org
• 15: I. Foster and C. Kesselman. Globus. "A metacomputing infrastructure toolkit", International Journal of Supercomputer Applications, 11(2), 1997, pp. 115--128.
• 16: Lingyun Yang , Jennifer M. Schopf , Ian Foster, Conservative Scheduling: Using Predicted Variance to Improve Scheduling Decisions in Dynamic Environments, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.31, November 15-21, 2003
• 17: Yu, D., and Robertazzi T. G., "Divisible Load Scheduling for Grid Computing", 15th IASTED International Conference Parallel and Distributed Computing and Systems, Marina del Rey, CA, USA, 2003.
• 18: K. van der Raadt, Y. Yang, and H. Casanova. "APST-DV: Divisible Load Scheduling and Deployment on the Grid". Technical Report CS2004--0785, Dept. of Computer Science and Engineering, University of California, San Diego, 2004.
• 19: H. M. Wong, D. Yu, V. Bharadwaj and T. G. Robertazzi., "Data Intensive Grid Scheduling: Multiple Sources with Capacity Constraints", 15th IASTED International Conference on Parallel and Distributed Computing and Systems, Los Angeles, 2003.
• 20: M. A. Moges and T. G. Robertazzi. "Grid scheduling divisible loads from multiple sources via linear programming", IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2004), Cambridge, MA, 2004.
• 21: Sivakumar Viswanathan , Bharadwaj Veeravalli , Dantong Yu , Thomas G. Robertazzi, Design and Analysis of a Dynamic Scheduling Strategy with Resource Estimation for Large-Scale Grid Systems, Proceedings of the Fifth IEEE/ACM International Workshop on Grid Computing (GRID'04), p.163-170, November 08-08, 2004 [doi>10.1109/GRID.2004.19]
• 22: Karl Czajkowski , Ian T. Foster , Nicholas T. Karonis , Carl Kesselman , Stuart Martin , Warren Smith , Steven Tuecke, A Resource Management Architecture for Metacomputing Systems, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.62-82, March 30, 1998
• 23: Ko, K., Robertazzi, T. G., "Equal allocation scheduling for data intensive applications", IEEE Transactions on Aerospace and Electronic Systems, 40 (2), 695--705. Apr. 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Design, Management