Efficient auction-based grid reservations using dynamic programming

ABSTRACT

Auction mechanisms have been proposed as a means to efficiently and fairly schedule jobs in high-performance computing environments. The Generalized Vickrey Auction has long been known to produce efficient allocations while exposing users to truth-revealing incentives, but the algorithms used to compute its payments can be computationally intractable. In this paper we present a novel implementation of the Generalized Vickrey Auction that uses dynamic programming to schedule jobs and compute payments in pseudo-polynomial time. Additionally, we have built a version of the PBS scheduler that uses this algorithm to schedule jobs, and in this paper we present the results of our tests using this scheduler.

REFERENCES

• 1: A. Mutz, R. Wolski, and J. Brevik, "Eliciting honest value information in a batch-queue environment," in Proceedings of 8th IEEE/ACM International Conference on Grid Computing, 2007.
• 2: Chaki Ng , Philip Buonadonna , Brent N. Chun , Alex C. Snoeren , Amin Vahdat, Addressing strategic behavior in a deployed microeconomic resource allocator, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080195]
• 3: M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason, "Auction protocols for decentralized scheduling," Games and Economic Behavior, vol. 35, no. 1--2, pp. 271--303, 2001. {Online}. Available: http://citeseer.ist.psu.edu/383290.html
• 4: B. Schnizler, D. Neumann, D. Veit, and C. Weinhardt, "A multiattribute combinatorial exchange for trading grid resources," in Proceedings of the Research Symposium on Emerging Electronic, 2005.
• 5: Brent N. Chun , David E. Culler, Market-based Proportional Resource Sharing for Clusters, University of California at Berkeley, Berkeley, CA, 2000
• 6: K. Lai, B. A. Huberman, and L. Fine, "Tycoon: A distributed market-based resource allocation system," 2004.
• 7: 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
• 8: 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]
• 9: 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
• 10: 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]
• 11: Anubhav Das , Daniel Grosu, Combinatorial Auction-Based Protocols for Resource Allocation in Grids, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 13, p.251.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.140]
• 12: K. Bubendorfer, K. Chard, P. Komisarczuk, and A. Desai, "Fine grained resource reservation and management in grid economies," in Proceedings of The 2005 International Conference on Grid Computing and Applications, 2005.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming; Scheduling

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance