多核编程的几个难题及其应对策略（难题一）
 
相关文章链接：多核编程中的负载平衡难题
                           多核编程中的锁竞争难题
                           OpenMP并行程序设计（二）
                           OpenMP并行程序设计（一）
                           双核CPU上的快速排序效率
随着多核CPU的出世，多核编程方面的问题将摆上了程序员的日程，有许多老的程序员以为早就有多CPU的机器，业界在多CPU机器上的编程已经积累了很多经验，多核CPU上的编程应该差不多，只要借鉴以前的多任务编程、并行编程和并行算法方面的经验就足够了。
我想说的是，多核机器和以前的多CPU机器有很大的不同，以前的多CPU机器都是用在特定领域，比如服务器，或者一些可以进行大型并行计算的领域，这些领域很容易发挥出多CPU的优势，而现在多核机器则是应用到普通用户的各个层面，特别是客户端机器要使用多核CPU，而很多客户端软件要想发挥出多核的并行优势恐怕没有服务器和可以进行大型并行计算的特定领域简单。
这次参加CSDN大会时和孟岩先生聊起多核编程时，孟岩先生对多核编程的前途感觉到很悲观，和去年见到他时对多核编程的前景看法完全发生了改变。想来孟岩先生对多核编程方面有了很深刻的理解，由于时间问题，没能和孟岩先生在这方面深入聊下去。在回来的路上，我重新思考了一下关于多核编程方面的困难之处，今天回到家赶紧把它写了下来，贴出来分享给大家。
难题一：串行化方面的难题
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)*fts
其中fts表示串行执行所占的比例
如果串行比例为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的优势。
 
作者介绍：周伟明，自由职业，从事软件行业十年有余。目前主要关注软件测试、多核编程、软件设计等基础方面的内容。写有《多任务下的数据结构与算法》一书，目前正在写作《软件测试实践》一书，计划在不久的将来写一本多核编程方面的书籍。
 
参考资料：《并行编程模式》Timothy Mattson等著 敖富江译
         《并行计算综论》Jack Dongarra等编著 莫则尧等译
               《并行程序设计》Barry Wilkinson等著 陆鑫达等译
               《多核程序设计技术》Shameem Akhter等著 李宝峰等译
         《并行算法实践》 陈国良等编著

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/drzhouweiming/archive/2007/04/10/1559698.aspx