一文看懂CPU cache的基本原理

CPU cache主要是为了解决CPU与内存之间的速度不匹配问题。

CPU cache一般分为多级，例如L1、L2、L3 cache等。越靠近CPU的cache，速度越快，成本越高，容量越小。L1 cache一般包括指令cache (I-Cache)和数据cache(D-Cache)，它们的原理基本一样，但是D-Cache需要读取和写入，而I-Cache只会被读取，不会被写入，因此D-Cache更复杂一些。

L1 Cache最靠近处理器，需要和处理器保持近似相等的速度。L1 Cache一般使用多端口SRAM来实现，容量大的SRAM需要更长的时间来找到一个指定地址的内容。因此，L1 Cache的速度最快，但容量最小。

L2 Cache一般都是指令和数据共享，它可以容忍更慢一些，尽量保存更多的内容。所以，CPU的L2 Cache一般是以MB为单位的。

cache主要由两部分组成，Tag RAM和Data RAM。cache利用了程序中的相关性，一个被访问的数据，它本身和它周围的数据在最近都有可能被访问，因此Data部分用来存一片连续地址的数据，而Tag部分则存储这片连续数据的公共地址，一个Tag和它对应的所有数据组成的一行称为一个Cache line（cache line大小一般为64B），Cache line中的数据部分称为数据块(Cache data block,也叫Cache block或Data block,在下文不进行区分)。如果一个数据可以存储在cache中的多个地方，这些被同一个地址找到的多个cache line称为cache set（即相同index，不同tag）。cache结构如下图。

cache的结构

上图表示了一种可能的实现方式。cache有三种实现方式，直接映射(direct-mappd)，组相连(set-associative)和全相连(fully associative)，这三种的原理如下图。对于物理内存中的一个数据来说，如果在Cache中只有一个地方可以容纳它，它就是直接映射的Cache；如果Cache中有多个地方都可以放这个数据，它就是组相连的Cache；如果Cache中任何地方都可以放这个数据，那它就是全相连的Cache。直接映射和全相连是组相连Cache的两种特殊情况，现代处理器中的TLB和Victim Cache多采用全相连结构，而I-Cache和D-Cache则采用组相连的结构。

cache的三种组成方式

Cache只能保存最近被处理器使用过的内容，由于容量有限，很多情况下，要找的指令或者数据并不在Cache中，这称为Cache的缺失(cache miss)。cache miss发生的频率直接影响CPU性能，影响Cache缺失的情况如下：

(1) Compulsory。由于Cache只是缓存以前访问过的内容，因此第一次被访问的指令或数据肯定不在Cache中，这个缺失肯定会发生。可以采用预取(prefetch)的方法来尽量降低这种缺失。

(2) Capcity。Cache容量越大，可以缓存更多的内容，容量是影响Cache缺失的一个关键因素。例如，当程序频繁使用的5个数据属于不同的Cache set，而Cache的容量只有4个Cache set时，那么就会经常发生缺失。

(3)Conflict。为了解决多个数据映射到Cache中同一个位置的情况，一般使用组相连Cache，由于实际硅片面积的限制，相连度不可能很高，例如，在一个两路结构 (2-way) 的Cache中。如果程序频繁使用的三个数据属于同一个Cache set，那么就会经常发生缺失，此时可以使用Victim Cache来缓解这个问题。

影响Cache缺失的这三个条件，称为3C定理。在超标量处理器中，可以采用预取和victim cache这两种方法，但无法从根本上消除cache缺失，只能减少它发生的频率。

1. cache的组成方式

1.1 直接映射

直接映射（direct-mapped）的Cache是最容易实现的一种方式，处理器访问存储器的地址分为三部分，Tag、Index和Block Offset。使用Index从Cahce中找到一个对应的Cache line，但是所有Index相同的地址都会寻址到这个Cache line，因此Cache line中还有Tag部分，用来和地址中的Tag进行比较，只有它们相等，才表明这个Cache line是想要的那个。一个Cache line中有多个数据（通常为64 Bytes），通过地址中的Block Offset定位到每个字节。Cache line中还有一个有效位valid，用来标记Cache line中的数据是否有效，只有在之前被访问过的存储器地址，它的数据才会存在于对应的Cache line中，相应的有效位也会被置1。

直接映射的cache

对于所有Index相同的存储器地址，都会寻址到同一个Cache line中，这就会发生冲突，这是直接映射Cache的一大缺点。如果两个Index相同的地址交叉访问Cache，就会一直导致Cache缺失，严重降低CPU执行效率。

下面通过一个例子来说明存储器地址的划分对Cache的影响，下图为一个32位存储器地址，Block Offset有5位，所以Data block的大小是2^5 = 32字节，Index是6位，表示Cache中共有2^6=64个Cache line(在直接映射中，Cache line和Cache Set是同义的)，存储器地址中剩余的32-5-6=21位作为Tag值，因此这个Cache中可以存储的数据大小为64*32=2048字节，即2KB；而Tag部分的大小是64*21=1344位，约为1.3Kb；有效位占用的大小为64*1=64位。一般以数据部分的大小来表示Cache的大小，因此这个Cache是一个2KB直接映射的Cache，实际它还额外占用多于1.3Kb的存储空间。

存储器的地址划分

直接映射的Cache在实现上最简单，它不需要替换算法，执行效率也是最低的，现代处理器很少使用这种方式。

1.2 组相连

组相连(set-associative)是为了解决直接映射Cache的不足而提出的。存储器中的一个数据不是只能放在一个Cache line中，而是可以放在多个Cache line中，对于一个组相连的Cache来说，如果一个数据可以放在n个位置，则称这个Cache是n路组相连(n-way)。下图为一个2-way组相连的cache。

2-way组相连的cache

这种结构仍然使用地址的Index部分对Cache进行寻址，此时可以得到2个Cache line，这2个Cache line称为一个Cache set，哪个Cache line是最终需要的，需要根据Tag比较结果来确定。如果两个Cache line的Tag比较都不相等，那么就发生了Cache缺失。

因为需要从多个Cache line中选择一个匹配的结果，这种Cache的实现方式和直接映射Cache相比，延迟会更大，但这种方式可以显著减少Cache缺失发生的频率，因此在现代处理器中广泛应用。

Tag和Data部分是分开放置的，称为Tag SRAM和Data SRAM，可以同时访问这两个部分，称为并行访问；相反，如果先访问Tag SRAM，根据Tag比较的结果再去访问Data SRAM，称为串行访问。这两种方式各有优缺点。

对于并行访问，当Tag部分的某个地址被读取的同时，这个地址在Data部分对应的所有数据也会被读出来，并送到一个多路选择器上，这个多路选择器受到Tag比较结果的控制，选出相应的Data block，然后根据存储器地址中的Block offset的值，选择出合适的字节，一般将选择字节的这个过程称为数据对齐。

并行访问Cache中的Tag和Data

Cache的访问一般是处理器关键路径，并行访问Cache若在一个周期内完成，在现实中会占据很大延迟，要想使处理器运行在较高的频率下，Cache的访问就需要使用流水线。前面说过，对于指令Cache来说，流水线的结构不会有太大的影响，仍旧可以实现每周期读取指令的效果；而对于数据Cache来说，使用流水线则会增大load指令的延迟，对处理器的性能造成影响。

并行访问cache的流水线如下图。流水线的地址计算阶段可以计算出存储器的地址，接下来的Disambiguation阶段对load/store指令之间存在的相关性进行检查，然后在Cache Access阶段就可以直接并行访问Tag SRAM和Data SRAM，并使用Tag比较的结果对输出的数据进行选择，然后在下一个流水线阶段Result Drive，使用地址中的block offset值选出最终需要的数据。将整个Cache的访问放到几个周期内完成，降低处理器的周期。

并行访问cache的流水线

而对于串行访问来说，首先对Tag SRAM进行访问，根据Tag比较的结果，就可以知道数据部分中的哪一路需要访问，此时可以直接访问这一路数据，就不需要多路选择器了，而且只需访问数据部分指定的那个SRAM，其他的SRAM由于都不需要被访问，可以将它们的使能信号置为无效，这样可以节省很多功耗。

串行访问Cache中的Tag和Data

完全串行Tag SRAM和Data SRAM这两部分的访问，它的延迟会更大，仍旧需要使用流水线来降低对处理器的周期时间的影响，用流水线降低了访问Tag SRAM和Data RAM的延迟，因为此时已经不再需要多路选择器，这对降低处理器的周期时间是有好处的，但是一个明显的缺点就是Cache的访问增加了一个周期，这也就增大了load指令的延迟，因为load指令处于相关性的顶端，会对执行效率造成影响。

并行访问会有较低的时钟频率和较大功耗，但是访问Cache的时间缩短一个周期。考虑到乱序执行的超标量处理器可以将访问Cache的这段时间，通过填充其他的指令而掩盖起来，所以对于超标量处理器，当Cache的访问处于关键路径时，可以采用串行访问来提高CPU时钟频率，同时并不会由于访问Cache的时间增加了一个周期而引起性能的明显降低；相反，对于普通的顺序执行的处理器来说，由于无法对指令进行调度，访问Cache如果增加了一个周期，很可能会引起处理器性能的降低，因此这种处理器使用并行访问比较合适。

1.3 全相连

在全相连cache中，对于一个存储器地址来说，它的地址可以放在任意一个Cache line中。地址不再有Index部分，而是直接在整个Cache中进行Tag比较，找到比较结果相等的那个Cache line，相当于直接使用存储器的内容来寻址，从存储器中找到匹配的项，这其实就是内容寻址的存储器（Content Address Memory，CAM）。实际处理器在使用全相连的Cache时，都是使用CAM来存储Tag值，使用普通的SRAM来存储数据。全相连的Cache有着最大的灵活度，延迟也是最大的，因此这种结构的Cache不会有很大的容量，例如TLB就会使用这种全相连的方式来实现。

全相联的cache

2. cache的替换策略

不管是读取还是写入Cache时发生了缺失，都需要从有效的Cache line中找到一个并替换，这就是替换(cache replacement)策略，本节介绍两种最常用的替换算法。

2.1 近期最少使用法

近期最少使用法（Least Recently Used，LRU）会选择最近被使用次数最少的Cahce line，因此这个算法需要跟踪每个Cache line的使用情况，为每个Cache line都设置一个年龄（age）部分，每次当一个Cache line被访问时，它对应的年龄就会增加，或者减少其他Cache line的年龄值。当进行替换时，选择age值最小的进行替换。但是随着Cache相关度的增加（也就是way数的增加），要精确实现这种LRU方式就非常昂贵了。因此在way的个数很多的情况下，都是使用伪LRU的方法。

伪LRU算法的工作流程

2.2 随机替换

在处理器中，Cache的替换算法一般都是使用硬件来实现，因此如果做得很复杂，会影响处理器的周期时间，于是就有了随机替换（Random replacement）的方法。

随机替换无需记录每个way的年龄信息，而是随机选择一个way进行替换。相比于LRU替换，随机替换发生缺失的频率会更高一些，但是随着Cache容量的增大，这个差距会越来越小。

实际设计很难做到严格的随机，一般采用时钟算法的方法来实现近似随机，其本质上是一个计数器，计数器的宽度由Cache的相关度，也就是way的个数来决定，例如8way就需要三位，每次当Cache中的某个line需要被替换时，就会访问这个计数器，使用计数器当前的值，从被选定的Cache set找出要替换的line，这样就近似实现一种随机替换。理论上其性能不是最优，但是它的硬件复杂度比较低，也不会损失过多的性能。

3. VIVT、PIPT、VIPT分类

CPU发出的地址是虚拟地址，要经过TLB或MMU转换成物理地址，最终从这个物理地址读写数据。cache的设计可以采用虚拟地址、物理地址、或者取两者地址部分组合来查找cache。

VIVT（Virtual Index Virtual Tag）：index和tag均使用虚拟地址；

PIPT（Physical Index Physical Tag）：index和tag均使用物理地址，一般用于L2 cache；

VIPT（Virtual Index Physical Tag）：index采用虚拟地址，tag采用物理地址，一般用于L1 cache（I-cache和D-cache）。

3.1 VIVT

使用虚拟地址寻址的cache称为虚拟cache。VIVT使用虚拟地址来寻址cache，如果cache hit，直接从cache中获得数据，不需要访问TLB；如果cache miss，则把虚拟地址发往TLB，使用TLB将VA转换成PA，然后使用PA去寻址 L2 Cache，从而得到缺失的数据（现代处理器中，L2及其下层的Cache都是物理Cache)。

虚拟cache的优点是不需要每次操作都把虚拟地址经过TLB转换为物理地址，这可以提升访问cache的速度，同时硬件设计也比较简单。但是使用了虚拟地址作为tag，引入很多软件使用上的问题，主要会面临两个问题：歧义(ambiguity)和别名(alias)。

3.2 PIPT

使用物理地址寻址的cache称为物理cache。由于tag和index都取自物理地址，物理的地址tag部分是独一无二的，而针对同一个物理地址，index也是唯一的，因此不存在歧义和别名的问题，这是PIPT最大的优点。CPU发出的虚拟地址先经过TLB转换成物理地址，然后使用物理地址来寻址cache。

3.3 VIPT

这种方式使用了虚拟Cache，根据Cache的大小，直接使用虛拟地址的—部分来寻址这个Cache(这就是virtually-indexed)，而在Cache 中的Tag则使用物理地址中的PFN(这就是physically-tagged)，这种Cache是目前被使用最多的，现代处理器的L1 cache（I-cache和D-cache）基本都使用这种方式。

VIPT以物理地址作为tag，因此不存在歧义问题。但是采用虚拟地址作为index，所以可能存在别名问题。