Gem5 version: v25.1.0.0

TODO List:

Berti: 可以探索，不同 workload 对 DeltaList 和 HistoryTable 的容量需求是否不同?

BOP: L1DCache 使用虚拟地址进行预测?(统计跨页预取)

组合预取器的效果?

Gem5 预取器协议

所有预取器的基类为 prefetch::Base

预取请求由 PrefetchInfo 类定义，在 Base::probeNotify() 中根据 cache 请求构建预取请求并通过 notify() 将预取请求下发到 cache

Base 会根据 useVirtualAddresses 参数决定构建的 PrefetchInfo 中预取使用的地址是虚拟地址(pkt->req->getVaddr())还是物理地址(pkt->req->getPaddr())
(useVirtualAddresses 默认 False)

一般而言，只有 L1DCache 有可能使用虚拟地址进行预取，其他 level cache 只能使用物理地址进行预取

L1DCache 使用虚拟地址预取的好处在于可以实现跨页的预取，当 workload 可能跨页时其物理地址可能并不连续，可能影响 prefetch pattern

Queued Prefetcher

继承自 Queued 的预取器实现均需要实现以下虚函数:

void notifyFill(const CacheAccessProbeArg &arg);
void calculatePrefetch(const PrefetchInfo &pfi,
                        std::vector<AddrPriority> &addresses,
                        const CacheAccessor &cache);

calculatePrefetch 是由 Queued 定义的纯虚函数，用于将计算得到的预取请求地址 push 入 addresses 的数组中，由 Queued 根据 addresses 数组中的地址生成 cache 请求并发出 (in Queued::notify())
notifyFill 是由 Base 定义的纯虚函数，用于在 cache fill 时通知预取器做出相应的动作 (hook)

BOP 预取器实现

属于 offset prefetcher

in src/mem/cache/prefetch/bop.[hh|cc]

BOP 也继承于 Queued，因此需要实现 calculatePrefetch 和 notifyFill.

参数：

scoreMax: 训练过程中 bestScore 一旦超出该限制，则视为一个训练周期结束
roundMax: 最大训练轮数，round 一旦超出该限制，则视为一个训练周期结束
badScore: bestScore 超过该阈值时，则可以发射预取请求
degree: 每次预取时预取几个 bestOffset 的步幅

硬件实现：

Recent Requests Table: rrLeft, rrRight （容量均为 p.rr_size）
Offsets List: offsetsList (容量为 p.offset_list_size)
- 其中所有的偏移量是固定的，在初始化时计算好，所有偏移量分解质因数后因数均不超过 5
Delay Queue: delayQueue （optional, 容量为 p.delay_queue_size）
训练硬件寄存器
- bestScore: 单个训练周期中训练出的最大分数
- phaseBestOffset: 单个训练周期中 bestScore 对应的 offset
- round: 单个训练周期内的训练轮数
- bestOffset: 当前训练好的 offset (每个训练周期结束更新)
- issuePrefetchRequests: 是否发送预取请求(每个训练周期结束更新，只有训练周期结束时 bestOffset 超出 badScore 阈值才会置位)

offset List 越大意味着单个训练周期越长

`BOP::calculatePrefetch`

根据请求地址计算出 tag
如果启用了 delayQueue (delayQueueEnabled): 将地址插入 delayQueue insertIntoDelayQueue()
否则将地址直接插入 rrLeft ：insertIntoRR()
学习 best offset: bestOffsetLearning()
如果此时满足发送预取请求的条件(issuePrefetchRequests): 以学习的 bestOffset 作为步幅发送 degree 次预取请求
(bestOffset 以 block size 为粒度, degree 需大于 1)

BOP::insertIntoDelayQueue

如果请求超出 delayQueueSize ，则忽略，不作任何处理
否则:

将当前预取地址插入 delayQueue, 延时设置为 process_tick = curTick() + delayTicks
如果 delayQueueEvent 未被调度，则在 process_tick 调度该事件

delayQueueEvent 被调度到时执行 BOP::delayQueueEventWrapper():

将 delayQueue 中所有 ticks 满足的 entry 都插入到 rrLeft
然后如果 delayQueue 非空，则调度下一个 delayQueueEntry 的 event

BOP::insertIntoRR

根据 way 和 tag 将 addr 插入 Recent Requests Table

索引方式为：

对于 Left Side, index = cacheline_addr ^ (cacheline_addr >> log_rr)
对于 Right Side, index = cacheline_addr ^ (cacheline_addr >> (2 * log_rr))

index 最终还需 wrap 到 RR Entries 内

BOP::bestOffsetLearning

根据当前的 offsetsListIterator 计算出 RR Table 的 lookup tag: testRR()
- 如果 RR Table Hit, 则将该 offsetsList Entry 的 Score++,
- 如果该 Entry 的 Score 超过 bestScore，则
  将 bestScore 改为当前 Entry 对应的 score, phaseBestOffset 改为当前 Entry 对应的 offset
然后将 offsetsListIterator++ 下一次调用该函数则检查下一个 RR Table Entry
- 如果 offsetsListIterator 指针指到 offsetsList 的末端, 则
  将指针再指回 offsetsList 的头部，并记录 round++
如果训练出的 bestScore 超出 scoreMax 或者训练的 round 超出 roundMax，则进入新的训练周期：
- round 归零
- 如果 bestScore 超出 badScore (使能预取的 score)，则
  将 bestOffset 设置为 phaseBestOffset, issuePrefetchRequests 置位 true
  否则：issuePrefetchRequests 置位 false
- 重置训练中间结果:
  - offsetsList 中所有 Entry 的 score 置 0: resetScores()
  - bestScore 和 phaseBestOffset 置 0

`BOP::notifyFill`

如果此时允许发送预取请求（issuePrefetchRequests）:将 (cache fill 的地址 - bestOffset) 的值插入 rrRight

Berti 预取器实现 (from xs-gem5)

属于 delta prefetcher

in src/mem/cache/prefetch/berti.[hh|cc]

Gem5 并没有 Berti 的相关实现，最原始的 Berti 只有 ChampSim 和 xs-gem5 的开源实现

BertiPrefetcher 继承于 Queued，因此需要实现 calculatePrefetch 和 notifyFill.

相比于原论文，
xs-gem5 在实现 Berti 时将 DeltaList 合并到 HistoryTable 中，二者共用 pc 作为 tag，但也意味着二者容量必须一致
（可以探索，不同 workload 对 DeltaList 和 HistoryTable 的容量需求是否不同?）

其中，HistoryTable 每个 Entry 中:

可以存储多个地址: 容量为 maxAddrListSize，采用 FIFO 替换策略
额外增加了一位 hysteresis 用于保护 entry 防止刚进入就被替换出去
（entry 第一次被替换时只会清除该位，不会做实际的替换，第二次替换才会做实际的替换）

HistoryTableEntry:
                      +------------+----------+             +---------+--------+---------+
                 +--->|   Vaddr0   |Timestamp0|          +->| covCtr0 | delta0 | status0 |
      hysteresis |    +------------+----------+          |  +---------+--------+---------+
          |      |                                       |
+--------+-+---+------------+------------+   +------------+----------+----------+   +----------+
| pc tag |h|ctr|HistoryInfo0|HistoryInfo1|...|HistoryInfox|DeltaInfo0|DeltaInfo1|...|DeltaInfoy|
+--------+-+---+------------+------------+   +------------+----------+----------+   +----------+

`BertiPrefetcher::calculatePrefetch`

将触发预取请求的地址插入 trainBlockFilter: trainBlockFilter.insert(blockIndex(pfi.getAddr()), 0);
如果触发预取请求的地址在 cache 中 hit : 以 pc 为 tag 查找 history table 如果也 hit :
- searchTimelyDeltas(): 在给定的 HistoryTableEntry 中找到及时的 deltas 并更新 DeltaList Entry
- statsBerti.trainOnHit++
更新 history table: updateHistoryTable(pfi);
如果 history table 中有 entry 训练完毕
- 如果定义采用激进的预取方式(aggressivePF)：将 entry->deltas 中所有非 NO_PREF 状态的 delta 候选项都发送一次预取请求
- 否则，只针对 bestDelta 进行预取

预取请求的发送通过 sendPFWithFilter() 将预取请求的地址填入 addresses 数组

预取地址的计算还会根据 useByteAddr 的设置来确定 delta 是按字节的 delta 预取还是按 cacheblk 的 delta 预取

1 2	Addr pf_addr = useByteAddr ? pfi.getAddr() + delta : (blockIndex(pfi.getAddr()) + delta) << lBlkSize;

`searchTimelyDeltas()` 在给定的 HistoryTableEntry 中找到及时的 deltas 并更新 DeltaList Entry

确定 delta 的最小绝对值：delta_thres: UseByteAddr ? lBlkSize : 8

遍历当前 HistoryTableEntry 的所有 HistoryInfo
- 计算出触发预取地址到 HistoryInfo Vaddr 的 delta ，如果 delta 低于最小阈值则忽略当前 HistoryInfo
- 计算当前 HistoryInfo 的预取请求是否已满足预取延时
  不满足意味着 HistoryInfo 如果触发过预取请求，此时也不可能完成，因此也忽略该 HistoryInfo
- 将所有未忽略的 deltas 加入 new_deltas list （超过 maxDeltafound 的 delta 也忽略）
该 HistoryTableEntry 的 counter++
遍历 new_deltas 中的所有 delta
- 检查是否和当前 pc 对应的 DeltaList Entry 中的 delta 有对应 (coverageCounter 要求非 0):
- 如果有对应：对应 delta 的 coverageCounter++
- 如果没有对应: 找到 DeltaList Entry 中 coverageCounter 最小的 delta 替换:
  替换初始值：coverageCounter = 1; status = NO_PREF
检查该 HistoryTableEntry 的 counter:
- 如果大于 6 (代表训练延时): 更新 Status entry.updateStatus()
  - coverageCounter < 2: status -> NO_PREF
  - 2 <= coverageCounter < 4: status -> L2_PREF
  - coverageCounter > 4: status -> L1_PREF
  - 同时确定 bestDelta : coverageCounter 最大的 delta
- 如果大于 16: 重置 DeltaList coverageCounter 但保留 status: entry.resetConfidence(false);

`updateHistoryTable()`

确定训练地址：useByteAddr ? pfi.getAddr() : blockIndex(pfi.getAddr())

lookup HistoryTable:

Hit
- 更新 HistoryTableEntry 替换策略的元数据: historyTable.accessEntry(entry);
- lookup HistoryInfo : 是否有地址和训练地址匹配
  - Hit：忽略此次更新
  - Miss：将训练地址 push 进 HistoryInfo FIFO
    如果 FIFO 已满(最大 maxAddrListSize)：替换第一个 entry 并置位当前 entry 的 hysteresis
Miss
- 如果 entry 的 hysteresis 有置位，清除 hysteresis 位不做任何替换
- 如果 entry 的 hysteresis 未置位
  - 如果当前 entry 可以进行预取 (entry->bestDelta.status != NO_PREF):
    将当前 entry 的 bestDelta 记入 evictedDeltas
  - 根据 HistoryTable 的替换策略将训练地址和预取来源 pc 等信息写入到 HistoryTable 中

注：只有 HistoryTable Hit 才会返回相应的 HistoryTableEntry ，否则返回 nullptr

`sendPFWithFilter()` 经过 filter 之后发送预取请求

如果预取地址在 filter 中，则不发送此次预取请求（仍在训练中）
否则：
- 更新 topDeltas: topDeltas[blk_delta] = topDeltas.count(blk_delta) ? topDeltas[blk_delta] + 1 : 1;
- 将该预取地址插入 filter: filter->insert(addr, 0);
- 将预取地址插入 addresses 数组：addresses.push_back(AddrPriority(addr, prio));

此处 clone 的 xs-gem5 最新分支 commit 为 11a1b6f013bdf3fdc34e7dc45fbbb1755605eb63 ，其中 filter 和其他预取器共用 sendPFFilter，此处可以单独实现

可以评估组合预取器的效果?

`BertiPrefetcher::notifyFill`

对于指令预取请求，没有 Vaddr 或 PC 的请求，不作任何处理，直接返回
对于预取请求引发的 refill ，不做任何处理，直接返回
在 HistoryTable 中查找是否有该 fill 请求对应的 entry: 没有则不做任何处理，直接返回
searchTimelyDeltas 在给定的 HistoryTableEntry 中找到及时的 deltas 并更新 DeltaList Entry

Gem5 预取器协议

Queued Prefetcher

BOP 预取器实现

BOP::calculatePrefetch

BOP::insertIntoDelayQueue

BOP::insertIntoRR

BOP::bestOffsetLearning

BOP::notifyFill

Berti 预取器实现 (from xs-gem5)

BertiPrefetcher::calculatePrefetch

searchTimelyDeltas() 在给定的 HistoryTableEntry 中找到及时的 deltas 并更新 DeltaList Entry

updateHistoryTable()

sendPFWithFilter() 经过 filter 之后发送预取请求

BertiPrefetcher::notifyFill