並行演算法 - 模型

並行演算法模型是透過考慮資料和處理方法的劃分策略，並應用合適的策略來減少互動而開發的。在本章中，我們將討論以下並行演算法模型：

資料並行

在資料並行模型中，任務被分配給程序，每個任務對不同的資料執行類似型別的操作。資料並行性是單個操作應用於多個數據項的結果。

資料並行模型可以應用於共享地址空間和訊息傳遞正規化。在資料並行模型中，可以透過選擇保留區域性性的分解、使用最佳化的集體互動例程或透過重疊計算和互動來減少互動開銷。

資料並行模型問題的首要特徵是資料並行性的強度隨著問題的規模而增加，這反過來使得可以使用更多程序來解決更大的問題。

示例 - 密集矩陣乘法。

在任務圖模型中，並行性由任務圖表示。任務圖可以是平凡的或非平凡的。在這個模型中，利用任務之間的相關性來促進區域性性或最小化互動成本。此模型用於解決與任務關聯的資料量與關聯的計算量相比非常大的問題。分配任務有助於改善任務之間資料移動的成本。

示例 - 並行快速排序、稀疏矩陣分解和透過分治法匯出的並行演算法。

在此，問題被劃分為原子任務並實現為一個圖。每個任務都是一個獨立的作業單元，它依賴於一個或多個先前的任務。在完成任務後，先前任務的輸出將傳遞給依賴任務。只有當它的所有先前任務都完成後，具有先前任務的任務才會開始執行。當最後一個依賴任務完成時（上圖中的任務 6），將收到圖的最終輸出。

在工作池模型中，任務被動態分配給程序以平衡負載。因此，任何程序都可能執行任何任務。當與任務關聯的資料量與關聯的計算量相比相對較小時，使用此模型。

沒有對任務到程序的預先分配。任務的分配是集中式或分散式的。指向任務的指標儲存在物理共享列表、優先順序佇列或雜湊表或樹中，或者它們可以儲存在物理分散式資料結構中。

任務可能在一開始就可用，也可能動態生成。如果任務是動態生成的並且進行了分散的任務分配，則需要終止檢測演算法，以便所有程序實際上都可以檢測到整個程式的完成並停止尋找更多工。

示例 - 並行樹搜尋

在主從模型中，一個或多個主程序生成任務並將其分配給從程序。如果以下情況，則可以預先分配任務：

此模型通常同樣適用於共享地址空間或訊息傳遞正規化，因為互動本質上是雙向的。

在某些情況下，任務可能需要分階段完成，並且每個階段的任務必須在生成下一階段的任務之前完成。主從模型可以推廣到分層或多級主從模型，其中頂級主控將大部分任務饋送到二級主控，二級主控進一步將任務細分給自己的從屬並可能執行一部分任務本身。

應注意確保主控不會成為擁塞點。如果任務太小或工作程式相對較快，則可能會發生這種情況。

應以執行任務的成本支配通訊成本和同步成本的方式選擇任務。

非同步互動可以幫助重疊互動和主控關聯的工作生成相關的計算。

它也稱為生產者-消費者模型。在這裡，一組資料透過一系列程序傳遞，每個程序對它執行某些任務。在這裡，新資料的到達會生成程序在佇列中執行新任務。這些程序可以形成線性或多維陣列、樹或具有或不具有迴圈的一般圖形狀的佇列。

此模型是生產者和消費者鏈。佇列中的每個程序都可以被認為是佇列中前一個程序的一系列資料項的消費者，並且是佇列中後一個程序的資料生產者。佇列不需要是線性鏈；它可以是有向圖。適用於此模型的最常見的互動最小化技術是將互動與計算重疊。

示例 - 並行 LU 分解演算法。

當需要多個模型來解決問題時，需要混合演算法模型。

混合模型可以由分層應用的多個模型或順序應用於並行演算法的不同階段的多個模型組成。

示例 - 並行快速排序

列印頁面