Trace-based evaluation of job runtime and queue wait time predictions in grids

ABSTRACT

Large-scale distributed computing systems such as grids are serving a growing number of scientists. These environments bring about not only the advantages of an economy of scale, but also the challenges of resource and workload heterogeneity. A consequence of these two forms of heterogeneity is that job runtimes and queue wait times are highly variable, which generally reduces system performance and makes grids difficult to use by the common scientist. Predicting job runtimes and queue wait times have been widely studied for parallel environments. However, there is no detailed investigation on how the proposed prediction methods perform in grids, whose resource structure and workload characteristics are very different from those in parallel systems. In this paper, we assess the performance and benefit of predicting job runtimes and queue wait times in grids based on traces gathered from various research and production grid environments. First, we evaluate the performance of simple yet widely used time series prediction methods and the effect of applying them to different types of job classes (e.g., all jobs submitted by single users or to single sites). Then, we investigate the performance of two kinds of queue wait time prediction methods for grids. Last, we investigate whether prediction-based grid-level scheduling policies can have better performance than policies that do not use predictions.

REFERENCES

• 1: Francine Berman , Richard Wolski , Henri Casanova , Walfredo Cirne , Holly Dail , Marcio Faerman , Silvia Figueira , Jim Hayes , Graziano Obertelli , Jennifer Schopf , Gary Shao , Shava Smallen , Neil Spring , Alan Su , Dmitrii Zagorodnov, Adaptive Computing on the Grid Using AppLeS, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.369-382, April 2003 [doi>10.1109/TPDS.2003.1195409]
• 2: J. Brevik , D. Nurmi , R. Wolski, Automatic methods for predicting machine availability in desktop Grid and peer-to-peer systems, Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, p.190-199, April 19-22, 2004
• 3: 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]
• 4: P. J. Brockwell and R. A. Davis. Introduction to Time Series and Forecasting. Springer, March 2002.
• 5: 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
• 6: M. Dobber, G. Koole, and R. V. D. Mei. Dynamic load balancing for a grid application. In HiPC, pages 342--352, 2004.
• 7: M. Dobber , G. Koole , R. van der Mei, Dynamic load balancing experiments in a grid, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.1063-1070, May 09-12, 2005
• 8: Menno Dobber , Rob van der Mei , Ger Koole, A prediction method for job runtimes on shared processors: Survey, statistical analysis and new avenues, Performance Evaluation, v.64 n.7-8, p.755-781, August, 2007 [doi>10.1016/j.peva.2007.01.001]
• 9: 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
• 10: 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
• 11: G. Elliott, T. J. Rothenberg, and J. H. Stock. Efficient tests for an autoregressive unit root. Econometrica, 64(4):813--836, 1996.
• 12: Dror G. Feitelson , Larry Rudolph , Uwe Schwiegelshohn , Kenneth C. Sevcik , Parkson Wong, Theory and Practice in Parallel Job Scheduling, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.1-34, April 05, 1997
• 13: A. Weil, Utilization and Predictability in Scheduling the IBM SP2 with Backfilling, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.542, March 30-April 03, 1998
• 14: Alexandru Iosup , Catalin Dumitrescu , Dick Epema , Hui Li , Lex Wolters, How are Real Grids Used? The Analysis of Four Grid Traces and Its Implications, Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, p.262-269, September 28-29, 2006 [doi>10.1109/ICGRID.2006.311024]
• 15: A. Iosup, D. Epema, C. Franke, A. Papaspyrou, L. Schley, B. Song, and R. Yahyapour. On grid performance evaluation using synthetic workloads. In JSSPP, pages 232--255, 2006.
• 16: A. Iosup, M. Jan, O. Sonmez, and D. Epema. The Characteristics and Performance of Groups of Jobs in Grids. In Euro-Par, pages 382--393, 2007.
• 17: Alexandru Iosup , Hui Li , Mathieu Jan , Shanny Anoep , Catalin Dumitrescu , Lex Wolters , Dick H. J. Epema, The Grid Workloads Archive, Future Generation Computer Systems, v.24 n.7, p.672-686, July, 2008 [doi>10.1016/j.future.2008.02.003]
• 18: Alexandru Iosup , Ozan Sonmez , Shanny Anoep , Dick Epema, The performance of bags-of-tasks in large-scale distributed systems, Proceedings of the 17th international symposium on High performance distributed computing, June 23-27, 2008, Boston, MA, USA [doi>10.1145/1383422.1383435]
• 19: Alexandru Iosup , Ozan Sonmez , Dick Epema, DGSim: Comparing Grid Resource Management Architectures through Trace-Based Simulation, Proceedings of the 14th international Euro-Par conference on Parallel Processing, August 26-29, 2008, Las Palmas de Gran Canaria, Spain [doi>10.1007/978-3-540-85451-7_3]
• 20: Michael A. Iverson , Fusun Ozguner , Gregory J. Follen, Run-Time Statistical Estimation of Task Execution Times for Heterogeneous Distributed Computing, Proceedings of the 5th IEEE International Symposium on High Performance Distributed Computing, p.263, August 06-09, 1996
• 21: Woochul Kang , Andrew Grimshaw, Failure Prediction in Computational Grids, Proceedings of the 40th Annual Simulation Symposium, p.275-282, March 26-28, 2007 [doi>10.1109/ANSS.2007.21]
• 22: Nirav H. Kapadia , José A. B. Fortes , Carla E. Brodley, Predictive Application-Performance Modeling in a Computational Grid Environment, Proceedings of the 8th IEEE International Symposium on High Performance Distributed Computing, p.6, August 03-06, 1999
• 23: B.-D. Lee and J. M. Schopf. Run-Time Prediction of Parallel Applications on Shared Environments. In Cluster, volume 0, pages 487--582, 2003.
• 24: Uri Lublin , Dror G. Feitelson, The workload on parallel supercomputers: modeling the characteristics of rigid jobs, Journal of Parallel and Distributed Computing, v.63 n.11, p.1105-1122, November 2003 [doi>10.1016/S0743-7315(03)00108-4]
• 25: Muthucumaru Maheswaran , Shoukat Ali , Howard Jay Siegel , Debra Hensgen , Richard F. Freund, Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, Proceedings of the Eighth Heterogeneous Computing Workshop, p.30, April 12-12, 1999
• 26: F. Nadeem, R. Prodan, T. Fahringer, and A. Iosup. A Framework For Resource Availability Characterization And Online Prediction in the Grids. In CoreGRID Integration Workshop, pages 209--224, 2008.
• 27: Daniel Charles Nurmi , John Brevik , Rich Wolski, QBETS: queue bounds estimation from time series, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 28: Daniel Pease , Arif Ghafoor , Ishfaq Ahmad , David L. Andrews , Kamal Foudil-Bey , Thomas E. Karpinski , Mohammad A. Mikki , Mohamed Zerrouki, PAWS: A Performance Evaluation Tool for Parallel Computing Systems, Computer, v.24 n.1, p.18-29, January 1991 [doi>10.1109/2.67190]
• 29: Kam Hong Shum, Adaptive Distributed Computing through Competition, Proceedings of the 3rd International Conference on Configurable Distributed Systems, p.220, May 06-08, 1996
• 30: Warren Smith , Ian T. Foster , Valerie E. Taylor, Predicting Application Run Times Using Historical Information, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.122-142, March 30, 1998
• 31: 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
• 32: SPECCPU Team. SPEC CPU2006. Standard Performance. http://www.spec.org/cpu2006/.
• 33: Henry Stark , John W. Woods, Probability, random processes, and estimation theory for engineers, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 34: The Parallel Workloads Archive Team. The parallel workloads archive logs, Jan. 2009. {Online}. Available: http://www.cs.huji.ac.il/labs/parallel/workload/logs.html.
• 35: Dan Tsafrir , Yoav Etsion , Dror G. Feitelson, Backfilling Using System-Generated Predictions Rather than User Runtime Estimates, IEEE Transactions on Parallel and Distributed Systems, v.18 n.6, p.789-803, June 2007 [doi>10.1109/TPDS.2007.70606]
• 36: Rich Wolski, Experiences with predicting resource performance on-line in computational grid settings, ACM SIGMETRICS Performance Evaluation Review, v.30 n.4, March 2003 [doi>10.1145/773056.773064]
• 37: Jaehyung Yang , Ishfaq Ahmad , Arif Ghafoor, Estimation of Execution times on Heterogeneous Supercomputer Architectures, Proceedings of the 1993 International Conference on Parallel Processing, p.219-226, August 16-20, 1993 [doi>10.1109/ICPP.1993.80]
• 38: Yuanyuan Zhang , Wei Sun , Yasushi Inoguchi, Predict task running time in grid environments based on CPU load predictions, Future Generation Computer Systems, v.24 n.6, p.489-497, June, 2008 [doi>10.1016/j.future.2007.07.003]

INDEX TERMS

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

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

General Terms:
Experimentation, Performance

Keywords:
grid scheduling, performance evaluation, predictions, time series prediction methods, trace-based simulation