In:
Journal of the ACM, Association for Computing Machinery (ACM), Vol. 46, No. 5 ( 1999-09), p. 720-748
Abstract:
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.
Type of Medium:
Online Resource
ISSN:
0004-5411
,
1557-735X
DOI:
10.1145/324133.324234
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
1999
detail.hit.zdb_id:
2006500-0
detail.hit.zdb_id:
6759-3
