知识卡片
工作与跨度给并行时间下界
T₁是全部计算在单处理器上的总工作量,T∞是无限处理器下仍必须串行经过的最长依赖链,T_P是用P个处理器的运行时间;P个处理器每单位时间至多做P单位工作,因此T_P≥T₁/P;- 再多处理器也不能突破关键依赖链,因此
T_P≥T∞。
所以 T_P≥max(T₁/P,T∞)。补充教学演示:若 T₁=100、T∞=30、P=4,工作律给出 25,跨度律给出 30,任何调度都不可能少于 30 个时间单位。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
The work and span provide lower bounds on the running time TP of a task-parallel computation on P processors: In one step, an ideal parallel computer with P processors can do at most P units of work, and thus in TP
参考来源
- 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[20000,25000))。
- 结论依据:原文给出工作律与跨度律;Art_P829–P830补全公式。数值代入为补充教学演示。
- 原始内容:The work and span provide lower bounds on the running time T P of a task-parallel computation on P processors: In one step, an ideal parallel computer with P processors can do at most P units of work, and thus in T P