单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第二章 并行计算基础,并行计算：,并行计算就是将一个大规模的计算问题分解成若干小的任务，通过运行在多个运算部件上的这些小任务的合作来求解一个规模很大的计算问题的一种方法强并行计算：如果一个计算由若干子计算构成，若各子计算之间不存在依赖关系，可以并行计算，那么这种计算可以称为强并行计算弱并行计算：如果一个计算由若干子计算构成，若各子计算之间存在依赖关系，不能并行计算，但是单个的子计算内又可以分解为若干更小粒度的子计算，且这些更小粒度的子计算是可以并行执行的，这种并行计算可以称为弱并行计算第二章 并行计算基础并行计算：,1,并行计算的应用,预测模型的构造和模拟、工程设计和自动化、能源勘探、医学、军事以及基础理论研究等领域中都对计算提出了极高的要求并行计算三种主要的基本类型：,计算密集型应用，如大型科学工程计算与数值模拟；,数据密集型应用，如数字图书馆、数据仓库、数据挖掘和计算可视化等；,网络密集型应用，如协同工作、遥控和远程医疗诊断等第二章 并行计算基础,并行计算的应用 第二章 并行计算基础,2,并行程序开发方法,并行层次与代码粒度,指令级并行：在多个并行层次中指令级并行是代码粒度最小的并行，也称为微粒度并行、甚细粒度并行；,数据级并行：又称为细粒度并行，它比指令级并行所执行的代码粒度要大一些，一般长度为几百条指令，这类并行通常都是在编译阶段由编译器来负责实现的；,控制级并行：也叫中粒度并行，通常是面对过程、子过程，其代码的长度一般为几千条指令。
这一级的并行通常需要程序员的参与，一般情况下必须由程序员先对过程间的数据依赖关系进行分析然后再开发出相应的并行性；,任务级并行：任务级并行也叫做作业级并行、粗粒度并行，其代码的长度一般可高达数万条指令，一般是由加载程序和操作系统来负责处理的并行程序开发方法 并行层次与代码粒度,3,并行程序开发方法,并行程序的开发策略,第一种是采用将已有的串行程序进行自动并行化的方法来开发适合于并行计算机运行的并行程序；,第二种是调用并行库来实现并行程序的开发；,第三种是使用并行语言重新编写能运行于高性能并行计算机上的并行代码并行程序开发方法并行程序的开发策略,4,并行程序设计模式,并行程序设计模式的基本思路,对数据进行分解，将大的数据块分解成若干小块，每个线程处理其中的某些小块；,对计算过程进行分解，将一个大的计算处理过程分解成若干可独立运行的子过程，然后每个线程运行其中的一个或多个子过程；,基于问题进行分解，将一个原问题分解为若干子问题，然后将子问题的解合并起来成为原问题的解并行程序设计模式 并行程序设计模式的基本思路,5,并行程序设计模式,并行程序设计模式,数据分解模式：将数据分解成若干独立的子数据块，每个线程处理其中的一个或多个子数据块；,分治模式：将一个原问题的求解分解为多个子问题的求解，然后再将多个子问题的解通过一定的计算方法合并为原问题的解；,流水线模式：将一个计算过程分解成流水线式的多个步骤序列，对于每个步骤的处理使用一个或多个线程来实现；,并行程序设计模式并行程序设计模式,6,并行程序设计模式,并行程序设计模式,任务并行模式：将一个大的静态计算任务分解成若干独立的小计算任务，让这些小计算任务并行执行；,任务图调度模式：将一个大的静态任务分解成若干小的计算任务时，由于很多时候各个小任务在执行时许多非独立的小任务之间存在依赖关系，将这种依赖关系通过一个无环有向图来描述，这个图就是任务图，对它的并行化方法是任务调度问题，这就是任务图调度模式;,动态任务调度模式:任务图调度模式调度的是静态的任务，但是在很多情况下任务不是静态的而是在运行过程中动态产生的。
运用共享资源分布式计算的知识实现的关于动态任务调度的并行模式就是动态任务调度模式，它的突出特点就是可以实现并行计算并行程序设计模式并行程序设计模式,7,并行计算基础,组成并行计算机的各个部分：,节点（,node,）：每个节点由多个处理器构成，可以直接进行输入输出（,I/O,）操作；,互联网络（,interconnect network,）：所有节点通过互联网络相互连接通信；,内存（,memory,）：内存由多个存储模块组成,1、与节点对称的分布在互联网络的两侧；,2、位于各个节点的内部并行计算基础组成并行计算机的各个部分：,8,并行计算基础,内存模块与节点分离,内存模块位于节点内部,并行计算基础内存模块与节点分离内存模块位于节点内部,9,多级存储体系结构,解决内存墙（,memory wall,）性能瓶颈问题；,节点内部的,cache,称为二级,cache,（,L2 cache,）；,处理器内部更小的,cache,成为一级,cache,（,L1 cache,）；,L1 cache,连接,CPU,寄存器和,L2 cache,，负责缓存,L2 cache,中的数据到寄存器中多级存储体系结构解决内存墙（memory wall）性能瓶颈,10,多级存储体系结构,并行计算机的多级存储结构主要包括两个问题：,Cache,的映射策略，即,cache,如何从内存中取得数据进行存储；,节点内部或者节点之间内存的访问模式,。
cache,原理，,cache,以,cache,线为基本单位，每条,cache,包含,L,个字，每个字,8,个字节例如，,L=4,，,则表示,cache,线包含,4*8=32,个字节内存空间分割成块（,block,），,每个块大小与,cache,线长度一致，数据在内存和,cache,之间的移动以,cache,线为基本单位,For i=1 to M,Ai=Ai+2*Bi,如果操作数存在,cache,中，称该次访问是命中的，否则，该次操作是“扑空”的,多级存储体系结构并行计算机的多级存储结构主要包括两个问题：,11,多级存储体系结构,cache,的映射策略（,内存块和,cache,线之间如何建立相互映射关系,）,：,直接映射策略（,direct mapping strategy,）：每个内存块只能被唯一的映射到一条,cache,线中,；,K,路组关联映射策略（,K-way set association mapping strategy,）：,Cache,被分解为,V,个组，每个组由,K,条,cache,线组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一条,cache,线；,全关联映射策略（,full association mapping strategy,）,:,内存块可以被映射到,cache,中的任意一条,cache,线。
多级存储体系结构cache的映射策略（内存块和cache线之,12,访存模型,UMA,（,Uniform Memory Access,）模型：该模型内存模块与节点分离，分别位于互联网络的两侧,物理存储器被所有节点共享；,所有节点访问任意存储单元的时间相同,；,发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；,各节点的,CPU,可带有局部私有高速缓存；,外围,I/O,设备也可以共享，且每个节点有平等的访问权利访存模型UMA（Uniform Memory Access）,13,访存模型,NUMA（Non-Uniform Memory Access）模型,：,该模型内存模块分布在各个节点内部，所有局部内存模块均构成并行计算机的全局内存模块内存模块在物理上是分布的，在逻辑上是全局共享的，这种模型也称之为“分布式共享访存模型”,物理存储器被所有节点共享，任意节点可以直接访问任意内存模块；,节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的,3,倍以上；,发生访存竞争时，仲裁策略对节点可能是不等价的；,各节点的,CPU,可带有局部私有高速缓存（,cache,）；,外围,I/O,设备也可以共享，但对各节点是不等价的。
访存模型NUMA（Non-Uniform Memory Ac,14,访存模型,COMA（Cache-Only Memory Access）模型,：,全高速缓存存储访问模型,各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；,利用分布的高速缓存目录进行远程高速缓存的访问；,COMA,中的高速缓存容量一般都大于,2,级高速缓存容量；,使用,COMA,时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方访存模型COMA（Cache-Only Memory Acc,15,并行计算模型,SIMD同步并行计算模型,共享存储的,SIMD,模型（,PRAM,模型）；,分布存储的,SIMD,模型（,SIMD,互联网络模型）,MIMD异步并行计算模型,异步,PRAM,模型,BSP,模型,LogP,模型,C,3,模型,并行计算模型 SIMD同步并行计算模型,16,同步并行计算模型,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共享存储模型假定存在着一个容量无限大,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分布存储模型,18,MIMD,异步计算模型,A,PRAM,模型,APRAM特点:,每个处理器都有其本地存储器、局部时钟和局部程序,处理器间的通信经过共享全局存储器,无全局时钟，各处理器异步地独立执行各自的指令,处理器任何时间依赖关系需明确地在各处理器的程序中加入同步障（,Synchronization Barrier,）,一条指令可在非确定但有限的时间内完成。
MIMD异步计算模型APRAM模型APRAM特点:,19,MIMD,异步计算模型,PRAM,模型,APRAM,模型中有四类指令,:,全局读，将全局存储单元中的内容读入本地存储器单元中,局部操作，对本地存储器中的数执行操作，其结果存入本地存储器中,全局写，将本地存储器单元中的内容写入全本地存储器单元中,同步，同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序,MIMD异步计算模型PRAM模型APRAM模型中有四类指,20,MIMD异步计算模型BSP模型,大同步并行,BSP,（,Bulk Synchronous Parallel,）,模型,作为计算机语言和体系结构之间的桥梁，由下述三个参数描述分布存储的并行计算机模型：,处理器,/,存储器模块（下文简称处理器）；,处。
