基于BKDRHash的混合內存損耗均衡算法研究

吳 煬，付印金，陳衛衛，仇小鋒

(解放軍理工大學 指揮信息系統學院，江蘇 南京 210007)

?

基于BKDRHash的混合內存損耗均衡算法研究

吳 煬，付印金，陳衛衛，仇小鋒

(解放軍理工大學 指揮信息系統學院，江蘇 南京 210007)

相變存儲器(PCM)是一種新型的非易失性存儲器(NVM)，與傳統內存DRAM互有優勢?；贒RAM和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-)，女，碩士，教授，碩士生導師，主要研究方向：云計算和大數據管理。