体系结构课后习题答案

1、3.某模型机有10条指令li-lio,它们的使用频度分别为，。计算采用等长操作码表示时的信息冗余量。要求操作码的平均长度最短，试设计操作码的编码，并计算所设计操作码的平均长度。只有二种码长，试设计平均码长最短的扩展操作码编码并计算平均码长。只有二种码长，试设计平均码长最短的等长扩展码编码并计算平均码长。3.(1)采用等长操作码表示时的信息冗余量为(2) 操作码的Huffman编码法如表所示，此种编码的平均码长为位。表 操作码的Huffman编码法、2-5扩展码和2-4等长扩展码编码法指令指令使用 频度PiHuffman 编码操作码长度l i2-5扩展码操作码长度li2-4等长扩展码操作码长度l

2、 iI 10 020 020 02I 21 020 120 12I 30 1 031 021 0 0 04I 40 1 131 1 0 0 051 0 0 14I 51 1 031 1 0 0 151 0 1 04I 61 1 1 0 051 1 0 1 051 0 1 14I 71 1 1 0 151 1 0 1 151 1 0 04I 81 1 1 1 051 1 1 0 051 1 0 14I 91 1 1 1 1 061 1 1 0 151 1 1 04I 101 1 1 1 1 161 1 1 1 051 1 1 14(3) 操作码的2-5扩展码编码法如表所示，此种编码的平均码长为位

3、。(4) 操作码的2-4等长扩展码编码法如表所示，此种编码的平均码长为位。.若某机设计有如下格式的指令：三地址指令12种，一地址指令254种，设指令字的长度为 16位，每个地址码字段的位数均为4位。若操作码的编码采用扩展操作码，问二地址指令最多可以设计多少种.二地址指令最多可以设计 48种。.一台模型机共有9条指令I1l9,各指令的使用频度分别为 30% 20%, 20% 10% 8%, 6%, 3% 2%, 1% 该模型机有8位和16位两种指令字长。8位字长指令为寄存器-寄存器(R-R)二地址类型，16位字长指令 为寄存器-存储器(R-MD二地址变址寻址类型。试设计有二种码长的扩展操作码，使

4、其平均码长最短，并计算此种编码的平均码长。在(1)的基础上，该机允许使用多少个可编址的通用寄存器若采用通用寄存器作为变址寄存器，试设计该机的两种指令格式，并标出各字段的位数。计算变址寻址的偏移地址范围。6.(1)操作码的2-5扩展码编码法如表所示，此种编码的平均码长为位。表操作码的Huffman编码法和2-4等长扩展码编码法指令指令使用频度Pi2-5扩展码操作码长度liI 10 02I 20 12I 31 02I 41 1 0 0 05I 51 1 0 0 15I 61 1 0 1 05I 71 1 0 1 15I 81 1 1 0 05I 91 1 1 0 15(2) 在(1)的基础上，该机

5、允许使用 8个可编址的通用寄存器。(3)该机的两种指令格式及各字段的位数如下：(4)变址寻址的偏移地址范围为 -16+15。3,假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为，则采用 Cache后， 能使整个存储系统获得的加速比是多少3, 3,57.某机是由Cache和主存组成的二级存储系统，Cache的存取时间t c=20ns,主存的存取时间tm=80ns, Cache分为指令Cache和数据Cache,指令Cache的命中率为，数据Cache的命中率为。假设在所有的访存 操作中有20%是访问指令体，求系统等效的存取时间。4. 22.16ns.如图所示的三级存储系

6、统，若M、M2、M的访问时间分别为 20ns、80ns和2000ns。M、M的命中率分别为和，则存储器系统的等效访问时间为多少图三级存储系统5.6,完成一个两级存储系统的容量规划。第一层M是高速缓存，其容量可为 64KB 128KB和256KR第二层M是容量为4MB的主存。设 c和cz分别是M和M2的每字节成本，而 3和tz分别是CP期问M和M时的存 取时间。假设c1=20c2, t2=10t1,而高速缓存在上述 3种容量时的命中率分别为、和。假设t1=20ns,当高速缓存的容量分别为上述 3种假设时的平均存取时间ta是多少当c2=$KB时，分别求整个存储器系统的平均成本。比较这3种存储层次结

7、构，并对平均成本和平均存取时间分别进行排序，根据平均成本和平均存取时间的乘积值，选择最优设计。6.(1)当M的容量为64KB时，平均存取时间ta=74ns；当M的容量为128KB时，平均存取时间ta=38ns；当M的容量为256KB时，平均存取时间ta=。c=$KB;当M的容量为64KB时，整个存储器系统的平均成本当M的容量为128KB时，整个存储器系统的平均成本c=$KB;当M的容量为256KB时，整个存储器系统的平均成本c=$KR第三种方案为最优设计7.假设在一个由Cache和主存构成的两级存储系统中，h1、t八s1和c分别为CPU方问Cache的命中率、Cache 的存取时间、存储容量和

8、每字节成本，t2、s2和c2分别为主存的存取时间、存储容量和每字节成本。若 h1=、 t1=20ns、s1=512KB c=$10/KB及c?=$5/KB, t?和s?未知，而整个存储器系统的预算上限为 $15000。推导此存储器系统的等效存取时间t a的公式。推导此存储器系统的总成本公式。在不超出预算的前提下，s2的最大值为多少 KB为了使ta=40ns,主存的存取时间12应为多少ns7.(1)t a=19+ (2)C total =5120+5s2 (3)1976KB (4)420ns8.有16个存储器模块，每个模块的容量为4MB字长为32位。现在要用这16个存储器模块构成一个主存储器，有

9、如下二种组织方式：方式1: 16个存储器模块用高位交叉方式构成存储器;方式2: 16个存储器模块用低位交叉方式构成存储器。写出访问各种存储器的地址格式；比较各种存储器的优缺点；不考虑访问冲突，计算各种存储器的频带宽度；画出各种存储器的逻辑示意图。.(1)方式1 (高位交叉)的存储器的地址格式为：4 位20位模块选择字地址方式2 (低位交叉)的存储器的地址格式为:20 位字地址模块选择方式1 (高位交叉)的存储器的优点为：当多处理机发出的访存地址的高4位均不相同时，可对共享存储器内的不同存储体进行同时存取，这种存储器一般适合于共享存储器的多处理机系统；缺点为：当 多处理机发出的访存地址的高4位均

10、相同时，便产生了存储器的分体冲突，此时的存储器的频宽与单体存储器的相同。方式2 (低位交叉)的存储器的优点为：当处理机依次发出的访存地址的低4位均不相同时，可对存储器内的不同存储体进行并行存取，这种存储器一般适合于单处理机内的高速数据存取及带Cache的主存;缺点为：当处理机依次发出的访存地址的低4位均相同时，便产生了存储器的分体冲突，此时的存储器的频宽与单体存储器的相同。若不考虑访问冲突，二种方式的存储器的频带宽度均为64字节/存储周期；(4)二种存储器的逻辑示意图类似课本第3章图和图。.在一个具有8个存储体的低位多体交叉存储器中，如果处理器的访存地址为以下8进制或16进制值，分别求该存储器

11、的平均访问速率为单体存储器的多少倍。(忽略初启时的延迟)(1)10018、10028、10038、11008(2)10028、10048、10068、12008(3)1003- 1006伯、1009伯、1300169.(1)8 ; (2)4 ; (3)811.在页式虚拟存储器中，一个程序由P1P5共5个页面组成。在程序执行过程中依次访问到的页面如下： P2, P3, P2, P1, P5, P2, P4, P5, P3, P2, P5, P2假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LRU和OPT三种页面替换算法对这 3页主存进行调度。分别画出这三种替换算法对同一页地址流的调度

12、过程，并计算每种替换算法获得的命中率。11.FIFO替换算法对页地址流的调度过程如图所示。图FIFO替换算法对页地址流的调度过程采用FIFO替换算法的页命中率为。LRU替换算法对页地址流的调度过程如图所示。图LRU替换算法对页地址流的调度过程采用LRU替换算法的页命中率为。OPT替换算法对页地址流的调度过程如图所示。图OPT替换算法对页地址流的调度过程 采用OPT替换算法的页命中率为。16.假设在一个采用组相联映象的 Cache存储器中，Cache的容量为1KB,要求Cache的每一块在一个主存 周期内能从主存取得。主存采用模 32交叉，每个分体的宽度为 64位，主存的总容量为 4MB采用按地

13、址 访问存储器构成的相联目录表，实现主存地址到Cache地址的变换，并约定采用 2个外相等比较电路。请设计主存地址格式和 Cache地址格式，并标出各段的位数；若替换算法采用LRU算法，对于如下主存块地址流：1、4、1、4、7、1、9、4、27、7,如主存中内容一开始未装入 Cache中，请列出随时间变化 Cache中各块的使用状况，求出此期间Cache的块命中率。 16.(1) 主存地址格式如下：随时间变化Cache中各块的使用状况如图所示。图随时间变化Cache中各块的使用状况此期间Cache的块命中率为。17.一个组相联映象 Cache由64个存储块构成，每组包含 4个存储块，主存包含

14、4096个存储块，每 块由128字组成，访存地址为字地址。设计主存地址格式和Cache地址格式并标出各字段的位数。17.主存地址格式如下：20.设某计算机的Cache-主存存储层次采用组相联映象和LRU替换算法，已知主存容量为1MB Cache容量为8KB,按4字块分组，每个字块的长度为8个字(32位/字)。假设Cache起始内容为空，CPlM主存单元0, 1, 2,，2079依次读出2080个字，并重复此一读数序列共 5次。问Cache的地址命中率为 多少20.3.指令的解释方式采用顺序、一次重叠和流水，其主要差别在什么地方流水方式与完全重复增加多 套解释部件的方式相比各有什么优缺点3.指令

15、的解释方式采用顺序、一次重叠和流水，其主要差别在于可并行解释指令的条数；流水方式 与完全重复增加多套解释部件的方式相比，其优点是省硬件、成本低，但缺点是控制复杂，要解决好指令 相关、数据相关，以及流水线的中断等问题。5.一台非流水处理器 X的时钟频率为25MHz平均CPI为4。处理器丫是对X机的改进，它有一条5级流水 线，各级经过的时间为一个时钟周期。但由于锁定器延迟和时钟扭斜效应，其时钟频率仅为20MHZ若含有100条指令的程序运行在两台处理机上时，假设每条指令之间不发生任何相关，求处理机Y相对于处理机X的加速比为多少计算执行此程序时每台处理机的MIPS速率。5.(1)；(2)X处理机的MI

16、PS速率为；Y处理机的MIPS速率为。9.已知一条由5个功能段组成的浮点加法流水线，每个功能段的延迟时间均为t,流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算 ，画出流 水线时-空图，并计算流水线的实际吞吐率、加速比和效率。9.流水线时-空图如图所示；流水线的实际吞吐率、加速比和效率分别为3/(7 At) 和 o10.一条线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均为t。流水线的输入端与输出端之间有直接数据通路，而且设置有足够的缓冲寄存器。现在用这

17、条流水线计算，画出流水线时-空图，并计算流水线的实际吞吐率、加速比和效率。10.流水线时-空图如图所示；流水线的实际吞吐率、加速比和效率分别为1/(2 At)、2和。13.已知一流水线有5个功能段，依次分别为 S1、S2、S3、S4、S5,其中流经S2需要2 At的时间，流经 S4需要3At的时间，其余各段所需时间均为t。现有6个任务流入流水线，要求：求流水线的实际吞吐率和效率；若把S2段进一步细分，S4段并联，令流水线最大吞吐率为1/ At ,画出流水线时-空图，并求流水线的效率。13.(1)流水线的实际吞吐率为 6/(23 At);效率为% o流水线时-空图如图所示；流水线的效率为 % o

18、14.在一个5段的流水线处理机上需经 9拍才能完成一个任务，其预约表如图所示，分别写出延迟禁止表、 冲突向量，并求出最小平均延迟、流水线的最大吞吐率及其调度方案。若按此调度方案输入6个任务，求实际吞吐率TP。图预约表14.延迟禁止表 F=1 , 3, 4, 8;冲突向量C=;最小平均延迟为拍；调度方案为(2 , 5);实际吞吐率TP=6/(25拍)。4.设32个处理器的编号分别为 0、1、2、31,用单级互连网络互连，若互连函数为：(1)Cube 3(2)PM2 +3(3)PM2 -4(4)Shuffle(5)Butterfly(6)Shuffle(Shuffle)Shuffle(Cube o

19、(PM2i)时，第11号处理器各与哪一个处理器相连.(1)3 ;(2)19;(3)27;(4)22;(5)26;(6)13 ;(7)16.在有8个处理器的混洗交换网络中，若要使第0号处理器与第5号处理器相连需要经过多少次混洗和多少交换以连接图的形式表明其变化过程。5.需要经过2次混洗和2次交换，其连接图如图所示。图 实现第0号处理器与第5号处理器相连的连接图6.一个N=8的混洗交换网络如图所示。试问此网络结点度为多少网络直径为多少网络的等分带宽为 多少6.此网络结点度为4;网络直径为5;网络的等分带宽为 4条链路的带宽之和。13.试在含一个PE的SISD机和在含8个PE且连接成一线性环的SIM

20、D机上计算下列求内积的表达式：假定完成每次加操作需 2个单位时间，完成每次乘操作需4个单位时间，沿双向环在相邻PE间移数需 1个单位时间。(1)SISD计算机上计算S的时间是多少(2)SIMD计算机上计算S的时间是多少(3) 用SIMD机计算S相对于SISD机计算的加速比是多少13.(1)190 个单位时间；(2)32 个单位时间；(3)17.当编号分别为0、1、2、15的16个处理器之间，要求按下列配对通信：(12,7), (1,10), (15,4), (5,14), (8,3), (6,13), (11,0), ( 2,9 )。试选择互连网络类型、控制方式，并画出该互连网络的拓扑结构和各

21、级交换开关状态图。17.采用4级立方体网络，级控制。互连网络的拓扑结构和各级开关的状态设置如图所示。图N=16的互连网络拓扑及开关状态图19.并行处理机有16个处理器，要实现相当于先8组2元交换，然后是4组4元交换，最后是2组8元交换，请写出此时各处理器之间所实现的互连函数的一般关系式。(P 3P2RP0) = P 3P2P1P05.在CRAY-1向量处理机上，V为向量寄存器，设向量长度均为64,所用浮点功能执行部件的执行时间分别 为：加法需6拍，相乘需7拍，从存储器读数需6拍，求倒数近似值需14拍，打入寄存器及启动功能部件(包括存储器)各需1拍。问下列各指令组中的哪些指令可以链接执行哪些指令可以并行执行试说明其原因并分别计算出各指令组全部执行完所需的拍数。 TOC o 1-5 h z 5.(1)3条向量指令并行执行；全部向量指令执行完所需的时间为72拍。第1、2条向量指令并行执行；由于第 3条向量指令与第1、2条向量指令之间存在源目向量相关，因此它们之间可以链接执行；全部向量指令执行完所需的时间为80拍。第1、2条向量指令并行执行；第 3条与第2条向量指令之间存在功能部件冲突，因此第 3条向量 指令只能与前2条向量指令串行执行；第 4条向量指令与第3条向量指令之间存在源目向量