多线程算法（完整版）
——算法导论第
3
版新增第
27
章
Thomas
H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
邓辉
译
原文：
http://software.intel.com/sites/products/documentation/cilk/book_chapter.pdf
本书中的主要算法都是顺序算法
，适合于运行在每次只能执行一条指令的单处理器计算机上。在本章中，我们要把算法模型转向并行算法
，它们可以运行在能够同时执行多条指令的多处理器计算机中。我们将着重探索优雅的动态多线程算法模型，该模型既有助于算法的设计和分析，同时也易于进行高效的实现。
并行计算机（就是具有多个处理单元的计算机）已经变得越来越常见，其在价格和性能方面差距甚大。相对比较便宜的有片上多处理器
桌面电脑和笔记本电脑，其中包含着一个多核集成芯片，容纳着多个处理“核”，每个核都是功能齐全的处理器，可以访问一个公共内存。价格和性能都处于中间的是由多个独立计算机（通常都只是些
PC
级的电脑）组成的集群，通过专用的网络连接在一起。价格最高的是超级计算机，它们常常采用定制的架构和网络以提供最高的性能（每秒执行的指令数）。
多处理器计算机已经以各种形态存在数十年了。计算社团早在计算机科学形成的初期就选定采用随机存取的机器模型来进行串行计算，但是对于并行计算来说，却没有一个公认的模型。这主要是因为供应商无法在并行计算机的架构模型上达成一致。比如，有些并行计算机采用共享内存
，其中每个处理器都可以直接访问内存的任何位置。而有些并行计算机则使用分布式内存
，每个处理器的内存都是私有的，要想去访问其他处理器的内存，必须得向其他处理器发送显式的消息。不过，随着多核技术的出现，新的笔记本和桌面电脑目前都成为共享内存的并行计算机，趋势似乎倒向了共享内存多处理这边。虽然一切还是得由时间来证明，不过我们在章中仍将采用共享内存的方法。
对于片上多处理器和其他共享内存并行计算机来说，使用静态线程
是一种常见的编程方法，该方法是一种共享内存“虚拟处理器”或者线程的软件抽象。每个线程维持着自己的程序计数器，可以独立地执行代码。操作系统把线程加载到一个处理器上让其运行，并在其他线程需要运行时将其换下。操作系统允许程序员创建和销毁线程，不过这些操作的开销较大。因此，对于大多数应用来说，在计算期间线程是持久存在的，这也是为何称它们为“静态”的原因。
遗憾的是，在共享内存并行计算机上直接使用静态线程编程非常的困难且易于出错。原因之一是，为了使每个线程所承担的负载大致相当，就需要动态地在线程间分配工作，而这是一项极其复杂的任务。除了那些最简单的应用之外，程序员都得使用复杂的通信协议来实现调度器以对工作进行均衡。这种状况导致了并发平台
的出现，并发平台就是一个用来协调、调度、管理并行计算资源的软件平台。有些并发平台被构建成运行时库，有些则提供了具有编译器和运行时支持的全功能的并行语言。
动态多线程编程
动态多线程
是一种重要的并发平台，也是本章中要采用的模型。使用动态多线程平台，程序员可以无需关心通信协议、负载均衡以及其他静态线程编程中的复杂问题，只要明确应用中的并行性即可。该并发平台中有一个调度器，用来自动均衡计算的负载，因此大大地简化了程序员的工作。动态多线程环境所具有的功能目前还在不断的演化之中，不过基本上都包含有两个功能：嵌套并行以及并行循环。嵌套并行就是可以去“
spawn
”一个子例程，并且使得调用者和子例程能够同时执行。并行循环和普通的
for
循环相似，只是循环中的迭代可以并发地执行。
这两个功能是我们将要在本章中研究的动态多线程模型的基础。该模型的一个关键特征为，程序员只需要指明计算中的逻辑并行性，底层并发平台中的线程会自动调度和均衡计算。我们将研究基于这种模型所编写的多线程算法，以及底层并发平台能够高效进行计算调度的原理。
动态多线程模型具有如下几个重要优点：
l
它是串行编程模型的简单扩展。只需在伪码中增加
3
个“并发”关键字：
parallel
，
spawn
以及
sync
，就可以描述多线程算法。此外，如果从多线程伪码中去掉这些关键字，就可以得到针对相同问题的串行伪代码，我们称之为“串行化”一个多线程算法。
l
它提供了一种理论上清晰的、基于“
work
（工作总量）”和“
span
（跨度）”这两个概念量化
parallelism
（并行度）的方法。
l
许多多线程算法所涉及的嵌套并行可以从分治范型自然得出。此外，正如串行分治算法可以容易地通过递归关系进行分析一样，多线程算法也是如此。
l
该模型符合并行计算实践的演化方向。越来越多的并发平台开始支持动态多线程技术的不同变种，包括
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
数的递归串行算法：
FIB(n)
1
if n
≤
1
2
return n
3
else x = FIB(n-1)
4
y = FIB(n-2)
5
return x+y
如果要计算很大的
Fibonacci
数，是不能使用该算法的，因为其中有大量的重复计算。图
27.1
展示了在计算
F6
时所创建的递归过程实例树。其中，对于对于
FIB(6)
的调用会递归地调用
FIB(5)
和
FIB(4)
。而对
FIB(5)
的调用又会去调用
FIB(4)
。这两个
FIB(4)
实例返回的结果完全相同（
F4
=3
）。由于
FIB
并没有去记住这些结果，因此对于
FIB(4)
的第二次调用重复了第一次调用的工作。
我们用
T(n)
表示
FIB(n)
的运行时间。由于
FIB(n)
包含了两个递归调用和其他一些常数时间的工作，因此得到如下递归方程：
T(n) = T(n-1) + T(n-2) +
Θ(1)
我们可以采用替换方法得到该方程的解：
T(n) =
Θ(
Fn)
。作为归纳假设，我们假设
T(n
)
≤aFn-b
，其中a>1
，b>0
且都为常数。通过替换，我们得到：
T(n)
≤ （aF
n-1
-b
）+ (aF
n-2
-b
）+
Θ(1)
=
a(
F
n-1 +
F
n-2
）- 2b +
Θ(1)
=
aF
n
-b – (b-
Θ(1))
≤
aF
n
-b
如果我们在选择b
时让其大到足以支配
Θ(1)
中的常量。那么我们接着可以把a
选得大到足以满足初始条件。其分析边界为：
T(n) =
Θ(
Φn
),
(27.1)
其中，
Φ=(1+sqrt(5))/2
是黄金分割率，由等式(3.25)
得出。由于Fn
随n
成指数级增长，因此在计算
Fibonacci
数时，该过程非常低效。（问题
31-3
中给出了快得多的方法）。
虽然上面的
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
（并行循环中会用到）后所得到的串行算法。事实上，我们的多线程伪代码具有一个不错的属性——其串行化版本就是解决相同问题的常用串行伪代码。
在过程调用前面加上
spawn
关键字时，就意味着嵌套并行
，如第
3
行中所示。
spawn
的语义和普通的过程调用不同，执行
spawn
的过程实例（
parent
）可以和被
spawn
出来的子例程（
child
）并行执行，而不像串行执行中那样去等待
child
执行完成。在本例中，当
child
在计算
P-FIB(n-1)
时，
parent
可以并行地去计算第
4
行中的
P-FIB(n-2)
。由于
P-FIB
过程是递归的，因此这两个对其自身进行调用的子例程就创建了嵌套的并行性，对其
children
来说同样如此，于是就产生了一个潜在的巨大子计算树，每个子计算都并行执行。
不过，关键字
spawn
并不是一定要求过程必须和其
child
并发执行，只是表示可以
并发执行。并发关键字表达了计算中的逻辑并行性
，表明了计算中的哪些部分可以并行的运行。哪些子计算实际上是并发运行的是由调度器
在运行时决定的，在计算进行中，调度器把子计算分配给可用的处理器。稍后，我们会讨论调度器的原理。
一个过程，仅当其执行了
sync
语句时（如第
5
行），才能够安全地使用由其
spawn
的
children
例程的返回值。关键字
sync
表示过程必须等待，直到其所
spawn
的
children
全部完成计算，才能够继续
sync
后面的语句。在
P-FIB
过程中，必须要在
return
语句（第
6
行）前增加
sync
语句，从而避免出现在
x
还没有被计算前就进行
x+y
操作的异常情况。除了
sync
语句所提供的显式同步之外，每个过程都会在其返回前隐式地执行一条
sync
语句，这样可以保证在其终止前，其所有的
children
都已经终止。
多线程执行模型
把多线程计算（由一个代表多线程程序的处理器执行的运行时指令集）看做是一个有向无环图
G=
（
V, E
）是很有帮助的，我们称其为计算
dag
（
directed acyclic graph
）
。图
27.2
中给出了一个示例，其中的计算
dag
来自计算
P-FIB(4)
。从概念层面来讲，
V
中的顶点都是指令，
E
中边则表示指令间的依赖关系，
(u,v
)
∈
E
表示指令
u
必须在指令
v
之前执行。为了方便起见，如果一条指令链中不包含任何并行控制语句（没有
spawn
、
sync
以及被
spawn
例程中
return
——显式的
return
语句或者过程执行完后的隐式
return
），我们就把它们组成一组，形成一个
strand
，每个
strand
都表示一条或者多条指令。涉及并行控制的指令不包括在
strand
中，但是会出现在
dag
结构中。例如，如果一个
strand
有两个后继，那么其中之一必须得被
spawn
出来，如果一个
strand
有多个前驱，就表示前驱因为一条
sync
语句被合并在一起。因此，一般来说，
V
形成了
strand
集合，而有向边集合
E
则表示由并行控制产生的
strand
间的依赖关系。如果
G
中有一个从
strand u
到
strand v
的有向路径，那么我们就说这两个
strands
是（逻辑上）串行的。否则就称其为（逻辑上）并行的。
我们可以把一个多线程计算表示为由内嵌于一棵过程实例树中的
strands
组成的有向无环图。比如，图
27.1
中展示了
P-FIB(6)
的过程实例树，其中没有显示
strands
细节。图
27.2
放大了该树中的一个片段，展现了构成每个过程的
strands
。所有连接
strands
的有向边要么运行于一个过程之中，要么沿着过程树中的无向边运行。
我们可以把计算
dag
的边进行分类，以表示出不同
strands
间依赖关系的种类。在图
27.2
中，沿水平方向连接
strand u
和其同一个过程实例中的后继
u’
的边被称为
continuation edage
（继续边）
（
u
，
u’
）。当
strand u spawn
了
strand v
时，
dag
中就包含了另一个
spawn edge
(u,v)
，在图中显示为指向下的边。表示正常过程调用的
call edge
也指向下。
Strand u spawn
了
strand v
和
u
调用
v
的差别在于：
spawn
会产生一条从
u
到其同一过程中后继
u’
的水平方向的
continuation edge
，意味着
u’
可以和
v
同时执行，而调用不会产生出这样的边。当
strand u
返回到其调用过程，而
x
是该调用过程中紧跟着下一条
sync
语句的
strand
时，计算
dag
中就会包含
return edge
(u,x)
，指向上方。计算从一个
initial strand
开始执行（图
27.2
中被标记为
P-FIB(4)
的过程中的黑色顶点），并以一个
final strand
结束（被标记为
P-FIB(4)
的过程中的白色顶点）。
我们将在理想并行计算机
上研究并行算法的执行，该理想并行计算机由一组处理器和一个顺序一致性
的共享内存组成。顺序一致性的意思是，虽然在实际上多个处理器可以同时对共享内存执行众多的存取操作，但是其产生的结果和在每一步中都只有来自一个处理器的一条指令被执行所产生的完全一样。也就是说，内存的行为就像是按照某个全局的线性顺序来执行指令，该全局顺序保证了每个处理器基于独立的顺序来发出自己的指令。对于动态多线程计算来说，计算是被并发平台自动调度到处理器上的，共享内存的工作方式看起来就像是多线程计算的指令相互交织形成了一个线性的顺序来保持计算
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
。
span
就是每个
strand
具有自己独立处理器时的运行时间（也就是说，如果可用的处理器数目是无限的），用
T
∞
来表示。
work
和
span
提供了在
P
个处理器上运行的多线程计算花费时间
T
P
的下界：
l
在一个单位时间中，具有
P
个处理器的理想并行计算机最多能够完成
P
个单位工作，因此在
T
P
时间内，能够完成最多
PT
P
数量的工作。由于总的工作为
T
1
，因此我们有：
PT
P
≥
T
1
。两边同除以P
得到work
法则（work law
）
：
T
P
≥
T
1
/P.
(27.2)
l
具有
P
个处理器的理想并行计算机肯定无法快过具有无限数量处理器的机器。换种说法，具有无限数量处理器的机器可以通过仅使用
P
个处理器的方法来仿真具有
P
个处理器的机器。因此，得到
span
法则（
spaw law
）
：
T
P
≥ T
∞
.
(27.3)
我们用比率
T
1
/ T
P
来定义在
P
个处理器上一个计算的加速因子（
speedup
）
，它表示该计算在
P
个处理器上比在
1
个处理器上快多少倍。根据
work
法则，
T
P
≥
T
1
/P
，意味着
T
1
/T
P
≤
P
。因此，在
P
个处理器上的加速因子最多为
P
。当加速因子和处理器的数目成线性关系时，也就是说，当
T
1
/T
P
=
Θ
P
时，该计算具有线性加速
的性质，当
T
1
/T
P
=P
时，称其为完全的线性加速
。
我们把
work
和
span
的比率
T
1
/T
∞
定义为多线程计算的
parallelism
（并行度）
。可以从三个角度来理解
parallelism
。作为一个比率，
parallelism
表示了对于关键路径上的每一步，能够并行执行的平均工作量。作为一个上限，
parallelism
给出了在具有任何数量处理器的机器上，能达到的最大可能加速。最后，也是最重要的，在达成完全线性加速的可能性上，
parallelism
提供了一个在限制。具体地说，就是一旦处理器的数目超过了
parallelism
，那么计算就不可能达成完全线性加速。为了说明最后一点，我们假设
P > T
1
/T
∞
，根据
span
法则，加速因子满足
T
1
/T
P
≤
T
1
/T