Adaptive work stealing with parallelism feedback

ABSTRACT

We present an adaptive work-stealing thread scheduler, A-Steal, for fork-join multithreaded jobs, like those written using the Cilk multithreaded language or the Hood work-stealing library. The A-Steal algorithm is appropriate for large parallel servers where many jobs share a common multiprocessor resource and in which the number of processors available to a particular job may vary during the job's execution. A-Steal provides continual parallelism feedback to a job scheduler in the form of processor requests, and the job must adaptits execution to the processors allotted to it. Assuming that the job scheduler never allots any job more processors than requested by thejob's thread scheduler, A-Steal guarantees that the job completes in near-optimal time while utilizing at least a constant fraction of the allotted processors.

Our analysis models the job scheduler as the thread scheduler's adversary, challenging the thread scheduler to be robust to the system environment and the job scheduler's administrative policies. We analyze the performance of A-Steal using "trim analysis," which allows us to prove that our thread scheduler performs poorly on at most a small number of time steps, while exhibiting near-optimal behavior on the vast majority. To be precise, suppose that a job has work T₁ and span (critical-path length)T_∞. On a machine with P processors, A-Steal completes the job in expected O(T₁/P + T_∞ + L lg 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 but the O(T_∞ + L lg P)time steps having the highest processor availability. When the job's parallelism dominates the trimmed availability, that is, P « T₁/T_∞, the job achieves nearly perfect linear speedup. Conversely, when the trimmed mean dominates the parallelism, the asymptotic running time of the job is nearly its span.

REFERENCES

• 1: Umut A. Acar , Guy E. Blelloch , Robert D. Blumofe, The data locality of work stealing, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.1-12, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341801]
• 2: Kunal Agrawal , Yuxiong He , Wen Jing Hsu , Charles E. Leiserson, Adaptive scheduling with parallelism feedback, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122988]
• 3: Kunal Agrawal , Yuxiong He , Charles E. Leiserson, An Empirical Evaluation ofWork Stealing with Parallelism Feedback, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.19, July 04-07, 2006 [doi>10.1109/ICDCS.2006.14]
• 4: 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]
• 5: James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994 [doi>10.1145/185675.185815]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: 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
• 10: Robert D. Blumofe, Executing multithreaded programs efficiently, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 11: 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
• 12: 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]
• 13: 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]
• 14: Robert D. Blumofe, Charles E. Leiserson, and Bin Song. Automatic processor allocation for work-stealing jobs. 1998.
• 15: Robert D. Blumofe and Philip A. Lisiecki. Adaptive and reliable parallel computing on networks of workstations. In USENIX, pages 133--147, Anaheim, California, 1997.
• 16: Robert D. Blumofe , Dionisios Papadopoulos, The performance of work stealing in multiprogrammed environments (extended abstract), ACM SIGMETRICS Performance Evaluation Review, v.26 n.1, p.266-267, June 1998
• 17: Robert D. Blumofe and Dionisios Papadopoulos. Hood: A user-level threads library for multiprogrammed multiprocessors. Technical report, University of Texas at Austin, 1999.
• 18: Robert D. Blumofe and David S. Park. Scheduling large-scale parallel computations on networks of workstations. In HPDC, pages 96--105, San Francisco, California, 1994.
• 19: 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]
• 20: F. Warren Burton , M. Ronan Sleep, Executing functional programs on a virtual tree of processors, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.187-194, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806778]
• 21: Su-Hui Chiang , Mary K. Vernon, Dynamic vs. Static Quantum-Based Parallel Processor Allocation, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.200-223, April 16, 1996
• 22: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 23: 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]
• 24: DESMO-J: A framework for discrete-event modelling and simulation. http://asi-www.informatik.uni-hamburg.de/desmoj/.
• 25: 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 ]
• 26: 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]
• 27: 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]
• 28: 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 ]
• 29: Dror G. Feitelson. Job scheduling in multiprogrammed parallel systems (extended version). Technical report, IBM Research Report RC 19790 (87657) 2nd Revision, 1997.
• 30: Raphael Finkel , Udi Manber, DIB—a distributed implementation of backtracking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.235-256, April 1987 [doi>10.1145/22719.24067]
• 31: 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
• 32: 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 ]
• 33: R. L. Graham. Bounds on multiprocessing anomalies. SIAM Journal on Applied Mathematics, pages 17(2):416--429, 1969.
• 34: Nian Gu. Competitive analysis of dynamic processor allocation strategies. Master's thesis, York University, 1995.
• 35: Michael Halbherr, Yuli Zhou, and Chris F. Joerg. MIMD-style parallel programming with continuation-passing threads. In Proceedings of the International Workshop on Massive Parallelism: Hardware, Software, and Applications, Capri, Italy, September 1994.
• 36: Robert H. Halstead, Jr., Implementation of multilisp: Lisp on a multiprocessor, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.9-17, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802017]
• 37: Yuxiong He, Hsu Wen Jing, and Charles E. Leiserson. Provably efficient two-level adaptive scheduling for multithreaded jobs on parallel computers. JSSPP, 2006.
• 38: 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
• 39: Richard Karp , Yanjun Zhang, A randomized parallel branch-and-bound procedure, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.290-300, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62240]
• 40: 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]
• 41: 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]
• 42: 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
• 43: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 44: 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]
• 45: Thu D. Nguyen , Raj Vaswani , John Zahorjan, Maximizing Speedup through Self-Tuning of Processor Allocation, Proceedings of the 10th International Parallel Processing Symposium, p.463-468, April 15-19, 1996
• 46: Thu D. Nguyen , Raj Vaswani , John Zahorjan, Using Runtime Measured Workload Characteristics in Parallel Processor Scheduling, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.155-174, April 16, 1996
• 47: Eric W. Parsons , Kenneth C. Sevcik, Multiprocessor Scheduling for High-Variability Service Time Distributions, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.127-145, April 25, 1995
• 48: Larry Rudolph , Miriam Slivkin-Allalouf , Eli Upfal, A simple load balancing scheme for task allocation in parallel machines, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.237-245, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113401]
• 49: William N. Scherer, III , Doug Lea , Michael L. Scott, Scalable synchronous queues, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122994]
• 50: Siddhartha Sen. Dynamic processor allocation for adaptively parallel jobs. Master's thesis, Massachusetts Institute of technology, 2004.
• 51: 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
• 52: Nir Shavit , Dan Touitou, Elimination trees and the construction of pools and stacks: preliminary version, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215419]
• 53: Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996 [doi>10.1145/235543.235546]
• 54: B. Song. Scheduling adaptively parallel jobs. Master's thesis, Massachusetts Institute of Technology, 1998.
• 55: 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 ]
• 56: 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
• 57: Roger Wattenhofer , Peter Widmayer, The counting pyramid: an adaptive distributed counting scheme, Journal of Parallel and Distributed Computing, v.64 n.4, p.449-460, April 2004 [doi>10.1016/S0743-7315(03)00114-X]
• 58: K. K. Yue and D. J. Lilja. Implementing a dynamic processor allocation policy for multiprogrammed parallel applications in the Solaris™ 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
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
adaptive scheduling, adversary, distributed scheduling, job scheduling, multiprogramming, multithreaded languages, parallel computation, parallelism feedback, processor allocation, space sharing, thread scheduling, trim analysis, two-level scheduling, work stealing