CPU-寄存器重命名的算法设计与实现

工程
Created At :
  1. 指令的相关性
    1. 为什么会出现WAW, WAR
  2. 寄存器重命名的实现
    1. 使用ROB+ARF重命名
    2. 使用ROB+ARF+PRF进行重命名
    3. 使用统一的PRF重命名
  3. 超标量CPU的寄存器重命名
    1. 读写口数量的分析
    2. 指令数据相关性的分析
      1. RAW相关性的处理
      2. WAW相关性的处理
  4. Renaming Table的设计
    1. 读优先/写优先问题
  5. 寄存器重命名的恢复
    1. Architecture State
    2. WALK

指令的相关性

如果一条指令的执行会依赖其他指令的执行情况, 那么这两条指令就具有相关性.

相关性可以大致分为如下几类:

  • 数据相关性(Data Dependency): RAW, WAW, WAR.
  • 内存指令的相关性(Memory Dependency): 也就是load/store指令之间的相关性, 也可以分为RAW, WAW和WAR.
  • 控制相关性: 后面指令的执行依赖分支指令的结果.
  • 结构相关性: 指令的执行需要等CPU中的资源空闲后才可以进行.

为什么会出现WAW, WAR

  • 在ISA中, 架构寄存器的个数有限, 导致在某些地方必须复用寄存器.
  • 循环结构:
    • 如果在一个循环体中写入某个寄存器, 那么WAW就会出现多次.
  • 函数调用:
    • 如果在一个函数中写入某个寄存器, 并且这个函数被调用多次, 那么WAW也会出现多次.

在数据相关性中, 只有RAW是真正的依赖, 而WAW和WAR是假依赖, 因为你完全可以换一个寄存器去写, 这样就解决了WAW和WAR.

寄存器重命名的实现

寄存器重命名可以解决数据相关性中的WAW和WAR.

CPU中实际的寄存器个数大于ISA中规定的寄存器的个数.

  • 实际存在的寄存器叫物理寄存器(Physical Register).
  • ISA中定义的寄存器叫架构寄存器(Architecture Register).

寄存器重命名会动态地将架构寄存器映射到数量更多的物理寄存器, 来解决WAW和WAR问题.

使用ROB+ARF重命名

使用ROB进行寄存器重命名的算法流程大概如下:

  • 指令按照程序的原始顺序, 将信息写入ROB表项中.
  • 这条指令对应ROB表项的编号, 就是指令目的寄存器对应的物理寄存器的编号.

  • 有一个重命名映射表(Register Renaming Table), 里面存储如下信息:

    • 每个架构寄存器的最新值是位于ROB还是架构寄存器中.
    • 如果位于ROB中, 那么对应ROB的表项编号是什么.
      • 这个信息也就是一个架构寄存器对应的物理寄存器的编号.

  • 当FU写回时, 会将值写入ROB中, 此时这个值不一定对, 因为可能前面的指令会有分支预测失败/异常.

  • 当指令commit后, 会将ROB中的值同步到架构寄存器中, 对应的物理寄存器的编号也就被释放.

设计的优点:

  • 容易实现, 复杂度不高.

设计的缺点:

  • 没有目的寄存器的指令也会占用ROB表项, 导致面积浪费.
  • 一个指令可能从架构寄存器/ROB中读取源操作数, 如果是n-way的超标量处理器, 指令有两个源操作数, 那么架构寄存器/ROB需要支持2n个读口, 对面积消耗大.

使用ROB+ARF+PRF进行重命名

这种设计主要针对ROB+ARF中“没有目的寄存器的指令也会占用ROB”这一个缺点来进行改进.

如果采用这种方法, 那么FU写回的数据就不会在ROB中, 而是写入一个统一的PRF中, ROB中就不会存储数据.

  • PRF对应的编号就是架构寄存器对应的物理寄存器编号.

  • 架构寄存器的最新值, 可能在PRF中, 也可能在ARF中, 需要有一个重命名映射表来存储信息.

  • 当指令被commit之后, PRF的对应值就会被同步到ARF中.

设计的缺点:

  • 和ROB+ARF一样, 需要ARF和PRF同时支持多个读口/写口, 消耗较大.

使用统一的PRF重命名

如果使用统一的PRF进行寄存器重命名, 需要如下结构上的改变:

  • 硬件上没有架构寄存器(ARF) 只有物理寄存器(Physical Register File, PRF).
  • 有一个重命名映射表(Register Renaming Table), 存储架构寄存器和物理寄存器的映射关系.
  • 有一个FreeList, 其中存储所有还没有建立映射的物理寄存器编号, 采用FIFO实现.

算法过程如下:

  • 重命名映射表首先被初始化为0.

  • 对于一个指令的目的寄存器, 从FreeList中弹出来一个物理寄存器编号建立映射, 并将映射写入重命名映射表.

    • 如果FreeList空了, 那么需要暂停寄存器重命名以及之前的流水线.
  • 对于一个指令的源寄存器, 直接从映射表中查找对应的物理寄存器即可.

什么时候释放一个物理寄存器的编号?

当从FreeList中弹出来物理寄存器编号的同时, 我会去重命名映射表中, 看一下这个目的寄存器是不是和一个物理寄存器建立过映射.

  • 如果有建立过映射, 假设这个映射对应的物理寄存器编号叫lprd.

那么, 指令在commit之后, 就会释放lprd, 释放具体有两个操作:

  • 将重命名映射表中lprd对应的映射清空.
  • 将lprd写入FreeList.

解释如下, 考虑这样一段代码:

add r1, r2, r3
...
mul r1, r4, r5

经过寄存器重命名之后, 变成:

add p1, p7, p9
...
mul p6, p8, p2

当mul r1, r4, r5这条指令被commit后, 我原来建立的r1的映射已经没用了, 因为:

  • 如果一条指令需要用add r1, r2, r3中r1的值, 那么它必然位于add和mul指令之间, 此时mul指令还没有被commit.
  • 如果mul指令被commit后, 一条指令还想用r1的值, 那么它必然用的是mul指令对应的p6的值, 此时, 前面的r1->p1的映射就再也不会被使用, 因此p1就可以被释放.

FreeList的面积分析

对于一个n-way的超标量处理器来说:

  • 一个周期最多会对n个指令进行寄存器重命名, 那么FreeList需要有n个读口.
  • 一个周期最多n个指令commit, 那么FreeList需要有n个写口.

采用统一的PRF还会导致一个新的问题, 如果要从外部获取CPU的状态, 本质上是需要获取已经commit指令对应的物理寄存器的值.

但是物理寄存器中的值可能是FU刚写回, 还没有被commit, 或者是已经被commit, 这个属性需要一个新的表格来存储. 这个表格存储的内容就是: 一个架构寄存器对应的物理寄存器, 其中这个物理寄存器的值是最新被commit的指令写入的值.

设计的优势:

  • 一个寄存器的值只会被写入一次 (只会被写入到PRF)中, 适用于低功耗.
    • 如果是ROB+ARF, 那么一个寄存器的值会先写入ROB, 再写入ARF, 功耗较高.
  • 一个寄存器的值只会存在一处(PRF中), 相对于ROB+ARF的方法来说, 面积更小, 功耗更低.

超标量CPU的寄存器重命名

超标量CPU的寄存器重命名需要解决如下几个问题:

  • 读写端口数量的问题.
  • 一个周期内, 同时进行寄存器重命名的指令之间, 可能会存在复杂的相关性.

假设下面的讨论都是基于n-way的超标量处理器, 并且采用统一的PRF重命名.

读写口数量的分析

  • 对于FreeList:
    • 一个周期内, n条指令进行重命名, 需要有n个读口.
    • 一个周期内, n条指令commit, 需要有n个写口.
  • 对于Renaming Table:
    • 一个周期内, n条指令重命名, 假设一个指令有两个源寄存器, 需要有3n个读口 (其中1个多余的读口是要读出lprd), 要有n个写口.

指令数据相关性的分析

在超标量CPU的设计过程中, 真正需要特殊处理的相关性只有两种, 分别是RAW和WAW.

为什么RAW需要特殊处理?

考虑下面的指令:

add r0, r1, r2
add r0, r3, r0

假设重命名之后, 得到的指令是:

add p30, p11, p12
add p31, p13, p30

其中, 对于第二条add指令来说, r0到p30的映射直接来自于第一条指令, 而不需要从重命名表(Renaming Table)中读取.

为什么WAW需要特殊处理?

这个有两点原因:

  • 对于具有WAW关系的两条指令, 只需要将最后一条指令的映射关系写入Renaming Table中即可.
  • 指令信息写入ROB时, 如果两条指令具有WAW的关系, 那么后面指令的lprd这个信息不是从Renaming Table中读取得到的, 而是从上面指令bypass过来的.

因此, 在重命名阶段, 需要提供相关检查电路用来检查指令之间是否存在RAW和WAW.

  • 注意: 这个检查电路和Renaming Table的读取是并行的.

RAW相关性的处理

电路的设计逻辑如下:

  • 对于每一条指令, 需要将它的源寄存器和之前所有指令的目的寄存器进行比较.
  • 如果相等, 那么源寄存器重命名后的结果就不来自于Renaming Table, 而来自于对应的指令.

WAW相关性的处理

这个检查电路分为两个部分:

  • 将映射关系写入Renaming Table之前的检查电路.
  • 将一个指令的lprd写入ROB之前的检查电路.

对写入Renaming Table进行检查的电路设计如下:

  • 对于每一条指令, 需要将它的目的寄存器和下面所有指令的目的寄存器比较.
    • 如果存在相等, 那么只要让最下面指令的映射关系写入Renaming Table即可.
    • 具体实现就是只让Renaming Table对应的某一个写口使能即可.

对写入ROB进行检查的电路设计如下:

  • 对于每一条指令, 需要将它的目的寄存器和上面所有指令的目的寄存器比较.
    • 如果存在相等, 那么这条指令要写入ROB的lprd, 就不来自于Renaming Table, 而来自于上面指令的目的寄存器重命名的结果.

Renaming Table的设计

Renaming Table本质上是一个表格:

  • 表格的索引: 架构寄存器的地址.
  • 表格的值: 物理寄存器的地址.

读优先/写优先问题

读优先和写优先主要是针对存储元件来说的, 如果一个周期内既需要读, 又需要写, 并且读写的还是同一个地址, 那么有两种模式:

  • 读优先 (Read-First): 当前周期读出来的是原来的内容, 下个周期读出来的是上个周期写的内容.
  • 写优先 (Write-First): 读出来的就是当前写的内容, 读写能够在一个周期内完成.

对于Renaming Table来说, 写就一种情况:

  • 将一个指令的目的寄存器和FreeList中读取的物理寄存器的映射写入.

读就两种情况:

  • 以指令的源寄存器为索引, 读取对应的物理寄存器.
    • 如果读写地址一样, 那么此时应该读取的是最新的映射关系, 应该选择写优先(Write-First).
  • 以指令的目的寄存器为索引, 读取lprd.
    • 如果读写地址一样, 那么此时应该读取的是旧的lprd, 应该选择读优先(Read-First)

但是这两种情况是矛盾的, 此时, 实际情况下选用的是Read-First, 对于第一种情况, 会使用RAW的检查电路进行bypass, 不让这个指令读取Renaming Table.

寄存器重命名的恢复

如果一条指令已经经过了寄存器重命名这个pipeline的阶段, 那么它就会占据对应的资源(也就是在Renaming Table中写入了新的映射), 如果后续出现了异常/分支预测失败, 需要对这个指令占用的资源进行恢复, 这里的恢复主要针对Renaming Table而言.

Architecture State

Architecture State的思路是对Renaming Table做一个备份(Renaming Table Backup).

  • 当一条指令commit时, 会将这条指令的rd和prd的映射关系写入Renaming Table Backup.
  • 当某一条指令出现异常/分支预测失误时:
    • 先不处理, 先继续执行.
    • 当这条指令成为流水线中最老的指令时, 开始处理.
    • 将Renaming Table Backup中的信息同步到真实的Renaming Table中.

为什么这种做法是正确的?

  • 如果一个指令被commit, 那么说明这条指令是正确无误的.
  • 后续没有被commit的指令会占用Renaming Table, 但是如果出现异常/分支预测失败, 这些指令都会从流水线flush, Renaming Table需要恢复到这些被flush的指令之前, 能够被commit的指令之后的那个状态.

使用Architecture State的另外一个好处.

如果使用了统一的PRF进行寄存器重命名, 那么CPU中就只有物理寄存器, 没有架构寄存器.

如果在CPU外部, 想访问一个架构寄存器, 那么就可以直接从Renaming Table Backup中, 通过rd找到prd, 然后根据prd访问对应的物理寄存器即可.

WALK

WALK这种方法主要是使用ROB来将Renaming Table的状态推导回去.

一个指令写入ROB的信息可以包括:

  • rd.
  • 对应的prd.
  • lprd.

根据这些信息可以把Renaming Table还原到出现异常/分支预测失败之前.

当某一条指令出现异常/分支预测失败时:

  • 先不处理, 等待这条指令成为流水线上最老的指令时开始处理.
  • 逆序遍历ROB中所有的指令, 对于每一条指令I:
    • 在Renaming Table中, 将I.rd -> I.prd这个映射, 修改为I.rd -> I.lprd的映射即可.

©2023 LiGaOg

Built with Hexo and 3-hexo theme