《计算机体系结构》第六章.ppt
《《计算机体系结构》第六章.ppt》由会员分享,可在线阅读,更多相关《《计算机体系结构》第六章.ppt(153页珍藏版)》请在文库网上搜索。
1、五、加速比的概念五、加速比的概念 加速比的常规定义 加速比加速比概念的延伸六、非线性流水线的调度六、非线性流水线的调度 非线性流水线的预约表 延迟禁止表如何建立 初始冲突向量如何确定 状态转移图如何绘制、调度方案、平均延迟指令级高级并行超级处理机指令级高级并行超级处理机 超标量处理机、超长指令字处理机和超流水线处理机 第六章第六章 多机系统多机系统1 1概述概述一、并行性概念一、并行性概念并行性是指在执行任务过程中可同时进行的运算或操作。并行性是指在执行任务过程中可同时进行的运算或操作。1.1.开发并行性的目的开发并行性的目的 提高计算机的运行效率提高计算机的运行效率2.2.并行性的含义并行性
2、的含义 具有双重含义:同时性与并发性具有双重含义:同时性与并发性 同时性同时性是指两个或两个以上的事件在同一时刻发生。是指两个或两个以上的事件在同一时刻发生。并发性并发性是指两个或两个以上的事件在同一时间间隔内是指两个或两个以上的事件在同一时间间隔内发生。发生。3.3.并行性的意义并行性的意义1 1)并并行行意意味味着着有有多多个个事事件件在在并并行行执执行行,当当这这些些事事件件都都在在完完成成同同一一性性质质的的处处理理时时,意意味味着着单单位位时时间间完完成成的的结结果果数数增增加加了了,从从而而可可提提高高对对数数据处理速度据处理速度。2 2)并并行行同同样样意意味味着着多多个个事事件
3、件中中并并行行处处理理,当当这这些些处处理理都都在在为为一一个个目目的的工工作作时时,从从提提高高可可靠靠性性出出发发,按按多多数数表表决决法法,对对多多数数得得出出的的相相同同结结果具有果具有高的可靠性高的可靠性。3 3)并行也可能意味着)并行也可能意味着要增加硬件成本要增加硬件成本,因而,因而 需根据性能价格比来评价这种开销是否合理。需根据性能价格比来评价这种开销是否合理。二、从单机向多机发展的三条途径二、从单机向多机发展的三条途径并行处理的四个等级:并行处理的四个等级:l单机流水处理中一条指令内多个操作的并行处理单机流水处理中一条指令内多个操作的并行处理;l并行处理机多条相同指令的并行处
4、理(指令间)并行处理机多条相同指令的并行处理(指令间);l多处理机多个任务的并行处理多处理机多个任务的并行处理;l多计算机系统多程序(作业)的并行处理。多计算机系统多程序(作业)的并行处理。三、多机系统的耦合度三、多机系统的耦合度1 1.何谓耦合度何谓耦合度多多机机之之间间相相互互的的通通信信控控制制能能力力或或相相互互依依赖赖程程度,称为多机之间的度,称为多机之间的耦合度耦合度。2 2.三种耦合度三种耦合度1 1)最最低低耦耦合合:多多机机之之间间几几乎乎没没有有共共享享设设备备,如如仅仅用用二二、三条线连接起来的计算机。(如三条线连接起来的计算机。(如RS232CRS232C通信)。通信)
5、。2 2)松松散散耦耦合合:多多机机之之间间有有一一定定的的共共享享设设备备,如如大大型型的的主主机机与与外外围围机机,它它们们之之间间共共享享受受主主存存,I/OI/O通通道道。但但它它们们之之间间也也可可相相对对独独立立工工作作,又又如如连连接接在在网网络络上上的的计计算算机机,连连接接在在局局域域网网上上的的计计算算机机共共享享硬硬盘盘。处处理理机机间间一一般般通通过过消消息息传传递递系系统统交交换换信信息息,也也有有通通过过通通道道互互联联实实现现处处理理机机间的通讯。间的通讯。3 3)紧紧密密耦耦合合:耦耦合合度度最最高高,相相互互依依赖赖很很强强,如如阵阵列列式式多多处处理理机机的
6、的CUCU(控控制制部部件件)和和PUPU(处处理理部部件件)之之间间。通通过过共共享享主主存存实实现现处处理理机机间间的的通通讯讯,通通讯讯速速率率受受限限于于主主存存频宽。频宽。四、多机系统的分类及特点四、多机系统的分类及特点多机系统指的是多处理机系统和多计算机系统。多机系统指的是多处理机系统和多计算机系统。1 1.多处理机系统多处理机系统 1 1)各处理机共享)各处理机共享I/OI/O通道、有共享主存。通道、有共享主存。2 2)属于紧耦合。)属于紧耦合。3 3)表现形式有:)表现形式有:并行并行(阵列阵列)式多处理机系统;式多处理机系统;分布式多处理机系统。分布式多处理机系统。2 2.多
7、计算机系统多计算机系统 1 1)各处理机具有自己的)各处理机具有自己的I/OI/O通道和主存通道和主存 2 2)属于最低耦合或松耦合)属于最低耦合或松耦合 3 3)典型表现为计算机网络。)典型表现为计算机网络。互连网络互连网络:是一种有开关元件按一定的拓扑结构和是一种有开关元件按一定的拓扑结构和控制方式构成的网络控制方式构成的网络,用来实现计算机系统中结点用来实现计算机系统中结点之间的相互连接之间的相互连接。五、互连网络五、互连网络网络拓扑分为静态和动态两种。这里的拓扑是指互网络拓扑分为静态和动态两种。这里的拓扑是指互联网络中的各个结点间连接关系,通常用图来描述。联网络中的各个结点间连接关系,
8、通常用图来描述。1.1.静态拓扑静态拓扑静态静态拓扑由点拓扑由点点直接相连而成,这种连结方式在点直接相连而成,这种连结方式在程序执行过程中不会改变程序执行过程中不会改变。如果用图来表示,结点代表开关,边代表通信链路,如果用图来表示,结点代表开关,边代表通信链路,结点间的链路无源,不能重构结点间的链路无源,不能重构,没有直接相连结点间的没有直接相连结点间的通信需通过中间结点中转。通信需通过中间结点中转。2.2.动态拓扑动态拓扑设置有源开关,可根据需要对连接通路加以重新组设置有源开关,可根据需要对连接通路加以重新组合,如单级循环网络和各种多极互连网络等。合,如单级循环网络和各种多极互连网络等。六、
9、典型网络的结构六、典型网络的结构1.1.线性阵列线性阵列 对对N N个结点的线性阵列,有个结点的线性阵列,有N-1N-1条链路,度为条链路,度为2 2,不对称。不对称。N N很大时,通信效率很低。很大时,通信效率很低。2.2.环环对对N N个结点的环,考虑相邻结点数据传送方向:个结点的环,考虑相邻结点数据传送方向:双向环双向环单向环单向环3.3.带弦环带弦环对上图中对上图中1212个结点的带弦个结点的带弦双向双向环,环,结点度为结点度为3 3结点度为结点度为4 4度度为为3 3的的带带弦弦环环度度为为4 4的的带带弦弦环环4.4.全链接全链接 全链接是带弦环的一种特殊情形。链接中的每全链接是带
10、弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。如下个结点和其他结点之间都有单一的直接链路。如下图中图中N=8N=8个结点的链接:个结点的链接:5.5.树形树形4层层的的二二叉叉树树树形的扩展:树形的扩展:带带环环树树二二叉叉胖胖树树这两种结构都可以缓解根结点的瓶颈问题。这两种结构都可以缓解根结点的瓶颈问题。CM-5CM-5采用胖树采用胖树6.6.星形星形 星形实际上是一种二层树(如右图)。星形实际上是一种二层树(如右图)。有有N N个结点的个结点的r r r r网(其中网(其中 )。7.7.网(格)网(格)有有N N个结点的个结点的r r r r网(其中网(其中 )网的
11、变形:网的变形:a.Illiac网 有有N N个结点的个结点的r r r r网(其中网(其中 )。b.b.环形网环形网8.8.超立方体超立方体0-0-立方体立方体1-1-立方体立方体2-2-立方体立方体3-3-立方体立方体4-4-立方体立方体一个一个n-n-立方体立方体由由N=2N=2n n个结点构成,它们分布在个结点构成,它们分布在n n维上,每边有两个结点。维上,每边有两个结点。9.9.带环立方体带环立方体带环带环3-3-立方体立方体10.k10.k元元n-n-立方体网络立方体网络4 4元元3-3-立方体立方体(隐藏的结点与连接没有画出(隐藏的结点与连接没有画出)传统的环网等价于4元2-立
12、方体。2 2 多处理机系统多处理机系统一、伊(一、伊(ILLIACILLIAC)IVIV阵列式阵列式 多处理机系统多处理机系统1 1.总体结构:最初设计具有总体结构:最初设计具有四个象限的阵列式多处理机四个象限的阵列式多处理机系统,其中,系统,其中,CUCU为阵列控制为阵列控制部件,部件,A A为阵列处理部件。为阵列处理部件。2 2.CU.CU的主要功能的主要功能1 1)对指令进行译码。)对指令进行译码。2 2)向阵列处理部件)向阵列处理部件A A发出公共地址、公共数据。发出公共地址、公共数据。3 3)向)向A A发出各种控制命令。发出各种控制命令。CUCU应当具备高性能的标量处理能力,否则将
13、制约整个应当具备高性能的标量处理能力,否则将制约整个阵列处理机的性能。阵列处理机的性能。3 3.阵列处理部件阵列处理部件A A1 1)由由6464个个PUPU组成,且排列成组成,且排列成8*88*8的阵列结构。的阵列结构。Illiac网2)各PU在水平方向上按1进行连接,且以64为模,称为水平螺旋连接。3)各PU在竖直方向上按8进行连接,也以64为模,称为竖直圆柱连接。4.4.阵列存储器阵列存储器1)每个PU除它们共享的主存外,各PU还有自己的局部存储器。(其总容量是2K64个局部存储器(PEM0 PEM63)共有2K64=128K)2)由于局部存储器随阵列分布,因此又称为阵列分布存储器。二、
14、阵列式多处理机适应的算法二、阵列式多处理机适应的算法1.1.二维调和函数的求解二维调和函数的求解 二二维维调调和和函函数数的的求求解解U(x,y):U(x,y):满满足足二二维维拉拉普普拉拉斯斯方方程程的的函函数,即数,即其中:其中:h h是网格点的间距,是网格点的间距,(x,y)x,y)为网格点坐标。为网格点坐标。利用此法计算,又称为利用此法计算,又称为平滑或滤波平滑或滤波,目的是消除偶然干扰。,目的是消除偶然干扰。2 2 矩阵加矩阵加1 1)有如下两个矩阵)有如下两个矩阵6357561598710aaaaaaaaaA =6357561598710bbbbbbbbbB=63575615987
15、10cccccccccC=计算C=A+B则:c0=a0+b0c1=a1+b1c63=a63+b632 2)阵列存储器分配)阵列存储器分配每个局部存储器占用三个单元每个局部存储器占用三个单元3 3)完成矩阵的加运算)完成矩阵的加运算CUCU向各向各PUPU发出有关命令:发出有关命令:公共地址公共地址K+0K+0和(取操和(取操 作作数)读命令。数)读命令。因此各因此各PUPU从从K+0K+0单元中分别取单元中分别取出出A A阵列数据阵列数据a a0 0a a6363。第二个公共地址第二个公共地址K+1K+1和取操和取操作数,各作数,各PUPU又将又将K+1K+1单元中的单元中的b b0 0b b
16、6363取出。取出。CUCU向各向各PUPU发出求和命令,各发出求和命令,各PUPU将取出的将取出的a ai i及及b bi i求和,即求和,即c ci i=a=ai i+b+bi i。CUCU第三次向各第三次向各PU PU 发出公共地址发出公共地址K+2K+2和写命令,各和写命令,各PUPU将将c ci i存入存入K+2K+2单单元。元。三、三、SIMDSIMD互连网络互连网络1.1.概述概述1 1)互连:实现处理机之间相互连接,称互连。)互连:实现处理机之间相互连接,称互连。2 2)互互连连网网络络:实实现现处处理理机机之之间间相相互互连连接接的的某某种种拓拓扑扑结构的逻辑电路,称互连网络
17、。结构的逻辑电路,称互连网络。3 3)互互连连函函数数:实实现现处处理理机机之之间间相相互互连连接接的的某某种种拓拓扑扑结构的逻辑函数,称互连函数。结构的逻辑函数,称互连函数。(表示互连网络的连接规律表示互连网络的连接规律)4 4)对互连网络的评价)对互连网络的评价要有利于实现;要有利于实现;要有一定的通信频带;要有一定的通信频带;要有一定的灵活性,可实现多种连接通信。要有一定的灵活性,可实现多种连接通信。5 5)互连网络的主要类型)互连网络的主要类型 从性质上分从性质上分 )立方体()立方体(cubecube)互连网络互连网络 )PM2IPM2I互连网络互连网络 )混洗交换互连网络)混洗交换
18、互连网络 从级数多少来分从级数多少来分 )单级互连网络)单级互连网络 )循环互连网络(物理一级但可实现多级)循环互连网络(物理一级但可实现多级)多级互连网络)多级互连网络6 6)互连函数中,部件(或处理机)的编码。)互连函数中,部件(或处理机)的编码。设用设用n n位二进制来表示部件编码,即有:位二进制来表示部件编码,即有:P Pn-1n-1P Pn-2 n-2 P P2 2P P1 1P P0 0当用当用3 3位二进制数表示时(即位二进制数表示时(即n=3n=3)则有:则有:P P2 2P P1 1P P0 02.2.单级立方体(单级立方体(CubeCube)互连网络互连网络1 1)立方体互
19、连函数(设)立方体互连函数(设n=3n=3)Cube0:Cube0:仅仅在在第第0 0位位上上的的代代码码取取反反,其其余余各各位位不变不变。Cube0Cube0(P P2 2P P1 1P P0 0)=P=P2 2P P1 1P P0 0 Cube1:Cube1:仅仅在在第第1 1位位上上的的代代码码取取反反,其其余余各各位不变。位不变。Cube1Cube1(P P2 2P P1 1P P0 0)=P=P2 2P P1 1P P0 0 Cube2:Cube2:仅在第仅在第2 2位上的代码取反,其余各位上的代码取反,其余各位不变。位不变。Cube2Cube2(P P2 2P P1 1P P0
20、0)=P=P2 2P P1 1P P0 0 2)实现的连接关系实现的连接关系Cube0 Cube1 Cube2Cube0 Cube1 Cube2P2P1P0P2P1P0P2P1P0P2P1P0000001010100001000011101010011000110011010001111100101110000101100111001110111100010111110101011 Cube0可实现8个部件(处理单元),在x方向连接。Cube1可实现8个部件(处理单元),在y方向连接。Cube2可实现8个部件(处理单元),在z方向连接。3)当n=4时,有P3P2P1P0,则Cube3(P3P2
21、P1P0)=P3P2P1P0用Cube3可将两个立方体连接起来,构成一个立方体组(四维空间)。当n=5时,有P4P3P2P1P0,则Cube4(P4P3P2P1P0)=P4P3P2P1P0用Cube4可将两个立方体组连接起来,构成一个立方体群(五维空间)。4)互连网络的链接关系图3.单级PM2I互连网络(Plus-Minus2i)1)PM2I互连函数 PM2+i(j)=j+2i PM2-i(j)=j-2i2)实现的连接关系(设j分别为07,以8为模。)jj+20j-20017120231342453564675706伊机在水平连接采用PM2+0、PM2-0(双向)且以64为模。3)PM21 P
22、M2+1(j)=j+21=j+2 PM2-1(j)=j-21=j-24)当I=3时,有PM2+3(j)=j+8 PM2-3(j)=j-8伊阵列式多处理机,在竖直方向上的连接采用PM23以64为模。所以,伊共采用了PM20和PM23实现相互连接(以64为模)。4.单级混洗交换互连网络1)立方体和PM2I互连函数太规整,为了实现具有随意性连接,采用混洗。2)混洗互连函数:Sh(Pn-1Pn-2P1P0)=Pn-2Pn-3P1P0Pn-1即循环左移一位,n=3时Sh(P2P1P0)=P1P0P20000000010100101000111101000011010111101011111113)利用混
23、洗互连网函数将8个部件分为互不相联的四组,如下图:0;1,2,4;3,5,6;74)在混洗基础上加入Cube0的交换,即构成混洗交换互连函数。01234567可将8个部件实现相互通信。Cube0(Shuffle(bn-1b0)=Cube0(bn-2b0bn-1)=bn-2b0bn-15.5.循环互连网络循环互连网络1 1)构构成成:由单级互连网络、多路开关(MUX)、输入寄存器(IR)和输出寄存器(OR)组成。2 2)目目的的:利用对单级互连网的重复使用,在一定程度上模拟互连网络的功能。3 3)特点:)特点:结构简单,易于实现。对单级互连网络的重复使用,往往是机械重复,灵 活性差。重复加入时,
24、重复频率受到限制。6.6.描述多级互连网络的三要素描述多级互连网络的三要素1 1)交换单元的功能)交换单元的功能 交换单元:是一个具有两个输入,两个输出和一个控制端的五端开关。双功能交换单元:具有直通和交换两种功能。四功能交换单元(G为两位):除上述的直通、交换外,还有上播、下播两种。2 2)拓扑结构)拓扑结构 拓扑结构是各级间出端与入端互连的模式。前述各种单级互连网络的连接模式均可用来组合构成不同的多级互连网络。解决在级与级之间采用何种规则连接,通常采用级间级间对号连接对号连接,如三级立方体互联网络:3 3)控制方式)控制方式 级控制方式:同一级的所有交换单元只用一个控制 信号控制。单元控制
25、方式:同一级的每个交换单元各有各的独立控制信号。部分级控制方式:介于两种控制方式之间,对同一级交换单元来讲,控制信号的数目2个,但小于交换单元数。11一、并行性概念一、并行性概念二、从单机向多机发展的三条途径二、从单机向多机发展的三条途径三、多机系统的耦合度三、多机系统的耦合度四、多机系统的分类及特点四、多机系统的分类及特点五、互连网络五、互连网络六、典型静态网络的结构六、典型静态网络的结构22一、伊(一、伊(ILLIAC)IV阵列式阵列式二、阵列式多处理机适应的算法二、阵列式多处理机适应的算法三、三、SIMD互连网络互连网络互连网络的主要类型互连网络的主要类型循环互连网络循环互连网络描述多级
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机体系结构 第六