武汉大学计算机学院《计算机系统结构》08级A卷B卷及答案

武汉大学计算机学院2010-2011学年度第一学期2008级《计算机系统结构》期末考试试卷〔A〕〔开卷〕姓名：学号：专业：〔注：①考试时间为120分钟；②所有解答必须写在答题纸上。〕一、单项选择题〔每题2分，共20分〕1．设计一个计算机系统时，以下对系统结构透明的选择是〔〕。【A】数据总线是64位还是32位【B】指令的寻址方式是否由操作码指明【C】是否设置堆栈数据表示【D】I/O系统是采用通道还是外围处理机2.在有通道处理机的I/O系统中，用户通过〔〕来向系统提出访问I/O设备的申请？【A】通道指令【B】中断指令【C】无链通道指令【D】广义指令3．RISC不采用的实现技术是〔〕。【A】重叠存放器窗口【B】以微程序为主解释指令【C】优化延迟转移【D】以硬联逻辑为主解释指令4、编号为0—F的16个处理器采用PM2+3单级网络互连，第13号处理器连至第〔〕号处理器。【A】4【B】5【C】6【D】75．流水计算机中采用“旁路技术”，可以解决〔〕。【A】RAR相关【B】WAR相关【C】RAW相关【D】WAW相关6、某I/O系统有两个选择通道，每个通道上都接有速率分别为500、450、600和500〔KB/S〕的四台设备。那么I/O系统的实际流量为〔〕KB/S。【A】450【B】500【C】600【D】都不是7、“直接用微程序去解释另一台系统结构不同的机器的指令系统、以实现软件的移植”方法，这种技术是〔〕。【A】向前兼容【B】向后兼容【C】仿真【D】模拟8、在Pentium处理器中，流水线对转移指令的猜想技术是〔〕。【A】BHT【B】BTB【C】BTIB【D】都不是9、在N个结点的混洗交换网络中，结点间的最大距离是〔〕。【A】n次交换【B】n次混洗【C】n次交换，n-1次混洗【D】n-1次交换，n次混洗10、德国时间2010年5月31日公布的第35届全球超级计算机TOP500排行榜中，我国星云超级计算机系统排名是〔〕。【A】第一【B】第二【C】第三【D】第四二、〔10分〕假设在一台40MHz处理机上运行180000条指令的目标代码，程序主要由4种指令组成。根据程序跟踪实验结果，指令混合比和每种指令所需的指令数如下表所示：指令类型CPI指令混合百分比算术和逻辑运算154%Cache命中时的加访问218%转移418%Cache失效的访问610%(1)计算在单处理机上用上述数据运行程序的平均CPI。(2)根据(1)所得CPI，计算相应的MIPS速率。三、〔10分〕某模型计算机有7条指令，各指令使用频度分别为0.40,0.26,0.15,0.06,0.05,0.04,0.04。试求出操作码的Huffman编码和扩展编码，并求其平均码长和信息冗余量。〔H=2.27〕四、〔10分〕假设某机要求有：三地址指令4条，单地址指令255条，零地址指令16条。设指令字长为12位，每个地址码长3位。问能否以扩展操作码为其编码？如果其中单地址指令为254条呢？说明其理由。五、〔10分〕有一字节多路通道连接磁盘、磁带、打印机三个设备。磁盘以20μs的间隔向控制器发DMA请求，磁带以25μs的间隔发DMA请求，打印机以40μs间隔发DMA请求。字节多路通道选择设备的时间为4.5μs，传送一个字节需要的时间为0.5μs。试问该通道能否正常工作?ⅠⅡⅢⅣ2Δt

ⅠⅡⅢⅣ2Δt

4Δt

2Δt

2Δt七、〔10分〕有一5功能段非线性流水线，预约表如下：时间t1234567K=1∨∨K=2∨∨K=3∨∨K=4∨∨K=5∨∨〔1〕写出其禁止表和冲突向量，画出流水线调度状态有向图；〔2〕分别写出不等间隔调度和等间隔调度两种方案中的最优调度方案，平均延迟各是多少？〔3〕按不等间隔最正确调度方案连续输入5个任务，画出时空图。八、〔10分)图(A)和(B)分别是N=8个结点的间接二进制n方体多级网络和多级混洗交换网络。分别在(A)、(B)图中要求同时实现PE5到PE0、PE7到PE1的连接，描述其路径。如有阻塞那么指明其路径上的开关号。001234567输出端01234567输入端ABCDEFGHILJK(A)ABCDEFGHILJK输入端01234567输出端01234567(B)九、〔10分〕对于4×4矩阵A和B，要求矩阵C=A×B。试分析这一运算在以下不同结构的计算机上执行过程，如有必要，请描述数据存储分配情况。(1)标量非流水线结构计算机(2)CRAY-1型向量计算机(3)ILLICA-Ⅳ阵列计算机〔全部试题完〕武汉大学计算机学院2010-2011学年度第一学期2008级《计算机系统结构》期末考试试卷〔A〕参考答案一、〔每题2分，共20分〕[解]：1-10：ADDBCDCBCB二、〔10分〕(评分:5+5)[解]：(1)CPI=2.22(2)MIPS≈18.02三、〔10分〕(评分:4+3+3)[解]：编码和树(4分)L哈=2.32(3分)R=〔2.32-2.27〕/2.32≈2.2%(3分)四、〔10分〕(评分:4+3+3)[解]：不能。(4分)当单地址指令为254时，可行。(3分)000×××××××××011×××××××××100000000×××111111101×××111111110000111111111111(3分)五、〔10分〕(评分:4+3+3)[解]：T=4.5μs+0.5μs=5μs，fmax=200〔KB/S〕(4分)fbyte=(1/20+1/25+1/40)×106=115〔KB/S〕(3分)<fmax=200〔KB/S〕(3分)所以，该通道能正常工作。六、〔10分〕(评分:时空图4+TP3+E3)[解]：〔时空图略〕七、〔10分〕(评分:4+3+3)[解]：〔1〕F={1，3，6}，C=〔100101)，状态图略。〔2〕最正确调度方案为〔2，2，5〕和〔4〕，平均延迟分别为3、4〔3〕输入5个任务时空图略。八、〔10分〕(评分:5+5)[解]：(1)间接二进制n方体多级网络:PE5(101)→PE0(000)，控制量为101，即第0级和第2级路径上的开关交换、第1级直连。路径为:PE5→C上→G上→I上→PE0同理PE7(111)→PE1(001)的控制量为110，路径为:PE7→D下→H上→J上→PE1。无阻塞。(2)对于多级混洗交换网络:采用终端地址控制寻径算法，同时实现PE5到PE0、PE7到PE1的连接，路径如下:PE5→B上→G上→I上→PE0PE7→D上→G上→I下→PE1。在开关G上发生了阻塞。九、〔10分〕(评分:4+3+3)[解]：(1)标量非流水线结构计算机乘法4×4×4=64次，加法4×4×3=48次。(2)CRAY-1型向量计算机第一步:将A、B矩阵元素向量化成64个分量值。第二步:用向量指令乘，结果存于某一向量存放器中。第三步:采用递归(累加)方法求C矩阵的各分量值。(数据分配存储略)(3)ILLICA-Ⅳ阵列计算机第一步:将A、B矩阵元素分别播送给64个PE的相同单元α和α+1单元。第二步:所有PE用指令乘，结果存于累加器中。第三步:采用递归(累加)方法求C矩阵的各分量值。(数据分配存储略)武汉大学计算机学院2010-2011学年度第一学期2008级《计算机系统结构》期末考试试卷〔B〕(开卷)姓名：学号：专业：〔注：①考试时间120分钟；②所有解答必须写在答题纸上。〕1．〔15分〕在时钟速率为40MHz的标量处理机上执行一个典型测试程序。它的指令类型，指令条数和每条指令的时钟周期数如下表：指令类型指令条数时钟周期数整数运算450001数据传送320002浮点运算150002比较转移80002试计算这个程序执行时的CPI,MIPS和Tcpu。2．〔10分〕将IEEE754单精度浮点数3F880000H、C0A00000H转换成十进制数。3．〔15分〕设一模型机有8条指令，它们的使用频度如下表所示。请设计出指令的Huffman编码和只有两种码长的扩展操作码编码，求其平均码长和信息冗余量。〔H=2.35〕指令I1I2I3I4I5I6I7I8使用频度0.30.30.20.10.050.020.020.014．〔15分〕设某程序包含5个虚页，其页地址流为4，5，3，2，5，1，3，2，2，5，1，3。〔1〕为获得最高的命中率，至少应该分配给该程序几个虚页？其可能的最高命中率为多少？〔2〕假设在程序执行过程中每访问一个虚页，平均要对该虚页所在主存实页位置内的存储单元访问1024次，求访问主存存储单元的命中率。5．〔15分〕现有3段流水线，各段经过时间依次为Δt,3Δt,Δt。连续输入6个任务时，流水线的实际吞吐率、效率和加速比为多少？6．〔15分〕在三种类型〔字节多路、数组和选择〕的通道上各接有5台设备，每台设备需完成1024B数据传输。请分别求出这三种通道完成所有数据传输的总时间。(设TS=9.8us,TD=0.2us,K=512B。其中，TS为通道选择设备的时间,TD为通道完成一个字节的传送时间，K为定长数据块大小)7．〔15分〕在一个5功能段的流水线处理机上需经9△t才能完成一个任务，各段执行时间均为△t，任务处理过程对各段使用时间的预约表如下所示。T1T2T3T4T5T6T7T8T9S1√√S2√√S3√√√S4√√S5√√(1)画出流水线的状态有向图，并由状态图得出流水线的最优调度策略。(2)按最优调度策略输入6个任务，求流水线的实际吞吐率。(全部试题完)武汉大学计算机学院2010-2011学年度第一学期2008级《计算机系统结构》期末考试试卷〔B〕参考答案1．〔15分〕解：〔5分〕〔5分〕〔5分〕2．〔10分〕解：3F880000H=1.0625〔5分〕C0A00000H=-5〔5分〕3．〔15分〕解：哈夫曼树略。哈夫曼编码及扩展编码如下表：指令频度Pi哈夫曼编码码长扩展编码码长I10.3002002I20.3012012I30.2102102I40.11103110005I50.0511104110015I60.02111105110105I70.021111106110115I80.0111111161110054．〔15分〕解：〔1〕当主存的页面数n=4时，其命中率到达最大值。最大命中率为H=7/12=58.3%；〔10分〕〔2〕主存单元的命中率为：〔5分〕%5．〔15分〕解：由于第二个部件为流水线中的瓶颈，连续输入6个任务时，任务之间必然有间隔〔停顿〕存在，间隔的拍数取决于瓶颈部件的延迟时间。流水线工作示意图如下列图所示。〔6分〕__3___3_2_1_m02019181716151413121110987652143T(Δ02