FTB 分支预测器

Tags:
Categories:

FTB 简介

FTB 是香山 BPU 的第三个子预测器，它也能一并获取到 uFTB 和 TAGE-SC 的输出。在 FTB 的输入接口中，s1 通道含有 uFTB 的基础预测结果，s2 通道和 s3 通道中仅有 br_taken_mask 一组信号被 TAGE-SC 填充，并无 FTB 项生成的基础预测结果。FTB 的工作便是为 s2 和 s3 通道提供基础预测结果。

FTB 在功能和结构上都与 uFTB 类似，其主要区别就是 FTB 能够容纳更多的 FTB 项，并且 FTB 的预测结果是在 s2 与 s3 通道输出。正是由于容量大，其读出的速度上会比 uFTB 慢，无法被放置在第一周期产生预测结果，但大容量也使它能够获得更加精准的预测结果。

uFTB 功能简介

  • 缓存更多 FTB 项，为 s2 和 s3 通道提供基础预测结果。 FTB 预测器的本质是一个较大容量的存储器，其会根据当前预测的 PC 读出对应的 FTB 项，并在 s2 阶段产出预测结果。与此同时该 FTB 项还会被再保存一个周期，生成 s3 阶段预测结果。生成结果需要注意的点是要考虑到上一预测器输入的 br_taken_mask 字段，避免在生成时丢失。
  • 根据更新请求，更新存储中的 FTB 项。

FTB 存储结构

FTB 预测器中 FTB 项被放置在了一个专门的存储结构中，叫做 FTBBank ，在进一步查看 FTBBank 的结构之前，我们先来看一下 FTBBank 是怎样使用的。

FTB 读请求

FTBBank 的读请求接口如下：

  • req_pc 请求的 pc
    • 接口类型：Flipped(DecoupledIO(UInt(VAddrBits.W)))
  • read_resp 读出来的FTB项
    • 接口类型：FTBEntry
  • read_hits 命中了哪一路 (way)
    • 接口类型：Valid(UInt(log2Ceil(numWays).W))

其中 req_pc 的接口是 Decoupled 的，也就是说含有 valid 和 ready 信号。 FTB 需要在 s1 阶段开始之前便获取到 pc，因此 s0_pc 被送入 req_pc 接口，s0_fire 信号被连接至 req_pc 的 valid 信号，ready 信号被连接至预测器的流水控制信号 s1_ready 。

当 s0_fire 之后进入 s1 阶段，s0_fire 的下一个周期，也就是在 s1_fire 的同时，FTBBank 已经将读出的 FTB 项输出至 read_resp 接口，并计算好了 read_hits 。但此时因为读出已经浪费了过多时延，无法在 s1 阶段进行输出了，因此该读出结果被保存在内部寄存器中。在 s2 和 s3 阶段会在寄存器中读出该 FTB 项并生成预测结果。

FTBBank

FTBBank 中定义了一个存储器来存储所有的 FTB 项，存储器采用组相联的结构（如果你不清楚组相联的含义，请自行 RTFM），共含 512 个组（Set），每组有 4 路（Way），最多能存储 2048 个 FTB 项，存储 FTB 的同时还会存储与 FTB 项对应的 tag 用于匹配 FTB 项。

具体地，tag 被定义为 pc[29:10]，即在 pc 中截取了 20 位用于标识 FTB 项，pc 的具体划分方式如下：

  pc: | ... |<-- tag(20 bits) -->|<-- idx(9 bits) -->|<-- instOffset(1 bit) -->|

读出时，向存储器提供组序号(idx)，读出该组中所有路，然后检测是否有某一路的 tag 与当前 tag 匹配，如果匹配，则表示命中，读出的 FTB 项通过 read_resp 接口送出，并把命中的路编号通过 read_hits 接口送出。

预测结果生成

正如我们之前提到的，对于 FTB 预测器，它需要向 s2, s3 通道提供由 FTB 项转化来的基础预测结果，FTB 项已经在 s1 阶段被读出并保存。在 s2 和 s3 阶段只需直接读出便生成即可，但需要注意的一点就是保护 TAGE-SC 在 s2 及 s3 通道中产生的预测结果 br_taken_mask 字段，这一字段为条件分支指令提供了精确的预测结果。对于 s1 通道，FTB 预测器不予更改。

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

  • hit FTB表项是否命中

    • 生成方式：FTBBank 输出的 read_hits 信号 valid 位有效。

  • 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)对应一位，表示该分支是否被预测为 taken

    • 生成方式：若 FTB 项命中并且 always_taken 字段有效，则预测为 taken；否则由相应通道输入接口中提供的 br_taken_mask 信号来决定。

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

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

FTB meta

在预测的第三周期，FTB 预测器会将本次预测的一些辅助信息输出至 last_stage_meta 中，还会将读出的 FTB 项送到 last_stage_ftrb_entry 接口中。

FTB meta 中含有 hit 和 writeWay 两个信息，分别表示本次预测是否命中，以及在哪一路读出。之后更新通道中会产生本次预测的更新信息，这两个信息也会随之送入，来指导更新后的 FTB 项写入的位置。

FTB 更新

update 通道中已经为我们指定好了 pc 以及新 FTB 项，并且还有 meta 信息中的 hit 和 writeWay 。如果 meta 中的 hit 有效，说明之前这一 pc 对应的 FTB 项在存储器中是有存储的，我们只需将它写入到 writeWay 对应的路中即可。

如果无效，说明以前没有存储，但现在是否存储我们并不知道，有可能在此更新请求之前，该 pc 对应的 FTB 项被另一个更新请求写入了。因此我们还需要给 FTBBank 发送一个读请求，来判断其中是否存在对应的 FTB 项。如果存在，下周期可直接写入到该位置，否则，通知 FTBBank 为其重新分配一个位置。

因此 FTB 项的更新需要的周期数需随 hit 情况而定。

我们首先来看一下 FTBBank是怎样处理更新的。

FTBBank 更新

FTBBank 的更新接口如下，分为更新读接口和更新写接口两部分。

  • u_req_pc 更新读请求 pc

    • Flipped(DecoupledIO(UInt(VAddrBits.W)))

  • update_hits 读出的命中情况

    • Valid(UInt(log2Ceil(numWays).W))

  • update_access 有更新请求但 meta 信息指示未命中

    • Bool()

  • update_pc 更新写请求 pc

    • UInt(VAddrBits.W))

  • update_write_data 更新请求写入的数据，valid 有效的时候写

    • Flipped(Valid(new FTBEntryWithTag))

  • update_write_way 更新请求写入的路索引

    • UInt(log2Ceil(numWays).W))

  • update_write_alloc 是否需要分配FTB项（以前未命中）

    • Bool()

对于更新读接口，FTBBank 通过 u_req_pc 信号获取更新读请求，该请求要比预测时的读请求优先级更高，在下一个周期，FTBBank 会将命中情况通过 update_hits 接口送出。update_access 仅用于 FTBBank 内部某些状态判断。

对于更新写接口，FTBBank 通过 update_pc 信号获取更新写请求的 pc，并在 update_write_data 有效时向 update_write_way 对应的位置写入其中的数据。如果 update_write_alloc 有效，说明不能直接写入请求中指定的位置，而是需要重新分配一个位置。

分配的策略如下：

  • 如果所有路均已填充，则使用伪 LRU 替换算法选取要替换的路
  • 若存在空路，否则选取空路。

更新请求时序

  • meta hit 有效 若更新请求中 meta 指示为 hit，则我们直接根据更新请求中的信息，指定好写入的地址和数据即可，写入仅需一周期
  • meta hit 无效 此时，在接收到更新请求后，我们将请求中的 pc 连接至 FTBBank 的读端口，读端口在下一周期将结果返回。由于时延问题，我们将这一结果保存，并在下一周期使用。下一周期根据结果中的命中情况指定是否需要设置 update_write_alloc，并发出写请求。这时的更新过程总共花费了三个周期。

接口列表

信号类型 信号位 信号名 信号描述
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个
input io_in_bits_resp_in_0_s2_full_pred_0_br_taken_mask_0 预测结果输入
input io_in_bits_resp_in_0_s2_full_pred_0_br_taken_mask_1
input io_in_bits_resp_in_0_s2_full_pred_1_br_taken_mask_0
input io_in_bits_resp_in_0_s2_full_pred_1_br_taken_mask_1
input io_in_bits_resp_in_0_s2_full_pred_2_br_taken_mask_0
input io_in_bits_resp_in_0_s2_full_pred_2_br_taken_mask_1
input io_in_bits_resp_in_0_s2_full_pred_3_br_taken_mask_0
input io_in_bits_resp_in_0_s2_full_pred_3_br_taken_mask_1
input io_in_bits_resp_in_0_s3_full_pred_0_br_taken_mask_0
input io_in_bits_resp_in_0_s3_full_pred_0_br_taken_mask_1
input io_in_bits_resp_in_0_s3_full_pred_1_br_taken_mask_0
input io_in_bits_resp_in_0_s3_full_pred_1_br_taken_mask_1
input io_in_bits_resp_in_0_s3_full_pred_2_br_taken_mask_0
input io_in_bits_resp_in_0_s3_full_pred_2_br_taken_mask_1
input io_in_bits_resp_in_0_s3_full_pred_3_br_taken_mask_0
input io_in_bits_resp_in_0_s3_full_pred_3_br_taken_mask_1
output io_out_s2_full_pred_0_br_taken_mask_0 s2 阶段输出的完整预测结果
output io_out_s2_full_pred_0_br_taken_mask_1
output io_out_s2_full_pred_0_slot_valids_0
output io_out_s2_full_pred_0_slot_valids_1
output [40:0] io_out_s2_full_pred_0_targets_0
output [40:0] io_out_s2_full_pred_0_targets_1
output [40:0] io_out_s2_full_pred_0_jalr_target
output [3:0] io_out_s2_full_pred_0_offsets_0
output [3:0] io_out_s2_full_pred_0_offsets_1
output [40:0] io_out_s2_full_pred_0_fallThroughAddr
output io_out_s2_full_pred_0_is_br_sharing
output io_out_s2_full_pred_0_hit
output io_out_s2_full_pred_1_br_taken_mask_0 同上
output io_out_s2_full_pred_1_br_taken_mask_1
output io_out_s2_full_pred_1_slot_valids_0
output io_out_s2_full_pred_1_slot_valids_1
output [40:0] io_out_s2_full_pred_1_targets_0
output [40:0] io_out_s2_full_pred_1_targets_1
output [40:0] io_out_s2_full_pred_1_jalr_target
output [3:0] io_out_s2_full_pred_1_offsets_0
output [3:0] io_out_s2_full_pred_1_offsets_1
output [40:0] io_out_s2_full_pred_1_fallThroughAddr
output io_out_s2_full_pred_1_is_br_sharing
output io_out_s2_full_pred_1_hit
output io_out_s2_full_pred_2_br_taken_mask_0 同上
output io_out_s2_full_pred_2_br_taken_mask_1
output io_out_s2_full_pred_2_slot_valids_0
output io_out_s2_full_pred_2_slot_valids_1
output [40:0] io_out_s2_full_pred_2_targets_0
output [40:0] io_out_s2_full_pred_2_targets_1
output [40:0] io_out_s2_full_pred_2_jalr_target
output [3:0] io_out_s2_full_pred_2_offsets_0
output [3:0] io_out_s2_full_pred_2_offsets_1
output [40:0] io_out_s2_full_pred_2_fallThroughAddr
output io_out_s2_full_pred_2_is_jalr
output io_out_s2_full_pred_2_is_call
output io_out_s2_full_pred_2_is_ret
output io_out_s2_full_pred_2_last_may_be_rvi_call
output io_out_s2_full_pred_2_is_br_sharing
output io_out_s2_full_pred_2_hit
output io_out_s2_full_pred_3_br_taken_mask_0 同上
output io_out_s2_full_pred_3_br_taken_mask_1
output io_out_s2_full_pred_3_slot_valids_0
output io_out_s2_full_pred_3_slot_valids_1
output [40:0] io_out_s2_full_pred_3_targets_0
output [40:0] io_out_s2_full_pred_3_targets_1
output [40:0] io_out_s2_full_pred_3_jalr_target
output [3:0] io_out_s2_full_pred_3_offsets_0
output [3:0] io_out_s2_full_pred_3_offsets_1
output [40:0] io_out_s2_full_pred_3_fallThroughAddr
output io_out_s2_full_pred_3_fallThroughErr
output io_out_s2_full_pred_3_is_br_sharing
output io_out_s2_full_pred_3_hit
output io_out_s3_full_pred_0_br_taken_mask_0 s3 阶段输出的完整预测结果
output io_out_s3_full_pred_0_br_taken_mask_1
output io_out_s3_full_pred_0_slot_valids_0
output io_out_s3_full_pred_0_slot_valids_1
output [40:0] io_out_s3_full_pred_0_targets_0
output [40:0] io_out_s3_full_pred_0_targets_1
output [40:0] io_out_s3_full_pred_0_jalr_target
output [40:0] io_out_s3_full_pred_0_fallThroughAddr
output io_out_s3_full_pred_0_fallThroughErr
output io_out_s3_full_pred_0_is_br_sharing
output io_out_s3_full_pred_0_hit
output io_out_s3_full_pred_1_br_taken_mask_0 同上
output io_out_s3_full_pred_1_br_taken_mask_1
output io_out_s3_full_pred_1_slot_valids_0
output io_out_s3_full_pred_1_slot_valids_1
output [40:0] io_out_s3_full_pred_1_targets_0
output [40:0] io_out_s3_full_pred_1_targets_1
output [40:0] io_out_s3_full_pred_1_jalr_target
output [40:0] io_out_s3_full_pred_1_fallThroughAddr
output io_out_s3_full_pred_1_fallThroughErr
output io_out_s3_full_pred_1_is_br_sharing
output io_out_s3_full_pred_1_hit
output io_out_s3_full_pred_2_br_taken_mask_0 同上
output io_out_s3_full_pred_2_br_taken_mask_1
output io_out_s3_full_pred_2_slot_valids_0
output io_out_s3_full_pred_2_slot_valids_1
output [40:0] io_out_s3_full_pred_2_targets_0
output [40:0] io_out_s3_full_pred_2_targets_1
output [40:0] io_out_s3_full_pred_2_jalr_target
output [40:0] io_out_s3_full_pred_2_fallThroughAddr
output io_out_s3_full_pred_2_fallThroughErr
output io_out_s3_full_pred_2_is_jalr
output io_out_s3_full_pred_2_is_call
output io_out_s3_full_pred_2_is_ret
output io_out_s3_full_pred_2_is_br_sharing
output io_out_s3_full_pred_2_hit
output io_out_s3_full_pred_3_br_taken_mask_0 同上
output io_out_s3_full_pred_3_br_taken_mask_1
output io_out_s3_full_pred_3_slot_valids_0
output io_out_s3_full_pred_3_slot_valids_1
output [40:0] io_out_s3_full_pred_3_targets_0
output [40:0] io_out_s3_full_pred_3_targets_1
output [40:0] io_out_s3_full_pred_3_jalr_target
output [3:0] io_out_s3_full_pred_3_offsets_0
output [3:0] io_out_s3_full_pred_3_offsets_1
output [40:0] io_out_s3_full_pred_3_fallThroughAddr
output io_out_s3_full_pred_3_fallThroughErr
output io_out_s3_full_pred_3_is_br_sharing
output io_out_s3_full_pred_3_hit
output [222:0] io_out_last_stage_meta 最后一个阶段输出的 meta 信息
output io_out_last_stage_ftb_entry_valid 最后一个阶段输出的 FTB 项
output [3:0] io_out_last_stage_ftb_entry_brSlots_0_offset
output [11:0] io_out_last_stage_ftb_entry_brSlots_0_lower
output [1:0] io_out_last_stage_ftb_entry_brSlots_0_tarStat
output io_out_last_stage_ftb_entry_brSlots_0_sharing
output io_out_last_stage_ftb_entry_brSlots_0_valid
output [3:0] io_out_last_stage_ftb_entry_tailSlot_offset
output [19:0] io_out_last_stage_ftb_entry_tailSlot_lower
output [1:0] io_out_last_stage_ftb_entry_tailSlot_tarStat
output io_out_last_stage_ftb_entry_tailSlot_sharing
output io_out_last_stage_ftb_entry_tailSlot_valid
output [3:0] io_out_last_stage_ftb_entry_pftAddr
output io_out_last_stage_ftb_entry_carry
output io_out_last_stage_ftb_entry_isCall
output io_out_last_stage_ftb_entry_isRet
output io_out_last_stage_ftb_entry_isJalr
output io_out_last_stage_ftb_entry_last_may_be_rvi_call
output io_out_last_stage_ftb_entry_always_taken_0
output io_out_last_stage_ftb_entry_always_taken_1
input io_ctrl_btb_enable 使能信号
input io_s0_fire_0 s0 阶段流水线控制信号
input io_s0_fire_1
input io_s0_fire_2
input io_s0_fire_3
output io_s1_ready s1 阶段流水线控制信号
input io_s1_fire_0
input io_s1_fire_1
input io_s1_fire_2
input io_s1_fire_3
input io_s2_fire_0 s2 阶段流水线控制信号
input io_s2_fire_1
input io_s2_fire_2
input io_s2_fire_3
input io_update_valid 更新有效性
input [40:0] io_update_bits_pc 传回的预测块pc（用于指示更新的预测块）
input io_update_bits_ftb_entry_valid 是否启用
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_sharing 无条件跳转指令槽中存储条件分支指令
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_isCall 是否是函数调用
input io_update_bits_ftb_entry_isRet 是否是函数返回
input io_update_bits_ftb_entry_isJalr 是否是 jalr 指令
input io_update_bits_ftb_entry_last_may_be_rvi_call 最后一个指令槽存储的可能是 rvi 的 call 指令
input io_update_bits_ftb_entry_always_taken_0 是否预测为总是跳转
input io_update_bits_ftb_entry_always_taken_1 是否预测为总是跳转
input io_update_bits_old_entry 是否是旧的 FTB 项
input [222:0] io_update_bits_meta meta 信息
最后修改 October 27, 2024: Fix typo (e95831c)