1.5   并行的困境

现在来看看为什么多处理器编程(www.cppentry.com)富有趣味性。理想情形下，从单处理器升级到n路关联多处理器应该提高了n倍的计算能力。遗憾的是，实际中不可能做到这一点，其主要原因就在于现实世界中的大多数计算问题在不考虑处理器之间通信和协作开销的情况下无法有效地并行化。

假设有5个朋友要粉刷一套有5个房间的房屋。如果所有房间大小都一样，那么可以指定每人负责一间，只要这5个人以同样的速度来粉刷，就能获得相当于由一个人完成整个粉刷工作5倍的加速比。如果每个房间的大小不一，问题就复杂多了。例如，若有一个房间是其他房间的2倍，那么这5个人同时工作就不可能获得5倍的加速比，因为整个任务的完成时间取决于粉刷时间最长的那个房间。

这样的分析对并发计算非常重要，可以用Amdahl定律进行解释。该定律揭示了这样一个概念：完成复杂工作（不只是粉刷房子）可获得的加速比是有限的，受限于这个工作中必须被串行执行的部分。

工作的加速比S定义为由一个处理器来完成一项工作的时间（用挂钟时间来计算）与采用n个处理器并发完成该工作的时间之比。Amdahl定律给出了用n个处理器协同完成一个应用时可获得的最大加速比S，其中p是该应用中可以并行执行的部分。为简单起见，假设由一个处理器完成整个应用需用1个单位的时间。使用n个处理器并发执行应用中的并行部分需用时p/n，应用中串行部分的执行时间为1-p。因此，并行化以后的计算时间为：

1 - p + p/n

按照Amdahl定律所给出的加速比定义，得到

S = 1 / (1 - p + p/n)

我们仍采用粉刷房屋的例子来解释Amdahl定律的含义。假定每个小房间是1个单位，唯一的大房间是2个单位。每个房间指定一个人（处理器）粉刷意味着6个单位中的5个可以并行粉刷，即p=5/6，1 - p = 1/6。由Amdahl定律可得加速比为

S = 1 / (1 - p + p/n) = 1 / (1/6 + 1/6) = 3

由此可知，若有一间房间的大小是其他房间的2倍，那么5个人同时粉刷房屋的加速比仅仅是一个人粉刷的3倍。

如果由10个人分别粉刷10间房间，其中一间房间是其他房间的2倍，情况将变得更糟。下面是所求出的加速比：

S = 1 / (1/11 + 1/11) = 5.5

可以看出，仅仅微小的失衡就使10个人粉刷房屋只能获得5倍多的加速比，几乎是预期值的一半。

因此，可以使用类似于前面素数打印中所采用的方案：一旦某个人完成了自己的工作，他就马上帮助其他人完成剩余的工作。然而，这种共享式粉刷所存在的问题就在于粉刷者之间需要协调合作，那么是否可以设法避免这种协调问题呢？

下面分析Amdahl定律所揭示的多处理器利用率问题。有些计算问题是可以“密集并行”的：那些易于划分为多个可并发执行部分的计算。这种问题有时会在科学计算或图像处理中出现，但在系统中却很少出现。通常情况下，对于一个给定的问题以及一台具有10个处理器的机器，由Amdahl定律可知，即使其中的90%可以并行，而仅有10%需要串行，最终也只能获得5倍的加速比，而不是10倍。也就是说，串行执行的10%使得机器的利用率降低了一半。由此可见，应该尽量使那10%的部分达到最大程度的并行，当然，这一点实现起来非常困难，其难点就在于新增的并行部分中往往涉及通信和协作。本书的重点就是：理解和掌握对程序代码中那些需要同步和协作的部分进行高效编程(www.cppentry.com)的技术和工具，这部分代码的改进将对系统性能产生很大的影响。

我们回顾图1-2所示的素数打印问题，分析其中三行主要代码：

如果线程将这三行代码作为一个原子单位来执行，也就是将它们放入一个互斥域内，那么问题的解决非常简单。然而，现在只让getAndIncrement()调用为原子的。这样的实现符合Amdahl定律：应最小化串行代码的粒度，即只采用互斥方式执行getAndIncrement()。此外，由于围绕着该可共享的互斥计数器的通信和协作本质上也会影响整个程序的性能，因此互斥机制的高效率实现也是很重要的。