💻 CSC3060 Week 8-9 Pipeline and Pipeline Hazards

⚠️ 本篇结尾有 Quiz-2 的 cheating paper。


Week 8 Pipelined Implementation

流水线 (pipelining) 的核心思想即让多条指令的不同阶段“重叠执行”。理想流水线是 “单发射” 的——即每个 short cycle 开始 1 条指令。

基础概念：

  • 吞吐量 (Throughput)：平均多少周期完成一个指令？
  • 指令延迟 (Latency)：单条指令从发射开始需要多少时间完成？
  • 阶段 (Stage)：所有指令可以被分为多个互相硬件独立的阶段。
  • Fill：指令依次被发射；Drain：等待最后一条指令的延迟。

⚠️ RISC-V ISA 天然适合流水线：

  • 指令长度固定 32-bit (除了 “C-Extention”)，更易将指令划分成规律的阶段 (而 x86 可变长 1–17B)。
  • 指令格式少且规则：译码 + 读寄存器能在同一步完成。
  • L/S 架构：只有 load/store 访存；地址计算在 EX，访存在 MEM，分工清晰。

五级流水、吞吐与耗时计算

经典 5 级流水：将指令划为五个阶段，分别占用处理器不同的区块

  1. IF：取指（Instruction Fetch），包括 PC(内含 Clk)、ADD4、IMEM；
  2. ID：译码 + 读寄存器（Instruction Decode & Register Read），包括 Regs、ImmGen(Sign-Extend)；
  3. EX：执行/算地址（Execute / Address Calculate），包括 ALU，及其 Asel、Bsel；
  4. MEM：访问数据存储器（Memory Access），包括 DMEM；
  5. WB：写回寄存器（Write Back），包括四元计算器 WBsel。

单周期机最小周期为最慢指令 lw 的总时长 (“long cycle”)；多周期机和流水线机最小周期为最慢阶段时长 (“short cycle”)，比如 MEM/EX。周期 (ps) 的倒数为频率 (GHz)。

  • 如果 1 long cycle = 5 short cycles，LW 要 5sc (所有阶段都要)、SW/ADD/SUB/JAL 要 4sc (后三者没有 MEM，SW 没有 WB)、BEQ 要 3sc (没有 MEM 和 WB)。那么执行 LW, LW, ADD, SUB, BEQ, SW, SW 需要：

    • 单周期：“延迟向上对齐”——7lc = 35sc，理想吞吐量 (Throughput) 为 1条指令 / 5sc；

    • 多周期：“实际需求”——5sc x 2 + 4sc x 4 + 3sc x 1 = 29sc，理想吞吐量为 1 条指令 / 平均 CPI (sc)；

    • 流水线：“阶段向上对齐” fill + drain (等最后一条指令走完剩下4个阶段)——7sc + 4sc = 11sc，理想吞吐量 (⚠️ 不算 drain) 为 1 条指令 / sc (CPI≈1)。

  • 故而，三者在五级流水下理想吞吐量为：1/5、1/3~1/5、1。

⚠️ 单周期受到最慢指令延迟限制、多周期受到 CPI 限制、流水线受到最慢阶段限制。


通用公式

(short cycle = n；流水线阶段数 = N)

  • 单周期 (用最慢指令定周期)：$T = n \times T_{long}$。

  • 多周期 (指令数为 i)：$T = \sum_i CPI(i)$。

  • 理想 N 级流水：$T = n + (N-1)$，即 drain = latency - 1。

  • 流水的提速 (speedup) 公式：$T_{pipe} = \frac{T_{SingleCycle}}{N}$，即提速 N 倍。(前提是各阶段平衡，如果各阶段耗时差异大，会导致提速下降)

  • ⚠️ 流水相对于多周期非流水的提速：$T_{pipe} = \frac{\sum_i CPI(i)}{i}$，即提速 “平均 CPI” 倍。

⚠️ 流水线加速来自 throughput 增加，而不是 latency 减少，事实上单条指令的 latency 反而可能更大 (若不平衡)。



流水线的代价

流水线要想“每个短周期都推进一条指令”，前提是——

  • 每个阶段需要的硬件资源能同时服务不同指令；
  • 否则就会出现结构冒险 (structural hazard)：资源冲突导致必须停顿（stall），流水线“断流”。

E.g.：如果 IF 和 MEM 共用同一个单端口内存，那么当某条 LW/SW 在 MEM 阶段访问内存时，下一条指令在 IF 阶段就必须等 (插入 bubble/stall)。解决需要把内存资源翻倍 (I-cache + D-cache 分离，或多端口存储器)，增大硬件开销。

流水线的代价是硬件冗余或更复杂的控制，理想的 “CPI=1” 只在 “资源足够且结构冒险都被解决” 时成立。

此问题在下文 (WEEK 9 部分) 展开讨论。



例题

  • 时钟周期为？——1250ps (单周期非流水)，350ps (多周期非流水)，350ps (流水)。

  • lw 命令的延迟为：？——1250ps (非流水)，350ps x 5 = 1750ps (流水)。

  • 如果改成六级流水，应该把哪个阶段拆开，拆开后周期为？——拆 ID，周期为 300ps。

  • 提速？——1250/350 (相对于单周期)，60% x 4 + 20% x 5 + 20% x 3 = 4 (相对于多周期)。



流水线的实际实现

流水线的 “节拍” 由最慢阶段决定，不同于多周期非流水，流水线中所有指令不能跳过阶段，否则会打乱节拍。

  • Sequentially 串行：同个指令的不同阶段，不能乱序；

  • Simultaneously 并行：不同指令的不同阶段可以同时进行。

特殊的，不是所有指令的 EX 都可以在单个短周期内算完，比如 div，对于这种高延迟操作：

1、Stall (停住流水线)：下一个指令停在 EX 前面一个阶段，形成气泡 bubble。操作简单，但会导致吞吐和提速崩溃。

2、Separate long-latency pipeline (另开长延迟功能单元)：把 DIV / FP 这种操作交给专用单元 M-Extentions 和 F/D-Extentions，让主流水线能继续推进其它独立指令，这就是 RISC-V 分离模块的缘由。通常，指令在 WB 阶段按程序顺序退休，原因是 “异常/陷阱 (traps)” 语义：如果后面的指令先退休了，而前面的指令后来触发异常，会导致程序状态不一致。然而 RISC-V 避免了很多算术异常，所以乱序退休也是可行的。


真正实现流水线的关键：插入流水寄存器

在单周期里，一条指令的控制信号“只服务这一条”，没歧义；但在流水线里，同一时刻有多条指令分别处于不同阶段，你就会遇到一些典型的混乱：

  • “现在该用哪条指令的 rs1/rs2/imm？”
  • “现在 WB 应该写哪条指令的 rd？”

解决方法就是：在阶段之间插入 pipeline registers (IF/ID、ID/EX、EX/MEM、MEM/WB)，把“数据 + 控制信号”一起往后带，保证每个阶段用到的都是“属于同一条指令”的那份信息。

Pipeline registers 不是 architectural state。上下文切换需要保存的是架构态（寄存器、PC、内存等），而流水寄存器、分支预测器、cache 等属于微架构态。




Week 9 Pipeline Hazards

除去 Fill & Drain 的开销、阶段划分不平衡的限制，Pipelining 还面临着 data hazards，structural hazards 和 control hazards。三类 hazards 通常会使后续指令被卡在 ID 阶段，形成 stall，从而产生 bubble，效率下降。

Fill & Drain 的开销决定了 ⚠️流水线偏爱长程序——

流水线的 fill/drain 都是额外成本，只有中间的完全并行时才是最优的。 流水线优化的是长程序，而对很短的代码段加速未必明显。


结构风险

结构风险是最朴素的资源冲突：硬件不够，导致两条指令同时争抢同一资源。

例子 A：IMEM 和 DMEM 端口冲突

  • IF 阶段要取指令，要访问 IMEM；
  • MEM 阶段的 load/store 要访问 DMEM。

如果机器采用的是 Von Neumann architecture (冯·诺依曼结构)，即指令和数据共用一套内存端口，那么当一条指令在 MEM 阶段访问数据时，另一条指令在 IF 阶段就没法同时取指了，于是冲突发生。

例子 B：两个相邻的除法指令

除法器往往不是 1 个周期做完，而是要占用功能单元很多周期，例如 32、64 个周期。如果两条除法指令连续出现，第二条除法就会发现：除法器还没腾出来。


规避结构风险

1、Pipeline stalls

最直接的方法就是冲突时让后继指令在 ID 阶段等着，插入 bubble。 简单但性能下降。

2、增加资源

在 标量架构 (scalar architectures) 中，结构冒险相对不常见，因为 —— 寄存器文件通常有足够的端口；有多个乘/除法单元或者这些功能单元本身就可流水化；IMEM 和 DMEM 通常分离；常有两个加法器：一个给 PC+4，一个给算术运算。拿硬件换性能。

3、Instruction Reordering

可以由：编译器静态调度 (static scheduling) 或硬件动态调度 (dynamic scheduling) 来尽量错开那些会争资源的指令。 拿顺序安排换性能。

4、ISA design

某些指令形式会额外要求更多写端口，比如 post-increment。或直接在 ISA 层禁止某些容易引发冲突的设计，例如 ALU 指令禁用 MEM。

  • 比如 R-Type 不存在 MEM 阶段，但不能提早 WB 打乱节拍，导致结构风险。


数据风险

数据冒险是指**后继的指令依赖前序指令产生的数据，但数据还没准备好。**即 RAW 依赖。

比如：

add x9, x0, x1：结果在 EXE 末尾算出来，在 WB 阶段写回 x9

sub x10, x9, x3：它需要在 ID 阶段读 x9

当 sub 到 ID 时，add 可能还没把 x9 正式写回寄存器堆。最糟糕时，就只能让 sub 等到 add 写回完成，形成 2 个周期的 bubble。


数据风险可以大致分为三类：

Register Access Issues

如果写和读同个寄存器恰好发生在同一周期，我们显然只需**同周期先写后读 (write-then-read) **解决。不必 stall。


ALU Result Access Issues

下图中， xor 指令的 Register Access Issue 被 Write-then-read 解决了，但 sub 和 or 因为 add 尚未 WB 得到错误值。

方案 1：Pipeline Stall at ID stage

按照上文中的例子那样，紧接着的下条指令 stall 2 cycles。

这种方法属于 Interlocking …… Which is terrible.

方案 2：Data Forwarding (Bypassing)

不等写回寄存器堆再读，直接把依赖对象流水中已经算出来的结果 “旁路” 送给 ALU。

能成功是因为后续指令进行到 EX 时，前序依赖至少已经结束了 EX 进入 MEM，所以可以直接从那里拿一份值。

这是现代流水线解决 ALU 数据冒险的核心机制之一。


Load Issues

Load 产生的数据在 MEM 阶段缓慢的访存后得到，⚠️ 紧接着的命令若依赖必须 Stall 1 cycle。

现实中，Load DMEM 也有 Latency，需要的时间与数据从哪里来有关：Cache 2 需要 2~3 cycle；Cache 3 需要 20 cycle；DRAM 需要 200 cycle。


数据风险的检测

前面流水级里将要写回的目标寄存器 RegRd，是否正好等于当前指令将要读取的源寄存器 RegRs？

从 EX/MEM 流水寄存器 Bypass：

  • EX/MEM.RegRd = ID/EX.RegRs1
  • EX/MEM.RegRd = ID/EX.RegRs2

从 MEM/WB 流水寄存器 Bypass：

  • MEM/WB.RegRd = ID/EX.RegRs1
  • MEM/WB.RegRd = ID/EX.RegRs2

额外判断：

  • 如果前面的指令根本不写寄存器，就不 forward。所以要检查 RegWr；
  • 如果目标寄存器是 $0，也不 forward，因为零号寄存器恒为 0。所以要检查 RegRd ≠ 0。

MIPS

MIPS = Micro-Processor without Interlocked Pipe Stages——硬件尽量不做复杂的流水线 interlock，数据冒险交给编译器。

这就是 code scheduling：编译器乱序重排指令，避开 WAW、WAR、RAW 依赖，如果找不到合适指令填空，就插入 NOP。非 MIPS 机中亦可用于减少 Interlock，从而减少 Stall。



控制风险

在分支条件尚未判定 T/NT 或者跳跃地址尚未算出前，下次发射 IF 时并不知道真正应该执行谁。

  • 控制风险来自：条件分支指令 (branch) 或 跳转指令 (jal or jalr)。

  • 分支指令比例约占 15% 到 30%。约每 4 到 5 条 指令就有一条分支。意味着控制风险是流水线性能的关键之一。

  • ⚠️ 最难预测的控制风险是 “indirect jump for branch JALR"。

⚠️ 控制风险的原因不是 “跳转” 这个行为本身，而在于直到 EX 这一步计算 (ALU/Comparator) 之后 (MEM) 才知道下个流水级真正的 IF 对象。故 jal 和 jalr 都会产生控制风险。

我们先讨论 Branch 的 T/NT 问题。

  • 如果不做风险防护，在 Branch 的风险发生期间，最多可能紧接着执行 3 个错误命令 (即 branch/jalr 执行 ID、EX、MEM 三个阶段发射的三条指令)。

  • 如果我们直接 flush 所有错误命令：20% 的指令是 branch，其中 50% 执行跳跃，基础 CPI = 1，flush 3 条指令 —— 导致至少 3 × 0.2 × 0.5 = 30% CPI Penalty。(实际在 30~60%)

  • 如果在 EX 阶段就知道分支结果 (比如 bypass 出来)，flush 的代价变为 2 条指令： 2 × 0.2 × 0.5 = 20% CPI Penalty (实际在 20~50%)。所以——

分支结果越早决定越好。


方案一：Predict Not Taken

最简单的预测方法——假设所有分支都不跳转，即默认下一条 PC = PC + 4，再在 MEM 阶段验证。“理论上” 性能损失减少一半。⚠️ 但是通常代码中 Branch 由 Loop (循环) 为主——每个循环 T 或有好多次，但 NT 只有一次，实际上平均准确率约 30~40%，CPI Penalty 约 28%。

方案二：Static Branch Prediction

静态预测：预测结果在编译期就基本决定好，运行时不怎么变。

比如：

  • 回跳 (backward branch) 预测为 T，因为循环 (Loop) 回跳大多在迭代，都会成立，到循环结束时也只会失败一次；

    比如 beq r3, r4, -8 → predict taken。

  • 前跳 (forward branch) 预测为 NT，因为编译器常把 “then” 部分放在顺序路径 (if, then, else…)；

    比如 beq r3, r4, 8 → predict fall-through。

  • 记录预测结果：ISA 可以为 branch 指令预留 prediction bit；或者像 HP 用指令中寄存器顺序表示 (beq r3, r4, 8 表示 NT / beq r4, r3, 8 表示 T，⚠️ 其它不对称 Branch 不能直接交换寄存器顺序)

但无论如何，这种静态预测准确率通常只有 60%~70%。编译器分析产生的静态预测约 80~85%


方案三：Dynamic Branch Prediction

在运行时根据同个指令的历史行为不断学习和更新的预测方法，准确率常能到 90%–99%。

BHT：Branch History Table

用最近 branch 指令的地址 (tag) 来索引，表里存分支过去的结果。⚠️ IF 阶段查表，按记录预测下一次结果，没有记录默认 NT；再根据实际结果更新 BHT。

⚠️ 表项里历史信息可能只要 1~2 bit，但 tag 可能要 30–46 bit。所以实际中往往直接拿 PC 的低若干位 去索引 BHT，而不做完整 tag。这会带来一个现象：aliasing (别名冲突)。不同分支可能映射到同一个 BHT 表项，互相污染历史。虽然 untagged BHT 简单、高性价比，但高性能处理器倾向于用 tagged BHT 来减少 aliasing。

1-bit Predictor

(上次 T，这次就预测 T，vice versa)

⚠️ 它在处理嵌套循环 (Nested Loop) 时发生典型的 “双连错”，准确率约 70~80%：

  1. 内层循环大部分都在迭代，都是 T；
  2. 最后一次退出循环时，真实结果突然变成 NT，于是第一次误判，更新成 NT；
  3. 下次再进入内层循环时，第一轮其实应该 T，但预测器还记着 NT，于是第二次误判。

2-bit Predictor (FSM)

只有连续两次预测错，才改变预测倾向。

这是一个有限状态机 (finite-state machine)。准确率约 85~95%


方案四：Correlated Prediction

也叫 2-level adaptive branch prediction，它不是只看 “这个分支自己上次怎样”，而是看：

最近若干个分支的整体模式，是否能帮助预测当前分支。准确率约 94~96%

1. GHB：Global Branch History Register

GHB 是一个移位寄存器，记录最近几个 branch 的结果。每个 bit 表示一次 branch T/NT。每来一个新分支结果，就 shift 一次，把旧的出队。相当于记录最近控制流的上下文。

2. PHT：Pattern History Table

PHT 里放的是 2-bit saturating counters。GHB 的内容作为其索引，如果当前 branch 实际 T，就把对应计数器 +1，否则 -1。它反映的不是 “某条 branch 永远怎样”，而是在某种全局历史下，这条 branch 倾向于怎样。

比如：

if (a==2) a=0;   // B1
if (b==2) b=0;   // B2
if (a!=b) {...}  // B3

如果 B1 T，B2 也 T，说明 a 和 b 都被置 0，那么 B3 很可能 not taken。B3 的结果和它前面两个分支的结果存在相关性 (correlation)。


准确率从 98% 到 99% 的提升不是 1% 而是 100%，因为性能由预测失败率主导，而非预测成功率主导 (长程序中失败代价高)。


光顾着跳不跳了，你到底要跳哪里去？

即使有各种 Predictor，跳转时仍可能有 1～2-cycle penalty，取决于 target address 是在 ID 还是 EXE 阶段算出来——

分支预测有两个问题：Whether (跳不跳) & Where (跳到哪)。

为了解决“where”的问题，引入 BTB，它本质上是 target address 的 cache。

  • target address 通常不变，因为 branch immediate 不变；

  • 因此可按 PC 建一个小缓存。在 IF 阶段取指时，用 PC 查 BTB；

  • 如果命中，并且预测为 taken，就可以立刻去取 target 指令，而不用等后面阶段再慢慢算地址 。

这就是为何现代处理器常把 BHT 和 BTB 配合使用：BHT 负责 whether，BTB 负责 where。



流水线中控制信号如何流动？

Pipeline Regs, BHT, BTB 都属于 Microarchitecture

EX stage

数据通路要有：rs1 内容、rs2 内容、PC、Imm 值

控制信号有：Asel、Bsel、ALUsel (所以需要两个 Adder)

MEM stage

数据通路里需要：ALUout (作为地址)、rs2 内容 (store 时要写入内存的数据)

控制信号有：MemRW、BrLt、BrEq

WB stage

数据通路里可能写回的来源有：ALUout、PC+4 (给 link register)、MEMout

控制信号有：Wbsel、rd、WRen

延迟使用：

  • EX 用的控制信号，1 个周期后 才真正用；
  • MEM 用的控制信号，是 2 个周期后；
  • WB 用的控制信号，是 3 个周期后；
  • RD (rd) 也要一路传到 WB 阶段。

当一条指令在 ID 阶段被译码出来时，控制单元已经知道将来要做什么，但它此刻还没到 EX/MEM/WB。所以这些控制位不能立刻消失，必须随同该指令一起存进流水寄存器，一级级往后传。




Cheating-paper for CSC3060 Quiz2

comments powered by Disqus