大多數人根據直覺就知道，在系統間傳遞消息要比在單個系統上執行簡單計算更加耗時。不過，在共享同一塊記憶體的系統的線程間傳遞消息是不是也更加耗時，這點可就不一定了。本章主要關注共享記憶體系統中的同步和通信的開銷，隻涉及了一些共享記憶體并行硬體設計的皮毛，想了解更多資訊的讀者，可以翻看Hennessy和Patterson的經典教材最新版[HP95]。
小問題：為什麼并行軟體程式員需要如此痛苦地學習硬體的低級屬性？如果隻學習更進階些的抽象是不是更簡單，更好，更通用？
概述
如果隻是粗略地掃過計算機系統規範手冊，很容易讓人覺得CPU的性能就像在一條清晰跑道上的賽跑，如下圖所示，總是最快的人赢得比賽。
雖然有一些隻限于CPU的基準測試能夠讓CPU達到上圖中顯示的理想情況，但是典型的程式不像跑道，更像是一條帶有障礙的道路。托摩爾定律的福，最近幾十年間CPU的内部架構發生了急劇的變化。在後面的章節中将描述這些變化。
CPU流水線
在上世紀80年代初，典型的微處理器在處理下一條指令之前，至少需要取指，解碼和執行3個時鐘周期來完成本條指令。與之形成鮮然對比是，上世紀90年代末期和本世紀初的CPU可以同時處理多條指令，通過一條很長的“流水線”來控制CPU内部的指令流，圖2.2顯示了這種差異。
帶有長流水線的CPU想要達到最佳性能，需要程式給出高度可預測的控制流。代碼主要在緊湊循環中執行的程式，可以提供恰當的控制流，比如大型矩陣或者向量中做算術計算的程式。此時CPU可以正确預測在大多數情況下，代碼循環結束後的分支走向。在這種程式中，流水線可以一直保持在滿狀态，CPU高速運作。
另一方面，如果程式中帶有許多循環，且循環計數都比較小；或者面向對象的程式中帶有許多虛對象，每個虛對象都可以引用不同的實對象，而這些實對象都有頻繁被調用的成員函數的不同實作，此時CPU很難或者完全不可能預測某個分支的走向。這樣CPU要麼等待控制流進行到足以知道分支走向的方向時，要麼幹脆猜測——由于此時程式的控制流不可預測——CPU常常猜錯。在這兩種情況中，流水線都是空的，CPU需要等待流水線被新指令填充，這将大幅降低CPU的性能，就像圖中的畫一樣。
不幸的是，流水線沖刷并不是唯一影響現代CPU運作性能的的障礙。下一節将講述記憶體引用帶來的危害。
記憶體引用
在上世紀80年代，微處理器從記憶體讀取一個值的時間比執行一條指令的時間短。在2006年，同樣是讀取記憶體的時間，微處理器可以在這段時間執行上百條甚至上千條指令。這個差異來源于摩爾定律使得CPU性能的增長速度大大超過記憶體性能的增長速度，也有部分是由于記憶體大小的增長速度。比如，70年代的微型計算機通常帶有4KB主存（是的，是KB，不是MB，更别提GB了），通路需要一個周期。到2008年，CPU設計者仍然可以構造單周期通路的4KB記憶體，即使是在幾GHz時鐘頻率的系統上。事實上這些設計者經常構造這樣的記憶體，但他們現在稱呼這種記憶體為“0級cache”。
雖然現代微型計算機上的大型緩存極大地減少了記憶體通路延遲，但是隻有高度可預測的資料通路模式才能讓緩存發揮最大效用。不幸的是，一般像周遊連結清單這樣的操作的記憶體通路模式非常難以預測——畢竟如果這些模式是可預測的，我們也就不會被指針所困擾了，是吧？
是以，正如圖中顯示的，記憶體引用常常是影響現代CPU性能的重要因素。
到現在為止，我們隻考慮了CPU在單線程代碼中執行時會遭遇的性能障礙。多線程會為CPU帶來額外的性能障礙，我們将在下面的章節中接着講述。
原子操作
其中一種障礙是原子操作。原子操作的概念在某種意義上與CPU流水線上的一次執行一條的彙編操作沖突了。拜硬體設計者的精密設計所賜，現代CPU使用了很多非常聰明的手段讓這些操作看起來是原子的，即使這些指令實際上不是原子的。不過即使如此，也還是有一些指令是流水線必須延遲甚至需要沖刷，以便一條原子操作成功完成。
原子指令對性能的影響見上圖。
不幸的是，原子操作通常隻用于資料的單個元素。由于許多并行算法都需要在更新多個資料元素時，保證正确的執行順序，大多數CPU都提供了記憶體屏障。記憶體屏障也是影響性能的因素之一，下一節将對它進行描述。
小問題：什麼樣的機器會允許對多個資料元素進行原子操作？
記憶體屏障
下面是一個簡單的基于鎖的臨界區。
spin_lock(&mylock);
a = a + 1;
spin_unlock(&mylock);
如果CPU沒有按照上述語句的順序執行，變量”a”會在沒有得到“mylock”保護的情況下加一，這肯定和我們取”a”的值的目的不一緻。為了防止這種有害的亂序執行，鎖操作原語必須包含或顯式或隐式的記憶體屏障。由于記憶體屏障的作用是防止CPU為了提升性能而進行的亂序執行，是以記憶體屏障幾乎一定會降低CPU性能，如下圖所示。
Cache Miss
對多線程程式來說，還有個額外的障礙影響CPU性能提升——“Cache Miss”。正如前文提到的，現代CPU使用大容量的高速緩存來降低由于較低的記憶體通路速度帶來的性能懲罰。但是，CPU高速緩存事實上對多CPU間頻繁通路的變量起反效果。因為當某個CPU想去更改變量的值時，極有可能該變量的值剛被其他CPU修改過。在這種情況下，變量存在于其他CPU而不是目前CPU的緩存中，這将導緻代價高昂的Cache Miss。如下圖所示。
I/O操作
緩存未命中可以視為CPU之間的I/O操作，這應該是代價最低廉的I/O操作之一。I/O操作涉及網絡、大容量存儲器，或者（更糟的）人類本身，I/O操作對性能的影響遠遠大于之前幾個章節提到的各種障礙，如下圖所示。
共享記憶體式的并行計算和分布式系統式的并行計算的其中一個不同點是，共享記憶體式并行計算的程式一般不會處理比緩存未命中更糟的情況，而分布式并行計算的程式則很可能遭遇網絡通信延遲。這兩種情況的延遲都可看作是通信的代價——在串行程式中所沒有的代價。是以，通信的開銷占執行的實際工作的比率是一項關鍵設計參數。并行設計的一個主要目标是盡可能的減少這一比率，以達到性能和可擴充性上的目的。
當然，說I/O操作屬于性能障礙是一方面，說I/O操作對性能的影響非常明顯則是另一方面。下面的章節将讨論兩者的差別。
開銷
本節将概述前一節列出的性能障礙的實際開銷。不過在此之前，需要讀者對硬體體系結構有一個粗略認識，下一小節将對該主題進行闡述。
硬體體系結構
上圖是一個粗略的八核計算機系統概要圖。每個管芯有兩個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操作了。
小問題：這是一個簡化後的事件序列嗎？還有可能更複雜嗎？
小問題：為什麼必須重新整理CPU7高速緩存中的緩存線？
操作的開銷
一些在并行程式中很重要的常見操作開銷如下所示。該系統的時鐘周期為0.6ns。雖然在現代微處理器上每時鐘周期retire多條指令并不常見，但是在表格的第三列，操作被标準化到了整個時鐘周期，稱作“比率”。關于這個表格，第一個需要注意的是比率的值都很大。
4-CPU 1.8GHz AMD Opteron 844系統
| 操作 | 開銷(ns) | 比率 |
| Clock period | 0. | 1.0 |
| Best-case CAS | 37.9 | 63.2 |
| Best-case lock | 65.6 | 109.3 |
| Single cache miss | 139.5 | 232.5 |
| CAS cache miss | 306.0 | 510.0 |
| Comms fabric | 3,000 | 5,000 |
| Global Comms | 130,000,000 | 216,000,000 |
最好情況下的CAS操作消耗大概40納秒，超過60個時鐘周期。這裡的“最好情況”是指對某一個變量執行CAS操作的CPU正好是最後一個操作該變量的CPU，是以對應的緩存線已經在CPU的高速緩存中了，類似地，最好情況下的鎖操作（一個“round trip對”包括擷取鎖和随後的釋放鎖）消耗超過60納秒，超過100個時鐘周期。這裡的“最好情況”意味着用于表示鎖的資料結構已經在擷取和釋放鎖的CPU所屬的高速緩存中了。鎖操作比CAS操作更加耗時，是因為鎖操作的資料結構中需要兩個原子操作。
緩存未命中消耗大概140納秒，超過200個時鐘周期。需要在存儲新值時查詢變量的舊值的CAS操作，消耗大概300納秒，超過500個時鐘周期。想想這個，在執行一次CAS操作的時間裡，CPU可以執行500條普通指令。這表明了細粒度鎖的局限性。
小問題：硬體設計者肯定被要求過改進這種情況！為什麼他們滿足于這些單指令操作的糟糕性能呢？
I/O操作開銷更大。一條高性能（也是高價的）光纖通信，比如Infiniand或者其他私有的 interconnects，它的通訊延遲大概有3微秒，在這期間CPU可以執行5000條指令。基于某種标準的通信網絡一般需要一些協定的處理，這更進一步增加了延遲。當然，實體距離也會增加延遲，理論上光速繞地球一周需要大概130毫秒，這相當于2億個時鐘周期。
小問題：這些數字大的讓人發瘋！我怎麼才能記住它們？
硬體的免費午餐
最近幾年并行計算受到大量關注的主要原因是摩爾定律的終結，摩爾定律帶來的單線程程式性能提升（或者叫“免費午餐”[Sut08]）也結束了。本節簡短地介紹一些硬體設計者可能采用的辦法，這些辦法可以帶來某種形式上的“免費午餐”。
不過，前文中概述了一些影響并發性的硬體障礙。其中對硬體設計者來說最嚴重的一個限制莫過于有限的光速。在一個1.8GHz的時鐘周期内，光隻能在真空中傳播大約8厘米遠。在5GHz的時鐘周期内，這個距離更是降到3厘米。這個距離對于一個現代計算機系統的體積來說，還是太小了點。
更糟糕的是，電子在矽中的移動速度比真空中的光慢3到30倍，比如，記憶體引用需要在将請求發送給系統的其他部分前，等待查找本地緩存操作結束。此外，相對低速和高耗電的驅動器需要将電信号從一個矽制管芯傳輸到另一個管芯，比如CPU和主存間的通信。
不過，以下（包括硬體和軟體的）技術也許可以改善這一情況：
1. 3D內建，
2. 新材料和新工藝，
3. 用光來替換電子，
4. 專用加速器，
5. 已有的并行計算軟體。
在下面的小節中将會分别介紹這些技術。
3D內建
不過，由于時鐘邏輯級别造成的延遲是無法通過3D內建的方式降低的，并且必須解決諸如生産、測試、電源和散熱等3D內建中的重大問題。散熱問題需要用基于鑽石的半導體來解決，鑽石是熱的良好導體，但卻是電的絕緣體。據說生成大型單晶體鑽石仍然很困難，更别說将鑽石切割成晶圓了。另外，看起來上述這些技術不大可能讓性能出現指數級增長，如同某些人習慣的那樣。
新材料和新工藝
據說斯蒂芬·霍金曾經聲稱半導體制造商面臨兩個基本問題：（1）有限的光速，（2）物質的原子本質。半導體制造商很有可能已經逼近這兩個限制，不過有一些研究報告和開發過程關注于如何規避這兩個基本閑置。
其中一個規避物質的原子本質的辦法是一種稱為“high-K”絕緣體材料，這種材料允許較大的裝置模拟較小型裝置的電氣屬性。這種材料存在一些嚴重的生産困難，但是能讓研究的前沿再向前推進一步。另一個比較奇異的規避方法，根據電子可以存在于多個能級之上的事實，在電子中存儲多個二進制位。不過這種方法還有待觀察，确定能否在生産的半導體裝置中穩定工作。
還有一種稱為“量子點”的規避方法，使得可以制造體積小得多的半導體裝置，不過該方法還處于研究階段。
雖然光速是一個很難跨越的限制，但是半導體裝置更多的是受限于電子移動的速度，而非光速，在半導體材料中移動的電子速度僅是真空中光速的3%到30%。在半導體裝置間用銅來連接配接是一種提升電子移動速度的方法，并且出現其他技術讓電子移動速度接近光速的可能性是很大的。另外，還有一些實驗用微小的光纖作為晶片内和晶片間的傳輸通道，因為在玻璃中的光速能達到真空中光速的60%還多。這種方法存在的一個問題是光電/電光轉換的效率，會産生電能消耗和散熱問題。
這也就是說，除開在實體學領域的基礎性進展以外，任何讓資料流傳輸速度出現指數級增長的想法都受限于真空中的光速。
專用加速器
用通用CPU來處理某個專門問題，通常會将大量的時間和能源消耗在一些與目前問題無關的事項上。比如，當對一對向量進行點積操作時，通用CPU一般會使用一個帶循環計數的循環（一般是展開的）。對指令解碼、增加循環計數、測試計數和跳轉回循環的開始處，這些操作在某種意義上來說都是無用功：真正的目标是計算兩個向量對應元素的乘積。是以，在硬體上設計一個專用于向量乘法的部件會讓這項工作做的既快速又節能。
這就是在很多商用微處理器上出現向量指令的原因。這些指令可以同時操作多個資料，能讓點積計算減少解碼指令消耗和循環開銷。
類似的，專用硬體可以更有效地進行加密/解密、壓縮/解壓縮、編碼/解碼和許多其他的任務。不過不幸的是，這種效率提升不是免費的。包含特殊硬體的計算機系統需要更多的半導體，即使在不用時也會帶來能源消耗。軟體也必須進行修改以利用專用硬體的長處，同時這種專門硬體又必須足夠通用，這樣高昂的up-front設計費用才能攤到足夠多的使用者身上，讓專用硬體的價錢變得可以承受。部分由于以上經濟考慮，專用硬體到目前為止隻在幾個領域出現，包括圖形處理（GPU），矢量處理器（MMX、SSE和VMX指令），以及相對規模較小的加密領域。
不過，随着摩爾定律帶來的單線程性能提升的結束，我們可以安全的預測：未來各種各樣的專用硬體會大大增加。
現有的并行軟體
雖然多核CPU曾經讓計算機行業驚訝了一把，但是事實上基于共享記憶體的并行計算機已經商用了超過半個世紀了。這段時間足以讓一些重要的并行軟體登上舞台，事實也确實如此。并行作業系統已經非常常見了，比如并行線程庫，并行關系資料庫管理系統和并行數值計算軟體。這些現有的并行軟體在解決我們可能遇見的并行難題上已經走了很長一段路。
也許最常見的例子是并行關系資料庫管理系統。它和單線程程式不同，并行關系資料庫管理系統一般用進階腳本語言書寫，并發地通路位于中心的關系資料庫。在現在的高度并行化系統中，隻有資料庫是真正需要直接處理并行化的。是以它運用了許多非常好的技術。
軟體設計
操作的開銷表格中的比率值至關重要，因為它們限制了并行計算程式的效率。為了弄清這點，我們假設一款并行計算程式使用了CAS操作來進行線程間通信。假設進行通信的線程不是與自身而主要是與其他線程通信，那麼CAS操作一般會涉及到緩存未命中。進一步假設對應每個CAS通信操作的工作需要消耗300納秒，這足夠執行幾個浮點transendental函數了。其中一半的執行時間消耗在CAS通信操作上！這也意味着有兩個CPU的系統運作這樣一個并行程式的速度，并不比單CPU系統運作一個串行執行程式的速度快。
在分布式系統中結果還會更糟糕，因為單次通信操作的延遲時間可能和幾千條甚至上百萬條浮點操作的時間一樣長。這就說明了會産生大量工作量的通信操作應該盡可能減少。
小問題：既然分布式系統的通信操作代價如此昂貴，為什麼人們還要使用它？
總結
并行算法必須将每個線程設計成盡可能獨立運作的線程。越少使用線程間通信手段，比如原子操作、鎖或者其它消息傳遞方法，應用程式的性能和可擴充性就會更好。簡而言之，想要達到優秀的并行性能和可擴充性，就意味着在并行算法和實作中掙紮，小心的選擇資料結構和算法，使用現有的并行軟體和環境，或者将并行問題轉換成已經有并行解決方案存在的問題。