Nothing Is Secret

Cache相联度测量

从上篇文章中我们得知Cache在兼顾性能及成本后都是设计成组相联方式的，以Intel Pentinum G5500T为例：L1是8路组相联，L2是4路组相联，LLC是16路组相联。针对一款未知CPU，可以通过cpuid指令来查询到以上信息，但我们的目标是通过内存访问延时的度量来测算出每级Cache的相联度。

测量方法

测量的原理是尝试制造“相联度冲突”强制触发CacheLine的驱逐(Evict)，以此来推算出Cache的相联度。参见下图： Cache 相联度测量方法

这里我们先将整个测试内存块分成不同数量的Window大小，然后以Window为间隔进行跳跃式的访问，为此分别构造两个指针链，第一条指针链是左图所示的每个Cache Line的第一个DWORD（或QWORD），右图则是第二指针链，将每个Cache Line的最后一个DOWRD（或QWORD）串联起来。测量过程分为两步预热和度量：先通过第一条链的访问达成Cache的预热（从内存加载至Cache），然后度量遍历第二条链的访问时间。

如果所有Window的内存块均在Cache中，将不会发生冲突，此时的延时将是最短的。如果不断增加Window的数量（即相联度）的话，必然在超过Cache所设计的相联度之后发生冲刷效应，如L1 Cache是8路组的，就是说可容纳8个来自不同页面的Cache Line，如果再访问第9个内存页的话，CPU将不得不驱逐一个Cache Line，从而导致度量第二条指针链时访问延时的增加。

测量结果

Cache 相联度测量结果

1，水平方向基本呈现4个台阶，分别对应不同的访问速度，但并不严格对应L1/L2/L3和内存，因为每次测量都是混合访问的结果，即L1、L2、L3或内存都有访问，但各自的比率不同，Cache的命中率越高延时越低，即垂直方向上高度越低

2，先以1K的步长来分析，1K应该一直在最低台阶上，然后在X轴32处时间跳跃，说明L1 的Cache Size为32K，当探测组数超过32组时会发生挤出效应，同理2K/4K分别是16组及8组的探测位置出现分叉

3，打32K的第一个分叉点：8，这时说明以32K为步长的话，同时访问超过8组的话会导致时延变长，直接跳到了最高台阶，说明L1 Cache是8路分组的

4，从第二个台阶水平 ，从最右边向最左分别找到32 8K及16 16K两个分叉点，即256K的容量

5，然后以256K的线从最左侧向右寻找跃升点，分别在4和8的位置跃升，说明L2是4路分组的。那为什么会在8的位置也出现跃升呢？大家可以自己想一想

特殊的LLC

从上图中来看L3，疑似L3的台阶从右向左只在256K的线发生了跃升，跃升点是32，即32 * 256K = 4M; 然后再找4M的线，结果4M的线只在4和8点有跃升，然后一直平稳在L3的台阶上。8M的线亦同样，与L1及L2相对呈现出了不同的规律。

其实原因在于L3即LLC采用了不同的分组hash计算方式及不同的替换策略，以致当前的探测方式不再适用。但我们依然可以做个猜测，比如 32K、64K、128K的直接越过了L3，说明了什么问题？当32K、64K、128K超过8组的时就已经超出了L3的组容量，即产生了挤出效应，从而造成了直接内存访问的局面。关于LLC的映射算法及替换策略可以参见文末的参考链接，等后续有时间我再进行详细解读。

参考链接

Cache为什么能提升性能

1. Cache的容量设计

上篇文章中介绍到CPU Cache是分级的，L1 Cache是集成在Core内部的，L2则是紧贴着Core，而L3是多个Core共享的。离Core（流水线）越近的分级速度越快，但容量也更小，并且造价愈贵。Cache的实现采用了高速的SRAM电路 (静态随机存取存储器: Static Random-Access Memory)，SRAM相对DRAM (动态随机存取存储器: Dynamic Random Access Memory)要复杂和庞大的多，即使不考虑成本能做到无限增大，但因为电路复杂度的提升其性能即访问速度必然会下降，另外也会使得CPU的面积急速膨胀。最终，CPU的每一级Cache的容量都是在设计之初考虑各方面因素折中后的结果（trade-off）。下图是AMD Zen的CCX的die shot[来源：1. Zen - Microarchitectures - AMD]，从图中我们就能看中L2及L3 Cache占据了很大一部分的面积： AMD ZEN die shot

一般而言L1 Cache约几十K，L2则是几百K，L3是几M或几十、几百M，但相比较内存动不动几十G的大小来说还是小了太多，根本不在一个数量级上。那么问题来了：Cache容量比内存小了太多，为什么根本不在一个数据量级的Cache能够大副度提升系统性能？

2. 局部性原理 (Principle of Locality)

简言之，程序倾向于访问（或执行）刚刚访问过的数据（执行过的指令）或与之相临近的数据（指令）

2.1 时间局部性 (Temporal locality):

刚刚被访问的地址（数据）在未来有很大的可能性被再次访问，即用过的数据可能会再次被用到

2.2 空间局部性 (Spatial locality):

刚刚被访问的地址的临近位置在未来有很大的可能被访问，以数组D[]为例，当前访问的是D[i]，那么D[i+1]有很大的可能将被访问

2.3 算法局部性：

程序代码也遵守2/8法则，即帕累托法则（Pareto principle，亦称关键少数法则），80%的时间都是在执行20%的代码

正是因为局部性原理，少量的Cache大大减少了数据的访问延迟，从而提升了整体性能。

3. Cache的放大效应

先来考虑一个问题：Cache命中率(Cache Hit) 99%与98%的差别会有多大？从数值上来看二者本身仅相差1%，性能上最终能有多大差别呢？

假设命中L1的延时为4 cycles，不命中的话需要从内存中读取数据的延时为150 cycles，那么： 99%命中率的情况: 0.99 4 + 0.01 150 = 5.46 98%命中率的情况: 0.98 4 + 0.02 150 = 6.92

后者比前者的延时多了(6.92 - 5.46) / 5.46 = 26.7% 之多。换成95%的命中率的话，延时将高达99%命中率时的一倍之多。由此看来，不命中（Cache Miss）所带的性能惩罚巨大，这也预示了未来Cache发展的趋势，即容量将越来越大，拥有GB级Cache容量的CPU将指日可待，另外增加L4分级也将是不可避免的，有兴趣的读者可进一步参阅 [2. The Next Platform: Cache Is King]。

4. Cache Miss的原因

前面说了Cache Miss的惩罚，下面说一下会导致Cache Miss的因素，可以简单归纳为3C:

  1. Cold (Compulsory) Miss： 第一次访问数据时，数据根本不在Cache中
  2. Conflict Miss： 因冲突导致Cache Line被驱逐出Cache，上一篇文章中提到了相关的方法，如Evict(驱逐)、Prime(装填)等，当然冲突所导致的Cache Miss只针对组相联的Cache结构（直接映射可以认为是单路组相联），而全相联的Cache结构是没有Conflict Miss的，后续还会针对此课题做详细的介绍
  3. Capacity Miss： Cache的容量毕竟有限，如果程序确实需要密集访问大量内存时，Cache必然是不够的

在指定的CPU硬件上如果想提升Cache Hit的话就要从这几个因素上着手，如通过硬件预取以减少Cold Miss，通过程序算法改进及结构重组可减少2和3所带来的Cache Miss的发生概率，本文先点到为止，后面将进行详细拆解。

5. 参考资料

  1. wikichip: Zen - Microarchitectures - AMD
  2. The Next Platform: Cache Is King

CPU Cache测量方法

通过上一篇文章《通过TSC观察CPU》知道了可以通过TSC来测量CPU的内部行为，本文将介绍CPU Cache的结构及几种常用的测量手法：

Cache的分级结构

Memory & Cache的分级结构

  • Cache 是分级的：一般分为3级，较老的CPU如Core 2 Duo只有2级。L1是集成是core内部的，指令与数据Cache是分离的，好L1C和L1D；L2是紧贴core的；L3是多核共享的，每个core有自己的Slice，通过Ring Bus或Mesh结构互联互访
  • Cache以Cache Line为访问单位，即Cache及内存的访问是以块为单位的，而不是字节单位。较新的X86 CPU的Cache Line一般是64字节。上一篇文章通过TSC观察CPU曾注意到一个有趣的测量结果：X86程序访问一个1字节与访问2个、4个及8个字节的延进均为31个指令周期，并不是线性增长的，就是这个原因
  • 层级包含与否由CPU实现决定：L2一般都是包含L1的全部内容的，L3可以是Non-inclusive，也可以是Exclusive。Intel的CPU一般是包含的，但AMD的Zen系列CPU的L3就是定义为L1/L2的Victim Cache，Victim是指从L1及L2中移除的Cache项
  • Cache自身的构造采用“组相联”方式

Cache不同分级的性能

Memory & Cache性能数据

在上图中看到Cache是分级的，用不同级的访问速度有很大不同，故我们可以通过制造冲突或直接Flush Cache的方式将数据从Cache中清除，从而通过前后内存访问的时间差来进行判定。

测量方法

制造冲突以清除Cache的常用手段有以下几种【参阅 1：Cache side channel attacks: CPU Design as a security problem by Anders Fog]】：

  1. Evict (驱逐) + Time (测量) ： 通过制造冲突以达成被测量目标数据从cache中清除的目的
  2. Prime (装填) + Probe (探测) ：与1)方法一样，只是作用对象是反的
  3. Flush (冲刷) + Reload (加载) ) ：最主动和最快的办法，直接利用clflush指令刷新，然后再读取内存，此时会发生Cache Miss事件。
  4. Flush (冲刷) + Flush (冲刷) ) ：与3)类似，但测量的是clflush指令针对数据在不在cache中的执行周期的不同 在条件许可的情况下，尽量采用第3种，即最快的办法。

实例：Flush + Reload

Flush即clflush指令，Visual C++中定义如下：

        extern void _mm_clflush(void const*_P);

测量代码：

        /* flush */
        _mm_clflush(&data[0]);

        /* measure cache miss latency */
        ts = rdtscp(&ui);
        m |= data[0];
        te = rdtscp(&ui);

实战：Cache Line的测量

原理： Cache性能测量方法

结论： Cache性能结果

从图中我们可以看到64字节是一个明显的分界点。

硬件预取: Hardware Prefetcher

如果你在自己的电脑上进行测试，你看到的可能不是上图所示的样子，很大的可能如下图所示，明显的分界点不是64字节而是128字节： Cache性能结果

这是因为硬件预取即HWPrefetcher的缘故，并且硬件预取默都是开启的。硬件预取功能会在每次Cache Miss的情况下多读一个Cache Line，可以理解为每次读取两个Cache Line即64 * 2 = 128字节，但数据并不是同时到达的，第二个Cache Line的数据的到达周期会晚些，这也是为什么在128这个点上的延时会比64高。 CPU Cache Prefetcher

如何关闭硬件预取:

  1. 通过BIOS设置： 通过BIOS选项来关闭hwprefetcher，对所有的CPU生效
  2. 通过内核调试器windbg直接关闭：通过直接改写msr寄存器关闭当前核的硬件预取功能: 
    0: kd> rdmsr 0x1a4
msr[1a4] = 00000000`00000000
0: kd> wrmsr 0x1a4 0x0f
0: kd> ~1
1: kd> rdmsr 0x1a4
msr[1a4] = 00000000`00000000
1: kd> wrmsr 0x1a4 0x0f
1: kd> rdmsr 0x1a4
msr[1a4] = 00000000`0000000f
1: kd> ~0

实战：Cache不同分级的访问延时测量

如果我们以更大的的stride进行同样的测试则可以测量出Cache每一级的大小，即L1D，L2，LLC和内存访问的延时。下图中我们分别以1K、2K，直至64M的stride测量出来结果： Cache性能结果 可以看到整个曲线有4个平台，分别表示L1D、L2、LLC和内存。L1D的大小为32K，L2为256K，这部分和CPUZ的输出是一致的。 但第三个平台包含了512K、1M及2M，从4M开始延进有明显的跃升，从8M之后基本稳定在高位。这里就涉及到了LLC组织的不同：L1D及L2 Cache都是与物理核（Core）绑定的，而LLC是绑定CPU的，即2核的CPU的两个核心会共享同一个LLC，整个LLC是平均分配给每个核的，然后每个核心的LLC通过Ring Bus互联，即每个核又可以访问所有的LLC。这里在4M的stride发生波动的原因有两个：

  1. 当前运行测量程序的CPU核心用尽自己的LLC后会通过Ring Bus竞争访问另一个核心的LLC
  2. 测量程序运行时整个操作系统也在运行，所以整个系统均会竞争使用LLC，必然会带来挤出效应，从而增大了延时

参考资料

  1. CSCA: Cache side channel attacks: CPU Design as a security problem by Anders Fogh
  2. HWPF: Disclosure of Hardware Prefetcher Control on Some Intel® Processors
  3. SourceCode: CacheLatency Github Repo