Scheduling multithreaded computations by work stealing

• Published in: Journal of the ACM 1999-09, Vol.46 (5), p.720-748
• Main Authors: BLUMOFE, ROBERT D, LEISERSON, CHARLES E
• Format: Article
• Language: English
• Subjects: Algorithms; Computation; Computational efficiency; Computer science; Constants; Multithreading; Operations research; Optimization; Parallel computers; Parallel processing; Processors; Scheduling; Serials; Studies
• ISSN: 0004-5411; 1557-735X
• DOI: 10.1145/324133.324234

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.