1、并行计算并行计算第 三 讲第二章李李 粤粤 2/52静态互连网络特性比较李李 粤粤 3/52空间并行计算的分类空间并行计算的分类指令流/数据流分类法，即费林-Flynn分类法。节点机耦合程度分类法。SIMD（单指令多数据流）和MIMD（多指令多数据流）SIMD是同步运行，即各个处理器分别在来自存储器的不同数据流上并行执行相同的指令流；各个处理器同步使用连接网络。MIMD是异步运行，即各个处理器在各自的数据流上执行自己的指令流；各个处理器异步使用连接网络。MIMD分为PVP（并行向量处理机），SMP（对称多处理机），DSM（分布共享存储多处理机），MPP（大规模并行处理机），COW（工作站机群）
2、。根据系统的存储器类型分为紧耦合和松耦合。李李 粤粤 4/52空间并行计算的发展空间并行计算的发展80 年代百家争鸣早期：以 MIMD 并行计算机的研制为主中期：SMP（共享存储多处理机）后期：具有强大计算能力的并行机90 年代：体系结构框架趋于统一(DSM、MPP、NOW)2000 年至今：前所未有大踏步发展（Cluster 机群、Constellation 星群、MPP-专用高性能网络）李李 粤粤 5/52五种结构特性一览表五种结构特性一览表属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD处理器类型专用定制商用商用商用商用互连网络定制交叉开关总线、交叉开关
3、定制网络定制网络商用网络（以太ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器Cray C-90，Cray T-90，银河1号IBM R50，S G I P o w e r Challenge，曙光1号Intel Paragon，IBMSP2，曙光1000/2000Stanford DASH，Cray T 3DBerkeley NOW，Alpha Farm李李 粤粤 6/52并行计算机体系结构并行计算机体系结构q 组成要
4、素l 结点（node）：一个或多个处理器组成l 互联网络（interconnetct network）：连接结点l 内存（memory）：多个存储模块组成李李 粤粤 7/52并行计算机访存模型（并行计算机访存模型（1)UMA（Uniform Memory Access）模型：均匀存储访问模型。COMA(Cache-Only Memory Access)模型：全高高速缓存速缓存存储访问。CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型：高速缓存高速缓存一致性非均匀存储访问模型。NUMA（Non-Uniform Memory Access）模型：
5、非均匀存储访问模型。李李 粤粤 8/52Cache（高速缓冲区）（高速缓冲区）内存访问速度 处理器执行速度Cache：CPU与内存间的临时存储器它的容量比内存小的多但是交换速度却比内存要快得多。工作原理：当CPU要读取一个数据时，首先从缓存中查找，如果找到就立即读取并送给CPU处理；如果没有找到，就用相对慢的速度从内存中读取并送给CPU处理，同时把这个数据所在的数据块调入缓存中。李李 粤粤 9/52Cache类别类别L2 cache：在结点内部的cacheL1 cache：在处理器内部的cache，更小容量它的容量比内存小的多但是交换速度却比内存要快得多。L1 cache 连接CPU 寄存器和
6、L2 cache，负责缓存L2 cache 中的数据到寄存器中。李李 粤粤 10/52多级存储结构示意图多级存储结构示意图位于最顶层的是CPU，它从寄存器中读取数据；寄存器从L1 cache中读取数据。CPU、寄存器和L1 cache 构成微处理器芯片(chip)。L1 cache 从L2 cache 中读取数据，而后者从本地局部内存中获取数据。李李 粤粤 11/52解决方案解决方案为了编制发挥处理器峰值性能的高性能并行程序一个是cache 的映射策略，即cache 是如何从内存中取数并存储的；另一个是结点内部或者结点之间内存的访问模式。李李 粤粤 12/52Cache使用原理使用原理Cach
7、e以cache线(line)为其基本组成单位，每条cache线包含L个字，每个字为8个字节。例如，L=4，则表示cache线包含4 x 8=32 个字节；数据从内存调入cache时，不是以该单个数据字为单位，而是以该数据所在的内存块为单位，将该块的L个字一次调入cache，存储在对应的cache线中。内存空间分割成块（block），每块大小与cache 线长度一致（L个字）。数据在内存和cache 之间的移动，以cache 线为基本单位：如果cache 中的数据单元要求写入内存空间，则也必须以cache 线为单位，即该数据单元所在cache 线中的所有内容一次写入内存中对应的块中。李李 粤粤
8、13/52Cache的作用的作用for(int i=0;I M;i+)a(i)=a(i)+5.0*b(i);如果没有cache，则内存读访问次数为2M次。原因：原因：程序的数据访问具有局部性，即程序中连续使用的数据一般存储在内存的连续位置。因此，通过cache 线的一次调入，随后的数据访问可能就落在cache 线中，从而达到减少内存访问的次数。如果有cache，则内存访问次数下降为2M/L次。李李 粤粤 14/52Cache设计的设计的几个关键问题cache 容量cache 线大小cache 个数cache 的映射策略合适的长度价格和性能的平衡cache 线越大，则一次载入的内存数据也越多，提
9、高性能的潜力就越大。但是，给定cache 的容量，则cache 线越大，cache 线的条数就越少，产生cache 访问冲突的可能性就越大。cache 线一般为48 个字。两级到三级按映射策略，内存块的数据能够且只能复制到被映射的cache 线中，而cache 线中的数据也能够且只能被映射到对应的内存块中。可分为直接映射策略，K路组关联映射策略和全关联映射策略（理论）三种。李李 粤粤 15/52Cache设计的设计的几个关键问题（2）cache 线的置换策略cache 数据一致性策略对K路组关联映射策略，当某个内存块请求被置入时，如何选择组中的某条cache 线，将其数据写回内存（如果该条ca
10、che 线的数据被修改）。LRU(Least Recently Used)算法：置换没引用时间最长的cache线；FIFO(First Input First Output)算法：置换最先置入的cache线；LFU(Least Frequently Used)算法：置换使用频率最低的cache线；随机算法：随机选择一条cache 线置换。保持cache 数据和内存数据的一致性。Writethrough 策略：cache 线中的数据一旦被修改，则立即写入内存块。它的缺点是，增加了许多不必要的内存访问。Writeback 策略：当且仅当要求进行cache 线置换时，或者有外部请求访问内存块时，将c
11、ache 线的数据写入内存。李李 粤粤 16/52Cache 读操作工作流程李李 粤粤 17/52UMA vs NUMAUMA：物理存储器被所有处理器均匀共享；P1P2PnI/OSM1SMm共享存储器处理器（）系统互连总线 交叉开关多级,网络LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSMNUMA：被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；所有处理器访问任何存储字取相同的时间；处理器访问存储器时间是不一样的；每台处理
12、器可带私有高速缓存；外围设备(I/O)也可以一定形式共享。每台处理器照例可带私有高速缓存。外设也可以某种形式共享。发生访存竞争时，仲裁策略平等对待每个结点，即每个结点机会均等；发生访存竞争时，仲裁策略对结点可能是不等价的。李李 粤粤 18/52COMA vs COMA：各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；NORMA：利用分布的高速缓存目录D进行远程高速缓存的访问;COMA中的高速缓存容量一般都大于2 级高速缓存容量；消息传递互连网络(网络，环网，超立方，立方环等)PMPMMPMPMPMPMPPMPMPM.互 连 网 络DCPDCPDCP李李 粤粤 19/52P/CL
13、MNIC定制网络(c)MPPP/CLMNICMBMBVPSM交叉开关(a)PVPVPVPSMSMP/CSMSMI/O总线或交叉开关(b)SMPP/CP/CP/CLMNICDIRMB定制网络(d)DSMP/CLMNICDIRMBLDP/CMMBIOB(e)COWLDP/CMMBIOB商品网络(以太网，ATM，etc.)BridgeNICNICBridge并行计算机结构模型并行计算机结构模型 李李 粤粤 20/52SMP vs DSMSMP：内存模块被所有处理器均匀共享(UMA)；DSM：内存模块局部在各个结点内部，并被所有结点共享(NUMA)。单一的操作系统映像;局部高速缓存cache 及其数据
14、一致性低通信延迟：通过读/写操作系统来完成处理器间的通信，500350300SPECfp 92283300750550600SPECint 958.0922511N/A7.4SPECfp 956.7030017N/A15其它特性CISC/RISC混合短流水线长L1高速缓存最高时钟频率最大片上2级高速缓存多媒体和图形指令MP机群总线可支持4个CPU李李 粤粤 48/52工作站机群工作站机群COW分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核优点：投资风险小系统结构灵活性能/价格比高能充分利用分散的计算资源可扩放性好问题通信性能
15、并行编程环境例子：Berkeley NOW，Alpha Farm,FXCOWP/CMMIOMIOMP/CNICNICDDLAN李李 粤粤 49/52典型的机群系统典型的机群系统典型的机群系统特点一览表名称系统特点Princeton:SHRIMPPC商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信Karsruhe:Parastation用于分布并行处理的有效通信网络和软件开发Rice:TreadMarks软件实现分布共享存储的工作站机群Wisconsin:Wind Tunnel在经由商用网络互连的工作站机群上实现分布共享存储C h i c a、M a r y l、Penns:NSCP国家
16、可扩放机群计划：在通过因特网互连的3个本地机群系统上进行元计算Argonne:Globus在由ATM连接的北美17个站点的WAN上开发元计算平台和软件Syracuse:WWVM使用因特网和HPCC技术，在世界范围的虚拟机上进行高性能计算HKU:Pearl Cluster研究机群在分布式多媒体和金融数字库方面的应用Virgina:Legion在国家虚拟计算机设施上开发元计算软件李李 粤粤 50/52MPP vs COWCOW的每个结点都是一台完整的计算机（可能没有鼠标、显示器等外设）。COW的每个结点上都有完整的操作系统，而MPP的每个结点上通常只有操作系统的微核。COW的每个结点内有本地磁盘，
17、而MPP的结点内没有。COW各结点的网络接口是连接到I/O总线上的（松耦合），而MPP各结点的网络接口是连接到存储总线上的（紧耦合）。其中LD：本地磁盘，B：存储总线与I/O总线的接口，IOB：I/O总线。其中MB：存储器总线，P/C：处理器和高速缓存，NIC：网络接口电路，LM：表示本地存储器。李李 粤粤 51/52NIC概念解析概念解析 网络接口电路（Network Interface Circuitry，NIC）是用来将计算机与网络（例如局域网）连接起来的接口电路。典型的NIC包括一个嵌入式的处理器，一些输入、输出缓冲器，以及一些控制存储器和控制逻辑。它的功能有：将消息格式化、路由选择、流和错误控制等。李李 粤粤 52/52SMPMPP机群比较机群比较系统特征SMPMPP机群节点数量(N)O(10)O(100)-O(1000)O(100)节点复杂度中粒度或细粒度细粒度或中粒度中粒度或粗粒度节点间通信 共享存储器消息传递或共享变量（有DSM时）消息传递节点操作系统1N(微内核)和1个主机OS(单一)N(希望为同构)支持单一系统映像永远部分希望地址空间单一多或单一（有DSM时）多个作业调度单一运行队列主机上单一运行队列协作多队列网络协议非标准非标准标准或非标准可用性通常较低低到中高可用或容错性能/价格比一般一般高互连网络总线/交叉开关定制商用
