《计算机系统结构习题补充例题与练习行业研究》由会员分享，可在线阅读，更多相关《计算机系统结构习题补充例题与练习行业研究（46页珍藏版）》请在金锄头文库上搜索。
1、1习题习题1v存在的存在的问题大多数同学大多数同学较认真，少数不太真，少数不太认真、有抄真、有抄袭现象象关于参考答案，要知其然，更要知其所以然关于参考答案，要知其然，更要知其所以然v第第5、7两两题理解透明性的含理解透明性的含义掌握掌握计算机系算机系统结构、构、组成、成、实现研究的范研究的范围，P4、5凡凡编写机器写机器语言和言和汇编语言程序要用到的（数据表示、指令言程序要用到的（数据表示、指令系系统、寄存器、寄存器）对计算机系算机系统结构都是不透明的构都是不透明的凡是只影响系凡是只影响系统速度和价格的速度和价格的逻辑实现（计算机算机组成）和物成）和物理理实现（计算机算机实现）对系系统结构都是
2、透明的构都是透明的2习题习题1v第第5题：哪些：哪些对计算机系算机系统结构是透明的构是透明的存存储器的模器的模m交叉存取：目的加快存交叉存取：目的加快存储器速度，器速度，透明透明浮点数据表示：硬件可直接浮点数据表示：硬件可直接识别的数据的数据类型，不透明型，不透明I/O是通道方式是通道方式还是是处理机方式：理机方式：I/O方式方式选择属于系属于系统结构，不透明构，不透明阵列运算部件（多个相同运算部件列运算部件（多个相同运算部件阵列排列）：加快运算速度，列排列）：加快运算速度，透明透明数据数据总线宽度：只影响数据度：只影响数据传输速度，不影响功能，速度，不影响功能，透明透明通道通道类型（型（结合
3、、独立，合、独立，P6）：功能相同、速度不同，）：功能相同、速度不同，透明透明访问方式保方式保护：属于系：属于系统结构，不透明构，不透明程序性中断：属于系程序性中断：属于系统结构，不透明构，不透明控制方式（串行、流水等）：控制方式（串行、流水等）：仅影响速度，影响速度，透明透明堆堆栈指令：指令系指令：指令系统属于系属于系统结构，不透明构，不透明存存储器最小器最小编址址单位：属于系位：属于系统结构，不透明构，不透明Cache存存储器：器：为了提高存了提高存储系系统速度，速度，组原原课中中细讲的，的，透明透明3习题习题1v第第7题：从机器（：从机器（汇编）语言看哪些是透明的言看哪些是透明的指令地址
4、寄存器：指的是程序指令地址寄存器：指的是程序计数器数器PC，80X86中中为IP，相，相对转移指移指令中用到，不透明令中用到，不透明指令指令缓冲器：冲器：缓冲和排冲和排队技技术属于属于计算机算机组成成P5，透明透明时标发生器：生器：产生系生系统时钟，汇编语言不能控制的具体硬件，言不能控制的具体硬件，透明透明条件条件码寄存器：存放寄存器：存放转移条件，也叫程序状移条件，也叫程序状态字字PSW，是条件，是条件转移指移指令的令的测试条件，不透明条件，不透明乘法器、移位器：乘法器、移位器：汇编语言不能控制的具体硬件，言不能控制的具体硬件，透明透明主存地址寄存器：也称存主存地址寄存器：也称存储器地址寄存
5、器器地址寄存器MAR，透明透明磁磁盘外外设：I/O指令可直接指令可直接对其操作（通其操作（通过端口号），不透明端口号），不透明先行先行进位位链：提高加法器运算速度的，：提高加法器运算速度的，组原和数字原和数字逻辑中学到，中学到，汇编语言不能控制的具体硬件，言不能控制的具体硬件，透明透明通用寄存器、中断字寄存器（中断响通用寄存器、中断字寄存器（中断响应、优先先级、屏蔽等）：程序中、屏蔽等）：程序中要用到，不透明要用到，不透明4习题习题1v第第8题题掌握三个公式掌握三个公式v第第12题优化之后各化之后各类指令所占比例，指令所占比例，ALU指令的减少也指令的减少也导致致总指令数减少指令数减少优化后算
6、化后算术运算指令所占比例运算指令所占比例从从MIPS之比得出的之比得出的结论：减少减少ALU指令的比例会使速度指令的比例会使速度变慢慢减少使用减少使用频率高的指令会使速度率高的指令会使速度变慢慢减少速度快的指令的比例会使速度减少速度快的指令的比例会使速度变慢慢5习题习题2vOPOP编码优化的目标编码优化的目标l平均长度短（冗余小）平均长度短（冗余小）l编码规整（长度种类少）编码规整（长度种类少）v最短平均长度最短平均长度（信息源熵信息源熵）：）：l v信息冗余量信息冗余量l（实际长度（实际长度-H-H）/ /实际长度实际长度vHuffmanHuffman编码编码l平均长度最短的方案平均长度最短
7、的方案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问：要求
8、：要求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条，条，总长1
9、6位，每个地址位，每个地址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平均平均长度最短的度最短
10、的扩展展编码，与第，与第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、若某机要求有：、若某
11、机要求有：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个个单地址
12、指令地址指令码点点因此，因此，单地址最多可以地址最多可以设计256-2=254条条4/255/164/254/1610补充习题补充习题v2、某机指令字、某机指令字长为16位。位。设有有单地址指令和双地址指令两地址指令和双地址指令两类。若每个地址字段均若每个地址字段均为6位，且双地址指令有位，且双地址指令有x条。条。问单地址指令可地址指令可以有多少条？以有多少条？4-10扩展展双地址指令剩余双地址指令剩余16-x个个码点作点作扩展展标志志共可共可扩出出单地址指令（地址指令（16-x）26条条11补充习题补充习题v某某处理机的指令字理机的指令字长为16位，有位，有2地址指令、地址指令、1地址指地址
13、指令和令和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用于文字处理的某专用机，每个文字字符用用于文字处理的某专用机
14、，每个文字字符用4位十进制数（位十进制数（0-9）编码表示，空格用）编码表示，空格用-表示，在对传送的文字符和空格进行表示，在对传送的文字符和空格进行统计后，得出其出现的概率为：统计后，得出其出现的概率为：若上述数字和空格均用二进制编码，试设计二进制信息位平均长度最短若上述数字和空格均用二进制编码，试设计二进制信息位平均长度最短的编码。的编码。若传送若传送106个文字符号（每个文字符号后均跟一个空格），按最短编码，个文字符号（每个文字符号后均跟一个空格），按最短编码，共需传送多少个二进制位？共需传送多少个二进制位？若十进制数字和空格均用若十进制数字和空格均用4位二进制码表示，共需传送多少个二进
15、制位？位二进制码表示，共需传送多少个二进制位？-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、支持、支持访存地址的存地
16、址的越界越界检查C、支持向量、数、支持向量、数组的运算的运算寻址址 D、支持、支持OS的的进程程调度度v对系系统程序程序员不透明的是（不透明的是（ ）A、Cache B、系列机各档不同的数据通路、系列机各档不同的数据通路宽度度C、指令、指令缓冲寄存器冲寄存器 D、虚、虚拟存存储器器14练习练习v对应用程序用程序员不透明的是（不透明的是（ ）A、先行、先行进位位链 B、乘法器、乘法器C、指令、指令缓冲寄存器冲寄存器 D、条件、条件码寄存器寄存器v计算机系算机系统结构不包括（构不包括（ ）A、主存速度、主存速度 B、机器工作状、机器工作状态C、信息保、信息保护 D、数据表示、数据表示v判断判断题系
17、系统是否是否设置浮点指令置浮点指令对计算机系算机系统结构是透明的。构是透明的。存存储器采用器采用单体体单字，字，还是多体交叉存取，是多体交叉存取，对系系统结构构设计应是透明的。是透明的。系列机增加新型号系列机增加新型号时，为增加增加寻址灵活性和址灵活性和缩短平均指令字短平均指令字长，可以由，可以由原等原等长操作操作码改改为有多种有多种码长的的扩展操作展操作码。对概率不等的事件用概率不等的事件用Huffman编码，其具体，其具体编码不唯一，但平均不唯一，但平均长度肯度肯定是唯一的，且是最短的。定是唯一的，且是最短的。15习题习题3v4、直接利用公式：、直接利用公式：P41Ta= fi(HiTc+
18、(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
19、1 0 1 0 2 3装入位装入位 1 0 0 1 1 0 0 116习题习题3v补充：补充：某段页式虚拟存储器，虚地址由某段页式虚拟存储器，虚地址由2位段号、位段号、2位页号和位页号和11位页内位移组成，主存容量位页内位移组成，主存容量32KB，每段可有访问方式保护，每段可有访问方式保护，其页表和保护位如下表所示。其页表和保护位如下表所示。此地址空间中共有多少虚页此地址空间中共有多少虚页当程序中遇到下列情况时，由虚地址计算实地址，说明哪个当程序中遇到下列情况时，由虚地址计算实地址，说明哪个会发生段失效、页失效和保护失效。会发生段失效、页失效和保护失效。段号段号段段0段段1段段2段段3访问方式
20、访问方式只读只读可读可读/执行执行可读可读/写写/执行执行可读可读/写写虚页虚页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，
21、可知实地址：，可知实地址：实页号实页号（4）页内位移（页内位移（11）l虚地址：虚地址：段号段号（2）页号页号（2）页内位移（页内位移（11）l页面大小：页面大小：211=2048Bl实地址计算方法同上实地址计算方法同上l页表不在主存内的段页表不在主存内的段2发生段失效发生段失效l页面在辅存上的发生页失效页面在辅存上的发生页失效l取数表示读，取出的数不能作为取数表示读，取出的数不能作为指令执行；只读单元不能写、执行；指令执行；只读单元不能写、执行；转移至此为执行，不能读、写，访转移至此为执行，不能读、写，访问不当的为保护方式失效问不当的为保护方式失效18习题习题3方式方式段段页页页内位移页内位
22、移段失效段失效页失效页失效实页号实页号实地址实地址保护失效保护失效取数取数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+A10123456789123456789123456789123456
23、789123456789123456789TP=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+
24、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请改为静态流水线练习请改为静态流水线练习ABCDEF2
25、3习题习题4v第第10题题6个任务的总执行时间为：个任务的总执行时间为：8（第一个任务用（第一个任务用8个周期）个周期）+53（后（后5个任务，每个任务，每3周期执行一个，周期执行一个，取决于最慢部件取决于最慢部件）实际吞吐率实际吞吐率=6/23 t效率效率=（86）/（235）=48/115=41.7%123111222333123112233123824习题习题4v第第11题禁止向量（延禁止向量（延迟禁止表）禁止表）=（1，3，4，8）原始冲突向量原始冲突向量=（10001101）状状态转移移图略略最大吞吐率的最大吞吐率的调度方案（度方案（2，5），吞吐率），吞吐率=1/3.5输入入6个任
26、个任务的的实际吞吐率：吞吐率：6/（9+2+5+2+5+2）=6/25v补：有：有长度度为8的向量的向量A和和B，分，分别画出在下列画出在下列4中中结构的构的处理器上求点理器上求点积的的时空空图有一个乘法部件和一个加法部件，不能同有一个乘法部件和一个加法部件，不能同时工作，部件内部采用工作，部件内部采用顺序方序方式，完成一次加、乘需要式，完成一次加、乘需要5拍拍同上，只是乘法器和加法器可以并行工作同上，只是乘法器和加法器可以并行工作有一个乘、加双功能静有一个乘、加双功能静态流水流水线，均由，均由5段段组成，每段成，每段1拍拍有乘、加两条流水有乘、加两条流水线，可并行工作，每段，可并行工作，每段
27、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）两条流水线可同时工作）两条流水线可同时
28、工作(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段的时间为段的时间为2 t
29、，其余段为，其余段为t，而，而且流水线的输出可以直接返回到输入端或暂存于相应的流水线且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存器中，现在要在该流水线上计算寄存器中，现在要在该流水线上计算 ，画出其时空图，并计算其吞吐率、加速比和效率。，画出其时空图，并计算其吞吐率、加速比和效率。v有一条动态多功能流水线由有一条动态多功能流水线由5段组成，加法用段组成，加法用1、3、4、5段，段，乘法用乘法用1、2、5段，第段，第2段的时间为段的时间为2 t，其余段为，其余段为t，而且流，而且流水线的输出可以直接返回到输入端或暂存于相应的流水线寄存水线的输出可以直接返回到输入端或暂存于相应的流水
30、线寄存器中，现在要在该流水线上计算器中，现在要在该流水线上计算 ，画，画出其时空图，并计算其吞吐率、加速比和效率。出其时空图，并计算其吞吐率、加速比和效率。29习题习题4（补充）（补充）v有一条动态多功能流水线由有一条动态多功能流水线由6段组成，其中段组成，其中1、4、5、6段组段组成乘法流水线，成乘法流水线，1、2、3、6段组成加法流水线，各流水段的时段组成加法流水线，各流水段的时间均为间均为50ns，假设流水线的输出可以直接返回到输入端，而，假设流水线的输出可以直接返回到输入端，而且有足够的缓冲寄存器，现在要用最快的方式在该流水线上计且有足够的缓冲寄存器，现在要用最快的方式在该流水线上计算
31、算 ，画出其时空图，并计算其吞吐率、，画出其时空图，并计算其吞吐率、加速比和效率。加速比和效率。30习题习题4（补充）（补充）v有一有一5段流水线，各段执行时间均段流水线，各段执行时间均t，其预约表如下：，其预约表如下：画出流水线任务调度的状态转移图画出流水线任务调度的状态转移图分别求出允许不等时间间隔的调度和等时间间隔的调度的两种最优调度分别求出允许不等时间间隔的调度和等时间间隔的调度的两种最优调度策略，以及这两种调度策略的流水线最大吞吐率策略，以及这两种调度策略的流水线最大吞吐率若连续输入若连续输入10个任务，求这两种调度策略的实际吞吐率和加速比个任务，求这两种调度策略的实际吞吐率和加速比
32、 时间时间功能段功能段1234567S1S2S3S4S531练习练习v下列关于下列关于标量流水机的量流水机的说法不正确的是（法不正确的是（ ）A、可、可对标量量进行流水行流水处理理 B、没有向量数据表示、没有向量数据表示C、不能、不能对向量数据向量数据进行运算行运算 D、可以、可以对向量、数向量、数组进行运算行运算v以下以下说法不正确的是（法不正确的是（ ）A、线性流水性流水线是是单功能流水功能流水线 B、动态流水流水线是双功能流水是双功能流水线C、静、静态流水流水线是多功能流水是多功能流水线 D、动态流水流水线只能是只能是单功能流功能流水水线v静静态流水流水线是指（是指（ ）A、只有一种功能
33、的流水、只有一种功能的流水线 B、可同、可同时执行多种功能的行多种功能的流水流水线C、同、同时只能完成一种功能的多功能流水只能完成一种功能的多功能流水线 D、功能不能改、功能不能改变的流水的流水线v非非线性流水性流水线是指（是指（ ）A、一次运算中使用流水、一次运算中使用流水线的多个功能段的多个功能段B、一次运算中要多次使用流水、一次运算中要多次使用流水线的某些功能段的某些功能段C、流水、流水线中某些功能段在各次运算中的作用不同中某些功能段在各次运算中的作用不同D、流水、流水线中的各个功能段在各种运算中有不同的中的各个功能段在各种运算中有不同的组合合32练习练习v与流水与流水线最大吞吐率高低有
34、关的是（最大吞吐率高低有关的是（ ）A、各个子、各个子过程的程的时间 B、最快子、最快子过程的程的时间C、最慢子、最慢子过程的程的时间 D、最后子、最后子过程的程的时间v在流水在流水线中，全局相关是指（中，全局相关是指（ ）A、先写后、先写后读相关相关 B、先、先读后写相关后写相关C、指令相关、指令相关 D、由、由转移指令引起的相关移指令引起的相关v流水机器流水机器对全局相关的全局相关的处理不包括（理不包括（ ）A、猜、猜测法法 B、提前形成条件、提前形成条件码C、加快短循、加快短循环程序的程序的执行行 D、设置相关置相关专用通路用通路vCRAY-1向量机要向量机要实现指令的指令的链接，必接，
35、必须满足的条件是（足的条件是（ ）A、源向量相同，功能部件不冲突，有指令相关、源向量相同，功能部件不冲突，有指令相关B、源向量不同，功能部件相同，无指令相关、源向量不同，功能部件相同，无指令相关C、源向量、功能部件都不同，指令有先写后、源向量、功能部件都不同，指令有先写后读相关相关D、源向量、功能部件都不同，指令有先、源向量、功能部件都不同，指令有先读后写相关后写相关33练习练习vCRAY-1机启机启动存存储器、流水部件及寄存器打入各需器、流水部件及寄存器打入各需1拍，拍，“加加”6拍、拍、“乘乘”7拍、拍、“访存存”6拍，下列向量指令串中的向量拍，下列向量指令串中的向量长度均度均为N，则指令
36、串最短的指令串最短的执行行时间是（是（ ）拍）拍 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号号处理器与哪
37、个相理器与哪个相连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，再最低位，再最
38、低位取反得取反得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
39、级）时，级）时，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
40、 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
41、 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，能否同，能否同时实现播送要求，画出开关状播送要求，画出开关状态图
42、。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
43、级级 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条指令全并行
44、，条指令全并行，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
45、+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，加速
46、比为，加速比为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阵列列处理
47、机主要理机主要实现的是（的是（ ）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
48、）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、 循循环左移一位左移一位v6
49、4个个结点的方体置点的方体置换互互连函数的个数是（函数的个数是（ ）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 、静、静态互
50、互连网网络 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
