并行計算模型是指從并行算法的設計和分析出發，將各種并行計算機的基本特征抽象出來的計算模型。這些模型不僅為并行計算提供了硬件和軟件界面，還使得并行系統硬件設計者和軟件設計者能夠開發出對并行性的支持機制，從而提升系統的性能。
PRAM模型
類型
PRAM（Parallel Random Access Machine，隨機存取并行機器）模型，也被稱為共享存儲的SIMD模型，是從串行的RAM模型直接發展而來的一種抽象的并行計算模型。在這個模型中，有一個容量無限大的共享存儲器，有限個或無限個功能相同的處理器，它們都能進行簡單的算術運算和邏輯判斷，并能在任何時候通過共享存儲單元互相交流數據。根據處理器對共享存儲單元同時讀、同時寫的限制，PRAM模型可分為以下類型：
獨占讀寫（EREW）的PRAM模型
不允許同時讀和同時寫，簡稱PRAM-EREW。
同時讀獨占寫（CREW）的PRAM模型
允許同時讀但不允許同時寫，簡稱PRAM-CREW。
同時讀寫（CRCW）的PRAM模型
允許同時讀和同時寫，簡稱PRAM-CRCW。
共同CRCW（CPRAM-CRCW）模型
只允許所有處理器同時寫相同的數。
優先CRCW（PPRAM-CRCW）模型
只允許最優先的處理器先寫。
隨意CRCW（APRAM-CRCW）模型
允許任意處理器自由寫。
求和CRCW（SPRAM-CRCW）模型
往存儲器中寫的實際內容是所有處理器寫的數的和。
在這些模型中，PRAM-EREW是最弱的功能模型，而PRAM-CRCW則是最強的功能模型。具體地說，一個具有時間復雜度為TCREW或TCRCW的算法，在PRAM-EREW模型上要花費logp倍的時間去模擬實現。
PRAM模型的優點
PRAM模型特別適合于并行算法的表達、分析和比較，使用簡單，許多關于并行計算機的底層細節，如處理器間通信、存儲系統管理和進程同步都被隱含在模型中。此外，該模型易于設計算法，并且經過適當修改后，可以在不同的并行計算機系統上運行。根據需要，還可以在PRAM模型中添加諸如同步和通信等內容。
PRAM模型的缺點
PRAM模型有一些局限性和挑戰，其中包括：
1. 模型中使用了一個全局共享存儲器，且局存容量較小，不足以描述分布主存多處理機的性能瓶頸。此外，共享單一存儲器的假定，顯然不適合于分布存儲結構的MIMD機器。
2. PRAM模型是同步的，這意味著所有的指令都按鎖步方式進行操作。盡管用戶感覺不到同步的存在，但它確實會消耗時間，并且無法反映現實中很多系統的異步性。
3. PRAM模型假設每個處理器均可在單位時間內訪問共享存儲器的任一單元，這一假設忽略了實際存在的細節，如資源競爭和有限帶寬，這是不現實的。
4. PRAM模型假設處理機有限或無限，對并行任務的增大無開銷。
5. 未能描述所線程技術和流水線預取技術，這兩種技術是當今并行體系結構中最常用的技術。
BSP模型
特點
BSP模型（Bulk Synchronous Parallel model）是一種分布存儲的MIMD計算模型，其特點包括：
1. 將處理器和路由器分開，強調了計算任務和通信任務的分離，而路由器僅負責點到點的消息傳遞，不提供組合、復制和廣播等功能。這種方法既掩蓋了具體的互連網絡拓撲，又簡化了通信協議。
2. 采用障礙同步的方式，以硬件實現的全局同步是在可控的粗粒度級別，從而提供了執行緊耦合同步式并行算法的有效方式，而程序員無需承擔過多的負擔。
3. 分析BSP模型的性能時，假設局部操作可以在一個時間步內完成，而在每個超級步中，一個處理器最多發送或接收h條消息（稱為h-relation）。假定s是傳輸建立時間，所以傳送h條消息的時間為gh+s。如果，則L至少應大于等于gh。很明顯，硬件可以將L設置得盡可能小（例如使用流水線或大的通信帶寬使g盡可能小），而軟件可以設置L的上限（因為L越大，并行粒度越大）。在實際使用中，g可以定義為每秒處理器所能完成的局部計算數目與每秒路由器所能傳輸的數據量之比。如果能夠適當地平衡計算和通信，則BSP模型在可編程性方面具有顯著的優勢，而直接在BSP模型上執行算法（而不是自動編譯它們），這一優勢將隨著g的增加而變得更加明顯。
4. 為PRAM模型所設計的算法，都可以采用在每個BSP處理器上模擬一些PRAM處理器的方法來實現。理論分析表明，這種模擬在常數因子范圍內是最佳的，只要并行松弛度（Parallel Slackness），即每個BSP處理器所能模擬的PRAM處理器的數量足夠大。在并發情況下，多個處理器同時訪問分布式的存儲器可能會引發一些問題，但使用哈希方法可以使程序均勻地訪問分布式存儲器。在PRAM-EREW情況下，如果所選擇的哈希函數足夠有效，則L至少是對數級別的，因此模擬可以達到最佳狀態。這是因為我們希望在p個物理處理器的BSP模型上，模擬個虛擬處理器，可將個虛擬處理器分配給每個物理處理器。在一個超級步內，v次存取請求可以均勻分布，每個處理器大約v/p次，因此計算機執行本次超級步的最佳時間為O(v/p)，且概率是高的。同樣，在v個處理器的PRAM-CRCW模型中，能夠在p個處理器（如果），和的BSP模型上用O(v/p)的時間也可以達到最佳模擬。
評價
BSP模型嘗試為軟件和硬件之間搭建一座類似于馮·諾依曼機的橋梁，Valiant論證了BSP模型可以起到這樣的作用，因此BSP模型也常被稱為橋模型。一般來說，分布存儲的MIMD模型的可編程性較差，但在BSP模型中，如果計算和通信可以適當地平衡（例如g=1），則它在可編程方面展現出顯著的優點。在BSP模型上，已經直接實現了若干重要算法（如矩陣乘法、并行前綴運算、快速傅里葉變換和排序等），這些算法都避免了自動存儲管理的額外開銷。BSP模型可以在超立方體網絡和光交叉開關互連技術上有效地實現，顯示出了該模型與特定技術實現無關，只要路由器具有一定的通信吞吐率。然而，BSP模型也有一些局限性，包括：
1. 超級步的長度必須能夠充分適應任意的h-relation，這是人們不太喜歡的一點。
2. 在BSP模型中，在超級步開始發送的消息，即使網絡延遲時間比超級步的長度短，它也只能在下一個超級步才能使用。
3. BSP模型中的全局障礙同步假定是用特殊硬件支持的，這在很多并行機中可能沒有相應的硬件。
4. Valiant提出的編程模擬環境，在算法模擬時的常數可能并不很小，如果考慮到進程間的切換（可能不僅要設置寄存器，而且還可能涉及部分高速緩存），則這個常數可能很大。
LogP模型
描述
LogP模型（Logarithmic in the Product of Parameters model）是由D.Culer等人在1993年提出的，旨在捕捉分布式存儲計算機的特點，并充分說明互聯網絡的性能特性，而不涉及具體的網絡結構，也不假定算法必須用現實的消息傳遞操作進行描述。LogP模型是一種分布存儲的、點到點通信的多處理機模型，其中通信網絡由四個主要參數描述：
1. L（Latency）表示源處理機與目標處理機進行消息（一個或幾個字）通信所需的等待或延遲時間的上限，表示網絡中消息的延遲。
2. o（Overhead）表示處理機準備發送或接收每個消息的時間開銷（包括操作系統核心開銷和網絡軟件開銷），在此期間處理機不能執行其他操作。
3. g（Gap）表示一臺處理機連續兩次發送或接收消息時的最小時間間隔，其倒數即微處理機的通信帶寬。
4. P（Processor）處理機/存儲器模塊數量。
假定一個周期完成一次局部操作，并定義為一個時間單位，那么，L，o和g都可以表示成處理器周期的整數倍。
特點
LogP模型的特點包括：
1. 抓住了網絡與處理機之間的性能瓶頸。g反映了通信帶寬，單位時間內最多有L/g個消息能進行處理機間傳送。
2. 處理機之間異步工作，并通過處理機間的消息傳送來完成同步。
3. 對多線程技術有所體現。每個物理處理機可以模擬多個虛擬處理機（VP），當某個VP有訪問請求時，計算不會終止，但VP的個數受限于通信帶寬和上下文交換的開銷。VP受限于網絡容量，至多有L/g個VP。
4. 消息延遲不確定，但延遲不大于L。消息經歷的等待時間是不可預測的，但在沒有阻塞的情況下，最大不超過L。
5. LogP模型鼓勵編程人員采用一些良好的策略，如作業分配、計算與通信重疊以及平衡的通信模式等。
6. 可以估算算法的實際運行時間。
不足之處
LogP模型也有其局限性，主要包括：
1. 對網絡中的通信模式描述不夠深入。如重發消息可能占滿帶寬、中間路由器緩存飽和等未加描述。
2. LogP模型主要適用于消息傳遞算法設計，對于共享存儲模式，則簡單地認為遠地讀操作相當于兩次消息傳遞，未考慮流水線預取技術、Cache引起的數據不一致性以及Cache命中率對計算的影響。
3. 未考慮多線程技術的上下文開銷。
4. LogP模型假設用點對點消息路由器進行通信，這增加了編程者考慮路由器上相關通信操作的負擔。
C3模型
C3模型（Communication Complexity model）由J.F.JaJa等人在1996年提出，這是一種塊分布存儲模型（Block Distributed Model），也是共享存儲編程模式與基于消息傳遞的分布存儲系統之間的橋梁模型。C3模型的主要參數包括：
1. P 處理器個數。
2. τ 處理機從發出訪問請求到得到遠程數據的最大延遲時間（包括準備請求時間、請求包在網絡中路由的時間、目的處理機接收請求的時間以及將包中M個連續字返回給原處理機的時間）。
3. M 局部存儲器中連續的M個字。
4. σ 處理機發送數據到網絡或從網絡接收數據的時間。
特點
C3模型的特點包括：
1. 使用Cl和Cp來衡量網絡的擁擠對算法性能的影響。
2. 考慮了不同路由和不同發送或接收原語對通信的影響。
3. 不需要用戶指定調度細節，即可評估超步的時間復雜性。
4. 類似于H-PRAM模型的層次結構，C3模型為編程者提供了K級路由算法的思路，即將系統劃分為K級子系統，各級子系統的操作相互獨立，用超步代替了H-PRAM中的Sub PRAM進行分割。
不足之處
C3模型的不足之處包括：
1. Cl度量的前提假設為同一通信對中的兩個處理機要分別位于網絡劃分后的不同子網絡內。
2. 模型假設了網絡帶寬等于處理機帶寬，這影響了正確描述可擴展系統。
3. 在K級算法中，處理機間的順序可以由多種排列，但C3模型不能區分不同排列的難易程度。
BDM模型
BDM模型（Block Distributed Model）由J.F.JaJa等人在1996年提出，這是一種塊分布存儲模型，也是共享存儲編程模式與基于消息傳遞的分布存儲系統之間的橋梁模型。BDM模型的主要參數包括：
1. P 處理器個數。
2. τ 處理機從發出訪問請求到得到遠程數據的最大延遲時間（包括準備請求時間、請求包在網絡中路由的時間、目的處理機接收請求的時間以及將包中M個連續字返回給原處理機的時間）。
3. M 局部存儲器中連續的M個字。
4. σ 處理機發送數據到網絡或從網絡接收數據的時間。
特點
BDM模型的特點包括：
1. 使用M反映出空間局部性特點，提供了一種評價共享主存算法的性能方法，度量了因遠程訪問引起的處理間的通信。
2. BDM認可流水線技術。某個處理機的K次預取所需的時間為τ+KMσ （否則為K(τ+Mσ))。
3. 可編程型好。
4. 考慮了共享主存中的存儲競爭問題。
5. 可以用來分析網絡路由情況。
不足
BDM模型的不足之處包括：
1. 假設初始數據置于局存中，對于共享主存程序的編程者來說，需要額外增加數據移動操作。
2. 未考慮網絡中影響延遲的因素（如處理機的本地性、網絡重擁擠等）。
3. 未考慮系統開銷。
參考資料 >
并行計算模型.CSDN博客.2024-10-29
一篇文章搞懂并行計算模型.一篇文章搞懂并行計算模型.2024-10-29