前面多核編程中的鎖競爭難題這篇文章中講過一個多核編程中的串行化的難題，這篇文章中再來講解一下多核編程中的另外一個難題，就是負載平衡方面的難題。

多核CPU中，要很好地發(fā)揮出多個CPU的性能的話，必須保證分配到各個CPU上的任務有一個很好的負載平衡。否則一些CPU在運行，另外一些CPU處于空閑，無法發(fā)揮出多核CPU的優(yōu)勢來。

要實現(xiàn)一個好的負載平衡通常有兩種方案，一種是靜態(tài)負載平衡，另外一種是動態(tài)負載平衡。

1、靜態(tài)負載平衡

靜態(tài)負載平衡中，需要人工將程序分割成多個可并行執(zhí)行的部分，并且要保證分割成的各個部分能夠均衡地分布到各個CPU上運行，也就是說工作量要在多個任務間進行均勻的分配，使得達到高的加速系數(shù)。

靜 態(tài)負載平衡問題從數(shù)學上來說是一個NP完全性問題，Richard M. Karp, Jeffrey D. Ullman, Christos H. Papadimitriou, M. Garey, D. Johnson等人相繼在1972年到1983年間證明了靜態(tài)負載問題在幾種不同約束條件下的NP完全性。

雖然NP完全性問題在數(shù)學上是難題，但是這并不是標題中所說的難題，因為NP完全性問題一般都可以找到很有效的近似算法來解決。      

2、動態(tài)負載平衡

動態(tài)負載平衡是在程序的運行過程中來進行任務的分配達到負載平衡的目的。實際情況中存在許多不能由靜態(tài)負載平衡解決的問題，比如一個大的循環(huán)中，循環(huán)的次數(shù)是由外部輸入的，事先并不知道循環(huán)的次數(shù)，此時采用靜態(tài)負載平衡劃分策略就很難實現(xiàn)負載平衡。

動態(tài)負載平衡中對任務的調(diào)度一般是由系統(tǒng)來實現(xiàn)的，程序員通常只能選擇動態(tài)平衡的調(diào)度策略，不能修改調(diào)度策略，由于實際任務中存在很多的不確定因素，調(diào)度算法無法做得很優(yōu)，因此動態(tài)負載平衡有時可能達不到既定的負載平衡要求。

3、負載平衡的難題在那里？

負載平衡的難題并不在于負載平衡的程度要達到多少，因為即使在各個CPU上分配的任務執(zhí)行時間存在一些差距，但是隨著CPU核數(shù)的增多總能讓總的執(zhí)行時間下降，從而使加速系數(shù)隨CPU核數(shù)的增加而增加。

負載平衡的困難之處在于程序中的可并行執(zhí)行塊很多要靠程序員來劃分，當然CPU核數(shù)較少時，比如雙核或4核，這種劃分并不是很困難。但隨著核數(shù)的增加，劃分 的粒度將變得越來越細，到了16核以上時，估計程序員要為如何劃分任務而抓狂。比如一段順序執(zhí)行的代碼，放到128核的CPU上運行，要手工劃分成128 個任務，其劃分的難度可想而知。

負載劃分的誤差會隨著CPU核數(shù)的增加而放大，比如一個需要16個時間單位的程序分到4個任務上執(zhí)行，平均每個任務上的負載執(zhí)行時間為4個時間單位，劃分誤 差為1個時間單位的話，那么加速系數(shù)變成 16/(4+1)=3.2，是理想情況下加速系數(shù) 4的80％。但是如果放到一個16核CPU上運行的話，如果某個任務的劃分誤差如果為0.5個時間單位的話，那么加速系數(shù)變成16/(1+0.5) = 10.67，只有理想的加速系數(shù)16的66.7%，如果核數(shù)再增加的話，由于誤差的放大，加速系數(shù)相比于理想加速系數(shù)的比例還會下降。

負載劃分的難題還體現(xiàn)在CPU和軟件的升級上，比如在4核CPU上的負載劃分是均衡的，但到了8核、16核上，負載也許又變得不均衡了。軟件升級也一樣， 當軟件增加功能后，負載平衡又會遭到破壞，又需要重新劃分負載使其達到平衡，這樣一來軟件設計的難度和麻煩大大增加了。

如果使用了鎖的話，一些看起來是均衡的負載也可能會由于鎖競爭變得不平衡起來，詳細情況請看：http://blog.csdn.net/drzhouweiming/archive/2007/04/10/1559718.aspx

4、負載平衡的應對策略

對于運算量較小的軟件，即使放到單核CPU上運行速度也很快，負載平衡做得差一些并沒有太大影響，實際中負載平衡要考慮的是大運算量和規(guī)模很大的軟件，這些軟件需要在多核上進行負載平衡才能較好地利用多核來提高性能。

對于大規(guī)模的軟件，負載平衡方面采取的應對策略是發(fā)展劃分并行塊的宏觀劃分方法，從整個軟件系統(tǒng)層面來進行劃分，而不是象傳統(tǒng)的針對某些局部的程序和算法來進行并行分解，因為局部的程序通常都很難分解成幾十個以上的任務來運行。

另外一個應對策略是在工具層面的，也就是編譯工具能夠協(xié)助人工進行并行塊的分解，并找出良好的分解方案來，這方面Intel已經(jīng)作出了一些努力，但是還需要更多的努力讓工具的功能更強大一些才能應對核數(shù)較多時的情況。

原文鏈接：http://blog.csdn.net/drzhouweiming/article/details/1568364