# 第三章 指令级并行 - 考试考点精细化梳理

---

## 考点分级

### 【必考核心考点】

#### 1. Tomasulo算法（计算题/分析题必考）

**核心考法**：计算题、分析题、画表题（★★★★★）

**核心概念**：
- Reservation Station（保留站）：存放指令和操作数
- Register Scoreboard（寄存器记分牌）：跟踪寄存器状态
- Reorder Buffer（ROB）：支持前瞻执行

**Tomasulo算法状态表**：

| 字段 | 说明 |
|------|------|
| 名称 | 保留站名称 |
| 忙 | 保留站是否占用 |
| Op | 操作类型 |
| Vj, Vk | 源操作数值 |
| Qj, Qk | 产生源操作数的保留站 |
| 状态 | 指令执行状态 |

**考题类型**：
- 给出指令序列，要求填写Tomasulo算法状态表
- 计算发射周期、执行周期、写回周期
- 理解寄存器重命名消除WAR/RAW冲突

**解题步骤**：
1. 跟踪每条指令：发射 → 执行 → 写回
2. 维护保留站状态
3. 监视CDB（公共数据总线）上的写回
4. 更新寄存器状态

**常见陷阱**：
- 混淆发射和执行阶段的判定
- 忽略CDB广播对其他指令的影响
- 不理解寄存器换名的作用

**易错易混点**：
- RAW（读后写）：真数据相关，必须等待
- WAR（写后读）：寄存器换名可消除
- WAW（写后写）：寄存器换名可消除

**答题模板**：
```
解：跟踪指令执行过程：

指令i发射时刻：
- 检查对应保留站是否有空
- 若源操作数就绪（Qi=Qj=0），读取Vj, Vk
- 否则记录Qj, Qk等待

指令i执行时刻：
- 等待所有源操作数就绪
- 在执行单元中执行操作

指令i写回时刻：
- 通过CDB广播结果
- 更新所有等待该结果的保留站
- 更新寄存器状态

完成所有指令后，给出最终状态表。
```

**踩分细则**：
- 正确追踪发射阶段：2分
- 正确追踪执行阶段：2分
- 正确追踪写回阶段：2分
- 正确填写状态表：4分

---

#### 2. 动态分支预测（计算题高频）

**核心考法**：计算题、选择题（★★★★☆）

**BHT（分支历史表）**：
```
2位预测器状态转换：
- 11（强分支）：预测分支发生，下同
- 10（弱分支）：预测分支发生
- 01（弱不分支）：预测不分支
- 00（强不分支）：预测不分支

预测错误时状态跳转（错误次数+2，正确次数-1，但不超过0-3范围）
```

**BTB（分支目标缓冲器）**：
- 存储分支指令的地址和目标地址
- 预测分支是否发生以及目标地址

**考题类型**：
- 给定分支序列，计算预测准确率
- 给定BHT初始状态，分析预测结果
- 比较不同分支预测策略的准确率

**解题思路**：
1. 初始化BHT状态（如00）
2. 对于每个分支：查表得预测，与实际比较，更新状态
3. 统计预测正确次数和总次数

**常见陷阱**：
- 混淆2位饱和计数器的状态转换规则
- 忽略BHT索引方式

---

#### 3. 前瞻执行（概念题高频）

**核心考法**：简答题、分析题（★★★★☆）

**核心概念**：
- 前瞻执行：允许指令乱序执行，但顺序确认
- ROB（Reorder Buffer）：维护指令执行顺序
- 确认阶段：指令结果真正写入寄存器堆

**三个阶段**：
1. 发射：从ISSU队列取出指令，分配ROB
2. 执行：等待操作数，就绪后执行
3. 确认：按顺序将结果写入寄存器/内存

**解决的问题**：
- 精确异常处理
- 跨分支前瞻
- WAR/WAW冲突消除

**常见陷阱**：
- 混淆"执行"和"确认"的顺序
- 不理解ROB在其中的作用

**答题话术**：
```
前瞻执行是一种动态调度技术，允许：
1. 指令乱序执行（Out-of-Order Execution）
2. 但必须顺序确认（In-Order Commit）

关键机制是Reorder Buffer（ROB）：
- 发射时分配ROB条目
- 执行后将结果写入ROB
- 按程序顺序确认ROB中的指令
- 确认时才真正更新寄存器堆

这样当分支预测错误时，可以flush ROB中所有后续指令，
实现精确异常和跨分支前瞻。
```

---

### 【高频考点】

#### 4. 循环展开与指令调度（综合分析题）

**核心考法**：分析题、计算题（★★★★☆）

**循环展开的作用**：
- 减少循环开销（分支判断）
- 增加可调度指令数量
- 消除WAR/WAW冲突

**指令调度约束**：
- 不能有WAR/WAW冲突
- 不能改变程序语义
- 受功能单元延迟影响

**常见考题**：
给出循环代码和功能单元延迟表，要求进行循环展开和指令调度。

---

#### 5. 记分牌算法 vs Tomasulo算法

**核心考法**：选择题、简答题（★★★☆☆）

**对比**：
| 特性 | 记分牌 | Tomasulo |
|------|--------|----------|
| 控制方式 | 集中式 | 分布式 |
| 寄存器换名 | 无 | 有（通过保留站） |
| 消除WAR/WAW | 不能 | 能 |
| 结构冲突检测 | 记分牌 | 保留站 |

**考试重点**：
- 理解Tomasulo算法如何消除WAR/WAW
- 理解集中式控制和分布式控制的区别

---

### 【了解考点】

#### 6. 指令级并行的概念

**考法**：选择题、填空题

**概念**：
- ILP（Instruction-Level Parallelism）：指令级并行
- 流水线冲突：结构冲突、数据冲突、控制冲突
- 动态调度 vs 静态调度

---

## 典型计算题解题示范

**例题**（类似记分牌/Tomasulo状态表题目）：
> 假设以下指令序列在 Tomasulo 算法中执行：
> LD F0, 0(R1)
> MULTD F2, F0, F4
> SD 0(R1), F2

**标准解题框架**：
```
解：跟踪每条指令的执行过程：

指令1：LD F0, 0(R1)
- 发射周期：检查保留站 Load1 有空，发布地址计算
- 执行周期：计算地址，访问内存
- 写回周期：将数据通过CDB写入F0和所有等待的保留站

指令2：MULTD F2, F0, F4
- 发射周期：检查乘法保留站有空，源操作数F0等待中（Qj=Load1）
- 执行周期：等待F0就绪后执行乘法
- 写回周期：通过CDB输出结果

指令3：SD 0(R1), F2
- 发射周期：检查存储保留站有空
- 执行周期：等待F2就绪，计算地址
- 写回周期：（存储指令无写回，通过CDB确认）

表（此处应绘制状态表）...
```

---

## 本章核心概念速记

```
1. RAW（真数据相关）：必须等待 ← Tomasulo用RS实现
2. WAR（写后读）：寄存器换名消除
3. WAW（写后写）：寄存器换名消除
4. BHT 2位预测器：00→01→11（不分支→分支），01→10→11，错误时+2，正确时-1
5. 前瞻执行三阶段：发射→执行→确认
6. ROB作用：按序确认，实现精确异常
7. 循环展开：消除循环分支开销，增加ILP
8. 记分牌 vs Tomasulo：集中式vs分布式，是否有寄存器换名
```