早期计算机系统的存储器层次只有三层： CPU寄存器、DRAM主存储器和磁盘存储器。
随着CPU和主存储器之间的性能差距越来越大，系统设计者在CPU和主存储器之间逐渐添加了L1、L2、L3高速缓存。下面我们来看看Cache的结构以及如何工作：

1.Cache基本结构

一个cahce的组织可以由下面的包含4个参数的参数组来标识(S，E，B，m)，S是缓存组的数目（index），E是每个组的高速缓存行的数目（way），B是一个cache line中保存的数据块的字节数，m是物理地址的bit数据。

• 行（line）：高速缓存行是cache中最小的访问单元，包含一小段主存储器中的数据，常见的高速缓存行大小是32Byte或64Byte等。每行不仅有数据区域，处理器需要通过行内偏移量来访问每行中的数据，所以还需要偏移量（Offset）来定位行内位置，需要标记域（Tag）来知道本行缓存的是哪个内存地址，还需要其他的一些位来知道此行是否有效(即已经缓存了数据)。
  
• 地址编码：就是处理器访问高速缓存行的地址编码。分3个部分，分别是偏移量（Offset）、索引域（Index）、标记域（Tag）。
• 偏移量（Offset）：行内的偏移量，处理器可以按照字或者字节来寻址，比如一行32byte，偏移量就有5bit，可以定位到字节。
• 标记域（Tag）：行内的标记域，用于判断高速缓存行存放的数据是否和处理器想要的一致。也就是这一行对于的内存地址是多少，比如32位的内存地址，标记域为32-5=27。
• 索引域（Index）：用于索引某一高速缓存中的某一组。例如上图中可以索引4组缓存，Index就有2bit。
• 组（Set）：相同索引域（Index）的高速缓存行组成一个组，也就是使用Index来定位组号。
• 路（Way）：在组相联的cache中，cache被分成大小相同的几个块，每一块就是一路，每一组。
  高速缓存的结构很像一个三维结构，可以用zyx坐标轴定位来表示高速缓存中的字节，x轴对于行内偏移量，y轴对于某一路中的索引，z轴对应路号。

举例：
问题：一个32KB的4路组相联缓存，其中高速缓存行为32字节，请问这个高速缓存有多少行，多少路，多少组，参数组是多少？
答：高速缓存行数 32*1024 / 32 = 1024行 高速缓存路数为 4路 高速缓存组数为 1024 / 4 = 256 组
由于是组相联缓存，所以访问地址编码中的偏移量是 5bit（2^5 = 32字节），索引域为8bit（2^8 =
256组），标记域为19（32-5-8），物理地址可以访问的就是13bit（5+8）。
所以这个缓存的参数组为 (S,E,B,m) = (256,4,32,13)

2.Cache的工作方式

处理器访问主存储器使用地址编码方式。cache也使用类似的地址编码方式，因此处理器使用这些编码地址可以访问各级cache。
以VIPT（virtual Index phg sical Tag）的cache组织方式 举例：

处理器在访问存储器时，会把地址同时传递给TLB（Translation Lookaside Buffer）和cache。TLB是一个用于存储虚拟地址到物理地址转换的小缓存，处理器先使用EPN （effective page number）在TLB中进行查找最终的RPN（Real Page Number）。如果这期间发生TLB miss，将会带来一系列严重的系统惩罚，处理器需要查询页表。假设这里TLB Hit，此时很快获得合适的页帧号RPN，并得到相应的物理地址（Physical Address, PA）。

同时，处理器通过cache编码地址的索引域（Index）可以很快找到相应的组（Set）。但是这里的cache block的数据不一定是处理器所需要的，因此有必要进行一些检查，将cache line中存放的地址和通过虚实地址转换得到的物理地址进行比较。如果相同并且状态位匹配，那么就会发生cache命中（Cache Hit），那么处理器经过字节选择和偏移（Byte Select and Align）部件，最终就可以获取所需要的数据。如果发生cache miss，处理器需要用物理地址进一步访问主存储器来获得最终数据，数据也会填充到相应的cache line中。

高速缓存目前是由硬件自动管理的，也就是当处理器访问存储器的时候， 会自动去高速缓存中尝试获取，如果高速缓存中不存在此数据，就会读取内存，并把此内容之后的一个高速缓存行大小的数据存入高速缓存。刚开机时，由于高速缓存为空，此时高速缓存会出现大量的miss，直到高速缓存满了，当高速缓存满了以后，如果出现miss，就会采用替换策略，将已存入的某行替换掉。

3.Cache的映射方式

第一节的例子中提到了组相联缓存，组相联就是Cache的映射方式。我们采用第一节讲到的参数组的方式来几种方式：

参数组(S，E，B，m)，S是缓存组的数目（index），E是每组的高速缓存行的数目（way），B是一个cache
line中保存的数据块的字节数，m是物理地址的bit数据。

根据参数组中的E（每组的高速缓存行的数目），cache可以分成不同的类。

• 当每组只有一行cache line时，称为直接映射高速缓存；
• 当整个高速缓存只有一组高速缓存时，即E=C/B，则为全相联高速缓存，C为此高速缓存的总大小；
• 当每组的高速缓存行数E在这个范围内 1<E<C/B ，则为组相联高速缓存；

下面详细讲解这几种方式构造的缘由：

3.1 直接映射方式

当每个组只有一行cache line时，称为直接映射高速缓存。
举例：下面用一个简单小巧的cache来说明，这个cache只有4行cache line，每行有4个字（16byte），总大小是64byte。这个cache控制器可以使用两个比特位（bits[3:2]）来选择高速缓存行中的字，以及使用另外两个比特位（bits[5:4]）作为索引（Index），选择4个cache line中的一个，其余的比特位用于存储标记值（Tag）。

• cache命中
  当索引域和标记域的值和查询的地址相等，并且有效位显示这个cache line包含有效数据时，则发生cache命中，那么可以使用偏移域来寻址cache line中的数据。

• cache替换
  如果cache line包含有效数据，但是标记域是其他地址的值，那么这个cache line需要被替换。

• 问题
  在这个cache中，主存储器中所有bit [5:4]相同值的地址都会映射到同一个高速缓存行中，并且同一时刻只有一个高速缓存行，因为高速缓存行被频繁换入换出，会导致严重的高速缓存颠簸（cache thrashing）

3.2 组相联映射方式

直接映射高速缓存中出现颠簸的原因是源于每个组只有一行 这个限制，组相联映射方式则放松了这条限制，即每个高速缓存组都有超过1个的高速缓存行。
如下图所示，每组高速缓存有2行，所以每次当地址中的bits[5:4]相同时，就存在50%的不可能被替换。

• cache命中
  当索引域和标记域的值和查询的地址相等时，还要检查每组中的多个行标记域和有效位，确认在此组中则发生cache命中，那么可以使用偏移域来寻址cache line中的数据。

• cache替换
  当索引域和标记域的值和查询的地址相等，且该组中的所有高速缓存行都包含有效数据，那么这个组中的某个高速缓存行需要被替换，如何选择组中的哪一行，则需要看替换策略。

3.3 全相联映射方式

这是一种特殊的组相联高速缓存，在全相联高速缓存中，只有1个组，则访问的时候没有组索引域，地址就简单被划分为了标记域和偏移量。这样的高速缓存，每一页都可能被映射到任何一个高速缓存行中。

• cache命中
  全相联高速缓存和组相联高速缓存的命中条件是一样的，他们的主要区别是规模大小的问题，因为高速缓存电路必须并行的搜索许多相匹配的标记，因此构造一个又大又快的全相联高速缓存很困难且非常昂贵，因此全相联映射方式仅适用于做小的高速缓存，例如TLB，它用来页表项。

• cache替换
  当标记域的值和查询的地址相等，且所有高速缓存行都包含有效数据，那么就需要替换某个高速缓存行，如何选择组中的哪一行，则需要看替换策略。

4.新计算机体系之下的多层Cache结构

目前的计算机体系缓存至少有2层，越接近CPU越快，但是容量也越小。最接近CPU的是L1缓存，这里通常有2个L1缓存，icache和dcache，分别用来缓存处理器需要执行的指令和数据，这个通常是一个处理器一个，如果是多核处理器就是每个核心一个，最后一个级别的缓存（这里是L3）通常是在所有核心之间共享使用，而中间其他级别的缓存要看具体的芯片设计。
例如：ARM Cortex-A53 就使用的是3层cache结构，由于cortex-v8将多个核心之间还分了组(cluster)，所以其将L2设计为核心组之间共享，也就变成了如下结构：

下表总结了ARM几种系列的多级高速缓存架构：

5.cache的类型——VIVP和PIPP

5.1 VIVT

即使用虚拟地址的索引域和虚拟地址的标记域，相当于虚拟高速缓存；
这种实现方式查找速度很快，直接和CPU连接。硬件实现也比较简单，直接在处理器和TLB之间添加缓存即可。
但是使用虚拟地址存在2个问题。

• 重名问题（aliasing）：即多个不同的虚拟地址映射到相同的物理地址；一个物理地址在缓存中存放了2份数据，还会产生歧义。这个问题只要是使用了虚拟地址就解决不了。
• 同名问题（homonyms）：即同一个虚拟地址被映射到不同的物理地址。
  解决办法：在进程切换的时候，将旧进程遗留下来的cache全部清空。因为新进程需要使用另一套页表，所以同样要使TLB无效。

5.2 VIPT

使用虚拟地址的索引域和物理地址的标记域。即利用虚拟地址索引 Cache 的同时，利用 TLB/MMU 将虚拟地址转换为物理地址。然后将转换后的物理地址与虚拟地址索引到的 Cache line 中的 Tag 作比较，如果匹配则命中。

这种方式的硬件设计比VIVT更加复杂。

这种方式由于使用物理地址作为匹配规则，不会存在同名问题，但是由于使用了虚拟地址的一部分，所以仍存在同名问题。

5.3 PIPT

使用物理地址的索引域和虚拟地址的标记域，相当于物理高速缓存；
这种方式由于完全使用物理地址做高速缓存，因此可以解决重名问题和同名问题。
但是硬件设计更加复杂，必须在TLB之后增加缓存，且读取缓存的速度相较于 VIPT 慢。
现在大多数的缓存都是采用PIPT。

6.关键问题

6.1 Cache是如何存入和写出的？

系统刚刚启动的时候，cache是空的，这个时候是怎么存入内存数据的呢？
当处理器读取或者写入内存时，就会将对于内存数据加入高速缓存，这其实是通过硬件实现的，比如ARM指令集中的内存读写指令 ldr和str，就会触发相关的操作。
每次存入一个高速缓存行的大小，如果读取内容比较多，就会继续存入，直到缓存满，这个比较简单。

但是CPU要改写Cache时，何时写入内存，则是由2种策略：

• 直写模式：当CPU写入cache之后，立刻就会写入内存，这种方式比较简单；
• 回写模式：当CPU写入cache之后，不会立刻写入内存，而是当高速缓存行要被换出的时候才写入内存，这种方式比较复杂，但是会减少总线的带宽；

6.2 Cache满了怎么办？——cache替换算法

在采用全相联映射和组相联映射方式时，如果cache已满，且有新的数据载入的话，就要采用替换算法置换 高速缓存行。
目前有如下4种：

1. 随机算法（RAND）：随机地确定替换的高速缓存行。由一个随机数产生器产生随机数来确定替换行，实现简单，但没有依据程序访问的局部性原理，故命中率较低。
2. 先进先出算法（FIFO）：选择最早调入的行进行替换。它比较容易实现，但也没有依据程序访问的局部性原理，故命中率也较低。
3. 近期最少使用算法（LRU）：选择近期内长久未访问过的高速缓存行作为替换的行，主要通过对每行设置计数器来实现，充分考虑了局部性原理。

目前使用较多的是LRU算法，比如Cortex-A72的一级缓存采用LRU算法，二级缓存采用伪随机算法或伪LRU算法。

6.3 多级缓存工作机制

面对有多个层级的cache，如何管理呢？
这里有一个关键疑问：L1缓存的数据是否一定要在L2里面？
根据这个问题，其实有多个方式：

• exclusive：L1 cahce中的内容不能包含在L2中
  exclusive方式可以存储更多数据。当然如果L2大大超过L1的大小，则这个优势也并不是很大了。
• strictly inclusive：L1cache的内容一定严格包含在L2中。
• Third one（没有正式名字）:不要求L1的一定包含在L2中
  目前实现大部分都是使用strictly inclusive模式：
  

6.4 cache和内存如何保持一致性

我们知道，cache有很多层，而且各个处理器核心都有各自独立的cache，如果不同的处理器核心之间可能会缓存相同的内存数据，所以，如果不同的cache中缓存了相同的数据，这些cache数据如果各自修改之后是否存在数据冲突。
这是每个处理器都会遇到的事情，这里讲述最新的解决方式——MESI 协议。
MESI 协议将每个缓存的高速缓存行设置了4种状态：

• M：代表已修改（Modified）
• E：代表独占（Exclusive）
• S：代表共享（Shared）
• I：代表已失效（Invalidated）
  每次对该行进行的读写操作就要进行状态转换，只有出现了读写数据时，都会在总线上发送命令，通知其他CPU对cache进行相应的处理。

6.5 Cache伪共享问题

由于内存和Cache之间的交换单位是高速缓存行，因此如果访问一个变量，会将一整个内存块读入一个高速缓存行。所以有可能出现多个CPU访问的同一个高速缓存行中的不同变量。在MESI协议的约束下，多个CPU在各自使用的时候，会去通知其他CPU更新该数据，这样导致多个CPU竞争使用一个高速缓存行，导致程序性能下降。这就是伪共享问题。
如何解决呢？——高速缓存行填充或高速缓存行对齐。
也就是对可能存在共享的变量，尽可能的使用一整个高速缓存行，就能尽可能的避免多个CPU竞争使用的情况。

6.6 Cache的性能指标

有许多性能指标来衡量高速缓存的性能。

• 命中率：在一个程序执行过程期间，存储器引用的命中的比率；
• 命中时间：从高速缓存传送一个字到CPU的时间；
• 不命中处罚：由于不命中所需要的额外时间。L1从L2得到服务通常是10个周期，从L3读取是40周期，直接从主存读取是100个周期。

6.6 是否处理器每次读取内存都要通过cache

当cache没有命中的时候，CPU会直接去从内存里面拿数据，然后通知cache控制器，将这边数据加入缓存，这样下次使用的时候就可以直接从cache中拿数据了。

6.7 进程/线程 切换对cache的影响

进程切换之后，处理器需要做2件事情：

1. 切换页目录以使用新的地址空间
2. 切换内核栈和硬件上下文

线程和进程的最大区别就在于地址空间，对于线程切换，第1步是不需要做的，第2是进程和线程切换都要做的。
所以：

• 进程切换会导致虚拟地址空间的切换，这会导致TLB清空，然后还会导致上个进程使用的内存全部要重新加载到cache中，因此进程切换的成本较高。
• 线程切换不会切换虚拟地址空间，再加上可能会使用相同的全局变量，高速缓存并不会完全无效清空，因此成本较小。

6.8 如何查询CPU的cache信息

1. lscpu 就会打印出cpu各级缓存的信息
   
2. /sys/devices/system/cpu/cpu0 查看详细信息
   

/sys/devices/system/cpu/cpu0/cache/index0/size
size表示查看当前缓存的大小

/sys/devices/system/cpu/cpu0/cache/index0/number_of_sets
number_of_sets表示查看当前缓存的组数

/sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity
ways_of_associativity 表示查看一组块的数目

/sys/devices/system/cpu/cpu0/cache/index0/type
查看类型是否是区分指令与数据的

/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
查看高速缓存行的大小

3.查看高速缓存行的大小

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

从上面我们的各种分析，我们清楚了，高速缓存是处理器通过硬件操作的，软件并不能直接操作cache，那么我们需要去使用它的时候，如何注意提高它的使用效率呢？
核心的原理是要有优秀的局部性，局部性好的程序，容易有更好的性能。
确保代码高速缓存友好的基本方法：

1. 让最常见的情况运行得快. 程序通常把大部分时间都花在少量的核心函数上，而这些函数通常把大部分时间都花在了少量的循环上。所以要把注意力集中在核心函数的循环上，而忽略其他部分。
2. 尽量减少每个循环内部的缓存不命中数量.在其他条件相同的情况下，不命中率较低的循环运行得更快。

举例：
假设高速缓存行的大小是32字节，32位CPU。
二位数组求和，一种是按行遍历，一种是按列遍历：

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

按行遍历的缓存命中情况：

a[i][j]	a[i][0]	a[i][1]	a[i][2]	a[i][3]	a[i][4]	a[i][5]	a[i][6]	a[i][7]	a[i][8]	a[i][9]	a[i][10]	a[i][11]	a[i][12]	a[i][13]	a[i][14]	a[i][15]
a[0][j]	miss	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit
a[1][j]	miss	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit
a[2][j]	miss	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit
a[3][j]	miss	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit	hit

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

按列遍历的缓存命中情况：

a[i][j]	a[i][0]	a[i][1]	a[i][2]	a[i][3]	a[i][4]	a[i][5]	a[i][6]	a[i][7]	a[i][8]	a[i][9]	a[i][10]	a[i][11]	a[i][12]	a[i][13]	a[i][14]	a[i][15]
a[0][j]	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss
a[1][j]	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss
a[2][j]	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss
a[3][j]	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss	miss

i, j, sum这种变量，编译器都会优化在寄存器中的，所以效率比较高。
如果此高速缓存行大小为64字节，则能容纳16个整型。
通过上面的命中率分析可以看出来：
按照内存方向顺序遍历是对高速缓存更友好的程序。

参考文献