知识卡片
递归并行矩阵乘法具有高并行度
八个子矩阵乘法可并发;每层额外初始化与合并的跨度为对数级,因此总跨度为对数平方级。工作量仍为三次方,得到三次方除以对数平方的并行度。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
Because the eight parallel recursive spawns all execute on matrices of the same size, the maximum span for any recursive spawn is just the span of a single one of them, or M∞(n/2).
参考来源
- 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[55000,65000))。
- 结论依据:第26章 P-MATRIX-MULTIPLY-RECURSIVE 第5–7、9–16、18–20行:八个同规模递归调用并发;M₁(n)=8M₁(n/2)+Θ(n²)=Θ(n³),图 Art_P837 式(26.6)为 M∞(n)=M∞(n/2)+Θ(lg n),故 M∞=Θ(lg²n)、并行度 Θ(n³/lg²n)。
- 原始内容:Because the eight parallel recursive spawns all execute on matrices of the same size, the maximum span for any recursive spawn is just the span of a single one of them, or M ∞ ( n /2).
- 公式图核读:`OEBPS/images/Art_P837.jpg` 的式(26.6)为 M∞(n)=M∞(n/2)+Θ(lg n)。
- 工作量旁证(文本字符[55000,60000)):The recursive case allocates and zeros the temporary matrix D in Θ( n 2 ) time, partitions in Θ(1) time, performs eight recursive multiplications of n /2 × n /2 matrices, and finishes up with the Θ( n 2 ) work from adding two n × n matrices. Thus the work outside the spawned recursive calls is Θ( n 2 ), and the recurrence for the work M 1 ( n ) becomes M 1 ( n ) = 8 M 1 ( n /2) + Θ( n 2 ) = Θ( n 3 ) by case 1 of the master theorem (Theorem 4.1).