超标量处理器设计笔记（11）发射内容：分配、仲裁、唤醒

概述

• Allocation
  • 分配已被重命名的的指令
• 发射队列
  • 存储已被重命名，但没有被送入到 FU 的指令
• 选择 arb 电路
  • 多个指令操作数都准备好后，找到最合适的指令，送到 FU
• 唤醒电路
  • 指令经过 FU 后，计算得到结果，通知给等待其结果的指令

集中式和分布式

策略：某几个 FU 共用一个发射队列

数据捕捉和非数据捕捉

数据捕捉

• 重命名后先读取物理寄存器，将值随着指令写入队列中
• 如果没被计算出来，则将寄存器编号写入到发射队列中，等待唤醒

在 payload RAM 存储了指令源操作数的值，指令从发射队列中被选择中时，直接从 RAM 里将数据取出来，并且送入到 FU。
当指令被选中时，目的寄存器的编号值会进行广播，其他指令会将源寄存器编号和广播编号值进行比较
如果相等，则进行标记
计算完毕后，结果会写入到 payload RAM 中（通过旁路网络来实现）

图中的 FU 不是选择器，而是 module

Machine width：每周期实际可以解码和重命名的指令个数
Issue width：每个周期最多在 FU 中并行执行的指令个数

Issue width > machine width

• 由于相关性，不能把重命名的 machine width 条指令都成功送入 FU，一直停留在 issue queueu 中，所以需要 issue width>machine width

由于这种是在发射阶段前读的寄存器堆，所以物理寄存器的读端口是 machine width X 2 ，两个源寄存器

非数据捕捉

被重命名后的指令不会读取物理寄存器堆，而是将编号放到发射队列中，被选中后，才使用源寄存器编号读取物理寄存器堆，送入到 FU 中执行，也就不需要 payload sram 了

此时寄存器堆的所需要的读端口个数是 issue width x 2

总结对比

数据捕捉：两读一写，从寄存器读出，写入发射队列，再继续读出，功耗大
在 ROB 进行寄存器重命名时，会使用数据捕捉
#问题 不用关心指令结果的变化是什么意思？

压缩式和非压缩式

压缩式发射队列

当发射队列中的指令出去之后，则立马顺着下移

实现方式多路选择器，可以选择自身、上面的表项、上上面的表项 (假如一次发射两条指令，则需要移动两格)

当两条指令不是背靠背时，则部分指令移动两格，部分指令一格，则需要产生不同的控制逻辑

优点：

• 选择电路比较简单，可以根据优先编码器选择出最老就绪的指令
• 分配电路简单，只需要使用写指针指向第一个空闲的空间

缺点：

• 延迟和发射队列的容量是正比的，指令个数越多，延迟越大
• 浪费面积，如果单个发射队列连接 2 个 FU 时，每个周期从两条指令送到 FU 执行，中间的压缩需要大量连线
• 功耗大，移动的数量多

非压缩式发射队列

新指令会找到一个空的位置，填写进去

总结

发射过程的流水线

非数据捕捉结构的流水线

发射的条件（步骤）

• 指令所有的源操作数准备就绪
• 被发射队列旋转，并且通过仲裁模块允许才能发射
• 根据寄存器编号从寄存器、旁路中获取原操作数

唤醒的方式有两种（主要用在 RAW 相关上）

• 当上条指令执行完，获得结果后便唤醒相关指令
• 当上条指令被仲裁后，就唤醒其相关指令，直接进行仲裁排队，节约两拍

仲裁和唤醒这两个步骤两种安置形式

• 放在一个周期内
  • 可以实现背靠背
  • 单个周期时间长，降低时钟频率
  • 某些 FU 模块执行周期长，需要两个周期才能执行完，那么旁路获取结果值会晚一拍
• 放在两个周期内
  • 流水线深度加长，分支预测惩罚会增大
  • 时钟频率会增加，效率说会增大
    • 案例
      • 如果原来是 1GHz，IPC 为 2，那么 1s 会执行 2 * 10^9 条指令
      • 拆开后，时间频率理想化为 2GHz，IPC 预计下降 10%-15%（文献数据），那么 1s 会执行 2 * 2 * 0.85=3.4 * 10^9 条指令
      • 实际上不能完美拆成两个五五开的周期，还有建立时间和保持时间的约束，可能是 73 开，那么要以 1/0.7 * 2 * 0.85 = 2.8 * 0.85 = 2.38 也就只提升 19 %
  • 增加流水线，门数也增加，电容 C 也增加，频率也变快，所以 W 也不断增大的
    • W = (1/2) CV^2F
  • Cache 访问周期也会增加，访问总时间不变，频率增加，周期会增加

数据捕捉结构的流水线

数据捕捉结构多了一项 payload 存储数据，所以直接从 payload 取出来就好

源操作数可以从几个地方取出来：payload 、旁路

Payload 同时发射有读取 n* 2 个端口 + 1 个写入端口，n 表示一个周期并行执行的指令数
那么其面积和延迟都会很大，导致周期时间长

由此将 payload 单独出来当作一站，选择和唤醒放在一站

分配

分配是将完成重命名的指令放入到发射队列中

放入的方式有几种

• Freelist 管理，当需要 allocated n 条指令时，freelist 送出 n 个空的队列标号，满足分配要求
• 假设每次有 n 条指令过来，将 issue queue 分为 n 组，每条指令在其对应的组内寻找，这种方式查找快，但如果有一组内容满了后，由于顺序写入的关系，其后面也写入不了。
  • 可以设计缓存去存储需要载入满足的指令，但由于相关性，其设计会复杂很多。

仲裁

1-of-M 的仲裁电路

在非压缩方式的队列中，采用优先编码选择，则是随机选择。

为什么要实现 oldest-fisrt 电路？

• 越旧的指令，其后面指令的相关性越强，越早算出结果，同时唤醒更多指令
• 指令不仅占用 issue queue，还会占用 ROB、store buffer 资源，释放这些硬件资源

需要从 ROB 拿到年龄的信息，怎么根据年龄信息判断先后，新增一位 flag 位来指示先后关系

• 当 Flag 相同时，数值越大，越 old
• 当 Flag 不同时，数值越小，越 old

再根据 rdy 位，结合年龄来判断最老项

首先利用二叉树结构两两比较

• 当 rdy 都为 1，比较年龄选择最 old 的
• 当 rdy 只有一个 1 时，选择 rdy 项

在比较时，同时附着指令队列编号，就不需要 CAM 比较电路了

N of M 的仲裁电路

适用于集中式设计的发射队列之中，一个队列连接多个 FU

可以根据指令类型再做选择电路，将同一类型的指令输出到同一个 FU 之中

但如果指令分布不均匀，比如说 ALU 指令数量多，则会导致该类指令会一直卡在队列中，而其他类的指令无法进入队列，等待唤醒/执行

由此新增 ALU 单元，比如说 ALU 0/1
但又带来新的问题：选择指令进入哪个 ALU0 还是 ALU1 呢？

方案：
在重命名阶段设置标志位，实现 ALU0/1 分配，但也没有实现严格意义上的 oldest-first 电路
为了避免情况发生，需要更复杂的分配算法，则会增加面积和时序

唤醒

#问题 是否存在跨队列唤醒？

单周期指令的唤醒

仲裁逻辑单元数目 = issue width

发射队列信息

• Src：表示源寄存器编号
• Valid：表示该指令是否存在该源寄存器
• Rdy：表示源操作数就绪
• Issued：表示该指令已经被仲裁选择

唤醒流程

• 指令操作数准备就绪，并且还没发射过，向裁决电路发出请求
• 裁决电路接受后，再反馈信号
• 发射队列接受到反馈信号后，广播目的寄存器编号到总线上
• 与其他源寄存器编号对比，如果编号一致则唤醒

多周期指令的唤醒

多周期指令无法在执行的第一个周期给到值，所以需要延迟一段时间

延迟广播

延迟几拍再广播出去，但存在新的问题，可能会出现广播冲突的情况

两种方式解决

• 增加广播总线，但因为这种情况存在很多，所以会占用大量总线
• 使用表格记录当前 FU 中指令执行所需周期数，判断是否有冲突
  • 裁决表格并行查找
  • 先表格后裁决串行查找
    • 需要先将旧指令查完，再查新指令，串行查找导致延迟可能会很大

并行查找

• 执行 A 指令后，广播 A 指令的目的寄存器后，表中就有记录
• 执行 B 指令时，先查表，发现存在冲突情况，等待下周期再发送裁决请求

但是如果发生冲突，则会浪费该周期，比如说 C 指令已经就绪，而且不会发生广播冲突（没有目的寄存器，执行周期数可以和 A 错开），导致性能下降

延迟唤醒

广播出去，发现命中，但不立即唤醒，等待 n-1 个周期（n 为上条指令在 FU 中所需周期数）

• Freed：该项为 free，提交退休后再标记
• Issued：已选中，并且将目的寄存器广播
• Src：源寄存器标号
• SrcL_M：表示源寄存器命中
• SrcL_SHIFT：需要当前需等待的周期数（不断右移，直到 LSB =1 时，赋值 rdy）
• Rdy：表示就绪
• Src_imm_valid：表示该源操作数是立即数
• Pdst_valid：表示存在目的寄存器
• Delay：表示该指令在 FU 单元执行周期数编码（如果执行 3 个周期，则为 100）
• ROB ID：ROB 的序号 ID 年龄信息

延迟方式

• 当选中后将 DELAY 和 Pdest 同时广播出去
• 如果有一路 tag 命中，则 SrcL_M 表示命中，并且将 DELAY 值送入到 SrcL_SHIFT 中
• 每过一个周期，只要 SrcL_M 为 1，SrcL_SHIFT 则算数右移一位，直到 LSB 为 1，同时 Rdy 设置为 1
• 选中发射出去，得到 grant 后将 Src_M、SrcL_SHIFT 置 0

推测唤醒

两种情况执行周期不确定

• Load 指令有可能发生 cache/tlb miss 情况，L1 L2 L3 cache 取周期数不同，Dram 访问周期不定
• 部分乘法指令执行简单

Cache miss 情况

最简单的方式，执行完再进行唤醒，Load 取到数值之后再唤醒，不过需要空闲等待很久，

提前到 TLB/Tag 阶段唤醒也一样

于是假设所有都会 L1 cache 命中，如果不命中，则把指令打回到 issue queue 中（取消该指令，并且把 issue queue 的 isssued 位给置为 0），延迟周期按照 L2 cache 去填写。同时将该 load 唤醒的指令也恢复在 load queue 中

再假设 L2 Cache 命中，唤醒与其目的寄存器相关的指令

TLB miss 情况

TLB miss 的情况

• 不触发 page fault
  • 将该 load 指令和其相关指令打回到 issue queue 中
  • 按照 mmu 访问执行周期数来延迟唤醒
• 触发 page fault
  • 硬件处理异常
    • 和不触发一致
  • 软件处理异常
    • 将流水线中的指令执行到该异常指令时，清空所有流水线，从 icache 里重新取指令

Independent 和 Speculative Window

当一条 load 指令推测执行时，其相关指令会延迟两拍进行（称为 SW），中间这两拍会由与其不相关的已 ready 指令填充（IW）

一旦发生 cache miss，抹掉处于 SW 区域的 wake-up 和 selcet 指令即可

• IW 并非一定不相关
  • 与其他 load 指令的 SW 区域重合
• SW 并非一定相关
  • 可能就绪，但是 age 比其他指令年轻

Issue Queue Based Replay

给发射队列设置一个标志位：issued
发射出去之后，如果发生 cache miss、load-load、store-load 违例时，则重新标记 issued 为 0，表示可以再次经过裁决

直到指令提交退休之后，才退出 issue queue

这样导致大量不会发生违例的指令占用 issue queue 很久

• 只针对 load 进行 queue 中 replay，一旦 load 指令 cache hit 后，便可以直接释放
  • 如果其他指令由于 load-load / load-store 违例需要 replay ，此时 queue 可能已满，所以无法恢复到 queue 中，同时 queue 中的项可能也等待被唤醒，造成死锁
    • 需要将这些 replay 指令从流水线抹掉，从 i-cache 中重新取出来放到流水线中
• Load 指令在发生 D-cache miss 后
  • Non-selective Replay
    • 将所有在 load 之后选中的指令重新放回到队列中（issued = 0），重新等待唤醒和选取
      • 但是处于 IW 中的无关指令也被 replay
    • 下图中，IW 区域 cal addr 和 TLB/tag 不需要被 replay，只需要将 SW 区域 Select 和 RF 区域的指令 replay 即可
    • 打回到 queue 中，非相关的可以直接就绪，与 load 相关的需要等待唤醒
    • 要求在队列中将相关性得到识别
      • 直接相关（图中 OR 指令）
      • 间接相关（图中 SUB 指令）
  • Selective Replay
    • 识别出相关性，选择具有相关性的指令 replay
    • Load-vector 来识别相关性
      • 识别方式
        • 对于非 Load 指令，两个源寄存器的 vector 值相或
        • 对于 load 指令，除了源寄存器，还会占用新的位
      • 随后行为
        • 重命名后开始读这个表，当 D-cache 发生缺失时，则找到相关的指令，置于 not ready 的状态，等待重新唤醒
      • 缺点
        • 如果深度过深，而且并行度高时，向量值的宽度会加大，否则会因为向量值宽度不够导致流水线暂停。宽度过高，则会消耗大量资源，增加延迟
    • Load Position Vector
      • 定义
        • 每条 load 指令使用 Vector 来指示处于流水线的哪个位置（Select、RF、Cal Addr、TLB/Tag 和 Data）
      • 流程
        • 在该 load 处于 Select 时，所有与其目的寄存器相同的源寄存器都会获得 Load 指令的 LPV 值
        • 由该源寄存器引发的相关也会继承 LPV 值，之后每个周期 LPV 都会右移一位
        • 多个 Load 相关
        • 当该 load 指令执行到 Data 时，发现 D-cache 缺失，则所有最低位为 1 的源寄存器表示相关和间接相关，置为 not ready
        • 而 LPV =0 时，则该指令可以直接从队列中释放
      • 优点
        • 占用资源少，速度快一些
      • 缺点
        • 如果一个周期有两条 load 同时执行，则需要两个 LPV 值

Replay Queue Based Replay

新增 replay queue 来 Replay

当指令从 issue queue 发射出来后释放，如果出现 D-cache miss，则清除当前流水线，
并且将该 Load 指令和相关指令都存入到 replay Queue 中，等待执行，
replay queue 发射的优先级会比 issue queue 的优先级更高一些

对于捕获数据结构的流水线，从 wake 到 executed 的执行流程少一些，所需要的 replay queue 的 size 会更小一些

对于非捕获数据结构的流水线，由于需要读取寄存器堆，从 wake 到 executed 的执行流程多一些，所需要的 replay queue 的 size 更大一些