PC7--PCAM并行程序设计方法学讲解.ppt

现代密码学理论与实践之五 并 行 计 算 中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月 第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程 第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结 PCAM设计方法学 设计并行算法的四个阶段 划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping) 划分：分解成小的任务，开拓并发性； 通讯：确定诸任务间的数据交换，监测划分的合理性； 组合：依据任务的局部性，组合成更大的任务； 映射：将每个任务分配到处理器上，提高算法的性能。 PCAM设计过程 第七章 并行算法的一般设计过程 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 划分判据 划分方法描述 充分开拓算法的并发性和可扩放性； 先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)； 使数据集和计算集互不相交； 划分阶段忽略处理器数目和目标机器的体系结构； 能分为两类划分： 域分解(domain decomposition) 功能分解(functional decomposition) 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 划分判据 功能分解 划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解； 划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着要重新进行域分解和功能分解； 功能分解是一种更深层次的分解。 功能分解 示例1：搜索树 示例2：气候模型 7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据 划分判据 划分是否具有灵活性？ 划分是否避免了冗余计算和存储？ 划分任务尺寸是否大致相当？ 任务数与问题尺寸是否成比例？ 功能分解是一种更深层次的分解，是否合理？ 第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结 7.3 通讯 7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据 通讯方法描述 通讯是PCAM设计过程的重要阶段； 划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通讯； 功能分解确定了诸任务之间的数据流； 诸任务是并发执行的，通讯则限制了这种并发性； 7.3 通讯 7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据 四种通讯模式 局部/全局通讯 结构化/非结构化通讯 静态/动态通讯 同步/异步通讯 局部通讯 通讯限制在一个邻域内 全局通讯 通讯非局部的 例如： All to All Master-Worker 结构化通讯 每个任务的通讯模式是相同的； 下面是否存在一个相同通讯模式？ 非结构化通讯 没有一个统一的通讯模式 例如：无结构化网格 7.3 通讯 7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据 通讯判据 所有任务是否执行大致相当的通讯? 是否尽可能的局部通讯？ 通讯操作是否能并行执行? 同步任务的计算能否并行执行？ 第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结 7.4