NANDフラッシュメモリのウェアレベリングアルゴリズムの最適化

0. はじめに

現在、ノートパソコン、スマートフォン、ソリッドステートドライブなどの新しい電子機器には、NANDフラッシュメモリが搭載されています。独自のストレージ方式と超高安定性および信頼性を備えたNANDフラッシュメモリは、ますます多くのメーカーに支持されています。NANDフラッシュメモリを搭載したソリッドステートドライブは、多くの利点があるため、従来の機械式ハードドライブに徐々に取って代わりつつあります[1]。

NANDフラッシュメモリをストレージデバイスとして使用するソリッドステートドライブは、機械式ハードディスクのような複雑で洗練された構造を使用していません。データの読み取りにシークタイムが不要で、書き込み方法も独自のため、比較的高速な読み取りおよび書き込み速度を実現できます。また、NANDフラッシュメモリはサイズが小さく、インターフェイスの用途が広く、さまざまな構造形式に適応できるため、携帯電話やラップトップなどの精密機器で使用できます[2]。ただし、NANDフラッシュメモリは電子管を使用してデータを保存するため、データの書き込みと消去を繰り返すと簡単に破損する可能性があります。その物理ブロックは、数千回の消去および書き込み操作にしか耐えられません。NANDフラッシュメモリを広く使用するには、フラッシュメモリの耐用年数を延ばすために、各物理ブロックの摩耗を平均化する適切なメカニズム、つまりウェアレベリングメカニズムを採用する必要があります。

[[228943]]

1994年、PCMCIA（Personal Computer Memory Card International Association）は、フラッシュ変換層（FTL）の概念を提案しました。NANDフラッシュにFATファイルシステムを使用すると、コントローラはNANDフラッシュを管理して、上位層アプリケーションが呼び出す論理FATファイルシステムを確立します。同時に、ウェアレベリングも効率的に実行できます[3]。フラッシュメモリのウェアレベリングを実装するためのアルゴリズムは、動的ウェアレベリングと静的ウェアレベリングの2種類に分けられます[4]。Banら[3]は、静的ウェアレベリングアルゴリズムのトリガーメカニズムを研究し、決定論的トリガーメカニズムとランダムトリガーメカニズムの2つのトリガーメカニズムを提案しました。Yared Hailu Gudetaら[5]は確率ベースの静的ウェアレベリングアルゴリズムを提案した。各状態では、標準偏差を使用して摩耗平均分布を計算し、しきい値を超えているかどうかを判断します。しきい値を超えた場合は、フラッシュメモリ内のホットブロックとコールドブロックを交換することで、すべてのブロックで摩耗バランスが維持されます。Leeら[6]は、システムの初期化時にフラッシュストレージスペースをいくつかのグループに分割し、最初の更新から各グループの消去と書き込みの数を記録する静的ウェアレベリングアルゴリズムを研究しました。ウェアレベリングのトリガー条件に達すると、平均よりも消去と書き込みの数が多いグループとグループ内の物理ブロックがカウントされ、これらのブロックのデータが空のブロックに移動され、アドレスマッピングテーブルが更新されます。

Xing Chunbo [7]はハイブリッドウェアレベリングアルゴリズム（HWL）を提案した。この方法でも、システム初期化中にフラッシュメモリ空間をブロックに分割する。各ブロックの消去および書き込み時間は、ストレージ空間の別のバイトによって記録され、すべてのブロックの消去および書き込みステータスを維持するために配列が使用されます。このアルゴリズムは、各システム更新サイクルで各ブロックの消去および書き込みステータスをカウントします。HWLアルゴリズムは、最も広く使用されているアルゴリズムの1つです。この論文もこのアルゴリズムに基づいて改良されています。

本論文では、フラッシュメモリの物理ブロックが使用中に消去および書き込みされる回数に応じてフラッシュメモリのデータブロックを分類し、対応する判断基準を示します。同時に、ウェアレベリングアルゴリズムと密接に関連するしきい値の概念を紹介します。ウェアレベリングアルゴリズムがストレージ需要に応じて調整できないという欠陥を狙って、データブロックが消去および書き込みされる回数の標準偏差に応じてしきい値を動的に調整するアルゴリズムを示します。従来の動的ウェアレベリングアルゴリズムと静的ウェアレベリングアルゴリズムを組み合わせて、ウェアレベリングアルゴリズムの評価基準を示し、静的ウェアレベリングアルゴリズムと動的ウェアレベリングアルゴリズムを組み合わせて新しいウェアレベリングアルゴリズムを設計します。需要に応じて、ウェアレベリングアルゴリズムの効果を評価するためのテスト実験を設計し、ウェアレベリングアルゴリズムの効果を実験的にテストします。実験結果は、本論文で提案された改良アルゴリズムがフラッシュメモリの消去と書き込みの不均衡を減らすのに良い効果を持っていることを示しています。

1 NANDフラッシュウェアレベリングのメカニズムと戦略

1.1 NANDフラッシュの動作原理

NANDは、より低い消費量、より良いパフォーマンスを持つ製品を追求し続けるため、NANDは非常に魅力的であることが証明されています。対応するマルチレベルのMLC制御法は、シングルレベルのセルSLC制御方法を改善しますマルチレベルセルMLC制御方法フラッシュメモリの寿命、摩耗レベリングメカニズムはファイルシステムで使用する必要があります。

1.2 損失平準化評価指標

ウェアレベリング[8]とは、ソリッドステートストレージデバイスの耐用年数を延ばすために使用されるプロセスを指します。フラッシュメモリのウェアレベリング技術の設計目標は、フラッシュメモリ内のすべてのブロックの消去回数の合計を最小限に抑え、フラッシュメモリ内の各ブロックの消去回数を可能な限り一定または一定の範囲内にすることです。統計的知識によれば、平均値はサンプルの平均レベルを表し、標準偏差はデータセットの分散度合いを反映することが分かっています。この設計目標に基づいて、フラッシュメモリのウェアレベリングを測定するための2つの指標、平均消去回数と消去回数の標準偏差（Deviation、略してDev）が提案されています。

式（１）及び（２）において、E(i)はi番目のブロックの消去回数を表し、nはフラッシュメモリ内のブロックの総数を表す。

上記の要因を組み合わせると、フラッシュメモリシステムのウェアレベリング戦略が優れているほど、ホットデータとコールドデータの移行をできるだけ多く行うことができ、物理ブロック全体の消去回数の平均値が小さいほど、フラッシュメモリの耐用年数が長くなることがわかります。また、物理ブロックの消去回数の標準偏差が小さいほど、各物理ブロックの消去回数が平均消去回数から逸脱する回数が少なくなり、ウェアレベリングメカニズムの実行効果が高くなります。逆に、ウェアレベリングメカニズムの実行効果は低くなります。

1.3 ウェアレベリング戦略

1) 動的損失平準化戦略

動的ウェアレベリングアルゴリズム[9]の主な原理は、まずすべてのフラッシュメモリの物理ブロックを動的に維持されるテーブルにリンクし、各物理ブロックの消去回数をテーブル内で大きいものから小さいものの順に並べ替えることです。データが更新されるときは、テーブルの上部にある物理ブロック、つまり消去回数が最も少ない物理ブロックに書き込まれ、次に消去回数で並べ替えられる必要があります。この方法によれば、データは常に消去回数が最も少ない物理ブロックに書き込まれるため、フラッシュメモリの各ブロックの摩耗状態は同じになります。

2) 静的損失平準化戦略

静的な摩耗アルゴリズムは、動的摩耗アルゴリズムが常により少ない時代のデータを作成することを考慮して、より少ない更新を伴う物理的なブロックを占めることを考慮して改善されますアルゴリズムは、コールドデータに焦点を当て、消去および書き込みのしきい値を事前に設定し、統計的に頻度を取得する方法を使用し、コールドデータブロックをスクリーニングし、その後、より熱いデータブロックを使用して、より多くのデータブロックを使用して、より多くのデータブロックを使用して、物理的なブロックに移動します。フラッシュメモリは比較的バランスが取れており、静的バランスメカニズムの連続トリガーにより、ホットデータブロックの消去時間が非常にゆっくりと増加し、コールドデータブロックの消去時間がある程度増加するため、非常に効果的な摩耗レベリングアルゴリズムです。

2 静的バランスアルゴリズムの設計

本論文の静的ウェアレベリングアルゴリズムは、既存の動的ウェアレベリングアルゴリズムと静的アルゴリズムを組み合わせて、より完全なアルゴリズムフローを設計する。静的ウェアレベリングアルゴリズムの基本的な設計原理は、前回の記事で紹介した。この目的のために、最大消去回数をNmax、最小消去回数をNmin、両者の差をThと定義する。研究対象となる問題[10]は次のように表現される。

ここで、式（４）のThは、本論文で検討した静的ウェアレベリングアルゴリズムの核心であり、物理ブロックの消去回数の上限と下限があまり変わらないように適切な閾値Thを選択することである。同時に、平均値と標準偏差は可能な限り小さくなければならない。

2.1 トリガー条件の最適化

決定論的トリガーの難しさは、適切なシステム更新回数を見つけることが困難であり、ランダムトリガーはシステム更新頻度が高い場合にのみ使用される[11]。

この目的のために、本論文では、決定論的トリガーとランダムトリガーを組み合わせて、トリガーメカニズムを動的に選択できるアルゴリズムを設計します。このアルゴリズムは、システムの更新頻度をカウントします。更新頻度が高い場合はランダムトリガー条件が選択され、更新頻度が低い場合は決定論的トリガー条件が選択されます。損失平準化メカニズムの評価基準を参照すると、システム更新回数の平均が判断条件として選択されます。フローチャートを図1に示します。

図1 最適化されたトリガー条件フローチャート

図1 最適なトリガー条件のフローチャート

2.2 しきい値はデータブロックの状態を決定します

データ ブロックの消耗状態は、ブロックが消去および書き込みされた回数と消去されたデータの総数の割合によって決まります。

式中、wi はブロックの摩耗度、ei は今回のシステム更新でブロックが消去および書き込みされた回数、a0 は今回のシステム更新でブロックが消去および書き込みされた合計回数を表します。

ウェアレベリングプロセス中、ウェア情報テーブルが維持され、各物理ブロックに 1 バイトのスペースが割り当てられ、ウェアステータス wi が記録されます。wi がしきい値 whigh に達すると、ブロックはホット データ ブロックとして定義されます。同様に、wi がしきい値 wlow より低い場合、ブロックはコールド データ ブロックとして定義されます。

2.3 アルゴリズムフロー

上記の結論から、ウェアレベリングの問題を解決するには、パフォーマンスへの影響を最小限に抑える条件下で、各データブロック内の消去タスクと書き込みタスクを均等に分散する必要があることがわかります[12]。この問題を解決するために、本稿では、以前の動的アルゴリズムと静的アルゴリズムの研究に基づいて、動的アルゴリズムと静的アルゴリズムを組み合わせたNAND FLASHフラッシュメモリウェアレベリングアルゴリズムを設計します。

完全な静的レベリングプロセスは次のとおりです。システムの更新操作が最初に開始されます。ブロックは、ホットデータブロックの有効なデータを摩耗状態に移動し、コールドデータブロックに移動します。特定の値による消去の平均数は、ホットデータブロックとしてマークされ、このようにして、ホットデータブロックは新しい物理ブロックに継続的に移動し、いくつかのブロックでのみ消去されます。

図2 完全な損失バランスフローチャート1

図2 完全バランス損失フロー図Ⅰ

図3 完全な損失バランスフローチャート2

図3 完全バランス損失フロー図Ⅱ

3 シミュレーションテスト

3.1 実験プラットフォームの構築

本論文で設計したウェアレベリングアルゴリズムの効果をテストするために、SSD Sim を利用してテストプラットフォームを構築しました。このプラットフォームは、通常のコンピュータプラットフォーム上で NAND フラッシュメモリのストレージ状態をシミュレートできます。ユーザーは、SSD Sim ソフトウェアでストレージ容量、ストレージチャネル、フラッシュブロックサイズなどのパラメータを設定できます。ユーザーのニーズに応じて、フラッシュハードウェアのサポートなしで NAND フラッシュメモリの使用をシミュレートできます。

ウェアレベリングアルゴリズムの効果を直接比較するために、本稿では、それぞれに4つのフラッシュメモリチップを割り当て、並列に接続した2つのNANDフラッシュメモリを設計した。フラッシュメモリ1は、従来の静的ウェアレベリングアルゴリズム[13]（HWLアルゴリズム）を使用し、フラッシュメモリ2は、本稿で改良したウェアレベリングアルゴリズムを使用する。両方のフラッシュメモリは、同じ1×106のデータ書き込み要求を書き込みます。2つのフラッシュメモリのその他の詳細な構成を表1に示します。

表1 フラッシュメモリ構成表

表1 フラッシュ構成表

3.2 テスト内容と結果の分析

このセクションでは、改善前と改善後のウェア レベリング アルゴリズムの効果を比較します。主に、2 つの摩耗状態しきい値 w、システム更新回数 n、静的摩耗サイクル M がフラッシュ ストレージのウェア レベリング パフォーマンスに与える影響を比較します。評価指標は、サイクル内の消去回数の標準偏差で表されます。

1) 摩耗状態しきい値の上限がフラッシュストレージの摩耗平準化性能に与える影響を調べるために、HWLアルゴリズムでw=1.2%とw=0.8%の2つのケースにおいて、書き込み要求の増加に伴う物理ブロック消去数の標準偏差の変化を記録します。

図4と図5から、HWLアルゴリズムと比較して、改良された静的ウェアレベリングアルゴリズムの方がウェアレベリング効果が優れていることがわかります。書き込み要求が増加し続けると、両方のアルゴリズムの標準偏差は着実に増加します。これは、書き込み要求が増加し続けると、標準偏差の増加が静的ウェアレベリングメカニズムの制御下で安定する傾向があることを示しています。安定する傾向がある場合、改良された消去時間と書き込み時間の標準偏差はHWLアルゴリズムよりも約16.4％小さくなり、改良されたしきい値によりウェアレベリング効果が向上することがわかります。

2) 物理ブロックの消去および書き込み回数の標準偏差曲線により、改善前後の静的ウェアレベリングサイクルが静的ウェアレベリング効果に与える影響を比較します。HWLアルゴリズムは固定サイクルを使用し、改善されたアルゴリズムは可変サイクルを使用します。図から、改善された静的ウェアレベリングアルゴリズムが大きな効果を発揮していることがはっきりとわかります。書き込み要求が2.2×105回に達すると、両方の消去および書き込み回数の標準偏差は***に達します。ただし、HWLアルゴリズムの消去および書き込み回数の標準偏差は増加し続け、書き込み要求が7.4×105に達するまで下降傾向にあります。ただし、改善後の消去および書き込み回数の標準偏差は減少し始め、最終的に約10×105に安定します。改善されたアルゴリズムは動的サイクル選択方式を採用しているため、HWLの固定サイクルと比較して、フラッシュメモリの静的ウェアレベリングのニーズをよりよく満たすことができます。

図4 摩耗状態閾値の上限がフラッシュストレージの摩耗平準化性能に与える影響

図4 摩耗状態閾値がフラッシュの摩耗均等化性能に与える影響

図5 静的損失平準化サイクルが静的損失平準化効果に与える影響の比較分析

図5 静的損失均等化サイクルが静的損失均等化に与える影響の比較と分析

同時に、本論文では比較と観察のために M = 10 の別の変化曲線を選択し、静的損失とバランス調整期間を比較的短く設定しても、損失バランス調整の効果は依然として理想的ではないことを発見しました。

4 結論

一般的な HWL ウェア レベリング アルゴリズムを最適化しました。データ ブロックのホット属性とコールド属性を再定義し、ホット データとコールド データの判定条件として高しきい値と低しきい値を使用し、トリガー メカニズムを最適化し、既存の静的ウェア レベリング戦略と動的ウェア レベリング戦略を組み合わせた最適化戦略を最適化しました。比較テストは、SSD Sim ソフトウェアによって完了しました。実験により、改善されたウェア レベリング アルゴリズムによって物理ブロック消去数の標準偏差が効果的に減少し、ウェア レベリング効果が向上することが証明されました。