Abstract
Although the current practice in parallel job scheduling requires jobs to specify a particular number of requested processors, most parallel jobs are moldable, i.e. the required number of processors is flexible. This paper addresses the issue of effective selection of processor partition size for moldable jobs. The proposed scheduling strategy is shown to provide significant benefits over a rigid scheduling model and is also considerably better than a previously proposed approach to moldable job scheduling.
Supported in part by a grant from Sandia National Laboratories.
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
S. V. Anastasiadis and K. C. Sevcik. Parallel Application Scheduling on Networks of Workstations. Journal of Parallel and Distributed Computing, 43(2): 109–124, 1997. 174
O. Arndt, B. Freisleben, T. Kielmann, and F. Thilo. A Comparative Study of Online Scheduling Algorithms for Networks of Workstations. Cluster Computing, 3(2):95–112, 2000. 174
S. H. Chiang, R. K. Mansharamani, and M. K. Vernon. Use of Application Characteristics and Limited Preemption for Run-to-Completion Parallel Processor Scheduling Policies. In SIGMETRICS, pages 33–44, 1994. 174
S. H. Chiang and M. K. Vernon. Production Job Scheduling for Parallel Shared Memory Systems. In Proceedings of the International Parallel and Distributed Processing Symp, 2001. 174
W. Cirne. Using Moldability to Improve the Performance of Supercomputer Jobs. Ph.D. Thesis. Computer Science and Engineering, University of California San Diego, 2001. 174, 176
W. Cirne. When the Herd is Smart: The Emergent Behavior of SA. In IEEE Trans. Par. Distr. Systems, 2002. 174, 176
W. Cirne and F. Berman. Adaptive Selection of Partition Size for Supercomputer Requests. In Workshop on Job Scheduling Strategies for Parallel Processing, pages 187–208, 2000. 174, 176
A. B. Downey. A Model For Speedup of Parallel Programs. Technical Report CSD-97-933. University of California at Berkeley, 1997. 176
D. G. Feitelson. Logs of real parallel workloads from production systems. http://www.cs.huji.ac.il/labs/parallel/workload/logs.html. 175, 176
D. G. Feitelson, L. Rudolph, U. Schwiegelshohn, K. C. Sevcik, and P. Wong. Theory and Practice in Parallel Job Scheduling. In Workshop on Job Scheduling Strategies for Parallel Processing, pages 1–34. 174, 176
D. Jackson, Q. Snell, and M. J. Clement. Core Algorithms of the Maui Scheduler. In Wkshp. on Job Sched. Strategies for Parallel Processing, pages 87–102, 2001. 175
P. J. Keleher, D. Zotkin, and D. Perkovic. Attacking the Bottlenecks of Backfilling Schedulers. Cluster Computing, 3(4):245–254, 2000. 174
D. Lifka. The ANL/IBM SP Scheduling System. In Workshop on Job Scheduling Strategies for Parallel Processing, pages 295–303, 1995. 175
A. W. Mu’alem and D. G. Feitelson. Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling. In IEEE Trans. Par. Distr. Systems, volume 12, pages 529–543, 2001. 174, 175
E. Rosti, E. Smirni, L. W. Dowdy, G. Serazzi, and B. M. Carlson. Robust Partitioning Policies of Multiprocessor Systems. Performance Evaluation, 19(2–3):141–165, 1994. 174
S. Setia and S. Tripathi. A Comparative Analysis of Static Processor Partitioning Policies for Parallel Computers. In Proc. of the Intl. Wkshp. on Modeling and Simulation of Computer and Telecomm. Syst. (MASCOTS), pages 283–286, 1993. 174
K. C. Sevcik. Application Scheduling and Processor Allocation in Multiprogrammed Parallel Processing Systems. Performance Evaluation, 19(2–3):107–140, 1994. 174
J. Skovira, W. Chan, H. Zhou, and D. Lifka. The EASY-LoadLeveler API Project. In Wkshp. on Job Sched. Strategies for Parallel Processing, pages 41–47, 1996. 175
S. Srinivasan, R. Kettimuthu, V. Subramani, and P. Sadayappan. Characterization of Backfilling Strategies for Parallel Job Scheduling. In Proceedings of the ICPP2002 Workshops, pages 514–519, 2002. 180
S. Srinivasan, R. Kettimuthu, V. Subramani, and P. Sadayappan. Selective Reservation Strategies for Backfill Job Scheduling. In Proceedings of the 8th Workshop on Job Scheduling Strategies for Parallel Processing, 2002. 180
A. Streit. On Job Scheduling for HPC-Clusters and the dynP Scheduler. In Proc. Intl. Conf. High Perf. Comp., pages 58–67, 2001. 174
D. Talby and D. Feitelson. Supporting Priorities and Improving Utilization of the IBM SP Scheduler Using Slack-Based Backfilling. In Proceedings of the 13th International Parallel Processing Symposium, 1999. 175
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
Srinivasan, S., Subramani, V., Kettimuthu, R., Holenarsipur, P., Sadayappan, P. (2002). Effective Selection of Partition Sizes for Moldable Scheduling of Parallel Jobs. In: Sahni, S., Prasanna, V.K., Shukla, U. (eds) High Performance Computing — HiPC 2002. HiPC 2002. Lecture Notes in Computer Science, vol 2552. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36265-7_17
Download citation
DOI: https://doi.org/10.1007/3-540-36265-7_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00303-8
Online ISBN: 978-3-540-36265-4
eBook Packages: Springer Book Archive