多核程序设计第二章并行程序设计基础并行计算基础课件

第二章并行计算基础并行计算：并行计算就是将一个大规模的计算问题分解成若干小的任务，通过运行在多个运算部件上的这些小任务的合作来求解一个规模很大的计算问题的一种方法。强并行计算：如果一个计算由若干子计算构成，若各子计算之间不存在依赖关系，可以并行计算，那么这种计算可以称为强并行计算。弱并行计算：如果一个计算由若干子计算构成，若各子计算之间存在依赖关系，不能并行计算，但是单个的子计算内又可以分解为若干更小粒度的子计算，且这些更小粒度的子计算是可以并行执行的，这种并行计算可以称为弱并行计算。第二章并行计算基础并行计算：1并行计算的应用预测模型的构造和模拟、工程设计和自动化、能源勘探、医学、军事以及基础理论研究等领域中都对计算提出了极高的要求。并行计算三种主要的基本类型：计算密集型应用，如大型科学工程计算与数值模拟；数据密集型应用，如数字图书馆、数据仓库、数据挖掘和计算可视化等；网络密集型应用，如协同工作、遥控和远程医疗诊断等。第二章并行计算基础并行计算的应用第二章并行计算基础2并行程序开发方法

并行层次与代码粒度指令级并行：在多个并行层次中指令级并行是代码粒度最小的并行，也称为微粒度并行、甚细粒度并行；数据级并行：又称为细粒度并行，它比指令级并行所执行的代码粒度要大一些，一般长度为几百条指令，这类并行通常都是在编译阶段由编译器来负责实现的；控制级并行：也叫中粒度并行，通常是面对过程、子过程，其代码的长度一般为几千条指令。这一级的并行通常需要程序员的参与，一般情况下必须由程序员先对过程间的数据依赖关系进行分析然后再开发出相应的并行性；任务级并行：任务级并行也叫做作业级并行、粗粒度并行，其代码的长度一般可高达数万条指令，一般是由加载程序和操作系统来负责处理的。并行程序开发方法并行层次与代码粒度3并行程序开发方法并行程序的开发策略第一种是采用将已有的串行程序进行自动并行化的方法来开发适合于并行计算机运行的并行程序；第二种是调用并行库来实现并行程序的开发；第三种是使用并行语言重新编写能运行于高性能并行计算机上的并行代码。并行程序开发方法并行程序的开发策略4并行程序设计模式

并行程序设计模式的基本思路对数据进行分解，将大的数据块分解成若干小块，每个线程处理其中的某些小块；对计算过程进行分解，将一个大的计算处理过程分解成若干可独立运行的子过程，然后每个线程运行其中的一个或多个子过程；基于问题进行分解，将一个原问题分解为若干子问题，然后将子问题的解合并起来成为原问题的解。并行程序设计模式并行程序设计模式的基本思路5并行程序设计模式并行程序设计模式数据分解模式：将数据分解成若干独立的子数据块，每个线程处理其中的一个或多个子数据块；分治模式：将一个原问题的求解分解为多个子问题的求解，然后再将多个子问题的解通过一定的计算方法合并为原问题的解；流水线模式：将一个计算过程分解成流水线式的多个步骤序列，对于每个步骤的处理使用一个或多个线程来实现；并行程序设计模式并行程序设计模式6并行程序设计模式并行程序设计模式任务并行模式：将一个大的静态计算任务分解成若干独立的小计算任务，让这些小计算任务并行执行；任务图调度模式：将一个大的静态任务分解成若干小的计算任务时，由于很多时候各个小任务在执行时许多非独立的小任务之间存在依赖关系，将这种依赖关系通过一个无环有向图来描述，这个图就是任务图，对它的并行化方法是任务调度问题，这就是任务图调度模式;动态任务调度模式:任务图调度模式调度的是静态的任务，但是在很多情况下任务不是静态的而是在运行过程中动态产生的。运用共享资源分布式计算的知识实现的关于动态任务调度的并行模式就是动态任务调度模式，它的突出特点就是可以实现并行计算。并行程序设计模式并行程序设计模式7并行计算基础组成并行计算机的各个部分：节点（node）：每个节点由多个处理器构成，可以直接进行输入输出（I/O）操作；互联网络（interconnectnetwork）：所有节点通过互联网络相互连接通信；内存（memory）：内存由多个存储模块组成1、与节点对称的分布在互联网络的两侧；2、位于各个节点的内部。并行计算基础组成并行计算机的各个部分：8并行计算基础内存模块与节点分离内存模块位于节点内部并行计算基础内存模块与节点分离内存模块位于节点内部9多级存储体系结构解决内存墙（memorywall）性能瓶颈问题；节点内部的cache称为二级cache（L2cache）；处理器内部更小的cache成为一级cache（L1cache）；L1cache连接CPU寄存器和L2cache，负责缓存L2cache中的数据到寄存器中。多级存储体系结构解决内存墙（memorywall）性能瓶颈10多级存储体系结构并行计算机的多级存储结构主要包括两个问题：Cache的映射策略，即cache如何从内存中取得数据进行存储；

节点内部或者节点之间内存的访问模式。cache原理，cache以cache线为基本单位，每条cache包含L个字，每个字8个字节。例如，L=4，则表示cache线包含4*8=32个字节。内存空间分割成块（block），每个块大小与cache线长度一致，数据在内存和cache之间的移动以cache线为基本单位。Fori=1toM

A[i]=A[i]+2*B[i]

如果操作数存在cache中，称该次访问是命中的，否则，该次操作是“扑空”的。多级存储体系结构并行计算机的多级存储结构主要包括两个问题：11多级存储体系结构cache的映射策略（内存块和cache线之间如何建立相互映射关系）：直接映射策略（directmappingstrategy）：每个内存块只能被唯一的映射到一条cache线中；

K－路组关联映射策略（K-waysetassociationmappingstrategy）：Cache被分解为V个组，每个组由K条cache线组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一条cache线；全关联映射策略（fullassociationmappingstrategy）:内存块可以被映射到cache中的任意一条cache线。多级存储体系结构cache的映射策略（内存块和cache线之12访存模型UMA（UniformMemoryAccess）模型：该模型内存模块与节点分离，分别位于互联网络的两侧物理存储器被所有节点共享；所有节点访问任意存储单元的时间相同；发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；各节点的CPU可带有局部私有高速缓存；外围I/O设备也可以共享，且每个节点有平等的访问权利。访存模型UMA（UniformMemoryAccess）13访存模型NUMA（Non-UniformMemoryAccess）模型：该模型内存模块分布在各个节点内部，所有局部内存模块均构成并行计算机的全局内存模块。内存模块在物理上是分布的，在逻辑上是全局共享的，这种模型也称之为“分布式共享访存模型” 物理存储器被所有节点共享，任意节点可以直接访问任意内存模块；节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的3倍以上；发生访存竞争时，仲裁策略对节点可能是不等价的；各节点的CPU可带有局部私有高速缓存（cache）；外围I/O设备也可以共享，但对各节点是不等价的。访存模型NUMA（Non-UniformMemoryAc14访存模型COMA（Cache-OnlyMemoryAccess）模型：全高速缓存存储访问模型各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；利用分布的高速缓存目录进行远程高速缓存的访问；COMA中的高速缓存容量一般都大于2级高速缓存容量；使用COMA时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方。访存模型COMA（Cache-OnlyMemoryAcc15并行计算模型

SIMD同步并行计算模型共享存储的SIMD模型（PRAM模型）；分布存储的SIMD模型（SIMD互联网络模型）MIMD异步并行计算模型异步PRAM模型BSP模型LogP模型C3模型并行计算模型SIMD同步并行计算模型16同步并行计算模型SIMD共享存储模型假定存在着一个容量无限大的共享存储器，有有限或无限个功能相同的处理器，且均具有简单的算术运算和逻辑判断功能，在任何时刻各处理器均可通过共享存储单元相互交换数据。

SIMD共享存储模型（PRAM模型）PRAM-EREW（Exclusive-ReadandExclusive-Write），不允许同时读和同时写；PRAM-CREW（Concurrent-ReadandExclusive-Write），允许同时读但不允许同时写；PRAM-CRCW（Concurrent-ReadandConcurrent-Write），允许同时读和同时写。优点：适合于并行算法的表达、分析和比较；使用简单，很多诸如处理器间通信、存储管理和进程同步等并行计算机的低级细节均隐含于模型中；易于设计算法和稍加修改便可运行在不同的并行计算机上；且有可能加入一些诸如同步和通信等需要考虑的方面。同步并行计算模型SIMD共享存储模型假定存在着一个容量无限大17同步并行计算模型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同步并行计算模型SIMD分布存储模型18MIMD异步计算模型——APRAM模型APRAM特点:每个处理器都有其本地存储器、局部时钟和局部程序处理器间的通信经过共享全局存储器无全局时钟，各处理器异步地独立执行各自的指令处理器任何时间依赖关系需明确地在各处理器的程序中加入同步障（SynchronizationBarrier）一条指令可在非确定但有限的时间内完成。MIMD异步计算模型——APRAM模型APRAM特点:19MIMD异步计算模型——PRAM模型APRAM模型中有四类指令:全局读，将全局存储单元中的内容读入本地存储器单元中局部操作，对本地存储器中的数执行操作，其结果存入本地存储器中全局写，将本地存储器单元中的内容写入全本地存储器单元中同步，同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序MIMD异步计算模型——PRAM模型APRAM模型中有四类指20MIMD异步计算模型——BSP模型大同步并行BSP（BulkSynchronousParallel）模型

作为计算机语言和体系结构之间的桥梁，由下述三个参数描述分布存储的并行计算机模型：处理器/存储器模块（下文简称处理器）；处理器模块之间点到点信息传递的路由器；执行以时间间隔L为周期的路障同步器。MIMD异步计算模型——BSP模型大同步并行BSP（Bulk21MIMD异步计算模型——BSP模型特点：将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅施行点到点的消息传递，不提供组合、复制或广播等功能，这样做既掩盖了具体的互联网络拓扑，又简化了通信协议；采用路障方式的以硬件实现的全局同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员并无过分的负担；在分析BSP模型的性能时，假定局部操作可在一个时间步内完成，而在每一超级步中，一个处理器至多发送或接受h条消息（h-relation）MIMD异步计算模型——BSP模型特点：22MIMD异步计算模型——LogP,C3模型LogP模型一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来描述，但它并不涉及到具体的网络结构，也不假定算法一定要用显式的消息传递操作进行描述。

C3（Computation,Communication,Congestion）是一个与体系结构无关的粗粒度的并行计算模型，旨在能反映计算复杂度，通信模式和通信期间潜在的拥挤等因素对粗粒度网络算法的影响。MIMD异步计算模型——LogP,C3模型LogP模型23并行编程环境比较流行的并行编程环境主要有3类：消息传递、共享存储和数据并行，共享存储并行编程基于线程级细粒度并行，可移植性不如消息传递并行编程，但是，由于他们支持数据的共享存储，所以并行编程的难度较小，但一般情况下，当处理机个数较多时，其并行性能明显不如消息传递编程；消息传递并行编程基于大粒度的进程级并行，具有最好的可扩展性，几乎被所有当前流行的各类并行计算机所支持，其具有较好的可扩展性，但是，消息传递并行编程只能支持进程间的分布式存储模式，即各个进程只能支持访问其局部内存空间，而对其他进程的局部内存空间的访问只能通过消息传递来实现，因此，学习和使用消息传递并行编程的难度均大于共享存储和数据并行这两种编程模式。

并行编程环境比较流行的并行编程环境主要有3类：消息传递、共享24并行编程环境3类并行编程环境的主要特征的比较总结

特征消息传递共享存储数据并行典型代表MPI,PVMOpenMPHPF可移植性所有主流并行计算机SMP,DSMSMP,DSM,MPP并行粒度进程级大粒度线程级细粒度进程级细粒度并行操作方式异步异步松散同步数据存储模式分布式存储共享存储共享存储数据分配方式显式隐式半隐式学习入门难度较难容易偏易可扩展性好较差一般并行编程环境3类并行编程环境的主要特征的比较总结特征消息传25并行计算性能评测加速比（Speedup）：用最优串行算法的执行时间除以并行程序的执行时间所得到的比值，能够准确描述对程序并行化之后所获得的性能收益。

最优串行算法的执行时间除以并行程序的执行时间所得到的比值：并行加速比就是指对于一个给定的应用，并行算法的执行速度相对于串行算法的执行速度加快了多少倍。并行计算性能评测加速比（Speedup）：用最优串行算法的执26并行计算性能评测并行程序执行时间等于从并行程序开始执行到所有进程执行完毕，墙上时钟走过的时间，也称为墙上时间（wallclocktime）。对各个进程，墙上时间可进一步分解为计算CPU时间、通信CPU时间、同步开销时间、同步导致的进程空闲时间；计算CPU时间：进程指令执行所花费的CPU时间，包括程序本身的指令执行占用的时间和系统指令花费的时间；通信CPU时间；同步开销时间；进程空闲时间：当一个进程阻塞式等待其他进程的消息时，CPU通常是空闲的，或者处于等待状态。进程空闲时间是指并行程序执行过程中，进程所有空闲时间总和。

并行计算性能评测并行程序执行时间27并行计算性能评测加速比性能定律——Amdahl定律能够计算并行程序相对于最优串行算法在性能提升上的理论最大值——表述是一种直观、清楚的表述，他将程序划分为可加速与不可加速两大部分，程序总的加速比是一个关于程序中这两部分所占比例以及可加速部分性能加速程度的函数

如果只对50%的程序加速15%的话，整个程序总的加速比就是：

Amdahl定律:S表示执行程序中串行部分的比例，n表示处理器核的数量。假设最优串行算法的执行时间为一个单位时间（也就是分子为1）。处理器核在数量上能够无限制的增加，但是无限的