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

习题1,存在的问题 大多数同学较认真，少数不太认真、有抄袭现象 关于参考答案，要知其然，更要知其所以然 第5、7两题 理解透明性的含义 掌握计算机系统结构、组成、实现研究的范围，P4、5 凡编写机器语言和汇编语言程序要用到的（数据表示、指令系统、寄存器）对计算机系统结构都是不透明的 凡是只影响系统速度和价格的逻辑实现（计算机组成）和物理实现（计算机实现）对系统结构都是透明的,习题1,第5题：哪些对计算机系统结构是透明的 存储器的模m交叉存取：目的加快存储器速度，透明 浮点数据表示：硬件可直接识别的数据类型，不透明 I/O是通道方式还是处理机方式：I/O方式选择属于系统结构，不透明 阵列运算部件（多个相同运算部件阵列排列）：加快运算速度，透明 数据总线宽度：只影响数据传输速度，不影响功能，透明 通道类型（结合、独立，P6）：功能相同、速度不同，透明 访问方式保护：属于系统结构，不透明 程序性中断：属于系统结构，不透明 控制方式（串行、流水等）：仅影响速度，透明 堆栈指令：指令系统属于系统结构，不透明 存储器最小编址单位：属于系统结构，不透明 Cache存储器：为了提高存储系统速度，组原课中细讲的，透明,习题1,第7题：从机器（汇编）语言看哪些是透明的 指令地址寄存器：指的是程序计数器PC，80X86中为IP，相对转移指令中用到，不透明 指令缓冲器：缓冲和排队技术属于计算机组成P5，透明 时标发生器：产生系统时钟，汇编语言不能控制的具体硬件，透明 条件码寄存器：存放转移条件，也叫程序状态字PSW，是条件转移指令的测试条件，不透明 乘法器、移位器：汇编语言不能控制的具体硬件，透明 主存地址寄存器：也称存储器地址寄存器MAR，透明 磁盘外设：I/O指令可直接对其操作（通过端口号），不透明 先行进位链：提高加法器运算速度的，组原和数字逻辑中学到，汇编语言不能控制的具体硬件，透明 通用寄存器、中断字寄存器（中断响应、优先级、屏蔽等）：程序中要用到，不透明,习题1,第8题 掌握三个公式,第12题 优化之后各类指令所占比例，ALU指令的减少也导致总指令数减少 优化后算术运算指令所占比例 从MIPS之比得出的结论： 减少ALU指令的比例会使速度变慢 减少使用频率高的指令会使速度变慢 减少速度快的指令的比例会使速度变慢,习题2,OP编码优化的目标 平均长度短（冗余小） 编码规整（长度种类少） 最短平均长度（信息源熵）： 信息冗余量 （实际长度-H）/实际长度,Huffman编码 平均长度最短的方案 编码不唯一，但长度确定 每次选择两个最小值节点 非叶子结点值相加,习题2,扩展编码 等长、不等长 X-Y-Z、X/Y/Z 短编码不能是长编码的前缀 一定要用短编码表示频率高的指令 变址位移量 补码表示（-2n-12n-1-1） 指令类型 R-R：速度快，给频率高的指令使用 M-M,习题2,第3题（10条指令） 第2问：要求OP平均长度最短，则一定是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=15.9个二地址指令码点 因此，二地址最多可以设计64-16=48条,习题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（补码）,补充习题,1、若某机要求有：3地址指令4条，单地址指令255条，0地址指令16条。设指令字长为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/16 4/254/16,补充习题,2、某机指令字长为16位。设有单地址指令和双地址指令两类。若每个地址字段均为6位，且双地址指令有x条。问单地址指令可以有多少条？ 4-10扩展 双地址指令剩余16-x个码点作扩展标志 共可扩出单地址指令（16-x）26条,补充习题,某处理机的指令字长为16位，有2地址指令、1地址指令和0地址指令3类，每个地址字段的长度均为6位。 如果2地址指令有15条，0地址指令和1地址指令的条数基本相等，那么0地址指令和1地址指令各有多少条？为3类指令分配操作码。 如果要求3类指令条数的比例为1：9：9。那么3类指令的条数各有多少条？为3类指令分配操作码。 解 4-10-16 15/63/64、14/126/128,补充习题,用于文字处理的某专用机，每个文字字符用4位十进制数（0-9）编码表示，空格用-表示，在对传送的文字符和空格进行统计后，得出其出现的概率为： 若上述数字和空格均用二进制编码，试设计二进制信息位平均长度最短的编码。 若传送106个文字符号（每个文字符号后均跟一个空格），按最短编码，共需传送多少个二进制位？ 若十进制数字和空格均用4位二进制码表示，共需传送多少个二进制位？,练习,计算机中优化使用的操作码编码方法是（ ） A、Huffman编码 B、ASCII码 C、BCD码 D、扩展编码 支持动态再定位的寻址方式是（ ） A、基址寻址 B、间接寻址 C、变址寻址 D、间接寻址 变址寻址的主要作用是（ ） A、支持程序的动态定位 B、支持访存地址的越界检查 C、支持向量、数组的运算寻址 D、支持OS的进程调度 对系统程序员不透明的是（ ） A、Cache B、系列机各档不同的数据通路宽度 C、指令缓冲寄存器 D、虚拟存储器,练习,对应用程序员不透明的是（ ） A、先行进位链 B、乘法器 C、指令缓冲寄存器 D、条件码寄存器 计算机系统结构不包括（ ） A、主存速度 B、机器工作状态 C、信息保护 D、数据表示 判断题 系统是否设置浮点指令对计算机系统结构是透明的。 存储器采用单体单字，还是多体交叉存取，对系统结构设计应是透明的。 系列机增加新型号时，为增加寻址灵活性和缩短平均指令字长，可以由原等长操作码改为有多种码长的扩展操作码。 对概率不等的事件用Huffman编码，其具体编码不唯一，但平均长度肯定是唯一的，且是最短的。,习题3,4、直接利用公式：P41 Ta= fi(HiTc+(1- Hi)Tm)+(1- fi)( HdTc+(1- Hd) Tm)=22.16ns fi=20%、Tc=20ns、Tm=80ns、Hi=98%、Hd=96% 10、 页面失效的虚页号：装入位为0的虚页，1、2、5、6 由虚地址计算实地址： 虚地址页面大小虚页号页内位移 由虚页号查页表得实页号 实地址=实页号页面大小页内位移 809610247928 310249284000 页面失效的无实地址,习题3,补充：某段页式虚拟存储器，虚地址由2位段号、2位页号和11位页内位移组成，主存容量32KB，每段可有访问方式保护，其页表和保护位如下表所示。 此地址空间中共有多少虚页 当程序中遇到下列情况时，由虚地址计算实地址，说明哪个会发生段失效、页失效和保护失效。,习题3,由主存容量为32KB，可知实地址：,虚地址：,页面大小：211=2048B 实地址计算方法同上 页表不在主存内的段2发生段失效 页面在辅存上的发生页失效 取数表示读，取出的数不能作为指令执行；只读单元不能写、执行；转移至此为执行，不能读、写，访问不当的为保护方式失效,习题3,习题4,第6题 A1+A2+ A3+A4+ A5+A6+ A7+A8+ A9+A10,1,2,3,4,5,6,7,8,9,TP=9/21t=3/7t Sp=（95）/21=2.14 E=（95）/（215）=42.9%,8,1,5,10,15,21,习题4,第7题：静态流水线 A1B1+A2B2+A3B3+A4B4+A5B5+A6B6,1,2,3,4,5,6,7,8,9,10,11,1,22,请改为动态流水线练习,1,2,3,4,5,6,习题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%,23,习题4,第9题 动态流水线 a1b1+a2b2+a3b3+a4b4+a5b5+a6b6+a7b7+a8b8,1,23,请改为静态流水线练习,A,B,C,D,E,F,习题4,第10题 6个任务的总执行时间为：8（第一个任务用8个周期）+53（后5个任务，每3周期执行一个，取决于最慢部件） 实际吞吐率=6/23t 效率=（86）/（235）=48/115=41.7%,8,习题4,第11题 禁止向量（延迟禁止表）=（1，3，4，8） 原始冲突向量=（10001101） 状态转移图略 最大吞吐率的调度方案（2，5），吞吐率=1/3.5 输入6个任务的实际吞吐率：6/（9+2+5+2+5+2）=6/25 补：有长度为8的向量A和B，分别画出在下列4中结构的处理器上求点积的时空图 有一个乘法部件和一个加法部件，不能同时工作，部件内部采用顺序方式，完成一次加、乘需要5拍 同上，只是乘法器和加法器可以并行工作 有一个乘、加双功能静态流水线，均由5段组成，每段1拍 有乘、加两条流水线，可并行工作，每段1拍,习题4,解 （1） （2）(a1b1+a2b2)+a3b3)+a4b4)+a5b5)+a6b6)+a7b7)+a8b8,5,40,75,5,40,45,习题4,（3）静态双功能流水线 (a1b1+ a2b2)+(a3b3+ a4b4)+(a5b5+ a6b6)+(a7b7 + a8b8),12,30,习题4,（4）两条流水线可同时工作 (a1b1+ a2b2)+ a7b7+ (a5b5+ a6b6)+(a3b3+ a4b4)+ a8b8,12,27,习题4（补充）,有一条静态加、乘多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2t，其余段为t，而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中，现在要在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。 有一条动态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第2段的时间为2t，其余段为t，而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中，现在要在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。,习题4（补充）,有一条动态多功能流水线由6段组成，其中1、4、5、6段组成乘法流水线，1、2、3、6段组成加法流水线，各流水段的时间均为50ns，假设流水线的输出可以直接返回到输入端，而且有足够的缓冲寄存器，现在要用最快的方式在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。,习题4（补充）,有一5段流水线，各段执行时间均t，其预约表如下： 画出流水线任务调度的状态转移图 分别求出允许不等时间间隔的调度和等时间间隔的调度的两种最优调度策略，以及这两种调度策略的流水线最大吞吐率 若连续输入10个任务，求这两种调度策略的实际吞吐率和加速比,练习,下列关于标量流水机的说法不正确的是（ ） A、可对标量进行流水处理 B、没有向量数据表示 C、不能对向量数据进行运算 D、可以对向量、数组进行运算 以下说法不正确的是（ ） A、线性流水线是单功能流水线 B、动态流水线是双功能流水线 C、静态流水线是多功能流水线 D、动态流水线只能是单功能流水线 静态流水线是指（ ） A、只有一种功能的流水线 B、可同时执行多种功能的流水线 C、同时只能完成一种功能的多功能流水线 D、功能不能改变的流水线 非线性流水线是指（ ） A、一次运算中使用流水线的多个功能段 B、一次运算中要多次使用流水线的某些功能段 C、流水线中某些功能段在各次运算中的作用不同 D、流水线中的各个功能段在各种运算中有不同的组合,练习,与流水线最大吞吐率高低有关的是（ ） A、各个子过程的时间 B、最快子过程的时间 C、最慢子过程的时间 D、最后子过程的时间 在流水线中，全局相关是指（ ） A、先写后读相关 B、先读后写相关 C、指令相关 D、由转移指令引起的相关 流水机器对全局相关的处理不包括（ ） A、猜测法 B、提前形成条件码 C、加快短循环程序的执行 D、设置相关专用通路 CRAY-1向量机要实现指令的链接，必须满足的条件是（ ） A、源向量相同，功能部件不冲突，有指令相关 B、源向量不同，功能部件相同，无指令相关 C、源向量、功能部件都不同，指令有先写后读相关 D、源向量、功能部件都不同，指令有先读后写相关,练习,CRAY-1机启动存储器、流水部件及寄存器打入各需1拍，“加”6拍、“乘”7拍、“访存”6拍，下列向量指令串中的向量长度均为N，则指令串最短的执行时间是（ ）拍 V3存储器 V4V0+V1 V2V4*V3 A、N+19 B、N+18 C、N+17 D、N+16 CRAY-1的两条向量指令属于 （） V1V2+V3 V4V1*V5 A、没有功能部件冲突和源向量冲突，可以并行 B、没有功能部件冲突和源向量冲突，可以链接 C、没有源向量冲突，可以交换顺序执行 D、有向量寄存器冲突，只能串行,习题5,4、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，再最低位取反得01000B，最后循环左移一位得：10000B=16D，16号 7、256个PE的SIMD机器，采用全混洗互连函数，混洗10次后，197号PE与哪个PE相连 197D=11000101B（8位，因为共256个PE） 循环左移10次（相当于2次，因为共8位）为：00010111B=23D，23号,习题5,18、32个处理器的5（log232）级STARAN网，当级控制信号为10110（从右至左分别控制第0级至第4级）时，17号处理器连接哪个处理器 根据STARAN网作为交换网络的特点，某级控制信号为1，就实现了某个Cubei，因此本题实现Cube4+Cube2+Cube1功能 17D=10001B，第4、2、1位取反后为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 F 8组2元交换：1 0 3 2 5 4 7 6 9 8 B A D C F E 4组4元交换：2 3 0 1 6 7 4 5 A B 8 9 E F C D 2组8元交换：5 4 7 6 1 0 3 2 D C F E 9 8 B A（输出） 可见实现了Cube2+Cube0 互连函数表达式：,习题5,补：N=16的STARAN网在级控制下实现分组交换置换，如果实现的分组交换置换是：首先是4组4元交换，然后是2组8元交换，最后是1组16元交换，请写出网络实现的互连函数。 0 1 2 3 4 5 6 7 8 9 A B C D E F 3 2 1 0 7 6 5 4 B A 9 8 F E D C 4 5 6 7 0 1 2 3 C D E F 8 9 A B B 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，能否同时实现播送要求，画出开关状态图。,习题5,能,习题5,补：对于采用级控制的3级立方体互连网络，当第i级为直连状态时，不能实现哪些节点之间的通信？为什么？反之，当第i级为交换状态呢？ 因为第i级为交换状态时，实现的是cubei互连函数，所以 第i级为直连状态时，不能实现第i位取反的节点间的通信 第i级为交换状态时，不能实现第i位不变的节点间的通信,习题6,5、 （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、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 ）,习题6,8、参考例6.9 设平均数度为Ra，可向量化比例为x，则有 要使Ra=6，则x=83.3% 也可以直接利用amdhal定律， P15，fnew=x, rnew=10/2=5 要使Ra=6，则Sp=6/2=3，则x=83.3%,习题6,9、 设标量速度为Rs，平均速度为为Ra，可向量化比例为x，加速比为SP，则有 要使SP=2，则X=55.6% 也可以直接利用Aamdhal定律，P15，fnew=x, rnew=10,习题6,10、用自己学过的C语言描述 for(i=1;i=32;i+) Ci=Ai+Bi; len=16 for(i=1;i=5;i+) for(j=1;j=len:j+) Cj=Cj+Cj+len; len=len/2; ,练习,ILLIAC 阵列处理机中，PE之间所用的互连函数是（ ） A、PM20和PM23 B、Cube0和Cube1 C、Shuffle D、PM22 阵列处理机主要实现的是（ ） A、作业级并行 B、任务级并行 C、指令操作级并行 D、指令内操作步骤并行 16个处理器编号为015，采用PM2+3单