计算机系统结构(习题补充例题与练习) 2

1、1习题1存在的问题大多数同学较认真，少数不太认真、有抄袭现象关于参考答案，要知其然，更要知其所以然第5、7两题理解透明性的含义掌握计算机系统结构、组成、实现研究的范围，P4、5凡编写机器语言和汇编语言程序要用到的（数据表示、指令系统、寄存器）对计算机系统结构都是不透明的凡是只影响系统速度和价格的逻辑实现（计算机组成）和物理实现（计算机实现）对系统结构都是透明的2习题1第5题：哪些对计算机系统结构是透明的存储器的模m交叉存取：目的加快存储器速度，透明浮点数据表示：硬件可直接识别的数据类型，不透明I/O是通道方式还是处理机方式：I/O方式选择属于系统结构，不透明阵列运算部件（多个相同运算部件阵列排

2、列）：加快运算速度，透明数据总线宽度：只影响数据传输速度，不影响功能，透明通道类型（结合、独立，P6）：功能相同、速度不同，透明访问方式保护：属于系统结构，不透明程序性中断：属于系统结构，不透明控制方式（串行、流水等）：仅影响速度，透明堆栈指令：指令系统属于系统结构，不透明存储器最小编址单位：属于系统结构，不透明Cache存储器：为了提高存储系统速度，组原课中细讲的，透明3习题1第7题：从机器（汇编）语言看哪些是透明的指令地址寄存器：指的是程序计数器PC，80X86中为IP，相对转移指令中用到，不透明指令缓冲器：缓冲和排队技术属于计算机组成P5，透明时标发生器：产生系统时钟，汇编语言不能控制的

3、具体硬件，透明条件码寄存器：存放转移条件，也叫程序状态字PSW，是条件转移指令的测试条件，不透明乘法器、移位器：汇编语言不能控制的具体硬件，透明主存地址寄存器：也称存储器地址寄存器MAR，透明磁盘外设：I/O指令可直接对其操作（通过端口号），不透明先行进位链：提高加法器运算速度的，组原和数字逻辑中学到，汇编语言不能控制的具体硬件，透明通用寄存器、中断字寄存器（中断响应、优先级、屏蔽等）：程序中要用到，不透明4习题1第8题掌握三个公式11()iniiniiiNNCPIICPICPIIII661010NcEIfMIPSTCPI第12题优化之后各类指令所占比例，ALU指令的减少也导致总指令数减少优化

4、后算术运算指令所占比例从MIPS之比得出的结论：减少ALU指令的比例会使速度变慢减少使用频率高的指令会使速度变慢减少速度快的指令的比例会使速度变慢610MIPSITNE43% 0.521.527.39%1 43% 0.578.55习题2niiilpL1iniippH12logvOPOP编码优化的目标编码优化的目标l平均长度短（冗余小）平均长度短（冗余小）l编码规整（长度种类少）编码规整（长度种类少）v最短平均长度最短平均长度（信息源熵信息源熵）：）：l v信息冗余量信息冗余量l（实际长度（实际长度-H-H）/ /实际长度实际长度vHuffmanHuffman编码编码l平均长度最短的方案平均长度

5、最短的方案l编码不唯一，但长度确定编码不唯一，但长度确定l每次选择两个最小值节点每次选择两个最小值节点l l非叶子结点值相加非叶子结点值相加6习题2v扩展编码扩展编码l等长、不等长等长、不等长lX-Y-ZX-Y-Z、X/Y/ZX/Y/Zl短编码不能是长编码的短编码不能是长编码的前缀前缀l一定要用短编码表示频率高的指令一定要用短编码表示频率高的指令v变址位移量变址位移量l补码表示（补码表示（-2-2n-1n-12 2n-1n-1-1-1）v指令类型指令类型lR-RR-R：速度快，给频率高的指令使用：速度快，给频率高的指令使用lM-MM-M7习题2第3题（10条指令）第2问：要求OP平均长度最短，

6、则一定是Huffman编码（画Huffman树时要注意，确保每次选两个概率最小的），2.7第3问： OP平均长度最短的扩展编码（不一定是等长扩展），究竟哪种最短，要一个一个去试，本题可以试一下2-5、2-4、3-4，结果2-5最短，2.9第4问： OP平均长度最短的等长扩展编码，只需考虑2-4（1-2不可能、3-6太长），2.92第5题（三地址12条，单地址254条，总长16位，每个地址4位）4-8-12等长扩展，12/X/254若不考虑单地址指令，则二地址最多416=64条考虑单地址指令，每预留一个二地址指令码点，则可以扩展16条单地址指令，要使单地址指令达到254条，则应预留254/16=

7、15.9个二地址指令码点因此，二地址最多可以设计64-16=48条8习题2第6题（9条指令，8位（R-R）、16位（R-M）两种指令字长）第1问：OP平均长度最短的扩展编码，与第3题类似，2-4、2-5比较后可知，2-5平均长度最短，2.9第2问：为提高速度，应将使用频率高的指令安排成R-R型，为减少存储容量，应将使用频率高的指令安排成短OP（2位），因此R编码占3位，可以表示8个通用寄存器第3、4问：通用寄存器做变址寄存器，则变址位移量只能是5位（16位-5位OP-3位R-3位X），偏移范围-1615（补码）9补充习题1、若某机要求有：3地址指令4条，单地址指令255条，0地址指令16条。设

8、指令字长为12位，每个地址码为3位。问能否用扩展操作码为其编码？单地址指令为254条呢？请说明理由。3-9-12不等长扩展， 4/255/16； 4/254/16若不考虑0地址指令，则单地址最多426=256条考虑0地址指令，每预留一个单地址指令码点，则可以扩展8条0地址指令，要使0地址指令达到16条，则应预留16/8=2个单地址指令码点因此，单地址最多可以设计256-2=254条4/255/164/254/1610补充习题2、某机指令字长为16位。设有单地址指令和双地址指令两类。若每个地址字段均为6位，且双地址指令有x条。问单地址指令可以有多少条？4-10扩展双地址指令剩余16-x个码点作扩

9、展标志共可扩出单地址指令（16-x）26条11补充习题某处理机的指令字长为16位，有2地址指令、1地址指令和0地址指令3类，每个地址字段的长度均为6位。如果2地址指令有15条，0地址指令和1地址指令的条数基本相等，那么0地址指令和1地址指令各有多少条？为3类指令分配操作码。如果要求3类指令条数的比例为1：9：9。那么3类指令的条数各有多少条？为3类指令分配操作码。解4-10-1615/63/64、14/126/12812补充习题用于文字处理的某专用机，每个文字字符用4位十进制数（0-9）编码表示，空格用-表示，在对传送的文字符和空格进行统计后，得出其出现的概率为：若上述数字和空格均用二进制编码

10、，试设计二进制信息位平均长度最短的编码。若传送106个文字符号（每个文字符号后均跟一个空格），按最短编码，共需传送多少个二进制位？若十进制数字和空格均用4位二进制码表示，共需传送多少个二进制位？-01234567890.20.170.060.080.110.080.050.080.130.030.01（文字）- （文字）- （文字）13练习计算机中优化使用的操作码编码方法是（ ）A、Huffman编码 B、ASCII码C、BCD码 D、扩展编码支持动态再定位的寻址方式是（ ）A、基址寻址 B、间接寻址C、变址寻址 D、间接寻址变址寻址的主要作用是（ ）A、支持程序的动态定位 B、支持访存地址的

11、越界检查C、支持向量、数组的运算寻址 D、支持OS的进程调度对系统程序员不透明的是（ ）A、Cache B、系列机各档不同的数据通路宽度C、指令缓冲寄存器 D、虚拟存储器14练习对应用程序员不透明的是（ ）A、先行进位链 B、乘法器C、指令缓冲寄存器 D、条件码寄存器计算机系统结构不包括（ ）A、主存速度 B、机器工作状态C、信息保护 D、数据表示判断题系统是否设置浮点指令对计算机系统结构是透明的。存储器采用单体单字，还是多体交叉存取，对系统结构设计应是透明的。系列机增加新型号时，为增加寻址灵活性和缩短平均指令字长，可以由原等长操作码改为有多种码长的扩展操作码。对概率不等的事件用Huffman

12、编码，其具体编码不唯一，但平均长度肯定是唯一的，且是最短的。15习题34、直接利用公式：P41Ta= fi(HiTc+(1- Hi)Tm)+(1- fi)( HdTc+(1- Hd) Tm)=22.16nsfi=20%、Tc=20ns、Tm=80ns、Hi=98%、Hd=96%10、页面失效的虚页号：装入位为0的虚页，1、2、5、6由虚地址计算实地址：虚地址页面大小虚页号页内位移由虚页号查页表得实页号实地址=实页号页面大小页内位移809610247928310249284000页面失效的无实地址虚页号01234567实页号23101023装入位1001100116习题3补充：某段页式虚拟存储器

13、，虚地址由2位段号、2位页号和11位页内位移组成，主存容量32KB，每段可有访问方式保护，其页表和保护位如下表所示。此地址空间中共有多少虚页当程序中遇到下列情况时，由虚地址计算实地址，说明哪个会发生段失效、页失效和保护失效。段号段0段1段2段3访问方式只读可读/执行可读/写/执行可读/写虚页0所在位置实页9在辅存上页表不在内存实页14虚页1所在位置实页3实页0实页1虚页2所在位置在辅存上实页15实页6虚页3所在位置实页12实页8在辅存上17习题3方式段页页内位移取数011取数1112取数332047存数014存数212存数1014转移至此13100取数0250取数205转移至此3060l由主存

14、容量为由主存容量为32KB，可知实地址：，可知实地址：实页号（4）页内位移（11）l虚地址：虚地址：段号（2）页号（2）页内位移（11）l页面大小：页面大小：211=2048Bl实地址计算方法同上实地址计算方法同上l页表不在主存内的段页表不在主存内的段2发生段失效发生段失效l页面在辅存上的发生页失效页面在辅存上的发生页失效l取数表示读，取出的数不能作为取数表示读，取出的数不能作为指令执行；只读单元不能写、执行；指令执行；只读单元不能写、执行；转移至此为执行，不能读、写，访转移至此为执行，不能读、写，访问不当的为保护方式失效问不当的为保护方式失效18习题3方式段页页内位移段失效页失效实页号实地址

15、保护失效取数011无无36145无取数1112无无010无取数332047无有无无/存数014无无36148有存数212有/无无/存数1014无有无无/转移至此13100无无816484无取数0250有有无无/取数205无/无无/转移至此3060无无1428732有19习题4第6题A1+A2+ A3+A4+ A5+A6+ A7+A8+ A9+A10123456789123456789123456789123456789123456789123456789TP=9/21t=3/7tSp=（95）/21=2.14E=（95）/（215）=42.9%81510152120习题4第7题：静态流水线A1

16、B1+A2B2+A3B3+A4B4+A5B5+A6B612345678910111234561234567891011789101112345678910111234567891011122请改为动态流水线练习请改为动态流水线练习12345621习题4第8题算法：(a1+b1)c1+(a2+b2)c2 +(a3+b3)c3+ (a4+b4)c4总时间：（3+31）+ （4+32）+（3+1） +3=23效率：(73+44)/(234)=37/92=40.2%1234一二三四567一 一 二 二 三 三 四 四12345671234一二三四5672322习题4第9题动态流水线a1b1+a2b2+

17、a3b3+a4b4+a5b5+a6b6+a7b7+a8b812345678一 二 三 四五六七一 二 三 四五六七一 二 三 四五六七123456781234567812345678一 二 三 四五六七123请改为静态流水线练习请改为静态流水线练习ABCDEF23习题4第10题6个任务的总执行时间为：8（第一个任务用8个周期）+53（后5个任务，每3周期执行一个，取决于最慢部件）实际吞吐率=6/23t效率=（86）/（235）=48/115=41.7%123111222333123112233123824习题4第11题禁止向量（延迟禁止表）=（1，3，4，8）原始冲突向量=（10001101）

18、状态转移图略最大吞吐率的调度方案（2，5），吞吐率=1/3.5输入6个任务的实际吞吐率：6/（9+2+5+2+5+2）=6/25补：有长度为8的向量A和B，分别画出在下列4中结构的处理器上求点积的时空图有一个乘法部件和一个加法部件，不能同时工作，部件内部采用顺序方式，完成一次加、乘需要5拍同上，只是乘法器和加法器可以并行工作有一个乘、加双功能静态流水线，均由5段组成，每段1拍有乘、加两条流水线，可并行工作，每段1拍25习题4解（1）（2）(a1b1+a2b2)+a3b3)+a4b4)+a5b5)+a6b6)+a7b7)+a8b8加乘54075加乘5404526习题4（3）静态双功能流水线(a1

19、b1+ a2b2)+(a3b3+ a4b4)+(a5b5+ a6b6)+(a7b7 + a8b8)910111213141591011121314159101112131415910111213141591011121314151 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8123027习题4（4）两条流水线可同时工作(a1b1+ a2b2)+ a7b7+ (a5b5+ a6b6)+(a3b3+ a4b4)+ a8b891011121314159101112131415910111213141591011121314159

20、1011121314151 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8122728习题4（补充）有一条静态加、乘多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2t，其余段为t，而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中，现在要在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。有一条动态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第2段的时间为2t，其余段为t，而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中，现

21、在要在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。41()iiiAB41iiiA B29习题4（补充）有一条动态多功能流水线由6段组成，其中1、4、5、6段组成乘法流水线，1、2、3、6段组成加法流水线，各流水段的时间均为50ns，假设流水线的输出可以直接返回到输入端，而且有足够的缓冲寄存器，现在要用最快的方式在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。51iiiix y z30习题4（补充）有一5段流水线，各段执行时间均t，其预约表如下：画出流水线任务调度的状态转移图分别求出允许不等时间间隔的调度和等时间间隔的调度的两种最优调度策略，以及这两种调度策略的

22、流水线最大吞吐率若连续输入10个任务，求这两种调度策略的实际吞吐率和加速比 时间功能段1234567S1S2S3S4S531练习下列关于标量流水机的说法不正确的是（ ）A、可对标量进行流水处理 B、没有向量数据表示C、不能对向量数据进行运算 D、可以对向量、数组进行运算以下说法不正确的是（ ）A、线性流水线是单功能流水线 B、动态流水线是双功能流水线C、静态流水线是多功能流水线 D、动态流水线只能是单功能流水线静态流水线是指（ ）A、只有一种功能的流水线 B、可同时执行多种功能的流水线C、同时只能完成一种功能的多功能流水线 D、功能不能改变的流水线非线性流水线是指（ ）A、一次运算中使用流水线

23、的多个功能段B、一次运算中要多次使用流水线的某些功能段C、流水线中某些功能段在各次运算中的作用不同D、流水线中的各个功能段在各种运算中有不同的组合32练习与流水线最大吞吐率高低有关的是（ ）A、各个子过程的时间 B、最快子过程的时间C、最慢子过程的时间 D、最后子过程的时间在流水线中，全局相关是指（ ）A、先写后读相关 B、先读后写相关C、指令相关 D、由转移指令引起的相关流水机器对全局相关的处理不包括（ ）A、猜测法 B、提前形成条件码C、加快短循环程序的执行 D、设置相关专用通路CRAY-1向量机要实现指令的链接，必须满足的条件是（ ）A、源向量相同，功能部件不冲突，有指令相关B、源向量不

24、同，功能部件相同，无指令相关C、源向量、功能部件都不同，指令有先写后读相关D、源向量、功能部件都不同，指令有先读后写相关33练习CRAY-1机启动存储器、流水部件及寄存器打入各需1拍，“加”6拍、“乘”7拍、“访存”6拍，下列向量指令串中的向量长度均为N，则指令串最短的执行时间是（ ）拍 V3存储器 V4V0+V1 V2V4*V3A、N+19 B、N+18 C、N+17 D、N+16CRAY-1的两条向量指令属于 （） V1V2+V3 V4V1*V5A、没有功能部件冲突和源向量冲突，可以并行B、没有功能部件冲突和源向量冲突，可以链接C、没有源向量冲突，可以交换顺序执行D、有向量寄存器冲突，只能

25、串行34习题54、32个处理器，编号031，11号处理器与哪个相连Cube3：11D=01011B，00011B = 3D，3号PM2+3：（11+23）mod 32 = 19，19号PM2-4：（11-24）mod 32 = 27，27号Shuffle：01011B循环左移一位=10110B=22D，22号Butterfly：01011B最高位与最低位交换=11010B=26D，26号Shuffle(shuffle)： 01011B循环左移二位=01101B=13D，13号Shuffle(Cube0 (PM2-1)： （11-21）mod 32 = 9D=01001B，再最低位取反得0100

26、0B，最后循环左移一位得：10000B=16D，16号7、256个PE的SIMD机器，采用全混洗互连函数，混洗10次后，197号PE与哪个PE相连197D=11000101B（8位，因为共256个PE）循环左移10次（相当于2次，因为共8位）为：00010111B=23D，23号35习题518、32个处理器的5（log232）级STARAN网，当级控制信号为10110（从右至左分别控制第0级至第4级）时，17号处理器连接哪个处理器根据STARAN网作为交换网络的特点，某级控制信号为1，就实现了某个Cubei，因此本题实现Cube4+Cube2+Cube1功能17D=10001B，第4、2、1位

27、取反后为00111B=7D，7号19、16个处理器，先8组2元交换、再4组4元交换，最后2组8元交换，写出互连函数输入： 0 1 2 3 4 5 6 7 8 9 A B C D E F8组2元交换：1 0 3 2 5 4 7 6 9 8 B A D C F E4组4元交换：2 3 0 1 6 7 4 5 A B 8 9 E F C D2组8元交换：5 4 7 6 1 0 3 2 D C F E 9 8 B A（输出）可见实现了Cube2+Cube0互连函数表达式：01230123)(PPPPPPPPCube36习题5补：N=16的STARAN网在级控制下实现分组交换置换，如果实现的分组交换置换

28、是：首先是4组4元交换，然后是2组8元交换，最后是1组16元交换，请写出网络实现的互连函数。0 1 2 3 4 5 6 7 8 9 A B C D E F3 2 1 0 7 6 5 4 B A 9 8 F E D C4 5 6 7 0 1 2 3 C D E F 8 9 A BB A 9 8 F E D C 3 2 1 0 7 6 5 4 (0 B)(1 A)(2 9)(3 8)(4 F)(5 E)(6 D)(7 C)Cube3+Cube1+Cube0补：用一个N=8的3级Omega网络连接8个处理机P0P7，如果P6要把数据广播给P0P4，如果P3要把数据广播给P5P7，能否同时实现播送要求

29、，画出开关状态图。37习题5能 0 0 2 2 1 1 3 3 4 4 6 6 5 5 7 7 0 0 2 2 1 1 3 3 4 4 6 6 5 5 7 7 0 0 4 4 1 1 5 5 2 2 6 6 3 3 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 I I J J K K L L 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 入入 端端 出出 端端 0 0 4 4 1 1 5 5 2 2 6 6 3 3 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7

30、2 2 级级 1 1 级级 0 0 级级 A A B B C C D D E E F F G G H H 38习题5补：对于采用级控制的3级立方体互连网络，当第i级为直连状态时，不能实现哪些节点之间的通信？为什么？反之，当第i级为交换状态呢？因为第i级为交换状态时，实现的是cubei互连函数，所以第i级为直连状态时，不能实现第i位取反的节点间的通信第i级为交换状态时，不能实现第i位不变的节点间的通信39习题65、（1）3条指令全并行，72拍（乘法最慢：1+7+1+63）（2）1、2并行与3链接，要求1比2早启动1拍，否则不能与3链接， 80拍（1+7+1+1+6+1+63）（3）1、2并行，3

31、、4链接，1、2和3、4之间串行。 151拍（1+6+1+63+1+6+1+1+7+1+63）（4）1、2、3两级链接与4串， 166拍（1+6+1+1+14+1+1+6+1+63+1+6+1+63）（5）1、2并与3链接，要求2比1早启动1拍，否则不能与3链接，与4串 151拍 （ 1+7+1+1+6+1+63+1+6+1+63）（6）1、2并，2与3链接，4与3串行， 152拍（1+6+1+1+7+1+63+1+7+1+63 ）40习题68、参考例6.8设平均数度为Ra，可向量化比例为x，则有要使Ra=6，则x=83.3%也可以直接利用amdhal定律， P19，fnew=x, rnew=10/2=5要使Ra=6，则Sp=6/2=3，则x=83.3%xxxRa4510)1 (211011xxxSp8 . 0115/)1 (141习题69、设标量速度为Rs，平均速度为为Ra，可向量化比例为x，加速比为SP，则有要使SP=2，则X=55.6%也可以直接利用Aamdhal定律，P19，fnew=x, rnew=10 xRsxRsRsxRsxRsRsRaSp9101091010)1 (11011xxxSp9 . 01110/)1 (142习题610、用自己学过的C语言描述for(i=1;i=32;i+) Ci=Ai+Bi;len=16for(i=1;i=5;i+) f