指令级并行及其利用

指令级并行: 概念与挑战

• 指令级并行 Instruction-Level Parallelism ILP
• ILP 的两种实现方式:
  • 依靠硬件技术在运行时动态发现并实现并行
  • 依靠软件技术在编译时静态发现并行
• 流水线的 CPI (cycles per instruction) 计算: $$ 流水线CPI=理想流水线CPI+结构化停顿+数据冒险停顿+控制停顿 $$
  • 为了提高流水线的 CPI, 则需要减少等式右边的元素产生的影响, 即减少各种的停顿

什么是指令级并行

• 基本块: 顺序代码序列, 转入/转出分支仅有入口/出口
• 最常见的并行: 循环级并行
  • 目标: 循环级并行转换为指令级并行
  • 相关技术的基本工作方式:
    • 编译器静态展开循环
    • 硬件动态展开循环

数据依赖与冒险

• 关键在于: 判断一条指令是否依赖于另一条指令

数据依赖

• 数据依赖:
  • 指令 i 生成的结果可能会被指令 j 使用
  • 指令 j 数据依赖于指令 k, 而指令 k 的数据依赖于指令 i
• 数据依赖所传递的信息:
  • 可能存在冒险
  • 计算结果时必须遵循顺序
  • 可利用并行度的上限
• 克服依赖的方法
  • 保持依赖但是避免冒险
  • 通过转换代码来消除依赖

名称依赖

• 名称依赖: 当两条指令使用相同的寄存器或存储地址, 但与该名称相关的指令之间并没有数据流动
• 两类名称依赖:
  • 指令 j 对指令 i 读取的寄存器或存储地址执行写操作时, 会发生反依赖 (WAR)
  • 当指令 i 和指令 j 对同一个寄存器或存储地址执行写操作时候, 发生输出依赖 (WAW)
• 对于名称依赖, 由于没有在指令之间传递值, 所以名称依赖不是真正的依赖
  • 解决方法: 寄存器重命名, 改变这些指令中使用的名称 (寄存器号或存储地址), 使得这些指令不再冲突, 则可以使名称依赖中设计的指令可以重新排序或同时执行

控制冒险

• 除了第一基本块外, 其余所有指令都与某组分支存在控制依赖

  [!example] 控制依赖 在上图中, S1 控制依赖于 p1, S2 控制依赖于 p2, 而不依赖于 p1

• 为了保持控制流的正确性, 控制依赖会施加以下两条约束:
  • 若一条指令控制依赖于一个分支, 则不能将这个指令移动到这个分支之前, 而使其不再受控于该分支
    • 不能将 if 语句 then 部分中的一条指令抽出, 移动到这个 if 语句之前
  • 若一条指令并不控制依赖于一个分支, 则不能将其移动到这个分支之后, 而使其受控于这个分支
    • 不能将 if 语句前的一个语句移动到其 then 部分

      [!important] 程序正确性的两个特性 异常行为与数据流 在不影响程序正确性的情况下, 我们可能希望执行一些还不应当被执行的指令, 从而破坏控制依赖, 因此, 控制依赖并不是一个必须保持的关键特性. 对异常行为的保护意味着指令执行顺序的改变不得改变程序抛出异常的方式

• 必须保持数据流的情况
  • 在本例中, or 指令所使用的 x1 值取决于是否进行了分支转移.
  • 单靠数据依赖不足以保证正确性, 还必须保持数据流
• 可破坏的控制依赖
  • 若在 skip 标号后, sub 指令的目标寄存器 x4 并未被使用, 即其不具备活性, 且若现有的 sub 指令不会发生异常, 则可以将 sub 指令移动到该分支之前

    [!note] 活性 一个值是否会被后续的指令使用, 这一特性被称为活性 若一个值不再被使用, 则称其不再具备活性

利用 ILP 的基本编译器技术

• 目的: 为了使处理器能够利用更多的指令级并行

基本流水线调度和循环展开

• 为了使流水线保持满载: 找出可以在流水线中重叠的不相关指令序列, 以充分利用指令并行
• 为了避免流水线停顿: 将依赖指令与源指令的执行隔开一定的时间周期
  • 这一间隔应等于源指令的流水线延迟
  • 编译器执行调度的能力依赖于
    • 程序中可用的 ILP
    • 流水线中功能单元的延迟

      [!tip] 本章节中所使用的一些假设 1. 浮点单元的延迟: 2. 采用一个标准的五级整数流水线, 分支的延迟为一个时钟周期 1. 为什么分支判断错误引起的停顿为 1 个时钟周期? - 分支判断在 ID 阶段进行, 此时分支的下一条指令已经进入流水线, 若判断为跳转, 则需要对流水线进行冲刷, 下一条指令无效, 并对跳转目标的指令重新进行取指, 相当于流水线停顿 1 个时钟周期 3. 这些功能单元被完全流水化, 每个时钟周期可以发射任意类型的运算指令, 而不存在结构冒险

• 循环体:

  for (i = 999;i >= 0;i = i - 1)
      x[i] = x[i] + s;
  

  • 汇编代码:
• 该循环体在简单流水线上执行的情况:
  • fld 与 fadd.d 存在依赖, 停顿一个周期
  • fadd.d 与 fsd 存在依赖, 停顿两个周期
  • addi 与 bne 存在依赖, 停顿一个周期
  • 由于分支错误, 再停顿一个周期
• 对循环进行调度后:
  • 进行调度后, fsd 仍与 fadd.d 存在数据依赖, 停顿两个周期
  • 在本例中, 每 7 个时钟周期完成一次循环迭代, 但是对数据元素进行实际运算仅占用这 7 个时钟周期中的 3 个, 而其余的 4 个使用周期包括循环的开销和两次停顿
• 循环展开
  • 简而言之, 将循环体复制多次, 并调整循环的终止代码
  • 提高效率但使用了更多的寄存器
    • 提高效率: 使用了更多独立的指令来消除数据使用停顿
    • 更多的寄存器: 对于每一次迭代, 都需要使用不同的寄存器 (若使用同一组寄存器, 则可能妨碍对循环的有效调度)
  • 对上面的循环进行循环展开:
    • 节省了三次分支转移和对 x1 的三次递减, 并对于载入和存储指令的地址进行修正
    • 优化的结果: 只需要 12(因依赖而产生的停顿) +14(指令发射)=26 个时钟周期就能完成 4 个元素的计算
  • 对展开的循环再次进行调度:
    • 消除了所有的数据依赖, 将执行周期缩减到了 14 个时钟周期, 每个元素 3.5 个时钟周期
  • 循环展开的代价: 更加庞大的代码规模
    • 但是换来了更高的执行效率

小结

• 循环展开的策略与变换:
  • 找出除维护循环的代码外互不相关的循环迭代, 判定循环展开是有用的
  • 使用不同的寄存器, 以避免由于不同运算使用相同寄存器而造成的非必要约束
  • 取出多余的测试和分支指令, 并调制循环终止与迭代代码
  • 通过观察不同迭代中的载入指令与存储指令互不相关, 判定展开后的循环中的载入指令换存储指令可以交换位置
    • 这一变换需要分析存储器地址, 确认他们没有引用同一个地址
  • 在保留必要的依赖, 以得到与源代码相同的结果的前提下, 对代码进行调度
• 3 种限制:
  • 每次展开操作分摊的开销降低
    • 循环展开的次数越多, 循环所带来的开销就会越低
  • 代码规模限制
    • 代码规模的增长会导致指令缓存缺失率上升
  • 编译器限制
• 循环展开的问题:
  • 由于大量进行展开和调度而造成寄存器紧缺
• 注意:
  • 保证正确性: 循环控制和操作数偏移量的修改
  • 注意有效性: 只有能够找到不同循环体之间的无关性, 才能有效地使用循环展开
  • 需要使用不同的寄存器, 否则可能导致新的冲突
  • 注意对存储器数据的相关性分析
  • 注意新的相关性: 循环展开后可能带来新的相关性

#TODO 用高级分支预测降低成本

- 附录 C 中所述的基础分支预测![[流水线#通过预测降低分支成本]]

用动态调度克服数据冒险

[!note] 静态调度 依靠编译器对代码进行调度, 以减少相关和冲突; 在编译期间对代码进行调度和优化; 通过把相关的指令拉开距离来减少可能的停顿; 指令调度与循环展开. - 动态调度: 硬件重新安排指令的执行顺序以减少停顿, 同时保持数据流和异常行为 - 优点: - 无须为不同的微体系结构重新编译 - 可以应对编译时依赖关系未知的情况 - 允许处理器容忍一些预料之外的延迟 - 缺点: - 更大的硬件开销 - 更复杂的通路

动态调度: 思想

• 简单流水线的限制: 顺序发射与执行
  • 若一条指令停顿在流水线中, 后续的指令都不能执行, 即使不存在依赖
    • sub 指令与上面的两条指令不存在依赖关系, 却因为 add 与 div 的依赖关系而无法执行
  • 解决方法: 将译码阶段分割为两个阶段, 依然是顺序发射, 但是乱序执行
    • 发射 (issue): 指令译码, 检查结构冒险
    • 读取操作数: 在没有数据冒险后, 读取操作数

      [!note] 乱序执行 在动态调度流水线中, 所有的指令都顺序地经历发射阶段, 但是, 它们可能在第二阶段 (读取操作数阶段)停顿或相互旁路, 从而进入乱序执行阶段

• 乱序执行带来的冒险: WAR 与 WAW
  • 这样的依赖关系被称为反依赖, 可以利用寄存器重命名解决

    [!hint] 反依赖 也称为假数据冒险, 并不包含实际的数据流动. 对于 WAW 型数据冒险 在这个例子中, 我们只需要将 and 指令的目标 r3 重命名为其他的寄存器, 既可以消除这个数据冒险 对于 WAR 型数据冒险 同样, 只需要将 add 指令的目标 r3 重命名为其他的寄存器即可消除数据冒险 只要后续的指令能够获得这个最新的寄存器数据, 即可以实现正确的数据流

• 乱序完成带来的问题: 使异常变得复杂
  • 乱序完成的动态调度必须保留异常行为, 使哪些严格按照程序顺序执行成会发生的异常仍然会实际发生, 并且不会发生其他异常
  • 尽管保留了异常, 但仍可能造成非精确异常: 在发生异常时候, 处理器的状态与严格按照程序顺序执行指令时的状态不完全一致, 则为非精确异常
• 主要技术:
  • 记分牌算法 (scoreboard): 允许在有足够资源且不存在数据依赖时乱序执行指令
  • Tomasulo 算法: 通过对寄存器进行动态重命名来处理反依赖和输出依赖
    • 可扩展以处理推测, 降低控制依赖的影响

Scoreboard 记分牌算法

• 结构:
• 四个阶段:
  • 发射: 译码并检查结构冒险
    • 顺序发射
    • 不发射的情况
      • 存在结构冒险则不发射
      • 存在输出依赖 (写同一个寄存器), 则不发射 (解决了 WAW 冒险)
  • 读操作数: 在没有数据冒险时候读取操作数
    • 等待操作数均为最新 (解决 RAW 冒险)
    • 不存在数据前推
  • 执行
    • 完成执行后通知 scoreboard
  • 写结果
    • 若其他指令不需要读当前计算结果即将写入的寄存器, 则写回 (解决 WAR 冒险, 避免指令读取了它不该读取的来自"未来"的数据)
• 3 个组成部分
  • 指令状态: 指示当前指令所处的状态
  • 功能单元状态: 指示功能单元的状态
    • 字段:
      • Busy: 忙碌
      • Op: 正在进行的操作
      • Fi: 目标寄存器
      • Fj, Fk: 源寄存器
      • Qj, Qk: 产生源寄存器数据的功能单元
      • Rj, Rk: 指示源寄存器的数据是否可读
  • 寄存器结果状态: 指示哪一个功能单元将会写这个寄存器

举例

- cycle 1: - 指令状态: 第一条指令发射 - 功能单元状态: 第一条指令使用 Integer 单元, 操作为 Load, 目标寄存器为 F6, 并且源寄存器可读 - 寄存器结果状态: F6 的结果来自于 Integer 单元 - cycle 2 - 指令状态: - 第一条指令进入读操作数阶段 - 第二条指令还无法发射, 因为存在结构冒险 (需要使用 Integer 单元, 而该单元被第一条指令占用) - 功能单元状态与寄存器结果状态不变 - cycle 3 - 指令状态: - 第一条指令进入执行阶段 - 第二条指令与第三条指令无法发射 (结构冒险与顺序发射) - 功能单元状态: - Rk 为 No, 表示不再读取 Rk 的值 - cycle 4 - 指令状态: - 第一条指令完成写回 - 清空功能单元和寄存器结果状态 - cycle 5 - 指令状态: - 第二条指令可发射 - cycle 6 - 指令状态: - 第三条指令发射 (不存在结构冒险) - cycle 7 - 指令状态: - 第三条指令由于操作数 Rj未准备好, 无法读取操作数 - 第四条指令可发射 (不存在冒险) - cycle 8a - 指令状态: - 第五条指令可发射 (不存在结构冒险) - cycle 8b - 指令状态: - 第二条指令写结果 - cycle 9 - 指令状态: - 第三条指令与第四条指令读取操作数 (第二条指令执行完毕, 可读取数据) - 功能单元状态: 乘法单元与加单元开始工作 - cycle 10 - 功能单元状态: 乘法单元与加法单元继续工作 - cycle 11 - 指令状态: sub 指令完成执行 - cycle 12 - 指令状态: - sub 指令写回结果 - div 指令还无法读取结果, 因为乘法单元还在工作, 其中一个操作数不可读取 - cycle 13 - 指令状态: - add 指令发射 (add 单元空闲, 不存在结构冒险) - cycle 14 - 指令状态: - add 指令读取操作数 (两个操作数均准备好, 可读取) - cycle 16 - 指令状态: - add 指令完成执行, - cycle 17 - 指令状态: - add 指令无法写回, 因为 div 指令未读取操作数, 而 add 与 div 存在 WAR 冒险, 不可写回 (不能读取来自未来的数据) - cycle 19 - 指令状态: - mul 指令执行完成 - cycle 20 - 指令状态: - mul 指令写回 - cycle 21 - 指令状态: - div 可读取操作数 - cycle 22 - 指令状态: - add 指令可写回结果 (WAR 冒险已消除) - cycle 61 - 指令状态: div 完成执行 - cycle 62 - 指令状态: div 执行完成, 可写回 - 结果: - 顺序发射, 乱序执行, 乱序完成 - 问题: 为了消除假数据冒险, 对流水线进行停顿

Tomasulo 算法

• 通过寄存器重命名的方式消除 WAR 和 WAW 冒险

[!note] 公共结果总线 Common Data Bus, CDB 允许同时载入所有等待一个操作数的单元. data+source: 使用广播方式传送数据, 如果与期望的功能部件匹配, 就读取总线上的数据 采用公共结果总线, 再由保留站从总线中提取结果, 就实现了静态调度流水线中的前递和旁路机制. 但是在动态调度方案中, 会在源于结果之间引入一个时钟周期的延迟, 因为相对于一个较简单的流水线"执行"阶段的末尾, 要等到"写结果"阶段的末尾, 才能让结果与其应用匹配起来. 因此, 在动态调度流水线中, 生成结果的指令与使用结果的指令之间的有效延迟, 要比生成该结果的功能单元的延迟至少长一个时钟周期(在写结果时候, 才将结果写入到 CDB 中, 进行广播). - 基于 Tomasulo 算法的处理器的基本结构: - 保留站 (reservation station): 在 Tomasulo 中提供寄存器重命名功能, 为等待发射的指令缓冲操作数, 并且与功能单元相关 - 基本思想: - 保留站在一个操作数可用时立即提取并缓冲它, 这样就不再需要从寄存器中获取该操作数, 之后与寄存器无关, 无须关心后续写入寄存器的数据 - 等待执行的指令会指定保留站为自己提供输入, 在发射指令时候, 会重命名待用操作数的寄存器说明符, 改为提供寄存器重命名功能的保留站名字 - 在对寄存器连续进行写操作并且重叠执行时, 实际只会使用最后一个操作来更新原寄存器 - 相当于为每一条通路配置了一组缓冲 - 每个保留站保存一条已经被发射, 正在功能单元等待执行的指令 - 若已经计算出这一指令的操作数值, 则保存这些操作数值, 否则记录这些操作数值的保留站 - 所有保留站都有标记字段, 供流水线控制使用 - 使用保留站而不是集中式寄存器堆的重要特性: - 冒险检测和执行控制为分布式的: 每个功能单元保留站中保存的信息, 决定了一条指令什么时候可以开始在该单元中执行 - 结果将直接从缓冲他们的保留站中传递给功能单元, 而无须经过寄存器 - 这一旁路是通过公共结果总线 (common data bus, CDB)完成的 - 载入缓冲区与存储缓冲区: 记录与存储器交互的数据或地址, 其行为方式基本与保留站相同 - 浮点寄存器通过一对总线连接到功能单元, 由一根总线连接到存储缓冲区 - 来自功能单元和来自存储器的所有结果都通过公共数据总线发送, 会通向除输入缓冲区之外的其他地方 - Tomasulo 算法的三个步骤 - 发射: 从指令队列的头部获取下一条指令(这一步骤消除了假冒险) - 指令队列按 FIFO 维护, 确保数据流的正确性 - 若有一个匹配的保留站为空, 则将该指令发送到这个站中 - 若操作数已位于寄存器中, 则一并发送到站中 - 若操作数不在寄存器中, 则一直跟踪将生成这些操作数的功能单元 - 若无空闲的保留站, 则存在结构冒险, 使其停顿, 直到有空闲的保留站或寄存器 - 执行: 当所有操作数都可用时, 则可以在相应功能单元中执行运算 - 如果还有一个或多个操作数不可用, 则在等待计算的同时监视公共数据总线 - 当其中一个操作数变得可用时候, 则将其放置到所有正在等待它的保留站中 - 写结果: 在计算出结果后, 将其写到 CDB 上 - 从 CDB 传送给寄存器和所有等待这一结果的保留站和存储缓冲区 - 存储指令一直缓存在存储缓冲区中, 直到待存储值和存储地址可用为止, 然后在有空闲存储器单元时, 立即写入结果 [!attention] 在同一时钟周期, 同一功能单元可能会有几条指令同时变为就绪状态. 尽管独立功能单元可以在同一时钟周期执行不同指令, 但如果单个功能单元有多条指令准备就绪, 那它就必须从这些指令中进行选择. 对于浮点保留站, 可以任意做出这一选择, 但是载入和存储指令要稍复杂一些. 载入指令和存储指令的执行过程分为两步: 1. 在基址寄存器可用时计算有效地址, 将有效地址放在载入缓冲区或存储缓冲区中 2. 载入指令可以立即执行; 而存储指令需要等待要存储的值, 然后将其发送给存储器单元

[!attention] 异常行为的保护 为了保护异常行为, 任何一条指令必须等到根据程序顺序排在它之前的所有分支全部完成之后, 才能执行. 这一限制保证了在执行期间导致异常的指令确实会被执行. 在使用分支预测的处理器中, 这意味着处理器在允许分支之后的指令开始执行之前, 必须知道分支预测是正确的. 若处理器记录了异常的发生, 但没有实际触发异常, 则可以开始执行一条指令, 并且在进入写回阶段之前不会停顿. - 寄存器重命名: - 保留站, 寄存器堆和载入/存储缓冲区中的字段: 标记 - 指出哪个保留站中包含的指令将会生成作为源操作数的结果 - 标记引用的是将会生成结果的缓冲区或单元; 当指令发射到保留站后, 寄存器名称将会被丢弃 - 记分牌中, 只有生成结果的指令已完成, 才会读取操作数 - 在指令被发射出去并开始等待源操作数之后, 将使用一个保留站编号来引用该操作数, 该保留站中保存着将对寄存器进行写操作的指令 - 若使用一个未用作保留站编号的值来引用该操作数(如 0), 则表明该操作数已经在寄存器中准备就绪, 可以直接从寄存器中读取 - 保留站的 7 个字段: - Op: 对源操作数进行的运算 - Qj, Qk: 将生成相应源操作数的保留站 - 当取值为 0 时, 表明已经可以在 Vj 或 Vk 中获得源操作数, 或者这个指令根本就不需要操作数 - Vj, Vk: 源操作数的值 - 注意: 对于每个操作数 V 字段和 Q 字段仅有一个有效 - A: 用于保存载入指令或存储器指令而寄存存储器地址所需要的信息 - 在开始时, 存储指令的立即数字段 - 在计算地址后, 存储有效地址 - Busy: 指明这个保留站及相关功能单元已被占用 - 寄存器堆的字段 Qi: 若一个运算的结果应当存储在这个寄存器中, 则 Qi 是包含此运算的保留站的编号 - 若 Qi 的值为空, 则当前没有活动指令正在计算应当存储在这个寄存器中的结果, 则可以直接通过读取寄存器获得目标值 - 载入/存储缓冲区的字段 A: 与保留站中的 A 字段一致 [!note] 载入与存储指令之间的冒险 只要载入指令和存储指令访问的是不同的地址, 就可以放心的乱序执行. 若载入指令与存储指令访问相同的地址, 则可能出现 WAR, RAW 和 WAW 冒险 (这里的读写针对的是数据存储器) 为了判断在给定时刻是否可以执行一条载入指令, 处理器需要检查: 根据程序顺序排在该载入指令之前的任何未完成的存储指令, 是否与该载入指令共享相同的数据存储器地址; 对于存储指令也进行一样的检查. 为了达到上述的目的, 处理器必须计算出任何先前存储器运算有关的数据存储器地址, 因此必须保持存储指令及其他存储器访问之间的相对顺序, 也就是说, 可以随意调整载入指令之间的顺序. 如果按程序顺序执行有效地址计算: 当一条载入/存储指令完成有效地址计算时, 就可以通过查看所有活动存储缓冲区的 A 字段来确定是否存在地址冒险, 如果发现匹配, 则在发生冒险的存储指令完成之前, 不要将载入指令发送到载入缓冲区.

示例

- cycle 1 - ld 可发射, 加载单元的 A 字段为 34+R2 - cycle 2 - ld 可发射, 加载单元的 A 字段为 45+R3 - cycle 3 - mul 功能单元的保留站为空, mul 指令可发射, 并将寄存器 F2 重命名为了 Load2 - Load1 加载单元执行完成, 但暂无指令需要 Load1 的结果 - cycle 4 - 将第一条 ld 指令的执行结果写回到了寄存器 (通过 CDB 获取数据) - 第二条指令执行完成, 此时有两条指令正在等待 Load2 的结果 - cycle 5 - Add1, Mult1 和寄存器 F2 同时通过 CDB 的广播获得 Load2 的结果 - cycle 6 - Add1 与 Mult1 单元开始执行, Mult2 由于需要 Mult1 , 还无法开始 - cycle 7 - Add1 完成, Add2 可以在下一个周期开始执行 - cycle 8 - Add2 开始执行 - cycle 9 - cycle 10 - Add2 单元执行完成 - cycle 11 - add 指令写结果 - cycle 15 - Mult1 完成 - cycle 16 - Mult1 完成, 通过 CDB 广播结果, Mult2 获得数据后, 可以开始执行 - cycle 56 - Mult2 执行完成 - cycle 57 - 所有指令完成 - 总结: - 顺序发射, 乱序执行, 乱序完成 - 缺点: - 需要大量高速的相联存储, 存储开销大 - 非精确异常 - 性能受限于 CDB: CDB 必须广播到多个功能部件单元, 容量大, 操作密集 - 两大优势 - 分布式冒险检测逻辑: - 若多条指令正在等待同一个结果, 而每条指令的其他操作数均已准备就绪, 那么在 CDB 上广播这一结果就可以同时释放这些指令. - 如果使用集中式的寄存器堆, 这些单元必须在寄存器总线可用时候, 自行从寄存器中读取自己的结果 - 消除了可能产生 WAW 冒险和 WAR 冒险的停顿 - 利用保留站来重命名寄存器, 并且在操作数可用时立即将其存储在保留站中

基于硬件的推测-前瞻执行

[!note] 当我们尝试利用更多指令级并行时, 维护控制依赖就会成为一项不断加重的负担. 分支预测减少了分支导致的直接停顿, 但对于每个时钟周期要执行多条指令的处理器来说, 仅靠正确的预测分支可能不足以生成期望数量的指令级并行. 宽发射处理器可能需要每个时钟周期执行一个分支才能维持最高性能. 因此, 要利用更多的并行, 需要克服控制依赖的局限性. - 基于硬件的推测结合了 3 种关键思想: - 用动态分支预测选择要执行哪些指令 - 利用推测, 可以在解决控制依赖问题之前执行指令 - 进行动态调度, 对基本块的各种组合进行跨块调度 - 扩展 Tomasulo 以支持推测: - 将指令结果的旁路从一条指令的实际完成操作中分离出来. 进行这种分离过后, 就可以允许执行一条指令, 并将其结果旁路给其他指令, 但不允许这条指令执行任何不能撤销的更新操作, 直到确认这条指令不再具有不确定性为止. - 使用旁路可以理解为执行了一次推测寄存器的读操作, 因为在提供源寄存器值的指令不再具有不确定性之前, 我们无法准确知道它是否提供了正确的值. 当一条指令不再具有不确定性时, 我们才允许这条指令更新寄存器堆或存储器->称为指令提交 (commit) - 实现推测的关键思想: 允许指令乱序执行, 但强制顺序提交, 并防止在指令提交之前采取任何不可撤销的动作 (如更新状态或引发异常) - 因此, 需要将执行完成的过程与指令提交分隔 - 添加硬件缓冲区-重排序缓冲区 (Re-Order Buffer, ROB) - 用于保存已经完成执行但还没有提交的指令结果 - 也可用于在可被推测的指令之间传送结果 [!note] ROB 与保留站 ROB 与保留站一样都提供了附加的寄存器. 但两者之间的关键区别在于: 在 Tomasulo 算法中, 一旦一条指令写出其结果, 任何后续发射的指令都会在寄存器堆中找到该结果. 而在采用推测时, 寄存器堆要等到指令提交过后才会更新, 因此, ROB 是在指令执行完毕到指令提交这段时间内提供操作数, 提供前推的功能. 对于重命名功能, 由于每条指令在提交之前都在 ROB 中拥有一个位置, 所以我们使用 ROB 条目编号而不是保留站编号来标记结果. 尽管保留站的重命名功能被 ROB 代替了, 但在发射运算之后仍然需要一个空间来缓冲它们, 直到它们开始执行为止. - ROB 的四个字段: - 指令类型: 指定这个指令为分支, 存储指令或寄存器操作 - 目的地字段: 目标寄存器编号 - 值字段: 保存指令结果 - 就绪字段: 指令执行是否完成? 结果是否准备就绪? [!note] ROB 与存储缓冲区 因为 ROB 类似于 Tomasulo 中的存储缓冲区, 因此, 可以将存储缓冲区的功能集成到 ROB 中. 存储指令依旧分为两步执行, 但第二步是由指令提交来执行的. - 前瞻执行的四个步骤: - 发射: - 若存在空闲保留站且 ROB 中有空插槽, 则发射该指令 - 若寄存器或 ROB 中已有这些操作数, 则将其发送到保留站 - 更新控制箱, 指明这些缓冲区正在被使用 - 若暂无这些操作数, 则将为指令结果分配的 ROB 条目编号也一并发送到保留站, 以便通过 CDB 获得结果 - 否则, 等待 - 执行: - 一旦数据准备好, 则立即开始执行 - 若还有操作数未就绪, 则持续检测 CDB - 写结果: - 当结果可用时, 将其写到 CDB 上, 保留站和 ROB 可以接收到这个结果, 并将保留站标记为可用. - 提交: - 顺序提交带来的是精确的异常 - 3 种操作序列: - 当一个指令到达 ROB 的头部而且其结果出现在缓冲区中时, 进行正常提交, 并且清除这个指令 - 当预测错误的分支指令到达 ROB 的头部时, 它指出推测时错误的, 直接清空 ROB, 执行过程从分支正确的地方重新开始 - 若分支预测正确, 则该分支完成提交 [!note] 对于执行阶段的载入和存储指令 对于载入指令, 需要有两个步骤. 对于存储指令, 这一阶段只是为了计算有效地址, 数据的写入在后续阶段进行, 因此, 在这一阶段只需要有基址寄存器可用即可.

[!note] 对于写结果阶段的存储指令 如果要存储的值已经就绪, 则需要将其写到 ROB 条目的目的值字段, 以备存储. 如果要存储的值还不可用, 则需要继续监听 CDB, 知道该数据被广播, 并写入到目的值字段. - 总结: 精确异常! [!note] 前瞻执行与精确异常 在处理异常时, 要等到做好提交准备才会识别异常. 如果推测的指令发生异常, 则将异常记录在 ROB 中. 若分支预测错误, 而且指令不应该被执行, 则在清楚 ROB 时候, 将异常一并清楚了. 若指令到达 ROB 的头部, 我们就知道它不再具有不确定性, 应当引发该异常. 我们还可以在异常出现后, 所有先前分支都已处理完毕的情况下, 立即处理异常.

举例

参考文献

• 计算机体系结构, 第三章, 指令集并行及其利用
• 计算机体系结构, 附录 C, 流水线: 基础与中级概念