Gem5 version: v25.1.0.0

TODO List:

  • Berti
    • 探索不同 workload 对 DeltaList 和 HistoryTable 的容量需求是否不同? (验证论文中的分离式结构和 xs-gem5 的统一结构的优劣)
    • 探索影响 pfLate 的因素（filter entries?）

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 的预取器实现均需要实现以下虚函数:

1
2
3
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)

NextLine 预取器实现

gem5 中 Nextline 预取器为 Tagged 预取器，继承自 Queued，只有一个可配置参数是 degree 预取深度，理论上仅预取器本身而言没有任何硬件开销。
但 Queue 本身会带来 address 队列的硬件开销。

其 calculatePrefetch() 实现很简单，只需要按照 prefetch degree，依次预取 next cacheline 即可。

Stride 预取器实现

Stride 继承于 Queued，需要实现 calculatePrefetch 和 notifyFill.

Note:
gem5 实现 stride 时没有 bit 限制，使用完整的 int 类型的 32 位进行预取

硬件开销：主要为 pcTables 引用预测表

  • pcTable 数量：启用 useRequestorId 后数量为需要预取的 requestorId 数量: 如 LSU, PageWalker, DMA, gpu…, 未启用则数量为 1 ，所有请求者都共用一个 pcTable
  • Entry Size: pcTableInfo.numEntries(p.table_entries)
  • Entry Bits: Tag, lastAddr, stride, confidence

IMP (Indirect Memory Predictor) 预取器实现

IndirectMemory 继承于 Queued, 面向 L1D Cache 设计

硬件 SRAM 开销:

  • Prefetch Table (实现由 Stream Table 和 Indirect Pattern Table 两个表共享 Tag 组成）
    • 继承 AssociativeCache
    • Entry Bits:
      • PC Tag： 存储完整的 PC tag (采用 TaggedIndexingPolicy)
      • Addr: address 存储完整的 64 位访存地址
      • Stream Table Hit Counter: 由 streamCounter 实现 (位宽由 streamCounterThreshold 决定)
      • Enable: 由 enabled 实现 (1 bit)，指示 Indirect Table 部分使能
      • index: 由 index 实现 (实现为理想的 64 bits counter)
      • Base Addr: 预测使用的基地址 (存储完整的 64 位)
      • Shift: 取值限定于 shiftValues(默认 [2, 3, 4, -3])，因此默认需要 3 bits
      • Indirect Table Hit Counter: 由 indirectCounter 实现(饱和计数器，位宽由 num_indirect_counter_bits 定义)
  • Indirect Pattern Detector
    • 继承 AssociativeCache
    • Entry Bits:
      • idx1: 第一次记录的索引值（64-bit）
      • idx2: 第二次记录的索引值（64-bit）
      • idx2 的 valid 位 (1-bit secondIndexSet)
      • base address array: 由 baseAddr 二维 vector 实现，大小为 shiftValues 的数量 * p.addr_array_len, 每个元素存储一个完整的 64 位基地址
      • 还需要有一个标识位指示 base address array 中哪些 address 记录有效(硬件上 p.addr_array_len 位的独热码更合理)

Indirect Memory Prefetcher

SPP (Signature Path Prefetcher) 实现

IndirectMemory 继承于 Queued, 面向 L2 Cache 设计

硬件 SRAM 开销:

  • Signature Table: (signatureTable)
    • 继承 AssociativeCache
    • Entry Bits:
      • PC Tag: 存储完整的 PC tag (采用 TaggedIndexingPolicy)
      • Last Offset: (实现为 SignatureEntry::lastBlock，仅记录页内上一次访问的 cacheline 地址)
      • Signature (SignatureEntry::signature): 位宽由 signatureBits 决定
  • Pattern Table (patternTable)
    • 继承 AssociativeCache
    • Entry Bits:
      • Signature Tag: 存储完整的 Signature 作为 tag (采用 TaggedIndexingPolicy)
      • Delta Array: 由 PatternEntry::strideEntries 实现（大小为 stridesPerPatternEntry）
        • Delta Value (PatternStrideEntry::stride): 仅记录页内上一次访问的 cacheline 地址
        • Delta Confidence (PatternStrideEntry::counter): 饱和计数器，位宽由 p.num_counter_bits 决定
      • Signature Confidence (PatternEntry::counter): 饱和计数器，位宽由 p.num_counter_bits 决定

SPP-V2 (Signature Path Prefetcher V2) 实现

相比于 SPP，SPP-V2 增加了 Global History Register 实现跨页预取

硬件 SRAM 开销:

  • Global History Register
    • 继承 AssociativeCache ，但实现为普通的 SRAM 表
    • Entry Bits:
      • Signature
      • Last Offset: 实现为 GlobalHistoryEntry::lastBlock，仅记录页内上一次访问的 cacheline 地址
      • Delta: 实现为 GlobalHistoryEntry::delta
      • Confidence: 实现为 GlobalHistoryEntry::confidence, 但实现为理想的 double 来记录置信度

AMPM 预取器实现

AMPMPrefetcher 继承自 Queued，仅负责实现 calculatePrefetch() 接口，其核心实现在其内部的成员 AccessMapPatternMatching &ampm

硬件 SRAM 开销：主要为 Access Map Table (accessMapTable)

  • 继承 AssociativeCache
  • Entry Bits: (AccessMapEntry)
    • addr tag: 存储完整的 Memory Access Addr Tag (采用 TaggedIndexingPolicy)
    • states vector: 每个 state 为 2-bit (AccessMapState 只有 4 种状态), 数量由 hotZoneSize(p.hot_zone_size) 决定: hotZoneSize / blkSize

SMS 预取器实现

Sms 继承于 Queued，需要实现 calculatePrefetch 和 notifyFill.

Entry Bits 实现：

  • FT 和 AGT 的 Tag 实现：预取触发地址(pfi.getAddr()) -> 块地址(blk_addr) -> region 地址(region_base)
  • PHT 的 Tag 实现：由访问 PC 和该 PC 的 Offset 组成
  • Offset 表示 Region 内的 Block 偏移，而 Pattern 记录 Region 内的访问位图 (gem5 使用集合 set 等效实现位图)

NOTE:
gem5 在实现 FT, AGT 和 PHT 的替换策略时采用了理想策略，硬件上不太可能实现：

  1. AGT 和 PHT 采用无限大的 LRU 队列实现(lruAGT, lruPHT)且是在整个 AGT 上实现，等价于理想 LRU 的全相联结构
  2. FT 采用无限大的 FIFO 队列实现(fifoFT)且是在整个 FT 上实现，等价于理想 FIFO 的全相联结构

此外，没有设置 prefetch degree 的限制，对 Region 内 Pattern 的所有 bits 都会发出预取请求

硬件开销：

  • Filter Table: (由 FT 实现)
    • Entry Size: Max_Contexts(p.ft_size)
    • Entry Bits: Tag, PC, Offset
  • Active Generation Table: (由 AGT 和 AGTPC 实现, 其中 AGT 存储 Pattern Bits, AGTPC 存储 PC Bits 和 Offset Bits)
    • Entry Size: Max_Contexts(p.ft_size)
    • Entry Bits: Tag, PC, Offset, Pattern
  • Pattern History Table
    • Entry Size: Max_PHTSize(p.pht_size)
    • Entry Bits: Tag, Pattern

Sms::calculatePrefetch

根据触发当前预取请求的地址计算出 offset, region_base, blk_addr

  1. Traning
    • 训练 AGT: 如果在 AGT 中找到对应的 Entry, 记录当前访问模式(加入 Pattern Bits) 并更新 LRU 元数据
    • 训练 FT:
      • 如果在 FT 中找到对应的 Entry, 将该 Entry 从 FT 移到 AGT 中 (如果 AGT 满，采用 LRU 替换策略)
      • 如果在 FT 和 AGT 中都没有找到对应的 Entry, 则将当前访问地址记录到 FT 中 (如果 FT 满，采用 FIFO 替换策略)
  2. Prediction
    • 在 PHT 中找到当前 <PC, Offset> 对应的 Pattern 之后，对 Pattern 内所有的历史访问都加入到 addresses 数组中进行预取，并清空对应的 lru 元数据

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

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

BOP::insertIntoDelayQueue

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

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

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

  1. 将 delayQueue 中所有 ticks 满足的 entry 都插入到 rrLeft
  2. 然后如果 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

  1. 根据当前的 offsetsListIterator 计算出 RR Table 的 lookup tag: testRR()
    • 如果 RR Table Hit, 则将该 offsetsList Entry 的 Score++,
    • 如果该 Entry 的 Score 超过 bestScore，则
      将 bestScore 改为当前 Entry 对应的 score, phaseBestOffset 改为当前 Entry 对应的 offset
  2. 然后将 offsetsListIterator++ 下一次调用该函数则检查下一个 RR Table Entry
    • 如果 offsetsListIterator 指针指到 offsetsList 的末端, 则
      将指针再指回 offsetsList 的头部，并记录 round++
  3. 如果训练出的 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 第一次被替换时只会清除该位，不会做实际的替换，第二次替换才会做实际的替换）
1
2
3
4
5
6
7
8
HistoryTableEntry:
                      +------------+----------+             +---------+--------+---------+
                 +--->|   Vaddr0   |Timestamp0|          +->| covCtr0 | delta0 | status0 |
      hysteresis |    +------------+----------+          |  +---------+--------+---------+
          |      |                                       |
+--------+-+---+------------+------------+   +------------+----------+----------+   +----------+
| pc tag |h|ctr|HistoryInfo0|HistoryInfo1|...|HistoryInfox|DeltaInfo0|DeltaInfo1|...|DeltaInfoy|
+--------+-+---+------------+------------+   +------------+----------+----------+   +----------+

BertiPrefetcher::calculatePrefetch

  1. 将触发预取请求的地址插入 trainBlockFilter: trainBlockFilter.insert(blockIndex(pfi.getAddr()), 0);
  2. 如果触发预取请求的地址在 cache 中 hit : 以 pc 为 tag 查找 history table 如果也 hit :
  3. 更新 history table: updateHistoryTable(pfi);
  4. 如果 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

  1. 遍历当前 HistoryTableEntry 的所有 HistoryInfo
    • 计算出触发预取地址到 HistoryInfo Vaddr 的 delta ，如果 delta 低于最小阈值则忽略当前 HistoryInfo
    • 计算当前 HistoryInfo 的预取请求是否已满足预取延时
      不满足意味着 HistoryInfo 如果触发过预取请求，此时也不可能完成，因此也忽略该 HistoryInfo
    • 将所有未忽略的 deltas 加入 new_deltas list （超过 maxDeltafound 的 delta 也忽略）
  2. 该 HistoryTableEntry 的 counter++
  3. 遍历 new_deltas 中的所有 delta
    • 检查是否和当前 pc 对应的 DeltaList Entry 中的 delta 有对应 (coverageCounter 要求非 0):
    • 如果有对应：对应 delta 的 coverageCounter++
    • 如果没有对应: 找到 DeltaList Entry 中 coverageCounter 最小的 delta 替换:
      替换初始值：coverageCounter = 1; status = NO_PREF
  4. 检查该 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

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

MultiPrefetcher 多预取器组合

所有子预取器定义于 prefetchers 成员变量中，各个预取器之间通过 Round Robin 轮转策略调度（在每次 getPacket() 时轮转）

Gem5 Prefetcher Stats 统计变量

prefetch::Base 统计变量

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
struct StatGroup : public statistics::Group
{
    StatGroup(statistics::Group *parent);
    statistics::Scalar demandMshrMisses;
    statistics::Scalar pfIssued;
    /** The number of times a HW-prefetched block is evicted w/o
      * reference. */
    statistics::Scalar pfUnused;
    /** The number of times a HW-prefetch is useful. */
    statistics::Scalar pfUseful;
    /** The number of times there is a hit on prefetch but cache block
      * is not in an usable state */
    statistics::Scalar pfUsefulButMiss;
    statistics::Formula accuracy;
    statistics::Formula coverage;

    /** The number of times a HW-prefetch hits in cache. */
    statistics::Scalar pfHitInCache;

    /** The number of times a HW-prefetch hits in a MSHR. */
    statistics::Scalar pfHitInMSHR;

    /** The number of times a HW-prefetch hits
      * in the Write Buffer (WB). */
    statistics::Scalar pfHitInWB;

    /** The number of times a HW-prefetch is late
      * (hit in cache, MSHR, WB). */
    statistics::Formula pfLate;
} prefetchStats;


accuracy = pfUseful / pfIssued;
coverage = pfUseful / (pfUseful + demandMshrMisses);
pfLate   = pfHitInCache + pfHitInMSHR + pfHitInWB;

Note: 这里的 pfLate 表示当前预取请求发送的太晚，预取请求发出时已经在 cache/mshr/write_buffer 找到了对应的 cacheline