riscv-boom's bim

bim

This module implements a Bimodal Branch Predictor using 2-bit saturating counters. The prediction is based on the MSB of the counter:

  • Counter = 0 (00): Strongly Not Taken
  • Counter = 1 (01): Weakly Not Taken
  • Counter = 2 (10): Weakly Taken
  • Counter = 3 (11): Strongly Taken

Key Features:

  • Multi-column memory organization for banking
  • Write bypass to handle read-after-write hazards
  • Pipeline stages: s0 (request) -> s1 (SRAM read) -> s2 (response)

参数

1
2
3
4
5
6
7
case class BoomBIMParams(
  nSets: Int = 2048,     // 总条目数
  nCols: Int = 8,         // 列数 (关键创新)
  singlePorted: Boolean = true, // 是否用单端口 SRAM
  useFlops: Boolean = false,   // 是否用寄存器阵列
  slow: Boolean = false        // 是否用慢速模式
)

元数据

1
2
3
4
class BIMMeta(implicit p: Parameters) extends BoomBundle ...
{
  val bims  = Vec(bankWidth, UInt(2.W))
}

地址分解

1
2
3
4
// s0_idx 是来自上游的、完整的 11-bit 索引 (log2(2048)=11)
val s0_col_mask = UIntToOH(s0_idx(log2Ceil(nCols)-1,0)) & Fill(nCols, s0_valid)
val s0_col_idx  = s0_idx >> log2Ceil(nCols) // s0_idx >> 3

更新bim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
for (c <- 0 until nCols) {
    val rdata = Wire(Vec(bankWidth, UInt(2.W)))
    rdata := DontCare
    val (ren, ridx) = if (params.slow) (s1_col_mask(c), s1_col_idx) else (s0_col_mask(c), s0_col_idx)
    val wen = WireInit(doing_reset || (s1_update.valid && s1_update.bits.is_commit_update && s1_update_col_mask(c) && !ren))
    if (params.slow) {
      s2_req_rdata_all(c) := rdata
    } else {
      s2_req_rdata_all(c) := RegNext(rdata)
    }
    if (params.useFlops) {
      val data = Reg(Vec(nSetsPerCol, Vec(bankWidth, UInt(2.W))))
      when (wen && doing_reset) {
        data(reset_idx) := VecInit(Seq.fill(bankWidth) { 2.U })
      } .elsewhen (wen) {
        for (i <- 0 until bankWidth) {
          when (s1_update_wmask(i)) {
            data(s1_update_col_idx)(i) := s1_update_wdata(i)
          }
        }
      }
      when (RegNext(ren) && !(wen && params.singlePorted.B)) {
        rdata := data(RegNext(ridx))
      }
    } else {
      val data = SyncReadMem(nSetsPerCol, Vec(bankWidth, UInt(2.W)))
      data.suggestName(s"bim_col_${c}")
      val r = if (params.singlePorted) data.read(ridx, ren && !wen) else data.read(ridx, ren)
      rdata := r
      when (wen) {
        val widx = Mux(doing_reset, reset_idx, s1_update_col_idx)
        val wdata = Mux(doing_reset, VecInit(Seq.fill(bankWidth) { 2.U }), s1_update_wdata)
        val wmask = Mux(doing_reset, (~(0.U(bankWidth.W))), s1_update_wmask.asUInt)
        data.write(widx, wdata, wmask.asBools)
      }
    }
  }

BIM 分支预测器工作流程详解

1. 整体架构概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
┌─────────────────────────────────────────────────────────────────────────────┐
│                         BIM Branch Predictor                                 │
│                                                                              │
│  ┌─────────────────────────────────────────────────────────────────────┐    │
│  │                    存储结构 (nCols 个列)                              │    │
│  │  ┌──────────┐ ┌──────────┐ ┌──────────┐       ┌──────────┐          │    │
│  │  │  Col 0   │ │  Col 1   │ │  Col 2   │  ...  │ Col N-1  │          │    │
│  │  │ ──────── │ │ ──────── │ │ ──────── │       │ ──────── │          │    │
│  │  │ Set 0    │ │ Set 0    │ │ Set 0    │       │ Set 0    │          │    │
│  │  │ Set 1    │ │ Set 1    │ │ Set 1    │       │ Set 1    │          │    │
│  │  │  ...     │ │  ...     │ │  ...     │       │  ...     │          │    │
│  │  │ Set M-1  │ │ Set M-1  │ │ Set M-1  │       │ Set M-1  │          │    │
│  │  └──────────┘ └──────────┘ └──────────┘       └──────────┘          │    │
│  │                                                                      │    │
│  │  每个 Set 包含 bankWidth 个 2-bit 计数器                               │    │
│  │  总共: nSets = 2048, nCols = 8, nSetsPerCol = 256                    │    │
│  └─────────────────────────────────────────────────────────────────────┘    │
│                                                                              │
│  ┌─────────────────────────────────────────────────────────────────────┐    │
│  │                    写旁路缓冲 (Write Bypass)                          │    │
│  │  ┌─────────────────────┐  ┌─────────────────────┐                    │    │
│  │  │ Entry 0             │  │ Entry 1             │                    │    │
│  │  │ idx: wrbypass_idxs  │  │ idx: wrbypass_idxs  │                    │    │
│  │  │ data: wrbypass      │  │ data: wrbypass      │                    │    │
│  │  └─────────────────────┘  └─────────────────────┘                    │    │
│  └─────────────────────────────────────────────────────────────────────┘    │
└─────────────────────────────────────────────────────────────────────────────┘

2. 2-bit 饱和计数器状态机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

                    ┌───────────────────────────────────────┐
                    │        2-bit 饱和计数器 (BIM)          │
                    └───────────────────────────────────────┘

     预测: Not Taken (NT)              预测: Taken (T)
    ┌─────────────────────┐         ┌─────────────────────┐
    │                     │         │                     │
    │  ┌─────┐   ┌─────┐  │         │  ┌─────┐   ┌─────┐  │
    │  │ 00  │◄──│ 01  │◄─┼─────────┼──│ 10  │◄──│ 11  │  │
    │  │ SNT │   │ WNT │  │   NT    │  │ WT  │   │ ST  │  │
    │  └──┬──┘   └──┬──┘  │         │  └──┬──┘   └──┬──┘  │
    │     │        │      │         │     │        │      │
    │     └───┬────┘      │         │     └───┬────┘      │
    │         │           │         │         │           │
    └─────────┼───────────┘         └─────────┼───────────┘
              │                               │
              │           Taken               │
              └───────────────────────────────┘

    SNT = 强不跳转 (00)    WNT = 弱不跳转 (01)
    WT  = 弱跳转   (10)    ST  = 强跳转   (11)

    预测逻辑: 取最高位 bit[1]，若为1则预测跳转

bimWrite 函数逻辑 (bim.scala:43-49):
输入: 当前值 v, 是否跳转 taken
输出: 新的计数器值

if (v == 3 && taken)     → 保持 3 (已饱和)
elif (v == 0 && !taken)  → 保持 0 (已饱和)
elif (taken)             → v + 1 (增加)
else                     → v - 1 (减少)

3. 索引计算与列选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
┌─────────────────────────────────────────────────────────────────────┐
│                        PC 索引映射                                   │
└─────────────────────────────────────────────────────────────────────┘

         PC / s0_idx (假设 log2(nSets) = 11 bits)
    ┌────────────────────────────────────────┐
    │  高位 (8 bits)    │   低位 (3 bits)    │
    │  col_idx          │   col_mask         │
    └────────────────────────────────────────┘
              │                   │
              │                   ▼
              │         ┌─────────────────────┐
              │         │   UIntToOH 解码     │
              │         │ 生成列选择 one-hot   │
              │         └─────────────────────┘
              │                   │
              ▼                   ▼
    ┌─────────────────┐  ┌──────────────────────────────┐
    │ 行地址 (row)    │  │ 列选择掩码 (col_mask)         │
    │ 选择哪一行 set  │  │ 例: 低3位=5 → 00100000        │
    └─────────────────┘  └──────────────────────────────┘

示例:
  s0_idx = 0b10110101011 (11 bits, nSets=2048)

  col_mask = UIntToOH(011) = 0b00001000  (选择 Col 3)
  col_idx  = 0b10110101 = 181           (选择第 181 行)

4. 流水线时序 (非慢速模式)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

┌─────────────────────────────────────────────────────────────────────────────┐
│                            预测流水线时序                                    │
└─────────────────────────────────────────────────────────────────────────────┘

  周期     S0 (取指)        S1 (访问)         S2 (输出)         S3 (延迟输出)
   │           │                │                 │                  │
   ▼           ▼                ▼                 ▼                  ▼
 ──────────────────────────────────────────────────────────────────────────────
   │                            │                 │                  │
   │  ┌──────────────┐          │                 │                  │
   │  │ s0_idx 计算   │          │                 │                  │
   │  │ s0_col_mask   │          │                 │                  │
   │  │ s0_col_idx    │──────────│                 │                  │
   │  └──────────────┘   RegNext │                 │                  │
   │                            │                 │                  │
   │                     ┌──────▼──────┐          │                  │
   │                     │ s1_col_mask │          │                  │
   │                     │ s1_col_idx  │          │                  │
   │                     │             │          │                  │
   │                     │ 发起 SRAM   │          │                  │
   │                     │ 读请求      │──────────│                  │
   │                     └─────────────┘  RegNext │                  │
   │                                              │                  │
   │                                      ┌───────▼───────┐          │
   │                                      │ s2_req_rdata  │          │
   │                                      │ (SRAM 返回)   │          │
   │                                      │               │          │
   │                                      │ s2_resp 计算  │──────────│
   │                                      │ = rdata[1]    │  RegNext │
   │                                      │               │          │
   │                                      │ io.resp.f2    │          │
   │                                      └───────────────┘          │
   │                                                                 │
   │                                                         ┌───────▼───────┐
   │                                                         │ io.resp.f3    │
   │                                                         │ io.f3_meta    │
   │                                                         └───────────────┘
 ──────────────────────────────────────────────────────────────────────────────

    关键路径:
    - f2 输出: S0 索引 → S1 SRAM 读 → S2 输出预测
    - f3 输出: 再延迟一个周期用于其他预测器使用

5. 更新流水线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

┌─────────────────────────────────────────────────────────────────────────────┐
│                            更新路径详解                                      │
└─────────────────────────────────────────────────────────────────────────────┘

                         s1_update (来自后端的更新请求)
                                    │
                                    ▼
        ┌───────────────────────────────────────────────────────────┐
        │                    解析更新信息                            │
        │  s1_update_idx      = 更新地址索引                         │
        │  s1_update_meta     = 保存的旧 BIM 值                      │
        │  s1_update_col_mask = 列选择掩码                           │
        │  s1_update_col_idx  = 行地址                              │
        └───────────────────────────────────────────────────────────┘
                                    │
                                    ▼
        ┌───────────────────────────────────────────────────────────┐
        │                    写旁路检查                              │
        │                                                           │
        │   wrbypass_hits = 检查更新地址是否命中旁路缓冲              │
        │                                                           │
        │   if (hit) {                                              │
        │       old_bim = wrbypass[hit_idx]  // 使用旁路中的新值     │
        │   } else {                                                │
        │       old_bim = s1_update_meta     // 使用元数据中的旧值    │
        │   }                                                       │
        └───────────────────────────────────────────────────────────┘
                                    │
                                    ▼
        ┌───────────────────────────────────────────────────────────┐
        │              计算新的计数器值 (每个 bank)                   │
        │                                                           │
        │  for w in 0..bankWidth:                                   │
        │    if (br_mask[w] || cfi_idx == w):                       │
        │      was_taken = 判断该指令是否真实跳转                     │
        │      s1_update_wdata[w] = bimWrite(old_bim[w], was_taken) │
        │      s1_update_wmask[w] = true                            │
        └───────────────────────────────────────────────────────────┘
                                    │
                    ┌───────────────┴───────────────┐
                    ▼                               ▼
        ┌───────────────────────┐       ┌───────────────────────┐
        │     写入 SRAM          │       │   更新写旁路缓冲       │
        │                        │       │                        │
        │  - 仅在 commit 时写入   │       │  if (hit):             │
        │  - 读写冲突时优先读     │       │    更新原条目           │
        │                        │       │  else:                 │
        │                        │       │    分配新条目           │
        │                        │       │    wrbypass_enq_idx++  │
        └───────────────────────┘       └───────────────────────┘

6. 写旁路机制详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

┌─────────────────────────────────────────────────────────────────────────────┐
│                         写旁路 (Write Bypass) 机制                           │
└─────────────────────────────────────────────────────────────────────────────┘

问题: SRAM 写入后不能立即读出 (需要至少1个周期延迟)
解决: 用寄存器缓存最近的写入，读取时先检查旁路

结构:
    ┌────────────────────────────────────────────────────────────┐
    │  wrbypass_idxs[0]  │  wrbypass_idxs[1]  │ (地址标签)        │
    ├────────────────────┼────────────────────┤                   │
    │  wrbypass[0]       │  wrbypass[1]       │ (数据: bankWidth  │
    │  [b0][b1]..[bN]    │  [b0][b1]..[bN]    │   个 2-bit 计数器) │
    └────────────────────┴────────────────────┘                   │
                                                                  │
    wrbypass_enq_idx: 循环队列入队指针                              │
    └────────────────────────────────────────────────────────────┘

工作流程:

    更新请求到达
         │
         ▼
    ┌─────────────────────────────────────┐
    │ 比较 s1_update_idx 与所有 wrbypass_idxs │
    └─────────────────────────────────────┘
         │
    ┌────┴────┐
    │         │
    ▼         ▼
  命中       未命中
    │         │
    │         ▼
    │    使用 s1_update_meta
    │    (原始预测时保存的值)
    │         │
    ▼         │
使用 wrbypass │
(最新写入值)  │
    │         │
    └────┬────┘
         │
         ▼
    计算新值并写入
         │
         ▼
    ┌────┴────┐
    │         │
    ▼         ▼
  命中       未命中
    │         │
    │         ▼
    │    分配新条目
    │    wrbypass_enq_idx++
    │         │
    ▼         │
更新原条目     │
    │         │
    └────┬────┘
         │
         ▼
       完成

这解决了 "read-after-write" 冲突问题

7. 多列存储结构详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

┌─────────────────────────────────────────────────────────────────────────────┐
│                        列组织 (Column Organization)                          │
└─────────────────────────────────────────────────────────────────────────────┘

为什么要分列?
  1. 减少每个 SRAM 块的大小，便于物理实现
  2. 在单端口配置下，不同列可以同时读写不同地址

存储布局:
                     nCols = 8 列
    ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
    │Col 0│Col 1│Col 2│Col 3│Col 4│Col 5│Col 6│Col 7│
    ├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
Row0│ S0  │ S1  │ S2  │ S3  │ S4  │ S5  │ S6  │ S7  │
    ├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
Row1│ S8  │ S9  │ S10 │ S11 │ S12 │ S13 │ S14 │ S15 │
    ├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
 ...│ ... │ ... │ ... │ ... │ ... │ ... │ ... │ ... │
    ├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
R255│S2040│S2041│S2042│S2043│S2044│S2045│S2046│S2047│
    └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

    每个单元格 (Set) 包含:
    ┌───────────────────────────────────────────┐
    │  Bank 0   Bank 1   Bank 2  ...  Bank N-1  │
    │  ┌─────┐ ┌─────┐ ┌─────┐      ┌─────┐     │
    │  │ 2b  │ │ 2b  │ │ 2b  │ ... │ 2b  │     │
    │  └─────┘ └─────┘ └─────┘      └─────┘     │
    └───────────────────────────────────────────┘

    总位宽 = bankWidth * 2 bits

读取路径:
    s0_idx 索引
         │
         ├─ 低 3 位 → col_mask (选择哪一列)
         │
         └─ 高 8 位 → col_idx  (选择哪一行)
                           │
                           ▼
                    只有一列被激活读取
                           │
                           ▼
                    Mux1H(col_mask, 所有列输出)
                           │
                           ▼
                    s2_req_rdata

8. 复位逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

┌─────────────────────────────────────────────────────────────────────────────┐
│                            复位流程                                          │
└─────────────────────────────────────────────────────────────────────────────┘

    系统复位
        │
        ▼
    doing_reset = true
    reset_idx = 0
        │
        ▼
    ┌─────────────────────────────────────┐
    │  每个周期:                           │
    │    1. 向所有列的 reset_idx 行写入     │
    │       初始值 = 2 (弱跳转 WT)          │
    │    2. reset_idx++                   │
    │    3. 预测输出被屏蔽 (!doing_reset)   │
    └─────────────────────────────────────┘
        │
        │  经过 nSetsPerCol (256) 个周期
        ▼
    reset_idx == nSetsPerCol - 1
        │
        ▼
    doing_reset = false
        │
        ▼
    正常工作

注意: 复位写入优先级高于正常更新写入
      wdata = Mux(doing_reset, 初始值, 更新值)

9. 单端口 vs 双端口模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

┌─────────────────────────────────────────────────────────────────────────────┐
│                     存储访问模式 (singlePorted 参数)                         │
└─────────────────────────────────────────────────────────────────────────────┘

单端口模式 (singlePorted = true, 默认):
─────────────────────────────────────────
    同一周期只能读或写，不能同时进行

    读请求       写请求
        │           │
        ▼           ▼
    ┌─────────────────────────────────┐
    │  if (读 && 写 && 同一列) {       │
    │      优先写，禁止读              │
    │      ren = ren && !wen          │
    │  }                              │
    └─────────────────────────────────┘

    优势: 面积小，功耗低
    劣势: 可能丢失预测机会

双端口模式 (singlePorted = false):
─────────────────────────────────────────
    可同时读写

    读请求       写请求
        │           │
        ▼           ▼
    ┌─────────────────────────────────┐
    │  读写可以并行进行                 │
    │  ren = ren (不受写影响)          │
    └─────────────────────────────────┘

    优势: 不丢失预测
    劣势: 面积大，功耗高

10. 完整数据流总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

┌─────────────────────────────────────────────────────────────────────────────┐
│                         完整数据流图                                         │
└─────────────────────────────────────────────────────────────────────────────┘

                              ┌─────────────────┐
                              │    取指请求      │
                              │   (s0_idx)      │
                              └────────┬────────┘
                                       │
              ┌────────────────────────┼────────────────────────┐
              │                        │                        │
              ▼                        ▼                        ▼
    ┌─────────────────┐      ┌─────────────────┐      ┌─────────────────┐
    │  计算 col_mask   │      │  计算 col_idx   │      │    更新路径      │
    │  (列选择 1-hot)  │      │  (行地址)       │      │  (s1_update)    │
    └────────┬────────┘      └────────┬────────┘      └────────┬────────┘
             │                        │                        │
             └────────────┬───────────┘                        │
                          │                                    │
                          ▼                                    ▼
                   ┌──────────────┐                   ┌──────────────┐
                   │   S1: 寄存    │                   │  写旁路检查   │
                   │   col_mask    │                   │              │
                   │   col_idx     │                   │              │
                   └──────┬───────┘                   └──────┬───────┘
                          │                                   │
                          ▼                                   ▼
             ┌────────────────────────────────────────────────────┐
             │                  SRAM 阵列 (nCols 列)              │
             │  ┌────────┐  ┌────────┐      ┌────────┐           │
             │  │ Col 0  │  │ Col 1  │ ...  │ Col N-1│           │
             │  │        │  │        │      │        │           │
             │  │ R   W  │  │ R   W  │      │ R   W  │           │
             │  └────────┘  └────────┘      └────────┘           │
             └────────────────────┬───────────────────────────────┘
                                  │
                                  ▼
                          ┌──────────────┐
                          │   S2: Mux1H  │
                          │  选择对应列   │
                          │  s2_req_rdata│
                          └──────┬───────┘
                                 │
                    ┌────────────┼────────────┐
                    │            │            │
                    ▼            ▼            ▼
           ┌─────────────┐ ┌──────────┐ ┌──────────┐
           │ 预测输出     │ │ 元数据    │ │ 更新旁路  │
           │             │ │          │ │          │
           │ taken =     │ │ bims =   │ │ 写入     │
           │ rdata[w][1] │ │ rdata    │ │ wrbypass │
           └──────┬──────┘ └────┬─────┘ └──────────┘
                  │             │
                  ▼             ▼
           ┌─────────────┐ ┌──────────┐
           │ io.resp.f2  │ │ S3: 寄存  │
           │ (即时输出)   │ │          │
           └─────────────┘ └────┬─────┘
                                │
                    ┌───────────┴───────────┐
                    ▼                       ▼
             ┌─────────────┐         ┌──────────┐
             │ io.resp.f3  │         │io.f3_meta│
             │ (延迟输出)   │         │(给TAGE用)│
             └─────────────┘         └──────────┘

关键参数总结

参数 默认值 说明
nSets 2048 总条目数
nCols 8 列数 (存储分区数)
nSetsPerCol 256 每列条目数
nWrBypassEntries 2 写旁路缓冲条目数
bankWidth 来自参数 每个取指包的指令数
singlePorted true 是否单端口 SRAM
useFlops false 是否用寄存器代替 SRAM
slow false 慢速模式 (多一拍延迟)

BIM 是一个简单但有效的基础预测器，通常与 TAGE 等更复杂的预测器配合使用，TAGE 的元数据中会包含 BIM 的预测值以便在更新时使用。

计算机体系结构
#分支预测
riscv-boom's bim
http://blog.luliang.online/2025/12/02/分支预测器bim/
作者
Luyoung
发布于
2025年12月2日
许可协议