(57)【要約】【課題】パフォーマンスが高いメモリシステムを提供すること。【解決手段】メモリシステムは、不揮発性の第１メモリと、メモリコントローラとを備える。メモリコントローラは、論理アドレスと物理アドレスとを対応付ける第１論物変換情報を複数の第２論物変換情報に分割して管理し、複数の第２論物変換情報のそれぞれを冗長情報を付して第１メモリに格納する。メモリコントローラは、複数の第２論物変換情報のうちの第３論物変換情報を使用する場合、複数の第２論物変換情報のうちの第３論物変換情報を含む複数の第２論物変換情報である複数の第４論物変換情報を読み出す。そして、メモリコントローラは、複数の第４論物変換情報のうちから第３論物変換情報と異なる第５論物変換情報を複数の第４論物変換情報のそれぞれに付された冗長情報に基づいて選択する。そして、メモリコントローラは、第５論物変換情報を第２メモリにキャッシュする。【選択図】図５
2019159791.tif 000002
【特許請求の範囲】
【請求項１】
ホストに接続可能なメモリシステムであって、
不揮発性の第１メモリと、
論理アドレスと物理アドレスとを対応付ける第１論物変換情報を複数の第２論物変換情報に分割して管理し、前記複数の第２論物変換情報のそれぞれを冗長情報を付して前記第１メモリに格納し、前記複数の第２論物変換情報のうちの一である第３論物変換情報を使用する場合、前記第１メモリに格納された前記複数の第２論物変換情報のうちの前記第３論物変換情報を含む複数の第２論物変換情報である複数の第４論物変換情報を読み出して、前記複数の第４論物変換情報のうちから前記第３論物変換情報と異なる第５論物変換情報を前記複数の第４論物変換情報のそれぞれに付された冗長情報に基づいて選択し、前記第５論物変換情報を第２メモリにキャッシュする、メモリコントローラと、
を備えるメモリシステム。
【請求項２】
前記複数の第２論物変換情報のそれぞれに付された前記冗長情報は、対応する第２論物変換情報によってカバーされる論理アドレス範囲を示し、
前記メモリコントローラは、前記第５論物変換情報に付加された前記冗長情報が示す論理アドレス範囲をタグ情報として登録する、
請求項１に記載のメモリシステム。
【請求項３】
前記複数の第４論物変換情報は、前記第１メモリの連続する領域に格納されている、
請求項１に記載のメモリシステム。
【請求項４】
誤り訂正回路をさらに備え、
前記複数の第４論物変換情報は、前記誤り訂正回路による誤り訂正のための１つのフレームに含まれる、
請求項１に記載のメモリシステム。
【請求項５】
前記第１論物変換情報は階層構造を有し、
前記複数の第２論物変換情報のそれぞれに付された前記冗長情報は、属する階層を示す階層情報を含み、
前記メモリコントローラは、前記複数の第４論物変換情報のそれぞれに付された前記冗長情報に含まれる階層情報に基づいて前記第５論物変換情報を選択する、
請求項１に記載のメモリシステム。
【請求項６】
前記第２メモリは、前記ホストに具備される、
請求項１に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、メモリシステムに関する。
【背景技術】
【０００２】
従来、ＮＡＮＤ型のフラッシュメモリ（以降、ＮＡＮＤメモリ）を備えるメモリシステムが知られている。メモリシステムは、ホストとＮＡＮＤメモリとの間のデータ転送を制御するメモリコントローラを具備する。メモリコントローラは、論理アドレスと物理アドレスとの対応を論物変換情報として管理する。論理アドレスは、メモリシステムがホストに提供する論理アドレス空間内の位置を示す位置情報である。物理アドレスは、ＮＡＮＤメモリ内の物理的な位置を示す位置情報である。
【０００３】
メモリコントローラは、論物変換情報を、ＲＡＭ（Random  Access  Memory）などの高速な動作が可能なメモリにキャッシュして、キャッシュにヒットした場合に、キャッシュされた論物変換情報を使用する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願公開第２０１７／００６８６２１号明細書
【特許文献２】米国特許出願公開第２０１５／００７４３３４号明細書
【特許文献３】特開２００８−２４２９４４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
一つの実施形態は、パフォーマンスが高いメモリシステムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
一つの実施形態によれば、メモリシステムは、ホストに接続可能である。メモリシステムは、不揮発性の第１メモリと、メモリコントローラとを備える。メモリコントローラは、論理アドレスと物理アドレスとを対応付ける第１論物変換情報を複数の第２論物変換情報に分割して管理し、複数の第２論物変換情報のそれぞれを冗長情報を付して第１メモリに格納する。メモリコントローラは、複数の第２論物変換情報のうちの一である第３論物変換報を使用する場合、第１メモリに格納された複数の第２論物変換情報のうちの第３論物変換情報を含む複数の第２論物変換情報である複数の第４論物変換情報を読み出す。そして、メモリコントローラは、複数の第４論物変換情報のうちから第３論物変換情報と異なる第５論物変換情報を複数の第４論物変換情報のそれぞれに付された冗長情報に基づいて選択する。そして、メモリコントローラは、第５論物変換情報を第２メモリにキャッシュする。
【図面の簡単な説明】
【０００７】
【図１】図１は、第１の実施形態のメモリシステムの構成を示す図である。
【図２】図２は、第１の実施形態のＮＡＮＤメモリに格納されるデータを示す図である。
【図３】図３は、第１の実施形態の論物変換情報のデータ構造を説明するための図である。
【図４】図４は、第１の実施形態の冗長情報の構成を示す図である。
【図５】図５は、第１の実施形態のメモリシステムの動作の概要を説明するための図である。
【図６】図６は、第１の実施形態のメモリシステムのキャッシュ動作を示すフローチャートである。
【図７】図７は、第２の実施形態の論物変換情報のデータ構造を説明するための図である。
【図８】図８は、第２の実施形態の冗長情報のデータ構造を示す図である。
【図９】図９は、第２の実施形態のメモリシステムのキャッシュ動作を示すフローチャートである。
【図１０】図１０は、第３の実施形態の論物変換テーブルがキャッシュされる位置を説明するための図である。
【発明を実施するための形態】
【０００８】
以下に添付図面を参照して、実施形態にかかるメモリシステムを詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【０００９】
（第１の実施形態）
図１は、第１の実施形態のメモリシステムの構成を示す図である。メモリシステム１は、ホスト２と接続される。接続の規格としては、任意の規格が採用され得る。ホスト２は、例えばパーソナルコンピュータ、携帯情報端末、またはサーバなどである。
【００１０】
メモリシステム１は、ホスト２からアクセス要求（リード要求およびライト要求）を受け付けることができる。各アクセス要求は、アクセス先を示す論理アドレスを伴う。論理アドレスは、メモリシステム１がホスト２に提供する論理アドレス空間内の位置を示す位置情報である。メモリシステム１は、ライト要求とともに、書き込み対象のデータを受信する。以降、ホスト２から受信した書き込み対象のデータを、ユーザデータと表記する。
【００１１】
メモリシステム１は、ＮＡＮＤ型のフラッシュメモリ（ＮＡＮＤメモリ）１０と、ホスト２とＮＡＮＤメモリ１０との間のデータ転送を実行するメモリコントローラ２０と、を備える。
【００１２】
ＮＡＮＤメモリ１０は、不揮発性の第１メモリの一例である。第１メモリとしては、任意の種類の不揮発性のメモリが採用され得る。
【００１３】
ＮＡＮＤメモリ１０は、複数のブロックからなるメモリセルアレイを備える。各ブロックに格納されているデータは、一括してイレースされる。各ブロックは、複数のページを備える。メモリセルアレイへのデータの書き込みおよびメモリセルアレイからのデータの読み出しは、ページ単位で実行される。
【００１４】
図２は、第１の実施形態のＮＡＮＤメモリ１０に格納されるデータを示す図である。本図に示されるように、ＮＡＮＤメモリ１０には、ユーザデータ１００と、論物変換情報２００と、が格納される。
【００１５】
ユーザデータ１００は、前述したように、ホスト２から受信したデータである。ユーザデータ１００は、メモリコントローラ２０において所定の処理が実施され、その後にＮＡＮＤメモリ１０に格納される。所定の処理は、誤り訂正のための符号化を含む。
【００１６】
論物変換情報２００は、論理アドレスと物理アドレスとの対応関係を示す情報である。物理アドレスは、ＮＡＮＤメモリ１０内の物理的な位置を示す位置情報である。
【００１７】
例えば、メモリシステム１がホスト２から新しくユーザデータ１００を受信すると、そのユーザデータ１００（新しいユーザデータ１００）は、空き領域を有するブロックに格納される。新しいユーザデータ１００がそのブロックに格納されると、論物変換情報２００が更新される。新しいユーザデータ１００の論理アドレスは、論物変換情報の更新によって、新しいユーザデータ１００が格納された位置を示す物理アドレスに対応付けられる。
【００１８】
メモリシステム１がホスト２からリード要求を受信すると、そのリード要求に伴う論理アドレスに対応する物理アドレスが、論物変換情報２００に基づいて特定される。即ち、論理アドレスが物理アドレスに変換される。そして、得られた物理アドレスが示す位置からユーザデータ１００が読み出されてホスト２に転送される。
【００１９】
第１の実施形態では、論物変換情報２００は、１つのルートテーブル２１０と、複数の論物変換テーブル２２０と、によって構成される。
【００２０】
図３は、第１の実施形態の論物変換情報２００のデータ構造を説明するための図である。本図では、複数の論物変換テーブル２２０として、４つの論物変換情報２２０ａ〜２２０ｄを図示している。４つの論物変換情報２２０ａ〜２２０ｄは、同様のデータ構造を有している。本図では代表として、論物変換情報２２０ａについてのみ詳細なデータ構造を図示している。
【００２１】
第１の実施形態では、メモリシステム１がホスト２に提供する論理アドレス空間は、複数のリージョンに分割される。各リージョンは、論理アドレス空間内の連続した領域であり、所定数の論理アドレスを含む。各論物変換テーブル２２０は、１つのリージョンに含まれる所定数の論理アドレスのそれぞれを、物理アドレスに対応付ける。ルートテーブル２１０は、リージョン毎に、対応する論物変換テーブル２２０が格納されている位置を示す。
【００２２】
図３の例によれば、論理アドレス空間は、２ａ個のリージョンに分割されており、各リージョンは、論理アドレスの上位側のａビットによって識別される。ここで、ａは正の整数である。ルートテーブル２１０は、論理アドレスの上位側のａビットを、論物変換テーブル２２０の位置を示す物理アドレスに対応付ける。そのためのデータ構造の一例として、ルートテーブル２１０は、２ａ個のレコードを備える。各レコードには、対応する論物変換テーブル２２０が格納されている位置を示す物理アドレスが記録されている。ルートテーブル２１０では、各レコードは、論理アドレスの順番で配列されている。
【００２３】
さらに、図３の例によれば、各リージョンは、連続する２ｂ個の論理アドレスを含む。ここで、ｂは正の整数である。各論物変換テーブル２２０は、対応するリージョン内の連続する２ｂ個の論理アドレスのそれぞれを、物理アドレスに対応付ける。そのためのデータ構造の一例として、各論物変換テーブル２２０は、２ｂ個のレコードを備える。各レコードには、対応するユーザデータ１００が格納されている位置を示す物理アドレスが記録されている。各論物変換テーブル２２０では、各レコードは、論理アドレスの順番で配列されている。
【００２４】
変換対象の論理アドレスの上位側のａビットを検索キーとして用いてルートテーブル２１０を検索することによって、対応する論物変換テーブル２２０が格納されている位置が特定される。そして、特定された位置に格納されている論物変換テーブル２２０を、変換対象の論理アドレスの下位側のｂビットを検索キーとして用いて検索することによって、変換対象の論理アドレスに対応する物理アドレスが取得される。
【００２５】
各論物変換テーブル２２０には、冗長情報２２１が付されている。例えば、論物変換テーブル２２０ａ、２２０ｂ、２２０ｃ、２２０ｄには、冗長情報２２１ａ、２２１ｂ、２２１ｃ、２２１ｄが付されている。
【００２６】
第１の実施形態では、図４に例示されるように、冗長情報２２１には、論理アドレス範囲が記録されている。論理アドレス範囲は、論物変換テーブル２２０がカバーする論理アドレスの範囲である。論理アドレス範囲は、例えば、リージョンを示す論理アドレス（論理アドレスの上位側のａビット）によって表現される。第１の実施形態では、各論物変換テーブル２２０がカバーする論理アドレスの範囲の大きさ（リージョンの大きさ）は一定であるので、論理アドレス範囲は、先頭の論理アドレスのみで表現されてもよい。論理アドレス範囲は、論物変換テーブル２２０がカバーする論理アドレスの範囲の先頭の論理アドレスと末尾の論理アドレスとで表現されてもよい。論理アドレス範囲は、論物変換テーブル２２０がカバーする論理アドレスの範囲の先頭の論理アドレスとサイズ情報とで表現されてもよい。
【００２７】
論物変換テーブル２２０がＮＡＮＤメモリ１０に格納される際には、誤り訂正に備えて、ＥＣＣ（Error  Correction  Circuit）２９によって符号化される。具体的には、ＥＣＣ２９は、複数の論物変換テーブル２２０から誤り訂正符号２３１を生成し、複数の論物変換テーブル２２０と誤り訂正符号２３１とを含む１つのフレーム２３０を生成する。生成されたフレーム２３０は、ＮＡＮＤメモリ１０内の連続する領域に格納される。
【００２８】
図３の例によれば、フレーム２３０ａは、４個の論物変換テーブル２２０ａ〜２２０ｄを含み、論物変換テーブル２２０ａ〜２２０ｄの符号化によって生成された誤り訂正符号２３１ａを含む。また、フレーム２３０ｂは、複数の論物変換テーブル２２０（不図示）と誤り訂正符号２３１ｂを含む。１つのフレーム２３０に含まれる論物変換テーブル２２０の数は、固定されていてもよいし、固定されていなくてもよい。
【００２９】
論物変換テーブル２２０のＮＡＮＤメモリ１０からの読み出しの際には、少なくともその論物変換テーブル２２０を含む１つのフレーム２３０が読み出され、そのフレーム２３０に含まれる誤りの検出および訂正が実行される。
【００３０】
図１に説明を戻す。メモリコントローラ２０は、ホスト２とＮＡＮＤメモリ１０との間のユーザデータ１００の転送や論物変換情報２００の管理を含めた、種々の制御を実行する。メモリコントローラ２０は、ＣＰＵ（Central  Processing  Unit）２１、ホストＩ／Ｆ（Interface）２２、リードコントローラ２３、ライトコントローラ２４、リード用メモリ２５、ライト用メモリ２６、キャッシュメモリ２７、タグメモリ２８、およびＥＣＣ２９を備える。
【００３１】
なお、コントローラ２０は、例えばＳｏＣ（System-On-a-Chip）として構成され得る。コントローラ２０は、複数のチップによって構成されてもよい。コントローラ２０は、ＣＰＵ２１に代えて、ＦＰＧＡ（field-programmable  gate  array）やＡＳＩＣ（application  specific  integrated  circuit）を備えていてもよい。つまり、コントローラ２０は、ソフトウェア、ハードウェア、またはこれらの組み合わせによって構成され得る。
【００３２】
リード用メモリ２５、ライト用メモリ２６、キャッシュメモリ２７、およびタグメモリ２８は、高速動作が可能な種類のメモリによって構成される。リード用メモリ２５、ライト用メモリ２６、キャッシュメモリ２７、およびタグメモリ２８は、例えば、ＳＲＡＭ（Static  Random  Access  Memory）、ＤＲＡＭ（Dynamic  Random  Access  Memory）、フリップフロップ、またはこれらの組み合わせによって構成される。リード用メモリ２５、ライト用メモリ２６、キャッシュメモリ２７、およびタグメモリ２８のうちの一部または全部は、１つのメモリに統合されてもよい。また、リード用メモリ２５、ライト用メモリ２６、キャッシュメモリ２７、およびタグメモリ２８のうちの一部または全部は、メモリコントローラ２０の外に設けられてもよい。
【００３３】
ライト用メモリ２６は、ホスト２からＮＡＮＤメモリ１０へのデータ転送に使用されるバッファメモリである。リード用メモリ２５は、ＮＡＮＤメモリ１０からホスト２へのデータ転送に使用されるバッファメモリである。
【００３４】
ホストＩ／Ｆ２２は、ホスト２と通信を行うためのインタフェース回路である。ホストＩ／Ｆ２２は、ホスト２からアクセス要求や書き込み対象のユーザデータ１００を受信したり、ホスト２に対して応答やリード要求による読み出し対象のユーザデータ１００を送信したりする。
【００３５】
ライトコントローラ２４は、ＮＡＮＤメモリ１０への書き込みを制御する回路である。ライトコントローラ２４は、ホストＩ／Ｆ２２がホスト２からユーザデータ１００を受信すると、当該ユーザデータ１００をライト用メモリ２６に一時的に格納する。そして、所定の条件が満たされると、ライトコントローラ２４は、ライト用メモリ２６に格納されたユーザデータ１００をＮＡＮＤメモリ１０に格納する。
【００３６】
また、ライトコントローラ２４は、ユーザデータ１００のＮＡＮＤメモリ１０への書き込みの際に、そのユーザデータ１００の位置を指定する論理アドレス（即ちライト要求に伴って送られてきた論理アドレス）とそのユーザデータ１００の書き込み先の物理アドレスとの対応を例えばライト用メモリ２６などに記憶しておく。そして、所定の条件が満たされたとき、ライトコントローラ２４は、記憶された対応を用いて複数の論物変換訳テーブル２２０を生成する。ライトコントローラ２４は、複数の論物変換テーブル２２０のそれぞれに、冗長情報２２１を付与する。ライトコントローラ２４は、それぞれ冗長情報２２１が付与された複数の論物変換テーブル２２０を、ＥＣＣ２９を介してＮＡＮＤメモリ１０に１つのフレーム２３０として書き込む。ライトコントローラ２４は、論物変換テーブル２２０をＮＡＮＤメモリ１０に書き込んだことに応じて、ルートテーブル２１０を更新する。
【００３７】
ＥＣＣ２９は、ＮＡＮＤメモリ１０に格納されるデータに対し、誤り訂正のための符号化を行い、フレームを生成する。特に、ＥＣＣ２９は、ライトコントローラ２４によって生成された、それぞれそれぞれ冗長情報２２１が付与された複数の論物変換テーブル２２０を符号化して１つのフレーム２３０を生成する。
【００３８】
また、ＥＣＣ２９は、ＮＡＮＤメモリ１０から読み出されたデータをフレーム単位で復号化し、誤りの検出および訂正を実行する。特に、ＥＣＣ２９は、ＮＡＮＤメモリ１０から読み出されたフレーム２３０に対し、そのフレーム２３０に含まれた誤り訂正符号２３１に基づき、誤りの検出および訂正を実行する。
【００３９】
なお、ＥＣＣ２９が実行する符号化／復号化の方式は、特定の方式に限定されない。ＥＣＣ２９は、例えば、ＬＤＰＣ（Low  Density  Parity  Check）に基づく符号化／復号化を実行してもよい。
【００４０】
リードコントローラ２３は、ＮＡＮＤメモリ１０からの読み出しを制御する回路である。リードコントローラ２３は、ホストＩ／Ｆ２２からリード要求を受信すると、論物変換情報２００に基づき、リード要求に伴って送られてきた論理アドレスを物理アドレスに変換する。そして、リードコントローラ２３は、変換によって得られた物理アドレスが示すＮＡＮＤメモリ１０内の位置からユーザデータ１００を少なくともフレームの単位で読み出す。ＥＣＣ２９は、読み出されたユーザデータ１００に対し、フレームの単位で誤りの検出および訂正を実行する。リードコントローラ２３は、誤りが訂正されたユーザデータ１００をリード用メモリ２５に格納する。その後、リードコントローラ２３は、リード用メモリ２５内のユーザデータ１００をホストＩ／Ｆ２２を介してホスト２に送信する。
【００４１】
ここで、リードコントローラ２３は、１以上の論物変換テーブル２２０をキャッシュメモリ２７にキャッシュし、変換を行う際には、キャッシュメモリ２７にキャッシュされた論物変換テーブル２２０を使用する。変換対象の論理アドレスの変換に必要な論物変換テーブル２２０（以降、対象の論物変換テーブル２２０）がキャッシュメモリ２７にキャッシュされていない場合、リードコントローラ２３は、対象の論物変換テーブル２２０をＮＡＮＤメモリ１０から読み出して、読み出した対象の論物変換テーブル２２０をキャッシュメモリ２７に格納する。
【００４２】
ここで、論物変換テーブル２２０は、復号化のために、少なくともフレーム２３０の単位で読み出される。第１の実施形態では、リードコントローラ２３は、対象の論物変換テーブル２２０をキャッシュメモリ２７にキャッシュするだけでなく、対象の論物変換テーブル２２０と同じフレーム２３０に含まれる他の論物変換テーブル２２０をキャッシュメモリ２７にキャッシュすることができる。
【００４３】
キャッシュメモリ２７は、１以上の論物変換テーブル２２０がキャッシュされ得るメモリである。タグメモリ２８は、タグ情報が記録されるメモリである。所望の論物変換テーブル２２０のタグ情報がタグメモリ２８に存在する場合、その論物変換テーブル２２０は、キャッシュメモリ２７にキャッシュされているとみなされる。所望の論物変換テーブル２２０のタグ情報がタグメモリ２８に存在しない場合、その論物変換テーブル２２０は、キャッシュメモリ２７にキャッシュされていないとみなされる。
【００４４】
なお、キャッシュメモリ２７およびタグメモリ２８に適用される連想方式は特定の方式に限定されない。例えば、フルアソシアティブ方式、ダイレクトマップ方式、またはｎウェイセットアソシアティブ方式が採用され得る。
【００４５】
ＣＰＵ２１は、メモリコントローラ２０に具備される各構成要素を統括的に制御する回路である。ＣＰＵ２１は、所定のプログラムに基づいて制御を実行する。
【００４６】
図５は、第１の実施形態のメモリシステム１の動作の概要を説明するための図である。リードコントローラ２３は、タグメモリ２８を検索して、対象の論物変換テーブル２２０がキャッシュメモリ２７にキャッシュされているか否かを判定する（Ｓ１０１）。タグメモリ２８は、キャッシュメモリ２７にキャッシュされている論物変換テーブル２２０を示すタグ情報が記録（登録）されたメモリである。
【００４７】
一例では、対応するリージョンを示す論理アドレス範囲がタグ情報として使用される。Ｓ１０１では、変換対象の論理アドレスを検索キーとして使用されてタグメモリ２８が検索される。タグメモリ２８に記録されたいずれかのタグ情報に変換対象の論理アドレスが含まれていれば、キャッシュヒットと判定される。タグメモリ２８に記録されたいずれのタグ情報にも変換対象の論理アドレスが含まれていない場合、キャッシュミスと判定される。
【００４８】
キャッシュヒットした場合、リードコントローラ２３は、キャッシュメモリ２７にキャッシュされた、変換対象の論理アドレスを含む論理アドレス範囲の論物変換テーブル２２０を用いて変換を実行する。
【００４９】
キャッシュミスした場合（Ｓ１０２）、即ち対象の論物変換テーブル２２０がキャッシュメモリ２７にキャッシュされていないことが判明した場合、リードコントローラ２３は、対象の論物変換テーブル２２０を含むフレーム２３０をＮＡＮＤメモリ１０から読み出す（Ｓ１０３）。ＮＡＮＤメモリ１０から読み出されたフレーム２３０は、ＥＣＣ２９によって復号化され、誤りの検出および訂正が実行される（Ｓ１０４）。
【００５０】
その後、リードコントローラ２３は、そのフレーム２３０に含まれる全ての論物変換テーブル２２０を冗長情報２２１とともにキャッシュメモリ２７に格納する（Ｓ１０５）。なお、ここでは、フレーム２３０には、論理アドレス範囲“A”、“B”、“C”、“D”にかかる４つの論物変換テーブル２２０が含まれ、論理アドレス範囲“A”にかかる論物変換テーブル２２０が対象の論物変換テーブル２２０であることとしている。
【００５１】
リードコントローラ２３は、対象の論物変換テーブル２２０をキャッシュデータとして登録し、キャッシュメモリ２７に格納された対象の論物変換テーブル２２０を用いて変換を実行する（Ｓ１０６）。対象の論物変換テーブル２２０は、タグ情報がタグメモリ２８に記録されることでキャッシュデータとして登録される。即ち、冗長情報２２１に記録されていた論理アドレス範囲“A”が、タグメモリ２８に記録される。
【００５２】
さらに、リードコントローラ２３は、Ｓ１０５の処理によってキャッシュメモリ２７に格納された各論物変換テーブル２２０の冗長情報２２１に基づき、対象の論物変換テーブル２２０を除く他の論物変換テーブル２２０から所定の条件を満たす論物変換テーブル２２０を選択し、選択した論物変換テーブル２２０をキャッシュデータとして登録する（Ｓ１０７）。本図では一例として、同一のフレーム２３０に含まれる他の全ての論物変換テーブル２２０（論理アドレス範囲“B”〜“D”にかかる論物変換テーブル２２０）が選択され、登録されたこととしている。
【００５３】
このように、リードコントローラ２３は、対象の論物変換テーブル２２０だけでなく、対象の論物変換テーブル２２０と同じフレーム２３０に含まれる他の論物変換テーブル２２０をキャッシュメモリ２７にキャッシュすることができる。よって、後に当該他の論物変換テーブル２２０が必要になったとき、キャッシュヒットする。論物変換情報２００にかかるキャッシュヒット率が向上するので、リード要求を処理するパフォーマンスが向上する。
【００５４】
なお、論物変換テーブル２２０の選択方法は、特定の方法に限定されない。例えば、有効な論物変換テーブル２２０は選択され、無効な論物変換テーブル２２０は選択されない。有効な論物変換テーブル２２０とは、同一のリージョンにかかる１以上の論物変換テーブル２２０のうちの最新の論物変換テーブル２２０をいう。無効な論物変換テーブル２２０とは、同一のリージョンにかかる複数の論物変換テーブル２２０がＮＡＮＤメモリ１０に存在する場合において、その複数の論物変換テーブル２２０のうちの最新の論物変換テーブル２２０を除く論物変換テーブル２２０をいう。
【００５５】
ある論物変換テーブル２２０が有効であるか無効であるかは、その論物変換テーブル２２０が格納されている位置がルートテーブル２１０によって何れかの論理アドレスに対応付けられているか否かに基づいて判定可能である。例えば、論物変換テーブル２２０の冗長情報２２１に記録された論理アドレス範囲をルートテーブル２１０を用いて物理アドレスに変換し、その論物変換テーブル２２０が格納されていた位置を示す物理アドレスが得られた場合、その論物変換テーブル２２０は、有効な論物変換テーブル２２０であると判定される。その論物変換テーブル２２０が格納されていた位置を示す物理アドレスが得られなかった場合、その論物変換テーブル２２０は、無効な論物変換テーブル２２０であると判定される。
【００５６】
なお、論物変換テーブル２２０が有効であるか無効であるかの判定方法は上記の方法に限定されない。冗長情報２２１に基づいて論物変換テーブル２２０が有効であるか無効であるかが判定できればよい。
【００５７】
図６は、第１の実施形態のメモリシステム１のキャッシュ動作を示すフローチャートである。本図に示される動作は、対象の論物変換テーブル２２０を使用する際に実行される。
【００５８】
リードコントローラ２３は、まず、タグメモリ２８を検索することによって、対象の論物変換テーブル２２０がキャッシュメモリ２７にキャッシュされているか否かを判定する（Ｓ２０１）。例えば、リードコントローラ２３は、変換対象の論理アドレスを検索キーとしてタグメモリ２８を検索する。
【００５９】
タグメモリ２８の検索の結果、キャッシュミスした場合（Ｓ２０２、Ｙｅｓ）、リードコントローラ２３は、ルートテーブル２１０に基づき、対象の論物変換テーブル２２０の格納位置を特定する（Ｓ２０３）。
【００６０】
Ｓ２０３では、リードコントローラ２３は、例えば、ＮＡＮＤメモリ１０に格納されているルートテーブル２１０を参照する。または、リードコントローラ２３は、ルートテーブル２１０を高速動作が可能なメモリ（例えばリード用メモリ２５）に予めロードしておき、当該ロードされたルートテーブル２１０を参照してもよい。
【００６１】
続いて、リードコントローラ２３は、ＮＡＮＤメモリ１０の特定された位置から、対象の論物変換テーブル２２０を含むフレーム２３０を読み出す（Ｓ２０４）。その際、ＥＣＣ２９は、誤りの検出および訂正を実行する（Ｓ２０５）。誤りの訂正後、リードコントローラ２３は、フレーム２３０に含まれていた全ての論物変換テーブル２２０を冗長情報２２１とともにキャッシュメモリ２７に格納する（Ｓ２０６）。
【００６２】
なお、論物変換テーブル２２０が格納されるキャッシュラインの選択方法は、特定の方法に限定されない。例えば、ＬＲＵ（Least  Recently  Used）によってキャッシュラインが選択されてもよいし、ラウンドロビン（Round  Robin）方式によってキャッシュラインが選択されてもよい。ランダムにキャッシュラインが選択されてもよい。
【００６３】
続いて、リードコントローラ２３は、対象の論物変換テーブル２２０を示すタグ情報をタグメモリ２８に登録する（Ｓ２０７）。これにより、対象の論物変換テーブル２２０がキャッシュメモリ２７にキャッシュされる。
【００６４】
続いて、リードコントローラ２３は、対象の論物変換テーブル２２０と同一のフレーム２３０に含まれていた他の論物変換テーブル２２０の冗長情報２２１をキャッシュメモリ２７から取得する（Ｓ２０８）。そして、リードコントローラ２３は、対象の論物変換テーブル２２０と同一のフレーム２３０に含まれていた他の論物変換テーブル２２０のうちから、論物変換テーブル２２０を、それぞれの冗長情報２２１に基づいて選択する（Ｓ２０９）。そして、リードコントローラ２３は、選択された論物変換テーブル２２０を示すタグ情報をタグメモリ２８に登録する（Ｓ２１０）。これにより、選択された論物変換テーブル２２０がキャッシュメモリ２７にキャッシュされる。
【００６５】
キャッシュヒットした場合（Ｓ２０２、Ｎｏ）、またはＳ２１０の処理によって、キャッシュ動作が完了する。リードコントローラ２３は、キャッシュメモリ２７にキャッシュされた対象の論物変換テーブル２２０を使用することによって変換を実行することができる。
【００６６】
なお、Ｓ２０６の処理では、リードコントローラ２３は、フレーム２３０に含まれる全ての論物変換テーブル２２０をキャッシュメモリ２７に格納する、として説明した。リードコントローラ２３は、フレーム２３０に含まれる全ての論物変換テーブル２２０を、冗長情報２２１とともに、キャッシュメモリ２７とは異なるメモリ（例えばリード用メモリ２５）に格納し、その後、対象の論物変換テーブル２２０と、冗長情報２２１に基づいて選択された論物変換テーブル２２０と、をキャッシュメモリ２７にキャッシュしてもよい。また、リードコントローラ２３は、必ずしも冗長情報２２１をキャッシュメモリ２７に残さなくてもよい。
【００６７】
また、図６に図示される処理は、リードコントローラ２３またはＥＣＣ２９によって実行されることとして説明した。図６に図示される処理のうちの一部または全部は、メモリコントローラ２０に具備される他の構成要素（例えばＣＰＵ２１）によって実行されてもよい。
【００６８】
また、論物変換テーブル２２０は、リード要求の処理以外においても使用され得る。例えば、メモリコントローラ２０は、ユーザデータ１００のリロケーションを実行する際に論物変換テーブル２２０を参照してもよい。リロケーションは、例えば、ガベージコレクションまたはリフレッシュを含む。また、メモリコントローラ２０は、ホスト２からのライト要求に伴う、論理アドレスと物理アドレスとの対応関係の更新の際に論物変換テーブル２２０を参照してもよい。また、メモリコントローラ２０は、Unmap処理（Trim処理とも呼ばれる）の際に論物変換テーブル２２０を参照してもよい。メモリコントローラ２０は、リード要求の処理に限らず、論物変換テーブル２２０を使用（参照）する際には、図６に示される一連の処理を実行してもよい。
【００６９】
以上述べたように、第１の実施形態によれば、メモリコントローラ２０は、論理アドレス空間の分の論理アドレスと物理アドレスとの対応を、複数の論物変換テーブル２２０に分割して管理する。そして、メモリコントローラ２０は、各論物変換テーブル２２０を冗長情報２２１を付してＮＡＮＤメモリ１０に格納する。そして、メモリコントローラ２０は、対象の論物変換テーブル２２０を含むフレーム２３０をＮＡＮＤメモリ１０から読み出して、そのフレーム２３０に含まれる複数の論物変換テーブル２２０のうち、対象の論物変換テーブル２２０を除く論物変換テーブル２２０を冗長情報２２１に基づいて選択し、対象の論物変換テーブル２２０と選択された論物変換テーブル２２０とをキャッシュメモリ２７にキャッシュする。
【００７０】
この構成により、メモリコントローラ２０は、対象の論物変換テーブル２２０だけでなく、対象の論物変換テーブル２２０と同じタイミングで読み出された他の論物変換テーブル２２０をキャッシュメモリ２７に格納することができる。よって、キャッシュメモリ２７のキャッシュラインを効率的に埋めていくことができる。その結果、キャッシュヒット率が向上し、メモリシステム１のパフォーマンスが向上する。
【００７１】
なお、論物変換テーブル２２０のＮＡＮＤメモリ１０からの読み出しの単位は、フレーム２３０だけに限定されない。例えば、リードコントローラ２３は、対象の論物変換テーブル２２０の格納位置を含む連続した領域（例えば１つのページ）から、全ての論物変換テーブル２２０を一括して読み出してもよい。そして、リードコントローラ２３は、一括して読み出された論物変換テーブル２２０のうちから、冗長情報２２１に基づいて、キャッシュメモリ２７にキャッシュされる論物変換テーブル２２０を選択してもよい。
【００７２】
また、第１の実施形態によれば、メモリコントローラ２０は、冗長情報２２１に含まれる、論物変換テーブル２２０がカバーする論理アドレス範囲を、タグ情報として登録する。よって、変換対象の論理アドレスを検索キーとしてタグメモリ２８を検索することによって、キャッシュヒット／ミスの判定を行うことが可能となる。
【００７３】
（第２の実施形態）
論物変換情報２００は、階層構造を有し得る。
【００７４】
図７は、第２の実施形態の論物変換情報２００のデータ構造を説明するための図である。論物変換情報２００は、複数の階層の論物変換テーブル２２０として、ルートテーブル２１０側（上位側）から、第１階層の論物変換テーブル２２０、第２階層の論物変換テーブル２２０、および第３階層の論物変換テーブル２２０を備える。なお、本図では、一例として、第１階層の論物変換テーブル２２０として論物変換テーブル２２０ｅ、２２０ｆが描画され、第２階層の論物変換テーブル２２０として論物変換テーブル２２０ｇ、２２０ｈが描画され、第３階層の論物変換テーブル２２０として論物変換テーブル２２０ｉ、２２０ｊ、２２０ｋが描画されている。論物変換情報２００を構成する各階層の論物変換テーブル２２０の数はこれらに限定されない。
【００７５】
ルートテーブル２１０の各レコードには、第１階層に属する論物変換テーブル２２０が格納されている位置を示す物理アドレスが記録される。第１階層に属する各論物変換テーブル２２０の各レコードには、第２階層に属する論物変換テーブル２２０が格納されている位置を示す物理アドレスが記録される。第２階層に属する各論物変換テーブル２２０の各レコードには、第３階層に属する論物変換テーブル２２０が格納されている位置を示す物理アドレスが記録される。第３階層に属する各論物変換テーブル２２０の各レコードには、ユーザデータ１００が格納されている位置を示す物理アドレスが記録される。
【００７６】
リードコントローラ２３は、論理アドレスを４つのビット列に分割し、各ビット列を用いてルートテーブル２１０および各階層に属する論物変換テーブル２２０を参照する。例えば、論理アドレスの最上位側のビット列は、ルートテーブル２１０の参照に使用される。論理アドレスの最上位側から２番目のビット列は、ルートテーブル２１０の参照によって特定された第１階層に属する論物変換テーブル２２０の参照に使用される。論理アドレスの最上位側から３番目のビット列は、第１階層に属する論物変換テーブル２２０の参照によって特定された第２階層に属する論物変換テーブル２２０の参照に使用される。論理アドレスの最下位側のビット列は、第２階層に属する論物変換テーブル２２０の参照によって特定された第３階層に属する論物変換テーブル２２０の参照に使用される。
【００７７】
このように、ルートテーブル２１０と複数階層の論物変換テーブル２２０とによって、論理アドレスが、ユーザデータ１００の格納位置を示す物理アドレスに変換される。
【００７８】
第１の実施形態と同様に、ＮＡＮＤメモリ１０には、複数の論物変換テーブル２２０を含むフレーム２３０が符号化されて格納される。１つのフレーム２３０には、任意の階層の論物変換テーブル２２０が含まれ得る。各論物変換テーブル２２０には、ライトコントローラ２４によって冗長情報２２１が付与される。
【００７９】
図８は、第２の実施形態の冗長情報２２１のデータ構造を示す図である。本図に示されるように、第２の実施形態では、冗長情報２２１には、論理アドレス範囲のほかに、階層情報が含まれる。階層情報は、論物変換テーブル２２０が属する階層を示す情報である。例えば、第ｉ階層に属する論物変換テーブル２２０の階層情報には、「ｉ」が記録されている。
【００８０】
各論物変換テーブル２２０は、所属する階層に関係なくキャッシュメモリ２７にキャッシュされ得る。タグメモリ２８には、例えば、論理アドレス範囲と階層情報との対がタグ情報として登録される。
【００８１】
図９は、第２の実施形態のメモリシステム１のキャッシュ動作を示すフローチャートである。
【００８２】
リードコントローラ２３は、まず、タグメモリ２８を検索することによって、対象の論物変換テーブル２２０がキャッシュメモリ２７にキャッシュされているか否かを判定する（Ｓ３０１）。リードコントローラ２３は、変換対象の論理アドレスを検索キーとして使用する。
【００８３】
タグメモリ２８の検索の結果、キャッシュミスした場合（Ｓ３０２、Ｙｅｓ）、リードコントローラ２３は、対象の論物変換テーブル２２０の格納位置を特定する（Ｓ３０３）。
【００８４】
Ｓ３０３では、例えば、リードコントローラ２３は、１階層だけ上位のテーブル（ルートテーブル２１０または論物変換テーブル２２０）を取得し、参照する。
【００８５】
続いて、リードコントローラ２３は、ＮＡＮＤメモリ１０の特定された位置から、対象の論物変換テーブル２２０を含むフレーム２３０を読み出す（Ｓ３０４）。その際、ＥＣＣ２９は、誤りの検出および訂正を実行する（Ｓ３０５）。誤りの訂正後、リードコントローラ２３は、フレーム２３０に含まれていた全ての論物変換テーブル２２０を冗長情報２２１とともにキャッシュメモリ２７に格納する（Ｓ３０６）。
【００８６】
続いて、リードコントローラ２３は、対象の論物変換テーブル２２０を示すタグ情報をタグメモリ２８に登録する（Ｓ３０７）。これにより、対象の論物変換テーブル２２０がキャッシュメモリ２７にキャッシュされる。
【００８７】
続いて、リードコントローラ２３は、対象の論物変換テーブル２２０と同一のフレーム２３０に含まれていた他の論物変換テーブル２２０の冗長情報２２１をキャッシュメモリ２７から取得する（Ｓ３０８）。そして、リードコントローラ２３は、冗長情報２２１に基づき、対象の論物変換テーブル２２０と同一のフレーム２３０に含まれていた他の論物変換テーブル２２０のうちから、所定の階層よりも上位の階層に属する論物変換テーブル２２０を選択する（Ｓ３０９）。そして、リードコントローラ２３は、選択された論物変換テーブル２２０を示すタグ情報をタグメモリ２８に登録する（Ｓ３１０）。これにより、選択された論物変換テーブル２２０がキャッシュメモリ２７にキャッシュされる。
【００８８】
キャッシュヒットした場合（Ｓ３０２、Ｎｏ）、またはＳ３１０の処理によって、対象の論物変換テーブル２２０にかかるキャッシュ動作が完了する。リードコントローラ２３は、キャッシュメモリ２７にキャッシュされた対象の論物変換テーブル２２０を使用することによって変換を実行することができる。
【００８９】
このように、第２の実施形態によれば、論物変換情報２００は、階層構造を有している。各論物変換テーブル２２０に付された冗長情報２２１は、所属する階層を示す階層情報を含む。メモリコントローラ２０は、階層情報に基づいて、所定の階層よりも上位の階層に属する論物変換テーブル２２０を選択し、対象の論物変換テーブル２２０と選択した論物変換テーブル２２０とをキャッシュメモリ２７にキャッシュする。
【００９０】
上位側の論物変換テーブル２２０がカバーする論理アドレス範囲は、下位側の論物変換テーブル２２０がカバーする論理アドレス範囲よりも広い。上記の方法によれば、上位側の論物変換テーブル２２０を優先的にキャッシュメモリ２７にキャッシュすることができるので、キャッシュヒット率が向上する。
【００９１】
なお、階層構造に基づく論物変換テーブル２２０の選択方法は、これに限定されない。例えば、所定の階層よりも下位の階層に属する論物変換テーブル２２０が選択されてキャッシュメモリ２７にキャッシュされてもよい。論理アドレスを物理アドレスに変換するプロセスにおいては、下位側の論物変換テーブル２２０は、上位側の論物変換テーブル２２０よりも物理アドレスを得るまでに要する処理量が少ない。よって、下位側の論物変換テーブル２２０を優先的にキャッシュメモリ２７にキャッシュすれば、キャッシュヒットした場合において変換にかかる時間が短縮される。
【００９２】
（第３の実施形態）
第１の実施形態および第２の実施形態によれば、メモリシステム１内のキャッシュメモリ２７に論物変換テーブル２２０がキャッシュされた。論物変換テーブル２２０は、ホスト２にキャッシュされてもよい。
【００９３】
例えば、図１０に示されるように、ホスト２は、メインメモリ３０を備える。メインメモリ３０には、メモリシステム１が使用可能なキャッシュエリアが確保されている。メモリシステム１は、キャッシュエリア３１に論物変換テーブル２２０をキャッシュする。
【００９４】
キャッシュエリア３１に論物変換テーブル２２０をキャッシュする際には、メモリコントローラ２０は、ホスト２に対し、論物変換テーブル２２０をキャッシュエリア３１に書き込むためのライト要求を送信する。キャッシュエリア３１にキャッシュされた論物変換テーブル２２０を参照する際には、メモリコントローラ２０は、ホスト２に対し、論物変換テーブル２２０を読み出すためのリード要求を送信する。
【００９５】
このように、論物変換テーブル２２０がキャッシュされるメモリは、ホスト２に具備されてもよい。
【００９６】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９７】
１  メモリシステム、２  ホスト、１０  ＮＡＮＤメモリ、２０  メモリコントローラ、２１  ＣＰＵ、２２  ホストＩ／Ｆ、２３  リードコントローラ、２４  ライトコントローラ、２５  リード用メモリ、２６  ライト用メモリ、２７  キャッシュメモリ、２８  タグメモリ、３０  メインメモリ、３１  キャッシュエリア、１００  ユーザデータ、２００  論物変換情報、２１０  ルートテーブル、２２０  論物変換テーブル、２２１  冗長情報、２３０  フレーム、２３１  誤り訂正符号。
【図１】
2019159791.tif 000003
【図２】
2019159791.tif 000004
【図３】
2019159791.tif 000005
【図４】
2019159791.tif 000006
【図５】
2019159791.tif 000007
【図６】
2019159791.tif 000008
【図７】
2019159791.tif 000009
【図８】
2019159791.tif 000010
【図９】
2019159791.tif 000011
【図１０】
2019159791.tif 000012