系统结构答案(1)复习过程

学习学习--——好资料更多精品文档更多精品文档T解：根据T解：根据Amdahl定理有：Sn=Tn主存的5倍，相当于改进存储器后获得的加速比为1.26假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90%,那么，采用Cache后能使整个存储系统获得多高的加速比 ？1 ;结合题意：Cache工作速度为11-Fe)+Fe/Se5,即Se=5;Cache被访问命中的概率为90%,相当于访问存储器的时间有90%化在Cache±,即Fe=0.9。所以Sn=1/[(1-0.9)+0.9/5]=3.57设计指令存储器有两种不同方案： 一种是采用价格较贵的高速存储器芯片， 另一种是采用价格便宜的低速存储器芯片。采用后一方案时，用同样的经费可使存储器总线带宽加倍，从而每隔 2个时钟周期可取出2条指令(每条指令为单字长32位)。而采用前一方案时，每一个时钟周期取出一条单字长指令。由于访存局部性原理，当取出 2个指令字时，通常这2个指令字都要使用，但仍有 25%的时钟周期中，取出的2个指令字中仅有1个指令字是有用的。试问采用这两种实现方案所构成的存储器带宽是多少？解：带宽是指单位时间内处理的二进制位数 ，相当于频率，用f表示。采用方案A时，存取指令的CPIa=1时钟周期/指令字，即：fa=1/CPIaX指令字长=1X32=32位/时钟周期。采用方案B时，存取指令的CPIb=0.75X2/2+0.25X2/1=1.25 时钟周期/指令字，即：f a=1/CPIaX指令字长=0.8X32=25.6位/时钟周期。某工作站采用时钟频率为 15MHz处理速率为10MIPS的处理机来执行一个测试程序。假定每次存储器存取为1个时钟周期，试问：(1)此计算机的有效CPI是多少？(2)假定将处理机的时钟频率提高到 30MHz但存储器的工作速率不变，这样，每次存储器存取需要 2个时钟周期。如果30%指令每条只需要一次存储器存取操作， 另外5%指令每条需要二次存储器存取操作，假定测试程序的指令数不变，并与原工作站兼容，试求改进后的处理机 CPI和MIPS解：(1)由MIPS=时钟频率/(CPIX106),则有：CPIa=时钟频率/(MIPSX106)=1.5。(2)当时钟频率为15MHz时，假设不进行存储操作指令的 CPI为x,则要进行一次存储操作指令的CPI为1+x,要进行二次存储操作指令的 CPI为2+x,因此有：.5=xX65%+(1+x)X30%+(2+x)X5%解得x=1.1当时钟频率为30MHz寸，不进行存储操作指令的 CPI不变为1.1,要进行一次存储操作指令的 CPI为2+x=3.1，要进行二次存储操作指令的 CPI为4+x=5.1，因此平均CPI为：CPI b=1.1X65%+3.1X30%+5.1X5%=1.9所以 MIPS b=时钟频率/(CPIbX106)=(30X106)/(1.9X106)=15.8MIPS某计算机Cache能存放2000条指令。假设10%勺指令承担了90%寸间的指令访问，而且这10%指令中每条指令的执行时间相同。如果要执行的某程序共50000条指令，当计算机执行该程序时，在Cache中能访问到的指令的概率是多少？解：由题意可知：45000条指令承担10%寸间的指令访问，5000条指令承担90%寸间的指令访问。显然5000条指令被频繁使用，设平均使用次数为 X;另外45000条指令仅使用一次。则有：45000:0.1=5000X:0.9 解得X=81所以该程序执行指令的条数为 Y=45000+5000X81=450000假设频繁使用的5000条指令均匀分布于程序之中，即每次调入Cache的2000条指令有200条是频繁使用的。另假设每次调入Cache的2000条指令中的1800条均被使用了一次。所以执行该程序时 Cache中能访问到的指令的概率为：(450000-50000/2000)+450000〜100%有一台计算机，不同类型指令在理想 Cache(无访问失败)与实际Cache(有访问失败)两种情况下的性能如下表。求理想 Cache相对于实际Cache的加速比？指令类型出现频率理想CacheCPI实际CacheCPI运算指令40%13取数指令120%28存数指令115%28控制指令125%24解：理想Cache情况下指令的平均时钟周期数 CPI为：nCPI理想=£(CPii*Ii/Ic)=1X40%+2X20%+2X15%+2X25%=1.6i1实际Cache情况下指令的平均时钟周期数 CPI为：nCPI实际=z(CPIi*Ii/Ic)=3X40%+8X20%+涿15%+*25%=5.0i1S二实际CacheCPUM行时间/理想CacheCPUM行时间二(ICX时钟周期xCPI实际)/(ICX时钟周期xCPI理想)=CPI/CPIa=5.0/1.6=3.12假设在一台40MHz处理机上运行测试程序共有 200000条指令，由4类指令组成。已知指令的CPI和所各占比例如下表。指令类型指令比例CPI算逻运算Cache命中存取控制指令Cache末命中访主仔60% 118% 212% 410% 8(1)计算处理机运行该程序的平均 CPI。(2)根据(1)所得CPI,计算相应的MIPS速率。n解：(1)CPI=Z(CPIi*Ii/Ic)=1X60%+2X18%+4X12%+8X10%=2.2i1MIPS=时钟频率/(CPIX106)=40X106/(2.2X106)=18.19已知4个程序在AB、C三台计算机上的执行时间(秒)分别如下表，假设每个程序都有100X106条指令要执行，计算这3台计算机对每个程序的MIPS速率。根据这些速率值，你能否得出这 3台计算机相对性能的明确结论？你能否找到一种将它们排序的方法？试说明理由。

程序计隼刑A计算机B计算机C程序11020程序2 •00010020程序3 1)00100050程序4 ,00800100程序1 100 105程序2 ().1 15程序3 ().2 0.12程序4 ,0.1251(2)由于MIPS与指令值、指，令使用的频率等后关，在同程序 计算机A计算机B计算机C率MIPS,程序1 100 105程序2 ().1 15程序3 ().2 0.12程序4 ,0.1251(2)由于MIPS与指令值、指，令使用的频率等后关，在同程序 计算机A计算机B计算机C率MIPS,因此不能仅用MIPS来评价计算机性能的优劣。而应用执行程序的算术平均台机器上运行不同的程序，得出不同的速Tcpu来评价比较好。所以性能排序为:epuA=epuB=TepuC=(1+1000+500+100)/4=400.25(10+100+1000+800)/4=477.5(20+20+50+100)/4=47.5根据上表中列出的Tcpu则可计算出相应的MIPS如下表所示。浮点数系统使用的阶码基值 re=2,阶值位数q=2,尾数基值rm=10,尾数位数p'=1,即按照使用的二进制位数来说，等价于 p=4o计算在非负阶、正尾数、规格化情况下的最小尾数值、最大尾数值、最大阶值、可表示的最小值和最大值及可表示数的个数。解：最小尾数值：rm1=10-1=0.1最大尾数值：1-rmp'=1-10-1=0.9最大阶值：2q-1=3可表示数的最小值：1xrm1=10-1=0.1可表示数的最大值： —q-1x(1-rmpj=103(1-10-1)=900可表示数的个数： 2qxrmp，(rm-1)/rm=22X101(10-1)/10=36一个处理机有I1〜I10共10条指令，经统计，各指令在程序中出现的概率如下：I1:0.25I2:0.20I3:0.15I4:0.10I5:0.08I6:0.08I7:0.05I8:0.04I9:0.03 I10 :0.02(1)计算这10条指令的操作码最短平均长度。(2)写出这10条指令的Huffman编码，并计算操作码编码的平均长度和信息冗余量。(3)采用3/7扩展编码法和2/8扩展编码法编写这10条指令的操作码。并分别计算编码的平均长度和信息冗余量。说明哪一种扩展编码较好的理由。

n解：(1)二.操作码编码的最短平均长度为： H=-£piXlogzpii4H=—(0.25log20.25+0.20log20.20+0.15log20.15+0.10log20.10+0.08log20.08+0.08log20.08+0.05log20.05+0.04log20.04+0.03log20.03+0.02log20.02)=2.96 (位)1I9I8I7(2)根据给出的使用频度，在构造Huffman树的过程中，有两个结点可供合并，因此可生成不同的Huffman树，其中给出一棵如图所示，相应的Huffman编码如表所示。1I9I8I7I10IiPiHuffman编码Li2-5编码(3/7)Li2-4编码(2/8)LiI10.25002002002I20.20102012012I30.15010310210004I40.10110311000510014I50.080110411001510104I60.081110411010510114I70.0501110511011511004I80.0401111511100510014I90.0311110511101511104I100.0211111511110511114nHuffman编码的平均长度为：l=Xpixli1l=0.25X2+0.20X2+0.15X3+0.10X3+0.08X4+0.08X4+0.05X5+0.04X5+0.03X5+0.02X5=2.99 (位)Huffman 编码的信息冗余量为： R=1-H/l= (1—2.96/2.99)X100%=1.0%3/7扩展编码和2/8扩展编码如表所示。3/7扩展编码要求短码码点数为 3,长码码点数为7。所以短码长取2位，有码点22=4个，用一个作扩展标志；长码长取 3位，有码点23=8个，有一个未被利用，即有一个 余码点。编码的平均长度为：学习学习--——好资料更多精品文档更多精品文档学习学习--——好资料l=(0.25 +0.20+0.15)X2+(0.10+0.08+0.08+0.05+0.04+0.03+0.02)X5=3.2 (位)3/7扩展编码的信息冗余量为： R=1—H/l=(1—2.96/3.2 )X100%=7.5%2/8扩展编码要求短码码点数为 2,长码码点数为8。所以短码长取2位，有码点22=4个，用二个作扩展标志；长码长取 2位，有码点22X2=8个，码点全部被利用，即没有多余码点。l=(0.25 +0.20)X2+(0.15+0.10+0.08+0.08+0.05+0.04+0.03+0.02)X4=3.1 (位)2/8扩展编码的信息冗余量为： R=1—H/l=(1—2.96/3.1 )X100%=4.5%可见，2/8扩展编码优于3/7扩展编码。7经统计，某种处理机 14条指令的使用频度分别为：0.01,0.15,0.12,0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14 ,0.11,0.03。分另给出它们的定长码、Huffman编码、只能有两种码长且平均长度尽可能短的扩展编码， 并分别计算三种编码的平均长度。0.150.150.140.130.120.110.040.040.030.030.020.020.010.012.28用于文字处理的某专用机,在对传送的文字符和空格进行统计后，i0.20 0:0.172.28用于文字处理的某专用机,在对传送的文字符和空格进行统计后，i0.20 0:0.175:0.05 6:0.08每个文字符用 4位十进制数字(得出它们的使用频度如下：1:0.06 2:0.08 3:0.11 4:0.087:0.13 8:0.03 9:0.010〜9)编码表不，空格用J表不。(1)若对数字0〜9和空格采用二进制编码，试设计编码平均长度最短的编码。(2)若传送106个文字符号，且每个文字符号后均自动跟一个空格，按最短的编码，共需传送多少个二进制位？若传送波特率为 9600bPS,共需传送多少时间？2)。(3)若对数字0〜9和空格采用42)。解：(1);操作码编码的平均长度最短为 Huffman编码，生成的Huffman树，如图所示，相应的Huffman编码如表所示。l=编码如表所示。l=£PiXli=3.23 (位)。i1(2)根据题意，每个字符的二进制码的平均长度为:3.23X(4+1)=16.15(位)。若要传输106个字符，则要传输二进制位数为： 106X16.15=1.615X107(位)106X4(4+1)=2X107(位)，传输时间若波特率为56Kb/s,则传输时间为：1.615X107/(56X10106X4(4+1)=2X107(位)，传输时间(3)当采用四位定长编码时，则需要传输二进制位数为:为：2X107/(56X103)=357(s)。1.000.400.600.200.200.270.330.11更多精品文档0.040.030.14片0.060.13为：2X107/(56X103)=357(s)。1.000.400.600.200.200.270.330.11更多精品文档0.040.030.14片0.060.130.160.170.080.080.081 6 4 2ITPi20Huffman编码Li00.17000370.13010330.11110320.080010440.080011460.080110410.060111450.051110480.0311110590.011111152.29—台模型机共有 7条指令，各指令的使用频度分别为： 35% 25% 20% 10% 5% 3% 2%有8个通用数据寄存器，2个变址寄存器。(1)要求操作码的平均长度最短，请设计操作码的编码，并计算操作码编码的平均长度。(2)设计8位字长的寄存器一一寄存器型指令 3条，16位字长的寄存器一存储器型变址寻址方式指令4条，变址范围不小于正、负127。请设计指令格式，并给出指令各字段的长度和操作码的编码。2.30 一台模型机共有 7条指令，各指令的使用频度分别为： 35% 25% 20% 10% 5%3%, 2%有8个通用数据寄存器，2个变址寄存器。(1)要求操作码的平均长度最短，请设计操作码的编码，并计算操作码编码的平均长度。(2)设计8位字长的寄存器一寄存器型指令 3条，16位字长的寄存器一存储器型变址寻址方式指令4条，变址范围不小于正、负 127。请设计指令格式，并给出指令各字段的长度和操作码的编码。解：(1);操作码编码的平均长度最短为 Hufman编码，生成的Huffman树如图所示，相应的Huffman编码如表所示。i1n编码如表所示。i1nl=" PiIiPiHuffman编码Li2-4编码（3/4）LiI10.35002002I20.25012012I30.20102102I40.10110311004I50.051110411014I60.0311110511104I70.0211111511114（2）由于通用寄存器有8个，则指令中通用寄存器字段应为 3位；操作码字段2位可有4个码点,用三个码点表示三条指令，另一个码点则作为扩展标志。所以 3条8位长的寄存器一寄存器型指令格式如下：操作码（2位）寄存器1（3位）寄存器2（3位）由于变址寄存器有2个，则指令中变址寄存器字段应为 1位；变址范围-127〜+127,则指令中相对位移字段应为8位；操作码字段前2位可有4个码点，用三个码点表示三条指令，另一个码点则作为扩展标志。扩展2位正好可表示四条指令，操作码字段则为 4位。所以4条16位长的寄存器一存储器型指令格式如下：操作码（4位）寄存器（3位）版址寄存器（1位）相对位移（8位）特别地，当采用3/4扩展编码时，使用频度高的用短码表示，使用频度低的用长码表示，其相应的编码如表所示。2.31某处理机的指令字长为16位，有二地址指令、一地址指令和零地址指令 3类，每个地址字段的长度土匀为6位。（1）如果二地址指令有15条，一地址指令和零地址指令的条数基本相等。问一地址指令和零地址指令各有多少条？并为这3类指令分配操作码。（2）如果指令系统要求这3类指令条数的比例大致为1:9:9,问这3类指令各有多少条？并为这 3类指令分配操作码。解：（1）操作码字段取4位可有24=16个码点，用15个码点（0000〜1110）表示15条二地址指令，另一个码点（1111）则作为扩展标志。所以15条二地址指令格式如下：操作码（4位）地址码1（6位）：地址码2（6位）由于要求一地址指令和零地址指令的条数基本相等。所以地址码 1字段6位扩展有26=64个码点，用63个码点（1111000000〜1111111110）表示63条一地址指令，另一个码点（1111111111）则作为扩展标志。而用地址码2字段6位扩展有26=64个码点，64个码点都用来表示零地址指令，共有 64条。（2）在一中指令条数的比例大约 1:4.2:4.2,因此若使一地址指令和零地址指令加大一倍，则三类指令条数的比例大约1：9:9。

操作码字段取4位时的16个码点，用14个码点（0000〜1101）表示14条二地址指令，另二个码点（1110与1111）则作为扩展标志。扩展标志（1110）扩展地址码1字段6位的64个码点（1110000000—1110111111）全部用来表示一地址指令，有64条。扩展标志（1111）扩展地址码1字段6位的64个码点，用62个码点（11110000001111111101）表示62条一地址指令，另二个码点（1111111110与1111111111）则作为扩展标志。这样一地址指令，共有126条。扩展标志（1111111110与1111111111）扩展地址码2字段6位，各有64个码点全部用来表示零地址指令，则有128条零地址指令。2.32某模型机9条指令使用频度为：ADD（加）30%SUB （减）24%JOM （按负转移）6% STO （存）7%JMP（转移）7%SHR （右移）2%CIL （循环左移）3% CLA （清除）20% STP（停机）1%要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设该机有若干通用寄存器，主存为16位宽，按字节编址，采用按整数边界存储，任何指令都在一个主存周期中取得，短指令为寄存器--寄存器型，长指令为寄存器--主存型，主存地址应能变址寻址。（1）仅根据使用频度，不考虑其它要求，设计出全 Huffman操作码，计算其平均码长；（2）考虑题目全部要求，设计优化实用的操作码形式，并计算其操作码的平均码长；（3）该机允许使用多少可编址的通用寄存器？（4）画出该机两种指令字格式，标出各字段之位数；（5）指出访存操作数地址寻址的最大相对位移量为多少个字节？解：（1）根据给出的使用频度，在构造 Huffman树的过程中，有两个结点可供合并，因此可生成不同的Huffman树，其中给出一棵如图所示，相应的 Huffman编码如表所示。Huffman编码的平均长度为:Huffman编码的平均长度为:nl=£pixlii=1l=0.3X2+0.24X2+0.2X2+0.07X4+0.07X4+0.06X4+0.03X5+0.02X6+0.01X6=2.61（位）STPSHR指令STPSHR指令IiPiHuffman编码Li2-5编码(3/6)LiADDI10.30012002SUBI20.24112012CLAI30.20102102STOI40.0700114110015JMPI50.0700104110105JOMI60.0600014110115CILI70.03000015111005SHRI80.020000016111015STPI90.010000006111105（2）任何指令都在一个主存周期中取得，那么短指令字长为 8位，长指令字长为16位。又指令都是二地址指令，所以短指令寄存器--寄存器型的格式为：操作码（2位）寄存器1（3位）寄存器2（3位）长指令为寄存器--主存型的格式为:操作码（5位）寄存器（3位）声址寄存器（3位）相对位移（5位）由题意可知：指令操作码采用扩展编码，且只能有两种码长。从指令使用频度来看， ADDSU*口CLA三条指令的使用频度与其它指令的使用频度相差较大，所以用两位操作码的三个码点来表示三条指令，一个码点作为扩展码点，且扩展三位来表示六条指令，即采用2--4扩展编码构成3/6编码，2--4扩展编码如表所示。n2--4扩展编码（3/6）的平均长度为：l=£piXli=2.78=1（4）由短指令寄存器―寄存器型的格式可知，寄存器号字段长度为 3位，寄存器个数为8个。则各字段长度如图格式所标识。而对于长指令寄存器--主存型，一般变址寄存器是某通用寄存器， 则变址寄存器号的字段长度为 3位,则各字段长度如图格式所标识。（5）由于相对位移字段长度为 5位，因此访存地址寻址的最大相对位移量为 25=32字节。弟早弟早在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译码需要一个时钟周期，MOVEADMMULB作分另需要2个、3个和4个时钟周期，每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k:MOVER1,R0;R1—(R0)k+1:MULR0,R2,R1;Rk(R2)X(R1)k+2：ADDR0，R2,R3;Rk(R2)+(R3)（1）就程序本身而言，可能有哪几种数据相关 ？（2）在程序实际执行过程中，哪几种数据相关会引起流水线停顿

（3）画出指令执行过程的流水线时空图，并计算完成这解：（1）就程序本身而言，可能有三种数据相关。若3条指令共需要多少个时钟周期?3条指令顺序流动，则k指令对R1寄存器的写33条指令共需要多少个时钟周期?3条指令顺序流动，则k指令对R1寄存器的写3条指令异步流动，则k指令对R0寄存器的读与k+1指令对R0寄存器的写形成的“先读后写”相关,k+2指令对R0寄存器的写与k+1指令对R0寄存器的写形成的“写一写”相关。（2）在程序实际执行过程中，二种数据相关会引起流水线停顿。一是“先写后读”相关， k指令对R1的写在程序执行开始后的第四个时钟； k+1指令对R1的读对指令本身是第三个时钟，但 k+1指令比k指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟要读 R1。不能在同一时钟周期内读写同一寄存器，因此k+1指令应推迟一个时钟进入流水线，产生了流水线停顿。二是“写一写”相关， k+1指令对R0的写对指令本身是第六个时钟，而要求该指令进入流水线应在程序执行开始后的第三个时钟，所以对R0的写是在程序执行开始后的第八个时钟。 k+2指令对R0的写对指令本身是第五个时钟，而 k+2指令比k+1指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟，所以对 R0的写是在程序执行开始后的第八个时钟。不能在同一时钟周期内写写同一寄存器，因此 k+2指令应推迟一个时钟进入流水线，产生了流水线停顿。另外，可分析“先读后写”相关不会产生流水线的停顿。（3）由题意可认位该指令流水线由六个功能段取指、译码、取数、运一、运二和存数等组成，则程存数K存数K+1存数K+2存数运二K+1运二运一K+1运一 K+2运一取数K 取数K+1取数 K+2 取数译码K 译码 K+1译码K+2 译码取指1K取指 K+1 取指K+2取指时间0 12 3 4 5 67 893条指令顺序流动，共需要9个时钟周期。序指令执行过程的流水线时空图如下图所示。若“空间某流水线由4个功能部件组成，每个功能部件的执行时间都为△ t。当输入10个数据后，停顿5t,又输入10个数据，如此重复。计算流水线的实际吞吐率、加速比和效率，并画出时空图。解：该题中的流水线的任务是非连续流入的，因此不能直接应用公式直接计算，要利用时空图。题意的流水线时空图如下图所示。TP=10/15AtTP=10/15At=0.67/ At0/Tk=10X4At/15At=2.671234567891011212345678910122345(578/)10-234567891012S4S3S2S11“空间0123456789101112131415161718时间E=4X10At/4X15At=0.673.11有一个四段指令流水线为取指（IF）、译码（ID）、执行（ER、写回（WB,分支指令在第二个时钟周期未决定是不是条件失败分支，在第三个时钟周期未决定是不是成功分支，还假定第一个时钟周

期的操作和条件分支无关，并略去其它流水线停顿。要求：(1)分别画出无条件分支、发生的条件分支、不发生的条件分支时指令执行的时空图。(2)假设条件分支指令占所有指令的 20%且其中60%旨令可能执行，无条件分支占 5%问实际的流水线加速比是多少。解：(1)根据题意，分支指令采用的是流水线停顿的方法来处理。 而判断条件分支指令让流水线停顿，应在取指功能段后设计一个“指令分析器”来判断流水线是否停顿。显然，无条件分支指令与条件成功(发生条件)分支是一样的，需要在第三个时钟周期未决定下一条指令的地址，因此流水线要停顿二个时钟周期。对于条件失败(条件不成功)分支，需要在第二个时钟周期未决定下一条指令的地址，因此流水线要停顿一个时钟周期。(2)串行执行N条指令的时间为：T1=N-k-At,流水线方式执行N条指令的时间为：Tn=(k-1)At+(N+N-5%-2+N・20%-60%-1.5)AtSn=T1/Tn=k/1.28103.13用一条5个功能段的浮点加法器流水线计算 F=£(Ai),每个功能段的延迟时间，每个功能段的延i1迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。解：为使计算过程充分利用流水线的性能，避免“先写后读”相关，需要将计算的算法改为：((((A+A2)+(A+A4))+(A9+A10))+((A5+A6)+(A7+A9)))且按括号的优先次序计算九次加法，相应的流水线时空图如下图所示。t空间TP=9/21AtTP=9/21At=0.429/At0/Tk=9X5At/21At=2.143S51;?3456789S4123456789S3123456789S2123456789S112345(5789时间 0123456789101112131415161718192021E=5X9At/5X21At=0.4293.15有一条3个功能段的流水线如下图所示，每个功能段的延迟时间均为△ t,但是，功能段险的输出要返回到它自己的输入端循环执行一次。输入—LS_I HS2 H_SL_I―'输出△t At At(1)如果每隔一个△t向流水线连续输入任务，这条流水线会发生什么问题？(2)求这条流水线能够正常工作的实际吞吐率、加速比和效率。(3)可用什么办法来提高流水线的吞吐率，画出改进后的流水线结构。解：(1)每个任务在段险要反馈循环一次，执行时间为 2At,其它各段的执行时间为At,因此应按

瓶颈段的执行时间2At流入任务，才不会发生冲突现象，否则会发生流水线的阻塞。(2)若连续输入n个任务，则流水线的实际吞吐率、加速比和效率分别为：TP=n/ (4At+2(n-1)At)=n/2(n+1)AtS=4nAt/(4At+2(n-1)At)=2n/(n+1)E=4n At/3(4At+2(n-1)At)=2n/3(n+1)(3)为提高流水线的吞吐率，可重复设置段S,并使两个段S2串连在一起，从而消除瓶颈段 S2,而且各段执行时间相等为At,流水线的段数为4。流水线的结构如下图所示。输入输出△t△t△t At3.16在一个5段的流水线处理机上需经输入输出△t△t△t At3.16在一个5段的流水线处理机上需经9At才能完成一个任务，其预约表为:(1)写出流水线的初始冲突向量。(2)画出流水线任务调度的状态有向图。(3)求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率。(4)按最优调度策略连续输入8个任务时，流水线的实际吞吐率是多少解：(1)解：(1)根据初始冲突向量的构成方法,对预约表各行中打“X”的拍数求出差值，除去重复的后汇集在F={1,5,6,8}F={1,5,6,8}。由F可得到初始冲突向量为:C=(2)根据后继冲突向量的递推规则（10110001）Cj=SHR（k）（C）G四个后继状态：C=SHR⑵(Co)VC0:=10111101C2=SHR⑶（Q）VCo=:10110111C3=SHR”）（G）VCO=10111011C4=SHR⑺（Co）VC0:=10110001=C0C二个后继状态：C5=SHR⑵(C)VCo:=10111111C6=SHR⑺（G）VC0=:10110001=C0G二个后继状态：G=SHR⑷(G)VCo:=10111011=C3C8=SHR⑺（Q）VCd=10110001=C0G二个后继状态：G=SHR⑶(G)VCo:=10110111=C2Co=SHR7）（G）VC0=:10110001=C0。一个后继状态：C11=SHR：7)(C5)VCo=：10110001=C0起，即得到延迟禁止表为由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。(3)由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。调度策略平均延迟时间(2,2,7)(2+2+7)At/3=3.67At(2,7)(2+7)At/2=由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。(3)由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。调度策略平均延迟时间(2,2,7)(2+2+7)At/3=3.67At(2,7)(2+7)At/2=4.5At(3,4,7)(3+4+7)At/3=4.67At(3,7)(3+7)At/2=5At(4,3,7)(4+3+7)At/3=4.67At(4,7)(4+7)At/2=5.5At⑺ 7△t特别地，从C0出发的［3,(4,3)］也是一个任务调度策略，除第一条有向弧外，第二、三条有向组成一个环路，该调度策略为( 4,3)。从表中可以得到平均延迟时间最小的调度策略为( 4,3),该调度策略则为最优调度策略，相应的最小平均延迟时间为3.5At,所以流水线的最大吞吐率为：TPmax=1/ (3.5At)=0.286/At3,(4,3) (4+3)At/2=3.5At(4)按最优调度策略[3,(4,3)]连续输入8个任务时，流水线的实际吞吐率为:TP=8/[ (3+4+3+4+3+4+3+9 )At]=0.24/At3.17有一个5段流水线的预约表如下：(1)画出流水线调度状态有向图。(2)分别求出允许不等间隔调度和等间隔调度的最优调度策略以及这两种调度策略的最大吞吐率。解：(1)根据初始冲突向量的构成方法,对预约表各行中打“X”的拍数求出差值，除去重复的后汇集在起，即得到延迟禁止表为F={1,3,6}。由F可得到初始冲突向量为:根据后继冲突向量的递推规则C=SHRk)。G三个后继状态：0=SHR⑵(Q)VC0=101101C2=SHR(4)(Q)VC0:=100111C3=SHR'5)9)VG=:100101=C0C二个后继状态：C4=SHR2)(G)VC0=101111C5=SHR⑸(C)VG:=100101=C0C2二个后继状态：C6=SHR⑷(G)VC0=100111=C2C=SHR'5)9)VC0=:100101=C0C4一个后继状态：C8=SHR⑸(C4)VC0=100101=C0C 0=(100101)Co则可得出所有的后继状态，具体有:由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示。(2)由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间，如下表所示。调度策略平均延迟时间(2,5)(2+5)At/2=3.5At(4,5)(4+5)At/2=4.5At(5) 5△t(2,2,5)(2+2+5)At/3=3At4,(4)4 At特别地，从Co出发的［4,(4)］也是一个任务调度策略，除第一条有向弧外，第二条有向弧是一个环路，该调度策略为(4)。从表中可以得到平均延迟时间最小的等间隔和不等间隔的调度策略为［4,(4)］和(2,2,5),相应的最小平均延迟时间为4At和3At,所以流水线的最大吞吐率为：Bmax=1/ (3At)=0.33/AtTPAmax=1/ (4At)=Bmax=1/ (3At)=0.33/At(3)按等间隔最优调度策略［4,(4)］连续^^入10个任务时，流水线的实际吞吐率为:TP=10/[ (4+4+4+4+4+4+4+4+4+7 )△t]=10/43At按不等间隔最优调度策略(2,2,5)连续输入10个任务时，流水线的实际吞吐率为：TP=10/[ (2+2+5+2+2+5+2+2+5+7 )△t]=5/17At第四章习题4.13由3个访问速度、存储容量和每位价格都不相同的存储器构成一个存储系统， 3个存储器M1、M2和M3的访问周期分别为R1、R2和R3,存储容量分别为Sl、S2和S3,每位价格分别为C1、C2和C3,Ml靠近CPU(1)写出这个三级存储系统的等效访问时间、等效存储容量 S和等效每位价格C的表达式。TOC\o"1-5"\h\z(2)在什么条件下，整个存储系统的每位平均价格接近于 C3?解：(1)设H为CPU^存在M中的概率，则存储系统的等效访问时间、存储容量和每位价格分别为:3 3 3T=ZHi*Ti、S=S3C=(£Ci*Si)/S,且£Hi=1。i1 i1 i1(2)当三个存储器的存储容量之间有 S3》S2»S1时，C=C&4.17在一个采用组相联映象方式的 Cache存储系统中，主存由Bo〜B7共8块组成，Cache有2组,每组2块，每块大小为16B。在一个程序执行过程中，访存的主存块地址流为： Be, B2, B4, B1,区，Bs,Bo,B,B5, E3O(1)写出主存地址的格式，并标出各字段的长度。(2)写出Cache地址的格式，并标出各字段的长度。(3)指出主存与Cache之间各个块的映象关系。(4)若Cache的4个块号为Co、G、C2和G,列出程序执行过程中的 Cache块地址流。(5)若采用FIFO替换算法，计算Cache的块命中率。(6)若采用LRU替换算法，计算Cache的块命中率。(7)若改为全相联映象方式，再做(5)和(6)。(8)若在程序执行过程中，每从主存装入一块到 Cache,平均要对这个块访问 16次，计算在这种情况下的Cache命中率。解：(1)(2)采用组相联映象时，主存和 Cache地址的格式分别为：区号E区号E区内组号G主存组内块号E块内地址W组号g组内块号b块内地址w主存按Cache的大小分区，现主存有8个块，Cache有2X2=4个块，则主存分为8/4=2个区，区号E的长度为1位。又每区号Gg的长度都为1个块，则块号B、b的位。每块大小为16个地址Ww的长度都为4的长度为1位。又每区号Gg的长度都为1个块，则块号B、b的位。每块大小为16个地址Ww的长度都为4(3)根据组相联存块0〜7与Cache块象关系为：主存块0、1、0、1之间全相联，主存块时间：567812主存块地址流：Cache块地址流:44*4*4*4*00*55511111*44*4*4*66*6*6*6*6*33333*3*222222*2*2*2*772、3、6、7与Cache块2、3之间全相联。9B7联映象的规则，该主一种Cache块地址流换算法为FIFO)。1234(4)根据组相存块地址流相应的如下表所示(组内替6B21B4B6B3B0B4B51C0C2C2C0C0C0有2个组，则组位。而每组有2长度又都为1存储字，故块内位。映象的规则，主0〜3之间的映4、5与Cache块1011(5)组内替换算法采用FIFO时，Cache块0〜3的使用过程如下表所示。时间： 123456789101112主存块地址流： B6B2B4B1B4B6B3B0B4B5B7B3Cache块0Cache块1Cache块2Cache块3命中命中 命中可见命中三次，Cache块命中率为H=3/12=0.25 。(6)组内替换算法采用LRU时，Cache块0〜3的使用过程如下表所示。时间：123456789101112主存块地址流： B6B2B4B1B4B6B3B0B4B5B7B3Cache块0Cache块1Cache块2Cache块3命中命中 命中 命中可见命中四次，Cache块命中率为H=4/12=0.33 。(7)全相联映象的规则是主存块 0〜7可装入Cache块0〜3的任一块上。当替换算法采用FIFO时，Cache块0〜3的使用过程如下表所示。时间：123456789101112主存块地址流： B6B2B4B1B4B6B3B0B4B5B7B3Cache块0Cache块1Cache块2Cache块3命中命中 命中 命中可见命中四次， Cache块命中率为H=4/12=0.33 。当替换算法采用LRU时，Cache块0〜3的使用过程如下表所示。时间：123456789101112主存块地址流： B6B2B4B1B4B6B3B0B4B5B7B3Cache块0Cache块1Cache块2Cache块3命中命中 命中可见命中三次， Cache块命中率为H=3/12=0.25 。(8)当命中三次时， Cache的命中率为H=(12X16-9)/(12X16)=1,当命中四次时， Cache的命中率为H= (12X16-8)/(12X16)=1。4.18在某联目录表实现地址6666*6*6*33333*3*222222*00000中，Cache的谷重是444444*4*555储体组成的低位交总容量是2MB,每一1111111*77位，。采用全相联映象、相变换Cache存储器2cB,主存是由m个存叉访问存储器，主存个存储体的字长是w(1)画出地址变换图。(2)写出主存地址和Cache地址的格式，并标出各字段的长度。(3)说明目录表的行数、相联比较的位数和目录表的宽度。解：(1)主存地址解：(1)主存地址目录表共有Q个字Cache地址命中(2)采用全相联映象时，主存和 Cache地址的格式分别为:

主存块号B主存块号B块内地址W组内块号b块内地址w主存和Cache单元数分别为：8X2Mw、8X2c/w,相应的地址长度分别为：log2(8X2Mw)=M+3-log2W、log2(2c/w)=C+3-log2W。块的大小为m个存储字，则主存和Cache的块内地址长度均为：log2日所以主存和Cache的块号长度分别为：(M+3-log2w)-log2m=M+3-log2wm(C+3-log2w)-log2m=C+3-log2wm(3)相联目录表的行数为(3)相联目录表的行数为Cache的块数，即Cb=2即M+3-log2wm，目录表的宽度(位数)为主存块号长度、C+3-log2wm+1=M+C+6-2log2wm+1(有效位一位)。(C+3-log2wm)=2C+3/wm；相联比较的位数为主存块号长度，Cache块号长度和有效位的和，即 M+3-log2wm+麦人位王仔贝号13110203120110004.25某页式虚拟存储器的虚拟空间分为 8个虚页,虚页号为0〜7,页的大小为1024个字，主存容量为4096个字，页表内容如表所示。(1)列出会发生页面失效的全部虚页号。(2)按以下虚地址计算出变换的主存实地址：0 , 3728, 1023, 1024,2055 ,7800, 4096, 6800。解：(1)页表的行号即是虚页号，装入位为“ 1”表示相应虚页已装入主存中，实页号指出的实页位置；装入位为“0”表示相应虚页未装入主存中，该行实页号无效。所以由给出的表可知，发生页面失效的全部虚页号是：2,3,5,7。(2)页式管理的虚拟存储器的虚、实地址变换的计算步骤如下：①由虚地址Av计算相应的虚页号P和页内地址D:P二 「虚地址Av/页面长度1024个字」 D=A vPX页面长度②由虚页号查页表的相应行，若装入位为“ 0”，则发生页面失效，需调进页，无需地址变换；若装入位为“1”，则取出相应的实页号p。③由于d=D,则可由实页号p和页内地址D计算出实地址A=pX1024+D=按上述步骤，则可由虚地址计算出变换出主存实地址如下表所示。虚地址A虚页号P页内地址D装入位实贝号p页内地址d实地址a0001303072372836560贝囿失效无102301023131023409510241011010242055270贝囿失效无780076320贝囿失效无409640120204868006656106566564.26一个程序由1200条指令组成，每条指令的字长均为 4个字节。假设这个程序访问虚拟存储器的字地址流为：12 ,40,260,280,180,800,500,560,600,1100,1200,1000采用FIFO替换算法，分配给这个程序的主存容量为 2048B。在下列不同的页面大小情况下， 分别写出这程序执行过程中依次访问的虚页地址流，并计算主存实页命中率。(1)页的大小为1024B。 (2)页的大小为512B。(3)页的大小为2048B。 (4)比较(1)、(2)、(3)的结果，可得出什么结论？(5)假设把分配给该程序的主存容量增加到 4096B,页的大小为1024B,再计算主存实页命中率。由此又可以得出什么结论？解：题中给出了字虚地址流，由虚地址可得出其相应的虚页号为：虚页号别地题中虚地址流是以字为单位，而页面大小是以字节为单位，且字长为另外，由给出的分配给主存容量和页面大小可得出相应的实页数为：实页数=「虚地址/页面大小」；特4B解：题中给出了字虚地址流，由虚地址可得出其相应的虚页号为：虚页号别地题中虚地址流是以字为单位，而页面大小是以字节为单位，且字长为另外，由给出的分配给主存容量和页面大小可得出相应的实页数为：实页数=「虚地址/页面大小」；特4B。=「主存容量/页面大小」。(1)页面大小(1)页面大小1024B=256字,实页数=「2048B/1024B」=2。根据给出的程序访存的字地址流对主存的使用过程为:虚页地址流：0 0110312 244 3虚页地址流：0 0110312 244 30页000*0*0*333*3*441页1111*1*222*2*虚字地址流： 12402602801808005005606001100120010004*3命中命中命中命中命中命中则有主存命中率为： Hi=6/12=0.5(2)则有主存命中率为： Hi=6/12=0.5(2)页面大小512B=128字，根据给出的程序访存的字地址流对主存的使用过程为:实页数=「2048B/512B」二4。虚字地址流:虚页地址流:124026028018080056060011001200100089 70*33虚字地址流:虚页地址流:124026028018080056060011001200100089 70*33333*722*44444*111*1*88850040216*命中命中命中则有主存命中率为： Hb=3/12=0.25(3)则有主存命中率为： Hb=3/12=0.25(3)页面大小1024B=512字，根据给出的程序访存的字地址流对主存的使用过程为:实页数=「2048B/2048B」二1。虚字地址流:虚页地址流:1240026028018018000虚字地址流:虚页地址流:12400260280180180005005601 1 260021100112001000命中 命中命中命中命中命中命中 命中则有主存命中率为： H3=6/12=0.5(4)当主存容量不变时，①中的页长>②中的页长，且有H>H2,(4)当主存容量不变时，①中的页长因在于页长减小，虚、实页数增加，程序跨页访问的概率增大，导致主存命中率下降。另外，当主存容量不变时，③中的页长 >①中的页长，且有H=H2,说明页长加大，主存命中率不变。原因在于页长加大，虚、实页数减小；一方面虚页数减小，可降低跨页访问的概率，可提高主存命中率；另一方面实页数减小，主存替换概率增大，导致主存命中率下降。(5)页面大小1024B=256(5)页面大小1024B=256字,实页数二「4096B/1024B」二4。根据给出的程序访存的字地址流对主存的使用过程为:虚字地址流:1240260280180800500560600110012001000虚字地址流:虚页地址流：0 0 1 1 0 3 1 2 2 40*0*444111111*1*1*页页页命中 命中命中则有主存命中率为111111*1*1*页页页命中 命中命中则有主存命中率为： Hk=7/12=0.58命中命中命中命中当页长不变时，主存容量增大，实页数增加时，主存命中率增大。但不是总是如此。4.27采用页式虚拟存储器，分时运行两道程序，其中程序X为：DO50I=1,3B(I)=A(I) -C(I)IF (B(I).LE.0)GOTO40D(I)=2*C(I) -A(I)IF (D(I).EQ.0)GOTO5040E(I)=050CONTINUEDATA:A=(-4,3,0)C=(-3,0,1)2,每个数组分别存放在不同的页面中； 而程序Y在运行过程中，其数组将依次用到程序空间的第3,5,4,2,5, 3,1, 3, 2,5,1, 3, 1,5,2页。如果采用LRU算法替换，实存只有 8页位置可供存放数组之用。试问为这两道程序的数组分配多少个实页最为合理？为什么？解：程序Y运行过程中要使用的数组虚页地址流题中已给出， LRU算法是堆栈算法，用堆栈对其模拟处理一次的过程如下所示。时间：1234567时间：123456789101112131415虚页地址流：3 5423 54353虚页地址流：3 5423 5435335425 3 12 5 34 2 53 4 25313 2 51 3 25 1 32 5 132511 3 15 1 32 5 53 2 23152521 53 12 3S(1)StS(1)St(2)St(3)St(4)St⑸St(6)n=1n=2 命中n=3 命中 命中命中命中命中n=4 命中命中n=5 命中命中命中命中命中命中

命中命中命中命中命中命中命中命中

命中命中命中命中程序XSt⑸St(6)n=1n=2 命中n=3 命中 命中命中命中命中n=4 命中命中n=5 命中命中命中命中命中命中

命中命中命中命中命中命中命中命中

命中命中命中命中数组所在的虚页号。E来表示E;第二CA、D、程序做三次循环。第一次循环B(1)=-1<0,转40号语句E(1)=0,所以使用数组为A、CB、次循环B(2)=2>0,顺序执行D(2)=-2,又D(2)<>0,顺序执行E(2)=0,所以使用数组为A、CBE;第三次循环同第一次循环为A、E来表示E;第二CA、D、NHXH时间：1234567891010012131415ACB)EA2C5B(CADEACBE 虚页地址流：A3A(3/153 E4A5C1BCADEACBBCADE4A8/1夕B1•15A/\BCADEACE510/1A)C10/15E1EEBCCDEAA、C、BE、A、C、BC、A、DE、A、C、BE用堆栈对其模拟处理一次的过程如下所示。EBBBDD11CASt(1)St(2)St(3)St(4)St⑸St(6)n=1n=3n=4 命中命命中命中 命中n=3n=4 命中命命中命中 命中命中命中 命中命中 命n=5 命中命命中命中 命中命中命中命中命由堆栈处理结果可得出相应于 X和Y程程配衣W二加巍YHXHrHran/dr353/1510/156.5/15