负载平衡问题
多核编程中的锁竞争难题 这篇文章中讲过一个多核编程中的串行化的难题,这篇文章中再来讲解一下多核编程中的另外一个难题,就是负载平衡方面的难题。
多核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、动态负载平衡
动态负载平衡是在程序的运行过程中来进行任务的分配达到负载平衡的目的。实际情况中存在许多不能由静态负载平衡解决的问题,比如一个大的循环中,循环的次数是由外部输入的,事先并不知道循环的次数,此时采用静态负载平衡划分策略就很难实现负载平衡。
动态负载平衡中对任务的调度一般是由系统来实现的,程序员通常只能选择动态平衡的调度策略,不能修改调度策略,由于实际任务中存在很多的不确定因素,调度算法无法做得很优,因此动态负载平衡有时可能达不到既定的负载平衡要求。[page]
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已经作出了一些努力,但是还需要更多的努力让工具的功能更强大一些才能应对核数较多时的情况。
多核编程中的锁竞争问题
在前一篇讲解多核编程的几个难题及其对策(难题一)的文章中提到了锁竞争会让串行化随CPU的核数增多而加剧的现象,这篇文章就来对多核编程的锁竞争进行深入的分析。
为了简化起见,我们先看一个简单的情况,假设有4个对等的任务同时启动运行,假设每个任务刚开始时有一个需要锁保护的操作,耗时为1,每个任务其他部分的耗时为25。这几个任务启动运行后的运行情况如下图所示:
图1:对等任务的锁竞争示意图
在上图中,可以看出第1个任务直接执行到结束,中间没有等待,第2个任务等待了1个时间单位,第3个任务等待了2个时间单位,第3个任务等待了3个时间单位。
这样有3个CPU总计等待了6个时间单位,如果这几个任务是采用OpenMP里的所有任务都在同一点上进行等待到全部任务执行完再向下执行时,那么总的运行时间将和第四个任务一样为29个时间单位,加速系数为:(1+4×25)/ 29 = 3.48即使以4个任务的平均时间27.5来进行计算,加速系数=101/27.5 = 3.67,按照阿姆尔达定律来计算加速系数的话,上述应用中,串行时间为1,并行处理的总时间转化为串行后为100个时间单位,如果放在4核CPU上运行的话,加速系数=p / (1 + (p-1)*f) = 4/(1+(4-1)*1/101) = 404/104 = 3.88。
这就产生了一个奇怪的问题,使用了锁之后,加速系数连阿姆尔达定律计算出来的加速系数都不如,更别说用Gustafson定律计算的加速系数了。
其实可以将上面4个任务的锁竞争情况推广到更一般的情况,假设有锁保护的串行化时间为1,可并行化部分在单核CPU上的运行时间为t,CPU核数为p,那么在p个对成任务同时运行情况下,锁竞争导致的总等待时间为:1+2+…+p = p*(p-1)/2
耗时最多的一个任务所用时间为: p + t/p
使用耗时最多的一个任务所用时间来当作并行运行时间的话,加速系数如下
S(p) = (t+1) / (p + t/p) = p*(t+1) / (p*p+t) (锁竞争下的加速系数公式)
这个公式表明在有锁竞争情况下,如果核数固定情况下,可并行化部分越大,那么加速系数将越大。在并行化时间固定的情况下,如果CPU核数越多,那么加速系数将越小。
还是计算几个实际的例子来说明上面公式的效果:
令t=100, p=4, 加速系数=4×(100 +1)/ (4*4+100) = 3.48
令t=100, p=16, 加速系数=16×(100+1) / (16*16+100) = 4.54
令t=100, p=64, 加速系数=64×(100+1) / (64*64+100) = 1.54
令t=100, p=128, 加速系数=128×(100+1) / (128*128+100) = 0.78
从以上计算可以看出,当核数多到一定的时候,加速系数不仅不增加反而下降,核数增加到128时,加速系数只有0.78,还不如在单核CPU上运行的速度。
上面的例子中,锁保护导致的串行代码是在任务启动时调用的,其实对等任务中在其他地方调用的锁保护的串行代码也是一样的。
对等型任务的锁竞争现象在实际情况中是很常见的,比如服务器软件,通常各个客户端处理任务都是对等的,如果在里面使用了锁的话,那么很容易造成上面说的加速系数随CPU核数增多而下降的现象。
以前的服务器软件一般运行在双CPU或四CPU机器上,所以锁竞争导致的加速系数下降现象不明显,进入多核时代后,随着CPU核数的增多,这个问题将变得很严重,所以多核时代对程序设计提出了新的挑战。以前的多任务下的编程思想放到多核编程上不一定行得通。
所以简单地认为多核编程和以前的多任务编程或并行计算等同的话是不切实际的,在讲串行化难题的那篇文章中提出了一些解决方面的对策,但是那些对策还有待业界继续努力才能做得到。
当然由于目前市面上销售的多核CPU还是双核和四核的,等到16核以上的CPU大规模进入市场可能还有几年时间,相信业界在未来的几年内能够对于上面对等任务上的锁竞争问题找到更好的解决方案。
『本文转载自网络,版权归原作者所有,如有侵权请联系删除』