新型非易失存儲器靜態(tài)損耗均衡算法

前言

新型非易失存儲器正在逐漸成熟，有望在未來成為工作存儲器。然而，在工業(yè)實踐中，我們發(fā)現(xiàn)一些非易失存儲器，包含阻變隨機存儲器（RRAM）、相變隨機存儲器（PCM）和閃存（Flash）等在使用時會面臨使用耐久性有限的問題，即對于一個地址的寫入次數(shù)是有限的，而實際對存儲器進行寫操作時，往往會很頻繁的訪問部分地址，一旦存儲器任何部分的寫入次數(shù)超過了耐久極限，整個器件就會被認為無法工作。因此，需要設計一些算法使得能對整個存儲器做均衡的訪問，而不是僅僅去對幾個特定的區(qū)域持續(xù)寫入，將對某些塊的操作分布到整片存儲器上，實現(xiàn)各塊寫入的平衡，這類算法就稱為損耗均衡（wear leveling）算法。

硬件損耗均衡算法簡介

硬件損耗均衡算法大致可以分為靜態(tài)和動態(tài)損耗均衡。

動態(tài)損耗均衡：這些算法通過重復使用擦除次數(shù)較少的塊來實現(xiàn)損耗平衡[1]。即當下寫入地址的被寫入量超過規(guī)定的閾值時就讓其與一個認為的寫入次數(shù)不大的地址做交換。然而對于原本就存在于那些被寫入次數(shù)不多的地址里面的數(shù)據(jù)，不做移動。

靜態(tài)損耗均衡：與動態(tài)相反，靜態(tài)損耗均衡算法試圖通過整個物理地址的移動，從而促進損耗的更均勻分布。

與動態(tài)方法相比靜態(tài)方法優(yōu)勢在于空間開銷小，不需要考慮具體程序的動態(tài)運行也能達到延長存儲器壽命的目的，但正因為于此靜態(tài)的方法不能充分的挖掘存儲器的生命潛力。而動態(tài)方法借助記錄每個地址被寫入的次數(shù)、建立地址映射表、定期清理垃圾數(shù)據(jù)等方式，雖然存儲開銷相比靜態(tài)方法增加了但可以獲得更好地延長存儲器壽命的結果。當然最好的均衡損耗算法一定是根據(jù)具體的應用場景去相應調整的，沒有最好的算法只有最適合的算法。

下面將先介紹一些靜態(tài)損耗均衡算法：

1.?基于 PCM 存儲器的 Start-Gap 算法[2]

借助兩個寄存器 Start、Gap 以及一個緩存區(qū)，周期性將每一行（包括很多個地址，具體怎么劃分依照設計者的需求決定）移動到其相鄰的位置來實現(xiàn)損耗均衡。實質上就是建立了一個代數(shù)關系，完成邏輯地址到物理地址的映射。

Gap 記錄緩存區(qū)的物理地址，Start 記錄的是所有塊均移動一次的次數(shù)。每當寫入次數(shù)達到設定的閾值時，通過 Gap 存儲的地址指引，將緩存區(qū)（圖中紅色塊）不斷向前移動，當緩存區(qū)到達第一塊時，下一次就移動到最后一塊，如此循環(huán)。具體每一次移動操作為（如圖1）：

圖1：在一個包含16行的存儲器上進行Start-Gap算法

邏輯地址（LA——logical address）與物理地址（PA——physical address）間的代數(shù)關系為：（N等于內存中不包含緩沖區(qū)的行數(shù)）

由于 CPU 在訪問寄存器時，無論是存取數(shù)據(jù)還是存取指令，都趨于聚集在一片區(qū)域——局部性原理，可以看出僅依靠這樣相鄰位的移動，會將一個大量寫入的行移動到另一個大量寫入的行，這可能導致早期的磨損。于是引入靜態(tài)地址隨機化，將原本連續(xù)的地址重映射為彼此間隔很大的新地址。

實現(xiàn)靜態(tài)隨機化處理可以借助隨機可逆的二進制矩陣（Random Invertible Binary Matrix），如圖2，RIB 內部的元素由0，1隨機序列，當邏輯地址與該矩陣相乘后，可以使得原本連續(xù)的 LA 值分散開。

圖2：4位地址隨機化

綜上所述，完整的 Start-Gap 算法框架如圖3：

圖3：Start-Gap架構

2.基于 RRAM 為主存儲器的細顆粒度均衡[3]

與上面介紹的 Start-Gap 算法思路比較相似，Start-Gap 算法是每到一個寫入閾值執(zhí)行一個行的數(shù)據(jù)遷移，而細顆粒度則是以時間為周期，每一周期將所有的地址均遷移一次，移動間隔為一個隨機數(shù)，每一周期生成一個新的隨機數(shù)。所謂細顆粒，意思就是均衡的對象是具體到每一個地址而不是將一些地址集合在一起視為一個整體來做處理。

3.?基于 Flash 的 SW Leveler 算法[4]

考慮 Flash 在更新數(shù)據(jù)時需要寫入另一個地址，將原地址標記為無效（垃圾），需要擦除后才能繼續(xù)寫入。算法設計的目的就是讓存儲器的各個地址擦除次數(shù)分布均勻。

具體為：觸發(fā)清潔器對選定的區(qū)塊進行垃圾收集，讓 SW 均衡器與塊擦除表(BET，建立的目的是記住哪個塊在預定的時間范圍內被擦除，以便找到冷數(shù)據(jù)的地址。)相關聯(lián)，以記住在選定的時間段內哪個塊被擦除了。當 SW 均衡器運行時，它要么重置 BET，要么撿起一個至今未被擦除的塊（基于BET信息），并觸發(fā)清潔器對該塊進行垃圾收集。區(qū)塊的選擇過程必須在有限的時間內以有效的方式完成。每當一個區(qū)塊被擦除時，BET 同步更新。

4.?基于 Flash 的 Rejuvenator 算法[1]

Rejuvenator 的基本原則為防止區(qū)塊更快地達到其使用壽命，并使它們保持年輕，即保持區(qū)塊寫入次數(shù)不會很多。只有在 Flash 寫入次數(shù)達到設定閾值時才會積極地平衡，以此來最大限度地減少搬移冷數(shù)據(jù)（不經(jīng)常被訪問但是需要長期保存的數(shù)據(jù)）的開銷，可用于大容量?Flash?的擴展。

根據(jù)區(qū)塊當前的擦除次數(shù)將其分為不同的組。

Rejuvenator 維護一個列表，將熱數(shù)據(jù)（經(jīng)常別訪問的數(shù)據(jù)）放在編號較低的區(qū)塊中，將冷數(shù)據(jù)放在編號較高的區(qū)塊中。集群的范圍被限制在一個閾值內。這個閾值是根據(jù)區(qū)塊的擦除次數(shù)來調整的。

每個區(qū)塊可以有三種類型的頁面：有效頁面、無效頁面和清潔頁面。有效頁包含有效的或活的數(shù)據(jù)。無效頁包含不再有效的數(shù)據(jù)。清潔頁不包含任何數(shù)據(jù)。

當一個寫入操作到來時，如果該邏輯地址有一個現(xiàn)有的映射（映射的物理塊中的相應頁面將是空閑或無效的）。數(shù)據(jù)將被寫入映射的物理塊中的相應頁面。如果沒有與 LBA 相關的塊映射，它將被寫到屬于較高編號列表的一個干凈的塊中。

此外還有一些已被提出來并且獲得了不錯效果的動態(tài)損耗均衡算法：

1.?基于硬件損耗均衡的 Flash 控制器[5]

將 Flash 中的塊分為三類，空閑塊，有效塊和垃圾塊?？臻e塊指的是尚未被使用，可以直接寫入新數(shù)據(jù)的塊。有效塊指的是該塊中存放著有效數(shù)據(jù)，該塊的地址已存在與地址映射表（記錄物理地址和邏輯地址映射關系的表格）中，存放的數(shù)據(jù)為最新寫入的正確的數(shù)據(jù)。垃圾塊指該塊中存放的數(shù)據(jù)已經(jīng)無效，之前對應該塊的地址已經(jīng)被映射到新的物理地址。

動態(tài)損耗均衡主要關注的是保證每次寫操作都會寫入到Flash中擦除（每次對一個塊寫入時需要先將原有的數(shù)據(jù)擦除掉才能寫入）次數(shù)最小的空閑塊中，從而避免某些塊被擦寫過多。

具體過程為：寫操作到來時，在空閑塊中找出擦除次數(shù)最小的塊，將其物理地址與收到的邏輯地址相對應，并存放在地址映射表中，同時將該邏輯地址原來對應的物理地址塊標記為垃圾塊，最后就將需要寫入的數(shù)據(jù)寫入到新的物理地址塊中。

2.基于PCM的雙重布隆濾波器（DLBF）算法[6]

上面介紹的基于?Flash?算法中提及了空閑塊、有效塊和垃圾塊的概念，與之相近的有冷地址和熱地址的概念，顧名思義，熱是指該地址被頻繁訪問，冷地址定義與之相反。

DLBF 算法借用 Bloom Filter（一種空間效率很高的隨機數(shù)據(jù)結構，它利用位數(shù)組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。）來識別讀、寫熱頁。

將布隆濾波器映射得到的布隆表的每一位擴展為一個計數(shù)器就能記錄每個地址被寫入的次數(shù)從而能根據(jù)閾值（閾值是會隨著時間改變的以此來提高識別的正確率）與計數(shù)器記錄的數(shù)據(jù)大小來判斷該地址是否為熱地址。以此來建立一個候選表（記錄現(xiàn)有的冷頁），每次寫操作到來時，先判斷這個地址是否已經(jīng)存在于地址映射表中，如果不在則先更新布隆表，然后判斷該地址是否為需要做交換的熱地址，如果是則將它與候選表中的冷地址做交換并更新地址映射表，如果不是熱地址則執(zhí)行正常的寫操作即可。

3.基于年齡的PCM損耗均衡算法[7]

算法的核心思想也是令熱地址與冷地址交換。但不需要維護一個候選表而是通過一個指針始終指向沒有被檢測到的所有頁面中最前的那個。總的來說就是利用指針的均勻移動使得所有地址都可以被均勻地使用，指針就像一個領隊員帶領著每一個寫入請求命令去到合適的地方。

4.基于PCM的動態(tài)損耗均衡算法[8]

同樣借助于布隆濾波器，根據(jù) EV（電子伏特）和寫入數(shù)量來選擇要交換的數(shù)據(jù)。動態(tài)管理布隆濾波器來提高所使用的濾波器的有效性（即通過動態(tài)更新寫數(shù)來避免計數(shù)器溢出），判斷地址是否為熱的閾值yes1動態(tài)變化的。

采用一種動態(tài)的冷熱列表（HCL）管理方法，試圖在 HCL 中保留盡可能長的熱邏輯地址（因此，減少交換開銷），同時從列表中刪除冷地址。

除此之外相關研究人員還從其他方向提出了實現(xiàn)損耗均衡的方法，例如：用新的緩存替換策略使回寫最小化以及避免不必要的寫，只寫實際改變的位單元[9]。通過在選擇替換頁時，優(yōu)先選擇一個未被修改過的頁面進行替換。盡可能讓頻繁修改的頁面長期保持在緩存中。方案中避免非必要的寫操作策略通過分頁技術和“讀—寫—讀”存儲頁差異識別方法實現(xiàn)。

對于上面動態(tài)損耗均衡算法中提及的垃圾數(shù)據(jù)處理，也有人提出了以最小化清理成本的損耗算法——CAT（cost?age?times）算法[10]，將 memory 細分為固定大小的塊。每一段有一個 segment header 來描述塊信息，該信息被用來加快清潔器加快選擇段進行清潔，當所有空閑段的數(shù)量低于一定閾值時，清潔器開始工作，在清理時，被清理段中的有效冷數(shù)據(jù)被遷移至專門存放冷數(shù)據(jù)的段中。同理有效熱數(shù)據(jù)被遷移至專門存放熱數(shù)據(jù)的段。這樣分別聚集，清理這些熱數(shù)據(jù)可以將遷移成本降到最低，因為被復制的有效數(shù)據(jù)量最少，而回收的垃圾量最大。CAT 算法的基本思想是最小化清理成本，給剛清理過的段更多時間來積累垃圾，以避免無用的遷移。

包括廣泛使用的布隆濾波器，關于它也有很多衍生的算法，例如在管理計數(shù)器時，因為不同地址會公用一個計數(shù)器，那么如果每次都將一個地址對應的所有計數(shù)器值都加一，這樣會增加將冷地址誤判為熱地址的概率。為了解決這個問題，除了動態(tài)調整判斷閾值，還可以令每次只有值最小的計數(shù)器加一。

識別冷熱地址的方式其實很簡單，就把地址被訪問的次數(shù)記錄下來即可，問題就在于我們無法事先得知誰會是熱地址，所以在給每個地址分配計數(shù)器時預留的空間都必須按照熱地址的寫入次數(shù)賦予，但實際上熱地址所占整個地址的比例不會很大，這樣就會造成很大的空間資源浪費，而往往我們需要集成密度大的電路這樣的存儲開銷是有些不合理的，所以才產生了各種各樣以減少存儲開銷的算法。

總結

總的來說，損耗均衡算法都是通過各種方式在寫入操作會集中在一些地址的情況下通過監(jiān)督地址的寫入情況或者直接在物理地址層面進行額外的數(shù)據(jù)遷移的方式來使得經(jīng)常被訪問的地址塊的損耗分擔到那些不怎么經(jīng)常被訪問的塊。

均衡損耗算法雖然不能提升存儲器實際的壽命，但可以提高存儲器實際使用壽命，對于存儲器的應用具有很大的意義。

需要提醒的是本文著重于介紹各個算法的設計思路，沒有具體提及、分析其功耗，時間、空間復雜度，實際電路所占面積等，而這些在實際的整體系統(tǒng)設計中同樣是重要的。誠然我們要實現(xiàn)一些功能總是會以其他功能受到影響為代價，比如加入了均衡損耗模塊會使得寫操作的延時增加，降低了 CPU 訪問存儲器的速度但是延長了存儲器的壽命，所以還是回到介紹各個算法前說的，最好的算法一定是根據(jù)具體應用場景去設計、調整的。??

//?參考文獻?//

[1] Murugan M, Du D H C. Rejuvenator: A static wear leveling algorithm for NAND flash memory with minimized overhead[C]//2011 IEEE 27th Symposium on Mass Storage Systems and Technologies (MSST). IEEE, 2011: 1-12.

[2] Qureshi M K, Karidis J, Franceschini M, et al. Enhancing lifetime and security of PCM-based main memory with start-gap wear leveling[C]//2009 42nd Annual IEEE/ACM international symposium on microarchitecture (MICRO). IEEE, 2009: 14-23.

[3] Grossi A, Vianello E, Sabry M M, et al. Resistive RAM endurance: Array-level characterization and correction techniques targeting deep learning applications[J]. IEEE Transactions on Electron Devices, 2019, 66(3): 1281-1288.

[4] Chang Y H, Hsieh J W, Kuo T W. Endurance enhancement of flash-memory storage systems: An efficient static wear leveling design[C]//Proceedings of the 44th annual Design Automation Conference. 2007: 212-217.

[5] 徐書韜.基于硬件損耗均衡算法的片上Nor Flash控制器設計[D].杭州:浙江大學，2017.

[6] Niu N, Fu F, Yang B, et al. DLBF: A low overhead wear leveling algorithm for embedded systems with hybrid memory[J].Microelectronics Reliability, 2021, 123: 114154.

[7] Chen C H, Hsiu P C, Kuo T W, et al. Age-based PCM wear leveling with nearly zero search cost[C]//Proceedings of the 49th Annual Design Automation Conference. 2012: 453-458.

[8] Yun J, Lee S, Yoo S. Dynamic wear leveling for phase-change memories with endurance variations[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014, 23(9): 1604-1615.

[9] Ferreira A P, Zhou M, Bock S, et al. Increasing PCM main memory lifetime[C]//2010 Design, Automation & Test in Europe Conference & Exhibition (DATE 2010). IEEE, 2010: 914-919.

[10] Chiang M L, Chang R C. Cleaning policies in mobile computers using flash memory[J]. Journal of Systems and Software, 1999, 48(3): 213-231.

編輯：黃飛

?