单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,*,*,*,第二章 并行计算基础,组成并行计算机的各个部分：,,节点（,node,）：每个节点由多个处理器构成，可以直接进行输入输出（,I/O,）操作；,,互联网络（,interconnect network,）：所有节点通过互联网络相互连接通信；,,内存 （,memory,）：内存由多个存储模块组成,,1,、与节点对称的分布在互联网络的两侧；,,2,、位于各个节点的内部第二章 并行计算基础,,内存模块与节点分离,内存模块位于节点内部,多级存储体系结构,解决内存墙（,memory wall,）性能瓶颈问题；,,节点内部的,cache,称为二级,cache,（,L2 cache,）；,,处理器内部更小的,cache,成为一级,cache,（,L1 cache,）；,,L1 cache,连接,CPU,寄存器和,L2 cache,，负责缓存,L2 cache,中的数据到寄存器中多级存储体系结构,并行计算机的多级存储结构主要包括两个问题：,,Cache,的映射策略，即,cache,如何从内存中取得数据进行存储；,,,节点内部或者节点之间内存的访问模式,。
cache,原理，,cache,以,cache,线为基本单位，每条,cache,包含,L,个字，每个字,8,个字节例如，,L=4,，则表示,cache,线包含,4*8=32,个字节内存空间分割成块（,block,），每个块大小与,cache,线长度一致，数据在内存和,cache,之间的移动以,cache,线为基本单位,For i=1 to M,,,,A[i]=A[i]+2*B[i],,,如果操作数存在,cache,中，称该次访问是命中的，否则，该次操作是“扑空”的,多级存储体系结构,cache,的映射策略（内存块和,cache,线之间如何建立相互映射关系）,：,,直接映射策略（,direct mapping strategy,）：每个内存块只能被唯一的映射到一条,cache,线中,；,,,K,－路组关联映射策略 （,K-way set association mapping strategy,）：,Cache,被分解为,V,个组，每个组由,K,条,cache,线组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一条,cache,线；,,全关联映射策略 （,full association mapping strategy,）,:,内存块可以被映射到,cache,中的任意一条,cache,线。
访存模型,UMA,（,Uniform Memory Access,）模型：该模型内存模块与节点分离，分别位于互联网络的两侧,,物理存储器被所有节点共享；,,所有节点访问任意存储单元的时间相同；,,发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；,,各节点的,CPU,可带有局部私有高速缓存；,,外围,I/O,设备也可以共享，且每个节点有平等的访问权利访存模型,NUMA,（,Non-Uniform Memory Access,）模型：该模型内存模块分布在各个节点内部，所有局部内存模块均构成并行计算机的全局内存模块内存模块在物理上是分布的，在逻辑上是全局共享的，这种模型也称之为“分布式共享访存模型”,,物理存储器被所有节点共享，任意节点可以直接访问任意内存模块；,,节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的,3,倍以上；,,发生访存竞争时，仲裁策略对节点可能是不等价的；,,各节点的,CPU,可带有局部私有高速缓存 （,cache,）；,,外围,I/O,设备也可以共享，但对各节点是不等价的访存模型,COMA,（,Cache-Only Memory Access,）模型：全高速缓存存储访问模型,,各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；,,利用分布的高速缓存目录进行远程高速缓存的访问；,,COMA,中的高速缓存容量一般都大于,2,级高速缓存容量；,,使用,COMA,时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方。
并行计算模型,SIMD,同步并行计算模型,,共享存储的,SIMD,模型（,PRAM,模型）；,,分布存储的,SIMD,模型（,SIMD,互联网络模型）,,MIMD,异步并行计算模型,,异步,PRAM,模型,,BSP,模型,,LogP,模型,,C3,模型,,同步并行计算模型,SIMD,共享存储模型假定存在着一个容量无限大的共享存储器，有有限或无限个功能相同的处理器，且均具有简单的算术运算和逻辑判断功能，在任何时刻各处理器均可通过共享存储单元相互交换数据SIMD,共享存储模型（,PRAM,模型）,,PRAM-EREW,（,Exclusive-Read and Exclusive-Write,），不允许同时读和同时写；,,PRAM-CREW,（,Concurrent-Read and Exclusive-Write,） ，允许同时读但不允许同时写；,,PRAM-CRCW,（,Concurrent-Read and Concurrent-Write,） ，允许同时读和同时写优点：,,适合于并行算法的表达、分析和比较；,,使用简单，很多诸如处理器间通信、存储管理和进程同步等并行计算机的低级细节均隐含于模型中；,,易于设计算法和稍加修改便可运行在不同的并行计算机上；,,且有可能加入一些诸如同步和通信等需要考虑的方面。
同步并行计算模型,SIMD,分布存储模型,,采用一维线性连接的,SIMD,模型，简记为,SIMD-LC,,采用网孔连接的,SIMD,模型，简记为,SIMD-MC,,采用树形连接的,SIMD,模型，简记为,SIMD-TC,,采用树网连接的,SIMD,模型，简记为,SIMD-MT,,采用立方连接的,SIMD,模型，简记为,SIMD-CC,,采用立方环连接的,SIMD,模型，简记为,SIMD-CCC,,采用洗牌交换连接的,SIMD,模型，简记为,SIMD-SE,,采用蝶形连接的,SIMD,模型，简介为,SIMD-BF,,采用多级互联网络连接的,SIMD,模型，简记为,SIMD-MIN,,MIMD,异步计算模型,——APRAM,模型,APRAM,特点,:,,每个处理器都有其本地存储器、局部时钟和局部程序,,处理器间的通信经过共享全局存储器,,无全局时钟，各处理器异步地独立执行各自的指令,,处理器任何时间依赖关系需明确地在各处理器的程序中加入同步障（,Synchronization Barrier,）,,一条指令可在非确定但有限的时间内完成MIMD,异步计算模型,——PRAM,模型,APRAM,模型中有四类指令,:,,全局读，将全局存储单元中的内容读入本地存储器单元中,,局部操作，对本地存储器中的数执行操作，其结果存入本地存储器中,,全局写，将本地存储器单元中的内容写入全本地存储器单元中,,同步，同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序,,MIMD,异步计算模型,——BSP,模型,大同步并行,BSP,（,Bulk Synchronous Parallel,）模型,作为计算机语言和体系结构之间的桥梁，由下述三个参数描述分布存储的并行计算机模型：,,处理器,/,存储器模块（下文简称处理器）；,,处理器模块之间点到点信息传递的路由器；,,执行以时间间隔,L,为周期的路障同步器。
MIMD,异步计算模型,——BSP,模型,特点：,,将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅施行点到点的消息传递，不提供组合、复制或广播等功能，这样做既掩盖了具体的互联网络拓扑，又简化了通信协议；,,采用路障方式的以硬件实现的全局同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员并无过分的负担；,,在分析,BSP,模型的性能时，假定局部操作可在一个时间步内完成，而在每一超级步中，一个处理器至多发送或接受,h,条消息（,h-relation,）,,MIMD,异步计算模型,——LogP,C3,模型,LogP,模型,,一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来描述，但它并不涉及到具体的网络结构，也不假定算法一定要用显式的消息传递操作进行描述C3,（,Computation, Communication, Congestion,）,,是一个与体系结构无关的粗粒度的并行计算模型，旨在能反映计算复杂度，通信模式和通信期间潜在的拥挤等因素对粗粒度网络算法的影响并行编程环境,比较流行的并行编程环境主要有,3,类：消息传递、共享存储和数据并行，,,共享存储并行编程基于线程级细粒度并行，可移植性不如消息传递并行编程，但是，由于他们支持数据的共享存储，所以并行编程的难度较小，但一般情况下，当处理机个数较多时，其并行性能明显不如消息传递编程,；,,消息传递并行编程基于大粒度的进程级并行，具有最好的可扩展性，几乎被所有当前流行的各类并行计算机所支持，其具有较好的可扩展性，但是，消息传递并行编程只能支持进程间的分布式存储模式，即各个进程只能支持访问其局部内存空间，而对其他进程的局部内存空间的访问只能通过消息传递来实现，因此，学习和使用消息传递并行编程的难度均大于共享存储和数据并行这两种编程模式。
并行编程环境,3,类并行编程环境的主要特征的比较总结,,特征,消息传递,共享存储,数据并行,典型代表,MPI, PVM,OpenMP,HPF,可移植性,所有主流并行计算机,SMP, DSM,SMP, DSM, MPP,并行粒度,进程级大粒度,线程级细粒度,进程级细粒度,并行操作方式,异步,异步,松散同步,数据存储模式,分布式存储,共享存储,共享存储,数据分配方式,显式,隐式,半隐式,学习入门难度,较难,容易,偏易,可扩展性,好,较差,一般,并行计算性能评测,加速比（,Speedup,）：,用,最优串行算法的执行时间,除以,并行程序的执行时间,所得到的比值，能够准确描述对程序并行化之后所获得的性能收益最优串行算法的执行时间除以并行程序的执行时间所得到的比值,：,,,,,并行加速比就是指对于一个给定的应用，并行算法的执行速度相对于串行算法的执行速度加快了多少倍并行计算性能评测,并行程序执行时间,,等于从并行程序开始执行到所有进程执行完毕，墙上时钟走过的时间，也称为墙上时间 （,wall clock time,）对各个进程，墙上时间可进一步分解为计算,CPU,时间、通信,CPU,时间、同步开销时间、同步导致的进程空闲时间；,,计算,CPU,时间：,进程指令执行所花费的,CPU,时间，包括程序本身的指令执行占用的时间和系统指令花费的时间,；,,通信,CPU,时间；,,同步开销时间；,,进程空闲时间：,当一个进程阻塞式等待其他进程的消息时，,CPU,通常是空闲的，或者处于等待状态。
进程空闲时间是指并行程序执行过程中，进程所有空闲时间总和并行计算性能评测,加速比性能定律,——Amdahl,定律,,能够计算并行程序相对于最优串行算法在性能提升上的理论最大值,——,表述是一种直观、清楚的表述，他将程序划分为可加速与不可加速两大部分，程序总的加速比是一个关于程序中这两部分所占比例以及可加速部分性能加速程度的函数,,,,如果只对,50%,的程序加速,15%,的话，整个程序总的加速比就是：,,,Amdahl,定律,:,,,,S,表示执行程序中串行部分的比例，,n,表示处理器核的数量假设最优串行算法的执行时间为一个单位时间（也就是分子为,1,）处理器核在数量上能够无限制的增加，但是无限的处理器核却并不能带来性能上的无限增长，无论如何，程序性能上的总是有个上限，这个要受限于串行部分所占的比例程序性能优化,串行程序性能优化,——,是并行程序性能优化的基础，一个好的并行程序首先应该拥有良好的单机性能，影响程序单机性能的主要因素是程序的计算流程和处理器的体系结构,,,调用高性能库：充分利用已有的高性能程序库是提高应用程序实际性能最有效的途径之一许多著名的高性能数学程序库，如,BLAS,和,FFTW,；,,选择适当的编译器优化选项 ：现代编译器在编译时能够对程序进行优化，从而提高所生成的目标代码的性能。
这些优化功能通常是通过一组编译选项来控制；,,合理定义数组维数：现代计算机为了提高内存带宽，多采用多体交叉并行存储系统，即使用多个独立的内存体，对他们统一编址为了充分利用多体存储，在进行连续数据访问时应该使地址的增量与内存体数的最大公约数尽量的小，特别要避免地址增量正好是体数的倍数的情况，因为此时所有的访问将集中在一个存储体中；,,程序性能优化,串行程序性能优化,,注意嵌套循环的顺序：提高,cache,使用效率的一个简单原则就是尽量改善数据访问的局部性，数据访问的局部性包括空间局部性和时间局部性，空间局部性指的是访问了一个地址后，会紧接着访问他的邻居地址在嵌套的多循环语句中，循环顺序往往对循环中数据访问的局部性有很大的影响在编写嵌套的多循环代码时，一个通用的原则就是尽量使最内层循环的数据访问连续进行；,,数据分块和循环展开和一些其他方法，例如使用一些优化工具如,Intel VTune,等程序性能优化,并行程序性能优化,——,并行程序的性能优化相对于串行程序而言就有些复杂了，最主要的是选择好的并行算法和通信模式，下面介绍一下常用的并行程序优化技术,,,减少通信量、提高通信粒度：主要有三个途径：较少通信量、提高通信粒度和提高通信中的并发度。
提高通信粒度的有效方法就是减少通信次数，尽可能将可以一次传递的数据合并起来一起传递；,,全局通信尽量利用高效集合通信算法,：,当组织多个进程之间的集合通信时，使用高效的通信算法可以大大地提高通信效率，从而降低通信开销,；,,挖掘算法的并行度，减少,CPU,空闲等待,：,些具有数据相关性的计算过程会导致并行运行的部分进程空闲等待在这种情况下，可以考虑改变算法来消除数据相关性,；,程序性能优化,并行程序性能优化,,负载平衡：是导致进程空闲等待的另外一个重要因素在设计并行程序时应该充分考虑负载平衡问题，动态调整负载时要考虑负载调整的开销及由于负载不平衡而引起的空闲等待对性能的影响，寻找最优负载调整方案；,,通信、计算的重叠,：,通常让通信和计算重叠进行，利用计算时间来屏蔽通信时间，是减少通信开销得非常有效的方法实现通信与计算重叠的方法一般基于非阻塞通信，先发出非阻塞的消息接受或发送命令，然后处理与收发数据无关的计算任务，完成这些计算后再等待消息收发的完成,；,,通过引入重复计算来减少通信，即以计算换通信,：,适当引入一些重复计算，可以减少通信量和通信次数由于当前大部分并行计算机的计算速度远远大于通信速度，并且在一些情况下，当一个进程计算时，别的进程往往处于空闲等待状态，因而适当引入重复计算可以提高程序的总体性能,。