Precise and realistic utility functions for user-centric performance analysis of schedulers

ABSTRACT

Utility functions can be used to represent the value users attach to job completion as a function of turnaround time. Most previous scheduling research used simple synthetic representations of utility, with the simplicity being due to the fact that real user preferences are difficult to obtain, and perhaps concern that arbitrarily complex utility functions could in turn make the scheduling problem intractable. In this work, we advocate a flexible representation of utility functions that can indeed be arbitrarily complex. We show that a genetic algorithm heuristic can improve global utility by analyzing these functions, and does so tractably. Since our previous work showed that users indeed have and can articulate complicated utility functions, the result here is relevant. We then provide a means to augment existing workload traces with realistic utility functions for the purpose of enabling realistic scheduling simulations.

REFERENCES

• 1: AuYoung, Alvin, Laura Grit, Janet Wiener and John Wilkes. "Service contracts and aggregate utility functions." 15th IEEE International Symposium on High Performance Distributed Computing, Paris, France, June 2006.
• 2: Brevik, John, Daniel Nurmi and Rich Wolski. "Predicting Bounds on Queueing Delay in Space-Shared Computing Environments." IEEE International Symposium on Workload Characterization, October, 2006.
• 3: Brent Nee Chun , David E. Culler, Market-based cluster resource management, University of California, Berkeley, 2001
• 4: B. N. Chun , P. Buonadonna , A. AuYoung , Chaki Ng , D. C. Parkes , J. Shneidman , A. C. Snoeren , A. Vahdat, Mirage: a microeconomic resource allocation system for sensornet testbeds, Proceedings of the 2nd IEEE workshop on Embedded Networked Sensors, p.19-28, April 30-May 01, 2005
• 5: Brent N. Chun , David E. Culler, User-Centric Performance Analysis of Market-Based Cluster Batch Schedulers, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.30, May 21-24, 2002
• 6: Steve J. Chapin , Walfredo Cirne , Dror G. Feitelson , James Patton Jones , Scott T. Leutenegger , Uwe Schwiegelshohn , Warren Smith , David Talby, Benchmarks and Standards for the Evaluation of Parallel Job Schedulers, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.67-90, April 16, 1999
• 7: Earheart, Travis and Nancy Wilkins-Diehr of SDSC provided the original workload to the Parallel Workloads Archive {6, 8} of Dror Feitelson et al. The specific Parallel Workoads Archive file version we used is SDSC-BLUE-2000-2.1-cln.swf.
• 8: Feitelson, Dror, et al. Parallel Workloads Archive and Standard Workload Format. http://www.cs.huji.ac.il/labs/parallel/workload/.
• 9: Dror G. Feitelson , Larry Rudolph, Towards Convergence in Job Schedulers for Parallel Supercomputers, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.1-26, April 16, 1996
• 10: 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
• 11: David E. Irwin , Laura E. Grit , Jeffrey S. Chase, Balancing Risk and Reward in a Market-Based Task Service, Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing, p.160-169, June 04-06, 2004 [doi>10.1109/HPDC.2004.5]
• 12: Lai, K. B. A. Huberman and L. Fine. "Tycoon: A Distributed Market-based Resource Allocation System. Technical Report." cs.DC/0404013, April 2004. Available at http://arxiv.org/abs/cs.DC/0404013
• 13: Cynthia Bailey Lee , Allan Snavely, On the User-Scheduler Dialogue: Studies of User-Provided Runtime Estimates and Utility Functions, International Journal of High Performance Computing Applications, v.20 n.4, p.495-506, November 2006 [doi>10.1177/1094342006068414]
• 14: Lee, Cynthia Bailey, Yael Schwartzman, Jennifer Hardy and Allan Snavely "Are user runtime estimates inherently inaccurate?" In 10th Job Scheduling Strategies for Parallel Processing, June 2004.
• 15: Ahuva W. Mu'alem , Dror G. Feitelson, Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling, IEEE Transactions on Parallel and Distributed Systems, v.12 n.6, p.529-543, June 2001 [doi>10.1109/71.932708]
• 16: Norvig, Peter. Python code, available at http://aima.cs.berkeley.edu/python/readme.html. Used according to terms of license. © 1998-2002.
• 17: Pfeiffer, Wayne. Personal Interview. San Diego Supercomputer Center, at the University of California, San Diego. La Jolla, CA. April 9, 2004.
• 18: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 19: Ion Stoica , Hussein M. Abdel-Wahab , Alex Pothen, A Microeconomic Scheduler for Parallel Computers, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.200-218, April 25, 1995
• 20: David Talby , Dror G. Feitelson , Adi Raveh, Comparing Logs and Models of Parallel Workloads Using the Co-plot Method, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.43-66, April 16, 1999
• 21: Tsafrir, Dan and Dror G. Feitelson. "Instability in parallel job scheduling simulation: the role of workload flurries." IEEE International Parallel and Distributed Processing Symposium. Rhodes Island, Greece, April 2006.
• 22: Tsafrir, Dan and Dror G. Feitelson. "The dynamics of backfilling: solving the mystery of why increased inaccuracy may help." IEEE International Symposium on Workload Characterization. October 2006.
• 23: Carl A. Waldspurger , Tad Hogg , Bernardo A. Huberman , Jeffrey O. Kephart , W. Scott Stornetta, Spawn: A Distributed Computational Economy, IEEE Transactions on Software Engineering, v.18 n.2, p.103-117, February 1992 [doi>10.1109/32.121753]
• 24: Weinberg, Jon and Allan Snavely. "Symbiotic Space-Sharing on SDSC's DataStar System." Proceedings of the 12th Workshop on Job Scheduling Strategies for Parallel Processing, E. Frachtenberg and U. Schwiegelshohn, eds. 2006.
• 25: Rich Wolski , James S. Plank , John Brevik , Todd Bryan, Analyzing Market-Based Resource Allocation Strategies for the Computational Grid, International Journal of High Performance Computing Applications, v.15 n.3, p.258-281, August 2001 [doi>10.1177/109434200101500305]
• 26: Dmitry Zotkin , Peter J. Keleher, Job-Length Estimation and Performance in Backfilling Schedulers, Proceedings of the 8th IEEE International Symposium on High Performance Distributed Computing, p.39, August 03-06, 1999

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Economics, Human Factors, Management, Measurement, Performance

Keywords:
genetic algorithms, scheduling, utility functions