缓存的相关概念

cache在计算机组织结构中很重要，理解cache对编写性能友好的程序很有帮助。

1. Cache的历史

在科研领域，C. J. Conti等人于1968年在描述360/85和360/91系统性能差异时最早引入了高速缓存（cache）一词。Alan Jay Smith于1982年的一篇论文中引入了空间局部性和时间局部性的概念。

Mark Hill在1987年发明了3C（Compulsory, Capacity, Conflict）冲突分类。

最早介绍非阻塞缓存的论文之一来自David Kroft（1981年）。

1990年Norman Paul Jouppi在一篇论文中介绍了受害者缓存并研究了使用流缓冲器进行预取的性能。

在工业领域，最早的有记载的缓存出现在IBM的360/85系统上。

Intel的x86架构CPU从386开始引入使用SRAM技术的主板缓存，大小从16KB到64KB不等。486引入两级缓存。其中8KBL1缓存和CPU同片，而L2缓存仍然位于主板上，大小可达268KB。将二级缓存置于主板上在此后十余年间一直设计主流。但是由于SDRAM技术的引入，以及CPU主频和主板总线频率的差异不断拉大，主板缓存在速度上的对内存优势不断缩水。因此，从Pentium Pro起，二级缓存开始和处理器一起封装，频率亦与CPU相同（称为全速二级缓存）或为CPU主频的一半（称为半速二级缓存）。

AMD则从K6-III开始引入三级缓存。基于Socket 7接口的K6-III拥有64KB和256KB的同片封装两级缓存，以及可达2MB的三级主板缓存。
今天的CPU将三级缓存全部集成到CPU芯片上。

多核CPU通常为每个核配有独享的一级和二级缓存，以及各核之间共享的三级缓存。

2. 什么是Cache

字面上理解就是，cache是一个硬件或软件的组件用来存储将来会请求到的数据，而且能让数据获取更快。因为如今缓存的概念已被扩充，不仅在CPU和主内存之间有Cache，而且在内存和硬盘之间也有Cache（磁盘缓存），乃至在硬盘与网络之间也有某种意义上的Cache──称为Internet临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构，均可称之为Cache。

• 硬件的cache：CPU cache，GPU cache，DSP（数字信号处理器）；

• 软件的cache：Disk Cache，Web Cache，数据库的Cache等。

  
  image.png

image.png image.png
image.png

3. 缓存命中和不命中

缓存命中

在存储器层次结构中，假设层次从上到下是增序排列，假设一个k值，当程序需要第k+1层的某个数据对象d时，它首先在第k层的一块中查找d，如果d刚好缓存在k层中，就是缓存命中(cache hit).
显然从k层读取数据是要比k+1层速度快很多的。

缓存不命中

当在k层找不到数据d时，我们就称k层缓存不命中(cache miss)。当发生缓存不命中的时候，第k层缓存从第k+1层缓存中取出包含d的那个块，如果k层缓存满了，就会覆盖现有的块。
覆盖一个现存的块的过程称为替换(replacing)或驱逐(evicting)这个块。被驱逐的块称为牺牲(victim)块。关于替换哪个具体的块是由替换策略来控制的。比如随机替换策略，或最少最近被使用策略(LRU)。

缓存不命中的种类

• 强制不命中或冷不命中：这种不命中是由于缓存是空的，它通常是短暂的，不会在反复访问存储器的过程中出现。

  
  image.png
  image.png

• 冲突不命中：这种缓存是由于放置策略引起的。如下图所示，放置如果程序请求0，然后8，然后0，然后8，在k层缓存中对这两个块的每次引用都不会命中，即便k层有4个缓存块

  
  image.png
• 容量不命中：当工作集的大小超过了缓存的大小的时候，不能处理这个工作集，就会发生容量不命中。

高速缓存存储器(SRAM)层级

• L1（一级缓存）：一般与处理器同片封装，访问速度几乎和寄存器一样快，通常是2-4个时钟周期，大小为8KB-128KB
• L2（二级缓存）：可以在chip中也可以在外部，访问速度大约是是10个时钟周期，大小为64KB-8MB
• L3（三级缓存）：在chip外部被多核处理器共享，访问速度大约是30～40个时钟周期，大小为4MB-128MB
• L4（四级缓存）：cc-NUMA集群系统的远程cache，大小比L3缓存大（大于512MB).

4. 高速缓存结构

一般而言，高速缓存的结构可以用元组(S, E, B, m)来表示，缓存大小C=B×E×S。如下图所示，每个存储器有m位，一个机器的高速缓存是一个有S个高速缓存组（cache set）的数组，每个组包含E行高速缓存行（cache line），每个行由一个B字节的数据块，一个有效位（valid bit）表示这个行是否有有意义的信息，t个（t=m-(b+s)）标志位（用于标识存储在这个高速缓存块中的位置）组成。

image.png
image.png
image.png

假设我们有这样一个系统,它有一个CPU、一个寄存器文件、一个L1高速缓存和一个主存。当CPU执行一条读内存字w的指令,它向L1高速缓存请求这个字。如果L1高速缓存有w的一个缓存的副本,那么就得到L1高速缓存命中,高速缓存会很快抽取出,并将它返回给CPU。否则就是缓存不命中,当L1高速缓存向主存请求包含w的块的一个副本时,CPU必须等待。当被请求的块最终从内存到达时,L1高速缓存将这个块存放在它的一个高速缓存行里,从被存储的块中抽取出字w,然后将它返回CPU。高速缓存确定一个请求是否命中，然后抽取出被请求的字的过程分为：

• 组选择
• 行匹配
• 字抽取

人们根据E(每个组的行数)的不同把高速缓存分成不同类，主要有

（1） 直接映射高速缓存(Direct Mapped cache)

image.png
组选择
image.png
行匹配
image.png
字选择
image.png
行替换
image.png
总结来说就是以下步骤：

• 组选择：根据s位组索引位选择出组；
• 行匹配：确定是否有字w的拷贝存储在组的高速缓存行中，当设置了有效位，并且行中的标记与w的地址中的标记相匹配的时候，我们认为这一行包含w的一个拷贝。因为每个组只有一行，所以很快就可以完成。如果找到了就是命中，反之不命中。
• 如果不命中要进行行替换
• 取出数据块

一个示例

image.png
image.png
image.png
image.png
冲突不命中
image.png
image.png
image.png
中间位索引的意义
image.png
image.png
image.png

（2） 组相联高速缓存(Set Associative cache)

image.png

组选择

同直接映射高速缓存的组选择过程。

行匹配和字选择

image.png
image.png

行替换

image.png
关于行替换更多详细内容后面替换策略部分会讲解

（3）全相联高速缓存(Fully Associative cache)

全相联高速缓存的条件是E=C/B，也就是缓存只有一组，组中包含E行。这样的相联完全免去了索引的使用

image.png
组选择
image.png
行匹配和字选择
image.png

（4）三种方式的性能总结

每次CUP所访问的单元在cache中，则命中，命中的概率为p，命中时CPU在cache中直接存取信息，所用时间开销称为命中时间，其值为cache访问时间，缺失时需要从主存读取一个主存块，同时将所需信息送入CPU，所用时间开销称为主存访问时间与cache访问时间之和

CPU在cache-主存的平均访问时间为：

由于程序访问的局部性特点，cache命中率p在80%以上甚至接近于1，即便主存访问时间远大于cache访问时间，然而最终平均访问时间接近于cache的访问时间

在以上基础上，对三种映射方式作出总结：

• 直接映射的优点是容易实现，命中时间短，但当多个块映射到同一cache行时，访问又引发不停地抖动时，即便别的cache行都空闲，也会引起频繁的调进调出，也就导致了命中率较低
• 全相联映射下，只要有空闲cache行，就不会引发冲突，因而块冲突概率低，但时间开销和原件开销大，实现困难，只适合小容量的cache
• 组相联映射结合前两者的优点，冲突概率比直接映射低，同时在开销上比全相联映射小，速度也很快

5. 缓存策略

在缓存的读写操作中，有不同的策略来指导操作的顺序以及位置。

（1）替换策略

当新的一个主存块复制到cache时，cache对应的组（如果有的话）包含的行可能已经被全部占满，此时必须淘汰掉一个cache行。直接映射的行替换因为只有一行，所以直接替换就可以了，但另外两种映射的行替换有以下几种方式：

• FIFO - First-In First-Out：先进先出算法，总是选择最早装入cache的缓存行将其替换。其算法实现方便，但不能正确反映程序的访问局部性，通常用于组相联高速缓存。
  

  image.png

• LRU - Least Recently Used：最近最少用算法，总是选择近期最少使用的缓存行，可以正确反映程序的访问局部性，这个缓存算法将最近使用的条目存放到靠近缓存顶部的位置。当一个新条目被访问时，LRU将它放置到缓存的顶部。当缓存达到极限时，较早之前访问的条目将从缓存底部开始被移除。这里会使用到昂贵的算法，而且它需要记录“年龄位”来精确显示条目是何时被访问的。此外，当一个LRU缓存算法删除某个条目后，“年龄位”将随其他条目发生改变。通常用于组相联高速缓存。
  

  image.png

• LFU – Least Frequently Used:最不经常使用算法，这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法，最低访问数的条目首先被移除。这个方法并不经常使用，因为它无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责。

  
  image.png
• Random：随机策略算法，从候选行中随机选取一个替换掉，与使用情况无关，其性能一般，但代价很低。

以上几种替换策略也会应用在数据库的缓存比如Redis中，对以上算法实现的java代码展示，见

（2） 回写策略

cache的回写策略决定怎么把cache的数据写到内存的位置中去。当发生回写时，由于cache的内容是部分主存块的副本，因此当CPU进行写操作需要对cache中的内容进行更新，就要考虑cache和主存的数据一致性问题，此外以下情况也会出现一致性问题：

• 当多个设备都允许访问主存时。例如磁盘类的高速I/O设备可以通过DMA方式直接与主存交换数据，如果cache中的内容被CPU修改而主存块没有更新，则从主存传送到I/O设备的内容就无效；同样的，当I/O设备修改了主存块的内容，则对应（如果有的话）cache行的内容将就无效
• 当多个CPU都带有各自的cache而共享主存时。在多CPU系统，如果某个CPU修改了自身cache的内容，则对应的主存块和其他CPU对应的cache行的内容都变为无效

未解决一致性问题，通常采用如下两种写操作方式：

1. 通写（write through）

通写是指，每当CPU执行写操作时，若写命中，则同时写cache和主存，若写不命中，则分为两种方式：写分配法，更新主存，同时将更新的主存块放入cache中；非写分配法，仅更新主存，不对cache做操作。前者开销更大，但也充分利用了空间局部性。

由于通写会引发造成大量写内存操作，有必要设置一个缓冲来减少硬件冲突。这个缓冲称作写缓冲器（Write buffer），采用FIFO队列，通常不超过4个缓存块大小。在写操作不频繁发生时性能不错，但在写操作频繁发生时则会因为写缓冲饱和而发生阻塞。

通写较写回易于实现，并且能更简单地维持数据一致性。

2. 回写（write back）

回写是指，仅当写不命中，也就是一个缓存块需要被替换回内存时，才将其内容写入内存。如果写命中，则总是不用更新内存。为了减少内存写操作，缓存块通常还设有一个脏位（dirty bit），用以标识该块在被载入之后是否发生过更新。如果一个缓存块在被置换回内存之前从未被写入过，则可以免去回写操作。回写的优点是节省了大量的写操作。这主要是因为，对一个数据块内不同单元的更新仅需一次写操作即可完成。这种内存带宽上的节省进一步降低了能耗，因此颇适用于嵌入式系统。

但由于回写没法同步更新cache和主存的内容，所以有内容不一致的潜在隐患，需要其他同步机制保证存储信息的一致性。

3. 总结

对试图编写对高速缓存友好的程序来说,我们建议在心里采用一个使用写回和写分配的高速缓存的模型。这样建议有几个原因。通常,由于较长的传送时间,存储器层次结构中较低层的缓存更可能使 用写回,而不是通写。例如,虚拟内存系统(用主存作为存储在磁盘上的块的缓存)只使用写回。但是由于逻辑电路密度的提高,写回的高复杂性也越来越不成为阻碍了,我们在现代系统的所有层次上都能看到写回缓存。所以这种假设符合当前的趋势。使用写回写分配方法的另一个原因是,它与处理读的方式相对称,因为写回写分配试图利用局部性。 因此,我们可以在高层次上开发我们的程序,展示良好的空间和时间局部性,而不是试图为某一个存储器系统进行优化。

6. 如何编写高速缓存友好的代码

当明白了高速缓存的原理后，我们在编程的过程中应该试着去编写高速缓存友好的代码。什么样的代码算是高速缓存友好的代码？局部性比较好的程序往往有更高的缓存命中率，而缓存命中率更高，代码运行的速度就更快。确保代码高速缓存友好的方法有：

让最常见的情况运行得快。

1. 程序通常大部分时间都在少量的核心函数上，而核心函数大部分时间都花在循环上面，让这些循环执行得快一点是我们需要关注的地方。
2. 在每个循环内部缓存不命中率数量小。在其他条件（加载和存储的次数）相同的情况下，不命中率较低的循环运行的更快。

举个经典的二维数据相加求和的例子：

int colsarray(int a[M][N])
{
    int i,j,sum=0;
    for(i = 0; i<N; i++)
        for(j = 0; j<M; j++)
            sum += a[i][j];
    return sum;
}

这个程序中内循环遍历行，外循环遍历列，一列一列地扫描过来，而由于缓存从内存中抓取的几乎都是同行不同列的数据，在接下来的循环中几乎没法被重负利用。如果只是做个小改动,把内外循环交换一下

int rowsarray(int a[M][N])
{
    int i,j,sum=0;
    for(i = 0; i<M; i++)
        for(j = 0; j<N; j++)
            sum += a[i][j];
    return sum;
}

这样如果a[i][0]失效，从内存中抓取的数据实际上包括了a[i][0]-a[i]7,这样后面7次循环缓存都可以命中。大大提高了缓存命中率。在实际的运行过程中，第二种的程序比第一种快2倍。