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

计算机科学与技术

图27.3 中展示了如何去分析span 。如果两个子计算被串行合并在一起，那么其组合的span 等于二者span 之和，如果它们被并行合并在一起，那么其组合的span 等于二者span 中较大的那一个。对于 P-FIB(n) 来说，第3 行中spawn 的P-FIB(n-1) 和第4 行中spawn 的P-FIB(n-2) 并行运行。因此，我们可以把P-FIB(n) 的span 表示为如下递归式：

T ∞ (n) = max(T ∞ (n-1), T ∞ (n-2)) + Θ(1)

= T ∞ (n-1) + Θ(1),

结果为： T ∞ (n) = Θ(n) 。

P-FIB(n) 的 parallelism 为 T 1 (n)/ T ∞ (n) = Θ( Φn /n) ，其随着n 增长的速度极快。因此，对 P-FIB(n) 来说， 即使在最大的并行计算机上，一个中等大小的n 值就足以获得接近完全的线性加速，因为该过程具有相当大的并行 slackness 。 并行循环

有许多算法，其包含的循环中的所有迭代都是可以并行执行的。我们将看到，可以使用 spawn 和 sync 关键字来并行化这种循环，不过如果能够直接指明这种循环的迭代可以并发执行的话，会更加方便一些。我们通过使用 parallel 并发关键字来在伪码中提供该功能，它位于 for 循环语句的 for 关键字之前。

我们以一个 n ×n 的矩阵A= （a ij ）乘以一个n 元向量x= （x j ）为例进行说明。相乘的结果为一个n 元向量y= （y i ），如下：

y i = ∑ n j=1 a ij x j ，