💻 CSC3060 Week 10-11 Memory Hierarchy

Project4 Cache Simulation


Week 10~11 Memory Hierarchy

记忆阶层出现的原因是主存和 CPU 的 memory wall (内存墙) 卡死了 CPU 算力。在记忆阶层中越高活动越频，每一级是下一级的缓存，CPU 寄存器处于最高级。利用 locality (局部性) 营造一种 “内存既大又快还便宜” 的假象。


随机存储寄存器 RAM

“随机”：强调存取数据所花的时间与目标数据所在 RAM 中物理位置无关。而磁盘磁带使用 SAM，必须从头读到尾才能找到特定数据 (顺序存取)，效率极低。

  • DRAM = Dynamic RAM (动态随机存储器)：1 capacitor + 1 transistor per bit。使用电容的 “满/空” 表示二进制 bit，电容会漏电，所以必须周期性刷新 (refresh)。以 2D 阵列形式储存，地址划分为行 (RAS) 和列 (CAS)，称为 “2-halves"。代表应用是主存，慢、便宜、规模大。主存是 CPU 外，临时的存储模块。电脑的文件未使用时都在磁盘里，只有使用时会缓存到主存。

  • SRAM = Static RAM (静态随机储存器)：6 or 8 transistors + 2 resistor per bit。使用 flip-flop circuit 的电阻双稳态表示二进制 bit。如果不断电数据会永远存在。代表应用是 CPU 缓存和寄存器，快、昂贵、规模小。

  • DRAM 受电容技术限制，SRAM 受半导体技术限制，两者都已逼近其发展极限。而处理器还在发展。

SRAM 以 100 倍的成本换 10 倍更快的访存。


DRAM

DRAM 像二维矩阵一样，通过 RAS（row access strobe） 先选一行，再通过 CAS（column access strobe） 选一列，数据先到 row buffer，再送出去。

d x w DRAM 是一种传统 DRAM 结构组织方式，表示总数为 d·w 的位 (bits) 被组织为 d 个超单元 (supercells)，每个超单元的大小为 w bits。w 即一次能够读取或写入的位数 (数据宽度)，常为 1B。

  • 这种主存的地址口宽度由 BIN (√w -1) (即最大地址) 的宽度决定；数据口宽度为 w。
  • 访存时，1、先输入 RAS 选行，并将对应整行复制到 row buffer；2、再用 CAS 选列，从 row buffer 复制出对应超单元进入数据线到 CPU 主控；3、最后所有数据写回行，刷新。

Memory Modules 是当代 DRAM 常用结构，比如 64 MB 记忆体含有 8 个 8Mx8 DRAMs，用同个行列的超单元拼出完整的 64 位信息。

  • DDR SDRAM (双倍数据速率同步动态随机存取存储器) 统治当代市场，其它非常规 DRAM 延迟相同，带宽可能更高。
  • NV Memory (闪存) 不属于 DRAM，在断电后不失去记忆，属于 EEPROM (电消除只读记忆体)，常见于 USB。
  • SAM 用于磁盘的长期存储。

lw：CPU 主控把地址 A 放到 memory bus；主存读这个地址，找到对应字 x；主存把 x 放到总线上；CPU 主控从总线把 x 读进寄存器。

sw：CPU 主控把地址 A 放总线上；主存准备接收数据；CPU 再把要写的数据 y 从寄存器复制到总线上；主存把 y 写进地址 A。


内存墙

CPU 效率的提升快于 DRAM 和 SSD 技术发展，之间的延迟也在变宽。在摩尔定律生效的年代 (80s~2003)，这个鸿沟以 50% 每年的速率拓宽。2003 年前是延迟差变大，之后则变为性能差变大。

内存墙两大因素：1、“Latency” 内存在物理上很远，时间鸿沟逐年变大；2、“Bandwidth” 内存/总线带宽不足。

解决思路：

最早的解决方案：Latency hiding 比如多线程 (IBM 360/91) or Latency Reduction 比如 cache (IBM 360/85)，后者更便宜，更影响后代机器。

  • Explicit (“显存”)：Local Memory：线程独享的内存资源，应对寄存器不足。

  • Implicit (“隐存”)：Cache and Memory Hierarchy：高层放少量常用数据，底层放大量程序数据——“Large, Cheap, but also Fast” 的假象。

  • 回顾：V-Extention 使用的向量寄存器 (V Regs) 可以用于 1. SIMD (单指令多数据批量操作) 实现 DLP (数据级并行)；2. 矩阵计算，比如图像处理。

寄存器与主存的关系由编译器/程序员控制；缓存到主存由硬件控制；主存到磁盘由硬件和 OS 控制；磁盘到磁带由硬件和程序员控制。


Cache Definations

“$” 谐音梗…

  • 广义上，缓存作为一种 “功能” 不仅是 L1, L2, L3 三级专用 Cache，Cache 不等价于 SRAM。

  • block / line：缓存的传输单位叫内存块或缓存行。一个 line 里通常有多个 word。cache miss 时，不是只搬一个 word，而是把整个 block 从下一级搬上来。

  • hit / miss：如果要访问的数据已经在 cache 里就是 hit 否则就 miss。相关量：

  • hit ratio = hits / accesses

  • miss ratio = 1 - hit ratio

  • miss penalty = miss 额外花的时间

  • hit time = 命中时访问 cache 的时间

Hit time « Miss penalty —— 这也是为什么即使 miss rate 只有几个百分点，也会严重拖慢性能。

回顾：缓存有效的原因——用两个局部性猜 CPU 要用什么：

  1. Temporal Locality：访问 A 后的一段时间很可能再次访问 A
  2. Spatial Locality：访问 A 后，其邻居，如 A-1、A+1 都很可能被访问

缓存设计的四大问题：

Q1. Where can a block be placed?

Q2. How is a block found?

Q3. Which block should be replaced on a miss?

Q4. What happens on a write?



Cache Design

Where can a block be placed?

Associativity：

  • set 记录了某个主存块被允许放进去的那一组 Cache line。⚠️ 通过 (block number) mod (number of set) 决定每条主存块能被映射到哪个 set 中。
  • Block number = address / block size = address » log2(block size) (这里表示二进制的移动位数)
  • way 代表每个 set 有多少 line(s)，即每个主存块映射到 Cache 有多少候选放法。

Fully associative (全相联) cache：1-set。任意内存块可以映射到 cache 的任意 line。优点：Hit 率高，冲突少；缺点：查找贵 (tag 大)，硬件复杂、慢、贵。

Direct-mapped (直接映射) cache：1-way/set，N-sets。每个内存块只能映射到唯一的 line (1-to-1 Hashmap)。优点：结构简单，查找快，成本低；缺点：容易发生 conflict miss。

⚠️ DM 不一定都比 FA 快，尤其是在搜索 (set selection) 时。FA 的 miss rate 与 replacement policy 有关，并不一定是 miss rate 最低的。


How is a block found?

  • Cache 一定比主存小，我们把主存地址拆除高位 (Tag) 和低位 (Index)，Index 位数与缓存行个数的二进制位宽相等。⚠️ 哈希冲突时不同主存块要可以辨别，所以缓存中要存 Tag。

  • 此外，还要预留一位 Valid bit，V=1 表示这行里有合法数据；V=0 表示这行目前是空的 / 正在从主存写入 / 无效 (cache flush)。

比如一个 8-block Direct-mapped Cache (1 word/block)，就有 8 sets，使用 3 位 Index。E.g. 地址为 42 的主存块的 Index = 010，Tag = 101。如果我们要访问它：

  1. 确认行，判断 hit/miss：访问第 010 行缓存，初始缓存为空所以 V=0，⚠️ compulsory miss (强制缺失)；
  2. 找 Tag，判断 hit/miss：找 Tag = 101 的块，找不到，miss；
  3. 如果 miss 从主存抄到当前 Index，设置 Tag 和 V：在 [010, 101] 写入 Mem[101010]，修改V=1；
  4. 下次再访问 42 就是 hit。
  5. ⚠️ 特殊的，如果访问 58 (111010)，因为 1 word/block 所以会发生 ⚠️ conflict miss，用 Mem[111010] 覆盖 Mem[101010]。
  • compulsory miss 代表第一次访问为空；conflict miss 代表两条内存被映射到同个缓存行，需要把前一条顶掉重写。

⚠️ 折中方案：Set Associative Caches

N-way 表示每个 set 有 N 条备选 Cachelines，也表示每行缓存能容纳 N 个主存块。

块先映射到某个 set，再在该 set 的若干 ways 中任选一格。相比 1-way 和 1-set 两种极端情况，N-way set associative cache 比前者冲突少，比后者便宜，所以更常见。

  • 因为缓存行数量是缓存大小和行宽决定的，与 associativity 无关，⚠️ 所以 #way 和 #set 之积是守恒的，所以 “N-ways” 中 N 越大，sets 数就越小。

地址拆分 Adress Subdivision

真正的缓存行含有 Data 和 Metadata (元数据) 两部分，Metadata 中除了 Valid bit 还有 Address 等等。⚠️ 16 KB 缓存不止占用 16 KB，只是实际数据有 16 KB！

实际使用中，RV32I 将主存地址拆成三部分：Address = Tag | Set selection | Byte offset。⚠️ 其中 offset 部分的意义是从块中选取具体的 Byte。set(index), tag, offset 分别决定组、块 (行)、字节。

⚠️ 计算公式 —— 设 cache size 为 C，line size 为 B，associativity 为 A (A-ways)：

  1. 行数 = C / B
  2. 组数 = (C / B) / A ——⚠️ 比如 direct-mapped 行数和组数相等
  3. ⚠️ 每行实际数据 Cache data bits = B × 8
  4. Set selection bits (index) = log2(#sets) ——⚠️ 比如 fully-associative 是 1-set 就没有 set bits；direct-mapped 的 set bits 最多。
  5. Offset bits = log2B，比如 64B line 的 offset 为 6b
  6. Tag bits = 32 - set bits - offset bits ——⚠️ 从 tag 的额外开销：direct-mapped 最省，fully associative 最贵。
  • Block size 越大，加上 DM (small associativity)，Tag bits 的需要位置越小；
  • Line size (Block size) 越大，越好的利用了 spacial locality。

为什么 associativity 越高，set bits 越少？因为在 cache 容量不变时：总 line 数固定，一个 set 里 way 越多，set 的个数就越少。

Block size trade-off

cache block (line) 更大理应有更小的 miss rate：如果每次 miss 时搬更多数据进 cache，通常会让后续访问更容易 hit。

原因：1. 更大程度上运用 spatial locality；2. 降低 tag cost (Cache 不变时 block 数量变少)

⚠️ block 越大不必越好：

  • block 少也意味着同时存储不同区块的能力下降，互相挤占空间导致 time locality 下降；
  • 过大的空间局部性导致 cache pollution，或者导致 bus 上传输消耗多个周期 (Transfer overhead)；
  • 以上 miss rate 弱点可能反而抵消优点。

两条 block 的折中/平衡技巧建议：

  1. 50K 以下的小缓存不适合大型 block，32～64 最好；50K 以上的大缓存喜欢大型 block，可以用 128~256 的 block。“小 Cache 需要平衡，大 Cache 喜欢大 block”。
  2. 虽然大 block 传输慢，但 Early restart 和 Critical-word-first 等技巧可以减少“CPU 真正等待的时间”。(先传/用最紧迫的 miss 部分，其它在后台继续传)

Hit and Miss, Read and Write

miss 分为 read / write。

Cache read

  1. Read hit (要读的在 cache 里)：CPU 继续执行
  2. Read miss (不在 cache 里) 分为两种：I-cache miss 要重新取指，D-cache miss 影响数据读写。基本方案：blocking cache (Stall pipeline 然后从下一层取 block)
  • 注意 I-cache 永远是 clean 的，当然不需要 copy back

Cache write

  1. Write hit (⚠️ 要写的地址对应的 block 在 cache 中) 方案：

    • Write-through (直写)：同时写回缓存和主存。优点：主存永远比较新，不怕 cache 出问题后丢更新；缺点：memory traffic 增大，总线和 DRAM 压力大，WB 阶段被拉长 (如果基础 CPI 为 1,10% 的指令是 100 延迟的写主存，实际 CPI 就变成 1 + 0.1×100 = 11)。

      解决方案：**write buffer **—— 把待写内容放进缓冲区，CPU 继续执行，后台 Memory Controller 写主存。WB 本质就是 FIFO queue，通常只需 4 位。

      WB 不过是缓冲问题而非解决问题：Store frequency > 1 / DRAM write cycle (CPU 产生写请求的速度可能比 DRAM 吞吐还快，导致 WB 越积越多，一旦 WB 饱和，CPU 还是得 stall)

      coalescing (将指向相邻或相同 block 的写请求合并处理) 可以一定程度上缓解 Memory Traffic-Jam。但是还是 Write-back 更受欢迎。

    • Write-back (回写)：只写缓存，当替换发生时再写回。

      需要 1-bit 的修改记录 (dirty bit)，属于 block metadata 部分：0 表示这行和主存一致，1 表示这行已经被改但主存里还是旧值。当脏行被替换，才需要写回主存。“脏行写回” 也可以用 **write buffer **—— 把待写内容放进缓冲区，Cache 先替换 block。

      ⚠️ 回写的目的是主存和缓存总有一处有所需值就行，两者可以不一致。如果另一个处理器/核同时要读同个数据，就需要 cache coherence (一致性协议)，比如 MESI。

      优点：WB 阶段的延迟低、Throughput 提升 (流水线友好)、Low Memory Traffic (多处理器友好)；

      缺点：Cache 故障有丢失数据的风险，需要 ECC (Error Correcting Code)，常为 8bits / 64 data bits。导致回写成本较大：

      一个 direct-mapped 16KB (block 宽 64B) 的 RV32 缓存有：256 lines，512b 实际数据，log264 = 6b offset，log2256 = 8b index，32 - 6 - 8 = 18b tag，1b validity，1b Dirty，512 / 64 x 8 = 64b ECC。统共 512+18+1+1+64 = 596 b/line，整个 Cache 占 152576 bits，相比 16KB (131072 bits) 大了不少。

  2. Write miss (要写的地址对应的 block 不在 cache 中) 方案：

    • Write-allocate (fetch-on-write) 天然对应 Write-back：先从下一层把 block 读进来，再写。适用于局部变量更新, 数组元素更新——现在写完之后很可能马上再读/再写它。初始开销大，但复用好；

    • No-write-allocate 对应 Write-through：默认 bypass (不把 miss block 拉进 cache)。适用于 strcpy(), memset(), memcpy(), initialization of arrays, 写 database——顺序大批量写但写完不太会马上再读。初始开销小，但复用性差。

⚠️ 现代 cache 的常用组合是 write-back + write-allocate 而不是 write-through + no-write / write-allocate。

Non-blocking read miss

Stall-on-Use (Non-blocking miss) vs Stall-on-Miss (Blocking miss)

如果不想 miss 不把 cache 完全锁死，需要 Miss Status Holding Register (MSHR) 登记 miss 的事务，每一层 cache 一个，相当于给 miss 加上缓冲。MSHR file 的每一项有：Block Address、Target Information、V (valid)。

优点：

  • 两个典型能力层级: Hit-under-miss (miss 时继续处理 hit) 和 Miss-under-miss (miss 时跟踪别的 miss)；

  • “Lockup-free caches” 支持 MLP (Memory Level Parallelism)，同时并行地等待 / 处理多个内存访问。

I-cache miss

第一步：把原始 PC (⚠️ 当前的 PC − 4) 发给 memory；

第二步：让主存 / 下一级 cache 去读整个 ⚠️ Instruction block；

第三步：把取回来的 block 写进 I-cache，Data 填入取回来的指令 block，Tag 填入地址高位，Valid bit改为有效；

第四步：重新开始取指。

预先取指 (prefetching) 是减少 I-chache miss 常用的优化 (optimization) 手段。但是程序未来会执行哪段代码并不总是容易预测。硬件 instruction prefetch 很常见，软件显式 I-cache prefetch 相对少见。


Memory Support

如何增大主存带宽以减小 miss-rate？

方案一：普通组织 (全局宽度一致)，BUS 也为 32b，传输缓慢。

方案二：加宽数据通路。理论上把 bus 变宽很好，但工程代价大——Pin limitation (集成电路不能无限制增加引脚)、Signal integrity challenge (干扰/时序偏差)、Design nightmare (死亡走线导致设计和制造方过劳死)。

⚠️ 方案三：交叉储存，不把总线和单个 memory 做得特别宽，把内存拆成多个 bank，连续地址可以分散到不同 bank 上，并行工作 (MLP)。这是最优解。

更大的 cache line (block)，prefetching，non-blocking，Write-through 这些功能都产生更大 Traffic，可能需要更大的 BUS 和主存带宽。



Cache Performance

CPU time with cache

CPU time 由两部分组成：正常执行时间 + memory stall 时间：

  1. CPU time = (Program execution cycles + memory stall cycles) × clock cycle time

  2. Actual CPI = Base CPI + I-cache stall + D-cache stall

  • Program execution cycles 包括 cache hit time；

  • Memory stall cycles 主要由 cache miss 导致，其 penalty 是导致 CPI 变大的主要因素。

    Memory stall cycles = (Memory accesses / Program instructions) × Miss rate × Miss penalty

例题

已知一段程序：I-cache miss rate = 2%, D-cache 4%；Miss penalty = 100 cycles；Base CPI (ideal cache) = 2；Load & stores 占比 36%，其实际 CPI 为？

  • IF 每次都需要访存，所以指令延迟 0.02 x 100 = 2；只有 36% 指令用 DMEM，所以数据延迟 0.36 x 0.04 x 100 = 1.44。实际 CPI 为 理论值加上 memory stall：2 + 2 + 1.44 = 5.44，被拖慢了 2.72 倍。

如果 CPI 异常高，很多时候不是算术单元慢，而是 memory stall。


AMAT

AMAT = Average Memory Access Time (平均内存访问时间)。CPI 关心整个程序：每条指令平均花多少周期，AMAT 只关心访存：每次访存平均花多少时间，单位为 cycles/access。

  • ⚠️ D-Cache AMAT = Hit time + Miss rate × Miss penalty —— 所以 AMAT 不能只看 miss rate，hit time 也会影响平均访问时间)

  • ⚠️ Overall AMAT = %instr × I-cache AMAT + %data × D-Cache AMAT (%inst 代表访问指令占总访存的比例) —— 一般 %instr > %data，但使用 V-Extention (SIMD/Vector) 处理 L&S 的程序可能 %instr < %data。


提升缓存性能

显然，根据 AMAT 的构成，我们可以通过：降低 Hit time、降低 miss rate 或者降低 miss penalty 来提升缓存性能。

1. Lower Hit Latency

CPU 去 cache 里查数据时，尽量少花时间。例如：小规模 cache、预测 way、虚拟地址缓存 / VIPT、低 associativity、布局离 CPU 近、地址翻译和 cache lookup 并行。


2. Decrease Conflict Miss

Cache Miss —— 4C’s

  1. Compulsory/cold miss：第一次访问某个行，必须要从主存搬到缓存。解决方案：Hardware prefetching 或者 Larger cache line size。
  2. Conflict/collision miss：set 大小 (associativity) 不足以支撑多个行映射到同组。
  3. Capacity miss：缓存本身的行数大小不足以支撑需要存储的内存行数。解决方案：增大缓存大小，或者 prefetching。
  4. Coherency miss：在多处理器中为了保持缓存数据一致性，由其他处理器发出的 invalidation requests 导致。⚠️ Coherency miss 是最难 remove 的，调整 cache 本身大小安排也没用。解决方案：对于 private caches，用 Snoopy 或 Directory；如果全是 shared caches，就不存在 Coherency 问题。

Conflict miss 就是 ⚠️ 相同 set bits 的主存行相邻被访问，但 ways 数不足安排进内存，只能挤掉前序记录。

方案一：Increase Cache Size

方案二：Bigger Associativity

出现大量 conflict miss 不仅仅需要考虑扩大缓存，更要考虑增大 Associativity 并重设计算法。

高 Associativity 会导致复杂的 MUX 设计、更多比较器和更长的 hit latency，但也越能减少 conflict miss。⚠️ 2-way set associative 比较平衡。而 4-way 也很常用，是 “Associativity sweet-spot”。

  • Fully associative：主存块随意放、访问时全表并行搜索——需要 1 comparator / line，灵活但是昂贵且慢。

  • N-way set associative：⚠️通过 modulo 映射到 set： set No. = (block No.) % (#sets) (放哪里由 block 序号决定)、只需在 set 中找——需要 N comparators，是灵活性和成本的折中。

  • ⚠️ associativity ↑ == #sets ↓ (缓存总行数守恒)，index bits 随之 ↓，tag bits ↑。

  • 一般来说，associativity 越高，miss rate 越低,但收益会 diminishing returns (递减)—— hit latency 和成本大幅增长。

    一个 64KB D-cache，16-word blocks，SPEC2000 的 miss 率：1-way: 10.3%、2-way: 8.6%、4-way: 8.3%、8-way: 8.1%。

方案三：DM + Victim Cache

对于 direct-mapped cache，⚠️ 所有 block 编号相差为组数的倍数的主存行都会 conflict miss；而 set-associative 通过 “给每个 set 多几个缓冲位” 来减少 conflict miss。

补丁1：⚠️ Victim cache 是一个很小的 (一般 4~8 行) fully-associative 备用 cache，加在 direct-mapped 的 L1 cache 到 L2 之间，作为缓冲区保存 “刚被 L1 conflict miss 挤出去的 cache lines”。

补丁 2：“padding” —— 比如 64 行的缓存访问相差 1024 的连续数组可以插入 Dummy：A[1024], Dummy0[8], B[1024], Dummy1[8], C[1024]，防止连续 conflict。但编译器可能发现Dummy[] 根本没被真正使用于是自动优化掉导致失效。

对比两种方案：2-way SA vs. DM+VC

  • Victim cache 特别擅长处理 “集中在少数几个地址/少数几个 set 上的、反复来回挤占” 的冲突。

    利用高 temporal locality (时间局部性)—— “刚被淘汰，很快又要用”。

  • 2-way 冲突不是集中在少数几个热点地址，而是分散在全局的不同 set 上，可以适应低时间局部性。

在通用系统 (桌面、服务器、笔记本) 里，2-way SA 更常见；DM+VC 更偏专用/嵌入式 (embedded)/成本导向等特定场景。


⚠️ Cache Block Replacement

(当一个满的 set 又来挤进来一条该如何处理 conflict miss，把谁踢出去？)

  • DM 或 DM+VC 没得选，毕竟只有 1-way/set，就把原本那条顶掉重写。所以 DM 的 replacement 是最简单的。
  • Set / Fully associative 就可以分为三种策略：Random、LRU (Least Recently Used) 或 FIFO。
    1. Random
    2. LRU：利用 temporal locality 替换 “最久没被用过” 的块。True-LRU 需要维护一个栈，但栈操作/硬件开销都很大；Approximate-LRU 适用于 2-way SA，用一个指针轮流指向各块，当访问到指针指向的块，就改指向下一块，替换时就换当前指向的块。便宜很多，但不准。
    3. FIFO：不管访问情况，只看进入缓存的顺序，依次过期。

General LRU：“记录每个缓存块的年龄”

  • 一个 4-way SA 的例子：每个块用一个 log2(4)=2 bit counter，记录 “多久没被访问” 的计数。某块被访问时把它的 counter 置 0，同 set 其他块的 counter 自增。Conflict miss 时就替换 counter 最大的块 (对于 4 块来说，最大值是 3)。

Theoretical Optimum：Belady’s Algorithm

  • 把未来最久之后才会再被访问的块换掉，从 hit rate 角度看是最优的。
  • 但是：1、不能实现因为无法精准预测未来；2、⚠️ 从 memory traffic / write-back 代价角度不一定最优 (dirty 概率高，要写回主存，BUS 压力变大)

现实中，替换谁这个问题要兼顾：hit rate、clean/dirty、memory traffic、功耗 …… 所有策略都试图逼近理论上限：Belady。

⚠️ FA LRU 的劣势：比如一个五个块的循环调用 (0, 1, 2, 3, 4, 0, 1 …)，如果用 4 行的 DM+Random，会有 60% hit；如果用 4 行的 FA+LRU，每次都恰好顶掉下个要用的块 (4 替换 0，0 替换 1,1 替换 2 …)，变成 0% hit。


3. Smaller Miss Penalty

方案一：多级缓存 (multilevel caches)

  • 符合 Memory Hierarchy：L1 直接接在 CPU 下，最小最快；L2 作为 L1 的缓存，处理其 conflict miss，相比 L1 稍慢稍大一些；部分高性能系统还有 L3 缓存，由同核多处理器共享；再往下就是主存。

  • 需要保持多层缓存信息一致，多核共享、WB、dirty 写回时会触发复杂的 coherency miss。

  • 比如两层缓存，如果 L1 miss 但 L2 hit，L1 miss 由 L2 hit 缓冲：⚠️ AMAT = L1 hit time + L1 miss rate × (L2 hit time + L2 miss rate × L2 miss penalty) —— 把一大部分原本 “要去主存” 的 L1 miss，截留在 L2 解决掉。

  • 典型命中率：L1 hit rate: 80–95%，L2: 50–80% (注意是对 L1 miss 而言)，L3: 20–40%。越往下：遇到的访问越来越“难”，所以下一级虽然更大，但面对的是更刁钻的 miss。

比较一级和两级缓存

4Ghz 的 CPU，基础 CPI=1，miss rate 为 2%，访存延迟 100ns。

  • 对于 L1 一级缓存，Penalty 为 100ns/(1/4)ns = 400 cycles，实际 CPI 为 1 + 2% x 400 = 9；

  • 现在增加一层 L2，访问延迟 5ns，miss rate 20%，L1 到 L2 的 miss rate 保持 2%。实际 CPI 就是 1 + 2% x (5/(1/4) + 0.2 x 400) = 3；

  • CPI 提升了 3 倍。

⚠️ 在两级缓存中，L1 和 L2 的设计目的不同：

  • L1 最重要是 hit 必须快，结构可以简单，容量和 Associativity 可以小一些；Spatial locality 很重要，把相邻数据一起带进来；L1 Write Hit 时，某些实现会选择 write-through 到 L2。
  • L2 最重要是降低 miss rate，尽量不要掉到主存；L2 的 hit time 没 L1 敏感；Temporal locality 更重要；L2 更大，若每次写都同步主存会导致巨大带宽压力，所以更常见 write-back 到主存。

相比一二级缓存，L2 更大，更慢，且没有分离 I/D (Unified)。一般只有 L3 是 shared (多处理器共享)。

其他方案

  1. 在上个部分的 “Block size trade-off” 中提过 Critical word first (miss 时，先把 CPU 最急需的那个 word 取回来，不等整行) 和 Early restart (只要关键字到了，CPU 就可以先继续执行，剩下的 line 后台慢慢补完)。
  2. 在上个部分提到过 “Non-blocking read miss"，用 MSHR 实现 MLP 和 miss overlap。
  3. Cache prefetching：不消灭 miss，而是让 miss 提前发生，“miss penalty hiding”。
  4. Write buffer for copy-back(WB) cache：之前已经提到过，CPU 继续执行，后台慢慢写回。
  5. Cache-aware code scheduling：compiler level “miss penalty hiding”

多处理器的缓存同步

单核里，cache 只是 CPU 和 memory 之间的加速层。但多核里会出现同一个内存地址，可能同时在多个处理器私有的 cache 里有不同版本。

Write-back 会让问题更明显；write-through 也不能自动解决，所以必须有 cache coherence protocol。

Snoopy Cache Coherence Scheme

所有处理器的 cache controller 都在 “偷听 (snoop)” global BUS 上广播的 coherence 相关的事件。

  • 如果一个处理器想写某个 line，它需要 invalidate 其他 cache 里的副本，保证只有最新版是 Valid 的。
  • 如果别的处理器要读某个 line，而当前某 cache 拥有 dirty copy 那它需要提供并分享这个资源。(cache 不只是 “消费者”，有时也会变成 “数据提供者”。)
  • Snoop scheme 的例子：SGI Challenge, SUN Enterprise, multiprocessor PCs, etc.

Cache controller 的输入来自两边 —— 不只响应本地处理器，还要响应别人通过总线广播出来的动作。

  • 来自本地 processor 的请求：本核要 R/W 或发生 miss
  • 来自总线 / snooper 的请求与响应：别的核发出的读共享 / 写独占请求、某个块被 invalidate、某个块需要提供数据

也就是 controller 可能会：更新状态、提供数据、发起 bus transaction (比如写独占)

Protocol is a distributed algorithm: cooperating state machines

  • 系统并非一个中央大脑指挥。每个 cache controller 都有一套自己的 state machine，通过总线广播互相配合维持一致性

Granularity of coherence is a cache block

  • 一致性按整个 cache line / block 来管理。

⚠️ MESI Protocol 是最经典的缓存一致性四元状态机之一。

  • M = Modified，表示该快只在本 cache 有，已修改过 (dirty)，主存旧。

  • E = Exclusive，表示该块只在本 cache 有，但没被写过所以和主存一致；写后转为 M。

  • S = Shared，该块可能在多个 cache 中都有副本，当前和主存一致；如果某核要写，通常得先 invalidate 别的副本。

  • I = Invalid，本 cache 里的这份副本被 invalidate，需要重新获取。

  • 比如 I -(读)> S -> E -(写)> M -> I。

⚠️ Snoopy cache protocol is not scalable 因为它依赖 global bus。在大系统中，上百上千个核的 coherence 事件都全体广播，BUS 带宽和 Snoop 成本会成为瓶颈。所以 snoopy 更适合：小到中等规模的共享总线系统。

Snoopy 方案可能产生很大的 snooping-BUS-traffic。


Directory Based Cache Coherency

对更大的系统，用 centralized 或 distributed directory 记录 “哪些处理器持有某个 cache line 的副本”

  • 不再靠 “全员广播”，而是维护一个 目录 (directory)；
  • 目录知道每个块当前处于什么状态以及哪些节点/cache 拥有它的副本。

当某个处理器要访问块 X 时，先访问 directory 返回这个块现在在哪些节点里有副本和状态是什么；然后 directory 定向地通知相关节点做 invalidation / sharing。

Directory 把 “公司群通知” 变成 “相关人员私聊”。

  • 优点：Scalability、Reduced traffic、Flexibility (适应不同系统 / 主存框架)。

  • 缺点：Complexity、Potential longer latency、Directory overhead (更多内存开销)


Inclusive/Exclusive Caches

用来处理 Coherency miss 的另一方法。

  • Inclusive 备份副本：L1 里有，L2 也有 (L1 是 L2 的 “子集”)；被 L1 evicted 的，L2 可以继续保留；但是 L2 evict 一个块时，要反过来通知 L1，把那份也失效 —— back invalidation。

    Inclusive 一般可以约下层缓存 line-size 越大。

  • Exclusive 分层分工：L1 有的，L2 不重复存；被 L1 evicted 的，才往 L2 放；L1 miss 但 L2 hit 时将 L2 的那一行 migrate 到 L1；都 miss 时只写到 L1。

    Exclusive 一般每层缓存 line-size 一样大。

Inclusive 的优势：更方便做多核一致性，L2 可以帮助检查和管理哪些 L1 里有这个块。所以更适合多核系统中做 cache coherence / invalidation 管理。

Exclusive 的优势：容量利用率更高，Inclusive Cache 的 L2 有 25% 的空间在 “重复存 L1 的东西”。

工程上，很多现代处理器更愿意牺牲一点容量效率，换取 coherence / 管理上的便利——更倾向 L1/L2 Inclusive。L1/L2-I, L2/L3-E 比较常见。

我们这节课的 Project4 实现的是 NINE (non-inclusive, non-exclusive) cache。


Other Notible Facts

  • 现代处理器中，4-way-SA, WB, Write Allocate 是最常见的，即使是对于适合 DM+VC 的 L1(D)。

  • 在高级 CPU 上，cache miss 的代价不再像“停多少拍”那么简单,尤其 Out-of-Order 处理器，会想办法把 miss penalty 藏起来。Cache miss 的实际惩罚取决于后面有没有足够多的独立工作可以填充进去，否则就要填 NOP 导致 CPI 下降。

  • 配合 non-blocking cache，可以让多个 miss 重叠 (MLP)。

  • 软件缓存用哈希表之类的数据结构查找，而硬件缓存支持 associative search；前者可以用复杂的 replacement policy，而后者必须用简单迅速的 policy。

  • Cache miss 的影响取决于 program data flow：关键路径 miss 被后面一长串指令依赖所以影响很大；非关键路径 miss CPU 可以先做很多别的工作，影响就小很多。AMAT 只是近似，不是所有 miss 都一样贵。

  • Miss 往往不是 “独立随机事件”，而是 correlated。Brainstorm：用 ML / AI 去发现这些相关性，用于训练现代化 prefetcher 取代过去的线性 prefetch。

  • 算法的算术复杂度低不等于运行就一定快，locality matters，程序访问数据的局部性，往往比单纯操作次数更能决定真实性能。

    比如当数据规模大时，Radix sort 需要的操作数比 quicksort 少，但前者受到 cache misses 影响，运行时间并没有更快。

  • 再次强调，**cache 不是只存在于 CPU 的 L1/L2/L3 里，cache 是一种解决问题的思想。**比如 Akamai / CDN 是网络世界的 cache，通过 distributed stations 解决网络堵车。再比如 GPU register access 加速也可引入类似的缓存层次。


comments powered by Disqus