A decoupled scheduling approach for the GrADS program development environment

ABSTRACT

Program development environments are instrumental in providing users with easy and efficient access to parallel computing platforms. While a number of such environments have been widely accepted and used for traditional HPC systems, there are currently no widely used environments for Grid programming. The goal of the Grid Application Development Software (GrADS) project is to develop a coordinated set of tools, libraries and run-time execution facilities for Grid program development.In this paper, we describe a Grid scheduler component that is integrated as part of the GrADS software system. Traditionally, application-level schedulers (e.g. AppLeS) have been tightly integrated with the application itself and were not easily applied to other applications. Our design is generic: we decouple the scheduler core (the search procedure) from the application-specific (e.g. application performance models) and platform-specific (e.g. collection of resource information) components used by the search procedure. We provide experimental validation of our approach for two representative regular, iterative parallel programs in a variety of real-world Grid testbeds. Our scheduler consistently outperforms static and user-driven scheduling methods.

REFERENCES

• 1: High Performance Parametric Modeling with Nimrod/G: Killer Application for the Global Grid?, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.520, May 01-05, 2000
• 2: BARRETT, R., BERRY, M. W., CHAN, T. F., DEMMEL, J., DONATO, J., DONGARRA, J., EIJKHOUT, V., POZO, R., ROMINE, C., AND VAN DER VORST, H. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM, Philadelphia, PA, 1994.
• 3: Francine Berman, High-performance schedulers, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 4: Francine Berman , Andrew Chien , Keith Cooper , Jack Dongarra , Ian Foster , Dennis Gannon , Lennart Johnsson , Ken Kennedy , Carl Kesselman , John Mellor-Crumme , Dan Reed , Linda Torczon , Rich Wolski, The GrADS Project: Software Support for High-Level Grid Application Development, International Journal of High Performance Computing Applications, v.15 n.4, p.327-344, November 2001 [doi>10.1177/109434200101500401]
• 5: Francine D. Berman , Rich Wolski , Silvia Figueira , Jennifer Schopf , Gary Shao, Application-level scheduling on distributed heterogeneous networks, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.39-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369109]
• 6: Henri Casanova , Graziano Obertelli , Francine Berman , Rich Wolski, The AppLeS parameter sweep template: user-level middleware for the grid, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.60-es, November 04-10, 2000, Dallas, Texas, United States
• 7: Steven Fitzgerald, Grid Information Services for Distributed Resource Sharing, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10'01), p.181, August 07-09, 2001
• 8: DAIL, H. A modular framework for adaptive scheduling in grid application development environments. Master's thesis, University of California at San Diego, March 2002. Available as UCSD Tech. Report CS2002--0698.
• 9: Holly Dail , Graziano Obertelli , Francine Berman , Rich Wolski , Andrew Grimshaw, Application-Aware Scheduling of a Magnetohydrodynamics Application in the Legion Metasystem, Proceedings of the 9th Heterogeneous Computing Workshop, p.216, May 01-01, 2000
• 10: Gary William Flake, The computational beauty of nature, MIT Press, Cambridge, MA, 1998
• 11: Ian Foster , Jonathan Geisler , William Gropp , Nicholas Karonis , Ewing Lusk , George Thiruvathukal , Steven Tuecke, Wide-area implementation of the message passing interface, Parallel Computing, v.24 n.12-13, p.1735-1749, Nov. 1998 [doi>10.1016/S0167-8191(98)00075-1]
• 12: I. Foster , C. Kesselman, The Globus Project: A Status Report, Proceedings of the Seventh Heterogeneous Computing Workshop, p.4, March 30-30, 1998
• 13: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 14: FOX, G. C., WILLIAMS, R. D., AND MESSINA, P. C. Parallel Computing Works! Morgan Kaufmann, San Francisco, CA, 1994. Available at http://www.npac.syr.edu/pcw.
• 15: Jörn Gehring , Thomas Preiss, Scheduling a Metacomputer with Uncooperative Sub-schedulers, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.179-201, April 16, 1999
• 16: Andrew Grimshaw , Adam Ferrari , Frederick Knabe , Marty Humphrey, Wide-Area Computing: Resource Sharing on a Large Scale, Computer, v.32 n.5, p.29-37, May 1999 [doi>10.1109/2.762790]
• 17: Volker Hamscher , Uwe Schwiegelshohn , Achim Streit , Ramin Yahyapour, Evaluation of Job-Scheduling Strategies for Grid Computing, Proceedings of the First IEEE/ACM International Workshop on Grid Computing, p.191-202, December 17, 2000
• 18: KENNEDY, K., BROOM, B., COOPER, K., DONGARRA, J., FOWLER, R., GANNON, D., JOHNSSON, L., MELLOR-CRUMMEY, J., AND TORCZON, L. Telescoping languages: A strategy for automatic generation of scientific problem-solving systems from annotated libraries. Journal of Parallel and Distributed Computing 61, 12 (2001), 1803--1826.
• 19: KENNEDY, K., MAZINA, M., AYDT, R., MENDES, C., DAIL, H., AND SIEVERT, O. GrADSoft and its Application Manager: An execution mechanism for Grid applications. GrADS Project Working Document V, available at http://hipersoft.cs.rice.edu/grads/publications_reports.htm, Oct 2001.
• 20: Yu-Kwong Kwok , Ishfaq Ahmad, Benchmarking and comparison of the task graph scheduling algorithms, Journal of Parallel and Distributed Computing, v.59 n.3, p.381-422, Dec. 1999 [doi>10.1006/jpdc.1999.1578]
• 21: LITZKOW, M. J., LIVNY, M., AND MUTKA, M. W. Condor--a hunter of idle workstations. In Proceedings of the 8th International Conference on Distributed Computing Systems (June 1988).
• 22: Chuang Liu , Lingyun Yang , Ian Foster , Dave Angulo, Design and Evaluation of a Resource Selection Framework for Grid Applications, Proceedings of the 11 th IEEE International Symposium on High Performance Distributed Computing HPDC-11 20002 (HPDC'02), p.63, July 24-26, 2002
• 23: lp_solve FTP site at ftp://ftp.es.ele.tue.nl/pub/lp_solve.
• 24: MILLER, N., AND STEENKISTE, P. Collecting network status information for network-aware applications. In INFO-COM'00 (March 2000).
• 25: Dragan Mirković , Rishad Mahasoom , Lennart Johnsson, An adaptive software library for fast Fourier transforms, Proceedings of the 14th international conference on Supercomputing, p.215-224, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335252]
• 26: Antoine Petitet , Susan Blackford , Jack Dongarra , Brett Ellis , Graham Fagg , Kenneth Roche , Sathish Vadhiyar, Numerical Libraries and the Grid, International Journal of High Performance Computing Applications, v.15 n.4, p.359-374, November 2001 [doi>10.1177/109434200101500403]
• 27: R. Raman , M. Livny , M. Solomon, Matchmaking: Distributed Resource Management for High Throughput Computing, Proceedings of the The Seventh IEEE International Symposium on High Performance Distributed Computing, p.140, July 28-31, 1998
• 28: SHAO, G., BERMAN, F., AND WOLSKI, R. Using Effective Network Views to promote distributed application performance. In Proceedings of the 1999 International Conference on Parallel and Distributed Processing Techniques and Applications (1999).
• 29: Gary Shao , Francine Berman , Rich Wolski, Master/Slave Computing on the Grid, Proceedings of the 9th Heterogeneous Computing Workshop, p.3, May 01-01, 2000
• 30: Shava Smallen , Walfredo Cirne , Francine Berman , Steve Young , Mark Ellisman , Jaime Frey , Rich Wolski , Mei-Hui Su , Carl Kesselman, Combining Workstations and Supercomputers to Support Grid Applications: The Parallel Tomography Experience, Proceedings of the 9th Heterogeneous Computing Workshop, p.241, May 01-01, 2000
• 31: Alan Su , Francine Berman , Richard Wolski , Michelle Mills Strout, Using Apples to Schedule Simple SARA on the Computational Grid, International Journal of High Performance Computing Applications, v.13 n.3, p.253-262, August 1999 [doi>10.1177/109434209901300308]
• 32: Vijay Subramani , Rajkumar Kettimuthu , Srividya Srinivasan , P. Sadayappan, Distributed Job Scheduling on Computational Grids Using Multiple Simultaneous Requests, Proceedings of the 11 th IEEE International Symposium on High Performance Distributed Computing HPDC-11 20002 (HPDC'02), p.359, July 24-26, 2002
• 33: VADHIYAR, S., May 2002. Personal Communication.
• 34: Sathish S. Vadhiyar , Jack J. Dongarra, A Metascheduler For The Grid, Proceedings of the 11 th IEEE International Symposium on High Performance Distributed Computing HPDC-11 20002 (HPDC'02), p.343, July 24-26, 2002
• 35: WEISSMAN, J. Prophet: Automated scheduling of SPMD programs in workstation networks. Concurrency: Practice and Experience 11, 6 (1999).
• 36: Jon B. Weissman , Xin Zhao, Scheduling parallel applications in distributed networks, Cluster Computing, v.1 n.1, p.109-118, 1998 [doi>10.1023/A:1019073113216]
• 37: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

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

General Terms:
Algorithms, Design, Experimentation