十二、并行程序设计基础.ppt

H.An Copyright Parallel Programming 十二、并行程序设计基础 并行程序设计基础 12.1 并行程序设计概述 12.2 进程 12.3 线程 12.4 同步 12.5 通信 12.6 并行程序设计模型 并行程序设计概述 并行程序设计难的原因 并行语言的构造方法 并行性问题 交互/通信问题 五种并行编程风范 计算圆周率的样本程序 相并行（Phase Parallel） 分治并行（Divide and Conquer Parallel） 流水线并行（Pipeline Parallel） 主从并行（Master-Slave Parallel） 工作池并行（Work Pool Parallel） 相并行（Phase Parallel） 一组超级步（相） 步内各自计算 步间通信、同步 BSP（4.2.3） 方便差错和性能分析 计算和通信不能重叠 主－从并行（Master-Slave Parallel） 主进程：串行、协调任务 子进程：计算子任务 划分设计技术（ 6.1） 与相并行结合 主进程易成为瓶颈 分治并行（Divide and Conquer Parallel） 父进程把负载分割并指派给子进程 递归 重点在于归并 分治设计技术（6.2） 难以负载平衡 流水线并行（Pipeline Parallel） 一组进程 流水线作业 流水线设计技术（6.5） 工作池并行（Work Pool Parallel） 初始状态：一件工作 进程从池中取任务执行 可产生新任务放回池中 直至任务池为空 易与负载平衡 临界区问题（尤其消息传递） 计算圆周率的c语言代码段 #define N 1000000 main() { double local, pi = 0.0, w; long i; w=1.0/N; for (i = 0; iN; i ++) { local = (i + 0.5)*w; pi = pi + 4.0/(1.0+local * local); } printf(“pi is %f \n”, pi *w); } 并行程序设计基础 12.1 并行程序设计概述 12.2 进程 12.3 线程 12.4 同步 12.5 通信 12.6 并行程序设计模型 进程 进程的基本概念 进程的并行执行 进程的相互作用 并行程序设计基础 12.1 并行程序设计概述 12.2 进程 12.3 线程 12.4 同步 12.5 通信 12.6 并行程序设计模型 线程 线程的基本概念 线程的管理 线程的同步 并行程序设计基础 12.1 并行程序设计概述 12.2 进程 12.3 线程 12.4 同步 12.5 通信 12.6 并行程序设计模型 同步 原子和互斥 高级同步结构 低级同步原语 并行程序设计基础 12.1 并行程序设计概述 12.2 进程 12.3 线程 12.4 同步 12.5 通信 12.6 并行程序设计模型 通信 影响通信系统性能的因素 低级通信支持 TCP/IP通信协议组简介 并行程序设计基础 12.1 并行程序设计概述 12.2 进程 12.3 线程 12.4 同步 12.5 通信 12.6 并行程序设计模型 并行程序设计模型 隐式并行模型 数据并行模型 消息传递模型 共享变量模型 并行程序设计模型 隐式并行（Implicit Parallel） 数据并行（Data Parallel） 共享变量（Shared Variable） 消息传递（Message Passing） 隐式并行（Implicit Parallel） 概况： 程序员用熟悉的串行语言编程 编译器或运行支持系统自动转化为并行代码 特点： 语义简单 可移植性好 单线程，易于调试和验证正确性 效率很低 数据并行（Data Parallel） 概况： SIMD的自然模型 局部计算和数据选路操作 特点： 单线程 并行操作于聚合数据结构（数组） 松散同步 单一地址空间 隐式交互作用 显式数据分布 共享变量（Shared Variable） 概况： PVP, SMP, DSM的自然模型 特点： 多线程：SPMD, MPMD 异步 单一地址空间 显式同步 隐式数据分布 隐式通信 消息传递（Message Passing） 概况： MPP, COW的自然模型 特点： 多线程 异步 多地址空间 显式同步 显式数据映射和负载分配 显式通信 国家高性能计算中心（合肥） 1 并行程序设计难的原因 技术先行,缺乏理论指导 程序的语法/语义复杂, 需要用户自已处理 任务/数据的划分/分配 数据交换 同步和互斥 性能平衡 并行语言缺乏代可扩展和异构可扩展, 程序移植困难, 重写代码难度太大 环境和工具缺乏较长的