并行算法 - 模型

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

数据并行

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

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

数据并行模型问题的主要特征是数据并行性的强度随着问题规模的增大而增加，从而可以使用更多的进程来解决更大的问题。

示例 − 密集矩阵乘法。

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

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

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

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

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

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

示例 − 并行树搜索

在主从模型中，一个或多个主进程生成任务并将其分配给从进程。任务可以预先分配，如果 −

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

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

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

应以执行任务的成本主导通信成本和同步成本的方式选择任务。

异步交互可能有助于重叠交互和与主机生成工作相关的计算。

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

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

示例 − 并行分解算法。

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

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

示例 − 并行快速排序