并行算法 - 模型

并行算法的模型是通过考虑划分数据的策略和处理方法并应用合适的策略来减少交互而开发的。在本章中，我们将讨论以下并行算法模型 -

数据并行

在数据并行模型中，任务被分配给进程，每个任务对不同的数据执行类似类型的操作。数据并行性是对多个数据项应用单个操作的结果。

数据并行模型可以应用于共享地址空间和消息传递范例。在数据并行模型中，可以通过选择局部性保留分解、使用优化的集体交互例程或通过重叠计算和交互来减少交互开销。

数据并行模型问题的主要特征是数据并行性的强度随着问题的规模而增加，这反过来又使得使用更多的进程来解决更大的问题成为可能。

示例- 密集矩阵乘法。

在任务图模型中，并行性通过任务图来表达。任务图可以是平凡的，也可以是重要的。在该模型中，利用任务之间的相关性来促进局部性或最小化交互成本。该模型用于解决与任务相关的数据量相对于任务相关的计算量来说巨大的问题。分配这些任务是为了帮助提高任务之间数据移动的成本。

示例- 并行快速排序、稀疏矩阵分解以及通过分而治之方法导出的并行算法。

在这里，问题被划分为Atomics任务并以图的形式实现。每个任务都是一个独立的作业单元，依赖于一个或多个先前任务。任务完成后，先行任务的输出将传递给从属任务。具有先行任务的任务仅在其整个先行任务完成时才开始执行。当最后一个依赖任务完成时（上图中的任务 6），接收到图的最终输出。

在工作池模型中，任务被动态分配给进程以平衡负载。因此，任何进程都可能执行任何任务。当与任务相关的数据量相对小于与任务相关的计算量时，使用该模型。

不需要将任务预先分配到流程上。任务分配可以是集中式的，也可以是分散式的。指向任务的指针保存在物理共享列表、优先级队列、哈希表或树中，或者它们可以保存在物理分布式数据结构中。

该任务可能在一开始就可用，或者可以动态生成。如果任务是动态生成的，并且任务的分散分配，那么就需要一个终止检测算法，以便所有进程能够真正检测到整个程序的完成，并停止寻找更多的任务。

示例- 并行树搜索

在主从模型中，一个或多个主进程生成任务并将其分配给从进程。如果出现以下情况，可以提前分配任务：

该模型通常同样适用于共享地址空间或消息传递范例，因为交互自然是两种方式。

在某些情况下，一个任务可能需要分阶段完成，并且每个阶段的任务必须完成后才能生成下一阶段的任务。主从模型可以推广为分层或多级主从模型，其中顶级主站将大部分任务提供给第二级主站，第二级主站进一步将任务细分给自己的从站，并可以执行任务本身的一部分。

应注意确保主站不会成为拥塞点。如果任务太小或工作人员速度相对较快，则可能会发生这种情况。

选择任务时应确保执行任务的成本主导通信成本和同步成本。

异步交互可以帮助重叠交互和与主机的工作生成相关联的计算。

它也被称为生产者-消费者模型。这里，一组数据通过一系列进程传递，每个进程都对其执行一些任务。这里，新数据的到来会导致队列中的进程执行新任务。这些进程可以形成线性或多维数组、树或带或不带循环的一般图形状的队列。

这个模型是一个生产者和消费者的链条。队列中的每个进程可以被视为队列中其前面的进程的一系列数据项的消费者，以及队列中其后面的进程的数据的生产者。队列不需要是线性链；它可以是有向图。适用于该模型的最常见交互最小化技术是与计算重叠交互。

示例- 并行 LU 分解算法。

当可能需要多个模型来解决问题时，需要混合算法模型。

混合模型可以由分层应用的多个模型或顺序应用于并行算法的不同阶段的多个模型组成。

示例- 并行快速排序