Evaluation of a workflow scheduler using integrated performance modelling and batch queue wait time prediction

ABSTRACT

Large-scale distributed systems offer computational power at unprecedented levels. In the past, HPC users typically had access to relatively few individual supercomputers and, in general, would assign a one-to-one mapping of applications to machines. Modern HPC users have simultaneous access to a large number of individual machines and are beginning to make use of all of them for single-application execution cycles. One method that application developers have devised in order to take advantage of such systems is to organize an entire application execution cycle as a workflow. The scheduling of such workflows has been the topic of a great deal of research in the past few years and, although very sophisticated algorithms have been devised, a very specific aspect of these distributed systems, namely that most supercomputing resources employ batch queue scheduling software, has heretofore been omitted from consideration, presumably because it is difficult to model accurately. In this work, we augment an existing workflow scheduler through the introduction of methods which make accurate predictions of both the performance of the application on specific hardware, and the amount of time individual workflow tasks will spend waiting in batch queues. Our results show that although a workflow scheduler alone may choose correct task placement based on data locality or network connectivity, this benefit is often compromised by the fact that most jobs submitted to current systems must wait in overcommited batch queues for a significant portion of time. However, incorporating the enhancements we describe improves workflow execution time in settings where batch queues impose significant delays on constituent workflow tasks.

REFERENCES

• 1: J. Blythe , S. Jain , E. Deelman , Y. Gil , K. Vahi , A. Mandal , K. Kennedy, Task scheduling strategies for workflow-based applications in grids, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.759-767, May 09-12, 2005
• 2: John Brevik , Daniel Nurmi , Rich Wolski, Predicting bounds on queuing delay for batch-scheduled parallel machines, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122989]
• 3: Deelman, E., Blythe, J., Gil, Y., Kesselman, C., Mehta, G., Patil, S., Su, M.-H., Vahi, K., And Livny, M. 2004. Pegasus: Mapping scientific workflows onto the grid. In Proceedings of the 2nd European Across Grids Conference.
• 4: Allen B. Downey, Predicting Queue Times on Space-Sharing Parallel Computers, Proceedings of the 11th International Symposium on Parallel Processing, p.209-218, April 01-05, 1997
• 5: Allen B. Downey, Using Queue Time Predictions for Processor Allocation, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.35-57, April 05, 1997
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Kerbyson, D. J., Alme, H. J., Hoisie, A., Petrini, F., Wasserman, H. J., And Gittings, M. 2001. Predictive performance and scalability modeling of a large-scale application.
• 8: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 9: Lifka, D., Henderson, M., And Rayl, K. 1995. Users guide to the argonne SP scheduling system. Tech. Rep. TM-201, Argonne National Laboratory, Mathematics and Computer Science Division, May.
• 10: Ludtke, S., Baldwin, P., And Chiu, W. 1999. Eman: Semiautomated software for high-resolution single-particle reconstructions. J. Struct. Biol. 128, 82--97.
• 11: Mandal, A., Kennedy, K., Koelbel, C., Marin, G., Mellor-Crummey, J., Liu, B., and Johnsson, L. 2005. Scheduling Strategies for Mapping Application Workflows onto the Grid. In 14-th IEEE Symposium on High Performance Distributed Computing (HPDC14), 125--134.
• 12: Gabriel Marin , John Mellor-Crummey, Cross-architecture performance predictions for scientific applications using parameterized models, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 13: NSF TeraGrid Project. http://www.teragrid.org/.
• 14: Hyunok Oh , Soonhoi Ha, A Static Scheduling Heuristic for Heterogeneous Processors, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.573-577, August 26-29, 1996
• 15: Performance Prophet: A Performance Modeling and Prediction Tool for Parallel and Distributed Programs, Proceedings of the 2005 International Conference on Parallel Processing Workshops (ICPPW'05), p.509-516, June 14-17, 2005 [doi>10.1109/ICPPW.2005.72]
• 16: G. C. Sih , E. A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.175-187, February 1993 [doi>10.1109/71.207593]
• 17: Warren Smith , Valerie E. Taylor , Ian T. Foster, Using Run-Time Predictions to Estimate Queue Wait Times and Improve Scheduler Performance, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.202-219, April 16, 1999
• 18: David Sundaram-Stukel , Mary K. Vernon, Predictive analysis of a wavefront application using LogGP, ACM SIGPLAN Notices, v.34 n.8, p.141-150, Aug. 1999
• 19: Valerie Taylor , Xingfu Wu , Rick Stevens, Prophesy: an infrastructure for performance analysis and modeling of parallel and grid applications, ACM SIGMETRICS Performance Evaluation Review, v.30 n.4, March 2003 [doi>10.1145/773056.773060]
• 20: Haluk Topcuouglu , Salim Hariri , Min-you Wu, Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.260-274, March 2002 [doi>10.1109/71.993206]
• 21: Tracy D. Braun , Howard Jay Siegel , Noah Beck , Lasislau L. Bölöni , Muthucumara Maheswaran , Albert I. Reuther , James P. Robertson , Mitchell D. Theys , Bin Yao , Debra Hensgen , Richard F. Freund, A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of Parallel and Distributed Computing, v.61 n.6, p.810-837, June 2001 [doi>10.1006/jpdc.2000.1714]
• 22: 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]
• 23: Rich Wolski , Neil Spring , Jim Hayes, Predicting the CPU Availability of Time-Shared Unix Systems on the Computational Grid, Proceedings of the The Eighth IEEE International Symposium on High Performance Distributed Computing, p.12, August 03-06, 1999

INDEX TERMS

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

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

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

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.1 Office Automation
          Subjects: Workflow management

General Terms:
Algorithms, Design, Management