# 案例研究：动态调度
案例与习题作者：Jason D. Bakos。

<!-- source: p0292 -->

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

~~~asm
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 {#exercise-3-1}

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

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

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

| 编号 | 指令 | 依赖于 | 使用该结果的指令 | 就绪周期 | 派发周期 | 完成周期 | 提交 / 分支确定周期 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | fld f2,0(x2) | | | | | | |
| 1 | fmul.d f4,f2,f2 | | | | | | |
| 9 | bne x1,zero,loop | | | | | | |
{.wide .expand}

### 习题 3.2 {#exercise-3-2}

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

### 习题 3.3 {#exercise-3-3}

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

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

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

### 习题 3.4 {#exercise-3-4}

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

### 习题 3.5 {#exercise-3-5}

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

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

### 习题 3.6 {#exercise-3-6}

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

### 习题 3.7 {#exercise-3-7}

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

<!-- source: p0294 -->

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

### 习题 3.8 {#exercise-3-8}

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

### 习题 3.9 {#exercise-3-9}

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

### 习题 3.10 {#exercise-3-10}

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

### 习题 3.11 {#exercise-3-11}

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