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

计算机科学与技术

就绪的 strands 少于 P 个，则称这个步骤为不完全步骤 ，调度器会把每个 strand 分配给独立的处理器。

根据 work 法则，在 P 个处理器上可以达到的最快运行时间为 T P = T 1 /P ，根据 span 法则，最好的情况是 T P = T ∞ 。下面的定理表明，因为贪婪式

调度器可以以这两个下界之和为其上界，所以其可被证明是一个好的调度器。

定理 27.1

在一台具有 P 个处理器的理想并行计算机上，对于一个 wrok 为 T 1 ， span 为 T ∞ 的多线程计算，贪婪调度器执行该计算的时间为：

T P ≤ T 1 / P + T ∞

. (27.4)

证明： 首先来考虑完全步骤。在每个完全步骤中， P 个处理器完成的工作总量为 P 。我们采用反证法，假设完全步骤的数目严格大于 └ T 1 / P ┘，那么完

全步骤所完成的工作总量至少为：

P*( └ T 1 / P ┘+1) = P └ T 1 / P ┘ + Ｐ

= T 1 －（ T 1 mod P ） + P ( 根据等式 3.8 得出 )

> T 1 ( 根据不等式 3.9 得出 ) 。