Cache设计

什么是 Cache

Cache 是一种高速缓存，用于存储计算机处理器频繁访问的数据，以提高计算机的性能。

计算机需要从内存中读取数据，但内存的读取速度比处理器慢得多。因此，Cache 作为一个介于处理器和内存之间的高速缓存，可以存储处理器频繁访问的数据，以便更快地访问。

设计 Cache 模块

  • 8KB, 两路组相连, 1 路 4KB, Cache 行大小 16B, 共 512 行,
  • 采用 Tag 和 Data 同步访问的形式
  • VIPT
  • 伪 LRU 替换算法
  • DCache 采用写回写分配的策略
  • 采用阻塞式设计
  • 不采用关键字优先技术

索引地址

Tag Index offset
31…12 11…4 3…0

行

Tag+Valid Byte0 Byte1 … Byte14 Byte15 Dirty
20+1 8 8 … 8 8 1

路

(行号) Tag+Valid Byte0 Byte1 … Byte14 Byte15 Dirty
0 20+1 8 8 … 8 8 1
1 20+1 8 8 … 8 8 1
… … … … … … … …
510 20+1 8 8 … 8 8 1
511 20+1 8 8 … 8 8 1

Cache

(路号) (行号) Tag+Valid Bank0 Bank1 Bank2 Bank3 Dirty
0 0 20+1 32 32 32 32 1
0 1 20+1 32 32 32 32 1
0 … … … … … … …
0 510 20+1 32 32 32 32 1
0 511 20+1 32 32 32 32 1
1 0 20+1 32 32 32 32 1
1 1 20+1 32 32 32 32 1
1 … … … … … … …
1 510 20+1 32 32 32 32 1
1 511 20+1 32 32 32 32 1

Way0_TagValid,Way0_Dirty,Way0_Bank0,Way0_Bank1,Way0_Bank2,Way0_Bank3Way0\_TagValid, Way0\_Dirty, Way0\_Bank0, Way0\_Bank1, Way0\_Bank2, Way0\_Bank3

Way1_TagValid,Way1_Dirty,Way1_Bank0,Way1_Bank1,Way1_Bank2,Way1_Bank3Way1\_TagValid, Way1\_Dirty, Way1\_Bank0, Way1\_Bank1, Way1\_Bank2, Way1\_Bank3

输入地址, 根据地址的 Index 中找到行号, 然后根据 Tag 和 Valid 位判断是否命中,

  • 如果命中, 则根据 offset 找到对应的 Byte,
  • 如果没有命中, 则根据伪 LRU 替换算法找到替换的行号, 然后根据 Tag 和 Valid 位判断是否需要写回,
    • 如果需要写回, 则根据 Dirty 位判断是否需要写回到内存, 然后根据 offset 找到对应的 Byte, 最后将数据写入到 Byte 中.
    • 如果不需要写回, 则直接根据 offset 找到对应的 Byte, 最后将数据写入到 Byte 中.

读/写 Cache 的执行过程

  • 读操作:
    • 第一拍: 将请求中虚地址的 Index 传入 Cache 模块, 将两路 Cache 中对应 Index 的行都读出来. 同时, 将虚地址送往 TLB 模块, 从 TLB 模块中读出对应的物理地址, 存入寄存器中.
    • 第二拍: 从 Cache RAM 中得到 Cache 行的 Tag, 与虚地址的 Tag 进行比较:
      • 如果命中(Tag 相同并且该 Cache 行的有效位 valid 为 1). 通过 Offset 的[3:2]找到对应的 Bank, 得到需要访问的 32 位数据(边界对齐). 返回这个 32 位数据.
      • 如果不命中. 发生 Cache 缺失.
  • 写操作:
    • 第一拍: 将请求中虚地址的 Index 传入 Cache 模块, 与读请求不同的是, 此时不需要将整个行读出来, 只需要读出 Tag+Valid 位来判断 Cache 是否命中.
    • 第二拍: 从 Cache RAM 中得到 Cache 行的 Tag, 与虚地址的 Tag 进行比较:
      • 如果命中(Tag 相同并且该 Cache 行的有效位 valid 为 1)., 则生成 Index, 路号, offset, 写使能(wsel)等信号. 并且将需要写的输入传入 WriteBuffer.
      • 如果不命中. 发生 Cache 缺失.
    • 第三拍: WriteBuffer 向 Cache 发出写请求, 将 WriteBuffer 中缓存的数据写入命中的 Cache 行, 同时将 Dirty 位置 1.
  • Cache 缺失操作:
    • 记录 Cache 缺失时发生的地址, 操作类型(读/写), 以及需要写入的数据(如果是写操作的话).
    • 通过 AXI 接口模块向外发起对确实 Cache 行的访问. 地址是确实 Cache 行的起始地址, 大小是一个 Cache 行的数据.
    • 根据替换算法, 选择一个路的 Cache 行进行替换. 记录下选择了哪一路.
      • 如果该 Cache 行的 Dirty 位和 Valid 位为 1, 需要将这个 Cache 行的数据通过 AXI 总线接口模块写出.
      • 如果该 Cache 行的 Dirty 位为 0, 那么不需要写出.
    • 从 AXI 接口模块读入确实 Cache 行的数据, 生成对应信号, 将 Cache 行的 V 置 1, 将 Tag 信息置为之前保存的 Cache 缺失的地址.
      • 如果这个 Cache Miss 是写操作, 那么 Cache 行的 D 置 1, Data 信息为"store 操作待写入值覆盖总线返回数据"之后形成的新数据.
      • 否则, Cache 行的 D 置 0, Data 信息为总线返回的数据.
    • 将 Cache 行信息写入第三步中记录的那一路.

Cache 表的组织管理

  • Cache 的状态机模型
    • Look Up: 判断是否在 Cache 中, 根据命中信息选取 Data 部分的内容.
    • Hit Write: 命中的写操作会进入 Write Buffer.
    • Replace: 为了给 Refill 的数据空出位置而发起的读取一个 Cache 行的操作.
    • Refill: 将内存返回的数据填入到 Replace 空出的位置上.
Look Up Hit Write Replace Refill
Tag 读所有路 读待替换路 更新待替换路
Valid 读所有路 读待替换路 更新待替换路
Data 读所有路的全部 更新命中路的局部 读待替换路的全部 更新待替换路的全部
Dirty 更新明中路 读待替换路 更新待替换路

由于 Tag 和 Valid 所做的操作是一样的, 所以可以合并成一个状态.

x Look Up Hit Write Replace Refill
TagValid 读所有路 读待替换路 更新待替换路
Data 读所有路的全部 更新命中路的局部 读待替换路的全部 更新待替换路的全部
Dirty 更新明中路 读待替换路 更新待替换路

考虑 Data 表, 如果同时发生 Look Up 的读操作和 Hit Write 的写操作, 那么会出现冲突. 但是, Look Up 操作和 Hit Write 操作对整个 Cache 的修改都是局部的. 因此, 可以将 Data 表分成四个 Bank, 每个 Bank 在同时还是只能有一个操作. 除非 Look Up 和 Hit Write 同时发生在同一个 Bank 上, 此时还是需要阻塞 Look Up 请求.
这是现在 Cache 的样子:

Way0_TagValid,Way0_Dirty,Way0_Bank0,Way0_Bank1,Way0_Bank2,Way0_Bank3Way0\_TagValid, Way0\_Dirty, Way0\_Bank0, Way0\_Bank1, Way0\_Bank2, Way0\_Bank3

Way1_TagValid,Way1_Dirty,Way1_Bank0,Way1_Bank1,Way1_Bank2,Way1_Bank3Way1\_TagValid, Way1\_Dirty, Way1\_Bank0, Way1\_Bank1, Way1\_Bank2, Way1\_Bank3

Table Width Depth Description RAM/Regfile Num
TagValid 512 21 Tag 和 Valid 信息 RAM 2
Dirty 512 1 Dirty 信息 Regfile 1
Bank 512 32 Bank 的数据 RAM 8

Cache 模块外部的数据通路

  • Look Up & Replace & Refill
    • Request Buffer: 用于存储 Cache 模块外部的请求, 由于 Cache 模块外部的请求可能会发生冲突, 因此需要一个 Buffer 来缓存请求. 将 op, index, tag, offset, wstrb 和 wdata 信息存入 Request Buffer. Request Buffer 既维护了 Tag 比较时需要的信息, 又维护了 Miss 操作时需要的信息.
    • Tag Compare: 用于比较 Tag, 将每一路 Cache 中读出的 Tag 和 Request Buffer 寄存下来的 tag(reg_tag)进行相等比较, 生成结果.
    • Data Select: 对两路 Cache 中读出的数据进行选择, 选择的依据是 Tag Compare 的结果.
      • 如果 Miss, Load 最终结果来自 AXI 接口的返回数据. 即 Replace 操作.
    • Miss Buffer: 用于记录缺失 Cache 行时要替换的路的信息, 以及已经从 AXI 总线中返回的数据.
    • LSFR: 线性反馈移位寄存器, 用于生成伪 LRU 替换算法的控制信号.
  • Hit Write
    • Write Buffer: 用于记录写操作的信息, 以及将写操作的数据缓存起来, 等待下一拍写入 Cache.

Cache 模块内部的数据通路

状态机

  • 主状态机
    • IDEL: Cache 模块空闲状态, 等待写操作的到来.
    • LOOKUP: Cache 模块正在进行一个操作并且已经得到了查询结果.
    • MISS: Cache 模块当前处理的操作 Cache 缺失, 并且正在等待 AXI 总线的 wr_rdy 信号.
    • REPLACE: 待替换的 Cache 行已经从 Cache 中读出, 并且正在等待 AXI 总线的 wr_rdy 信号.
    • REFILL: Cache 缺失的访存请求已经发出, 准备 / 正在将缺失的 Cache 行数据写入 Cache 中.
  • WriteBuffer状态机
    • IDLE: WriteBuffer 没有待写的数据.
    • WRITE: WriteBuffer 正在将数据写入 Cache 中.

状态转换

  • 主状态机
    • IDLE -> IDLE: 无请求
    • IDLE -> LOOKUP: 有读请求
    • LOOKUP -> IDLE: Cache命中 && (无新的请求 || 有请求但和HitWrite冲突)
    • LOOKUP -> LOOKUP: Cache命中 && 有新的请求
    • LOOKUP -> MISS: Cache缺失
    • MISS -> MISS: AXI总线未返回
    • MISS -> REPLACE: AXI总线返回
    • REPLACE -> REPLACE: AXI总线未返回, 同时向AXI总线发出请求
    • REPLACE -> REFILL: AXI总线返回
    • REFILL -> REFILL: 缺失Cache行的最后一个32位数据尚未返回
    • REFILL -> IDLE: 缺失Cache行的最后一个32位数据返回