Cache entries

数据在主存和缓存之间以固定大小的”块（block）”为单位传递，也就是每次从main memory读取的最小数据的单元。每个块的大小可能是4，8，16 Bytes或其他值，不同的CPU不尽相同，目前的x86 CPU cache line基本都是64 bytes。通常，人们更习惯称之为cache行，或者cache line。根据前一篇文章的描述，每个cache line除了包含数据，还包含TAG（地址信息）和状态信息。

关联方式（Associativity）

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

直接映射

 

直接映射

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

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

I =（Am÷ B）mod N

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

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

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

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

2路组相联

 

2路组相连

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

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

N路组相联

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

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

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

全相联

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

小结

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

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

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

N路组相联的Cache结构

 

N 路组相连

如上图所示，一个cache line 分成两部分存储，RAT和Status状态位存储在CAM(Content Addressable Memory)中，以利于并行查找（Parallel search），相比较于串行查找（Sequential search），并行查找虽然可以获得较快的速度，但当Way数较多时，需要占用相当多的物理资源。目前大部分的架构中，数据字段一般采用多端口，多Bank的SRAM阵列。

CAM分NAND和NOR两种，NOR CAM使用并行查找，NAND CAM使用级联查找。随着每个cache line上包含的信息越来越多，使用NOR CAM时需要的功率越来越大，且由于实现方式的原因，路数越多会导致时延越大（参考4）；而NAND CAM采用一推一的方式，对功耗的要求较低。

CAM除了需要判断某一单元是否命中之外，就是查找电路的驱动问题，一个门电路的驱动能力和许多因 素有关，如电流、频率、介质等。提升驱动能力的方法有很多，如采用金属介质、适应多级驱动器，缩短走线距离等，但这些方法不是导致功耗变大，就是导致时延变长。当然还有人提出使用流水方式，使用更多的节拍来完成搜索，这显然和各大厂家努力在尽可能少的节拍内完成cache读写操作的目标相悖。种种原因使得现代处理器中L1 cache的关联路数不会太大。

目前大部分CPU采用的是2-Ways、4-Ways、8-Ways或者16-Ways组相联的方式，路数多为2的幂，以便于硬件的实现，当然也不是没有例外，个别CPU中就有10路或者12路的情况，出现这个现象的原因在于路数并非对。在一个外设中，CPU 和外设都可以访问主存储器，比如显卡或者各类PCIe设备。这些访问并不完全相同，多数情况下，CPU经过LSQ、FLC、MLCs之后通过LLC最终与主存交换数据，外设进行DMA访问时，直接面对的是LLC和主存储器，并对L1 cache产生间接影响。这些差异使得处理器中中LLC路数的构成是由若干而2的幂之和。

除了访问路线的不一致，另一个使得非对等路数的原因是为了降低miss 率。如Skewed-Associative cache（参考5）使用两种hash算法，分别映射一个组内的不同两路，这样可以在不增加组和路数的情况下有效降低miss率。

在某些情况下，cache miss导致的代价是无法忍受的，比如TLB miss，无论采用存软件还是硬件辅助的形式，miss导致的代价都过于昂贵，最终人们选择了全相联的实现方式。TLB的设计还必须对Hit time和Hit rate进行折中，应此TLB分成两级，L1-TLB的设计侧重于使Hit time小一些，其目标就是尽可能快；而L2则需要进一步考虑命中率问题，通常比较大，而且是采用N路组相联的方式。

参考1：《Phased set associative cache design for reduced power consumption》，链接

参考2：《Computer Architecture A Quantitative Approach》 David A. Patterson and John L. Hennessy [Jan. 2008]

参考3：《Cache Memories》 Alan Jay Smith [Sep. 1982], ACM Computing Surveys Volume 14 Issue 3.

参考4：《Cache Memory》 Wang Qi, Yang xi等 [Mar. 2010]

参考5：《A case for two-way skewed-associative caches》 Andre Séance [May. 1993]