多核編程的幾個(gè)難題及其應對策略
——
加入技術(shù)交流群
我想說(shuō)的是，多核機器和以前的多CPU機器有很大的不同，以前的多CPU機器都是用在特定領(lǐng)域，比如服務(wù)器，或者一些可以進(jìn)行大型并行計算的領(lǐng)域，這些領(lǐng)域很容易發(fā)揮出多CPU的優(yōu)勢，而現在多核機器則是應用到普通用戶(hù)的各個(gè)層面，特別是客戶(hù)端機器要使用多核CPU，而很多客戶(hù)端軟件要想發(fā)揮出多核的并行優(yōu)勢恐怕沒(méi)有服務(wù)器和可以進(jìn)行大型并行計算的特定領(lǐng)域簡(jiǎn)單。
這次參加CSDN大會(huì )時(shí)和孟巖先生聊起多核編程時(shí)，孟巖先生對多核編程的前途感覺(jué)到很悲觀(guān)，和去年見(jiàn)到他時(shí)對多核編程的前景看法完全發(fā)生了改變。想來(lái)孟巖先生對多核編程方面有了很深刻的理解，由于時(shí)間問(wèn)題，沒(méi)能和孟巖先生在這方面深入聊下去。在回來(lái)的路上，我重新思考了一下關(guān)于多核編程方面的困難之處，今天回到家趕緊把它寫(xiě)了下來(lái)，貼出來(lái)分享給大家。
難題一：串行化方面的難題
1）加速系數
衡量多處理器系統的性能時(shí)，通常要用到的一個(gè)指標叫做加速系數，定義如下：
S(p) = 使用單處理器執行時(shí)間（最好的順序算法）/ 使用具有p個(gè)處理器所需執行時(shí)間
2）阿姆爾達定律
并行處理時(shí)有一個(gè)阿姆爾達定律，用方程式表示如下：
S(p) = p / (1 + (p-1)*f)
其中 S(p)表示加速系數
p表示處理器的個(gè)數
f表示串行部分所占整個(gè)程序執行時(shí)間的比例
當f = 5%, p = 20時(shí), S(p) = 10.256左右
當f = 5%, p = 100時(shí), S(p) = 16.8左右
也就是說(shuō)只要有5％的串行部分，當處理器個(gè)數從20個(gè)增加到100個(gè)時(shí)，加速系數只能從10.256增加到16.8左右，處理器個(gè)數增加了5倍，速度只增加了60％多一點(diǎn)。即使處理器個(gè)數增加到無(wú)窮多個(gè)，加速系數的極限值也只有20。
如果按照阿姆爾達定律的話(huà)，可以說(shuō)多核方面幾乎沒(méi)有任何發(fā)展前景，即使軟件中只有1％的不可并行化部分，那么最大加速系統也只能到達100，再多的CPU也無(wú)法提升速度性能。按照這個(gè)定律，可以說(shuō)多核CPU的發(fā)展讓摩爾定律延續不了多少年就會(huì )到達極限。
3）Gustafson定律
Gustafson提出了和阿姆爾達定律不同的假設來(lái)證明加速系數是可以超越阿姆爾達定律的限制的，Gustafson認為軟件中的串行部分是固定的，不會(huì )隨規模的增大而增大，并假設并行處理部分的執行時(shí)間是固定的（服務(wù)器軟件可能就是這樣）。Gustafson定律用公式描述如下：
S(p) = p + (1-p)*fts
其中fts表示串行執行所占的比例
如果串行比例為5％，處理器個(gè)數為20個(gè)，那么加速系數為20＋(1-20)*5%=19.05
如果串行比例為5％，處理器個(gè)數為100個(gè)，那么加速系數為100＋(1-100)*5%=95.05
Gustafson定律中的加速系數幾乎跟處理器個(gè)數成正比，如果現實(shí)情況符合Gustafson定律的假設前提的話(huà)，那么軟件的性能將可以隨著(zhù)處理個(gè)數的增加而增加。
4）實(shí)際情況中的串行化分析
阿姆爾達定律和Gustafson定律的計算結果差距如此之大，那么現實(shí)情況到底是符合那一個(gè)定律呢？我個(gè)人認為現實(shí)情況中既不會(huì )象阿姆爾達定律那么悲觀(guān)，但也不會(huì )象Gustafson定律那么樂(lè )觀(guān)。為什么這樣說(shuō)呢？還是進(jìn)行一下簡(jiǎn)單的分析吧。
首先需要確定軟件中到底有那么內容不能并行化，才能估計出串行部分所占的比例，20世紀60年代時(shí)，Bernstein就給出了不能進(jìn)行并行計算的三個(gè)條件：
條件1：C1寫(xiě)某一存儲單元后，C2讀該單元的數據。稱(chēng)為“寫(xiě)后讀”競爭
條件2：C1讀某一存儲單元數據后，C2寫(xiě)該單元。稱(chēng)為“讀后寫(xiě)”競爭
條件1：C1寫(xiě)某一存儲單元后，C2寫(xiě)該單元。稱(chēng)為“寫(xiě)后寫(xiě)”競爭滿(mǎn)足以上三個(gè)條件中的任何一個(gè)都不能進(jìn)行并行執行。不幸的是在實(shí)際的軟件中大量存在滿(mǎn)足上述情況的現象，也就是我們常說(shuō)的共享數據要加鎖保護的問(wèn)題。
加鎖保護導致的串行化問(wèn)題如果在任務(wù)數量固定的前提下，串行化所占的比例是隨軟件規模的增大而減小的，但不幸的是它會(huì )隨任務(wù)數量的增加而增加，也就是說(shuō)處理器個(gè)數越多，鎖競爭導致的串行化將越嚴重，從而使得串行化所占的比例隨處理器個(gè)數的增加而急劇增加。（關(guān)于鎖競爭導致的串行化加劇情況我會(huì )在另一篇文章中講解）。所以串行化問(wèn)題是多核編程面臨的一大難題。
5）可能的解決措施
對于串行化方面的難題，首先想到的解決措施就是少用鎖，甚至采用無(wú)鎖編程，不過(guò)這對普通程序員來(lái)說(shuō)幾乎是難以完成的工作，因為無(wú)鎖編程方面的算法太過(guò)于復雜，而且使用不當很容易出錯，許多已經(jīng)發(fā)表到專(zhuān)業(yè)期刊上的無(wú)鎖算法后來(lái)又被證明是錯的，可以想象得到這里面的難度有多大。
第二個(gè)解決方案就是使用原子操作來(lái)替代鎖，使用原子操作本質(zhì)上并沒(méi)有解決串行化問(wèn)題，只不過(guò)是讓串行化的速度大大提升，從而使得串行化所占執行時(shí)間比例大大下降。不過(guò)目前芯片廠(chǎng)商提供的原子操作很有限，只能在少數地方起作用，芯片廠(chǎng)商在這方面可能還需要繼續努力，提供更多功能稍微強大一些的原子操作來(lái)避免更多的地方的鎖的使用。
第三個(gè)解決方案是從設計和算法層面來(lái)縮小串行化所占的比例。也許需要發(fā)現實(shí)用的并行方面的設計模式來(lái)縮減鎖的使用，目前業(yè)界在這方面已經(jīng)積累了一定的經(jīng)驗，如任務(wù)分解模式，數據分解模式，數據共享模式，相信隨著(zhù)多核CPU的大規模使用將來(lái)會(huì )有更多的新的有效的并行設計模式和算法冒出來(lái)。
第四個(gè)解決方案是從芯片設計方面來(lái)考慮的，由于我對芯片設計方面一無(wú)所知，所以這個(gè)解決方案也許只是我的一廂情愿的猜想。主要的想法是在芯片層面設計一些新的指令，這些指令不象以前單核CPU指令那樣是由單個(gè)CPU完成的，而是由多個(gè)CPU進(jìn)行并行處理完成的一些并行指令，這樣程序員調用這些并行處理指令編程就象編寫(xiě)串行化程序一樣，但又充分利用上了多個(gè)CPU的優(yōu)勢。
作者介紹：周偉明，自由職業(yè)，從事軟件行業(yè)十年有余。目前主要關(guān)注軟件測試、多核編程、軟件設計等基礎方面的內容。寫(xiě)有《多任務(wù)下的數據結構與算法》一書(shū)，目前正在寫(xiě)作《軟件測試實(shí)踐》一書(shū)，計劃在不久的將來(lái)寫(xiě)一本多核編程方面的書(shū)籍。
參考資料：《并行編程模式》Timothy Mattson等著(zhù) 敖富江譯
《并行計算綜論》Jack Dongarra等編著(zhù) 莫則堯等譯
《并行程序設計》Barry Wilkinson等著(zhù) 陸鑫達等譯
《多核程序設計技術(shù)》Shameem Akhter等著(zhù) 李寶峰等譯
《并行算法實(shí)踐》 陳國良等編著(zhù)
linux操作系統文章專(zhuān)題:linux操作系統詳解（linux不再難懂） 加速度計相關(guān)文章:加速度計原理
評論