系统结构习题

1、第一章（P33）1.7T.9（透明性概念），1.12-1.18（Amdahl定律）1.19、1.21、1.24（CPT/MTPS）第二章（P124）2.3、2.5、2.6（浮点数性能）,2.13、2.15（指令编码）第三章（P202）3.3（存储层次性能），3.5（并行主存系统），3.15-3.15加1题（堆栈模拟）,3.19中（3）（4）（6）（8）问（地址映象/替换算法一实存状况图）第五章（P343）5.9（流水线性能/时空图），5.15（2种调度算法）第六章（P391）（向量流水时间计算）6.10（Amdahl定律/MFLOPS）第七章（P446）7.3、7.29（互连函数计算），7.6

2、-7.14（互连网性质）,7.4、7.5、7.26（多级网寻径算法）,7.27（寻径/选播算法）第八章（P498）（SISD/SIMD算法）第九章（P562）9.18（SISD/多功能部件/SIMD/MIMD算法）例,习题第一章（P33）1.6试以实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系与相互影响。系统结构、组成和实现是三个不同的概念，它们各自包含不同的内容，但又有紧密的关系。以存储系统为例，主存储器容量和寻址方式的确定属计算机系统结构，主存的速度应多高在逻辑结构上采用什么措施属计算机组成，而主存的物理实现，如存储器采用什么样器件逻辑电路设计和微组装技术则属计算机实现。1.

3、7什么是透明性概念？对计算机系统结构，下列哪些是透明的？哪些是不透明的？存贮器的模m交叉存取；透明（组成）浮点数据表示；不透明（系统结构）I/O系统是采用通道方式还是I/O处理机方式；不透明数据总线宽度；透明（组成）阵列运算部件；透明（组成）通道是采用结合型的还是独立型的；透明（组成）PDP-11系列中的单总线结构；不透明（系统结构）访问方式保护；不透明（系统结构）程序性中断；不透明（系统结构）串行、重叠还是流水控制方式；透明（组成）堆栈指令；存贮最小编址单位；不透明（系统结构）Cache存贮器。透明（组成）1.12如果某一计算任务用向量方式求解比用标量方式求解要快20倍，称可用向量方式求解部

4、分所花费时间占总的时间的百分比为可向量化百分比。请画出加速比与可向量化比例两者关系的曲线。解：可向量化百分比为Fe,Se=20,根据Amdahl定律To(1-Fe)+FeSe将Se代入Amdahl定律得1-1920e1.13在题1.12中,为达到加速比2,可向量化的百分比应为多少？1-19F=220则可向量化的百分比Fe=0.5261.14在题1.12中,为获得采用向量方式最大加速比的半值(即10)时,所需可向量化的百分比为多少。1-19F=1020则可向量化的百分比Fe=0.9471.15在题1.12中,如果某程序可向量化部分为70%,硬件设计组认为可以通过加大工程投资,使向量处理速度加倍来

5、进一步增加性能；而编译程序编写组认为只需设法增加向量工作方式的百分比就同样可使性能得到相同的提高,问：此时需使可向量化成分再增加多少百分比就可实现。你认为上述硬、软件两种方法中,哪一种方法更好？用硬件组方法,已知Se=2X20=40,Fe=0.7解出Sn=40/12.73.1496用软件组方法，已知Se=20,得到硬件组方法的相同性能Sn=40/12.7解出Fe=27.3/380.7184结论：软件组方法更好。因为硬件组需要将Se再提高100%(20-40),而软件组只需将Fe再提高1.84%(0.7-0.7184)。1.17假设高速缓存Cache工作速度为主存的5倍，且Cache被访问命中的

6、概率为90%,则采用Cache后，能使整个存储系统获得多高的加速比？解：To1-0.9+(1-Fe)+0.91.4FeSe3.571.19用一台40MHz处理机执行标准测试程序，它含的混合指令数和相应所需的时钟周期数如下：指令类型指令数时钟周期数整数运算450001数据传送320002浮点150002控制传送80002求有效CPI、MIPS速率和程序的执行时间。=40 x106IC=工Ii=45000+32000+15000+8000=100000i=1有效CPI=工CPU-1/IC=i=145000 x1+32000 x2+15000 x2+8000 x2100000=1.55MIPS=CP

7、Ix10640 x1061.55x10640155沁25.806ICMIPSx106有效CPI-mipsx10615x106=1.510 x106-=0.003875(秒)x1061.55T=CPIIC-t=1.55x100000 x=0.003875s40 x1061.20某工作站采用时钟频率为15MHz、处理速率为10MIPS的处理机来执行一个已知混合程序。假定每次存储器存取为1周期延迟、试问：此计算机的有效CPI是多少？假定将处理机的时钟提高到30MHz，但存储器子系统速率不变。这样，每次存储器存取需要两个时钟周期。如果30%指令每条只需要一次存储存取，而另外5%每条需要两次存储存取，还

8、假定已知混合程序的指令数不变，并与原工作站兼容，试求改进后的处理机性能。解：(a)f=15MHz,MIPS=10,每次存取时间为2个时钟周期(b)f=30MHz,存储系统的速率不变，但每次存取为2个时钟周期30%指令每条只需要一次存储存取，改进前共需1周期，改进后共需2周期而另外5%每条需要两次存储存取，改进前共需2周期，改进后共需4周期CPI=CPI+30%x(2-1)+5%x(4-2)=1.9新原MIPS=f=30%106=15.8CPIx1061.9x106TIxCPIxt1.5x30Sn=原=c原原=1.58TIxCPIxt1.9x15C新新1.21假设在一台40MHz处理机上运行20

9、000O条指令的目标代码，程序主要由四种指令组成。根据程序跟踪实验结果，已知指令混合比和每种指令所需的指令数如下：指令类型CPI指令混合比算术和逻辑160%高速缓存命中的加载/存储218%转移412%高速缓存缺失的存储器访问810%计算在单处理机上用上述跟踪数据运行程序的平均CPI根据(a)所得CPI,计算相应的MIPS速率。解：CPI=Wxic)i=1(1)CPI=1x0.6+2x0.18+4x0.12+8x0.1=2.2440 x1062.24x106沁17.86第二章(P124)一台模型机共有7条指令,各指令的使用频率分别为35%,25%,20%,10%,5%,3%和2%,有8个通用数据

10、寄存器,2个变址寄存器。要求操作码的平均长度最短,请设计操作码的编码,并计算所设计操作码的平均长度。设计8字长的寄存器-寄存器型指令3条,16位字长的寄存器-存储器型变址寻址方式指令4条,变址范围不小于127。请设计指令格式,并给出各字段的长度和操作码的编码。解：要使得到的操作码长度最短,应采用Huffman编码,构造Huffman树如下1.00由此可以得到7条指令的编码分别如下：指令出现的频率编码135%00225%01320%10410%11055%111063%1111072%11111这样，采用Huffman编码法得到的操作码的平均长度为：H=2X(0.35+0.25+0.20)+3X

11、0.10+4X0.05+5X(0.03+0.02)=1.6+0.3+0.2+0.25=2.35第三章(P202)第五章(P343)5.7一条线性流水线有4个功能段组成，每个功能段的延迟时间都相等，都为t。开始5个At,每间隔一个t向流水线输入一个任务，然后停顿2个At,如此重复。求流水线的实际吞吐率、加速比和效率。解答流水线的时空图如下：我们可以看出，在(lln+1)t的时间内，可以输出5n个结果，如果指令的序列足够长(n-g),并且指令间不存在相关，那么，吞吐率可以认为满足：Tp=5n(11n+1)At5(11+1/n)At加速比为：c5nx4At20n2020z、S=(nTg)(11n+1

12、)At11n+111+1/n11从上面的时空图很容易看出，效率为：耳TE=0kxTk20nAt4x(lln+1)At511+1/n5.8用一条5个功能段的浮点加法器流水线计算F=丈Aii=1每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率解答首先需要考虑的是，10个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：9次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们

13、可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R,源操作数寄存器称为A,最后结果寄存器称为F,并假设源操作数已经在寄存器中，则指令如下：I1:R1A1+A2I2:R2A3+A4I3:R3A5+A6I4:R4A7+A8I5:R5A9+A10I6:R6R1+R2I7:R7R3+R4I8:R8R5+R6I9:FR7+R8这并不是唯一可能的计算方法。假设功能段的延迟为At。时空图如下，图中的数字是指令号。整个计算过程需要21At,所以吞吐率为:Tp=921At=7A7加速比为:9x5At21At45=2.142921效率为:T9x5At3E=ikxT5x21At7k5S3XXS4X(1)写

14、出流水线的禁止向量和初始冲突向量。画出调度流水线的状态图。求流水线的最小启动循环和最小平均启动距离。求平均启动距离最小的恒定循环。解：禁止向量为：(2，4，6)初始冲突向量：101010初始冲突向量逻辑右移2、4、6位时，不作任何处理，逻辑右移1、3、5和大于等于7时，要进行处理。初始冲突向量右移1位之后：010101101010=111111,初始冲突向量右移3位之后：000101V101010=101111,初始冲突向量右移5位之后：000001V101010=101011,初始冲突向量右移7位或大于7位后：还原到它本身。例外：中间冲突向量101111右移5位之后：000001V10101

15、0=101011,中间冲突向量101011右移3位之后：000101V101010=101111,中间冲突向量101011右移5位之后：000001V101010=101011。非线性流水线的状态图平均启动距离预约表与状态图是唯一对应,但不同的预约表也可能有相同的状态图。简单循环：状态图中各种冲突向量只经过一次的启动循环。简单循环的个数一般是有限的。由简单循环可以计算出平均启动距离。简单循环(1,7)(3,7)(5，7)（3,5，7）5(5,3,7)(3,5)(5)(7)最小的启动循环为（1,7）或（3,5）。其平均启动距离为4。平均启动距离最小的恒定循环为5。最小启动循环（3.5）的流水线工

16、作状态时间功能段r123456789101112131415S1X1X2X1X3X2X4X3S2X1X2X1X2X3X4X3S3X1X1X2X2X3X3X4S4X1X2X3X4启动周期动周期忑重复启最小启动循环（1.7）的流水线工作状态时间功能段、123456789101112131415S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4*启动周期重复启动周期恒定启动彳循环的流1水线工作状态时间功能段、123456789101112131415S1X1X2X1X3X2S2X1X1X2X2X3S3X1X1X2X2X3X3S4X1X2X3-启动周期-*一重复启动周期fS、S、S对应的行有2个“X”123因此,最小平均启动距离为2。以恒定循环（2）作为最小启动循环。检查每一行中与第1个“X”的距离为2的倍数的位置都要预留出来S3行的第2个“X”从周期5延迟到周期6。为此，S2行的第2个“x”也要向后延迟一个周期，从周期6延迟到周期7；S行的第2个“X”也要向后延迟一个周期，从周期7延迟到周期8。实