(57)【特許請求の範囲】
【請求項１】
不揮発性記憶装置と、前記不揮発性記憶装置と通信を行う情報処理装置とを有するメモリシステムであって、
前記情報処理装置は、
前記不揮発性記憶装置の第１の論理アドレス領域からデータを読み出し、
前記第１の論理アドレス領域に対応する読み出しデータが特定のデータパターンを指定する第１の関数で表されるデータと同じである場合に、前記不揮発性記憶装置に、前記第１の論理アドレス領域のデータを無効にするための削除通知を行う第１の制御回路を具備し、
前記不揮発性記憶装置は、
不揮発性記憶媒体と、
有効なデータに対応する論理アドレスと物理アドレスとを関連付ける管理テーブルと、
前記削除通知により指定された論理アドレスを無効にするように前記管理テーブルを書き換え、
前記情報処理装置から受信した読み出し命令に含まれる論理アドレスが無効である場合に、前記第１の関数で表されるデータを前記情報処理装置に送信する第２の制御回路と、
を具備することを特徴とするメモリシステム。
【請求項２】
前記不揮発性記憶媒体は、前記第１の関数を格納する記憶領域を有し、
前記第１の制御回路は、
前記記憶領域の前記第１の関数を第２の関数に書き換え、
前記不揮発性記憶装置から読み出された読み出しデータが前記第１の関数で表されるデータと同じである第２の論理アドレス領域に、前記第１の関数で表されるデータを書き込む
ことを特徴とする請求項１に記載のメモリシステム。
【請求項３】
前記第１の制御回路は、ユーザから指示を受けた場合に、前記削除通知に関する処理を実行することを特徴とする請求項１又は２に記載のメモリシステム。
【請求項４】
前記第１の制御回路は、規定の時刻に到達した場合に、前記削除通知に関する処理を実行することを特徴とする請求項１又は２に記載のメモリシステム。
【請求項５】
前記第２の制御回路は、前記削除通知に関する処理を実行するための命令を前記情報処理装置に送信し、
前記第１の制御回路は、前記不揮発性記憶装置から前記命令を受けた場合に、前記削除通知に関する処理を実行する
ことを特徴とする請求項１又は２に記載のメモリシステム。
【請求項６】
不揮発性記憶装置と、前記不揮発性記憶装置と通信を行う情報処理装置とを有するメモリシステムであって、
前記不揮発性記憶装置は、
不揮発性記憶媒体と、
有効なデータに対応する論理アドレスと物理アドレスとを関連付ける管理テーブルと、
前記情報処理装置から受信した読み出し命令に含まれる第１の論理アドレスが有効である場合に、前記管理テーブルにおいて前記第１の論理アドレスに対応する第１の物理アドレスに記憶されたデータを前記情報処理装置に送信する第１の制御回路と、
を具備し、
前記情報処理装置は、
前記不揮発性記憶装置の前記第１の論理アドレスを指定した読み出し命令を前記不揮発性記憶装置へ送信し、前記第１の物理アドレスに記憶された第１のデータを前記不揮発性記憶装置から受信し、前記第１のデータが特定のデータパターンと同じである場合に、前記不揮発性記憶装置へ、前記第１の論理アドレスのデータを無効にするための削除通知を行う第２の制御回路
を具備し、
前記第１の制御回路は、
前記情報処理装置から前記第１の論理アドレスのデータを無効にするための前記削除通知を受信した場合に、前記第１の論理アドレスを無効にするように前記管理テーブルを書き換える
ことを特徴とするメモリシステム。
【請求項７】
情報処理装置と通信を行う不揮発性記憶装置であって、
不揮発性記憶媒体と、
有効なデータに対応する論理アドレスと物理アドレスとを関連付ける管理テーブルと、
前記不揮発性記憶媒体からデータを読み出し、
前記読み出しデータが特定のデータパターンを指定する第１の関数で表されるデータと同じである場合に、前記読み出しデータの論理アドレスを無効にするように前記管理テーブルを書き換え、
前記情報処理装置から受信した読み出し命令に含まれる論理アドレスが無効である場合に、前記第１の関数で表されるデータを前記情報処理装置に送信する制御回路と、
を具備することを特徴とする不揮発性記憶装置。
【請求項８】
前記制御回路は、前記情報処理装置から一定期間アクセスがない場合に、前記管理テーブルを書き換える処理を実行することを特徴とする請求項７に記載の不揮発性記憶装置。
【請求項９】
前記制御回路は、前記情報処理装置から命令を受けた場合に、前記管理テーブルを書き換える処理を実行することを特徴とする請求項７に記載の不揮発性記憶装置。
【請求項１０】
前記制御回路は、不揮発性記憶媒体のフリーブロック数が規定値を下回った場合に、前記管理テーブルを書き換える処理を実行することを特徴とする請求項７に記載の不揮発性記憶装置。
【請求項１１】
不揮発性記憶装置の制御方法であって、
前記不揮発性記憶装置の第１の論理アドレス領域からデータを読み出す工程と、
前記第１の論理アドレス領域に対応する読み出しデータが特定のデータパターンを指定する第１の関数で表されるデータと同じであるか否かを判定する工程と、
前記読み出しデータと前記第１の関数で表されるデータとが同じである場合に、前記不揮発性記憶装置に、前記第１の論理アドレス領域のデータを無効にするための削除通知を行う工程と、
を具備することを特徴とする不揮発性記憶装置の制御方法。
【請求項１２】
前記不揮発性記憶装置に格納された前記第１の関数を第２の関数に書き換える工程と、
前記不揮発性記憶装置から読み出された読み出しデータが前記第１の関数で表されるデータと同じである第２の論理アドレス領域に、前記第１の関数で表されるデータを書き込む工程と、
をさらに具備することを特徴とする請求項１１に記載の不揮発性記憶装置の制御方法。
【請求項１３】
不揮発性記憶媒体と、有効なデータに対応する論理アドレスと物理アドレスとを関連付ける管理テーブルと、を有する不揮発性記憶装置と、前記不揮発性記憶装置と通信を行う情報処理装置とを備えるメモリシステムの制御方法であって、
前記不揮発性記憶装置が、前記情報処理装置から受信した読み出し命令に含まれる第１の論理アドレスが有効である場合に、前記管理テーブルにおいて前記第１の論理アドレスに対応する第１の物理アドレスに記憶されたデータを前記情報処理装置に送信し、
前記情報処理装置が、前記不揮発性記憶装置の前記第１の論理アドレスを指定した読み出し命令を前記不揮発性記憶装置へ送信し、前記第１の物理アドレスに記憶された第１のデータを前記不揮発性記憶装置から受信し、前記第１のデータが特定のデータパターンと同じであるか否かを判定し、前記第１のデータが前記特定のデータパターンと同じであると判定した場合に前記不揮発性記憶装置へ、前記第１の論理アドレスのデータを無効にするための削除通知を送信し、
前記不揮発性記憶装置が、前記第１の論理アドレスのデータを無効にするための前記削除通知を受信した場合に前記第１の論理アドレスを無効にするように前記管理テーブルを書き換える
ことを特徴とするメモリシステムの制御法方法。
【請求項１４】
不揮発性記憶装置を制御するためのプログラムであって、
前記プログラムは、情報処理装置に、
前記不揮発性記憶装置の第１の論理アドレス領域からデータを読み出す処理と、
前記第１の論理アドレス領域に対応する読み出しデータが特定のデータパターンを指定する第１の関数で表されるデータと同じであるか否かを判定する処理と、
前記読み出しデータと前記第１の関数で表されるデータとが同じである場合に、前記不揮発性記憶装置に、前記第１の論理アドレス領域のデータを無効にするための削除通知を行う処理と、
を実行させるためのプログラム。
【請求項１５】
前記不揮発性記憶装置に格納された前記第１の関数を第２の関数に書き換える処理と、
前記不揮発性記憶装置から読み出された読み出しデータが前記第１の関数で表されるデータと同じである第２の論理アドレス領域に、前記第１の関数で表されるデータを書き込む処理と、
をさらに具備することを特徴とする請求項１４に記載のプログラム。
【請求項１６】
情報処理装置と、
前記情報処理装置と通信を行い、不揮発性記憶媒体と、有効なデータに対応する論理アドレスと物理アドレスとを関連付ける管理テーブルと、を有し、前記情報処理装置から受信した読み出し命令に含まれる第１の論理アドレスが有効である場合に、前記管理テーブルにおいて前記第１の論理アドレスに対応する第１の物理アドレスに記憶されたデータを前記情報処理装置に送信する不揮発性記憶装置とを備えるメモリシステムを制御するためのプログラムであって、
前記プログラムは、前記情報処理装置に、
前記不揮発性記憶装置の前記第１の論理アドレスを指定した読み出し命令を前記不揮発性記憶装置へ送信する処理と、
前記第１の物理アドレスに記憶された第１のデータを前記不揮発性記憶装置から受信する処理と、
前記第１のデータが特定のデータパターンと同じであるか否かを判定する処理と、
前記第１のデータが前記特定のデータパターンと同じであると判定した場合に前記不揮発性記憶装置へ、前記第１の論理アドレスのデータを無効にするための削除通知を送信する処理と、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、メモリシステム、不揮発性記憶装置及びその制御方法に関する。
【背景技術】
【０００２】
オペレーティングシステム（ＯＳ）上において外部記憶装置（例えば、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）)のファイルデータが削除される場合、ＯＳ上でのデータの管理情報が削除されるだけで、外部記憶装置からは実際にはデータが削除されないようにする方式がある。ＯＳ上でデータ削除のたびに外部記憶装置で削除処理が行われるわけではないので、削除処理が行われない分、外部記憶装置の動作のパフォーマンスが向上する。この方式は特に、アクセスの遅いＨＤＤにおいて有効である。
【０００３】
一方で、ＯＳ上では削除したはずのデータが外部記憶装置では有効なデータであると認識されているため（これを無効データと呼ぶ）、外部記憶装置上でデータの存在しない空き領域が、ＯＳが認識している空き領域よりも常に少なくなってしまう。特に、外部記憶装置の空き領域が枯渇すると、論理アドレスと物理アドレスとが必ずしも一対一対応しないＳＳＤにおいて大きな問題となる場合がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−１５７１３３号公報
【特許文献２】特開２０１０−１６１１９９号公報
【特許文献３】特開２０１１−２９５８６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
実施形態は、読み出し動作を高速化し、かつ書き込みに利用可能なフリーブロックを増加させることが可能なメモリシステム、不揮発性記憶装置及びその制御方法を提供する。
【課題を解決するための手段】
【０００６】
実施形態に係るメモリシステムは、不揮発性記憶装置と、前記不揮発性記憶装置と通信を行う情報処理装置とを有するメモリシステムであって、前記情報処理装置は、前記不揮発性記憶装置の第１の論理アドレス領域からデータを読み出し、前記第１の論理アドレス領域に対応する読み出しデータが第１の関数で表されるデータと同じである場合に、前記不揮発性記憶装置に、前記第１の論理アドレス領域のデータを無効にするための削除通知を行う第１の制御回路を具備する。前記不揮発性記憶装置は、不揮発性記憶媒体と、有効なデータに対応する論理アドレスと物理アドレスとを関連付ける管理テーブルと、前記削除通知により指定された論理アドレスを無効にするように前記管理テーブルを書き換え、前記情報処理装置から受信した読み出し命令に含まれる論理アドレスが無効である場合に、前記第１の関数で表されるデータを前記情報処理装置に送信する第２の制御回路とを具備する。
【０００７】
実施形態に係る不揮発性記憶装置の制御方法であって、前記不揮発性記憶装置の第１の論理アドレス領域からデータを読み出す工程と、前記第１の論理アドレス領域に対応する読み出しデータが第１の関数で表されるデータと同じであるか否かを判定する工程と、前記読み出しデータと前記第１の関数で表されるデータとが同じである場合に、前記不揮発性記憶装置に、前記第１の論理アドレス領域のデータを無効にするための削除通知を行う工程とを具備する。
【図面の簡単な説明】
【０００８】
【図１】第１の実施形態に係るメモリシステムのブロック図。
【図２】管理テーブルの一部を説明する図。
【図３】第１の実施形態に係るホスト装置のブロック図。
【図４】ＮＡＮＤ型フラッシュメモリに格納されるデータの一部を説明する図。
【図５】デスクトップコンピュータの概略図。
【図６】ポータブルコンピュータの概略図。
【図７】ＳＳＤの書き込み動作を示すフローチャート。
【図８】ＳＳＤのＮＡＮＤ整理処理を示すフローチャート。
【図９】ＳＳＤの削除通知処理を示すフローチャート。
【図１０】ＳＳＤの読み出し動作を示すフローチャート。
【図１１】ホスト装置の最適化処理を示すフローチャート。
【図１２】ホスト装置の最適化フラグ設定処理を示すフローチャート。
【図１３】最適化プログラムのＧＵＩの一例を示す概略図。
【図１４】“０”で埋め尽くされたデータの割合と平均読み出し速度との関係を示すグラフ。
【図１５】“０”で埋め尽くされたデータの割合とフリーブロック量との関係を示すグラフ。
【図１６】第２の実施形態に係るホスト装置の最適化処理を示すフローチャート。
【図１７】第３の実施形態に係るホスト装置の最適化フラグ設定処理を示すフローチャート。
【図１８】第４の実施形態に係るＳＳＤの最適化起動情報の生成処理を示すフローチャート。
【図１９】ホスト装置の最適化フラグ設定処理を示すフローチャート。
【図２０】第５の実施形態に係るホスト装置の最適化処理を示すフローチャート。
【図２１】第６の実施形態に係るメモリシステムのブロック図。
【図２２】管理テーブルの一部を説明する図。
【図２３】ＳＳＤの最適化処理を示すフローチャート。
【図２４】比較元データ領域がＤＲＡＭ上に割り当てられる場合のメモリシステムのブロック図。
【図２５】物理アドレスのマッピングテーブルを説明する図。
【図２６】物理アドレスのマッピングテーブルを説明する図。
【図２７】比較元データ領域がＳＳＤコントローラ上に割り当てられる場合のメモリシステムのブロック図。
【図２８】物理アドレスのマッピングテーブルを説明する図。
【図２９】物理アドレスのマッピングテーブルを説明する図。
【図３０】比較元データ領域がＮＡＮＤ型フラッシュメモリ上に割り当てられる場合のメモリシステムのブロック図。
【図３１】物理アドレスのマッピングテーブルを説明する図。
【図３２】物理アドレスのマッピングテーブルを説明する図。
【図３３】第７の実施形態に係るホスト装置のブロック図。
【図３４】ＳＳＤのＮＡＮＤ整理処理を示すフローチャート。
【図３５】ＳＳＤの削除通知処理を示すフローチャート。
【図３６】ＳＳＤの読み出し動作を示すフローチャート。
【図３７】ホスト装置の最適化処理を示すフローチャート。
【図３８】実施例１に係るホスト装置の最適化処理を示すフローチャート。
【図３９】実施例２に係るホスト装置の比較元データ書き換え処理を示すフローチャート。
【図４０】実施例２に係るＳＳＤの比較元データ書き換え処理を示すフローチャート。
【図４１】第８の実施形態に係るＳＳＤの最適化処理を示すフローチャート。
【図４２】実施例１に係る論理アドレス及びデータの一例を示す図。
【図４３】0-fillセクタの存在確率分布を示す図。
【図４４】実施例２に係る論理アドレス及びデータの一例を示す図。
【図４５】0-fillセクタ及び1-fillセクタの存在確率分布を示す図。
【図４６】実施例３に係る論理アドレス及びデータの一例を示す図。
【図４７】３種類のデータパターンの存在確率分布を示す図。
【図４８】実施例６に係る論理アドレス及びデータの一例を示す図。
【図４９】最適化処理によって解放されるセクタを説明する図。
【図５０】実施例７に係る関数ｆの決定方法を説明する図。
【発明を実施するための形態】
【０００９】
ＳＳＤの空き領域が枯渇している、すなわちＳＳＤコントローラに有効なデータを全く持っていないと認識されているＮＡＮＤ型フラッシュメモリの物理ブロック（フリーブロック）が枯渇している場合、そのＳＳＤに書き込みを行うと、ＳＳＤコントローラに有効なデータを持っていると認識されているＮＡＮＤ型フラッシュメモリの物理ブロック（アクティブブロック）上の無効なデータ領域を検索し、有効なデータを整理（ＮＡＮＤ整理）して新たなフリーブロックを確保する処理に負荷がかかり、書き込みのパフォーマンスが著しく劣化してしまう。
【００１０】
また、ＮＡＮＤ型フラッシュメモリに無効データが多い、すなわちＳＳＤ上での空き領域が枯渇している状況で書き込みが行われると、特定の領域に書き込みが集中したり、頻繁に発生するＮＡＮＤ整理でＮＡＮＤ型フラッシュメモリの余分な消去が発生したりするため、ＳＳＤの信頼性が著しく劣化する可能性がある。
【００１１】
以下、実施形態について図面を参照して説明する。以下に示す幾つかの実施形態は、本発明の技術思想を具体化するための装置および方法を例示したものであって、構成部品の形状、構造、配置などによって、本発明の技術思想が特定されるものではない。なお、以下の説明において、同一の機能及び構成を有する要素については、同一符号を付し、重複説明は必要な場合にのみ行う。
【００１２】
［第１の実施形態］
［１．メモリシステムの構成］
図１は、第１の実施形態に係るメモリシステム１のブロック図である。メモリシステム１は、ホスト装置（情報処理装置）２と、外部記憶装置としての不揮発性記憶装置３とを備えている。不揮発性記憶装置３として、本実施形態では、ＳＳＤ（Solid State Drive）を例に挙げて説明する。
【００１３】
ＳＳＤ３は、インターフェースコントローラ１０、ＳＳＤコントローラ（制御回路）１１、メインメモリとしてのＤＲＡＭ１２、不揮発性記憶媒体としてのＮＡＮＤ型フラッシュメモリ１３、及びこれらを接続するバスを備えている。
【００１４】
インターフェースコントローラ１０は、ホスト装置２とのインターフェース処理を実行する。インターフェースコントローラ１０は、例えばＳＡＴＡ（Serial Advanced Technology Attachment）規格に準拠した通信インターフェースでホスト装置２に接続され、ＳＡＴＡ規格に準拠したインターフェース処理を実行する。インターフェース規格については、ＳＡＴＡ以外に、ＳＡＳ（Serial Attached SCSI）やＵＳＢ（universal serial bus）などを用いてもよい。
【００１５】
ＳＳＤコントローラ１１は、ＳＳＤ３全体の各種動作を制御する。ＳＳＤコントローラ１１は、ＮＡＮＤ型フラッシュメモリ１３に格納されているプログラムをＤＲＡＭ１２に読み出して所定の処理を実行することにより、各種テーブルをＤＲＡＭ１２に作成する。また、ＳＳＤコントローラ１１は、ホスト装置２から書き込み命令、読み出し命令、消去命令などを受信し、これらの命令に応答してＮＡＮＤ型フラッシュメモリ１３に所定の処理を実行する。
【００１６】
ＮＡＮＤ型フラッシュメモリ１３は、（ｎ＋１）個のＮＡＮＤメモリチップＣｈｉｐ０〜Ｃｈｉｐｎによって構成されている。ｎは、０以上の整数である。ＮＡＮＤメモリチップＣｈｉｐ０〜Ｃｈｉｐｎは、並列動作が可能なように構成されていてもよい。各ＮＡＮＤメモリチップは、複数のフラッシュメモリセルからなるメモリセルアレイ、及び周辺回路（例えば、ロウデコーダ、カラムデコーダ、ページバッファ、データキャッシュなど）を備えている。ＮＡＮＤ型フラッシュメモリ１３のメモリセルアレイは、複数のブロックから構成され、各ブロックは、複数のページから構成されている。ブロックは、データ消去の最小単位であり、ページは、データ書き込み及び読み出しの最小単位である。
【００１７】
ＮＡＮＤ型フラッシュメモリ１３のメモリセルアレイを構成するメモリセルトランジスタは、半導体基板上に形成された積層ゲート構造を備えたＭＯＳＦＥＴ（Metal Oxide Semiconductor Field Effect Transistor）から構成される。積層ゲート構造は、半導体基板上にゲート絶縁膜を介在して形成された電荷蓄積層（浮遊ゲート電極）、及び浮遊ゲート電極上にゲート間絶縁膜を介在して形成された制御ゲート電極を含んでいる。メモリセルトランジスタは、浮遊ゲート電極に蓄えられる電子の数に応じて閾値電圧が変化し、この閾値電圧の違いに応じてデータを記憶する。メモリセルトランジスタは、１ビットを記憶するように構成されていてもよいし、多値（２ビット以上のデータ）を記憶するように構成されていてもよい。また、メモリセルトランジスタは浮遊ゲート電極を有する構造に限らず、ＭＯＮＯＳ（Metal-Oxide-Nitride-Oxide-Silicon）型など、電荷蓄積層としての窒化界面に電子をトラップさせることで閾値電圧を調整可能な構造であってもよい。ＭＯＮＯＳ型のメモリセルトランジスタについても同様に、１ビットを記憶するように構成されていてもよいし、多値を記憶するように構成されていてもよい。また、不揮発性記憶媒体として、特開２０１０−１６１１９９や特開２０１１−２９５８６に記述されるような３次元的にメモリセルが配置された半導体記憶媒体であってもよい。
【００１８】
ＤＲＡＭ１２は、ホスト装置２とＮＡＮＤ型フラッシュメモリ１３との間でのデータ転送用キャッシュ、及びＳＳＤコントローラ１１の作業用メモリなどとして機能する。ＤＲＡＭ１２の作業領域用メモリに記憶されるものとしては、起動時などにＮＡＮＤ型フラッシュメモリ１３から読み出される管理テーブルや関数ｆなどがある。ＤＲＡＭ１２は、管理テーブルを格納する記憶領域１２Ａ、及び関数ｆを格納する記憶領域１２Ｂを含んでいる。管理テーブル及び関数ｆについての詳細は後述する。メインメモリとしては、ＤＲＡＭ以外のメモリを用いてもよい。メインメモリとしては、ランダムアクセスメモリ（ＲＡＭ）を用いることが望ましい。メインメモリとしては、ＤＲＡＭの他に、ＳＲＡＭ、ＦｅＲＡＭ（Ferroelectric Random Access Memory）、ＭＲＡＭ（Magnetoresistive Random Access Memory）、ＰＣＲＡＭ（Phase Change Random Access Memory）などを用いてもよい。また、上記メインメモリは、独立したチップとしてＳＳＤ基板上に実装してもよいし、組み込み型メモリとしてＳＳＤコントローラ内に実装してもよい。
【００１９】
図２は、ＤＲＡＭ１２に格納される管理テーブルの一部を説明する図である。ホスト装置２がＳＳＤ３へ命令を送信すると、インターフェースコントローラ１０を介してその命令がＳＳＤコントローラ１１に送られる。ＳＳＤコントローラ１１は、受信した命令を処理する。その際、ＳＳＤコントローラ１１は、ＤＲＡＭ１２上の管理テーブルを参照することで、適宜ホスト装置２より受信した論理アドレスを物理アドレスに変換する。論理アドレスとは、ホスト装置２で管理しているアドレスであり、物理アドレスとは、ＳＳＤ３で管理している実アドレスである。
【００２０】
図２に示すように、管理テーブルは、フリーブロックテーブル、アクティブブロックテーブル、及びアクティブページテーブルを含む。物理ブロックＩＤ及び物理ページアドレスは物理アドレスに含まれる。アクティブブロックテーブルは、物理ブロックＩＤと論理アドレスとを結び付けて管理しており、アクティブブロックテーブルに登録されている物理ブロック（アクティブブロック）は、少なくともＳＳＤコントローラ１１にとっては有効なデータを保持していることになる。フリーブロックテーブルは、論理アドレスに結び付けられていない物理ブロックを管理している。フリーブロックテーブルに登録されている物理ブロック（フリーブロック）は、論理アドレスに結び付けられていないため、有効なデータを保持していないことになる。
【００２１】
アクティブページテーブルは、物理ページアドレスと論理アドレスとを結び付けて管理しており、アクティブページテーブルに登録されている物理ページ（アクティブページ）は、少なくともＳＳＤコントローラ１１にとっては有効なデータを保持していることになる。また、アクティブページテーブルに登録されている物理ページは、これが属する物理ブロックＩＤと関連付けられている。なお、管理テーブルで管理されている論理アドレスは、ＳＳＤ３で管理できる最小データサイズ又はそれより大きいデータサイズのアドレスである。
【００２２】
次に、ホスト装置２の構成について説明する。図３は、ホスト装置２のブロック図である。ＣＰＵ（制御回路）２０がホスト装置２における中央演算処理装置であり、ホスト装置２における種々の演算及び制御はＣＰＵ２０によって行われる。ＣＰＵ２０はサウスブリッジ２１を介してＳＳＤ３や、ＤＶＤ−ＲＯＭなどの光学ドライブ３１の制御を行う。ＣＰＵ２０は、ノースブリッジ２２を介して、メインメモリとしてのＤＲＡＭ２３の制御を行う。
【００２３】
ユーザは、キーボード２９やマウス３０などの入力装置を通してホスト装置２の制御を行い、キーボード２９やマウス３０からの信号はＵＳＢ（Universal Serial Bus）コントローラ２８及びサウスブリッジ２１を介してＣＰＵ２０で処理される。ＣＰＵ２０は、ノースブリッジ２２及び表示コントローラ２４を介してディスプレイ（表示装置）２５に画像データやテキストデータなどを送る。ユーザは、ディスプレイ２５を介してホスト装置２からの画像データやテキストデータなどを視認することができる。
【００２４】
ＣＰＵ２０は、ＢＩＯＳ（Basic Input/Output System）−ＲＯＭ２６に格納されたＢＩＯＳを実行する。ＢＩＯＳは、ハードウェア制御のためのプログラムである。その他、ＣＰＵ２０は、サウスブリッジ２１を介してＬＡＮ（Local Area Network）コントローラ２７を制御する。
【００２５】
ＤＲＡＭ２３は、ＣＰＵ２０の作業用メモリとして機能し、ＯＳ（Operating System）を格納する記憶領域２３Ａ、最適化プログラムを格納する記憶領域２３Ｂ、最適化フラグを格納する記憶領域２３Ｃ、及び関数ｆを格納する記憶領域２３Ｄを含んでいる。ＯＳは、一般的に知られているように、ホスト装置２の入出力装置を管理し、ディスクやメモリを管理し、ソフトウェアがホスト装置２のハードウェアを利用可能にするための制御を行うなど、ホスト装置２全体を管理するプログラムである。最適化プログラム及び最適化フラグについての詳細は後述する。ＯＳ、最適化プログラム、及び関数fは、ホスト装置２が電源オフとなっている時は、図４に示すようにＳＳＤ３のＮＡＮＤ型フラッシュメモリ１３に格納されているが、ホスト装置２の起動時又はプログラム起動時に、ＮＡＮＤ型フラッシュメモリ１３からＤＲＡＭ２３にロードされる。ＮＡＮＤ型フラッシュメモリ１３は、ＯＳを格納する記憶領域１３Ａ、最適化プログラムを格納する記憶領域１３Ｂ、関数ｆを格納する記憶領域１３Ｃ、及び管理テーブルを格納する記憶領域１３Ｄを含んでいる。また、ＮＡＮＤ型フラッシュメモリ１３は、ユーザデータを格納する記憶領域（図示せず）を含んでいる。
【００２６】
次に、メモリシステム１の構成例について説明する。メモリシステム１は、例えば、デスクトップコンピュータやノートブック型のポータブルコンピュータとして実現し得る。図５は、メモリシステム１としてのデスクトップコンピュータの概略図である。
【００２７】
デスクトップコンピュータ１は、情報処理装置本体４０、ディスプレイ２５、キーボード２９、及びマウス３０などを備えている。情報処理装置本体４０は、主要なハードウェアが搭載されたマザーボード４１、ＳＳＤ３、及び電源装置４２などを備えている。ＳＳＤ３は、ＳＡＴＡケーブルを介してマザーボード４１に物理的に接続され、マザーボード４１上に実装されたサウスブリッジを介して、同じくマザーボード上に実装されたＣＰＵ２０に電気的に接続されている。電源装置４２は、デスクトップコンピュータ１で使用される各種電源を発生し、電源ケーブルを介してマザーボード４１やＳＳＤ３などに電源を供給する。
【００２８】
図６は、メモリシステム１としてのポータブルコンピュータの概略図である。ポータブルコンピュータ１は、情報処理装置本体５０、及びディスプレイユニット５１から構成されている。ディスプレイユニット５１は、例えばＬＣＤ（Liquid Crystal Display）で構成される表示装置２５が組み込まれている。
【００２９】
ディスプレイユニット５１は、情報処理装置本体５０に対し、この本体５０の上面が露出される開放位置と本体２の上面を覆う閉塞位置との間を回動自由に取り付けられている。本体２は薄い箱形の筐体を有しており、その上面には、電源スイッチ５２、キーボード２９、タッチパッド５３等が配置されている。また、本体５０も、デスクトップコンピュータと同様に、ＳＳＤ３、マザーボード、及び電源装置などを備えている。
【００３０】
その他、メモリシステム１はスチルカメラ或いはビデオカメラなどの撮像装置などであってもよいし、ゲーム機器やカーナビゲーションシステムなどであってもよい。
【００３１】
［２．動作］
＜２−１．書き込み動作＞
図７は、ＳＳＤ３の書き込み動作を示すフローチャートである。ＳＳＤ３は、ホスト装置２から書き込み命令を受信する（ステップＳ１０）。書き込み命令には、書き込みコマンド、論理アドレス、及びデータが含まれる。
【００３２】
続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からフリーブロックテーブルを読み出し、フリーブロックテーブルから物理ブロックＩＤを取得する（ステップＳ１１）。フリーブロックが存在しない場合は、後述するＮＡＮＤ整理処理を行い、物理ブロックＩＤを取得する（ステップＳ１３，Ｓ１２）。
【００３３】
続いて、ＳＳＤコントローラ１１は、取得した物理ブロックＩＤに対応するフリーブロックに対してプログラム処理を行う（ステップＳ１４）。続いて、ＳＳＤコントローラ１１は、プログラムされた物理ブロックＩＤをフリーブロックテーブルから削除する（ステップＳ１５）。続いて、ＳＳＤコントローラ１１は、アクティブブロックテーブル及びアクティブページテーブルを更新する（ステップＳ１６）。すなわち、プログラムされたブロックに対応する論理アドレス及び物理ブロックＩＤをアクティブブロックテーブルに追加し、さらに、論理アドレス、物理ブロックＩＤ及び物理ページアドレスをアクティブページテーブルに追加する。
【００３４】
なお、ステップＳ１４のプログラム処理の前に、書き込み対象の物理ブロックについて消去を行ってもよい。
【００３５】
＜２−２．ＮＡＮＤ整理処理＞
次に、ＳＳＤ３のＮＡＮＤ整理処理について説明する。図８は、ＳＳＤ３のＮＡＮＤ整理処理を示すフローチャートである。ある物理ブロックに対し、その物理ブロックに含まれる全ページのうちアクティブページテーブルに含まれているアクティブページ（有効ページ）は論理アドレスに対応付けられている。一方、ある物理ブロックに含まれる全ページが有効ページであるとは限らず、有効ページに該当しないページ（無効ページ）は論理アドレスに対応付けられていない。物理ブロックは無効ページの分だけデータに空きがあることになり、これら無効ページと有効ページとを分類することでフリーブロックを確保することができる。
【００３６】
まず、ＳＳＤコントローラ１１は、列番号ｉ＝０、空き領域累積量ｓ＝０に設定する（ステップＳ２０）。続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブブロックテーブルの先頭行を読み出し、物理ブロックＩＤを取得する（ステップＳ２１）。ステップＳ２１にて取得した物理ブロックＩＤを現在物理ブロックＩＤと呼ぶ。続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブページテーブルを読み出し、現在物理ブロックＩＤに含まれる全物理ページアドレスを取得する（ステップＳ２２）。
【００３７】
続いて、ＳＳＤコントローラ１１は、現在物理ブロックのうち無効ページのサイズを算出し、この無効ページサイズを変数ｖに代入する（ステップＳ２３）。続いて、ＳＳＤコントローラ１１は、“ｖ＞０”であるか否かを判定し（ステップＳ２４）。“ｖ＞０”である場合は、現在物理ブロックＩＤを整理対象ブロックリストに追加する（ステップＳ２６）。一方、ステップＳ２４において無効ページがないと判定された場合、ＳＳＤコントローラ１１は、現在物理ブロックＩＤをインクリメントして、作業対象を次の物理ブロックＩＤに移す（ステップＳ２５）。
【００３８】
続いて、ＳＳＤコントローラ１１は、空き領域累積量ｓに変数ｖを加算する（ステップＳ２７）。続いて、ＳＳＤコントローラ１１は、空き領域累積量ｓが物理ブロックサイズに到達したか否か、すなわちこれまでに取得した無効ページのサイズ総量が物理ブロックサイズに到達したか否かを判定する（ステップＳ２８）。空き領域累積量ｓが物理ブロックサイズに到達してない場合、列番号ｉに１を加算した後（ステップＳ２５）、ステップＳ２１以下の処理を繰り返す。
【００３９】
一方、空き領域累積量ｓが物理ブロックサイズに到達した場合、ＳＳＤコントローラ１１は、整理対象ブロックリストの全物理ブロックから全アクティブページのデータを読み出し、この読み出したデータをＤＲＡＭ１２に格納する（ステップＳ２９）。続いて、ＳＳＤコントローラ１１は、整理対象ブロックリストの全物理ブロックに対して消去処理を行う（ステップＳ３０）。続いて、ＳＳＤコントローラ１１は、アクティブブロックテーブル、フリーブロックテーブル、及びアクティブページテーブルを更新する（ステップＳ３１）。すなわち、消去処理が行われた物理ブロックをアクティブブロックテーブルから削除してフリーブロックテーブルに追加し、また、データが読み出されたアクティブページをアクティブページテーブルから削除する。
【００４０】
続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２に格納された全アクティブページのデータをフリーブロックにプログラムする（ステップＳ３２）。続いて、ＳＳＤコントローラ１１は、アクティブブロックテーブル、フリーブロックテーブル、及びアクティブページテーブルを更新する（ステップＳ３１）。すなわち、プログラムされた物理ブロックをフリーブロックテーブルから削除してアクティブブロックテーブルに追加し、また、プログラムされた物理ページをアクティブページテーブルに追加する。
【００４１】
このように、ＮＡＮＤ整理はＮＡＮＤ型フラッシュメモリ１３の読み出し動作、消去動作、及びプログラム動作を多数伴うため、多くの時間を要する。よって、フリーブロックが枯渇した状況で書き込みを行うとＮＡＮＤ整理が発生するため、ホスト装置２からみた書き込み処理速度が低下し、かつＮＡＮＤ型フラッシュメモリ１３の信頼性が低下する可能性がある。
【００４２】
なお、ステップＳ３０の消去処理はステップＳ１３のＮＡＮＤ整理内では行わずに、ステップＳ１４の書き込み動作直前に行うようにしてもよい。
【００４３】
＜２−３．削除通知処理＞
次に、ＳＳＤ３の削除通知処理について説明する。INCITS ATA8-ACSで採用されたdata set management command （通称、トリムコマンド）がある。このトリムコマンドは、削除通知として機能する。削除通知処理は、ホスト装置上でデータが削除された場合、削除されたデータの存在する論理アドレス空間をＳＳＤに通知することにより、以後ＳＳＤ上でもその領域を空き領域として扱うことができる方式である。削除通知を受信した場合には、ＳＳＤは管理テーブルにアクセスして該当領域を無効化する処理を行う。無効化処理では、ＳＳＤの管理テーブルを書き換えて該当領域が無効であることにすればよく、実際に該当領域のデータそのものを消さなくてもよいし、消してもよい。
【００４４】
図９は、ＳＳＤ３の削除通知処理を示すフローチャートである。ＳＳＤ３は、ホスト装置２から削除通知を受信する（ステップＳ４０）。削除通知には、削除コマンド、及び論理アドレスが含まれる。
【００４５】
続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブページテーブルを読み出す（ステップＳ４１）。続いて、ＳＳＤコントローラ１１は、削除通知によって指定された削除対象となる論理アドレス領域に対応する全ページのうち、ページ内全領域が削除通知対象である全ページをアクティブページテーブルから削除する（ステップＳ４２）。
【００４６】
続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブブロックテーブルを読み出す（ステップＳ４３）。続いて、ＳＳＤコントローラ１１は、アクティブブロックテーブルを参照し、アクティブページテーブルに物理ブロックＩＤを持たない物理ブロックをアクティブブロックテーブルから削除しフリーブロックテーブルに追加する（ステップＳ４４）。このように、ＳＳＤ３は、ＮＡＮＤ整理以外に、削除通知処理によってもフリーブロックを確保することができる。
【００４７】
なお、ホスト装置２が削除通知を行うデータサイズは、ＳＳＤ３が管理テーブルで管理している最小データサイズ以上であればよい。
【００４８】
＜２−４．読み出し動作＞
次に、ＳＳＤ３の読み出し動作について説明する。図１０は、ＳＳＤ３の読み出し動作を示すフローチャートである。ＳＳＤ３は、ホスト装置２から読み出し命令を受信する（ステップＳ５０）。読み出し命令には、読み出しコマンド、及び論理アドレスが含まれる。
【００４９】
続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブブロックテーブルを読み出す（ステップＳ５１）。続いて、ＳＳＤコントローラ１１は、ホスト装置２から受信した論理アドレスに対応する物理ブロックＩＤを参照する（ステップＳ５２）。アクティブブロックテーブルに物理ブロックＩＤが存在する場合、ＳＳＤコントローラ１１は、以後、既書き込み領域読み出し処理を行う。すなわち、ＳＳＤコントローラ１１は、アクティブページテーブルを読み出し（ステップＳ５３）、ＮＡＮＤ型フラッシュメモリ１３の該当ページを読み出す（ステップＳ５４）。そして、ＳＳＤコントローラ１１は、読み出したデータをホスト装置２に送信する（ステップＳ５５）。
【００５０】
一方、ホスト装置２から受信した論理アドレスに対応する物理ブロックＩＤがアクティブブロックテーブルに存在しない場合、ＳＳＤコントローラ１１は、以後、未書き込み領域読み出し処理を行う。すなわち、ＳＳＤコントローラ１１は、ＮＡＮＤ型フラッシュメモリ１３の読み出し処理を行わず、関数ｆで表されたデータをホスト装置２からの要求に対応するデータ長分ホスト装置２に送信する（ステップＳ５６）。具体的には、関数ｆで表されたデータは、アドレスＡｉ、データＤｉとすると、関数ｆ（Ａｉ）＝Ｄｉ（ｉは０以上の整数）を満たす。関数ｆは、ユーザ側で自由に設定することが可能であり、本実施形態では、論理アドレス（ＬＢＡ：Logical Block Addressing）を変数として、“関数ｆ（ＬＢＡ）＝０”と定義する。この例の場合、ＳＳＤコントローラ１１は、ホスト装置２からの要求に対応するデータ長分の“０”で埋め尽くされたデータをホスト装置２に送信する。
【００５１】
未書き込み領域読み出し動作は、ＮＡＮＤ型フラッシュメモリ１３の読み出し処理が伴わない。このため、アクティブページテーブルの読み出し処理及びＮＡＮＤ型フラッシュメモリ１３の読み出し処理が伴う既書き込み領域読み出し動作に比べ、未書き込み領域読み出し動作は高速に行われる。
【００５２】
＜２−５．最適化処理＞
次に、ホスト装置２の最適化処理について説明する。図１１は、ホスト装置２の最適化処理を示すフローチャートである。論理アドレス空間を物理ページサイズで区切って考え、区切った要素を論理ページと定義する。
【００５３】
ホスト装置２のＣＰＵ２０は、ある特定のフラグ（これを最適化フラグと呼ぶ）を監視し（ステップＳ６０）、最適化フラグが立っていることを確認すると、現在論理アドレスを０に設定する（ステップＳ６１）。続いて、ＣＰＵ２０は、現在論理アドレスからページサイズ分のデータ、すなわち現在論理アドレスから１つの論理ページ分を読み出すための読み出し命令をＳＳＤ３に送信する（ステップＳ６２）。これに対して、ＳＳＤ３は、ホスト装置２から受信した読み出し命令に従って読み出し処理を行い、読み出しデータをホスト装置２に送信する。
【００５４】
続いて、ＣＰＵ２０は、ＳＳＤ３から１つの論理ページ分の読み出しデータを受信する（ステップＳ６３）。続いて、ＣＰＵ２０は、読み出しデータが全て“０”で埋め尽くされているか否かを判定する（ステップＳ６４）。読み出しデータが全て“０”で埋め尽くされている場合、ＣＰＵ２０は、読み出した論理アドレス領域に対して削除通知を行う（ステップＳ６５）。これに対して、ＳＳＤ３は、前述した削除通知処理を行う。
【００５５】
続いて、ＣＰＵ２０は、現在論理アドレスにページサイズ分を追加する（ステップＳ６６）。続いて、ＣＰＵ２０は、全論理ページを読み出すまで、ステップＳ６２〜Ｓ６６の処理を繰り返す（ステップＳ６７）。
【００５６】
この最適化処理によって削除通知処理が行われた論理ページ群は、対応する論理アドレスがアクティブページテーブルから削除されるため、ＳＳＤ３内部では物理アドレスに対応付けられていない。削除通知処理が行われた論理ページに関してＳＳＤ３に読み出し命令を送信すると、図１０の未書き込み領域読み出し動作が行われ、ホスト装置２は“０”で埋め尽くされたデータをＳＳＤ３から受信するため、ホスト装置２からみたＳＳＤ３内部のデータは最適化処理前と変わらない。一方、未書き込み領域読み出し動作は、既書き込み領域読み出し動作よりも高速に行われるため、削除通知対象の論理ページ読み出しのパフォーマンスは、最適化処理前に比べて増大する。
【００５７】
なお、ホスト装置２は、最適化フラグが立っていることを確認し、かつＳＳＤ３がアイドル状態の時に最適化処理を行うようにしてもよい。これにより、ＳＳＤ３の通常動作（書き込み動作など）におけるパフォーマンスが低下するのを防ぐことができる。
【００５８】
この最適化処理は、全ＬＢＡ領域について行ってもよいし、一部のＬＢＡ領域に限定して行ってもよい。例えば、最適化処理を行う範囲を１０ギガバイトの範囲に限定して行ってもよい。その場合、例えば、初回の最適化処理はＬＢＡ＝０から１０ギガバイトの範囲にわたって実行し、次に最適化フラグが立って最適化処理が開始されると、前回最適化を行った領域の末尾の次のＬＢＡ（例えばＬＢＡ＝０＋１０ギガバイト＋１）から１０ギガバイトの範囲にわたって実行するようにしてもよい。このようにして、全ＬＢＡ領域を複数回に分けて最適化処理を行うことで、１回の最適化処理にかかる時間を短縮することができる。
【００５９】
＜２−６．最適化フラグ設定処理＞
次に、ホスト装置２の最適化フラグ設定処理について説明する。図１２は、ホスト装置２の最適化フラグ設定処理を示すフローチャートである。
【００６０】
ユーザは、ホスト装置２の最適化プログラムを起動し、ＧＵＩ（Graphical User Interface）上のボタン若しくはメニューを選択して最適化機能を呼び出す、又は、コマンドラインから最適化プログラムを起動し、コマンドを入力して最適化機能を呼び出す。図１３は、最適化プログラムのＧＵＩの一例を示す概略図である。図１３のＧＵＩに対して、ユーザはマウスなどを用いてＯＫボタンを選択する。このようなユーザの操作により、ホスト装置２の最適化機能が呼び出される。
【００６１】
ホスト装置２のＣＰＵ２０は、ユーザによって最適化機能が呼び出されたか否かを監視している（ステップＳ７０）。ユーザによって最適化機能が呼び出されると、ＣＰＵ２０は、ＤＲＡＭ２３の記憶領域２３Ｃに最適化フラグを立てる。以後、最適化フラグが立っていることが確認されると、前述した最適化処理が行われる。
【００６２】
［３．効果］
以上詳述した第１の実施形態によれば、以下のような効果が得られる。  
ホスト装置２上で有効なユーザデータのうち特定パターンの繰り返しであるような論理アドレス領域に関して、ホスト装置２からＳＳＤ３に対し削除通知を送信し、当該論理アドレス領域を削除する。そして、削除通知処理が行われたユーザデータをＮＡＮＤ型フラッシュメモリ１３以外の特定領域（ＤＲＡＭなど）から読み出すことで、当該ユーザデータの読み出し動作を高速化することができる。
【００６３】
また、ＳＳＤ３に削除通知を行うことでフリーブロックを確保することができるため、最適化処理後は書き込み動作のパフォーマンスが向上し、かつＳＳＤ３の信頼性が劣化するのを低減することができる。この効果は、ホスト装置２上で有効なユーザデータのうち“０”で埋め尽くされたデータが多ければ多いほど効果が増大する。
【００６４】
図１４は、“０”で埋め尽くされたデータの割合と平均読み出し速度との関係を示すグラフである。平均読み出し速度とは、ある特定の期間に発生した読み出し動作の読み出し速度を平均したものである。ＳＳＤ３に格納されたユーザデータのうち“０”で埋め尽くされたデータの割合が大きくなるほど未書き込み領域読み出し動作が増えるため、平均読み出し速度が速くなる。
【００６５】
図１５は、“０”で埋め尽くされたデータの割合とフリーブロック量との関係を示すグラフである。図１５のグラフのかさ上げされた部分は、ユーザ領域以外のフリーブロック量である。ＳＳＤ３に格納されたユーザデータのうち“０”で埋め尽くされたデータの割合が大きくなるほどホスト装置２からみたフリーブロック量が多くなる。
【００６６】
例えば、Windows（登録商標）においてＳＳＤ３に対しフルフォーマットを行うと、ＳＳＤ３の全論理アドレスに対し“０”データが書き込まれることになる。これにより、フリーブロックの数が大幅に減少してしまうため、書き込みパフォーマンスが低下し、以後の書き込み動作でＳＳＤ３の信頼性が劣化しやすくなる。ところが、フルフォーマット後のＳＳＤ３に対して本実施形態の最適化処理を行うと、“０”で埋め尽くされた領域全てに関し削除通知処理が行われるため、フリーブロックの数が大幅に増大する。これにより、書き込みパフォーマンスが増大し、以後の書き込み動作におけるＳＳＤ３の信頼性が劣化するのを低減することができる。
【００６７】
本実施形態は、ＳＳＤ３がアイドル状態の時にＳＳＤ３に対して最適化処理を行って管理テーブルを書き換えるソフトウェアやファームウェアをホスト装置２に実装するだけで実現できる。よって、本実施形態を実現するための機能を低コストかつ容易に実現できる。また、ＳＳＤ３がアイドル状態の時に最適化処理が行われるようにすることが望ましく、それにより本実施形態を実現した場合でもＳＳＤ３の書き込み等のパフォーマンス低下を伴わない。
【００６８】
なお、上記説明では、未書き込み領域読み出し動作においてＳＳＤコントローラ１１がホスト装置２に送信するデータとして“０”で埋め尽くされたデータを用いたが、関数ｆで表されたデータはユーザ側で自由に設定することが可能である。例えば、“関数ｆ（ＬＢＡ）＝１”と定義することで、“１”で埋め尽くされたデータを用いてもよい。また、“関数ｆ（ＬＢＡ）＝ＬＢＡ”と定義することで、“ＬＢＡ”で表されたデータを用いてもよい。さらに、論理アドレス空間を分割して管理し、第１のパーティションに対しては削除通知に“０”で埋め尽くされたデータを用い、第２のパーティションに対しては削除通知に“１”で埋め尽くされたデータを用いるようにしてもよい。この場合の関数ｆは、例えば、“ｆ（ＬＢＡ）＝０（ＬＢＡ＜Ｃａｐ／２, ｆ（ＬＢＡ）＝１（ＬＢＡ≧Ｃａｐ／２）”と定義される。Ｃａｐは、ＳＳＤ３の記憶容量である。
【００６９】
また、最適化処理でＳＳＤ３から読み出された論理ページが特定のデータパターンＸ（Ｘのデータサイズはページサイズと同じ）と同じである場合に、ホスト装置２が削除通知を行うようにしてもよい。この場合、“関数ｆ＝Ｘ”になっているものとする。この削除通知をＳＳＤ３が受信した場合、ＳＳＤコントローラ１１は、未書き込み領域読み出し動作においてＤＲＡＭ１２に格納されたデータパターンＸをホスト装置２に送信する。削除通知に特定のデータパターンを用いる例は、メモリシステム１が頻繁に同じデータを扱う場合に特に有効である。  本実施形態では、簡単のため、ＮＡＮＤ型フラッシュメモリの物理アドレスは管理情報においてＬＢＡに対して直接関連付けられていたが、例えば特開２００９−２１７６０３号のようにセクタサイズの２以上の自然数倍の管理単位を用いてＬＢＡを管理し、ＬＢＡではなく、上記管理単位とＮＡＮＤ型フラッシュメモリとの対応関係を管理情報に記述するようにしてもよい。ＬＢＡの管理単位などのように、ＮＡＮＤ型フラッシュメモリの物理アドレスとＬＢＡとの対応関係を記述する管理情報は様々な形態をとりうるが、物理アドレスとＬＢＡとの対応関係を記述するテーブル（論物変換テーブル）の取る形態の詳細は、本実施形態の本質には影響しない。
【００７０】
また、本実施形態においては、ＮＡＮＤ型フラッシュメモリにホスト装置から受信したデータが書き込まれるとき、ホスト装置から受信したデータそのもの（平文）が記録されるとしたが、平文をランダマイズしてＮＡＮＤ型フラッシュメモリに記憶したり、平文を暗号化してＮＡＮＤ型フラッシュメモリに記憶したりする場合にも本実施形態は適用可能である。
【００７１】
［第２の実施形態］
第１の実施形態の最適化処理では、全論理アドレスを読み出すようにしているのに対して、第２の実施形態では、ホスト装置２内のＯＳの管理領域にアクセスすることでファイルリストを取得し、ファイル単位で最適化処理を行うようにしている。
【００７２】
図１６は、第２の実施形態に係るホスト装置２の最適化処理を示すフローチャートである。ホスト装置２のＣＰＵ２０は、最適化フラグを監視し（ステップＳ８０）、最適化フラグが立っていることを確認すると、ＯＳからファイル管理情報を取得し、ファイル管理情報に登録されている全ファイルを最適化対象ファイルリストに追加する（ステップＳ８１）。最適化対象ファイルリストは、例えばホスト装置２のＤＲＡＭ２３に格納される。
【００７３】
続いて、ＣＰＵ２０は、最適化対象ファイルリストの先頭ファイルを現在ファイルに設定する（ステップＳ８２）。続いて、ＣＰＵ２０は、現在ファイルを読み出すための読み出し命令をＳＳＤ３に送信する（ステップＳ８３）。これに対して、ＳＳＤ３は、ホスト装置２から受信した読み出し命令に従って読み出し処理を行い、読み出しデータをホスト装置２に送信する。
【００７４】
続いて、ＣＰＵ２０は、ＳＳＤ３から現在ファイルに対応する読み出しデータを受信する（ステップＳ８４）。続いて、ＣＰＵ２０は、読み出したファイル内に“０”で埋め尽くされた論理ページが存在するか否かを判定する（ステップＳ８５）。“０”で埋め尽くされた論理ページが存在する場合、ＣＰＵ２０は、該当する論理ページに対して削除通知を行う（ステップＳ８６）。これに対して、ＳＳＤ３は、前述した削除通知処理を行う。
【００７５】
続いて、ＣＰＵ２０は、最適化対象ファイルリスト内の次のファイルを現在ファイルに設定する（ステップＳ８７）。続いて、ＣＰＵ２０は、最適化対象ファイルリスト内の全ファイルを読み出すまで、ステップＳ８３〜Ｓ８７の処理を繰り返す（ステップＳ８８）。
【００７６】
以上詳述したように第２の実施形態では、最適化処理において、全論理アドレス空間に対する読み出し動作を行わず、ホスト装置２上で有効なファイルに対してのみ読み出し動作を行うようにしている。このため、最適化対象のデータ量を減らすことができるため、最適化処理にかかる時間を短縮することができる。
【００７７】
この最適化処理は、全ファイルについて行ってもよいし、一部のファイルに限定して行ってもよい。例えば、最適化処理を行うファイル数を１００００個に限定して行ってもよい。その場合、例えば、初回の最適化処理はファイルリスト先頭から１００００個にわたって実行し、次に最適化フラグが立って最適化処理が開始されると、前回最適化を行った最後のファイルの次のファイル（例えば、ファイルリストの“０＋１００００＋１”番目）から１００００個にわたって実行するようにしてもよい。或いは、最適化処理を行うファイルの容量を１０ギガバイトに限定して行ってもよい。その場合、例えば、初回の最適化処理はファイルリスト先頭から合計１０ギガバイト分のファイルにわたって実行し、次に最適化フラグが立って最適化処理が開始されると、前回最適化を行った最後のファイルの次のファイルから合計１０ギガバイト分のファイルにわたって実行するようにしてもよい。このようにして、全ファイルを複数回に分けて最適化処理を行うことで、１回の最適化処理にかかる時間を短縮することができる。
【００７８】
［第３の実施形態］
第３の実施形態は、最適化フラグ設定処理に関する他の実施例であり、ホスト装置２の時計が規定の時刻に到達した時に、最適化フラグを立てるようにしている。
【００７９】
図１７は、第３の実施形態に係るホスト装置２の最適化フラグ設定処理を示すフローチャートである。ホスト装置２は、時計を有しており、ホスト装置２のＣＰＵ２０は、この時計が規定の時刻に到達したか否かを監視している（ステップＳ９０）。規定の時刻に到達した場合、ＣＰＵ２０は、ＤＲＡＭ２３の記憶領域２３Ｃに最適化フラグを立てる。以後、最適化フラグが立っていることが確認されると、前述した最適化処理が行われる。
【００８０】
第３の実施形態では、メモリシステム１は、ユーザの明示的な指示なしにバックグラウンドで最適化処理を行うことが可能である。
【００８１】
［第４の実施形態］
第４の実施形態は、最適化フラグ設定処理に関する他の実施例であり、ＳＳＤ３からホスト装置２へ送信される情報をトリガとして、最適化フラグ設定処理を開始するようにしている。ＳＳＤ３からホスト装置２へ送信される最適化処理の実施を促す情報を最適化起動情報と呼ぶ。ＳＳＤ３内部で管理している情報の一つとして、例えば、フリーブロック数がある。第４の実施形態では、このフリーブロック数を用いて最適化起動情報を生成する。
【００８２】
まずは、ＳＳＤ３側の動作について説明する。図１８は、第４の実施形態に係るＳＳＤ３の最適化起動情報の生成処理を示すフローチャートである。ＳＳＤコントローラ１１は、フリーブロック数を監視しており（ステップＳ１００）、フリーブロック数が規定値（例えば、設計時に予め決められている規定値）を下回った場合、ＳＳＤコントローラ１１は、ホスト装置２に最適化起動情報を送信する（ステップＳ１０１）。上記規定値としては、例えば、ＳＳＤ３の書き込み動作において、書き込み速度を一定以上に保つために必要なフリーブロックの最低数を用いることができる。
【００８３】
次に、ホスト装置２側の動作について説明する。図１９は、ホスト装置２の最適化フラグ設定処理を示すフローチャートである。ホスト装置２のＣＰＵ２０は、ＳＳＤ３から最適化起動情報を受信したか否かを監視している（ステップＳ１１０）。最適化起動情報を受信すると、ＣＰＵ２０は、ＤＲＡＭ２３の記憶領域２３Ｃに最適化フラグを立てる。以後、最適化フラグが立っていることが確認されると、前述した最適化処理が行われる。
【００８４】
最適化起動情報の監視及び授受には、例えば、メモリの自己診断機能であるS.M.A.R.T（Self-Monitoring Analysis and Reporting Technology）のコマンドであるSMART READ DATA（B0h（D0h））又はベンダー独自のコマンドを用いてもよい。或いは、ＣＰＵ２０は、例えば、S.M.A.R.TのコマンドであるSMART READ DATA（B0h（D0h））又はベンダー独自のコマンドを用いてＳＳＤ３のフリーブロック数を直接監視し、フリーブロック数が規定値（例えば、設計時に予め決められている規定値で、最適化プログラム２３Ｂ上に保持されている）を下回った場合、ＣＰＵ２０がＤＲＡＭ２３の記憶領域２３Ｃに最適化フラグを立てるようにしてもよい。
【００８５】
第４の実施形態では、ＳＳＤ３側の最適なタイミングで最適化処理を行うことが可能である。
【００８６】
［第５の実施形態］
第５の実施形態は、関数ｆで定義されるデータパターンを、ＳＳＤ３の使用状況に応じて変更可能なようにメモリシステム１を構成している。図２０は、第５の実施形態に係るホスト装置２の最適化処理を示すフローチャートである。特定のデータパターンをＸと表記し、“関数ｆ＝Ｘ”になっているものとする。
【００８７】
図２０のステップＳ１２０〜Ｓ１２３は、図１１のステップＳ６０〜Ｓ６３と同じである。続いて、ＣＰＵ２０は、読み出しデータが関数ｆで表されるデータパターンと同じであるか否かを判定する（ステップＳ１２４）。読み出しデータが関数ｆで表されるデータパターンと同じである場合、ＣＰＵ２０は、読み出した論理アドレス領域に対して削除通知を行う（ステップＳ１２５）。これに対して、ＳＳＤ３は、前述した削除通知処理を行う。
【００８８】
続いて、ＣＰＵ２０は、現在論理アドレスにページサイズ分を追加する（ステップＳ１２６）。続いて、ＣＰＵ２０は、全論理ページを読み出すまで、ステップＳ１２２〜Ｓ１２６の処理を繰り返す（ステップＳ１２７）。
【００８９】
続いて、ＣＰＵ２０は、全論理アドレス領域のうちデータパターンＸの領域の合計サイズを算出する（ステップＳ１２８）。続いて、ＣＰＵ２０は、全論理アドレス領域のうちデータパターンＸと異なるデータパターンＸ´の領域の合計サイズを算出する（ステップＳ１２９）。
【００９０】
続いて、ＣＰＵ２０は、データパターンＸ´の合計サイズがデータパターンＸの合計サイズより大きいか否かを判定する（ステップＳ１３０）。データパターンＸ´の合計サイズがデータパターンＸの合計サイズ以下である場合、ＣＰＵ２０は、最適化処理を終了する。一方、データパターンＸ´の合計サイズがデータパターンＸの合計サイズより大きい場合、ＤＲＡＭ２３の記憶領域２３Ｄに格納されている“関数ｆ＝Ｘ”を“関数ｆ＝Ｘ´”に書き換える（ステップＳ１３１）。ステップ１３０における判定条件を（データパターンＸ´の合計サイズ）≧（データパターンＸの合計サイズ）とすると、データパターンＸ´の合計サイズとデータパターンＸの合計サイズがほぼ等しい時に関数ｆの書き換えが頻繁に発生するため、例えば（データパターンＸ´の合計サイズ）≧１．１×（データパターンＸの合計サイズ）のように、判定条件にマージンを持たせることが望ましい。
【００９１】
現時点では、データパターンＸである論理ページ群については削除通知処理が行われているので、ＳＳＤ３は、この論理ページをアクティブページとして管理していない。このため、ＣＰＵ２０は、データパターンＸである論理ページ群についてデータパターンＸに書き換える書き込み命令をＳＳＤ３に送信する（ステップＳ１３２）。続いて、ＣＰＵ２０は、ＮＡＮＤ型フラッシュメモリ１３の記憶領域１３Ｃに格納されている“関数ｆ＝Ｘ”を“関数ｆ＝Ｘ´”に書き換える命令をＳＳＤ３に送信する（ステップＳ１３３）。関数ｆの書き換え命令は、例えばベンダー独自のコマンドを用いてもよい。これに対して、ＳＳＤ３は、ＮＡＮＤ型フラッシュメモリ１３の記憶領域１３Ｃに“関数ｆ＝Ｘ´”を書き込むとともに、ＤＲＡＭ１２の関数ｆを更新する。
【００９２】
以上詳述したように第５の実施形態によれば、削除通知対象であるデータパターンを変更することができる。これにより、最も存在確率が高いデータパターンに対して未書き込み領域読み出し動作が行われることになるので、読み出し動作を高速化することができる。なお、ファイル単位で最適化処理を行う第２の実施形態に第５の実施形態を適用することも可能である。
【００９３】
［第６の実施形態］
第６の実施形態は、ＳＳＤ３自身が前述した最適化処理と同じ処理を行うようにしている。図２１は、第６の実施形態に係るメモリシステム１のブロック図である。ＳＳＤ３のＤＲＡＭ１２は、最適化フラグを格納する記憶領域１２Ｃを含んでいる。その他の構成は、図１と同じである。
【００９４】
本実施形態では、ホスト装置２は、最適化プログラム２３Ｂ、最適化フラグ２３Ｃ、及び関数ｆ（２３Ｄ）を保持しなくてもよい。ＳＳＤコントローラ１１は、ＤＲＡＭ１２の記憶領域１２Ｃに最適化フラグを立てる。
【００９５】
図２２は、ＤＲＡＭ１２に格納される管理テーブルの一部を説明する図である。最適化処理を重複して行わないために、アクティブページテーブルには、最適化済マークが追加されていることが望ましい。最適化済マークは、論理アドレスに対応して設けられている。最適化済マークは、後述する最適化処理が実施されたか否かを判断するための情報である。
【００９６】
ＳＳＤ３の書き込み動作は、第１の実施形態で示した図７のフローチャートと同じである。ただし、図７のステップＳ１６においてアクティブページテーブルを更新する際、最適化済マーク＝false（偽）を追加する。
【００９７】
次に、最適化処理について説明する。図２３は、ＳＳＤ３の最適化処理を示すフローチャートである。
【００９８】
ＳＳＤコントローラ１１は、ＤＲＡＭ１２の記憶領域１２Ｃに最適化フラグが立っていることを確認すると（ステップＳ１４０）、アクティブページテーブルの１行目を現在行に設定する（ステップＳ１４１）。続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブページテーブルの現在行を読み出す（ステップＳ１４２）。
【００９９】
続いて、ＳＳＤコントローラ１１は、現在行に含まれる最適化済マークを確認することで、現在行が示す物理ページが最適化済みであるか否かを判定する（ステップＳ１４３）。物理ページが最適化済みである場合（最適化済マーク＝True（真））は、当該物理ページに対して最適化処理は行われない。一方、物理ページが最適化済みでない場合（最適化済マーク＝false）、ＳＳＤコントローラ１１は、ＮＡＮＤ型フラッシュメモリ１３から現在行が示す物理ページを読み出す（ステップＳ１４４）。
【０１００】
続いて、ＳＳＤコントローラ１１は、読み出しデータが“０”で埋め尽くされている（“関数ｆ（ＬＢＡ）＝０”の場合）か否かを判定する（ステップＳ１４５）。読み出しデータが“０”で埋め尽くされている場合、ＳＳＤコントローラ１１は、アクティブページテーブルから現在行を削除する（ステップＳ１４６）。或いは、現在行の要素に無効なデータを書き込むことで、現在行を無効化してもよい。読み出しデータが“０”で埋め尽くされていない場合、ＳＳＤコントローラ１１は、現在行の最適化済マークに“True”を書き込む（ステップＳ１４７）。続いて、ＳＳＤコントローラ１１は、アクティブページテーブルの次の行を現在行に設定する（ステップＳ１４８）。
【０１０１】
続いて、ＳＳＤコントローラ１１は、ホスト装置２から割込み命令を受信した場合は、最適化処理を終了すべく、ステップＳ１５１に移行する。ホスト装置２から割込み命令を受信していない場合は、ＳＳＤコントローラ１１は、アクティブページテーブルの全行を読み出すまで、ステップＳ１４２〜Ｓ１４８の処理を繰り返す（ステップＳ１５０）。続いて、ＳＳＤコントローラ１１は、アクティブブロックテーブル及びフリーブロックテーブルを更新する（ステップＳ１５１）。すなわち、アクティブブロックテーブルを参照し、アクティブページテーブルに要素を持たない物理ブロックをアクティブブロックテーブルから削除してフリーブロックテーブルに追加する。なお、割込み命令が急を要する場合には、アクティブブロックテーブル及びフリーブロックテーブルの更新を後で行うようにしてもよい。
【０１０２】
ＳＳＤ３の読み出し動作及びＮＡＮＤ整理動作については、第１の実施形態と同じである。従って、最適化処理によって削除された論理ページに関してホスト装置２がＳＳＤ３に読み出し命令を送信すると、図１０の未書き込み領域読み出し動作が行われ、ホスト装置２は“０”で埋め尽くされたデータをＳＳＤ３から受信する（“関数ｆ（ＬＢＡ）＝０”の場合）ため、ホスト装置２からみたＳＳＤ３内部のデータは最適化処理前と変わらない。一方、未書き込み領域読み出し動作は、既書き込み領域読み出し動作よりも高速に行われるため、最適化対象の論理ページ読み出しのパフォーマンスは、最適化処理前に比べて増大する。また、第６の実施形態によれば、ホスト装置２の処理負担を軽減することができる。
【０１０３】
なお、最適化フラグを立てる条件としては、ホスト装置２から、例えばベンダー独自のコマンドなどによって明示的に指示された場合でもよいし、ホスト装置２から明示的に指示された場合でなくてもよい。例えば、ホスト装置２から一定期間（例えば１０秒）アクセスがない場合に、ＳＳＤコントローラ１１がＤＲＡＭ１２の記憶領域１２Ｃに最適化フラグを立てるようにしてもよい。また、第４の実施形態と同様に、ＳＳＤコントローラ１１は、フリーブロック数を監視しており、フリーブロック数が規定値（例えば、設計時に予め決められている規定値）を下回った場合に、ＤＲＡＭ１２の記憶領域１２Ｃに最適化フラグを立てるようにしてもよい。
【０１０４】
上記最適化は、アクティブページテーブルの全要素について行うようにしてもよいが、一部の要素に限定して行うようにしてもよい。例えば、各最適化動作において、１００００個の要素に限定して行うようにしてもよい。この場合、初回の最適化ではアクティブページテーブルの０番目〜９９９９番目の要素について最適化を行い、次回の最適化では１００００番目〜１９９９９番目の要素について最適化を行い、次回の最適化では２００００番目〜２９９９９番目の要素について最適化を行う、というようにしてもよい。このようにアクティブページテーブルを分割して最適化を行うことで、一回の最適化に要する時間を短縮することができる。
【０１０５】
なお、上記説明では、未書き込み領域読み出し動作においてＳＳＤコントローラ１１がホスト装置２に送信するデータとして“０”で埋め尽くされたデータを用いたが（“関数ｆ（ＬＢＡ）＝０”の場合）、関数ｆで表されたデータはユーザ側で自由に設定することが可能であり、ステップＳ１４５において、データパターンと関数ｆの比較が行われる。例えば、“関数ｆ（ＬＢＡ）＝１”と定義することで、“１”で埋め尽くされたデータを用いてもよい。また、“関数ｆ（ＬＢＡ）＝ＬＢＡ”と定義することで、“ＬＢＡ”で表されたデータを用いてもよい。さらに、論理アドレス空間を分割して管理し、第１のパーティションに対しては最適化に“０”で埋め尽くされたデータを用い、第２のパーティションに対しては最適化に“１”で埋め尽くされたデータを用いるようにしてもよい。この場合の関数ｆは、例えば、“ｆ（ＬＢＡ）＝０（ＬＢＡ＜Ｃａｐ／２, ｆ（ＬＢＡ）＝１（ＬＢＡ≧Ｃａｐ／２）”と定義される。Ｃａｐは、ＳＳＤ３の記憶容量である。
【０１０６】
また、ステップＳ１４５で、ＮＡＮＤ型フラッシュメモリ１３のあるＬＢＡから読み出されたデータが特定のデータパターンＸ（Ｘのデータサイズはページサイズと同じ）と同じである場合に、ＳＳＤコントローラ１１が最適化処理を行うようにしてもよい（ステップＳ１４６）。この場合、“関数ｆ＝Ｘ”に該当する。この削除通知をＳＳＤ３が受信した場合、ＳＳＤコントローラ１１は、未書き込み領域読み出し動作においてＤＲＡＭ１２に格納されたデータパターンＸをホスト装置２に送信する。削除通知に特定のデータパターンを用いる例は、メモリシステム１が頻繁に同じデータを扱う場合に特に有効である。
【０１０７】
本実施形態では、簡単のため、ＮＡＮＤ型フラッシュメモリの物理アドレスは管理情報においてＬＢＡに対して直接関連付けられていたが、例えば特開２００９−２１７６０３号のようにセクタサイズの２以上の自然数倍の管理単位を用いてＬＢＡを管理し、ＬＢＡではなく、上記管理単位とＮＡＮＤ型フラッシュメモリとの対応関係を管理情報に記述するようにしてもよい。ＬＢＡの管理単位などのように、ＮＡＮＤ型フラッシュメモリの物理アドレスとＬＢＡとの対応関係を記述する管理情報は様々な形態をとりうるが、物理アドレスとＬＢＡとの対応関係を記述するテーブル（論物変換テーブル）の取る形態の詳細は、本実施形態の本質には影響しない。
【０１０８】
また、本実施形態においては、ＮＡＮＤ型フラッシュメモリにホスト装置から受信したデータが書き込まれるとき、ホスト装置から受信したデータそのもの（平文）が記録されるとしたが、平文をランダマイズしてＮＡＮＤ型フラッシュメモリに記憶したり、平文を暗号化してＮＡＮＤ型フラッシュメモリに記憶したりする場合にも本実施形態は適用可能である。その際、ステップＳ１４５におけるデータの比較は、復号後の平文について行われることが望ましいが、復号前のランダマイズデータ又は暗号化データについて行ってもよい。
【０１０９】
［第７の実施形態］
第７の実施形態は、ホスト装置がある論理アドレス領域をＳＳＤから読み出したデータが比較元データと同一である場合、ホスト装置が上記論理アドレス領域に対して削除通知を行う。そして、上記論理アドレス領域に対応する論理アドレスを、ＮＡＮＤ型フラッシュメモリ上の物理アドレスを疑似的に割り当てた「比較元データ領域」に対応するよう管理テーブルを書き換えることで、繰り返しパターンであるようなユーザデータの読み出し動作を高速化し、ＳＳＤが利用可能なフリーブロックを増加させるようにしている。
【０１１０】
［１．メモリシステムの構成］
比較元データ領域に格納されているデータ（比較元データ）がＮＡＮＤ型フラッシュメモリの物理アドレス領域で繰り返し存在する場合、上記物理アドレス領域に対応するＬＢＡ（論理アドレス）は本実施形態により比較元データ領域に全て対応付けられる。これにより、最大で「（繰り返しデータパターンのデータ量）−（繰り返しデータ領域のデータ量）」に相当する物理ブロックがフリーブロックとなるため、ＳＳＤコントローラが利用可能なフリーブロックを増加させることができる。上記比較元データ領域は、ＤＲＡＭなどのＲＡＭ、ＳＳＤコントローラ内のＬＳＩ若しくはＲＡＭ、又はＮＡＮＤ型フラッシュメモリ上に割り当てられる。それぞれの場合について以下に説明する。なお、本実施形態では簡単のため、ＮＡＮＤ型フラッシュメモリの最小管理単位は物理ページサイズに等しいとする（一般的には最小管理単位は物理ページサイズの自然数倍であればよい）。
【０１１１】
＜比較元データ領域がＤＲＡＭ上の場合＞
図２４は、比較元データ領域がＤＲＡＭ１２上に割り当てられる場合のメモリシステム１のブロック図である。以後、簡単のため、ＮＡＮＤ型フラッシュメモリ１３の個別チップはブロック図から省略する。
【０１１２】
ＤＲＡＭ１２は、比較元データを格納する記憶領域１２Ｄを備えている。ＮＡＮＤ型フラッシュメモリ１３は、バックアップ用の比較元データ（以後、バックアップ比較元データという）を格納する記憶領域１３Ｅを備えている。ＮＡＮＤ型フラッシュメモリ１３の記憶領域１３Ｅには、工場出荷時に例えば”０”で埋め尽くされたデータのような初期データが書き込まれている。ＤＲＡＭ１２の記憶領域１２ＤとＮＡＮＤ型フラッシュメモリ１３の記憶領域１３Ｅとのサイズは等しい。ＳＳＤ３の起動時に、ＳＳＤコントローラ１１は、バックアップ比較元データをＤＲＡＭ１２に読み出す。
【０１１３】
本実施形態では、第１の実施形態に比べて、物理アドレスのアドレスマッピング方法に特徴がある。図２５は、物理アドレスのマッピングテーブルを説明する図である。図２５の“ｈ”は、１６進数表記を意味している。
【０１１４】
ＮＡＮＤ型フラッシュメモリ１３の全物理ページには物理ブロックＩＤと物理ページアドレスとが割り当てられており、全物理ページは互いに区別可能になっている。第１の実施形態では、物理アドレスにはＮＡＮＤ型フラッシュメモリ１３の物理ページのみが割り当てられていたが、本実施形態では、ＤＲＡＭ１２上の記憶領域１２Ｄ（比較元データ領域）がＮＡＮＤ型フラッシュメモリの物理アドレスとして割り当てられる。比較元データ領域の管理単位は、ＮＡＮＤ型フラッシュメモリ１３の最小管理単位に等しい、つまり本実施形態では、物理ページサイズに等しい。
【０１１５】
比較元データ領域の疑似的な物理ブロックＩＤは、アドレスマッピング方式によってＮＡＮＤ型フラッシュメモリ１３の物理ブロックＩＤと区別できるようになっている。比較元データ領域が割り当てられているＤＲＡＭ１２の物理アドレス領域はＮＡＮＤ型フラッシュメモリの物理ページサイズごとに分割して管理され、ＤＲＡＭ１２の物理アドレスが小さい順にそれら管理単位に対して疑似的な物理ページアドレスが昇り順で割り当てられる。比較元データ領域のサイズがＮＡＮＤ型フラッシュメモリ１３の物理ブロックサイズより大きい場合は、比較元データ領域が割り当てられているＤＲＡＭ１２の物理アドレス領域をＮＡＮＤ型フラッシュメモリ１３の物理ブロックサイズごとに分割し、ＤＲＡＭ１２の物理アドレスが小さい順にそれらに対して疑似的な物理ブロックＩＤを昇り順で割り当て、物理ページアドレスは０〜最大物理ページアドレスを繰り返す。比較元データ領域に割り当てられている物理ブロックＩＤは、工場出荷時の段階からアクティブブロックテーブルに登録されている。
【０１１６】
比較元データ領域のサイズは、ＮＡＮＤ型フラッシュメモリ１３の最小管理単位の自然数倍になっている、つまり本実施形態では、物理ページサイズの自然数倍になっている。比較元データ領域のサイズはＮＡＮＤ型フラッシュメモリ１３の物理ブロックのサイズ以上でもよいし、未満でもよい。以後、本実施形態では簡単のため、比較元データ領域のサイズは１物理ページ分とする（図２６）。比較元データ領域のサイズが複数物理ページ分の場合は、例えば比較元データ領域を物理ページごとに分割して処理すればよいので、実施形態の本質は同じである。
【０１１７】
＜比較元データ領域がＳＳＤコントローラ上の場合＞
図２７は、比較元データ領域がＳＳＤコントローラ１１上に割り当てられる場合のメモリシステム１のブロック図である。
【０１１８】
ＳＳＤコントローラ１１上のＳＲＡＭ（その他のＲＡＭでもよい）又はＬＳＩ（その他のＲＯＭでもよい）には、比較元データを格納する記憶領域１１Ａ（比較元データ領域）が割り当てられている。記憶領域１１ＡがＲＡＭの場合は、ＤＲＡＭの場合と同じように、ＳＳＤ３の起動時に、ＳＳＤコントローラ１１は、バックアップ比較元データを記憶領域１１Ａに読み出す。記憶領域１１ＡがＲＯＭの場合は、工場出荷時に例えば”０”で埋め尽くされたデータのような初期データがＲＯＭに書き込まれている。
【０１１９】
図２８に示すように、物理アドレスのマッピングテーブル方式は、前述したＤＲＡＭの場合と同じである。以後、本実施形態では簡単のため、比較元データ領域のサイズは１物理ページ分とする（図２９）。
【０１２０】
＜比較元データ領域がＮＡＮＤ型フラッシュメモリ上の場合＞
図３０は、比較元データ領域がＮＡＮＤ型フラッシュメモリ１３上に割り当てられる場合のメモリシステム１のブロック図である。
【０１２１】
ＮＡＮＤ型フラッシュメモリ１３の一部領域には、比較元データを格納する記憶領域１３Ｅ（比較元データ領域）が割り当てられている。ＮＡＮＤ型フラッシュメモリ１３の比較元データ領域には、工場出荷時に例えば”０”で埋め尽くされたデータのような初期データが書き込まれている。
【０１２２】
図３１は、物理アドレスのマッピングテーブルを説明する図である。ＮＡＮＤ型フラッシュメモリ１３の全物理ページには物理ブロックＩＤと物理ページアドレスとが割り当てられており、かつ、これら物理ページ群の一部が比較元データ領域として割り当てられる。比較元データ領域における管理単位などのデータ管理方式は、その他のＮＡＮＤ型フラッシュメモリ１３上の領域と同じである。比較元データ領域のサイズは、ＮＡＮＤ型フラッシュメモリ１３の最小管理単位の自然数倍になっている、つまり本実施形態では、物理ページサイズの自然数倍になっている。比較元データ領域の先頭アドレスは、いずれかの物理ページの先頭アドレスに等しい（物理ページの途中であってはいけない）。比較元データ領域に割り当てられている物理ブロックＩＤは、工場出荷時の段階からアクティブブロックテーブルに登録されていることが望ましい。
【０１２３】
比較元データ領域のサイズはＮＡＮＤ型フラッシュメモリ１３の物理ブロックのサイズ以上でもよいし、未満でもよい。以後、本実施形態では簡単のため、比較元データ領域のサイズは１物理ページ分とする（図３２）。比較元データ領域のサイズが複数物理ページ分の場合は、例えば比較元データ領域を物理ページごとに分割して処理すればよいので、実施形態の本質は同じである。
【０１２４】
以上、比較元データ領域がＤＲＡＭ１２、ＳＳＤコントローラ１１、又はＮＡＮＤ型フラッシュメモリ１３上に割り当てられた場合について説明してきたが、いずれの場合であっても、比較元データ領域は通常のＮＡＮＤ型フラッシュメモリの物理ページと同等の物理アドレスマッピングがされ、同等に扱うことができる。よって、以降の説明は、比較元データ領域が確保される部分（ＤＲＡＭ１２、ＳＳＤコントローラ１１、又はＮＡＮＤ型フラッシュメモリ１３）に関わらず同じように実施可能である。
【０１２５】
次に、ホスト装置２の構成について説明する。図３３は、ホスト装置２のブロック図である。ＤＲＡＭ２３は、関数ｆの代わりに、比較元データを格納する記憶領域２３Ｅを含んでいる。その他の構成は、第１の実施形態の図３と同じである。
【０１２６】
ホスト装置２のＣＰＵ２０は、ホスト装置２の起動時又は最適化プログラムの起動時に、ＳＳＤ３に比較元データを読み出すための読み出し命令を送信し、ＳＳＤ３から読み出された比較元データをＤＲＡＭ２３の記憶領域２３Ｅに格納する。読み出しには、読み出しコマンドを用いてもよいし、ベンダー独自のコマンドなどその他のコマンドを用いてもよい。或いは、ホスト装置２に接続された他の外部記憶装置に比較元データを保存しておき、ホスト装置２の起動時又は最適化プログラムの起動時に、ホスト装置２のＣＰＵ２０が当該外部記憶装置から比較元データを読み出すようにしてもよい。
【０１２７】
［２．動作］
＜２−１．ＮＡＮＤ整理処理＞
図３４は、ＳＳＤ３のＮＡＮＤ整理処理を示すフローチャートである。ＳＳＤコントローラ１１は、列番号ｉ＝０、空き領域累積量ｓ＝０に設定する（ステップＳ１６０）。続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブブロックテーブルの先頭行を読み出し、物理ブロックＩＤを取得する（ステップＳ１６１）。ステップＳ１６１にて取得した物理ブロックＩＤを現在物理ブロックＩＤと呼ぶ。
【０１２８】
続いて、ＳＳＤコントローラ１１は、図２６、図２９又は図３２のアドレスマッピングに基づき、現在物理ブロックＩＤが比較元データ領域を含むか否かを判定する（ステップＳ１６２）。現在物理ブロックＩＤが比較元データ領域を含む場合、ＳＳＤコントローラ１１は、現在物理ブロックＩＤをインクリメントして、作業対象を次の物理ブロックＩＤに移す（ステップＳ１６３）。現在物理ブロックＩＤが比較元データ領域を含まない場合、第１の実施形態の図８と同様に、ＤＲＡＭ１２からアクティブページテーブルを読み出し、現在物理ブロックＩＤに含まれる全物理ページアドレスを取得する（ステップＳ１６４）。このようにして、比較元データ領域はＮＡＮＤ整理対象から除外される。比較元データ領域はＮＡＮＤ整理対象から除外されるのが望ましいが、比較元データ領域をＮＡＮＤ整理対象としてもよい。以後のフローは第１の実施形態の図８と同じである。
【０１２９】
＜２−２．削除通知処理＞
次に、ＳＳＤ３の削除通知処理について説明する。図３５は、ＳＳＤ３の削除通知処理を示すフローチャートである。ＳＳＤ３は、ホスト装置２から削除通知を受信する（ステップＳ１８０）。削除通知には、削除コマンド、及び論理アドレスが含まれる。
【０１３０】
続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブページテーブルを読み出す（ステップＳ１８１）。続いて、ＳＳＤコントローラ１１は、アクティブページテーブルにおいて、削除通知によって指定された削除対象となる論理アドレス領域（削除対象論理領域）を比較元データ領域と関連付ける（ステップＳ１８２）。本実施形態では、比較元データ領域のサイズは１物理ページ分であるので、削除対象論理領域は１論理ページ分である。
【０１３１】
続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブブロックテーブルを読み出す（ステップＳ１８３）。続いて、ＳＳＤコントローラ１１は、アクティブブロックテーブルを参照し、アクティブページテーブルに物理ブロックＩＤを持たない物理ブロックをアクティブブロックテーブルから削除してフリーブロックテーブルに追加する（ステップＳ１８４）。このように、ＳＳＤ３は、ＮＡＮＤ整理以外に、削除通知処理によってもフリーブロックを確保することができる。
【０１３２】
＜２−３．読み出し動作＞
次に、ＳＳＤ３の読み出し動作について説明する。図３６は、ＳＳＤ３の読み出し動作を示すフローチャートである。ＳＳＤ３は、ホスト装置２から読み出し命令を受信する（ステップＳ１９０）。読み出し命令には、読み出しコマンド、及び論理アドレスが含まれる。
【０１３３】
続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブブロックテーブルを読み出し（ステップＳ１９１）、ホスト装置２から受信した論理アドレスに対応する物理ブロックＩＤを参照する。続いて、ＳＳＤコントローラ１１は、アクティブページテーブルを読み出し（ステップＳ１９２）、図２６、図２９又は図３２のアドレスマッピングに基づき、該当する物理アドレスの読み出し動作を行う（ステップＳ１９３）。この時、読み出し対象がＤＲＡＭ１２やＳＳＤコントローラ１１上の比較元データ領域である場合は、読み出し動作が高速に行われるため、読み出しパフォーマンスが向上する。そして、ＳＳＤコントローラ１１は、読み出したデータをホスト装置２に送信する（ステップＳ１９４）。
【０１３４】
＜２−４．最適化処理＞
次に、ホスト装置２の最適化処理について説明する。図３７は、ホスト装置２の最適化処理を示すフローチャートである。最適化フラグの設定処理は、これまでに述べたホスト装置２の処理と同様である。
【０１３５】
ホスト装置２のＣＰＵ２０は、最適化フラグを監視し（ステップＳ２００）、最適化フラグが立っていることを確認すると、現在論理アドレスを０に設定する（ステップＳ２０１）。続いて、ＣＰＵ２０は、現在論理アドレスからページサイズ分のデータ、すなわち現在論理アドレスから１つの論理ページ分を読み出すための読み出し命令をＳＳＤ３に送信する（ステップＳ２０２）。これに対して、ＳＳＤ３は、ホスト装置２から受信した読み出し命令に従って読み出し処理を行い、読み出しデータをホスト装置２に送信する。
【０１３６】
続いて、ＣＰＵ２０は、ＳＳＤ３から１つの論理ページ分の読み出しデータを受信する（ステップＳ２０３）。続いて、ＣＰＵ２０は、読み出しデータがＤＲＡＭ２３の記憶領域２３Ｅに格納された比較元データと一致しているか否かを判定する（ステップＳ２０４）。読み出しデータが比較元データと一致している場合、ＣＰＵ２０は、読み出した論理アドレス領域に対して削除通知を行う（ステップＳ２０５）。これに対して、ＳＳＤ３は、前述した削除通知処理を行う。
【０１３７】
続いて、ＣＰＵ２０は、現在論理アドレスにページサイズ分を追加する（ステップＳ２０６）。続いて、ＣＰＵ２０は、全論理ページを読み出すまで、ステップＳ２０２〜Ｓ２０６の処理を繰り返す（ステップＳ２０７）。最適化を行うＬＢＡ領域は全ＬＢＡ領域であってもよいし、ＬＢＡ領域の一部であってもよい。
【０１３８】
この最適化処理によって削除通知処理が行われた論理ページ群は、ＳＳＤ３内の比較元データ領域の物理アドレスに関連付けられることになる。削除通知処理が行われた論理ページに関してホスト装置２がＳＳＤ３に読み出し命令を送信すると、比較元データをＳＳＤ３から受信するため、ホスト装置２からみたＳＳＤ内部のデータは最適化処理前と変わらない。一方、比較元データ領域がＳＳＤ３側のＤＲＡＭやＳＳＤコントローラに存在する場合、比較元データの読み出し動作は高速に行われるため、削除通知対象の論理ページ読み出しのパフォーマンスは、最適化処理前に比べて増大する。
【０１３９】
［３.効果］
以上詳述した第７の実施形態によれば、以下のような効果が得られる。  
ホスト装置２上で有効なユーザデータのうち比較元データと同じである論理アドレス領域に関して、ホスト装置２からＳＳＤ３に対して削除通知を送信する。これにより、削除通知が行われた論理アドレスがＳＳＤ３内の比較元データ領域の物理アドレスに関連付けられる。そして、削除通知処理が行われたユーザデータをＳＳＤ３側のＤＲＡＭやＳＳＤコントローラに存在する比較元データ領域から読み出すことで、当該ユーザデータの読み出し動作を高速化することができる。
【０１４０】
また、最適化処理を行うことでフリーブロックを確保することができるため、最適化処理後は書き込み動作のパフォーマンスが向上し、かつＳＳＤ３の信頼性劣化が軽減する。本実施形態の効果は、ホスト装置２上で有効なユーザデータのうち比較元データに一致するデータが多ければ多いほど効果が増大する。
【０１４１】
［４.実施例］
（実施例１）
第８の実施形態に第２の実施形態を適用してもよい。すなわち、実施例１は、第２の実施形態と同様に、ホスト装置内のＯＳの管理領域にアクセスすることでファイルリストを取得し、ファイル単位で最適化処理を行うようにしている。
【０１４２】
図３８は、実施例１に係るホスト装置２の最適化処理を示すフローチャートである。ファイル単位でＳＳＤ３から読み出しデータを受信する工程は、第２の実施形態の図１６と同じである。
【０１４３】
続いて、ホスト装置２のＣＰＵ２０は、読み出したファイル内に比較元データと一致する論理ページが存在するか否かを判定する（ステップＳ２１５）。比較元データと一致する論理ページが存在する場合、ＣＰＵ２０は、該当する論理ページに対して削除通知を行う（ステップＳ２１６）。これに対して、ＳＳＤ３は、前述した削除通知処理を行う。その後の工程は、第２の実施形態の図１６と同じである。
【０１４４】
以上詳述したように実施例１では、最適化処理において、全論理アドレス空間に対する読み出し動作を行わず、ホスト装置２上で有効なファイルに対してのみ読み出し動作を行うようにしている。このため、最適化対象のデータ量を減らすことができるため、最適化処理にかかる時間を短縮することができる。最適化を行うファイルは全ファイルであってもよいし、一部のファイルであってもよい。
【０１４５】
（実施例２）
ＳＳＤ上の比較元データ、及びホスト装置上の比較元データは、工場出荷後に書き換えられてもよい。図３９は、実施例２に係るホスト装置２の比較元データ書き換え処理を示すフローチャートである。
【０１４６】
ホスト装置２のＣＰＵ２０は、例えばユーザの指示に応答して、ＤＲＡＭ２３の記憶領域２３Ｅに格納された旧比較元データを新比較元データに書き換える（ステップＳ２２０）。続いて、ＣＰＵ２０は、比較元データを書き換えるための書き換え命令、及び比較元データをＳＳＤ３に送信する（ステップＳ２２１）。比較元データを書き換えるための書き換え命令は、通常の書き込み命令でもよいし、ベンダー独自の命令などその他命令でもよい。
【０１４７】
図４０は、実施例２に係るＳＳＤ３の比較元データ書き換え処理を示すフローチャートである。ＳＳＤ３は、ホスト装置２から比較元データの書き換え命令、及び比較元データを受信する（ステップＳ２３０）。
【０１４８】
ＳＳＤ３の比較元データを書き換える場合、ＮＡＮＤ型フラッシュメモリ１３のデータに矛盾が生じないようにする必要がある。そこで、ＳＳＤコントローラ１１は、旧比較元データに関連付けられた論理ページに旧比較元データを書き込む（ステップＳ２３１）。例えば、ＳＳＤコントローラ１１は、旧比較元データをＮＡＮＤ型フラッシュメモリ１３の論理アドレス領域のうち旧比較元データに関連付けられた論理ページの数だけ複製し、これら論理ページに旧比較元データを書き込む。続いて、ＳＳＤコントローラ１１は、ＮＡＮＤ型フラッシュメモリ１３やＤＲＡＭ１２の比較元データ領域を新比較元データに書き換える（ステップＳ２３２）。
【０１４９】
本実施形態では、簡単のため、各種物理アドレスは管理情報においてＬＢＡに対して直接関連付けられていたが、例えば特開２００９−２１７６０３号のようにセクタサイズの２以上の自然数倍の管理単位を用いてＬＢＡを管理し、ＬＢＡではなく、上記管理単位とＮＡＮＤ型フラッシュメモリとの対応関係を管理情報に記述するようにしてもよい。ＬＢＡの管理単位などのように、ＮＡＮＤ型フラッシュメモリの物理アドレスとＬＢＡとの対応関係を記述する管理情報は様々な形態をとりうるが、物理アドレスとＬＢＡとの対応関係を記述するテーブル（論物変換テーブル）の取る形態の詳細は、本実施形態の本質には影響しない。
【０１５０】
また、本実施形態においては、ＮＡＮＤ型フラッシュメモリにホスト装置から受信したデータが書き込まれるとき、ホスト装置から受信したデータそのもの（平文）が記録されるとしたが、平文をランダマイズしてＮＡＮＤ型フラッシュメモリに記憶したり、平文を暗号化してＮＡＮＤ型フラッシュメモリに記憶したりする場合にも本実施形態は適用可能である。
【０１５１】
［第８の実施形態］
第８の実施形態は、第７の実施形態で示した比較元データに関する最適化処理をＳＳＤ３自身が行うようにしている。ＳＳＤ３が備える比較元データ領域の構成は第７の実施形態と同じであり、ＳＳＤ３が備える比較元データ領域は、ＤＲＡＭなどのＲＡＭ、ＳＳＤコントローラ内のＬＳＩ若しくはＲＡＭ、又はＮＡＮＤ型フラッシュメモリ上に割り当てられる。また、第７の実施形態と同様に、本実施形態では簡単のため、比較元データ領域のサイズは１物理ページ分とする。
【０１５２】
図４１は、第８の実施形態に係るＳＳＤ３の最適化処理を示すフローチャートである。ＳＳＤコントローラ１１は、ＤＲＡＭ１２の記憶領域１２Ｃに最適化フラグが立っていることを確認すると（ステップＳ２４０）、アクティブページテーブルの１行目を現在行に設定する（ステップＳ２４１）。続いて、ＳＳＤコントローラ１１は、ＤＲＡＭ１２からアクティブページテーブルの現在行を読み出す（ステップＳ２４２）。
【０１５３】
続いて、ＳＳＤコントローラ１１は、現在行が示す物理アドレスが比較元データ領域であるか否かを判定する（ステップＳ２４３）。現在行が示す物理アドレスが比較元データ領域である場合は、当該物理アドレスに対して最適化処理は行われない。一方、現在行が示す物理アドレスが比較元データ領域でない場合は、ＮＡＮＤ型フラッシュメモリ１３から現在行が示す物理ページを読み出す（ステップＳ２４４）。
【０１５４】
続いて、ＳＳＤコントローラ１１は、読み出しデータが比較元データと一致しているか否かを判定する（ステップＳ２４５）。読み出しデータが比較元データと一致している場合、ＳＳＤコントローラ１１は、アクティブページテーブルの現在行に、比較元データ領域に疑似的に割り当てられた物理ブロックＩＤ、及び比較元データ領域に疑似的に割り当てられた物理ページアドレスを書き込む（ステップＳ２４６）。読み出されたデータが比較元データ領域のデータに一致しない場合は、当該物理ページに対して最適化処理は行われない。
【０１５５】
その後、第６の実施形態の図２３と同様に、アクティブページテーブルの全行に対して最適化処理が行われる。最適化処理は一部の行について行われてもよい。続いて、ＳＳＤコントローラ１１は、アクティブブロックテーブル及びフリーブロックテーブルを更新する（ステップＳ２５０）。すなわち、ＳＳＤコントローラ１１は、アクティブブロックテーブルを参照し、ＮＡＮＤ型フラッシュメモリ１３の比較元データ領域以外の領域のうちアクティブページテーブルに要素を持たない物理ブロックに関して、アクティブブロックテーブルから削除してフリーブロックテーブルに追加する。なお、割込み命令が急を要する場合には、アクティブブロックテーブル及びフリーブロックテーブルの更新を後で行うようにしてもよい。
【０１５６】
ＳＳＤ３の読み出し動作及びＮＡＮＤ整理動作については、第７の実施形態と同じである。
【０１５７】
以上詳述したように第８の実施形態によれば、比較元データ領域のデータと同じデータを有する物理ページが複数ある場合、最適化処理により複数の論理アドレス（ＬＢＡ）が単一の比較元データ領域に関連付けられることになる。上記論理アドレスに関連付けられていた物理ページは解放されることになり、それによりフリーブロックを新たに確保できた場合は、最適化処理後は書き込み動作のパフォーマンスが向上し、かつＳＳＤ３の信頼性劣化が軽減する。
【０１５８】
また、比較元データ領域がＲＡＭ上やＳＳＤコントローラ上に確保されている場合は、比較元データ領域に関連付けられた論理アドレスに関してホスト装置２がＳＳＤ３に読み出し命令を送信すると、ＮＡＮＤ型フラッシュメモリ１３の読み出しが伴う読み出し動作よりも高速に読み出し動作が行われる。これにより、読み出しパフォーマンスが向上する。本実施形態の効果は、ＮＡＮＤ型フラッシュメモリ１３に書き込まれたデータのうち比較元データ領域に一致するデータが多ければ多いほど増大する。
【０１５９】
なお、第７の実施形態と同様に、ＳＳＤ上の比較元データは、工場出荷後に書き換えるようにしてもよい。この場合は、旧比較元データをＮＡＮＤ型フラッシュメモリ１３の論理アドレス領域のうち旧比較元データに関連付けられた論理ページの数だけ複製し、これら論理ページに旧比較元データを書き込む。その後、ＮＡＮＤ型フラッシュメモリ１３やＤＲＡＭ１２の比較元データ領域を新比較元データに書き換えることで、データに矛盾が生じない。
【０１６０】
また、最適化フラグを立てる条件としては、ホスト装置２から明示的に指示された場合に限らない。すなわち、第６の実施形態と同様に、ホスト装置２から一定期間（例えば１０秒）アクセスがない場合に最適化フラグを立てるようにしてもよいし、フリーブロック数が規定値（例えば、設計時に予め決められている規定値）を下回った場合に最適化フラグを立てるようにしてもよい。
【０１６１】
本実施形態では、簡単のため、各種物理アドレスは管理情報においてＬＢＡに対して直接関連付けられていたが、例えば特開２００９−２１７６０３号のようにセクタサイズの２以上の自然数倍の管理単位を用いてＬＢＡを管理し、ＬＢＡではなく、上記管理単位とＮＡＮＤ型フラッシュメモリとの対応関係を管理情報に記述するようにしてもよい。ＬＢＡの管理単位などのように、ＮＡＮＤ型フラッシュメモリの物理アドレスとＬＢＡとの対応関係を記述する管理情報は様々な形態をとりうるが、物理アドレスとＬＢＡとの対応関係を記述するテーブル（論物変換テーブル）の取る形態の詳細は、本実施形態の本質には影響しない。
【０１６２】
また、本実施形態においては、ＮＡＮＤ型フラッシュメモリにホスト装置から受信したデータが書き込まれるとき、ホスト装置から受信したデータそのもの（平文）が記録されるとしたが、平文をランダマイズしてＮＡＮＤ型フラッシュメモリに記憶したり、平文を暗号化してＮＡＮＤ型フラッシュメモリに記憶したりする場合にも本実施形態は適用可能である。その際、ステップＳ２４５におけるデータの比較は、復号後の平文について行われることが望ましいが、復号前のランダマイズデータまたは暗号化データについて行ってもよい。
【０１６３】
［第９の実施形態］
第１乃至６の実施形態では、ホスト装置（情報処理装置）内又はＳＳＤ内の関数ｆ（ＬＢＡ）を用いて最適化処理を行っている。第９の実施形態では、最適化プログラム設計時、製品設計時若しくは工場出荷前において、又は工場出荷後において関数ｆ（ＬＢＡ）を決定する手法について説明する。特に、ＳＳＤにインストールするＯＳやシステム構成が決定しているときは、それらシステムに対して最適な関数ｆ（ＬＢＡ）を最適化プログラム設計時、製品設計時若しくは工場出荷前に設定しておくことが望ましい。
【０１６４】
（実施例１）
図４２は、論理アドレス及びデータの一例を示す図である。ＳＳＤの論理アドレス領域は、論理アドレス（ＬＢＡ）によってホスト装置に認識される。論理アドレスは１セクタが最小管理単位となっており、１セクタは例えば５１２バイトである。図４２のように、各セクタに対し論理アドレス（0000h、0001h、0002h、・・・、ba02h、・・・）が割り当てられている。
【０１６５】
図４２は、あるＳＳＤ搭載パーソナルコンピュータにおいて、予めＯＳやその他ソフトウェアをインストールしておいてから出荷する場合に、ＳＳＤに出荷前に書き込まれるデータパターンの例である。或いは、実際には書かれていなくても、エンドユーザが書き込むであろうデータを想定して（シミュレートして）以下のように関数ｆ（ＬＢＡ）を決定してもよい。
【０１６６】
ＳＳＤは例えば出荷前にフルフォーマットが行われ、全論理アドレス領域に０データが書き込まれる。その後、ＳＳＤにＯＳやその他ソフトウェアがインストールされ、一部セクタに０でないデータが書き込まれる（図４２のＬＢＡ＝0000h、0001h、0003h、ba02hなど）。書き込みが行われていない論理アドレスに関しては“０”で埋め尽くされた１セクタ長のデータ（0-fillセクタ）が書き込まれたままである（図４２のＬＢＡ＝0002h、0004h、0005h、ba03hなど)。ＬＢＡ＝ba03h以降はデータが書かれておらず、全て0-fillセクタのままである。
【０１６７】
全論理アドレスを読み出して、0-fillセクタと比較することで、図４３のような0-fillセクタの存在確率分布を導くことができる。また、比較時に、0-fillセクタとなっているセクタ数合計を全論理アドレス領域の合計容量で割ると、正味の0-fillセクタの割合を導くことができる。
【０１６８】
関数ｆ（ＬＢＡ）＝０００・・・０（固定値、０は５１２バイト分の繰り返し)とすることで、最大で0-fillセクタとなっているセクタ数合計相当のブロックを開放してフリーブロックを確保することができる。
【０１６９】
また、最適化処理は、この正味の0-fillセクタの割合が有意であるとき（例えば５％以上であるとき）にのみ行うようにしてもよい。また、関数ｆ（ＬＢＡ）の書き換えは、この正味の0-fillセクタの割合が有意であるとき（例えば５％以上であるとき）にのみ行うようにしてもよい。0-fillセクタの割合が有意であるかどうかの基準は、例えば、以下のように決定される。
【０１７０】
（１）書き込み応答時間が所定値（例えば仕様書に提示されたスペック）以下となることを保証できるためのフリーブロックの全容量に占める割合
（２）Write Amplification（ＷＡ）が所定値以下となることを保証できるためのフリーブロックの全容量に占める割合
なお、上記ＷＡは以下のようにして定義される。
【０１７１】
ＷＡ＝（ＮＡＮＤ型フラッシュメモリに書き込まれたデータの総サイズ）／（ホスト装置からＳＳＤに転送された書き込みデータの総サイズ）
又は、
ＷＡ＝（ブロックの総消去回数）×（ブロックサイズ）／（ホスト装置からＳＳＤに転送された書き込みデータの総サイズ）
なお、上記“ＮＡＮＤ型フラッシュメモリに書き込まれたデータの総サイズ”は、ユーザデータだけでなく、管理情報、ＥＣＣの冗長データ、暗号化キーなど、ユーザデータ以外のデータも含むことが望ましい。
【０１７２】
（実施例２）
図４４は、関数ｆ（ＬＢＡ）が固定値とならない例である。ある論理アドレス領域ではあるデータパターンが頻発し、ある論理アドレス領域では別のデータパターンが頻発するというように、論理アドレス領域によって頻発する繰り返しパターンが異なる場合がある。図４４のように、論理アドレス領域の前半では0-fillセクタが多数存在する一方、論理アドレス領域の後半では1-fillデータ（全ビットが“１”で埋め尽くされたデータ、１６進数で表すとfで埋め尽くされたデータということになる）が多数存在するよう場合を考える。
【０１７３】
0-fillセクタの存在確率分布及び1-fillセクタの存在確率分布は図４５のようになる。この場合、関数ｆ（ＬＢＡ）＝０００・・・０（固定値）としたり、関数ｆ（ＬＢＡ）＝１１１・・・１（固定値）とするよりも、“関数ｆ（ＬＢＡ）＝０００・・・０ｈ（ＬＢＡ≦c000h），ｆ（ＬＢＡ）＝１１１・・・１ｈ（ＬＢＡ≦c000h）”のように、関数ｆ（ＬＢＡ）を２つの論理アドレス領域で異なる値とするほうが、解放できるセクタ数が多くなるため望ましい。
【０１７４】
（実施例３）
図４６は、３つの論理アドレス領域で頻発するデータが異なる場合である。0-fillセクタの存在確率分布、320a-fillセクタ（320aデータで埋め尽くされた１セクタ長のデータ）の存在確率分布、及び1-fillセクタの存在確率分布は図４７のようになる。この場合、“関数ｆ（ＬＢＡ）＝０００・・・０ｈ（ＬＢＡ≦7fffh），ｆ（ＬＢＡ）＝３２０ａ３２０ａ・・・３２０ａｈ（8000h≦ＬＢＡ≦c000h），ｆ（ＬＢＡ）＝１１１・・・１ｈ（ＬＢＡ≦c001h）”のように、関数ｆ（ＬＢＡ）を３つの論理アドレス領域で異なる値とするほうが、解放できるセクタ数が多くなるため望ましい。
【０１７５】
（実施例４）
実施例４では、論理アドレス領域をサイズＬごとに分割した管理単位を用いる。サイズＬはＬＢＡの最小単位以上である。関数ｆ（ＬＢＡ）は管理単位の内部では一定値をとるが、異なる管理単位間では関数ｆ（ＬＢＡ）は異なってもよい。先頭の管理単位では関数ｆ（ＬＢＡ）＝Ｄ０（固定値）、次の管理単位では関数ｆ（ＬＢＡ）＝Ｄ１（固定値）、・・・というようになる。この場合の関数ｆ（ＬＢＡ）は、以下のように表される。
【０１７６】
“ｆ（ＬＢＡ）＝Ｄ０（０≦ＬＢＡ≦Ｌ−１，ｆ（ＬＢＡ）＝Ｄ１（Ｌ≦ＬＢＡ≦２Ｌ−１），ｆ（ＬＢＡ）＝Ｄ２（２Ｌ≦ＬＢＡ≦３Ｌ−１，・・・，Ｄｋ（ｋＬ≦ＬＢＡ≦（ｋ＋１）Ｌ−１），・・・”
Ｄｋ（ｋ＝０、１、・・・）は、サイズがＬの任意のデータパターンである。
【０１７７】
Ｄｋ（ｋ＝０、１、・・・）の選び方には任意性があり、最適なＤｋを選ぶことで最適な関数ｆ（ＬＢＡ）が決定される。Ｄｋの各種候補に対して、ＳＳＤの出荷前検査装置、情報処理装置のＣＰＵ、又はＳＳＤコントローラは、以下の手法で点数付けを行う。
【０１７８】
（１）  各種セクタごとのデータを読み出す（又は、セクタの整数倍ごとにデータを読み出してもよいし、管理単位ごとにデータを読み出してもよい）
（２）  （１）で読み出したデータが関数ｆ（ＬＢＡ）に等しいか否かを判定する（セクタの整数倍ごとにデータを読み出した場合は、その中の全セクタが関数ｆ（ＬＢＡ）に等しいか否かを判定する）
（３）  等しい場合は１点、等しくない場合は０点と点数をつける
（４）  ＳＳＤの全論理アドレス領域に対して点数付けを行い、点数の合計を算出する（代表して一部領域のみについて点数付けを行ってもよい）
そして、もっとも高得点となったＤｋが最適ということになり、このＤｋを用いて最適な関数ｆ（ＬＢＡ）が決定される。例えば、Ｌ＝１２８ＭｉＢ（ＭｉＢ＝1,048,576バイト）とすると、ＳＳＤの全論理アドレス領域を始端から均等に１２８ＭｉＢごとに区切り、それぞれの区画を読み出し、区画内全データが関数ｆ（ＬＢＡ）に等しいか否かを判定し、等しい場合は１点加算し、合計点数を計算する。その点数計算を例えば（Ｄ０，Ｄ１，・・・）＝（0000・・・，0000・・・，・・・），（FFFF・・・，FFFF・・・，・・・），（FFFF・・・，0000・・・，・・・），（0000・・・，FFFF・・・，・・・）のような複数の候補について行い、もっとも得点の高い候補を最適な（Ｄ０，Ｄ１，・・・）として選定して関数ｆ（ＬＢＡ）を決定する。
【０１７９】
（実施例５）
実施例４では、管理単位として固定長に区切った区画を用いたが、可変長に区切った区画を管理単位として用いてもよい。この場合の関数ｆ（ＬＢＡ）は、以下のように表される。
【０１８０】
“ｆ（ＬＢＡ）＝Ｄ０（Ｌ０＝０≦ＬＢＡ≦Ｌ１−１，ｆ（ＬＢＡ）＝Ｄ１（Ｌ１≦ＬＢＡ≦Ｌ２−１），ｆ（ＬＢＡ）＝Ｄ２（Ｌ２≦ＬＢＡ≦Ｌ３−１，・・・，Ｄｋ（Ｌｋ≦ＬＢＡ≦Ｌ（ｋ＋１）−１），・・・”
Ｄｋ（ｋ＝０、１、・・・）は、サイズがＬの任意のデータパターンである。“Ｌ０＜Ｌ１＜Ｌ２＜・・・Ｌｋ＜・・・”である。
【０１８１】
（実施例６）
実施例６は、同一データで埋め尽くされているセクタが少ないため、前述の手法を適用しても十分な効果が得られないが、データとＬＢＡとに一定の相関がある場合のケースである（図４８）。このような場合には、より一般的な関数ｆ（ＬＢＡ）の決定手法を用いることが好ましい。例えば、複数の関数ｆ（ＬＢＡ）の候補を用意し、それぞれのｆ（ＬＢＡ）に対して前述の点数付けを行い、もっとも高得点のｆ（ＬＢＡ）を最適なｆ（ＬＢＡ）として決定する。実施例６では、図４９に示すように、データとＬＢＡとに一定の相関があるセクタが解放される。
【０１８２】
（実施例７）
例えば、２種類のパラメータａ，ｂについて、“関数ｆ（ＬＢＡ）＝ａ×ＬＢＡ＋ｂ”を定義し、パラメータａ，ｂを振ったものを関数ｆ（ＬＢＡ）の候補として用いる。そして、もっとも高得点の（ａ，ｂ）を求め、もっとも高得点の（ａ，ｂ）を用いて関数ｆ（ＬＢＡ）を決定してもよい。
【０１８３】
図５０は、実施例７に係る関数ｆ（ＬＢＡ）の決定方法を説明する図である。図５０には、パラメータｂがｂ１、ｂ２、ｂ３の場合を図示している。パラメータａを変えると、（ａ，ｂ）＝（ａ０，ｂ２）がもっとも得点の高い。よって、“関数ｆ（ＬＢＡ）＝ａ０×ＬＢＡ＋ｂ２”が算出される。
【０１８４】
より一般的には、ＬＢＡがＳＡＴＡ規格において一般的な４８ビットＬＢＡである場合にはＬＢＡ＝（ｄ０，ｄ１，ｄ２，・・・，ｄ４７）ｔという列数４８のベクトルとし（tは転置記号）、Ａを５１２×４８の行列とし、ｂを列数４０９６（１セクタ＝５１２バイト＝４０９６ビット）のベクトルとすることで、“関数ｆ（ＬＢＡ）＝Ａ×ＬＢＡ＋ｂ”というように関数ｆ（ＬＢＡ）を列数４０９６のベクトル形式で取得してもよい。この場合、ベクトルｆ（ＬＢＡ）の１列目が１ビット目のデータに、２列目が２ビット目のデータに、・・・、という対応関係がある。
【０１８５】
さらに一般的には、ＬＢＡがｎビットで記述されるとき、ＬＢＡ＝（ｄ０，ｄ１，ｄ２，・・・，ｄｎ−１）ｔという列数ｎのベクトルとし、Ａをｎ×ｍの行列とし、ｂを列数ｍのベクトルとすることで、“関数ｆ（ＬＢＡ）＝Ａ×ＬＢＡ＋ｂ”というように関数ｆ（ＬＢＡ）を列数ｍのベクトル形式で取得してもよい。
【０１８６】
上記各実施形態で説明したコントローラの処理は、プログラムで実現することも可能である。プログラムのフローチャートは、上記各実施形態で示したフローチャートを使用することができる。
【０１８７】
上記各実施形態では、不揮発性記憶装置３としてＳＳＤを例に挙げて説明したが、ＳＳＤ以外の不揮発性記憶装置に広く適用可能であり、例えば、磁性媒体（プラッタ）を用いたハードディスクドライブ（ＨＤＤ）や、ＮＡＮＤ型フラッシュメモリと磁性媒体（プラッタ）の両方を用いたハイブリッドハードディスクドライブ（ハイブリッドＨＤＤ）に適用することも可能である。
【０１８８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１８９】
１…メモリシステム、２…ホスト装置、３…ＳＳＤ、１０…インターフェースコントローラ、１１…ＳＳＤコントローラ、１２…ＤＲＡＭ、１３…ＮＡＮＤ型フラッシュメモリ、２０…ＣＰＵ、２１…サウスブリッジ、２２…ノースブリッジ、２３…ＤＲＡＭ、２４…表示コントローラ、２５…ディスプレイ、２６…ＢＩＯＳ−ＲＯＭ、２７…ＬＡＮコントローラ、２８…ＵＳＢコントローラ、２９…キーボード、３０…マウス、３１…光学ドライブ、４０…情報処理装置本体、４１…マザーボード、４２…電源装置、５０…情報処理装置本体、５１…ディスプレイユニット、５２…電源スイッチ、５３…タッチパッド。
【図１】
0005405513.tif 000002
【図２】
0005405513.tif 000003
【図３】
0005405513.tif 000004
【図４】
0005405513.tif 000005
【図５】
0005405513.tif 000006
【図６】
0005405513.tif 000007
【図７】
0005405513.tif 000008
【図８】
0005405513.tif 000009
【図９】
0005405513.tif 000010
【図１０】
0005405513.tif 000011
【図１１】
0005405513.tif 000012
【図１２】
0005405513.tif 000013
【図１３】
0005405513.tif 000014
【図１４】
0005405513.tif 000015
【図１５】
0005405513.tif 000016
【図１６】
0005405513.tif 000017
【図１７】
0005405513.tif 000018
【図１８】
0005405513.tif 000019
【図１９】
0005405513.tif 000020
【図２０】
0005405513.tif 000021
【図２１】
0005405513.tif 000022
【図２２】
0005405513.tif 000023
【図２３】
0005405513.tif 000024
【図２４】
0005405513.tif 000025
【図２５】
0005405513.tif 000026
【図２６】
0005405513.tif 000027
【図２７】
0005405513.tif 000028
【図２８】
0005405513.tif 000029
【図２９】
0005405513.tif 000030
【図３０】
0005405513.tif 000031
【図３１】
0005405513.tif 000032
【図３２】
0005405513.tif 000033
【図３３】
0005405513.tif 000034
【図３４】
0005405513.tif 000035
【図３５】
0005405513.tif 000036
【図３６】
0005405513.tif 000037
【図３７】
0005405513.tif 000038
【図３８】
0005405513.tif 000039
【図３９】
0005405513.tif 000040
【図４０】
0005405513.tif 000041
【図４１】
0005405513.tif 000042
【図４２】
0005405513.tif 000043
【図４３】
0005405513.tif 000044
【図４４】
0005405513.tif 000045
【図４５】
0005405513.tif 000046
【図４６】
0005405513.tif 000047
【図４７】
0005405513.tif 000048
【図４８】
0005405513.tif 000049
【図４９】
0005405513.tif 000050
【図５０】
0005405513.tif 000051