一、引子

在这个小节中，我们要学习 Cache 和主存的 3 种映射方式。

上一小节的末尾，我们留下了这样的几个问题。

由于Cache，它保存的是主存里边的某一些数据块的副本，我们必须考虑到的一个问题就是如何区分 Cache 和主存它们之间的这种数据块的映射关系。

这个小节要介绍的 Cache 和主存的映射方式，探讨的就是这个主题。

---

二、介绍

（1）三种映射方式

我们总共会学习三种映射方式。

<1> 第一种叫做全相联映射。如果采用这种映射策略，就意味着对于任何一个主存块，它可以存放到 Cache 里的任何一个 Cache 块当中。

采用这种方式，就意味着 Cache 里的某一行或者某一个 Cache 块，它里边的数据有可能来自于主存的任何一个位置。

<2> 第二种叫直接映射。直接映射方式就是主存里的某一个主存块，它只能存放在 Cache 当中某一个规定的位置。

确认的方式是这样的，我们可以用主存块号对 Cache 的总块数进行一个取余的操作。余数是多少，我们就把相应的主存块放到哪个位置。

比如对于这个例子来说， Cache 块的总数应该是有 8 块，对于 1 号主存块来说，它的存放位置就是 1（1%8=1）。 再来看，对于 9 号主存块， 9 对 8 取余也等于1。所以如果要把主存块的内容调入Cache，同样的，它只能放到 Cache 块号为 1 的位置。

所以如果采用直接映射方式，就意味着每一个主存块它只有可能会存放到 Cache 里的某一个特定的位置。

<3> 第三种叫组相联映射。看这个图不难理解，我们会把 Cache 的各个块进行一个分组，每一组的总块数是相同的。

比如在这个例子当中，我们把 8 个 Cache 块分成了 4 个分组，每一个分组当中会有 2 个 Cache 块。对于任何一个主存块，我们可以用主存块号对分组的总数进行一个取余，来确定某一个主存块它应该放在哪一个分组。

这个例子当中，总共分了 4 个分组。对于1 号主存块来说，它可以存放的位置应该是1（1%4=1），也就是它应该放到第一个分组里边，第一个分组里边有两个空位，哪个地方有空，我们就可以放到哪。

再来看 9 号主存块， 9 对 4 取余余数等于1，所以 9 主存块它也应该放到第一个分组。同样的，第一个分组内哪有空就可以把它放到哪儿。

这就是小节当中要学习的 3 种映射方式。

---

（2）标记及有效位

回到刚开始提出的问题，我们应该如何区分 Cache 当中存放的是哪一个主存块？

一个比较容易想到的办法是，我们可以给每一个 Cache 块或者每一个 Cache 行建立一个所谓的标记，可以记录下来 Cache 块它所对应的主存块号是多少。以主存块号作为标记。

所以对于全相联映射来说，如果我们给前三个 Cache 块给它们记录的标记是9、8、5。

意思就是 0 号 Cache 块，它存放的数据其实是 9 号内存块的一个副本。 1 号 Cache 块，它所存放的数据应该是 8 号内存块的一个副本。 2 号 Cache 块也是类似，存放的是 5 号主存块的一个副本。

所以我们可以用主存块的块号来作为标记，记录下来每一个 Cache 块它所对应的数据应该是什么。

现在看起来好像问题已经解决了，是不是只有标记就够了？

大家要知道，这儿所谓的标记在计算机内部，在计算机硬件的层面，其实记录的就是一些二进制的 0101 ，就是用二进制来记录主存的块号。

像刚才这个例子当中，我们并没有记录后续这些 Cache 块它的标记，我们让它保持为空就可以。然而对于计算机硬件来说，所有的二进制位只有可能是 0 或者 1 这样的两种状态，不可能出现所谓空的状态。

所以站在计算机硬件的角度来看，其实刚开始所有的这些 Cache 块的一个标记信息，肯定都会被初始化为全 0 这样的一个状态。

后边这些标记都是全0，是不是意味着 3、4、5、6、7 这几个块保存的都是主存块号为 0 的一个副本？显然不对。

所以我们光有标记是不够的，我们还需要增加一个有效位。

有效位可以为 0 或者为1，如果为1，表示标记是有效的；如果为0，表示标记无效。

像这个例子当中，只有最后这一行 （7 这一行），它的有效位是1，同时标记为0，就说明 7 号 Cache 块它所存放的数据是 0 号主存块的一个副本。如下：

所以对于每一个 Cache 块来说，除了给它配一个标记之外，还需要给它配一个有效位。

这些东西都是直接用硬件电路来实现的。

三、详细讲解

接下来我们来展开看一下这三种映射方式的一些具体的细节。

（1）全相联映射

先来看全相联映射，也就是可以随意映射。

我们给定这样的一个场景，假设有个计算机，它的储存地址空间是 256 兆字节，并且是按字节编址。它的 Cache 总共有 8 个 Cache 行。

上个小节我们说过， Cache 行就是 Cache 块，每个的 Cache 行的大小 为64 个字节，应该是和主存块的大小是保持一致的。

1.Cache

我们先给出 Cache 的图。如下：

总共有 8 个 Cache 行，就是 8 个 Cache 块，每一块的大小是 64 个字节，所以总共是 512 个字节。

2.主存

再来看主存，256GB的主存也是被分为了一个一个的块。

首先， 256 兆个字节应该是对应 2 的 28 次方这么多个字节，所以主存它总共的地址位数应该是28 位。256MB（2 ^28）除以64B（ 2^ 6），得到的结果是 2 ^22。

这就意味着整个主存会被划分为 2的22 次方这么多个主存块。

我们可以用前边的 22 位作为主存块号，然后末尾的 6 位作为块内地址。

那么主存块号应该是从0一直到 2^22-1，这是主存块号的范围。

每一个主存块的大小是 64 个字节，也就是每一个主存块会对应 64 个地址。我们可以把这些地址的范围进行一个标注。 如下：

第一个主存块，它的 22 位的块号都是0，块内地址是000000~111111。后续的都是一样的。

3.映射

再次强调，每一个 Cache 块的大小和主存块的大小是相同的。

另外，这两个部件之间传送数据是以块为单位。

接下来看一下全相联映射如何实现。

首先我们一定需要有一个有效位，刚开始整个 Cache 都是空的，所以所有的有效位都把它记为0。

接下来我们假设要把主存的第0块放到 Cache 当中。

由于采用的是全相联映射，这就意味着主存块可以放到 Cache 里的任何一个位置。

假设我们挑选 3 这个位置，把它放进去。

为了区分 3 这个Cache 块它存放的是哪个主存块，因此我们需要在前边记录一个标记，其实就是主存块的块号。

之前我们说过，主存块的块号总共需要占 22 位，所以这里我们记录了 22 个0。 （上图3号Cache位的蓝色数字）

---

再来看下一个。假设我们要把紫色的主存块放到 Cache 当中，同样的，我们可以随意挑一个位置把它放进去。

假设我们挑中的是 1 这个位置，把它放进去之后，同样的，我们需要修改有效位为1。

同时把标记设置为当前的块号。

后续的就不再展开。 总之，采用全相联映射，任意一个主存块可以放到 Cache 里的任意一个位置。

4.访存

接下来我们再来考虑这样的一个问题，采用这种映射方式， CPU 如何访问一个主存的地址？

• 命中

假设现在 CPU 要访问的主存地址是这样的一个地址，它的主存块号刚好和我们紫色的这一块的主存块号一致。

引入了Cache之后是这么做的。

首先会取主存地址的前 22 位，也就是取出主存块号。用主存块号来和 Cache 当中的每一行的标记进行对比。

如果某一个 Cache 行的标记和我们主存地址的块号是相同的，我们再检查有效位，当有效位为1，同时 22 位的标记匹配之后，就说明 Cache 命中，也就是我们此时要访问的地址所对应的数据，其实在 Cache 当中是存在副本的。

之前我们说过，每一个 Cache 块，每一个主存块都是 64 个字节的大小。所以接下来我们只需要根据后半部分这 6 位的块内地址（001110)来 Cache 当中找到相应的字节或者相应的字就可以。

• 未命中

上述是命中的情况。

如果没有命中，就是所有的标记和我们给出的主存的主存块号都不能匹配。或者即便标记匹配了，但是有效位为 0 的情况下， CPU 就不能访问Cache，它必须进行一次访问主存的操作。

对于主存的访问如何实现，我们之前已经讲过具体的硬件细节了，这就不再赘述。

这就是基于全相联映射的一个缓存的过程。

（2）直接映射

1.映射

接下来我们再看第二种映射方式直接映射。

每一个主存块它只能放到固定的位置，具体可以放到什么位置，我们可以用主存块号对 Cache 的总块数进行一个取余得到。

比如，此时要把 0 号主存块放到 Cache 当中， 0 对 Cache 的总块数 8 取余等于0，这就意味着 0 号主存块它只能放到 Cache 的第0行第0块这个位置。

我们把它放过去，同时把有效位改为 1 。标记和刚才一样，我们同样需要记录下主存块的块号。

---

现在，假设我们要把 8 号主存块调入Cache。

由于 8 对 8 取余同样等于0，这就意味着 8 号主存块它也只能被放到 0 号Cache块这个位置。如下：

所以这个时候我们只能把之前存放的数据给覆盖掉，同时要把标记改为 8 号主存块的块号。大家可以看一下，0...01000翻译成二进制刚好是8 。

所以，如果采用直接映射方式，有个显而易见的缺点，就是虽然这Cache里边还存在很多个空闲的 Cache 块，但是这些块我们都用不了，我们只能把主存块放到固定的位置。

因此相比于全相联映射，直接映射的灵活性要差一些，空间利用率也不充分。

接下来思考这样一个问题，我们这采用了 22 比特的标记，也就是把整个主存块号都给保存下来作为标记，这个方式可不可以进行优化？

要回答这个问题，我们得回到主存块它存放位置的确定方式。

主存块在Cache中的位置等于主存块号对 Cache 的总块数进行一个取余。

这个例子当中，我们会发现， Cache 的总块数刚好是8，可以把它写成 2 的 n 次方这种形式， 8 等于 2^ 3。

从二进制的角度来看，就是主存块号对 2 的三次方进行取余。

这个运算的结果其实相当于我们保留了整个主存块号的末尾三位。

这也就意味着，对于计算机硬件来说，硬件不需要去做这种取余的操作。

计算机硬件只需要把主存块号的末尾 3 位，也就是把上图橙色的地址部分给截取下来。

这三个二进制位直接指明了一个主存块它应该存放在 Cache 中的什么位置。

比如刚才的 0 号块（绿色），它的块号的末尾三位刚好是三个0，三个 0 对应十进制的0，而 8 号块，它的末尾三位也刚好是三个0，同样也是对应十进制的0。

这也就意味着这两个主存块肯定是存放在 Cache 的 0 号位置。

所以这就说明，如果某一个主存块，它能够存放在 0 号 Cache 位置，那么这个主存块的块号末尾的三位一定都是0。

既然如此，我们是不是就没必要保存主存块号的末尾 3 位了？

所以当我们的 Cache 总块数可以写为 2 的 n 次方这种形式的时候，主存块号的末尾 n 位就直接反映了它在 Cache 当中的位置。

因此我们这儿存储的标记就没必要存储最末尾的 n 位的信息。

对于这个例子来说，我们的标记位实际只需要存储 19 位就可以，末尾的 3 位是可以把它砍掉的。

我们把 Cache 的这些 Cache 块号翻译成二进制的形式，这样大家就可以更方便地和右边给出的这些主存的地址进行一个对比。

总之，主存块号的末尾三位如果是010，那么这个主存块一定是存放在 Cache 块号同样为 010 这个位置。

经过分析之后，我们可以知道，在这个例子当中，只需要记录内存块号前边 19 位来作为标记，末尾的 3 位可以直接把它舍弃。

因此，如果采用直接映射，原本的主存块号，可以再把它细分为两个逻辑部分，前边的 19 位可以作为 Cache 行的标记，后边的 3 位反映了每一个主存块号应该存储在哪个 Cache 行。

2.访存

接下来看一下基于这种映射方式，如何进行访存。

• 命中

假设此时 CPU 要访问的主存地址是这样的一个地址0…01000 001110，这个地址被包含在 8 号主存块当中（橙色）。

由于采用的是直接映射，所以第一步 CPU 应该确定主存块它会放在 Cache 的哪一个位置。

具体的做法就是

①取出块号的后三位的信息000（橙色部分）来确定主存块它在 Cache 中的存放位置。

现在我们已经知道了，它应该是存放在 0 这个位置。

②所以接下来 CPU 会对比主存块号的前边 19 位0...01（蓝色部分），用这 19 位和 0 号 Cache 块的标记进行一个对比，如果标记相同，并且有效位也为1，就说明 Cache 命中。

接下来再根据块内地址，在 Cache 块当中找到想要的数据就可以，这是命中的情况。

• 未命中

而如果没有命中，或者有效位为0， CPU 同样还是需要进行访存。

这就是直接映射。

（3）组相联映射

1.映射

接下来再来看最后一种组相联映射。

每一个主存块可以被放到特定分组当中的任意一个位置。

具体应该放到哪个分组是这么来确定的。可以用主存块号对总的分组数进行一个取余操作。

在这个例子当中，假设我们采用了 2 路的组相联映射，所谓的 2 路指的是每两个 Cache 块为一组，总共有 8 个 Cache 块，所以我们会分为 4 组。

所以 1 号主存块它应该是被放到了第一组。

第一组里任何一个空闲的位置，我们都可以把它放进去，比如把它放到 3 这个位置。

---

再看下面橙色的主存块，大家可以算一下。 222-3对 4 进行取余，刚好也是等于1，所以我们可以把它放到第一组的任何一个位置。

由于 2 号是空闲了，所以可以把它放到 2 号这个位置。

和之前类似，由于我们的分组数刚好可以写成 2 的 n 次方这种形式。

这个例子当中总共是有 22这么多个分组。所以主存块号对分组数进行取余，相当于我们只保留了主存块号的末尾 2 位（上图橙色的地址部分），而末尾的两位主存块号刚好又反映了它所属的分组的组号是多少。

所以大家并不需要去算22这个数对 4 取余到底是多少，我们只需要直接看它的主存块号末尾的两位是01，就可以确定22它对 4 取余运算的结果一定是01，也就是对应十进制的1。所以应该把它放到第1个分组。

和之前类似，既然有可能出现在同一组的这些主存块，它们块号的末尾两位一定都是相同的。那我们是不是就没有必要记录后面的这两位了？

所以在这个例子当中，我们的标记位只需要取主存块号的前 20 位进行记录就可以。

如果采用组相联映射，在这个例子当中，我们可以把这 22 位的主存块号进一步地细分为两个逻辑部分。

第一个前边的 20 位可以作为 Cache 行的标记，后面的这2位我们可以用来判断主存块应该放到哪个分组，也反映了组号的信息。

2.访存

来看一下如何进行访存。

• 命中

这地方我们把每一个 Cache 块它所从属的分组的组号给它标记上去了，可以2个比特来表示。

如果此时 CPU 要访问的主存地址是这样的1...1101 001110，此时 CPU 应该先判断这个地址它所从属的主存块，如果存放在 Cache 当中，应该放在第几个分组里边。

具体的判断方法就是

①取出主存块号的后面两位01（橙色部分）。就可以知道，如果它在 Cache 中有副本，肯定是存放在编号为 01 的分组当中。

②接下来CPU就可以在01分组当中一个一个的去对比标记和我们给出的地址的标记是否能够匹配。

如果能匹配并且有效位为1，就说明 Cache 命中。

③接下来再结合块内地址，再从 Cache 块里边读取出相应的存储单元就可以。

这是命中的情况。

• 未命中

如果没有命中CPU，同样需要对主存进行访问。

这就是最后一种组相联映射方式。

四、对比总结

这一小节当中，我们学习了 Cache 和主存的映射方式，分为全相联映射、直接映射和组相连联映射。

不同的映射方式对于主存块可以存放在 Cache 的哪个位置，它的限制是不一样的。

由于这种限制不一样，因此当我们要记录 Cache 块和主存块的对应关系的时候，所需要记录的标记位也会出现一些区别。

再来简单分析一下各种地址映射方式的一个优缺点。

①对于全相联映射，由于它的自由度很高，我们可以把任何一个内存块放到 Cache 里的任何一个位置，因此 Cache 的存储空间会利用得很充分。

这就意味着，只要 Cache 没满，我们就可以继续往 Cache 里边存入更多的主存块，这就会导致 Cache 的命中率更高。

另一个方面，使用全相联映射，我们在查找标记的时候，有可能需要把所有的 Cache 行它的标记都进行一个对比。所以查找标记的速度在三种方法当中是最慢的。

②再来看直接映射

直接映射和全相联映射，刚好是两个极端。

它的优点就是对于任何一个地址，我们可以直接根据块号来确定它唯一有可能在Cache 当中出现的位置。

因此，我们只需要进行一次的标记对比，就可以确定 Cache 是否命中。所以这种方法，它标记的对比速度是最快的。

另一个方面，由于每一个主存块只能放到 Cache 的某一个固定位置，所以 Cache 的存储空间利用得会很不充分，同时也会导致 Cache 的命中率降低。

③最后是组相联映射

其实是上面这两种方法的一个中和，综合效果会更好。

组相联映射方式具备了全相联映射的自由度，同时又具备了直接映射的标记对比速度。

---

大家需要注意，在做题的时候，有可能会出现 n 路组相连映射这样的一个描述。所谓的 n 路就是指每 n 个 Cache 行作为一组。

最后，同学们还需要能够根据每一种地址映射方式的地址结构来思考，如果给定一个主存地址，那么 CPU 是如何拆分地址的？如何查找Cache，如何对比标记，这些也是大家需要掌握的东西。