PCM混合主存系统的写感知主存管理算法*

何爱华，岳丽华，吴章玲，郭有强.蚌埠学院 计算机科学与技术系，安徽 蚌埠 33030.中国科学技术大学 计算机科学与技术学院，合肥 3007



PCM混合主存系统的写感知主存管理算法*

何爱华1,2+，岳丽华2，吴章玲2，郭有强1
1.蚌埠学院 计算机科学与技术系，安徽 蚌埠 233030
2.中国科学技术大学 计算机科学与技术学院，合肥 230027

HE Aihua,YUE Lihua,WU Zhangling,et al.Write-aware memory management in PCM-based hybrid memory systems.Journal of Frontiers of Computer Science and Technology,2016,10(6)：799-810.

摘要：相变存储器（phase change memory，PCM）凭借字节可寻址，读取速度快（纳秒级），高存储密度，低能耗等优点，在目前基于DRAM（dynamic random access memory）的主存扩展达到瓶颈的情形下，已经成为最具前途的主存存储介质之一，但是PCM有高写延迟，寿命有限等缺陷，因此出现了DRAM/PCM混合主存架构。提出了一种以减少PCM写和保持命中率为目标的混合主存管理算法——写感知的CLOCK算法（CLOCK with a write-aware strategy，CLOCKW）。已有研究主要基于写临近信息（recency of writes，RW）来预测页面写热度，CLOCKW引入内在写距离（inter-write-distance，IWD）概念，并结合写临近信息来预测页面写热度，从而把写密集页面放置在DRAM。此外，CLOCKW通过记录有限的历史写操作信息，将新置换进的页面放在合适的存储介质，避免不必要的页面迁移。最后，基于CLOCK算法的CLOCKW满足虚拟主存管理的低代价要求。实验显示，CLOCKW在保持命中率前提下，可以有效减少PCM写次数。

关键词：相变存储器；混合主存；写感知；主存管理

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0799-12

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

信息爆炸时代产生的海量数据，对数据处理和数据分析技术带来了挑战，其中首当其冲的是大数据存储技术的挑战。为了克服数据存取过程中DRAM（dynamic random access memory）和二级存储之间的I/O瓶颈，主张配置大容量DRAM的全新分布式内存计算平台Spark[1]成为热门话题。但是单节点上基于DRAM的主存扩展已经达到瓶颈，限制了高效数据处理与分析技术的发展[2]。以相变存储器（phase change memory，PCM）为代表的新型非易失存储器，凭借接近DRAM的读速度和支持字节可寻址的特性，以及存储密度高，非易失，能耗低等优点，一度被期望代替DRAM成为新的主存存储介质（如图1（a）所示）[3]。但是PCM的写延迟高，寿命有限等固有缺陷，使PCM完全代替DRAM作为主存的方案不可行。因此，基于DRAM/PCM的混合主存模型成为当前的一个研究热点[4-8]。目前主流的混合主存模型有两种：一种是仅PCM的物理地址对操作系统可见，而DRAM作为PCM的缓存，类似于L1、L2片上缓存，其地址空间对操作系统不可见（如图1（b）所示）；另一种是DRAM和PCM的物理地址空间都对操作系统可见，操作系统可以对两种存储介质统一编址（如图1（c）所示）。对于图1（b）所示结构，整个主存架构存储层次比其他两种主存架构多一层，CPU访问主存数据需要多一层的映射机制转换。另外，CPU访问数据都需要经过DRAM缓冲，而CPU上运行程序的多样性和访问数据的大规模性，将会导致DRAM与PCM之间数据交互增多，频繁的DRAM数据置换和PCM数据读写将极大影响系统的整体性能。因此本文聚焦于基于图1（c）架构的主存管理研究[9]。

目前基于PCM的混合主存管理技术，主要是针对PCM的读写不均衡和写寿命有限的特性，对传统面向DRAM的CLOCK、LRU（least recently used）算法进行改进，以减少PCM写为目标，将写操作集中在DRAM。LRU-WPAM（LRU with prediction and migration）[10]通过预测页面读写倾向性，将读倾向页迁移到PCM，写倾向页迁移到DRAM来减少PCM写操作。CLOCK-DWF（CLOCK with dirty bits and write frequency）[11]通过页面迁移策略，致力于用DRAM服务所有发生在PCM的写请求。但是这两种算法在页面迁移时都会将一个页面替换出主存，造成命中率下降。主存读写速度比二级存储高多个数量级，因此命中率下降会严重影响算法整体性能。在页缺失情况下，从二级存储读一个页面到PCM主存时，也会造成PCM写操作，因此D-CLOCK（dual-CLOCK）[12]必要时替换DRAM的页来限制PCM上发生页缺失的次数，从而减少PCM的写次数，这也是以降低命中率为代价。MHR-LRU（maintain-hit-ratio LRU）[13]和APP-LRU（access pattern prediction based LRU）[14]以保证命中率为首要目标，但是只有在页缺失情况下才会触发页面迁移操作，不能及时将写倾向页迁移到DRAM，性能提升有限。

Fig.1　Architectures of PCM-based memory systems图1　基于PCM的主存系统架构图

LRU算法造成频繁的链表移动以及需要较多的硬件支持，因此并没有应用到操作系统的虚拟主存管理中，而是广泛应用于类似于数据库系统缓冲区管理的场景。近似于LRU但是代价更低的CLOCK算法成为虚拟主存管理的主流算法[15-16]。因此，本文提出一种基于CLOCK的混合主存管理算法——写感知的CLOCK算法（CLOCK with a write-aware strategy，CLOCKW）。CLOCKW保留了原CLOCK的数据结构以及页面替换算法，因此可以保持和CLOCK相同的命中率。此外，CLOCKW以减少PCM写为目标，关注页面写热度预测，以便及时将写热度高的页面存储到DRAM。CLOCKW借鉴LIRS（low inter reference recency set）[17]的IRR（inter-reference recency）思想，引入了内在写距离（inter-write-distance，IWD）概念，并结合页面写临近信息（recency of writes，RW）来定义页面写热度，用于决策是否将页面存储于DRAM来减少PCM写次数。同时，当页面被替换出主存时，CLOCKW并不立即丢弃该页写信息，而是继续保留一段时间，用于未来该页重新被载入主存时衡量页面写热度，从而将该页存储在合适的存储介质上，避免将来不必要的页面迁移。为了满足虚拟主存管理的低代价需求，CLOCKW只保留限定数目的当前写和历史写信息。因此，CLOCKW不仅有媲美于CLOCK的命中率，而且能有效预测页面写热度，从而将热写页存储到DRAM上减少PCM上的写次数，还可以实际应用于混合主存系统的虚拟主存管理。

2　相关工作

国内PCM存储器上的研究开展得较早，取得的成果也较多。PCM存储器研究工作的主要机构有上海微系统与信息技术研究所、华中科技大学、国防科技大学、中国科学技术大学、清华大学等，它们主要致力于国产PCM芯片[18]、PCM存储单元纠错机制[19]、缓冲区管理[12-14]等方面的研究。

由于混合存储系统中不同介质的访问速度不同，且PCM写寿命有限，传统的面向DRAM主存系统的页面置换算法已不再适用。

LRU-WPAM[10]在原LRU算法的基础上，分别增加了DRAM读链表、写链表和PCM读链表、写链表，用于监控主存中每个页的读写请求，并以此为基础将读倾向页迁移到PCM、写倾向页迁移到DRAM。MHR-LRU[13]和APP-LRU[14]都是在页缺失时进行页面迁移操作。MHR-LRU使用DRAM写链表——DWL（DRAM write-aware LRU）记录DRAM页的写操作信息，当DRAM页面被写时，被写页被置于DWL链表头部，因此位于DWL链表尾部的页面被认为是写最冷的页面。如果写一个新页面触发页面置换，而置换出的页面在PCM，MHR-LRU将DRAM中写最冷的页迁移到PCM刚置换出的空间，同时将新页面存储于DRAM以服务于新页面上写请求。APPLRU记录了部分被替换出页的读写信息作为访问历史信息，并结合页面当前访问信息衡量页面读写倾向性。当页缺失时，可根据新页面的访问历史信息选择合适的存储介质。

CLOCK-DWF[11]分别用一个改进的CLOCK链表和通用CLOCK链表管理DRAM和PCM中的页面。CLOCKW-DWF所有写请求都会在DRAM执行，当一个新页面或PCM页面写命中时，都会将页面载入DRAM，若此时DRAM没有空闲页面，CLOCK-DWF会根据DRAM页面的最近被写操作命中的情况和写频率判断页面写冷热，从而将DRAM写最冷的页面迁移到PCM。如果PCM没有空闲空间存放从DRAM迁移出的页面，会调用CLOCK算法将一个PCM页替换出主存，引起命中率下降。D-CLOCK[12]采用与CLOCK-DWF相同的策略处理写请求，即所有写请求都会在DRAM执行。但是D-CLOCK使用全局CLOCK链表管理DRAM和PCM页面，用于页面置换时选择替换出的页面，同时维护一个额外链表监控DRAM上页面RW和写频率，用于区分写热度高（热写）页和写热度低（冷写）页。此外，DCLOCK并不是严格遵从CLOCK算法选择替换页，必要时替换DRAM的页来限制PCM上发生页缺失的次数，因为即使读一个页到PCM也会产生一次PCM写，而强制替换DRAM页可能会降低命中率。

综上所述，LRU-WPAM和APP-LRU算法的数据划分方法为读写倾向性划分，致力于将读倾向的页面存储到PCM上，写倾向的页面存储到DRAM上。前者在页面迁移时可能将一个页面换出缓冲区，引起命中率下降；而后者虽然能保证命中率，但页面替换时才可能触发页面迁移操作，不能将读写倾向性发生变化的页面及时迁移到合适的存储介质上。MHR-LRU、CLOCK-DWF和D-CLOCK则是根据访问冷热进行数据划分。MHR-LRU只有DRAM到PCM的单向迁移，当PCM页面发生频繁更新时，无法将其迁移到DRAM上进一步减少PCM上的写操作。而CLOCK-DWF和D-CLOCK在两种存储介质之间执行数据迁移时，会将数据换出主存空间，存在命中率下降的问题。本文提出的CLOCKW算法对数据进行写冷热划分，将热写页存储到DRAM上，冷写页存储到PCM上，既能保证算法命中率，也能通过DRAM与PCM之间的页面迁移有效减少对PCM的写操作次数。

3　CLOCKW概述

3.1基本思路

基于PCM混合主存系统的主存管理算法关键在于准确预测热写页，并将其存储到DRAM上，以发挥DRAM写带宽高的优势。此外，应避免将冷写页误分类为热写页，导致DRAM资源浪费和不必要的迁移操作。

已有研究主要借鉴LRU算法，用RW预测页面写热度，但是LRU算法无法有效应对局部性较弱的访问模式，如数据扫描、访问间隔大于缓冲区大小的循环数据访问。LIRS算法提出IRR概念来解决LRU算法的缺陷[17]，该算法定义IRR为页最近两次访问期间被访问的其他页的个数，并用IRR定义页面访问热度，即IRR越小，页面越热。CLOCKW借鉴LIRS思想，引入内在写距离概念，定义如下：

定义1（内在写距离，IWD）页p的IWD指p在倒数第二次写和最近一次写的间隔内被写的其他页的数量。如果页p只被写过一次或从未被写过，则p 的IWD为无穷大。

定义2（写临近信息，RW）页p的RW指的是该页最近一次被写以后，其他被写访问过的页面数。

直观地理解，IWD越小的页面，写热度越高。但是如果一个IWD很小的页面很长时间没有被写，将该页面继续归类为热写页是不合适的。因此，CLOCKW综合RW和IWD对热写页和冷写页进行分类。

假设热写页里p1的RW最大（记为RWmax），即p1是热写页里最近最久没被写过的页。当一个RW比RWmax小但是IWD很大的冷写页 p2被再次写时，p2的IWD被更新，此时将p2转换为热写页，p1转换为冷写页。因为即使p1当前的IWD比 p2的新IWD小，但是p1未来更新的新IWD必然比RWmax大，而p2的新IWD比RWmax小（p2被再次访问前的RW比RWmax小），所以可以认为 p2的写热度比 p1的写热度高。因此CLOCKW只需追踪RW比RWmax小的页的写信息即可有效检测热写页。

CLOCKW的设计思路如下：

（1）CLOCKW设定热写页数目的上限为DRAM可容纳的页数目。当一个写请求命中位于PCM上的页时，如果CLOCKW保留了该页的写历史信息，则认为该页是热写页。因此，CLOCKW将该热写页迁移至DRAM，同时将DRAM一个冷写页迁移至PCM。

（2）为了保证命中率，CLOCKW采用CLOCK的页替换算法，但是当一个页被替换出主存时，该页写信息被继续保留一段时间。当读一个新页触发页面置换时，根据历史信息判定该页是热写页还是冷写页，进而决定该页是存储到DRAM还是PCM，避免后来不必要的页面迁移操作。

（3）当写一个新页触发页面置换，并且置换出的页面在PCM时，如果CLOCKW保留了新页的写历史信息，则按（1）处理。但如果CLOCKW未保留该页写历史信息，尽管该页是冷写页，仍将该页载入DRAM，同时将DRAM里冷写页迁移至PCM。因为将新页载入PCM和写新页会造成两次PCM写，将该页载入DRAM可将这两次PCM写集中于DRAM，而迁移只造成一次PCM写。

3.2基本结构

CLOCKW的结构如图2所示。全局CLOCK链表采用原CLOCK的数据结构和页面替换算法来管理所有主存页面，以保证CLOCKW的命中率和CLOCK的相同。写CLOCK链表记录了DRAM页、PCM页的写信息，以及部分被替换出主存的页历史写信息。DRAM冷写页链表存放写CLOCK链表中未记录写信息的DRAM页，这些DRAM页在相当长一段时间内未被写过。如果所有DRAM页都在写CLOCK链表有对应写信息，则DRAM冷写页链表为空。

Fig.2　Structure of CLOCKW图2　CLOCKW结构图

设DRAM容量为nd页，PCM容量为np页，主存总容量为n页（n=nd+np）。写CLOCK链表根据所记录页的写信息，把页分为热写页和冷写页。CLOCKW的目标是将所有热写页存储到DRAM以减少PCM写，因此设置热写页数目的上限为nd。HANDhot指向RW最大（即RWmax）的热写页，类似于LIRS算法，将最近最久未访问的热页置于LRU栈底，CLOCKW指定HANDhot指向的热写页为写CLOCK链表尾部，而HANDhot逆时针方向所指的第一个页自然成为写CLOCK链表头部。当热写页数目超过上限时，顺时针转动HANDhot，将指向的热写页变为冷写页。HANDcold总是指向顺时针方向离写CLOCK链表尾部（HANDhot）最近的冷写页，即RW最大的冷写页。CLOCKW限定写CLOCK链表节点总数（包括历史页写信息和当前在主存中的页写信息）上限为2n，如果节点总数超过2n，则移动HANDcold将指向的冷写页从写CLOCK链表移除。从写CLOCK链表移除的DRAM页会插入到DRAM冷写页链表头部。

CLOCK算法引入访问位来近似LRU的栈操作，CLOCKW与CLOCK类似。当一个页被写时，如果写CLOCK链表保留了该页写信息，将该页写访问位置1。HANDhot扫过写访问位为1的热写页时，不会将该热写页变为冷写页，而是将写访问位置0，继续寻找下一个热写页。HANDcold扫过写访问位为1的冷写页时，由于该页最近又被写过，HANDcold并不会将该页移除，而是引入冷标志位，将该页冷标志位置1。引入冷标志位概念后，HANDcold应指向顺时针方向离HANDhot最近且冷标志位未被置1的冷写页。

HANDcold扫过热写页时，直接略过该页，但是HANDhot扫过冷写页时，所做工作和HANDcold扫过该页一样，即将写访问位为0的冷写页移除，写访问位为1的页面的冷标志位置1。这是因为HANDhot指向的热写页为写CLOCK链表尾部，该热写页代表RW最大（RWmax）的热写页，而CLOCKW只需追踪RW比RWmax小的页的写信息，当HANDhot定位在新的热写页时，RW比新的热写页大的写信息无需再保留。

DRAMcold总是指向离HANDcold顺时针方向最近的写访问位为0的DRAM冷写页或者访问位为1且冷标志位为1的DRAM冷写页。如果没有这两种类型的DRAM冷写页，则DRAMcold为空。

3.3页请求处理策略

当一个页请求到达时，主存系统会面临页请求命中和未命中两种情形，在介绍这两种情形下的处理方法之前，首先介绍一个辅助算法——DRAM冷写页查找算法。该算法查找DRAM上的冷写页，优先从DRAM冷写页链表查找，接着查看DRAMcold指针是否指向一个DRAM冷写页，若找到存储在DRAM上的冷写页，则直接返回（算法1第1～4行）。如果都没找到，CLOCKW尝试把一个写访问位为1且冷标志位为0的冷写页变热，这可能会导致热写页数目超过上限，从而触发HANDhot顺时针转动把相对较冷的热写页转换为冷写页（算法1第5～20行）。CLOKCW致力于将热写页置于DRAM，因此变冷的热写页很大概率会在DRAM上（变冷的页也有可能不在主存中，因为CLOCKW保留了原CLOCK的页面替换算法，一个热写页可能因其他页的频繁读请求被替换出主存），当变冷的页面不在DRAM上面时，算法返回空指针，否则返回变冷的DRAM页面，如算法1第18～20行所示。若临时指针扫描一圈都未找到写访问位为1且冷标志位为0的DRAM冷写页，可断定所有热写页都是DRAM页，此时转动HANDhot将写热度最低的DRAM热写页变冷，如算法1第21～23行所示。

算法1 DRAM冷写页查找算法

输出：存储在DRAM上的冷写页或空。

1.If（DRAM冷写页链表不为空）then

2.return位于DRAM冷写页链表尾部的页；

3.else if（DRAMcold指针不为空）then

4.return DRAMcold指针指向的页并将DRAMcold指向顺时针方向下一个DRAM冷写页；

5.else//DRAMcold为空

6.启动临时指针p，从HANDcold开始顺时针扫描

7.if（p是热写页或写访问位为0的冷写页）then

8.p指向顺时针方向的下一个页面；

9.else if（p是写访问位和冷标志位都为1的冷写页）then

10.将该页移到写CLOCK链表头部；

11.p的写访问位和冷标志位置为0；

12.else if（p是写访问位为1且冷标志位为0的冷写页）then

13.将该页转为热写页；写访问位置为0；

14.移动该页到写CLOCK链表头部；

15.if（热写页数目未超过上限）then

16.return NULL；

17.else

18.转动HANDhot将一个热写页p转为冷写页；

19.If（p为DRAM页）then返回p；

20.else return NULL；

21.转动HANDhot将一个热写页p转为冷写页；

22.if（p为DRAM页）then returnp；

23.else return NULL；

算法2给出了CLOCKW在页请求命中时的处理策略。只有写一个PCM页并且写CLOCK链表中保留了该页写信息时，才可能发生页面迁移，如第3～7行所示。因为此时该PCM页被认为是热写页，应将该页面与一个DRAM冷写页交换。当一个PCM页被认定为热写页时，算法1将调用DRAM冷写页查找算法尝试寻找一个DRAM冷写页，并将该冷写页与被命中的PCM页进行交换（第5～7行）。否则，若写CLOCK链表中未发现被写访问命中的页写信息，则认为该页为冷写页，无需进行交换操作，但它的写访问信息将被加入到写CLOCK链表中，如第8～12行所示。但若访问请求类型为读操作，则除了置位页面的访问位以外，没有任何其他操作。

算法2页请求命中处理算法

输入：请求页p，访问类型op。

输出：请求页的主存地址。

1.将全局CLOCK链表中页p的访问位置1；

2.If（op为写请求）then

3.if（写CLOCK链表保留了页p写信息）then

4.将写CLOCK链表中页p写访问位置1；

5.if（p在PCM）then

6.if（调用DRAM冷写页查找算法找到一个DRAM冷写页q）then

7.将q迁移至PCM；将页p载入DRAM；

8.else//写CLOCK链表未发现页p写信息

9.将页p的写信息加入到链表头部；

10.设置页p为冷写页；初始化写访问位和冷标志位为0；

11.if（链表保留的写信息达到上限）then

12.转动HANDcold移除部分冷写页信息；

13.返回页p在DRAM或PCM的主存地址；

算法3给出了CLOCKW在页请求未命中时的处理策略。该算法首先根据传统CLOCK页面替换规则从全局CLOCK链表中选取页面换出主存（第1行），当一个缺失页准备从磁盘载入主存时，CLOCKW根据该页的写历史信息和访问类型选择合适的存储介质。若页请求类型为读且被访问页在写CLOCK链表显示为热写页，则尝试为其分配一个DRAM上的存储空间，此时若换出页在PCM上，将触发迁移操作从DRAM迁移一个冷写页到PCM上，如第3～10行所示。但是正如3.1节设计思路所提到的，如果写一个新页触发页面置换，并且置换出的页面在PCM时，CLOCKW总是将DRAM一个冷写页迁移至PCM，同时将新页载入DRAM（第21～25行所示）。此外，还需向写CLOCK链表更新或添加被访问页的写信息，以便将来对其进行写冷热判断，具体细节如第14～20行所示。最后算法更新全局CLOCK链表信息，用于执行页面替换策略（第26行）。

算法3页请求未命中处理算法

输入：请求页p，访问类型op。

输出：请求页的主存地址。

1.根据全局CLOCK链表的访问信息，利用CLOCK的页面替换算法，选择一个页q替换出主存；

2.If（op是读操作）then

3.if（写CLOCK链表保留了页p的写信息，并显示p是热写页）then

4.if（页q在DRAM）then

5.将页p载入DRAM；

6.else//页q在PCM

7.if（调用DRAM冷写页查找算法找到一个DRAM冷写页c）then

8.将页c迁移至q所在位置；将页p载入DRAM

9.else//尝试寻找DRAM冷写页失败

10.将页p载入到页q的位置；

11.else//页p是冷写页

12.将页p载入到页q的位置；

13.else//op是写操作

14.if（写CLOCK链表保留页p写信息）then

15.将写CLOCK链表中页p写访问位置1；

16.else//写CLOCK链表未发现页p写信息

17.将页p的写信息加入到链表头部；

18.设置页p为冷写页；初始化写访问位和冷标志位为0

19.if（链表保留的写信息达到上限）then

20.转动HANDcold移除部分冷写页信息;

21.if（页q在DRAM）then

22.将页p载入DRAM；

23.else//页q在PCM

24.调用DRAM冷写页查找算法直到找到一个DRAM冷写页c为止；

25.将页c迁移至q所在位置；将页p载入DRAM；

26.将页p加入全局CLOCK链表；设置访问位为1；

27.返回页p在DRAM或PCM的主存地址；

总体来说，相比于CLOCK算法，CLOCKW中每个页需要4 bit表示页写信息和访问信息，原CLOCK算法只需要1 bit表示其访问信息，空间复杂度增长并不是很大，若原CLOCK算法的空间复杂度为S(n)，则CLOCKW算法的空间复杂度为S(4n)。CLOCKW算法最好情况下，每次读写操作都不会触发迁移操作，只有对全局CLOCK链表的扫描执行页面替换操作，这种情形下CLOCKW算法退化成CLOCK算法，其算法时间复杂度与原CLOCK算法相同；相反，若每次写请求均会触发迁移操作，迁移操作将会对写CLOCK链表进行扫描，而写CLOCK链表的长度是全局CLOCK链表的两倍，因此CLOCKW算法最坏情形下的时间复杂度是原CLOCK算法的3倍。最后，当页面被写命中时，只需更新对应页面的位信息，而位信息置位可由底层硬件实现，只有可能触发页面迁移时才会有部分链表操作，这些操作将大大减少PCM上的写操作，但PCM写延迟是DRAM的几倍，因此总体上来说，并不会影响系统的整体性能。

4　实验与分析

本文实验与传统CLOCK算法和基于CLOCK算法设计的CLOCK-DWF[6]、D-CLOCK[7]进行对比。

4.1实验设置

由于PCM目前还没有商业化产品，本文采用仿真实验来测试算法的有效性，实验中仿真实现了DRAM与PCM的同级主存架构，采用统一编址模式，DRAM占据低端地址空间，而PCM使用高端地址空间，即算法可以通过页面地址判断出该页是属于DRAM还是PCM；在为新页分配空间时，指定需要存储在DRAM上还是PCM上，系统根据分配的页面地址空间判断是否符合分配需求，若不符合则可能触发迁移操作。实验中，主存页帧大小为4 KB，主存空间大小设定从1 000个页帧到3 000个页帧。PCM的存储密度被认为可以达到DRAM的4倍，因此DRAM与PCM总是维持1∶4的空间大小比例。

实验中使用了5种类型的测试数据集，如表1所示。其中一个是OLTP数据集，即由Gerhard Weikum提供的真实的银行系统交易处理数据集，该数据集对CODASYL数据库进行了470 677次页面读和136 713次页面写，曾被用于文献[20-21]的实验测试。另外4个是人工生成的Zipf访问序列[22]。对于有N个不同页面的Zipf数据集，页面i被访问的概率满足式（1）：

Table 1　Parameters of Zipf and OLTP traces表1 Zipf与OLTP数据集参数

4.2合成数据集实验评估

4.2.1页面缺失

图3显示了系统运行Zipf合成数据集时，CLOCKW与其他3个对比算法的页面缺失数随着主存空间大小变化的实验结果。

从图3中可以看出，各个算法的页面缺失随着主存空间增加而减少，CLOCKW页面缺失数与传统CLOCK算法相同。实验数据显示，D-CLOCK的页面缺失数虽然在多数情况下与CLOCK相近，但在某些情形下会略高于CLOCK，这是由于D-CLOCK为防止从二级存储器读入的页被频繁写入PCM，会从DRAM上强制替换出一个页面用于存储新读入的页面，这种做法可能会将一个热度较高的页面替换出主存。而CLOCK-DWF虽然在Zipf1955和Zipf4655数据集下页缺失数与其他3个算法相似，但在数据访问比较集中的情况下（如Zipf4682和Zipf1982），页面缺失数较其他3种算法多。这是因为CLOCK-DWF在从DRAM迁移页面到PCM且PCM没有空闲空间时，会调用CLOCK算法将PCM页替换出主存，从而增加页面缺失。

Fig.3　Page fault counts on Zipf traces图3　Zipf系列数据集页面缺失数

4.2.2PCM写次数

在基于PCM的混合主存系统中的主存管理算法，除了要保证命中率以外，减少PCM上的写次数也是一个重要的设计目标。图4描述了随着主存空间变化，4种算法对PCM主存的写操作数，包括从磁盘写入PCM和从DRAM迁移到PCM引起的写，以及数据集对PCM的写请求。

从图4中可以明显看出，虽然数据集不同，但随着主存空间容量变大，DRAM空间也相应增加，能容纳更多的写页面，4种算法对PCM的写次数有着相似的变化趋势——呈递减趋势。图4同时也显示，CLOCKW对PCM的写操作次数仅是CLOCK算法的55%～66%，而相比于CLOCKW，D-CLOCK和CLOCKDWF会引起更多PCM写。

这是因为在D-CLOCK和CLOCK-DWF中，每一次PCM上的写命中都会触发一次页面迁移，这会引起大量的页面迁移操作，而CLOCKW是根据对命中的PCM页面的冷热判断来决定是否需要迁移到DRAM，从而减少了某些不必要的页面迁移。

4.3OLTP数据集实验评估

本节介绍OLTP数据集在4种算法上的运行结果。图5（a）和图5（b）分别描述了实验在PCM上的写次数和页面缺失数对比。

从图5（a）可以看出，CLOCKW的PCM写次数高于D-CLOCK。实验显示，D-CLOCK的PCM写次数仅是CLOCK的78%～81%，而CLOCKW比D-CLOCK大约多10%的PCM写。这是由于OLTP数据集具有较多的不同访问页面，缺失率高，同时该数据集含有大量的读请求，CLOCKW不会将读未命中的页面强制放入DRAM上存储，但D-CLOCK会以降低命中率为代价，强制替换出DRAM的页，使得从二级存储器新读入的页被存储到DRAM上，从而限制新进页写入到PCM上的次数，以减少PCM的写次数。当目标存储器上没有空闲的存储空间时，D-CLOCK和CLOCKDWF均会采取强制页替换策略，因此D-CLOCK和CLOCK-DWF在运行OLTP数据集时，页缺失数明显高于CLOCK和CLOCKW算法，如图5（b）所示。由于主存与二级存储器之间的访问延迟相差多个数量级，以大量页面缺失来换取PCM写次数的减少将严重影响系统数据访问的性能。

Fig.4　PCM write counts on Zipf traces图4　Zipf系列数据集PCM写次数

Fig.5　Page fault counts and PCM write counts on OLTP trace图5　OLTP数据集页面缺失数和PCM写次数

5　结论

本文提出了一种基于CLOCK的混合主存管理算法——写感知CLOCK算法CLOCKW。CLOCKW采用传统的CLOCK算法替换策略，以保证与CLOCK相同的命中率。同时，CLOCKW引入了“内在写距离”概念，并结合页面写临近信息来定义和预测页面写热度，从而能及时将写热度高的页面放置于DRAM上，减少对PCM的写。当页面被替换出主存时，CLOCKW会保留页面历史写信息用于未来该页重新被载入主存时衡量页面写热度，从而将该页放置在合适的存储介质上，减少不必要的页面迁移。实验结果表明，本文算法在不同数据集下都能保证与CLOCK相同的命中率，同时又能较为准确地预测页面的写冷热，通过DRAM与PCM之间的页面迁移，有效减少PCM的写次数。

References:

[1]Apache Spark.Spark overview and programming guide [EB/OL].[2016-02-19].http://spark.apache.org/.

[2]Wu Zhangling,Jin Peiquan,Yue Lihua,et al.A survey on PCM-based big data storage and management[J].Journal of Computer Research and Development,2015,52(2):343-361.

[3]Seong N H,Woo D H,Lee H S.Security refresh:prevent malicious wear-out and increase durability for phase-change memory with dynamically randomized address mapping[C]// Proceedings of the 37th International Symposium on Computer Architecture,Saint-Malo,France,Jun 19-23,2010. New York,USA:ACM,2010:383-394.

[4]Seok H,Park Y,Park K H.Migration based page caching algorithm for a hybrid main memory of DRAM and PRAM[C]// Proceedings of the 26th Annual ACM Symposium on Applied Computing,Taichung,China,Mar.21-24,2011.New York,USA:ACM,2011:595-599.

[5]Shin D J,Park S K,Kim S M,et al.Adaptive page grouping for energy efficiency in hybrid PRAM-DRAM main memory[C]//Proceedings of the 2012 ACM Research in Applied Computation Symposium,San Antonio,USA,Oct 23-26, 2012.New York,USA:ACM,2012:395-402.

[6]Qureshi M K,Srinivasan V,Rivers J A.Scalable high performance main memory system using phase-change memory technology[C]//Proceedings of the 36th Annual International Symposium on Computer Architecture,Austin,USA,Jun 20-24,2009.New York,USA:ACM,2009:24-33.

[7]Park H,Yoo S,Lee S.Power management of hybrid dram/ pram-based main memory[C]//Proceedings of the 48th ACM/ EDAC/IEEE Design Automation Conference,San Diego, USA,Jun 5-9,2011.New York,USA:ACM,2011:59-64.

[8]Condit J,Nightingale E B,Frost C,et al.Better I/O through byte-addressable,persistent memory[C]//Proceedings of the 22nd ACM SIGOPS Symposium on Operating Systems Principles,Big Sky Resort,USA,Oct 11-14,2009.New York,USA:ACM,2009:133-146.

[9]Chen Shimin,Gibbons P B,Nath S.Rethinking database algorithms for phase change memory[C]//Proceedings of the 5th Biennial Conference on Innovative Data Systems Research,Asilomar,USA,Jan 9-12,2011:21-31.

[10]Seok H,Park Y,Park K W,et al.Efficient page caching algorithm with prediction and migration for a hybrid main memory[J].ACM SIGAPP Applied Computing Review, 2011,11(4):38-48.

[11]Lee S,Bahn H,Noh S H.CLOCK-DWF:a write historyaware page replacement algorithm for hybrid PCM and DRAM memory architectures[J].IEEE Transactions on Computers,2014,63(9):2187-2200.

[12]Chen Kaimeng,Jin Peiquan,Yue Lihua.Efficient buffer management for PCM-enhanced hybrid memory architecture[C]//LNCS 9313:Proceedings of the 17th Web Technologies and Applications,Guangzhou,China,Sep 18-20,2015. Berlin,Heidelberg:Springer,2015:29-40.

[13]Chen Kaimeng,Jin Peiquan,Yue Lihua.A novel page replacement algorithm for the hybrid memory architecture involving PCM and DRAM[C]//LNCS 8707:Proceedings of the 11th IFIP International Conference on Network and Parallel Computing,Ilan,China,Sep 18-20,2014.Berlin, Heidelberg:Springer,2014:108-119.

[14]Wu Zhangling,Jin Peiquan,Yang Chengcheng,et al.APPLRU:a new page replacement method for PCM/DRAM-based hybrid memory systems[C]//LNCS 8707:Proceedings of the 11th IFIP International Conference on Network and Parallel Computing,Ilan,China,Sep 18-20,2014.Berlin, Heidelberg:Springer,2014:84-95.

[15]Friedman M B.Windows NT page replacement policies[C]// Proceedings of the 25th International Computer Measurement Group Conference,Reno,USA,Dec 5-10,1999:234-244.

[16]Jiang Song,Chen Feng,Zhang Xiaodong.CLOCK-Pro:an effective improvement of the CLOCK replacement[C]// Proceedings of the Annual Conference on USENIX Annual Technical Conference,Anaheim,USA,Apr 10-15,2005.Berkeley,USA:USENIXAssociation,2005:323-336.

[17]Jiang Song,Zhang Xiaodong.LIRS:an efficient low inter-reference recency set replacement policy to improve buffer cache performance[J].ACM SIGMETRICS Performance Evaluation Review,2002,30(1):31-42.

[18]Cai Daolin,Chen Houpeng,Wang Qian,et al.An 8 Mb phase change random access memory based on 0.13 μm technology[J].Research&Progress of Solid State Electronics,2011,31(6):601-605.

[19]Fan Jie,Jiang Song,Shu Jiwu,et al.Aegis:partitioning data block for efficient recovery of stuck-at-faults in phase change memory[C]//Proceedings of the 46th Annual IEEE/ ACM International Symposium on Microarchitecture,Davis, USA,Dec 7-11,2013.NewYork,USA:ACM,2013:433-444.

[20]Jin Peiquan,Ou Yi,Härder T,et al.AD-LRU:an efficient buffer replacement algorithm for flash-based databases[J]. Data&Knowledge Engineering,2012,72:83-102.

[21]OƳneil E,OƳneil P,Weikum G.The LRU-K page replacement algorithm for database disk buffering[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data,Washington,USA,May 25-28,1993. New York,USA:ACM,1993:297-306.

[22]Knuth D.Sorting and searching[M]//TheArt of Computer Programming:Volume 3.Massachusetts:Addison-Wesley,1973.

附中文参考文献：

[2]吴章玲,金培权,岳丽华,等.基于PCM的大数据存储与管理研究综述[J].计算机研究与发展,2015,52(2):343-361.

[18]蔡道林,陈后鹏,王倩,等.基于0.13 μm工艺的8 Mb相变存储器[J].固体电子学研究与进展,2011,31(6):601-605.

HE Aihua was born in 1975.She received the M.S.degree from Anhui University in 2008.Now she is a teacher at Bengbu University,and visiting scholar at University of Science and Technology of China.Her research interests include hybrid memory management and flash-based databases.

何爱华（1975—），女，2008年于安徽大学获得硕士学位，现为蚌埠学院教师，中国科学技术大学访问学者，主要研究领域为混合存储管理，闪存数据库。

YUE Lihua was born in 1952.She received the M.S.degree from University of Science and Technology of China in 1991.Now she is a professor and Ph.D.supervisor at University of Science and Technology of China.Her research interests include database system and application,information integration and real time database.

岳丽华（1952—），女，1991年于中国科学技术大学获得硕士学位，现为中国科学技术大学教授、博士生导师，主要研究领域为数据库系统及运用，信息集成，实时数据库。

WU Zhangling was born in 1988.She is a Ph.D.candidate at University of Science and Technology of China.Her research interests include hybrid memory management,flash-based databases and new database architecture.

吴章玲（1988—），女，中国科学技术大学计算机科学与技术学院博士研究生，主要研究领域为混合存储管理,闪存数据库，新型数据库架构。

GUO Youqiang was born in 1966.He received the M.S.degree from Hefei University of Technology in 2006.Now he is a professor and M.S.supervisor at Bengbu University.His research interests include data mining,information integration,algorithm design and optimization.

郭有强（1966—），男，2006年于合肥工业大学获得硕士学位，现为蚌埠学院教授、硕士生导师，主要研究领域为数据挖掘，信息集成，算法设计及优化。

*The National Natural Science Foundation of China under Grant No.61472376(国家自然科学基金);the Key Projects of Domestic and Foreign Research and Training of Outstanding Young and Middle Aged Backbone Talents in Universities under Grant No. gxfxZD2016269(高校优秀中青年骨干人才国内外访学研修重点项目).

Received 2016-02,Accepted 2016-04.

CNKI网络优先出版:2016-04-21,http://www.cnki.net/kcms/detail/11.5602.TP.20160421.1451.002.html

+Corresponding author:E-mail:flyhah@163.com

文献标志码：A

中图分类号：TP316.1

doi:10.3778/j.issn.1673-9418.1603007

Write-Aware Memory Management in PCM-Based Hybrid Memory Systemsƽ

HEAihua1,2+,YUE Lihua2,WU Zhangling2,GUO Youqiang1
1.Department of Computer Science and Technology,Bengbu University,Bengbu,Anhui 233030,China
2.School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027,China

Abstract:Phase change memory(PCM)has been increasingly viewed as an attractive technology to incorporate into the memory hierarchy since the scalability of DRAM(dynamic random access memory)is approaching its limit.Although PCM has higher density and lower idle power consumption than DRAM while exhibiting byte-addressability and read latencies in the nanosecond range,it has poor write performance and limited endurance.Therefore,researchers have proposed hybrid memory systems involving both PCM and DRAM.This paper presents CLOCKW(CLOCK with a write-aware strategy),a novel hybrid memory management scheme that is designed to not only minimize writes to PCM,but also maintain a high hit ratio.The purpose of CLOCKW is trying to make write-intensive pages resident in DRAM.Particularly,differing from previous studies,which use RW(recency of writes)to estimate future access patterns,this paper introduces the concept of IWD(inter-write-distance),and combines it with RW to estimate hotness of future writes.In addition,by additionally keeping a record of a limited number of replaced pages’write references and placing the newly reached page in an appropriate storage medium when page fault occurs,unnecessary migrationsbetween DRAM and PCM can be avoided.More importantly,CLOCKW is based on the CLOCK scheme,and its running cost is affordable for virtual memory management.The evaluation shows that CLOCKW can efficiently reduce PCM writes without degrading the hit ratio.

Key words:phase change memory;hybrid memory;write-aware;buffer management