计算机系统结构计算题答案.ppt

《计算机系统结构计算题答案.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构计算题答案.ppt（127页珍藏版）》请在装配图网上搜索。

1、计算机系统结构作业题解,作1.2 如有一个经解释实现的计算机，可以按功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释。若执行第一级的一条指令需K(ns)时间，那么执行第2、3、4级的一条指令各需要用多少时间(ns)?,第1章,解：第二级的一条指令需第1级的N条指令解释 第二级的一条指令执行时间为NKns； 第三级的一条指令执行时间为N2Kns； 第四级的一条指令执行时间为N3Kns。,本题有两个问题应特别注意：第一个问题是“上一级”与“下一级”的关系，即哪是上一级，哪是下一级？在图1.1中第3级是第2级的“上一级”，第1级又是第2级的“下一级”。第二个问题是该计算机是一个“经解释

2、实现的计算机”，上一级的程序在下一级上实现不是经翻译完成，只能是解释。,第1级 N3条指令解释,第2级 N2条指令解释,第3级 N条指令解释,第4级 一条指令,上级,下级,作1.3 有一个计算机系统可按功能划分成4级，各级的指令都不相同，每一级的指令都比其下一圾的指令在效能上强M倍，即第i级的一条指令能完成第i-1级的M条指令的计算量。现若需第i级的N条指令解释第i+1级的一条指令，而有一段第1级的程序需要运行Ks，问在第2、3和4级上的一段等效程序各需要运行多长时间(s)?,解：,第2级上的一段等效程序运行时间为：,第3级上的一段等效程序运行时间为：,第4级上的一段等效程序运行时间为：,作1

3、.7 从机器（汇编）语言程序员看，哪些对应用程序员透明？ 指令地址寄存器，指令缓冲器，时标发生器，条件码寄存器，乘法器，主存地址寄存器，磁盘外设，先行进位链，移位器，通用寄存器，中断字寄存器。 答：对机器语言程序员透明，指的是这些器件是机器语言程序员不可修改、不可控制。因此指令缓冲器，时标发生器，乘法器，先行进位链，移位器。,作1.6 什么是透明性概念?对计算机系统结构，下列哪些是透明的?哪些是不透明的? 存贮器的模m交叉存取；浮点数据表示；IO系统是采用通道方式还是外围处理机方式；数据总线宽度；字符行运算指令；阵列运算部件；通道是采用结合型的还是独立型的；PDP一1l系列中的单总线结构；访问

4、方式保护；程序性中断；串行、重叠还是流水控制方式；堆栈指令；存贮嚣最小编址单位；Cache存贮器。,分析：有关系统结构属性所包括的内容，对系统结构都不透明。,对于计算机系统结构透明的是：存储器的模m交叉存取、数据总线宽度、阵列运算部件、通道是采用结合型还是独立型、PDP-11系列的单总线结构、串行、重叠还是流水控制方式、Cache存储器。 对于计算机系统结构不透明的是：浮点数据表示、 I/O系统是采用通道方式还是外围处理机方式、字符型运算指令、访问方式保护、程序性中断、堆栈指令、存储器最小编址单位。,例1.1 假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的

5、40%，则采用加快措施后能使整个系统的性能提高多少？,解：由题意可知 fe=0.4, re=10, 根据Amdahl定律,作1.13 假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90，则采用Cache后，能使整个存储系统获得多高的加速比？,解：fe=0.9 ，re=5,作1.11 某工作站采用时钟频率为15MHz、处理速率为 10MIPS的处理机来执行一个巳知混合程序。假定每次 存储器存取为1周期延迟、试问： (1) 此计算机的有效CPI是多少? (2) 假定将处理机的时钟提高到30MHz，但存储器子 系统速率不变。这样，每次存储器存取需要两个时钟 周期。如果30

6、指令每条只需要一次存储存取，而另 外5每条需要两次存储存取，还假定已知混合程序 的指令数不变，并与原工作站兼容，试求改进后的处 理机性能。,解 (1),(2) 依题意可知：30%的指令需要一次存储存取，则 这些指令在处理器提高时钟频率之后需要增加1个时 钟周期；另外5%的指令需要增加2个时钟周期。,改进后性能提高情况可用CPU时间之比表示：,作1.15 假定利用增加向量模块来提高计算机的运算速度。计算机处理向量的速度比其通常的运算要快20倍，将可用向量处理部分所花费的时间占总时间的百分比称为可向量化百分比。 （1）求出加速比S和向量化百分比之间的关系式。 （2）当要得到加速比为2时的可向量化百

7、分比F为多少？ （3）为了获得在向量模式所得到的最大加速比的一半，可向量化百分比F为多少？,(2) 由（1）式有,解（1）： 由Amdahl定律知,(1),(3) 由题意可知,题1.1 某计算机系统同时采用两种措施改进性能，使得两个功能部件的性能分别提高到原来的re1倍和re2 ，这两个部件在运行时使用的时间比例分别为fe1和fe2 。试分析系统性能提高的总体加速比。,解:,例1.2 用一台4OMHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下： 指令类型 指令条数 时钟周期数 整数运算 45000 1 数据传送 32000 2 浮点运算 15000 2 控制传送 800

8、0 2 求有效CPI、MIPS速率和程序的执行时间。,解：依题意可知 IN=105条，n=4,题1.2 设有两台机器A和B，对条件转移采用不同的方法。CPUA采用比较指令和条件转移指令处理方法，若条件转移指令占总执行指令数的20，比较指令也占20。CPUB采用比较和条件转移指令合一的方法，占执行指令数的20。若规定两台机器执行条件转移指令需2T，其它指令需1T。CPUB的条件转移指令比CPUA慢25，现比较CPUA合和CPUB哪个工作速度更快？,解: CPIA=0.220.811.2 CPUA时间ICACPIATA1.2TAICA ICA是CPUA的指令条数，由于CPUB无比较指令，因此ICB

9、=0.8 ICA，若ICA=100，则ICB=80 ，而CPUB的条件转移指令仍是20条，所以占比例为20/800.2525 CPIB=0.2520.7511.25 又因为CPUB的TB比CPUA的TA慢25%，所以TB=1.25TA CPUB=ICBCPIBTB0.8ICA1.251.25TA 1.25TAICA 可见，CPUA时间CPUB时间，CPUA比CPUB工作速度快。,解：,上例中，TB只比TA 慢10%，则哪个CPU更快些？,TB1.1TA CPUB时间0.8ICA1.251.1TA 1.1TAICA 因此CPUB时间CPUA时间，则CPUB更快些。,题1.3 某向量计算机系统中，

10、标量指令的平均CPI是1，向量运算指令的平均CPI是64，系统加快向量部件的速度后使向量运算速度提高到原来的2倍，某一测试程序执行时的向量运算指令数量占全部指令数的10，问计算机系统运行这个测试程序的整体性能比原来提高多少？,解：,作1.12 假设在一台40MHz处理机上运行200 000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：,(1)计算在单处理机上用上述踪数据运行程序的平均CPI。 (2)根据(1)所得CPI，计算相应的MIPS 速率。,解：依题意可知 IN=2105条，n=4，,第2章,题2.1 一种浮点数有1位符号位，阶

11、码为7位移码，尾数8位与符号位一起采用原码的规格化表示，基数为2，该浮点数可表示的最大数为 ，最大数与最接近它的数据（次最大数）的差值为 ，可表示的最小数为 ，最小数与最接近它的正数（次最小数）的差值为 。,解：,最大数,最小正数,最大数与次大数的差值,最小正数与次小正数的差值,解：阶码为7位移码表示，1位符号位，尾数8位，原码规格化表示，基数为2，其格式为：,尾数基值 rm 2（二进制） 阶码的基值re 2，尾数长度p=8 (不包括符号位），阶码长度q=6(不包括符号位）， 规格化表示的正数的范围：,浮点数N,可表示的最小正浮点数为,可表示的最大正浮点数为,最大尾数为,最大阶码为,最小阶码为

12、,最小尾数为,规格化表示的正数的范围：,可表示的正阶、正尾规格化数的个数为,可表示的最小负浮点数为,可表示的最大负浮点数为,最大尾数为,最大阶码为,最小阶码为,最小尾数（原码）为,规格化表示的负数的范围：,1,0,0,0,0,0,0,1,1,1,0.09,0.15,1,0.06,1,0.03,0.03,0.04,0.05,0.15,0.30,0.40,I7 I6 I5 I4 I3 I2 I1,例2.1 某指令系统各指令使用频度如下： I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03 1.Huffman编码,由此可得到哈夫曼编码如下： I

13、1: 0 I2: 10 I3: 110 I4: 11100 I5: 11101 I6: 11110 I7: 11111 平均码长 L=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5 +0.03*5+0.03*5 = 2.20位 信息冗余量R=(2.20-2.17)/2.20=1.36% 指令长度个数=4,2.扩展哈夫曼编码 I1, I2, I3 用两位: 00, 01, 10 I4, I5, I6, I7 用四位: 1100, 1101, 1110, 1111 L=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4 = 2.30位 信息冗余量=(

14、2.302.20)/2.30=0.0565=5.65%,操作码的扩展（等长扩展）,平均码长： 2. 2 2.3,例2.2 指令系统共有42种指令，前15种使用频率平均为0.05，中间13种使用频率平均为0.015，最后14种使用频率平均为0.004。如何编码？,解：因频率分布有三种，故码长可有三种；,因每段指令数基本相同，故可采用等长扩展(4-8-12位)， 保留特征码的每段指令数相同(15-15-15)方法。结果如图所示；,结果：采用15-15-15扩展方法，最后一种编码用于扩展，每段00001110用于编码，1111用于扩展。,例2.3 指令系统共有74种指令，前4种使用频率平均为0.12

15、，中间15种使用频率平均为0.02，最后55种使用频率平均为0.004。如何编码？,解：同上例方法，码长可有三种；,因每段指令数成比例(1：4)，故可采用等长扩展方法(3-6-9位)扩展，保留标志位方法，结果如图所示；,结果：采用4-16-64扩展方法，编码第一位用于扩展，每段0XX用于编码，1XX用于扩展。,0 xx 4种 1xx 0 xx 16种 1xx 1xx 0 xx 64种,4-16-64平均码长 =0.12*4*3+0.02*15*6+0.004*55*9=5.22；,例2.4 指令系统共有78种指令，前10种使用频率平均为0.049，中间18种使用频率平均为0.02，最后50种使

16、用频率平均为0.003。如何编码？,解：同上例方法，码长可有三种；因每段指令数比例为1：2：5，故不可采用等长扩展，采用不等长编码( 4-6-10位)较能减少平均码长。,第一种采用4位编码中前10种(00001001)； 第二种采用第一种频率编码中的后5种编码(10101110)与扩展的2位共20种编码； 第三种采用第一种频率编码中的最后一种(1111)与扩展的6位共64种编码。,作2.3 设某机阶码6位、尾数48位，阶符和数符不在其内，当尾数分别以2、8、16为基时，在非负阶、正尾数、规格化数情况下，求出其最小阶、最大阶、阶的个数、最小尾数值、最大尾数值、可表示的最小值和最大值及可表示的规格

17、化数的总个数,解：p=6、m=48时，在非负阶、规格化、正尾数情况下，尾基rm=2、8、16时的各个参数的计算结果如下表所示。,作2.15 某模型机有9条指令，其使用频率为： ADD（加）30%SUB（减）24% JOM（按负转移）6% STO（存）7% JMP（转移）7% SHR（右移）2% CIL（循环左移）3% CLA（清加）20% STP（停机）1% 要求有两种指令字长，都按双操作数指令格式编,采用扩展操作码，并限制只能有两种操作码码长。设该机有若干个通用寄存器，主存为16位宽，按字节编址，采用整数边界存贮，任何指令都在一个主存周期中取得，短指令为寄存器寄存器型，长指令为寄存器主存型，

18、主存地址应能变址寻址。,解：(1) Huffman树的形式如图所示。,0.01,0.02,0.03,0,1,0.03,0.06,0,1,0.06,0.12,0,1,0.07,0.07,0.14,0,1,0.26,0,1,0,0.30,0.20,0.24,0.44,0,1,0.56,1,0,0,1,1,由上图可得到的Huffman编码为： ADD(加) 30% 01 SUB(减) 24% 11 CLA(清加) 20% 10 JOM(按负转移) 6% 0001 STO(存) 7% 0011 JMP(转移) 7% 0010 CIL(循环左移) 3% 00001 SHR(右移) 2% 000001 S

19、TP(停机) 1% 000000 因此，操作码的平均码长为：,(2) 采用2-5扩展的操作码编码为： ADD(加) 30% 00 SUB(减) 24% 01 CLA(清加) 20% 10 JOM(按负转移) 6% 11000 STO(存) 7% 11001 JMP(转移) 7% 11010 SHR(右移) 2% 11011 CIL(循环左移) 3% 11100 STP(停机) 1% 11101 因此，操作码的平均码长为：,(3) 该机允许使用的可编址的通用寄存器个数为23=8个 (4) 短指令为寄存器-寄存器型，格式如下：,OP(2位),R1(3位),R2(3位),OP(5位),R1(3位),

20、X(2位),相对位移d(6位),(5) 访主存操作数地址寻址的最大相对位移量为64个字节(-32+31个字节),长指令为寄存器-主存型，格式如下：,例2.5 若某机要求有：三地址指令4条，单地址指令192条，零地址指令16条。设指令字长为12位，每个地址码长3位。问能否以扩展操作码为其编码？,解： 1. 三种指令格式字如下：,OPC,000 xxx xxx xxx 011 xxx xxx xxx 000 000 xxx 111 101 xxx 111 111 110 000 111 111 111 111,三地址4条,一地址192条,零地址16条,3,3,3,3,三地址指令4条,单地址指令19

21、2条,零地址指令16条,2.某机指令字长16位。设有单地址指令和双地址指令两类。若每个地址字段为6位，且双地址指令有X条。问单地址指令最多可有多少条？ 解：二种指令格式字如下：,由于双地址指令有X条，单地址指令最多可有：,作2.16 某处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令三类，并假设每个地址字段的长度为16位。 （1）如果双地址指令有15条，单地址和零地址指令的条数基本相同，问单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。 （2）如果三类指令的比例为1：9：9，问双地址指令、单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。,解：,（1）双

22、地址指令15条，地址码： 00001110 单地址指令26163条，地址码：1111 000000 1111 111110 零地址指令64条，地址码： 1111 111111 000000 1111 111111 111111 （2）双地址指令14条，地址码：00001101 单地址指令2622126条， 1110 000000 1110 111110 零地址指令128条，地址码：1111 111110 000000 1111 111111 111111,作3.2 设一个任务在计算机中的处理时间为50秒，CPU处理时间为30秒，I/O处理时间为20秒。如果将CPU的处理速度提高4倍，则总的处理

23、时间将是多少？,第3章,解：如使CPU的速度增加4倍,则CPU的处理时间为: Tcpu=30/4=7.5s 则总的处理时间为:T=Tcpu+Ti/o=7.5+20=27.5s,题3.1 假设一台计算机的I/O处理占10，当其CPU性能改变，而I/O性能保持不变，系统总体性能会出现什么变化？ （1）如果CPU的性能提高10倍 （2）如果CPU的性能提高100倍,解：假设原来的程序执行时间为1个单位时间。如果CPU的性能提高10倍，则程序的计算（包含I/O处理）时间为 （110）/10+10%=0.19 即整机性能只能提高约5倍，差不多有50的CPU性能浪费在I/O上。 如果CPU的性能提高100

24、倍，则程序的计算时间为 （110）/100+10%=0.109 而整机性能只能提高约10倍，表示有90的性能浪费在I/O上了。,(1)在上表中填出设备相应二次请求传送字节的间隔时间。 (2)当所有设备同时要传送数据时，求其对通道要求的总流量fbyte,例3.1 某字节交叉多路通道连接6台设备，其数据传送速率如下表所示。,(3)让通道以极限流量fmax.byte=fbyte的工作周期工作，通道的工作周期(即TS+TD的时间间隔)是多少？ (4)让通道中所挂设备速率越高的数据传送请求被响应的优先级越高。画出6台设备同时发送请求到下次同时发送请求期间里，通道响应和处理完各设备请求时刻的示意图。哪个设

25、备丢失了信息？提出一种不丢失信息的解决办法。,解：(1),(2) 总容量 (3) 传送周期 TS+TD=1ms/200B=5S,1,2,3,4,5,6,6号设备丢失了一次数据,20us,方法1：增加通道的最大流量，保证连接在通道上的所有设备的数据传送请求能够及时得到通道的响应 方法2：动态改变设备的优先级 方法3：增加一定数量的数据缓冲器，特别是对优先级比较低的设备,例3.2 印字机各占一个子通道，0号打印机、1号打印机和0号光电输入机合用一个子通道。假定数据传送期内高速印字机每隔25us发一个请求，低速打印机每隔150us发一个字节请求，光电输入机每隔800us发一个字节请求，则这5台设备要

26、求通道的实际流量为多少？,字节多路通道,0子通道,2子通道,1子通道,0号高速印字机,1号高速印字机,0号打印机,1号打印机,0号光电输入机,解：5台设备要求通道的数据流量为：,可将该通道设计成0.1MB/s，即所设计的工作周期为：,这样各设备的请求就能及时得到响应和处理，不会丢失信息。,0号印字机,通道工作周期,0us 50us 100us 150us,1号印字机,0号打印机,1号打印机,0号光电机,表示设备提出申请的时刻 表示通道处理完设备申请的时刻 优先级次序：0号印字机、1号印字机、0号打印机、1号打印机、0号光电机,例3.3 设通道在数据传送期中，选择设备需4.9S，传送一个字节数据

27、需0.lS。 （1）其低速设备每隔250S发出一个字节数据传送请求，问最多可接多少台这种设备？ （2）若有AE共5种高速设备，要求字节传送的间隔时间如下表所示，其时间单位为S。若一次通信传送的字节数不少于1024个字节，问哪些设备可挂在此通道上？哪些则不能？,其中，n1024，应使select i maxselect 由此可得出通道工作周期为：T0.1048(us) 所以，只有A、C、D、E可挂在此通道上，B则不行。,解：(1)低速设备应接字节多路通道,n 250/5=50台，所以，n50台，即最多可接50台这种设备,(2)根据题意，此通道为选择通道,作3.2 设一个任务的处理时间为64秒，C

28、PU在这期间始终忙于处理，I/O处理时间为36秒。为提高系统性能，有两种方案：使CPU的速度增加1倍，或者使CPU和I/O的处理速度同时增加1倍。计算这两种情况下的处理时间。 解：如使CPU的速度增加1倍,则CPU的处理时间为: Tcpu=64/2=32 则总的处理时间为:T=Tcpu+Ti/o-Toverlap Toverlap=32+36-32=36 当两者速度同时增加1 倍时:Tcpu=64/2=32 Ti/o=18 则: T=32+18-18=32,作3.10 （1）字节多路通道、数组多路通道、选择通道，它们一般用什么数据宽度来进行通信？ （2）如果通道在数据传送期中选择设备需9.8u

29、s，传送一个字节数据需0.2 us，某低速设备每隔500 us发出一个字节数据传送请求，问至多可接几台这种低速设备？对于如下AF6种高速设备，一次通信传送的字节数不少于1024个字节，问哪些设备可以挂在此通道上？哪些则不能？其中AF设备每发一个字节数据传送请求的时间间隔分别为,解: （1） 字节通道的数据流量为：,（2） 传送周期 TS+TD=3us2us=5S,0号设备,通道工作周期,（3）通道处理完成各设备第一次服务请求的时刻： 0号设备：5us，1号设备：10us ，2号设备：30 us，3号设备：丢失,1号设备,2号设备,3号设备,表示设备提出申请的时刻 表示通道处理完设备申请的时刻

30、优先级次序：0号设备、1号设备、2号设备、3号设备,(4) 从时间关系图中看，这个字节通道不能正常工作，因为以现在的工作频率，不可能连接过多的设备。 （5）改进的措施： 1）增加此通道的工作频率； 2）改变设备的优先级； 3）增加一定数量的缓冲器，保存优先级低设备可能丢失的数据。,例4.1 假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90，则采用Cache后，能使整个存储系统获得多高的加速比？ 解：,第4章,例4.2 假设高速缓存Cache的访问周期为50ns，主存的访问周期为400ns ，且Cache被访问命中的概率为95，则采用Cache后，能使整个存储系统等

31、效的访问周期为多少？获得多高的加速比？ 解：,例4.3 设某用户虚存共有8页, 主存有4页, 每页大小为1KB. 试根据页表计算出虚地址1023和6800的主存实地址。,提示：注意页表中虚、 实页对应关系,页表,每页首地址=页号X每页大小,解：页号与地址对应关系,虚地址1023，虚页号为0，页内位移 为1023；根据虚页号查页表得知实页 号为3，且装入位为1。 主存实地址PA=3072+1023=4095,虚地址6800，虚页号为6，页内位移 为656；根据虚页号查页表得知实页 号为0，且装入位为1。 主存实地址PA=0+656=656,虚页号虚地址1024,例4.4 虚存32页, 主存16页

32、, 每页为1KB。某时刻已调入主存的实页与虚页对应如下: 虚页号 0 1 2 8 实页号 5 10 4 7 求虚地址0A5CH和1A5CH对应的实地址。,0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0,查页表（未装入）,单用户的虚地址,页面失效，无对应的主存实地址。,P,D,直接,1A5CH,解：,用户的虚页并未装入主存中，当执行该虚页程序时，找不到对应的实页。,例4.5 虚拟存储器举例IBM370/168,相等比较位数？ 相等寄存器位数？ 快表行数？ 快表每行的位数？,用户数？ 每个用户虚页数？ 每页大小？,如何减少散列冲突？ 快表为何采用两组？ 相等比较的作用？,224,2

33、12=4K,212=4KB,15位,30位,64行,24+24位,假若一计算机的主存储器按64块组织，块大小 为8个字，高速缓存有8块。试按下述要求画图 回答问题。 （1）画出全相联映像示意图、指定标记字段 和主存地址格式。 （2）画出直接映像示意图、指定标记字段和 主存地址格式。 （3）画出2路组相联映像示意图、指定标记字段 和主存地址格式。,例4.6,解：,（1）全相联映像,标记6位的高速缓存,主存地址,缓存地址,（2）直接映像,标记3位的高速缓存,主存储器,主存地址,缓存地址,B7,B8,B9,B1,B0,B56,B57,B63,区0,区7,3位,3位,3位,3位,3位,（3）2路组相联

34、映像,标记4位的高速缓存,主存储器,主存地址,缓存地址,B3,B4,B5,B2,B1,B0,B60,B61,B63,B62,区0,区15,4位,2位,3位,1位,3位,2位,作4.6 解：,（1）由于虚地址中有2位表示段号、2位表示页号，所 以此地址空间共有2222=16个虚页。,（2）根据上页表，题中所示操作的虚地址访问情况如下,其中，实地址=实页号页大小+页内位移。如下表第1行中， 实地址=32048+1=6145,作4.8 解：,（1）可有1K个任务，短期内只有4个用户， 指示用户号的地址字段U=10位；ID=2位； 又每个用户程序空间可达4096页，每页512B， P=12, D=(9

35、+3)=12位； 又主存地址长度为20位， 实页号p=20-12=8位。,（2）每个相联寄存器的相联比较位数为U=10位； （3）每个相联寄存器的总位数为U+ID=12位； （4）散列变换硬件的输入和输出位数为14位和4位； （5）每个相等比较器的位数为P+ID=12+2=14位； （6）快表的总容量为16(12+2+8)2=704（位）。,用户号U 虚页号P 页内位移D,多用户的虚地址,34位,实页p 页内位移d,主存实地址,20位,8位,12位,12位,12位,10位,散列变换,相等？,相等？,14位,4位,16行,直接,P+ID,P+ID,p,p,U1,U2,U3,U3,00,01,10

36、,11,虚实地址经快表变换的逻辑示意图,作4.12 解：,依题意可知，每块大小为44=16B，用4位二进制表示。 采用4个外相等比较电路，指示块号用2位二进制表示。 指示组号地址为10-2-4=4位。 又因为主存容量为256KB，主存总位数18位。所以， 指示区号的位数为18-10=8位。 地址对应关系如下：,相联目录表如下：,相联目录表行数：2q=24=16行； 每行总位数：E+B+b=8+2+2=12位； 每个相等比较电路的位数：E+B=8+2=10位。,题4.1 在一个Cache存储系统中， Cache的访问周期为10ns，主存储器的访问周期为60ns，每个数据在Cache中平均重复使用

37、4次。当块大小为1个字节时，存储系统的访问效率只有0.5，现在要通过增加块大小，使存储系统的访问效率达到0.94。 （1）当存储系统的访问效率为0.5时，计算命中率和等效访问周期。 （2）为了使存储系统的访问效率达到0.94，命中率和等效访问周期应该提高到多少？ （3）为了使存储系统的访问效率从0.5提高到0.94，块的大小至少增加到几个字？,解:（1）当存储系统的访问效率为0.5时，由表达式,可求出命中率为,等效访问周期为,或由,得,（2）当存储系统的访问效率提高到0.94时，命中率 应该提高到H2,等效访问周期应提高为,或由,得,（3）为了使存储系统的访问效率由0.5提高到0.94， 块大

38、小应为B个字。则有,在上式中代入相关参数，可求出,其中n为Cache的块大小与数据重复使用次数的乘积，H1是原来的命中率，H是块大小增加后的命中率。,题4.2 对于下述访存字节地址序列： 1,14,50,89,20,17,19,56,19,11,14,43,15,16,9,17标出每次访存后的cache存储空间的分配情况和命中情况。假定cache是2路组相联的，采用FIFO替换策略，每块是4个32位的字。Cache的容量是16字，初始cache为空。,主存地址,cache地址,区号 组号 块号 字W,1位,1位,2位,1位,2位,组号 块号 字w,1位,解：,B3,B4,B2,B1,B0,B7

39、,B5,B6,主存储器,组0,组1,区0,区1,3位,B4,B7,B5,B6,区7,时间 t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 字地址流,（2路组相联FIFO）,调进,调进,调进,替换,替换,替换,替换,命中,命中1次,组0,组1,替换,替换,替换,1,1,14,14,50,19,56,89 89 89 89,20*,50*,17,17,19,11,17,56,17,17,19,19,14,50,14,20,14,14*,89*,89,1 14 50 89 20 17 19 56 19 11 14 43 15 16 9 17,替换,17,56*,43

40、,17,16,14*,19,14,11*,19,17,43,17*,15,19,43*,16,15,19,9,16,15,19*,9,15,1 1*,调进,替换,替换,替换,作5.2 设一条指令的执行过程分为“取指令”、“分析”和“执行”三段，每一段的执行时间分别为t、2t和3t。在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。 （1）顺序执行方式。 （2）仅“取指令”和“执行”重叠。 （3） “取指令”、“分析”和“执行”重叠 （4）先行控制方式,第5章,解： （1）顺序执行需要的时间如下： （2）取指令和执行重叠，即一次重叠执行方式，我们假设第n+1条指令的取指令和第n条指令

41、的执行同时结束，那么所需要的时间为： （3）取指令、分析和执行重叠 (4)先行控制方式,1,2,3,4,t t 3t t,例5.1 带有瓶颈部件的4功能段流水线, t1=t2=t4=t, t3=3t,4个任务、10个任务时TP，E、SP 。,（1）分析法: 各段时间不等,S,T,S1,S2,S3,S4,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t12,t13,t14,t15,1,2,3,4,t11,1,2,3,4,1,2,3,4,1,2,3,4,输出,（2）时空图法,例5. 2 以浮点加法运算为例（四段流水线）各段时间相等，求吞吐率、效率。 求Z=A+B+C+D+E+F+G

42、+H，TP、E、Sp (注意有相关),解:,流水线的效率不高，原因在于存在着数据相关,有空闲功能段。,例5.3 ASC计算机多功能算术运算流水线各段时间相等，6次浮点加、 5次定点乘的吞吐率，效率，加速比 m=8，n=11,分析：T加=6+(6-1)*1=11(t) T乘=4+(5-1)*1=8(t),则 TP=11/(11+8)t=11/19t E=(6*6+5*4)t/(19*8t)=36.8% Sp=(6*6+5*4)t/19t=56/19=2.94,1,2,3,4,5,8,6,7,1,2,3,4,5,6,时间,浮加,定点乘,一,二,三,四,五,一,二,三,四,五,一,二,三,四,五,一

43、,二,三,四,五,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19,题5.1 一条线性流水线有4个功能段组成，每个功能段的延迟时间都相等，都为t。开始5个t，每间隔一个t向流水线输入一个任务，然后停顿2个t，如此重复。求流水线的实际吞吐率、加速比和效率。,解答流水线的时空图如下：,我们可以看出，在（11n+1）t的时间内，可以输出5n个结果，如果指令的序列足够长（n），并且指令间不存在相关，那么，吞吐率可以认为满足： 加速比为： 从上面的时空图很容易看出，效率为：,例5.4 用一条5个功能段的浮点加法器流水线计算 每个功能段的延迟时间均相等，流水线

44、的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。 解答首先需要考虑的是，10个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：9次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：,I1：R1A1+A2 I2：R2A3+A4 I3：R3A5+A6 I4

45、：R4A7+A8 I5：R5A9+A10 I6：R6R1+R2 I7：R7R3+R4 I8：R8R5+R6 I9：FR7+R8 这并不是唯一可能的计算方法。假设功能段的延迟为t。时空图如下，图中的数字是指令号。,3,2,1,4,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,7,7,7,7,7,8,8,8,8,8,9,9,9,9,9,21t,部件m,1,5,4,3,2,R1=A1+A2,R2=A3+A4,R3=A5+A6,R4=A7+A8,R5=A9+A10,R6=R1+R2,R7=R3+R4,R8=R5+R6,F=R7+R8,R1,R3

46、,R5,R6,R7,R8,F,R2,R4,整个计算过程需要21t，所以吞吐率为： 加速比为： 效率为：,作5.5 流水线由4个功能部件组成，每个功能部件的延迟时间为t。当输入10个数据后，间歇5t ，又输入10个数据，如此周期性地工作，求此时流水线的吞吐率，并画出其时空图。,分析 所谓输入10个数据后，间歇5t，又输入10个数据的含义应当是以输入时间为基准，即从第10个数据输入时算起，隔5t后又开始输入新的一轮数据。,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,1

47、,时间(t),部件,5t,解答按题意可得4个功能部件流水时的时空关系如下图所示,所以，按周期性工作时的流水线平均吞吐率为 Tp=10/(14t)=5/(7t),0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,4 3 2 1,作5.6 有一个浮点乘流水线如下图(a)所示，其乘积可直接返回输入端或暂存于相应缓冲寄存器中，画出实现A*B*C*D的时空图以及输入端的变化，并求出该流水线的吞吐率和效率；当流水线改为下图(b)形式实现同一计算时，求该流水线的效率及吞吐率。,阶加,尾乘,规格化,t,3t,t,积,操作数,图(a),阶加,尾乘1,尾乘2,尾乘3,规格化,积,t

48、,3t,t,3t,3t,图(b),分析为了减少运算过程中的操作数相关，A*B*C*D应改为采用(A*B)*(C*D) 的算法步骤进行运算。 解按图(a)组织，实现A*B*C*D的时空关系如下图(A)所示。,时间,部件,输入,输出,A B,C D,A*B,C*D,A*B C*D,A*B*C*D,13,规格化 尾乘 阶加,图(A),吞吐率TP=3/(13t) 效率E=(35t)/(313t)=5/13=38.5%,时间,部件,输入,输出,A B,C D,A*B,C*D,A*B C*D,A*B*C*D,规格化 尾乘3 尾乘2 尾乘1 阶加,图(B),11,流水线按图(b)组织时，实现A*B*C*D的

49、时空关系如图(B) 吞吐率TP=3/(11t) 效率E =(35t)/(511t)=3/11=27.3%,例5.5 (类似题5.8) 一条线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输入端与输出端之间有直接数据通路，而且设置有足够的缓冲寄存器。现在用这条流水线计算： 画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。,解：为了取得较高的速度，我们需要一次将乘法作完，设源操作数存放在寄存器A、B中，中间结果存放在寄存器R中，最后结果存放在寄存器F中，则执行的指令序列如下所示： I

50、1：R1A1*B1 I2：R2A2*B2 I3：R3A3*B3 I4：R4A4*B4 I5：R5A5*B5 I6：R6A6*B6 I7：R7R1+R2 I8：R8R3+R4 I9：R9R5+R6 I10：R10R7+R8 I11：FR9+R10,这并不是唯一可能的计算方法。假设功能段的延迟为t。时空图（不完全）如下，图中的数字是指令号。,1,2,22t,部件m,1,5,4,3,2,R1=A1*B1,R2=A2*B2,R3=A3*B3,R4=A4*B4,R5=A5*B5,R6=A6*B6,R7=R1+R2,R8=R3+R4,F=R9+R10,R1,R10,R6,R7,R8,F,6,1,1,1,3

51、,3,2,2,2,3,4,3,4,4,4,5,6,5,5,5,6,6,6,7,8,7,7,7,8,8,8,9,R9=R5+R6,R10=R7+R8,9,9,9,10,10,11,10,10,11,11,11,乘法,加法,作5.4 在一台单流水线多操作部件的处理机上执行下面的程序，取指令、指令译码各需要1个时钟周期，MOVE,ADDT和MUL操作各需要2个、3个和4个时钟周期。每个操作都在第一个时钟周期从寄存器中读取操作数，在最后1个时钟周期把运算结果写到通用寄存器中。,K： MOVE R1,R0 ; R1R0,K+2：ADD R0,R2 , R3 ; R0 (R2) +( R3),K+1：MU

52、L R0 , R2 ,R1 ; R0 (R1)( R2),（1）就程序本身而言，可能有哪几种相关？ （2）在程序实际执行过程中，有哪几种相关会引起流水线的停顿? （3）画出指令执行过程的流水线时空图，并计算机执行晚这3条指令共使用了多少个时钟周期？,K、K+1 存在写读相关，读写相关； K+1、K+2存在写写相关。,K： MOVE R1,R0 ; R1R0,K+2：ADD R0,R2 , R3 ; R0 (R2) +( R3),K+1：MUL R0 , R2 ,R1 ; R0 (R1)( R2),解（1）,（2）K、K+1 的写读相关，会引起流水线的停顿； K+1、K+2的写写相关会引起流水线

53、的停顿。,IF1,ID1,RR1,EXE1,IF2,MD1,RR2,ID2,MD2,MD3,IF3,ID3,WR3,RR3,FA1,I1,I2,I3,时钟周期,1 2 3 4 5 6 7 8 9 10,（3）,WAW,WAW,(RAW),(RAW),WAW,共使用11个时钟周期,K： MOVE R1,R0 ; R1R0,K+2：ADD R0,R2 , R3 ; R0 (R2) +( R3),K+1：MUL R0 , R2 ,R1 ; R0 (R1)( R2),WR1,WR2,FA2,作5.13 一台非流水处理机A的工作时钟频率为25MHz，它的平均CPI为4。处理器B是A的改进型，它有1条5段

54、的线性指令流水线。由于锁定电路延迟及时钟扭斜效应，它的工作时钟频率仅为20MHz,问： （1）若在A和B两个处理器上执行100条指令的程序，则处理器B对A的加速比是多少？ （2）在执行上述程时，计算A，B处理器各自的MIPS速率是多少？,解: 已知：MIPSB=20,题5.2 某超标量流水线计算机每个时钟发射两条指令，其4级指令流水线中包含IF、ID、EXE、WB流水级，各个流水段都是花费一个时钟周期。ALU指令在EXE流水段完成算术运算，乘除指令比ALU指令多花费2个时钟周期，访存指令在EXE功能段完成访存操作。流水中无相关专用通路。指出下列指令序列中的数据相关性，分别画出指令流水线在有序执

55、行有序写回、无序执行无序写回情况下的时空图。,1：LOAD R0 , A ; R0主存(A)单元,2：ADD R1 , R0 ; R1 (R1) +( R0),3: LOAD R2 , B ; R2主存(B)单元,4：MUL R3 , R4 ; R3 (R3) +( R4),5：AND R4 , R5 ; R4 (R4) ( R5),6：ADD R2 , R5 ; R2 (R2) +( R5),解（1）相关性分析:1、2 存在写读相关；4、5存在读写相关；3、6存在写读相关；3、6存在写写相关。,IF1,ID1,EXE1,WR1,IF2,顺序,WR2,EXE2,ID2,顺序,(RAW),顺序,

56、顺序,顺序,EXE1,MD2,WR1,IF2,ID2,EXE2,ID1,IF1,WR2,ID1,EXE1,IF1,WR1,ID2,MD1,MD2,MD3,I1,WR2,IF2,I2,I3,I4,I5,I6,时钟周期,1 2 3 4 5 6 7 8 9 10,（2）相关性分析: 按序发射按序完成之调度,1：LOAD R0 , A ; R0主存(A)单元 (1,2RAW),2：ADD R1 , R0 ; R1 (R1) +( R0),3: LOAD R2 , B ; R2主存(B)单元 (3,6RAW,WW),4：MUL R3 , R4 ; R3 (R3)( R4) (4,5WAR),5：AND

57、R4 , R5 ; R4 (R4) ( R5),6：ADD R2 , R5 ; R2 (R2) +( R5),顺序,顺序,顺序,顺序,(RAW),(RAW),(RAW),(RAW),(RAW),(RAW),(RAW),主共使用11个时钟周期,IF1,ID1,EXE1,WR1,IF2,WR2,EXE2,ID2,RAM,EXE2,MD2,MD1,WR1,IF2,ID2,EXE2,ID1,IF1,WR2,ID1,EXE1,IF1,WR1,ID2,I1,WR2,IF2,I3,I4,I5,I2,I6,时钟周期,1 2 3 4 5 6 7 8 9 10,（3）相关性分析: 无序发射无序完成之调度,1：LO

58、AD R0 , A ; R0主存(A)单元 (1,2RAW),2：ADD R1 , R0 ; R1 (R1) +( R0),3: LOAD R2 , B ; R2主存(B)单元 (3,6RAW),WW,4：MUL R3 , R4 ; R3 (R3) ( R4) (4,5WAR),5：AND R4 , R5 ; R4 (R4) ( R5),6：ADD R2 , R5 ; R2 (R2) +( R5),(RAW),MD3,主共使用7个时钟周期,IF1,ID1,EXE1,WR1,IF2,WR2,EXE2,ID2,EXE2,MD2,MD1,WR1,IF2,ID2,EXE2,ID1,IF1,WR2,ID

59、1,EXE1,IF1,WR1,ID2,I1,WR2,IF2,I3,I4,I5,I2,I6,时钟周期,1 2 3 4 5 6 7 8 9 10,（4）相关性分析: 无序发射无序完成之调度（设置专用数据通路）,1：LOAD R0 , A ; R0主存(A)单元 (1,2RAW),2：ADD R1 , R0 ; R1 (R1) +( R0),3: LOAD R2 , B ; R2主存(B)单元 (3,6RAW),WW,4：MUL R3 , R4 ; R3 (R3) ( R4) (4,5WAR),5：AND R4 , R5 ; R4 (R4) ( R5),6：ADD R2 , R5 ; R2 (R2)

60、 +( R5),MD3,主共使用7个时钟周期,作5.17 在CRAY-1机上，设向量长度均为64，所有浮点功能部件的执行时间分别为：相加需6拍，相加需7拍，求倒数近似值需14拍，从存储器读数据需6拍，打入寄存器机启动功能部件各需1拍，问下列个指令组，组内的哪些指令可以链接？，哪些指令不可以链接？不能链接的原因是什么？并分别计算各指令组全部完成所需的拍数。,（1） V0 存储器 （2） V2 V0 V1,V1 V2 V3 V3 存储器,V4 V5V6 V4 V2 V3,（3） V0 存储器 （4） V2 存储器,V2 V0 V1 V1 1/V0,V3 V2 V0 V3 V1 V2,V5 V3 V

61、4 V5 V3 V4,解： 组（1）三条指令可并行执行。 T=1+7+1+64-1=72(拍)。 组（2）前二条指令可并行执行，前两条与第三条指令可链接执行。 T=（1+7+1+1+6+1）+63=80（拍）。 组（3） 前3条指令可链接执行，后一条指令只能串行（加法部件冲突） T=（8+9+8+63）+8+63=159（拍）。 组（4）前二条指令可并行执行，后两条可链接，这样前两条与后两条指令可链接执行。 T=（14）+（9）+(8)+63=94（拍）。,题5.3 对于以下计算表达式: I=A+B+C+DEF+G+H 其中A,B,I 都是寄存器名。 （1）指出其中的并行性，即哪些操作可以并行

62、执行； （2）对于采用5级指令流水线的计算机，试安排完成表达式计算的操作顺序，并写出指令序列，使得流水线的停顿时间最少； （3）对于一台VLIW计算机，假定其有2个加法部件和一个乘法部件，都能在一个流水周期中完成计算，试将上述表达式用最少的超长指令序列表示。,解（1） I=A+B+C+DEF+G+H 可并行操作的运算为： A+B+C+G+H DEF （3） A+B，G+H， DE A+B+C，DEF A+B+C+G+H A+B+C+G+H + DEF,IF2,ID,EXE1,WR,MEM,WR,EXE,ID,MD1,MD2,IF3,ID,IF6,（2）,2: R1E,6: R0D *E,WR,

63、MEM,MD3,MEM,3: R2G,IF8,ID,EXE4,WR,MEM,WR,EXE,ID,EXE,IF9,ID,IF18,10: R7C,9: R3 A+B,WR,MEM,MEM,8: R6F,IF1,ID,EXE,WR,MEM,1: R0D,IF5,ID,EXE1,WR,MEM,WR,EXE,ID,IF7,5: R4B,MEM,7: R5H,IF4,ID,EXE,WR,MEM,4: R3A,EXE,ID,IF10,WR,MEM,EXE,ID,IF14,WR,MEM,12: R5D*E*F,MD1,MD2,ID,IF12,WR,MD3,MEM,11: R3G+H,EXE,ID,IF11,WR,MEM,14: R3A+B+C,18: R3A+B+C+R5,共用21个时钟周期，有4个 时钟周期的停顿,作6.1 画出16台处理器仿ILLIAC 的模式进行互连的互连结构图，列出PE0分别只经一步、二步和三步传送能将信息传送到的各个处理器号。 解：16