《计算机体系结构》第六章.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直通

24、 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.三级PM2I互连网络1）网络构成：由PM22、PM21、PM20三级构成。,2）控制信号与功能关系。Gi=00 直通（或平控）Gi=01 上控（按PM2+I，如第一级I=

25、2）Gi=10 下控（按PM2-I）3）利用三级PM2I互连网络实现点到点通信所需各级控制信号和路径（可有多条路径）。如：实现05通信 方案一：上控（04）平控（44）上控（45）G2G1G0=010001 方案二：上控（04）上控（46）下控（65）G2G1G0=010110 又称数据变换网络，可以采用单元控制实现各种灵活的互联通信。,五、寻径算法1.网寻径,当目的地址编码从高位开始的第i位（从0开始）为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接。,0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1,2.立方体网络中的E

26、立方体寻径假设有一个N=2n个结点的n方体。每个结点的二进制编码为：b=bn-1 bn-2 b1 b0s=sn-1 sn-2 s1 s0d=dn-1 dn-2 d1 d0如何确定一条从s到d的步数最小的路径？寻径按照从维1到维4的顺序进行。如果s和d的第i位相同，则沿维i的方向不需要寻径，否则从当前结点沿着这一维方向走向下一结点（立方体中，每维包括两个结点）。重复这一过程直到到达目的结点。,寻径：n=4，s=0110，d=1101（1）计算方向位,r=,0110,0010,0000,0100,0111,0001,0011,0101,1110,1010,1000,1100,1111,1001,1

27、011,1101,4维立方体网络,n=4,s=0110,d=1101,r=1011,路径为：0110 011101011101,0110,0010,0000,0100,0111,0001,0011,0101,1110,1010,1000,1100,1111,1001,1011,1101,思考题：有16个并行处理器，要实现先4组4元交换，再2组8元交换，最后是1组16元交换，写出最后实现的互联函数的关系式。,解：输入端号|0123 4567 89AB CDEF|,4组4元交换后|3210 7654 BA98 FEDC|,再2组8元交换|4567 0123 CDEF 89AB|,最后1组16元交换

28、|BA98 FEDC 3210 7654|,最终实现的是（0 B）,（1 A）,（2 9）,（3 8）,（4 F）,（5 E）,（6 D）,（7 C）,7.全排列互连网络8.三级PM2I互连网络五、寻径算法1.网寻径2.立方体网络中的E立方体寻径,思考题：有16个并行处理器，要实现先4组4元交换，再2组8元交换，最后是1组16元交换，写出最后实现的互联函数的关系式。,解：输入端号|0123 4567 89AB CDEF|,4组4元交换后|3210 7654 BA98 FEDC|,再2组8元交换|4567 0123 CDEF 89AB|,最后1组16元交换|BA98 FEDC 3210 7654

29、|,最终实现的是（0 B）,（1 A）,（2 9）,（3 8）,（4 F）,（5 E）,（6 D）,（7 C）,题 画出16台处理器仿ILLIAC 的连接模式进行互连的互连结构图，列出PE0 分别只经一步、二步和三步传送能将信息传送到的各处理器号。分析 按照ILLIAC的连接模式，不难得出N为16个处理单元时，构成的是44的方阵，各PE之间的连接规律就是PM20(mod 16)和PM22(mod 16)。根据所画出的互连结 构图，PE0只经一步、二步和三步传送将信息传送到的各处理器号就可以很容易地求得了。,解答 16台处理机仿ILLIAC的连接模式互连的结构图（略）。PE0经一步可将信息传送到

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

31、 专用机 通用机3 软、硬件交界面 计算机系统的性能/价格比41 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)在现有器件的条件下，系统要有较高的性能价格比；2)不要不合理地限制各种组成、实现技术的采用；3)

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

33、.解：1）两级描述符：,或：,2）三级描述符,2.解：1）规格化浮点数表：rm=2时，P=3，m=3 正尾数、规格化、非负阶时共有32个规格化浮点数,rm=8时，共有56个规格化浮点数,2）规格化浮点数表：rm=2时，规格化浮点数共有4*8=32个rm=8时，规格化浮点数共有7*8=56个，在0.5，112中，有数19个（上表中红的数字表示）。,3题:（A+B）*（C-D）+（E/F）-（G+H)*I 解：1）数学表达式的树结构,2）逆波兰表达式AB+CD-*EF/+GH+I*-,4题 解：1）画HuffmanA方案的树结构,2）分别写出等长法、H-A、扩展法编码 方案：,L,3）扩展码时L最

34、小，即L扩展=3.444.54 选用扩展法,0.150.150.140.130.120.110.040.040.030.030.020.020.010.01,1101111011000110010000000101001010100100001011101011000101111,L=.8*3+.08*4+.08*5+.02*6+.02*7=2.4+.72+.26=3.38,5.解：1）4 4 4 4 三地址指令12条 两地址指令62条 单地址指令31条 零地址指令32条(24-12）24-62)24-31)24=1632 不能满足32条零地址指令的要求，为保证32条零地址指令可减少一条单地址

35、指令。即(24-12）24-62)24-30)24=322）12条三地址指令 0 0 0 0 A1 A2 A3 1 0 1 1,62条两地址指令 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 A1 A2 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1,30条单地址指令 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 A1 1 1 1 1 1 1 1 1 1 1 0 1 32条零地址指令 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1,

36、第三章参考答案：1.采用何种方法以获取总线的使用权 分布式 集中式 2.串行链接 独立请求 定时查询 串行链接与独立请求相结合 独立请求 串行链接 3.专用 非专用 4.B 5.D 6.A 7.A 8.D 9.B 10.C 11.D 12.C 13.A 14.同一时钟周期 15.中断级屏蔽 16.响应 处理程序 17.同级及更低级的其它 18.片总线 内总线 系统总线 外总线 19.物理特性 功能特性 电气特性 时间特性 20.低 单节字高 定长块 优先级高的中高 可变长块,1.解：（1）结构示意图（2）L=log264=6所需独立线数：6+2=8（3）有部件请求时，请求信号送C；C收到请求后

37、，将当前计数器的计数值，通过6条代码线同时送到各部件；若与此计数值编号相同的部件已提出请求，则该部件建立忙电平，C收到忙电平后，停止向下计数，表示该部件接管总线。若与此计数值相同编号的部件未提出请求，等待一个计数脉冲周期后，计数器将进行+1计数，此时C又将下一个计数值又同时发往各部件，余类推。,2.解（1）处理顺序为 1-3-5-4-2（2）中断响应处理时空图,主程序 中断处理程序,响,一 二 三 四 五,t,嵌套,中断请求,嵌套,返回主程序,3.解：1）(1)fb=100+40+40+10+10=200(KB/s)(2)106/(200103)=5s(3)Tbj=1/fj 第j个子CH提供一

38、个字节的时间 计算完整申请周期：上述5个时间的最小公倍数是100s。,子CH 5 4 3 2 1 0 10 20 30 40 50 60 70 80 90 100 t(s),2）计算CH系统流量 f=200+680+620=1500KB/s 3)存储器流量:15004=6000 KB/s 4）tm=106/（6000103）0.167s,第四章参考答案：1.全相联 直接相联 组相联 段相联 2.体内连续编址 体间连续编址 同步启动 异步启动 3.虚拟存储器 命中率H 存储空间利用率 Cache-主存体系 命中率H和等效访问时间tA 4.LRU 堆栈法 比较对法 5.虚拟存储器 Cache-主存

39、体系 6.D 7.C 8.B 9.D 10.B 11.A 12.A 13.D 14.B 15.A 16.D 17.虚、实地址 虚地址找到实地址 18.页面争用 19.大容量 高速度 20.命中 实现 软硬件,1 解：失效的虚页号：2、3、5、7。命中的虚页号：0、1、4、6。查地址 Nv Nr nr 实地址 装入位 命中否0 0 0 3 3072 1 命中3728 3 656 3 3728 0 失效1023 0 1023 3 4095 1 命中1024 1 0 1 1024 1 命中2055 2 7 2 2055 0 失效7800 7 632 0 632 0 失效4096 4 0 2 2048

40、 1 命中6800 6 656 0 656 1 命中,虚页,01234567,2 解：1）页面数为:2N=220 页面容量:2P=512=29 则页表层次数:N/P=20/9=3(层)2）经3次(层)页表访问及1次操作数访问，需要4次访问主存；3）查表时间=（3+1）*0.25=1(s)；4）tm=0.25/(3+1)=0.0625(s),3 解：1）,2）tA=H*tc+（1-H）*tm=5/12*0.02+（1-5/12）*.2=0.125（s）,4 解：（1），（2）,5 解：,命中率H,t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,6 解：1）,主存,Ca

41、che,2）,01234567,主存页号,1位 1位 1位,1位 1位,3)可放入Cache 0组的主存块号:0 1 4 5 可放入Cache 1组的主存块号:2 3 6 7,t 块流,失 失 失 中 失 失 失 中 失 争 争 失 中 失 争,4)块失效:凡是不命中都属于失效;块争用:换出了不该换出的页面.所以:即失效又争用的时刻是:t10,t11及t155)tA=H*tc+(1-H)*tm=0.2*2+0.8*15=12.4(ns)块争用:失效且发生页面替换,第五章 参考答案：1 推迟法 相关专用通路法 2 等待执行 等待译码 3 横向 纵向 纵横向 4 数相关 指令相关 5 猜测法 分支

42、预测 短转移(短循环)增加指令站容量 6C 7.B 8.C 9.D 10.D 11.B 12.D 13.C 14.A 15.C16.C 17.C 18.D 19.A 20.D,1.解：1）顺序执行：t=k*（t取+t译+t执）=300(4+5+6)=4500（t）2）两条重叠：t=t取+k*t译+(k-1)*(t取,t执)max+t执=4+3005+(300-1)6+6=3304（t）3）三条重叠：t=t取+(t译,t取)max+(k-2)*(t取,t译,t执)max+(t执,t译)max+t执=4+5+(300-2)6+6+6=1809（t）,2 解：M=a0*a1*a2*a3*a4*a5*

43、a6*a71）合理分解算式M=a*a1 M1=a2*a3 M2=a4*a5 M3=a6*a7 M4=M0*M1 M5=M2*M3 M=M4*M52）时空图,3）吞吐率：TP=7/21=1/3（个/t）效率：=（7*6 t）/（21t*6）=1/3,3.解 长度为4向量A和B的点积为 ABa1*b1+a2*b2+a3*b3+a4*b4 共需做4乘法和3加法：c1=a1*b1,c2=a2*b2,c3=a3*b3,c4=a4*b4d1=c1+c2,d2=c3+c4,d3=d1+d2=AB(1)乘法部件和加法部件不能同时工作，部件内也只能顺序方式工作如下图所示。由向量点积AB运算的时空图可知，完成全部

44、运算最少为4 5十3 535(拍)部件 0 5 10 15 20 25 30 35 拍,c4,加乘,(2)乘法部件和加法部件可并行的时空图 其中，e1=d1+c3,e2=e1+c4=AB,部件,加乘,0 5 10 15 20 25 拍,(3)处理器有一个乘、加双功能半动态流水线时的时空图,加,乘,部件,0 5 8 10 15 19拍,54321,54321,(4)处理器有乘、加两条流水线，可同时工作时的时空图,加,乘,部件,0 5 8 10 15 18拍,54321,54321,4.解1）串：1+6+1+(N-1)+1+6+1+(N-1)+1+7+1+(N-1)=22+3N()2）并+串:1+

45、6+1+(N-1)+1+7+1+(N-1)=15+2N()3）链接：1+6+1+1+7+1+（N-1)=16+N()4）时空图：,5有一个由4段组成的单功能非线性流水线，其非线性流水线的预约表如下：（1）写出延迟禁止表、初始冲突向量，画出冲突向量的状态转移图。（2）写出该非线性流水线的最佳调度方案及其最大吞吐率。,5.解：（1）延迟禁止表为：F=1，5 初始冲突向量为：C=（10001）状态转移图：,（2）显然，最佳调度方案为每隔2个节拍流入一个任务，此时最大吞吐率为：TP=1/2（任务/t）,第六章 参考答案：1.交换单元的功能、拓扑结构、控制方式2.立方体 PM2I 混洗交换互连网络 3.

46、级控制、单元控制、部分级控制4.时间重叠 资源重复 资源共享5.多处理机系统 多计算机系统6.直通、交换、下播、上播7.松耦合 紧耦合 8.B 9.C 10.B 11.D 12.D 13.C 14.B 15.C 16.D 17.A 18.B 19.B 20.A,1.解（1）,（2）,（3）1）0#14#：A直通 B交换 C交换 D交换 7#10#：E交换 F直通 C交换 G交换对每个交换单元的功能无矛盾要求，但第一、二级不可以用级控，可采用单元控制或部分级控。2）10#1#：H交换 I交换 J直通 K交换 15#9#：L直通 M交换 J交换 K直通 对J、K交换单元的功能有矛盾要求，因此不能直接通信。2.解（1）三级立方体互联网络图、三级PM2I互联网络图及三级混洗互联网络图分别绘图如下：（2）2#5#通信分析 立方体：B交换 F交换 J交换 PM2I：上控（2 6）平控（6 6）下控（6 5）混洗：C交换 F交换 K交换,3.解（1）三级混洗互联网络图绘图如下：（2）4#号部件广播式通信第一级：A下播（11）第二级：E、F上播（10）第三级：I、J、K、L上播（10）（3）G2G1G0=11 10 10,4.解1）,2）3）G2G1G0=10 11 11,