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

计算机科学与技术

虽然上面的 FIB 过程对计算 Fibonacci 数来说是一种糟糕的方法，但是在说明多线程算法分析中的关键概念方面，它却是一个好例子。在 FIB(n) 中，第 3 行、第 4 行对 FIB(n-1) 和 FIB(n-2) 的两个递归调用彼此之间相互独立：它们可以按照任意顺序被调用，相互之间也不会有任何影响。因此，这两个递归调用是可以并行运行的。

我们在伪代码中增加了并发关键字 spawn 和 sync 来指示并行属性。下面是采用动态多线程技术重写的 FIB 过程：

P-FIB(n)

1 if n ≤ 1

2 return n

3 else x = spawn P-FIB(n-1)

4 y = P-FIB(n-2)

5 sync

6 return x+y

请注意，如果我们从 P-FIB 中删除掉并发关键字 spawn 和 sync ，剩下的代码和 FIB 完全一样（除了开始和两处递归调用处的过程名字被更改之外）。我们把多线程算法的串行化 定义为：删除了多线程关键字 spawn 、 sync 以及 parallel （并行循环中会用到）后所得到的串行算法。事实上，我们的多线程伪代码具有一个不错的属性——其串行化版本就是解决相同问题的常用串行伪代码。