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

计算机科学与技术

法则，在 P 个处理器上的加速因子满足 T 1 /T P ≤ T 1 /T ∞ <P 。事实上，随着

slackness 从 1 降低到 0 ，计算的加速因子就越来越远离完全线性加速。如果 slackness 大于 1 ，那么单个处理器上工作量就成为限制约束。我们将看到，随着 slackness 从 1 开始增加，一个好的调度器可以越来越接近于完全线性加速。

调度

好的性能并不仅仅来自于对 work 和 span 的最小化，还必须能够高效地把 strands 调度到并行计算机的处理器上。我们的多线程编程模型中没有提供指定哪些 strands 运行在哪些处理器上的方法。而是依赖于并发平台的调度器来把动态展开的计算映射到单独的处理器上。事实上，调度器只把 strands 映射到静态线程，由操作系统来把线程调度到处理器上，不过这个额外的间接层次并不是理解调度原理所必需的。我们可以就认为是由并发平台的调度器直接把 strands 映射到处理器的。

多线程调度器必须能够在事先不知道 strands 何时被 spawn 以及何时完成的情况下进行计算的调度——它必须在线（ on-line ） 操作。此外，一个好的调度器是以分散的（ distributed ）形式运转的，其中实现调度器的线程互相协作以均衡计算负载。好的在线、分散式调度器确实存在，不过对它们进行分析是非常困难的。

因此，为了简化分析工作，我们将研究一个在线、集中式（ centralized ） 调度器，在任意时刻，它都知道计算的全局状态。我们将特别分析贪婪式调度器 ，它们会在每个执行步骤中把尽可能多的 strands 分配给处理器。如果在一个执行步骤中有至少 P 个 strands 可以执行，那么就称这个步骤为完全步骤 ，贪婪调度器会把就绪 strands 中的任意 P 个分配给处理器。否则，如果