VARQ: virtual advance reservations for queues

ABSTRACT

In high-performance computing (HPC) settings, in which multiprocessor machines are shared among users with potentially competing resource demands, processors are allocated to user workload using space sharing. Typically, users interact with a given machine by submitting their jobs to a centralized batch scheduler that implements a site-specific policy designed to maximize machine utilization while providing tolerable turn-around times. To these users, the functioning of the batch scheduler and the policies it implements are both critical operating system components since they control how each job is serviced. In practice, while most HPC systems experience good utilization levels, the amount of time experienced by individual jobs waiting to begin execution has been shown to be highly variable and difficult to predict, leading to user confusion and/or frustration.

One method for dealing with this uncertainty that has been proposed is to allow users who are willing to plan ahead to make "advanced reservations" for processor resources. To date, however, few HPC centers provide an advanced reservation capability to their general user populations since previous research indicates that diminished machine utilization will occur if and when advanced reservations are introduced.

In this work, we describe VARQ, a new method for job scheduling that provides users with probabilistic "virtual" advanced reservations using only existing best effort batch schedulers. VARQ functions as an overlay, submitting jobs that are indistinguishable from the normal workload serviced by a scheduler. We describe the statistical methods we use to implement VARQ, detail an empirical evaluation of its effectiveness in a number of HPC settings, and explore the potential future impact of VARQ should it become widely used. Without requiring HPC sites to support advanced reservations, we find that VARQ can implement a reservation capability probabilistically and that the effects of this probabilistic approach are unlikely to negatively affect resource utilization.

REFERENCES

• 1: Fran Berman , Geoffrey Fox , Anthony J. G. Hey , Tony Hey, Grid Computing: Making the Global Infrastructure a Reality, John Wiley & Sons, Inc., New York, NY, 2003
• 2: John Brevik , Daniel Nurmi , Rich Wolski, Predicting bounds on queuing delay for batch-scheduled parallel machines, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122989]
• 3: A. I. D. Bucur , D. H. J. Epema, The Performance of Processor Co-Allocation in Multicluster Systems, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.302, May 12-15, 2003
• 4: S. Clearwater and S. Kleban. Heavy-tailed distributions in supercomputer jobs. Technical Report SAND2002-2378C, Sandia National Labs, 2002.
• 5: Karl Czajkowski , Ian T. Foster , Nicholas T. Karonis , Carl Kesselman , Stuart Martin , Warren Smith , Steven Tuecke, A Resource Management Architecture for Metacomputing Systems, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.62-82, March 30, 1998
• 6: Allen B. Downey, Predicting Queue Times on Space-Sharing Parallel Computers, Proceedings of the 11th International Symposium on Parallel Processing, p.209-218, April 01-05, 1997
• 7: Allen B. Downey, Using Queue Time Predictions for Processor Allocation, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.35-57, April 05, 1997
• 8: Carsten Ernemann , Volker Hamscher , Uwe Schwiegelshohn , Ramin Yahyapour , Achim Streit, On Advantages of Grid Computing for Parallel Job Scheduling, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.39, May 21-24, 2002
• 9: C. Ernemann, V. Hamscher, and R. Yahyapour. Economic scheduling in grid computing, 2002.
• 10: D. G. Feitelson. A survey of scheduling in multiprogrammed parallel systems.
• 11: D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn. Parallel job scheduling -- a status report, 2004.
• 12: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 13: Jörn Gehring , Thomas Preiss, Scheduling a Metacomputer with Uncooperative Sub-schedulers, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.179-201, April 16, 1999
• 14: M. Harchol-Balter. The effect of heavy-tailed job size distributions on computer system design. In Proceedings of ASA-IMS Conference on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics, June 1999.
• 15: F. Heine, M. Hovestadt, O. Kao, and A. Streit. On the impact of reservations from the grid on planning-based resource management. In International Workshop on Grid Computing Security and Resource Management (GSRM 2005) at ICCS 2005, Atlanta, USA, Springer, LNCS 3516, pages 155--162.
• 16: 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
• 17: D. Lifka. The ANL/IBM SP scheduling system, volume 949. Springer-Verlag, 1995.
• 18: Maui scheduler home page -- http://www.clusterresources.com/products/maui/.
• 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: 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]
• 21: D. Nurmi, J. Brevik, and R. Wolski. Qbets: Queue bounds estimation from time series. In Proceedings of Job Scheduling Strategies for Parallel Processing (JSSPP), June 2007.
• 22: The qbets web page -- http://nws.cs.ucsb.edu/batchq.
• 23: Jeffrey Shneidman , Chaki Ng , David C. Parkes , Alvin AuYoung , Alex C. Snoeren , Amin Vahdat , Brent Chun, Why markets could (but don't currently) solve resource allocation problems in systems, Proceedings of the 10th conference on Hot Topics in Operating Systems, p.7-7, June 12-15, 2005, Santa Fe, NM
• 24: L. Smarr and C. E. Catlett. Metacomputing, 1992.
• 25: Scheduling with Advanced Reservations, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.127, May 01-05, 2000
• 26: Warren Smith , Valerie E. Taylor , Ian T. Foster, Using Run-Time Predictions to Estimate Queue Wait Times and Improve Scheduler Performance, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.202-219, April 16, 1999
• 27: Quinn Snell , Mark J. Clement , David B. Jackson , Chad Gregory, The Performance Impact of Advance Reservation Meta-scheduling, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.137-153, May 01, 2000
• 28: The teragrid user portal -- http://portal.teragrid.org.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

General Terms:
Experimentation, Measurement, Performance

Keywords:
advance reservation, batch queue scheduling, super-computing