title: Dynamic Adaptive Replacement Policy in Shared Last-Level Cache of DRAM/PCM Hybrid Memory for Big Data Storagedate: 2018-10-11 22:04:10
tags: 缓存替换策略

大数据存储DRAM／PCM混合存储器共享级缓存中的动态自适应替换策略

引言

本文使用非易失性存储器（NVM）中的具体一种”相变存储器（PCM）“来实现混合存储系统的缓存替换策略。

PCM使用LRU，DRAM使用根据进程行为的替换策略。

Ⅰ.简介

DRAM缺点：如高功率消耗和低密度。

PCM缺点：高访问延迟和有限写寿命。

适用PCM替代DRAM不现实，继而出现混合存储方式，PCM+DRAM。

最后一级缓存遗漏比减少可以等于主存访问数减少，但是它不能表示混合主内存开销的减少。

通过PCM长延时访问，可以增加混合主存储器存取开销。

提出动态自适应替代策略（DARP）

  1. 最后一级缓存中的数据被划分为PCM数据和DRAM数据，因为不同的数据使用不同的替换策略。
  2. 建立了间接模型。此外，主存由两种媒介组成，不同的媒介具有不同的间接访问权。在确定每个数据最方便的替换策略时，开销模型是至关重要的。
  3. 采用基于阶段的进程剖面，使用进程内存访问行为。
  4. 最后，使用了开销模型和进程行为的组合，用于动态确定每个数据的替换策略。

Ⅱ.LRU在DRAM/PCM混合主存储器中的挑战

对不同内存介质访问的不对称性

PCM的写延迟比DRAM高6-10倍。

内存访问数依赖于混合内存配置

随着PCM/DRAM的增大，对PCM的访问量增加。

CACHE_大数据存储DRAM／PCM混合存储器共享级缓存中的动态自适应替换策略 - 图1

缓存容量比分析

PCM的内存访问数比PCM的容量比率增长更快。

我们的目标是增加末级缓存PCM数据容量，以减少PCM内存访问数，并提高性能。

对混合内存配置的性能依赖

PCM访问数增加 —> 性能下降

过程内存访问行为的动态变化

gcc基准的实时IPC值显示在图4中。IPC值每500万次被采样。实时IPC值的动态变化可以反映过程内存访问行为的动态变化。

CACHE_大数据存储DRAM／PCM混合存储器共享级缓存中的动态自适应替换策略 - 图2

以此为基础，提出了基于动态过程行为的动态自适应替代策略（DARP）。

Ⅲ.动态适应替换政策(DARP)

DARP概述(简介中有提出)

DARP由四个部分组成:

  1. 数据分区，由于DRAM/PCM混合主存有两种内存介质，所有数据被分为PCM数据和DRAM数据;
  2. 为了证明不同内存介质的访问成本，提出了一种开销模型。
  3. 基于动态进程内存访问行为的进程分析。
  4. 结合开销模型和每个进程阶段的内存访问行为，以确定所有阶段的替换策略。每个阶段都有相应的替换策略;因此，我们的替代策略是动态适应的。

数据分割机制

提出一种数据分割算法，该算法需要两个先决条件，并且这也是混合存储系统的条件：

  1. 所有的PCM和DRAM存储器都是连续的。
  2. DRAM位于低地址，PCM位于高地址。

T: the candidate cache line tag（候选缓存栈标记）

MD: the DRAM memory capacity（DRAM存储容量）

S: the whole cache sets（全部缓存集）

CL: the cache line size（缓存栈大小）

CACHE_大数据存储DRAM／PCM混合存储器共享级缓存中的动态自适应替换策略 - 图3%0A#card=math&code=DV%20%3D%20MD%2F%28S%20%E2%88%97%20CL%29%0A)

通过CACHE_大数据存储DRAM／PCM混合存储器共享级缓存中的动态自适应替换策略 - 图4)%0A%3D(TSCL)%2FM%7BD%7D#card=math&code=temp%3D%20T%2FDV%3DT%2F%28M%7BD%7D%2F%28S%2ACL%29%29%0A%3D%28T%2AS%2ACL%29%2FM_%7BD%7D) 判断数据是DRAM缓存栈还是PCM缓存栈。

开销模型

内存访问成本的不对称性是一大难题。

DRAM和PCM的读写命中/遗漏比率在每个过程中都不同，以往的再最终衡量的方式是无价值的，现提出以过程为阶段，在每个阶段开始之前计算一次之前的开销，以用来协助替换策略。

开销模型：C = H{pre} ∗ C{c} + M{PRpre} ∗ C{PR} + M{PWpre} ∗ C{PW}+M{DRpre} ∗ C{DR} + M{DW pre} ∗ C{DW}

CACHE_大数据存储DRAM／PCM混合存储器共享级缓存中的动态自适应替换策略 - 图5%E5%8F%AF%E4%BB%A5%E6%9D%A5%E6%A3%80%E6%B5%8B%E6%9C%AB%E7%BA%A7%E7%BC%93%E5%AD%98%E5%91%BD%E4%B8%AD%E7%8E%87%EF%BC%8C%E5%B9%B6%E4%B8%94%E5%85%B6%E5%9C%A8%E5%BD%93%E5%89%8D%E6%AF%8F%E4%B8%AACPU%E4%B8%AD%E9%83%BD%E5%AD%98%E5%9C%A8%EF%BC%8C%E5%BC%80%E9%94%80%E5%8F%AF%E4%B8%8D%E8%AE%B0%E3%80%82%0A%0A%E7%84%B6%E8%80%8C%EF%BC%8CPMU%E5%8F%AA%E8%83%BD%E8%AE%B0%E5%BD%95%E5%9C%A8%E7%BB%9F%E4%B8%80%E6%80%BB%E4%B8%BB%E5%AD%98%E7%9A%84%E9%81%97%E6%BC%8F%E7%8E%87%EF%BC%8C%E9%9C%80%E8%A6%81%E9%80%9A%E8%BF%87%E6%95%B0%E6%8D%AE%E5%88%86%E5%89%B2%E7%AE%97%E6%B3%95%E5%8E%BB%E5%88%A4%E6%96%AD%E6%98%AF%E5%B1%9E%E4%BA%8EDRAM%E8%BF%98%E6%98%AFPAM%E3%80%82%0A%0A%0A%0A%23%23%23%23%23%20%E5%8A%A8%E6%80%81%E8%87%AA%E9%80%82%E5%BA%94%E6%9B%BF%E6%8D%A2%E7%AD%96%E7%95%A5%E7%AE%97%E6%B3%95%0A%0A%E7%BC%93%E5%AD%98%E6%9B%BF%E6%8D%A2%E7%AD%96%E7%95%A5%E8%A2%AB%E5%88%86%E4%B8%BA%E4%B8%A4%E9%83%A8%E5%88%86%EF%BC%9A%E6%8F%92%E5%85%A5%E7%AD%96%E7%95%A5%20%2B%20%E6%8F%90%E5%8D%87%E7%AD%96%E7%95%A5%0A%0A%E6%8F%92%E5%85%A5%E7%AD%96%E7%95%A5%E5%86%B3%E5%AE%9A%E5%BD%93%E7%BC%93%E5%AD%98%E9%81%97%E6%BC%8F%E6%97%B6%E6%96%B0%E6%95%B0%E6%8D%AE%E8%A2%AB%E6%8F%92%E5%85%A5%E7%BC%93%E5%AD%98%E9%9B%86%E7%9A%84%E4%BD%8D%E7%BD%AE%E3%80%82%E6%8F%90%E5%8D%87%E7%AD%96%E7%95%A5%E5%86%B3%E5%AE%9A%E5%BD%93%E7%BC%93%E5%AD%98%E5%91%BD%E4%B8%AD%E6%97%B6%E8%A2%AB%E6%8F%90%E5%8D%87%E7%9A%84%E4%BD%8D%E7%BD%AE%E3%80%82%0A%0ADARP%E6%8F%90%E5%87%BA%E6%89%80%E6%9C%89%E7%9A%84PCM%E6%95%B0%E6%8D%AE%E5%BA%94%E5%BD%93%E8%A2%AB%E6%8F%92%E5%85%A5%E5%9C%A8MRU%E4%B8%AD%E4%BB%A5%E5%87%8F%E5%B0%91%E4%B8%A2%E5%A4%B1%E7%8E%87%EF%BC%8C%E8%80%8CDRAM%E6%95%B0%E6%8D%AE%E5%BA%94%E5%BD%93%E4%BE%9D%E6%8D%AE%E5%8A%A8%E6%80%81%E5%BC%80%E9%94%80%E6%A8%A1%E5%9E%8B%E7%A1%AE%E5%AE%9A%E5%85%B6%E4%BD%8D%E7%BD%AE%E3%80%82%0A%0A%E4%BD%8D%E7%BD%AE%E5%9B%A0%E5%AD%90%EF%BC%8C%E8%A1%A8%E7%A4%BA%E6%8F%92%E5%85%A5%2F%E6%8F%90%E5%8D%87%E4%BD%8D%E7%BD%AEP%20F%EF%BC%8C%E5%AE%9A%E4%B9%89%E4%B8%BA%3A%24%24PF%20%3D%20(M%7BPRpre%7D%20%E2%88%97%20C%7BPR%7D%20%2B%20M%7BPWpre%7D%20%E2%88%97%20C%7BPW%7D%20)%2FC#card=math&code=H%7Bpre%7D%2C%20M%7BPRpre%7D%2C%20M%7BPWpre%7D%2C%20M%7BDRpre%7D%2C%20M%7BDWpre%7D%24%24%E5%88%86%E5%88%AB%E8%A1%A8%E7%A4%BA%E5%9C%A8%E5%89%8D%E4%B8%80%E4%B8%AA%E8%BF%9B%E7%A8%8B%E9%98%B6%E6%AE%B5%E7%9A%84%E6%9C%80%E5%90%8E%E4%B8%80%E7%BA%A7%E7%BC%93%E5%AD%98%E4%B8%AD%E7%9A%84%E6%9C%80%E5%90%8E%E4%B8%80%E7%BA%A7%E7%BC%93%E5%AD%98%E5%91%BD%E4%B8%AD%E7%8E%87%EF%BC%8CPCM%E8%AF%BB%E9%81%97%E6%BC%8F%E7%8E%87%EF%BC%8CPCM%E5%86%99%E9%81%97%E6%BC%8F%E7%8E%87%EF%BC%8CDRAM%E8%AF%BB%E4%B8%A2%E7%8E%87%E5%92%8CDRAM%E5%86%99%E9%81%97%E6%BC%8F%E7%8E%87%EF%BC%8CC%E8%A1%A8%E7%A4%BA%E5%BC%80%E9%94%80%E3%80%82%0A%0A%0A%0A%23%23%23%23%23%20%E5%9F%BA%E4%BA%8E%E8%BF%9B%E7%A8%8B%E9%98%B6%E6%AE%B5%E7%9A%84%E8%BF%87%E7%A8%8B%E5%88%86%E6%9E%90%0A%0A%E6%80%A7%E8%83%BD%E7%9B%91%E8%A7%86%E5%99%A8%E5%8D%95%E5%85%83%28PMU%29%E5%8F%AF%E4%BB%A5%E6%9D%A5%E6%A3%80%E6%B5%8B%E6%9C%AB%E7%BA%A7%E7%BC%93%E5%AD%98%E5%91%BD%E4%B8%AD%E7%8E%87%EF%BC%8C%E5%B9%B6%E4%B8%94%E5%85%B6%E5%9C%A8%E5%BD%93%E5%89%8D%E6%AF%8F%E4%B8%AACPU%E4%B8%AD%E9%83%BD%E5%AD%98%E5%9C%A8%EF%BC%8C%E5%BC%80%E9%94%80%E5%8F%AF%E4%B8%8D%E8%AE%B0%E3%80%82%0A%0A%E7%84%B6%E8%80%8C%EF%BC%8CPMU%E5%8F%AA%E8%83%BD%E8%AE%B0%E5%BD%95%E5%9C%A8%E7%BB%9F%E4%B8%80%E6%80%BB%E4%B8%BB%E5%AD%98%E7%9A%84%E9%81%97%E6%BC%8F%E7%8E%87%EF%BC%8C%E9%9C%80%E8%A6%81%E9%80%9A%E8%BF%87%E6%95%B0%E6%8D%AE%E5%88%86%E5%89%B2%E7%AE%97%E6%B3%95%E5%8E%BB%E5%88%A4%E6%96%AD%E6%98%AF%E5%B1%9E%E4%BA%8EDRAM%E8%BF%98%E6%98%AFPAM%E3%80%82%0A%0A%0A%0A%23%23%23%23%23%20%E5%8A%A8%E6%80%81%E8%87%AA%E9%80%82%E5%BA%94%E6%9B%BF%E6%8D%A2%E7%AD%96%E7%95%A5%E7%AE%97%E6%B3%95%0A%0A%E7%BC%93%E5%AD%98%E6%9B%BF%E6%8D%A2%E7%AD%96%E7%95%A5%E8%A2%AB%E5%88%86%E4%B8%BA%E4%B8%A4%E9%83%A8%E5%88%86%EF%BC%9A%E6%8F%92%E5%85%A5%E7%AD%96%E7%95%A5%20%2B%20%E6%8F%90%E5%8D%87%E7%AD%96%E7%95%A5%0A%0A%E6%8F%92%E5%85%A5%E7%AD%96%E7%95%A5%E5%86%B3%E5%AE%9A%E5%BD%93%E7%BC%93%E5%AD%98%E9%81%97%E6%BC%8F%E6%97%B6%E6%96%B0%E6%95%B0%E6%8D%AE%E8%A2%AB%E6%8F%92%E5%85%A5%E7%BC%93%E5%AD%98%E9%9B%86%E7%9A%84%E4%BD%8D%E7%BD%AE%E3%80%82%E6%8F%90%E5%8D%87%E7%AD%96%E7%95%A5%E5%86%B3%E5%AE%9A%E5%BD%93%E7%BC%93%E5%AD%98%E5%91%BD%E4%B8%AD%E6%97%B6%E8%A2%AB%E6%8F%90%E5%8D%87%E7%9A%84%E4%BD%8D%E7%BD%AE%E3%80%82%0A%0ADARP%E6%8F%90%E5%87%BA%E6%89%80%E6%9C%89%E7%9A%84PCM%E6%95%B0%E6%8D%AE%E5%BA%94%E5%BD%93%E8%A2%AB%E6%8F%92%E5%85%A5%E5%9C%A8MRU%E4%B8%AD%E4%BB%A5%E5%87%8F%E5%B0%91%E4%B8%A2%E5%A4%B1%E7%8E%87%EF%BC%8C%E8%80%8CDRAM%E6%95%B0%E6%8D%AE%E5%BA%94%E5%BD%93%E4%BE%9D%E6%8D%AE%E5%8A%A8%E6%80%81%E5%BC%80%E9%94%80%E6%A8%A1%E5%9E%8B%E7%A1%AE%E5%AE%9A%E5%85%B6%E4%BD%8D%E7%BD%AE%E3%80%82%0A%0A%E4%BD%8D%E7%BD%AE%E5%9B%A0%E5%AD%90%EF%BC%8C%E8%A1%A8%E7%A4%BA%E6%8F%92%E5%85%A5%2F%E6%8F%90%E5%8D%87%E4%BD%8D%E7%BD%AEP%20F%EF%BC%8C%E5%AE%9A%E4%B9%89%E4%B8%BA%3A%24%24PF%20%3D%20%28M%7BPRpre%7D%20%E2%88%97%20C%7BPR%7D%20%2B%20M%7BPWpre%7D%20%E2%88%97%20C_%7BPW%7D%20%29%2FC)

C: 平均开销

CACHE_大数据存储DRAM／PCM混合存储器共享级缓存中的动态自适应替换策略 - 图6%24%24%3A%20PCM%E6%95%B0%E6%8D%AE%E9%81%97%E6%BC%8F%E5%BC%80%E9%94%80%0A%0ADARP%E7%AE%97%E6%B3%95%E5%9F%BA%E4%BA%8EPF%EF%BC%8C%E5%AE%9A%E4%B9%89PF0%3D0.3%2C%20PF1%3D0.6.%EF%BC%8CPF%E5%80%BC%E8%B6%8A%E5%B0%8F%EF%BC%8C%E7%BC%93%E5%AD%98%E6%80%A7%E8%83%BD%E5%AF%B9PCM%E8%AE%BF%E9%97%AE%E6%88%90%E6%9C%AC%E8%B6%8A%E4%B8%8D%E6%95%8F%E6%84%9F%EF%BC%8CPF%E5%80%BC%E8%B6%8A%E5%A4%A7%EF%BC%8C%E5%AF%B9PCM%E8%AE%BF%E9%97%AE%E6%88%90%E6%9C%AC%E8%B6%8A%E6%95%8F%E6%84%9F%E3%80%82%E5%9B%A0%E6%AD%A4%EF%BC%8C%E5%A6%82%E6%9E%9CPF%E5%80%BC%E5%BE%88%E5%B0%8F%EF%BC%8CDRAM%E6%95%B0%E6%8D%AE%E7%9A%84%E6%8F%92%E5%85%A5%2F%E6%8F%90%E5%8D%87%E4%BD%8D%E7%BD%AE%E5%8F%AF%E4%BB%A5%E5%9C%A8MRU%E9%99%84%E8%BF%91%EF%BC%8C%E5%90%A6%E5%88%99%EF%BC%8CDRAM%E6%95%B0%E6%8D%AE%E7%9A%84%E6%8F%92%E5%85%A5%2F%E6%8F%90%E5%8D%87%E4%BD%8D%E7%BD%AE%E5%BF%85%E9%A1%BB%E5%9C%A8LRU%E9%99%84%E8%BF%91%E3%80%82%0A%0A%E5%9B%A0%E6%AD%A4%EF%BC%8C%E5%AF%B9PCM%E6%95%B0%E6%8D%AE%E9%80%82%E7%94%A8LRU%EF%BC%8C%E5%AF%B9DRAM%E6%95%B0%E6%8D%AE%E9%80%82%E7%94%A8DARP%E3%80%82%0A%0ADARP%20algorithm%0A%0A%60%60%60python%0Aif%200%20%3C%20P%20and%20F%20%3C%20PF0%3A%0A%09T%20%3D%206%20%E2%88%97%20N%2F16%0Aelse%20if%20PF0%20%3C%3D%20PF%20%3C%20PF1%3A%0A%09T%20%3D%2010%20%E2%88%97%20N%2F16%0Aelse%20if%20PF1%20%3C%3D%20PF%20%3C%3D%201%3A%0A%09T%20%3D%2013%20%E2%88%97%20N%2F16%0Areturn%20T%0A%60%60%60%0A%0A%0A%0A%23%23%23%23%20IV.%E5%AE%9E%E9%AA%8C%E8%A3%85%E7%BD%AE%0A%0A%23%23%23%23%20V.%E7%BB%93%E6%9E%9C%E5%92%8C%E5%88%86%E6%9E%90%0A%0A%E9%AA%8C%E8%AF%81%E9%83%A8%E5%88%86%E7%95%A5%E8%BF%87%E3%80%82%0A%0A%0A%0A%23%23%23%23%20VI.%E7%9B%B8%E5%85%B3%E5%B7%A5%E4%BD%9C%0A%0A%E5%85%B3%E4%BA%8E%E6%9C%80%E5%90%8E%E4%B8%80%E7%BA%A7%E7%BC%93%E5%AD%98%E7%AE%A1%E7%90%86%E6%9C%BA%E5%88%B6%E7%9A%84%E7%A0%94%E7%A9%B6%E5%BE%88%E5%A4%9A%EF%BC%8C%E5%8F%AF%E4%BB%A5%E5%88%86%E4%B8%BA%E4%B8%A4%E7%B1%BB%3A%E6%9B%BF%E6%8D%A2%E7%AD%96%E7%95%A5%E5%92%8C%E5%88%86%E5%8C%BA%E6%9C%BA%E5%88%B6%E3%80%82%0A%0A#card=math&code=%28M%7BPRpre%7D%20%E2%88%97%20C%7BPR%7D%20%2B%20M%7BPWpre%7D%20%E2%88%97%20C%7BPW%7D%20%29%24%24%3A%20PCM%E6%95%B0%E6%8D%AE%E9%81%97%E6%BC%8F%E5%BC%80%E9%94%80%0A%0ADARP%E7%AE%97%E6%B3%95%E5%9F%BA%E4%BA%8EPF%EF%BC%8C%E5%AE%9A%E4%B9%89PF0%3D0.3%2C%20PF1%3D0.6.%EF%BC%8CPF%E5%80%BC%E8%B6%8A%E5%B0%8F%EF%BC%8C%E7%BC%93%E5%AD%98%E6%80%A7%E8%83%BD%E5%AF%B9PCM%E8%AE%BF%E9%97%AE%E6%88%90%E6%9C%AC%E8%B6%8A%E4%B8%8D%E6%95%8F%E6%84%9F%EF%BC%8CPF%E5%80%BC%E8%B6%8A%E5%A4%A7%EF%BC%8C%E5%AF%B9PCM%E8%AE%BF%E9%97%AE%E6%88%90%E6%9C%AC%E8%B6%8A%E6%95%8F%E6%84%9F%E3%80%82%E5%9B%A0%E6%AD%A4%EF%BC%8C%E5%A6%82%E6%9E%9CPF%E5%80%BC%E5%BE%88%E5%B0%8F%EF%BC%8CDRAM%E6%95%B0%E6%8D%AE%E7%9A%84%E6%8F%92%E5%85%A5%2F%E6%8F%90%E5%8D%87%E4%BD%8D%E7%BD%AE%E5%8F%AF%E4%BB%A5%E5%9C%A8MRU%E9%99%84%E8%BF%91%EF%BC%8C%E5%90%A6%E5%88%99%EF%BC%8CDRAM%E6%95%B0%E6%8D%AE%E7%9A%84%E6%8F%92%E5%85%A5%2F%E6%8F%90%E5%8D%87%E4%BD%8D%E7%BD%AE%E5%BF%85%E9%A1%BB%E5%9C%A8LRU%E9%99%84%E8%BF%91%E3%80%82%0A%0A%E5%9B%A0%E6%AD%A4%EF%BC%8C%E5%AF%B9PCM%E6%95%B0%E6%8D%AE%E9%80%82%E7%94%A8LRU%EF%BC%8C%E5%AF%B9DRAM%E6%95%B0%E6%8D%AE%E9%80%82%E7%94%A8DARP%E3%80%82%0A%0A%2A%2ADARP%20algorithm%2A%2A%0A%0A%60%60%60python%0Aif%200%20%3C%20P%20and%20F%20%3C%20PF0%3A%0A%09T%20%3D%206%20%E2%88%97%20N%2F16%0Aelse%20if%20PF0%20%3C%3D%20PF%20%3C%20PF1%3A%0A%09T%20%3D%2010%20%E2%88%97%20N%2F16%0Aelse%20if%20PF1%20%3C%3D%20PF%20%3C%3D%201%3A%0A%09T%20%3D%2013%20%E2%88%97%20N%2F16%0Areturn%20T%0A%60%60%60%0A%0A%0A%0A%23%23%23%23%20IV.%E5%AE%9E%E9%AA%8C%E8%A3%85%E7%BD%AE%0A%0A%23%23%23%23%20V.%E7%BB%93%E6%9E%9C%E5%92%8C%E5%88%86%E6%9E%90%0A%0A%E9%AA%8C%E8%AF%81%E9%83%A8%E5%88%86%E7%95%A5%E8%BF%87%E3%80%82%0A%0A%0A%0A%23%23%23%23%20VI.%E7%9B%B8%E5%85%B3%E5%B7%A5%E4%BD%9C%0A%0A%E5%85%B3%E4%BA%8E%E6%9C%80%E5%90%8E%E4%B8%80%E7%BA%A7%E7%BC%93%E5%AD%98%E7%AE%A1%E7%90%86%E6%9C%BA%E5%88%B6%E7%9A%84%E7%A0%94%E7%A9%B6%E5%BE%88%E5%A4%9A%EF%BC%8C%E5%8F%AF%E4%BB%A5%E5%88%86%E4%B8%BA%E4%B8%A4%E7%B1%BB%3A%2A%2A%E6%9B%BF%E6%8D%A2%E7%AD%96%E7%95%A5%E5%92%8C%E5%88%86%E5%8C%BA%E6%9C%BA%E5%88%B6%2A%2A%E3%80%82%0A%0A)