知识卡片
串行归并限制并行归并排序扩容
即使两半递归排序并行,若顶层归并仍串行,最长依赖链仍是线性,工作量为n log n,并行度只有log n。
要扩容到更多处理器,必须降低归并步骤本身的跨度。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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.