中科大并行程序设计课件第二章.pptVIP

现代密码学理论与实践之五 并行算法实践 上篇 并行程序设计导论 并行算法实践上篇 并行程序设计导论 单元I 并行程序设计基础 单元II 并行程序编程指南 单元III 并行程序开发方法 单元I 并行程序设计基础 第一章 并行计算机系统与结构模型 第二章 PC机群的搭建 第三章 并行程序设计简介 第三章 并行程序设计简介 3.1 并行程序开发方法 3.1.1 并行层次与代码粒度 3.1.2 并行程序开发策略 3.1.3 并行编程模式 3.1.4 并行应用编程过程 3.2 并行程序设计模型 3.2.1 计算π样本程序 3.2.2 数据并行模型 3.2.3 消息传递模型 3.2.4 共享变量模型 3.3 并行编程语言和环境概述 3.3.1 早期并行编程语言 3.3.2 近代并行编程语言与环境 3.3.3 并行说明性语言环境 3.4 循环程序并行化的一般方法 3.4.1 数据相关分析 3.4.2 .数据划分与处理器指派 3.4.3 循环重构 并行层次与代码粒度 并行程序开发策略 并行编程模式 主-从式（Master-Slave） 单程序多数据流（Single Program Multiple Data ） 数据流水线（Data Pipelining） 分治策略（Divide and Conquer） 主-从式（Master-Slave） 其基本思想是将一个待求解的任务分成一个主任务（主进程）和一些从任务（子进程）。主进程负责将任务的分解、派发和收集诸子任务的求解结果并最后汇总得到问题的最终解。诸子进程接收主进程发来的消息；并行进行各自计算；向主进程发回各自的计算结果。 单程序多数据流（SPMD） 亦称为单控制流多数据流模式，其基本思想是并行运行的进程均执行相同的代码段，但却操作在各自不同的数据上。这种编程模式首先需要将应用程序的数据预先分配给各个计算进程（处理器）；然后诸计算进程并行的完成各自的计算任务，包括计算过程中各进程间的数据交换（施行通信同步）；最后才将各计算结果汇集起来。 数据流水线（Data Pipelining） 其基本思想是将各计算进程组织成一条流水线，每个进程执行一个特定的计算任务，相应于流水线的一个阶段。一个计算任务在功能上划分成一些子任务（进程），这些子任务完成某种特定功能的计算工作，而且一旦前一个子任务完成，后继的子任务就可立即开始。在整个计算过程中各进程之间的通信模式非常简单，仅发生在相邻的阶段之间，且通信可以完全异步地进行。 分治策略（Divide and Conquer） 其基本思想是将一个大而复杂的问题分解成若干个特性相同的子问题分而治之。若所得的子问题规模仍嫌过大，则可反复使用分治策略，直至很容易求解诸子问题为止。问题求解可分为三步：①将输入分解成若干个规模近于相等的子问题；②同时递归地求解诸子问题；③归并各子问题的解成为原问题的解。 并行应用编程过程－PCAM 设计并行应用的四个阶段 划分(Partitioning) 通信(Communication) 组合(Agglomeration) 映射(Mapping) 划分：分解成小的任务，开拓并发性； 通信：确定诸任务间的数据交换，监测划分的合理性； 组合：依据任务的局部性，组合成更大的任务； 映射：将每个任务分配到处理器上，提高并行性能。 PCAM设计过程 划分方法描述 充分开拓算法的并发性和可扩放性； 先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)； 使数据集和计算集互不相交； 划分阶段忽略处理器数目和目标机器的体系结构； 能分为两类划分： 域分解(Domain Decomposition) 功能分解(Functional Decomposition) 域分解 划分的对象是数据，可以是程序中的输入数据、中间处理数据和输出数据； 将数据分解成大致相等的小数据片； 划分时考虑数据上的相应操作； 如果一个任务需要别的任务中的数据，则会产生任务间的通信； 域分解 示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法： 域分解 不规则区域的分解示例： 功能分解 划分的对象是计算（亦称为任务分解或计算划分），将计算划分为不同的任务，其出发点不同于域分解； 划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着存在大量的通信开销，要重新进行域分解和功能分解； 功能分解是一种更深层次的分解。 功能分解 示例1：有哪些信誉好的足球投注网站树 示例2：气候模型 划分判据 划分是否具有灵活性？ 划分是否避免了冗余计算和存储？ 划分任务尺寸是否大致相当？ 任务数与问题尺寸是否成比例？ 功能分解是一种更深层次的分解，是否合理？ 通信分析 通信是PCAM设计过程的重要阶段