- 並行演算法有用資源
- 並行演算法 - 快速指南
- 並行演算法 - 有用資源
- 並行演算法 - 討論
並行隨機存取機
並行隨機存取機 (PRAM)是一種模型，它被認為適用於大多數並行演算法。在這裡，多個處理器連線到單個記憶體塊。PRAM模型包含：
一組類似型別的處理器。
所有處理器共享一個公共記憶體單元。處理器只能透過共享記憶體相互通訊。
一個記憶體訪問單元 (MAU) 將處理器與單個共享記憶體連線起來。
在這裡，n個處理器可以在特定時間單位內對n個數據執行獨立操作。這可能會導致不同的處理器同時訪問相同的記憶體位置。
為了解決這個問題，在PRAM模型上施加了以下約束：
獨佔讀獨佔寫 (EREW) - 在這裡，不允許兩個處理器同時從同一記憶體位置讀取或寫入。
獨佔讀併發寫 (ERCW) - 在這裡，不允許兩個處理器同時從同一記憶體位置讀取，但允許同時寫入同一記憶體位置。
併發讀獨佔寫 (CREW) - 在這裡，允許所有處理器同時從同一記憶體位置讀取，但不允許同時寫入同一記憶體位置。
併發讀併發寫 (CRCW) - 允許所有處理器同時從同一記憶體位置讀取或寫入。
有許多方法可以實現PRAM模型，但最突出的方法是：
- 共享記憶體模型
- 訊息傳遞模型
- 資料並行模型
共享記憶體模型
共享記憶體強調控制並行性而不是資料並行性。在共享記憶體模型中，多個程序在不同的處理器上獨立執行，但它們共享一個公共記憶體空間。由於任何處理器的活動，如果任何記憶體位置發生任何更改，則其他處理器都可以看到。
由於多個處理器訪問同一記憶體位置，因此在任何特定時間點，可能有多個處理器訪問同一記憶體位置。假設一個正在讀取該位置，而另一個正在寫入該位置。這可能會造成混淆。為了避免這種情況，實現了一些控制機制，例如鎖/訊號量，以確保互斥。
共享記憶體程式設計已在以下方面實現：
執行緒庫 - 執行緒庫允許多個控制執行緒在同一記憶體位置併發執行。執行緒庫提供了一個介面，透過子程式庫支援多執行緒。它包含用於以下方面的子程式：
- 建立和銷燬執行緒
- 排程執行緒執行
- 線上程之間傳遞資料和訊息
- 儲存和恢復執行緒上下文
執行緒庫的示例包括：SolarisTM執行緒（用於Solaris），POSIX執行緒（在Linux中實現），Win32執行緒（在Windows NT和Windows 2000中可用）以及作為標準JavaTM開發工具包 (JDK)一部分的JavaTM執行緒。
分散式共享記憶體 (DSM) 系統 - DSM系統在鬆散耦合架構上建立共享記憶體的抽象，以便在沒有硬體支援的情況下實現共享記憶體程式設計。它們實現標準庫並使用現代作業系統中存在的先進使用者級記憶體管理功能。示例包括Tread Marks系統、Munin、IVY、Shasta、Brazos和Cashmere。
程式註釋包 - 這是在具有統一記憶體訪問特性的架構上實現的。程式註釋包最著名的示例是OpenMP。OpenMP實現函式式並行性。它主要關注迴圈的並行化。
共享記憶體的概念提供了對共享記憶體系統的低階控制，但它往往很繁瑣且容易出錯。它更適用於系統程式設計而不是應用程式程式設計。
共享記憶體程式設計的優點
全域性地址空間為使用者提供了友好的記憶體程式設計方法。
由於記憶體與CPU的接近性，程序間的資料共享速度快且一致。
無需明確指定程序間的資料通訊。
程序通訊開銷可忽略不計。
它很容易學習。
共享記憶體程式設計的缺點
- 它不可移植。
- 管理資料區域性性非常困難。
訊息傳遞模型
訊息傳遞是分散式記憶體系統中最常用的並行程式設計方法。在這裡，程式設計師必須確定並行性。在這個模型中，所有處理器都有自己的本地記憶體單元，它們透過通訊網路交換資料。
處理器使用訊息傳遞庫進行相互通訊。除了傳送的資料外，訊息還包含以下元件：
傳送訊息的處理器的地址；
傳送處理器中資料的記憶體位置的起始地址；
傳送資料的型別；
傳送資料的大小；
傳送訊息的處理器的地址；
接收處理器中資料的記憶體位置的起始地址。
處理器可以透過以下任何方法相互通訊：
- 點對點通訊
- 集體通訊
- 訊息傳遞介面
點對點通訊
點對點通訊是最簡單的訊息傳遞形式。在這裡，訊息可以透過以下任何傳輸模式從傳送處理器傳送到接收處理器：
同步模式 - 只有在收到確認其先前訊息已送達後，才傳送下一條訊息，以保持訊息的順序。
非同步模式 - 要傳送下一條訊息，不需要收到先前訊息送達的確認。
集體通訊
集體通訊涉及多個處理器進行訊息傳遞。以下模式允許集體通訊：
屏障 - 如果通訊中包含的所有處理器都執行特定塊（稱為屏障塊）進行訊息傳遞，則屏障模式是可能的。
廣播 - 廣播有兩種型別：
一對多 - 在這裡，一個處理器使用單個操作將相同的訊息傳送到所有其他處理器。
全對全 - 在這裡，所有處理器都向所有其他處理器傳送訊息。
廣播的訊息可能有三種類型：
個性化 - 向所有其他目標處理器傳送唯一的訊息。
非個性化 - 所有目標處理器都收到相同的訊息。
歸約 - 在歸約廣播中，組中的一個處理器從組中的所有其他處理器收集所有訊息，並將它們組合成一條單一訊息，組中的所有其他處理器都可以訪問該訊息。
訊息傳遞的優點
- 提供對並行性的低階控制；
- 它是可移植的；
- 錯誤更少；
- 並行同步和資料分佈的開銷較少。
訊息傳遞的缺點
與並行共享記憶體程式碼相比，訊息傳遞程式碼通常需要更多的軟體開銷。
訊息傳遞庫
有很多訊息傳遞庫。在這裡，我們將討論兩個最常用的訊息傳遞庫：
- 訊息傳遞介面 (MPI)
- 並行虛擬機器 (PVM)
訊息傳遞介面 (MPI)
這是一個通用標準，用於在分散式記憶體系統中的所有併發程序之間提供通訊。大多數常用的平行計算平臺至少提供了一種訊息傳遞介面的實現。它已被實現為稱為庫的預定義函式的集合，並且可以從C、C++、Fortran等語言呼叫。與其他訊息傳遞庫相比，MPI速度快且可移植。
訊息傳遞介面的優點
僅在共享記憶體架構或分散式記憶體架構上執行；
每個處理器都有自己的區域性變數；
與大型共享記憶體計算機相比，分散式記憶體計算機成本更低。
訊息傳遞介面的缺點
- 並行演算法需要更多程式設計更改；
- 有時難以除錯；並且
- 在節點之間的通訊網路中效能不佳。
並行虛擬機器 (PVM)
PVM是一個可移植的訊息傳遞系統，旨在連線獨立的異構主機機器以形成單個虛擬機器。它是一個易於管理的平行計算資源。像超導性研究、分子動力學模擬和矩陣演算法這樣的大型計算問題可以透過使用許多計算機的記憶體和總功率來更經濟有效地解決。它管理網路中不相容計算機架構的所有訊息路由、資料轉換和任務排程。
PVM 的特點
- 非常易於安裝和配置；
- 多個使用者可以同時使用PVM；
- 一個使用者可以執行多個應用程式；
- 它是一個小包；
- 支援C、C++、Fortran；
- 對於給定的PVM程式執行，使用者可以選擇機器組；
- 它是一個訊息傳遞模型，
- 基於程序的計算；
- 支援異構架構。
資料並行程式設計
資料並行程式設計模型的主要重點是同時對資料集執行操作。資料集被組織成某種結構，例如陣列、超立方體等。處理器對相同的資料結構進行集體操作。每個任務都在相同資料結構的不同分割槽上執行。
它是有限制的，因為並非所有演算法都可以用資料並行性來指定。這就是資料並行性不是通用的原因。
資料並行語言有助於指定資料分解和對映到處理器。它還包括資料分佈語句，允許程式設計師控制資料——例如，哪些資料將放在哪個處理器上——以減少處理器內部的通訊量。