to_be_rdwr banshee

返回主页
返回上一页

BanShee [MICRO'17]

[Title] Banshee: Bandwidth-Efficient DRAM Caching via Software/Hardware Cooperation

年份比较早，这篇文章分析不追求过多细节，直接速通

本文代码开源，基于ZSim模拟器进行实验

 

Abstract

将 DRAM 放置在与处理器相同的封装中，可以实现比传统的封装外 DRAM 高出数倍的内存带宽。然而，封装内 DRAM 的延迟并没有明显低于封装外 DRAM。封装内 DRAM 的一个有前景的应用是作为大缓存。不幸的是，大多数以前的 DRAM 缓存设计主要优化缓存命中延迟，而没有将带宽效率作为首要设计约束。因此，正如本文所展示的，这些设计在与封装内 DRAM 配合使用时是次优的。我们提出了一种新的 DRAM 缓存设计——Banshee，它优化了封装内和封装外 DRAM 的带宽效率，同时不会降低访问延迟。Banshee 基于两个关键思想。首先，它通过使用 TLB 和页表条目跟踪 DRAM 缓存的内容，从而消除了标签查找的开销，这一点得益于我们提出的一种新的轻量级 TLB 一致性协议。其次，它通过一种新的基于频率的带宽感知替换策略，减少了不必要的 DRAM 缓存替换流量。我们的评估结果表明，Banshee 在性能上显著提高（平均提升 15%），并且比之前优化延迟的最佳 DRAM 缓存设计减少了 35.8% 的 DRAM 流量。

 

Introduction

论文速览采用AI翻译，部分名词有误，未作修正，意会即可。如内包外包等，即片上片外。

封装内 DRAM 技术将 CPU 和大容量 DRAM 集成在同一封装中，能够为 CPU 提供比传统封装外 DRAM 高得多的主存带宽。对于受限于内存带宽的应用程序（如图处理、某些机器学习算法、基于稀疏线性代数的高性能计算代码等），封装内 DRAM 可以显著提升系统性能 [9, 10, 17, 30, 34]。多个硬件厂商已经推出了配备封装内 DRAM 的处理器（如 Intel 的 Knights Landing [56]、AMD 的 Fiji [3] 和 Nvidia 的 Pascal [2]），并且已有大量系统设计为利用封装内 DRAM [18, 20, 27, 32, 38, 39, 41, 45, 50, 54, 59]。封装内 DRAM 的一个关键特性是，尽管它提供了高带宽，但其延迟与封装外 DRAM 相似，甚至可能更高 [1, 19, 55]。这是因为现代封装内 DRAM 产品面向的计算应用通常是带宽密集型且对延迟具有一定容忍度。然而，许多以前的 DRAM 缓存设计假设封装内 DRAM 的低延迟，因此并不一定适合具有封装内 DRAM 的实际系统。特别是，许多现有的 DRAM 缓存设计会为元数据管理（如获取 DRAM 缓存标签）和缓存替换产生大量流量到封装内和/或封装外 DRAM。由于多GB缓存的标签数组无法轻易地放入芯片上的 SRAM 中，许多以前的设计（特别是细粒度设计）将标签数组存储在封装内 DRAM 中 [32, 45, 50]，并且每次标签查找都需要访问它。尽管使用以前提出的技术 [32, 45, 50]，标签查找的延迟可以在很大程度上被隐藏，但元数据访问仍然消耗了宝贵的带宽。

对于页粒度的 DRAM 缓存设计，缓存替换可能会导致过多的 DRAM 流量，因为每次替换都需要在片内片外 DRAM 之间移动整页数据。对于那些具有较少空间局部性的页面，大部分传输的数据根本不会被处理器访问，从而浪费了片内片外 DRAM 带宽。当系统中使用大页（例如 2MB 或 1GB）时，这个问题会变得更加严重。此外，如果元数据（例如 LRU 位或频率计数器）存储在 DRAM 缓存本身中，访问和更新这些元数据也会带来额外的 DRAM 流量。现有的解决方案，如足迹缓存 [28, 31]，通过仅缓存那些可能会被处理器访问的页面部分，能够在一定程度上缓解带宽压力。然而，我们的评估（第六节）表明，仍然存在显著的改进空间。

在本文中，我们提出了 Banshee，一种 DRAM 缓存设计，其目标是最大化片内片外 DRAM 的带宽效率，同时提供低访问延迟。Banshee 基于两个关键思想。首先，类似于之前的工作 [38]，Banshee 通过使用 PTE（页表项）和 TLB（转换后备缓冲区）条目来跟踪 DRAM 缓存内容，从而避免了标签查找。然而，与之前的工作不同，Banshee 使用了一种新颖且轻量级的 TLB 一致性机制，具有低复杂度。具体来说，Banshee 在每个内存控制器上维护一个小型硬件表（称为标签缓冲区），该表存储有关页是否被缓存的信息，适用于最近插入或替换的页面。PTE 和 TLB 条目只有在标签缓冲区满时才会延迟更新，从而大大降低了 TLB 一致性所带来的性能开销。Banshee 的第二个关键思想是基于频率的带宽高效替换（FBR）策略，其目标是减少不必要的 DRAM 缓存替换流量。

为此，Banshee 通过带宽感知的 FBR 策略，限制替换发生的速率，从而减少

具体来说，本工作做出了以下贡献：

（1）我们提出了一种懒惰且轻量级的 TLB 一致性机制，它比之前基于页表的 DRAM 缓存设计中的 TLB 一致性机制更简单、更高效。

（2）我们提出了一种新的带宽感知频率基础替换策略，通过最小化不必要的数据和元数据传输，显著提高了页粒度 DRAM 缓存的带宽效率。

（3）通过结合基于页表的页映射管理和带宽高效的缓存替换策略，Banshee 显著提升了内包 DRAM 带宽效率。与三种其他先进的 DRAM 缓存设计相比，Banshee 的表现优于最好的设计（Alloy Cache [50]）15.0%，同时减少了 35.8% 的内包 DRAM 流量。

 

Background

论文速览采用AI翻译，部分名词有误，未作修正，意会即可。如内包外包等，即片上片外。

在大数据分析、机器学习和高性能计算等应用领域，数据集的规模不断增加。对于这些应用，内存带宽可能成为主要的性能瓶颈。为了满足这些应用对高内存带宽的需求，内包 DRAM 被集成到了 CPU 和 GPU 中，在一些现有系统中，它们被作为缓存进行管理 [2, 56]。

内包 DRAM 的带宽应谨慎使用，以获得最佳性能。这是因为一些经过精心优化的应用程序可以充分利用内包 DRAM 带宽，如果传输应用程序未使用的数据（例如，DRAM 缓存元数据、因过度缓存替换而产生的额外流量），可能会限制系统性能。尽管内包 DRAM 带宽正在增长，但芯片的计算能力也在提升。我们预计在近期内，带宽/计算比率不会发生剧烈变化。因此，提高 DRAM 缓存的带宽效率将有利于整体系统性能。为了更加具体地说明这一点，我们计算了 Nvidia P100（Pascal）系统（0.14 B/FLOP）[4]、Nvidia V100（Volta）系统（0.12 B/FLOP）[6] 和 Intel Knights Landing 系统（0.12 B/FLOP）[56] 的带宽/FLOPS2 比率。我们发现，尽管这三种系统的内包 DRAM 带宽相差 2 倍，但它们的比率非常相似。这表明，随着额外的 DRAM 带宽可用，计算能力也在增加。

在本节中，我们将讨论 DRAM 缓存的设计空间，并说明之前的方案在这个空间中的位置。我们展示了之前方案在两个主要设计考虑方面的带宽低效性：1）跟踪缓存内容，即映射（第 2.1 节）；2）更改缓存内容，即替换（第 2.2 节）。在我们的讨论中，我们假设处理器具有一个在细粒度（64B）管理的 SRAM 最后级缓存（LLC）。物理地址以粗粒度（4KB 页）静态映射到内存控制器（MC）。我们还假设内包 DRAM 类似于第一代高带宽内存（HBM）[29, 46]。内存控制器和 HBM 之间的连接宽度为 16B，但最小数据传输大小为 32B。因此，读取一个 64B 的缓存行加标签需要至少 96B 的传输。我们还假设内包和外包 DRAM 具有相同的延迟 [55]。

 

Tracking DRAM Cache Contents

对于每个 LLC 未命中，内存控制器需要确定是访问内包 DRAM 还是外包 DRAM。因此，必须在系统中存储每个数据块所在位置的映射。映射可以通过标签或通过虚拟到物理地址的重映射来管理。

Using Tags

跟踪缓存内容的最常见技术是显式存储标签集，即通过每个数据块的地址中的位来唯一标识该块。然而，当 DRAM 缓存很大时，标签存储的开销可能会很大。例如，一个 16 GB 的 DRAM 缓存，如果以细粒度（或粗粒度）管理，需要 512 MB（或 8 MB）的标签存储。因此，许多先进的 DRAM 缓存设计将标签存储在内包 DRAM 中。这些设计会消耗额外的 DRAM 带宽用于与 DRAM 缓存访问相关的标签查找。表 1 总结了几种先进的 DRAM 缓存设计的特点，其中包括两个将标签存储在内包 DRAM 中的设计：Alloy Cache [50] 和 Unison Cache [32]。

 

Using Address Mapping

另一种用于跟踪 DRAM 缓存中数据的技术是通过页表中的虚拟到物理地址映射机制 [38, 44]。在这些设计中，数据始终以页粒度进行管理。物理地址空间在内包 DRAM 和外包 DRAM 之间进行划分。虚拟页地址映射到哪里可以通过其物理地址严格确定。因此，系统不像前面讨论的基于标签的设计那样执行标签查找。

在这些基于页表的设计中，有两个主要挑战。第一个挑战是 TLB 一致性。每当页面被插入或从 DRAM 缓存中替换时，其虚拟到物理的映射会发生变化。这个映射的变化必须在系统中的所有 TLB 中保持一致，以确保没有 TLB 存储错误或过时的映射。在当前系统中，这需要执行全局 TLB 清除操作，即系统中的每个核心都接收到一个中断并刷新其本地 TLB。由于 TLB 清除通常需要多个微秒来服务 [58]，频繁的 TLB 清除会严重影响性能。

基于页表的设计中的第二个主要挑战是我们所说的地址一致性。当虚拟页被重新映射时，其物理地址会发生变化。为了避免系统中任何缓存中的数据不正确，所有属于重新映射物理页面的缓存行必须从所有片上 SRAM 缓存中移除。否则，如果后来将另一个虚拟页面映射到相同的物理页面，核心可能会读取到 SRAM 缓存中的错误值，从而导致执行错误。每次页面重新映射时移除这些包含过时物理地址的缓存行会带来显著的性能开销。

 

 

DRAM Cache Replacement

缓存替换是内包 DRAM 设计中的另一个重要挑战。我们将讨论先前工作中提出的硬件和软件方法。

Hardware-Managed

硬件管理的缓存能够在每次 DRAM 缓存未命中时做出替换决策，因此可以快速适应不断变化的工作负载行为。许多设计，包括 Alloy Cache、Unison Cache 和 TDC，在每次缓存未命中时总是将获取的数据插入到 DRAM 缓存中。虽然这是 SRAM 缓存的常见做法，但对于 DRAM 缓存来说，由于带宽有限，所产生的额外替换流量是昂贵的。一些先前的设计尝试通过一种随机机制 [20, 33] 来减少替换流量，即每次访问时以小概率发生替换。我们将在 Banshee 中使用类似的技术（参见第 4.2 节）。对于页面粒度的 DRAM 缓存设计，频繁的替换还会导致过度获取（over-fetching），即整个页面被缓存，但在驱逐之前，只有对应的部分缓存行被访问。这会导致不必要的 DRAM 流量。由于替换产生的 DRAM 流量甚至可能比完全禁用 DRAM 缓存时还要高，从而导致性能的大幅下降，如 [33] 所示。为了解决这个问题，先前的工作使用了扇区缓存设计 [40, 52]，并依赖于足迹预测器 [28, 35] 来确定在缓存未命中时应该加载页面内的哪些缓存行。我们将在第 6 节中展示 Banshee 如何在这些设计中提高带宽效率。

替换策略必须选择一个受害者进行驱逐。Alloy Cache 是直接映射的，因此只有一个受害者可以被替换。传统的集合关联缓存（例如 Unison Cache）使用最近最少使用（LRU）[32] 或频率基础替换（FBR）[33] 策略。这些策略需要额外的元数据来跟踪缓存行的相对访问时间或访问频率。加载和更新这些元数据会产生显著的 DRAM 流量。TDC 实现了一个完全关联的 DRAM 缓存，但使用了 FIFO 替换策略，这对于某些应用会降低命中率。由于 TDC 在每次缓存未命中时按页面粒度进行替换，它不能高效地支持大页面 [38]。

Software-Managed

基于软件的缓存替换算法（例如 HMA [44]）可能相对复杂。因此，它们在预测应该保留哪些数据在 DRAM 缓存中时，可能比硬件机制表现更好。然而，它们会带来显著的执行时间开销，因此通常仅周期性地调用（例如 [44] 中的做法）。这使得它们在适应变化的应用行为时较慢。

 

BANSHEE DRAM CACHE DESIGN

Banshee 的目标是最大化内包 DRAM 和外包 DRAM 的带宽效率。在本节中，我们将描述 Banshee 如何跟踪 DRAM 缓存的内容。关于 Banshee 如何处理缓存替换，我们将在第 4 节中进行详细说明。

Banshee Architecture

图 1 显示了 Banshee 的架构。为了简化起见，我们假设内包 DRAM 和外包 DRAM 共享相同的内存控制器。如果它们具有独立的内存控制器，我们的技术同样适用。内包 DRAM 作为内存侧缓存，并且与片上 SRAM 缓存不是包含关系。硬件和软件进行了三项主要更改，这些更改在图中以红色标出。首先，扩展了页表项（PTE）和 TLB 条目，以指示一个页面是否被缓存，如果被缓存，还会指明它被缓存的位置。其次，新增了一个硬件结构——标签缓冲区（Tag Buffer），用于内存控制器中的高效 TLB 一致性管理。第三，内存控制器中的逻辑被更改，以支持缓存内容跟踪和缓存替换，具体内容我们将在下文中描述。

Banshee 以页为粒度管理 DRAM 缓存，并使用页表和 TLB 来跟踪 DRAM 缓存内容，类似于 TDC [38] 和 HMA [44]。然而，与之前基于页表的设计不同，Banshee 使用相同的地址空间来处理内包和外包 DRAM，以解决地址一致性问题（在 2.1.2 节讨论）。Banshee 在相应的页表项（PTE）和 TLB 条目中增加了额外的位，用来指示一个页面是否被缓存。这个简单的改动解决了地址一致性问题。因为当页面被重新映射时，它的物理地址不会改变，因此在 SRAM 缓存中存在的页面的所有缓存行总是具有一致的地址。

为了简化 TLB 一致性问题，Banshee 实现了一种懒惰的软件/硬件协同 TLB 一致性协议，使用 Tag Buffer 存储信息。最近重新映射的页面信息仅存储在 Tag Buffer 中，而不会更新到相应的 PTE 和 TLB 条目。所有内存请求都可以通过检查内存控制器中的 Tag Buffer 来找到最新的映射信息。当 Tag Buffer 被填满时，存储在其中的映射信息将通过软件支持传播到 PTE 和 TLB 条目中。因此，Banshee 通过这种机制显著降低了 TLB 一致性的成本。

 

Page Table and TLB Extension

Banshee 中的 DRAM 缓存是集合关联式的。每个 PTE 都扩展了两条映射信息，指示页面是否以及在哪里被缓存：

1）一个新的缓存位指示页面是否驻留在 DRAM 缓存中，2）一些新的位指示页面缓存的方式。

每个 L1 缺失都会将映射信息（即缓存位和方式位）从 TLB 带入内存层次结构。如果请求在到达内存控制器之前被满足，缓存位和方式位将被简单忽略。如果请求错过了 LLC 并到达内存控制器，首先会查找 Tag Buffer 中该页面的最新映射。Tag Buffer 缺失意味着请求附带的信息是最新的。对于 Tag Buffer 命中，请求附带的映射信息将被忽略，并使用 Tag Buffer 中的正确映射信息。来自 L2 或更高层次（如 L3）的硬件预取请求会带来一些复杂性。这些缓存通常在物理地址空间中操作，因此无法访问 TLB 来获取映射信息。然而，在大多数系统中，这类预取会停留在页面边界处 [5]，因为物理地址空间中超出该边界的数据可能与相邻虚拟页中的数据无关。此外，这些预取通常由核心或 L1 缓存发出的需求或预取请求触发（直接或间接）。因此，我们可以将触发请求的映射信息复制到它所触发的预取请求中。

 

Tag Buffer

Banshee 为每个内存控制器添加了一个 Tag Buffer。Tag Buffer 存储属于该内存控制器的最近重新映射页面的映射信息。图 2 显示了 Tag Buffer 的组织结构。它被组织为一个小型的集合关联缓存。物理页面号作为标签。有效位指示该条目是否包含有效的映射。对于有效条目，缓存位和方式位指示页面是否存在于 DRAM 缓存中以及其存在的位置。重新映射位（remap bit）用于表示一个页面的重新映射信息未在该页面的页面表项中更新。重新映射位启用了我们接下来讨论的优化。

与到达内存控制器的请求不同，LLC 脏数据驱逐并不携带映射信息。对于这些情况，如果被驱逐的缓存行的映射信息不在 Tag Buffer 中，那么内存控制器需要查询存储在 DRAM 缓存中的标签（参见第4.1节）来确定请求是命中还是未命中。这些标签查询操作会消耗 DRAM 缓存带宽，可能会影响性能。

为了减少这种标签查询，我们利用 Tag Buffer 中原本为空的条目来存储缓存于 LLC 中的页面的映射信息。在 LLC 未命中且 Tag Buffer 也未命中的情况下，我们会为该页面在 Tag Buffer 中分配一个条目：该条目的有效位被设置为 1，表示有用的映射，但重新映射位（remap bit）设置为 0，表示该条目存储的是与 PTE 中相同的映射信息。对于 Tag Buffer 命中的情况，脏数据驱逐时无需查询 DRAM 缓存，从而减少 DRAM 流量。其重新映射位为 0 的条目可以从 Tag Buffer 中替换出去，而不影响正确性（我们在这些条目中使用 LRU 替换策略）。

 

Page Table and TLB Coherence

随着 Tag Buffer 的填充，存储在其中的映射信息需要传播到页面表，以便为未来的缓存替换腾出空间。由于 Tag Buffer 只包含页面的物理地址，而页面表是通过虚拟地址进行索引的，因此我们需要一种机制来识别所有与物理地址对应的 PTE。TDC 提出了一个基于硬件的反向页面表来将页面的物理地址映射到其 PTE【38】。然而，这种解决方案无法处理页面别名问题，其中多个虚拟页面映射到同一个物理页面。为了识别是否存在别名问题，必须访问操作系统中的一些内部数据结构（即页面描述符），这会产生显著的额外开销。我们观察到，现代操作系统已经具有一个反向映射机制，可以快速识别与物理页面关联的 PTE，无论是否存在别名问题。这个功能对于实现主内存和二级存储（例如硬盘或固态驱动器）之间的页面替换是必要的，因为回收主内存页面框架需要访问并更新所有对应的 PTE。现有系统中的反向映射通常是通过反向页面表（例如 Ultra SPARC 和 PowerPC 中的实现【57】）或特殊的反向映射机制（例如 Linux【12】）来实现的。

在 Banshee 中，我们使用这种反向映射来识别映射到给定物理页面的 PTE。当 Tag Buffer 填充到预定的阈值时，它会向随机选择的核心发送一个中断。接收中断的核心执行一个软件例程。具体来说，核心从所有内存控制器的 Tag Buffer 中读取所有条目（那些重新映射位被设置为 1 的条目）（这些条目是内存映射的）。每个 Tag Buffer 条目中存储的物理地址用于通过反向映射机制识别相应的 PTE。然后，根据 Tag Buffer 条目中的值，更新每个 PTE 的缓存位和方式位。在此过程中，Tag Buffer 被锁定，以防止发生 DRAM 缓存替换。然而，DRAM 仍然可以被访问，并且不需要停止程序（与先前的工作【44】不同）

在所有 Tag Buffer 条目已传播到 PTE 后，软件例程会发出全系统的 TLB 清除操作以强制执行 TLB 一致性。之后，会向所有 Tag Buffer 发送一条消息，清除所有条目的重新映射位。请注意，为了减少脏数据驱逐时的标签探测，映射信息可以保留在 Tag Buffer 中（参见第 3.3 节）。这里描述的 TLB 一致性机制强制执行缓存位和方式位的一致性。这是唯一可以暂时不一致和过时的两个字段。PTE 的其他字段（例如物理地址、权限位）始终保持一致，因为 Banshee 不会更改它们。因此，当页面表和 TLB 不一致时，操作系统功能（例如调度）对这些 PTE 字段的需求不会受到影响。

根据系统的软件和硬件，上述机制可能需要数万个周期【12】。然而，由于这个成本仅在 Tag Buffer 快满时才需要支付，因此 TLB 一致性的成本得到了摊销。此外，正如我们将在第 4 节看到的，页面频繁重映射会因高替换流量而导致性能下降。因此，我们的设计尝试限制页面重映射的频率，进一步减少这种 TLB 一致性发生的次数，从而降低其成本。

 

BANDWIDTH-EFFICIENT CACHE REPLACEMENT

如第 2.2 节所讨论的，缓存替换策略会显著影响在封装内和封装外 DRAM 中的流量。对于页面粒度的 DRAM 缓存设计来说，这一点尤为重要，因为在一个页面内会出现过度预取的问题。在本节中，我们提出了一种新的基于频率的替换（FBR）策略，通过采样来实现良好的缓存命中率，同时最小化 DRAM 流量。我们首先在第 4.1 节讨论 DRAM 缓存中数据和元数据的物理布局。然后，在第 4.2 节中描述 Banshee 的缓存替换算法。

DRAM Cache Layout

许多先前提出的基于标签的 DRAM 缓存设计将元数据（例如，标签、LRU 位）和数据存储在同一 DRAM 行中，以利用行缓冲区的局部性，因为它们总是将元数据与数据一起加载。对于细粒度的 DRAM 缓存来说，这种组织方式是高效的。然而，对于页面粒度的 DRAM 缓存来说，页面和标签在 DRAM 行缓冲区中无法很好对齐【32】，这导致了额外的设计复杂性和低效率。

在 Banshee 中，并不是每个主存请求都需要访问元数据。因此，我们将元数据和数据分开存储，以便更好的对齐。图 3 显示了一个 DRAM 缓存的数据行和元数据行的布局，假设行缓冲区的大小为 8 KB，页面大小为 4 KB。每个 DRAM 缓存集的元数据占用 32 字节，在标签行中存储。对于一个 4 路关联的 DRAM 缓存，每个集包含 16 KB 的数据和 32 字节的元数据，因此元数据存储的开销仅为 0.2%。

Banshee 为每个缓存的页面（图 3 中的灰色部分）存储元数据，同时也为它考虑缓存的一组候选页面存储元数据。每个页面的元数据包括一个标签和一个计数，表示该页面的访问频率。缓存页面的元数据还包括有效位和脏位。直观上，访问最频繁的页面（即频率计数较大的页面）应该保留在 DRAM 缓存中。在未缓存的页面中，最频繁访问的页面应该被追踪为候选页面。

Bandwidth-Aware Replacement Policy

FBR 策略会带来 DRAM 缓存流量，原因有 1) 读取和更新频率计数器，以及 2) 替换数据。在 4.2.1 节中，我们介绍了一种基于采样的计数器维护方案，以减少计数器读取/更新的流量。在 4.2.2 节中，我们讨论了我们新的带宽感知替换算法，旨在在保持良好的缓存命中率的同时，最小化替换流量。

Sampling-Based Counter Updates

在标准的 FBR 策略 [36, 51] 中，每次访问页面时都会增加该页面的频率计数器。我们观察到，增加每次访问的计数器并不是必要的。相反，在 Banshee 中，每次访问只会以一定的采样率更新频率计数器。例如，对于 10% 的采样率，频率计数器每 10 次内存访问更新一次。这将计数器读取/更新流量减少了 10 倍。此外，由于采样减慢了计数器的递增速率，我们可以使用更少的位来表示每个计数器。虽然通过这种采样更新计数器可能导致“热”页面检测不准确，但大多数应用程序都表现出一定的空间局部性。当对 64 字节的 L1 缓存行的请求在 DRAM 缓存中未命中时，属于同一页面的其他缓存行（对于 4 KB 的页面，应该有 64 个缓存行）很可能会很快被访问。每个访问都有机会更新该页面的频率计数器。事实上，如果不进行采样，我们发现计数器会很快达到较大的值，且只有高位对替换决策有影响。采样有效地“丢弃”了存储和跟踪每个计数器低位的需求，因为低位通常没有有用信息。

我们进一步观察到，当 DRAM 缓存工作良好时，即缓存未命中率较低时，替换应该是少见的，计数器也不需要频繁更新。因此，Banshee 使用一种自适应采样率，该采样率是缓存未命中率（动态跟踪）与常数采样系数的乘积。

Replacement Algorithm

对于粗粒度的设计，DRAM 缓存替换可能会非常昂贵，特别是在内存流量方面。每次替换时，内存控制器都会将整个页面从包外 DRAM 转移到包内 DRAM。如果一个页面的空间局部性较差（即该页面在被替换之前只经历了很少的访问），则由于替换引起的包内和包外 DRAM 流量可能会比没有 DRAM 缓存时还要高。这会导致性能下降（参见第六节）。

基于频率的替换本身并不能解决这个问题，因为该算法可能会反复将缓存中访问频率最低的页面替换为访问频率更高的候选页面。当页面的计数器值相似时，可能会触发大量这种替换，导致缓存抖动，从而浪费宝贵的包内和包外 DRAM 带宽。

Banshee 通过仅在新页面的计数器值大于潜在替换页面的计数器值达到一定阈值时才进行替换，从而解决了这个问题。这确保了刚从 DRAM 缓存中驱逐出去的页面在重新进入缓存之前，预计会被访问（2 × 阈值/采样率）次（即页面的频率计数器将超过缓存页面的频率计数器达到阈值）。这避免了页面频繁进出缓存的情况。

需要注意的是，减少替换的频率也会增加 Tag Buffer 溢出的时间，从而间接减少 TLB 一致性的开销。

算法 1 展示了 Banshee 完整的缓存替换算法。对于每个来自 LLC 的请求，首先生成一个随机数来确定当前的访问是否应该被采样（第 3 行）。如果不进行采样，这是常见的情况，则请求会直接访问适当的 DRAM（包内或包外）。此时不会访问元数据，也不会发生替换。如果当前的访问被采样，则相应集合的元数据将从 DRAM 缓存加载到内存控制器（第 4 行）。如果当前访问的页面在元数据中存在（第 5 行），则其计数器会增加（第 6 行）。如果当前页面是候选页面之一，并且其计数器比缓存页面的计数器大于一个阈值，则应进行缓存替换（第 7-9 行）。默认情况下，阈值是页面中缓存行数与采样系数的乘积除以二（阈值 = 页面大小 × 采样系数 / 2）。直观地讲，这意味着只有当替换页面的好处大于替换操作的成本时，才会进行替换。如果计数器在增加后饱和，则所有元数据中的计数器会通过硬件的移位操作被减半（第 10-15 行）。

如果当前页面在元数据中不存在（第 17 行），则会随机选择一个候选页面作为牺牲品（第 19 行）。然而，Banshee 并不总是替换选中的牺牲品：相反，当前页面只能以一定的概率替换选中的牺牲品，且这个概率随着牺牲品计数器的增大而减小（第 20-24 行）。通过这种方式，温暖的候选页面被驱逐的可能性较小。

 

后续扩展和实验部分略去