《并行计算基础》由会员分享，可在线阅读，更多相关《并行计算基础（47页珍藏版）》请在金锄头文库上搜索。
1、多核软件开发技术第二讲：并行计算基础 北京大学 二零零八年春季*致谢：感谢Intel对本课程项目的资助本讲主要内容 并行计算机体系结构 并行计算模型 进程 线程 并行编程环境 编程语言与编译器 并行计算性能评测 常用并行数值算法 并行编译器 并行计算机体系结构组成并行计算机的各个部分为： 节点（node）： 每个节点由多个处理器构成，可以直接输入输出 互联网络（interconnect network）： 所有节点通过互联网络相互连接通信。 内存 （memory）： 内存由多个存储模块组成，这些模块或者与节点 对称地分布在互联网络的两侧，或者位于各个节 点的内部并行计算机体系结构示意图，内存模
2、块与节点分离并行计算机体系结构示意图，内存模块位于节点内部 多级存储体系结构 微处理器的峰值运算速度每18个月翻一番 内存模块的容量每年几乎翻一番 内存模块的访问速度却没有得到平衡发展 内存的访问速度要比处理器执行速度慢很多 内存墙性能瓶颈=多级存储结构 多级存储体系结构 并行计算机访存模型UMA（Uniform Memory Access）模型 内存模块与节点分离，分别位于互联网络两侧 物理存储器被所有节点共享 所有节点访问任意存储单元的时间相同 发生访存竞争时，仲裁策略平等对待每个节点 各节点的CPU可带有局部私有高速缓存 外围I/O设备也可以共享，且每个节点有平等的 访问权利 并行计算机
3、访存模型NUMA（Non-Uniform Memory Access）模型 内存模块分布在各个节点内部 物理存储器被所有节点共享，任意节点可以直接访 问任意内存模块 节点访问内存模块的速度不同 发生访存竞争时，仲裁策略对节点可能是不等价的 各节点的CPU可带有局部私有高速缓存 外围I/O设备也可以共享，但对各节点是不等价的 并行计算机访存模型COMA（Cache-Only Memory Access）模型 各处理器节点中没有存储层次结构 利用分布的高速缓存目录进行远程高速缓存 的访问 COMA中的高速缓存容量一般都大于2级高速 缓存容量 数据开始时可以任意分配 ，在运行时它最终 会被迁移到要用
4、到它的地方 并行计算机访存模型NORMA（No-Remote Memory Access）模型 所有存储器都是私有的 绝大多数NORMA都不支持远程存储器访问 并行计算机系统的不同访存模型分类 并行计算模型 SIMD同步并行计算模型 SIMD共享存储模型 ；并行随机存取机器 假定存在着一个容量无限大的共享存储器 有有限或无限个功能相同的处理器 均具有简单的算术运算和逻辑判断功能 在任何时刻各处理器均可通过共享存储单元 相互交换数据 SIMD同步并行计算模型SIMD分布存储模型 ，常见模型有： 采用一维线性连接的SIMD模型 采用网孔连接的SIMD模型 采用树形连接的SIMD模型 采用树网连接的
5、SIMD模型 采用立方连接的SIMD模型 采用立方环连接的SIMD模型 采用洗牌交换连接的SIMD模型 采用多级互联网络连接的SIMD模型 MIMD异步并行计算模型 异步PRAM模型 每个处理器都有其本地存储器、局部时钟和 局部程序 处理器间的通信经过共享全局存储器 无全局时钟，各处理器异步地独立执行各自 的指令 处理器任何时间依赖关系需明确地在各处理 器的程序中加入同步（路）障 一条指令可在非确定但有限的时间内完成 MIMD异步并行计算模型BSP模型 计算由一系列用全局同步分开的周期为L的超 级步（superstep）组成 在各超级步中: 每个处理器均执行局部计算 通过路由器接受和发送消息
6、然后做一全局检查，以确定该超级步是否已由所 有的处理器完成 若是，则前进到下一超级步 否则下一L周期被分配给未曾完成的超级步 MIMD异步并行计算模型LogP模型 一种分布存储的、点到点通信的多处理机模型 其中通信网络由一组参数来描述: L （Latency）表示消息从源到目的在网络上的延迟 o （overhead）表示处理器发送或接受一条消息消耗 在网络协议栈中的开销 g （Gap）表示处理器可连续进行消息发送或接受的 最小时间间隔 P （Processor）表示处理器/存储器模块数 MIMD异步并行计算模型C3（Computation, Communication, Congestion）
7、模型 一个与体系结构无关的粗粒度的并行计算模型 强调用公用的通信操作来开发粗粒度的并行算法 考虑到了网络链路拥挤和处理器拥挤对并行算法性 能的影响 进程 进程的定义进程（process）可表示成四元组（P, C, D, S） P是程序代码 C是进程的控制状态 D是进程的数据 S是进程的执行状态 进程的状态 非存在状态：进程依赖的程序还没有投入运行 就绪状态：进程由其父进程调入并准备运行 运行状态：进程占有CPU和其它必须的计算资源 ，并执行指令 挂起状态：由于CPU或其它必须的计算资源被其 它进程占有，或必须等待某类事件的发生，进程 转入挂起状态 退出状态：进程正常结束或因异常退出而被废弃 进
8、程间通信 进程是操作系统资源调度的基本单位 各进程不能直接访问其它进程的局部内存空间 多个进程之间相互交流信息 的三种形式 ： 通信：进程间的数据传递称为进程间通信 同步：同步是使位于相同或不同处理机中的多个进程 之间相互等待的操作 聚集：聚集将位于相同或不同处理机中的多个进程的 局部结果综合起来 影响通信系统性能的因素 通信硬件 ： 包括节点存储器、I/O结构、网络界面和通信网络 本身等 通信软件： 包括通信协议结构和算法等 所提供的通信服务： 包括消息传送、流控、失效处理和保护等通信性能改进 BCL（Basic Communication Library）起着 关键的作用 三种有代表性的B
9、CL ： 双拷贝 （2Copy） 单拷贝（1-Copy） 零拷贝（Zero-Copy） 线程 线程 将一个进程分解成两个部分 ： 一部分由其资源特征构成，仍称之为进程 一部分由其执行特征构成，称之为线程 进程可由单个线程来执行 进程也可由多个线程来并行执行 多个线程将共享该进程的所有资源特征 线程单进程多线程执行示意图 并行编程环境 特征消息传递共享存储数据并行典型代表MPI, PVMOpenMPHPF可移植性主流并行计算机SMP, DSMSMP, DSM, MPP 并行粒度进程级大粒度线程级细粒度进程级细粒度并行操作方式异步异步松散同步数据存储模式分布式存储共享存储共享存储数据分配方式显式隐
10、式半隐式学习入门难度较难容易偏易可扩展性好较差一般编程语言与编译器 自动并行 研究始于20世纪70年代的自动向量化 支持将程序移植到向量计算机上 重要技术就是依赖分析 搜索确定对同一数据结构的哪些引用对是访 问同一存储单元的 HPF：数据并行编程 思想：使数据管理的多数细节自动并行化 它提供了一个指令集 用户可在程序中插入指令，以描述数据布局 HPF提供了注释形式的指令来扩展变量类型 的说明，能够对数组的数据布局进行相当详 细的控制OpenMP：共享存储并行编程 一个与FORTRAN 77和C绑定的非正式并行编程 接口 OpenMP指令在单机编译器上被当作注释而忽略 OpenMP提供锁变量用于
11、线程间的细粒度同步 在多处理机工作站机群上，OpenMP通常和MPI 同时使用，OpenMP用于节点内，MPI用于节点 间的消息传递 并行计算性能评测 并行程序执行时间 从并行程序开始执行到所有进程执行完毕，墙上时钟走过 的时间 ，包括下面几个部分： 计算CPU时间 ： 进程指令执行所花费的CPU时间 通信CPU时间 ： 进程通信花费的CPU时间 同步开销时间 ： 进程同步花费的时间 进程空闲时间 ： 当一个进程阻塞式等待其他进程的消息时，CPU通常是空闲的 加速比性能定律 并行加速比： 指对于一个给定的应用，并行算法（或并行程序）的执行速 度相对于串行算法（或串行程序）的执行速度加快了多少倍
12、 参数定义： p是并行系统中的处理器数 W是问题规模 Ws是应用程序中的串行分量 ，Wp为W中可并行化部分 f是串行分量比例 Ts=T1为串行执行时间，Tp为并行执行时间 S为加速比，E为效率 Amdahl定律 随着处理器数目的无限增大，并行系统所能达到的加速上限为1/f Gustafson定律 归一化后可得随着处理器数目的增加，加速几乎与处理器数成比例的线性增加 Sun和Ni定律 基本思想：只要存储空间许可，应尽可能增 大问题规模以产生更好或更精确的解并行程序性能评价方法 浮点峰值性能与实际浮点性能 浮点峰值性能=CPU内部浮点乘加指令流水线的条数 每条流水线每个时钟周期完成的浮点运算次数 处理器主频 数值效率和并行效率 程序性能优化 串行程序性能优化 调用高性能库 选择适当的编译器优化选项 合理定义数组维数 注意嵌套循环的顺序 数据分块 循环展开 针对CPU的指令调度、分之预测等 并行程序性能优化 减少通信量、提高通信粒度 全局通信尽量利用高效集合通信算法 挖掘算法的并行度，减少CPU空闲等待 负载平衡 通信、计算的重叠 通过重复计算来减少通信，即以计算换通信 并行编译器 并行编译器 由三部分组成：流分析，程序优化和代码生成
