改进的偏向写调度的混合内存缓冲区调度策略

刘 兵 ，汪令辉，张 锐，崔 莹，段 峰

（1.中国科技大学 计算机科学与技术学院，安徽 合肥 230027；2.铜陵职业技术学院 信息工程系，安徽 铜陵 244061；3.铜陵有色金属集团公司，安徽 铜陵 244000）

随着大数据、人工智能等技术的发展，数据的处理量越来越大，这对计算机的主存储器提出了越来越高的要求。当前，以动态随机存取存储器（dynamic random access memory，DRAM）为主的主存储技术也面临着较大的挑战，主要面临的问题为DRAM 存储集成已达极限，且能耗也是一个重要问题。人们从软件和硬件等方面提出了多种方式，希望弥补这一缺点，比如通过非易失存储（non-volatile memory，NVM）来解决这一问题。非易失存储具有较高的集成度、非易失、低能耗、字节寻址等特点。非易失存储器有电阻随机存储器ReRAM[1]、自旋磁存储器[2]、相变存储器[3]（phase change memory，PCM）等。其中，PCM 具有良好的可扩展性，有望成为新一代的主流技术。

1 研究背景和相关工作

1.1 PCM的相关特性

相变存储器是一种硫族化合物，分为晶体状态和非晶体状态。它具有写的不对称性，PCM写1（SET）的时候，要施加一个时间长、电压低的电脉冲，温度在结晶点以上、融化点以下，导致其结晶，物质从非晶态到晶态转化。PCM写0（RESET）的时候，要施加一个电压高、时间短的电脉冲，当温度上升到溶点后，再经过一个淬火（降温速率大于109 K/s）的过程，物质从晶态到非晶态转化。

相变存储器在晶态和非晶态时，其阻抗是不同的，当施加一个电压时，对应的电流不同，从而可以判断为0或1。PCM读的过程中，电流通过时产生的热量很小，不会引起晶态的变化。

PCM和DRAM 相比较，具有存储密度大和无空闲功耗的优点。DRAM的工艺制程是PCM的4倍，所以在相同的芯片面积下，PCM可以增加更大的容量；DRAM 空闲时，需要通过不断地刷电来保持数据，而PCM为非易失性存储设备，不需要刷电。

PCM和DRAM 相比较，也有它自身的缺点，主要如下：

1）PCM的读操作时间是DRAM的2倍，功耗相差不大；

2）PCM的写操作时间是DRAM的10倍，PCM写功耗比DRAM 大；

3）PCM的写次数为108～1 012，DRAM几乎无限，写次数为大于1 015。

1.2 PCM在内存中的应用

1.2.1 混合内存架构

目前，针对PCM的特性，许多研究者尝试结合二者的优点，提出了混合内存[4-9]的概念。混合内容的主要架构方式包括层次架构和平行架构两种。

1）层次架构。该方式下，DRAM 作为PCM的缓存，所有的请求都先访问DRAM，当请求没有选中是时，再访问PCM。这种架构方式的优点是利用DRAM 弥补PCM的写不足，同时利用PCM 增加存储密度，利用其非易失性存储特点，减少空闲能耗。

2）平行架构。该方式中PCM和DRAM的同一层混合使用，整个内存由两者共同组成，统一编址，数据只放在PCM或者DRAM中的一个中，如将写倾向较高的页面放在DRAM中，将读倾向较高的页面放在PCM中。

在层次架构下，当出现对内存需要较大的调用时，会增大DRAM和PCM 交换的工作量，系统效率较大下降，并且会增大PCM的磨损。平行架构中，根据PCM 也是字节寻址的特点，将DRAM和PCM统一地址空间，但由于二者的读写等特性不一样，为了降低能耗并延长PCM的使用时间，缓冲区的管理算法就显得尤为重要。

1.2.2 平行架构缓冲区管理算法

已有关于混合内存的缓冲区管理算法主要有LRU-WPAM（least recently used with prediction and migration）[10-11]和CLOCK-DWF（clock with dirty bit and write frequency）[12]。其中，CLOCK-DWF算法对CLOCK 算法进行了改进，通过记录每个页面的写次数来判断读倾向和写倾向，从而调度写倾向在DRAM中，读倾向在PCM中；LRU-WPAM算法以最近最少使用（LRU）算法为基础，增加了一个页面读写预测机制，从而进行页面的调度。

在LRU-WPAM的缓冲区管理中，当缓冲区页面未命中时，与LRU算法一样，选择缓冲区最近最少使用的页面进行置换；当缓冲区中页面命中时，首先根据读写请求修改页面权值，然后判断是否达到阀值，并根据权值决定是否将页面移动到PCM或者DRAM中，如果目标存储器上没有空闲空间，在DRAM中选择读子队列尾部页面释放，在PCM上选择写子队列尾部页面释放。

在CLOCK-DWF的缓冲区管理中，首先，将DRAM和PCM分别组成一个环状队列；然后，根据数据访问时的读写类型，将写请求的页面存放在DRAM中，读请求页面存放在PCM中。当DRAM空闲空间不足时，将“写”冷页写入PCM，当PCM空闲空间不足时，用CLOCK页面调度的算法对页面进行调度。

2 FWLRU混合内存缓冲区调度策略

在上述算法的混合内存管理中，根据“写”热页和“读”热页的判断，调度页面在PCM或者DRAM中存储。如果所在页面当前存储和判断的结果不一致，则需要进行PCM和DRAM的页面迁移。根据以上调度算法，主要会造成以下几个问题：

1）频繁地在PCM和DRAM中进行页面迁移，要消耗大量的系统资源。同时，当PCM和DRAM中的空闲空间不足时，需要从二者中选择页面进行释放，释放的页面可能就是即将访问的页面，这样就会将缓冲区原先命中的访问变成没有命中，造成缓冲区命中率下降。

2）将“读”热页从DRAM中迁入PCM，迁移写入时实际上增加了PCM的写，与减少PCM写的初衷不一致。

3）当页面的访问是读倾向较多的时候，按照LRU-WPAM、CLOCK-DWF算法的要求，都要迁移进入PCM，这样反而造成PCM写的增加。

另外，根据A.R.Alameldeen 等的研究[13-15]，内存数据访问具有明显的局部性，局部数据的访问达到40%以上，有些情况下甚至超过60%。

针对以上情况，本文提出一种偏向写调度缓冲区调度策略（favors write least recently used，FWLRU）的混合内存缓冲区调度策略，主要进行了以下两个方面的优化：

1）只进行“写”热页的调度，而不进行“读”热页的调度。混合内存的主要目的是充分利用PCM的高存储密度和低能耗这两个优点来优化内存，避免PCM读写不均衡、写有限等缺点。DRAM和PCM在读上区别并不大，如果强制将所有大于权值的读倾向页移动进入PCM，将增加PCM的写操作，特别是如果读操作较多时，写的次数将更多。但是如果不进行读页面的调度，对系统性能将没有什么影响。所以在FWLRU算法中只考虑将“写”热页调度进入DRAM，而不进行“读”热页的调度。

2）“写”热页采取PCM和DRAM页面互换的原则进行迁移。在将“写”热页从PCM 置换到DRAM 过程中，当DRAM 空间不够时，如果采取淘汰策略，有可能淘汰的页面就是下一次就要访问的页面，这样就把将要访问的页面淘汰掉了，从而把原本命中的操作变成了不命中，降低了命中率。而FWLRU算法中，不进行页面的淘汰，只是将PCM页面的DRAM中的页面采取互换原则，以此避免淘汰可能将要被访问的页面，提高页面的命中率。

2.1 访问行为记录

FWLRU混合内存缓冲区调度策略中使用了3个LRU队列：DRAM读队列（DR）、DRAM写队列（DW）、PCM写队列（PW）。

LRU队列在缓冲区中按照访问时间组成队列，其中，最近访问位于队列首部，最长时间访问位于队列尾部。DR队列记录DRAM中页面的读操作，DW队列记录DRAM中的写操作，PW 队列记录PCM中的写操作，都按照最近访问原则从前至后排列。

2.2 PCM中“写”热页和DRAM中页面的互换

FWLRU 偏向写调度的缓冲区调度策略中，当缓冲区块命中时，修改页面的权值，如果是“读”命中，权值增加；如果是“写”命中，权值减少。将权值和“读写热页判定标准”阀值进行比较，若页面权值小于阀值，则说明是一个“写”热页。根据缓冲区和内存空间的物理地址（internal memory address）映射，查看这个页面的物理地址是在DRAM中还是在PCM中，如果在PCM中，要进行PCM和DRAM 空间页面的互换，同时将页面加在LRU队列首部。和“读写热页判定标准”阀值比较，如果大于阀值，则说明是一个“读”热页，不进行操作。

同时，根据读写操作，如果是写，那么根据物理地址的映射，加入到DW或者PW 队列的头部；如果是DRAM读写，那么加入到队列的头部，并修改页面的权值。

“写”热页将执行页面从PCM写入DRAM，如果DRAM 空间有空闲，那么直接写入；如果DRAM空间已满，那么将DR队列尾部页面和“写”热页互换，如图1所示。页面互换时，不进行DRAM页面的淘汰，这样可以避免将有可能即将访问的页面淘汰掉，把页面原本的命中操作变成不命中操作，从而降低缓冲区的页面命中率。

图1 PCM写热页与DRAM中DR队列尾部页面互换Fig.1 Exchange of PCM hot page and DR queue tail page in DRAM

2.3 调度流程

算法1 描述了混合内存缓冲区调度策略的调度流程。算法中IMAddr（internal memory address）为页面从缓冲区映射到内存的物理地址，物理地址根据字节地址范围划分为DRAM和PCM 区域。页面如果判定是“写”热页，且IMAddr在PCM中时，执行2.2所述页面互换工作。缓冲区页面访问类型为“读”时，修改页面权值加1，同时将页面序列加入到LRU和DR队列头部。

算法1 混合内存缓冲区调度策略流程

算法完成后，返回IMAddr值。

3 实验结果及分析

3.1 实验方法

本实验采用在ubuntu 18.04系统上架设GEM5[16]模拟器仿真，同时安装NVMain[17-18]模拟相变存储器，从而实现DRAM和PCM 混合实验环境。系统采用SE（系统调用）模式，PCM的延迟数据参照F.Bedeschi的研究[19]，DRAM的延迟参照Micron的测试[20]。每个页面大小设定为固定值4 kB，DRAM和PCM的比例采取固定配置形式，按照1∶4 配置，整体存储空间按照实验需要进行增大或减少。

本实验选用的数据集由真实数据和合成数据两部分构成，其中真实数据出自于安徽芜湖某电商网站交易系统的某日交易记录，该数据集对数据库进行了356 733次读和115 790次写操作；合成数据来自开源软件DiskSim，版本为4.0。DiskSim 进行磁盘读写模拟，同时改变配置参数，设置局部性读写不同的比例来得到系列数据集，挑选其中具有代表性的4个数据组参与混合内存实验。局部性（Locality）中“80%/20%”，指80%的数据发生在20%的空间上。具体实验数据集测试参数见表1。

表1 实验数据集Table1 Experimental data set

3.2 页面命中率

将FWLRU混合内存缓冲区调度策略和LRU、LRU-WPAM、CLOCK-DWF在模拟器上进行了页面命中率检测。图2给出了5组测试数据集在内存页面逐渐增大的情况下，4种不同的缓冲区调度下页面未命中的数量。

图2 不同调度策略下的命中率实验结果Fig.2 Experiment results of hit rate under different scheduling

分析图2所示实验结果数据，可得出以下结果：

1）从图2a至2e的5组类型数据的实验情况看，随着内存容量逐渐增大，页面未命中的数量明显减小。可见内存容量的大小对命中率有着直接的影响，容量越大，命中率越高。

2）从命中率情况看，FWLRU算法的命中率比LRU-WPAM和CLOCK-DWF的要高，接近LRU算法的。这和FWLRU算法中不进行页面的淘汰有关，只是将“写”热页从PCM到DRAM的互换，防止了将即将访问的页面淘汰而造成的命中率下降。

通过实验结果对比可以看出，相对于LRUWPAM和CLOCK-DWF算法，FWLRU算法提高了页面的命中率。

3.3 PCM写次数

设定内存空间大小固定为1GB（DRAM 与PCM的比值为1∶4）的情况下，对PCM在FWLRU、LRU、LRU-WPAM、CLOCK-DWF 4种策略下的写总次数进行实验模拟，结果如图3所示。

图3 不同调度策略下的PCM写次数实验结果Fig.3 Experiment results of PCM write times under different scheduling

通过图3所示实验数据可以看出，LRU 由于不考虑两种存储介质的不同，没有进行“写”热页和“读”热页的调度，所以PCM写的次数最多；LRU-WPAM和CLOCK-DWF 考虑了PCM和DRAM 这两种存储介质，并进行了将“写”热页存放在DRAM、“读”热页存放在PCM上，导致PCM写的数量有所降低，但将“读”热页集中到PCM上，移动的过程也增加了PCM的写，并且对读比例大的页面进行访问，反而有可能加大PCM的写。FWLRU 考虑读操作上DRAM和PCM的区别不大，故不进行“读”热页的移动，只将“写”热页互换到DRAM中，所以PCM写的次数比LRU-WPAM和CLOCK-DWF的有所降低。实验结果证明，FWLRU 对PCM 进行了优化，写的次数减少。

4 结论

非易失性存储材料PCM 是解决DRAM的存储密度和降低能耗的好材料，但是PCM 具有读写不对称和写有限等缺点，许多研究者提出以多种混合内存的缓冲区调度策略来解决这一问题。本文在混合内存架构的基础上，提出了一种偏向写调度的混合内存缓冲区调度策略。

1）只将“写”热页从PCM 置换进DRAM，没有将“读”热页写入PCM，避免了调度过程中或者频繁调度中对PCM的写，特别是读偏向较多的页面；

2）PCM和DRAM 采取页面互换的形式，不从DRAM中淘汰页面，避免了将可能即将访问的页面淘汰，将命中操作变成没有命中操作的情况，提高了页面访问的命中率。

3）本文从缓冲区调度入手来解决PCM读写不对称、写有限等问题。但是冷热页的划分还是采取简单的权值计数方式，这种冷热页划分方式是否过于简单还有待考证；而且没有对PCM的磨写均衡进行考虑，这是下一步研究的方向。