Scheduling in MPP

Model & definitions

• job scheduling: which job is allocated next
• allocation: assignment of job to set of nodes
• gang scheduling: coordinated time-sharing between parallel jobs

Examples of algorithms

• FCFS: first come first serve
• Scan-up: scanning the waiting queue for an optimal candidate

• buddy: hierachical free lists
• gray code: use of coding theory, better recognition
• first fit: searching for fits
• non-contiguous: request may be scatted

• matrix: 2 dimensional space
• continous: linear
• undivided: linear and contiguous

Results

• Krueger: to overcome fragmentation scheduling is more important than allocation
• non-contiguity: overcomes fragmentation, introduces contention

Tools

References

• M. Chen and K. G. Shin. Processor Allocation in an n-CUBE Multiprocessor using Gray Codes. IEEE Transactions on Computers, December 1987
• K. Li and K.-H. Cheng. A Two-dimensional Buddy System for Dynamic Resource Allocation in a Partitionable Mesh Connected System. Journal of Parallel and Distributed Computing, 1991
• P. Chuang and N. Tzeng. An Efficient Submesh Allocation Strategy for Mesh Computer Systems. Proceedings of International Conference on Distributed Computer Systems, 1991
• Y. Zhu. Efficient Processor Allocation Strategies for Mesh-connected Parallel Computers. Journal of Parallel and Distributed Computing, 1992
• M. Livingston and Q. F. Stout. Parallel Allocation Algorithms for Hypercubes and Meshes. Proceedings of the 4th Conference on Hypercube Concurrent Computers and Applications, 1989
• W. Liu, V. Lo, K. Windisch, and B. Nitzberg. Non-Contiguous Processor Allocation Algorithms for Distributed Memory Multicomputers. Proceedings of Supercomputing 1994
• 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. Proceedings of the 2nd Workshop on Job Scheduling Strategies for Parallel Processing, IPPS '96
• D. G. Feitelson. A Survey of Scheduling in Multiprogrammed Parallel Systems. IBM Research Division Research Report RC 19790, 1994
• J. K. Ousterhout. Scheduling Techniques for Concurrent Systems Proceedings of 3rd International Conference on Distributed Computing Systems, October 1982
• P. Krueger, T. Lai, and V. A. Dixit-Radiya. Job Scheduling is More Important Than Processor Allocation for Hypercube Computers. IEEE Transactions on Parallel and Distributed Systems, May 1994