计算机系统结构习题补充例题和练习教育课件

1计算机系统计算机系统结构结构(习题习题补充例题和补充例题和练习练习)2习题习题1v第第5题：哪些对计算机系统结构是透明的题：哪些对计算机系统结构是透明的存储器的模存储器的模m交叉存取：目的加快存储器速度，交叉存取：目的加快存储器速度，透明透明浮点数据表示：硬件可直接识别的数据类型，不透明浮点数据表示：硬件可直接识别的数据类型，不透明I/O是通道方式还是处理机方式：是通道方式还是处理机方式：I/O方式选择属于系统结构，不透明方式选择属于系统结构，不透明阵列运算部件（多个相同运算部件阵列排列）：加快运算速度，阵列运算部件（多个相同运算部件阵列排列）：加快运算速度，透明透明数据总线宽度：只影响数据传输速度，不影响功能，数据总线宽度：只影响数据传输速度，不影响功能，透明透明通道类型（结合、独立，通道类型（结合、独立，P6）：功能相同、速度不同，）：功能相同、速度不同，透明透明访问方式保护：属于系统结构，不透明访问方式保护：属于系统结构，不透明程序性中断：属于系统结构，不透明程序性中断：属于系统结构，不透明控制方式（串行、流水等）：仅影响速度，控制方式（串行、流水等）：仅影响速度，透明透明堆栈指令：指令系统属于系统结构，不透明堆栈指令：指令系统属于系统结构，不透明存储器最小编址单位：属于系统结构，不透明存储器最小编址单位：属于系统结构，不透明Cache存储器：为了提高存储系统速度，组原课中细讲的，存储器：为了提高存储系统速度，组原课中细讲的，透明透明3习题习题1v第第7题：从机器（汇编）语言看哪些是透明的题：从机器（汇编）语言看哪些是透明的指令地址寄存器：指的是程序计数器指令地址寄存器：指的是程序计数器PC，80X86中为中为IP，相对转移指，相对转移指令中用到，不透明令中用到，不透明指令缓冲器：缓冲和排队技术属于计算机组成指令缓冲器：缓冲和排队技术属于计算机组成P5，透明透明时标发生器：产生系统时钟，汇编语言不能控制的具体硬件，时标发生器：产生系统时钟，汇编语言不能控制的具体硬件，透明透明条件码寄存器：存放转移条件，也叫程序状态字条件码寄存器：存放转移条件，也叫程序状态字PSW，是条件转移指，是条件转移指令的测试条件，不透明令的测试条件，不透明乘法器、移位器：汇编语言不能控制的具体硬件，乘法器、移位器：汇编语言不能控制的具体硬件，透明透明主存地址寄存器：也称存储器地址寄存器主存地址寄存器：也称存储器地址寄存器MAR，透明透明磁盘外设：磁盘外设：I/O指令可直接对其操作（通过端口号），不透明指令可直接对其操作（通过端口号），不透明先行进位链：提高加法器运算速度的，组原和数字逻辑中学到，汇编先行进位链：提高加法器运算速度的，组原和数字逻辑中学到，汇编语言不能控制的具体硬件，语言不能控制的具体硬件，透明透明通用寄存器、中断字寄存器（中断响应、优先级、屏蔽等）：程序中通用寄存器、中断字寄存器（中断响应、优先级、屏蔽等）：程序中要用到，不透明要用到，不透明4习题习题1v第第8题题掌握三个公式掌握三个公式v第第12题题优化之后各类指令所占比例，优化之后各类指令所占比例，ALU指令的减少也导致总指令数减少指令的减少也导致总指令数减少优化后算术运算指令所占比例优化后算术运算指令所占比例从从MIPS之比得出的结论：之比得出的结论：减少减少ALU指令的比例会使速度变慢指令的比例会使速度变慢减少使用频率高的指令会使速度变慢减少使用频率高的指令会使速度变慢减少速度快的指令的比例会使速度变慢减少速度快的指令的比例会使速度变慢5习题习题2vOPOP编码优化的目标编码优化的目标l平均长度短（冗余小）平均长度短（冗余小）l编码规整（长度种类少）编码规整（长度种类少）v最短平均长度最短平均长度（信息源熵信息源熵）：）：l v信息冗余量信息冗余量l（实际长度（实际长度-H-H）/实际长度实际长度vHuffmanHuffman编码编码l平均长度最短的方案平均长度最短的方案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习题习题2v第第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.92v第第5题（三地址题（三地址12条，单地址条，单地址254条，总长条，总长16位，每个地址位，每个地址4位）位）4-8-12等长扩展，等长扩展，12/X/254若不考虑单地址指令，则二地址最多若不考虑单地址指令，则二地址最多416=64条条考虑单地址指令，每预留一个二地址指令码点，则可以扩展考虑单地址指令，每预留一个二地址指令码点，则可以扩展16条单地址指条单地址指令，要使单地址指令达到令，要使单地址指令达到254条，则应预留条，则应预留254/16=15.9个二地址指令码点个二地址指令码点因此，二地址最多可以设计因此，二地址最多可以设计64-16=48条条8习题习题2v第第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补充习题补充习题v1、若某机要求有：、若某机要求有：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/164/254/1610补充习题补充习题v2、某机指令字长为、某机指令字长为16位。设有单地址指令和双地址指令两类。位。设有单地址指令和双地址指令两类。若每个地址字段均为若每个地址字段均为6位，且双地址指令有位，且双地址指令有x条。问单地址指令可条。问单地址指令可以有多少条？以有多少条？4-10扩展扩展双地址指令剩余双地址指令剩余16-x个码点作扩展标志个码点作扩展标志共可扩出单地址指令（共可扩出单地址指令（16-x）26条条11补充习题补充习题v某处理机的指令字长为某处理机的指令字长为16位，有位，有2地址指令、地址指令、1地址指地址指令和令和0地址指令地址指令3类，每个地址字段的长度均为类，每个地址字段的长度均为6位。位。如果如果2地址指令有地址指令有15条，条，0地址指令和地址指令和1地址指令的条数基本地址指令的条数基本相等，那么相等，那么0地址指令和地址指令和1地址指令各有多少条？为地址指令各有多少条？为3类指令分类指令分配操作码。配操作码。如果要求如果要求3类指令条数的比例为类指令条数的比例为1：9：9。那么。那么3类指令的条类指令的条数各有多少条？为数各有多少条？为3类指令分配操作码。类指令分配操作码。v解解4-10-1615/63/64、14/126/12812补充习题补充习题v用于文字处理的某专用机，每个文字字符用用于文字处理的某专用机，每个文字字符用4位十进制数（位十进制数（0-9）编码表示，空格用）编码表示，空格用-表示，在对传送的文字符和空格进行表示，在对传送的文字符和空格进行统计后，得出其出现的概率为：统计后，得出其出现的概率为：若上述数字和空格均用二进制编码，试设计二进制信息位平均长度最短若上述数字和空格均用二进制编码，试设计二进制信息位平均长度最短的编码。的编码。若传送若传送106个文字符号（每个文字符号后均跟一个空格），按最短编码，个文字符号（每个文字符号后均跟一个空格），按最短编码，共需传送多少个二进制位？共需传送多少个二进制位？若十进制数字和空格均用若十进制数字和空格均用4位二进制码表示，共需传送多少个二进制位？位二进制码表示，共需传送多少个二进制位？-01234567890.20.170.060.080.110.080.050.080.130.030.01（文字）（文字）-（文字）（文字）-（文字）（文字）13练习练习v计算机中优化使用的操作码编码方法是（计算机中优化使用的操作码编码方法是（）A、Huffman编码编码 B、ASCII码码C、BCD码码 D、扩展编码、扩展编码v支持动态再定位的寻址方式是（支持动态再定位的寻址方式是（）A、基址寻址、基址寻址 B、间接寻址、间接寻址C、变址寻址、变址寻址 D、间接寻址、间接寻址v变址寻址的主要作用是（变址寻址的主要作用是（）A、支持程序的动态定位、支持程序的动态定位 B、支持访存地址的、支持访存地址的越界检查越界检查C、支持向量、数组的运算寻址、支持向量、数组的运算寻址 D、支持、支持OS的进程调度的进程调度v对系统程序员不透明的是（对系统程序员不透明的是（）A、Cache B、系列机各档不同的数据通路宽度、系列机各档不同的数据通路宽度C、指令缓冲寄存器、指令缓冲寄存器 D、虚拟存储器、虚拟存储器14练习练习v对应用程序员不透明的是（对应用程序员不透明的是（）A、先行进位链、先行进位链 B、乘法器、乘法器C、指令缓冲寄存器、指令缓冲寄存器 D、条件码寄存器、条件码寄存器v计算机系统结构不包括（计算机系统结构不包括（）A、主存速度、主存速度 B、机器工作状态、机器工作状态C、信息保护、信息保护 D、数据表示、数据表示v判断题判断题系统是否设置浮点指令对计算机系统结构是透明的。系统是否设置浮点指令对计算机系统结构是透明的。存储器采用单体单字，还是多体交叉存取，对系统结构设计应是透明的。存储器采用单体单字，还是多体交叉存取，对系统结构设计应是透明的。系列机增加新型号时，为增加寻址灵活性和缩短平均指令字长，可以由系列机增加新型号时，为增加寻址灵活性和缩短平均指令字长，可以由原等长操作码改为有多种码长的扩展操作码。原等长操作码改为有多种码长的扩展操作码。对概率不等的事件用对概率不等的事件用Huffman编码，其具体编码不唯一，但平均长度肯编码，其具体编码不唯一，但平均长度肯定是唯一的，且是最短的。定是唯一的，且是最短的。15习题习题3v4、直接利用公式：、直接利用公式：P41Ta=fi(HiTc+(1-Hi)Tm)+(1-fi)(HdTc+(1-Hd)Tm)=22.16nsfi=20%、Tc=20ns、Tm=80ns、Hi=98%、Hd=96%v10、页面失效的虚页号：装入位为页面失效的虚页号：装入位为0的虚页，的虚页，1、2、5、6由虚地址计算实地址：由虚地址计算实地址：虚地址虚地址页面大小虚页号页面大小虚页号页内位移页内位移由虚页号查页表得实页号由虚页号查页表得实页号实地址实地址=实页号实页号页面大小页内位移页面大小页内位移809610247928310249284000页面失效的无实地址页面失效的无实地址虚页号虚页号 0 1 2 3 4 5 6 7实页号实页号 2 3 1 0 1 0 2 3装入位装入位 1 0 0 1 1 0 0 116习题习题3v补充：补充：某段页式虚拟存储器，虚地址由某段页式虚拟存储器，虚地址由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由主存容量为由主存容量为32KB，可知实地址：，可知实地址：实页号实页号（4）页内位移（页内位移（11）l虚地址：虚地址：段号段号（2）页号页号（2）页内位移（页内位移（11）l页面大小：页面大小：211=2048Bl实地址计算方法同上实地址计算方法同上l页表不在主存内的段页表不在主存内的段2发生段失效发生段失效l页面在辅存上的发生页失效页面在辅存上的发生页失效l取数表示读，取出的数不能作为取数表示读，取出的数不能作为指令执行；只读单元不能写、执行；指令执行；只读单元不能写、执行；转移至此为执行，不能读、写，访转移至此为执行，不能读、写，访问不当的为保护方式失效问不当的为保护方式失效18习题习题3方式方式段段页页页内位移页内位移段失效段失效页失效页失效实页号实页号实地址实地址保护失效保护失效取数取数011无无无无36145无无取数取数1112无无无无010无无取数取数332047无无有有无无无无/存数存数014无无无无36148有有存数存数212有有/无无无无/存数存数1014无无有有无无无无/转移至此转移至此13100无无无无816484无无取数取数0250有有有有无无无无/取数取数205无无/无无无无/转移至此转移至此3060无无无无1428732有有19习题习题4v第第6题题vA1+A2+A3+A4+A5+A6+A7+A8+A9+A10123456789123456789123456789123456789123456789123456789TP=9/21t=3/7tSp=（95）/21=2.14E=（95）/（215）=42.9%81510152120习题习题4v第第7题：静态流水线题：静态流水线A1B1+A2B2+A3B3+A4B4+A5B5+A6B612345678910111234561234567891011789101112345678910111234567891011122请改为动态流水线练习请改为动态流水线练习12345621习题习题4v第第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习题习题4v第第9题题动态流水线动态流水线a1b1+a2b2+a3b3+a4b4+a5b5+a6b6+a7b7+a8b812345678一一 二二 三三 四四五五六六七七一一 二二 三三 四四五五六六七七一一 二二 三三 四四五五六六七七123456781234567812345678一一 二二 三三 四四五五六六七七123请改为静态流水线练习请改为静态流水线练习ABCDEF23习题习题4v第第10题题6个任务的总执行时间为：个任务的总执行时间为：8（第一个任务用（第一个任务用8个周期）个周期）+53（后（后5个任务，每个任务，每3周期执行一个，周期执行一个，取决于最慢部件取决于最慢部件）实际吞吐率实际吞吐率=6/23t效率效率=（86）/（235）=48/115=41.7%123111222333123112233123824习题习题4v第第11题题禁止向量（延迟禁止表）禁止向量（延迟禁止表）=（1，3，4，8）原始冲突向量原始冲突向量=（10001101）状态转移图略状态转移图略最大吞吐率的调度方案（最大吞吐率的调度方案（2，5），吞吐率），吞吐率=1/3.5输入输入6个任务的实际吞吐率：个任务的实际吞吐率：6/（9+2+5+2+5+2）=6/25v补：有长度为补：有长度为8的向量的向量A和和B，分别画出在下列，分别画出在下列4中结构的处理器上求点积的中结构的处理器上求点积的时空图时空图有一个乘法部件和一个加法部件，不能同时工作，部件内部采用顺序方有一个乘法部件和一个加法部件，不能同时工作，部件内部采用顺序方式，完成一次加、乘需要式，完成一次加、乘需要5拍拍同上，只是乘法器和加法器可以并行工作同上，只是乘法器和加法器可以并行工作有一个乘、加双功能静态流水线，均由有一个乘、加双功能静态流水线，均由5段组成，每段段组成，每段1拍拍有乘、加两条流水线，可并行工作，每段有乘、加两条流水线，可并行工作，每段1拍拍25习题习题4v解解（1）（2）(a1b1+a2b2)+a3b3)+a4b4)+a5b5)+a6b6)+a7b7)+a8b8加加乘乘54075加加乘乘5404526习题习题4（3）静态双功能流水线）静态双功能流水线(a1b1+a2b2)+(a3b3+a4b4)+(a5b5+a6b6)+(a7b7+a8b8)910111213141591011121314159101112131415910111213141591011121314151234567812345678123456781234567812345678123027习题习题4（4）两条流水线可同时工作）两条流水线可同时工作(a1b1+a2b2)+a7b7+(a5b5+a6b6)+(a3b3+a4b4)+a8b8910111213141591011121314159101112131415910111213141591011121314151 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 81 2 3 4 5 6 7 8122728习题习题4（补充）（补充）v有一条静态加、乘多功能流水线由有一条静态加、乘多功能流水线由5段组成，加法用段组成，加法用1、3、4、5段，乘法用段，乘法用1、2、5段，第段，第3段的时间为段的时间为2t，其余段为，其余段为t，而且流水线的输出可以直接返回到输入端或暂存于相应的流水而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中，现在要在该流水线上计算线寄存器中，现在要在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。，画出其时空图，并计算其吞吐率、加速比和效率。v有一条动态多功能流水线由有一条动态多功能流水线由5段组成，加法用段组成，加法用1、3、4、5段，段，乘法用乘法用1、2、5段，第段，第2段的时间为段的时间为2t，其余段为，其余段为t，而且流，而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中，现在要在该流水线上计算器中，现在要在该流水线上计算 ，画，画出其时空图，并计算其吞吐率、加速比和效率。出其时空图，并计算其吞吐率、加速比和效率。29习题习题4（补充）（补充）v有一条动态多功能流水线由有一条动态多功能流水线由6段组成，其中段组成，其中1、4、5、6段组段组成乘法流水线，成乘法流水线，1、2、3、6段组成加法流水线，各流水段的时段组成加法流水线，各流水段的时间均为间均为50ns，假设流水线的输出可以直接返回到输入端，而，假设流水线的输出可以直接返回到输入端，而且有足够的缓冲寄存器，现在要用最快的方式在该流水线上计且有足够的缓冲寄存器，现在要用最快的方式在该流水线上计算算 ，画出其时空图，并计算其吞吐率、，画出其时空图，并计算其吞吐率、加速比和效率。加速比和效率。30习题习题4（补充）（补充）v有一有一5段流水线，各段执行时间均段流水线，各段执行时间均t，其预约表如下：，其预约表如下：画出流水线任务调度的状态转移图画出流水线任务调度的状态转移图分别求出允许不等时间间隔的调度和等时间间隔的调度的两种最优调度分别求出允许不等时间间隔的调度和等时间间隔的调度的两种最优调度策略，以及这两种调度策略的流水线最大吞吐率策略，以及这两种调度策略的流水线最大吞吐率若连续输入若连续输入10个任务，求这两种调度策略的实际吞吐率和加速比个任务，求这两种调度策略的实际吞吐率和加速比 时间时间功能段功能段1234567S1S2S3S4S531练习练习v下列关于标量流水机的说法不正确的是（下列关于标量流水机的说法不正确的是（）A、可对标量进行流水处理、可对标量进行流水处理 B、没有向量数据表示、没有向量数据表示C、不能对向量数据进行运算、不能对向量数据进行运算 D、可以对向量、数组进行运算、可以对向量、数组进行运算v以下说法不正确的是（以下说法不正确的是（）A、线性流水线是单功能流水线、线性流水线是单功能流水线 B、动态流水线是双功能流水线、动态流水线是双功能流水线C、静态流水线是多功能流水线、静态流水线是多功能流水线 D、动态流水线只能是单功能流、动态流水线只能是单功能流水线水线v静态流水线是指（静态流水线是指（）A、只有一种功能的流水线、只有一种功能的流水线 B、可同时执行多种功能的、可同时执行多种功能的流水线流水线C、同时只能完成一种功能的多功能流水线、同时只能完成一种功能的多功能流水线 D、功能不能改变的流水、功能不能改变的流水线线v非线性流水线是指（非线性流水线是指（）A、一次运算中使用流水线的多个功能段、一次运算中使用流水线的多个功能段B、一次运算中要多次使用流水线的某些功能段、一次运算中要多次使用流水线的某些功能段C、流水线中某些功能段在各次运算中的作用不同、流水线中某些功能段在各次运算中的作用不同D、流水线中的各个功能段在各种运算中有不同的组合、流水线中的各个功能段在各种运算中有不同的组合32练习练习v与流水线最大吞吐率高低有关的是（与流水线最大吞吐率高低有关的是（）A、各个子过程的时间、各个子过程的时间 B、最快子过程的时间、最快子过程的时间C、最慢子过程的时间、最慢子过程的时间 D、最后子过程的时间、最后子过程的时间v在流水线中，全局相关是指（在流水线中，全局相关是指（）A、先写后读相关、先写后读相关 B、先读后写相关、先读后写相关C、指令相关、指令相关 D、由转移指令引起的相关、由转移指令引起的相关v流水机器对全局相关的处理不包括（流水机器对全局相关的处理不包括（）A、猜测法、猜测法 B、提前形成条件码、提前形成条件码C、加快短循环程序的执行、加快短循环程序的执行 D、设置相关专用通路、设置相关专用通路vCRAY-1向量机要实现指令的链接，必须满足的条件是（向量机要实现指令的链接，必须满足的条件是（）A、源向量相同，功能部件不冲突，有指令相关、源向量相同，功能部件不冲突，有指令相关B、源向量不同，功能部件相同，无指令相关、源向量不同，功能部件相同，无指令相关C、源向量、功能部件都不同，指令有先写后读相关、源向量、功能部件都不同，指令有先写后读相关D、源向量、功能部件都不同，指令有先读后写相关、源向量、功能部件都不同，指令有先读后写相关33练习练习vCRAY-1机启动存储器、流水部件及寄存器打入各需机启动存储器、流水部件及寄存器打入各需1拍，拍，“加加”6拍、拍、“乘乘”7拍、拍、“访存访存”6拍，下列向量指令串中的向量长拍，下列向量指令串中的向量长度均为度均为N，则指令串最短的执行时间是（，则指令串最短的执行时间是（）拍）拍 V3存储器存储器 V4V0+V1 V2V4*V3A、N+19 B、N+18 C、N+17 D、N+16vCRAY-1的两条向量指令属于的两条向量指令属于（）（）V1V2+V3 V4V1*V5A、没有功能部件冲突和源向量冲突，可以并行、没有功能部件冲突和源向量冲突，可以并行B、没有功能部件冲突和源向量冲突，可以链接、没有功能部件冲突和源向量冲突，可以链接C、没有源向量冲突，可以交换顺序执行、没有源向量冲突，可以交换顺序执行D、有向量寄存器冲突，只能串行、有向量寄存器冲突，只能串行34习题习题5v4、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号号v7、256个个PE的的SIMD机器，采用全混洗互连函数，混洗机器，采用全混洗互连函数，混洗10次后，次后，197号号PE与哪个与哪个PE相连相连197D=11000101B（8位，因为共位，因为共256个个PE）循环左移循环左移10次（相当于次（相当于2次，因为共次，因为共8位）为：位）为：00010111B=23D，23号号35习题习题5v18、32个处理器的个处理器的5（log232）级）级STARAN网，当级控制信号网，当级控制信号为为10110（从右至左分别控制第（从右至左分别控制第0级至第级至第4级）时，级）时，17号处理器连号处理器连接哪个处理器接哪个处理器根据根据STARAN网作为交换网络的特点，某级控制信号为网作为交换网络的特点，某级控制信号为1，就实现了某个，就实现了某个Cubei，因此本题实现，因此本题实现Cube4+Cube2+Cube1功能功能17D=10001B，第，第4、2、1位取反后为位取反后为00111B=7D，7号号v19、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互连函数表达式：互连函数表达式：36习题习题5v补：补：N=16的的STARAN网在级控制下实现分组交换置换，如果网在级控制下实现分组交换置换，如果实现的分组交换置换是：首先是实现的分组交换置换是：首先是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+Cube0v补：用一个补：用一个N=8的的3级级Omega网络连接网络连接8个处理机个处理机P0P7，如，如果果P6要把数据广播给要把数据广播给P0P4，如果，如果P3要把数据广播给要把数据广播给P5P7，能否同时实现播送要求，画出开关状态图。，能否同时实现播送要求，画出开关状态图。37习题习题5v能能 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 2 2 级级 1 1 级级 0 0 级级 A A B B C C D D E E F F G G H H 38习题习题5v补：对于采用级控制的补：对于采用级控制的3级立方体互连网络，当第级立方体互连网络，当第i级为直连状级为直连状态时，不能实现哪些节点之间的通信？为什么？反之，当第态时，不能实现哪些节点之间的通信？为什么？反之，当第i级级为交换状态呢？为交换状态呢？因为第因为第i级为交换状态时，实现的是级为交换状态时，实现的是cubei互连函数，所以互连函数，所以第第i级为直连状态时，不能实现第级为直连状态时，不能实现第i位取反的节点间的通信位取反的节点间的通信第第i级为交换状态时，不能实现第级为交换状态时，不能实现第i位不变的节点间的通信位不变的节点间的通信39习题习题6v5、（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）40习题习题6v8、参考例、参考例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%41习题习题6v9、设标量速度为设标量速度为Rs，平均速度为为，平均速度为为Ra，可向量化比例为，可向量化比例为x，加速比为，加速比为SP，则有，则有要使要使SP=2，则，则X=55.6%也可以直接利用也可以直接利用Aamdhal定律，定律，P15，fnew=x,rnew=1042习题习题6v10、用自己学过的、用自己学过的C语言描述语言描述for(i=1;i=32;i+)Ci=Ai+Bi;len=16for(i=1;i=5;i+)for(j=1;j=len:j+)Cj=Cj+Cj+len;len=len/2;43练习练习vILLIAC 阵列处理机中，阵列处理机中，PE之间所用的互连函数是（之间所用的互连函数是（）A、PM20和和PM23 B、Cube0和和Cube1C、Shuffle D、PM22v阵列处理机主要实现的是（阵列处理机主要实现的是（）A、作业级并行、作业级并行 B、任务级并行、任务级并行C、指令操作级并行、指令操作级并行 D、指令内操作步骤并行、指令内操作步骤并行v16个处理器编号为个处理器编号为015，采用，采用PM2+3单级网络互连，与单级网络互连，与13号号处理器相连的处理器号是（处理器相连的处理器号是（）A、5 B、1C、7 D、14v用互连循环表示用互连循环表示8个结点的个结点的PM2-1互连函数，应该是（互连函数，应该是（）A、（、（6 4 2 0）（7 5 3 1）B、（0 2 4 6）（1 3 5 7）C、（、（0 1 2 3 4 5 6 7）D、（0 4）（）（1 5）（）（2 6）（）（3 7）44练习练习v16号处理器用单级互连网络互连，将号处理器用单级互连网络互连，将9号连到号连到13号处理器，可号处理器，可用（用（）A、Cube3 B、PM2+2 C、PM2+4 D、Shufflev16个处理器编号为个处理器编号为015，采用单级，采用单级Cube3互连函数，与互连函数，与13号号处理器相连的处理器号是（处理器相连的处理器号是（）A、2 B、3 C、4 D、5v交换置换互连函数得到输出端地址的方法是把输入端二进制地交换置换互连函数得到输出端地址的方法是把输入端二进制地址（址（）A、最高位取反、最高位取反 B、最低位取反、最低位取反 C、最高位与最低位交换、最高位与最低位交换 D、循环左移一位循环左移一位v64个结点的方体置换互连函数的个数是（个结点的方体置换互连函数的个数是（）A、3 B、4 C、5 D、6v64个结点的个结点的PM2I互连函数的个数是（互连函数的个数是（）A、6 B、8 C、12 D、6445练习练习v结构不对称的静态互连网络是（结构不对称的静态互连网络是（）A、线性阵列、线性阵列 B、环形环形 C、立方体网络、立方体网络 D、全连接网络全连接网络v结构对称的静态互连网络是（结构对称的静态互连网络是（）A、二叉树、二叉树 B、星型星型 C、二维网格、二维网格 D、超超立方体立方体vSTARAN网络是一种（网络是一种（）A、多级立方体网络、多级立方体网络 B、多级混洗交换网络多级混洗交换网络C、静态互连网络、静态互连网络 D、非阻塞网络非阻塞网络v三级三级STARAN网络对网络对8个输入端实现个输入端实现2组组4元分组交换后，输入元分组交换后，输入端端号序列端端号序列01234567置换连接的输出端序列是（置换连接的输出端序列是（）A、76543210 B、32107654 C、10325476 D、67452301v三级三级STARAN网络对网络对8个输入端实现模个输入端实现模8移移4的移数置换后，输的移数置换后，输入端端号序列入端端号序列01234567置换连接的输出端序列是（置换连接的输出端序列是（）A、12345670 B、23456701 C、45670123 D、1230567446练习练习v用用N=16的互连网络互连的互连网络互连16个处理器，编号为个处理器，编号为0-15，若网络实，若网络实现的互连函数是现的互连函数是Shuffle(Shuffle)，则与，则与12号处理器连接的是（）号处理器连接的是（）A、9 B、6 C、3 D、12