并行算法 - 结构

为了正确应用任何算法，选择合适的的数据结构非常重要。这是因为在特定数据结构上执行的特定操作可能比在另一个数据结构上执行相同操作花费更多时间。

示例 - 使用数组访问集合中的第 i 个元素可能需要常数时间，但使用链表，执行相同操作所需的时间可能会变成多项式。

因此，必须考虑体系结构和要执行的操作类型来选择数据结构。

以下数据结构通常用于并行编程：

• 链表
• 数组
• 超立方体网络

链表

链表是一种数据结构，它具有零个或多个通过指针连接的节点。节点可能占用也可能不占用连续的内存位置。每个节点有两个或三个部分 - 一个数据部分存储数据，另外两个是链接字段，存储前一个或下一个节点的地址。第一个节点的地址存储在一个称为头的外部指针中。最后一个节点，称为尾，通常不包含任何地址。

链表有三种类型：

• 单链表
• 双链表
• 循环链表

单链表

单链表的节点包含数据和下一个节点的地址。一个称为头的外部指针存储第一个节点的地址。

双链表

双链表的节点包含数据以及前一个和下一个节点的地址。一个称为头的外部指针存储第一个节点的地址，另一个称为尾的外部指针存储最后一个节点的地址。

循环链表

循环链表与单链表非常相似，除了最后一个节点保存第一个节点的地址这一事实。

数组

数组是一种数据结构，我们可以在其中存储类似类型的数据。它可以是一维的或多维的。数组可以静态或动态创建。

• 在静态声明的数组中，数组的维度和大小在编译时已知。

• 在动态声明的数组中，数组的维度和大小在运行时已知。

对于共享内存编程，数组可以用作公共内存；对于数据并行编程，可以通过将其划分为子数组来使用它们。

超立方体网络

超立方体架构对于那些每个任务必须与其他任务通信的并行算法很有帮助。超立方体拓扑可以轻松嵌入其他拓扑，例如环和网格。它也称为 n 维超立方体，其中n是维数。超立方体可以递归地构造。