基于BKDRHash的混合内存损耗均衡算法研究

吴 炀，付印金，陈卫卫，仇小锋

(解放军理工大学 指挥信息系统学院，江苏 南京 210007)



基于BKDRHash的混合内存损耗均衡算法研究

吴 炀，付印金，陈卫卫，仇小锋

(解放军理工大学 指挥信息系统学院，江苏 南京 210007)

相变存储器(PCM)是一种新型的非易失性存储器(NVM)，与传统内存DRAM互有优势。基于DRAM和PCM的混合内存使得同时发挥DRAM与PCM各自的优势成为可能。然而，由于PCM写操作寿命有限，在设计混合内存的管理策略时，不仅要对混合内存体系结构进行设计，还需要设计一种损耗均衡算法对PCM写操作进行负载均衡优化。文中设计了一种损耗均衡算法，将写操作逻辑地址作为输入，使用BKDRHash函数对地址进行映射，实现PCM的损耗均衡。实验结果表明，文中提出的损耗均衡算法能够以很少的时延与功耗损失大幅提升PCM的使用寿命。

PCM；DRAM；损耗均衡；BKDRHash函数

0 引言

近年来，随着硬件技术和多核技术的发展，现有的计算机体系结构受到存储容量、系统功耗与计算速度的挑战，特别是内存的性能已经远远满足不了大数据催生的计算需求。新型非易失性存储器(NVM)的出现与发展为解决此问题提供了契机。特别是相变存储器(PCM)，具有非易失、低功耗和大容量的优势，被认为是最有可能取代DRAM的非易失型存储器。但PCM仍然存在一些缺点：写能耗约为DRAM的4倍、写操作寿命非常有限等，故PCM还不能完全取代DRAM，需要一种混合内存来同时发挥两者的优势。图1为DRAM与PCM的性能参数对比[1]，其中，左边柱条为DRAM性能，右边柱条为PCM性能。

图1 DRAM与PCM性能对比

从图1中可以看出，PCM在写操作上存在短板，需要用DRAM来弥补此缺点，而且每个单元写寿命仅108～1010次，非常有限，所以采用混合内存的方式来同时发挥DRAM与PCM的优势。在设计混合内存时，研发人员提出将写操作地址进行重定位，能够有效避免同一存储单元频繁写操作。本文提出一种基于BKDRHash函数的损耗均衡算法，利用Hash函数对地址进行重定位，并将热数据迁移至DRAM。

1 相关工作

研究者在设计混合内存系统的过程中，提出了一系列混合内存体系架构，大体分为两类：横向内存架构和纵向内存架构。横向内存架构中DRAM与PCM统一编址，纵向架构中，DRAM作为PCM的缓存。在对两种架构设计时，需要在PCM控制器中设计损耗均衡策略，使PCM的写操作均匀分布，如图2所示。

图2 混合内存架构图

图2中，PCM的写操作经损耗均衡算法处理再寻址执行，而DRAM写操作经系统寻址后执行。研究者们提出了一些损耗均衡算法，大体可以分为以下两类：

(1)利用地址映射实现。比如李骁等人[2]提出通过维持一个队列来保存逻辑地址到物理地址的映射；文献[3-4]都是利用地址映射，当满足一定条件时，如某个页面写次数过多，那么系统以一定的方式改变这个映射，本来写到原有页面的数据就会写到另外页面；佐治亚理工学院的SEONG N H等人[5]提出Security Refresh技术，每一轮刷新都改变映射；文献[6]提出Start-Gap技术，在逻辑地址与物理地址之间进行代数映射。这些方法通过改变映射进行地址重定位，虽然一定程度上能够增加系统寿命，但是功耗和延迟都比较高，计算复杂。

(2)利用特殊数据结构或者硬件实现。文献[7]提出了一种叫做Row Shifting的细粒度的损耗均衡和一种叫做Segment Swapping的粗粒度方法，需要专用硬件来实现；文献[8]提出基于Bloom filter数据结构的损耗均衡算法，能够有效提高PCM寿命；文献[9]提出Curling-PCM算法，挖掘特定应用的读写特征。这些方法容易实现，能够在特定应用上取得较好效果，但是功耗与时延需要进一步减少。

本文提出一种基于BKDRHash的损耗均衡算法，能够在现有硬件条件下，以较小的功耗和延迟代价实现PCM的损耗均衡，提高其寿命。

2 基于Hash的损耗均衡算法

由于PCM的写操作寿命有限，每个单元的寿命都是108～1010次，当其中某一个PCM单元达到寿命后，整个PCM芯片都会失去作用，从而影响整个内存系统的使用。所以，在设计混合内存系统时，不仅要减少PCM的写操作，而且需要使得PCM上面的写操作分布均匀，适当地设计从逻辑地址到物理地址的映射函数。映射函数可以利用Hash函数的冲突概率小的特性实现，对同一数据块多次更新还需要进一步设计策略。

3 基于BKDRHash函数的损耗均衡算法

本文的损耗均衡算法在写操作之前执行，在命令中的逻辑地址映射为物理地址时，使得PCM存储空间损耗均衡。由于DRAM写性能较好，可以在DRAM内存空间中保存各个PCM存储空间的写次数，并且可以经常更新。为了充分使PCM单元上的写操作均匀分布，对PCM上的写操作和空闲状态进行如下设计。

(1)写请求

当需要在PCM上执行写请求时，首先从命令等待队列中取出命令，从命令中取出数据的逻辑地址，然后对地址进行BKDRHash函数处理，得到数据的物理地址。定义写平均次数为总写入次数与执行过写操作的单元数之商。为了使写操作分布更加均匀，生成随机系数p，即写入的概率。若此物理地址空闲，并且count小于随机生成的概率p与写平均次数avg_count的乘积(即以一定的概率写入)，则将数据写入此物理地址中，删除等待队列中的命令。若物理地址不空闲或count不小于p与写平均次数avg_count的乘积，则跳到下一存储块，进行上述判断，直到找到符合条件的存储块为止，进行写入。具体算法过程如下：

输入：写操作命令；

输出：true/false；

算法过程：

addr1 = getaddr(wait_list);

//从等待队列上取出逻辑地址

addr =BKDRHash(addr1);

//利用BKDRHash函数计算逻

辑地址为addr的物理地址并返回

p = Random();

//生成随机系数

count = getcount(addr);

//获取写操作次数count

max=get();

//获取循环次数，即地址阈值

while(1){

if(addr.empty() && (count

{//满足条件，存储块为空

count++;

//写次数加1

write();

//执行PCM写操作

delete1();

//删除等待队列上的命令

break;

}

else

if(addr==max) return false；

addr++;

//跳到下一存储块

}

return true;

(2)空闲状态

在空闲状态时，即此时内存的负载低时，某些PCM单元仍然存在写操作频繁的问题，这是由于某块数据需要经常更新引起的。上述写操作算法无法解决此问题，需要设计一种方法解决此问题。

由于DRAM写操作性能比PCM好，因此在本文中，提出一种主动迁移热数据策略，将上述更新频繁的数据迁移到DRAM中。同样的，为了使得分布更加均匀，生成一个随机系数q(以一定的概率迁移数据)，维持一个离线迁移队列。在每一时钟周期时，处理离线迁移队列上对应的数据。

首先，在PCM上执行一个写操作之后，检查写操作次数count是否大于随机系数q与平均写次数avg_count的乘积，若不等式成立，则将此数据挂入离线迁移队列上，若不成立，则不需要迁移。挂入离线迁移队列的算法如下：

输入：写操作命令；

输出：true/false；

算法过程：

q = Random();

if(count>q*avg_count)

{

//写操作次数大于q与平均写次数的乘积

hang(data);

//将数据挂入离线迁移队列

return true;

}

return false;

当数据挂入离线迁移队列时，数据仍然存储于PCM，只有在每一时钟周期系统空闲时，迁移队列上的数据至DRAM之后，才能删除PCM上的数据。

其次，在每一时钟周期内存系统空闲时，取出离线迁移队列上的数据，将数据写入相应的DRAM地址中，在计算DRAM物理地址时，同样采用BKDRHash函数计算，若DRAM单元空闲，则将数据迁移此单元中，并删除离线迁移队列上的数据。具体的数据迁移算法如下：

输入：离线迁移队列；

输出：true/false；

算法过程：

data = getdata();

//获取需要迁移的数据

addr2 = getaddr();

//获取迁移的DRAM地址

addr3 = BKDRHash(addr2);

//利用BKDRHash函数计算

逻辑地址为addr2的物理地址并返回

if(addr3.empty())

//存储块空闲

{

write(data);

//将数据写入DRAM

delete2(data);

//删除离线迁移队列上的数据

return true；

}

return false；

在此过程中，需要在DRAM单元空闲时执行，避免数据发生冲突。在执行迁移过程中，若需要执行读写操作，立即中断迁移。

4 理论分析

4.1 写操作分析

对于p、q来说，生成的随机值直接影响后续的操作，当p越接近1时，执行写操作的概率越大，所以能够更快找到存储块的地址，将数据写入。当p越小，接近0时，能够更好地选出写次数较小的存储块进行存储。当q越接近1时，迁移的概率越大，产生越多的时延与能耗，但是能够有效减少写操作次数。当q越接近0时，更少的数据进行迁移，但是写操作次数更多。

4.2 开销分析

在整个策略的过程中，存在两种开销，一种是额外存储的数据结构的开销，一种是计算产生的时延开销。

本文需要存储的数据结构包括存储PCM每一存储单元对应的写操作次数的数据结构、等待队列、离线迁移队列等，这些数据结构都存储在DRAM中，由操作系统统一管理。计算产生的时延开销包括BKDRHash函数计算产生的开销、随机数的生成等，这些开销对内存的计算速度影响不大。

5 结果验证

5.1 实验环境

实验采用Linux环境，Ubuntu版本为Ubuntu12.04 64位，虚拟机硬件设置为：内存1 GB、硬盘(SCSI)20 GB、处理器数量为1。使用DRAMsim2模拟器进行仿真模拟。

实验过程中，通过改变system.ini等配置文件中的参数进行混合内存系统模拟，将PCM+DRAM混合内存系统加入该策略与否进行对比实验。

文中使用5种系统配置，配置参数如表1所示。

表1 5种系统配置参数

5.2 评估指标

实验中评估指标有三项，首先是为了评估系统寿命，所有PCM存储块的最大写操作次数与最小写操作次数之差是损耗均衡效果的很好的一项参考标准；其次是能耗，在产生额外的数据结构之后，相比于原系统来说产生额外的能耗；最后是延迟，反映了由算法计算产生的额外延迟。后两项反映了本文损耗均衡算法所产生的代价。

5.3 实验结果与分析

5.3.1 寿命测试结果

本文以寿命为测试指标，使用PCM存储单元的写操作最大次数与最小次数之差量化。在系统1配置下进行实验，表2给出了实验结果 (循环次数为读取命令的条数)。

表2 寿命测试结果

由表2可以看出，当循环次数增加时，写操作最大次数与最小次数之差增加直至趋于稳定，并且，使用本文损耗均衡算法能够大幅减少写操作最大次数与最小次数之差，即使得写操作分布更加均匀，大大延长了系统寿命。

5.3.2 能耗测试结果

图3展示了在系统1配置下功耗测试结果。图4阐述了不同系统配置的功耗测试结果。

图3 同一系统功耗测试结果

图4 不同系统功耗测试结果

从图3可以看出，随着循环次数的增加，功耗减小，这是因为系统消耗的能量增加，但是作为除数的循环次数也增加，功率反而减小。从图4可以看出，不同系统配置产生的功耗不同。

综合图3、4可以看出，在使用本文的损耗均衡策略之后，功耗仅仅有少量的增加，增加的平均幅度仅为1%～3%，这说明本文损耗均衡策略功耗的代价较小。

5.3.3 延迟测试结果

图5展示了在系统1配置下延迟测试结果。图6阐述了不同系统配置的延迟测试结果。

图5 同一系统延迟测试结果

图6 不同系统延迟测试结果

从图5可以看出，随着循环次数的增加，系统延迟在一定范围内波动之后，持续增加。从图6可以看出，不同系统产生的延迟不同。

综合图5、6可以看出，使用本文的损耗均衡策略之后，延迟有少量的增加，增加的平均幅度为10%～15%，虽然增加的幅度比功耗大，但是实验中是以μs为单位，两者的平均差距在0.1～0.9 s之间，不影响系统的运行，是可以接受的。故本文的损耗均衡算法产生的延迟代价是可以接受的。

6 结束语

由于NVM写操作寿命有限，每一单元仅为108～1010次，需要均衡NVM存储单元上的写操作，本文提出一种基于BKDRHash函数的损耗均衡算法，利用BKDRHash函数冲突概率小的特性，同时引入了随机系数，使得写操作分布更加均匀，而且，将更新频繁的数据向DRAM迁移，能够大幅提高PCM的寿命。本文损耗均衡算法针对两种情况进行设计，首先是在执行写操作时，需要将逻辑地址映射为物理地址，其次，对于频繁更新的数据进行热数据迁移，将PCM上的数据迁移至DRAM中。实验证明，提出的损耗均衡算法能够以很少的时延与功耗大幅提高PCM的使用寿命，进而提高整个内存系统的寿命与稳定性。

[1] 冒伟，刘景宁，童薇，等.基于相变存储器的存储技术研究综述[J]. 计算机学报, 2015, 38(5): 944-960.

[2] 李骁.基于混合架构的高效页面替换算法的分析[D].济南：山东大学，2015.

[3] Shao Zili, Chang Naehyuck, Dutt N. PTL: PCM translation layer[C]. In VLSI(ISVLSI), 2012 IEEE Computer Society Annual Symposium on, 2012: 380-385.

[4] Liu Duo, Wang Tianzheng , Wang Yi, et al, Curling-PCM: application-specific wear leveling for phase change memory based embedded systems[C]. In ASP-DAC, 2013: 279-284.

[5] 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 Annual International Symposium on Computer Architecture. New York, USA: ACM, 2010: 383-394.

[6] QURESHI M K, KARIDIS J, FRANCESCHINI M, et al. Enhancing lifetime and security of PCM-based main memory with start-gap wear leveling[C].Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture. ACM, 2009: 14-23.

[7] ZHOU P, ZHAO B, YANG J, et al. A durable and energy efficient main memory using phase change memory technology[J].Acm Sigarch Computer Architecture News, 2009,37(3):14-23.

[8] YUN J, LEE S, YOO S. Bloom filter-based dynamic wear leveling for phase-change RAM[C].Proceedings of the Conference on Design, Automation and Test in Europe. EDA Consortium, 2012: 1513-1518.

[9] HU J, ZHUGE Q, XUE C J, et al. Software enabled wear-leveling for hybrid PCM main memory on embedded systems[C].Design, Automation & Test in Europe Conference & Exhibition(DATE), 2013: 599-602.

The research of wear-leveling algorithm based on BKDRHash in hybrid memory

Wu Yang, Fu Yinjin, Chen Weiwei, Qiu Xiaofeng

(College of Command Information System, PLA University of Science and Technology, Nanjing 210007, China)

As an emerging Non-Volatile Memory (NVM), Phase Change Memory (PCM) can compensate with traditional DRAM memory for its own advantages. Hybrid memory based on DRAM and PCM makes it possible to play the respective advantages of DRAM and PCM simultaneously. However, because the life of the writing operation on PCM media is limited, researchers not only design a management strategy of hybrid memory, but also need to give a wear-leveling algorithm for writing operation on PCM. In this paper, a wear-leveling algorithm is designed. In order to achieve a more balance distribution, in this algorithm, the writing operation logical address is used as input, and the BKDRHash function is used for address mapping. Experimental results show that the proposed wear-leveling algorithm can greatly prolong the service life of PCM with little time delay and energy consumption.

PCM; DRAM; wear-leveling algorithm; BKDRHash function

TP391.4

A

10.19358/j.issn.1674- 7720.2017.11.005

吴炀，付印金，陈卫卫，等.基于BKDRHash的混合内存损耗均衡算法研究[J].微型机与应用，2017,36(11)：15-18，22.

2017-01-13)

吴炀(1992-)，男，硕士研究生，主要研究方向：云存储、混合内存。

付印金(1984-)，男，博士，讲师，主要研究方向：大数据管理、网络存储和云计算。

陈卫卫(1967-)，女，硕士，教授，硕士生导师，主要研究方向：云计算和大数据管理。