计算机体系结构 6.823期末考试 2002年春 姓名： 开卷考试 180分钟 22页 注意事项： ·试题难度不等，请先浏览整张试卷，把握好答题时间。 ●注意表述清楚你所做的假设。 ●在每张试卷上都写上姓名（你可以因此得到6分)。 ●字迹清楚。 姓名： 6分 Part A:(试题1-试题4) 20分 Part B:(试题5-试题7) 16分 Part C:(试题8-试题12) 24分 PatD:(试题13-试题20) 24分 Part E:(试题21-试题24) 31分 Part F:(试题25-试题27) 16分 Part G:(试题28一试题30) 12分 Part H:(试题31-试题37) 31分 总计： 180分
计算机体系结构 6.823 期末考试 2002 年春 姓名：_________ 开卷考试 180 分钟 22 页 注意事项： z 试题难度不等，请先浏览整张试卷，把握好答题时间。 z 注意表述清楚你所做的假设。 z 在每张试卷上都写上姓名（你可以因此得到 6 分）。 z 字迹清楚。 姓名:________ 6 分 Part A: (试题 1 －试题 4) ________ 20 分 Part B: (试题 5 －试题 7) ________ 16 分 Part C: (试题 8 －试题 12) ________ 24 分 Part D: (试题 13－试题 20) ________ 24 分 Part E: (试题 21－试题 24) ________ 31 分 Part F: (试题 25－试题 27) ________16 分 Part G: (试题 28－试题 30) ________ 12 分 Part H: (试题 31－试题 37) ________ 31 分 总计:__________ 180 分
姓名 PartA:复杂流水线技术(20分) 参照一个乱序的超标量系统结构的DLX处理器，它用一个专门的统一物理寄存器组来实现寄存 器一重命名调度（见第14章）。这种机器有128个物理的寄存器。而DLXISA有32个通用寄 存器和32个浮点寄存器。 问题1(4分) 空闲表中最大寄存器数目是多少？描述一种情形，其中最多寄存器数在空闲表中。 问题2(4分) 空闲表中最小寄存器数目指多少？描述一种情形，其中最少寄存器数在空闲表中。 问题3(6分) 在寄存器重命名和放置重命名后的指令到重新排序缓冲器之前，对于一条指令来说，下面哪种 条件需要检查？圈出所有影响一条指令是否能被放置到重新排序缓冲器的条件 A.此指令所需的功能单元是否正在使用 B. 空闲表中是否存在物理寄存器 C. 此指令是否会引发异常 D 此指令和之前存在于重新排序寄存器里的指令一起执行时是否会引起读写冲突 E. 此指令和之前存在于重新排序寄存器里的指令一起执行时是否会引起写写冲突 F. 是否有更多的、可用的重命名表瞬象 第2页/共22页 姓名 问题4(6分) 假设我们将指令MOVZ添加至DLXISA。 MOVZ的语义是指： MOVZ Rd,Rs1,Rs2;if(Rs2 ==0)then Rd <Rs1 如果Rs2的值等于零，将Rsl的内容放置到Rd。MOVZ是R型指令(R-type instruction?)。 如果用Part A开头提及的乱序超标量来实现MOVZ,会出现什么问题？ 第3页/共22页
姓名______________________ Part A: 复杂流水线技术（20 分） 参照一个乱序的超标量系统结构的 DLX 处理器，它用一个专门的统一物理寄存器组来实现寄存 器－重命名调度（见第 14 章）。这种机器有 128 个物理的寄存器。而 DLXISA 有 32 个通用寄 存器和 32 个浮点寄存器。 问题1（4分） 空闲表中最大寄存器数目是多少？描述一种情形，其中最多寄存器数在空闲表中。 问题2（4分） 空闲表中最小寄存器数目指多少？描述一种情形，其中最少寄存器数在空闲表中。 问题3 （6分） 在寄存器重命名和放置重命名后的指令到重新排序缓冲器之前，对于一条指令来说，下面哪种 条件需要检查？圈出所有影响一条指令是否能被放置到重新排序缓冲器的条件 A． 此指令所需的功能单元是否正在使用 B． 空闲表中是否存在物理寄存器 C． 此指令是否会引发异常 D． 此指令和之前存在于重新排序寄存器里的指令一起执行时是否会引起读写冲突 E． 此指令和之前存在于重新排序寄存器里的指令一起执行时是否会引起写写冲突 F． 是否有更多的、可用的重命名表瞬象 第2页/共22页 姓名_________________________________ 问题4（6分） 假设我们将指令MOVZ添加至DLXISA。 MOVZ的语义是指： MOVZ Rd,Rs1,Rs2; if (Rs2 = = 0) then Rd <- Rs1 如果Rs2的值等于零，将Rs1的内容放置到Rd。MOVZ是R型指令（R-type instruction？）。 如果用Part A开头提及的乱序超标量来实现MOVZ，会出现什么问题？ 第3页/共22页
姓名 Part B:Cache(16分) 考察一个物理索引的，虚拟标记的，组关联映射，采用写回法的Cache。变换后的物理地址的一 些位用于索引Cache,而未变换的虚拟地址一些位用来做标记。 虚拟页大小为2字节。Cache有2个组和2"路。每Cache行是2b字节。虚拟可寻址内存容量是22 字节，物理可寻址内存的容量也是22字节。 问题5(6分) 是否会出现别名问题吗？解释之。 问题6(6分) 根据k、L、b和w,写一个表达式，表示Cache行标记所需要的位数。 问题7(4分) 使用一个物理索引、虚拟标记的Cache:没有意义，为什么？ 第4页/共22页
姓名_________________________________ Part B：Cache（16分） 考察一个物理索引的，虚拟标记的，组关联映射，采用写回法的Cache。变换后的物理地址的一 些位用于索引Cache，而未变换的虚拟地址一些位用来做标记。 虚拟页大小为2k 字节。Cache有2L 个组和2w路。每Cache行是2b 字节。虚拟可寻址内存容量是232 字节，物理可寻址内存的容量也是232 字节。 问题5 (6分) 是否会出现别名问题吗？解释之。 问题6 (6分) 根据k、L、b和w，写一个表达式，表示Cache行标记所需要的位数。 问题7（4分） 使用一个物理索引、虚拟标记的Cache没有意义，为什么？ 第4页/共22页
姓名 Part C:转移预测（24分) 受深度流水线讲义的启发，Ben Bitdiddle.决定建立一个顺序的、单发射的、深度流水的、没有延 迟槽的DLX。他的设计用的是如下的流水线： IF1 IF2 IDI ID2 EX1 EX2 MAI MA2 WB 原始指令取(F)、指令译码(D)、执行(EX)及内存(MA)段都一分为二。指令取采用 单一的“预测不发生”策略，顺序地从指令内存中取指令，除非被已执行的转移重定向了。寄 存器组在第一个执行段(EX1)的开始被读入。 问题8(3分) 对此流水线，条件转移(BEQZ或BNEZ)预测转移发生，最小惩罚是多少（用周期数表示）？ 清楚地表述转移在哪一阶段确定。 问题9(8分) 为了改善处理器的性能，Bn决定添加动态转移预测。他在第一个指令译码阶段(IDl)加入了 BHT。指令从指令内存中顺序取得，除非被预测的或已处理的转移重定向了。 在下面的表中，对每一种情形，填入最小条件转移惩罚（用周期表示）。清楚说明你的答案所 用到的每一个假设。 Actual Branch Direction Predicted Branch Direction Taken Not Taken Taken Not Taken 第5页/共22页
姓名_________________________________ Part C: 转移预测（24分） 受深度流水线讲义的启发，Ben Bitdiddle决定建立一个顺序的、单发射的、深度流水的、没有延 迟槽的DLX。他的设计用的是如下的流水线： 原始指令取（IF）、指令译码（ID）、执行（EX）及内存（MA）段都一分为二。指令取采用 单一的“预测-不发生”策略，顺序地从指令内存中取指令，除非被已执行的转移重定向了。寄 存器组在第一个执行段（EX1）的开始被读入。 问题8（3分） 对此流水线，条件转移（BEQZ或BNEZ）预测转移发生，最小惩罚是多少（用周期数表示）？ 清楚地表述转移在哪一阶段确定。 问题9（8分） 为了改善处理器的性能，Ben决定添加动态转移预测。他在第一个指令译码阶段（ID1）加入了 BHT。指令从指令内存中顺序取得，除非被预测的或已处理的转移重定向了。 在下面的表中，对每一种情形，填入最小条件转移惩罚（用周期表示）。清楚说明你的答案所 用到的每一个假设。 第5页/共22页
姓名 问题10(3分) 使用这种方法的间接跳转(JR)的最小惩罚是什么（用周期表示）？清楚说明你答案里用到的 每一个假设。 问题11(4分) Louis Reasoner认为Ben可以通过将BHT移至第一个取指令阶段(IFI)来减少转移惩罚。这个观 点有什么不妥？ 第6页/共22页 姓名 问题12(6分) Ben用下面的基程序来评估将BHT加到阶段D1的好处（见PS4)。程序的输入是一个O/1交替出 现的序列(0101010..)。 ;R3的初始内容是指向32位寄存器队列开头的指针。 ;R1的初始内容是队列长度（大于0） :R2的初始值是0(R2将存放程序的结果) loop: LW R4,0(R3) ADDI R3,R3,#4 SUBI R1,R1,#1 b1: BEQZ R4,b2 ADDI R2,R2,#1 b2: BNEZ R1,loop 他使用与PS4中一样的2位预测器(L13-11),0X预测发生，1X预测不发生：
姓名_________________________________ 问题10（3分） 使用这种方法的间接跳转（JR）的最小惩罚是什么（用周期表示）？清楚说明你答案里用到的 每一个假设。 问题11（4分） Louis Reasoner认为Ben可以通过将BHT移至第一个取指令阶段（IF1）来减少转移惩罚。这个观 点有什么不妥？ 第6页/共22页 姓名_________________________________ 问题12（6分） Ben用下面的基程序来评估将BHT加到阶段ID1的好处（见PS4）。程序的输入是一个0/1交替出 现的序列(“0101010…”)。 ；R3的初始内容是指向32位寄存器队列开头的指针。 ；R1的初始内容是队列长度（大于0） ；R2的初始值是0（R2将存放程序的结果） 他使用与PS4中一样的2位预测器（L13-11），0X预测发生，1X预测不发生：
11 taken -taken taken taken 00 10 taken taken taken taken 01 不同于PS4中的BHT,Bn的BHT只有一项，在转移处理时更新。用上面的基程序，给定项的初 始值为“00”，BHT在稳定状态下平均预测精确度是多少？解释之。 第7页/共22页 姓名 PartD:向量计算机(24分) 下面的每个循环都被变换，运行在带向量寄存器向量计算机上。对每一种情况，求最大向量长 度（向量化代码时用到），并简要说明代码的哪些特征限制向量长度。 假设向量机拥有足够长的向量寄存器，不同的数组保存在内存的无重叠区域。所有操作数均 为整数。 问题13(3分) for (i=0;i<N;i++) c[i]=A[i]+B[i]: 问题14(3分) for (i=0;i<N;i++) A[1]=A[1]+A[i+1]:
不同于PS4中的BHT，Ben的BHT只有一项，在转移处理时更新。用上面的基程序，给定项的初 始值为“00”，BHT在稳定状态下平均预测精确度是多少？解释之。 第7页/共22页 姓名_________________________________ Part D: 向量计算机（24分） 下面的每个循环都被变换，运行在带向量寄存器向量计算机上。对每一种情况，求最大向量长 度（向量化代码时用到），并简要说明代码的哪些特征限制向量长度。 假设向量机拥有足够长的向量寄存器，不同的数组保存在内存的无重叠区域。所有操作数均 为整数。 问题13（3分） 问题14（3分）
问题15(3分) for(i=1;1<N+1;i++) A[i]=A[i]+A[i-1]: 问题16(3分) for(1=13;1<N+13:i++) A[1]=A[i]+A[i-13]: 第8页/共22页 姓名 问题17(3分) for (i=0;i<N;i++) A[i]=A[i]+B[c[i]]: 问题18(3分) for (i=0;i<N;i++) A[i]=A[C[i]]+B[i]: 问题19(3分) for (i=0;i<N;i++) AA B[i];//A is a scalar variable
问题15（3分） 问题16（3分） 第8页/共22页 姓名_________________________________ 问题17（3分） 问题18（3分） 问题19（3分）
问题20(3分) for (j=0;j<N;j++) for(i=0;i<M;1++) A[i][j]=A[i][j]+B[i][j]; 第9页/共22页 姓名 Part E:Cache-一致性更新协议(31分) 在PS6-3中，我们考查了Cache一致的分布式共享存储器系统。Ben想把基于目录的Cache一致 性无效协议转换为更新协议。他提出如下方案。 Cache采用写直达法，无写分配。当处理器要写某内存单元时，将存储请求和要写入的数据字- 起发给主站点。主站点更新内存，并将更新的请求和新的数据发给每个缓存该块数据的站点， 除非该站点是正在处理存储的处理器，这种情况，它发送一个包含新数据的存储-应答。 如果正在执行存储程序的处理器要缓存正被写的块，它就必须等待主站点的回复，然后才能将 新的值写入Cache。如果处理器没有缓存正在被写的的块，它就可以在发出存储请求后执行。 注意这里的存储请求意义和用法与PS6里的协议是不同的。同时要注意存储请求和更新请 求包含的数据都是字粒度的，而非块粒度的。 在此方案里，内存里数据总是最新的，像C-修改、H-修改和H过渡这样的表述不再使用。 像PS6中一样，互联网络保证了报文传送是可靠的，而且不存在死锁、活锁和饥饿（长期得不 到资源)情况。同样和PS6一样，报文传送时采用FFO算法。每个主站点维护到来请求的FIFO 队列，并按照接收的顺序处理它们。 问题21(5分) Alyssa声称Bn的协议并不能保持顺序一致性，因为它允许两个处理器以不同的次序读取存储内 容。描述这个问题发生的一个场景。 第10页/共22页
问题20（3分） 第9页/共22页 姓名_________________________________ Part E: Cache一致性更新协议（31分） 在PS6-3中，我们考查了Cache一致的分布式共享存储器系统。Ben想把基于目录的Cache一致 性无效协议转换为更新协议。他提出如下方案。 Cache采用写直达法，无写分配。当处理器要写某内存单元时，将存储请求和要写入的数据字一 起发给主站点。主站点更新内存，并将更新的请求和新的数据发给每个缓存该块数据的站点， 除非该站点是正在处理存储的处理器，这种情况，它发送一个包含新数据的存储-应答。 如果正在执行存储程序的处理器要缓存正被写的块，它就必须等待主站点的回复，然后才能将 新的值写入Cache。如果处理器没有缓存正在被写的的块，它就可以在发出存储请求后执行。 注意这里的存储请求意义和用法与PS6里的协议是不同的。同时要注意存储请求和更新请 求包含的数据都是字粒度的，而非块粒度的。 在此方案里，内存里数据总是最新的，像C-修改、H-修改和H-过渡这样的表述不再使用。 像PS6中一样，互联网络保证了报文传送是可靠的，而且不存在死锁、活锁和饥饿（长期得不 到资源）情况。同样和PS6一样，报文传送时采用FIFO算法。每个主站点维护到来请求的FIFO 队列，并按照接收的顺序处理它们。 问题21（5分） Alyssa声称Ben的协议并不能保持顺序一致性，因为它允许两个处理器以不同的次序读取存储内 容。描述这个问题发生的一个场景。 第10页/共22页
姓名 问题22(16分) 注意到很多商用系统并没有保证顺序一致性，Bn决定用任一方法实现它的协议。根据提出的方 案填下面的状态转换表。我们用k来表示发出接收到消息的站点。 No. Current State Event Received Next State Action 1 C-invalid Load C-transient load-request→home 2 C-invalid Store 3 C-invalid update-request 4 C-shared Load C-shared processor reads cache 5 C-shared Store 6 C-shared Replace C-invalid nothing 7 C-shared update-request 8 C-transient load-reply C-shared data cache,processor reads cache 9 C-transient store-reply 10 C-transient update-request 表l:Cache状态转换表 No. Current State Message Received Next State Action 1 H-uncached load-request H-shared[] load-reply→k 2 H-uncached store-request 3 H-shared[.S] load-request H-shared[S] load-reply→k H-shared[S] store-request 表2：局部目录状态转换表 第11页/共22页
姓名_________________________________ 问题22（16分） 注意到很多商用系统并没有保证顺序一致性，Ben决定用任一方法实现它的协议。根据提出的方 案填下面的状态转换表。我们用k来表示发出接收到消息的站点。 表1：Cache状态转换表 表2：局部目录状态转换表 第11页/共22页
姓名 问题23(5分) 在系统用这个协议运行一段时间后，Ben发现网络被更新请求淹没了。Alyssa说这是协议的一个 缺陷。问题出在哪里？怎么修正？ 问题24(5分) 就像在PS6中，FFO消息传送是保证协议正确性的前提假设。如果网络不是FFO,那么就可能 处理器无法读取到别的处理器存储的结果。描述这种问题可以发生的场景
姓名____________________ 问题23（5分） 在系统用这个协议运行一段时间后，Ben发现网络被更新请求淹没了。Alyssa说这是协议的一个 缺陷。问题出在哪里？怎么修正？ 问题24 (5分) 就像在PS6中，FIFO消息传送是保证协议正确性的前提假设。如果网络不是FIFO，那么就可能 处理器无法读取到别的处理器存储的结果。描述这种问题可以发生的场景