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 »

Cache与内存的映射

1. 理解Cache Line

在大家印象中Cache Line就是一个数据块,能有什么理解难度呢?不妨再反问一下自己:真的是这样吗?

上篇文章中就说到Cache本身的容量远远小于内存容量,CPU为了能正确定位数据所在的CacheLine还需要做很多工作。简单来说可以将Cache Line理解成一个带标签的存储槽,下面以一个直观的例子来说明:

小A同学坐在座位上,如果老师想检查小A的作业的话就需要先定位到小A所在的座位号,然后再从小A的座位上拿到小A作业本。在这个例子中,小A的作业本就对应Cache Line中的数据,老师就是CPU Core,小A其实对应着内存地址(TAG),小A的座位就是Cache Line本身,而座位号就是Cache Line在Cache中的位置(索引,Index),教室里所有的座位就可以理解为整个Cache,而学校里所有的学生则是全部的系统内存。

上图就是Cache的内部组织,除了TAG和数据外,还有两个标志位,V表示此CacheLine中的数据是否是有效的,即座位上有没有学生,D表示CacheLine中的数据有没有被修改过,修改过的数据是不能直接清除的,需要写回到主存(内存)。

2. Cache与内存的映射

映射方式有3种:
1. 直接映射 (Direct Mapping)
2. 组相联 (K-Way Set Associative Mapping)
3. 全相联 (Full Associative Mapping)

2.1 全相联

继续以学生和座位为例,正常情况下我们并不限定位置,大家随便坐,先到先得。老师如果想检查一个同学的作业的话,也可以一个一个来找,即线性搜索,当然此举必然花费老师很多时间。另外一点需要强调,学生并不是老老实实坐在座位上的,不断会有学生进来或离开,也会有同学出去后又进来但前后的坐位并不相同的情况,这样的话“线性搜索”将不再可能。

想像最常见的一个场景,老师并不会主动来找,而是直接喊这个同学的学号(名字可能会有重名,但学号不会),所有的学生在听到名字后同时判断老师叫的是不是自己,只有被叫到的同学才会应答。在听到老师的请求后所有的学生同时并行判断的动作,对应于CPU及硬件实现就是一个并行的比较电路,而比较的内容则是座位上的同学和老师叫的学号,分别对应着TAG和内存地址。

这个例子中的随机编排座位的方式就是全相联映射。全相联映射方式的定位操作是最高效的,但是硬件成本亦最高,毕竟要实现复杂的并行比较电路,只有容量较小且对性能至关重要的缓存才会使用,如CPU的内存管理单元 (MMU, Mmemory Management Unit) 的TLB缓存 (Translation Lookaside Buffer),TLB中存放的是虚拟地址与物理地址的1:1的转换关系。

2.2 直接映射

假设上面例子中的教室只有20个座位,编号为0-19,全校共有400名学生,学号分别为0-399。直接映射方式的求是座位不能随便选择,而是通过学号和所有座位数的余数决定,即学号为0、20、40、60...的同学只能坐在0号座位上,同样学号为1、21、41、61...的同学只能争1号座位,后来的同学会将正坐在位置上的同学挤出去,如果1号和21号同学都要来教室的话就会发生两人不断被挤出去的情况,这就是Cache的颠簸效应(Cache Thrashing)。

2.3 组相联

为了解决直接映射的颠簸效应,遂引入了组相联映射。假设学校共有5个系,每个系均有80名学生,那我们可以这样安排座位,一系的学生只能选择0/5/10/15这4个座,二系则是1/6/11/16,依次类推,如下图所示:每个系有4个座位,这4个座位是没有顺序的,即本系的学生随意坐,但全系的80名学生将争抢这4个座位,这种分为5组的映射方式就是4路组相连映射,4路的意思是每组中有4个座位,即4个CacheLine。现实中CPU Cache无论是组数还是相联度(路)均是2的幂指数,不会出现本例中奇数5的情形。

直接映射方式其实是组相联映射的一种特例,亦称作是单路组相联。

2.4 特别说明

更详细的阐述可参考链接1 [蜗窝科技: 浅谈Cache Memory],作者smcdef通过举例来说明三种方式的实现细节,作图精美,本文不再做过多说明。

3. Cache的分类及访问流程

目前主流的CPU,如Intel及AMD的桌面或服务器平台的CPU都是支持分页的,即物理内存的管理是以页划分和管理的。X86平台的页大小通常是4K,即4096字节。CPU层所操作的内存地址称作是虚拟地址(逻辑地址),并不是物理的内存地址,从虚拟地址至物理地址的翻译由硬件MMU来执行。Cache与MMU的位置关系直接决定了Cache的分类:如果Cache相对MMU离CORE的距离更近,则此类Cache被称作为逻辑Cache;相反则称作是物理Cache。下图是L1、L2及LLC与MMU的关系,L1是集成在CORE内部的,所以可以得出L1是逻辑Cache,而L2和LLC则是物理Cache。

如果再加上TAG的取值,取物理地址或虚拟地址,又可以组合成4种情况:

3.1. PIPT (Physically Indexed Virtually Tagged)

下图是2路组相联的PIPT的示例,CacheLine大小为64字节,即6个比特,组索引(SET)由S个比特来编址,剩余的部分即为标签项(TAG),CPU通过组索引来定位此地址所在Cache组,然后通过两组比较电路进行TAG值的并发比较,然后即可确定Cache所在位置,当然也有可能出现没有命中的情况。

L2及LLC,以及早期的CPU的L1均是使用PIPT的方式,这是因为内存的物理地址是唯一的,这就大大简单化PIPT的实现逻辑。

3.2. VIVT (Virtually Indexed Virtually Tagged)

VIVT的Index和Tag均使用虚拟地址,全程不需要MMU的参与,是性能最好的定位方式,但是由于虚拟地址的特性会导致歧义和别名的问题,最终决定了VIVT方式的不可行:

歧义 (Ambiguity,亦称Homonyms问题):不同的进程拥有相同的虚拟地址空间,虚拟化平台上不同的虚拟机亦是同样的情况。从而会导致相同的虚拟地址(不同进程或不同虚拟机)所对应的物理页面不同的,VIVT的方式将不能正确区分。

别名 (Alias):是指同一个物理页映射至不同的虚拟地址,即同一个物理地址将有多个虚拟地址的别名。多个别名的情况下VIVT将会映射至不同的CacheLine,将不能保证数据的一致性。

3.3. VIPT (Virtually Indexed Physically Tagged)

CPU层的指令所操作的均是虚拟地址,使用虚拟地址作为索引来直接进行Cache的定位不必经过MMU的转换。此时Cache Set的定位和MMU的转换过程是并发的,定位到指定Cache Set之后再进行两个Cache Line的Tag的对比,此时两个Tag的比对也是并行处理的。

3.4. PIVT (Physically Indexed Virtually Tagged)

PIVT方式相比PIPT和VIPT来说没有任何优势,性能上必须等MMU转换完成之后,而且在数据一致性上无法处理好别名问题。

4. L1 Cache (VIPT)的别名问题

在Cache与内存的映射关系上,考虑到成本及性能,多采用组相联方式;在CacheLine的定位和访问方式上,L1 Cache多是VIPT,而L2及LLC是PIPT。以Intel Pentinum G5500T为例:L1是8路组相联,大小为32K; L2是4路组相联,大小为256K;LLC即L3则是16路组相联,大小为4M。

L1采用的是VIPT映射方式,虽然VIPT方式通过物理地址TAG解决了歧义的问题,但别名的问题依然存在,是怎样解决的呢?

实际上L1 Cache的每个Cache Set的数量正好限定在 (PAGE_SIZE/CACHE_LINE) 之内的,以G5500T为例,32K/(8*64) = 4K/64 = 64。虚拟地址最低6位为CacheLine中的偏移;位6-11共6位是组索引,6+6正好是12,即一个4K PAGE的大小,从而可推论出不管虚拟地址是多少,任意内存页面的固定偏移总是映射到相同的Cache Set中,而TAG的选择正是物理地址中的是12-47,可以理解为PFN,即每一个物理页面的唯一帧号,所以同一物理页的不同的虚拟地址最终将定位到同一个Cache Set中的同一个Cache Line上。

L1是8路组相联的,也就是说一个Cache Set中容纳了8个Cache Line,由上面的结论可得出:这8个Cache Line将分别来自于不同的物理页。最后大家不妨想一个问题,如果要将L1 Cache从32K增加到64K的话,怎样构造L1的相联度及Cache Set组数才是合理的?有多少种组合?

5. 参考连接

  1. 蜗窝科技: 浅谈Cache Memory
  2. CHIPRESS:What are the types of caches based on index and tag bits?
Continue reading » · Rating: · Written on: 09-04-20 · No Comments »

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占据了很大一部分的面积:

一般而言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

Continue reading » · Rating: · Written on: 08-30-20 · No Comments »

CPU Cache测量方法

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

Cache的分级结构

CPU Memory Architecture
- 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不同分级的性能

Cache Heirarachy

在上图中看到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的测量

原理:

结论:


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

硬件预取: Hardware Prefetcher

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

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

如何关闭硬件预取

  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测量出来结果:


可以看到整个曲线有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
Continue reading » · Rating: · Written on: 08-19-20 · No Comments »