知识卡片
工作跨度可预测扩容后的性能
并行优化若减少总工作量却增加最长依赖链,在小机器上可能更快、扩容后反而更慢。
用工作量除以处理器数再加跨度估算时,跨度会在处理器增多后主导耗时;因此不能只看当前机器的基准时间。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
The optimization that speeds up the program on 32 processors makes the program run for twice as long on 512 processors! The optimized version’s span of 8, which is not the dominant term in the running time on 32 processors, becomes the dominant term on 512 processors, nullifying the advantage from using more processors. The optimization does not scale up.
参考来源
- 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[50000,55000))。
- 结论依据:第26章国际象棋程序扩容案例:优化使工作 T₁ 从2048降至1024秒,但跨度从1升至8秒;用式(26.4)近似时,32核上65→40秒,512核上5→10秒。
- 原始内容:The optimization that speeds up the program on 32 processors makes the program run for twice as long on 512 processors! The optimized version’s span of 8, which is not the dominant term in the running time on 32 processors, becomes the dominant term on 512 processors, nullifying the advantage from using more processors. The optimization does not scale up.
- 工作跨度数据(文本字符[50000,55000)):The original version of the program had work T 1 = 2048 seconds and span T ∞ = 1 second. Let’s treat inequality (26.4) on page 760 as the equation T P = T 1 / P + T ∞ , which we can use as an approximation to the running time on P processors. Then indeed we have T 32 = 2048/32 + 1 = 65. With the optimization, the work becomes T ′ 1 = 1024 seconds, and the span becomes T ′ ∞ = 8 seconds.