并行编程模型

在電腦科學中，**並列編程模型**（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 採用的 SIMT （例如 NVIDIA Tesla）。

#### 任務並列

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

### 隱式並列

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

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

## 術語

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

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

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

## 並列編程模型

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

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 範式。

## 參見

* 並行計算
* 異構計算
* 高效能計算
* 叢集計算
* 分散式計算
* 並行及並列程式語言列表
* 遠端直接記憶體存取
* 並列外部記憶體

## 參照

## 進一步閱讀

* Blaise Barney, Introduction to Parallel Computing, Lawrence Livermore National Laboratory
* Murray I. Cole., Algorithmic Skeletons: Structured Management of Parallel Computation (PDF), University of Glasgow
* J. Darlinton; M. Ghanem; H. W. To, Structured Parallel Programming (PDF), In Programming Models for Massively Parallel Computers. IEEE Computer Society Press, 1993
* Ian Foster, Designing and Building Parallel Programs, Argonne National Laboratory