(57)【要約】【課題】メモリデバイスにおいて複数のブロックを含むメモリを管理する方法を得る。【解決手段】メモリの各ブロックに関して、ブロックが何回消去されたか、そして少なくとも一つの他のブロックが何回消去されたかの関数である数を計算する。それらの数を、メモリを含むメモリ・デバイス内に記憶し、ブロックが消去されるときに必要に応じて数を更新する。そして、消去すべきブロックをそれらの数に応じて選択する。各ブロックの関数がブロックの相対等級であることが好ましい。【選択図】図１
2009506389.tif 000002
【特許請求の範囲】
【請求項１】
メモリ・デバイスの、複数のブロックを含むメモリを管理するための方法であって、各ブロックに関して、
（ａ）前記各ブロックが何回消去されたか、そして少なくとも一つの他のブロックが何回消去されたかの関数である数を計算するステップ、そして
（ｂ）前記メモリ・デバイス内に前記数を記憶するステップからなる、方法。
【請求項２】
さらに、各ブロックに関して、
（ｃ）前記各ブロックが消去されるときはいつでも前記数を更新するステップからなる、請求項１の方法。
【請求項３】
さらに、各ブロックに関して、
（ｃ）前記少なくとも一つの他のブロックの一つが消去されるときはいつでも前記数を更新するステップからなる、請求項１の方法。
【請求項４】
さらに、
（ｃ）前記数に少なくとも部分的に従って、消去すべき少なくとも一つのブロックを選択するステップからなる、請求項１の方法。
【請求項５】
前記記憶が、前記ブロックの少なくとも一つの各々に関して、前記各ブロック内に前記数を記憶することを含むステップによって実行される、請求項１の方法。
【請求項６】
前記記憶が、前記ブロックの少なくとも一つの各々に関して、前記各ブロック外に前記数を記憶することを含むステップによって実行される、請求項１の方法。
【請求項７】
各ブロックに関して、前記関数が前記各ブロックの相対等級である、請求項１の方法。
【請求項８】
前記ブロックの少なくとも一つの各々に関して、前記相対等級が、前記各ブロックの消去計数と、一つの他のブロックの消去計数との間の相違に依存する、請求項７の方法。
【請求項９】
前記一つの他のブロックが、前記各ブロックの隣である、請求項８の方法。
【請求項１０】
前記ブロックの少なくとも一つの各々に関して、前記相対等級が、前記各ブロックの消去計数と、少なくとも二つの他のブロックの平均消去計数との間の相違に依存する、請求項７の方法。
【請求項１１】
前記少なくとも二つの他のブロックの少なくとも一つが、前記各ブロックの隣である、請求項１０の方法。
【請求項１２】
前記計算が、各ブロックに関して、ブロック毎の消去回数の最大許容数を記憶するのに不十分なビット数において、前記関数を打ち切ることを含む、請求項１の方法。
【請求項１３】
（ａ）複数のブロックを含むメモリ、そして
（ｂ）コントローラからなる、メモリ・デバイスであって、前記コントローラが、前記ブロックの各々に関して、
（i）前記各ブロックが何回消去されたか、そして少なくとも一つの他の前記ブロックが何回消去されたかの関数である数を計算すること、そして
（ii）前記メモリ・デバイス内に前記数を記憶することを含むステップによって前記メモリを管理する、メモリ・デバイス。
【請求項１４】
前記メモリがフラッシュメモリである、請求項１３のメモリ・デバイス。
【請求項１５】
メモリ・デバイスの、複数のブロックを含むメモリを管理するためのコンピュータ読み取り可能なコードを持つコンピュータ読み取り可能な記憶メディアであって、前記コンピュータ読み取り可能な記憶メディア上に具現化された前記コンピュータ読み取り可能なコードが、
（ａ）前記各ブロックが何回消去されたか、そして少なくとも一つの他の前記ブロックが何回消去されたかの関数である数を各ブロックに関して計算するためのプログラム・コード、そして
（ｂ）各ブロックに関して前記数を前記メモリ・デバイス内に記憶するためのプログラム・コードからなる、コンピュータ読み取り可能な記憶メディア。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はフラッシュメモリに関し、より詳しくは、メモリ内のブロックの損耗平準化を達成することによって、フラッシュメモリの実用寿命を延長させるための方法に関する。
【背景技術】
【０００２】
フラッシュメモリ・デバイスは、長年既知である。フラッシュデバイスは、ＰＤＡや携帯電話内でのデータ記憶のための、ＭＰ３プレーヤ内でのオーディオ・ファイル記憶のための、そして他の多くのアプリケーションのための、高度に信頼性が高いソリッドステート・ディスクを製造するために使用される。データ記憶のためにフラッシュメモリを使用する製品を設計する場合に考慮しなければならない局面の一つは、フラッシュ・ブロックの消去および書き換え回数に制限があることである。例えば、製造業者は、現在購入可能なＮＡＮＤフラッシュ・デバイスが、典型的に、１ブロックにつき最高１００，０００回の書き込みあるいは消去をサポートする、と明記している。また、１セル毎に２ビットを記憶する、より高密度なマルチレベル・セル（ＭＬＣ）ＮＡＮＤフラッシュデバイスが、典型的に、１ブロックにつき最高１０，０００回の書き込みあるいは消去をサポートする、と明記している。製造業者は、１ブロックがその明記された書き込みあるいは消去回数限度に到達した後のデバイスの、その仕様に沿う作動を保証していない。したがって、メモリのブロックが、不必要に、この限度に到達する状況を回避するよう配慮しなければならない。
【０００３】
記憶ユニットを示す用語は、フラッシュメモリ販売業者間での統一ができていないので、本開示の目的のために、まず、ここに用語を定義する。「ブロック」は、単一オペレーションで消去できる最も小さな記憶ユニットであり、「ページ」は、単一オペレーションで書き込み（すなわち「プログラム」）が可能な、最も小さな記憶ユニットである。
【０００４】
もし、非均一な損耗を回避するための対策がなされないなら、メモリ・システムの通常オペレーションは、ブロックの個体群全体に渡る、そのような非均一な損耗をもたらし得る。これは、ほとんどのソフトウェア・システムが、記憶アドレス空間全体に渡って、不均一な様式で書き込みを行う傾向があるためである。この傾向は、マイクロソフトＦＡＴ等のファイル・システムが記憶システム内に維持される場合、さらに大きい。そのような場合、典型的に、ファイル・システムによって、記憶システム・アドレス空間の最初の部分にいくつかの管理データが保管される。これらのデータは、ファイル・アロケーション・テーブルの一つ以上のコピー、または記憶ボリュームのルート・ディレクトリである。これらの管理データ領域に書き込む頻度は、他の記憶領域に比べ、非常に高いため、特別な対策がなされない限り、それらを含むブロックは、非常に大きな、書き込みあるいは消去回数に到達し、他のブロックよりも早く寿命に至る。この場合、記憶ボリュームは、ほとんどのブロックが依然として使用可能なのに、既に寿命に到達した多少の危険なブロックが存在するために、ボリューム全体としては、その末期に既に到達してしまったこととなる。
【０００５】
上記のことから、書き込みあるいは消去回数を、デバイスのブロック全体に渡って等しくすべきであるということが明らかである。すべてのブロックの、書き込みあるいは消去の経歴がほぼ類似するなら、記憶システムの寿命は全体として最大になる。
【０００６】
上記の、フラッシュメモリの損耗を平準化するという課題に対しては、従来の技術において多くの解決策が開示されている。いくつかの例を、以下に列挙する。
レーフグレン氏らへの米国特許公報第６，２３０，２３３号、
ウェルズ氏への米国特許公報第５，３４１，３３９号、
ジョウ氏らへの米国特許公報第５，５６８，４２３号、
アサー氏らへの米国特許公報第５，３８８，０８３号、
ハラリ氏への米国特許公報第５，７１２，８１９号、
ハラリ氏への米国特許公報第６，５７０，７９０号、
ハラリ氏への米国特許公報第５，９６３，４８０号、
チャン氏らへの米国特許公報第６，８３１，８６５号。
上記の特許のすべては、参照によって、すべての目的のために完全に本文に記述したかのように、含むものとする。
【０００７】
上記すべての従来の技術に共通することは、すべてが、各ブロックが経験する消去回数を計数することに基づいていることである。本開示の説明における「消去計数」は、フラッシュメモリのブロックが、その使用歴に渡って、消去された回数を表す数である。消去計数は、記憶システム内に記憶され、システム・オペレーション中に管理維持される。ブロックを消去するときはいつも、その消去計数が１だけ増加される。上記の解決策のいくつかは、ブロック内にブロックの消去計数を記憶する。いくつかは、フラッシュメモリ内の、特別に割り当てたロケーション内にある中央テーブル内に、すべてのブロックのすべての消去計数を記憶する。さらに、他のものは、不揮発性メモリ内に消去計数を記憶することに加えて、フラッシュメモリを管理するコントローラのＲＡＭ内に消去計数を記憶する。しかし、すべてのケースにおいて、ブロックで実行される消去回数は、記憶され、損耗平準化のゴールを達成するために使用される。ブロックの消去計数を見ることによって、フラッシュ管理ソフトウェアは、最も使用されたブロックがどれか、また最も使用されないブロックがどれかを検出できる。
【０００８】
この消去計数の情報を、損耗平準化を達成するために利用する方法には、二つの主要なレベルがある。最も単純なレベルは、使用のために新しいブロックを割り当てる必要があるときに作動する。フラッシュ管理システムは、利用可能な空きブロックのいずれを、割り当てブロックとするのかを決定しなければならない。典型的に、決定アルゴリズムは、消去回数が大きいブロックよりも、消去回数が小さいブロックを好むため、計数の広がりは小さくなり、また、ブロックの損耗は、より均一になる。損耗平準化のこのレベルは、本文においては「動的損耗平準化」と呼ぶ。より上級なレベルにおいては、いくつかのファイルは、性質が静的であり、典型的に、一度書き込まれるとほとんど更新あるいは書き換えされないという事実を考慮する。このことは、ほとんどのオペレーティングシステム・コード・ファイルまたは、例えばワープロ等のソフトウェア・アプリケーションにおいて真実である。特別な対策を施すことがなければ、動的損耗平準化アルゴリズムが実行する損耗平準化は、静的ファイルが使用するブロックに影響を及ぼすことはない。それは、それらのブロックが、システム・オペレーションの正規のコースで自由になることが決してないからである。このことは、それらのブロックが、非常に小さい消去計数のまま留まり、実際、メモリ・システムの寿命が、対策を施した場合よりも短いことを意味する。したがって、上級の損耗平準化解決策は、たとえ静的ファイルを書き換えないとしても臨時にこれらのファイルを強制的に他のブロックへ移動させることによって、この課題を処理する。これは、静的ファイルのブロックが、記憶割り当てに参加する頻繁に割り当てられるブロックのプールへ再び入ることを可能にする。これによって、消去計数の全体的な平準化、そして記憶システムの寿命は改善する。このレベルの損耗平準化を、本文では「静的損耗平準化」と呼ぶ。追加の修飾がない用語「損耗平準化」は、動的および静的損耗平準化の両方を意味する。
【０００９】
上記従来の技術による参照例は、損耗平準化における所望の結果を達成する多くのアルゴリズムを開示しているが、すべてのこれらのアルゴリズムは、ブロックの消去計数を知ることに依存している。
【００１０】
この一般的なルールへの例外は、バン氏への米国特許公報第６，７３２，２２１号である。バン氏は、ブロック毎の消去回数を数えることに依存しない、フラッシュメモリ内の損耗平準化を達成するための方法を開示している。代わりに、バン氏は、割り当てて使用するブロックを選択するのに統計的方法を用いる。したがって、長期的に、システムがブロックを多数回消去した後は、すべてのブロックの損耗は、高い確率で均一に近い。しかしながら、バン氏は、比較的に小さな消去回数のみで、短期的に損耗平準化の均一性を達成することを保証していない。したがって、バン氏の解決策は、書き込みあるいは消去回数限度が非常に小さい、例えば１，０００回等のフラッシュデバイスに対してはうまく機能しない。
【００１１】
ブロック毎の消去回数を数えることに依存するすべての従来の技術による解決策では、各ブロックの計数を記憶する必要がある。計数を、該当する同じブロック内に保持するか、または他のロケーション内に保持するかに関係なく、計数に対して記憶域を割り当てなければならない。１００，０００回のフラッシュデバイスに対しては、計数毎に少なくとも１７ビットが必要であり、また１０，０００回のフラッシュデバイスに対しては、計数毎に少なくとも１４ビットが必要である。これは、場合によっては、その目的に確保するには、あまりに大きな領域である。例えば、ＮＡＮＤフラッシュ・デバイスを管理するためのフラッシュ管理システムを想像すると、５１２バイトのユーザ・データの各ページに、システムの制御情報を記憶するための１６バイトの「追加領域」が付随することになる。消去計数は、ブロック全体の属性であり、単一ページのものではないため、典型的に、そのような消去計数は、ブロック内の単に１ページのみに、通常第一ページに記憶される。こうして少なくとも、第一のページの追加領域の（１００，０００回デバイスを仮定して）３バイトが、ブロックの消去計数を記憶するために割り当てられるべきである。しかし、これらの追加領域バイトは、フラッシュ管理ソフトウェアが効果的な管理に必要とする他の管理情報を記憶するために、またはページ内に記憶したデータに対するエラー補正スキームのパリティ・ビットのために必要なこともある。
【００１２】
同様に、消去計数を中央テーブル内に保管する場合も、必要となるスペースの量はあまりに大きい。フラッシュ・ディスクが、４つの１Ｇｂｉｔフラッシュデバイスを含み、各々が、３２キロバイトの４，０９６ブロックを持ち、そして各々が、３バイトの消去計数を必要とすると、テーブルのサイズは、４ｘ４，０９６ｘ３＝４９，１５２バイトである。これは、バックアップのためのマルチプルを含む前でさえも、ブロックのサイズを超えるものである。より重要なことは、性能的な理由で、ＲＡＭ内に消去計数テーブルのコピーを保管することが有用であるが、上記の量はあまりに大きく、一般的に、フラッシュコントローラ内のＲＡＭの、利用可能な量を超えている。
【００１３】
したがって、一方で、ブロック個体群全体に渡って均一な消去回数を提供し、他方で、消去回数を数えてそれらの数を記憶する従来の技術による方法よりも少ないメモリを消費する、フラッシュメモリ・ブロックの損耗平準化を達成するための方法に対する必要性が広く認識される。そして、そのような方法を得ることは非常に有利である。
【発明の開示】
【課題を解決するための手段】
【００１４】
本発明によれば、メモリ・デバイスの、複数のブロックを含むメモリを管理するための、次のステップを含む方法が提供される。各ブロックに関して、（ａ）各ブロックが何回消去されたか、そして少なくとも一つの他のブロックが何回消去されたかの関数である数を計算するステップ。そして（ｂ）その数をメモリ・デバイス内に記憶するステップ。
【００１５】
本発明によれば、次のものを含むメモリ・デバイスが提供される。（ａ）複数のブロックを含むメモリ。そして（ｂ）コントローラ。このコントローラは、各ブロックに関して、以下のことを含むステップによってメモリを管理する。（i）各ブロックが何回消去されたか、そして少なくとも一つの他のブロックが何回消去されたかの関数である数を計算すること。そして（ii）その数をメモリ・デバイス内に記憶すること。
【００１６】
本発明によれば、コンピュータ読み取り可能なコードを持つコンピュータ読み取り可能な記憶メディアが提供される。コンピュータ読み取り可能な記憶メディア上に具現化されたコンピュータ読み取り可能なコードは、メモリ・デバイスの、複数のブロックを含むメモリを管理するためのもので、次のものを含む。（ａ）各ブロックに関して、各ブロックが何回消去されたか、そして少なくとも一つの他のブロックが何回消去されたかの関数である数を計算するためのプログラム・コード。そして（ｂ）各ブロックに関して、その数をメモリ・デバイス内に記憶するためのプログラム・コード。
【００１７】
本発明の基本的な方法によって、メモリ・デバイスのメモリのブロック管理は、各ブロックに関して、ブロックが何回消去されたか、そして一つ以上の他のブロックが何回消去されたかの関数である数を計算すること、そしてそれらの数をメモリ・デバイス内に記憶することを含む。ブロックが消去されるときはいつでも、そして消去計数が関数の引数である他のブロックの一つが消去されるときはいつでも、各ブロックの数を更新することが好ましい。
【００１８】
この方法は、それらの数に少なくとも部分的に応じて、少なくとも一つの消去すべきブロックを選択するステップを含むことが好ましい。
【００１９】
各ブロックの数は、ブロックそれ自体内に、またはブロック外に記憶してもよい。
【００２０】
各ブロックに関して、関数がブロックの相対等級であることが好ましい。本文から明らかなように、ブロックの「相対等級」は、少なくとも一つの他のブロックが何回消去されたかに相対する、ブロックが何回消去されたかの目安である。下記の説明から明らかになることであるが、一般的に、相対等級を計算するのに、ブロックが消去された回数を明示的に数える必要はない。
【００２１】
本発明の一つの好適実施例においては、使用される特定な「相対等級」は、ブロックの少なくとも一つに関して、そのブロックの相対等級が、そのブロックの消去計数と、他の一つのブロックの消去計数との間の相違に依存する、というものである。この場合、他のブロックが、目標ブロックの隣であることが最も好ましい。
【００２２】
本発明のもう一つの好適実施例においては、使用される特定な「相対等級」は、ブロックの少なくとも一つに関して、そのブロックの相対等級が、そのブロックの消去計数と、少なくとも二つの他のブロックの平均消去計数との間の相違に依存する、というものである。他のブロックの少なくとも一つが、目標ブロックの隣であることが最も好ましい。
【００２３】
上記の数を計算することが、ブロック毎の消去回数の期待最大数を記憶するのに不十分なビット数において、各ブロックの関数を打ち切ることを含むことが好ましい。
【００２４】
本発明の範囲は、また、本発明の方法によって管理されるメモリ・デバイス、そして本発明の方法によってメモリを管理するためのコンピュータ読み取り可能なコードを具現化して載せたコンピュータ読み取り可能な記憶メディアを含む。
【発明を実施するための最良の形態】
【００２５】
本発明は、消去回数を明示的に数えることなく、フラッシュメモリ等のメモリ内の損耗平準化を達成する方法に関する。
【００２６】
本発明による損耗平準化の原理および作用は、図面とその説明文を参照することによって、よりよく理解できる。
【００２７】
本発明は、ブロックの消去回数を均一にするために、真に、各ブロックの正確な消去回数を知る必要はないという観察に基づいている。消去回数の均等性は、実際は、異なるブロックの回数間の関係の問題であるため、回数の絶対値を保持することに依存するのではなく、異なるブロックの回数間の関係のみを保持することに依存する対策によって、そのゴールを達成することは可能である。
【００２８】
そのような方法の例としては、各ブロックに関して、ブロックが消去された回数と、それに最も近い二つの隣接ブロックが消去された平均回数との間の相違に等しい値を保持することである。本文における「隣」は、ブロック・アドレスによって定義される。例えば、ブロックに連続的に番号を付した場合、ブロック１０の「隣」はブロック９および１１である。あるいは、より正式な記法では、ブロックｎに関わる数は、ＥＣ（ｎ）−（ＥＣ（ｎ−１）＋ＥＣ（ｎ＋１））/２である。この場合のＥＣ（ｉ）は、ブロックｉの消去計数である。分数は扱うのに便利でないため、値の定義を僅かに修正して、上記の表現の２倍とする。したがって、以下の説明において、値は、２ＥＣ（ｎ）−ＥＣ（ｎ−１）−ＥＣ（ｎ＋１）に等しい。
【００２９】
この値は、本文でブロックの「相対等級」と呼ぶものの単純な例である。相対等級の上記定義を、最初と最後のブロックにも適用できるようにするために、最初と最後のブロックは、相互に隣であると定義する。したがって、すべてのブロックは、最後のブロックを第一のブロックが追うよう循環的に順序づけられている、と見なす。であるから、（ブロックがゼロからＮ−１へ付番されていると仮定すると）第一のブロックの相対等級は、２ＥＣ（０）−ＥＣ（Ｎ−１）−ＥＣ（１）であり、最後のブロックの相対等級は、２ＥＣ（Ｎ−１）−ＥＣ（Ｎ−２）−ＥＣ（０）である。
【００３０】
各ブロックに関して記憶されるものは、ブロックの消去計数ではなく、ブロックの相対等級である。注目すべきことは、相対等級は消去計数から一意的に決定するものであるが、消去計数は相対等級から一意的に決定するものではないことである。これは、すべてのブロックが正確に同じ回数だけ消去された単純なケースを考察することによって、容易に証明できる。そのようなケースでは、すべてのブロックが、ゼロの相対等級を持つ。しかし、すべてのブロックの相対等級を知っていることで、消去計数を復元することが可能になるというわけではない。すべてのブロックは、消去回数１０を通過しているかも知れない、あるいは消去回数１，０００を通過しているかも知れない。どの整数Ｎに対しても、すべてのブロックが消去回数Ｎを通過するケースでは、正確に同じ相対等級に、すなわち、すべてのブロックに対してゼロの相対等級になる。
【００３１】
したがって、相対等級の概念は、消去計数の概念とは基本的に異なることが明らかである。ブロックの消去計数は、その個々のブロックの特性であるが、ブロックの相対等級は、その個々のブロックの特性ではなく、むしろ他のブロックとの比較によるそのブロックの相対的な状態を指し示すものである。ブロックの相対等級は、ブロック単独でのブロックの状態に関する絶対情報を全く含まない。これは、相対等級アプローチを、損耗平準化を達成するための基礎として消去計数を使用する従来の技術による解決策から、また、消去計数の一般化として「ブロックの特性」を使用するハラリ氏の米国特許公報第５，７１２，８１９号の一般的な解決策から区別する。
【００３２】
相対等級の概念は、各ブロックに関して、消去計数の２倍あるいはまたは消去計数の平方等の、ブロックの消去計数の関数を記憶することとは基本的に異なる。消去計数の平方は、確かに消去計数とは異なるが、ブロックの状態のみに依存するので、「ブロックの特性」の範囲内に入る。注目すべきことは、相対等級をブロックの特性と異なるものとする相対等級の重要な特徴が、相対等級から消去計数を復元できないということではなく、ブロックの相対等級が、単にその同じブロックの消去計数によって一意的に決定されないということである。例えば、各ブロックに関して、その消去計数の、整数Ｍによって除算した余りを記憶する場合、この値は、その余りから消去計数を復元することが不可能であっても、その余りがそのブロックの消去計数によって一意的に決定されるため、依然としてブロックの特性である。
【００３３】
消去計数ではなく相対等級を記憶することの一つの利点は、記憶スペースの節約である。損耗平準化が適切に作用して、ブロックの個体群に渡る消去回数をほぼ均一にするというゴールを達成した場合、相対等級の絶対値は小さい。これは、ブロック毎の使用ビットを少なくでき、不揮発性あるいは揮発性メモリのいずれにおいても、損耗平準化の目的に専念する全記憶量が、従来の技術による解決策よりも少ないことを意味する。ブロックに対する最大許容消去回数が１００，０００であるとしても、例えば、ブロックにつき僅かに８ビットの記憶を割り当てればよい。これは、消去計数を記憶する従来の技術によるシステムが使用する記憶量の半分よりも少ない。注目すべきことは、常に正の整数である消去計数と違って、相対等級は正または負のいずれでもよいことである。したがって、相対等級につき８ビットを使用すると、負数を表すための「２の補数」方法を使用すると仮定して、表示できる値の範囲は、−１２８と＋１２７との間になる。
【００３４】
すべてのブロックに対して相対等級を提供するとして、ブロックの損耗平準化を達成するために、これらの相対等級を消去計数の代わりに用いる。消去計数を使用する従来の技術に開示されている損耗平準化アルゴリズムの各々を、消去計数の代わりに相対等級を使用するよう、容易に適応させることができる。さて図面を参照するが、図１は、これを達成する方法の一例を示す。  図１は、空きブロックを使用に割り当てる必要があるときに（つまり、動的損耗平準化を実行するために）行うステップのフローチャートである。ステップ１００で、フラッシュ管理システムから、空きブロックを使用に割り当てるための要求が受信される。ステップ１１０で、すべての空きブロックの相対等級がスキャンされて、最低相対等級を持つ空きブロックを見つける。複数の空きブロックが同じ最小値を持つ場合は、それらのブロックの一つを任意に選択する。ステップ１２０で、その選択したブロック（以下「ブロックＫ」）を消去する。これは、フラッシュ管理システムが空きブロックのプールを非消去状態で保持している、と仮定している。空きブロックを使用する処理の速度を上げるために、空きブロックのプールを、既に消去した状態で保持するフラッシュ管理システムもある。損耗平準化のこの方法をそのようなシステム内で作動するよう修正することは、同業者には容易である。ステップ１３０で、ブロックＫの使用を開始する。これがどのように実行されるのか、またその結果としてどの制御フィールドが更新されるのかの詳細は、異なるフラッシュ管理システム間で異なり、本発明の方法を理解することに関係はない。
【００３５】
ステップ１４０で、ブロックＫがたった今もう一つの消去サイクルを通過したという事実を反映するために、ブロックＫの相対等級を更新する。これは、図２でさらに詳述する。
【００３６】
ステップ１５０で、ブロックＫがたった今もう一つの消去サイクルを通過したという事実を反映するために、ブロックＫ−１の相対等級を更新する。これは、図３でさらに詳述する。
【００３７】
ステップ１６０で、ブロックＫがたった今もう一つの消去サイクルを通過したという事実を反映するために、ブロックＫ＋１の相対等級を更新する。これは、また、図３でさらに詳述する。
【００３８】
図２は、ブロックＫの相対等級を更新する方法（図１のステップ１４０）を詳述する。ステップ２００で、ブロックＫの相対等級が、記憶可能な最大値に等しいかどうかをチェックする。８ビットを使用する相対等級の上記例に対しては、これは、相対等級が１２７に等しいかどうかを尋ねることを意味する。答えが肯定的である場合、相対等級をさらに１だけ増加させることはできないので、何も実行しない（ステップ２１０）。答えが否定的である場合、相対等級を１だけ増加させるための余地がある。それから、さらに、ブロックＫの相対等級が、記憶可能な最大値引く１に等しいかどうかをチェックする（ステップ２２０）。８ビットを使用する相対等級の上記例に対しては、これは、相対等級が１２６に等しいかどうかを尋ねることを意味する。答えが肯定的である場合、それからステップ２３０において、相対等級を１だけ増加させる。答えが否定的である場合、ステップ２４０において、相対等級を２だけ増加させる。このロジックの結果は、そのような増分値のための余裕がある限り、相対等級を２だけ増加させる。余裕がないケースでは、相対等級を最大可能値で打ち切る。この結果は、ブロックの消去回数とその隣の二つの平均消去回数との間の相違の二倍であるという、相対等級の定義に従っている。（この段階で、隣の二つが追加消去サイクルを通過しないのに）ブロックに一回の追加消去サイクルを通過させることは、相対等級を２だけ上昇させることが明確である。
【００３９】
図３は、ブロックＫ−１およびＫ＋１の相対等級を更新する方法（図１の、各々ステップ１５０および１６０）を詳述する。ステップ３００で、ブロックＫ−１またはブロックＫ＋１の相対等級が、記憶可能な最小値に等しいかどうかをチェックする。８ビットを使用する相対等級の上記例に対しては、これは、相対等級が−１２８に等しいかどうかを尋ねることを意味する。答えが肯定的である場合、相対等級をさらに減少させることはできないので、何も実行しない（ステップ３１０）。答えが否定的である場合は、相対等級を減少させるための余地があるため、それからステップ３２０で、相対等級を１だけ減少させる。このロジックの結果は、そのような減少のための余地がある限り、相対等級を１だけ減少させることである。余地がない場合は、相対等級を最小可能値で打ち切る。この結果は、再び、ブロックの消去回数とその隣の二つの平均消去回数との間の相違の二倍である相対等級の定義に従っている。（この段階で、そのブロックも隣の他のブロックも追加の消去サイクルを通過しないのに）隣の一つのブロックに一回の追加サイクルを通過させることは、明確に、相対等級が一つ下がるという結果になる。
【００４０】
相対等級値が最小または最大値で打ち切られる可能性があるという事実は、相対等級の保持値が単に理論的に正しい値の近似値であるのかも知れない、ということを意味する。しかしながら、損耗平準化を達成するための相対等級の使用は、相対等級を典型的に小さく、ゼロに近いものとするため、この近似は、ほとんどのブロックに対して非常に正確である。損耗平準化アルゴリズムは、典型的に、消去回数の正確な計数からの小さな逸脱に対して敏感ではない。したがって、いくらかの不正確さを伴う、また値を近似するということの引き替えに、相対等級を記憶するために少ないビット数を使用するのであるから、記憶領域を節約するのは当然である。
【００４１】
上記の説明は、相対等級に基づいて動的損耗平準化を達成することを扱った。相対等級はまた、静的損耗平準化の目的でも使用できる。これを達成するために、時々、すべての使用ブロックの相対等級をスキャンし、非常に低い相対等級を持つブロックを探す。そのような低い相対等級を持つブロックの発見は、そのブロックのサイクルが、その隣よりも非常に少ないことを意味する。フラッシュ管理システムは、それから、そのブロックの内容を、それを移動するために割り当てたもう一のブロックへコピーするように処理し、それから、そのブロックを空きブロック・プール内へ戻す。これは結局、要望通り、他のブロックに比較してそのブロックの消去回数を均一にするという結果になる。非常に低い相対等級を持つブロックに対するスキャンは、定期的に特定な周期で行うこともできるし、あるいはユーザ起因の書き込みオペレーションが発生した場合にのみ静的ブロックを空きプール内へ戻すよう、動的損耗平準化メカニズム内へ含ませることもできる。両方法は、静的損耗平準化を実現するための従来の技術に開示されている。
【００４２】
理解すべきことは、損耗平準化の基礎として相対等級を使用することが、最適な平準化をもたらさない可能性のある近似であるということである。これは、相対等級が、ブロックの使用量に関して、隣のブロックに比較したローカル情報のみを提供するからである。デバイス全体に適用するグローバル情報は提供しない。第一のブロックが第二のブロックの相対等級よりも高い相対等級を持つが、実際は、第一のブロックよりも第二のブロックの方がより多くの消去回数を通過している、ということは起こり得る。しかし依然、平均して、また長期の稼働時間に渡って、相対等級への依存は、最適な損耗平準化に近いものを提供する。
【００４３】
消去計数ではなく相対等級を使用する本発明の方法は、すべてのブロックの等級を一緒に中央ロケーションに記憶するシステムに対して特に有用である。これは、三つの隣接ブロックの相対等級を更新する、または一つのブロックの相対等級を更新するコストが、実質的に同じであるからである。この点に関して、各ブロックの等級をそのブロック内に記憶するシステムではそうではない。なぜなら、この場合、三つのブロックの相対等級を更新することは、三つのブロック内へ書き込むことを意味するため、単一のブロックを更新する時間の三倍の時間を費やすことになる。しかしながら、本発明の方法は、中央記憶のケースよりも効率的でないとしても、相対等級を別個に記憶するこのケースにも適用できる。
【００４４】
ブロックの相対等級を計算するための、そのブロックの消去回数とその隣の二つの平均消去回数との間の相違を二倍にする、上記に提示した公式が、相対等級を計算する唯一の方法ではない。例えば、ブロックの消去回数と、それに最も近い隣四つ（各々側に二つずつ）の平均消去回数との間の相違を表す相対等級を定義することも可能である。より一般的に、あらゆる偶数Ｎに関して、ブロックの消去回数と、それに最も近い隣Ｎ個、各側にＮ/２ブロックずつの平均消去回数との間の相違を表す相対等級を計算してもよい。隣Ｎブロック計算の一般的なケースにおいては、各ブロック消去オペレーションで、Ｎ＋１ブロックの相対等級を更新しなければならないが、上記に提示した隣二ブロック計算の利点は、各ブロック消去オペレーションで、単に三ブロックの相対等級のみを更新する必要があるということである。更新すべき相対等級の数の、この最小化は、相対等級が各々別個にそのブロック内に記憶される場合、より多くのブロックに書き込む必要があり、またフラッシュメモリ内への書き込みが比較的時間を要するオペレーションであるため、特に重要である。他方、Ｎ>２を使用することは、本発明をローカル変動に対して鈍感にする。
【００４５】
相対等級の計算は、ブロックを中央にして点対称的な相対等級を採用することによって、さらに近似および単純化できる。例えば、相対等級は、ブロックの消去回数と、それの隣接ブロックの内で先行する一つの消去回数との間の相違を表す、と定義してもよい。したがって、ブロックｉの相対等級は、ＥＣ（ｉ）−ＥＣ（ｉ−１）に等しく、また、Ｎをブロックの数とするとき、ブロック０の相対等級は、ＥＣ（０）−ＥＣ（Ｎ−１）である。この一方に偏った定義は、上記に論じた対称形の定義よりも、ブロックの消去回数の相対的な非均衡の、より粗野な近似を提供するが、長期に渡れば、依然として十分に良好な損耗平準化を提供する。この単純化した相対等級の定義の利点は、各ブロック消去オペレーションにつき、僅かに二つの相対等級だけを更新する必要がある、ということである。
【００４６】
さらに、任意のブロックの相対等級を計算するのに使用する他のブロックが、実際に隣接していることさえ必要なことではない。すべてのブロックに渡って一貫した計算を保持する限りにおいて、他のどのブロックでもよい。例えば、ブロックｉの相対等級が、２ＥＣ（ｉ）−ＥＣ（ｉ＋３０）−ＥＣ（ｉ＋７０）に等しいという定義を使用してもよい。すべてのブロックに関して意味のある計算とするために、第一のブロックが最後のブロックに続くと見なす。相対等級のこの定義は、上記に提示した第一の定義に類似している。相違は、（−１）および（＋１）のオフセットの代わりに、（＋３０）および（＋７０）のオフセットが使用されることである。相対等級のこれら二つの定義に基づく損耗平準化アルゴリズムは、平均で、同じレベルで実行することが期待できる。
【００４７】
上記すべてのものの結果として、本発明の方法が、フラッシュメモリに基づく記憶システムのブロックの損耗平準化を達成するための効率的なやり方を提供することが分かる。本発明の範囲は、上記に提示した方法、それらの方法を採用したメモリ・システム、そしてコンピュータ読取り可能なコードを含みそれらの方法を実現するコンピュータ読取り可能な記憶メディアを含む。
【００４８】
再び図面を参照する。図４は、ホスト３０に結合した、本発明のフラッシュメモリ・デバイス２０の高度なブロック図である。図４は、バン氏の米国特許公報第５，４０４，４８５号に関する図１から適応させたものである。その特許は、すべての目的のために参照によって、本文内に完全に記述したかのように含むものとする。（注記：米国特許公報第５，４０４，４８５号は、本開示とは異なる用語を使用している。米国特許公報第５，４０４，４８５号は、フラッシュメモリの消去ブロックを「ユニット」と呼ぶ。）フラッシュメモリ・デバイス２０は、フラッシュメモリ２４、コントローラ２２およびランダムアクセス・メモリ（ＲＡＭ）２６を含む。米国特許公報第５，４０４，４８５号のフラッシュコントロール１４に対応するコントローラ２２は、米国特許公報第５，４０４，４８５号に説明があるように、ＲＡＭ２６の助けを借りてフラッシュメモリ２４を管理する。コントローラ２２はまた、先に述べたように相対等級を用いる、フラッシュメモリ２４のブロックの損耗平準化をサポートする。
【００４９】
図５は、本発明の代替的なデータ記憶システム５０を表す、高度な部分ブロック図である。データ記憶システム５０は、プロセッサ５２、そして４つのメモリ・デバイスを含む。これらのメモリ・デバイスは、ＲＡＭ５４、ブートＲＯＭ５６、大容量記憶デバイス（ハードディスク）５８およびフラッシュメモリ・デバイス４０であり、すべてがコモンバス６０を介して通信する。フラッシュメモリ・デバイス２０のように、フラッシュメモリ・デバイス４０はフラッシュメモリ４２を含む。フラッシュメモリ・デバイス２０とは異なり、フラッシュメモリ・デバイス４０は、それ自体のコントローラおよびＲＡＭを含んでいない。その代わりに、プロセッサ５２は、例えば、イスラエル、クファル  サバにあるエム-システムズ  フラッシュ  ディスク  パイオニアーズ  リミテッドのＴｒｕｅＦＦＳ（商標）ドライバの様式で、米国特許公報第５，４０４，４８５号の方法を実現し、また本発明の損耗平準化方法をも実現するソフトウェア・ドライバを実行することによって、コントローラ２２をエミュレートする。フラッシュメモリ・デバイスは、また、プロセッサ５２がフラッシュメモリ４２と通信することを可能にするためのバス・インターフェイス４４をも含む。
【００５０】
フラッシュメモリ４２を管理するためにプロセッサ５２が実行するソフトウェア・ドライバのコードは、大容量記憶デバイス５８内に記憶されており、実行のためにＲＡＭ５４へ転送される。したがって、大容量記憶デバイス５８は、本発明の原理によってフラッシュメモリ４２を管理するためのコンピュータ読み取り可能なコードを埋め込んだ、コンピュータ読み取り可能コード記憶メディアの一例である。
【００５１】
本発明を限られた数の実施例に関して説明したが、本発明の多くの変形、修正、そして他の応用が可能であることは明らかである。
【図面の簡単な説明】
【００５２】
本発明を、例としてのみ、添付の図面を参照して説明する。
【図１】本発明による、使用のために空きブロックを割り当てる方法を表すフローチャートである。
【図２】図１に示すブロックの相対等級を更新する方法を示すフローチャートである。
【図３】図１に示すブロックの隣の相対等級を更新する方法を表すフローチャートである。
【図４】本発明のフラッシュメモリ・デバイスを表す、高度なブロック図である。
【図５】本発明のデータ記憶システムを表す、高度な部分ブロック図である。
【図１】
2009506389.tif 000003
【図２】
2009506389.tif 000004
【図３】
2009506389.tif 000005
【図４】
2009506389.tif 000006
【図５】
2009506389.tif 000007
【国際調査報告】
2009506389.tif 000008
2009506389.tif 000009