Scheduling multithreaded computations by work stealing
Robert D. Blumofe, Charles E. Leiserson · Annual Symposium on Foundations of Computer Science · 2002
This paper studies the problem of efficiently scheduling 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 T/sub P/ to execute a fully strict computation on P processors using our work-stealing scheduler is T/sub P/=O(T/sub 1//P+T/sub /spl infin//), where T/sub 1/ is the minimum serial execution time of the multithreaded computation and T/sub /spl infin// is the minimum execution time with an infinite number of processors. Moreover, the space S/sub P/ required by the execution satisfies S/sub P//spl les/S/sub 1/P. We also show that the expected total communication of the algorithm is at most O(T/sub /spl infin//S/sub max/P), where S/sub max/ is the size of the largest activation record of any thread, thereby justifying 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 409 works. doi:10.1109/sfcs.1994.365680
Authors
References
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- The Parallel Evaluation of General Arithmetic Expressions
- How to emulate shared memory
- Resource requirements of dataflow programs
- DIB—a distributed implementation of backtracking
- Lazy task creation: a technique for increasing the granularity of parallel programs
- I-structures: data structures for parallel computing
- WorkCrews: An abstraction for controlling parallelism
- Implementation of multilisp