平行計算

平行計算（英語：parallel computing）一般是指許多指令得以同時進行的計算模式。在同時進行的前提下，可以將計算的過程分解成小部份，之後以並行方式來加以解決^[1]。

此條目頁的主題是parallel computing。關於concurrent computing，請見「並行計算」。

電腦軟體可以被分成數個運算步驟來執行。為了解決某個特定問題，軟體採用某個演算法，以一連串指令執行來完成。傳統上，這些指令都被送至單一的中央處理器，以循序方式執行完成。在這種處理方式下，單一時間中，只有單一指令被執行（processor level: 比較微處理器，CISC, 和RISC，即管線Pipeline的概念，以及後來在Pipeline基礎上以提高指令處理效率為目的的硬體及軟體發展，比如branch-prediction, 比如forwarding，比如在每個運算單元前的指令堆疊，組譯程式設計師對programm code的順序覆寫）。平行運算採用了多個運算單元，同時執行，以解決問題。

基本體系結構

相對於序列計算，平行計算可以劃分成時間平行和空間平行。時間平行即指令流水化，空間平行使用多個處理器執行並行計算，當前研究的主要是空間的平行問題。以程式和演算法設計人員的角度看，平行計算又可分為資料平行和任務平行。資料平行把大的任務化解成若干個相同的子任務，處理起來比任務平行簡單。

空間上的平行導致兩類平行機的產生，按照麥克·弗萊因（Michael Flynn）的說法分為單指令流多資料流（SIMD）和多指令流多資料流（MIMD），而常用的串行機也稱為單指令流單資料流（SISD）。MIMD類的機器又可分為常見的五類：平行向量處理機（PVP）、對稱多處理機（SMP）、大規模平行處理機（MPP）、工作站機群（COW）、分散式共享儲存處理機（DSM）。

訪存模型

平行計算機有以下五種訪存模型：均勻訪存模型（UMA）、非均勻訪存模型（NUMA）、全高速緩衝記憶體訪存模型（COMA）、一致性高速緩衝記憶體非均勻儲存訪問模型（CC-NUMA）和非遠端儲存訪問模型（NORMA）。

平行計算模型

不像序列計算機那樣，主流使用馮·諾伊曼的計算模型，平行計算機沒有一個統一的計算模型。不過，人們已經提出了幾種有價值的參考模型：PRAM模型，BSP模型，LogP模型，C^3模型等。

平行計算機網路

平行計算機是靠網路將各個處理機或處理器連接起來的，一般來說有以下幾種方式

1. 靜態連接：一維線性連接，網孔連接，超立方體連接，樹連接，立方環連接，洗牌交換連接，蝶形連接，金字塔連接等。
2. 動態連接：匯流排連接（Bus），交叉開關（CS），多級網際網路（MIN）。

網路的基本術語：

1. 節點度
2. 網路直徑
3. 對剖寬度
4. 嵌入

平行計算機效能度量

1. 基本指標
   1. 執行時間
   2. 工作負載
   3. 存取效能
2. 加速比評測
   1. Amdahl定理
   2. Gustafson定理（英語：Gustafson's law）
   3. Sun-Ni定理
3. 可擴放性標準
   1. 等效率標準
   2. 等速度標準
   3. 平均延遲標準

平行演算法

主條目：平行演算法

平行演算法是一門還沒有發展成熟的學科，雖然人們已經總結出了相當多的經驗，但是遠遠不及串行演算法那樣豐富。平行演算法設計中最常用的的方法是PCAM方法，即劃分，通訊，組合，對映。首先劃分，就是將一個問題平均劃分成若干份，並讓各個處理器去同時執行；通訊階段，就是要分析執行過程中所要交換的資料和任務的協調情況，而組合則是要求將較小的問題組合到一起以提高效能和減少任務開銷，對映則是要將任務分配到每一個處理器上。總之，平行演算法還需要相當多完善的地方。 平行演算法與串行演算法最大的不同之處在於，平行演算法不僅要考慮問題本身，而且還要考慮所使用的平行模型，網路連接等等。

• 常見的非數值演算法設計方法舉例
  • 平行播送與平行求和
  • 平行排序演算法；
  • 平行選擇演算法：所謂選擇問題就是在一給定的序列中選擇出某組（個）滿足給定條件的元素。
  • 關於圖論中的一些平行演算法：
    • 圖論作為一門到近代才發展起來的科學。在圖論中有很多關於如何設計演算法的問題，比如求最小生成樹，單源最短路徑等等。事實上，這些演算法中有很多是可以平行化的，而且平行化時運用的思想具有很大的啟發性，下面是幾個常見的平行圖論演算法。
  • 關於串處理的平行演算法：
    • KMP演算法的平行化：在英特爾的開發手冊《Intel® 64 and IA-32 Architectures Optimization Reference Manual》中，「14.3.3 Substring Searches」章節內提供了KMP演算法基於SIMD指令集平行的C語言實現常式，可以作為KMP演算法平行化的參考範例。其中涉及到若干SIMD Intrinsics指令，比如：_mm_loadu_si128、_mm_cmpestrs、_mm_cmpestri等，其具體含義及用法可從 Intel Intrinsics Guide（ https://intel-intrinsics.com/ （頁面存檔備份，存於網際網路檔案館） ）線上手冊中查詢獲悉。
• 常見的數值演算法設計方法舉例
  • 平行快速傅立葉變換。

參考文獻

1. 平行計算基礎理論,系統及應用研究. 國立中正大學資訊工程研究所. 1992 [2 June 2013].

參見

• 電腦科學
• 理論電腦科學
• 訊息傳遞介面 （Message Passing Interface － MPI）