Cache Hit / Cache Miss#

1. cache hit（命中）

   • 处理器要的数据已经在 cache 中；
   • 这时直接从 cache 返回，处理器几乎感觉不到“下面还有主存”这件事。

2. cache miss（失效）

   • 处理器要的数据不在 cache 中；
   • 这时就必须继续访问下层存储，把数据取回来。

对处理器来说，hit 和 miss 的差别非常大：

• hit 时，控制逻辑很简单；
• miss 时，不仅要访问下层 memory，还可能要 replacement、write-back，甚至让整个处理器 stall。

Block / Line#

cache 和 memory 之间传输数据时，基本单位不是单个 word，而是：

• block（块）
• 也常叫 cache line（缓存行）

它表示的是：

一组固定大小的数据，其中包含了当前请求的那个 word。

NOTE

为什么不只搬一个 word？

• 空间局部性说明：既然访问了这个地址，附近地址的数据很可能也快要用了；
• 所以一次 miss 时顺手把整个 block 一起搬上来，通常更划算。

对应而生的参数：

• byte offset 决定 block 内具体取哪个字节；
• index 决定这个 block 去 cache 的哪一行/哪一组；
• tag 决定当前这行里放的是不是我要的那个 block。

Direct Mapped#

direct mapped cache（直接映射） :

一个 memory block 只能去 cache 里的一个固定位置。

优点：

• 实现最简单；
• 查找快；
• hit time 往往较小。

缺点：

• 灵活性最差；
• 很容易出现 conflict miss。

Fully Associative#

fully associative cache（全相联） : 一个 memory block 可以放到 cache 中任意位置。

优点：

• 放置最灵活；
• conflict miss 最少。

缺点：

• 查找最贵；
• 需要比较所有 tag；
• 硬件开销大。

Set Associative#

set associative cache（组相联） 处于两者之间。

如果是 n-way set associative，表示：

• cache 被分成若干 set（组）；
• 每个 set 里有 n 个 block；
• 一个 memory block 先确定自己属于哪一组；
• 进入该组后，再从这组里的 n 个位置中挑一个。

三者其实可以都看作 Set Associative：

• direct mapped = 1-way set associative
• fully associative = 整个 cache 只有一组

TIP

• associativity 不是越大越好；
• associativity 越高，冲突越少，但查找和 replacement 逻辑也越复杂；
• 实际系统里，很多 cache 的 associativity 常见是 n ≤ 4。

NOTE

why index with the middle bits。

核心原因是：

• 低位已经被 block offset 占掉，不能再用来选 set；
• 如果直接拿高位做 index，那么很多连续地址会扎堆映射到同一个 set；
• 这会破坏空间局部性本来带来的好处。

所以更常见的做法是：

• 保留最低位给 offset
• 用中间若干位做 index
• 把更高位留给 tag

这样连续地址更容易分散到相邻 set，局部性利用会更自然。

Example#

设：

• $M$：Cache 总块数
• $n$：每组中的块数，即相联度（associativity）
• $G$：组数（number of sets）

则有：

• 全相联（full-associative）

  • $n = M$
  • $G = 1$
  • 整个 Cache 只有一组，主存块可放入任意 Cache 块中

• 直接映射（direct mapped）

  • $n = 1$
  • $G = M$
  • 每组只有一个块，主存块只能映射到唯一位置

• 组相联（set-associative）

  • $1 < n < M$
  • $1 < G < M$
  • 主存块先映射到某一组，再放入该组内任意一个块中

相联度 $n$ 越大，优点：

• Cache 空间利用更充分
• 块冲突（block collision） 更少
• 冲突失效（conflict miss） 降低
• 整体 miss rate 往往下降

缺点：

• 命中判断更复杂，需要比较更多 tag
• 硬件成本更高
• 功耗增加
• 命中时间（hit time）可能变长
• 替换策略（如 LRU）实现更复杂

实际设计中，大多数 Cache 的相联度不会太高，常见为：

即通常采用 2-way 或 4-way set-associative cache。

查找方式#

Direct Mapped#

• index 选中唯一一行；
• 看这一行的 valid；
• 再把请求地址的 tag 和该行的 tag 比较；
• 相等则 hit，否则 miss。

特点：

• 查找路径最短；
• 但如果别的 block 映射到同一行，就一定会冲突。

Fully Associative#

Assume cache has 4 blocks

fully associative 最灵活，也最贵：

• 没有传统意义上的 index；
• 访问时必须对所有行的 tag 做比较；
• 任意一行匹配就算 hit。

因此它通常只在规模较小、对灵活性要求很高的结构里更适合。

Set Associative#

• Assume cache has 4 blocks and each block is 1 word
• 2 blocks per set, hence 2 sets per cache

• index 先选中一组；
• 组内每一行都要看 valid，并比较 tag；
• 只要组内某一行匹配，就 hit。

因此它比 direct mapped 多出来的，是：

• 组内并行比较多个 tag；
• 以及 miss 时还得在组内决定替换谁。

FSM Control Simple Cache#

Cache 的行为是一个时序过程。
一次访存请求到来后，控制器可能需要依次完成：

• 接收 CPU 请求
• 比较 Tag
• 判断命中 / 失效
• 判断被替换块是否为脏块（dirty）
• 若脏，则先写回主存（write-back）
• 再从主存读入新块（allocate）
• 最后通知 CPU Cache 已准备好

Cache Controller 适合建模成一个 有限状态机。

FSM#

一个有限状态机通常包括三部分：

• 当前状态（current state）
• 输入（inputs）
• 输出（outputs）

并由两类逻辑决定行为：

1. 下一状态函数 根据：当前状态、当前输入，决定：下一拍进入哪个状态
2. 输出函数 根据：当前状态、有时还包括输入，产生：对数据通路（datapath）的控制信号
   例如：是否读主存、是否写主存、是否更新 valid/tag/dirty、是否通知 CPU ready 等。

State Machine#

Cache 容量计算#

• 地址长度：$A$ bits
  （例如 64 位地址时，$A=64$）
• Cache 数据区共有 $L$ 个 cache line（或 block）
• 每个 block 大小为 $2^m$ words
• 每个 word = 4 bytes = 32 bits
• 相联度（associativity）为 $k$
  • direct-mapped：$k=1$
  • $k$-way set-associative：$1<k<L$
  • full-associative：$k=L$
• 组数为 $S$

则有：

Example#

替换策略#

常见的替换策略有：Random / FIFO / LRU / OPT

LRU#

LRU（Least Recently Used，最近最少使用） 是最经典也最符合 locality 直觉的策略之一：

• 认为最近刚访问过的 block，更可能很快又被访问；
• 因此优先淘汰最久没被访问过的 block。

既然无法预测未来，那就让已经发生的访问历史来帮助猜测未来。

优点：

• 和 temporal locality 很契合；
• 通常表现优于纯随机和 FIFO。

缺点：

• 需要额外记录访问顺序；
• associativity 一大，硬件代价就会上升得很快。

Example#

2, 3, 2, 1, 5, 2, 4, 5, 3, 4

• cache block 数量：3
• 访问序列：

1
2, 3, 2, 1, 5, 2, 4, 5, 3, 4

hit 次数：

• replacement policy 确实会直接影响 hit rate；
• 而 hit rate 的变化，最终又会传导到 miss rate 和 AMAT。

Thrashing and Belady Anomaly#

Thrashing#

如果工作集比 cache 能承受的更大，并且访问序列不断在几组数据之间来回切换，就会出现 thrashing（抖动）。

典型序列：

1
1, 2, 3, 4, 1, 2, 3, 4

当 cache 太小、映射又不友好时：

• 刚装进来的数据很快又被挤掉；
• hit 非常少；
• 系统大部分时间都花在 miss 和 replacement 上。

thrashing 的本质就是：

• 工作集大于有效 cache 容量
• 映射冲突太严重

Comparison Pair#

如果想精确实现 LRU，可以使用 comparison pair method（成对比较法）。

基本思想是：

• 对组内每两个 block 记录谁比谁更新近；
• 然后用这些 pairwise 状态推导出谁是最久未使用者。

例如 3 个 block A, B, C 时，可以维护：

• T_AB
• T_AC
• T_BC

但这个方法的代价增长非常快。 $C_p^2$

• 3 个 block：需要 3 个 flip-flop
• 4 个 block：需要 6 个 flip-flop
• 8 个 block：需要 28 个 flip-flop
• 64 个 block：需要 2016 个 flip-flop

所以：

• 精确 LRU 在 associativity 较高时硬件代价非常大
• 这也是为什么实际处理器里经常用 pseudo-LRU（近似 LRU），而不是严格 LRU

Write Hit#

Write-Through vs Write-Back

Write Miss#

Write Allocate vs No-Write-Allocate

write miss 时，策略分歧主要在：

要不要先把目标 block 装进 cache？

常见组合#

理论上 write hit 和 write miss 策略可以自由组合，但有两种最常见组合：

1. write-back + write-allocate

   • 写 miss 时先把 block 调上来；
   • 后续读写都更可能 hit；
   • 真正回 memory 等 replacement 再说。

2. write-through + no-write-allocate

   • 写 miss 时直接写 main memory；
   • 不把数据引入 cache；
   • 简单、直观，也避免无意义占用 cache。

性能优先 -> 更偏 write-back + write-allocate 一致性 / 可预测性优先 -> 更偏 write-through + no-write-allocate

Write Stall and Write Buffer#

write-through 的一个直接问题是：

• 每次写都可能要等 main memory；
• CPU 很容易被迫停下来。

这就是 write stall（写停顿）。

一种非常常见的优化是：

• write buffer（写缓冲）

它的思路是：

• CPU 先把要直写的数据放入一个小 buffer；
• 然后继续执行后续指令；
• 由 buffer 在后台慢慢把数据推到 memory。

这样可以明显减轻 write-through 的性能损失。
但它也不是万能的，因为：

• 如果短时间内写太密集；
• buffer 还是可能被写满；
• 写满后 CPU 仍然要 stall。

Example#

No-Write-Allocate vs Write-Allocate

条件：

• fully associative
• write-back
• cache 很大，不考虑 replacement
• 初始为空
• 访问序列如下：

1
1. write Mem[100]
2
2. write Mem[100]
3
3. read  Mem[200]
4
4. write Mem[200]
5
5. write Mem[100]

比较：

• no-write-allocate
• write-allocate

Case 1：No-Write-Allocate

1. write Mem[100]

   • write miss
   • 直接写 memory，不装入 cache
   • miss

2. write Mem[100]

   • cache 中仍没有这个 block
   • 还是 miss

3. read Mem[200]

   • 读 miss
   • 把 block 200 调入 cache
   • miss

4. write Mem[200]

   • 此时 block 200 已在 cache 中
   • hit

5. write Mem[100]

   • 100 对应 block 仍不在 cache 中
   • miss

因此结果是：

总计：

• 1 hit
• 4 misses

Case 2：Write-Allocate

1. write Mem[100]

   • write miss
   • 但因为采用 write allocate，要先把 100 所在 block 调到 cache
   • 再写入 cache
   • miss

2. write Mem[100]

   • 100 所在 block 已经在 cache 中
   • hit

3. read Mem[200]

   • 第一次访问 200
   • miss
   • 并把 200 所在 block 调入 cache

4. write Mem[200]

   • 200 所在 block 刚才已经调入
   • hit

5. write Mem[100]

   • 100 所在 block 也还在 cache 中
   • hit

所以结果是：

总计：

• 3 hits
• 2 misses

如果后续确实还要继续访问这个 block；那么 write allocate 往往更合适。也就是说，write allocate 的效果本质上还是靠 locality 在支撑。

Small and Simple First-Level Caches#

L1 cache 几乎每次访存都会经过，所以 L1 的 hit time 往往比它的 miss rate 更敏感。

核心思路：

• L1 不做得太大；
• associativity 不做得太高；
• 让 tag compare、data access、way select 这条关键路径尽量短。

优点：

• hit 更快；
• 往往也更省电。

代价：

• 容量小、相联度低时，可能增加 miss rate；
• 需要依赖更大的 L2 / L3 来兜底。

所以经典设计通常是：

• 小而快的 L1
• 大而慢的 L2 / L3

Way Prediction#

组相联 cache 的问题在于：
为了知道哪一 way 命中，通常要比较多个 tag，再做数据选择，这会拉长 hit time。

way prediction 的做法是：

• 先预测“这次大概率命中哪一 way”；
• 先按这个预测去访问；
• 如果预测正确，就接近 direct-mapped 的 hit path；
• 如果预测错误，再补查其他 way，付出额外延迟。

本质上它是在做这样的折中：

• 用少量预测状态
• 换取 平均 hit time 的下降

适合场景：

• 组相联 cache；
• 对 hit time 很敏感的前端 / L1。

代价：

• 预测错时会有额外 penalty；
• 数据 cache 上做 way prediction 一般比 I-cache 更麻烦，因为误判更容易影响后续流水线。

Pipelined Caches#

把一次 cache access 拆成多个 pipeline stage，例如：

• 地址/index 处理
• tag compare
• data array access
• 返回结果

这样做的好处是：

• 可以提高时钟频率；
• cache 本身吞吐更高。

但要注意：

• 带宽上升，不代表单次访问 latency 下降
• 有时 latency 反而更高了

影响：

• I-cache pipeline 更深，会放大 branch misprediction 的代价；
• D-cache pipeline 更深，会增加 load-use latency。

所以 pipelined cache 更像是在用 更长的访问流水，换 更高的频率和吞吐。

Multibanked Caches#

把一个 cache 分成多个独立 bank，让不同访问可以并行落到不同 bank：

• 若两个请求去不同 bank，可以同周期并行；
• 若两个请求撞到同一个 bank，就会出现 bank conflict。

优点：

• 提高并发访问能力；
• 对 superscalar、多发射、多 load/store 系统尤其重要。

代价：

• bank 映射和仲裁逻辑更复杂；
• 存在 bank conflict；
• 程序访问模式会直接影响收益。

所以它本质上是在做：

• 把一个大缓存拆成多个可并行的小通道

Nonblocking Caches#

传统 blocking cache 在 miss 时会卡住后续访问。
nonblocking cache 则允许：

• hit under miss：一个 miss 正在处理时，后续 hit 还能继续；
• miss under miss：甚至允许多个 miss 并行在途。

直观理解：

• miss 不再把整个 cache 前端“封死”；
• 处理器能把部分等待隐藏掉。

关键实现点：

• 要记录多个 outstanding misses；
• 常见做法是用 MSHR（Miss Status Handling Register） 跟踪每个 miss 的去向、返回数据该填到哪里、唤醒哪条 load/store。

优点：

• 显著降低 effective miss penalty；
• 对 memory-level parallelism 较高的程序很有效。

代价：

• 控制逻辑明显更复杂；
• 需要处理返回乱序、命中/失效碰撞、coherence 等问题。

Multilevel Caches#

这是最基本也最常见的方法：

• L1 miss 后先查 L2；
• L2 miss 后再查 L3；
• 最后才去 main memory。

作用：

• 把“直接掉到主存”的昂贵 miss，改成“更低一级 cache hit”的相对便宜 miss；
• 从而降低 effective miss penalty。

代价：

• hierarchy 更复杂；
• inclusive / exclusive / non-inclusive 等策略会影响设计；
• 多级之间的一致性和替换关系更复杂。

Critical Word First / Early Restart#

一次 miss 往往是按 block 为单位搬运的。
但处理器真正急需的，常常只是其中一个 word。

因此可以：

• Critical Word First：先取当前最需要的那个 word；
• Early Restart：只要关键 word 到了，就先让处理器继续执行，剩余部分稍后补齐。

作用：

• 不一定减少总传输量；
• 但可以减少处理器真正“卡住”的时间。

适合场景：

• block 较大；
• miss penalty 中“首字返回延迟”占比较高。

Read Miss Priority Over Write Miss#

读 miss 往往直接阻塞程序继续执行；
写请求很多时候可以先暂存在 write buffer 里。

所以常见策略是：

• 读优先于写
• 尤其是 read miss priority over write miss

这样做可以：

• 让关键路径上的 stall 更少；
• 避免写流量把读请求拖住。

Merging Write Buffers#

如果 write buffer 中有多次写，目标恰好落在同一 cache line 或相邻区域，就可以合并：

• 减少总线事务数；
• 减少下层存储压力；
• 降低写流量对读 miss 的干扰。

优点：

• 对 write-through cache 特别常见；
• 硬件代价通常不算太夸张。

代价：

• 需要检测可合并性；
• buffer 管理更复杂。

Victim Cache#

victim cache 是一个很小的、通常是 fully-associative 的缓冲区，
专门保存 刚从主 cache 被替换出去的 block。

工作方式：

• L1 hit：直接返回；
• L1 miss 且 victim cache hit：通常执行 swap，把 victim cache 中的目标块和 L1 中冲突块交换；
• L1 miss 且 victim cache miss：再访问下层存储。

它针对的核心问题是：

• conflict miss
• 且通常是 被替换后很快又重用 的那类 conflict miss

优点：

• 不把额外复杂度放到 L1 正常 hit path 上；
• 对 direct-mapped cache 很有吸引力；
• 常能以很小硬件代价显著缓解“ABAB 式冲突抖动”。

局限：

• 对 capacity miss 帮助有限；
• 对长 reuse distance、流式访问帮助也有限；
• 它不是一个“正常的额外 cache level”，而是一个 专门接住 victim line 的小旁路结构。

Larger Block Size#

block 变大以后，一次 miss 会顺带把附近更多数据带上来，因此：

• spatial locality 利用更充分；
• compulsory miss 往往下降。

但副作用也很明显：

• miss penalty 变大；
• 同样 cache 容量下，block 数变少；
• 可能加重 conflict miss / capacity miss。

所以 block size 永远是 locality 和 penalty 的折中。

Larger Cache Size#

cache 更大时，能留下更多 block，因此：

• capacity miss 一般下降。

但代价是：

• 成本和面积增加；
• 功耗上升；
• hit time 可能变长。

因此：

• L1 通常不会做得很大；
• 更大的容量往往放到 L2 / L3 / LLC。

Higher Associativity#

提高 associativity 的核心作用是：

• 把“只能放一个位置”变成“能在同组多个位置中选一个”
• 从而减少 conflict miss

优点：

• 对冲突敏感的工作负载常常有效。

代价：

• tag compare 更多；
• replacement 逻辑更复杂；
• hit time 往往更长；
• 功耗也会增加。

所以常见的理解就是：

• direct-mapped：快，但脆弱
• higher associativity：稳，但贵

Compiler Optimizations#

有些 miss 不是硬件“命不好”，而是程序访问顺序本身写得不友好。

编译器常见优化包括：

Hardware Prefetching#

核心思想：

• 在处理器真正发出 demand access 之前，
• 预测它很快会用到哪些数据，
• 然后提前取回来。

常见形式：

• next-line prefetch
• stream buffer
• stride prefetch
• 更复杂的相关性预取

优点：

• 若预取及时，可把后续 miss 变成 hit；
• 若不够及时，也能降低 miss penalty。

代价：

• 预取错会浪费带宽；
• 还可能污染 cache；
• 对功耗也可能有负面影响。

所以 prefetch 的本质是：

• 用多做一点“可能没必要的工作”
• 去换 关键时刻少等一点

Compiler-Controlled Prefetching#

这类方法由编译器显式插入 prefetch 指令：

• 在真正用到数据之前若干迭代，先发预取；
• 目标通常是让访问和计算重叠。

优点：

• 编译器更了解循环结构和访问模式；
• 对规则数组访问特别有效。

前提：

• 必须给预取留出足够“提前量”；
• cache 通常需要是 nonblocking 的，否则预取本身又会把执行卡住。

代价：

• 会增加指令数；
• 预取距离不好选；
• 程序行为稍变，效果可能就明显波动。

Using HBM to Extend the Memory Hierarchy#

HBM（High Bandwidth Memory） 是把 DRAM 堆叠起来，放得更靠近处理器/加速器的一种近存储方案。

特点：

• 总线非常宽；
• 带宽很高；
• 容量通常不如外部大容量 DRAM；
• 成本和封装要求更高。

在 hierarchy 中，HBM 常见角色是：

• 作为高带宽近内存；
• 作为比 DDR 更快但更贵的一层；
• 有时也可视作 L4 / near-memory cache。

它解决的主要矛盾是：

• 传统 DDR 容量够，但带宽不够
• HBM 带宽很强，但容量和成本受限

Using CXL to Extend the Memory Hierarchy#

CXL（Compute Express Link） 可以把外部内存设备、加速器和主机以 cache-coherent 的方式连起来。

从 memory hierarchy 视角看，它的重要价值是：

• 支持 memory expansion（内存扩展）
• 支持 memory pooling（内存池化）
• 支持 memory sharing（内存共享）
• 让部分“原本不在本机板上的内存”也能进入层次结构

可以把它理解成：

• 在本地 DDR / HBM 之下，
• 引入一层 更远、通常更慢、但更灵活、更大 的扩展内存层。

优点：

• 提升容量弹性；
• 资源利用率更高；
• 对数据中心和大规模异构系统很重要。

代价：

• 延迟通常高于本地 DRAM；
• QoS、coherence、资源管理都更复杂；
• 更适合作为“较远的一层内存”，不适合作为最靠近核心的高速层。

Using UnifiedBus to Extend the Memory Hierarchy#

这里把 UnifiedBus 理解为近年来“统一互连 / memory-semantic fabric / 资源池化总线”这一类方案。

它的目标通常是：

• 把 CPU、GPU、NPU、内存和 I/O 设备放到更统一的互连语义下；
• 让远端内存、池化内存、异构设备内存更容易被系统按层次结构使用；
• 支持更大范围的资源共享与扩展。

直观理解：

• 传统 memory hierarchy 多是在单机板内分层；
• UnifiedBus 这类方案是在 更大系统范围 上继续分层。

优点：

• 容量扩展强；
• 资源池化能力强；
• 对大规模 AI / 数据中心系统有吸引力。

代价：

• 延迟一定高于本地 cache / DRAM；
• 流控、QoS、容错、隔离、安全都更难；
• 软件栈和资源调度复杂度明显上升。