Implicit coscheduling: coordinated scheduling with implicit information in distributed systems

ABSTRACT

In modern distributed systems, coordinated time-sharing is required for communicating processes to leverage the performance of switch-based networks and low-overhead protocols. Coordinated time-sharing has traditionally been achieved with gang scheduling or explicit coscheduling, implementations of which often suffer from many deficiencies: multiple points of failure, high context-switch overheads, and poor interaction with client-server, interactive, and I/O -intensive workloads. Implicit coscheduling dynamically coordinates communicating processes across distributed machines without these structural deficiencies. In implicit coscheduling, no communication is required across operating systems schedulers; instead, cooperating processes achieve coordination by reacting to implicit information carried by communication existing within the parallel application. The implementation of this approach is simple and allows participating nodes to act autonomously. We introduce two key mechanisms in implicit coscheduling. The first is conditional two-phase waiting, a generalization of traditional two-phase waiting in which spin-time may be increased depending upon events occuring while the process waits. The second is an extension to stride scheduling that provides preemption and is fair to processes that block. To demonstrate that implicit coscheduling performs well, we show results from an extensive set of simulation and implementation experiments. To exercise the conditional two-phase waiting algorithm, we examine three workloads: bulk-synchronous and continuous-communication synthetic applications and application kernels written in the Split-C language. To exercise the local scheduler, we examine competing jobs with different communication characteristics. We demonstrate that our implementation scales well with the number of jobs and workstations and is robust to process placement. Our experiments show that implicit coscheduling is effective and fair for a wide range of workloads; most perform within 30% of an idealized model of gang scheduling.

REFERENCES

• 1: Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.95-105, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215427]
• 2: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 3: T. E. Anderson , M. D. Dahlin , J. M. Neefe , D. A. Patterson , D. S. Roselli , R. Y. Wang, Serverless network file systems, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.109-126, December 03-06, 1995, Copper Mountain, Colorado, United States
• 4: 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
• 5: ARPACI-DUSSEAU,A.AND CULLER, D. 1997. Extending Proportional-Share Scheduling to a Network of Workstations. In International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA) (Las Vegas, Nevada, June 1997).
• 6: Andrea Carol Arpaci-Dusseau , David Culler, Implicit coscheduling: coordinated scheduling with implicit information in distributed systems, 1998
• 7: Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau , David E. Culler , Joseph M. Hellerstein , David A. Patterson, High-performance sorting on networks of workstations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.243-254, May 11-15, 1997, Tucson, Arizona, United States
• 8: BIAGIONI, E., COOPER, E., AND SANSOM, R. 1993. Designing a Practical ATMLAN. IEEE Network 7,2 (March), 32-39.
• 9: 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]
• 10: Eric A. Brewer , Bradley C. Kuszmaul, How to Get Good Performance from the CM-5 Data Network, Proceedings of the 8th International Symposium on Parallel Processing, p.858-867, April 01, 1994
• 11: BUCHANAN,M.AND CHIEN, A. 1997. Coordinated Thread Scheduling for Workstation Clusters Under Windows NT. In Proceedings of USENIX Windows NT Workshop (Aug. 1997).
• 12: Douglas C. Burger , Rahmat S. Hyder , Barton P. Miller , David A. Wood, Paging tradeoffs in distributed-shared-memory multiprocessors, Proceedings of the 1994 conference on Supercomputing, p.590-599, December 1994, Washington, D.C., United States
• 13: M. Crovella , P. Das , C. Dubnicki , T. LeBlanc , E. Markatos, Multiprogramming on Multiprocessors, University of Rochester, Rochester, NY, 1991
• 14: CULLER, D., ARPACI-DUSSEAU, A., ARPACI-DUSSEAU, R., CHUN, B., LUMETTA, S., MAINWARING, A., MARTIN, R., YOSHIKAWA,C.,AND WONG, F. 1997. Parallel Computing on the Berkeley NOW. In Ninth Joint Symposium on Parallel Processing (Kobe, Japan, May 1997).
• 15: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 16: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 17: Dorothy E. Denning , Peter J. Denning, Data Security, ACM Computing Surveys (CSUR), v.11 n.3, p.227-249, Sept. 1979 [doi>10.1145/356778.356782]
• 18: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 19: DOWDY, L. 1988. On the Partitioning of Multiprocessor Systems. Technical Report 88-06 (July), Department of Computer Science, Vanderbilt University.
• 20: 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
• 21: 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]
• 22: EYKHOLT, J. R., KLEIMAN, S. R., BARTON, S., VOLL, J., FAULKNER, R., SHIVALINGIAH, A., SMITH, M., STEIN, D., WEEKS, M., AND WILLIAMS, D. 1992. Beyond Multiprocessing: Multithreading the SunOS Kernel. In Proceedings of the Summer 1992 USENIX Technical Conference and Exhibition (San Antontio, TX, USA, June 1992), pp. 11-18.
• 23: FEITELSON, D. G. 1995. A Survey of Scheduling in Multiprogrammed Parallel Systems. Research Report RC 19790 (87657) (February), IBM T. J. Watson Research Center, Yorktown Heights, NY. Second Revision, August 1997.
• 24: 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
• 25: Dror G. Feitelson, Distributed Hierarchical Control for Parallel Processing, Computer, v.23 n.5, p.65-77, May 1990 [doi>10.1109/2.53356]
• 26: FEITELSON,D.G.AND RUDOLPH, L. 1992. Gang Scheduling Performance Benefits for Fine- Grained Synchronization. Journal of Parallel and Distributed Computing 16, 4 (December), 306-18.
• 27: 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]
• 28: Douglas P. Ghormley , David Petrou , Steven H. Rodrigues , Amin M. Vahdat , Thomas E. Anderson, GLUnix: a global layer Unix for a network of workstations, Software—Practice & Experience, v.28 n.9, p.929-961, July 25, 1998 [doi>10.1002/(SICI)1097-024X(19980725)28:9<929::AID-SPE183>3.0.CO;2-C]
• 29: 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
• 30: J. L. Hellerstein, Achieving Service Rate Objectives with Decay Usage Scheduling, IEEE Transactions on Software Engineering, v.19 n.8, p.813-825, August 1993 [doi>10.1109/32.238584]
• 31: 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]
• 32: 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
• 33: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 34: KARLIN, A. R., MANASSE, M., MCGEOCH, L., AND OWICKI, S. 1994. Competitive Randomized Algorithms For Nonuniform Problems. Algorithmica 11, 6 (June), 542-71.
• 35: J. Kay , P. Lauder, A fair share scheduler, Communications of the ACM, v.31 n.1, p.44-55, Jan. 1988 [doi>10.1145/35043.35047]
• 36: Walter Lee , Matthew Frank , Victor Lee , Kenneth Mackenzie , Larry Rudolph, Implications of I/O for Gang Scheduled Workloads, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.215-237, April 05, 1997
• 37: 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
• 38: MAINWARING, A. M. 1995. Active Message Application Programming Interface and Communication Subsystem Organization. Master's thesis, University of California, Berkeley.
• 39: Richard P. Martin , Amin M. Vahdat , David E. Culler , Thomas E. Anderson, Effects of communication latency, overhead, and bandwidth in a cluster architecture, Proceedings of the 24th annual international symposium on Computer architecture, p.85-97, June 01-04, 1997, Denver, Colorado, United States
• 40: Randolph Nelson , Donald Towsley, A performance evaluation of several priority policies for parallel processing systems, Journal of the ACM (JACM), v.40 n.3, p.714-740, July 1993 [doi>10.1145/174130.174143]
• 41: Jason Nieh , James G. Hanko , J. Duane Northcutt , Gerard A. Wall, SVR4UNIX Scheduler Unacceptable for Multimedia Applications, Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video, p.41-53, November 03-05, 1993
• 42: OUSTERHOUT, J. K. 1982. Scheduling Techniques for Concurrent Systems. In Third International Conference on Distributed Computing Systems (May 1982), pp. 22-30.
• 43: 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]
• 44: Emilia Rosti , Giuseppe Serazzi , Evgenia Smirni , Mark S. Squillante, The impact of I/O on program behavior and parallel scheduling, ACM SIGMETRICS Performance Evaluation Review, v.26 n.1, p.56-65, June 1998
• 45: 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
• 46: Patrick Sobalvarro , Scott Pakin , William E. Weihl , Andrew A. Chien, Dynamic Coscheduling on Workstation Clusters, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.231-256, March 30, 1998
• 47: V. S. Sunderam, PVM: a framework for parallel distributed computing, Concurrency: Practice and Experience, v.2 n.4, p.315-339, Dec. 1990 [doi>10.1002/cpe.4330020404]
• 48: CORPORATE The MPI Forum, MPI: a message passing interface, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.878-883, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169855]
• 49: 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
• 50: 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
• 51: Carl A. Waldspurger, Lottery and stride scheduling: flexibile proportional-share resource management, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 52: C. A. Waldspurger , W. E. Weihl, An object-oriented framework for modular resource management, Proceedings of the 5th International Workshop on Object Orientation in Operating Systems (IWOOOS '96), p.138, October 27-28, 1996
• 53: Fang Wang , Marios C. Papaefthymiou , Mark S. Squillante, Performance Evaluation of Gang Scheduling for Parallel and Distributed Multiprogramming, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.277-298, April 05, 1997
• 54: WARREN,M.S.,BECKER,D.J.,GODA,M.P.,SALMON,J.K.,AND STERLING, T. 1997. Parallel Supercomputing with Commodity Components. In International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA) (Las Vegas, Nevada, June 1997), pp. 1372- 1381.
• 55: Frederick C. Wong , Andrea C. Arpaci-Dusseau , David E. Culler, Building MPI for Multi-Programming Systems Using Implicit Information, Proceedings of the 6th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, p.215-222, September 26-29, 1999

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

General Terms:
Algorithms, Design, Performance

Keywords:
clusters, coscheduling, gang scheduling, networks of workstations, proportional-share scheduling, two-phase waiting