[go: up one dir, main page]

Skip to main content
Log in

New Grid Scheduling and Rescheduling Methods in the GrADS Project

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

The goal of the Grid Application Development Software (GrADS) Project is to provide programming tools and an execution environment to ease program development for the Grid. This paper presents recent extensions to the GrADS software framework: a new approach to scheduling workflow computations, applied to a 3-D image reconstruction application; a simple stop/migrate/restart approach to rescheduling Grid applications, applied to a QR factorization benchmark; and a process-swapping approach to rescheduling, applied to an N-body simulation. Experiments validating these methods were carried out on both the GrADS MacroGrid (a small but functional Grid) and the MicroGrid (a controlled emulation of the Grid).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. I. Foster and C. Kesselman (eds.), The Grid: Blueprint for a New Computing Infrastructure, 2nd Ed., Morgan Kaufmann (2003)

  2. K. Kennedy, M. Mazina, J. Mellor-Crummey, K. Cooper, L Torczon, F. Berman, A. Chien, H. Dail, O. Sievert, D. Angulo, I Foster, D. Gannon, S. L. Johnsson, C. Kesselman, R. Aydt, D. Reed, J. Dongarra, S. Vadhiyar, and R. Wolski, Towards a Framework for Preparing and Executing Adaptive Grid Programs, Proceedings of NSF Next Generation Systems Program Workshop (International Parallel and Distributed Processing Symposium), Fort Lauderdale, Florida (April 2002)

  3. R.L. Ribler H. Simitci D.A. Reed (September 2001) ArticleTitleThe Autopilot Performance-directed Adaptive Control System Future Generation Computer Systems. 18 IssueID1 175–18kk7

    Google Scholar 

  4. Vraalsen F., Aydt R.A., Mendes C.L., Reed D.A. Performance Contracts: Predicting and Monitoring Grid Application Behavior, Lecture Notes in Computer Science, Vol. 2242, pp. 154–165, Springer Verlag (November 2001)

  5. H. Song, X. Liu, D. Jakobsen, R. Bhagwan, X. Zhang, K. Taura, and A. Chien, The MicroGrid: A Scientific Tool for Modeling Computational Grids, Proceedings of SC2000 (November 2000)

  6. O. Sievert and H. Casanova, Policies for Swapping MPI Processes, Proceedings of HPDC-12, the Symposium on High Performance and Distributed Computing (June 2003)

  7. Barish B., Weiss R. (1999). Ligo and detection of gravitational waves. Physics Today. 52(10)

  8. S. Hastings, T. Kurc, S. Langella, U. Catalyurek, T. Pan, and J. Saltz, Image Processing on the Grid: A Toolkit or Building Grid-enabled Image Processing Applications, 3rd International Symposium on Cluster Computing and the Grid (2003)

  9. K. Taura and A. Chien, A Heuristic Algorithm for Mapping Communicating Tasks on Heterogeneous Resources, Heterogeneous Computing Workshop (May 2000)

  10. S. Vadhiyar and J. Dongarra, A Metascheduler for the Grid, Proceedings of the High Performance Distributed Computing Conference (July 2002)

  11. R. Wolski, J. Plank, J. Brevik, and T. Bryan, G-commerce: Market Formulations Controlling Resource Allocation on the Computational Grid, Proceedings of 2001 International Parallel and Distributed Processing Symposium (1PDPS) (March 2001)

  12. Condor Team, Condor Version 6.4.7 Manual, //www.cs.wisc.edu/condor/ manual/v6.4/

  13. S. Fitzgerald, I. Foster, C. Kesselman, G. von Laszewski, W Smith, and S. Tuecke, A Directory Service for Configuring High-Performance Distributed Computations, Proceedings of the 6th IEEE Symposium on High-Performance Distributed Computing, pp 365–375 (August 1997), URL papers/fitzgerald–hpdc97-mds.pdf

  14. R. Wolski N.T. Spring J. Hayes (1999) ArticleTitleThe network weather service: a distributed resource performance forecasting service for metacomputing Future Generation Computer Systems. 15 IssueID5–6 757–768

    Google Scholar 

  15. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of Np-Completeness, MIT Press (1979)

  16. H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman, Heuristics for Scheduling Parameter Sweep applications in Grid environments, 9th Heterogeneous Computing workshop (HCW’2000) (2000)

  17. D. Tracy Braun et al. (2001) ArticleTitleA Comparision of eleven Static Heuristics for Maping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems Journal of Parallel and Distributed Computing. 61 810–837

    Google Scholar 

  18. G. Marin, Semi-Automatic Synthesis of Parameterized Performance Models for Scientific Programs, Master’s thesis, Department of Computer Science, Rice University (April 2003)

  19. S. Ludtke P. Baldwin W. Chiu (1999) ArticleTitleEMAN: Semiautomated Software for High- Resolution Single-Particle Reconstructions J. Struct. Biol. 128 82–97

    Google Scholar 

  20. S. Vadhiyar J. Dongarra (June 2003) ArticleTitleSRS A Framework for Developing Malleable and Migratable Parallel Applications for Distributed Systems Parallel Processing Letters. 13 IssueID2 291–312

    Google Scholar 

  21. J.S. Plank, M. Beck, W. Elwasif, T. Moore, M. Swany, and R Wolski, The Internet Backplane Protocol: Storage in the Network, NetStore99: The Network Storage Symposium (1999)

  22. L.S. Blackford, J. Choi, A. Cleary, E. D’Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammerling, G. Henry, A. Petitet, K Stanley, D. Walker, and R.C. Whaley, ScaLAPACK User’s Guide. (1997)

  23. S. Vadhiyar and J. Dongarra, A Performance Oriented Migration Framework for the Grid, IEEE Computing Clusters and the Grid (CCGrid, http://www.ccgrid.org) (May 12–15 2003)

  24. O. Sievert and H. Casanova, A Simple MPI Process Swapping Architecture for Iterative Applications, The International Journal of High Performance Computing Applications (2004), to appear

  25. X. Liu and A. Chien, Traffic-based Load Balance for Scalable Network Emulation, Proceedings of SC2003 (November 2003)

  26. H. Xia, H. Dail, H. Casanova, F. Berman, and A. Chien, Evaluating the GrADS Scheduler in Diverse Grid Environments Using the MicroGrid (May 2003), submitted for publication

  27. A. Petitet, S. Blackford, J. Dongarra, B. Ellis, G. Fagg, K Roche, and S. Vadhiyar, Numerical Libraries and the Grid, Proceedings of SC’01 (November 2001)

  28. M. Ripeanu, A. Iamnitchi, and I. Foster, Cactus Application: Performance Predictions in a Grid Environment, Proceedings of European Conference on Parallel Computing (EuroPar)2001 (August 2001)

  29. W. Chrabakh and R. Wolski, GrADSAT: A Parallel SAT Solver for the Grid, Technical Report CS-2003-05, University of California, Santa Barbara (2003), available from http://www.cs.ucsb.edu/research/trcs/index.shtml

  30. H. Dail, A Modular Framework for Adaptive Scheduling in Grid Application Development Environments, Master’s thesis, University of California, San Diego, Department of Computer Science and Engineering (Mardh 2002), available as UCSD Technical Report CS2002-0698

  31. A. Mandal, Mapping HPF onto the Grid, Technical report TR03-417, Department of Computer Science, Rice University, Houston (November 2002), URL http://www.cs. rice edu/anirban/MSthesis.ps.gz

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to K. Kennedy.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Berman, F., Casanova, H., Chien, A. et al. New Grid Scheduling and Rescheduling Methods in the GrADS Project. Int J Parallel Prog 33, 209–229 (2005). https://doi.org/10.1007/s10766-005-3584-4

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10766-005-3584-4

Keywords

Navigation