并行计算

并行计算 arallel Computing 主讲人孙广中 Spring, 2016

并行计算 结构 算法 编程 第一篇并行计算的基础 第一章并行计算与并行计算机结构模型 第二章并行计算机系统互连与基本通信操作 第三章典型并行计算机系统介绍 第四章并行计算性能评测 2

第一章并行计算及并行机结构模型 1.1 计算与计算机科学 1.2* 单处理机与指令级并行 1.3* 多核处理器与线程级并行 1.4 并行计算机体系结构 1.4.1 并行计算机结构模型 1.4.2 并行计算机访存模型 1.4.3 Intel 和 AMD 多核 CU 架构 3

并行计算 计算科学 计算需求 并行计算 : 并行机上所作的计算, 又称高性能计算或超级计算 计算科学 : 计算物理 计算化学 计算生物等 计算是科学发现的三大支柱之一 科学与工程问题的需求 : 气象预报 油藏模拟 核武器数值模拟 航天器设计 基因测序等 需求类型 : 计算密集 数据密集 网络密集 美国 ASCI 计划 (1996): 核武器数值模拟 4

第一章并行计算及并行机结构模型 1.1 计算与计算机科学 1.2* 单处理机与指令级并行 1.3* 多核处理器与线程级并行 1.4 并行计算机体系结构 1.4.1 并行计算机结构模型 1.4.2 并行计算机访存模型 1.4.3 Intel 和 AMD 多核 CU 架构 5

并行计算机结构模型 (1) V V V /C /C /C MB /C LM MB /C LM 交叉开关 总线或交叉开关 NIC NIC SM SM SM SM SM I/O (a)v (b)sm 定制网络 (c)m MB /C LM DIR MB /C LM DIR MB /C M Bridge MB /C M Bridge NIC NIC LD IOB LD IOB NIC NIC 定制网络 (d)dsm 商品网络 ( 以太网,ATM,etc.) (e)cow 6

并行计算机结构模型 (2) SM SM SM DSM DSM DSM SM SM SM M M M SAN/LAN SAN/LAN (f) SM-Cluster (g) DSM-Cluster SM LM DSM SM M M WAN (h) Grid (Cluster of Clusters) 7

并行计算机结构模型 (3) SISD computer -Von Neumann's model SIMD computer 8

并行计算机结构模型 (4) Symmetric multiprocessor MIMD-SM Massively parallel processor MIMD-DM 9

并行计算机结构模型 (5) Cluster of workstations MIMD-DM 10

并行计算机体系合一结构 SM M DSM 和 COW 并行结构渐趋一致 C M D 节点 1 大量的节点通过高速网络互连起来 节点遵循 Shell 结构 : 用专门定制的 Shell 电路将商用微处理器和节点的其它部分 ( 包括板级 Cache 局存 NIC 和 DISK) 连接起来 优点是 CU 升级只需要更换 Shell Shell NIC 互连网络 (a) 无共享 节点 N NIC C M 节点 1 Shell NIC 互连网络 共享磁盘 (b) 共享磁盘 节点 N NIC C Shell 共享存储器 互连网络 C Shell (c) 共享存储 共享磁盘 11

五种结构特性一览表 属性 V SM M DSM COW 结构类型 MIMD MIMD MIMD MIMD MIMD 处理器类型专用定制商用商用商用商用 互连网络 定制交叉开关 总线 交叉开 关 定制网络 定制网络 商用网络 ( 以 太 ATM) 通信机制共享变量共享变量消息传递共享变量消息传递 地址空间单地址空间单地址空间多地址空间单地址空间多地址空间 系统存储器集中共享集中共享分布非共享分布共享分布非共享 访存模型 UMA UMA NORMA NUMA NORMA 代表机器 Cray C-90, Cray T-90, 银河 1 号 IBM R50, SGI ower Challenge, 曙光 1 号 Intel aragon, IBMS2, 曙光 1000/2000 Stanford DASH,Cray T 3D Berkeley NOW,Alpha Farm 12

并行计算机访存模型 (1) UMA(Uniform Memory Access) 模型是均匀存储访问模型的简称 其特点是 : 物理存储器被所有处理器均匀共享 ; 所有处理器访问任何存储字取相同的时间 ; 每台处理器可带私有高速缓存 ; 外围设备也可以一定形式共享 处理器 1 2 n 系统互连 ( 总线, 交叉开关, 多级网络 ) I/O SM 1 SM m 共享存储器 13

并行计算机访存模型 (2) NUMA(Nonuniform Memory Access) 模型是非均匀存储访问模型的简称 特点是 : 被共享的存储器在物理上是分布在所有的处理器中的, 其所有本地存储器的集合就组成了全局地址空间 ; 处理器访问存储器的时间是不一样的 ; 访问本地存储器 LM 或群内共享存储器 CSM 较快, 而访问外地的存储器或全局共享存储器 GSM 较慢 ( 此即非均匀存储访问名称的由来 ); 每台处理器照例可带私有高速缓存, 外设也可以某种形式共享 GSM GSM GSM 全局互连网络 CSM CSM LM 1 1 LM 2 2 互连网络 C I N CSM CSM C I N CSM CSM LM n n 群 1 群 N (a) 共享本地存储模型 (b) 层次式机群模型 14

并行计算机访存模型 (3) COMA(Cache-Only Memory Access) 模型是全高速缓存存储访问的简称 其特点是 : 各处理器节点中没有存储层次结构, 全部高速缓存组成了全局地址空间 ; 利用分布的高速缓存目录 D 进行远程高速缓存的访问 ; COMA 中的高速缓存容量一般都大于 2 级高速缓存容量 ; 使用 COMA 时, 数据开始时可任意分配, 因为在运行时它最终会被迁移到要用到它们的地方 互连网络 D D D C C C 15

并行计算机访存模型 (4) CC-NUMA(Coherent-Cache Nonuniform Memory Access) 模型是高速缓存一致性非均匀存储访问模型的简称 其特点是 : 大多数使用基于目录的高速缓存一致性协议 ; 保留 SM 结构易于编程的优点, 也改善常规 SM 的可扩放性 ; CC-NUMA 实际上是一个分布共享存储的 DSM 多处理机系统 ; 它最显著的优点是程序员无需明确地在节点上分配数据, 系统的硬件和软件开始时自动在各节点分配数据, 在运行期间, 高速缓存一致性硬件会自动地将数据迁移至要用到它的地方 /C 节点 1 /C 总线或交叉开关 Mem /C 节点 N /C 总线或交叉开关 Mem I/O NIC,DIR,RC I/O NIC,DIR,RC 系统互连网路 16

并行计算机访存模型 (5) NORMA(No-Remote Memory Access) 模型是非远程存储访问模型的简称 NORMA 的特点是 : 所有存储器是私有的, 仅能由其处理器访问 ; 绝大数 NORMA 都不支持远程存储器的访问 ; M M... M M M... 消息传递互连网络 ( 网络, 环网, 超立方, 立方环等 ) M... M M M... M 17

构筑并行机系统的不同存储结构 MIMD 多处理机 ( 单地址空间共享存储器 ) NORMA 多计算机 ( 多地址空间非共享存储器 ) 中央存储器 UMA NUMA 分布存储器 Cluster V (Cray T90) SM (IBM S2,DEC TruCluster Tandem Hymalaya,H, Microsoft Wolfpack,etc) ( 松散耦合 ) M (Intel TFLOS) ( 紧耦合 ) (Intel SHV,SunFire,DEC 8400, SGI owerchallenge,ibmr60,etc.) COMA (KSR-1,DDM) CC-NUMA NCC-NUMA (Stanford Dash, SGI Origin 2000,Sequent NUMA-Q, H/Convex Exemplar) (Cray T3E) DSM (TreadMarks, Wind Tunnel, IVY,Shrimp, etc.) 18

The coherence problem 一致性问题 Since we have private s: How to keep the data consistent across s? Each core should perceive the memory as a monolithic array, shared by all the cores 19

The coherence problem Suppose variable x initially contains 15213 Core 1 Core 2 Core 3 Core 4 Main memory x=15213 multi-core chip 20

The coherence problem Core 1 reads x Core 1 Core 2 Core 3 Core 4 x=15213 Main memory x=15213 multi-core chip 21

The coherence problem Core 2 reads x Core 1 Core 2 Core 3 Core 4 x=15213 x=15213 Main memory x=15213 multi-core chip 22

The coherence problem Core 1 writes to x, setting it to 21660 Core 1 Core 2 Core 3 Core 4 x=21660 x=15213 multi-core chip Main memory x=21660 assuming write-through s 23

The coherence problem Core 2 attempts to read x gets a stale copy Core 1 Core 2 Core 3 Core 4 x=21660 x=15213 Main memory x=21660 multi-core chip 24

Solutions for coherence This is a general problem with multiprocessors, not limited just to multi-core There exist many solution algorithms, coherence protocols, etc. A simple solution: invalidation-based protocol with snooping 25

Inter-core bus Core 1 Core 2 Core 3 Core 4 Main memory multi-core chip inter-core bus 26

Invalidation protocol with snooping Invalidation: If a core writes to a data item, all other copies of this data item in other s are invalidated Snooping: All cores continuously snoop (monitor) the bus connecting the cores. 27

The coherence problem Revisited: Cores 1 and 2 have both read x Core 1 Core 2 Core 3 Core 4 x=15213 x=15213 Main memory x=15213 multi-core chip 28

The coherence problem Core 1 writes to x, setting it to 21660 Core 1 Core 2 Core 3 Core 4 x=21660 x=15213 sends invalidation request Main memory x=21660 INVALIDATED assuming write-through s multi-core chip inter-core bus 29

The coherence problem After invalidation: Core 1 Core 2 Core 3 Core 4 x=21660 Main memory x=21660 multi-core chip 30

The coherence problem Core 2 reads x. Cache misses, and loads the new copy. Core 1 Core 2 Core 3 Core 4 x=21660 x=21660 Main memory x=21660 multi-core chip 31

Alternative to invalidate protocol: update protocol Core 1 writes x=21660: Core 1 Core 2 Core 3 Core 4 x=21660 x=21660 UDATED broadcasts updated value Main memory x=21660 assuming write-through s multi-core chip inter-core bus 32

Which do you think is better? Invalidation or update? 33

Invalidation vs update Multiple writes to the same location invalidation: only the first time update: must broadcast each write (which includes new variable value) Invalidation generally performs better: it generates less bus traffic 34