并行计算基础

并行计算基础第一页，共四十七页，2022年，8月28日本讲主要内容并行计算机体系结构并行计算模型进程线程并行编程环境编程语言与编译器并行计算性能评测常用并行数值算法并行编译器第二页，共四十七页，2022年，8月28日并行计算机体系结构第三页，共四十七页，2022年，8月28日组成并行计算机的各个部分为：节点（node）：每个节点由多个处理器构成，可以直接输入输出互联网络（interconnectnetwork）：所有节点通过互联网络相互连接通信。内存（memory）：内存由多个存储模块组成，这些模块或者与节点对称地分布在互联网络的两侧，或者位于各个节点的内部第四页，共四十七页，2022年，8月28日并行计算机体系结构示意图，内存模块与节点分离第五页，共四十七页，2022年，8月28日并行计算机体系结构示意图，内存模块位于节点内部

第六页，共四十七页，2022年，8月28日多级存储体系结构微处理器的峰值运算速度每18个月翻一番内存模块的容量每年几乎翻一番内存模块的访问速度却没有得到平衡发展内存的访问速度要比处理器执行速度慢很多内存墙性能瓶颈 =〉多级存储结构第七页，共四十七页，2022年，8月28日多级存储体系结构第八页，共四十七页，2022年，8月28日并行计算机访存模型UMA（UniformMemoryAccess）模型内存模块与节点分离，分别位于互联网络两侧物理存储器被所有节点共享所有节点访问任意存储单元的时间相同发生访存竞争时，仲裁策略平等对待每个节点各节点的CPU可带有局部私有高速缓存外围I/O设备也可以共享，且每个节点有平等的访问权利第九页，共四十七页，2022年，8月28日并行计算机访存模型NUMA（Non-UniformMemoryAccess）模型内存模块分布在各个节点内部物理存储器被所有节点共享，任意节点可以直接访问任意内存模块节点访问内存模块的速度不同发生访存竞争时，仲裁策略对节点可能是不等价的各节点的CPU可带有局部私有高速缓存外围I/O设备也可以共享，但对各节点是不等价的第十页，共四十七页，2022年，8月28日并行计算机访存模型COMA（Cache-OnlyMemoryAccess）模型各处理器节点中没有存储层次结构利用分布的高速缓存目录进行远程高速缓存的访问COMA中的高速缓存容量一般都大于2级高速缓存容量数据开始时可以任意分配，在运行时它最终会被迁移到要用到它的地方第十一页，共四十七页，2022年，8月28日并行计算机访存模型NORMA（No-RemoteMemoryAccess）模型所有存储器都是私有的绝大多数NORMA都不支持远程存储器访问第十二页，共四十七页，2022年，8月28日

并行计算机系统的不同访存模型分类

第十三页，共四十七页，2022年，8月28日并行计算模型第十四页，共四十七页，2022年，8月28日SIMD同步并行计算模型SIMD共享存储模型；并行随机存取机器假定存在着一个容量无限大的共享存储器有有限或无限个功能相同的处理器均具有简单的算术运算和逻辑判断功能在任何时刻各处理器均可通过共享存储单元相互交换数据第十五页，共四十七页，2022年，8月28日SIMD同步并行计算模型SIMD分布存储模型，常见模型有：采用一维线性连接的SIMD模型采用网孔连接的SIMD模型采用树形连接的SIMD模型采用树网连接的SIMD模型采用立方连接的SIMD模型采用立方环连接的SIMD模型采用洗牌交换连接的SIMD模型采用多级互联网络连接的SIMD模型第十六页，共四十七页，2022年，8月28日

MIMD异步并行计算模型异步PRAM模型每个处理器都有其本地存储器、局部时钟和局部程序处理器间的通信经过共享全局存储器无全局时钟，各处理器异步地独立执行各自的指令处理器任何时间依赖关系需明确地在各处理器的程序中加入同步（路）障一条指令可在非确定但有限的时间内完成第十七页，共四十七页，2022年，8月28日MIMD异步并行计算模型BSP模型计算由一系列用全局同步分开的周期为L的超级步（superstep）组成在各超级步中:每个处理器均执行局部计算通过路由器接受和发送消息然后做一全局检查，以确定该超级步是否已由所有的处理器完成若是，则前进到下一超级步否则下一L周期被分配给未曾完成的超级步第十八页，共四十七页，2022年，8月28日MIMD异步并行计算模型LogP模型一种分布存储的、点到点通信的多处理机模型其中通信网络由一组参数来描述:L（Latency）表示消息从源到目的在网络上的延迟o（overhead）表示处理器发送或接受一条消息消耗在网络协议栈中的开销g（Gap）表示处理器可连续进行消息发送或接受的最小时间间隔P（Processor）表示处理器/存储器模块数

第十九页，共四十七页，2022年，8月28日MIMD异步并行计算模型C3（Computation,Communication,Congestion）模型一个与体系结构无关的粗粒度的并行计算模型强调用公用的通信操作来开发粗粒度的并行算法考虑到了网络链路拥挤和处理器拥挤对并行算法性能的影响第二十页，共四十七页，2022年，8月28日进程第二十一页，共四十七页，2022年，8月28日进程的定义进程（process）可表示成四元组（P,C,D,S）P是程序代码C是进程的控制状态D是进程的数据S是进程的执行状态第二十二页，共四十七页，2022年，8月28日进程的状态非存在状态：进程依赖的程序还没有投入运行就绪状态：进程由其父进程调入并准备运行运行状态：进程占有CPU和其它必须的计算资源，并执行指令挂起状态：由于CPU或其它必须的计算资源被其它进程占有，或必须等待某类事件的发生，进程转入挂起状态退出状态：进程正常结束或因异常退出而被废弃第二十三页，共四十七页，2022年，8月28日进程间通信进程是操作系统资源调度的基本单位各进程不能直接访问其它进程的局部内存空间多个进程之间相互交流信息的三种形式：通信：进程间的数据传递称为进程间通信同步：同步是使位于相同或不同处理机中的多个进程之间相互等待的操作聚集：聚集将位于相同或不同处理机中的多个进程的局部结果综合起来第二十四页，共四十七页，2022年，8月28日影响通信系统性能的因素通信硬件：包括节点存储器、I/O结构、网络界面和通信网络本身等通信软件：包括通信协议结构和算法等所提供的通信服务：包括消息传送、流控、失效处理和保护等第二十五页，共四十七页，2022年，8月28日通信性能改进BCL（BasicCommunicationLibrary）起着关键的作用三种有代表性的BCL：双拷贝（2－Copy）单拷贝（1-Copy）零拷贝（Zero-Copy）第二十六页，共四十七页，2022年，8月28日线程第二十七页，共四十七页，2022年，8月28日线程将一个进程分解成两个部分：一部分由其资源特征构成，仍称之为进程一部分由其执行特征构成，称之为线程进程可由单个线程来执行进程也可由多个线程来并行执行多个线程将共享该进程的所有资源特征第二十八页，共四十七页，2022年，8月28日线程单进程多线程执行示意图

第二十九页，共四十七页，2022年，8月28日并行编程环境第三十页，共四十七页，2022年，8月28日特征消息传递共享存储数据并行典型代表MPI,PVMOpenMPHPF可移植性主流并行计算机SMP,DSMSMP,DSM,MPP并行粒度进程级大粒度线程级细粒度进程级细粒度并行操作方式异步异步松散同步数据存储模式分布式存储共享存储共享存储数据分配方式显式隐式半隐式学习入门难度较难容易偏易可扩展性好较差一般第三十一页，共四十七页，2022年，8月28日编程语言与编译器第三十二页，共四十七页，2022年，8月28日自动并行研究始于20世纪70年代的自动向量化支持将程序移植到向量计算机上重要技术就是依赖分析搜索确定对同一数据结构的哪些引用对是访问同一存储单元的第三十三页，共四十七页，2022年，8月28日HPF：数据并行编程思想：使数据管理的多数细节自动并行化它提供了一个指令集用户可在程序中插入指令，以描述数据布局HPF提供了注释形式的指令来扩展变量类型的说明，能够对数组的数据布局进行相当详细的控制第三十四页，共四十七页，2022年，8月28日OpenMP：共享存储并行编程一个与FORTRAN77和C绑定的非正式并行编程接口OpenMP指令在单机编译器上被当作注释而忽略OpenMP提供锁变量用于线程间的细粒度同步在多处理机工作站机群上，OpenMP通常和MPI同时使用，OpenMP用于节点内，MPI用于节点间的消息传递第三十五页，共四十七页，2022年，8月28日并行计算性能评测第三十六页，共四十七页，2022年，8月28日并行程序执行时间 从并行程序开始执行到所有进程执行完毕，墙上时钟走过的时间，包括下面几个部分：计算CPU时间：进程指令执行所花费的CPU时间通信CPU时间：进程通信花费的CPU时间同步开销时间：进程同步花费的时间进程空闲时间：当一个进程阻塞式等待其他进程的消息时，CPU通常是空闲的第三十七页，共四十七页，2022年，8月28日加速比性能定律并行加速比：指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍参数定义：p是并行系统中的处理器数W是问题规模Ws是应用程序中的串行分量，Wp为W中可并行化部分f是串行分量比例Ts=T1为串行执行时间，Tp为并行执行时间S为加速比，E为效率第三十八页，共四十七页，2022年，8月28日Amdahl定律随着处理器数目的无限增大，并行系统所能达到的加速上限为1/f

第三十九页，共四十七页，2022年，8月28日Gustafson定律归一化后可得

随着处理器数目的增加，加速几乎与处理器数成比例的线性增加第四十页，共四十七页，2022年，8月28日Sun和Ni定律基本思想：只要存储空间许可，应尽可能增大问题规模以产生更好或更精确的解

第四十一页，共四十七页，2022年，8月28日并行程序性能评价方法浮点峰值性能与实际浮点性能浮点峰值性能=CPU内部浮点乘加指令流水线的条数╳每条流水线每个时钟周期完成的浮点运算次数╳处理器主频数值效率和并行效率第四十二页，共四十七页，2022年，8月28日程序性能优化第四十三页，共四十七页，2022年，8月28日串行程序性能优化调用高性能库选择适当的编译器优化选项合理定义数组维数注意嵌套循环的顺序数据分块