Student Contribution

SC Conference - Activity Details

Efficient Auction-based Grid Reservations using Dynamic Programming

Andrew Mutz  (University of California, Santa Barbara)
Rich Wolski  (University of California, Santa Barbara)
Papers Session
Grid Resource Management
Tuesday,  02:30PM - 03:00PM
Room Ballroom G
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.
The full paper can be found in the IEEE Xplore Digital Library and ACM Digital Library
   IEEE Computer Society  /  ACM     2 0   Y E A R S   -   U N L E A S H I N G   T H E   P O W E R   O F   H P C