1. Introduction to Instruction-Level Parallelism

1.1. Terminologies

• 时延(latency)：单个指令从进入流水线开始，到它完成执行并可以写会结果所需要的时钟周期数．

  • 功能单元时间(function unit time)：指指令在 EX/MEM 阶段的 latency．

  • $\text{latency } = \text{ function unit time } - 1$．

• 启动间隔(initiation interval)：一个功能单元需要经过多少个时钟周期才能被重新使用．

  • 对于 完全流水线的(full pipelined) 功能单元：$\text{initiation interval } = 1$．

  • 对于 非流水线的(non-pipelined) 功能单元：$\text{initiation interval } = \text{ latency } + 1$．

浮点数流水线中功能单元的时延与启动间隔

这里 FP add 是四级流水线（$\text{latency } = \text{ function unit time } - 1 = 3$），并且是完全流水线的（说明启动间隔为 $1$）功能模块．

• 基本块(basic block)：一段连续的、直线执行的代码．只有一个入口和一个出口，没有分支．

2. Dependencies & Hazards | 依赖与冒险

2.1. Structural Hazards | 结构冒险

2.1.1. Structural Hazards for the FP Register Write Port | 浮点数寄存器写端口结构冒险

• 浮点数流水线（顺序发射、顺序执行、乱序完成(out-of-order complete)）导致的结构冒险问题：

  • (1) 单个时钟周期内多个 WB 操作．

  • (2) 写回顺序被打乱导致冒险．

• 解决方法一：增加写端口的数量，从而允许一个时钟周期内执行多个 WB 操作．、

• 解决方法二：通过移位寄存器，在指令译码阶段跟踪写端口的使用——因为在静态调度流水线中，必定是顺序执行的，且在译码阶段已经可以计算需要 stall 几个周期，因此也可以直接结算处在什么时候写回．

• 解决方法三：在指令试图进入 MEM 或 WB 阶段时进行 stall，在托马斯路等算法中可能再次用到．

2.2. Data Hazards | 数据冒险

2.2.1. RAW Dependences

• 读后写依赖(read-after-write dependency, RAW dependency)，又称 真数据依赖(true data dependency)．

• 一般来说，只能通过 forwarding 或 stall 来解决．

通过 stall 解决 RAW 冒险

2.2.2. WAW Dependences

• 写后写依赖(write-after-write dependency, WAW dependency)，又称 输出依赖(output dependency)，是 命名依赖(name dependency) 的一种．

• WAW 和 WAR 这两种命名依赖都可以通过重命名寄存器的方式解决．

通过 stall 解决 WAW 冒险

• 解决方法一：取消掉前一条指令的 WB 阶段，可以在 ID 阶段进行检测．

• 解决方法二：检测到冲突时阻滞在 ID 阶段（即后文小结的方法）．

2.2.3. WAR Dependences

• 写后读依赖(write-after-read dependency, WAR dependency) 又称 反依赖(anti-dependency)，是 命名依赖(name dependency) 的一种．

• 在大部分顺序发射、顺序执行的流水线（称为 顺序流水线(sequential pipeline)）中，因为是顺序读取（一般都是尽可能早的读取出值），不会出现 WAR 冒险．

小结：顺序流水线解决结构冒险与数据冒险的方法

一种简单且常用的方法是，对于结构冒险、RAW 冒险和 WAR 冒险，全都在 ID 阶段进行判断，如果不行就在 ID 阶段暂停，等到依赖解除后再进行发射．

MIPS R4000 流水线

• | IF | IS | RF | EX | DF | DS | TC | WB |

miss?

这里讲的冒险问题其实没听懂

2.3. Controls Hazards | 控制冒险

• 最常用的方法就是 stall（延迟分支(delayed branch)）．

2.4. Hazards among FP Instructions

mark

3. Basic Compiler Techniques | 基本编译技术

在本节中，我们考虑以下 C 代码：

for (i = 999; i >= 0; i--)   // typeof i is long long
    x[i] += s;               // typeof x[i] is double

编译到 RISC-V 的结果如下：

Loop:
    fld     f0, 0(x1)
    fadd.d  f4, f0, f2
    fsd     f4, 0(x1)
    addi    x1, x1, -8
    bne     x1, x2, Loop

3.1. Scheduling | 调度

• 使用 调度(scheduling) 优化本节实例代码，可以减少一个时钟周期的停顿．

3.2. Loop Unrolling | 循环展开

• 使用 循环展开(loop unrolling) 并进行调度，可以进一步减少每次迭代的平均周期数．

• 这里假设了迭代次数是 $4$ 的倍数，如果不是的话需要再后面再补上单迭代的循环，以确保总迭代次数不变．

TBD: 具体方法论

4. Dynamic Scheduling | 动态调度

• 回顾（计组知识）：静态调度(static scheduling) 静态调度的流水线处理器在获取指令后会发射该指令，除非发现该指令存在数据依赖且无法通过 前递(forwarding) 来隐藏该指令，此时冒险检测硬件会暂停流水线，直到依赖清除后在获取新的指令．

• 动态调度(dynamic scheduling)：通过硬件重排指令的执行阶段（允许 顺序发射(in-order issue) 但是 乱序执行(out-of-order execution)）以减少停顿，并且不改变 数据流(data flow) 和 异常(exception behavior)．

  • 优点：

    • 可以让在某个流水线上被编译的代码在其他流水线上也能高效运行．

    • 能够处理在编译时无法处理的依赖，比如内存引用或数据依赖分支，或者采用现代的动态链接或分派．

    • 能让处理器容忍无法预测的时延，比如对于高速缓存失效，可通过在等待失效解决时执行其他代码来实现这一点．

4.1. The Scoreboard Algorithm | 记分牌算法

• 带记分牌的流水线阶段：IF - IS - RO - EX - WB．

  • 与 RISC-V 五级流水线的区别：

    • ID 阶段：分成了 发射(issue) 和 取数(read operands) 两个阶段．

    • MEM 阶段：省略，合并到 EX 阶段．

• 记分牌流水线工作流程：

  • IS

    • 当且仅当 (1) 功能单元可用 (2) 没有其他活跃指令占用了相同的目标寄存器 时，发射指令．

    • 可以避免结构冒险与 WAW 冒险．

  • RO

    • 直到两个源操作数都可用时，才进行读取．

    • 可以动态地避免 RAW 冒险．

• 记分牌的数据结构：

  • 指令状态：

  • 功能单元状态(function unit state)：

    • $\mathrm{\text{Busy}}$：表明这个功能单元是否在执行某条指令．

    • $\mathrm{\text{Op}}$：正在这个功能单元执行的指令操作．

    • $F_{i}$：目标寄存器．

    • $F_{j},F_{k}$：源寄存器．

    • $Q_{j},Q_{k}$：源寄存器会由哪个功能单元产生（如有）．

    • $R_{j},R_{k}$：源寄存器是否就绪（都就绪时才读），读完在下一周期要标记为 NO．

  • 计算器结果状态：

4.2. Tomasulo Algorithm | 托马斯路算法

• Tomasulo 算法的优点：

• Tomasulo 算法的缺点：

  • 无法避免内存上的 WAW 与 WAR 冒险，只是通过保留站解决了寄存器上的 WAW 与 WAR 冒险．

  • TBD

• Tomasulo 算法在循环场景中也有助于提升性能（我认为这是因为 Tomasulo 算法的优化不会），但是效果肯定没有直接循环展开的提升来的大．

5. References

• cwz、jxh 等老师的课件．

• lxr 等同学的笔记．

• https://note.noughtq.top/system/ca/3

• https://en.wikipedia.org/wiki/Data_dependency

• https://zhuanlan.zhihu.com/p/496078836

• https://zhuanlan.zhihu.com/p/499978902