Abstract
We describe a new, non-FCFS policy to schedule parallel jobs on systems that may be part of a computationalgrid . Our algorithm continuously monitors the system (i.e., the intensity of incoming jobs and variability of their resource demands), and adapts its scheduling parameters according to workload fluctuations. The proposed policy is based on backfilling, which reduces resource fragmentation by executing jobs in an order different than their arrivalwit hout delaying certain previously submitted jobs. We maintain multiple job queues that effectively separate jobs according to their projected execution time. Our policy supports different job priorities and job reservations, making it appropriate for scheduling jobs on parallel systems that are part of a computational grid. Detailed performance comparisons via simulation using traces from the Parallel Workload Archive indicate that the proposed policy consistently outperforms traditional backfilling.
This work was partially supported by the National Science Foundation under grants EIA-9977030, EIA-9974992, CCR-0098278, and ACI-0090221.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Crockett, Tom: Private Communication, June 2002. tom@compsci.wm.edu, http://www.compsci.wm.edu/?tom/. 76
Feitelson, D.G.: A Survey of Scheduling in Multiprogrammed Parallel Systems. Technical Report RC 19790, IBM Research Division, October 1994. 73
Keleher, P., Zotkin, D., and Perkovic, D.: Attacking the Bottlenecks in Backfilling Schedulers. Cluster Computing: The Journal of Networks, Software Tools and Applications. 3(4) (2000) 245–254. 73, 74
Lawson, B.G., Smirni, E., and Puiu D.: Self-Adapting Backfilling Scheduling for Parallel Systems. Proceedings of the 2002 International Conference on Parallel Processing (ICPP 2002). August 2002, 583–592. 73, 74, 75
Mu’alem, A.W. and Feitelson, D. G.: Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBMSP2 with Backfilling. IEEE Transactions on Parallel and Distributed Systems. 12(6) (2001) 529–543. 73, 74
Perkovic, D. and Keleher, P.: Randomization, Speculation, and Adaptation in Batch Schedulers. Proceedings of Supercomputing 2000 (SC 2000). November 2000. 73, 74
Talby, D. and Feitelson, D.G.: Supporting Priorities and Improving Utilization of the IBM SP2 Scheduler Using Slack-Based Backfilling. Proceedings of the 13th International Parallel Processing Symposium. April 1999, 513–517. 73
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lawson, B.G., Smirni, E. (2002). Multiple-Queue Backfilling Scheduling with Priorities and Reservations for Parallel Systems. In: Feitelson, D.G., Rudolph, L., Schwiegelshohn, U. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 2002. Lecture Notes in Computer Science, vol 2537. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36180-4_5
Download citation
DOI: https://doi.org/10.1007/3-540-36180-4_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00172-0
Online ISBN: 978-3-540-36180-0
eBook Packages: Springer Book Archive