Modeling and analysis of dynamic coscheduling in parallel and distributed environments

ABSTRACT

Scheduling in large-scale parallel systems has been and continues to be an important and challenging research problem. Several key factors, including the increasing use of off-the-shelf clusters of workstations to build such parallel systems, have resulted in the emergence of a new class of scheduling strategies, broadly referred to as dynamic coscheduling. Unfortunately, the size of both the design and performance spaces of these emerging scheduling strategies is quite large, due in part to the numerous dynamic interactions among the different components of the parallel computing environment as well as the wide range of applications and systems that can comprise the parallel environment. This in turn makes it difficult to fully explore the benefits and limitations of the various proposed dynamic coscheduling approaches for large-scale systems solely with the use of simulation and/or experimentation.To gain a better understanding of the fundamental properties of different dynamic coscheduling methods, we formulate a general mathematical model of this class of scheduling strategies within a unified framework that allows us to investigate a wide range of parallel environments. We derive a matrix-analytic analysis based on a stochastic decomposition and a fixed-point iteration. A large number of numerical experiments are performed in part to examine the accuracy of our approach. These numerical results are in excellent agreement with detailed simulation results. Our mathematical model and analysis is then used to explore several fundamental design and performance tradeoffs associated with the class of dynamic coscheduling policies across a broad spectrum of parallel computing environments.

REFERENCES

• 1: Cosimo Anglano, A Comparative Evaluation of Implicit Coscheduling Strategies for Networks of Workstations, Proceedings of the Ninth IEEE International Symposium on High Performance Distributed Computing (HPDC'00), p.221, August 01-04, 2000
• 2: Andrea C. Arpaci-Dusseau , David E. Culler , Alan M. Mainwaring, Scheduling with implicit information in distributed systems, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.233-243, June 22-26, 1998, Madison, Wisconsin, United States
• 3: S. Asmussen. Phase-type distributions and related point processes: Fitting and recent advances. Matrix-Analytic Methods in Stochastic Models, S. R. Chakravarthy & A. S. Alfa (eds.), 137-149, 1997.
• 4: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• 5: 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
• 6: D. G. Feitelson. A survey of scheduling in multiprogrammed parallel systems, Research Report RC 19790(87657), IBM Research Division, 1994.
• 7: Dror G. Feitelson , Bill Nitzberg, Job Characteristics of a Production Parallel Scientivic Workload on the NASA Ames iPSC/860, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.337-360, April 25, 1995
• 8: Anja Feldmann , Ward Whitt, Fitting mixtures of exponentials to long-tail distributions to analyze network performance models, Performance Evaluation, v.31 n.3-4, p.245-279, Jan. 1998 [doi>10.1016/S0166-5316(97)00003-5]
• 9: D. Gaver, P. Jacobs, G. Latouche. Finite birth-and-death models in randomly changing environments. Advances in Applied Probability, 16:715-731, 1984.
• 10: A. Horvath, M. Telek. Approximating heavy tailed behaviour with phase type distributions. Advances in Algorithmic Methods for Stochastic Models, G. Latouche & P. Taylor (eds.), 191-214, 2000.
• 11: Steven Hotovy, Workload Evolution on the Cornell Theory Center IBM SP2, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.27-40, April 16, 1996
• 12: Nayeem Islam , Andreas L. Prodromidis , Mark S. Squillante, Dynamic Partitioning in Different Distributed-Memory Environments, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.244-270, April 16, 1996
• 13: G. Latouche, V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM, Philadelphia, 1999.
• 14: J. D. C. Little. A proof of the queuing formula L = λW. Operations Research, 9:383-387, 1961.
• 15: Shailabh Nagar , Ajit Banerjee , Anand Sivasubramaniam , Chita R. Das, A closer look at coscheduling approaches for a network of workstations, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.96-105, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305630]
• 16: M. F. Neuts. Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. The Johns Hopkins University Press, 1981.
• 17: B. F. Nielsen. Modelling long-range dependent and heavy-tailed phenomena by matrix analytic methods. Advances in Algorithmic Methods for Stochastic Models, G. Latouche & P. Taylor (eds.), 265-278, 2000.
• 18: J. K. Ousterhout. Scheduling techniques for concurrent systems. Proceedings of International Conference on Distributed Computing Systems, 22-30, 1982.
• 19: Patrick Gregory Sobalvarro , William E. Weihl, Demand-based coscheduling of parallel jobs on multiprogrammed multiprocessors, 1997
• 20: M. S. Squillante. A matrix-analytic approach to a general class of G/G/c queues. Research Report, IBM Research Division, 1996.
• 21: Mark S. Squillante , Fang Wang , Marios Papaefthymiou, Stochastic analysis of gang scheduling in parallel and distributed systems, Performance Evaluation, 27-28, p.273-296, Oct. 1996 [doi>10.1016/0166-5316(96)00042-9]
• 22: M. S. Squillante, Y. Zhang, A. Sivasubramaniam, N. Gautam, H. Franke, J. Moreira. Analytic modeling and analysis of dynamic coscheduling for a wide spectrum of parallel and distributed environments. Research Report, IBM Research Division, 2000.
• 23: Specification for the Virtual Interface Architecture. http://www.viarch.org.
• 24: Yanyong Zhang , Anand Sivasubramaniam , Jose Moreira , Hubertus Franke, A simulation-based study of scheduling mechanisms for a dynamic cluster environment, Proceedings of the 14th international conference on Supercomputing, p.100-109, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335241]