1 / 4概念
Dynamic Scheduling
指令在程序里的顺序不是它必须执行的顺序。动态调度让硬件在运行时检查操作数就绪状态,并在有限窗口内重排发射与执行,把缓存缺失和长延迟运算藏进其他指令。读完应能区分顺序发射、乱序执行与乱序完成,并判断一次停顿来自依赖、资源还是窗口。
1 概念
1.1 一句话定义
动态调度是处理器在运行时判断操作数是否就绪、并重排指令发射与执行的机制。它保持数据流语义,用硬件窗口替代编译器的静态时间表。
1.2 它解决什么问题
- 长延迟:缓存缺失、除法与浮点运算的延迟随运行时变化,静态调度无法预知。
- 顺序停顿:顺序流水线遇到一条未就绪指令就整条停住,后面的独立指令填不进空拍。
- 有限 ILP:单个基本块内独立指令不足,需要让相邻基本块的指令重叠执行。
- 资源闲置:不同功能单元的空闲周期可以被其他就绪指令利用。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 寄存器重命名与 ROB 提交 | Register Renaming and ROB |
| 分支方向与目标预测 | Branch Prediction |
| 编译器静态调度、VLIW | VLIW and Static ILP |
| 缓存组织与内存层次 | Memory Hierarchy |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| scoreboard | 集中记录功能单元与寄存器就绪状态的控制表 | 不是缓存,也不是 ROB |
| Tomasulo | 用保留站与公共数据总线做分布式记分的算法 | 得名于 IBM 360/91 的实现 |
| 保留站 | 等待操作数与功能单元的就绪指令槽 | 不是架构寄存器 |
| CDB | 公共数据总线,广播结果与生产者标签 | 现代核常用分布式旁路网络 |
| RAW / WAR / WAW | 真依赖、反依赖、输出依赖 | 只有 RAW 是数据流真依赖 |
| 乱序完成 | 指令按操作数就绪顺序写回结果 | 提交仍应保持程序顺序 |
| 窗口 | 可同时跟踪的在飞指令集合 | 不等于 ROB 大小 |
2 机制
2.1 心智模型
把处理器想成一台受窗口限制的数据流机器:指令在窗口内等待,操作数齐了就点火,点火顺序与程序顺序无关。 窗口越大,能覆盖的延迟越长,但唤醒、选择与旁路的成本随窗口增长。硬件只决定“何时执行”,提交顺序仍由程序保证。
2.2 机制拆解
- 顺序前端:取指、译码、重命名按程序顺序进行,保证控制流与异常可追踪。
- 记分板:集中表记录指令状态、功能单元占用和寄存器结果来源;发射顺序,执行乱序,遇 WAW/WAR 停顿。
- Tomasulo:每个功能单元配保留站,操作数未就绪时记录生产者标签;结果经 CDB 广播,等待者按标签唤醒,标签换名隐含消除 WAR/WAW。
- 唤醒与选择:标签匹配唤醒等待者,选择器从就绪集合中挑最老或最关键的指令发射,这是
O(window²)的关键路径。 - 访存与写回:load/store 队列保存地址与数据,load 可越过更老的 store,但需地址消歧;结果经旁路网络送到等待单元,省去寄存器堆往返。
2.3 完整枚举
| 方案 | 发射顺序 | 执行顺序 | 完成顺序 | 依赖处理 | 典型代表 |
|---|---|---|---|---|---|
| 顺序流水线 | 顺序 | 顺序 | 顺序 | 停顿 | 经典五级 |
| Scoreboard | 顺序 | 乱序 | 乱序 | 记分板停顿 | CDC 6600 |
| Tomasulo | 顺序 | 乱序 | 乱序 | 保留站 + CDB | IBM 360/91 |
| Tomasulo + ROB | 顺序 | 乱序 | 乱序 | 保留站 + 重命名 | 现代 x86、ARM64 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| 发射宽度 | 4–8 条/周期 | 受译码、重命名与端口限制 |
| 保留站 | 每单元 4–16 项 | 总量约 50–200 |
| ROB | 200–600 项 | 决定在飞指令上限 |
| L1 命中 | 4–5 周期 | 含地址生成与旁路 |
| DRAM 延迟 | 200–300 周期 | 决定窗口需求 |
| 窗口需求 | IPC × 延迟 | 4 IPC × 200 周期 = 800 项 |
依据 Little 定律,窗口要覆盖“并发度 × 延迟”。4 IPC 配 200 周期内存延迟需要 800 个在飞操作,超过多数 ROB,因此内存级并行与预取比继续加宽更有效。
3 实践
3.1 最小示例
mul x1, x2, x3 # 长延迟,结果写 x1
add x4, x1, x5 # 依赖 mul,必须等
sub x6, x7, x8 # 与上面无关,可以提前
动态调度会把 sub 提到 add 之前:sub 的操作数早已就绪,add 仍在等 mul 写回。若 x1 来自 cache miss,收益会从数个周期变成数百个周期。
3.2 常用操作与参数
| 操作 | 参数 | 说明 |
|---|---|---|
| 设窗口 | ROB 项数、保留站项数 | 覆盖延迟与功耗的折中 |
| 设发射宽度 | 每周期 4–8 条 | 受重命名与寄存器端口约束 |
| 选唤醒策略 | 标签匹配、推测唤醒 | 推测唤醒可早一拍,但可能回滚 |
| 选选择策略 | 最老优先、就绪优先 | 最老优先利于公平与提交 |
| 配访存消歧 | 保守、预测、混合 | 影响 load 能提前多少 |
3.3 标准流程
- 取指并按程序顺序译码、重命名。
- 为指令分配 ROB 项,送入对应功能单元的保留站。
- 操作数就绪的指令进入选择队列,按策略发射到功能单元。
- 执行完成后经 CDB 或旁路网络广播结果与标签。
- 唤醒等待者,并按程序顺序提交到架构状态。
3.4 与相邻技术的组合
重命名与 ROB 提供可回滚的精确状态,分支预测让前端持续供指,缓存与预取缩短平均延迟,SMT 用第二线程填补发射空拍。四者共享同一窗口与端口,任一不足都会把瓶颈转移。
3.5 选型维度
| 场景 | 首选 | 理由 |
|---|---|---|
| 通用服务器 | 宽发射 + 大 ROB + 乱序 | 单线程延迟与吞吐都要 |
| 移动 SoC | 中等窗口 + 低功耗调度 | 能效优先于峰值 IPC |
| 实时控制 | 顺序或受限乱序 | 最坏执行时间可分析 |
| 安全敏感 | 关闭或限制推测 | 降低侧信道暴露面 |
3.6 决策规则
- 先看停顿构成:依赖停顿靠窗口,资源停顿靠加端口,控制停顿靠预测。
- 窗口不是越大越好:唤醒与选择的延迟、功耗和验证成本随窗口超线性增长。
- 内存延迟主导时,宜优先提高内存级并行,而不是继续加宽发射。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 静态调度 | 硬件简单、功耗低 | 依赖编译器与固定延迟 | VLIW、DSP |
| Scoreboard | 结构集中、易理解 | 不消除 WAR/WAW | 早期超算 |
| Tomasulo | 分布式、天然换名 | 无精确异常 | 经典乱序 |
| 乱序 + ROB | 精确异常 + 高 ILP | 面积、功耗、验证 | 通用 CPU |
3.8 何时不该用
- 硬实时路径不应依赖乱序:最坏执行时间难以界定。
- 面积与功耗极紧的 MCU 宜用顺序流水线。
- 程序独立指令极少且分支密集时,扩大窗口收益有限,应先改算法或数据布局。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 结果偶发错误 | WAR/WAW 未正确换名 | 检查保留站标签与释放时机 |
| 流水线死锁 | 唤醒丢失或 CDB 仲裁饥饿 | 加超时检测,检查标签比较 |
| 提交卡住 | ROB 满且最老指令等异常 | 检查异常路径与清空逻辑 |
| 访存顺序错 | load 越过别名 store | 加地址消歧或保守停顿 |
| 性能不及预期 | 窗口不足或选择策略偏 | 看 stall 原因与窗口占用 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 把乱序当免费性能 | 功耗与验证成本被低估 | 按负载选窗口 |
| 只加 ROB 不加访存队列 | 内存停顿仍然卡住 | 同步扩大 LSQ |
| 用 IPC 单独评价调度 | 掩盖公平性与尾延迟 | 结合 MPKI 与尾延迟 |
4.3 可观测信号
perf stat 的 cycles、instructions、stalled-cycles-backend;uops_issued.any 与 uops_executed.any 看在飞与执行;resource_stalls 区分 ROB、RS、LSQ 满;llvm-mca 可估算静态片段的吞吐与瓶颈单元。IPC 低而 backend stall 高,通常是窗口或访存;frontend stall 高则先查取指与预测。
4.4 安全 / 性能 / 一致性边界
- 安全:乱序与推测让未提交的访存留下缓存痕迹,Spectre 类攻击正利用这一点。
- 性能:窗口、端口与旁路共同决定上限;加宽到一定程度后,收益被唤醒延迟与功耗抵消。
- 一致性:乱序执行不改变架构可见的内存序;提交顺序、store buffer 与 fence 才是内存模型的落点。