Bid based scheduler with backfilling for a multiprocessor system

ABSTRACT

We consider a virtual computing environment that provides computational resources on demand to users with multi attribute task descriptions that include a valuation, resource (CPU) needs and a completion deadline. Achieving a high quality of service in this environment depends on finding a balance between processing high priority tasks before their deadlines expire, while maximizing resource utilization. The problem becomes more challenging in an economic setting, where the task valuation is private. We propose a bid-based server that publishes a history of the success rate table (SRT) for processed tasks. Clients use the history to optimize their bid for resources on a (single) multiprocessor server. The server schedules tasks in descending order of their bid- Highest Bid First (HBF) and backfills the schedule with smaller tasks when resources are still available. The scheduler follows a hard deadline model where tasks cannot be processed after their deadline. We propose three variations of the SRT where biding history is publicized at different granularity. Using a simulation based study, we analyze the behavior of clients' bids in respond to the SRT. We compare the best HBF variant with an efficient Earliest Deadline First (EDF) mechanism that charges a fixed price. Our results show that the HBF mechanism is able to exploit price discrimination and therefore complete the execution of more high value jobs under a heavy workload, leading to better weighted throughput. HBF can also maximize server profit and client surplus (the difference between value and the client bid) in different settings. Thus, HBF may yield solutions that benefit both the client and the server.

REFERENCES

• 1: Amazon Elastic Compute Cloud- Amazon EC2, http://aws.amazon.com/ec2.
• 2: Y. Bartal, F. Chin, M. Chrobak, S. Fung, W. Jawor, R. Lavi, J. Sgall, and T. Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. In 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS'04), pages 187--198, 2004. Lecture Notes in Computer Science vol. 2996.
• 3: R. Buyya1, D. Abramson, J. Giddy, and H. Stockinger. Economic models for resources management and scheduling in grid computation. The Journal on Concurrency and Computation: Practice and Experience 14, pages 1507--1542, 2002.
• 4: E. Chajakis and M. Guignard. Exact algorithms for the setup knapsack problem. INFOR special issue: Knapsack, packing and cutting, part I, 32:124--142, 1994. Published and sponsored by the Canadian Operational Research Society and Canadian Information Processing Society.
• 5: Su-Hui Chiang , Rajesh K. Mansharamani , Mary K. Vernon, Use of application characteristics and limited preemption for run-to-completion parallel processor scheduling policies, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.33-44, May 16-20, 1994, Nashville, Tennessee, United States
• 6: Dror G. Feitelson , Larry Rudolph, Parallel Job Scheduling: Issues and Approaches, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.1-18, April 25, 1995
• 7: Dror G. Feitelson , Larry Rudolph, Parallel Job Scheduling: Issues and Approaches, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.1-18, April 25, 1995
• 8: 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
• 9: 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
• 10: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 11: R. Graham, E. L. Lawler, and A. H. G. R. Kan. Optimization and approximaton in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287--326, 1979.
• 12: Sun N1 Grid Engine, http://www.sun.com/software/gridware.
• 13: B. Hajek. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. Proceedings of the 35th Conference in Information Sciences and Systems (CISS'01), pages 434--438, 2001.
• 14: IBM Corporation. MVS JCL User's Guide, 2003.
• 15: Barry G. Lawson , Evgenia Smirni, Multiple-Queue Backfilling Scheduling with Priorities and Reservations for Parallel Systems, Revised Papers from the 8th International Workshop on Job Scheduling Strategies for Parallel Processing, p.72-87, July 24, 2002
• 16: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 17: IBM LoadLeveler Scheduler, http://www.ibm.com/products.
• 18: Maui Scheduler Open Cluster Software, http://mauischeduler.sourceforge.net.
• 19: 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]
• 20: Portable Batch System, http://www.openpbs.org.
• 21: Ryan Porter, Mechanism design for online real-time scheduling, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988783]
• 22: E. Shmueli and D. G. Feitelson. Backfilling with lookahead to optimize the performance of parallel jobs cheduling. In D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn, editors, Job Scheduling Strategies for Parallel Processing, pages 228--251. Springer Verlag, 2003. Lecture Notes in Computer Science vol. 2862.
• 23: Patrick Sobalvarro , William E. Weihl, Demand-Based Coscheduling of Parallel Jobs on Multiprogrammed Multiprocessors, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.106-126, April 25, 1995
• 24: David Talby , Dror G. Feitelson, Supporting Priorities and Improving Utilization of the IBM SP Scheduler Using Slack-Based Backfilling, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.513, April 12-16, 1999
• 25: Douglas Thain , Todd Tannenbaum , Miron Livny, Distributed computing in practice: the Condor experience: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.2-4, p.323-356, February 2005 [doi>10.1002/cpe.v17:2/4]
• 26: Xgrid: High Performance Computing for the Rest of Us, http://developer.apple.com/hardwaredrivers/hpc/xgrid intro.html.
• 27: I. Yahav, A. Gal, and N. Larson. Bid-based approach for pricing web services. In Proceedings of the OTM Federated Conferences (OTM'06), pages 360--376, Nov 2006. Lecture Notes in Computer Science vol. 4275.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Design, Economics, Theory

Keywords:
bid-based scheduler, strategic users