高性能计算教案-第三讲-last.ppt

第 三 讲,第二章,静态互连网络特性比较,空间并行计算的分类,指令流/数据流分类法，即费林-Flynn分类法。,节点机耦合程度分类法。,SIMD（单指令多数据流）和MIMD（多指令多数据流） SIMD是同步运行，即各个处理器分别在来自存储器的不同数据流上并行执行相同的指令流；各个处理器同步使用连接网络。 MIMD是异步运行，即各个处理器在各自的数据流上执行自己的指令流；各个处理器异步使用连接网络。 MIMD分为PVP（并行向量处理机），SMP（对称多处理机），DSM（分布共享存储多处理机），MPP（大规模并行处理机），COW（工作站机群）。,根据系统的存储器类型分为紧耦合和松耦合。,空间并行计算的发展,80 年代百家争鸣,早期：以 MIMD 并行计算机的研制为主 中期：SMP（共享存储多处理机） 后期：具有强大计算能力的并行机,90 年代：体系结构框架趋于统一 (DSM、MPP、NOW),2000 年至今：前所未有大踏步发展（ Cluster 机群、 Constellation 星群、MPP-专用高性能网络）,五种结构特性一览表,并行计算机体系结构,并行计算机访存模型（1),UMA（Uniform Memory Access）模型：均匀存储访问模型。,COMA(Cache-Only Memory Access)模型：全高速缓存存储访问。,CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型：高速缓存一致性非均匀存储访问模型。,NORMA（No-Remote Memory Access）模型：非远程存储访问模型。,NUMA（Non-Uniform Memory Access）模型：非均匀存储访问模型。,Cache（高速缓冲区）,内存访问速度 处理器执行速度,Cache：CPU与内存间的临时存储器,它的容量比内存小的多但是交换速度却比内存要快得多。,工作原理： 当CPU要读取一个数据时，首先从缓存中查找，如果找到就立即读取并送给CPU处理； 如果没有找到，就用相对慢的速度从内存中读取并送给CPU处理，同时把这个数据所在的数据块调入缓存中。,Cache类别,L2 cache：在结点内部的cache,L1 cache：在处理器内部的cache，更小容量,它的容量比内存小的多但是交换速度却比内存要快得多。,L1 cache 连接CPU 寄存器和L2 cache，负责缓存L2 cache 中的数据到寄存器中。,多级存储结构示意图,位于最顶层的是CPU，它从寄存器中读取数据；寄存器从L1 cache中读取数据。CPU、寄存器和L1 cache 构成微处理器芯片(chip)。L1 cache 从L2 cache 中读取数据，而后者从本地局部内存中获取数据。,解决方案,为了编制发挥处理器峰值性能的高性能并行程序,一个是cache 的映射策略，即cache 是如何从内存中取数并存储的；,另一个是结点内部或者结点之间内存的访问模式。,Cache使用原理,Cache以cache线(line) 为其基本组成单位，每条cache线包含L个字，每个字为8个字节。,例如，L = 4，则表示cache线包含4 x 8 = 32 个字节；,数据从内存调入cache时，不是以该单个数据字为单位，而是以该数据所在的内存块为单位，将该块的L个字一次调入cache，存储在对应的cache线中。,内存空间分割成块（block），每块大小与cache 线长度一致（L个字）。,数据在内存和cache 之间的移动，以cache 线为基本单位：,如果cache 中的数据单元要求写入内存空间，则也必须以cache 线为单位，即该数据单元所在cache 线中的所有内容一次写入内存中对应的块中。,Cache的作用,for(int i=0; I M; i+) a(i) = a(i) + 5.0 * b(i); ,如果没有cache，则内存读访问次数为2M次。,原因：程序的数据访问具有局部性，即程序中连续使用的数据一般存储在内存的连续位置。因此，通过cache 线的一次调入，随后的数据访问可能就落在cache 线中，从而达到减少内存访问的次数。,如果有cache，则内存访问次数下降为2M/L次。,Cache设计的几个关键问题,cache 容量,cache 线大小,cache 个数,cache 的映射策略,合适的长度,价格和性能的平衡,cache 线越大，则一次载入的内存数据也越多，提高性能的潜力就越大。但是，给定cache 的容量，则cache 线越大，cache 线的条数就越少，产生cache 访问冲突的可能性就越大。cache 线一般为48 个字。,两级到三级,按映射策略，内存块的数据能够且只能复制到被映射的cache 线中，而cache 线中的数据也能够且只能被映射到对应的内存块中。 可分为直接映射策略，K路组关联映射策略和全关联映射策略（理论）三种。,Cache设计的几个关键问题（2）,cache 线的置换策略,cache 数据一致性策略,对K路组关联映射策略，当某个内存块请求被置入时，如何选择组中的某条cache 线，将其数据写回内存（如果该条cache 线的数据被修改）。 LRU (Least Recently Used) 算法：置换没引用时间最长的cache线； FIFO (First Input First Output) 算法：置换最先置入的cache线； LFU (Least Frequently Used) 算法：置换使用频率最低的cache线； 随机算法：随机选择一条cache 线置换。,保持cache 数据和内存数据的一致性。 Writethrough 策略：cache 线中的数据一旦被修改，则立即写入内存块。它的缺点是，增加了许多不必要的内存访问。 Writeback 策略：当且仅当要求进行cache 线置换时，或者有外部请求访问内存块时，将cache 线的数据写入内存。,Cache 读操作工作流程,UMA vs NUMA,UMA：,物理存储器被所有处理器均匀共享；,NUMA：,被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；,所有处理器访问任何存储字取相同的时间；,处理器访问存储器时间是不一样的；,每台处理器可带私有高速缓存；,外围设备(I/O)也可以一定形式共享。,每台处理器照例可带私有高速缓存。,外设也可以某种形式共享。,发生访存竞争时，仲裁策略平等对待每个结点，即每个结点机会均等；,发生访存竞争时，仲裁策略对结点可能是不等价的。,COMA vs NORMA,COMA：,各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；,NORMA：,所有存储器是私有的；,利用分布的高速缓存目录D进行远程高速缓存的访问;,绝大数NUMA都不支持远程存储器的访问；,COMA中的高速缓存容量一般都大于2 级高速缓存容量；,在DSM中，NORMA就消失了；,并行计算机结构模型,SMP vs DSM,SMP：,内存模块被所有处理器均匀共享(UMA)；,DSM：,内存模块局部在各个结点内部，并被所有结点共享(NUMA)。,单一的操作系统映像;,局部高速缓存cache 及其数据一致性,低通信延迟：通过读/写操作系统来完成处理器间的通信，网络通信的延迟。,全系统只有一个操作系统驻留在共享存储器中，根据各个处理器的负载情况，它动态地分配各个进程到各个处理器，并保持各处理器间的负载平衡。,共享总线带宽,支持消息传递、共享存储并行程序设计。,欠可靠、可扩展性较差。,单一的操作系统映像;,局部高速缓存cache 及其数据一致性,支持消息传递、共享存储并行程序设计,低通信延迟（同SMP）与高通信带宽,可扩展性强,CC-NUMA,其特点是： 大多数使用基于目录的高速缓存一致性协议； 保留SMP结构易于编程的优点，也改善常规SMP的可扩放性； CC-NUMA实际上是一个分布共享存储的DSM多处理机系统； 它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。,五种并行机结构特性一览表,动态网络之单一总线,连接处理器、存储模块和I/O 设备等的一组导线和插座，在主设备（处理器）和从设备（存储器）之间传递数据。,三个特征：,公用总线以分时工作为基础，各处理器模块分时共享总线带宽，即在同一个时钟周期，至多只有一个设备能占有总线；,总线带宽=总线主频*总线宽度，例如假设主板的总线频率为150MHz，总线宽度为64 位，则该总线的带宽为1.2GB/s；,采用公平的监听协议与仲裁算法，以确定在某个时刻选择哪个设备占有总线。,动态网络之交叉开关,所有结点通过交叉开关阵列相互连接，每个交叉开关均为其中两个结点之间提供一条专用连接通路，同时，任意两个结点之间也能找到一个交叉开关，在它们之间建立专用连接通路。,三个特征：,结点之间的连接：交叉开关一般构成N x N 阵列，但在每一行和每一列同时只能有一个交叉点开关处于“开”状态，从而它同时只能接通N 对结点。,一般地，结点和存储器模块作为连接的对象，分别分布在拓扑结构的两侧。,结构为N x N 的交叉开关只能提供2 x N 个端口，这限制了它在大规模并行机中的应用。交叉开关一般仅适合数个处理器的情形，或者，在结点内部为处理器和存储器之间提供快速高效的通道,动态网络之例子,动态网络之例子（2）,并行计算机结构模型比较,PVP与SMP： 均为单地址空间。 在是否带Cache、互连网络要求、I/O并行度方面不同。,MPP与DSM： 在多/单地址空间、通信方式、Cache一致性方面不同。,MPP与COW： 在节点结构、互连网络要求、耦合程度方面不同。,五种并行机结构特性一览表,?,一致性问题,包括高速缓存(cache)一致性、存储一致性两个方面：,（1）高速缓存一致性 指私有Cache中共享数据的副本和共享存储器中共享数据之间的一致性。 特征：多处理器对同一存储单元的操作引起的一致性。 原因：Cache采用写回法更新策略所引起。,（2）存储一致性 指多个处理器程序的执行次序与共享存储器中共享数据存取次序之间的一致性。 特征：不同处理器对不同存储单元的操作引起的一致性。 原因：处理器内部优化执行效率(如异步流水)所致。,存储一致性例子,a. A:=1 b. print B,C,c. B:=1 d. print A,C,e. C:=1 f. print A,B,A、 B、C为共享变量 (初始状态均为0),处理器1,处理器2,处理器3,共享存储器,各PE按原有程序次序执行：有90种执行组合，26=64种输出组合； 各处理器不按原有程序次序执行：有6!=720种执行组合，64种输出组合，存在如何规定程序执行次序以保证结果正确的问题。,单处理机的一致性模型,31,Cache一致性： 一致性策略-禁止法(禁止非且仅CPU控制的主存数据进入Cache)； Cache级间一致性基于作废的监听协议。,存储一致性： 弱一致性(同步操作串行、同步操作间保证正确性)。,多处理机的一致性模型,Cache一致性： 一致性策略基于作废、基于更新； 一致性实现监听法(总线互连)、目录法(其他互连)； 一致性协议有策略和实现组合的四种协议。,存储一致性： 有顺序一致性、弱一致性、处理器一致性、释放一致性等。 不同互连结构，采取不同方法时，效果不同。,一致性模型研究内容：一致性的定义及实现结构。,Cache一致性协议,（1）总线监听一致性协议 思路：每个Cache块设有状态，各节点监听总线上的总线事务、并根据Cache块状态控制(基于作废/更新)其状态变化(状态转换图)，实现私有Cache中副本与共享存储器数据的一致性。,（2）目录一致性协议 思路：在每个宿主共享存储器单元(块)上建立一个目录，记录使用该单元的所有处理器(Cache)信息和数据状态信息，宿主节点根据这些信息实现(基于作废/更新)各Cache的一致性。,（3）一致性协议性能参数 一致性协议的实现会产生网络流量(通信)。 性能参数主要有扑空率、更新速率、流量。 影响因素：Cache容量、块大小(存储粒度)、一致性粒度等。,并行计算机通信模型,1、交互机制 交互包含交互操作、交互方式、交互模式三个方面。,（1）交互操作,通信：在两个或多个进程间传送数据。 可分为数据并行、共享地址、消息传递三种类型。,同步：进程间相互等待或允许等待的进程继续执行。 可分为原子操作、控制同步、数据同步三种类型。,（2）交互方式 可分为同步、异步互锁、异步非互锁三种方式。,（3）交互模式 有一对一(如点点)、一对多(如广播)、多对一(如聚集)、多对多(如置换)四种模式。,通信模型层次结构,通信抽象：将编程模型中的交互转换为操作系统层的通信原语的转换过程。可泛指各层之间的映射。,层间距离：表示实现的难易程度。,通信模型研究内容：定义软件/硬件界面基本的交互机制； 定义有效实现这些交互的组织结构。,编程模型,种类：共享变量、消息传输、数据并行。,内容：命名、操作、操作次序（定序）,命名：交互对象的类型和表示方式。 操作：对交互对象实施的操作的集合。 定序：对交互对象可实施的操作之间的次序关系。,命名、操作和定序类似于指令系统中指令的操作数表示、操作类型和操作步骤。,共享变量通信模型,（1）共享变量编程模型 命名：通过虚地址方式表示需要访问的任何(私有和共享) MEM内容的位置，MEM内容的数据类型通过操作表示。 操作：读、写、进程创建、进程同步。 定序：进程内操作序-采用对应进程程序的操作序； 进程间操作序采用同步原语语义的操作序。,（2）共享变量通信模型硬件原语 读、写、同步原语。 硬件通信原语与编程模型的通信抽象结果一一对应。,共享变量通信模型实现,a.虚地址-物理地址的映射 *并行机具有全局物理地址空间-UMA 硬件通过虚地址-物理地址的映射实现；,*并行机具有多个独立的局部物理地址空间-NUMA 硬件实现硬件通过虚地址-物理地址映射实现； 软件实现产生缺页事件，由OS介入实现映射。,b.通信与复制 第一次访问或产生访问扑空时发生通信，将数据副本复制到本地，否则只是数据副本重用； 共享数据不需要重新命名(与本地数据使用方法相同)； 必须保持共享数据的一致性(硬件或软件)； 通信粒度较细。,共享变量通信模型的可扩展设计,提高并行系统性能方法： 改善(更快的PE)、并行(更多的PE)。,限制PE数量的因素： PE增加时，对互连网络要求较高； 交叉开关成本太高、总线互连每个PE带宽太低 PE增加时，一致性导致的网络流量增加较快。,可扩展设计： 可扩展互连网络如多级互连网络，要求扩展成本小、访问延迟小、高的网络带宽；,向分布共享转化通过开发数据访问局部性减少网络通信概率，降低对互连网络的要求，已发展成为主流方法。,消息传递通信模型,（1）消息传递编程模型 命名：本地MEM内容位置，采用虚地址方式命名，数据类型通过操作表示；远程MEM内容位置，通过消息方式命名，数据类型也通过消息表示。 消息内容包含消息信封和消息缓冲区两部分。,操作：本地MEM访问-读、写； 远程MEM访问-发送消息、接收消息、进程创建。 发送/接收操作对应的是数据拷贝(复制+重新绑定)。,定序：进程内操作序采用对应进程程序的操作序； 进程间操作序采用发送/接收原语的操作序。 发送/接收交互有同步、异步互锁/非互锁三种交互方式。,消息传递通信模型（2）,（2）消息传递通信模型硬件原语 发送消息、接收消息。 硬件通信原语与编程模型的通信抽象结果有很大距离。,（3）消息传递通信模型实现,a.消息传递 所有消息均通过OS转换成硬件通信原语后发送； 消息通过硬件匹配接收，再由OS通知到相应进程。,b.通信与复制 每次发送/接收操作都会发生通信； 共享数据复制后需要重新命名(与本地地址重新绑定)； 由程序显式保持共享数据的一致性； 通信粒度较粗。,消息传递通信模型的发展,早期模型： 数据传输为基于CPU的阻塞传输； 互连网络传输采用存储-转发方式，传输延迟主要为网络的延迟； 对互连网络拓扑结构要求很高。,现在模型： DMA传输取代CPU的阻塞传输； 互连网络传输改为流水方式，传输延迟集中在PE到网络的延迟； 采用专用网络接口和可扩展互连网络来提高通信性能。,五种并行机结构特性一览表,NORMA非远程存储访问模型模型,访问特征：各P只能访问本地存储器，不能直接访问远程存储器(需要通过消息传递实现间接访问)。 高速缓存一致性特征：不支持。,应用：分布存储多计算机(MPP)。,大规模并行机MPP,成百上千个处理器组成的大规模计算机系统，规模是变化的。 NORMA结构，高带宽低延迟定制互连。 可扩放性：Mem, I/O,平衡设计 系统成本：商用处理器，相对稳定的结构，SMP,分布 通用性和可用性：不同的应用，PVM,MPI,交互，批处理，互连对用户透明，单一系统映象，故障 通信要求 存储器和I/O能力 例子：Intel Option Red IBM SP2 Dawning 1000,典型MPP系统特性比较,MPP所用的高性能CPU特性比较,工作站机群COW,分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核 优点： 投资风险小 系统结构灵活 性能/价格比高 能充分利用分散的计算资源 可扩放性好 问题 通信性能 并行编程环境 例子：Berkeley NOW，Alpha Farm, FXCOW,典型的机群系统,MPP vs COW,COW的每个结点都是一台完整的计算机（可能没有鼠标、显示器等外设）。COW的每个结点上都有完整的操作系统，而MPP的每个结点上通常只有操作系统的微核。 COW的每个结点内有本地磁盘，而MPP的结点内没有。 COW各结点的网络接口是连接到I/O总线上的（松耦合），而MPP各结点的网络接口是连接到存储总线上的（紧耦合）。,其中LD：本地磁盘，B：存储总线与I/O总线的接口，IOB：I/O总线。,其中MB：存储器总线，P/C：处理器和高速缓存，NIC：网络接口电路，LM：表示本地存储器。,NIC概念解析,网络接口电路（Network Interface Circuitry，NIC）是用来将计算机与网络（例如局域网）连接起来的接口电路。,典型的NIC包括一个嵌入式的处理器，一些输入、输出缓冲器，以及一些控制存储器和控制逻辑。,它的功能有：将消息格式化、路由选择、流和错误控制等。,SMPMPP机群比较,