CPU Cache 学习

CPU Cache 是什么

Small,fast storage used to improve average access time to slow memory.

CPU Cache 的原理

时空局部性

典型的 Nehalem 架构(Intel 2008年,45nm 处理器),建立在 core 微架构上:

三层 Cache:

  • L1(per-core): 32KB data cache,32KB instruction cache
  • L2(per-core): 256KB(data + instruction)
  • L3(shared): 8M

CPU Cache 策略

  • Inclusive 多层 Cache:外层 Cache 包含内层 Cache 的所有数据,比较常见的形式.
  • Exclusive 多层 Cache:外层 Cache 一定不包含内层 Cache 的数据.
  • 选择原则:Inclusive 浪费空间效率高;Exclusive 节约空间效率低.

如何查看 CPU 的 Cache 信息

Linux 下:

  • 在开机信息中查看,dmesg | grep cache
  • 在 /sys/devices/system/cpu/ 目录下,查看每个 CPU 的 cache 信息
  • Windows 下:coreinfo 命令行工具。

CPU Cache 性能参考

L1 1ns,L2 3ns,L3 12ns,memory 65ns

之前Jeff Dean给的参考:L1:0.5ns,L2 7ns,Memory 100ns

CPU Cache 的映射

Cache Line: 存取内存时最小的 Cache 单位,(已经不再是按字节访问,而是按块存取)。 X86: 64 bytes ARM: 32 bytes

在做映射时,每块的内存(一个chunk)映射到对应的 Cache 槽。

假设 Cache 一共 M 个 slot(每个 slot 就是 cache line 大小),N 路映射:

  1. 直接映射(direct mapped cache),相当于 N=1,就一个 Set,地址为 addr 的内存 chunk 会映射到 addr % M 的 slot 上,竞争会比较激烈,带来的结果就是命中率降低。
  2. N 路组关联(N-way set associative cache),分了 N 个 Set,每个 Set 有 M/N 个 Slot,内存 chunk 可以映射到 N 个 set 中的任意一个。是比较经典的方案,既兼顾了效率,硬件也 OK。
  3. 完全关联(Fully associative cache),相当于每个 slot 就是一个 set,每块内存 chunk 都已映射到任意一个 slot,硬件复杂,查询的效率也是最大的:O(N),N=M 最大。

以上图的 L3 Cache 为例:

  • Cache Line 64 bytes
  • M = 8M / 64 = 128k
  • N = 16 ways
  • Set = M / N = 8k Slot

假设是按内存地址映射,如果 addr1 % 8k == addr2 % 8k,那么 addr1 和 addr2 的内存块会竞争这个 16 ways。

const size_t len = (16 << 20);
int a[len];
int pos = 0, step = 256;
for (int i = 0; i < loop; ++ i)
{
    a[pos & (len - 1)] ++;
    pos += step;
}

这个代码中,步长 step 的值影响了最终的执行效率,如果 step=256 的话,意味着每过一段就会发生 Cache 的竞争导致不命中,执行效率会比较低。

具体可以参考这一篇:7个示例科普CPU Cache

CPU Cache Conherence (缓存一致性)

多核 CPU 在读写 Cache 时,保证 Cache 中的数据一致。

一般情况下,CPU 通过 MESI 协议机制,保证了 Cache conherence。

MESI 协议的4种状态:Invalid、Shared、Exclusive、Modified

状态 描述
M(Modified) 脏数据,被修改过,还没有写入内存
E(Exclusive) 只存在当前Cache中,与内存中一致
S(Shared) 多个Cache中都有该数据,与内存中一致
I(Invalid) 数据失效

在 MESI 协议中,每个 Cache 的 Cache 控制器不仅知道自己的读写,还会监听其他 Cache 的读写,并根据这些操作做状态流转来保证数据一致性

需要注意的几处:

  • 监听到 remote write,如果本地是 Exclusive、Share或者Invalid,直接转入 Invalid,如果本地是 Modified,则应该先写入内存,再转入 Invalid;
  • 监听到 remote read,如果本地是 Exclusive 则转入 Shared,如果是 Modified,也要先写入内存,再转入 Invalid;

一些改进版本:

  • AMD 的 Opteron 处理器使用从 MESI 中演化出的 MOESI 协议,O(Owned) 是 MESI 中 S 和 M 的一个合体,表示本 Cache line 被修改,和内存中的数据不一致,不过其它的核可以有这份数据的拷贝,状态为 S。
  • Intel 的 core i7 处理器使用从 MESI 中演化出的 MESIF 协议,F(Forward) 从 Share 中演化而来,一个 Cache line 如果是 Forward 状态,它可以把数据直接传给其它内核的 Cache,而 Share 则不能。

参考文章