多核编程中的负载平衡难题
作者：周伟明
相关文章链接：
多核编程中的锁竞争难题
多核编程的几个难题及其应对策略（难题一）
OpenMP并行程序设计（二）
OpenMP并行程序设计（一）
双核CPU上的快速排序效率
前面
多核编程中的锁竞争难题 这篇文章中讲过一个多核编程中的串行化的难题，这篇文章中再来讲解一下多核编程中的另外一个难题，就是负载平衡方面的难题。
多核CPU中，要很好地发挥出多个CPU的性能的话，必须保证分配到各个CPU上的任务有一个很好的负载平衡。否则一些CPU在运行，另外一些CPU处于空闲，无法发挥出多核CPU的优势来。
要实现一个好的负载平衡通常有两种方案，一种是静态负载平衡，另外一种是动态负载平衡。
1
、静态负载平衡
静态负载平衡中，需要人工将程序分割成多个可并行执行的部分，并且要保证分割成的各个部分能够均衡地分布到各个CPU上运行，也就是说工作量要在多个任务间进行均匀的分配，使得达到高的加速系数。
静态负载平衡问题从数学上来说是一个NP完全性问题，Richard M. Karp, Jeffrey D. Ullman, Christos H. Papadimitriou, M. Garey, D. Johnson等人相继在1972年到1983年间证明了静态负载问题在几种不同约束条件下的NP完全性。
虽然NP完全性问题在数学上是难题，但是这并不是标题中所说的难题，因为NP完全性问题一般都可以找到很有效的近似算法来解决。
2
、动态负载平衡
动态负载平衡是在程序的运行过程中来进行任务的分配达到负载平衡的目的。实际情况中存在许多不能由静态负载平衡解决的问题，比如一个大的循环中，循环的次数是由外部输入的，事先并不知道循环的次数，此时采用静态负载平衡划分策略就很难实现负载平衡。
动态负载平衡中对任务的调度一般是由系统来实现的，程序员通常只能选择动态平衡的调度策略，不能修改调度策略，由于实际任务中存在很多的不确定因素，调度算法无法做得很优，因此动态负载平衡有时可能达不到既定的负载平衡要求。
3
、负载平衡的难题在那里？
负载平衡的难题并不在于负载平衡的程度要达到多少，因为即使在各个CPU上分配的任务执行时间存在一些差距，但是随着CPU核数的增多总能让总的执行时间下降，从而使加速系数随CPU核数的增加而增加。
负载平衡的困难之处在于程序中的可并行执行块很多要靠程序员来划分，当然CPU核数较少时，比如双核或4核，这种划分并不是很困难。但随着核数的增加，划分的粒度将变得越来越细，到了16核以上时，估计程序员要为如何划分任务而抓狂。比如一段顺序执行的代码，放到128核的CPU上运行，要手工划分成128个任务，其划分的难度可想而知。
负载划分的误差会随着CPU核数的增加而放大，比如一个需要16个时间单位的程序分到4个任务上执行，平均每个任务上的负载执行时间为4个时间单位，划分误差为1个时间单位的话，那么加速系数变成 16/(4+1)=3.2，是理想情况下加速系数 4的80％。但是如果放到一个16核CPU上运行的话，如果某个任务的划分误差如果为0.5个时间单位的话，那么加速系数变成16/(1+0.5) = 10.67，只有理想的加速系数16的66.7%，如果核数再增加的话，由于误差的放大，加速系数相比于理想加速系数的比例还会下降。
负载划分的难题还体现在CPU和软件的升级上，比如在4核CPU上的负载划分是均衡的，但到了8核、16核上，负载也许又变得不均衡了。软件升级也一样，当软件增加功能后，负载平衡又会遭到破坏，又需要重新划分负载使其达到平衡，这样一来软件设计的难度和麻烦大大增加了。
如果使用了锁的话，一些看起来是均衡的负载也可能会由于锁竞争变得不平衡起来，详细情况请看：
http://blog.csdn.net/drzhouweiming/archive/2007/04/10/1559718.aspx
4
、负载平衡的应对策略
对于运算量较小的软件，即使放到单核CPU上运行速度也很快，负载平衡做得差一些并没有太大影响，实际中负载平衡要考虑的是大运算量和规模很大的软件，这些软件需要在多核上进行负载平衡才能较好地利用多核来提高性能。
对于大规模的软件，负载平衡方面采取的应对策略是发展划分并行块的宏观划分方法，从整个软件系统层面来进行划分，而不是象传统的针对某些局部的程序和算法来进行并行分解，因为局部的程序通常都很难分解成几十个以上的任务来运行。
另外一个应对策略是在工具层面的，也就是编译工具能够协助人工进行并行块的分解，并找出良好的分解方案来，这方面Intel已经作出了一些努力，但是还需要更多的努力让工具的功能更强大一些才能应对核数较多时的情况。
参考资料：《并行编程模式》Timothy Mattson等著 敖富江译
《并行计算综论》Jack Dongarra等编著 莫则尧等译
《并行程序设计》Barry Wilkinson等著 陆鑫达等译
《多核程序设计技术》Shameem Akhter等著 李宝峰等译
《并行算法实践》 陈国良等编著
