高性能计算教案-第三讲-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 UniformMemoryAccess 模型 均匀存储访问模型 COMA Cache OnlyMemoryAccess 模型 全高速缓存存储访问 CC NUMA Coherent CacheNonuniformMemoryAccess 模型 高速缓存一致性非均匀存储访问模型 NORMA No RemoteMemoryAccess 模型 非远程存储访问模型 NUMA Non UniformMemoryAccess 模型 非均匀存储访问模型 Cache 高速缓冲区 内存访问速度 处理器执行速度 Cache CPU与内存间的临时存储器 它的容量比内存小的多但是交换速度却比内存要快得多 工作原理 当CPU要读取一个数据时 首先从缓存中查找 如果找到就立即读取并送给CPU处理 如果没有找到 就用相对慢的速度从内存中读取并送给CPU处理 同时把这个数据所在的数据块调入缓存中 Cache类别 L2cache 在结点内部的cache L1cache 在处理器内部的cache 更小容量 它的容量比内存小的多但是交换速度却比内存要快得多 L1cache连接CPU寄存器和L2cache 负责缓存L2cache中的数据到寄存器中 多级存储结构示意图 位于最顶层的是CPU 它从寄存器中读取数据 寄存器从L1cache中读取数据 CPU 寄存器和L1cache构成微处理器芯片 chip L1cache从L2cache中读取数据 而后者从本地局部内存中获取数据 解决方案 为了编制发挥处理器峰值性能的高性能并行程序 一个是cache的映射策略 即cache是如何从内存中取数并存储的 另一个是结点内部或者结点之间内存的访问模式 Cache使用原理 Cache以cache线 line 为其基本组成单位 每条cache线包含L个字 每个字为8个字节 例如 L 4 则表示cache线包含4x8 32个字节 数据从内存调入cache时 不是以该单个数据字为单位 而是以该数据所在的内存块为单位 将该块的L个字一次调入cache 存储在对应的cache线中 内存空间分割成块 block 每块大小与cache线长度一致 L个字 数据在内存和cache之间的移动 以cache线为基本单位 如果cache中的数据单元要求写入内存空间 则也必须以cache线为单位 即该数据单元所在cache线中的所有内容一次写入内存中对应的块中 Cache的作用 for inti 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线一般为4 8个字 两级到三级 按映射策略 内存块的数据能够且只能复制到被映射的cache线中 而cache线中的数据也能够且只能被映射到对应的内存块中 可分为直接映射策略 K 路组关联映射策略和全关联映射策略 理论 三种 Cache设计的几个关键问题 2 cache线的置换策略 cache数据一致性策略 对K 路组关联映射策略 当某个内存块请求被置入时 如何选择组中的某条cache线 将其数据写回内存 如果该条cache线的数据被修改 LRU LeastRecentlyUsed 算法 置换没引用时间最长的cache线 FIFO FirstInputFirstOutput 算法 置换最先置入的cache线 LFU LeastFrequentlyUsed 算法 置换使用频率最低的cache线 随机算法 随机选择一条cache线置换 保持cache数据和内存数据的一致性 Write through策略 cache线中的数据一旦被修改 则立即写入内存块 它的缺点是 增加了许多不必要的内存访问 Write back策略 当且仅当要求进行cache线置换时 或者有外部请求访问内存块时 将cache线的数据写入内存 Cache读操作工作流程 UMAvsNUMA UMA 物理存储器被所有处理器均匀共享 NUMA 被共享的存储器在物理上是分布在所有的处理器中的 其所有本地存储器的集合就组成了全局地址空间 所有处理器访问任何存储字取相同的时间 处理器访问存储器时间是不一样的 每台处理器可带私有高速缓存 外围设备 I O 也可以一定形式共享 每台处理器照例可带私有高速缓存 外设也可以某种形式共享 发生访存竞争时 仲裁策略平等对待每个结点 即每个结点机会均等 发生访存竞争时 仲裁策略对结点可能是不等价的 COMAvsNORMA COMA 各处理器节点中没有存储层次结构 全部高速缓存组成了全局地址空间 NORMA 所有存储器是私有的 利用分布的高速缓存目录D进行远程高速缓存的访问 绝大数NUMA都不支持远程存储器的访问 COMA中的高速缓存容量一般都大于2级高速缓存容量 在DSM中 NORMA就消失了 并行计算机结构模型 SMPvsDSM SMP 内存模块被所有处理器均匀共享 UMA DSM 内存模块局部在各个结点内部 并被所有结点共享 NUMA 单一的操作系统映像 局部高速缓存cache及其数据一致性 低通信延迟 通过读 写操作系统来完成处理器间的通信 网络通信的延迟 全系统只有一个操作系统驻留在共享存储器中 根据各个处理器的负载情况 它动态地分配各个进程到各个处理器 并保持各处理器间的负载平衡 共享总线带宽 支持消息传递 共享存储并行程序设计 欠可靠 可扩展性较差 单一的操作系统映像 局部高速缓存cache及其数据一致性 支持消息传递 共享存储并行程序设计 低通信延迟 同SMP 与高通信带宽 可扩展性强 CC NUMA 其特点是 大多数使用基于目录的高速缓存一致性协议 保留SMP结构易于编程的优点 也改善常规SMP的可扩放性 CC NUMA实际上是一个分布共享存储的DSM多处理机系统 它最显著的优点是程序员无需明确地在节点上分配数据 系统的硬件和软件开始时自动在各节点分配数据 在运行期间 高速缓存一致性硬件会自动地将数据迁移至要用到它的地方 五种并行机结构特性一览表 动态网络之单一总线 连接处理器 存储模块和I O设备等的一组导线和插座 在主设备 处理器 和从设备 存储器 之间传递数据 三个特征 公用总线以分时工作为基础 各处理器模块分时共享总线带宽 即在同一个时钟周期 至多只有一个设备能占有总线 总线带宽 总线主频 总线宽度 例如假设主板的总线频率为150MHz 总线宽度为64位 则该总线的带宽为1 2GB s 采用公平的监听协议与仲裁算法 以确定在某个时刻选择哪个设备占有总线 动态网络之交叉开关 所有结点通过交叉开关阵列相互连接 每个交叉开关均为其中两个结点之间提供一条专用连接通路 同时 任意两个结点之间也能找到一个交叉开关 在它们之间建立专用连接通路 三个特征 结点之间的连接 交叉开关一般构成NxN阵列 但在每一行和每一列同时只能有一个交叉点开关处于 开 状态 从而它同时只能接通N对结点 一般地 结点和存储器模块作为连接的对象 分别分布在拓扑结构的两侧 结构为NxN的交叉开关只能提供2xN个端口 这限制了它在大规模并行机中的应用 交叉开关一般仅适合数个处理器的情形 或者 在结点内部为处理器和存储器之间提供快速高效的通道 动态网络之例子 动态网络之例子 2 并行计算机结构模型比较 PVP与SMP 均为单地址空间 在是否带Cache 互连网络要求 I O并行度方面不同 MPP与DSM 在多 单地址空间 通信方式 Cache一致性方面不同 MPP与COW 在节点结构 互连网络要求 耦合程度方面不同 五种并行机结构特性一览表 一致性问题 包括高速缓存 cache 一致性 存储一致性两个方面 1 高速缓存一致性指私有Cache中共享数据的副本和共享存储器中共享数据之间的一致性 特征 多处理器对同一存储单元的操作引起的一致性 原因 Cache采用写回法更新策略所引起 2 存储一致性指多个处理器程序的执行次序与共享存储器中共享数据存取次序之间的一致性 特征 不同处理器对不同存储单元的操作引起的一致性 原因 处理器内部优化执行效率 如异步流水 所致 存储一致性例子 a A 1b printB C c B 1d printA C e C 1f printA 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结构 高