"複数のブロックに組織化された不揮発性メモリであって、各ブロックは、共に消去可能なメモリユニットに分割される不揮発性メモリにおいて、前記メモリ内のデータを記憶および更新する方法は、aデータの互いに異なる種類を保持するステップと、b前記データの互いに異なる種類に対してランク付けを割り当てるステップと、c各ブロックが実質的に同種類のデータを記憶するように、前記データの互いに異なる種類の更新を複数のブロックに記憶するステップと、d所定の数より少ない空きメモリユニットを有し、かつ前記複数のブロックの中から最上位ランクのデータ種類を有するブロックに応じて、前記ブロックのデータの現在の更新を他のブロックに移転するステップと、e中断されるまでcからdを繰り返すステップと、を含む方法。請求項1記載の方法において、第1の種類のデータの更新が第2の種類のデータよりも更新頻度が低い場合に、第1のデータ種類は、第2のデータ種類よりランクが高い方法。請求項1記載の方法において、ブロックを実質的に充填する第2の種類の更新データのカスケード効果によって第1の種類のデータの更新が生じる場合に、第1のデータ種類は、第2のデータ種類よりランクが高い方法。請求項1記載の方法において、空きメモリユニットの前記所定の数は、1から6の間である方法。請求項1~4のいずれか記載の方法において、前記不揮発性メモリは、フローティングゲートメモリセルを有する方法。請求項1~4のいずれか記載の方法において、前記不揮発性メモリは、フラッシュEEPROMである方法。請求項1~4のいずれか記載の方法において、前記不揮発性メモリは、NROMである方法。請求項1~4のいずれか記載の方法において、前記不揮発性メモリは、メモリカード内にある方法。請求項1~4のいずれか記載の方法において、前記不揮発性メモリは、それぞれがデータの1ビットを記憶するメモリセルを有する方法。請求項1~4のいずれか記載の方法において、前記不揮発性メモリは、それぞれがデータの1ビットより多くを記憶するメモリセルを有する方法。不揮発性メモリであって、複数のブロックに組織化されたメモリアレイであって、各ブロックは、共に消去可能なメモリユニットに分割されるメモリアレイと、データの種類の更新をそれぞれ記憶するための複数のブロックであって、データの各種類は、複数のうちのランクを有する複数のブロックと、あるブロック内の現在の更新を、所定の数より少ない空きメモリユニットを有し、かつ前記複数のブロックのうちの最上位ランクのデータ種類を有する前記ブロックに応じて、他のブロックに移転するためのコントローラと、を備える不揮発性メモリ。請求項11記載の不揮発性メモリにおいて、第1の種類のデータの更新が第2の種類のデータよりも更新頻度が低い場合に、第1のデータ種類は、第2のデータ種類よりランクが高い不揮発性メモリ。請求項11記載の不揮発性メモリにおいて、ブロックを実質的に充填する第2の種類の更新データのカスケード効果によって第1の種類のデータの更新が生じる場合に、第1のデータ種類は、第2のデータ種類よりランクが高い不揮発性メモリ。請求項11記載の不揮発性メモリにおいて、空きメモリユニットの前記所定の数は、1から6の間である不揮発性メモリ。請求項11~14のいずれか記載の不揮発性メモリにおいて、前記不揮発性メモリは、フローティングゲートメモリセルを有する不揮発性メモリ。請求項11~14のいずれか記載の不揮発性メモリにおいて、前記不揮発性メモリは、フラッシュEEPROMである不揮発性メモリ。請求項11~14のいずれか記載の不揮発性メモリにおいて、前記不揮発性メモリは、NROMである不揮発性メモリ。請求項11~14のいずれか記載の不揮発性メモリにおいて、前記不揮発性メモリは、メモリカード内にある不揮発性メモリ。請求項11~14のいずれか記載の不揮発性メモリにおいて、前記不揮発性メモリは、それぞれがデータの1ビットを記憶するメモリセルを有する不揮発性メモリ。請求項11~14のいずれか記載の不揮発性メモリにおいて、前記不揮発性メモリは、それぞれがデータの1ビットより多くを記憶するメモリセルを有する不揮発性メモリ。図1は、本発明を実施するのに適切なメモリシステムの主要ハードウェアの構成要素を概略的に示す。メモリシステム20は、典型的には、ホストインターフェイスを通じてホスト10と共に動作する。メモリシステムは、典型的には、メモリカードの形式を取るか、または埋め込み形メモリシステムである。メモリシステム20は、動作がコントローラ100によって制御されるメモリ200を含む。メモリ200は、1つ以上の集積回路チップに渡って分散された不揮発性メモリセルの1つ以上のアレイからなる。コントローラ100は、インターフェイス110と、プロセッサ120と、オプションのコプロセッサ121と、ROM122読み出し専用メモリと、RAM130ランダムアクセスメモリと、オプションのプログラム可能な不揮発性メモリ124とを含む。インターフェイス110は、ある構成要素をコントローラからホストへとインターフェイスさせ、他の構成要素をメモリ200とインターフェイスさせる。不揮発性ROM122および/またはオプションの不揮発性メモリ124に記憶されたファームウェアは、コントローラ100の機能を実施するためにプロセッサ120に対して符号を提供する。誤り訂正符号は、プロセッサ120またはオプションのコプロセッサ121によって処理されてもよい。代替の実施形態において、コントローラ100は、状態マシン図示せずによって実施される。さらに他の実施形態において、コントローラ100は、ホスト内で実施される。論理および物理ブロック構造図2は、本発明の好ましい実施形態に係る、セクタまたはメタブロックの物理グループに組織化され、コントローラのメモリマネージャによって管理されたメモリを示す。メモリ200は、メタブロックに組織化され、各メタブロックは、共に消去可能な物理セクタS0,...,SN1のグループである。ホスト10は、ファイルシステムまたはオペレーティングシステムの下でアプリケーションを実行する場合に、メモリ200にアクセスする。典型的には、ホストシステムは、データを論理セクタ単位でアドレス指定し、例えば、各セクタは、512バイトのデータを含んでもよい。また、ホストが、論理クラスタ単位でメモリシステムに対して読み出しまたは書き込みを行うのが通常であり、各クラスタは、1つ以上の論理セクタからなる。ホストシステムによっては、より低いレベルのメモリ管理をホスト側で行うためにオプションのホスト側メモリマネージャが存在する場合がある。多くの場合、読み出しまたは書き込み動作中に、ホスト10は、実質的に、メモリシステム20に対してコマンドを発行して、データの論理セクタのストリングを含むセグメントを連続するアドレスと共に読み出しまたは書き込みを行う。フラッシュメモリ200のメタブロック内のホスト論理セクタのデータの記憶および検索を管理するために、メモリ側メモリマネージャが、メモリシステム20のコントローラ100内で実施される。好ましい実施形態において、メモリマネージャは、メタブロックの消去、読み出し、書き込み動作を管理するための数多くのソフトウェアモジュールを含む。また、メモリマネージャは、フラッシュメモリ200とコントローラRAM130との間の動作に関連したシステム制御およびディレクトリデータを保持する。図3Ai~iiiは、本発明の好ましい実施形態に係る、論理グループとメタブロックとの間のマッピングを概略的に示す。物理メモリのメタブロックは、論理グループのデータのN個の論理セクタを記憶するためのN個の物理セクタを有する。図3Aiは、論理グループLGiからのデータを示し、論理セクタは、連続論理順序0,1,...,N-1である。図3Aiiは、同一の論理順序のメタブロック内に記憶されている同じデータを示す。このように記憶される場合に、メタブロックは、順次であるといわれる。一般的に、メタブロックは、異なる順序で記憶されたデータを有してもよく、その場合は、メタブロックは、非順次またはカオス的であるといわれる。論理グループの最小のアドレスと、それがマッピングされるメタブロックの最小アドレスとの間には、オフセットがあることがある。この場合、論理セクタアドレスは、メタブロック内の論理グループの末尾から先頭へ戻るループとして折り返す。例えば、図3Aiiiでは、メタブロックは、その最初の位置が論理セクタkのデータで始まるように記憶する。最終論理セクタN-1に達すると、セクタ0に戻り、最終的には、その最終物理セクタに論理セクタk-1に関連したデータを記憶する。好ましい実施形態において、メタブロックの最初の物理セクタに記憶されたデータの最初の論理セクタアドレスを識別するといった、任意のオフセットの識別のために、ページタグが使用される。2つのブロックは、ページタグだけが異なる場合、その論理セクタを同様の順序で記憶しているものと考えられる。図3Bは、論理グループとメタブロックと間のマッピングを概略的に示す。各論理グループは、データが現在更新中の少数の論理グループを除いて、固有のメタブロックにマッピングされる。論理グループが更新された後、別のメタブロックにマッピングされてもよい。マッピング情報は、論理/物理ディレクトリのセットに維持され、これについては、詳細に後述する。メタブロックマッピングに対する他の種類の論理グループも予期される。例えば、可変サイズのメタブロックが、本願と同日にアランシンクレアによって出願された適応メタブロックという同時継続出願中の共有された米国特許出願特許文献16に開示されている。同時継続出願の開示全体は、本願明細書において参照により援用されている。本発明の特徴の1つは、システムは単一の論理区画で動作し、メモリシステムの論理アドレス範囲にわたる論理セクタのグループは同一に扱われることである。例えば、システムデータを含むセクタと、ユーザデータを含むセクタとは、論理アドレス空間内のどこにでも分散することができる。従来技術のシステムとは異なり、高頻度かつ小サイズの更新を伴うデータを含む可能性が高い論理アドレス空間セクタに局在化させるための、システムセクタすなわち、ファイル割り当てテーブルに関連するセクタ、ディレクトリ、またはサブディレクトリの特別な分割またはゾーニングはない。代わりに、セクタの論理グループを更新するこの手法は、システムセクタに典型的なアクセスパターンおよびファイルデータに典型的なアクセスパターンを効率的に扱うことになる。図4は、物理メモリにおける構造を含むメタブロックの配列を示す。フラッシュメモリは、一単位として共に消去可能なメモリセルのブロックを備える。このような消去ブロックは、フラッシュメモリの消去の最小単位、またはメモリの最小消去ユニットMEUである。最小消去ユニットは、メモリのハードウェア設計パラメータであるが、複数のMEUの消去をサポートするメモリシステムによっては、1つ以上のMEUを備える超MEUを構成することができる。フラッシュEEPROMについて、MEUは1つのセクタを備えてもよいが、複数のセクタが好ましい。図に示されている例では、M個のセクタを有する。好ましい実施形態において、各セクタは、512バイトのデータを記憶することができ、ユーザデータ部分と、システムまたはオーバーヘッドデータを記憶するためのヘッダ部分とを有する。メタブロックがP個のMEUから構成されている場合には、各MEUはM個のセクタを含み、そして、各メタブロックは、N=PM個のセクタを有することになる。メタブロックは、システムレベルでは、例えば共に消去可能なセクタといった、メモリ位置のグループを表す。フラッシュメモリの物理アドレス空間は、メタブロックを消去の最小単位とした、メタブロックのセットとして扱われる。本願明細書においてメタブロックおよびブロックという用語は、媒体管理のためのシステムレベルにおける消去の最小単位を規定するために類義語として使用され、最小消去ユニットまたはMEUは、フラッシュメモリの消去の最小単位を示すために使用される。メタブロックを形成するための最小消去ユニットMEUのリンク付けプログラミング速度および消去速度を最大限にするために、複数のMEUにある複数のページの情報が並列にプログラミングされるように、かつ複数のMEUが並列に消去されるようにすることによって、並行処理ができる限り活用される。フラッシュメモリにおいて、ページは、1回の動作で共にプログラムすることができるメモリセルの集まりである。ページは、1つ以上のセクタを備えていてもよい。また、メモリアレイは、1つ以上のプレーンに分割されてもよく、1つのプレーン内の1つのMEUのみが1度にプログラムまたは消去されてもよい。最後に、プレーンは、1つ以上のメモリチップに渡って分散されていてもよい。フラッシュメモリにおいて、MEUは、1つ以上のページを備えていてもよい。フラッシュメモリチップ内のMEUは、プレーンに組織化されてもよい。各プレーンからの1つのMEUは並行してプログラムまたは消去されてもよいので、各プレーンから1つのMEUを選択することによって複数のMEUメタブロックを形成するのが得策である以下の図5B参照。図5Aは、互いに異なるプレーンの最小消去ユニットのリンク付けから構成されるメタブロックを示す。MB0,MB1,...などの各メタブロックは、メモリシステムの互いに異なるプレーンからのMEUから構成され、互いに異なるプレーンは、1つ以上のチップにわたって分散されていてもよい。図2に示されているメタブロックリンクマネージャ170は、各メタブロックについてのMEUのリンク付けを管理する。各メタブロックは、初期フォーマット処理中に構成され、その構成成分であるMEUを、MEUのうちの1つに障害があるまで、システムの寿命がある限り保持する。図5Bは、1つの最小消去ユニットMEUが、メタブロックへのリンク付けのために各プレーンから選択される、一実施形態を示す。図5Cは、1つより多くの最小消去ユニットMEUが、メタブロックへのリンク付けのために各プレーンから選択される、別の実施形態を示す。別の実施形態において、1つより多くのMEUが各プレーンから選択されて超MEUが形成されてもよい。例えば、超MEUは、2つのMEUから形成されてもよい。この場合、読み出しまたは書き込み動作について1つより多くのパスを利用してもよい。MEUをメタブロックにリンク付けまたは再リンク付けすることは、本願と同日にカルロスゴンザレスらによって出願されたマルチブロック単位へのブロックの適応決定論的グループ化という同時継続出願中の共有された米国特許出願特許文献17に開示されている。同時継続出願の開示全体は、本願明細書において参照により援用されている。メタブロック管理図6は、コントローラおよびフラッシュメモリにおいて実施されるようなメタブロック管理システムの概略ブロック図である。メタブロック管理システムは、コントローラ100において実施された様々な機能モジュールを備え、様々な制御データディレクトリデータを含むをフラッシュメモリ200およびコントローラRAM130内に階層的に分散されたテーブルおよびリストに保持する。コントローラ100内に実装された機能モジュールは、インターフェイスモジュール110と、論理/物理アドレス変換モジュール140と、更新ブロックマネージャモジュール150と、消去ブロックマネージャモジュール160と、メタブロックリンクマネージャモジュール170とを含む。インターフェイス110により、メタブロック管理システムは、ホストシステムとインターフェイスすることができる。論理/物理アドレス変換モジュール140は、論理アドレスをホストから物理メモリ位置へマッピングする。更新ブロックマネージャモジュール150は、データの所定の論理グループについて、メモリにおけるデータ更新動作を管理する。消去ブロックマネージャモジュール160は、メタブロックの消去動作と、新規の情報を記憶するためのメタブロック割り当てとを管理する。メタブロックリンクマネージャモジュール170は、セクタの最小消去可能ブロックのサブグループのリンク付けを管理して、所定のメタブロックを構成する。これらのモジュールの詳細な説明は、それぞれの欄で行う。動作中に、メタブロック管理システムは、アドレス、制御および状態情報などの制御データを生成して、それと共に動作する。制御データのほとんどが小さなサイズの頻繁に変化するデータであることが多いので、大きなブロック構造のフラッシュメモリ内では簡単かつ効率的に記憶および保持することができない。より静的な制御データを不揮発性フラッシュメモリに記憶させ、より変化するより少ない量の制御データをコントローラRAMに位置づけるという階層的分散手法を使用することで、さらに効率的な更新およびアクセスを行う。電源遮断または障害時には、この手法により、揮発性コントローラRAM内の制御データは、不揮発性メモリ内の小さなセットの制御データを走査することによって、迅速に再構築することができる。これが可能なのは、本発明が、データの所定の論理グループの予想される動作に関連するブロックの数を制限しているからである。加えて、存続が必要とされる制御データのいくつかは、セクタ毎に更新可能な不揮発性のメタブロックに記憶され、新規のセクタを生じさせる各更新が、以前の更新に代わって記録される。セクタインデックス付け手法を制御データのために使用して、メタブロック内のセクタ毎の更新を追跡する。不揮発性フラッシュメモリ200は、比較的静的な大量の制御データを記憶する。これには、グループアドレステーブルGAT210と、カオス的ブロックインデックスCBI220と、消去済みブロックリストEBL230と、MAP240とが含まれる。GAT210は、セクタの論理グループと、その対応するメタブロックとの間のマッピングを追跡する。マッピングは、更新を受けるもの以外は変化しない。CBI220は、更新中の論理的な非順次セクタのマッピングを追跡する。EBL230は、消去されたメタブロックのプールを追跡する。MAP240は、フラッシュメモリ内のすべてのメタブロックの消去状態を示すビットマップである。揮発性コントローラRAM130は、頻繁に変化およびアクセスされる制御データの小さな部分を記憶する。これには、割り当てブロックリストABL134と、クリア済みブロックリストCBL136とが含まれる。ABL134は、更新データを記録するためにメタブロックの割り当てを追跡し、CBL136は、割り当て解除および消去されたメタブロックを追跡する。好ましい実施形態において、RAM130は、フラッシュメモリ200に記憶された制御データについてのキャッシュとしての役割を果たす。更新ブロックマネージャ図2に示されている更新ブロックマネージャ150は、論理グループの更新を扱う。本発明の一態様によれば、更新を受けているセクタの各論理グループには、更新データを記録するために、専用の更新メタブロックが割り当てられる。好ましい実施形態において、論理グループの1つ以上のセクタの任意のセグメントが、更新ブロックに記録されることになる。更新ブロックは、順次順序または非順次カオス的としても知られる順序のいずれかで更新データを受信するように管理される。カオス的更新ブロックでは、セクタデータを論理グループ内で任意の順序で更新することができ、また個別のセクタの任意の繰り返しがあってもよい。特に、順次更新ブロックは、いずれのデータセクタの移転の必要なく、カオス的更新ブロックになりえる。カオス的データ更新には、ブロックの所定の割り当ては必要ない。任意の論理アドレスでの非順次書き込みが自動的に対処される。よって、従来技術のシステムとは異なり、論理グループの様々な更新セグメントが論理的な順次順序であってもまたは非順次順序であっても、特殊な処理はない。一般的な更新ブロックは、ホストによって要求された順序で様々なセグメントを記憶するために、単に使用されることになる。例えば、ホストシステムデータまたはシステム制御データがカオス的に更新されがちな場合でも、ホストシステムデータに対応する論理アドレス空間の領域を、ホストユーザデータを伴う領域と別々に扱う必要はない。セクタの完全な論理グループのデータは、1つのメタブロック内に論理的な順次順序で記憶されるのが好ましい。このように、記憶された論理セクタに対するインデックスは、予め規定されている。メタブロックが所定の順序で所定の論理グループのすべてのセクタを記憶している場合、これは変化なしといわれる。更新ブロックに関して、更新データを論理的な順次順序で最終的に充填する場合、更新ブロックは、元メタブロックを容易に置換する更新された変化なしのメタブロックとなる。他方、更新ブロックが更新データを、変化なしのブロックとは異なる論理的な順序で充填する場合、更新ブロックは、非順次またはカオス的更新ブロックであり、順序がばらばらのセグメントは、変化なしのブロックと同一の順序で論理グループの更新データが最終的には記憶されるように、さらに処理されなければならない。好ましい場合において、このセグメントは、1つのメタブロック内の論理的な順次順序である。さらなる処理には、元ブロック内の変化していないセクタを伴う更新ブロック内の更新されたセクタを、さらに他の更新メタブロックに統合化することを伴う。統合化された更新ブロックは、その後、論理的な順次順序となり、元ブロックを置換するために使用することができる。何らかの所定の条件下では、統合化処理に先立って、1つ以上のコンパクト化処理がある。コンパクト化処理は、カオス的更新ブロックのセクタを、置換するカオス的更新ブロックに単純に再記録し、同じ論理セクタの以前の更新によって廃止された重複する論理セクタを削除することはない。更新手法により、複数の更新スレッドを、所定の最大限まで並行して実行することができる。各スレッドは、専用の更新メタブロックを使用して更新を受けている論理グループである。順次データ更新ある論理グループに属するデータを最初に更新する場合、論理グループの更新データについての更新ブロックとして、メタブロックが専用に割り当てられる。更新ブロックが割り当てられるのは、コマンドがホストから受信されて、既存のメタブロックがそのすべてのセクタを変化なく記憶している論理グループの1つ以上のセクタのセグメントを書き込む場合である。最初のホスト書き込み動作の場合、データの最初のセグメントが更新ブロックに記録される。各ホスト書き込みは連続論理アドレスを伴う1つ以上のセクタのセグメントであるので、最初の更新は、その性質上常に順次的であることとなる。後続のホスト書き込みでは、同一の論理グループ内の更新セグメントが、ホストから受信された順序で更新ブロックに記録される。ブロックは、順次更新ブロックとして管理され続けるのに対し、関連する論理グループ内でホストによって更新されたセクタは、論理的に順次的であり続ける。この論理グループ内で更新されたすべてのセクタは、このブロックが閉鎖されるか、カオス的更新ブロックに変換されるかのいずれかとなるまで、この順次更新ブロックに書き込まれる。図7Aは、2つの別個のホスト書き込み動作の結果、順次更新ブロックへ順次順序で書き込まれる論理グループ内のセクタの一例を示し、この論理グループについての元ブロック内の対応するセクタは廃止になる。ホスト書き込み動作1において、論理セクタLS5~LS8内のデータが更新中である。LS5’~LS8’として更新されたデータは、新規に割り当てられた専用の更新ブロックに記録される。便宜上、論理グループ内の更新すべき第1のセクタは、第1の物理セクタ位置から開始する専用更新ブロックに記録される。一般的に、更新すべき第1の論理セクタは、必ずしもグループの論理的に第1番目のセクタではないので、論理グループの最初と、更新ブロックの最初との間にはオフセットがあることがある。このオフセットは、図3Aに関連して前に説明したように、ページタグとして知られている。後続のセクタは、論理的な順次順序で更新される。論理グループの最後のセクタが書き込まれる場合、グループアドレスは折り返して、書き込みシーケンスを、グループの最初のセクタで継続する。ホスト書き込み動作2において、論理セクタLS9~LS12内のデータのセグメントが更新中である。LS9’~LS12’として更新されたデータは、専用の更新ブロック内の、最後の書き込みが終了した場所に直接続く位置に記録される。2つのホスト書き込みは、更新データが論理的な順次順序で、すなわち、LS5’~LS12’のようにして、更新ブロックに記録されたようなものとして理解することができる。更新ブロックが順次更新ブロックとみなされるのは、論理的な順次順序で充填されているからである。更新ブロックに記録された更新データによって、元ブロック内の対応するデータが廃止される。カオス的データ更新カオス的更新ブロック管理は、関連論理グループ内でホストによって更新された任意のセクタが論理的に非順次の場合に、既存の順次更新ブロックについて開始される。カオス的更新ブロックは、関連する論理グループ内の論理セクタが任意の順序でかつ任意の繰り返し量で更新されてもよいようなデータ更新ブロックの形式を取る。これは、ホストによって書き込まれたセクタが、更新中の論理グループ内の以前書き込んだセクタに対して論理的に非順次である場合に、順次更新ブロックからの変換によって作成される。この論理グループ内のその後の更新されたすべてのセクタは、グループ内の論理セクタアドレスが何であれ、カオス的更新ブロック内の次に使用可能なセクタ位置に書き込まれる。図7Bは、5つの別個のホスト書き込み動作の結果、カオス的更新ブロックへカオス的順序で書き込まれる論理グループ内のセクタの一例を示し、この論理グループについての元ブロック内の取り替えられたセクタと、カオス的更新ブロック内の複製セクタとは廃止になる。ホスト書き込み動作1において、元メタブロックに記憶されている所定の論理グループの論理セクタLS10~LS11が更新される。更新された論理セクタLS10’~LS11’は、新規に割り当てられた更新ブロックに記憶される。この点で、更新ブロックは、順次的である。ホスト書き込み動作2において、論理セクタLS5~LS6がLS5’~LS6’に更新されて、更新ブロック内の最終の書き込みに直接続く位置に記録される。これにより、更新ブロックは、順次的からカオス的なものへと変換される。ホスト書き込み動作3において、論理セクタLS10が再び更新中であり、更新ブロックの次の位置にLS10’’として記録される。この点で、更新ブロック内のLS10’’は、元ブロック内のLS10に取って代わる以前の記録内のLS10’に取って代わる。ホスト書き込み動作4において、論理セクタLS10内のデータは再び更新されて、更新ブロックの次の位置にLS10’’’として記録される。よって、LS10’’’が、論理セクタLS10についての現在における最新かつ唯一の有効データとなる。ホスト書き込み動作5において、論理セクタLS30内のデータが更新中であり、更新ブロックにLS30’として記録される。よって、この例は、任意の順序および任意の繰り返しによって、論理グループ内のセクタをカオス的更新ブロックに書き込むことができることを示す。強制的順次更新図8は、2つの別個のホスト書き込み動作の結果としての、論理アドレスに不連続性を有する、順次更新ブロックへ順次順序で書き込まれる論理グループ内のセクタの一例を示す。ホスト書き込み1において、論理セクタLS5~LS8における更新データは、LS5’~LS8’として専用の更新ブロック内に記録される。ホスト書き込み2において、論理セクタLS14~LS16における更新データは、最終の書き込みに続く更新ブロック内にLS14’~LS16’として記録されている。しかし、LS8とLS14との間にアドレスジャンプがあり、ホスト書き込み2は、通常、更新ブロックを非順次的にすることになる。アドレスジャンプは重要ではないので、1つのオプションとしては、ホスト書き込み2を実行する前に、介在セクタのデータを元ブロックから更新ブロックへコピーすることによってパディング動作2Aをまず行うというものである。このように、更新ブロックの順次的性質が維持される。図9は、本発明の一般的な一実施形態に係る、データの論理グループを更新するための更新ブロックマネージャによる処理を示すフロー図である。更新処理は、以下のステップを含む。ステップ260:メモリはブロックに組織化され、各ブロックは共に消去可能なメモリユニットに分割され、各メモリユニットは、データの論理ユニットを記憶するためのものである。ステップ262:データは論理グループに組織化され、各論理グループは、論理ユニットに分割される。ステップ264:標準的な場合、論理グループのすべての論理ユニットは、第1の所定の順序、好ましくは論理的な順次順序に従って、元ブロックのメモリユニットに記憶される。このように、ブロック内の個々の論理ユニットをアクセスするためのインデックスがわかる。ステップ270:データの所定の論理グループ例えば、LGxについて、LGx内で論理ユニットを更新するための要求が行われる一例として、論理ユニット更新が挙げられる。一般的には、更新は、LGx内の1つ以上の連続論理ユニットのセグメントとなる。ステップ272:要求された更新論理ユニットが、LGxの更新の記録専用の第2のブロックに記憶されることになる。記録順序は、第2の順序であり、典型的には、更新が要求された順序に従う。本発明の一特徴は、論理的な順次またはカオス的順序でデータを記録するように、更新ブロックを最初に一般的に設定することができるようにする。第2の順序によっては、第2のブロックは、順次的なものである場合も、カオス的なものである場合もある。ステップ274:処理がステップ270にループバックするにつれて、第2のブロックは、論理ユニットが記録されるように要求し続ける。閉鎖のための所定の条件が具体化すると、第2のブロックは閉鎖されて、さらなる更新を受信しなくなる。この場合、処理は276へ進む。ステップ276:閉鎖された第2のブロックが元ブロックと同様の順序でその更新論理ユニットを記録しているかどうかについて決定が行われる。図3Aに関して説明したように、ページタグ分だけ異なる論理ユニットを記録している場合には、2つのブロックは同様の順序であるとみなされる。2つのブロックが同様の順序である場合は、処理はステップ280へ進み、そうでなければ、ステップ290において、何らかのガーベッジコレクションを行う必要がある。ステップ280:第2のブロックは第1のブロックと同一の順序なので、第2のブロックは、元ブロックである第1のブロックを置換するために使用される。更新処理は、その後、ステップ299で終了する。ステップ290:所定の論理グループの各論理ユニットの最新バージョンが、第2のブロック更新ブロックおよび第1のブロック元ブロックから収集される。所定の論理グループの統合化された論理ユニットは、その後、第1のブロックと同様の順序で第3のブロックに書き込まれる。ステップ292:第3のブロック統合化されたブロックは第1のブロックと同様の順序であるので、第3のブロックは、元ブロックである第1のブロックを置換するために使用される。更新処理は、その後、ステップ299で終了する。ステップ299:閉鎖処理によって変化のない更新ブロックが作成されると、これが所定の論理グループにとっての新規の標準ブロックとなる。論理グループについての更新スレッドは終了される。図10は、本発明の好ましい実施形態に係る、データの論理グループを更新するための更新ブロックマネージャによる処理を示すフロー図である。更新処理は、以下のステップを含む。ステップ310:データの所定の論理グループ例えば、LGxについて、LGx内で論理セクタを更新するための要求が行われる一例として、セクタ更新が挙げられる。一般的には、更新は、LGx内の1つ以上の連続論理セクタのセグメントととなる。ステップ312:LGxに専用の更新ブロックがまだ存在しない場合、ステップ410へ進み、論理グループについて新規の更新スレッドを開始する。これは、論理グループの更新データを記録するのに専用の更新ブロックを割り当てることによって達成されることになる。開放されている更新ブロックが既にあれば、ステップ314へ進み、更新ブロックに対する更新セクタの記録を開始する。ステップ314:現在の更新ブロックが既にカオス的すなわち、非順次的である場合には、そのままステップ510へ進み、要求された更新セクタをカオス的更新ブロックに記録する。現在の更新ブロックが順次的である場合、ステップ316へ進み、順次更新ブロックの処理を行う。ステップ316:本発明の一特徴は、論理的な順次またはカオス的順序でデータを記録するように、更新ブロックを最初に一般的に設定することができるようにする。しかし、論理グループは、最終的にはそのデータを論理的な順次順序でメタブロックに記憶させるので、更新ブロックをできるだけ順次的に維持するのが望ましい。そうすれば、更新ブロックが閉鎖されてさらなる更新ができなくなった場合、ガーベッジコレクションは必要ないので、必要とされる処理が少なくなる。要求された更新が更新ブロックの現在の順次順序に従うかどうかについての決定がなされる。更新が順次的に従う場合、ステップ510へ進み、順次更新が行われ、更新ブロックは順次的なままである。他方、更新が順次的に従わないカオス的更新の場合、他の動作が行われないならば、順次更新ブロックをカオス的なものに変換する。一実施形態において、状況を守るためにこれ以上何もせず、処理は直接ステップ370へ進み、更新ブロックをカオス的なものにする更新が許容される。オプションの強制的順次処理他の実施形態において、強制的順次処理ステップ320が、保留中のカオス的更新の観点から順次更新ブロックをできるだけ保存するためにオプションとして行われる。2つの状況があり、どちらも、欠落したセクタを元ブロックからコピーして、更新ブロック上に記録された論理セクタの順次順序を維持するものである。第1の状況は、更新によって短いアドレスジャンプが生じることである。第2の状況は、更新ブロックを順次的に保つために、更新ブロックを早く閉鎖することである。強制的順次処理ステップ320は、以下のサブステップを含む。ステップ330:更新によって、所定の量CBより大きい論理アドレスジャンプが生じる場合、処理はステップ350の強制的順次更新処理へと進み、そうでなければ、処理はステップ340へと進んで、強制的順次閉鎖の資格があるかどうかの検討を行う。ステップ340:充填されていない物理セクタ数が、更新ブロックのサイズの半分が典型的な値である所定の設定パラメータCCを超える場合、更新ブロックは、比較的使用されず、早く閉鎖されることはない。処理はステップ370へ進み、更新ブロックは、カオス的となる。他方、更新ブロックがおおむね充填されている場合、既に十分に使っているとみなされるので、ステップ360へと進み、強制的順次閉鎖となる。ステップ350:強制的順次更新により、現在の順次更新ブロックを、アドレスジャンプが所定量CBを超えない限り順次的なままとすることができる。基本的には、更新ブロックの関連する元ブロックからのセクタがコピーされて、アドレスジャンプによるギャップを埋める。よって、順次更新ブロックは、ステップ510へ進んで現在の更新を順次記録する前に、介在アドレス内のデータで埋められることになる。ステップ360:強制的順次閉鎖により、現在の順次的な更新ブロックを、カオス的なものに変換するよりも保留中のカオス的更新によって既におおむね充填されていれば、閉鎖することができる。カオス的または非順次更新は、前述したアドレスジャンプ例外、逆方向アドレス遷移、またはアドレス反復の対象ではなく、順方向アドレス遷移を伴うものとして規定される。順次更新ブロックがカオス的更新によって変換されるのを防止するために、更新ブロックの未書き込みのセクタ位置が、更新ブロックの関連した元の部分的に廃止されたブロックからセクタをコピーすることによって充填される。元ブロックは、その後完全に廃止されて、消去することができる。現在の更新ブロックは、現在では、フルセットの論理セクタを有するので、元メタブロックを置き換える変化のないメタブロックとして閉鎖される。処理は、ステップ430へと進み、ステップ310において最初に要求された保留中のセクタ更新の記録を受け付けるために、新規の更新ブロックをその位置に割り当てる。カオス的更新ブロックへの変換ステップ370:保留中の更新が順次順序でなく、オプションとして、強制的順次条件が満たされていない場合、処理がステップ510へ進むときに非順次アドレスを有する保留中の更新セクタが更新ブロックへ記録されるようにするために、順次更新ブロックは、カオス的なものに変換されることが許容される。カオス的更新ブロックの最大数が存在する場合に、変換が進む前に、最近最もアクセスされていないカオス的更新ブロックを閉鎖する必要がある。よって、カオス的更新ブロックの最大数が超えないようにする。最近最もアクセスされていないカオス的更新ブロックの識別は、ステップ420において説明した一般的な場合と同一であるが、カオス的更新ブロックだけに制約される。このときにカオス的更新ブロックを閉鎖することは、ステップ550において説明したような統合化によって達成される。システム制約を受ける新規の更新ブロックの割り当てステップ410:消去メタブロックを更新ブロックとして割り当てる処理は、所定のシステム制約が超えているかどうかを判断することから開始する。リソースは有限であるため、メモリ管理システムは、典型的には、更新ブロックの所定の最大数CAが並行して存在することを許容する。この制限は、順次更新ブロックとカオス的更新ブロックとの総計であり、設計パラメータである。好ましい実施形態において、この制限は、例えば、最大8つの更新ブロックである。また、システムリソースに対するさらなる高い需要により、並行して開放されているカオス的更新ブロックの最大数に対する対応する所定の制限があってもよい例えば、4つ。よって、CA個の更新ブロックが既に割り当てられていれば、次の割り当て要求は、既存の割り当てられたものの1つが閉鎖された後にはじめて満足することができるようになる。処理はステップ420へ進む。開放更新ブロックの数がCAを下回る場合には、処理は直接ステップ430へ進む。ステップ420:更新ブロックCAの最大数を超える場合には、最近最もアクセスされていない更新ブロックが閉鎖されて、ガーベッジコレクションが行われる。最近最もアクセスされていない更新ブロックは、最近最もアクセスされていない論理ブロックに関連した更新ブロックとして識別される。最近最もアクセスされていないブロックを決定する目的で、アクセスは、論理セクタの書き込みと、オプションで読み出しとを含む。開放更新ブロックのリストが、アクセス順に保持され、初期化の際には、アクセス順序は何ら想定されていない。更新ブロックの閉鎖は、更新ブロックが順次的な場合のステップ360および530、ならびに更新ブロックがカオス的な場合のステップ540に関連して説明したのと同様の処理に従う。閉鎖により、ステップ430において新規の更新ブロックを割り当てる空間ができる。ステップ430:割り当て要求は、新規のメタブロックを所定の論理グループLGxに専用の更新ブロックとして割り当てることで満足される。その後、処理はステップ510へ進む。更新データの更新ブロックへの記録ステップ510:要求された更新セクタは、更新ブロックの次に使用可能な物理位置上に記録される。その後、処理はステップ520へ進み、更新ブロックを閉鎖する機が熟したかどうかが判断される。更新ブロックの閉鎖ステップ520:さらなる更新を受け付けるための空間が更新ブロックにまだある場合には、ステップ570へ進む。そうでない場合には、ステップ522へ進み、更新ブロックを閉鎖する。現在の要求された書き込みが、ブロックが有する空間よりも多くの論理セクタを書き込もうとするものである場合に、更新ブロックを満たす実装例として2つのものがある。第1の実装例において、書き込み要求は2つの部分に分割され、第1の部分がブロックの最終物理セクタまで書き込む。その後、ブロックは閉鎖され、書き込みの第2の部分が、次に要求された書き込みとして扱われることになる。他方の実装例において、要求された書き込みは、ブロックが残りのセクタが埋め込まれて閉鎖されている間は保留される。要求された書き込みは、次に要求された書き込みとして扱われることになる。ステップ522:更新ブロックが順次的であれば、ステップ530へと進み、順次閉鎖となる。更新ブロックがカオス的であれば、ステップ540へと進み、カオス的閉鎖となる。順次更新ブロックの閉鎖ステップ530:更新ブロックが順次的かつ満杯であるので、そこに記憶された論理グループには変化がない。メタブロックは変化がなく、元のものを置換する。このとき、元ブロックは完全に廃止され、消去されてもよい。その後、処理はステップ570へと進み、所定の論理グループに対する更新スレッドは終了する。カオス的更新ブロックの閉鎖ステップ540:更新ブロックは非順次的に充填され、いくつかの論理セクタの複数の更新を含む場合もあるので、ガーベッジコレクションが行われて、内部の有効なデータを救い出す。カオス的更新ブロックは、コンパクト化または統合化のいずれかが行われることになる。どちらの処理を行うかは、ステップ542において決定される。ステップ542:コンパクト化を行うか、または統合化を行うかは、更新ブロックの重なり具合に依存する。論理セクタが複数回更新されていれば、その論理アドレスは非常に重なっている。更新ブロックに記録された同一の論理セクタの複数のバージョンがあることになり、最後に記録されたバージョンのみが、この論理セクタについて有効なものである。複数のバージョンを有する論理セクタを含む更新ブロックにおいて、別個の論理セクタの数は、論理グループの数よりはるかに少ないことになる。好ましい実施形態において、更新ブロック内の別個の論理セクタの数が、論理グループの大きさの半分が典型的な値である所定の設計パラメータCDを超える場合には、閉鎖処理はステップ550において統合化を行い、そうでなければ、処理はステップ560においてコンパクト化を行う。ステップ550:カオス的更新ブロックが統合化されることになる場合、元ブロックと更新ブロックとが、統合化されたデータを含む新規の標準メタブロックに置換されることになる。統合化後、更新スレッドはステップ570において終了する。ステップ560:カオス的更新ブロックがコンパクト化されることになる場合、コンパクト化されたデータを保持する新規の更新ブロックに置換されることになる。コンパクト化後、コンパクト化された更新ブロックの処理は、ステップ570において終了する。代わりに、更新ブロックが再び書き込まれるまで、コンパクト化を遅らせることもでき、これにより、介在する更新がないのに統合化に続いてコンパクト化が生じる可能性を排除する。新規の更新ブロックは、その後、LGxにおける更新への次の要求がステップ502において生じるときに、所定の論理ブロックのさらなる更新を行う際に使用されることになる。ステップ570:閉鎖処理によって変化のない更新ブロックが作成される場合には、それが所定の論理グループの新規の標準ブロックになる。この論理グループの更新スレッドは終了することになる。閉鎖処理によって既存のものを置換する新規の更新ブロックが作成される場合には、この新規の更新ブロックは、所定の論理グループに対して要求される次の更新を記録するために使用されることになる。更新ブロックが閉鎖されない場合には、処理は、LGx内の更新に対する次の要求がステップ310に生じる場合に継続する。前述した処理からわかるように、カオス的更新ブロックが閉鎖される場合には、そこに記録された更新データがさらに処理される。特に、その有効データに対しては、他のカオス的ブロックへコンパクト化する処理か、またはその関連する元ブロックに統合化して新たな標準順次ブロックを形成する処理によって、ガーベッジコレクションが行われる。図11Aは、図10に示されているカオス的更新ブロックを閉鎖する統合化処理をより詳細に示すフロー図である。カオス的更新ブロックの統合化は、更新ブロックが閉鎖されている場合、例えば、更新ブロックが最終物理セクタ位置に書き込みがなされた状態で一杯である場合に行われる、2つの予想される処理のうちの1つである。統合化は、ブロックに書き込まれた別個の論理セクタの数が所定の設計パラメータCDを超える場合に選ばれる。図10に示されている統合化処理ステップ550は、以下のサブステップを備える。ステップ551:カオス的更新ブロックが閉鎖されている場合に、それを置換する新規のメタブロックが割り当てられることになる。ステップ552:廃止されたセクタはすべて無視して、カオス的更新ブロックおよびその関連する元ブロック内の各論理セクタの最新バージョンを収集する。ステップ554:収集された有効なセクタを新規のメタブロックに論理的な順次順序で記録して、変化のないブロック、すなわち、論理グループのすべての論理セクタが順次順序で記録されているブロックを形成する。ステップ556:元ブロックを新規の変化のないブロックに置換する。ステップ558:閉鎖された更新ブロックおよび元ブロックを消去する。図11Bは、図10に示されているカオス的更新ブロックを閉鎖するためのコンパクト化処理をより詳細に示すフロー図である。コンパクト化は、ブロック内の別個の論理セクタの数が所定の設計パラメータCDを下回る場合に選ばれる。図10に示されているコンパクト化処理ステップ560は、以下のサブステップを備える。ステップ561:カオス的更新ブロックがコンパクト化されている最中に、それを置換する新規のメタブロックが割り当てられる。ステップ562:コンパクト化されるべき既存のカオス的更新ブロック内の各論理セクタの最新バージョンを収集する。ステップ564:収集されたセクタを新規更新ブロックに記録して、コンパクト化されたセクタを有する新規の更新ブロックを形成する。ステップ566:既存の更新ブロックをコンパクト化されたセクタを有する新規の更新ブロックに置換する。ステップ568:閉鎖された更新ブロックを消去する。論理およびメタブロック状態図12Aは、様々な動作下における、論理グループの予想されるすべての状態と、その状態間で予想される遷移とを示す。図12Bは、論理グループの予想される状態を列挙する表である。論理グループの状態は、以下のように規定される。1.変化なし:論理グループ内のすべての論理セクタが、論理的な順次順序で、ページタグ折り返しなどを使用して、1つのメタブロックに書き込まれている。2.未書き込み:論理グループ内の論理セクタが全く書き込まれていない。論理グループは、グループアドレステーブルにおいて未書き込みとして印付けされ、割り当てられたメタブロックはない。このグループ内のすべてのセクタに対するホスト読み出しに応答して、予め定められたデータパターンが返される。3.順次更新:論理グループ内のいくつかのセクタが、論理的な順次順序で、ページタグなどを使用してメタブロックに書き込まれ、これらのセクタによって、このグループの以前の変化なしの状態から対応する論理セクタが置換される。4.カオス的更新:論理グループ内のいくつかのセクタが、論理的な非順次順序で、ページタグなどを使用してメタブロックに書き込まれ、これらのセクタによって、このグループの以前の変化なしの状態から対応する論理セクタが置換される。グループ内のセクタは、1回より多く書き込まれてもよく、最新のバージョンが、以前のすべてのバージョンを置換することになる。図13Aは、様々な動作下における、メタブロックの予想されるすべての状態と、その状態間で予想される遷移とを示す。図13Bは、メタブロックの予想される状態を列挙する表である。メタブロックの状態は、以下のように規定される。1.消去済み:メタブロック内のすべてのセクタは消去される。2.順次更新:メタブロックには、セクタが論理的な順次順序でページタグなどを使用して部分的に書き込まれている。すべてのセクタは、同一の論理グループに属する。3.カオス的更新:メタブロックには、セクタが論理的な非順次順序で部分的または一杯に書き込まれている。任意のセクタは1回より多く書き込むことができる。すべてのセクタは、同一の論理グループに属する。4.変化なし:メタブロックは、論理的な順次順序でページタグなどを使用して一杯に書き込まれている。5.オリジナル:メタブロックは、以前は変化なしであったが、少なくとも1つのセクタがホストデータ更新によって廃止されている。図14A~14Jは、論理グループの状態と、物理メタブロックとに対する様々な動作の効果を示す状態図である。図14Aは、第1の書き込み動作についての論理グループおよびメタブロック遷移に対応する状態図である。ホストは、依然未書き込みの論理グループの1つ以上のセクタを、新規に割り当てられた消去済みメタブロックに、論理的な順次順序で書き込む。論理グループおよびメタブロックは、順次更新状態になる。図14Bは、第1の変化なし動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだった順次更新論理グループは、すべてのセクタが順次的にホストによって書き込まれると、変化なしとなる。この遷移は、カードが残りの未書き込みのセクタを予め定められたデータパターンで埋めることによって、グループを充填する場合も生じうる。メタブロックは変化なしとなる。図14Cは、第1のカオス的動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだった順次更新論理グループは、少なくとも1つのセクタが非順次的にホストによって書き込まれると、カオス的となる。図14Dは、最初のコンパクト化動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだったカオス的更新論理グループ内のすべての有効なセクタが、旧ブロックから新規のカオス的メタブロックへコピーされ、旧ブロックは、その後消去される。図14Eは、最初の統合化動作についての論理グループおよびメタブロック遷移に対応する状態図である。以前に未書き込みだったカオス的更新論理グループ内のすべての有効なセクタが、旧カオス的ブロックから移動されて、新規に割り当てられたブロックに論理的な順次順序で充填される。ホストによって書き込みされていないセクタには、予め定められたデータパターンが充填される。旧カオス的ブロックは、その後消去される。図14Fは、順次書き込み動作についての論理グループおよびメタブロック遷移に対応する状態図である。ホストは、変更なしの論理グループの1つ以上のセクタを、論理的な順次順序で、新規に割り当てられた消去済みブロックに書き込む。論理グループおよびメタブロックは、順次更新状態となる。以前変更なしであったメタブロックは、元メタブロックとなる。図14Gは、順次充填動作についての論理グループおよびメタブロック遷移に対応する状態図である。順次更新論理グループは、そのすべてのセクタが順次的にホストによって書き込まれる場合に、変化なしとなる。これは、順次更新論理グループを変化無しとするために、元ブロックからの有効なセクタで充填する場合にも生じることがあり、その後、元ブロックは消去される。図14Hは、非順次書き込み動作についての論理グループおよびメタブロック遷移に対応する状態図である。順次更新論理グループは、少なくとも1つのセクタが非順次的にホストによって書き込まれる場合に、カオス的となる。非順次的セクタの書き込みは、更新ブロック内または対応する元ブロック内のいずれかの有効なセクタを廃止することがあってもよい。図14Iは、コンパクト化動作についての論理グループおよびメタブロック遷移に対応する状態図である。カオス的更新論理グループ内のすべての有効なセクタは、旧ブロックから新規のカオス的メタブロックへコピーされて、旧ブロックは、その後消去される。元ブロックは、影響を受けない。図14Jは、統合化動作についての論理グループおよびメタブロック遷移に対応する状態図である。カオス的更新論理グループ内のすべての有効なセクタは、旧カオス的ブロックおよび元ブロックからコピーされて、新規に割り当てられた消去ブロックは論理的な順次順序で充填される。その後、旧カオス的ブロックおよび元ブロックは消去される。更新ブロックの追跡および管理図15は、割り当てのための開放または閉鎖された更新ブロックおよび消去ブロックの状況を追跡するための割り当てブロックリストABLの構造の好ましい実施形態を示す。割り当てブックリストABL610は、コントローラRAM130に保持され、消去されたブロックの割り当て、割り当てられた更新ブロック、関連するブロック、および制御構造の管理を行うことができ、また正確な論理/物理アドレス変換を可能にする。好ましい実施形態において、ABLは、消去済みブロックのリストと、開放更新ブロックリスト614と、閉鎖更新ブロックリスト616とを含む。開放更新ブロックリスト614は、開放更新ブロックの属性を伴う、ABL内のブロックエントリのセットである。開放更新ブロックリストは、現在開放されている各データ更新ブロック毎に1つのエントリを有する。各エントリは、以下の情報を保持する。LGは、現在の更新メタブロックが専用である論理グループアドレスである。順次/カオス的は、更新ブロックが順次またはカオス的更新データで充填されているかどうかを示す状態である。MBは、更新ブロックのメタブロックアドレスである。ページタグは、更新ブロックの最初の物理位置に記録された開始論理セクタである。書き込まれたセクタ数は、更新ブロックに現在書き込まれたセクタの数を示す。MB0は、関連する元ブロックのメタブロックアドレスである。ページタグ0は、関連する元ブロックのページタグである。閉鎖更新ブロックリスト616は、割り当てブロックリストABLのサブセットである。閉鎖更新ブロックの属性を伴う、ABL内のブロックエントリのセットである。閉鎖更新ブロックリストは、閉鎖されたデータ更新ブロック毎に1つのエントリを有するが、そのエントリは、論理的に主要物理ディレクトリに更新されていない。各エントリは、以下の情報を保持する。LGは、現在の更新ブロックが専用である論理グループアドレスである。MBは、更新ブロックのメタブロックアドレスである。ページタグは、更新ブロックの最初の物理位置に記録された開始論理セクタである。MB0は、関連する元ブロックのメタブロックアドレスである。カオス的ブロックのインデックス付け順次更新ブロックは、論理的に順次順序でデータを記憶しているので、ブロック内の任意の論理セクタは、容易に位置決定することができる。カオス的更新ブロックは、その論理セクタを順序がばらばらに記憶し、論理セクタの複数の更新生成物を記憶してもよい。各有効な論理セクタがカオス的更新ブロックのどこにあるかを追跡するために、追加の情報を保持しなければならない。好ましい実施形態において、カオス的ブロックのインデックス付けのデータ構造は、カオス的ブロックにおけるすべての有効なセクタの追跡および高速アクセスを可能にする。カオス的ブロックのインデックス付けは、論理アドレス空間の小さな領域を独立して管理するものであり、システムデータと、ユーザデータのホット領域を効率的に扱う。インデックス付けデータ構造により、性能が大幅な影響を受けないように、本質的にインデックス付け情報が、更新が稀であるという要件でフラッシュメモリ内に保持することができる。他方、カオス的ブロックに現在書き込まれているセクタのリストは、コントローラRAMにおけるカオス的セクタリストに保持される。また、フラッシュメモリからのインデックス情報のキャッシュが、アドレス変換のためのフラッシュセクタアクセス数を最小限にするために、コントローラRAMに保持される。カオス的ブロック毎のインデックスが、フラッシュメモリ内のカオス的ブロックインデックCBI内に記憶される。図16Aは、カオス的ブロックインデックスCBIセクタのデータフィールドを示す。カオス的ブロックインデックスセクタCBIセクタは、カオス的更新ブロックにマッピングされた論理グループ内のセクタ毎のインデックスを含み、カオス的更新ブロックまたはその関連する元ブロック内の論理グループの各セクタの位置を規定する。CBIセクタは、カオス的ブロック内の有効セクタを追跡するためのカオスブロックインデックスフィールドと、カオスブロックについてのアドレスパラメータを追跡するためのカオス的ブロック情報フィールドと、CBIセクタを記憶するメタブロックCBIブロック内の有効なCBIセクタを追跡するためのセクタインデックスフィールドとを含む。図16Bは、カオス的ブロックインデックスCBIセクタが専用のメタブロックに記録されている一例を示す。専用のメタブロックを、CBIブロック620と称する。CBIセクタが更新されると、CBIブロック620内の次に使用可能な物理セクタ位置に書き込まれる。したがって、CBIセクタの複数のコピーがCBIブロック内に存在し、最後に書き込まれたコピーのみが有効である。例えば、論理グループLG1についてのCBIセクタは3回更新され、最後に書き込まれたコピーのみが有効なものである。CBIブロック内の各有効セクタの位置は、ブロック内の最後に書き込まれたCBIセクタ内のインデックスのセットによって識別される。この例において、ブロック内に最後に書き込まれたCBIセクタは、LG136についてのCBIセクタであり、そのインデックスのセットは、以前のすべてのものに取って代わる有効なものである。CBIブロックが最終的にCBIセクタで満杯になると、ブロックは、制御書き込み動作中に、すべての有効セクタを新規のブロック位置に書き換えることによってコンパクト化される。その後、一杯のブロックは、消去される。CBIセクタ内のカオス的ブロックインデックスフィールドは、カオス的更新ブロックにマッピングされた論理グループまたはサブグループ内の各論理セクタについてのインデックスエントリを含む。各インデックスエントリは、対応する論理セクタについての有効データが位置するカオス的更新ブロック内のオフセットを示す。予約されたインデックス値は、論理セクタについての有効データがカオス的更新ブロック内に存在しないことを示し、関連する元ブロック内の対応するセクタが有効であることを示す。いくつかのカオス的ブロックインデックスフィールドエントリのキャッシュが、コントローラRAMに保持される。CBIセクタ内のカオス的ブロック情報フィールドは、システム内に存在するカオス的更新ブロック毎に1つのエントリを含み、ブロックについてのアドレスパラメータ情報を記録する。このフィールド内の情報は、CBIブロック内に最後に書き込まれたセクタにおいて有効であるのみである。この情報は、RAM内のデータ構造にも存在する。カオス的更新ブロック毎のエントリは、3つのアドレスパラメータを含む。1つ目は、カオス的更新ブロックに関連する論理グループの論理アドレスまたは論理グループ番号である。2つ目は、カオス的更新ブロックのメタブロックアドレスである。3つ目は、カオス的更新ブロック内に最後に書き込まれたセクタの物理アドレスのオフセットである。オフセット情報は、RAM内にデータ構造を再構築するために、初期化中のカオス的更新ブロックの走査のための開始点を設定する。セクタインデックスフィールドは、CBIブロックにおける有効CBIセクタ毎のエントリを含む。各許可されたカオス的更新ブロックに関する最も最近書き込まれたCBIセクタが位置するCBIブロック内のオフセットを規定する。インデックス内のオフセットの予約値は、許可されたカオス的更新ブロックが存在しないことを示す。図16Cは、カオス的更新を受けている所定の論理グループの論理セクタのデータに対するアクセスを示すフロー図である。更新処理中に、更新データがカオス的更新ブロックに更新データを記録し、変化していないデータは、論理グループに関連する元メタブロック内に留まる。カオス的更新下で論理グループの論理セクタをアクセスする処理は、以下のようである。ステップ650:所定の論理グループの所定の論理セクタの位置決定を開始する。ステップ652:CBIブロック内の最終書き込みCBIセクタを位置決定する。ステップ654:最終書き込みCBIセクタのカオス的ブロック情報フィールドを検索することによって、所定の論理グループに関連したカオス的更新ブロックまたは元ブロックを位置決定する。このステップは、ステップ662の前であればいつでも行うことができる。ステップ658:最終書き込みCBIセクタが所定の論理グループ宛であれば、CBIセクタは位置決定される。ステップ662へ進む。そうでなければ、ステップ660へ進む。ステップ660:最終書き込みCBIセクタのセクタインデックスフィールドを検索することによって、所定の論理グループについてのCBIセクタを位置決定する。ステップ662:位置決定されたCBIセクタのカオス的ブロックインデックスフィールドを検索することによって、カオス的ブロックまたは元ブロック内の所定の論理セクタを位置決定する。図16Dは、論理グループがサブグループに分割されている代替の実施形態に係る、カオス的更新を受けている所定の論理グループの論理セクタのデータに対するアクセスを示すフロー図である。CBIセクタの容量は有限なので、論理セクタの所定の最大数を追跡することができるのみである。論理グループが単一のCBIセクタが扱えるより多くの論理セクタを有する場合には、論理グループは、CBIセクタがそれぞれ割り当てられた複数のサブグループに分割される。一例において、各CBIセクタは、256個のセクタと、8個までのカオス的更新ブロックとからなる論理グループを追跡するのに十分な容量を有する。論理グループが256セクタを超えるサイズを有する場合には、256セクタのサブグループのそれぞれための別個のCBIセクタが論理グループ内に存在する。8個までのサブグループのためのCBIセクタが論理グループ内に存在してもよく、サイズで2048個のセクタまでの論理グループに対してサポートを提供する。好ましい実施形態において、インデックスの管理を促進するために、間接インデックス付け手法が取られる。セクタインデックスの各エントリは、直接および間接フィールドを有する。直接セクタインデックスは、特定のカオス的更新ブロックに関連するすべての予想されるCBIセクタが位置するCBIブロック内のオフセットを規定する。このフィールドの情報は、最後に書き込まれた、この特定のカオス的更新ブロックに関連するCBIセクタにおいてのみ有効である。インデックス内のオフセットの予約値は、CBIセクタが存在しないことを示す。というのは、カオス的更新ブロックに関連する対応する論理サブグループが、存在しないか、または更新ブロックが割り当てられて以来更新されていないからである。間接セクタインデックスは、各許可されたカオス的更新ブロックに関連する最も最近書き込まれたCBIセクタが位置するCBIブロック内のオフセットを規定する。インデックス内のオフセットの予約値は、許可された更新ブロックが存在しないことを示す。図16Dは、以下のような、カオス的更新下の論理グループの論理セクタをアクセスする処理を示す。ステップ670:各論理グループを複数のサブグループに分割して、CBIセクタを各サブグループに割り当てる。ステップ680:所定の論理グループの所定のサブグループの所定の論理セクタの位置決定を開始する。ステップ682:CBIブロック内の最終書き込みCBIセクタを位置決定する。ステップ684:最終書き込みCBIセクタのカオス的ブロック情報フィールドを検索することによって、所定のサブグループに関連したカオス的更新ブロックまたは元ブロックを位置決定する。このステップは、ステップ696の前であればいつでも行うことができる。ステップ686:最終書き込みCBIセクタが所定の論理グループ宛である場合には、ステップ691へ進む。そうでなければ、ステップ690へ進む。ステップ690:最終書き込みCBIセクタの間接セクタインデックスフィールドを検索することによって、所定の論理グループについての複数のCBIセクタの最終書き込みを位置決定する。ステップ691:所定の論理グループについてのサブグループの1つに関連したCBIセクタが少なくとも位置決定されている。続く。ステップ692:位置決定されたCBIセクタが所定のサブグループ宛である場合には、この所定のサブグループについてのCBIセクタが位置決定される。ステップ696へ進む。そうでなければ、ステップ694へ進む。ステップ694:現在の位置決定されたCBIセクタの直接セクタフィールドを検索することによって、所定のサブグループについてのCBIセクタを位置決定する。ステップ696:所定のサブグループについてのCBIセクタのカオス的ブロックインデックスフィールドを検索することによって、カオス的ブロックまたは元ブロック内の所定の論理セクタを位置決定する。図16Eは、各論理グループが複数のサブグループに分割される実施形態についての、カオス的ブロックインデックス付けCBIセクタおよびその機能の例を示す。論理グループ700は、その変化のないデータを、元メタブロック702内に記憶する。その後、論理グループは、専用のカオス的更新ブロック704の割り当てを伴う更新を受ける。この例において、論理グループ700は、サブグループA,B,C,Dのようなサブグループに分割され、各サブグループは256個のセクタを有する。サブグループB内のi番目のセクタを位置決定するために、CBIブロック620内の最終書き込みCBIセクタを最初に位置決定する。最終書き込みCBIセクタのカオス的ブロック情報フィールドは、所定の論理グループについてのカオス的更新ブロック704を位置決定するためのアドレスを提供する。同時に、これは、カオス的ブロックに書き込まれた最終セクタの位置をも提供する。この情報は、走査および再構築の際に有用である。最終書き込みCBIセクタが所定の論理グループの4つのCBIセクタのうちの1つであることがわかると、このセクタが確かにi番目の論理セクタを含む所定のサブグループBについてのCBIセクタかどうかをさらに確認することになる。そうであれば、CBIセクタのカオス的ブロックインデックスは、i番目の論理セクタについてのデータを記憶するメタブロック位置を指すことになる。セクタ位置は、カオス的更新ブロック704または元ブロック702のいずれかでありうる。最終書き込みCBIセクタが所定の論理グループの4つのCBIセクタのうちの1つではあるが、正確にはサブグループBについてのCBIセクタではないことがわかると、その直接セクタインデックスを検索して、サブグループBについてのCBIセクタを位置決定する。この正確なCBIセクタが位置決定されると、そのカオス的ブロックインデックスを検索して、カオス的更新ブロック704および元ブロック702の中のi番目の論理セクタを位置決定する。最終書き込みCBIセクタが所定の論理グループの4つのCBIセクタのうちのいずれでもないことがわかると、その間接セクタインデックスを検索して、4つのうちの1つを位置決定する。図16Eに示されている例において、サブグループCについてのCBIセクタを位置決定する。その後、サブグループCについてのこのCBIセクタは、その直接セクタインデックスを検索して、サブグループBについての正確なCBIセクタを位置決定する。図に示されている例では、カオス的ブロックインデックスを検索すると、i番目の論理セクタが変化していないことがわかり、その有効データが元データ内で位置決定される。同様の検討が、所定の論理グループのサブグループC内のj番目の論理セクタを位置決定することにも適用される。図に示されている例では、最終書き込みCBIセクタが所定の論理グループの4つのCBIセクタのうちのいずれでもないことがわかる。その間接セクタインデックスは、所定のグループについての4つのCBIセクタのうちの1つを指す。また、4つのうちの指された最終書き込み分は、確かにサブグループCについてのCBIセクタであることがわかる。そのカオス的ブロックインデックスを検索すると、j番目の論理セクタが、カオス的更新ブロック704内の指定された位置に位置決定されることがわかる。カオス的セクタのリストが、システム内の各カオス的更新ブロックについてのコントローラRAM内にある。各リストは、関連するCBIセクタがフラッシュメモリ内で最後に更新されたときからの、カオス的更新ブロック内に書き込まれたセクタの記録を含む。特定のカオス的更新ブロックについての論理セクタアドレスの数は、カオス的セクタリスト内に保持することができ、8から16というのが典型的な値の設計パラメータである。このリストの最適なサイズは、カオス的データ書き込み動作についてのオーバーヘッドに対する影響と、初期化中のセクタ走査時間とを調整して決定される。システム初期化中に、各カオス的更新ブロックを必要に応じて走査して、関連するCBIセクタのうちの1つについての以前の更新以来書き込まれた有効なセクタを識別する。各カオス的更新ブロックについてのコントローラRAM内のカオス的セクタリストが構築される。各ブロックは、最終書き込みCBIセクタ内のカオス的ブロック情報フィールドで規定された最終セクタアドレスから走査されればよい。カオス的更新ブロックが割り当てられると、CBIセクタが、すべての更新された論理サブグループに対応するように書き込まれる。カオス的更新ブロックについての論理および物理アドレスは、カオス的ブロックインデックスフィールド内の空白エントリと共に、セクタ内の使用可能なカオス的ブロック情報フィールド内に書き込まれる。カオス的セクタリストは、コントローラRAMにおいて開放される。カオス的更新ブロックが閉鎖されると、CBIセクタが、セクタ内のカオス的ブロック情報フィールドから除去されたブロックの論理および物理アドレスと共に書き込まれる。RAM内の対応するカオス的セクタリストは、使用されなくなる。コントローラRAM内の対応するカオス的セクタリストは、カオス的更新ブロックに書き込まれたセクタの記録を含むように修正される。コントローラRAM内のカオス的セクタリストが、カオス的更新ブロックに対するさらなるセクタ書き込みの記録について使用可能な空間を有していない場合には、更新されたCBIセクタが、リスト内のセクタに関連する論理サブグループについて書き込まれ、リストはクリアされる。CBIブロック620が満杯になると、有効なCBIセクタが割り当てられた消去済みブロックにコピーされ、以前のCBIブロックは消去される。アドレステーブル図2に示されている論理/物理アドレス変換モジュール140は、ホストの論理アドレスをフラッシュメモリ内の対応する物理アドレスに関連付ける役割を担う。論理グループと物理グループメタブロックとの間のマッピングが、不揮発性フラッシュメモリ200および揮発性だが動作が速いRAM130図1参照に分散されたテーブルおよびリストのセット内に記憶される。アドレステーブルは、フラッシュメモリに保持され、メモリシステム内の各論理グループについてのメタブロックアドレスを含む。加えて、最近書き込まれたセクタについての論理/物理アドレス記録は、RAMに一時的に保持される。これらの揮発性記録は、電源投入後にシステムを初期化するときに、フラッシュメモリ内のブロックリストおよびデータセクタヘッダから再構築することができる。よって、フラッシュメモリ内のアドレステーブルは、たまに更新されればよく、制御データについてのオーバーヘッド書き込み動作の割合が減ることになる。論理グループについてのアドレス記録の階層は、開放更新ブロックリストと、RAM内の閉鎖更新ブロックリストと、フラッシュメモリに保持されたグループアドレステーブルGATとを含む。開放更新ブロックリストは、更新されたホストセクタデータについて現在開放されているデータ更新ブロックのコントローラRAM内のリストである。あるブロックに対するエントリは、ブロックが閉鎖されると、閉鎖更新ブロックリストに移動される。閉鎖更新ブロックリストは、閉鎖されているデータ更新ブロックのコントローラRAM内のリストである。リスト内のエントリのサブセットは、制御書き込み動作中に、グループアドレステーブル内のセクタに移動される。グループアドレステーブルGATは、メモリシステム内のホストデータのすべての論理グループについてのメタブロックアドレスのリストである。GATは、論理アドレスに従って順次的に並べられた、論理グループ毎に1つのエントリを含む。GAT内のn番目のエントリは、アドレスnの論理グループについてのメタブロックアドレスを含む。好ましい実施形態において、このテーブルは、フラッシュメモリ内にあるテーブルであり、メモリシステム内のすべての論理グループについてのメタブロックアドレスを規定するエントリを伴うセクタGATセクタと称するのセットを含む。GATセクタは、フラッシュメモリ内の1つ以上の専用制御ブロックGATブロックと称する内にある。図17Aは、グループアドレステーブルGATセクタのデータフィールドを示す。GATセクタは、例えば、128個の連続する論理グループのセットについてのGATエントリを含むのに十分な容量を有してもよい。各GATセクタは、2つの構成要素、すなわち、ある範囲内の各論理グループのメタブロックアドレスについてのGATエントリのセットと、GATセクタインデックスとを含む。第1の構成要素は、論理アドレスに関連するメタブロックを位置決定するための情報を含む。第2の構成要素は、GATブロック内のすべての有効なGATセクタを位置決定するための情報を含む。各GATエントリは、3つのフィールド、すなわち、メタブロック番号と、図3Aiiiに関連して前に規定したようなページタグと、メタブロックが再リンクされたかどうかを示すフラグとを有する。GATセクタインデックスは、GATブロック内の有効なGATセクタの位置を列挙する。このインデックスは、各GATセクタ内にあるが、GATブロック内の次に書き込まれたGATセクタのバージョンによって取って代わられる。よって、最終書き込みGATセクタ内のバージョンのみが有効である。図17Bは、グループアドレステーブルGATセクタが1つ以上のGATブロックに記録されている一例を示す。GATブロックは、GATセクタを記録する専用のメタブロックである。GATセクタが更新される場合には、GATブロック720内の次に使用可能な物理セクタ位置に書き込まれる。したがって、GATセクタの複数のコピーがGATブロック内に存在することがあり、最後に書き込まれたコピーのみが有効である。例えば、GATセクタ45は、少なくとも2回更新され、最終バージョンが有効なものである。GATブロック内の各有効セクタの位置は、ブロック内の最終書き込みGATセクタ内のインデックスのセットによって識別される。この例において、ブロック内の最終書き込みGATセクタは、GATセクタ56であり、そのインデックスのセットは、すべての以前のものにとって代わる有効なものである。GATブロックが、GATセクタで最終的に満杯になった場合には、ブロックは、すべての有効なセクタを新規のブロック位置に書き換えることによって、制御書き込み動作中にコンパクト化される。その後、一杯のブロックは消去される。前に説明したように、GATブロックは、論理アドレス空間のある領域におけるグループの論理的に連続したセットについてのエントリを含む。GATブロック内のGATセクタは、それぞれ、128個の連続する論理グループについての論理/物理マッピング情報を含む。GATブロックが対象とするアドレス範囲内のすべての論理グループについてのエントリを記憶するのに必要な数多くのGATセクタは、ブロック内の全セクタ位置のほんのわずかを占めるに過ぎない。したがって、あるGATセクタは、ブロック内の次に使用可能なセクタ位置に書き込まれることによって更新されてもよい。すべての有効なGATセクタおよびそれらのGATブロック内の位置のインデックスが、直近の書き込みGATセクタ内のインデックスフィールドに保持される。有効なGATセクタによって占められたGATブロック内の僅かな合計セクタは、システム設計パラメータであり、典型的には25である。しかし、GATブロック毎に最大64個の有効GATセクタがある。論理容量が大きいシステムにおいて、1つ以上のGATブロックにGATセクタを記憶する必要がある場合がある。この場合、各GATブロックは、固定的な範囲の論理グループに関連付けられる。GAT更新は、制御書き込み動作の一部として行われ、割り当てのためのブロックがABLになくなったときにトリガされる図18参照。これは、ABL充填動作およびCBLを空にする動作と並行して行われる。GAT更新動作中に、1つのGATセクタは、閉鎖更新ブロックリスト内の対応するエントリからの情報で更新されたエントリを有する。GATエントリが更新されると、対応するエントリはどれでも、閉鎖更新ブロックリストCUBLから除去される。例えば、更新すべきGATセクタは、閉鎖更新ブロックリスト内の最初のエントリに基づいて選択される。更新されたセクタは、GATブロック内の次に使用可能なセクタ位置に書き込まれる。更新されたGATセクタに使用可能なセクタ位置がなくなったときに、GAT書き換え動作は、制御書き込み動作中に生じる。新たなGATブロックが割り当てられ、GATインデックスによって規定された有効なGATセクタは、順次順序で一杯のGATブロックからコピーされる。その後、一杯のGATブロックは消去される。GATキャッシュは、GATセクタ内の128個のエントリの再分割部分内のエントリの、コントローラRAM130内のコピーである。GATキャッシュエントリの数は、システム設計パラメータであり、典型的な値は32である。該当セクタの再分割部分についてのGATキャッシュは、エントリがGATセクタから読み出される度に作成される。複数のGATキャッシュが保持される。その数は、設計パラメータであり、典型的な値は4である。GATキャッシュは、最近最も使用されていないことに基づいて、異なるセクタの再分割部分についてのエントリで上書きされる。消去済みメタブロックの管理図2に示されている消去ブロックマネージャ160は、ディレクトリおよびシステム制御情報を保持するためのリストのセットを使用して、消去ブロックを管理する。これらのリストは、コントローラRAM130およびフラッシュメモリ200に分散されている。消去されたメタブロックがユーザデータの記憶のため、またはシステム制御データ構造の記憶のために割り当てられなければならない場合には、コントローラRAMに保持された割り当てブロックリストABL図15参照内の次に使用可能なメタブロック番号が選択される。同様に、メタブロックが廃棄後に消去される場合には、その番号が、同じくコントローラRAMに保持されたクリア済みブロックリストCBLに追加される。比較的静的なディレクトリおよびシステム制御データが、フラッシュメモリ内に記憶される。これらには、消去済みブロックリストと、フラッシュメモリ内のすべてのメタブロックの消去された状態のビットマップMAPリストとが含まれる。消去済みブロックリストおよびMAPは、個別のセクタに記憶され、MAPブロックとして知られる専用のメタブロックに記録される。これらのリストは、コントローラRAMおよびフラッシュメモリに分散されて、消去済みメタブロックの使用を効率的に管理するための消去済みブロック記録の階層を提供する。図18は、消去済みブロックの使用およびリサイクルのための制御およびディレクトリ情報の分配および流れを示す概略ブロック図である。制御およびディレクトリデータは、コントローラRAM130内か、フラッシュメモリ200内に常駐するMAPブロック750内のいずれかに保持されるリストに保持される。好ましい実施形態において、コントローラRAM130は、割り当てブロックリストABL610と、クリア済みブロックリストCBL740とを保持する。図15に関連して前に説明したように、割り当てブロックリストABLは、ユーザデータの記憶のため、またはシステム制御データ構造の記憶のために最近割り当てられたのがどのメタブロックかを追跡する。新規の消去済みメタブロックを割り当てる必要がある場合には、割り当てブロックリストABL内の次に使用可能なメタブロック番号が選択される。同様に、クリア済みブロックリストCBLを使用して、割り当て解除および消去された更新メタブロックを追跡する。ABLおよびCBLは、比較的アクティブな更新ブロックを追跡する際の迅速なアクセスおよび容易な操作のために、コントローラRAM130図1参照に保持される。割り当てブロックリストABLは、消去済みメタブロックのプールと、消去済みメタブロックを更新ブロックにする割り当てとを追跡する。よって、これらの各メタブロックは、ABL保留割り当ての消去済みブロックか、開放更新ブロックか、閉鎖更新ブロックかどうかを指定する属性によって記述されてもよい。図18は、消去済みABLリスト612と、開放更新ブロックリスト614と、閉鎖更新ブロックリスト616とを含むABLを示す。加えて、開放更新ブロックリスト614に関連付けられているのは、関連する元ブロックリスト615である。同様に、閉鎖更新ブロックリストに関連付けられているのは、関連消去済みの元ブロックリスト617である。図15において前に示したように、これらの関連リストは、それぞれ、開放更新ブロックリスト614および閉鎖更新ブロックリスト616のサブセットである。消去済みABLブロックリスト612、開放更新ブロックリスト614、および閉鎖更新ブロックリスト616は、すべて、割り当てブロックリストABL610のサブセットであり、それぞれの中のエントリは、それぞれ対応する属性を有する。MAPブロック750は、フラッシュメモリ200内の消去管理記録を記憶するのに専用のメタブロックである。MAPブロックは、時系列のMAPブロックセクタを記憶し、各MAPセクタは、消去ブロック管理EBMセクタ760またはMAPセクタ780のいずれかである。メタブロックが廃棄されて、消去済みブロックが割り当てで使い尽くされてリサイクルされるにつれて、関連する制御およびディレクトリデータは、MAPブロック内で更新される論理セクタに含まれるのが好ましく、更新データの各インスタンスは、新規のブロックセクタに記録される。EBMセクタ760およびMAPセクタ780の複数のコピーがMAPブロック750内に存在してもよく、その最新バージョンのみが有効である。有効MAPセクタの位置へのインデックスは、EMBブロック内のフィールド内に含まれる。有効なEMBセクタが、制御書き込み動作中のMAPブロック内にいつも最後に書き込まれる。MAPブロック750が一杯の場合には、すべての有効セクタを新規のブロック位置に書き換えることによって、制御書き込み動作中にコンパクト化される。その後、一杯のブロックは消去される。各EBMセクタ760は、消去済みブロックリストEBL770を含み、これは、消去済みブロックの母集団のサブセットのアドレスのリストである。消去済みブロックリストEBL770は、消去済みメタブロック番号を含むバッファとしての役割を果たし、EBLから、メタブロック番号が周期的に取り出されてABLを再充填し、EBLに対して、メタブロック番号が周期的に追加されてCBLを再び空にする。EBL770は、使用可能ブロックバッファABB772、消去済みブロックバッファEBB774、および消去済みブロックバッファCBB776のためのバッファとしての役割を果たす。使用可能ブロックバッファABB772は、前回のABL充填動作のすぐ後に続くABL610内のエントリのコピーを含む。これは、実質上、ABL充填動作直後のABLのバックアップコピーである。消去済みブロックバッファEBB774は、MAPセクタ780から、または後述するCBBリスト776からのいずれかから先に転送され、かつABL充填動作中にABL610へ転送に使用可能である消去済みブロックアドレスを含む。クリアされたブロックバッファCBB776は、CBLを空にする動作中にCBL740から転送され、かつMAPセクタ780またはEBBリスト774へ後に転送される消去済みブロックのアドレスを含む。各MAPセクタ780は、MAPと称されるビットマップ構造を含む。MAPは、フラッシュメモリ内のメタブロック毎に1ビットを使用し、これは、各ブロックの消去状態を示すために使用される。ABL、CBL、またはEBM内の消去済みブロックリスト内に列挙されたブロックアドレスに対応するビットは、MAP内において消去済み状態に設定されない。有効データ構造を含まず、かつMAP内の消去済みブロック、消去済みブロックリスト、ABL、またはCBLとして指定されていないブロックはどれでも、ブロック割り当てアルゴリズムによって決して使用されず、従ってホストまたは制御データ構造の記憶のためにアクセスすることはできない。これにより、アクセス可能なフラッシュメモリアドレス空間から障害位置のあるブロックを除外するための簡単な機構が提供される。図18に示されている階層により、消去済みブロック記録を効率的に管理することができるようになり、コントローラのRAM内に記憶されたブロックアドレスリストの完全なセキュリティを提供する。消去済みブロックエントリが、これらのブロックアドレスリストと、1つ以上のMAPセクタ780との間で、稀に交換される。これらのリストは、電源が切られた後のシステム初期化中に、消去済みブロックリスト、およびフラッシュメモリ内のセクタに記憶されたアドレス変換テーブル内の情報と、フラッシュメモリ内のわずかな数の参照済みデータブロックの限定的な走査とを介して再構築される。消去済みメタブロック記録の階層を更新するために採用されたアルゴリズムにより、消去済みブロックが、MAPブロック750からのアドレス順序のブロックのバーストと、ブロックがホストによって更新された順序を反映するCBL740からのブロックアドレスのバーストとをインターリーブする順序で使用するために割り当てられる結果となる。メタブロックサイズおよびシステムメモリ容量のほとんどについて、1つのMAPセクタは、システム内のすべてのメタブロックについてのビットマップを提供する。この場合、消去済みブロックは、このMAPセクタに記録されるとおりのアドレス順序での使用のために常に割り当てられる。消去ブロック管理動作前に説明したように、ABL610は、使用のために割り当てられるであろう消去済みメタブロック、およびデータ更新ブロックとして最近割り当てられたメタブロックについてのアドレスエントリを有するリストである。ABL内のブロックアドレスの実際の数は、上限と下限という、システム設計の変数の間にある。製造中にフォーマットされたABLエントリの数は、カードの種類と容量との関数である。加えて、システムの寿命の終わりが近づくとABL内のエントリの数が減少するのは、使用可能な消去済みブロックの数が寿命内でのブロックの障害によって減少するためである。例えば、充填動作の後、ABL内のエントリは、以下の目的のために使用可能なブロックを指定してもよい。ブロック毎に1つのエントリを有する部分的に書き込まれたデータ更新ブロックについてのエントリであり、同時に開放されている更新ブロックの最大数についてのシステム制限を越えないもの。データ更新ブロックとして割り当てるための消去済みブロックについての1個から12個の間のエントリ。制御ブロックとして割り当てるための消去済みブロックについての4つのエントリ。ABL充填動作ABL610が割り当てによって使い尽くされると、再充填される必要があることになる。ABLを充填する動作は、制御書き込み動作中に生じる。これは、ブロックを割り当てなければならない場合にトリガされるが、ABLには、データ更新ブロックとして割り当てるため、またはいくつかの他の制御データ更新ブロックのために使用可能な消去済みブロックエントリが十分には含まれていない。制御書き込み中に、ABL充填動作は、GAT更新動作と並行して行われる。以下の動作が、ABL充填動作中に生じる。1.現在のデータ更新ブロックの属性を有するABLエントリは保持される。2.閉鎖データ更新ブロックの属性を有するABLエントリは、このブロックについてのエントリが並行GAT更新動作において書き込み中でなければ保持され、書き込み中であれば、このエントリはABLから除去される。3.割り当てられていない消去ブロックについてのABLエントリは保持される。4.ABLは、エントリの除去によって生じたギャップを除去するためにコンパクト化され、エントリの順序が維持される。5.ABLは、EBBリストから次に使用可能なエントリをつけることによって完全に充填される。6.ABBリストは、ABL内の現在のエントリで上書きされる。CBLを空にする動作CBLは、消去済みブロックエントリの数に対するABLと同じ制限を有する、コントローラRAM内の消去済みブロックアドレスのリストである。CBLを空にする動作は、制御書き込み動作中に生じる。したがって、この動作は、ABL充填/GAT更新動作、またはCBIブロック書き込み動作と並行して行われる。CBLを空にする動作において、エントリはCBL740から除去されて、CBBリスト776に書き込まれる。MAP交換動作MAPセクタ780およびEBMセクタ760内の消去ブロック情報間のMAP交換動作は、EBBリスト774が空の場合に、制御書き込み動作中に周期的に生じてもよい。システム内のすべての消去済みメタブロックは、EBMセクタ760内に記録され、MAPセクタ780はなく、MAP交換は行われない。MAP交換動作中に、EBB774に消去済みブロックを入力するMAPセクタは、送信元MAPセクタ782とみなされる。逆に、CBB776から消去済みブロックを受信するMAPセクタは、送信先MAPセクタ784とみなされる。MAPセクタが1つだけ存在する場合は、以下に規定するように、送信元および送信先MAPセクタの両方としての役割を果たす。以下の動作が、MAP交換中に行われる。1.送信元MAPセクタが、増分ポインタに基づいて選択される。2.送信先MAPセクタが、送信元MAPセクタ内ではない最初のCBBエントリ内のブロックアドレスに基づいて選択される。3.送信先MAPセクタが、CBB内の該当エントリによって規定されたように更新され、当該エントリは、CBBから除去される。4.別個の送信元MAPセクタが存在しなければ、更新された送信先MAPセクタが、MAPブロックに書き込まれる。5.送信元MAPセクタが、CBB内の該当エントリによって規定されたように更新され、当該エントリは、CBBから除去される。6.CBB内の残りのエントリが、EBBに付加される。7.EBBには、送信元MAPセクタから規定された消去済みブロックアドレスができる限り充填される。8.更新済みの送信元MAPセクタが、MAPブロック内に書き込まれる。9.更新済みのEBMセクタが、MAPブロック内に書き込まれる。リスト管理図18は、様々なリスト間の制御およびディレクトリ情報の分配および流れを示す。便宜のために、リストの要素間でエントリを移動する動作、またはエントリの属性を変更する動作は、[A]から[O]として図18に示され、以下のようなものである。[A]消去済みブロックがホストデータについての更新ブロックとして割り当てられる場合には、そのエントリのABL内にある属性は、消去済みABLブロックから開放更新ブロックに変更される。[B]消去されたブロックが制御ブロックとして割り当てられる場合には、ABL内のそのエントリが除去される。[C]ABLエントリが開放更新ブロック属性と共に作成される場合には、更新中の論理グループについての元メタブロックアドレスを記録するために、関連する元ブロックフィールドがエントリに付加される。この情報は、GATから取得される。[D]更新ブロックが閉鎖されると、そのエントリのABL内にある属性は、開放更新ブロックから閉鎖更新ブロックへ変更される。[E]更新ブロックが閉鎖されると、その関連する元ブロックは消去されて、ABL内にあるそのエントリ内の関連する元ブロックフィールドの属性は、消去済み元ブロックに変更される。[F]ABL充填動作中、同一の制御書き込み動作中にGAT内でアドレスが更新された閉鎖更新ブロックはどれでも、そのエントリがABLから除去される。[G]ABL充填動作中、閉鎖更新ブロックについてのエントリがABLから除去されると、その関連する消去済みの元ブロックについてのエントリが、CBLへ移動される。[H]制御ブロックが消去されると、それについてのエントリが、CBLへ追加される。[I]ABL充填動作中、消去済みブロックエントリが、EBBリストからABLへ移動され、消去済みABLブロックの属性が与えられる。[J]ABL充填動作中のすべての該当ABLエントリの修正後、ABL内のブロックアドレスが、ABBリスト内のブロックアドレスに取って代わる。[K]制御書き込み中にABL充填動作と並行して、CBL内の消去済みブロックについてのエントリが、CBBリストへ移動される。[L]MAP交換動作中、すべての該当エントリが、CBBリストからMAP送信先セクタへ移動される。[M]MAP交換動作中、すべての該当エントリが、CBBリストからMAP送信元セクタへ移動される。[N]MAP交換動作中の[L]および[M]に続いて、すべての残りのエントリが、CBBリストからEBBリストへ移動される。[O]MAP交換動作中の[N]に続いて、可能であれば、[M]において移動されたもの以外のエントリが、MAP送信元セクタから移動されて、EBBリストを充填する。論理/物理アドレス変換フラッシュメモリ内の論理セクタの物理位置を位置決定するために、図2に示されている論理/物理アドレス変換モジュール140は、論理/物理アドレス変換を行う。最近更新された論理グループを除いて、大量の変換を、フラッシュメモリ200またはコントローラRAM130内のGATキャッシュ内にあるグループアドレステーブルGATを使用して行うことになる可能性がある。最近更新された論理グループについてのアドレス変換は、主にコントローラRAM130内にある更新ブロックについてのアドレスリストを検索することを必要とすることになる。したがって、論理セクタアドレスについての論理/物理アドレス変換のための処理は、セクタが位置する論理グループに関連したブロックの種類に依存する。ブロックの種類には、変化のないブロックと、順次データ更新ブロックと、カオス的データ更新ブロックと、閉鎖データ更新ブロックとがある。図19は、論理/物理アドレス変換の処理を示すフローチャートである。基本的には、対応するメタブロックおよび物理セクタは、論理セクタアドレスを使用して、最初に、開放更新ブロックリストおよび閉鎖更新ブロックリストなどの様々な更新ディレクトリを検索することによって、位置決定される。関連するメタブロックが更新処理の一部でない場合、ディレクトリ情報がGATによって提供される。論理/物理アドレス変換は、以下のステップを含む。ステップ800:論理セクタアドレスが与えられる。ステップ810:コントローラRAM内の開放更新ブロックリスト614図15および18参照内の所定の論理アドレスが検索される。検索が失敗すると、ステップ820へ進み、そうでなければ、ステップ830へ進む。ステップ820:閉鎖更新ブロックリスト616内の所定の論理アドレスを検索する。検索が失敗すると、所定の論理アドレスはどの更新処理の一部でもないことになり、GATアドレス変換のためのステップ870へ進む。そうでなければ、閉鎖更新ブロックアドレス変換のためのステップ860へ進む。ステップ830:所定の論理アドレスを含む更新ブロックが順次であれば、順次更新ブロックアドレス変換のためのステップ840へ進む。そうでなければ、カオス的更新ブロックアドレス変換のためのステップ850へ進む。ステップ840:順次更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ880へ進む。ステップ850:カオス的更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ880へ進む。ステップ860:閉鎖更新ブロックアドレス変換を使用して、メタブロックアドレスを取得する。ステップ880へ進む。ステップ870:グループアドレステーブルGAT変換を使用して、メタブロックアドレスを取得する。ステップ880へ進む。ステップ880:メタブロックアドレスを物理アドレスに変換する。変換方法は、メタブロックが再リンクされているかどうかに依存する。ステップ890:物理セクタアドレスが取得される。様々なアドレス変換処理について、以下により詳細に説明する。順次更新ブロックアドレス変換ステップ840順次更新ブロックに関連した論理グループ内の対象論理セクタアドレスについてのアドレス変換は、以下のように、開放更新ブロックリスト614内の情報から直接達成される図15および18。1.リスト内のページタグフィールドおよび書き込みセクタの数フィールドから、対象論理セクタが更新ブロックにあるか、またはその関連する元ブロックにあるかどうかを判断する。2.対象論理セクタに適切なメタブロックアドレスが、リストから読み出される。3.メタブロック内のセクタアドレスが、適切なページタグフィールドから決定される。カオス的更新ブロックアドレス変換ステップ850カオス的更新ブロックに関連した論理グループ内の対象論理セクタアドレスについてのアドレス変換シーケンスは、以下の通りである。1.RAM内のカオス的セクタリストから、セクタが最近書き込まれたセクタであると判断される場合には、アドレス変換は、このリスト内のその位置から直接達成されてもよい。2.CBIブロック内の直近に書き込まれたセクタは、そのカオス的ブロックデータフィールド内に、対象論理セクタアドレスに該当するカオス的更新ブロックの物理アドレスを含む。また、その間接セクタインデックスフィールド内に、このカオス的更新ブロックに関連する最終書き込みCBIセクタのCBIブロック内のオフセットを含む図16A~16E参照。3.これらのフィールド内の情報は、RAM内にキャッシュされ、後続のアドレス変換中にセクタを読み出す必要をなくしている。4.間接セクタインデックスフィールドによってステップ3において識別されたCBIセクタが読み出される。5.直近にアクセスされたカオス的更新サブグループについての直接セクタインデックスフィールドは、RAM内にキャッシュされ、同一のカオス的更新ブロックに対する繰り返しのアクセスのためのステップ4における読み出しを行う必要をなくしている。6.ステップ4または5において読み出された直接セクタインデックスフィールドは、対象論理セクタアドレスを含む論理サブグループに関連するCBIセクタを識別する。7.対象論理セクタアドレスについてのカオス的ブロックインデックスエントリは、ステップ6において識別されたCBIセクタから読み出される。8.直近に読み出されたカオス的ブロックインデックスフィールドは、コントローラRAM内にキャッシュされてもよく、同一の論理サブグループに対する繰り返しのアクセスのためのステップ4およびステップ7における読み出しを行う必要をなくしている。9.カオス的ブロックインデックスエントリは、カオス的更新ブロックまたは関連する元ブロックのいずれかの内に対象論理セクタの位置を規定する。対象論理セクタの有効コピーが元ブロック内にあれば、元メタブロックおよびページタグ情報を使用して位置決定される。閉鎖更新ブロックアドレス変換ステップ860閉鎖更新ブロックに関連した論理ブロックループ内の対象論理セクタアドレスについてのアドレス変換は、以下のように、閉鎖ブロック更新リスト内の情報から直接達成することができる図18参照。1.対象論理グループに割り当てられたメタブロックアドレスは、リストから読み出される。2.メタブロック内のセクタアドレスは、リスト内のページタグフィールドから決定される。GATアドレス変換ステップ870論理グループが開放または閉鎖ブロック更新リストのいずれかによって参照されない場合には、GAT内のそのエントリは有効である。GATによって参照される論理グループ内の対象論理セクタアドレスについてのアドレス変換シーケンスは、以下の通りである。1.RAM内の使用可能なGATキャッシュの範囲を評価して、対象論理グループについてのエントリがGATキャッシュ内に含まれるかどうかを判断する。2.対象論理グループがステップ1において見つかった場合、GATキャッシュは、メタブロックアドレスおよびページタグを含む全グループアドレス情報を含み、対象論理セクタアドレスの変換が可能となる。3.対象アドレスがGATキャッシュ内にない場合、GATインデックスを対象GATブロックについて読みだして、対象論理グループアドレスに関するGATセクタの位置を識別しなければならない。4.最後にアクセスされたGATブロックについてのGATインデックスは、コントローラRAM内に保持され、フラッシュメモリからセクタを読み出す必要なくアクセスされてもよい。5.各GATブロックについてのメタブロックアドレスのリストと、各GATブロック内に書き込まれたセクタの数とが、コントローラRAM内に保持される。必要なGATインデックスがステップ4において使用可能でない場合、フラッシュメモリからすぐに読み出されてもよい。6.対象論理グループアドレスに関するGATセクタは、ステップ4またはステップ6において取得されたGATインデックスによって規定されたGATブロック内のセクタ位置から読み出される。GATキャッシュが、対象エントリを含むセクタの再分割部分によって更新される。7.対象セクタアドレスは、対象GATエントリ内のメタブロックアドレスおよびページタグフィールドから取得される。メタブロック/物理アドレス変換ステップ880メタブロックが再リンクされていることをメタブロックアドレスに関連したフラグが示されている場合、該当LTセクタがBLMブロックから読み出されて、対象セクタアドレスについての消去ブロックアドレスであると決定する。そうでなければ、消去ブロックアドレスは、メタブロックアドレスから直接決定される。制御データ管理図20は、メモリ管理の動作中に、制御データ構造に対して行われる動作の階層を示す。データ更新管理動作は、RAM内にある様々なリストに対して作用する。制御書き込み動作は、様々な制御データセクタおよびフラッシュメモリ内の専用ブロックに対して作用し、またRAM内のリストとデータを交換する。データ更新管理動作が、RAM内で、ABL、CBL、およびカオス的セクタリストに対して行われる。ABLは、消去済みブロックが更新ブロックまたは制御ブロックとして割り当てられる場合、または更新ブロックが閉鎖される場合に更新される。CBLは、制御ブロックが消去される場合、または閉鎖更新ブロックについてのエントリがGATに書き込まれる場合に更新される。更新カオス的セクタリストは、セクタがカオス的更新ブロックに書き込まれる場合に更新される。制御書き込み動作によって、RAM内の制御データ構造からの情報がフラッシュメモリ内の制御データ構造に書き込まれ、必要があれば、フラッシュメモリおよびRAM内の他の補助制御データ構造を更新する結果となる。これは、更新ブロックとして割り当てるべき消去済みブロックについてのエントリをABLがこれ以上含まない場合、またはCBIブロックが書き換えられる場合にトリガされる。好ましい実施形態において、ABL充填動作、CBLを空にする動作、およびEBMセクタ更新動作は、各制御書き込み動作中に行われる。EBMセクタを含むMAPブロックが一杯になると、有効EBMおよびMAPセクタが、割り当てられた消去済みブロックにコピーされ、以前のMAPブロックは消去される。各制御書き込み動作中に、1つのGATセクタが書き込まれ、かつ閉鎖更新ブロックリストがそれに従って修正される。GATブロックが一杯になると、GAT書き換え動作が行われる。CBIセクタが、前に説明したように、あるカオス的セクタ書き込み動作後に書き込まれる。CBIブロックが一杯になると、有効なCBIセクタが、割り当てられた消去済みブロックにコピーされ、以前のCBIブロックは消去される。MAP交換動作が、前に説明したように、EBMセクタ内のEBBリスト内に消去済みブロックエントリがこれ以上ない場合に行われる。MAPアドレスMAPAセクタは、MAPブロックの現在アドレスを記録し、MAPブロックが書き換えられる度に専用のMAPAブロックに書き込まれる。MAPAブロックが一杯になると、有効なMAPAセクタは、割り当てられた消去ブロックにコピーされ、以前のMAPAブロックは消去される。ブートセクタが、MAPAブロックが書き換えられる度に現在のブートブロック内に書き込まれる。ブートブロックが一杯になると、有効なブートセクタは、ブートブロックの現在のバージョンからバックアップバージョンへコピーされ、その後、現在のバージョンとなる。以前の現在のバージョンは消去されて、バックアップバージョンとなり、そこに有効なブートセクタは書き戻される。複数のメモリプレーンに渡って分散されたメモリの配列図4および図5A~5Cに関連して前に説明したように、性能を向上させるために、複数のメモリプレーンが並列に動作される。基本的には、各プレーンは、プレーンの範囲のメモリセルの対応するページを並列に処理するための読み出しおよびプログラム回路の一部としての独自のセンス増幅器のセットを有する。複数のプレーンが組み合わされると、複数のページが並列に動作されてもよく、さらに性能が高まる。本発明の他の態様において、消去可能なブロックに組織化され、かつ論理ユニットを複数のプレーンに並列に読み出しまたはプログラムすることができるように複数のメモリプレーンから構成されるメモリアレイについて、所定のメモリプレーンに記憶された第1のブロックの元論理ユニットが更新される場合、更新済みの論理ユニットが元論理ユニットと同一のプレーンに維持されるための措置が講じられる。これは、更新済み論理ユニットを、同一のプレーン内ではあるが第2のブロックの次に使用可能な位置に記録することによって達成される。好ましくは、論理ユニットは、所定の論理ユニットのすべてのバージョンが検知回路の同一のセットによって処理されるように、プレーン内の他のバージョンにおけるのと同一のオフセット位置で記憶される。本発明の好ましい実施形態において、最後にプログラムされたメモリユニットから次に使用可能なプレーン配列されたメモリユニットへの介在ギャップが、論理ユニットの現在のバージョンに従ってパディングされる。パディングは、論理ユニットから論理的に先行する論理ユニットの現在のバージョンが次に使用可能なプレーン配列されたメモリユニットに記憶された状態で、最後にプログラムされた論理ユニットから論理的に従う論理ユニットの現在のバージョンでギャップを埋めることによって達成される。このように、ガーベッジコレクション動作において、論理ユニットの最終バージョンを異なるプレーンから取り出すという、性能を低下させる結果を生じる動作が必要ないように、ある論理ユニットのすべてのバージョンが、同一プレーン内に、元のものと同一のオフセットを有して保持される。好ましい実施形態において、プレーン上の各メモリユニットは、最終バージョンによって更新またはパディングされる。よって、複数のプレーンに渡る並列処理において、論理ユニットは、さらに再構成をする必要なく、論理的な順次順序となる。この手法は、論理グループの論理ユニットの最終バージョンをプレーン上で再構成することを可能にし、互いに異なるメモリプレーンから最終バージョンを収集する必要性を回避することによって、カオス的ブロックの統合化のための時間を削減する。これは、ホストインターフェイスに関する性能仕様によってメモリシステムによるセクタ書き込み動作の完了に対する最大待ち時間が規定される場合に、有利である。図21は、複数のメモリプレーンから構成されるメモリアレイを示す。メモリプレーンは、同一のメモリチップから、または複数のメモリチップからであってもよい。各プレーン910は、メモリセルのページ914を並列に処理するための読み出しプログラム回路912の独自のセットを有する。一般性を失うことなく、図に示されている例において、メモリアレイは、並列に動作する4つのプレーンを有する。一般的に、論理ユニットは、ホストシステムによるアクセスの最小単位である。典型的には、論理ユニットは、512バイトのサイズのセクタである。ページは、プレーンにおける並列読み出しまたはプログラミングの最大単位である。典型的には、論理ページは、1つ以上の論理ユニットを含む。したがって、複数のプレーンを組み合わせる場合に、並列読み出しまたはプログラミングの最大総計ユニットを、メモリセルのメタページとみなすことができ、メタページは、複数の各プレーンからなるページによって構成される。例えば、MP0などのメタページは、各プレーンP0,P1,P2,およびP3からの4つのページを有し、論理ページLP0,LP1,LP2,およびLP3を並列に記憶する。よって、メモリの読み出しおよび書き込み性能は、1つのプレーンにおいてのみ動作するのと比較して4倍に増加する。メモリアレイは、MB0,MBjなどのメタブロックにさらに組織化され、各メタブロック内のすべてのメモリセルは、ユニットとして共に消去可能である。MB0などのメタブロックは、複数のメモリ位置から構成され、LP0~LPN1などのデータの論理ページ914を記憶するためのものである。メタブロック内の論理ページは、メタブロックに充填される順序に従って、所定のシーケンスで、4つのプレーンP0,P1,P2,およびP3に渡って分散される。例えば、論理ページが論理的な順次順序で充填される場合には、プレーンは、第1のページは第1のプレーンに、第2のページは第2のプレーンに、というような周期的な順序で巡回される。最後のプレーンに到達後、充填は周期的に戻って、次のメタページにおいて第1のプレーンから再開する。このように、論理ページの連続実行は、すべてのプレーンが並列に動作される場合に、並列にアクセス可能である。一般的に、並列に動作するW個のプレーンがあり、メタブロックが論理的な順次順序で充填される場合に、メタブロック内のk番目の論理ページは、x=kMODWの場合のプレーンxにある。例えば、プレーンが4つ、すなわちW=4であり、ブロックを論理的な順次順序で充填する場合、図21に示されているように、5番目の論理ページLP5が5MOD4によって与えられるプレーン、すなわちプレーン1内にある。各メモリプレーンにおけるメモリ動作は、読み出し/書き込み回路912のセットによって行われる。各読み出し/書き込み回路へのデータおよびそこからのデータは、コントローラ920の制御下で、データバス930を介して転送される。コントローラ920内のバッファ922は、データ転送をデータバス930を介してバッファするのを助ける。特に、第1のプレーンにおける動作が第2のプレーン内のデータに対するアクセスを必要とする場合には、2つの段階の処理が必要である。まず、データが第2のプレーンからコントローラによって読み出され、その後、データバスおよびバッファを介して第1のプレーンへ転送される。実際、たいていのメモリ構成において、2つの互いに異なるビットライン間のデータ転送は、データバス920を通じてのデータのやり取りをも必要とする。極少なくとも、これには、あるプレーンにおける読み出し/書き込み回路のあるセットからの転送と、別のプレーンにおける読み出し/書き込み回路の他のセットへの転送を伴うものであった。プレーンが互いに異なるチップからである場合には、チップ間の転送が必要となる。本発明は、性能を最大化するために、あるプレーンによる他のプレーンからのアクセスを回避するようなメモリブロック管理についての構造および手法を提供する。図21に示されているように、メタページは、複数の論理ページによって形成され、プレーン毎に1つある。各論理ページは、1つ以上の論理ユニットからなってもよい。データが複数のプレーンに渡って論理ユニット毎にブロックに記録されているので、各論理ユニットは、4つのメモリプレーンのうちの1つに該当することになる。プレーン配列の問題が生じるのは、論理ユニットを更新する場合である。この例において、図示の目的のために、論理ユニットは、512バイトの論理セクタとされ、論理ページも、論理ユニット全体である。フラッシュメモリは、最初に全体のブロックを消去することなくブロックの一部を書き換えることができないので、論理ページに対する更新は、既存の位置には書き込まれないが、ブロックの未使用の位置に記録される。その後、論理ユニットの以前の複数のバージョンが廃止とみなされる。数多くの更新の後、ブロックは、更新されることによって廃止となった数多くの論理ユニットを含む場合がある。その後、ブロックは、汚いと称され、ガーベッジコレクション動作が、この汚い論理ユニットを無視するが、各個別の論理ユニットの最新バージョンを収集して、それらを論理的な順次順序で1つ以上の新規ブロックに再記録する。その後、汚いブロックは、消去されリサイクルされる。更新済みの論理ユニットがブロック内の次に未使用の位置に記録される場合、一般的には、以前のバージョンと同一のメモリプレーンに記録されない。統合化またはコンパクト化などのガーベッジコレクション動作の場合、論理ユニットの最新バージョンは、元のと同一のプレーン内に再記録されて、元の順序を維持する。しかし、最新バージョンを他のプレーンから取り出さなければならない場合には、性能が低下する。よって、本発明の他の態様によれば、所定のプレーンに記憶された第1のブロックの元論理ユニットが更新される場合、更新済みの論理ユニットが元論理ユニットと同一のプレーンに維持されるための措置が講じられる。これは、更新済み論理ユニットを、同一のプレーン内ではあるが第2のブロックの次に使用可能な位置に記録することによって達成される。好ましくは、最後にプログラムされたメモリユニットから次に使用可能なプレーン配列されたメモリユニットへの介在ギャップが、元ブロック内の元論理ユニットと同一の相対位置内の論理ユニットの現在のバージョンでパディングすなわち、コピーによって充填される。図22Aは、本発明の一般的な実施に係る、プレーン配列を伴う更新の方法を示すフロー図である。ステップ950:ブロックに組織化された不揮発性メモリにおいて、各ブロックは、共に消去可能なメモリユニットに分割され、各メモリユニットは、データの論理ユニットを記憶するためのものである。ステップ952:複数のメモリプレーンからメモリを構成し、各プレーンは、並列にメモリページを処理するための検知回路のセットを有し、前記メモリページは、1つ以上のメモリユニットを含む。ステップ954:論理ユニットの第1のバージョンを第1の順序に従って第1のブロックのメモリユニットに記憶し、各第1のバージョンの論理ユニットは、メモリプレーンのうちの1つに記憶される。ステップ956:論理ユニットの後続のバージョンを第1の順序とは異なる第2の順序に従って第2のブロックへ記憶し、各後続のバージョンは、論理ユニットのすべてのバージョンが検知回路の同一のセットによって同一のプレーンからアクセス可能であるように、第1のバージョンと同一プレーン内で次に使用可能なメモリユニットに記憶される。図22Bは、図22Aに示されているフロー図における更新を記憶するステップの好ましい実施形態を示す。ステップ956’は、ステップ957、ステップ958、およびステップ959を含む。ステップ957:各ブロックをメタページに分割し、各メタページは、各プレーンのページから構成される。このステップは、どの記憶するステップの前でも行うことができる。ステップ958:論理ユニットの後続のバージョンを、第1の順序とは異なる第2の順序に従って第2のブロックへ記憶し、各後続のバージョンは、メタページ内の第1のバージョンと同一のオフセットを有する次に使用可能なメモリユニット内に記憶する。ステップ959:論理ユニットの後続のバージョンと並行して、前記次に使用可能なメモリユニットに先立つあらゆる未使用のメモリユニットを、メタページ毎に、論理ユニットの現在のバージョンを第1の順序に従ってコピーすることによってパディングする。図23Aは、プレーン配列を考慮しないで順次更新ブロックへ順次順序で書き込まれる論理ユニットの一例を示す。この例は、各論理ページが、LS0,LS1などの論理セクタの大きさであることを示している。4プレーンの例において、MB0などの各ブロックは、メタページMP0,MP1,に分割され、MP0などの各メタページは、それぞれプレーンP0,P1,P2,およびP3からのLS0,LS1,LS2,およびLS3のような4つのセクタを含む。したがって、ブロックは、セクタ毎に、プレーンP0,P1,P2,およびP3内の論理ユニットに周期的な順序で充填される。ホスト書き込み動作1において、論理セクタLS5~LS8内のデータが更新中である。LS5’~LS8’となった更新済みのデータが、新規に割り当てられた更新ブロックに、最初に利用可能な位置から記録される。ホスト書き込み動作2において、論理セクタLS9~LS12内のデータのセグメントが更新中である。LS9’~LS12’となった更新済みのデータは、最終書き込みが終了した箇所に直接続く位置にある更新ブロック内に記録される。2つのホスト書き込みは、更新データが論理的な順次順序で更新ブロック、すなわちLS5’~LS12’に記録されているようになっていることがわかる。更新ブロックは、論理的な順次順序で充填されているので、順次更新ブロックとみなされる。更新ブロックに記録された更新データは、元ブロック内の対応するデータを廃止する。しかし、更新論理セクタは、次に使用可能な位置に従うがプレーン配列には関係なく、更新ブロックに記録されている。例えば、セクタLS5は、元々はプレーンP1内に記録されているが、更新されたLS5’は、今やP0に記録されている。同様に、他の更新セクタもすべて位置関係が合っていない。図23Bは、プレーン配列を考慮しないでカオス的更新ブロックへ非順次順序で書き込まれる論理ユニットの一例を示す。ホスト書き込み動作1において、元メタブロック内に記憶された所定の論理グループの論理セクタLS10~LS11が更新される。更新済み論理セクタLS10’~LS11’は、新たに割り当てられた更新ブロックに記憶される。この時点で、更新ブロックは順次的である。ホスト書き込み動作2において、論理セクタLS5~LS6がLS5’~LS6’に更新されて、最終書き込みの直後の位置にある更新ブロック内に記録される。これにより、更新ブロックは、順次的からカオス的なものに変換される。ホスト書き込み動作3において、論理セクタLS10’は再び更新されて、更新ブロックの次の位置にLS10’’として記録される。この時点で、更新ブロックのLS10’’は、元ブロック内のLS10に取って代わった以前の記録におけるLS10’に取って代わる。ホスト書き込み動作4において、論理セクタLS10’’内のデータは再び更新され、更新ブロックの次の位置にLS10’’’として記録される。よって、LS10’’’が、論理セクタLS10についての現在最新かつ唯一有効なバージョンである。LS10のすべての以前のバージョンは今や廃止される。ホスト書き込み動作5において、論理セクタLS30のデータが更新され、更新ブロック内にLS30’として記録される。この例において、論理グループ内の論理ユニットを、任意の順序かつ任意の繰り返しで、カオス的更新ブロック内に書き込むことができる。繰り返すが、更新論理セクタは、次に使用可能な位置に従うがプレーン配列には関係なく、更新ブロックに記録されている。例えば、セクタLS10は、元々はプレーンP2すなわち、MP2,第3のプレーン内に記録されているが、更新されたLS10’は、今やP0すなわち、MP0’,第1のプレーン内に記録されている。同様に、ホスト書き込み動作3において、論理セクタLS10’は再びLS10’’に更新されて、次に使用可能な位置、つまり同じくプレーンP0MP1’内の第1のプレーンに置かれる。よって、一般的に、ブロックの次に使用可能な位置に更新セクタを記録すると、更新済みのセクタが以前のバージョンとは異なるプレーンに記録されることになる場合があることがわかる。パディングによって介在ギャップが埋められた、プレーン配列された順次更新ブロック図24Aは、本発明の好ましい実施形態に係る、プレーン配列およびパディングを伴う図23Aの順次更新の例を示す。ホスト書き込み動作1において、LS5’~LS8’としての更新済みデータは、第1の使用可能なプレーン配列の位置から始めて、新規に割り当てられた更新ブロックに記録される。この場合、LS5は、元々はP1、すなわちメタページの第2のプレーン内にある。したがって、LS5’~LS7’は、更新ブロックの第1の使用可能なメタページMP0内の対応するプレーンにプログラムされることになる。同時に、MP0’内の未使用の第1のプレーンのギャップは、元ブロックのメタページ内でLS5に先立つ論理セクタLS4の現在のバージョンでパディングされている。元のLS4は、その後、廃止データとして扱われる。残りのLS8’は、その後、次のメタページMP1’の第1のプレーンに記録されて、プレーン配列される。ホスト書き込み動作2において、LS9’~LS12’としての更新済みのデータは、次に使用可能なプレーン配列の位置における更新ブロック内に記録される。したがって、LS9’は、次に使用可能なプレーン配列のメモリユニット、すなわちMP1’の第2のプレーンに記録される。この場合、ギャップは生じず、パディングは必要ない。更新ブロックは、論理的な順次順序で充填されているので、順次更新ブロックとみなされる。さらに、各更新論理ユニットはその元のものと同じプレーン内にあるので、プレーン配列されている。介在ギャップを伴う、プレーン配列されたカオス的更新ブロック図24Bは、本発明の好ましい実施形態に係る、プレーン配列は伴うがパディングは伴わない図23Bのカオス的更新の例を示す。ホスト書き込み動作1において、更新済み論理セクタLS10’~LS11’が新規に割り当てられた更新ブロック内に記録される。これらを次に使用可能なメモリユニットに記憶する代わりに、これらは、次に使用可能なプレーン配列のメモリユニットに記憶される。LS10’およびLS11’は元々はプレーンP2およびP3元ブロックのMP2の第3および第4のプレーン内にそれぞれ記憶されていたので、次に使用可能なプレーン配列のメモリユニットは、更新ブロックのMP0’の第3および第4のプレーン内にあることになる。この時点で、更新ブロックは非順次的であり、メタページMP0’のページは、未充填、未充填、LS10’およびLS11’という順序で充填される。ホスト書き込み動作2において、論理セクタLS5~LS6は、LS5’~LS6’に更新されて、次に使用可能なプレーン配列の位置における更新ブロック内に記録される。よって、第2P1および第3P2のプレーンまたは元ブロックのMP1のメモリユニットにあるLS5’~LS6’は、更新ブロックにおける次に利用可能なメタページMP1’内の対応するプレーンにプログラムされることになる。これにより、MP1’内の先行する未使用の第1のプレーンはそのままとされる。ホスト書き込み動作3において、論理セクタLS10’は再び更新されて、LS10’’として更新ブロックの次にプレーン配列された位置に記録される。よって、これは次に使用可能な第3のプレーンである、MP2’に書き込まれることになる。これにより、MP1’内の最終プレーンの先行ギャップと、MP2’の最初の2つのプレーンとは、そのままとされる。これにより、MP0’内のLS10’が廃止される。ホスト書き込み動作4において、論理セクタLS10’’内のデータは再び更新されて、LS10’’’として更新ブロック内のメタページMP2’の次に使用可能な第3のプレーン内に記録される。よって、LS10’’’は、論理セクタLS10についての現在最新かつ唯一有効なバージョンである。これにより、MP2’内の最終プレーンと、MP3’内の最初の2つのプレーンとからなるギャップは、そのままとされる。ホスト書き込み動作5において、論理セクタLS30内のデータは更新され、LS30’として更新ブロック内に記録される。元のLS30はP2またはメタページの第3のプレーン内にあるので、更新ブロック内の次に使用可能な第3のプレーンに書き込まれることになる。この場合、MP4’の第3のプレーンとなる。MP3’の最後のプレーンからMP4’の最初の2つのプレーンにかけてギャップが形成される。よって、この例は、論理グループ内の論理セクタを、カオス的更新ブロック内に、任意の順序でかつプレーン配列となるような任意の繰り返しによって書き込むことができることを示している。後続のガーベッジコレクション動作の際に、すべてのバージョン、特に所定の論理セクタの最新バージョンは、検知回路の同一のセットによって都合よく処理されるようになる。パディングによって介在ギャップが埋められた、プレーン配列されたカオス的更新ブロック図24Cは、本発明の他の好ましい実施形態に係る、プレーン配列およびパディングを伴う図23Bのカオス的更新の例を示す。動作は、介在ギャップがパディングによってまず埋められる以外は、図24Bに示されているものと同様である。ホスト書き込み動作1において、メタページMP0’の第1および第2の未使用のプレーンによって形成されたギャップは、元ブロック内にあるLS8およびLS9の最新バージョンでまずパディングされる。これにより、元ブロック内のLS8およびLS9が廃止される。この時点で、更新ブロックは順次的であり、メタページMP0’がLS8,LS9,LS10’,およびLS11’の順で充填される。ホスト書き込み動作2において、MP1’内の先行する未使用の第1のプレーンによってギャップが形成され、まずLS4でパディングされる。これにより、元ブロック内のLS4が廃止されることになる。前述したように、第2の書き込みは、更新ブロックを順次的からカオス的なものに変換する。ホスト書き込み動作3において、未使用の、MP1’内の最後のプレーンと、MP2’の最初の2つのプレーンによってギャップが形成される。MP1’の最後のプレーンは、最後にプログラムされたLS6’に続くLS7でパディングされ、MP2’の最初の2つのプレーンは、LS10に先行する論理ユニット、すなわちLS8およびLS9でパディングされる。これにより、MP0’内のLS10’と、元ブロック内のLS7~LS9とが廃止される。ホスト書き込み動作4において、MP2’内の最後のプレーンと、MP3’内の最初の2つのプレーンとからなるギャップが形成される。MP2’の最後のプレーンは、メタページMP2’内の最後に書き込みされたLS10’’に続く論理ユニットの最新バージョンであるLS11’によってパディングされる。MP3’の最初の2つのプレーンは、メタページMP3’内のLS10’’’に先行する論理ユニットとして、LS8およびLS9によってそれぞれパディングされる。ホスト書き込み動作5において、MP3’の最後のプレーンからMP4’の2つのプレーンにかけてのギャップは、それに応じて、すなわちそれぞれLS11’,LS28,およびLS29でパディングされることになる。よって、この例は、論理グループ内の論理セクタを、カオス的更新ブロック内に、任意の順序でかつプレーン配列となるような任意の繰り返しによって書き込むことができることを示している。好ましい実施形態において、メタページは、個別のプレーンからのページの周期的な実行を含む。メタページは並列に読み出しまたはプログラム可能なので、各ホスト更新をメタページの粒度で実施するのが得策である。もしあれば、パディングが、メタページ毎に、更新済み論理ユニットと共に記録される。図24Aおよび図24Cの例に示されている実施形態において、各ホスト書き込み中に、更新がプログラムされるべきプレーン配置されたメモリユニットに先行する未使用のメモリユニットに対して、パディングが行われる。最後にプログラムされたメモリユニットに続く任意の未使用のメモリユニットの動作は、次のホスト書き込みまで延期される。通常、任意の先行する未使用のメモリユニットが各メタページの境界内でパディングされる。言い換えれば、先行するギャップが2つのメタページにまたがる場合には、パディングは、各メタページに適切な論理的な順次順序で、各メタページに対して行われるが、境界に渡る連続性とは見なされない。ブロックの統合化の場合には、最後の書き込みメタページが部分的に書き込まれていれば、パディングによって完全に充填される。他の実施形態において、任意の部分的に充填されたメタページが、次のメタページに移動する前に完全にパディングされる。メモリユニットの粒度個々のメモリ構成によってサポートされる柔軟性に依存して、読み出しまたはプログラムのユニットを変更することが可能である。個々のプレーンの個々の性質によって、あるメタページ内の個々のプレーンからの各ページを個別に読み出しまたはプログラムすることができる。前に説明した例では、プログラムの最大ユニットは、各プレーン内のページである。メタページ内において、すべてのページより少ない数の部分メタページプログラミングが可能である。例えば、メタページの最初の3ページをプログラムし、その後に4ページ目をプログラムすることが可能である。また、プレーンレベルにおいて、1つ以上のメモリユニットを含んでもよい。各メモリユニットがデータのセクタを記憶することができる場合は、物理ページは、1つ以上のセクタを記憶してもよい。メモリ構成によっては、部分ページプログラミングをサポートしているものもあり、ページ内において選択されたメモリユニットのプログラミングを禁止することによって、選択された論理ユニットを、複数のプログラミングパスに渡って、互いに異なるときに個別にプログラムするようにしてもよい。論理グループのカオス的更新についてのメモリプレーン内における論理ユニット配列ブロックメモリ管理システムにおいて、論理ユニットの論理グループが、元ブロック内での論理的な順次順序で記憶される。論理グループが更新される場合に、論理ユニットの後続のバージョンが更新ブロックに記憶される。論理ユニットがカオス的にすなわち、非順次に更新ブロックに記憶される場合、最終的にはガーベッジコレクションが行われ、元ブロック内の論理ユニットの最新版と更新ブロックとを収集して、それらを新規の元ブロックに順次に統合化する。ガーベッジコレクション動作がさらに効率的となるのは、所定の論理ユニットの更新済みバージョンが、すべてのバージョンが検知回路の同一のセットによってアクセス可能であるように、元ブロック内の元バージョンに揃って、更新ブロック内にすべて記憶される場合である。本発明の他の態様によれば、前述したブロックメモリ管理システムにおいて、メモリが一連のメモリページに組織化される場合に、メモリユニットの各ページは、検知回路のセットによって並列に処理され、所定の論理ユニットのすべてのバージョンは、記憶されるページ内の同一のオフセット位置をすべてが有する場合には、整列される。図25は、各ページが2つの論理セクタのような2つの論理ユニットを記憶するための2つのメモリユニットを含むメモリ組織の一例を示す。元ブロックにおいて、論理セクタは論理的な順次順序で記憶されているので、論理セクタLS0およびLS1は、ページP0に記憶され、論理セクタLS2およびLS3は、ページP1に記憶され、論理セクタLS4およびLS5は、ページP3に記憶されるといった具合である。この2セクタページにおいて、左から1番目のセクタは、ページオフセット0を有し、2番目のセクタは1のページオフセットを有することがわかる。元ブロック内に順次的に記憶された論理セクタの論理グループを更新する場合、更新済み論理セクタは、更新ブロック内に記録される。例えば、論理セクタLS2は、ページP0内に、元ブロック内のオフセット0で存在する。最初の書き込みにおいて、LS2がLS2’に更新されると、同じページオフセット0を有する更新ブロック内の最初に使用可能な位置に記憶されることになる。これは、ページP0’の最初のメモリユニット内であることになる。第2の書き込みにおいて、LS5はLS5’に更新され、同じページオフセット1を有する更新ブロック内の最初に使用可能な位置に記憶されることになる。これは、ページP1’のオフセット1を有する第2のメモリユニット内であることになる。しかし、LS5’を記憶する前に、P0’内のオフセット1とP1’内のオフセット0とを有する未使用のメモリユニットは、少なくとも各ページ内で論理的な順次順序を維持するような論理セクタの最新バージョンをコピーすることによって、最初にパディングされることになる。この場合、LS3がP0’内のオフセット1の位置にコピーされ、LS4がP1’内のオフセット0の位置にコピーされることになる。第3の書き込みにおいて、LS2’が再びLS2’’に更新されると、P2’のオフセット0内に記憶されることになる。第4の書き込みにおいて、LS22およびLS23がLS22’およびLS23’にそれぞれ更新されると、P3’のオフセット0および1内にそれぞれ記憶されることになる。しかし、その前に、P2’内のオフセット1を有する未使用のメモリユニットはLS3でパディングされる。前述した更新シーケンスは、あるページ内の個別のセクタをプログラムすることが可能であるものとしている。部分ページプログラミングをサポートしないメモリ構成によっては、あるページ内のすべてのセクタは、共にプログラムされなければならない。その場合、第1の書き込みにおいて、LS2’およびLS3は、P0’に共にプログラムされる。第2の書き込みにおいて、LS4およびLS5’は、P1’に共にプログラムされる。第3の書き込みにおいて、LS2’’およびLS3は、P2’に共にプログラムされるといった具合である。メタページ内でのプレーン配列代わりに、プログラムのユニットは、メタページの粒度を有してもよい。カオス的更新ブロックへの書き込みの粒度がペタページとなる場合には、図16Aおよび16Bに関連して説明したCBIブロック内のエントリは、セクタの代わりにメタページに関連してもよい。粒度が上昇すると、カオス的更新ブロックに対して記録されなければならないエントリ数は減少し、直接インデックスを除去して、単一のCBIセクタがメタブロック毎に使用することができるようになる。図26Aは、各ページが1つではなく2つのセクタを含む以外は、図21のメモリ構造と同様のものである。よって、メタページMP0は、今やデータの2つの論理ユニットを記憶することができる各ページを有することがわかる。各論理ユニットがセクタであれば、論理セクタが、LS0およびLS1をプレーンP0に、LS3をプレーンP1にという具合に、MP0内に順次に記憶される。図26Bは、模式的に線形に配置されたメモリユニットを有する、図26Aに示されているメタブロックを示す。図21の単一セクタページと比較すると、論理セクタは、2つのセクタが各ページにあるように、4つのページ内に周期的に記憶される。一般的に、並列に動作するW個のプレーンがあり、ページ毎にK個のメモリユニットがあり、メタブロックが論理的な順次順序で充填される場合に、メタブロック内のk番目の論理ページは、x=k’MODWの場合のプレーンxにあり、ここでk’=INTk/Kである。例えば、プレーンが4つ、すなわちW=4であり、ページ毎に2セクタ、すなわちK=2であれば、k=5の場合、つまり第5の論理セクタLS5のことだが、図24Aに示されているように、2MOD4によって与えられるプレーン、すなわち、プレーン2内にあるkとになる。一般的に、前に説明したプレーン配列を実施するために同一の原則が当てはまる。前に示した例は、複数プレーンの構成におけるプレーンを有するページ配列についてのものである。複数のセクタを有するページの場合には、ページ内にセクタ配列を維持することも利点となる。このように、検知回路の同一のセットを、同一の論理セクタの互いに異なるバージョンに対して都合よく使用することができる。移転またはあるセクタの読み出し変更書き込みのような動作が、効率的に行われる。ページ内でセクタ順序を整列する場合に、ページをプレーンに整列するのと同じ技術を使用することができる。また、実施形態によっては、任意の介在ギャップがパディングされてもよいし、されなくてもよい。パディングなしの論理ユニットまたはプレーンの配列図27は、ある位置から他の位置へコピーすべき論理ユニットをパディングしない、更新ブロック内のプレーン配列のための代替の手法を示す。4つのプレーンのうちの更新ブロックと交差する部分は、ホストから受信するプレーン配列された更新済み論理ユニットを収集する4つのバッファとみなしてもよい。ホストから受信された各論理ユニットは、適切なバッファの次に使用可能なメモリユニット内にパディングすることなくプログラムされる。ホストから受信される論理ユニットアドレスのシーケンスに従って、異なる数の論理ユニットが各プレーンにプログラムされている可能性もある。カオス的更新ブロックMB’1は、MP’0の場合のように、論理メタページのすべての論理ユニットの更新済みバージョンを含んでもよい。また、これは、MP’1の場合のように、メタページのすべての論理ユニットより少ない論理ユニットを含んでもよい。MP’1の場合、失われた論理ユニットLS4は、対応する元ブロックMB0から取得することができる。この代替の手法は、メモリ構成が各プレーンから任意の論理ページを並列に読み出すことをサポートしている場合に特に効率的である。このように、個々の論理ページが同列からのものでなくても、あるメタページのすべての論理ページを単一の並列読み出し動作で読み出すことができる。フェーズ化されたプログラムエラー処理あるブロック内にプログラム障害がある場合、このブロックに記憶すべきすべてのデータは、典型的には他のブロックに移動され、障害ブロックは不良と印付けされる。障害が生じる動作についてのタイミング仕様によっては、記憶済みデータを他のブロックにさらに移動するのに十分な時間がない場合もある。最悪の場合は、通常のガーベッジコレクション動作中のプログラム障害であり、すべてのデータを他のブロックへ移転するために、他の同様のガーベッジコレクション動作が必要となる。この場合、所定のホスト/メモリ装置の特定の書き込み待ち時間限度が破られることもある。なぜなら、典型的には、2つのガーベッジコレクション動作ではなく1つのガーベッジコレクション動作に対応するように設計されているからである。図28は、統合化動作中に不良ブロックにプログラム障害が生じた場合に、統合化動作が他のブロックに対して繰り返される手法を示す。この例において、ブロック1は、論理グループの完全な論理ユニットを論理的な順次順序で記憶する元ブロックである。図示の目的から、元ブロックは、セクションA,B,C,およびDを含み、それぞれは、論理ユニットのサブグループを記憶している。グループのある論理ユニットをホストが更新する場合に、論理ユニットのより新しいバージョンが更新ブロック、すなわちブロック2に記録される。更新ブロックに関連して前に説明したように、ホストによっては、更新は、論理ユニットを順次または非順次カオス的順序で記録することもできる。最終的には、更新ブロックは、一杯または何らかの他の理由で閉鎖されて、さらなる更新を受信することができなくなる。更新ブロックブロック2が閉鎖されると、更新ブロックまたは元ブロックブロック1のいずれかにある論理ユニットの現在のバージョンが、新規のブロックブロック3に統合化されて、この論理グループについての新規の元ブロックを形成する。この例は、論理ユニットのより新規のバージョンがセクションBおよびDに含まれている更新ブロックを示す。便宜上、セクションBおよびDは、ブロック2内であり、必ずしも記録された位置ではないがブロック1内の元の位置に整列する位置に、模式的に示されている。統合化動作において、元々はブロック1内にある論理グループのすべての論理ユニットの現在のバージョンは、順次順序で、統合化ブロックブロック3に記録される。よって、セクションAの論理ユニットがまずブロック1からブロック3へコピーされ、続いてセクションBの論理ユニットがブロック2からブロック3へコピーされる。この例において、セクションCの論理ユニットをブロック1からブロック3へコピーする場合には、ブロック3の不良がプログラム障害という結果となる。プログラム障害を処理する1つのやり方としては、新規のブロックブロック4に対して統合化処理を再開することである。セクションA,B,C,およびDは、ブロック4にコピーされ、その後、不良ブロック3は廃棄される。しかし、これは、2つの統合化動作を並行して行うという意味になってしまい、論理ユニットで一杯の2つのブロックをコピーするという結果となってしまう場合もある。メモリ装置は、ある動作を完了させるのに特定の時間的余裕を有している。例えば、ホストがメモリ装置に対して書き込む場合に、書き込み動作が、書き込み待ち時間として知られる特定の時間内に完了することが期待されている。メモリカードのようなメモリ装置が、ホストからのデータを書き込むのに忙しい間は、BUSY状態をホストに対して知らせる。BUSY状態が書き込み待ち期間よりも長く続く場合には、ホストは、書き込み動作をタイムアウトして、例外またはエラーを書き込み動作に対して登録する。図29は、書き込み更新動作および統合化動作を完了するのに十分な時間を取れるようなタイミングまたは書き込み待ち時間を伴うホスト書き込み動作を模式的に示す。ホスト書き込み動作は、ホストデータを更新ブロックに書き込む更新動作972図29Aを完了するのに十分な時間を提供することになる書き込み待ち時間TWを有する。前にブロック管理システムにおいて説明したように、更新ブロックに対するホスト書き込みは、統合化動作をトリガする場合がある。よって、タイミングは、更新動作972に加えて、統合化動作974図29Bも考慮している。しかし、失敗した動作に応答して統合化処理を新規に再開しなければならないとすると、非常に多くの時間がかかり、指定された書き込み待ち時間を超える場合がある。本発明の他の態様によれば、ブロック管理システムを伴うメモリにおいて、時間が重視されるメモリ動作中のブロック内のプログラム障害が、ブレークアウトブロック内のプログラミング動作を継続することによって処理される。後のあまり危機的でないときに、中断前に障害ブロック内に記憶されたデータは他のブロックに転送され、この他のブロックもブレークアウトブロックであってもよい。その後、障害ブロックを廃棄することができる。このように、不良ブロックが生じる場合に、データを失うこともなく、不良ブロック内に記憶されたデータを直ちに転送しなければならないことによって指定された時間制限を超えることもなく、不良ブロックを処理することができる。このエラー処理は、危機的な最中にすべての動作を新規のブロックに対して繰り返す必要がないようにするために、ガーベッジコレクション動作にとっては特に重要である。その後、都合のよいときに、不良ブロックからのデータは、他のブロックへ移転されることによって復旧される。図30は、本発明の一般的な手法に係る、プログラム障害処理のフローチャートを示す。ステップ1002:不揮発性メモリをブロックに組織化し、各ブロックは、共に消去可能なメモリユニットに分割され、各メモリは、データの論理ユニットを記憶するためのものである。プログラム障害処理第1のフェーズステップ1012:データの論理ユニットのシーケンスを第1のブロックに記憶する。ステップ1014:数多くの論理ユニットを記憶した後の第1のブロックにおける記憶障害に応じて、後続の論理ユニットを第1のブロック用のブレークアウトブロックとしての役割を果たす第2のブロックに記憶する。プログラム障害処理最終のフェーズステップ1020:予め定められたイベントに応じて、第1のブロック内に記憶された論理ユニットを第3のブロックへ転送し、第3のブロックは、第2のブロックと同一であってもなくてもよい。ステップ1022:第1のブロックを破棄する。図31Aは、第3の最終移転ブロックが第2のブレークアウトブロックとは異なる、プログラム障害処理の一実施形態を示す。フェーズIにおいて、論理ユニットのシーケンスが、第1のブロックに記録されている。論理ユニットがホスト書き込みからであれば、第1のブロックは、更新ブロックであるとみなされてもよい。論理ユニットが統合化動作またはコンパクト化動作からであれば、第1のブロックは、移転ブロックであるとみなされてもよい。ある時点でブロック1にプログラム障害が発生すると、ブレークアウトブロックとして機能する第2のブロックが提供される。ブロック1に記録することができなかった論理ユニットおよび任意の後続の論理ユニットは、代わりにブレークアウトブロック上に記録される。このように、障害ブロック1およびそこにあるデータを置き換えるのに追加の時間を必要としない。中間フェーズIIにおいて、シーケンスのすべての記録済み論理ユニットは、ブロック1およびブロック2から取得可能である。最終フェーズIIIにおいて、障害ブロック1およびそこにあるデータは、論理ユニットを移転ブロックとしての役割を果たすブロック3へ移転させることによって置き換えられる。よって、障害ブロック内のデータは復旧され、その後、障害ブロックを廃棄することができる。最終フェーズは、任意の同時期のメモリ動作のタイミングと衝突しないように時間調整される。この実施形態において、移転ブロック3は、ブレークアウトブロック2とは別のものである。これは、中間フェーズ中に追加の論理ユニットをブレークアウトブロックに記録していた場合には都合がよい。よって、ブレークアウトブロックは更新ブロックに変化し、不良ブロックから論理ユニットを移転するには適さない。図31Bは、第3の最終移転ブロックが第2のブレークアウトブロックと同一である、プログラム障害処理の他の実施形態を示す。フェーズIおよびIIは、図31Aに示されている第1の実施形態と同様である。しかし、フェーズIIIにおいて、不良ブロック1からの論理ユニットは、ブレークアウトブロック2へ移転される。これは、以前の書き込み動作の元シーケンス以外の追加の論理ユニットをブレークアウトブロック2に記録していない場合には都合がよい。このように、この論理ユニットを記憶するために必要なブロックが最小限となる。統合化中のプログラム障害処理のための実施形態プログラム障害処理は、統合化動作中には特に重要である。通常の統合化動作は、元ブロックおよび更新ブロック内にある論理グループのすべての論理ユニットの現在のバージョンを統合化ブロックに統合化する。統合化動作中に、統合化ブロック内にプログラム障害が生じると、残りの論理ユニットの統合化を受け入れるために、ブレークアウト統合化ブロックとして機能する他のブロックが提供されることとなる。このように、1回より多くコピーをする必要のある論理ユニットはなく、例外処理を伴う動作も、通常の統合化処理について指定された期間内に完了することができる。好都合なときには、グループのすべての未処理の論理ユニットをブレークアウトブロックに統合化することによって、統合化動作を完了することができる。好都合なときとは、統合化を行う時間があるときに、現在のホスト書き込み動作以外の何らかの他の期間中のことを指すことになる。このような好都合なときの1つとして、更新はあるが、関連する統合化処理がない場合の他のホスト書き込み中が挙げられる。基本的には、プログラム障害処理を伴う統合化は、複数のフェーズ内で実施されるものとみなされる。第1のフェーズにおいて、各論理ユニットを1回より多く統合化することを避けるために、論理ユニットは、プログラム障害が生じた後に、1つより多くのブロックに統合化されている最中である。最終フェーズは、好都合なときに完了し、その際に、論理グループは、好ましくはすべての論理ユニットをブレークアウト統合化ブロックに順次順序で収集することによって、1つのブロックに統合化される。図32Aは、統合化処理となる最初の更新動作のフローチャートを示す。ステップ1102:ブロックに組織化された不揮発性メモリを組織化し、各ブロックは、共に消去可能なメモリユニットに分割され、各メモリは、データの論理ユニットを記憶するためのものである。ステップ1104:データを複数の論理グループに組織化し、各論理グループは、あるブロック内に記憶可能な論理ユニットのグループである。ステップ1112:論理ユニットにパッケージ化されたホストデータを受信する。ステップ1114:論理グループの論理ユニットの第1のバージョンを第1の順序に従って第1のブロックに記憶することによって、論理グループの元ブロックを作成する。ステップ1116:論理グループの論理ユニットの後続のバージョンを含む第2のブロックに第2の順序に従って記憶することによって、論理グループの更新ブロックを作成する。ステップ1119:前述した章において説明したような予め定められたイベントにおいて、様々なブロック内の論理ユニットの現在のバージョンを収集して新規のブロックに再記録するために、ガーベッジコレクションが行われる。図32Bは、本発明の好ましい実施形態に係る、複数フェーズ統合化動作のフローチャートを示す。統合化障害処理フェーズIエラー処理を伴う統合化であるフェーズI動作1120は、ステップ1122およびステップ1124からなる。ステップ1122:論理グループの論理ユニットの現在のバージョンを第3のブロックに第1の順序と同様に記憶することによって、論理グループについての統合化ブロックを作成する。ステップ1124:統合化ブロックにおける記憶障害に応じて、前記第3のブロックにはない論理グループの論理ユニットを第4のブロックに第1の順序と同様に記憶することによって、ブレークアウト統合化ブロックを提供する。ブロック1および2内のデータは、ブロック3およびブロック4へ転送されているので、ブロック1および2は、空間を開放するために消去することができる。好ましい実施形態において、ブロック2をEBL消去済みブロックリスト、図18参照へ直接開放して、再利用することができる。ブロック1は、これが閉鎖更新ブロックであり、対応するGATエントリが指し示す他のブロックがある場合にのみ開放される。基本的に、ブロック3は、論理グループについての元ブロックとなり、ブロック4は、ブロック3についての置換順序更新ブロックとなる。フェーズI統合化が完了すると、メモリ装置は、BUSY信号を発行することによってその旨ホストに対して通知する。中間動作フェーズIIフェーズII中間動作1130は、フェーズIII統合化動作1140の前に生じてもよい。ステップ1132,1134,1136のいずれか1つによって与えられるような、数多くの予想される場合が可能である。ステップ1132:論理グループの書き込み動作において、更新ブロックとしての第4のブロックブレークアウト統合化ブロックに対して書き込みを行う。ホストがこの元論理データへ書き込みを行うと、ブレークアウト統合化ブロックであり、置換順次更新ブロックの役割を現在まで担ってきたブロック4が、通常の更新ブロックとして使用されることになる。ホスト書き込みによっては、順次的のままである場合もあるし、カオス的状態に変化している場合もある。更新ブロックとして、先の好ましい実施形態において説明したように、何らかの時点で、他のカオス的ブロックの閉鎖をトリガする。ホストが他の論理グループに書き込むと、フェーズIII動作に直接進む。ステップ1134:または、読み出し動作において、論理グループについての元ブロックとしての第3のブロックと、更新ブロックとしての第4のブロックと共にメモリを読み出す。この場合、セクションAおよびBからの論理ユニットは、論理グループの元ブロックとしてのブロック3から読み出されることとなり、セクションCおよびDからの論理ユニットは、グループの更新ブロックとしてのブロック4から読み出されることとなる。セクションAおよびBのみがブロック3から読み出すことができるので、プログラミングが失敗したページに対するアクセスはないことになり、その後の未書き込み部分に対するアクセスもないことになる。フラッシュメモリ内のGATディレクトリはまだ更新されておらず、元ブロックとしてブロックIをまだ指し示してはいるが、そこから読み出されるデータはなく、ブロック自体はそれ以前に消去されている。中間フェーズの他の可能性として、論理グループ内の論理ユニットのホスト読み出しが挙げられる。この場合、セクションAおよびBからの論理ユニットは、論理グループの元ブロックとしてのブロック3から読み出されることとなり、セクションCおよびDからの論理ユニットは、グループの順次更新ブロックとしてのブロック4から読み出されることとなる。ステップ1136:または、電源投入初期化の際に、第1から第4のブロックのいずれかをその内容を走査することによって再識別する。中間フェーズに関する他の可能性として、メモリ装置の電源が落とされて、その後に再始動される場合が挙げられる。前に説明したように、電源投入初期化中に、割り当てブロックリスト消去プールのブロックが使用される、図15および図18参照内のブロックが走査されて、特別な状態の元ブロックブロック3となった不良統合化ブロックと、論理グループに関する関連する順次更新ブロックブロック4とを識別する。関連するブロックはプログラムエラーが生じている元ブロックブロック3である旨を、ブレークアウトブロックブロック4の第1の論理ユニット内のフラグが示すことになる。ブロックディレクトリGATを調べることによって、その後、ブロック3を位置決定することができる。一実施形態において、ブレークアウト統合化ブロックブロック4内の第1の論理ユニットにフラグがプログラムされている。これは、論理グループの特別な状態、すなわちブロック3およびブロック4という2つのブロックに統合化されていることを示すのに役立つ。フラグを使用して不良ブロックを有する論理グループを識別する代替の手法としては、元ブロックが一杯となるほどこのブロックが一杯ではない最終ページにエラーが生じて、最終ページにECCエラーがない場合を除いてという特性によって、走査中にブロックが不良であることを検出することが挙げられる。また実施によっては、ブレークアウト統合化ブロックブロック4に書き込まれた第1のセクタのヘッダ領域内の単なるフラグではなく、フラッシュメモリ内の制御データ構造内に記憶された障害グループ/ブロックについての情報記録がある場合がある。統合化完了フェーズIIIステップ1142:予め定められたイベントに応じて、第4のブロックがフェーズI以来さらに記録されることがなかった場合である第1の場合には、論理グループのすべての未処理の論理ユニットの現在のバージョンを第1の順序と同様に記憶し、第4のブロックがフェーズI以来さらに記録されることがあった場合である第2の場合には、第3および第4のブロックを第5のブロックに統合化する。ステップ1144:その後、第1の場合には、論理グループについての元ブロックとしての統合化された第4のブロックと共にメモリを動作させ、第2の場合には、論理グループの元ブロックとしての第5のブロックと共にメモリを動作させる。何らかの特定の時間的制限を違反しない機会があるときはいつでも、フェーズIIIにおける最終統合化が実施される。好ましい時機としては、統合化動作を伴わない他の論理グループへの更新動作がある場合に、次のホスト書き込みスロットに便乗することが挙げられる。他の論理グループへのホスト書き込みがガーベッジコレクション自体をトリガする場合には、フェーズIIIの統合化は延期される。図33は、複数フェーズ統合化動作の最初および最後のフェーズのタイミング例を示す。ホスト書き込み遅延は、期間TWを伴う各ホスト書き込み時間スロットの幅である。ホスト書き込み1は、単純な更新であり、論理グループLG1内の論理ユニットの第1のセットの現在のバージョンが関連する更新ブロック上に記録される。ホスト書き込み2において、論理グループLG1に対する他の更新が生じて、更新ブロックが閉鎖される結果となる例えば、一杯で。新規の更新ブロックが、残りの更新を記録するために提供されることになる。新規の更新ブロックの提供によって、ガーベッジコレクションがトリガされて、ブロックの再利用のためにリサイクルするために、LG4に対して統合化動作が生じる結果となる場合がある。LG4グループの現在の論理ユニットは、統合化ブロック上に順次順序で記録中である。統合化動作は、統合化ブロック内に不良が生じるまで進む。その後、フェーズIの統合化が呼び出されて、統合化処理はブレークアウト統合化ブロックに対して継続する。その間、LG4の最終統合フェーズIIIは、次の機会を待つ。ホスト書き込み3において、論理グループLG2の論理ユニットの書き込みも生じて、LG2についての統合化をトリガする。これは、時間スロットが既に完全に使用されていることを意味する。ホスト書き込み4において、動作は、LG2のいくつかの論理ユニットをその更新ブロックに単に記録するだけである。時間スロット内の余った時間は、LG4の最終統合化を実行する機会を提供する。ブレークアウト統合化ブロックが更新ブロックに変換されない実施形態図34Aおよび図34Bは、図28および図31における例に対して適用した、複数のフェーズ統合化のフェーズIおよびフェーズIII動作に関する第1の場合をそれぞれ示す。図34Aは、ブレークアウト統合化ブロックが、更新ブロックとしてよりも、統合化処理が中断された統合化ブロックとして使用される場合を示す。特に、図34Aは、ホストが論理グループLG1に属する論理ユニットの更新を書き込むものであり、その動作によって他の論理グループLG4に関連したブロックの統合化もトリガされる、図33に示されているホスト書き込み2を参照している。元ブロックブロック1および更新ブロックブロック2の形成は、図28における例と同様の手法で行われる。同様に、統合化動作中に、統合化ブロックブロック3には、セクションC内の論理ユニットを統合化するポイントにおいて障害があることがわかる。しかし、図28に示されている統合化手法とは異なり、この複数フェーズ手法は、統合化動作を、ブレークアウト統合化ブロックとしての役割を果たす新規に与えられたブロックブロック4に対して行い続ける。よって、フェーズIの統合化動作において、セクションAおよびB内の論理ユニットは、統合化ブロックブロック3内に統合化されている。セクションCおよびD内の残りの論理ユニットは、プログラム障害が統合化ブロック内で生じると、ブレークアウト統合化ブロックブロック4へ順次にコピーされる。第2の論理グループに関連したブロックの統合化動作をトリガする第1の論理グループにおける更新をホストが本来書き込む場合は、第1の論理グループの更新は、第1の論理グループについての更新ブロック典型的には、新規の更新ブロックに記録される。この場合、ブレークアウト統合化ブロックブロック4は、統合化動作外のどの更新データを記録するのにも使用されず、未だ完了されていないブレークアウト統合化ブロックのままである。ブロック1および2内のデータは他のブロックブロック3および4内に今や完全に含まれているので、リサイクルのために消去することができる。アドレステープルGATは更新されて、ブロック3を論理グループについての元ブロックとして示す。更新ブロックについてのディレクトリ情報ACL内、図15および図18参照も更新されて、論理グループ例えば、LG4についての順次更新ブロックとなったブロック4を示す。その結果、統合化された論理ブロックは、1つのブロックに局在化せず、不良統合化ブロックブロック3およびブレークアウト統合化ブロックブロック4に渡って分散される。この手法の重要な特徴は、1つより多いブロックに渡って統合化を分散させる代償として、グループ内の論理ユニットはこのフェーズにおいて1回統合化されるだけであるということである。このように、統合化動作は、通常の指定された時間内に完了することができる。図34Bは、図34Aで開始された複数フェーズ統合化の第3および最終フェーズを示す。図33に関連して説明したように、フェーズIIIの統合化は、付随する統合化動作をトリガしない後続のホスト書き込み中といった、第1のフェーズ後の好都合なときに実行される。特に、図34Bは、図33に示されているホスト書き込み4が生じる時間スロットを示す。その期間中に、ホスト書き込みは、他の追加の統合化動作をトリガしない論理グループLG2に属する論理ユニットを更新する。よって、時間スロット内の余った時間は、論理グループLG4の統合化の完了のためのフェーズIII動作のために好都合に使用することができる。この動作により、既にブレークアウトブロック内にないLG4のすべての未処理の論理ユニットをブレークアウトブロックに統合化する。この例において、これは、セクションAおよびBがブロック3からブレークアウトブロックブロック4へ論理的な順次順序でコピーされることになることを意味する。ブロック内での論理ユニットの折り返し手法およびページタグ図3Aの使用を考慮して、この例では、ブロック4内において、セクションAおよびBがセクションCおよびDの後に記録されているように示されているにもかかわらず、記録済みのシーケンスは、A,B,C,およびDという順次順序と同等であるとみなされることになる。実施によっては、コピーすべき未処理の論理ユニットの現在のバージョンは、ブロック3では既に統合化の形式となっているので、ブロック3から取得されるのが好ましいが、消去されていなければブロック1およびブロック2から収集されてもよい。ブレークアウトブロックブロック4に対する最終統合化が完了した後、この論理グループの元ブロックと指定されることになり、適切なディレクトリ例えば、GAT、図17A参照がそれに従って更新されることになる。同様に、障害物理ブロックブロック3は、不良と印付けされ、マッピングからはずされる。他のブロックであるブロック1およびブロック2は消去されてリサイクルされる。その間、LG2の更新がLG2に関連した更新ブロック内に記録される。ブレークアウト統合化ブロックが更新ブロックに変更されない場合の実施形態図35Aおよび図35Bは、図28および図33における例に対して適用した、複数のフェーズ統合化のフェーズIおよびフェーズIII動作に関する第2の場合をそれぞれ示す。図35Aは、ブレークアウト統合化ブロックが、統合化ブロックとしてよりも、ホスト書き込みを受け取る更新ブロックとして保持される場合を示す。これは、例えば論理グループLG4を更新し、その処理において同一の論理グループ内の統合をもトリガするホスト書き込みに適用可能である。図34Aの場合のように、ブロック1およびブロック2のブロック3への統合化は、セクションCを処理中にプログラム障害が発生するまで進む。その後、統合化は、ブレークアウト統合化ブロックブロック4へ続く。未処理の論理ユニット例えば、セクションCおよびDがブレークアウトブロックブロック4に統合化された後に、フェーズIIIにおいて論理グループの統合化の完了を待つ代わりに、ブレークアウトブロックは更新ブロックとして保持される。この場合は、ホスト書き込みが論理グループを更新して、同一の論理グループの統合化をトリガする場合に、特に適用可能である。この例において、これにより、論理グループLG4についてのホスト更新の記録を、新規の更新ブロックに記録する代わりに、ブレークアウト統合化ブロックブロック4内に記録することができる。以前はブレークアウト統合化ブロックブロック4であった更新ブロックは、記録されたホストデータによっては、順序的であることも、またはカオス的になることもある。図に示されている例において、セクションC内の論理ブロックの後続の新規のバージョンがブロック4内の以前のバージョンを廃止するので、ブロック4はカオス的に変化している。中間フェーズ中に、ブロック3は、LG4についての元ブロックとみなされることになり、ブロック4は、関連する更新ブロックとなる。図35Bは、第2の場合について図35Aにおいて開始した複数のフェーズ統合化の第3および最終フェーズを示す。図33に関連して説明したように、フェーズIIIの統合化は、付随する統合化動作をトリガしない後続のホスト書き込み中といった、第1のフェーズ後の好都合なときに実行される。その期間中に、ホスト書き込みは、統合化動作をトリガしない論理グループに属する論理ユニットを更新する。よって、時間スロット内の余った時間は、論理グループLG4の統合化の完了のためのフェーズIII動作のために好都合に使用することができる。その後、論理ブロックLG4は、ブロック3および4から新規の統合化ブロックブロック5へガーベッジコレクションされる。その後、ブロック3は不良と印付けされ、ブロック4はリサイクルされて、新規の統合化ブロックブロック5が論理グループLG4についての新規の元ブロックになる。ブロック1およびブロック2という他のブロックも、消去されリサイクルされる。フェーズ化されたプログラム障害処理の他の実施形態図31A,31B,34A,34B,35A,および35Bにおいて説明した例は、同一の論理グループに属する論理ユニットのみを記憶する各物理ブロックメタブロックを有する、好ましいブロック管理システムに当てはまる。本発明は、例えば、国際公開特許出願第WO03/027828号特許文献14および国際公開特許出願第WO00/49488号特許文献15に開示されているような、物理ブロック配列する論理グループがない他のブロック管理システムにも等しく適用可能である。フェーズ化されたプログラム障害処理方法を他のシステムに対して実施するいくつかの例を、図36A,36B,および36Cに示す。図36Aは、ホスト書き込みが更新ブロックの閉鎖をトリガし、かつ更新ブロックが順次的な場合に適用されるような、フェーズ化されたプログラムエラー処理方法を示す。この場合の閉鎖は、残りの有効データBおよびCを元のブロック2から順次更新ブロック3へコピーすることによって行われる。データ部分Cのプログラミングの開始時におけるプログラム障害の場合、部分Cは、確保していたブロック4へプログラムされることになる。その後、新規のホストデータは、新規の更新ブロック5図示せずに書き込むことができる。この方法のフェーズIIおよびIIIは、カオス的ブロック閉鎖の場合と同一である。図36Bは、更新ブロックの更新の場合の部分的ブロックシステムに適用可能であるような、フェーズ化されたプログラムエラー処理方法を示す。この場合、論理グループは、元ブロック1と他の更新ブロックとに記憶される。統合化動作には、更新ブロックのうちの1つ何らかの規則に従って選ばれる、図ではブロック3に対して、元ブロック1および他の更新ブロック2からデータをコピーすることが含まれる。既に説明した基本的な場合との違いは、ブロック3が既に部分的に書き込まれていることである。図36Cは、メタブロックにマッピングされた論理グループをサポートしないメモリブロック管理システムにおける、フェーズ化されたプログラムエラー処理、ガーベッジコレクション動作、またはクリーンアップを示す。このようなメモリブロック管理周期的記憶システムは、国際公開特許出願第WO03/027828号特許文献14に記載されている。周期的な記憶システムの際立った特徴は、ブロックが1つの論理グループに割り当てられるのではないということである。メタブロック内の制御データについての複数の論理グループ化をサポートしている。ガーベッジコレクションは、無関係なこともあるランダム論理ブロックアドレス有効データセクタを、既に何らかのデータを有している場合もある部分的に廃止されたブロックから移転ブロックへ取り出すことを伴う。移転ブロックが動作中に一杯になると、他のブロックが開放される。非順次更新ブロックのインデックス付け図16A~16Eに関連したカオス的ブロックのインデックス付けについての先の章において、CBIセクタが、カオス的または非順次的更新ブロック内にランダムに記憶された論理セクタの位置を追跡するインデックスを記憶するために使用される。本発明の他の態様によれば、非順次論理ユニットを有する更新ブロックをサポートするブロック管理システムを伴う不揮発性メモリにおいて、RAMにバッファされた更新ブロック内の論理ユニットのインデックスが、不揮発性メモリ内に周期的に記憶される。一実施形態において、インデックスは、インデックスを記憶する専用のブロック内に記憶される。他の実施形態において、インデックスは、更新ブロック自体に記憶される。さらに他の実施形態において、インデックスは、各論理ユニットのヘッダ内に記憶される。他の態様において、最終のインデックス更新の後だが次の分の前に書き込まれた論理ユニットは、インデックス付け情報を各論理ユニットのヘッダ内に記憶させる。このように、停電後に、初期化中に走査を実行する必要なく、最近書き込まれた論理ユニットの位置を決定することができる。さらに他の態様において、ブロックは、部分的に順次にかつ部分的に非順次に、1つより多い論理サブグループを対象として管理される。所定のトリガイベント後のCBIブロック内のCBIセクタ内に記憶されたインデックスポインタ図16A~16Eに関連して説明した手法によれば、カオス的ブロック内の最近書き込み済みのセクタのリストは、コントローラRAM内に保持される。直近のインデックス付け情報を含むCBIセクタは、所定のカオス的ブロックに関連した論理ブロックへの所定数の書き込みの後にのみ、フラッシュメモリCBIブロック620に書き込まれる。このようにして、CBIブロックに対する更新の回数を減少する。ある論理グループについてのCBIセクタの次の更新に先立って、論理グループについての最近書き込み済みのセクタのリストがコントローラRAM内に保持される。メモリ装置が電源遮断にあった場合にはリストは失われるが、電源投入後の初期化時に更新済みブロックを走査することによって再構築することができる。図37は、同一の論理グループのN回毎のセクタ書き込み後に、関連するカオス的インデックスセクタブロックへのCBIセクタの書き込みのスケジュールの一例を示す。この例は、2つの論理グループLG3およびLG11が並行更新を受けていることを示す。最初に、LG3の論理セクタが順次順序で元ブロックに記憶されている。グループ内の論理セクタの更新は、ホストによって支持された順序で、関連する更新ブロックに記録される。この例は、カオス的更新シーケンスを示す。並行して、論理グループLG11も、その更新ブロックにおいて同様のやり方で更新されている。各論理セクタ書き込みの後、更新ブロック内のその位置は、コントローラRAM内に保持される。各所定のトリガイベントの後、更新ブロック内の論理セクタの現在のインデックスが、カオス的インデックスセクタの形式で、不揮発性のカオス的インデックスセクタブロックへ書き込まれる。例えば、N回毎の書き込みの後に所定のトリガイベントが生じ、ここで、Nは3であってもよい。提示された例は、セクタとしてのデータの論理ユニットを伴うものとしたが、当業者が、論理ユニットをセクタまたはセクタのグループを含むページのような何らかの他の集合体でありうると認識することになる。また、順次ブロックの最初のページは、必ずしも論理ページ0である必要はない。なぜなら、ページタグの折り返しがある場合があるからである。所定のトリガイベント後のカオス的更新ブロック内のCBIセクタに記憶されたインデックスポインタ他の実施形態において、インデックスポインタは、N回毎の書き込みの後に、カオス的更新ブロック内の専用のCBIセクタ内に記憶される。この手法は、インデックスもCBIセクタ内に記憶する場合の前述した実施形態と同様である。先の実施形態において異なる点は、CBIセクタはCBIセクタブロックに記録され、更新ブロック自体には記録されないことである。この方法は、すべてのカオス的ブロックインデックス付け情報をカオス的更新ブロック自体に保持することに基づく。図37A,37B,および37Cは、3つの異なる段階においてCBIセクタをも記憶する更新ブロックの状態をそれぞれ示す。図38Aは、所定数の書き込みの後にCBIセクタが記録される時点までの更新ブロックを示す。この例において、ホストが論理セクタ0~3を順次書き込んだ後に、論理セクタ1の他のバージョンを書き込むためのコマンドを発行し、よってデータ書き込みの連続シーケンスを破断させる。その後、更新ブロックは、CBIセクタ内に保持されたカオス的ブロックインデックスの実施を伴うカオス的更新ブロックに変換される。前述したように、CBIは、カオス的ブロックのすべての論理セクタについてのインデックスを含むインデックスである。例えば、0番目のエントリは、0番目の論理セクタについての更新ブロック内のオフセットを示し、同様に、n番目のエントリは、n番目の論理セクタについてのオフセットを示す。CBIセクタは、更新ブロック内の次に利用可能な位置に書き込まれる。頻繁なフラッシュアクセスを回避するために、CBIセクタは、N回毎のデータセクタの書き込みの後、書き込まれる。この例において、Nは4である。この時点で電力が失われると、最終書き込みセクタはCBIセクタとなり、ブロックは、カオス的更新ブロックとみなされることになる。図38Bは、インデックスセクタの後に論理セクタ1,2,および4がさらに記録される、図38Aの更新ブロックを示す。論理セクタ1および2の新規のバージョンが、更新ブロック内に以前に記録された古いバージョンに取って代わる。この時点での電力周期の場合、最終書き込みセクタを最初に見つける必要があり、その後、最終書き込みインデックスセクタおよび最近書き込まれたデータセクタを見つけるために、N個のセクタを走査する必要がある。図38Cは、インデックスセクタの次の記録をトリガするために他の論理セクタが書き込まれる、図38Bの更新ブロックを示す。他のNN=4個のセクタ書き込みの後に同じ更新ブロックが、CBIセクタの他の現在のバージョンを記録する。この手法の利点は、CBIブロックを分離する必要性をなくすことである。同時に、物理フラッシュセクタのオーバーヘッドデータ領域が、カオス的更新ブロック内の有効セクタに対するインデックスについて必要とされるエントリ数を収容することができるほど大きいかどうかを心配する必要はない。カオス的更新ブロックは、その後、すべての情報を含み、アドレス変換のための外部データを必要としない。これにより、CBIブロックのコンパクト化に関連する制御更新の数を減少させ、かつカスケード制御更新を短縮させる、単純なアルゴリズムとなるCBIブロック管理についての前述した章を参照。カオス的更新ブロック内のデータセクタヘッダに記憶された、最近書き込み済みのセクタについての情報本発明の他の態様によれば、あるブロックに記録された論理ユニットのインデックスは、N回毎の書き込みの後、不揮発性メモリ上に記録され、中間書き込みの論理ユニットについての現在の情報は、書き込まれた各論理ユニットのオーバヘッド部分に記憶される。このように、電力が再開した後に、最終インデックス更新以来書き込まれた論理ユニットについての情報が、ブロックを走査する必要なく、ブロック内の最終書き込み論理ユニットのオーバーヘッド部分から即座に取得することができる。図39Aは、カオス的更新ブロック内の各データセクタのヘッダに記憶されている中間書き込みについての中間インデックスを示す。図39Bは、書き込まれた各セクタのヘッダ内に中間書き込みについての中間インデックスを記憶する一例を示す。この例において、4つのセクタLS0~LS3が書き込まれた後、CBIインデックスが、ブロック内の次のセクタとして書き込まれる。その後、論理セクタLS’1,LS’2,およびLS’4がブロックに書き込まれる。その度に、ヘッダは、最終CBIインデックス以来書き込まれた論理ユニットについての中間インデックスを記憶する。よって、LS’2内のヘッダは、最終CBIインデックスのオフセットすなわち、位置を与えると共にLS’1のオフセットも与えるインデックスを有することとなる。同様に、LS4におけるヘッダは、最終CBIインデックスのオフセットを与えると共にLS’1およびLS’2のオフセットも与えるインデックスを有することになる。最終書き込み済みデータセクタは、N個の最終書き込み済みページすなわち、最終書き込み済みCBIセクタまでについての情報を常に含む。電力再開があるときにはいつでも、最終CBIインデックスは、CBIインデックスセクタ以前に書き込まれた論理ユニットについてのインデックス付け情報を提供し、後続の論理ユニットについてのインデックス情報は、最終書き込みデータセクタのヘッダ内に見つけられる。これには、初期化の際に、後続の書き込み済みセクタについてのブロックを走査してその位置を決定する必要がない点で有利である。中間インデックス情報をデータセクタのヘッダに記憶する手法は、CBIインデックスセクタを更新ブロック自体に記憶させるか、または前述した章で説明したような別個のCBIセクタブロック内に記憶させるどうかについて等しく適用可能である。カオス的更新ブロック内のデータセクタヘッダ内に記憶されたインデックスポインタ他の実施形態において、全CBIインデックスは、カオス的更新ブロック内の各データセクタのオーバーヘッド部分に記憶される。図40は、カオス的更新ブロック内の各データセクタのヘッダに記憶されているカオス的インデックスフィールド内の情報を示す。セクタヘッダの情報容量は限られているので、任意の1つのセクタによって提供されるインデックスの範囲は、階層的なインデックス付け手法の一部として設計されてもよい。例えば、メモリの特定のプレーン内におけるセクタが、このプレーン内のセクタのみに対してインデックス付けを提供してもよい。また、論理アドレスの範囲は、複数の副範囲に分割されてもよく、これによって、間接的インデックス付け手法を採用することができる。例えば、64個の論理アドレスを有するセクタがあるプレーンに記憶されてもよい場合に、各セクタがセクタオフセット値についての3つのフィールドを有してもよく、各フィールドは4つのオフセット値を記憶することができる。第1のフィールドは、論理オフセット範囲0~15,15~31,32~47,および48~63内の最終書き込みセクタについての物理オフセットを規定する。第2のフィールドは、それぞれが関連する範囲内にある4つのセクタの4つの副範囲についての物理オフセット値を規定する。第3のフィールドは、関連する副範囲内の4つのセクタについての物理オフセット値を規定する。したがって、カオス的更新ブロック内の論理セクタの物理オフセットは、3つのセクタまでからの間接オフセット値を読み出すことによって決定されてもよい。この手法の利点は、別個のCBIブロックまたはCBIセクタに対する必要性もなくすことにある。しかし、物理フラッシュセクタのオーバーヘッドデータ領域がカオス的更新ブロック内の有効セクタに対するインデックスに必要なエントリ数を収容することができるのに十分なほど大きい場合にのみ適用されてもよい。カオス的更新ブロックについての論理グループ内の限られた論理範囲ある論理グループ内において、非順次に書き込み可能なセクタの論理範囲が減少される。この手法の主な利点は、この範囲外のセクタが元ブロック内に順次書き込みされ続け、コピー元およびコピー先が整列していることを条件として、そうでなければ、他の読み出しが必要となる場合もあるコピー先ページについてのすべてのデータを得るためには1つのマルチセクタページマルチチップの場合には複数ページの並列的な読み出しの場合もあるだけを読み出せばよいので、順次書き込み済みデータのコピーの方が早く行えるので、ガーベッジコレクションをはるかに短時間に行えることである。また、順次データは、そのコピー元からコピー先へ、コントローラに対するデータ転送なして、オンチップコピー機能を使用してコピーすることができる。カオス的ブロックにおいて生じるような、コピー元データが分散している場合には、コピー先へ書き込むべきすべてのセクタを収集するために、セクタ毎に1ページまでの読み出しが必要になる。一実施形態において、論理範囲をいくつかのセクタに文字通り制限する代わりに、CBIの数を制限することによってそれを行うカオス的範囲を大きなグループ/メタブロックに対してのみ制限することは理にかない、これには、複数のカオス的ブロックインデックスが全論理グループの範囲をカバーすることが必要となる。例えば、メタブロック/グループが2048個のセクタを有する場合、8個までのCBIセクタが必要となる場合があり、それぞれは、256個のセクタの1つのサブグループの連続論理範囲をカバーする。CBIの数が4に制限されると、4つのサブグループいずれでもよいまでのセクタを書き込むために、カオス的メタブロックを使用することができる。よって、論理グループは、4つまでの部分的または完全なカオス的サブグループを有することが許可され、最小4つのサブグループが完全に順次的のままであることになる。カオス的ブロックが4つの有効なCBIセクタを有する場合であり、それに関連して、これらのCBIセクタカオス的サブグループの範囲外のセクタをホストが書き込む場合には、カオス的論理グループは、統合化されて閉鎖されなければならない。しかし、これが生じることは滅多にない。なぜならば、実際の応用では、ホストは、2048個のセクタ論理グループの範囲内の256個のセクタサブグループのカオス的範囲を4つより多く必要としないからである。その結果、通常の場合、ガーベッジコレクション時間も影響を受けないが、制限規則によって、ホストのタイムアウトをトリガするような長すぎるガーベッジコレクションの極端な場合が生じるのを防ぐ。一部順次的なカオス的更新ブロックのインデックス付けブロックがカオス的管理モードに変換される前に、順次更新ブロックが一部書き込まれた場合には、論理グループのすべてまたは一部の順次更新済みセクションは、順次更新されたものとして扱われ続けてもよく、カオス的更新管理は、論理グループのアドレス範囲のサブセットにのみ適用されてもよい。制御データの整合性および管理メモリ装置に記憶されたデータは、電力中断またはあるメモリ位置の不良によって、破損する場合がある。メモリブロック内に不良が生じると、データは異なるブロックに移転されて、不良ブロックは廃棄される。エラーが広範でない場合は、データと共に対比してある誤り訂正符号ECCによってすぐに訂正することができる。しかし、ECCが破損データを訂正できない場合もある。例えば、エラービット数がECCの能力を超える場合である。これは、メモリブロック管理システムに関連した制御データなどの重要データについては受け入れられない。制御データの例として、図20に関連して説明したような、メモリブロック管理システムに関連したディレクトリ情報およびブロック割り当て情報が挙げられる。前に説明したように、制御データは、高速のRAMと、低速の不揮発性メモリブロックとの両方に保持される。頻繁に変化する制御データを、周期的な制御書き込みによってRAM内に保持して、不揮発性メタブロック内に記憶されたものと同等の情報を更新する。このように、制御データは、不揮発だが低速のフラッシュメモリに、頻繁にアクセスする必要なく記憶される。図20に示されているGAT,CBI,MAP,MAPAなどの制御データ構造の階層は、フラッシュメモリに内に保持される。よって、制御書き込み動作により、RAM内の制御データ構造からの情報が、フラッシュメモリ内の同等の制御データ構造を更新する。重要データの複製本発明の他の態様によれば、制御データのいくつかまたはすべてといった重要なデータは、複製にして保持しておけば、信頼性のレベルが上がることが保証される。メモリセルの同一のセットのマルチビットを順次にプログラムするための2パスプログラミング手法を使用する多状態メモリシステムについて、第1のパスによって確立されたデータが第2のパスにおけるいかなるプログラミングエラーによっても破損されないように、複製が行われる。また、複製は、書き込みの異常終了の検出、誤検出の検出すなわち、両コピーは良好なECCを有するが、データが異なる場合の助けとなり、信頼性のレベルが向上する。データ複製にはいくつかの手法が考えられる。一実施形態において、所定のデータの2つのコピーが先のプログラミングパスにプログラムされた後に、後続のプログラミングパスは、2つのコピーのうちの少なくとも1つを記憶するメモリセルをプログラムすることを回避する。このように、2つのコピーのうちの少なくとも1つは、後続のプログラミングパスが完了前に異常終了して先のパスのデータを破損する場合に、その影響を受けないことになる。他の実施形態において、所定のデータの2つのコピーは、2つのコピーのうちの多くても1つがそのメモリセルを後続のプログラミングパス内にプログラムする、2つの異なるブロックに記憶される。さらに他の実施形態において、所定のデータの2つのコピーがプログラミングパスに記憶された後は、2つのコピーを記憶するメモリセルのセットに対して、これ以上のプログラミングが行われないことになる。これは、2つのコピーをメモリセルのセットについての最終的なプログラミングパスにプログラムすることによって達成される。さらに他の実施形態において、所定のデータの2つのコピーは、プログラムされたメモリセルに対してさらなるプログラミングが生じないように、バイナリプログラミングモードの多状態メモリ内にプログラムされる。さらに他の実施形態において、メモリセルの同一のセットのマルチビットを順次にプログラムするための2パスプログラミング手法を使用する多状態メモリシステムについて、先のプログラミングパスによって確立されたデータが後続のプログラミングパスにおけるエラーの影響を受けないようにするために、障害耐性コードを使用して、複数のメモリ状態を符号化する。各メモリセルがデータの1ビットより多くを記憶する多状態メモリにおいては、データの複製が複雑になることが生じる。例えば、4状態メモリは、2ビットで表現することができる。既存の手法の1つとして、2パスプログラミングを使用してこのようなメモリをプログラムすることが挙げられる。第1のビット下位ページビットは、第1のパスによってプログラムされる。その後、同一のセルが、第2のパス内にプログラムされて、所望の第2のビット上位ページビットを表す。第2のパス内の第1のビットの値を変更しないようにするために、第1のビットのメモリ状態表現を、第2のビットの値に依存させる。したがって、第2のビットのプログラミング中に、電力中断または他の理由でエラーが生じて誤ったメモリ状態になってしまった場合には、第1のビットの値も破損されている可能性がある。図41Aは、各メモリセルがデータの2ビットを記憶する場合の4状態メモリのしきい値電圧分布を示す。4つの分布は、4つのメモリ状態U、XY、およびZの群を示す。メモリセルは、プログラムされる前にまず消去されて、Uまたは未書き込みの状態にされる。メモリ状態XY、およびZは、メモリセルが次第にプログラムされていくに従って、徐々に到達される。図41Bは、グレイコードを使用する既存の2パスプログラミング手法を示す。4つの状態は、下位ページビットおよび上位ページビットという2つのビットによって表現することができ、例えば上位ページビット、下位ページビットのように表現することができる。並列にプログラムされるべきセルのページについては、論理下位ページおよび論理上位ページという、確かに2つの論理ページが存在する。第1のプログラミングパスは、論理下位ページのみをプログラムする。適切なコード化によって、セルの同じページに対する後続の第2のプログラミングパスは、論理下位ページを再設定することなく、論理上位ページをプログラムすることになる。一般的に使用されるコードは、グレイコードであり、隣接する状態へ移行する際に1ビットしか変化しない。したがって、このコードは、1ビットしか関与しないので、エラー訂正に対する要求が少なくなるという利点を有する。グレイコードを使用する一般的な手法では、1は非プログラム状態を表す。よって、消去済みメモリ状態Uは、上位ページビット,下位ページビット=1,1によって表される。したがって、論理下位ページをプログラムするための第1のパスでは、データ0を記憶するセルはどれでも、x,1からx,0へ移行する論理状態を有することになり、ここでxは、上位ビットの無関係値を表す。しかし、上位ビットはまだプログラムされていないので、xは整合性のために1と標記されても構わない。1,0という論理状態は、セルをメモリ状態Xにプログラムすることによって表される。すなわち、第2のプログラムパスの前に、下位ビット値0は、メモリ状態Xによって表される。第2のパスプログラミングは、論理上位ページのビットを記憶するために実行される。上位ページビット値0を必要とするセルのみが、プログラムされる。第1のパスの後、ページ内のセルは、論理状態1,1または1,0のいずれかの状態である。下位ページの値を第2のパスに保存するためには、下位ビット値0または1を区別する必要がある。1,0から0,0への移行について、このメモリセルは、メモリ状態Yにプログラムされる。1,1から0,1への移行について、このメモリセルは、メモリ状態Zにプログラムされる。このように、読み出し中に、セル内にプログラムされたメモリ状態を判断することによって、下位ページビットおよび上位ページビットの両方を復号化することができる。しかし、グレイコードの2パスプログラミング手法は、第2のパスプログラミングが誤りである場合には問題となりうる。例えば、上位ページビットのプログラミングが0であり、下位ビットが1にあると、1,1から0,1への移行を生じさせることとなる。これは、メモリセルがUからXおよびYを通ってZへ徐々にプログラムされることを要求する。プログラミングの完了前に停電になると、メモリセルは、過渡的なメモリ状態のうちの1つ、例えばXで終わってしまう場合もある。メモリセルを読み出す場合には、Xが復号化されて、論理状態1,0とされる。これは、上位および下位ビットの両方について誤った結果をもたらす。なぜならば、本来は0,1であるはずだったからである。同様に、Yに到達した場合にプログラミングが中断されると、0,0に相当する。今度は上位ビットは正しいが、下位ビットはまだ誤りである。よって、上位ページプログラミングが、既に下位ページ内にあるデータを破損しうるという問題があることがわかる。特に、第2のパスプログラミングが中間メモリ状態を越えるパスを伴う場合、プログラムの異常終了によって、プログラミングがそのメモリ状態で終わる場合があり、誤った下位ページビットが復号化される結果となりうる。図42は、各セクタを複製化して退避することによって重要データを保護するやり方の一つを示す。例えば、セクタA,B,C,およびDは、複製コピーで退避される。あるセクタコピーにおいてデータの破損があれば、他のものが代わりに読み出される。図43は、複製セクタが典型的には多状態メモリ内に退避される非ロバストを示す。前に説明したように、4状態メモリの例において、多状態ページは、実際には、2つのパスでそれぞれプログラムされる論理下位ページおよび論理上位ページを含む。図に示されている例において、ページは4セクタの幅である。よって、セクタAおよびその複製は、論理下位ページに並行にプログラムされることとなり、セクタBおよびその複製についても同様である。その後、論理上位ページ内のプログラミングの後続の第2のパスにおいて、セクタC,Cは、並行にプログラムされることとなり、セクタD,Dについても同様である。セクタC,Cのプログラミング中にプログラム異常終了が生じた場合には、下位ページ内のセクタA,Aが破損することになる。上位ページプログラミングの前に下位ページセクタがまず読み出されかつバッファされるのでなければ、破損の場合に回復不可能な場合もある。よって、セクタA,Aのように重要なデータの2つのコピーを並行に退避しても、後で上位ページ内にセクタC,Cを退避する際に問題があると、両方共、破損を回避することができない。図44Aは、重要データのずらし複製コピーを多状態メモリへ退避する、一実施形態を示す。基本的に、図43におけるのと同様の手法、すなわちセクタA,AおよびセクタB,Bで、下位ページが退避される。しかし、上位ページプログラミングにおいて、C,D,C,Dのように、セクタC,Dは、その複製とインターリーブされている。部分的なページプログラミングがサポートされている場合には、セクタCの2つのコピーを並行にプログラムすることができ、セクタDの2つのコピーについても同様である。プログラムが、例えば2つのセクタCが異常終了する場合には、セクタAの一方のコピーおよびセクタBの一方のコピーに関してのみ、下位ページが破損されうる。他方のコピーは影響を受けないままである。よって、第1のパスに記憶された重要データの2つのコピーがある場合、後続の第2のパスプログラミングに同時に影響を受けることはない。図44Bは、重要データの複製コピーを多状態メモリの論理上位ページにのみ退避する、他の実施形態を示す。この場合、下位ページ内のデータは使用されない。セクタA,AおよびセクタB,Bなどの重要データおよびその複製は、論理上位ページにのみ退避される。このように、プログラム異常修了がある場合に、重要データは他の論理上位ページに書き換えられることができ、下位ページデータに対する破損は重要でなくなる。この解決策は、基本的には、各多状態ページの記憶容量の半分を使用することである。図44Cは、重要データの複製コピーを多状態メモリのバイナリモードで退避する、さらに他の実施形態を示す。この場合、各メモリセルは、しきい値範囲が2つの領域にのみ分割されているバイナリモードでプログラムされる。よって、1つのパスプログラミングのみであり、プログラム異常終了が生じる場合には、プログラミングを、異なる位置から再開することができる。この解決策も、各多状態ページの記憶容量の半分を使用することである。多状態メモリをバイナリモードで動作させることは、米国特許第6,456,528号特許文献18に記載され、その開示全体は本願明細書において参照により援用されている。図45は、重要データの複製コピーを2つの互いに異なるメタブロックへ並行に退避する、さらに他の実施形態を示す。ブロックのうちの1つが使用不可能になった場合、データは他方から読み出すことができる。例えば、重要データが、セクタA,B,C,Dと、E,F,G,Hと、I,J,K,Lとに含まれている。各セクタは、複製されて退避されている。2つのコピーは、2つの互いに異なるブロックであるブロック0およびブロック1に対して並行に書き込まれることになる。一方のコピーが論理下位ページに書き込まれると、他方のコピーは、論理上位ページに書き込まれることになる。このように、論理上位ページにプログラムされるコピーが常に存在することになる。プログラム異常終了が生じると、他の論理上位ページへ再プログラムすることができる。同時に、下位ページが破損される場合には、他のブロック内の他の上位ページのコピーが常に存在することになる。図46Bは、障害耐性コードを使用して重要データの複製コピーを並行に退避する、さらに他の実施形態を示す。図46Aは、4状態メモリアレイのしきい値電圧分布を示す点で図41と類似し、図46Bについての参考として示す。障害耐性コードは、基本的には、任意の上位ページプログラミングが任意の中間状態を通じて移行するのを回避する。よって、第1のパスの下位ページプログラミングは、消去済みメモリ状態UからYへプログラムすることによって表されるように、論理状態1,1を1,0に移行させる。上位ページビットを0にする第2のパスプログラミングにおいて、下位ページビットが1にある場合、消去済みメモリ状態UからXへプログラムすることによって表されるように、論理状態1,1は0,1に移行する。下位ページビットが0にある場合、メモリ状態YからZへプログラムすることによって表されるように、論理状態1,0は0,0に移行する。上位ページプログラミングは次に隣接するメモリ状態へのプログラミングのみを伴うので、プログラム異常終了によって、下位ページビットは変化しない。順次書き込み重要データの複製コピーは、前述したように、並行に書き込まれるのが好ましい。両コピーが同時に衝突するのを避ける他のやり方として、コピーを順次的に書き込むことが挙げられる。この方法は遅いが、コントローラが両コピーをチェックする際に、コピー自体がプログラミングが成功したかどうかを示す。図47は、データの2つのコピーの予想される状態と、データの有効性とを示す表である。第1および第2のコピーにECCエラーがない場合には、データのプログラミングは完全にうまくいったと考えられる。いずれのコピーからも有効データが得られる。第1のコピーにはECCエラーはないが、第2のコピーにはECCエラーがある場合には、プログラミングが第2のコピープログラミング中に中断されたことを意味する可能性がある。第1のコピーは、有効データを含む。第2のコピーデータは、エラーが訂正可能であっても信頼することができない。第1のコピーにはECCエラーがなく、第2のコピーは空消去済みである場合には、第1のコピープログラミングの後であるが第2のコピーが始まる前に、プログラミングが中断されたことを意味する可能性がある。第1のコピーは、有効データを含む。第1のコピーにECCエラーがあり、第2のコピーは空消去済みである場合には、プログラミングが第1のコピープログラミング中に中断されたことを意味する可能性がある。第1のコピーは、エラーが訂正可能であっても無効データを含むことがある。複製で保持されるデータを読み出すためには、以下の手法が好ましい。なぜならば、複製コピーの存在を利用するからである。両コピーを読み出しおよび比較する。この場合、図47に示されているような両コピーの状態を使用して、エラー誤検出がないことを確認することができる。コントローラが1つのコピーのみを読み出す他の実施形態において、速度および簡易性を考慮して、コピー読み出しは、2つのコピー間で交互に行うのが好ましい。例えば、コントローラが制御データを読み出す場合、例えばコピー1を読み出す場合に、次の制御読み出し任意の制御読み出しは、コピー2から行わなくてはならず、その後に再びコピー1などとなる。このように、2つのコピーを読み出して整合性を定期的にチェックするECCチェック。これにより、劣化したデータ保持によって生じた時間エラーを検出しない危険性が減少する。例えば、通常はコピー1のみを読み出す場合、コピー2は、エラーがECCによって回復することができないレベルに徐々に劣化して、第2のコピーを使用することができなくなる。プリエンプティブなデータ移転図20に関連して説明したように、ブロック管理システムは、その動作中にフラッシュメモリ内に制御データのセットを保持する。制御データのこのセットは、ホストデータと同様に、メタブロックに記憶される。このように、制御データ自体はブロック管理されることになり、更新を受けるので、ガーベッジコレクション動作も受けることになる。また、低階層のデータが高階層のデータよりも頻繁に更新される、制御データの階層が存在することについても説明してきた。例えば、すべての制御ブロックは、書き込むためのN個の制御セクタを有すると想定すると、制御更新および制御ブロック移転の以下のシーケンスが通常生じる。図20を再び参照すると、各N個のCBI更新によって、CBIブロックが充填されて、CBI移転書き換えおよびMAP更新がトリガされる。カオス的ブロックが閉鎖されると、GAT更新もトリガされる。各GAT更新は、MAP更新をトリガする。各N個のGAT更新によって、ブロックが充填されて、GATブロック移転がトリガされる。加えて、MAPブロックが一杯になると、MAPブロック移転およびMAPAブロックMAPAブロックがあればであるが、そうでなければ、BOOTブロックはMAPを直接ポイントする更新もトリガされる。加えて、MAPAブロックが一杯になると、MAPAブロック移転、BOOTブロック更新、およびMAP更新もトリガされる。加えて、BOOTブロックが一杯になると、他のBOOTブロックに対するアクティブなBOOTブロック移転がトリガされる。BOOT制御データが先頭で、次にMAPA、MAP、そしてGATが続いて階層が形成されるので、N3回のGAT更新毎に、GAT、MAP、MAPA、およびBOOTブロックのすべてが移転されるようなカスケード制御更新が生じることとなる。GAT更新がホスト書き込みによるカオス的または順次更新ブロックの閉鎖によって生じる場合、ガーベッジコレクション動作すなわち、移転または書き換えも生じることとなる。カオス的更新ブロックのガーベッジコレクションの場合、CBIが更新されるが、CBIブロック移転もトリガされる。よって、この極端な例の場合、数多くのメタブロックが同時にガーベッジコレクションされる。階層の各制御データブロックが、埋め込みおよび移転に関して独自の周期性を有することがわかる。それぞれが通常通り進めば、数多くのブロックのフェーズが並んで、これらすべてのブロックが関与する大量の移転またはガーベッジコレクションを同時にトリガするときがあることになる。数多くの制御ブロックを移転するには長い時間がかかり、このような大量の制御動作によって生じる長時間の遅延を許容しないホストもあるので、これは避けるべきである。本発明の他の態様によれば、ブロック管理システムを伴う不揮発性メモリにおいて、数多くの更新ブロックすべてを並行して移転する必要が生じるような状況を回避するために、制御ガーベッジコレクションまたはメモリブロックのプリエンプティブな移転が実施される。例えば、この状況は、ブロック管理システムの動作を制御するために使用される制御データを更新する際に生じうる。制御データ種の階層は更新頻度が様々なので、その関連する更新ブロックは、それぞれ異なる度合いで、ガーベッジコレクションまたは移転を必要とすることとなる。1つより多くの制御データ種のガーベッジコレクション動作が同時に生じるときがあることになる。極端な例の場合、すべての制御データ種についての更新ブロックの移転フェーズが並んでしまうこともあり得るので、すべての更新ブロックが同時に移転を必要とすることになってしまう。この望ましくない状況は、本発明によって回避され、本発明において、現在のメモリ動作が自発的なガーベッジコレクション動作に対応することができるときにはいつでも、ブロックが完全に埋められる前に予め更新データのプリエンプティブな移転を生じさせる。特に、最も遅いレートを有する、階層内で最高位のデータ種を有するブロックに優先度が与えられる。このように、最も遅いレートのブロックが移転されると、他のガーベッジコレクションを比較的長い時間行う必要がなくなる。また、階層内で高いところに位置する遅いレートのブロックは、トリガする移転のカスケードをほとんど有しない。本発明の方法は、様々なブロックのフェーズが並ぶのを避けるために、混合物全体に対してある種のディザリングを導入するとみなすことができる。よって、機会が生じるときはいつでも、完全に充填されるのにはあまりマージンのない、低速に充填されるブロックが、プリエンプティブに移転されることになる。カスケード効果によって、階層が低いデータが階層が高いデータよりも高速に変化している制御データの階層を有するシステムにおいて、階層内で高いところにある制御データのブロックに対して優先度が与えられる。自発的なプリエンプティブな移転を行う機会の一例として、ホスト書き込みが、それ自体、移転をトリガしないので、待ち時間の期間の余裕を使用してプリエンプティブな移転動作を行うという場合である。一般的に、絶対に移転されなければならないブロックの前のマージンは、ブロックが完全に充填される前の未書き込みのメモリユニットの所定の数である。ブロックが満杯になる前に移転を突然行っても十分なマージンであるかどうかを考慮する必要はあるが、あまりにも早計でないならば、リソースの無駄となってしまう。好ましい実施形態において、未書き込みのメモリユニットの所定の数は、1つから6つの間のメモリユニットである。図48は、制御データを記憶するメモリブロックのプリエンプティブな移転のフローチャートを示す。ステップ1202:不揮発性メモリをブロックに組織化し、各ブロックは、共に消去可能なメモリユニットに分割される。ステップ1204:互いに異なる種類のデータを保持する。ステップ1206:互いに異なる種類のデータにランク付けを割り当てる。ステップ1208:各ブロックが実質的に同一の種類のデータを記憶するように、前記互いに異なる種類のデータの更新を複数のブロックに渡って記憶する。ステップ1210:ブロックが所定の数よりも少ない空メモリユニットを有し、かつ前記複数のブロックに渡って最高ランクのデータ種類を有することに応じて、前記ブロックのデータの現在の更新を他のブロックへ移転する。中断されなければ、ステップ1208へ進む。図20に示されている制御データについてのプリエンプティブな移転を実施するためのアルゴリズムの例は、以下のとおりである。Ifユーザデータのためにガーベッジコレクションがない場合ORMAPに残る未書き込みのセクタは6つ以下であるORGATに残る未書き込みのセクタは3つ以下である、ThenIfBOOTに残る未書込みのセクタは1つであるThenBOOTを移転すなわち、ブロックに移転ElseIfMAPAに残る未書込みのセクタは1つであるThenMAPAを移転してMAPを更新ElseIfMAPに残る未書き込みのセクタは1つであるThenMAPを移転ElseIf最終更新または最大GATに残る未書込みのセクタは1つであるThenGATを移転ElseIfCBIに残る未書込みのセクタは1つであるThenCBIを移転ElseElseExitよって、プリエンプティブな移転は、通常、ユーザデータガーベッジコレクションが生じることなく行われる。最悪の場合、すべてのホスト書き込みがユーザデータガーベッジコレクションをトリガするが、1つのブロックの自発的な移転には時間があり、プリエンプティブな移転を1回に1つの制御ブロックに対して行うことができる。ユーザデータガーベッジコレクション動作および制御更新は物理的エラーと同時に生じることがあるので、例えば、ブロックがまた2つ以上の未書き込みのメモリユニット例えば、セクタを有している間などに、プリエンプティブな移転または制御されたガーベッジコレクションを事前に行っておくことで、安全のための大きなマージンを持っておく方がよい。本発明の様々な態様をいくつかの実施形態と共に説明してきたが、本発明が添付の特許請求の範囲の全範囲内においてその権利が保護されるべきであることが理解されよう。"