CPU设计之Cache-数据放置策略

要让打胜仗成为一种信仰，没有退路就是胜利之路

--马丁·邓普西

Cache的数据放置策略

在讲cache的构成前，先要讲几个概念。首先，缓存的大小称之为cache size，其中每一个缓存行称之为cache line。Cache主要由两部分组成，Tag部分和Data部分。因为cache是利用了程序中的相关性，一个被访问的数据，它本身和它周围的数据在最近都有可能被访问，因此Data部分就是用来保存一片连续地址的数据，而Tag部分则是存储着这片连续地址的公共地址，一个Tag和它对应的所有数据Data组成一行称为cache line，而cache line中的数据部分成为数据块(cache data block，也称做cache block或data block)。如果一个数据可以存储在cache的多个地方，这些被同一个地址找到的多个cache line称为cache set。当CPU在读取缓存数据时，一个cache line的多字节会被同时读出。

假设我们现在的cache size是32KB，一个cache line是64Bytes。通过简单的除法我们就知道在cache中有512条cache line。假设我们的系统中地址宽度是32bit，当一个地址发下来，会用最低的6bits作为块内的偏移地址（offset），用较高的9bits作为cache索引地址（index），将其余的17bits地址作为标志位（tag）作为比对。

使用Index来从cache中找到一个对应的cache line，但是所有Index相同的地址都会寻址到这个cache line，因此在cache line中还有Tag部分，用来和地址中的Tag进行比较，只有它们相等才表明这个cache line就是想要的那个。在一个cache line中有很多数据，通过存储器地址中的Offset部分可以找到真正想要的数据，它可以定位到每个字节。在cache line中还有一个有效位(Valid)，用来标记这个Cache line是否保存着有效的数据，只有在之前被访问过的存储器地址，它的数据才会存在于对应的cache line中，相应的有效位也会被置为1。每个cache line中会有一个bit位记录数据是否被修改过，称之为dirty bit。

图1 cache组成结构示意图

上面的地址对应关系被称为直接映射（direct-mapped）。直接映射缓存在硬件设计上会更加简单，因此成本上也会较低。根据直接映射，我们可以画出主存地址与cache的对应关系如下图：

图2 直接映射的内存与cache对应关系

问题来了，如果CPU需要连续访问0x0000_0000，0x0001_0000，0x0002_0000地址，会发生什么呢？这三个地址的index位是一样的，tag位不同，因此对应的cache line是同一个。所以当访问0x0000_0000时，cache缺失，需要从主存中搬入数据（假设只有一级cache）；当访问0x0001_0000时，同样是cache缺失，需要从主存中搬入数据，替换掉cache中的上一条数据；当访问0x0002_0000时，依然cache缺失，需要从主存中搬入数据。这就相当于每次访问数据都要从主存中读取，所以cache的存在并没有对性能有什么提升。这种现象叫做cache颠簸（cache thrashing）。

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

图3 两路组相联cache

这种结构仍旧使用存储器地址的Index部分对cache进行寻址，此时可以得到两个cache line，这两个cache line称为一个cache set，究竟哪个cache line才是最终需要的，是根据Tag比较的结果来确定的，如果两个cache line的Tag比较结果都不相等，那么就说明这个存储器地址对应的数据不在cache中，也就是发生了cache缺失。上图所示为并行访问，如果先访问Tag SRAM部分，根据Tag比较的结果再去访问Data SRAM部分，就称为串行访问。

两路组相联缓存的硬件成本相对于直接映射缓存更高。因为其每次比较tag的时候需要比较多个cache line对应的tag（某些硬件可能还会做并行比较，增加比较速度，这就增加了硬件设计复杂度）。为什么我们还需要两路组相联缓存呢？因为其可以有助于降低cache颠簸可能性。

既然组相联缓存那么好，如果所有的cache line都在一个组内。岂不是性能更好？由于所有的cache line都在一个组内，因此地址中不需要set index部分。因为，只有一个组让你选择，间接来说就是你没得选。我们根据地址中的tag部分和所有的cache line对应的tag进行比较（硬件上可能并行比较也可能串行比较）。哪个tag比较相等，就意味着命中某个cache line。因此，在全相连缓存中，任意地址的数据可以缓存在任意的cache line中。所以，这可以最大程度的降低cache颠簸的频率。但是硬件成本上也是更高。