cache工作原理

cache工作原理

cache是干啥的？

在以前，CPU的主频比较慢，CPU和内存DRAM之间速度差别不是很大，存储数据或者指令还OK。但是CPU的飞速发展，CPU大哥速度已经飞快，而内存速度却跟不上大哥的步伐，所以大哥每次要读取或者写入内存的时候都要等一等小弟，这个时候怎么办。cache就出来了，它类似与一个第三方。位于内存和CPU之间，速度非常快，所以CPU就把数据直接写入cache，然后CPU就可以干其他的了，剩下的事情就交给cache这个跑腿的，cache在合适的时机可以慢慢的把数据写入内存，也就是相当于解了CPU的燃眉之急。

说白了，CPU要读数据首先是在cache中读，如果cache命中，也叫cache hit，CPU就可以极快的得到该地址处的值。如果cache miss 也就是没有命中，它就会通过总线在内存中去读，并把连续的一块单元加载到cache中，下次好使用。

cache大多是SRAM（静态RAM），而内存大多是DRAM（动态随即存储）或者DDR(双倍动态随机存储)。

cache容量一般非常小，因为价格贵，所以cache小是有道理的。一级cache一般就几KB，cache 的单位又分成cache line ，它是从内存单元加载到cache中的最小单元，一般为几个字大小，32字节或者64字节偏多。（因为时间局部性和空间局部性所以加载一次是以一个cache单元为最小单位）

cache有两种模式（写回模式） 和 （写通模式）

简单介绍，写通也就是当CPU写入cache的时候，将数据再从cache 中写到内存中，这两个过程要都结束后，CPU的写入 *** 作才算完成，也就是时刻保持内存和缓存的同步，这显然是很耗时的。

什么是多级cache？

一级cache 有指令cache和数据cache之分，这使整个系统更加高效，因为1Lcache 容量小，所以有了多级cache ，比如二级cache ，他容量大，但是速度就要比1Lcache 慢些，但比内存快多了。三级cache就更m慢一些了。

写回也就是当CPU写入cache中的时候，数据不会马上从cache中写到内存里面，而是等待时机成熟后写入（比如 发生cache miss，其他内存要占用该cache line的时候将该单元写回到内存中，或者一定周期后写入到内存中 ，或者其它地核需要读取该内存的时候）。

内存写入cache的时候，如果cache 满了，则用一定的算法淘汰，比如随机淘汰还有或者LRU淘汰(用的少的被淘汰 常用)来替换掉原来的cache line 单元。

缓存(cache)大小是CPU的重要指标之一，其结构与大小对CPU速度的影响非常大。简单地讲，缓存就是用来存储一些常用或即将用到的数据或指令，当需要这些数据或指令的时候直接从缓存中读取，这样比到内存甚至硬盘中读取要快得多，能够大幅度提升cpu的处理速度。

CPU与cache之间的数据交换是以”字”为单位，而cache与主存之间的数据交换是以”块”为单位，一个块由若干字组成，是定长的，以体现”保存下级存储器刚才被存取过的数据及其邻近小范围的数据”这一概念。

CPU进行存储器读 *** 作时，根据主存地址可分成命中和未命中两种情况。对于前者，从Cache中可直接读到所需的数据；对于后者，需访问主存，并将访问单元所在的整个块从内存中全部调入Cache，接着要修改Cache标记。若Cache已满，需按一定的替换算法，替换掉一个旧块。

二级缓存（L2 CACHE）出现是为了协调一级缓存与内存之间的速度。最初缓存只有一级，后来处理器速度又提升了，一级缓存不够用了，于是就添加了二级缓存。二级缓存是比一级缓存速度更慢，容量更大的内存，主要就是做一级缓存和内存之间数据临时交换的地方用。“L1级Cache-L2级Cache-主存”这种层次从工作原理上讲与前述的Cache工作原理是完全相同的，即CPU首先访L1级Cache，若不命中，再访问L2级Cache和主存。

当CPU试图读取主存一个字时，发出此字内存地址同时到达cache和主存，此时cache控制逻辑依据地址的标记部分进行判断此字当前是否在cache中。若是（命中），此字立即递交给CPU，若否（未命中），则要用主存读取周期把这个字从主存读出送到CPU，与此同时把含有这个字的整个数据块从主存读出送到cache中。由于程序的存储器访问具有局部性，当为满足一次访问需求而取来一个数据块时，下面的多次访问很可能是读取此块中的其它字。

cache读 *** 作流程png

今天为了做ppt讲解如何使用oprofile（以测试cache miss为例），要写一个cache miss的小例子，以Level 2 data cache为例，具体步骤见下文。

1、查看你的系统cache大小：

$ cat /sys/devices/system/cpu/cpu0/cache/index2/size

我的系统是centos 58。以上命令是查看Level 2cache的大小，在我的服务器上是256k，记住这个数，写程序时要用。

2、查看cache line的大小：

$ cat /sys/devices/system/cpu/cpu0/cache/index2/coherency_line_size

我的服务器上是64，单位是bytes，记住这个数，也要用到。

3、编写测试程序cachec：

[cpp] view plaincopyprint

int matrix[8192][16]; //4819216=2^18=512k bytes

void bad_access()

{

int k, j, sum = 0;

for(k = 0; k < 16; k++)

for(j = 0; j < 8192; j++)

sum += matrix[j][k];

}

int main()

{

int i;

for(i = 0; i< 5000000; i++)

bad_access();

return 0;

}

以上代码虽然简单，但要理解需要懂cache的简单结构及原理：cache是以64字节或者128字节为一行的，分为多组（或者叫多路），每次发生cache miss取数据时，cache会按照cache line为单位（这里也就是一次取64字节）从内存取数据。

第一步得知level 2 data cache总大小是256k，第二步得到每个cache line是64字节，所以，level2 data cache共256k/64=2^12=4096行。

想象一个表，每行64字节，一共4096行，共256k大小，这就是我们cache的简单结构。为了保证每次取数据都会发生miss，我们必须以>=64字节的步长取数据。

首先创建一个512K大的数组，要比cache大一倍。如果数组也是256k，当第一次循环结束，数组用完后再次从头开始取数据时，cache就不再被替换，所以不会再发生cache miss，为了保证每次取数据都要发生cache miss，数组必须至少是cache大小的两倍及以上。

循环读取数组中的数据，每次读一个int大小，然后加64，再读取下一个cache line的数据，循环直到数组数据全部取出。

oprofile统计cache miss有个最低限制（我的098版本是2000000次），所以发生的miss数太小的话是娶不到的，所以加大循环次数至5000000。

4、至此可以进行100% cache miss的测试了，但是经过测试发现 cache miss压根没发生，百思不得其解，请教boss后才想起来，x86有个stream buffer硬件预取器，如果你取数据非常规律，那么硬件预取器经过训练后，会在你真正取数据之前，将你要的数据直接放到cache中。所以，要在至强处理器的服务器上做cache miss测试，必须重启系统后，关闭硬件预取器。否则就要修改程序，写出真正随机取数据的代码，但是这无法保证cache miss 率是100%，只能保证cache 命中率比较低而已。

5、SPEC CPU2006中的mcf发生cache miss rate很高，可以用其做测试。

oprofile的使用暂且不表。有问题欢迎留言讨论。

所谓缓存，就是将程序或系统经常要调用的对象存在内存中，一遍其使用时可以快速调用，不必再去创建新的重复的实例。这样做可以减少系统开销，提高系统效率。缓存机制的实现有很多中，这里讲一种。

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

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

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

相对于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路组相联的方式。

如上图所示，一个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]

以上就是关于cache工作原理全部的内容，包括:cache工作原理、如何编写100% cache miss的C程序、java 中常用缓存cache机制的实现 程序启动自动加载时怎么实现的等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！