隨著多核CPU的出世，多核編程方面的問題將擺上了程序員的日程，有許多老的程序員以為早就有多CPU的機(jī)器，業(yè)界在多CPU機(jī)器上的編程已經(jīng)積累了很多經(jīng)驗(yàn)，多核CPU上的編程應(yīng)該差不多，只要借鑒以前的多任務(wù)編程、并行編程和并行算法方面的經(jīng)驗(yàn)就足夠了。
    我想說的是，多核機(jī)器和以前的多CPU機(jī)器有很大的不同，以前的多CPU機(jī)器都是用在特定領(lǐng)域，比如服務(wù)器，或者一些可以進(jìn)行大型并行計(jì)算的領(lǐng)域，這些領(lǐng)域很容易發(fā)揮出多CPU的優(yōu)勢，而現(xiàn)在多核機(jī)器則是應(yīng)用到普通用戶的各個(gè)層面，特別是客戶端機(jī)器要使用多核CPU，而很多客戶端軟件要想發(fā)揮出多核的并行優(yōu)勢恐怕沒有服務(wù)器和可以進(jìn)行大型并行計(jì)算的特定領(lǐng)域簡單。
 
串行化方面的難題
 
1）加速系數(shù)
 
衡量多處理器系統(tǒng)的性能時(shí)，通常要用到的一個(gè)指標(biāo)叫做加速系數(shù)，定義如下：
S(p) = 使用單處理器執(zhí)行時(shí)間（最好的順序算法）/ 使用具有p個(gè)處理器所需執(zhí)行時(shí)間
 
2）阿姆爾達(dá)定律
 
并行處理時(shí)有一個(gè)阿姆爾達(dá)定律，用方程式表示如下：
S(p) = p / (1 + (p-1)*f)
其中 S(p)表示加速系數(shù)
p表示處理器的個(gè)數(shù)
f表示串行部分所占整個(gè)程序執(zhí)行時(shí)間的比例
當(dāng)f = 5%, p = 20時(shí), S(p) = 10.256左右
當(dāng)f = 5%, p = 100時(shí), S(p) = 16.8左右
 
        也就是說只要有5%的串行部分，當(dāng)處理器個(gè)數(shù)從20個(gè)增加到100個(gè)時(shí)，加速系數(shù)只能從10.256增加到16.8左右，處理器個(gè)數(shù)增加了5倍，速度只增加了60%多一點(diǎn)。即使處理器個(gè)數(shù)增加到無窮多個(gè)，加速系數(shù)的極限值也只有20。
 
        如果按照阿姆爾達(dá)定律的話，可以說多核方面幾乎沒有任何發(fā)展前景，即使軟件中只有1%的不可并行化部分，那么最大加速系統(tǒng)也只能到達(dá)100，再多的CPU也無法提升速度性能。按照這個(gè)定律，可以說多核CPU的發(fā)展讓摩爾定律延續(xù)不了多少年就會到達(dá)極限。
 
3）Gustafson定律
 
        Gustafson提出了和阿姆爾達(dá)定律不同的假設(shè)來證明加速系數(shù)是可以超越阿姆爾達(dá)定律的限制的，Gustafson認(rèn)為軟件中的串行部分是固定的，不會隨規(guī)模的增大而增大，并假設(shè)并行處理部分的執(zhí)行時(shí)間是固定的（服務(wù)器軟件可能就是這樣）。Gustafson定律用公式描述如下：
 
S(p) = p + (1-p)*fts
其中fts表示串行執(zhí)行所占的比例
如果串行比例為5%，處理器個(gè)數(shù)為20個(gè)，那么加速系數(shù)為20＋(1-20)*5%=19.05
如果串行比例為5%，處理器個(gè)數(shù)為100個(gè)，那么加速系數(shù)為100＋(1-100)*5%=95.05
 
        Gustafson定律中的加速系數(shù)幾乎跟處理器個(gè)數(shù)成正比，如果現(xiàn)實(shí)情況符合Gustafson定律的假設(shè)前提的話，那么軟件的性能將可以隨著處理個(gè)數(shù)的增加而增加。
 
4）實(shí)際情況中的串行化分析
 
        阿姆爾達(dá)定律和Gustafson定律的計(jì)算結(jié)果差距如此之大，那么現(xiàn)實(shí)情況到底是符合那一個(gè)定律呢？我個(gè)人認(rèn)為現(xiàn)實(shí)情況中既不會象阿姆爾達(dá)定律那么悲觀，但也不會象Gustafson定律那么樂觀。為什么這樣說呢？還是進(jìn)行一下簡單的分析吧。
首先需要確定軟件中到底有那么內(nèi)容不能并行化，才能估計(jì)出串行部分所占的比例，20世紀(jì)60年代時(shí)，Bernstein就給出了不能進(jìn)行并行計(jì)算的三個(gè)條件：
 
條件1：C1寫某一存儲單元后，C2讀該單元的數(shù)據(jù)。稱為“寫后讀”競爭
條件2：C1讀某一存儲單元數(shù)據(jù)后，C2寫該單元。稱為“讀后寫”競爭
條件1：C1寫某一存儲單元后，C2寫該單元。稱為“寫后寫”競爭
 
        滿足以上三個(gè)條件中的任何一個(gè)都不能進(jìn)行并行執(zhí)行。不幸的是在實(shí)際的軟件中大量存在滿足上述情況的現(xiàn)象，也就是我們常說的共享數(shù)據(jù)要加鎖保護(hù)的問題。
 
        加鎖保護(hù)導(dǎo)致的串行化問題如果在任務(wù)數(shù)量固定的前提下，串行化所占的比例是隨軟件規(guī)模的增大而減小的，但不幸的是它會隨任務(wù)數(shù)量的增加而增加，也就是說處理器個(gè)數(shù)越多，鎖競爭導(dǎo)致的串行化將越嚴(yán)重，從而使得串行化所占的比例隨處理器個(gè)數(shù)的增加而急劇增加。（關(guān)于鎖競爭導(dǎo)致的串行化加劇情況我會在另一篇文章中講解）。所以串行化問題是多核編程面臨的一大難題。
 
5）可能的解決措施
 
        對于串行化方面的難題，首先想到的解決措施就是少用鎖，甚至采用無鎖編程，不過這對普通程序員來說幾乎是難以完成的工作，因?yàn)闊o鎖編程方面的算法太過于復(fù)雜，而且使用不當(dāng)很容易出錯，許多已經(jīng)發(fā)表到專業(yè)期刊上的無鎖算法后來又被證明是錯的，可以想象得到這里面的難度有多大。
 
        第二個(gè)解決方案就是使用原子操作來替代鎖，使用原子操作本質(zhì)上并沒有解決串行化問題，只不過是讓串行化的速度大大提升，從而使得串行化所占執(zhí)行時(shí)間比例大大下降。不過目前芯片廠商提供的原子操作很有限，只能在少數(shù)地方起作用，芯片廠商在這方面可能還需要繼續(xù)努力，提供更多功能稍微強(qiáng)大一些的原子操作來避免更多的地方的鎖的使用。
 
        第三個(gè)解決方案是從設(shè)計(jì)和算法層面來縮小串行化所占的比例。也許需要發(fā)現(xiàn)實(shí)用的并行方面的設(shè)計(jì)模式來縮減鎖的使用，目前業(yè)界在這方面已經(jīng)積累了一定的經(jīng)驗(yàn)，如任務(wù)分解模式，數(shù)據(jù)分解模式，數(shù)據(jù)共享模式，相信隨著多核CPU的大規(guī)模使用將來會有更多的新的有效的并行設(shè)計(jì)模式和算法冒出來。
 
        第四個(gè)解決方案是從芯片設(shè)計(jì)方面來考慮的，由于我對芯片設(shè)計(jì)方面一無所知，所以這個(gè)解決方案也許只是我的一廂情愿的猜想。主要的想法是在芯片層面設(shè)計(jì)一些新的指令，這些指令不象以前單核CPU指令那樣是由單個(gè)CPU完成的，而是由多個(gè)CPU進(jìn)行并行處理完成的一些并行指令，這樣程序員調(diào)用這些并行處理指令編程就象編寫串行化程序一樣，但又充分利用上了多個(gè)CPU的優(yōu)勢。 
負(fù)載平衡問題
多核編程中的鎖競爭難題 這篇文章中講過一個(gè)多核編程中的串行化的難題，這篇文章中再來講解一下多核編程中的另外一個(gè)難題，就是負(fù)載平衡方面的難題。
 
        多核CPU中，要很好地發(fā)揮出多個(gè)CPU的性能的話，必須保證分配到各個(gè)CPU上的任務(wù)有一個(gè)很好的負(fù)載平衡。否則一些CPU在運(yùn)行，另外一些CPU處于空閑，無法發(fā)揮出多核CPU的優(yōu)勢來。
 
        要實(shí)現(xiàn)一個(gè)好的負(fù)載平衡通常有兩種方案，一種是靜態(tài)負(fù)載平衡，另外一種是動態(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、動態(tài)負(fù)載平衡
 
        動態(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ù)載平衡。
 
        動態(tài)負(fù)載平衡中對任務(wù)的調(diào)度一般是由系統(tǒng)來實(shí)現(xiàn)的，程序員通常只能選擇動態(tài)平衡的調(diào)度策略，不能修改調(diào)度策略，由于實(shí)際任務(wù)中存在很多的不確定因素，調(diào)度算法無法做得很優(yōu)，因此動態(tài)負(fù)載平衡有時(shí)可能達(dá)不到既定的負(fù)載平衡要求。
(本文轉(zhuǎn)自電子工程世界：http://www.eeworld.com.cn/mcu/2014/0902/article_16171.html)
 
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ù)載劃分的誤差會隨著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ù)的比例還會下降。
 
        負(fù)載劃分的難題還體現(xiàn)在CPU和軟件的升級上，比如在4核CPU上的負(fù)載劃分是均衡的，但到了8核、16核上，負(fù)載也許又變得不均衡了。軟件升級也一樣，當(dāng)軟件增加功能后，負(fù)載平衡又會遭到破壞，又需要重新劃分負(fù)載使其達(dá)到平衡，這樣一來軟件設(shè)計(jì)的難度和麻煩大大增加了。
 
        如果使用了鎖的話，一些看起來是均衡的負(fù)載也可能會由于鎖競爭變得不平衡起來，詳細(xì)情況請看：http://blog.csdn.net/drzhouweiming/archive/2007/04/10/1559718.aspx
 
4、負(fù)載平衡的應(yīng)對策略
 
        對于運(yùn)算量較小的軟件，即使放到單核CPU上運(yùn)行速度也很快，負(fù)載平衡做得差一些并沒有太大影響，實(shí)際中負(fù)載平衡要考慮的是大運(yùn)算量和規(guī)模很大的軟件，這些軟件需要在多核上進(jìn)行負(fù)載平衡才能較好地利用多核來提高性能。
 
        對于大規(guī)模的軟件，負(fù)載平衡方面采取的應(yīng)對策略是發(fā)展劃分并行塊的宏觀劃分方法，從整個(gè)軟件系統(tǒng)層面來進(jìn)行劃分，而不是象傳統(tǒng)的針對某些局部的程序和算法來進(jìn)行并行分解，因?yàn)榫植康某绦蛲ǔ６己茈y分解成幾十個(gè)以上的任務(wù)來運(yùn)行。
 
        另外一個(gè)應(yīng)對策略是在工具層面的，也就是編譯工具能夠協(xié)助人工進(jìn)行并行塊的分解，并找出良好的分解方案來，這方面Intel已經(jīng)作出了一些努力，但是還需要更多的努力讓工具的功能更強(qiáng)大一些才能應(yīng)對核數(shù)較多時(shí)的情況。
多核編程中的鎖競爭問題
       在前一篇講解多核編程的幾個(gè)難題及其對策（難題一）的文章中提到了鎖競爭會讓串行化隨CPU的核數(shù)增多而加劇的現(xiàn)象，這篇文章就來對多核編程的鎖競爭進(jìn)行深入的分析。
 
       為了簡化起見，我們先看一個(gè)簡單的情況，假設(shè)有4個(gè)對等的任務(wù)同時(shí)啟動運(yùn)行，假設(shè)每個(gè)任務(wù)剛開始時(shí)有一個(gè)需要鎖保護(hù)的操作，耗時(shí)為1，每個(gè)任務(wù)其他部分的耗時(shí)為25。這幾個(gè)任務(wù)啟動運(yùn)行后的運(yùn)行情況如下圖所示： 
 
圖1：對等任務(wù)的鎖競爭示意圖
 
        在上圖中，可以看出第1個(gè)任務(wù)直接執(zhí)行到結(jié)束，中間沒有等待，第2個(gè)任務(wù)等待了1個(gè)時(shí)間單位，第3個(gè)任務(wù)等待了2個(gè)時(shí)間單位，第3個(gè)任務(wù)等待了3個(gè)時(shí)間單位。
 
        這樣有3個(gè)CPU總計(jì)等待了6個(gè)時(shí)間單位，如果這幾個(gè)任務(wù)是采用OpenMP里的所有任務(wù)都在同一點(diǎn)上進(jìn)行等待到全部任務(wù)執(zhí)行完再向下執(zhí)行時(shí)，那么總的運(yùn)行時(shí)間將和第四個(gè)任務(wù)一樣為29個(gè)時(shí)間單位，加速系數(shù)為：（1＋4×25）/ 29 ＝ 3.48即使以4個(gè)任務(wù)的平均時(shí)間27.5來進(jìn)行計(jì)算，加速系數(shù)＝101/27.5 = 3.67，按照阿姆爾達(dá)定律來計(jì)算加速系數(shù)的話，上述應(yīng)用中，串行時(shí)間為1，并行處理的總時(shí)間轉(zhuǎn)化為串行后為100個(gè)時(shí)間單位，如果放在4核CPU上運(yùn)行的話，加速系數(shù)＝p / (1 + (p-1)*f) ＝ 4/(1+(4-1)*1/101) = 404/104 = 3.88。
        這就產(chǎn)生了一個(gè)奇怪的問題，使用了鎖之后，加速系數(shù)連阿姆爾達(dá)定律計(jì)算出來的加速系數(shù)都不如，更別說用Gustafson定律計(jì)算的加速系數(shù)了。
 
        其實(shí)可以將上面4個(gè)任務(wù)的鎖競爭情況推廣到更一般的情況，假設(shè)有鎖保護(hù)的串行化時(shí)間為1，可并行化部分在單核CPU上的運(yùn)行時(shí)間為t，CPU核數(shù)為p，那么在p個(gè)對成任務(wù)同時(shí)運(yùn)行情況下，鎖競爭導(dǎo)致的總等待時(shí)間為：1＋2＋…＋p ＝ p*(p-1)/2
耗時(shí)最多的一個(gè)任務(wù)所用時(shí)間為： p + t/p
 
使用耗時(shí)最多的一個(gè)任務(wù)所用時(shí)間來當(dāng)作并行運(yùn)行時(shí)間的話，加速系數(shù)如下
 
S(p) = (t+1) / (p + t/p) = p*(t+1) / (p*p+t)       （鎖競爭下的加速系數(shù)公式）
 
        這個(gè)公式表明在有鎖競爭情況下，如果核數(shù)固定情況下，可并行化部分越大，那么加速系數(shù)將越大。在并行化時(shí)間固定的情況下，如果CPU核數(shù)越多，那么加速系數(shù)將越小。
 
還是計(jì)算幾個(gè)實(shí)際的例子來說明上面公式的效果：
令t=100, p=4, 加速系數(shù)＝4×(100 +1)/ (4*4+100) = 3.48
令t=100, p=16, 加速系數(shù)＝16×(100+1) / (16*16+100) = 4.54
令t=100, p=64, 加速系數(shù)＝64×(100+1) / (64*64+100) = 1.54
令t=100, p=128, 加速系數(shù)＝128×(100+1) / (128*128+100) = 0.78
 
        從以上計(jì)算可以看出，當(dāng)核數(shù)多到一定的時(shí)候，加速系數(shù)不僅不增加反而下降，核數(shù)增加到128時(shí)，加速系數(shù)只有0.78，還不如在單核CPU上運(yùn)行的速度。
 
        上面的例子中，鎖保護(hù)導(dǎo)致的串行代碼是在任務(wù)啟動時(shí)調(diào)用的，其實(shí)對等任務(wù)中在其他地方調(diào)用的鎖保護(hù)的串行代碼也是一樣的。
 
        對等型任務(wù)的鎖競爭現(xiàn)象在實(shí)際情況中是很常見的，比如服務(wù)器軟件，通常各個(gè)客戶端處理任務(wù)都是對等的，如果在里面使用了鎖的話，那么很容易造成上面說的加速系數(shù)隨CPU核數(shù)增多而下降的現(xiàn)象。
 
        以前的服務(wù)器軟件一般運(yùn)行在雙CPU或四CPU機(jī)器上，所以鎖競爭導(dǎo)致的加速系數(shù)下降現(xiàn)象不明顯，進(jìn)入多核時(shí)代后，隨著CPU核數(shù)的增多，這個(gè)問題將變得很嚴(yán)重，所以多核時(shí)代對程序設(shè)計(jì)提出了新的挑戰(zhàn)。以前的多任務(wù)下的編程思想放到多核編程上不一定行得通。
 
        所以簡單地認(rèn)為多核編程和以前的多任務(wù)編程或并行計(jì)算等同的話是不切實(shí)際的，在講串行化難題的那篇文章中提出了一些解決方面的對策，但是那些對策還有待業(yè)界繼續(xù)努力才能做得到。
 
        當(dāng)然由于目前市面上銷售的多核CPU還是雙核和四核的，等到16核以上的CPU大規(guī)模進(jìn)入市場可能還有幾年時(shí)間，相信業(yè)界在未來的幾年內(nèi)能夠?qū)τ谏厦鎸Φ热蝿?wù)上的鎖競爭問題找到更好的解決方案。