南京大学：《并行处理技术——分布式与并行计算 Distributed and Parallel computing（并行计算——结构、算法、编程）》课程教学资源（课件讲稿）第七章 并行算法的一般设计过程

第七章并行算法的一般设计过程 7.1PCAM设计方法学 7.2划分 73通讯 7.4组合 7.5映射 L生

第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结

PCAM设计方法学 *设计并行算法的四个阶段 *划分(Partitioning) *通讯(Communication) *组合(Agglomeration) *映射(Mapping) *划分：分解成小的任务，开拓并发性； *通讯：确定诸任务间的数据交换，监测划分的合理性； *组合：依据任务的局部性，组合成更大的任务； *映射：将每个任务分配到处理器上，提高算法的性能。 2011/11/1

 设计并行算法的四个阶段  划分(Partitioning)  通讯(Communication)  组合(Agglomeration)  映射(Mapping)  划分：分解成小的任务，开拓并发性；  通讯：确定诸任务间的数据交换，监测划分的合理性；  组合：依据任务的局部性，组合成更大的任务；  映射：将每个任务分配到处理器上，提高算法的性能。 4 2011/11/1 PCAM设计方法学

PCAM设计过程 问题 划分 通信 组合 映射 d 5 2011/11/1

问题 划分 映射 组合 通信 5 2011/11/1 PCAM设计过程

第七章并行算法的一般设计过程 7.1PCAM设计方法学 7.2划分 7.3通讯 7.4组合 7.5映射

第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结

7.2划分 7.2.1方法描述 7.2.2域分解 7.2.3功能分解 7.2.4划分判据

7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据

划分方法描述 *充分开拓算法的并发性和可扩放性》 *先进行数据分解（称域分解），再进行计算功 能的分解（称功能分解）； *使数据集和计算集互不相交； *划分阶段忽略处理器数目和目标机器的体 系结构； *能分为两类划分： *域分解(domain decomposition) *功能分解(functional decomposition) 8 2011/11/1

 充分开拓算法的并发性和可扩放性；  先进行数据分解(称域分解)，再进行计算功 能的分解(称功能分解)；  使数据集和计算集互不相交；  划分阶段忽略处理器数目和目标机器的体 系结构；  能分为两类划分：  域分解(domain decomposition)  功能分解(functional decomposition) 8 2011/11/1 划分方法描述

7.2划分 7.2.1方法描述 7.2.2域分解 7.2.3功能分解 7.2.4划分判据

7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据

域分解 *划分的对象是数据，可以是算法的输入数 据、中间处理数据和输出数据， *将数据分解成大致相等的小数据片； *划分时考虑数据上的相应操作； *如果一个任务需要别的任务中的数据，则 会产生任务间的通讯； 10 2011/11/1

 划分的对象是数据，可以是算法的输入数 据、中间处理数据和输出数据；  将数据分解成大致相等的小数据片；  划分时考虑数据上的相应操作；  如果一个任务需要别的任务中的数据，则 会产生任务间的通讯； 10 2011/11/1 域分解

域分解 *示例：三维网格的域分解，各格点上计算 都是重复的。下图是三种分解方法： 1-D 2-D 3-D 图7.2 2011/11/1 11

域分解  示例：三维网格的域分解，各格点上计算 都是重复的。下图是三种分解方法： 图7.2 1 D ‐ 2 D ‐ 3 D ‐ 11 2011/11/1

域分解 *不规则区域的分解示例： 2011/11/1 12

域分解  不规则区域的分解示例： 12 2011/11/1