並行計算，一般是指許多指令得以同時進行的計算模式。
目錄 [隱藏]
1 基本體系結構
2 訪存模型
3 平行計算模型
4 並行計算機網路
5 並行計算機性能度量
6 並行演算法
7 參閱
[編輯]基本體系結構
並行計算或稱平行計算是相對於串列計算來說的；所謂並行計算可分為時間上的並行和空間上的並行。 時間上的並行就是指流水線技術，而空間上的並行則是指用多個處理器併發的執行計算。並行計算科學中主要研究的是空間上的並行問題。從程序和演算法設計人員的角度來看，並行計算又可分為數據並行和任務並行。一般來說，因為數據並行主要是將一個大任務化解成相同的各個子任務，比任務並行要容易處理。
空間上的並行導致了兩類並行機的產生，按照Flynn的說法分為：單指令流多數據流（SIMD）和多指令流多數據流（MIMD）。我們常用的串列機也叫做單指令流單數據流（SISD）。MIMD類的機器又可分為以下常見的五類：並行向量處理機（PVP）、對稱多處理機（SMP）、大規模並行處理機（MPP）、工作站機群（COW）、分散式共享存儲處理機（DSM）。
[編輯]訪存模型
並行計算機有以下五種訪存模型：均勻訪存模型（UMA）、非均勻訪存模型（NUMA）、全高速緩存訪存模型（COMA）、一致性高速緩存非均勻存儲訪問模型（CC-NUMA）和非遠程存儲訪問模型（NORMA）。
[編輯]平行計算模型
不像串列計算機那樣，全世界基本上都在使用馮·諾伊曼的計算模型；並行計算機沒有一個統一的計算模型。不過，人們已經提出了幾種有價值的參考模型：PRAM模型，BSP模型，LogP模型，C^3模型等。
[編輯]並行計算機網路
並行計算機是靠網路將各個處理機或處理器連接起來的，一般來說有以下幾種方式
靜態連接：一維線性連接，網孔連接，超立方體連接，樹連接，立方環連接，洗牌交換連接，蝶形連接，金字塔連接等。
動態連接： 匯流排連接(Bus)，交叉開關(CS)，多級網際網路(MIN)。
網路的基本術語：
節點度
網路直徑
對剖寬度
嵌入
[編輯]並行計算機性能度量
基本指標
執行時間
工作負載
存取性能
加速比評測
Amdahl定理
Gustafson定理
Sun-Ni定理
可擴放性標準
等效率標準
等速度標準
平均延遲標準
[編輯]並行演算法
並行演算法是一門還沒有發展成熟的學科，雖然人們已經總結出了相當多的經驗，但是遠遠不及串列演算法那樣豐富。並行演算法設計中最常用的的方法是PCAM方法，即劃分，通信，組合，映射。首先劃分，就是將一個問題平均劃分成若干份，並讓各個處理器去同時執行；通信階段，就是要分析執行過程中所要交換的數據和任務的協調情況，而組合則是要求將較小的問題組合到一起以提高性能和減少任務開銷，映射則是要將任務分配到每一個處理器上。總之，並行演算法還需要相當多完善的地方。 並行演算法與串列演算法最大的不同之處在於，並行演算法不僅要考慮問題本身，而且還要考慮所使用的並行模型，網路連接等等。
常見的非數值演算法設計方法舉例
並行播送與並行求和
並行排序演算法；
並行選擇演算法：所謂選擇問題就是在一給定的序列中選擇出某組（個）滿足給定條件的元素。
關於圖論中的一些並行演算法：
圖論作為一門到近代才發展起來的科學。在圖論中有很多關於如何設計演算法的問題，比如求最小生成樹，單源最短路徑等等。事實上，這些演算法中有很多是可以並行化的，而且並行化時運用的思想具有很大的啟發性，下面是幾個常見的並行圖論演算法。
關於串處理的並行演算法：
KMP演算法的並行化。
常見的數值演算法設計方法舉例
並行快速傅立葉變換。
