12 KiB
tags, create time
| tags | create time | |||
|---|---|---|---|---|
|
2026-06-15 10:00 |
流水线技术
概述
本文档系统讲解指令流水线的基本原理、冲突类型（结构/数据/控制）、流水线调度策略（预约表与冲突向量）以及时空图分析。流水线是提升处理器吞吐率的核心技术，也是历年考试的高频难点。
[!tip] 考试重点 流水线调度（预约表→禁止表→冲突向量→状态转移图）是分析题的核心考点，需完整掌握从预约表到最优调度策略的全过程。数据相关的三种类型（RAW/WAR/WAW）也常考。
正文
一、流水线基本概念
核心思想：将指令执行过程分成多个阶段（段），不同指令的不同阶段可以重叠执行，从而提高吞吐率。
graph LR
A["IF: Fetch"] --> B["ID: Decode"] --> C["EX: Execute"] --> D["MEM: Memory"] --> E["WB: Write Back"]
性能指标：
| 指标 | 公式 | 说明 |
|---|---|---|
| 吞吐率 | TP = n / T_k |
n 个任务在 T_k 时间内完成 |
| 加速比 | S = T_{seq} / T_k |
串行 vs 流水线 |
| 效率 | E = S / k |
流水线的利用率（k 为段数） |
二、流水线冲突
2.1 结构冲突（Structural Hazard）
多条指令在同一时钟周期争用同一硬件资源。
[!example] 典型场景 指令和数据共用一个存储端口，取指和访存同时发生冲突。解决方案：分离指令 Cache 和数据 Cache。
2.2 数据冲突（Data Hazard）
后续指令需要使用前面指令的运算结果，但结果尚未写回。
| 类型 | 全称 | 含义 | 示例 |
|---|---|---|---|
| RAW | Read After Write | 后读前写（真数据相关） | ADD R1,... ; MOV R2,R1 |
| WAR | Write After Read | 后写前读（反相关） | MOV R2,R1 ; ADD R1,... |
| WAW | Write After Write | 后写前写（输出相关） | ADD R1,... ; SUB R1,... |
解决方案：
- 数据前推/旁路（Forwarding）：将结果直接从 EX/MEM 传递到下一条指令的 EX 输入
- 插入气泡（Stall）：暂停流水线等待数据就绪
- 编译器调度：重排指令顺序避免冲突
[!question] 定向传送（旁路）为什么不能完全消除数据冲突？ Load-use 冲突：从内存 Load 的数据在 EX 段结束时才可用，但下一条指令可能需要在 EX 段开始时就使用它，此时必须插入一个气泡。
Load-use 冲突 vs Forwarding 效果对比：
假设指令序列为 LW R1, 0(R2) → ADD R3, R1, R4，Load 指令的 R1 在 MEM 段末才从存储器读出，而 ADD 指令在 EX 段开头就需要 R1 的值。
| 时钟周期 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 无 Forwarding，无 Stall | ||||||||
LW R1 |
IF | ID | EX | MEM | WB | |||
ADD R3,R1,R4 |
IF | ID | EX | MEM | WB | |||
| 有 Stall，无 Forwarding | ||||||||
LW R1 |
IF | ID | EX | MEM | WB | |||
ADD R3,R1,R4 |
IF | ID | Stall | EX | MEM | WB | ||
| 有 Forwarding（Load-use 需 1 拍 Stall） | ||||||||
LW R1 |
IF | ID | EX | MEM | WB | |||
ADD R3,R1,R4 |
IF | ID | Stall | EX | MEM | WB | ||
| 理想 Forwarding（非 Load 指令） | ||||||||
ADD R1,... |
IF | ID | EX | MEM | WB | |||
ADD R3,R1,R4 |
IF | ID | EX | MEM | WB |
[!important] 关键区别
- EX→EX 前推（非 Load 指令）：结果在 EX 段末产生，下一条指令 EX 段初可用，无需 Stall
- MEM→EX 前推（Load-use）：数据在 MEM 段末才可用，但下一条指令 EX 段初就需要，必须插入 1 拍 Stall
- 这就是为什么 Load-use 冲突无法被完全消除的根本原因——存在一拍的物理时间差
2.3 控制冲突（Control Hazard）
分支指令的执行结果决定后续取指方向，但在分支确定前已经预取了后续指令。
解决方案：
- 暂停：等待分支结果确定后再取指（最简单但性能差）
- 预测：静态预测（总预测不跳转/总预测跳转）或动态预测（分支历史表）
- 延迟分支：在分支指令后填充一条必定执行的指令（延迟槽）
三、流水线调度（非线性流水线）
非线性流水线中，各段的使用存在重叠冲突，不能简单地每拍送入新任务。需要通过预约表分析确定安全的调度间隔。
3.1 预约表
记录一个任务在各时钟周期对各段的占用情况，是调度分析的起点。
3.2 禁止表
从预约表中提取同一段被两次以上占用的时间间隔，构成禁止表 $F$。
3.3 冲突向量
根据禁止表构建初始冲突向量 $C_0$：
- 冲突向量的第
i位为 1 表示间隔i个周期不能进入新任务 - 位数 = 最大禁止间隔
3.4 状态转移图
对每个状态（冲突向量），计算允许的间隔 j 对应的新状态：
C_{new} = SHR^{(j)}(C) \lor C_0
其中 SHR^{(j)} 表示右移 j 位，\lor 表示按位或。
3.5 最优调度策略
在状态转移图中找出所有闭合回路，计算每个回路的平均延迟：
\text{平均延迟} = \frac{\text{回路中各间隔之和}}{\text{回路长度}}
平均延迟最小的回路即为最优调度策略。
[!example] 完整例题：从预约表到最优调度
已知某非线性流水线预约表如下（3 段：S1, S2, S3，7 个时钟周期）：
段 \ 时刻 1 2 3 4 5 6 7 S1 x x S2 x x S3 x x Step 1：提取禁止表 F
- S1 在时刻 1 和 5 被占用，间隔 = 5 - 1 = 4
- S2 在时刻 2 和 4 被占用，间隔 = 4 - 2 = 2
- S3 在时刻 3 和 7 被占用，间隔 = 7 - 3 = 4
因此禁止表 $F = {2, 4}$（去掉重复的 4）
Step 2：构建初始冲突向量 $C_0$
最大禁止间隔为 4，冲突向量共 4 位（第 1~4 位），第
i位为 1 表示间隔i禁止：C_0 = 1010其中第 2 位和第 4 位为 1（对应禁止间隔 2 和 4），第 1 位和第 3 位为 0（对应允许间隔 1 和 3）。
Step 3：计算各状态转移
初始状态 $C_0 = 1010$，允许间隔为 $j \in {1, 3}$：
- $j=1$：
SHR^{(1)}(1010) \lor 1010 = 0101 \lor 1010 = 1111 = C_1- $j=3$：
SHR^{(3)}(1010) \lor 1010 = 0001 \lor 1010 = 1011 = C_2状态 $C_1 = 1111$，所有位为 1，不允许任何间隔，为终态。
状态 $C_2 = 1011$，第 2 位为 0，允许间隔 $j=2$：
- $j=2$：
SHR^{(2)}(1011) \lor 1010 = 0010 \lor 1010 = 1010 = C_0Step 4：画状态转移图
graph LR C0["C0 = 1010"] -->|"j = 1"| C1["C1 = 1111"] C0 -->|"j = 3"| C2["C2 = 1011"] C2 -->|"j = 2"| C0Step 5：找最优调度策略
从
C_0出发，找到所有闭合回路：
回路 间隔序列 平均延迟 C_0 \xrightarrow{j=3} C_2 \xrightarrow{j=2} C_0(3, 2) \frac{3+2}{2} = 2.5拍这是唯一可循环的回路，最优调度策略为 (3, 2)，平均延迟 2.5 拍。
[!tip] 验证 按 (3, 2, 3, 2, ...) 调度，任务进入时刻为 0, 3, 5, 8, 10, 13, ... 每个任务 7 拍完成，5 个任务在时刻 0~17 完成，吞吐率 = $5/18 \approx 0.278$（远优于串行的 $1/7 \approx 0.143$）
状态转移图示例（与上面例题对应的图示化表达）：
graph LR
C0["C0 = 1010"] -->|"j = 1"| C1["C1 = 1111 (终态)"]
C0 -->|"j = 3"| C2["C2 = 1011"]
C2 -->|"j = 2"| C0
[!question] 为什么 C1 = 1111 是"死胡同"？ 当所有位都为 1 时，没有任何间隔是允许的——此时流水线已完全阻塞，新任务无法进入。因此在实际调度中应避免进入此类状态，本题的最优回路 (3,2) 恰好避开了 C1。
四、时空图分析
时空图是分析流水线性能的直观工具，横轴为时间（时钟周期），纵轴为流水线段或功能部件。
绘图步骤：
- 确定每个任务的各段执行时间
- 根据调度策略确定任务间的间隔
- 注意数据相关的约束（无定向传送时需插入气泡）
- 计算总完成时间和吞吐率
[!example] 数值化示例：4 段流水线性能分析
已知：4 段流水线（S1, S2, S3, S4），各段延迟分别为 2ns, 4ns, 3ns, 2ns。时钟周期取最长段延迟 = 4ns。连续执行 5 个任务。
情况 A：线性流水线，无冲突
任务 \ 段 S1(2ns) S2(4ns) S3(3ns) S4(2ns) 完成时刻 T1 0-4 4-8 8-12 12-16 16 T2 4-8 8-12 12-16 16-20 20 T3 8-12 12-16 16-20 20-24 24 T4 12-16 16-20 20-24 24-28 28 T5 16-20 20-24 24-28 28-32 32
- 总时间
T_k = (4-1) \times 4 + (2+4+3+2) = 12 + 11 = 23ns（但按 4ns 时钟周期计算 = 32ns）- 串行时间
T_{seq} = 5 \times (2+4+3+2) = 55ns- 吞吐率
TP = 5/32 = 0.156任务/ns- 加速比
S = 55/32 = 1.72- 效率
E = 1.72/4 = 43\%[!question] 为什么效率只有 43%？ 因为各段延迟不均衡（S2 占 4ns，S1 和 S4 只占 2ns），S1 和 S4 的大部分时间处于空闲状态。这就是段间不均衡带来的效率损失——改善方法是细分较长段或合并较短段。
[!example] 综合计算题：含数据冲突的流水线性能
已知：5 段流水线（IF/ID/EX/MEM/WB），每段 1 时钟周期。执行以下指令序列：
I1: LW R1, 0(R2) ; Load R1 from memory I2: ADD R3, R1, R4 ; R3 = R1 + R4 (RAW on R1, Load-use) I3: SUB R5, R3, R6 ; R5 = R3 - R6 (RAW on R3) I4: SW R5, 0(R7) ; Store R5 to memory (RAW on R5)问题：(a) 无 Forwarding 时需要多少 Stall？(b) 有 Forwarding 时需要多少 Stall？(c) 分别计算加速比和效率。
(a) 无 Forwarding
时钟 1 2 3 4 5 6 7 8 9 10 11 12 I1 LW IF ID EX MEM WB I2 ADD IF ID S S EX MEM WB I3 SUB IF S S ID S S EX MEM WB I4 SW IF S S ID S S EX... 解释：I2 等 I1 在 WB 后才能读 R1（需等 2 拍）；I3 等 I2 在 WB 后才能读 R3；I4 等 I3 在 WB 后才能读 R5。
无 Forwarding 总共需要 8 个 Stall 拍。
(b) 有 Forwarding（Load-use 需 1 拍 Stall）
时钟 1 2 3 4 5 6 7 8 I1 LW IF ID EX MEM WB I2 ADD IF ID S EX MEM WB I3 SUB IF ID EX MEM WB I4 SW IF ID EX MEM WB 解释：
- I2 的 R1 依赖 I1（Load-use）：数据在 MEM 末可用，I2 需在 EX 初使用，插入 1 拍 Stall
- I3 的 R3 依赖 I2（非 Load，EX→EX 前推）：无需 Stall
- I4 的 R5 依赖 I3（非 Load，EX→EX 前推）：无需 Stall
有 Forwarding 仅需 1 个 Stall 拍。
(c) 性能对比
指标 无 Forwarding 有 Forwarding 总拍数 12 拍 8 拍 串行时间 4 \times 5 = 20拍20 拍 加速比 20/12 \approx 1.6720/8 = 2.5效率 1.67/5 = 33.3\%2.5/5 = 50\%Forwarding 将加速比提升了 50%（从 1.67 到 2.5），这就是为什么现代处理器都实现了 Forwarding 旁路网络。