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

五、加速比的概念加速比的常规定义加速比概念的延伸六、非线性流水线的调度非线性流水线的预约表延迟禁止表如何建立初始冲突向量如何确定状态转移图如何绘制、调度方案、平均延迟指令级高级并行超级处理机超标量处理机、超长指令字处理机和超流水线处理机,第六章多机系统1概述,一、并行性概念并行性是指在执行任务过程中可同时进行的运算或操作。1.开发并行性的目的提高计算机的运行效率,2.并行性的含义具有双重含义：同时性与并发性同时性是指两个或两个以上的事件在同一时刻发生。并发性是指两个或两个以上的事件在同一时间间隔内发生。,3.并行性的意义1）并行意味着有多个事件在并行执行，当这些事件都在完成同一性质的处理时，意味着单位时间完成的结果数增加了，从而可提高对数据处理速度。2）并行同样意味着多个事件中并行处理，当这些处理都在为一个目的工作时，从提高可靠性出发，按多数表决法，对多数得出的相同结果具有高的可靠性。3）并行也可能意味着要增加硬件成本，因而需根据性能价格比来评价这种开销是否合理。,二、从单机向多机发展的三条途径,并行处理的四个等级：单机流水处理中一条指令内多个操作的并行处理;并行处理机多条相同指令的并行处理（指令间）;多处理机多个任务的并行处理;多计算机系统多程序（作业）的并行处理。三、多机系统的耦合度1.何谓耦合度多机之间相互的通信控制能力或相互依赖程度，称为多机之间的耦合度。,2.三种耦合度1）最低耦合：多机之间几乎没有共享设备，如仅用二、三条线连接起来的计算机。（如RS232C通信）。2）松散耦合：多机之间有一定的共享设备，如大型的主机与外围机，它们之间共享受主存，I/O通道。但它们之间也可相对独立工作，又如连接在网络上的计算机，连接在局域网上的计算机共享硬盘。处理机间一般通过消息传递系统交换信息，也有通过通道互联实现处理机间的通讯。3）紧密耦合：耦合度最高，相互依赖很强，如阵列式多处理机的CU（控制部件）和PU（处理部件）之间。通过共享主存实现处理机间的通讯，通讯速率受限于主存频宽。,四、多机系统的分类及特点多机系统指的是多处理机系统和多计算机系统。1.多处理机系统1）各处理机共享I/O通道、有共享主存。2）属于紧耦合。3）表现形式有：并行(阵列)式多处理机系统；分布式多处理机系统。2.多计算机系统1）各处理机具有自己的I/O通道和主存2）属于最低耦合或松耦合3）典型表现为计算机网络。,互连网络:是一种有开关元件按一定的拓扑结构和控制方式构成的网络,用来实现计算机系统中结点之间的相互连接。,五、互连网络,网络拓扑分为静态和动态两种。这里的拓扑是指互联网络中的各个结点间连接关系，通常用图来描述。1.静态拓扑静态拓扑由点点直接相连而成，这种连结方式在程序执行过程中不会改变。如果用图来表示，结点代表开关，边代表通信链路，结点间的链路无源，不能重构,没有直接相连结点间的通信需通过中间结点中转。,2.动态拓扑设置有源开关，可根据需要对连接通路加以重新组合，如单级循环网络和各种多极互连网络等。,六、典型网络的结构1.线性阵列,对N个结点的线性阵列，有N-1条链路，度为2，不对称。N很大时，通信效率很低。,2.环,对N个结点的环，考虑相邻结点数据传送方向：双向环单向环,3.带弦环,对上图中12个结点的带弦双向环，结点度为3结点度为4,4.全链接全链接是带弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。如下图中N=8个结点的链接：,5.树形,4层的二叉树,树形的扩展：,带环树,这两种结构都可以缓解根结点的瓶颈问题。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为阵列处理部件。,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个局部存储器（PEM0PEM63）共有2K64=128K）2）由于局部存储器随阵列分布，因此又称为阵列分布存储器。,二、阵列式多处理机适应的算法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+b0c1=a1+b1c63=a63+b63,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）互连函数：实现处理机之间相互连接的某种拓扑结构的逻辑函数，称互连函数。(表示互连网络的连接规律)4）对互连网络的评价要有利于实现；要有一定的通信频带；要有一定的灵活性，可实现多种连接通信。,5）互连网络的主要类型从性质上分）立方体（cube）互连网络）PM2I互连网络）混洗交换互连网络从级数多少来分）单级互连网络）循环互连网络（物理一级但可实现多级）多级互连网络,6）互连函数中，部件（或处理机）的编码。设用n位二进制来表示部件编码，即有：Pn-1Pn-2P2P1P0当用3位二进制数表示时（即n=3）则有：P2P1P0,2.单级立方体（Cube）互连网络1）立方体互连函数（设n=3）Cube0:仅在第0位上的代码取反，其余各位不变。Cube0（P2P1P0）=P2P1P0Cube1:仅在第1位上的代码取反，其余各位不变。Cube1（P2P1P0）=P2P1P0Cube2:仅在第2位上的代码取反，其余各位不变。Cube2（P2P1P0）=P2P1P0,2）实现的连接关系Cube0Cube1Cube2P2P1P0P2P1P0P2P1P0P2P1P0000001010100001000011101010011000110011010001111100101110000101100111001110111100010111110101011,Cube0可实现8个部件（处理单元），在x方向连接。Cube1可实现8个部件（处理单元），在y方向连接。Cube2可实现8个部件（处理单元），在z方向连接。,3）当n=4时，有P3P2P1P0，则Cube3（P3P2P1P0）=P3P2P1P0用Cube3可将两个立方体连接起来，构成一个立方体组（四维空间）。当n=5时，有P4P3P2P1P0，则Cube4（P4P3P2P1P0）=P4P3P2P1P0用Cube4可将两个立方体组连接起来，构成一个立方体群（五维空间）。4）互连网络的链接关系图,3.单级PM2I互连网络（Plus-Minus2i）1）PM2I互连函数PM2+i(j)=j+2iPM2-i(j)=j-2i,2）实现的连接关系（设j分别为07,以8为模。）,jj+20j-20017120231342453564675706,伊机在水平连接采用PM2+0、PM2-0（双向）且以64为模。,3）PM21PM2+1(j)=j+21=j+2PM2-1(j)=j-21=j-2,4）当I=3时，有PM2+3(j)=j+8PM2-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)=P1P0P2000000001010010100011110100001101011110101111111,3）利用混洗互连网函数将8个部件分为互不相联的四组，如下图：0；1，2，4；3，5，6；7,4）在混洗基础上加入Cube0的交换，即构成混洗交换互连函数。01234567可将8个部件实现相互通信。Cube0(Shuffle(bn-1b0)=Cube0(bn-2b0bn-1)=bn-2b0bn-1,5.循环互连网络1）构成：由单级互连网络、多路开关(MUX)、输入寄存器（IR）和输出寄存器（OR）组成。2）目的：利用对单级互连网的重复使用，在一定程度上模拟互连网络的功能。3）特点：,结构简单，易于实现。对单级互连网络的重复使用，往往是机械重复，灵活性差。重复加入时，重复频率受到限制。,6.描述多级互连网络的三要素1）交换单元的功能交换单元：是一个具有两个输入，两个输出和一个控制端的五端开关。,双功能交换单元：具有直通和交换两种功能。,四功能交换单元（G为两位）：除上述的直通、交换外，还有上播、下播两种。,2）拓扑结构拓扑结构是各级间出端与入端互连的模式。前述各种单级互连网络的连接模式均可用来组合构成不同的多级互连网络。解决在级与级之间采用何种规则连接，通常采用级间对号连接，如三级立方体互联网络：,3）控制方式级控制方式：同一级的所有交换单元只用一个控制信号控制。单元控制方式：同一级的每个交换单元各有各的独立控制信号。部分级控制方式：介于两种控制方式之间，对同一级交换单元来讲，控制信号的数目2个，但小于交换单元数。,1一、并行性概念二、从单机向多机发展的三条途径三、多机系统的耦合度四、多机系统的分类及特点五、互连网络六、典型静态网络的结构2一、伊（ILLIAC）IV阵列式二、阵列式多处理机适应的算法三、SIMD互连网络互连网络的主要类型循环互连网络描述多级互连网络的三要素,立方体（Cube）互连网络的拓扑结构,Cube0可实现x方向连接Cube1可实现y方向连接Cube2可实现z方向连接,四、典型互连网络的性能分析1.采用双功能交换单元级控制方式的三级立方体互连网络（由Cube0、Cube1、Cube2三级构成）。1）要求画出3*4=12个交换单元的三级立方体互连网络图。,2）写出控制信号G2G1G0实现的连接关系表。3）画出控制信号G2G1G0实现的连接关系图。4）写出控制信号G2G1G0实现的连接名称。,2.采用级控和部分级控相结合的三级立方体互连网络移数网络1）网络构成：也由Cube0、Cube1、Cube2三级构成。2）控制方式第一级采用级控制方式（G0）。第二级采用部分级控制方式（G1G2）。第三级采用部分级控制方式(G3G4G5)。,3）控制信号（G5G0）与连接关系表、连接关系图和移数名称。,思考：经3级立方体网络对07八个端子（01234567）进行排列，当进行移2模4变换后得到的这八个端子新的排列应当是,（23016745）,3.采用四功能交换单元，级控制方式的三级立方体实现广播式通信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）第二组部件：50，7150号部件通信：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,3）控制信号G3G2G1G0与连接关系表、连接关系图及连接关系名称。,6.三级混洗交换互连网络1）网络构成：也由Cube2、Cube1、Cube0三级构成，但与三级立方体互连网络有以下两点区别：Cube0与Cube2的位置互换（第一级是Cube2，第三级是Cube0）Cube1中间两个交换单元位置互换。其目的是使级间连接形式与混洗连接一致。（混洗循环左移一位）,2）对以下两组部件同时通信能力分析。05，1705：A交换F直通K交换17：B交换H交换L直通对交换单元无矛盾要求，但第二、三级需采用部分级控制或单元控制。50，7150：B交换G直通I交换71：D交换G交换I直通对G、I交换单元有矛盾要求，因此不能同时通信。（与三级立方体正好相反逆网络）3）三级混洗交换互连网络的控制信号G2G1G0与连接关系表、关系图、连接名称与三级立方体相似。（略）,四、典型互连网络的性能分析1.采用双功能交换单元级控制方式的三级立方体互连网络。要求画出互连网络图;写出控制信号G2G1G0实现的连接关系表、连接关系图、连接名称。,110,010,000,100,111,001,011,101,Cube1,Cube0,Cube2,2.采用级控和部分级控相结合的移数网络在给定控制信号（G5G0）下的连接关系表、连接关系图和移数名称。,3.采用四功能交换单元的三级立方体实现广播式通信,4.三级立方体互连网络对多组部件同时通信能力分析,给出一组部件：两对部件同时通信涉及的交换单元是否有矛盾要求，决定能否实现同时通信。能实现同时通信时，各级要采用什么控制方式。,5.四级立方体互连网络网络构成广播式通信给定一组控制信号下的连接关系表、连接关系图及连接关系名称6.三级混洗交换互连网络网络构成三级立方体的逆网络给定一组控制信号下的连接关系表、连接关系图及连接关系名称,7.全排列互连网络（教材P213图6-23的问题）1）网络构成：由三级立方体与三级混洗交换互连网络构成。,2）对05，17同时通信能力分析。05：A交换F直通K交换Q直通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.三级PM2I互连网络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.网寻径,当目的地址编码从高位开始的第i位（从0开始）为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接。,000001010011100101110111,2.立方体网络中的E立方体寻径假设有一个N=2n个结点的n方体。每个结点的二进制编码为：b=bn-1bn-2b1b0s=sn-1sn-2s1s0d=dn-1dn-2d1d0如何确定一条从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,1011,1101,4维立方体网络,n=4,s=0110,d=1101,r=1011,路径为：0110011101011101,0110,0010,0000,0100,0111,0001,0011,0101,1110,1010,1000,1100,1111,1001,1011,1101,思考题：有16个并行处理器，要实现先4组4元交换，再2组8元交换，最后是1组16元交换，写出最后实现的互联函数的关系式。,解：输入端号|0123456789ABCDEF|,4组4元交换后|32107654BA98FEDC|,再2组8元交换|45670123CDEF89AB|,最后1组16元交换|BA98FEDC32107654|,最终实现的是（0B）,（1A）,（29）,（38）,（4F）,（5E）,（6D）,（7C）,7.全排列互连网络8.三级PM2I互连网络五、寻径算法1.网寻径2.立方体网络中的E立方体寻径,思考题：有16个并行处理器，要实现先4组4元交换，再2组8元交换，最后是1组16元交换，写出最后实现的互联函数的关系式。,解：输入端号|0123456789ABCDEF|,4组4元交换后|32107654BA98FEDC|,再2组8元交换|45670123CDEF89AB|,最后1组16元交换|BA98FEDC32107654|,最终实现的是（0B）,（1A）,（29）,（38）,（4F）,（5E）,（6D）,（7C）,题画出16台处理器仿ILLIAC的连接模式进行互连的互连结构图，列出PE0分别只经一步、二步和三步传送能将信息传送到的各处理器号。分析按照ILLIAC的连接模式，不难得出N为16个处理单元时，构成的是44的方阵，各PE之间的连接规律就是PM20(mod16)和PM22(mod16)。根据所画出的互连结构图，PE0只经一步、二步和三步传送将信息传送到的各处理器号就可以很容易地求得了。,解答16台处理机仿ILLIAC的连接模式互连的结构图（略）。PE0经一步可将信息传送到的处理器号有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从上而下从下到上专用机通用机3软、硬件交界面计算机系统的性能/价格比41TFLOPS的计算能力1TByte的主存容量1TBytes的IO带宽5虚拟机实际机器6统一高级语言模拟仿真系列机7控制流数据流SISDSIMDMISDMIMD8汇编语言程序员9任务单一化操作重叠化吞吐匹配化程序多道化,10.D11.C12.D13.A14.B15.A16.B17.L0（微程序）级L5（应用语言）级18.非用户片（通用片）现场片用户片（全用户片）19.答：1)在现有器件的条件下，系统要有较高的性能价格比；2)不要不合理地限制各种组成、实现技术的采用；3)硬件的设计要考虑如何为软件提供更好的支持。20.答：软件和硬件在逻辑功能上是等效的，但是，在性能、价格、实现的难易程度上却是各不相同的，硬件执行速度快，软件灵活性好。即软件和硬件在物理意义上是不等效的。,第二章参考答案：1标志符描述符2基地址向量长度位移量起始地址有效向量长度3数的个数数的范围精度稀密度4A5.B6.D7指尾数右移过程中丢掉的溢出位8查表舍入法、舍入法恒置1法截断法9指令使用频度不同时采用不等长编码10D11.D12寄存器堆栈主存13程序员编程用的地址物理14逻辑物理动态再定位152FFF16A17.D18.D19.A20.C,1.解：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最小，即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）4444三地址指令12条两地址指令62条单地址指令31条零地址指令32条(24-12）24-62)24-31)24=1632不能满足32条零地址指令的要求，为保证32条零地址指令可减少一条单地址指令。即(24-12）24-62)24-30)24=322）12条三地址指令0000A1A2A31011,62条两地址指令00001100111100001110A1A21111000011111101,30条单地址指令00001111111011110000A111111111110132条零地址指令11111111111000001111111111111111,第三章参考答案：1.采用何种方法以获取总线的使用权分布式集中式2.串行链接独立请求定时查询串行链接与独立请求相结合独立请求串行链接3.专用非专用4.B5.D6.A7.A8.D9.B10.C11.D12.C13.A14.同一时钟周期15.中断级屏蔽16.响应处理程序17.同级及更低级的其它18.片总线内总线系统总线外总线19.物理特性功能特性电气特性时间特性20.低单节字高定长块优先级高的中高可变长块,1.解：（1）结构示意图（2）L=log264=6所需独立线数：6+2=8（3）有部件请求时，请求信号送C；C收到请求后，将当前计数器的计数值，通过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提供一个字节的时间计算完整申请周期：上述5个时间的最小公倍数是100s。,子CH543210102030405060708090100t(s),2）计算CH系统流量f=200+680+620=1500KB/s3)存储器流量:15004=6000KB/s4）tm=106/（6000103）0.167s,第四章参考答案：1.全相联直接相联组相联段相联2.体内连续编址体间连续编址同步启动异步启动3.虚拟存储器命中率H存储空间利用率Cache-主存体系命中率H和等效访问时间tA4.LRU堆栈法比较对法5.虚拟存储器Cache-主存体系6.D7.C8.B9.D10.B11.A12.A13.D14.B15.A16.D17.虚、实地址虚地址找到实地址18.页面争用19.大容量高速度20.命中实现软硬件,1解：失效的虚页号：2、3、5、7。命中的虚页号：0、1、4、6。查地址NvNrnr实地址装入位命中否000330721命中37283656337280失效102301023340951命中102410110241命中205527220550失效7800763206320失效409640220481命中6800665606561命中,虚页,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,t123456789101112131415,6解：1）,主存,Cache,2）,01234567,主存页号,1位1位1位,1位1位,3)可放入Cache0组的主存块号:0145可放入Cache1组的主存块号:2367,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猜测法分支预测短转移(短循环)增加指令站容量6C7.B8.C9.D10.D11.B12.D13.C14.A15.C16.C17.C18.D19.A20.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*a6*a71）合理分解算式M=a*a1M1=a2*a3M2=a4*a5M3=