0. 引 言

現(xiàn)在越來越多的筆記本電腦、智能手機(jī)、固態(tài)硬盤等新型電子設(shè)備開始裝備NAND閃存，憑借特有的存儲方式和超高的穩(wěn)定性、可靠性，NAND閃存得到越來越多廠商的青睞.配備NAND閃存的固態(tài)硬盤也憑借諸多優(yōu)勢逐漸取代傳統(tǒng)機(jī)械硬盤[1].

采用NAND閃存作為存儲裝置的固態(tài)硬盤沒有采用像機(jī)械硬盤那樣的復(fù)雜精密結(jié)構(gòu)，讀取數(shù)據(jù)不需要尋道時間，并且也有獨特的寫入方式，所以能夠獲得比較快的讀取和寫入速度.并且由于NAND閃存體積小，接口應(yīng)用廣泛，適應(yīng)各種結(jié)構(gòu)形式，所以可以被手機(jī)、筆記本電腦等精密設(shè)備采用[2].然而NAND閃存存儲器使用電子管來存儲，重復(fù)寫入擦除數(shù)據(jù)極易導(dǎo)致?lián)p壞，其物理塊僅能承受幾千次的擦寫操作.要想廣泛的應(yīng)用NAND閃存就需要采用合適的平均每個物理塊磨損的機(jī)制，也就是損耗均衡機(jī)制，以此才能延長閃存的使用壽命.

[[228943]]

在1994年，PCMCIA(個人計算機(jī)內(nèi)存卡國際協(xié)會)提出了Flash轉(zhuǎn)換層(FTL)的概念，F(xiàn)AT文件系統(tǒng)用于NAND Flash時，是由控制器通過管理NAND Flash建立一個邏輯的FAT文件系統(tǒng)，供上層應(yīng)用調(diào)用，同時它也可以高效的執(zhí)行損耗均衡[3].實現(xiàn)閃存損耗均衡的算法按照類型分為：動態(tài)損耗均衡和靜態(tài)損耗均衡[4].Ban等[3]針對靜態(tài)均衡算法的觸發(fā)機(jī)制進(jìn)行了研究，并提出兩種觸發(fā)機(jī)制：確定性觸發(fā)機(jī)制和隨機(jī)性觸發(fā)機(jī)制.Yared Hailu Gudeta等[5]提出了基于概率的靜態(tài)損耗平均算法.在每個狀態(tài)下，磨損平均分布使用標(biāo)準(zhǔn)偏差來計算，以確定其是否超過閾.如果它超過閾值，則在所有塊中維持損耗平衡通過將熱塊與冷塊交換在閃存中.Lee等[6]在靜態(tài)損耗均衡算法上進(jìn)行了研究，該算法會在系統(tǒng)初始化時將閃存存儲空間劃分成若干組，從開始***次更新之后就記錄每一個組的擦寫次數(shù).到達(dá)損耗均衡的觸發(fā)條件時統(tǒng)計高于平均擦寫次數(shù)的組及組內(nèi)的物理塊，然后將這些塊的數(shù)據(jù)搬運至空塊，再更新地址映像表.

邢春波[7]提出一種混合損耗均衡算法(HWL)，該法也是在系統(tǒng)初始化時將閃存空間分塊，每塊的擦寫次數(shù)由單獨分配的一個字節(jié)的存儲空間記錄擦寫情況，并采用一個數(shù)組來維護(hù)所有的塊的擦寫情況.該算法統(tǒng)計每一個系統(tǒng)更新周期內(nèi)的各塊擦寫情況， HWL算法是目前應(yīng)用最廣發(fā)的算法之一，本文也是建立在該算法的基礎(chǔ)上進(jìn)行改進(jìn)而來.

本文根據(jù)閃存的物理塊在使用過程中擦寫的次數(shù)，對閃存數(shù)據(jù)塊進(jìn)行分類并給出相應(yīng)的判斷標(biāo)準(zhǔn)，同時引入與損耗均衡算法密切相關(guān)的閥值的概念；針對損耗均衡算法不能隨著存儲需求作調(diào)整的缺陷，給出根據(jù)數(shù)據(jù)塊擦寫次數(shù)的標(biāo)準(zhǔn)差動態(tài)調(diào)整閥值的算法；結(jié)合傳統(tǒng)的動態(tài)損耗均衡算法和靜態(tài)損耗均衡算法，給出損耗均衡算法的評價標(biāo)準(zhǔn)，將靜態(tài)損耗均衡算法和動態(tài)損耗均衡算法兩者結(jié)合設(shè)計出新的均衡損耗算法；根據(jù)需求設(shè)計了評估損耗均衡算法效果的測試實驗，對損耗均衡算法的效果進(jìn)行了實驗測試.實驗結(jié)果表明本文提出的改進(jìn)算法對減小閃存存儲器擦寫的不均衡性有很好的效果.

1 NAND閃存損耗均衡機(jī)制及策略

1.1 NAND閃存的工作原理

NAND是一種計算機(jī)閃存設(shè)備.隨著人們持續(xù)不斷追求功耗更低、重量更輕和性能更佳的產(chǎn)品，這證明了NAND***吸引力.閃存存儲器按照存儲單元的存儲控制方式可分為單層單元SLC和多層單元MLC控制方式.單層單元SLC控制方式是依靠MOS管疊柵上不同的電荷量來區(qū)分0與1兩種狀態(tài)，多個MOS管組成疊柵成為一個存儲單元.相對應(yīng)的多層單元MLC控制方式由單層單元SLC控制方式改進(jìn)而來，它的一個疊柵可以識別四種存儲狀態(tài)：00、01、10、11.但同時由于該種MOS管需要去識別多種電荷量，然而這會造成物理性能不穩(wěn)定，導(dǎo)致這種閃存的壽命較少.正是因為這種問題，損耗均衡機(jī)制的重要性被進(jìn)一步提高，為了保證多層單元MLC控制方式閃存的使用壽命，必須在文件系統(tǒng)中使用損耗均衡和機(jī)制.

1.2 損耗均衡評價指標(biāo)

損耗均衡(wear leveling)[8]是指用來延長固態(tài)存儲設(shè)備使用壽命的過程.閃存損耗均衡技術(shù)的設(shè)計目標(biāo)是：在盡可能減少閃存中所有塊的總擦除次數(shù)的前提下，盡可能使閃存中的每個塊擦除次數(shù)趨向一致或在一定范圍內(nèi).根據(jù)統(tǒng)計學(xué)的知識我們可以知道平均值描述了一個樣本的平均水平，標(biāo)準(zhǔn)差能反映一個數(shù)據(jù)集的離散程度.根據(jù)這個設(shè)計目標(biāo)提出衡量閃存損耗均衡度的兩個指標(biāo)：平均擦除次數(shù)擦除次數(shù)標(biāo)準(zhǔn)偏差Deviation,簡寫為Dev.

公式(1)、(2)中E(i)表示第i塊的擦除次數(shù)，n為閃存的總塊數(shù).

綜合以上因素可以知道，一個較好的閃存系統(tǒng)損耗均衡策略可以使熱數(shù)據(jù)和冷數(shù)據(jù)的遷移次數(shù)盡可能多，同時總的物理塊擦除次數(shù)的平均值越小，這樣閃存的使用壽命大大延長.另外物理塊的擦除次數(shù)的標(biāo)準(zhǔn)差越小，表明每一個物理塊的擦出次數(shù)偏離平均擦除次數(shù)較少，損耗均衡機(jī)制的執(zhí)行效果較好.相反，損耗均衡機(jī)制的執(zhí)行效果較差.

1.3 損耗均衡策略

1)動態(tài)損耗均衡策略

動態(tài)損耗均衡算法[9]主要原理是：先將所有的閃存物理塊鏈接到一個動態(tài)維護(hù)的表格，在表格中將各物理塊的擦除次數(shù)從大到小進(jìn)行排序.當(dāng)數(shù)據(jù)更新時，要求數(shù)據(jù)寫入到表格***的物理塊，也就是擦除次數(shù)最小的物理塊，然后再按照擦寫次數(shù)進(jìn)行排序.按照這樣的方法數(shù)據(jù)永遠(yuǎn)都是寫入到擦除次數(shù)最小的物理塊，使得閃存的各塊均得到同樣的磨損狀況.

2)靜態(tài)損耗均衡策略

靜態(tài)損耗均衡算法在動態(tài)損耗均衡算法的基礎(chǔ)上改進(jìn)而來，考慮到動態(tài)損耗均衡算法中一直優(yōu)先將數(shù)據(jù)寫入到擦出次數(shù)較少的物理塊中，原先儲備的更新較少的冷數(shù)據(jù)就會一直占據(jù)該物理塊，得不到釋放.所以靜態(tài)損耗均衡算法考慮了冷數(shù)據(jù)的搬運，使得整個閃存存儲空間都在不斷的進(jìn)行均衡磨損.靜態(tài)損耗均衡算法將焦點放在冷數(shù)據(jù)上，預(yù)先設(shè)置擦寫次數(shù)的閥值，采用遍歷各塊的方法統(tǒng)計得出更新頻率低于閥值的方法，篩選出冷數(shù)據(jù)塊，然后將數(shù)據(jù)搬遷至擦出次數(shù)較多的物理塊中.用同樣的方法篩選出熱數(shù)據(jù)塊，將熱數(shù)據(jù)塊搬遷至擦除次數(shù)較少的物理塊中.通過這種方法，閃存中的各物理塊的擦除次數(shù)比較均衡，并且隨著靜態(tài)均衡機(jī)制的不斷觸發(fā)，熱數(shù)據(jù)塊的擦出次數(shù)增長十分緩慢，冷數(shù)據(jù)塊的擦出次數(shù)有一定的提高，從而是十分有效的損耗均衡算法.

2 靜態(tài)均衡算法設(shè)計

本文的靜態(tài)損耗均衡算法是將現(xiàn)有的動態(tài)均衡算法與靜態(tài)算法相結(jié)合，設(shè)計出一種更加完善的算法流程.靜態(tài)損耗均衡算法的設(shè)計基本原理在前文介紹過，為此定義擦除次數(shù)最多為Nmax，擦除次數(shù)最少為Nmin，兩者差值為Th，則需要研究的問題[10]的表述為：

這里式(4)中的Th就是本文所研究的靜態(tài)損耗均衡算法的核心，即要選擇恰當(dāng)?shù)拈y值Th，使得物理塊的擦除次數(shù)上下限相差不會太大.同時又要滿足盡可能小的平均值和標(biāo)準(zhǔn)差.

2.1 觸發(fā)條件的優(yōu)化

確定性觸發(fā)的難點在于難以找到合適的系統(tǒng)更新次數(shù)，隨機(jī)性觸發(fā)只是用于系統(tǒng)更新頻率較高的情況[11].

為此本文設(shè)計了一種可以動態(tài)選擇觸發(fā)機(jī)制的算法，將確定性觸發(fā)和隨機(jī)性觸發(fā)相結(jié)合，該算法會統(tǒng)計系統(tǒng)的更新頻率.如果更新頻率較高則選擇隨機(jī)觸發(fā)條件，如果更新頻率較低則選擇確定性觸發(fā)條件.參考損耗均衡機(jī)制的評價標(biāo)準(zhǔn)，選擇系統(tǒng)更新次數(shù)的均值當(dāng)做判別條件.流程圖如圖1所示.

圖1 優(yōu)化的觸發(fā)條件流程圖

Fig.1 Flow chart of optimal trigger condition

2.2 閥值確定數(shù)據(jù)塊的狀態(tài)

數(shù)據(jù)塊的磨損狀態(tài)由該塊的擦寫次數(shù)在數(shù)據(jù)擦寫中所占的比例決定，即

式中wi表示該塊的磨損程度，ei表示該塊在本次系統(tǒng)更新中的擦寫次數(shù)，a0是本次系統(tǒng)更新總的擦寫次數(shù).

在磨損均衡過程中維護(hù)了一個磨損信息表，表中為每個物理塊分配一個字節(jié)的空間記錄磨損狀態(tài)wi.如果wi達(dá)到閥值whigh就將該塊定義為熱數(shù)據(jù)塊，同理低于閥值wlow就將該塊定義為冷數(shù)據(jù)塊.

2.3 算法流程

由以上結(jié)論可知，要想解決損耗均衡的問題，就必須在盡可能小的影響性能的條件下使擦寫任務(wù)均勻的分布在每個數(shù)據(jù)塊[12].本文在解決這個問題時候，通過對以往動態(tài)和靜態(tài)算法的研究下，就此設(shè)計了動態(tài)靜態(tài)算法相結(jié)合的NAND FLASH閃存損耗均衡的算法.

一個完整的靜態(tài)損耗均衡流程為：在系統(tǒng)更新操作每過一定的擦寫次數(shù)n時啟動靜態(tài)損耗均衡機(jī)制，首先遍歷所有參與擦寫的數(shù)據(jù)塊，計算得出數(shù)據(jù)塊的磨損狀態(tài).按照磨損狀態(tài)從低到高排序，達(dá)到閥值whigh就將該塊定義為熱數(shù)據(jù)塊，低于閥值wlow就定義為冷數(shù)據(jù)塊.然后將熱數(shù)據(jù)塊中的有效數(shù)據(jù)搬遷至新的空塊或者磨損狀態(tài)wi***塊，將冷數(shù)據(jù)塊搬遷到原先的最熱數(shù)據(jù)塊，重排后依次進(jìn)行，將搬遷后的數(shù)據(jù)塊重新鏈接到文件系統(tǒng).本次損耗均衡結(jié)束后計算沒有超出閥值的數(shù)據(jù)塊的擦除次數(shù)標(biāo)準(zhǔn)偏差，如果過高則標(biāo)記超出平均擦除次數(shù)一定值的塊為熱數(shù)據(jù)塊，并參與下一次系統(tǒng)更新.這樣熱數(shù)據(jù)塊就會不斷被搬遷新的物理塊，不會只在部分塊內(nèi)擦寫，有效降低了閃存數(shù)據(jù)塊的磨損.算法流程如圖2，圖3所示.

圖2 完整的均衡損耗流程圖一

Fig.2 Complete balanced loss flow diagramⅠ

圖3 完整的均衡損耗流程圖二

Fig.3 Complete balanced loss flow diagramⅡ

3 仿真測試

3.1 實驗平臺搭建

為了測試本文設(shè)計的損耗均衡算法的效果，借助SSD Sim搭建測試平臺.它可以在普通的計算機(jī)平臺上模擬NAND閃存的存儲狀況，用戶可以在SSD Sim軟件中設(shè)置存儲容量、存儲信道、閃存塊大小等參數(shù)，根據(jù)用戶需求可以在沒有閃存硬件的支持下模擬NAND閃存的使用情況.

為了直觀的對比損耗均衡算法的效果，本文設(shè)計了兩個NAND閃存，每個閃存分配4個閃存芯片，它們之間以并行方式連接，其中閃存1采用傳統(tǒng)的靜態(tài)損耗均衡算法[13](HWL算法);閃存2采用本文改進(jìn)后的損耗均衡算法，兩個閃存都寫入同樣的1×106次數(shù)據(jù)量寫入請求.兩個閃存的其他詳細(xì)配置如表1所示.

表1閃存配置表

Table1Flashconfigurationtable

3.2 測試內(nèi)容及結(jié)果分析

本節(jié)比較了分別采用改進(jìn)前和改進(jìn)后的損耗均衡算法的效果.主要通過對比兩種磨損狀態(tài)閥值w，系統(tǒng)更新次數(shù)n和靜態(tài)損耗周期M三個因素對閃存存儲的磨損均衡性能的影響，評價的指標(biāo)用一個周期內(nèi)的擦除次數(shù)標(biāo)準(zhǔn)偏差來描述.

1)為研究磨損狀態(tài)閥值上限對閃存存儲的磨損均衡性能的影響，設(shè)置HWL算法下w=1.2%和w=0.8%兩種情況下記錄隨著寫入請求的增加，物理塊擦除次數(shù)標(biāo)準(zhǔn)差的變化情況.

從圖4、圖5可以看出相比HWL算法，改進(jìn)后的靜態(tài)損耗均衡算法的損耗均衡效果更好一些.隨著寫入請求不斷增加，兩者的標(biāo)準(zhǔn)差都是穩(wěn)定增長.這說明隨著寫入請求的不斷增多在靜態(tài)損耗均衡機(jī)制的控制下標(biāo)準(zhǔn)差的增長趨于穩(wěn)定，趨于穩(wěn)定時改進(jìn)后的擦寫次數(shù)的標(biāo)準(zhǔn)差比HWL算法小約16.4%，這說明改進(jìn)后的閥值使得損耗均衡效果更好.

2)通過物理塊擦寫次數(shù)的標(biāo)準(zhǔn)差變化曲線，比較改進(jìn)之前和改進(jìn)之后的靜態(tài)損耗均衡的周期對靜態(tài)損耗均衡效果的影響.HWL算法是采用固定周期，改進(jìn)后的算法采用變周期.從圖中可以明顯看出改進(jìn)后的靜態(tài)損耗均衡算法效果顯著：從寫入請求達(dá)到2.2×105次時，兩者的擦寫次數(shù)標(biāo)準(zhǔn)差均達(dá)到***.但是隨后HWL算法的擦寫次數(shù)標(biāo)準(zhǔn)差繼續(xù)增長，直到寫入請求達(dá)到7.4×105時才有下降的趨勢；然而改進(jìn)后的擦寫次數(shù)標(biāo)準(zhǔn)差開始下降，并最終穩(wěn)定到10×105左右.由于改進(jìn)后的算法采用了動態(tài)的周期選擇的方法，相比HWL的固定周期能更好地適應(yīng)閃存靜態(tài)損耗均衡的需求.

圖4 磨損狀態(tài)閥值上限對閃存存儲的 磨損均衡性能的影響

Fig.4 Effect of wear state threshold on wear equalization performance of flash

圖5 靜態(tài)損耗均衡的周期對靜態(tài) 損耗均衡效果影響的對比分析圖

Fig.5 Comparison and analysis of the influence of static loss equalization cycle on static loss equalization

同時本文選取了另外一個M=10的變化曲線對比觀察，發(fā)現(xiàn)即使是將靜態(tài)損耗及均衡周期設(shè)置的比較短，損耗均衡的效果仍然不理想.

4 結(jié) 論

對目前較流行的HWL損耗均衡算法進(jìn)行優(yōu)化.重新定義了數(shù)據(jù)塊的冷熱屬性，并以高低閥值作為熱數(shù)據(jù)和冷數(shù)據(jù)的判定條件；對觸發(fā)機(jī)制進(jìn)行優(yōu)化和將現(xiàn)有的靜態(tài)損耗均衡策略與動態(tài)損耗均衡策略相結(jié)合的優(yōu)化策略.通過SSD Sim軟件完成了對比測試，實驗證明改進(jìn)后的損耗均衡算法有效的降低了物理塊擦除次數(shù)的標(biāo)準(zhǔn)差，使得損耗均衡效果得到提高.