多核的陷阱：從程序的角度探討計算機的極限

在上兩期的《走進計算機文化史》中我們分別從工程和功耗兩個方面討論了計算機的極限問題，並由此分別引出了摩爾定律及登納德縮放定律。 這一期我們暫時拋開硬體，從程序的角度解釋系統並行化的極限。

上期我們講到，在功耗非線性增長的迫使下，晶元廠商開發出了多核晶元，試圖通過多核來解決之前單核的時鐘頻率增加所帶來的功耗問題。然而這種決定忽略了另外一個很重要的問題。要講清楚這個問題，我們先來講個故事。

從前有一個不知足的地主，之前都是雇一個長工耕田。這個長工也很配合，隨著時間的推移技術越來越好，耕田也越來越快。但有一天這個勞工達到了體能極限，再要他快就該殘了。於是地主就琢磨著他這塊田怎麼能再快點耕完。終於有一天地主下了個血本從市場上又買了另外三個技能相當的長工扔到了田裡，並滿心希望之前一天能耕完的地現在六個小時就能搞定。於是地主六個小時之後去地里一看，瞬間後悔了。因為剛買來的三個長工也不知道自己該做什麼，就坐在邊上看著原先的那位苦逼工作。

故事講到這裡，可能有心的讀者就已經發現了多核處理的問題。就是在此之前的絕大多數程序都是按照串列演算法開發的，而這些程序還不能很好地在多核晶元上並行執行。因為整個程序里並沒有啟用多餘的核進行處理，而這些多餘的核在大多數時間裡也都是空閑的。（當然需要說明的是這種情況只是在執行單個程序時候發生，如果是執行多個不同的程序，那麼多核還是會有效果的。就像如果這個地主有四塊地分別分給買來的四個長工，他們還是可以有效工作的。）

於是學術界和工業開始了又一波對並行化的研究。他們一部分人希望通過設計新的編程語言，讓程序員人工提高程序的並行度。另一部分人則希望通過對編譯器的優化，讓編譯器自動識別程序中可並行的部分並生成可並行的二進位碼。然而雙方的成效都非常有限。可並行的編程語言需要程序員有並行的編程思想，然而這多多少少有違人類本身的邏輯思維方式。同時，並行語言為程序調試帶來了很大的挑戰。使得大規模的並行程序開發變得相當困難。與此同時，編譯器能在程序中找到的可並行部分也相當有限，這也使得自動並行化的效率非常之低。

這麼看來多核晶元真的是一個好的決定嗎？程序的並行極限又在哪裡呢？要解釋這個問題，我們便不得不提到計算機科學界的另一個經驗法則——阿姆達爾定律。

阿姆達爾定律於1967年由IBM360系列機的主要設計者吉因恩·阿姆達爾（Gene Amdahl）首先提出。它代表了處理器並行運算之後效率提升的能力。該定律首先將一個程序分成了可並行和不可並行兩部分，並指出程序中對某一部份進行並行後所能獲得的系統性能改進程度，取決於並行部分被使用的頻率，或所佔總執行時間的比例。換句話說，在並行計算中用多核處理器對單個程序的加速受限於該程序所需的串列時間百分比。比如一個程序中如果有一半是不能被並行的，那麼即便是有無限核數的處理器，該程序能得到的最大加速比也只是兩倍。

阿姆達爾定律給出了下面這一個核心公式，speedup=1/(s+(1-s)/n)。該公式計算了一個程序並行化之後所能帶來的最大加速比。其中 s 為程序串列部分（或不可並行部分）所佔比例；1-s 則為程序可並行部分所佔比例；n為並行處理節點的個數，可以大致理解為處理器的核數。所以如果一整個程序都是可並行的（s = 0），那麼能得到的加速比上限就是 n。相反如果一整個程序都是不可並行的（s = 1），那麼加速比上限就是1。阿姆達爾定律通過該公式指出了多核的有效利用率和程序的可並行部分所佔的百分比是密切相關的。這就像如果地主家的田地是很窄很長的，一次只能通過一個人的，那麼就算買來再多的長工也無濟於事。

阿姆達爾定律的結論給並行化研究的領域蒙上了一層沮喪的陰影，使得該領域像是一個一眼就能看到天花板的研究。而在阿姆達爾定律中，作者使用了兩個設定作為前提。正是這兩個設定讓我們在1988年看到了對並行化研究不一樣的前景。

阿姆達爾定律的第一個假設是固定負載（即計算總量不變）的量化標準。也就是說它沒有考慮到硬體發展帶動下的軟體更新。舉個簡單的例子，上世紀90年代的時候我們用英特爾奔騰處理器跑 Windows95 的操作系統，而到了如今我們有了i9處理器的同時我相信沒誰的電腦里還裝著 Windows95 了。換句話說，長工的技能增加的同時，地主的田地也在擴張嘛。到了上世紀80年代，Sandia 國家實驗室的科學家們在使用1024個處理器時觀察到了3個實際應用程序隨著處理器的增加發生線性加速的現象。於是在阿姆達定律的基礎上，另一個定律由此誕生——古斯塔夫森定律。

古斯塔夫森定律於1988年由約翰.古斯塔夫森（John Gustafson)提出。古斯塔夫森指出，阿姆達爾定律的問題出在它的前提過於理想化。硬體性能的提升會直接導致軟體規模及複雜度提升。即使演算法仍然存在著串列部分，但由於程序規模的不斷擴大，演算法中串列部分所佔比例往往會持續減少。至此，他給出了另外一個公式：Speedup= s +(1-s)n，其中 s 是給定任務中不可並行的時間占實際執行時間的百分比，n 代表並行計算節點個數。並指出在許多實際的應用程序中，因處理器核數的持續增加而得到接近線性的加速效果是可能的。

同古斯塔夫森定律一樣，阿姆達爾定律的另一個設定是假設程序中可並行的部分在實際情況中可以完全被並行。這種設定作為一個純數學模型忽略了可並行化在執行的時候所帶來的開銷。於是，大衛.費舍爾（David. Fisher）於1988年發表論文「Your Favorite Parallel Algorithms Might Not Be as Fast as You Think」[1]，並提出這樣一個理論。如果一個輸入大小為 n 的程序在串列時需要 T(n) 個步驟來完成，那麼該程序被 d 個計算節點（可粗略看作處理器核數）並行之後所需的執行步驟數會以 T(n) 的 d+1 次方根增加。這個結論將邏輯門以及銅線連接的延遲考慮進去，打破了古斯塔夫定律中線性加速效果的可能，並將可並行化的加速上限設在了一個更低卻更現實的高度。同時，在銅線延遲開始超過邏輯門延遲的如今，信號已然無法在一個時鐘周期內被傳達到晶元的所有地方。這也同樣在並行處理的過程中加入了串列依賴[2]。

和之前兩期介紹到的，科學家們試圖以各種新科技突破現有的物理極限不同，在並行化領域裡我們現在所能達到的離阿姆達爾提出的極限還很遠。多數科學家們還在試圖用各種方法去接近阿姆達爾定律所提出的極限。CNFET晶體管的出現大大的改善了內部連接的延遲[3]。英特爾在2013年聲稱其打算用硅光產品代替原有的銅線來連接晶元中的不同核[4]。當然研究領域裡也不乏試圖再次突破現有體系所帶來的物理極限的嘗試。其中最大的項目要數對量子計算機的研究。從底層電路到計算機體系結構，再到上層的演算法設計，學術界和工業界都投入了大量的精力進行研究。然而，雖然對於某些應用, 量子計算機確實在理論上會優於傳統計算機[5]，但現階段量子計算機的整個容錯系統會帶來巨大的開銷，從而大大的抵消了其在理論上能夠帶來的優勢[6]。加之量子計算機從本質上來講也是一個圖靈機，其程序本身的複雜程度使得即便是量子計算機也很難超越費舍爾所提出的並行化加速上限[7]。

雖然從阿姆達爾定律提出之後並行化的研究屢遭質疑，多核技術的出現與流行對計算機體系結構，演算法及程序設計都帶來了重要的影響和新的挑戰。而未來這些方面都需要去適應多核晶元的發展。並行化的研究面臨著諸多的機遇和挑戰，但相信未來會有更大的突破。

往下拉可在留言處發表你的見解

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！