53      阿裏雲  技術社區[雲棲]

硬件的習性

大多數人根據直覺就知道，在係統間傳遞消息要比在單個係統上執行簡單計算更加耗時。不過，在共享同一塊內存的係統的線程間傳遞消息是不是也更加耗 時，這點可就不一定了。本章主要關注共享內存係統中的同步和通信的開銷，隻涉及了一些共享內存並行硬件設計的皮毛，想了解更多信息的讀者，可以翻看 Hennessy和Patterson的經典教材最新版[HP95]。

小問題4.1：為什麼並行軟件程序員需要如此痛苦地學習硬件的低級屬性？如果隻學習更高級些的抽象是不是更簡單，更好，更通用？

2.1. 概述

如果隻是粗略地掃過計算機係統規範手冊，很容易讓人覺得CPU的性能就像在一條清晰跑道上的賽跑，如下圖所示，總是最快的人贏得比賽。

圖2.1 CPU的最佳性能

雖然有一些隻限於CPU的基準測試能夠讓CPU達到上圖中顯示的理想情況，但是典型的程序不像跑道，更像是一條帶有障礙的道路。托摩爾定律的福，最近幾十年間CPU的內部架構發生了急劇的變化。在後麵的章節中將描述這些變化。

2.1.1. CPU流水線

在上世紀80年代初，典型的微處理器在處理下一條指令之前，至少需要取指，解碼和執行3個時鍾周期來完成本條指令。與之形成鮮然對比是，上世紀90 年代末期和本世紀初的CPU可以同時處理多條指令，通過一條很長的“流水線”來控製CPU內部的指令流，圖2.2顯示了這種差異。

圖2.2 新CPU和舊CPU

帶有長流水線的CPU想要達到最佳性能，需要程序給出高度可預測的控製流。代碼主要在緊湊循環中執行的程序，可以提供恰當的控製流，比如大型矩陣或 者向量中做算術計算的程序。此時CPU可以正確預測在大多數情況下，代碼循環結束後的分支走向。在這種程序中，流水線可以一直保持在滿狀態，CPU高速運 行。

另一方麵，如果程序中帶有許多循環，且循環計數都比較小；或者麵向對象的程序中帶有許多虛對象，每個虛對象都可以引用不同的實對象，而這些實對象都 有頻繁被調用的成員函數的不同實現，此時CPU很難或者完全不可能預測某個分支的走向。這樣CPU要麼等待控製流進行到足以知道分支走向的方向時，要麼幹 脆猜測——由於此時程序的控製流不可預測——CPU常常猜錯。在這兩種情況中，流水線都是空的，CPU需要等待流水線被新指令填充，這將大幅降低CPU的 性能，就像圖中的畫一樣。

圖2.3 CPU遭遇pipeline flush

不幸的是，流水線衝刷並不是唯一影響現代CPU運行性能的的障礙。下一節將講述內存引用帶來的危害。

2.1.2. 內存引用

在上世紀80年代，微處理器從內存讀取一個值的時間比執行一條指令的時間短。在2006年，同樣是讀取內存的時間，微處理器可以在這段時間執行上百 條甚至上千條指令。這個差異來源於摩爾定律使得CPU性能的增長速度大大超過內存性能的增長速度，也有部分是由於內存大小的增長速度。比如，70年代的微 型計算機通常帶有4KB主存（是的，是KB，不是MB，更別提GB了），訪問需要一個周期。到2008年，CPU設計者仍然可以構造單周期訪問的4KB內 存，即使是在幾GHz時鍾頻率的係統上。事實上這些設計者經常構造這樣的內存，但他們現在稱唿這種內存為“0級cache”。

雖然現代微型計算機上的大型緩存極大地減少了內存訪問延遲，但是隻有高度可預測的數據訪問模式才能讓緩存發揮最大效用。不幸的是，一般像遍曆鏈表這樣的操作的內存訪問模式非常難以預測——畢竟如果這些模式是可預測的，我們也就不會被指針所困擾了，是吧？

圖2.4 CPU遭遇內存引用

因此，正如圖中顯示的，內存引用常常是影響現代CPU性能的重要因素。

到現在為止，我們隻考慮了CPU在單線程代碼中執行時會遭遇的性能障礙。多線程會為CPU帶來額外的性能障礙，我們將在下麵的章節中接著講述。

2.1.3. 原子操作

其中一種障礙是原子操作。原子操作的概念在某種意義上與CPU流水線上的一次執行一條的匯編操作衝突了。拜硬件設計者的精密設計所賜，現代CPU使 用了很多非常聰明的手段讓這些操作看起來是原子的，即使這些指令實際上不是原子的。不過即使如此，也還是有一些指令是流水線必須延遲甚至需要衝刷，以便一 條原子操作成功完成。

圖2.5 CPU遭遇原子操作

原子指令對性能的影響見上圖。

不幸的是，原子操作通常隻用於數據的單個元素。由於許多並行算法都需要在更新多個數據元素時，保證正確的執行順序，大多數CPU都提供了內存屏障。內存屏障也是影響性能的因素之一，下一節將對它進行描述。

小問題 4.2：什麼樣的機器會允許對多個數據元素進行原子操作？

2.1.4. 內存屏障

內存屏障的更多細節在第12.2節和附錄C中。下麵是一個簡單的基於鎖的臨界區。

1 spin_lock(&mylock);

2 a = a + 1;

3 spin_unlock(&mylock);

如果CPU沒有按照上述語句的順序執行，變量”a”會在沒有得到“mylock”保護的情況下加一，這肯定和我們取”a”的值的目的不一致。為了防 止這種有害的亂序執行，鎖操作原語必須包含或顯式或隱式的內存屏障。由於內存屏障的作用是防止CPU為了提升性能而進行的亂序執行，所以內存屏障幾乎一定 會降低CPU性能，如下圖所示。

圖2.6 CPU遭遇內存屏障

2.1.5. Cache Miss

對多線程程序來說，還有個額外的障礙影響CPU性能提升——“Cache Miss”。正如前文提到的，現代CPU使用大容量的高速緩存來降低由於較低的內存訪問速度帶來的性能懲罰。但是，CPU高速緩存事實上對多CPU間頻繁 訪問的變量起反效果。因為當某個CPU想去更改變量的值時，極有可能該變量的值剛被其他CPU修改過。在這種情況下，變量存在於其他CPU而不是當前 CPU的緩存中，這將導致代價高昂的Cache Miss（詳細內容見附錄C.1節），如上圖所示。

圖2.7 CPU遭遇Cache Miss

2.1.6. I/O操作

緩存未命中可以視為CPU之間的I/O操作，這應該是代價最低廉的I/O操作之一。I/O操作涉及網絡、大容量存儲器，或者（更糟的）人類本身，I/O操作對性能的影響遠遠大於之前幾個章節提到的各種障礙，如下圖所示。

圖2.8 CPU等待I/O完成

共享內存式的並行計算和分布式係統式的並行計算的其中一個不同點是，共享內存式並行計算的程序一般不會處理比緩存未命中更糟的情況，而分布式並行計 算的程序則很可能遭遇網絡通信延遲。這兩種情況的延遲都可看作是通信的代價——在串行程序中所沒有的代價。因此，通信的開銷占執行的實際工作的比率是一項 關鍵設計參數。並行設計的一個主要目標是盡可能的減少這一比率，以達到性能和可擴展性上的目的。

當然，說I/O操作屬於性能障礙是一方麵，說I/O操作對性能的影響非常明顯則是另一方麵。下麵的章節將討論兩者的區別。

2.2. 開銷

本節將概述前一節列出的性能障礙的實際開銷。不過在此之前，需要讀者對硬件體係結構有一個粗略認識，下一小節將對該主題進行闡述。

2.2.1. 硬件體係結構

圖2.9 係統硬件體係結構

上圖是一個粗略的八核計算機係統概要圖。每個管芯有兩個CPU核，每個核帶有自己的高速緩存，管芯內還帶有一個互聯模塊，使管芯內的兩個核可以互相通信。在圖中央的係統互聯模塊可以讓四個管芯相互通信，並且將管芯與主存連接起來。

數據以“緩存線”為單位在係統中傳輸，“緩存線”對應於內存中一個2的冪大小的字節塊，大小通常為32到256字節之間。當CPU從內存中讀取一個 變量到它的寄存器中時，必須首先將包含了該變量的緩存線讀取到CPU高速緩存。同樣地，CPU將寄存器中的一個值存儲到內存時，不僅必須將包含了該值的緩 存線讀到CPU高速緩存，還必須確保沒有其他CPU擁有該緩存線的拷貝。

比如，如果CPU0在對一個變量執行“比較並交換”（CAS）操作，而該變量所在的緩存線在CPU7的高速緩存中，就會發生以下經過簡化的事件序列：

1. CPU0檢查本地高速緩存，沒有找到緩存線。

2. 請求被轉發到CPU0和CPU1的互聯模塊，檢查CPU1的本地高速緩存，沒有找到緩存線。

3. 請求被轉發到係統互聯模塊，檢查其他三個管芯，得知緩存線被CPU6和CPU7所在的管芯持有。

4. 請求被轉發到CPU6和CPU7的互聯模塊，檢查這兩個CPU的高速緩存，在CPU7的高速緩存中找到緩存線。

5. CPU7將緩存線發送給所屬的互聯模塊，並且刷新自己高速緩存中的緩存線。

6. CPU6和CPU7的互聯模塊將緩存線發送給係統互聯模塊。

7. 係統互聯模塊將緩存線發送給CPU0和CPU1的互聯模塊。

8. CPU0和CPU1的互聯模塊將緩存線發送給CPU0的高速緩存。

9. CPU0現在可以對高速緩存中的變量執行CAS操作了。

小問題4.3：這是一個簡化後的事件序列嗎？還有可能更複雜嗎？

小問題4.4：為什麼必須刷新CPU7高速緩存中的緩存線？

2.2.2. 操作的開銷

The overheads of some common operations important to parallel programs are displayed in Table . This system’s clock period rounds to 0.6ns. Although it is not unusual for modern microprocessors to be able to retire multiple instructions per clock period, the operations will be normalized to a full clock period in the third column, labeled “Ratio”. The first thing to note about this table is the large values of many of the ratios. 一些在並行程序中很重要的常見操作開銷如上圖所示。該係統的時鍾周期為0.6ns。雖然在現代微處理器上每時鍾周期retire多條指令並不常見，但是在 表格的第三列，操作被標準化到了整個時鍾周期，稱作“比率”。關於上表，第一個需要注意的是比率的值都很大。

Table: Performance of Synchronization Mechanisms on 4-CPU 1.8GHz AMD Opteron 844 System

最好情況下的CAS操作消耗大概40納秒，超過60個時鍾周期。這裏的“最好情況”是指對某一個變量執行CAS操作的CPU正好是最後一個操作該變 量的CPU，所以對應的緩存線已經在CPU的高速緩存中了，類似地，最好情況下的鎖操作（一個“round trip對”包括獲取鎖和隨後的釋放鎖）消耗超過60納秒，超過100個時鍾周期。這裏的“最好情況”意味著用於表示鎖的數據結構已經在獲取和釋放鎖的 CPU所屬的高速緩存中了。鎖操作比CAS操作更加耗時，是因為鎖操作的數據結構中需要兩個原子操作。

緩存未命中消耗大概140納秒，超過200個時鍾周期。需要在存儲新值時查詢變量的舊值的CAS操作，消耗大概300納秒，超過500個時鍾周期。想想這個，在執行一次CAS操作的時間裏，CPU可以執行500條普通指令。這表明了細粒度鎖的局限性。

小問題4.5：硬件設計者肯定被要求過改進這種情況！為什麼他們滿足於這些單指令操作的糟糕性能呢？

I/O操作開銷更大。一條高性能（也是高價的）光纖通信，比如Infiniand或者其他私有的 interconnects，它的通訊延遲大概有3微秒，在這期間CPU可以執行5000條指令。基於某種標準的通信網絡一般需要一些協議的處理，這更進 一步增加了延遲。當然，物理距離也會增加延遲，理論上光速繞地球一周需要大概130毫秒，這相當於2億個時鍾周期。

小問題4.6：這些數字大的讓人發瘋！我怎麼才能記住它們？

2.3. 硬件的免費午餐

最近幾年並行計算受到大量關注的主要原因是摩爾定律的終結，摩爾定律帶來的單線程程序性能提升（或者叫“免費午餐”[Sut08]）也結束了，見第？？頁的圖。本節簡短地介紹一些硬件設計者可能采用的辦法，這些辦法可以帶來某種形式上的“免費午餐”。

不過，前文中概述了一些影響並發性的硬件障礙。其中對硬件設計者來說最嚴重的一個限製莫過於有限的光速。如第？？的圖所示，在一個1.8GHz的時 鍾周期內，光隻能在真空中傳播大約8厘米遠。在5GHz的時鍾周期內，這個距離更是降到3厘米。這個距離對於一個現代計算機係統的體積來說，還是太小了 點。

更糟糕的是，電子在矽中的移動速度比真空中的光慢3到30倍，and common clocked logic constructs run still more slowly, 比如，內存引用需要在將請求發送給係統的其他部分前，等待查找本地緩存操作結束。此外，相對低速和高耗電的驅動器需要將電信號從一個矽製管芯傳輸到另一個 管芯，比如CPU和主存間的通信。

不過，以下（包括硬件和軟件的）技術也許可以改善這一情況：

1. 3D集成，

2. 新材料和新工藝，

3. 用光來替換電子，

4. 專用加速器，

5. 已有的並行計算軟件。

在下麵的小節中將會分別介紹這些技術。

2.3.1. 3D集成

不過，由於時鍾邏輯級別造成的延遲是無法通過3D集成的方式降低的，並且必須解決諸如生產、測試、電源和散熱等3D集成中的重大問題。散熱問題需要 用基於鑽石的半導體來解決，鑽石是熱的良好導體，但卻是電的絕緣體。據說生成大型單晶體鑽石仍然很困難，更別說將鑽石切割成晶圓了。另外，看起來上述這些 技術不大可能讓性能出現指數級增長，如同某些人習慣的那樣（這句翻譯的爛啊）。這就是說，還必須走上Jim Gray最新的smoking hairy golf balls。

2.3.2. 新材料和新工藝

據說斯蒂芬·霍金曾經聲稱半導體製造商麵臨兩個基本問題：（1）有限的光速，（2）物質的原子本質。半導體製造商很有可能已經逼近這兩個限製，不過有一些研究報告和開發過程關注於如何規避這兩個基本閑置。

其中一個規避物質的原子本質的辦法是一種稱為“high-K”絕緣體材料，這種材料允許較大的設備模擬較小型設備的電氣 屬性。這種材料存在一些嚴重的生產困難，但是能讓研究的前沿再向前推進一步。另一個比較奇異的規避方法，根據電子可以存在於多個能級之上的事實，在電子中 存儲多個二進製位。不過這種方法還有待觀察，確定能否在生產的半導體設備中穩定工作。

還有一種稱為“量子點”的規避方法，使得可以製造體積小得多的半導體設備，不過該方法還處於研究階段。

雖然光速是一個很難跨越的限製，但是半導體設備更多的是受限於電子移動的速度，而非光速，在半導體材料中移動的電子速度 僅是真空中光速的3%到30%。在半導體設備間用銅來連接是一種提升電子移動速度的方法，並且出現其他技術讓電子移動速度接近光速的可能性是很大的。另 外，還有一些實驗用微小的光纖作為芯片內和芯片間的傳輸通道，因為在玻璃中的光速能達到真空中光速的60%還多。這種方法存在的一個問題是光電/電光轉換 的效率，會產生電能消耗和散熱問題。

這也就是說，除開在物理學領域的基礎性進展以外，任何讓數據流傳輸速度出現指數級增長的想法都受限於真空中的光速。

2.3.3. 專用加速器

用通用CPU來處理某個專門問題，通常會將大量的時間和能源消耗在only tangentially related to the problem at hand.比如，當對一對向量進行點積操作時，通用CPU一般會使用一個帶循環計數的循環（一般是展開的）。對指令解碼、增加循環計數、測試計數和跳轉回 循環的開始處，這些操作在某種意義上來說都是無用功：真正的目標是計算兩個向量對應元素的乘積。因此，在硬件上設計一個專用於向量乘法的部件會讓這項工作 做的既快速又節能。

這就是在很多商用微處理器上出現向量指令的原因。這些指令可以同時操作多個數據，能讓點積計算減少解碼指令消耗和循環開銷。

類似的，專用硬件可以更有效地進行加密/解密、壓縮/解壓縮、編碼/解碼和許多其他的任務。不過不幸的是，這種效率提升不是免費的。包含特殊硬件的 計算機係統需要更多的晶體管，即使在不用時也會帶來能源消耗。軟件也必須進行修改以利用專用硬件的長處，同時這種專門硬件又必須足夠通用，這樣高昂的 up-front設計費用才能攤到足夠多的用戶身上，讓專用硬件的價錢變得可以承受。部分由於以上經濟考慮，專用硬件到目前為止隻在幾個領域出現，包括圖 形處理（GPU），矢量處理器（MMX、SSE和VMX指令），以及相對規模較小的加密領域。

不過，隨著摩爾定律帶來的單線程性能提升的結束，我們可以安全的預測：未來各種各樣的專用硬件會大大增加。

2.3.4. 現有的並行軟件

雖然多核CPU曾經讓計算機行業驚訝了一把，但是事實上基於共享內存的並行計算機已經商用了超過半個世紀了。這段時間足以讓一些重要的並行軟件登上 舞台，事實也確實如此。並行操作係統已經非常常見了，比如並行線程庫，並行關係數據庫管理係統和並行數值計算軟件。這些現有的並行軟件在解決我們可能遇見 的並行難題上已經走了很長一段路。

也許最常見的例子是並行關係數據庫管理係統。它和單線程程序不同，並行關係數據庫管理係統一般用高級腳本語言書寫，並發地訪問位於中心的關係數據庫。在現在的高度並行化係統中，隻有數據庫是真正需要直接處理並行化的。因此它運用了許多非常好的技術。

2.4. 軟件設計Implication

表2.1上的比率值至關重要，因為它們限製了並行計算程序的效率。為了弄清這點，我們假設一款並行計算程序使用了CAS操作來進行線程間通信。假設 進行通信的線程不是與自身而主要是與其他線程通信，那麼CAS操作一般會涉及到緩存未命中。進一步假設對應每個CAS通信操作的工作需要消耗300納秒， 這足夠執行幾個浮點transendental函數了。其中一半的執行時間消耗在CAS通信操作上！這也意味著有兩個CPU的係統運行這樣一個並行程序的 速度，並不比單CPU係統運行一個串行執行程序的速度快。

在分布式係統中結果還會更糟糕，因為單次通信操作的延遲時間可能和幾千條甚至上百萬條浮點操作的時間一樣長。這就說明了會產生大量工作量的通信操作應該盡可能減少（通順嗎？）

小問題2.7：既然分布式係統的通信操作代價如此昂貴，為什麼人們還要使用它？

這一課應該非常明了：並行算法必須將每個線程設計成盡可能獨立運行的線程。越少使用線程間通信手段，比如原子操作、鎖或者其它消息傳遞方法，應用程 序的性能和可擴展性就會更好。簡而言之，想要達到優秀的並行性能和可擴展性，就意味著在並行算法和實現中掙紮，小心的選擇數據結構和算法，使用現有的並行 軟件和環境，或者將並行問題轉換成已經有並行解決方案存在的問題。

下一章將討論可以提升性能和可擴展性的設計紀律。

文章轉自 並發編程網-ifeve.com

最後更新：2017-05-22 15:33:51

  上一篇：  Adopt Open JDK官方文檔（八）OpenJDK 項目介紹

  下一篇：  Adopt Open JDK官方文檔(四)基於虛擬機的編譯環境