吳 煬，付印金，陳衛(wèi)衛(wèi)，仇小鋒

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

?

基于BKDRHash的混合內(nèi)存損耗均衡算法研究

吳 煬，付印金，陳衛(wèi)衛(wèi)，仇小鋒

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

相變存儲(chǔ)器(PCM)是一種新型的非易失性存儲(chǔ)器(NVM)，與傳統(tǒng)內(nèi)存DRAM互有優(yōu)勢(shì)。基于DRAM和PCM的混合內(nèi)存使得同時(shí)發(fā)揮DRAM與PCM各自的優(yōu)勢(shì)成為可能。然而，由于PCM寫操作壽命有限，在設(shè)計(jì)混合內(nèi)存的管理策略時(shí)，不僅要對(duì)混合內(nèi)存體系結(jié)構(gòu)進(jìn)行設(shè)計(jì)，還需要設(shè)計(jì)一種損耗均衡算法對(duì)PCM寫操作進(jìn)行負(fù)載均衡優(yōu)化。文中設(shè)計(jì)了一種損耗均衡算法，將寫操作邏輯地址作為輸入，使用BKDRHash函數(shù)對(duì)地址進(jìn)行映射，實(shí)現(xiàn)PCM的損耗均衡。實(shí)驗(yàn)結(jié)果表明，文中提出的損耗均衡算法能夠以很少的時(shí)延與功耗損失大幅提升PCM的使用壽命。

PCM；DRAM；損耗均衡；BKDRHash函數(shù)

0 引言

近年來，隨著硬件技術(shù)和多核技術(shù)的發(fā)展，現(xiàn)有的計(jì)算機(jī)體系結(jié)構(gòu)受到存儲(chǔ)容量、系統(tǒng)功耗與計(jì)算速度的挑戰(zhàn)，特別是內(nèi)存的性能已經(jīng)遠(yuǎn)遠(yuǎn)滿足不了大數(shù)據(jù)催生的計(jì)算需求。新型非易失性存儲(chǔ)器(NVM)的出現(xiàn)與發(fā)展為解決此問題提供了契機(jī)。特別是相變存儲(chǔ)器(PCM)，具有非易失、低功耗和大容量的優(yōu)勢(shì)，被認(rèn)為是最有可能取代DRAM的非易失型存儲(chǔ)器。但PCM仍然存在一些缺點(diǎn)：寫能耗約為DRAM的4倍、寫操作壽命非常有限等，故PCM還不能完全取代DRAM，需要一種混合內(nèi)存來同時(shí)發(fā)揮兩者的優(yōu)勢(shì)。圖1為DRAM與PCM的性能參數(shù)對(duì)比[1]，其中，左邊柱條為DRAM性能，右邊柱條為PCM性能。

圖1 DRAM與PCM性能對(duì)比

從圖1中可以看出，PCM在寫操作上存在短板，需要用DRAM來彌補(bǔ)此缺點(diǎn)，而且每個(gè)單元寫壽命僅108～1010次，非常有限，所以采用混合內(nèi)存的方式來同時(shí)發(fā)揮DRAM與PCM的優(yōu)勢(shì)。在設(shè)計(jì)混合內(nèi)存時(shí)，研發(fā)人員提出將寫操作地址進(jìn)行重定位，能夠有效避免同一存儲(chǔ)單元頻繁寫操作。本文提出一種基于BKDRHash函數(shù)的損耗均衡算法，利用Hash函數(shù)對(duì)地址進(jìn)行重定位，并將熱數(shù)據(jù)遷移至DRAM。

1 相關(guān)工作

研究者在設(shè)計(jì)混合內(nèi)存系統(tǒng)的過程中，提出了一系列混合內(nèi)存體系架構(gòu)，大體分為兩類：橫向內(nèi)存架構(gòu)和縱向內(nèi)存架構(gòu)。橫向內(nèi)存架構(gòu)中DRAM與PCM統(tǒng)一編址，縱向架構(gòu)中，DRAM作為PCM的緩存。在對(duì)兩種架構(gòu)設(shè)計(jì)時(shí)，需要在PCM控制器中設(shè)計(jì)損耗均衡策略，使PCM的寫操作均勻分布，如圖2所示。

圖2 混合內(nèi)存架構(gòu)圖

圖2中，PCM的寫操作經(jīng)損耗均衡算法處理再尋址執(zhí)行，而DRAM寫操作經(jīng)系統(tǒng)尋址后執(zhí)行。研究者們提出了一些損耗均衡算法，大體可以分為以下兩類：

(1)利用地址映射實(shí)現(xiàn)。比如李驍?shù)热薣2]提出通過維持一個(gè)隊(duì)列來保存邏輯地址到物理地址的映射；文獻(xiàn)[3-4]都是利用地址映射，當(dāng)滿足一定條件時(shí)，如某個(gè)頁面寫次數(shù)過多，那么系統(tǒng)以一定的方式改變這個(gè)映射，本來寫到原有頁面的數(shù)據(jù)就會(huì)寫到另外頁面；佐治亞理工學(xué)院的SEONG N H等人[5]提出Security Refresh技術(shù)，每一輪刷新都改變映射；文獻(xiàn)[6]提出Start-Gap技術(shù)，在邏輯地址與物理地址之間進(jìn)行代數(shù)映射。這些方法通過改變映射進(jìn)行地址重定位，雖然一定程度上能夠增加系統(tǒng)壽命，但是功耗和延遲都比較高，計(jì)算復(fù)雜。

(2)利用特殊數(shù)據(jù)結(jié)構(gòu)或者硬件實(shí)現(xiàn)。文獻(xiàn)[7]提出了一種叫做Row Shifting的細(xì)粒度的損耗均衡和一種叫做Segment Swapping的粗粒度方法，需要專用硬件來實(shí)現(xiàn)；文獻(xiàn)[8]提出基于Bloom filter數(shù)據(jù)結(jié)構(gòu)的損耗均衡算法，能夠有效提高PCM壽命；文獻(xiàn)[9]提出Curling-PCM算法，挖掘特定應(yīng)用的讀寫特征。這些方法容易實(shí)現(xiàn)，能夠在特定應(yīng)用上取得較好效果，但是功耗與時(shí)延需要進(jìn)一步減少。

本文提出一種基于BKDRHash的損耗均衡算法，能夠在現(xiàn)有硬件條件下，以較小的功耗和延遲代價(jià)實(shí)現(xiàn)PCM的損耗均衡，提高其壽命。

2 基于Hash的損耗均衡算法

由于PCM的寫操作壽命有限，每個(gè)單元的壽命都是108～1010次，當(dāng)其中某一個(gè)PCM單元達(dá)到壽命后，整個(gè)PCM芯片都會(huì)失去作用，從而影響整個(gè)內(nèi)存系統(tǒng)的使用。所以，在設(shè)計(jì)混合內(nèi)存系統(tǒng)時(shí)，不僅要減少PCM的寫操作，而且需要使得PCM上面的寫操作分布均勻，適當(dāng)?shù)卦O(shè)計(jì)從邏輯地址到物理地址的映射函數(shù)。映射函數(shù)可以利用Hash函數(shù)的沖突概率小的特性實(shí)現(xiàn)，對(duì)同一數(shù)據(jù)塊多次更新還需要進(jìn)一步設(shè)計(jì)策略。

3 基于BKDRHash函數(shù)的損耗均衡算法

本文的損耗均衡算法在寫操作之前執(zhí)行，在命令中的邏輯地址映射為物理地址時(shí)，使得PCM存儲(chǔ)空間損耗均衡。由于DRAM寫性能較好，可以在DRAM內(nèi)存空間中保存各個(gè)PCM存儲(chǔ)空間的寫次數(shù)，并且可以經(jīng)常更新。為了充分使PCM單元上的寫操作均勻分布，對(duì)PCM上的寫操作和空閑狀態(tài)進(jìn)行如下設(shè)計(jì)。

(1)寫請(qǐng)求

當(dāng)需要在PCM上執(zhí)行寫請(qǐng)求時(shí)，首先從命令等待隊(duì)列中取出命令，從命令中取出數(shù)據(jù)的邏輯地址，然后對(duì)地址進(jìn)行BKDRHash函數(shù)處理，得到數(shù)據(jù)的物理地址。定義寫平均次數(shù)為總寫入次數(shù)與執(zhí)行過寫操作的單元數(shù)之商。為了使寫操作分布更加均勻，生成隨機(jī)系數(shù)p，即寫入的概率。若此物理地址空閑，并且count小于隨機(jī)生成的概率p與寫平均次數(shù)avg_count的乘積(即以一定的概率寫入)，則將數(shù)據(jù)寫入此物理地址中，刪除等待隊(duì)列中的命令。若物理地址不空閑或count不小于p與寫平均次數(shù)avg_count的乘積，則跳到下一存儲(chǔ)塊，進(jìn)行上述判斷，直到找到符合條件的存儲(chǔ)塊為止，進(jìn)行寫入。具體算法過程如下：

輸入：寫操作命令；

輸出：true/false；

算法過程：

addr1 = getaddr(wait_list);

//從等待隊(duì)列上取出邏輯地址

addr =BKDRHash(addr1);

//利用BKDRHash函數(shù)計(jì)算邏

輯地址為addr的物理地址并返回

p = Random();

//生成隨機(jī)系數(shù)

count = getcount(addr);

//獲取寫操作次數(shù)count

max=get();

//獲取循環(huán)次數(shù)，即地址閾值

while(1){

if(addr.empty() && (count

{//滿足條件，存儲(chǔ)塊為空

count++;

//寫次數(shù)加1

write();

//執(zhí)行PCM寫操作

delete1();

//刪除等待隊(duì)列上的命令

break;

}

else

if(addr==max) return false；

addr++;

//跳到下一存儲(chǔ)塊

}

return true;

(2)空閑狀態(tài)

在空閑狀態(tài)時(shí)，即此時(shí)內(nèi)存的負(fù)載低時(shí)，某些PCM單元仍然存在寫操作頻繁的問題，這是由于某塊數(shù)據(jù)需要經(jīng)常更新引起的。上述寫操作算法無法解決此問題，需要設(shè)計(jì)一種方法解決此問題。

由于DRAM寫操作性能比PCM好，因此在本文中，提出一種主動(dòng)遷移熱數(shù)據(jù)策略，將上述更新頻繁的數(shù)據(jù)遷移到DRAM中。同樣的，為了使得分布更加均勻，生成一個(gè)隨機(jī)系數(shù)q(以一定的概率遷移數(shù)據(jù))，維持一個(gè)離線遷移隊(duì)列。在每一時(shí)鐘周期時(shí)，處理離線遷移隊(duì)列上對(duì)應(yīng)的數(shù)據(jù)。

首先，在PCM上執(zhí)行一個(gè)寫操作之后，檢查寫操作次數(shù)count是否大于隨機(jī)系數(shù)q與平均寫次數(shù)avg_count的乘積，若不等式成立，則將此數(shù)據(jù)掛入離線遷移隊(duì)列上，若不成立，則不需要遷移。掛入離線遷移隊(duì)列的算法如下：

輸入：寫操作命令；

輸出：true/false；

算法過程：

q = Random();

if(count>q*avg_count)

{

//寫操作次數(shù)大于q與平均寫次數(shù)的乘積

hang(data);

//將數(shù)據(jù)掛入離線遷移隊(duì)列

return true;

}

return false;

當(dāng)數(shù)據(jù)掛入離線遷移隊(duì)列時(shí)，數(shù)據(jù)仍然存儲(chǔ)于PCM，只有在每一時(shí)鐘周期系統(tǒng)空閑時(shí)，遷移隊(duì)列上的數(shù)據(jù)至DRAM之后，才能刪除PCM上的數(shù)據(jù)。

其次，在每一時(shí)鐘周期內(nèi)存系統(tǒng)空閑時(shí)，取出離線遷移隊(duì)列上的數(shù)據(jù)，將數(shù)據(jù)寫入相應(yīng)的DRAM地址中，在計(jì)算DRAM物理地址時(shí)，同樣采用BKDRHash函數(shù)計(jì)算，若DRAM單元空閑，則將數(shù)據(jù)遷移此單元中，并刪除離線遷移隊(duì)列上的數(shù)據(jù)。具體的數(shù)據(jù)遷移算法如下：

輸入：離線遷移隊(duì)列；

輸出：true/false；

算法過程：

data = getdata();

//獲取需要遷移的數(shù)據(jù)

addr2 = getaddr();

//獲取遷移的DRAM地址

addr3 = BKDRHash(addr2);

//利用BKDRHash函數(shù)計(jì)算

邏輯地址為addr2的物理地址并返回

if(addr3.empty())

//存儲(chǔ)塊空閑

{

write(data);

//將數(shù)據(jù)寫入DRAM

delete2(data);

//刪除離線遷移隊(duì)列上的數(shù)據(jù)

return true；

}

return false；

在此過程中，需要在DRAM單元空閑時(shí)執(zhí)行，避免數(shù)據(jù)發(fā)生沖突。在執(zhí)行遷移過程中，若需要執(zhí)行讀寫操作，立即中斷遷移。

4 理論分析

4.1 寫操作分析

對(duì)于p、q來說，生成的隨機(jī)值直接影響后續(xù)的操作，當(dāng)p越接近1時(shí)，執(zhí)行寫操作的概率越大，所以能夠更快找到存儲(chǔ)塊的地址，將數(shù)據(jù)寫入。當(dāng)p越小，接近0時(shí)，能夠更好地選出寫次數(shù)較小的存儲(chǔ)塊進(jìn)行存儲(chǔ)。當(dāng)q越接近1時(shí)，遷移的概率越大，產(chǎn)生越多的時(shí)延與能耗，但是能夠有效減少寫操作次數(shù)。當(dāng)q越接近0時(shí)，更少的數(shù)據(jù)進(jìn)行遷移，但是寫操作次數(shù)更多。

4.2 開銷分析

在整個(gè)策略的過程中，存在兩種開銷，一種是額外存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)的開銷，一種是計(jì)算產(chǎn)生的時(shí)延開銷。

本文需要存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)包括存儲(chǔ)PCM每一存儲(chǔ)單元對(duì)應(yīng)的寫操作次數(shù)的數(shù)據(jù)結(jié)構(gòu)、等待隊(duì)列、離線遷移隊(duì)列等，這些數(shù)據(jù)結(jié)構(gòu)都存儲(chǔ)在DRAM中，由操作系統(tǒng)統(tǒng)一管理。計(jì)算產(chǎn)生的時(shí)延開銷包括BKDRHash函數(shù)計(jì)算產(chǎn)生的開銷、隨機(jī)數(shù)的生成等，這些開銷對(duì)內(nèi)存的計(jì)算速度影響不大。

5 結(jié)果驗(yàn)證

5.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用Linux環(huán)境，Ubuntu版本為Ubuntu12.04 64位，虛擬機(jī)硬件設(shè)置為：內(nèi)存1 GB、硬盤(SCSI)20 GB、處理器數(shù)量為1。使用DRAMsim2模擬器進(jìn)行仿真模擬。

實(shí)驗(yàn)過程中，通過改變system.ini等配置文件中的參數(shù)進(jìn)行混合內(nèi)存系統(tǒng)模擬，將PCM+DRAM混合內(nèi)存系統(tǒng)加入該策略與否進(jìn)行對(duì)比實(shí)驗(yàn)。

文中使用5種系統(tǒng)配置，配置參數(shù)如表1所示。

表1 5種系統(tǒng)配置參數(shù)

5.2 評(píng)估指標(biāo)

實(shí)驗(yàn)中評(píng)估指標(biāo)有三項(xiàng)，首先是為了評(píng)估系統(tǒng)壽命，所有PCM存儲(chǔ)塊的最大寫操作次數(shù)與最小寫操作次數(shù)之差是損耗均衡效果的很好的一項(xiàng)參考標(biāo)準(zhǔn)；其次是能耗，在產(chǎn)生額外的數(shù)據(jù)結(jié)構(gòu)之后，相比于原系統(tǒng)來說產(chǎn)生額外的能耗；最后是延遲，反映了由算法計(jì)算產(chǎn)生的額外延遲。后兩項(xiàng)反映了本文損耗均衡算法所產(chǎn)生的代價(jià)。

5.3 實(shí)驗(yàn)結(jié)果與分析

5.3.1 壽命測(cè)試結(jié)果

本文以壽命為測(cè)試指標(biāo)，使用PCM存儲(chǔ)單元的寫操作最大次數(shù)與最小次數(shù)之差量化。在系統(tǒng)1配置下進(jìn)行實(shí)驗(yàn)，表2給出了實(shí)驗(yàn)結(jié)果 (循環(huán)次數(shù)為讀取命令的條數(shù))。

表2 壽命測(cè)試結(jié)果

由表2可以看出，當(dāng)循環(huán)次數(shù)增加時(shí)，寫操作最大次數(shù)與最小次數(shù)之差增加直至趨于穩(wěn)定，并且，使用本文損耗均衡算法能夠大幅減少寫操作最大次數(shù)與最小次數(shù)之差，即使得寫操作分布更加均勻，大大延長(zhǎng)了系統(tǒng)壽命。

5.3.2 能耗測(cè)試結(jié)果

圖3展示了在系統(tǒng)1配置下功耗測(cè)試結(jié)果。圖4闡述了不同系統(tǒng)配置的功耗測(cè)試結(jié)果。

圖3 同一系統(tǒng)功耗測(cè)試結(jié)果

圖4 不同系統(tǒng)功耗測(cè)試結(jié)果

從圖3可以看出，隨著循環(huán)次數(shù)的增加，功耗減小，這是因?yàn)橄到y(tǒng)消耗的能量增加，但是作為除數(shù)的循環(huán)次數(shù)也增加，功率反而減小。從圖4可以看出，不同系統(tǒng)配置產(chǎn)生的功耗不同。

綜合圖3、4可以看出，在使用本文的損耗均衡策略之后，功耗僅僅有少量的增加，增加的平均幅度僅為1%～3%，這說明本文損耗均衡策略功耗的代價(jià)較小。

5.3.3 延遲測(cè)試結(jié)果

圖5展示了在系統(tǒng)1配置下延遲測(cè)試結(jié)果。圖6闡述了不同系統(tǒng)配置的延遲測(cè)試結(jié)果。

圖5 同一系統(tǒng)延遲測(cè)試結(jié)果

圖6 不同系統(tǒng)延遲測(cè)試結(jié)果

從圖5可以看出，隨著循環(huán)次數(shù)的增加，系統(tǒng)延遲在一定范圍內(nèi)波動(dòng)之后，持續(xù)增加。從圖6可以看出，不同系統(tǒng)產(chǎn)生的延遲不同。

綜合圖5、6可以看出，使用本文的損耗均衡策略之后，延遲有少量的增加，增加的平均幅度為10%～15%，雖然增加的幅度比功耗大，但是實(shí)驗(yàn)中是以μs為單位，兩者的平均差距在0.1～0.9 s之間，不影響系統(tǒng)的運(yùn)行，是可以接受的。故本文的損耗均衡算法產(chǎn)生的延遲代價(jià)是可以接受的。

6 結(jié)束語

由于NVM寫操作壽命有限，每一單元僅為108～1010次，需要均衡NVM存儲(chǔ)單元上的寫操作，本文提出一種基于BKDRHash函數(shù)的損耗均衡算法，利用BKDRHash函數(shù)沖突概率小的特性，同時(shí)引入了隨機(jī)系數(shù)，使得寫操作分布更加均勻，而且，將更新頻繁的數(shù)據(jù)向DRAM遷移，能夠大幅提高PCM的壽命。本文損耗均衡算法針對(duì)兩種情況進(jìn)行設(shè)計(jì)，首先是在執(zhí)行寫操作時(shí)，需要將邏輯地址映射為物理地址，其次，對(duì)于頻繁更新的數(shù)據(jù)進(jìn)行熱數(shù)據(jù)遷移，將PCM上的數(shù)據(jù)遷移至DRAM中。實(shí)驗(yàn)證明，提出的損耗均衡算法能夠以很少的時(shí)延與功耗大幅提高PCM的使用壽命，進(jìn)而提高整個(gè)內(nèi)存系統(tǒng)的壽命與穩(wěn)定性。

[1] 冒偉，劉景寧，童薇，等.基于相變存儲(chǔ)器的存儲(chǔ)技術(shù)研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(5): 944-960.

[2] 李驍.基于混合架構(gòu)的高效頁面替換算法的分析[D].濟(jì)南：山東大學(xué)，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

吳煬，付印金，陳衛(wèi)衛(wèi)，等.基于BKDRHash的混合內(nèi)存損耗均衡算法研究[J].微型機(jī)與應(yīng)用，2017,36(11)：15-18，22.

2017-01-13)

吳煬(1992-)，男，碩士研究生，主要研究方向：云存儲(chǔ)、混合內(nèi)存。

付印金(1984-)，男，博士，講師，主要研究方向：大數(shù)據(jù)管理、網(wǎng)絡(luò)存儲(chǔ)和云計(jì)算。

陳衛(wèi)衛(wèi)(1967-)，女，碩士，教授，碩士生導(dǎo)師，主要研究方向：云計(jì)算和大數(shù)據(jù)管理。