6.6 KiB
6.6 KiB
第三章 指令级并行 - 考试考点精细化梳理
考点分级
【必考核心考点】
1. Tomasulo算法（计算题/分析题必考）
核心考法：计算题、分析题、画表题（★★★★★）
核心概念：
- Reservation Station（保留站）：存放指令和操作数
- Register Scoreboard（寄存器记分牌）：跟踪寄存器状态
- Reorder Buffer（ROB）：支持前瞻执行
Tomasulo算法状态表：
| 字段 | 说明 |
|---|---|
| 名称 | 保留站名称 |
| 忙 | 保留站是否占用 |
| Op | 操作类型 |
| Vj, Vk | 源操作数值 |
| Qj, Qk | 产生源操作数的保留站 |
| 状态 | 指令执行状态 |
考题类型：
- 给出指令序列，要求填写Tomasulo算法状态表
- 计算发射周期、执行周期、写回周期
- 理解寄存器重命名消除WAR/RAW冲突
解题步骤：
- 跟踪每条指令：发射 → 执行 → 写回
- 维护保留站状态
- 监视CDB（公共数据总线）上的写回
- 更新寄存器状态
常见陷阱：
- 混淆发射和执行阶段的判定
- 忽略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初始状态，分析预测结果
- 比较不同分支预测策略的准确率
解题思路：
- 初始化BHT状态（如00）
- 对于每个分支：查表得预测，与实际比较，更新状态
- 统计预测正确次数和总次数
常见陷阱：
- 混淆2位饱和计数器的状态转换规则
- 忽略BHT索引方式
3. 前瞻执行（概念题高频）
核心考法：简答题、分析题（★★★★☆）
核心概念：
- 前瞻执行：允许指令乱序执行，但顺序确认
- ROB（Reorder Buffer）：维护指令执行顺序
- 确认阶段：指令结果真正写入寄存器堆
三个阶段：
- 发射：从ISSU队列取出指令，分配ROB
- 执行：等待操作数，就绪后执行
- 确认：按顺序将结果写入寄存器/内存
解决的问题：
- 精确异常处理
- 跨分支前瞻
- 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分布式，是否有寄存器换名