并行设计模式全解析

### 并行设计模式全解析 #### 1. 并行元模式概述 在并行编程中，有一些关键的元模式起着重要作用，下面为你详细介绍： - **共享队列（Shared Queue）**：该元模式创建的队列数据类型，允许队列被并发访问。共享队列用于支持不同上下文中并发活动的交互，从线程到进程，再到运行在 CPU 协处理器上的并发活动。例如在主/从（Master/Worker）元模式中，就会使用共享队列来为工作进程分配任务。 - **分布式数组（Distributed Array）**：此元模式对并行程序中与数组管理相关的各个方面进行建模，这些数组会被划分并分布到不同的并发活动中。分布式数组常用于实现逻辑上由并发活动共享的数据结构，但可以以某种方式进行划分，使得每个并发活动拥有并管理分布式数组的一部分。其挑战在于组织数组，使每个执行单元（UE）所需的元素在计算的合适时间处于附近，即数组的分布要与计算流程相匹配。该元模式对于使用几何分解元模式的程序特别有用，有助于算法构建，并在使用单程序多数据（SPMD）元模式时组织程序结构。 不同的元模式在支持算法结构设计空间中不同模式的实现方面具有不同的适用性。例如，任务并行性由程序结构组中的四个元模式很好地支持，而递归数据模式仅由 SPMD 和主/从模式部分支持。 #### 2. 实现机制设计空间 与并行应用程序实现相关的第二个（也是最低级别的）设计空间是实现机制设计空间，其中包含代表支持并行编程典型并行计算抽象所需的基本机制的元模式，主要包括： - **并发活动（Concurrent activities）** - **同步（Synchronization）** - **通信（Communication）** 这个设计空间只有三个与上述抽象对应的不同元模式： |元模式|说明| | ---- | ---- | |UE 管理（UE Management）|与执行单元（进程、线程）的管理相关，处理并行应用程序中并发活动的各个方面，包括它们的创建、销毁和管理。虽然通常只考虑线程和进程，但该元模式也可适应处理放置在 CPU 协处理器（如 GPU 内核）上的并发活动。| |同步（Synchronization）|处理与执行并行应用程序的 UE 中事件/计算排序相关的所有方面，涉及并发活动和内存的同步，涵盖锁/栅栏机制、更高级别的互斥构造（如监视器）和集体同步（如屏障）等方面。| |通信（Communication）|管理实现并行应用程序的不同 UE 之间发生的通信的所有方面，处理并发活动之间的数据交换，包括不同类型的点对点消息传递（如发送和接收、同步和异步）以及多点或集体通信（如广播、散射、收集、归约），其中多个 UE 参与单个通信事件。| #### 3. 常见并行模式 ##### 3.1 易并行问题（Embarrassingly Parallel） 这并非真正的模式，而是一类问题。在某些问题中，将工作划分为独立任务非常明显和简单，这类问题被称为易并行问题或令人愉悦的并行问题。 例如： - 第 12 章中用于计算 π 的梯形法则程序，可以并行计算任意数量梯形的面积。 - 使用循环通过乘法或加法累积值的程序。 - 密码破解程序。 - 计算机图形图像渲染。 - 计算曼德布洛特集的点。 - 面部识别系统。 - 许多计算机模拟，如气候模型。 易并行问题还可能取决于输入数据的类型和大小。例如，有几百万个 TIFF 文件要转换为 GIF 文件，可以将 M/P 个 TIFF 文件（M 是文件总数，P 是处理元素的数量）分配给每个处理元素进行转换；或者有一整个文本文件目录，要计算整个目录中的单词频率，可以将文档划分到所有处理元素上，在每个子集上进行计数，然后合并所有子集。 ##### 3.2 主/从模式（Master/Worker） 在该模式中，一个主任务会设置多个并发的工作线程或进程以及一个任务包。每个工作进程从任务包中取出一个任务并并行执行，完成后会继续从任务包中取出任务执行，直到任务包为空或满足其他结束条件。任务包通常实现为共享队列。主/从模式对于易并行程序特别有用，因为大量的工作任务之间没有依赖关系。 其流程如下： ```mermaid graph LR A[Master] --> B[创建 Worker 线程/进程] A --> C[创建任务包（共享队列）] B --> D[从任务包取任务] D --> E[执行任务] E --> F{任务包是否为空} F -- 否 --> D F -- 是 --> G[结束] ``` ##### 3.3 映射和归约模式（Map and Reduce） - **映射模式（Map）**：可能是最容易遇到的模式。与主/从模式一样，映射和归约模式非常适合易并行问题。映射模式将程序的一部分（可称为函数）并行应用于数据的每个元素。这些函数必须没有副作用，并且相同且独立。由于这种独立性，映射模式可以利用尽可能多的执行单元。 - **归约模式（Reduce）**：与映射模式结合使用时，归约模式将部分解决方案集合中的所有元素两两组合，创建一个汇总值作为最终解决方案。虽然部分解决方案的组合不需要满足交换律，但大多数归约应用都假设满足交换律和结合律。 在 OpenMP 中，`#pragma omp parallel for` 编译器指令会为易并行程序中的 for 循环启动映射操作。添加 `reduction(+: <var-list>)` 到编译器指令将添加归约组件。例如，在梯形法则程序中： ```c #pragma omp parallel for private(x) reduction(+:sum) /* loop to compute the area under f(x) */ for (int i = 0; i <= steps; i++) { x = i * width; sum = sum + f(x); } ``` 映射和归约模式也可以单独使用。 ##### 3.4 映射归约模式（MapReduce） 该模式结合了映射和归约模式来完成常见任务。它旨在解决输入、处理和生成大型数据集的问题，并且其实现可以在多个处理器上进行扩展。MapReduce 的实现执行三个基本功能： - **映射（Mapping）**：程序将大型数据集（或大量文件）划分为 N 个离散且独立的子集，每个子集将在单个处理器上进行处理。输出通常是某种映射数据结构，包含不一定唯一的（键，值）对列表。 - **洗牌（Shuffle）**：程序提取相似的（键，值）对，并将它们分配到进行归约操作的新处理器上。 - **归约（Reduce）**：将输入数据集中的元素合并为一个输出结果。每个处理器的结果列表构成生成的输出数据集。 以计算文本文件目录中单词频率为例，其伪代码如下： ```python def map(docID_key, input_value): # docID_key 是文档的名称 # input_value 是文档的内容 myMap = {} for word in input_value.split(): if word in myMap: myMap[word] = myMap[word] + 1 else: myMap[word] = 1 return myMap # 洗牌操作 # 输入是所有包含 (word, frequency) 对的 myMap 输出文件 # 输出是中间键（单词）和该单词在所有文件中的频率计数列表 def reduce(intermediate_key, value_list): # intermediate_key 是文档中的一个单词 # value_list 是该单词的计数列表 result = 0 for value in value_list: result += value return result ``` MapReduce 非常常见，为此创建了一个名为