并行计算概述[专业相关]

1、并行计算 1 专业课 并行计算结构算法编程 2 专业课 并行计算结构算法编程 3 专业课 第一章并行计算机系统及结构模型 4 专业课 并行计算 5 专业课 6 专业课 7 专业课 并行计算 8 专业课 9 专业课 10 专业课 11 专业课 12 专业课 13 专业课 高性能计算机 14 专业课 系统互连 局 部 总 线 I/O 总 线 SCI HiPPI Myrinet 千 兆 位以 太 网 光 纤 通 道 快 速 以 太 网 以 太 网 10 Base T FDDI ATM 总 线 或 开 关SANLANMANWAN 100 Gb/s 10 Gb/s 1 Gb/s 100 Mb/s 10

2、Mb/sIsoEnet 网络带宽 交 叉 开 关 MIN 或 100 Base T 15 专业课 局部总线、I/O总线、SAN和LAN PM I/O 桥 磁盘 SAN(e.g.Myrinet) LAN(e.g.以太网,FDDI) 系统 II I/O总线, 接口 系统 I 处理器总线 局部总线,存储器总线 SCSI 节点 2节点N 系统总线 节点 1 16 专业课 网络性能指标 17 专业课 静态互连网络 与动态互连网络 18 专业课 静态互连网络（1） 2/N 19 专业课 静态互连网络（2） ) 1(2N N 1NN2 2/2NN2 NN (a)2-D网孔(b)Illiac网孔(c)2-D环

3、绕 20 专业课 静态互连网络（3） 1log2N 2/N (a)二叉树(b)星形连接 (c)二叉胖树 21 专业课 静态互连网络（4） n N2 2/N (b)4-立 方(a)3-立 方 (c)顶 点 代 之 以 环(d)3-立 方 环 22 专业课 嵌入 23 专业课 嵌入 1000100110111010 1100110111111110 0100010101110110 0000000100110010 0 01 10 01 10 01 10 00 0 0 00 00 00 00 00 00 01 1 0 01 11 11 10 01 11 10 0 0 00 01 10 00 00

4、01 11 1 1 11 10 01 11 11 10 00 0 1 10 00 00 01 10 00 01 1 1 11 11 11 11 11 11 10 0 1 10 01 10 01 10 01 11 1 24 专业课 N N N N NN NN NN n N2 k kN2 1N 1N 2/N ) 1(2N 1N 2/2N 1log2N 2/12kk N N2 N2 2/N 2/N )2/(kN 1N N )(2NN N2 N2 1N 1N 2/nN 2/3N 静态互连网络特性比较 25 专业课 动态互连网络 (1) L MI O C 本 地 总 线 高 速 缓 存 C P U I

5、FI F I F 存 储 器 总 线 存 储 器 单 元 I F I F C P U 板存 储 器 板 I / O 板通 信 板 系 统 总 线( 底 板 上 ) 数 据 总 线 缓 冲 C CI O P 数 据 总 线 网 络 ( 以 太 网 等 ) 磁 盘 和 磁 带 部 件 打 印 机 或 绘 图 仪 本 地 外 围 设 备 ( S C S I 总 线 ) M C I F缓 冲 26 专业课 动态互连网络 （2） 27 专业课 动态互联网络 （3） 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 (a)4种可能的开关连接 000 001 010 011 100 101 1

6、10 111 输入 000 001 010 011 100 101 110 111 输出 第0级第1级第2级 (b)一种8输入的Omega网络 28 专业课 动态互连网络（4） n 2 log22 29 专业课 动态互连网络比较 )(wnO)log(wnnO k)( 2w nO )/(nwfO)(wfO )(wfO)(wfO 30 专业课 标准互联网络（1） 31 专业课 Myrinet连接的LAN/Cluster 交换开关交换开关 交换开关交换开关 桌面主机 机箱内多计算机机群 多处理机机群 网络RAM和 VME 单板 磁盘 32 专业课 标准互连网络（2) 33 专业课 使用HiPPI通道

7、和开关构筑的 LAN主干网 HiPPI 交 换 开 关 超 级 计 算 机帧 缓 冲 器 RGB 显 示 器 HiPPI 串 行 文 件 服 务 器 工 作 站 小 型 机 大 规 模 并 行 处 理 系 统 25米 300米 25米 25米 HiPPI 串 行 300米 直 至 10千 米 300米 HiPPI 串 行 存 储 器 服 务 器 工 作 站 光 纤 扩 展 器光 纤 扩 展 器 HiPPI 交 换 开 关 34 专业课 标准互连网络（3） 35 专业课 双向FDDI环作为主干网 文件服务器 数据库服务器 计算机服务器 双向 FDDI环 FDDI集中器 FDDI 集中器FDDI

8、集中器 桌面计算机 以太网集线器 路由器 36 专业课 标准互联网络（4） 37 专业课 香港大学开发的Pearl机群 ASX-200BX LAX-20 HARNET Power 集 线 器 7000 IBM SP2 城 市 大 学 的 WS池 浸 会 大 学 的 WS池 USC的 IMSC XL服 务 器 PC FDDI PC 和 WS 去 USA 主 干 因 特 网 Sun E-6000 服 务 器 (8 CPU) 以 太 网 工 作 站 池 HP 服 务 器 Sun E-4000 Sun UltraSPARC 2/1200 Sun SPARC 20/HS14 以 太 网 T3 T1 15

9、5Mb/s ASX-1000 ATM开 关 T1 T1 155Mb/s 155Mb/s SGI Power Challenge (8CPU) 32节 点 ）( 38 专业课 标准互连网络（5） 39 专业课 并行计算机结构模型 P/C LM NIC 定制网络 (c)MPP P/C LM NIC MBMB VP SM 交叉开关 (a)PVP VPVP SMSM P/C SMSMI/O 总线或交叉开关 (b)SMP P/CP/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 IO

10、B 商品网络(以太网，ATM，etc.) Bridge NICNIC Bridge 40 专业课 并行计算机体系合一结构 C P NIC (a)无 共 享 NIC 互 连 网 络 M D 节 点N 节 点1 Shell 共 享 磁 盘 C P NIC (b)共 享 磁 盘 NIC M 互 连 网 络 节 点N 节 点1 Shell C P 互 连 网 络 共 享 存 储 器共 享 磁 盘 (c)共 享 存 储 C P ShellShell 41 专业课 五种结构特性一览表 属性PVPSMPMPPDSMCOW 结构类型MIMDMIMDMIMDMIMDMIMD 处理器类型专用定制商用商用(可定制)

11、商用商用 互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（以太 ATM） 通信机制共享变量共享变量消息传递共享变量消息传递 地址空间单地址空间单地址空间多地址空间单地址空间多地址空间 系统存储器集中共享集中共享分布非共享分布共享分布非共享 访存模型UMAUMANORMANUMANORMA 代表机器Cray C-90， Cray T-90， 银河1号 IBM R50， S G I P o w e r Challenge， 曙光1号 Intel Paragon， IBMSP2，曙光 1000/2000 Stanford DASH， Cray T 3D Berkeley NOW， Alp

12、ha Farm 42 专业课 并行计算机访存模型（1) P1P2Pn I/OSM1SMm 共享存储器 处理器 （） 系统互连 总线 交叉开关多级,网络 43 专业课 并行计算机访存模型（2) LM1P1 LM2P2 LMnPn 互 连 网 络 (a)共享本地存储模型 全局互连网络 (b)层次式机群模型 GSMGSMGSM P C I N CSM P P CSM CSM 群1 P C I N CSM 群N P P CSM CSM 44 专业课 并行计算机访存模型（3) 互 连 网 络 D C P D C P D C P 45 专业课 并行计算机访存模型（4) I/ONIC,DIR,RC 系统互连

13、网路 MemP/CP/C I/ONIC,DIR,RC MemP/CP/C 节点N节点1 总线或交叉 开关总线或交叉 开关 46 专业课 并行计算机访存模型（5) 消息传递互连网络 (网络，环网，超立方， 立方环等) PM PM MP MP M P M P M P P M P M P M . . . . 47 专业课 构筑并行机系统的不同存储结构 MIMDMIMD 多计算机 (多地址空间非共享存储器) (IBM SP2,DEC TruCluster Tandem Hymalaya,HP, Microsoft Wolfpack,etc) NORMANORMA UMAUMA NUMANUMA Clu

14、sterCluster MPPMPP(Intel TFLOPS) 紧耦合 PVPPVP(Cray T90) SMPSMP (Intel SHV,SunFire,DEC 8400, SGI PowerChallenge,IBMR60,etc.) COMACOMA(KSR-1,DDM) CC-NUMACC-NUMA (Stanford Dash, SGI Origin 2000,Sequent NUMA-Q, HP/Convex Exemplar) NCC-NUMANCC-NUMA(Cray T3E) DSMDSM (TreadMarks, Wind Tunnel, IVY,Shrimp, etc

15、.) （） 松散耦合（） 中央存储器 分布存储器 多处理机 单地址 共享 （ ） 空间 存储器 48 专业课 第二章 当代并行机系统 49 专业课 对称多处理机SMP(1) P / C S MS MI / O 总线或交叉开关 P / CP / C 50 专业课 对称多处理机SMP(2) 51 专业课 大规模并行机MPP P/C LM NIC 定 制 网 络 P/C LM NIC MBMB 52 专业课 典型MPP系统特性比较 MPP模型Intel/Sandia ASCI Option Red IBM SP2SGI/Cray Origin2000 一个大型样机的配置9072个处理器， 1.8Tf

16、lop/s(NSL) 400个处理器， 100Gflop/s(MHPC C) 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分布共享 主存和共享磁盘 互连网络和主存模型分离

17、两维网孔， NORMA 多级网络， NORMA 胖超立方体网络， CC-NUMA 节点操作系统轻量级内核 （LWK） 完全AIX（IBM UNIX） 微内核Cellular IRIX 自然编程机制基于PUMA Portals的MPI MPI和PVMPower C， Power Fortran 其他编程模型Nx，PVM，HPFHPF，LindaMPI，PVM 53 专业课 MPP所用的高性能CPU特性比较 属性Pentium ProPowerPC 602 Alpha 21164A Ultra SPARC II MIPS R10000 工艺BiCMOSCMOSCMOSCMOSCMOS 晶体管数5.

18、5M/15.5M7M9.6M5.4M6.8M 时钟频率150MHz133MHz417MHz200MHz200MHz 电压2.9V3.3V2.2V2.5V3.3V 功率20W30W20W28W30W 字长32位64位64位64位64位 I/O 高速缓存 8KB/8KB32KB/32KB8KB/8KB16KB/16KB32KB/32K B 2级 高速缓存 256KB (多芯片模块 ) 1128MB (片外) 96KB (片上) 16MB (片外) 16MB (片外) 执行单元5个单元6个单元4个单元9个单元5个单元 超标量3路(Way)4路4路4路4路 流水线深 度 14级48级79级9级57级

19、SPECint 92366225500350300 SPECfp 92283300750550600 SPECint 958.0922511N/A7.4 SPECfp 956.7030017N/A15 其它特性CISC/RISC 混合 短流水线长 L1高速缓存 最高时钟频 率最大片上 2级高速缓 存 多媒体和图 形指令 MP机群总 线可支持4 个CPU 54 专业课 机群型大规模并行机SP2 NIC D E 节 点 1 NIC D E 节 点 S 以 太 网 P MCCMCC P P P N 高 性 能Omega，网 络开 关 I/O总 线 I/O总 线 55 专业课 工作站机群COW P/C

20、 M MIOMIO M P/C NICNIC DDLAN 56 专业课 典型的机群系统 典型的机群系统特点一览表 名称系统特点 Princeton:SHRIMPPC商用组件，通过专用网络接口达到共享虚拟存储，支持 有效通信 Karsruhe:Parastation用于分布并行处理的有效通信网络和软件开发 Rice:TreadMarks软件实现分布共享存储的工作站机群 Wisconsin:Wind Tunnel在经由商用网络互连的工作站机群上实现分布共享存储 C h i c a 、 M a r y l 、 Penns:NSCP 国家可扩放机群计划：在通过因特网互连的3个本地机群系 统上进行元计算

21、 Argonne:Globus在由ATM连接的北美17个站点的WAN上开发元计算平台和 软件 Syracuse:WWVM使用因特网和HPCC技术，在世界范围的虚拟机上进行高性 能计算 HKU:Pearl Cluster研究机群在分布式多媒体和金融数字库方面的应用 Virgina:Legion在国家虚拟计算机设施上开发元计算软件 57 专业课 SMPMPP机群比较 系统特征SMPMPP机群 节点数量(N)O(10)O(100)-O(1000)O(100) 节点复杂度中粒度或细粒度细粒度或中粒度中粒度或粗粒度 节点间通信 共享存储器消息传递 或共享变量（有DSM时） 消息传递 节点操作系统1N(微

22、内核) 和1个主机OS(单一) N (希望为同构) 支持单一系统映像永远部分希望 地址空间单一多或单一（有DSM时）多个 作业调度单一运行队列主机上单一运行队列协作多队列 网络协议非标准非标准标准或非标准 可用性通常较低低到中高可用或容错 性能/价格比一般一般高 互连网络总线/交叉开关定制商用 58 专业课 第三章 并行计算性能评测 59 专业课 CPU的某些基本性能指标 T n T TT n T n 11 ,max 60 专业课 存储器性能 寄 存 器 1级 高 速 缓 存 2级 高 速 缓 存 主 存 磁 盘 远 程 存 储 器 C2KB L=0周 期 B=1-32GB/S 4-256KB

23、 0-2周 期 1-16GB/S 64KB-4MB 2-10周 期 1-4GB/S 16MB-16GB 10-100周 期 0.4-2GB/S 1-100GB 100K-1M周 期 1-16MB/S 1-100GB 100-100K周 期 1-300MB/S 各层性能参数：各层性能参数：容量容量C C、延迟、延迟L L、带宽、带宽B B。 相关参数：相关参数：存储粒度、一致性粒度、层管理方案等。存储粒度、一致性粒度、层管理方案等。 61 专业课 影响存储器容量影响存储器容量C C设计因素：设计因素： 与主流应用的进程数及各进程工作集尺寸等有关。与主流应用的进程数及各进程工作集尺寸等有关。 影响

24、存储器延迟影响存储器延迟L L设计因素：设计因素： 与与CPUCPU指令系统指令系统CPICPI及指令所需数据量等有关。及指令所需数据量等有关。 影响存储器带宽影响存储器带宽B B设计因素：设计因素： 与应用的数据通信量、通信频率和延迟与应用的数据通信量、通信频率和延迟L L等有关。等有关。 62 专业课 并行与通信开销 63 专业课 Ping-Pong Scheme 64 专业课 并行开销的表达式：点到点通信 65 专业课 并行开销的表达式：整体通信 66 专业课 机器的成本、价格与性/价比 67 专业课 算法级性能评测 68 专业课 Amdahl 定律 69 专业课 Amdahl定律（co

25、ntd) pWWs WpWs S P / )1(1 1 )1( pf p p f f ff S WpWpf p W p fW fW W W p W W WW S O OO P S PS /) 1(1 )1 ( 70 专业课 Amdahls law (contd) 程序中顺序部分的百分比f (c) 0% 1% 2% 3% 4% 100% 加速比S S1024=1024/(1+1023f) 1024x 91x 48x 31x 24x 1x WpWp Wp WpWp Wp W1W1W1W1W1W1 工作负载W 处理器数P (a) 123456 T1 T1 Tp Tp Tp Tp Tp Tp T1 T

26、1 T1 执行时间T 处理器数P (b) T1 123456 71 专业课 Gustafson定律 PS S S S WW pWpW pWppW pWpW S / ) p-f (p-p) f ( p -f) p ( f S 111 WW fpf WWW pWW S OOPS PS /1 1 72 专业课 Gustafson定律（contd) 程序中顺序部分的百分比f (c) S1024=1024-1023f 0%1%2%3%4% 1024x 1014x 1004x 993x 983x 加速比S 处理器数P 工作负载W (a) W1 W1 W1 W1 W1 W1 Wp Wp Wp Wp Wp Wp