【課題】ユーザデータをメモリアレイにプログラムし、またメモリアレイからユーザデータを読み出す間の並列性を高める。
【解決手段】データラン内のデータは、不揮発性メモリアレイの、データ境界の位置に応じて構成される適応メタブロック９８に格納される。適応メタブロック９８を形成するために使われるプレーンは、アレイの消去ブロックの効率的な使用を提供するアルゴリズムに従って選択される。また、そのプレーン内でコピー操作を実行することができるように、更新されているマテリアルのために使用されているのと同じプレーンを新しいマテリアルのために使用することを考慮する。同時に２つ以上の適応メタブロックをプログラムすることによって、小さな適応メタブロックで高い並列性を維持する。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不揮発性メモリシステムの操作に関し、特にこのようなメモリシステム内でのデータの処理に関する。
【背景技術】
【０００２】
今日、特に小型形状のファクタカードの形式である商業的に成功した不揮発性メモリ製品が多くあり、それらは１つ以上の集積回路チップ上に形成されたフラッシュＥＥＰＲＯＭ（フラッシュ形の電気的に消去可能でプログラム可能な読み出し専用メモリ）のアレイを使用する。メモリコントローラは、必ずしもそうとは限らないが普通は別の集積回路チップ上にあり、カードが取り外し可能に接続されているホストとインターフェイスし、そのカード内のメモリアレイの動作を制御する。このようなコントローラは、通常、マイクロプロセッサと、何らかの不揮発性読み出し専用メモリ（ＲＯＭ）と、揮発性ランダムアクセスメモリ（ＲＡＭ）と、データのプログラミングおよび読み出し中にデータからそれがコントローラを通るときに誤り訂正符号（ＥＣＣ）を計算する回路などの１つ以上の特別の回路とを含む。市販されているカードのうちの幾つかは、コンパクトフラッシュ（登録商標）（ＣＦ）カード、マルチメディアカード（ＭＭＣ）、セキュアデジタル（ＳＤ）カード、スマートメディアカード、個人タグ（Ｐ−Ｔａｇ）およびメモリスティックカードである。ホストは、パーソナルコンピュータ、ノートブックコンピュータ、個人用携帯情報端末（ＰＤＡ）、種々のデータ通信装置、デジタルカメラ、携帯電話、携帯用オーディオプレーヤ、自動車音響システム、および類似のタイプの装置を含む。メモリカードの実装例のほかに、このタイプのメモリは、いろいろなタイプのホストシステムに択一的に埋め込まれてもよい。
【０００３】
２つの一般的なメモリセルアレイの構成、ＮＯＲおよびＮＡＮＤが、商業的に応用されている。代表的なＮＯＲアレイでは、メモリセルは、列方向に延びる隣接するビットラインソースおよびドレイン拡散部の間に接続され、コントロールゲートがセルの行に沿って延びるワードラインに接続される。メモリセルは、ソースとドレインとの間のセルチャネル領域の少なくとも一部分の上に位置する少なくとも１つの記憶素子を含む。従って、記憶素子のプログラムされたレベルの電荷がセルの動作特性を制御し、アドレス指定されたメモリセルに適切な電圧を印加することにより読み出される。このようなセルの例、メモリシステムにおけるその使用方法およびそれらを製造する方法が、米国特許第５，０７０，０３２号（特許文献１）、第５，０９５，３４４号（特許文献２）、第５，３１３，４２１号（特許文献３）、第５，３１５，５４１号（特許文献４）、第５，３４３，０６３号（特許文献５）、第５，６６１，０５３号（特許文献６）および第６，２２２，７６２号（特許文献７）において見いだされ、これらの特許は、本願明細書において引用されている全ての特許および特許出願と共に、その全体が本願明細書において参照により援用されている。
【０００４】
ＮＡＮＤアレイは、個々のビットラインと基準電位との間に１つ以上の選択トランジスタと共に接続された３個以上の、例えば１６または３２個の、メモリセルの直列ストリングを利用してセルの列を形成する。ワードラインは、これらの多数の列の中でセルを横断して延びる。列の中の個々のセルは、プログラミング中、ストリングを通って流れる電流がアドレス指定されたセルに蓄積されている電荷のレベルに依存するようにストリング中の残りのセルをオンに激しく転換させることによって読み出され検証される。ＮＡＮＤ構成のアレイの例と、メモリシステムの一部としてのその動作とが、米国特許第５，５７０，３１５号（特許文献８）、第５，７７４，３９７号（特許文献９）、第６，０４６，９３５号（特許文献１０）および第６，５２２，５８０号（特許文献１１）において見出される。
【０００５】
現在のフラッシュＥＥＰＲＯＭアレイの電荷記憶素子は、前に参照により援用されている特許において論じられているように、大概、通常は導伝性のドープされたポリシリコン材料から形成される導電性フローティングゲートである。フラッシュＥＥＰＲＯＭシステムで有益な１つの代わりのタイプのメモリセルは、電荷を不揮発性に蓄積するために導伝性フローティングゲートの代わりに非導電性誘電体材料を利用する。酸化シリコン、窒化シリコンおよび酸化シリコン（ＯＮＯ）から形成される３層誘電体が導電性コントロールゲートと、メモリセルチャネルの上の半導体基板の表面との間に挟まれる。セルは、セルチャネルから窒化物に電子を注入することによってプログラムされ、電子はそこに捉えられて限られた領域に蓄積され、その窒化物にホットホールを注入することによって消去される。誘電体記憶素子を使用する幾つかの特定のセル構造およびアレイが、ハラリらの米国公開特許出願第２００３／０１０９０９３号（特許文献１２）に幾つか記載されている。
【０００６】
個々のフラッシュＥＥＰＲＯＭセルは、或る量の電荷を、１ビット以上のデータを表す電荷記憶素子または電荷記憶単位に蓄積する。記憶素子の電荷レベルは、そのメモリセルのしきい値電圧（通例、Ｖ_T として参照される）を制御し、それをセルの記憶状態を読み出す動作の基礎として使用する。しきい値電圧ウィンドウは、通例、メモリセルの２つ以上の記憶状態の各々について１つずつの、数個の範囲に分割される。これらの範囲は、個々のセルの記憶状態を判定することを可能にする名目上の感知レベルを含む保護帯域により分離される。これらの記憶レベルは、近隣のまたは他の関連するメモリセル、ページまたはブロックにおいて実行される電荷妨害をするプログラミング、読み出しまたは消去動作の結果としてシフトする。従って、通常、コントローラによって誤り訂正符号（ＥＣＣ）が計算されて、プログラムされるホストデータと共に記憶され、読み出し動作時にデータを検証して必要ならば或るレベルのデータ訂正を実行するために使用される。また、シフトする電荷レベルは、妨害をする操作がそれらを完全にその画定された範囲の外へシフトさせ、従ってエラーのあるデータが読み出されるようになる前に、時折その状態範囲の中心に戻されて再蓄積される。データリフレッシュまたはスクラブと称されるこの処理は、米国特許第５，５３２，９６２号（特許文献１３）および第５，９０９，４４９号（特許文献１４）に記載されている。
【０００７】
殆ど全ての集積回路の用途の場合と同様に、何らかの集積回路機能を実現するために必要とされるシリコン基板面積を小さくする圧力は、フラッシュＥＥＰＲＯＭメモリセルアレイに関しても存在する。所与のサイズのメモリカードおよび他のタイプのパッケージの記憶容量を増大させるためにシリコン基板の所与の面積に記憶可能なデジタルデータ量を増大させること、或いは容量を増大させかつサイズを減少させることが絶え間なく望まれている。データの記憶密度を増大させる１つの方法は、メモリセルあたりおよび／または記憶単位または記憶素子あたり１ビットより多いデータを記憶させることである。これは記憶素子の電荷レベルの電圧範囲のウィンドウを３つ以上の状態に分割することにより達成される。このような状態を４つ使えば各セルは２ビットのデータを記憶することができ、８つの状態では記憶素子あたり３ビットのデータを記憶することができるなどとなる。フローティングゲートを用いる多状態フラッシュＥＥＰＲＯＭ構造とその動作とが、米国特許第５，０４３，９４０号（特許文献１５）および第５，１７２，３３８号（特許文献１６）に記載され、誘電体フローティングゲートを用いる構造については、前述した米国公開特許出願第２００３／０１０９０９３号（特許文献１２）に記載されている。米国特許第５，９３０，１６７号（特許文献１７）および第６，４５６，５２８号（特許文献１８）に記載されているように、多状態メモリセルアレイの選択された部分を種々の理由から２状態（バイナリ）で動作させることもできる。
【０００８】
代表的なフラッシュＥＥＰＲＯＭアレイのメモリセルは、一緒に消去されるセルの別々のブロックに分割される。すなわち、消去ブロックは消去単位、すなわち同時に消去可能な最小数のセルである。各消去ブロックは通常１ページ以上のデータを記憶し、ページはプログラミングおよび読み出しの最小単位であるが、別々のサブアレイまたはプレーンで２ページ以上が並行してプログラムされ或いは読み出されてもよい。各ページは通常１セクタ以上のデータを記憶し、セクタのサイズはホストシステムにより確定される。一例としてのセクタは、磁気ディスクドライブに関して確立されている標準規格に従う５１２バイトのユーザデータと、そのユーザデータおよび／またはそれらが記憶される消去ブロックに関する或る個数のバイトのオーバーヘッド情報とを含む。このようなメモリは、通常、各消去ブロックの中の１６，３２或いはそれより多数のページで構成され、各ページは１セクタ或いはほんの数個のホストセクタのデータを記憶する。
【０００９】
ユーザデータをメモリアレイにプログラムし、またメモリアレイからユーザデータを読み出す間の並列性の程度を高めるために、アレイは、通常、一般にプレーンと称される複数のサブアレイに分割され、それらは、データのセクタが数個または全てのプレーンの各々に同時にプログラムされ或いはプレーンの各々から同時に読み出されるように並列動作を可能にするそれ自身のデータレジスタおよび他の回路を含む。単一の集積回路上の１つのアレイは複数のプレーンに物理的に分割されてよく、或いは各プレーンが別々の１つ以上の集積回路チップから形成されてもよい。このようなメモリの実装例が、米国特許第５，７９８，９６８号（特許文献１９）および第５，８９０，１９２号（特許文献２０）に記載されている。
【００１０】
或るメモリシステムでは、物理的なメモリセルは２つ以上のゾーンにもグループ分けされる。ゾーンは、物理的メモリまたはメモリシステムの、特定の範囲の論理ブロックアドレスがその中にマッピングされる任意の分割された部分集合である。例えば、６４メガバイトのデータを記憶可能なメモリシステムは、ゾーンあたり１６メガバイトのデータを記憶する４つのゾーンに分割される。このとき論理ブロックアドレスの範囲も４つのグループに分割され、その４つのゾーンのうちの各ゾーンの消去ブロックに１つのグループが割り当てられる。代表的な実装例では、論理ブロックアドレスは、各々のデータが、その中に論理ブロックアドレスがマッピングされる単一の物理ゾーンの外側には決して書き込まれないように、制限される。それ自身のアドレス指定回路、プログラミング回路および読み出し回路を各々有する複数のプレーン（サブアレイ）に分割されているメモリセルアレイでは、各ゾーンは、好ましくは、通常は各プレーンからの同数の消去ブロックである、複数のプレーンからの消去ブロックを含む。ゾーンは、主として、論理から物理への変換のようなアドレス管理を簡単化するために使用され、変換テーブルが小形化し、それらのテーブルを保持するために必要なＲＡＭメモリが少なくなり、メモリの現在のアクティブな領域をアドレス指定するアクセス時間が高速化するという結果をもたらすけれども、制限の多い性質ゆえに最適には及ばない損耗レベリングをもたらす可能性を有する。
【００１１】
さらに効率よくメモリを管理するために、消去ブロック同士を連結して仮想ブロック、すなわちメタブロックを形成してもよい。すなわち、各メタブロックは、各プレーンから１つずつの消去ブロックを規定する。メタブロックの使用は、米国特許第６，７６３，４２４号（特許文献２１）に記載されている。メタブロックは、データをプログラムし、読み出すための宛先としてホスト論理ブロックアドレスによって特定される。同様に、メタブロックの全ての消去ブロックは一緒に消去される。このような大きなブロックおよび／またはメタブロックで動作するメモリシステムにおけるコントローラは、ホストから受け取られた論理ブロックアドレス（ＬＢＡ）とメモリセルアレイ内の物理的ブロック番号（ＰＢＮ）との間の変換を含む幾つかの機能を実行する。ブロック内の個々のページは、通常、ブロックアドレス内でのオフセットにより特定される。アドレス変換は、論理ブロック番号（ＬＢＮ）と論理ページとの中間項の使用をしばしば必要とする。
【００１２】
メタブロックに記憶されたデータはしばしば更新され、メタブロックで発生する更新の尤度は、メタブロックのデータ容量が大きくなるにつれて大きくなる。１メタブロックの更新されたセクタは、通常、他のメタブロックに書き込まれる。変更されていないセクタも、普通、データを統合するために、同じプログラミング動作の一部として、元のメタブロックから新しいメタブロックにコピーされる。或いは、変更されていないデータは、後に更新されたデータと統合されて再び単一のメタブロックにされるまで、元のメタブロックに留まることができる。
【００１３】
変更されていないセクタをコピーする操作は、消去操作が実行されるまでは元のメタブロックを使用することができないので、コピーに要する時間を増やし、メモリアレイにおいてデータにより占められるスペースを増やすことになる。変更されていないセクタをコピーする操作は、ホストファイルの異なるメタブロックの中への論理的フラグメンテーションの結果である。１つのメタブロックが２つのホストファイルの複数の部分を含む場合、一方のファイルを更新することは、同じメタブロックに記憶されている他方のファイルの部分をコピーすることも含む。メタブロックが大きくなるにつれて、コピーされる部分も大きくなる。従って、メタブロックが大きくなるときに、論理的フラグメンテーションは大きな問題となる。
【００１４】
大きなブロックまたはメタブロックシステムを、消去済みブロックプールにおいて維持されている何らかの余分の消去ブロックと共に操作することは普通のことである。１つの消去ブロックの容量より少ない１ページ以上のデータが更新されるとき、更新されるページをプールからの消去ブロックに書き込み、その後に変更されないページのデータを元の消去ブロックから消去プールブロックへコピーすることは典型的なことである。この技術の変形例が、前に援用されている米国特許第６，７６３，４２４号（特許文献２１）に記載されている。時間が経つと、ホストデータファイルが再書き込みされ更新される結果として、多数の消去ブロックの割合に少数のページが有効なデータを含み、残りのページが最早現行のものではないデータを含むようになる。アレイのデータ記憶容量を効率よく使用することができるように、有効なデータの論理的に関連し合っているデータページは、時々、多数の消去ブロックの中のフラグメントから集められて、より小数の消去ブロックに統合される。この処理は、一般に“ガーベッジコレクション”と称される。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】米国特許第５，０７０，０３２号
【特許文献２】米国特許第５，０９５，３４４号
【特許文献３】米国特許第５，３１３，４２１号
【特許文献４】米国特許第５，３１５，５４１号
【特許文献５】米国特許第５，３４３，０６３号
【特許文献６】米国特許第５，６６１，０５３号
【特許文献７】米国特許第６，２２２，７６２号
【特許文献８】米国特許第５，５７０，３１５号
【特許文献９】米国特第５，７７４，３９７号許
【特許文献１０】米国特許第６，０４６，９３５号
【特許文献１１】米国特許第６，５２２，５８０号
【特許文献１２】米国公開特許出願第２００３／０１０９０９３号
【特許文献１３】米国特許第５，５３２，９６２号
【特許文献１４】米国特許第５，９０９，４４９号
【特許文献１５】米国特許第５，０４３，９４０号
【特許文献１６】米国特許第５，１７２，３３８号
【特許文献１７】米国特許第５，９３０，１６７号
【特許文献１８】米国特許第６，４５６，５２８号
【特許文献１９】米国特許第５，７９８，９６８号
【特許文献２０】米国特許第５，８９０，１９２号
【特許文献２１】米国特許米国特許第６，７６３，４２４号
【特許文献２２】米国特許出願第１０／７４９，８３１号
【特許文献２３】米国特許出願第１０／７５０，１５５号
【特許文献２４】本願と同じ日に出願された“スクラッチパッドブロック”という米国特許出願
【発明の概要】
【００１６】
データは、メモリアレイにおいて適応メタブロックに記憶される。適応メタブロックのサイズは、記憶されるべきデータに合わせて調整される。適応メタブロックのサイズは、データの性質（制御データ、ホストからのデータ）に基づいて決定されてよく、或いはファイル間の境界のようなデータの中の境界に基づいて決定されてもよい。適応メタブロックをデータに応じて構成すると、論理的フラグメンテーションの効果が減少する。
【００１７】
メモリアレイの１つの消去ブロック内のデータに等しいデータを含む論理グループは、論理的に連続するセクタから形成される。適応論理ブロックは論理グループから形成される。適応論理ブロックは、いろいろな数の論理グループを含むことができる。個々の適応論理ブロックはメモリアレイにおいて個々の適応メタブロックに格納される。適応メタブロックの中の消去ブロックの数は、対応する適応論理ブロック内の論理グループの数に等しい。従って、適応メタブロックは、可変的な数の消去ブロックを有する。メタブロックの消去ブロックは、メモリアレイの全てのプレーンよりは少ないプレーンからの消去ブロックである。一度に２つ以上の適応メタブロックをプログラムすることができる。適応メタブロックは、記憶されるべきデータに応じて形成される。大きな適応メタブロックは、プログラミング中に高度の並列性を得るために使用されてもよい。格納されているデータの効率的な更新を可能にするために、より小さな適応メタブロックを使用することができる。
【００１８】
適応論理ブロックは、適応論理ブロック同士の間の境界が、例えばファイルまたはデータのストリームの間の境界などのデータ中の境界を反映するように、形成される。適応論理ブロックをこのように調整することによって、メモリアレイ内でのデータのコピー操作を減らすことができる。データが更新される場合、その更新されたデータを少量の古いデータと共に保持するように新しい適応論理ブロックを形成することができる。従って、同じデータが再び更新されるのであれば、コピーされる必要のある古いデータは少量だけである。
【００１９】
適応論理ブロックが部分的に満たされる場合、そのデータは、より小さな適応論理ブロックにコピーされる。これは、部分的に満たされた適応論理ブロックがプログラムされる前に行われてよく、或いは部分的に満たされた適応論理ブロックが適応メタブロックにプログラムされた後に行われてもよく、その場合には、部分的に満たされた適応論理ブロックを含む適応メタブロックは陳腐とマークされることになる。より小さな適応論理ブロックはメモリアレイにおいてより小さな適応メタブロックにプログラムされる。従って、メモリアレイにおいてスペースが節約されることになる。
【００２０】
更新データを保持するために非順次的に更新されるメタブロック（カオス的ブロック）を使用する構成では、代わりに適応メタブロックを使用することができる。適応メタブロックのサイズは、更新される論理アドレス範囲に応じて選択される。適応メタブロックが特定の論理アドレス範囲に合わせて調整されるならば、その範囲における更新は、データのコピーがより少ないので、より効率的に実行される。
【００２１】
適応メタブロックの形成と、記憶されたデータの位置の記録とは、メディアマネージャによって実行される。メディアマネージャは、利用可能な消去ブロックの記録を維持する。記憶されたデータの位置の記録もメディアマネージャによって維持される。記憶されているデータの位置の記録は、各論理グループについて１つのエントリを有するテーブル（またはリスト）において維持される。各論理グループについてのエントリは、その論理グループを含む適応メタブロック（および対応する適応論理ブロック）のサイズと、その適応論理ブロックの中での論理グループの位置と、メタブロックの消去ブロックのうちの１つの物理的位置とを示す。
【００２２】
データを適応メタブロックに格納するフラッシュメモリアレイと組み合わせて不揮発性ランダムアクセスメモリ（ＮＶＲＡＭ）を使用することができる。ＮＶＲＡＭは、データがフラッシュメモリにプログラムされる前に、データを保持するデータバッファとして使用することができる。データがＮＶＲＡＭ内にある間に、それをどのように効率的にプログラムすることができるかを判定することができる。数個のデータストリームをＮＶＲＡＭにおいて保持し、一緒に効率的な方法でプログラムすることができる。ＮＶＲＡＭは、フラッシュメモリアレイの一部分の代わりとして一定のデータのために代わりの記憶位置を提供することもできる。このアプリケーションでは、ＮＶＲＡＭは、フラッシュメモリと同様に使用されるように構成することができる。ＮＶＲＡＭは、フラッシュメモリの消去ブロックと同じサイズの複数の単位に分割することができる。ＮＶＲＡＭは１つの物理アドレス範囲を持つことができるので、ＮＶＲＡＭに記憶されている論理グループにＮＶＲＡＭ物理アドレス範囲内の物理アドレスが割り当てられる。論理グループは、頻繁に更新されるのであれば、ＮＶＲＡＭに割り当てることになる。従って、フラッシュメモリアレイにおけるコピーおよび消去を行うことなく更新を行うことが可能となる。ＮＶＲＡＭにおけるデータの更新はフラッシュメモリにおける更新より効率的であるが、電源が失われても揮発性メモリの場合のようにデータが失われることはない。
【００２３】
ファイル境界のようなデータ境界が、フラッシュメモリに格納されるべきデータの中に生じる。記憶されるべきデータが論理グループを単位としてアドレス指定される場合、論理グループ同士の間の境界はデータ境界と一致しないことがある。従って、論理グループと、論理グループから形成されるメタグループ（論理ブロック）とがデータ境界を含んでもよい。大きなメタグループおよびメタブロックがデータ境界を含む場合、ファイルの更新は大量のデータをコピーすることを必要とする。これは、システム資源を使用し、新しいデータをメモリアレイに書き込む速度を低下させる。
【００２４】
適応メタブロックは、データ境界を最小サイズの適応メタブロックに格納するように形成することができる。データ境界を最小サイズのメタブロックにプログラムすることによって、その後にファイル内のデータを更新する間にデータをコピーする操作を少なくすることができる。ファイルの更新が行われるとき、そのファイルを含む元のメタブロックは陳腐なデータを含む。幾つかの元のメタブロックは、更新されるファイルの一部ではないデータを含む。それらのデータは、陳腐ではないかも知れず、従って、元のメタブロックが消去されて再使用される前に新しい位置にコピーされる必要がある。このような元のメタブロックをより小さくすることによって、コピーされるデータの量を減らすことができる。１つの消去ブロックから成る適応メタブロックが使用される場合、１論理グループより少ないデータがコピーされる。複数のこのような適応メタブロックは並列にプログラムされるので、縮小された適応メタブロックサイズは、プログラミング中に使用される並列性を低下させるとは限らない。
【００２５】
例えば１つのファイルの末端に存するデータ境界が元のメタブロックの中にあり、そのデータ境界の後にデータがない場合など、或る元のメタブロックはデータで完全に埋められてはいないかもしれない。このような元のメタブロック内のデータは、最小限の空きスペースでデータを保持するサイズのメタブロックにコピーすることができる。これによって、メモリアレイ内のスペースを節約することが可能となる。小さな適応メタブロックは並列にプログラムすることができる。並列にプログラムされる複数の適応メタブロックは、再配置されたデータとホストデータとを含み得るので、再配置操作は、ホストデータがメモリアレイに書き込まれるのと同時に実行される。
【００２６】
或るメモリシステムでは、ホストは、論理境界（例えば、ファイル境界およびデータラン境界）の位置に関して、ホストからメモリシステムに送られるデータで情報をメモリコントローラに供給することができる。ホストにより提供された（或いは他の方法で得られた）論理境界位置に基づいて、データは、始めに中間フォーマットでメモリアレイまたはＮＶＲＡＭに記憶されることなく、整列したフォーマットでメモリアレイに直接記憶するこができる。論理境界を含まないデータの部分は、メモリアレイの最大サイズのメタブロックに直接書き込まれてもよい。
【００２７】
論理境界を含むデータの部分は、結局、最小サイズのメタブロックに格納される。しかし、このようなメタブロックだけを書き込むのは低速であろうから、データのそのような部分は始めにバッファリングされる。後に整列した態様でメモリアレイに書き込まれるホストからのデータの部分を格納するようにシリアルフラッシュバッファが設けられる。シリアルフラッシュバッファは最大サイズのメタブロックから成るので、データは最大の並列性で書き込まれる。データがシリアルフラッシュバッファからコピーされるときには、一度に２つ以上の適応メタブロックを書き込むことによってデータは高度の並列性で書き込まれる。従って、最小サイズのメタブロックに割り当てられるデータは、始めにシリアルフラッシュバッファに最大の並列性で書き込まれ、後に複数の最小サイズのメタブロックに並列に書き込むことによって最小サイズのメタブロックに高度の並列性でコピーされる。このように、シリアルフラッシュバッファは、小さなメタブロックが使用される場合にも高度の並列性（従って、高度の性能）を保つのに役立つ。中間サイズのメタブロックについて、データはメモリアレイに直接書き込まれてもよく、或いは始めにメタブロックのサイズに応じてバッファリングされてもよい。
【００２８】
メモリに格納されているデータの部分は、部分の各末端に存する論理境界が最小サイズのメタブロックに格納されるときに、完全に整列した態様で格納されていると考えられる。データの部分は、一方の末端に存する論理境界が最小サイズのメタブロックに格納され、かつ他方の末端に存する論理境界が最小サイズのメタブロックに格納されていない場合に、部分的に整列した態様で格納されている。データの部分は、どの論理境界も最小サイズのメタブロックに格納されていなければ、整列していない態様で格納されている。データの部分が更新されるとき、それが更新するデータよりも高度の整列で格納される。
【図面の簡単な説明】
【００２９】
【図１Ａ】一緒に動作する不揮発性メモリのブロック図である。
【図１Ｂ】一緒に動作するホストシステムのブロック図である。
【図２】図１Ａのメモリアレイの編成の第１の例を示す。
【図３】図１Ａのメモリアレイに記憶されているオーバーヘッドデータを伴うホストデータセクタの例を示す。
【図４】図１Ａのメモリアレイの編成の第２の例を示す。
【図５】図１Ａのメモリアレイの編成の第３の例を示す。
【図６】図５のメタブロックのようなメモリアレイにおけるメタブロックの例を示す。
【図７】図６に示されているようなメタブロックに記憶されている論理ブロックの例を示す。
【図８】元のデータがメモリアレイ内のメタブロックに記憶されるデータ更新を示す。
【図９Ａ】メモリアレイ内の適応メタブロックに格納される適応論理ブロックを示す。
【図９Ｂ】セクタから論理グループへ、および論理グループから図９Ａの適応論理ブロックへの論理マッピングを示す。
【図１０】２つの適応論理ブロックの２つの適応メタブロックへの並列プログラミングを示す。
【図１１】種々の構成で適応論理ブロックにマッピングされる論理グループを示す。
【図１２Ａ】更新されて新しい適応論理ブロックに格納される、適応論理ブロックに記憶されているデータを示す。
【図１２Ｂ】データストリームに適合するように再マッピングされる適応論理ブロックの例を示す。
【図１２Ｃ】データストリームに適合するように再マッピングされる適応論理ブロックの他の例を示す。
【図１３】より小さな適応論理ブロックに再マッピングされる、部分的に充填されている適応論理ブロックを示す。
【図１４】更新される論理アドレス範囲に適合させられているデータを更新するために使用される適応論理ブロックを示す。
【図１５Ａ】メモリアレイの適応メタブロックに記憶されている適応論理ブロックを示す。
【図１５Ｂ】メモリアレイに記憶されている図１５Ａの適応論理ブロックの論理グループのセクタを示す。
【図１５Ｃ】メモリアレイに記憶されている論理グループのセクタの他の例を示す。
【図１５Ｄ】２つの適応メタブロックが並列にプログラムされるセクタの配置の例を示す。
【図１５Ｅ】３つのメタブロックの並列プログラミングの例と、その結果としてのメタブロック内でのページの配置とを示す。
【図１５Ｆ】最初に更新されるセクタが適応メタブロック内の第１のセクタではないデータ更新の例を示す。
【図１６】メモリアレイの適応メタブロックに記憶されている論理グループの位置を記録したテーブルを示す。
【図１７】適応メタブロック構成を管理するために使用可能なメディアマネージャを示す。
【図１８Ａ】消去済みブロック管理階層の例を示すブロック図である。
【図１８Ｂ】１つの有効なセクタと複数の陳腐なセクタとを含む複数のセクタを含むＥＢＬブロックを示す。
【図１８Ｃ】アドレステーブル管理階層の例を示すブロック図である。
【図１８Ｄ】ブートアドレスおよびブートブロックを含むデータ構造を示す。
【図１９】ＮＶＲＡＭを含むメモリシステムを示す。
【図２０】ＮＶＲＡＭを使用するメモリアレイに効率的に記憶された２つのデータストリームを示す。
【図２１】ＮＶＲＡＭに記憶されている更新されたデータを示す。
【図２２】データランから成るファイルを示す。
【図２３】データランの中でのファイル境界を示す。
【図２４】データ単位の階層を示す。
【図２５】メタグループにマッピングされる２つのデータランを示す。
【図２６】メタグループにマッピングされるファイル境界を伴うデータランを示す。
【図２７】データ境界管理を伴うフラッシュメモリにデータを格納するための２つの方式を示す。
【図２８Ａ】図２５のメタグループＡ〜Ｄを記憶するメタブロックＡ〜Ｄから成るプログラムブロックを示す。
【図２８Ｂ】図２８ＡのメタブロックＡ〜Ｄにおけるセクタの構成を示す。
【図２８Ｃ】プログラムブロックに転送されるアキュムレータ内のセクタを示す。
【図２９Ａ】満杯のメタグループを示す。
【図２９Ｂ】部分的メタグループを示す。
【図２９Ｃ】短いメタグループを示す。
【図２９Ｄ】スタートメタグループを示す。
【図２９Ｅ】マルチファイルメタグループを示す。
【図３０Ａ】部分的メタグループの再マッピングを示す。
【図３０Ｂ】短いメタグループの再マッピングを示す。
【図３０Ｃ】スタートメタグループの再マッピングを示す。
【図３０Ｄ】マルチファイルメタグループの再マッピングを示す。
【図３１】ホストータおよび再配置されるデータの並列プログラミングを示す。
【図３２】シリアルフラッシュバッファを用いるホストデータの記憶を示す。
【図３３Ａ】ホストからのデータを格納する代替の方法を示す。
【図３３Ｂ】ホストからのデータの書き込みと共に元のデータがコピーされる図３３Ａの代替の方法を示す。
【図３４】ホストからのデータを格納するための代替の方式を示す。
【図３５Ａ】非整列で記憶されたデータランを示す。
【図３５Ｂ】部分的整列で記憶されたデータランを示す。
【図３５Ｃ】完全整列で記憶されたデータランを示す。
【図３５Ｄ】データランの代表的な構造を示す。
【図３５Ｅ】いろいろな長さのデータランの代表的な構造を示す。
【図３６】データラン内のデータの更新中に発生し得る遷移の例を示す。
【図３７】完全から完全への遷移の例を示す。
【図３８】部分的から完全への遷移の例を示す。
【図３９】部分的から部分的への遷移の例を示す。
【図４０】非整列から完全整列への遷移の例を示す。
【図４１】非整列から部分的整列への遷移の例を示す。
【図４２】非整列から部分的整列への遷移の第２の例を示す。
【図４３】非整列から非整列への例を示す。
【図４４】一定のデータ構造と、データ構造と関連して実行可能な操作との一覧表である。
【図４５】本発明の実施形態に従ってセクタを記憶する操作を示すフローチャートである。
【図４６】図４５のセクタの書き込みを示すフローチャートである。
【図４７】本発明の実施形態に従ってデータランを閉じる操作を示すフローチャートである。
【発明を実施するための形態】
【００３０】
メモリ構成とその動作
始めに図１Ａを参照すると、フラッシュメモリはメモリセルアレイおよびコントローラを含む。図に示されている例では、２つの集積回路装置（チップ）１１および１３が、メモリセルのアレイ１５と種々の論理回路１７とを含む。論理回路１７は、データ、コマンドおよび状態回路を通して別のチップ上のコントローラ１９とインターフェイスし、またアドレス指定、データ転送および感知、および他のサポートをアレイ１３に提供する。メモリアレイチップの数は、提供される記憶容量に依存して、１から多数とすることができる。メモリセルアレイは、単一のチップ上に配置されてもよく、或いは複数のチップ上の複数のメモリセルから成ってもよい。コントローラと、アレイの一部または全体とを単一の集積回路チップに代わりに結合させることもできるが、現在では経済的な選択肢ではない。
【００３１】
代表的なコントローラ１９は、マイクロプロセッサ２１と、主としてファームウェアを記憶する読み出し専用メモリ（ＲＯＭ）２３と、主としてメモリチップ１１および１３に書き込まれ或いはこれらから読み出されるユーザデータの一時的記憶のためのバッファメモリ（ＲＡＭ）２５とを含む。バッファメモリ２５は、揮発性または不揮発性のメモリであってよい。回路２７はメモリアレイチップ（１つまたは複数）とインターフェイスし、回路２９は結線３１を通してホストとインターフェイスする。この例ではデータの完全性は、符号を計算するために専用される回路３３でＥＣＣを計算することにより決定される。ユーザデータがホストからフラッシュメモリアレイに格納されるべく転送されているときに、回路はデータからＥＣＣを計算し、その符号はメモリに格納される。そのユーザデータが後にメモリから読み出されるとき、データは再び回路３３を通され、同じアルゴリズムによってＥＣＣを計算して、符号を計算されてそのデータと共に格納された符号と比較する。それらが同様であれば、データの完全性が確認される。それらが異なっていれば、利用される特定のＥＣＣアルゴリズムに依存して、アルゴリズムによりサポートされる数まで、エラーのあるビットを特定して訂正することができる。
【００３２】
図１Ａのメモリの結線３１はホストシステムの結線３１’と接合し、その例が図１Ｂに示されている。ホストと図１Ａのメモリとの間でのデータ転送はインターフェイス回路３５を通る。代表的なホストは、マイクロプロセッサ３７と、ファームウェア符号を格納するためのＲＯＭ３９と、ＲＡＭ４１とをも含む。他の回路およびサブシステム４３は、しばしば、その特定のホストシステムにより、大容量磁気データ記憶ディスクドライブと、キーボードのためのインターフェイス回路と、モニタなどとを含む。このようなホストの幾つかの例は、デスクトップコンピュータ、ラップトップコンピュータ、ハンドヘルドコンピュータ、パームトップコンピュータ、個人用携帯情報端末（ＰＤＡ）、ＭＰ３およびその他のオーディオプレーヤ、デジタルカメラ、ビデオカメラ、電子ゲーム機械、無線および有線の電話装置、留守番電話、ボイスレコーダ、ネットワークルータおよびその他を含む。
【００３３】
図１Ａのメモリは、図１Ｂのホストと取り外し可能に接続可能な形式でコントローラおよびその全てのメモリアレイ回路装置を含む小形の閉鎖形カードとして実現することができる。すなわち、接合結線３１および３１’は、カードを取り外して他のホストへ移すことを可能にし、或いは他のカードをホストに接続することによってカードを取り替えることを可能にする。或いは、メモリアレイ装置は、コントローラと結線３１とを含むカードと電気的にかつ機械的に接続可能な別のカードに封入されてもよい。他の選択肢として、図１Ａのメモリは図１Ｂのホストの中に埋め込まれてもよく、その場合結線３１および３１’は永久的に作られる。この場合、メモリは、普通は、他の構成要素と共にホストのエンクロージャーの中に含まれる。さらなる選択肢として、メモリチップ１１のようなメモリチップは、間にメモリコントローラを持たずにホストシステムの結線３１’に直接結合することができる。この場合、メモリコントローラの機能は、ホストシステムのマイクロプロセッサ３７によって実行される。
【００３４】
図２は、メモリアレイの一部分を示し、ここでメモリセルは消去ブロックにグループ分けされ、各消去ブロック内のセルは単一の消去操作の一部分として、普通は同時に、一緒に消去可能である。消去ブロックは、消去の最小単位である。
【００３５】
図２の個々のメモリセル消去ブロックのサイズは変化してもよいが、１つの商業的に実施されている形は、個々の消去ブロック内に単一のセクタのデータを含む。このようなデータセクタの内容が図３に示されている。ユーザデータ５１は通常５１２バイトである。ユーザデータ５１の他にオーバーヘッドデータがあり、これは、ユーザデータから計算されたＥＣＣ５３と、セクタデータおよび／または中にそのセクタがプログラムされている消去ブロックに関連するパラメータ５５と、パラメータ５５およびその他の包含される任意のオーバーヘッドデータから計算されたＥＣＣ５７とを含む。或いは、単一のＥＣＣが、ユーザデータ５１およびパラメータ５５の両方から計算されてもよい。
【００３６】
パラメータ５５は、消去ブロックが経験したプログラム／消去サイクルの数に関連する量を含むことができ、この量は各サイクル後に或いは一定の数のサイクルの後に更新される。この経験量が損耗レベリング・アルゴリズムで使用されるときには、全ての消去ブロックの使用（損耗）を均すために論理ブロックアドレスは定期的に異なる物理ブロックアドレスに再マッピングされる。経験量の他の使用法は、プログラミング、読み出しおよび／または消去の電圧およびその他のパラメータをいろいろな消去ブロックが経験したサイクルの数の関数として変更することである。
【００３７】
パラメータ５５は、メモリセルの記憶状態の各々に割り当てられる、それらの“回転 (rotation) ”と称されるビット値の表示を含むこともできる。これも、損耗レベリングに関して有益な効果を有する。ステータスまたは状態を示す１つ以上のフラグもパラメータ５５に含まれる。消去ブロックをプログラムしかつ／または消去するために使われる電圧レベルの表示もパラメータ５５の中に格納されてよく、それらの電圧は、消去ブロックが経験したサイクルの数および他のファクタが変化するときに更新される。パラメータ５５の他の例は、消去ブロック内の欠陥のあるセルの特定、この物理ブロック中にマッピングされたデータの論理アドレス、および主消去ブロックに欠陥がある場合における代用の消去ブロックのアドレスを含む。任意のメモリシステムに使われる複数のパラメータ５５の具体的な組み合わせは、設計に従って変化する。また、オーバーヘッドデータの一部または全部は、ユーザデータを含むか或いはオーバーヘッドデータが関連する消去ブロックにではなく、その機能に専用される消去ブロックに格納される。
【００３８】
図４のマルチセクタ消去ブロックは図２の単一データセクタ消去ブロックとは異なる。依然として消去の最小単位である例としての消去ブロック５９は、４つのページ０〜３を含み、その各々はプログラミングの最小単位である。１つ以上のホストセクタのデータが、普通は、少なくともセクタのデータから計算されたＥＣＣを含むオーバーヘッドデータと共に各ページに格納され、図３のデータセクタの形をとることができる。
【００３９】
１つの消去ブロック全体のデータを再書き込みするには、普通、消去ブロックプールの１つの使用可能な消去ブロックに新しいデータをプログラムすることが必要であり、その後に元の消去ブロックが消去されて消去プールに置かれる。１つの消去ブロックの全ページよりは少ないデータが更新されるときには、更新されるデータは、通常、消去済みブロックプールからの１つの消去ブロックの１つのページに格納され、残りの変更されないページ中のデータは元の消去ブロックから新しい消去ブロック中にコピーされる。その後に元の消去ブロックが消去される。この大ブロック管理手法の変形例は、元の消去ブロックからデータを移動させたり、それを消去したりせずに、更新されるデータを他の１つの消去ブロックの１つのページに書き込むことを含む。これは、同じ論理アドレスを有する複数のページをもたらす。データの最も新しいページは、セクタまたはページオーバーヘッドデータ内の１つのフィールドとして記録されるプログラミングの時間のような何らかの便利な手法により特定される。
【００４０】
別のマルチセクタ消去ブロック配置が図５に示されている。ここでは、メモリセルアレイ全体が２つ以上のプレーンに物理的に分割され、４つのプレーン０〜３が示されている。各プレーンは、他のプレーンから大幅に独立して動作するように、自身のデータレジスタ、センス増幅器、アドレス指定デコーダなどを有するメモリセルのサブアレイである。全てのプレーンが単一の集積回路装置上或いは複数の装置上に設けられてよく、一例は、各プレーンを１つ以上の別個の集積回路装置から形成することである。図５のシステム例における各消去ブロックは１６個のページＰ０〜Ｐ１５を含み、各ページは、１つ、２つまたはそれ以上のホストデータセクタと多少のオーバーヘッドデータとの容量を有する。
【００４１】
メタブロック
さらに他のメモリセル配置が図６に示されている。各プレーンが多数の消去ブロックを含んでいる。操作の並列性の程度を高めるために、別々のプレーン内の消去ブロックが論理的に連結されてメタブロックを形成する。このような１つのメタブロックが図６に示されている。各メタブロックは論理的にアドレス指定可能であり、メモリコントローラは、個々のメタブロックを形成する消去ブロックを割り当てて追跡する。ホストシステムは、データをセクタのストリームの形で供給する。このセクタのストリームは複数の論理ブロックに分割される。ここで、論理ブロックは、メモリアレイの１つのメタブロックに含まれるものと同数のデータセクタを含むデータの論理単位である。メモリコントローラは、各論理ブロックが格納されている記憶位置の記録を維持する。例えば、図６のこのような論理ブロック６１は、コントローラによりメタブロックを構成するブロックの物理的ブロック番号（ＰＢＮ）にマッピングされる論理ブロックアドレス（ＬＢＡ）により特定される。メタブロックの全てのブロックは一緒に消去され、各ブロックからのページは一般に同時にプログラムされ、読み出される。
【００４２】
図７は、メモリアレイに格納されるデータを示す。データは、ホストにより、データのセクタのストリーム７５の形で送られる。セクタは論理ブロック７１，７２に形成される。次に、論理ブロックはメタブロックにプログラムされる。例えば、論理ブロック７２はメタブロック７４にプログラムされる。図７は、４つのプレーンを有するメモリアレイ７６を示す。メタブロック７４は、プレーン０，１，２および３の各々からの１つの消去ブロックを有する。全てのプレーンが並列にプログラム可能なようにメタブロック７４はアレイの全てのプレーンにわたって延びる。従って、メタブロックのサイズは、通常、アレイの中のプレーンの数によって決まる。また、対応する論理ブロックのサイズは、このサイズによって決まる。
【００４３】
図８は、データがメタブロックに格納されているメモリアレイにおいて更新されるデータを示す。更新されたデータセクタ８１がメモリアレイに格納されるべくホストから受け取られる。更新されたデータセクタ８１は、論理ブロック８２，８３内の元のデータセクタに対応する。論理ブロック８２，８３内の元のデータはメモリアレイ８９内のメタブロック８４，８５に格納される。従って、メタブロック８４内のセクタのうちの幾つかとメタブロック８５内のセクタのうちの幾つかとは更新される必要がある一方、その他は更新不要である。更新は、更新されたデータセクタ８１を、更新される必要のないメタブロック８４，８５内の元のセクタと結合することにより行われる。これらの組み合わされたデータは置換メタブロック８６，８７に書き込まれ、元のメタブロック８４，８５は陳腐とマークされる。陳腐なメタブロック８４，８５は、結局、消去されて、ガーベッジコレクションの間に再び使用可能にされる。更新されたデータセクタ８１を元のセクタと結合させる操作は、データが受け取られるときに行うことができる。或いは、更新されたデータ８１のセクタは他の記憶位置に書き込まれ、後にガーベッジコレクションの一部として元のデータと結合することができる。大きなメタブロックは、並列性が大きいので高速プログラミングを可能にするけれども、大きなメタブロックに格納されているデータを更新するためには、少量の新しいデータだけが受け取られる場合でも大量のデータをコピーすることを必要とする。メタブロックにおいて新しいデータと元のデータとを統合する操作は、ガーベッジコレクションの間に顕著なオーバーヘッドを課すことになる。
【００４４】
適応メタブロック
図９Ａは、データをメモリアレイに格納するために使われる適応メタブロック９８の例を示す。データは、データのセクタのストリーム９９の形で受け取られる。セクタは、論理グループ９１，９２，９３を含む論理グループに形成される。論理グループは、メモリアレイの１つの消去ブロックに格納されているデータの量に等しいデータの論理単位である。論理グループは、ホストから受け取られた論理的に連続する複数のセクタから形成される。各論理グループは、特定の論理アドレス範囲で形成される。このように、論理グループは、多数のセクタを含むことができるけれども一般的には適応メタブロックより小さいデータの中間論理単位である。
【００４５】
論理グループは適応論理ブロックに形成される。適応論理ブロック或いは論理ブロックは“メタグループ”と称されてもよい。“メタグループ”という用語は“適応論理ブロック”という用語と同等であると考えられる。“適応論理ブロック”という用語がこの出願では一般的に使用される。適応論理ブロックは、可変数の論理グループを含む。図９Ａにおいて適応論理ブロック９５は３つの論理グループ９１，９２，９３を含む。適応論理ブロック９６は２つの論理グループを含み、論理ブロック９７は４つの論理グループを含む。適応論理ブロック９５は適応メタブロック９８にプログラムされる。適応論理ブロック９５は３つの論理グループ９１，９２，９３を含み、同様に、適応メタブロック９８は３つの消去ブロック９１１，９１２，９１３を含む。従って、適応メタブロック９８はアレイの各プレーンからの消去ブロックを持っているのではなくて、プレーン０，２および３からの消去ブロックのみを有する。適応メタブロック９８はプレーン１からの消去ブロックを持っていない。図９Ｂは、セクタが論理グループ９１，９２，９３にどのようにマッピングされるかをより詳しく示す。各論理グループ９１，９２，９３は、データのｎ個のセクタを含む。図９Ｂも、適応論理ブロック９５にマッピングされる論理グループ９１，９２，９３を示す。適応論理ブロックは、メモリアレイ内の対応するサイズの適応メタブロックにプログラムされる。
【００４６】
メタブロック構成の幾つかの例では、メタブロックのサイズは固定される。アレイ内のプレーンの数は、メタブロックのサイズを決定することができる。これらの例では、論理ブロックのサイズも固定され、セクタは所定の仕方で論理ブロックにマッピングされる。従って、論理アドレス空間は、固定された論理アドレス範囲と固定された境界位置とを有する等しいサイズの論理ブロックに分割される。対照的に、適応メタブロックを使用する構成では、適応論理ブロックは固定されたサイズを持たず、適応論理ブロックは所定範囲の論理アドレス空間に限定されない。代わりに、適応論理ブロックのサイズは個々別々であってよく、適応論理ブロックはいろいろな範囲の論理アドレス空間にわたって広がるように形成することができる。論理グループの形成は、それからいろいろなサイズの適応論理ブロックを形成可能な中間データ単位を提供することによって適応メタブロック構成を容易にする。このように、適応メタブロックは固定されたサイズを持たないメタブロックの例であり、適応論理ブロックは固定されたサイズを持たない論理ブロックの例である。
【００４７】
適応メタブロックを形成するために使われるプレーンは、アレイの消去ブロックの効率的な使用を提供するアルゴリズムに従って選択される。プレーン内の使用可能な消去ブロックの数と、特定のプレーンが前の操作から依然として使用中であるか否かということとに基づいてプレーンにいろいろな優先順位を与えることができる。また、そのプレーン内でコピー操作を実行することができるように、更新されているマテリアルのために使用されているのと同じプレーンを新しいマテリアルのために使用することを考慮する。プレーン内でのこのようなデータのコピー（オンチップコピー）は、或る構成ではより効率的である。一般に、選択されたプレーンの中での特定の消去ブロックの選択は重要ではない。
【００４８】
いろいろなサイズの適応メタブロックがあるということの１つの結果は、幾つかの適応メタブロックがアレイの全てのプレーンから１つずつの消去ブロックを含まないことがあるということである。このような適応メタブロックが個別にプログラムされるならば、プログラミングは可能な最大の並列性を用いない。例えば、図９Ａでは、プレーン１は、図に示されている操作の時にはプログラムされない。一般に、プログラミング速度を高めるために可能な最大の並列性でプログラムすることが望ましい。より少数のプレーンにプログラムすれば、効率が低下する結果となる。適応メタブロックが小さいが１つのアレイの中に多数のプレーンがあるときには、特にそうである。しかし、同時に２つ以上の適応メタブロックをプログラムすることによって、小さな適応メタブロックで高い並列性を維持することが可能である。
【００４９】
図１０は、並列にプログラムされる２つの適応メタブロック１０３０，１０４０を示す。メタブロック１０３０，１０４０内のデータは、ホストにより供給される更新されたデータ或いはフラッシュメモリ内で再配置されるデータである。図１０のメモリアレイ１００５は６個のプレーンを有する。適応論理ブロック１００１は３つの論理グループ１０１０〜１０１２を含む。従って、対応するメタブロック１０４０は、メモリアレイの３つのプレーンからの３つの消去ブロック１０４１，１０４２，１０４３を必要とする。適応論理ブロック１００１が単独でプログラムされるならば、３つのプレーンだけが使用され、他の３つはアイドル状態である。しかし、適応論理ブロック１００２が適応論理ブロック１００１と並列にプログラムされるので、６個のプレーンのうちの５個が使用される。このように、アレイ内のプレーンの個数より遥かに少ない消去ブロックを含む適応メタブロックでも高度の並列性を達成することができる。
【００５０】
アルゴリズムが種々の基準に従ってプレーンを割り当てるので、適応論理ブロック１００１はプレーン１，２および５の中の消去ブロックにプログラムされる一方、適応論理ブロック１００２はプレーン０および４の中の消去ブロックにプログラムされる。プレーン３の中のどの消去ブロックも、この操作ではプログラムされない。最大の並列性が望ましいけれども、全てのプログラミング操作において６個のプレーンの全てが一緒にプログラムされるとは限らない。プレーンの中に使用可能な消去ブロックがなければ、そのプレーンはプログラムされない。そのプレーンの中の使用可能な消去ブロックが非常に少なければ、プログラミングのためにプレーンが選択されるときに、そのプレーンには低い優先順位が割り当てられる。ここでは、適応論理ブロック１００１および１００２を格納するために消去ブロックが５個だけ必要とされる。従って、５つのプレーンだけが選択され、プレーン３は選択されない。プレーン３は、この操作では最低の優先順位を有するプレーンである。しかし、次のプログラミング操作が行われるときに、優先順位は再評価されうる。プレーン０，１，２，４，５の各々において１つ以上の消去ブロックが使用されているので、次の操作については優先順位は変化している可能性がある。従って、プレーン３の中に使用可能な消去ブロックがあるならば、プレーン３は後のプログラミング操作において使用される可能性がある。このアルゴリズムは、特定のプレーンがより速やかに満杯になり、かつ使用不可能になることのないように、いろいろなプレーン内の使用される消去ブロックの数を平均化させる。
【００５１】
個々の適応メタブロックのために使用されるプレーン同士は物理的に隣接していなくてもよい。例えば、図１０の適応メタブロック１０３０はプレーン０および４内に消去ブロック１０４４，１０４５を有する一方、適応メタブロック１０４０はプレーン１，２および５内に消去ブロック１０４１〜１０４３を有する。並列にプログラムされる複数の論理ブロックは、論理的に連続していなくてもよい。論理的に分離されている適応論理ブロック同士が並列にプログラムされる。例えば、適応論理ブロック１００１および１００２は論理的に連続していない。これらは適応論理ブロック１００３により分離されている。
【００５２】
１つの適応メタブロック内の全てのデータが、データの更新されたバージョンまたは再配置されたバージョンにより取って代わられて陳腐になると、その適応メタブロックを形成する消去ブロックは消去される必要がある。しかし、その適応メタブロックはアレイの全てのプレーンからの消去ブロックを含んでいないかもしれず、このようなメタブロックが個々に消去されるときには、消去は最大の並列性を使用しない。従って、データのプログラミングは普通に使用されるフラッシュメモリチップにおける消去操作の間に実行されないので、データを消去するために最大速度は達成されず、従ってメモリシステムの実効プログラミング速度は可能な最大速度から減じられる。これは、適応メタブロックを形成する消去ブロックの消去を、各プレーンからの１つの消去ブロックが使用可能になるまで遅らせて最大の消去並列性を達成することによって、克服することができる。消去のために使用可能な消去ブロックはリストにおいて保持され、可能な最大の並列性を達成するためにブロックのセットが消去のために定期的にスケジュールされる。そのリストが幾つかのプレーンの中のブロックを含まないときには、ブロックのより小さなセットの消去が実行される。
【００５３】
図１１は、適応メタブロックを使用する可能な幾つかのデータ記憶構成を示す。図１１は、入ってくるセクタ内のデータの論理グループへのマッピングと、論理グループの適応論理ブロックへのマッピングとを示す。このマッピングは単に論理的なものであるが、適応論理ブロックがメモリアレイの適応メタブロックにプログラム可能であることを理解されたい。通常、データは始めに、最大の並列性を用いて格納されるセクタのストリームとして受け取られる。従って、最初の書き込みの間、メモリシステムは図７に記載されているシステムのように動作することができる。図１１は、適応論理ブロック１１０１〜１１０３を示し、各適応論理ブロック１１０１〜１１０３は４つの論理グループを有する。従って、適応論理ブロック１１０１〜１１０３は、４つのプレーンを有するメモリアレイについての最大サイズの適応論理ブロックである。
【００５４】
後に、元の適応論理ブロックは、論理グループを再マッピングすることによって新しい適応論理ブロックに取って代わられる。例えば、図１１の第１の更新では、適応論理ブロック１１０１は、２つの適応論理ブロック１１１０および１１１１に取って代わられる。従って、単一の適応論理ブロックが２つのより小さな適応論理ブロックに取って代わられて、前は境界がなかったところに論理ブロック同士の間の境界が形成される。第１の更新中に適応論理ブロック１１１３が作られる。適応論理ブロック１１１３は、前は適応論理ブロック１１０３の一部であった論理ブロック１１２２と、前は適応論理ブロック１１０２の一部であった論理グループ１１２０，１１２１とを含む。従って、適応論理ブロック１１１３は、前は適応論理ブロック１１０２および１１０３の間の境界を含んでいた論理アドレス範囲にわたって広がる。適応論理ブロック同士が結合されてより大きな適応論理ブロックを形成してもよい。図１１の第２の更新では、論理グループ１１１１および１１１２が結合されて論理グループ１１１５を形成する。ここで、適応論理ブロック１１１５は、前は適応論理ブロック１１１１および１１１２により占められていた論理アドレス範囲にわたって広がっている。このように、適応論理ブロックは、適応論理グループのいろいろな組み合わせから形成することができる。適応論理ブロックのサイズは、１論理グループから最大数の論理グループまでの任意のサイズであってよい。論理グループの最大数は、アレイ内のプレーンの数である。適応論理ブロック構成の変化は、１つ以上の適応論理ブロック内のデータが更新されるときに生じ、或いは他の何らかの理由から生じる。例えば、適応論理ブロック構成は、ガーベッジコレクションの一部として或いはデータ記憶を最適化する予定ルーチン (a scheduled routine)として更新される。
【００５５】
アプリケーション
図１２Ａは、その後の更新がより効率的に実行されるように、プログラムされているデータを新しいデータで更新する操作を示す。しばしば、プログラムされている適応メタブロックより小さい新しいデータの一部が受け取られて、プログラムされているデータを更新するために使用される。図１２Ａは、２つの適応論理ブロック１２２０，１２３０の部分に対応する新しいデータ１２１０を示している。この新しいデータは、適応論理ブロック１２２０と適応論理ブロック１２３０との間の境界を覆って広がるアドレス範囲を有する。従って、適応論理ブロック１２２０および１２３０に対応する適応メタブロック１２２１，１２３１は更新を必要とする。
【００５６】
新しいデータ１２１０は、３つの連続する論理グループ１２４１，１２４２および１２４３のアドレス範囲の中にある１つの論理アドレス範囲にわたって広がる。論理グループ１２４１〜１２４３の各々は、更新されるべき少なくとも或る程度の部分を有する。図１２Ａは、置き換えられるべきデータと置き換えられるべきではないデータとの両方を有する論理グループ１２４１および１２４３を示している。論理グループ１２４２は、置き換えられるべきデータだけを有する。新しい論理グループ１２１１，１２１２および１２１３は、新しいデータ１２１０と、論理グループ１２４１および１２４３からの元のデータ１２１４および１２１５の部分とから形成される。新しい適応論理ブロック１２５０が論理グループ１２１１〜１２１３により形成される。適応論理ブロック１２５０に対応する適応メタブロック１２５１がメモリアレイにおいて３つの消去ブロック１２５２〜１２５４から形成される。適応論理ブロック１２５６および１２５７は、その中に新しいデータのない論理グループから形成される。例えば、適応論理ブロック１２５７は論理グループ１２４４〜１２４６から形成される。論理グループ１２４４〜１２４６は、メモリアレイ内の適応メタブロック１２３１からコピーされる。適応論理ブロック１２５７は適応メタブロック１２５９にプログラムされる。適応論理ブロック１２５６は適応メタブロック１２５８にプログラムされる。このように、３つの適応論理ブロック１２５０，１２５６および１２５７が、前は２つの適応論理ブロック１２２０，１２３０により占められていた論理アドレス範囲の中に形成される。３つの適応メタブロック１２５１，１２５８および１２５９が、このデータを記憶するメモリアレイ内に形成される。
【００５７】
図１２Ａは、第１の更新の後に行われる新しいデータの第２の更新を示す。新しいデータ１２６０は、新しいデータ１２１０の論理アドレス範囲と同じ論理アドレス範囲である論理アドレス範囲を有するセクタのストリームから成っている。この状況は、不揮発性メモリシステムでしばしば生じる。同じ範囲のデータが、記憶されるデータ（例えば、ＦＡＴのようなテーブル、ディレクトリおよびサブディレクトリ、アプリケーションファイル内のインデックス）の性質ゆえに、繰り返して更新されることになる。第２の更新は、適応論理ブロック１２５０内のデータを取り替えるだけである。従って、第２の更新では適応論理ブロック１２５０と対応する適応メタブロック１２５１とだけが更新される。適応論理ブロック１２５０は、３つの論理グループ１２１１〜１２１３だけを含む。適応論理ブロック１２５６および１２５７は更新を必要としない。新しいデータ１２６０は適応論理ブロック１２５０の論理アドレス範囲の全体にわたって広がっているわけではないので、論理グループ１２６１および１２６３を満たすために元のデータの部分１２１４，１２１５がコピーされる。論理グループ１２６１，１２６２および１２６３は、新しいデータ１２６０と元のデータ１２１４，１２１５とから形成される。適応論理ブロック１２７０が論理グループ１２６１〜１２６３から形成される。適応論理ブロック１２７０は、メモリアレイ内の適応メタブロック１２７１にプログラムされる。元のデータをコピーする操作は、第１の更新の場合より遥かに少ない。元のデータ１２１４および１２１５だけがコピーされ、適応論理ブロック１２５６および１２５７内のデータは第２の更新ではコピーされない。従って、更新されるデータの論理境界とより密接に一致する境界を有する適応論理ブロックを作ることによって、後の更新をより効率的にすることができる。
【００５８】
図１２Ｂは、再マッピングされる適応論理ブロックを示す。ここでは、データのストリームは２つのファイル１２８０および１２８２を含む。ファイル１２８０は境界１２８１によってファイル１２８２から分離されている。一般に、新しいデータがメモリシステムに書き込まれるときには、データのセクタのストリームとして受け取られる。このようなストリームの中にファイル境界がある。或る構成では、このような境界はデータが受け取られるときに識別され、それに応じて適応論理ブロックを構成することができる。他の構成では、ファイル境界の位置は、ホストにより更新される１つの範囲のデータによって表示することができる。図１２Ｂは、論理グループ１２８６の論理アドレス範囲内に位置するファイル境界１２８１を示す。初期プログラミング動作の間に、データは適応論理ブロック１２９０〜１２９３に形成される。論理ブロック１２９０〜１２９３は、各々、８個の論理グループ、すなわち使用されるメモリアレイについての最大サイズ、を含む。ファイル境界１２８１は、適応論理ブロック１２９２の中に位置する。適応メタブロック１２９２に格納されているファイル１２８０の論理グループが２個未満であっても、ファイル１２８０を更新するためにはメタブロック１２９０，１２９１および１２９２を更新する必要がある。適応論理ブロック１２９２の論理グループは新しい適応論理ブロック１２９４および１２９５に再マッピングされる。論理ブロック１２９４は論理グループ１２８５および１２８６だけから成る。従って、ファイル１２８０の一部を含む論理グループは適応論理ブロック１２９４を形成する一方、ファイル１２８０の部分を含まない論理グループは適応論理ブロック１２９５を形成する。ファイル１２８０を更新するために適応論理ブロック１２９５を更新する必要はない。従って、ファイル境界が存在すると分かっているところでは、ファイル境界に適合するように調整された境界を有する適応論理ブロックを形成することができる。
【００５９】
図１２Ｃは、データストリーム１２８０，１２８２からの代わりのデータの再マッピングを示す。ここでは、ファイル境界１２８１は論理グループ１２８６の中に存在する。論理グループ１２８６は、始めは論理ブロック１２９６に組み込まれる。ファイル１２８０を更新するためには、論理ブロック１２９６の半分より多くのデータがファイル１２８０からのデータではなくても、論理ブロック１２９６を更新する必要がある。更新中に、適応論理ブロックの第２のセットが形成される。適応論理ブロック１２９６は、新しい適応論理ブロック１２９７，１２９８，１２９９に取って代わられる。適応論理ブロック１２９８はちょうど１つの論理グループのデータを含む。境界１２８１が適応論理ブロック１２９８の中に存在するので、データストリーム１２８０或いはデータストリーム１２８２を更新するためには、適応論理ブロック１２９８を更新する必要がある。従って、ファイル１２８１が論理グループ同士の間の境界と整列していないので、旧データの或る程度のコピーが常に行われる。しかし、適応メタブロック１２９８は唯一の論理グループを含むので、メタブロック１２９６のようなより大きなメタブロックが使用される場合と比べて、コピーされるべきデータ量は少ない。このように、ファイル境界を含む適応論理ブロックのサイズを小さくすることによって、更新中のデータのコピー操作を減らすことができる。
【００６０】
図１３は、より少量の空きスペースを有するより小さな適応メタブロック１３４０に再書き込まれる、部分的に満たされている適応メタブロック１３２１を示す。データのストリームを受け取って、最大の並列性を用いてプログラム可能である。例えば、４つのプレーンを有するアレイにおいて、４つの論理グループを含む適応論理ブロックが形成されて、データが４つの消去ブロックを有するメタブロックまたは適応メタブロックに格納される。しかし、このようなデータのストリームの末端では、１つの適応メタブロックが部分的にのみ満たされる。このような適応メタブロックは、メモリアレイの、格納されるデータのために必要な部分よりも多い量を占める。図１３は、受け取られるデータのセクタのストリーム１３０５を示している。データは、論理グループ１３１０〜１３１５を含む論理グループにマッピングされる。論理グループ１３１０〜１３１７は、４つの論理グループを各々有する適応論理ブロック１３２０，１３２１に形成される。データのセクタのストリーム１３０５の末端は、論理グループ１３１５の論理アドレス範囲の中にある１つの論理アドレスに存在する。適応論理ブロック１３２１は、論理ブロック１３１４〜１３１７から形成される。論理グループ１３１４および１３１５は、データのセクタのストリーム１３０５からのデータを含む。論理グループ１３１６および１３１７はデータを含まない。このように、適応論理ブロック１３２１は、空の論理グループ１３１６および１３１７と、部分的に満たされた論理グループ１３１５とを含む。適応論理ブロック１３２１は適応メタブロック１３３１にプログラムされる。適応メタブロック１３３１は、メモリアレイの４つの消去ブロックを含む。空の論理グループ１３１６および１３１７と部分的に満たされた論理グループ１３１５とがあるので、適応メタブロック１３３１の幾つかの部分は使用されない。これは、メモリアレイ内のスペースを浪費する。図１３は、論理グループ１３１４および１３１５から形成された適応論理ブロック１３４０を示している。適応論理ブロック１３４０は、メモリアレイ内の適応メタブロック１３４１にプログラムされる。従って、適応メタブロック１３４１は、１３３１と同じデータを含むが、メモリアレイにおいて僅か半分のスペースを占めるだけである（４つの消去ブロックでなく、２つの消去ブロック）。適応論理ブロック１３４０と適応メタブロック１３４１とは、メモリアレイ内の適応メタブロック１３３１からデータをコピーすることによって形成される。適応メタブロック１３３１内のデータが適応メタブロック１３４１にコピーされるとき、適応メタブロック１３３１は陳腐とマークされる。その後、適応メタブロック１３３１は消去されてもよい。
【００６１】
部分的に満たされているメタブロックからより小さなメタブロックへのデータのコピーは、データのセクタのストリーム１３０５の受け取りからの時間の経過によりトリガされる。コピーする操作は、ガーベッジコレクション・ルーチンの一部として行われてもよい。データのセクタのストリーム１３０５がバッファ内にある間にデータのセクタのストリーム１３０５の末端が検出されたならば、１３４０のようなより小さな適応メタブロックは、受け取られたデータから直接形成される。この場合、データは始めにより大きな適応メタブロックに書き込まれてから後により小さなメタブロックにコピーされるのではない。従って、消去すべき陳腐な適応メタブロックはない。或る構成では、ホストは、データのストリームの末端がどこにあるかを示す信号を送ることができる。そのとき、データのストリームからのセクタを含む論理グループだけを含む適応論理ブロックを形成することができる。
【００６２】
特定のメモリ構成では、更新されたデータを格納するために消去ブロックまたはメタブロックを割り当てることができる。このような消去ブロックおよびメタブロックの例が、２００３年１２月３０日に出願されたコンリーらの“大きな消去ブロックを有する不揮発性メモリシステムの管理”という米国特許出願第１０／７４９，８３１号（特許文献２２）に記載され、その全体が本願明細書において参照により援用されている。メモリアレイのプレーンのための更新されたデータを格納するために、Ｅ１およびＥ２と称される特定のメタブロックが使用される。特定の消去ブロックまたはメタブロックのための更新されたデータを受け取るように、ｄＥ１と称される他の消去ブロックまたはメタブロックが割り当てられる。適応メタブロックは、Ｅ１，Ｅ２，或いはｄＥ１と称されてよい。このような適応メタブロックは、頻繁に更新される論理アドレス範囲に合うように調整される。更新されたデータに適するように選択されたサイズを有する適応メタブロックを形成することによって、元のデータのコピー操作を減らすことができる。Ｅ１とｄＥ１とは、更新データを受け取って、それらを非順次的な仕方で格納する。更新データを非順次的に記憶する更新ブロック（またはメタブロック、または適応メタブロック）は、カオス的ブロックと見なされる。
【００６３】
図１４は、更新されたデータの論理アドレス範囲に適合させられているサイズを有するカオス的ブロックとしての適応メタブロックの使用を示す。データは、元の適応メタブロック１４１０を含む元の適応メタブロックに格納される。通常、このような元の適応メタブロックは最大サイズの適応メタブロックである。元の適応メタブロック１４１０の中のデータに対応する更新されたデータを受け取るように適応メタブロック１４２０が割り当てられる。適応論理ブロック１４１１および１４２１は、元の適応メタブロック１４１０および適応メタブロック１４２０に各々対応する。適応論理ブロック１４２１は、適応論理ブロック１４１１と同じ論理アドレス範囲を有する。第１の更新データ１４１５は、適応論理ブロック１４１１の論理アドレス範囲の中の論理アドレス範囲を有する。元の適応論理ブロック１４１１の論理アドレス範囲の一部だけが第１の更新で更新される。第１の更新データ１４１５は非順次的（カオス的）である。従って、適応メタブロック１４２０はカオス的ブロックとなる。更新データ１４１５は、図に示されている論理アドレス範囲内のセクタの数個のストリームを含むことができる。同じセクタが数回更新されてもよい。結局、メタブロック１４２０は満杯になり、統合されなければならない。
【００６４】
第１の統合の間、各セクタの最新のコピーだけが新しい適応メタブロック１４２２〜１４２４にコピーされる。更新されたデータに関しては、最新のコピーが適応メタブロック１４２０から生じ、更新されないデータに関しては最新のコピーが適応メタブロック１４１０から生じる。統合は、適応メタブロック１４１０および適応メタブロック１４２０からのデータを論理的順序で結合させる。適応メタブロック１４２３に割り当てられる論理アドレス範囲は、第１の更新データ１４１５の論理アドレス範囲を含む。適応メタブロック１４２２，１４２４は、更新されなかったデータだけを含む。
【００６５】
第１の統合の後に第２の更新データ１４２５が受け取られる。第２の更新データ１４２５は、第１の更新データ１４１５と同じ論理アドレス範囲の中にある。第２の更新データ１４２５は、適応メタブロック１４３０に格納される新しい適応論理ブロック１４３１に割り当てられる。適応論理ブロック１４３１は、適応メタブロック１４２３に格納されているデータと同じ論理アドレス範囲を有する。適応メタブロック１４３０は、カオス的に更新され、従ってカオス的ブロックとなることができる。適応メタブロック１４３０が満たされたとき、適応メタブロック１４３０および適応メタブロック１４２３の中のデータが適応メタブロック１４４０に統合される。そのとき、適応メタブロック１４４０は適応メタブロック１４２３に取って代わり、適応メタブロック１４２３は陳腐とマークされることになる。適応メタブロック１４２２および１４２４は変更されないままである。第２の統合では第１の統合の場合より小さい論理アドレス範囲が統合されるので、変更されないデータをコピーする操作は少ない。また、第１の統合後は、更新のために使用される適応メタブロックはより小さいので、メモリアレイにおいて必要とされるスペースはより少ない。さらなる更新が同じ論理アドレス範囲の中で行われ、第２の統合の場合のように統合されることになる。
【００６６】
メディア管理
図１５Ａは、適応論理ブロック１５２０の論理グループ１５１０，１５１１および１５１２が適応メタブロック１５４０の消去ブロック１５３１，１５３２および１５３３にどのようにマッピングされるかを示す。適応論理ブロック１５２０の中の論理グループの数は適応メタブロック１５４０内の消去ブロックの数に等しいけれども、この例では個々の論理ブロックは個々の消去ブロックに直接マッピングされない。代わりに、各論理グループ１５１０〜１５１２の一部分が適応メタブロック１５４０の各消去ブロック１５３１〜１５３３に格納されるようにデータが格納される。
【００６７】
図１５Ｂは、適応論理ブロック１５２０のメモリアレイへのマッピングをより詳しく示す。図１５Ｂは、論理グループ１５１０からのセクタがメモリアレイにおいてどのようにプログラムされるかを示している。論理グループ１５１０はｎ個のセクタのデータを含む。メモリアレイのプレーン０〜４は、各々４セクタの幅を有する。或るメモリ構成では、アレイの１つのプレーンにわたって広がる４つのセクタは、並列にプログラムされる。従って、４個のセクタが１つのページを形成し、これはアレイのプログラミングの最小単位である。セクタは通常順次到着し、アレイへの書き込み前にレジスタに格納することができる。適応メタブロックの全ての消去ブロックの中のセクタを並列にプログラムすることができる。例えば、セクタ０〜１１は並列にプログラムされる。その後、セクタ１２〜２３を並列にプログラムすることができる。これは、論理グループ１５１０の中の全てのセクタがプログラムされるまで続行される。次に、論理グループ１５１１，１５１２が順番にプログラムされる。
【００６８】
図１５Ｃは、１つのメモリアレイにおいて３つの消去ブロックにより形成される適応メタブロックを示す。メモリの中でのセクタの配置は図１５Ｂに示されているものと同様であり、数ｎは３２に等しい。しかし、３２は３で平等に割り切れないので、１つの論理グループ内のセクタは消去ブロック１５５１〜１５５３に平等に分配されない。第１の論理グループはセクタ０〜３１から成る。これらのセクタは、消去ブロック１５５１に１２セクタ、消去ブロック１５５２に１２セクタ、消去ブロック１５５３に８セクタ、分配される。第２の論理グループの第１のセクタ０’は消去ブロック１５５３にプログラムされる。このように、複数の論理グループは別様にプログラムされ、別々の消去ブロックから始まることができる。別々の論理グループからのセクタを並列にプログラムすることができる。例えば、第１の論理グループからのセクタ２４〜３１と第２の論理グループからのセクタ０’〜３’は並列にプログラムされる。
【００６９】
図１５Ｄは、並列にプログラムされる２つのメタブロックを示す。消去ブロック１５６１および１５６２は適応メタブロック１５６５を形成し、消去ブロック１５６３および１５６４は適応メタブロック１５６６を形成する。適応メタブロック１５６５および１５６６は、各々２つの消去ブロックから成り、従って各適応メタブロック１５６５および１５６６はデータの２つの論理グループを含む。適応メタブロック１５６５は論理グループ１５７１および１５７２を含む。適応メタブロック１５６６は論理グループ１５７３および１５７４を含む。論理グループ１５７１および１５７３のセクタのプログラミングが示されている。論理グループ１５７１および１５７３は並列にプログラムされる。メモリアレイへの第１の書き込みの間に、論理グループ１５７１からのセクタ１〜８は論理グループ１５７３からのセクタ１’〜８’と同時にプログラムされる。その後、セクタ９〜１６がセクタ９’〜１６’と同時にプログラムされる。これは、論理グループ１５７１および１５７３内の全てのセクタがプログラムされるまで続く。その後、論理グループ１５７２および１５７４が同様にプログラムされる。
【００７０】
図１５Ｅは、並列にプログラムされる３つの適応メタブロックを示す。メタブロック１５９０は４つの消去ブロックを含み、メタブロック１５９１は１つの消去ブロックを含み、メタブロック１５９２は３つの消去ブロックを含む。メタブロック１５９０〜１５９２は並列にプログラムされる。メタブロック１５９０〜１５９２は異なる数の消去ブロックを含むので、メタブロック１５９０〜１５９２の各々においてデータは別様に整列させられる。図１５Ｅは、メタブロック１５９０〜１５９２の中でのページの整列を示す。１つのページは、単一のセクタ、４つのセクタ、またはプログラミングの単位としてプログラムされる他の何らかの数のセクタである。図１５Ｅにおいて同じ水平レベルにある別々の消去ブロックに存するデータのページは並列にプログラムされる。例えば、メタブロック１５９０のページ１２〜１５と、メタブロック１５９１のページ３と、メタブロック１５９２のページ９〜１１とは並列にプログラムされる。
【００７１】
図１５Ｆは、データ更新の１つの例を示し、この場合、更新されたデータの第１のセクタは１つの論理グループ内の第１のセクタではない。更新されたデータ１５８２内の第１のセクタは論理アドレス１３を有する。論理グループ１５８０は、論理アドレス１〜１６を有するセクタから構成されている。更新されたデータ１５８２は、少なくとも２つの論理グループからのセクタを含み、２消去ブロックの適応メタブロックサイズは、更新されたデータ１５８２を含む始めの２つの論理グループを格納するように選択される。消去ブロック１５８５および１５８６は、更新されたデータ１５８２を含む始めの２つの論理グループを格納するように選択される。論理アドレス１３を有する、更新されたデータ１５８２の第１のセクタは、消去ブロック１５８５内の第１の位置に書き込まれる。論理アドレス１４を有するセクタは第２の位置に書き込まれ、以降、論理グループ内の最後のセクタ、すなわち論理アドレス１６を有するセクタが書き込まれるまで、同様である。論理グループ１５８０からの更新されないデータはその後にメモリアレイにコピーされる。従って、論理グループの第１のセクタと、適応メタブロックに格納された第１のセクタとの間にはオフセットがある。次の論理グループの第１のセクタは通常の仕方で書き込まれるので、１つの適応メタブロックの中で別々の論理グループが別々のオフセットで書かれてもよい。論理アドレス１’を有するセクタは、論理グループ１５８１を更新するときに最初に書き込まれるセクタである。
【００７２】
図１６は、論理グループに応じたメモリアレイ内のデータの位置を記録するために使われるテーブルを示し、ここで適応論理ブロック１６１０が適応メタブロック１６２０に格納される。列１は個々の論理グループの各々のアイデンティティを示す。これは論理グループを一意的に明示する論理アドレスである。論理グループは一般に順次に列挙される。列２は、論理グループが格納される適応メタブロックのサイズを示す。サイズは、単に、適応メタブロック内の消去ブロックの個数である。ここでは、メタブロックは３つの消去ブロックから成るので、サイズは全ての論理ブロックについて３である。列３は、適応論理ブロック内の論理グループのグループ番号Ｎを与える。論理グループは、論理アドレス範囲に従って順次に番号を付される。従って、論理グループＬ１はＮ＝１を有し、Ｌ２はＮ＝２を有し、Ｌ３はＮ＝３を有する。列４は、Ｎ番目の消去ブロックの適応メタブロック内での位置を与える。これは、消去ブロックの物理的ブロック番号 (physical block number)（ＰＢＮ）であってよい。適応論理ブロック内の論理グループの数は適応メタブロック内の消去ブロックの数に等しいので、１つの適応メタブロックの消去ブロックの位置の完全な記録は、各論理グループについて１つの消去ブロック位置を記録することによって形成される。
【００７３】
特定の論理グループの位置のテーブルは、メモリシステムのメディア管理の一部分として揮発性または不揮発性のメモリにおいて維持される。メディア管理システムは、使用可能な消去ブロックの位置と、データの論理から物理へのマッピングとを記録した種々のテーブルを持つことができる。メディアマネージャは、メディア管理システムのテーブルを管理する。通常、メディアマネージャは、コントローラ内のファームウェアとして実現される。
【００７４】
図１７は、メディアマネージャの例を示す。図１７に示されているものに類似したメディアマネージャの動作が、２００３年１２月３０日に出願されたベネットらの“不揮発性メモリおよびブロック管理システムを伴う方法”という米国特許出願第１０／７５０，１５５号（特許文献２３）に記載され、この出願は、その全体が本願明細書において参照により援用されている。メディアマネージャは、適応メタブロックマネージャ、ブロック割り当てマネージャおよびアドレステーブルマネージャを含む。これら３つのマネージャと、これらに関連するテーブルとは、適応メタブロックの管理に特別に関連するものであるので、以下でさらに説明する。
【００７５】
適応メタブロックマネージャは、組み合わせて適応論理ブロックを形成させる論理グループの数、従って適応メタブロック内の消去ブロックの数を、決定する。データがホストから受け取られる場合、この決定は数個のファクタに基づくことができる。ホストからのコマンドシーケンスが評価され、現在のコマンドに基づいて或いはホストコマンドの過去の評価に基づいて適応メタブロックのサイズを決定することができる。評価可能な現在のコマンドの特性は、論理アドレス、コマンドセクタカウント、（ＤＯＳクラスタのような）ファイルシステムクラスタとの整列、前のコマンドとの論理的関係、およびファイルシステムセクタに関してのアドレスを含む。非順次タイプの更新ブロックにより管理される範囲のアドレスに関してのアドレスも考慮される。過去の操作の特性は、順次データのストリームについてのホストコマンドシーケンス、完全なファイルについてのホストコマンド構造、頻繁に更新された論理アドレス範囲の記録、および最近書き込まれた順次データの最終アドレスを含むことができる。適応メタブロックマネージャは、情報へのアクセスを得るために適切なホストインターフェイスプロトコルのもとでホストとの対話を確立することができ、それは適切なメタブロックサイズを決定することを可能にする。
【００７６】
データが再配置される場合、適応メタブロックのサイズは、再配置されるデータを含む論理グループの数に基づくことができる。制御データが適応メタブロックに格納される場合、適応メタブロックのサイズは、格納されるべきデータのタイプに応じて固定することができる。大きな適応メタブロックで得られる大きな並列性とより小さな適応メタブロックで得られる減少したガーベッジコレクションとを均衡させることに基づいて適応メタブロックのサイズを決定することができる。必要な消去ブロックの数が適応メタブロックマネージャにより判定されると、その数の消去ブロックを求めるリクエストがブロック割り当てマネージャに送られる。
【００７７】
ブロック割り当てマネージャは、メモリアレイの別々のプレーンから消去ブロックを選択する。プレーンは、プレーン内の使用可能な消去ブロックの数に基づいて選択することができる。種々のサイズの適応メタブロックが使用される場合、プレーンはいろいろなレベルまで満たされる。従って、或るプレーンは満杯になり得るが、その他のプレーンは依然として使用可能な消去ブロックを有する。これが生じたならば、アレイの１つのプレーンが使用不可能となり、それに応じて並列性が限定されることになる。これが生じるのを防止或いは延期するために、ブロック割り当てマネージャは、適応メタブロックを形成する消去ブロックを割り当てるとき、小数の使用可能な消去ブロックを含むプレーンに低い優先順位を与え、多数の使用可能な消去ブロックを含むプレーンに高い優先順位を与える。前の操作から依然としてビジーであるプレーンにも低い優先順位が与えられることになる。データを１プレーンから別のプレーンへ再配置するより効率良く１つのプレーン内で再配置可能な場合、再配置されるデータを有するプレーンに高い優先順位が与えられることになる。ブロック割り当てマネージャは、割り当てブロックリスト（ＡＢＬ）から使用可能な消去ブロックを選択する。
【００７８】
図１８Ａは、適応メタブロックに使用される消去済みブロック管理階層を示す。特定のサイズのメタブロックを割り当てるべき旨の適応メタブロックマネージャからのリクエストを受け取ると、ブロック割り当てマネージャは、別々のプレーンから消去ブロックを選択し、ブロックを連結して１つのメタブロックにするように関連する制御構造を更新する。それからの消去済みブロックが使われるプレーンは、所定の基準に従うアルゴリズムにより選択される。より少ない消去済みブロックを含むプレーンに低い優先順位が与えられる。前の操作から依然としてビジーなプレーンは低い優先順位を与えられる。そのプレーンを選択すればデータを他のプレーンからコピーする代わりにそのプレーンの中でコピーすることができるようになるようなプレーンには高い優先順位を与えることができる。或る構成では、このようなプレーン内コピーはより効率的である。
【００７９】
消去済みブロックは、アレイの各プレーンについて別々に管理される。１つのプレーンが選択されたとき、適応メタブロックの部分を形成するためにそのプレーンから任意の消去ブロックが選択されてもよい。通常、消去ブロックはリストの頂上から選択される一方、新たに使用可能になった消去ブロックはリストの底部に加えられる。消去ブロックは、図１８Ａに示されているように複数のリストの階層により管理される。個々の消去ブロックは、一度に１つのリストにのみ現れる。不良なブロックはどのリストにも現れず、従ってデータ記憶のために使用されない。複数のリスト間で消去済みブロックアドレスを動かすことにより、書き込み／サイクルカウントをメモリアレイ全体に分布させることができる。これは、個々の消去ブロックのエラーの危険を減少させる損耗レベリングを提供する。
【００８０】
割り当てブロックリスト（ＡＢＬ）１８１０は、消去済みブロックアドレスの短いリストであり、これからメタブロックを形成するべく消去済みブロックが選択される。従って、ＡＢＬ１８１０はリストの階層の頂上にある。ＡＢＬ１８１０内で、メモリアレイの各プレーンについて別々のフィールドが維持される。通常、ＡＢＬ１８１０は、コントローラＲＡＭのような不揮発性メモリにおいて維持される。しかし、コピーも不揮発性メモリにおいて維持される。
【００８１】
１つの適応メタブロックが形成されるごとにＡＢＬ１８１０のコピーがログ１８１３に書き込まれ、それを形成するために使用された消去済みブロックはＡＢＬ１８１０から除去される。このように、ログ１８１３に存するＡＢＬ１８１０のコピーは定期的に更新される。消去操作を通して消去済みブロックが使用可能になると、それはＡＢＬ１８１０内の、消去ブロックを含むプレーンに対応するフィールドに加えられる。ＡＢＬ１８１０は、電源喪失後に、ログ１８１３からコピーすることによって、回復可能である。しかし、ログ１８１３への前のコピーの後に消去済みブロックがＡＢＬ１８１０に加えられているために、ログのコピーは最新ではないかもしれない。このような消去済みブロックは、他のデータ構造から容易に特定される。特に、ログ１８１３は割り当て済みメタブロックの記録を含んでいる。割り当て済みメタブロックは、その中のデータがホストにより現在更新されているメタブロック或いは適応メタブロックである。従って、電源が始めに投入されたとき、元のメタブロックの消去ブロックが消去されているか否かを判定するために元のメタブロックの各消去ブロックの第１のセクタが走査されることになる。消去ブロックが消去されていれば、そのアドレスがＡＢＬに加えられる。アドレスデータは、メタブロックサイズ、グループ番号およびブロックアドレスについてのエントリを有する図１６に示されているフォーマットで連結された始動論理グループアドレスとしてログ１８１３において維持される。従って、ＡＢＬ１８１０の完全なコピーが電源喪失後に容易に再建可能である。ログは、消去のために使用可能な完全に陳腐なデータを有する消去ブロックのリストも含むことができる。
【００８２】
ＡＢＬ１８１０は、所定数のブロックアドレスを消去済みブロックリスト（ＥＢＬ）１８１１から移動させることによって初期化されることになる。ＡＢＬの各フィールドは、対応するＥＢＬフィールドからアドレスを移動させることによって初期化されることになる。例えば、ＡＢＬフィールドは、その容量の半分まで満たされる。メタブロックへの割り当てのために１つのブロックが必要とされるときには、関連するＡＢＬフィールド内の第１のブロックが使用され、そのアドレスがＡＢＬから除去される。ガーベッジコレクションの間に１つのブロックが消去されるとき、それは関連するＡＢＬフィールドの末端に加えられる。
【００８３】
ＡＢＬ１８１０は、ＥＢＬ１８１１からの消去済みブロックアドレスで再充填されることになる。これは、ＡＢＬ１８１０が空の場合に必要になる。消去済みブロックアドレスは、ＡＢＬ１８１０の１つのフィールドが満杯または空であるときに、ＡＢＬ１８１０とＥＢＬ１８１１との間で交換することができる。交換は、１フィールド（或いは、アレイのプレーン）のみについて或いは全てのフィールドについて行われる。交換は、ＡＢＬ１８１０を上まで一杯に満たすことを含み、或いはＡＢＬ１８１０内の全てのエントリの完全な交換を含むことができる。交換は、１つのフィールドが満杯または空になったことによりトリガされ、または他のイベントによりトリガされ、或いは定期的に行われる。
【００８４】
ＥＢＬ１８１１は、一般に、不揮発性メモリにおいて保持されるセクタに維持される。アレイの各プレーンについて別々のフィールドを有する消去済みブロックのリストを含む。ＡＢＬ１８１０と同じフォーマットであり、従ってＥＢＬ１８１１とＡＢＬ１８１０との間でエントリを容易に交換することができる。ＥＢＬ１８１１は、不揮発性メモリにおいて単一のセクタとして維持されるので、速やかにアクセスされ更新され、従ってＥＢＬ１８１１とＡＢＬ１８１０との間での交換を容易にする。ＥＢＬとＡＢＬとの間でのアドレスの交換は、ＡＢＬが満杯或いは空であるときに行われる。或いは、メモリアレイ内の特定の位置を激しく使用することを避けるために交換をもっと頻繁に行ってもよい。ＥＢＬ１８１１内のアドレスをＡＢＬ１８１０と、プレーンブロックリストと交換することもできる。
【００８５】
ＥＢＬセクタだけを含むＥＢＬブロックにおいてＥＢＬセクタが維持される。図１８Ｂは、複数のＥＢＬセクタを有するＥＢＬブロック１８０１を示す。ＥＢＬデータが変更されるとき、新しいＥＢＬセクタが書き込まれ、旧ＥＢＬセクタは陳腐になる。従って、陳腐なセクタ１８０３は、もはや有効ではないＥＢＬの前のコピーを含む。最後に書き込まれたＥＢＬセクタ１８０２だけが有効である。１つのＥＢＬセクタが各ＥＢＬフィールドに列挙されている消去ブロックのカウントを含むこともできる。これらのカウントは、適応メタブロックを形成するときのプレーンを選択する際に１つのファクタとして使用される。これらのカウントのコピーもログ１８１３において維持される。
【００８６】
ＰＢＬ１８１２のような１つのプレーンブロックリスト（ＰＢＬ）がアレイの各プレーンについての不揮発性メモリにおいて維持される。ＰＢＬ１８１２は、メモリアレイの特定のプレーン内の消去ブロックのリストである。ＡＢＬ１８１０またはＥＢＬ１８１１に列挙されている消去ブロックはＰＢＬ１８１２に列挙されない。ＰＢＬ１８１２は１つのセクタを占めることができるが、セクタは満杯でなくてもよい。通常、ＰＢＬは１つまたは複数のＰＢＬブロックにグループ分けされる。ＰＢＬブロックは、ＰＢＬセクタだけを含む専用ブロックである。１つのＰＢＬセクタ内の情報が変更されるときには、更新されたバージョンがＰＢＬブロック内の次の位置に書き込まれる。旧セクタは陳腐とマークされる。１つの特定のプレーンについて唯一の有効なＰＢＬセクタが特定のＰＢＬブロックの中に存在する。しかし、ＰＢＬセクタが別々のＰＢＬブロック内にあるならば、１つの特定のプレーンについて２つ以上の有効なＰＢＬセクタが存在することになる。ＰＢＬセクタは、２つのフィールド、消去ブロックの位置を定義するエントリのセットと、ＰＢＬブロック内の全ての有効なＰＢＬセクタの位置を列挙するセクタインデックスとを有する。消去ブロックの位置を定義するエントリは、必ずしも特定の順序でなくてもよい。エントリの順序は、対応するＥＢＬフィールドとの交換の結果である。最後に書き込まれたＰＢＬセクタのインデックスだけが有効である。部分的に書き込まれたメモリには、多数の消去済みブロックと、従って多数のＰＢＬブロックを必要とする多数のＰＢＬセクタとがある。しかし、メモリが満たされてゆくとき、消去済みブロックの数は減少し、必要なＰＢＬブロックの数も減少する。論理的に満杯のメモリシステムには、ＰＢＬブロックはないかもしれない。ＰＢＬ１８１２とＥＢＬとの間でのアドレスの交換は、ＥＢＬとＡＢＬとの間でのアドレスの交換と同様である。交換は、一方向性または双方向性である。複数のＰＢＬブロックが使用される場合、１つのＰＢＬブロックが交換のために使用されるアクティブなブロックである。アクティブなＰＢＬブロックは定期的に変更される。ＥＢＬ１８１１内のフィールドは、バックグラウンド操作として単一のＰＢＬセクタから更新される。
【００８７】
図１８Ｃは、適応メタブロックを使用するメモリシステムにおけるアドレス変換情報についてのアドレステーブル管理階層を示す。データセクタがデータ更新アルゴリズムに従ってメモリアレイに書き込まれるとき、アドレステーブルマネージャは、論理から物理へのマッピングの不揮発性記録を作り、かつメモリアレイ内の任意のセクタの高速変換を可能にするために、アドレステーブル管理階層における関連する制御データ構造を更新する。高速変換は、不揮発性メモリから単一のセクタを読み出すことによって任意のセクタの物理的位置を決定するようにすることによって達成される。不揮発性メモリにおいて物理的位置がまだ更新されていない場合、それを揮発性ＲＡＭから速やかに決定することができる。適応メタブロックのサイズおよび構成は可変であるので、メタブロック内のこのような消去可能なブロックの位置を回復することは、それらが不揮発性メモリに格納されていなければ、困難である。従って、メタブロックの消去ブロックの位置は、不揮発性メモリに格納される。
【００８８】
図１８Ｃの階層の頂上には書き込みセクタリスト（ＷＳＬ）１８１４がある。ＷＳＬ１８１４は、一般に、コントローラＲＡＭのような揮発性メモリにおいて維持される。ＷＳＬ１８１４は、ホストにより順次書き込みストリームと関連付けられたか、または不揮発性メモリ内の他の位置から再配置されたセクタを特定する。各ホスト書き込みストリームについて別々のＷＳＬが存在する。ホストからの新しい書き込みストリームのためにメタブロックが割り当てられるときに、１つのＷＳＬが開かれる。ＷＳＬは、開始位置と書き込まれたセクタの数などの短縮された形を持つことになる。
【００８９】
ログ１８１３はＷＳＬ１８１４の下にある。ログ１８１３は、ＷＳＬ１８１４に列挙されているセクタの格納のために割り当てられた適応メタブロックの累積リストを記憶する。ログ１８１３は、それが更新されるときの全てのＷＳＬのコピーも含む。ログ１８１３は、メタブロックが割り当てられるごとに更新される。ログ１８１３は、ログブロックの中のログセクタに含まれる。ログ１８１３内の情報が変更されるとき、新しいログセクタがログブロック内の次の使用可能な位置に書き込まれる。前のログセクタは陳腐になり、最後に書き込まれたログセクタだけが有効である。ログ１８１３の下には一時的グループアドレステーブル（ＴＧＡＴ）１８１５とグループアドレステーブル（ＧＡＴ）１８１６とがある。ＧＡＴ１８１６は、論理グループアドレス順に順次に配置されている全ての論理グループについての物理アドレスを含む不揮発性メモリ内のセクタに格納されるアドレステーブルである。従って、ＧＡＴ内のｎ番目のエントリは、論理グループアドレスｎを有する論理グループに関連する。ＧＡＴ１８１６に格納されているアドレスデータは、メタブロックサイズ、グループ番号およびブロックアドレスについてのエントリを有する図１６に示されているフォーマットである。
【００９０】
ＧＡＴセクタは、論理グループの１つの論理的に連続するセットについてのエントリを有する１つの専用ＧＡＴブロックに格納される。ＧＡＴブロックは２つの区画、すなわちＧＡＴ区画およびＴＧＡＴ区画に分割される。ＧＡＴ区画は、ＧＡＴブロックの論理アドレス範囲内の各論理グループについての１つの元のエントリを含む。ＴＧＡＴ区画は、ＧＡＴセクタと同じフォーマットを有するセクタを含む。ＴＧＡＴセクタは、ＧＡＴを更新する前にアドレスデータを更新するために使用される。定期的に、１つのブロック内のＧＡＴ区画は、ＴＧＡＴ区画内のセクタに記録された更新を組み込むように書き換えられる。ＴＧＡＴセクタは、アドレス情報を更新するためにＧＡＴ内の対応するセクタに一時的に取って代わる。ＴＧＡＴセクタは、有効なＴＧＡＴセクタのインデックスを含む。このインデックスは最後に書き込まれたＴＧＡＴセクタ内でのみ有効である。このようなインデックスはＧＡＴのためには不要である。ＴＧＡＴセクタは、ＷＳＬと関連付けられたログからのアドレス情報でＧＡＴセクタを更新する。その後、ＷＳＬおよびログエントリは削除される。
【００９１】
特定の論理アドレスを有するデータのセクタの物理的セクタアドレスは、リスト１８１４〜１８１６から決定される。そのセクタが最近書き込まれたか否かを判定するために始めにＷＳＬが読み出される。そうであるならば、物理的セクタアドレスはＷＳＬ内のセクタの位置に対応するメタブロックアドレスから見出される。セクタがＷＳＬ内に見出されなければ、セクタがＴＧＡＴエントリを有するか否かを判定するためにＴＧＡＴセクタ内のインデックスが読み出される。そうであるならば、物理的セクタアドレスは、適切なＴＧＡＴセクタを読み出すことによって判定される。セクタがＷＳＬにもＴＧＡＴにも列挙されていなければ、その物理的位置を判定するために適切なＧＡＴセクタが読み出される。データが順次アドレス順に書き込まれ或いは読み出されるときに、アドレス変換時間を短縮するためにコントローラＳＲＡＭ内のログ、ＴＧＡＴおよびＧＡＴエントリのルックアヘッド・キャッシングを実行することができる。
【００９２】
図１８Ｄは、消去済みブロックおよびアドレス変換を管理するために使用されるデータ構造を示す。既に記載されたリストの他に、ブロックアドレス１８２１およびブートブロック１８２０が示されている。ブロックアドレス１８２１は、制御データ構造を記憶する全ての消去ブロックの物理アドレスの一覧表を形成する。専用ブロックアドレス（ＢＡ）ブロックを、ブロックアドレス１８２１を含むＢＡセクタを格納するために使用することができる。制御ブロックの位置が変更されるとき、新しいＢＡセクタが書き込まれる。前のＢＡセクタは陳腐とマークされる。従って、最後に書き込まれたＢＡセクタだけが有効である。
【００９３】
ブートブロック１８２０は、ブートセクタを含む専用ブロックである。ブートセクタ内の情報が変更されると、新しいブートセクタが書き込まれる。最後に書き込まれたブートセクタだけが有効である。ブートブロック１８２０は、固定された物理的位置を有し、システム初期化時に走査することによって特定される。ブートブロックの位置は、１つの正確な位置に固定されるのではなくて１つの範囲の中に固定されるので、走査する必要があるかもしれない。これは、不良な消去ブロックの可能性を考慮に入れるためである。走査を速やかに完了するようにブートブロックの位置は狭い範囲の中に固定されることになる。ブートセクタは、ブロックアドレス１８２１の位置と、必要とされる他の任意のシステム構成情報とを含む。従って、初期化時に、図１８Ｄのデータ構造は速やかに再建されることになる。ブートブロック１８２０は、固定された位置を有し、ブロックアドレス１８２１の位置を示し、ブロックアドレス１８２１の位置は図に示されているデータ構造の位置を示している。
【００９４】
前に説明されている或るデータ構造は、ＥＢＬブロック、ＰＢＬブロックおよびＧＡＴブロックのような専用ブロックを使用する。このような専用ブロックは、メモリアレイの単一の消去ブロックであり、或いは複数の消去ブロックを含む適応メタブロックである。適応メタブロックを使用することの１つの利点は、使用される適応メタブロックのサイズを保持されるべきデータの量に合わせて調整することである。例えば、メモリが多数の消去ブロックを有する場合、多数のＰＢＬセクタがあるので、おそらく大きなＰＢＬブロックが適している。メモリアレイがデータで満杯であるときには、消去済みブロックの数は少なく、従ってＰＢＬセクタの数は少ないので、おそらくより小さなＰＢＬブロックが適している。
【００９５】
最大サイズに満たないサイズの適応メタブロックが制御データのために使用される場合には、制御データは他のデータと並列にプログラムされてもよい。データがホストからメモリアレイへプログラムされるべく送られる場合、このような並列プログラミングは、制御データをホストデータのプログラミングと同時に更新することを可能にすることになる。従って、制御データが更新されている間にホストデータのプログラミングに対する妨害はないけれども、ホストデータのプログラミングのために使用可能な並列性が低下するためにプログラミング速度が低下する可能性がある。従って、図１５Ｄ、１５Ｅおよび１５Ｆに示されている並列プログラミングの例は、制御データ、コピーされるデータおよびホストデータの組み合わせの並列プログラミングに適用される。これは、制御データがプログラムされ終わるまでホストデータのプログラミングが遅らせられる他のメモリシステムに見られる待ち時間を避けることができる。
【００９６】
不揮発性ＲＡＭ
或る不揮発性メモリ構造は、データにランダムにアクセスすることを可能にする。これは、データが１ページの最小単位で書き込まれ、１消去ブロックの最小単位で消去されるフラッシュメモリとは対照的である。不揮発性ランダムアクセスメモリ（ＮＶＲＡＭ）の例は、磁気抵抗ＲＡＭ（ＭＲＡＭ）、強誘電性ＲＡＭ（ＦｅＲＡＭ）、および位相変化メモリ（オボニックス・ユニファイド・メモリ (Ovonics Unified Memory) 或いはＯＵＶ）としても知られている）を含む。ＮＶＲＡＭは、フラッシュメモリも使用するメモリシステムの一部として使用されてもよい。ＮＶＲＡＭは、別個のチップ上に配置されてもよいし、或いはコントローラチップまたはフラッシュメモリチップに組み込まれてもよい。ＮＶＲＡＭは、フラッシュメモリカード或いは組み込み形フラッシュメモリシステムの一部であってもよい。ＮＶＲＡＭは揮発性ＲＡＭと同じアプリケーションの多くに使用され、ＮＶＲＡＭに格納されているデータは電源が失われても失われないという利点がある。例えば、メディア管理テーブルはＮＶＲＡＭにおいて維持される。
【００９７】
図１９は、メモリシステム１９００上に配置されているＮＶＲＡＭ１９０１を示す。メモリシステム１９００は、取り外し可能なメモリカードにおいて実現可能である。ＮＶＲＡＭ１９０１は、ホスト１９０５から受け取られているデータのためのバッファとして使用することもできる。データをフラッシュメモリアレイ１９１０にプログラムする前にデータをバッファリングすることによって、メモリアレイ１９１０の適応メタブロックを、受け取られたデータにより良く適合するように構成することができる。図１２Ａ、１２Ｂおよび１２Ｃに示されている前の例では、メモリアレイのメタブロックに格納されたデータは、後に、そのデータのためにより良く構成されたメタブロックにコピーされた。ＮＶＲＡＭバッファを使用することにより、フラッシュメモリの１つの部分から他の部分へのこのようなコピー操作を回避し或いは最少にすることができる。
【００９８】
図２０は、始めにＮＶＲＡＭに格納されるデータのストリームの境界を反映するように適応論理ブロックをどのように構成することができるかということの例を示す。データストリーム２００１および２００２は、ホストから受け取られて、ＮＶＲＡＭに格納される。データストリーム２００１と２００２とは論理的に不連続である。すなわち、データストリーム２００１とデータストリーム２００２との間の論理アドレス範囲にギャップがあり、それらは別々のストリームであり、別様に処理されることが示されている。別々のストリームは、ストリームとストリームの間の時間遅れにより、或いはストリームとストリームの間に断絶が存在することを示すホストからの何らかの連絡によっても区別される。
【００９９】
データストリーム２００１は、５個の論理グループ２０１０〜２０１４にわたって広がる論理アドレス範囲を有する。データストリーム２００２は、７個の論理グループ２０１７〜２０２３にわたって広がる論理アドレス範囲を有する。適応論理ブロック２０３０および２０３１が論理グループ２０１０〜２０１４から形成される。適応論理ブロック２０３２および２０３３が論理グループ２０１７〜２０２３から形成される。適応論理ブロック２０３０〜２０３３は、データストリーム２００１，２００２のフラッシュメモリアレイ２０４０へのプログラミングの間に最大の並列性を可能にするように構成される。フラッシュメモリアレイ２０４０は４個のプレーンを有するので、適応論理ブロックは４論理グループの最大サイズを有する。適応論理ブロック２０３０および２０３３は、４個の論理グループから各々成り、最大の並列性で別個にプログラム可能である。適応論理ブロック２０３１，２０３２は、並列に、最大の並列性で、一緒にプログラム可能である。データストリーム２００１が特定のホストファイルに対応し、データストリーム２００２が別のホストファイルに対応するならば、その２つのファイルがデータの最少量のコピー操作で別々に更新されるように、２つのファイルを別々の適応メタブロックにおいて維持するのが有利である。従って、データストリームを含むように使用される論理ブロックの境界は、データストリームの境界になるべく適合させられる。データストリーム２００１および２００２は、論理アドレス空間において他のデータストリームにより分離されることになる。ＮＶＲＡＭにおいて数個のデータストリームを維持することにより、数個のデータストリームの特性を比較して、データストリーム内のデータをフラッシュメモリアレイ２０４０にプログラムする最善の方法を判定することができる。図２０の例は図１９に示されているハードウェアで実施され、この場合データストリーム２００１，２００２はＮＶＲＡＭ１９０１に格納され、メモリアレイ２０４０はフラッシュメモリセルアレイ１９１０に対応する。
【０１００】
図２１は、ＮＶＲＡＭの他のアプリケーションを示す。データの性質によりデータをいずれかのタイプのメモリに格納することができるように、メモリシステムはＮＶＲＡＭとフラッシュメモリとを統合することができる。例えば、頻繁に更新されるデータはＮＶＲＡＭに格納される。ＮＶＲＡＭは、フラッシュメモリのように使用されるように構成することができる。フラッシュメモリが特定の消去ブロックサイズを有する場合、ＮＶＲＡＭは同サイズのデータを単位として動作するように構成される。
【０１０１】
図２１は、ＮＶＲＡＭに格納される更新済みデータ２１４０を示す。適応論理ブロック２１３０〜２１３２は、元のデータのストリーム２１０５からの元のデータを含む論理グループ２１１０〜２１２１から形成される。適応論理ブロック２１３０〜２１３２はメモリアレイ（図示せず）にプログラムされる。更新済みデータ２１４０はホストから受け取られる。前述したように、更新済みデータは更新中に新しい適応論理ブロックに格納することができるので、１つ以上の適応論理ブロックは更新済みデータを含み、他の適応論理ブロックは元のデータだけを含む。論理グループ２１２５，２１２６は、更新済みデータ２１４０と、元の論理グループ２１１５，２１１６からの多少の元のデータとから形成される。適応論理ブロック２１３５は論理グループ２１２５，２１２６から形成される。適応論理ブロック２１３６，２１３７は、適応論理ブロック２１３１内の残りの論理グループから形成される。従って、適応論理ブロック２１３１は、元のデータだけを含む適応論理ブロック２１３６および２１３７と更新済みデータを含む適応論理ブロック２１３５とにより取って代わられる。
【０１０２】
適応論理ブロック２１３５は、フラッシュメモリアレイではなくてＮＶＲＡＭに格納される。これは、適応論理ブロック２１３５が効率的に更新されることを可能にする。一般に、フラッシュメモリで可能な速度より高い速度でＮＶＲＡＭに書き込むことが可能である。データは、非順次的順序で、ガーベッジコレクションなしで書き込まれてもよい。メディアマネージャは、フラッシュメモリと同様の仕方でＮＶＲＡＭを処理することができる。ＮＶＲＡＭは、フラッシュメモリの消去ブロックと同じサイズを有するアドレス指定可能な複数の単位に分割される。アドレス指定可能な単位は並列にプログラムされてもよい。論理グループ２１２５，２１２６の位置を記録するテーブルは、ＮＶＲＡＭ内のアドレス指定可能な単位のアドレスを単に記録する。更新済みデータと同じ論理範囲を有するデータのその後の更新があるならば、それらの更新は、フラッシュメモリの一部分から他の部分へデータをコピーすることなく迅速に行われることになる。適応論理ブロック２１３５はＮＶＲＡＭからフラッシュメモリへ再配置される。例えば、他の目的に使用するために使用可能なＮＶＲＡＭ内の容量が不十分であるとき、適応論理ブロック２１３５からのデータをＮＶＲＡＭからフラッシュメモリへ移して、使用可能なＮＶＲＡＭの容量を作り出すことができる。
【０１０３】
適応論理ブロック２１３６および２１３７は、唯一の論理グループを各々有する。これらの論理グループは、新しい適応論理ブロック２１３８，２１３９が形成されるように再構成することができる。適応論理ブロック２１３８，２１３９は、適応論理ブロック２１３６，２１３７より大きく、より効率的なデータ処理を可能にする。
【０１０４】
データ境界
メモリシステムにより受け取られるデータの中にデータ境界が存在する。データ境界（論理境界）の例は、データラン境界およびファイル境界を含む。通常、１つのホストファイルは１つ以上のデータランとして格納される。データランは、ファイル記憶のためにホストにより割り当てられる論理的に連続する複数のセクタのセットである。データランは、有効なデータを既に含んでいない論理アドレス空間の部分に割り当てられる。図２２は２つのファイル、ファイルＡおよびファイルＢを示す。ファイルＡはデータラン１、データラン３およびデータラン５を含む。ファイルＢはデータラン２およびデータラン４を含む。
【０１０５】
ファイル境界は、ホストが１つのファイルを他のファイルの末端の直ぐ後に１つのアドレスから書き始める場合に作られる。従って、ファイル境界は１つのデータランの中にあることになる。図２３は、単一のデータランの中に書き込まれたファイルＣとファイルＤとの間のファイル境界を示す。
【０１０６】
通常、適応メタブロックを使用するメモリアレイによりデータが受け取られるとき、そのデータの格納のための適応メタブロックの構造は、データ境界の位置を考慮に入れない。その理由は、データ境界の位置が分からないこと、或いはデータを大きな適応メタブロックに速やかに書き込まざるを得なくする時間的制約があることにある。このようなメモリアレイに記憶されているデータが更新されるとき、多少のデータが元のメタブロックから新しいメタブロックにコピーされなければならない。このようなデータのコピーは、メモリシステムの、新しいデータを書き込むための容量を減少させる。通常、所与の操作において単一の論理ファイルだけが更新される。１つの適応メタブロックが２つ以上のファイルの部分を含んでいる場合、付加的なファイル部分は新しい適応メタブロックにコピーされなければならない。このような部分のコピーは、ガーベッジコレクションの間に行われ、かなりの資源を使い果たす可能性を有する。従って、データ境界を含む適応メタブロックは、それらが更新されるときに、不要なオーバーヘッドの原因となる。
【０１０７】
メモリアレイ内でのデータのコピーを最小限にすると同時にプログラミング中に並列性を最大にすることによって高性能を達成することができる。これら２つの目標は、高度の並列性を達成するために複数の適応メタブロックを並列にプログラムし、データ境界を含むように最小サイズの適応論理ブロック（メタグループ）を形成することによって、達成されることになる。適応メタブロックは、１つの単位としてプログラムされる“プログラムブロック”に形成可能である。プログラムブロックは、最大並列プログラミングの単位である。すなわち、１つのプログラムブロックは、全体としてメモリアレイの全てのプレーンにわたって広がる複数の適応メタブロックから構成される。図２４は、このようなメモリシステムにおいて使用されるデータ単位の階層を示す。
【０１０８】
データ境界を含むように最小サイズのメタグループを形成することの例が図２５および２６に示されている。図２５は、最小サイズのメタグループであるメタグループに各々格納された２つのデータラン境界を示す。ホストセクタデータラン２５１０は、論理アドレスＡから論理アドレスＡ＋４ｎ＋Ｘまで広がっている。従って、データ境界２５２０が論理アドレスＡ＋４ｎ＋Ｘに存在する。論理アドレスＡ＋４ｎ＋Ｘは、論理グループ２５３０の中にある。メタグループＢはデータ境界２５２０を含むように形成される。メタグループＢは、論理グループを１つだけ含む最小サイズのメタグループである。ホストセクタデータラン２５１０の残りの部分はメタグループＡに含まれる。メタグループＡは最小サイズのメタグループではなくて４つの論理グループを含む。図２５は、論理アドレスＢ＋Ｙから広がるホストセクタデータラン２５１１も示す。従って、データ境界が論理アドレスＢ＋Ｙに形成される。論理アドレスＢ＋Ｙは、論理グループ２５３１の中にある。メタグループＣは、データ境界２５２１を含むように形成される。メタグループＣは、論理グループを１つだけ含む最小サイズのメタグループである。ホストセクタデータラン２５１１の残りの部分はメタグループＤに含まれる。メタグループＤは、２つの論理グループを有し、最小サイズのメタグループではない。ホストセクタデータラン２５１０および２５１１が後に更新されるとき、これは更新されるデータラン内に存しない付加的なデータの僅かなコピー操作で行われる。その理由は、メタグループＢおよびＣだけが付加的なデータを含み、これらの各々が１論理グループに及ばない付加的データを含むことにある。
【０１０９】
図２６は、最小サイズの適応メタグループにマッピングされるファイル２６１０およびファイル２６１１間のファイル境界２６１５を示す。ファイル境界２６１５は、論理アドレスＡ＋４ｎ＋Ｘに示されている。ファイル境界２６１５はホストセクタデータラン２６０５の中にある。論理アドレスＡ＋４ｎ＋Ｘは、論理グループ２６３０の中にある。メタグループＢは論理グループ２６３０から形成される。メタグループＡは、ファイル２６１０の残りの部分から形成される。メタグループＣは、ファイル２６１１の残りの部分から形成される。ファイル２６１０は、メタグループＡおよびＢを更新することによって更新されることになる。従って、メタグループＢに含まれるファイル２６１１の一部２６４１だけがファイルＡの更新の間にコピーされる。同様に、ファイルＢは、メタグループＢおよびＣを更新することによって更新されることになる。これは、メタグループＢに格納されているファイル２６１０の一部２６４０だけをコピーすることを含む。
【０１１０】
データ境界情報はメモリシステムにより、メモリシステムに供給されるデータから判定され、或いはデータ境界情報はメモリシステムに直接供給されることになる。例えば、ホストは、ホストシステム自体がメモリシステムに供給するデータに関するデータ境界情報を供給することができる。データ境界情報は、ホストにより供給されるデータの中のデータラン境界またはファイル境界の位置を含むことができる。このようなデータ境界情報は、通常、境界を含むデータより前に提供される。メタグループの最大サイズがＬ個の論理グループである場合、提供されるデータより少なくともＬ個の論理グループだけ前にデータ境界情報を提供することが望ましい。
【０１１１】
ホストは、直ぐ書き込めるデータがそれ以上はないことを知らせるためにデータランのシーケンスの終わりについての通知を提供することもできる。この通知は、メモリシステムがバックグラウンド操作をスケジュールすることを可能にする。電源切断操作の通知もホストにより提供される。このような通知は、ハンドシェイク操作の一部分である。電源切断操作は、メモリシステムがホストに応答して、メモリシステム自体が電源切断に適する状態にあることを示すまでは行われない。メモリシステムがメモリシステム自体の能力をホストに知らせ、またその逆も行われるように、電源投入の後にホストとメモリシステムとの間で対話が行われる。このような能力は、前述したようにデータ境界情報を受け入れて使用する能力を含む。
【０１１２】
ホストからのデータ境界情報を受け取る他に、データ境界はメモリシステムにより他の情報源からも判定可能である。これは、更新される１つの範囲のデータからデータ境界位置を引き出すことを含む。データランの始まりは、ホストにより提供されるデータアドレスから直接特定されることになる。データランの終わりは、他のデータランへのアドレス移行から仮定されることになる。ファイル境界は、ホストによるディレクトリおよびＦＡＴアクセスのパターンから仮定されることになる。データ境界およびファイル境界を推測するために元のデータについてのメタグループマッピングを使用することもできる。
【０１１３】
データ境界管理操作
方式Ａでは、データ境界位置に応答する構成でのデータ格納は、始めにこのようなデータを一時的位置に格納し、その後データをフラッシュメモリに格納すべくメタグループにマッピングすることによって、行われることになる。一時的位置は、アキュムレータＲＡＭにより提供される。或いは、一時的位置は、フラッシュメモリアレイの一部により提供される。図２７は、データ境界管理情報を用いてデータを構成するためのこれら２つの選択肢を示す。方式Ａは、一時的アキュムレータＲＡＭに格納されているデータを示し、これは、次に、データ境界管理でフラッシュメモリに格納される前にメタグループマッピングにさらされる。方式Ｂは、メタグループ再マッピングの前に中間メタグループマッピングでデータをフラッシュメモリに格納し、その後にデータ境界管理でフラッシュメモリに格納することを示している。
【０１１４】
一時的アキュムレータＲＡＭは、ホストからセクタのデータを受け取り、セクタのデータは、後に、データ境界の位置により決定される仕方でフラッシュメモリにおいて並列プログラムされるべく転送される。アキュムレータＲＡＭは、少なくとも１つのプログラムブロックのデータを格納することを可能にするのに充分な容量を持つことができる。従って、アキュムレータＲＡＭ内のデータは、後に単一のプログラムブロックにおいて並列にプログラムされるメタブロックに形成される。アキュムレータＲＡＭは、ＮＶＲＡＭ１９０１のような不揮発性メモリである。或いはアキュムレータＲＡＭは揮発性メモリであってよく、その場合には、データがフラッシュメモリにプログラムされる前にホストによって電源が除去されれば、アキュムレータＲＡＭ内のデータが失われる危険がある。この危険は、ホストとメモリシステムとの間に適切なプロトコルを持つことによって管理されることになる。
【０１１５】
図２８Ａは、図２５に示されているメタブロックＡ〜Ｄから構成されるプログラムブロック２８００を示す。最大プログラミング速度のためには、メタブロックＡ〜Ｄを一緒にプログラムすること、従ってメモリシステムの最大並列プログラミング容量を使用することが望ましい。ファイルを更新する操作の効率のためには、メタブロックＢおよびＣを、各々１つの消去ブロックから成る別々のメタブロックとして維持することが望ましい。図２８Ａに示されているデータの構成は、これらの目標の両方を達成する。データのセクタは、２つの別々のデータランとして、すなわちＡからＡ＋４ｎ＋Ｘまでのデータラン２５１０およびＢ＋ＹからＢ＋３ｎ−１までのデータラン２５１１として、ホストから受け取られる。図２８Ｂは、これらのデータランからのデータのセクタがメタブロックＡ〜Ｄにどのようにプログラムされるのかを示す。この例では、ページはデータの単一のセクタを含むけれども、他の例ではページは複数のセクタを含むことができる。プログラムブロックはメモリアレイの全てのプレーンにわたって広がる。プログラムブロック内では、セクタは、メタブロック構成により決定される順序でプログラム可能である。プログラムブロックページが示され、１つのプログラムブロックページは、並列にプログラム可能であるメモリアレイの各プレーンからの１つのページから構成される。すなわち、プログラムブロックページ０はメモリアレイの全てのプレーンにわたって広がり、プログラムブロックページ０内の全てのセクタは同じプログラミングステップでプログラムされる。プログラムロックページ０がプログラムされ終わると、プログラムブロックページ１がプログラムされ、以降同様に行われる。図２８Ｂにおいてセクタがプログラムされる順序は、これらのセクタが図２５に示されているようにホストから受け取られる順序ではない。アキュムレータＲＡＭにおけるこれらのセクタの順序の変更が図２８Ｃに示されている。図２８Ｃは、プログラムブロック２８００にプログラミングのために転送されるアキュムレータＲＡＭ内に保持されているデータラン２５１０およびデータラン２５１１を示す。プログラムブロックにコピーされるべきデータは、図に示されているようにアキュムレータＲＡＭに書き込まれることになる。セクタＡ＋４ｎ＋ＸからＡ＋５ｎ−１までとＢからＢ＋ＹまでとはアキュムレータＲＡＭにコピーされるので、これらはプログラムブロックに転送されるように使用可能である。或いは、コピーされるべきデータは、フラッシュメモリ内に既に置かれ、従ってフラッシュメモリアレイの１つの部分から他の部分へと直接コピーされることになる。図２８Ｃは、図２８Ｂのプログラムブロックページ０およびプログラムブロックページ１についてのセクタのマッピングを示す。
【０１１６】
図２７の方式Ｂの場合のように、ホストから受け取られるデータのための一時的記憶位置を提供するためにフラッシュメモリが使用される場合、データは、いろいろなタイプのメタグループを含む中間フォーマットで格納される。このようなメタグループのサイズは、最大サイズのメタグループの論理アドレス範囲の中のデータラン境界またはファイル境界のような論理境界の存在により、また任意の論理境界の後にさらなるデータを転送する必要により、決定される。中間の形のデータ記憶を提供するために次の５つのメタグループタイプ、すなわちフルメタグループ、パーシャルメタグループ、ショートメタグループ、スタートメタグループおよびマルチファイルメタグループ、を使用することができる。
【０１１７】
フルメタグループ２９００が図２９Ａに示されている。完全メタグループは、格納されるべきデータの中に論理境界がない場合、或いは存在する任意の論理境界に関して使用可能な情報がない場合に、割り当てられる。
【０１１８】
パーシャルメタグループ２９０１が図２９Ｂに示されている。格納されるべきデータ中に論理境界が存在するけれども中間フォーマットでデータをプログラムするときに最大の並列性が望まれる場合にパーシャルメタグループが割り当てられる。論理境界は、プログラミングの前に（例えば、ホストから）知られ、或いはプログラミング中に遭遇される。パーシャルメタグループは、１つのメタグループにおいて可能な最大個数より少ないデータの論理グループを含む。パーシャルメタグループは、最大サイズのメタブロックにプログラムされるので、アレイの全プレーンを並列に用いてプログラムされ、従ってなるべく速やかにプログラムされる。
【０１１９】
ショートメタグループ２９０２が図２９Ｃに示されている。ショートメタグループは、格納されるべきデータの中に論理境界が存在して最大の並列性が不要である場合に、割り当てられる。ショートメタグループは、１つのメタグループにおいて可能な最大個数の論理グループより少ない論理グループを有する。ショートメタグループは、最大サイズのメタブロックに含まれる消去ブロックより少ない消去ブロックを含むメタブロックにプログラムされる。データ書き込み帯域幅は減るが、再配置されるデータはショートメタグループと並列にプログラム可能である。ショートメタグループは、データラン境界の直ぐ後にそれ以上のデータが続かないということをホストが信号したときに使用されることになる。
【０１２０】
スタートメタグループ２９０３が図２９Ｄに示されている。スタートメタグループは、データランのスタート境界のデータを格納するために割り当てられる。データラン内の第１のセクタが論理グループの第１のセクタではない場合、整列フセットを使用することができる。第１の論理グループを完成させるデータは、他の位置からコピーされることになる。スタートメタグループは、書き込み中に論理境界に遭遇した場合、パーシャルメタグループであってもよい。
【０１２１】
マルチファイルメタグループ２９０４が図２９Ｅに示されている。マルチファイルメタグループは、ファイル境界を含み、従って少なくとも２つの異なるファイルの部分を含む。マルチファイルメタグループは、パーシャルメタグループ、ショートメタグループ或いはスタートメタグループであってもよい。
【０１２２】
前述した中間フォーマットのメタグループの中のデータは、後に論理境界が存在するときにより望ましい構成に再マッピングされることになる。フルメタグループは論理境界を含んでいないので、再マッピングは不要である。しかし、パーシャルメタグループ、ショートメタグループ、スタートメタグループおよびマルチファイルメタグループは図３０に示されているように再マッピングされることになる。図３０Ａは、パーシャルメタグループ３０１０のメタグループＡおよびメタグループＢへの再マッピングを示す。メタグループＢは最小サイズ（１論理グループ）のメタグループである。メタグループＢは、１つの元のブロックからコピーされたデータで完成される。図３０Ｂは、ショートメタグループ３０２０のメタグループＡおよびメタグループＢへの再マッピングを示す。これは、パーシャルメタグループの再マッピングと同様である。図３０Ｃは、スタートメタグループ３０３０のメタグループＡおよびメタグループＢへの再マッピングを示す。ここで、スタートメタグループ３０３０は整列オフセットを有する。この整列オフセットは、メタグループＡが順序整然となるように、除去される。図３０Ｄは、メタグループＡ、ＢおよびＣに再マッピングされるマルチファイルメタグループ３０４０を示す。メタグループＢは、論理境界３０４１を含む。メタグループＢは、最小サイズ（１論理グループ）のメタグループである。
【０１２３】
中間フォーマットの中のデータは、ホストからの受け取りの直後に再マッピングのために分析される。しかし、データの再配置は直ぐには行われないかもしれない。代わりに、データのためにプログラム操作がスケジュールされ、データと計画された再マッピングとに関する情報が再マップリストに格納されることになる。その後、データ再配置は、より適切な時にバックグラウンドで行われ、或いは格納されたデータの範囲内の更新されたデータの受け取りのようなイベントによりトリガされることになる。再マップリストは、適切な制御情報構造でフラッシュメモリに、例えばログまたは専用再マップセクタに格納することができる。
【０１２４】
再マップリストは、再マッピング操作が未解決になっている中間フォーマットで最近書き込まれた各メタグループについて１つのエントリを有する。このようなメタグループは一般にデータ境界を含む。再マップリスト中のエントリは以下のように６個のフィールド、すなわち
メタグループのタイプ（パーシャル、ショート、スタートまたはマルチファイル）
メタグループ中のデータランのスタートの論理アドレス
メタグループサイズ（メタグループ中の論理グループの個数）
メタブロックサイズ（メタブロック中の消去ブロックの個数）
メタグループ内の境界のオフセット
ページタグ
を含むことができる。
【０１２５】
中間フォーマットのメタグループが作られるとき、１つのエントリがリストに加えられる。中間フォーマットの１つのメタグループがリストから削除されるとき、リストから１つのエントリが除去される。１つのエントリが追加または削除されるとき、新しいリストを新しい位置に、例えば新しいログセクタまたは新しい再マップセクタに、書き込むことによってリストは更新可能である。
【０１２６】
再マップリスト中のメタグループマッピングは、関連するデータに関する如何なるメディア管理操作のためにも使用されない。メディア管理制御構造は、データの一時的記憶のために割り当てられた中間フォーマットのメタグループに関する。従って、他のメディア管理機能に影響を及ぼさずに再マップリストからエントリを除去することができる。例えば、未解決の操作のバックログが大きくなりすぎたならば、エントリを削除することになる。これは、データがメモリアレイに格納される仕方の効率を単に低下させる。
【０１２７】
中間フォーマットからのデータのプログラミングは、ホストデータを書き込むためにホストが使用可能な書き込み帯域幅が減じられることのないようにスケジュールされることになる。再マッピング操作は、データがホストから受け取られていないときに、バックグラウンド操作として実行される。単一の中間メタグループについての全ての再マッピングされるメタグループは並列にプログラム可能である。再マッピング操作が実行されている間に電源が失われることのないように、メモリシステムの電源切断を管理するためにホストとのハンドシェイクプロトコルを確立することができる。再マッピング操作は、元のホストデータのプログラミングと並列に実行可能である。図３１は、ホストからのデータ３１５０が適応メタブロック３１１０にプログラムされる間に、メモリアレイから再配置されたデータ３１６０が並列に適応メタブロック３１２０にプログラムされることを示す。このような並列操作は元のホストデータを書き込むために使用可能な書き込み帯域幅を減じるため、このような並列プログラミングは直ぐに書き込むために使用可能な元のホストデータがそれ以上はないということをホストがメモリシステムに知らせる場合に限って適切である。再マッピング操作は、ホスト更新に応答して実行可能である。更新されるべきデータが中間フォーマットであり、再マップリストに列挙されている場合、更新されるデータは、中間メタグループからコピーされるデータと共に再マッピングフォーマットで書き込むことができる。
【０１２８】
ホストインターフェイスにおいて新しい処理に迅速に応答することができるように再マッピング操作を一時停止させることができる。再マッピング操作は現在のページプログラミング操作の完了後に一時停止されてよく、その場合には、後に次のページのプログラミングから再開される。或いは、チップの構成が可能ならば、ホストに速く応答するために、１つのページをプログラムしている途中で再マッピング操作を一時停止させることができる。ページプログラミング中に再マッピング操作を一時停止させるために、リセットコマンドをフラッシュメモリチップに発することによってフラッシュメモリにおけるその実行を終わらせることができる。チップは、その後、新しいホスト処理に応じて直ぐにアクセスすることができる。再マッピング操作は、その後、一時停止されたページについて同一のデータをフラッシュチップに再転送し、次にプログラムコマンドを送ることによって、再開することができる。多くのフラッシュチップの構成は、データパターンが変わっていなければ、部分的にプログラムされたページのプログラミングの再開を許容する。
【０１２９】
ホストが境界位置情報を提供するデータ記憶
一実施形態では、ホストは、ホストデータをメモリアレイにより効率的に格納するために使用可能な付加的情報をメモリシステムに提供する。このような情報の一例は、送られるホストデータ内のデータ境界（論理境界）の位置である。通常、データ境界の位置は、ホストデータが受け取られるときにそれが効率的に格納され、始めに中間フォーマットで格納されなくてもよいように、境界を含むホストデータが送られる前に提供されるべきである。
【０１３０】
データ境界位置に基づいてホストデータをより効率的に格納するために、データをメモリアレイの適応メタブロックに格納する前に一定のデータをバッファリングすることが有利である。この目的のために、シリアルフラッシュバッファを設けることができる。図３２は、消去済みブロックプール３２０４からの消去ブロックで構成されるシリアルフラッシュバッファ３２０２を示す。シリアルフラッシュバッファ３２０２内の消去ブロックは、在来のメタブロックのような最大サイズの適応メタブロックとして構成することできる。これは、メモリアレイの最大の並列性でデータをシリアルフラッシュバッファにプログラムすることを可能にする。メモリアレイが複数のプレーンに分割されている場合、このことは、シリアルフラッシュバッファのメタブロックがメモリアレイの各プレーンからの１つの消去ブロックを含むことを一般的に意味する。従って、シリアルフラッシュバッファ３２０２は１つ以上のバッファメタブロックから構成され、それらは、一般に、必ずしもそうとは限らないけれども、最大の並列性でのデータ格納を可能にするメタブロックである。シリアルフラッシュバッファとして使用することができる構造の例が、本願と同じ日に出願され、その全体が本願明細書において参照により援用されている代理人整理番号ＳＮＤＫ．４０６ＵＳ０の“スクラッチパッドブロック”という米国特許出願（特許文献２４）に記載されている。
【０１３１】
前述したようにメモリアレイ内の適応メタブロックにデータを直接格納する代わりに、ホストデータをシリアルフラッシュバッファ３２０２に送ることができる。シリアルラッシュバッファは、メモリアレイ内の１つ以上のバッファメタブロックから成る。バッファメタブロックは、論理的に関連していないデータの複数の部分を含むことができる。シリアルフラッシュバッファ３２０２内のいろいろなメタブロックは、論理境界とバッファメタブロックのメタブロック境界との整合がないので、如何なる特別の意味も持たない。すなわち、順次データの部分は、単一のメタブロックに格納され、或いは複数のメタブロックに格納され、また一般にバッファメタブロックとは整列させられない。データがバッファメタブロックからコピーされるとき、バッファメタブロック内のデータが陳腐になる。１つのバッファメタブロック内の全てのデータが陳腐であるとき、そのバッファメタブロックを含む消去ブロックは消去済みブロックプールに返されることになる。従って、バッファメタブロックは、必要に応じて消去済みブロックプールからの消去ブロックから形成される。それらが陳腐なデータだけを含むとき、消去ブロックは消去されて消去済みブロックプールに返される。シリアルフラッシュバッファ３２０２は線形メモリを形成し、シリアルフラッシュバッファ３２０２に格納されるべき新しいデータは消去済みブロックプール３２０４からの（割り当てブロックリストまたは同様の構造からの）連結された複数のブロックからバッファの頂部に形成されたバッファメタブロックに書き込まれ、バッファの底部のバッファメタブロック内のデータは割り当てられた適応メタブロックにコピーされるのでバッファの底部のメタブロック内のデータは陳腐になる。陳腐なデータだけを含むバッファメタブロックの消去ブロックは、（プレーンブロックリストまたは同様の構造に）消去済みブロックプール３２０４に返される。バッファメタブロックは、固定されたサイズのメタブロックであり、或いは個々に選択されたサイズの適応メタブロックである。例えば、最大サイズのメタブロックは、高度の並列性を提供するバッファメタブロックとして使用することができる。
【０１３２】
図３３Ａは、フラッシュメモリアレイの割り当てられた適応メタブロックに格納されるホストデータのための２つの択一的ルートを示す。データは、割り当てられた適応メタブロック３３０８に直接書き込まれる（３３０６）。或いは、データは、シリアルフラッシュバッファ３３０２のバッファメタブロック３３１２に書き込まれ（３３１０）、その後バッファメタブロック３３１２から割り当てられた適応メタブロック３３１６にコピーをする（３３１４）ことができる。特定のデータのためにこれらの択一的ルートのどちらが使用されるかは、論理境界の位置によることになる。特に、論理境界の位置がホストによって提供される場合、どちらのルートを使用するべきかは、提供された位置に応じて決定されることである。データの一部分が最大サイズのメタグループと同じかまたはこれより大きくて如何なる論理境界も持っていない場合、データのその部分は、割り当てられた適応メタブロックに直接格納することになる。最大の並列性を目的として可能な場合には最大サイズの適応メタブロックが使用される。最大サイズのメタグループより小さなデータの部分が格納される場合、どちらのルートを使用するかは部分のサイズに基づいて決定することである。データの一部分が論理境界を有する場合、一般にはそれを最小サイズの適応メタブロックに格納するのが望ましい。データのこのような部分は、バッファメタブロックに格納されて後に割り当てられた適応メタブロックにコピーされることになる。これは、データのこのような部分をホストから受け取って始めに最大の並列性で速やかに格納することを可能にする。後に、データのこれらの部分は、図３３Ａにおいて３３０６および３３１４で示されているように、割り当てられた適応メタブロックに他のデータと並列にコピーされるので、高度の並列性が使用される。従って、最小サイズの適応メタブロックが書き込まれる場合でも低度の並列性でのデータ書き込みは一般に回避される。
【０１３３】
図３３Ｂは他の例を示し、この例ではバッファメタブロック３３１８内のデータが最小サイズの適応メタブロック３３２２にコピーされ（３３２０）、ここで元の適応メタブロック３３２８からコピーされたデータ３３２４と共に格納される。この例は、論理境界を含む最小サイズの適応メタブロックを代表している。論理境界は適応メタブロックの論理アドレス空間内の何処かに存在するので、論理境界の一方の側のデータが更新されるときには、更新されたデータと或る程度の元のデータとの両方が適応メタブロックに格納される。
【０１３４】
図３４は、前述した方式ＡおよびＢと対比させて、シリアルフラッシュバッファを使用する方式、方式Ｃを示す。方式ＡおよびＢは、受け取られた全てのデータを何らかの中間形で（ＲＡＭまたはフラッシュに）格納し、（論理境界の位置のような）データの特性を判定し、その後にデータをそれらの特性に応じてフラッシュに格納する。対照的に、方式Ｃでは、データの特性はホストから受け取られる。これらの特性の受け取りは、データをその特性に応じてフラッシュメモリに直接格納することを可能にする。しかし、或るデータはバッファメタブロック３４３０に格納されて、後に、高速操作を可能にするように特性に応じてフラッシュメモリに格納されるべくコピーされる（３４３２）。従って、バッファメタブロックの目的は、方式ＡおよびＢのＲＡＭまたは中間メタグループの目的とは異なり、格納されるデータの多くが割り当てられたメタブロックに直接書き込まれる。
【０１３５】
データはデータラン単位で更新され、データランは、割り当ての直前には使用されていなくて割り当てられたセクタ同士の間に広がる、ホストにより割り当てられた論理的に連続する複数のセクタのセットである。データランは、論理アドレス空間の複数の割り当てられた部分により画定される空いている論理アドレス空間の１つの連続する部分にホストがデータを割り当てるときに形成される。或るシステムでは、データランはメタグループ構造と整列しておらず、このことはデータ更新時の非能率の原因となる。ここで説明する特定のシステムでは、データランは、メタグループのサイズおよび境界位置（従って、対応する適応メタブロックのサイズ）をデータに適合させることによってメタグループと整列させられるほうがよい。特に、論理境界を含むデータの部分を格納するために最小サイズのメタグループを使用してもよい。データラン境界の位置はメモリコントローラによって決定することができる。データランのスタート部に存するデータラン境界は、最後に受け取られたデータとは連続していないデータがホストから受け取られたときに、特定されることになる。データランの終端部に存するデータラン境界も、論理アドレスにおけるジャンプにより特定されることになる。このようなジャンプの前の最後のセクタは、１つのデータランの最後のセクタである。しかし、ホストから受け取られたセクタの中の論理アドレスに存するジャンプが（ＦＡＴのような）システム情報の更新またはいろいろなデータランへのインターリーブな書き込みに起因するものであるという例外がある。或るシステムではホストは２つ以上のデータランにインターリーブ的に書き込むことができる。コントローラは、この事態に対処するために複数の開いているデータランを維持することができるので、１つの開いているデータランに連続するデータが受け取られたならば、それはそのデータランの一部として処理される。それが１つの開いているデータランに連続するものでなければ、それは新しいデータランのスタート部であると見なされる。開いているデータランは、一定時間後にコントローラによって、データランの個数が限度に達したとき、或いはホストからの信号に応答して、閉じられることになる。
【０１３６】
図３５Ａは、非整列 (non-alignment)（Ｎ）で格納されたデータラン３５３０を示す。これは、論理境界の位置を考慮せずに格納されたデータランである。メタグループ構造は、最大サイズの全てのメタグループを示す。図３５Ｂは、部分的整列 (partial alignment)（Ｐ）で格納されたデータラン３５３２を示す。データラン３５３２のスタート部に存するデータラン境界を格納するために最小サイズのメタグループ３５３４（１論理グループ）が使用される。データラン３５３２の残りの部分は最大サイズのメタグループ３５３６，３５３８に格納されるので、データの終端部は最大サイズのメタグループ３５３８内に存在する。このように、各端部にデータ境界を有するデータランについて、唯一のデータ境界が最小サイズのメタグループに割り当てられる。図３５Ｃは、完全整列 (full alignment) （Ｆ）で格納されたデータラン３５４０を示す。データラン３５４０の両端部に存するデータラン境界に最小サイズのメタグループ３５４２，３５４８が割り当てられる。最大サイズのメタグループは、高い並列性を得るために可能なところで（例えば、メタグループ３５４４）使用される。しかし、この例では、終端部から２番目のメタグループのために短縮されたサイズのメタグループ３５４６が使用されている。
【０１３７】
通常、データランの各端部に１つの最小サイズのメタグループが割り当てられる場合、これらのメタグループの間のデータランの部分は整数個の最大サイズのメタグループを形成しない。従って、データランの中央部分からの少なくとも１つのメタグループは最大サイズに及ばないメタグループである。図３５Ｃに示されている例では、終端部から２番目のメタグループ３５４６は、短縮されたサイズのメタグループ（或いはパッドメタグループ）である。しかし、パッドメタグループは、特定の位置に存在しなければならないわけではない。図３５Ｄは、いろいろなサイズの適応メタブロックにマッピングされた１つのデータランを有する１つのデータラン構造を示す。最小サイズのヘッドブロック３５５０とテールブロック３５５６とはデータラン境界を含む論理グループのために使用されている。データラン境界を含む論理グループ３５５０，３５５６の間では、データは、可能な場合には最大サイズの適応メタブロック（例えば、メタブロック３５５２）にマッピングされる。他の例では、複数のフルブロックが１つのデータランのために使用される。残りのデータはパッドブロック３５５４に格納されるが、これは短縮されたサイズの適応メタブロックである。
【０１３８】
図３５Ｅは、８個の論理グループの最大メタグループサイズを有するメモリに完全整列で格納されたいろいろな長さのデータランを示す。データラン境界が単一の論理グループ内に存在する場合、この論理グループは最小サイズのメタグループ３５５８を形成し、ヘッドメタグループと見なされる。データランが２個の論理グループにわたる場合、各論理グループは最小サイズの１つのメタグループ３５６０，３５６２を形成し、ヘッドメタグループおよびテールメタグループと見なされる。データランが３個の論理グループにわたる場合、中央の論理グループ３５６４は最小サイズのメタグループを形成し、パッドメタグループと見なされる。３個の論理グループと９個の論理グループとの間に及ぶデータランについて、ヘッドメタグループおよびテールメタグループは同じままであるが、パッドメタグループのサイズはデータランのサイズに従って大きくなる。データランが１０個の論理グループにわたる場合、ヘッドメタグループとテールメタグループとの間にフルメタグループ３５６６を形成することができる。従って、パッドメタグループは不要である。１０個の論理グループより大きなデータランについては、１つのフルメタグループと１つのパッドメタグループとを形成することができる。１８個の論理グループより大きいデータランについて、２つのフルメタグループを形成することができる。より大きなデータランについては、必要なときには適切なサイズの１つのパッドメタグループと共に、複数のフルメタグループを形成することができる。
【０１３９】
データがホストにより更新されるとき、そのデータは一般にデータラン境界の間に広がるデータランとして受け取られる。このようなデータラン境界の位置は、前に特定されてデータを格納するために使われていたものと同じである。従って、データランは、更新データのデータラン境界と整列して既に格納されているデータを更新することができる。例えば、１つのデータランが、同じ論理アドレス範囲にわたって広がる１つのデータランによって前に更新されたデータを更新する場合、データは同じ論理境界に整列させられることになる。格納されたデータが同じデータ境界に完全に整列して格納されたのならば、そのデータの更新は完全から完全への遷移を含む。格納されたデータが部分的整列で格納されたのならば、更新は、部分的から完全への或いは部分的から部分的への遷移を含むことになる。格納されたデータが非整列で格納されたのならば、更新は、非から完全への、非から部分的への、或いは非から非への遷移を含むことができる。図３６は、データ更新中に生じる遷移のうちの幾つかを示す。（完全から非へのような）他の或る遷移が可能ではあるが、それらは一般には望ましくないので図３６には示されていない。
【０１４０】
図３７は、データラン３７７０がホストから受け取られるときの完全から完全への（Ｆ２Ｆ）遷移の例を示す。データラン３７７０は、データの論理的に連続するセクタのストリームとして受け取られることになる。さらに、ホストは、データランのスタート部および終端部に存するデータ境界の位置を含むデータ境界位置情報を送ることができる。データランのスタート部３７７２の位置は、データラン３７７０内の第１に受け取られるセクタのアドレスから判定されて、前もって知られていなくてもよいけれども、データランの終端部３７７４の位置が、この例では完全整列を可能にするためにデータラン３７７０の最後のセクタが受け取られる前に知られる。他の例では、データランの終端部の位置は確実に知られないかもしれないが、位置は前のデータランの終端部の位置から予測される。このようなデータ境界位置は、ホストによりリストに記録可能である。ホストからのデータラン３７７０のデータラン境界は、完全整列で格納された前に受け取られたデータランのデータラン境界と同じである。従って、元のメタグループと同じサイズを有する更新されたメタグループが割り当てられることになる。データラン３７７０のデータの部分ＡおよびＤは、データラン境界を含む論理グループ内にあり、従って最小サイズのメタグループに格納される。従って、それらは始めにシリアルフラッシュバッファに格納される（Ａ→Ｋ，Ｄ→Ｌ）。バッファＫおよびＬ内のデータは、後に元のデータ（Ｐ→Ｅ，Ｑ→Ｊ）と一緒にヘッドメタグループ３７７６およびテールメタグループ３７７８にコピーされる（Ｋ→Ｆ，Ｌ→Ｉ）。ヘッドメタグループ３７７６およびテールメタグループ３７７８は、最小サイズのメタグループとしてメモリアレイに格納される。データランの部分Ｂは、最大サイズのメタグループＧを形成し、従ってシリアルフラッシュバッファに格納されずに割り当てられた最大サイズのメタブロックに直接格納される。データラン３７７０の部分Ｃは、最大サイズには及ばないメタグループＨを形成する。メタグループＨは、フラッシュメモリ内の割り当てられた適応メタブロックに直接書き込まれる。
【０１４１】
或る例では、部分Ｃのようなデータの部分は、割り当てられた適応メタブロックに格納される前にシリアルフラッシュバッファに格納することができる。しかし、部分Ｃのサイズによっては、それをフラッシュメモリに直接書き込むほうがより効率的である。例えば、部分Ｃが１つの完全メタグループの部分と殆ど同じ量のデータを含んでいる場合、データをフラッシュに直接書き込むほうが、それをシリアルバッファに書き込んで後にそれを整列したフォーマットでフラッシュにコピーするより効率的である。一般に、データをシリアルバッファにバッファリングすることからの効率のゲインは、少量のデータについて最大であり、大量のデータについて最小である。データをバッファリングするか否かの決定は、データの部分のサイズに基くことができる。完全メタグループのデータは最大サイズのメタブロックに直接書き込まれ、１論理グループまたはそれ未満を含むデータはシリアルバッファに書き込まれ、１論理グループと１完全メタグループとの間のデータは、１つのしきい値サイズより少量であれば、バッファリングすることができる。例えば、そのしきい値は、１つの完全メタグループ内の論理グループの個数の半分、または（１つの完全メタグループ内の論理グループの個数の半分）−２（Ｎ／２−２、ここでＮは１つの完全メタグループ内の論理グループの個数である）である。Ｎ／２−２は、効率的な操作を可能にして収斂性シリアルフラッシュバッファを持つために計算されたしきい値である。従って、１つのメタグループ内に１６個の論理グループがあるならば、６個の論理グループまたはそれ未満の論理グループを含むデータの部分はシリアルバッファにバッファリングすることができる一方、６個より多い論理グループを含むデータの部分はフラッシュに直接書き込まれてもよい。
【０１４２】
図３８は、部分的整列から完全整列への（Ｐ２Ｆ）遷移の例を示す。この例ではデータラン３８８０がホストから受け取られて完全整列で格納される。最小サイズのヘッドメタグループ３８８２およびテールメタグループ３８８４が割り当てられる。データラン３８８０により更新されるデータは、データランのデータ境界に部分的に整列させられて前に格納されたものである。従って、ヘッドメタグループと同じ論理アドレス空間について最小サイズの元のメタグループ３８８６が存在する。しかし、データランのテールに対応する元の最小サイズのメタグループはない。データランのスタート部のデータは図３７に示されているものと同様に扱われる。データＡはシリアルフラッシュバッファに格納される（Ａ→Ｋ）。その後、バッファＫ内のデータが、元のメタグループからコピーされるバッファＥ内のデータと一緒に（Ｐ→Ｅ）最小サイズの更新されるメタグループ３８８２にコピーされる（Ｋ→Ｆ）。データＢおよびＣは、前と同様にメタグループＧおよびＨにプログラムされる。メタグループＧは、最大サイズの更新されるメタグループに直接プログラム可能な最大サイズのメタグループとして示されている。メタグループＨは、最大には及ばないサイズであり、更新されるメタブロックに直接プログラムされ、或いはメタグループＨのサイズによっては先にシリアルフラッシュバッファに格納される。この例では、メタグループＨは更新されるメタグループに直接プログラムされる。より長いデータランが受け取られた場合、最大サイズの追加メタグループを使用することができる。
【０１４３】
データラン３８８０の終端部のデータＤは、シリアルフラッシュバッファにコピーされ（Ｄ→Ｌ）、その後に、元のメタグループからコピーされるデータＪ（Ｑ→Ｊ）と一緒にテールメタグループ３８８４にコピーされる。データＪは、最小サイズより大きなメタグループ３８８８（この場合、最大サイズのメタグループ）からコピーされる。メタグループ３８８８は、データランによって更新されないデータだけを含む論理グループＲを含む。論理グループＲは、再配置メタグループに再配置される（Ｒ→Ｔ）。他の例では、再配置メタグループは複数の論理グループを含むことができる。元のメタグループから再配置メタグループへの元のデータのこのコピー操作は、より大きな効率を得るために他のプログラミング操作と並列に行われてもよい。図３７および３８から分かるように、部分的から完全への遷移は完全から完全への遷移が含むよりも多くのデータコピー操作を含むことになる（例えば、元のデータＲの再配置メタブロックＴへのコピー）。
【０１４４】
図３９は、ホストから受け取られたデータラン３９９０についての部分的整列から部分的整列への（Ｐ２Ｐ）遷移の例を示す。この遷移は、データランのスタート部のデータについて前に説明したものと同様である。データラン３９９０のスタート部のデータＡは、シリアルフラッシュバッファに格納され（Ａ→Ｋ）、後に、元のメタグループ３９９４からコピーされるデータＥ（Ｐ→Ｅ）と一緒に最小サイズの更新されるメタグループ３９９２にコピーされる（Ｋ→Ｆ）。データＢは、最大サイズのメタグループにプログラムされる（Ｂ→Ｇ）。データラン境界まで広がっていて最大サイズに及ばないメタグループを含むデータＤは、最大サイズの更新されるメタグループ３９９６に書き込まれる（Ｄ→Ｉ）。元のメタグループからのデータＱは、同じ最大サイズの更新メタグループ３９９６にコピーされる（Ｑ→Ｊ）。このように、この遷移中、整列は同じままであり、スタートデータラン境界は最小サイズの適応メタグループ３９９２にマッピングされ、残りのデータは最大サイズの適応メタグループにマッピングされる。
【０１４５】
図４０は、非整列から完全整列への（Ｎ２Ｆ）遷移の例を示す。ホストからのデータラン４００２が受け取られて、データラン境界との整列なしで（非整列で）格納されている元のデータを更新するために使用される。この例では、元のデータは最大サイズのメタブロックに格納される。対照的に、更新されるメタグループは、データラン４００２のスタート部および終端部のデータ境界について最小サイズのヘッドメタグループ４００４およびテールメタグループ４００６を含む。データラン４００２の第１の部分的論理グループからのデータＡはシリアルバッファにバッファリングされる（Ａ→Ｋ）。同様に、データランの最後の部分的論理グループからのデータＤはシリアルバッファにバッファリングされる（Ｄ→Ｌ）。これは、データラン４００２の終端部のデータラン境界の位置に関してホストにより提供される情報に対する応答である。データＢは、最大サイズのメタグループとして格納される（Ｂ→Ｇ）。より大きなデータランについて、追加のデータは最大サイズの追加メタグループとして格納することができる。メタグループＧは最大サイズのメタグループに格納される。ヘッド、テール或いは最大サイズのメタグループに割り当てられない残りのデータＣはパッドメタグループに割り当てられる（Ｃ→Ｈ）。メタグループＨはこの例では最大サイズに及ばないメタブロックに直接格納されるが、他の例では始めにシリアルバッファに格納され、その後に最大サイズ未満のメタブロックにコピーされる。この例では、Ｃはテールパッドデータと見なされてよく、Ｈはテールパッドブロックと見なされる。更新されない元のメタグループ（Ｏ，Ｐ，Ｑ，Ｒ）内のデータは、再配置メタグループに（Ｏ→Ｓ，Ｒ→Ｔ）或いはヘッドメタグループおよびテールメタグループに（Ｐ→Ｅ，Ｑ→Ｊ）コピーされる。データのこれらの部分のコピーは、可能な場合には並列に行うことができる。例えば、再配置されたメタグループＳおよびＴへの部分ＯおよびＲのコピーを並列に行うことができ、ここでＯおよびＲは共同で１つの最大サイズのメタグループと同等またはそれ未満のデータを含む。部分ＰおよびＱのコピーは、他の元のメタグループからまたはシリアルバッファからの他のコピー操作と並列に行うことができる。データ部分Ｃが短い場合、データ部分Ｃはバッファリングされ、データ部分Ｅ，Ｆ，ＩおよびＪのプログラミングのような他のプログラミング操作と並列に、更新されるメタグループにコピーすることができる。
【０１４６】
図４１は、非整列から部分的整列への（Ｎ２Ｐ）遷移の例を示す。元のメタグループは、データラン４１１０のデータラン境界と整列していない。この例では、元のメタグループは最大サイズのメタグループであるけれども、これは非整列については必ずしもそうではない。更新されたメタグループは、データランと部分的に整列して形成される。図４０の場合のようにデータラン４１１０のスタート部のデータラン境界に最小サイズの更新されたメタグループ４１１２が割り当てられる。残りのメタグループは最大サイズのメタグループであり、データラン４１１０の終端部のデータラン境界は最小サイズのメタグループに割り当てられない。代わりに、この例では、データラン４１１０の終端部のデータラン境界は最大サイズのメタグループ４１１４に割り当てられる。元のメタグループは、更新されたメタグループに（Ｐ→Ｅ，Ｑ→Ｊ）或いは再配置されたメタグループに（Ｏ→Ｓ，Ｒ→Ｔ）コピーされる元のデータ（Ｏ，Ｐ，Ｑ，Ｒ）を含む。
【０１４７】
図４２は、非整列から部分的整列への（Ｎ２Ｐ）遷移の他の例を示す。元のメタブロックは、また、最大サイズのメタブロックである。図４２は、元のメタブロックに対応しない（非整列）データラン境界を有するホストからのデータラン４２２０を示す。データラン内のデータをデータ境界に部分的に整列させて格納するために、更新されたメタブロックが形成される。この例では、データラン４２２０のスタート部のデータラン境界に最小サイズの更新されたメタグループ４２２２が割り当てられる。他の更新されたメタグループのメタグループ境界は、元のメタグループのメタグループ境界と同じ位置に配置される。この例では、ヘッドメタグループと次のメタグループ境界との間に最大サイズ未満のメタグループＧが使用される。これは、ヘッドパッドメタグループと見なされ、これに格納されているデータはヘッドパッドデータと見なされる。ヘッドパッドメタグループは、直接に、またはシリアルフラッシュバッファにバッファリングされた後に、ヘッドパッドメタブロックに格納することができる。ヘッドパッドメタグループを直接格納するか或いはそれをバッファリングするかに関する決定は、（テールパッドデータに関して前に論じられたように）それが何らかのしきい値より大きいか或いは小さいかに基づくことができる。前と同様に、必要に応じて元のデータは再配置されたメタグループに（Ｏ→Ｓ）或いは更新されたメタグループに（Ｑ→Ｊ）コピーすることができる。
【０１４８】
図４３は、非整列から非整列への（Ｎ２Ｎ）遷移の例を示す。この例では、ホストからデータラン４３３０が受け取られ、これは、データランの境界と全く整列していない元のメタグループに格納されているデータを更新する。更新されたデータは、データランの境界と全く整列していない更新されるメタグループに格納される。この例では、元のメタグループと更新されたメタグループとの両方が最大サイズのメタグループだけを含んでいる。この方式は、適応メタブロックを使用しないシステム（メタブロックのサイズが固定されているシステム）で使用されてもよい。この例では、シリアルフラッシュバッファは使用されない。元のデータ（Ｐ，Ｑ）は、更新されるメタブロックにコピーされる（Ｐ→Ｅ，Ｑ→Ｊ）。このように、大量の元のデータが更新されるメタグループに格納され、その後のデータランが同じデータラン境界位置を持って受け取られたならば、このデータは再びコピーされる。
【０１４９】
データラン更新管理
ファイルは、ホストシステム内で作られたか、または外部情報源からホストシステムに受け取られたデータのセットであり、ホストシステム内で論理的セクタアドレスにマッピングされる。連続する論理的セクタアドレスのセットはデータランと称される。データランは、１つ以上のファイルまたは１つのファイルの複数の部分の格納のためにホストにより割り当てられた論理的に連続するセクタのセットと見なされてよく、データランは、論理アドレス空間の前に割り当てられた複数の部分の間に広がる。ホストは、いろいろなデータランへの書込み操作をインターリーブすることができる。通常、何時でも限られた数の開いたデータランが許容されるので、データランが必要に応じて開閉される。データランの中のセクタは、開いているバッファに、またはそのデータランと関連付けられている更新ブロックに、書き込まむことができる。データランからのデータを受け取って格納するには、データランと、データを格納するために使われる（バッファおよび更新メタブロックを含む）メモリ構造との管理が必要である。図４４は、構造の幾つかと、これらに関して実行可能な操作とを示す。
【０１５０】
データランを開く操作は、現存する１つのデータラン内の最後のセクタと連続していなく、かつ１つの現存するデータラン内の最後のセクタから許容される順次アドレスジャンプの範囲内にない１つのセクタが受け取られたときに、行うことができる。データランは、最も長い間更新されていない（ＬＲＵ）データランであり、許容される最大個数のデータランが存在して、新しいデータランが開かれなければならないときに、閉じられることになる。また、データランの中の１つのセクタが更新され、更新がカオス的であると見なされる原因となるときにも、閉じられる。このようなカオス的更新は、一般に、米国特許出願第１０／７５０，１５５号（特許文献２３）に記載されている方法のような他の方法を用いて処理される。
【０１５１】
バッファは、データランからの順次データを書き込むためのシリアルフラッシュバッファの部分である。バッファは、シリアルフラッシュバッファ内で物理的に連続していなくてもよい。複数の不連続なバッファがあれば、複数のバッファへのインターリーブな書き込みを容易にすることができる。データランが開かれるとき、データランの第１の論理グループが不完全であれば、バッファが開かれることになる。バッファは、データランの最後の論理グループについて第１のセクタが受け取られたときにも、開かれることになる。バッファは、パッドデータ（ヘッドパッド或いはテールパッド）のためにも、そのパッドデータが何らかの所定量に及ばない場合に、開かれることになる。バッファは、これに書き込まれるべきデータが完全であるときに、閉じられることになる。閉じられたバッファは、そのデータの全てを更新ブロックに書き込むことによってコピーされる。コピーは、バッファがシリアルフラッシュバッファの終端部に存する次の使用可能なバッファのうちの１つであるときに、行うことができる。通常、このようなコピー操作は、他のバッファのまたは元のデータの他のコピー操作と並列に、行われる。
【０１５２】
更新メタブロックは、ホストからのまたはバッファからの何らかの更新されたデータが書き込まれる適応メタブロックである。バッファに送られない、それについての不完全な更新メタブロックが存在しないデータが受け取られたときに、更新メタブロックが割り当てられる。更新メタブロックは、データがバッファからコピーされるときにも割り当てられる。更新メタブロックのサイズは、格納されるべきデータの量による。更新メタブロックは、最小サイズのメタブロック、短縮されたサイズのメタブロック或いは最大サイズのメタブロックである。例えば、最小サイズのメタブロックはデータランのスタート部（ヘッド）および終端部（テール）のために使用され、短縮されたサイズのメタブロックはパッドデータ（ヘッドパッドまたはテールパッド）のために使用され、最大サイズのメタブロックはデータランの他の全てのデータのために使用されてもよい。更新ブロックは、最後のセクタがホスト、バッファまたは元のブロックからのデータで満たされたときに、完成したと見なされる。従って、完成は、バッファからのコピー操作の結果として或いは元のブロックからのコピーの結果として生じ、データランの閉鎖によりトリガされる。
【０１５３】
元のメタブロックは適応メタブロックであり、ホストからの更新されたセクタによって陳腐にされた１つ以上のセクタを含む。メタブロックは、その中のセクタが更新されたデータのセクタの受け取りによって陳腐にされたとき、開いている元のメタブロックと見なされる。元のメタブロックは、その中のそれ以上のセクタが、任意の開いているデータランへのホストによるさらなる書き込みによって陳腐にされないときに、完成していると見なされてよい。データは、完成した元のメタブロックから再配置メタブロックにコピーすることができる。完成している元のメタブロックは、その中の全ての有効なセクタがコピーされたときには、完全に陳腐な元のメタブロックと見なされる。完全に陳腐な元のメタブロックは消去されることになる。
【０１５４】
再配置メタブロックは、その中に元のメタブロックからデータの連続する論理グループをコピーすることができる適応メタブロックである。データが元のメタブロックからコピーされることになっていてヘッドメタブロックまたはテールメタブロックの一部ではないときに、再配置メタブロックが割り当てられることになる。再配置メタブロックは、その最後のセクタ位置が書き込まれたときに、完成していると見なされる。再配置メタブロックは、最小サイズまたは短縮されたサイズのメタブロックである。
【０１５５】
図４５は、本発明の実施形態に従ってデータ境界整列を伴ってホストから受け取られたセクタを格納するためのフローチャートを示す。この例はデータのセクタが格納されることを示しているが、データの他の単位も使用可能である。最初に、セクタの格納が開いているデータランへのカオス的更新を必要とするか否かが判定される（４５５０）。カオス的更新は、セクタが非順次的に更新される更新であり、米国特許出願第１０／７５０，１５５号（特許文献２３）にさらに記載され、この出願は、その全体が本願明細書において参照により援用されている。開いているデータランへのカオス的更新は、データ境界整列を伴う格納の代わりに実行されてもよい。従って、カオス的更新は、ここでは詳しく説明しない。セクタがカオス的更新を必要としないと判定されたならば、受け取られたセクタが開いているデータランに連続するか否かが判定される（４５５２）。
【０１５６】
受け取られたセクタが開いているデータランに連続するものではなくて、開いているデータランの数が所定の最大値より少なければ（４５５４）、新しいデータランが開かれる（４５５６）。開いているデータランの数が所定の最大値より少なくなければ、新しいデータランを開く（４５５６）前に、（後に詳述するように）１つのデータランを閉じなければならない（４５５８）。新しいデータランが開かれた後、論理グループ境界からデータランのスタート部までにオフセットがあるか否かが判定される（４５６０）。オフセットがあればバッファが開かれ（４５６２）、バッファのサイズは、ヘッドデータ、すなわちデータランの第１の論理グループ内の部分、に等しい。その後、このバッファの終端部に達するまでこのバッファにセクタが書き込まれ、そしてバッファは閉じられる。
【０１５７】
受け取られるセクタが開いているデータランに連続し、またデータランのために開いているバッファが存在するならば（４５６４）、セクタはバッファに書き込まれる（４５６６）。データランのために開いているバッファがない（４５６４）が、データランのために不完全なメタブロックが存在するならば（４５６８）、後述するようにセクタはその不完全なメタブロックに書き込まれる（４５７０）。データランのために開いているバッファがなく、また不完全なメタブロックが存在しなければ、受け取られたセクタがヘッドパッドデータであるか否かが判定される（４５７２）。また、論理グループ境界からのオフセットなしで（４５６０）新しいデータランが開かれる場合、この判定が行われる。セクタがヘッドパッドデータである場合、データの量（セクタの数）が、バッファリングのための最大のパッド長さである所定値（ｍａｘｐａｄ）と比較される（４５７４）。セクタの数がｍａｘｐａｄより大きくなければ、ヘッドパッドデータと同じサイズのバッファが開かれる（４５７６）。セクタの数がｍａｘｐａｄより大きければ、短縮されたメタブロックが割り当てられ（４５７８）、後にセクタはこの短縮されたメタブロックに書き込まれる（４５７０）。
【０１５８】
セクタがヘッドパッドデータではないと判定されたならば（４５７２）、次に、セクタがテールパッドであるのか或いはテールデータであるのかが判定される（４５８０）。それらがテールパッド或いはテールデータでなければ、最大サイズのメタブロックが割り当てられ（４５８２）、セクタは後に最大サイズのメタブロックに書き込まれる（４５７０）。これは、ヘッドでもなくテールデータでもないデータについて一種のデフォルト条件である。従って、データランの中央部のデータは一般に最大の並列性を用いるために最大サイズのメタブロックに書き込まれる。セクタがテールパッドまたはテールデータを含んでいれば、セクタが（データランの最後の論理グループからの）テールデータであるか否かが判定される（４５８４）。それらが最後の論理グループからのものであれば、バッファが開かれ（４５８６）、バッファのサイズはテールデータに等しい（データランからの、最後の論理グループ内のデータに等しい）。その後、セクタはバッファに書き込まれる（４５６６）。セクタが最後の論理グループからのものでなければ、セクタはテールパッドデータであり、テールパッドの長さが所定のサイズ（ｍａｘｐａｄ）より大きいか否かが判定される（４５８８）。セクタの数がｍａｘｐａｄより多ければ、短縮されたサイズのメタブロックが割り当てられ（４５７８）、その後にセクタはメタブロックに書き込まれる（４５７０）。テールパッドがｍａｘｐａｄより大きくなければ（４５８８）、テールパッドに等しいバッファが開かれる（４５９０）。セクタは、その後、このバッファに書き込まれる（４５６６）。
【０１５９】
図４６は、１つ以上のメタブロックにセクタを書き込むためのフローチャートを示す。本願のこのフローチャートおよび他のフローチャートにおいて、論理の流れはフローチャートの底部に向かい、判断ボックスは、ボックスの下に示された肯定結果と、ボックスの一方の側に示されている否定結果とを有する。セクタのグループの格納のために割り当てられたメタブロックが短縮されたまたは最小サイズのメタブロックであるかが始めに判定される（４６０１）。短縮された或いは最小サイズのメタブロックが割り当てられていなければ（最大サイズのメタブロックが割り当てられていれば）、書き込まれるべきセクタは、割り当てられたメタブロックに並列に書き込まれる（４６０３）。その後、メタブロックが満杯か否かが判定される（４６０５）。メタブロックが満杯であれば、それは“完全”と称される（４６０７）。その後、データランまたはホストによりデータランに書き込まれるさらなるデータに対応するデータの全てが元のメタブロックにおいて陳腐になっているか否かが判定され（４６０９）、そうであるならば、元のブロックは完成していると見なされる（４６１１）。短縮されたまたは最小サイズのメタブロックが書き込まれるのであれば（４６０１）、バッファが現在コピーされていなければ（４６１２）、コピーされるべく使用可能な閉じているバッファが特定され（４６１３）、これらのバッファに関連付けられている元のデータが特定され（４６１５）、１つ以上の短縮されたまたは最小サイズのメタブロックが割り当てられる（４６１７）。元のデータが現在再配置されていなければ（４６１９）、完全な元のメタブロックから再配置されるべきデータが特定され（４６２１）、短縮されたまたは最小サイズのメタブロックが割り当てられる（４６２３）。その後、バッファからコピーされる或いは短縮されたメタブロックに再配置されるセクタの書き込みと並列の、セクタのグループに割り当てられたメタブロックへのセクタの書き込みが前のように実行される。
【０１６０】
図４７は、データランを閉じるためのフローチャートを示す。最も長い間使用されていない（ＬＲＵ）データランが始めに特定される（４７３１）。このデータランのための開いているバッファが存在するならば（４７３３）、それは閉じられ（４７３５）、データランのための不完全なメタブロックが存在するならば（４７３７）、その不完全なメタブロックが完全になるまで（４７４１）元のメタブロックまたはバッファからデータがコピーされる（４７３９）。部分的に陳腐な元のメタブロックが存在するならば（４７４３）（完全な元のメタブロック）短縮されたサイズのメタブロックが再配置されたメタブロックとして割り当てられ（４７４５）、元のブロックが完全に陳腐になるまで（４７４９）有効なセクタがコピーされる（４７４７）。その後、データランは閉じられていると称される（４７５１）。
【０１６１】
本発明を種々の代表的な実施形態に関して説明してきたが、本発明が添付の特許請求の範囲の全範囲内においてその権利が保護されるべきことが理解されよう。

【特許請求の範囲】
【請求項１】
別々にプログラム可能なプレーンに配置された複数のマルチセクタ消去ブロックを含むメモリアレイにデータを格納する方法であって、
前記メモリアレイに格納されるべきデータから複数の論理グループを形成するステップであって、論理グループが前記メモリアレイの１消去ブロックに格納されるデータのセクタの数に等しい数のデータのセクタを含むステップと、
複数の論理グループから適応論理ブロックを形成するステップと、
複数のマルチセクタ消去ブロックから適応メタブロックを形成するステップと、
複数のマルチセクタ消去ブロックの各々が複数の論理グループの各々の部分を含むように前記適応論理ブロックを前記メモリアレイの前記適応メタブロックに格納するステップと、
前記適応論理ブロックの論理グループについてアドレス情報を個別に記録するステップと、
を含む方法。

【図１Ａ】

【図１Ｂ】

【図２】

【図３】

【図４】

【図５】

【図６】

【図７】

【図８】

【図９Ａ】

【図９Ｂ】

【図１０】

【図１１】

【図１２Ａ】

【図１２Ｂ】

【図１２Ｃ】

【図１３】

【図１４】

【図１５Ａ】

【図１５Ｂ】

【図１５Ｃ】

【図１５Ｄ】

【図１５Ｅ】

【図１５Ｆ】

【図１６】

【図１７】

【図１８Ａ】

【図１８Ｂ】

【図１８Ｃ】

【図１８Ｄ】

【図１９】

【図２０】

【図２１】

【図２２】

【図２３】

【図２４】

【図２５】

【図２６】

【図２７】

【図２８Ａ】

【図２８Ｂ】

【図２８Ｃ】

【図２９Ａ】

【図２９Ｂ】

【図２９Ｃ】

【図２９Ｄ】

【図２９Ｅ】

【図３０Ａ】

【図３０Ｂ】

【図３０Ｃ】

【図３０Ｄ】

【図３１】

【図３２】

【図３３Ａ】

【図３３Ｂ】

【図３４】

【図３５Ａ】

【図３５Ｂ】

【図３５Ｃ】

【図３５Ｄ】

【図３５Ｅ】

【図３６】

【図３７】

【図３８】

【図３９】

【図４０】

【図４１】

【図４２】

【図４３】

【図４４】

【図４５】

【図４５Ａ】

【図４５Ｂ】

【図４６】

【図４７】

【公開番号】特開２０１２−９９１３９（Ｐ２０１２−９９１３９Ａ）
【公開日】平成２４年５月２４日（２０１２．５．２４）
【国際特許分類】
【出願番号】特願２０１２−５２１７（Ｐ２０１２−５２１７）
【出願日】平成２４年１月１３日（２０１２．１．１３）
【分割の表示】特願２００６−５４７３６４（Ｐ２００６−５４７３６４）の分割
【原出願日】平成１６年１２月２２日（２００４．１２．２２）
【出願人】（５０６１９７９０１）サンディスク　コーポレイション (175)
【Ｆターム（参考）】