Scheduling multithreaded computations by work stealing
Robert D. Blumofe, Charles E. Leiserson · Journal of the ACM · 1999
This paper studies the problem of efficiently schedulling fully strict (i.e., well-structured) multithreaded computations on parallel computers. A popular and practical method of scheduling this kind of dynamic MIMD-style computation is “work stealing,” in which processors needing work steal computational threads from other processors. In this paper, we give the first provably good work-stealing scheduler for multithreaded computations with dependencies. Specifically, our analysis shows that the expected time to execute a fully strict computation on P processors using our work-stealing scheduler is T 1 / P + O ( T ∞ , where T 1 is the minimum serial execution time of the multithreaded computation and ( T ∞ is the minimum execution time with an infinite number of processors. Moreover, the space required by the execution is at most S 1 P , where S 1 is the minimum serial space requirement. We also show that the expected total communication of the algorithm is at most O ( PT ∞ ( 1 + n d ) S max ), where S max is the size of the largest activation record of any thread and n d is the maximum number of times that any thread synchronizes with its parent. This communication bound justifies the folk wisdom that work-stealing schedulers are more communication efficient than their work-sharing counterparts. All three of these bounds are existentially optimal to within a constant factor.
Cited by 1,336 works. doi:10.1145/324133.324234
Authors
References
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- The Parallel Evaluation of General Arithmetic Expressions
- Department of electrical engineering and computer science
- The implementation of the Cilk-5 multithreaded language
- Cilk: An Efficient Multithreaded Runtime System
- How to emulate shared memory
- Speedup versus efficiency in parallel systems
- Resource requirements of dataflow programs
- DIB—a distributed implementation of backtracking