Cache存储器空间块的映像关系示意图
时间： 21:44:43
&&&&&&&&系统结构习题&&&&第一章&&&&1.1解释下列术语：层次结构，计算机系统结构，计算机组成，计算机实现，透明性，由上而下设计，由下而上设计，由中间向两边设计，软件兼容，向上兼容，固件，系列机，兼容机，模拟，仿真，虚拟机，宿主机，指令流，数据流，单指令流单数据流，多指令流多数据流，CPI，MIPS，Amdahl定律。1．2存储程序计算机的主要特征是什么？存在的主要问题是什么？目前的计算机系统是如何改进的？1．3从机器（汇编）语言程序员看，以下哪些是透明的？指令地址寄存器，指令缓冲器，时标发生器，先行进位链，条件码寄存器，乘法器，主存地址寄存器，移位寄存器，通用寄存器，中断字寄存器，磁盘外设。1．4如有一个经解释实现的计算机，可以按功能分成4级。每一级为了执行一条指令需要下一级N条指令解释。若执行第一级的一条指令需Kns时间，那么执行第2、3、4级的一条指令各需要用多少时间？1．5假定你是一个计算机设计者，对高级语言结构的使用研究表明，过程调用是最常用的操作之一。你已设想了一个优化设计方案，它能减少过程调用和返回所需的取/存指令次数。为了进行验证，对未加优化和已优化的方案进行实验测试，假定所使用的是相同的优化编译器。实验测得的结果如下：（1）未优化的时钟周期比优化的快5%；（2）未优化方案中的取/存指令数占总指令数的30%；（3）优化方案中的取/存指令数比未优化的少1/3，对于其他指令，两种方案的动态执行数没有变化；（4）所有指令，包括取/存指令，均只需要1个时钟周期。要求你定量地判断，哪一种设计方案的计算机工作速度更快。1．假设在一台40MHz处理器上运行200000条指令的目标代码，6程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：指令类型算术和逻辑高速缓存命中的加载/存储转移高速缓存缺失的存储器访问CPI1248指令混合比60%18%12%10%&&&&&&&&（1）计算在单处理机上用上述跟踪数据运行程序的平均CPI。（2）根据（1）所得CPI，计算相应MIPS速率。1．7对于一台40MHz计算机执行标准测试程序，程序中指令类型，执行数量和平均时钟周期数如下：指令类型整数数据传送浮点分支指令执行数量001500平均时钟周期数1242&&&&&&&&求该计算机的有效CPI、MIPS和程序执行时间。&&&&&&&&1&&&&&&&&&&&&1．8计算机系统中有三个部件可以改进，这三个部件的部件加速比如下：部件加速比1=30部件加速比2=20部件加速比3=10（1）如果部件1和部件2的可改进比例均为30%，那么当部件3的可改进比例为多少时，系统加速比才可以达到10？（2）如果三个部件的可改进比例分别为30%、30%和20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？（3）如果相对某个测试程序三个部件的可改进比例分别为20%，20%和70%，要达到最好改进效果，仅对一个部件改进时，要选择哪个部件？如果允许改进两个部件，又如何选择？1．9在某个程序中，简单指令占80%，复杂指令占20%，在CISC机中简单指令执行需4个机器周期，复杂指令执行需8个机器周期。RISC机中简单指令执行只需1个机器周期，而复杂指令要通过一串指令来实现。假定复杂指令平均需要14条简单指令，即需要14个周期，若该程序中需要执行的总指令数为1000000，Tc为100ns，那么（1）RISC机需执行的指令数为多少？（2）CISC和RISC机的CPU时间分别为多少？（3）RISC机对CISC的加速比为多少？1．10假定利用增加向量处理模块来提高计算机的运算速度。计算机处理向量的速度比其通的运算要快20倍。将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。（1）求出加速比S和可向量化百分比F之间的关系式。（2）当要得到加速比为2时的可向量化百分比F为多少？（3）为了获得在向量模式所得到的最大加速比的一半，可向量化百分比F为多少？&&&&&&&&第二章&&&&2．1解释下列术语：数据表示，寻址方式，有效地址，逻辑地址，物理地址，静态再定位，动态再定位，堆栈型机器，累加器型机器，通用寄存器型机器，高级语言机器，Huffman编码概念，扩展操作码，CISC，RISC。2．2考虑一个浮点数系统，所使用的阶基rp=2，阶码位数p=2,，尾数基值rm=10，以rm为基的尾数位数m’=1，按照使用的位数来说，等价于m=4，试计算在非负阶、正尾数、规格化情况下的最小尾数值和最大尾数值、最大阶值、可表示的最小值和最大值及可表示的数个数。2．3设某机阶码为6位，尾数48位，阶符和数符不在其内，当尾数分别以2、8、16为基时，在非负阶、正尾数、规格化数的情况下，求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最大值和最小值及可表示的规格化数的总个数。2．4变址寻址和基址寻址各适合于何种场合？设计一种只用6位地址码就可以指向一个大地址空间中任意64个地址之一的寻址机构。2．5假设有A和B两种不同类型的处理机，A处理机中的数据不带标志符，其指令字长和数据字长均为32位。B处理机的数据带有标志符，每个数据的字长增加至36位，其中有4位是标志符，它的指令数由最多256条减少到不到64条。如果每执行一条指令平均要访问两个操作数，每个存放在存储器中的操作数平均要被访问8次。对于一个由1000条指令组成的程序，分别计算这个程序在A处理器和B处理器所占用的存储空间大小（包括指令和数据），从中得到什么启发？2．6设计如IBM370那样有基地址寄存器的机器的另一种办法是，每条指令不用现在的基地址寄存器地址（4位）加位移量（12位）共16位作为地址码，而是让每条指令都有一个24位的直接地址。针对这两种情况评价一下这个方法的优缺点：&&&&&&&&2&&&&&&&&&&&&（1）数据集中于有限几块，但这些分布在整个存储空间：（2）数据均匀地分布在整个地址空间中。你认为IBM370的设计者在实际应用中考虑着两种情况的哪一种可能性大？为什么？2．7若某机要求有如下形式的指令：三地址指令4条，单地址指令255条，零地址指令16条。设指令地址字长为12位，每个地址码长为3位，问能否以扩展操作码为其编码？如果其中单地址指令为254条呢？说明其理由。2．8何谓指令优化？简要列举包括操作码和地址码两部分的指令格式优化可采用的各种途径和思路。2．9某模型机有9条指令，其使用频率为ADD（加）30%SUB（减）24%JOM（按负转移）6%7%JMP（转移）7%SHR（右移）2%STO（存）CIL（循环左移）3%CLA（清加）20%STP（停机）1%要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设该机有若干个通用寄存器，主存有16位宽按字节编址，采用整数边界存储，任何指令都在一个主存周期中取得，短指令为寄存器—寄存器型，长指令为寄存器—主存型，主存地址应能变址寻址。（1）仅根据使用频度，不考虑其他因素，设计出全Huffman操作码，并计算出该操作码方式的平均码长；（2）考虑题目其他全部要求，设计优化的实用指令操作码形式，并计算操作码的平均码长；（3）该机允许使用多少可编址的通用寄存器？（4）画出该机两种指令字格式，标出各字段之位数；（5）指出访存操作数地址寻找的最大相对位移量为多少个字节？2．10用于文字处理的某专用机，每个字符用4位十进制数字（0~9）编码表示，空格则用‘’表示，在对传送的文字符和空格进行统计后，得出它们的出现频率分别为：20%0：17%1：6%2：8%3：11%4：8%5：5%6：8%7：13%8：3%9：1%（1）若上述数字和空格均用二进制码编码，，试设计二进制信息位平均长度最短的编码；（2）若传送106个文字符号（每个文字浮后均跟一个空格），按最短的编码，共需传送多少个二进制位？（3）若十进制数字和空格均用4位二进制编码，共需传送多少个二进制位？2．11处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令3类，并假设每个地址的长度均为6位。（1）如果双地址指令有15条，单地址指令和零地址指令的条数基本相同，问单地址和零地址指令各有多少条？并且为这3类指令分配操作码。（2）如果要求3类指令的比例大致为1：9：9，问双地址指令、单地址指令和零地址指令各有多少条？并且为这3类指令分配操作码。2．12什么叫高级语言机器？一般有哪两种方式实现？高级语言难以发展的主要原因是什么？2．13简要比较CISC机器和RISC机器各自的结构特点，它们分别存在哪些不足和问题？为什么说今后的发展方向应是CISC和RISC的结合？2．14为某城市设计一火车订票系统，在城市各点设置了若干售票处，全部车票信息以文件形式集中存放在系统之主存中，为各售票处终端微机所共享，请设计一种办法保证各售票处不会卖出重票（即同一车票），简述这种办法的具体要求和可能出现的问题。&&&&&&&&3&&&&&&&&&&&&第三章&&&&3．1解释下列术语：存储层次（体系），虚拟存储器，Cache存储器，多体交叉存储器，页式管理，段式管理，段页式管理，程序局部性，存储器频宽，平均访问时间，LRU算法，优化算法，堆栈型替换算法，地址映像，地址变换，全相连映像，直接映像，组相连映像，写回法，写直达法，不命中预取法，恒预取法，按写分配法，命中率，热启动失效率，。3．2由三个访问速度、存储容量和每位价格都不相同的存储器构成一个存储体系。其中，M1靠近CPU，回答下列问题：M1(T1,S1,C1)(1)M2(T2,S2,C2)M3(T3,S3,C3)&&&&&&&&写出这个三级存储体系的等效访问时间T，等效存储容量S和等效每位价格C的表达式。(2)在什么条件下，整个存储体系的每位价格接近于C3？3．3简述“Cache—主存”层次与“主存—辅存”层次的区别。3．4要求主存实际频宽为4MB/s，现设主存每个分体的存储周期为2us,宽度为4个字节，采用模m多体交叉存取，但实际频宽只能达到最大频宽的0.6倍，问主存模数m应取多少方能使两者的速度基本匹配？其中m取2的幂。3．5采用页式管理的虚拟存储器中，什么叫“页面失效”？什么叫“页面争用”？什么时候，这两者不同时发生？什么时候，这两者又同时发生？3．6某虚拟存储器共8个页面，每页为1024个字，实际主存为4096个字，采用页表法进行地址映像。映像表的内容如右表所示。实页号装入位（1）列出会发生页面失效的全部虚页号；31（2）按以下虚地址计算主存实地址：110，，，．7一个虚拟存储体系最多有64个用户，每个用户程序最大不超过308192页，每页4KB，主存容量64MB。为了加快地址变换过程，采用2110快慢表结构，快表的容量为64个存储字，快表地址经散列函数变换得01到。为避免散列冲突，需要一个相等比较器。00（1）写出虚拟地址的格式，标出各字段的名称和长度。（2）写出主存地址的格式，标出各字段的名称和长度。（3）散列变换部件的输入位数和输出位数各为多少？（4）相等比较器的位数是多少？（5）写出快表每个存储字的格式，标出各字段的名称和长度。3．8在页式虚拟存储器中，一个程序由P1~P5共5个虚页组成。在程序执行过程中依次访问到的页面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LRU和OPT三种替换算法对这三页主存进行调度。（1）画出主存页面调入、替换和命中的情况表。（2）统计三种页面替换算法的页命中率。3．一个程序由5个虚页构成，9采用LRU算法，在程序执行过程中依次访问的页地址流如下：P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3（1）可能的最高页命中率是多少？&&&&&&&&4&&&&&&&&&&&&至少要分配给该程序多少个主存页面才能获得最高的命中率？如果在程序执行过程中每访问一个页面，平均要对该页面内的存储单元访问1024次，求访问存储单元的命中率。3．10假定一个由16个存储器模块构成的主存储器系统有下列3种交叉存储器设计方案，每个模块的容量为1MB，机器按字节寻址。设计1：用1个存储体16路交叉；设计2：用2个存储体8路交叉；设计3：用4个存储体4路交叉。（1）确定上述每种存储器组织的地址格式。（2）在上述每种存储器组织中，假定只有一个存储器模块失效，确定能获得的最大存储器频宽。，Cache为4个块（0～3），3．11有一个“Cache—主存”存储层次。主存共分8个块（0～7）采用组相连映像，组内块数为2块，替换算法为近期最少使用算法（LRU）。（1）画出主存、Cache存储器地址的各字段对应关系（标出位数）；（2）画出主存、Cache存储器空间块的映像关系示意图；（3）对于如下主存块地址流：1、2、4、1、3、7、0、1、2、5、4、6、4、7、2，如主存中内容一开始未装入Cache中，请列出随时间的Cache中各块的使用状况；（4）对于（3），指出块失效又发生块争用的时刻；（5）对于（3），求出此间Cache之命中率。3．12给定以下的假设，试计算直接映像Cache和两路组相连Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？假设：（1）理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.2次；（2）两种Cache容量均为64MB，块大小都是32字节；（3）组相连Cache中的多路选择器使CPU的时钟增加了10％；（4）这两种Cache的失效开销都是80ns；（5）命中时间为1个时钟周期；（6）64KB直接映像Cache的失效率为1.4％，64KB两路相连Cache的失效率为1.0％。3．13在一个Cache存储系统中，Cache的访问周期为10ns，主存储器的访问周期为60ns，每个数据在Cache中平均重复使用4次。当块的大小为1个字时，存储系统的访问效率只有0.5，现在要通过增加块大小，使存储系统的访问效率达到0.94。（1）当存储系统的访问效率为0.5时，计算命中率和等效访问周期。（2）为了使存储系统的访问效率达到0.94，命中率和等效访问周期应提高到多少？（3）为了使存储系统的访问效率从0.5提高到0.94，块的大小至少增加到几个字？3．14采用组相连映像，LRU替换算法的“Cache—主存”层次，发现等效访问速度不高，为此，建议：（1）增大主存容量；（2）增大Cache中的块数（块的大小不变）（3）增大组相连的组的大小（块的大小不变）（4）增大块的大小（组的大小和Cache总容量不变）（5）提高Cache本身器件的访问速度。3．15你对现有“Cache”存储层次的速度不满意，于是你申请到一批有限的经费，为了能发挥最大的经济效益，有人建议你去买一些同样速度的高速缓冲存储器片子对高速缓冲存储器容量加以扩充；而另一些人却建议你不如干脆买更高速的缓冲存储器片子更换掉现有低速的缓冲存储器片子。你认为那种建议可取，你如何作决定？为什么？3．试列举Cache存储器和虚拟存储器在软硬功能分配及具体实现上至少有4个方面的差别，16并简述理由。&&&&&&&&（2）（3）&&&&&&&&5&&&&&&&&&&&&第四章&&&&4．1解释下列术语：指令级并行，指令调度，动态调度，指令的重叠解释，操作数相关，指令相关，单功能流水线，多功能流水线，静态流水线，动态流水线，线性流水线，非线性流水线，流水线吞吐率，流水线效率，全局性相关，局部性相关，先读后写相关，先写后读相关，写—写相关，不精确断点法，精确断点法，顺序发射顺序完成，顺序发射乱序完成，乱序发射乱序完成，向量处理机，超标量处理机，超流水线处理机，超标量超流水线处理机。4．2指令的解释方式采用顺序、一次重叠和流水，其主要差别在什么地方？流水方式与完全重复增加多套解释部件的方式相比各有什么优缺点？4．3在流水线处理机中，可能有哪几种操作数相关？这几种相关分别发生在什么情况下？解决操作数相关的基本方法有哪几种？4．4在一台单流水线多操作部件上执行下面的程序，取指令、指令译码各需要一个时钟周期，MOVE、ADD和MUL操作各需要2个、3个、和4个时钟周期。每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k：MOVER1，R0；R1←（R0）k+1：MULR0，R2，R1；R0←(R2)×(R1)k+2：ADDR0，R2，R3；R0←(R2)+(R3)（1）就程序本身而言，可能有哪几种数据相关？（2）在程序实际执行过程中，有哪几种数据相关会引起流水线停顿？（3）画出指令执行过程的流水线时空图，并计算执行完这三条指令共使用了多少各时钟周期？4．5若有一个浮点乘法流水线如图（A）所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A×B×C×D的时空图以及输入端的变化，并求出该流水线的吞吐率和效率；当流水线改为图(B)形式时，求实现同一计算时，该流水线的效率及吞吐率。&&&&3△t△t3△t△t&&&&&&&&操作数&&&&&&&&积操作数&&&&&&&&尾乘&&&&△t△t&&&&&&&&阶加&&&&&&&&尾乘&&&&&&&&规格化&&&&&&&&积&&&&&&&&阶加&&&&&&&&尾乘尾乘&&&&&&&&规格化&&&&&&&&（A）(B)3△t4．6某个流水线由4个功能部件组成，每个功能部件的延迟时间为△t，当输入10个数据后，间歇5△t，又输入10个数据，如此周期的工作。求此流水线的吞吐率，并画出时空图。4．7假设分支概率如下（相对于所有指令）：条件分支：20％跳转和过程调用：5％其中，条件成功分支有60％可能执行。在一个4段的流水线中，如果分支指令在第2个时钟周期末决定是否是条件失败分支，在第3个时钟周期末决定是否是条件成功分支。假定第1个时钟周期的操作和条件分支无关，并且忽略其它流水线停顿，那么，如果没有控制相关，处理机能快多少？4．8如图给出了一个非线性流水线。若4条指令依次间隔2△t进入流水线，求出其实际的吞吐率和效率并画出时空图。如果用加快流水，使流水线每隔2△t流出一个结果，应减少哪个流水段本身经过的时间？应减少到多少，流水线方能满足要求？求出此时连续流入4条指令时的实际吞吐率和效率。&&&&&&&&6&&&&&&&&&&&&循环一次&&&&2△t2△t2△t2△t&&&&&&&&1&&&&&&&&2&&&&&&&&3&&&&10&&&&&&&&4&&&&&&&&4．9用一条有5个功能段的浮点加法器计算F=&&&&&&&&∑Ai&&&&i=1&&&&&&&&。每个功能段的延迟时间均相等，流&&&&&&&&水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。4．10一条有3个功能段的流水线如图，每个功能段的延迟时间都相等，为△t。功能段S2的输出返回到它自己的输入端循环一次。（1）如果每隔一个△t向流水线输入端连续输入新任务，问这条流水线会发生什么情况？（2）求这条流水线能够正常工作的最大吞吐率。加速比和效率？（3）有什么办法能够提高这条流水线的吞吐率？画出新的流水线。&&&&&&&&输入&&&&&&&&S1&&&&△t&&&&&&&&S2&&&&△t&&&&&&&&S3&&&&△t&&&&&&&&输出&&&&&&&&4．11一条4个功能段的非线性流水线，每个功能段的延迟时间都相等，都为20ns，它的预约表如下：&&&&时间功能段&&&&&&&&1╳&&&&&&&&2&&&&&&&&3&&&&&&&&4&&&&&&&&5&&&&&&&&6&&&&&&&&7╳&&&&&&&&S1S2S3S4&&&&&&&&╳╳╳╳&&&&&&&&╳&&&&&&&&（1）写出流水线的禁止向量和初始冲突向量。（2）画出调度流水线的状态图。（3）求流水线的最小启动循环和最小平均启动距离。（4）求平均启动距离最小的恒定循环。（5）求流水线的最大吞吐率。&&&&&&&&（6）照最小启动循环连续输入10个任务，求流水线的实际吞吐率。（7）画出该流水线各功能段之间的连接图。4．12一条静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。用这条流水线计算：&&&&6&&&&&&&&F=&&&&&&&&∑(Ai*Bi)&&&&i=1&&&&&&&&画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。&&&&&&&&4．13下面一段程序在一台超标量处理机上运行，每个时钟周期发射两条指令。所有指令都要经过“取指令”“执行”“译码”和“写结果”四个阶段，其中，、。“取指令”“译码”和“写、结果”三个阶段的延迟时间都为一个时钟周期，在“执行”阶段，访问存储器部件和逻辑操作部件各延迟一个时钟周期，加法操作部件延迟两个时钟周期，乘法操作部件延迟3个时钟周期，4种操作部件各设置一个。加法部件和乘法部件都采用流水线结构，每一级流水线的延迟时间都为一个时钟周期。每个操作部件的输出都有直接数据通路连接到其它操作部件的输入端。k：LOADR0，A；R0←Cache的（A）单元k+1：ADDR1，R0；R1←（R1）＋（R0）&&&&&&&&7&&&&&&&&&&&&k+1：STORER1，B；Cache的B单元←（R1）ADDR2，R3；R2←（R2）+（R3）k+3：k+4：MULR3，R4；R3←（R3）×（R4）ORR5，R6；R5←（R5）∨（R6）k+5：k+6：ADDR5，R7；R5←（R5）＋（R7）（1）列出程序中可能出现的所有数据相关。（2）采用顺序发射顺序完成调度方法，画出流水线的时空图，并计算执行这个程序所用的时间。（3）采用顺序发射乱序完成调度方法，画出流水线的时空图和各操作的完成时间图，并计算执行这个程序所用的时间。（4）如果再增加一个能够存放7条指令的先行窗口，采用乱序发射乱序完成调度方法，画出流水线的时空图、各操作的发射时间图和完成时间图，并计算执行这个程序所用的时间。4．14一条3个功能段的非线性流水线如图：预约表如图：&&&&输出&&&&&&&&输入&&&&&&&&S1&&&&&&&&S2&&&&&&&&S3&&&&&&&&时间功能段&&&&&&&&1╳&&&&&&&&2&&&&&&&&3&&&&&&&&4&&&&&&&&5╳&&&&&&&&S1S2S3&&&&&&&&╳╳&&&&&&&&╳╳&&&&&&&&（1）写出流水线的禁止向量和初始冲突向量，并画出调度流水线的状态转换图。（2）求流水线的最小启动循环和最小平均启动距离。（3）通过插入非计算延迟功能段使该流水线达到最优调度，确定该流水线的最佳启动循环及其最小平均启动距离。&&&&&&&&（4）画出插入非计算延迟功能段后的流水线连接图及其预约表。（5）画出插入非计算延迟功能段后的流水线状态转换图。（6）在插入非计算延迟功能段前后，分别计算流水线的最大吞吐率，并计算最大吞吐率改进的百分比。4．15在CRAY—1机上，设向量长度均为64；所用浮点功能部件的执行时间分别为：相加需6拍，相乘需7拍，求倒数近似值需14拍；从存储器读数需6拍；打入寄存器及启动功能部件各需1拍，问下列各指令组，组内的哪些指令可以连接？哪些指令不可连接？不能连接的原因是什么？并分别计算出各指令组全部完成所需的拍数。（1）V0←存储器(2)V2←V0×V1V1←V2＋V3V3←存储器V4←V5×V6V4←V2＋V3（3）V0←存储器(4)V0←存储器V2←V0×V1V1←1/V0V3←V2+V0V3←V1×V2V5←V3+V4V5←V3+V4&&&&&&&&第5～8章（基本概念）&&&&并行处理机，多处理机，阵列机，数据流机，集群计算机，多端口存储器，相连存储器，相连处理机，互连网络，交叉开关网络，紧耦合处理机，松耦合处理机，RISC，CISC。&&&&&&&&8&&&&&&&&&&&&系统结构部分习题答案&&&&1．3从机器（汇编）语言程序员看，以下哪些是透明的？答：时标发生器，条件码寄存器，乘法器，先行进位链，移位寄存器，条件码寄存器，指令缓冲器，磁盘外设。1．4如有一个经解释实现的计算机，可以按功能分成4级。每一级为了执行一条指令需要下一级N条指令解释。若执行第一级的一条指令需Kns时间，那么执行第2、3、4级的一条指令各需要多少时间？答：第1级：Kns第2级：NKns第3级：N2Kns第4级：N3Kns1．7对于一台40MHz计算机执行标准测试程序，程序中指令类型，执行数量和平均时钟周期数如下：指令类型整数数据传送浮点分支指令执行数量001500平均时钟周期数1242&&&&&&&&求该计算机的有效CPI、MIPS和程序执行时间。答：CPI=CPU时钟周期总数/IC（指令条数）=(*2+0*2)/IC=1.78IC（指令条数）=+9500CPU时间=IC*CPI/f=5762usMIPS=IC/（CPU时间*106）=f/（CPI*106）=22.471．8计算机系统中有三个部件可以改进，这三个部件的部件加速比如下：部件加速比1=30部件加速比2=20部件加速比3=10（4）如果部件1和部件2的可改进比例为30%，那么当部件3的可改进白了比例为多少时，系统加速比才可以达到10？（5）如果三个部件的可改进比例分别为30%，30%和20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？（6）如果相对某个测试程序三个部件的可改进比例分别为20%，20%和70%，要达到最好改进效果，仅对一个部件改进时，要选择哪个部件？如果允许改进两个部件，又如何选择？&&&&&&&&9&&&&&&&&&&&&答：（1）S1=30,S2=20,S3＝10，SN=10F1=0.3,F2=0.3,求F3=?SN=1/[1-(F1+F2+F3)+F1/S1+F2/S2+F3/S3]F3=0.36(2)S1=30,S2=20,S3＝10F1=0.3,F2=0.3,F3=0&&&&.2求不可加速部分执行时间/总执行时间=?不可加速部分执行时间=[1-(F1+F2+F3)]T0总执行时间=TNSN=T0/TN=1/[1-(F1+F2+F3)+F1/S1+F2/S2+F3/S3]=4.08不可加速部分执行时间/总执行时间=[1-(F1+F2+F3)]T0/TN=81%（3）S1=30,S2=20,S3＝10，F1=0.2,F2=0.3,F3=0.2仅对一个部件改进，改进部件1仅对两个部件改进，改进部件1、21．10假定利用增加向量处理模块来提高计算机的运算速度。计算机处理向量的速度比其通的运算要快20倍。将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。（4）求出加速比S和可向量化百分比F之间的关系式。（5）当要得到加速比为2的可向量化百分比F为多少？（6）为了获得在向量模式所得到的最大加速比的一半，可向量化百分比F为多少？答：（1）S=1/[（1-F）+F/S]=1/[（1-F）+F/20]（2）SN=2，求F2=1/[（1-F）+F/20]，F=10/19=0.53=53%（7）SN=10，求F10=1/[（1-F）+F/20]，F=18/19=0.95=95%2．5假设有A和B两种不同类型的处理机，A处理机中的数据不带标志符，其指令字长和数据字长均为32位。B处理机的数据带有标志符，每个数据的字长增加至36位，其中有4位是标志符，它的指令数由最多256条减少到不到64条。如果每执行一条指令平均要访问两个操作数，每个存放在存储器中的操作数平均要被访问8次。对于一个由1000条指令组成的程序，分别计算这个程序在A处理器和B处理器所占用的存储空间大小（包括指令和数据），从中得到什么启发？答：A机：1000*32（位指令）+/8（位数据）=40000（位）B机：1000*30（位指令）+/8（位数据）=39000（位）40000由此看出，由于数据的平均访问次数要大于指令，所以，通过改进数据的格式来减少指令的长度，可以减少总的存储空间的大小。2．11处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令3类，并假设每个地址的长度均为6位。（3）如果双地址指令有15条，单地址指令和零地址指令的条数基本相同，问单地址和零地址指令各有多少条？并且为这3类指令分配操作码。（4）如果要求3类指令的比例大致为1：9：9，问双地址指令、单地址指令和零地址指令各有多少条？并且为这3类指令分配操作码。&&&&&&&&10&&&&&&&&&&&&答：（1）双地址指令15条用四位编码，两个操作数各占6位（共16位）单地址指令63条用十位编码~，一个操作数占6位（共16位）零地址指令64条用十六位编码（2）双地址指令14条，操作码：单地址指令26*2-2=126条，操作码：~零地址指令128条，操作码：~．9某模型机有9条指令，其使用频率为30%SUB（减）24%JOM（按负转移）6%ADD（加）STO（存）7%JMP（转移）7%SHR（右移）2%CLA（清加）20%STP（停机）1%CIL（循环左移）3%要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设该机有若干个通用寄存器，主存有16位宽按字节编址，采用整数边界存储，任何指令都在一个主存周期中取得，短指令为寄存器—寄存器型，长指令为寄存器—主存型，主存地址应能变址寻址。（6）仅根据使用频度，不考虑其他因素，设计出全Huffman操作码，并计算出该操作码方式的平均码长；（7）考虑题目其他全部要求，设计优化的实用指令操作码形式，并计算操作码的平均码长；（8）该机允许使用多少可编址的通用寄存器？（9）画出该机两种指令字格式，标出各字段之位数；指出访存操作数地址寻找的最大相对位移量为多少个字节？答：(1)Huffman树如图&&&&0.300.240.0.140..&&&&&&&&0&&&&&&&&0&&&&&&&&0.06&&&&&&&&1&&&&&&&&0.1200.56&&&&1&&&&&&&&1&&&&&&&&10.26&&&&&&&&1&&&&&&&&11.00&&&&&&&&9&&&&&&&&L（Huffman平均码长）＝&&&&&&&&∑Pi*Li＝(0.3+0.24+0.2)*2+(0.07+0.07+0.06)*4&&&&i=1&&&&&&&&+0.03*5+(0.02+0.01)*6=2.61(位/指令)&&&&&&&&11&&&&&&&&&&&&Huffman编码指令ADDSUBCLASTOJMPJOMCILSHRSTR编码&&&&&&&&扩展编码指令ADDSUBCLASTOJMPJOMCILSHRSTR编码&&&&&&&&L（扩展编码平均码长）＝（3*2+5*6）/9=4(位/指令)ADD、SUB、CLA设计为R-R型双操作数指令，允许使用可编址的寄存器为8个。后6条为R-S型双操作数指令，允许使用可编址的寄存器为8个。（4）R-R型双操作数指令233OPR-S型双操作数指令OPD3．7一个虚拟存储体系最多有64个用户，每个用户程序最大不超过8192页，每页4KB，主存容量64MB。为了加快地址变换过程，采用快慢表结构，快表的容量为64个存储字，快表地址经散列函数变换得到。为避免散列冲突，需要一个相等比较器。写出虚拟地址的格式，标出各字段的名称和长度。写出主存地址的格式，标出各字段的名称和长度。散列变换部件的输入位数和输出位数各为多少？相等比较器的位数是多少？写出快表每个存储字的格式，标出各字段的名称和长度。5RR3R&&&&&&&&(2)(3)&&&&&&&&（6）（7）（8）（9）&&&&&&&&答：（1）虚地址格式共31位6用户号（2）主存地址共26位14实页号（5）散列变换部件输入位数为19位，输出为6位。（6）相等比较器的位数是6+13=19位（7）快表格式共33位613用户号虚页号12页内地址13虚页号12页内地址&&&&&&&&14实页号&&&&&&&&12&&&&&&&&&&&&4．4在一台单流水线多操作部件上执行下面的程序，取指令、指令译码各需要一个时钟周期，MOVE、ADD和MUL操作各需要2个、3个、和4个时钟周期。每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k：MOVER1，R0；R1←（R0）MULR0，R2，R1；R0←(R2)×(R1)k+1：k+2：ADDR0，R2，R3；R0←(R2)+(R3)（4）就程序本身而言，可能有哪几种数据相关？（5）在程序实际执行过程中，有哪几种数据相关会引起流水线停顿？（6）画出指令执行过程的流水线时空图，并计算执行完这三条指令共使用了多少时钟周期？答：（1）K与K+1：先写后读相关K+1与K+2：写写相关（4）由流水线时空图看，K与K+1：先写后读相关在第4时钟周期会引起流水线停顿，而K+1与K+2：写写相关在第8时钟周期会引起流水线停顿。&&&&K+2K+1K&&&&&&&&IF1&&&&&&&&IFID2&&&&&&&&IFIDRR3&&&&&&&&IDRR*EX4&&&&&&&&RREXWB5&&&&&&&&EXEX6&&&&&&&&EXEX7&&&&&&&&WB*WB89&&&&&&&&（3）由流水线时空图看，共插入了3个时钟周期的停顿，执行完这三条指令共使用了11个时钟周期。IFIDidleidleRREXEXidleWBIFIDidleidleRREXEXEXWBIFIDRREXWB14．11一条4个功能段的非线性流水线，每个功能段的延迟时间都相等，都为20ns，它的预约表如下：&&&&K+2K+1K时间功能段&&&&&&&&1╳&&&&&&&&2&&&&&&&&3&&&&&&&&4&&&&&&&&5&&&&&&&&6&&&&&&&&7╳&&&&&&&&S1S2S3S4&&&&&&&&╳╳╳╳&&&&&&&&╳&&&&&&&&（6）写出流水线的禁止向量和初始冲突向量。（7）画出调度流水线的状态图。（8）求流水线的最小启动循环和最小平均启动距离。（9）求平均启动距离最小的恒定循环。（10）求流水线的最大吞吐率。&&&&&&&&（8）照最小启动循环连续输入10个任务，求流水线的实际吞吐率。（9）画出该流水线各功能段之间的连接图。答：（1）禁止向量：（2，4，6），初始冲突向量：（101010）。（2）状态图&&&&&&&&13&&&&&&&&&&&&7*&&&&&&&&101010&&&&7*3&&&&&&&&7*&&&&&&&&1111111&&&&57*&&&&&&&&101111&&&&&&&&（3）简单循环（1，7）（3，7）（3，5，7）（5，7）（5）（7）&&&&&&&&平均启动距离455657&&&&&&&&3&&&&&&&&最小平均启动距离4最小启动循环（1，7）&&&&5&&&&&&&&101011&&&&&&&&（4）平均启动距离最小的恒循环（5）（5）流水线的最大吞吐率假设用此流水线完成N个任务（N为偶数）：TPMAX=N/（N/2*12*△T）=1/（6△T）其中：*12表示每执行2个任务需要12个△T时间，N/2平均每6个△T完成一个任务。假设用此流水线完成N个任务（N为奇数）：TPMAX=N/[（（N-1）/2*12+5）*△T]其中：（N-1）/2*12表示每执行2个任务需要12个△T时间，5为最后一个任务多执行的周期数。&&&&时间功能段&&&&&&&&1╳&&&&&&&&2&&&&&&&&3&&&&&&&&4&&&&&&&&5&&&&&&&&6△╳&&&&&&&&7╳△&&&&&&&&8&&&&&&&&9&&&&&&&&10&&&&&&&&113△&&&&&&&&12△3&&&&&&&&13&&&&&&&&14&&&&&&&&15&&&&&&&&16&&&&&&&&173&&&&&&&&S1S2S3S4&&&&&&&&╳╳╳╳&&&&&&&&3333&&&&&&&&△△△&&&&&&&&4．12一条静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。用这条流水线计算：&&&&6&&&&&&&&F=&&&&&&&&∑(Ai*Bi)&&&&i=1&&&&&&&&画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。&&&&&&&&答：将F改写为F=（A1*B1）+（A2*B2）+（A3*B3）+（A4*B4）+（A5*B5）+（A6*B6）=（C1+C2）+（C3+C4）+（C5+C6）=（D1+D2）+D3=（D4+D3）=F第一次先做6个乘法任务，（1，2，3，4，5，6）第二次做3个加法任务，（7，8，9）第三次再做1个加法任务，（10）第四次再做1个加法任务。（11）&&&&&&&&（1）（2）（3）（4）&&&&&&&&14&&&&&&&&&&&&该运算时空图见下表：（横坐标代表时间，纵坐标代表功能段）12211&&&&&&&&1&&&&&&&&1&&&&&&&&2&&&&&&&&3&&&&&&&&4&&&&&&&&5&&&&&&&&6&&&&&&&&7&&&&&&&&78&&&&&&&&789&&&&&&&&89&&&&&&&&91010&&&&&&&&101111&&&&&&&&11&&&&&&&&吞吐率：TP=11/（22△T）=1/（2△T）加速比：S=（（6*4+5*4）△T）/（22△T）=2效率：E=（（6*4+5*4）△T）/（6*22△T）=2/6=33%4．13下面一段程序在一台超标量处理机上运行，每个时钟周期发射两条指令。所有指令都要经过“取指令”“译码”“执行”和“写结果”四个阶段，其中，、、“取指令”“译码”和“写、结果”三个阶段的延迟时间都为一个时钟周期，在“执行”阶段，访问存储器部件和逻辑操作部件各延迟一个时钟周期，加法操作部件延迟两个时钟周期，乘法操作部件延迟3个时钟周期，4种操作部件各设置一个。加法部件和乘法部件都采用流水线结构，每一级流水线的延迟时间都为一个时钟周期。每个操作部件的输出都有直接数据通路连接到其它操作部件的输入端。k：LOADR0，A；R0←Cache的（A）单元ADDR1，R0；R1←（R1）＋（R0）k+1：k+2：STORER1，B；Cache的B单元←（R1）ADDR2，R3；R2←（R2）+（R3）k+3：k+4：MULR3，R4；R3←（R3）×（R4）k+5：ORR5，R6；R5←（R5）∨（R6）k+6：ADDR5，R7；R5←（R5）＋（R7）（5）列出程序中可能出现的所有数据相关。（6）采用顺序发射顺序完成调度方法，画出流水线的时空图，并计算执行这个程序所用的时间。（7）采用顺序发射乱序完成调度方法，画出流水线的时空图和各操作的完成时间图，并计算执行这个程序所用的时间。（4）如果再增加一个能够存放7条指令的先行窗口，采用乱序发射乱序完成调度方法，画出流水线的时空图、各操作的发射时间图和完成时间图，并计算执行这个程序所用的时间。答：（1）K与K+1：先写后读相关K+1与K+2：先写后读相关K+3与K+4：先读后写相关K+5与K+6：先写后读相关，写写相关（2）采用顺序发射顺序完成调度方法，例如对K+3指令，先执行完了也不能结束，必须等第K+2条指令执行完，才可结束；K+4，K+5均出现这种情况。而K+1、K+2、K+6的等待，是因出现了数据相关。（RR：读寄存器）总执行时间14个时钟周期。流水线时空图如下：&&&&K+6K+5K+4K+3K+2K+1K&&&&&&&&IF&&&&&&&&IFID&&&&&&&&IFIDRR&&&&&&&&IFIDRREX&&&&&&&&IDRREXEX&&&&&&&&IdleEXEXidle&&&&&&&&RRIdleEXidle&&&&&&&&EXIdleIdleWB&&&&&&&&EXIdleWB&&&&&&&&idleWB&&&&&&&&WB&&&&&&&&15&&&&&&&&&&&&IF1&&&&&&&&IFID2&&&&&&&&IFIDEX3&&&&&&&&IDidleEX4&&&&&&&&idleRRWB5&&&&&&&&idleEX6&&&&&&&&idleEX7&&&&&&&&RRWB8&&&&&&&&EX&&&&&&&&WB&&&&&&&&9&&&&&&&&10&&&&&&&&11&&&&&&&&12&&&&&&&&13&&&&&&&&14&&&&&&&&（3）采用顺序发射乱序完成调度方法，K+2、K+4、K+5不必等待，可自行完成，总执行时间减少一个时钟周期（13）。流水线时空图如下：&&&&K+6K+5K+4K+3K+2K+1K&&&&&&&&IF1&&&&&&&&IFID2&&&&&&&&IFIDEX3&&&&&&&&IFIDidleEX4&&&&&&&&IFIDidleRRWB5&&&&&&&&IFIDRRidleEX6&&&&&&&&IFIDRREXidleEX7&&&&&&&&IDRREXEXRRWB8&&&&&&&&IdleEXEXWBEX&&&&&&&&RRWBEXWB&&&&&&&&EXWB&&&&&&&&EX&&&&&&&&WB&&&&&&&&9&&&&&&&&10&&&&&&&&11&&&&&&&&12&&&&&&&&13&&&&&&&&14&&&&&&&&（4）如果再增加一个能够存放7条指令的先行窗口，采用乱序发射乱序完成调度方法总执行时间又减少一个时钟周期（12）。流水线时空图如下：k：LOADR0，A；R0←Cache的（A）单元k+3：ADDR2，R3；R2←（R2）+（R3）k+1：ADDR1，R0；R1←（R1）＋（R0）k+2：STORER1，B；Cache的B单元←（R1）k+5：ORR5，R6；R5←（R5）∨（R6）k+4：MULR3，R4；R3←（R3）×（R4）k+6：ADDR5，R7；R5←（R5）＋（R7）IFIDRREXEXWBK+6IFIDRREXEXEXWBK+4K+5IFIDRREXWBK+2IFIDEXEXWBK+1IFIDRREXEXWBK+3IFIDRREXEXWBKIFIDEXEXWB在CRAY—1机上，设向量长度均为64；所用浮点功能部件的执行时间分别为：相加需6拍，相乘需7拍，求倒数近似值需14拍；从存储器读数需6拍；打入寄存器及启动功能部件各需1拍，问下列各指令组，组内的哪些指令可以连接？哪些指令不可连接？不能连接的原因是什么？并分别计算出各指令组全部完成所需的拍数。（2）V0←存储器(2)V2←V0×V1V1←V2＋V3V3←存储器V4←V2＋V3V4←V5×V6（3）V0←存储器(4)V0←存储器V2←V0×V1V1←1/V0V3←V2+V0V3←V1×V2V5←V3+V4V5←V3+V4&&&&&&&&16&&&&&&&&&&&&&&&&}