多核编程的串行化难题及其应对策略

【引自周伟明的博客】随着多核CPU的出世，多核编程方面的问题将摆上了程序员的日程，有许多老的程序员以为早就有多CPU的机器，业界在多CPU机器上的编程已经积累了很多经验，多核CPU上的编程应该差不多，只要借鉴以前的多任务编程、并行编程和并行算法方面的经验就足够了。

我想说的是，多核机器和以前的多CPU机器有很大的不同，以前的多CPU机器都是用在特定领域，比如服务器，或者一些可以进行大型并行计算的领域，这些领域很容易发挥出多CPU的优势，而现在多核机器则是应用到普通用户的各个层面，特别是客户端机器要使用多核CPU，而很多客户端软件要想发挥出多核的并行优势恐怕没有服务器和可以进行大型并行计算的特定领域简单。

难题一：串行化方面的难题

1）加速系数

衡量多处理器系统的性能时，通常要用到的一个指标叫做加速系数，定义如下：

S(p) = 使用单处理器执行时间（最好的顺序算法）/ 使用具有p个处理器所需执行时间

2）阿姆尔达定律

并行处理时有一个阿姆尔达定律，用方程式表示如下：

S(p) = p / (1 + (p-1)*f)

其中 S(p)表示加速系数

p表示处理器的个数

f表示串行部分所占整个程序执行时间的比例

当f = 5%, p = 20时, S(p) = 10.256左右

当f = 5%, p = 100时, S(p) = 16.8左右

也就是说只要有5％的串行部分，当处理器个数从20个增加到100个时，加速系数只能从10.256增加到16.8左右，处理器个数增加了5倍，速度只增加了60％多一点。即使处理器个数增加到无穷多个，加速系数的极限值也只有20。

如果按照阿姆尔达定律的话，可以说多核方面几乎没有任何发展前景，即使软件中只有1％的不可并行化部分，那么最大加速系统也只能到达100，再多的CPU也无法提升速度性能。按照这个定律，可以说多核CPU的发展让摩尔定律延续不了多少年就会到达极限。

3）Gustafson定律

Gustafson提出了和阿姆尔达定律不同的假设来证明加速系数是可以超越阿姆尔达定律的限制的，Gustafson认为软件中的串行部分是固定的，不会随规模的增大而增大，并假设并行处理部分的执行时间是固定的（服务器软件可能就是这样）。Gustafson定律用公式描述如下：

S(p) = p + (1-p)*ft_s

其中ft_s表示串行执行所占的比例

如果串行比例为5％，处理器个数为20个，那么加速系数为20＋(1-20)*5%=19.05

如果串行比例为5％，处理器个数为100个，那么加速系数为100＋(1-100)*5%=95.05

Gustafson定律中的加速系数几乎跟处理器个数成正比，如果现实情况符合Gustafson定律的假设前提的话，那么软件的性能将可以随着处理个数的增加而增加。

4）实际情况中的串行化分析

阿姆尔达定律和Gustafson定律的计算结果差距如此之大，那么现实情况到底是符合那一个定律呢？我个人认为现实情况中既不会象阿姆尔达定律那么悲观，但也不会象Gustafson定律那么乐观。为什么这样说呢？还是进行一下简单的分析吧！

首先需要确定软件中到底有那么内容不能并行化，才能估计出串行部分所占的比例，20世纪60年代时，Bernstein就给出了不能进行并行计算的三个条件：

条件1：C1写某一存储单元后，C2读该单元的数据。称为“写后读”竞争

条件2：C1读某一存储单元数据后，C2写该单元。称为“读后写”竞争

条件1：C1写某一存储单元后，C2写该单元。称为“写后写”竞争

满足以上三个条件中的任何一个都不能进行并行执行。不幸的是在实际的软件中大量存在满足上述情况的现象，也就是我们常说的共享数据要加锁保护的问题。

加锁保护导致的串行化问题如果在任务数量固定的前提下，串行化所占的比例是随软件规模的增大而减小的，但不幸的是它会随任务数量的增加而增加，也就是说处理器个数越多，锁竞争导致的串行化将越严重，从而使得串行化所占的比例随处理器个数的增加而急剧增加。（关于锁竞争导致的串行化加剧情况我会在另一篇文章中讲解）。所以串行化问题是多核编程面临的一大难题。

5）可能的解决措施

对于串行化方面的难题，首先想到的解决措施就是少用锁，甚至采用无锁编程，不过这对普通程序员来说几乎是难以完成的工作，因为无锁编程方面的算法太过于复杂，而且使用不当很容易出错，许多已经发表到专业期刊上的无锁算法后来又被证明是错的，可以想象得到这里面的难度有多大。

第二个解决方案就是使用原子操作来替代锁，使用原子操作本质上并没有解决串行化问题，只不过是让串行化的速度大大提升，从而使得串行化所占执行时间比例大大下降。不过目前芯片厂商提供的原子操作很有限，只能在少数地方起作用，芯片厂商在这方面可能还需要继续努力，提供更多功能稍微强大一些的原子操作来避免更多的地方的锁的使用。

第三个解决方案是从设计和算法层面来缩小串行化所占的比例。也许需要发现实用的并行方面的设计模式来缩减锁的使用，目前业界在这方面已经积累了一定的经验，如任务分解模式，数据分解模式，数据共享模式，相信随着多核CPU的大规模使用将来会有更多的新的有效的并行设计模式和算法冒出来。

第四个解决方案是从芯片设计方面来考虑的，由于我对芯片设计方面一无所知，所以这个解决方案也许只是我的一厢情愿的猜想。主要的想法是在芯片层面设计一些新的指令，这些指令不象以前单核CPU指令那样是由单个CPU完成的，而是由多个CPU进行并行处理完成的一些并行指令，这样程序员调用这些并行处理指令编程就象编写串行化程序一样，但又充分利用上了多个CPU的优势。

查看本文来源