多核編程的幾個難題及其應對策略

發(fā)布時間:2008/6/5 0:00:00 訪問次數:315

　　隨著多核 cpu的出世，多核編程方面的問題將擺上了程序員的日程，有許多老的程序員以為早就有多cpu的機器，業(yè)界在多cpu機器上的編程已經積累了很多經驗，多核cpu上的編程應該差不多，只要借鑒以前的多任務編程、并行編程和并行算法方面的經驗就足夠了。

　　我想說的是，多核機器和以前的多cpu機器有很大的不同，以前的多cpu機器都是用在特定領域，比如服務器，或者一些可以進行大型并行計算的領域，這些領域很容易發(fā)揮出多cpu的優(yōu)勢，而現在多核機器則是應用到普通用戶的各個層面，特別是客戶端機器要使用多核cpu，而很多客戶端軟件要想發(fā)揮出多核的并行優(yōu)勢恐怕沒有服務器和可以進行大型并行計算的特定領域簡單。

　　串行化方面的難題

　　1）加速系數

　　衡量多處理器系統(tǒng)的性能時，通常要用到的一個指標叫做加速系數，定義如下：s(p) = 使用單處理器執(zhí)行時間（最好的順序算法）/ 使用具有p個處理器所需執(zhí)行時間

　　2）阿姆爾達定律

　　并行處理時有一個阿姆爾達定律，用方程式表示如下：

　　s(p) = p / (1 + (p-1)*f)

　　其中 s(p)表示加速系數

　　p表示處理
器的個數

　　f表示串行部分所占整個程序執(zhí)行時間的比例

　　當f = 5%, p = 20時, s(p) = 10.256左右

　　當f = 5%, p = 100時, s(p) = 16.8左右

　　也就是說只要有5%的串行部分，當處理器個數從20個增加到100個時，加速系數只能從10.256增加到16.8左右，處理器個數增加了5倍，速度只增加了60%多一點。即使處理器個數增加到無窮多個，加速系數的極限值也只有20。

　　如果按照阿姆爾達定律的話，可以說多核方面幾乎沒有任何發(fā)展前景，即使軟件中只有1%的不可并行化部分，那么最大加速系統(tǒng)也只能到達100，再多的cpu也無法提升速度性能。按照這個定律，可以說多核cpu的發(fā)展讓摩爾定律延續(xù)不了多少年就會到達極限。

　　3）gustafson定律

　　gustafson提出了和阿姆爾達定律不同的假設來證明加速系數是可以超越阿姆爾達定律的限制的，gustafson認為軟件中的串行部分是固定的，不會隨規(guī)模的增大而增大，并假設并行處理部分的執(zhí)行時間是固定的（服務器軟件可能就是這樣）。gustafson定律用公式描述如下：

　　s(p) = p + (1-p)*fts

　　其中fts表示串行執(zhí)行所占的比例

　　如果串行比例為5%，處理器個數為20個，那么加速系數為20＋(1-20)*5%=19.05

　　如果串行比例為5%，處理器個數為100個，那么加速系數為100＋(1-100)*5%=95.05

　　gustafson定律中的加速系數幾乎跟處理器個數成正比，如果現實情況符合gustafson定律的假設前提的話，那么軟件的性能將可以隨著處理個數的增加而增加。

　　4）實際情況中的串行化分析

　　阿姆爾達定律和gustafson定律的計算結果差距如此之大，那么現實情況到底是符合那一個定律呢？我個人認為現實情況中既不會象阿姆爾達定律那么悲觀，但也不會象gustafson定律那么樂觀。為什么這樣說呢？還是進行一下簡單的分析吧。

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

　　條件1：c1寫某一存儲單元后，c2讀該單元的數據。稱為“寫后讀”競爭

　　條件2：c1讀某一存儲單元數據后，c2寫該單元。稱為“讀后寫”競爭

　　條件1：c1寫某一存儲單元后，c2寫該單元。稱為“寫后寫”競爭

　　滿足以上三個條件中的任何一個都不能進行并行執(zhí)行。不幸的是在實際的軟件中大量存在滿足上述情況的現象，也就是我們常說的共享數據要加鎖保護的問題。

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