.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
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总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息