並行計算模型

引言

所謂計算模型實際上是軟體和硬體之間的一種橋樑，使用它能夠設計、分析演算法，在其上高級語言能被有效的編譯且能夠用硬體來實現。

串列計算時，典型的，被公認的，通用的計算模型是馮?諾依曼機。但是並行計算時，沒有一個類似馮?諾依曼機被公認的，通用的計算模型。

現在流行的並行計算模型要麼過於簡單、抽象（如 ），要麼過於專用（如 互聯網路模型）。在這裡，我們先介紹一些常用的並行計算模型：模型，非同步模型，模型和模型。

PRAM模型

基本概念

由和 1978年提出，又稱模型。有一個集中的共享存儲器和一個指令控制器，通過SM的R/W交換數據，隱式同步計算。

結構圖

分類

並發讀並發寫

(Common PRAM-CRCW)：僅允許寫入相同數據

(Priority PRAM-CRCW)：僅允許優先順序最高的處理器寫入

(Arbitrary PRAM-CRCW)：允許任意處理器自由寫入

並發讀互斥寫

互斥讀互斥寫

計算能力比較

是最強的計算模型，可倍模擬和。

優缺點

優點：適合併行演算法表示和複雜性分析，易於使用，隱藏了並行機的通訊、同步等細節。

缺點：不適合併行機，忽略了SM的競爭、通訊延遲等因素

非同步PRAM模型

基本概念

又稱分相（）或。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器非同步執行；處理器通過SM進行通訊；處理器間依賴關係，需在並行程序中顯式地加入同步路障。

指令類型

全局讀：將全局存儲單元中的內容讀入局存單元中

局部操作：對局存中的數執行操作，其結果存入局存中。

全局寫：將局存單元中內容寫入全局存儲單元中。

同步：同步是計算中的一個邏輯點，在該點各個處理器均需等待別的處理器操作完成後才能繼續執行其局部程序。

計算過程

計算時間

優缺點

易編程和分析演算法的複雜度，但與現實相差較遠，其上並行演算法非常有限，也不適合模型。

BSP模型

基本概念

由Valiant(1990)提出的，「塊」同步模型，是一種非同步模型，支持消息傳遞系統，塊內非同步並行，塊間顯式同步。

模型參數

p：處理器數(帶有存儲器)

l：同步障時間(Barrier synchronization time)

g：帶寬因子(time steps/packet)=1/bandwidth)

計算過程

由若干超級步組成，每個超級步計算模式如下圖所示：

優缺點

強調了計算和通訊的分離，提供了一個編程環境，易於程序複雜性分析。但需要顯式同步機制，限制至多h條消息的傳遞等。

LogP模型

基本概念

由Culler(1993)年提出的，是一種分布存儲的、點到點通訊的多處理機模型，其中通訊由一組參數描述，實行隱式同步。

模型參數

L：network latency

o：communication overhead

g：gap=1/bandwidth

P：#processors

註：L和g反映了通訊網路的容量

優缺點

捕捉了MPC的通訊瓶頸，隱藏了並行機的網路拓撲、路由、協議，可以應用到共享存儲、消息傳遞、數據並行的編程模型中；但難以進行演算法描述、設計和分析。

BSP模型 vs LogP模型

BSP -> LogP：BSP塊同步?BSP子集同步?BSP進程對同步＝LogP

BSP可以常數因子模擬LogP，LogP可以對數因子模擬BSP

BSP＝LogP+Barriers－Overhead

BSP提供了更方便的程設環境，LogP更好地利用了機器資源

BSP似乎更簡單、方便和符合結構化編程

參考

[並行計算——結構·演算法·編程].陳國良

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！