知识卡片
两层并行矩阵乘法的跨度为线性
矩阵乘法并行化外层行、列循环,内层累加仍串行,因此总工作量为三次方、跨度为线性、并行度为平方。
若直接把内层也并行化,多个迭代会写同一矩阵元素。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
The span is T∞(n) = Θ(n), because it follows a path down the tree of recursion for the parallel for loop starting in line 1, then down the tree of recursion for the parallel for loop starting in line 2, and then executes all n iterations of the ordinary for loop starting in line 3, resulting in a total span of Θ(lg n) + Θ(lg n) + Θ(n) = Θ(n). Thus the parallelism is Θ(n3)/Θ(n) = Θ(n2).
参考来源
- 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[50000,60000))。
- 结论依据:第26章 P-MATRIX-MULTIPLY 第1–3行:前两层 parallel for 各贡献 Θ(lg n) 跨度,内层普通 for 贡献 Θ(n);T₁=Θ(n³)、T∞=Θ(n)、并行度 Θ(n²);直接并行内层会产生竞争。
- 原始内容:The span is T ∞ ( n ) = Θ( n ), because it follows a path down the tree of recursion for the parallel for loop starting in line 1, then down the tree of recursion for the parallel for loop starting in line 2, and then executes all n iterations of the ordinary for loop starting in line 3, resulting in a total span of Θ(lg n ) + Θ(lg n ) + Θ( n ) = Θ( n ). Thus the parallelism is Θ( n 3 )/Θ( n ) = Θ( n 2 ).