2.6.3 受害者缓存

我们知道，缓存的工作原理基本上依赖于程序的两种基本的访问模式：时间局部性（Temporal Locality）和空间局部性（Spatial Locality）。时间局部性是指，如果一个数据项在某个时间被访问，那么它在近期内可能会再次被访问，例如在循环中重复访问的数据或经常调用的函数的指令。空间局部性是指，如果一个数据项被访问，那么其附近的数据项在近期内也可能被访问。这是因为程序通常会被顺序执行，数据也通常以块或数组的形式被存储和访问。

缓存利用这些局部性原则，预测哪些数据和指令可能会在近期内被重复使用。通过将这些数据和指令存储在一个距离 CPU 更近、访问速度更快的存储设备（缓存）中，可以加速CPU的数据访问，从而提高整体的系统性能。当CPU需要访问某个数据项时，它就要检查该数据项是否已经在缓存中。如果数据项在缓存中（称为“缓存命中”），则CPU可以快速地访问它，而无须等待从主内存中获取。如果数据项不在缓存中（称为“缓存未命中”），则CPU必须从主内存中获取数据，同时将其放入缓存中，以供将来使用。

当一个数据项由于冲突而被替换出缓存时，我们不立即丢弃它，而是先将其存放在受害者缓存（Victim Cache）中。如果我们很快再次访问这个数据项，则CPU可以直接从受害者缓存中获取它，而不是从主内存中重新加载它。这大大提高了缓存命中率，并降低了由于冲突导致的缓存未命中率。

受害者缓存是一种策略，它为直接映射缓存添加了一个小型的全相联缓存部分，可以被理解为缓存的缓存，其数据都是从原本的缓存中驱逐出来的。它的设计目的是结合直接映射缓存的快速命中时间，同时避免由于多个内存块映射到同一缓存行而导致的抖动（Thrashing）现象。这种抖动现象会导致块在缓存中被频繁替换，从而降低命中率。当一个块从直接映射缓存中被替换时，这个块不会立即被丢弃，而是被移动到受害者缓存。当处理器再次访问这个被替换的块时，可以在受害者缓存中快速找到它，从而提高整体的缓存命中率。受害者缓存是一个额外的、小型的全相联缓存部分。在IBM Power 9中，L2和L3缓存都使用了受害者缓存策略。

受害者缓存包含4条数据线，L1缓存是直接映射的，因此每条缓存线由内存中的一个数据块加上一个小标签组成，受害者缓存是相联的（Associative），因此每条缓存线包含一个来自内存的数据块和一个大标签，如图2-13所示。受害者缓存中的标签由与直接映射缓存长度相等的标签和比较器组成，标签和比较器唯一地标识一个内存块，来自处理器的内存引用可以并行搜索相联缓存中的所有条目，以确定所需的缓存行是否存在。通过使用FIFO策略，受害者缓存实现了真正的LRU行为。

图2-13 受害者缓存的工作流程和组织形式

具体数据缓存流程方面：在遇到L1缓存未命中的情况下，如果受害者缓存里面有所需数据，则该数据将会返还给L1缓存，L1缓存里被驱逐的数据会被存进受害者缓存；如果L1缓存和受害者缓存中都没有所需数据，就从更低一级的存储器中取出该数据，并把它返还给L1缓存。任何被受害者缓存驱逐的未修改过的数据都会被写进内存或者被丢弃。

选择性受害者缓存（Selective Victim Cache）是对受害者缓存策略的一种改进，它允许在直接映射缓存和受害者缓存之间选择性地放置或交换块。选择性受害者缓存可以提高缓存的命中率，更智能地预测哪些块在未来更有可能被引用。当从主存或L2缓存中取来一个新块时，不再固定地将其放入直接映射缓存，而是根据预测算法决定是否将其放入主缓存或受害者缓存。当直接映射缓存未命中但受害者缓存命中时，可以选择性地交换两个缓存中的块，而不是总进行交换。

受害者缓存策略在缓存容量较小时使用是有益的，但随着技术的发展和设计需求的变化，在主流的CPU和GPU设计中，它可能不再是最佳选择。但这并不意味着它的设计思想已经完全被遗弃，其背后的基本思想“利用小型、专用的缓存来优化缓存性能”仍然在现代处理器设计中有所体现。现代处理器中的专用预取缓存、流缓存和其他类似的技术都从某种程度上借鉴了受害者缓存的设计思想。