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

《计算机系统机构 ppt 第9章课件.ppt》由会员分享，可在线阅读，更多相关《计算机系统机构 ppt 第9章课件.ppt（93页珍藏版）》请在三一办公上搜索。

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

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

3、器CTC把两个不同计算机系统的IOP连接起来通过并口或串口把多台计算机连接起来如用串行口加一个MODEL拨号上网也可以直接连接多台计算机之间的连接需要有多个接口通过Ethernet网络接口连接多台计算机速度达10Mb、100Mb、1GbMynet已经达到1.28Gb和2.56Gb当通信速度要求更高时，可通过一个通道和仲裁开关CAS(Channel and Arbiter Switch)直接在存储器总线之间建立连接在CAS中有一个高速的通信缓冲存储器,5,通过多输入输出输出口连接的多处理机,6,通过消息传送系统连接的松散耦合多处理机,7,9.1.1b 紧密偶合多处理机,处理机之间共享主存储器，通

4、过高速总线或高速开关连接主存储器有多个独立的存储模块每个CPU能够访问任意一个存储器模块通过映象部件MAP把全局逻辑地址变换成局部物理地址通过互连网络寻找合适的路径，并分解访问存储器的冲突多个输入输出处理机IOP也连接在互连网络上，I/O设备与CPU共享主存储器处理机个数不能太多，几个到十几个紧密偶合方式要求有很高通信频带。可以采用如下措施(1) 采用高速互连网络(2) 增加存储器模块个数，一般nm，取12倍之间(3) 每个存储器模块再分成多个小模块，并采用流水线方式工作(4) 每个CPU都有自己的局部存储器LM(5) 每个CPU设置一个Cache,8,紧密耦合多处理机模型,9,带二维共享存储

5、器、局部Cache及存储器的多处理机,10,多处理机在结构原理上区别于并行处理机的主要特点,(1)多处理机有多个控制器有多个指令部件，对各个PE实现单独的控制，而又相互协调配合。(2)多处理机的外围设备要能够被多个PE分别调用，通过互连网络转接并行处理机的外围设备统一访问主存储器进行程序和数组的有规则的传送。,11,多处理机在结构原理上区别于并行处理机的主要特点,(3)并行处理机由于主要完成数组向量运算，它的PE和MM之间的数据交往是比较有规则的，存储器访问的地址变换功能要求不高，因而互连网络的作用主要放在数据对准上，可以做得比较简单多处理机由于互连网络必须满足各个PE随机地访问主存储器的要求

6、连接模式、频带和路径选择等问题都要复杂得多存储映射部件对每一个PE也是必需的多处理机系统中存储器的数据和存储空间都要被多个处理机共享不能允许每一个PE在运行自己的程序段时直接产生物理地址要利用存储映射部件来满足存储器动态分配和处理机共享数据块的需要,12,9.1.2 多处理机系统的特点,1、结构灵活并行处理机：专用，PE数很多(几千个)，固定有限的通信多处理机：通用，几十个，高速灵活的通信2、程序并行性并行处理机的并行性存在于指令内部，识别比较容易多处理机的并行性存在于指令外部，在多个任务之间，识别难度较大一个简单的例子Y = A+B*C*D/E+F用两个处理机CPU1CPU2B*CD/EA+

7、FB*C*D/EA+B*C*D/E+F,13,9.1.2 多处理机系统的特点,3、并行任务派生并行处理机把同种操作集中在一起，由指令直接启动各PE同时工作多处理机用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务如果任务数多于处理机数，多余的任务进入排队器等待4、进程同步并行处理机仅一个CU，自然是同步的多处理机执行不同的指令，工作进度不会也不必保持相同,先做完的要停下来等待有数据相关和控制相关也要停下来等待要采取特殊的同步措施来保持程序所要求的正确顺序,14,9.1.2 多处理机系统的特点,5、资源分配和进程调度并行处理机的PE是固定的，采用屏蔽手段改变实际参加

8、操作的PE数目多处理机执行并发任务，需用处理机的数目不固定，各个处理机进入或退出任务的时刻不相同，所需共享资源的品种、数量又随时变化提出资源分配和进程调度问题，它对整个系统的效率有很大的影响,15,9.2 多处理机性能模型,引起峰值性能下降的原因是(1)因处理机间通信而产生的延迟(2)一台处理机与其它处理机同步所需的开销(3)没有足够多任务时，一台或多台处理机处于空闲状态(4)由于一台或多台处理机执行无用的工作(5)系统控制和操作调度所需开销研究多处理机的目的提前5年得到速度高10倍的机器-跨越设计、生产工艺的台阶或用1/10的价格获得一台高性能的机器-低成本的组合设计得好，某些适合进行并行处

9、理得应用领域，可达到提前10年得到速度高100倍的机器或用1/100的价格获得一台高性能的机器,16,R/C比值,并行性在很大程度上依赖于R/C比值其中：R代表程序执行时间，C代表通信开销通常：R/C比值小，并行性低。R/C比值大，并行性高如果把作业分解成较大的块，就能得到较大的R/C值，但是所得到的并行性比最大可能的并行性要小得多R/C比值是衡量任务粒度(Granularity)大小的尺度在粗粒度(Coarsegrain)并行情况下，R/C比值比较大，通信开销小在细粒度(Finegrain)并行情况下，R/C比值比较小，通信开销大细粒度并行性需要的处理机多，粗粒度并行性需要的处理机少细粒度并

10、行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务。在极端情况下，一个小任务只完成一个操作,17,9.2.1 基本模型,假设有一个包含M个任务的应用程序，希望在一个由N台处理机组成的系统上以最快的速度执行这个程序先考虑一个仅有两台处理机的系统，然后再逐步增加处理机数目为了模拟性能，需要用公式表示出执行时间和额外开销先承认下面两个假设是成立的，以获得初步结论，然后放宽假设，观察性能如何变化(1)每个任务的执行时间为R个单位时间(2)当两个任务不在同一台处理机上时，其通信所需的额外开销为C个单位时间。当两个任务在同一台处理机上时，通信所需的额外开销为0,18,一个应用程序在两台处理机系统上

11、运行有多种分配方法可以把全部任务都分配给一台处理机而另一台空闲这种分配方法的通信开销最小，但没有利用并行性也可以按各种不同比例将任务分配给两台处理机那么总处理时间是执行时间和额外开销时间之和CPU1CPU2M0M-11M-22.0M,19,用C表示用于通信的时间，其实它还包括系统所有其它额外开销某些情况下，系统的额外开销的操作可与计算过程重叠进行如处理机在执行指令的同时能通过I/O接口进行通信并不是所有的额外开销都可以被屏蔽掉如处理机在访问共享数据或通信通路时可能会发生竞争，处理机在等待同步信号期间处于空闲状态等假设一部分额外开销的操作会增加总处理时间,20,用下列等式表示一个程序的总处理时间

12、总处理时间=Rmax(M-K，K)+C(M-K)K(9.1)M个任务的应用程序，在由N台处理机组成的系统执行C表示用于通信的时间每个任务的执行时间为R个单位总处理时间是两个时间的和一个是执行时间另一个是用于通信和其它额外开销的时间对两台处理机系统，执行时间取两台处理机较大的一个K个任务分配给一台处理机，剩下的(M-K)个任务分配给另一台处理机时，执行时间取R(M-K)和RK中较大的一个K为任务分配参数第二项表示额外开销时间与通信次数成正比例关系通信次数与任务分配方法有关从式(9.1)可知，第一项是K的线性函数，第二项是K的二次函数,21,从式(9.1)可知总处理时间是K的函数，其最小值是多少呢

13、？也就是说，任务如何分配才能获得最小的总处理时间用图解法来求最小处理时间R/C代入式(9.1)，令C=1,22,图9.2 两种不同R/C比值的并行执行时间,对于该模型的结论是当R/CM/2时，把所有任务分配给同一台处理机能使总处理时间最小当R/CM/2时，把任务平均地分配给两台处理机能使总处理时间最小使任务分配参数K=0或K=M/2当M为奇数时，应使K尽可能接近M/2,23,9.2.2 N台处理机系统的基本模型,M个任务分配给N台处理机，求总处理时间的最小值实际的最小值发生在极端分配情况下，或者将所有的任务集中在一台处理机上，或者将任务平均分配给所有处理机先讨论平均分配方法4个任务平均分给3台

14、处理机(P),24,11个任务平均分给5台处理机(P),每个P最大任务数3完全均分，每个P为2个任务，多出的一个分给其中任一个不超出最大任务数3，往前推，若干个3，一个2，其余为0最大任务数尽量小-R尽量往前推，不足最大任务数的余数分给一个P-C,25,M个任务平均分配给N台处理机的最佳分配方法,最大任务数每台分 个任务分得最大任务数的有 台处理机如果M/N 0则另有1台处理机分得剩下的 个任务剩下的 台处理机不分配任何任务处理机任务数有3个取值： 、 、0如101个任务平均分给50台处理机每台分给 =3个任务,有 = 33台处理机另有1台处理机分给 101 mod 3 =2个任务剩下的 50

15、-33-1=16 台处理机不分配任务,26,假设Ki个任务分给了第i台处理机第一项求出N台处理机中最大执行时间第二项计算出Ki与(M-Ki)任务之间两两通信的开销时间,第二项是关于Ki的二次函数其中，Ki最多有3个取值： 、 、0当M是N的倍数时，有：当R/CM/2时采用平均分配方法当R/CM/2时采用集中分配方法,27,多处理机系统的加速比,一个计算问题在一台处理机上运行时间与在多处理机系统上运行时间的比值称为多处理机系统的加速比当M 是N 的倍数时，有如果M 和N 较小，R /C 较大，即分母中的第一项远大于第二项，则加速比与处理机台数N 成正比当处理机台数N很大，加速比 即加速比趋近于一

16、个常数这时再增加处理机，性能的提高很小，与所增加的成本相比是不值得的,28,9.2.3 随机模型,略,29,9.2.4 通信开销为线性的模型,略,30,9.2.5 完全重叠通信的理想模型,略,31,9.2.6 具有多条通信链的模型,略,32,几个模型的总结,(1)多处理机系统结构所需的额外开销，包括调度，对共享资源的竞争，同步，处理机之间通信等串行机和向量机(或别的单指令流机)系统结构中不存在(2)当运行某个程序的处理机数目增加时，用于计算的那部分时间将减少，而额外开销时间却增加了实际上，额外开销的增加可能比处理机数目的线性增加更快,33,几个模型的总结,(3)R/C比值表示当一个程序在某一特

17、定系统结构上执行时，程序执行时间(运行时间)与额外开销时间(通信时间)的比值该比值越大，越有利于计算过程因为随着R/C比值的增加属于额外开销的时间相对减少了如果将整个计算分成几大部分而不是很多小部分从而获得较大的R/C值，那么，并行程度将大为降低，也就限制了在多处理机上能够获得的加速比一方面，R/C要足够小使能并行执行的任务数目较多另一方面，R/C要足够大以免额外开销太大由于这个矛盾，不能期望简单地通过增加处理机数目制造出高速的多处理机系统处理机数目究竟多少才能使价格和性能都比较合理其实存在一个极大值，这个值很大程度上依赖于机器的系统结构，基本技术(尤其是通信技术)和每一个具体应用问题的性质,

18、34,9.2.7 多处理机模型,略,35,9.3 多处理机的Cache一致性,在并行处理机和多处理机系统中，采用局部Cache会引起Cache与共享存储器之间的一致性问题9.3.1 问题由来9.3.2 监听协议9.3.3 基于目录的协议,36,9.3.1 问题由来,出现不一致性问题的原因有三个共享可写的数据进程迁移I/O传输,37,1、写共享数据引起的不一致性,使用多个局部Cache时，可能发生Cache不一致性问题共享可写数据引起的Cache不一致性当P1把X的值写为X之后，如果P1采用写通过策略，内存中的内容也变为X，但是P2处理机Cache中的内容还是X如果P1采用写回策略，内存中的内容

19、还是X，当P2处理机要读X时，读到的是X而不是X,38,2、进程迁移引起的数据不一致性,P1和P2中都有共享数据X的拷贝P2修改了X，采用写通过方式，所以内存中的X修改成了X。如果该进程迁移到P1上，这时，P1的Cache中仍然是XP1中有共享数据X的拷贝，而P2中没有该共享数据，P1进程对X进行了修改，如果采用了写回方式，暂时没有对内存中的数据进行修改。如果该进程迁移到了P2上，P2运行时从内存中读到是X,39,3、I/O造成数据不一致性,如果P1和P2在各自的局部Cache中都有X的拷贝，当I/O将一个新数据X写入存储器时就导致了存储器和Cache之间的数据不一致性如果两个局部Cache中

20、都有X的拷贝，并采用写回方式，当P1把X修改成X之后，输出部件读X，存储器就把X传给了输出部件,40,一种解决I/O操作引起数据不一致性的方法是把I/O处理机分别连接到各自的局部Cache上这样，I/O处理机就能和CPU共享Cache只要能够保证各Cache之间以及Cache和内存之间的数据一致性，就能够保证I/O操作的一致性,41,9.3.2 监听协议,两类解决Cache不一致性问题的协议监听协议基于目录的协议在总线互连的多处理机系统中，解决Cache不一致性通常采用监听协议在其他多处理机系统中，解决Cache不一致性通常采用基于目录协议,42,1、两种监听协议,使用监听协议，有两种方法方法

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

22、块的其他Cache，增加了总线的负担大部分多处理机系统使用写无效策略,44,2、采用写通过方式的Cache,数据块有两种状态: 有效和无效有效表示该数据块内容正确，两种状态的转换如图RL、WL表示本地处理机对Cache的读操作和写操作RR、WR表示远程处理机对Cache中相同内容数据的读操作和写操作,45,3、采用写回方式的Cache,只读状态表示整个系统中有多个数据块拷贝是正确的读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，即在整个系统中只有一个数据块拷贝正确对于只读的数据块，本地的和远程的读操作都是安全的，本地的写操作将使状态转移为读写，远程的写操作将使之变为无效对于读

23、写状态的数据块，本地的读、写操作都是安全的，而远程的读操作将数据块传递给远程处理机的Cache，使两个Cache都转移至只读状态，远程写操作使远程处理机Cache转移至读写状态，而本地Cache转移至无效状态对于无效状态，本地读操作，使状态转移至只读；本地写操作，使状态转移至读写，同时使其他Cache中相应数据块的状态转移为无效状态；其他操作不会引起从无效状态向其他状态的转移,46,采用写回方式的Cache状态图,47,4、写一次(Write-Once)协议,1983年James Goodman提出写一次Cache一致性协议第一次写Cache采用写通过方式，以后采用写回方式整个系统中只有一份正

24、确的拷贝为了区分第一次写，把“读写”状态分为：“保留(Reserved)”和“重写(Dirty)”。共有4种状态(1)有效(Valid, 相当于写回方式中的只读)从存储器读入的并与存储器一致的Cache数据块(2)无效(Invalid)在Cache中找不到或Cache中的数据块已作废(3)保留(Reserved)数据从存储器读入Cache后只被写过一次Cache和存储器中的拷贝都是正确(4)重写(Dirty)Cache中的数据块被写过多次，且是唯一正确的数据块此时存储器中的数据块不正确,48,写一次协议的状态图,Rl、Rr、Wl、Wr分别表示本地读、远程读、本地写、远程写,49,CPU读Cac

25、he,有两种可能性,(1)数据块在Cache中存在(包括有效、保留或重写)CPU直接读取数据，Cache状态不变(2)Cache中的数据块处于无效状态触发读缺失事件如果存在处于有效、保留或重写状态的相应数据块将其调入本地Cache在相应数据块处于重写状态时，还要同时禁止存储器操作如果不存在处于有效、保留或重写状态的相应数据块只有存储器中是唯一正确的拷贝直接从存储器中读入把读入Cache中的相应数据块置为“有效”状态,50,CPU写Cache,也有两种可能,(1)写命中当Cache处于“有效”状态时，采用写通过方式，把写入Cache的内容同时写入存储器，将Cache的状态转移为“保留”，将其他C

26、ache的相应数据块状态置为“无效”当Cache处于“保留”或“重写”态时，使用写回方式，Cache的状态转移至“重写”,其他的存有相同内容的Cache处于“无效”态(2)写不命中将数据块调入Cache，采用写通过方式, 同时写存储器;将本地Cache的状态置为“保留”，同时将其他Cache的状态置为“无效”,51,写一次协议的优点减少大量的无效操作，提高了总线效率缺点当主存储器的内容无效时,读缺失引起的总线读操作必须禁止访问主存储器大多数总线不支持这种操作。IEEE Futurebus+总线支持该操作,52,9.3.3 基于目录的协议,在非总线结构的多处理机系统中，采用基于目录的Cache一

27、致性协议,53,1、Cache目录结构,Cache目录中存放的内容是大量的指针，用以指明块拷贝的地址每个目录项还有一个重写位，指明是否有一个Cache允许写入数据根据Cache目录的存放形式，有集中式和分布式两种根据目录的结构，目录协议分成三类全映射(Full-Map)目录：存放全局存储器中每个块的有关数据有限(Limited)目录：每个目录项的指针数固定链式(Chained)目录：把目录分布到所有Cache目录的使用规则当一个CPU对Cache进行写操作时，根据Cache目录的内容将所有其他存有相同内容的Cache拷贝无效，并置重写位在CPU对Cache进行读操作时如果读命中，直接读Cach

28、e如果重写位为“0”，则从主存或其他Cache中读入该块，并修改目录,54,2、全映射目录,目录项中有N个处理机位和一个重写位处理机位表示相应处理机对应的Cache块的状态重写位为“1”，且只有一个处理机位为“1”，则该处理机可以对该块进行写操作Cache的每个数据块有两个状态位: 一位表示数据块是否有效，另一位表示有效块是否允许写图(a)表示全系统中所有Cache中都没有X的拷贝图(b)表示三个处理机都对X有过读请求图(c)表示P3处理机获得对X的写权限之后的状态,55,从第二种状态转移至第三种状态的过程如下(1) Cache3发现包含X单元的块是有效的，但是不允许写(2) Cache3向包

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

30、g2N位，目录所占的总存储空间与(O(Nlog2N)成正比目录项数为2，当Cache1和Cache2中都有X的拷贝时，若P3请求X，则必须在Cache1和Cache2中选择一个使之无效，这种替换过程称为驱逐有限目录的驱逐需要一种驱逐策略，驱逐策略的好坏对系统的性能具有很大的影响。驱逐策略与Cache替换策略在很多方面是相同的,57,4 链式目录,通过维护一个目录指针链来跟踪共享数据拷贝当P1读X时，存储器送X到Cache1，同时写Cache1的一个链结束指针CT，在存储器中也保存一个指向Cache1的指针当P2读X时，存储器送X给Cache2，同时给Cache2一个指向Cache1的指针，存储

31、器则保存一个指向Cache2的指针,58,当某一个处理机需要写X时，它必须沿整个目录链发送一个数据无效信息。在收到所有相关处理机的回答信号之后，存储器才给该处理机写允许权Cache中的数据块需要替换时，把该Cache从目录链中删除(1) 把Cachei+1的指针指向Cachei-1。在Cachei中可以存放别的数据块(2) 使Cachei及链中位于其后的所有Cache中的单元X无效(3) 使用双向链。在替换时不再需要遍历整个链。但指针增加了一倍，一致性协议也更加复杂优点：不限制共享数据块的拷贝数目，又保持了可扩展性。指针的长度以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机

32、数目无关缺点：链式目录的复杂程度超过了前两种目录,59,9.4 多处理机实例,多处理机系统主要有四大类：(1) 多向量处理机系统如CRAY YMP-90, NEC SX-3和FUJITSU VP-2000(2) SMP (Symmetry MultiProcessors)对称多处理机SMP (Shared Memory MulptiProcessors)共享存储多处理机 如SGI Challenge，Sun SparcCenter 2000(3)MPP (massively parallel processing)大规模并行处理机如Intel Paragon, CM-5, Cray T3D(4

33、) Cluster 机群系统(NOW或COM)9.4.1 大规模并行处理机(MPP)9.4.2 对称多处理机(SMP)9.4.3 机群系统(Cluster),60,9.4.1 大规模并行处理机(MPP),科学计算中的重大课题要求提供3T性能(1) 1 Teraflops计算能力(2) 1 Terabyte主存储器(3) 1 Terabyte/s 输入输出频带宽度目前，速度还慢1000倍左右，存储容量和I/O带宽差距更大科学计算中的重大课题全球气候预报, 基因工程 ,飞行动力学 ,海洋环流, 流体动力学, 超导建模, 半导体建模, 量子染色动力学, 视觉采用的关键技术VLSI可扩展技术共享虚拟存

34、储技术,61,虚拟共享存储器(Shared Virtual Memory),也称为共享分布存储器(Distributed Shared Memory)物理上分布存储器，逻辑上共享存储器虚拟共享存储器的优点编程容易, 系统结构灵活可扩充性好, 有较好的软件移植性与消息传递方式相比，程序运行效率高，主要原因(1) 数据块缓存在本地 (内存或Cache中), 可以多次使用(2) 通信时间分散，提高了并行性(3) 扩大存储空间，减少换页操作虚拟共享存储器实现途径(1) 硬件实现, 利用Cache技术。需要增加专用硬件(2) 操作系统和库实现，通过虚拟存储机制取得共享和一致性。在松耦合的分布存储多处理机

35、上，不需要增加任何硬件(3) 编译实现，自动将共享访问转换成同步和一致原语大多数系统采用途径(1)和(2)，或这两种途径结合实现,62,1、同步的MIMD机器,SIMD与MIMD的优点结合在一起CM-5的同步MIMD结构能够同时支持SIMD与MIMD两种并行计算方式数据并行可采用SIMD模式、多SIMD模式或同步MIMD模式,63,CM-5,32到16384个处理器结点每个结点有一个SPARC处理机，32MB存储器，64位浮点和整数操作，速度为128Mflops的向量处理部件控制处理机1到几十台根据需要配置存储器和磁盘输入输出接口与图形设备、海量辅助存储器以及高性能网络相连占地面积为30米30

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

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

38、并行处理资源的管理一部分控制处理机管理用户区的计算资源，其它管理I/O资源,67,4、处理结点,采用SPARC处理器，利用重叠寄存器窗技术，实现快速的进程切换，使不同时间不同用户分区能够动态地使用处理结点网络接口通过控制网络和数据网络将结点与系统的其它部分相连向量部件执行由标量处理机发出的向量指令，每个向量部件有一个流水ALU和64个64位的寄存器每条向量指令可能传送给一个指定的向量部件、或一对向量部件、或同时广播给所有4个向量部件标量处理机负责地址转换和循环控制，与向量部件的操作并行执行每个结点的峰值速度为128Mflops16384个处理结点的总峰值速度为21427=221 Mflops

39、=2Tflops网络的系统结构设计，做到与所选择的处理器无关,68,处理结点基本结构带向量部件的处理结点,69,9.4.2 对称多处理机 (SMP),SMP称为共享存储多处理机(Shared Memory mulptiProcessors)也称为对称多处理机(Symmetry MultiProcessors)1 三种模型(1) UMA多处理机均匀存储器存取模型(Uniform Memory Access)存储器被所有处理机均匀共享所有处理机对所有存储单元具有相同的存取时间每台处理机有局部Cache外围设备可以共享(2) NUMA多处理机非均匀存储器存取(Nonuniform Memory Ac

40、cess)模型存储器访问时间随存储单元的位置不同而变化。共享存储器物理上是分布在所有处理机中的本地存储器所有局部存储器地址空间的集合就组成了全局地址空间处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟,70,71,(3) COMA多处理机,只有Cache的存储器结构(Cache-Only Memory Architecture)模型COMA是一种只用Cache的多处理机系统实际上，COMA模型是NUMA模型的一种特例，后者分布存储器换成了Cache在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址空间远程Cache访问通过

41、分布Cache目录进行共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输,72,COMA多处理机模型,73,2、S2MP结构,1996年SGI Origin 2000服务器，采用S2MP并行计算机体系结构可扩展共享存储器多处理(Scalable Shared-memory MultiProcessing)S2MP实际上是NUMA多处理机系统，采用分布存储器，通过cache对系统的共享和私有数据都进行缓存，以达到高性能从用户编程角度看，S2MP是一种共享存储的多处理机系统S2MP的主要特点：易编程、可扩展(1) 编程简单，使用方便(2) 可扩展性好，增加处理器数目不受总线带宽的限制(3

42、) 通信开销小，可以开发程序中的细粒度并行性S2MP的关键技术(1) 高速无阻塞互连网络，增加系统的通信带宽(2) 采用分布式存储器，随处理器数目的增加自动增加存储器带宽(3) 引入cache，降低访存时延(4) 所有存储器统一编址，提供单一的地址空间(5) 在每个处理器结点上增加一个目录存储器，维护cache一致性,74,S2MP结构,75,3. SGI Origin 2000系列服务器,Origin 2000将SMP、MPP、NOW的优点结合起来SMP易编程，MPP可扩展性，NOW可用性有4种机型Origin 2000，塔式系统，最多4个处理器Origin 2000 Deskside，桌边

43、服务器，最多8个处理器Origin 2000 Rack，机柜服务器，处理器数目最多为16个Cray Origin 2000，支持128个处理器是S2MP结构的典型实现，地址空间成指数增长，连续可扩展最多可以扩展至1024个处理器，具有高带宽和低时延关键技术CrayLink，多重交叉开关互连技术，用于连接处理器、存储器、I/O设备等Cellular IRIX，蜂窝式操作系统，实现从小系统到大系统的连续扩展,76,Origin 2000系列服务器结构：,(1) 结点板每个结点板(Origin 2000的主板)有一到两个R10000处理器、二级cache、主存储器、目录存储器、HUB、I/O接口、互

44、连网络路由器接口,77,HUB结构,HUB有四个双向的端口每个端口的单向速率800MB/S，双工带宽1.6GB/S四个端口分别连接到处理器、主存储器、XIO和互连网络四个端口在内部以交叉开关互连,78,HUB ASIC结构,79,(3) 互连网络,互连网络是一组开关组成，称为路由器允许多个传输同时发生；速度极高，每条链路带宽达到1.6GB/s互连网络不需要仲裁，也不存在竞争路由器的核心是6路全交叉开关峰值通信带宽9.6GB/s,80,路由器Router ASIC结构,81,(4) 存储系统,有一个统一的共享地址空间，存储系统共分为四个层次第一层：寄存器堆，访问延迟时间最短第二层：Cache，主

45、Cache在R10000芯片上，二级Cache在结点板上第三层：本地存储器，在结点板上，包括主存储器和目录存储器第四层：远程Cache，用于减少访问共享存储空间所需的时间,82,(8) 扩展连接方式,可以构成4、16、32、64、128个处理器的互连拓扑结构图中：P是处理器、N是结点板、H表示HUB、R表示路由器,83,两个结点板通过HUB直接连接得到4个处理器的机器由于路由器提供了两条连接结点板的链路，由一个路由器和两个结点板构成一个模块，利用路由器的其他4个接口可以扩展到不同的规模使用其中的2条链路，可连接16个处理器使用其中的3条链路，形成一个立方体，可连接32个处理器使用4条链路，构成

46、一个4维超立方体，可连接64个处理器采用Cray Router，最大配置可以达到128个处理器,84,85,9.4.3 机群系统 (Cluster),1、机群系统的组成机群系统是利用高速网络将一组高性能工作站或高档PC机连接起来在并行程序设计以及可视化人机交互集成开发环境支持下统一调度，协调处理，实现高效并行处理的系统Cluster、NOW、COW从结构和结点间的通信方式来看，属于分布存储系统机群系统中的主机和网络可以是同构的，也可以是异构的。微处理机技术、网络技术和并行编程环境的发展使得机群系统这一新的并行处理系统形式正成为当前研究的热点(1)微处理器的性能不断提高(2)网络技术的进步使得松

47、散耦合系统的通信瓶颈逐步得到缓解(3)并行编程环境的开发使得新编并行程序或改写串行程序更为容易,86,2、机群系统的特点,(1)系统开发周期短(2)用户投资风险小(3)系统价格低(4)节约系统资源UC Berkeley计算机系100多台工作站的使用情况调查表明，一般单机系统的使用率不到10%，而机群系统中的资源利用率可达到80%左右(5)系统扩展性好(6)用户编程方便,87,3、机群系统的关键技术,(1)高效的通信系统在用户空间实现通信协议精简通信协议Active Message通信机制,88,PVM(Parallel Virtual Machine)开始于1989年夏天,美国橡树岭国家实验室

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

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

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