系统结构答案

1、第 一 章 1.26 假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90，那么，采用Cache后能使整个存储系统获得多高的加速比? T0 1解：根据Amdahl定理有：Sn = = ；结合题意：Cache工作速度为 Tn （1 Fe）+ Fe / Se主存的5倍，相当于改进存储器后获得的加速比为5，即Se=5；Cache被访问命中的概率为90，相当于访问存储器的时间有90化在Cache上，即Fe=0.9。 所以 Sn = 1/（1-0.9）+0.9/5 = 3.571.27 设计指令存储器有两种不同方案：一种是采用价格较贵的高速存储器芯片，另一种是采用价格便宜的低速

2、存储器芯片。采用后一方案时，用同样的经费可使存储器总线带宽加倍，从而每隔2个时钟周期可取出2条指令(每条指令为单字长32位)。而采用前一方案时，每一个时钟周期取出一条单字长指令。由于访存局部性原理，当取出2个指令字时，通常这2个指令字都要使用，但仍有25的时钟周期中，取出的2个指令字中仅有1个指令字是有用的。试问采用这两种实现方案所构成的存储器带宽是多少？ 解：带宽是指单位时间内处理的二进制位数，相当于频率，用f表示。 采用方案A时，存取指令的CPIa = 1时钟周期/指令字，即：fa = 1/CPIa ×指令字长 = 1×32 = 32位/时钟周期。采用方案B时，存取指令

3、的CPIb = 0.75×2/2 + 0.25×2/1 = 1.25时钟周期/指令字，即： fa = 1/CPIa ×指令字长 = 0.8×32 = 25.6位/时钟周期。1.28 某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个测试程序。假定每次存储器存取为1个时钟周期，试问：(1)此计算机的有效CPI是多少?(2)假定将处理机的时钟频率提高到30MHz，但存储器的工作速率不变，这样，每次存储器存取需要2个时钟周期。如果30指令每条只需要一次存储器存取操作，另外5指令每条需要二次存储器存取操作，假定测试程序的指令数不变，并与原

4、工作站兼容，试求改进后的处理机CPI和MIPS。 解：（1）由MIPS = 时钟频率/（CPI×106），则有：CPIA =时钟频率/（MIPS×106）= 1.5。 （2）当时钟频率为15MHZ时，假设不进行存储操作指令的CPI为x，则要进行一次存储操作指令的CPI为1+ x，要进行二次存储操作指令的CPI为2+ x，因此有： 1.5 = x×65% + （1+ x）×30% + （2+ x）×5% 解得x = 1.1当时钟频率为30MHZ时，不进行存储操作指令的CPI不变为1.1，要进行一次存储操作指令的CPI为2+ x = 3.1，要进行

5、二次存储操作指令的CPI为4+ x = 5.1，因此平均CPI为： CPIB = 1.1×65% + 3.1×30% + 5.1×5% = 1.9所以 MIPSB = 时钟频率/（CPIB×106）=（30×106）/（1.9×106）= 15.8MIPS1.29 某计算机Cache能存放2000条指令。假设10%的指令承担了90%时间的指令访问，而且这10%指令中每条指令的执行时间相同。如果要执行的某程序共50000条指令，当计算机执行该程序时，在Cache中能访问到的指令的概率是多少？解：由题意可知：45000条指令承担10%时间

6、的指令访问，5000条指令承担90%时间的指令访问。显然5000条指令被频繁使用，设平均使用次数为X；另外45000条指令仅使用一次。则有：45000 : 0.1 = 5000X : 0.9 解得 X = 81所以该程序执行指令的条数为Y = 45000 + 5000×81 = 450000假设频繁使用的5000条指令均匀分布于程序之中，即每次调入Cache的2000条指令有200条是频繁使用的。另假设每次调入Cache的2000条指令中的1800条均被使用了一次。所以执行该程序时Cache中能访问到的指令的概率为: （450000 - 50000/2000）÷ 45000

7、0 100%1.30 有一台计算机，不同类型指令在理想Cache（无访问失败）与实际Cache（有访问失败）两种情况下的性能如下表。求理想Cache相对于实际Cache的加速比？指令类型 出现频率 理想CacheCPI 实际CacheCPI运算指令 40% 1 3取数指令 20% 2 8存数指令 15% 2 8控制指令 25% 2 4解：理想Cache情况下指令的平均时钟周期数CPI为： CPI理想 = =1×40%+2×20%+2×15%+2×25% = 1.6实际Cache情况下指令的平均时钟周期数CPI为： CPI实际= =3×40%+8

8、×20%+8×15%+4×25% = 5.0S = 实际CacheCPU执行时间/理想CacheCPU执行时间=（IC×时钟周期×CPI实际）/（IC×时钟周期×CPI理想）= CPI/CPIA = 5.0/1.6 = 3.121.31 假设在一台40MHz处理机上运行测试程序共有200000条指令，由4类指令组成。已知指令的CPI和所各占比例如下表。 指令类型 指令比例 CPI算逻运算 60% 1 Cache命中存取 18% 2 控制指令 12% 4 Cache末命中访主存 10% 8 (1)计算处理机运行该程序的平均CP

9、I。(2)根据(1)所得CPI，计算相应的MIPS速率。解: （1）CPI= =1×60% + 2×18% + 4×12% + 8×10% = 2.2（2）MIPS = 时钟频率/（CPI×106）= 40×106/（2.2×106）= 18.191.32 已知4个程序在A、B、C 三台计算机上的执行时间(秒)分别如下表，假设每个程序都有100×106条指令要执行，计算这3台计算机对每个程序的MIPS速率。根据这些速率值，你能否得出这3台计算机相对性能的明确结论？你能否找到一种将它们排序的方法？试说明理由。 程序

10、计算机A 计算机B 计算机C程序1 1 10 20程序2 1000 100 20程序3 500 1000 50程序4 100 800 100 解：（1）由MIPS的定义有：MIPS = Ic/(Tcpu×106) = 100×106/(Tcpu×106) = 100/Tcpu。根据上表中列出的Tcpu则可计算出相应的MIPS如下表所示。 程序 计算机A 计算机B 计算机C程序1 100 10 5程序2 0.1 1 5程序3 0.2 0.1 2程序4 1 0.125 1（2）由于MIPS与指令值、指令使用的频率等有关，在同一台机器上运行不同的程序，得出不同的速率MI

11、PS，因此不能仅用MIPS来评价计算机性能的优劣。而应用执行程序的算术平均Tcpu来评价比较好。 TcpuA = （1+1000+500+100）/4 = 400.25 TcpuB = （10+100+1000+800）/4 = 477.5TcpuC = （20+20+50+100）/4 = 47.5所以性能排序为：C > A > B。第 二 章 2.25 浮点数系统使用的阶码基值re=2，阶值位数q=2，尾数基值rm=10，尾数位数p=1，即按照使用的二进制位数来说，等价于p=4。计算在非负阶、正尾数、规格化情况下的最小尾数值、最大尾数值、最大阶值、可表示的最小值和最大值及可表示

12、数的个数。解: 最小尾数值：rm-1 = 10-1 = 0.1最大尾数值：1- rm-p =1-10-1 = 0.9最大阶值：2q-1=3可表示数的最小值：1×rm-1 = 10-1 = 0.1可表示数的最大值：rm2q-1×（1- rm-p）=103（1-10-1）= 900可表示数的个数：2q×rmp（rm-1）/rm = 22×101（10-1）/10 = 362.26 一个处理机有I1I10共10条指令，经统计，各指令在程序中出现的概率如下：I1：0.25 I2：0.20 I3：0.15 I4：0.10 I5：0.08I6：0.08 I7：0.0

13、5 I8：0.04 I9：0.03 I10：0.02（1）计算这10条指令的操作码最短平均长度。（2）写出这10条指令的Huffman编码，并计算操作码编码的平均长度和信息冗余量。（3）采用3/7扩展编码法和2/8扩展编码法编写这10条指令的操作码。并分别计算编码的平均长度和信息冗余量。说明哪一种扩展编码较好的理由。解：（1）操作码编码的最短平均长度为：H=-×log2pi H= (0.25log20.250.20log20.200.15log20.150.10log20.100.08log20.080.08log20.080.05log20.050.04log20.040.03lo

14、g20.030.02log20.02) =2.96（位） （2）根据给出的使用频度，在构造Huffman树的过程中，有两个结点可供合并，因此可生成不同的Huffman树，其中给出一棵如图所示，相应的Huffman编码如表所示。1.00 1 0 1 0 1 00.150.080.050.570.320.170.090.040.250.20 I2 I10.10 1 0 1 00.080.430.230.130.05 1 0 I4 1 0 I30.030.02 1 0 I6 1 0 I5 I10 I9 I8 I7IiPiHuffman编码Li2-5编码（3/7）Li2-4编码（2/8）LiI1025

15、002002002I2020102012012I3015010310210004I4010110311000510014I50080110411001510104I60081110411010510114I700501110511011511004I800401111511100510014I900311110511101511104I1000211111511110511114 Huffman编码的平均长度为：l=×lil = 0.25×20.20×20.15×30.10×30.08×40.08×40.05×50

16、.04×50.03×50.02×5 = 2.99（位） Huffman编码的信息冗余量为：R = 1-H/l =（12.96/ 2.99）×100% = 1.0%（3）3/7扩展编码和2/8扩展编码如表所示。3/7扩展编码要求短码码点数为3，长码码点数为7。所以短码长取2位，有码点22=4个，用一个作扩展标志；长码长取3位，有码点23=8个，有一个未被利用，即有一个 余码点。编码的平均长度为：l = (0.250.200.15)×2(0.100.080.080.050.040.030.02)×5 = 3.2（位）3/7扩展编码的信息冗

17、余量为：R = 1H/l =（12.96/ 3.2）×100% = 7.5%2/8扩展编码要求短码码点数为2，长码码点数为8。所以短码长取2位，有码点22=4个，用二个作扩展标志；长码长取2位，有码点22×2=8个，码点全部被利用，即没有多余码点。l = (0.250.20)×2(0.150.100.080.080.050.040.030.02)×4 = 3.1（位）2/8扩展编码的信息冗余量为：R = 1H/l =（12.96/ 3.1）×100% = 4.5% 可见，2/8扩展编码优于3/7扩展编码。2.27 经统计，某种处理机14条指令的

18、使用频度分别为：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.15 0.15 0.14 0.13 0.12 0.11 0.04 0.04 0.03 0.03 0.02 0.02 0.01 0.012.28 用于文字处理的某专用机，每个文字符用4位十进制数字（09）编码表示，空格用表示。在对传送的文字符和空格进行统计后，得出它们的使用频度如下：0.20 0:0.17 1:0.06 2:

19、0.08 3:0.11 4:0.085: 0.05 6:0.08 7:0.13 8:0.03 9:0.01（1）若对数字09和空格采用二进制编码，试设计编码平均长度最短的编码。（2）若传送106个文字符号，且每个文字符号后均自动跟一个空格，按最短的编码，共需传送多少个二进制位？若传送波特率为9600bPS，共需传送多少时间？（3）若对数字09和空格采用4位定长码编码，重新计算问题（2）。解：（1）操作码编码的平均长度最短为Huffman编码，生成的Huffman树，如图所示，相应的Huffman编码如表所示。l=×li = 3.23（位）。（2）根据题意，每个字符的二进制码的平均长度

20、为：3.23×（41）=16.15（位）。若要传输106个字符，则要传输二进制位数为：106×16.15 =1.615×107（位）若波特率为56Kb/s，则传输时间为：1.615×107/（56×103）=288（s）。1.000.010.040.090.200.400.030.050.110.200.080.060.140.270.600.160.080.130.330.170.08（3）当采用四位定长编码时，则需要传输二进制位数为：106×4（41）=2×107（位），传输时间为：2×107/（56×

21、;103）=357（s）。 1 0 1 0 1 0 1 0 1 0 1 0 3 7 0 5 1 6 4 2IiPiHuffman编码Li02010200170003701301033011110320080010440080011460080110410060111450051110480031111059001111115 9 82.29 一台模型机共有7条指令，各指令的使用频度分别为：35%，25%，20%，10%，5%，3%，2%，有8个通用数据寄存器，2个变址寄存器。（1）要求操作码的平均长度最短，请设计操作码的编码，并计算操作码编码的平均长度。（2）设计8位字长的寄存器寄存器型指令3

22、条，16位字长的寄存器一存储器型变址寻址方式指令4条，变址范围不小于正、负127。请设计指令格式，并给出指令各字段的长度和操作码的编码。2.30 一台模型机共有7条指令，各指令的使用频度分别为：35%，25%，20%，10%，5%，3%，2%，有8个通用数据寄存器，2个变址寄存器。（1）要求操作码的平均长度最短，请设计操作码的编码，并计算操作码编码的平均长度。（2）设计8位字长的寄存器寄存器型指令3条，16位字长的寄存器一存储器型变址寻址方式指令4条，变址范围不小于正、负127。请设计指令格式，并给出指令各字段的长度和操作码的编码。1.000.020.050.100.200.400.030.0

23、50.100.200.250.600.35解：（1）操作码编码的平均长度最短为Huffman编码，生成的Huffman树如图所示，相应的Huffman编码如表所示。l=×li = 2.35（位）IiPiHuffman编码Li2-4编码（3/4）LiI1035002002I2025012012I3020102102I4010110311004I50051110411014I600311110511104I700211111511114（2）由于通用寄存器有8个，则指令中通用寄存器字段应为3位；操作码字段2位可有4个码点，用三个码点表示三条指令，另一个码点则作为扩展标志。所以3条8位长的

24、寄存器寄存器型指令格式如下：操作码（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类

25、，每个地址字段的长度均为6位。（1）如果二地址指令有15条，一地址指令和零地址指令的条数基本相等。问一地址指令和零地址指令各有多少条？并为这3类指令分配操作码。（2）如果指令系统要求这3类指令条数的比例大致为1：9：9，问这3类指令各有多少条？并为这3类指令分配操作码。解：（1）操作码字段取4位可有24=16个码点，用15个码点（00001110）表示15条二地址指令，另一个码点（1111）则作为扩展标志。所以15条二地址指令格式如下：操作码（4位）地址码1（6位）地址码2（6位）由于要求一地址指令和零地址指令的条数基本相等。所以地址码1字段6位扩展有26=64个码点，用63个码点（11110

26、000001111111110）表示63条一地址指令，另一个码点（1111111111）则作为扩展标志。而用地址码2字段6位扩展有26=64个码点，64个码点都用来表示零地址指令，共有64条。（2）在一中指令条数的比例大约1：4.2：4.2，因此若使一地址指令和零地址指令加大一倍，则三类指令条数的比例大约1：9：9。操作码字段取4位时的16个码点，用14个码点（00001101）表示14条二地址指令，另二个码点（1110与1111）则作为扩展标志。扩展标志（1110）扩展地址码1字段6位的64个码点（11100000001110111111）全部用来表示一地址指令，有64条。扩展标志（1111

27、）扩展地址码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%要求有两种指令字长

28、，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设该机有若干通用寄存器，主存为16位宽，按字节编址，采用按整数边界存储，任何指令都在一个主存周期中取得，短指令为寄存器-寄存器型，长指令为寄存器-主存型，主存地址应能变址寻址。（1）仅根据使用频度，不考虑其它要求，设计出全Huffman操作码，计算其平均码长；（2）考虑题目全部要求，设计优化实用的操作码形式，并计算其操作码的平均码长；（3）该机允许使用多少可编址的通用寄存器？（4）画出该机两种指令字格式，标出各字段之位数；（5）指出访存操作数地址寻址的最大相对位移量为多少个字节？解：（1）根据给出的使用频度，在构造Huff

29、man树的过程中，有两个结点可供合并，因此可生成不同的Huffman树，其中给出一棵如图所示，相应的Huffman编码如表所示。 Huffman编码的平均长度为：l=×lil=0.3×20.24×20.2×20.07×40.07×40.06×40.03×50.02×60.01×6=2.61（位）0.560.010.030.060.120.260.020.030.060.070.141.000.200.070.440.240.30 ADD CLA SUB J0M JMP STO CIL 指令IiP

30、iHuffman编码Li2-5编码（3/6）LiADDI1030012002SUBI2024112012CLAI3020102102STOI400700114110015JMPI500700104110105JOMI600600014110115CILI7003000015111005SHRI80020000016111015STPI90010000006111105 STP SHR （2）任何指令都在一个主存周期中取得，那么短指令字长为8位，长指令字长为16位。又指令都是二地址指令，所以短指令寄存器-寄存器型的格式为：操作码（2位）寄存器1（3位）寄存器2（3位）长指令为寄存器-主存型的格式

31、为：操作码（5位）寄存器（3位）变址寄存器（3位）相对位移（5位）由题意可知：指令操作码采用扩展编码，且只能有两种码长。从指令使用频度来看，ADD、SUB和CLA三条指令的使用频度与其它指令的使用频度相差较大，所以用两位操作码的三个码点来表示三条指令，一个码点作为扩展码点，且扩展三位来表示六条指令，即采用2-4扩展编码构成3/6编码，2-4扩展编码如表所示。 2-4扩展编码（3/6）的平均长度为：l=×li=2.78（3）（4）由短指令寄存器-寄存器型的格式可知，寄存器号字段长度为3位，寄存器个数为8个。则各字段长度如图格式所标识。而对于长指令寄存器-主存型，一般变址寄存器是某通用寄

32、存器，则变址寄存器号的字段长度为3位，则各字段长度如图格式所标识。（5）由于相对位移字段长度为5位，因此访存地址寻址的最大相对位移量为25=32字节。第 三 章 习 题3.8 在一台单流水线多操作部件的处理机上执行下面的程序，每条指令的取指令、指令译码需要一个时钟周期，MOVE、ADD和MUL操作分别需要2个、3个和4个时钟周期，每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k： MOVE R1，R0 ；R1 (R0)k+1： MUL R0，R2，R1 ；R0 (R2)×(R1)k+2： ADD R0，R2，R3 ；R0 (R2)+(

33、R3)(1)就程序本身而言，可能有哪几种数据相关?(2)在程序实际执行过程中，哪几种数据相关会引起流水线停顿?(3)画出指令执行过程的流水线时空图，并计算完成这3条指令共需要多少个时钟周期？解：（1）就程序本身而言，可能有三种数据相关。若3条指令顺序流动，则k指令对R1寄存器的写与k+1指令对R1寄存器的读形成的“先写后读”相关。若3条指令异步流动，则k指令对R0寄存器的读与k+1指令对R0寄存器的写形成的“先读后写”相关，k+2指令对R0寄存器的写与k+1指令对R0寄存器的写形成的“写写”相关。（2）在程序实际执行过程中，二种数据相关会引起流水线停顿。一是“先写后读”相关，k指令对R1的写在

34、程序执行开始后的第四个时钟；k+1指令对R1的读对指令本身是第三个时钟，但k+1指令比k指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟要读R1。不能在同一时钟周期内读写同一寄存器，因此k+1指令应推迟一个时钟进入流水线，产生了流水线停顿。二是“写写”相关，k+1指令对R0的写对指令本身是第六个时钟，而要求该指令进入流水线应在程序执行开始后的第三个时钟，所以对R0的写是在程序执行开始后的第八个时钟。k+2指令对R0的写对指令本身是第五个时钟，而k+2指令比k+1指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟，所以对R0的写是在程序执行开始后的第八个时钟。不能在同一时钟周期内写

35、写同一寄存器，因此k+2指令应推迟一个时钟进入流水线，产生了流水线停顿。另外，可分析“先读后写”相关不会产生流水线的停顿。 （3）由题意可认位该指令流水线由六个功能段取指、译码、取数、运一、运二和存数等组成，则程序指令执行过程的流水线时空图如下图所示。若3条指令顺序流动，共需要9个时钟周期。 空间存数 K存数 K+1存数 K+2存数 运二 K+1运二 运一 K+1运一 K+2运一 取数 K取数 K+1取数 K+2取数 译码 K译码 K+1译码 K+2译码 取指 K取指 K+1取指 K+2取指 时间 0 1 2 3 4 5 6 7 8 93.9 某流水线由4个功能部件组成，每个功能部件的执行时间

36、都为t。当输入10个数据后，停顿5t，又输入10个数据，如此重复。计算流水线的实际吞吐率、加速比和效率，并画出时空图。解：该题中的流水线的任务是非连续流入的，因此不能直接应用公式直接计算，要利用时空图。题意的流水线时空图如下图所示。 空间 S4 1 2 3 4 5 6 7 8 9 10 1 2 S3 1 2 3 4 5 6 7 8 9 10 1 2 S2 1 2 3 4 5 6 7 8 9 10 1 2 S1 1 2 3 4 5 6 7 8 9 10 1 2 时间 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 TP = 10/15t = 0.67

37、/t S = T0/TK = 10×4t/15t = 2.67 E = 4×10t/4×15t = 0.673.11 有一个四段指令流水线为取指（IF）、译码（ID）、执行（EX）、写回（WB），分支指令在第二个时钟周期未决定是不是条件失败分支，在第三个时钟周期未决定是不是成功分支，还假定第一个时钟周期的操作和条件分支无关，并略去其它流水线停顿。要求： （1）分别画出无条件分支、发生的条件分支、不发生的条件分支时指令执行的时空图。 （2）假设条件分支指令占所有指令的20%，且其中60%指令可能执行，无条件分支占5%，问实际的流水线加速比是多少。解：（1）根据题意，

38、分支指令采用的是流水线停顿的方法来处理。而判断条件分支指令让流水线停顿，应在取指功能段后设计一个“指令分析器”来判断流水线是否停顿。显然，无条件分支指令与条件成功（发生条件）分支是一样的，需要在第三个时钟周期未决定下一条指令的地址，因此流水线要停顿二个时钟周期。对于条件失败（条件不成功）分支，需要在第二个时钟周期未决定下一条指令的地址，因此流水线要停顿一个时钟周期。 （2）串行执行N条指令的时间为：T1=N·k·t， 流水线方式执行N条指令的时间为：Tn=（k-1）t+（N+N·5%·2+N·20%·60%·1.5）t Sn

39、=T1/Tn=k/1.283.13 用一条5个功能段的浮点加法器流水线计算F=，每个功能段的延迟时间，每个功能段的延迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。 解：为使计算过程充分利用流水线的性能，避免“先写后读”相关，需要将计算的算法改为： （A1 + A2）+（A3 + A4）+（A9 + A10）+（A5 + A6）+（A7 + A9）且按括号的优先次序计算九次加法，相应的流水线时空图如下图所示。 空间 S5 1 2 3 4 5 6 7 8 9 S4 1 2 3

40、 4 5 6 7 8 9 S3 1 2 3 4 5 6 7 8 9 S2 1 2 3 4 5 6 7 8 9 S1 1 2 3 4 5 6 7 8 9 时间 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 TP = 9/21t = 0.429/t S = T0/TK = 9×5t/21t = 2.143 E = 5×9t/5×21t = 0.4293.15 有一条3个功能段的流水线如下图所示，每个功能段的延迟时间均为t，但是，功能段S2的输出要返回到它自己的输入端循环执行一次。S2S3S1 输入 输出

41、 t t t（1）如果每隔一个t向流水线连续输入任务，这条流水线会发生什么问题？（2）求这条流水线能够正常工作的实际吞吐率、加速比和效率。 （3）可用什么办法来提高流水线的吞吐率，画出改进后的流水线结构。解：（1）每个任务在段S2要反馈循环一次，执行时间为2t，其它各段的执行时间为t，因此应按瓶颈段的执行时间2t流入任务，才不会发生冲突现象，否则会发生流水线的阻塞。 （2）若连续输入n个任务，则流水线的实际吞吐率、加速比和效率分别为： TP = n/（4t +2（n1）t）= n/2（n + 1）t S = 4nt/（4t +2（n1）t）= 2n/（n + 1） E = 4nt/3（4t +

42、2（n1）t）= 2n/3（n + 1）（3）为提高流水线的吞吐率，可重复设置段S2，并使两个段S2串连在一起，从而消除瓶颈段S2，而且各段执行时间相等为t，流水线的段数为4。流水线的结构如下图所示。S3S2S2S1 输入 输出 t t t t3.16 在一个5段的流水线处理机上需经9t才能完成一个任务，其预约表为： 时间 1 2 3 4 5 6 7 8 9流水段S1 × ×S2 × × ×S3 ×S4 × ×S5 × ×延迟D2 × （1）写出流水线的初始冲突向量。（2）画出流水线任务调度的状态有向图。（3）求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率。（4）按最优调度策略连续输入8个任务时，流水线的实际吞吐率是多少? 解：（1）根据初始冲突向量的构成方法，对预约表各行中打“×”的拍数求出差值，除去重复的后汇集在一起，即得到延迟禁止表为F =1，5，6，8。由F可得到初始冲突向量为： C =（10110001） （2）根据后继冲突向量的递推规则Cj = SHR（k）（Ci）C0则可得出所有的后继状态，具体有：