什么是Cachecache有什么用说明cache的几种替换策略

Cache是什么

Cache是一种特殊的存储器，它由Cache 存储部件和Cache控制部件组成。Cache 存储部件一般采用与CPU同类型的半导体存储器件，存取速度比内存快几倍甚至十几倍。而Cache 控制器部件包括主存地址寄存器、Cache 地址寄存器，主存—Cache地址变换部件及替换控制部件等。至于它们各自又是怎样工作的、有何作用等等，我想我们就没有必要做进一步的研究，知道一般Cache分为L1 Cache(其中又分为数据Cache、代码Cache)、L2 Cache就行了。

根据程序局部性规律可知：程序在运行中，总是频繁地使用那些最近被使用过的指令和数据。这就提供了替换策略的理论依据。综合命中率、实现的难易及速度的快慢各种因素，替换策略可有随机法、先进先出法、最近最少使用法等。

1随机法（RAND法）

随机法是随机地确定替换的存储块。设置一个随机数产生器，依据所产生的随机数，确定替换块。这种方法简单、易于实现，但命中率比较低。

2先进先出法（FIFO法）

先进先出法是选择那个最先调入的那个块进行替换。当最先调入并被多次命中的块，很可能被优先替换，因而不符合局部性规律。这种方法的命中率比随机法好些，但还不满足要求。先进先出方法易于实现，例如Solar－16/65机Cache采用组相联方式，每组4块，每块都设定一个两位的计数器，当某块被装入或被替换时该块的计数器清为0，而同组的其它各块的计数器均加1，当需要替换时就选择计数值最大的块被替换掉。

3最近最少使用法（LRU法）

LRU法是依据各块使用的情况， 总是选择那个最近最少使用的块被替换。这种方法比较好地反映了程序局部性规律。

实现LRU策略的方法有多种。 下面简单介绍计数器法、寄存器栈法及硬件逻辑比较对法的设计思路。

计数器方法：缓存的每一块都设置一个计数器，计数器的 *** 作规则是：

(1) 被调入或者被替换的块， 其计数器清“0”，而其它的计数器则加“1”。

(2) 当访问命中时，所有块的计数值与命中块的计数值要进行比较，如果计数值小于命中块的计数值，则该块的计数值加“1”；如果块的计数值大于命中块的计数值，则数值不变。最后将命中块的计数器清为0。

(3) 需要替换时，则选择计数值最大的块被替换。

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的使用暂且不表。有问题欢迎留言讨论。

不是的，程序计数器(Program Counter, PC)不属于指令缓存（Instruction Cache）部分。

程序计数器是一个CPU中的寄存器，它的作用是记录当前执行到的指令的地址或位置。当CPU执行指令时，程序计数器会按照程序的逻辑顺序更新指令地址，以便后续执行下一条指令。

而指令缓存是处理器内部的一种高速缓存，主要用于存储最近使用的指令，以便尽可能快地引用和执行这些指令。指令缓存通常是每个CPU核心独立存在的，与程序计数器的作用不同，它是在执行指令时加速访问指令的存储单元，提高CPU性能的重要组成部分。

因此，程序计数器是CPU中与指令流程有关的寄存器，而指令缓存是一种用于存储指令的高速缓存。它们在CPU的不同部件中具有不同的作用和应用场景。

以上就是关于什么是Cachecache有什么用说明cache的几种替换策略全部的内容，包括:什么是Cachecache有什么用说明cache的几种替换策略、cache工作原理、如何编写100% cache miss的C程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！