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

计算机科学与技术

加速因子最多为 P 。当加速因子和处理器的数目成线性关系时，也就是说，当 T 1 /T P = Θ P 时，该计算具有线性加速 的性质，当 T 1 /T P =P 时，称其为完

全的线性加速 。

我们把 work 和 span 的比率 T 1 /T ∞ 定义为多线程计算的 paralleli

sm （并行度） 。可以从三个角度来理解 parallelism 。作为一个比率， parallelism 表示了对于关键路径上的每一步，能够并行执行的平均工作量。作为一个上限， parallelism 给出了在具有任何数量处理器的机器上，能达到的最大可能加速。最后，也是最重要的，在达成完全线性加速的可能性上， parallelism 提供了一个在限制。具体地说，就是一旦处理器的数目超过了 parallelism ，那么计算就不可能达成完全线性加速。为了说明最后一点，我们假设 P > T 1 /T ∞ ，根据 span 法则，加速因子满足 T 1 /T P ≤ T 1 /T ∞ <P 。此外，如果理想并行

计算机的处理器数目 P 大大超过了 parallelism （也就是说，如果 P >> T 1 /T ∞ ），那么 T 1 /T P <<P ，这样，加速因子就远小于处理器的数目。换句话说，

处理器的数目超过 parallelism 越多，就越无法达成完全加速。

例如，我们来看看图 27.2 中 P-FIB(4) 的计算过程，并假设每个 strand 花费单位时间。由于 work T 1 =17 ， span T ∞ =8 ，因此 parallelism T 1 /T ∞ =17/8=2.125 。从而，无论我们用多少处理器来执行该计算，都无法获得 2

倍以上的加速因子。不过，对于更大一些的输入来说， P-FIB(n) 会呈现出更大的 parallelism 。

我们把在一台具有 P 个处理器的理想并行计算机上执行多线程算法的并行 slackness （闲置因子） 定义为： (T 1 /T ∞ )/P = T 1 /(PT ∞ ) ，也就

是计算的 parallelism 超过机器处理器数目的倍数因子。因此，如果 slackness 小于1 ，那么就不能达成完全的线性加速，因为 T 1 /(PT ∞ )<1 ，根据 span