什麼是並行演算法？

並行演算法是專門為平行計算機設計的演算法。如果不存在物理約束或通訊開銷，則理想化的並行演算法是為 PRAM 模型編寫的演算法。在現實世界中，只有當演算法能夠以經濟高效的方式在物理機器上實現時，才被認為是有效的。從這個意義上講，所有可機器實現的演算法都必須依賴於體系結構。這意味著不能忽略通訊開銷和體系結構約束的影響。

並行演算法的特徵

並行演算法有以下幾種特徵：

• 確定性與非確定性 − 只有確定性演算法才能在實際機器上實現。我們的研究僅限於具有多項式時間複雜度的確定性演算法。
• 計算粒度 − 粒度決定了計算中使用的資料項和程式模組的大小。從這個意義上講，我們還將演算法分類為細粒度、中粒度或粗粒度。
• 並行性輪廓 − 演算法中並行度的分佈揭示了並行處理的機會。這通常會影響並行演算法的有效性。
• 通訊模式和同步需求 − 通訊模式涉及記憶體訪問和處理器間通訊。模式可以是靜態的或動態的，具體取決於演算法。靜態演算法更適合 SIMD 或流水線機器，而動態演算法則適用於 MIMD 機器。同步頻率通常會影響演算法的效率。
• 操作的統一性 − 這指的是要執行的基本操作型別。如果操作在整個資料集上是統一的，則 SIMD 處理或流水線處理可能更可取。換句話說，隨機結構的演算法更適合 MIMD 處理。其他相關問題包括所需的資料型別和精度。
• 記憶體需求和資料結構 − 在解決大型問題時，資料集可能需要巨大的記憶體空間。記憶體效率受所選資料結構和演算法中的資料移動模式的影響。時間和空間複雜度都是並行演算法粒度的關鍵度量。

Ginni

更新於： 2021年7月30日

940 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習