Abstract
An important issue in multiprogrammed multiprocessor systems is the scheduling of parallel jobs. Consequently, there has been a considerable amount of analytic research in this area recently. A frequent criticism, however, is that proposed disciplines that are studied analytically are rarely ever implemented and even more rarely incorporated into commercial scheduling software. In this paper, we seek to bridge this gap by describing how at least one commercial scheduling system, namely Platform Computing's Load Sharing Facility, can be extended to support a wide variety of new scheduling disciplines.
We then describe the design and implementation of a number of multiprocessor scheduling disciplines, each differing considerably in terms of the type of preemption that is assumed to be available and in terms of the flexibility allowed in allocating processors. In evaluating the performance of these disciplines, we find that preemption can significantly reduce overall response times, but that the performance of disciplines that must commit to allocations when a job is first activated can be significantly affected by transient loads.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Timothy B. Brecht and Kaushik Guha. Using parallel program characteristics in dynamic processor allocation policies. Performance Evaluation, 27&28:519–539, 1996.
Su-Hui Chiang, Rajesh K. Mansharamani, and Mary K. Vernon. Use of application characteristics and limited preemption for run-to-completion parallel processor scheduling policies. In Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems, pages 33–44, 1994.
Dror G. Feitelson and Bill Nitzberg. Job characteristics of a production parallel scientific workload on the NASA Ames iPSC/860. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 949, pages 337–360. Springer-Verlag, 1995.
Dror G. Feitelson and Larry Rudolph. Gang scheduling performance benefits for fine-grain synchronization. Journal of Parallel and Distributed Computing, 16:306–318, 1992.
Richard Gibbons. A historical application profiler for use by parallel schedulers. Master's thesis, Department of Computer Science, University of Toronto, 1996.
Richard Gibbons. A historical application profiler for use by parallel schedulers. In Dror G. Feitelson and Larry Rudolph, editors, Proceedings of the Third Workshop on Job Scheduling Strategies for Parallel Processing, 1997. To appear.
Dipak Ghosal, Guiseppe Serazzi, and Satish K. Tripathi. The processor working set and its use in scheduling multiprocessor systems. IEEE Transactions on Software Engineering, 17(5):443–453, May 1991.
Anoop Gupta, Andrew Tucker, and Luis Stevens. Making effective use of shared-memory multiprocessors: The process control approach. Technical Report CSL-TR-91-47 5A, Computer Systems Laboratory, Stanford University, July 1991.
Robert L. Henderson. Job scheduling under the portable batch system. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 949, pages 279–294. Springer-Verlag, 1995.
Steven Hotovy. Private communication, November 1996.
Steven Hotovy. Workload evolution on the Cornell Theory Center IBM SP2. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 1162, pages 27–40. Springer-Verlag, 1996.
David A. Lifka. The ANL/IBM SP scheduling system. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 949, pages 295–303. Springer-Verlag, 1995.
Silvano Martello and Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations. Wiley & Sons, 1990.
Cathy McCann, Raj Vaswani, and John Zahorjan. A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessors. ACM Transactions on Computer Systems, 11(2):146–178, May 1993.
Cathy McCann and John Zahorjan. Processor allocation policies for message-passing parallel computers. In Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pages 19–32, 1994.
Cathy McCann and John Zahorjan. Scheduling memory constrained jobs on distributed memory parallel computers. In Proceedings of the 1995 ACM SIGMETRICS Joint International Conference on Measurement and Modelling of Computer Systems, pages 208–219, 1995.
Vijay K. Naik, Sanjeev K. Setia, and Mark S. Squillante. Performance analysis of job scheduling policies in parallel supercomputing environments. In Proceedings of Supercomputing '93, pages 824–833, 1993.
Thu D. Nguyen, Raj Vaswani, and John Zahorjan. Using runtime measured workload characteristics in parallel processor scheduling. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 1162, pages 175–199. Springer-Verlag, 1996.
John K. Ousterhout. Scheduling techniques for concurrent systems. In Proceedings of the Ad International Conference on Distributed Computing (ICDCS), pages 22–30, October 1982.
Eric W. Parsons.Using Knowledge of Job Characteristics in Multiprogrammed Multiprocessor Scheduling. PhD thesis, Department of Computer Science, University of Toronto, 1997.
Jim Pruyne and Miron Livny. Managing checkpoints for parallel programs. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 1162, pages 140–154. Springer-Verlag, 1996.
Eric W. Parsons and Kenneth C. Sevcik. Multiprocessor scheduling for high-variability service time distributions. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 949, pages 127–145. Springer-Verlag, 1995.
Eric W. Parsons and Kenneth C. Sevcik. Benefits of speedup knowledge in memory-constrained multiprocessor scheduling. Performance Evaluation, 27&28:253–272, 1996.
Eric W. Parsons and Kenneth C. Sevcik. Coordinated allocation of memory and processors in multiprocessors. In Proceedings of the 1996 ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems, pages 57–67, 1996.
E. Rosti, E. Smirni, L. W. Dowdy, G. Serazzi, and B. M. Carlson. Robust partitioning policies of multiprocessor systems. Performance Evaluation, 19:141–165, 1994.
Joseph Skovira, Waiman Chan, Honbo Zhou, and David Lifka. The EASYLoadLeveler API project. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 1162, pages 41–47. Springer-Verlag, 1996.
Sanjeev K. Setia. The interaction between memory allocations and adaptive partitioning in message-passing multiprocessors. In Dror G. Feitelson and Larry Rudolph, editors, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 949, pages 146–164. Springer-Verlag, 1995.
Kenneth C. Sevcik. Characterizations of parallelism in applications and their use in scheduling. In Proceedings of the 1989 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 171–180, May 1989.
K. C. Sevcik. Application scheduling and processor allocation in multiprogrammed parallel processing systems. Performance Evaluation, 19:107–140, 1994.
Sanjeev Setia and Satish Tripathi. A comparative analysis of static processor partitioning policies for parallel computers. In Proceedings of the International Workshop on Modeling and Simulation of Computer and Telecommunication Systems (MASCOTS), pages 283–286, January 1993.
Andrew Tucker and Anoop Gupta. Process control and scheduling issues for multiprogrammed shared-memory multiprocessors. In Proceedings of the 12th ACM Symposium on Operating Systems Principles, pages 159-166, 1989.
Michael Wan, Regan Moore, George Kremenek, and Ken Steube. A batch scheduler for the Intel Paragon with a non-contiguous node allocation algorithm. In Dror G. Feitelson and Larry Rudolph, editors, Job Schedul ing Strategies for Parallel Processing, Lecture Notes in Computer Science Vol. 1162, pages 48–64. Springer-Verlag, 1996.
John Zahorjan and Cathy McCann. Processor scheduling in shared memory multiprocessors. In Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems, pages 214–225, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Parsons, E.W., Sevcik, K.C. (1997). Implementing multiprocessor scheduling disciplines. In: Feitelson, D.G., Rudolph, L. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 1997. Lecture Notes in Computer Science, vol 1291. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63574-2_21
Download citation
DOI: https://doi.org/10.1007/3-540-63574-2_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63574-1
Online ISBN: 978-3-540-69599-8
eBook Packages: Springer Book Archive