Abstract
Jobs that do not require all processors in the system can be packed together for gang scheduling. We examine accounting traces from several parallel computers to show that indeed many jobs have small sizes and can be packed together. We then formulate a number of such packing algorithms, and evaluate their effectiveness using simulations based on our workload study. The results are that two algorithms are the best: either perform the mapping based on a buddy system of processors, or use migration to re-map the jobs more tightly whenever a job arrives or terminates. Other approaches, such as mapping to the least loaded PEs, proved to be counterproductive. The buddy system approach depends on the capability to gang-schedule jobs in multiple slots, if there is space. The migration algorithm is more robust, but is expected to suffer greatly due to the overhead of the migration itself. In either case fragmentation is not an issue, and utilization may top 90% with sufficiently high loads.
Preview
Unable to display preview. Download preview PDF.
References
A. Barak and A. Shiloh, “A distributed load-balancing policy for a multicomputer”. Software — Pract. & Exp. 15(9), pp. 901–913, Sep 1985.
J. M. Barton and N. Bitar, “A scalable multi-discipline, multiple-processor scheduling framework for IRIX”. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 45–69, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.
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 Conf. Measurement & Modeling of Comput. Syst., pp. 33–44, May 1994.
E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson, “Approximation algorithms for bin-packing — an updated survey”. In Algorithm Design for Computer Systems Design, G. Ausiello, M. Lucertini, and P. Serafini (eds.), pp. 49–106, Springer-Verlag, 1984.
E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson, “Bin packing with divisible item sizes”. J. Complex. 3(4), pp. 406–428, Dec 1987.
F. Douglis and J. Ousterhout, “Process migration in the Sprite operating system”. In 7th Intl. Conf. Distributed Comput. Syst., pp. 18–25, Sep 1987.
D. G. Feitelson, A Survey of Scheduling in Multiprogrammed Parallel Systems. Research Report RC 19790 (87657), IBM T. J. Watson Research Center, Oct 1994.
D. G. Feitelson and B. Nitzberg, “Job characteristics of a production parallel scientific workload on the NASA Ames iPSC/860”. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 337–360, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.
D. G. Feitelson and L. Rudolph, “Distributed hierarchical control for parallel processing”. Computer 23(5), pp. 65–77, May 1990.
D. G. Feitelson and L. Rudolph, “Evaluation of design choices for gang scheduling using distributed hierarchical control”. J. Parallel & Distributed Comput., 1996. to appear.
D. G. Feitelson and L. Rudolph, “Parallel job scheduling: issues and approaches”. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 1–18, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.
D. G. Feitelson and L. Rudolph, “Wasted resources in gang scheduling”. In 5th Jerusalem Conf. Information Technology, pp. 127–136, IEEE Computer Society Press, Oct 1990.
B. Gorda and R. Wolski, “Time sharing massively parallel machines”. In Intl. Conf. Parallel Processing, Aug 1995.
B. C. Gorda and E. D. Brooks III, Gang Scheduling a Parallel Machine. Technical Report UCRL-JC-107020, Lawrence Livermore National Laboratory, Dec 1991.
S. Hotovy, “Workload evolution on the Cornell Theory Center IBM SP2”. In Job Scheduling Strategies for Parallel Processing II, D. G. Feitelson and L. Rudolph (eds.), Springer-Verlag, 1996. Lecture Notes in Computer Science.
Intel Corp., iPSC/860 Multi-User Accounting, Control, and Scheduling Utilities Manual. Order number 312261-002, May 1992.
Intel Supercomputer Systems Division, Paragon User's Guide. Order number 312489-003, Jun 1994.
K. C. Knowlton, “A fast storage allocator”. Comm. ACM 8(10), pp. 623–625, Oct 1965.
P. Krueger, T-H. Lai, and V. A. Radiya, “Processor allocation vs. job scheduling on hypercube computers”. In 11th Intl. Conf. Distributed Comput. Syst., pp. 394–401, May 1991.
S. T. Leutenegger and M. K. Vernon, “The performance of multiprogrammed multiprocessor scheduling policies”. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 226–236, May 1990.
D. Lifka, “The ANL/IBM SP scheduling system”. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), pp. 295–303, Springer-Verlag, 1995. Lecture Notes in Computer Science Vol. 949.
M. H. MacDougall, Simulating Computer Systems: Techniques and Tools. MIT Press, 1987.
S. Majumdar, D. L. Eager, and R. B. Bunt, “Scheduling in multiprogrammed parallel systems”. In SIGMETRICS Conf. Measurement & Modeling of Comput. Syst., pp. 104–113, May 1988.
J. K. Ousterhout, “Scheduling techniques for concurrent systems”. In 3rd Intl. Conf. Distributed Comput. Syst., pp. 22–30, Oct 1982.
J. L. Peterson and T. A. Norman, “Buddy systems”. Comm. ACM 20(6), pp. 421–431, Jun 1977.
D. L. Russell, “Internal fragmentation in a class of buddy systems”. SIAM J. Comput. 6(4), pp. 607–621, Dec 1977.
T. Suzuoka, J. Subhlok, and T. Gross, Evaluating Job Scheduling Techniques for Highly Parallel Computers. Technical Report CMU-CS-95-149, School of Computer Science, Carnegie Mellon University, 1995.
Thinking Machines Corp., Connection Machine CM-5 Technical Summary. Nov 1992.
M. Wan, R. Moore, G. Kremenek, and K. Steube, “A batch scheduler for the Intel Paragon MPP system with a non-contiguous node allocation algorithm”. In Job Scheduling Strategies for Parallel Processing II, D. G. Feitelson and L. Rudolph (eds.), Springer-Verlag, 1996. Lecture Notes in Computer Science.
G. K. Zipf, Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feitelson, D.G. (1996). Packing schemes for gang scheduling. In: Feitelson, D.G., Rudolph, L. (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 1996. Lecture Notes in Computer Science, vol 1162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0022289
Download citation
DOI: https://doi.org/10.1007/BFb0022289
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61864-5
Online ISBN: 978-3-540-70710-3
eBook Packages: Springer Book Archive