并行算法实践 上篇 并行程序设计导论.

Presentation on theme: "并行算法实践 上篇 并行程序设计导论."— Presentation transcript:

1 并行算法实践 上篇 并行程序设计导论

2 并行算法实践 上篇 并行程序设计导论 单元I 并行程序设计基础 单元II 并行程序编程指南 单元III 并行程序开发方法
并行算法实践 上篇 并行程序设计导论 单元I 并行程序设计基础 单元II 并行程序编程指南 单元III 并行程序开发方法 国家高性能计算中心（合肥） 2018/12/8

3 单元I 并行程序设计基础 第一章 并行计算机系统与结构模型 第二章 PC机群的搭建 第三章 并行程序设计简介 国家高性能计算中心（合肥）
2018/12/8

4 第一章 并行计算机系统与结构模型 1.1 典型并行计算机系统简介 1.2 当代并行计算机体系结构 1.3 小结 1.1.1 阵列处理机
1.1.2 向量处理机 1.1.3 共享存储多处理机 1.1.4 分布存储多计算机 1.1.5 分布共享存储多处理机 1.2 当代并行计算机体系结构 1.2.1 并行计算机体系结构模型 1.2.2 并行计算机存储结构模型 1.2.3 分布式高速缓存与主存体系结构 1.3 小结 国家高性能计算中心（合肥） 2018/12/8

5 典型并行计算机系统 阵列处理机 向量处理机 共享存储多处理机 分布存储多计算机 分布存储 共享存储 流水线 并行向量机 紧耦合多机系统
同构对称对机系统 DSM/SVM 国家高性能计算中心（合肥） 2018/12/8

6 阵列处理机的两种基本结构 (a)分布存储阵列机 (b)共享存储阵列机 国家高性能计算中心（合肥） 2018/12/8

7 阵列处理机的特点 SIMD－单指令多数据流机 利用资源重复开拓计算空间的并行 同步计算－－所有PE执行相同操作
适于特定问题（如有限差分、矩阵运算等）求解 国家高性能计算中心（合肥） 2018/12/8

8 Cray-1的向量处理 国家高性能计算中心（合肥） 2018/12/8

9 共享存储的多处理机 MIMD－多指令多数据流机 单一的共享地址空间 易于编程、难于扩展 存储访问可成为性能瓶颈 紧耦合与同构对称方式
国家高性能计算中心（合肥） 2018/12/8

10 典型的紧耦合多处理机系统 国家高性能计算中心（合肥） 2018/12/8

11 Balance同构对称多处理机系统 国家高性能计算中心（合肥） 2018/12/8

12 分布存储多计算机 松散耦合多机系统 节点独立（可有局存、IO设备等） 易于扩展 多地址空间 消息传递通信界面 难于编程
国家高性能计算中心（合肥） 2018/12/8

13 Intel Paragon系统框图 国家高性能计算中心（合肥） 2018/12/8

14 分布共享存储多处理机 分布共享存储DSM－Distributed Shared Memory
将物理上分布的存储系统，通过硬件和软件的办法，向用户提供一个单一的全局地址空间 易于编程 易于扩展 国家高性能计算中心（合肥） 2018/12/8

15 并行计算机体系结构 单指令多数据流机SIMD（Single-Instruction Multiple-Data）；
并行向量处理机PVP（Parallel Vector Processor）； 对称多处理机SMP（Symmetric Multiprocessor）； 大规模并行处理机MPP(Massively Parallel Processor)； 工作站机群COW(Cluster of Workstation) 分布式共享存储DSM(Distributed Shared Memory)多处理机。 国家高性能计算中心（合肥） 2018/12/8

16 并行计算机体系结构模型 国家高性能计算中心（合肥） 2018/12/8

17 对称多处理机SMP(1) 例子：SGI Power Challenge, DEC Alpha Server,Dawning 1
SMP: 采用商用微处理器，通常有片上和片外Cache，基于总线连接，集中式共享存储，UMA结构 例子：SGI Power Challenge, DEC Alpha Server,Dawning 1 国家高性能计算中心（合肥） 2018/12/8

18 对称多处理机SMP(2) 优点 问题 对称性 单地址空间，易编程性，动态负载平衡，无需显示数据分配
高速缓存及其一致性，数据局部性，硬件维持一致性 低通信延迟，Load/Store完成 问题 欠可靠，BUS,OS,SM 通信延迟（相对于CPU），竞争加剧 慢速增加的带宽（MB double/3年,IOB更慢） 不可扩放性---〉CC-NUMA 国家高性能计算中心（合肥） 2018/12/8

19 大规模并行机MPP IBM SP2 Dawning 1000 成百上千个处理器组成的大规模计算机系统，规模是变化的。
NORMA结构，高带宽低延迟定制互连。 可扩放性：Mem, I/O,平衡设计 系统成本：商用处理器，相对稳定的结构，SMP,分布 通用性和可用性：不同的应用，PVM,MPI,交互，批处理，互连对用户透明，单一系统映象，故障 通信要求 存储器和I/O能力 例子：Intel Option Red IBM SP2 Dawning 1000 国家高性能计算中心（合肥） 2018/12/8

20 典型MPP系统特性比较 国家高性能计算中心（合肥） 2018/12/8 MPP模型 Intel/Sandia ASCI Option Red
IBM SP2 SGI/Cray Origin2000 一个大型样机的配置 9072个处理器，1.8Tflop/s(NSL) 400个处理器，100Gflop/s(MHPCC) 128个处理器，51Gflop/s(NCSA) 问世日期 1996年12月 1994年9月 1996年10月 处理器类型 200MHz, 200Mflop/s Pentium Pro 67MHz，267Mflop/s POWER2 200MHz，400Mflop/s MIPS R10000 节点体系结构 和数据存储器 2个处理器，32到256MB主存，共享磁盘 1个处理器，64MB到2GB本地主存，1GB到14.5GB本地磁盘 2个处理器，64MB到256MB分布共享主存和共享磁盘 互连网络和主存模型 分离两维网孔，NORMA 多级网络，NORMA 胖超立方体网络，CC-NUMA 节点操作系统 轻量级内核（LWK） 完全AIX（IBM UNIX） 微内核Cellular IRIX 自然编程机制 基于PUMA Portals的MPI MPI和PVM Power C， Power Fortran 其他编程模型 Nx，PVM，HPF HPF，Linda MPI，PVM 国家高性能计算中心（合肥） 2018/12/8

21 机群型大规模并行机SP2 设计策略： 系统结构： 机群体系结构 标准环境 标准编程模型 系统可用性 精选的单一系统映像
高性能开关 HPS 多级Ω网络 宽节点、窄节点和窄节点2 国家高性能计算中心（合肥） 2018/12/8

22 工作站机群COW 分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核
优点： 投资风险小 系统结构灵活 性能/价格比高 能充分利用分散的计算资源 可扩放性好 问题 通信性能 并行编程环境 例子：Berkeley NOW，Alpha Farm, FXCOW P/C M MIO NIC D LAN 国家高性能计算中心（合肥） 2018/12/8

23 典型的机群系统 典型的机群系统特点一览表 名称 系统特点 Princeton:SHRIMP
PC商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信 Karsruhe:Parastation 用于分布并行处理的有效通信网络和软件开发 Rice:TreadMarks 软件实现分布共享存储的工作站机群 Wisconsin:Wind Tunnel 在经由商用网络互连的工作站机群上实现分布共享存储 Chica、Maryl、Penns:NSCP 国家可扩放机群计划：在通过因特网互连的3个本地机群系统上进行元计算 Argonne:Globus 在由ATM连接的北美17个站点的WAN上开发元计算平台和软件 Syracuse:WWVM 使用因特网和HPCC技术，在世界范围的虚拟机上进行高性能计算 HKU:Pearl Cluster 研究机群在分布式多媒体和金融数字库方面的应用 Virgina:Legion 在国家虚拟计算机设施上开发元计算软件 国家高性能计算中心（合肥） 2018/12/8

24 SMP\MPP\机群比较 系统特征 SMP MPP 机群 节点数量(N) O(10) O(100)-O(1000) O(100)
节点复杂度 中粒度或细粒度 细粒度或中粒度 中粒度或粗粒度 节点间通信 共享存储器 消息传递 或共享变量（有DSM时） 节点操作系统 1 N(微内核) 和1个主机OS(单一) N (希望为同构) 支持单一系统映像 永远 部分 希望 地址空间 单一 多或单一（有DSM时） 多个 作业调度 单一运行队列 主机上单一运行队列 协作多队列 网络协议 非标准 标准或非标准 可用性 通常较低 低到中 高可用或容错 性能/价格比 一般 高 互连网络 总线/交叉开关 定制 商用 国家高性能计算中心（合肥） 2018/12/8

25 五种结构特性一览表 属性 PVP SMP MPP DSM COW 结构类型 MIMD 处理器类型 专用定制 商用 互连网络 定制交叉 开关
总线、交叉开关 定制网络 商用网络 以太,ATM 通信机制 共享变量 消息传递 地址空间 单地址空间 多地址空间 系统存储器 集中共享 分布非共享 分布共享 访存模型 UMA NORMA NUMA 代表机器 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/12/8

26 并行计算机访存模型 均匀存储访问模型－ UMA 非均匀存储访问模型－ NUMA 全高速缓存访问模型－COMA
高速缓存一致性非均匀存储访问模型－CC-NUMA 非远程存储访问模型－NORMA 国家高性能计算中心（合肥） 2018/12/8

27 UMA访存模型 UMA（Uniform Memory Access）模型是均匀存储访问模型的简称。其特点是：
物理存储器被所有处理器均匀共享； 所有处理器访问任何存储字取相同的时间； 每台处理器可带私有高速缓存； 外围设备也可以一定形式共享。 国家高性能计算中心（合肥） 2018/12/8

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

29 COMA访存模型 COMA(Cache-Only Memory Access)模型是全高速缓存存储访问的简称。其特点是：
各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间； 利用分布的高速缓存目录D进行远程高速缓存的访问; COMA中的高速缓存容量一般都大于2 级高速缓存容量； 使用COMA时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用到它们的地方。 国家高性能计算中心（合肥） 2018/12/8

30 CC-NUMA访存模型 CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是高速缓存一致性非均匀存储访问模型的简称。其特点是： 大多数使用基于目录的高速缓存一致性协议； 保留SMP结构易于编程的优点，也改善常规SMP的可扩放性； CC-NUMA实际上是一个分布共享存储的DSM多处理机系统； 它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。 国家高性能计算中心（合肥） 2018/12/8

31 NORMA访存模型 NORMA（No-Remote Memory Access）模型是非远程存储访问模型的简称。NORMA的特点是：
所有存储器是私有的； 绝大数NUMA都不支持远程存储器的访问； 在DSM中，NORMA就消失了。 国家高性能计算中心（合肥） 2018/12/8

32 构筑并行机系统的不同存储结构 国家高性能计算中心（合肥） 2018/12/8

33 分布式存储中的共享与非共享存储 在并行计算机中，一个物理上分布的存储器在逻辑上可以被共享与非共享。
如果系统内任何处理器上的进程都能直接地访问系统内任何本地存储器和远程存储器，则就称该系统具有共享存储结构。注意，所谓直接访问系指能用load和store之类的指令存取整个系统内的任何存储单元。 如果系统内任何处理器上的进程不能直接对远程存储器用load和store之类的指令进行访问，而必须借助于运行时软件层和用户可调用的例程库来实现，则就称该系统具有非共享存储结构。 国家高性能计算中心（合肥） 2018/12/8

34 分布存储中四种不同的远程访问 国家高性能计算中心（合肥） 2018/12/8

35 五种分布存储结构的特性比较 特性 NORMA NCC-NUMA SC-NUMA CC-NUMA COMA 共享单位（粒度） 变量 页
页/高速缓存行 高速缓存行 一致性维护 由用户应用实现 由用户级软件实现 由OS或运行时系统实现 在高速缓存行级由硬件实现 复制和迁移的实现 由用户在变量级实现 由OS或运行时系统在页面级实现 由OS在页面级实现 由硬件在高速缓存行级实现 假共享现象 无 有 国家高性能计算中心（合肥） 2018/12/8