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

划分方法描述 *充分开拓算法的并发性和可扩放性》 *先进行数据分解（称域分解），再进行计算功 能的分解（称功能分解）； *使数据集和计算集互不相交； *划分阶段忽略处理器数目和目标机器的体 系结构； *能分为两类划分： *域分解(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