八条设计多线程程序的简单规则

八条设计多线程程序的简单规则

更新：
[2010.3.6] Scalability翻译从”可扩展性“改成”可伸缩性“.

前言：最近在看该作者的《The Art of Concurrency》，里面第四章就是上面这篇文章，觉得很实用而且很有共鸣。作者基于在并行编程领域的20多年工作经验总结成下面八条简单的原则， 一下子帮我把之前并行编程时的一些认识给理清了，量化了，实在是“居家旅行，并行编程，必备良药”。花了几天时间把它翻译了一下，不知道各位在看了之后是 否有些共鸣呢？

作者：Clay Breshears
译者：并行实验室 Parallel Labs

在Intel，并行化技术主要有四个步骤：分析，设计与实现，调试以及性能调优。这些步骤用来对一段串行代码进行并行化。尽管这四个步骤中的第一、三、四步都已经有了很多相关文档，但是关于怎样进行设计与实现的却不多。

并行编程更像是一门艺术，而不是一门科学。这里将会给出八条设计多线程程序的简单规则，你可以把他们一一放进你的多线程程序设计百宝箱中。通过参考 这些规则，你能写出高质量、高效率的多线程程序。我努力试着将这些规则按照(半)时间顺序组织起来，但是它们之间并没有硬性的先后顺序。就像“别在泳池边 奔跑”和“别在浅水区跳水”一样，两个都是好主意，但是后者也能放在前者的前面，反之亦然。

规则一：找到真正不相关的计算任务
如果你将要执行的运算任务相互之间不独立的话，你是不可能将它们并行化的。我可以很容易的举出一些真实世界中相互独立的任务如何为了达成同一个目的而工作 的例子。比如说一个DVD出租店，它先把收到的求租电影的订单分给员工们，员工再从存放电影DVD的地方根据订单找到影片拷贝。当一个员工取出一张古典音 乐喜剧的拷贝时，他并不影响另一个寻找最近科幻电影大作的员工，也不影响另一个寻找某热门犯罪连续剧第二季花絮的员工（我假设所有不能被满足的订单在递交 给DVD出租店之前就已经被处理过了）。同样的，每个订单的打包和邮递工作也不会影响其他订单的查找、运送和处理工作。

你也可能会遇到某些不能被并行化的而只能串行执行的计算任务，它们大多数是因为循环之间或者计算步骤之间有依赖关系从而导致它们只能按照特定的顺序 串行执行。一个很好的例子是驯鹿怀孕的过程。通常驯鹿需要八个月来生小驯鹿，你不可能为了早点生个小驯鹿就让八个驯鹿来一起来生，想一个月就生出一个来。 但是，如果圣诞老人希望尽快的扩充雪橇队伍，他可以让八只驯鹿一起生，这样八个月后就能有八只小驯鹿了（注：可以理解为尽管单个任务的执行时间没缩短，但 是吞吐量却大了）。

规则二：尽可能地在最高层进行并行化
在对一段串行代码进行并行化时我们有两种方法可以选择，一个是自底向上，另一个是自顶向下。在对我们的代码进行分析的过程中，我们先找到花费了最多执行时间的程序热点(hotspots)。对这些代码段进行并行化是使我们获得最大的性能提升的最好办法。

在自底向上的方法中，你可以考虑先直接对那些程序热点进行并行化。如果这不太可能实现的话，我们可以顺着它的调用栈(call stack)向上查找，看看能不能找到其他的可以并行化的程序热点。假如你的程序热点在一个嵌套循环的最里层，我们可以从内向外的逐一检查每一层循环，看 看某一层是否能被并行执行。即使我们能一开始就很顺利的把程序热点并行化了，我们仍然应该去检查一下是否可能在调用栈中更高的某一层上实现并行化。这样做 能提高每个线程所执行的任务的粒度。（注：每个线程所执行的任务的粒度可以理解为成功并行化了的部分在整个程序中所占的比例，根据Amdahl定律，并行 化的部分越多，程序的整体性能越高）

为了更清楚的描述这条规则，让我们举一个对视频编码程序进行并行化的例子。如果你的程序热点是针对每个像素的计算，你可以先找到对一帧视频中的每个 像素进行计算的循环，并考虑对它进行并行化。以此为基础向“上”找，你可能会发现对每一帧进行处理的循环也是可以被并行化的，这意味着每个线程都可以以帧 为单位对一组数据进行独立的处理。如果这个视频编码程序同时要对好几个视频进行处理，那么让每个线程单独处理一个视频流将会是最高层的并行化。

在另一种自顶向下的并行化方法中，我们可以先对整个程序以及计算的流程（为了完成计算任务而依序组合起来的各个程序模块）进行分析。如果并行化的机 会不是很明显，我们可以挑出那些包含了程序热点的模块并对他们进行分析，如果不行就再分析更小的程序热点模块，直到能找到独立的计算任务为止。

对视频编码程序的例子来说，如果你的程序热点是针对单个像素的计算，采用自顶向下的方法时就可以首先考虑该程序对多个不同的视频流进行编码的情况 （每个编码任务都包含了像素计算的任务）。如果你能在这一层成功进行并行化，那么你已经得到了最高层的并行。如果没能成功，那我们可以向“下”找，看看每 个视频流的不同帧的计算是否能被并行处理，最后看看每个帧的不同像素的计算是否能被并行处理。

并行任务的粒度可以理解成在进行同步之前所需要完成的计算量。同步之间运行的时间越长，粒度越大。细粒度的并行存在的隐患就是给每个线程分配的任务 可能不够多，以至于都不够弥补使用多线程所带来的开销。此时，在计算量不变的情况下使用更多的线程只会让情况变得更加糟糕。粗粒度的并行化拥有相对来说更 少的线程开销，并且更可能在线程增多的情况下仍然有很好的可扩展性。尽可能的在最高层对程序热点实现并行化是实现对多线程的粗粒度任务划分的主要方法之 一。

规则三：尽早针对众核趋势做好可伸缩性的规划
当我写这本书的时候，四核处理器已经成为了主流。未来处理器的核心数量只会越来越多。所以你应该在你的软件中为这个发展趋势做好规划。可伸缩性 （scalability）被用来用来衡量一个程序应对变化的能力，典型的变化有系统资源（例如核心数量，内存大小，总线速度）或数据集大小的增加等。在 面对越来越多的可用核心时，你必须写出能灵活高效的利用不同数量的核心的代码。

C. Northcote Parkinson说过，“数据的增长是为了适应处理能力的增加”。这意味着随着计算能力的增长加（核心数量的增加），很有可能我们会有更多的数据需要处 理。我们永远会有更多的计算任务需要完成。不管是增加科学模拟中的建模精度，还是处理更清晰的高清视频，又或者搜索许多更大的数据库，如果你拥有了更多的 计算资源，总会有人想要处理更多的数据。

用数据分解(data decomposition)的方法来设计和实现并行化能给你提供更多的高可扩展性的解决方案。任务分解(task decomposition)的方法可能会面临程序中可独立运行的函数或者代码段数量有限或者数量固定的问题。等到每一个独立的任务已经在单独的线程和核 心上运行的时候，再想通过增加线程的数量来利用空闲的多余核心的方法就提高不了程序的性能了。因为在一个程序中数据的大小比独立的计算任务的数量更有可能 增加，所以基于数据分解的设计将更有可能获得很好的可伸缩性。

即使有的程序已经基于任务分解的模式给每个线程分配了不同的计算任务，我们仍然可以在需要处理的数据增加的时候利用更多的线程来完成工作。例如我们 需要修建一个杂货店，这项工程由一些不同的任务组成。如果开发商又买了一块相邻的地皮，并且商店要盖的楼层数翻倍了，我们可以雇佣更多的工人去完成这些的 任务，比如说更多的油漆工，更多的盖顶工，更多的电工。因此，我们应该注意是否能对增加了的数据进行数据分解，以便利用空闲核心上的可用线程来完成这个工 作，哪怕是在我们已经采用了任务分解的方式的程序中。

规则四：尽可能利用已有的线程安全库
如果你的程序热点的计算任务能通过库函数调用来完成，强烈建议你考虑使用同等功能的库函数，而不是调用自己手写的代码。即使是串行程序，“重新造轮子”来 完成已经被高度优化的库函数实现了的功能仍不是一个好主意。许多的库，例如Intel Math Kernel Library（Intel MKL）和Intel Integrated Performance Primitives (Intel IPP)，提供了能更好的利用多核处理器的并行版本的函数。

比使用并行版本的函数库更重要的一点是：我们需要确保所有的库函数调用都是线程安全的（thread-safe）。如果你已经把你串行代码中的程序 热点替换成了一个库函数调用，你仍有可能在调用树(call tree)的更高层上发现能把程序分解成独立的计算任务的代码段。当你有好几个并行的计算任务，并且它们都同时调用了库函数（特别是第三方函数库），那么 函数库中引用并更新共享变量的函数可能会造成数据竞争(data race)。记得好好检查你在并行编程中所调用的函数库的文档中关于线程安全性的描述。当你在设计和编写自己的用于并行执行的函数库时，请务必确保函数是 可重入(reentrant)的。如果不能确保的话，你应该给共享的资源加上同步机制。

规则五：使用合适的多线程模型
如果并行版的函数库不足以完成程序的并行化，而你又想使用可以自己控制的线程，在隐式的多线程模型能满足你的功能需求的前提下请尽量使用该模型（例如 OpenMP或者Intel Thread Building Block）而不是显式的多线程模型（例如Pthread）。显式的多线程模型确实能提供对线程的更精确的控制。但是，如果你仅仅是想把你的计算密集型循 环给并行化，或者你不需要显式多线程模型提供的诸多特性，那么我们最好还是能满足需要就好。实现的复杂度越高，犯错误的几率就越大，以后代码的维护难度也 会越大。

OpenMP采用的是数据分解的方法，它尤其适合并行化那些需要处理大量数据的循环。尽管这种类型的并行化可能是唯一一种你能引入的并行模式，但是 可能还会有其他的要求（例如由你的雇主或者管理层所决定的工程方案）让你不能使用OpenMP。如果是那样的话，我建议你先使用OpenMP来快速开发出 并行化后的模型，估算一下可能的性能提升、可扩展性以及大概需要多少时间才能把这些串行代码用显式多线程库给并行化。

规则六：永远不要假设具体的执行顺序
在串行程序中我们可以非常容易地预测某个程序的当前状态结束之后它会变成什么状态。然而，多个线程的执行顺序却是不确定的，它是由操作系统的调度器 (scheduler)决定的。这意味着我们不可能准确的预测两个执行状态之间多个线程的执行顺序，甚至连预测哪个线程会在下一步被调度执行也不能。这样 的机制主要是为了隐藏程序运行时的延迟，特别是当运行的线程的数量多于核心的数量时。例如，如果一个线程因为要访问不在cache中的地址，或者需要处理 一个I/O请求而被阻塞了(blocked)，那么操作系统的调度器就会把该线程调度到等待队列里，同时把另一个等待执行的线程调度进来并执行它。

数据竞争(data race)就是由这种调度的不确定性造成的。如果你假设一个线程对共享变量的写操作会在另一个线程对该共享变量的读操作之前完成，你的预测可能会一直正 确，有可能有些时候会正确，也有可能从来都不会正确。如果你足够幸运的话，有时候在一个特定平台上每次你运行这个程序时线程的执行顺序都不会改变。但是系 统间的每个不同（例如数据在磁盘上存储的位置，内存的速度或者插座中的交流电源）都有可能影响线程的调度。对一段需要特定的线程执行顺序的代码来说，如果 仅仅依靠乐观的估计而不采取任何实质性的措施的话，很有可能会受到数据竞争，死锁等问题的困扰。

从性能的角度来讲，最好的情形当然是让所有的线程尽可能没有约束的运行，就像比赛中的赛马或猎犬的一样。除非必要的话，尽可能不要规定一个特定的执行顺序。你需要找到那些确实需要规定执行顺序的地方，并且实现一些必要的同步方法来调整线程间的执行顺序。

拿接力赛跑来说，第一棒的选手会竭尽全力的奔跑。但是为了成功的完成接力赛，第二个，第三个和最后一棒都需要先等到拿到接力棒之后才能开始跑他们的赛段。接力棒的交接就是他们的同步机制，这样就确保了接力过程中的“执行”顺序。

规则七：尽可能使用线程本地存储或者对特定的数据加锁
同步（Synchronization）本身并不属于计算任务，它只是为了确保程序的并行执行能得到正确的结果所产生的额外开销。虽然它产生了额外的开销 但是又不可或缺。因此我们还是要尽可能的把同步所产生的开销降低到最低。你可以使用线程私有的存储空间或者独占的内存地址（例如一个用线程ID来进行索引 的数组）来达到这个目的。

那些很少需要在线程间共享的临时变量可以被每个线程单独地在本地进行声明或分配。那些存储着每个线程的部分结果（partial result）的变量也应该是线程私有的。但是在把每个线程的部分结果保存到一个共享的变量的时候就需要采取一些适当的同步措施了。如果我们能确保这样的 共享更新操作能尽可能少的进行，我们就可以把同步的额外开销降到最低了。如果我们使用显式的线程编程模型的话，我们可以使用那些线程本地存储 （Thread Local Storage）的API来保证线程私有变量在多个并行区域的执行过程中，或者在一个并行函数的多次调用的过程中的一致性。

如果线程本地存储不可行，而且你必须用同步的对象（例如锁）来协调对共享资源的访问的话，请确保对数据进行了适当的锁操作。最简单的方法就是对锁和 数据对象采取一一对应的分配策略。如果对变量的内存地址的访问都是在同一个临界区进行的话，我们就可以使用一把锁来对多个数据进行保护。

如果你有大量的数据需要保护，例如由一万个数据的数组，我们该怎么办呢？如果我们对整个数组只用一个锁来进行保护的话，很可能会造成严重的锁竞争从 而导致性能瓶颈。那么我们是不是可以给每个数组元素创建一个锁呢？然而即使是有32个或者64个线程在同时访问这个数组，这样做看起来也浪费了很多的内存 空间来保护那些只有百分之一不到的发生概率的访问冲突。不过有一种折中的解决方案，叫做“取模锁”（modulo lock）。取模锁是用来保护数据集合中的所有的第N个元素，其中N是锁的数量。例如，有两个锁，一个保护所有的奇数个的元素，另一个保护所有的偶数个元 素。当需要访问一个被保护的变量时，线程需要先对要访问的地址进行取模操作，然后再去获得对应的取模锁。使用的锁的数量应该是基于线程的数量以及两个线程 同时访问相同元素的可能性来决定。

但是，当你决定用锁来对数据进行保护时，请一定不要用多于一个的锁来给一个单独的元素进行加锁。西格尔定律告诉我们“一个人看着一个表能知道现在几 点了，但是他要是有两个表那么他就确定不了时间了”。如果两个不同的锁都对同一个变量进行了保护，那么可能出现代码中的某一部分通过第一个锁来进行访问的 同时，代码中的另一部分通过第二个锁也进行了访问。正在执行这两个代码段的多个线程就可能发生数据竞争，因为它们都以为它们对这个被保护的变量有独占的访 问权限。

规则八：敢于更换更易并行化的算法
当比较串行或者并行程序的性能的时候，运行时间就是衡量的首要标准。程序员会根据算法的时间复杂度来进行选择。时间复杂度和一个程序的性能是息息相关的。 它的含义就是，当其他的一切条件都一样时，完成同样功能的时间复杂度为O(NlogN)的算法（例如快速排序）要比O（n^2）的算法（例如选择排序）要 快。

在并行程序中，拥有更好的时间复杂度的算法也会更快一些。然而，有些时候时间复杂度更好的算法却不是很容易被并行化。如果算法的热点不太容易被并行 化的话（而且在调用栈的更高层中你又找不到能很容易被并行化的热点），那么你可以尝试换一个稍微慢一点但是却更容易被并行化的算法。当然，还有可能一些其 他的改动措施也能让你比较轻松的把某一段代码给并行化了。

这里我们可以给出一个线性代数中两个矩阵相乘的例子。Strassen的算法拥有最好的时间复杂度：O(n^2.81)。这当然比传统的三重循环的 O(n^3)的算法要好。Strassen的算法把每个分成四部分，然后进行七次递归调用来对n/2 x n/2的子矩阵进行乘运算。如果想把这七次递归调用并行化的话，我们可以在每次的递归调用的时候创建一个新线程来进行运算，直到子矩阵到达一个预设的大小 为止。这样的话线程的数量就会指数级的成倍增长。随着子矩阵越来越小，给新创建的线程分配的计算任务就会越来越少。还有另一种方法，就是先创建一个有七个 线程的线程池。七次子矩阵相乘的运算任务可以分别分配给这七个线程以完成并行化。这样的话线程池就会跟串行版本的程序一样递归调用Strassen算法来 对子矩阵进行乘运算。然而，这种方法的缺点就在于对一个拥有大于八个核的系统来说，永远只有七个核在工作，其他的资源都被浪费了。

另一个更容易被并行化的矩阵乘法就是三重循环的算法了。我们可以有很多方法来对矩阵进行数据分解（按行分解，按列分解或者按块分解）然后再把它们分 配给不同的线程。通过用OpenMP在某一层循环中加上编译指示，或者用显式线程模型实现矩阵分割，我们很容易的就能完成并行化。只需要更少的代码改动就 可以对这个简单的串行算法完成并行化，并且代码的整体结构改动也会比Strassen算法要少很多。

总结
我们已经列出了八条简单的规则，在把串行程序并行化的过程中你应该时刻记住它们。通过遵循这些规则以及一些实际的编程规则，你应该可以更容易的创造更健壮的并行化解决方案，同时能包含更少的并行化时的问题，以及在更短的时间里得到最好的性能。

原文链接：