系统结构作业2

3.1 解释下列名词（任选5个）

根据课件内容，选择以下5个常见名词进行解释：

1. 流水线技术 (Pipelining)：把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样每个子过程就可以与其他的子过程并行进行。
2. 吞吐率 (Throughput)：在单位时间内流水线所完成的任务数量或输出结果的数量。
3. 数据冲突 (Data Hazard)：当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们非流水实现时的顺序，从而发生的冲突（对应真数据相关）。
4. 结构冲突 (Structural Hazard)：因硬件资源满足不了指令重叠执行的要求而发生的冲突。例如功能部件不是完全流水或资源份数不够。
5. 换名技术 (Register Renaming)：通过改变指令中操作数的名来消除名相关（反相关和输出相关）的技术。对于寄存器操作数进行换名称为寄存器换名。

---

3.3 简述通过软件（编译器）来减少分支延迟的三种方法，这些方法的共同特点是什么？

三种方法：

1. 消除分支：用条件执行指令（或flag条件判断）替换分支指令，从而在根本上消除分支带来的延迟。
2. 预测执行——预测分支失败（Predict Not Taken）：允许分支指令后的指令继续在流水线中流动，就像没发生分支一样。若确定分支失败，则流水线正常流动；若确定分支成功，则把分支指令后取出的指令转化为空操作，并按分支目标重新取指。
3. 延迟分支 (Delayed Branch)：在分支指令后面加上若干条指令（即延迟槽），把它们看成一个整体。不管分支是否成功，都顺序执行这些延迟槽中的指令，以此来掩盖分支延迟。

共同特点： 这几种方法对分支的处理策略在程序的执行过程中始终是不变的，是静态的（由编译器在编译时决定）。要么总是预测分支成功，要么总是预测分支失败。

---

3.4 简述延迟分支方法中的三种调度策略的优缺点。

在延迟槽中放入有用指令的三种调度策略及其优缺点（或适用条件/效果）如下：

1. 从前调度（首选策略）：
   • 要求：被调度的指令必须与分支指令的条件判定无关。
   • 优缺点：最理想的策略，无论分支成功与否都能起作用，不会增加额外开销。
2. 从目标处调度：
   • 要求：必须保证在分支失败时，执行被调度的指令不会导致错误（相当于静态预测分支成功）。
   • 优缺点：在分支成功时起作用；缺点是可能需要复制指令，有可能会增大程序代码的空间。
3. 从失败处调度：
   • 要求：必须保证在分支成功时，执行被调度的指令不会导致错误（相当于静态预测分支失败）。
   • 优缺点：只有在分支失败时才起作用，适用于大概率不发生跳转的条件分支。

---

3.11 在 MIPS 流水线上运行代码序列

循环次数分析： R3的初值是R2 + 396，每次循环R2递增4。退出条件是DSUB R4, R3, R2产生的R4 == 0。 共需执行 $396 \div 4 = 99$ 次循环。

(1) 无定向硬件，排空流水线处理分支（即必须等到写回才读取，分支在MEM段修改PC）

• LW 到 DADDIU R1：发生RAW，无定向需停顿2拍。
• DADDIU R1 到 SW：发生RAW，需停顿2拍。
• DADDIU R2 到 DSUB：发生RAW，需停顿2拍。
• DSUB 到 BNEZ：发生RAW，需停顿2拍。
• BNEZ 采用排空流水线，在 MEM 段更新 PC，产生3拍的分支延迟。 时钟周期计算：单次循环的间隔为 $1(\text{基础}) + 2\times4(\text{四个RAW停顿}) + 3(\text{排空分支延迟}) + 5(\text{指令数}) = 17$ 个周期。 执行 99 次循环，前 98 次每次启动间隔 17 个周期。第 99 次最后一条指令(BNEZ)写回完成需要 $1 + 98 \times 17 + 17$ (即最后一次本身需要的17拍执行完加排空) $- 1 = 1684$ 个时钟周期。

(2) 正常定向路径，预测分支失败（条件测试在 ID 段进行）

• LW 到 DADDIU R1：Load-use 冲突，利用定向仍需停顿1拍。
• DADDIU R1 到 SW：EX 到 EX 定向，无需停顿。
• DADDIU R2 到 DSUB：EX 到 EX 定向，无需停顿。
• DSUB 到 BNEZ：BNEZ在 ID 段需要判断条件，DSUB在 EX 段产生结果，EX 到 ID 定向需停顿1拍。
• BNEZ 预测失败，但实际跳转成功。在 ID 段(第2拍)解析出目标，清除后面错取的1条指令，产生1拍延迟。 时钟周期计算：单次循环的间隔为 $6(\text{指令}) + 1(\text{Load-use}) + 1(\text{DSUB至ID}) + 1(\text{预测失败冲刷}) = 9$ 个周期。 共需 $98 \times 9 + 12(\text{最后一次循环BNEZ写回所需总拍数}) = 894$ 个时钟周期。

(3) 正常定向路径 + 1个延迟分支槽，重新组织指令 采用从前调度，将 SW R1, 0(R2) 移动到延迟槽中（注意此时 R2 已经提前加了4，所以偏移量需改为 -4），并将不会引发停顿的指令穿插以消除数据相关： 调度后的代码：

LOOP: LW    R1, 0(R2)
      DADDIU R2, R2, #4      ; 提前执行，避免与DSUB产生停顿
      DSUB  R4, R3, R2
      DADDIU R1, R1, #1      ; 插入LW和SW之间，且距离LW足够远，消除Load-use停顿
      BNEZ  R4, LOOP         ; 分支判断
      SW    R1, -4(R2)       ; 延迟槽指令，偏移量修正为-4

时钟周期计算：调度后所有数据冲突均被定向机制完美消除（Load-use 距离被拉开，DSUB到BNEZ的距离也被拉开），且延迟槽吸收了分支延迟，全程无任何停顿。 每次循环耗时刚好是指令条数，即 6 个周期。 共需 $98 \times 6 + 10 (\text{最后一次SW写回完毕}) = 598$ 个时钟周期。

---

3.12 加速比计算

题意解析：

• 理想情况（无控制相关）：每周期执行一条指令，理想 $\text{CPI} = 1$。
• 实际情况（有控制相关）：流水线段数为 4 段。
  • 条件分支 (CB) 占 20%，其中 60% 成功 (Taken)，40% 失败 (Not Taken)。条件分支在第 3 周期（EX段结束）解析，若采用默认的预测失败机制（题干给出成功率即暗示预测失败策略），失败时无惩罚，成功时需冲刷已取出的指令，惩罚为 2 个时钟周期。
  • 无条件跳转 (UB) 占 5%，在第 2 周期（ID段结束）解析，因必然跳转，冲刷已取出的指令，惩罚为 1 个时钟周期。

计算过程：

1. 分支指令带来的平均停顿周期（Penalty）： \(\text{Penalty} = (20\% \times 60\%) \times 2 + 5\% \times 1 = 0.12 \times 2 + 0.05 = 0.24 + 0.05 = 0.29\)
2. 存在控制相关情况下的实际 $\text{CPI}$： \(\text{CPI}_{\text{实际}} = \text{CPI}_{\text{理想}} + \text{Penalty} = 1 + 0.29 = 1.29\)
3. 无控制相关相对于有控制相关的加速比： \(\text{Speedup} = \frac{\text{CPI}_{\text{实际}}}{\text{CPI}_{\text{理想}}} = \frac{1.29}{1} = 1.29\)

答： 在没有任何控制相关的情况下，该流水线相对于存在上述控制相关情况下的加速比是 1.29。