A simulation-based study of scheduling mechanisms for a dynamic cluster environment

ABSTRACT

Scheduling of processes onto processors of a parallel machine has always been an important and challenging area of research. The issue becomes even more crucial and difficult as we gradually progress to the use of off-the-shelf workstations, operating systems, and high bandwidth networks to build cost-effective clusters for demanding applications. Clusters are gaining acceptance not just in scientific applications that need supercomputing power, but also in domains such as databases, web service and multimedia, which place diverse Quality-of-Service (QoS) demands on the underlying system. Further, these applications have diverse characteristics in terms of their computation, communication and I/O requirements, making conventional parallel scheduling solutions, such as space sharing or coscheduling, an unattractive option. At the same time, leaving it to the native operating system of each node to make decisions independently can lead to ineffective use of system resources whenever there is communication. Instead, an emerging class of dynamic coscheduling mechanisms, that attempt to take remedial actions to guide the system towards coscheduled execution without requiring explicit synchronization, offer a lot of promise for cluster scheduling. Using a detailed simulator, this paper evaluates the pros and cons of different dynamic coscheduling alternatives, while comparing their advantages over traditional coscheduling (and not performing any coordinated scheduling at all). The impact of dynamic job arrivals, job characteristics and different system parameters on these alternatives are evaluated in terms of several performance criteria.

REFERENCES

• 1: 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
• 2: M. Buchanan and A. Chien. Coordinated Thread Scheduling for Workstation Clusters under Windows NT. In Proceedings of the USENIX Windows NT Workshop, August 1997.
• 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 and L. Rudolph. Coscheduling based on Run-Time Identification of Activity Working Sets. Technical Report Research Report RC 18416(80519), IBM T. J. Watson Research Center, October 1992.
• 5: D. G. Peitelson and L. Rudolph. Gang Scheduling Performance Benefits for Fine-Grained Synchronization. Journal of Parallel and Distributed Computing, 16(4):306-318, December 1992.
• 6: H. Franke , J. Jann , J. E. Moreira , P. Pattnaik , M. A. Jette, An evaluation of parallel job scheduling for ASCI Blue-Pacific, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.45-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331577]
• 7: Atsushi Hori , Hiroshi Tezuka , Yutaka Ishikawa, Global State Detection Using Network Preemption, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.262-276, April 05, 1997
• 8: David A. Lifka, The ANL/IBM SP Scheduling System, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.295-303, April 25, 1995
• 9: José E. Moreira , Hubertus Franke , Waiman Chan , Liana L. Fong , Morris A. Jette , Andy Yoo, A Gang-Scheduling System for ASCI Blue-Pacific, Proceedings of the 7th International Conference on High-Performance Computing and Networking, p.831-840, April 12-14, 1999
• 10: 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]
• 11: Shailabh Nagar , Ajit Banerjee , Anand Sivasubramaniam , Chita R. Das, Alternatives to coscheduling a network of workstations, Journal of Parallel and Distributed Computing, v.59 n.2, p.302-327, Nov. 1999 [doi>10.1006/jpdc.1999.1576]
• 12: J. K. Ousterhout. Scheduling Techniques for Concurrent Systems. In Proceedings of the 3rd International Conference on Distributed Computing Systems, pages 22-30, May 1982.
• 13: Scott Pakin , Mario Lauria , Andrew Chien, High performance messaging on workstations: Illinois fast messages (FM) for Myrinet, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.55-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224360]
• 14: F. Petrini and W. Feng. Buffered Coscheduling: A New Method for Multitasking Parallel Jobs on Distributed Systems. Technical report, Los Alamos National Laboratory, September 1999.
• 15: Patrick Gregory Sobalvarro , William E. Weihl, Demand-based coscheduling of parallel jobs on multiprogrammed multiprocessors, 1997
• 16: R. Subrahmaniam. Implementing Coscheduling Heuristics for Windows NT Clusters. Master's thesis, Dept. of Computer Science and Engineering, Penn State University, University Park, PA 16802, October 1999.
• 17: Thinking Machines Corporation, Cambridge, Massachusetts. The Connection Machine CM-5 Technical Summary, October 1991.
• 18: Specification for the Virtual Interface Architecture. http://maw, viarch, org.
• 19: T. von Eicken , A. Basu , V. Buch , W. Vogels, U-Net: a user-level network interface for parallel and distributed computing (includes URL), Proceedings of the fifteenth ACM symposium on Operating systems principles, p.40-53, December 03-06, 1995, Copper Mountain, Colorado, United States
• 20: Improving Parallel Job Scheduling by Combining Gang Scheduling and Backfilling Techniques, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.133, May 01-05, 2000
• 21: Y. Zhang, A. Sivasubramaniam, J. Moreira, and H. Franke. A Simulation-based Study of Scheduling Mechanisms for a Dynamic Cluster Environment. Technical Report CSE-99-022, Dept. of Computer Science and Engineering, The Pennsylvania State University, November 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
clusters, coscheduling, dynamic coscheduling, parallel scheduling, simulation