中图种学学计算机科学与术系 University of Science and Technology of China D三 PARTMENT OF C。HPu SCIEN -从 、式 (Master-Slave) ■其基本思想是将一个待求分 主进程 解的任务分成一个主任务任 (主进程)和一些从任务务 子进程1子进程2··子进程-1子进程 (子进程)。主进程负责 将任务的分解、派发和收 集诸子任务的求解结果并 最后汇总得到问题的最终 解。诸子进程接收主进程 发来的消息;并行进行各收 自计算;向主进程发回各结 自的计算结果 国家高性能计算中心(合肥) 2021/2/1
国家高性能计算中心（合肥） 9 2021/2/1 主-从式（Master-Slave） ▪ 其基本思想是将一个待求 解的任务分成一个主任务 （主进程）和一些从任务 （子进程）。主进程负责 将任务的分解、派发和收 集诸子任务的求解结果并 最后汇总得到问题的最终 解。诸子进程接收主进程 发来的消息；并行进行各 自计算；向主进程发回各 自的计算结果。 主进程 子进程1 子进程2 子进程i-1 子进程i 分 配 任 务 收 集 结 果 …
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT DF COMPUTE三巴 ENCE AND ECHNOLDD 单程序多数据流(SPMD) 亦称为单控制流多数据流模式,其基本思想是并行运行 的进程均执行相同的代码段,但却操作在各自不同的数 据上。这种编程模式首先需要将应用程序的教据预先分 配给各个计算进程(处理器);然后诸计算进程并行的 完成各自的计算任务,包括计算过程中各进程间的教据 交换(施行通信同步);最后才将各计算结果汇集起来 分配数据 计算 计算 计算 计算 交换 交换 交换 交换 计算 计算 计算 计算 收集结果 国家高性能计算中心(合肥) 2021/2/1 10
国家高性能计算中心（合肥） 10 2021/2/1 单程序多数据流（SPMD） ▪ 亦称为单控制流多数据流模式，其基本思想是并行运行 的进程均执行相同的代码段，但却操作在各自不同的数 据上。这种编程模式首先需要将应用程序的数据预先分 配给各个计算进程（处理器）；然后诸计算进程并行的 完成各自的计算任务，包括计算过程中各进程间的数据 交换（施行通信同步）；最后才将各计算结果汇集起来。 分配数据 计算 交换 计算 计算 交换 计算 计算 交换 计算 计算 交换 计算 收集结果
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT DF COMPUTE三巴 ENCE AND ECHNOLDD 数据流水线( Data Pipelining) 其基本思想是将各计算进程组织成一条流水线,每个进 程执行一个特定的计算任务,相应于流水线的一个阶段 一个计算任务在功能上划分成一些子任务(进程),这 些子任务完成某种特定功能的计算工作,而且一旦前一 个子任务完成,后继的子任务就可立即开始。在整个计 算过程中各进程之间的通信模式非常简单,仅发生在相 邻的阶段之间,且通信可以完全异步地进行。 输入一-阶段1-阶段2 阶段i 输出 进程1 进程2 进程 国家高性能计算中心(合肥) 2021/2/1
国家高性能计算中心（合肥） 11 2021/2/1 数据流水线（Data Pipelining） ▪ 其基本思想是将各计算进程组织成一条流水线，每个进 程执行一个特定的计算任务，相应于流水线的一个阶段。 一个计算任务在功能上划分成一些子任务（进程），这 些子任务完成某种特定功能的计算工作，而且一旦前一 个子任务完成，后继的子任务就可立即开始。在整个计 算过程中各进程之间的通信模式非常简单，仅发生在相 邻的阶段之间，且通信可以完全异步地进行。 输入 阶段1 阶段2 阶段i 输出 进程1 进程2 进程i …
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD n个流水部件,m次执行 Pn-1 P13 P31 m-1]1 Pn1)2 Pn1 Tn+m-2 P(n-1)m Pn(m-1) Tn+m-1 国家高性能计算中心(合肥) 2021/2/1 12
国家高性能计算中心（合肥） 12 2021/2/1 P1 P2 P3 Pn-1 Pn T1 P1 1 T2 P1 2 P2 1 T3 P1 3 P2 2 P3 1 P(n-1)1 Pn1 Tn Tn-1 P(n-1)2 Tn+m-1 Pnm Pn(m-1) Tn+m-2 P(n-1)m n个流水部件，m次执行
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 分治策略( Divide and Conquer) ■其基本思想是将一个大而复杂 原问题 的问题分解成若干个特性相同 的子问题分而治之。若所得的 子问题规模仍嫌过大,则可反 复使用分治策略,直至很容易分归 求解诪子问題为止。问题求解解井 可分为三步:①将輪入分解成 若千个想近于相子的子问题;O 子问题 ②同时递归地求解诸子问题; ③归并各子问题的解成为原问 分解过程 归并过程 题的解。 国家高性能计算中心(合肥) 2021/2/1 13
国家高性能计算中心（合肥） 13 2021/2/1 分治策略（Divide and Conquer） ▪ 其基本思想是将一个大而复杂 的问题分解成若干个特性相同 的子问题分而治之。若所得的 子问题规模仍嫌过大，则可反 复使用分治策略，直至很容易 求解诸子问题为止。问题求解 可分为三步：①将输入分解成 若干个规模近于相等的子问题； ②同时递归地求解诸子问题； ③归并各子问题的解成为原问 题的解。 原问题 子问题 分 解 归并 分解 归 并 分解过程 归并过程