多核編程的幾個難題及其應(yīng)對策略

       隨著多核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)用到普通用戶的各個層面，特別是客戶端機(jī)器要使用多核CPU，而很多客戶端軟件要想發(fā)揮出多核的并行優(yōu)勢恐怕沒有服務(wù)器和可以進(jìn)行大型并行計(jì)算的特定領(lǐng)域簡單。

      這次參加CSDN大會時(shí)和孟巖先生聊起多核編程時(shí)，孟巖先生對多核編程的前途感覺到很悲觀，和去年見到他時(shí)對多核編程的前景看法完全發(fā)生了改變。想來孟巖先生對多核編程方面有了很深刻的理解，由于時(shí)間問題，沒能和孟巖先生在這方面深入聊下去。在回來的路上，我重新思考了一下關(guān)于多核編程方面的困難之處，今天回到家趕緊把它寫了下來，貼出來分享給大家。

      難題一：串行化方面的難題
     1）加速系數(shù)
     衡量多處理器系統(tǒng)的性能時(shí)，通常要用到的一個指標(biāo)叫做加速系數(shù)，定義如下：
S(p) = 使用單處理器執(zhí)行時(shí)間（最好的順序算法）/ 使用具有p個處理器所需執(zhí)行時(shí)間
     2）阿姆爾達(dá)定律
     并行處理時(shí)有一個阿姆爾達(dá)定律，用方程式表示如下：
S(p) = p / (1 + (p-1)*f)
其中 S(p)表示加速系數(shù)
p表示處理器的個數(shù)
f表示串行部分所占整個程序執(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)處理器個數(shù)從20個增加到100個時(shí)，加速系數(shù)只能從10.256增加到16.8左右，處理器個數(shù)增加了5倍，速度只增加了60％多一點(diǎn)。即使處理器個數(shù)增加到無窮多個，加速系數(shù)的極限值也只有20。
 
      如果按照阿姆爾達(dá)定律的話，可以說多核方面幾乎沒有任何發(fā)展前景，即使軟件中只有1％的不可并行化部分，那么最大加速系統(tǒng)也只能到達(dá)100，再多的CPU也無法提升速度性能。按照這個定律，可以說多核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％，處理器個數(shù)為20個，那么加速系數(shù)為20＋(1-20)*5%=19.05
如果串行比例為5％，處理器個數(shù)為100個，那么加速系數(shù)為100＋(1-100)*5%=95.05
Gustafson定律中的加速系數(shù)幾乎跟處理器個數(shù)成正比，如果現(xiàn)實(shí)情況符合Gustafson定律的假設(shè)前提的話，那么軟件的性能將可以隨著處理個數(shù)的增加而增加。

      4）實(shí)際情況中的串行化分析
阿姆爾達(dá)定律和Gustafson定律的計(jì)算結(jié)果差距如此之大，那么現(xiàn)實(shí)情況到底是符合那一個定律呢？我個人認(rèn)為現(xiàn)實(shí)情況中既不會象阿姆爾達(dá)定律那么悲觀，但也不會象Gustafson定律那么樂觀。為什么這樣說呢？還是進(jìn)行一下簡單的分析吧。 


      首先需要確定軟件中到底有那么內(nèi)容不能并行化，才能估計(jì)出串行部分所占的比例，20世紀(jì)60年代時(shí)，Bernstein就給出了不能進(jìn)行并行計(jì)算的三個條件：


      條件1：C1寫某一存儲單元后，C2讀該單元的數(shù)據(jù)。稱為“寫后讀”競爭
      條件2：C1讀某一存儲單元數(shù)據(jù)后，C2寫該單元。稱為“讀后寫”競爭
      條件1：C1寫某一存儲單元后，C2寫該單元。稱為“寫后寫”競爭滿足以上三個條件中的任何一個都不能進(jìn)行并行執(zhí)行。不幸的是在實(shí)際的軟件中大量存在滿足上述情況的現(xiàn)象，也就是我們常說的共享數(shù)據(jù)要加鎖保護(hù)的問題。


      加鎖保護(hù)導(dǎo)致的串行化問題如果在任務(wù)數(shù)量固定的前提下，串行化所占的比例是隨軟件規(guī)模的增大而減小的，但不幸的是它會隨任務(wù)數(shù)量的增加而增加，也就是說處理器個數(shù)越多，鎖競爭導(dǎo)致的串行化將越嚴(yán)重，從而使得串行化所占的比例隨處理器個數(shù)的增加而急劇增加。（關(guān)于鎖競爭導(dǎo)致的串行化加劇情況我會在另一篇文章中講解）。所以串行化問題是多核編程面臨的一大難題。

      5）可能的解決措施


      對于串行化方面的難題，首先想到的解決措施就是少用鎖，甚至采用無鎖編程，不過這對普通程序員來說幾乎是難以完成的工作，因?yàn)闊o鎖編程方面的算法太過于復(fù)雜，而且使用不當(dāng)很容易出錯，許多已經(jīng)發(fā)表到專業(yè)期刊上的無鎖算法后來又被證明是錯的，可以想象得到這里面的難度有多大。


      第二個解決方案就是使用原子操作來替代鎖，使用原子操作本質(zhì)上并沒有解決串行化問題，只不過是讓串行化的速度大大提升，從而使得串行化所占執(zhí)行時(shí)間比例大大下降。不過目前芯片廠商提供的原子操作很有限，只能在少數(shù)地方起作用，芯片廠商在這方面可能還需要繼續(xù)努力，提供更多功能稍微強(qiáng)大一些的原子操作來避免更多的地方的鎖的使用。

      第三個解決方案是從設(shè)計(jì)和算法層面來縮小串行化所占的比例。也許需要發(fā)現(xiàn)實(shí)用的并行方面的設(shè)計(jì)模式來縮減鎖的使用，目前業(yè)界在這方面已經(jīng)積累了一定的經(jīng)驗(yàn)，如任務(wù)分解模式，數(shù)據(jù)分解模式，數(shù)據(jù)共享模式，相信隨著多核CPU的大規(guī)模使用將來會有更多的新的有效的并行設(shè)計(jì)模式和算法冒出來。


      第四個解決方案是從芯片設(shè)計(jì)方面來考慮的，由于我對芯片設(shè)計(jì)方面一無所知，所以這個解決方案也許只是我的一廂情愿的猜想。主要的想法是在芯片層面設(shè)計(jì)一些新的指令，這些指令不象以前單核CPU指令那樣是由單個CPU完成的，而是由多個CPU進(jìn)行并行處理完成的一些并行指令，這樣程序員調(diào)用這些并行處理指令編程就象編寫串行化程序一樣，但又充分利用上了多個CPU的優(yōu)勢。
 
      作者介紹：周偉明，自由職業(yè)，從事軟件行業(yè)十年有余。目前主要關(guān)注軟件測試、多核編程、軟件設(shè)計(jì)等基礎(chǔ)方面的內(nèi)容。寫有《多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法》一書，目前正在寫作《軟件測試實(shí)踐》一書，計(jì)劃在不久的將來寫一本多核編程方面的書籍。
 
      參考資料：《并行編程模式》Timothy Mattson等著 敖富江譯
         《并行計(jì)算綜論》Jack Dongarra等編著 莫則堯等譯 
         《并行程序設(shè)計(jì)》Barry Wilkinson等著 陸鑫達(dá)等譯 
         《多核程序設(shè)計(jì)技術(shù)》Shameem Akhter等著 李寶峰等譯
         《并行算法實(shí)踐》 陳國良等編著

linux操作系統(tǒng)文章專題:linux操作系統(tǒng)詳解（linux不再難懂）
加速度計(jì)相關(guān)文章:加速度計(jì)原理