Six Basic Cache Optimizations

普通内存访问时间公式给了我们一个框架，来提高缓存优化以提高缓存性能，因此，我们将六种缓存优化分为三类：

■ 降低未命中率——更大的块大小、更大的缓存大小和更高的关联性
■ 减少未命中惩罚——多级缓存并给予读优先于写
■ 减少命中缓存的时间——在索引缓存时避免地址转换B-40 页上的图 B.18 总结了这六种技术的实现复杂性和性能优势。

改进缓存行为的经典方法是降低未命中率，我们提出了三种技术来做到这一点。 为了更好地了解失误的原因，我们首先从一个模型开始，该模型将所有失误分为三个简单的类别：

■ 强制——对块的第一次访问不能在高速缓存中，因此必须将该块带入高速缓存。 这些也称为冷启动未命中或首次引用未命中。
■ 容量——如果高速缓存不能包含程序执行期间所需的所有块，由于块被丢弃并随后被检索，将发生容量缺失（除了强制缺失）。
■ 冲突——如果块放置策略设置为关联或直接映射，则会发生冲突未命中（除了强制和容量未命中之外），因为如果有太多块映射到其集合，则块可能会被丢弃并随后被检索。

这些未命中也称为碰撞未命中。 这个想法是，完全关联缓存中的命中在 n 路集合关联缓存中变为未命中是由于某些流行集合上的请求超过 n 次。

（第 5 章添加了第四个 C，用于由于缓存刷新导致的一致性缺失，以保持多处理器中多个缓存的一致性；我们不会在这里考虑这些。）

图 B.8 显示了缓存未命中的相对频率，按三个 C 细分。 强制未命中是发生在无限高速缓存中的那些。 容量未命中是在完全关联的缓存中发生的那些。 冲突未命中是从完全关联到八向关联、四向关联等发生的那些。 图 B.9 以图形方式显示了相同的数据。 上图显示绝对未命中率； 底部图表按未命中类型绘制了所有未命中百分比作为缓存大小的函数。

为了显示关联性的好处，冲突未命中被划分为由每次关联性降低引起的未命中。 以下是冲突未命中的四个部分及其计算方法：

■ 八路——由于从完全关联（无冲突）到八路关联而导致的冲突未命中
■ 四路——由于从八路关联到四路关联而导致的冲突未命中
■ 双向——由于从四向关联变为双向关联而导致的冲突未命中
■ 单向——由于从双向关联到单向关联（直接映射）而导致的冲突未命中从图中我们可以看出，SPEC2000 程序的强制未命中率非常小，就像许多长时间运行的程序一样。

确定了三个 C 之后，计算机设计师可以对它们做些什么呢？从概念上讲，冲突是最简单的：完全关联的放置避免了所有冲突未命中。 但是，完全关联在硬件中很昂贵，并且可能会降低处理器时钟速率（请参见第 B-29 页上的示例），从而导致整体性能降低。

除了扩大缓存之外，几乎没有什么可做的容量。 如果上层内存比程序所需的内存小得多，并且很大一部分时间用于在层次结构中的两个级别之间移动数据，则可以说内存层次结构颠簸。 由于需要进行如此多的替换，抖动意味着计算机的运行速度接近于较低级别内存的速度，或者由于未命中开销而可能更慢。

改进三个 C 的另一种方法是使块更大以减少强制未命中的数量，但是，正如我们很快将看到的，大块会增加其他类型的未命中。

三个 C 可以深入了解未命中的原因，但这个简单的模型有其局限性； 它可以让您深入了解平均行为，但可能无法解释个别失误。 例如，更改缓存大小会更改冲突未命中和容量未命中，因为更大的缓存会将引用分散到更多块。 因此，随着缓存大小的变化，未命中可能会从容量未命中转变为冲突未命中。 类似地，改变块大小有时可以减少容量缺失（除了预期的强制缺失减少），如 Gupta 等人。 (2013) 显示。

还要注意，三个 C 也忽略了替换策略，因为它很难建模，而且一般来说它不太重要。 在特定情况下，替换策略实际上会导致异常行为，例如较大关联性的错误率较低，这与三个 C 的模型相矛盾。 （有些人建议使用地址跟踪来确定内存中的最佳位置，以避免三个 C 模型中的位置错误；我们在这里没有遵循该建议。）

唉，许多降低未命中率的技术也会增加命中时间或未命中惩罚。 使用三种优化来降低未命中率的愿望必须与使整个系统快速的目标相平衡。 第一个例子显示了平衡视角的重要性。

First Optimization: Larger Block Size to Reduce Miss Rate

降低未命中率的最简单方法是增加块大小。 图 B.10 显示了一组程序和缓存大小的块大小与未命中率的权衡。 更大的块大小也将减少强制未命中。 这种减少的发生是因为局部性原则有两个组成部分：时间局部性和空间局部性。 较大的块利用空间局部性。

同时，较大的块会增加未命中惩罚。 因为它们减少了缓存中的块数，如果缓存很小，较大的块可能会增加冲突未命中甚至容量未命中。 显然，几乎没有理由将块大小增加到会增加未命中率的大小。 如果增加平均内存访问时间，那么降低未命中率也没有任何好处。 未命中惩罚的增加可能超过未命中率的降低。

与所有这些技术一样，缓存设计者试图将未命中率和未命中惩罚都降至最低。 块大小的选择取决于底层内存的延迟和带宽。 高延迟和高带宽鼓励大块尺寸，因为缓存每次未命中获得更多字节，而未命中惩罚的小幅增加。 相反，低延迟和低带宽鼓励较小的块大小，因为从较大的块中节省的时间很少。 例如，一个小块两倍的未命中惩罚可能接近于一个两倍大小的块的惩罚。 大量的小块也可以减少冲突失误。 请注意，图 B.10 和 B.12 显示了基于最小化未命中率选择块大小与最小化平均内存访问时间之间的差异。

在看到较大块大小对强制和容量未命中的正面和负面影响后，接下来的两个小节将着眼于更高容量和更高关联性的潜力。（块大，强制未命中率小；但是在缓存比较小的情况下，块大，容量未命中率和冲突未命中率大。）（高带宽高延迟，用大块；低延迟低贷款，用小块。）