A provisioning model and its comparison with best-effort for performance-cost optimization in grids

ABSTRACT

The resource availability in Grids is generally unpredictable due to the autonomous and shared nature of the Grid resources and stochastic nature of the workload resulting in a best effort quality of service. The resource providers optimize for throughput and utilization whereas the users optimize for application performance. We present a cost-based model where the providers advertise resource availability to the user community. We also present a multi-objective genetic algorithm formulation for selecting the set of resources to be provisioned that optimizes the application performance while minimizing the resource costs. We use trace-based simulations to compare the application performance and cost using the provisioned and the best effort approach with a number of artificially generated workflow-structured applications and a seismic hazard application from the earthquake science community. The provisioned approach shows promising results when the resources are under high utilization and/or the applications have significant resource requirements.

REFERENCES

• 1: Charlie Catlett, The Philosophy of TeraGrid: Building an Open, Extensible, Distributed TeraScale Facility, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.8, May 21-24, 2002
• 2: The Open Science Grid Consortium, http://www.opensciencegrid.org.
• 3: Daniel S. Katz , Joseph C. Jacob , G. Bruce Berriman , John Good , Anastasia C. Laity , Ewa Deelman , Carl Kesselman , Gurmeet Singh, A Comparison of Two Methods for Building Astronomical Image Mosaics on a Grid, Proceedings of the 2005 International Conference on Parallel Processing Workshops (ICPPW'05), p.85-94, June 14-17, 2005 [doi>10.1109/ICPPW.2005.6]
• 4: Ewa Deelman , Carl Kesselman , Gaurang Mehta , Leila Meshkat , Laura Pearlman , Kent Blackburn , Phil Ehrens , Albert Lazzarini , Roy Williams , Scott Koranda, GriPhyN and LIGO, Building a Virtual Data Grid for Gravitational Wave Scientists, Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, p.225, July 24-26, 2002
• 5: Ewa Deelman , Scott Callaghan , Edward Field , Hunter Francoeur , Robert Graves , Nitin Gupta , Vipin Gupta , Thomas H. Jordan , Carl Kesselman , Philip Maechling , John Mehringer , Gaurang Mehta , David Okaya , Karan Vahi , Li Zhao, Managing Large-Scale Workflow Execution from Resource Provisioning to Provenance Tracking: The CyberShake Example, Proceedings of the Second IEEE International Conference on e-Science and Grid Computing, p.14, December 04-06, 2006 [doi>10.1109/E-SCIENCE.2006.99]
• 6: 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]
• 7: Droegemeier, K. K., et al. Linked Environments for Atmospheric Discovery (LEAD): A CyberInfrastructure for Mesoscale Meteorology Research and Education. in 20th Conference on Interactive Information Processing Systems for Meteorology, Oceanography, and Hydrology. 2004. Seattle, WA.
• 8: Robert L. Henderson, Job Scheduling Under the Portable Batch System, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.279-294, April 25, 1995
• 9: Songnian Zhou , Xiaohu Zheng , Jingwen Wang , Pierre Delisle, Utopia: a load sharing facility for large, heterogeneous distributed computer systems, Software—Practice & Experience, v.23 n.12, p.1305-1336, Dec. 1993 [doi>10.1002/spe.4380231203]
• 10: Litzkow, M. J., M. Livny, and M. W. Mutka. Condor-a hunter of idle workstations. in Distributed Computing Systems, 1988., 8th International Conference on. 1988.
• 11: Czajkowski, K., I. Foster, and C. Kesselman, Agreement-based resource management. Proceedings of the IEEE, 2005. 93(3): p. 631--643.
• 12: Gurmeet Singh , Carl Kesselman , Ewa Deelman, Application-Level Resource Provisioning on the Grid, Proceedings of the Second IEEE International Conference on e-Science and Grid Computing, p.83, December 04-06, 2006 [doi>10.1109/E-SCIENCE.2006.25]
• 13: Carlos M. Fonseca , Peter J. Fleming, Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization, Proceedings of the 5th International Conference on Genetic Algorithms, p.416-423, June 01, 1993
• 14: Mandal, A., et al. Scheduling Strategies for Mapping Application Workflows onto the Grid. in The 14th IEEE International Symposium on High Performance Distributed Computing (HPDC-14). 2005.
• 15: 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]
• 16: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 17: Marek Wieczorek , Radu Prodan , Thomas Fahringer, Scheduling of scientific workflows in the ASKALON grid environment, ACM SIGMOD Record, v.34 n.3, September 2005 [doi>10.1145/1084805.1084816]
• 18: 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
• 19: Feitelson, D. G., Logs of real parallel workloads from production systems, in URL: http://www.cs.huji.ac.il/labs/parallel/workload.
• 20: Singh, G., C. Kesselman, and E. Deelman, A Provisioning Model and its Comparison with Best-Effort for Performance-Cost Optimization in Grids, in USC Technical Report no. 07-890. 2007.
• 21: Buyya, R. and M. Murshed, GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing. Concurrency and Computation: Practice and Experience, 2002. 14(13-15): p. 1175--1220.
• 22: Iosup, A., et al. How are Real Grids Used? The Analysis of Four Grid Traces and its Implications. in 7th IEEE/ACM International Conference on Grid Computing. 2006. Barcelona, Spain.
• 23: Sabin, G., V. Sahasrabudhe, and P. Sadayappan. Assessment and enhancement of meta-schedulers for multi-site job sharing. in High Performance Distributed Computing, 2005. HPDC-14. Proceedings. 14th IEEE International Symposium on. 2005.
• 24: Ewa Deelman , Gurmeet Singh , Mei-Hui Su , James Blythe , Yolanda Gil , Carl Kesselman , Gaurang Mehta , Karan Vahi , G. Bruce Berriman , John Good , Anastasia Laity , Joseph C. Jacob , Daniel S. Katz, Pegasus: A framework for mapping complex scientific workflows onto distributed systems, Scientific Programming, v.13 n.3, p.219-237, July 2005
• 25: Deelman, E., et al., Pegasus: Mapping Large-Scale Workflows to Distributed Resources, in Workflows for e-Science: Scientific Workflows for Grids, I. Taylor, et al., Editors. 2007, Springer.
• 26: Condor DAGMan: http://www.cs.wisc.edu/condor/dagman.
• 27: David B. Jackson , Quinn Snell , Mark J. Clement, Core Algorithms of the Maui Scheduler, Revised Papers from the 7th International Workshop on Job Scheduling Strategies for Parallel Processing, p.87-102, June 16, 2001
• 28: Marek Wieczorek , Mumtaz Siddiqui , Alex Villazon , Radu Prodan , Thomas Fahringer, Applying Advance Reservation to Increase Predictability of Workflow Execution on the Grid, Proceedings of the Second IEEE International Conference on e-Science and Grid Computing, p.82, December 04-06, 2006 [doi>10.1109/E-SCIENCE.2006.26]
• 29: Zhao, H. and R. Sakellariou. Advance Reservation Policies for Workflows. in 12th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP). 2006. Saint-Malo, France.
• 30: Mohammed H. Haji , Iain Gourlay , Karim Djemame , Peter M. Dew, A SNAP-Based Community Resource Broker Using a Three-Phase Commit Protocol: A Performance Study, The Computer Journal, v.48 n.3, p.333-346, May 2005 [doi>10.1093/comjnl/bxh088]
• 31: Foster, I., et al. A Distributed Resource Management Architecture that Supports Advance Reservations and Co-Allocation. in Proc. International Workshop on Quality of Service. 1999.
• 32: Zhang, L., et al., RSVP: a new resource ReSerVation Protocol. Network, IEEE, 1993. 7(5): p. 8--18.
• 33: 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]
• 34: Brevik, J., D. Nurmi, and R. Wolski. Predicting Bounds on Queueing Delay in Space-Shared Computing Environments. in IEEE International Symposium on Workload Characterization. 2006.
• 35: Daniel Nurmi , Anirban Mandal , John Brevik , Chuck Koelbel , Rich Wolski , Ken Kennedy, Evaluation of a workflow scheduler using integrated performance modelling and batch queue wait time prediction, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188579]
• 36: Roblitz, T., F. Schintke, and J. Wendler. Elastic Grid Reservations with User-Defined Optimization Policies. in Proceedings of the Workshop on Adaptive Grid Middleware. 2004.
• 37: T. Roblitz , A. Reinefeld, Co-reservation with the concept of virtual resources, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 1, p.398-406, May 09-12, 2005
• 38: Mumtaz Siddiqui , Alex Villazón , Thomas Fahringer, Grid capacity planning with negotiation-based advance reservation for optimized QoS, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188563]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction; Simulation

General Terms:
Algorithms, Management, Performance

Keywords:
agreement based resource management, best effort service, resource provisioning