Multiple-queue backfilling scheduling with priorities and reservations for parallel systems

ABSTRACT

We describe a new, non-FCFS policy to schedule parallel jobs on systems that may be part of a computational grid. Our algorithm continuously monitors the system (i.e., intensity of incoming jobs and variability of their resource demands) and continuously adapts its scheduling parameters to sudden workload fluctuations. The proposed policy is based on backfilling which permits job rearrangement in the waiting queue. By exploiting otherwise idle processors, this rearrangement reduces fragmentation of system resources, thereby providing higher system utilization. We propose to maintain multiple job queues that effectively separate jobs according to their projected execution time. Our policy supports different job priority classes as well as 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 scheduling approaches.

REFERENCES

• 1: Bode B., Halstead D.H., Kendall R., Lei Z., "The Portable Batch Scheduler and the Maui Scheduler on Linux Clusters", in Proceedings of the 4th Annual Linux Showcase and Conference, Atlanta, Georgia, October 2000.
• 2: 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
• 3: Feitelson D.G., "A survey of scheduling in multiprogrammed parallel systems", Technical Report RC 19790, IBM Research Division, October 1994.
• 4: IBM LoadLeveler, http://www.ibm.com/products/.
• 5: Peter J. Keleher , Dmitry Zotkin , Dejan Perkovic, Attacking the bottlenecks of backfilling schedulers, Cluster Computing, v.3 n.4, p.245-254, 2000 [doi>10.1023/A:1019044623636]
• 6: Barry G. Lawson , Evgenia Smirni , Daniela Puiu, Self-Adapting Backfilling Scheduling for Parallel Systems, Proceedings of the 2002 International Conference on Parallel Processing (ICPP'02), p.583, August 18-21, 2002
• 7: 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]
• 8: Maui Scheduler Open Cluster Software, http://mauischeduler.sourceforge.net/.
• 9: Parallel Workload Archive, http://www.cs.huji.ac.il/labs/parallel/workload/.
• 10: Dejan Perkovic , Peter J. Keleher, Randomization, speculation, and adaptation in batch schedulers, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.7-es, November 04-10, 2000, Dallas, Texas, United States
• 11: Portable Batch System, http://www.openpbs.org/.
• 12: Alma Riska , Wei Sun , Evgenia Smirni , Gianfranco Ciardo, ADAPTLOAD: Effective Balancing in Custered Web Servers Under Transient Load Conditions, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.104, July 02-05, 2002
• 13: E. Rosti , E. Smirni , L. W. Dowdy , G. Serazzi , B. M. Carlson, Robust partitioning policies of multiprocessor systems, Performance Evaluation, v.19 n.2-3, p.141-165, March 1994 [doi>10.1016/0166-5316(94)90037-X]
• 14: Bianca Schroeder , Mor Harchol-Balter, Evaluation of Task Assignment Policies for Supercomputing Servers: The Case for Load Unbalancing and Fairness, Proceedings of the Ninth IEEE International Symposium on High Performance Distributed Computing (HPDC'00), p.211, August 01-04, 2000
• 15: 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

INDEX TERMS

Keywords:
backfilling schedulers, batch schedulers, computational grids, parallel systems, performance analysis