(57)【要約】      （修正有）【課題】テーブルのコンパクション処理を実行する場合に、フラッシュメモリに対するアクセスを低減し、コンパクション処理の効率化を図ることができるメモリ制御装置を提供する。【解決手段】リード・ライトコントローラ１３は、データ及び論理・物理アドレス変換用の第１のテーブルを記憶するフラッシュメモリに対する読み出し、書き込みを実行する。バッファメモリ１６は、第１のテーブルの一部または全てを含むキャッシュテーブルとして使用する第２のテーブル、及び第１及び第２のテーブルの論理・物理アドレスを管理する管理テーブルを格納する。第１のテーブルコントローラ１５２は、第２のテーブルを使用して論理・物理アドレスの変換処理を実行する。第２のテーブルコントローラ１５１は、第１のテーブルのコンパクション処理を実行し、コンパクション元領域内のデータの有効・無効判定処理を管理テーブルを使用して実行する。【選択図】図１
2013206307.tif 000002
【特許請求の範囲】
【請求項１】
データ及び論理・物理アドレス変換用の第１のテーブルを記憶するフラッシュメモリに対する読み出し、書き込みを実行するリード・ライトコントローラと、
前記リード・ライトコントローラにより読み出された第１のテーブルの一部または全てを含むキャッシュテーブルとして使用する第２のテーブル、及び前記第１及び第２のテーブルの論理・物理アドレスを管理する管理テーブルを格納するバッファメモリと、
前記第２のテーブルを使用して論理・物理アドレスの変換処理を実行する第１のテーブルコントローラと、
前記第１のテーブルのコンパクション処理を実行し、当該コンパクション処理のコンパクション元領域内のデータの有効・無効判定処理を前記バッファメモリに格納された管理テーブルを使用して実行する第２のテーブルコントローラと
を具備するメモリ制御装置。
【請求項２】
前記第１のテーブルコントローラは、
前記リード・ライトコントローラにより読み出し、書き込みを実行する場合に、前記フラッシュメモリから前記第１のテーブルを読み出すことなく、前記第２のテーブルを使用して論理・物理アドレスの変換処理を実行する請求項１に記載のメモリ制御装置。
【請求項３】
前記リード・ライトコントローラは、
電源投入時に、前記フラッシュメモリから前記第１のテーブルの一部または全てを読み出して、前記バッファメモリに前記第２のテーブルとして格納する請求項１または請求項２のいずれか１項に記載のメモリ制御装置。
【請求項４】
前記管理テーブルは、
前記第１のテーブルの所定単位のデータを示す論理的情報から対応する前記フラッシュメモリ上の物理的位置情報を検索するための第１の管理テーブルと、
前記フラッシュメモリ上の物理的位置情報から前記論理的情報を検索するための第２の管理テーブルと
を含む請求項１から請求項３のいずれか１項に記載のメモリ制御装置。
【請求項５】
第２のテーブルコントローラにより有効と判定されたデータを示す論理的情報を記憶するメモリを有する請求項１から請求項４のいずれか１項に記載のメモリ制御装置。
【請求項６】
第２のテーブルコントローラは、
有効と判定したデータを示す論理的情報を前記メモリに記憶し、
無効と判定したデータを示す論理的情報を無効化する請求項５に記載のメモリ制御装置。
【請求項７】
第２のテーブルコントローラにより有効と判定されたデータを示す論理的情報を記憶するメモリと、
前記メモリに記憶された論理的情報に基づいて、前記有効と判定されたデータを前記フラッシュメモリのコンパクション先領域に書き込む第３のテーブルコントローラと
をさらに有する請求項１から請求項４のいずれか１項に記載のメモリ制御装置。
【請求項８】
データ及び論理・物理アドレス変換用の第１のテーブルを記憶するフラッシュメモリと、
第１のテーブルの一部または全てを含むキャッシュテーブルとして使用する第２のテーブル、及び前記第１及び第２のテーブルの論理・物理アドレスを管理する管理テーブルを格納するバッファメモリと、
前記フラッシュメモリに対する読み出し、書き込みを実行するリード・ライトコントローラと、
前記第２のテーブルを使用して論理・物理アドレスの変換処理を実行する第１のテーブルコントローラと、
前記第１のテーブルのコンパクション処理を実行し、当該コンパクション処理のコンパクション元領域内のデータの有効・無効判定処理を前記バッファメモリに格納された管理テーブルを使用して実行する第２のテーブルコントローラと
を具備するデータ記憶装置。
【請求項９】
前記リード・ライトコントローラは、
電源投入時に、前記フラッシュメモリから前記第１のテーブルの一部または全てを読み出して、前記バッファメモリに前記第２のテーブルとして格納する請求項８に記載のデータ記憶装置。
【請求項１０】
前記管理テーブルは、
前記第１のテーブルの所定単位のデータを示す論理的情報から対応する前記フラッシュメモリ上の物理的位置情報を検索するための第１の管理テーブルと、
前記フラッシュメモリ上の物理的位置情報から前記論理的情報を検索するための第２の管理テーブルと
を含む請求項８または請求項９のいずれか１項に記載のデータ記憶装置。
【請求項１１】
データ及び論理・物理アドレス変換用の第１のテーブルを記憶するフラッシュメモリと、
第１のテーブルの一部または全てを含むキャッシュテーブルとして使用する第２のテーブル、及び前記第１及び第２のテーブルの論理・物理アドレスを管理する管理テーブルを格納するバッファメモリとを有するデータ記憶装置に適用するメモリ制御方法であって、
前記フラッシュメモリに対する読み出し、書き込みを実行する場合に、前記第２のテーブルを使用して論理・物理アドレスの変換処理を実行し、
前記第１のテーブルのコンパクション処理を実行し、当該コンパクション処理のコンパクション元領域内のデータの有効・無効判定処理を前記バッファメモリに格納された管理テーブルを使用して実行するメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、フラッシュメモリを使用するデータ記憶装置のメモリ制御装置及びメモリ制御方法に関する。
【背景技術】
【０００２】
近年、データ記憶装置として、書き換え可能な不揮発性メモリであるNAND型フラッシュメモリ（以下、単にフラッシュメモリと表記する場合がある）を使用するＳＳＤ（solid state drive）の開発が推進されている。フラッシュメモリは、データの読み出し単位と書き込み単位がページ単位であるのに対して、データの消去単位がブロック単位である。また、書き換え対象の記憶領域に対しては、書き換え前に消去処理が必要となる。
【０００３】
このようなフラッシュメモリの特性から、ＳＳＤでは、特にフラッシュメモリに記録された論理・物理アドレス変換用のテーブルなどの情報をバッファメモリに格納することで、フラッシュメモリに対するアクセスが削減されている。
【０００４】
また、フラッシュメモリに対するデータの書き換えが進むと、無効なデータ（最新でないデータ）により、ブロック内は有効データを格納できない記憶領域の割合が増大する。ＳＳＤは、ブロック内の記憶領域を有効活用するために、コンパクション（compaction）処理を実行する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−１５７１４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
コンパクション処理は、フラッシュメモリに記録されたユーザデータだけでなく、論理・物理アドレス変換用のテーブルを記録しているブロックもコンパクション対象ブロックとなる。コンパクション処理では、コンパクション対象ブロック内のデータの有効または無効を判定する処理などのために、フラッシュメモリからテーブルのデータを読み出す処理が必要となる。
【０００７】
そこで、本発明の目的は、テーブルのコンパクション処理を実行する場合に、フラッシュメモリに対するアクセスを低減し、コンパクション処理の効率化を図ることができるメモリ制御装置を提供することにある。
【課題を解決するための手段】
【０００８】
実施形態によれば、メモリ制御装置は、リード・ライトコントローラと、バッファメモリと、第１のテーブルコントローラと、第２のテーブルコントローラとを具備する。リード・ライトコントローラは、データ及び論理・物理アドレス変換用の第１のテーブルを記憶するフラッシュメモリに対する読み出し、書き込みを実行する。バッファメモリは、前記リード・ライトコントローラにより読み出された第１のテーブルの一部または全てを含むキャッシュテーブルとして使用する第２のテーブル、及び前記第１及び第２のテーブルの論理・物理アドレスを管理する管理テーブルを格納する。第１のテーブルコントローラは、前記第２のテーブルを使用して論理・物理アドレスの変換処理を実行する。第２のテーブルコントローラは、前記第１のテーブルのコンパクション処理を実行し、当該コンパクション処理のコンパクション元領域内のデータの有効・無効判定処理を前記バッファメモリに格納された管理テーブルを使用して実行する。
【図面の簡単な説明】
【０００９】
【図１】実施形態に関するＳＳＤの構成を説明するためのブロック図。
【図２】実施形態に関するＬＵＴの構成を説明するための図。
【図３】実施形態に関するＬＵＴキャッシュテーブルの構成を説明するための図。
【図４】実施形態に関するＮＶＬＵＴ正引きテーブルの構成を説明するための図。
【図５】実施形態に関するＮＶＬＵＴ逆引きテーブルの構成を説明するための図。
【図６】実施形態に関するコンパクション処理を説明するための図。
【図７】実施形態に関するデータ書き込み処理を説明するためのフローチャート。
【図８】実施形態に関するＬＵＴコンパクション処理を説明するためのフローチャート。
【図９】実施形態に関するＬＵＴコンパクション処理を説明するためのフローチャート。
【発明を実施するための形態】
【００１０】
以下図面を参照して、実施形態を説明する。
【００１１】
［データ記憶装置の構成］
図１は、実施形態に係るデータ記憶装置の構成を示すブロック図である。
【００１２】
図１に示すように、データ記憶装置はＳＳＤ（solid state drive）であり、ＳＳＤコントローラ１０と、不揮発性メモリのNAND型フラッシュメモリ（以下、フラッシュメモリ）１８とを有する。フラッシュメモリ１８はＳＳＤのデータ記憶媒体であり、通常ではチャネル毎に分割されている。
【００１３】
ＳＳＤコントローラ１０は、ホストインターフェース（ホストＩ／Ｆ）１１と、メイン制御部１２と、リード・ライト（Ｒ／Ｗ）制御部１３と、データ用バッファメモリ（以下データバッファ）１４と、ルックアップテーブル（ＬＵＴ:lookup table）制御部（以下ＬＵＴ制御部）１５と、テーブル用バッファメモリ（以下テーブルバッファ）１６と、フラッシュメモリコントローラ（以下NANDコントローラ）１７と、データバス１９とを有する。
【００１４】
ホストＩ／Ｆ１１は、ＳＳＤコントローラ１０とホストデバイス２０との間で、データ、コマンド、アドレスの転送（送受信）を制御する。ホストデバイス２０は、例えばＳＡＴＡ（Serial ATA）規格のインターフェースを含むコンピュータなどである。メイン制御部１２は、マイクロプロセッサ（ＭＰＵ）から構成されており、ＳＳＤコントローラ１０の全体的制御（各要素間の連携など）を実行する。本実施形態では、メイン制御部１２は、リード・ライト制御部１３、データバッファ１４、及びＬＵＴ制御部１５の連携するように制御する。
【００１５】
Ｒ／Ｗ制御部１３は、基本的にはNANDコントローラ１７に対して、リードコマンド及びライトコマンドを発行する。NANDコントローラ１７は、チャネル毎のフラッシュメモリ１８に対応し、Ｒ／Ｗ制御部１３からのリードコマンドに応じてフラッシュメモリ１８からデータを読み出す。また、NANDコントローラ１７は、Ｒ／Ｗ制御部１３からのライトコマンドに応じてフラッシュメモリ１８にデータを書き込む。
【００１６】
Ｒ／Ｗ制御部１３は、本実施形態に関係するコマンド・ディスパッチャ（ＣＤ: Command dispatcher、以下ＣＤ部と表記する）１３０と、コンパクション・マネージャ（ＣＭ: compaction manager、以下ＣＭ部と表記する）１３１と、ライトコントローラ（ＷＣ:write controller、以下ＷＣ部と表記する）１３２と含む。データを書き込み時に、ＷＣ部１３２はＣＤ部１３０に対してライトコマンドを発行する。ＣＤ部１３０は、ＷＣ部１３２や図示しないリードコントローラなどからのコマンドを整理し、NANDコントローラ１７に渡すためのコマンドに変更して送出する。ＣＭ部１３１は、後述するコンパクション処理に必要なＬＵＴデータの書き込み要求を実行する。具体的には、ＣＭ部１３１は、コンパクション元ブロックのアドレスの提示などの処理を含む。
【００１７】
データバッファ１４は、リードバッファ（ＲＢ）１４０と、ライトバッファ（ＷＢ）１４１を含むＳＲＡＭ（Static Random Access Memory）のバッファメモリである。ＲＢ１４０は、フラッシュメモリ１８から読み出されたデータを一時的に格納する。ホストＩ／Ｆ１１は、ＲＢ１４０に格納されたデータをホストデバイス２０に転送する。ＷＢ１４１は、フラッシュメモリ１８に書き込むためのデータを一時的に格納する。例えば、ホストＩ／Ｆ１１は、ホストデバイス２０から受信したデータをＷＢ１４１に格納する。
【００１８】
ＬＵＴ制御部１５は、アドレス変換部１５０と、ＬＵＴコンパクション処理部１５１を含む。アドレス変換部１５０は基本的には、テーブルバッファ１６に格納されているルックアップテーブル（以下、ＬＵＴと表記する場合がある）を参照して、フラッシュメモリ１８にデータを書き込むときの論理・物理アドレス変換処理を実行する。ＬＵＴコンパクション処理部１５１は本実施形態の主要部であり、後述するように、フラッシュメモリ１８に記録されているＬＵＴのコンパクション処理を実行する。
【００１９】
テーブルバッファ１６は、ＤＲＡＭ（Dynamic Random Access Memory）１６０及びＳＲＡＭ１６１を含み、後述するように、複数種のＬＵＴを格納する。ＬＵＴ制御部１５は、テーブルバッファ１６に格納されている各ＬＵＴを参照して、アドレス変換処理及びＬＵＴコンパクション処理を実行する。
【００２０】
［テーブル構成］
図２は、テーブルバッファ１６及びフラッシュメモリ１８に格納されるＬＵＴの構成を説明するための図である。
【００２１】
図２に示すように、テーブルバッファ１６のＤＲＡＭ１６０には、ＬＵＴキャッシュテーブル（以下、ＬＵＴキャッシュと省略する場合がある）２００が格納される。ＤＲＡＭ１６０には、ＬＵＴキャッシュ２００以外に、後述するＬＵＴ正引きテーブル２０１及びＬＵＴ逆引きテーブル２０２が格納される。
【００２２】
ここで、ＮＶ（Non-Volatile）ＬＵＴは、不揮発化されたＬＵＴを意味する。具体的には、図２に示すように、フラッシュメモリ１８に格納されたＬＵＴであり、ＬＵＴキャッシュ２００に対応するＮＶＬＵＴ２１０である。
【００２３】
また、ＳＲＡＭ１６１には、後述するＬＡＢ-Indexテーブル（以下、ＬＩテーブルと表記する場合がある）２０３及びＬＵＴコンパクションリスト２０４が格納される。さらに、フラッシュメモリ１８には、ＮＶＬＵＴ２１０以外に、ＮＶＬＵＴ正引きテーブル２１１及びＮＶＬＵＴ逆引きテーブル２１２が格納される。
【００２４】
図３は、ＬＵＴキャッシュ２００の構成を示す図である。
【００２５】
図３に示すように、ＬＵＴキャッシュ２００は、ホストデバイス２０からのリード要求またはライト要求時に、アドレス変換部１５０が参照して、論理アドレス（ＬＢＡ:Logical Block Address）を物理アドレス（ＰＢＡ：Physical Block Address）に変換するためのテーブルである。後述するように、ＬＵＴキャッシュ２００は、例えばＳＳＤの電源投入時にフラッシュメモリ１８上に分散記録されているＮＶＬＵＴ２１０がＤＲＡＭ１６０上に展開されたテーブルである。
【００２６】
ここで、アドレス変換部１５０は、論理アドレスとしてＬＢＡから論理クラスタアドレス（ＬＣＡ: Logical Cluster Address）を求める。ＬＣＡは、フラッシュメモリ１８上のアクセス単位であるクラスタの論理的位置を示すアドレスである。例えば１クラスタは８セクタ（１セクタは５１２バイト）に相当するデータ領域である。従って、ＰＢＡはクラスタの物理的位置に相当し、最新のクラスタ位置を示す。なお、ＰＢＡとして、ＬＢＡとＰＢＡとの仲介アドレスであるメディア・ブロック・アドレス（ＭＢＡ:Media Block Address）またはメディア・クラスタ・オフセット（ＭＣＯ:Media Cluster Offset）を使用してもよい。
【００２７】
図３に示すように、ＬＵＴキャッシュ２００が不揮発化されたものが、フラッシュメモリ１８に書き込まれたＮＶＬＵＴ２１０である。即ち、Ｒ／Ｗ制御部１３及びNANDコントローラ１７により、ＤＲＡＭ１６０上のＬＵＴキャッシュ２００は、フラッシュメモリ１８に書き込まれて、ＮＶＬＵＴ２１０として保存される。
【００２８】
ここで、テーブルバッファ１６には、図示しないＬＵＴダーティテーブル（Dirty table）が格納されている。このＬＵＴダーティテーブルは、電源遮断時などに、ＤＲＡＭ１６０上のＬＵＴキャッシュ２００とフラッシュメモリ１８上のＮＶＬＵＴ２１０との整合性を保つために使用される。即ち、ＬＵＴキャッシュ２００とＮＶＬＵＴ２１０との差異が登録される。ＬＵＴダーティテーブルに一定量が登録されると、この差異情報が更新情報として、フラッシュメモリ１８上のＮＶＬＵＴ２１０に書き込まれることになる。
【００２９】
ホストデバイス２０からのリード要求またはライト要求時に、論理アドレス（ＬＢＡまたはＬＣＡ）から物理アドレス（ＰＢＡ，ＭＢＡまたはＭＣＯ）への変換処理は、ＬＵＴキャッシュ２００が使用される。ＤＲＡＭ１６０及びＳＲＡＭ１６１において、ＬＵＴキャッシュ２００以外の各テーブルなどは、後述するように、ＬＵＴキャッシュ２００の不揮発化、再構築、コンパクション処理のために使用される。
【００３０】
図４は、ＬＵＴ正引きテーブル２０１の構成を示す図である。
【００３１】
図４に示すように、ＬＵＴ正引きテーブル２０１は、論理アドレスとしてリージョン番号（ＲＮ:Region Number）から、フラッシュメモリ１８上のＮＶＬＵＴ２１０の位置を示す物理アドレス（ＰＢＡ）を求めるために使用される。ＬＵＴ正引きテーブル２０１が不揮発化されたものが、フラッシュメモリ１８に書き込まれたＮＶＬＵＴ正引きテーブル２１１である。即ち、Ｒ／Ｗ制御部１３及びNANDコントローラ１７により、ＤＲＡＭ１６０上のＬＵＴ正引きテーブル２０１は、フラッシュメモリ１８に書き込まれて、不揮発性化されたＮＶＬＵＴ正引きテーブル２１１として保存される。
【００３２】
図５は、ＬＵＴ逆引きテーブル２０２の構成を示す図である。
【００３３】
図５に示すように、ＬＵＴ逆引きテーブル２０２は、物理アドレス（ＰＢＡ）としてフラッシュメモリ１８上のＮＶＬＵＴ２１０用の有効論理ブロック（アクティブブロック）内の位置から、その位置に書き込まれているＮＶＬＵＴ２１０のリージョン番号（ＲＮ）を求めるために使用される。即ち、ＬＵＴ逆引きテーブル２０２は、アクティブブロック内に、どのリージョン（番号）に対応するＮＶＬＵＴ２１０のエントリが配置されているかを示すテーブルである。ＬＵＴ逆引きテーブル２０２は、フラッシュメモリ１８に書き込まれて、不揮発化されたＮＶＬＵＴ逆引きテーブル２１２として保存される。
【００３４】
前述したように、テーブルバッファ１６のＳＲＡＭ１６１には、ＬＩテーブル２０３が格納される（図２を参照）。ＬＩテーブル２０３は、ＬＡＢ-Index(LUT Active Block Index)テーブルであり、アクティブブロック内に配置されたＮＶＬＵＴ２１０の物理アドレス（ＭＢＡ）からＬＵＴ逆引きテーブル２０２内の位置を求めるためのテーブルである。また、ＳＲＡＭ１６１には、ＬＵＴコンパクションリスト２０４が格納される。ＬＵＴコンパクションリスト２０４は、コンパクション元のアクティブブロックから抽出された有効なリージョン（番号）を登録するためのリストである。
【００３５】
ここで、リージョン（Region）とは、例えばＬＵＴキャッシュ２００を不揮発化する場合の最小単位である。即ち、リージョンは、ＬＵＴキャッシュ２００の各エントリがフラッシュメモリ１８に書き込まれて、ＮＶＬＵＴ２１０を再構築する場合の最小データサイズである。
【００３６】
［コンパクション処理］
先ず、コンパクション処理の背景として、図７のフローチャートを参照して、本実施形態のＳＳＤコントローラ１０によるユーザデータの書き込み処理を説明する。
【００３７】
ホストデバイス２０からライト要求（ライトコマンドの受信）があると、ＳＳＤコントローラ１０はユーザデータ（ホストデータ）の書き込み処理を開始する（ブロック７００）。ホストＩ／Ｆ１１は、ホストデバイス２０からライトコマンドに伴う書き込み用データ（ライトデータ）を受信すると、ライトバッファ（ＷＢ）１４１に格納する（ブロック７０１）。メイン制御部１２は、ＷＢ１４１に一定量のライトデータが格納されると、Ｒ／Ｗ制御部１３のＷＣ部１３２にライト要求を行う。
【００３８】
ＷＣ部１３２は、当該ライトデータを書き込むアドレスを示す情報を含むログデータを作成し、ＣＤ部１３０に対して書き込み命令を発行する（ブロック７０２）。ＣＤ部１３０は、ＷＣ部１３２からのコマンドを整理し、NANDコントローラ１７に渡すためのコマンドに変更して送出する（ブロック７０３）。NANDコントローラ１７は、ＷＢ１４１からライトデータを読み出して、フラッシュメモリ１８に書き込むライト処理を実行する（ブロック７０４）。
【００３９】
ここで、ＷＣ部１３２は、NANDコントローラ１７によるライト処理が終了すると、ＬＵＴ制御部１５に対して、フラッシュメモリ１８に新たに書き込まれたデータのアドレスに基づいてＬＵＴを更新するアドレス更新処理を要求する。ＬＵＴ制御部１５は、フラッシュメモリ１８のアドレスを管理しているＬＵＴにおいて、論理・物理アドレス間のアドレス変換用データを更新する。
【００４０】
このようなデータの書き込み処理において、ＳＳＤでは、ホストデバイス２０からのデータの書き込み単位がセクタであるのに対して、フラッシュメモリ１８上でＬＵＴによるデータの管理単位がクラスタである。クラスタは、セクタより容量的に大きい単位であり、例えば１クラスタが８セクタに相当する。このため、ＳＳＤは、書き込み処理での書き換え対象のセクタを含むクラスタのデータをフラッシュメモリ１８から読み出して、フラッシュメモリ１８の外部にあるバッファ領域に一時的に格納する。そして、バッファ領域で書き換え対象のセクタのデータを書き換えて、クラスタ単位のデータをフラッシュメモリ１８に書き戻す動作が行われる。これを、リード・モディファイ・ライト（ＲＭＷ: Read Modify Write）処理と呼ぶ。
【００４１】
ＲＭＷ処理では、読み出したデータをフラッシュメモリ１８上の元のブロック位置に書き戻すことができないため、新たな場所に書き込むことになる。即ち、データを書き換える場合に、元のデータを消去するのではなく、別の場所に新たなデータを書き加える。このため、最新のデータ（書き換えたデータ）を有効データとし、元のデータを無効データとして論理的に区別する必要がある。この有効データの記録位置を効率よく検索するためにＬＵＴが必要となる。
【００４２】
ＳＳＤでは、フラッシュメモリ１８に対するデータの消去単位がブロック単位であるのに対して、書き込み単位がページ単位である。ブロックは、ページより容量的に大きい単位である。このため、データの書き込み時間は、消去時間より１／１０以下程度の短さである。また、フラッシュメモリ１８のセルの寿命は、消去と書き換えの繰り返し回数により大きく影響される。この場合、複数のブロック間の消去回数の均一化は、後述するコンパクション処理でのコンパクション元ブロックの選定方法により実現される。即ち、消去回数が比較的少ないものをコンパクション元ブロックとして選定する。コンパクション処理では、このコンパクション元ブロックがフリーブロック（書き込み可能なブロック）化されて再利用可能となる。このようなコンパクション処理においても、ＬＵＴが有効である。
【００４３】
以下、図６を参照して、コンパクション処理の概要を説明する。
【００４４】
図６に示すように、例えば３ブロック分のコンパクション元ブロック６００が存在する場合に、コンパクション処理は、各ブロック６００から有効データ（最新のデータ）６０１を収集する。これらの有効データ６０１を、コンパクション先ブロック（消去済みのブロック）６１０に移動させる。この動作を繰り返すことにより、有効データのみのブロック６１０と無効データのみのブロック６００とに分離することができる。無効データのみのブロック６００は、消去処理により新たなデータの書き込み可能な記録ブロック（フリーブロック）６２０として再生することができる。
【００４５】
以上のようなコンパクション処理は、ユーザデータが記録されているブロックだけでなく、ＬＵＴが記録されているブロックに対しても必要となる。即ち、図２に示すように、フラッシュメモリ１８上に記録されているＮＶＬＵＴ２１０などである。前述したように、ホストデバイス２０からライト要求が発生すると、ユーザデータの書き込み処理に伴って、アドレス更新処理に応じたＬＵＴのデータ（アドレス変換用データ）の変更処理が必要となる。この場合、ＬＵＴ制御部１５は、後述するように、Ｒ／Ｗ制御部１３のＣＭ部１３１を介してＮＶＬＵＴ２１０のＴデータの書き換え要求を実行する（図９のフローチャートを参照）。
【００４６】
ここで、本実施形態では、図２に示すように、ＤＲＡＭ１６０上には、ＬＵＴキャッシュ２００が格納される。ＬＵＴキャッシュ２００は、例えばＳＳＤの電源投入時に、メイン制御部１２の制御に基づいて、Ｒ／Ｗ制御部１３、データバッファ１４、及びＬＵＴ制御部１５の連携動作により、フラッシュメモリ１８上から読み出されたＮＶＬＵＴ２１０のコピーである。ＮＶＬＵＴ２１０は、フラッシュメモリ１８上に分散記録されている。
【００４７】
前述したように、ホストデバイス２０からライト要求に応じたユーザデータ（ホストデータ）は、一連の書き込み処理によりフラッシュメモリ１８上に書き込まれる。この場合、ユーザデータのアドレス（論理アドレスと物理アドレス）を管理するＬＵＴのデータ（アドレス変換用データ）を更新する必要がある。本実施形態では、ＬＵＴ制御部１５は、ＤＲＡＭ１６０上のＬＵＴキャッシュ２００のアドレス変換用データを更新するだけで、フラッシュメモリ１８上のＮＶＬＵＴ２１０のデータ更新処理を実行しない。
【００４８】
従って、本実施形態では、ホストデバイス２０からライト要求に応じたデータ書き込み処理時には、アドレス解決処理（論理アドレスから物理アドレスを求める処理）とアドレス更新処理を高速に行うことができる。即ち、ＤＲＡＭ１６０上のＬＵＴキャッシュ２００を使用し、フラッシュメモリ１８上のＮＶＬＵＴ２１０をアクセスする必要がないためである。なお、ホストデバイス２０からリード要求に応じたデータ読み出し処理時にも、ＤＲＡＭ１６０上のＬＵＴキャッシュ２００が常に最新の状態に更新されるため、論理アドレスから物理アドレスへの変換処理のために、フラッシュメモリ１８上のＮＶＬＵＴ２１０を読み出す必要はない。
【００４９】
次に、主として図８及び図９のフローチャートを参照して、本実施形態のＬＵＴのコンパクション処理を説明する。
【００５０】
本実施形態では、ＬＵＴ制御部１５のＬＵＴコンパクション処理部１５１が、ＬＵＴのコンパクション処理を実行する。Ｒ／Ｗ制御部１３のＣＭ部１３１は、ＬＵＴコンパクション処理部１５１と連携し、後述するコンパクション処理に必要なＬＵＴデータの書き込み要求などの処理を実行する（図９のフローチャートを参照）。
【００５１】
図８に示すように、ＣＭ部１３１は、コンパクション元ブロック（図６のブロック６００に相当）の物理アドレス（ここではＭＢＡ）をＬＵＴコンパクション処理部１５１に通知する（ブロック８００）。ＬＵＴコンパクション処理部１５１は、ＤＲＡＭ１６０上のＬＵＴ逆引きテーブル２０２を参照し、ＮＶＬＵＴ２１０のリージョン番号（ＲＮ）を求める（ブロック８０１）。
【００５２】
但し、実際には、ＬＵＴコンパクション処理部１５１は、ＳＲＡＭ１６１に格納されたＬＩテーブル２０３を参照して、ＮＶＬＵＴ２１０のリージョン番号（ＲＮ）を求める。即ち、ＬＵＴコンパクション処理部１５１は、アクティブブロック内に配置されたＮＶＬＵＴ２１０の物理アドレス（ＭＢＡ）からＬＵＴ逆引きテーブル２０２内の位置を求める。これにより、フラッシュメモリ１８上のアクティブブロック（コンパクション元ブロック）内に、当該リージョン番号に対応するＮＶＬＵＴ２１０のエントリ（アドレス変換データ）が配置されていることが確認される。
【００５３】
ＬＵＴコンパクション処理部１５１は、ＬＵＴ逆引きテーブル２０２から検索したＮＶＬＵＴ２１０のリージョン番号（ＲＮ）が有効データを示すか否かを判定するリージョンの有効・無効判定処理を行なう（ブロック８０２）。具体的には、ＬＵＴコンパクション処理部１５１は、ＤＲＡＭ１６０上のＬＵＴ正引きテーブル２０１を参照し、リージョン番号（ＲＮ）に対応するＮＶＬＵＴ２１０の物理アドレス（ＭＢＡ）を求める。
【００５４】
ＬＵＴコンパクション処理部１５１は、ＤＲＡＭ１６０上のＬＵＴ逆引きテーブル２０２とＬＵＴ正引きテーブル２０１の相互参照により、リージョン番号に対応する各物理アドレスが同一であれば、当該リージョン番号が有効データ（最新のエントリ）を示すものと判定（有効判定）する（ブロック８０３のＹＥＳ）。ＬＵＴコンパクション処理部１５１は、有効であると判定したリージョン番号を、ＳＲＡＭ１６１のＬＵＴコンパクションリスト２０４に登録する（ブロック８０４）。ＬＵＴコンパクションリスト２０４は、コンパクション元のアクティブブロックから抽出された有効なリージョン（番号）を登録するためのリストである。
【００５５】
一方、ＬＵＴコンパクション処理部１５１は、各物理アドレスが不一致であれば当該リージョン番号が無効データを示すものと判定し、何も処理せずに次の処理に移行する（ブロック８０３のＮＯ，８０５）。
【００５６】
次に、Ｒ／Ｗ制御部１３は、ＬＵＴコンパクション処理部１５１と連携し、コンパクション処理によりＬＵＴコンパクションリスト２０４に登録されたリージョン番号のＬＵＴデータ（エントリデータ）をフラッシュメモリ１８上のブロックに書き込む処理を実行する（ブロック８０６）。図９のフローチャートを参照して具体的に説明する。
【００５７】
図９に示すように、Ｒ／Ｗ制御部１３のＣＭ部１３１は、エントリデータの書き込み要求をＷＣ部１３２に行なう（ブロック９００）。ここで、メイン制御部１２は、ＬＵＴコンパクション処理部１５１からＬＵＴコンパクションリスト２０４に登録されたリージョン番号のリストの通知を受ける（ブロック９０１）。メイン制御部１２は、通知されたリージョン番号に対応するエントリデータを、ＤＲＡＭ１６０上のＬＵＴキャッシュ２００から読み出してＷＢ１４１に格納する（ブロック９０２）。即ち、メイン制御部１２は、通知されたリージョン番号について、ＬＵＴキャッシュ２００から該当リージョン番号のエントリデータをＷＢ１４１に格納して準備する（不揮発化処理の準備）。ここで、エントリデータをＷＢ１４１に格納せずに、ＤＲＡＭ１６０上のＬＵＴキャッシュ２００からフラッシュメモリ１８に直接書き込む処理でもよい。
【００５８】
ＬＵＴコンパクション処理部１５１は、ＬＵＴ逆引きテーブル２０２とＬＵＴ正引きテーブル２０１を参照して、リージョン番号に対応するエントリデータをＬＵＴキャッシュ２００から読み出す。ＬＵＴコンパクション処理部１５１は、ＷＢ１４１に格納したエントリデータのリージョン番号を、ＬＵＴコンパクションリスト２０４から削除する（ブロック９０３）。
【００５９】
この後の処理は、前述したユーザデータの書き込み処理と同様である。即ち、ＷＣ部１３２は、ＣＤ部１３０に対してフラッシュメモリ１８上の新しいブロックにエントリデータを書き込むための書き込み命令を発行する（ブロック９０４）。ＣＤ部１３０は、ＷＣ部１３２からのコマンドを整理し、NANDコントローラ１７に渡すためのコマンドに変更して送出する（ブロック９０５）。NANDコントローラ１７は、ＷＢ１４１からエントリデータを読み出して、フラッシュメモリ１８上の新しいブロックに書き込むライト処理を実行する（ブロック９０６）。
【００６０】
ＬＵＴコンパクション処理部１５１は、ＤＲＡＭ１６０上のＬＵＴ正引きテーブル２０１とＬＵＴ逆引きテーブル２０２の更新処理を行なう（ブロック９０７）。即ち、ＬＵＴ正引きテーブル２０１には、あるリージョン番号のエントリデータを書き込んだフラッシュメモリ１８上の場所（ＰＢＡ）を記録する。ＬＵＴ逆引きテーブル２０２には、当該フラッシュメモリ１８上の場所（ＰＢＡ）に書き込みしたリージョン番号を記録する。
【００６１】
このような書き込み処理により、コンパクション処理によりＬＵＴコンパクションリスト２０４に登録されたリージョン番号のＬＵＴデータ（エントリデータ）を、フラッシュメモリ１８上の新たなブロックに書き込むことができる。
【００６２】
再度図８を参照すると、ＬＵＴコンパクション処理部１５１は、コンパクション元ブロックの全てのリージョン番号に対する一連の処理が終了すると、当該コンパクション元ブロックをフリーブロックに設定する（ブロック８０７のＹＥＳ、８０８）。これにより、ＬＵＴのコンパクション元ブロックは、図６に示すように、消去処理により新たなデータの記録ブロック（フリーブロック）６２０として再生することができる。
【００６３】
以上のように本実施形態によれば、ＬＵＴのコンパクション処理に必要なコンパクション元ブロック内の有効データと無効データを判定する判定処理を、ＤＲＡＭ１６０上のＬＵＴ逆引きテーブル２０２とＬＵＴ正引きテーブル２０１の相互参照により実現することができる。
【００６４】
即ち、従来のコンパクション処理では、コンパクション対象ブロック内のデータの有効または無効を判定するために、フラッシュメモリ１８０から当該ＬＴＵデータを読み出す処理が必要であった。これに対して、本実施形態の判定処理は、フラッシュメモリ１８０からのデータ読み出し処理が不要であり、ＤＲＡＭ１６０上で実行される。従って、ＬＴＵのコンパクション処理の時間を短縮化できるため、ＬＴＵのコンパクション処理の効率化を図ることが可能となる。
【００６５】
さらに、本実施形態では、ＤＲＡＭ１６０上には、ＬＵＴキャッシュ２００が格納される。ＬＵＴキャッシュ２００は、フラッシュメモリ１８上に分散記録されているＮＶＬＵＴ２１０のコピーである。ここで、ＮＶＬＵＴ２１０をフラッシュメモリ１８上に移動する場合（エントリデータのコピー）に、従来であればフラッシュメモリ１８からＮＶＬＵＴ２１０のデータをバッファメモリ（データバッファ１４）に読み出して、このバッファメモリからフラッシュメモリ１８に書き戻す処理が必要である。これに対して、本実施形態は、ＤＲＡＭ１６０上のＬＵＴキャッシュ２００のデータをフラッシュメモリ１８に書き出すことにより実現することができる。
【００６６】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００６７】
１０…ＳＳＤコントローラ、１１…ホストインターフェース（ホストＩ／Ｆ）、
１２…メイン制御部、１３…リード・ライト（Ｒ／Ｗ）制御部、
１４…データ用バッファメモリ（データバッファ）、１５…ＬＵＴ制御部、
１６…テーブル用バッファメモリ（テーブルバッファ）、
１７…フラッシュメモリコントローラ（NANDコントローラ）、
１８…NAND型フラッシュメモリ（フラッシュメモリ）、１９…データバス、
２０…ホストデバイス。
【図１】
2013206307.tif 000003
【図２】
2013206307.tif 000004
【図３】
2013206307.tif 000005
【図４】
2013206307.tif 000006
【図５】
2013206307.tif 000007
【図６】
2013206307.tif 000008
【図７】
2013206307.tif 000009
【図８】
2013206307.tif 000010
【図９】
2013206307.tif 000011