(57)【要約】【課題】論理アドレスと、アドレス範囲とを含む要求を受け取るメディア・コントローラを提供する。【解決手段】この要求に応答して、メディア・コントローラは、受け取られた要求が無効にする要求であるかどうかを判定する。受け取られた要求タイプが無効にする要求である場合、メディア・コントローラは、マップを使用して、その論理アドレスおよび範囲に関連付けられたマップの１つまたは複数のエントリを特定する。これらのマップ・エントリのそれぞれに関連付けられたマップの中の標識が、これらのマップ・エントリが無効にされるべきことを示すように設定される。メディア・コントローラは、無効にする要求が完了したという確認応答をホスト・デバイスに対して行い、メディア・コントローラのアイドル・モードにおいて、無効にされるべきマップ・エントリに基づいて空きスペース・カウントを更新する。無効にされたマップ・エントリに関連付けられた物理アドレスが、ホスト・デバイスからのその後の要求に関して再使用されるように利用可能にされる。【選択図】図１
2014179084.tif 000002
【特許請求の範囲】
【請求項１】
ソリッドステート・メディアおよびホスト・デバイスと通信状態にあるメディア・コントローラによって受け取られたホスト要求を処理する方法であって、
前記メディア・コントローラにより、前記ホスト・デバイスからの要求を受け取り、前記要求は、少なくとも１つの論理アドレスと、アドレス範囲とを含むこと、
前記要求を受け取ったことに応答して、
前記受け取られた要求が無効にする要求であるかどうかを判定し、前記受け取られた要求タイプが無効にする要求である場合、
前記メディア・コントローラのマップを使用して、前記ソリッドステート・メディアの前記少なくとも１つの論理アドレスおよび前記アドレス範囲に関連付けられた前記マップの１つまたは複数のエントリを特定すること、
前記マップの中で、前記マップ・エントリのそれぞれに関連付けられた標識に印を付け、前記標識は、前記１つまたは複数のマップ・エントリが無効にされるべきことを示すこと、
前記ホスト・デバイスに対して、前記無効にする要求が完了したという確認応答を行うこと、
前記メディア・コントローラのアイドル・モードにおいて、無効にされるべき前記１つまたは複数のマップ・エントリに基づいて前記メディア・コントローラの空きスペース・カウントを更新すること、および
前記無効にされたマップ・エントリに関連付けられた物理アドレスを、前記ホスト・デバイスからのその後の要求に関して再使用されるように利用可能にすることを備える方法。
【請求項２】
前記マップは、第１レベル・マップと、第２レベル・マップとを備えるマルチレベル・マップである方法であって、
複数の第２レベル・マップ・ページの複数のエントリのそれぞれを、前記ソリッドステート・メディアの物理アドレスに関連付けること、および
前記第１レベル・マップの複数のエントリのそれぞれを或る第２レベル・マップ・ページに関連付け、その結果、前記少なくとも１つの論理アドレス、および前記アドレス範囲を前記第２レベル・マップ・エントリのうちの少なくとも１つに関連付けることをさらに備える、請求項１に記載の方法。
【請求項３】
各第２レベル・マップ・エントリは、有効指示を備え、
各第１レベル・マップ・エントリは、前記第２レベル・マップ・ページのうちの対応する１ページのアドレスと、前記第１レベル・マップ・エントリに関連付けられた前記第２レベル・マップの１つまたは複数のエントリに対応する有効指示と、前記第２レベル・マップのエントリが無効であるが、書き込むのに利用できない場合にそのことを示すように構成された処理されるべき（ＴＢＰ）標識とを備える方法であって、
前記要求の前記アドレス範囲内に完全に含まれる前記第２レベル・マップ・ページのうちのページに関連付けられた前記第１レベル・マップの中の前記ＴＢＰ標識のうちの特定のＴＢＰ標識を設定することによって、前記第２レベル・マップのエントリを無効にすることをさらに備える、請求項２に記載の方法。
【請求項４】
前記要求の前記アドレス範囲内に部分的にだけ含まれる前記第２レベル・マップ・ページのうちのページのエントリを直接にトリミングすることによって、前記第２レベル・マップのエントリを無効にすることをさらに備える、請求項３に記載の方法。
【請求項５】
前記ＴＢＰ標識が所与の第２レベル・マップに関して設定されている場合、前記所与の第２レベル・マップに関する後続の無効にする要求が受け取られるまで、前記所与の第２レベル・マップに関する前記無効にする要求を処理することを遅延させて、その結果、前記無効にする要求に関する処理時間を短くし、前記所与の第２レベル・マップを更新する前記ソリッドステート・メディアに対する書き込み動作を少なくすることをさらに備える、請求項３に記載の方法。
【請求項６】
前記第２レベル・マップの前記無効にされたエントリのそれぞれを、前記ホスト・デバイスからのその後の要求に関して再使用されるように利用可能にする前記ステップは、
設定されている場合、前記関連付けられたＴＢＰ標識をクリアすること、および
設定されている場合、関連付けられた有効標識をクリアすることを備える、請求項３に記載の方法。
【請求項７】
前記メディア・コントローラのマップ・メモリの中に前記第１レベル・マップを格納すること、
前記ソリッドステート・メディアの中に前記第２レベル・マップ・ページのすべてを格納すること、および
前記メディア・コントローラの制御プロセッサに結合されたマップ・キャッシュの中に前記第２レベル・マップ・ページの少なくともサブセットを一時的に格納することをさらに備える、請求項３に記載の方法。
【請求項８】
前記メディア・コントローラの前記空きスペース・カウントは、複数のエントリを有するブロック使用されるスペース・テーブルを備える方法であって、
前記ブロック使用されるスペース・テーブルの各エントリを前記ソリッドステート・メディアの複数の物理領域のうちの１つに関連付けることをさらに備える、請求項１に記載の方法。
【請求項９】
前記無効にする要求は、シリアル・アドバンスト・テクノロジー・アタッチメント（ＳＡＴＡ）ＴＲＩＭコマンド、スモール・コンピュータ・システム・インターフェース（ＳＣＳＩ）ＵＮＭＡＰコマンド、マルチメディアカード（ＭＭＣ）ＥＲＡＳＥコマンド、およびセキュア・デジタル（ＳＤ）カードＥＲＡＳＥコマンドのうちの１つである、請求項１に記載の方法。
【請求項１０】
各第１レベル・マップ・エントリは、前記要求の前記範囲内に含まれる前記関連付けられた第２レベル・マップのいくつかの部分を追跡するように構成された少なくとも１つのＴＲＩＭアドレス範囲標識を備える請求項３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はソリッドステート・メディアにおけるマルチレベル・マッピングに関する。
【０００２】
（関連出願の相互参照）
本出願は、参照によって教示の全体が本明細書に組み込まれている、２０１２年８月８日に出願した国際特許出願ＰＣＴ／ＵＳ２０１２／０４９９０５号の一部継続出願であり、ＰＣＴ／ＵＳ２０１２／０４９９０５号の出願日の利益を主張するものである。
【０００３】
本出願は、参照によって教示の全体が本明細書に組み込まれている、２０１３年３月１４日に出願した米国特許仮出願第６１／７８３，５５５号の出願日の利益を主張するものである。
【０００４】
本出願の主題は、参照によって教示の全体が本明細書に組み込まれている、２０１２年５月４日に出願した米国特許出願第１３／４６４，４３３号、２０１２年８月４日に出願した米国特許出願第１３／５６７，０２５号、２０１２年８月３１日に出願した米国特許出願第１３／６００，４６４号、２０１２年１２月２８日に出願した米国特許出願第１３／７２９，９６６号、および２０１３年１月２３日に出願した米国特許出願第１３／７４８，２６０号と関係する。
【背景技術】
【０００５】
フラッシュ・メモリは、或る特定のタイプの電気的に消去可能なプログラマブル読み出し専用メモリ（ＥＥＰＲＯＭ）である不揮発性メモリ（ＮＶＭ）である。１つの一般的に使用されているタイプのフラッシュ・メモリ技術が、ＮＡＮＤフラッシュ・メモリである。ＮＡＮＤフラッシュ・メモリは、１セル当たり要求するチップ面積が小さく、通常、１つまたは複数のバンクまたはプレーンに分割される。各バンクは、ブロックに分割され、各ブロックは、ページに分割される。各ページは、ユーザ・データまたは誤り訂正コード（ＥＣＣ）情報、あるいはユーザ・データとＥＣＣ情報の両方を格納するための数バイトを含む。
【０００６】
ＮＡＮＤデバイスに関して以下の３つの基本的な動作、すなわち、読み出し、書き込み、および消去が存在する。読み出し動作および書き込み動作は、ページごとに実行される。ページ・サイズは、一般に、２Ｎバイトのユーザ・データ（加えて、ＥＣＣ情報のためのさらなる数バイト）であり、ただし、Ｎは、整数であり、典型的なユーザ・データ・ページ・サイズは、例えば、１ページ当たり２，０４８バイト（２ＫＢ）、４，０９６バイト（４ＫＢ）、８，１９２バイト（８ＫＢ）、またはそれ以上である。「読み出し単位」は、最少量のデータ、およびＮＶＭから読み取られ、ＥＣＣによって訂正されることが可能な対応するＥＣＣ情報であり、通常、４Ｋビットから３２Ｋビットまでの範囲内であることが可能である（例えば、一般に、１ページ当たり整数の読み出し単位が存在する）。ページは、通常、ブロックとして構成され、消去動作は、ブロックごとに実行される。典型的なブロック・サイズは、例えば、１ブロック当たり６４ページ、１２８ページ、またはそれ以上である。ページは、通常、ブロック内の下位のアドレスから上位のアドレスに向って順次に書き込まれなければならない。より下位のアドレスには、そのブロックが消去されるまで再書き込みすることができない。各ページに関連付けられているのが、ＥＣＣ情報および／またはメモリ管理のために使用される他のメタデータの格納のために一般に使用される予備の領域（通常、１００〜６４０バイト）である。ＥＣＣ情報は、一般に、ページの中に格納されたユーザ・データの誤りを検出し、訂正するのに使用され、メタデータは、物理アドレスに論理アドレスをマップするため、および物理アドレスから論理アドレスにマップするために使用されることが可能である。複数のバンクを有するＮＡＮＤフラッシュ・チップにおいて、各バンクからの複数のページが実質的に並行にアクセスされることを可能にするマルチバンク動作がサポートされることが可能である。
【０００７】
ＮＡＮＤフラッシュ・メモリは、フローティング・ゲート・トランジスタから作られたメモリ・セルのアレイの中に情報を格納する。これらのトランジスタは、電荷とも呼ばれる電圧レベルを、外部電源が供給されることなしに、数ヶ月または数年のオーダの長期間にわたって保つ。シングル・レベル・セル（ＳＬＣ）フラッシュ・メモリにおいて、各セルは、１ビットの情報を格納する。マルチレベル・セル（ＭＬＣ）フラッシュ・メモリにおいて、各セルは、フラッシュ・メモリの複数のセルのフローティング・ゲートに印加すべき複数のレベルの電荷の間で選択を行うことによって、１セル当たり複数のビットを格納することができる。ＭＬＣ  ＮＡＮＤフラッシュ・メモリは、同一の数のトランジスタを使用して、より多くのビットが格納されることを可能にするようにシリアルで結合されたトランジスタ構成で１セル当たり複数の電圧レベルを使用する。このため、個々に考慮すると、各セルは、そのセルの中に格納された論理ビット値（複数可）に対応する特定のプログラミングされた電荷を有し（例えば、ＳＬＣフラッシュの場合、０または１、ＭＬＣフラッシュの場合、００、０１、１０、１１）、それらのセルは、各セルに関する１つまたは複数のしきい値電圧に基づいて読み取られる。しかし、１セル当たりのビット数を増やすことは、セル間干渉および保持ノイズを増加させて、読み出し誤りの尤度を高め、このため、システムのビット誤り率（ＢＥＲ）を高める。さらに、各セルの読み出ししきい値電圧は、例えば、読み出しディスターブ、書き込みディスターブ、保持損失、セルの経年変化、ならびにプロセス、電圧、および温度（ＰＶＴ）の変動に起因して、ＮＶＭの動作時間につれて変化して、やはり、ＢＥＲを高める。
【０００８】
前述したとおり、通常のＮＶＭは、新たなデータがブロックに書き込まれることが可能であるにはまず、そのブロックが消去されることを要求する。このため、１つまたは複数のＮＶＭチップを使用するソリッドステート・ディスク（ＳＳＤ）などのＮＶＭシステムは、通常、「陳腐な」、つまり、古くなったデータを消去して、実現されるフラッシュ・メモリ容量を小さくする、大部分が古くなったデータでフラッシュ・メモリが一杯になることを防止する「ガーベジ・コレクション」プロセスを周期的に開始する。しかし、ＮＶＭブロックは、デバイス障害が生じるまで、限られた回数しか消去することができない。例えば、ＳＬＣフラッシュは、約１００，０００回しか消去できない可能性があり、ＭＬＣフラッシュは、約１０，０００回しか消去できない可能性がある。したがって、ＮＶＭの動作寿命につれて（例えば、ＮＡＮＤフラッシュの場合、定格のプログラミング／消去（Ｐ／Ｅ）サイクル数につれて）、ＮＶＭは消耗し、フラッシュ・メモリのブロックは、障害を生じて、使用不能になる。ＮＶＭにおけるブロック障害は、ハードディスク・ドライブ（ＨＤＤ）におけるセクタ障害に類似する。通常のＮＶＭシステムは、ＮＶＭのすべてのブロックにわたって可能な限り均一にＰ／Ｅサイクルを分散させる消耗平準化（ｗｅａｒ−ｌｅｖｅｌｌｉｎｇ）を実行することも可能である。このため、ＮＶＭシステムの寿命にわたって、不良なブロックの数が増加し、および／またはシステム・データ要件（例えば、論理−物理変換テーブル、ログ、メタデータ、ＥＣＣなど）のために使用されるストレージの量が増加するにつれ、全体的なストレージ容量が小さくなる可能性がある。このため、ガーベジ・コレクション・プロセス中にＮＶＭに書き込まれるデータの量を減らすことが重要であり得る。
【０００９】
ガーベジ・コレクション・プロセス中、依然として有効であるブロック内のユーザ・データが、背景プロセスにおいて記憶媒体上の新たなロケーションに移動される。「有効な」ユーザ・データは、ホスト・デバイスがこのデータをもはや使用していない場合でも、少なくとも１回、書き込まれたことのある任意のアドレスである可能性がある。ガーベジ・コレクション中に再書き込みされる「有効」ではあるが、もはや必要とされないデータの量を減らすのに、いくつかのストレージ・プロトコルは、ＮＶＭが、以前に保存されたデータのブロックを不要または無効と指定できるようにして、それらのブロックがガーベジ・コレクション中に移動されないようにし、それらのブロックが新たなデータを格納するのに利用可能にされ得るようにするコマンドをサポートする。そのようなコマンドの例が、ＳＡＴＡ  ＴＲＩＭ（データ・セット管理）コマンド、ＳＣＳＩ  ＵＮＭＡＰコマンド、マルチメディアカード（ＭｕｌｔｉＭｅｄｉａＣａｒｄ）（ＭＭＣ）ＥＲＡＳＥコマンド、およびセキュア・デジタル（ＳＤ）カードＥＲＡＳＥコマンドである。一般に、そのようなコマンドは、完全にトリミングされたＮＶＭが、同一のタイプの新規に製造された（すなわち、空の）ＮＶＭの性能に近い性能を有するようにＮＶＭ性能を向上させる。しかし、多数のブロックに関してこれらのコマンドを一度に実行することは、時間がかかり、ＮＶＭの動作効率を低下させる可能性がある。
【発明の概要】
【課題を解決するための手段】
【００１０】
この概要は、詳細な説明において後段でさらに説明される選定された概念を、簡略化された形態で概説するために与えられる。この概要は、主張される主題の重要な特徴、または不可欠な特徴を特定することは意図しておらず、主張される主題の範囲を限定するのに使用されることも意図していない。
【００１１】
説明される実施形態は、ソリッドステート・メディアのためのメディア・コントローラを提供する。このメディア・コントローラは、少なくとも１つの論理アドレスと、アドレス範囲とを含む要求をホスト・デバイスから受け取る制御プロセッサを含む。この要求に応答して、制御プロセッサは、受け取られた要求が無効にする要求（ｉｎｖａｌｉｄａｔｉｎｇ  ｒｅｑｕｅｓｔ）であるかどうかを判定する。受け取られた要求タイプが無効にする要求である場合、制御プロセッサは、メディア・コントローラのマップを使用して、その論理アドレスおよび範囲に関連付けられたマップの１つまたは複数のエントリを特定する。これらのマップ・エントリのそれぞれに関連付けられたマップの中の標識が、これらのマップ・エントリが無効にされるべきことを示すように設定される。制御プロセッサは、無効にする要求が完了したという確認応答をホスト・デバイスに対して行い、メディア・コントローラのアイドル・モードにおいて、無効にされるべきマップ・エントリに基づいて空きスペース・カウントを更新する。無効にされたマップ・エントリに関連付けられた物理アドレスが、ホスト・デバイスからのその後の要求に関して再使用されるように利用可能にされる。
説明される実施形態の他の態様、特徴、および利点が、後段の詳細な説明、添付の特許請求の範囲、および添付の図面から、より完全に明白となる。図面では、同様の参照符号は、同様の、または同一の要素を識別する。
【図面の簡単な説明】
【００１２】
【図１】例示的な実施形態によるフラッシュ・メモリ・ストレージ・システムを示すブロック図である。
【図２】単一の標準のフラッシュ・メモリ・セルを示す例示的な機能ブロック図である。
【図３】例示的な実施形態による例示的なＮＡＮＤ  ＭＬＣフラッシュ・メモリ・セルを示す図である。
【図４】図１のフラッシュ・メモリ・ストレージ・システムのフラッシュ・メモリの例示的な構成を示すブロック図である。
【図５】図１のフラッシュ・メモリ・ストレージ・システムの論理ブロック図番号（ＬＢＡ）の論理ページ番号（ＬＰＮ）部分の例示的なマッピングを示すブロック図である。
【図６】図１のフラッシュ・メモリ・ストレージ・システムの例示的な２レベル・マッピング構造を示すブロック図である。
【図７】図１のフラッシュ・メモリ・ストレージ・システムによって使用される例示的なマップ・ページ・ヘッダを示すブロック図である。
【図８】図１のフラッシュ・メモリ・ストレージ・システムによって使用されるメガＴＲＩＭ動作を示す例示的な流れ図である。
【発明を実施するための形態】
【００１３】
説明される実施形態は、ソリッドステート・メディアに関するメディア・コントローラを提供する。このメディア・コントローラは、少なくとも１つの論理アドレスと、アドレス範囲とを含む要求をホスト・デバイスから受け取る制御プロセッサを含む。この要求に応答して、制御プロセッサは、受け取られた要求が無効にする要求であるかどうかを判定する。受け取られた要求タイプが無効にする要求である場合、制御プロセッサは、メディア・コントローラのマップを使用して、その論理アドレスおよび範囲に関連付けられたマップの１つまたは複数のエントリを特定する。これらのマップ・エントリのそれぞれに関連付けられたマップの中の標識が、これらのマップ・エントリが無効にされるべきことを示すように設定される。制御プロセッサは、無効にする要求が完了したという確認応答をホスト・デバイスに対して行い、メディア・コントローラのアイドル・モードにおいて、無効にされるべきマップ・エントリに基づいて空きスペース・カウントを更新する。無効にされたマップ・エントリに関連付けられた物理アドレスが、ホスト・デバイスからのその後の要求に関して再使用されるように利用可能にされる。
【００１４】
表１が、説明される実施形態を理解する助けとして本明細書全体で使用される頭字語のリストを定義する。
【表１】
2014179084.tif 000003
【００１５】
図１は、不揮発性メモリ（ＮＶＭ）ストレージ・システム１００のブロック図を示す。ＮＶＭストレージ・システム１００は、メディア・コントローラ１２０に結合されたメディア１１０を含む。メディア１１０は、ＮＡＮＤフラッシュ・ソリッドステート・ディスク（ＳＳＤ）として、ハードディスク・ドライブ（ＨＤＤ）などの磁気記憶媒体として、またはハイブリッド・ソリッドステート−磁気システムとして実装されることが可能である。図１には示されないものの、メディア１１０は、複数のフラッシュ・チップなどの１つまたは複数の物理メモリ（例えば、不揮発性メモリ、ＮＶＭ）を、通常、含むことが可能である。図１に示されるとおり、メディア１１０とメディア・コントローラ１２０とがひとまとまりとしてＳＳＤ１０１である。メディア・コントローラ１２０は、ソリッドステート・コントローラ１３０と、制御プロセッサ１４０と、バッファ１５０と、入出力インターフェース１６０とを含む。メディア・コントローラ１２０は、メディア１１０と、通信リンク１７０に結合されたホスト・デバイス１８０との間のデータの転送を制御する。メディア・コントローラ１２０は、システム・オン・チップ（ＳｏＣ）として、または他の集積回路（ＩＣ）として実装されることが可能である。ソリッドステート・コントローラ１３０は、メディア１１０内のメモリ・ロケーションにアクセスするのに使用されることが可能であり、通常、低レベルのデバイス固有の動作を実装して、メディア１１０とのインターフェースをとる。バッファ１５０は、制御プロセッサ１４０のためのキャッシュの役割、および／またはソリッドステート・メディア１１０とホスト・デバイス１８０との間の動作のための読み出し／書き込みバッファの役割をするように使用されるＲＡＭバッファであることが可能である。例えば、データが、一般に、入出力インターフェース１６０とリンク１７０とを介した、ソリッドステート・メディア１１０とホスト・デバイス１８０との間の転送中にバッファ１５０の中に一時的に格納されることが可能である。バッファ１５０は、通信リンク１７０のデータ転送サイズとメディア１１０の格納単位サイズ（例えば、読み出し単位サイズ、ページ・サイズ、セクタ・サイズ、またはマップされた単位サイズ）との差を勘案するようにデータをグループ化する、または分割するのに使用されることが可能である。バッファ１５０は、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）として、またはメディア・コントローラ１２０内部の組み込みダイナミック・ランダム・アクセス・メモリ（ｅＤＲＡＭ）として実装されることが可能であるが、バッファ１５０は、ダブル・データ・レート（例えば、ＤＤＲ−３）ＤＲＡＭとして通常、実装されることが可能な、メディア・コントローラ１２０外部のメモリ（図示せず）を含むことも可能である。
【００１６】
制御プロセッサ１４０が、ソリッドステート・コントローラ１３０と通信して、メディア１１０の中のデータに対するデータ・アクセス（例えば、読み出し動作または書き込み動作）を制御する。制御プロセッサ１４０は、１つまたは複数のＰｅｎｔｉｕｍ（登録商標）プロセッサ、Ｐｏｗｅｒ  ＰＣ（登録商標）プロセッサ、Ｔｅｎｓｉｌｉｃａ（登録商標）プロセッサ、またはＡＲＭプロセッサとして、あるいは様々なプロセッサ・タイプの組み合わせとして実装されることが可能である（Ｐｅｎｔｉｕｍ（登録商標）は、インテル・コーポレーション（Ｉｎｔｅｌ  Ｃｏｒｐｏｒａｔｉｏｎ）の登録商標であり、Ｔｅｎｓｉｌｉｃａ（登録商標）は、テンシリカ社（Ｔｅｎｓｉｌｉｃａ  Ｉｎｃ．）の商標であり、ＡＲＭプロセッサは、ＡＲＭホールディングス（ＡＲＭ  Ｈｏｌｄｉｎｇｓ，  ｐｌｃ）によるものであり、Ｐｏｗｅｒ  ＰＣ（登録商標）は、ＩＢＭ社の登録商標である）。図１では単一のプロセッサとして示されるものの、制御プロセッサ１４０は、複数のプロセッサ（図示せず）によって実装されるとともに、説明される実施形態により、しきい値最適化された（ｔｈｒｅｓｈｏｌｄ  ｏｐｔｉｍｉｚｅｄ）動作を実行することを含む動作のために必要とされるソフトウェア／ファームウェアを含むことも可能である。制御プロセッサ１４０は、メディア１１０に書き込まれるデータに関するＬＤＰＣ符号化、およびメディア１１０から読み出されるデータに関する復号化を実行する低密度パリティ検査（ＬＤＰＣ）符号器／復号器（コーデック）１４２と通信状態にある。また、制御プロセッサ１４０は、ホスト動作の論理アドレス（例えば、読み出し／書き込み動作のための論理ブロック・アドレス（ＬＢＡ）など）とメディア１１０上の物理アドレスとの間の変換を行うのに使用されるマップ１４４とも通信状態にある。本明細書で使用されるように、ＬＢＡという用語は、ＨＰＡ（ホスト・ページ・アドレス）と同義である。
【００１７】
通信リンク１７０が、ＮＶＭシステム１００とインターフェースをとるコンピュータ・システムであることが可能なホスト・デバイス１８０と通信するのに使用される。通信リンク１７０は、カスタム通信リンクであることが可能であり、あるいは、例えば、スモール・コンピュータ・システム・インターフェース（「ＳＣＳＩ」）プロトコル・バス、シリアル・アタッチト（Ｓｅｒｉａｌ  Ａｔｔａｃｈｅｄ）ＳＣＳＩ（「ＳＡＳ」）プロトコル・バス、シリアル・アドバンスト・テクノロジー・アタッチメント（Ｓｅｒｉａｌ  Ａｄｖａｎｃｅｄ  Ｔｅｃｈｎｏｌｏｇｙ  Ａｔｔａｃｈｍｅｎｔ）（「ＳＡＴＡ」）プロトコル・バス、ユニバーサル・シリアル・バス（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）（「ＵＳＢ」）、イーサネット（Ｅｔｈｅｒｎｅｔ）リンク、ＩＥＥＥ８０２．１１リンク、ＩＥＥＥ８０２．１５リンク、ＩＥＥＥ８０２．１６リンク、ペリフェラル・コンポーネント・インターコネクト・エクスプレス（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｅｘｐｒｅｓｓ）（「ＰＣＩ−Ｅ」）リンク、シリアル・ラピッド（Ｓｅｒｉａｌ  Ｒａｐｉｄ）入出力（「ＳＲＩＯ」）リンク、または周辺デバイスをコンピュータに接続するための他の任意の類似したインターフェース・リンクなどの標準通信プロトコルにより動作するバスであることが可能である。
【００１８】
図２は、ソリッドステート・メディア１１０内に見られることが可能な単一のフラッシュ・メモリ・セルの例示的な機能ブロック図を示す。フラッシュ・メモリ・セル２００は、２つのゲートを有するＭＯＳＦＥＴである。ワード線制御ゲート２３０は、フローティング・ゲート２４０の上に配置される。フローティング・ゲート２４０は、ワード線制御ゲート２３０、およびＭＯＳＦＥＴチャネルから絶縁層によって絶縁され、ＭＯＳＦＥＴチャネルは、Ｎチャネル２５０および２６０と、Ｐチャネル２７０とを含む。フローティング・ゲート２４０は、電気的に絶縁されるため、フローティング・ゲート２４０に加えられた電荷は、留まり、通常、数ヶ月にもわたって大きく放電されない。フローティング・ゲート２４０が電荷を保持する場合、フローティング・ゲート２４０は、セルのしきい値電圧を変えるワード線制御ゲート２３０による電界を部分的にキャンセルする。しきい値電圧は、チャネルを導通させるように制御ゲート２３０に印加される電圧の量である。チャネルが導通することによって、例えば、フローティング・ゲート２４０上の電荷を検知することによって、セルの中に格納された値が特定される。
【００１９】
図３は、ソリッドステート・メディア１１０内に見られることが可能である例示的なＮＡＮＤ  ＭＬＣフラッシュ・メモリ・ストリング３００を示す。図３に示されるとおり、フラッシュ・メモリ・ストリング３００は、ドレインからソースまで直列に接続された、１つまたは複数のワード線トランジスタ２００（２）、２００（４）、２００（６）、２００（８）、２００（１０）、２００（１２）、２００（１４）、および２００（１６）（例えば、８つのフラッシュ・メモリ・セル）、ならびにビット線選択トランジスタ３０４を含むことが可能である。この直列接続は、ビット線３２２が完全に引き下げられるように対応するゲートを高に駆動することによって、接地選択トランジスタ３０２、ワード線トランジスタ２００（２）、２００（４）、２００（６）、２００（８）、２００（１０）、２００（１２）、２００（１４）、および２００（１６）、ならびにビット線選択トランジスタ３０４がすべて「オンにされる」ようになっている。オンにされるワード線トランジスタ２００（２）、２００（４）、２００（６）、２００（８）、２００（１０）、２００（１２）、２００（１４）、および２００（１６）の数（または、これらのトランジスタが線形領域で動作しているか、飽和領域で動作しているか）を変えることにより、ＭＬＣストリング３００が複数の電圧レベルを実現することができるようになり得る。通常のＭＬＣ  ＮＡＮＤフラッシュは、フローティング・ゲートを有する６４のトランジスタの「ＮＡＮＤストリング」（例えば、図３に示されるとおり）を使用することが可能である。書き込み動作中、書き込まれるべきワード線位置でＮＡＮＤストリングに高い電圧が印加される。読み出し動作中、所望される読み出しロケーションに対応するトランジスタを除いて、ＮＡＮＤストリングにおけるすべてのトランジスタのゲートに電圧が印加される。所望される読み出しロケーションは、フローティング・ゲートを有する。
【００２０】
本明細書で説明されるとおり、ＳＬＣ  ＮＡＮＤフラッシュとＭＬＣ  ＮＡＮＤフラッシュの両方において、各セルは、読み出ししきい値電圧レベルとの比較などによって検知され得る電荷電圧レベル（例えば、アナログ信号）を有する。メディア・コントローラは、電荷電圧レベルを読み出し、セルの対応するバイナリ値を検出するのに使用される所与の数の所定の電圧しきい値を有することが可能である。例えば、ＭＬＣ  ＮＡＮＤフラッシュに関して、３つのしきい値（０．１、０．２、０．３）が存在する場合、セル電圧レベルが０．０≦セル電圧＜０．１である際、そのセルは、［００］という値を有すると検出されることが可能である。セル電圧レベルが０．１≦セル電圧＜０．２である場合、値は、［１０］であることが可能であり、以下同様である。このため、測定されたセル・レベルは、そのセル・レベルが、２つのしきい値の中間にあると判定され、およびそのセル・レベルが検出され得るまで、通常、１つずつのしきい値と比較されることが可能である。このため、検出されたデータ値が、メモリ・コントローラ１２０の復号器に供給されて、検出された値（例えば、誤り訂正コードと一緒に）が復号されて、ホスト・デバイス１８０に供給されるべきデータにされる。
【００２１】
図４は、図１のソリッドステート・メディア１１０の例示的な構成のブロック図を示す。図４に示されるとおり、メディア１１０は、スペース不足（Ｏｕｔ−ｏｆ−Ｓｐａｃｅ）（ＯＯＳ）条件が生じるのを防止するようにオーバ・プロビジョニング（ｏｖｅｒ−ｐｒｏｖｉｓｉｏｎｉｎｇ）（ＯＰ）を伴って実装されることが可能である。図４に示されるとおり、ＯＰは、３つの様態で実現されることが可能である。第１に、ＳＳＤ製造業者が、通常、「ＧＢ」という用語を用いて１０進数のギガバイトを表すが、１０進数のギガバイト（１，０００，０００，０００バイト、つまり、１０９バイト）と２進数のギガバイト（１，０７３，７４１，８２４バイト、つまり、２３０バイト）は等しくない。したがって、ＳＳＤの物理容量は、２進数のＧＢに基づくので、ＳＳＤの論理容量が１０進数のＧＢに基づく場合、ＳＳＤは、７．３７％（例えば、［（２３０−１０９）／１０９］）の組み込まれたＯＰを有することが可能である。このことが、図４に「７．３７％」ＯＰ４０２として示される。しかし、このＯＰのいくらか、例えば、合計容量の２〜４％は、ＮＡＮＤフラッシュの不良なブロック（例えば、欠陥）のために失われる可能性がある。第２に、ＯＰは、ホスト・デバイス１８０が利用できない、システムが使用するための特定の量の物理メモリを取って置くことによって実装されることも可能である。例えば、製造業者が、１２８ＧＢの合計物理容量に基づいて、１００ＧＢ、１２０ＧＢ、または１２８ＧＢの論理容量を有する製造業者のＳＳＤに関する仕様を公開して、これにより、場合により、それぞれ２８％、７％、または０％の例示的なＯＰを実現することが可能である。このことが、図４に静的ＯＰ（「０から２８＋％」）４０４として示される。
【００２２】
第３に、いくつかのストレージ・プロトコル（例えば、ＳＡＴＡ）は、ホスト・デバイス１８０が、以前に保存されたデータのブロックを不要または無効と指定できるようにして、ガーベジ・コレクション中にＮＶＭシステム１００がそれらのブロックを保存しないようにする「ＴＲＩＭ」コマンドをサポートする。ＴＲＭコマンドに先立って、ホスト・デバイス１８０が或るファイルを消去した場合、そのファイルは、ホスト・デバイス・レコードから除去されているが、ＮＶＭシステム１００の実際の内容は、実際には消去されておらず、このことにより、ＮＶＭシステム１００が、ガーベジ・コレクション中に無効なデータを保持することになり、これにより、ＮＶＭ容量が小さくなる。ＴＲＩＭコマンドを使用することによる効率的なガーベジ・コレクションによるＯＰが、図４に動的ＯＰ４０６として示される。動的ＯＰ４０６およびユーザ・データ４０８が、ホスト・デバイス１８０の活性のデータを含むメディア１１０の領域を形成する一方で、ＯＰ領域４０２および４０４は、ホスト・デバイス１８０の活性のデータを含まない。ＴＲＩＭコマンドは、オペレーティング・システムが、データのいずれのページが、ユーザまたはオペレーティング・システム自らによる消去のために今では無効であるかをＳＳＤに通知することを可能にする。削除動作中、ＯＳは、削除されたセクタに新たなデータのために空いているという印を付け、もはや有効でないという印が付けられるべき削除されたセクタに関連するＳＳＤの論理ブロック・アドレス（ＬＢＡ）の１つまたは複数の範囲を指定するＴＲＩＭコマンドを送る。
【００２３】
ＴＲＩＭコマンドを実行した後、メディア・コントローラは、トリミングされたＬＢＡからのデータを、ガーベジ・コレクション中に再配置せず、メディアに対する書き込み動作の回数を減らし、これにより、書き込み拡大を小さくするとともに、ドライブ寿命を増加させる。ＴＲＩＭコマンドは、一般に、ＴＲＩＭコマンドが影響を及ぼすデータを不可逆に削除する。ＴＲＩＭコマンドの例が、ＳＡＴＡ  ＴＲＩＭ（データ・セット管理）コマンド、ＳＣＳＩ  ＵＮＭＡＰコマンド、マルチメディアカード（ＭＭＣ）ＥＲＡＳＥコマンド、およびセキュア・デジタル（ＳＤ）カードＥＲＡＳＥコマンドである。一般に、ＴＲＩＭは、完全にトリミングされたＳＳＤが、同一のタイプの新規に製造された（すなわち、空の）ＳＳＤの性能に近い性能を有するようにＳＳＤ性能を向上させる。
【００２４】
一般に、メディア・コントローラ１２０は、ホスト・デバイス１８０から受け取られたコマンドを実行する。これらのコマンドのうちの少なくともいくつかは、データがホスト・デバイス１８０から送られて、メディア１１０にデータを書き込み、またはメディア１１０からデータを読み出し、読み出されたデータをホスト・デバイス１８０に送る。メディア・コントローラ１２０は、１つまたは複数のデータ構造を使用して、論理メモリ・アドレス（例えば、ホスト動作に含められたＬＢＡ）をメディアの物理アドレスにマップする。ＬＢＡがＳＳＤの中に書き込まれる際、ＬＢＡは、一般に、毎回、異なる物理ロケーションに書き込まれ、各書き込みは、そのＬＢＡのデータが不揮発性メモリ（例えば、メディア１１０）の中でどこに存在するかを記録するようにマップを更新する。例えば、２０１２年８月８日に出願した国際特許出願ＰＣＴ／ＵＳ２０１２／０４９９０５号で説明されるようなシステムにおいて、メディア・コントローラ１２０は、リーフ・レベルと、より上位の１つまたは複数のレベルとを含むマルチレベル・マップ構造（例えば、マップ１４４）を使用する。リーフ・レベルは、１つまたは複数のエントリをそれぞれが有するマップ・ページを含む。接続されたメディア（例えば、メディア１１０）のＬＢＡなどの論理アドレスが、マルチレベル・マップ構造の中で調べられて、リーフ・レベル・ページのうちの特定の１つのページの中の複数のエントリのうちの対応する１つが特定される。ＬＢＡの対応するエントリは、そのＬＢＡに関連付けられたメディア１１０の物理アドレスなどの、そのＬＢＡに関連付けられた情報を含む。一部の実施例において、対応するエントリは、その対応するエントリが有効であるか、または無効であるかについて、および、オプションとして、そのＬＢＡに対してＴＲＩＭコマンドが実行され（「トリミングされ」）ているか、または全く書き込まれていないかについての指示をさらに備える。例えば、無効なエントリは、関連するＬＢＡがトリミングされているかどうかなどの情報を、無効なエントリの物理ロケーション部分の中に符号化することができる。
【００２５】
ＬＢＡを調べるのを迅速化するのに、リーフ・レベル・ページのうちの少なくともいくつかのページのキャッシュ（図示せず）が保持されることが可能である。一部の実施形態において、マップ・データ構造の少なくとも一部分が、ホスト・デバイス１８０からは見えないプライベート・ストレージのために使用される（例えば、メディア・コントローラ１２０のログ、統計、マッピング・データ、または他のプライベート／制御データを格納するのに）。
【００２６】
本明細書で説明されるとおり、マップ１４４は、ホスト・デバイス１８０によって使用される論理データ・アドレス指定と、メディア１１０によって使用される物理データ・アドレス指定の間で変換を行う。例えば、マップ１４４は、ホスト・デバイス１８０によって使用されるＬＢＡと、メディア１１０の１つまたは複数のフラッシュ・チップ（ｆｌａｓｈ  ｄｉｅｓ）のブロック・アドレスおよび／またはページ・アドレスの間で変換を行う。例えば、マップ１４４は、論理アドレスと物理アドレスの間の変換を実行する、または調べる１つまたは複数のテーブルを含むことが可能である。
【００２７】
各ＬＢＡに関連するデータは、固定の、圧縮されていないサイズで、またはそれぞれの圧縮されたサイズで、メディア１１０の対応する物理アドレスにおいて格納される。本明細書で説明されるとおり、読み出し単位は、メディア１１０のページの一部分などの、独立に読み出し可能であるメディア１１０の最も細かい粒度である。読み出し単位は、誤り訂正コード（ＥＣＣ）によって保護されるすべてのデータとともに、ＥＣＣの検査ビットおよび／または冗長性データを含む（またはそのようなビットおよび／またはデータに対応する）ことが可能である。図５は、マップ１４４によるＬＢＡのＬＰＮ部分をマップする実施形態の選択された詳細を示す。図５に示されるとおり、ＬＢＡ５０６は、論理ページ番号（ＬＰＮ）５０２と、論理オフセット５０４とを含む。マップ１４４は、ＬＰＮ５０２を、読み出し単位アドレス５０８、および読み出し単位での長さ５１０（および、場合により、省略記号で示される他のマップ・データ）を含むマップ・データ５１２に変換する。マップ・データ５１２は、通常、マップ１４４のマップ・テーブルの中にマップ・エントリとして格納されることが可能である。マップ１４４は、通常、システム１００が能動的に使用中である各ＬＰＮにつき１つのマップ・エントリを保持することが可能である。図示されるとおり、マップ・データ５１２は、読み出し単位アドレス５０８と、読み出し単位での長さ５１０とを含む。一部の実施形態において、長さおよび／またはスパンは、ＬＰＮに関連付けられたデータの長さを、読み出し単位での長さ５１０の全部（または一部分）におけるスパンからのオフセットとして格納することなどによって、符号化されて格納される。スパン（または読み出し単位での長さ）は、ＬＰＮに関連付けられたデータを取得するのに読み出されるべき読み出し単位の数を指定するのに対して、長さ（ＬＰＮに関連付けられたデータの）は、ＳＳＤの各ブロックの中の使用されるスペースの量を追跡するブロック使用されるスペース（Ｂｌｏｃｋ  Ｕｓｅｄ  Ｓｐａｃｅ）（ＢＵＳ）などの統計のために使用される。通常、長さは、スパンと比べて、より細かい粒度を有する。
【００２８】
一部の実施形態において、第１のＬＰＮが、第１のマップ・エントリに関連付けられ、第２のＬＰＮ（第１のＬＰＮとは異なるが、第１のＬＰＮによって参照される論理ページと同一サイズの論理ページを参照する）が、第２のマップ・エントリに関連付けられ、第１のマップ・エントリの読み出し単位でのそれぞれの長さは、第２のマップ・エントリの読み出し単位でのそれぞれの長さとは異なる。そのような実施形態において、同一の時点で、第１のＬＰＮが、第１のマップ・エントリに関連付けられ、第２のＬＰＮが、第２のマップ・エントリに関連付けられ、第１のマップ・エントリのそれぞれの読み出し単位アドレスは、第２のマップ・エントリのそれぞれの読み出し単位アドレスと同一であり、したがって、第１のＬＰＮに関連付けられたデータと第２のＬＰＮに関連付けられたデータはともに、メディア１１０の同一の物理読み出し単位の中に格納される。
【００２９】
様々な実施形態において、マップ１４４は、１レベル・マップ、第１レベル・マップ（ＦＬＭ）と、ホスト・プロトコルのＬＢＡをメディア１１０内の物理格納アドレスに関連付ける１つまたは複数の第２レベル（またはより下位レベルの）マップ（ＳＬＭ）とを含む２レベル・マップのいずれかである。例えば、図６に示されるとおり、例えば、マップ１４４内で、ＦＬＭ６１０が、メディア・コントローラ１２０内にオンチップで保持される。一部の実施形態において、ＦＬＭ６１０の不揮発性（ただし、わずかにより古い）コピーもまた、メディア１１０上に格納される。ＦＬＭ６１０の中の各エントリは、実質的に、ＳＬＭページ（例えば、ＳＬＭ６１６のうちの１つ）に対するポインタである。ＳＬＭ６１６は、メディア１１０の中に格納され、一部の実施形態において、これらのＳＬＭのうちのいくつかは、マップ１４４のオンチップＳＬＭキャッシュ（例えば、ＳＬＭキャッシュ６０８）の中にキャッシュされる。ＦＬＭ６１０の中のエントリは、対応する第２レベル・マップ・ページ（例えば、ＳＬＭキャッシュ６０８またはメディア１１０の中の）のアドレス（および、場合により、アドレスまたは他の情報のデータ長／範囲）を含む。図６に示されるとおり、マップ・モジュール１４４は、所与のＬＢＡ（例えば、ＬＢＡ６０２）の第１の関数（例えば、そのＬＢＡを、第２レベル・マップ・ページのそれぞれの中に含められたエントリの固定の数で割った際に得られる商）を、ＳＬＭ６１６として示される複数の第２レベル・マップ（ＳＬＭ）のうちの１つの中のそれぞれのアドレスに関連付ける第１レベル・マップ（ＦＬＭ）６１０を有する２レベル・マップを含むことが可能であり、各ＳＬＭは、ＬＢＡの第２の関数（例えば、そのＬＢＡを、第２レベル・マップ・ページのそれぞれの中に含められたエントリの固定の数で割った際に得られる剰余）を、そのＬＢＡに対応するメディア１１０内のそれぞれのアドレスに関連付ける。
【００３０】
例えば、図６に示されるとおり、トランスレータ６０４が、或るホスト動作に対応するＬＢＡ（ＬＢＡ６０２）（例えば、ホスト１８０からの、メディア１１０上の対応するＬＢＡに対して読み出しまたは書き込みを行う要求）を受け取る。トランスレータ６０４は、例えば、ＬＢＡ６０２を、対応するＳＬＭページ６１６の各ページの中のエントリの整数で割ることによって、ＬＢＡ６０２をＦＬＭインデックス６０６およびＳＬＭページ・インデックス６１４に変換する。説明される実施形態において、ＦＬＭインデックス６０６は、この除算演算の商であり、ＳＬＭページ・インデックス６１４は、この除算演算の剰余である。この除算演算を使用することは、ＳＬＭページ６１６が、２のべき乗でない数のエントリを含むことを可能にし、このことは、ＳＬＭページ６１６のサイズが小さくされることを許して、ＳＬＭページ６１６を更新する書き込み動作に起因するメディア１１０の書き込み拡大を小さくすることが可能である。ＦＬＭインデックス６０６は、ＦＬＭ６１０の中のエントリを一意的に識別するのに使用され、このエントリは、ＳＬＭページ６１６のうちの１つに対応するＳＬＭページ・インデックス（６１４）を含む。６１２で示されるとおり、ＦＬＭエントリのＳＬＭページ・インデックスに対応するＳＬＭページがＳＬＭキャッシュ６０８の中に格納される実例において、ＦＬＭ６１０が、ＬＢＡ６０２に対応するメディア１１０の物理アドレスを戻すことが可能である。ＳＬＭページ・インデックス６１４は、ＳＬＭ６１６の中のエントリを一意的に識別するのに使用され、このエントリは、６１８で示されるとおり、ＬＢＡ６０２に対応するメディア１１０の物理アドレスに対応する。ＳＬＭ６１６のエントリは、読み出し単位アドレス（例えば、フラッシュ・ページのＥＣＣ訂正可能な下位単位のアドレス）、および読み出し単位の長さとして符号化されることが可能である。
【００３１】
ＳＬＭページ６１６（または、より低レベルのマルチレベル・マップ（ＭＬＭ）構造）はすべて、同一数のエントリを含むことが可能であり、またはＳＬＭページ６１６（または、より低レベルのＭＬＭ構造）のそれぞれは、異なる数のエントリを含むことが可能である。さらに、ＳＬＭページ６１６（または、より低レベルのＭＬＭ構造）のエントリは、同一の粒度であることが可能であり、または粒度は、ＳＬＭページ６１６（または、より低レベルのＭＬＭ構造）のそれぞれに関して設定されることが可能である。例示的な実施形態において、ＦＬＭ６１０は、１エントリ当たり４ＫＢの粒度を有し、ＳＬＭページ６１６（または、より低レベルのＭＬＭ構造）のそれぞれは、１エントリ当たり８ＫＢの粒度を有する。このため、例えば、ＦＬＭ６１０の中の各エントリは、５１２ＢのＬＢＡの整列された８セクタ（４ＫＢ）領域に関連付けられ、ＳＬＭページ６１６のうちの１つのページの中の各エントリは、５１２ＢのＬＢＡの整列された１６セクタ（８ＫＢ）領域に関連付けられる。
【００３２】
一部の実施形態において、ＦＬＭ６１０（またはＭＬＭ構造のより高レベルのマップ）のエントリは、対応するより低レベルのマップ・ページのフォーマット情報を含む。図７は、例示的なＦＬＭ７００のブロック図を示す。図示されるとおり、ＦＬＭ７００のＮ個のエントリ７０１のそれぞれが、対応するより低レベルのマップ・ページのフォーマット情報を含む。図示されるとおり、ＦＬＭ７００は、ＳＬＭページ粒度７０２と、読み出し単位物理アドレス範囲７０４と、各ＬＢＡに関するデータ・サイズ７０６と、データ無効標識７０８と、ＴＲＩＭ動作進行中標識７１０と、ＴＲＩＭ  ＬＢＡ範囲７１２と、処理されるべき（Ｔｏ−Ｂｅ−Ｐｒｏｃｅｓｓｅｄ）（ＴＢＰ）標識７１４とを含むことが可能である。また、他のメタデータ（図示せず）が含められることも可能である。マップ・ページ粒度７０２は、ＦＬＭ７００のエントリに対応するＳＬＭページの粒度を示す。読み出し単位物理アドレス範囲７０４は、例えば、開始読み出し単位アドレスおよびスパンとして、ＦＬＭ７００のエントリに対応するＳＬＭページの読み出し単位（複数可）の物理アドレス範囲を示す。各ＬＢＡ７０６に関するデータ・サイズは、関連するＬＢＡのデータを得るのに読み出されるべき読み出し単位の数、またはＦＬＭ７００のエントリに対応するＳＬＭページに関してメディア１１０の中に格納された関連するＬＢＡのデータのサイズを示す。データ無効標識７０８は、関連するＬＢＡのデータが既にトリミングされている、またはそれ以外で無効にされているなどのために、関連するＬＢＡのデータが、メディア１１０の中に存在しないことを示す。代替の実施形態において、データ無効標識は、読み出し単位物理アドレス範囲７０４の一部として符号化されることが可能である。後段でより詳細に説明されるとおり、ＴＲＩＭ動作進行中標識７１０は、ＴＲＩＭ  ＬＢＡ範囲７１２によって示されるＬＢＡに対してＴＲＩＭ動作が進行中であることを示す。一部の実施形態において、ＴＲＩＭ動作進行中標識７１０は、ＴＲＩＭ  ＬＢＡ範囲７１２の一部として符号化されることが可能である。ＴＢＰ標識７１４は、マップ・ページに関連するＬＢＡが既に無効にされている（例えば、トリミングされているようにホスト１８０に見える）が、それらのＬＢＡが、新たなデータを書き込むのにまだ利用できない場合、そのことを示す。より高レベルのマップ・エントリに無効の印を付けるのとは異なり、より高レベルのマップ・エントリのＴＢＰビットを設定することは、そのより高レベルのマップ・エントリの中に格納されたより低レベルのマップ・ページの物理アドレスが無効であることは暗示せず、つまり、そのより低レベルのマップ・ページがＢＵＳ更新のために処理されるまで、その物理アドレスは、要求され、そのより低レベルのマップ・ページ自体、割り当て解除され得ない。このため、より低レベルのマップ・ページは、以下の３つの状態、すなわち、無効、有効、またはＴＢＰのうちの１つに入っていることが可能である。
【００３３】
本明細書で説明されるマルチレベル・マップ（ＭＬＭ）構造を使用するＳＳＤは、複数のリーフ・レベル・マップ単位にわたる改良されたＴＲＩＭ動作を可能にする。このため、標準のＴＲＩＭ動作の場合のように個々のＬＢＡエントリを無効にする代わりに、改良されたＴＲＩＭ動作は、ＭＬＭ構造のより高いマップ・レベルにおけるリーフ単位全体を無効にすることができる。このことは、メディア・コントローラ１２０に結合されたホスト・デバイスから見てＴＲＩＭ動作の待ち時間を短縮して、より高いシステム性能を有利に可能にする。しかし、リーフ・レベル・マップの中のトリミングされた個々のＬＢＡエントリを単に破棄することは、トリミングされたＬＢＡが依然としてブロック使用されるスペース（ＢＵＳ）に寄与しているように見えるので、ＢＵＳアカウンティングの不正確さを被る可能性がある。ＢＵＳカウントは、所与のブロック、または所与のグループのブロック（例えば、最も少ないＢＵＳを有するブロック）に対していつガーベジ・コレクションを実行すべきかを判定して、ガーベジ・コレクション書き込み拡張を小さくする１つの方法として、フラッシュ・ブロックごとに、またはグループのフラッシュ・ブロックごとになど、ＳＳＤの不揮発性メモリの各領域に関して、メディア・コントローラ１２０によってメディア１１０の中に保持される。このため、ＢＵＳが不正確であることは、不正確なガーベジ・コレクション、および／またはメディア１１０に対するより多くの回数の書き込みをもたらして、書き込み拡大を大きくするとともに、ＳＳＤ寿命を短くする可能性がある。改良されたＴＲＩＭ動作は、ホスト・デバイスに対してＴＲＩＭ動作の確認応答を行った後に、背景でＢＵＳカウントを更新することによってＢＵＳの正確さも維持しながら、ＬＢＡの迅速なトリミングを実行することができる。
【００３４】
説明される実施形態において、ＴＲＩＭ動作は、トリミングされたすべてのＬＢＡに無効の印を付けるようにＭＬＭ構造を更新する。さらに、ＴＲＩＭ動作は、メディア１１０の対応する領域のＢＵＳカウントから、トリミングされたＬＢＡによって前に使用されていたフラッシュ・スペースを引いて、正確なガーベジ・コレクションをもたらす。このため、特定のＬＢＡを適切にトリミングするのに、以下の２つのことが行われる。すなわち、その特定のＬＢＡがＭＬＭ構造の中で無効にされ、ＢＵＳカウントが、その特定のＬＢＡがもはやフラッシュ・スペースを消費しないことを反映して更新される。しかし、大きいトリム領域（例えば、ＳＳＤ全体）または複数の大きいトリム領域の場合、無効化およびＢＵＳ更新を実行するのに要求される時間は、大きくなり、システム性能に悪影響を与える可能性がある。
【００３５】
本明細書で説明される、ＦＬＭの中に格納されたＳＬＭページ情報は、対応するＳＬＭページ内のＬＢＡが既に無効にされている（例えば、トリミングされているようにホスト１８０に見える）が、ＴＲＩＭ動作のＢＵＳ更新部分がまだ完了していない場合、そのことを示す指示（例えば、処理されるべき（ＴＢＰ）標識７１４）を含むことが可能である。より高レベルのマップ・エントリに無効の印を付けるのとは異なり、より高レベルのマップ・エントリのＴＢＰ標識を設定することは、そのより高レベルのマップ・エントリの中に格納されたより低レベルのマップ・ページの物理アドレスが無効であることは暗示せず、つまり、そのより低レベルのマップ・ページがＢＵＳ更新のために処理されるまで、その物理アドレスは、要求され、そのより低レベルのマップ・ページ自体、割り当て解除され得ない。しかし、そのより高レベルのマップ・エントリに関連するすべてのユーザ・データは、そのより高レベルのマップ・エントリに無効の印が付けられているとした場合と同じく、ホスト読み出し操作に関して無効である。
【００３６】
メディア１１０の中に格納された関連するＬＢＡのデータのサイズ（例えば、７０６）は、ＳＳＤ１０１がＴＲＩＭ動作を実行する際に対応する領域に関するＢＵＳ値を更新するのに使用される。例えば、これらのサイズ値が、対応する領域のＢＵＳカウントから引かれる。ＭＬＭ構造を使用する実施形態において、ＢＵＳカウントを更新することは、ＢＵＳカウントを更新することが、リーフ・レベル・マップ・エントリを１つずつ処理することを要求するので、時間がかかり得る。処理時間を改善するのに、説明される実施形態は、ＳＳＤ１０１の背景動作モードでメディア１１０の対応する領域のＢＵＳカウントを更新するメガＴＲＩＭ動作を使用する。
【００３７】
例えば、ＳＳＤ１０１が、ホスト１８０からＴＲＩＭコマンドを受け取ると、メディア・コントローラ１２０が、ＴＲＩＭコマンドに関連付けられたＳＬＭページ（複数可）に対応するＦＬＭエントリ（例えば、７０１）のそれぞれのＴＢＰ標識（例えば、７１４）を設定するメガＴＲＩＭ動作を実行する。そのＴＲＩＭ動作が、そのＳＬＭページの中のＳＬＭエントリの一部分だけにしか影響しない場合、一部の実施形態は、トリミングされるＳＬＭエントリに無効の印を付けること、およびＳＬＭページのトリミングされる部分を反映するようにＢＵＳカウントを更新することによって、部分的ＳＬＭページの個々を更新することによって、部分的ＳＬＭページの個々のエントリを処理することが可能である。他の実施形態は、ＴＢＰ標識（例えば、７１４）、ＴＲＩＭ動作進行中標識（例えば、７１０）、およびＴＲＩＭ  ＬＢＡ範囲（例えば、７１２）を使用して、トリミングされたＳＬＭエントリに無効の印を付けること、およびＢＵＳカウントを更新することの遅延を許すことによって、部分的ＳＬＭページを更新することを遅らせることが可能である。次に、部分的にトリミングされたＳＬＭページのその後の部分的ＴＲＩＭ動作が、オプションとして、および／または選択的に、部分的にトリミングされたＳＬＭページに対する更新動作の一部またはすべてを即時に実行して、所与のＴＲＩＭ  ＬＢＡ範囲（例えば、７１２）内で複数の部分範囲を追跡する必要性を回避する。しかし、代替の実施形態は、ＴＲＩＭ  ＬＢＡ範囲（例えば、７１２）内の複数の部分範囲を追跡して、トリミングされたＳＬＭエントリに無効の印を付けること、およびＢＵＳカウントを更新することのより長い遅延を許すことが可能である。
【００３８】
メガＴＲＩＭ動作が実行されると、関連するＬＢＡを無効にした後、ＳＳＤ１０１は、ＢＵＳカウントが更新されるのに先立って、ホスト１８０に対してＴＲＩＭコマンドの確認応答を行うことが可能である。次に、ＢＵＳカウントを更新することが、ＳＳＤ１０１の背景プロセスにおいて実行される（ＴＲＩＭ範囲、およびホスト１８０によって開始された活動の量に依存して、通常、数秒から数分までの範囲内に完了する）。関連するＦＬＭエントリの中でＴＢＰ標識が設定されているＳＬＭページのうちの１つが完全に処理される（例えば、トリミングされたＳＬＭエントリに無効の印を付け、トリミングされたＳＬＭページの中のすべてのＳＬＭエントリに関するＢＵＳカウントを更新して）たびに、関連するＦＬＭエントリの中のＴＢＰ標識がクリアされる。ＳＬＭページのうちの１つのページのＳＬＭエントリのすべてがトリミングされた場合、関連するＦＬＭエントリには、トリミングされたという印が付けられて、新たな書き込みが、そのＳＬＭページ内の少なくとも１つのエントリを有効にするまで、そのＳＬＭページをさらに処理する必要性を除く。
【００３９】
図８は、メガＴＲＩＭ動作８００の流れ図を示す。図８に示されるとおり、ステップ８０２で、ＴＲＩＭ動作要求が、ＳＳＤ１０１によってホスト１８０から受け取られる。ステップ８０４で、ＳＳＤ１０１が、ＴＲＩＭ動作の範囲（例えば、１つまたは複数の開始ＬＢＡおよび終了ＬＢＡ）を特定する。ＳＳＤ１０１は、ＴＢＰ指標が設定されて、ＦＬＭのその部分が、ＢＵＳカウントを更新し、メディア１１０のメモリ・ブロックをホスト１８０が再び利用できるようにする背景動作を要求することを示す、ＦＬＭの部分を示すＦＬＭの開始ＴＢＰインデックス（ｍｉｎ＿ｆｌｍ＿ｉｎｄｅｘ＿ｔｂｔ）および終了ＴＢＰインデックス（ｍａｘ＿ｆｌｍ＿ｉｎｄｅｘ＿ｔｂｔ）を保持することが可能である。背景で（例えば、ＳＳＤ１０１の別のアイドルの時間中に）、ＳＳＤ１０１が、開始ＴＢＰインデックスにおけるＦＬＭエントリを検査することと、そのＦＬＭエントリ上にＴＢＰが設定されている場合、関連するＳＬＭページを読み出すことと、関連するＳＬＭページの中の各エントリに応じてＢＵＳカウントを更新し、そのＦＬＭエントリの中のＴＢＰ標識をクリアし、そのＦＬＭエントリにトリミングされたという印を付けて、そのＳＬＭページ全体がトリミングされたことを示すことによって、そのＳＬＭページ全体をトリミングすることとが可能である。開始ＴＢＰインデックス（ｍｉｎ＿ｆｌｍ＿ｉｎｄｅｘ＿ｔｂｔ）が、そのエントリが処理されたことを示すように更新される。
【００４０】
図８に示されるとおり、或るトリム範囲（例えば、ＳＡＴＡの場合、セクタごとに６４のＮＣＱトリム範囲（ｔｈｅ  ６４−ｐｅｒ−ｓｅｃｔｏｒ  ＮＣＱ  ｔｒｉｍ  ｒａｎｇｅ）のうちの１つ）を有するＴＲＩＭコマンドが処理されると、ステップ８０６で、ＳＳＤ１０１が、そのＴＲＩＭ範囲の最初のＳＬＭページとそのＴＲＩＭ範囲の最後のＳＬＭページの少なくともいずれかが、部分的ＳＬＭページである（例えば、そのＴＲＩＭ範囲が、そのＳＬＭページの一部だけに適用される）かどうかを判定する。ステップ８０６で、その範囲の始め、または終わりに部分的ＳＬＭページが存在する場合、ステップ８０８で、ＳＳＤ１０１は、その部分的ＳＬＭページがキャッシュ６０８の中に格納されているかどうかを判定する。ステップ８０８で、そのＴＲＩＭ範囲の始め、または終わりの部分的ＳＬＭページがキャッシュ６０８の中に格納されている場合、プロセス８００は、ステップ８１２に進む。ステップ８０８で、そのＴＲＩＭ範囲の始め、または終わりの部分的ＳＬＭページがキャッシュ６０８の中に格納されていない場合、ステップ８１０で、ＳＳＤ１０１は部分的ＳＬＭページをメディア１１０からキャッシュ６０８へフェッチし、プロセス８００はステップ８１２に進む。ステップ８１２で、ＴＲＩＭ動作のその範囲内にある部分的ＳＬＭページのエントリに関してＴＲＩＭ動作が実行される。例えば、その部分的ＳＬＭページの中のＴＲＩＭ範囲内の任意のＬＢＡに対応する、そのＴＲＩＭ範囲内のＳＬＭページ・エントリが更新される。ＳＬＭページの中のエントリを更新することは、データ無効標識を設定すること、およびＢＵＳカウントを更新することを含む。プロセス８００は、ステップ８２０に進む。
【００４１】
ステップ８０６で、そのＳＬＭページが部分的ＳＬＭページではなかった場合、ステップ８１４で、ＳＳＤ１０１は、完全なＳＬＭページがキャッシュ６０８の中に格納されているかどうかを判定する。ステップ８１４で、完全なＳＬＭページがキャッシュ６０８の中に格納されている場合、プロセス８００は、ステップ８１６に進む。ステップ８１４で、完全なＳＬＭページがキャッシュ６０８の中に格納されていなかった場合、ステップ８１８で、ＳＳＤ１０１は、そのＳＬＭページに対応するＦＬＭの中のＴＢＰ標識（例えば、７１４）を設定する。プロセス８００は、ステップ８２０に進む。
【００４２】
或るＳＬＭページがメディア１０１からフェッチされる必要がある際、関連するＦＬＭエントリの中でＴＢＰが設定されている場合、そのＳＬＭページは、完全に無効にされている（そのＳＬＭページ内のすべてのエントリは、ホスト・アクセスに関して無効として扱われる）が、そのＳＬＭページは、ＢＵＳ更新の目的でまだ処理されていない。読み出しに関して、そのＳＬＭページは、必要とされず（そのＳＬＭページによって参照されるすべてのデータは、トリミングされている）、そのＳＬＭページをフェッチすることは、要求されない。書き込みに関して、そのＳＬＭページは、フェッチされ、そのＳＬＭページの中のすべてのＬＢＡに関してＢＵＳカウントが更新され、そのＳＬＭページの中のすべてのエントリは、無効にされ、その後、書き込まれているそのＳＬＭページ内のＳＬＭエントリが更新される。ステップ８１６で、書き込みのための動作のサブセットが実行される。すなわち、そのＳＬＭページの中のすべてのＬＢＡに関してＢＵＳカウントが更新され、そのＳＬＭページの中のすべてのエントリが無効にされる。
【００４３】
ステップ８２２で、ＳＳＤ１０１は、ＴＢＰ標識が設定されていて（例えば、ｍｉｎ＿ｆｌｍ＿ｉｎｄｅｘ＿ｔｂｔおよびｍａｘ＿ｆｌｍ＿ｉｎｄｅｘ＿ｔｂｔ）、ＦＬＭのその部分が、ＢＵＳカウントを更新し、メディア１１０のメモリ・ブロックをホスト１８０が再び利用できるようにする背景動作を要求することを示す、ＦＬＭのエントリの範囲を特定する。ステップ８２４で、残りのＴＲＩＭ動作（例えば、ＢＵＳカウントを更新すること、およびメモリ・ブロックを、ホスト１８０によって使用可能であるものとして解放すること）が背景で行われる（例えば、ＳＤ１０１の別のアイドルな時間中に）。ＳＳＤ１０１は、ステップ８１６でメモリ・ブロックがトリミングされると（例えば、メモリ・ブロックのＢＵＳカウントが更新されると）更新される１つまたは複数のポインタを保持して、ブロックが処理されるにつれ新たなＴＲＩＭ範囲が記憶されることを確実にすることが可能である。例えば、ＳＳＤ１０１が、開始ＴＢＰインデックスにおけるＦＬＭエントリを検査することと、そのＦＬＭエントリ上でＴＢＰが設定されている場合、関連するＳＬＭページを読み出すことと、ＢＵＳカウントを更新し、そのＦＬＭエントリの中のＴＢＰ標識をクリアし、そのＦＬＭエントリにトリミングされたという印を付けて、そのＳＭＬページ全体がトリミングされたことを示すことによってそのＳＬＭページ全体をトリミングすることとが可能である。開始ＴＢＰインデックス（ｍｉｎ＿ｆｌｍ＿ｉｎｄｅｘ＿ｔｂｔ）は、そのエントリが処理されたことを示すように更新される。ステップ８２４で背景ＴＲＩＭ動作が完了すると、ホスト１８０に対してＴＲＩＭ動作の確認応答が行われる。ステップ８２６で、プロセス８００は完了する。
【００４４】
このため、本明細書で説明されるとおり、説明される実施形態は、ソリッドステート・メディアのためのメディア・コントローラを提供する。このメディア・コントローラは、少なくとも１つの論理アドレスと、アドレス範囲とを含む要求をホスト・デバイスから受け取る制御プロセッサを含む。この要求に応答して、制御プロセッサは、受け取られた要求が無効にする要求であるかどうかを判定する。受け取られた要求タイプが無効にする要求である場合、制御プロセッサは、メディア・コントローラのマップを使用して、その論理アドレスおよび範囲に関連付けられたマップの１つまたは複数のエントリを特定する。これらのマップ・エントリのそれぞれに関連付けられたマップの中の標識が、これらのマップ・エントリが無効にされるべきことを示すように設定される。制御プロセッサは、無効にする要求が完了したという確認応答をホスト・デバイスに対して行い、メディア・コントローラのアイドル・モードにおいて、無効にされるべきマップ・エントリに基づいて空きスペース・カウントを更新する。無効にされたマップ・エントリに関連付けられた物理アドレスが、ホスト・デバイスからのその後の要求に関して再使用されるように利用可能にされる。
【００４５】
本明細書で「１つの実施形態」または「或る実施形態」に言及することは、その実施形態に関連して説明される特定のフィーチャ、構造、または特徴が、少なくとも１つの実施形態に含まれ得ることを意味する。本明細書の様々な箇所における「一実施形態において」という句の出現は、必ずしもすべて同一の実施形態を指すわけではなく、別々の実施形態も、代替の実施形態も、必ずしも他の実施形態と相容れないわけでもない。同じことは、「実施例」という用語にも当てはまる。
【００４６】
本出願で使用されるように、「例示的」という語は、例、実例、または例示の役割をすることを意味するように本明細書で使用される。本明細書で「例示的」と説明される態様または設計は、必ずしも、他の態様または設計より好ましいとも、有利であるとも解釈されるべきではない。むしろ、例示的という語の使用は、具体的な方法で概念を提示することを意図している。
【００４７】
例示的な実施形態は、デジタル・シグナル・プロセッサ、マイクロコントローラ、または汎用コンピュータとしての可能な実装を含め、ソフトウェア・プログラムにおける処理ブロックに関連して説明されてきたが、説明される実施形態は、そのように限定されない。当業者には明白なとおり、ソフトウェアの様々な機能は、回路のプロセスとして実装されることも可能である。そのような回路は、例えば、単一の集積回路、マルチチップ・モジュール、単一のカード、またはマルチカード回路パックにおいて使用されることが可能である。
【００４８】
また、説明される実施形態は、それらの方法を実施するための方法および装置の形態で実現されることも可能である。また、説明される実施形態は、磁気記録媒体、光記録媒体、ソリッドステート・メモリ、フロッピー・ディスケット、ＣＤ−ＲＯＭ、ハードドライブ、または他の任意の一時的でないマシン可読記憶媒体などの一時的でない実体のある媒体として実現されたプログラム・コードの形態で実現されることも可能であり、そのプログラム・コードが、コンピュータなどのマシンにロードされ、そのマシンによって実行されると、そのマシンが、説明される実施形態を実施するための装置となる。説明される実施形態は、例えば、一時的でないマシン可読記憶媒体の中に格納されて、マシンにロードされ、および／またはマシンによって実行されるか、あるいは電気配線もしくはケーブル配線を介して、光ファイバを介して、または電磁放射を介してなど、何らかの伝送媒体または搬送波を介して伝送されるかにかかわらず、プログラム・コードの形態で実現されることも可能であり、そのプログラム・コードが、コンピュータなどのマシンにロードされ、そのマシンによって実行されると、そのマシンが、説明される実施形態を実施するための装置となる。汎用プロセッサ上で実装されると、プログラム・コード・セグメントは、そのプロセッサと一緒になって、特定の論理回路と同様に動作する独特のデバイスをもたらす。また、説明される実施形態は、説明される実施形態の方法および／もしくは装置を使用して生成された、媒体を介して電気的に、もしくは光学的に伝送される信号値のビットストリームまたは他のシーケンス、磁気記録媒体の中の格納された磁界変化などの形態で実現されることも可能である。
【００４９】
本明細書で提示される例示的な方法のステップは、必ずしも、説明される順序で実行されることは必須ではないものと理解されるべきであり、そのような方法のステップの順序は、単に例示的であるものと理解されたい。同様に、そのような方法にさらなるステップが含められることも可能であり、いくつかのステップが、説明される様々な実施形態と合致する方法において省略される、または組み合わされることも可能である。
【００５０】
要素および標準に関連して本明細書で使用される「互換性がある」という用語は、その要素が、その標準によって完全な様態で、または部分的に指定される様態で他の要素と通信し、他の要素によって、その標準によって指定される様態でそれらの他の要素と通信することが十分にできるものと認識されることを意味する。互換性のある要素は、内部では、その標準によって指定される様態で動作しなくてもよい。特に明記しない限り、各数値および各範囲は、「約」または「ほぼ」という語がその値または範囲の値に先行するかのように、近似であるものと解釈されたい。
【００５１】
この説明に関して、「結合する」、「結合している」、「結合された」、「接続する」、「接続している」、または「接続された」という用語は、２つ以上の要素間でエネルギーが伝達されることが許される、当技術分野で知られている、または後に開発される任意の様態を指し、さらなる１つまたは複数の要素を介在させることが企図されるが、必須ではない。逆に、「直接に結合された」、「直接に接続された」などの言い方は、そのようなさらなる要素が無いことを暗示する。信号、および対応するノードもしくはポートは、同一の名前で呼ばれることが可能であるとともに、本明細書では互いに区別されない。
【００５２】
説明される実施形態の性質を説明するために説明され、例示されてきた部分の詳細、材料、および構成の様々な変更が、以下の特許請求の範囲に記載される範囲を逸脱することなく、当業者によって行われることが可能であることが、さらに理解されよう。
【図１】
2014179084.tif 000004
【図２】
2014179084.tif 000005
【図３】
2014179084.tif 000006
【図４】
2014179084.tif 000007
【図５】
2014179084.tif 000008
【図６】
2014179084.tif 000009
【図７】
2014179084.tif 000010
【図８】
2014179084.tif 000011