中科大多核并行计算课件2777575.ppt

H.An Copyright Parallel Programming 多核并行计算Multicore Parallel Computing 主讲人 徐 云 十二、并行程序设计基础 并行程序设计基础 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） 与相并行结合 主进程易成为瓶颈 主-从式（Master-Slave） 其基本思想是将一个待求解的任务分成一个主任务（主进程）和一些从任务（子进程）。主进程负责将任务的分解、派发和收集诸子任务的求解结果并最后汇总得到问题的最终解。诸子进程接收主进程发来的消息；并行进行各自计算；向主进程发回各自的计算结果。 分治并行（Divide and Conquer Parallel） 父进程把负载分割并指派给子进程 递归 重点在于归并 分治设计技术（6.2） 难以负载平衡 分治策略（Divide and Conquer） 其基本思想是将一个大而复杂的问题分解成若干个特性相同的子问题分而治之。若所得的子问题规模仍嫌过大，则可反复使用分治策略，直至很容易求解诸子问题为止。问题求解可分为三步：①将输入分解成若干个规模近于相等的子问题；②同时递归地求解诸子问题；③归并各子问题的解成为原问题的解。 流水线并行（Pipeline Parallel） 一组进程 流水线作业 流水线设计技术 数据流水线（Data Pipelining） 其基本思想是将各计算进程组织成一条流水线，每个进程执行一个特定的计算任务，相应于流水线的一个阶段。一个计算任务在功能上划分成一些子任务（进程），这些子任务完成某种特定功能的计算工作，而且一旦前一个子任务完成，后继的子任务就可立即开始。在整个计算过程中各进程之间的通信模式非常简单，仅发生在相邻的阶段之间，且通信可以完全异步地进行。 工作池并行（Work Pool Parallel） 初始状态：一件工作 进程从池中取任务执行 可产生新任务放回池中 直至任务池为空 易与负载平衡 临界区问题（尤其消息传递） 并行程序设计基础 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） 概况： 程序员用熟悉的串行语言编程 编译器或运行支持系统自动转化为并行代码 特点： 语义简单 可移植性好 单线程，易于调试和验证正确性 效率很低 π的计算 计算π的串行C代码 #define N 1000000 main() { double local, pi = 0.0,