Colloid [SOSP'24]

【Title】Tiered Memory Management: Access Latency is the Key !

【开源项目链接】https://github.com/host-architecture/colloid

Comment

非常有价值的问题和方向，在许多最近的分层内存/异构内存都能捕捉到这种idea的一些影子。最典型的就是带宽饱和时，延迟的指数级增加。文章还额外指出了即使带宽不饱和，延迟也会增加（按照论文图描述，延迟随着内存争用强度增强接近线性增加）。这就使得传统意义上的性能层/快速层/默认层，可能会具备容量层/慢速层/备用层更高的延迟，从而影响到系统性能和吞吐量。从而热点数据不应该集中在性能层/快速层/默认层。

本文第一作者Midhul Vuppalapati大佬本身是做过网络系统（拿过SIGCOMM最佳学生论文）的，因此对于这种网络吞吐和延迟的优化问题会有非常深刻的见解。论文的idea看似简单，但是蕴含了非常多的排队理论相关的知识和细节，也涵盖了一些统计学的优化方法。论文通过CHA硬件计数器计算上几段时间片段（指数加权移动平均）访问延迟和不同层级请求访问概率，计算总体平均延迟p。定义两个watermarks代表延迟上下限，以二分的方式将p收敛到p*最佳平衡点，并对一些极端情况（无法收敛）重置watermarks。并设计了动态迁移限制，优化页面迁移产生的额外流量。

是一个高质量工作，值得学习（但是我大概（现在）是学不会的，涉及到的统计学和网络优化确实超过了当前的知识范围）。

Abstract

分层内存体系结构的出现重新引发了对内存管理的关注。最近关于分层内存管理的研究在访问跟踪、页面迁移和动态页面大小确定的机制上有所创新；然而，它们都采用了相同的页面放置算法——将“最热点”页面打包到默认层（具有最低硬件指定内存访问延迟的内存层）。这一做法隐含了一个假设：尽管默认层服务于“最热点”页面，但其访问延迟低于其他内存层。然而，这一假设与现实情况相差甚远：计算机体系结构领域普遍的知识，在多请求并行处理的实际场景下，内存访问延迟可能显著高于硬件指定的延迟。我们发现，即使在中等负载下，默认层的访问延迟也可能膨胀至替代层延迟的2.5倍；在这种情况下，最先进的内存分层系统的性能可能比最优性能差2.3倍。

真实系统中，多个内存请求可能同时发出（称为“多请求并行”），这会引发

• 资源争用：多个请求可能需要访问同一内存控制器、通道或银行，导致排队等待。

• 调度延迟：内存控制器需要根据调度策略（如First-Ready, First-Come-First-Served，FR-FCFS）确定请求处理顺序，这会增加请求的服务时间。

• 冲突开销：如果多个请求访问不同的内存行，可能需要额外的预充电和行激活操作，从而增加访问时间。

由于上述原因，实际的内存访问延迟通常比理论值大得多。例如，在高负载下（并发请求数量较多），内存延迟可能成倍增长。这种延迟膨胀尤其明显在内存层次结构中速度较快的层，因为这些层的低延迟可能会吸引更多请求，进一步加剧拥塞。

Colloid 是一种内存管理机制，体现了平衡访问延迟的原则——跨层的页面放置应当以平衡其平均（Loaded）访问延迟为目标。为了实现这一原则，Colloid 在每个层次的内存访问延迟测量机制和页面放置算法上进行了创新，这些算法决定了每个层次中应放置哪些页面。我们将 Colloid 集成到三个最先进的内存分层系统 HeMem、TPP 和 MEMTIS 中。通过对各种工作负载的评估，结果表明，Colloid 一贯地使底层系统能够实现接近最优的性能。

Introduction

现代内存密集型应用程序，如内存数据库、图处理引擎和机器学习框架，受益于更大的内存容量和内存互连带宽。事实上，内存已经成为云服务器成本中越来越大的一部分（例如，Meta约为37%，微软Azure约为50%）。不幸的是，经典内存架构的技术趋势——通过DDR内存互连将DRAM模块暴露给处理器——已经停滞不前，使得以具有成本效益的方式扩展内存容量和内存互连带宽变得困难。内存互连带宽的情况尤其严峻：随着核心数量和每核心并发性的持续增加，内存互连的竞争变得越来越激烈。例如，在最近几代英特尔服务器中——英特尔Cascade Lake（2019）、Ice Lake（2021）和Sapphire Rapids（2023）处理器的流量分别是内存互连带宽的2.98倍、3.31倍和4.5倍；对于AMD Genoa（2023），处理器生成的流量是内存互连带宽的9.37倍。

经典内存架构达到了其扩展的极限，这促使了分层内存架构的出现。这些架构除了提供经典的DDR附加内存外，还通过替代的内存互连技术向处理器暴露新的缓存一致性内存形式。例如，CXL使处理器能够通过外设互连技术的串行接口（如PCIe）访问缓存一致性内存，从而启用了一个新的内存层次，具有更高的内存带宽，但延迟更高。分层内存架构的出现引发了对内存管理的重新关注，因为跨内存层次的页面放置对应用性能有着至关重要的影响。

针对分层内存架构的内存管理的近期研究提出了许多创新的机制，如访问跟踪、页面迁移、动态页面大小确定等；然而，它们都采用了相同的页面放置算法——将尽可能多的热点页面放入具有最低未加载访问延迟的内存层（称为默认层 [有的论文称为性能层 Performance Tier]），其余页面则放入其他层次。该页面放置算法基于一个核心的隐性假设：尽管默认层服务于最热点的页面，但其内存访问延迟低于其他层次的延迟。然而，这一假设与现实情况相去甚远：计算机体系结构界普遍常识，在多请求并行处理的实际场景中，内存访问延迟可能显著大于unloaded延迟，即使内存互连带宽远未饱和。我们称这种情况为内存互连争用memory interconnect contention。事实上，我们证明，即使在中等负载下，内存互连争用也会导致默认层的访问延迟膨胀达到5倍。考虑到现有CXL硬件的访问延迟，这种膨胀会导致默认层的延迟比其他层高出2.5倍。我们展示了，在内存互连争用的情况下，最先进的内存分层系统的性能可能比最优性能差2.3倍。

Unloaded latency（未加载延迟）是指在没有其他并发内存请求的情况下，内存访问的基本延迟。它代表了内存系统在没有负载时的响应时间，也就是内存访问的最理想状态下的延迟。在这种情况下，内存访问路径上的延迟仅包括硬件的固有延迟（如内存芯片的访问时间、传输延迟等），而不受其他请求或竞争的影响。Unloaded latency（未加载延迟）是一个理论上的最小延迟，通常用于评估内存系统的基本性能。

与之相对的是loaded latency（加载延迟），即在有多个并发请求或其他系统负载的情况下，内存访问的延迟。这种情况下，内存访问延迟可能因为请求的排队、内存互连带宽的争用、资源的竞争等因素而增大。

我们提出了Colloid，这是一种分层内存管理机制，体现了平衡访问延迟的原则——跨层的页面放置应当以平衡它们的平均（加载后的）访问延迟为目标。平衡访问延迟的原则基于一个简单的观察：将更多热点页面放入访问延迟较低的层次，可能会增加该层的访问延迟，并减少其他层次的访问延迟（从而使各层次的访问延迟更加平衡）；然而，这样做将减少整体的平均内存访问延迟。这个观察非常重要，因为每个处理器核心能够保持一定数量的内存请求处于飞行状态；因此，最小化平均内存访问延迟可以直接最大化内存访问吞吐量和应用层性能（§3）。

平衡访问延迟的原则提供了一种统一的内存管理方法。首先，它自然地捕捉了各层的未加载延迟——如果默认层的（加载后的）访问延迟小于其他层的延迟，那么平衡访问延迟就要求增加对默认层的访问比例，从而与现有系统中的页面放置算法趋同。其次，它捕捉到即使在内存带宽远未饱和的情况下，内存互连争用也可能发生——在CPU到内存的数据路径中的任何点发生内存互连争用，都会导致相应层的访问延迟增加，因此，在基于这一原则做出页面放置决策时，内存互连争用将自动被考虑在内。

基于平衡访问延迟原则的内存管理改变了分层内存管理问题的核心结构。事实上，单纯将尽可能多的热点页面放入默认层已不再是最优策略，因为将热点页面放入其他层可能会提高应用性能。因此，我们需要新的机制来测量内存访问延迟，以及新的页面放置算法来决定将哪些页面放置到每个层次。Colloid在这两个方面进行了创新。首先，Colloid展示了现代服务器在CPU到内存的数据路径中有一些有利位置，可以利用这些位置进行低开销的每层队列占用率和请求到达率的测量；通过使用Little定律，这使得Colloid能够在细粒度的时间尺度上测量每层的内存访问延迟。其次，Colloid提出了一种新的页面放置算法，该算法以每层的内存访问延迟和每个页面的访问跟踪信息为输入，利用平衡访问延迟的原则来有效地决定将哪些（热点和冷页）页面放置到每个层次。

Little定律（Little's Law） 是排队理论中的一个基本定理，描述了在稳定系统中，队列长度、等待时间和系统处理率之间的关系。它可以用以下公式表示：

$$L=\lambda W$$

L：系统中的平均排队长度（平均客户数或请求数）。

λ：到达率，即单位时间内到达系统的平均请求数。

W：系统中的平均等待时间（即一个请求在系统中逗留的平均时间）。

在一个稳定的排队系统中，无论系统的具体细节如何，平均排队长度与到达率和平均等待时间的乘积是恒定的。该定律不依赖于具体的分布或系统的排队方式，因此在很多不同类型的排队系统中都适用。

在内存系统中，假设每个请求的到达率为 λ，请求在内存系统中的平均等待时间为 W，那么内存队列中的平均请求数 L 就等于 λW。这可以用来估算内存访问延迟与队列中的请求数量之间的关系。

Colloid 设计兼容任何不同层次不共享内存通道的缓存一致性分层内存架构；这包括本地 DDR 附加内存、通过处理器互连暴露的远程插槽内存、CXL 附加内存和高带宽内存。Colloid 设计还与现有的访问跟踪、页面迁移和页面大小确定机制兼容，从而使 Colloid 可以轻松集成到现有的内存分层系统中。我们通过将 Colloid 与先进的内存分层系统集成，展示了这一点。我们使用实际应用程序和标准工作负载生成器，对一系列静态和时变工作负载进行了评估，涵盖了不同的内存互连争用、核心数、对象大小、内存访问延迟以及读/写特性。在所有评估的场景中，我们发现 Colloid 能够使每个系统在内存互连争用强度不同的情况下实现接近最优的性能；我们还发现，Colloid 不会影响系统在时变工作负载下的收敛时间。

Motivation

在本节中，我们研究了三种最先进的内存分层系统——HeMem [48]、TPP2 [35] 和 MEMTIS [29]，并展示了以下内容：

• 在多个内存请求并行处理的实际情况下，默认层的访问延迟可能是其空载延迟的5倍。我们将这种情况称为内存互连争用状态（在§3.1中精确定义）。在我们的设置中，内存互连争用状态下，默认层的延迟可能膨胀到比替代层的延迟高出2.4倍。根据实际CXL硬件报告的延迟数据，默认层访问延迟的5倍膨胀将对应于比替代层高出2.5倍的延迟。

• 现有的内存分层系统将尽可能多的热页放入默认层。在内存互连争用状态下，这实际上是一种次优策略，导致这些系统的性能远低于最佳状态——对于HeMem、TPP和MEMTIS，性能分别比最佳性能差2.3倍、2.36倍和2.46倍。

Experimental Setup

Dual Socket Intel Xeon Platinum 8362 CPU，拥有32个核心，每个核心1.25MB的L2缓存

48MB的LLC缓存，8个3200MHz DDR4内存通道，每个通道连接一个DIMM。因此，所有通道的理论最大带宽为205GB/s。插槽之间通过一个UPI链接连接，理论最大带宽为75GB/s（每个方向）。

• 默认层（性能层）32GB 70ns延迟

• 替代层（容量层）96GB 135ns延迟

工作集由一个大小为72GB的虚拟连续缓冲区组成。该缓冲区的随机24GB区域构成热集

因此，热集适合放入默认层，而完整的工作集则不适合。核心1−15每个运行一个线程，按90%的概率从热集中随机选择一个64字节对象进行读取和更新（读写比为1：1），10%的概率从完整工作集中选择对象进行相同操作。核心31−32用于在内存分层系统中使用的采样和迁移线程。

这个是怎么做的 ? 怎么随机24GB ? 连续24GB ？

我们没有过度订阅CPU核心，因为我们的评估不侧重于现有系统的CPU开销评估；这已经在之前的工作中进行了研究。我们主要关注默认层的内存互连争用；在替代层的内存互连争用不会打破默认层延迟低于替代层延迟的假设——现有系统在这种状态下已经能理想地进行页面放置。

为了生成可控的内存互连争用，和之前的工作一样，我们在核心16−30上使用一个内存对抗进程，生成针对500MB缓冲区的顺序1：1读写内存流量，该缓冲区被绑定到默认层内存中。为了研究系统在稳态下的行为，并提供对观察结果的更深入见解，我们在整个实验过程中生成持续的内存互连争用；稍后我们将研究系统在内存互连争用动态变化下的行为。

“顺序1：1读写”指的是对内存缓冲区的访问是以读操作和写操作等比例进行的，每次读取和写入的数据量相等。

• 内存对抗进程是为了制造可控的内存互连争用而设计的进程。内存互连争用通常发生在多个进程或线程同时访问内存时，尤其是在多核系统中。当多个核心同时访问内存时，内存子系统（如内存控制器和内存互连）可能会成为瓶颈，导致内存访问延迟增加。通过设计一个进程，使其在多个核心上运行，并在内存中产生大量读写请求，可以模拟出这种内存争用的情况。这个进程通过顺序读写内存的方式，持续不断地向内存发送请求，从而增加内存控制器和内存互连链路的负载。

• 在这种实验设计中，顺序1:1读写流量意味着内存对抗进程会不断地进行读操作和写操作，并且读和写的比例是1:1。这是一种比较简单且均匀的内存访问模式，目的是避免其他复杂的内存访问模式（如随机访问等）可能带来的额外影响，使得内存争用的影响可以更容易被控制和评估。顺序访问意味着数据按照一个连续的顺序进行读写，而不是随机地访问不同的内存地址。这样可以产生稳定的内存访问模式，确保实验可重复性和可控性。

• 缓冲区绑定到默认层内存（通常是本地内存，位于某个CPU插槽上）意味着这个500MB的缓冲区被固定在某个特定的内存区域，而不是分散在多个内存层次或多个节点上。这样可以更容易模拟和测量特定层次内存（如本地内存）上的争用情况。绑定内存的目的是让内存对抗进程集中访问特定区域的内存，以便增加内存互连的竞争。这样，当有多个核心访问这个区域时，内存控制器和内存互连链路会发生争用，从而提高争用的强度和可控性。

• 为什么选择500MB缓冲区? 500MB的缓冲区是一个特定大小的内存区域，用于进行测试。这个缓冲区的大小可以根据实验的需求和目标进行选择。通常选择500MB是为了确保缓冲区足够大，可以模拟一定规模的内存访问负载，同时又不至于过大，以至于测试的时间过长或实验系统的资源消耗过大。

在实验中，我们通过改变运行内存对抗进程的核心数量来调整内存互连争用的强度——0×、1×、2×、3×强度分别对应0、5、10、15个核心，分别在独立运行时的内存带宽使用率为0%、51%、65%、70%。我们确保每个系统达到稳态，并测量稳态下的应用吞吐量。

我们通过手动将热集的0−100%（以10%的增量）放入默认层（使用Linux mbind API），来确定每种配置的最佳内存放置；剩余的热集放入替代层，默认层的任何剩余容量都用冷集中的随机选择页面填充。我们将这些手动放置中最高的吞吐量称为最佳应用吞吐量。

现有分层内存系统内存争用

Understanding impact of memory interconnect contention on existing memory tiering systems

图1展示了每个系统在稳态下的吞吐量以及在不同内存互连争用强度下的最佳吞吐量。对于0×内存互连争用强度，HeMem、TPP和MEMTIS的吞吐量分别在最佳吞吐量的1.5%、4.6%和10.1%以内。MEMTIS根据访问跟踪信息自动决定是否使用4KB或2MB页面来处理工作集的不同部分。在这里，由于将2MB页面拆分为4KB页面，虽然对于该工作负载没有益处，MEMTIS仍然导致额外的性能下降。这是因为它在工作负载尚未达到稳态时就做出了大页面拆分的决策，并且无法合并已拆分的页面；进一步分析发现，MEMTIS使用低效的机制扫描虚拟地址空间来执行页面合并，这比该工作负载达到稳态所需的时间要长得多。随着内存互连争用的增加，这些系统的吞吐量开始偏离最佳吞吐量。即使在1×内存互连争用强度下，HeMem、TPP和MEMTIS的吞吐量分别比最佳吞吐量低1.21倍、1.35倍和1.41倍。随着内存互连争用强度的增加，吞吐量差距进一步扩大，分别达到HeMem、TPP和MEMTIS的2.3倍、2.36倍和2.46倍。

• 这个图的意思就是随着内存争用强度上来，实际吞吐量离理论最佳吞吐量差距越来越大

在内存互连争用下，默认层的访问延迟可能超过备用层。我们通过使用处理器中的硬件计数器（缓存和主机代理，CHA）测量了每个层次的平均内存访问延迟，具体细节请参见§3.1。图2(a)展示了以往所有研究中假设的情况——即默认层在提供最热页面时，其内存访问延迟低于备用层——并不成立。事实上，我们发现，随着内存互连争用强度从1×增加到2×再到3×，默认层的访问延迟分别增加了2.5倍、3.8倍和5倍。在我们的实验设置中，这意味着默认层的访问延迟分别超过备用层1.2倍、1.8倍和2.4倍。访问延迟的增加是由于内存控制器中请求的排队，即使内存带宽远未饱和，这种排队现象也可能发生（更详细的讨论请参见§3.1）。

看起来是线性的。也就是说在带宽远未饱和的情况下，一旦发生内存争用，延迟会随着争用强度线性增长。结合其它论文的结果，当内存带宽接近饱和时，延迟会指数级增长。

现有系统在内存互连争用下仍然贪婪地将最热页面放置在默认层。图2(b)展示了GUPS在每个层次上的内存带宽使用情况，分别为最佳情况和现有的每种策略，使用Intel的内存带宽监控（MBM）功能测量。对于最佳情况，在1×、2×和3×内存互连争用强度下，默认层带宽分别仅占总带宽的25%、4.5%和4%——这对应于越来越大比例的热集被放置在备用层。当默认层的访问延迟超过备用层时，将整个热集放在默认层不再是最优选择。然而，对于HeMem、TPP和MEMTIS来说，无论内存互连争用强度如何，默认层带宽分别占总带宽的90%、75%和85%以上——这表明它们总是将大部分热集放置在默认层。这样的内存互连争用无关的页面放置方式是它们吞吐量远离最优的根本原因。具体来说，由于每个核心可以维持一定数量的在飞内存请求[55, 58]，每个核心的吞吐量（𝑇）由公式

给出，其中𝑁是飞行中的请求数量，𝐿是访问延迟，64是每个内存请求的大小（即1个缓存行）。从0×到3×内存互连争用强度，默认层访问延迟增加约3.5倍，且每个系统的吞吐量也相应减少了相似的倍数（HeMem为3.42倍，TPP为3.39倍，MEMTIS为3.29倍）。

In-flight memory requests （在飞内存请求）是指在处理器或内存系统中已发出的，但尚未完成的内存访问请求。换句话说，这些请求已经被提交到内存控制器或缓存，但还没有得到响应或者尚未完全处理。

Colloid

我们现在介绍Colloid设计。我们从Colloid设计的核心原则——平衡访问延迟的原则开始，讨论它是如何提供一种统一的方式来指导分层内存架构中的页面放置（§3.1）。然后，我们描述Colloid是如何将这一原则实现为端到端的分层内存管理机制的。具体来说，我们描述了一种高效的机制，用于在细粒度时间尺度上衡量每一层内存的访问延迟（§3.1），以及一个基于访问延迟的跨层动态页面放置新算法（§3.2）

我们考虑一种分层内存架构，如图3所示。所有层级的内存都暴露在主机物理地址空间中，并且可以通过CPU核心以缓存一致的方式通过load/store指令进行访问，同时遵循相同的内存一致性模型。延迟最小的层级被称为默认层级(Default)，其余的统称为备用层级(Alternative)。访问每个层级是通过独立的内存控制器实现的。上述特性适用于现有的分层内存架构，其中默认层级是本地的DDR直连内存，而备用层级则可以是通过处理器互连暴露的远程插槽内存、CXL连接内存和/或高带宽内存。

处理器与备用层级内存控制器之间的物理路径取决于备用内存层级的类型。图中以CXL连接内存为例，这里第一跳是处理器互连上的Root Complex，它通过PCIe通道连接到外部内存控制器。

为简明起见，我们假设内存分层系统中的所有机制（如访问跟踪、延迟测量、页面放置等）都在固定的时间间隔内周期性执行，这些时间间隔被称为量子（quantums）。正如我们在§4中讨论的，Colloid可以轻松集成到使用各种触发机制（例如页面错误）进行访问跟踪和/或页面放置的系统中。

Access Latency is the key

Colloid 设计的核心概念是平衡访问延迟的原则。该原则表明，跨层级的页面放置应以平衡它们的平均访问延迟为目标。

内存请求是指由核心发出的内存访问，这些访问未命中所有缓存层级并由默认层级或备用层级提供服务。我们将

• 无负载延迟(unloaded latency)定义为系统中仅存在一个正在处理的内存请求时的延迟；

• 有负载延迟(loaded latency)定义为存在多个并发内存请求时的延迟。

众所周知，由于 CPU 到内存数据路径中的争用，无论是默认层级还是备用层级，它们的有负载延迟都可能超出其无负载延迟：

• 当相应的互连带宽达到饱和时，由于请求排队，延迟可能会增加。带宽利用率在饱和点的表现难以事先精确表征，因为这取决于工作负载是以读取为主还是以写入为主，其差异可能高达 1.75 倍，并且可能比理论最大带宽低至 2.5 倍。

• 即使在互连带宽远未饱和的情况下，延迟也可能增加。这是由于内存模块内部层级中的争用引起的。例如，每个 DRAM 模块由多个banks组成；当这些banks之间的负载不均衡，以及每个bank内的访问模式缺乏局部性时，会导致请求在内存控制器处排队，从而导致延迟膨胀。

我们将内存访问延迟超出无负载延迟的情况统称为内存互连争用。我们定义一个页面在给定量子期间的访问概率为该页面的内存请求总数相对于该量子期间所有页面内存请求总数的归一化值。在一个给定量子期间，设默认层级和备用层级的平均访问延迟分别为 LD 和 LA，并设当前位于默认层级的页面的访问概率之和为 p。

平衡访问延迟的原则表明：

平衡访问延迟原则背后的逻辑是简单的。内存密集型应用的性能受限于整体内存访问吞吐量（即内存请求被服务的速率）。每个核心能够维持的最大在飞内存请求数量N受限于硬件缓冲区的大小（如行填充缓冲区）。因此，每个核心的平均内存访问吞吐量T与平均内存访问延迟L之间直接相关，公式为

其中64是每个内存请求的大小（即一个缓存行）。因此，最小化平均访问延迟可以最大化吞吐量。

平均内存访问延迟由下面的公式计算给出

总体而言，下面的等式 确实是最小化平均访问延迟并最大化吞吐量的平衡点。

平衡访问延迟的原则提供了一种统一的方法来指导跨层级的页面放置。

• 首先，它自动捕捉每个层级的无负载延迟——这些延迟分别包含在 LD 和 LA 中。例如，如果层级之间的无负载延迟差距较大，那么 LD 将始终小于 LA , 直到默认层级的争用程度增加，此时平衡访问延迟的原则将建议将更多的热点页面放置在默认层级。

• 其次，它捕捉每个层级的最大理论带宽。较高层级的带宽通常意味着可以处理更高的负载，同时将访问延迟保持在接近无负载延迟的水平（反之亦然）。如果任何层级的带宽达到饱和，那么其相应的访问延迟将增加，从而被平衡访问延迟的原则所捕捉。

• 第三，它捕捉内存互连争用的影响，即使带宽未饱和——内存访问数据路径中的任何排队都会导致相应层级的访问延迟增加，从而被纳入基于该原则的页面放置决策中。

平衡访问延迟的原则自然可以推广到具有多个层级的分层内存架构。如果所有层级的访问延迟不相等，那么通过将更多的热点页面放置在访问延迟最小的层级，可以减少平均访问延迟。因为这样做将增加该层级中页面的访问概率之和，同时相应减少其他访问延迟较高层级中页面的访问概率之和。类似的推理可以递归地应用于第二小访问延迟的层级，依此类推。如果所有层级的访问延迟相等，那么调整页面放置不会导致平均访问延迟的变化。因此，跨层级平衡访问延迟的状态仍然是最小化平均访问延迟并最大化吞吐量的平衡点。

测量访问延迟 近期的英特尔和AMD处理器提供了硬件计数器，可以低开销地测量每个层级的访问延迟。为了简洁起见，我们将重点讨论英特尔处理器。

无论工作负载的读写比如何，整体内存访问吞吐量主要依赖于内存读请求的延迟。

这是因为，即使是写请求，存储指令在缓存未命中时首先会生成内存读请求以将数据加载到缓存中；然后，数据在缓存中被更新，并且内存写入将在缓存回写时异步处理。因此，写请求的内存访问吞吐量直接依赖于内存读请求的延迟。为了实现这一点，我们只需要一种机制来测量内存读请求的延迟。

Colloid利用处理器的缓存和主代理（CHA，Cache and Home Agent）作为测量每个层级访问延迟的有利位置。CHA在处理缓存一致性时将内存层级抽象化，与系统的其他部分隔离。如图3所示，CHA被物理分割为多个切片（与核心共址），每个切片拥有主机物理地址空间的一个不重叠子集。当L1/L2缓存未命中时，内存请求首先会根据其物理地址转发到对应的CHA切片。CHA会查找L3缓存，在未命中的情况下，CHA会将请求排队到其缓冲区，并根据物理地址将请求转发到默认层级或备用层级。该请求会一直在CHA的队列中，直到从相应的层级得到服务。

Cache and Home Agent (CHA) 是一种在处理器架构中用于处理缓存一致性和内存访问的组件，尤其是在多层级缓存和分层内存架构中发挥重要作用。

• 缓存一致性管理： CHA 负责管理处理器的缓存一致性协议，确保多个核心对同一内存位置的访问不会产生冲突。例如，在多核处理器中，CHA 确保各个缓存中存储的数据是最新的，防止数据不一致的情况发生。

• 内存请求调度与路由： 当处理器的 L1 或 L2 缓存未命中时，内存请求会被转发到 CHA。CHA 根据请求的物理地址，将请求转发到更高层次的缓存（如 L3 缓存），如果仍然未命中，则将请求转发到系统的默认内存层级或备用内存层级（如 DRAM、HBM等）。

• 内存层级抽象： CHA 抽象化了多个内存层级的细节，隐藏了层级之间的差异，将内存访问过程简化，使得处理器能够透明地与不同类型的内存进行交互。这意味着，CHA 使得各个内存层级（例如本地缓存、远程内存）对于处理器而言是“透明”的，处理器只需关注如何高效地访问数据，而不需要知道数据究竟来自哪个具体层级的内存。

• 队列和请求管理： 在 CHA 中，当请求未命中并需要访问较低层级内存时，CHA 会将请求放入缓冲区（queue），等待内存层级响应。请求会被排队并按顺序处理，直到从目标内存层级获取数据并返回。

CHA硬件计数器使得可以低开销地对每种请求类型（读/写）和每个内存层级（如本地DDR内存、通过处理器互连暴露的远程插槽内存、CXL附加内存以及高带宽内存）进行队列占用率和请求到达率的测量。

所以是通过硬件计数器得到队列占用率和请求到达率

这些测量可以在比内存分层系统通常做页面放置决策的时间尺度更细粒度的时间尺度上进行。在给定的时间量子内，设 𝑂𝐷 和 𝑂𝐴 分别为默认层和备用层请求的平均队列占用率，𝑅𝐷 和 𝑅𝐴 分别为默认层和备用层请求的平均到达率（在该量子期间到达的内存请求数量除以量子时长）。𝑅𝐷 和 𝑅𝐴 与 𝑝（默认层中页面访问概率的总和）直接相关： 𝑝 = 𝑅𝐷 / (𝑅𝐷 + 𝑅𝐴)。

Colloid 使用Little's Law来测量每个层级的访问延迟（𝐿𝐷，𝐿𝐴）： 𝐿𝐷 = 𝑂𝐷 / 𝑅𝐷， 𝐿𝐴 = 𝑂𝐴 / 𝑅𝐴。由于Little's Law适用于任何队列不会无限增长的系统（对到达、服务行为、调度策略等没有任何假设），在CHA上应用它可以得到CHA到内存的平均延迟；近期的研究[58]对基于Little's law的内存访问延迟测量进行了深入验证。

测得的 𝐿𝐷 和 𝐿𝐴 中唯一缺失的成分是CPU到CHA的延迟。这个延迟只占CPU到内存访问延迟的极小一部分，因此可以忽略不计。

例如，在我们的硬件设置中，对于默认层的大约70ns未加载延迟，约5ns是CPU到CHA的延迟，约65ns是CHA到DRAM的延迟；在内存互连争用的情况下，后者的延迟会更高，从而使前者在总延迟中所占的比例更小。

简单总结一下这里出现的公式：

我们对队列占用率和请求到达率的测量应用了指数加权移动平均（EWMA）法，以平滑信号中的噪声。这种方法在工作负载变化时牺牲了略高的反应时间，以换取更好的稳定性。

指数加权移动平均（EWMA, Exponentially Weighted Moving Average）法 是一种统计学方法，用于平滑时间序列数据，减少短期波动，强调长期趋势。EWMA通过赋予较近的历史数据更高的权重，从而使得最近的数据点对最终平均值的影响更大。这种方法广泛应用于金融、信号处理、过程控制等领域，尤其在数据平滑和噪声过滤方面非常有效。

EWMA的基本原理

$$\begin{array}{c}\text{在}EWMA\text{中}，\text{每}\text{个}\text{数}\text{据}\text{点}\text{的}\text{权}\text{重}\text{是}\text{指}\text{数}\text{衰}\text{减}\text{的}。\text{假}\text{设}\text{有}\text{一}\text{组}\text{时}\text{间}\text{序}\text{列}\text{数}\text{据}:\\ x_1,x_2,x_3,\cdot \cdot \cdot ,x_t\\ \text{其}\text{中}t\text{是}\text{当}\text{前}\text{的}\text{时}\text{间}\text{步}\text{骤}，EWMA\text{的}\text{计}\text{算}\text{公}\text{式}\text{如}\text{下}：\\ S_t=\alpha \cdot x_t+(1-\alpha )\cdot S_{t-1}\\ S_t\text{是}\text{当}\text{前}\text{的}\text{平}\text{滑}\text{值}（\text{即}EWMA\text{的}\text{输}\text{出}）。\\ x_t\text{是}\text{当}\text{前}\text{时}\text{刻}\text{的}\text{原}\text{始}\text{数}\text{据}\text{点}\\ S_{t-1}\text{是}\text{上}\text{一}\text{时}\text{刻}\text{的}\text{平}\text{滑}\text{值}（\text{在}\text{第}\text{一}\text{次}\text{计}\text{算}\text{时}\text{可}\text{以}\text{认}\text{为}\text{是}\text{初}\text{始}\text{值}\text{或}\text{者}\text{是}\text{第}\text{一}\text{个}\text{数}\text{据}\text{点}）。\\ \alpha \text{是}\text{平}\text{滑}\text{因}\text{子}（\text{权}\text{重}\text{因}\text{子}），\text{其}\text{值}\text{在}0\text{到}1\text{之}\text{间}。\text{较}\text{大}\text{的}\alpha \text{表}\text{示}\text{对}\text{最}\text{近}\text{数}\text{据}\text{点}\text{赋}\text{予}\text{更}\text{高}\text{的}\text{权}\text{重}，\text{较}\text{小}\text{的}\alpha \text{则}\text{表}\text{示}\text{对}\text{过}\text{去}\text{数}\text{据}\text{点}\text{赋}\text{予}\text{更}\text{多}\text{的}\text{权}\text{重}。\end{array}$$

EWMA的特点

• 平滑效果：EWMA法通过给最近的观察值赋予更大的权重，能够有效减少噪声对数据的影响，并且对趋势变化更加敏感。

• 加权机制：与简单移动平均（SMA）不同，EWMA在计算时赋予每个数据点不同的权重，最近的数据点权重较高，而较早的数据点权重较低。这样可以更好地反映最新的变化趋势。

• 递归计算：EWMA公式是递归的，只需要保存最近的平滑值，不需要存储所有的历史数据，因此节省内存并且计算效率高。

Colloid page placement algorithm

Colloid页面放置算法以每个层次的访问延迟和每个页面的访问跟踪信息为输入，并根据这些信息调整页面在各个层次之间的放置。

Overview of the Colloid page placement algorithm

算法 1 展示了端到端的 Colloid 页面放置算法。在每个时间量子（quantum）的开始，它获取上一个时间量子内每个层次的平均队列占用率（𝑂𝐷, 𝑂𝐴）和平均请求速率（𝑅𝐷, 𝑅𝐴），计算每个层次的访问延迟（𝐿𝐷, 𝐿𝐴），以及当前默认层次页面的访问概率总和 𝑝。

然后，它根据平衡访问延迟的原则（§3.1）决定页面迁移的方向——如果默认层次的访问延迟小于备用层次的延迟，则将热页面从备用层次提升到默认层次；否则，将热页面从默认层次降级到备用层次（第 5-8 行）。

接下来，算法通过三步确定迁移哪些页面。首先，它计算在层次间转移多少访问概率，记作 Δ𝑝（第 9 行）。其次，它计算迁移限制。最后，它执行页面查找过程（第 10 行），目标是在以下两个约束条件下找到一组要在默认/备用层次进行降级/提升的页面：

• 它们的访问概率总和小于或等于 Δ𝑝；

• 它们的大小总和（字节数）不超过迁移限制或目标层次的可用容量

根据底层系统和访问跟踪机制的不同，可以实现不同的页面查找过程，具体实现我们将在 §4 中描述。最后，它通过底层的页面迁移机制迁移这些页面。

Desired shift in per-tier access probability

每个层次的访问概率的期望变化。在现有的内存分层系统中，决定在每个时间量子期间迁移哪些热页面是简单的——只需尽可能迁移更多的热页面（同时遵守迁移速率限制）。然而，对于 Colloid 来说，平衡访问延迟的原则改变了问题的结构——平衡点可能对应于将一部分热页面放置在默认层次，另一部分热页面放置在备用层次。因此，在每个时间量子期间迁移哪些热页面的决策变得不再简单。迁移过多的热页面可能会导致围绕平衡点的震荡，而迁移过少的热页面可能会导致达到平衡点的时间更长。Colloid 通过计算每个层次的访问概率的期望变化来确定要迁移的热页面集合。

为了找到所需的访问概率变化，Colloid 执行一种二分查找风格的过程（算法 2），使用两个水位标记

直观上，𝑝ℎ𝑖 为默认层的访问延迟可能小于备用层的访问延迟的访问概率之和的上界（该值是通过在前几个量子中进行的测量得到的）

而 𝑝𝑙𝑜 则为默认层访问延迟肯定小于备用层访问延迟的访问概率之和的下界。

上述直观定义表明，𝑝𝑙𝑜 应该初始化为 0，𝑝ℎ𝑖 应该初始化为 1，基于各层的空载访问延迟。此外，如果存在可行的平衡点 𝑝∗，它总是位于低水位和高水位之间——也就是说，𝑝𝑙𝑜 ≤ 𝑝∗ ≤ 𝑝ℎ𝑖。在每个量子期间，Colloid 尝试缩小 𝑝𝑙𝑜 和 𝑝ℎ𝑖 之间的差距，从而使系统更接近平衡点。如果默认层的访问延迟小于备用层的访问延迟，那么更新 𝑝𝑙𝑜 为 𝑝，否则更新 𝑝ℎ𝑖 为 𝑝。然后，Colloid 将系统向 𝑝𝑙𝑜 和 𝑝ℎ𝑖 的中点移动。为此，跨层的访问概率变化被计算为：

如图 4(a) 所示，对于任何给定的静态工作负载，如果存在平衡点，上述过程将会收敛到该平衡点。这是因为在每个量子期间，𝑝𝑙𝑜 和 𝑝ℎ𝑖 之间的差距会减小，同时不变式 𝑝𝑙𝑜 ≤ 𝑝 ≤ 𝑝ℎ𝑖 和 𝑝𝑙𝑜 ≤ 𝑝∗ ≤ 𝑝ℎ𝑖 会继续成立。因此，𝑝 最终会收敛到 𝑝∗。如果即使在 𝑝 = 1 时，默认层的访问延迟仍然低于备用层，那么 Colloid 会收敛到 𝑝 = 1 的最优操作点。

关键挑战是处理动态时间变化的工作负载。这种工作负载可能导致两个意外的变化：

• 工作负载访问模式的变化可能会导致 𝑝 值的突然变化，从而违反 𝑝𝑙𝑜 ≤ 𝑝 ≤ 𝑝ℎ𝑖 的不变式；

• 内存互连争用的变化可能会导致 𝑝∗ 值的突然变化，从而违反 𝑝𝑙𝑜 ≤ 𝑝∗ ≤ 𝑝ℎ𝑖 的不变式。

如图 4(b) 所示，𝑝 的变化会通过上述过程自动处理，因为在计算 Δ𝑝 值之前，水位标记(plo,phi)会先进行更新。

然而，𝑝∗ 的变化需要更加谨慎地处理。

例如，假设由于内存互连争用的变化，𝑝∗ 突然变得大于 𝑝ℎ𝑖，如图 4(c) 中 𝑡 = 3 所示。由于上述过程确保 𝑝 始终保持小于 𝑝ℎ𝑖，且此时 𝑝∗ 已经大于 𝑝ℎ𝑖，因此 𝑝 将无法收敛到新的 𝑝∗。

为了处理平衡点的动态变化，Colloid 会检查水位标记是否非常接近，并且系统尚未达到平衡点（即，层的访问延迟未平衡）；如果是这样，Colloid 会根据层的访问延迟重置水位标记。

具体来说，如果 𝑝𝑙𝑜 非常接近 𝑝ℎ𝑖 且默认层的访问延迟小于备用层的访问延迟，则 𝑝∗ 很可能已经超过了 𝑝ℎ𝑖；因此，Colloid 会将 𝑝ℎ𝑖 重置为 1。类似地，如果 𝑝𝑙𝑜 非常接近 𝑝ℎ𝑖 且默认层的访问延迟大于备用层的访问延迟，则 𝑝∗ 很可能已经小于 𝑝𝑙𝑜；因此，Colloid 会将 𝑝𝑙𝑜 重置为 0。

需要时重置水位标记可以使 Colloid 即使在平衡点因内存互连争用变化而发生偏移时，仍能收敛到平衡点。如图 4(c) 所示。为了量化水位标记之间的差距，我们使用一个阈值 𝜖（0 < 𝜖 < 1），并且为了确定系统是否接近平衡点，我们检查层的访问延迟是否在一个 𝛿 的因子范围内（0 < 𝛿 < 1）。在固定 𝛿 的情况下，增大 𝜖 会加快动态工作负载变化的检测，但会牺牲系统的稳定性。在固定 𝜖 的情况下，增大 𝛿 会提高稳定性，但会以较差的稳态吞吐量为代价。

Dynamic migration limit

随着 Colloid 趋近平衡点，它必须谨慎权衡访问概率变化 Δ𝑝 与页面迁移产生的额外内存流量对应用性能的影响。在给定的时间量子内，如果 Δ𝑝 很小且有很多页面，每个页面的访问概率都很小（例如，如果 Δ𝑝 = 0.01，且有 1000 个页面，每个页面的概率为 0.00001），Colloid 可能会不必要地迁移大量页面。这可能导致大量的迁移流量，从而引发围绕平衡点的振荡，并影响应用性能。为了解决这个问题，Colloid 引入了一个与 Δ𝑝 成正比的动态迁移限制。如果迁移流量大于预期的访问率变化 Δ𝑝 (𝑅𝐷 + 𝑅𝐴)，那么执行这样的迁移就不是理想的。因此，Colloid 将迁移限制设置为 Δ𝑝 (𝑅𝐷 + 𝑅𝐴) 和基于现有系统中迁移流量最大速率限制的静态限制的最小值，后者是一个可配置的参数。

Selecting pages to migrate

给定所需的访问概率变化 Δ𝑝，Colloid 使用底层系统中的访问追踪机制来找到一小组符合访问概率变化限制的页面 (§4)。也就是和其它现有的工作结合起来。如TPP、MEMTIS、HeMem等。

Evaluation

实验部分和与其它系统集成的部分后续再补充。