知识卡片

普通读书笔记卡 · 3673

串行归并限制并行归并排序扩容

理解等级:高级

即使两半递归排序并行,若顶层归并仍串行,最长依赖链仍是线性,工作量为n log n,并行度只有log n。

要扩容到更多处理器,必须降低归并步骤本身的跨度。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The two recursive calls in lines 5 and 7 run in parallel, and so its span is given by the recurrence T∞(n) = T∞(n/2) + Θ(n) = Θ(n), by case 1 of the master theorem. Thus the parallelism of P-NAIVE-MERGE-SORT is T1(n)/T∞(n) = Θ(lg n), which is an unimpressive amount of parallelism.

    参考来源

    - 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[65000,70000))。 - 结论依据:第26章 P-NAIVE-MERGE-SORT:两个递归排序并发,串行 MERGE 的工作与跨度均 Θ(n);T₁=Θ(n lg n),T∞(n)=T∞(n/2)+Θ(n)=Θ(n),并行度 Θ(lg n)。 - 原始内容:The two recursive calls in lines 5 and 7 run in parallel, and so its span is given by the recurrence T ∞ ( n ) = T ∞ ( n /2) + Θ( n ) = Θ( n ), by case 1 of the master theorem. Thus the parallelism of P-N AIVE -M ERGE -S ORT is T 1 ( n )/ T ∞ ( n ) = Θ(lg n ), which is an unimpressive amount of parallelism.