Cache相联度测量

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

参考链接

  1. Reverse Engineering Intel Last-Level Cache Complex Addressing Using Performance Counters
  2. Cracking Intel Sandy Bridge’s Cache Hash Function
  3. Mapping the Intel Last-Level Cache
Continue reading » · Rating: · Written on: 09-09-20 · No Comments »