缓存理解要点

概念部分

1. 什么是组相连、全相连、直接相连

2. 组相连中 Way、Set、Offset 的含义

3. 缓存为什么以 CacheBlock (Cacheline) 为单位进行管理，L1/L2/L3 是否能用不同 Size 的 CacheBlock

4. 维护 Cache Coherence 的两种策略： Directory、Snoop

5. 非阻塞的缓存一定中“非阻塞”的含义，它一直是非阻塞的嘛？

6. 缓存包含关系 Inclusive、Non-inclusive、Exclusive 的含义（与各自优势）

7. 预取算法、替换算法在缓存中发挥哪些作用？

总线部分

（括号中为可参考的手册页数，手册版本为 TileLink SPEC 1.8.1）

1. ABCDE 各条通道的方向与优先级，它们分别用来传递什么信息

A通道和D通道是两个基本通道。

A通道：从master到slave，发送对指定地址范围进行操作的请求，访问或缓存数据。
D通道：从slave到master，向原始请求者发送数据响应或确认消息。

TL-C通道引入了B、C、E三个通道。

B通道：从slave到master，发送请求，请求在一个被master缓存的地址上执行操作，访问或回写缓存的数据。
C通道：从master到slave，发送数据或确认信息以响应请求。
E通道：从master到slave，从原始请求者发送缓存块传输的最终确认，用于序列化。

消息跨通道的优先级依次为A < B < C < D < E。

2. 各个总线 Opcode 的语义

TileLink op

3. 缓存块的状态有几种，它们是怎么发生状态转移的（P61-P64）

Nothing：没有缓存数据副本，没有读写权限。
Trunk：在Tip和Root之间的路径上拥有缓存副本的节点。此副本的数据可能不是最新的，因此不具有其副本的读写权限。
Tip：包含最新的数据。
- Tip with no Branches：具有读写权限。可能有脏数据。
- Tip with Branches：由于上面还有branch，所以只有读权限。可能有脏数据。如果想要写权限，就要把上面的branch清掉。
Branch：在Tip结点之上，具有只读的副本，不具有脏数据。

Coherence tree

4. 为什么请求之间会有“打断”的问题

保证数据的正确性，且避免死锁。

Probe 打断 Acquire 的重要性（P69）

当Slave收到ProbeAck之后才能向主端发送Grant。

Probe and Acquire

主代理A先发送Acquire，但由于网络延迟，后到达从代理。
主代理B后发送Acquire，但先到达从代理，被序列化在A的前面。
从代理向A发送Probe，Slave的Grant必须包含最新数据，所以Probe的优先级要高于Acquire。即使A还在等待Grant，A也必须先处理Probe，以避免死锁。
从代理接收到A的ProbeAck后，向B发送Grant。
从代理接收到A的Acquire，但由于正等待B的GrantAck，所以现在还不能处理这个请求。
一旦接收到B的GrantAck，A的事务就可以正常处理了。
从代理向B发送Probe，但这个操作被在上一个Grant之后。
从代理向A发送合适类型的Grant(包括数据副本)，说明A在Acquire后被Probe过。

Release 请求打断 Probe 的重要性（P69）

如果Master在一个块上有一个未完成的Release事务，它就不能用ProbeAcks响应此块上传入的探测请求，直到它从Slave收到一个ReleaseAck，确认回写完成。

Probe and Acquire

主代理A向从代理发送Acquire。
与此同时，主代理B通过Release主动剔除相同的数据缓存块。
从代理向B发送Probe。
从代理等待每个发送出的Probe，但可以处理主动发起的Release。从代理发送ReleaseAck确认主动写回的操作完成。
B在接收到写回确认前不处理Probe。
在从代理接收到B的ProbeAck后，A的事务就可以正常执行了。

6. 为什么 Grant 和 Release 后续都需要分别跟一个 GrantAck 和 ReleaseAck（P69）

假设将消息点到点、有序地传递到特定的代理，那么Slave只需将Grant消息发送到原始的Master就足够了。 Slave可以处理块上的后续事务。对同一Master的后续Probe和Grant将按顺序到达。由于不能保证这种排序，因此我们转而依赖GrantAck消息来允许从Slave序列化这两个事务。

ReleaseAck同理。

CPL2 部分

参考代码为 CPL2 的 master 分支 https://github.com/OpenXiangShan/CoupledL2

1. 缓存总体框架

顶层模块：src/main/scala/coupledL2/CoupledL2.scala。其中例化了Prefetcher、Slice、Arbiter，以及TopDownMonitor。

Prefetcher，用于预取
Slice，把缓存分成若干个Slice，可以提升并行性
Arbiter，此处是l1Hint_arb
TopDownMonitor，用于性能监控

其中Slice是最重要的模块。每个Slice中包含了RequestArb、MainPipe、SinkA-C、SourceC、DataStorage、Directory、RequestBuffer、MSHRCtl、MSHRBuffer等模块。

MSHR，即 Miss Status Holding Registers
Directory，存储tag以及其他元数据
DataStorage，一块SRAM，用于存储缓存的数据
RequestArb，详见3
MainPipe，详见3
GrantBuffer，详见7
RefillBuffer，详见8
ReleaseBuffer，详见8

2. 请求的处理流程

收到 L1 Acquire，且命中

L1 由 A 通道向 L2 发送 Acquire。sinkA接收请求，转换为 Cache 内部请求TaskBundle，发送给RequestBuffer。
经过RequestBuffer的缓冲，请求传入RequestArb，由RequestArb进行仲裁。
这个请求在某个周期被RequestArb选中。RequestArb在s1读取Directory，目录的查询结果在 s3 返回给MainPipe，结果为命中。
MainPipe执行实际的操作。对于AcquirePerm来说，MainPipe只需修改Directory即可。若是AcquireBlock，还需要从DataStorage读取数据。
Acquire操作本身完成，接下来MainPipe要从 D 通道发送Grant，这个Grant会发送给GrantBuffer，由GrantBuffer发送给 L1。
最终 L1 由 E 通道发送GrantAck以确认，由GrantBuffer接收并且处理。

收到 L1 Acquire，且缺失，需要从 L3 获取

Directory在 s3 返回给MainPipe的结果是缺失。此时需要分配MSHR，以向 L3 发送Acquire。MainPipe向MSHRCtl发送分配请求。
执行 refill 流程。MSHRCtl由 A 通道向 L3 发送 Acquire。L3 向 L2 发送Grant，RefillUnit处理Grant，转发给MSHRCtl，写入RefillBuffer，并且向 L3 发送GrantAck。
接下来，RequestArb进行仲裁，选中MSHR中的refill请求。由MainPipe在 s3 读RefillBuffer写入DataStorage，完成 refill 流程，同时向 L1 发送Grant。后续流程与命中的情况类似。

b 的基础上 + 需要替换

还需要在 C 通道发送一个Release请求。RequestArb仲裁时选择MSHR发出的Release请求，发送给MainPipe。
MainPipe在 s3 从 SourceC 发送 Release。

收到 L3 Probe，且需要去 Probe L1

L3 由 B 通道向 L2 发送Probe。sinkB接收请求，转换为 Cache 内部请求TaskBundle，发送给RequestArb，等待RequestArb仲裁。
这个Probe请求在某个时钟周期被RequestArb选中，在 s1 读Directory。读取结果在 s3 返回给MainPipe。根据读Directory的结果，MainPipe需要去Probe L1。此时分配MSHR。
MSHRCtl通过 B 通道向 L1 发送Probe。L1 通过 C 通道回复的ProbeAck被sinkC接收。
MainPipe在 s3 可能还要写Directory。

3. ReqArb / MainPipe 包含几个流水级，分别完成什么任务

RequestArb对来自MSHR、sinkA（RequestBuffer）、sinkB、sinkC的请求进行仲裁，分为s0、s1、s2。

s0，从MSHR接收请求。锁存一拍，传入s1。
s1，把状态发送给MainPipe，进行仲裁，优先级顺序：MSHR>sinkC>sinkB>sinkA
- 向Directory发送查询
- 向RequestBuffer发送信息
s2，向MainPipe发送信息，读RefillBuffer和ReleaseBuffer

MainPipe是主流水线，分为s2、s3、s4、s5

s2，接收RequestArb的请求，读sinkC(bufRead)
s3，从Directory、RefillBuffer、ReleaseBuffer接收查询结果，根据结果做以下事情
- 写入Directory
- 向DataStorage发送读写请求
- 向MSHRCtl请求分配MSHR
- 把 C 通道请求发给 SourceC，把 D 通道请求发给 GrantBuffer
s4，读取MSHR的分配结果，把 C 通道请求发给 SourceC，把 D 通道请求发给 GrantBuffer
s5，从DataStorage获得数据，写RefillBuffer和ReleaseBuffer，把 C 通道请求发给 SourceC，把 D 通道请求发给 GrantBuffer

s3/s4/s5 在向 C/D 通道发送请求时，需要经过一个仲裁。

在流水线部分以外，MainPipe也接收RequestArb在 s1 的请求与状态，控制其通道阻塞。

4. Directory 目录项包含哪些内容

class MetaEntry(implicit p: Parameters) extends L2Bundle {
  val dirty = Bool()
  val state = UInt(stateBits.W)
  val clients = UInt(clientBits.W)  // valid-bit of clients
  // TODO: record specific state of clients instead of just 1-bit
  val alias = aliasBitsOpt.map(width => UInt(width.W)) // alias bits of client
  val prefetch = if (hasPrefetchBit) Some(Bool()) else None // whether block is prefetched
  val prefetchSrc = if (hasPrefetchSrc) Some(UInt(PfSource.pfSourceBits.W)) else None // prefetch source
  val accessed = Bool()

  def =/=(entry: MetaEntry): Bool = {
    this.asUInt =/= entry.asUInt
  }
}

dirty，脏位
state，分为INVALID、BRANCH、TRUNK、TIP四种
clients，clients 的有效位
alias，别名位，解决 Cache 别名问题
prefetch位，表示这个 block 是不是被预取的
prefetchSrc，预取的来源
accessed

5. 状态机的逻辑

class FSMState(implicit p: Parameters) extends L2Bundle {
  // schedule
  val s_acquire = Bool()  // acquire downwards
  val s_rprobe = Bool()   // probe upwards, caused by replace
  val s_pprobe = Bool()   // probe upwards, casued by probe
  val s_release = Bool()  // release downwards
  val s_probeack = Bool() // respond probeack downwards
  val s_refill = Bool()   // respond grant upwards
  // val s_grantack = Bool() // respond grantack downwards, moved to GrantBuf
  // val s_triggerprefetch = prefetchOpt.map(_ => Bool())

  // wait
  val w_rprobeackfirst = Bool()
  val w_rprobeacklast = Bool()
  val w_pprobeackfirst = Bool()
  val w_pprobeacklast = Bool()
  val w_pprobeack = Bool()
  val w_grantfirst = Bool()
  val w_grantlast = Bool()
  val w_grant = Bool()
  val w_releaseack = Bool()
  val w_replResp = Bool()
}

其中s_表示要调度的请求，w_表示要等待的应答。

设置逻辑

MainPipe在 s3 向MSHRCtl发送分配请求，MSHR项的状态就是alloc_state，其类型是FSMState。需要完成的事件（s_*和w_*寄存器）置为false.B，表示请求还未发送或应答还没有收到。

when(req_s3.fromA) {
  alloc_state.s_refill := false.B
  alloc_state.w_replResp := dirResult_s3.hit // need replRead when NOT dirHit
  // need Acquire downwards
  when(need_acquire_s3_a) {
    alloc_state.s_acquire := false.B
    alloc_state.w_grantfirst := false.B
    alloc_state.w_grantlast := false.B
    alloc_state.w_grant := false.B
  }
  // need Probe for alias
  // need Probe when Get hits on a TRUNK block
  when(cache_alias || need_probe_s3_a) {
    alloc_state.s_rprobe := false.B
    alloc_state.w_rprobeackfirst := false.B
    alloc_state.w_rprobeacklast := false.B
  }
  // need trigger a prefetch, send PrefetchTrain msg to Prefetcher
  // prefetchOpt.foreach {_ =>
  //   when (req_s3.fromA && req_s3.needHint.getOrElse(false.B) && (!dirResult_s3.hit || meta_s3.prefetch.get)) {
  //     alloc_state.s_triggerprefetch.foreach(_ := false.B)
  //   }
  // }
}
when(req_s3.fromB) {
  // Only consider the situation when mshr needs to be allocated
  alloc_state.s_pprobe := false.B
  alloc_state.w_pprobeackfirst := false.B
  alloc_state.w_pprobeacklast := false.B
  alloc_state.w_pprobeack := false.B
  alloc_state.s_probeack := false.B
}

控制子请求的逻辑

这部分逻辑在MSHR中。在被设为false.B的事件完成后，对应的寄存器置为true.B，当所有事件都完成后，该项MSHR就会被释放。

6. 流水线入口阻塞逻辑（ReqArb 里的 BlockA/B/C）

在RequestArb中，block_A/B/C的逻辑是类似的。

val block_A = io.fromMSHRCtl.blockA_s1 || io.fromMainPipe.blockA_s1 || io.fromGrantBuffer.blockSinkReqEntrance.blockA_s1
val block_B = io.fromMSHRCtl.blockB_s1 || io.fromMainPipe.blockB_s1 || io.fromGrantBuffer.blockSinkReqEntrance.blockB_s1
val block_C = io.fromMSHRCtl.blockC_s1 || io.fromMainPipe.blockC_s1 || io.fromGrantBuffer.blockSinkReqEntrance.blockC_s1

MSHRCtl/MainPipe/GrantBuffer都可以阻塞某一通道。

MSHRCtl若 MSHR 距离填满只差一项，则阻塞 A 通道；若 MSHR 已满，则阻塞 B 通道；不阻塞 C 通道。
MainPipe的s23Block可以检查RequestArb s1 某个通道（a/b/c/g）操作所在的 set 是否与MainPipe的 s2/s3 操作所在的 set 冲突。bBlock用于检查 B 通道的 set 冲突情况，可以选择是否比对 tag。
- 若 s2 或 s3 与 A 通道发生 set 冲突，则阻塞 A 通道。
- 若 s2 或 s3 与 B 通道发生 set 冲突，或者 s4 或 s5 发生 set 与 tag 冲突，则阻塞 B 通道。
- 若 s2 与 C 通道发生 set 冲突，则阻塞 C 通道。
GrantBuffer检查剩余空间，若剩余空间不足，也会进行反压。

另外需要注意，这三个通道的优先级顺序是sinkC>sinkB>sinkA。MSHR的优先级高于这三个通道。

7. GrantBuffer 的作用

经由 D 通道，向上层返回Grant响应
经由 E 通道，接收GrantAck
阻塞流水线入口（反压控制）

8. RefillBuffer 和 ReleaseBuffer 的作用

在CoupledL2中，RefillBuffer和ReleaseBuffer是两个MSHRBuffer。

RefillBuffer

参考香山文档。为了减少 Cache Miss的延迟，使用RefillBuffer来缓冲从下层 Cache 或 Memory 中 Refill 的数据，这样 Refill 的数据不需要先写入 SRAM 就可以直接返回给上层 Cache。

ReleaseBuffer

ReleaseBuffer缓冲需要被Release的数据。

9. 如何实现高优先级请求对低优先级请求的嵌套

例如Probe打断Acquire的情况。

10. Cache 别名问题是什么，怎么解决的

参考香山文档。 Cache 别名问题：当两个虚页映射到同一个物理页时，如果不做额外处理的话，通过 VIPT 索引 (Virtual Index Physical Tag) 后这两个虚页会位于 cache 不同的 set，导致同一个物理页在 cache 中缓存了两份，造成一致性错误。

例如，对于 128KB，8 路组相联的 ICache 来说，每路 16KB。此时 Index 和 Offset 一共有 14 位，超过了 12 位的 page offset。超出的 2 位称为别名位。

Cache Alias

具体的解决方式是由 L2 Cache 保证一个物理块在上层的一个 VIPT cache 中最多只有一种别名位。下面举一个例子说明 L2 如何解决 cache 别名问题。如下图所示，DCache 中有有一个虚地址为 0x0000 的块。虚地址 0x0000 和 0x1000 映射到了同一个物理地址，且这两个地址的别名是不一样的。此时 DCache 向 L2 Acquire了地址为 0x1000 的块，并在Acquire请求的 user 域中记录了别名 (0x1)。 L2 的MainPipe在 s3 读目录后发现请求命中，但是Acquire的别名 (0x1) 和 L2 记录的 DCache 在该物理地址的别名 (0x0) 不同。于是， L2 会发起一个Probe子请求，并在Probe的 data 域中记录要 probe 下来的别名 (0x0)；Probe子请求完成后，L2 再将这个块Grant给 DCache，并将 L2 client directory 中的别名改为 (0x1)。

具体地，在发起Probe子请求时，需要为请求分配MSHR，在 alloc_state 中设置要执行的操作/等待的事件，包含 s_rprobe，w_rprobeackfirst，w_rprobeacklast。进入MSHRCtl，分配了一个MSHR，然后通过sourceB信号组发送Probe请求，probe 的别名位在 data 域中。接下来等待ProbeAck返回。发送Grant/GrantData，再次进入主流水线。如果刚才Probe到了数据，那么从ReleaseBuffer中读数据，更新元数据中的别名位、dirty 位；如果没有Probe回来数据，那么从DataStorage读数据，更新元数据中的别名位。

Alias Solution