並行演算法 - 結構

為了正確應用任何演算法，選擇合適的的資料結構非常重要。這是因為在特定資料結構上執行的特定操作可能比在另一個數據結構上執行相同操作花費更多時間。

示例 - 使用陣列訪問集合中的第 i 個元素可能需要常數時間，但使用連結串列，執行相同操作所需的時間可能會變成多項式。

因此，必須考慮體系結構和要執行的操作型別來選擇資料結構。

以下資料結構通常用於並行程式設計：

• 連結串列
• 陣列
• 超立方體網路

連結串列

連結串列是一種資料結構，它具有零個或多個透過指標連線的節點。節點可能佔用也可能不佔用連續的記憶體位置。每個節點有兩個或三個部分 - 一個資料部分儲存資料，另外兩個是連結欄位，儲存前一個或下一個節點的地址。第一個節點的地址儲存在一個稱為頭的外部指標中。最後一個節點，稱為尾，通常不包含任何地址。

連結串列有三種類型：

• 單鏈表
• 雙鏈表
• 迴圈連結串列

單鏈表

單鏈表的節點包含資料和下一個節點的地址。一個稱為頭的外部指標儲存第一個節點的地址。

雙鏈表

雙鏈表的節點包含資料以及前一個和下一個節點的地址。一個稱為頭的外部指標儲存第一個節點的地址，另一個稱為尾的外部指標儲存最後一個節點的地址。

迴圈連結串列

迴圈連結串列與單鏈表非常相似，除了最後一個節點儲存第一個節點的地址這一事實。

陣列

陣列是一種資料結構，我們可以在其中儲存類似型別的資料。它可以是一維的或多維的。陣列可以靜態或動態建立。

• 在靜態宣告的陣列中，陣列的維度和大小在編譯時已知。

• 在動態宣告的陣列中，陣列的維度和大小在執行時已知。

對於共享記憶體程式設計，陣列可以用作公共記憶體；對於資料並行程式設計，可以透過將其劃分為子陣列來使用它們。

超立方體網路

超立方體架構對於那些每個任務必須與其他任務通訊的並行演算法很有幫助。超立方體拓撲可以輕鬆嵌入其他拓撲，例如環和網格。它也稱為 n 維超立方體，其中n是維數。超立方體可以遞迴地構造。