title: Cost aware cache replacement policy in shared last-level cache for hybrid memory based fog computingdate: 2018-10-07 22:04:10
tags: 缓存替换策略

基于雾计算的混合内存下的共享LLC缓存成本感知缓存替换策略

引言

由于高功耗，动态随机存取存储器（DRAM）通常使用随机存取存储器，不能被包含在雾计算系统中。

非易失性记忆（NVM），如相变内存（PCM）和自旋转移扭矩RAM（STT-RAM），其低功耗，取代了DRAM。混合主存储器，包括DRAM和NVM，在可伸缩性和功耗方面都显示出了很好的优势。

NVM的缺点：例如长读/写延迟，会导致潜在的问题，导致混合主存储器中的非对称缓存丢失。

当前的最后一级缓存（LLC）策略是基于统一未命中的成本，并导致LLC的表现不佳，并增加了使用NVM的成本。

为了最小化混合主存储器中的缓存遗漏成本，我们提出了一个成本敏感的缓存替换策略（CACRP），它减少了NVM的缓存丢失的数量，并提高了混合内存系统的缓存性能。

Ⅰ.Introduction 前言

  1. 雾计算建议扩展云计算的覆盖范围，以在移动终端提供服务。其愿景是通过减少延迟和提高服务质量（QoS）来提高服务质量，因为这种雾计算需要很大的主存容量来处理计算资源的增加需求。动态随机存取存储器（DRAM），通常使用的随机存取存储器受到其高功耗（Li等人2012）和有限的可伸缩性（薛等人2011）的限制，使其不适合在移动终端的主存系统中使用。为了解决这些限制，近年来已经看到了非易失性记忆（NVM）的发展，如相变内存（PCM）（Nirschl等人2007），自旋转移转矩RAM（STT-RAM）（Dieny 2011）和电阻RAM（ReRAM）（Kawahara等人2012），具有更好的可伸缩性和更低的功耗。然而，这些新记忆的缺点是，在设计雾计算设备时，需要考虑更长的读/写延迟。一个很有前途的主要内存架构可以解决功耗和可伸缩性问题，同时保持读写的延迟，这是一种混合的DRAM/NVM内存的开发。因此，混合DRAM/NVM内存将应用于雾计算，因为它的能耗低，可伸缩性高。但是在当前的内存管理方法下，在NVM中，移动设备的性能将会降低。因此，不能保证QoS是无法接受的，这对于雾计算来说是不可接受的。在雾计算中提高移动设备的混合内存性能是当务之急，以提供高质量的服务。
  3. 图1中演示了包含DRAM和NVM介质的最流行的混合内存架构之一。这两种记忆媒介使用统一的物理地址空间。因此，为了利用这两种媒介的优点，**经常读取**的数据被分配给**NVM内存**，而**频繁写入**的数据被分配给**DRAM内存**。然而，这种混合内存架构的最好使用要求共享的最后一级缓存（LLC）策略解决NVM内存的长读/写延迟（Jia et al.2016a）。不幸的是，大多数现行的LLC策略（Jaleel等人，2010年;2014年Samira Khan和Alameldeen;Seshadri等人，2012年;和Xie 和Loh 2009）在不区分不同的记忆媒介的情况下，不能降低平均内存访问成本。LLC策略需要将DRAM访问与NVM访问区分开来，以便最小化NVM访问以提高LLC的性能。
  5. 我们的论文的贡献如下：
1. 我们解释混合内存中使用的当前水平缓存替换策略的低性能。NVM数据的更高的替换成本降低了缓存性能，而没有区分成本。
2. 我们提出一个成本敏感的缓存替换政策（CACRP）。在CACRP中，有两个单独的替换策略，一个用于DRAM数据，另一个用于NVM数据。NVM数据替换的策略只是一个LRU策略，而DRAM数据替换的策略是基于成本的动态策略。这两种策略的组合提高了性能。
3. 我们使用不同的工作负载来评估所提议的方法。实验结果表明，CACRP对LLC的效果更好，与LRU相比，它能提高LLC的功效，达到43.6%（平均15.5%）。

Ⅱ.Motivations 动机

图2展示了使用LRU替代策略在混合内存不同配置下的标准化完成时间。x轴代表不同的配置（1:15表示DRAM和NVM之间的内存容量比为1到15）。y轴表示完成时间规范化为仅用于DRAM的内存。随着NVM的比例降低，缓存性能会显著增加，但是整个缓存容量和主要内存容量都是固定的。图3展示了NVM数据增加的NVM数据的比例，导致其缓存的比例增加。在NVM中，一个未被缓存的缓存的成本较高，因为延迟的延迟会导致进程的完成时间的增加和性能的降低。公式（1）表示在一个仅为DRAM的主存中，平均内存访问时间:

CACHE_基于雾计算的混合内存下的共享末级缓存成本感知缓存替换策略 - 图1

$$AT_{memory}$$表示平均内存访问时间，H是缓存命中率，$$T_{cache}$$是缓存访问时间，$$M$$是缓存遗漏比率，而$$T_{memory}$$是内存访问时间。$$AT_{memory}$$越小，缓存性能就越好。在公式（1）中，$$T_{cache}$$和$$T_{memory}$$是恒定的，而$$H$$是$$1 - M$$，因此，在一个只有DRAM的主存中，增加缓存命中率将导致$$AT_{memory}$$的减少，以及缓存性能的提高。因此，传统LLC缓存替换策略的唯一目的是提高缓存命中率。但是在混合内存系统中，平均内存访问时间可以用公式（2）表示：

CACHE_基于雾计算的混合内存下的共享末级缓存成本感知缓存替换策略 - 图2

$$AT_hmemory$$代表平均混合内存访问时间,$$H$$代表缓存命中率,$$T_{cache}$$代表缓存访问时间,医学博士代表了缓存错过DRAM的比例数据,$$T_{memory_D}$$代表DRAM内存访问时间,MN表示缓存错过NVM的比例数据,和$$T_{memory_N}$$代表NVM内存访问时间。

$$AT_{hmemory}$$越小，混合内存系统的缓存性能就越好。在公式（2）中，$$T_{cache}$$、$$T_{memory_D}$$和$$T_{memory_N}$$都是常量，$$H=1-MD-MN$$。此外，$$T_{memory_N}  > T_{memory_D}$$。因此，为了提高混合内存系统的缓存性能，我们不仅需要增加缓存命中率，而且还需要减少NVM数据的缓存遗漏率。

在缓存替换策略方面，仅DRAM内存和一个混合的主存储器之间的主要区别在于它们处理缓存遗漏比的方法。在本文中，我们提出了一个成本感知缓存替换策略（CACRP），它旨在通过减少NVM数据的缓存遗漏率来提高缓存性能。

Ⅲ.Cost aware cache replacement policy (CACRP) 成本感知的缓存替换策略

3.1 Overview of CACRP 概述
图4显示了支持CACRP的框架的概述。我们的CACRP主要由三个步骤组成：
  1. 区分DRAM数据和NVM数据之间的缓存栈。
  2. 计算DRAM和NVM的成本损失，影响成本的过程行为。

  3. 根据DRAM和NVM的不同成本，确定DRAM数据的插入位置。我们的CACRP的目的是为了提高缓存的性能，减少NVM数据的误差率。因此，我们需要尽可能长时间地将NVM数据的缓存栈保存在缓存中。

    在这篇文章中，我们的CACRP将NVM数据插入到最近使用的（MRU）的位置，在一个命中或一个新负载之后，但是DRAM数据根据一个命中或一个新的负载在一个特定的位置插入。通过这种方式，我们的方法能够在缓存中延长NVM数据，以减少遗漏的比率。

3.2. Cache line distinguishing mechanism 缓存栈区分机制
为了实现我们的CACRP，优先级的工作是区分DRAM数据和NVM数据的缓存栈。为了在不同的数据缓存栈路上实现不同的缓存替换策略，这是必需的。NVM数据缓存栈,我们将数据插入到最近使用后(系统)的位置或一个新的负载,而在DRAM数据高速缓存栈路的情况下,我们插入在基于成本命中后的特定位置或一个新的负载。

在本文中，我们采用了一种简单的方法来区分DRAM数据和NVM数据的缓存栈。算法1显示了区别机制。在这个算法中，我们做了两个假设：

  1. DRAM和NVM的主要内存是连续的;

  2. DRAM的主要内存位于地址空间的小区域，而NVM的主要内存位于地址空间的大区域。

这两个假设在当前的混合内存系统中是合理的。集合中的每一个缓存栈都包含一个惟一的标记，以区别于其他的。我们使用这个独特的标签来确定缓存栈是否来自于DRAM数据或NVM数据。

在算法中，$$T$$表示候选缓存栈的标记（正在进行判断），$$CL$$表示缓存栈的大小（主要是64字节或128字节）。$$S$$是最后一级缓存中缓存集的总数。$$N$$是混合主存储器中的DRAM大小。$$CA$$表示混合主存储器中候选缓存栈的物理地址。如果$$CA % N == 0$$，这意味着候选缓存栈的物理地址小于$$N$$，因此它属于DRAM空间;否则，它属于NVM空间。例如，如果最后一级缓存是8 MB，而$$CL=64、S=8 K、N=512 MB$$，那么$$T=03C0 H$$.因此，$$CA=03C0 H 64 8 K=1e000000 H$$，因此，$$CA%512 MB=0$$。因此，候选缓存栈路来自DRAM内存，因此，数据来自DRAM。

基于标签和我们的区分算法，很容易确定缓存栈是来自DRAM数据还是NVM数据。

3.3. Replacement cost calculation 重置成本计算
CACRP根据DRAM数据和NVM数据之间的缓存成本差异来确定DRAM数据的替换策略。公式（3）显示了DRAM数据的丢失成本：

CACHE_基于雾计算的混合内存下的共享末级缓存成本感知缓存替换策略 - 图3

$$C_{DRAM}$$表示DRAM数据的丢失成本，$$R_{rDRAM}$$代表DRAM的读取率，$$T_{rDRAM}$$代表DRAM读取的存取周期，$$R_{wDRAM}$$代表DRAM的写比率，$$T_{wDRAM}$$代表DRAM写入的存取周期。在这个公式中，$$R_{rDRAM}+R_{wDRAM}=1$$和$$T_{rDRAM}=T_{wDRAM}$$。公式（4）显示NVM数据的成本：

CACHE_基于雾计算的混合内存下的共享末级缓存成本感知缓存替换策略 - 图4

$$C_{NVM}$$代表NVM数据的丢失成本，$$R_{rNVM}$$代表NVM的读取率，$$T_{rNVM}$$代表NVM读取的存取周期，$$R_{wNVM}$$表示NVM书写的写比，$$T_{wNVM}$$表示NVM书写的访问周期。在这个公式中，$$R_{rNVM}+R_{wNVM=1}$$和$$T_{wNVM}$$。因为记忆媒介的不同，$$T_{rNVM}$$，$$T_{rDRAM}$$，$$T_{wNVM}$$，$$T_{wDRAM}$$。因此，$$C_{DRAM}$$。但是为了确定替换位置，我们必须计算K的值，它满足$$C_{NVM}=K * C_{DRAM}$$的值。值K是确定插入位置所需的关键因素。公式（5）演示了计算K的过程：

CACHE_基于雾计算的混合内存下的共享末级缓存成本感知缓存替换策略 - 图5%2F(R%7BrDRAM%7D%20*%20T%7BrDRAM%7D%20%2B%20R%7BwDRAM%7D%20*%20T%7BwDRAM%7D)%5C%5C%3D%20(R%7BrNVM%7D%20*%20T%7BrNVM%7D%20%2B%20R%7BwNVM%7D%20*%20T%7BwNVM%7D)%2FT%7BrDRAM%7D%0A#card=math&code=K%20%3D%20C%7BNVM%7D%2FC%7BDRAM%7D%5C%5C%3D%20%28R%7BrNVM%7D%20%2A%20T%7BrNVM%7D%20%2B%20R%7BwNVM%7D%20%2A%20T%7BwNVM%7D%29%2F%28R%7BrDRAM%7D%20%2A%20T%7BrDRAM%7D%20%2B%20R%7BwDRAM%7D%20%2A%20T%7BwDRAM%7D%29%5C%5C%3D%20%28R%7BrNVM%7D%20%2A%20T%7BrNVM%7D%20%2B%20R%7BwNVM%7D%20%2A%20T%7BwNVM%7D%29%2FT%7BrDRAM%7D%0A)

在公式（5）中，$$T_{rNVM}$$、$$T_{wNVM}$$和$$T_{rDRAM}$$都是常量。但是$$R_{rNVM}$$和$$R_{wNVM}$$是变量。$$R_{rNVM}$$和$$R_{wNVM}$$的值决定了K的插入位置。$$R_{rNVM}$$和$$R_{wNVM}$$的值与正在运行的进程的行为有关，特别是DRAM的读和写行为。如果一个进程的行为包含50%的读和50%的内存，那么K的值是由$$K=（T_{rNVM}+T_{wNVM}）/（2 * T_{rDRAM}）$$给出的。

3.4. Adaptive position replacement policy 适应位置替换政策
每一个进程都有一个用于区分的K值，用于其不同的内存访问行为。为了提高缓存性能，我们必须将DRAM数据的缓存栈插入不同的位置。图5演示了这种自适应位置替换策略。在计算了K的值之后，我们可以确定在缓存栈路命中或新负载之后插入DRAM数据缓存栈的位置T。算法2显示了这种自适应位置替换策略。K是一个单一进程的公式（5）的结果。N表示最后一级缓存是N通道关联。P是插入位置，在这里插入DRAM缓存栈。如果K的值是1，这意味着DRAM和NVM的内存成本是相同的。因此，插入位置应该是MRU，也就是位置0。此外，通过我们的实验，我们确定当K的值接近4时，最佳的插入位置是13。插入位置随着K值的增加而增加。我们建立一个线性模型将插入位置与值K联系起来，因此，我们使用公式（6）来确定插入位置：

CACHE_基于雾计算的混合内存下的共享末级缓存成本感知缓存替换策略 - 图6

在K大于1的情况下，插入位置将在0<P<15的范围内。通过这种方式，很容易确定插入位置。

通过算法2，我们可以确定一个命中或一个新负载后的DRAM缓存栈路的插入位置。但是对于NVM缓存线路，我们总是将它们插入到MRU位置。在这个替换策略中，NVM缓存线路可以在缓存中保存更长的时间，以降低成本。