250 lines
6.6 KiB
Markdown
250 lines
6.6 KiB
Markdown
# 第三章 指令级并行 - 考试考点精细化梳理
|
||
|
||
---
|
||
|
||
## 考点分级
|
||
|
||
### 【必考核心考点】
|
||
|
||
#### 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分布式，是否有寄存器换名
|
||
``` |