计算机系统机构-第9章课件.ppt

1、1计算机系统结构n第一章 基本概念n第二章 指令系统n第三章 存储系统n第四章 输入输出系统n第五章 标量处理机n第六章 向量处理机n第七章 互连网络n第八章 并行处理机n第九章 多处理机2第九章 多处理机n多处理机系统n两个或两个以上处理机(包括PE和CU)，n通过高速互连网络连接起来，n在统一的操作系统管理下，n实现指令以上级(任务级、作业级)并行n按照Flynn分类法，多处理机系统属于MIMD计算机n多处理机系统由多个独立的处理机组成n每个处理机都能够独立执行自己的程序39.1 多处理机结构n流水线机器：n流水线机器通过几级流水的同时操作来获得高性能n连续计算机器：n连续计算的机器由多台

2、处理机组成，每台处理机执行相同的程序n前几章讨论了如何加快单指令流执行速度的方法n尽管只有一个程序在执行,前面讨论过的技术可以进一步开发单条指令流内部的指令并行性n本章讨论多处理机-由若干台独立的处理机组成的系统n器件本身的物理条件限制了任何单处理机的速度最高不能超过某个上界值n欲达到超过这个上界值的速度就必须采用其它的方法n本章通过研究多处理机系统来实现这个目的n本章的中心议题是多处理机的结构和性能n介绍如何把多台处理机组成高并行度的系统n深入分析这类系统的瓶颈和改进性能的方法49.1.1a 松散偶合多处理机n处理机之间的连接频带比较低n通过输入输出接口连接,处理机间互为外围设备进行连接n如

3、IBM公司的机器，都可以通过通道到通道的连接器CTC把两个不同计算机系统的IOP连接起来n通过并口或串口把多台计算机连接起来n如用串行口加一个MODEL拨号上网n也可以直接连接n多台计算机之间的连接需要有多个接口n通过Ethernet网络接口连接多台计算机n速度达10Mb、100Mb、1GbnMynet已经达到1.28Gb和2.56Gbn当通信速度要求更高时，可通过一个通道和仲裁开关CAS(Channel and Arbiter Switch)直接在存储器总线之间建立连接n在CAS中有一个高速的通信缓冲存储器5LM0IOP0互连网络CPU0LM0IOP0CPU0LM0IOP0CPU0通过多输入

4、输出输出口连接的多处理机6LMIOP互连网络CPUCAS模块LMIOPCPUCAS模块n-1通过消息传送系统连接的松散耦合多处理机79.1.1b 紧密偶合多处理机n处理机之间共享主存储器，通过高速总线或高速开关连接n主存储器有多个独立的存储模块n每个CPU能够访问任意一个存储器模块n通过映象部件MAP把全局逻辑地址变换成局部物理地址n通过互连网络寻找合适的路径，并分解访问存储器的冲突n多个输入输出处理机IOP也连接在互连网络上，I/O设备与CPU共享主存储器n处理机个数不能太多，几个到十几个n紧密偶合方式要求有很高通信频带。n可以采用如下措施n(1)采用高速互连网络n(2)增加存储器模块个数，

5、一般nRn尽量往前推，不足最大任务数的余数分给一个P-C2322266663*(2+2+2+2)=24444625M个任务平均分配给N台处理机的最佳分配方法n最大任务数每台分 个任务n分得最大任务数的有 台处理机n如果M/N 0n则另有1台处理机分得剩下的 个任务n剩下的 台处理机不分配任何任务n处理机任务数有3个取值：、0n如101个任务平均分给50台处理机n每台分给 =3个任务,有 =33台处理机n另有1台处理机分给 101 mod 3=2个任务n剩下的 50-33-1=16 台处理机不分配任务NMM/NM/NMM/mod1/NMMN50/1013/101NM/NMM/mod26n假设Ki

6、个任务分给了第i台处理机n第一项求出N台处理机中最大执行时间n第二项计算出Ki与(M-Ki)任务之间两两通信的开销时间,第二项是关于Ki的二次函数n其中，Ki最多有3个取值：、0n当M是N的倍数时，有：n当R/CM/2时采用平均分配方法n当R/CM/2时采用集中分配方法)(2)(21221NiiNiiiKMCNMRKMKCNMR总处理时间NM/NMM/mod)11(22NCMNRMC总处理时间27多处理机系统的加速比n一个计算问题在一台处理机上运行时间与在多处理机系统上运行时间的比值称为多处理机系统的加速比n当M 是N 的倍数时，有n如果M 和N 较小，R/C 较大，即分母中的第一项远大于第二

7、项，则加速比与处理机台数N 成正比n当处理机台数N很大，加速比 n即加速比趋近于一个常数n这时再增加处理机，性能的提高很小，与所增加的成本相比是不值得的NiiKMCNMRRM1222）（加速比21)222）（加速比NMCRNCRNMMCNRMRMCMR2289.2.3 随机模型n略299.2.4 通信开销为线性的模型n略309.2.5 完全重叠通信的理想模型n略319.2.6 具有多条通信链的模型n略32几个模型的总结n(1)多处理机系统结构所需的额外开销，包括调度，对共享资源的竞争，同步，处理机之间通信等n串行机和向量机(或别的单指令流机)系统结构中不存在n(2)当运行某个程序的处理机数目增

8、加时，用于计算的那部分时间将减少，而额外开销时间却增加了n实际上，额外开销的增加可能比处理机数目的线性增加更快33几个模型的总结n(3)R/C比值表示当一个程序在某一特定系统结构上执行时，程序执行时间(运行时间)与额外开销时间(通信时间)的比值n该比值越大，越有利于计算过程n因为随着R/C比值的增加属于额外开销的时间相对减少了n如果将整个计算分成几大部分而不是很多小部分从而获得较大的R/C值，那么，并行程度将大为降低，也就限制了在多处理机上能够获得的加速比n一方面，R/C要足够小使能并行执行的任务数目较多n另一方面，R/C要足够大以免额外开销太大n由于这个矛盾，不能期望简单地通过增加处理机数目

9、制造出高速的多处理机系统n处理机数目究竟多少才能使价格和性能都比较合理n其实存在一个极大值，这个值很大程度上依赖于机器的系统结构，基本技术(尤其是通信技术)和每一个具体应用问题的性质349.2.7 多处理机模型n略359.3 多处理机的Cache一致性n在并行处理机和多处理机系统中，采用局部Cache会引起Cache与共享存储器之间的一致性问题n9.3.1 问题由来n9.3.2 监听协议n9.3.3 基于目录的协议369.3.1 问题由来n出现不一致性问题的原因有三个n共享可写的数据n进程迁移nI/O传输371、写共享数据引起的不一致性n使用多个局部Cache时，可能发生Cache不一致性问题

10、n共享可写数据引起的Cache不一致性n当P1把X的值写为X之后，如果P1采用写通过策略，内存中的内容也变为X，但是P2处理机Cache中的内容还是Xn如果P1采用写回策略，内存中的内容还是X，当P2处理机要读X时，读到的是X而不是X 处理机 Cache 总线 共享 存储器 更新之前 写通过方式 写回方式 P1 P2 X X X P1 P2 X X X P1 P2 X X X 382、进程迁移引起的数据不一致性nP1和P2中都有共享数据X的拷贝nP2修改了X，采用写通过方式，所以内存中的X修改成了X。n如果该进程迁移到P1上，这时，P1的Cache中仍然是XnP1中有共享数据X的拷贝，而P2中

11、没有该共享数据，nP1进程对X进行了修改，如果采用了写回方式，暂时没有对内存中的数据进行修改。n如果该进程迁移到了P2上，P2运行时从内存中读到是X 处理机 Cache 总线 共享 存储器 更新之前 写通过方式 写回方式 P1 P2 X X X P1 P2 X X X P1 P2 X X X 393、I/O造成数据不一致性n如果P1和P2在各自的局部Cache中都有X的拷贝，当I/O将一个新数据X写入存储器时就导致了存储器和Cache之间的数据不一致性n如果两个局部Cache中都有X的拷贝，并采用写回方式，当P1把X修改成X之后，输出部件读X，存储器就把X传给了输出部件 处理机 Cache 总

12、线 存储器 I/O 存储器 输入 存储器 输出 更新之前 写通过方式 写回方式 P1 P2 X X X P1 P2 X X X P1 P2 X X X X X 40n一种解决I/O操作引起数据不一致性的方法是把I/O处理机分别连接到各自的局部Cache上n这样，I/O处理机就能和CPU共享Cachen只要能够保证各Cache之间以及Cache和内存之间的数据一致性，就能够保证I/O操作的一致性419.3.2 监听协议n两类解决Cache不一致性问题的协议n监听协议n基于目录的协议n在总线互连的多处理机系统中，解决Cache不一致性通常采用监听协议n在其他多处理机系统中，解决Cache不一致性通

13、常采用基于目录协议421、两种监听协议n使用监听协议，有两种方法n方法一：方法一：写无效(Write Invalidate)策略，在本地Cache的数据块修改时使远程数据块都无效n方法二：写方法二：写更新(Write Update)策略，在本地Cache数据块修改时通过总线把新的数据块广播给含该数据块的所有其他Cachen采用写无效或写更新策略与Cache采用写回方式(Write Back)还是写通过方式(Write Through)无关n如果Cache采用的写通过方式，在使远程数据块无效或更新其他Cache的同时，还要同时修改共享存储器中的内容43Cache采用写通过方式时的写无效策略和写更

14、新策略n由于写更新策略在本地Cache修改时需要通过总线把修改过的数据块广播给所有含该数据块的其他Cache，增加了总线的负担n大部分多处理机系统使用写无效策略 处理机 Cache 总线 共享 存储器 更新之前 写无效策略 写更新策略 P1 P2 X X X P1 P2 X I X P1 P2 X X X 442、采用写通过方式的Cachen数据块有两种状态:有效和无效n有效表示该数据块内容正确，两种状态的转换如图nRL、WL表示本地处理机对Cache的读操作和写操作nRR、WR表示远程处理机对Cache中相同内容数据的读操作和写操作 RL,WLRL,WL RR,WR RR 有效 无效 WR4

15、53、采用写回方式的Cachen只读状态表示整个系统中有多个数据块拷贝是正确的n读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，即在整个系统中只有一个数据块拷贝正确n对于只读的数据块，n本地的和远程的读操作都是安全的，n本地的写操作将使状态转移为读写，n远程的写操作将使之变为无效n对于读写状态的数据块，n本地的读、写操作都是安全的，n而远程的读操作将数据块传递给远程处理机的Cache，使两个Cache都转移至只读状态，n远程写操作使远程处理机Cache转移至读写状态，而本地Cache转移至无效状态n对于无效状态，n本地读操作，使状态转移至只读；n本地写操作，使状态转移至读写，

16、同时使其他Cache中相应数据块的状态转移为无效状态；n其他操作不会引起从无效状态向其他状态的转移46采用写回方式的Cache状态图 WLRL,WL RL,RR 读写 只读 RR WL WR WR RL 无效 RR,WR采用写回方式的采用写回方式的 CacheCache 状态图状态图RL：本地处理机对 Cache 的读操作WL：本地处理机对 Cache 的写操作 RR：远程处理机对 Cache 中相同内容数据的读操作 WR：远程处理机对 Cache 中相同内容数据的写操作474、写一次(Write-Once)协议n1983年James Goodman提出写一次Cache一致性协议n第一次写Ca

17、che采用写通过方式，以后采用写回方式n整个系统中只有一份正确的拷贝n为了区分第一次写，把“读写”状态分为：“保留(Reserved)”和“重写(Dirty)”。n共有4种状态n(1)有效(Valid,相当于写回方式中的只读)n从存储器读入的并与存储器一致的Cache数据块n(2)无效(Invalid)n在Cache中找不到或Cache中的数据块已作废n(3)保留(Reserved)n数据从存储器读入Cache后只被写过一次nCache和存储器中的拷贝都是正确n(4)重写(Dirty)nCache中的数据块被写过多次，且是唯一正确的数据块n此时存储器中的数据块不正确48写一次协议的状态图nRl

18、、Rr、Wl、Wr分别表示本地读、远程读、本地写、远程写49CPU读Cache,有两种可能性n(1)数据块在Cache中存在(包括有效、保留或重写)nCPU直接读取数据，Cache状态不变n(2)Cache中的数据块处于无效状态n触发读缺失事件n如果存在处于有效、保留或重写状态的相应数据块n将其调入本地Cachen在相应数据块处于重写状态时，还要同时禁止存储器操作n如果不存在处于有效、保留或重写状态的相应数据块n只有存储器中是唯一正确的拷贝n直接从存储器中读入n把读入Cache中的相应数据块置为“有效”状态50CPU写Cache,也有两种可能n(1)写命中n当Cache处于“有效”状态时，n采

19、用写通过方式，把写入Cache的内容同时写入存储器，n将Cache的状态转移为“保留”，n将其他Cache的相应数据块状态置为“无效”n当Cache处于“保留”或“重写”态时，n使用写回方式，nCache的状态转移至“重写”,n其他的存有相同内容的Cache处于“无效”态n(2)写不命中n将数据块调入Cache，n采用写通过方式,同时写存储器;n将本地Cache的状态置为“保留”，n同时将其他Cache的状态置为“无效”51n写一次协议的优点n减少大量的无效操作，提高了总线效率n缺点n当主存储器的内容无效时,读缺失引起的总线读操作必须禁止访问主存储器n大多数总线不支持这种操作。nIEEE Fu

20、turebus+总线支持该操作529.3.3 基于目录的协议n在非总线结构的多处理机系统中，采用基于目录的Cache一致性协议531、Cache目录结构nCache目录中存放的内容是大量的指针，用以指明块拷贝的地址n每个目录项还有一个重写位，指明是否有一个Cache允许写入数据n根据Cache目录的存放形式，有集中式和分布式两种n根据目录的结构，目录协议分成三类n全映射(Full-Map)目录：存放全局存储器中每个块的有关数据n有限(Limited)目录：每个目录项的指针数固定n链式(Chained)目录：把目录分布到所有Cachen目录的使用规则n当一个CPU对Cache进行写操作时，根据C

21、ache目录的内容将所有其他存有相同内容的Cache拷贝无效，并置重写位n在CPU对Cache进行读操作时n如果读命中，直接读Cachen如果重写位为“0”，则从主存或其他Cache中读入该块，并修改目录542、全映射目录n目录项中有N个处理机位和一个重写位n处理机位表示相应处理机对应的Cache块的状态n重写位为“1”，且只有一个处理机位为“1”，则该处理机可以对该块进行写操作nCache的每个数据块有两个状态位:一位表示数据块是否有效，另一位表示有效块是否允许写n图(a)表示全系统中所有Cache中都没有X的拷贝n图(b)表示三个处理机都对X有过读请求n图(c)表示P3处理机获得对X的写权

22、限之后的状态 读X 读X 读X 写X (a)(b)(c)P 1 P 2 P 3 Cache1 Cache2 Cache3 X:共享存储器 C 0 0 0 数据 P 1 P 2 P 3 Cache1 X：数据 Cache2 X：数据 Cache3 X：数据 X:共享存储器 0 1 1 1 数据 P 1 P 2 P 3 Cache1 Cache2 Cache3 X：数据 X:共享存储器 1 0 0 1 数据 55n从第二种状态转移至第三种状态的过程如下n(1)Cache3发现包含X单元的块是有效的，但是不允许写n(2)Cache3向包含X单元的存储器模块发写请求，并暂停P3的工作n(3)该存储器模

23、块发无效请求至Cache1和Cache2n(4)Cache1和Cache2接到无效请求后，将对应块置为无效态，并发回答信号给存储器模块n(5)存储器模块接到Cache1和Cache2的回答信号后，置重写位为“1”，清除指向Cache1和Cache2的指针，发允许写信号到Cache3n(6)Cache3接到允许写信号，更新Cache状态，并激活P3n全映射目录协议的效率比较高n但开销与处理机数目的平方成正比，不具有扩展性。563、有限目录n处理机数目为N，限制目录大小为O(Nlog2N)n目录指针需要对N进行二进制编码，每个指针占log2N位，目录所占的总存储空间与(O(Nlog2N)成正比n目

24、录项数为2，当Cache1和Cache2中都有X的拷贝时，若P3请求X，则必须在Cache1和Cache2中选择一个使之无效，这种替换过程称为驱逐n有限目录的驱逐需要一种驱逐策略，n驱逐策略的好坏对系统的性能具有很大的影响。n驱逐策略与Cache替换策略在很多方面是相同的 读 X (a)(b)有限目录的驱逐 P1 P2 P3 Cache1 X：数据 Cache2 X：数据 Cache3 X:共享存储器 C 数据 P1 P2 P3 Cache1 X：数据 Cache2 Cache3 X：数据 X:共享存储器 C 数据 574 链式目录n通过维护一个目录指针链来跟踪共享数据拷贝n当P1读X时，存储

25、器送X到Cache1，同时写Cache1的一个链结束指针CT，在存储器中也保存一个指向Cache1的指针n当P2读X时，存储器送X给Cache2，同时给Cache2一个指向Cache1的指针，存储器则保存一个指向Cache2的指针 读 X 写 X (a)(b)链式目录 P1 P2 P3 Cache1 X：数据 Cache2 Cache3 X:共享存储器 C 数据 CT P1 P2 P3 Cache3 X:共享存储器 C 数据 Cache1 X：数据 CT Cache2 X：数据 58n当某一个处理机需要写X时，它必须沿整个目录链发送一个数据无效信息。在收到所有相关处理机的回答信号之后，存储器才

26、给该处理机写允许权nCache中的数据块需要替换时，把该Cache从目录链中删除n(1)把Cachei+1的指针指向Cachei-1。在Cachei中可以存放别的数据块n(2)使Cachei及链中位于其后的所有Cache中的单元X无效n(3)使用双向链。在替换时不再需要遍历整个链。但指针增加了一倍，一致性协议也更加复杂n优点：不限制共享数据块的拷贝数目，又保持了可扩展性。n指针的长度以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机数目无关n缺点：链式目录的复杂程度超过了前两种目录599.4 多处理机实例n多处理机系统主要有四大类：n(1)多向量处理机系统n如CRAY YMP

27、-90,NEC SX-3和FUJITSU VP-2000n(2)SMP(Symmetry MultiProcessors)对称多处理机nSMP(Shared Memory MulptiProcessors)共享存储多处理机 n如SGI Challenge，Sun SparcCenter 2000n(3)MPP(massively parallel processing)大规模并行处理机n如Intel Paragon,CM-5,Cray T3Dn(4)Cluster 机群系统(NOW或COM)n9.4.1 大规模并行处理机(MPP)n9.4.2 对称多处理机(SMP)n9.4.3 机群系统(Cl

28、uster)609.4.1 大规模并行处理机(MPP)n科学计算中的重大课题要求提供3T性能n(1)1 Teraflops计算能力n(2)1 Terabyte主存储器n(3)1 Terabyte/s 输入输出频带宽度n目前，速度还慢1000倍左右，存储容量和I/O带宽差距更大n科学计算中的重大课题n全球气候预报,基因工程,飞行动力学,海洋环流,流体动力学,超导建模,半导体建模,量子染色动力学,视觉n采用的关键技术nVLSIn可扩展技术n共享虚拟存储技术61虚拟共享存储器(Shared Virtual Memory)n也称为共享分布存储器(Distributed Shared Memory)n物

29、理上分布存储器，逻辑上共享存储器n虚拟共享存储器的优点n编程容易,系统结构灵活n可扩充性好,有较好的软件移植性n与消息传递方式相比，程序运行效率高，主要原因n(1)数据块缓存在本地(内存或Cache中),可以多次使用n(2)通信时间分散，提高了并行性n(3)扩大存储空间，减少换页操作n虚拟共享存储器实现途径n(1)硬件实现,利用Cache技术。需要增加专用硬件n(2)操作系统和库实现，通过虚拟存储机制取得共享和一致性。n在松耦合的分布存储多处理机上，不需要增加任何硬件n(3)编译实现，自动将共享访问转换成同步和一致原语n大多数系统采用途径(1)和(2)，或这两种途径结合实现621、同步的MIM

30、D机器nSIMD与MIMD的优点结合在一起nCM-5的同步MIMD结构能够同时支持SIMD与MIMD两种并行计算方式n数据并行可采用SIMD模式、多SIMD模式或同步MIMD模式 处理机结点 控制处理机 I/O 接口 控制网格 数据网格 诊 断 网 格 NI P M NI P M NI P M NI P M NI P M NI NI I/O I/O 63CM-5n32到16384个处理器结点n每个结点有一个SPARC处理机，32MB存储器，64位浮点和整数操作，速度为128Mflops的向量处理部件n控制处理机1到几十台n根据需要配置存储器和磁盘n输入输出接口与图形设备、海量辅助存储器以及高性

31、能网络相连n占地面积为30米30米，峰值速度超过1Tflopsn三个网络：数据网络、控制网络和诊断网络n数据网络提供点对点通信n控制网络提供广播、同步、扫描和系统管理功能n诊断网络从后台访问所有系统硬件，测试系统完整性，检测和隔离错误n数据网络和控制网络有很好的可扩展性，与处理机类型无关n可以划分成一个或多个分区供用户使用n每个分区一台控制处理机，一组处理结点，数据和控制网络的专用部分n允许任何分区中的进程可以访问任何I/O设备642、CM-5网络结构n数据网络采用胖树型网n数据处理结点、控制处理机和I/O通道都位于胖树的叶子上n利用胖树的层次结构特性，可以划分一棵子树给一个用户 65n采用4

32、元胖树实现，每个内部开关结点由n个寻径器芯片组成。每个寻径器与4个子芯片和2个或4个父芯片相连n可以分配不同的子树处理不同的作业，子树的大小可以任意n为了把消息从一台处理机传送到另一台处理机，首先沿树将消息向上传送到离两台处理机最近的公共祖先，然后向下传送到目的处理机n每台处理机与数据网络有两条连接通路，每个叶子结点的输入和输出的频宽为40兆字节/秒n当一个消息沿树向上传送时，使用哪条父连接通路则有几种选择663、控制处理机n控制处理机由CPU、存储器、本地磁盘、网络接口、以太网组成。它相当于一台标准工作站n网络接口通过控制网络和数据网络使处理机与系统的其它部分相连n控制处理机专门执行管理功能

33、，不需要高性能的运算部件n每台控制处理机运行操作系统，负责并行处理资源的管理n一部分控制处理机管理用户区的计算资源，其它管理I/O资源 数据网络 控制网络 标准工作站 本地网络 存储器 网络接口 CPU I/O I/O 674、处理结点n采用SPARC处理器，利用重叠寄存器窗技术，实现快速的进程切换，使不同时间不同用户分区能够动态地使用处理结点n网络接口通过控制网络和数据网络将结点与系统的其它部分相连n向量部件执行由标量处理机发出的向量指令，每个向量部件有一个流水ALU和64个64位的寄存器n每条向量指令可能传送给一个指定的向量部件、或一对向量部件、或同时广播给所有4个向量部件n标量处理机负责

34、地址转换和循环控制，与向量部件的操作并行执行n每个结点的峰值速度为128Mflopsn16384个处理结点的总峰值速度为21427=221 Mflops=2Tflopsn网络的系统结构设计，做到与所选择的处理器无关68n处理结点基本结构n带向量部件的处理结点 数据网络 控制网络 64 位总线 64 位总线 CPU 网络接口 存储器 存储控制器 存储器 存储器 存储器 数据网络 控制网络 64 位总线 标量处理机 网络接口 存储器 存储器 存储器 存储器 向量部件 向量部件 向量部件 向量部件 699.4.2 对称多处理机(SMP)nSMP称为共享存储多处理机(Shared Memory mul

35、ptiProcessors)n也称为对称多处理机(Symmetry MultiProcessors)n1 三种模型n(1)UMA多处理机n均匀存储器存取模型(Uniform Memory Access)n存储器被所有处理机均匀共享n所有处理机对所有存储单元具有相同的存取时间n每台处理机有局部Cachen外围设备可以共享n(2)NUMA多处理机n非均匀存储器存取(Nonuniform Memory Access)模型n存储器访问时间随存储单元的位置不同而变化。n共享存储器物理上是分布在所有处理机中的本地存储器n所有局部存储器地址空间的集合就组成了全局地址空间n处理机访问本地存储器比较快，访问属于

36、另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟70系统互连网络NUMA多处理机模型P1LM1P2LM2PnLMn系统互连网络(总线、交叉开关、多级网络)UMA多处理机模型P1P2PnSM1SM2SM2I/O71(3)COMA多处理机n只有Cache的存储器结构(Cache-Only Memory Architecture)模型nCOMA是一种只用Cache的多处理机系统n实际上，COMA模型是NUMA模型的一种特例，后者分布存储器换成了Cachen在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址空间n远程Cache访问通过分布Cache目录进行n共享存储

37、系统拥有统一的寻址空间，程序员不必参与数据分配和传输72互连网络COMA多处理机模型D1Cache1P1D2Cache2P2DnCachenPnCOMA多处理机模型732、S2MP结构n1996年SGI Origin 2000服务器，采用S2MP并行计算机体系结构n可扩展共享存储器多处理(Scalable Shared-memory MultiProcessing)nS2MP实际上是NUMA多处理机系统，采用分布存储器，通过cache对系统的共享和私有数据都进行缓存，以达到高性能n从用户编程角度看，S2MP是一种共享存储的多处理机系统nS2MP的主要特点：易编程、可扩展n(1)编程简单，使用方

38、便n(2)可扩展性好，增加处理器数目不受总线带宽的限制n(3)通信开销小，可以开发程序中的细粒度并行性nS2MP的关键技术n(1)高速无阻塞互连网络，增加系统的通信带宽n(2)采用分布式存储器，随处理器数目的增加自动增加存储器带宽n(3)引入cache，降低访存时延n(4)所有存储器统一编址，提供单一的地址空间n(5)在每个处理器结点上增加一个目录存储器，维护cache一致性74S2MP结构 P：处理机，C：Cache，M：主存储器，D：目录存储器 高 速 互 连 网 络 M1 C1 1 D1 M2 C2 2 D2 Mn Cn n Dn 753.SGI Origin 2000系列服务器 nOr

39、igin 2000将SMP、MPP、NOW的优点结合起来nSMP易编程，MPP可扩展性，NOW可用性n有4种机型nOrigin 2000，塔式系统，最多4个处理器nOrigin 2000 Deskside，桌边服务器，最多8个处理器nOrigin 2000 Rack，机柜服务器，处理器数目最多为16个nCray Origin 2000，支持128个处理器n是S2MP结构的典型实现，地址空间成指数增长，连续可扩展最多可以扩展至1024个处理器，具有高带宽和低时延n关键技术nCrayLink，多重交叉开关互连技术，用于连接处理器、存储器、I/O设备等nCellular IRIX，蜂窝式操作系统，实

40、现从小系统到大系统的连续扩展76 Origin 2000系列服务器结构：n(1)结点板n每个结点板(Origin 2000的主板)有一到两个R10000处理器、二级cache、主存储器、目录存储器、HUB、I/O接口、互连网络路由器接口R10000Secondarycache1MB/4MBR10000Secondarycache1MB/4MB780MB/S peakMain MemoryDirectoryMemoryBX ASICHUB ASICAddress/ControlDirectory dataDirectory address/control780MB/S peak780MB/S78

41、0MB/SRouter780MB/SXIO780MB/S77HUB结构nHUB有四个双向的端口n每个端口的单向速率800MB/S，双工带宽1.6GB/Sn四个端口分别连接到处理器、主存储器、XIO和互连网络n四个端口在内部以交叉开关互连78HUB ASIC结构Processor InterfaceMemory/Directory InterfaceI/O InterfaceInterconnection FabricOutput FIFOInput FIFOInput FIFOOutput FIFOOutput FIFOInput FIFOInput FIFOOutput FIFOAsynch

42、/Synch InterfaceAsynch Interface79(3)互连网络n互连网络是一组开关组成，称为路由器n允许多个传输同时发生；速度极高，每条链路带宽达到1.6GB/sn互连网络不需要仲裁，也不存在竞争n路由器的核心是6路全交叉开关n峰值通信带宽9.6GB/s80路由器Router ASIC结构CrossbarReceiverSenderLLPSSD/SSRReceiverSenderLLPSSD/SSRReceiverSenderLLPSSD/SSRReceiverSenderLLPSSD/SSRReceiverSenderLLPSSD/SSRReceiverSenderLLP

43、SSD/SSR81(4)存储系统n有一个统一的共享地址空间，存储系统共分为四个层次n第一层：寄存器堆，访问延迟时间最短n第二层：Cache，主Cache在R10000芯片上，二级Cache在结点板上n第三层：本地存储器，在结点板上，包括主存储器和目录存储器n第四层：远程Cache，用于减少访问共享存储空间所需的时间82(8)扩展连接方式n可以构成4、16、32、64、128个处理器的互连拓扑结构n图中：P是处理器、N是结点板、H表示HUB、R表示路由器HPP4个处理器HPP16个处理器=NRNNRNNRNNRNN32个处理器RNNRNNRNNRNNRNNRNNRNNRNN83n两个结点板通过H

44、UB直接连接得到4个处理器的机器n由于路由器提供了两条连接结点板的链路，由一个路由器和两个结点板构成一个模块，利用路由器的其他4个接口可以扩展到不同的规模n使用其中的2条链路，可连接16个处理器n使用其中的3条链路，形成一个立方体，可连接32个处理器n使用4条链路，构成一个4维超立方体，可连接64个处理器n采用Cray Router，最大配置可以达到128个处理器84RNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNN64个处理器RNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNR

45、NNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRNNRRRRRRRR65-128个处理器Cray Router859.4.3 机群系统(Cluster)n1、机群系统的组成n机群系统是n利用高速网络将一组高性能工作站或高档PC机连接起来n在并行程序设计以及可视化人机交互集成开发环境支持下n统一调度，协调处理，实现高效并行处理的系统nCluster、NOW、COWn从结构和结点间的通信方式来看，属于分布存储系统n机群系统中的主机和网络可以是同构的，也可以是异构的。n微处理机技术、网络技术和并行编程环境的发展使得机群系统这一新的并行处理系统形式正成为当前研究的热点n(1)微处理器

46、的性能不断提高n(2)网络技术的进步使得松散耦合系统的通信瓶颈逐步得到缓解n(3)并行编程环境的开发使得新编并行程序或改写串行程序更为容易862、机群系统的特点n(1)系统开发周期短n(2)用户投资风险小n(3)系统价格低n(4)节约系统资源nUC Berkeley计算机系100多台工作站的使用情况调查表明，一般单机系统的使用率不到10%，而机群系统中的资源利用率可达到80%左右n(5)系统扩展性好n(6)用户编程方便873、机群系统的关键技术n(1)高效的通信系统n在用户空间实现通信协议n精简通信协议nActive Message通信机制88nPVM(Parallel Virtual Mac

47、hine)n开始于1989年夏天,美国橡树岭国家实验室(ORNL)n一套并行计算工具软件，支持多用户及多任务运行n支持多种结构的计算机，工作站、并行机以及向量机等n支持C、C+和Fortran语言n自由软件，使用非常广泛n编程模型可以是SPMD或MPMDn具有容错功能，发现一个结点出故障时，自动将之删除(2)并行程序设计环境89nMPI(Message Passing Interface)n在1992年11月至1994年元月产生n能用于大多数并行计算机、计算机机群和异构网络环境n支持C和Fortran两种语言,编程模型采用SPMDnExpress：n美国Parasoft公司推出；能在不同的硬件

48、环境上运行；支持C和Fortran两种程序设计语言nLinda：n美国Yale大学与科学计算协会共同研制；通过函数扩充现并行程序的设计；支持C-Linda、Fortran-Linda等90(3)并行程序设计语言n在多处理机系统中，必须用并行程序设计语言编写程序。或者把已经用串行语言编写的程序转换成并行语言程序之后，才能在多处理机系统上运行n传统串行语言程序转换成并行语言程序的过程称为并行编译n有两种并行编译方式n全自动并行编译与半自动并行编译n全自动并行编译是方向，但实现起来很困难n半自动并行编译又称为交互式并行编译。程序员通过多次与机器对话，找到串行程序中可以并行执行的部分n并行编译器生成代

49、码的形式有多种n并行高级语言程序、并行中间语言程序、并行目标语言程序91(4)负载平衡技术n一个大任务可分解为多个子任务，把多个子任务分配到各个处理结点上并行执行的技术称为负载平衡技术n对于由异构处理结点构成的并行系统，相同的负载在各结点上的运行时间可能不同。因此，准确的负载定义应是负载量与结点处理能力的比值n负载平衡技术的核心就是调度算法，即将各个任务比较均衡地分布到不同的处理结点上并行计算，从而使各结点的利用率达到最大n负载平衡技术分为静态和动态两大类n静态方法n是在编译时针对用户程序的各种信息(任务的计算量和通信关系等)及并行系统本身的状况(网络结构、各结点计算能力等)对用户程序中的并行

50、任务作出静态分配决策n动态方法n是在程序运行过程中实现负载平衡的。它通过分析并行系统的实时负载信息，动态地将任务在各处理机之间进行分配和调整，以消除系统中负载分布的不均匀性。动态负载平衡的算法简单，实时控制，但增加了系统的额外开销92(5)并行程序调试技术n用并行程序设计语言编写程序，比用串行程序设计语言更容易出错n在多处理机系统中，用并行程序设计语言编写程序更加依赖于并行调试工具n并行程序调试的主要困难：并行程序的执行过程不能重现93(6)可靠性技术n在多处理机上运行的程序通常比较大，程序执行时间很长(几十个小时或几十天)。如果在程序执行过程中出现偶然故障(如电源掉电、磁盘满、某一台处理机故