综述翻译：Machine Learning-Based Cache Replacement Policies: A Survey 2021

本文主要是介绍综述翻译：Machine Learning-Based Cache Replacement Policies: A Survey 2021，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

摘要：

虽然在提高命中率方便有了广泛进展，设计一个模拟Belady‘s 算法的缓存替换策略依旧很有挑战。现存的标准静态替换策略并不适合动态的内存访问模式，而计算机程序的多样性加剧了这个问题。有几个因素影响缓存策略的设计，如硬件升级，内存开销，内存访问模式，模型延时等。

用机器学习的算法解决缓存替换的问题取得了令人惊讶的结果，并朝着具有成本效应的解决方案发展。在本文中，我们回顾了一些基于机器学习的缓存替换策略，它们优于静态启发式策略。

keywords：Belady’s algorithm, Cache Replacement, Machine Learning

1. Introduction

随着高速处理器和存储层次结构的高速发展，缓存被证明是一种减少内存延时方面非常有前途的机制。由于引入缓存所产生的性能收益是缓存被包含在大部分系统种的重要原因质疑。缓存是容量小（大约几~几十MB）速度快的存储单元，它存储着被频繁使用的数据。可以通过增加缓存容量来提高性能，但价格太贵了。通常的方法是通过数据和指令预取来阻止未来的缓存缺失和有效的缓存替换策略来明智的丢弃缓存行为新缓存行提高空间，以此措施来提高缓存命中率。

在这篇文章种，我们聚焦于缓存替换策略和它们的性能。集中静态的缓存替换策略已经被开发，但它们受限于几种固定的访问模式，并在复杂的环境下表现很差。这指引我们在具有挑战的领域讨论现代技术。

机器学习和深度学习在自然语言处理，计算机视觉，语音识别和时间序列分析领域取得了显著的进步。这些现代和强大的工具在计算机架构中的使用并不新鲜，并且已经被广泛研究以改进某些领域，如分支预测、缓存替换、数据预取[3]。

然而，当涉及将其应用于硬件预测器时，会遇到一些挑战。训练一个神经网络会消耗大量的数据和资源，因此需要离线训练。但对于广泛的计算机程序和访问模式所显示的动态变化，离线模型被证明是不那么有效的。在受内存限制的硬件芯片上部署离线模型是另一个关键问题。对实时性要求高的系统，模型的预测时间可能会成为一种障碍。除此之外，一些方法还需要修改硬件，并可能导致额外的开销。尽管如此，基于机器学习的缓存替换技术显著优于静态启发式，可以被认为是一种可行的解决方案，可以在多线程环境[4]的情况下提高整体系统性能和性能的扩展。在本文中，我们探讨了一些最近基于机器学习的缓存替换策略。

Ⅱ背景：

缓存替换策略是一种启发式策略，它可以驱逐缓存中存在的数据项来放置取回来的新数据集。

其主要目标是替换哪些在最近的未来最不可能被使用的数据项。最佳算法总是能驱逐将来不再需要的数据，称为Belay算法。这只能是理论最佳，因为准确的预测未来是不可能的。因此，任何替换算法都应该努力逼近Belady’s算法。在这里，我们回顾了一些常见的常规缓存替换策略：

首先是先出（FIFO）：所有策略中最简单的一种，它按照它被缓存的顺序驱逐块。[6]。

随机替换（RR）：该算法从缓存中随机获取一个数据项，并将其替换为所需的数据项。FIFO和RR策略都没有考虑到缓存内容的历史记录，因此成本比竞争算法[7]要低。

最近使用最少的算法（LRU）：使用最广泛的算法之一，有越来越多的变体。顾名思义，这种缓存算法会了那些最近通过跟踪内容历史而使用最少的条目。这是使用老化位实现的，由于在每个缓存引用[8]之后，每个缓存行的老化位的状态都会发生变化，因此可能会很昂贵。

伪LRU（PLRU）：LRU的一种变体，其中的核心原理保持不变，但缓存块的年龄是近似的，而不是作为一个精确的值来保持。它可以通过两种方式来实现，即TreePLRU和Bit-PLRU。Tree-PLRU构造了一个二进制搜索树，其中每个节点都包含一个标志，它有助于遍历树以找到PLRU元素。Bit-PLRU为每个缓存行维护一个名为mru位的位。如果引用该行，则位设置为1，只要最后一个零位设置为1，其余的位设置为0。在缓存丢失期间，算法替换最左边位为0的行。PLRU被认为在低功耗和低开销方面优于LRU。然而，它有最差的失误率。

分段LRU（SLRU）：这种技术依赖于缓存设计，分为保护段和试用段[9]。获取的数据首先缓存在试用段，下一次命中后移动到受保护的段。由于受保护段的大小固定，当受保护段满时，受保护段LRU端的线移到试用段的MRU端。SLRU取代了LRU结束的试用期部分。

最不常用（LFU）：该缓存算法基于访问频率和具有最小频率的条目的条目。驱逐具有相同频率的条目是任意进行的。

时钟： LRU使用一个单个全局锁来序列化缓存命中。时钟方法旨在缓解锁争用并模拟LRU，从而增加了并发性和吞吐量[10]。

自适应替换缓存（ARC）：该缓存算法是LRU和LFU的混合算法，作为跟踪时间局部性的自适应过滤器，具有近因性和频率的优势。它的实现类似于LRU，但其性能大大优于LRU，并且在[11]的本质上具有抗扫描性。

自适应替换时钟（CAR）：通过采用ARC和时钟的特点，该缓存技术实现了低开销[12]的高性能。

虽然标准替换策略及其变体的列表很广泛，但上面描述的算法为理解和评估基于机器学习的缓存替换技术提供了一个坚实的概述。

Ⅲ 基于ML的高速缓存替换策略

常用的增强缓存替换的机器学习技术是强化学习（RL）[13]和循环神经网络（RNNs），特别是长短期记忆（LSTMs）[14]。RL可以被视为一种典型的缓存替换解决方案，其中评估并学习服务于过去缓存访问的一系列操作，以生成新策略。在任何中间状态下，没有任何行动被认为是最好的；如果一个行动导致了一个好的政策，那么它就被认为是好的。lstm是一种能够学习的神经网络，它通过学习序列数据来预测下一个时间步的输出。

在缓存替换的上下文中，缓存访问的历史记录形成了顺序数据。对基于ml的缓存替换策略进行分类的一种方法是基于pc的（程序计数器）、非基于pc的和使用传统静态启发式作为专家训练的模型。下面将讨论其中的一些技术：

A. LeCAR

LeCAR是一种基于ML的缓存替换算法，设计用于较小的缓存大小（相对于工作负载），它利用了众所周知的静态启发式算法，LRU和LFU [15]所提供的好处。基于LRU和LFU权值的概率分布的策略提供每个缓存丢失。LeCAR框架被建模为一个具有遗憾最小化的强化学习问题。遗憾最小化的基本原则是“有时后悔是一种改进的好方法”。遗憾是指本应采取的行动方针。

LeCAR维护一个FIFO队列，该队列保存从高速缓存中最近的删除（历史记录）。队列中的每个条目都被导致其被驱逐的策略所标记，即LRU或LFU。如果在队列/历史中找到引用，与策略相关的遗憾将增加，并更新其他策略的权重，表明可以做出更好的决策。这是一个在线模型，模型在每次失误后学习，以减少遗憾。当对ARC进行评估时，LeCAR消耗的空间是工作集的3倍，但缓存大小是工作集（1/1000）的18倍。ref: GitHub - sylab/LeCaR: The design and algorithms used in LeCaR are described in this USENIX HotStorage'18 paper and talk slides: https://www.usenix.org/conference/hotstorage18/presentation/vietri

B. CACHEUS

CACHEUS是LeCAR的自适应版本，它采用了基于梯度的随机爬山方法来计算学习率。

虽然LeCAR被证明只对某些类型的工作负载（LRU和LFU友好）是有效的，但CACHEUS被设计用来适应其他工作集、扫描和干扰[16]。扫描是指一组只被访问一次的高速缓存条目。搅动是指一组以等概率重复访问的缓存条目。CACHEUS首先使用了最先进的缓存算法LFU、LIRS和ARC作为专家，类似于LeCAR如何选择两个策略，LRU和LFU，来做出驱逐决定。然而，通过设计一种新型自适应抗扫描的LRU（SR-LRU）和抗扰动的LFU（CR-LFU），在广泛的工作负载中提高了性能。

在测试网络邮件工作负载时，ARC、LIRS、LeCAR的缓存命中率分别为30.08%、40.71%和42.08%，而以SR-LRU和CR-LFU作为专家的缓存命中率为43.95%，被证明是最一致的算法[16]。

C. Hawkeye

霍凯将缓存替换定义为一个二进制分类问题，其中缓存行被归类为对缓存友好或厌恶缓存的[17]。霍凯由3个主要组成部分组成，即OPTgen，霍凯预测器和一个采样器。OPTgen可以看作是一个模拟器，它可以有效地模拟了Belady的算法来生成输入。输入基本上表示内存访问的历史。如果OPTgen将某个特定的行标识为缓存命中，那么任何访问这些行的PC都被认为是积极的例子，否则则是消极的例子。这些例子被用于训练基于Belady的最优策略的鹰眼预测器/二元分类器。如果分类器计算缓存友好，这些行被标记为高优先级，而厌恶缓存的行被标记为驱逐/替换候选行。这种方法最困难的方面是构建OPTgen，它使用一种称为活动间隔的新方法来解决。OPTgen提出的另一个挑战是计算最优决策的长期历史需求，使用集合决斗采样器通过采样缓存线的采样器来减少存储需求。对于SPEC 2006 CPU基准测试，鹰眼对2MB LLC比LRU降低了8.4%，对4个核心系统wi降低了15%

D. Glider 滑翔机

滑翔机缓存替换策略建立在鹰眼的基础上，显著提高了预测精度。滑翔机被建模为一个序列标签问题，其中一个序列中的每个内存访问都被分配一个二进制标签[18]。输入序列是由它们的程序计数器（PC）表示的一系列负载。该学习模型的目的是预测一个特定的PC是访问对缓存友好还是厌恶缓存的缓存行。

采用离线缓存模型、离线分析模型和在线模型三步方法。离线模型是基于具有注意机制的LSTM来预测输入序列中重要的程序计数器。然后分析权重，并对输入特征进行紧凑的编码，因为缓存决策并不依赖于输入序列的长期历史，而只依赖于少数内存访问。这些见解被用于训练基于SVM的在线模型来预测重要的pc，其准确性与离线LSTM模型相当。在编码的输入特征上建立SVM模型的原因是，LSTM又大又慢，不能在硬件预测器上进行训练或部署。对于SPEC 2006年和2017年的程序，滑翔机在单核配置中比LRU减少了8.9%，而鹰眼只减少了6.5%。在多核场景中，滑翔机比LRU降低了14.7%，而鹰眼比[18]降低了13.6%。

E. Reinforcement Learning Replacement (RLR)

虽然鹰眼和滑翔机是两个最有效的基于pc的预测器，但有成本效益低的开销和硬件升级的替换策略是至关重要的。在RLR中，最初，通过训练强化学习（RL）代理和爬山分析[19]来推导出一组目标特征。根据神经网络权值选择预用距离、线最后访问类型、插入后的行命中和线近因性等特征。特征选择的过程是完全自动化的，并允许RL代理能够适应中的访问模式的动态变化。然后，通过为缓存行分配优先级级别，使用这些有限的特性设计了一个替换策略。PC被有意排除在特征集之外，因为它增加了硬件复杂性以及向PC数据传输到LLC所产生的通信开销。RLR优于现有的基于非pc的预测器DRRIP。通过可忽略的开销，RLR比LRU [19]的单核和四核系统性能分别提高了3.25%和4.86%。

F PARROT

PARROT是第一个使用近似于Belady的[20]的模仿学习来构建端到端缓存替换策略的方法。该算法首先将输入，即缓存访问（嵌入式内存地址和嵌入式PC）转换为状态。为了减少train和test期间状态分布差异造成的复合误差，转换采用了DAgger方法。在LSTM模型中，这些状态被采样和初始化为隐藏状态，随后使用BPTT算法进行训练。将初始化的替换策略应用于其余的状态，就会得到损失函数。损失函数由预测重用距离时发生的等级损失和损失之和给出。权重参数根据这个损失函数进行更新，允许学习替换策略。对于鹦鹉来说，之前被认为可以准确接近贝拉迪的访问次数被发现是80次，之后的改进达到饱和。与传统的网络搜索基准策略相比，鹦鹉的LRU策略将缓存命中率提高了61%。不幸的是，由于该模型的大尺寸和高延迟，其实际应用受到了限制。

IV. CONCLUSION

缓存替换策略不断发展，目的是接近由Belady算法定义的理论结果。其趋势是应用ML/DL来解决缓存替换问题。在设计任何缓存替换策略时，目标必须是构建具有成本效益的解决方案，很少需要硬件修改，减少芯片外带宽需求和最小化开销。算法还必须努力减少模型大小和低延迟，以便不掩盖策略所提供的好处，从而最终实现实际部署。

本文首先讨论了一些传统的缓存替换算法，以方便地简单地解释基于机器学习的技术。对许多基于ML的缓存替换算法的调查显示，与传统方法相比有了显著的增强，但每个策略都经过了优化，只满足特定类型的工作负载。设计一个适用于所有工作负载的良好的通用策略仍然是一项具有挑战性的任务。此外，这些技术大多是仅为单级缓存开发的，这使得层次级缓存替换策略的开发成为ML中的热门研究主题。

这篇关于综述翻译：Machine Learning-Based Cache Replacement Policies: A Survey 2021的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！