并行算法 - 模型

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

数据并行

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

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

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

示例 - 密集矩阵乘法。

在任务图模型中，并行性由任务图表示。任务图可以是平凡的或非平凡的。在这个模型中，利用任务之间的相关性来促进局部性或最小化交互成本。此模型用于解决与任务关联的数据量与关联的计算量相比非常大的问题。分配任务有助于改善任务之间数据移动的成本。

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

在此，问题被划分为原子任务并实现为一个图。每个任务都是一个独立的作业单元，它依赖于一个或多个先前的任务。在完成任务后，先前任务的输出将传递给依赖任务。只有当它的所有先前任务都完成后，具有先前任务的任务才会开始执行。当最后一个依赖任务完成时（上图中的任务 6），将收到图的最终输出。

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

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

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

示例 - 并行树搜索

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

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

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

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

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

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

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

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

示例 - 并行 LU 分解算法。

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

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

示例 - 并行快速排序

打印页面