並行計算

並行計算（Parallel computing）是一種計算模式，指將多個計算任務或進程同時進行處理。龐大複雜的問題通常可以被拆分為多個較小的部分，隨後在同一時間內被並行求解。並行計算有幾種不同的形式：位級並行、指令級並行、數據並行以及任務並行。並行計算長期以來一直被應用於高性能計算，但隨著阻礙頻率縮放的物理限制日益凸顯，它如今獲得了更為廣泛的關注。由於近年來電腦的功耗及發熱問題日益嚴峻，並行計算現已成為電腦架構的主導範式，這在多核處理器的普及上體現得尤為明顯。

<image>

在電腦科學中，並行性（parallelism）和並發性（concurrency）是兩個截然不同的概念：並行程序利用多個CPU核心，每個核心獨立且同時地執行一個任務。相比之下，並發性使得程序即使在單核CPU上也能處理多個任務：核心在多個任務（即線程）之間快速切換，無需等待上一個任務完全結束。一個程序可以兼具兩者、兩者皆無，或者是並行性與並發性特徵的某種組合。

並行計算機可以根據硬體支持並行的級別進行大致分類。多核電腦與多處理器電腦在一台機器內部擁有多個處理單元；而電腦集群、大規模並行處理系統（MPP）和網格計算則調動多台電腦協同處理同一任務。有時，傳統的處理器還會搭配專門的並行計算機架構使用，以加速特定任務的處理。

在某些情況下，並行性對程式設計師而言是透明的（例如位級並行或指令級並行）；但顯式編寫的並行演算法（特別是那些利用了並發性的演算法），往往比順序演算法更難開發，這是因為並發性引入了多類潛在的新型軟體缺陷，其中最常見的就是競爭條件。不同子任務之間的通信與同步，往往是實現並行程序最佳性能所面臨的最大障礙。

單一程序通過並行化所能達到的理論加速比上界，由阿姆達爾定律給出。該定律指出，程序的加速比受限於其能夠被並行化的那部分時間比例。

## 背景

傳統上，電腦軟體通常是為串行計算而編寫的。為了解決某個問題，人們會構建一個演算法，並將其實現為一串線性的指令流。這些指令在同一台電腦上的一個中央處理器中執行。在任何特定時刻，只能有一條指令在執行——待該指令執行完畢後，才會接著執行下一條。

相比之下，並行計算同時使用多個處理單元來解決問題。它的實現方式是將大問題拆分為相互獨立的小分塊，使得每個處理單元都能與其它單元同時執行其負責的算法部分。處理單元的形式多種多樣，包括配備多處理器的單台電腦、多台聯網的電腦、專用硬體，或者是上述方式的任意組合。歷史上，並行計算主要用於科學計算及自然現象的模擬，特別是在自然科學和工程科學領域，如氣象學。這一需求推動了並行硬體、軟體系統以及高性能計算的設計與發展。

從20世紀80年代中期直到2004年，頻率縮放一直是提升電腦性能的主要驅動力。程序運行的運行時等於指令數乘以每條指令的平均執行時間。在保持其他條件不變的情況下，提高時鐘頻率會減少執行單條指令所需的平均時間。因此，頻率的提升能夠直觀地降低所有計算密集型程序的運行時間。然而，晶片消耗的功率（$P$）由公式 $P = C \times V^2 \times F$ 決定，其中 $C$ 是每個時鐘周期發生開關操作的電容（與狀態發生改變的電晶體數量成正比），$V$ 是電壓，$F$ 是處理器頻率（每秒周期數）。頻率的增加會直接導致處理器功耗的急劇攀升。過高的功耗最終導致了英特爾在2004年5月8日取消了其Tejas和Jayhawk處理器的研發計劃，這通常被視作頻率縮放作為主導電腦架構範式終結的標誌。

為了解決功耗和過熱問題，各大主要的中央處理器製造商開始生產具備多核心且功耗效率更高的處理器。核心是處理器的計算單元，在多核處理器中，每個核心都是獨立的，並且可以並發地訪問同一記憶體。多核處理器將並行計算引入了日常的台式電腦。由此，串行程序的並行化成為了一項主流的編程任務。到了2012年，四核處理器已成為台式電腦的標配，而伺服器則普遍擁有10核以上的處理器。摩爾定律曾預測每個處理器的核心數量每18到24個月將翻一番。截至2023年，一些處理器已擁有超過一百個核心。受限於散熱和設計約束，有些設計甚至混合了性能核心與能效核心（例如ARM的big.LITTLE設計）。

作業系統能夠確保不同的任務和使用者程序在可用的核心上並行運行。然而，為了讓串行軟體程序充分利用多核架構，程式設計師需要對代碼進行重構和並行化處理。應用軟體運行時間的縮短將不再僅僅依賴於硬體頻率的提升；相反，程式設計師必須並行化他們的軟體代碼，以充分發揮多核架構日益強大的計算潛力。

### 相關定律

<image>

<image>

理想情況下，並行化帶來的加速比應當是線性的——處理單元數量翻倍應使運行時間減半，再次翻倍則運行時間應再次減半。然而，極少數並行演算法能達到如此完美的加速效果。它們中的大多數在處理單元較少時能表現出近乎線性的加速比，但當處理單元數量龐大時，加速比就會逐漸趨於平緩，最終變為一個常數。

整體系統潛在的最大加速比可以通過阿姆達爾定律來計算。阿姆達爾定律表明，要想實現最優的性能提升，必須在增強任務的並行部分與非並行部分之間取得平衡。此外，它揭示了單純增加處理器數量會導致收益遞減的現象，一旦越過某個臨界點，能夠獲得的加速收益將微乎其微。

阿姆達爾定律也有其局限性，它預設了工作負載是固定的，並且忽略了進程間通信與同步的開銷。它主要只聚焦於計算層面，而對外部因素（如數據持久化、I/O操作和記憶體訪問延遲）缺乏考量。

古斯塔夫森定律與通用可擴展性定律對並行性能給出了更為現實的評估。

<image>

### 依賴關係

理解數據依賴對於實現並行演算法至關重要。程序的執行速度不可能超過其中最長的那條相互依賴的計算鏈（通常被稱為關鍵路徑），因為鏈條中後續的計算必須等待前置計算產生結果後，才能按順序執行。然而，絕大多數演算法並非僅僅由單一且漫長的依賴鏈構成；往往存在大量的機會來並行執行那些互不依賴的計算。

假設 $P_i$ 和 $P_j$ 是兩個程序段。伯恩斯坦條件（Bernstein's conditions）描述了這兩段程序在什麼情況下是互不依賴且可以並行執行的。對於 $P_i$，設 $I_i$ 為其所有輸入變量的集合，$O_i$ 為其輸出變量的集合，對 $P_j$ 亦然。若且唯若它們滿足以下條件時，$P_i$ 和 $P_j$ 才是獨立的：

$$I_j \cap O_i = \varnothing,$$

$$I_i \cap O_j = \varnothing,$$

$$O_i \cap O_j = \varnothing.$$

如果違反了第一個條件，就會產生「流依賴」（flow dependency），即第一段程序產生的結果被第二段程序當作輸入使用。第二個條件代表了「反依賴」（anti-dependency），即第二段程序產生的結果覆蓋了第一段程序所需讀取的變量。第三個也是最後一個條件代表「輸出依賴」：當兩段程序都要向同一個位置寫入數據時，最終保存在那裡的結果必須來自於邏輯上最後執行的那段程序。

請看以下幾個函數，它們展示了各種依賴關係：

```text
 1: function Dep(a, b)
 2: c := a * b
 3: d := 3 * c
 4: end function
```

在這個例子中，指令3不能在指令2之前（甚至也不能與指令2並行）執行，因為指令3使用了指令2的結果。它違反了條件1，因此引入了流依賴。

```text
 1: function NoDep(a, b)
 2: c := a * b
 3: d := 3 * b
 4: e := a + b
 5: end function
```

在這個例子中，指令之間不存在任何依賴關係，因此它們可以全部並行運行。

伯恩斯坦條件默認不同進程之間不會共享內存。如果需要共享內存，就必須使用某種手段來強制規範訪問順序，例如使用信號量、屏障或是其他同步方法。

### 競爭條件、互斥、同步與並行減速

並行程序中的子任務通常被稱為線程。一些並行計算機架構使用更小、更輕量級的線程版本，稱為纖程，而另一些則使用更大的版本，即進程。不過，「線程」一詞現已被普遍接受作為子任務的統稱。線程往往需要以同步的方式訪問某個對象或其他資源，例如當它們必須更新一個共享的變量時。如果沒有同步機制，兩個線程之間的指令可能會以任何隨機順序交錯執行。例如，考慮以下程序：

線程 A｜線程 B

1A: 讀取變量 V｜1B: 讀取變量 V

2A: 將變量 V 加 1｜2B: 將變量 V 加 1

3A: 寫回變量 V｜3B: 寫回變量 V

如果指令 1B 在 1A 和 3A 之間執行，或者指令 1A 在 1B 和 3B 之間執行，程序將會產生錯誤的數據。這被稱為競爭條件。程式設計師必須使用鎖來提供互斥。鎖是一種程式語言結構，允許一個線程獲取變量的控制權，並在該變量被解鎖前，阻止其它線程讀取或寫入它。持有鎖的線程可以自由地執行其臨界區（程序中需要獨占訪問某個變量的代碼段），並在完成後解鎖數據。因此，為了保證程序的正確執行，可以將上述程序改寫為使用鎖的形式：

線程 A｜線程 B

1A: 鎖定變量 V｜1B: 鎖定變量 V

2A: 讀取變量 V｜2B: 讀取變量 V

3A: 將變量 V 加 1｜3B: 將變量 V 加 1

4A: 寫回變量 V｜4B: 寫回變量 V

5A: 解鎖變量 V｜5B: 解鎖變量 V

其中一個線程將成功鎖定變量 V，而另一個線程將被鎖定在外——在 V 再次被解鎖前無法繼續執行。這確保了程序的正確運行。當線程必須排隊（串行化）訪問資源時，使用鎖也許是保證程序正確性的必要手段，但這會極大拖慢程序的執行速度，並可能影響其可靠性。

使用非原子性鎖來鎖定多個變量可能會引入程序死鎖的風險。原子鎖會一次性鎖定所有需要的變量。如果它不能同時鎖定所有變量，它就不會鎖定其中的任何一個。如果兩個線程都需要使用非原子鎖去鎖定相同的兩個變量，很可能發生的情況是：一個線程鎖定了其中一個變量，而第二個線程鎖定了另一個變量。在這種情況下，任何一個線程都無法繼續推進，從而導致死鎖。

許多並行程序要求其子任務同步執行。這就需要用到屏障。屏障通常通過鎖或信號量來實現。有一類被統稱為無鎖與無等待演算法的演算法，能夠完全避免使用鎖和屏障。然而，這種方法往往難以實現，並且需要對數據結構進行極為精巧的設計。

並非所有的並行化都能帶來加速效果。通常情況下，隨著任務被分割成越來越多的線程，這些線程將把越來越大比例的時間花在相互通信或者等待資源訪問上。一旦資源爭用或通信帶來的開銷超過了實際計算所花費的時間，進一步的並行化（即把工作負載分配給更多的線程）反而會增加而不是減少完成任務的時間。這一問題被稱為並行減速，但在某些情況下，它可以通過軟體層面的分析與重新設計來得到改善。

### 細粒度、粗粒度與極其並行

應用程式經常根據其子任務需要彼此同步或通信的頻率來進行分類。如果一個應用程式的子任務每秒必須通信許多次，那麼它表現出的就是細粒度並行（fine-grained parallelism）；如果它們每秒不需要通信太多次，則表現為粗粒度並行（coarse-grained parallelism）；如果它們很少或者根本不需要通信，那麼它就具備極其並行（embarrassing parallelism，也譯作易並行）特性。極其並行的應用程式通常被認為是最容易實現並行化的。

### 弗林分類法

麥可·弗林為並行（及順序）電腦與程序創建了最早的分類系統之一，如今被稱為弗林分類法。弗林根據指令流是單一還是多重，以及這些指令操作的數據流是單一還是多重，對程序和電腦進行了分類。

單一指令流｜多指令流

單一資料流｜單指令流單數據流（SISD）｜多指令流單數據流（MISD）

多資料流｜單指令流多數據流（SIMD）｜多指令流多數據流（MIMD）

單指令流單數據流（SISD）分類相當於一個完全順序執行的程序。單指令流多數據流（SIMD）分類類似於對龐大的數據集反覆執行相同的操作，這在信號處理應用中非常常見。多指令流單數據流（MISD）是一個較少使用的分類。儘管曾經設計過應對這一分類的電腦架構（如脈動陣列），但符合該類別的實際應用卻寥寥無幾。多指令流多數據流（MIMD）程序則是迄今為止最為常見的並行程序類型。

正如大衛·帕特森和約翰·軒尼詩所言：「當然，有些機器是這些分類的混合體，但這種經典模型之所以能留存至今，是因為它簡單、易於理解，並且能夠提供一個很好的初步近似評估。也許正因為其通俗易懂，它也是應用最廣泛的分類方案。」

## 缺點

在實踐中，並行計算可能會引入顯著的額外開銷，這主要是因為需要將來自多個進程的數據進行同步與合併。具體而言，與在單個線程上處理相同數據相比，進程間通信和同步所導致的開銷要大得多——通常要高出兩個甚至更多數量級。因此，應當仔細評估並行化帶來的整體性能提升是否物有所值。

## 粒度

### 位級並行

<image>

從20世紀70年代超大規模積體電路（VLSI）電腦晶片製造技術問世，一直到大約1986年，電腦架構運算速度的提升主要依賴於電腦字長（處理器每個周期能夠處理的資訊量）的翻倍。增加字長減少了處理器為了對尺寸大於字長的變量執行運算而必須執行的指令數量。例如，當一個8位處理器必須對兩個16位整數整數執行加法運算時，處理器必須首先使用標準的加法指令將兩個整數的8個低位比特相加，然後使用帶進位加法指令加上剛才低位加法產生的進位位與兩個整數的8個高位比特。因此，8位處理器需要兩條指令來完成單次運算，而16位處理器只需一條指令即可完成。

歷史上，4位微處理器被8位取代，隨後是16位、32位。隨著32位處理器的普及，這一趨勢在通用計算領域停滯了長達二十年之久，32位成為了標準。直到2000年代初，隨著x86-64架構的出現，64位處理器才開始變得普遍。

### 指令級並行

<image>

本質上，電腦程式是由處理器執行的一連串指令流。如果沒有指令級並行，處理器只能在每個時鐘周期發射不到一條指令（$IPC < 1$）。這類處理器被稱為「亞標量」（subscalar）處理器。通過將這些指令重新排序並組合成組，使其能夠在不改變程序最終結果的前提下被並行執行，這就是所謂的指令級並行。從20世紀80年代中期到90年代中期，指令級並行技術的進步主導了電腦架構的發展。

<image>

所有現代處理器都具備多級指令流水線。流水線中的每一個階段對應於處理器在這一階段對指令執行的不同操作；一個擁有 $N$ 級流水線的處理器可以同時處理多達 $N$ 條處於不同完成階段的指令，因此每個時鐘周期能夠發射一條指令（$IPC = 1$）。這類處理器被稱為「標量」（scalar）處理器。經典流水線處理器的一個代表是具有五個階段的RISC處理器：取指（IF）、解碼（ID）、執行（EX）、訪存（MEM）和寫回（WB）。奔騰4處理器更是擁有高達35級的流水線。

<image>

大多數現代處理器也配備了多個執行單元。它們通常將此特性與流水線技術相結合，從而在每個時鐘周期內能夠發射多條指令（$IPC > 1$）。這類處理器被稱為「超標量」處理器。超標量處理器與多核處理器的區別在於，其內部的多個執行單元並非獨立的完整處理器。只有當指令之間不存在數據依賴時，它們才能被組合在一起執行。記分板技術（Scoreboarding）和托馬蘇洛算法（類似於記分板但運用了寄存器重命名）是實現亂序執行與指令級並行的兩種最常用技術。

### 任務並行

任務並行是並行程序的一種特性，即「可以將完全不同的計算操作作用於相同或不同的數據集上」。這與數據並行形成了對比，在數據並行中，是對相同或不同的數據集執行相同的計算。任務並行涉及將一個大任務分解為多個子任務，然後將每個子任務分配給各個處理器去執行。這些處理器隨後將並發地、且通常是協作地執行這些子任務。任務並行的規模通常不會隨著問題規模的擴大而自動擴展。

### 超字級並行

超字級並行（Superword level parallelism）是一種基於循環展開和基本塊向量化的自動向量化技術。它與循環向量化演算法的不同之處在於，它可以利用內聯代碼的並行性，例如處理坐標、顏色通道或是手動展開的循環。

## 硬體

### 記憶體與通信

並行計算機中的主存要麼是共享內存（在單一的地址空間內被所有處理單元共享），要麼是分布式記憶體（每個處理單元擁有各自局部的地址空間）。分布式記憶體意味著記憶體不僅在邏輯上是分布的，往往在物理上也是分開的。分布式共享內存和記憶體虛擬化結合了這兩種方法的優勢：處理單元既擁有屬於自己的本地記憶體，也可以訪問非本地處理器上的記憶體。訪問本地記憶體的速度通常比訪問非本地記憶體快得多。在超級計算機上，可以使用諸如分區全局地址空間（PGAS）等編程模型來實現分布式共享內存空間。這種模型允許一個計算節點上的進程透明地訪問另一節點的遠程記憶體。所有的計算節點還會通過高速互連網路（如InfiniBand）連接到一個外部的共享內存系統，這個系統被稱為突發緩衝區，通常由物理分布在多個I/O節點上的非易失性存儲器陣列構建而成。

<image>

能夠以相同的延遲和帶寬訪問主存中每個存儲單元的電腦架構，被稱為統一記憶體訪問（UMA）系統。通常只有記憶體非物理分布的共享內存系統才能實現這一點。不具備這一特性的系統則被稱為非統一記憶體訪問架構（NUMA）。分布式記憶體系統均屬於非統一記憶體訪問架構。

電腦系統利用CPU緩存（位於處理器附近的小型高速存儲器）來存放記憶體值的臨時副本（不僅在物理距離上更近，邏輯上也緊密配合）。在並行計算機系統中，如果同一個變量的值被緩存到多個不同的位置，可能會導致緩存數據不一致，進而引起程序執行錯誤。為了解決這個問題，這些電腦需要引入緩存一致性系統，該系統負責追蹤被緩存的值並策略性地將其清除，從而保障程序的正確執行。總線嗅探是追蹤哪些值正被訪問（並應當被清理）的最常見方法之一。設計大型、高性能的緩存一致性系統是電腦架構中一個非常棘手的難題。正因為如此，共享內存架構的擴展性遠不如分布式記憶體系統。

處理器與處理器之間、處理器與記憶體之間的通信可以在硬體層面上通過多種方式實現，包括使用共享內存（無論是多埠還是多路復用記憶體）、交叉開關矩陣、共享總線或各種拓撲結構的互連網路，例如星型、環型、樹型、超立方體、胖超立方體（每個節點上有多個處理器的超立方體）或是N維網格。

基於互連網路的並行計算機需要配備一定的路由機制，以實現在沒有直接連接的節點間傳遞消息。在大型多處理器機器中，處理器間通信所使用的媒介通常呈現出層次化的結構特徵。

### 並行計算機的分類

並行計算機可以根據硬體支持並行的級別進行大致分類。這種分類方式很大程度上與基礎計算節點之間的物理或邏輯距離相對應。這些分類並非互不相容的；例如，由對稱多處理器組成的集群就非常普遍。

#### 多核計算

多核處理器是指在同一個晶片上集成了多個處理單元（稱為「核心」）的處理器。它有別於超標量處理器：超標量處理器包含多個執行單元，可以在每個時鐘周期內從同一個指令流（線程）中發射多條指令；相反，多核處理器則能在每個時鐘周期內從多個獨立的指令流中發射多條指令。專為索尼PlayStation 3遊戲機設計的IBMCell微處理器就是一款極其出色的多核處理器。多核處理器中的每個核心甚至可能同時也是超標量的——也就是說，在每個時鐘周期內，每個核心不僅獨立運作，還能從各自的一個線程中發射多條指令。

同步多線程（其中以英特爾的超線程技術最為人熟知）是早期的一種偽多核形式。能夠支持並發多線程的處理器在其處理單元內包含了多個執行單元（即具備超標量架構），並且能在每個時鐘周期內從「多個」線程中發射指令。與此不同，時間多線程在處理單元內僅包含一個執行單元，每次只能從「多個」線程中的某一個發射一條指令。

#### 對稱多處理

對稱多處理器（SMP）是一種由多個相同的處理器構成的電腦系統，這些處理器共享內存並通過總線相互連接。然而，總線競爭限制了總線架構的擴展能力。因此，SMP系統的處理器數量一般不會超過32個。由於處理器的尺寸日益縮小，加之大容量緩存大幅降低了對總線帶寬的需求，只要能保證充足的記憶體帶寬，這種對稱多處理器系統在性價比上極具吸引力。

#### 分布式計算

分布式計算機（也被稱為分布式記憶體多處理器系統）是指處理單元通過網路互相連接的分布式記憶體電腦系統。分布式計算機具有極高的可擴展性。術語「並發計算」、「並行計算」和「分布式計算」之間有很大的重疊，彼此間並沒有明確的界限。同一個系統往往可以同時被稱為「並行的」與「分布式的」；在一個典型的分布式系統中，各個處理器實際上也是在並發地並行運行。

##### 集群計算

<image>

集群是由一組鬆散耦合的電腦組成的群體，它們緊密協作，在很多方面可以被視作一台獨立的電腦。集群由多台通過網路互連的獨立機器組成。儘管集群中的機器不必完全對稱，但如果它們硬體存在差異，實現負載均衡就會變得更為困難。最常見的一種集群是貝奧武夫集群，它是由多台完全相同的商用現貨計算機構建的，這些電腦通過基於TCP/IP的乙太網區域網相連。貝奧武夫技術最早由托馬斯·斯特林和唐納德·貝克開發。全球TOP500超級計算機榜單中，有87%的系統都屬於集群架構。剩下的部分則是大規模並行處理器（下文將介紹）。

因為網格計算系統（下文將詳細描述）可以輕鬆處理極其並行的問題，所以現代集群通常被設計用於解決更為複雜的計算難題——這些問題要求節點之間更頻繁地共享中間計算結果。這需要互連網路不僅具備高帶寬，更重要的是具備低延遲。許多歷史上以及現役的超級計算機都採用了專門為集群計算量身定製的定製化高性能網路硬體，例如克雷（Cray）的 Gemini 網路。截至2014年，大多數現有的超級計算機都在使用某些標準的現成網路硬體，最常見的是Myrinet、InfiniBand或千兆乙太網。

##### 大規模並行計算

<image>

大規模並行處理器（MPP）是一台包含了成百上千甚至更多聯網處理器的單一電腦。MPP在很多特徵上與集群相似，但MPP採用的是專用的互連網路（而集群多採用商用現貨硬體進行網路連接）。此外，MPP的規模通常遠大於一般集群，其處理器數量通常「遠超」100個。在一台MPP系統中，「每個CPU都配備了自己的記憶體、作業系統副本以及應用程式。各個子系統通過高速互連網路與其它部分進行通信。」

IBM的Blue Gene/L正是這樣一台MPP，它曾在2009年6月的TOP500榜單中位列世界第五快超級計算機。

##### 網格計算

網格計算是並行計算分布最為廣泛的一種形式。它通過網際網路（Internet）將分布各地的電腦聯繫起來，共同處理某個特定問題。受限於網際網路相對較低的帶寬和極高的延遲，這種分布式計算方式通常只適合處理極其並行的問題。

大多數網格計算應用都依賴於中間件（一種介於作業系統和應用程式之間的軟體層，專門負責管理網路資源及標準化軟體接口）。最廣為人知的網格計算中間件當屬伯克利開放式網路計算平台（BOINC）。很多志願計算軟體就是利用了電腦在空閒時的「剩餘周期」來執行後台計算。

##### 雲計算

網際網路的普及和高帶寬網路的發展催生了雲計算，這是一種將大規模並行資源作為服務對外提供的模式。該範式將底層硬體進行了抽象，使得使用者無需親自動手管理物理基礎設施，就能利用虛擬化的集群來處理可動態擴展的計算工作負載。

##### 分布式帳本技術

現代分布式帳本協議巧妙地應用了並行計算原理，旨在突破傳統區塊鏈存在的串行瓶頸。通過將狀態空間進行分片（sharding），新型的共識架構實現了「大規模並行的交易處理」。在這種模型下（例如Cerberus等協議所採用的方式），獨立的交易被視為並行任務，並被分配到不同的節點上同時執行，而不是像過去那樣在單一的全局區塊中進行串行排隊處理。

#### 專用並行計算機

在並行計算的廣闊天地中，存在一些專用並行設備，它們始終是屬於特定領域的利基設備。雖然它們未必是針對某種特定領域語言設計的，但往往只能應用於少數幾類並行計算問題。

##### 結合FPGA的可重構計算

可重構計算涉及將現場可編程邏輯門陣列（FPGA）作為通用電腦的協處理器來使用。本質上，FPGA是一種能夠根據特定任務的需要，在物理層面上重新改變自身線路連接的電腦晶片。

人們可以使用諸如VHDL或Verilog等硬體描述語言為FPGA編寫程序。目前已有幾家供應商推出了C轉HDL語言的編譯器，試圖模擬大多數程式設計師所熟悉的C語言的語法和語義。比較著名的C轉HDL語言包括Mitrion-C、Impulse C以及Handel-C。基於C++的部分SystemC子集也可以用於此目的。

AMD向第三方供應商開放其HyperTransport總線技術的決定，成為了推動高性能可重構計算發展的關鍵賦能技術。據DRC電腦公司營運長麥可·R·達穆爾（Michael R. D'Amour）透露：「當我們最初走進AMD大門時，他們戲稱我們是『插槽竊賊』。而現在，他們將我們視作親密的合作夥伴。」

##### 圖形處理器通用計算（GPGPU）

<image>

在圖形處理器上進行通用計算（GPGPU）是電腦工程研究中一個相對較新的趨勢。GPU原本是專門為電腦圖形學處理而進行了高度優化的協處理器。而電腦圖形處理領域恰恰由海量的數據並行操作所主導——尤其是線性代數中的矩陣運算。

在早期，GPGPU程序必須借道普通的圖形API來執行計算任務。然而如今，業界已經構建了多種全新的程式語言和平台，旨在直接利用GPU進行通用計算，Nvidia和AMD分別推出了包含CUDA和Stream SDK的專屬開發環境。其他涉及GPU編程的語言和平台還包括BrookGPU、PeakStream以及RapidMind。Nvidia甚至還在其Tesla系列中推出了專為科學計算打造的計算卡產品。技術聯盟Khronos Group發布了OpenCL規範，這是一個旨在編寫能夠跨CPU和GPU等異構平台執行的程序的框架。目前，AMD、蘋果公司、英特爾、Nvidia等多家巨頭均已宣布支持OpenCL。

##### 專用積體電路（ASIC）

工程師們已經設計出了幾種基於專用積體電路（ASIC）的方法來應對高度特定的並行應用。

顧名思義，ASIC是為特定應用量身定製的，因此它可以為該應用進行毫不妥協的全方位優化。這就使得對於給定的計算任務而言，ASIC往往能夠擊敗任何通用的電腦架構。然而，ASIC必須通過紫外光刻工藝製造，這一過程需要製作掩模，成本極其昂貴。一套掩模的成本可能高達上百萬美元。（晶片所需的電晶體越小，掩模的成本就越發驚人。）與此同時，通用電腦性能的隨時間演進（正如摩爾定律所描述的那樣）往往會在一兩代晶片之後，就將ASIC原本的性能優勢蠶食殆盡。高昂的初期成本，加上極易被遵循摩爾定律發展的通用計算硬體趕超，使得ASIC對於大多數並行計算應用而言都不夠經濟。不過，仍有一些特殊的ASIC被製造了出來。一個著名的例子就是計算能力達到PFLOPS級別的理化學研究所MDGRAPE-3機器，它專門使用定製的ASIC來進行分子動力學的模擬。

##### 向量處理器

<image>

向量處理器是一種能夠對大規模數據集執行同一條指令的CPU或電腦系統。這類處理器具備針對數字或向量的一維線性陣列進行操作的高級運算功能。一個經典的向量運算例子是 $A = B \times C$，其中 $A$、$B$ 和 $C$ 都是包含了64個64位浮點數字的向量。它們與弗林分類法中的SIMD類別有著極為緊密的淵源。

在20世紀70年代和80年代，克雷公司憑藉其向量處理電腦在業界名聲大噪。然而，作為獨立的CPU或完整的電腦系統，向量處理器如今基本上已經淡出了歷史舞台。不過，現代處理器的指令集中確實融入了許多用於處理向量的指令，例如飛思卡爾半導體的AltiVec技術和英特爾的單指令流多數據流擴展（SSE）。

## 軟體

### 並行程式語言

為了在並行計算機上進行編程，人們開發出了各種並發程式語言、程序庫、API以及並行編程模型（例如演算法骨架）。這些工具大致可以根據它們對底層記憶體架構的假設來劃分：針對共享內存、針對分布式記憶體，或是針對分布式共享內存。編寫共享內存語言的程序通過操作共享的記憶體變量進行通信；而分布式記憶體系統則主要依賴於消息傳遞。POSIX線程（Pthreads）和OpenMP是兩種最被廣泛使用的共享內存API；而消息傳遞接口（MPI）則是分布式記憶體中應用最廣的消息傳遞API。在並行編程的諸多概念中，Future與Promise被經常使用：程序的某個部分做出一個承諾（Promise），保證會在未來的某個時刻向程序的另一部分交付某個所需的數據（Future）。

目前，業界也在致力於推行並行編程標準的統一，比如針對混合多核計算的開放標準OpenHMPP。這是一種基於指令（directive）的編程模型，它提供了一套語法，通過遠程過程調用（RPC），能將計算任務高效卸載到硬體加速器上，並優化與硬體記憶體之間的數據移動。

消費級GPU的崛起極大地推動了業界對計算內核的支持，不論是在圖形API中（通常被稱為計算著色器）、專用的計算API中（如OpenCL），還是在其他語言的擴展包中。

### 自動並行化

藉助編譯器實現串行程序的自動並行化，一直被視作並行計算領域孜孜以求的「聖杯」，在處理器時鐘頻率遇到瓶頸的今天，這一訴求顯得尤為迫切。儘管編譯器研究人員付出了幾十年的努力，但自動並行化目前取得的成功仍相當有限。

主流的並行程式語言要麼仍然需要程式設計師進行顯式並行編程，要麼最好也只是做到部分隱式並行——即程式設計師通過向編譯器發送編譯指令來協助其完成並行化操作。目前存在極少數能夠實現完全隱式並行的程式語言，包括SISAL、Parallel Haskell、SequenceL、以及專門用於FPGA的SystemC、Mitrion-C、VHDL和Verilog。

### 應用程式檢查點

隨著電腦系統複雜度的增加，其平均故障間隔時間通常會變得越來越短。應用程式檢查點是一種容錯技術，系統會給應用程式打個「快照」——即記錄下所有當前的資源分配狀態以及變量值，類似於進行一次核心轉儲；倘若電腦發生崩潰，這份記錄就可以用來恢復程序的運行。使用應用程式檢查點意味著，程序只需從它最近一次記錄的檢查點重新啟動即可，而無需從頭再來。儘管檢查點技術在許多場合下都能發揮作用，但它對那些被用於高性能計算、包含大量處理器且高度並行的系統來說，尤為不可或缺。

## 算法方法

隨著並行計算機變得愈發龐大與快速，我們現在已經能夠解決過去因為計算時間過長而無法觸及的難題。從生物資訊學（用於蛋白質摺疊和序列分析）到經濟學，形形色色的領域都已從並行計算中獲益。在並行計算的應用中，常見的求解問題類型包括：

- 稠密線性代數
- 稀疏線性代數
- 譜方法（例如庫利-圖基快速傅立葉變換演算法）
- N體問題（例如Barnes-Hut模擬）
- 結構化網格問題（例如格子玻爾茲曼方法）
- 非結構化網格問題（例如在有限元分析中所見的問題）
- 蒙特卡羅方法
- 組合邏輯（例如暴力密碼分析技術）
- 圖遍歷（例如排序算法）
- 動態規劃
- 分支定界法
- 機率圖模型（例如檢測隱馬爾可夫模型以及構建貝葉斯網路）
- HBJ模型，一種簡潔的消息傳遞模型
- 有限狀態機模擬
- 優化問題（例如遺傳算法與模擬退火）
- 粒子方法（例如網格質點法與平滑粒子流體動力學）
- 約束滿足問題
- 數據挖掘與模式識別
- 機器學習與深度學習的訓練
- 光線追蹤與渲染
- 時間序列分析
- 流數據分析

## 容錯機制

並行計算的理念同樣可以被應用到容錯電腦系統的設計中去，最典型的便是通過鎖步系統讓多個組件並行執行完全相同的操作。一旦某個組件發生故障，這便能提供熱備用的冗餘；如果多次計算的結果出現分歧，系統還能藉此進行自動的錯誤檢測甚至錯誤糾正。這些方法常被用來防止由瞬態錯誤引起的單事件翻轉效應。儘管在嵌入式系統或高度專用的系統中有時還需要輔以額外的措施，但就商用現貨系統而言，這種方法提供了一種實現N模冗餘（N-modular redundancy）的極具成本效益的途徑。

## 歷史

<image>

真正意義上的（MIMD）並行計算的根源，可以追溯到路易吉·費德里科·梅納布雷亞以及他的著作《關於由查爾斯·巴貝奇發明的分析機的草圖》。

1957年，布爾機器公司宣布推出了世界上第一款專門為並行性設計的電腦架構——Gamma 60。它採用了一種Fork-Join模型，並利用一個「程序分發器」（Program Distributor）在中央存儲器與各個獨立的處理單元之間分發和收集數據。

1958年4月，斯坦利·吉爾（來自費蘭蒂公司）探討了並行編程以及引入分支（branching）與等待（waiting）機制的必要性。同樣在1958年，IBM的研究員約翰·科克與丹尼爾·斯洛特尼克首次在數值計算領域探討了並行性思想的運用。寶來公司於1962年推出了D825，這是一款配備了四個處理器的電腦，通過交叉開關矩陣能夠訪問多達16個記憶體模塊。1967年，在一次美國資訊處理學會聯合會的會議上，阿姆達爾與斯洛特尼克針對並行處理的可行性展開了激烈的辯論。正是在這場辯論的背景下，後人熟知的阿姆達爾定律被提了出來，用以界定由並行化所能帶來的加速極限。

1969年，霍尼韋爾推出了首款基於Multics的系統，這是一個能夠並行運行多達八個處理器的對稱多處理器系統。誕生於20世紀70年代的C.mmp是卡內基梅隆大學發起的一個多處理器項目，它是首批處理器數量超過寥寥幾個的多處理器系統之一。而1984年的 Synapse N+1 則是首台具備窺探緩存（snooping caches）並基於總線連接的多處理器電腦。

SIMD並行計算機的歷史同樣可以追溯到20世紀70年代。設計早期SIMD電腦的初衷，是為了將處理器控制單元的門電路傳播延遲分攤到多條指令上去。早在1964年，斯洛特尼克就曾提議為勞倫斯利弗莫爾國家實驗室建造一台大規模並行計算機。他的這項設計後來獲得了美國空軍的資助，這便是最早投入實際研發的SIMD並行計算工程——ILLIAC IV。其設計的核心在於極高的並行度，規劃了多達256個處理器，允許機器對巨量的數據集執行操作，這種思想後來演變成了人們所熟知的向量處理。然而，ILLIAC IV卻被貼上了「最聲名狼藉的超級計算機」的標籤，因為該項目耗時11年，開銷幾乎飆升至最初預算的四倍，而最終只完成了原計劃規模的四分之一。

$8 million estimated in 1966 to $

當它在1976年終於準備好運行第一個真正的應用程式時，它的性能反而被當時已經上市的商用超級計算機（如Cray-1）拋在了身後。

## 作為大規模並行計算機的生物大腦

早在20世紀70年代初，在麻省理工學院電腦科學與人工智慧實驗室，馬文·明斯基和西摩·派普特就開始構思他們的《心智社會》理論，該理論將生物的大腦視作一台大規模並行計算機器。1986年，明斯基出版了《心智社會》一書，他在書中提出「心智是由眾多微小的智能體（agent）組成的，而這些智能體本身是沒有智能的」。該理論試圖解釋我們稱之為「智能」的現象，是如何通過那些不具備智能的微小部件相互作用而湧現出來的。明斯基坦言，觸發該理論靈感的最主要來源是他試圖創造一種能夠操縱機器臂、攝像機以及電腦去搭積木的機器人的研究工作。

類似的模型（同樣將生物大腦視為一台大規模並行計算機，即認為大腦由一群獨立的或半獨立的智能體組成）也被以下學者或著作提出過：

- 托馬斯·R·布萊克斯利（Thomas R. Blakeslee）。
- 麥可·加扎尼加。
- 羅伯特·奧恩斯坦。
- 歐內斯特·希爾加德。
- 加來道雄。
- 喬治·葛吉夫。
- 神經集群大腦模型（Neurocluster Brain Model）。

## 外部連結

- Lawrence Livermore National Laboratory: Introduction to Parallel Computing
- Designing and Building Parallel Programs, by Ian Foster
- Internet Parallel Computing Archive