並行計算

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

並行計算（英語：parallel 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定理
   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/ （頁面存檔備份，存於網際網路檔案館） ）在線手冊中查詢獲悉。
• 常見的數值算法設計方法舉例
  • 並行快速傅里葉變換。

參見

• 計算機科學
• 理論計算機科學
• 訊息傳遞介面 （Message Passing Interface － MPI）