title: MALRU miss-penalty aware LRU-based cache replacement for hybrid memory systemsdate: 2018-09-11 22:04:10
tags: 缓存替换策略

混合存储系统中基于遗漏感知的LRU缓存替换策略

I. INTRODUCTION（介绍）

名词解释

缓存淘汰算法

根据数据的历史访问记录来进行淘汰数据

LRU：最近最少使用数据置换算法(Least Recently Used)，淘汰最长时间未被使用的数据。

LFU：最近最不常用数据置换算法(Least Frequently Used)，淘汰一定时期内被访问次数最少的数据。

该paper名词

MALRU：一种适用于混合内存系统的减值敏感LRU缓存替代策略

AMAT：平均内存访问时间。一种更通用的缓存性能度量。在混合存储系统中，Cache hit rate（缓存命中率）由于不对称问题的出现，该评判标准不再适用，转而提出AMAT判别标准。

LLC：最末级缓存机制。

贡献
  1. 我们研究了在非均匀记忆中LLC的不对称性，并观察到了缓存替代政策的低效率。因此，我们提倡AMAT度量，以评估混合内存系统的内存性能。
  2. MALRU优先驱逐低延迟的DRAM块，并保留高延迟的NVM块和一些低延迟的DRAM块，在保留区中具有良好的数据位置。MALRU定期调整保留区，以保护最常被访问的DRAM块，它能带来比NVM块更多的性能收益。
  3. 我们用SPEC CPU 2006基准测试MALRU，并将MALRU与传统的最近使用的（LRU）和混合内存系统中最先进的HAP策略进行比较。与混合内存感知缓存分区技术（HAP）相比，我们的评估显示，MALRU提高了应用程序的性能，提高了11.7%（平均5.7%）。并且实现了单线程应用程序的平均速度提高6.1%，而多程序工作负载则提高了4.8%。

II. MOTIVATION（动机）

为了更有效地管理混合内存系统，我们不仅要考虑数据的位置，还要考虑缓存遗漏的不对称性。

原则

  1. 比起将NVM块从LLC中移除，移除低延迟的DRAM块是更有利的。不幸的是，在混合内存系统中，ARD不能总是比LRU策略更好。如果带有时间位置的DRAM块经常被驱逐，那么就会导致缓存。ARD增加了内存访问开销，因为它会驱逐经常访问的DRAM块。一些具有良好的时间位置的块将在近距离的时间间隔内被重新引用。我们称其为近直接引用的块。这些块也应该保存在有LLC中，以避免缓存波动。我们有原则2来改进混合内存系统中的缓存性能。
  2. 迅速被重新引用的DRAM块对于缓存命中率是有价值的，并且不应该从LLC中被驱逐。

基于这两种原则和重新预测缓存区间，我们提出了一种有效的缓存替代策略，即在LLC中保留NVM块和近直接引用的DRAM块。

III. MISS PENALTY-AWARE LRU REPLACEMENT（遗漏感知的LRU缓存替代）

MALRU通过保留指针将LLC化为两个区，保留区(reserved section)和受害区(victim section)。

A.Detection of Cache Miss Penalty（检出缓存器）

用标记法来对缓存块进行区分，划分为低延迟区域和高延迟区域。

B. Re-reference Interval Distribution（Re-reference间隔分布）

C. Determine the Boundary of Reserved Section（确定保留区的边界）

由于缓存命中率在混合存储系统中并不适用，引入AMAT（平均内存访问时间）来度量缓存的效果。

CACHE_混合存储系统中基于遗漏感知的LRU缓存替换策略 - 图1、CACHE_混合存储系统中基于遗漏感知的LRU缓存替换策略 - 图2：分别表示对DRAM和NVM的访问频率。

CACHE_混合存储系统中基于遗漏感知的LRU缓存替换策略 - 图3：LLS延迟时间

CACHE_混合存储系统中基于遗漏感知的LRU缓存替换策略 - 图4、CACHE_混合存储系统中基于遗漏感知的LRU缓存替换策略 - 图5：分别表示DRAM和NVM的平均访问延迟时间。

CACHE_混合存储系统中基于遗漏感知的LRU缓存替换策略 - 图6、CACHE_混合存储系统中基于遗漏感知的LRU缓存替换策略 - 图7：分别表示LLC的DRAM、NVM的命中率。

CACHE_混合存储系统中基于遗漏感知的LRU缓存替换策略 - 图8)%2BP%7Bd%7D%20%E2%88%97%20(HitTime%20%2B%20T%7Bd%7D%20%E2%88%97%20(1%20%E2%88%92%20HitRate%7Bd%7D))%20%0A#card=math&code=AMAT%20%3D%20P%7Bn%7D%20%E2%88%97%20%28HitTime%20%2B%20T%7Bn%7D%20%E2%88%97%20%281%20%E2%88%92%20HitRate%7Bn%7D%29%29%2BP%7Bd%7D%20%E2%88%97%20%28HitTime%20%2B%20T%7Bd%7D%20%E2%88%97%20%281%20%E2%88%92%20HitRate_%7Bd%7D%29%29%20%0A)

由于每个缓存块要么是DRAM，要么是NVM，所以P{d}+P{n} = 1。

V. RELATED WORK

在缓存替换策略上有大量的工作。这些研究可分为三类：重新引用区间预测、死块预测和基于分区的替换策略。

  1. 重新引用间隔预测（RRIP）进一步提高了混合内存访问模式的倾斜性能。
  2. “死块”预测技术通过优先替换死块来提高缓存效率，因为这些块在被驱逐之前“不太可能被重新引用”。
  3. 基于分区的替换策略将LLC划分为几个分区。这些分区对不同的内存访问行为进行了划分，并分别替换。这些策略提出了复杂的方案来动态地调整每个分区的大小。