前言

新型非易失存儲器正在逐漸成熟，有望在未來成為工作存儲器。然而，在工業實踐中，我們發現一些非易失存儲器，包含阻變隨機存儲器（RRAM）、相變隨機存儲器（PCM）和閃存（Flash）等在使用時會面臨使用耐久性有限的問題，即對于一個地址的寫入次數是有限的，而實際對存儲器進行寫操作時，往往會很頻繁的訪問部分地址，一旦存儲器任何部分的寫入次數超過了耐久極限，整個器件就會被認為無法工作。

因此，需要設計一些算法使得能對整個存儲器做均衡的訪問，而不是僅僅去對幾個特定的區域持續寫入，將對某些塊的操作分布到整片存儲器上，實現各塊寫入的平衡，這類算法就稱為損耗均衡（wear leveling）算法。

硬件損耗均衡算法簡介

硬件損耗均衡算法大致可以分為靜態和動態損耗均衡。

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

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

與動態方法相比靜態方法優勢在于空間開銷小，不需要考慮具體程序的動態運行也能達到延長存儲器壽命的目的，但正因為于此靜態的方法不能充分的挖掘存儲器的生命潛力。

而動態方法借助記錄每個地址被寫入的次數、建立地址映射表、定期清理垃圾數據等方式，雖然存儲開銷相比靜態方法增加了但可以獲得更好地延長存儲器壽命的結果。當然最好的均衡損耗算法一定是根據具體的應用場景去相應調整的，沒有最好的算法只有最適合的算法。

下面將先介紹一些靜態損耗均衡算法：

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

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

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

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

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

由于 CPU 在訪問寄存器時，無論是存取數據還是存取指令，都趨于聚集在一片區域——局部性原理，可以看出僅依靠這樣相鄰位的移動，會將一個大量寫入的行移動到另一個大量寫入的行，這可能導致早期的磨損。

于是引入靜態地址隨機化，將原本連續的地址重映射為彼此間隔很大的新地址。

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

圖2：4位地址隨機化

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

圖3：Start-Gap架構

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

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

3.?基于 Flash 的 SW Leveler 算法

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

具體為：觸發清潔器對選定的區塊進行垃圾收集，讓 SW 均衡器與塊擦除表(BET，建立的目的是記住哪個塊在預定的時間范圍內被擦除，以便找到冷數據的地址。)相關聯，以記住在選定的時間段內哪個塊被擦除了。

當 SW 均衡器運行時，它要么重置 BET，要么撿起一個至今未被擦除的塊（基于BET信息），并觸發清潔器對該塊進行垃圾收集。區塊的選擇過程必須在有限的時間內以有效的方式完成。每當一個區塊被擦除時，BET 同步更新。

4.?基于 Flash 的 Rejuvenator 算法

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

根據區塊當前的擦除次數將其分為不同的組。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.基于PCM的動態損耗均衡算法

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

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

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

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

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

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

總結

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

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

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

審核編輯：劉清