中国科学技术大学：《并行算法实践》课程教学资源（PPT课件讲稿）上篇 并行程序设计导论 单元I 并行程序设计基础 第三章 并行程序设计简介

中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 第三章并行程序设计简介 3.1并行程序开发方法 311并行层次与代码粒度 312并行程序开发策略 313并行编程模式 314并行应用编程过程 3.2并行程序设计模型 321计算π样本程序 322数据并行模型 ■3.2.3消息传递模型 ■3.24共享变量模型 ■3.3并行编程语言和环境概述 331早期并行编程语言 332近代并行编程语言与环境 333并行说明性语言环境 ■3.4循环程序并行化的一般方法 341数据相关分析 342数据划分与处理器指派 343循环重构 国家高性能计算中心(合肥) 2021/2/1

国家高性能计算中心（合肥） 4 2021/2/1 第三章 并行程序设计简介 ▪ 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 循环重构

中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 并行层次与代码粒度 并行级别 消息 消息 代码粒度 任务级 任务主-1 任务主 任务i+1 粗粒度 func1o func2O funct 控制级 中粒度 数据级 a[1]= [2] b[0] b[1]= b[2]= 细粒度 指令级 甚细粒度 国家高性能计算中心(合肥) 2021/2/1

国家高性能计算中心（合肥） 5 2021/2/1 并行层次与代码粒度 func1() { ... } func2() { ... } func3() { ... } a[0]=... b[0]=... a[1]=... b[1]=... a[2]=... b[2]=... × 并行级别 消息 消息 任务级 控制级 数据级 指令级 代码粒度 粗粒度 中粒度 细粒度 甚细粒度 任务i-1 任务i 任务i+1 + /

中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 并行层次 粒度(指令 数) 并行实施编程支持 几十条,如 甚细粒度指令级并行多指令发射、 内存交又余/硬件处理器 取 几百条,如 细粒度数据级并行循环指令块编译器 共享变量 几千条,如程序员(编共享变量、消 中粒度控制级并行过程、函数译器) 息传递 数万条,如 粗粒度任务级并行独立的作业操作系统消息传递 任务 国家高性能计算中心(合肥) 2021/2/1

国家高性能计算中心（合肥） 6 2021/2/1 并行层次 粒度（指令 数） 并行实施 编程支持 甚细粒度指令级并行 几十条，如 多指令发射、 内存交叉存 取 硬件处理器 细粒度数据级并行 几百条，如 循环指令块 编译器 共享变量 中粒度控制级并行 几千条，如 过程、函数 程序员（编 译器） 共享变量、消 息传递 粗粒度任务级并行 数万条，如 独立的作业 任务 操作系统 消息传递

中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 并行程序开发策略 现有的串 有目的稍许 并行应 行源代码 修改源代码 自动并行化 用程序 (a)自动并行化 现有的串 行源代码 开发并行库 重新链接 并行应 用程序 b)并行库 现有的串 编译器支 并行应 行源代码 作重大修改 持并行化 用程序 (c)重新编写并行代码 国家高性能计算中心(合肥) 2021/2/1

国家高性能计算中心（合肥） 7 2021/2/1 并行程序开发策略 现有的串 行源代码 (a) 自动并行化 (b) 并行库 (c) 重新编写并行代码 有目的稍许 修改源代码 自动并行化 并行应 用程序 现有的串 行源代码 开发并行库 重新链接 并行应 用程序 现有的串 行源代码 作重大修改 编译器支 持并行化 并行应 用程序

中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT DF COMPUTE三巴 ENCE AND ECHNOLDD 并行編程模式 主-从式( Master-S|ave) 单程序多数据流( Single Program Multiple data) 数据流水线( Data Pipelining) 分治策略( Divide and Conquer) 国家高性能计算中心(合肥) 2021/2/1 8

国家高性能计算中心（合肥） 8 2021/2/1 并行编程模式 ▪ 主-从式（Master-Slave） ▪ 单程序多数据流（Single Program Multiple Data ） ▪ 数据流水线（Data Pipelining） ▪ 分治策略（Divide and Conquer）

中图种学学计算机科学与术系 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） ▪ 其基本思想是将一个大而复杂 的问题分解成若干个特性相同 的子问题分而治之。若所得的 子问题规模仍嫌过大，则可反 复使用分治策略，直至很容易 求解诸子问题为止。问题求解 可分为三步：①将输入分解成 若干个规模近于相等的子问题； ②同时递归地求解诸子问题； ③归并各子问题的解成为原问 题的解。 原问题 子问题 分 解 归并 分解 归 并 分解过程 归并过程