Brief announcement: a lower bound for depth-restricted work stealing

ABSTRACT

Work stealing is a common technique used in the runtime schedulers of parallel languages such as Cilk and parallel libraries such as Intel Threading Building Blocks (TBB). Depth-restricted work stealing is a restriction of Cilk-like work stealing in which a processor blocked on a task at depth d can only steal tasks from other processors at depth greater than d. To support programs coded in a blocking style, i.e., code without explicit continuations, TBB imposes a depth restriction on work stealing to limit the stack space used by a computation.

We present a lower bound on the completion time of a computation executed using a depth-restricted work-stealing scheduler. In particular, we construct a computation which on P processors runs a factor of Ω(P) slower with depth-restricted work stealing as compared to unrestricted work stealing. On this pessimal computation, depth-restricted work stealing asymptotically serializes execution while unrestricted work stealing achieves linear speedup.

REFERENCES

• 1: 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]
• 2: Mingdong Feng , Charles E. Leiserson, Efficient detection of determinacy races in Cilk programs, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.1-11, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258493]
• 3: 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
• 4: James Reinders, Intel threading building blocks, O'Reilly & Associates, Inc., Sebastopol, CA, 2007

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

General Terms:
Algorithms, Performance, Theory

Keywords:
cilk, dynamic multithreading, intel threading building blocks, scheduling, work stealing