计算机系统结构第2版课后习题答案

你计算机系统结构

清华第2版习题解答

tiger

200709011目录第一章(P33)7-1.9(透明性概念)，1.12-1.18(Amdahl定律),1.19、1.21、1.24(CPI/MIPS)1.2第二章(P124)2.3、2.5、2.6(浮点数性能),2.13、2.15(指令编码)1.3第三章(P202)3.3(存储层次性能)，3.5(并行主存系统)，3.15-3.15加1题(堆栈模拟),3.19中(3)(4)(6)(8)问(地址映象/替换算法—实存状况图)1.4第四章（P250）4.5（中断屏蔽字表/中断过程示意图）,4.8（通道流量计算/通道时间图）1.5第五章（P343）5.9（流水线性能/时空图）,5.15（2种调度算法）1.6第六章（P391）6.6（向量流水时间计算）,6.10（Amdahl定律/MFL0PS）1.7第七章（P446）3、7.29（互连函数计算），7.6-7.14（互连网性质）,7.4、7.5、7.26（多级网寻径算法）,27（寻径/选播算法）1.8第八章(P498)12(SISD/SIMD算法)1.9第九章(P562)18(SISD/多功能部件/SIMD/MIMD算法)（注：每章可选「2个主要知识点，每个知识点可只选1题。有下划线者为推荐的主要知识点。）2例，习题2.1第一章(P33)例1.1,pio假设将某系统的某一部件的处理速度加快到10倍,但该部件的原处理时间仅为整个运行时间解:的40%,则采用加快措施后能使整个系统的性能提高多少？由题意可知：Fe=0.4,Se=10,根据Amdahl定律解:Tc 1«1.56例1.2,pl0采用哪种实现技术来求浮点数平方根FPSQR的操作对系统的性能影响较大。假设FPSQR操作占整个测试程序执行时间的20%。一种实现方法是采用FPSQR硬件，使FPSQR操作的速度加快到10倍。另一种实现方法是使所有浮点数据指令的速度加快，使FP指令的速度加快到2倍，还假设FP指令占整个执行时间的50%。请比较这两种设计方案。解：分别计算出这两种设计方案所能得到的加速比：c—T。— 1一-（1一户e）十点FeFPSQR=0.20,Sefpsqr=10FeFP=0.50,Sefp=2—=1.220.82^n^nFP= 77T(l-0.5)+-y—=1.330.75例1.3,pll如果FP操作的比例为25%,FP操作的平均CPI=4.0,其它指令的平均CPI为1.33,FPSQR操作的比例为2%,FPSQR的CPI为20„假设有两种设计方案，分别把FPSQR操作的CPI和所有FP操作的CPI减为2。试利用CPU性能公式比较这两种设计方案哪一个更好（只改变CPI而时钟频率和指令条数保持不变）。解：CP1=£（CPI‘+原系统的CPIfp=4.0,~jq=25%CPR.33,j=1-25%CPU;=£（CP/,x*）=4.0X25%+1.33X75%=2方案1(使FPSQR操作的CPI为2)系统CPI=CPI原-CPLfW单^^+CPIHW新IC IC=CPI原-/7空(CPIhw®-CPIitswr)=2-2%X(20-2)=1.64方案2(提高所有FP指令的处理速度，使FPSQR操作的CPI为2)CPI=CPI-CPIfpk—+CPIfp»-^IC IC=CPI原-q(CPIfpk-CPIfp«)IC=2-25%X(4-2)=1.5我们也可以根据以下公式计算出方案2系统(同求CPIQCPI-75%X1.33+25%X2=1.5显然，提高所有FP指令处理速度的方案要比提高FPSQR处理速度的方案要好。方案2的加速比采用改进措施后的性能加卷生二没有采用改进措施前的性能SToCPC时间原系统"一工一CPC时间方案2ICx时钟周期＞CPI原系统IC＞时钟周期＞CPI方案2_CPI原系统CPI方案2=2/1,5=1.33例1.4假设两台机器的指令系统中，执行条件转移指令需2个时钟周期，而其它指令只需1个时钟周期。CPU.:采用一条比较指令来设置相应的条件码，由紧随其后的一条转移指令对此条件码进行测试，以确定是否进行转移。显然实现一次条件转移要执行比较和测试两条指令。条件转移指令占总执行指令条数的20%。由于每条转移指令都需要一条比较指令，所以比较指令也将占20%。CPUb采用比较功能和判别是否实现转移功能合在一条指令的方法，这样实现一条件转移就只需一条指令就可以完成。由于CPU,在转移指令中包含了比较功能，因此它的时钟周期就比CPU要慢25%«现在要问，采用不同转移指令方案的CP&和CPUh,那个工作速度会更快些？解：CPIA=0.2X2+0.8X1=1.2Tc™=ICAX1.2XtA=1.2ICAXtACPU；转移指令占20%—80%=25%CPI„=0.25X2+0.75X1=1.25由于CPU,中没有比较指令，因此ICb=0.8XICaCPU,时钟周期就比CPU要慢25%ts=1.25tATcpib=ICbXCPIbXts=0.8ICAXl.25Xl.25tA=1.25ICAXtATcpua<Tcpib所以CPUa比CPUb运行得更快些。例1.5在例L4中，如果CPUB的时钟周期只比CPUA的慢10%,那么哪一个CPU会工作得更快些？解：CPUb时钟周期就比CPUa要慢10%tB=1.10tATcpvb=ICbXCPIbX1b=0.8ICaX1.25X1.10tA=1.1ICaXtATcpva>Tcpvb所以CPUb比CPUa运行得更快些。例1.A1计算PentiumII450(IPC=2)处理机的运算速度。解：由于Pentiumll450处理机的IPC=2(或CPI=0.5)Fz=450MHz,MIPSpt.,lliu.ii4M=FzXIPC=450MHzX2=900(MIPS)例1.A2我国最早研制的小型计算机DJST30,定点16位，加法每秒50万次，但没有硬件乘法和除法指令，用软件实现乘法和除法，速度低100倍左右。求等效速度。解：定点等效速度为：指令条数 时钟频率MIPS= = 执行时间X1()6 CP/X106等效指令速度MIPS=1/(―+0,20)=0.02MIPS0.50.5/100即每秒2万次，由于乘法和除法用软件实现，等效速度降低了25倍。例LA3假设在程序中浮点开平方操作FPSQR的比例为2%,它的CPI为100：其他浮点操作FP的比例为23%,它的CPI=4.0；其余75%指令的CPI=L33,计算该处理机的等效CPI。如果FPSQR操作的CPI也为4.0,重新计算等效CPI。解：CP/=W（CP/,x今）等效CPI=100'2%+4'23%+l.33'75%=3.92等效CPI2=4'25%+1.33'75%=2.00解释下列术语层次结构，计算机系统结构，计算机组成，计算机实现，透明性，由上而下设计，由下而上设计，由中间向两边设计，软件兼容，向上兼容，固件，系列机，兼容机，模拟，仿真,虚拟机，宿主机，指令流，数据流，单指令流单数据流，多指令流多数据流，Amdahl定律,CPI,MIPS,MFLOPSo每一级为了执行一条指令需要下一级的N条指令解释，若执行第一级的一条指令需kns,那么执行第2级、第3级、第4级的指令需要多少时间？第1级1条1级指令kns第2级1条2级指令N条1级指令1-N-kns=Nkns第3级1条3级指令N条2级指令1-N-N-kns=N2kns第4级1条4级指令N条3级指令1-N-N-N-kns=N3kns每一级指令能完成下一级的M条指令的工作量，且每一级指令需要下一级的N条指令解释,若执行第一级的一条指令需kns,那么执行第2级、第3级、第4级的等效程序需要多少时间？第1级1条1级指令 kns第2级等效程序为1/M条2级指令需N/M条1级指令解释 N/M-kns第3级等效程序为1/M/M条3级指令需NN/M/M条1级指令解释 N2/M2ns第4级等效程序为1/M/M/M条4级指令需NNN/M/M/M条1级指令解释 Ns/M3ns试以实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系与相互影响。系统结构、组成和实现是三个不同的概念，它们各自包含不同的内容，但又有紧密的关系以存储系统为例，主存储器容量和寻址方式的确定属计算机系统结构，主存的速度应多高在逻辑结构上采用什么措施属计算机组成，而主存的物理实现，如存储器采用什么样器件逻辑电路设计和微组装技术则属计算机实现。什么是透明性概念？对计算机系统结构，下列哪些是透明的？哪些是不透明的?存贮器的模m交叉存取；透明（组成）浮点数据表示；不透明（系统结构）I/O系统是采用通道方式还是I/O处理机方式；不透明数据总线宽度；透明（组成）阵列运算部件：透明（组成）通道是采用结合型的还是独立型的；透明（组成）PDPT1系列中的单总线结构：不透明（系统结构）访问方式保护；不透明（系统结构）程序性中断：不透明（系统结构）串行、重叠还是流水控制方式；透明（组成）堆栈指令；存贮最小编址单位；不透明（系统结构）Cache存贮器。透明（组成）（1）从指定角度来看，不必要了解的知识称为透明性概念（2）见下表，“ 为透明性概念。模m交叉，V,浮点数据，x,P4通道与I/O处理机，X,P4总线宽度，J,阵列运算部件，X,结合型与独立型通道，V,单总线，访问保护，X,中断，X,指令控制方式，V,堆栈指令，X,最小编址单位，X,Cache存储器，V,1.8从机器（汇编）语言程序员看，以下哪些是透明的？■指令地址寄存器；指令缓冲器；时标发生器：条件码寄存器；乘法器；主存地址寄存器；磁盘外设：先行进位链；移位器；通用寄存器；中断字寄存器。见下表，“J”为透明性概念指令地址寄存器，X,指令缓冲器，V,时标发生器，V,条件码寄存器，X,乘法器，J,主存地址寄存器，V,磁盘，X,先行进位链，J,移位器，通用寄存器，X,中断字寄存器，X,1.9见下表，“J”表示都透明，“应”表示仅对应用程序员透明，“义”表示都不透明数据通路宽度，虚拟存储器，应，Cache存储器，V,程序状态字，X,“启动I/O”指令，应，“执行”指令，X,指令缓冲寄存器，V,1.12如果某一计算任务用向量方式求解比用标量方式求解要快20倍，称可用向量方式求解部分所花费时间占总的时间的百分比为可向量化百分比。请画出加速比与可向量化比例两者关系的曲线。

解：可向量化百分比为Fe,Se=20,根据Amdahl定律S=生= 1 1.13在题1.12中，为达到加速比2,可向量化的百分比应为多少？S=——1——=2则可向量化的百分比Fe=O.5261.14在题1.12中，为获得采用向量方式最大加速比的半值（即10）时，所需可向量化的百分比为多少。S”= =10“ 191-—Fe20,则可向量化的百分比Fe=O.9471.15在题1.12中，如果某程序可向量化部分为70%,硬件设计组认为可以通过加大工程投资，使向量处理速度加倍来进一步增加性能；而编译程序编写组认为只需设法增加向量工作方式的百分比就同样可使性能得到相同的提高，问：此时需使可向量化成分再增加多少百分比就可实现。你认为上述硬、软件两种方法中，哪一种方法更好？(1)用硬件组方法，已知Se=2X20=40,Fe=0.7解出Sn=40/12.7=3.1496(2)用软件组方法，已知Se=20,得到硬件组方法的相同性能Sn=40/12.7解出Fe=27.3/38*0.7184(3)结论：软件组方法更好。因为硬件组需要将Se再提高100%(20—40),而软件组只需将Fe再提高1.84%(0.7-0.7184)«1.16某计算机的高速小容量存储器能存储2000条指令。假设10%的指令承担了90%的指令访问且对这10%的指令的使用是均匀的(即其中每条指令的执行时间相同)。如果要执行的某程序共有50000条指令且已知其中的10%是频繁使用的，则当该计算机执行该程序时，在高速小容量存储器中能访问到的指令会占多少百分比？解：对该应用程序来说，在9。％的时间里，只有50000*10%=5000条指令在运行，其他的45000条指令的平均运行次数很少，因此，可以假设对它们来说，Cache总是缺失的.对频繁访问的这10%的指令，假设它们访问均匀，这样，Cache的行为便可以认为是均匀覆盖了这些指令.所以，10%的指令承担了90%的指令访问，指令访问次数(50000*10%)/90%

命中次数2000Cache的命中率为：H=2000/[(50000*10%)/90%]=0.361.17假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的概率为90%,则采用Cache后，能使整个存储系统获得多高的加速比？解：S“=S“=ToS= ? =—«3.57"「0.9+空L451.18设计指令存储器有两种不同方案：一是采用价格较贵的高速存储器芯片，另一是采用价格便宜的低速存储芯片。采用后一方案时，用同样的经费可使存储器总线带宽加倍，从而每隔2个时钟周期就可取出2条指令（每条指令为单字长32位）：而采用前一方案时，每个时钟周期存储器总线仅取出1条单字长指令。由于访存空间局部性原理，当取出2个指令字时，通常这2个指令字都要使用，但仍有25%的时钟周期中，取出的2个指令字中仅有1个指令字是有用的。试问采用这两种实现方案所构成的存储器带宽为多少？解：方案一：采用高速缓冲存储器，使每个时钟周期存储器总线取出1条指令，则存储器带宽=1字/时钟周期=32位/时钟周期方案二：使存储器总线带宽加倍，从而每隔2个时钟周期就可取出2条指令（每条指令为单字长32位），但仍有25%的时钟周期中，取出的2个指令字中仅有1个指令字是有用的，则实际带宽=空出土型史=0.875字/时钟周期1.19用一台40MHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下指令类型 指令数 时钟周期数整数运算 45000 1数据传送 32000 2浮点 15000 2控制传送 8000 2求有效CPI、MIPS速率和程序的执行时间。/=40xl06 /C=Z〃=45000+32000+15000+8000=100000/=!有效"/=ECPIili/IC=1=]1OOOOO45000x1+32000x2+15000x2+有效"/=ECPIili/IC=1=]1OOOOO〃心=3=捺得=瑞质取IC105M/PSxlOIC105M/PSxlO640L55X=0.003875（秒）T=CPIICr=l.55xlOOOOOx =0.003875s40x1061.20某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个已知混合程序。假定每次存储器存取为1周期延迟、试问：(a)此计算机的有效CPI是多少？(b)假定将处理机的时钟提高到30MHz,但存储器子系统速率不变。这样，每次存储器存取需要两个时钟周期。如果30%指令每条只需要一次存储存取，而另外5%每条需要两次存储存取，还假定已知混合程序的指令数不变，并与原工作站兼容，试求改进后的处理机性能。解：解f=15MHz,MIPS=10,每次存取时间为2个时钟周期有效CP/=——*-；=*'I。：=1.5MIPSx10610xl06(b)f=30M”z,存储系统的速率不变，但每次存取为2个时钟周期30%指令每条只需要一次存储存取，改进前共需1周期，改进后共需2周期而另外5%每条需要两次存储存取，改进前共需2周期，改进后共需4周期CP/新=€77原+30%x(2—1)+5%X(4-2)=1.9MIP._f_3OxlO6/W/io— —1 T--10.oCP/X1061.9X106o"i/。乂°尸/原、丁原1.5x30\n=—= = =i.jo7^^cxCPI新xt新1.9x151.21假设在一台40MHz处理机上运行200000条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：指令类型CPI指令混合比算术和逻辑160%高速缓存命中的加载/存储218%转移412%高速缓存缺失的存储器访问810%(a)计算在单处理机上用上述跟踪数据运行程序的平均CPI(b)根据(a)所得CPI,计算相应的MIPS速率。解：CP1=2(CPI产勿(1)CP/=1x0.6+2x0.18+4x0.12+8x0.1=2.24(2)MIPS=CP/x10(2)MIPS=CP/x10640x1()62.24x106a17.861.24假定你是一个计算机设计者，对高级语言结构的使用研究表明，过程调用是最常用的操作之一。你已设想了一个优化设计方案，它能减少过程调用和返回所需的取/存指令次数。为了进行验证，对未加优化和已优化的方案进行实验测试，假定所使用的是相同的优化编译器。实验测得的结果如下：(1)未优化的时钟周期比优化的快5%；(2)未优化方案中的取/存指令数占总指令数的30%；(3)优化方案中的取/存指令数比未优化的少1/3,对于其他指令，两种方案的动态执行数没有变化：(4)所有指令，包括取/存指令，均只需要1个时钟周期。要求你定量地判断，哪一种设计方案的计算机工作速度更快。解：记新方案时钟周期为Tc,已知CPI=CPL=1原时间=CPIXICX0.95Tc=0.95ICXTc新时间=(0.3X2/3+0.7)XICXTc=0.9ICXTc二者比较，新时间较短。1.A1某台计算机只有Load/Store指令能对存储器进行读/写操作，其它指令只对寄存器进行操作。根据程序跟踪实验结果，已知每种指令所占的比例及CPI数如下：指令类型指令所占比例CPI算逻指令43%1Load指令21%2Store指令12%2转移指令24%2(1)求上述情况下的平均CPI。(2)假设程序有M条指令组成。算逻运算中25%的指令的两个操作数中的一个已在寄存器中,另一个必须在算逻指令执行前用Load指令从存储器取到寄存器。因此有人建议增加另一种算逻指令，其特点是一个操作数取自寄存器，另一个操作数取自存储器，即寄存器％存储器类型，假设这种指令的CPI等于2。同时，转移指令的CPI变为3。求新指令系统的平均CPIo解：CPI10=(0.43X1+0.21X2+0.12X2+0.24X2)=1.57原算逻指令中的25%变成了寄存器％存储器型指令，所以算逻指令(寄存器%寄存器型)少了(0.25X0.43)M条，Load指令少了(0.25X0.43)M条，而(0.25X0.43)M条的新指令为寄存器%存储器型指令。指令总数少了(0.25X43%)M条。设执行算逻指令(寄存器％寄存器型)、Load指令、算逻指令(寄存器％存储器型)、Store指令和转移指令的周期总数分别为Cl,C2,C3,C4,C5,所以：Cl=(0.43-(0.25*0.43))MX1=0.3225MC2=(0.21-(0.25X0.43))MX2=0.205MC3=(0.25X0.43)MX2=0.215MC4=0.12MX2=0.24MC5=0.24X3M=0.72M新指令总数N=(1-(0.25X0.43))M=0.892CPI新=(C1+C2+C3+C4+C5)/N=1.7025M/0.8925M=1.9081.A2计算机系统中有三个部件可以改进，这三个部件的部件加速比如下：部件加速比1=30部件加速比2=20部件加速比3=10(1)如果部件1和部件2的可改进比例均为30%,那么当部件3的可改进比例为多少时，系统加速比才可以达到10?(2)如果三个部件的可改进比例分别为30%、30%和20%,三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？(3)如果相对某个测试程序三个部件的可改进比例分别为20%,20%和70%,要达到最好改进效果，仅对一个部件改进时，要选择哪个部件？如果允许改进两个部件，又如何选择？1.A3在某个程序中，简单指令占80%,复杂指令占20%,在CISC机中简单指令执行需4个机器周期，复杂指令执行需8个机器周期。RISC机中简单指令执行只需1个机器周期，而复杂指令要通过一串指令来实现。假定复杂指令平均需要14条简单指令，即需要14个周期，若该程序中需要执行的总指令数为1000000,Tc为100ns,那么RISC机需执行的指令数为多少？CISC和RISC机的CPU时间分别为多少?RISC机对CISC的加速比为多少？第二章(P124)忽略P124倒1行〜P125第8行文字，以简化题意)已知2种浮点数，求性能指标。此题关键是分析阶码、尾数各自的最大值、最小值。原图为数据在内存中的格式，阶码的小数点在其右端，尾数的小数点在其左端，遵守规格化要求。由于尾数均为原码，原码的绝对值与符号位无关，所以最大正数与最小负数的绝对值相同，可用“土最大绝对值”回答；最小正数与最大负数的绝对值相同，可用“土最小绝对值”回答。第1小问中，阶码全部位数为8,作无符号数看待真值为。〜255,作移T27码看待真值为T27〜+128；尾数(不计符号位)有23位小数，另加1位整数隐藏位，所以尾数绝对值为1.0〜2.0-2”，有效位数p=24；第2小问中，阶码全部位数为11,作无符号数看待真值为。〜2047,作移T023码看待真值为-1023〜+1024；尾数(不计符号位)有52位小数，另加1位整数隐藏位，所以尾数绝对值为1.0~2.0-2划,有效位数p=53.最大绝对值为最大阶码与最大尾数绝对值的组合，最小绝对值为最小阶码与最小尾数绝对值的组合。代入相关公式后得最终结果如下表。32位64位士最大绝对值±(1-2%)•2您±(1-2-53)•21025土最小绝对值±2-127I2T023表数精度52a2W表数效率n100%100%2.5r.=2,n=2,p=24(隐藏最高位)，q=7。=1.7X1038,-|N|oi„=-1.47X10-396W5.96X10卡-10-722,n=100%2.60.2=0.333333HX160设阶码为移-63码(即-吸+l,原题未指明)0.2=0.110011001100110011001101BX2z（其中最高有效位需隐藏）1位&位 23位阶码为移T27码（即-2，+1）|o|01111101|10011001100110011001101|（2）符号位不变，（阶码-63）X4+127；尾数左规，除去最高位；（3）符号位不变，（阶码-127）/4+63；尾数补最高位，按除法余数右移若干位，左补0。2.13已知10条指令使用频度，求3种编码方法的平均码长与信息冗余量。（1）此问中的“最优Huffman编码法”实际是指码长下限，即信源的平均信息量——端，代公式得11=2.9566。（2）Huffman编码性能如下表；（3）2/8扩展编码是8/64/512法的变种，第一组2条指令，码长为2（1位扩展标志，1位编码），第二组8条指令，码长为4（1位扩展标志，与第一组区别，加3位编码），编码性能如下表；（4）3/7扩展编码是15/15/15法的变种，第一组3条指令，码长为2（共有4种组合，其中3种组合分别代表3条指令，留1种组合作为扩展前缀标志），第二组7条指令，码长为5（2位固定的前缀扩展标志，与第一组区别，加3位编码，只用其中7种组合），编码性能如下表Huffman编码2/8扩展编码3/7扩展编码平均码长二2.993.13.2信息冗余量R1.10%4.61%7.59%2.14一台模型机共有7条指令，各指令的使用频率分别为35%,25%,20%,10%,5%,3%和2%,有8个通用数据寄存器，2个变址寄存器。(1)要求操作码的平均长度最短，请设计操作码的编码，并计算所设计操作码的平均长度。(2)设计8字长的寄存器-寄存器型指令3条，16位字长的寄存器-存储器型变址寻址方式指令4条，变址范围不小于±127。请设计指令格式，并给出各字段的长度和操作码的编码。解：(1)要使得到的操作码长度最短，应采用Huffman编码，构造Huffman树如下：1.00由此可以得到7条指令的编码分别如下:指令出现的频率编码135%00225%01320%10410%11055%111063%1111072%11111这样，采用Huffman编码法得到的操作码的平均长度为：H=2X(0.35+0.25+0.20)+3X0.10+4X0.05+5X(0.03+0.02)=1.6+0.3+0.2+0.25=2.35设计8位字长的寄存器.寄存器型变址寻址方式指令如下，因为只有8个通用寄存器，所以寄存器地址需3位，操作码只有两位，设计格式如下：7 6 5 3 2 0操作码OP源寄存器R1目的寄存器R2三条指令的操作码分别为00,01,10设计16位字长的寄存器-存储器型变址寻址方式指令如下:15 1211 9 8 7 0操作码OP函甬寄存器|变址寄存器 偏移地忆|四条指令的操作码分别为1100,1101,1110,11112.15某处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令三类，并假设每个地址字段的长度均为6位。(1)如果双地址指令有15条，单地址指令和零地址指令的条数基本相同，问单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。(2)如果要求三类指令的比例大致为1：9：9,问双地址指令、单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。解：⑴15条/63条/64条14条/126条/128条(D根据指令地址的数量来决定各种指令在指令空间上的分布：如果我们按照从小到大的顺序分配操作码，这样，按照指令数值从小到大的顺序，分别为双地址指令、单地址指令和零地址指令。其次可以根据指令的条数来大致的估计操作码的长度：双指令15条，需要4位操作码来区分，剩下的12位操作码平均分给单地址和零地址指令,每种指令可以用6位操作码来区分，这样，各指令的条数为：双地址指令15条，操作码：00001110；单地址指令2〜6-1=63条,操作码：1111000000~1111111110；零地址指令64条，操作码：1111111111000000^1111111111111111.(2)与上面的分析相同，可以得出答案：双地址指令14条，操作码：OOOO'llOl；单地址指令2~6x2-2=126条，1110000000"1110111110,1111OOOOOO'llll111110；零地址指令128条1110111111000000'1110111111111111,1111111111000000^1111111111111111(2)B双地址指令同上，14条，操作码：00001101；单地址指令64+62=126条，64条单地址指令操作码1110000000^111011111162条单地址指令操作码1111000000^1111111101零地址指令128条1111111110000000^1110111110111111,1111111111000000^11111111111111112.3第三章(P202)例3.1假设Tz=5T”在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。解：_7\_7i_ 1当H=0.9时，e.=l/(0.94-5(1-0.9))=0.72当H=0.99时，e2=l/(0.99+5(1-0.99))=0.96・提高存储系统速度的两条途径：一是提高命中率H二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)，因此，主要依靠提高命中率例3.2在虚拟存储系统中，两级存储器的速度相差特别悬殊12=10町1。如果要使访问效率e=0.9,问需要有多高的命中率？解：0.9= 5 70.911+90000(1-H)=l89999.1H=89999计算得H=0.999998888877777…-0.999999例3.3在一个Cache存储系统中，当Cache的块大小为一个字时，命中率为H=0.8；假设数据的重复利用率为5,计算Cache的块大小为4个字时，Cache存储系统的命中率是多少？假设T2=5Ti,分别计算访问效率。解：n=4X5=20,采用预取技术之后，命中率提高到：wH+n-\ 0.8+20-1n 20Cache的块大小为一个字时，H=0.8,访问效率为：&=1/(0.8+5(1-0.8))=0.55...Cache的块大小为4个字时，H=0.99,访问效率为：e2=1/(0.99+5(1-0.99))=0.96例3.4在一个虚拟存储系统中，T2=105Ti,原来的命中率只有0.8,现采用预取技术，访问磁盘存储器的数据块大小为4K字，如果要求访问效率不低于0.9,计算数据在主存储器中的重复利用率至少为多少？解：假设数据在主存储器中的重复利用率为m,根据前面的给出关系：1 ,0.8+4096/zz—1U.9= 7 9H—H'+(l-//')-io 4096m解这个方程组，得到m=44,即数据在主存储器中的重复利用率至少为44次。例3.6Star-100巨型机存储系统采用并行和交叉相结合的方式工作，有32个存储体低位交叉,每次并行读写512位，存储周期为1.28um(磁心存储器)，处理机字长32位，计算它的频带宽度Bm和峰值速度T»解：因为：n=32,w=512,Tm=1280ns,Bm=nw/tm=32x512b/1280ns=12.8Gb/s=1.6GB/s=400MW/sT=2.5ns,与Tm相比，峰值速度提高512倍。例3.8一个程序共有5个页面组成，分别为P1〜P5。程序执行过程中的页地址流（即程序执行中依次用到的页面）如下：Pl,P2,Pl,P5,P5,Pl,P3,P4,P3,P4假设分配给这个程序的主存储器共有3个页面。给出FIFO.LRU和OPT三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。时间t12315678910实际命中次数页地址流P1P2P1P5P4P1P3P4P2P4先进先出算法（FIFO算法）1111*-144*4*222次2222*1111*1555*3333*调入调入命中调入替换替换替换命中替换替换最久没有使用算法（LRU算法）11111111*224次222*444*44455*5*333*3*调入调入命中调入替换命中替换命中替换命中111111*3*3*33

最优替换算法（OPT算法）2222*222225次5*-144414调入调入命中调入替换命中替换命中命中命中三种页面替换算法对同一个页地址流的调度过程例3.9一个循环程序，依次使用Pl，P2,P3,P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。时间t12345678实际命中次数页地址流P1P2P3P4P1P2P3P4先进先出算法（FIFO算法）111*444*330次222*111*4333*222*调入调入调入替换替换替换替换替换最久没有使用算法111*444*33222*111*1

（LRU算法）333*222*0次调入调入调入替换替换替换替换替换最优替换算法（OPT算法）11111*1113次22222*3*33*4*4444*调入调入调入替换命中命中替换命中页面调度中的颠簸现象3.1由三个访问速度、存储容量和每位价格都不相同的存储器构成一个存储体系。其中，Mi靠近CPU,回答下列问题：Mi/ 4m2M3(Ti.Si.Ci)(t2,s2,c2)■■(T3.S3,C3)（1）写出这个三级存储体系的等效访问时间T,等效存储容量S和等效每位价格C的表达式。(2)在什么条件下，整个存储体系的每位价格接近于C3?3.3直接代公式计算存储层次性能指标。(1)74ns,38ns,23.6ns(2)0.258,0.315,0.424(3)T256K<T128K<T64Kc256K>C128K>c64K(4)19.092,11.97,10.0064«答案是256K方案最优。3.5已知瓦；=上学也，其中g=0.1依题意有用二=Ug)”：>^7+0.2=Ug匚+0.2g g整理得0.9n\0.2,解出生丝a15.28,向下取整，得151g0.9按另一种题意理解是向上取整，得16,也对。3.7方式1：16个模块高位交叉31 0模块的片内地址 模块号方式3：16个模块低位交叉模块的片内地址方式4：2路高位交叉8路低位交叉16个存储模块每8个组成一个大的模块:模块号模块的片内地址模块号模块的片内地址方式5：4路高位交叉4路低位交叉16个存储模块每4个组成一个大的模块:31模块号模块的片内地址31模块号模块的片内地址方式6：4路并行访问4路低位交叉31 0模块的片内地址 模块号输出选择(1)这几种存储器都能够并行工作，因此可以提高频带宽度。总的来说，并行访问存储器的优点是实现简单、容易，缺点是访问冲突大；高位交叉访问存储器的优点是扩充方便，缺点是访问效率不高：低位交叉访问存储器可以用分时的方法来提高速度，但扩充不方便。(2)各种存储器的频带宽度和他们的工作频率有关，在不考虑冲突的情况下，如果有足够多的独立控制电路和寄存器，那么，他们的频带宽度是相同的。(3)存储器的逻辑示意图略。注意，并行访问存储器和低位交叉访问存储器很相象，只不过，并行访问存储器使用存储模块号(存储体号)来对已经输出的结果进行选择，而低位交叉访问存储器则用来生成对存储模块(存储体)的片选信号，他通过流水的方式来提高访问的速度。3.14在页式虚拟存储器中，一个程序由P1〜P5共5个虚页组成。在程序执行过程中依次访问到的页面如下：P2,P3,P2,Pl,P5,P2,P4,P5,P3,P2,P5,P2假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LRU和OPT三种替换算法对这三页主存进行调度。画出主存页面调入、替换和命中的情况表.统计三种页面替换算法的页命中率。3.15（1）在分配的主存页面数目大于等于5的情况下，这时，除了第一次调入不命中，以后的访问均命中，可以达到最高的页面命中率：实际命中的次数为7次，所以可能达到的最高页面命中率为：7"=——=0.583312（2）由于在页面数大于等于5的情况下，肯定可以达到最高命中率，所以我们来看页面数小于5时能否达到该命中率：分配的主存页面数等于4时，调度过程如下：LFU算法44441555*55333:222i周调调调命中调11111命中7次55:5553:33:3:22222命中命中命中命中命中命中此时也可以达到最高命中率；分配的主存页面等于3时，调度过程如下:LFU算法444*2255555*3331*调调调调命调入入入入中入3333命中3次:22:1111555调调命调调命入入中入入中此时不能达到最高命中率。所以至少应该分配4个主存页面。（3）我们假设程序每次只访问一个存储单元，这样，对每一个特定页面的访问过程可以描述如下：因为第一次总是不命中的，而平均起来，随后的1023次总是命中的，然后再次被调出主存,并再次重复先前的过程。所以访问存储单元的命中率为：10237/=-^=0.9991024欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“表示命中。p=453251 32351 3命中次数453251 32351 345325 13235 14532 51123 5443 25512 24 44444 4n=l0n=2J1n=3JJV3n=4JJVVJJJ7n=5JJJJVJJ7(1)^=7/12^58.3%(2)n=4

(3)当1次页面访问代表连续1024次该页内存储单元访问时，后1023次单元访问肯定是命中的，而第1次单元访问的命中情况与这1次页面访问的命中情况相同。根据上图中最高命中情况，共有7次页命中(折算为7X1024次单元命中)，5次页不命中(折算为5X1023次单元命中，也可写为5X1024-5),单元访问总次数为12X1024,故有：Hcen=(12X1024-5)/(12X1024)=12283/12288=99.96%3.15A加1题一个二级存储层次，采用全相联映象和最久没有使用算法，实存共5页，为2道程序分享，页地址流分别如下P)=12341321P2=12342233试作2试作2个实存分配方案,(1)命中率相同；(2)命中次数之和最大。分别使2道程序满足解：分别为2道程序作“堆栈模拟图”，其中“J”表示命中。P.=I2 3 4 1 3 2I命中次数N⑴12341321123413212341312244JP2=12342233命中次数N⑵12342233123442212334411111VVVVV将两图结果综合，得到4个分配方案的命中率情况表如下Bi12Bi1234Md0024Ih4321N⑵4422N⑴+N⑵4446N(1)+N(2).■ No、、i+4 2+3一;较4+1结论如下(1)命中率相同的方案是ni=3而n2=2；(2)命中次数之和最大的方案是ni=4而nz=1。3.19(1)主存共有2个区，每个区2组，每个组2块，每块16个字节，如果按字节寻址，那么主存需要7位，如下图所示：组号(1位)组号(1位)区号(1位)块号(1位) 块内地址(4位)(2)Cache地址需要6位，如下图所示：组号(1位)块号(1位)块内地址(4位)中(3)(4)(6)(8)问虚组。虚组。虚存0(4)通过作“实存状况图”模拟各虚块的调度情况，可获得Cache的块地址流序列。P=624146304573COClC26 6* 6* 6* 6* 6 6* 6* 6* 6* 7 7*入入入入中中替替中替C=230102310123此间最容易出错的地方是忽略“组相联”地址约束，将虚页装错实组。另外没有及时标注“*”号也容易导致淘汰对象错误。(6)11=4/12-33%(8)做法同3.15题(3)问，Heeii=(12X16-8)/(12X16)=«95.8%2.4第四章(P250)4.5已知中断服务次序为3-2-4-l,o(1)中断屏蔽字表如下图；(2)中断过程示意图如右图。D1D2D3D4D10111D20010D30000D40110时间中断请求主程序1级2级3级4级D1,D1,D3.4.8(Df=2Xl()5字节/秒，t=5us(2)Ts+Td=5us,通道时间图如下。作图时注意：至少要画到最慢设备的第二次请求出现,

才能确定是否丢失数据(因为响应优先级低的设备较易丢失数据)。设优备先号级(3)5,160,20,40；(4)D2丢失第一次请求的数据;(5)参见P245。2.5第五章(P343)例5.1一个采用先行控制方式的处理机，指令分析器分析一条指令用一个周期，到主存储器中取一条指令装入先行指令缓冲栈平均要用4个周期。如果这种指令的平均长度Li=9,即90%的指令是执行时间短的指令。计算先行指令缓冲栈的缓冲深度为：Di= = =/t2 4例5.2用一条4段浮点加法器流水线求8个浮点数的和：Z=A+B+C+D+E+F+G+H解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]空间结果A+BC+DE+Fg+H空间结果A+BC+DE+Fg+HA+B+C+DE+F+G+H用一条4段浮点加法器流水线求8个数之和的流水线时空图7个浮点加法共用了15个时钟周期。n7 1流水线的吞吐率为：TP=—= =0-47—Tk15-A? Ar流水线的加速比为：S二流水线的效率为：E=-21^=1.87Tk15-AfTo4x7-A/八)r = =0-47k-Tk4x15-Ar例5.3一条有4个功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下:间功能应1234567SiXXS2XXS3XXS4X(1)写出流水线的禁止向量和初始冲突向量。(2)画出调度流水线的状态图。(3)求流水线的最小启动循环和最小平均启动距离(4)求平均启动距离最小的恒定循环。解:禁止向量为：（2,4,6）初始冲突向量：101010初始冲突向量逻辑右移2、4、6位时，不作任何处理,逻辑右移1、3、5和大于等于7时，要进行处理。初始冲突向量右移1位之后：010101vl01010=llllll (0)-1->(1)初始冲突向量右移3位之后：000101vl01010=101111 (0)-3->(2)初始冲突向量右移5位之后：000001vl01010=101011 (0)-5->(3)初始冲突向量右移7位或大于7位后：还原到它本身。 (0)-7->(0)中间冲突向量101111 右移5位之后：000001vl01010=101011 (2)-5->(3)中间冲突向量101011 右移3位之后：000101vl01010=101111 (3)-3->(2)中间冲突向量101011 右移5位之后：000003101010=101011 (3)-5->(3)101011非线性流水线的状态图预约表与状态图是唯一对应，但不同的预约表也可能有相同的状态图・简单循环：状态图中各种冲突向量只经过一次的启动循环。简单循环的个数一般是有限的。由简单循环可以计算出平均启动距离。简单循环平均启动距离(1,7)4(3,7)5(5,7)6(3,5,7)5(5,3,7)5(3,5)4(5)5

(7) 7最小的启动循环为（1,7）或（3,5）。其平均启动距离为4平均启动距离最小的恒定循环为5。最小启动循环(1,7)的流水线工作状态功蔽工123456789101112131415・・・S.XiX2XiX2X3X4X3•••S2X1X2XiX2X3X4X3X4・・・S3x,X2X,X2X3X4X3x<・・•S4X1X2X3x4・・・< 启动周期 >< 重复启动周期 >恒定启动循环(5)的流水线工作状态功自济'123456789101112131415…s,XiX。X.X3X2•・・SzXiXiX2X2X3•••S3XiX1先X2X3・・・S4XiX2x“・・・ 启动周期 )w一重复启动周期一>采用预留调度算法S„S2、S3对应的行有2个“X”，因此，最小平均启动距离为2。以恒定循环（2）作为最小启动循环。检查每一行中与第1个“义”的距离为2的倍数的位置都要预留出来。S3行的第2个“X”从周期5延迟到周期6。为此，S2行的第2个"X”也要向后延迟一个周期，从周期6延迟到周期7；S,行的第2个“X”也要向后延迟一个周期，从周期7延迟到周期8。实际上，只要在S*的输出端到S3的输入端中间插入一个非计算延迟Di，如下表和下图所示。注：①表示由Di延迟一个时钟周期

例5.A1某单功能非线性流水线的预约表如下图所示。要求：(1)写出其禁止表F和冲突向量C。(2)画出该流水线状态图，确定其最佳调度方案以及最小平均流水速率(3)计算当按此流水线调度方案执行8个任务所需的时间。(4)计算此流水线在执行8个任务时的吞吐率、加速比和利用率。答：⑴F={2,4,6)C=101010(2)流水线状态图如下:最优调度方案为(1,7),平均间隔4个周期或(3,5),平均间隔4个周期⑶时间为7+1+7+1+7+1+7+1=32或7+3+5+3+5+3+5+3=34调度方案为(1,7)输入间隔0,17,1,7,1,7,1清空时间7时间为(1+7+14-7+1+7+1)+7=32或调度方案为(3,5)输入间隔0,3,535,3,5,3清空时间7(3+5+3+5+3+5+3)+7=34(4)吞吐率=8/32=25%力口速比=(7*8)/32=7/4=1.75利用率=(7*8)/(4*32)=0.43755.3假设一条指令的执行过程分为“取指令”、"分析”和"执行”三段，每一段的执行时间分别为△t、2At和3At。在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。（1）顺序执行方式。⑵仅“取指令”和“执行”重叠。（3）先行控制方式。［解答］取指，分析，执行I取指;分析，执行I取指;分析，执行顺序方式工作的时间关系图取指，分析，执存取指，分析，前方取指:分析，执行取指:分析,双方“执行”和“取指”重叠方式工作的时间关系图顺序方式：执行n条指令的时间=nX(t取指+t分析+t执行)“执行”和“取指”重叠：执行n条指令的时间=t取指+nXt分析+(n-1)XMAX{t取指，t执行}+t执行取指，分析，短行取指，分析，筋方取指，分析，执存取指，分析1双方执行”、“取指”和“分析”重叠方式工作的时间关系图取指，分析: 执行一iliilli^JIlli Hili丽一莉一执行一先行控制方式工作的时间关系图“执行”、"分析"和''取指"重叠：执行n条指令的时间=t取指+MAX{t取指，t分析}+(n-2)XMAX{t取指，t分析，t执行}+MAX{t分析，t执行}+t执行先行控制：执行n条指令的时间=t取指+t分析+nXt执行(1)顺序执行需要的时间如下：7=(At+2At+3At)xn=6nAt

(2)取指令和执行重叠，即一次重叠执行方式，我们假设第n+1条指令的取指令和第n条指令的执行同时结束，那么所需要的时间为：T=A/+(24+3Af)xn=5n\t+Af(3)采用先行控制以后：T=4+24+3&x〃=3〃zV+345.6在一台单流水线多操作部件上执行下面的程序，取指令、指令译码各需要一个时钟周期，MOVE、ADD和MUL操作各需要2个、3个、和4个时钟周期。每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k：k+1：k+2：中。k：k+1：k+2：各时MOVEMULADD就程序本身而言,Ro;R?，RiR2，R3Ri-(Ro);Ro*-(R2)X(Ri)Ro—(Rz)+(R3)可能有哪几种数据相关？在程序实际执行过程中，有哪几种数据相关会引起流水线停顿？画出指令执行过程的流水线时空图，并计算执行完这三条指令共使用了多少钟周期？答：(1)K与K+1：先写后读相关K+1与K+2：写写相关(2) 由流水线时空图看，K与K+1：先写后读相关在第4时钟周期会引起流水线停顿，

而K+1与K+2：写写相关在第8时钟周期会引起流水线停顿。IFIDRREXEXWB*IFIDRR*EXEXEXWBIFIDRREXWB123456789(3)由流水线时空图看，共插入了3个时钟周期的停顿，执行完这三条指令共使用了11个时钟周期。IFIDidleidleRREXEXidleWBIFIDidleidleRREXEXEXWBIFIDRREXWB1234567891011一条线性流水线有4个功能段组成，每个功能段的延迟时间都相等，都为At。开始5个At,每间隔一个At向流水线输入一个任务，然后停顿2个At,如此重复。求流水线的实际吞吐率、加速比和效率。［解答］流水线的时空图如下：我们可以看出，在(lln+1)At的时间内，可以输出5n个结果，如果指令的序列足够长(n一8),并且指令间不存在相关，那么，吞吐率可以认为满足：Tn== - =5(〃-8)加(ll+l/n)ArHAr加速比为:20=”…)加速比为:20=”…)11从上面的时空图很容易看出，效率为：rTo20〃加 5 5kxTk4x(ll〃+lW11+1/n11用一条5个功能段的浮点加法器流水线计算101=1每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。［解答］首先需要考虑的是，10个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：9次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R,源操作数寄存器称为A,最后结果寄存器称为F,并假设源操作数已经在寄存器中，则指令如下：II： RI-A1+A212： R2-A3+A413： R3-A5+A614： R4-A7+A815： R5-A9+A1016： R6-R1+R217： R7-R3+R418： R8-R5+R619： F-R7+R8这并不是唯一可能的计算方法。假设功能段的延迟为At。时空图如下，图中的数字是指令号。整个计算过程需要21At,所以吞吐率为:Tp整个计算过程需要21At,所以吞吐率为:Tp=9 321Ar-7Ar_9x5Ar3= 21Ar加速比为:45=—=2.142921效率为:EJ一9x5加=3kxTk5x21A/7一条线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输入端与输出端之间有直接数据通路，而且设置有足够的缓冲寄存器。现在用这条流水线计算：尸=5（小8）1-1画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。为了取得较高的速度，我们需要一次将乘法作完，设源操作数存放在寄存器A、B中，中间结果存放在寄存器R中，最后结果存放在寄存器F中，则执行的指令序列如下所示：II： R1*-A1*B112： R2-A2*B213： R3-A3*B314： R4-A4*B415： R5-A5*B516： R6-A6*B6

17：R7-R1+R218：R8-R3+R419：R9-R5+R6110：R10-R7+R8Ill：F-R9+R10时空图（不完全）如下，图中的这并不是唯一可能的计算方法。假设功能段的延迟为数字是指令号。时空图（不完全）如下，图中的整个计算过程需要22At,所以吞吐率为:功能段5功能段整个计算过程需要22At,所以吞吐率为:功能段5功能段4功能段3功能段2功能段17891899Tp=1122AZ2A/加速比为:。Ux4ArcS= =222Ar效率为:E_To_11x4Ar_1kxTk6x22Ar3为了缩短运算时间，首先应考虑“最少切换算法”，即先执行完所有乘法（任务编号1-6）再执行加法（任务编号7T1）,其次在加法中采用“最少相关算法”（即二叉树算法）。t己cfAiXBi,,C6=AeXB6＞下图（a）是加法的计算顺序二叉树，注意任务t己cfAiXBi,一级最早完成的任务7和8的结果，如果用任务9的结果则要推迟1拍启动，使总时间增加1拍。(a) (b)(a) (b)根据时空图(b)得TP=U/(22At)=1/(2At)S=(6X4At+5X4At)/(22At)=2E=(6X4At+5X4At)/(6X22At)=1/35.10一条有3个功能段的流水线如图，每个功能段的延迟时间都相等，为。功能段S2的输出返回到它自己的输入端循环一次。(1)如果每隔一个at向流水线输入端连续输入新任务，问这条流水线会发生什么情况？求这条流水线能够正常工作的最大吞吐率。加速比和效率？有什么办法能够提高这条流水线的吞吐率？画出新的流水线。5.11一条4个功能段的非线性流水线，每个功能段的延迟时间都相等，都为20ns,它的预约表如下：0D01234567S1XXS2XXS3XS4XX(1)写出流水线的禁止向量F和初始冲突向量C,(2)画出调度流水线的状态图。(3)求流水线的最小启动循环和最小平均启动距离。(4)求平均启动距离最小的恒定循环。(5)求流水线的最大吞吐率。(1)照最小启动循环连续输入10个任务，求流水线的实际吞吐率(2)画出该流水线各功能段之间的连接图。答：解：(1)禁止向量F=(2,4,6)初始冲突向量C=(101010)(2)状态图t—)5(3)简单循环平均启动距离TOC\o"1-5"\h\z(1. 7) 4(3, 7) 5(3, 5, 7) 5(5,7) 6(5) 5(7) 7最小平均启动距离4最小启动循环(1,7)⑷平均启动距离最小的恒循环⑸(5)流水线的最大吞吐率假设用此流水线完成N个任务(N为偶数)：TPMAX=N/(N/2*12*AT)=1/(6AT)其中：N/2*12表示每执行2个任务需要12个4T时间，平均每6个AT完成一个任务。假设用此流水线完成N个任务(N为奇数)：TPMAX=N/[((N-1)/2*12+5)*AT]其中：(N-l)/2*12表示每执行2个任务需要12个4T时间，5为最后一个任务多执行的周期数。(1)禁止向量：(2,4,6),初始冲突向量：(101010).(2)状态图

(3)简单循环(1,7)(3,7)(3,5,7)(5,7)(5)(7)平均启动距离455657平均启动距离455657最小平均启动距离最小启动循环4(1,7)(5)流水线的最大吞吐率假设用此流水线完成N个任务(N为偶数)：TPmax=N/(N/2*12*AT)=1/(6AT)其中：N/2*12表示每执行2个任务需要12个AT时间，平均每6个AT完成一个任务。假设用此流水线完成N个任务(N为奇数)：TPmax=N/[((N-l)/2*12+5)*AT]其中：(N-l)/2*12表示每执行2个任务需要12个AT时间，

5为最后一个任务多执行的周期数。\时7功能能、12345678910II121314151617S1X△X3△3S2XX△△33S3X△3S4XX△△335.12一条3个功能段的非线性流水线及其预约表如图:输入(1)写出流水线的禁止向量和初始冲突向量，并画出调度流水线的状态转换图。(2)求流水线的最小启动循环和最小平均启动距离。(3)通过插入非计算延迟功能段使该流水线达到最优调度，确定该流水线的最佳启动循环及其最小平均启动距离。(4)画出插入非计算延迟功能段后的流水线连接图及其预约表。输出j7间t段铲、t1t2t3t4t5S1XXS2XXS3XX(5)画出插入非计算延迟功能段后的流水线状态转换图。(6)在插入非计算延迟功能段前后，分别计算流水线的最大吞吐率，并计算最大吞吐率改进的百分比。5.15At=10ns=10s秒(1)F={L2,5},C=(100U)(2)状态转移图如下图(a)所示。(3)最小启动循环=(3),最小平均启动距离=3At。(4)插入2个延迟，最小启动循环=(2)，最小平均启动距离=2At(5)新预约表如下图(b)所示。(6)F={1,3,7},C=(1000101),状态转移图如下图(c)所示。(7)插入前TP11M=1/3At=l/30ns,插入后TP^=1/2At=l/20ns,(8)插入前TP=10/33At=l/33ns,插入后TP=10/26At=l/26ns,如下图所示。初态4,6,38ID1010/V0001\11初态3,4SiA2X>20Q■>$3AA&41AAUi►-►U2(t)(a)(a)插入前(b)(b)插入后5.18在下列不同结构的处理机上运行8X8的矩阵乘法C=AXB,计算所需要的最短时间。只计算乘法指令和加法指令的执行时间，不计算取操作数、数据传送和程序控制等指令的执行时间。加法部件和乘法部件的延迟时间都是3个时钟周期，另外，加法指令和乘法指令还要经过一个“取指令”和“指令译码”的时钟周期，每个时钟周期为20ns,C的初始值为“0”。各操作部件的输出端有直接数据通路连接到有关操作部件的输入端，在操作部件的输出端设置有足够容量的缓冲寄存器。(a)处理机内只有一个通用操作部件，采用顺序方式执行指令。(b)单流水线标量处理机，有一条两个功能的静态流水线，流水线每个功能段的延迟时间均为一个时钟周期，加法操作和乘法操作各经过3个功能段。(c)多操作部件处理机，处理机内有独立的乘法部件和加法部件，两个操作部件可以并行工作。只有一个指令流水线，操作部件不采用流水线结构。(d)单流水线标量处理机，处理机内有两条独立的操作流水线，流水线每个功能段的延迟时间均为一个时钟周期。(e)超标量处理机，每个时钟周期同时发射一条乘法指令和一条加法指令，处理机内有两条独立的操作流水线，流水线的每个功能段的延迟时间均为一个时钟周期。(f)超流水线处理机，把一个时钟周期分为两个流水级，加法部件和乘法部件的延迟时间都为6个流水级，每个时钟周期能够分时发射两条指令，即每个流水级能够发射一条指令。(g)超标量超流水线处理机，把一个时钟周期分为两个流水级，加法部件和乘法部件延迟时间都为6个流水级，每个流水级能够同时发射一条乘法指令和一条加法指令。要完成上面的矩阵乘法，我们可以计算需要完成的各种操作的数量(假定A和B都是8X8的矩阵。C语言代码如下：intk;for(inti=0;i<8;i++)for(intj=0;j<8;j++){ sum=0;for(k=0;k<8;k++)sum+=A[i][k]XB[k][j]C[i][j]=sum;需要完成的乘法数目为8X8X8=512次；需要完成的加法数目为8X8X7=448次：下面我们分析处理机的结构会给性能带来什么样的影响。(1)顺序执行时，每个乘法和加法指令都需要5个时钟周期(取指令、指令分析、指令执行)；所以所需要的时间为：7=(512+448)x5x20/iv=96000/iv=96〃zv(2)单流水线标量处理机，采用两功能静态流水线时；因为有足够的缓冲寄存器，所以我们可以首先把所有的乘法计算完，并通过调度使加法流水线不出现停顿，所以所需要的时间为：7=条(一条指令进入流水线+琮法+务1法=[2+(3+512-1)+(3+448-1)]*20心=19320心(3)多操作部件处理机，只有一条指令流水线。由于只有一条指令流水线，所以只能一个时钟周期发射一条指令，我们可以考察加法部件的执行过程，对C矩阵的第一个元素，当乘法部件完成两次计算后，加法部件启动运行7次，然后对其余的元素，加法部件停顿3个时钟周期，然后运行7次。故执行时间为：T=[2+(3x2+3x7)+63x(3+3x7)]x20m-=30820ns(4)单流水线标量处理机，有两条独立的操作流水线；由于只有一条指令流水线，所以只能一个时钟周期发射一条指令，由于存在足够的缓冲寄存器，我们可以通过合适的调度消除数据相关。故执行时间为：T=[2+3+(512-l)+3]x20〃s=1038Ws(5)超标量机，能同时发射一条加法和一条乘法指令，有两条独立的操作流水线。他的执行过程和(3)很相象，乘法流水线一直在运行，而加法流水线因为数据相关而存在停顿。我们可以换个角度，来考察乘法流水线的运行情况。从第3个时钟周期，乘法流水线一直忙碌，在乘法流水线完成所有计算后，加法流水线还需要完成最后一次计算。所以执行时间为：T=[2+3+(512+448)-l]x20ra=19280n.y(6)超流水线处理机，每个时钟周期发射两条指令，加法部件和乘法部件都为6个流水级。事实上相当于将时钟周期变成了10ns,而加法和乘法流水线变成了6级。这样和(4)类似有执行时间为：r=[2+6+(512+448)-l]xl0/?5=9670/w(7)超标量超流水线处理机，一个时钟周期分为两个流水级，加法部件和乘法部件都为6个流水级，每个流水级能同时发射一条加法和一条乘法指令。综合(5)和(6)的分析，我们可以知道，执行时间为：7'=[2+6+(512-l)+6]xlO/w=525Om-5.A1如图给出了一个非线性流水线。若4条指令依次间隔2入进入流水线，求出其实际的吞吐率和效率并画出时空图。如果用加快流水，使流水线每隔2Z\t流出一个结果，应减少哪个流水段本身经过的时间？应减少到多少，流水线方能满足要求？求出此时连续流入4条指令时的实际吞吐率和效率。倍秣一%，—>1——A2—3 42.6第六章(P391)例6.A1有如下3条向量指令。V3—AV2—V0+V1V4<-V2*V3第一、二条指令没有数据相关和功能部件冲突，可以同时开始执行第三条指令与第一、二条指令均存在写读数据相关。数据进入和流出每个功能部件，包括访存都需要1拍时间。浮点加•三种执行方式比较:如果向量长度为N,三条指令采用串行方法执行的时间为：[(1+6+1)+N-1]+[(1+6+1)+N-1]+((1+7+1)+N-1]=3N+22拍如果前两条指令并行执行，第三条指令串行执行，则执行时间为:[(1+6+1)+N-1]+[(1+7+1)+N-1]=2N+15拍如果采用链接技术，则执行时间为：(l+6+l)+(l+7+l)+(N-l)=17+N-l=N+16拍例6.1假设一台向量处理机中功能部件的启动开销为：取数和存数部件为12个时钟周期、乘法部件为7个时钟周期、加法部件为6个时钟周期。先把序列向量操作分成编队，然后计算每个编队的开始时间、获得第一个结果元素的时间和获得最后一个结果元素的时间。LVVI,Rx取向量XMULTSVV2,FO,VI；向量和标量相乘LVV3,Ry取向量丫ADDVV4,V2,V3；加法SVRy,V4?存结果解：第一条指令LV为第一个编队。MULTSV指令和第二条LV指令为第二个编队ADDV指令为第三个编队。SV指令为第四个编队。如果向量长度为n,则每个编队的开始时间、获得第一个结果元素和最后一个结果元素时间如下表所示。编队开始时间第一个结果时间最后一个结果时间1.LV01111+n2.MULTSVLV12+n12+n+1123+2n3.ADDV24+2n24+2n+529+3n4.SV30+3n30+3n+1141+4n如果采用向量链接技术(不考虑访问存储器的冲突)，需要：12+7+6+12+n-l=36+n个周期。・如果考虑向量长度大于向量寄存器长度时，则需要分段开采。向量长度为n的一组向量操作的整个执行时间为：Tn=x(Tloop+Tstart)+nxTchime其中：loop为执行标量代码的开销，Tstan为每个编队的向量启动开销。MVL是向量寄存器的长度。Tloop可以看作是一个常数，Cray1机的Tioop约等于15。例6.2在一台向量处理机上实现A=BXs操作，其中A和B是长度为200的向量，s是一个标量。向量寄存器长度为64。各功能部件的启动时间与上例相同。求总的执行时间。解：因为向量长度超过了向量寄存器的长度，所以要采取分段开采方法。每次循环主要由下面三条向量指令组成：LV VI,Rb ；取向量BMULTVSV2,VI,Fs；向量和标量相乘SV Ra,V2 ；存向量假设A和B的最初分别放在Ra和Rb之中，s在Fs中。三条指令分成3个编队，Tchime=3。T2oo=4X(15+Tstart)+200x3=60+(4XTstart)+600=660+(4XTstart)其中：丁的=12+7+12=31因此，T2(x)=660+4X31=784例6.3在某台向量处理机上执行代码代码如下：1：LVVI,Rx ；取向量X2：MULTSVV2,FO,VI；向量和标量相乘3：LVV3,Ry ；取向量Y4：ADDVV4,V2,V3；加法5：SVRy,V4 ；存结果考虑访问存储器冲突，向量寄存器长度为、各功能部件的启动时间与上例相同。求总的执行时间。解：指令1、2,指令3、4和指令5分成三个编队，前两个编队中两条指令采用向链接技术

执行。=(n+64)+3n=4n+64

对于例3,假设时钟频率为200MHZ。每个循环2个浮点运算:CRAY-1的111/2=10〜20,CYBER205的对于例3,假设时钟频率为200MHZ。每个循环2个浮点运算:CRAY-1的111/2=10〜20,CYBER205的ni/2=100»由MFLOPS定义可知：时钟周期MFLOPS执行小〃循环时的浮点运算次数执行%/2循环的时钟周期数对于例3,如果向量处理机的时钟频率为200MHz。因为Rs=lOOMFLOPS,因此有：2x200MHz=100MFLOps假设:ni/2^64,因此：Tni/2=64