(57)【要約】【課題】管理情報を記憶するランダムアクセス可能なメモリの記憶容量を増大させることなく、ランダムリード及びランダムライト性能を向上させる。【解決手段】実施形態においては、ランダムアクセス可能な第１の半導体メモリに含まれる第１の記憶部と、ページ単位で読み出し及び書き込みが行われ、ページより大きなブロック単位で消去が行われる不揮発性の第２の半導体メモリに含まれる第２の記憶部と、第２の半導体メモリの記憶領域を、ブロック単位で前記第２の記憶部に割り当てるコントローラと、第２の記憶部のデータを第１の管理単位で管理するための第１の管理テーブルであって、第２の半導体メモリに記憶される第１の管理テーブルと、第２の記憶部のデータを第１の管理単位より大きな第２の管理単位で管理するための第２の管理テーブルであって、第１の半導体メモリに記憶される第２の管理テーブルとを備える。【選択図】図１
2012141946.tif 000002
【特許請求の範囲】
【請求項１】
ランダムアクセス可能な第１の半導体メモリに含まれる第１の記憶部と、
ページ単位で読み出し及び書き込みが行われ、前記ページより大きなブロック単位で消去が行われる不揮発性の第２の半導体メモリに含まれる第２の記憶部と、
前記第２の半導体メモリの記憶領域を、ブロック単位で前記第２の記憶部に割り当てるコントローラと、を備え、
前記コントローラは、
前記第２の記憶部のデータを第１の管理単位で管理するための第１の管理テーブルを前記第２の半導体メモリに記録し、
前記第２の記憶部のデータを前記第１の管理単位より大きな第２の管理単位で管理するための第２の管理テーブルを前記第１の半導体メモリに記録し、
前記第１の記憶部に書き込まれたセクタ単位の複数のデータを第１の管理単位のデータ及び第２の管理単位のデータの何れかとして前記第２の記憶部に追い出すデータ追い出し処理を実行し、前記第１の管理テーブル及び前記第２の管理テーブルの少なくとも一方を更新し、
前記第２の記憶部のリソース使用量が閾値を超えた場合、前記第２の記憶部の有効データを集めて前記第２の記憶部の他のブロックに書き直すデータ整理処理を実行し、前記第１の管理テーブル及び前記第２の管理テーブルの少なくとも一方を更新する、
ことを特徴とする半導体記憶装置。
【請求項２】
前記コントローラは、
前記第１の管理テーブルの少なくとも一部のキャッシュである第３の管理テーブルを前記第１の半導体メモリに記録し、
前記第２の記憶部へのデータ追い出し処理に応じて、前記第１の管理テーブル、前記第２の管理テーブル、及び前記第３の管理テーブルの少なくとも一つを更新し、
前記第２の記憶部でのデータ整理処理に応じて、前記第１の管理テーブル、前記第２の管理テーブル、及び前記第３の管理テーブルの少なくとも一つを更新する、
ことを特徴とする請求項１に記載の半導体記憶装置。
【請求項３】
前記コントローラは、前記データ追い出し処理において、
前記第１の記憶部において前記第２の管理単位のアドレスに含まれるデータの個数が所定の閾値以上である場合は、前記第１の記憶部に書き込まれたセクタ単位のデータを前記第２の管理単位のデータとして前記第２の記憶部に追い出し、
前記データの個数が前記所定の閾値未満である場合は、前記第１の記憶部に書き込まれたセクタ単位のデータを前記第１の管理単位のデータとして前記第２の記憶部に追い出す、
ことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項４】
前記コントローラは、前記データ追い出し処理において、
前記第２の管理単位のアドレスに含まれ、かつ、前記第２の管理単位のデータとして前記第２の記憶部に書き込んだ後で前記第１及び第２の記憶部に書き込んだデータの個数が所定の閾値以上である場合は、前記第１の記憶部に書き込まれたセクタ単位のデータを前記第２の管理単位のデータとして前記第２の記憶部に追い出し、
前記データの個数が前記所定の閾値未満である場合は、前記第１の記憶部に書き込まれたセクタ単位のデータを前記第１の管理単位のデータとして前記第２の記憶部に追い出す、
ことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項５】
前記コントローラは、前記データ追い出し処理において、
前記第１の記憶部に保持されるデータが所属する前記第２の管理単位のアドレスの個数が所定の閾値以上である場合は、前記第１の記憶部に書き込まれたセクタ単位のデータを前記第１の管理単位のデータとして前記第２の記憶部に追い出し、
前記アドレスの個数が前記所定の閾値未満である場合は、前記第２の管理単位のデータとして前記第２の記憶部に追い出す、
ことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項６】
前記コントローラは、前記データ追い出し処理において、
前記第２の管理単位のデータとして前記第２の記憶部に書き込んだ後で前記第１及び第２の記憶部にデータを書き込んだ前記第２の管理単位のアドレスの個数が所定の閾値以上である場合は、前記第１の記憶部に書き込まれたセクタ単位のデータを前記第２の管理単位のデータとして前記第２の記憶部に追い出し、
前記アドレスの個数が所定の閾値未満である場合は、前記第１の管理単位のデータとして前記第２の記憶部に追い出す、
ことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項７】
前記コントローラは、前記データ追い出し処理において、
ホスト装置からのアクセス頻度が閾値以上である場合は、前記第１の記憶部に書き込まれたセクタ単位のデータを前記第１の管理単位のデータとして前記第２の記憶部に追い出し、
前記アクセス頻度が閾値未満である場合は、前記第２の管理単位のデータとして前記第２の記憶部に追い出す、
ことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項８】
前記コントローラは、前記データ整理処理において、ホスト装置からのアクセス頻度が閾値未満である場合に、選択した整理対象のブロック内の有効データを集めて、第２の管理単位のデータとして他のブロックに書き直すことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項９】
前記コントローラは、整理対象のブロックを、書き込み時期が所定の閾値よりも古いブロックから優先して選択することを特徴とする請求項８に記載の半導体記憶装置。
【請求項１０】
前記コントローラは、整理対象のブロックを、有効データ数または有効データ率が所定の閾値よりも少ないブロックから優先して選択することを特徴とする請求項８に記載の半導体記憶装置。
【請求項１１】
前記コントローラは、整理対象のブロックを、書き込み時期が所定の閾値よりも古く、有効データ数または有効データ率が所定の閾値よりも少ないブロックから優先して選択することを特徴とする請求項８に記載の半導体記憶装置。
【請求項１２】
前記コントローラは、整理対象のブロックを、読み出しアクセスが所定の閾値よりも多いブロックから優先して選択することを特徴とする請求項８に記載の半導体記憶装置。
【請求項１３】
前記コントローラは、整理対象のブロックを、前記第２の管理単位のデータとして前記第２の記憶部に書き込んだ後で前記第１及び第２の記憶部に書き込んだデータの個数が所定の閾値よりも多い前記第２の管理単位のデータを含むブロックから優先して選択することを特徴とする請求項８に記載の半導体記憶装置。
【請求項１４】
前記コントローラは、整理対象のブロックを、読み出しアクセスが所定の閾値よりも多い前記第２の管理単位のデータを含むブロックから優先して選択することを特徴とする請求項８に記載の半導体記憶装置。
【請求項１５】
前記コントローラは、前記データ整理処理において、前記第２の管理単位のデータとして前記第２の記憶部に書き込んだ後で前記第１及び第２の記憶部にデータを書き込んだ第２の管理単位のアドレスの個数が所定の閾値を超えた場合に、選択した整理対象のブロック内の有効データを集めて第２の管理単位のデータとして他のブロックに書き直すことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項１６】
前記コントローラは、整理対象のブロックを、書き込み時期が所定の閾値よりも古いブロックから優先して選択することを特徴とする請求項１５に記載の半導体記憶装置。
【請求項１７】
前記コントローラは、整理対象のブロックを、有効データ数または有効データ率が所定の閾値よりも少ないブロックから優先して選択することを特徴とする請求項１５に記載の半導体記憶装置。
【請求項１８】
前記コントローラは、整理対象のブロックを、書き込み時期が所定の閾値よりも古く、有効データ数または有効データ率が所定の閾値よりも少ないブロックから優先して選択することを特徴とする請求項１５に記載の半導体記憶装置。
【請求項１９】
前記コントローラは、整理対象のブロックを、読み出しアクセスが所定の閾値よりも多いブロックから優先して選択することを特徴とする請求項１５に記載の半導体記憶装置。
【請求項２０】
前記コントローラは、整理対象のブロックを、前記第２の管理単位のデータとして前記第２の記憶部に書き込んだ後で前記第１及び第２の記憶部に書き込んだデータの個数が所定の閾値よりも多い前記第２の管理単位のデータを含むブロックから優先して選択することを特徴とする請求項１５に記載の半導体記憶装置。
【請求項２１】
前記コントローラは、整理対象のブロックを、読み出しアクセスが所定の閾値よりも多い前記第２の管理単位のデータを含むブロックから優先して選択することを特徴とする請求項１５に記載の半導体記憶装置。
【請求項２２】
前記コントローラは、前記データ整理処理において、
整理対象ブロック内の第２の管理単位のデータ内の有効な第１の管理単位のデータ量または整理対象ブロック内の第２の管理単位のデータ内の有効な第１の管理単位のデータ率が所定の閾値以上である第２の管理単位のデータを集めて、第２の管理単位のデータとして他のブロックに書き直し、
前記書き直しを実行した後、整理対象ブロック内の第１の管理単位のデータを集めて第２の管理単位のデータとして他のブロックに書き直す、
ことを特徴とする請求項８乃至請求項２１のいずれか一つに記載の半導体記憶装置。
【請求項２３】
前記コントローラは、ホスト装置からのアクセス頻度が閾値以上である場合に、選択した整理対象のブロック内の有効データを集めて第１の管理単位のデータとして他のブロックに書き直すことを特徴とする請求項１または２に記載の半導体記憶装置。
【請求項２４】
前記コントローラは、整理対象のブロックを、有効データ数または有効データ率が所定の閾値よりも少ないブロックから優先して選択することを特徴とする請求項２３に記載の半導体記憶装置。
【請求項２５】
前記コントローラは、整理対象のブロックを、書き込み時期が所定の閾値よりも古く、有効データ数または有効データ率が所定の閾値よりも少ないブロックから優先して選択することを特徴とする請求項２３に記載の半導体記憶装置。
【請求項２６】
前記コントローラは、前記第２の記憶部のリソース使用量としての第２の記憶部の未使用ブロック数が閾値より少なくなったときに、選択した整理対象のブロック内の有効データを集めて第１の管理単位のデータとして他のブロックに書き直すことを特徴とする請求項１または２に記載の半導体記憶装置。
【請求項２７】
前記コントローラは、整理対象のブロックを、有効データ数または有効データ率が所定の閾値よりも少ないブロックから優先して選択することを特徴とする請求項２６に記載の半導体記憶装置。
【請求項２８】
前記コントローラは、整理対象のブロックを、書き込み時期が所定の閾値よりも古く、有効データ数または有効データ率が所定の閾値よりも少ないブロックから優先して選択することを特徴とする請求項２６に記載の半導体記憶装置。
【請求項２９】
前記コントローラは、前記データ整理処理において、ホスト装置からのアクセス頻度が閾値未満である場合に、選択した整理対象のブロック内の有効データを集めて第１の管理単位のデータとして他のブロックに書き直すことを特徴とする請求項１または２に記載の半導体記憶装置。
【請求項３０】
前記コントローラは、整理対象のブロックを、書き込みアクセスが閾値より多い第２の管理単位のデータを含むブロックから優先して選択することを特徴とする請求項２９に記載の半導体記憶装置。
【請求項３１】
前記コントローラは、ホスト装置からのアクセス頻度が閾値以上である場合において、
整理対象ブロック内の第２の管理単位のデータ内の有効データ数または前記整理対象ブロック内の第２の管理単位のデータ内の有効データ率が閾値未満である場合は、前記整理対象のブロック内の有効データを集めて第１の管理単位のデータとして他のブロックに書き直し、
前記整理対象ブロック内の第２の管理単位のデータ内の有効データ数または前記整理対象ブロック内の第２の管理単位のデータ内の有効データ率が前記閾値以上である場合は、有効データ数または有効データ率が閾値以上存在する第２の管理単位のデータを管理単位の変換を行わずに第２の管理単位のデータとして他のブロックに書き直す、
ことを特徴とする請求項１または２に記載の半導体記憶装置。
【請求項３２】
前記コントローラは、
環境温度が閾値以上のとき、選択した整理対象のブロック内の有効データを集めて第２の管理単位のデータとして他のブロックに書き直し、
前記環境温度が閾値未満のとき、選択した整理対象のブロック内の有効データを集めて第１の管理単位のデータとして他のブロックに書き直す、
ことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項３３】
前記コントローラは、
前記半導体記憶装置の消費電力量を閾値以上とすべき場合に、選択した整理対象のブロック内の有効データを集めて第２の管理単位のデータとして他のブロックに書き直し、
前記消費電力量を閾値未満とすべき場合に、選択した整理対象のブロック内の有効データを集めて第１の管理単位のデータとして他のブロックに書き直すことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項３４】
前記コントローラは、
ホスト装置からのアクセス頻度が閾値未満である場合に、書き込み時期が第１の閾値より新しいブロックのなかで有効データ量が少ないブロックを選択し、かつ書き込み時期が第２の閾値よりも古いブロックの中で有効データ量が少ないブロックを選択し、選択したブロック内のデータを第１または第２の管理単位のデータとして他のブロックに書き直すことを特徴とする請求項１または請求項２に記載の半導体記憶装置。
【請求項３５】
ランダムアクセス可能な第１の半導体メモリに含まれる第１の記憶部と、
ページ単位で読み出し及び書き込みが行われ、前記ページより大きなブロック単位で消去が行われる不揮発性の第２の半導体メモリに含まれる第２の記憶部と、
前記第２の半導体メモリの記憶領域を、ブロック単位で前記第２の記憶部に割り当てるコントローラと、を備え、
前記コントローラは、
前記第２の記憶部のデータを第１の管理単位で管理するための第１の管理テーブルを前記第２の半導体メモリに記録し、
前記第２の記憶部のデータを前記第１の管理単位より大きな第２の管理単位で管理するための第２の管理テーブルを前記第１の半導体メモリに記録し、
前記第１の記憶部に書き込まれたセクタ単位の複数のデータを、前記第１の管理単位のデータとして前記第２の記憶部に追い出すデータ追い出し処理を実行し、前記第１の管理テーブル及び前記第２の管理テーブルの少なくとも一方を更新し、
前記第２の記憶部のリソース使用量が閾値を超えた場合、前記第２の記憶部の有効データを集めて前記第２の記憶部の他のブロックに書き直すデータ整理処理を実行し、前記第１の管理テーブル及び前記第２の管理テーブルの少なくとも一方を更新し、
前記データ整理処理において、ホスト装置からのアクセス頻度が閾値未満である場合に、選択した整理対象のブロック内の有効データを集めて第２の管理単位のデータとして他のブロックに書き直す、
ことを特徴とする半導体記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、不揮発性半導体メモリを備えた半導体記憶装置に関する。
【背景技術】
【０００２】
ＳＳＤ（Solid  State  Drive）では、ホストが指定する論理アドレスのデータをＮＡＮＤフラッシュメモリのどの位置に記録するかを管理するデータ管理機構と、ユーザデータを管理する単位の選択が読み書き性能とが、ＮＡＮＤフラッシュメモリの寿命を大きく左右する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特表２０１０−５２１７１８号公報
【特許文献２】特開２００１−１４２７７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の一つの実施形態は、管理情報を記憶するランダムアクセス可能なメモリの記憶容量を増大させることなく、ランダムリード及びランダムライト性能を向上させる半導体記憶装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の一つの実施形態によれば、ランダムアクセス可能な第１の半導体メモリに含まれる第１の記憶部と、ページ単位で読み出し及び書き込みが行われ、前記ページより大きなブロック単位で消去が行われる不揮発性の第２の半導体メモリに含まれる第２の記憶部と、前記第２の半導体メモリの記憶領域を、ブロック単位で前記第２の記憶部に割り当てるコントローラと、を備える。前記コントローラは、前記第２の記憶部のデータを第１の管理単位で管理するための第１の管理テーブルを前記第２の半導体メモリに記憶し、前記第２の記憶部のデータを前記第１の管理単位より大きな第２の管理単位で管理するための第２の管理テーブルを前記第１の半導体メモリに記憶し、前記第１の記憶部に書き込まれたセクタ単位の複数のデータを第１の管理単位のデータ及び第２の管理単位のデータの何れかとして前記第２の記憶部に追い出すデータ追い出し処理を実行し、前記第１の管理テーブル及び前記第２の管理テーブルの少なくとも一方を更新し、前記第２の記憶部のリソース使用量が閾値を超えた場合、前記第２の記憶部の有効データを集めて前記第２の記憶部の他のブロックに書き直すデータ整理処理を実行し、前記第１の管理テーブル及び前記第２の管理テーブルの少なくとも一方を更新する。
【図面の簡単な説明】
【０００６】
【図１】図１は、第１の実施形態のＳＳＤの構成例を示す機能ブロック図。
【図２】図２は、ＬＢＡ論理アドレスを示す図。
【図３】図３は、ＮＡＮＤメモリ内に形成された機能構成を示すブロック図。
【図４】図４は、管理テーブルの構成例を示す図。
【図５】図５は、ＷＣ管理テーブルの一例を示す図。
【図６】図６は、トラック管理テーブルの一例を示す図。
【図７】図７は、正引きクラスタ管理テーブルの一例を示す図。
【図８】図８は、揮発性クラスタ管理テーブルの一例を示す図。
【図９】図９は、逆引きクラスタ管理テーブルの一例を示す図。
【図１０】図１０は、トラックエントリ管理テーブルの一例を示す図。
【図１１】図１１は、ブロック内有効クラスタ数管理テーブルの一例を示す図。
【図１２】図１２は、ブロックＬＲＵ管理テーブルの一例を示す図。
【図１３】図１３は、ブロック管理テーブルの一例を示す図。
【図１４】図１４は、読み出し処理の動作例を示すフローチャート。
【図１５】図１５は、アドレス解決を概念的に示す図。
【図１６】図１６は、アドレス解決を概念的に示す図。
【図１７】図１７は、アドレス解決を概念的に示す図。
【図１８】図１８は、書き込み処理の動作例を示すフローチャート。
【図１９】図１９は、忙しいときのＮＡＮＤメモリの整理を概念的に示す図。
【図２０】図２０は、暇なときのＮＡＮＤメモリの整理を概念的に示す図。
【図２１】図２１は、ＮＡＮＤメモリの整理の動作例を示すフローチャート。
【図２２】図２２は、第１の実施形態のＳＳＤの構成例を示す機能ブロック図。
【図２３】図２３は、ＮＡＮＤメモリの整理の他の動作例を示すフローチャート。
【図２４】図２４は、ＮＡＮＤメモリ内に形成された他の機能構成を示すブロック図。
【図２５】図２５は、ＮＡＮＤメモリ内に形成された他の機能構成を示すブロック図。
【図２６】図２６は、ＮＡＮＤメモリの他の追い出し処理を示すフローチャート。
【図２７】図２７は、ＮＡＮＤメモリの他の追い出し処理を示すフローチャート。
【図２８】図２８は、ＮＡＮＤメモリの他の追い出し処理を示すフローチャート。
【図２９】図２９は、ＮＡＮＤメモリの他の追い出し処理を示すフローチャート。
【図３０】図３０は、パーソナルコンピュータの外観を示す斜視図。
【図３１】図３１は、パーソナルコンピュータの機能構成例を示す図。
【発明を実施するための形態】
【０００７】
ＳＳＤの管理方式として、ユーザデータを管理する単位としてサイズの小さな管理単位を採用している場合、小さい管理単位でＳＳＤ全体を均一に管理することで、参照の局所性がない書き込み（広域ランダムライト）を連続して続行する際でも高い読み書き性能を達成可能であるが、大容量ＳＳＤを作る際には、管理単位が小さいことから管理情報を一時記録するための管理情報記憶バッファの容量が巨大になるという問題がある。
【０００８】
一方、ＳＳＤにおいて、ユーザデータを管理する単位として、大きな管理単位と小さな管理単位の２つを組み合わせて制御を行う方式では、管理情報記憶バッファの容量が少ない場合でも高い読み書き性能と寿命を達成することが可能である。しかし、この方式では、小さな単位で管理できるデータ量に制限があることから、広域ランダムライトを連続で実行し続ける場合、小さな管理単位から大きな管理単位への変換が必ず発生してしまうため、書き込みの速度が遅くなる可能性がある。
【０００９】
そこで、本実施形態においては、
・ユーザデータを管理する単位としては、大きな管理単位（第２の管理単位）と小さな管理単位（第１の管理単位）の２つを持つ
・ホストからのアクセス頻度が高いときは、小さな管理単位を使用して動作することで、広域ランダムライト性能を向上させる
・ホストからのアクセス頻度が低いときは、大きな管理単位と小さな管理単位とを使用して動作することで、リード性能と狭域ランダムライト性能を向上させる
といった制御を実行する。
また、不揮発性半導体メモリ上にＳＳＤ内全データ分の小さな管理単位の管理情報を持つ。この小さな管理単位の管理情報は、管理情報記憶バッファにキャッシュしてもよい。
また、ホストからのアクセス頻度が低いときに、断片化した小さな管理単位のデータを大きな管理単位のデータとして並べ直すことで、大きな管理単位と小さな管理単位との２つを組み合わせて制御を行う管理構造へ戻す。
【００１０】
以下、本発明の実施形態について図面を参照して説明する。なお、以下の説明において、同一の機能及び構成を有する要素については、同一符号を付し、重複説明は必要な場合にのみ行う。
【００１１】
先ず、本明細書で用いる用語について定義しておく。
・ページ：ＮＡＮＤ型フラッシュメモリ内部において一括して書き込み及び読み出しが可能な単位のこと。
・ブロック：ＮＡＮＤ型フラッシュメモリ内部において一括して消去が可能な単位であり、ブロックは、複数のページから構成される。
・セクタ：ホストからの最小アクセス単位のこと。セクタサイズは、例えば５１２Ｂ。
・クラスタ：ＳＳＤ内部で「小さなデータ」を管理する管理単位。セクタサイズの自然数倍がクラスタサイズとなるように定められる。
・トラック：ＳＳＤ内部で「大きなデータ」を管理する管理単位。クラスタサイズの２以上の自然数倍がトラックサイズとなるように定められる。
・フリーブロック（ＦＢ）：内部に有効データを含まない、用途未割り当てのブロックのこと。
・アクティブブロック（ＡＢ）：内部に有効データを含むブロックのこと。
・有効クラスタ：論理アドレスに対応するクラスタサイズの最新データ。
・無効クラスタ：同一論理アドレスの最新データが他の場所に書きこまれ、参照されることがなくなったクラスタサイズのデータ。
・有効トラック：論理アドレスに対応するトラックサイズの最新データ。
・無効トラック：同一論理アドレスの最新データが他の場所に書きこまれ、参照されることがなくなったトラックサイズのデータ。
・コンパクション：管理単位の変換を含まないデータの整理のこと。
・デフラグメンテーション（デフラグ）：クラスタからトラックへの管理単位の変換を含むデータの整理のこと。
・クラスタマージ（トラックの解体）：トラックからクラスタへの管理単位の変換を含むデータの整理のこと。
【００１２】
なお、以下実施形態に示す各機能ブロックは、ハードウェア、及びソフトウェアのいずれか、又は両者の組み合わせとして実現することができる。このため、各機能ブロックは、これらのいずれでもあることが明確となるように、概してそれらの機能の観点から以下に説明される。このような機能が、ハードウェアとして実現されるか、又はソフトウェアとして実現されるかは、具体的な実施態様、或いはシステム全体に課される設計制約に依存する。当業者は、具体的な実施態様ごとに、様々な方法でこれらの機能を実現し得るが、そのような実現を決定することは本発明の範疇に含まれる。
【００１３】
（第１の実施形態）
図１は、第１の実施形態におけるＳＳＤ１００の構成例を示す機能ブロック図である。ＳＳＤ１００は、ＡＴＡインタフェース（ＡＴＡ  Ｉ／Ｆ）などのホストインタフェース（ホストＩ／Ｆ）２を介してパーソナルコンピュータなどのホスト装置（以下、ホストと略す）１と接続され、ホスト１の外部メモリとして機能する。ホスト１としては、パーソナルコンピュータのＣＰＵ、スチルカメラ、ビデオカメラなどの撮像装置のＣＰＵなどがあげられる。
【００１４】
また、ＳＳＤ１００は、不揮発性半導体メモリとしてのＮＡＮＤ型フラッシュメモリ（以下、ＮＡＮＤフラッシュと略す）１０と、ＮＡＮＤフラッシュ１０よりも高速記憶動作及びランダムアクセスが可能で消去動作が不要な揮発性半導体メモリとしてのＤＲＡＭ２０（Dynamic Random Access Memory）と、ＮＡＮＤフラッシュ１０とホスト装置１間のデータ転送に関する各種制御を実行するコントローラ３０とを備える。ＳＳＤ１００に、環境温度を検出する温度センサ９０が設けられていてもよい。
【００１５】
揮発性半導体メモリとしては、ＤＲＡＭ２０の他に、ＳＲＡＭ（Static Random Access Memory）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）、ＭＲＡＭ（Magnetoresistive Random Access Memory）、ＰＲＡＭ（Phase Change Random Access Memory）などを採用することができる。また、揮発性半導体メモリはコントローラ３０に混載されていてもよい。コントローラ３０に混載された揮発性半導体メモリの容量が大きい場合は、後述するデータ及び管理情報をコントローラ３０内部の揮発性半導体メモリに格納し、コントローラ３０外部に別途揮発性半導体メモリを設けなくてもよい。
【００１６】
ＮＡＮＤフラッシュ１０は、ホスト１によって指定されたユーザデータを記憶したり、ユーザデータを管理する管理テーブルを記憶したり、ＤＲＡＭ２０で管理される管理情報をバックアップ用に記憶したりする。ＮＡＮＤフラッシュ１０のデータ領域を構成するデータストレージ（以下、ＤＳという）４０には、ユーザデータが記憶される。管理テーブルバックアップ領域１４には、ＤＲＡＭ２０で管理される管理情報がバックアップされる。
【００１７】
正引きの不揮発性クラスタ管理テーブル１２（以下、正引きクラスタ管理テーブルと略す）及び逆引きの不揮発性クラスタ管理テーブル１３（以下、逆引きクラスタ管理テーブルと略す）が、ＮＡＮＤフラッシュ１０上で管理されている。管理テーブルの詳細については、後述する。但し、ＮＡＮＤフラッシュ１０上で、便宜上、データ領域、管理領域と区別したが、これら領域において使用されるブロックが固定されているわけではない。
【００１８】
ＮＡＮＤフラッシュ１０は、複数のメモリセルがマトリクス状に配列されたメモリセルアレイを有し、個々のメモリセルは上位ページ及び下位ページを使用して多値記憶が可能である。ＮＡＮＤフラッシュ１０は、複数のメモリチップによって構成され、各メモリチップは、データ消去の単位であるブロックを複数配列して構成される。また、ＮＡＮＤ１０では、ページごとにデータの書き込み及びデータの読み出しが行われる。ブロックは、複数のページによって構成されている。なお、同一ページに対する上書きは、当該ページを含むブロック全体を一旦消去した後に行う必要がある。また、ＮＡＮＤフラッシュ１０を構成する並列動作可能な複数のチップから１個ずつブロックを選択し、これら複数のブロックを組みにして一括消去単位としてもよい。同様に、ＮＡＮＤフラッシュ１０を構成する並列動作可能な複数のチップから１個ずつページを選択し、これら複数のページを組みにして一括書き込み、一括読み出し単位としてもよい。
【００１９】
ＤＲＡＭ２０は、ホスト１とＮＡＮＤフラッシュ１０間でのデータ転送用キャッシュとして機能するライトキャッシュ（以下、ＷＣという）２１を有する。また、ＤＲＡＭ２０は、管理情報記憶用メモリ及び作業領域用メモリとして機能する。ＤＲＡＭ２０で管理される管理情報記憶テーブルとしては、ＷＣ管理テーブル２２、トラック管理テーブル２３、揮発性クラスタ管理テーブル２４、トラックエントリ管理テーブル２５、その他の各種管理テーブルを有する。管理テーブルの詳細については、後述する。ＤＲＡＭ２０で管理される管理テーブルは、ＮＡＮＤフラッシュ１０に記憶されている各種管理テーブル（正引きのクラスタ管理テーブル１２及び逆引きのクラスタ管理テーブル１３を除いた管理テーブル）が起動時などに展開されたものであり、電源断時には、ＮＡＮＤフラッシュ１０の管理テーブルバックアップ領域１４に退避保存される。
【００２０】
なお、データ転送用キャッシュ領域と管理情報記憶用メモリ及び作業領域用メモリとの両方が同一のＤＲＡＭ２０内に形成されている必要はない。データ転送用キャッシュ領域は第１のＤＲＡＭ内に形成され、管理情報記憶用メモリ及び作業領域用メモリは第１のＤＲＡＭと異なる第２のＤＲＡＭ内に形成されていてもよい。また両者が互いに異なる種類の揮発性メモリ内に形成されていてもよい。例えば、データ転送用キャッシュはコントローラ外部のＤＲＡＭ内に形成され、管理情報記憶用メモリ及び作業領域用メモリはコントローラ内部のＳＲＡＭ内に形成されていてもよい。また更に、ＤＲＡＭ２０は、ホスト１とＮＡＮＤフラッシュ１０間でのデータ転送用キャッシュとして機能するリードキャッシュ（以下、ＲＣという）を有していてもよい。また本実施形態ではライトキャッシュ、リードキャッシュとして説明するが、キャッシュアルゴリズムを用いずに一時的に書き込みデータまたは読み出しデータを保持する単純なデータバッファを採用してもよい。
【００２１】
コントローラ３０は、ＮＡＮＤフラッシュ１０に記憶されたシステムプログラム（ファームウエア）を実行するプロセッサと、各種ハードウェア回路などによってその機能が実現され、ホスト１からのライト要求、キャッシュフラッシュ要求、リード要求等の各種コマンドに対するホスト１−ＮＡＮＤフラッシュ１０間のデータ転送制御、ＤＲＡＭ２０及びＮＡＮＤフラッシュ１０に記憶された各種管理テーブルの更新・管理などを実行する。コントローラ３０は、コマンド解釈部３１、書き込み制御部３２、読み出し制御部３３及びＮＡＮＤ整理部３４を有する。各構成要素の機能は後述する。コントローラ３０のハードウェア回路として、例えば、ブートローダを格納するＲＯＭ（Read Only Memory）、ファームウエア展開用のＲＡＭ（Random Access Memory）、誤り検出及び訂正回路等が挙げられる。
【００２２】
ホスト１はＳＳＤ１００に対し、リード要求またはライト要求を発行する際には、ホストＩ／Ｆ２を介して論理アドレスとしてのＬＢＡ（Logical Block Addressing）を入力する。ＬＢＡは、図２に示すように、セクタ（サイズ：例えば５１２Ｂ）に対して０からの通し番号をつけた論理アドレスである。本実施形態においては、ＷＣ２１、ＮＡＮＤフラッシュ１０の管理単位として、ＬＢＡの下位（ｓ＋１）ビット目から上位のビット列で構成されるクラスタアドレスと、ＬＢＡの下位（ｓ＋ｔ＋１）ビットから上位のビット列で構成されるトラックアドレスとを定義する。また、以下の説明では、１ブロックは４個のトラックデータから構成され、１トラックは８個のクラスタデータから構成され、１ブロックは３２個のクラスタデータから構成されるとするが、これらの関係は任意である。
【００２３】
図３は、ＮＡＮＤフラッシュ１０内に形成されたデータ領域の機能ブロックを示すものである。ホスト１とＮＡＮＤフラッシュ１０との間には、ＤＲＡＭ２０上に構成されたライトキャッシュ（ＷＣ）２１が介在している。なお、ＤＲＡＭ２０上にリードキャッシュを形成することにしてもよい。ＷＣ２１はホスト１から入力されたデータを一時保存する。
【００２４】
ＮＡＮＤフラッシュ１０内のブロックは、コントローラ３０によって、クラスタ用入力バッファ領域（クラスタＩＢ）４１、トラック用入力バッファ領域（トラックＩＢ）４２、データストレージ（ＤＳ）４０という管理領域に割り当てられている。クラスタＩＢ４１を構成する１つのブロックには、３２個のクラスタデータが格納可能であり、トラックＩＢ４２を構成する１つのブロックには、４個のトラックデータが格納可能である。クラスタＩＢ４１及びトラックＩＢ４２はそれぞれ複数個のブロックで構成されていてもよい。
【００２５】
ＷＣ２１からＮＡＮＤフラッシュ１０へデータを追い出す際、「小さな単位」であるクラスタ単位で追い出す場合には、クラスタＩＢ４１にデータを追い出し、「大きな単位」であるトラック単位で追い出す場合には、トラックＩＢ４２にデータを追い出す。クラスタ単位で追い出すかトラック単位で追い出すかの管理単位の切り替え規則については後述する。クラスタデータで満杯になったクラスタＩＢ４１あるいはトラックデータで満杯になったトラックＩＢ４２は、その後ＤＳ４０のブロックとして管理されることで、ＤＳ４０に移動される。
【００２６】
・ライトキャッシュ（ＷＣ）２１
ＷＣ２１は、ホスト１からのライト要求に対して、ホスト１から入力されたデータを一時的に保存するための領域である。ＷＣ２１上のデータは、セクタ単位で管理される。ＷＣ２１のリソースが不足した場合、ＷＣ２１の記憶データをＮＡＮＤフラッシュ１０に追い出す。この追い出しの際、所定の追い出し規則に従ってＷＣ２１上に存在するデータをクラスタＩＢ４１及びトラックＩＢ４２の何れか一方に追い出す。
【００２７】
追い出し規則としては、例えばＬＲＵ（Least  Recently  Used）等の基準に基づいて、古いデータが先に選択されるようにＷＣ２１からの追い出し対象のセクタデータを選択すればよい。管理単位の切り替え規則としては、例えば、ＷＣ２１上に存在する追い出し対象のセクタデータを含むトラック中の更新データ量（有効データ量）が閾値以上の場合には、トラックデータとしてトラックＩＢ４２に追い出し、ＷＣ２１上に存在する追い出し対象のセクタデータを含むトラック中の更新データ量が閾値未満の場合には、クラスタデータとしてクラスタＩＢ４１に追い出すといった規則を採用する。
【００２８】
ＷＣ２１からクラスタデータとしてデータを追い出す際にＷＣ２１上に全てのデータが揃っていない場合は、ＮＡＮＤフラッシュ１０内に同一クラスタに含まれる有効なセクタデータがあるか否かを判定し、有効なセクタデータが存在する場合は、ＤＲＡＭ２０上で、ＷＣ２１にあるクラスタデータにＮＡＮＤフラッシュ１０内のセクタデータを穴埋めし、穴埋めされたクラスタデータをクラスタＩＢ４１に追い出す。
【００２９】
ＷＣ２１からトラックデータとしてデータを追い出す際にＷＣ２１上に全てのデータが揃っていない場合は、ＮＡＮＤフラッシュ１０内に同一トラックに含まれる有効なクラスタデータまたは有効なセクタデータがあるか否かを判定し、有効なクラスタデータまたはセクタデータが存在する場合は、ＤＲＡＭ２０上で、ＷＣ２１にあるトラックデータにＮＡＮＤフラッシュ１０内のクラスタデータまたはセクタデータを穴埋めし、穴埋めされたトラックデータをトラックＩＢ４２に追い出す。
【００３０】
・データストレージ領域（ＤＳ）４０
ＤＳ４０はトラック単位及びクラスタ単位でデータの管理が行われ、ユーザデータが格納される。ＤＳ４０に入力されたトラックと同一ＬＢＡのトラックについてはＤＳ４０のブロック内で無効化され、ブロック内の全トラックが無効になったブロックはフリーブロックＦＢとして解放される。ＤＳ４０に入力されたクラスタと同一ＬＢＡのクラスタについては、ＤＳ４０のブロック内で無効化され、ブロック内の全クラスタが無効になったブロックはフリーブロックＦＢとして解放される。ＤＳ４０内のブロックは、データの書き込み順序（ＬＲＵ）、換言すればクラスタＩＢ４１またはトラックＩＢ４２からＤＳ４０に移動された順序でブロックの新旧が管理されている。また、ＤＳ４０は、ブロック内の有効データ数（例えば有効クラスタ数）の大小の順序でもブロックが管理されている。
【００３１】
ＤＳ４０では、データの整理が行われる。データ整理のための条件が満たされた場合、コンパクションまたはデフラグなどを含むデータの整理が行われる。コンパクションとは、管理単位の変換を含まないデータの整理のことをいい、有効クラスタを集めてクラスタのまま１つのブロックに書き戻すクラスタコンパクション、有効トラックを集めてトラックのまま１つのブロックに書き戻すトラックコンパクションを含む。デフラグは、クラスタからトラックへの管理単位の変換を含むデータの整理のことをいい、有効クラスタを集めて、集めた有効クラスタをＬＢＡ順に並べてトラックに統合して１つのブロックに書き戻す。クラスタマージは、所謂トラックの解体であり、トラックからクラスタへの管理単位の変換を含むデータの整理のことをいい、トラック内の有効クラスタを集めて１つのブロックに書き戻す。データ整理については、後で詳述する。
【００３２】
図４は、コントローラ３０がＷＣ２１、ＤＳ４０を管理するための管理テーブルを示すものであり、最新の管理情報を含む管理テーブルが、ＤＲＡＭ２０、ＮＡＮＤフラッシュ１０のどちらに存在するかも示している。ＤＲＡＭ２０上には、ＷＣ管理テーブル２２、トラック管理テーブル２３、揮発性クラスタ管理テーブル２４、トラックエントリ管理テーブル２５、ブロック内有効クラスタ数管理テーブル２６、ブロックＬＲＵ管理テーブル２７、ブロック管理テーブル２８などを有する。ＮＡＮＤフラッシュ１０上には、正引きのクラスタ管理テーブル１２、逆引きのクラスタ管理テーブル１３を有する。
【００３３】
・ＷＣ管理テーブル２２
図５に、ＷＣ管理テーブル２２の一例を示す。ＷＣ管理テーブル２２は、ＤＲＡＭ２０上に記憶され、ＷＣ２１上に記憶されたデータをＬＢＡのセクタアドレス単位に管理する。ＷＣ管理テーブル２２の各エントリには、ＷＣ２１上に記憶されたデータに対応するＬＢＡのセクタアドレス、ＤＲＡＭ２０での記憶位置を示す物理アドレス、及び当該セクタが有効か無効かを示すセクタフラグが関連付けられている。有効データとは最新データのことであり、無効データとは、同一論理アドレスのデータが他の場所に書きこまれ、参照されることがなくなったデータのことである。なお、ＷＣ２１からＮＡＮＤフラッシュ１０への追い出しの際に、ＬＲＵを基準に追い出し順序を決定する場合は、セクタアドレス毎にセクタ間の更新時刻の新旧の順序を示すＬＲＵ情報を登録するようにしてもよい。また、ＷＣ管理テーブル２２をクラスタ単位、あるいはトラック単位に管理してもよい。クラスタ単位あるいはトラック単位に管理する場合においても、クラスタ間、あるいはトラック間の、ＷＣ２１でのＬＲＵ情報（例えば、ＷＣ２１でのデータ更新時刻順序）を管理するようにしてもよい。
【００３４】
・トラック管理テーブル２３
図６に、トラック管理テーブル２３の一例を示す。トラック管理テーブル２３は、ＤＲＡＭ２０上に記憶され、ＬＢＡのトラックアドレスからトラック情報を取得するためのテーブルである。トラック情報としては、トラックデータが記憶されているＮＡＮＤフラッシュ１０上の記憶位置（トラックデータが記憶されているブロック番号とブロック内記憶位置）、及び当該トラックが有効か無効かを示すトラック有効／無効フラグと、当該トラックに断片化されたクラスタデータが存在するか否かを示す断片化フラグを含み、これらが関連付けられている。
【００３５】
断片化されたクラスタデータとは、例えばトラックデータが格納されているブロックと異なるブロックに存在する、当該トラックに含まれる最新のクラスタデータのことである。別言すれば、断片化されたクラスタデータとは、ＮＡＮＤフラッシュ１０におけるトラック内の更新クラスタデータを示している。断片化フラグが、断片化クラスタが存在しないと示しているときは、トラック管理テーブル２３のみでアドレスを解決でき（勿論、正引きクラスタ管理テーブル１２には、ＳＳＤ内全データ分のクラスタ管理単位の管理情報を持っているので、正引きクラスタ管理テーブル１２を使用してもアドレス解決可能である）、断片化フラグが、断片化クラスタが存在すると示しているときは、トラック管理テーブル２３のみでアドレスを解決できず、揮発性クラスタ管理テーブル２４や正引きクラスタ管理テーブル１２をさらに検索することが必要であることを示している。
【００３６】
なお、トラック管理テーブル２３において、図６に示すように、断片化情報として断片化数（断片化されたクラスタ数）を管理するようにしてもよい。さらに、トラック管理テーブル２３において、トラック毎の読み出しデータ量、トラック毎の書き込みデータ量を管理することにしてもよい。トラックの読み出しデータ量とは、トラックに含まれるデータ（セクタ、クラスタ、トラック）の延べの読み出しデータ量のことをいい、リードアクセスが多いトラックであるか否かを判定するために使用する。なお、トラックの読み出しデータ量に代えてトラックの読み出し回数（トラックに含まれるデータ（セクタ、クラスタ、トラック）の延べの読み出し回数）を使用しても良い。
【００３７】
トラックの書き込みデータ量とは、トラックに含まれるデータ（セクタ、クラスタ、トラック）の延べの書き込みデータ量のことをいい、ライトアクセスが多いトラックであるか否かを判定するために使用する。トラックの書き込みデータ量に代えてトラックの書き込み回数（トラックに含まれるデータ（セクタ、クラスタ、トラック）の延べの書き込み回数）を使用しても良い。
【００３８】
・正引きクラスタ管理テーブル１２
図７に、正引きクラスタ管理テーブル１２の一例を示す。正引きクラスタ管理テーブル１２は、ＮＡＮＤフラッシュ１０上に記憶される。正引きテーブルとは、論理アドレス（ＬＢＡ）からＮＡＮＤフラッシュ１０上の記憶位置を検索するためのテーブルである。これに対し、逆引きテーブルとは、ＮＡＮＤフラッシュ１０上の記憶位置から論理アドレス（ＬＢＡ）を検索するためのテーブルである。
【００３９】
正引きクラスタ管理テーブル１２は、ＬＢＡのクラスタアドレスからクラスタ情報を取得するためのテーブルである。正引きクラスタ管理テーブル１２には、ＮＡＮＤフラッシュ１０のＤＳ４０の全容量分のクラスタ単位の管理情報を持っている。クラスタアドレスは、トラック単位にまとめられている。本実施形態では、１トラックに８クラスタを含むとしているので、１トラックに８個のクラスタ情報のエントリを含む。クラスタ情報としては、クラスタデータが記憶されているＮＡＮＤフラッシュ１０上の記憶位置（クラスタデータが記憶されているブロック番号とブロック内記憶位置）、及び当該クラスタが有効か無効かを示すクラスタ有効／無効フラグを含み、これらが関連付けられている。
【００４０】
正引きクラスタ管理テーブル１２は、トラック単位の管理情報が同一ブロックにまとめて記憶されてあれば、トラック単位の管理情報が複数のブロックに分散して記憶されていてもよい。この場合、トラック単位の管理情報のＮＡＮＤフラッシュ１０上での記憶位置は、後述するトラックエントリ管理テーブル２５によって管理される。また、この正引きクラスタ管理テーブル１２は、リード処理などに使用される。
【００４１】
・揮発性クラスタ管理テーブル２４
図８に、揮発性クラスタ管理テーブル２４の一例を示す。揮発性クラスタ管理テーブル２４は、ＮＡＮＤフラッシュ１０上に記憶されている正引きクラスタ管理テーブル１２の一部がＤＲＡＭ２０上にキャッシュされたものである。したがって、揮発性クラスタ管理テーブル２４も正引きクラスタ管理テーブル１２と同様、トラック単位にまとめられており、各クラスタアドレスのエントリ毎に、クラスタデータが記憶されているＮＡＮＤフラッシュ１０上の記憶位置（クラスタデータが記憶されているブロック番号とブロック内記憶位置）、及び当該クラスタが有効か無効かを示すクラスタ有効／無効フラグを含む。
【００４２】
ＤＲＡＭ２０上での、揮発性クラスタ管理テーブル２４のリソース使用量は増減する。ＳＳＤ１００が起動された直後の時点では、ＤＲＡＭ２０上での揮発性クラスタ管理テーブル２４のリソース使用量は零である。ＮＡＮＤフラッシュ１０からクラスタデータを読み出す際に、読み出すべきクラスタを含むトラックに対応するトラック単位の正引きクラスタ管理テーブル１２がＤＲＡＭ２０上にキャッシュされる。また、ＮＡＮＤフラッシュ１０にクラスタデータを書き込む際に、書き込むべきクラスタに対応する揮発性クラスタ管理テーブル２４がＤＲＡＭ上にキャッシュされていないときには、書き込むべきクラスタを含むトラックに対応するトラック単位の正引きクラスタ管理テーブル１２をＤＲＡＭ２０上にキャッシュして、書き込み内容に応じてキャッシュしたＤＲＡＭ２０上の揮発性クラスタ管理テーブル２４を更新し、さらに更新した揮発性クラスタ管理テーブル２４をＮＡＮＤフラッシュ１０に書き込んで、テーブルの不揮発化を実行する。このように、ＮＡＮＤフラッシュ１０に対する読み出しや書き込みに伴って、ＤＲＡＭ２０上での揮発性クラスタ管理テーブル２４のリソース使用量は許容値までの範囲内で変化する。
【００４３】
コントローラ３０は、揮発性クラスタ管理テーブル２４→正引きクラスタ管理テーブル１２→トラック管理テーブル２３の優先順位で管理テーブルを更新管理しており、この順番がアドレス解決のための情報の信頼性の優先順位であるともいえる。
【００４４】
・逆引きクラスタ管理テーブル１３
図９に、逆引きクラスタ管理テーブル１３の一例を示す。逆引きクラスタ管理テーブル１３は、ＮＡＮＤフラッシュ１０上に記憶される。逆引きクラスタ管理テーブル１３は、ＮＡＮＤフラッシュ１０上の記憶位置からＬＢＡのクラスタアドレスを検索するためのテーブルであり、例えばブロック番号単位にまとめられている。すなわち、ブロック番号とブロック内記憶位置（例えばページ番号）から特定されるＮＡＮＤフラッシュ１０上の記憶位置に、ＬＢＡのクラスタアドレスが関連付けられている。この逆引きクラスタ管理テーブル１３は、ＮＡＮＤフラッシュ１０の整理などに使用される。なお、逆引きクラスタ管理テーブル１３の一部をＤＲＡＭ２０上にキャッシュするようにしてもよい。逆引きクラスタ管理テーブル１３も、正引きクラスタ管理テーブル１２と同様、ＮＡＮＤフラッシュ１０のＤＳ４０の全容量分のクラスタ単位の管理情報を持っている。
【００４５】
・トラックエントリ管理テーブル２５
図１０に、トラックエントリ管理テーブル２５の一例を示す。トラックエントリ管理テーブル２５は、ＤＲＡＭ２０上に記憶される。トラックエントリ管理テーブル２５は、正引きクラスタ管理テーブル１２のトラックアドレス単位にまとめられた各トラックエントリ（この実施形態では１つのトラックエントリは８個のクラスタエントリから成る）のＮＡＮＤフラッシュ１０上での記憶位置を特定するためのテーブルである。トラックエントリ管理テーブル２５は、例えば、トラックアドレス毎に、トラックエントリのＮＡＮＤフラッシュ１０上での記憶位置を特定するためのポインタ情報が関連付けられている。なお、複数のトラックエントリをまとめて１つのポインタ情報で特定することとしてもよい。また、ポインタ情報を、クラスタアドレス単位に持つようにしてもよい。
【００４６】
・ブロック内有効クラスタ数管理テーブル２６
図１１に、ブロック内有効クラスタ数管理テーブル２６の一例を示す。ブロック内有効クラスタ数管理テーブル２６はＤＲＡＭ２０上に記憶される。ブロック内有効クラスタ数管理テーブル２６は、ブロック内の有効クラスタ数をブロック毎に管理するテーブルであり、図１１では、１つのブロックに関する有効クラスタ数を含む情報同士を双方向リストとして有効クラスタ数の小さいブロック順に管理している。リストの１つのエントリには、前エントリへのポインタ情報、有効クラスタ数（あるいは有効クラスタ率）、ブロック番号、次エントリへのポインタ情報が含まれる。ブロック内有効クラスタ数管理テーブル２６の主な用途は、ＮＡＮＤフラッシュ１０の整理であり、コントローラ３０は、有効クラスタ数によって整理対象ブロックを選択する。
【００４７】
・ブロックＬＲＵ管理テーブル２７
図１２に、ブロックＬＲＵ管理テーブル２７の一例を示す。ブロックＬＲＵ管理テーブル２７はＤＲＡＭ２０上に記憶される。ブロックＬＲＵ管理テーブル２７は、ブロックにおける書き込みを実行した時点の新旧の順序（ＬＲＵ：Least Recently used）をブロック毎に管理するテーブルであり、図１２では、１つのブロックのブロック番号を含む情報同士を双方向リストとしてＬＲＵ順に管理している。ブロックＬＲＵ管理テーブル２７で管理する書き込み時点とは、例えばフリーブロックＦＢからアクティブブロックＡＢになった時点とする。リストの１つのエントリには、前エントリへのポインタ情報、ブロック番号、次エントリへのポインタ情報が含まれる。ブロックＬＲＵ管理テーブル２７の主な用途は、ＮＡＮＤフラッシュ１０の整理であり、コントローラ３０は、ブロックの新旧の順序によって整理対象ブロックを選択する。
【００４８】
・ブロック管理テーブル２８
図１３に、ブロック管理テーブル２８の一例を示す。ブロック管理テーブル２８は、各ブロックが使用中であるか否か、すなわち各ブロックがフリーブロックＦＢであるかアクティブブロックＡＢであるかを識別管理する。フリーブロックＦＢとは、内部に有効データを含まない、用途未割り当ての未使用ブロックのことである。アクティブブロックＡＢとは、内部に有効データを含み、用途が割り当てられた使用中ブロックのことである。このブロック管理テーブル２８を使用して、ＮＡＮＤフラッシュ１０に対する書き込みの際に使用するフリーブロックＦＢを選択する。なお、未使用ブロックは、今まで一度も書き込みが行われなかったブロック及び一旦書き込みが行われたがその後全てのデータが無効データとなったブロックの両方を含む。上述した通り同一ページへの上書きを行うためには事前の消去動作が必要なので、フリーブロックＦＢはアクティブブロックＡＢとして利用される前の所定のタイミングで消去される。
【００４９】
なお、ブロック管理テーブル２８において、読み出しアクセスが多いブロックを識別するためにブロック毎の読み出し回数を管理するようにしてもよい。ブロックの読み出し回数とは、ブロック内のデータに読み出し要求が発生した延べの回数のことをいい、読み出しアクセスが多いブロックを判定するために使用する。なお、読み出し回数に代えてブロック内の読み出しデータ量（ブロック内から読み出された延べのデータ量）を使用しても良い。
【００５０】
ＳＳＤ１００では、論理アドレス（ＬＢＡ）と物理アドレス（ＮＡＮＤフラッシュ１０の記憶位置）との関係は予め静的に決定されておらず、データの書込み時に動的に関係付けられる論物変換方式が採用されている。例えば、同じＬＢＡのデータを上書きする場合は、つぎのような操作が行われる。論理アドレスＡ１にブロックサイズの有効なデータが保存されており、記憶領域としてはブロックＢ１が使用されていたとする。ホスト１から論理アドレスＡ１のブロックサイズの更新データを上書きするコマンドを受信した場合、フリーブロックＦＢ（ブロックＢ２とする）を１個確保し、そのフリーブロックＦＢにホスト１から受信したデータを書き込む。その後、論理アドレスＡ１とブロックＢ２を関係付ける。その結果、ブロックＢ２はアクティブブロックＡＢになり、ブロックＢ１に保存されたデータは無効になるためブロックＢ１はフリーブロックＦＢとなる。
【００５１】
このように、ＳＳＤ１００では、同じ論理アドレスＡ１のデータであっても、実際の記録領域として使用されるブロックは書込みの度に変化する。なお、ブロックサイズの更新データ書き込みでは、必ず書き込み先ブロックが変化するが、ブロックサイズ未満の更新データ書き込みでは、同じブロックに更新データが書き込まれることもある。例えばブロックサイズ未満のクラスタデータが更新される場合、当該ブロック内において同じ論理アドレスの旧クラスタデータが無効化され、新たに書き込まれた最新のクラスタデータが有効クラスタとして管理される。ブロック内の全データが無効化されると、当該ブロックはフリーブロックＦＢとして解放される。
【００５２】
上記各管理テーブルで管理される管理情報によって、コントローラ３０は、ホスト１で使用される論理アドレス（ＬＢＡ）と、ＳＳＤ１００で使用される物理アドレスとの間を対応付けることができ、ホスト１とＮＡＮＤフラッシュ１０との間のデータの転送を行うことが可能となる。
【００５３】
図１に示すように、コントローラ３０は、コマンド解釈部３１、書き込み制御部３２、読み出し制御部３３及びＮＡＮＤ整理部３４を有する。コマンド解釈部３１は、ホスト１からのコマンドを解析し、解析結果を書き込み制御部３２、読み出し制御部３３及びＮＡＮＤ整理部３４に通知する。
【００５４】
書き込み制御部３２は、ホスト１から入力されたデータをＷＣ２１に書き込むＷＣ書き込み制御、ＷＣ２１からＮＡＮＤフラッシュ１０にデータを追い出す追い出し制御、ＷＣ書き込み制御及び追い出し制御に対応する各種管理テーブルの更新など書き込みに関する制御を実行する。
【００５５】
読み出し制御部３３は、ホスト１から指定された読み出しデータをＮＡＮＤフラッシュ１０から読み出して、ＤＲＡＭ２０を経由してホスト１へ転送する読み出し制御、読み出し制御に対応する各種管理テーブルの更新など読み出しに関する制御を実行する。
【００５６】
ＮＡＮＤ整理部３４は、ＮＡＮＤフラッシュ１０での整理（コンパクション、デフラグ、クラスタマージなど）を実行する。ＮＡＮＤ整理部３４は、ＮＡＮＤフラッシュ１０の使用リソース量が閾値を越えたときに、ＮＡＮＤ整理を実行する。なお、ＤＲＡＭ２０上の管理テーブルのリソース使用量（例えば、揮発性クラスタ管理テーブル２４のリソース使用量）をＮＡＮＤ整理のトリガとして採用しても良い。リソース量とは、ＮＡＮＤフラッシュ１０上のデータを記録するフリーブロック数、ＤＲＡＭ２０上のＷＣ２１用の領域の量、ＤＲＡＭ２０上の揮発性クラスタ管理テーブル２４の未使用領域の量などを指しているが、これ以外をリソースとして管理してもよい。
【００５７】
・読み出し処理
つぎに、読み出し処理の概要について説明する。読み出し処理の際には、ＷＣ管理テーブル２２、揮発性クラスタ管理テーブル２４、トラック管理テーブル２３、正引きクラスタ管理テーブル１２をアドレス解決のために主に使用する。アドレス解決のための情報の信頼性の優先順位は、以下の通りである。
（１）ＷＣ管理テーブル２２
（２）揮発性クラスタ管理テーブル２４
（３）正引きクラスタ管理テーブル１２
（４）トラック管理テーブル２３
【００５８】
しかし、検索の高速性を考慮して、本実施形態では以下の順番にテーブル検索を行っている。
（１）ＷＣ管理テーブル２２
（２）トラック管理テーブル２３
（３）揮発性クラスタ管理テーブル２４
（４）正引きクラスタ管理テーブル１２
なお、揮発性クラスタ管理テーブル２４の検索を２番目にし、トラック管理テーブル２３の検索を３番目にしてもよい。また、トラック管理テーブル２３に、ＷＣ２１にデータが存在するか否かのフラグを設けるようにすれば、最初にトラック管理テーブル２３を検索するようにもテーブルの検索順番を変更することも可能である。このように、管理テーブルの検索順番は、管理テーブルの作り方次第で任意に設定可能である。
【００５９】
図１４を用いて正引きのアドレス解決手順について説明する。ホスト１から、ホストＩ／Ｆ２を介して読み出しコマンド及び読み出しアドレスとしてのＬＢＡが入力されると、読み出し制御部３３は、ＷＣ管理テーブル２２を検索することで、ＷＣ２１にＬＢＡに対応するデータが存在しているか否かを検索する（ステップＳ１００）。ＷＣ管理テーブル２２上でＬＢＡがヒットした場合は、ＷＣ管理テーブル２２からＬＢＡに対応するデータのＷＣ２１上の記憶位置を取得し（ステップＳ１１０）、取得した記憶位置を用いて当該ＬＢＡに対応するＷＣ２１のデータを読み出す。
【００６０】
読み出し制御部３３は、ＷＣ２１でヒットしなかった場合は、検索対象のデータがＮＡＮＤフラッシュ１０のどこに格納されているかを検索する。まず、トラック管理テーブル２３を検索し、トラック管理テーブル２３に当該ＬＢＡに対応する有効なトラックエントリが存在するか否かを判定する（ステップＳ１３０）。有効なトラックエントリが存在しない場合は、手順をステップＳ１６０に移行させる。有効なトラックエントリが存在する場合は、当該トラックエントリ中の断片化フラグを検索し、当該トラック中に断片化クラスタが存在するか否かを判定する（ステップＳ１４０）。断片化クラスタが存在しない場合は、当該トラックエントリからトラックデータのＮＡＮＤフラッシュ１０上の記憶位置を取得し（ステップＳ１５０）、取得した記憶位置を用いて当該ＬＢＡに対応するＮＡＮＤフラッシュ１０上のデータを読み出す。
【００６１】
ステップＳ１３０でトラック管理テーブル２３に有効なトラックエントリが存在しない場合、あるいはステップＳ１４０で断片化クラスタが存在する場合は、読み出し制御部３３は、つぎに、揮発性クラスタ管理テーブル２４を検索し、揮発性クラスタ管理テーブル２４に当該ＬＢＡに対応する有効なトラックエントリが存在するか否かを判定する（ステップＳ１６０）。揮発性クラスタ管理テーブル２４に当該ＬＢＡに対応する有効なクラスタエントリが存在する場合は、該当クラスタエントリからクラスタデータのＮＡＮＤフラッシュ１０上の記憶位置を取得し（ステップＳ１９０）、取得した記憶位置を用いて当該ＬＢＡに対応するＮＡＮＤフラッシュ１０上のデータを読み出す。
【００６２】
ステップＳ１６０で、当該ＬＢＡに対応するクラスタエントリが揮発性クラスタ管理テーブル２４に存在しない場合は、読み出し制御部３３は、つぎに、正引きクラスタ管理テーブル１２を検索するために、トラックエントリ管理テーブル２５を検索する。すなわち、当該ＬＢＡのクラスタアドレスに対応するトラックエントリ管理テーブル２５のエントリから、クラスタ管理テーブルのＮＡＮＤフラッシュ１０上の記憶位置を取得し、取得したＮＡＮＤフラッシュ１０上の記憶位置を用いて正引きクラスタ管理テーブル１２の当該トラックエントリをＮＡＮＤフラッシュ１０から読み出し、読み出したトラックエントリを揮発性クラスタ管理テーブル２４としてＤＲＡＭ２０上にキャッシュする。そして、キャッシュした正引きクラスタ管理テーブル１２を用いて、当該ＬＢＡに対応するクラスタエントリを抽出し（ステップＳ１８０）、抽出したクラスタエントリからクラスタデータのＮＡＮＤフラッシュ１０上の記憶位置を取得し（ステップＳ１９０）、取得した記憶位置を用いて当該ＬＢＡに対応するＮＡＮＤフラッシュ１０上のデータを読み出す。
【００６３】
このようにして、ＷＣ管理テーブル２２、トラック管理テーブル２３、揮発性クラスタ管理テーブル２４、正引きクラスタ管理テーブル１２の検索によってＷＣ２１またはＮＡＮＤフラッシュ１０から読み出されたデータを、必要に応じてＤＲＡＭ２０上で結合してホスト１へ送る。
【００６４】
図１５は、上記したＮＡＮＤフラッシュ１０内データのアドレス解決を概念的に示す図である。トラック管理テーブル２３で管理しているトラックデータと、正引きクラスタ管理テーブル１２で管理しているクラスタデータは包括関係にある。図１５は、あるＬＢＡのクラスタの記録場所をトラック管理テーブル２３及び正引きクラスタ管理テーブル１２のどちらでも解決できる場合である。図１６は、あるＬＢＡのクラスタの記録場所を正引きクラスタ管理テーブル１２でのみ解決できる場合である。図１７は、揮発性クラスタ管理テーブル２４のみが最新の記録場所を解決できる場合であり、揮発性クラスタ管理テーブル２４の情報を正引きクラスタ管理テーブル１２に保存した段階で、正引きクラスタ管理テーブル１２でも最新の記録場所を解決できるようになる。
【００６５】
・書き込み処理
つぎに、図１８に示すフローチャートに従って書き込み処理の概要について説明する。書き込み処理では、ホストＩ／Ｆ２を介して書き込みアドレスとしてのＬＢＡを含む書き込みコマンドが入力されると（ステップＳ２００）、書き込み制御部３２は、ＬＢＡで指定されたデータをＷＣ２１に書き込む。具体的には、書き込み制御部３２は、ＷＣ２１に当該書き込み要求に応じた空き領域が有るか否かを判定し（ステップＳ２１０）、ＷＣ２１に空き領域がある場合は、ＬＢＡで指定されたデータをＷＣ２１に書き込む（ステップＳ２５０）。このＷＣ２１への書き込みに伴って書き込み制御部３２は、ＷＣ管理テーブル２２を更新する。
【００６６】
一方、ＷＣ２１に空き領域がない場合は、書き込み制御部３２は、ＷＣ２１からデータを追い出し、追い出したデータをＮＡＮＤフラッシュ１０に書き込み、ＷＣ２１に空き領域を作成する。具体的には、書き込み制御部３２は、ＷＣ管理テーブル２２に基づいてＷＣ２１上に存在するトラック中の更新データ量を判定し、更新データ量が閾値ＤＣ１以上の場合には（ステップＳ２２０）、トラックデータとしてトラックＩＢ４２にデータを追い出し（ステップＳ２３０）、ＷＣ２１上に存在するトラック中の更新データ量が閾値ＤＣ１未満の場合には、クラスタデータとしてクラスタＩＢ４１に追い出す（ステップＳ２４０）。ＷＣ２１上に存在するトラック中の更新データ量とは、ＷＣ２１上に存在する同一トラック中の有効データ量のことをいい、トラック内の有効データ量が閾値ＤＣ１以上のトラックはトラックサイズのデータとしてトラックＩＢ４２にデータを追い出し、トラック内の有効データ量が閾値ＤＣ１未満のトラックはクラスタサイズのデータとしてクラスタＩＢ４１にデータを追い出す。例えば、ＷＣ２１をセクタアドレスで管理する場合は、ＷＣ２１上に存在する同一トラック中の有効なセクタデータの合計量を閾値ＤＣ１と比較し、この比較結果に応じてトラックＩＢ４２またはクラスタＩＢ４１にデータを追い出す。また、ＷＣ２１をクラスタアドレスで管理する場合は、ＷＣ２１上に存在する同一トラック中の有効なクラスタデータの合計量を閾値ＤＣ１と比較し、この比較結果に応じてトラックＩＢ４２またはクラスタＩＢ４１にデータを追い出す。
【００６７】
ただし、ＷＣ２１からデータを追い出す際、ＷＣ管理テーブル２２のＬＲＵ情報に基づき古いデータが先に追い出されるような順序規則に従ったほうが望ましい。また、ＷＣ２１にキャッシュされたトラック中の有効データ量を計算する際には、ＷＣ管理テーブル２２中の有効なセクタアドレスを用いてトラック中の有効データ量を都度計算することとしてもよいし、トラック中の有効データ量をトラック毎に逐次計算してＤＲＡＭ２０に管理情報として記憶しておき、この記憶された管理情報に基づきトラック中の有効データ量を判定するようにしてもよい。また、ＷＣ管理テーブル２２をクラスタ単位に管理する場合も、ＷＣ管理テーブル２２を用いてトラック中の有効クラスタ数をその都度計算することにしてもよいし、トラック中の有効クラスタ数をトラック毎に管理情報として記憶しておくようにしてもよい。また、トラック中の有効データ量に代えてトラック中の有効データ率を使用し、有効データ率と閾値との比較結果に応じてデータの追い出し先を決定するようにしてもよい。
【００６８】
前述したように、ＷＣ２１からクラスタデータとしてデータを追い出す際に、ＷＣ２１上に全てのデータが揃っていない場合は、ＮＡＮＤフラッシュ１０内に同一クラスタに含まれる有効なセクタデータがあるか否かを判定し、有効なセクタデータが存在する場合は、ＤＲＡＭ２０上で、ＷＣ２１にあるクラスタデータにＮＡＮＤ１０内のセクタデータを穴埋めし、穴埋めされたクラスタデータをクラスタＩＢ４１に追い出す。また、ＷＣ２１からトラックデータとしてデータを追い出す際に、ＷＣ２１上に全てのデータが揃っていない場合は、ＮＡＮＤフラッシュ１０内に同一トラックに含まれる有効なクラスタデータ及び有効なセクタデータがあるか否かを判定し、有効なクラスタデータまたはセクタデータが存在する場合は、ＤＲＡＭ２０上で、ＷＣ２１にあるトラックデータにＮＡＮＤ１０内のクラスタデータまたはセクタデータを穴埋めし、穴埋めされたトラックデータをクラスタＩＢ４１に追い出す。
【００６９】
このようにして、ＷＣ２１に空き領域を作った後、書き込み制御部３２は、ＬＢＡで指定されたデータをＷＣ２１に書き込む（ステップＳ２５０）。また、ＷＣ２１へのデータ書き込みに応じて、またＮＡＮＤフラッシュ１０へのデータ追い出しに応じて、管理テーブルを更新する。具体的には、ＷＣ２１の更新状態に応じてＷＣ管理テーブル２２を更新する。
【００７０】
ＮＡＮＤフラッシュ１０へトラックデータとして追い出した場合は、トラック管理テーブル２３を更新するとともに、トラックエントリ管理テーブル２５を参照して対応するクラスタ管理テーブル１２の位置を特定して読み出し、揮発性クラスタ管理テーブル２４としてＤＲＡＭ２０上にキャッシュして更新する。さらに更新後のテーブルをＮＡＮＤフラッシュ１０上に書き込んだ後、この書き込み位置をポインティングするようにトラックエントリ管理テーブル２５を更新する。また、逆引きのクラスタ管理テーブル１３についても更新する。
【００７１】
一方、ＮＡＮＤフラッシュ１０へクラスタとして追い出した場合は、トラックエントリ管理テーブル２５を参照して対応するクラスタ管理テーブル１２の位置を特定して読み出し、揮発性クラスタ管理テーブル２４としてＤＲＡＭ２０上にキャッシュして更新する。さらに更新後のテーブルをＮＡＮＤフラッシュ１０上に書き込んだ後、この書き込み位置をポインティングするようにトラックエントリ管理テーブル２５を更新する。なお、揮発性クラスタ管理テーブル２４がすでにＤＲＡＭ２０上に存在する場合には、ＮＡＮＤフラッシュ１０上のクラスタ管理テーブル１２の読み出しは省略する。
【００７２】
・ＮＡＮＤフラッシュの整理
つぎに、ＮＡＮＤフラッシュの整理について説明する。本実施形態では、ホスト１からのアクセス頻度が高いときと、ホスト１からのアクセス頻度が低いときとでＮＡＮＤフラッシュの整理の内容を異ならせる。アクセス頻度が高いとは、例えば、ホスト１からのデータ転送要求にかかるコマンドの受信間隔が閾値Ｔｃ以下の場合であるとし、アクセス頻度が低いときとはホスト１からのデータ転送要求にかかるコマンドの受信間隔が閾値Ｔｃより長い場合であるとする。なお、アクセス頻度をホスト１からのデータ転送レートに基づき判断することにしてもよい。
【００７３】
アクセス頻度が高いときのデータ整理は、
・ＮＡＮＤフラッシュ１０のリソース使用量が限界値を超えた場合に（例えば、フリーブロックＦＢの個数が限界値Ｆlmt以下になった場合に）発動され、
・有効データ量（例えば、有効クラスタ数）がより少ないブロックをデータ整理対象ブロックとして選択し、
・データ整理対象ブロックの有効データはすべてクラスタ単位で管理して整理（クラスタマージ、クラスタコンパクション）を実行する。
アクセス頻度が高いときのデータ整理として、トラック単位からクラスタ単位への管理単位の変換が行われるクラスタマージを採用している点が、本実施形態の１つの特徴である。なお、有効データ量がより少ないブロックをデータ整理対象ブロックとして選択するとは、有効データ量が最も少ないものから順番に選択するという意味である。なお、アクセス頻度が高いときのデータ整理の際、有効データ量が閾値より少ないブロックをデータ整理対象ブロックとして選択するようにしてもよい。
【００７４】
アクセス頻度が低いときのデータ整理は、
・ＮＡＮＤフラッシュ１０のリソース使用量が目標値を超えた場合に（フリーブロックＦＢの個数が目標値Ｆref（＞Ｆlmt）以下になった場合に）発動され、
・書き込み時期が古いブロックの中で、有効データ量（例えば、有効クラスタ数）がより少ないブロックをデータ整理対象ブロックとして選択し、
・データ整理対象ブロックの有効データはすべてトラック単位で管理して整理（デフラグ、トラックコンパクション）を実行する。
アクセス頻度が低いときのデータ整理として、クラスタからトラックへの管理単位の変換が行われるデフラグを採用している点が、本実施形態の１つの特徴である。なお、アクセス頻度が低いときのデータ整理の際、書き込み時期が古いブロックの中で、有効データ量が閾値より少ないブロックをデータ整理対象ブロックとして選択するようにしてもよい。
【００７５】
図１９は、アクセス頻度が高いときのデータ整理の一例の様子を概念的に示す図である。本実施形態では、１個のブロックには、４個のトラックデータあるいは３２個のクラスタデータを収容することが可能である。１トラック分の記憶容量には、８個のクラスタデータを収容可能である。白抜きの四角が無効データを示し、ハッチング付きの四角が有効データを示している。
【００７６】
アクセス頻度が高いときの整理では、有効クラスタ数が少ないブロックから有効クラスタまたはトラック内の有効クラスタがフリーブロックＦＢに集められる。ここでデータ集合先のフリーブロックＦＢはクラスタ単位で管理され、トラック単位では管理をされないようにする。アクセス頻度が高いときのデータ整理には、図１９に示すように、例えば、トラックの解体（クラスタマージ）と、クラスタコンパクションが含まれる。データ集合先のフリーブロックＦＢは、アクティブブロックＡＢとして、ブロックＬＲＵ管理テーブル２７でＬＲＵ順が管理されるリストの入口（最も書き込み時期が新しい方）に挿入する。データ整理により有効データが存在しなくなったブロックはフリーブロックＦＢとして解放される。
【００７７】
ただし、トラックの解体（クラスタマージ）の際、ブロックに記憶されているトラック内の有効クラスタ数が閾値以上ある場合は、トラックの解体を行わずにそのまま無効クラスタを含むトラックとしてデータ集合先のフリーブロックＦＢにデータをコピーし、その後もトラック管理するといった例外処理を行うことも可能である。すなわち、データ整理の際に、トラック管理テーブル２３から整理対象トラックの断片化数を取得し、取得した断片化数を閾値と比較し、断片化数が閾値より少ない場合は、トラックの解体を行わずにそのままデータ集合先のフリーブロックＦＢにデータをコピーし、コピーしたトラックはその後もトラック管理する。このようにして、トラックの解体によって断片化数の少ないトラックのクラスタが分散されることを抑制し、これによりリード性能の低下を防止する。
【００７８】
図２０は、アクセス頻度が低いときのデータ整理の一例の様子を概念的に示す図である。アクセス頻度が低いときの整理では、デフラグを行うことで、断片化した複数のクラスタデータをトラックデータとしてＬＢＡ順に並べ直すことで、ＮＡＮＤフラッシュ１０をクラスタ単位とトラック単位との２つの管理単位を組み合わせて制御を行う管理構造へ戻すようにする。なお、アクセス頻度が低いときには、デフラグのみを行うようにしてもよいが、図２０に示すように、デフラグ、トラックコンパクション、さらにはクラスタコンパクションを併用してもよい。データ整理により有効データが存在しなくなったブロックはフリーブロックＦＢとして解放される。
【００７９】
図２０では、まず、トラックコンパクションを行う。トラックコンパクションでは、ブロック内の有効クラスタをチェックし、有効クラスタが所属するトラックがトラックデータとして管理されていて、かつクラスタ化率が所定割合以下のトラックを１つのフリーブロックＦＢへ集める。クラスタ化率は、トラック管理テーブル２３の断片化数を用いて、断片化数／トラック内の全クラスタ数、に基づき算出する。勿論、クラスタ化率に代えて断片化数を用いることで、トラックコンパクション対象のトラックを選択してもよい。データ集合先のフリーブロックＦＢは、アクティブブロックＡＢとして、ブロックＬＲＵ管理テーブル２７でＬＲＵ順が管理されるリストにおいて、例えば、コンパクション対象データが存在したブロックよりも出口側（書き込み時期が古い方）へ挿入する。
【００８０】
つぎの、デフラグでは、トラックコンパクションに該当しない有効クラスタをトラックデータに統合して１つのフリーブロックＦＢに集める。データ集合先のフリーブロックＦＢは、アクティブブロックＡＢとして、ブロックＬＲＵ管理テーブル２７でＬＲＵ順が管理されるリストの入口（最も書き込み時期が新しい方）に挿入する。
【００８１】
書き換え頻度が高いデータは、ブロックＬＲＵ管理テーブル２７でＬＲＵ順が管理されるリストの入口側に集まると期待されるので、書き換え頻度が低いと思われる、リストの出口側のデータから優先的にトラック化する。この動作を続けると、書き換え頻度が少ないトラックデータがリストの出口側に集まってくることが期待される。
【００８２】
クラスタコンパクションは、例えば、ＮＡＮＤフラッシュ１０の整理によってフリーブロックＦＢの個数が閾値より少なくなった際に実行する。すなわち、デフラグを行うとフリーブロックＦＢが少なくなる可能性が高いので、クラスタコンパクションを行ってフリーブロックＦＢを増やす。クラスタコンパクションでは、例えば、上記トラックコンパクション、デフラグの対象とならなかった有効クラスタを１つのフリーブロックＦＢに集める。データ集合先のフリーブロックＦＢは、アクティブブロックＡＢとして、ブロックＬＲＵ管理テーブル２７でＬＲＵ順が管理されるリストの入口（最も書き込み時期が新しい方）に挿入する。なお、フリーブロック数は、ブロック管理テーブル２８に登録されたフリーブロックＦＢの個数を計数して求めてもよいし、フリーブロック数を管理情報として記憶しておくようにしてもよい。
【００８３】
なお、データ整理の際には、ＷＣ２１からの追い出しのときと同様、必要に応じてセクタ穴埋め及びクラスタ穴埋めを実行する。すなわち、クラスタマージ、クラスタコンパクションの際にはセクタ穴埋めを行い、デフラグ、トラックコンパクションの際には、セクタ穴埋め及びクラスタ穴埋めを実行する。ただし、ＷＣ２１上のデータを除いてデータ整理する際には、セクタ穴埋めは省略可能である。
【００８４】
つぎに、図２１に示すフローチャートにしたがってＮＡＮＤフラッシュの整理をより詳細に説明する。ＮＡＮＤ整理部３４は、ブロック管理テーブル２８に基づきフリーブロックＦＢの個数を管理している（ステップＳ３００）。フリーブロックＦＢの個数が限界値Ｆlmt以下になった場合、ホスト１からのデータ転送要求の間隔が閾値（例えば５秒）より短いか否かを調べることでアクセス頻度が高いか否かを判断し（ステップＳ３１０）、アクセス頻度が高いと判断した場合は、ブロック内有効クラスタ数管理テーブル２６を参照して有効クラスタ数がより少ないブロックを整理対象ブロックとして選択する（ステップＳ３２０）。
【００８５】
つぎに、ＮＡＮＤ整理部３４は、整理対象ブロックのブロック番号から逆引きクラスタ管理テーブル１３にアクセスして、該当ブロック中に記憶されているクラスタデータのアドレスを全て取得する。そして、取得したクラスタアドレスから揮発性クラスタ管理テーブル２４及びクラスタ管理テーブル１２にアクセスし、取得したクラスタが有効であるか否かを判定し、有効なクラスタのみを整理対象のクラスタデータとする。整理対象のクラスタデータが決定すると、クラスタアドレスからトラックアドレスを算出してトラック管理テーブル２３にアクセスし、整理対象のクラスタデータを含むトラック中のすべてのクラスタデータを正引きクラスタ管理テーブル１２で管理することとし、トラック管理テーブル２３の該当トラックの情報を無効化する。
【００８６】
上記処理を繰り返して整理対象のクラスタデータが１ブロック分集められた場合、集めたクラスタデータをフリーブロックＦＢへ書き込み、この書き込み内容に応じて正引きクラスタ管理テーブル１２及びトラックエントリ管理テーブル２５の該当クラスタのエントリを更新する。さらに、クラスタデータの集合先として使用されたフリーブロックＦＢをアクティブブロックＡＢに変更するようブロック管理テーブル２８を更新する。なお、集めたクラスタデータの整理前の記録位置をクラスタ管理テーブル１２、トラックエントリ管理テーブル２５にアクセスして取得し、取得した記録位置からクラスタデータを以前記憶していたブロックの番号を取得し、ブロックの番号からブロック内有効クラスタ数管理テーブル２６にアクセスしてブロック番号に対応するリストエントリ内の有効クラスタ数を更新する。最後に、クラスタデータを集合させたブロックの情報をブロック内有効クラスタ数管理テーブル２６、ブロックＬＲＵ管理テーブル２７、逆引きクラスタ管理テーブル１３に反映させる。このように、アクセス頻度が高いときは、整理対象として選択したブロックの有効データをクラスタ単位で管理してデータの整理を実行する（ステップＳ３３０）。
【００８７】
また、ステップＳ３１０の判断がＮＯである場合、ＮＡＮＤ整理部３４は、後述するステップＳ３６０、Ｓ３７０の処理を実行する。
【００８８】
一方、ステップＳ３００の判断がＮＯである場合、ＮＡＮＤ整理部３４は、フリーブロックＦＢの個数が目標値Ｆref以下になったか否かを判定し（ステップＳ３４０）、フリーブロックＦＢの個数が目標値Ｆref以下になっている場合、つぎにホスト１からのデータ転送要求の間隔が閾値（例えば５秒）より短いか否かを調べることでアクセス頻度が低いか否かを判断し（ステップＳ３５０）、アクセス頻度が低いと判断した場合は、ブロックＬＲＵ管理テーブル２７を参照して最も古くに書き込みを実行したブロックを整理対象候補ブロックとして選択する（ステップＳ３６０）。
【００８９】
そして、ＮＡＮＤ整理部３４は、選択した整理対象候補ブロックの番号を元にブロック内有効クラスタ数管理テーブル２６にアクセスして有効クラスタ数を取得し、取得した有効クラスタ数を閾値Ｄｎと比較し、有効クラスタ数が閾値Ｄｎ以下の場合は、この整理対象候補ブロックを整理対象ブロックとして決定する。有効クラスタ数が閾値Ｄｎより多い場合は、再度、ブロックＬＲＵ管理テーブル２７を参照して２番目に古くに書き込みを実行したブロックを整理対象候補ブロックとして選択し、選択した整理対象候補ブロックの有効クラスタ数を同様にして取得し、前述と同様の処理を実行する。このようにして、整理対象ブロックを決定できるまで、同様の処理を繰り返す。
【００９０】
このようにして整理対象のブロックを選択したら、ＮＡＮＤ整理部３４は、整理対象ブロックのブロック番号から逆引きクラスタ管理テーブル１３にアクセスして、整理対象ブロック中に記憶されているクラスタデータのアドレスを全て取得する。そして、取得したクラスタアドレスから揮発性クラスタ管理テーブル２４及び正引きクラスタ管理テーブル１２にアクセスし、取得したクラスタが有効であるか否かを判定し、有効なクラスタのみを整理対象のクラスタデータとする。
【００９１】
整理対象のクラスタデータが決定すると、クラスタアドレスからトラックアドレスを算出し、算出したトラックアドレスに対応するトラックデータを整理対象として決定する。整理対象ブロック中に記憶されている各クラスタデータに関し、前記同様の処理を実行して、整理対象トラックを１ブロック分（本実施形態では４個）揃える。そして、これら４個の整理対象トラックを構成する有効クラスタの記憶位置を揮発性クラスタ管理テーブル２４、正引きクラスタ管理テーブル１２及びトラック管理テーブル２３にアクセスして取得し、トラックを構成する有効クラスタを集めてトラックデータを１つずつ構成した後、各トラックデータをフリーブロックＦＢに書き込む。
【００９２】
この書き込み内容に応じてトラック管理テーブル２３、正引きクラスタ管理テーブル１２及びトラックエントリ管理テーブル２５の該当エントリを更新する。さらに、トラックデータの集合先として使用されたフリーブロックＦＢをアクティブブロックＡＢに変更するようブロック管理テーブル２８を更新する。なお、前述と同様、集めたトラックデータ及びクラスタデータの整理前の記録位置をトラック管理テーブル２３、正引きクラスタ管理テーブル１２、トラックエントリ管理テーブル２５にアクセスして取得し、取得した記録位置からトラックデータ及びクラスタデータを以前記憶していたブロックの番号を取得し、ブロックの番号からブロック内有効クラスタ数管理テーブル２６にアクセスしてブロック番号に対応するリストエントリ内の有効クラスタ数を更新する。最後に、トラックデータ及びクラスタデータを集合させたブロックの情報をブロック内有効クラスタ数管理テーブル２６、ブロックＬＲＵ管理テーブル２７、逆引きクラスタ管理テーブル１３に反映させる。
【００９３】
なお、ステップＳ３６０において、データ整理の対象ブロックを選択する際に、書き込み時期が閾値ｋ１より新しいブロックのなかで有効データ量が少ないブロックを選択し、かつ書き込み時期が閾値ｋ２よりも古いブロックの中で有効データ量が少ないブロックを選択することによって、書き込み時期が新しいデータ同士をまとめてトラック管理し、書き込み時期が古いデータ同士をまとめてトラック管理するようにしてもよい。この方法を採用すると、書き込み時期が異なるトラックが同一ブロックに集まることを防止することができるので、無駄な書き込みを防止することが可能になる。
【００９４】
なお、ＷＣ２１からＮＡＮＤフラッシュ１０へのデータ追い出し時、またはＮＡＮＤフラッシュ１０内でのデータ整理時に、どの管理テーブルを更新すれば良いかは、上述した管理テーブル群の構造や、どの時点でＤＲＡＭ２０上の管理テーブルをＮＡＮＤフラッシュ１０にバックアップするか等に依存するものであり、求める性能や処理の複雑さに応じて適宜設定すべきものである。例えば、ＮＡＮＤフラッシュ１０内でのデータ整理時に、揮発性クラスタ管理テーブル２４の更新のみに留める方法や、デフラグ時にトラックデータを生成した際に、トラック管理テーブル２３のみを更新する方法等が考えられる。
【００９５】
このように、アクセス頻度が低いときは、整理対象として選択したブロックの有効データをトラック単位で管理してデータの整理を実行する（ステップＳ３７０）。整理中にフリーブロックＦＢが足りなくなった場合には、アクセス頻度が高いと判断したときと同様の処理（ステップＳ３２０、Ｓ３３０）を行ってフリーブロックＦＢを生成する。なお、アクセス頻度が低いときの整理中に、所定の条件を満たす場合には、アクセス頻度が低いときの整理を終了してもよい。所定の条件としては、例えば、アクセス頻度、断片化クラスタの存在しないトラック数、及びフリーブロックＦＢ数等を基準とすれば良い。アクセス頻度が低いときの整理を途中で中断することで、必要以上にＮＡＮＤフラッシュの書き換えを行わないようにすることができる。
【００９６】
このように第１の実施形態では、ＮＡＮＤフラッシュ１０のＤＳ４０の管理単位として、大きな管理単位であるトラックと小さな管理単位であるクラスタの２つを持ち、クラスタを管理する正引きクラスタ管理テーブル１２をＮＡＮＤフラッシュ１０で更新管理し、トラックを管理するトラック管理テーブル２３をＤＲＡＭ２０で更新管理し、ホストからのアクセスパターンに応じて内部でのデータ配置及び管理情報を適応することとしたので、大容量の揮発性半導体メモリを採用することなく、ランダムライト性能と、ランダムリード性能との両者を向上させる管理方式を実現することが可能となる。また、ＮＡＮＤフラッシュ１０上の正引きクラスタ管理テーブル１２のキャッシュとして、ＤＲＡＭ２０上に揮発性クラスタ管理テーブル２４を持つようにしたので、管理情報へのアクセス性能がより向上する。
【００９７】
さらに、本実施形態では、ホスト１からのアクセス頻度が高いときは、小さな管理単位であるクラスタを使用してデータの整理を行うこととしたので、ランダムライト性能を向上させることができ、ホスト１からのアクセスが少なくなったときには、大きな管理単位であるトラックと小さな管理単位であるクラスタを使用して動作することとしたので、ランダムリード性能を向上させることが可能となる。
【００９８】
さらに、ホスト１からのアクセス頻度が高いときは、データ整理対象ブロックの有効データを全てクラスタ管理して整理を行うこととしたので、より高速にフリーブロックＦＢを増やすことができる。従ってＮＡＮＤフラッシュ１０のリソース使用量を高速に安定状態に戻すことが可能となり、ランダムライト性能を向上させることが可能となる。
【００９９】
また、ホストからのアクセス頻度が低いときに、断片化した小さな管理単位のクラスタデータを大きな管理単位のトラックデータとしてＬＢＡ順に並べ直すといった整理を行うことにしたので、アクセス頻度が低いときに大きな管理単位と小さな管理単位の２つを組み合わせて制御を行う管理構造へ戻すことができ、リード性能を向上させることが可能となる。
【０１００】
（第２の実施形態）
図２２は、ＳＳＤ１００の第２の実施形態の構成例を示す機能ブロック図である。第２の実施形態においては、第１の実施形態で採用されている揮発性クラスタ管理テーブル２４が存在せず、クラスタ管理をＮＡＮＤフラッシュ１０上のクラスタ管理テーブル１２のみで行うようにしている。これにより、ＤＲＡＭ２０の容量を更に削減することが可能となる。その他の構成要素、作用は第１の実施形態と同様である。
【０１０１】
（第３の実施形態）
第３の実施形態においては、アクセス頻度が低いときのＮＡＮＤフラッシュの整理の方法を第１の実施形態とは異ならせている。図２３は、第３の実施形態におけるＮＡＮＤフラッシュの整理手順を示すフローチャートである。図２２のフローチャートにおいては、アクセス頻度が低いときの動作手順であるステップＳ３６５、ステップＳ３７５を第１の実施形態（図２１）と異ならせている。
【０１０２】
第３の実施形態では、アクセス頻度が低いときには、有効データ量（例えば、有効クラスタ数）がより少ないブロックをデータ整理対象ブロックとして決定し（ステップＳ３６５）、決定したブロック中の有効データはすべてクラスタ管理して整理（クラスタマージ、クラスタコンパクション）を実行する（ステップＳ３７５）。これにより、第３の実施形態では、アクセス頻度が低いときであっても、ＮＡＮＤフラッシュ１０のリソース使用量を早急に安定状態に戻すことが可能となる。
【０１０３】
なお、この第３の実施形態では、ＳＳＤ１００がスタンバイ状態へ移行するときや、電源断シーケンスの際に、クラスタ単位からトラック単位への管理単位の変換を伴うＮＡＮＤフラッシュの整理を行うようにしてもよい。
【０１０４】
また、ステップＳ３６５において、データ整理の対象ブロックを選択する際に、書き込み時期が閾値ｋ３より新しいブロックのなかで有効データ量が少ないブロックを選択し、かつ書き込み時期が閾値ｋ４よりも古いブロックの中で有効データ量が少ないブロックを選択することによって、書き込み時期が新しいデータ同士をまとめてクラスタ管理し、書き込み時期が古いデータ同士をまとめてクラスタ管理するようにしてもよい。この方法を採用すると、書き込み時期が異なるクラスタが同一ブロックに集まることを防止することができるので、無駄な書き込みを防止することが可能になる。
【０１０５】
（第４の実施形態）
図２４は、第４の実施形態でのＷＣ２１からＮＡＮＤフラッシュ１０への追い出し構造を示すものである。第４の実施形態では、ＷＣ２１からＮＡＮＤフラッシュ１０への追い出しの際に、管理単位の選択を行うことなく、全てクラスタ単位でクラスタＩＢ４１へ追い出すようにする。そして、第４の実施形態では、図２１のステップＳ３６０、Ｓ３７０に示したように、アクセス頻度が低いときのＮＡＮＤフラッシュの整理によって、クラスタ単位からトラック単位への管理単位の変換を行うこととする。すなわち、アクセス頻度が低いときのＮＡＮＤ整理によって、初めてトラックデータが生成される。
【０１０６】
（第５の実施形態）
図２５は、第５の実施形態のＮＡＮＤフラッシュ１０の記憶領域を機能的に示すものである。第４の実施形態では、ＤＳ４０の前段に前段ストレージ（ＦＳ：Front  Storage）５０を配置している。ＦＳ５０は、ＤＳ４０と同様、クラスタ及びトラック単位でデータが管理されるバッファであり、クラスタＩＢ４１またはトラックＩＢ４２がデータで満杯になると、クラスタＩＢ４１またはトラックＩＢ４２がＦＳ５０の管理下に移動する。
【０１０７】
ＦＳ５０は、ＤＳ４０と同様、データの書き込み順序（ＬＲＵ）でブロックが管理されるＦＩＦＯ構造となっている。ＦＳ５０に存在するクラスタデータまたはトラックデータと同一ＬＢＡのクラスタデータまたはトラックデータがＦＳ５０に入力された場合、ＦＳ５０内のクラスタデータまたはトラックデータを無効化するだけでよく、書き換え動作を伴わない。
【０１０８】
ＦＳ５０に入力されたクラスタデータまたはトラックデータと同一ＬＢＡのクラスタデータまたはトラックデータについては、ブロック内で無効化し、ブロック内の全クラスタデータまたはトラックデータが無効になったブロックはフリーブロックＦＢとして解放する。ＦＳ５０のＦＩＦＯ管理構造の最後まで到達したブロックは、ホスト１から再書き込みされる可能性の低いデータとみなし、ＤＳ４０の管理下に移動する。
【０１０９】
更新頻度の高いデータはＦＳ５０を通過している最中に無効化され、更新頻度の低いデータだけがＦＳ５０から溢れていくため、更新頻度の高いデータと低いデータとをＦＳ５０で選り分けることができる。ＮＡＮＤ整理部３４は、ＦＳ５０をデータ整理対象から除外しており、これにより更新頻度の高いデータと更新頻度が低いデータとが同じブロックに混ざることを防いでいる。すなわち、この第５の実施形態では、ブロックの書き込み時期の新旧でストレージをＦＳ５０とＤＳ４０に分けており、図１２に示したブロックＬＲＵ管理テーブル２７を用いることによっても第５の実施形態と同様のストレージ管理をなし得る。
【０１１０】
（第６の実施形態）
第６の実施形態では、図１８などで説明したＷＣ２１からＮＡＮＤフラッシュ１０（クラスタＩＢ４１またはトラックＩＢ４２）への追い出し及び管理単位の切り替え規則についての変形例について述べる。
【０１１１】
図２６は、第６の実施形態の第１例を示すフローチャートである。図１８では、トラック中のＷＣ２１にキャッシュされた更新データ量（あるいは更新データ率）を参照して管理単位の切り替えを行うこととしたが、図２６では、同一トラック内におけるＷＣ２１及びＮＡＮＤフラッシュ１０上の更新データ量（あるいは更新データ率）を参照することとする。すなわち、図１５に示したように、ホスト１からのライト要求によって一旦トラックデータとしてＮＡＮＤフラッシュ１０に書き込まれるかあるいはデフラグ処理によってトラック化されてＮＡＮＤフラッシュ１０に書き込まれた後、同一トラック内のデータがホスト１からのライト要求によって更新された場合、図１６あるいは図１７に示すように、同一トラック内のデータがＷＣ２１上あるいはＮＡＮＤフラッシュ１０上の他のブロックに分散配置（断片化）される。第１例では、ＷＣ２１上に配置された同一トラック内のデータ量とＮＡＮＤフラッシュ１０上に断片化されて分散配置された同一トラック内のデータ量の合計を参照して管理単位の切り替えを行う。
【０１１２】
図２６においては、図１８のステップＳ２２０をステップＳ２２１に変更している。すなわち、図２６において、ＷＣ２１に空き領域がない場合は（ステップＳ２１０：ＹＥＳ）、書き込み制御部３２は、同一トラックに含まれるデータの更新データ量をＷＣ２１及びＮＡＮＤフラッシュ１０上でトラック毎に計算し、この計算した更新データ量を閾値ＤＣ２と比較し（ステップＳ２２１）、更新データ量が閾値ＤＣ２以上のトラックに含まれるデータに関してはトラックデータとしてトラックＩＢ４２に追い出し（ステップＳ２３０）、更新データが閾値ＤＣ２未満のトラックに含まれるデータに関してはクラスタデータとしてクラスタＩＢ４１に追い出す（ステップＳ２４０）。
【０１１３】
ＷＣ２１上のトラック中の更新データ量を計算する際は、前述したように、図５に示したＷＣ管理テーブル２２中の有効なセクタアドレスを用いてトラック中の更新データ量を計算することとしてもよいし、トラック中の更新データ量をトラック毎に逐次計算してＤＲＡＭ２０に管理情報として記憶しておき、この記憶した管理情報を使用するようにしてもよい。また、ＮＡＮＤフラッシュ１０上のトラック中の更新データ量を計算する際は、図６に示したトラック管理テーブル２３の断片化数を用いる。
【０１１４】
すなわち、トラック中の更新データ量（更新データ率）が多いと言うことは、データが散らばっている可能性が高く、リード性能が低下してくる可能性が高いため、トラックにまとめてデータをＮＡＮＤフラッシュ１０に追い出すことにより、リード性能を向上させる。
【０１１５】
図２７は、第６の実施形態の第２例を示すフローチャートである。図２７では、ＷＣ２１にキャッシュされているトラック数（異なるトラックアドレスの個数）を参照して管理単位の切り替えを行う。図２７においては、図１８のステップＳ２２０をステップＳ２２２に変更し、ステップＳ２２２のＹｅｓ，Ｎｏを図１８のステップＳ２２０と逆にしている。図２７において、ＷＣ２１に空き領域がない場合は（ステップＳ２１０：ＹＥＳ）、書き込み制御部３２は、ＷＣ２１上のトラック数を計算し、この計算したトラック数を閾値ＤＣ３と比較し（ステップＳ２２２）、ＷＣ２１上のトラック数が閾値ＤＣ３以上存在している状況下では、ＷＣ２１上のデータをクラスタデータとしてクラスタＩＢ４１に追い出し（ステップＳ２４０）、ＷＣ２１上のトラック数が閾値ＤＣ３未満存在している状況下では、ＷＣ２１上のデータをトラックデータとしてトラックＩＢ４２に追い出す（ステップＳ２３０）。
【０１１６】
ＷＣ２１上のトラック数を導出する際は、前述したように、図５に示したＷＣ管理テーブル２２中の有効なセクタアドレスを用いてトラック数を計算することとしてもよいし、ＷＣ２１上のトラック数を逐次計算してＤＲＡＭ２０に管理情報として記憶しておき、この記憶した管理情報を使用するようにしてもよい。また、ＷＣ管理テーブル２２として、ＷＣ２１上に記憶されたデータをトラック単位に管理するテーブルを採用する場合は、ＷＣ管理テーブル２２中の有効なトラックエントリ数を計数すればよい。
【０１１７】
ＷＣ２１からデータを追い出す場合に、トラック個数が多い場合は、トラック書き込みによるリード／ライト量が多くなり、かつランダムパターンの書き込みであることが予測される。このため、ＷＣ２１からデータを追い出す場合に、トラック個数が多い場合は、ライト性能を低下させないために、クラスタ書き込みを実行させる。
【０１１８】
図２８は、第６の実施形態の第３例を示すフローチャートである。図２８では、ＮＡＮＤフラッシュ１０において、クラスタ管理しているトラックの個数を参照して管理単位の切り替えを行う。図２８においては、図１８のステップＳ２２０をステップＳ２２３に変更している。図３０において、ＷＣ２１に空き領域がない場合は（ステップＳ２１０：ＹＥＳ）、書き込み制御部３２は、ＮＡＮＤフラッシュ１０上において、クラスタ管理しているトラックの個数を計算し、この計算したトラック数を閾値ＤＣ４と比較し（ステップＳ２２３）、クラスタ管理しているトラックの個数が閾値ＤＣ３以上の場合は、トラックデータとしてトラックＩＢ４２に追い出し（ステップＳ２３０）、クラスタ管理しているトラックの個数が閾値ＤＣ３未満の場合は、クラスタデータとしてクラスタＩＢ４１に追い出す（ステップＳ２４０）。
【０１１９】
クラスタ管理しているトラックとは、図６に示すトラック管理テーブル２３にエントリされている有効トラックであって、かつトラック管理テーブル２３上にトラックアドレスに対応して記憶位置が登録されているブロックとは異なるブロックに同一トラック内のクラスタが存在しているトラックのことをいう。したがって、ＮＡＮＤフラッシュ１０上のクラスタ管理しているトラックの個数を計算する際は、例えば、図６に示したトラック管理テーブル２３において、トラック有効／無効フラグが有効であって、断片化フラグが断片化有りを示しているトラックの個数を計数する。なお、クラスタ管理しているトラックの個数を管理情報として記憶しておき、この記憶した管理情報を使用するようにしてもよい。
【０１２０】
ＮＡＮＤフラッシュ１０の整理（クラスタマージ）などにより、トラック管理しているトラックが減少した場合、別言すればクラスタ管理しているトラックが増加した場合には、リード性能が低下している可能性があるため、ＷＣ２１からデータを追い出す際、トラック管理しているトラックが減少している場合は、ＷＣ２１にデータが存在するトラックについては、トラック追い出しを実行する。
【０１２１】
図２９は、第６の実施形態の第４例を示すフローチャートである。図２９では、ホスト１からのコマンド発行頻度を参照する。図２９においては、図１８のステップＳ２２０をステップＳ２２４に変更している。図２９において、ＷＣ２１に空き領域がない場合は（ステップＳ２１０：ＹＥＳ）、書き込み制御部３２は、ホスト１からのコマンド発行頻度を導出する。コマンド発行頻度としては、例えばホスト１からのデータ転送要求間隔を導出する。そして、導出したデータ転送要求間隔を閾値時間ＤＣ５と比較し（ステップＳ２２３）、ホスト１からのデータ転送要求間隔が閾値時間ＤＣ５以上ある場合は、トラックデータとして追い出し（ステップＳ２３０）、ホスト１からのデータ転送要求間隔が閾値ＤＣ５未満である場合は、クラスタデータとして追い出す（ステップＳ２４０）。すなわち、ホスト１からのコマンド発行頻度が低い場合にはトラックとして追い出し、高い場合にはクラスタとして追い出す。
【０１２２】
ホスト１のコマンド発行頻度が低い場合には、トラックとして書き込むための時間増加が与える影響が少ないのでリード性能の低下を防ぐためにトラックとして追い出し、逆に頻度が高い場合には、トラック化による時間増加が性能低下につながるので、クラスタとして書き込みを実行する。なお、コマンド発行頻度をホスト１とＳＳＤ１００との間の転送レートによって判断するようにしてもよい。すなわち、ホスト１とＳＳＤ１００との間の転送レートが閾値以下の場合はトラックデータとして追い出し、ホスト１とＳＳＤ１００との間の転送レートが閾値より大きい場合は、クラスタデータとして追い出すようにしてもよい。
【０１２３】
また、管理情報がＤＲＡＭ２０上に存在するデータはクラスタデータとして追い出し、管理情報がＮＡＮＤフラッシュ１０上に存在するデータはトラックデータとして追い出すようにしてもよい。
【０１２４】
（第７の実施形態）
第７の実施形態では、デフラグを行う際のデータ整理対象ブロックの選択の仕方についての他の例を説明する。第１の実施形態では、アクセス頻度が低い場合に、ＮＡＮＤフラッシュ１０のリソース使用量が目標値Ｆrefを超えた場合に、クラスタをＬＢＡ順に集めてトラック化するデフラグを発動するようにしており、さらにデフラグを行う際には、書き込み時期が古いブロックの中で、有効データ量が少ないブロックを整理対象ブロックとして選択することとしているが、デフラグを行う際、書き込み時期が閾値より古いブロックのデータを整理対象ブロックとして選択することにしてもよいし、あるいは書き込み時期がより古いデータから整理対象ブロックを選択することにしてもよい。
【０１２５】
また、デフラグを行う際、有効データ量が閾値より少ないブロックを整理対象ブロックとして選択することにしてもよいし、あるいは有効データ量がより少ないブロックから整理対象ブロックを選択することにしてもよい。
【０１２６】
また、デフラグを行う際、読み出しアクセスが多いブロックを整理対象ブロックとして選択することにしてもよい。すなわち、図１３に示したブロック管理テーブル２８を用いてブロック毎の読み出し回数（または読み出しデータ量）をカウントすることとし、デフラグを行う際には、ブロック管理テーブル２８を用いて読み出し回数（または読み出しデータ量）が閾値より多いブロックを選択し、選択したブロックを整理対象ブロックとする。この手法では、頻繁に読み出しが発生するブロックを選択して、そのブロック内のデータをトラック化することで、リード速度を上昇させる。デフラグが終了すると、ブロック管理テーブル２８の読み出し回数は、零にリセットされる。
【０１２７】
また、デフラグを行う際、更新データ量が閾値よりも多いトラックに所属するクラスタを集めるようにしてもよい。すなわち、更新データ量が閾値よりも多いトラックに所属するクラスタを含むブロックをデフラグの対象ブロックとして選択し、選択したデフラグ対象ブロック内のクラスタを集めてトラック化する。例えば、図６に示したトラック管理テーブル２３の断片化数が閾値以上存在するトラックを選択することで、更新データ量が多いトラックを選択する。断片化数が多いということは、トラック化された後に、他のブロックにクラスタとして離散されているクラスタ数が多いということであるので、更新データ量が多いトラックを判定するための目安となる。この手法では、各ブロックにクラスタが離散されている可能性の高いトラックのクラスタを集めてトラック化するので、リード速度を上昇させることが可能である。
【０１２８】
また、デフラグを行う際、読み出しアクセスが多いトラックに所属するクラスタを集めるようにしてもよい。すなわち、読み出しアクセスが閾値よりも多いトラックに所属するクラスタを含むブロックをデフラグの対象ブロックとして選択し、選択したデフラグ対象ブロック内のクラスタを集めてトラック化する。例えば、図６に示したトラック管理テーブル２３の読み出しデータ量（読み出し回数）が閾値以上存在するトラックを選択することで、読み出しアクセスが多いトラックを選択する。この手法では、頻繁に読み出しが発生するトラックを選択して、そのトラックに所属するクラスタをトラック化することで、リード速度を上昇させる。デフラグが終了すると、トラック管理テーブル２３の読み出しデータ量は、零にリセットされる。
【０１２９】
（第８の実施形態）
つぎに、デフラグの発動条件についての他の例について述べる。第１の実施形態では、アクセス頻度が低い場合に、ＮＡＮＤフラッシュ１０のリソース使用量が目標値Ｆrefを超えた場合に、クラスタをＬＢＡ順に集めてトラック化するデフラグを発動するようにしているが、第８の実施形態では、ＮＡＮＤフラッシュ１０のリソース使用量が目標値Ｆrefを超えた場合に、クラスタ管理するトラック数が閾値以上になったときにデフラグを発動させることとする。クラスタ管理するトラック数は、第６の実施形態で説明したように、図６に示したトラック管理テーブル２３において、トラック有効／無効フラグが有効であって、断片化がありのトラックの個数を計数することによって求める。
【０１３０】
この第８の実施形態においては、トラック管理しているトラックが減少した場合、別言すればクラスタ管理しているトラックが増加した場合に、デフラグ発動条件が成立したとしてデフラグを行うようにしており、これによりトラック管理するトラックが増加され、リード速度を向上させることが可能となる。また、この第８の実施形態の手法を用いてデフラグの発動をトリガした場合においても、先の第１の実施形態あるいは第７の実施形態で説明したデフラグ対象ブロックあるいはデフラグ対象データの選択手法を採用するようにしてもよい。すなわち、デフラグを行う際は、
・書き込み時期が閾値より古いブロックのデータをデフラグ対象ブロックとして選択する
・有効データ量が閾値より少ないブロックをデフラグ対象ブロックとして選択する
・書き込み時期が閾値より古く、有効データ量が閾値より少ないブロックをデフラグ対象ブロックとして選択する
・読み出しアクセスが閾値より多いブロックを整理対象ブロックとして選択する
・更新データ量が閾値よりも多いトラックに所属するクラスタを集めてデフラグする
・読み出しアクセスが多いトラックに所属するクラスタを集めてデフラグする
の少なくとも１つを採用するようにしてもよい。
【０１３１】
（第９の実施形態）
第９の実施形態では、クラスタコンパクションについての他の例について述べる。第１の実施形態では、ホスト１からのアクセス頻度が高いときに、有効データ量が閾値より少ないブロックを整理対象ブロックとして選択してクラスタコンパクションを行うようにしたが、アクセス頻度が高いときに、書き込み時期が閾値より古く、有効データ量が閾値より少ないブロックをクラスタコンパクションの対象ブロックとして選択するようにしてもよい。書き込み時期が閾値より古いブロックを選択する際、図１２に示したブロックＬＲＵ管理テーブル２７を用いるようにしてもよいし、図２５に示したように、ブロックの書き込み時期の新旧でストレージをＦＳ５０とＤＳ４０に分ける手法の何れを採用しても良い。
【０１３２】
また、第１の実施形態では、クラスタコンパクションは、アクセス頻度が低いときに、デフラグなどのＮＡＮＤフラッシュ１０の整理を行ってフリーブロックＦＢの個数が閾値より少なくなった際に実行されるようにしているが、どのような状況下であってもフリーブロックＦＢの個数が閾値より少なくなった際に、クラスタコンパクションが実行されるようにしてもよい。また、第１の実施形態では、トラックコンパクション、デフラグの対象とならなかった有効クラスタを１つのフリーブロックＦＢに集めることでクラスタコンパクションを実行しているが、有効データ量が閾値より少ないブロックをクラスタコンパクションの対象ブロックとして選択するようにしてもよく、さらには、書き込み時期が閾値より古く、有効データ量が閾値より少ないブロックをクラスタコンパクションの対象ブロックとして選択するようにしてもよい。
【０１３３】
さらに、ホスト１からのアクセス頻度が低いときに、書き込みデータ量が閾値より多いトラックのデータを１つのブロックに集めるトラックの解体（クラスタマージ）あるいはクラスタコンパクションを実行するようにしてもよい。この手法では、例えば、図６に示したトラック管理テーブル２３の書き込みデータ量（書き込み回数）が閾値以上存在するトラックを選択することで、書き込みアクセスが多いトラックを選択する。この手法では、書き込みアクセスが多いトラックを１つのブロックに集めることで、書き込み速度を向上させる。
【０１３４】
（第１０の実施形態）
第１０の実施形態では、ＳＳＤ１００の温度をＮＡＮＤフラッシュ１０の整理の発動パラメータとしている。ＳＳＤ１００は、温度センサ９０（図１、図２２参照）を搭載しており、温度センサ９０の出力に基づき環境温度が閾値未満のときには、第７または第８の実施形態で説明したデフラグを実行する。さらに、環境温度が閾値以下のとき、書き込みデータ量が閾値より多いトラックのデータを１つのブロックに集めるトラックの解体（クラスタマージ）を行うようにしてもよい。温度センサはコントローラ３０に隣接して設けてもよいし、ＮＡＮＤフラッシュ１０に隣接して設けてもよい。ＮＡＮＤフラッシュ１０、ＤＲＡＭ２０、及びコントローラ３０が実装されるＳＳＤ１００の基板上であれば設置場所は自由であり、複数の温度センサを設けてもよい。また、ＳＳＤ１００自体は温度センサを有さず、ホスト１から環境温度を含む情報が通知される構成で合ってもよい。
【０１３５】
一方、環境温度が閾値以上のときには、有効データ量が閾値より少ないブロックを整理対象ブロックとして選択するクラスタコンパクションあるいは書き込み時期が閾値より古く、有効データ量が閾値より少ないブロックを整理対象ブロックとして選択するクラスタコンパクションを実行する。クラスタコンパクションは、デフラグあるいはトラックの解体（クラスタマージ）に比べ、ＮＡＮＤフラッシュ１０に対するリード／ライトアクセスが少なくて済み、消費電力量、温度上昇も少ないので、環境温度が高めのときに実行させる。これに対し、デフラグあるいはトラックの解体（クラスタマージ）は、環境温度が低めのときに実行させる。
【０１３６】
（第１１の実施形態）
第１１の実施形態では、ＳＳＤ１００の消費電力量をＮＡＮＤフラッシュ１０の整理の発動パラメータとしている。ＳＳＤ１００の消費電力量を閾値以上にしてもよい状況下では、消費電力量が比較的大きなデフラグあるいはトラックの解体（クラスタマージ）を実行させ、ＳＳＤ１００の消費電力量を閾値以上にしてはいけない状況下では、消費電力量が比較的小さなクラスタコンパクションを実行させる。例えば、ホスト１は自身の電源能力に従い、許容できる消費電力量をＳＳＤ１００に通知する。コントローラ３０は当該通知を受け取り、通知された許容消費電力量が閾値以上であるか否かを判断すればよい。
【０１３７】
（第１２の実施形態）
データ整理の対象ブロックを次のような手法を用いて決定してもよい。
・書き込み時期が閾値よりも新しいブロックの中で有効データ量が閾値よりも少ないブロックをデータ整理対象として決定する。この方式では、書き込み時期が同じ（新しい）時期のデータを集めて１つのブロックに書き直すので、書き込み時期が離れたデータが１つのブロックに混在することが防止される。
・ブロック内で各クラスタが所属するトラックの個数が多いブロックをデータ整理対象として決定する。
・ブロック内で各クラスタが所属するトラックの個数が少ないブロックをデータ整理対象として決定する。
・書き込みアクセスが多いブロックを整理対象と決定する。この場合は、整理対象としたブロックの有効データをクラスタ管理してコンパクションまたはクラスタマージする。
【０１３８】
また、上記実施形態では、整理対象ブロックを決定する際に、ブロック内の有効データ量として有効クラスタ数を参照するようにしたが、ブロックの有効クラスタの比率（割合）、で整理対象ブロックを選択するようにしてもよい。ブロックの有効クラスタの比率は、例えば、有効クラスタ量（数）／書き込み可能なクラスタ量（数）によって求める。また、ＷＣ２１からの追い出しの際に、トラック内の更新データ量あるいはトラック内の有効データ量を参照するようにしたが、トラック内の更新データ率あるいはトラック内の有効データ率を参照するようにしてもよい。同様に、上記実施の形態において、データ量、データ数を参照している判定に関しては、データ率を参照する判定に置き換えても良い。
【０１３９】
さらに、ＮＡＮＤフラッシュ１０上の管理テーブルが記憶されたブロックを整理対象に含めるようにしてもよい。また、クラスタ管理されるブロックをＳＬＣ(Single Level Cell)で記録し、トラック管理されるブロックをＭＬＣ（Multi Level Cell）で記録するようにしてもよい。ＳＬＣとは、１つのメモリセルに１ビットを記録する方式を示し、ＭＬＣとは、１つのメモリセルに２ビット以上を記録する方式を示す。ＭＬＣにおける一部ビットのみを使用して、疑似的なＳＬＣ方式で管理することも可能である。また、管理情報についてはＳＬＣで記録するようにしてもよい。
【０１４０】
（第１３の実施形態）
図３０は、ＳＳＤ１００を搭載したパーソナルコンピュータ１２００の一例を示す斜視図である。パーソナルコンピュータ１２００は、本体１２０１、及び表示ユニット１２０２を備えている。表示ユニット１２０２は、ディスプレイハウジング１２０３と、このディスプレイハウジング１２０３に収容された表示装置１２０４とを備えている。
【０１４１】
本体１２０１は、筐体１２０５と、キーボード１２０６と、ポインティングデバイスであるタッチパッド１２０７とを備えている。筐体１２０５内部には、メイン回路基板、ＯＤＤ（Optical  Disk  Device）ユニット、カードスロット、及びＳＳＤ１００等が収容されている。
【０１４２】
カードスロットは、筐体１２０５の周壁に隣接して設けられている。周壁には、カードスロットに対向する開口部１２０８が設けられている。ユーザは、この開口部１２０８を通じて筐体１２０５の外部から追加デバイスをカードスロットに挿抜することが可能である。
【０１４３】
ＳＳＤ１００は、従来のＨＤＤの置き換えとして、パーソナルコンピュータ１２００内部に実装された状態として使用してもよいし、パーソナルコンピュータ１２００が備えるカードスロットに挿入した状態で、追加デバイスとして使用してもよい。
【０１４４】
図３１は、ＳＳＤを搭載したパーソナルコンピュータのシステム構成例を示している。パーソナルコンピュータ１２００は、ＣＰＵ１３０１、ノースブリッジ１３０２、主メモリ１３０３、ビデオコントローラ１３０４、オーディオコントローラ１３０５、サウスブリッジ１３０９、ＢＩＯＳ−ＲＯＭ１３１０、ＳＳＤ１００、ＯＤＤユニット１３１１、エンベデッドコントローラ／キーボードコントローラＩＣ（ＥＣ／ＫＢＣ）１３１２、及びネットワークコントローラ１３１３等を備えている。
【０１４５】
ＣＰＵ１３０１は、パーソナルコンピュータ１２００の動作を制御するために設けられたプロセッサであり、ＳＳＤ１００から主メモリ１３０３にロードされるオペレーティングシステム（ＯＳ）を実行する。更に、ＯＤＤユニット１３１１が、装填された光ディスクに対して読出し処理及び書込み処理の少なくとも１つの処理の実行を可能にした場合に、ＣＰＵ１３０１は、それらの処理の実行をする。
【０１４６】
また、ＣＰＵ１３０１は、ＢＩＯＳ−ＲＯＭ１３１０に格納されたシステムＢＩＯＳ（Basic  Input  Output  System）も実行する。尚、システムＢＩＯＳは、パーソナルコンピュータ１２００内のハードウェア制御のためのプログラムである。
【０１４７】
ノースブリッジ１３０２は、ＣＰＵ１３０１のローカルバスとサウスブリッジ１３０９との間を接続するブリッジデバイスである。ノースブリッジ１３０２には、主メモリ１３０３をアクセス制御するメモリコントローラも内蔵されている。
【０１４８】
また、ノースブリッジ１３０２は、ＡＧＰ（Accelerated  Graphics  Port）バス等を介してビデオコントローラ１３０４との通信、及びオーディオコントローラ１３０５との通信を実行する機能も有している。
【０１４９】
主メモリ１３０３は、プログラムやデータを一時的に記憶し、ＣＰＵ１３０１のワークエリアとして機能する。主メモリ１３０３は、例えばＲＡＭから構成される。
【０１５０】
ビデオコントローラ１３０４は、パーソナルコンピュータ１２００のディスプレイモニタとして使用される表示ユニット１２０２を制御するビデオ再生コントローラである。
【０１５１】
オーディオコントローラ１３０５は、パーソナルコンピュータ１２００のスピーカ１３０６を制御するオーディオ再生コントローラである。
【０１５２】
サウスブリッジ１３０９は、ＬＰＣ（Low  Pin  Count）バス１３１４上の各デバイス、及びＰＣＩ（Peripheral  Component  Interconnect）バス１３１５上の各デバイスを制御する。また、サウスブリッジ１３０９は、各種ソフトウェア及びデータを格納する記憶装置であるＳＳＤ１００を、ＡＴＡインタフェースを介して制御する。
【０１５３】
パーソナルコンピュータ１２００は、セクタ単位でＳＳＤ１００へのアクセスを行う。ＡＴＡインタフェースを介して、書き込みコマンド、読出しコマンド、キャッシュフラッシュコマンド等がＳＳＤ１００に入力される。
【０１５４】
また、サウスブリッジ１３０９は、ＢＩＯＳ−ＲＯＭ１３１０、及びＯＤＤユニット１３１１をアクセス制御するための機能も有している。
【０１５５】
ＥＣ／ＫＢＣ１３１２は、電力管理のためのエンベデッドコントローラと、キーボード（ＫＢ）１２０６及びタッチパッド１２０７を制御するためのキーボードコントローラとが集積された１チップマイクロコンピュータである。
【０１５６】
このＥＣ／ＫＢＣ１３１２は、ユーザによるパワーボタンの操作に応じてパーソナルコンピュータ１２００の電源をＯＮ／ＯＦＦする機能を有している。ネットワークコントローラ１３１３は、例えばインターネット等の外部ネットワークとの通信を実行する通信装置である。
【０１５７】
なお、ＳＳＤ１００が搭載される情報処理装置として、スチルカメラ、ビデオカメラなどの撮像装置を採用してもよい。このような情報処理装置は、ＳＳＤ１００を搭載することによって、ランダムリード及びランダムライト性能を向上させることが可能となる。従って、情報処理装置を使用するユーザの利便性が向上する。
【０１５８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１５９】
１  ホスト  ２  ホストＩ／Ｆ  １０  ＮＡＮＤフラッシュ、１２  不揮発性クラスタ管理テーブル（正引き）、１３  不揮発性クラスタ管理テーブル（逆引き）、２０  ＤＲＡＭ、２１  ライトキャッシュ（ＷＣ）、２２  ＷＣ管理テーブル、２３  トラック管理テーブル、２４  揮発性クラスタ管理テーブル、２５  トラックエントリ管理テーブル、２６  ブロック内有効クラスタ数管理テーブル、２７  ブロックＬＲＵ管理テーブル、２８  ブロック管理テーブル、３０  コントローラ、３１  コマンド解釈部、３２  書き込み制御部、３３  読み出し制御部、３４  ＮＡＮＤ整理部。
【図１】
2012141946.tif 000003
【図２】
2012141946.tif 000004
【図３】
2012141946.tif 000005
【図４】
2012141946.tif 000006
【図５】
2012141946.tif 000007
【図６】
2012141946.tif 000008
【図７】
2012141946.tif 000009
【図８】
2012141946.tif 000010
【図９】
2012141946.tif 000011
【図１０】
2012141946.tif 000012
【図１１】
2012141946.tif 000013
【図１２】
2012141946.tif 000014
【図１３】
2012141946.tif 000015
【図１４】
2012141946.tif 000016
【図１５】
2012141946.tif 000017
【図１６】
2012141946.tif 000018
【図１７】
2012141946.tif 000019
【図１８】
2012141946.tif 000020
【図１９】
2012141946.tif 000021
【図２０】
2012141946.tif 000022
【図２１】
2012141946.tif 000023
【図２２】
2012141946.tif 000024
【図２３】
2012141946.tif 000025
【図２４】
2012141946.tif 000026
【図２５】
2012141946.tif 000027
【図２６】
2012141946.tif 000028
【図２７】
2012141946.tif 000029
【図２８】
2012141946.tif 000030
【図２９】
2012141946.tif 000031
【図３０】
2012141946.tif 000032
【図３１】
2012141946.tif 000033