706-高速缓存的组织结构

高速缓存是一个非常精细的部件，想让它高效地工作，就得在设计时，进行仔细地权衡。想要设计出一个优秀的高速缓存部件，我们就得从几个基本概念开始入手。

‍

我们再来看一看 Cache 的访问过程。如果 CPU 向 Cache 发出了读请求， 那 Cache 就会检查对应的数据是否在自己内部，如果在， 我们就称为 Cache 命中。那有项性能指标就叫做命中率， 这说的是 CPU 所有访存请求中发生了 Cache 命中的请求所占的比例， 那如果命中就从 Cache 内部向 CPU 返回数据。 那从 Cache 中将命中的数据返回的时间，就称为命中时间， 这也是一个重要的性能参数。现在的 CPU 当中，一级 Cache 的命中时间大约是 1 到 3 个周期，二级 Cache 的命中时间大约是 5 到 20 个周期

那如果数据不在 Cache 里，我们就称为 Cache 失效，那对应的就是失效率。 失效率和命中率加在一起，肯定是百分之一百。 那在失效之后，Cache 会向主存发起读请求，那么等待 从主存中返回读数据的这个时间，我们就称为失效代价。 那现在通常需要在 100 到 300 个时钟周期之后，才能得到读的数据。

​

‍

‍

平均访存时间

那要评价访存的性能，我们经常会用到平均访存时间这个指标， 这个指标就是用刚才介绍的那几个参数推算出来的。 平均访存时间就等于命中时间，加上失效代价乘以失效率，那想要提高访存的性能， 我们就得降低平均访存时间，那要做的就是分别降低这三个参数。 这就是提高访存性能的主要途径。

其中想要降低命中时间，就要尽量将 Cache 的容量做得小一些， Cache 的结构也不要做得太复杂。 但是小容量的结构简单的 Cache，又很容易发生失效， 这样就会增加平均访存时间。

其中如果要减少失效代价， 要么是提升主存的性能，要么是在当前的高速缓存和主存之间再增加一级高速缓存。 那在新增的那级高速缓存当中，也需要面临这些问题。 所以这三个途径并不是独立的，它们是交织在一起， 相互影响。

​

‍

那我们先重点来看一看命中率这个因素。 如果有的 Cache 的命中率是 97%， 我们假设命中时间是 3 个周期，失效代价是 300 个周期， 那么平均访存时间就是 12 个周期。那如果我们有一个方法可以在不影响命中时间和失效代价的情况下，将命中率提高到 99%， 那这时候的平均访存时间就降低到了 6 个周期。 所以虽然命中率只提高了 2%，看起来并不起眼， 但是访存性能却提高了一倍，这是非常大幅度的提升。 所以对于现在的 Cache 来说，能够提高一点点命中率，都可以带来很好的性能提升。

​

‍

那哪些因素会影响命中率呢？ 或者我们反过来看，Cache 失效会由哪些原因造成？

有一种叫做义务失效， 那从来没有访问过的数据块，肯定就不在 Cache 里， 所以第一次访问这个数据块所发生的失效，就称为义务失效， 义务失效是很难避免的。

第二种失效原因称为容量失效， 那如果这个程序现在所需的数据块已经超过了这个 Cache 容量的总和， 那不管我们怎么去精巧地设计这个 Cache，总会发生失效。 当然容量失效可以通过扩大 Cache 来缓解， 但是增加了 Cache 容量之后，一方面会增加成本， 另一方面可能也会影响到命中时间，所以也需要综合地考虑。

第三种失效，称为冲突失效，也就是在 Cache 并没有满的情况下， 因为我们将多个存储器的位置映射到了同一个 Cache 行，导致位置上的冲突而带来的失效。

​

‍

映射策略

那我们重点就来看一看如何解决冲突失效这个问题。那这个问题就成为 Cache 的映射策略。

‍

直接映射

那这是一块主存储器的区域，我们还是按照每 16 个字节一个数据块的形式把这块存储器的区域画出来， 所以这里标记的是这个数据块的起始地址， 每个地址之间正好相差 16。那如果我们有一个 8 表项的 Cache， 那么就采用我们之前介绍过的那种存放方法，地址为 0 的数据块是要发在表项 0 当中， 而地址为 080 的数据块，也得放在表项 0 当中， 同样地址为 100 的数据块，也要存放在这个表项中。 这其实就是把内存分成每 8 个数据块为一组，任何一组当中的第 0 个数据块，都会被放在表象 0，第一个数据块都会被放在表象 1， 那这样的 Cache 的映射策略就叫做直接映射。 它的优点在于硬件结构非常简单， 我们只要根据地址就可以知道对应的数据块应该放在哪个表项。

但是它的问题也很明显，如果我们在程序当中正好要交替地不断访问两个数据， 不妨称为数据 A 和数据 B，那如果数据 A 在地址为 0 的这个数据块当中，而数据 B 在地址 080 的这个数据块当中， 那在访问到数据 A 时，会把地址 0 的这个数据块调到 Cache 当中来， 然后把对应的数据 A 交给 CPU，然后 CPU 又需要访问数据 B， 其后开始发现，数据 B 不在 Cache 当中，所以又要把 080 对应的这个数据块调进来， 替换掉原有的表项 0 当中的数据，然后再将数据 B 交给 CPU， 然后接下来 CPU 又访问到数据 A， 那 Cache 又要把地址为 0 的这个数据块调进来，再次覆盖表项 0。

那如果 CPU 不断地在交替访问数据 A 和数据 B， 那这段时间的 Cache 访问每一次都是不命中的，这样的访存性能还不如没有 Cache， 而这时 Cache 当中其他的行，都还是空着的，根本没有发挥作用。 所以这就是这个映射策略上的问题。

​

‍

‍

‍

那为了解决这个问题，我们可以做一些改进，在不增加 Cache 总的容量情况下，我们可以将这 8 个 Cache 行分为两组， 这就是二路组相联的 Cache。 那这样刚才那种交替地访问数据 A 和数据 B 的情况，就不会有问题了， 因为 CPU 访问数据 A 时，就会把地址 0 对应的数据块放在这里， 而接下来在访问数据 B 时，就会把地址 080 对应的数据块放在这里， 然后再反复地访问数据 A 和数据 B，都会在 Cache 中命中， 这样访存的性能就会非常好。

当然如果 CPU 在交替地访问这三个数据块当中的数据， 那么二路组相联的 Cache 又会出现连续不命中的情况，所以我们还可以对它进一步切分。 这就是一个四路组相联的 Cache。 那我们是不是可以无限制地切分下去呢？ 这倒是可以的，如果这个 Cache 总共只有 8 行，而我们把它分成八路组相联， 那也就是说，内存当中任一个数据块都可以放到这个 Cache 当中的任何一个行中， 而不用通过地址的特征来约定固定放在哪一个行。 那这样结构的 Cache 就叫做全相联的 Cache

这样的设计灵活性显然是最高的，但是它的控制逻辑也会变得非常的复杂。 我们假设 CPU 发了一个地址，Cache 要判断这个地址是否在自己内部， 那它就需要把可能包含这个地址的 Cache 行当中的标签取出来进行比较， 对于直接映射的 Cache，只需要取一个标签来比较就行， 二路组相联的时候，就需要取两个标签同时进行比较， 四路组相联的时候就需要取出四个标签来比较， 而在全相联的情况下，那就需要把所有行当中的标签都取出来比较。 这样的比较需要选用大量的硬件电路，既增加了延迟，又增加了功耗， 如果划分的路数太多，虽然有可能降低了失效率，但是却增加了命中时间， 这样就得不偿失了。而且话又说回来，增加了路数，还不一定能够降低失效率， 因为在多路组相联的 Cache 当中，同一个数据块可以放在不同的地方， 那如果这些地方都已经被占用了，就需要去选择一行替换出去， 这个替换算法设计得好不好，就对性能有很大的影响。 如果这个 Cache 选择替换出去的行，恰恰总是过一会就要使用到的那个数据块， 那这样性能的表现就会很差。

​

‍

‍

‍

现在常见的 Cache 替换算法有这几种， 最简单的是随机替换，这个性能显然不会很好。 然后还有轮转替换，也就是按照事先设定好的顺序依次地进行替换， 那如果是四路组相联，上一次替换了第 0 路，这一次就替换第 1 路，下一次就替换第 2 路。 这个从硬件设计设计上来说比较简单，但是性能也一般。 性能比较好的替换算法，是最近最少使用的替换算法，简称为 LRU， 那它需要额外的硬件来记录访问的历史信息， 在替换的时候，选择距离现在最长时间没有被访问的那个 Cache 行进行替换，在使用中，这种方法的性能表现比较好，但是其硬件的设计也相当的复杂。 所以映射策略和替换算法都需要在性能和实现代价之间进行权衡。

​

‍

那我们再来看看一些 Cache 设计的实例， 在 X86 系列 CPU 当中，486 是最早在 CPU 芯片内部集成了 Cache 的， 但它使用的是一个指令和数据共用的 Cache， 这个 Cache 有一个很明显的缺点，那就是指令和数据的局部性会互相影响， 因为指令和数据一般是存放在内存中的不同区域，所以它们各自具有局部性。 利用在执行一个要操作大量数据的程序， 那这些数据就会很快地沾满 Cache，把其中的指令都挤出去了， 那在这个时候，执行一条指令，取指的阶段很可能是 Cache 不命中，需要等待访问存储器， 那就需要花很长的时间，而在执行阶段，去取操作数时，却往往会命中 Cache，那虽然这段时间比较短，但是整个指令执行的时间还是很长。

​

‍

‍

所以到了后来的奔腾，就把指令和数据分成了两个独立的 Cache， 这样它们各自的局部性就不会相互影响了， 现在大多数 CPU 的一级 Cache 都会采用这样的形式。

​

‍

那这个是现在比较先进的 Core i7，它内部采用了多级 Cache 的结构， 其中一级 Cache 是指令和数据分离的各 32K 个 Byte， 采用了 8 路组相联的形式，命中时间是 4 个周期， 所以在 CPU 的流水线当中，访问 Cache 也需要占多个流水级。

那么在这个 4 核的 i7 当中，每个处理器核还有自己独享的二级 Cache， 二级 Cache 就不再分成指令和数据两个部分了， 因为它的容量比较大，指令和数据之间的相互影响就不那么明显。 但是二级 Cache 的命中时间也比较长，需要 11 个周期，那 i7 CPU 的流水线 总共也就 16 级左右，肯定是没有办法和二级 Cache 直接协同工作的。 这也是为什么一级 Cache 不能做得很大的一个重要原因。

那在二级 Cache 之下，还有一个三级 Cache，这是由四个核共享的，总共 8 兆个字节， 三级 Cache 采用了 16 路组相联的结构， 而且容量也很大，达到了 8 兆个字节，这又导致它的命中时间很长，需要 30 到 40 个周期， 但它这样的结构命中率会很高，这样就很少需要去访问主存了。 那我们可以看到这三级的 Cache，它的命中时间从 4 个周期、11 个周期到 40 个周期， 那我们再考虑到主存的 100 到 300 个周期， 这就可以看出，这个多级 Cache 加主存的结构就拉开了明显的层次， 在各自的设计时就可以有不同的侧重，相互配合来提升整个系统的性能。

‍

‍

‍

高速缓存的研究已经持续了很长时间， 直到今天仍然是一个研究的热点， 那只不过之前的研究对象是 CPU 和主存之间的这一级高速缓存， 而现在的研究对象则是由多级高速缓存组成的这么一个多层次的结构， 那不管怎么样，高速缓存技术的研究给我们带来了在可控成本之下，尽可能高的系统性能。