计算机系统结构 习题集4 2002春 学生每三人分成一个小组合作完成作业。每组只诺要文一份该习思的答案。在顶定课程开始的时候， 会布置作业。为了便于译分，各种习题必须独立分类。而且将你最近参加的组号标在对应的间避上面. (如果你的知号己经改变，请明疏的指出，我们将为你分配新的组号。)参考答案经发做，我们将不 身按收业， 习恶一：置序调度 Ben Bitdiddle将一个浮点数单元知入到一个基本的DLX流水中，也已经在BM3609I的了点数单元 的基础上完成了阁纸设计。他的设计包括·个加法拾，·个乘法券和·个存储单元。法器有一个2川则 的廷时并且是全蓬水的，束法器有个觉则的延退并且是十流水前。存储单元有·个很长的延迟并且是 全欲水的，它按序处理所有的存结请求。 有四个浮点寄存#，0F3他们独立于整型寄存松。有一个单精口的写巫回精口至浮点寄存华如。 在写返回神突时。较早的指令先被写回。就像在讲义中所解释的一样，深点指令必须花贵一个周期在写 返回除受，结果才可用。山是。型结果西常在可一月期内就可用。 Bn现在正在考地采用(a)基于计分板的按序发射，(b》乱序发射，或者(e)带寄存器盈金名 的乱序发射。也最喜欢的基测试是这个内循环〔最后一条指令存在一个转移延退槽上)。你的任务是评 估这三种透抒方案。 10op: 11 LE F0,A{R2) MULTF F3,F1,F2 ADDE E3,E3,F0 I4 SE B(R2),F3 Is LF F1,C(R2) I6 MULTF F3,F0,F2 I ADDE E3,E3,E1 Io SF D(R2),F3 I BNEZ R2,loop 110 ADDI R2,R2,t-8
计算机系统结构 习题集 4 2002 春 学生每三人分成一个小组合作完成作业。每组只需要交一份该习题的答案。在预定课程开始的时候， 会布置作业。为了便于评分，各种习题必须独立分类。而且将你最近参加的组号标在对应的问题上面。 （如果你的组号已经改变，请明确的指出，我们将为你分配新的组号。）参考答案一经发放，我们将不 再接收作业。 习题一：乱序调度 Ben Bitdiddle 将一个浮点数单元加入到一个基本的DLX流水中。他已经在IBM 360/91的浮点数单元 的基础上完成了图纸设计。他的设计包括一个加法器，一个乘法器和一个存储单元。加法器有一个2周期 的延时并且是全流水的。乘法器有一个3周期的延迟并且是非流水的。存储单元有一个很长的延迟并且是 全流水的，它按序处理所有的存储请求。 有四个浮点寄存器，F0-F3.他们独立于整型寄存器。有一个单端口的写返回端口至浮点寄存器组。 在写返回冲突时，较早的指令先被写回。就像在讲义中所解释的一样，浮点指令必须花费一个周期在写 返回阶段，结果才可用。但是，整型结果通常在同一周期内就可用。 Ben 现在正在考虑采用 （a）基于计分板的按序发射，（b）乱序发射，或者（c）带寄存器重命名 的乱序发射。 他最喜欢的基测试是这个内循环（最后一条指令存在一个转移延迟槽上）。你的任务是评 估这三种选择方案。 1
问题1.入 基于计分板的顺序发射 问题1.B 乱序发射 的指令没有与冲突，那么在译假 R 问题1.C 奇存器重命名 代的 在可0 2
问题1.A 基于计分板的顺序发射 填写表A中的计分板（见幻灯片L11－30）来模仿该循环一次迭代的执行过程。假设读花费n个周期 （n是一个很大的数），写回需要再加一个周期。空出表中的一行来填写等待装入结果花费的时间。要记 得的是，在这个方案中，不会发出和以前的还没有被写回的指令具有写写冲突的指令（正如讲稿中所说）。 问题1.B 乱序发射 现在考虑一个单一发射的乱序实现（见幻灯片L12－3）。在这个方案中，发射阶段缓冲器存贮着多个 等待发射的指令。译码段能够每个时钟周期向发射缓冲器加入一个指令。如果发射缓冲器还有空间并且该 指令与以前没有发射的指令没有读写冲突，或者与以前还没有写回的指令没有写写冲突，那么在译码段， 就将该指令加入发射缓冲器。此处假设你有一个无限大的发射存储器。 表B描述循环处于就稳定态时一次循环的迭代执行过程。填写每个指令发射或写回时所用的周期数。 表的第一行已经为你填好了，请将表的剩余部分填满。要注意所列指令的顺序并不一定要是指令的发射顺 序。我们定义循环I1 指令发射的时间为周期0。同时假设装入需要n个时钟周期。如果读写单元充分流水化， 你不必担心n的值会导致结构上的冲突。 在表B中，用箭头画出包含在循环的关键路径中的相关关系。多个迭代能否重叠执行？ 问题1.C 寄存器重命名 ISA中的寄存器数目限制了能够进入流水线的指令的最大数目。这个习题研究如何用寄存器重命名来 解决这一问题。在这个问题中，我们采用一个理想化的模型，即我们有无限的资源用于重命名寄存器。 表C显示了基程序中执行两个迭代的指令，使用和表B中相同的格式。首先，在需要的地方给每个指令填写 一个新的寄存器名字，考虑到我们有无限的资源用于寄存器重命名，当需要重命名一个寄存器时，每次你 都需要使用一个未用过的名字（T0,T1,T2，等等）。要注意当一个寄存器被重命名后，随后使用该寄存器 的指令都需要指向新的寄存器名。你会发现创建自己的重命名表很有帮助。只对浮点型指令进行重命名。 接着，填写每个指令发射或写回时所需的时钟周期数。译码阶段能够每个时钟周期向ROB加入一条指令。 假设指令I2在周期0译码，直到周期1才发射。同时假设装入需要n个时钟周期，而且ROB是无限大的。 对于两次迭代，在哪一个时钟周期最后发射的指令发射？在哪一个时钟周期最后被发射的指令发射，用于 1000次迭代？性能瓶颈是什么？ 2
问题1D 发 3
问题 1.D Tomasulo的算法 考虑一个使用Tomasulo算法的乱序发射（见幻灯片L12－12）。在这个方案中，没有单独的浮点指令队 列（ROB）。浮点指令从取指令直接到达其中一个预留站。如果没有空间，取指令阶段停滞。如果在预留站 中多条指令都能够被发射，则发射最早的一条。 不同于以前的问题，在每个预留站里都有固定个槽，这限制了能够被重命名的寄存器个数。假设我们为 加法预留站提供了三个槽，为乘法站提供两个槽，为存储器提供三个槽，为装入器提供六个槽。 在基程序中多少个迭代能够重叠执行？如果有指令同时来自于同一预留站的不同迭代，或者来自于不同 的预留站，我们定义两个迭代是重叠的。假设n是一个很大的数（n>100）。 最少需要为乘法预留站提供多少槽来获得尽可能大的性能？假设其他所有的站都有无限的槽。 3
同愿：装移须型防火人州-个标准共食斯制星的发，休习道中，敏XS在 b1: 器：品 b2: BNEZ R1,1o0p 2保的结果) ?设在B中地1利2不冲突、 图：BP比特我态图 学子升么？和成是2当环洁束，贮的什 4
问题2：转移预测 这个习题研究将全局历史位加入到一个标准转移预测机制里的效果。在本习题中，假设DLX ISA不存在 延迟槽。 整个习题的讨论都使用下面这个程序。 假设R1的初始值是n（n>0） 假设R2的初始值是0（R2保存程序的结果） 假设R3的初始值是p（p是一个指向32比特整型数组起始位置的指针） 在习题中，我们将采用一个2位的预测状态机（见幻灯片L13－11）。 在状态1X，我们猜不发生；在状态0X，我们猜发生。 假设在BHT中b1和b2不冲突。 图1：BP 比特状态图 问题2.A 程序 该程序计算了什么？也就是说，当循环结束，R2的值是什么？ 4
间题2.B 两位转移顶测 人不高品成，·来中的移验水自于m,如和线标，成效 使用一个全局历史位的转移预 问题2.D 使用两个全局历史位的转移预测 句题2.E 分桥1 器器器牛器 问感2.F 分桥2 当另外的历史位有月且对你有害时。这告诉了你什么？
问题2.B 两位转移预测 现在我们要研究我们的标准两位历史转移预测究竟表现如何。假设程序的输入是n=8 and p[0] = 1, p[1] = 0, p[2] = 1, p[3] = 0…等等；也就是说数组的元素值呈现交替的0或1。填写表1（注意前几行已经帮你填好了）。 误预测的次数是多少？ 表1包含每次转移被执行时的入口（或者b1或者b2），表中的转移预测位来自于BHT。如果b1被执行，就填 入BHT中的b1位。如果b2被执行，就填入BTH中的b2位。 问题2.C 使用一个全局历史位的转移预测 现在我们向转移预测中加入一个全局历史位（见幻灯片L13－13）。填写表2，用同样输入执行该程序， 给出总的误预测数。 问题2.D 使用两个全局历史位的转移预测 现在我们向转移预测中再加入一个全局历史位（见幻灯片L13－14）。填写表3，再次用同样输入执行该 程序，给出总的误预测数。 问题2.E 分析1 比较来自问题2.B,2.C和2.D的结果。在每个情况中，误预测什么时候最易发生？（例如在开始，周期性的， 还是在结束时）? 这一结果在总体上告诉你关于全局历史位的什么特征？对于一个大数n，那种情况性能最好？ 简单解释一下。 问题2.F 分析2 在这个习题中，我们采用的是常规输入。如果输入是随机的（数组元素为0或为1的概率是相等的）， 你预测情况会有什么变化？在我们研究的三种转移预测中，哪种预测在这样的输入下性能更好？对于n 很大或者n很小的情况，你的答案相同吗？ 当另外的历史位有用且对你有损害时，这告诉了你什么？ 5
问题3 寄存器重命名和静态VS动态调度 下面的DLX代算了点表达在=AB+C-D的能，A.CD和E相应的储RL.2R.R4和R F0,0(R1】 间题3.A 筒单流水线 、十歌热的照入所促典是米花态一 问感3.B 静态调度 问题3.C 少量寄存器 间感3，D 寄存器型命名和动态调度 6
问题3：寄存器重命名和静态VS动态调度 下面的DLX代码计算了浮点表达式E = A * B + C – D的值，A, B, C, D和 E相应的存储在R1, R2, R3, R4和R5 中。 问题3.A 简单流水线 计算在一个简单按序流水机上，该代码序列执行所需的周期数（也就是说，从第一个被装入的指令到最后 一个被装入的指令之间的时钟周期）。假设装入延迟为两个周期，浮点乘法有四个周期的延迟。其他浮点算术 操作有两个周期的延迟。向浮点寄存器写回有一个周期的延迟。同样假设所有的功能模块都充分流水化并且忽 略写回冲突。给出第一个被装入的指令到最后一个被装入的指令之间的周期数。 问题3.B 静态调度 按代码序列重新排序指令，使执行时间最小。给出新的指令序列并且给出这个序列在简单按序流水 线上执行所花的周期数。 问题3.C 少量寄存器 重写代码序列，但是这次只使用两个浮点寄存器。优化以达到最短运行时间。总体上说，当寄存器不足 以完成计算任务时，编译器会使用临时的内存单元来存放中间值，在这个方案中有一个称为寄存器溢出的进 程，使得你不许要让任何寄存器溢出。列出代码序列并给出执行所需的周期 问题3.D 寄存器重命名和动态调度 现在模拟带寄存器重命名和乱序发射的原始代码在单一发射机上的运行结果。忽略除了每个周期内 单一指令译码冲突以外的其他所有结构冲突。给出程序是如何执行的，并且给出所需的周期数。比较本 代码与3.B中的优化后的代码。 6
问题4：寄存器生命周期 给出下列指令好列： r;2 增加RL位 Instruction Sre1 RL Bit Sre2 RL Bit 给定存器的生金明包，我们现在尝试优化寄器重金名技术。如12所描述的
问题4：寄存器生命周期 对于这个问题，我们引入一个方案，即指令中每一个源寄存器标识符都有一个额外的寄存器生命周期位 （由编译器设置），来指出相应的指令是最后需要某个特定寄存器值的指令。也就是说，当没有其他指令重 新写入一个新值之前，是不会由指令读该寄存器的。 给出下列指令序列： 问题4.A 增加 RL 位 请创建一个如下所示的表格，并标出哪些寄存器的生命周期位能够被上面所给的代码设置。对只有一 个源操作数的指令，使用Src1栏。 给定寄存器的生命周期位，我们现在尝试优化寄存器重命名技术。如12讲所描述的。 7
问惠4B 释放物理将存器 是说.瓷告的开食物理专台（电 问题4C 新的寄存器解分配策 有什发爱式库有生州验火装现险能反生群不程青行省货货中 问题4.D 生命雨期位的好处 Sequence C 2: Sequence B 2,R3 I3:ADD R2,R1,R3 8
问题4.B 释放物理寄存器 在第十四讲中讲解的物理寄存器文件重命名方案，什么时候能够安全的释放物理寄存器？（也就 是说，什么时候能够将该寄存器放入释放列表并能够重新为新的重命名使用）。 问题4.C 新的寄存器解分配策略 假设现在我们使用寄存器生命周期位来提高机器的性能。简要解释一下物理寄存器的释放时间在该策略中 有什么变化？ 问题4.D 生命周期位的好处 在下面的代码序列中，带下划线的操作数表示相应的寄存器生命周期位已经被设置。画出任何该位已被设 置而且能导致与仅仅采用原始的寄存器重命名策略相比，微处理器能够更早重命名I3以后的其他指令的代码序 列。假设CPLX指令是一个需要花费很多时钟周期的延迟很长的操作。解释一下你的选择。 8
间题5：别名&同名异义 布处与适有惠洗程的原被加个只有主车引，虚都标签，因路并联并且可写的娱有。假股户 问题5A 问题5R 我们能否遇过将级存为写直西级存来逐免出现名问墨？请解释。 问题5 华热都票将a流为接政时关业明名何：加果采细皮装，米时充回合 问题5E 不清的决园的鞋是风：筑牛析 问题5F 我们能香通过使用盛拟案引，钓理标签缓存来解决同名异义问恩？解释 间愿5.G 品智品 9
问题5：别名&同名异义 考虑向运行多进程的系统中添加一个具有虚拟索引，虚拟标签，四路并联并且可写回的缓存。假设TLB 和处理器都是用地址空间标识符。 问题5.A 当不同的虚拟地址指向同一个物理地址时，出现同名问题，也称为别名问题（即可出现在单一处理器上， 也可以出现在多处理器上）。举一个由于出现同名而导致严重错误的简单例子。 问题5.B 我们能否通过将缓存改为写直通缓存来避免出现同名问题？请解释。 问题5.C 我们能否通过将cache改为直接映射来避免出现同名问题？如果采用直接映射，采用写直通和写回是否一 样？请解释。 问题5.D 如果采用虚拟索引，物理标签的cache，我们是否仍然面对同名问题？请解释。 问题5.E 当两个进程使用同样的虚拟地址想访问不同的物理位置时，会出现同名异义的问题。解决这一问题的一 个方法是在每次上下文切换时都清空缓存。Alyssa P. Hacker通过向每个cache行加入很少一部分信息，就可以 不清空缓存而解决同名异义问题，请简单解释一下如何能做到这一点。可以通过这一方法解决别名问题吗？ （假设使用的是原始的虚拟索引，虚拟标签的缓存） 问题5.F 我们能否通过使用虚拟索引，物理标签缓存来解决同名异义问题？请解释。 问题5.G Ben Bitdiddle指出别名问题和同名异义问题都能够通过将虚拟索引，虚拟标签的缓存替换为物理索引， 物理标签的缓存来解决。他的观点是否能够彻底解决这两个问题？使用虚拟索引缓存有什么缺点？请给 出简单解释。 9
Table A-problem 1.A 1山0F0