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

计算机科学与技术

程计算的指令相互交织形成了一个线性的顺序来保持计算 bag 中的偏序关系。这个顺序和调度有关，因此在程序的每次运行可能互不相同，但是每次运行时，我都可以假设指令是按照和计算 bag 一致的某个线性顺序执行的，并基于这个假设来理解其行为。

除了对语义进行假设外，还可以对理想并行计算机模型做一些性能方面的假设。特别地，我们假设机器中的每个处理器具有相同的计算能力，并忽略掉调度的开销。虽然后面这个假设听起来过于乐观，不过在实践中，对于具有充分“ parallelism （并行度）”（后面会准确定义这个术语）的算法来说，调度的开销通常是极其小的。

性能度量

我们可以使用两个度量：“ work ”和“ span ”，来衡量多线程算法的理论效率。 work 指的是在一个处理器上完成全部的计算所需要的总时间。也就是说， work 是所有 strand 执行时间的总和。如果计算 dag 中每个 strand 都花费单位时间，那么其 work 就是 dag 中顶点的数目。 span 是在沿 dag 中任意路径执行 strand 所花费的最长时间。同样，如果 dag 中每个 strand 都花费单位时间，那么其 span 就等于 dag 中最长路径（也就是关键路径 ）上顶点的数目。（在 24.2 节中讲过，可以在 Θ (V+E) 时间内找到 dag G=(V,E) 的一条关键路径 ）。例如，图 27.2 中的计算 dag 共有 17 个顶点，其中 8 个在关键路径上，因此，如果每个 strand 花费单位时间的话，那么其 work 是 17 个单位时间，其 span 为 8 个单位时间。

多线程计算的实际运行时间不仅依赖于其 work 和 span ，还和可用处理器的数目以及调度器向处理器分配 strand 的策略有关。我们用下标 P 来表示一个在 P 个处理器上的多线程计算的运行时间。比如，我们用 T P 来表示算法在

P 个处理器上的运行时间。 work 就是在一个处理器上的运行时间，也就是 T 1 。