Instruction-Level Parallelism

时间并行：采用流水线技术，使指令重叠并行执行

空间并行：重复设置多个处理部件，让它们同时执行相邻或相近的多条指令

静态调度：编译阶段，减少相关、冲突

动态调度：执行过程中用硬件调度

1. 指令的动态调度

Out-of-order Execution & Out-of-order Completion

• 指令的流出拆分为两步：
  • 检测结构冲突
  • 等待数据冲突消失
• 具体实现上，将 ID 阶段分解为：
  • 流出（issue, in-order）：译码，如果没有「结构冲突」则流出
  • 读操作数：如果没有数据冲突，读操作数

1.1 Scoreboard

4 段执行过程：

• in-order 流出 if
  • 功能部件空闲
  • 正在执行的指令的目的寄存器与该指令不同（解决了 WAW）
• 读操作数 if
  • 源操作数可用：前面已流出且还在执行的指令都不对该寄存器进行写操作（解决 RAW）
• 执行
• 写结果 if
  • 不存在 WAR 冲突：不存在前面的某条指令还没有读本指令的目的寄存器

1.2 Tomasulo

核心思想：

• 操作数一旦就绪就执行，尽可能减少 RAW 。
• 通过 renaming 消除 WAR （反相关）和 WAW （输出相关）。

1.2.1 硬件结构

保留站：记录操作码、操作数，等待功能部件接收并执行。

通过保留站和流出逻辑共同完成 renaming ：

• 指令流出时，如果操作数没有就绪，则将其换为将要产生这个操作数的保留站的标识。
• 因此，指令流出到保留站后，操作数寄存器要么被换为数据（如果数据就绪），要么被换为保留站标识，无论如何与寄存器无关。所以不会产生 WAR 冲突。

1.2.2 执行步骤

• in-order 流出
  • if 指令所需的保留站有空闲
  • 替换源操作数（解决 WAR ）
  • 预约目的寄存器：将目的寄存器设置为接收功能部件的结果。由于 in-order 流出，因此最后一次预约的结果将留下，解决了 WAW 。
• 执行
  • 一旦操作数就绪就执行
  • load/store 计算 effective address 有效地址，放入缓冲器
  • 如果存储器就绪， load 在此存储
• 写结果（out-of-order 完成）
  • 功能部件计算完毕后，将结果放在 CDB 上。
  • store 写入存储器

注意事项：

• 如果流水线中有分支指令没有执行，则当前指令不能进入「执行」阶段。
  • 「流出」阶段后，顺序不保证。
  • 为了保持正确的异常行为，需要增加此限制。

1.3 Speculation and Re-order Buffer

How? 对分支指令的结果进行猜测，并假设这个猜测总是对的

在 Tomasulo 的基础上，拆分「写结果」和「指令完成」：

• 写结果：将前瞻执行的结果写入 ROB ，并通过 CDB 在指令之前传送结果。
• 指令确认 in-order commit ：分支方向确定后，确认前瞻执行的结果。

ROB 每项的组成：

• 指令类型
• 目的地址
• 数据值
• 是否就绪：指令是否完成执行并且数据就绪

ROB 是 FIFO 的队列。

保留站：需要额外记录 dest ，即结果需要写入哪项 ROB 。

执行步骤：

• 流出 in-order issue ：
  • if 保留站和 ROB 都有空项

• 执行

  • load 计算有效地址、读取数据
  • store 计算有效地址

• 写结果

  - 写入 ROB 项

• 确认 in-order commit

硬件支持精确中断的条件： in-order commit

2. Multiple Issue

两种基本风格：

• superscalar
• very long instruction word: 流出指令包，显式并行

超流水线：对流水段做进一步细分，每个时钟周期流出 n 条指令

---

Last update: June 14, 2022

Authors: Co1lin