Performance characteristics of gang scheduling in multiprogrammed environments

ABSTRACT

Gang scheduling provides both space-slicing and time-slicing of computer resources for parallel programs. Each thread of execution from a parallel job is concurrently scheduled on an independent processor in order to achieve an optimal level of program performance. Time-slicing of parallel jobs provides for better overall system responsiveness and utilization than otherwise possible. Lawrence Livermore National Laboratory has deployed three generations of its gang scheduler on a variety of computing platforms. Results indicate the potential benefits of this technology to parallel processing are no less significant than time-sharing was in the 1960's.

REFERENCES

• 1: Cray Research Inc. Cray T3D System Architecture Overview. Order number HR-04033, Sept 1993.
• 2: B. C. Curtis and B. E. Kelly, Dedicated Computing on a YMP/C916. Cray User Group, Sep 95.
• 3: Andrea C. Dusseau , Remzi H. Arpaci , David E. Culler, Effective distributed scheduling of parallel workloads, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.25-36, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 4: D. G. Feitelson, A Survey of Scheduling in Multiprogrammed Parallel Systems. IBM Research Report RC19790(87657), Feb 1995.
• 5: Dror G. Feitelson , Morris A. Jette, Improved Utilization and Responsiveness with Gang Scheduling, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.238-261, April 05, 1997
• 6: B. Gorda and R. Wolski, Timesharing massively parallel machines. International Conference on Parallel Processing, volume II, Aug 1995, pp. 214-217.
• 7: B. C. Gorda and E. D. Brooks III, Gang Scheduling a Parallel Machine. Technical Report UCRL-JC-107020, Lawrence Livermore National Laboratory, Dec 1991.
• 8: M. Jette and J. Reynolds, Centralized User Banking and User Administration on UNICOS. Cray User Group, Mar 1994.
• 9: M. Jette, D. Storch and E. Yim, Gang Scheduler - Timesharing the Cray T3D". Cray User Group, Mar 1996, pp. 247-252.
• 10: Keqin Li , Kam-Hoi Cheng, A two-dimensional buddy systems for dynamic resource allocation in a partitionable mesh connected system, Journal of Parallel and Distributed Computing, v.12 n.1, p.79-83, May 1991 [doi>10.1016/0743-7315(91)90032-5]
• 11: Cathy McCann , Raj Vaswani , John Zahorjan, A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.2, p.146-178, May 1993 [doi>10.1145/151244.151246]
• 12: Emilia Rosti , Evgenia Smirni , Giuseppe Serazzi , Lawrence W. Dowdy, Analysis of Non-Work-Conserving Processor Partitioning Policies, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.165-181, April 25, 1995
• 13: Patrick Sobalvarro , William E. Weihl, Demand-Based Coscheduling of Parallel Jobs on Multiprogrammed Multiprocessors, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.106-126, April 25, 1995
• 14: P. G. Sobalvarro, S. Pakin, W. E. Weihl, and A. A. Chien, Dynamic Coscheduling on Workstation Clusters. Symposium on Operating Systems Design and Implementation, Oct 1996.
• 15: Charles Severance , Richard J. Enbody, Comparing Gang Scheduling with Dynamic Space Sharing on Symmetric Multiprocessors Using Automatic Self-Allocating Threads (ASAT), Proceedings of the 11th International Symposium on Parallel Processing, p.288, April 01-05, 1997
• 16: A. Tucker , A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.159-166, November 1989
• 17: R. Wood, Distributed Production Control System. Technical Report UCRL-TB-122372, Lawrence Livermore National Laboratory, Nov 1995.
• 18: Q. Yang , H. Wang, A New Graph Approach to Minimizing Processor Fragmentation in Hypercube Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.4 n.10, p.1165-1171, October 1993 [doi>10.1109/71.246077]

INDEX TERMS

Keywords:
gang scheduling, multiprogramming, parallel system, scheduling, space-slicing, time-slicing