Linux内核2-Cache基本原理

1 Cache最小单位

主存和缓存之间以固定大小的块（block）为单位进行搬运，也就是每次从主内存读写的最小数据单元。每个块的大小可能是4，8，16字节或其它值，不同的CPU不尽相同。目前，X86架构和ARM架构都是采用64字节大小的块。通常，人们更习惯称这样的块为cache行，或者cache line。每个line除了包含数据之外，还包含TAG（地址信息）和状态信息。

2 关联方式

Cache的替换策略决定了主存中的数据块会拷贝到cache中的哪个位置，如果对于一块数据（大小为一个line），只有一个line与之对应，我们称之为直接映射；如果该数据块可以和cache中的任意一个line对应，则称之为全相联。而目前，更多的实现是采用N路相关联的方式，即内存中的某一块数据可能在cache中的N个位置出现，N可能是2，4，8，12，或其它值。

2.1 直接映射

这是一种多对一的映射关系。在这种映射方式下，主存中的每个数据块只能有一个line与之对应，因此直接映射也称为单路组相关联。在1990年代初期，直接映射是当时最流行的机制，Alpha的21064、21064A和21164的L1级的D Cache和I Cache都采用直接映射。它所需的硬件资源非常有限，每次对主存的访问都固定到一个指定的line，这种简单明了有一系列的好处，最大的优点是在200～300MHz CPU主频的情况下，Load-Use Latency可以快到只需要1个cycle！

一般地，缓存索引I，可以表示为：

I =（Am ÷ B）% N

其中, Am为内存地址，B为line大小，N为line的总数。

随着CPU主频的提高，Load-Use Latency也在相对缩小，直接映射方式的优势也就显得不那么明显。同时，成平方级别增长的主存容量使得cache的容量显得越来越小。

由于没有替换策略，主存的数据能存在哪个cache line根本没得选 ，这也意味着当两个变量映射到同一个line时，他们会不停地把对方替换出去。由于严重的冲突，频繁刷新cache将造成大量的延时，而且在这种机制下，如果没有足够大的cache，程序几乎无时间局部性可言。

如今直接映射机制正在逐渐退出舞台。

2.2 2路组相关联

一个2组2路相关联的如上图所示，cache分成s组，每组包含两个line，也称为两路，主存中的每个数据块只能位于s个组中的某一个，但可以在指定组中的任意一个line中。

AMD的Athlon的L1级cache所采用的就是这种2路组相联的映射方式。

2.3 N路组相关联

相对于2路组相联更通用的方式是N路组相关联：cache共分成s组，每组有N个line组成。

一般地，缓存索引I可以示为：

其中, Am为内存地址，B为cache line 大小， N表示每组含多少路数（ways），S为组数。

2.4 全相关联

全相联是组相关联的一个极端，这种映射关系意味着主存中的数据块可能出现在任意一个line中。这样，替换算法有最大的灵活度，也意味着可以有最低的miss率。但是，因为没有索引可以使用，检查一个cache是否命中需要在整个cache范围内搜索，这带来了查找电路的大量延时。因此只有在缓存极小的情况才有可能使用这种关联方式。

3 总结

主存和cache的关联方式的选择，是多种因素互相妥协的结果。比如某种替换策略使得一个主存数据块可以有10个line与之相对应时，处理器就必须想办法查找这10个位置，看看是否在其中某一个命中。越多的查找，意味着需要越大的功耗，越大的芯片面积，以及越长的时间；而从另一个角度来看则是，越多的对应项可已有越低的miss，也就需要花费更少的时间来等待数据从低速主存获取。

研究表明将路数N增大一倍，对于cache命中率的提升效果和增大一倍cache面积几乎相等。但是，当路数大于4以后，对于命中率的提高作用就不那么明显。而另一些研究则表明，就单级cache而言，8路组相关联的方式和全相联从miss率上来看效果相当。不少CPU采用了16路甚至32路组相联的关联方式，并不是单单为了降低miss率。

前大部分cache使用的都是N路组相联的方式。