并行计算 教学课件.ppt

《并行计算 教学课件.ppt》由会员分享，可在线阅读，更多相关《并行计算 教学课件.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、并行计算系统体系结构概述,Pingpeng YuanService Computing Technology and System LabCluster and Grid Computing Lab,2,2019/10/22,目录,并行计算机系统及结构模型当代并行机系统并行计算性能评测,3,2019/10/22,1 并行计算机系统及结构模型,1.1 并行计算需求1.2 并行计算机系统互连1.2.1 系统互连1.2.2 静态互联网络1.2.3 动态互连网络1.2.4 标准互联网络1.3 并行计算机系统结构1.3.1 并行计算机结构模型1.3.2 并行计算机访存模型,4,2019/10/22,Dr

2、ivers of Parallel Computing,Application Needs: Our insatiable need for computing cyclesScientific computing: CFD, Biology, Chemistry, Physics, .General-purpose computing: Video, Graphics, CAD, Databases, TP.Internet applications: Search, e-Commerce .Technology Trends,5,2019/10/22,Scientific Computin

3、g Demand,Ever increasing demand due to need for more accuracy, higher-level modeling and knowledge, and analysis of exploding amounts of dataExample area: Climate and Ecological Modeling goalsSimply resolution, simulated time, and improved physics leads to increased requirement by factors of 104 to

4、107. Then Reliable global warming, natural disaster and weather predictionPredictive models of rainforest destruction, forest sustainability, effects of climate change on ecoystems and on foodwebs, global health trendsVerifiable global ecosystem and epidemic modelsIntegration of macro-effects with l

5、ocalized and then micro-effectsPredictive effects of human activities on earths life support systemsUnderstanding earths life support systems,6,2019/10/22,Engineering Computing Demand,Large parallel machines a mainstay in many industriesPetroleum (reservoir analysis)Automotive (crash simulation, dra

6、g analysis, combustion efficiency), Aeronautics (airflow analysis, engine efficiency, structural mechanics, electromagnetism), Computer-aided designPharmaceuticals (molecular modeling)Visualization in all of the aboveentertainment (movies), architecture (walk-throughs, rendering)Financial modeling (

7、yield and derivative analysis)etc.,7,2019/10/22,Commercial Computing,Also relies on parallelism for high endScale not so large, but use much more wide-spreadComputational power determines scale of business that can be handledDatabases, online-transaction processing, decision support, data mining, da

8、ta warehousing .E-commerce, search and other scalable internet servicesParallel applications running on clustersDeveloping new parallel software models and primitivesInsight from automated analysis of large disparate data,8,2019/10/22,Drivers of Parallel Computing,Application NeedsTechnology Trends,

9、9,2019/10/22,Technology Trends: Rise of the Micro,The natural building block for multiprocessors is now also about the fastest!,10,2019/10/22,General Technology Trends,Microprocessor performance increases 50% - 100% per yearClock frequency doubles every 3 yearsTransistor count quadruples every 3 yea

10、rs Moores law: xtors per chip = 1.59year-1959 (originally 2year-1959)Huge investment per generation is carried by huge commodity market,11,2019/10/22,Clock Frequency Growth Rate (Intel family),30% per year,12,2019/10/22,Transistor Count Growth Rate (Intel family),Transistor count grows much faster t

11、han clock rate- 40% per year, order of magnitude more contribution in 2 decadesWidth/space has greater potential than per-unit speed,13,2019/10/22,How to Use More Transistors,Improve single threaded performance via architecture:Not keeping up with potential given by technology (next)Use transistors

12、for memory structures to improve data localityDoesnt give as high returns (2x for 4x cache size, to a point)Use parallelismInstruction-level Thread levelBottom line: Not that single-threaded performance has plateaued, but that parallelism is natural way to stay on a better curve,14,2019/10/22,Microp

13、rocessor Performance,15,2019/10/22,Similar Story for Storage (Transistor Count),16,2019/10/22,Similar Story for Storage (DRAM Capacity),17,2019/10/22,Similar Story for Storage,Divergence between memory capacity and speed more pronouncedCapacity increased by 1000x from 1980-95, and increases 50% per

14、yrLatency reduces only 3% per year (only 2x from 1980-95)Bandwidth per memory chip increases 2x as fast as latency reduces,Larger memories are slower, while processors get fasterNeed to transfer more data in parallelNeed deeper cache hierarchiesHow to organize caches?,18,2019/10/22,Similar Story for

15、 Storage,Parallelism increases effective size of each level of hierarchy, without increasing access timeParallelism and locality within memory systems tooNew designs fetch many bits within memory chip; follow with fast pipelined transfer across narrower interfaceBuffer caches most recently accessed

16、dataDisks too: Parallel disks plus cachingOverall, dramatic growth of processor speed, storage capacity and bandwidths relative to latency (especially) and clock speed point toward parallelism as the desirable architectural direction,19,2019/10/22,Top 10 Fastest Computers (Linpack),RankSiteComputerP

17、rocessorsYearRmaxDOE/NNSA/LLNL USAIBM BlueGene 1310722005280600NNSA/Sandia Labs, USACray Red Storm, Opteron 26544 2006101400IBM Research, USA,IBM Blue Gene Solution 40960 2005 91290DOE/NNSA/LLNL, USAASCI Purple - IBM eServer p5 12208 2006 75760Barcelona Center, Spain IBM JS21 Cluster, PPC 970 10240

18、2006 62630NNSA/Sandia Labs, USADell Thunderbird Cluster 9024 2006 53000CEA, FranceBull Tera-10 Itanium2 Cluster 9968 2006 52840NASA/Ames, USASGI Altix 1.5 GHz, Infiniband 101602004 51870GSIC Center, JapanNEC/Sun Grid Cluster (Opteron) 11088 2006 47380Oak Ridge Lab, USACray Jaguar XT3, 2.6 GHz dual 1

19、0424 2006 43480,NEC Earth Simulator (top for 5 lists) moves down to #14 #10 system has doubled in performance since last year,20,2019/10/22,Top 500: Architectural Styles,21,2019/10/22,Top 500: Processor Type,22,2019/10/22,系统互连,不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN,23,2019/10/22,局部总线、I/O总线、SAN和LAN,24,2019

20、/10/22,网络性能指标,节点度（Node Degree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（Network Diameter）： 网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（Bisection Width） ：对分网络各半所必须移去的最少边数对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称网络为对称的（Symmetry）,25,2019/10/22,静态互连网络 与动态互连网络,静态互连网络：处理单元间有着固定连接的一类网络，在程

21、序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。,26,2019/10/22,静态互连网络（1）,一维线性阵列（1-D Linear Array）：并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为i

22、nt(n/2) （双向环）或为N-1（单向环），对剖宽度为2,27,2019/10/22,静态互连网络（2）,二维网孔（2-D Mesh）：每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为 ，对剖宽度为 在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为 ，而对剖宽度为 垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus），节点度恒为4，网络直径为 ，对剖宽度为,28,2019/10/22,静态互连网络（3）,二叉树：除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为 如果

23、尽量增大节点度为，则直径缩小为2，此时就变成了星形网络传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。,29,2019/10/22,静态互连网络（4）,超立方 ：一个n-立方由 个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为n，网络直径也是n ，而对剖宽度为 。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。,30,2019/10/22,嵌入,将网络中的各节点映射到另一个网络中去用膨胀（Dilation）系数来描述嵌入的质量，它是

24、指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数 如果该系数为1，则称为完美嵌入。 环网可完美嵌入到2-D环绕网中 超立方网可完美嵌入到2D环绕网中,31,2019/10/22,嵌入,32,2019/10/22,静态互连网络特性比较,33,2019/10/22,动态互连网络 (1),总线：PCI、VME、Multics、Sbus、MicroChannel 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等,34,2019/10/22,动态互连网络 （2）,交叉开关（Crossbar）：单级交换网络，可为每个端口

25、提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。,35,2019/10/22,动态互联网络 （3）,单级交叉开关级联起来形成多级互连网络MIN（Multistage Interconnection Network）,36,2019/10/22,标准互联网络,Myrinet:Myrinet是由Myricom公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，

26、使系统互连成为一种商业产品。Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。Myrinet在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，Myrinet网使用全双工SAN链路,37,2019/10/22,Myrinet,#4 System on Top500 listSystem sustains 64% of peak performanceBut smaller systems hit 70

27、-75% of peak,38,2019/10/22,MareNostrum: largest Myrinet cluster in the world,IBM system at Barcelona Supercomputer Center4812 PowerPC 970 processors, 9.6 TB memory,39,2019/10/22,Quadrics,QsNetII E-seriesReleased at the end of May 2004Deliver 128-port standalone switchesPerformance:Latency: 3 usBandw

28、idth: 900 MB/sCost/port (based on 64-port configuration): $1800Switch + NIC + cablehttp:/ on Top500 listSustains 74% of peakOther systems on Top500 list sustain 70-75% of peak,41,2019/10/22,Infiniband,Newest interconnectCurrently shipping 32-port switchesRequires 20 switches to support a full bisect

29、ion bandwidth network for 128 nodes Performance:Latency: 6.8 usBandwidth: 840 MB/sEstimated cost/port (based on 64-port configuration): $1700 - 3000Switch + NIC + cablehttp:/ on Top500 listSustained 58% of peakThe other 2 Infiniband machines on Top500 list achieved 64% and 68%,43,2019/10/22,Intercon

30、nects / Systems,44,2019/10/22,并行计算机结构模型,45,2019/10/22,并行计算机体系合一结构,SMP(Symmetric Multiprocessor)、MPP(Massively Parallel Processor)、DSM和COW(Cluster of Worksations )并行结构渐趋一致。大量的节点通过高速网络互连起来,46,2019/10/22,五种结构特性一览表,47,2019/10/22,存储器层次,48,2019/10/22,存储器存取模型( UMA NUMA COMA NORMA),NORMA,COMA,NUMA,UMA,49,20

31、19/10/22,并行计算机访存模型（1),UMA（Uniform Memory Access）模型是均匀存储访问模型的简称。其特点是：物理存储器被所有处理器均匀共享；所有处理器访问任何存储字时间相同；每台处理器可带私有高速缓存；外围设备也可以一定形式共享。,50,2019/10/22,并行计算机访存模型（2),NUMA(Nonuniform Memory Access)模型是非均匀存储访问模型的简称。特点是：被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；处理器访问存储器的时间是不一样的；访问本地存储器LM或群内共享存储器CSM较快，而访问外地的存

32、储器或全局共享存储器GSM较慢(此即非均匀存储访问名称的由来)；每台处理器照例可带私有高速缓存，外设也可以某种形式共享。,51,2019/10/22,并行计算机访存模型（3),COMA(Cache-Only Memory Access)模型是全高速缓存存储访问的简称。其特点是：各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；利用分布的高速缓存目录D进行远程高速缓存的访问;COMA中的高速缓存容量一般都大于2 级高速缓存容量；使用COMA时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用到它们的地方。,52,2019/10/22,并行计算机访存模型（4),CC-NUMA（

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

34、。NORMA的特点是：所有存储器是私有的；在DSM中，NORMA就消失了。,54,2019/10/22,构筑并行机系统的不同存储结构,55,2019/10/22,2 当代并行机系统,2.1 共享存储多处理机系统2.1.1 对称多处理机SMP结构特性2.2 分布存储多计算机系统2.2.1 大规模并行机MPP结构特性2.3 机群系统2.3.1 工作站机群COW,56,2019/10/22,对称多处理机SMP(1),SMP: 采用商用微处理器，通常有片上和片外Cache，基于总线连接，集中式共享存储，UMA结构例子：SGI Power Challenge, DEC Alpha Server,Dawn

35、ing 1,57,2019/10/22,对称多处理机SMP(2),优点对称性单地址空间，易编程性，动态负载平衡，无需显示数据分配高速缓存及其一致性，数据局部性，硬件维持一致性低通信延迟，Load/Store完成问题欠可靠，BUS,OS,SM通信延迟（相对于CPU），竞争加剧慢速增加的带宽（MB double/3年,IOB更慢）不可扩放性-CC-NUMA,58,2019/10/22,大规模并行机MPP,成百上千个处理器组成的大规模计算机系统，规模是变化的。NORMA结构，高带宽低延迟定制互连。可扩放性：Mem, I/O,平衡设计系统成本：商用处理器，相对稳定的结构，SMP,分布通用性和可用性：不

36、同的应用，PVM,MPI,交互，批处理，互连对用户透明通信要求存储器和I/O能力例子：Intel Option Red IBM SP2 Dawning 1000,59,2019/10/22,典型MPP系统特性比较,60,2019/10/22,MPP所用的高性能CPU特性比较,61,2019/10/22,工作站机群COW,分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核优点：投资风险小系统结构灵活性能/价格比高能充分利用分散的计算资源可扩放性好问题通信性能并行编程环境例子：Berkeley NOW，Alpha Farm, FXC

37、OW,62,2019/10/22,典型的机群系统,63,2019/10/22,SMPMPP机群比较,64,2019/10/22,3 并行计算性能评测,3.1 并行机的一些基本性能指标3.2 加速比性能定律3.2.1 Amdahl定律3.2.2 Gustafson定律3.2.3 Sun和Ni定律3.3 可扩放性评测标准3.3.1 并行计算的可扩放性3.3.2 等效率度量标准3.3.3 等速度度量标准3.3.4 平均延迟度量标准,65,2019/10/22,CPU的某些基本性能指标,工作负载执行时间 浮点运算数 指令数目 并行执行时间 T comput 为计算时间，T paro 为并行开销时间，T

38、 comm为相互通信时间 T n = T comput + T paro+ T comm,66,2019/10/22,存储器性能,存储器的层次结构(C,L,B)估计存储器的带宽RISC add r1,r2,r3 r 8bytes 100MHzB = 3*8*100*106 B/s= 2.4GB/s,67,2019/10/22,并行与通信开销,并行和通信开销：相对于计算很大。 PowerPC (每个周期 15ns 执行4flops; 创建一个进程1.4ms 可执行372000flops)开销的测量：乒-乓方法（Ping-Pong Scheme）节点0发送m个字节给节点1；节点1从节点0接收m个字

39、节后，立即将消息发回节点0。总的时间除以2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。,68,2019/10/22,Ping-Pong Scheme,if （my _node _id =0） then /*发送者*/start _time =second（ ） send an m-byte message to node 1 receive an m-byte message from node 1end_time = second（ ）total_time = end_time start_time communication_timei = total_time/2 el

40、se if （my_node_id = 1） then /*接收者*/ receive an m-byte message from node 0 send an m-byte message to node 0endif,69,2019/10/22,并行开销的表达式：整体通信,典型的整体通信有： 播送（Broadcasting）：处理器0发送m个字节给所有的n个处理器收集（Gather）：处理0接收所有n个处理器发来在消息，所以处理器0最终接收了m n个字节；散射（Scatter）：处理器0发送了m个字节的不同消息给所有n个处理器，因此处理器0最终发送了m n个字节；全交换（Total Ex

41、change）：每个处理器均彼此相互发送m个字节的不同消息给对方，所以总通信量为mn2个字节；循环移位（Circular-shift）：处理器i发送m个字节给处理器i+1，处理器n-1发送m个字节给处理器0，所以通信量为m n个字节。,70,2019/10/22,机器的成本、价格与性/价比,机器的成本与价格机器的性能/价格比 Performance/Cost Ratio ：系指用单位代价（通常以百万美元表示）所获取的性能（通常以MIPS或MFLOPS表示） 利用率（Utilization）：可达到的速度与峰值速度之比,71,2019/10/22,算法级性能评测,加速比性能定律并行系统的加速比是

42、指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。Amdahl 定律Gustafson定律Sun Ni定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准,72,2019/10/22,Amdahl 定律,P：处理器数；W：问题规模（计算负载、工作负载，给定问题的总计算量）；Ws：应用程序中的串行分量，f是串行分量比例（f = Ws/W， Ws=W1）；WP：应用程序中可并行化部分，1-f为并行分量比例；Ws +W p =W；Ts=T1 ：串行执行时间，T p ：并行执行时间；S：加速比，E：效率； 出发点：固定不变的计算负载；

43、 固定的计算负载分布在多个处理器上的，增加处理器加快执行速度，从而达到了加速的目的。,73,2019/10/22,Amdahl定律（contd),固定负载的加速公式： W s+ W p可相应地表示为fW+（1-f）Wp时，上式极限为： S= 1 / f W o为额外开销,74,2019/10/22,Amdahls law (contd),75,2019/10/22,Gustafson定律,出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；在实际应用中没有必要固定工作负载而计

44、算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。 Gustafson加速定律 :并行开销W o ：,76,2019/10/22,Gustafson定律（contd),77,2019/10/22,Sun 和 Ni定律,基本思想：只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之，此时工作负载W= fW + （1-f）W。 在p 个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到pM。令因子G（p）反应存储容量增加到p倍时并行工作负载的增加量，所以扩大后的

45、工作负载W = fW + （1-f）G（p）W。存储受限的加速公式 ：,78,2019/10/22,Sun 和 Ni定律(contd),G（p）=1时就是Amdahl加速定律； G（p）=p 变为 f + p（1-f），就是Gustafson加速定律G（p）p时，相应于计算机负载比存储要求增加得快，此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。,79,2019/10/22,可扩展性评测标准,并行计算的可扩展性（Scalability）也是主要性能指标可扩展性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理器数的增加而按比例提高的能

46、力 影响加速比的因素：处理器数与问题规模求解问题中的串行分量并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）加大的处理器数超过了算法中的并发程度增加问题的规模有利于提高加速的因素：较大的问题规模可提供较高的并发度；额外开销的增加可能慢于有效计算的增加；算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题规模的增大而缩小）。增加处理器数会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩展性这一指标。,80,2019/10/22,可扩展性评测标准（contd),可扩展性:调整什么和按什么比例调整并行计算要调整的是处理数p和问题规模W，两者可按不同比例进行调整，此比例关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。 可扩展性研究的主要目的：确定解决某类问题用何种并行算法与何种并行体系结构的组合，可以有效地利用大量的处理器；对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能；对固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大的加速比；用于指导改进并行算法和并行机体系结构，以使并行算法尽可能地充分利用可扩充的大量处理器 目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准,