案例研究：动态调度

案例与习题作者：Jason D. Bakos。

本案例研究考察以下简单循环在运行时的行为：

loop: fld f2,0(x2)       # 加载 guess
      fmul.d f4,f2,f2    # temp = guess^2
      fsub.d f4,f4,f0    # temp = temp - s
      fmul.d f6,f2,f8    # temp2 = guess * 2
      fdiv.d f4,f4,f6    # temp = temp/temp2
      fsub.d f2,f2,f4    # temp = guess - temp
      fsd f2,0(x2)       # 存储 guess
      addi x1,x1,-1     # 递减计数器
      addi x2,x2,8      # 递增地址
      bne x1,zero,loop  # 循环

这个循环执行一次 Newton–Raphson 迭代，以求出 $x^2-s$ 的根。假定：

• $s$ 保存在寄存器 f0 中。
• 常数 2.0 保存在寄存器 f8 中。
• 迭代次数保存在 x1 中。
• 输入数组的基地址保存在寄存器 x2 中。

习题 3.1

[15] 〈3.3, 3.6〉 在单发射、顺序执行 CPU 上执行这个循环体，需要多少个周期？假定：

• 加载延迟为 4 个周期，即产生结果与使用结果的指令之间，至少需要插入 3 个周期。
• 浮点指令延迟为 5 个周期。
• 整数指令延迟为 2 个周期。
• 分支在 4 个周期内确定结果。
• 存储的有效延迟为 0 个周期。
• 依赖指令可以在最后一条为其产生输入的指令完成的同一周期发射，并且转发总线数量无限。
• 最后完成提交的那条指令所在的周期，视为循环完成的周期。

请填写类似下表的表格来解答：

习题 3.2

[5] 〈3.3, 3.6〉 在你对 3.1 的解答中，CPU 发射了指令的周期占总周期的百分之几？

习题 3.3

[15] 〈3.3, 3.6〉 假定 CPU 可以乱序发射、乱序提交指令，但每周期只能派发一条指令，也只能提交一条指令。

如果同一周期有不止一条指令准备好派发或提交，取指最晚的那条必须停顿。暂时假设寄存器自动重命名，以避免 WAR 和 WAW 名依赖引起的不一致。后面的问题将考察这是否必要。

执行该循环体需要多少个周期？请使用与 3.1 类似的表格。

习题 3.4

[5] 〈3.3, 3.6〉 在你对 3.3 的解答中，CPU 发射了指令的周期占总周期的百分之几？

习题 3.5

[15] 〈3.4, 3.6〉 现在假定可以对分支进行推测，分支预测器的准确率为 100%。在分支之后取到的指令，可以在分支结果确定之前派发，但必须等到分支结果确定之后才能提交。

执行两次迭代时，平均每次迭代需要多少个周期？请使用与 3.1 类似的指令调度表解答。

习题 3.6

[5] 〈3.4, 3.6〉 在你对 3.5 的解答中，CPU 派发了指令的周期占总周期的百分之几？

习题 3.7

[15] 〈3.5〉 假定每条指令的目标寄存器，从该指令提交的周期开始，到最后一条依赖于它的指令派发为止，都视为“存活”（live）。

对于你在 3.5 中得到的调度，找出寄存器 x1、x2、f2、f4、f6 的存活周期区间。

习题 3.8

[10] 〈3.5〉 你在 3.7 中得到的寄存器生存期，是否说明代码存在某些名依赖（WAR、WAW），会在当前动态指令顺序下引起问题？为什么？

习题 3.9

[15] 〈3.3, 3.6〉 现在假定目标体系结构支持双发射、双提交，并具有无限大的指令窗口，可以从中选取指令调度。执行两次迭代时，平均每次迭代需要多少个周期？

习题 3.10

[5] 〈3.6〉 在你对 3.9 的解答中，发射槽位的利用率是多少？

习题 3.11

[5] 〈3.6〉 3.9 的性能结果是否符合你的预期？为什么？