并行计算 Parallel Computing 主讲人 孙广中 Spring, 2018 2018/3/19 1 / 43
思考题 1 问题 1: 谈谈你所知道的高性能计算与云计算的区别? 问题 2: 并行程序的描述应如何? 与串行程序有什么不同? 问题 3: 如何并行地尽快求解 n 个元素的最大值或排序? 2018/3/19 2 / 43
并行计算 结构 算法 编程 ( 第三版 ) 第一篇并行计算硬件平台 : 并行计算机 第一章并行计算与并行计算机结构模型 第二章并行计算机系统互连与基本通信操作 第三章典型并行计算机系统介绍 第四章并行计算性能评测 2018/3/19 3 / 43
第一章并行计算及并行机结构模型 1.1 计算与计算机科学 1.2* 单处理机与指令级并行 1.3* 多核处理器与线程级并行 1.4 并行计算机体系结构 1.4.1 并行计算机结构模型 1.4.2 并行计算机访存模型 1.4.3* 并行计算机存储模型 1.5 并行计算概述 2018/3/19 4 / 43
并行计算 计算科学 计算需求 并行计算 : 并行机上所作的计算, 又称高性能计算或超级计算 计算科学 : 计算物理 计算化学 计算生物等 计算是科学发现的三大支柱之一 科学与工程问题的需求 : 气象预报 油藏模拟 核武器数值模拟 航天器设计 基因测序等 美国 ASCI 计划 (1996): 核武器数值模拟 需求类型 : 计算密集 数据密集 网络密集 2018/3/19 5 / 43
第一章并行计算及并行机结构模型 1.1 计算与计算机科学 1.2* 单处理机与指令级并行 1.3* 多核处理器与线程级并行 1.4 并行计算机体系结构 1.4.1 并行计算机结构模型 1.4.2 并行计算机访存模型 1.4.3* 并行计算机存储模型 1.5 并行计算概述 2018/3/19 6 / 43
并行计算机结构模型 (1) VP VP VP P/C P/C P/C MB P/C LM MB P/C LM 交叉开关 总线或交叉开关 NIC NIC SM SM SM SM SM I/O (a)pvp (b)smp 定制网络 (c)mpp MB P/C LM DIR MB P/C LM DIR MB P/C M Bridge MB P/C M Bridge NIC NIC LD IOB LD IOB NIC NIC 定制网络 (d)dsm 商品网络 ( 以太网,ATM,etc.) (e)cow 2018/3/19 7 / 43
并行计算机结构模型 (2) SM SM SM DSM DSM DSM SMP SMP SMP MPP MPP MPP SAN/LAN SAN/LAN (f) SMP-Cluster (g) DSM-Cluster SM LM DSM SMP MPP MPP WAN (h) Grid (Cluster of Clusters) 2018/3/19 8 / 43
并行计算机结构模型 (3) SISD computer -Von Neumann's model SIMD computer 2018/3/19 9 / 43
并行计算机结构模型 (4) Symmetric multiprocessor MIMD-SM Massively parallel processor MIMD-DM 2018/3/19 10 / 43
并行计算机结构模型 (5) Cluster of workstations MIMD-DM 2018/3/19 11 / 43
并行计算机结构模型 (6) 五种结构小结 属性 PVP SMP MPP DSM COW 结构类型 MIMD MIMD MIMD MIMD MIMD 处理器类型专用定制商用商用商用商用 互连网络 定制交叉开关 总线 交叉开 关 定制网络 定制网络 商用网络 ( 以 太 ATM) 通信机制共享变量共享变量消息传递共享变量消息传递 地址空间单地址空间单地址空间多地址空间单地址空间多地址空间 系统存储器集中共享集中共享分布非共享分布共享分布非共享 访存模型 UMA UMA NORMA NUMA NORMA 代表机器 Cray C-90, Cray T-90, 银河 1 号 IBM R50, SGI Power Challenge, 曙光 1 号 Intel Paragon, IBMSP2, 曙光 1000/2000 Stanford DASH,Cray T 3D Berkeley NOW,Alpha Farm 2018/3/19 12 / 43
并行计算机访存模型 (1) UMA UMA(Uniform Memory Access) 模型是均匀存储访问模型的简称 其特点是 : 物理存储器被所有处理器均匀共享 ; 所有处理器访问任何存储字取相同的时间 ; 每台处理器可带私有高速缓存 ; 外围设备也可以一定形式共享 处理器 P 1 P 2 P n 系统互连 ( 总线, 交叉开关, 多级网络 ) I/O SM 1 SM m 共享存储器 2018/3/19 13 / 43
并行计算机访存模型 (2) NUMA NUMA(Nonuniform Memory Access) 模型是非均匀存储访问模型的简称 特点是 : 被共享的存储器在物理上是分布在所有的处理器中的, 其所有本地存储器的集合就组成了全局地址空间 ; 处理器访问存储器的时间是不一样的 ; 访问本地存储器 LM 或群内共享存储器 CSM 较快, 而访问外地的存储器或全局共享存储器 GSM 较慢 ( 此即非均匀存储访问名称的由来 ); 每台处理器照例可带私有高速缓存, 外设也可以某种形式共享 2018/3/19 14 / 43
并行计算机访存模型 (2) NUMA GSM GSM GSM 全局互连网络 P CSM P CSM LM 1 LM 2 P 1 P 2 互连网络 P P C I N CSM CSM P P C I N CSM CSM LM n P n 群 1 群 N (a) 共享本地存储模型 (b) 层次式机群模型 2018/3/19 15 / 43
并行计算机访存模型 (3) COMA COMA(Cache-Only Memory Access) 模型是全高速缓存存储访问的简称 其特点是 : 各处理器节点中没有存储层次结构, 全部高速缓存组成了全局地址空间 ; 利用分布的高速缓存目录 D 进行远程高速缓存的访问 ; COMA 中的高速缓存容量一般都大于 2 级高速缓存容量 ; 使用 COMA 时, 数据开始时可任意分配, 因为在运行时它最终会被迁移到要用到它们的地方 2018/3/19 16 / 43
并行计算机访存模型 (3) COMA 互连网络 D D D C C C P P P 2018/3/19 17 / 43
并行计算机访存模型 (4) CC-NUMA CC-NUMA(Coherent-Cache Nonuniform Memory Access) 模型是高速缓存一致性非均匀存储访问模型的简称 其特点是 : 大多数使用基于目录的高速缓存一致性协议 ; 保留 SMP 结构易于编程的优点, 也改善常规 SMP 的可扩放性 ; CC-NUMA 实际上是一个分布共享存储的 DSM 多处理机系统 ; 它最显著的优点是程序员无需明确地在节点上分配数据, 系统的硬件和软件开始时自动在各节点分配数据, 在运行期间, 高速缓存一致性硬件会自动地将数据迁移至要用到它的地方 2018/3/19 18 / 43
并行计算机访存模型 (4) CC-NUMA P/C 节点 1 P/C 总线或交叉开关 Mem P/C 节点 N P/C 总线或交叉开关 Mem I/O NIC,DIR,RC I/O NIC,DIR,RC 系统互连网路 2018/3/19 19 / 43
并行计算机访存模型 (5) NORMA...... NORMA(No-Remote Memory Access) 模型是非远程存储访问模型的简称 NORMA 的特点是 : 所有存储器是私有的, 仅能由其处理器访问 ; 绝大数 NORMA 都不支持远程存储器的访问 ; M M P P... M P M P M P 消息传递互连网络 ( 网络, 环网, 超立方, 立方环等 ) P M P M P M P M... P M 2018/3/19 20 / 43
并行机系统的不同存储结构 MIMD 多处理机 ( 单地址空间共享存储器 ) NORMA 多计算机 ( 多地址空间非共享存储器 ) 中央存储器 UMA NUMA 分布存储器 Cluster PVP (Cray T90) SMP (IBM SP2,DEC TruCluster Tandem Hymalaya,HP, Microsoft Wolfpack,etc) ( 松散耦合 ) MPP (Intel TFLOPS) ( 紧耦合 ) (Intel SHV,SunFire,DEC 8400, SGI PowerChallenge,IBMR60,etc.) COMA (KSR-1,DDM) CC-NUMA NCC-NUMA (Stanford Dash, SGI Origin 2000,Sequent NUMA-Q, HP/Convex Exemplar) (Cray T3E) DSM (TreadMarks, Wind Tunnel, IVY,Shrimp, etc.) 2018/3/19 21 / 43
第一章并行计算及并行机结构模型 1.1 计算与计算机科学 1.2* 单处理机与指令级并行 1.3* 多核处理器与线程级并行 1.4 并行计算机体系结构 1.4.1 并行计算机结构模型 1.4.2 并行计算机访存模型 1.4.3* 并行计算机存储模型 1.5 并行计算概述 2018/3/19 22 / 43
The Landscape of Parallel Computing Research A view from Berkeley 2006 年的白皮书 计算数学 计算物理 计算机软件 计算机硬件 计算机算法 电子学等多个学科 20 余名教授, 半年时间研讨 http://view.eecs.berkeley.edu/wiki/main_page 2018/3/19 23 / 43
A view from Berkeley 2018/3/19 24 / 43
高性能计算应用需求 2018/3/19 25 / 43
超级计算机性能的发展趋势 2018/3/19 26 / 43
作业 1( 研究生必做, 本科生选做 ) 1. 课本第 35 页 1.11 题 并行计算应用调研 2. 根据调研的应用需求, 预算 150 万人民币购置计算资源 请确定购买的机器配置 提交截止时间 :2018 年 3 月 28 日 ( 周二 )22:00 提交方式 :http://home.ustc.edu.cn/~zzh04/pc.html 2018/3/19 27 / 43
思考题 2 与串行计算相比, 并行机系统的存储结构更为复杂 试描述缓存一致性 ( coherence) 问题 请考虑可以如何解决这个问题 2018/3/19 28 / 43
Core 1 Core 2 Core 3 Core 4 Main memory x=15213 multi-core chip 2018/3/19 29 / 43
Core 1 reads x Core 1 Core 2 Core 3 Core 4 x=15213 Main memory x=15213 multi-core chip 2018/3/19 30 / 43
Core 2 reads x Core 1 Core 2 Core 3 Core 4 x=15213 x=15213 Main memory x=15213 multi-core chip 2018/3/19 31 / 43
Core 1 writes to x, setting it to 21660 Core 1 Core 2 Core 3 Core 4 x=21660 x=15213 Main memory x=21660 assuming write-through s multi-core chip 2018/3/19 32 / 43
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 2018/3/19 33 / 43
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 2018/3/19 34 / 43
Inter-core bus Core 1 Core 2 Core 3 Core 4 Main memory multi-core chip inter-core bus 2018/3/19 35 / 43
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. 2018/3/19 36 / 43
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 2018/3/19 37 / 43
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 2018/3/19 38 / 43
The coherence problem After invalidation: Core 1 Core 2 Core 3 Core 4 x=21660 Main memory x=21660 multi-core chip 2018/3/19 39 / 43
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 2018/3/19 40 / 43
Alternative to invalidate protocol: update protocol Core 1 writes x=21660: Core 1 Core 2 Core 3 Core 4 x=21660 x=21660 UPDATED broadcasts updated value Main memory x=21660 assuming write-through s multi-core chip inter-core bus 2018/3/19 41 / 43
Which do you think is better? Invalidation or update? 2018/3/19 42 / 43
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 2018/3/19 43 / 43