Microsoft PowerPoint - PC1.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - PC1.pptx"

念就王
5 years ago
Views:

1 并行计算结构算法编程主讲教师 : 谢磊

2 并行计算结构算法编程第一篇并行计算的基础第一章并行计算机系统及其结构模型第二章当代并行机系统 :SMP MPP 和 Cluster 第三章并行计算性能评测第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程 2

3 并行计算结构算法编程第三篇并行数值算法第八章基本通信操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换第四篇并行程序设计第十二章并行程序设计基础第十三章并行程序设计模型和共享存储系统编程第十四章分布存储系统并行编程第十五章并行程序设计环境与工具 3

4 第一章并行计算机系统及结构模型 1.1 并行计算并行计算与计算科学当代科学与工程问题的计算需求 1.2 并行计算机系统互连系统互连静态互联网络动态互连网络标准互联网络 1.3 并行计算机系统结构并行计算机结构模型并行计算机访存模型 4

5 并行计算并行计算并行机上所作的计算, 又称高性能计算或超级计算 Parallel Computing:Multiple processes cooperating to solve a single problem. A Parallel Computer is a collection of processing elements that communicate and cooperate to solve large problem fast [David E. Culler] 三大科学计算科学理论科学与实验科学计算科学计算物理计算化学计算生物等 5

6 并行计算科学与工程问题的需求气象预报油藏模拟核武器数值模拟航天器设计基因测序等需求类型计算密集数据密集网络密集美国 HPCC 计划 : 重大挑战性课题,3T 性能美国 Petaflops 研究项目 :Pflop/s 美国 ASCI 计划 : 核武器数值模拟 6

7 高性能计算机 Period Supercomputer Peak speed Location U. of Pennsylvania ENIAC 50 kflops Aberdeen Proving Ground, Maryland, USA MIT TX-0 83 kflops Massachusetts Inst. of Technology, Lexington, Massachusetts, USA IBM SAGE 400 kflops U.S. Air Force, USA UNIVAC LARC 500 kflops Lawrence Livermore National Laboratory, California, USA IBM 7030 "Stretch" 1.2 MFLOPS Los Alamos National Laboratory, New Mexico, USA CDC MFLOPS Lawrence Livermore National Laboratory, California, USA CDC MFLOPS Lawrence Livermore National Laboratory, California, USA CDC Star MFLOPS Lawrence Livermore National Laboratory, California, USA Burroughs ILLIAC IV 150 MFLOPS NASA Ames Research Center, California, USA Cray MFLOPS Los Alamos National Laboratory, New Mexico, USA (80+ sold worldwide) 7

8 高性能计算机 CDC Cyber MFLOPS (numerous sites worldwide) Cray X-MP/4 941 MFLOPS Los Alamos & Lawrence Livermore Nat. Laboratories, Battelle, Boeing M GFLOPS Scientific Research Institute of Computer Complexes, Moscow, USSR Cray-2/8 3.9 GFLOPS Lawrence Livermore National Laboratory, California, USA ETA10-G/ GFLOPS Florida State University, Florida, USA Thinking Machines CM GFLOPS Los Alamos National Laboratory, California, USA Fujitsu Numerical Wind Tunnel II 236 GFLOPS National Aerospace Lab, Japan Intel ASCI Red 2.15 TFLOPS Sandia National Laboratories, New Mexico, USA IBM ASCI White NEC Earth Simulator TFLOPS TFLOPS Lawrence Livermore National Laboratory, California, USA Yokohama Institute for Earth Sciences, Japan 8

9 高性能计算机 IBM Blue Gene/L prototype 74 TFLOPS IBM, Rochester, Minnesota, USA IBM Blue Gene/L prototype TFLOPS IBM, Rochester, Minnesota, USA IBM Blue Gene/L prototype TFLOPS IBM, Rochester, Minnesota, USA IBM Blue Gene/L prototype TFLOPS IBM, Rochester, Minnesota, USA IBM Roadrunner PFLOPS IBM, Los Alamos, USA IBM Roadrunner PFLOPS IBM, Los Alamos, USA Cray Jaguar PFLOPS Cray, Oak Ridge National Laboratory, USA 9

10 最新全球超级计算机五百强出炉国际 TOP500 组织 2011 年 6 月 20 日在网站上公布了最新全球超级计算机 500 强排行榜, 日本超级计算机京以每秒 8162 万亿次的实测运算速度跻身榜首, 中国的天河一号排名降至第二这份排行榜还显示, 中国的超级计算机数量不断增加, 包括实测运算速度达 2600 万亿次的天河一号和排名第四的星云在内, 进入排行榜的超级计算机系统已达 62 个, 第三名德国是 30 个中国超级计算机系统无论是总数还是累计峰值运算能力都超过了德日法等传统的超级计算机大国, 美国则以 256 个遥遥领先于其他所有国家

11 系统互连不同带宽与距离的互连技术总线处理器总线局部总线 ( 存储器总线 ) I/O 总线 ( 系统总线 ) SAN: 系统域网络 LAN: 局域网络 MAN: 都域网 WAN: 广域网 11

12 局部总线 I/O 总线 SAN 和 LAN P I/O 桥节点 1 处理器总线局部总线, 存储器总线 SCSI M 磁盘系统 I 节点 2 节点 N SAN(e.g.Myrinet) I/O 总线, 系统总线接口 LAN(e.g. 以太网,FDDI) 系统 II 12

13 系统互连网络带宽 100 Gb/s 10 Gb/s 1 Gb/s 100 Mb/s MIN 或交叉开关局部总线 I/O 总线 SCI Myrinet 光纤通道千兆位快速以太网 100 Base T HiPPI 以太网 FDDI ATM 10 Mb/s IsoEnet 以太网 10 Base T 总线或开关 SAN LAN MAN WAN 13

14 网络性能指标节点度 (Node Degree): 射入或射出一个节点的边数在单向网络中, 入射和出射边之和称为节点度网络直径 (Network Diameter): 网络中任何两个节点之间的最长距离, 即最大路径数对剖宽度 (Bisection Width) : 对分网络各半所必须移去的最少边数对剖带宽 ( Bisection Bandwidth): 每秒钟内, 在最小的对剖平面上通过所有连线的最大信息位 ( 或字节 ) 数如果从任一节点观看网络都一样, 则称网络为对称的 (Symmetry) 14

15 静态互连网络与动态互连网络静态互连网络处理单元间有着固定连接的一类网络, 在程序执行期间, 这种点到点的链接保持不变典型的静态网络有一维线性阵列二维网孔树连接超立方网络立方环洗牌交换网蝶形网络等动态网络用交换开关构成的, 可按应用程序的要求动态地改变连接组态典型的动态网络包括总线交叉开关和多级互连网络等 15

16 静态互连网络 (1) 一维线性阵列 (1 D Linear Array): 并行机中最简单最基本的互连方式, 每个节点只与其左右近邻相连, 也叫二近邻连接, N 个节点用 N 1 条边串接之, 内节点度为 2, 直径为 N 1, 对剖宽度为 1 当首尾节点相连时可构成循环移位器, 在拓扑结构上等同于环, 环可以是单向的或双向的, 其节点度恒为 2, 直径或为 N /( 2 双向环 ) 或为 N 1( 单向环 ), 对剖宽度为 2 16

17 N N 静态互连网络 (2) 二维网孔 (2 D Mesh): 每个节点只与其上下左右的近邻相连 ( 边界节点除外 ), 节点度为 4, 网络直径为 2( N 1), 对剖宽度为 N 在垂直方向上带环绕, 水平方向呈蛇状, 就变成 Illiac 网孔了, 节点度恒为 4, 网络直径为 N 1, 而对剖宽度为 2 N 垂直和水平方向均带环绕, 则变成了 2 D 环绕 (2 D Torus), 节点度恒为 4, 网络直径为 2 N / 2, 对剖宽度为 2 N (a)2-d 网孔 (b)illiac 网孔 (c)2-d 环绕 17

18 静态互连网络 (3) 二叉树 : 除了根叶节点, 每个内节点只与其父节点和两个子节点相连节点度为 3, 对剖宽度为 1, 而树的直径为 2 log N 1 如果尽量增大节点度为 N 1, 则直径缩小为 2, 此时就变成了星形网络, 其对剖宽度为 N / 传统二叉树的主要问题是根易成为通信瓶颈胖树节点间的通路自叶向根逐渐变宽 2 (a) 二叉树 (c) 二叉胖树 (b) 星形连接 18

19 静态互连网络 (4) 超立方 : n 一个 n 立方由 N 2 个顶点组成, 3 立方如图 (a) 所示 ;4 立方如图 (b) 所示, 由两个 3 立方的对应顶点连接而成 n 立方的节点度为 n, 网络直径也是 n, 而对剖宽度为 N / 2 如果将 3 立方的每个顶点代之以一个环就构成了如图 (d) 所示的 3 立方环, 此时每个顶点的度为 3, 而不像超立方那样节点度为 n (a)3- 立方 (c) 顶点代之以环 (b)4- 立方 (d)3- 立方环 19

20 嵌入将网络中的各节点映射到另一个网络中去用膨胀 (Dilation) 系数来描述嵌入的质量, 它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数如果该系数为 1, 则称为完美嵌入环网可完美嵌入到 2 D 环绕网中超立方网可完美嵌入到 2-D 环绕网中 20

21 嵌入

22 静态互连网络特性比较网络名称网络规模节点度网络直径对剖宽度对称链路数线性阵列 2 1 非 N N 1 N 1 环形 2 ( 双 N N / 2 向 ) 2 是 N 2-D 网孔 4 非 N N 2( N 1) N Illiac 网孔 4 非 N N N 1 2 N 2-D 环绕 4 是 2 N N N / 2 2 N 二叉树 3 1 非 2 log N 1 N 星形 2 非 N / 2 N N 1 2( N N 2N 2N N 1 N 1 ) 超立方 n n 是 N 2 n 立方环 k 3 2k 1 k / 2 是 N k 2 22 N / 2 N/(k 2) nn / 2 3N / 2

23 动态互连网络 (1) 总线 : 总线实际上是连接处理器存储模块和 I/O 外围设备等的一组导线和插座总线系统用以主设备 ( 如处理器 ) 和从设备 ( 如存储器 ) 之间的数据传输目前已有很多总线标准 :PCI VME Multics Sbus MicroChannel 多处理机总线系统的主要问题包括总线仲裁中断处理协议转换快速同步高速缓存一致性协议分事务总线桥和层次总线扩展等 23

24 动态互连网络 (2) CPU 板本地外围设备 (SCSI 总线 ) 存储器板 LM CPU IOC 存储器单元本地总线存储器总线高速缓存 IF IF MC 系统总线 ( 底板上 ) I/O 板通信板 IOP IF IF CC 数据总线数据总线缓冲 IF 缓冲 IF 磁盘和磁带部件打印机或绘图仪 24 网络 ( 以太网等 )

25 交叉开关 (Crossbar): 动态互连网络 (3) 单级交换网络, 可为每个端口提供更高的带宽象电话交换机一样, 交叉点开关可由程序控制动态设置其处于开或关状态, 而能提供所有 ( 源目的 ) 对之间的动态连接交叉开关一般有两种使用方式 : 一种是用于对称的多处理机或多计算机机群中的处理器间的通信 ; 另一种是用于 SMP 服务器或向量超级计算机中处理器和存储器之间的存取 25

26 动态互联网络 (4) 单级交叉开关级联起来形成多级互连网络 MIN (Multistage Interconnection Network) (a)4 种可能的开关连接输入第 0 级第 1 级第 2 级输出 (b) 一种 8 输入的 Omega 网络 26

27 动态互连网络 (5) 交换开关模块 : 一个交换开关模块有 n 个输入和 n 个输出, 每个输入可连接到任意输出端口, 但只允许一对一或一对多的映射, 不允许多对一的映射, 因为这将发生输出冲突级间互连 (Interstage Connection ): 均匀洗牌蝶网多路均匀洗牌交叉开关立方连接 n 输入的 Ω 网络需要 log n 级开关, 在 Ilinois 大学的 Cedar[2] 多处理机系统中采用了 Ω 网络 Cray Y/MP 多级网络, 该网络用来支持 8 个向量处理器和 256 个存储器模块之间的数据传输网络能够避免 8 个处理器同时进行存储器存取时的冲突 27

28 动态互连网络比较动态互连网络的复杂度和带宽性能一览表网络特性总线系统多级互连网络交叉开关开关复杂度每个处理器带宽 O (n) ( n log n) O k O( n 2 ) ~ O (w O (w) ~ (nw) O(w) ~ O ( w/ n) ) O O(nw) 报道的聚集带宽 SunFire 服务器中的 Gigaplane 总线 :2.67GB/s IBM SP2 中的 512 节点的 HPS: 10.24GB/s Digital 的千兆开关 :3.4GB/s n, 节点规模 w, 数据宽度 28

29 标准互联网络 (1) Myrinet: Myrinet 是由 Myricom 公司设计的千兆位包交换网络, 其目的是为了构筑计算机机群, 使系统互连成为一种商业产品 Myrinet 是基于加州理工学院开发的多计算机和 VLSI 技术以及在南加州大学开发的 ATOMIC/LAN 技术 Myrinet 能假设任意拓扑结构, 不必限定为开关网孔或任何规则的结构 Myrinet 在数据链路层具有可变长的包格式, 对每条链路施行流控制和错误控制, 并使用切通选路法以及定制的可编程的主机接口在物理层上,Myrinet 网使用全双工 SAN 链路, 最长可达 3 米, 峰值速率为 ( )Gbps( 目前有 ) 29

30 标准互联网络 (1) Myrinet: Myrinet 交换开关 :8,12,16 端口 Myrinet 主机接口 : 32 位的称作 LANai 芯片的用户定制的 VLSI 处理器, 它带有 Myrinet 接口包接口 DMA 引擎和快速静态随机存取存储器 SRAM 140 of the November 2002 TOP500 use Myrinet, including 15 of the top

31 Myrinet 连接的 LAN/Cluster 桌面主机机箱内多计算机机群交换开关交换开关交换开关交换开关 VME 单板网络 RAM 和磁盘多处理机机群 31

32 标准互连网络 (2) 高性能并行接口 (HiPPI) Los Alamos 国家实验室于 1987 年提出的一个标准, 其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口在大型机和超级计算机工业界,HiPPI 作为短距离的系统到系统以及系统到外设连接的高速 I/O 通道 1993 年,ANSI X3T9.3 委员会认可了 HiPPI 标准, 它覆盖了物理和数据链路层, 但在这两层之上的任何规定却取决于用户 HiPPI 是个单工的点到点的数据传输接口, 其速率可达 800Mbps 到 1.6Gbps 32

33 标准互连网络 (2) 高性能并行接口 (HiPPI) 开发成功了一种能提供潜在的 6.4Gbps 速率, 比 HiPPI 快 8 倍且有很低时延的超级 HiPPI 技术, SGI 公司和 Los Alamos 国家实验室都开发了用来构筑速率高达 25.6Gbps 的 HiPPI 交换开关的 HiPPI 技术 HiPPI 通道和 HiPPI 交换开关被用在 SGI Power Challenge 服务器 IBM 390 主机 Cray Y/MP C90 和 T3D/T3E 等系统 33

34 使用 HiPPI 通道和开关构筑的 LAN 主干网存储器 25 米服务器 HiPPI 串行 300 米超级计算机 300 米大规模并行处理系统 HiPPI 交换开关 HiPPI 串行小型机光纤扩展器直至 10 千米帧缓冲器光纤扩展器 25 米工作站 RGB HiPPI 交换开关 300 米显示器 25 米 HiPPI 串行工作站文件服务器 34

35 标准互连网络 (3) 光纤通道 FC(Fiber Channel) : 通道和网络标准的集成光纤通道既可以是共享介质, 也可以是一种交换技术光纤通道操作速度范围可从 100 到和 800Mbps FCSI 厂商也正在推出未来具有更高速度 (1 2 或 4Gbps) 的光纤通道光纤通道的价值已被现在的某些千兆位局域网所证实, 这些局域网就是基于光纤通道技术的连网拓扑结构的灵活性是光纤通道的主要财富, 它支持点到点仲裁环及交换光纤连接 35

36 标准互连网络 (3) FDDI : 光纤分布式数据接口 FDDI(Fiber Distributed Data Interface) FDDI 采用双向光纤令牌环可提供 Mbps 数据传输速率 FDDI 具有互连大量设备的能力传统的 FDDI 仅以异步方式操作 36

37 双向 FDDI 环作为主干网文件服务器 FDDI 集中器双向 FDDI 环 FDDI 集中器以太网集线器路由器 FDDI 集中器桌面计算机数据库服务器计算机服务器 37

38 标准互联网络 (4) ATM(Asynchronous Transfer Mode): 由成立于 1991 年的 ATM 论坛和 ITU 标准定义 ATM 是一种独立于介质的消息传输协议, 它将消息段变成更短的固定长度为 53 字节的报元进行传输这种技术是基于报元交换机制 ATM 的目的是将实时和突发数据的传输合并成单一的网络技术 ATM 网络支持从 25 到和 622Mbps 不同的速率, 其速率越低 ATM 交换器和使用的链路价格越低 38

39 ( 香港大学开发的 Pearl 机群 IBM SP2 32 节点 ) FDDI 城市大学的 WS 池 T1 HARNET 浸会大学的 WS 池 T1 T3 USC 的 IMSC 去 USA 主干因特网 PC 和 WS 以太网 LAX-20 ASX-200BX T1 SGI Power Challenge XL 服务器 (8CPU) 155Mb/s HP 服务器 ASX-1000 ATM 开关 155Mb/s 155Mb/s Sun E-6000 服务器 (8 CPU) PC Sun E-4000 Sun UltraSPARC 2/1200 Sun SPARC 20/HS14 工作站池 39 Power 集线器 7000 以太网

40 标准互联网络 (4) 以太网以太网 (Ethernet) 是一种计算机局域网组网技术 IEEE 制定的 IEEE 标准给出了以太网的技术标准它规定了包括物理层的连线电信号和介质访问层协议的内容以太网是当前应用最普遍的局域网技术它很大程度上取代了其他局域网标准, 如令牌环网 (token ring) FDDI 和 ARCNET 以太网的标准拓扑结构为总线型拓扑, 但目前的快速以太网 (100BASE T 1000BASE T 标准 ) 为了最大程度的减少冲突, 最大程度的提高网络速度和使用效率, 使用交换机 (Switch hub) 来进行网络连接和组织, 这样, 以太网的拓扑结构就成了星型, 但在逻辑上, 以太网仍然使用总线型拓扑和 CSMA/CD(Carrier Sense Multiple Access/Collision Detect 即带冲突检测的载波监听多路访问 ) 的总线争用技术 40

41 标准互连网络 (5) 代别类型以太网 10BaseT 快速以太网 100BaseT 千兆位以太网 1GB 引入年代速度 ( 带宽 ) 10Mb/s 100Mb/s 1Gb/s 最大距离 UTR( 非屏蔽双扭对 ) STP( 屏蔽双扭对 ) 同轴电缆 100m 100m m 500m 100m m 多模光纤 2Km 412m( 半双工 ) 500m 2Km( 全双工 ) 单模光纤 25Km 20Km 3Km 主要应用领域文件共享, 打印机共享 COW 计算, C/S 结构, 大型数据库存取等大型图像文件, 多媒体, 因特网, 内部网, 数据仓库等 41

42 SISD MIMD SIMD MISD 1966 年,MichealFlynn 根据指令和数据流的概念对计算机的体系结构进行了分类, 这就是所谓的 Flynn 分类法 Flynn 将计算机划分为四种基本类型, 即 SISD MIMD SIMD MISD 传统的顺序执行的计算机在同一时刻只能执行一条指令 ( 即只有一个控制流 ) 处理一个数据( 即只有一个数据流 ), 因此被称为单指令流单数据流计算机 (Single Instruction Single Data, SISD) 42

43 SISD MIMD SIMD MISD 而对于大多数并行计算机而言, 多个处理单元都是根据不同的控制流程执行不同的操作, 处理不同的数据, 因此, 它们被称作是多指令流多数据流计算机, 即 MIMD(Multiple Instruction Multiple Data,MIMD) 计算机曾经在很长一段时间内成为超级并行计算机主流的向量计算机除了标量处理单元之外, 最重要的是具有能进行向量计算的硬件单元在执行向量操作时, 一条指令可以同时对多个数据 ( 组成一个向量 ) 进行运算, 这就是单指令流多数据流 (Single Instruction Multiple Data,SIMD) 的概念因此, 我们将向量计算机称为 SIMD 计算机 43

44 SISD MIMD SIMD MISD 第四种类型即所谓的多指令流单数据 (Multiple Instruction Single Data, MISD) 计算机在这种计算机中, 各个处理单元组成一个线性阵列, 分别执行不同的指令流, 而同一个数据流则顺次通过这个阵列中的各个处理单元这种系统结构只适用于某些特定的算法相对而言,SIMD 和 MISD 模型更适合于专用计算在商用并行计算机中,MIMD 模型最为通用,SIMD 次之, 而 MISD 最少用 PII 的 MMX 指令采用的是 SISD, 高性能服务器与超级计算机大多属于 MIMD 44

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

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

47 五种结构特性一览表属性 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, Intel Paragon, SGI Power IBMSP2, 曙 Challenge, 光 1000/2000 曙光 1 号 47 Stanford DASH, Cray T 3D Berkeley NOW, Alpha Farm

48 并行计算机访存模型 (1) UMA(Uniform Memory Access) 模型是均匀存储访问模型的简称其特点是 : 物理存储器被所有处理器均匀共享 ; 所有处理器访问任何存储字取相同的时间 ; 每台处理器可带私有高速缓存 ; 外围设备也可以一定形式共享 48

49 并行计算机访存模型 (1) 处理器 P 1 P 2 P n 系统互连 ( 总线, 交叉开关, 多级网络 ) I/O SM 1 SM m 共享存储器 49

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

51 并行计算机访存模型 (2) GSM GSM GSM 全局互连网络 P CSM P CSM LM 1 P 1 LM 2 P 2 互连网络 P P C I N CSM CSM P P C I N CSM CSM LM n P n 群 1 群 N (a) 共享本地存储模型 (b) 层次式机群模型 51

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

53 并行计算机访存模型 (3) 互连网络 D D D C C C P P P 53

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

55 并行计算机访存模型 (4) P/C 节点 1 P/C 总线或交叉开关 Mem P/C 节点 N P/C 总线或交叉开关 Mem I/O NIC,DIR,RC I/O NIC,DIR,RC 系统互连网路 55

56 并行计算机访存模型 (5) NORMA(No-Remote Memory Access) 模型是非远程存储访问模型的简称 NORMA 的特点是 : 所有存储器是私有的 ; 绝大数 NUMA 都不支持远程存储器的访问 ; 在 DSM 中,NORMA 就消失了 56

57 并行计算机访存模型 (5) M P M P... M P M P M... P 消息传递互连网络 ( 网络, 环网, 超立方, 立方环等 ) P M P... M P M P M... P M 57

58 构筑并行机系统的不同存储结构 MIMD 多处理机 ( 单地址空间共享存储器 ) NORMA 多计算机 ( 多地址空间非共享存储器 ) 中央存储器 UMA NUMA 分布存储器 Cluster PVP (Cray T90) SMP (IBM SP2,DEC TruCluster Tandem Hymalaya,HP, Microsoft Wolfpack,etc) ( 松散耦合 ) MPP (Intel TFLOPS) ( 紧耦合 ) 58 (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.)

并行计算

并行计算 arallel Computing 主讲人孙广中 Spring, 2016 并行计算结构算法编程第一篇并行计算的基础第一章并行计算与并行计算机结构模型第二章并行计算机系统互连与基本通信操作第三章典型并行计算机系统介绍第四章并行计算性能评测 2 第一章并行计算及并行机结构模型 1.1 计算与计算机科学 1.2* 单处理机与指令级并行 1.3* 多核处理器与线程级并行 1.4