并行计算

Size: px

Start display at page:

Download "并行计算"

寻山
5 years ago
Views:

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

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

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

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

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

6 并行计算机结构模型 (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

7 并行计算机结构模型 (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

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

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

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

11 并行计算机体系合一结构 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

12 五种结构特性一览表属性 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

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

14 并行计算机访存模型 (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

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

16 并行计算机访存模型 (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

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

18 构筑并行机系统的不同存储结构 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

19 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

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

21 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

22 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

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

24 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

25 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

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

27 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

28 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

29 The coherence problem Core 1 writes to x, setting it to 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

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

31 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

32 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

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

34 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

分层并行计算模型 Loyered Models of Parallel Computation

分层并行计算模型 Loyered Models of Parallel Computation 并行计算 Parallel Computing 主讲人孙广中 Spring, 2018 2018/3/19 1 / 43 思考题 1 问题 1: 谈谈你所知道的高性能计算与云计算的区别? 问题 2: 并行程序的描述应如何? 与串行程序有什么不同? 问题 3: 如何并行地尽快求解 n 个元素的最大值或排序? 2018/3/19 2 / 43 并行计算结构算法编程 ( 第三版 ) 第一篇并行计算硬件平台