《计算机体系结构》第六章.ppt
《《计算机体系结构》第六章.ppt》由会员分享,可在线阅读,更多相关《《计算机体系结构》第六章.ppt(153页珍藏版)》请在三一办公上搜索。
1、五、加速比的概念 加速比的常规定义 加速比概念的延伸六、非线性流水线的调度 非线性流水线的预约表 延迟禁止表如何建立 初始冲突向量如何确定 状态转移图如何绘制、调度方案、平均延迟指令级高级并行超级处理机 超标量处理机、超长指令字处理机和超流水线处理机,第六章 多机系统1概述,一、并行性概念并行性是指在执行任务过程中可同时进行的运算或操作。1.开发并行性的目的 提高计算机的运行效率,2.并行性的含义 具有双重含义:同时性与并发性 同时性是指两个或两个以上的事件在同一时刻发生。并发性是指两个或两个以上的事件在同一时间间隔内发生。,3.并行性的意义1)并行意味着有多个事件在并行执行,当这些事件都在完
2、成同一性质的处理时,意味着单位时间完成的结果数增加了,从而可提高对数据处理速度。2)并行同样意味着多个事件中并行处理,当这些处理都在为一个目的工作时,从提高可靠性出发,按多数表决法,对多数得出的相同结果具有高的可靠性。3)并行也可能意味着要增加硬件成本,因而 需根据性能价格比来评价这种开销是否合理。,二、从单机向多机发展的三条途径,并行处理的四个等级:单机流水处理中一条指令内多个操作的并行处理;并行处理机多条相同指令的并行处理(指令间);多处理机多个任务的并行处理;多计算机系统多程序(作业)的并行处理。三、多机系统的耦合度1.何谓耦合度多机之间相互的通信控制能力或相互依赖程度,称为多机之间的耦
3、合度。,2.三种耦合度1)最低耦合:多机之间几乎没有共享设备,如仅用二、三条线连接起来的计算机。(如RS232C通信)。2)松散耦合:多机之间有一定的共享设备,如大型的主机与外围机,它们之间共享受主存,I/O通道。但它们之间也可相对独立工作,又如连接在网络上的计算机,连接在局域网上的计算机共享硬盘。处理机间一般通过消息传递系统交换信息,也有通过通道互联实现处理机间的通讯。3)紧密耦合:耦合度最高,相互依赖很强,如阵列式多处理机的CU(控制部件)和PU(处理部件)之间。通过共享主存实现处理机间的通讯,通讯速率受限于主存频宽。,四、多机系统的分类及特点多机系统指的是多处理机系统和多计算机系统。1.
4、多处理机系统 1)各处理机共享I/O通道、有共享主存。2)属于紧耦合。3)表现形式有:并行(阵列)式多处理机系统;分布式多处理机系统。2.多计算机系统 1)各处理机具有自己的I/O通道和主存 2)属于最低耦合或松耦合 3)典型表现为计算机网络。,互连网络:是一种有开关元件按一定的拓扑结构和控制方式构成的网络,用来实现计算机系统中结点之间的相互连接。,五、互连网络,网络拓扑分为静态和动态两种。这里的拓扑是指互联网络中的各个结点间连接关系,通常用图来描述。1.静态拓扑静态拓扑由点点直接相连而成,这种连结方式在程序执行过程中不会改变。如果用图来表示,结点代表开关,边代表通信链路,结点间的链路无源,不
5、能重构,没有直接相连结点间的通信需通过中间结点中转。,2.动态拓扑设置有源开关,可根据需要对连接通路加以重新组合,如单级循环网络和各种多极互连网络等。,六、典型网络的结构1.线性阵列,对N个结点的线性阵列,有N-1条链路,度为2,不对称。N很大时,通信效率很低。,2.环,对N个结点的环,考虑相邻结点数据传送方向:双向环单向环,3.带弦环,对上图中12个结点的带弦双向环,结点度为3结点度为4,4.全链接 全链接是带弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。如下图中N=8个结点的链接:,5.树形,4层的二叉树,树形的扩展:,带环树,这两种结构都可以缓解根结点的瓶颈问题。
6、CM-5采用胖树,6.星形,星形实际上是一种二层树(如右图)。,有N个结点的rr网(其中)。,7.网(格),有N个结点的rr网(其中),网的变形:a.Illiac 网,有N个结点的rr网(其中)。,b.环形网,8.超立方体,4-立方体,一个n-立方体由N=2n个结点构成,它们分布在n维上,每边有两个结点。,9.带环立方体,带环3-立方体,10.k元n-立方体网络,4元3-立方体(隐藏的结点与连接没有画出),传统的环网等价于4元2-立方体。,2 多处理机系统一、伊(ILLIAC)IV阵列式 多处理机系统1.总体结构:最初设计具有四个象限的阵列式多处理机系统,其中,CU为阵列控制部件,A为阵列处理
7、部件。,2.CU的主要功能1)对指令进行译码。2)向阵列处理部件A发出公共地址、公共数据。3)向A发出各种控制命令。CU应当具备高性能的标量处理能力,否则将制约整个阵列处理机的性能。,3.阵列处理部件A1)由64个PU组成,且排列成8*8的阵列结构。,Illiac 网,2)各PU在水平方向上按1进行连接,且以64为模,称为水平螺旋连接。3)各PU在竖直方向上按8进行连接,也以64为模,称为竖直圆柱连接。4.阵列存储器1)每个PU除它们共享的主存外,各PU还有自己的局部存储器。(其总容量是2K64个局部存储器(PEM0 PEM63)共有2K64=128K)2)由于局部存储器随阵列分布,因此又称为
8、阵列分布存储器。,二、阵列式多处理机适应的算法1.二维调和函数的求解 二维调和函数的求解U(x,y):满足二维拉普拉斯方程的函数,即其中:h是网格点的间距,(x,y)为网格点坐标。利用此法计算,又称为平滑或滤波,目的是消除偶然干扰。,2 矩阵加1)有如下两个矩阵,63,57,56,15,9,8,7,1,0,a,a,a,a,a,a,a,a,a,A,=,63,57,56,15,9,8,7,1,0,b,b,b,b,b,b,b,b,b,B,=,63,57,56,15,9,8,7,1,0,c,c,c,c,c,c,c,c,c,C,=,计算C=A+B则:c0=a0+b0 c1=a1+b1 c63=a63+b
9、63,2)阵列存储器分配每个局部存储器占用三个单元,3)完成矩阵的加运算CU向各PU发出有关命令:公共地址K+0和(取操 作数)读命令。因此各PU从K+0单元中分别取出A阵列数据a0a63。第二个公共地址K+1和取操作数,各PU又将K+1单元中的b0b63取出。,CU向各PU发出求和命令,各PU将取出的ai及bi求和,即ci=ai+bi。CU第三次向各PU 发出公共地址K+2和写命令,各PU将ci存入K+2单元。,三、SIMD互连网络1.概述1)互连:实现处理机之间相互连接,称互连。2)互连网络:实现处理机之间相互连接的某种拓扑结构的逻辑电路,称互连网络。3)互连函数:实现处理机之间相互连接的
10、某种拓扑结构的逻辑函数,称互连函数。(表示互连网络的连接规律)4)对互连网络的评价要有利于实现;要有一定的通信频带;要有一定的灵活性,可实现多种连接通信。,5)互连网络的主要类型 从性质上分)立方体(cube)互连网络)PM2I互连网络)混洗交换互连网络 从级数多少来分)单级互连网络)循环互连网络(物理一级但可实现多级)多级互连网络,6)互连函数中,部件(或处理机)的编码。设用n位二进制来表示部件编码,即有:Pn-1Pn-2 P2P1P0当用3位二进制数表示时(即n=3)则有:P2P1P0,2.单级立方体(Cube)互连网络1)立方体互连函数(设n=3)Cube0:仅在第0位上的代码取反,其余
11、各位不变。Cube0(P2P1P0)=P2P1P0 Cube1:仅在第1位上的代码取反,其余各位不变。Cube1(P2P1P0)=P2P1P0 Cube2:仅在第2位上的代码取反,其余各位不变。Cube2(P2P1P0)=P2P1P0,2)实现的连接关系 Cube0 Cube1 Cube2 P2P1P0 P2P1P0 P2P1 P0 P 2P1 P0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0
12、 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 1 1,Cube0可实现8个部件(处理单元),在x方向连接。Cube1可实现8个部件(处理单元),在y方向连接。Cube2可实现8个部件(处理单元),在z方向连接。,3)当n=4时,有P3P2P1P0,则 Cube3(P3P2P1P0)=P3 P2P1 P0 用Cube3可将两个立方体连接起来,构成一个立方体组(四维空间)。当n=5时,有P4P3P2P1P0,则 Cube4(P4P3P2P1P0)=P4 P3 P2P1 P0 用Cube4可将两个立方体组连接起来,构
13、成一个立方体群(五维空间)。4)互连网络的链接关系图,3.单级PM2I互连网络(Plus-Minus2i)1)PM2I互连函数 PM2+i(j)=j+2i PM2-i(j)=j-2i,2)实现的连接关系(设j分别为07,以8为模。),j j+20 j-20 0 1 7 1 2 0 2 3 1 3 4 2 4 5 3 5 6 4 6 7 5 7 0 6,伊机在水平连接采用PM2+0、PM2-0(双向)且以64为模。,3)PM21 PM2+1(j)=j+21=j+2 PM2-1(j)=j-21=j-2,4)当I=3时,有 PM2+3(j)=j+8 PM2-3(j)=j-8 伊阵列式多处理机,在竖直
14、方向上的连接采用PM23以64为模。所以,伊共采用了PM20和PM23实现相互连接(以64为模)。,4.单级混洗交换互连网络1)立方体和PM2I互连函数太规整,为了实现具有随意性连接,采用混洗。2)混洗互连函数:Sh(Pn-1Pn-2P1P0)=Pn-2Pn-3P1P0Pn-1即循环左移一位,n=3时,Sh(P2P1P0)=P1P0P2 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1,3)利用混洗互连网函数将8个部件分为互不相联的四组,如下图:0;1,
15、2,4;3,5,6;7,4)在混洗基础上加入Cube0的交换,即构成混洗交换互连函数。01 23 45 67 可将8个部件实现相互通信。Cube0(Shuffle(bn-1b0)=Cube0(bn-2b0bn-1)=bn-2b0bn-1,5.循环互连网络1)构成:由单级互连网络、多路开关(MUX)、输入寄存器(IR)和输出寄存器(OR)组成。2)目的:利用对单级互连网的重复使用,在一定程度上模拟互连网络的功能。3)特点:,结构简单,易于实现。对单级互连网络的重复使用,往往是机械重复,灵 活性差。重复加入时,重复频率受到限制。,6.描述多级互连网络的三要素1)交换单元的功能 交换单元:是一个具有
16、两个输入,两个输出和一个控制端的五端开关。,双功能交换单元:具有直通和交换两种功能。,四功能交换单元(G为两位):除上述的直通、交换外,还有上播、下播两种。,2)拓扑结构 拓扑结构是各级间出端与入端互连的模式。前述各种单级互连网络的连接模式均可用来组合构成不同的多级互连网络。解决在级与级之间采用何种规则连接,通常采用级间对号连接,如三级立方体互联网络:,3)控制方式 级控制方式:同一级的所有交换单元只用一个控制 信号控制。单元控制方式:同一级的每个交换单元各有各的独立控制信号。部分级控制方式:介于两种控制方式之间,对同一级交换单元来讲,控制信号的数目2个,但小于交换单元数。,1一、并行性概念二
17、、从单机向多机发展的三条途径三、多机系统的耦合度四、多机系统的分类及特点五、互连网络六、典型静态网络的结构2 一、伊(ILLIAC)IV阵列式 二、阵列式多处理机适应的算法三、SIMD互连网络互连网络的主要类型循环互连网络描述多级互连网络的三要素,立方体(Cube)互连网络的拓扑结构,Cube0可实现x方向连接 Cube1可实现y方向连接 Cube2可实现z方向连接,四、典型互连网络的性能分析 1.采用双功能交换单元级控制方式的三级立方体互连网络(由Cube0、Cube1、Cube2三级构成)。1)要求画出3*4=12个交换单元的三级立方体互连网络图。,2)写出控制信号G2G1G0实现的连接关
18、系表。3)画出控制信号G2G1G0实现的连接关系图。4)写出控制信号G2G1G0实现的连接名称。,2.采用级控和部分级控相结合的三级立方体互连网络移数网络1)网络构成:也由Cube0、Cube1、Cube2三级构成。2)控制方式 第一级采用级控制方式(G0)。第二级采用部分级控制方式(G1G2)。第三级采用部分级控制方式(G3G4G5)。,3)控制信号(G5G0)与连接关系表、连接关系图和移数名称。,思考:经3级立方体网络对07八个端子(0 1 2 3 4 5 6 7)进行排列,当进行移2模4变换后得到的这八个端子新的排列应当是,(23016745),3.采用四功能交换单元,级控制方式的三级立
19、方体实现广播式通信1)网络构成:也由Cube0、Cube1、Cube2三级构成。2)实现某个部件向所有部件进行广播式通信(如4#部件)。写出有关交换单元的功能。画出完成广播式通信的通信线路图。写出控制信号G2G1G0。,实现4#部件向07部件完成广播式通信。第一级交换单元C上播:G0=10第二级交换单元GH上播:G1=10第三级交换单元IJKL下播:G2=11,4.对三级立方体互连网络同时通信能力分析,1)第一组部件:05与17同时通信。05号部件通信:A交换 F直通 J交换 17号部件通信:A直通 F交换 L交换 同时对A、F两个交换单元有矛盾要求,所以不能同时实现05、17同时通信。2)第
20、二组部件:50,71 50号部件通信:C交换 G直通 I交换 71号部件通信:D直通 H交换 J交换 没有对交换单元矛盾要求,但第一、二级要采用部分控 制方式或单元控制方式才可同时通信。,5.四级立方体互连网络1)网络构成:由Cube0cube3四级构成(共4*8=32个交换单元)。2)四功能交换单元,广播式通信。例:5号对015号广播式通信。3)控制信号G3G2G1G0与连接关系表、连接关系图及连接关系名称。,2)5号对015号广播式通信:第一级A下播:G0=11 第二级B、C上播:G1=10 第三级DG下播:G2=11 第四级HO上播:G3=10 即 G3G2G1G0=10111011B,
21、3)控制信号G3G2G1G0与连接关系表、连接关系图及连接关系名称。,6.三级混洗交换互连网络1)网络构成:也由Cube2、Cube1、Cube0三级构成,但与三级立方体互连网络有以下两点区别:Cube0与Cube2的位置互换(第一级是Cube2,第三级是Cube0)Cube1中间两个交换单元位置互换。其目的是使级间连接形式与混洗连接一致。(混洗循环左移一位),2)对以下两组部件同时通信能力分析。05,17 05:A交换 F直通 K交换 17:B交换 H交换 L直通 对交换单元无矛盾要求,但第二、三级需采用部分级控制或单元控制。50,71 50:B交换 G直通 I交换 71:D交换 G交换 I
22、直通 对G、I交换单元有矛盾要求,因此不能同时通信。(与三级立方体正好相反逆网络)3)三级混洗交换互连网络的控制信号G2G1G0与连接关系表、关系图、连接名称与三级立方体相似。(略),四、典型互连网络的性能分析 1.采用双功能交换单元级控制方式的三级立方体互连网络。要求画出互连网络图;写出控制信号G2G1G0实现的连接关系表、连接关系图、连接名称。,110,010,000,100,111,001,011,101,Cube1,Cube0,Cube2,2.采用级控和部分级控相结合的移数网络在给定控制信号(G5G0)下的连接关系表、连接关系图和移数名称。,3.采用四功能交换单元的三级立方体实现广播式
23、通信,4.三级立方体互连网络对多组部件同时通信能力分析,给出一组部件:两对部件同时通信涉及的交换单元是否有矛盾要求,决定能否实现同时通信。能实现同时通信时,各级要采用什么控制方式。,5.四级立方体互连网络网络构成广播式通信给定一组控制信号下的连接关系表、连接关系图及连接关系名称6.三级混洗交换互连网络网络构成三级立方体的逆网络给定一组控制信号下的连接关系表、连接关系图及连接关系名称,7.全排列互连网络(教材P213图6-23的问题)1)网络构成:由三级立方体与三级混洗交换互连网络构成。,2)对05,17同时通信能力分析。05:A交换 F直通 K交换 Q直通 S直通 17:B直通 G直通 I直通
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机体系结构 第六
链接地址:https://www.31ppt.com/p-5051810.html