动态调度与指令级并行

一、核心概念

1. 指令级并行（ILP）

   • 通过硬件技术同时执行多条指令，降低CPI（每条指令时钟周期数）。
   • 目标：挖掘指令间并行性，减少流水线停顿。

2. 相关性与冲突

   • 数据相关（真相关，RAW）：指令B需指令A的结果。
   • 名相关
     • 反相关（WAR）：指令B写指令A读的寄存器。
     • 输出相关（WAW）：两条指令写同一寄存器。
   • 控制相关：分支指令导致的指令执行顺序依赖。
   • 流水线冲突：相关导致的硬件资源竞争，分结构冲突、数据冲突、控制冲突。

3. 动态调度核心思想

   • 乱序执行：指令执行/完成顺序与程序顺序不同。
   • 将译码（ID）阶段拆分为：
     • 发射（IS）：检查结构冲突（按序）。
     • 读操作数（RO）：等待数据冲突消失（乱序）。

二、关键算法与技术

1. 记分牌算法（Scoreboard）

• 目标：无结构冲突时尽早执行无数据冲突的指令。
• 硬件结构：
  • 执行状态表：跟踪指令状态（发射、执行、写回）。
  • 功能部件状态表：记录部件忙闲、操作类型、操作数来源。
  • 寄存器状态表：标记寄存器被哪个功能部件占用。
• 流程：

  发射 → 等待操作数就绪 → 执行 → 写回

• 缺点：
  • WAR/WAW冲突导致阻塞（后续同类型指令无法发射）。
  • 乱序完成导致调试困难，不支持精确中断。
• 示例：

  DIV.D F0, F2, F4  ; 长延迟指令
  ADD.D F6, F0, F8  ; 等待F0
  SUB.D F8, F10, F14

  SUB.D因WAR冲突（F8）被阻塞，即使无真数据相关。

2. 显式寄存器重命名

• 解决名相关（WAR/WAW）：
  • 结构寄存器（AR）：软件可见（如F0-F31）。
  • 物理寄存器（PR）：硬件实际使用（如T0-T127），数量多于AR。
  • 映射表（Rename Table）：维护AR→PR的映射。
• 操作流程：
  1. 发射指令时为目标AR分配新PR。
  2. 读操作数时查找映射表获取最新PR。
  3. 释放旧PR（当无指令引用时）。
• 示例：循环展开中的重命名
  原始循环：

  A1: LD F0, 0(R0)   ; 多次迭代使用F0导致WAW
  B1: MUL F4, F0, F2

  重命名后：

  A1: LD F0→T9, 0(R0)
  A2: LD F0→T10, 0(R0)  ; 消除名相关

3. Tomasulo算法

• 核心改进：
  • 隐式寄存器重命名：通过保留站消除WAR/WAW冲突。
  • 公共数据总线（CDB）：广播结果至所有等待部件。
  • 分布式冲突检测：保留站自主判断操作数就绪。
• 硬件结构：
  • 保留站（RS）：缓存已发射指令（含操作数/源标签）。
  • Load/Store缓冲器：管理内存访问地址与数据。
  • 寄存器状态表（Qi）：记录寄存器结果来源的保留站。
• 执行阶段：
  1. 发射（Issue）：
     • 分配空闲保留站。
     • 若操作数就绪则读取，否则记录来源标签（如"Multi1"）。
  2. 执行（Execute）：操作数就绪后启动计算。
  3. 写回（Writeback）：结果广播至CDB，更新等待部件。
• 优势：
  • 支持循环间并行（动态重命名）。
  • 无集中控制瓶颈。
• 示例时序（关键指令）：

  L.D F6, 34(R2)  ; Cycle1发射，Cycle3完成
  L.D F2, 45(R3)  ; Cycle2发射，Cycle4完成
  MUL.D F0, F2, F4 ; Cycle3发射，Cycle15完成（10周期乘法）
  SUB.D F8, F6, F2 ; Cycle4发射，Cycle7完成

  SUB.D乱序执行，无需等待MUL.D。

4. 重排序缓存（ROB）

• 目标：实现乱序执行 + 顺序提交，支持精确中断。
• 核心机制：
  • ROB结构：环形队列，每条指令占一项，含字段：
    • Busy、Instruction、State（Issue/Exec/Write/Commit）、Destination、Value。
  • 提交（Commit）：仅队头指令可提交（写回寄存器/内存）。
• 工作流程：
  1. 发射：指令加入ROB队尾。
  2. 执行：乱序执行，结果写入ROB的Value字段。
  3. 提交：按序提交队头指令，释放ROB项。
• 优势：
  • 中断时：提交之前指令，丢弃之后指令。
  • 内存写入延迟提交，保证原子性。
• 示例：

  LD F6,34(R2)   ; Cycle1发射，Cycle4提交
  MUL.D F0,F2,F4 ; Cycle3发射，Cycle16提交（需顺序提交）

三、关键技术对比

特性	记分牌	Tomasulo	Tomasulo+ROB
窗口大小	$\leq$ 5指令	$\leq$ 14指令	由ROB大小决定
WAR/WAW处理	停顿	隐式重命名消除	隐式重命名消除
结果传递	经寄存器	CDB广播	CDB广播至ROB
精确中断	不支持	不支持	支持
控制结构	集中式记分牌	分布式保留站	分布式+ROB

四、难点与关键设计

1. CDB竞争问题

   • 多结果同时写回时需仲裁（如多CDB设计）。
   • 示例：浮点加（2周期）与乘（10周期）同时完成时，CDB需分时传输。

2. 物理寄存器管理

   • 释放时机：当无指令引用旧值（通过空闲列表管理）。
   • 示例（显式重命名）：
     • 初始：F0→T0
     • DIV.D F0, F2, F4 → 分配T9，更新映射为F0→T9。
     • 当后续指令不再使用T0时释放。

3. 保留站与ROB协同

   • Tomasulo+ROB：结果先写ROB，提交时写寄存器。
   • 数据路径：RF → 保留站 → 执行单元 → ROB → RF，可能成为时序瓶颈。

4. 循环并行示例

   Loop:
     LD F0, 0(R1)       ; 迭代1发射Cycle1
     MUL.D F4, F0, F2   ; 迭代1发射Cycle2
     SD F4, 0(R1)       ; 迭代1发射Cycle3
     SUBI R1, R1, 8     ; 更新指针
     BNEZ R1, Loop      ; 分支

   • 动态展开：第二迭代的LD在Cycle6发射，与第一迭代MUL.D并行。