多核編程中的負(fù)載平衡難題
作者：周偉明
相關(guān)文章鏈接：多核編程中的鎖競(jìng)爭(zhēng)難題
多核編程的幾個(gè)難題及其應(yīng)對(duì)策略（難題一）
OpenMP并行程序設(shè)計(jì)（二）
OpenMP并行程序設(shè)計(jì)（一）
雙核CPU上的快速排序效率
前面 多核編程中的鎖競(jìng)爭(zhēng)難題 這篇文章中講過一個(gè)多核編程中的串行化的難題，這篇文章中再來講解一下多核編程中的另外一個(gè)難題，就是負(fù)載平衡方面的難題。
多核CPU中，要很好地發(fā)揮出多個(gè)CPU的性能的話，必須保證分配到各個(gè)CPU上的任務(wù)有一個(gè)很好的負(fù)載平衡。否則一些CPU在運(yùn)行，另外一些CPU處于空閑，無法發(fā)揮出多核CPU的優(yōu)勢(shì)來。
要實(shí)現(xiàn)一個(gè)好的負(fù)載平衡通常有兩種方案，一種是靜態(tài)負(fù)載平衡，另外一種是動(dòng)態(tài)負(fù)載平衡。
1、靜態(tài)負(fù)載平衡
靜態(tài)負(fù)載平衡中，需要人工將程序分割成多個(gè)可并行執(zhí)行的部分，并且要保證分割成的各個(gè)部分能夠均衡地分布到各個(gè)CPU上運(yùn)行，也就是說工作量要在多個(gè)任務(wù)間進(jìn)行均勻的分配，使得達(dá)到高的加速系數(shù)。
靜態(tài)負(fù)載平衡問題從數(shù)學(xué)上來說是一個(gè)NP完全性問題，Richard M. Karp, Jeffrey D. Ullman, Christos H. Papadimitriou, M. Garey, D. Johnson等人相繼在1972年到1983年間證明了靜態(tài)負(fù)載問題在幾種不同約束條件下的NP完全性。
雖然NP完全性問題在數(shù)學(xué)上是難題，但是這并不是標(biāo)題中所說的難題，因?yàn)镹P完全性問題一般都可以找到很有效的近似算法來解決。
2、動(dòng)態(tài)負(fù)載平衡
動(dòng)態(tài)負(fù)載平衡是在程序的運(yùn)行過程中來進(jìn)行任務(wù)的分配達(dá)到負(fù)載平衡的目的。實(shí)際情況中存在許多不能由靜態(tài)負(fù)載平衡解決的問題，比如一個(gè)大的循環(huán)中，循環(huán)的次數(shù)是由外部輸入的，事先并不知道循環(huán)的次數(shù)，此時(shí)采用靜態(tài)負(fù)載平衡劃分策略就很難實(shí)現(xiàn)負(fù)載平衡。
動(dòng)態(tài)負(fù)載平衡中對(duì)任務(wù)的調(diào)度一般是由系統(tǒng)來實(shí)現(xiàn)的，程序員通常只能選擇動(dòng)態(tài)平衡的調(diào)度策略，不能修改調(diào)度策略，由于實(shí)際任務(wù)中存在很多的不確定因素，調(diào)度算法無法做得很優(yōu)，因此動(dòng)態(tài)負(fù)載平衡有時(shí)可能達(dá)不到既定的負(fù)載平衡要求。
3、負(fù)載平衡的難題在那里？
負(fù)載平衡的難題并不在于負(fù)載平衡的程度要達(dá)到多少，因?yàn)榧词乖诟鱾€(gè)CPU上分配的任務(wù)執(zhí)行時(shí)間存在一些差距，但是隨著CPU核數(shù)的增多總能讓總的執(zhí)行時(shí)間下降，從而使加速系數(shù)隨CPU核數(shù)的增加而增加。
負(fù)載平衡的困難之處在于程序中的可并行執(zhí)行塊很多要靠程序員來劃分，當(dāng)然CPU核數(shù)較少時(shí)，比如雙核或4核，這種劃分并不是很困難。但隨著核數(shù)的增加，劃分的粒度將變得越來越細(xì)，到了16核以上時(shí)，估計(jì)程序員要為如何劃分任務(wù)而抓狂。比如一段順序執(zhí)行的代碼，放到128核的CPU上運(yùn)行，要手工劃分成128個(gè)任務(wù)，其劃分的難度可想而知。
負(fù)載劃分的誤差會(huì)隨著CPU核數(shù)的增加而放大，比如一個(gè)需要16個(gè)時(shí)間單位的程序分到4個(gè)任務(wù)上執(zhí)行，平均每個(gè)任務(wù)上的負(fù)載執(zhí)行時(shí)間為4個(gè)時(shí)間單位，劃分誤差為1個(gè)時(shí)間單位的話，那么加速系數(shù)變成 16/(4+1)=3.2，是理想情況下加速系數(shù) 4的80％。但是如果放到一個(gè)16核CPU上運(yùn)行的話，如果某個(gè)任務(wù)的劃分誤差如果為0.5個(gè)時(shí)間單位的話，那么加速系數(shù)變成16/(1+0.5) = 10.67，只有理想的加速系數(shù)16的66.7%，如果核數(shù)再增加的話，由于誤差的放大，加速系數(shù)相比于理想加速系數(shù)的比例還會(huì)下降。
負(fù)載劃分的難題還體現(xiàn)在CPU和軟件的升級(jí)上，比如在4核CPU上的負(fù)載劃分是均衡的，但到了8核、16核上，負(fù)載也許又變得不均衡了。軟件升級(jí)也一樣，當(dāng)軟件增加功能后，負(fù)載平衡又會(huì)遭到破壞，又需要重新劃分負(fù)載使其達(dá)到平衡，這樣一來軟件設(shè)計(jì)的難度和麻煩大大增加了。
如果使用了鎖的話，一些看起來是均衡的負(fù)載也可能會(huì)由于鎖競(jìng)爭(zhēng)變得不平衡起來，詳細(xì)情況請(qǐng)看：
http://blog.csdn.net/drzhouweiming/archive/2007/04/10/1559718.aspx4、負(fù)載平衡的應(yīng)對(duì)策略
對(duì)于運(yùn)算量較小的軟件，即使放到單核CPU上運(yùn)行速度也很快，負(fù)載平衡做得差一些并沒有太大影響，實(shí)際中負(fù)載平衡要考慮的是大運(yùn)算量和規(guī)模很大的軟件，這些軟件需要在多核上進(jìn)行負(fù)載平衡才能較好地利用多核來提高性能。
對(duì)于大規(guī)模的軟件，負(fù)載平衡方面采取的應(yīng)對(duì)策略是發(fā)展劃分并行塊的宏觀劃分方法，從整個(gè)軟件系統(tǒng)層面來進(jìn)行劃分，而不是象傳統(tǒng)的針對(duì)某些局部的程序和算法來進(jìn)行并行分解，因?yàn)榫植康某绦蛲ǔ６己茈y分解成幾十個(gè)以上的任務(wù)來運(yùn)行。
另外一個(gè)應(yīng)對(duì)策略是在工具層面的，也就是編譯工具能夠協(xié)助人工進(jìn)行并行塊的分解，并找出良好的分解方案來，這方面Intel已經(jīng)作出了一些努力，但是還需要更多的努力讓工具的功能更強(qiáng)大一些才能應(yīng)對(duì)核數(shù)較多時(shí)的情況。
