Effective distributed scheduling of parallel workloads

ABSTRACT

We present a distributed algorithm for time-sharing parallel workloads that is competitive with coscheduling. Implicit scheduling allows each local scheduler in the system to make independent decisions that dynamically coordinate the scheduling of cooperating processes across processors. Of particular importance is the blocking algorithm which decides the action of a process waiting for a communication or synchronization event to complete. Through simulation of bulk-synchronous parallel applications, we find that a simple two-phase fixed-spin blocking algorithm performs well; a two-phase adaptive algorithm that gathers run-time data on barrier wait-times performs slightly better. Our results hold for a range of machine parameters and parallel program characteristics. These findings are in direct contrast to the literature that states explicit coscheduling is necessary for fine-grained programs. We show that the choice of the local scheduler is crucial, with a priority-based scheduler performing two to three times better than a round-robin scheduler. Overall, we find that the performance of implicit scheduling is near that of coscheduling (+/- 35%), without the requirement of explicit, global coordination.

REFERENCES

• 1: Remzi H. Arpaci , David E. Culler , Arvind Krishnamurthy , Steve G. Steinberg , Katherine Yelick, Empirical evaluation of the CRAY-T3D: a compiler perspective, Proceedings of the 22nd annual international symposium on Computer architecture, p.320-331, June 22-24, 1995, S. Margherita Ligure, Italy
• 2: Remzi H. Arpaci , Andrea C. Dusseau , Amin M. Vahdat , Lok T. Liu , Thomas E. Anderson , David A. Patterson, The interaction of parallel and sequential workloads on a network of workstations, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.267-278, May 15-19, 1995, Ottawa, Ontario, Canada
• 3: K. Arvind, Probabilistic Clock Synchronization in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.474-487, May 1994 [doi>10.1109/71.282558]
• 4: M. J. Atallah, C. L. Black, D. C. Marinescu, H. J. Siegel, and T. L. Casavant. Models and Algorithms for Co-scheduling Compute-Intensive Tasks on a Network of Workstations Journal of Parallel and Distrbuted Computing, 16-319-327, 1992.
• 5: Rohit Chandra , Scott Devine , Ben Verghese , Anoop Gupta , Mendel Rosenblum, Scheduling and page migration for multiprocessor compute servers, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.12-24, October 05-07, 1994, San Jose, California, United States
• 6: J. Chapin , M. Rosenblum , S. Devine , T. Lahiri , D. Teodosiu , A. Gupta, Hive: fault containment for shared-memory multiprocessors, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.12-25, December 03-06, 1995, Copper Mountain, Colorado, United States
• 7: Su-Hui Chiang , Rajesh K. Mansharamani , Mary K. Vernon, Use of application characteristics and limited preemption for run-to-completion parallel processor scheduling policies, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.33-44, May 16-20, 1994, Nashville, Tennessee, United States
• 8: M. Crovella, P. Das, C. Dubnicki, T. LeBlanc, and E. Markatos. Multiprogramming on Multiprocessors. In Proceed,ngs of the Third IEEE Symposium on Parallel and D~stmbuted Processzng, pages 590-597, Dec. 1991.
• 9: David E. Culler , Lok Tin Liu , Richard P. Martin , Chad O. Yoshikawa, Assessing Fast Network Interfaces, IEEE Micro, v.16 n.1, p.35-43, February 1996 [doi>10.1109/40.482310]
• 10: R. Cypher , A. Ho , S. Konstantinidou , P. Messina, Architectural requirements of parallel scientific applications with explicit communication, Proceedings of the 20th annual international symposium on Computer architecture, p.2-13, May 16-19, 1993, San Diego, California, United States
• 11: J. J. Dongarra, J. R. Bunch, C. B. Moler, and G W. Stewart LINPACK User's Guide. SIAM, Philadelphia, Penn, 1979.
• 12: Andrea C. Dusseau , David E. Culler , Klaus Erik Schauser , Richard P. Martin, Fast Parallel Sorting Under LogP: Experience with the CM-5, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.791-805, August 1996 [doi>10.1109/71.532111]
• 13: S. Evans, K. Clarke, D. Singleton, and B. Smaalders. Optimizing Unix Resource Scheduling for User Interaction. In 1993 Summer Usen,x, pages 205-218. USENIX, June 1993.
• 14: Dror G. Feitelson, Distributed Hierarchical Control for Parallel Processing, Computer, v.23 n.5, p.65-77, May 1990 [doi>10.1109/2.53356]
• 15: D. G. Feltelson and L Rudolph. Gang Scheduling Performance Benefits for Fine-Grained Synchronization Journal of Parallel and D,stmbuted Computing, 16(4):306-318, Dec. 1992
• 16: Dror G. Feitelson , Larry Rudolph, Coscheduling based on runtime identification of activity working sets, International Journal of Parallel Programming, v.23 n.2, p.135-160, April 1995 [doi>10.1007/BF02577787]
• 17: Dipak Ghosal , Giuseppe Serazzi , Satish K. Tripathi, The Processor Working Set and its Use in Scheduling Multiprocessor Systems, IEEE Transactions on Software Engineering, v.17 n.5, p.443-453, May 1991 [doi>10.1109/32.90447]
• 18: Berny Goodheart , James Cox, The magic garden explained: the internals of UNIX System V Release 4: an open systems design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 19: Anoop Gupta , Andrew Tucker , Shigeru Urushibara, The impact of operating system scheduling policies and synchronization methods of performance of parallel applications, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.120-132, May 21-24, 1991, San Diego, California, United States
• 20: High Performance Fortran Forum. High Performance Fortran language specification version 1 0 Draft, Jan. 1993
• 21: Mark D. Hill , James R. Larus , Steven K. Reinhardt , David A. Wood, Cooperative shared memory: software and hardware for scalable multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.300-318, Nov. 1993 [doi>10.1145/161541.161544]
• 22: Anna R. Karlin , Kai Li , Mark S. Manasse , Susan Owicki, Empirical studies of competitve spinning for a shared-memory multiprocessor, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.41-55, October 13-16, 1991, Pacific Grove, California, United States
• 23: K. Keeton, T. Anderson, and D. Patterson. LogP Quantified: The Case for Low-Overhead Local Area Networks. In Proceedings of Hot Interconnects II{, Aug. 1995
• 24: Leonidas Kontothanassis , Robert W. Wisniewski, Using scheduler information to achieve optimal barrier synchronization performance, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.64-72, May 19-22, 1993, San Diego, California, United States
• 25: Marshall Kirk McKusick , Keith Bostic , Michael J. Karels , John S. Quarterman, The design and implementation of the 4.4BSD operating system, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 26: S. T. Leutenegger , X.-H. Sun, Distributed computing feasibility in a non-dedicated homogeneous distributed system, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.143-152, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169673]
• 27: Scott T. Leutenegger , Mary K. Vernon, The performance of multiprogrammed multiprocessor scheduling algorithms, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.226-236, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 28: R. P. Martin HPAM An Active Message Layer for a Network of Workstations. In Proceedzngs of Hot Interconnects {I, July 1994.
• 29: 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]
• 30: Cathy McCann , John Zahorjan, Processor allocation policies for message-passing parallel computers, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.19-32, May 16-20, 1994, Nashville, Tennessee, United States
• 31: Cathy McCann , John Zahorjan, Scheduling memory constrained jobs on distributed memory parallel computers, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.208-219, May 15-19, 1995, Ottawa, Ontario, Canada
• 32: L McVoy and C. Staelin. lmbench: Portable Tools for Performance Analysis. In Proceedings of the i996 W, nter USENIX, Jan. 1996.
• 33: V. K. Naik , M. S. Squillante , S. K. Setia, Performance analysis of job scheduling policies in parallel supercomputing environments, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.824-833, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169848]
• 34: A. Olson , K. G. Shin, Fault-Tolerant Clock Synchronization in Large Multicomputer Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.912-923, September 1994 [doi>10.1109/71.308530]
• 35: J. K. Ousterhout. Scheduling Techniques for Concurrent Systems. In Th,rd International Conference on D~stmbuted Comput,ng Systems, pages 22-30, May 1982
• 36: Vinod G. J. Peris , Mark S. Squillante , Vijay K. Naik, Analysis of the impact of memory in distributed parallel processing systems, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.5-18, May 16-20, 1994, Nashville, Tennessee, United States
• 37: K. C. Sevcik, Characterizations of parallelism in applications and their use in scheduling, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.171-180, May 23-26, 1989, Oakland, California, United States
• 38: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 39: 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
• 40: 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
• 41: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 42: Robert W. Wisniewski , Leonidas I. Kontothanassis , Michael L. Scott, High performance synchronization algorithms for multiprogrammed multiprocessors, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.199-206, July 19-21, 1995, Santa Barbara, California, United States
• 43: J. Zahor9an and E. D. Lazowska. Spinning Versus Blocking m Parallel ~y~tems with Uncertain~y. In Proceedings of the IFIP International Seminar on Performance of D,stmbuted and Parallel Systems, pages 455-472, Dec. 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Management, Measurement, Performance, Verification