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

计算机科学与技术

span 就是每个 strand 具有自己独立处理器时的运行时间（也就是说，如果可用的处理器数目是无限的），用 T ∞ 来表示。

work 和 span 提供了在 P 个处理器上运行的多线程计算花费时间 T P 的下界： 在一个单位时间中，具有 P 个处理器的理想并行计算机最多能够完成 P

个单位工作，因此在 T P 时间内，能够完成最多 PT P 数量的工作。由于总

的工作为 T 1 ，因此我们有： PT P ≥ T 1 。两边同除以P 得到work 法则

（work law ） ：

T P ≥ T 1 /

P. (27.2)

具有 P 个处理器的理想并行计算机肯定无法快过具有无限数量处理器的

机器。换种说法，具有无限数量处理器的机器可以通过仅使用 P 个处理器的方法来仿真具有 P 个处理器的机器。因此，得到 span 法则（ spaw law ） ：

T P ≥ T ∞

. (27.3)

我们用比率 T 1 / T P 来定义在 P 个处理器上一个计算的加速因子（ sp

eedup ） ，它表示该计算在 P 个处理器上比在 1 个处理器上快多少倍。根据 work 法则， T P ≥ T 1 /P ，意味着 T 1 /T P ≤ P 。因此，在 P 个处理器上的