(57)【要約】【課題】揮発性及び不揮発性メモリにおいてデータ構造を使用して論理的セクタが物理的ページへとマップされる不揮発性メモリのためのメモリマッピング技術を提供する。【解決手段】ある実施形態において、不揮発性メモリにおける第１のルックアップテーブルは、論理的セクタを物理的ページへと直接マップする。揮発性メモリにおける第２のルックアップテーブルは、不揮発性メモリにおける第１のルックアップテーブルの物理的アドレスを保持する。ある実施形態において、揮発性メモリにおけるキャッシュは、最も最近書き込まれた論理的セクタの物理的アドレスを保持する。又、ガベージコレクション及び回復オペレーションに使用できるブロックコンテンツを記述するブロックＴＯＣも開示される。【選択図】図１
2011511388.tif 000002
【特許請求の範囲】
【請求項１】
不揮発性メモリの第１ページアドレスに対応する１つ以上の論理的セクタに関連した読み取り要求を得、
前記第１ページアドレスが揮発性メモリにおけるインデックステーブルキャッシュに含まれるかどうか決定し、
前記第１ページアドレスが前記インデックステーブルキャッシュに含まれる場合は、
前記第１ページアドレスを前記インデックステーブルキャッシュから読み取り、
前記第１ページアドレスを使用して読み取りオペレーションを遂行し、
前記第１ページアドレスが前記インデックステーブルキャッシュに含まれない場合は、
前記揮発性メモリにおけるインデックス目次（ＴＯＣ）から、前記第１ページアドレスを記憶している不揮発性メモリのインデックステーブルエントリーの第２ページアドレスを得、
前記インデックステーブルエントリーから前記第１ページアドレスを読み取り、
前記第１ページアドレスを使用して読み取りオペレーションを遂行する、
ことを含む方法。
【請求項２】
前記揮発性メモリにおけるインデックステーブルキャッシュに前記第１ページアドレスを記憶することを更に含む、請求項１に記載の方法。
【請求項３】
メモリの利用性、１つ以上のトリガー事象、又は１つ以上の動作モードに基づいて前記揮発性メモリを動的に構成することを更に含む、請求項１に記載の方法。
【請求項４】
１つ以上の論理的セクタに関連した書き込み要求を得、
現在データブロックがいっぱいであるかどうか決定し、
前記現在データブロックがいっぱいである場合には、
前記現在データブロックのページにブロック目次（ＴＯＣ）を書き込み、
前記現在データブロックがいっぱいでない場合には、
前記現在データブロックに１つ以上のページを書き込み、
現在ブロックＴＯＣを更新し、
前記現在データブロックに対する有効なページコンテンツを更新する、
ことを含む方法。
【請求項５】
前記現在データブロックがいっぱいである場合には、
空きブロックを使用できるかどうか決定し、
空きブロックを使用できる場合には、その空きブロックを現在データブロックとして割り当て、
空きブロックを使用できない場合には、ガベージコレクションオペレーションを遂行して、空きブロックを発生する、
ことを含む請求項４に記載の方法。
【請求項６】
前記現在データブロックいっぱいでない場合には、
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含むかどうか決定し、
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含む場合には、有効なページカウントを更新する、
ことを含む請求項４に記載の方法。
【請求項７】
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含まない場合には、
インデックステーブルキャッシュに空きスペースがあるかどうか決定し、
インデックステーブルキャッシュに空きスペースがある場合には、インデックステーブルキャッシュに記憶された位置を使用してインデックスページを読み取り、
インデックステーブルキャッシュに空きスペースがない場合には、インデックステーブルキャッシュから古いページをフラッシュする、
ことを含む請求項６に記載の方法。
【請求項８】
前記ブロックＴＯＣは、現在データブロックの最終ページに書き込まれる、請求項４に記載の方法。
【請求項９】
インデックステーブルキャッシュ及びインデックス目次を記憶する揮発性メモリと、
論理的セクタに対応するページアドレスを記憶するインデックステーブルを記憶する不揮発性メモリと、
前記揮発性メモリ及び不揮発性メモリに結合されたコントローラであって、
論理的セクタに関連した読み取り要求を得、
前記論理的セクタに関連した第１ページアドレスがインデックステーブルキャッシュに含まれるかどうか決定し、
前記第１ページアドレスが前記インデックステーブルキャッシュに含まれる場合は、
前記第１ページアドレスを前記インデックステーブルキャッシュから読み取り、
前記第１ページアドレスを使用して読み取りオペレーションを遂行し、
更に、前記第１ページアドレスが前記インデックステーブルキャッシュに含まれない場合は、
前記揮発性メモリにおけるインデックス目次から、前記第１ページアドレスを記憶している不揮発性メモリのインデックステーブルエントリーの第２ページアドレスを得、
前記インデックステーブルエントリーから前記第１ページアドレスを読み取り、
前記第１ページアドレスを前記インデックステーブルキャッシュに記憶する、
ように動作できるコントローラと、
を備えたメモリシステム。
【請求項１０】
前記コントローラは、前記揮発性メモリにおけるインデックステーブルキャッシュに前記第１ページアドレスを記憶するように動作できる、請求項９に記載のメモリシステム。
【請求項１１】
前記コントローラは、メモリの利用性、１つ以上のトリガー事象、又は１つ以上の動作モードに基づいて前記揮発性メモリを動的に構成するように動作できる、請求項９に記載のメモリシステム。
【請求項１２】
インデックステーブルキャッシュ及びインデックス目次を記憶する揮発性メモリと、
論理的セクタに対応するページアドレスを記憶するエントリーをもつインデックステーブルを記憶する不揮発性メモリと、
前記揮発性メモリ及び不揮発性メモリに結合されたコントローラであって、
１つ以上の論理的セクタに関連した書き込み要求を得、
現在データブロックがいっぱいであるかどうか決定し、
前記現在データブロックがいっぱいである場合には、
前記現在データブロックのページにブロック目次（ＴＯＣ）を書き込み、
前記現在データブロックがいっぱいでない場合には、
前記現在データブロックに１つ以上のページを書き込み、
現在ブロックＴＯＣを更新し、
前記現在データブロックに対する有効なページコンテンツを更新する、
ように動作できるコントローラと、
を備えたメモリシステム。
【請求項１３】
前記現在データブロックがいっぱいである場合には、
空きブロックを使用できるかどうか決定し、
空きブロックを使用できる場合には、その空きブロックを現在データブロックとして割り当て、
空きブロックを使用できない場合には、ガベージコレクションオペレーションを遂行して、空きブロックを発生する、
ことを含む請求項１２に記載のメモリシステム。
【請求項１４】
前記現在データブロックいっぱいでない場合には、
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含むかどうか決定し、
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含む場合には、有効なページカウントを更新する、
ことを含む請求項１２に記載のメモリシステム。
【請求項１５】
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含まない場合には、
インデックステーブルキャッシュに空きスペースがあるかどうか決定し、
インデックステーブルキャッシュに空きスペースがある場合には、インデックステーブルキャッシュに記憶された位置を使用してインデックスページを読み取り、
インデックステーブルキャッシュに空きスペースがない場合には、インデックステーブルキャッシュから古いページをフラッシュする、
ことを含む請求項１４に記載のメモリシステム。
【請求項１６】
前記ブロックＴＯＣは、現在データブロックの最終ページに書き込まれる、請求項１２に記載のメモリシステム。
【請求項１７】
第１メモリにおけるデータページに対応する論理的セクタを読み取り又は書き込むための要求を得、
第２メモリにおける第１ルックアップテーブルを読み取って、第１メモリにおける第２ルックアップテーブルの位置を決定し、
第２ルックアップテーブルを読み取って、論理的セクタとデータページとの間のマッピングを決定する、
ことを含む方法。
【請求項１８】
不揮発性メモリから第１ルックアップテーブルを、そして揮発性メモリから第２ルックアップテーブルを読み取ることを更に含む、請求項１７に記載の方法。
【請求項１９】
論理的セクタとデータページとの間のマッピングを決定し、
そのマッピングを使用して不揮発性メモリからデータページを読み取る、
ことを更に含む請求項１８に記載の方法。
【請求項２０】
論理的セクタとデータページとの間のマッピングを決定し、
そのマッピングを使用してデータページへデータを書き込む、
ことを更に含む、請求項１８に記載の方法。
【請求項２１】
前記第１ルックアップテーブルは、目次であり、前記第２ルックアップテーブルは、インデックステーブルであり、前記インデックス目次は、インデックステーブルエントリーのページアドレスを記憶し、そしてインデックステーブルエントリーは、データページアドレスを記憶する、請求項１８に記載の方法。
【請求項２２】
第１ルックアップテーブルを記憶する揮発性メモリと、
第２ルックアップテーブルを記憶する不揮発性メモリと、
前記揮発性メモリ及び不揮発性メモリに結合されたコントローラであって、
論理的セクタを読み取り又は書き込むための要求を得、
揮発性メモリから第１ルックアップテーブルを読み取って、不揮発性メモリにおける第２ルックアップテーブルの位置を決定すると共に、第２ルックアップテーブルを読み取って、不揮発性メモリにおける論理的セクタとデータページとの間のマッピングを決定する、ように動作できるコントローラと、
を備えたメモリシステム。
【請求項２３】
前記データページは、前記ルックアップテーブルとは異なるメモリ装置に記憶される、請求項２２に記載のシステム。
【請求項２４】
前記コントローラは、前記マッピングを使用して前記不揮発性メモリからデータページを読み取るように動作できる、請求項２２に記載のシステム。
【請求項２５】
前記コントローラは、前記マッピングを使用して前記データページへデータを書き込むように動作できる、請求項２２に記載のシステム。
【請求項２６】
前記第１ルックアップテーブルは、目次であり、前記第２ルックアップテーブルは、インデックステーブルであり、前記インデックス目次は、インデックステーブルエントリーのページアドレスを記憶し、そしてインデックステーブルエントリーは、データページアドレスを記憶する、請求項２２に記載のシステム。
【請求項２７】
前記データページは、前記不揮発性メモリのブロックに含まれ、このブロックは、前記データページを前記論理的セクタに関連付けるブロック目次を含む、請求項２２に記載のシステム。
【請求項２８】
前記ブロック目次は、前記ブロックの最終ページに記憶される、請求項２７に記載のシステム。
【請求項２９】
前記揮発性メモリは、少なくとも前記ブロックに対する有効ページカウントを記憶するためのブロックテーブルを含む、請求項２８に記載のシステム。
【請求項３０】
ホスト装置へ結合すると共に、ホスト装置から読み取り又は書き込み要求を得るように構成できるインターフェイスを更に備えた、請求項２２に記載のシステム。
【請求項３１】
プロセッサにより実行されたときに、プロセッサが、
データページアドレスを記憶するためのエントリーを有するインデックステーブルを不揮発性メモリに生成し、及び
前記インデックステーブルの対応エントリーのページアドレスを記憶するためのエントリーを有するインデックス目次を揮発性メモリに生成する、
ことを含むオペレーションを遂行するようにさせるインストラクションが記憶されたコンピュータ読み取り可能な媒体。
【請求項３２】
不揮発性メモリにおけるデータページに対応する論理的セクタを読み取り又は書き込むための要求を得、
インデックス目次を読み取って、データページアドレスを記憶する対応インデックステーブルエントリーのページアドレスを決定し、
インデックステーブルエントリーを読み取って、データページアドレスを得、
前記データページアドレスを使用してデータページにおいて読み取り又は書き込みオペレーションを遂行する、
ことを更に含む請求項３１に記載のコンピュータ読み取り可能な媒体。
【請求項３３】
不揮発性メモリのブロックのページにブロック目次（ＴＯＣ）が存在するかどうか決定し、
前記ブロックＴＯＣが存在しない場合には、
そのブロック全体を読み取り、
不揮発性メモリにおけるインデックステーブルを更新し、インデックステーブルは、読み取り又は書き込み要求の論理的セクタをブロックのページへマッピングするためのページアドレスを記憶するものであり、
前記インデックステーブルを不揮発性メモリへ書き込み、
前記インデックステーブルを使用して、揮発性メモリにおいてインデックスＴＯＣを発生し、
前記ブロックＴＯＣが存在する場合には、
ブロックＴＯＣを使用して前記インデックステーブルを更新し、
前記インデックステーブルを不揮発性メモリへ書き込み、
前記インデックステーブルから揮発性メモリにおいてインデックスＴＯＣを発生することを含む方法。
【請求項３４】
揮発性メモリにおいて前記インデックステーブルを解除することを更に含む、請求項３３に記載の方法。
【請求項３５】
不揮発性メモリのブロックの最終ページに前記ブロックＴＯＣが記憶される、請求項３３に記載の方法。
【請求項３６】
揮発性メモリにおいてブロックに対する有効なページカウントを更新することを更に含み、その有効なページカウントは、ガベージコレクション（ＧＣ）オペレーションのための最良の候補ブロックを決定するのに使用される、請求項３３に記載の方法。
【請求項３７】
前記ブロックは、ブロックの分類されたリストから得られる、請求項３３に記載の方法。
【請求項３８】
前記ブロックの分類されたリストは、ブロックの年齢に基づき、増加する順に分類される、請求項３７に記載の方法。
【請求項３９】
候補ブロックのページからブロック目次（ＴＯＣ）を読み取って、候補ブロックを記述する情報を得、
前記情報を使用して前記候補ブロックにおける無効ページを決定し、
前記候補ブロックに対する有効なページカウントを更新する、
ことを含み、前記有効なページカウントは、その後のガベージコレクション（ＧＣ）オペレーションのための最良の候補ブロックを決定するのに使用される、方法。
【請求項４０】
前記ＧＣオペレーションのための候補ブロックの数に関連した有効なページカウントを読み取り、
前記有効なページカウントに基づいてＧＣオペレーションのための最良の候補ブロックを決定する、
ことを更に含む請求項３９に記載の方法。
【請求項４１】
前記情報は、論理的セクタ番号を含む、請求項３９に記載の方法。
【請求項４２】
前記無効ページを決定することは、更に、
論理的セクタ番号を分類し、
その分類された論理的セクタ番号をインデックステーブルページと相互参照して、前記候補ブロックにおける無効ページを決定する、
ことを含む請求項４１に記載の方法。
【請求項４３】
不揮発性メモリと、
前記不揮発性メモリに結合されたコントローラであって、前記不揮発性メモリのブロックのページにブロック目次（ＴＯＣ）が存在するかどうか決定し、
前記ブロックＴＯＣが存在しない場合には、
そのブロック全体を読み取り、
不揮発性メモリにおけるインデックステーブルを更新し、インデックステーブルは、読み取り又は書き込み要求の論理的セクタをブロックのページへマッピングするためのページアドレスを記憶するものであり、
前記インデックステーブルを不揮発性メモリへ書き込み、
前記インデックステーブルを使用して、揮発性メモリにおいてインデックスＴＯＣを発生し、
前記ブロックＴＯＣが存在する場合には、
ブロックＴＯＣを使用して前記インデックステーブルを更新し、
前記インデックステーブルを不揮発性メモリへ書き込み、
前記インデックステーブルから揮発性メモリにおいてインデックスＴＯＣを発生するように動作できるコントローラと、
を備えたシステム。
【請求項４４】
揮発性メモリにおいて前記インデックステーブルを解除することを更に含む、請求項４３に記載のシステム。
【請求項４５】
不揮発性メモリのブロックの最終ページに前記ブロックＴＯＣが記憶される、請求項４３に記載のシステム。
【請求項４６】
揮発性メモリにおいてブロックに対する有効なページカウントを更新することを更に含み、その有効なページカウントは、ガベージコレクション（ＧＣ）オペレーションのための最良の候補ブロックを決定するのに使用される、請求項４３に記載のシステム。
【請求項４７】
前記ブロックは、ブロックの分類されたリストから得られる、請求項４３に記載のシステム。
【請求項４８】
前記ブロックの分類されたリストは、ブロックの年齢に基づき、増加する順に分類される、請求項４７に記載のシステム。
【請求項４９】
不揮発性メモリと、
前記不揮発性メモリに結合されたコントローラであって、候補ブロックのページからブロック目次（ＴＯＣ）を読み取って、候補ブロックを記述する情報を得、
前記情報を使用して前記候補ブロックにおける無効ページを決定し、
前記候補ブロックに対する有効なページカウントを更新する、
ように動作できるコントローラと、
を備え、前記有効なページカウントは、その後のガベージコレクション（ＧＣ）オペレーションのための最良の候補ブロックを決定するのに使用される、システム。
【請求項５０】
前記ＧＣオペレーションのための候補ブロックの数に関連した有効なページカウントを読み取り、
前記有効なページカウントに基づいてＧＣオペレーションのための最良の候補ブロックを決定する、
ことを更に含む請求項４９に記載のシステム。
【請求項５１】
前記情報は、論理的セクタ番号を含む、請求項４９に記載のシステム。
【請求項５２】
前記無効ページを決定することは、更に、
論理的セクタ番号を分類し、
その分類された論理的セクタ番号をインデックステーブルページと相互参照して、前記候補ブロックにおける無効ページを決定する、
ことを含む請求項５１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、メモリマッピングに係る。
【０００２】
関連出願：本出願は、参考としてここにそのまま援用する、２００８年２月４日出願の“Memory Mapping Techniques”と題するプロビジョナル特許出願第６１／０２６，０９５号の優先権の利益を主張するものである。
【０００３】
又、本出願は、各々参考としてここにそのまま援用する、２００８年８月１８日出願の“Memory Mapping Architecture”と題する特許出願第１２／１９３，５６３号（代理人管理番号第２２７４８−００１２００１号）、及び２００８年８月１８日出願の“Memory Restore & Garbage Collection”と題する米国特許出願第１２／１９３，６１３号（代理人管理番号第２２７４８−００１３００１号）に関連している。
【背景技術】
【０００４】
フラッシュメモリは、電気的に消去可能なプログラマブルリードオンリメモリ（ＥＥＰＲＯＭ）の一形式である。フラッシュメモリは、不揮発性で且つ比較的高密度であるために、ハンドヘルドコンピュータや、移動電話や、デジタルカメラや、ポータブル音楽プレーヤや、他の記憶解決策（例えば、磁気ディスク）が適さない他の多数の装置において、ファイル及び他の持続性オブジェクトを記憶するのに使用される。不都合なことに、フラッシュメモリは、２つの制約で悩まされている。第１に、メモリの大きなブロックを消去しないと、ビットをクリアできない。第２に、各ブロックは、限定された消去回数しか行えず、それを過ぎると、もはや確実にデータを記憶することができない。これらの制約により、フラッシュメモリを効率的に使用するのに、複雑なデータ構造及びアルゴリズムがしばしば要求される。これらのアルゴリズム及びデータ構造は、データの効率的なノット・イン・プレース(not-in-place)更新をサポートし、消去の回数を減少し、そして装置内のブロックの摩耗を平坦化するために使用される。
【０００５】
フラッシュメモリは、ページを含むブロックが最初に消去されない限り、物理的メモリページへのイン・プレース更新又は再書き込みをサポートしない。この欠点を克服するために、ハードウェア及び／又はソフトウェアレイヤがフラッシュサブシステムにしばしば追加される。フラッシュトランスレーションレイヤ（ＦＴＬ）ともしばしば称されるこのレイヤは、フラッシュメモリと共に、論理的セクタを物理的メモリページへマッピングすることで二次記憶装置を模擬することができる。メモリフラッシュベースの装置の場合に、ＦＴＬは、ハードウェアのコントローラとして実施される。このコントローラは、プロセッサ又はマイクロコントローラを少量の揮発性メモリ（例えば、ＲＡＭ）と共に備えることができる。コントローラは、ファイルシステム（例えば、論理的セクタ）からの読み取り／書き込み要求をフラッシュの特定のブロックにおける読み取り／書き込み動作へと変換し、そして「ガベージコレクション」（ＧＣ）を開始して、汚染ブロックを消去し、解放ブロックを再生利用するという役割を果たすことができる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ランダムアクセス又は更新を要求するフラッシュ装置（例えば、スマートホン）は、ＦＴＬが特別な読み取り／書き込み及びＧＣオペレーションを実行するようにさせる。これら特別なオペレーションは、予想し得ない装置の振舞い及び著しい性能低下を招くことになる。
【課題を解決するための手段】
【０００７】
揮発性及び不揮発性メモリにおいてデータ構造を使用して論理的セクタが物理的ページへとマップされる不揮発性メモリのためのメモリマッピング技術が開示される。ある実施形態において、不揮発性メモリにおける第１のルックアップテーブルは、論理的セクタを物理的ページへと直接マップする。揮発性メモリにおける第２のルックアップテーブルは、不揮発性メモリにおける第１のルックアップテーブルの位置を保持する。ある実施形態において、揮発性メモリにおけるキャッシュは、最も最近書き込まれた論理的セクタの物理的アドレスを保持する。又、ガベージコレクション及び回復オペレーションに使用できるブロックコンテンツを記述するブロックＴＯＣも開示される。
【発明の効果】
【０００８】
ここに開示するメモリマッピング技術は、従来のフラッシュメモリブロックマッピング技術に勝る多数の効果を発揮する。これら効果の幾つかは、次のものを含むが、これらに限定されない。１）論理的セクタを物理的ページへ直接マッピングすることによりブロックマッピングの必要性を排除し、２）現在ブロックの全てのページが割り当てられるまで新たなブロックを割り当てる必要性を排除し、３）異なる論理的エリアに対して異なるジャーナルブロックを割り当てる必要性を排除し、そして４）現在ブロックの全てのページが割り当てられるまでＧＣオペレーションをトリガーする必要性を排除する。
【図面の簡単な説明】
【０００９】
【図１】インデックステーブル及びインデックス目次(table of contents)（ＴＯＣ）を使用して論理的セクタを物理的ページへ直接マッピングするためのメモリマッピングアーキテクチャーを例示するブロック図である。
【図２Ａ】図１に示すメモリマッピングアーキテクチャーを使用する読み取りオペレーションを例示するフローチャートである。
【図２Ｂ】図１に示すメモリマッピングアーキテクチャーを使用する読み取りオペレーションを例示するフローチャートである。
【図３Ａ】図１のメモリマッピングアーキテクチャーを使用する書き込みオペレーションを例示するフローチャートである。
【図３Ｂ】図１のメモリマッピングアーキテクチャーを使用する書き込みオペレーションを例示するフローチャートである。
【図３Ｃ】図１のメモリマッピングアーキテクチャーを使用する書き込みオペレーションを例示するフローチャートである。
【図４Ａ】図１のメモリマッピングアーキテクチャーを使用する回復オペレーションを例示するフローチャートである。
【図４Ｂ】図１のメモリマッピングアーキテクチャーを使用する回復オペレーションを例示するフローチャートである。
【図５Ａ】図１−４及び図７のメモリアーキテクチャー及びオペレーションを実施するためのメモリサブシステムを例示するブロック図である。
【図５Ｂ】図１−４及び図７のメモリアーキテクチャー及びオペレーションを実施するためのメモリサブシステムを含む装置のシステムアーキテクチャーを例示するブロック図である。
【図６】ブロック目次をもつ現在データブロックを例示する図である。
【図７】図６のブロック目次を使用するＧＣオペレーションを例示するフローチャートである。
【発明を実施するための形態】
【００１０】
システムの概略
図１は、ルックアップテーブルを使用して論理的セクタを物理的ページへとマッピングするためのメモリマッピングアーキテクチャー１００を例示するブロック図である。ある実施形態では、揮発性メモリ（例えば、ＲＡＭ）におけるルックアップテーブル１０２は、不揮発性メモリ（例えば、フラッシュメモリ）におけるルックアップテーブル１０６の位置（例えば、物理的アドレス）を保持する。ルックアップテーブル１０６は、データページ１０８の物理的アドレスを保持する。ある実施形態では、揮発性メモリにおけるキャッシュ１０４は、より高速な読み出しを行えるように、最近書き込まれた論理的セクタの物理的アドレスを保持する。ここに示す実施例では、ルックアップテーブル１０２は、インデックスＴＯＣ１０２とも称され、ルックアップテーブル１０６は、インデックステーブル１０６又はインデックスページとも称され、そしてキャッシュ１０４は、インデックステーブルキャッシュ１０４とも称される。
【００１１】
アーキテクチャー１００において、インデックスＴＯＣ１０２は、インデックステーブル１０６を不揮発性メモリに記憶できるようにする。これが効果的であるのは、典型的にコントローラ内に利用できる少量のＲＡＭは、コントローラのコスト、面積及び消費電力の上昇のために拡張できないからである。ある実施形態では、揮発性メモリは、その利用性、或いは他のトリガー事象及び／又は動作モードに基づいて動的に構成することができる。
【００１２】
揮発性メモリにおけるデータ構造の例
ある実施形態において、データブロックは、揮発性メモリに記憶されるブロックテーブルに関連付けることができ、これは、ブロック状態データ（例えば、空き、不良、割り当て済み、現在）、有効ページ番号、消去カウント、及びエラー修正コード（ＥＣＣ）固定カウントを含むことができる。
【００１３】
ある実施形態において、インデックスＴＯＣ１０２の各エントリーは、インデックステーブル１０６のエントリーの不揮発性メモリにおける物理的アドレスと、インデックステーブルキャッシュ１０４のエントリーを指すポインタとを記憶する。インデックステーブル１０６の希望のエントリーがインデックステーブルキャッシュ１０４に記憶されていないことを指示するために、アドレス０ｘｆｆ又は他の指示子をインデックスＴＯＣ１０２のエントリーに配置することができる。
【００１４】
ある実施形態では、揮発性メモリ（例えば、ＲＡＭ）に次の構造を割り当てる必要がある。インデックステーブルキャッシュにおける空きエントリーの数、現在データブロック（例えば、書き込み又は更新オペレーションに使用されるブロック）、現在ブロックにおける次の空きページを指すポインタ、現在ブロックＴＯＣ（例えば、論理的セクタをブロック内のページへとマッピングするための情報を含むブロックに記憶されたＴＯＣ）、現在インデックスブロック（例えば、インデックス更新に使用されるブロック）、インデックスブロックにおける次の空きページを指すポインタ、現在インデックスブロックＴＯＣ、及び空きブロックの数。
【００１５】
ある実施形態では、インデックステーブルキャッシュ１０４の各エントリーは、次のものを含むが、これに限定されない。即ち、データを保持するためのバッファ（例えば、２Ｋバッファ）、状態データ（例えば、清潔、汚染、空き）、カウンタ（例えば、特定のブロックが何回アクセスされたかを示すシリアルカウンタ又はカウント）。
【００１６】
上述したデータ構造は、例示に過ぎず、用途に応じて他のデータ構造を使用することもできる。ブロックＴＯＣのようなデータ構造は、他の図面を参照して詳細に説明する。
【００１７】
読み取りオペレーションの例
図２Ａ−２Ｂは、図１に示すメモリマッピングアーキテクチャーを使用する読み取りオペレーション２００を例示するフローチャートである。
【００１８】
図２Ａを参照すれば、ある実施形態において、読み取りオペレーション２００は、１つ以上の論理的セクタに関連した読み取り要求を得ることにより開始することができる（２０２）。例えば、読み取り要求は、ファイルシステムにより発生することができる。読み取り要求は、第１セクタ番号と、連続するセクタの数とを含むことができる。要求における論理的セクタごとに（２０４）、揮発性メモリのインデックスＴＯＣ（例えば、インデックスＴＯＣ１０２）をチェックして（２０６）、現在論理的セクタに関連したデータページアドレスが揮発性メモリのインデックステーブルキャッシュ（例えば、インデックステーブルキャッシュ１０４）に記憶されるかどうか決定する。データページアドレスがインデックステーブルキャッシュに記憶される場合には（２０８）、データページアドレスがインデックステーブルキャッシュから読み取られ（２１０）、不揮発性メモリで読み取り動作を遂行するのに使用される（２１２）。
【００１９】
データページアドレスがインデックステーブルキャッシュに記憶されない場合には（２０８）、データページアドレスを記憶する当該インデックステーブルエントリの物理的ページアドレスがインデックスＴＯＣから読み取られ（２１４）、データページアドレスを記憶する当該インデックステーブルエントリがインデックステーブルエントリから読み取られ、インデックステーブルキャッシュに記憶される（２１６）。次いで、データページアドレスがインデックステーブルキャッシュから読み取られ、不揮発性メモリで読み取り動作を遂行するのに使用される（２１２）。
【００２０】
より多くの論理的セクタを処理する必要がある場合には（２０４）、読み取りオペレーション２００のために全ての論理的セクタが処理されるまで、次のステップが繰り返される。
【００２１】
ある実施形態では、ステップ２１６の間に、インデックステーブルキャッシュがいっぱいになった場合に、インデックステーブルキャッシュの古いデータページアドレスをフラッシュして、不揮発性メモリのインデックステーブルから読み取られた新たなデータページのための余地を作ることができる。インデックステーブルキャッシュをフラッシュすると、不揮発性メモリへの不必要な書き込みオペレーションがトリガーされる。この不必要な書き込みオペレーションを回避するために、揮発性メモリにオーバーフローバッファを形成し、これを使用して、不揮発性メモリのインデックステーブルから読み取られたデータページアドレスを記憶することができる。オーバーフローバッファを読み取って、読み取りオペレーション２００に使用するためのデータページアドレスを得ることができる。従って、揮発性メモリにオーバーフローバッファを形成することで、読み取り動作中に不揮発性メモリへの不必要な書き込みオペレーションを防止することができる。
【００２２】
図１を参照すれば、揮発性メモリのインデックスＴＯＣ１０２は、読み取られるべきデータページ１０８の物理的ページアドレスを保持するインデックステーブル１０６に関する情報を含む。インデックステーブル１０６は、揮発性メモリのインデックステーブルキャッシュ１０４に記憶されるか、又は不揮発性メモリのインデックスブロックに記憶される。インデックステーブル１０６がインデックステーブルキャッシュ１０４に記憶される場合には、インデックステーブルキャッシュ１０４からインデックステーブル１０６を読み取り、それを使用して、不揮発性メモリにおいて読み取られるべきデータページ１０８の物理的アドレスを見出すことができる。インデックステーブル１０６がインデックステーブルキャッシュ１０４に記憶されない場合には、データページアドレスを不揮発性メモリのインデックステーブル１０６の当該エントリーからインデックステーブルキャッシュ１０４へ読み取ることができる。インデックステーブルキャッシュ１０４からデータページアドレスを読み取り、これを使用して、不揮発性メモリのデータページ１０８で読み取りオペレーションを遂行することができる。
【００２３】
ある実施形態では、読み取りオペレーション２００は、論理的セクタ番号（Ｌｐｎ）と、読み取るべき連続する論理的セクタの数とを得る。読み取りオペレーション２００は、論理的セクタ番号を不揮発性メモリにおける物理的位置へとマップする。２ＫＢのページサイズを仮定すれば、次のような擬似コードを使用して、読み取りオペレーション２００のための幾つかの例示的ステップを説明することができる。
ステップ１：ｉｎｄｅｘＰａｇｅ＝ｒｅａｄＰｈｙｓｉｃａｌＰａｇｅ（ＴＯＣ［Ｌｐｎ／５１２］）
ステップ２：ｄａｔａＢｕｆｆｅｒ＝ｒｅａｄＰｈｙｓｉｃａｌＰａｇｅ（ｉｎｄｅｘＰａｇｅ［Ｌｐｎ％５１２］）
ステップ３：ｒｅｔｕｒｎ  ｄａｔａＢｕｆｆｅｒ
ここで、ｒｅａｄＰｈｙｓｉｃａｌＰａｇｅは、物理的ページを指すポインタを返送する機能であり、ＴＯＣ［］及びｉｎｄｅｘＰａｇｅ［］は、各々、ＴＯＣエントリー及びｉｎｄｅｘＰａｇｅエントリーを記憶するためのアレイであり、そして５１２は、インデックステーブルエントリによりマップされるデータページの数である（５１２＊４バイト＝２ＫＢ）。この例では、形式ｉｎｄｅｘＰａｇｅは、インデックステーブルの出発アドレス（ポインタ）を保持し、そして形式ｄａｔａＢｕｆｆｅｒは、読み取られるべき論理的セクタ番号Ｌｐｎに対応するデータページの出発アドレス（ポインタ）を保持する。
【００２４】
書き込みオペレーションの例
図３Ａ−３Ｃは、図１に示すアーキテクチャーを使用する書き込みオペレーション３００を例示するフローチャートである。
【００２５】
図３Ａ及び３Ｂを参照すれば、ある実施形態において、書き込みオペレーション３００は、１つ以上の論理的セクタに関連した書き込み要求を得ることにより開始することができる（３０２）。例えば、書き込み要求は、ファイルシステムによって発生することができる。書き込み要求は、第１の論理的セクタアドレスと、書き込むべき連続する論理的セクタの数とを含むことができる。要求における論理的セクタごとに（３０３）、現在データブロックがいっぱいである場合に（３０４）、図６を参照して述べるように、現在データブロックのページ（例えば、最終ページ）にブロックＴＯＣを書き込む（３０６）。
【００２６】
現在データブロックは、更新に使用されるアクティブなブロックである。ブロックＴＯＣは、ブロック内の全てのページを記述する不揮発性メモリのページ（例えば、ブロック内の最終ページ）である。ブロックＴＯＣは、図４Ａ−４Ｂを参照して述べるように、全ブロックをスキャニング（読み取り）せずに揮発性メモリ（ＲＡＭ）において一時的インデックステーブルを再構成するための回復オペレーションに使用することができる。又、ブロックＴＯＣは、図７を参照して述べるように、ＧＣオペレーションに使用することもできる。
【００２７】
図３Ｂを参照すれば、空きブロックを使用できる場合（３０８）、その使用可能な空きブロックは、新たな現在データブロックとして割り当てることができる（３１２）。空きブロックが使用できない場合（３０８）（例えば、空きブロックの数がスレッシュホールド値より低い場合）、空きブロックのスレッシュホールド数を満足するまでＧＣオペレーションを遂行して空きブロックを発生することができる（３１０）。次いで、空きブロックを現在データブロックとして割り当てることができる（３１２）。現在データブロックがいっぱいでない場合には（３０４）、図３Ｃに示すように、書き込みオペレーション３００は、ステップ３１４へと続く。
【００２８】
ある実施形態では、現在データブロックのブロックＴＯＣは、現在データブロックがいっぱいになり且つ新たな現在データブロックが割り当てられるまで、揮発性メモリに記憶することができる。そのとき、古い現在データブロックのブロックＴＯＣは、不揮発性メモリ（例えば、現在データブロックの最終ページ）へ書き込むことができ、そして新たな現在データブロックのブロックＴＯＣは、揮発性メモリにおいてリセットすることができる。
【００２９】
図３Ｃを参照すれば、書き込みオペレーションは、ページを現在データブロックへ逐次に書き込み、そして揮発性メモリにおいて現在ブロックＴＯＣを更新することにより継続する（３１４）。現在データブロックのための有効ページカウントが更新される（例えば、適当な数だけ増加又は減少される）。インデックステーブルキャッシュが、書き込まれたセクタに関連したインデックスページを含む場合には、それが更新される（３２０）。ある実施形態では、有効なページカウントをブロックテーブル５１３（図５）に記憶することができる。
【００３０】
書き込まれたセクタに関連したインデックステーブルエントリがインデックステーブルキャッシュに存在せず（３１８）、又、インデックステーブルキャッシュに使用可能な空きスペースがある（３２２）場合には、インデックスＴＯＣに記憶されると共に揮発性メモリのインデックステーブルキャッシュに記憶された位置を使用して不揮発性メモリからインデックスページが読み取られる（３２６）。キャッシュに空きスペースがない場合には（３２２）、古いキャッシュページを不揮発性メモリに対してフラッシュして（３２４）、不揮発性メモリから読み取られた新たなページを記憶するためのスペースをキャッシュにおいて解放することができる。インデックステーブルキャッシュにおいてスペースが解放された後に、ステップ（３２２）において条件が満足され、インデックスＴＯＣに記憶された位置を使用して不揮発性メモリからインデックスページが読み取られ、揮発性メモリのインデックステーブルキャッシュに記憶される（３２６）。
【００３１】
ある実施形態では、書き込みオペレーション３００は、論理的セクタ番号（Ｌｐｎ）と、書き込むべき連続する論理的セクタの数とを得る。次いで、書き込みオペレーション３００は、全てのページを、更新に使用される不揮発性メモリの現在データブロックへと順次に記憶する。現在データブロックがいっぱいの場合には、新たな現在データブロックを更新のために割り当てることができる。新たな現在データブロックを割り当てる必要があり、且つ充分な空きブロックがない場合には、ＧＣオペレーションを空きブロックに対して遂行することができる。次のような擬似コードを使用して書き込みオペレーション３００を説明することができる。
ステップ１：新たなブロックを割り当てる（任意）。
ステップ２：新たなブロックが必要で且つ充分な空きブロックがない場合には、ＧＣオペレーションを遂行して空きブロックを発生する（任意）。
ステップ３：Ｌｐｎを表すｄａｔａＢｕｆｆｅｒを現在データブロック（Ｃｖｂｎ）へ書き込み、物理的ページ番号（Ｖｐｎ）をメモリに記憶する。
ステップ４：Ｌｐｎに関連したインデックスページがインデックスキャッシュにあるかどうかチェックし、もしそうであれば、ステップ６へ進む。
ステップ５：インデックスキャッシュがいっぱいであるかどうかチェックし、もしそうであれば、ステップ７へ進まない。
ステップ６：キャッシュからのインデックスページの１つを書き込み、インデックスＴＯＣにおいてそれに関連したエントリーをフラッシュし更新する。
ステップ７：Ｌｐｎに関連したインデックスページをインデックスキャッシュへ読み込む：ｉｎｄｅｘＰａｇｅ＝ｒｅａｄＰｈｙｓｉｃａｌＰａｇｅ（ＴＯＣ［Ｌｐｎ／５１２］）。
ステップ８：Ｌｐｎに関連したインデックスページのエントリーを更新する：ｉｎｄｅｘＰａｇｅ［Ｌｐｎ％５１２］＝Ｖｐｎ。
【００３２】
ステップ１及び２は、任意であることに注意されたい。ステップ１は、現在データブロック状態（例えば、現在ブロックがどの程度いっぱいか）に依存し、又、ステップ２は、どれほど多くの空きブロックを使用できるかに依存する。
【００３３】
特別な読み取り／書き込みオペレーションの実行を回避するために、インデックステーブルページの幾つかを揮発性メモリ（例えば、コントローラのＲＡＭ）に記憶することができる。これらのページは、キャッシュ記憶のインデックステーブルページとして定義することができる。キャッシュサイズは、動的に構成可能であり、例えば、システムＲＡＭ利用性及び／又は動作モードに依存する。動作モードは、例えば、歌がホストコンピュータの歌ライブラリーと同期されるｉＰｏｄ（登録商標）「同期モード」である。この「同期」モードでは、例えば、バッファが解放されて、読み取り／書き込みメモリオペレーションに使用される。
【００３４】
ブロックＴＯＣを使用するガベージコレクションの例
媒体が完全に使用されると、来るべき更新に対してもはや有効ではないデータによって占有されたブロックを解放するために、ＧＣオペレーションを使用することができる。「最良の候補」ブロックは、最低量の有効ページしかもたないブロックである。ＧＣオペレーションを開始するための多数のトリガーがあり、これは、空きブロックの数が規定限界より下がったときに、読み取り／書き込み妨害質低下（長期間消去されていない古いブロックのリフレッシュ）に応答して、新たな不良ブロックを発見する、等を含むが、これに限定されない。
【００３５】
ＧＣオペレーションは、ブロックＴＯＣから読み取られたページメタデータから利益を得ることができる。ＧＣオペレーションは、典型的に、低速であり、各ページメタデータが実際にブロック内の有効ページの１つであるかどうかを確立するためにそれを読み出すことを必要とする（実際上、１ページ全体を読み取ることを意味する）。ページメタデータの当該部分は、ブロックＴＯＣによって与えられ、これは、コントローラが、不必要なメモリアクセスを実行せずに、ＧＣオペレーションを有効に管理できるようにする。
【００３６】
ある実施形態では、現在インデックスブロックに対するブロックＴＯＣが生成されて、揮発性メモリ内にポピュレートされる。各ブロックＴＯＣエントリーは、現在データブロックにおけるページに対応することができる。現在データブロックにおける各ページが書き込まれるときに、ブロックＴＯＣの対応エントリーが、そのページに対応する対応論理的セクタ番号で更新される。現在データブロックがいっぱいになると、現在データブロックの最終ページにブロックＴＯＣが書き込まれる。例えば、図６に示すように、完全ブロック６００の最終ページ（例えば、ページＮ）にブロックＴＯＣ６０２を書き込むことができる。ブロックＴＯＣ６０２が最終ページに書き込まれた後に、新たなブロックを現在データブロックとして割り当てることができる。
【００３７】
新たなブロックを使用できない場合には、ＧＣオペレーションを実行して完全ブロックを解放することができる。ＧＣオペレーションに対する「最良の候補ブロック」は、最低量の有効ページしかもたない完全ブロックである。というのは、ブロックを消去できる前に無効ページが新たなページにコピーされないからである。従って、ＧＣオペレーションに対する「最良の候補ブロック」を決定するために、メモリシステムは、各完全ブロックにおける有効ページのカウントを決定する。所与のページが有効であるかどうか決定するために、ページをブロックから読み出し、そして不揮発性メモリにおけるインデックステーブル１０６の対応エントリーと相互参照することができる。しかしながら、この相互参照オペレーションは、望ましからぬ書き込みオペレーションをトリガーして、不揮発性メモリにおけるインデックステーブル１０６から揮発性メモリにおけるキャッシュへインデックスページを転送することがある。この不必要な書き込みオペレーションを軽減するために、メモリシステムは、ブロックＴＯＣのエントリーからページに対応する論理的セクタ番号を読み取り、ページが有効であるかどうか決定することができる。ある実施形態では、論理的セクタ番号とインデックステーブルページとの相互参照を簡単化するために、ブロックＴＯＣエントリーが分類される（例えば、同様の論理的セクタ番号をクラスター化するために次第に増加する順に分類される）。同じ論理的セクタ番号に対応するページは無効であり、ページ全体を読み取らずに消去することができる。ある実施形態では、図６に示すように、有効ページカウントを、揮発性メモリにおけるブロックテーブル５１３（図５Ａ及び５Ｂ）に記憶することができる。
【００３８】
ガベージコレクションオペレーションの例
図７は、図６のブロックＴＯＣを使用するＧＣオペレーション７００を例示するフローチャートである。ある実施形態では、ＧＣオペレーション７００は、ブロックテーブルを読み取って、候補ブロックを決定し（７０２）、候補ブロックのブロックＴＯＣを読み取って、ブロックのコンテンツを記述するメタデータを得る（７０４）ことを含む。この例では、情報は、ブロックのページに関連した論理的セクタ番号を含む。
【００３９】
ある実施形態では、論理的セクタ番号は、分類基準に基づいて分類される（例えば、次第に増加する順に分類される）（７０６）。分類により同じ論理的セクタ番号クラスターが生じ、これは、分類された論理的セクタ番号をインデックスページと相互参照して候補ブロックにおける無効ページを決定する次のステップを容易にする（７０８）。候補ブロックにおける無効ページは、現在ブロックが消去されるまで新たなブロックへコピーされない。各有効ページは、不揮発性メモリから揮発性メモリへ読み取られる。例えば、図３Ａ−３Ｃを参照して述べたように新たなページを書き込むためのプロセスを使用して現在ブロックへページを書き込むために書き込みセクタプロセスが実行される。
【００４０】
ブロックＴＯＣを使用する回復オペレーションの例
図４Ａ−４Ｂは、図１のアーキテクチャーを使用する回復オペレーション４００を例示するフローチャートである。この回復オペレーション４００は、破滅的事象（例えば、停電）のために失われるインデックステーブル１０６及びインデックスＴＯＣ１０２を再現するのに使用できる。ある実施形態では、回復オペレーション４００は、ブロックごとに第１ページを読み取ることにより開始される（４０２）。ブロックが空きである場合には（４０４）、ブロックは、インデックステーブルにおける空きブロックとしてセットされる（４０６）。ブロックが空きでなく（４０４）且つブロックがインデックスブロックである（４０８）場合には、インデックスブロックを消去することができ（４１０）、ブロックテーブルにおける空きブロックとしてセットされる（４０６）。ブロックが空きでもインデックスブロックでもない（４０８）場合には、ブロックを、それらの年齢に応じて分類される割り当てられたブロックのリストに挿入することができる（４１２）。
【００４１】
図４Ｂを参照すれば、分類されたリストにおけるブロックごとに、ステップ４１５−４２２は、次のように遂行することができる。ブロックＴＯＣがブロックから読み取られる（４１５）。ブロックＴＯＣが存在する場合には（４１６）、ブロックＴＯＣを使用して揮発性メモリにおける一時的なインデックステーブルを更新することができる（４１８）。ブロックＴＯＣが存在しない場合には（４１６）、完全ブロックスキャンを使用してブロックの各ページを読み取ることができ（４２０）、有効なページカウント及び一時的なインデックステーブルが更新される（４２２）。分類されたブロックがステップ４１５−４２２により処理された後に、一時的なインデックステーブルを不揮発性メモリに書き込むことができ（４２４）、インデックスＴＯＣを揮発性メモリにおいて発生することができ（４２６）、そして一時的インデックステーブルを揮発性メモリにおいて解除することができる（４２８）。
【００４２】
ある実施形態では、リストは、ブロックの年齢に基づいて、増加する順序で分類され、「最も若い」又は最も最近割り当てられたデータが、分類されたリストの最上部に来るようにされる。これは、分類された順序で「最も若い」から「最も年長」へと進みながら、各論理的セクタの最も新鮮なコピーが得られることを保証する。
【００４３】
ある実施形態では、より小さなメモリ占有面積で回復オペレーション４００を機能させることができるように各部分でインデックステーブルを回復することができる。これは、例えば、揮発性メモリが一時的インデックステーブルを受け入れるに充分な大きさでない場合に行うことができる。この場合には、回復オペレーション４００は、インデックステーブルの一部分をカバーするバッファを割り当てることができる。回復オペレーションを繰り返すたびに、割り当てられたインデックスバッファによりカバーできるデータ範囲が再マップされる。繰り返し数は、インデックスバッファのサイズに比例する。例えば、インデックスバッファが大きいほど、各繰り返しで大きなデータ範囲がカバーされるので、繰り返しが少なくて済む。
【００４４】
メモリサブシステムの例
図５Ａは、図１−４及び図７のメモリアーキテクチャー及びオペレーションを実施するためのメモリサブシステムを例示するブロック図である。ある実施形態では、サブシステム５００は、コントローラ５０２と、不揮発性メモリ５０４と、ホストインターフェイス５０６とを含むことができる。コントローラ５０２は、揮発性メモリ５１０（例えば、ＲＡＭ）及びプロセッサ５０８を含むことができる。揮発性メモリ５１０は、ブロックＴＯＣ５１２と、ブロックテーブル５１３と、インデックステーブルキャッシュ５１４とを記憶する。揮発性メモリ５１０は、利用性及び他の適当なファクタに基づいてプロセッサ５０８により動的に構成することができる。不揮発性メモリ５０４は、インデックステーブル５１６及びデータページ５１８を含むことができる。サブシステム５００は、明瞭化のために図５から省略された他のコンポーネントを含むことができる。
【００４５】
オペレーション中に、ホストインターフェイス５０６は、ホストシステムからバス（例えば、ＩＤＥ／ＡＴＴ）を経て読み取り／書き込み要求を得ることができる。ホストインターフェイス５０６は、データ、アドレス及び制御信号を受信するための回路及びソフトウェアを含むことができる。読み取り／書き込み要求は、論理的セクタ番号と、読み取り／書き込みすべき連続する論理的セクタの数とを含むことができる。
【００４６】
プロセッサ５０８は、揮発性メモリ５１０にアクセスし、インデックスＴＯＣ５１２を読み取って、インデックステーブルキャッシュ５１４が論理的セクタに対する物理的アドレスを含むかどうか決定することができる。インデックステーブルキャッシュ５１４が物理的アドレスを含む場合には、その物理的アドレスが読み取り／書き込みオペレーションに使用される。インデックステーブルキャッシュ５１４が物理的アドレスを含まない場合には、プロセッサ５０８は、揮発性メモリ５１０にアクセスして、インデックスＴＯＣを読み取り、不揮発性メモリ５０４におけるインデックステーブル５１６のページアドレスを得る。プロセッサ５０８は、インデックステーブル５１６における物理的アドレスを使用して、読み取り／書き込みオペレーション中にデータページ５１８へのメモリマッピングを遂行することができる。ブロックテーブル５１３は、図７を参照して述べたように、「最良の候補ブロック」を決定するのに使用できるブロックに対する有効ページカウントを記憶することができる。
【００４７】
ある実施形態では、データページ５１８、インデックスＴＯＣ５１２及び／又はインデックステーブル５１６を、１つ以上の異なるメモリ装置において実施することができる。
【００４８】
図５Ｂは、図１−４及び図７のメモリアーキテクチャー及びオペレーションを実施するためのメモリサブシステムを含む装置５２０を例示するブロック図である。ある実施形態では、装置５２０は、例えば、メディアプレーヤ装置、パーソナルデジタルアシスタント、移動電話、ポータブルコンピュータ、デジタルカメラ、等のポータブル装置である。
【００４９】
装置５２０は、ホストコントローラ（又はいわゆる「システム・オン・チップ」即ち「ＳｏＣ」５２２、及び不揮発性メモリ５２８を備えている。装置５２０は、ホストコントローラ５２２及び不揮発性メモリ５２８の外部の付加的なメモリを含むのも任意である。ホストコントローラ５２２は、１つ以上のプロセッサ５２４及び揮発性メモリ５２６を含む。ある実施形態では、揮発性メモリ５２６は、スタティックなランダムアクセスメモリ（ＳＲＡＭ）である。ホストコントローラ５２２は、図２−４を参照して述べたオペレーションを含む種々の処理オペレーション及び入力／出力オペレーションを遂行する。例えば、ホストコントローラ５２２は、ユーザ入力を受け取って処理し、出力を発生し、メディア（例えば、オーディオ、ビデオ、グラフィック）デコーディング及び処理オペレーション、他の処理オペレーション、等を遂行することができる。ホストコントローラ５２２は、揮発性メモリ５２６からデータを読み取り且つ揮発性メモリ５２６へデータを書き込むことができる。又、ホストコントローラ５２２は、インターフェイス（図示せず）を通して不揮発性メモリ５２８へ読み取り又は書き込みオペレーションを発生することもできる。
【００５０】
ある実施形態では、不揮発性メモリ５２８は、ＮＡＮＤフラッシュメモリである。他の実施形態では、不揮発性メモリ５２８は、別の形式の不揮発性メモリ、例えば、ＮＯＲフラッシュメモリ、他の形式のソリッドステートメモリ、又はハードディスクドライブである。又、装置５２０は、明瞭化のために図５Ｂから省略されている１つ以上の他のコンポーネントを含むこともできる。
【００５１】
幾つかの実施形態を説明したが、種々の変更がなされ得ることを理解されたい。例えば、１つ以上の実施形態の要素を組み合わせ、削除し、変更し、又は補足して、更に別の実施形態を形成することができる。更に別の例として、図示された論理的フローは、望ましい結果を達成するために、図示された特定の順序又は逐次の順序を必要とするものではない。更に、上述したフローに他のステップを設けてもよく、又はそこからステップを除去してもよいし、上述したシステムに他のコンポーネントを追加してもよく、又はそこから除去してもよい。従って、これらの他の実施形態は、特許請求の範囲内に包含される。
【符号の説明】
【００５２】
１００：メモリマッピングアーキテクチャー
１０２：インデックスＴＯＣ
１０４：インデックステーブルキャッシュ
１０６：インデックステーブル
１０８：データページ
５０２：メモリコントローラ
５０４：不揮発性メモリ
５０６：ホストインターフェイス
５０８：プロセッサ
５１０：揮発性メモリ
５１２：インデックスＴＯＣ
５１３：ブロックテーブル
５１４：インデックステーブルキャッシュ
５１６：インデックステーブル
５１８：データページ
５２２：ホストコントローラ
５２４：プロセッサ
５２６：揮発性メモリ
５２８：不揮発性メモリ
【図１】
2011511388.tif 000003
【図２Ａ】
2011511388.tif 000004
【図２Ｂ】
2011511388.tif 000005
【図３Ａ】
2011511388.tif 000006
【図３Ｂ】
2011511388.tif 000007
【図３Ｃ】
2011511388.tif 000008
【図４Ａ】
2011511388.tif 000009
【図４Ｂ】
2011511388.tif 000010
【図５Ａ】
2011511388.tif 000011
【図５Ｂ】
2011511388.tif 000012
【図６】
2011511388.tif 000013
【図７】
2011511388.tif 000014
【手続補正書】
【提出日】平成22年10月1日(2010.10.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
不揮発性メモリの第１ページアドレスに対応する１つ以上の論理的セクタに関連した読み取り要求を得、
前記第１ページアドレスが揮発性メモリにおけるインデックステーブルキャッシュに含まれるかどうか決定し、
前記第１ページアドレスが前記インデックステーブルキャッシュに含まれる場合は、
前記第１ページアドレスを前記インデックステーブルキャッシュから読み取り、
前記第１ページアドレスを使用して読み取りオペレーションを遂行し、
前記第１ページアドレスが前記インデックステーブルキャッシュに含まれない場合は、
前記揮発性メモリにおけるインデックス目次（ＴＯＣ）から、前記第１ページアドレスを記憶している不揮発性メモリのインデックステーブルエントリーの第２ページアドレスを得、
前記インデックステーブルエントリーから前記第１ページアドレスを読み取り、
前記第１ページアドレスを使用して読み取りオペレーションを遂行する、
ことを含む方法。
【請求項２】
前記揮発性メモリにおけるインデックステーブルキャッシュに前記第１ページアドレスを記憶することを更に含む、請求項１に記載の方法。
【請求項３】
メモリの利用性、１つ以上のトリガー事象、又は１つ以上の動作モードに基づいて前記揮発性メモリを動的に構成することを更に含む、請求項１に記載の方法。
【請求項４】
１つ以上の論理的セクタに関連した書き込み要求を得、
現在データブロックがいっぱいであるかどうか決定し、
前記現在データブロックがいっぱいである場合には、
前記現在データブロックのページにブロック目次（ＴＯＣ）を書き込み、
前記現在データブロックがいっぱいでない場合には、
前記現在データブロックに１つ以上のページを書き込み、
現在ブロックＴＯＣを更新し、
前記現在データブロックに対する有効なページコンテンツを更新する、
ことを含む方法。
【請求項５】
前記現在データブロックがいっぱいである場合には、
空きブロックを使用できるかどうか決定し、
空きブロックを使用できる場合には、その空きブロックを現在データブロックとして割り当て、
空きブロックを使用できない場合には、ガベージコレクションオペレーションを遂行して、空きブロックを発生する、
ことを含む請求項４に記載の方法。
【請求項６】
前記現在データブロックいっぱいでない場合には、
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含むかどうか決定し、
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含む場合には、有効なページカウントを更新する、
ことを含む請求項４に記載の方法。
【請求項７】
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含まない場合には、
インデックステーブルキャッシュに空きスペースがあるかどうか決定し、
インデックステーブルキャッシュに空きスペースがある場合には、インデックステーブルキャッシュに記憶された位置を使用してインデックスページを読み取り、
インデックステーブルキャッシュに空きスペースがない場合には、インデックステーブルキャッシュから古いページをフラッシュする、
ことを含む請求項６に記載の方法。
【請求項８】
前記ブロックＴＯＣは、現在データブロックの最終ページに書き込まれる、請求項４に記載の方法。
【請求項９】
インデックステーブルキャッシュ及びインデックス目次を記憶する揮発性メモリと、
論理的セクタに対応するページアドレスを記憶するインデックステーブルを記憶する不揮発性メモリと、
前記揮発性メモリ及び不揮発性メモリに結合されたコントローラであって、
論理的セクタに関連した読み取り要求を得、
前記論理的セクタに関連した第１ページアドレスがインデックステーブルキャッシュに含まれるかどうか決定し、
前記第１ページアドレスが前記インデックステーブルキャッシュに含まれる場合は、
前記第１ページアドレスを前記インデックステーブルキャッシュから読み取り、
前記第１ページアドレスを使用して読み取りオペレーションを遂行し、
更に、前記第１ページアドレスが前記インデックステーブルキャッシュに含まれない場合は、
前記揮発性メモリにおけるインデックス目次から、前記第１ページアドレスを記憶している不揮発性メモリのインデックステーブルエントリーの第２ページアドレスを得、
前記インデックステーブルエントリーから前記第１ページアドレスを読み取り、
前記第１ページアドレスを前記インデックステーブルキャッシュに記憶する、
ように動作できるコントローラと、
を備えたメモリシステム。
【請求項１０】
前記コントローラは、前記揮発性メモリにおけるインデックステーブルキャッシュに前記第１ページアドレスを記憶するように動作できる、請求項９に記載のメモリシステム。
【請求項１１】
前記コントローラは、メモリの利用性、１つ以上のトリガー事象、又は１つ以上の動作モードに基づいて前記揮発性メモリを動的に構成するように動作できる、請求項９に記載のメモリシステム。
【請求項１２】
インデックステーブルキャッシュ及びインデックス目次を記憶する揮発性メモリと、
論理的セクタに対応するページアドレスを記憶するエントリーをもつインデックステーブルを記憶する不揮発性メモリと、
前記揮発性メモリ及び不揮発性メモリに結合されたコントローラであって、
１つ以上の論理的セクタに関連した書き込み要求を得、
現在データブロックがいっぱいであるかどうか決定し、
前記現在データブロックがいっぱいである場合には、
前記現在データブロックのページにブロック目次（ＴＯＣ）を書き込み、
前記現在データブロックがいっぱいでない場合には、
前記現在データブロックに１つ以上のページを書き込み、
現在ブロックＴＯＣを更新し、
前記現在データブロックに対する有効なページコンテンツを更新する、
ように動作できるコントローラと、
を備えたメモリシステム。
【請求項１３】
前記現在データブロックがいっぱいである場合には、
空きブロックを使用できるかどうか決定し、
空きブロックを使用できる場合には、その空きブロックを現在データブロックとして割り当て、
空きブロックを使用できない場合には、ガベージコレクションオペレーションを遂行して、空きブロックを発生する、
ことを含む請求項１２に記載のメモリシステム。
【請求項１４】
前記現在データブロックいっぱいでない場合には、
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含むかどうか決定し、
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含む場合には、有効なページカウントを更新する、
ことを含む請求項１２に記載のメモリシステム。
【請求項１５】
インデックステーブルキャッシュが、書き込まれた論理的セクタに関連したインデックスページを含まない場合には、
インデックステーブルキャッシュに空きスペースがあるかどうか決定し、
インデックステーブルキャッシュに空きスペースがある場合には、インデックステーブルキャッシュに記憶された位置を使用してインデックスページを読み取り、
インデックステーブルキャッシュに空きスペースがない場合には、インデックステーブルキャッシュから古いページをフラッシュする、
ことを含む請求項１４に記載のメモリシステム。
【請求項１６】
前記ブロックＴＯＣは、現在データブロックの最終ページに書き込まれる、請求項１２に記載のメモリシステム。
【請求項１７】
第１メモリにおけるデータページに対応する論理的セクタを読み取り又は書き込むための要求を得、
第２メモリにおける第１ルックアップテーブルを読み取って、第１メモリにおける第２ルックアップテーブルの位置を決定し、
第２ルックアップテーブルを読み取って、論理的セクタとデータページとの間のマッピングを決定する、
ことを含む方法。
【請求項１８】
不揮発性メモリから第１ルックアップテーブルを、そして揮発性メモリから第２ルックアップテーブルを読み取ることを更に含む、請求項１７に記載の方法。
【請求項１９】
論理的セクタとデータページとの間のマッピングを決定し、
そのマッピングを使用して不揮発性メモリからデータページを読み取る、
ことを更に含む請求項１８に記載の方法。
【請求項２０】
論理的セクタとデータページとの間のマッピングを決定し、
そのマッピングを使用してデータページへデータを書き込む、
ことを更に含む、請求項１８に記載の方法。
【請求項２１】
前記第１ルックアップテーブルは、目次であり、前記第２ルックアップテーブルは、インデックステーブルであり、前記インデックス目次は、インデックステーブルエントリーのページアドレスを記憶し、そしてインデックステーブルエントリーは、データページアドレスを記憶する、請求項１８に記載の方法。
【国際調査報告】
2011511388.tif 000015
2011511388.tif 000016
2011511388.tif 000017
2011511388.tif 000018
2011511388.tif 000019