ConcurrencyWithJava

设计并发算法的方法论

我们将提出一个五步骤的方法论来获得某一串行算法的并发版本。
该方法论基于 Intel 公司在其“Threading Methodology: Principles and Practices”文档中给出的方法论。

起点：算法的一个串行版本

我们实现并发算法的起点是该算法的一个串行版本。
当然，也可以从头开始设计一个并发算法。

算法的串行版本有两个方面的好处：

• 我们可以使用串行算法来测试并发算法是否生成了正确的结果。
  当接收同样的输入时，这两个版本的算法必须生成同样的输出结果，这样我们就可以检测并发版本中的一些问题，例如数据竞争或者类似的条件。

• 我们可以度量这两个算法的吞吐量，以此来观察使用并发处理是否能够改善响应时间或者提升算法一次性所能处理的数据量。

第 1 步：分析

在这一步中，我们将分析算法的串行版本来寻找它的代码中有哪些部分可以以并行方式执行。
我们应该特别关注那些执行过程花费时间最多或者执行代码较多的部分，因为实现这些部分的并发版本将能获得较大的性能改进。

对这一过程而言，比较好的候选方案就是循环排查，让其中的一个步骤独立于其他步骤，或者让其中某些部分的代码独立于其他部分的代码 。 （例如一个用于初始化某个应用程序的算法，它打开与数据库的连接，加载配置文件，初始化一些对象。所有这些前期任务都是相互独立的）

第 2 步：设计

一旦你知道了要对哪些部分的代码并行处理，就要决定如何对其进行并行化处理了。
代码的变化将影响应用程序的两个主要部分：

• 代码的结构。
• 数据结构的组织。

你可以采用两种方式来完成这一任务。

• 任务分解：当你将代码划分成两个或多个可以立刻执行的独立任务时，就是在进行任务分解。
  其中有些任务可能必须按照某种给定的顺序来执行，或者必须在同一点上等待。
  你必须使用同步机制来实现这样的行为。

• 数据分解：当使用同一任务的多个实例分别对数据集的一个子集进行处理时，就是在进行数据分解。
  该数据集是一个共享资源，因此，如果这些任务需要修改数据，那你必须实现一个临界段来保护对数据的访问。

另一个必须牢记的要点是解决方案的粒度。
实现一个算法的并发版本，其目标在于实现性能的改善，因此你应该使用所有可用的处理器或核。
另一方面，当你采用某种同步机制时，就引入了一些额外的必须执行的指令。
如果你将算法分割成很多小任务（细粒度），实现同步机制所需额外引入的代码就会导致性能下降。
如果你将算法分割成比核数还少的任务（粗粒度），那么就没有充分利用全部资源。
同样，你还要考虑每个线程都必须要做的工作，尤其是当你实现细粒度解决方案时。
如果某个任务的执行时间比其他任务长，那么该任务将决定整个应用程序的执行时间。你需要在这两点之间找到平衡。

第 3 步：实现

使用某种编程语言来实现并发算法了，而且如果必要，还要用到线程库。

第 4 步：测试

在完成实现过程之后，你应该对该并行算法进行测试。
如果你有了算法的串行版本，可以对比这两个版本算法的结果，从而验证并行版本是否正确。

测试和调试一个并行程序的具体实现是非常困难的任务，因为应用程序中不同任务的执行顺序是无法保证的。

第 5 步：调整

对比并行算法和串行算法的吞吐量。 如果结果并未达到预期，那么你必须重新审查该算法，查找造成并行算法性能较差的原因。
也可以测试该算法的不同参数（例如任务的粒度或数量），从而找到最佳配置。

还有其他一些指标可用来评估通过使算法并行处理可能获得的性能改进。
下面给出的是最常见的三个指标。

• 加速比（speedup）：这是一个用于评价并行版算法和串行版算法之间相对性能改进情况的指标。
  Speedup = T sequential / T concurrent
  其中，T sequential 是算法串行版的执行时间，而 T concurrent 是算法并行版的执行时间。

• Amdahl 定律：该定律用于计算对算法并行化处理之后可获得的最大期望改进。
  Speedup ≤ 1 / ((1-P) + (P/N))
  其中，P是可以进行并行化处理的代码的百分比，而 N是你准备用于执行该算法的计算机的核数。
• Gustafson-Barsis 定律：Amdahl 定律具有一定缺陷。 它假设当你增加核的数量时输入数据集是相同的，但是一般来说，当拥有更多的核时，你就想处理更多的数据。
  Gustafson 定律认为，当你有更多可用的核时，可同时解决的问题规模就越大，其公式如下：
  Speedup = P - a * ( P - 1)
  其中，N 为核数，而 P 为可并行处理代码所占的百分比。

结论

并非每一个算法都可以进行并行化处理。
例如，如果你要执行一个循环，其每次迭代的结果取决于前一次迭代的结果，那么你就不能对该循环进行并行化处理。
对性能良好的串行版算法实现并行处理，实际上是个糟糕的出发点。

当你实现一个并发应用程序时（从头开始或者基于一个串行算法），必须要考虑下面几点。

• 效率：并行版算法花费的时间必须比串行版算法少。
  对算法进行并行处理的首要目标就是实现运行时间比串行版算法少，或者说它能够在相同时间内处理更多的数据。

• 简单：当你实现一个算法（无论是否为并行算法）时，必须尽可能确保其简单。
  它应该更加容易实现、测试、调试和维护，这样就会少出错。
• 可移植性：你的并行算法应该只需要很少的更改就能够在不同的平台上执行。
  因为在本书中使用 Java 语言，所以做到这一点非常简单。
  有了 Java，你就可以在每一种操作系统中执行程序而无须任何更改（除非因为程序实现而必须更改）。
• 伸缩性：如果你增加了核的数目，算法会发生什么情况？
  正如前面提到的，你应该使用所有可用的核，这样一来你的算法就能利用所有可用的资源。