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

测量方法

测量的原理是尝试制造“相联度冲突”强制触发CacheLine的驱逐(Evict)，以此来推算出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，从而导致度量第二条指针链时访问延时的增加。

测量结果

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的映射算法及替换策略可以参见文末的参考链接，等后续有时间我再进行详细解读。

参考链接

• Reverse Engineering Intel Last-Level Cache Complex Addressing Using Performance Counters
• Cracking Intel Sandy Bridge’s Cache Hash Function
• Mapping the Intel Last-Level Cache