《并行计算：Parallel Computing》 结构编程算法应用 §3.1并行程序设计基础与样例 (第二部分) 徐悦牲Yueshen Xu) ysxu@xidian.edu.cn 软件工程系 西安电子科技大学
§3.1 并行程序设计基础与样例 （第二部分） 徐悦甡(Yueshen Xu) ysxu@xidian.edu.cn 软件工程系 西安电子科技大学 《并行计算：Parallel Computing》 结构 编程 算法 应用
上节回顾 面些毛子种枝大兽 XIDIAN UNIVERSITY →并行程序设计基础与样例 口并行程序设计样例 ■小 求最大数 CPUO CPU 1 CPU 2 CPU 3 2
上节回顾 并行程序设计基础与样例 CPU 0 CPU 1 CPU 2 CPU 3 2 并行程序设计样例 求最大数
上节回顾 历些毛子种枝大” XIDIAN UNIVERSITY →并行程序设计基础与样例 ▣串行语言→并行语言→并行程序设计 ■并行程序设计中需要解决的一般性问题 >并行性问题 -针对一个程序/进程，如何实现并行化 >交互性问题 -不同的程序/进程，在并行执行过程中，如何交互
上节回顾 并行程序设计基础与样例 串行语言 并行语言 并行程序设计 并行程序设计中需要解决的一般性问题 ➢ 并行性问题 - 针对一个程序/进程，如何实现并行化 ➢ 交互性问题 - 不同的程序/进程，在并行执行过程中，如何交互 3
上节回顾 历些荒子种枚大多 XIDIAN UNIVERSITY →并行程序设计基础与样例 ▣开发动态并行性的一般方法 ■Fork/Join Process A Process B Process C begin begin begin Z:=1 fork(C); Y:=foo(Z); fork(B); X:=foo(Z); join(C); end T:=foo(3); output(X+Y); end end Fork:派生一个子进程 Join:强制父进程等待子进程
上节回顾 并行程序设计基础与样例 开发动态并行性的一般方法 Fork/Join begin Z:=1 fork(B); T:=foo(3); end begin fork(C); X:=foo(Z); join(C); output(X+Y); end begin Y:=foo(Z); end Fork：派生一个子进程 Join：强制父进程等待子进程 Process A Process B Process C 4
本节目录 历粤毛子种枝大兽 XIDIAN UNIVERSITY ▣并行性问题（续） ■进程编组、划分与分配 并行性问题的延续 ■并行性与并行粒度 ▣进程间的交互问题 ■3 交互的类型 交互问题 ■交互的模式 ▣并行程序设计模型 如何写程序 ■ 以计算圆周率程序为例
本节目录 并行性问题（续） 进程编组、划分与分配 并行性与并行粒度 进程间的交互问题 交互的类型 交互的模式 并行程序设计模型 以计算圆周率程序为例 5 交互问题 并行性问题的延续 如何写程序
并行程序设计的一般性问题 历些毛子科枚大多 XIDIAN UNIVERSITY )并行性问题 口进程编组、划分与分配 ■进程编组 >目的：支持进程间的交互，常把需要交互的进程调度在同一组中 >一个进程组成员由：组标识符+成员序号唯一确定 ■划分与分配 >原侧：使系统大部分时间忙于计算，而不是闲置或忙于交互 >划分：切割数据和工作负载 >分配：将划分好的数据和工作负载映射到计算结点/处理器上 多机 多核 决定并行性与并行粒度 6
划分与分配 ➢ 原则: 使系统大部分时间忙于计算，而不是闲置或忙于交互 ➢ 划分: 切割数据和工作负载 ➢ 分配: 将划分好的数据和工作负载映射到计算结点/处理器上 并行程序设计的一般性问题 并行性问题 进程编组、划分与分配 进程编组 ➢ 目的:支持进程间的交互,常把需要交互的进程调度在同一组中 ➢ 一个进程组成员由：组标识符+成员序号 唯一确定 多机 多核 决定并行性与并行粒度 6
并行程序设计的一般性问题 历粤毛子种拔大学 XIDIAN UNIVERSITY )并行性问题 ■分配方式 >显式分配：由用户指定数据和负载如何加载 >隐式分配：由编译器和运行时支持系统决定 ■分配原则 >就近分配原则：进程所需的数据靠近使用它的进程代码 口并行性与并行粒度 ■并行性或并行度(Degree of Parallelism,DOP) >同时执行的分进程数
并行程序设计的一般性问题 并行性问题 分配方式 ➢ 显式分配: 由用户指定数据和负载如何加载 ➢ 隐式分配：由编译器和运行时支持系统决定 分配原则 ➢ 就近分配原则：进程所需的数据靠近使用它的进程代码 7 并行性与并行粒度 并行性或并行度(Degree of Parallelism, DOP) ➢ 同时执行的分进程数
并行程序设计的一般性问题 历些毛子科枚大多 XIDIAN UNIVERSITY )并行性问题 ■ 并行粒度(Granularity) >两次并行或交互操作之间所执行的计算负载 指令级并行 小粒度 块级并行 中粒度 进程级并行 任务级并行 大粒度 ■ 并行度与并行粒度常为负相关关系 >增大粒度会减小并行度 >一味增加并行度会增加系统开销（主要体现在进程同步开销上） 8
并行粒度(Granularity) ➢ 两次并行或交互操作之间所执行的计算负载 指令级并行 块级并行 进程级并行 任务级并行 并行程序设计的一般性问题 并行性问题 小粒度 中粒度 大粒度 并行度与并行粒度常为负相关关系 ➢ 增大粒度会减小并行度 ➢ 一味增加并行度会增加系统开销（主要体现在进程同步开销上） 8
并行程序设计的一般性问题 历粤毛子种技大” XIDIAN UNIVERSITY )并行性问题 口并行粒度 Java/Python Task i-l Task i Task i+1 任务级并行，程序 编程语言 func1 ( func2 ( func: Process/Threads 进程级并行 线程 Compilers 88▣ a(1)=. b(1)=. 块级并行 (编译器) CPU Load 指令级并行 9
并行程序设计的一般性问题 并行性问题 9 Java/Python Task i-l Task i Task i+1 编程语言 任务级并行，程序 func1 ( ) { .... .... } func2 ( ) { .... .... } func3 ( ) { .... .... } Process/Threads 线程 进程级并行 a ( 0 ) =.. b ( 0 ) =.. a ( 1 )=.. b ( 1 )=.. a ( 2 )=.. b ( 2 )=.. Compilers （编译器） 块级并行 CPU + x Load 指令级并行 并行粒度
并行程序设计的一般性问题 历些毛子代枚大多 XIDIAN UNIVERSITY )进程间的交互问题 ▣进程间的交互问题 ■交互：进程间的相互影响 ■ 交互的类型 >通信（类型一）：两个或多个进程间传送数的操作 并行计算 >通信方式 的有效实 共享变量 现亦依赖 于操作系 ·参数传递（父进程传给子进程方式） 统的知识 ·消息传递 10
并行程序设计的一般性问题 进程间的交互问题 进程间的交互问题 交互：进程间的相互影响 交互的类型 并行计算 的有效实 现亦依赖 于操作系 统的知识 ➢ 通信(类型一): 两个或多个进程间传送数的操作 ➢ 通信方式 - 共享变量 - 参数传递(父进程传给子进程方式) - 消息传递 10