《并行计算基础课件》由会员分享，可在线阅读，更多相关《并行计算基础课件（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）起着关键的作用 三种有代表性的BCL ： 双拷贝
9、 （2Copy） 单拷贝（1-Copy） 零拷贝（Zero-Copy）,线程,线程,将一个进程分解成两个部分 ： 一部分由其资源特征构成，仍称之为进程 一部分由其执行特征构成，称之为线程 进程可由单个线程来执行 进程也可由多个线程来并行执行 多个线程将共享该进程的所有资源特征,线程,单进程多线程执行示意图,并行编程环境,编程语言与编译器,自动并行,研究始于20世纪70年代的自动向量化 支持将程序移植到向量计算机上 重要技术就是依赖分析 搜索确定对同一数据结构的哪些引用对是访问同一存储单元的,HPF：数据并行编程,思想：使数据管理的多数细节自动并行化 它提供了一个指令集 用户可在程序中插入指令，
10、以描述数据布局 HPF提供了注释形式的指令来扩展变量类型的说明，能够对数组的数据布局进行相当详细的控制,OpenMP：共享存储并行编程,一个与FORTRAN 77和C绑定的非正式并行编程接口 OpenMP指令在单机编译器上被当作注释而忽略 OpenMP提供锁变量用于线程间的细粒度同步 在多处理机工作站机群上，OpenMP通常和MPI同时使用，OpenMP用于节点内，MPI用于节点间的消息传递,并行计算性能评测,并行程序执行时间,从并行程序开始执行到所有进程执行完毕，墙上时钟走过的时间 ，包括下面几个部分： 计算CPU时间 ： 进程指令执行所花费的CPU时间 通信CPU时间 ： 进程通信花费的C
11、PU时间 同步开销时间 ： 进程同步花费的时间 进程空闲时间 ： 当一个进程阻塞式等待其他进程的消息时，CPU通常是空闲的,加速比性能定律,并行加速比： 指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍 参数定义： p是并行系统中的处理器数 W是问题规模 Ws是应用程序中的串行分量 ，Wp为W中可并行化部分 f是串行分量比例 Ts=T1为串行执行时间，Tp为并行执行时间 S为加速比，E为效率,Amdahl定律,随着处理器数目的无限增大，并行系统所能达到的加速上限为1/f,Gustafson定律,归一化后可得,随着处理器数目的增加，加速几乎
12、与处理器数成比例的线性增加,Sun和Ni定律,基本思想：只要存储空间许可，应尽可能增大问题规模以产生更好或更精确的解,并行程序性能评价方法,浮点峰值性能与实际浮点性能 浮点峰值性能=CPU内部浮点乘加指令流水线的条数 每条流水线每个时钟周期完成的浮点运算次数 处理器主频 数值效率和并行效率,程序性能优化,串行程序性能优化,调用高性能库 选择适当的编译器优化选项 合理定义数组维数 注意嵌套循环的顺序 数据分块 循环展开 针对CPU的指令调度、分之预测等,并行程序性能优化,减少通信量、提高通信粒度 全局通信尽量利用高效集合通信算法 挖掘算法的并行度，减少CPU空闲等待 负载平衡 通信、计算的重叠 通过重复计算来减少通信，即以计算换通信,并行编译器,并行编译器,由三部分组成：流分析，程序优化和代码生成,
