为了缓和计算机的运行速度和主存（内存）访问速度之间的矛盾，Cache作为中间的一级，容量小但读写速度快于主存，夹在了主存和CPU之间。CPU需要访存时会优先访问Cache，如果Cache命中则直接使用Cache中的数据。在缓存设置合理的情况下，CPU访存时间大幅降低，显著提升了CPU的吞吐量。

主存分块，Cache分片

不论是何种实现方式，对主存和Cache的分块/分行是必不可少的。

计算机主存按字节编址，举个例子，一个1KB的主存，它的地址是从0000000000到1111111111，每个数字代表了一个字节（Byte）。这么多的地址，将若干数量的地址(大部分情况的个数是$2^n，n \in N^+$)组成一块进行分块，每块的大小称为主存块大小。

同时，Cache中的数据，是主存块中地址的一个部分缩影，所以它的内部也进行了分块，这种分块被称为行。
主存块和Cache分块大小保持一致，并且大小都是$2^n$。这种设计让主存和Cache交换数据时更有效率，也简化了缓存系统的设计。

块内地址

我们对主存地址进行分块之后，整个主存地址也就被分为了2部分。以上图为例，主存地址总共有6位，前面四位用来表示图中16($2^4 = 16$)块主存块中的哪一块，称为主存块号。后2位($2^2 = 4$)可以表示在某个主存块内的位置，称为块内地址。

映射方式

接下来，我们需要考虑，主存中的块，和Cache中的行，如何进行对应。首先在Cache中，除了存储数据，我们需要记录一些额外的数据。

不论何种映射方式，我们都需要一位来记录当前Cache行是否有效。

图中只有Cache data2是有效的。其它的Cache行的数据是无效的

全相联映射

全相联映射中，主存中的块，可以映射到Cache中的任何位置。访存时，当Cache未命中时，CPU将主存块调入Cache中的空位。

需要记录一些信息，来确保在调回主存时，Cache行能找到它所对应的主存块。

我们无需记录任何块内地址的信息，如果我们找到了行对应的块，通过主存地址的最后N位，我们一定也能找到它在某个块内的位置。

对于全相联映射而言，我们必须记录主存块号，也就是主存地址中，除了块内地址的剩余部分。我们把它记录在Cache的每一行中，称为标记，或者Tag

图上对于地址在100000B~100111B的主存块，被映射到了Cache data1的行中，他们之间的映射关系，由Tag100体现

对于全相联映射的Cache，访存时的行为是：

Cache中每一行的tag都与访问地址中的Tag进行比较，如果某一行相等且有效(valid = 1，下同)，则缓存命中

这种映射方式Cache利用率高，但每次访存时需要和全部的Tag比较，电路实现复杂

全相联映射下，地址的结构为

假设Cache行数为$m$，我们需要$m$个比较器才能在一个常数级的时间知晓Cache是否命中，因此电路实现复杂。

直接映射

直接映射方式，将主存块号 对 cache行数取余，通过余数来确定映射到哪个Cache中。

如图中，对于主存块号为3(011B)和7（111B) ，他们都会被映射到行号为3的Cache行中，因此我们通过Cache行找回Cache中时，我们的Tag要区分它到底来自于3还是7。

既然主存块号取余能知道映射到哪一块，那么余数之外的部分，即$主存块号 / Cache行数$，就能作为tag，用于在这些余数相等的块中做区分。以这种方法，块号为3的Tag为0B，块号为7的为1B。

对于Tag的长度，我们这样思考：

Tag区分的是，映射到同一Cache行的不同主存块。举个例子，我们假设Cache行数为4，主存块数为16，那么映射关系如下

相同的Cache行号，会被$(主存行数 / Cache行数)$个主存块映射，又因为Cache的行，和主存的块大小相同。它所占的位数就是

对于行号的位数，就是：$log_2(Cache行数)$

这种映射方式实现简单，但利用率低，这种策略在Cache中存在空行时但缓存未命中，可能会调出行而不是使用空行。

对于直接映射法，访存时的过程是：

根据访问的地址的高位，取到Cache对应的一个行号和Tag，如果Cache行有效并且Tag相等，则缓存命中

直接映射法，它的地址结构为

我们只需要1个比较器，所以Cache电路实现是最简单的。

组相联映射

直接映射法会导致Cache利用率低，而全相联映射法又会导致在检查Cache是否命中时，电路中比较器个数较多，组相联映射便是他们之间折中的映射方法

组相联映射法将Cache的行按照某个大小合并为1组，一组的大小为$2^n$。之后与直接映射原理的操作几乎相同。

$组号 = 主存块号 \% Cache组数$，$Tag = 主存块号 / Cache组数$

它的访存过程为：

1. 根据访问地址，得到组号和Tag
2. 对一组Cache中的所有行的Tag与访存地址的Tag进行比较，如果找到Tag相等且有效的缓存，则缓存命中

组相联映射法的地址结构为

假设我们缓存一组里有$m$行，我们需要$m$个比较器

总结