《计算机体系结构》第六章.ppt

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互连网络互连网络互连网络的主要类型互连网络的主要类型循环互连网络循环互连网络描述多级

26、互连网络的三要素描述多级互连网络的三要素立方体（立方体（Cube）互连网络的拓扑结构互连网络的拓扑结构 Cube0可实现x方向连接 Cube1可实现y方向连接 Cube2可实现z方向连接四、典型互连网络的性能分析四、典型互连网络的性能分析 1.1.采采用用双双功功能能交交换换单单元元级级控控制制方方式式的的三三级级立立方方体体互互连连网络网络（由（由Cube0Cube0、Cube1Cube1、Cube2Cube2三级构成）三级构成）。1 1）要要求求画画出出3*4=123*4=12个个交交换换单单元元的的三三级级立立方方体体互互连连网网络图。络图。2 2）写出控制信号）写出控制信号G G2 2

27、G G1 1G G0 0实现的连接关系表。实现的连接关系表。3 3）画出控制信号）画出控制信号G G2 2G G1 1G G0 0实现的连接关系图。实现的连接关系图。4 4）写出控制信号）写出控制信号G G2 2G G1 1G G0 0实现的连接名称。实现的连接名称。2.2.采用级控和部分级控相结合的三级立方体采用级控和部分级控相结合的三级立方体互连网络互连网络移数网络移数网络1）网络构成：也由Cube0、Cube1、Cube2三级构成。2）控制方式 第一级采用级控制方式（G0）。第二级采用部分级控制方式（G1G2）。第三级采用部分级控制方式(G3G4G5)。3）控制信号（G5G0）与连接关系

28、表、连接关系图和移数名称。思考：思考：经3级立方体网络对07八个端子（0 1 2 3 4 5 6 7）进行排列，当进行移2模4变换后得到的这八个端子新的排列应当是（23016745）3.3.采采用用四四功功能能交交换换单单元元，级级控控制制方方式式的的三三级级立立方方体体实实现现广播式通信广播式通信1 1）网络构成：也由）网络构成：也由Cube0Cube0、Cube1Cube1、Cube2Cube2三级构成。三级构成。2 2）实实现现某某个个部部件件向向所所有有部部件件进进行行广广播播式式通通信信（如如4#4#部部件件）。写出有关交换单元的功能。写出有关交换单元的功能。画出完成广播式通信的通信

29、线路图。画出完成广播式通信的通信线路图。写出控制信号写出控制信号G G2 2G G1 1G G0 0。实现实现4#4#部件向部件向0 07 7部件完成广播式通信。部件完成广播式通信。第一级交换单元第一级交换单元C C上播：上播：G0=10G0=10第二级交换单元第二级交换单元GHGH上播：上播：G1=10G1=10第三级交换单元第三级交换单元IJKLIJKL下播：下播：G2=11G2=114.对三级立方体互连网络同时通信能力分析对三级立方体互连网络同时通信能力分析1）第一组部件：05与17同时通信。05号部件通信：A交换 F直通 J交换 17号部件通信：A直通 F交换 L交换 同时对A、F两个

30、交换单元有矛盾要求，所以不能同时实现05、17同时通信。2）第二组部件：50，71 50号部件通信：C交换 G直通 I交换 71号部件通信：D直通 H交换 J交换 没有对交换单元矛盾要求，但第一、二级要采用部分控 制方式或单元控制方式才可同时通信。5.5.四级立方体互连网络四级立方体互连网络1）网络构成：由Cube0cube3四级构成（共4*8=32个交换单元）。2）四功能交换单元，广播式通信。例：5号对015号广播式通信。3）控制信号G3G2G1G0与连接关系表、连接关系图及连接关系名称。2）5号对015号广播式通信：第一级A下播：G0=11 第二级B、C上播：G1=10 第三级DG下播：G

31、2=11 第四级HO上播：G3=10 即 G3G2G1G0=10111011BG3G2G1G0=10111011B3）控制信号控制信号G3G2G1G0与连接关系表、连接关系图及连接关系与连接关系表、连接关系图及连接关系名称。名称。6.6.三级混洗交换互连网络三级混洗交换互连网络1）网络构成：也由Cube2、Cube1、Cube0三级构成，但与三级立方体互连网络有以下两点区别：Cube0与Cube2的位置互换（第一级是Cube2，第三级是Cube0）Cube1中间两个交换单元位置互换。其目的是使级间连接形式与混洗连接一致。（混洗循环左移一位）2）对以下两组部件同时通信能力分析。05，17 05：

32、A交换 F直通 K交换 17：B交换 H交换 L直通 对交换单元无矛盾要求，但第二、三级需采用部分级控制或单元控制。50，71 50：B交换 G直通 I交换 71：D交换 G交换 I直通 对G、I交换单元有矛盾要求，因此不能同时通信。（与三级立方体正好相反逆网络）3）三级混洗交换互连网络的控制信号G2G1G0与连接关系表、关系图、连接名称与三级立方体相似。（略）四、典型互连网络的性能分析四、典型互连网络的性能分析 1.1.采采用用双双功功能能交交换换单单元元级级控控制制方方式式的的三三级级立立方方体体互互连连网网络络。要求要求l画出互连网络图画出互连网络图;l写出控制信号写出控制信号G2G1G

33、0实现的连接关系表、连接关系实现的连接关系表、连接关系图、连接名称。图、连接名称。110010000100111001011101Cube1Cube0Cube22.2.采采用用级级控控和和部部分分级级控控相相结结合合的的移移数数网网络络在在给给定定控控制制信信号号（G5G0）下的连接关系表、连接关系图和移数名称。下的连接关系表、连接关系图和移数名称。3.采用四功能交换单元的三级立方体实现广播式通信采用四功能交换单元的三级立方体实现广播式通信4.4.三级立方体互连网络对多组部件同时通信能力分析三级立方体互连网络对多组部件同时通信能力分析给出一组部件：两对部件同时通信涉及的交换单元是否有矛盾要求，

34、决定能否实现同时通信。能实现同时通信时，各级要采用什么控制方式。5.5.四级立方体互连网络四级立方体互连网络网络构成网络构成广播式通信广播式通信给定一组控制信号下的给定一组控制信号下的连接关系表、连接关系图及连连接关系表、连接关系图及连接关系名称接关系名称6.6.三级混洗交换互连网络三级混洗交换互连网络网络构成网络构成三级立方体的逆网络三级立方体的逆网络给定一组控制信号下的给定一组控制信号下的连接关系表、连接关系图及连连接关系表、连接关系图及连接关系名称接关系名称7.全排列互连网络全排列互连网络（教材（教材P213P213图图6-236-23的问题）的问题）1）网络构成：由三级立方体与三级混洗

35、交换互连网络构成。2）对05，17同时通信能力分析。0505：A A交换交换 F F直通直通 K K交换交换 Q Q直通直通 S S直通直通 17：B直通 G直通 I直通 N交换 U交换 无对交换单元矛盾要求，但级控不行，单元控、部分级控可以。（可以有两条以上通路：B交换 H直通 K直通 Q交换 U直通 B交换 H交换 L直通 Q直通 U直通）3）对50，71同时通信能力分析。50：B交换 G直通 I交换 M直通 R直通 71：D交换 G直通 J直通 N交换 S直通 （D直通 H交换 K直通 Q直通 S交换）无对交换单元功能的矛盾要求，但级控不行（第一、二、五级可以），部分、单元控制可以。8.

36、8.三级三级PM2IPM2I互连网络互连网络1）网络构成：由PM22、PM21、PM20三级构成。2）控制信号与功能关系。Gi=00 直通（或平控）Gi=01 上控（按PM2+I，如第一级I=2）Gi=10 下控（按PM2-I）3）利用三级PM2I互连网络实现点到点通信所需各级控制信号和路径（可有多条路径）。如：实现05通信 方案一：上控（04）平控（44）上控（45）G2G1G0=010001 方案二：上控（04）上控（46）下控（65）G2G1G0=010110 又称数数据据变变换换网网络络，可以采用单单元元控控制制实现各种灵活的互联通信。五、寻径算法五、寻径算法1.1.网寻径网寻径012

37、3456701234567第0级第1级第2级当当目的地址目的地址编码从高位开始的第编码从高位开始的第i i位（从位（从0 0开始）为开始）为0 0时，第时，第i i级的级的2 2 2 2开关的输入端与上输出端连接，否则开关的输入端与上输出端连接，否则输入端与下输出端连接。输入端与下输出端连接。0000010100111001011101112.2.立方体网络中的立方体网络中的E E立方体寻径立方体寻径假设有一个假设有一个N=2N=2n n个结点的个结点的n n方体。每个结点的二方体。每个结点的二进制编码为：进制编码为：b=bb=bn-1 n-1 b bn-2 n-2 b b1 1 b b0 0

38、s=ss=sn-1 n-1 s sn-2 n-2 s s1 1 s s0 0d=dd=dn-1 n-1 d dn-2 n-2 d d1 1 d d0 0如何确定一条从如何确定一条从s s到到d d的步数最小的路径？的步数最小的路径？寻径按照从维寻径按照从维1 1到维到维4 4的顺序进行。的顺序进行。如果如果s s和和d d的第的第i i位相同，则沿维位相同，则沿维i i的方向不需的方向不需要寻径，否则从当前结点沿着这一维方向走向下一要寻径，否则从当前结点沿着这一维方向走向下一结点（立方体中，每维包括两个结点）。重复这一结点（立方体中，每维包括两个结点）。重复这一过程直到到达目的结点。过程直到到

39、达目的结点。寻径寻径：n=4，s=0110，d=1101（1）计算方向位计算方向位011r4110r3101r2011r1r=01100010000001000111000100110101111010101000110011111001101111014维立方体网络n=4,s=0110,d=1101,r=1011路径为：01100111010111010110001000000100011100010011010111101010100011001111100110111101思考题：有有1616个并行处理器，要实现先个并行处理器，要实现先4 4组组4 4元交换，再元交换，再2 2组组8 8

40、元交元交换，最后是换，最后是1 1组组1616元交换，写出最后实现的互联函数的关系式。元交换，写出最后实现的互联函数的关系式。解：输入端号输入端号|0123 4567 89AB CDEF|0123 4567 89AB CDEF|4 4组组4 4元交换后元交换后|3210 7654 BA98 FEDC|3210 7654 BA98 FEDC|再再2 2组组8 8元交换元交换|4567 0123 CDEF 89AB|4567 0123 CDEF 89AB|最后最后1 1组组1616元交换元交换|BA98 FEDC 3210 7654|BA98 FEDC 3210 7654|最终实现的是（最终实现的

41、是（0 B0 B）,（1 A1 A）,（2 92 9）,（3 83 8）,（4 F4 F）,（5 E5 E）,（6 D6 D）,（7 C7 C）互联函数的关系式互联函数的关系式:Cube(b3b2b1b0)=b3b2b1b07.全排列互连网络全排列互连网络8.三级三级PM2I互连网络互连网络五、寻径算法五、寻径算法1.1.网寻径网寻径2.2.立方体网络中的立方体网络中的E E立方体寻径立方体寻径思考题：有有1616个并行处理器，要实现先个并行处理器，要实现先4 4组组4 4元交换，再元交换，再2 2组组8 8元交元交换，最后是换，最后是1 1组组1616元交换，写出最后实现的互联函数的关系式。

42、元交换，写出最后实现的互联函数的关系式。解：输入端号输入端号|0123 4567 89AB CDEF|0123 4567 89AB CDEF|4 4组组4 4元交换后元交换后|3210 7654 BA98 FEDC|3210 7654 BA98 FEDC|再再2 2组组8 8元交换元交换|4567 0123 CDEF 89AB|4567 0123 CDEF 89AB|最后最后1 1组组1616元交换元交换|BA98 FEDC 3210 7654|BA98 FEDC 3210 7654|最终实现的是（最终实现的是（0 B0 B）,（1 A1 A）,（2 92 9）,（3 83 8）,（4 F4

43、F）,（5 E5 E）,（6 D6 D）,（7 C7 C）互联函数的关系式互联函数的关系式:Cube(b3b2b1b0)=b3b2b1b0l题画出16台处理器仿ILLIAC的连接模式进行互连的互连结构图，列出PE0分别只经一步、二步和三步传送能将信息传送到的各处理器号。l分析按照ILLIAC的连接模式，不难得出N为16个处理单元时，构成的是44的方阵，各PE之间的连接规律就是PM20(mod16)和PM22(mod16)。根据所画出的互连结构图，PE0只经一步、二步和三步传送将信息传送到的各处理器号就可以很容易地求得了。l解答16台处理机仿ILLIAC的连接模式互连的结构图（略）。lPE0经一

44、步可将信息传送到的处理器号有PE1、PE4、PE12、PE15。lPE0经二步可将信息传送到的处理器号除了一步可送到的PE1、PE4、PE12、PE15外，还有PE2、PE3、PE5、PE8、PE11、PE13、PE14。lPE0经三步可将信息传送到的处理器号除了PE1、PE2、PE3、PE4、PE5、PE8、PE11、PE12、PE13、PE14、PE15外，还有PE6、PE7、PE9、PE10。l可见，最多经3步就可以将PE0的信息传送到任何其它的处理器上，所以其最大的距离为3步。l46章习题答案第一章参考答案：第一章参考答案：1应用语言级 高级语言级 汇编语言级 操作系统级 机器语言级

45、微程序语言级。2 从上而下 从下到上 专用机 通用机3 软、硬件交界面 计算机系统的性能/价格比4 1 TFLOPS的 计 算 能 力 1 TByte的 主 存 容 量 1 TBytes 的IO带宽5 虚拟机 实际机器6 统一高级语言 模拟 仿真 系列机7 控制流 数据流 SISD SIMD MISD MIMD8 汇编语言程序员9 任务单一化 操作重叠化 吞吐匹配化 程序多道化10.D 11.C 12.D 13.A 14.B 15.A 16.B 17.L0（微程序）级 L5（应用语言）级18.非用户片（通用片）现场片 用户片（全用户片）19.答：1)在现有器件的条件下，系统要有较高的性能价格比

46、；2)不要不合理地限制各种组成、实现技术的采用；3)硬件的设计要考虑如何为软件提供更好的支持。20.答：软件和硬件在逻辑功能上是等效的，但是，在性能、价格、实现的难易程度上却是各不相同的，硬件执行速度快，软件灵活性好。即软件和硬件在物理意义上是不等效的。第二章参考答案：第二章参考答案：1标志符 描述符2基地址 向量长度 位移量 起始地址 有效向量长度3数的个数 数的范围 精度 稀密度4A 5.B 6.D7指尾数右移过程中丢掉的溢出位8查表舍入法、舍入法 恒置1法 截断法 9指令使用频度不同时 采用不等长编码10D 11.D12寄存器 堆栈 主存13程序员编程用的地址 物理14逻辑 物理 动态再

47、定位152FFF16A 17.D 18.D 19.A 20.C1.解：1）两级描述符：或：2）三级描述符2.2.解：解：1 1）规格化浮点数表：）规格化浮点数表：r rm m=2=2时，时，P=3 P=3，m=3 m=3 正尾数、规格化、非负阶时正尾数、规格化、非负阶时共有共有3232个规格化浮点数个规格化浮点数m p0000010100111001011101111004/84/44/2481632641015/85/45/25102040801106/86/46/26122448961117/87/47/27142856112rm=8时，共有时，共有56个规格化浮点数个规格化浮点数mp00

48、00010100111001011101110011/8181*821*831*841*851*860102/82162*822*832*842*852*860113/83243*823*833*843*853*861004/84324*824*834*844*854*861015/85405*825*835*845*855*861106/86486*826*836*846*856*861117/87567*827*837*847*857*862 2）规格化浮点数表：）规格化浮点数表：r rm m=2=2时，规格化浮点数共有时，规格化浮点数共有4*8=324*8=32个个r rm m=8=8时

49、时，规规格格化化浮浮点点数数共共有有7*8=567*8=56个个，在在0.50.5，112112中中，有数有数1919个（上表中红的数字表示）。个（上表中红的数字表示）。rm规格化浮点数个数规格化浮点数个数数的表示范围数的表示范围e2320.511218560.12518350080.63题:（A+B）*（C-D）+（E/F）-（G+H)*I解：1）数学表达式的树结构2）逆波兰表达式AB+CD-*EF/+GH+I*-4题解：1）画HuffmanA方案的树结构2 2）分别写出等长法、）分别写出等长法、H-AH-A、扩展法编码、扩展法编码 方案：方案：IiPi等长法等长法H-A扩展法扩展法OPli

50、OPliOPliI1I2I3I4I5I6I7I8I9I10I11I12I13I140.150.150.140.130.120.110.040.040.030.030.020.020.010.0100000001001000110100010101100111100010011010101111001101401011011101111011111011111101111111011111111011111111101111111111011111111111011111111111101111111111111123456789101112131300000101001110010111000