Adaptive scheduling with parallelism feedback

ABSTRACT

Multiprocessor scheduling in a shared multiprogramming environment is often structured as two-level scheduling, where a kernel-level job scheduler allots processors to jobs and a user-level task scheduler schedules the work of a job on the allotted processors. In this context, the number of processors allotted to a particular job may vary during the job's execution, and the task scheduler must adapt to these changes in processor resources. For overall system efficiency, the task scheduler should also provide parallelism feedback to the job scheduler to avoid the situation where a job is allotted processors that it cannot use productively.We present an adaptive task scheduler for multitasked jobs with dependencies that provides continual parallelism feedback to the job scheduler in the form of requests for processors. Our scheduler guarantees that a job completes near optimally while utilizing at least a constant fraction of the allotted processor cycles. Our scheduler can be applied to schedule data-parallel programs, such as those written in High Performance Fortran (HPF), *Lisp, C*, NESL, and ZPL.Our analysis models the job scheduler as the task scheduler's adversary, challenging the task scheduler to be robust to the system environment and the job scheduler's administrative policies. For example, the job scheduler can make available a huge number of processors exactly when the job has little use for them. To analyze the performance of our adaptive task scheduler under this stringent adversarial assumption, we introduce a new technique called "trim analysis," which allows us to prove that our task scheduler performs poorly on at most a small number of time steps, exhibiting near-optimal behavior on the vast majority.To be precise, suppose that a job has work T1 and critical-path length T∞ and is running on a machine with P processors. Using trim analysis, we prove that our scheduler completes the job in O(T1/P + T∞ + Llg P) time steps, where L is the length of a scheduling quantum and P denotes the O(T∞ + L lg P)-trimmed availability. This quantity is the average of the processor availability over all time steps excluding the O(T∞ + L lg P) time steps with the highest processor availability. When T1/T∞ >> P (the job's parallelism dominates the O(T∞ + L lg P)-trimmed availability), the job achieves nearly perfect linear speedup. Conversely, when T1/T∞ << P, the asymptotic running time of the job is nearly the length of its critical path.

REFERENCES

• 1: Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277678]
• 2: Nikhil Bansal , Kedar Dhamdhere , Amitabh Sinha, Non-Clairvoyant Scheduling for Minimizing Mean Slowdown, Algorithmica, v.40 n.4, p.305-318, September 2004 [doi>10.1007/s00453-004-1115-0]
• 3: Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999 [doi>10.1145/301970.301974]
• 4: Guy E. Blelloch , Jonathan C. Hardwick , Jay Sipelstein , Marco Zagha , Siddhartha Chatterjee, Implementation of a portable nested data-parallel language, Journal of Parallel and Distributed Computing, v.21 n.1, p.4-14, April 1994 [doi>10.1006/jpdc.1994.1038 ]
• 5: Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215403]
• 6: Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.213-225, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 7: Robert D. Blumofe, Executing multithreaded programs efficiently, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 8: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 9: Robert D. Blumofe , Charles E. Leiserson, Space-Efficient Scheduling of Multithreaded Computations, SIAM Journal on Computing, v.27 n.1, p.202-229, Feb. 1998 [doi>10.1137/S0097539793259471]
• 10: Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999 [doi>10.1145/324133.324234]
• 11: Robert D. Blumofe and Philip A. Lisiecki. Adaptive and reliable parallel computing on networks of workstations. In Proceedings of the USENIX Annual Technical Symposion, pages 133--147, 1997.
• 12: Robert D. Blumofe and Dionisios Papadopoulos. Hood: a user-level threads library for multiprogrammed multiprocessors. Technical report, University of Texas at Austin, 1999.
• 13: Robert D. Blumofe and David S. Park. Scheduling large-scale parallel computations on networks of workstations. In Proceedings of the IEEE International Symposium on High-Performance Distributed Computing, pages 96--105, 1994.
• 14: Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
• 15: J. Bruno , E. G. Coffman, Jr. , R. Sethi, Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, v.17 n.7, p.382-387, July 1974 [doi>10.1145/361011.361064]
• 16: Bradford L. Chamberlain , Sung-Eun Choi , E. Christopher Lewis , Calvin Lin , Lawrence Snyder , W. Derrick Weathersby, ZPL: A Machine Independent Programming Language for Parallel Computers, IEEE Transactions on Software Engineering, v.26 n.3, p.197-211, March 2000 [doi>10.1109/32.842947 ]
• 17: Xiaotie Deng , Patrick Dymond, On multiprocessor system scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.82-88, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237510]
• 18: Xiaotie Deng , Nian Gu , Tim Brecht , KaiCheng Lu, Preemptive scheduling of parallel jobs on multiprocessors, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.159-167, January 28-30, 1996, Atlanta, Georgia, United States
• 19: D. L. Eager , J. Zahorjan , E. D. Lozowska, Speedup Versus Efficiency in Parallel Systems, IEEE Transactions on Computers, v.38 n.3, p.408-423, March 1989 [doi>10.1109/12.21127 ]
• 20: Guy Edjlali , Gagan Agrawal , Alan Sussman , Jim Humphries , Joel Saltz, Compiler and runtime support for programming in adaptive parallel environments, University of Maryland at College Park, College Park, MD, 1995
• 21: Guy Edjlali , Gagan Agrawal , Alan Sussman , Joel Saltz, Data parallel programming in an adaptive environment, University of Maryland at College Park, College Park, MD, 1994
• 22: Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301299]
• 23: Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clair voy ant multiprocessor scheduling of jobs with changing execution characteristics, Journal of Scheduling, v.6 n.3, p.231-250, May/June 2003 [doi>10.1023/A:1022952324290]
• 24: Zhixi Fang , Peiyi Tang , Pen-Chung Yew , Chuan-Qi Zhu, Dynamic Processor Self-Scheduling for General Parallel Nested Loops, IEEE Transactions on Computers, v.39 n.7, p.919-929, July 1990 [doi>10.1109/12.55693 ]
• 25: Dror G. Feitelson. Job scheduling in multiprogrammed parallel systems (extended version). Technical report, IBM Research Report RC 19790 (87657) 2nd Revision, 1997.
• 26: High Performance Fortran Forum. High Performance Fortran language specification version 1.0. Technical report, Rice University, 1993.
• 27: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• 28: Joseph Gil , Yossi Matias, Fast and efficient simulations among CRCW PRAMs, Journal of Parallel and Distributed Computing, v.23 n.2, p.135-148, Nov. 1994 [doi>10.1006/jpdc.1994.1127 ]
• 29: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 30: R. L. Graham. Bounds on multiprocessing anomalies. SIAM Journal on Applied Mathematics, pages 17(2):416--429, 1969.
• 31: Nian Gu. Competitive analysis of dynamic processor allocation strategies. Master's thesis, York University, 1995.
• 32: Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994 [doi>10.1145/176979.176984]
• 33: S. F. Hummel , E. Schonberg, Low-overhead scheduling of nested parallelism, IBM Journal of Research and Development, v.35 n.5-6, p.743-765, Sept./Nov. 1991
• 34: D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
• 35: C. Lasser. The Essential *Lisp Manual. Thinking Machines Corporation, 1986.
• 36: 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
• 37: S. Majumdar , D. L. Eager , R. B. Bunt, Scheduling in multiprogrammed parallel systems, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.104-113, May 24-27, 1988, Santa Fe, New Mexico, United States
• 38: Xavier Martorell , Julita Corbalán , Dimitrios S. Nikolopoulos , Nacho Navarro , Eleftherios D. Polychronopoulos , Theodore S. Papatheodorou , Jesús Labarta, A Tool to Schedule Parallel Applications on Multiprocessors: The NANOS CPU MANAGER, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.87-112, May 01, 2000
• 39: 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]
• 40: Eric Mohr , David A. Kranz , Robert H. Halstead, Jr., Lazy task creation: a technique for increasing the granularity of parallel programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.185-197, June 27-29, 1990, Nice, France [doi>10.1145/91556.91631]
• 41: Rajeev Motwani , Steven Phillips , Eric Torng, Non-clairvoyant scheduling, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.422-431, January 25-27, 1993, Austin, Texas, United States
• 42: 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]
• 43: Girija J. Narlikar , Guy E. Blelloch, Space-efficient scheduling of nested parallelism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.1, p.138-173, Jan. 1999 [doi>10.1145/314602.314607]
• 44: Liang Peng, Weng~Fai Wong, Ming Dong Feng, and Chung Kwong Yuen. SilkRoad: a multithreaded runtime system with software distributed shared memory for SMP clusters. In IEEE International Conferrence on Cluster Computing, pages 243--249, 2000.
• 45: J. R. Rose and G. L. Steele Jr. C*: An extended C language for data parallel programming. In Proceedings of Supercomputing, pages 2--16, 1987.
• 46: E. Rosti , E. Smirni , L. W. Dowdy , G. Serazzi , B. M. Carlson, Robust partitioning policies of multiprocessor systems, Performance Evaluation, v.19 n.2-3, p.141-165, March 1994 [doi>10.1016/0166-5316(94)90037-X]
• 47: Emilia Rosti , Evgenia Smirni , Giuseppe Serazzi , Lawrence W. Dowdy, Analysis of Non-Work-Conserving Processor Partitioning Policies, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.165-181, April 25, 1995
• 48: Siddhartha Sen. Dynamic processor allocation for adaptively parallel jobs. Master's thesis, Massachusetts Institute of Technology, 2004.
• 49: B. Song. Scheduling adaptively parallel jobs. Master's thesis, Massachusetts Institute of Technology, 1998.
• 50: Mark S. Squillante, On the Benefits and Limitations of Dynamic Partitioning in Parallel Computer Systems, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.219-238, April 25, 1995
• 51: Dan Suciu , Val Tannen, Efficient compilation of high-level data parallel algorithms, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.57-66, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181032]
• 52: Timothy B. Brecht , Kaushik Guha, Using parallel program characteristics in dynamic processor allocation policies, Performance Evaluation, 27-28, p.519-539, Oct. 1996 [doi>10.1016/0166-5316(96)00030-2 ]
• 53: A. Tucker , A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.159-166, November 1989
• 54: John Turek , Walter Ludwig , Joel L. Wolf , Lisa Fleischer , Prasoon Tiwari , Jason Glasgow , Uwe Schwiegelshohn , Philip S. Yu, Scheduling parallelizable tasks to minimize average response time, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.200-209, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181331]
• 55: K. K. Yue and D. J. Lilja. Implementing a dynamic processor allocation policy for multiprogrammed parallel applications in the solaris (tm) operating system. Concurrency and Computation-Practice and Experience, 13(6):449--464, 2001.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Performance, Theory

Keywords:
adaptive scheduling, adversary, critical path, data-parallel computing, greedy scheduling, instantaneous parallelism, job scheduling, multiprocessing, multiprogramming, parallel computation, parallelism feedback, processor allocation, space sharing, task scheduling, trim analysis, two-level scheduling, work