.png){kind=icon}
Return
Scheduling multithreaded computations by work stealing
.png){kind=icon}
PRE
AI
DOI：10.1145/324133.324234.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
No journal information available
Organization
No organization information available
Cited Papers
No cited papers available