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

计算机科学与技术

因此， P 个处理器所完成的工作比所需要的还多，矛盾，所以完全步骤的数目最多为 └ T 1 / P ┘。

现在，考虑一个不完全步骤。我们用 G 来表示整个计算的dag ，不失一般性，假设每个strand 都花费单位时间。（我们可以把超过单位时间的strand 用一串单位时间strand 来替代）。令G’ 为在该不完全步骤开始时G 已经执行的部分构成的子图，令G” 为在该不完全步骤完成后G 中还没有执行的部分构成的子图。dag 中最长的路径一定起始于入度（ in-degree ）为0 的顶点。由于贪婪调度器中的一个不完全步骤会把G’ 中所有入度为0 的 strands 全部执行，因此 G ”的最长路径长度一定不 G ’中的最长路径小 1 。换句话说，一个不完全步骤会把还没有执行的 dag 的 span 减 1 。所以，非完全步骤的数目最多为 T ∞ 。

由于每个步骤要么是完全的，要么是不完全的，因此定理得证。

下面是定理 27.1 的推论，说明了贪婪式调度器总是具有好的调度性能。

推论 27.2

在一台具有 P 个处理器的理想并行计算机上，任何由贪婪式调度器调度的多线程计算的运行时间 T P ，不会超过最优时间的 2 倍。