摘要

Java Streams 系列的第 4 期文章将解释决定并行处理的有效性的因素，从历史和技术角度分析它们。了解这些因素是最高效地使用 Streams 库实现并行执行的基础，下一期文章 会重点介绍如何将这些原则直接应用于 Streams。

前期部分文章请查看：

更多核心，而不是更快的核心

从 2002 年左右开始，芯片设计者用于实现性能指数级增长的技术开始枯竭。由于各种原因，进一步提高时钟频率变得不切实际，包括功耗和散热，而且在每个周期完成更多工作的技术（指令级并行性）所带来的收益也已开始出现滑坡。

摩尔定律 预言，可集成到一个晶片上的 晶体管 数量约每两年翻一番。当芯片设计者 2002 年遇到频率瓶颈 时，这并不是因为摩尔定律已失效；我们可以看到，晶体管数量仍然稳定地呈指数级增长。不过，虽然利用这种不断增加的晶体管预算来获得 更快核心 的能力已失去作用，但芯片设计者仍能使用这种不断增加的晶体管预算在单个晶片上放入 更多核心 。图 1 通过来自英特尔处理器的数据演示了这种趋势，这些数据标绘在一个对数标尺上。最顶部的（直）线表示晶体管数量的指数级增长，表示时钟频率、功耗和指令级 并行性 的线在 2002 年左右都表现出明显的趋平状态。

图 1. 英特尔 CPU 的晶体管数量和 CPU 性能（图像来源：Herb Sutter）

拥有更多核心可实现更高的功率效率（未被主动使用的核心可独立地中断电源），但这不一定等同于提供更高的程序性能 — 除非您可以保持所有核心都不停地执行有用的工作。诚然，如今的芯片并没有为我们提供摩尔定律所允许的核心数 — 主要是因为如今的软件无法富有成本效益地利用它们。

从并发到并行

几乎在整个计算历史中，并发性的目标都是大致相同的 （通过增加 CPU 利用率来提高性能），但技术（和性能度量）却已发生改变。在单核系统时代，并发性主要依靠的是异步性— 允许某个活动在等待 I/O 完成期间让出 CPU。异步性可提高响应速度（在后台活动执行期间不冻结 UI）和吞吐量（在等待 I/O 完成期间允许另一个活动使用 CPU）。在一些并发性模型（例如 Actors and Communicating Sequential Processes [CSP]）中，并发性模型影响着程序结构，但在大多数情况下（不论好坏），我们仅根据性能需要来使用并发性。

“影响并行性的有效性的因素包括问题本身、解决问题所使用的 算法 、对任务分解和调度的运行时支持，以及数据集的大小和内存位置。”

随着我们进入多核时代，并发性的主要应用是将工作负载分解为独立的、粗粒度的任务（比如用户请求），这样做的目的在于通过同时处理多个请求来增加吞吐量。这一次，Java 库获得了一些工具，比如线程池、旗语 (semaphore) 和 future，它们非常适合基于任务的并发性。

但是随着核心数量的不断增加，可能没有足够的 “自然发生的任务” 来让所有核心一直处于繁忙状态。随着可用核心数超过任务数，另一个性能目标就变得很诱人：使用多个核心更快完成单个任务来减少延迟。不是所有任务都能通过这种分解来轻松处理；最适合的任务是数据密集型的查询，其中的同一个操作会在大型的数据集上完成。

不幸的是，术语并发性 和并行性 没有标准定义，它们常常被（错误地）交替使用。在过去，并发性 描述的是 程序 的一个属性（程序结构所实现的合作计算活动的交互程度），而并行性 是程序的一个 执行 属性，描述事件实际同时发生的程度。（根据此定义，并发性是并行性的 潜在能力 。）这种区别在真实的并发执行主要停留在理论阶段时很有用，但随着时间的推移，有用性变得越来越低。

更多现代课程将并发性 描述为正确、高效地控制对共享资源的访问，而并行性 指的是使用更多资源更快地解决问题。构造线程安全的数据结构属于并发性范畴，通过锁、事件、旗语、协同程序或软件事务内存 (STM) 等 原语 实现。另一方面，并行性使用分区或分片等技术来使多个活动处理一项任务，而 没有 协调过程。

为什么这一区别很重要？毕竟，并发性和并行性的目标都是同时完成多件事。但是，应用这两种技术的轻松程度有着很大差别。使用锁等协调原语正确创建并发代码很难、容易出错且不自然。通过让每个工作者拥有自己的问题部分来处理问题，从而正确创建并行代码，这样做相对更简单、更安全且更自然。

并行性

尽管并行性的原理通常很简单，但难点在于知道 何时 使用它。严格地讲，并行性是一种优化；它是一种为一次特定计算使用更多资源的选择，以期更快获得答案，而您始终有权选择按顺序执行计算。不幸的是，使用更多资源并不能保证更快（甚至快速）获得答案。此外，如果并行性消耗了额外的资源却没有为我们带来收益（或负面收益），我们不应使用它。当然，收益高低取决于环境，所以没有统一的答案。但是我们拥有各种工具，可帮助评估在给定情形中能否有效使用并行性：分析、度量和性能需求。

本文主要介绍分析（和探索）哪些计算种类可以很好地并行化，哪些不能。但是，作为经验规则，除非您有理由相信并行性会带来提速， 而且 获得的提速依据性能需求具有实际意义，否则会优先使用顺序执行方法。（许多程序已足够快，所以优化它们所花的工作可更好地花在能创造更多价值的活动上，比如提高适用性或可靠性。）

可以用提速来度量并行性有效性，提速是并行运行时间与顺序运行时间的比率。选择并行性（假设它能带来提速）是对注重时间而不是 CPU 和功率利用率的谨慎选择。并行执行完成的工作始终比顺序执行的多，因为除了解决问题之外，它还必须分解问题，创建和管理描述子问题的任务，分派和等待这些任务，合并它们的结果。所以并行执行始终在顺序执行 “之后” 开始，希望通过规模经济来补偿最初的落后。

要让并行性成为更好的选择，必须综合考虑多个方面。首先我们需要一个允许采用并行解决方案的问题 — 不是所有问题都允许采用并行解决方案。然后，我们需要实现利用了内在并行性的解决方案。我们需要确保用来实现并行性的技术没有太多开销，以至于浪费花在问题上的周期。而且我们还需要 足够的数据 ，以便可以实现获得提速所需的规模经济。

利用并行性

不是所有问题都适合并行化。考虑以下问题：给定一个函数 f，我们假设计算成本很高，将 g 定义如下：

g(0) = f(0)

g(n) = f( g(n-1) ), for n > 0

我们可以为 g 实现一个并行算法并度量它的提速，但我们不需要这么做；我们可以查看问题，而且立即就会发现它完全是顺序的。为了看到此结果，我们可以采用稍微不同的方式重写 g(n)：

g(n) = f( f( … n times … f(0) … ) )

重写之后，我们看到只有在 g(n-1) 计算完成后才能开始计算 g(n)。在计算 g(4) 的数据流依赖关系图中，如图 2 所示，g(n) 的每个值都依赖于前一个值 g(n-1)。

图 2. 函数 g 的数据流依赖关系图

您可能忍不住得出这样的判断：问题源于 g(n) 是以递归方式定义的，但其实不然。考虑计算函数 h(n) 的稍微不同的问题：

h(0) = f(0)

h(n) = f(n) + h(n-1)

如果编写计算 h(n) 的比较明显的实现，我们最终会得到一个类似图 3 的数据流依赖关系图，其中每个 h(n) 依赖于 h(n-1)。

图 3. 函数 h 的一种草率实现的数据流依赖关系图

但是，如果以不同方式重写 h(n)，就可以立即看到此问题可以通过并行性解决。我们可以独立地计算每一项，然后对它们求和（这也允许并行性）：

h(n) = f(0) + f(1) + .. + f(n)

结果会得到图 4 中所示的数据流依赖关系图，其中每个 h(n) 均可独立计算。

图 4. 函数 h 的数据流依赖关系图

这些示例表明了两点：首先，看起来类似的问题可能拥有完全不同的并行性可利用程度；第二，一个可利用并行性解决的问题的解决方案的 “明显” 实现不一定会 利用 并行性。要获得提速机会，需要同时满足两个条件。

分而治之

实现可利用的并行性的标准技术称为递归分解 或分而治之。在此方法中，会反复将问题分解为许多子问题，直到子问题小到比按照顺序解决更有意义；我们会并行解决子问题，然后组合子问题的各部分结果来获得总结果。

清单 1 使用 伪代码 演示了一个典型的分而治之解决方案，为并发执行使用了一个假想的 CONCURRENT 原语。

清单 1.递归分解

 R solve( problem <R> problem) {
    if (problem.isSmall())
        return problem.solveSequentially();
    R leftResult, rightResult;
    CONCURRENT {
        leftResult = solve(problem.leftHalf());
        rightResult = solve(problem.rightHalf());
    }
    return problem.combine(leftResult, rightResult);
}  

递归分解很吸引人，因为它 很简单 （在处理已递归定义的数据结构（比如树）时尤其如此）。类似清单 1 的并行代码可跨众多计算环境进行移植；它能够使用一个核心或许多核心高效地处理数据，而且它不需要担心协调对共享可变状态的访问带来复杂性 — 因为没有共享可变状态。将问题分解为若干个子问题，安排每个问题仅访问来自某个特定子问题的数据，这通常不需要进行 线程 间协调。

性能考虑因素

使用 清单 1 作为模型，我们现在可以继续分析并行性可带来优势的条件。通过分而治之方法引入了两个额外的算法步骤（分解问题和组合部分结果），每个步骤或多或少适合并行性。另一个可能影响并行性能的因素是并行性原语本身的效率，我们对 清单 1 的伪代码中假想的 CONCURRENT 机制进行了演示。其他两个因素是数据集的属性：数据集的大小和它的内存位置。我们将依次查看每个条件。

一些问题（比如 “利用并行性” 部分的 g(n) 函数）完全不允许使用分解。甚至在问题允许采用分解时，分解可能也需要成本。（至少，分解一个问题涉及到创建子问题的描述。）例如，Quicksort 算法的分解步骤需要找到一个支点，也就是问题大小中的 O(n)，因为它涉及到检查并（可能）更新所有数据。此需求比 “对一个元素数组求和” 这样的问题的分解步骤的需求要高得多，后者的分解步骤为 O(1)— “对最高和最低指数求平均值。”此外，即使可以高效地分解问题，如果两个子问题的大小非常不均匀，我们可能不会获得太多可利用的并行性。

类似地，在解决两个子问题时，必须组合结果。如果我们的问题是 “删除重复元素”，步骤的组合需要合并两个集合；如果我们想要获得结果的一种平面表示，此步骤也为 O(n)。另一方面，如果我们的问题是 “对一个数组求和”，我们的组合步骤也是 O(1)— “添加两个数”。

管理要并发执行的任务可能涉及到多个可能的效率损失来源，比如将数据从一个线程转交给另一个线程的内在延迟，或者争用共享数据结构的风险。fork-join 框架（Java SE 7 中添加来管理细粒度、计算密集型任务）旨在最大限度减少并行分派中许多常见的低效性来源。java.util.stream 库使用 fork-join 框架实现并行执行。

最后，我们必须考虑数据。如果数据集很小，则很难获得任何提速，原因是并行执行会带来启动成本。类似地，如果数据集所在的内存位置不佳（指针众多的数据结构，比如图表，而不是数组），利用如今典型的内存受限的系统执行并行可能会导致许多线程等待来自缓存的数据，而不是有效使用核心来更快地计算答案。

这些因素中的每一个都有可能降低提速；在某些情况下，它们不仅会降低提速，甚至还会导致减速。

阿姆达尔定律

阿姆达尔定律 描述计算的顺序部分对可能的并行提速有何限制。大部分问题都有一定数量的工作无法并行化；这部分工作被称为串行分数 (serial fraction)。例如，如果将从一个数组将数据复制到另一个数组，复制过程可以并行化，但目标数组的分配（具有内在的顺序性）必须在发生任何复制之前执行。

图 5 展示了阿姆达尔定律的效果。各种曲线演示了此定律所允许的可能的最佳加速比，是如何随着可获得的处理器数量的变化的同时，对于不同的并行分数（串行分数的补集），阿姆达尔定律所允许的最大提速。举例而言，如果并行碎片为 .5（一半的问题必须顺序执行）且有无限多个处理器可用，阿姆达尔定律会告诉我们，我们有望实现的最大提速为 2 倍。结果一目了然；即使我们可以通过并行化将可并行化部分的成本减少到 0，我们仍有一半的问题要顺序解决。

图 5. 阿姆达尔定律（图像来源：Wikimedia Commons）

阿姆达尔定律暗示的模型（工作的一些碎片必须完全顺序地执行，剩余部分可完美地并行化）过于简单。不过，该模型仍对理解阻碍并行性的因素很有用。查明和减少串行碎片的能力，是能够设计出更高效的并行算法的关键因素。

阿姆达尔定律的另一种解释是：如果您有一台 32 核的机器，对于您设置并行计算所花的每个周期，有 31 个周期不能应用来解决问题。而且如果您将问题拆分为两个子问题，每个时钟周期仍将浪费 30 个周期。只有当您拆分足够的工作来让所有处理器保持繁忙时，您才会获得全速性能 — 而且如果您没有足够快地达到全速性能（或在此状态停留足够长时间），将很难获得不错的提速。

结束语

并行性是一种权衡，它使用更多计算资源来希望获得提速。尽管从理论上讲，我们使用 N 个核心可将问题解决速度提高 N 倍，但现实通常离此目标相距甚远。影响并行性有效性的因素包括问题本身、解决问题所使用的算法、对任务分解和调度的运行时支持，以及数据集的大小和内存位置。Java Streams 的 第 5 部分 会将这些考虑因素应用到 Streams 库，并展示一些流管道如何（和为什么能）比其他管道更有效地实现并行化。

下期见咯~^_^