RISC-V BOOM 分支预测器：Loop Predictor 机制

loop

The Loop Predictor specializes in predicting loop exit branches.It learns the iteration count of loops and predicts the loop exit when the learned count is reached.

Structure:

  • Small table (16 sets by default)
  • Each entry stores: tag, confidence, age, predicted count, speculative count
  • When speculative count matches predicted count with high confidence,
    predict the opposite of the base predictor (i.e., exit the loop)

Update Policy:

  • On misprediction at loop exit: update predicted count, adjust confidence
  • Age-based replacement for conflicting entries

Loop Predictor

功能定位

  • 检测固定次数的循环
  • 纠正TAGE对循环边界的预测
  • 处理for(i=0; i<N; i++)这类模式

核心问题

TAGE的限制：

1
2
3
4
5
6
7
for (int i = 0; i < 100; i++) {
    if (i < 99) {  // 这个分支
        // taken 99次
    } else {
        // not taken 1次
    }
}

TAGE看到的历史：TTTTTTT...TTTN（99个T，1个N）

  • 历史中99%是T，TAGE会强烈偏向Taken
  • 在第100次（应该Not Taken）时，TAGE可能预测错误

Loop预测器的作用：

  • 记住”这个分支每100次循环后会Not Taken”
  • 在第100次时反转TAGE的预测

存储结构

表项定义（loop.scala:31-37）：

1
2
3
4
5
6
7
class LoopEntry extends Bundle {
  val tag   = UInt(10.W)   // PC标签
  val conf  = UInt(3.W)    // 置信度（0-7）
  val age   = UInt(3.W)    // 年龄（用于替换）
  val p_cnt = UInt(10.W)   // 预测的循环次数（0-1023）
  val s_cnt = UInt(10.W)   // 当前循环计数（0-1023）
}

组织结构：

  • 16个sets，每个set有多列（way）
  • 全相联查找（在每个set内）

工作原理

预测阶段（loop.scala:81-85）：

1
2
3
4
5
6
7
8
9
10
11
// 默认：使用前一级预测器的结果
io.f3_pred := io.f3_pred_in

// 检查是否命中循环表
when (entry.tag === current_tag) {
  // 检查是否到达循环边界
  when (s_cnt === entry.p_cnt && entry.conf === 7.U) {
    // 反转预测！
    io.f3_pred := !io.f3_pred_in
  }
}

更新逻辑（loop.scala:95-106）：

1
2
3
4
5
6
7
8
9
10
11
12
// F4阶段（预测后的下一个cycle）
when (f4_fire && entry.tag === tag) {
  when (f4_scnt === entry.p_cnt && entry.conf === 7.U) {
    // 检测到循环边界，重置计数器
    entries(idx).s_cnt := 0.U
    entries(idx).age   := 7.U
  } .otherwise {
    // 循环内部，递增计数器
    entries(idx).s_cnt := f4_scnt + 1.U
    entries(idx).age   := Mux(age === 7.U, 7.U, age + 1.U)
  }
}

预测错误时的学习（loop.scala:114-167）：

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
when (mispredict && !doing_reset) {
  val entry = entries(update_idx)
  val tag_match = entry.tag === update_tag
  val ctr_match = entry.p_cnt === update_scnt

  when (entry.conf === 7.U && tag_match) {
    // 已学习，但预测错误 → 降低置信度
    wentry.conf := entry.conf - 1.U
    wentry.s_cnt := 0.U

  } .elsewhen (entry.conf === 7.U && !tag_match) {
    // 已学习，但tag不匹配 → 不做替换（保护高置信度entry）

  } .elsewhen (entry.conf =/= 0.U && tag_match && ctr_match) {
    // 学习中，计数匹配 → 增加置信度
    wentry.conf := entry.conf + 1.U
    wentry.s_cnt := 0.U

  } .elsewhen (entry.conf =/= 0.U && tag_match && !ctr_match) {
    // 学习中，计数不匹配 → 重新学习
    wentry.conf := 0.U
    wentry.p_cnt := update_scnt  // 更新预期循环次数
    wentry.s_cnt := 0.U

  } .elsewhen (entry.conf =/= 0.U && !tag_match && entry.age === 0.U) {
    // 学习中，tag不匹配，age低 → 替换
    wentry.tag := update_tag
    wentry.conf := 1.U
    wentry.p_cnt := update_scnt
    wentry.s_cnt := 0.U

  } .elsewhen (entry.conf =/= 0.U && !tag_match && entry.age =/= 0.U) {
    // 学习中，tag不匹配，age高 → 降低age
    wentry.age := entry.age - 1.U

  } .elsewhen (entry.conf === 0.U && tag_match) {
    // 未初始化，tag匹配
    when (ctr_match) {
      wentry.conf := 1.U  // 开始学习
      wentry.s_cnt := 0.U
    } .otherwise {
      wentry.p_cnt := update_scnt  // 记录循环次数
      wentry.s_cnt := 0.U
    }

  } .elsewhen (entry.conf === 0.U && !tag_match) {
    // 未初始化，分配新entry
    wentry.tag := update_tag
    wentry.conf := 1.U
    wentry.p_cnt := update_scnt
    wentry.s_cnt := 0.U
  }
}

状态机

Loop entry的学习过程：

1
2
3
4
5
6
7
8
9
10
11
[conf=0, 未初始化]
         ↓ 第一次预测错误，记录循环次数N
[conf=1, 学习中, p_cnt=N]
         ↓ 再次在第N次时预测错误
[conf=2, 学习中]
         ↓ 持续匹配
      ...
         ↓
[conf=7, 已学习] ← 开始生效，反转预测
         ↓ 如果再次错误
[conf=6, 降低置信度]

为什么有效

例子：

1
2
3
for (int i = 0; i < 100; i++) {
    if (i < 99) { ... }  // 分支A
}

TAGE的视角：

  • 历史：TTTTTT...TTTTN（99个T，1个N）
  • 预测：总是Taken（因为99%历史是T）
  • 第100次：预测Taken，实际Not Taken → 错误

Loop的视角：

  • 记录：这个分支每100次有一个边界
  • s_cnt: 0→1→2→…→99
  • 当s_cnt=99时：检测到边界，反转TAGE的预测
  • 预测：Not Taken → 正确

预测器的组合逻辑级联

代码实现

所有预测器的连接（config-mixins.scala:603-609）：

1
2
3
4
5
6
7
8
9
10
11
12
// 初始输入（全0预测）
val resp_in = (0.U).asTypeOf(new BranchPredictionBankResponse)

// 组合逻辑链
ubtb.io.resp_in(0)  := resp_in
bim.io.resp_in(0)   := ubtb.io.resp      // 组合逻辑
btb.io.resp_in(0)   := bim.io.resp       // 组合逻辑
tage.io.resp_in(0)  := btb.io.resp       // 组合逻辑
loop.io.resp_in(0)  := tage.io.resp      // 组合逻辑

// 最终输出
final_resp = loop.io.resp

Loop Predictor 循环预测器工作流程详解

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

┌──────────────────────────────────────────────────────────────────────────────────────────┐
│                              Loop Branch Predictor                                        │
│                                                                                           │
│  ┌─────────────────────────────────────────────────────────────────────────────────────┐ │
│  │                      多列结构 (bankWidth 个独立 Column)                              │ │
│  │                                                                                      │ │
│  │   Column 0           Column 1           Column 2          ...      Column N-1       │ │
│  │  ┌──────────────┐   ┌──────────────┐   ┌──────────────┐         ┌──────────────┐   │ │
│  │  │  entries[16] │   │  entries[16] │   │  entries[16] │   ...   │  entries[16] │   │ │
│  │  │              │   │              │   │              │         │              │   │ │
│  │  │  LoopEntry   │   │  LoopEntry   │   │  LoopEntry   │         │  LoopEntry   │   │ │
│  │  │  寄存器阵列   │   │  寄存器阵列   │   │  寄存器阵列   │         │  寄存器阵列   │   │ │
│  │  └──────────────┘   └──────────────┘   └──────────────┘         └──────────────┘   │ │
│  │         │                  │                  │                        │           │ │
│  │         └───────────���──────┴──────────────────┴────────────────────────┘           │ │
│  │                                         │                                           │ │
│  │                                         ▼                                           │ │
│  │                              ┌─────────────────────┐                                │ │
│  │                              │   Loop 覆盖逻辑     │                                │ │
│  │                              │ (高置信度时翻转预测) │                                │ │
│  │                              └─────────────────────┘                                │ │
│  └─────────────────────────────────────────────────────────────────────────────────────┘ │
│                                                                                           │
│  基础预测器: io.resp_in(0) 提供初始预测 (通常来自 TAGE/BIM)                               │
│  Loop 预测器: 在检测到稳定循环模式时覆盖基础预测                                           │
└─────────────────────────────────────��────────────────────────────────────────────────────┘

2. 数据结构详解

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

┌─────────────────────────────────────────────────────────────────────────────────┐
│                           LoopEntry (循环条目)                                   │
└─────────────────────────────────────────────────────────────────────────────────┘

┌────────────────────────────────────���────────────────────────────────────────────┐
│                           LoopEntry Bundle                                       │
├────────────┬────────────┬────────────┬────────────┬────────────────────────────┤
│  tag (10b) │  conf (3b) │  age (3b)  │ p_cnt (10b)│        s_cnt (10b)         │
│  地址标签   │  置信度    │  年龄计数  │ 预测循环次数│        当前迭代次数         │
└────────────┴────────────┴────────────┴────────────┴────────────────────────────┘

字段详解:
┌────────────┬───────────────────────────────────────────────────────────────────┐
│    tag     │ 分支地址的高位标签，用于匹配检查                                    │
│            │ 范围: 10 bits                                                      │
├────────────┼────────────────────────────────────────────────────────────────��──┤
│    conf    │ 置信度计数器 (0-7)                                                 │
│            │ conf = 7: 完全学习，可以进行预测覆盖                                │
│            │ conf = 0: 未学习/不确定                                            │
├────────────┼───────────────────────────────────────────────────────────────────┤
│    age     │ 年龄计数器 (0-7)，用于替换策略                                      │
│            │ age = 0: 可被替换                                                  │
│            │ age = 7: 最近活跃，不应被替换                                       │
├────────────┼───────────────────────────────────────────────────────────────────┤
│   p_cnt    │ 预测的循环次数 (Predicted Count)                                   │
│            │ 记录学习到的循环迭代次数                                            │
│            │ 范围: 0-1023 (10 bits)                                             │
├────────────┼───────────────────────────────────────────────────────────────────┤
│   s_cnt    │ 推测执行计数 (Speculative Count)                                   │
│            │ 当前循环已执行的迭代次数                                            │
│            │ 当 s_cnt == p_cnt 时，预测循环结束                                  │
└────────────┴───────────────────────────────────────────────────────────────────┘


LoopMeta (预测元数据):
┌───────��──────────────────────────────────────────────────────────────���──────────┐
│                           LoopMeta Bundle                                        │
├─────────────────────────────────────────────────────────────────────────────────┤
│                         s_cnt (10 bits)                                          │
│                     记录预测时的推测计数值                                        │
│                     用于误预测恢复时修复状态                                      │
└─────────────────────────────────────────────────────────────────────────────────┘

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
29
30
31
32
33
34
35

┌─────────────────────────────────────────────────────────────────────────────────┐
│                        循环预测原理                                              │
└──────────────────────────────��──────────────────────────────────────────────────┘

典型循环代码:
    for (int i = 0; i < 100; i++) {
        // loop body
    }

对应的分支行为:
    迭代 0:   Taken  (继续循环)
    迭代 1:   Taken  (继续循环)
    ...
    迭代 98:  Taken  (继续循环)
    迭代 99:  Not Taken (退出循环)  ← 这是关键点!

问题: 传统预测器 (BIM/TAGE) 难以预测最后一次退出
     因为前 99 次都是 Taken，会训练计数器趋向 Taken

Loop Predictor 解决方案:
    1. 学习循环的精确次数 (p_cnt = 100)
    2. 跟踪当前迭代 (s_cnt = 0, 1, 2, ... 99)
    3. 当 s_cnt == p_cnt 时，预测 Not Taken (覆盖基础预测器)

    迭代:     0     1     2    ...   98    99
              │     │     │          │     │
    s_cnt:    0     1     2    ...   98    99
              │     │     │          │     │
    p_cnt:   100   100   100   ...  100   100
              │     │     │          │     │
    匹配?:   No    No    No    ...  No    Yes!
              │     │     │          │     │
    动作:   透传   透传   透传  ...  透传  翻转!

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

┌─────────────────────────────────────────────────────────────────────────────────┐
│                        置信度 (conf) 状态机                                      │
└─────────────────────────────────────────────────────────────────────────────────┘

                    置信度等级与行为
    ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
    │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │
    │未学 │ 低  │ 低  │ 中  │ 中  │ 高  │ 高  │完全 │
    │ 习  │置信 │置信 │置信 │置信 │置信 │置信 │学习 │
    └─────┴─────┴─────┴─��───┴─────┴─────┴─────┴─────┘
                                              │
                                              ▼
                                     只有 conf=7 时
                                     才会覆盖基础预测

状态转换:

    ┌──────────────────────────────────────────────────────────────────────────┐
    │                                                                           │
    │     新分支发现                 循环计数匹配              最终学习完成       │
    │         │                          │                        │            │
    │         ▼                          ▼                        ▼            │
    │     ┌───────┐  匹配且计数正确  ┌───────┐  匹配且计数正确  ┌───────┐       │
    │     │conf=0 │ ─────────────► │conf=1 │ ─────────────► │conf=7 │       │
    │     │ 未学习 │                │ 开始  │    ...         │ 完成  │       │
    │     └───────┘                └───────┘                └───────┘       │
    │         ▲                        │                        │            │
    │         │                        │ 计数不匹配              │ 误预测     │
    │         │                        ▼                        ▼            │
    │         │                   重置 p_cnt              conf = conf - 1    │
    │         │                   保持 conf                                   │
    │         │                                                               │
    │         └───────────────────────────────────────────────────────────────│
    │                          循环模式改变时完全重置                           │
    └──────────────────────────────────────────────────────────────────────────┘

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

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

  周期     F2 (查找)        F3 (预测)         F4 (更新)
   │          │                │                 │
   ▼          ▼                ▼                 ▼
 ─────────────────────────────────────────────────────────────────
   │                           │                 │
   │  ┌──────────────────┐     │                 │
   │  │ f2_req_valid     │     │                 │
   │  │ f2_req_idx       │     │                 │
   │  │                  │     │                 │
   │  │ 读取 entries     │─────│                 │
   │  │ f2_entry =       │ Reg │                 │
   │  │ entries(idx)     │     │                 │
   │  │                  │     │                 │
   │  │ 旁路检查:        │     │                 │
   │  │ repair/mispredict│     │                 │
   │  └──────────────────┘     │                 │
   │                           │                 │
   │                    ┌──────▼──────┐          │
   │                    │ f3_entry    │          │
   │                    │ f3_scnt     │          │
   │                    │ f3_tag      │          │
   │                    │             │          │
   │                    │ 标签匹配?   │          │
   │                    │ tag == f3_tag│         │
   │                    │             │          │
   │                    │ 预测条件:   │          │
   │                    │ s_cnt==p_cnt│          │
   │                    │ && conf==7  │──────────│
   │                    │             │   Reg    │
   │                    │ 输出:       │          │
   │                    │ f3_pred     │          │
   │                    │ f3_meta     │          │
   │                    └─────────────┘          │
   │                                             │
   │                                     ┌───────▼───────┐
   │                                     │ f4_fire       │
   │                                     │ f4_entry      │
   │                                     │ f4_scnt       │
   │                                     │               │
   │                                     │ 更新 entries: │
   │                                     │ s_cnt++       │
   │                                     │ age 管理      │
   │                                     └───────────────┘
 ─────────────────────────────────────────────────────────────────

关键点:

  • F2: 读取条目，处理旁路
  • F3: 标签匹配，做出预测决策
  • F4: 推测更新 s_cnt (在预测被使用后)

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

┌─────────────────────────────────────────────────────────────────────────────────┐
│                         预测决策流程                                             │
└─────────────────────────────────────────────────────────────────────────────────┘

                         ┌─────────────────────────┐
                         │   f3_pred_in            │
                         │ (来自基础预测器的预测)   │
                         └────────────┬────────────┘
                                      │
                                      ▼
                         ┌─────────────────────────┐
                         │   f3_entry.tag == f3_tag?│
                         │   (标签匹配检查)         │
                         └────────────┬────────────┘
                                      │
                    ┌─────────────────┴─────────────────┐
                    │                                   │
                    ▼                                   ▼
              标签匹配                             标签不匹配
                    │                                   │
                    ▼                                   ▼
    ┌───────────────────────────────┐      ┌───────────────────────┐
    │  f3_scnt == f3_entry.p_cnt?   │      │  透传基础预测          │
    │  && f3_entry.conf == 7?       │      │  f3_pred = f3_pred_in  │
    └───────────────┬───────────────┘      └───────────────────────┘
                    │
       ┌────────────┴────────────┐
       │                         │
       ▼                         ▼
    条件满足                  条件不满足
       │                         │
       ▼                         ▼
┌──────────────────┐    ┌──────────────────┐
│ 翻转预测!         │    │ 透传基础预测      │
│ f3_pred =        │    │ f3_pred =        │
│   !f3_pred_in    │    │   f3_pred_in     │
└──────────────────┘    └──────────────────┘


代码对应 (loop.scala:78-85):

    io.f3_pred := io.f3_pred_in    // 默认透传

    when (f3_entry.tag === f3_tag) {
      when (f3_scnt === f3_entry.p_cnt && f3_entry.conf === 7.U) {
        io.f3_pred := !io.f3_pred_in    // 翻转!
      }
    }

7. 推测更新逻辑 (F4 阶段)

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
┌───────────────────────��─────────────────────────────────────────────────────────┐
│                         F4 推测更新                                              │
└─────────────────────────────────────────────────────────────────────────────────┘

目的: 在预测被前端使用后，更新循环计数器

触发条件: f4_fire (预测已发送且被采用)

                         ┌─────────────────────────┐
                         │       f4_fire           │
                         │   (预测被采用)           │
                         └────────────┬────────────┘
                                      │
                                      ▼
                         ┌─────────────────────────┐
                         │ f4_entry.tag == f4_tag? │
                         └────────────┬────────────┘
                                      │
                    ┌─────────────────┴─────────────────┐
                    │                                   │
                    ▼                                   ▼
              标签匹配                             标签不匹配
                    │                                   │
                    ▼                                   ▼
    ┌───────────────────────────────┐      ┌───────────────────────┐
    │  循环结束条件?                 │      │  不更新               │
    │  s_cnt == p_cnt && conf == 7   │      │                       │
    └───────────────┬───────────────┘      └───────────────────────┘
                    │
       ┌────────────┴────────────┐
       │                         │
       ▼                         ▼
    循环结束                  循环继续
       │                         │
       ▼                         ▼
┌──────────────────┐    ┌────────────────────────┐
│ 重置计数器:       │    │ 递增计数器:             │
│ s_cnt = 0        │    │ s_cnt = s_cnt + 1      │
│ age = 7 (刷新)   │    │ age = min(age+1, 7)    │
└──────────────────┘    └────────────────────────┘


示例 (循环 100 次):

    迭代     s_cnt    p_cnt    动作
    ───────────────────────────────────
      0        0      100     s_cnt++ → 1
      1        1      100     s_cnt++ → 2
      2        2      100     s_cnt++ → 3
     ...      ...     ...     ...
     98       98      100     s_cnt++ → 99
     99       99      100     s_cnt++ → 100 ✗ 应该重置!
    ───────────────────────────────────

    等等，上面有问题！因为预测翻转发生在 s_cnt==p_cnt 时
    实际上:

    迭代     s_cnt    p_cnt    预测        动作
    ───────────────────────────────────────────────
      0        0      100     Taken       s_cnt++ → 1
     ...      ...     ...     ...         ...
     99       99      100     Taken       s_cnt++ → 100
    100      100      100     翻转→NT!    s_cnt = 0 (重置)
    ───────────────────────────────────────────────

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
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
68
69
70
71
72
73
74
75
76
77
78
79
┌─────────────────────────────────────────────────────────────────────────────────┐
│                         误预测更新状态机                                         │
└─────────────────────────────────────────────────────────────────────────────────┘

输入信号:
  - update_mispredict: 分支误预测
  - tag_match: 标签是否匹配
  - ctr_match: 循环计数是否匹配 (p_cnt == update_meta.s_cnt)

状态转换表:

┌─────────────────┬───────────┬───────────┬─────────────────────────────────────────┐
│     当前状态     │ tag_match │ ctr_match │              操作                        │
├─────────────────┼───────────┼───────────┼─────────────────────────────────────────┤
│ conf=7 (已学习) │    Yes    │     -     │ conf--, s_cnt=0 (降低置信度)             │
├─────────────────┼───────────┼───────────┼─────────────────────────────────────────┤
│ conf=7 (已学习) │    No     │     -     │ 不操作 (保护高置信条目)                   │
├─────────────────┼───────────┼───────────┼─────────────────────────────────────────┤
│ conf∈[1,6]     │    Yes    │    Yes    │ conf++, s_cnt=0 (增加置信度)             │
├─────────────────┼───────────┼───────────┼─────────────────────────────────────────┤
│ conf∈[1,6]     │    Yes    │    No     │ conf=0, s_cnt=0, p_cnt=meta.s_cnt       │
│                 │           │           │ (循环次数改变，重新学习)                  │
├─────────────────┼───────────┼───────────┼─────────────────────────────────────────┤
│ conf∈[1,6]     │    No     │     -     │ if age==0: 替换条目                      │
│                 │           │           │ else: age-- (老化)                       │
├─────────────────┼───────────┼───────────┼─────────────────────────────────────────┤
│ conf=0 (未学习) │    Yes    │    Yes    │ conf=1, age=7, s_cnt=0 (开始学习)        │
├─────────────────┼───────────┼───────────┼─────────────────────────────────────────┤
│ conf=0 (未学习) │    Yes    │    No     │ p_cnt=meta.s_cnt, age=7, s_cnt=0        │
│                 │           │           │ (更新预测计数)                           │
├─────────────────┼───────────┼───────────┼─────────────────────────────────────────┤
│ conf=0 (未学习) │    No     │     -     │ 分配新条目: tag, conf=1, age=7,         │
│                 │           │           │ s_cnt=0, p_cnt=meta.s_cnt               │
└─────────────────┴─────────���─┴─��─────────┴─────────────────────────────────────────┘


状态机可视化:

                              误预测事件
                                  │
                                  ▼
            ┌─────────────────────────────────────────────────┐
            │                 conf == 7?                      │
            └─────────────────────┬───────────────────────────┘
                    ┌─────────────┴─────────────┐
                    │                           │
                    ▼                           ▼
                conf = 7                    conf < 7
                    │                           │
                    ▼                           ▼
            ┌─────────────┐           ┌─────────────────────┐
            │ tag_match?  │           │     conf == 0?      │
            └──────┬──────┘           └──────────┬──────────┘
               ┌───┴───┐                    ┌────┴────┐
               ▼       ▼                    ▼         ▼
             Yes      No                 conf=0    conf>0
               │       │                    │         │
               ▼       ▼                    ▼         ▼
          ┌────────┐ ┌────────┐      ┌──────────┐ ┌────────────┐
          │conf--  │ │不操作  │      │tag_match?│ │ tag_match? │
          │s_cnt=0 │ │(保护)  │      └────┬─────┘ └─────┬──────┘
          └────────┘ └────────┘       ┌───┴───┐     ���───┴───┐
                                      ▼       ▼     ▼       ▼
                                    Yes      No   Yes      No
                                      │       │     │       │
                                      ▼       ▼     ▼       ▼
                                 ┌────────┐ ┌────┐ ┌───┐ ┌────────┐
                                 │ctr_match│ │分配│ │ctr│ │age==0?│
                                 └────┬───┘ │新条│ │匹配│ └───┬───┘
                                  ┌───┴───┐ │目  │ │?  │   ┌─┴──┐
                                  ▼       ▼ └────┘ └─┬─┘   ▼    ▼
                                Yes      No      ┌──┴──┐ 替换 age--
                                  │       │      ▼     ▼
                                  ▼       ▼    Yes    No
                            ┌────────┐ ┌────────┐│      │
                            │conf=1  │ │更新    ││      │
                            │age=7   │ │p_cnt   │▼      ▼
                            └────────┘ └────────┘conf++ 更新p_cnt

9. 修复更新 (Repair Update)

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

┌─────────────────────────���───────────────────────────────────────────────────────┐
│                         修复更新 (Repair)                                        │
└─────────────────────────────────────────────────────────────────────────────────┘

场景: 推测执行被取消，需要恢复 s_cnt 到正确状态

    误预测发生
         │
         ▼
    ┌─────────────────────────────────────────────────────────────┐
    │  is_repair_update = true                                   │
    │  update_meta.s_cnt = 正确的循环计数值                        │
    └─────────────────────────────────────────────────────────────┘
         │
         ▼
    ┌─────────────────────────────────────────────────────────────┐
    │  检查条件:                                                  │
    │  1. tag_match (确保是同一个循环)                            │
    │  2. !(f4_fire && update_idx == f4_idx)                     │
    │     (避免与推测更新冲突)                                     │
    └─────────────────────────────────────────────────────────────┘
         │
         ▼
    ┌─────────────────────────────────────────────────────────────┐
    │  entries(update_idx).s_cnt := update_meta.s_cnt            │
    │  恢复到误预测前的计数值                                      │
    └─────────────────────────────────────────────────────────────┘


F2 阶段的旁路处理:

    当前读取的条目可能已经被修复/误预测更新影响
    需要实时旁路:

    f2_entry.s_cnt :=
        if (update_repair && idx_match)      → update_meta.s_cnt
        elif (update_mispredict && idx_match) → 0
        else                                  → entries(idx).s_cnt

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

┌─────────────────────────────────────────────────────────────────────────────────┐
│                         年龄 (Age) 替换策略                                      │
└─────────────────────────────────────────────────────────────────────────────────┘

目的: 管理条目的生命周期，平衡新旧循环

年龄计数器行为:

    ┌────────────────────────────────────────────────────────────────────────────┐
    │                                                                             │
    │   增加 age (保护条目):                                                       │
    │   ├─ 每次成功预测使用: age = min(age + 1, 7)                                │
    │   ├─ 新分配条目: age = 7                                                   │
    │   └─ 循环结束重置: age = 7                                                  │
    │                                                                             │
    │   减少 age (老化):                                                          │
    │   └─ 误预测且标签不匹配: age = age - 1 (如果 age > 0)                       │
    │                                                                             │
    │   替换条件:                                                                 │
    │   └─ conf ∈ [1,6] && !tag_match && age == 0                                │
    │                                                                             │
    └────────────────────────────────────────────────────────────────────────────┘

替换流程:

    新循环分支需要条目
           │
           ▼
    ┌─────────────────────────────────────┐
    │  检查目标位置的条目                  │
    │  entry = entries(hash(pc))          │
    └────────────��────┬───────────────────┘
                      │
                      ▼
    ┌─────────────────────────────────────┐
    │  conf == 7?                         │
    └─────────────────┬───────────────────┘
                      │
         ┌────────────┴────────────┐
         │                         │
         ▼                         ▼
    conf == 7                  conf < 7
    (已完全学习)                (未完全学习)
         │                         │
         ▼                         ▼
    ┌─────────────┐        ┌─────────────────────┐
    │ 不替换!     │        │ age == 0?           │
    │ 保护高置信度│        └──────────┬──────────┘
    └─────────────┘                   │
                            ┌─────────┴───────��─┐
                            │                   │
                            ▼                   ▼
                        age == 0            age > 0
                            │                   │
                            ▼                   ▼
                    ┌─────────────┐      ┌─────────────┐
                    │ 替换!       │      │ age--       │
                    │ 分配新条目  │      │ 下次可能替换│
                    └─────────────┘      └─────────────┘

11. 完整数据流图

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

┌──────────────────────────────────────────────────────────────────────────────────────────┐
│                           Loop Predictor 完整数据流                                       │
└──────────────────────────────────────────────────────────────────────────────────────────┘

                              ┌─────────────────┐
                              │  取指请求        │
                              │  s2_idx         │
                              │  s2_valid       │
                              └────────┬────────┘
                                       │
                                       ▼
    ┌─────────────────────────────────────────────────────────────────────────────────────┐
    │                              F2: 条目读取                                            │
    │                                                                                      │
    │   ┌─��───────────────────────────────────────────────────────────────────────────┐   │
    │   │  对每个 Column (0..bankWidth-1):                                             │   │
    │   │                                                                              │   │
    │   │    f2_entry = entries(f2_req_idx)                                           │   │
    │   │                                                                              │   │
    │   │    旁路检查 (同一索引的更新):                                                  │   │
    │   │    if (update_repair && idx_match):                                         │   │
    │   │        f2_entry.s_cnt = update_meta.s_cnt                                   │   │
    │   │    elif (update_mispredict && idx_match):                                   │   │
    │   │        f2_entry.s_cnt = 0                                                   │   │
    │   └─────────────────────────────────────────────────────────────────────────────┘   │
    │                                                                                      │
    └───────────────────────────────────────────────┬──────────────────────────────────────┘
                                                    │ RegNext
                                                    ▼
    ┌─────────────────────────────────────────────────────────────────────────────────────┐
    │                              F3: 预测决策                                            │
    │                                                                                      │
    │   ┌─────────────────────────────────────────────────────────────────────────────┐   │
    │   │  f3_entry = RegNext(f2_entry)                                               │   │
    │   │  f3_tag = PC 高位标签                                                        │   │
    │   │  f3_scnt = s_cnt (可能被旁路更新)                                            │   │
    │   │                                                                              │   │
    │   │  io.f3_pred = io.f3_pred_in   // 默认透传                                   │   │
    │   │                                                                              │   │
    │   │  when (f3_entry.tag == f3_tag):                                             │   │
    │   │      when (f3_scnt == f3_entry.p_cnt && f3_entry.conf == 7):                │   │
    │   │          io.f3_pred = !io.f3_pred_in   // 翻转预测!                          │   │
    │   │                                                                              │   │
    │   │  io.f3_meta.s_cnt = f3_scnt   // 保存用于恢复                                │   │
    │   └─────────────────────────────────────────────────────────────────────────────┘   │
    │                                                                                      │
    └───────────────────────────────────────────────┬──────────────────────────────────────┘
                                                    │ RegNext
                                                    ▼
    ┌─────────────────────────────────────────────────────────────────────────────────────┐
    │                              F4: 推测更新                                            │
    │                                                                                      │
    │   ┌─────────────────────────────────────────────────────────────────────────────┐   │
    │   │  when (f4_fire && f4_entry.tag == f4_tag):                                  │   │
    │   │                                                                              │   │
    │   │      when (f4_scnt == f4_entry.p_cnt && f4_entry.conf == 7):                │   │
    │   │          // 循环结束                                                         │   │
    │   │          entries(f4_idx).s_cnt = 0                                          │   │
    │   │          entries(f4_idx).age = 7                                            │   │
    │   │                                                                              │   │
    │   │      otherwise:                                                             │   │
    │   │          // 循环继续                                                         │   │
    │   │          entries(f4_idx).s_cnt = f4_scnt + 1                                │   │
    │   │          entries(f4_idx).age = min(f4_entry.age + 1, 7)                     │   │
    │   └─────────────────────────────────────────────────────────────────────────────┘   │
    │                                                                                      │
    └──────────────────────────────────────────────────────────────────────────────────────┘

                              ┌─────────────────┐
                              │  更新路径        │
                              │  s1_update      │
                              └────────┬────────┘
                                       │
    ┌──────────────────────────────────┴───────────────────────────────────────────────────┐
    │                                                                                       │
    │   ┌────────────────────────────────┐      ┌────────────────────────────────┐         │
    │   │     update_mispredict          │      │       update_repair            │         │
    │   │     (误预测更新)                │      │       (修复更新)               │         │
    │   └───────────────┬────────────────┘      └───────────────┬────────────────┘         │
    │                   │                                       │                          │
    │                   ▼                                       ▼                          │
    │   ┌────────────────────────────────────────────────────────────────────────────┐    │
    │   │                                                                             │    │
    │   │  误预测: 根据 conf, tag_match, ctr_match 执行状态机                         │    │
    │   │          更新 conf, age, p_cnt, s_cnt, tag                                 │    │
    │   │                                                                             │    │
    │   │  修复: 仅恢复 s_cnt = update_meta.s_cnt                                     │    │
    │   │        (如果 tag_match 且无 F4 冲突)                                        │    │
    │   │                                                                             │    │
    │   └────────────────────────────────────────────────────────────────────────────┘    │
    │                                                                                       │
    └───────────────────────────────────────────────────────────────────────────────────────┘

12. Loop Predictor 与其他预测器的协作

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

┌─────────────────────────────────────────────────────────────────────────────────┐
│                    Loop Predictor 在预测器层次中的位置                           │
└─────────────────────────────────────────────────────────────────────────────────┘

                              ┌─────────────────┐
                              │    取指 PC       │
                              └────────┬────────┘
                                       │
                    ┌──────────────────┴──────────────────┐
                    │                                     │
                    ▼                                     ▼
            ┌───────────────┐                     ┌───────────────┐
            │     BTB       │                     │   BIM/TAGE    │
            │ (��标地址)    │                     │ (方向预测)    │
            └───────┬───────┘                     └───────┬───────┘
                    │                                     │
                    │                                     ▼
                    │                             ┌───────────────┐
                    │                             │    Loop       │
                    │                             │  Predictor    │
                    │                             │ (循环覆盖)    │
                    │                             └───────┬───────┘
                    │                                     │
                    │                                     │
                    └──────────────────┬──────────────────┘
                                       │
                                       ▼
                              ┌───────────────────┐
                              │   最终预测结果     │
                              │                   │
                              │ target = BTB      │
                              │ taken = Loop或BIM │
                              └───────────────────┘

数据流:

    io.resp_in(0)          io.resp
         │                    │
         │  ┌─────────────┐   │
         └─►│    Loop     │───┘
            │  Predictor  │
            └─────────────┘

    Loop 接收基础预测 (f3_pred_in)
    条件满足时翻转输出 (f3_pred)
    否则透传基础预测

优势:

  • BIM/TAGE 善于预测通用分支模式
  • Loop Predictor 专门处理循环退出
  • 两者互补，提高整体预测精度

13. 关键参数总结

参数 默认值 说明
nSets 16 每列条目数
tagSz 10 标签位宽
nWays 4 (参数中定义但未使用)
threshold 7 (参数中定义但未使用)
LoopEntry 字段 位宽 说明
tag 10 地址标签
conf 3 置信度 (0-7)
age 3 年龄计数器 (0-7)
p_cnt 10 预测循环次数 (0-1023)
s_cnt 10 当前迭代次数 (0-1023)

14. 设计特点总结

1
2
3
4

┌─────────────────────────────────────────────────────────────────────────────────┐
│                         Loop Predictor 设计特点                                  │
└─────────────────────────────────────────────────────────────────────────────────┘

  1. 专用性:

    • 专门针对循环分支设计
    • 不试图预测所有分支，只处理学习到的稳定循环

  2. 保守性:

    • 只有 conf=7 时才覆盖基础预测
    • 需要多次正确观察才能建立置信度
    • 减少错误覆盖导致的性能损失

  3. 推测执行支持:

    • s_cnt 在预测使用后推测更新 (F4)
    • 支持 repair 恢复误预测路径上的状态
    • 旁路机制确保最新数据可见

  4. 老化与替换:

    • age 计数器防止有用条目被快速替换
    • 高置信度条目 (conf=7) 受到保护
    • 未活跃条目逐渐老化可被替换

  5. 资源效率:

    • 使用寄存器而非 SRAM (小规模 16 条目)
    • 每个 bank 独立的 Column，避免冲突
    • 简单的标签匹配，无复杂的多路选择

Loop Predictor 是一种专用预测器，专门用于处理循环分支的退出预测问题。它通过学习循环的精确迭代次数，在循环即将结束时覆盖基础预测器的预测，从而显著提高循环密集型代码的分支预测精度。

Computer Architecture
#branch prediction #RISC-V BOOM #loop predictor
RISC-V BOOM 分支预测器：Loop Predictor 机制
http://blog.luliang.online/2025/12/02/riscv-boom-loop-predictor/
作者
Luyoung
发布于
2025年12月2日
许可协议