299 lines
12 KiB
Markdown
299 lines
12 KiB
Markdown
---
|
||
tags:
|
||
- 计算机系统结构
|
||
- 复习
|
||
- 流水线
|
||
create time: 2026-06-15 10:00
|
||
---
|
||
|
||
# 流水线技术
|
||
|
||
## 概述
|
||
|
||
本文档系统讲解指令流水线的基本原理、冲突类型（结构/数据/控制）、流水线调度策略（预约表与冲突向量）以及时空图分析。流水线是提升处理器吞吐率的核心技术，也是历年考试的高频难点。
|
||
|
||
> [!tip] 考试重点
|
||
> 流水线调度（预约表→禁止表→冲突向量→状态转移图）是分析题的核心考点，需完整掌握从预约表到最优调度策略的全过程。数据相关的三种类型（RAW/WAR/WAW）也常考。
|
||
|
||
## 正文
|
||
|
||
### 一、流水线基本概念
|
||
|
||
**核心思想**：将指令执行过程分成多个阶段（段），不同指令的不同阶段可以**重叠执行**，从而提高吞吐率。
|
||
|
||
```mermaid
|
||
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_0$
|
||
>
|
||
> **Step 4：画状态转移图**
|
||
>
|
||
> ```mermaid
|
||
> graph LR
|
||
> C0["C0 = 1010"] -->|"j = 1"| C1["C1 = 1111"]
|
||
> C0 -->|"j = 3"| C2["C2 = 1011"]
|
||
> C2 -->|"j = 2"| C0
|
||
> ```
|
||
>
|
||
> **Step 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$）
|
||
|
||
**状态转移图示例**（与上面例题对应的图示化表达）：
|
||
|
||
```mermaid
|
||
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。
|
||
|
||
### 四、时空图分析
|
||
|
||
时空图是分析流水线性能的直观工具，横轴为时间（时钟周期），纵轴为流水线段或功能部件。
|
||
|
||
**绘图步骤**：
|
||
|
||
1. 确定每个任务的各段执行时间
|
||
2. 根据调度策略确定任务间的间隔
|
||
3. 注意数据相关的约束（无定向传送时需插入气泡）
|
||
4. 计算总完成时间和吞吐率
|
||
|
||
> [!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 = 23$ ns（但按 4ns 时钟周期计算 = 32ns）
|
||
> - 串行时间 $T_{seq} = 5 \times (2+4+3+2) = 55$ ns
|
||
> - 吞吐率 $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.67$ | $20/8 = 2.5$ |
|
||
> | 效率 | $1.67/5 = 33.3\%$ | $2.5/5 = 50\%$ |
|
||
>
|
||
> Forwarding 将加速比提升了 **50%**（从 1.67 到 2.5），这就是为什么现代处理器都实现了 Forwarding 旁路网络。
|
||
|
||
## 关联笔记
|
||
- [[计算机系统结构/复习文档/计算机系统结构基础与定量原理]]
|
||
- [[计算机系统结构/复习文档/存储系统与Cache]]
|
||
- [[计算机系统结构/index|试题册索引]]
|