- 並行演算法有用資源
- 並行演算法 - 快速指南
- 並行演算法 - 有用資源
- 並行演算法 - 討論
並行演算法 - 簡介
一個演算法是一系列步驟，這些步驟接收使用者的輸入，經過一些計算後產生輸出。一個並行演算法是一種演算法，它可以在不同的處理裝置上同時執行多個指令，然後將所有單個輸出組合起來以產生最終結果。
併發處理
計算機的易用性以及網際網路的增長改變了我們儲存和處理資料的方式。我們生活在一個數據大量可用的時代。每天我們都要處理大量需要複雜計算的資料，而且還要在短時間內完成。有時，我們需要從同時發生的類似或相互關聯的事件中提取資料。這就是我們需要併發處理的地方，它可以將複雜的任務分解並將其處理到多個系統中，以便在短時間內產生輸出。
併發處理在任務涉及處理大量複雜資料時必不可少。例如 - 訪問大型資料庫、飛機測試、天文計算、原子和核物理、生物醫學分析、經濟規劃、影像處理、機器人技術、天氣預報、基於 Web 的服務等。
什麼是並行性？
並行性是同時處理多組指令的過程。它減少了總計算時間。並行性可以透過使用平行計算機來實現，即具有多個處理器的計算機。平行計算機需要並行演算法、程式語言、編譯器和支援多工處理的作業系統。
在本教程中，我們只討論並行演算法。在繼續之前，讓我們先討論一下演算法及其型別。
什麼是演算法？
一個演算法是一系列用於解決問題的指令。在設計算法時，我們應該考慮演算法將在其上執行的計算機的體系結構。根據體系結構，計算機有兩種型別：
- 順序計算機
- 平行計算機
根據計算機的體系結構，我們有兩種型別的演算法：
順序演算法 - 一種演算法，其中一些連續的指令步驟按時間順序執行以解決問題。
並行演算法 - 問題被分解成子問題，並並行執行以獲得單個輸出。隨後，將這些單個輸出組合在一起以獲得最終所需的輸出。
將一個大問題分解成子問題並不容易。子問題之間可能存在資料依賴關係。因此，處理器必須相互通訊以解決問題。
已經發現，處理器之間相互通訊所需的時間多於實際處理時間。因此，在設計並行演算法時，應考慮適當的 CPU 利用率以獲得有效的演算法。
為了正確設計算法，我們必須清楚地瞭解平行計算機中的基本計算模型。
計算模型
順序和平行計算機都根據一組（流）稱為演算法的指令進行操作。這些指令集（演算法）指示計算機在每個步驟中必須執行的操作。
根據指令流和資料流，計算機可以分為四類：
- 單指令流，單資料流 (SISD) 計算機
- 單指令流，多資料流 (SIMD) 計算機
- 多指令流，單資料流 (MISD) 計算機
- 多指令流，多資料流 (MIMD) 計算機
SISD 計算機
SISD 計算機包含一個控制單元、一個處理單元和一個儲存單元。
在這種型別的計算機中，處理器從控制單元接收單個指令流，並對來自儲存單元的單個數據流進行操作。在計算過程中，在每個步驟中，處理器從控制單元接收一條指令，並對從儲存單元接收的單個數據進行操作。
SIMD 計算機
SIMD 計算機包含一個控制單元、多個處理單元和共享記憶體或互連網路。
在這裡，一個控制單元將指令傳送到所有處理單元。在計算過程中，在每個步驟中，所有處理器都從控制單元接收一組指令，並對來自儲存單元的不同資料集進行操作。
每個處理單元都有自己的本地儲存單元來儲存資料和指令。在 SIMD 計算機中，處理器需要相互通訊。這是透過共享記憶體或互連網路完成的。
當一些處理器執行一組指令時，其餘處理器等待它們的下一組指令。來自控制單元的指令決定哪個處理器將處於活動狀態（執行指令）或處於非活動狀態（等待下一條指令）。
MISD 計算機
顧名思義，MISD 計算機包含多個控制單元、多個處理單元和一個公共儲存單元。
在這裡，每個處理器都有自己的控制單元，它們共享一個公共儲存單元。所有處理器都分別從自己的控制單元獲取指令，並根據從各自控制單元接收的指令對單個數據流進行操作。此處理器同時執行。
MIMD 計算機
MIMD 計算機具有多個控制單元、多個處理單元以及共享記憶體或互連網路。
在這裡，每個處理器都有自己的控制單元、本地儲存單元以及算術和邏輯單元。它們從各自的控制單元接收不同的指令集，並對不同的資料集進行操作。
注意
共享公共記憶體的 MIMD 計算機稱為多處理器，而使用互連網路的計算機稱為多計算機。
根據處理器的物理距離，多計算機分為兩種型別：
多計算機 - 當所有處理器彼此非常靠近時（例如，在同一個房間裡）。
分散式系統 - 當所有處理器彼此相距很遠時（例如，在不同的城市中）。