知识卡片

普通读书笔记卡 · 3672.b

并行斯特拉森降低工作但跨度同阶

理解等级:高级

斯特拉森的七个子乘积可以并发计算,每层矩阵加减保留对数级跨度。

跨度仍为 Θ(lg²n),并行度略低于八乘积版本,原因是总工作量更少;评价并行度时要同时比较工作和跨度。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第26章 并行算法 · 查看原书依据

      In this case, seven recursive calls execute in parallel, but since they all operate on matrices of the same size, we obtain the same recurrence (26.6) as we did for P-MATRIX-MULTIPLY-RECURSIVE, with solution Θ(lg2 n).

    参考来源

    - 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[60000,65000))。 - 结论依据:第26章“Parallelizing Strassen’s method”:七个 n/2 子乘积并发;工作 Θ(n^lg7),跨度沿用式(26.6)的 Θ(lg²n),故并行度 Θ(n^lg7/lg²n)。相对八乘积版本,降低的是工作,并非跨度阶。 - 原始内容:In this case, seven recursive calls execute in parallel, but since they all operate on matrices of the same size, we obtain the same recurrence (26.6) as we did for P-M ATRIX -M ULTIPLY -R ECURSIVE , with solution Θ(lg 2 n ). - 工作量旁证(文本字符[60000,65000)):Since the serial projection is the same as the original serial algorithm, the work is just the running time of the serial projection, namely, Θ( n lg 7 ).