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

计算机科学与技术

多线程算法（完整版）

——算法导论第 3 版新增第 27 章

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Ste

in

邓辉 译

原文： /sites/products/documentation/cilk/boo

k_chapter.pdf

本书中的主要算法都是顺序算法 ，适合于运行在每次只能执行一条指令的单处理器计算机上。在本章中，我们要把算法模型转向并行算法 ，它们可以运行在能够同时执行多条指令的多处理器计算机中。我们将着重探索优雅的动态多线程算法模型，该模型既有助于算法的设计和分析，同时也易于进行高效的实现。

并行计算机（就是具有多个处理单元的计算机）已经变得越来越常见，其在价格和性能方面差距甚大。相对比较便宜的有片上多处理器 桌面电脑和笔记本电脑，其中包含着一个多核集成芯片，容纳着多个处理“核”，每个核都是功能齐全的处理器，可以访问一个公共内存。价格和性能都处于中间的是由多个独立计算机（通常都只是些 PC 级的电脑）组成的集群，通过专用的网络连接在一起。价格最高的是超级计算机，它们常常采用定制的架构和网络以提供最高的性能（每秒执行的指令数）。

计算机科学与技术

多处理器计算机已经以各种形态存在数十年了。计算社团早在计算机科学形成的初期就选定采用随机存取的机器模型来进行串行计算，但是对于并行计算来说，却没有一个公认的模型。这主要是因为供应商无法在并行计算机的架构模型上达成一致。比如，有些并行计算机采用共享内存 ，其中每个处理器都可以直接访问内存的任何位置。而有些并行计算机则使用分布式内存 ，每个处理器的内存都是私有的，要想去访问其他处理器的内存，必须得向其他处理器发送显式的消息。不过，随着多核技术的出现，新的笔记本和桌面电脑目前都成为共享内存的并行计算机，趋势似乎倒向了共享内存多处理这边。虽然一切还是得由时间来证明，不过我们在章中仍将采用共享内存的方法。

对于片上多处理器和其他共享内存并行计算机来说，使用静态线程 是一种常见的编程方法，该方法是一种共享内存“虚拟处理器”或者线程的软件抽象。每个线程维持着自己的程序计数器，可以独立地执行代码。操作系统把线程加载到一个处理器上让其运行，并在其他线程需要运行时将其换下。操作系统允许程序员创建和销毁线程，不过这些操作的开销较大。因此，对于大多数应用来说，在计算期间线程是持久存在的，这也是为何称它们为“静态”的原因。

遗憾的是，在共享内存并行计算机上直接使用静态线程编程非常的困难且易于出错。原因之一是，为了使每个线程所承担的负载大致相当，就需要动态地在线程间分配工作，而这是一项极其复杂的任务。除了那些最简单的应用之外，程序员都得使用复杂的通信协议来实现调度器以对工作进行均衡。这种状况导致了并发平台 的出现，并发平台就是一个用来协调、调度、管理并行计算资源的软件平台。有些并发平台被构建成运行时库，有些则提供了具有编译器和运行时支持的全功能的并行语言。

动态多线程编程

计算机科学与技术

动态多线程 是一种重要的并发平台，也是本章中要采用的模型。使用动态多线程平台，程序员可以无需关心通信协议、负载均衡以及其他静态线程编程中的复杂问题，只要明确应用中的并行性即可。该并发平台中有一个调度器，用来自动均衡计算的负载，因此大大地简化了程序员的工作。动态多线程环境所具有的功能目前还在不断的演化之中，不过基本上都包含有两个功能：嵌套并行以及并行循环。嵌套并行就是可以去“ spawn ”一个子例程，并且使得调用者和子例程能够同时执行。并行循环和普通的 for 循环相似，只是循环中的迭代可以并发地执行。

这两个功能是我们将要在本章中研究的动态多线程模型的基础。该模型的一个关键特征为，程序员只需要指明计算中的逻辑并行性，底层并发平台中的线程会自动调度和均衡计算。我们将研究基于这种模型所编写的多线程算法，以及底层并发平台能够高效进行计算调度的原理。

动态多线程模型具有如下几个重要优点： 它是串行编程模型的简单扩展。只需在伪码中增加 3 个“并发”关键字： paral

lel ， spawn 以及 sync ，就可以描述多线程算法。此外，如果从多线程伪码中去掉这些关键字，就可以得到针对相同问题的串行伪代码，我们称之为“串行化”一个多线程算法。

它提供了一种理论上清晰的、基于“ work （工作总量）”和“ span （跨度）”

这两个概念量化 parallelism （并行度）的方法。

许多多线程算法所涉及的嵌套并行可以从分治范型自然得出。此外，正如串行分

治算法可以容易地通过递归关系进行分析一样，多线程算法也是如此。

计算机科学与技术

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

技术的不同变种，包括 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 的下界： 在一个单位时间中，具有 P 个处理器的理想并行计算机最多能够完成 P

个单位工作，因此在 T P 时间内，能够完成最多 PT P 数量的工作。由于总

的工作为 T 1 ，因此我们有： PT P ≥ T 1 。两边同除以P 得到work 法则

（work law ） ：

T P ≥ T 1 /

P. (27.2)

具有 P 个处理器的理想并行计算机肯定无法快过具有无限数量处理器的

机器。换种说法，具有无限数量处理器的机器可以通过仅使用 P 个处理器的方法来仿真具有 P 个处理器的机器。因此，得到 span 法则（ spaw law ） ：

T P ≥ T ∞

. (27.3)

我们用比率 T 1 / T P 来定义在 P 个处理器上一个计算的加速因子（ sp

eedup ） ，它表示该计算在 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 ∞ 定义为多线程计算的 paralleli

sm （并行度） 。可以从三个角度来理解 parallelism 。作为一个比率， parallelism 表示了对于关键路径上的每一步，能够并行执行的平均工作量。作为一个上限， parallelism 给出了在具有任何数量处理器的机器上，能达到的最大可能加速。最后，也是最重要的，在达成完全线性加速的可能性上， parallelism 提供了一个在限制。具体地说，就是一旦处理器的数目超过了 parallelism ，那么计算就不可能达成完全线性加速。为了说明最后一点，我们假设 P > T 1 /T ∞ ，根据 span 法则，加速因子满足 T 1 /T P ≤ T 1 /T ∞ <P 。此外，如果理想并行

计算机的处理器数目 P 大大超过了 parallelism （也就是说，如果 P >> T 1 /T ∞ ），那么 T 1 /T P <<P ，这样，加速因子就远小于处理器的数目。换句话说，

处理器的数目超过 parallelism 越多，就越无法达成完全加速。

例如，我们来看看图 27.2 中 P-FIB(4) 的计算过程，并假设每个 strand 花费单位时间。由于 work T 1 =17 ， span T ∞ =8 ，因此 parallelism T 1 /T ∞ =17/8=2.125 。从而，无论我们用多少处理器来执行该计算，都无法获得 2

倍以上的加速因子。不过，对于更大一些的输入来说， P-FIB(n) 会呈现出更大的 parallelism 。

我们把在一台具有 P 个处理器的理想并行计算机上执行多线程算法的并行 slackness （闲置因子） 定义为： (T 1 /T ∞ )/P = T 1 /(PT ∞ ) ，也就

是计算的 parallelism 超过机器处理器数目的倍数因子。因此，如果 slackness 小于1 ，那么就不能达成完全的线性加速，因为 T 1 /(PT ∞ )<1 ，根据 span

计算机科学与技术

法则，在 P 个处理器上的加速因子满足 T 1 /T P ≤ T 1 /T ∞ <P 。事实上，随着

slackness 从 1 降低到 0 ，计算的加速因子就越来越远离完全线性加速。如果 slackness 大于 1 ，那么单个处理器上工作量就成为限制约束。我们将看到，随着 slackness 从 1 开始增加，一个好的调度器可以越来越接近于完全线性加速。

调度

好的性能并不仅仅来自于对 work 和 span 的最小化，还必须能够高效地把 strands 调度到并行计算机的处理器上。我们的多线程编程模型中没有提供指定哪些 strands 运行在哪些处理器上的方法。而是依赖于并发平台的调度器来把动态展开的计算映射到单独的处理器上。事实上，调度器只把 strands 映射到静态线程，由操作系统来把线程调度到处理器上，不过这个额外的间接层次并不是理解调度原理所必需的。我们可以就认为是由并发平台的调度器直接把 strands 映射到处理器的。

多线程调度器必须能够在事先不知道 strands 何时被 spawn 以及何时完成的情况下进行计算的调度——它必须在线（ on-line ） 操作。此外，一个好的调度器是以分散的（ distributed ）形式运转的，其中实现调度器的线程互相协作以均衡计算负载。好的在线、分散式调度器确实存在，不过对它们进行分析是非常困难的。

因此，为了简化分析工作，我们将研究一个在线、集中式（ centralized ） 调度器，在任意时刻，它都知道计算的全局状态。我们将特别分析贪婪式调度器 ，它们会在每个执行步骤中把尽可能多的 strands 分配给处理器。如果在一个执行步骤中有至少 P 个 strands 可以执行，那么就称这个步骤为完全步骤 ，贪婪调度器会把就绪 strands 中的任意 P 个分配给处理器。否则，如果

计算机科学与技术

就绪的 strands 少于 P 个，则称这个步骤为不完全步骤 ，调度器会把每个 strand 分配给独立的处理器。

根据 work 法则，在 P 个处理器上可以达到的最快运行时间为 T P = T 1 /P ，根据 span 法则，最好的情况是 T P = T ∞ 。下面的定理表明，因为贪婪式

调度器可以以这两个下界之和为其上界，所以其可被证明是一个好的调度器。

定理 27.1

在一台具有 P 个处理器的理想并行计算机上，对于一个 wrok 为 T 1 ， span 为 T ∞ 的多线程计算，贪婪调度器执行该计算的时间为：

T P ≤ T 1 / P + T ∞

. (27.4)

证明： 首先来考虑完全步骤。在每个完全步骤中， P 个处理器完成的工作总量为 P 。我们采用反证法，假设完全步骤的数目严格大于 └ T 1 / P ┘，那么完

全步骤所完成的工作总量至少为：

P*( └ T 1 / P ┘+1) = P └ T 1 / P ┘ + Ｐ

= T 1 －（ T 1 mod P ） + P ( 根据等式 3.8 得出 )

> T 1 ( 根据不等式 3.9 得出 ) 。

计算机科学与技术

因此， P 个处理器所完成的工作比所需要的还多，矛盾，所以完全步骤的数目最多为 └ T 1 / P ┘。

现在，考虑一个不完全步骤。我们用 G 来表示整个计算的dag ，不失一般性，假设每个strand 都花费单位时间。（我们可以把超过单位时间的strand 用一串单位时间strand 来替代）。令G’ 为在该不完全步骤开始时G 已经执行的部分构成的子图，令G” 为在该不完全步骤完成后G 中还没有执行的部分构成的子图。dag 中最长的路径一定起始于入度（ in-degree ）为0 的顶点。由于贪婪调度器中的一个不完全步骤会把G’ 中所有入度为0 的 strands 全部执行，因此 G ”的最长路径长度一定不 G ’中的最长路径小 1 。换句话说，一个不完全步骤会把还没有执行的 dag 的 span 减 1 。所以，非完全步骤的数目最多为 T ∞ 。

由于每个步骤要么是完全的，要么是不完全的，因此定理得证。

下面是定理 27.1 的推论，说明了贪婪式调度器总是具有好的调度性能。

推论 27.2

在一台具有 P 个处理器的理想并行计算机上，任何由贪婪式调度器调度的多线程计算的运行时间 T P ，不会超过最优时间的 2 倍。

计算机科学与技术

证明： 令 T P * 为在具有 P 个处理器的机器上，一个最优调度器产生的运行时

间，令 T 1 和 T ∞ 为该计算的 work 和 span 。根据 work 法则和 span 法则（不

等式 27.2 和 27.3 ），得出：

T P * ≥ max(T 1 /P, T ∞ ) ，根据定理 27.1 ，有：

T P ≤ T 1 /P + T ∞

≤ 2*max(T 1 /P, T ∞ )

≤ 2* T P *

下一个推论告诉我们，对于任何多线程计算来所，随着 slackness 的增

长，贪婪式调度器都可以达到接近完全的线性加速。

推论 27.3

令 T P 为在一台具有 P 个处理器的理想并行计算机上，贪婪式调度器调度一个多

线程计算的运行时间，令 T 1 和 T ∞ 为该计算的 work 和 span 。那么如果 P <

< T 1 /T ∞ ，就有 T P ≈ T 1 /P （或者相等），也就是具有大约为 P 的加速因

子。

证明： 假设 P<< T 1 /T ∞ ，那么就有 T ∞ << T 1 /P ，因此根据定理 27.1 ，

有 T P ≤ T 1 /P + T ∞ 。根据 work 法则（ 27.2 ）得到 T P ≥ T 1 /P ，因此得出 T P ≈ T 1 /P （或者相等），加速因子为： T 1 /T P ≈ P 。

符号 << 表示“远小于”，但是“远小于”意味着多少呢？作为经验之谈，当 slackness 至少为 10 时（也就是说， parallelism 是处理器数目的 10 倍），

计算机科学与技术

通常就足以得到很高的加速因子。贪婪调度器的上界不等式（ 27.4 ）中的 span 项小于单处理器 work 项的 10% ，这对于绝大多数实际应用情况而言已经足够好了。例如，如果一个计算仅在 10 个或者 1000 个处理器上运行，那么去说 1,000,000 的 parallelism 比 10,000 更好是没有意义的，即使它们之间有 100 倍的差异。正如问题 27-2 所表明的那样，有时通过降低计算的最大并行度，所得到的算法要好于关注其他问题所得到算法，并且还能在相当数目的处理器上伸缩良好。

多线程算法分析

现在，我们已经拥有了分析多线程算法的所有工具，并且对于在不同数目处理器上的运行时间也有了个不错的边界。对于 work 的分析相对简单，因为只不过就是分析一个普通的串行算法的运行时间（也就是多线程算法的串行化版本），对此，我们早已熟悉，这正是本书大部分内容所讲的东西！对 span 的分析会更有趣一些，一旦掌握了其中的诀窍，通常也不难。我们将以 P-FIB 程序为例来研究一些基本概念。

分析 P-FIB(n) 的 work T 1 (n) 没什么难度，因为我们已经做过了。原

始的 FIB 过程就是 P-FIB 的串行化版本，因此 T 1 (n)= T(n)= Θ( Φn ) （基于等式 27.1 ）。

计算机科学与技术

图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 ，

计算机科学与技术

i=1 ，2 ， ,n 。我们可以通过并行地计算y 的所有项来进行矩阵- 向量的乘法操作，如下：

MAT-VEC(A,x) 1 n = A.rows

2 令 y 为一个新的长度为 n 的向量

3 parallel for i = 1 to n

4 y i = 0

5 parallel for i = 1 to n

6 for j = 1 to n

7 y i = y i + a ij x j

8 return y

在这段代码中，第 3 行和第 5 行中的 parallel for 关键字表示这两个循环中的迭代都可以并发执行。编译器可以把 parallel for 循环实现为基于嵌套并行的分治式子例程。例如，第 5 到 7 行中的 parallel for 循环可以被实现为对 MAT-VEC-MAIN-LOOP(A,x,y,n,l,n) 的调用，子例程 MAT-VEC-MAIN-LOOP 是编译器生成的辅助子例程，如下：

MAT-VEC-MAIN-LOOP(A, x, y, n, i, i’)

1 if i == i’

2 for j = 1 to n

计算机科学与技术

3 y i = y i + a ij x j

4 else mid = └(i+i’)/2 ┘

5 spawn MAT-VEC-MAIN-LOOP(A, x, y, n, i, mid)

6 MAT-VEC-MAIN-LOOP(A, x, y, n, mid+1, i’)

7 sync

该代码递归地 spawn 循环中的前半部分迭代，使其和后半部分迭代并行执行，然后执行一条 sync 语句，创建了一棵二叉树式的执行过程，其中叶子为单独的循环迭代，如图 27.4 所示。

现在来计算对于 n ×n 矩阵， MAT-VEC 的 work T 1 (n) ，也就是计算

其串行化版本的运行时间，这个串行化版本可以通过把 parallel for 循环替换成普通的 for 循环得到。由此，我们得到 T 1 (n)= Θ(n2 ) ，因为第5 到7 行的两重嵌套循环所产生的平方级运行时间占支配地位。在这个分析中，我们忽略掉了实现并行循环的递归 spawn 的开销。事实上，和其串行化版本相比，递归spawn 的开销确

本文来源：https://www.bwwdw.com/article/tsu1.html