《并行计算：Parallel Computing》 结构编程算法应用 §3.1并行程序设计基础与样例 (第一部分) 徐悦牲Yueshen Xu) ysxu@xidian.edu.cn 软件工程系 西安电子科技大学
§3.1 并行程序设计基础与样例 （第一部分） 徐悦甡(Yueshen Xu) ysxu@xidian.edu.cn 软件工程系 西安电子科技大学 《并行计算：Parallel Computing》 结构 编程 算法 应用
上节回顾 历些毛子代枚大多 XIDIAN UNIVERSITY →并行计算机性能测评 ▣Amdahl定律 S= Ws+Wp f+(1-f) p Ws Wp/p f+1-T 1+f0-可1+fx0-画 Amdahl's Law 20 18 Parallel portion 16 50% 75% 0% 95 12 10 9州名目晟月百是量眉昌胃圆 Number of processors
上节回顾 并行计算机性能测评 Amdahl 定律 𝑆 = 𝑊𝑠 + 𝑊𝑝 𝑊𝑠 + 𝑊𝑝Τ𝑝 = 𝑓 + (1 − 𝑓ሻ 𝑓 + 1 − 𝑓 𝑝 = 𝑝 1 + 𝑓(𝑝 − 1ሻ = 1 1 + 𝑓 × (𝑝 − 1ሻ 𝑝
上节回顾 历些毛子代枝大等 XIDIAN UNIVERSITY →并行计算机性能测评 口等效率度量标准 >T。：有效计算时间（即串行算法时间） >Tp：并行计算时间 p-1 Te te >Te+T=p×Tp >卫：处理器个数 p-1 >E:效率 To to Te Te S= p Te+To T b 1+e 0 1+W >如果问题规模W保持不变 >处理器数p增加，开销T,增大 1 E= >效率E下降 1+T
上节回顾 并行计算机性能测评 等效率度量标准 𝑇𝑒 = 𝑖=0 𝑝−1 𝑡𝑒 𝑖 𝑇𝑜 = 𝑖=0 𝑝−1 𝑡𝑜 𝑖 ➢ 𝑇𝑒 ：有效计算时间（即串行算法时间） ➢ 𝑇𝑝 ：并行计算时间 ➢ 𝑇𝑒 + 𝑇𝑜 = 𝑝 × 𝑇𝑝 ➢ 𝑝: 处理器个数 ➢ 𝐸：效率 𝑆 = 𝑇𝑒 𝑇𝑝 𝐸 = 𝑆 𝑝 = 𝑇𝑒 𝑇𝑒 + 𝑇𝑜 𝑝 = 𝑝 1 + 𝑇𝑜 𝑇𝑒 = 𝑝 1 + 𝑇𝑜 𝑊 = 1 1 + 𝑇𝑜 𝑇𝑒 = 1 1 + 𝑇𝑜 𝑊 ➢ 如果问题规模𝑊保持不变 ➢ 处理器数𝑝增加，开销𝑇𝑜增大 ➢ 效率𝐸下降
本节提纲 历忠毛子代枚大” XIDIAN UNIVERSITY ▣并行程序设计语言构造与分类 ■并行程序样例与引入 从编程语言的角度 ■并行语言的构造方法 ■并行语言的分类 ▣并行程序设计通信与编程规范 ■并行程序设计的一般性问题 >并行性问题 从编程范式的角度 >进程间的交互问题 ■并行程序设计的编程规范 ■计算圆周率程序样本 4
本节提纲 并行程序设计语言构造与分类 并行程序样例与引入 并行语言的构造方法 并行语言的分类 从编程范式的角度 从编程语言的角度 并行程序设计通信与编程规范 并行程序设计的一般性问题 ➢ 并行性问题 ➢ 进程间的交互问题 并行程序设计的编程规范 计算圆周率程序样本 4
并行程序样例与引入 历粤毛子种拔大学 XIDIAN UNIVERSITY ▣找出最大值 ■思考：一般的串行程序应该怎么写 ■程序≈≈语言+数据结构+算法 载体 逻辑 并行程序设计部分 所涉及的内容
并行程序样例与引入 找出最大值 思考：一般的串行程序应该怎么写 程序 ≈≈ 语言 + 数据结构 + 算法 载体 工具 逻辑 并行程序设计部分 所涉及的内容 5
并行程序设计样例 历些毛子代枚大多 XIDIAN UNIVERSITY 》 求最大数（一） CPU O CPU 1 CPU 2 CPU 3 6
并行程序设计样例 求最大数（一） CPU 0 CPU 1 CPU 2 CPU 3 6
并行程序设计样例 历粤毛子种技大兽 XIDIAN UNIVERSITY 求最大数（二） CPUO CPU 1 CPU 2 CPU 3
并行程序设计样例 求最大数（二） CPU 0 CPU 1 CPU 2 CPU 3 7
并行程序设计样例 历些荒子代枝大多 XIDIAN UNIVERSITY 求最大数（三） CPU O CPU 1 CPU 2 CPU 3 8
并行程序设计样例 求最大数（三） CPU 0 CPU 1 CPU 2 CPU 3 8
并行程序设计样例 历粤毛子种技大》 XIDIAN UNIVERSITY 》求最大数（四） CPUO CPU 1 CPU 2 CPU 3 9
并行程序设计样例 求最大数（四） CPU 0 CPU 1 CPU 2 CPU 3 9
并行程序设计样例 历些毫子种拔大势 XIDIAN UNIVERSITY 求最大数（五） CPU O CPU 1 CPU 2 CPU 3 10
并行程序设计样例 求最大数（五） CPU 0 CPU 1 CPU 2 CPU 3 10