uFTB 分支预测器

Tags:
Categories:

uFTB 简介

uFTB 是香山所有预测器中第一个预测器，也是其他预测器产生预测结果的基石。uFTB 工作在 s1 阶段，它获取到 s1_pc 后能在本周期内产生预测结果，并在 s1 通道输出，其他通道不予更改。分支指令的位置、指令的跳转目标都是由它来提供，后续预测器也将会根据这一预测结果进行进一步的预测。

而其本质则是一个 FTB 项缓存，其中存储了 FTB 项，基础的预测结果将直接由读出的 FTB 项生成。

因此，在你开始文档的阅读之前，请确保你理解了 FTB 项和含义以及预测结果接口的具体细节。

uFTB 功能简介

  • 缓存FTB项，生成一周期预测结果 uFTB 中维护了一个小型的 FTB 项缓存，拿到 PC 之后，会在一周期之内读出 PC 所对应的 FTB 项，并从 FTB 项生成 s1 阶段预测结果。
  • 维护两比特饱和计数器，提供基础条件分支结果 uFTB 中为 FTB项缓存的每一行都维护了对应的两比特饱和计数器，其方向预测结果会反映在 uFTB 的预测结果输出中。
  • 根据更新请求更新 FTB 缓存和两比特饱和计数器

uFTB 缓存结构

如上所述，uFTB 本质上是一个存储了 FTB 项的小型缓存，其大致结构如下图所示。

在当前版本的香山中，uFTB 共有 32 个缓存行，每个缓存行被称作 FauFTBWay，一个缓存行中可以存储一个 FTB 项。

当 s1 流水有效时，uFTB 会使用 s1_pc 来决定读出 uFTB 缓存的哪一项。缓存是根据 PC 中的 tag 字段来索引，tag 字段被定义为 pc[16: 1]，即在 PC 中截取了 16 比特作为标识来匹配缓存中的某一行。

缓存中的每一行，即 FauFTBWay 中的数据请求接口有三项：

  • req_tag 输入 pc 中截取的 tag 标识
  • resp 输出本行所存储的 FTB 项
  • resp_hit 输出指示本行的 FTB 项是否与 req_tag 匹配

uFTB 会将 tag 连接到缓存的每一行的数据请求接口，并根据 resp_hit 信号，选出命中的那一个 FTB 项。后续将会根据这一 FTB 项生成完整预测结果。

两比特饱和计数器

uFTB 中为 FTB 项缓存的每一行都维护了对应的两比特饱和计数器。我们知道，在一个 FTB 项最多可以存储两个条件分支指令，因此每一行对应的两比特饱和计数器也有两个，负责为其中的条件分支指令提供粗略的预测结果。

uFTB 在索引到 FTB 项时，也会索引到对应的两比特饱和计数器。

当预测结果生成时，会根据 FTB 项与其对应的两个两比特饱和计数器中的内容来产生。

预测结果生成

uFTB 通过 s1_pc 索引到对应的 FTB 项以及两个两比饱和计数器之后，需要根据他们产生预测结果。uFTB 产生的预测结果，将在 s1 流水有效时，通过 s1 通道进行输出，对于 s2 以及 s3 通道，uFTB 不予更改。

s1 预测结果中的信号产生方式可参考以下列表：

  • hit FTB表项是否命中

    • 生成方式：FauFTBWay 中的 resp_hit 信号，存在一个有效

  • slot_valids slot有效位，表示 ftb 项中的每个 slot 是否有效

  • targets 每个slot对应的跳转目标地址

  • offsets 每个slot中的指令相对于预测块起始地址的偏移

  • is_jal 预测块内包含jal指令

  • is_jalr 预测块内包含jalr指令

  • is_call 预测块内包含call指令

  • is_ret 预测块内包含ret指令

  • last_may_be_rvi_call 预测结果预测块末尾可能为一个RVI类型的call指令信号

  • is_br_sharing 最后一个slot (tailSlot) 中存储的是条件分支指令信号

    • 生成方式： FTB 项中对应字段导出

  • fallThroughErr FTB项中记录的 pftAddr 有误

    • 生成方式：比较 pftAddr 代表的预测块结束地址是否大于预测块的起始地址，如果小于，则代表出现错误，此信号置为有效。这种情况可能会发生在 pc 索引到错误的 FTB 项的情况。

  • fallThroughAddr 预测块的结束地址

    • 生成方式：如果 fallThroughErr 无效，则根据 pftAddr 生成，否则将其设置为起始地址 + 预测宽度。

  • br_taken_mask 分支预测结果，每个分支(slot)对应一个 bit，表示该分支是否被预测为 taken

    • 生成方式：根据 FTB 项中的 always_taken 字段和两比特饱和计数器指示结果生成。

  • jalr_target 本预测块中的 jalr 的跳转目标

    • 生成方式：FTB 项中 tailSlot 中的跳转目标。

uFTB 更新

uFTB 的更新涉及 FTB 项缓存的更新，以及两比特饱和计数器的更新，而更新的内容都是通过更新接口来获取的。

在 uFTB 预测器中，缓存和两比特饱和计数器的读与写并不冲突，因此我们无需考虑读和更新之间的时序冲突问题，可以将他们看做是独立的两部分。

FTB 缓存更新

FTB 缓存的更新过程很简单，更新通道中已经为我们指定好了 pc 以及新生成的 FTB 项，只需将其写入到缓存的指定位置即可。

FTB 缓存的更新需要两个周期：

  • 在第一周期，通过 update 中的信号计算出如下内容：
    • 更新请求对应的预测块在缓存的哪一行 更新请求中的 pc 截取 tag 后被发送到 FauFTBWay 的更新请求通道，根据每一行所返回的 hit 信号计算
  • 在第二周期，根据第一周期求出的需要更新的位置进行更新，如果无任何一行命中，则 uFTB 会使用 伪 LRU 替换算法 选出需要写入的行。
    • 具体的，更新通道中的 ftb_entry 信号组包含了新 FTB 项的完整信息，将该信息发送到需要更新的某一个缓存行即可。

两位饱和计数器更新

两位饱和计数器的更新则需要结合后续程序的真实执行情况，以及 FTB 项中记录的分支指令信息来进行更新了，而这些信息都可以从更新通道中进行获取。

两位饱和计数器的更新也需要两个周期：

  • 在第一周期，计算出槽中哪些条件分支指令 对应的两位饱和计数器 需要被更新，这需要满足以下条件：
    • 当前分支指令槽有效，并且存放了一条条件分支指令
    • 当前分支指令槽并没有被标识为 always_taken。（因为被标识为 always_taken 后不会采用两位饱和计数器的结果）
    • 当前分支指令槽不在实际发生了跳转的分支指令槽之后。
  • 在第二周期，更新饱和计数器
    • 根据第一周期生成的需要更新的掩码，以及更新通道中的 br_taken_mask 信息进行更新。

接口列表

信号类型 信号位 信号名 信号描述
input clock 输入时钟
input reset 复位信号
input [35:0] io_reset_vector 用于reset时，reset s1_pc_dup_0 提供的值
input [40:0] io_in_bits_s0_pc_0 输入位s0_pc 的 第0个复制
input [40:0] io_in_bits_s0_pc_1 同上 第1个
input [40:0] io_in_bits_s0_pc_2 同上 第2个
input [40:0] io_in_bits_s0_pc_3 同上 第3个
output [40:0] io_out_s1_pc_0 输出s1_pc 的 第0个复制
output [40:0] io_out_s1_pc_1 同上 第1个
output [40:0] io_out_s1_pc_2 同上 第2个
output [40:0] io_out_s1_pc_3 同上 第3个
output io_out_s1_full_pred_0_br_taken_mask_0 solt 0 是否被预测为 always taken
output io_out_s1_full_pred_0_br_taken_mask_1 solt 1 是否被预测为 always taken
output io_out_s1_full_pred_0_slot_valids_0 solt 0 是否启用
output io_out_s1_full_pred_0_slot_valids_1 solt 1 是否启用
output [40:0] io_out_s1_full_pred_0_targets_0 solt 0 对应的跳转目标地址
output [40:0] io_out_s1_full_pred_0_targets_1 solt 1 对应的跳转目标地址
output [3:0] io_out_s1_full_pred_0_offsets_0 solt 0 中分支指令相对于地址块起始pc的偏移
output [3:0] io_out_s1_full_pred_0_offsets_1 solt 1 中分支指令相对于地址块起始pc的偏移
output [40:0] io_out_s1_full_pred_0_fallThroughAddr 预测块的结束地址
output io_out_s1_full_pred_0_is_br_sharing solt 1（无条件跳转）是否被共享为有条件跳转指令
output io_out_s1_full_pred_0_hit
output io_out_s1_full_pred_1_br_taken_mask_0 类似 io_out_s1_pc_1 io_out_s1_full_pred_0的复制
output io_out_s1_full_pred_1_br_taken_mask_1
output io_out_s1_full_pred_1_slot_valids_0
output io_out_s1_full_pred_1_slot_valids_1
output [40:0] io_out_s1_full_pred_1_targets_0
output [40:0] io_out_s1_full_pred_1_targets_1
output [3:0] io_out_s1_full_pred_1_offsets_0
output [3:0] io_out_s1_full_pred_1_offsets_1
output [40:0] io_out_s1_full_pred_1_fallThroughAddr
output io_out_s1_full_pred_1_is_br_sharing
output io_out_s1_full_pred_1_hit
output io_out_s1_full_pred_2_br_taken_mask_0 同上
output io_out_s1_full_pred_2_br_taken_mask_1
output io_out_s1_full_pred_2_slot_valids_0
output io_out_s1_full_pred_2_slot_valids_1
output [40:0] io_out_s1_full_pred_2_targets_0
output [40:0] io_out_s1_full_pred_2_targets_1
output [3:0] io_out_s1_full_pred_2_offsets_0
output [3:0] io_out_s1_full_pred_2_offsets_1
output [40:0] io_out_s1_full_pred_2_fallThroughAddr
output io_out_s1_full_pred_2_is_br_sharing
output io_out_s1_full_pred_2_hit
output io_out_s1_full_pred_3_br_taken_mask_0 同上
output io_out_s1_full_pred_3_br_taken_mask_1
output io_out_s1_full_pred_3_slot_valids_0
output io_out_s1_full_pred_3_slot_valids_1
output [40:0] io_out_s1_full_pred_3_targets_0
output [40:0] io_out_s1_full_pred_3_targets_1
output [3:0] io_out_s1_full_pred_3_offsets_0
output [3:0] io_out_s1_full_pred_3_offsets_1
output [40:0] io_out_s1_full_pred_3_fallThroughAddr
output io_out_s1_full_pred_3_fallThroughErr
output io_out_s1_full_pred_3_is_br_sharing
output io_out_s1_full_pred_3_hit
output [222:0] io_out_last_stage_meta 输出最后阶段的元信息 io_out_last_stage_meta = {213’h0, resp_meta_pred_way_r_1, resp_meta_hit_r_1}
input io_ctrl_ubtb_enable 控制ubtb是否启用
input io_s0_fire_0 输入s0_fire_0，与 io_out_s1_pc_0 <= io_in_bits_s0_pc_0 的时钟门控相关
input io_s0_fire_1 输入s0_fire_1
input io_s0_fire_2 输入s0_fire_2
input io_s0_fire_3 输入s0_fire_3
input io_s1_fire_0 输入s1_fire_0
input io_s2_fire_0 输入s2_fire_0
input io_update_valid 更新有效性
input [40:0] io_update_bits_pc 传回的预测块pc（用于指示更新的预测块）
input [3:0] io_update_bits_ftb_entry_brSlots_0_offset solt 0 中分支指令相对于地址块起始pc的偏移
input [11:0] io_update_bits_ftb_entry_brSlots_0_lower 跳转目标地址的低位
input [1:0] io_update_bits_ftb_entry_brSlots_0_tarStat 跳转后的 pc 高位是否进退位
input io_update_bits_ftb_entry_brSlots_0_valid 是否启用
input [3:0] io_update_bits_ftb_entry_tailSlot_offset solt 1 中分支指令相对于地址块起始pc的偏移
input [19:0] io_update_bits_ftb_entry_tailSlot_lower 跳转目标地址的低位
input [1:0] io_update_bits_ftb_entry_tailSlot_tarStat 跳转后的 pc 高位是否进退位
input io_update_bits_ftb_entry_tailSlot_sharing 无条件跳转指令槽中存储条件分支指令
input io_update_bits_ftb_entry_tailSlot_valid 是否启用
input [3:0] io_update_bits_ftb_entry_pftAddr Partial Fallthrough Addr 如果预测块中没有跳转，那么程序将会顺序执行到达的地址，预测块的结束地址。
input io_update_bits_ftb_entry_carry pc+pft时是否产生进位
input io_update_bits_ftb_entry_always_taken_0 是否预测为总是跳转
input io_update_bits_ftb_entry_always_taken_1 是否预测为总是跳转
input io_update_bits_br_taken_mask_0 是否跳转
input io_update_bits_br_taken_mask_1 是否跳转
最后修改 October 27, 2024: Fix typo (e95831c)