之前在讲解多核编程的几个问题及对策（问题一）中提到锁竞争会随着CPU核数的增加而使序列化加剧，本文将深入分析多核编程中的锁竞争。为了简单起见，我们先来看一个简单的情况，假设有4个点对点任务同时运行，假设每个任务一开始都有一个需要锁保护的操作，而时间——consuming为1，每个task的其他部分Time-consuming为25。这些task启动后的运行状态如下图所示：图1：点对点任务锁竞争示意图上图如图，可以看出第一个任务直接执行到最后，中间没有等待，第二个任务等了1个时间单位，第3个任务等了2个时间单位，第3个任务等了3个时间单位。这样总共有3个CPU在等待6个时间单位。如果这些任务使用OpenMP中的所有任务都在同一个点等待，直到所有任务都执行完再向下执行，那么总的运行时间就和第四个任务一样，也是29个时间单位，加速系数为：（1+4×25)/29=3.48即使4个任务的平均时间为27.5来计算，加速系数=101/27.5=3.67根据Amurda法计算加速系数的话，在上面的应用中，串行时间为1，串行化后并行处理的总时间换算成100个时间单位。如果在4核CPU上运行，加速系数=p/(1+(p-1)*f)=4/(1+(4-1)*1/101)=404/104=3.88这就产生了一个奇怪的问题，使用锁后，加速度系数甚至Erda定律计算的加速度系数还不如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)（锁竞争下的加速系数公式）这个公式表明在锁竞争的情况下，如果cores固定，可并行部分越大，加速系数越大。在并行化时间固定的情况下，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上跑得快。在上面的例子中，锁保护导致的串行代码在任务启动时被调用。其实peer任务中其他地方调用的锁保护的串行代码是一样的。点对点任务的锁竞争现象在实际情况中非常普遍，比如服务端软件，通常每个客户端平等的处理任务，如果在其中使用锁，很容易造成上述加速因素的一种现象随着CPU内核数量的增加而减少。以往的服务器软件一般运行在双CPU或四CPU机器上，锁竞争带来的加速系数下降并不明显。进入多核时代后，随着CPU核心数量的增加，这个问题会变得非常严重，所以多核时代给程序设计带来了新的挑战。以前的多任务下的编程思路，在多核编程中不一定行得通。因此，简单地认为多核编程等同于以前的多任务编程或并行计算是不现实的。在关于连载问题的文章中，提出了一些对策，但这些对策还需要业界努力。只有这样才能做到。当然，由于目前市面上的多核CPU还是双核和四核的，16核以上的CPU大规模进入市场可能还需要几年时间。相互竞争的问题找到更好的解决方案。原文链接：http://blog.csdn.net/drzhouweiming/article/details/1559718
