並行編程模型

在電腦科學中，並行編程模型（Parallel programming model）是並行計算機架構的抽象化，通過它可方便的表達演算法和它們在程序中的合成。判別編程模型的價值可以通過它的通用性：在各種不同架構上能表達多大範圍的不同問題，和它的性能：編譯的程序在執行時有多高的效率。並行編程模型的實現形式可以是從「順序編程」語言中調用的函式庫，作為現存語言的擴展，或作為全新的語言。

圍繞特定編程模型的共識是很重要的，這可導致建造不同的並行計算機來支持這個模型，從而促進軟體的可移植性。在這個意義上，編程模型被稱為在硬體和軟體之間的橋接模型。

## 並行編程模型的分類

並行編程模型的分類可以寬泛的在兩個領域主題下進行：進程交互和問題分解。

### 進程交互

進程交互有關於並行進程能夠籍此相互通信的機制。最常見的交互形式是共享內存和消息傳遞。

#### 共享內存

共享內存是在進程間傳遞數據的高效方式。在共享內存模型中，並行進程共享它們可以異步讀與寫的全局地址空間。異步並發訪問可能導致競爭條件，和用來避免它們的機制如：鎖、信號量和監視器。常規的多核處理器直接支持共享內存，很多並行程式語言和庫在設計上利用了它，比如採用分叉會合模型的：Cilk、OpenMP和線程建造塊。

#### 消息傳遞

在消息傳遞模型中，並行進程通過消息傳遞相互交換數據。這種通信可以是異步的，就是說消息可以在接收者準備好之前發出；或是同步的，就是說消息發出前接收者必須準備好。通信順序進程（CSP）形式化了使用同步通信通道來連接進程的消息傳遞，並引出了重要的語言如：Occam、Limbo和Go。與之相對，演員模型使用異步消息傳遞，並被採用於如下語言的設計中：D、Scala和SALSA。

#### 分布式記憶體

分布式記憶體指稱一類多處理器電腦系統，其中每個處理器都有自己私有的記憶體，計算任務只能在本地數據上運算，如果需要遠程數據，計算任務必須與一個或多個遠程處理器通信。在分布式記憶體系統編程中的關鍵要點是如何把數據分布到各個記憶體上；依賴於所解決的問題，數據可以靜態分布，也可以在節點間移動；數據可以在需要時移動，也可以事先推入新的節點。

MPI規定了用於分布式記憶體系統的通信協議，支持點到點通信和集體通信（collective communication）二者。MPI還是消息傳遞API，帶有對其特徵在任何實現中必須如何表現的協議和語義規定。MPI的目標是高性能、可伸縮性和可移植性，目前仍是高性能計算領域中統治性的模型。此外還有支持單邊通信（one-sided communication）的分區全局地址空間模型。

### 問題分解

並行程序由同時執行的進程構成。問題分解有關於規劃（formulate）成員進程的方式。

#### 數據並行

數據並行模型關注進行運算所在的數據集，典型的是正規結構的陣列。一組任務將在這些數據上運算，但是單獨的處於在不相交的分區中。數據並行通常對應SPMD編程模型，相應執行模型對應費林分類法中的SIMD（例如AVX處理器補充功能）或MIMD（例如Xeon Phi），還有GPGPU採用的單指令多線程（例如NVIDIA Tesla）。

#### 任務並行

任務並行模型關注進程或線程的執行。這些進程通常表現出獨特性，並強調對通信的需求。任務並行是表達消息傳遞通信的自然方式。任務並行通常對應MPMD編程模型，與SPMD的區別在於適合解決的問題而非執行模型。

### 隱式並行

與上述顯式並行相反，隱式並行不向編程者透露任何編譯器、運行時系統或硬體負責的事情。例如，在編譯器中自動並行化是把順序代碼轉變程並行代碼的過程；而在電腦架構中，超標量執行是採用指令級並行來進行並行運算的機制，因自身限制而被實際利用為同時多線程/超線程。

在隱式並行中，進程交互對編程者均不可見，轉而由編譯器和/或運行時系統負責進行交互。函數式程式語言不存在副作用，允許無依賴的函數並行執行，人們已經進行了很多有關的研究實驗。以SISAL和SAC為代表的一類數據流程程式語言，是可以高效隱式並行的函數式程式語言，其關鍵特徵是單賦值和面向陣列。

## 術語

並行計算模型是計算模型的一大範疇，包括：細胞自動機、PRAM機、LogP機、佩特里網、進程網和交互網模型等。計算模型是用來分析計算進程代價的一種抽象化，利用它並行演算法分析性能，可以不取決於特定實現和技術所特有的各種變化，並行演算法一般而言是針對特定計算模型而編寫的，為PRAM機編寫的偽碼通常會採用某種For循環形式的並發編程構造。

編程模型指稱一種編程樣式，即通過看起來像庫調用的方式引發執行。例子包括POSIX的Pthreads庫和Apache Hadoop中的MapReduce。在這二者情況下，執行模型都符合這個庫所用語言的語法卻不能按照其語義來理解。不同於計算模型，編程模型特別暗含著對硬體或軟體實現的實際考慮。

在並行計算中，執行模型經常必須暴露硬體特徵來達成高性能。並行硬體有大量的變種導致了同時需要類似數量的並行執行模型。對每個執行模型都建立一門新語言是不實際的，因此常見的實踐都是通過某個API來引發並行執行模型的行為。並行程式語言可以基於一種或一個組合的編程模型。例如，高性能Fortran基於共享內存交互和數據並行問題分解，而Go提供共享內存交互和消息傳遞交互。

## 並行編程模型

這裡列出的編程模型是可稱為橋接模型的電腦的抽象模型，它提供了在一個機器的物理實現和編程者可獲得的這個機器的抽象概念之間的橋梁；換句話說，它意圖在硬體和軟體工程師之間提供共同的理解層面。成功的編程模型可以在現實中有效的實現並被編程者有效的作為目標；特別是應當有可能用典型的高級語言編譯器生成良好的代碼。從編程者的角度來看，這種橋接並行編程模型一般典型的位於Pthreads、IPC、MPI等之上，而在OpenMP、OpenACC等之下。

名稱｜交互類別｜分解類別｜實現及用例

分叉會合模型｜共享內存｜數據｜Cilk，OpenMP，線程建造塊

整體同步並行模型｜共享內存｜數據｜BSPlib：MulticoreBSP、BSPonMPI，Apache Giraph，Apache Hama

分區全局地址空間模型｜分布式記憶體｜數據｜SHMEM，協同陣列Fortran，Chapel，X10 (程式語言)

通信順序進程模式｜同步消息傳遞｜任務｜Occam，Ada，Go

演員模型｜異步消息傳遞｜任務｜Erlang，D，Scala，很多的框架和庫實現

異構計算框架｜共享內存｜數據｜OpenCL，CUDA，SYCL，Pocl

串流處理/數據流程范型｜管道｜數據｜BrookGPU，Apache Flink，RaftLib，TensorFlow，Lustre

高級綜合電子設計自動化｜通道｜任務｜C轉HDL：Handel-C、SystemC

OpenCL將計算系統視為組成自一組「計算設備」，它們可以是CPU或是附加的「加速器」比如GPU。它定義了一種類C語言用來寫程序。在OpenCL設備上執行的函數叫做「內核」。一個單一的計算設備典型的組成自一些「計算單元」，它們依次又包含很多「處理元素」（PE）。一個單一的內核執行可以在所有或多個PE上並行運行。OpenCL定義了API，允許運行於主機上的程序，啟動在計算設備上的內核，並管理設備記憶體，它至少在概念上分離於主機記憶體。用OpenCL語言寫的程序預期會被即時編譯，所以使用OpenCL的應用程式在針對各種設備的實現之間是可移植的。

FPGA可以被用來解決任何可計算的問題，這通過用FPGA能實現軟微處理器的事實就可輕易的證明。它們的好處在於對某些應用它們明顯的要更快速，因為它們有著並行本質和在對用在特定處理上的邏輯門的數目方面的優化。近年來開始興起使用OpenCL編程來利用FPGA提供的性能和能耗效率。OpenCL允許編程者用C語言編碼並把FPGA組合函數作為使用OpenCL構造的OpenCL計算內核的目標。

MapReduce是通過並行、分布式演算法在集群上處理和生成鍵/值對形式的大數據集的編程模型和有關實現，Apache Hadoop中將它與HDFS分立實現。MapReduce受到了在函數式編程范型中常用的map和reduce函數的啟發，但是它們在MapReduce框架中的用途不同於它們在起初形式中那樣。

並行編程模型還有很多，比如：馬里蘭大學學院市分校依據PRAM計算模型，建立了指令級並行顯式多線程的多處理器電腦和程式語言XMTC，實現了Spawn-Join范型。