算法导论第三版新增27章中文版(18)

计算机科学与技术

通常就足以得到很高的加速因子。贪婪调度器的上界不等式（ 27.4 ）中的 span 项小于单处理器 work 项的 10% ，这对于绝大多数实际应用情况而言已经足够好了。例如，如果一个计算仅在 10 个或者 1000 个处理器上运行，那么去说 1,000,000 的 parallelism 比 10,000 更好是没有意义的，即使它们之间有 100 倍的差异。正如问题 27-2 所表明的那样，有时通过降低计算的最大并行度，所得到的算法要好于关注其他问题所得到算法，并且还能在相当数目的处理器上伸缩良好。

多线程算法分析

现在，我们已经拥有了分析多线程算法的所有工具，并且对于在不同数目处理器上的运行时间也有了个不错的边界。对于 work 的分析相对简单，因为只不过就是分析一个普通的串行算法的运行时间（也就是多线程算法的串行化版本），对此，我们早已熟悉，这正是本书大部分内容所讲的东西！对 span 的分析会更有趣一些，一旦掌握了其中的诀窍，通常也不难。我们将以 P-FIB 程序为例来研究一些基本概念。

分析 P-FIB(n) 的 work T 1 (n) 没什么难度，因为我们已经做过了。原

始的 FIB 过程就是 P-FIB 的串行化版本，因此 T 1 (n)= T(n)= Θ( Φn ) （基于等式 27.1 ）。