(57)【要約】【課題】書き込み効率の高いメモリシステムを得る。【解決手段】実施形態のメモリシステムは、ユーザデータ、ホストアドレスに対応するユーザデータの物理アドレスを管理する正引きアドレス変換表、および物理アドレスに対応するホストアドレスを管理する逆引きアドレス変換表を保持する不揮発性メモリと、メモリを備える。実施形態のメモリシステムは、メモリ上に少なくとも一部が読み出された逆引きアドレス変換表を用いて第１物理アドレスに対応する第１ホストアドレスを求め、メモリ上に読み出された正引きアドレス変換表を用いて第１ホストアドレスに対応する第２物理アドレスを求め、第１物理アドレスと第２物理アドレスが一致する場合は第１物理アドレスのユーザデータは有効データであると判定し、それ以外の場合は第１物理アドレスのユーザデータは無効データであると判定するアドレス変換表比較部を有するコントローラを備える。【選択図】図１
2013174972.tif 000002
【特許請求の範囲】
【請求項１】
ユーザデータ、ホストアドレスに対応する前記ユーザデータの物理アドレスを管理する正引きアドレス変換表、および物理アドレスに対応するホストアドレスを管理する逆引きアドレス変換表を保持する不揮発性メモリと、
メモリと、
前記メモリ上に少なくとも一部が読み出された前記逆引きアドレス変換表を用いて第１の物理アドレスに対応する第１のホストアドレスを求め、前記メモリ上に読み出された前記正引きアドレス変換表を用いて第１のホストアドレスに対応する第２の物理アドレスを求め、第１の物理アドレスと第２の物理アドレスが一致する場合は、第１の物理アドレスの前記ユーザデータは有効データであると判定し、第１の物理アドレスと第２の物理アドレスが一致しない場合は、第１の物理アドレスの前記ユーザデータは無効データであると判定するアドレス変換表比較部を有するコントローラと、
を備えたことを特徴とするメモリシステム。
【請求項２】
前記コントローラは、コンパクション元となるブロックを前記不揮発性メモリから選択し、選択されたブロックのユーザデータが有効データであるか無効データであるかの判定を前記アドレス変換表比較部に実行させ、有効データと判定されたユーザデータをコンパクション先となるブロックに書き込む
ことを特徴とする請求項１に記載のメモリシステム。
【請求項３】
前記ブロック毎に前記逆引きアドレス変換表が存在する
ことを特徴とする請求項２に記載のメモリシステム。
【請求項４】
前記メモリは、前記不揮発性メモリ上の前記逆引きアドレス変換表の位置を示すアドレス変換表保存位置情報を保持し、
前記コントローラは、前記アドレス変換表保存位置情報に基づいて前記逆引きアドレス変換表の少なくとも一部を前記メモリに読み出す
ことを特徴とする請求項１乃至３のいずれか１項に記載のメモリシステム。
【請求項５】
前記コントローラは、前記不揮発性メモリが保持する前記アドレス変換表保存位置情報を前記メモリ上に読み出す、
ことを特徴とする請求項１乃至４のいずれか１項に記載のメモリシステム。
【請求項６】
ユーザデータ、ホストアドレスに対応する前記ユーザデータの物理アドレスを管理する正引きアドレス変換表、および物理アドレスに対応するホストアドレスを管理する逆引きアドレス変換表を保持する不揮発性メモリと、メモリと、を備えたメモリシステムのコントローラであって、
前記メモリ上に少なくとも一部が読み出された前記逆引きアドレス変換表を用いて第１の物理アドレスに対応する第１のホストアドレスを求め、前記メモリ上に読み出された前記正引きアドレス変換表を用いて第１のホストアドレスに対応する第２の物理アドレスを求め、第１の物理アドレスと第２の物理アドレスが一致する場合は、第１の物理アドレスの前記ユーザデータは有効データであると判定し、第１の物理アドレスと第２の物理アドレスが一致しない場合は、第１の物理アドレスの前記ユーザデータは無効データであると判定するアドレス変換表比較部を備える、
ことを特徴とするコントローラ。
【請求項７】
コンパクション元となるブロックを前記不揮発性メモリから選択し、選択されたブロックのユーザデータが有効データであるか無効データであるかの判定を前記アドレス変換表比較部に実行させ、有効データと判定されたユーザデータをコンパクション先となるブロックに書き込む
ことを特徴とする請求項６に記載のコントローラ。
【請求項８】
前記ブロック毎に前記逆引きアドレス変換表が存在する
ことを特徴とする請求項７に記載のコントローラ。
【請求項９】
前記メモリが保持する前記不揮発性メモリ上の前記逆引きアドレス変換表の位置を示すアドレス変換表保存位置情報に基づいて前記逆引きアドレス変換表の少なくとも一部を前記メモリに読み出す
ことを特徴とする請求項６乃至８のいずれか１項に記載のコントローラ。
【請求項１０】
前記不揮発性メモリが保持する前記アドレス変換表保存位置情報を前記メモリ上に読み出す、
ことを特徴とする請求項６乃至９のいずれか１項に記載のコントローラ。
【請求項１１】
ユーザデータ、ホストアドレスに対応する前記ユーザデータの物理アドレスを管理する正引きアドレス変換表、および物理アドレスに対応するホストアドレスを管理する逆引きアドレス変換表を保持する不揮発性メモリと、メモリと、を備えたメモリシステムの制御方法であって、
前記メモリ上に少なくとも一部が読み出された前記逆引きアドレス変換表を用いて第１の物理アドレスに対応する第１のホストアドレスを求め、
前記メモリ上に読み出された前記正引きアドレス変換表を用いて第１のホストアドレスに対応する第２の物理アドレスを求め、
第１の物理アドレスと第２の物理アドレスが一致する場合は、第１の物理アドレスの前記ユーザデータは有効データであると判定し、
第１の物理アドレスと第２の物理アドレスが一致しない場合は、第１の物理アドレスの前記ユーザデータは無効データであると判定する
ことを特徴とするメモリシステムの制御方法。
【請求項１２】
コンパクション元となるブロックを前記不揮発性メモリから選択し、
選択されたブロックの第１の物理アドレスのユーザデータが有効データと判定された場合に、当該ユーザデータをコンパクション先となるブロックに書き込む
ことを特徴とする請求項１１に記載のメモリシステムの制御方法。
【請求項１３】
前記ブロック毎に前記逆引きアドレス変換表が存在する
ことを特徴とする請求項１２に記載のメモリシステムの制御方法。
【請求項１４】
前記メモリが保持する前記不揮発性メモリ上の前記逆引きアドレス変換表の位置を示すアドレス変換表保存位置情報に基づいて前記逆引きアドレス変換表の少なくとも一部を前記メモリに読み出す
ことを特徴とする請求項１１乃至１３のいずれか１項に記載のメモリシステムの制御方法。
【請求項１５】
前記不揮発性メモリが保持する前記アドレス変換表保存位置情報を前記メモリ上に読み出す、
ことを特徴とする請求項１１乃至１４のいずれか１項に記載のメモリシステムの制御方法。
【請求項１６】
選択されたブロックの第１の物理アドレスのユーザデータが無効データと判定された場合は、選択された前記ブロック内の第１の物理アドレスの次の物理アドレスのユーザデータが有効データか無効データかを判定する
ことを特徴とする請求項１２乃至１５のいずれか１項に記載のメモリシステムの制御方法。
【請求項１７】
必要な数の空きブロックが確保されていない場合は、選択された前記ブロック内の第１の物理アドレスの次の物理アドレスのユーザデータが有効データか無効データかを判定する
ことを特徴とする請求項１２乃至１６のいずれか１項に記載のメモリシステムの制御方法。
【請求項１８】
前記次の物理アドレスが存在しない場合は、コンパクション元となるブロックを前記不揮発性メモリから再度選択する、
ことを特徴とする請求項１６または１７に記載のメモリシステムの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、メモリシステム、コントローラ、メモリシステムの制御方法に関する。
【背景技術】
【０００２】
ＮＡＮＤブロック内のユーザデータを、新規書き込みなどにより無効化すると、ブロック内の有効データ量の少ないブロック(低密度ブロック)が発生する。ブロック全体の中で低密度ブロック数が増加すると、使用中のブロック数が増加するため、新規のブロック確保ができなくなってしまう。そのため、ユーザデータが書き込まれたブロックから低密度ブロックを複数選択し、ブロック中の有効なデータを抽出、新規ブロックに移動し、高密度なデータブロックとして書き込みする。低密度ブロックはデータ移動後に解放することができるので、空きブロック数を増やすことができる。この処理をコンパクション処理とよぶ。コンパクション処理では、移動元ブロック内のデータが有効データであるかあるいは無効データであるかの判定が必要となる。このためには、逆引きアドレス変換表（ＮＡＮＤアドレスからホストアドレスへの変換表：Ｒｅｖｅｒｓｅ  Ｌｏｏｋｕｐ  Ｔａｂｌｅ）をメモリ上に用意する必要がある。ちなみに、ホストアドレスからＮＡＮＤアドレスへの変換表は正引きアドレス変換表（Ｌｏｏｋｕｐ  Ｔａｂｌｅ）である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−２１１２２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の一つの実施形態は、書き込み効率の高いメモリシステム、コントローラ、メモリシステムの制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の一つの実施形態のメモリシステムは、ユーザデータ、ホストアドレスに対応する前記ユーザデータの物理アドレスを管理する正引きアドレス変換表、および物理アドレスに対応するホストアドレスを管理する逆引きアドレス変換表を保持する不揮発性メモリと、メモリと、を備える。実施形態のメモリシステムは、前記メモリ上に少なくとも一部が読み出された前記逆引きアドレス変換表を用いて第１の物理アドレスに対応する第１のホストアドレスを求め、前記メモリ上に読み出された前記正引きアドレス変換表を用いて第１のホストアドレスに対応する第２の物理アドレスを求め、第１の物理アドレスと第２の物理アドレスが一致する場合は、第１の物理アドレスの前記ユーザデータは有効データであると判定し、第１の物理アドレスと第２の物理アドレスが一致しない場合は、第１の物理アドレスの前記ユーザデータは無効データであると判定するアドレス変換表比較部を有するコントローラを備える。
【図面の簡単な説明】
【０００６】
【図１】図１は、比較例にかかるメモリシステムの構成を示す図である。
【図２】図２は、比較例にかかる正引きアドレス変換表および逆引きアドレス変換表の構成を示す図である。
【図３】図３は、比較例においてユーザデータが上書きされる場合のフローチャートである。
【図４】図４は、比較例にかかる正引きアドレス変換表および逆引きアドレス変換表の構成を示す図である。
【図５】図５は、比較例にかかるメモリシステムの構成を示す図である。
【図６】図６は、実施形態にかかる正引きアドレス変換表および逆引きアドレス変換表の構成を示す図である。
【図７】図７は、実施形態におけるアドレス変換表比較部による有効データか無効データかの判定の手順を示すフローチャートである。
【図８】図８は、実施形態におけるコンパクション処理の手順を示すフローチャートである。
【図９】図９は、実施形態にかかる正引きアドレス変換表および逆引きアドレス変換表の構成を示す図である。
【図１０】図１０は、実施形態においてユーザデータが上書きされる場合のフローチャートである。
【発明を実施するための形態】
【０００７】
図１は、比較例にかかるメモリシステム１００の構成を示す。メモリシステム１００は、ホストコントローラ２、コントローラ３、ＮＡＮＤコントローラ４、ＮＡＮＤフラッシュメモリ５（不揮発性メモリ）、ＲＡＭなどからなるメモリ６（揮発性メモリ）を備える。メモリシステム１００はホストコントローラ２を介してホスト機器１と接続する。コンパクション処理では、移動元データについて有効データか無効データかの判定が必要となる。有効なデータとはホストアドレスと対応付けられているデータであり、無効なデータとはホストアドレスが対応付けられていないデータである。比較例においては、ＮＡＮＤフラッシュメモリ５が有するＮＡＮＤブロック上のデータが、どのホストアドレスに属するかもしくは無効データであることを示す逆引きアドレス変換表（ＮＡＮＤアドレス（物理アドレス）からホストアドレスへの変換表：Ｒｅｖｅｒｓｅ  Ｌｏｏｋｕｐ  Ｔａｂｌｅ）を使用する。逆引きアドレス変換表５２はＮＡＮＤフラッシュメモリ５に保持されており、メモリシステム１００の動作時にはメモリ６上に逆引きアドレス変換表５２と同じ内容であるがその一部のみを逆引きアドレス変換表（一部）６２として展開する。
【０００８】
逆引きアドレス変換表の一例は、図２において逆引きアドレス変換表（Ｂ）として示されている。逆引きアドレス変換表（Ｂ）には、ＮＡＮＤアドレス上に記録されたユーザデータが有効データの場合、対応するホストアドレスが存在する。例えばＮＡＮＤアドレスＸにはホストアドレスＭが、ＮＡＮＤアドレスＹにはホストアドレスＮが対応している。新規書き込みや、コンパクションによるユーザデータ移動が発生した場合は、移動元のＮＡＮＤアドレスのユーザデータは無効になるので、当該ＮＡＮＤアドレスに対応するホストアドレスには無効を示す値(無効値)を入れる。図２の逆引きアドレス変換表（Ｂ）の例では、ＮＡＮＤアドレスＺに対応するホストアドレスに無効値が入っている。
【０００９】
コンパクション時には、この逆引きアドレス変換表を使用することにより、ＮＡＮＤブロック上のデータが有効データか無効データかの判定を行うことができる。なお、ホストデータの読み出しには、ホストアドレスからＮＡＮＤブロック上のアドレスを参照する正引きアドレス変換表（ホストアドレスからＮＡＮＤアドレスへの変換表：Ｌｏｏｋｕｐ  Ｔａｂｌｅ）（Ａ）が必要となる（図２）。正引きアドレス変換表５１もＮＡＮＤフラッシュメモリ５に保持されており、メモリシステム１００の動作時にはメモリ６上に同じ内容の正引きアドレス変換表６１が展開される。この正引きアドレス変換表６１、５１は、同ホストアドレスに対するデータの上書きや、コンパクション処理後に、移動先のＮＡＮＤアドレスを指すように更新する必要がある。
【００１０】
比較例において、図２に示したホストアドレスＮおよびＭにユーザデータが上書きされる場合について、図３のフローチャートおよび図４を用いて以下に説明する。
【００１１】
まず、図３のステップＳ１０１にて、上書き元の逆引きアドレス変  換表（Ｂ）（図２）がＮＡＮＤフラッシュメモリ５からメモリ６にロード（Load）される。次に、ステップＳ１０２にて上書き先の逆引きアドレス変換表（Ｃ）がＮＡＮＤフラッシュメモリ５からメモリ６にロードされる。ここでは、逆引きアドレス変換表（Ｂ）および（Ｃ）は使用しない場合は不揮発化（ＮＡＮＤフラッシュメモリ５に保持されメモリ６上に存在しない状態）されているとする。また、逆引きアドレス変換表（Ｃ）のＮＡＮＤアドレスＰおよびＱに対応するホストアドレスには無効値が書き込まれているとする。即ち、アドレスＰおよびＱは対応するホストアドレスを有しておらず、書き込み可能なアドレスである。正引きおよび逆引きアドレス変換表更新の例として、ホストアドレスＮおよびＭに新たなユーザデータが上書きされる場合を考える。アドレスＮおよびＭに書き込まれる新たなユーザデータは、それぞれＮＡＮＤアドレスＱおよびＰに書き込まれる（ステップＳ１０３）。
【００１２】
次に、図２の逆引きアドレス変換表（Ｂ）のＮＡＮＤアドレスＸおよびＹに対応するホストアドレスにそれぞれ無効値を書き込む（ステップＳ１０４）。その結果、逆引きアドレス変換表（Ｂ）は図４に示すようになる。さらに、図４に示すように、逆引きアドレス変換表（Ｃ）のＮＡＮＤアドレスＰおよびＱに対応するホストアドレスにアドレスＭおよびＮを新たに書き込む（ステップＳ１０５）。そして、図２の正引きアドレス変換表（Ａ）のホストアドレスＮおよびＭに対応するＮＡＮＤアドレスに図４に示すようにユーザデータが書き込まれた新たなＮＡＮＤアドレスＱおよびＰを書き込んで更新する（ステップＳ１０６）。なお、正引きアドレス変換表（Ａ）も必要時にメモリ６にロードするようにしてもよい。これら正引きおよび逆引きアドレス変換表の更新はメモリ６上での操作になるが、その後、逆引きアドレス変換表（Ｂ）をＮＡＮＤフラッシュメモリ５にストア(Store)し（ステップＳ１０７）、逆引きアドレス変換表（Ｃ）をＮＡＮＤフラッシュメモリ５にストア(Store)する（ステップＳ１０８）。逆引きアドレス変換表（Ｃ）を継続して使用する場合はメモリ６に情報を残しておいてもよい。なお、コンパクションの場合は、ＮＡＮＤアドレスＰにアドレスＸに書かれていたデータがコピーされ、ＮＡＮＤアドレスＱにアドレスＹに書かれていたデータがコピーされる点が異なるが、アドレスＸおよびＹに対応するホストアドレスに無効値を書き込まなければならない点は同様である。
【００１３】
上記のように比較例においては、逆引きアドレス変換表を元にＮＡＮＤフラッシュメモリ５上のデータが有効データか無効データかの判定を行っている。このためには、データの上書きや、コンパクションによるデータ移動が発生しユーザデータの無効化が必要になった場合、元データのＮＡＮＤアドレスの逆引きアドレス変換表の対応するホストアドレスに当該ホストアドレスは無効であることを示す値（無効値）を入れる必要がある。この処理のために書き込み効率は低下する。また従来、正引きおよび逆引きアドレス変換表をメモリ６上にすべて展開していたが、大きなメモリサイズを必要とするという問題があった。この問題を解決するために例えば、この比較例では逆引きアドレス変換表はＮＡＮＤフラッシュメモリ５上に不揮発化されている。すなわち、コンパクション処理時などの必要な場合に、ＮＡＮＤフラッシュメモリ５上に不揮発化されている逆引きアドレス変換表５２の必要となる一部をメモリ６に逆引きアドレス変換表（一部）６２としてロードし使用する。さらに必要な逆引きアドレス変換表がどこに保存されているかを知るために、メモリ６上に逆引きアドレス変換表の保存位置情報（テーブルポインタ）を持っておく。この場合も、不揮発化された逆引きアドレス変換表を更新するためには、不揮発化された逆引きアドレス変換表の読み出し、更新、再不揮発化（ＮＡＮＤフラッシュメモリ５へのストア）を行う必要があるため、オーバヘッドが大きくなるという問題があった。また、頻繁に不揮発化が発生するため、ＮＡＮＤフラッシュメモリ５への書き込み効率が悪化するという問題があった。
【００１４】
以下に添付図面を参照して、実施形態にかかるメモリシステム、コントローラ、メモリシステムの制御方法を詳細に説明する。なお、この実施形態により本発明が限定されるものではない。
【００１５】
（実施形態）
図５は、実施形態にかかるメモリシステム２００の構成を示す。メモリシステム２００は、ホストコントローラ２、コントローラ３、ＮＡＮＤコントローラ４、ＮＡＮＤフラッシュメモリ５（不揮発性メモリ）、ＲＡＭなどからなるメモリ６（揮発性メモリ）を備える。メモリシステム２００はホストコントローラ２を介してホスト機器１と接続する。コントローラ３は、書き込み制御部３１に加えてコンパクション処理を制御するコンパクション制御部３２を備え、コンパクション制御部３２はアドレス変換表比較部３０を備える。ＮＡＮＤフラッシュメモリ５（不揮発性メモリ）は、ユーザデータの他に、正引きアドレス変換表５１（ホストアドレスからＮＡＮＤアドレス（物理アドレス）への変換表：Ｌｏｏｋｕｐ  Ｔａｂｌｅ）、逆引きアドレス変換表５２（ＮＡＮＤアドレスからホストアドレスへの変換表：Ｒｅｖｅｒｓｅ  Ｌｏｏｋｕｐ  Ｔａｂｌｅ）、および逆引きアドレス変換表５２の保存位置情報（テーブルポインタ）５０を記憶している。アドレス変換表比較部３０は、メモリ６上の逆引きアドレス変換表６２と正引きアドレス変換表６１の両方を使用して、コンパクション処理において、ユーザデータが有効データか無効データかの判定を行う。メモリ６上には逆引きアドレス変換表保存位置情報（テーブルポインタ）６０も展開されており、後述するようにこれを用いて、必要に応じて、逆引きアドレス変換表５２の一部をメモリ６上にロードして逆引きアドレス変換表（一部）６２として使用する。
【００１６】
アドレス変換表比較部３０による有効データか無効データかの判定の手順を図６および図７のフローチャートを用いて説明する。図６の逆引きアドレス変換表（Ｂ）のＮＡＮＤアドレスＸのデータが有効か無効かの判定を例にとり説明する。まず、逆引きアドレス変換表（Ｂ）のＮＡＮＤアドレスＸに対応するホストアドレスＭを求める（図７、ステップＳ２０１）。次に、図６の正引きアドレス変換表（Ａ）より、ホストアドレスＭに対応するＮＡＮＤアドレスＸ’（図６ではＸになっている）を求める（ステップＳ２０２）。そして、ＮＡＮＤアドレスＸとＮＡＮＤアドレスＸ’が等しいか否かでＮＡＮＤアドレスＸのデータが有効か無効かの判定を行う（ステップＳ２０３）。即ち、ＮＡＮＤアドレスＸとＮＡＮＤアドレスＸ’が等しい場合（ステップＳ２０３：Ｙｅｓ）は、ＮＡＮＤアドレスＸには有効データが存在することになる（ステップＳ２０４）。他方、ＮＡＮＤアドレスＸとＮＡＮＤアドレスＸ’が等しくない場合（ステップＳ２０３：Ｎｏ）は、ＮＡＮＤアドレスＸのデータは無効データであることになる（ステップＳ２０５）。図６のＮＡＮＤアドレスＸの場合は、ステップＳ２０２にてＸ’＝Ｘが求まるので、ステップＳ２０３においてＮＡＮＤアドレスＸには有効データが存在すると判定される。同様に、図６のＮＡＮＤアドレスＹにも有効データが存在すると判定される。他方、図６のＮＡＮＤアドレスＺについては、上記ステップＳ２０１にて求められたホストアドレスＭからは、ステップＳ２０２でＮＡＮＤアドレスＺとは異なるＮＡＮＤアドレスＸが求められる。従って、ステップＳ２０３にてＮＡＮＤアドレスＺのデータは無効データであると判定される。
【００１７】
上記した有効／無効データの判定を用いたコンパクション処理の手順を図８のフローチャートを用いて説明する。コンパクション処理は空きブロックが少なくなった場合に実行されるが、以下ではその要件を満たしてコンパクション処理の実行がされる場合について説明する。まず、コンパクションの元となるＮＡＮＤフラッシュメモリ５内のブロックを選択する（ステップＳ３０１）。次に、逆引きアドレス変換表保存位置情報（テーブルポインタ）６０を用いてブロック単位に存在する逆引きアドレス変換表５２をＮＡＮＤフラッシュメモリ５からメモリ６上に読み出す。メモリ６上にはステップＳ３０１で選択されたブロックの逆引きアドレス変換表６２が展開される。そして、この逆引きアドレス変換表６２および、同じくメモリ６上に展開されている正引きアドレス変換表６１に基づいて、ＮＡＮＤアドレス毎のデータの有効／無効が判定される（ステップＳ３０２）。ステップＳ３０２の判定は上述した図７のフローチャートに基づいて実行される。ステップＳ３０２で、有効データと判定されたＮＡＮＤアドレスのデータは（ステップＳ３０２：Ｙｅｓ）、コンパクション先のブロックにコピーされる（ステップＳ３０３）。コンパクション先のブロックの逆引きアドレス変換表６２のホストアドレスにはコピーしたデータのホストアドレスが書き込まれる。この様子を図６および図９を用いて説明する。例えば、図６の逆引きアドレス変換表（Ｂ）がコンパクションの元の逆引きアドレス変換表であるとする。ＮＡＮＤアドレスＸおよびＹは、ステップＳ３０２において有効データが存在すると判定されるので、ステップＳ３０３でＮＡＮＤアドレスＸおよびＹの有効データはコンパクション先のブロックのＮＡＮＤアドレスＰおよびＱにコピーされる。従って、図９の逆引きアドレス変換表（Ｃ）のＮＡＮＤアドレスＰおよびＱに対応するホストアドレスには、逆引きアドレス変換表（Ｂ）にてＮＡＮＤアドレスＸおよびＹに対応するホストアドレスＭおよびＮがそれぞれ書き込まれる。
【００１８】
ステップＳ３０２にて、無効データであると判定された場合は（ステップＳ３０２：Ｎｏ）、判定されたＮＡＮＤアドレスの次のＮＡＮＤアドレスが存在するか否かが判定される（ステップＳ３０５）。この場合、同一ブロック内にＮＡＮＤアドレスが無い場合は、コンパクションの元となる別のブロック（のＮＡＮＤアドレス）が存在するかまで調べる。次のＮＡＮＤアドレスが存在する場合（ステップＳ３０５：Ｙｅｓ）は次のＮＡＮＤアドレスに移動し（ステップＳ３０６）、データの有効／無効が判定される（ステップＳ３０２）。ステップＳ３０５において、コンパクションの元となるブロック内のＮＡＮＤアドレスについて全てデータの有効／無効を判定し終えている場合は次のＮＡＮＤアドレスが存在しないので（ステップＳ３０５：Ｎｏ）、ステップＳ３０１に戻って、再度、コンパクションの元となるＮＡＮＤフラッシュメモリ５内のブロックを選択する。
【００１９】
ステップＳ３０３の後は、ステップＳ３０４において、コンパクションにより必要な数の空きブロックが確保できたか否かが判定される。必要な数の空きブロックが確保できていない場合（ステップＳ３０４：Ｎｏ）は、ステップＳ３０５に進む。必要な数の空きブロックが確保できた場合（ステップＳ３０４：Ｙｅｓ）は、コンパクション処理を終了する。
【００２０】
本実施形態のコンパクション処理においては、図７のフローチャートに基づいて逆引きアドレス変換表６２と正引きアドレス変換表６１の両方を使用して、ユーザデータが有効データか無効データかの判定を行うことにより、例えば図６の逆引きアドレス変換表（Ｂ）の更新および再不揮発化（ＮＡＮＤフラッシュメモリ５への書き込み）が不要となりコンパクション処理における書き込み効率が向上する。
【００２１】
本実施形態において、図６に示したホストアドレスＮおよびＭにユーザデータが上書きされる場合について、図１０のフローチャートおよび図９を用いて以下に説明する。
【００２２】
まず、図１０のステップＳ４０１にて、上書き先の逆引きアドレス変換表（Ｃ）がＮＡＮＤフラッシュメモリ５からメモリ６にロードされる。ここでは、逆引きアドレス変換表（Ｃ）は使用しない場合は不揮発化されているとする。また、逆引きアドレス変換表（Ｃ）のＮＡＮＤアドレスＰおよびＱに対応するホストアドレスには無効値が書き込まれているとする。無効値は、初期設定時および上述したコンパクション処理で空ブロックを生成した場合に書き込んでおけばよい。即ち、アドレスＰおよびＱは対応するホストアドレスを有しておらず、書き込み可能なアドレスである。正引きおよび逆引きアドレス変換表更新の例として、ホストアドレスＮおよびＭに新たなユーザデータが上書きされる場合を考える。アドレスＮおよびＭに書き込まれる新たなユーザデータは、それぞれＮＡＮＤアドレスＱおよびＰに書き込まれる（ステップＳ４０２）。
【００２３】
次に、図９に示すように、逆引きアドレス変換表（Ｃ）のＮＡＮＤアドレスＰおよびＱに対応するホストアドレスにアドレスＭおよびＮを新たに書き込む（ステップＳ４０３）。そして、図６の正引きアドレス変換表（Ａ）のホストアドレスＮおよびＭに対応するＮＡＮＤアドレスに図９に示すようにユーザデータが書き込まれた新たなＮＡＮＤアドレスＱおよびＰを書き込んで更新する（ステップＳ４０４）。なお、正引きアドレス変換表（Ａ）も必要時にメモリ６にロードするようにしてもよい。これら正引きおよび逆引きアドレス変換表の更新はメモリ６上での操作になるが、その後、逆引きアドレス変換表（Ｃ）をＮＡＮＤフラッシュメモリ５にストア(Store)する（ステップＳ４０５）。逆引きアドレス変換表（Ｃ）を継続して使用する場合はメモリ６に情報を残しておいてもよい。なお、コンパクションの場合は、ＮＡＮＤアドレスＰに新規データではなくアドレスＸに書かれていたデータがコピーされ、ＮＡＮＤアドレスＱに新規データではなくアドレスＹに書かれていたデータがコピーされる点が異なる。
【００２４】
上に説明した本実施形態における上書きのフローチャートを比較例にかかる図３のフローチャートと比較すると、逆引きアドレス変換表（Ｂ）のメモリ６へのロード（ステップＳ１０１）、逆引きアドレス変換表（Ｂ）のホストアドレスへの無効値の書き込み（ステップＳ１０４）、逆引きアドレス変換表（Ｂ）のＮＡＮＤフラッシュメモリ５へのストア(Store)（ステップＳ１０７）が不要になっており、上書きにおいても書き込み効率の向上が図れることがわかる。
【００２５】
以上説明したように、本実施形態においては、コンパクション処理を実行する場合に必要となる逆引きアドレス変換表をメモリ上に全て展開する必要がないのでメモリ使用量の削減をしたうえで、オーバヘッドの低減、書き込み効率向上が図れる。即ち、ユーザデータの上書き、コンパクションによりデータが無効化された場合に、逆引きアドレス変換表に無効値を入れて更新する必要がなくなる。そのため、逆引きアドレス変換表を不揮発化していても、無効化されるＮＡＮＤアドレスを有する逆引きアドレス変換表の更新、再不揮発化をする必要がなくなる。また、上書き時には無効化されるＮＡＮＤアドレスを有する逆引きアドレス変換表の不揮発性メモリからの読み出しも不要となる。
【００２６】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００２７】
１  ホスト機器、２  ホストコントローラ、３  コントローラ、４  ＮＡＮＤコントローラ、５  ＮＡＮＤフラッシュメモリ、６  メモリ、１００、２００  メモリシステム。
【図１】
2013174972.tif 000003
【図２】
2013174972.tif 000004
【図３】
2013174972.tif 000005
【図４】
2013174972.tif 000006
【図５】
2013174972.tif 000007
【図６】
2013174972.tif 000008
【図７】
2013174972.tif 000009
【図８】
2013174972.tif 000010
【図９】
2013174972.tif 000011
【図１０】
2013174972.tif 000012