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

计算机科学与技术

证明： 令 T P * 为在具有 P 个处理器的机器上，一个最优调度器产生的运行时

间，令 T 1 和 T ∞ 为该计算的 work 和 span 。根据 work 法则和 span 法则（不

等式 27.2 和 27.3 ），得出：

T P * ≥ max(T 1 /P, T ∞ ) ，根据定理 27.1 ，有：

T P ≤ T 1 /P + T ∞

≤ 2*max(T 1 /P, T ∞ )

≤ 2* T P *

下一个推论告诉我们，对于任何多线程计算来所，随着 slackness 的增

长，贪婪式调度器都可以达到接近完全的线性加速。

推论 27.3

令 T P 为在一台具有 P 个处理器的理想并行计算机上，贪婪式调度器调度一个多

线程计算的运行时间，令 T 1 和 T ∞ 为该计算的 work 和 span 。那么如果 P <

< T 1 /T ∞ ，就有 T P ≈ T 1 /P （或者相等），也就是具有大约为 P 的加速因

子。

证明： 假设 P<< T 1 /T ∞ ，那么就有 T ∞ << T 1 /P ，因此根据定理 27.1 ，

有 T P ≤ T 1 /P + T ∞ 。根据 work 法则（ 27.2 ）得到 T P ≥ T 1 /P ，因此得出 T P ≈ T 1 /P （或者相等），加速因子为： T 1 /T P ≈ P 。

符号 << 表示“远小于”，但是“远小于”意味着多少呢？作为经验之谈，当 slackness 至少为 10 时（也就是说， parallelism 是处理器数目的 10 倍），