Cache原理

cache line（缓存行） 是缓存进行管理的最小存储单元，也叫缓存块，每个 cache line 包含 Flag、Tag 和 Data ，通常 Data 大小是 64 字节，但不同型号 CPU 的 Flag 和 Tag 可能不相同。从内存向缓存加载数据是按整个缓存行加载的，一个缓存行和一个相同大小的内存块对应。

Cache设计需要考虑的问题

Cache索引方式

Cache的容量远小于内存，会涉及多个内存单元映射到同一个Cache单元的情况，具体怎么映射需要考虑。通常分为3种索引方式：直接相连、全相连和组相连。

Cache与下一层存储的数据关系

从缓存和内存的更新关系来看，分为：

• 写回（write-back） 对缓存的修改不会立刻传播到内存，只有当缓存行被替换时，这些被修改的缓存行才会写回并覆盖内存中过时的数据。
• 写直达（write through） 缓存中任何一个字节的修改，都会立刻穿透缓存直接传播到内存，这种比较耗时。

从写缓存时 CPU 之间的更新策略来看，分为：

• 写更新（Write Update） 每次缓存写入新的值，该核心必须发起一次总线请求，通知其他核心更新他们缓存中对应的值。

  • 坏处：写更新会占用很多总线带宽；
  • 好处：其他核心能立刻获得最新的值。

• 写无效（Write Invalidate） 每次缓存写入新的值，都将其他核心缓存中对应的缓存行置为无效。

  • 坏处：当其他核心再次访问该缓存时，发现缓存行已经失效，必须从内存中重新载入最新的数据；
  • 好处：多次写操作只需发一次总线事件，第一次写已经将其他核心缓存行置为无效，之后的写不必再更新状态，这样可以有效地节省核心间总线带宽。

从写缓存时数据是否被加载来看，分为：

• 写分配（Write Allocate） 在写入数据前将数据读入缓存。当缓存块中的数据在未来读写概率较高，也就是程序空间局部性较好时，写分配的效率较好。
• 写不分配（Not Write Allocate） 在写入数据时，直接将数据写入内存，并不先将数据块读入缓存。当数据块中的数据在未来使用的概率较低时，写不分配性能较好。

Cache的替换策略

分为随机替换、LRU替换和FIFO替换。当发生Cache失效而需要取回想要的Cache行，此时如果Cache满了，则需要进行替换。进行Cache替换时，如果有多个Cache行可供替换，可以选择随机进行替换，也可以替换掉最先进入Cache的Cache行（FIFO替换），或者替换掉最近最少使用的Cache行（LRU替换）。

目前最常用的缓存替换策略是最近最少使用算法（Least Recently Used ，LRU）或者是类似 LRU 的算法。 LRU 算法比较简单，如图，缓存有 4 路，并且访问的地址都哈希到了同一组，访问顺序是 D1、D2、D3、D4 和 D5，那么 D1 会被 D5 替换掉。算法的实现方式有很多种，最简单的实现方式是位矩阵。
首先，定义一个行、列都与缓存路数相同的矩阵。当访问某个路对应的缓存行时，先将该路对应的所有行置为 1，然后再将该路对应的所有列置为 0。 最近最少使用的缓存行所对应的矩阵行中 1 的个数最少，最先被替换出去

缓存缺失

缓存缺失就是缓存未命中，需要把内存中数据加载到缓存，所以运行速度会变慢。

[1] CPU缓存一致性：从理论到实践 （公众号：科英）