Skip to content

Ch3-1 ILP & Scoreboard

:material-circle-edit-outline: 约 1826 个字 :fontawesome-solid-code: 12 行代码 :material-clock-time-two-outline: 预计阅读时间 6 分钟

计算机体系结构 2024-10-21 第 3-5 节

PPT

[!ABSTRACT]

我们之前学过的所有解决 hazard 的办法都属于静态调度，通过引入 stall 来调度指令，很死板

接下来我们学动态调度的算法，不同情况分别处理，尽可能减少 stall

Instruction-Level Parallelism

ILP 有两种实现途径，基于硬件的动态办法和基于编译器的静态办法

先看看并行乱序执行需要怎么避免各类 hazard

ILP & Hazard

data hazard

在编译器中，hazard 有新的名称

  • RAW - True dependence
  • name dependence，相邻指令使用了同一个 reg，但并没有数据传递
    • WAW - output dependence
      • 执行顺序必须保持
    • WAR - anti-dependence
      • ID 乱序就会出问题，initial 顺序必须保持

所以无论是硬件还是软件 HW/SW，我们要做的一个事情是，在会出问题的地方要阻止并行执行，保证顺序执行

以及检查相同寄存器的使用是否是真实依赖关系，不是的话可以改名

优化后的编译器会生成一张数据流图，用于识别数据依赖，进而判断 RAW 和 renaming 执行

control hazard

主要是跳转指令，分为 branch 和 jump 两类，我们先关注 branch

branch 指令是判断指令，逻辑为 if p1: S1 else: S2

乱序对 branch 的影响可以消除，例如可以先把 S1 和 S2 算完，然后再根据 p1 的结果选择保留和消除

[!EXAMPLE]

当然有特殊情况，例如

  add x1,x2,x3
  beq x4,x0,L
  sub x1,x1,x6
L:    …
  or x7,x1,x8

如果跳转不成功，那么 or 与 sub 是真依赖

所以这里的 branch 也不能允许乱序并行执行

[!EXAMPLE]

还有一种情况如下，sub 就算移到了 beq 之前也不会对程序造成错误，那我们乱序调度的时候是可以先执行这一条的，这样调度就比较细致

  add x1,x2,x3
  beq x12,x0,skip
  sub x4,x5,x6
  add x5,x4,x9
skip:
  or x7,x8,x9

根据上面的分析，只有 RAW 的时候需要阻止并行并保持顺序执行

此外，还有 exception 处理顺序也要与顺序执行的顺序一致

ILP Software approaches

首席我们将指令集分为一个个 Basic Block，就是一串无 branch 的指令序列，将其作为并行指令的基本单位，基于此我们有以下办法

  1. Basic Compiler Technique for Exposing ILP
    • Loop unrolling
  2. Static Branch Prediction
  3. Static multiple Issue: VLIW
  4. Advanced Compilor Support
    • Software pipelining
    • Global Code scheduling
  5. Hardware Support
    • Conditional or Predicated instructions
    • Compiler speculation with hardware support

基本块内部调度优化

先看看正常的浮点数运算，下面是个例子，左边是没优化的，右边是优化的

image-20241030180404284

稍微调整了顺序就优化了很多

Loop unrolling

对于一块需要循环迭代的代码，如果还是按 basic block 分的话可能会分为很多快分别迭代，而且上面的基本块内部调度优化会受到限制

我们就把这几个基本块合并为一个大基本块，这样基本块内部调度优化效果会更好，然后又拆分为基本块并行迭代

下面是一个 Unroll Loop Four Times (straightforward way) 例子

image-20241030181311930

image-20241030181335965

HW Schemes: Dynamic scheduling

当流水线出现 stall 时，如果后面的指令与 stall 无关，那就可以让后面无关的指令继续执行

即按序发射，乱序执行，当然能不能绕过前面的指令由硬件执行

Dynamic Scheduling Step 1

简单流水线将结构 hazard 和数据 hazard 都放在 ID 执行，ID 实际上有两个功能

我们希望将 ID 两个功能拆分为两个阶段:

  • Issue 即 decode 指令，检查 hazard
  • read operand 即等没有 hazard

Dynamic Scheduling with a Scoreboard

允许指令在有资源且无数据以来的情况下乱序执行

  • 顺序 issue
  • 乱序完成

Basic structure of a pipelined processor with a scoreboard

image-20241030190958386

scoreboard 是一个集中控制硬件，调度组件什么时候可以访问 reg

引入 scoreboard 后的流水线阶段变成了 IF, IS, RO, EX, WB 五个阶段，ID 裂开成 IS 和 RO，MEM 被忽略，不是把 MEM 删了，而是我们现在是主要关注浮点数运算，对 MEM 访问较少，先不管

确切地说，MEM 合并到了 EX 的 ALU 组件，可以回去看看有不同组件的那张图

Scoreboard Pipeline stage

  • Issue 发射
    • an instruction is issued when（两点要同时满足）
      • The functional unit is available（FU 有空闲）
      • No other active instruction has the same destination registe（不能有 WAW）
    • Avoid strutural hazard and WAW hazard
    • 确认无 hazard 可以发射就会在周期结束时将指令相关信息写入 scoreboard，三个数据结构都会更新
  • Read Operands (RO)
    • The read operation is delayed until both the operands are available.
      • 多目指令只要有一个数据读不了，就都不读
    • This resolves RAW hazards
    • 此阶段会将 Rj, Rk 置 No
    • ？？？？？？？？？？？？？？？？？
  • Execution (EX)
    • Notify the scoreboard when completed so the functional unit can be reused.
    • 同时 Fj, Fk 也被修改，表明不再需要对应的寄存器
  • Write result (WB)
    • The scoreboard checks for WAR hazards
    • 如果其它 FU 的 Fj, Fk 是当前要写入的，那就会发生 WAR
      • 如此一来就要先 stall，等前序指令读完寄存器再写
    • 此外，会通过 forwarding 传递数据，所以有依赖关系的指令 Rj, Rk 会更新为 Yes，相应的 Qj 和 Qk 也会清除，使其能在下一周期离开 IS 进入 RO 执行
    • 结果写回到寄存器堆，同时会清空记分牌中 FU status 和 reg res status 的相关信息

The scoreboard

scoreboard 的核心是三个数据结构，所有调度都是据此展开

  • Instruction status
    • which of the four steps the instruction is in（除了 IF）
    • 某指令目前在哪个阶段
    • 在 IS 阶段被更新
  • Functional unit status
    • 标记各组件状态 buzy, op, Fi, Fj, Fk, Qj, Qk , Rj, Rk
    • busy - 当前组件是否 busy (Yes/No)
    • op - 组件当前执行的指令类型 (Load/sub/...)
    • Fi - destination reg(F2,...)
    • Fj, Fk - source reg(F1,...)
    • Qj, Qk - 会产生 Fj, Fk 的组件(Integer/mult1/...)
      • 如果源 reg 没准备好该向哪要数据
    • Rj, Rk - 标识 Fj, Fk 对应的数据已 ready 但还没 read，RO 阶段 read 后置 No(Yes/No)
      • 因为是在 IS 阶段标记，RO 阶段才读取，如果数据都已在 reg file 里，也会先在 IS 阶段置 yes，在 RO 阶段才置 no
    • 在 IS 阶段被更新
  • Register result status
    • which functional unit will write that register
    • 哪个寄存器正准备被哪个 FU 写
    • 在 IS 阶段被更新
    • 完成操作后不会被清空

image-20241030194357353

这段指令的运行过程中三个数据结构的变化有问题可以看 PPT 39 页

ILP 局限

如果找不到符合条件（无依赖）的指令进行调度，scoreboard 就爱莫能助了

以及，scoreboard 调度寻找指令不是无限范围寻找的，这个窗口就叫 Issue 队列

在 scoreboard 流水线里，我们可以想象指令是从 issue 这个检查站发射出去的

我们目前假设窗口大小为一个基本块大小

WAW 和 WAR 在 scoreboard 流水线里也会造成 stall，甚至比 RAW 还严重，不过我们可以通过其它办法解决，就是 renaming，确切说是寄存器编译重命名技术

我真的服了，同一个问题同一个办法反复出现在一堂课前后多个地方

拓展阅读

计算机体系结构-记分牌 ScoreBoard - 知乎