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

计算机科学与技术

该模型符合并行计算实践的演化方向。越来越多的并发平台开始支持动态多线程

技术的不同变种，包括 Cilk [51, 118], Cilk++ [72], OpenMP [60], Task Parallel Library [230], and Threading Building Blocks [292] 。

在 27.1 小节中，我们会介绍动态多线程模型，以及有关 work 、 span 以及 parallelism 的度量方法，我们会使用该度量去分析多线程算法。在 27.2 小节中，我们将研究如何使用多线程来进行矩阵相乘，在 27.3 小节中，我们将处理一个更为困难的问题：归并排序的多线程算法

27.1 动态多线程技术基础

我们将以递归地计算 Fibonacci 数为例来开始对于动态多线程技术的探索历程。先来回忆一下 3.22 小节中给出的 Fibonacci 数的递归定义：

F0 = 0,

F1 = 1,

Fi = Fi-1 + Fi-2 for i ≥ 2.

下面是一个简单的用于计算第 n 个 Fibonacci 数的递归串行算法：