Cache的基本原理（直接映射、组相联、全相联）

  Cache，中译名高速缓冲存储器，其作用是为了更好的利用局部性原理，以便减少CPU访问主存的次数。简单地说，CPU正在访问的指令和数据及附近的指令和数据，可能会被以后多次访问到。因此，第一次访问这一块区域时，将访问到的这一片区域（根据 Cache 大小决定）复制到 Cache 中，下次需要访问该区域的指令或者数据时，就不用再从主存中取出。

Cache 缓存行（Cache line）   Cache是由一组称为缓存行（Cache line）的固定大小的数据块组成，其大小是以突发读或者突发写周期的大小为基础的。每个高速缓存行完全是在一个突发读操作周期中进行填充或者下载的。即使处理器只存取一个字节的存储器，高速缓存控制器也启动整个存取器访问周期并请求整个数据块。缓存行第一个字节的地址总是突发周期尺寸的倍数。缓存行的起始位置总是与突发周期的开头保持一致。当从内存中取单元到 Cache 中时，会一次取一个Cache line 大小的内存区域到 Cache 中，然后存进相应的Cache line 中。

Cache 命中率   缓存命中率是影响缓存性能的重要指标之一，表示在处理器与存储器交互过程中，数据从缓存中读取的比率。

Cache 更新策略(Cache update policy)   Cache 更新策略是指当发生 Cache 命中时，写操作应该如何更新数据。Cache更新策略分成两种：写直通和回写。

写直通（write through）   写直通又称写穿，当CPU执行store指令并在cache命中时，我们更新cache中的数据并且更新主存中的数据。cache和主存的数据始终保持一致。

写回（write back）   当CPU执行store指令并在cache命中时，我们只更新cache中的数据。每个cache line中会有一个bit位记录数据是否被修改过，称之为dirty bit。主存中的数据可能是未修改的数据，而修改的数据躺在cache中。cache和主存的数据可能不一致。

读分配（read allocation）   当CPU读数据时，发生cache缺失这种情况下都会分配一个cache line缓存从主存读取的数据默认情况下， cache都支持读分配。

写分配（write allocation）   当CPU写数据发生cache缺失时，才会考虎写分配策略。当我们不支持写分配的情况下，写指令只会更新主存数据，然压就结束了。当支持写分配的时候，我们首先从主存中加载数据到cache line中 (相当于先做个读分配动作)，然后会更新cache line中的数据。

歧义（ambiguity）   歧义是指不同的数据在 Cache 中具有相同的 Tag 和 index。例如：A 进程将物理地址 0x1000 映射到虚拟地址的 0x5000 ，B 进程将虚拟地址 0x1000 映射到物理地址 0x3000 。当 CPU 从 A 进程切换到 B 进程时，在访问虚拟地址 0x1000 时，此时 B进程 的 虚拟地址的 Tag 和 index 与 A 进程在访问虚拟地址 0x1000 时相同，则会出现 Cache 虽然命中，但访问到的数据并不是 B进程需要的数据，此时便出现 Cache歧义。

  歧义问题可以经过操作系统进行避免，当进行进程切换时，对 Cache 进行清除（Flush ），即清除 Cache 中的所有数据，在进程切换后，CPU 读数据时，在进行加载。但是由于进程切换后开始时会有大量的 Cache miss 发生，故会对 Cache 的性能有很大影响。

别名（alias）   当不同的虚拟地址映射相同的物理地址，而这些虚拟地址的 index 不同时就会发生别名问题。

  内存与 Cache 采用直接映射（direct-mapped）方式关联示意图如下图1所示：  

  如上图1 所示，Cache 与内存采用直接映射方式，其中 Cache 的大小（Cache Size）为 64 Bytes，缓存行（Cache line）的大小为 8 bytes。

  直接映射采用内存与 Cache 多对一的方式，是最简单的地址映射方式，并且其硬件设计简单，成本低，地址变换速度快，而且不涉及替换算法问题。但是这种方式不够灵活，Cache 的存储空间并不能得到充分利用，每个主存块只有一个固定位置可存放，容易产生冲突，使 Cache 效率下降，因此只适合大容量 Cache 采用。例如，如果一个程序查询的地址为 0x1000_0000 后查找 0x1000_0040 之后再去查找 0x1000_0000、0x1000_0040，每次查找的地址正好跨过了 Cache 的大小，此时，每次查询 Cache 时，都会出现 Cache 缺失（miss），这会使 Cache 不断的进行替换，这种现象称为 Cache 颠簸。最好的方式是将主存 0x1000_0000 与 0x1000_0040 同时复制到 Cache 中，但由于是直接映射的方式，它们都只能复制到 Cache 的第0个 Cache line 中去，即使 Cache 中别的存储空间空着也不能占用，因此这两个块会不断地交替装入Cache中，导致 Cache 命中率降低。

优点

缺点

  在全相连（fully-associative）的方式中，对于一个存储器地址来说，它的数据可以放在任意一个 Cache line 中。全相联映射方式内存与 Cache 关联示意图如下图2所示：

  如上图2所示，内存中任何一块都可以映射到 Cache 中的任何一个 Cache line 中。

优点

缺点

  以两路组相联映射为例  

  组相联（set-associative）映射实际上是直接映射和全相联映射的折中方案，存储器中的一个数据不单单只能放在一个 Cache line中，而是可以放在多个 Cache line 中，对于一个组相连结构的 Cache 来说，如果一个数据可以放在 n 个位置，则称这个 Cache 是 n 路组相连的 Cache (n-way set-associative Cache)。

  组相联映射可看成内存与 Cache的 组 之间采用直接映射，而 组内 采用全相联映射。即在图3中，Cache的组0的 Cache line 0~3可以存储 0x1000_0000、0x1000_0008、0x1000_0010、0x1000_0018 中任意一个地址块，也可以存储 0x1000_0040、0x1000_0048、0x1000_0050、0x1000_0058 中任意一个地址块，如下图4所示：

特点

  组内有一定的灵活性，而且因组内行数较少，比较的硬件电路比全相联方式简单。并且空间利用率比直接映射方式要高。

  直接映射方式地址变换如下图5所示：  

  全相联映射地址变换如下图7所示：

  全相联映射对于存储器地址来说，它可以存储在任意一个 Cache line 中，即相当于省略了 index 部分，而是在整个 Cache 中对每个 Cache line 的 Tag 部分进行比较，查找到比较结果相等的 Cache line ，这种方式相当于直接使用存储器的内容来寻址。全相连结构的 Cache 有着最大的灵活度，因此它的缺失率是最低的，但是很明显可以看出，由于有大量的内容需要进行比较，它的延迟也是最大的，因此一般这种结构的 Cache 都不会有很大的容量。

  两路组相联映射地址变换如下图7所示：

  组相联映射的数据会存放于多个 Cache line 中，在处理器访问存储器时，使用 index 对 Cache line 进行寻址，此时会得到两个 Cache line ，接下来同时对两个 Cache line 的 Tag 部分与传入的地址的 Tag 部分进行比较，找出对应的 Cache line。最终通过有效位（valid）位决定此 Cache line 是否有效，若有效，则根据传入的 Offset 找到对应的数据。

🎄 🎨 🎱

《超标量处理器设计-姚永斌》

知乎专栏：高速缓存与一致性

博客园：Cache Line操作和Cache相关概念介绍

哔哩哔哩：计算机组成原理cache组相联映射