(57)【要約】【課題】性能を改善することができるメモリシステムを実現する。【解決手段】実施形態によれば、メモリシステムは、不揮発性メモリと、不揮発性メモリに格納されている論理物理アドレス変換テーブルの一部を格納するように構成された第１のキャッシュを、第１のキャッシュタグを使用して管理するコントローラとを含む。第１のキャッシュは各々が複数のサブラインを含む複数のキャッシュラインを含み、第１のキャッシュタグの各エントリーは対応するキャッシュライン内の複数のサブラインに論理物理アドレス変換テーブルのデータが転送済みであるか否かを示す複数のビットマップフラグを含む。コントローラは、論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定する。【選択図】図１３
2019133252.tif 000002
【特許請求の範囲】
【請求項１】
ホストに接続可能なメモリシステムであって、
不揮発性メモリと、
前記不揮発性メモリに電気的に接続され、前記不揮発性メモリに格納されている論理物理アドレス変換テーブルの一部を格納するように構成された第１のキャッシュを、第１のキャッシュタグを使用して管理するコントローラとを具備し、
前記第１のキャッシュは各々が複数のサブラインを含む複数のキャッシュラインを含み、前記第１のキャッシュタグは前記複数のキャッシュラインに対応する複数のエントリーを含み、前記第１のキャッシュタグの各エントリーは、前記論理物理アドレス変換テーブルのどの領域が対応するキャッシュラインに格納されているかを示すタグと、前記対応するキャッシュライン内の複数のサブラインに対応する複数のビットマップフラグとを含み、各ビットマップフラグは対応するサブラインに前記論理物理アドレス変換テーブルのデータが転送済みであるか否かを示し、
前記コントローラは、
前記第１のキャッシュの一つのキャッシュラインを入れ替える場合、入れ替え対象キャッシュライン候補の中で、前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定するように構成されている、メモリシステム。
【請求項２】
前記コントローラは、前記入れ替え対象キャッシュライン候補の中から、有効を示す値のビットマップフラグの数が最も少ないキャッシュラインを探すことによって、前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインを前記入れ替え対象キャッシュラインに決定するように構成されている請求項１記載のメモリシステム。
【請求項３】
前記第１のキャッシュタグの各エントリーは、対応する複数のビットマップフラグの中に含まれる、有効を示す値のビットマップフラグの数を示すカウンタをさらに含み、
前記コントローラは、前記入れ替え対象キャッシュライン候補の中から、前記カウンタの値が最も小さいキャッシュラインを探すことによって、前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインを前記入れ替え対象キャッシュラインに決定するように構成されている請求項１記載のメモリシステム。
【請求項４】
前記第１のキャッシュタグの各エントリーは、第１のリプレースモードが使用される場合には、ＬＲＵ（least recently used）ポリシー用のタイムスタンプが格納され、第２のリプレースモードが使用される場合には、対応する複数のビットマップフラグの中に含まれる、有効を示す値のビットマップフラグの数を示すカウンタが格納される、共用記憶領域をさらに含み、
前記コントローラは、
前記第１のリプレースモードが使用される場合には、前記入れ替え対象キャッシュライン候補の間で、前記タイムスタンプを比較することによってタイムスタンプが最も旧いキャッシュラインを前記入れ替え対象キャッシュラインに決定し、前記第２のリプレースモードが使用される場合には、前記入れ替え対象キャッシュライン候補の間で、前記カウンタを比較することによって前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインを前記入れ替え対象キャッシュラインに決定するように構成されている請求項１記載のメモリシステム。
【請求項５】
前記タイムスタンプは最近使用されたキャッシュラインほど大きな値に設定されるように更新され、
前記コントローラは、前記第１のリプレースモードまたは前記第２のリプレースモードのどちらが使用される場合でも、前記入れ替え対象キャッシュライン候補の中から前記共用記憶領域に格納されている値が最も小さいキャッシュラインを前記入れ替え対象キャッシュラインに決定するように構成されている請求項４記載のメモリシステム。
【請求項６】
前記第１のキャッシュタグの各エントリーは、最近使用されたキャッシュラインほど大きな値または小さな値に設定されるように更新されるタイムスタンプをさらに含み、
前記コントローラは、前記入れ替え対象キャッシュライン候補から、対応するタイムスタンプと最新のタイムスタンプとの間の差分が閾値よりも小さいキャッシュラインを除外し、残りのキャッシュラインの中で、前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインを前記入れ替え対象キャッシュラインに決定するように構成されている請求項１記載のメモリシステム。
【請求項７】
前記第１のキャッシュタグの各エントリーは、ＬＲＵ（least recently used）ポリシー用のタイムスタンプをさらに含み、
前記コントローラは、前記入れ替え対象キャッシュライン候補の中に、前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインが２以上存在する場合、前記データが転送済みのサブラインの数が最も少ない前記２以上のキャッシュラインの中で、前記タイムスタンプが最も旧いキャッシュラインを前記入れ替え対象キャッシュラインに決定するように構成されている請求項１記載のメモリシステム。
【請求項８】
前記第１のキャッシュタグの各エントリーは、ＬＲＵ（least recently used）ポリシー用のタイムスタンプと、キャッシュライン内の複数のサブラインにそれぞれ対応する複数のダーティーフラグとをさらに含み、各ダーティーフラグは、対応するサブラインが前記論理物理アドレス変換テーブルに反映されていないデータを保持するダーティーなサブラインであるか否かを示し、
前記コントローラは、前記入れ替え対象キャッシュライン候補の中に、前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインが２以上存在する場合、前記データが転送済みのサブラインの数が最も少ない２以上のキャッシュラインの中から、ダーティーなサブラインの数が最も少ないキャッシュラインを探し、
前記データが転送済みのサブラインの数が最も少ない２以上のキャッシュラインの中に、ダーティーなサブラインの数が最も少ないキャッシュラインが２以上存在する場合、ダーティーなサブラインの数が最も少ない前記２以上のキャッシュラインの中で、タイムスタンプが最も旧いキャッシュラインを前記入れ替え対象キャッシュラインに決定するように構成されている請求項１記載のメモリシステム。
【請求項９】
前記第１のキャッシュは前記ホストのメモリに格納されている請求項１記載のメモリシステム。
【請求項１０】
前記第１のキャッシュは前記メモリシステム内のランダムアクセスメモリに格納されている請求項１記載のメモリシステム。
【請求項１１】
前記ランダムアクセスメモリは前記コントローラ内のスタティックＲＡＭまたは前記コントローラの外部に設けられたダイナミックＲＡＭである請求項１０記載のメモリシステム。
【請求項１２】
前記第１のキャッシュは前記ホストのメモリに格納され、
前記コントローラは、前記ホストのメモリ内の前記第１のキャッシュに格納すべき、前記論理物理アドレス変換テーブルのデータと、前記ホストのメモリに格納すべき、前記論理物理アドレス変換テーブル以外の他のデータとをキャッシュするように構成された第２のキャッシュをさらに含み、
前記第２のキャッシュは、前記第２のキャッシュのキャッシュラインのうち、前記論理物理アドレス変換テーブルのデータが格納されているキャッシュラインよりも、前記他のデータが格納されているキャッシュラインを優先的に入れ替え対象キャッシュラインに決定するように構成されたキャッシュコントローラを含む請求項１記載のメモリシステム。
【請求項１３】
前記第２のキャッシュは、前記第２のキャッシュ内の各キャッシュラインに対応する優先度を格納するように構成された第２のキャッシュタグを含み、
前記第２のキャッシュの前記キャッシュコントローラは、前記第２のキャッシュの一つのキャッシュラインに格納されるべき第１のデータのライトアドレスが前記他のデータを格納するための前記ホストのメモリ上の第１の記憶領域のアドレス範囲に属する場合、前記第２のキャッシュの前記一つのキャッシュラインに対応する前記第２のキャッシュタグのエントリーに、前記第２のキャッシュの前記一つのキャッシュラインを優先的に入れ替え対象とするための優先度を格納するように構成されている請求項１２記載のメモリシステム。
【請求項１４】
前記コントローラは、前記ホストのメモリに前記他のデータを格納するためのライト要求を発行するように構成された第１のバスマスタを含み、
前記第２のキャッシュは、前記第２のキャッシュ内の各キャッシュラインに対応する優先度を格納するように構成された第２のキャッシュタグを含み、
前記第２のキャッシュは、前記第１のバスマスタからの前記ライト要求に応じて前記第２のキャッシュの一つのキャッシュラインにデータを格納する場合、前記第２のキャッシュの前記一つのキャッシュラインに対応する前記第２のキャッシュタグのエントリーに、前記第２のキャッシュの前記一つのキャッシュラインを優先的に入れ替え対象とするための優先度を格納するように構成されている請求項１２記載のメモリシステム。
【請求項１５】
ホストに接続可能なメモリシステムであって、
不揮発性メモリと、
前記不揮発性メモリに電気的に接続され、前記不揮発性メモリに格納されている論理物理アドレス変換テーブルの一部を格納するように構成された第１のキャッシュを、第１のキャッシュタグを使用して管理するコントローラとを具備し、
前記第１のキャッシュは前記ホストのメモリに格納され、前記第１のキャッシュは各々が複数のサブラインを含む複数のキャッシュラインを含み、前記第１のキャッシュタグは前記複数のキャッシュラインに対応する複数のエントリーを含み、前記第１のキャッシュタグの各エントリーは、前記論理物理アドレス変換テーブルのどの領域が対応するキャッシュラインに格納されているかを示すタグと、前記対応するキャッシュライン内の複数のサブラインにそれぞれ対応する複数のビットマップフラグとを含み、各ビットマップフラグは対応するサブラインに前記論理物理アドレス変換テーブルのデータが転送済みであるか否かを示し、
前記コントローラは、
前記ホストのメモリ内の前記第１のキャッシュに格納すべき、前記論理物理アドレス変換テーブルのデータと、前記ホストのメモリに格納すべき、前記論理物理アドレス変換テーブル以外の他のデータとをキャッシュするように構成された第２のキャッシュをさらに含み、
前記コントローラは、前記第１のキャッシュの一つのキャッシュラインを入れ替える場合、入れ替え対象キャッシュライン候補の中で、前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定するように構成され、
前記第２のキャッシュは、前記第２のキャッシュのキャッシュラインのうち、前記論理物理アドレス変換テーブルのデータが格納されているキャッシュラインよりも、前記他のデータが格納されているキャッシュラインを優先的に入れ替え対象キャッシュラインに決定するように構成されたキャッシュコントローラを含む、メモリシステム。
【請求項１６】
前記第２のキャッシュは、前記第２のキャッシュ内の各キャッシュラインに対応する優先度を格納するように構成された第２のキャッシュタグを含み、
前記第２のキャッシュの前記キャッシュコントローラは、前記第２のキャッシュの一つのキャッシュラインに格納されるべき第１のデータのライトアドレスが前記他のデータを格納するための前記ホストのメモリ上の第１の記憶領域のアドレス範囲に属する場合、前記第２のキャッシュの前記一つのキャッシュラインに対応する前記第２のキャッシュタグのエントリーに、前記第２のキャッシュの前記一つのキャッシュラインを優先的に入れ替え対象とするための優先度を格納するように構成されている請求項１５記載のメモリシステム。
【請求項１７】
前記コントローラは、前記ホストのメモリに前記他のデータを格納するためのライト要求を発行するように構成された第１のバスマスタを含み、
前記第２のキャッシュは、前記第２のキャッシュ内の各キャッシュラインに対応する優先度を格納するように構成された第２のキャッシュタグを含み、
前記第２のキャッシュの前記キャッシュコントローラは、前記第１のバスマスタからの前記ライト要求に応じて前記第２のキャッシュの一つのキャッシュラインにデータを格納する場合、前記第２のキャッシュの前記一つのキャッシュラインに対応する前記第２のキャッシュタグのエントリーに、前記第２のキャッシュの前記一つのキャッシュラインを優先的に入れ替え対象とするための優先度を格納するように構成されている請求項１５記載のメモリシステム。
【請求項１８】
ホストに接続可能なメモリシステムであって、
不揮発性メモリと、
前記ホストが指定する論理アドレスと、前記不揮発性メモリの記憶領域を示す物理アドレスとの対応を示すアドレス変換データを第１のキャッシュにキャッシュするコントローラと、を具備し、
前記第１のキャッシュは前記コントローラが前記第１のキャッシュを無効化する単位であるキャッシュラインを複数含み、前記複数のキャッシュラインのそれぞれは、前記コントローラが前記アドレス変換データをキャッシュする単位であるサブラインを複数含み、
前記コントローラは、前記アドレス変換データがキャッシュされている前記サブラインの数が少ないキャッシュラインを優先して前記第１のキャッシュから追い出す、メモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、不揮発性メモリを制御する技術に関する。
【背景技術】
【０００２】
近年、不揮発性メモリを備えるメモリシステムが広く普及している。
【０００３】
このようなメモリシステムとして、ＮＡＮＤ型フラッシュメモリを備えるユニバーサル・フラッシュ・ストレージ（ＵＦＳ）デバイス、ＮＡＮＤ型フラッシュメモリを備えるソリッドステートドライブ（ＳＳＤ）、等、が知られている。ＳＳＤは、様々なコンピューティングデバイスのメインストレージとして使用されている。
【０００４】
このようなメモリシステムにおいては、論理アドレスを不揮発性メモリの物理アドレスに変換するためのアドレス変換が実行される。このアドレス変換に要する時間が長くなると、メモリシステムの性能の低下が引き起こされる場合がある
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第５０１２０１６号公報
【特許文献２】特開平５−２８２２０８号公報
【特許文献３】米国特許第５７８４５９０号明細書
【特許文献４】米国特許出願公開第２０１７／００６８６２１号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明が解決しようとする課題は、性能を改善することができるメモリシステムを提供することである。
【課題を解決するための手段】
【０００７】
実施形態によれば、ホストに接続可能なメモリシステムは、不揮発性メモリと、前記不揮発性メモリに電気的に接続され、前記不揮発性メモリに格納されている論理物理アドレス変換テーブルの一部を格納するように構成された第１のキャッシュを、第１のキャッシュタグを使用して管理するコントローラとを具備する。前記第１のキャッシュは各々が複数のサブラインを含む複数のキャッシュラインを含み、前記第１のキャッシュタグは前記複数のキャッシュラインに対応する複数のエントリーを含み、前記第１のキャッシュタグの各エントリーは、前記論理物理アドレス変換テーブルのどの領域が対応するキャッシュラインに格納されているかを示すタグと、前記対応するキャッシュライン内の複数のサブラインに対応する複数のビットマップフラグとを含み、各ビットマップフラグは対応するサブラインに前記論理物理アドレス変換テーブルのデータが転送済みであるか否かを示す。前記コントローラは、前記第１のキャッシュの一つのキャッシュラインを入れ替える場合、入れ替え対象キャッシュライン候補の中で、前記論理物理アドレス変換テーブルのデータが転送済みのサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定する。
【図面の簡単な説明】
【０００８】
【図１】第１実施形態に係るメモリシステムを含む情報処理システムの構成例を示すブロック図。
【図２】第１実施形態のメモリシステム内の不揮発性メモリの構成例を示す図。
【図３】第１実施形態のメモリシステムによって管理されるアドレス変換テーブルキャッシュとアドレス変換テーブルキャッシュタグとの関係の例を示す図。
【図４】図３のアドレス変換テーブルキャッシュタグの構成例を示す図。
【図５】図３のアドレス変換テーブルキャッシュタグの他の構成例を示す図。
【図６】図３のアドレス変換テーブルキャッシュの構成例を示す図。
【図７】キャッシュヒット時に第１実施形態のメモリシステムによって実行されるキャッシュ制御処理の処理シーケンスを示す図。
【図８】キャッシュラインヒット（ビットマップミス）時に第１実施形態のメモリシステムによって実行されるキャッシュ制御処理の処理シーケンスを示す図。
【図９】図８のキャッシュ制御処理において実行される、サブライン転送動作およびビットマップフラグ更新動作示す図。
【図１０】キャッシュミス時に第１実施形態のメモリシステムによって実行されるキャッシュ制御処理の処理シーケンスを示す図。
【図１１】図１０のキャッシュ制御処理において実行される、キャッシュライン無効化動作、サブライン転送動作およびキャッシュライン有効化動作を示す図。
【図１２】アドレス変換テーブルキャッシュおよびアドレス変換テーブルキャッシュを第１実施形態のメモリシステム内のコントローラに内蔵されたＲＡＭ内に置く構成を示すブロック図。
【図１３】アドレス変換テーブルキャッシュおよびアドレス変換テーブルキャッシュを第１実施形態のメモリシステム内のコントローラの外部のＤＲＡＭに置く構成を示すブロック図。
【図１４】第１実施形態のメモリシステムによって実行される入れ替え対象キャッシュライン決定動作の手順を示すフローチャート。
【図１５】各キャッシュラインに対応する複数のビットマップフラグを使用することによって第１実施形態のメモリシステムによって実行される入れ替え対象キャッシュライン決定動作の手順を示すフローチャート。
【図１６】第１実施形態のメモリシステムによって実行されるキャッシュライン入れ替え動作の手順を示すフローチャート。
【図１７】第１実施形態のメモリシステムによって実行されるキャッシュライン転送動作の手順を示すフローチャート。
【図１８】第１実施形態のメモリシステムによって管理される、アドレス変換テーブルキャッシュと、ビットマップカウンタを含むアドレス変換テーブルキャッシュタグとの関係の例を示す図。
【図１９】図１８のアドレス変換テーブルキャッシュタグ内の各ビットマップカウンタの値の例を示す図。
【図２０】各キャッシュラインに対応するビットマップカウンタを使用することによって第１実施形態のメモリシステムによって実行される入れ替え対象キャッシュライン決定動作の手順を示すフローチャート。
【図２１】アドレス変換テーブルキャッシュタグが各キャッシュラインに対応するビットマップカウンタを含む場合に、第１実施形態のメモリシステムによって実行されるサブライン転送動作の手順を示すフローチャート。
【図２２】アドレス変換テーブルキャッシュタグが各キャッシュラインに対応するビットマップカウンタを含む場合に、第１実施形態のメモリシステムによって実行されるキャッシュライン入れ替え動作の一連の手順を示すフローチャート。
【図２３】第１実施形態のメモリシステムによって管理される、アドレス変換テーブルキャッシュと、タイムスタンプ／ビットマップカウンタ用の共用記憶領域を含むアドレス変換テーブルキャッシュタグとの関係の例を示す図。
【図２４】第１実施形態のメモリシステムによって実行されるタイムスタンプ更新動作の手順を示すフローチャート。
【図２５】アドレス変換テーブルキャッシュタグが各キャッシュラインに対応するタイムスタンプ／ビットマップカウンタ用の共用記憶領域を含む場合に、第１実施形態のメモリシステムによって実行される入れ替え対象キャッシュライン決定動作の手順を示すフローチャート。
【図２６】第２実施形態のメモリシステムによって管理されるアドレス変換テーブルキャッシュとアドレス変換テーブルキャッシュタグとの関係の例を示す図。
【図２７】各キャッシュラインに対応する複数のビットマップフラグと各キャッシュラインに対応するタイムスタンプとを使用することによって第２実施形態のメモリシステムによって実行される入れ替え対象キャッシュライン決定動作の手順を示すフローチャート。
【図２８】各キャッシュラインに対応する複数のビットマップフラグと各キャッシュラインに対応するタイムスタンプとを使用することによって第２実施形態のメモリシステムによって実行される入れ替え対象キャッシュライン決定動作の別の手順を示すフローチャート。
【図２９】第３実施形態のメモリシステムによって管理されるアドレス変換テーブルキャッシュとアドレス変換テーブルキャッシュタグとの関係の例を示す図。
【図３０】各キャッシュラインに対応する複数のビットマップフラグと各キャッシュラインに対応する複数のダーティーフラグとを使用することによって第３実施形態のメモリシステムによって実行される入れ替え対象キャッシュライン決定動作の手順を示すフローチャート。
【図３１】第３実施形態のメモリシステムによって実行されるキャッシュライン入れ替え動作の手順を示すフローチャート。
【図３２】第４実施形態のメモリシステムによって管理されるアドレス変換テーブルキャッシュとアドレス変換テーブルキャッシュタグとの関係の例を示す図。
【図３３】各キャッシュラインに対応する複数のビットマップフラグと各キャッシュラインに対応する複数のダーティーフラグと各キャッシュラインに対応するタイムスタンプとを使用して第４実施形態のメモリシステムによって実行される入れ替え対象キャッシュライン決定動作の手順を示すフローチャート。
【図３４】第５実施形態のメモリシステムを含む情報処理システムの構成例を示すブロック図。
【図３５】第５実施形態のメモリシステムによって管理される、ホストメモリに書き込むべきデータをキャッシュするように構成されたキャッシュの構成を示すブロック図。
【図３６】ホストからのリード要求の受信時に第５実施形態のメモリシステム内のＣＰＵまたはハードウェアアクセラレータ（ＨＷＡ）によって実行される処理の手順を示すフローチャート。
【図３７】アドレス変換テーブルキャッシュからテーブルデータをリードするためのリード要求の受信時に図３３のキャッシュによって実行される動作の手順を示すフローチャート。
【図３８】アドレス変換テーブルキャッシュにテーブルデータを格納するためのライト要求の受信時に図３３のキャッシュによって実行される動作の手順を示すフローチャート。
【図３９】第５実施形態のメモリシステム内のＣＰＵまたはハードウェアアクセラレータ（ＨＷＡ）によって実行される、不揮発性メモリに書き込まれたデータの消失復元用のパリティをホストメモリに書き込む動作の手順を示すフローチャート。
【図４０】ホストメモリ上の優先置換領域へのライトデータが格納されるキャッシュラインに対して置換されやすいユーゼージ情報を割り当てる動作を説明するための図。
【図４１】ホストメモリ上の優先置換領域へのライトデータに対しては対応するキャッシュラインを置換されやすくするユーゼージ情報を割り当てる動作を説明するための図。
【図４２】ホストメモリ上の優先置換領域以外の領域へのライトデータに対しては対応するキャッシュラインを置換されにくくするユーゼージ情報を割り当てる動作を説明するための図。
【図４３】ホストメモリ上の優先置換領域へのライトデータに対しては対応するキャッシュラインを置換されやすくするユーゼージ情報を割り当てる動作を説明するための図。
【図４４】図３５のキャッシュによって実行されるユーゼージ情報更新動作の手順を示すフローチャート。
【図４５】図３５のキャッシュによって実行されるユーゼージ情報更新動作の一連の手順を示すフローチャート。
【発明を実施するための形態】
【０００９】
以下、図面を参照して、実施形態を説明する。  
【００１０】
（第１実施形態）
まず、図１を参照して、第１実施形態に係るメモリシステムを含む情報処理システム１の構成を説明する。
【００１１】
このメモリシステムは、不揮発性メモリにデータをライトし、不揮発性メモリからデータをリードするように構成されたストレージデバイスである。このメモリシステムは、例えば、ＮＡＮＤフラッシュ技術ベースのストレージデバイス３として実現されている。ストレージデバイス３は、ユニバーサル・フラッシュ・ストレージ（ＵＦＳ）デバイスのような組み込みストレージデバイスとして実現されてもよいし、ソリッドステートドライブ（ＳＳＤ）として実現されてもよい。
【００１２】
情報処理システム１は、ホスト（ホストデバイス）２と、ストレージデバイス３とを含む。ホスト２は、パーソナルコンピュータやサーバ、携帯電話、撮像装置であってもよいし、タブレット、スマートフォンなどの携帯端末であってもよいし、ゲーム機器であってもよいし、カーナビゲーションシステムなどの車載端末であってもよい。
【００１３】
ストレージデバイス３は、ホスト２として機能する情報処理装置の外部記憶装置として使用され得る。ストレージデバイス３が組み込みストレージデバイスとして実現されている場合には、ストレージデバイス３は、情報処理装置に内蔵される。ストレージデバイス３がＳＳＤとして実現されている場合には、ストレージデバイス３は、情報処理装置に内蔵されてもよいし、情報処理装置にケーブルまたはネットワークを介して接続されてもよい。
【００１４】
ホスト２とストレージデバイス３とを相互接続するためのインタフェースとしては、ＳＣＳＩ、Ｓｅｒｉａｌ  Ａｔｔａｃｈｅｄ  ＳＣＳＩ（ＳＡＳ）、ＡＴＡ、Ｓｅｒｉａｌ  ＡＴＡ（ＳＡＴＡ）、ＰＣＩ  Ｅｘｐｒｅｓｓ（ＰＣＩｅ）（登録商標）、Ｅｔｈｅｒｎｅｔ（登録商標）、Ｆｉｂｒｅ  ｃｈａｎｎｅｌ、ＮＶＭ  Ｅｘｐｒｅｓｓ（ＮＶＭｅ）（登録商標）、ユニバーサルシリアルバス（ＵＳＢ）、Ｍｏｂｉｌｅ  Ｉｎｄｕｓｔｒｙ  Ｐｒｏｃｅｓｓｏｒ  Ｉｎｔｅｒｆａｃｅ（ＭＩＰＩ）、ＵｎｉＰｒｏ等を使用し得る。
【００１５】
ストレージデバイス３は、コントローラ４および不揮発性メモリ（ＮＡＮＤ型フラッシュメモリ）５を備える。ＮＡＮＤ型フラッシュメモリ５は、限定されないが、複数のＮＡＮＤ型フラッシュメモリチップを含んでいてもよい。コントローラ４は、ＮＡＮＤ型フラッシュメモリ５に電気的に接続され、ＮＡＮＤ型フラッシュメモリ５を制御するように構成されたメモリコントローラとして動作する。このコントローラ４は、Ｓｙｓｔｅｍ−ｏｎ−ａ−ｃｈｉｐ（ＳｏＣ）のような回路によって実現されてもよい。
【００１６】
ＮＡＮＤ型フラッシュメモリ５は、ユーザデータ６と、論理物理アドレス変換テーブル（ｌｏｇｉｃａｌ−ｔｏ−ｐｈｙｓｉｃａｌ  ａｄｄｒｅｓｓ  ｔｒａｎｓｌａｔｉｏｎ  ｔａｂｌｅ（Ｌ２Ｐテーブル））７のような管理情報とを格納する。論理物理アドレス変換テーブル７は、以下、単にアドレス変換テーブル７としても参照される。このアドレス変換テーブル７は、論理アドレスそれぞれとＮＡＮＤ型フラッシュメモリ５の物理アドレスそれぞれとの間のマッピングを管理する。論理アドレスは、ストレージデバイス３の論理空間内の位置をアドレス指定するためにホスト２によって使用されるアドレスである。この論理アドレスとしては、ＬＢＡ（ｌｏｇｉｃａｌ  ｂｌｏｃｋ  ａｄｄｒｅｓｓ（ａｄｄｒｅｓｓｉｎｇ））が使用され得る。物理アドレスは、データが格納されているＮＡＮＤ型フラッシュメモリ５内の物理記憶位置を示す。アドレス変換テーブル７は、論理アドレスを、この論理アドレスに対応するデータが格納されているＮＡＮＤ型フラッシュメモリ５内の物理記憶位置を示す物理アドレスに変換するために使用される。
【００１７】
ＮＡＮＤ型フラッシュメモリ５は、メモリセルアレイを有する１以上のＮＡＮＤ型フラッシュメモリチップを有する。メモリセルアレイは、マトリクス状に配列された複数のメモリセルを有する。ＮＡＮＤ型フラッシュメモリ５のメモリセルアレイは、図２に示されているように、複数のブロック（物理ブロック）Ｂ０〜Ｂｊ−１を含む。ブロックＢ０〜Ｂｊ−１は、消去動作の単位として機能する。
【００１８】
ブロックＢ０〜Ｂｊ−１は複数のページ（物理ページ）を含む。つまり、ブロックＢ０〜Ｂｊ−１の各々は、ページＰ０、Ｐ１、…Ｐｋ−１を含む。各ページは、同一ワード線に接続された複数のメモリセルを含む。ＮＡＮＤ型フラッシュメモリ５においては、データのリードおよびデータのライトはページ単位で実行される。
【００１９】
図１において、コントローラ４は、ＮＡＮＤ型フラッシュメモリ５のデータ管理とＮＡＮＤ型フラッシュメモリ５のブロック管理とを実行するように構成されたフラッシュトランスレーション層（ＦＴＬ）として機能し得る。
【００２０】
データ管理には、（１）論理アドレスそれぞれと物理アドレスそれぞれとの間の対応関係を示すマッピング情報の管理、（２）ページ単位のリード／ライトとブロック単位の消去動作とを隠蔽するための処理、等が含まれる。論理アドレスと物理アドレスとの間のマッピングの管理は、アドレス変換テーブル７を用いて実行される。コントローラ４は、アドレス変換テーブル７を使用して、論理アドレスそれぞれと物理アドレスそれぞれとの間のマッピングを所定の管理サイズ単位で管理する。ある論理アドレスに対応する物理アドレスは、この論理アドレスのデータがライトされたＮＡＮＤ型フラッシュメモリ５内の最新の物理記憶位置を示す。
【００２１】
ページへのデータ書き込みは、１消去サイクル当たり１回のみ可能である。このため、コントローラ４は、ある論理アドレスに対応する更新データを、この論理アドレスに対応する以前のデータが格納されている物理記憶位置ではなく、別の物理記憶位置に書き込む。そして、コントローラ４は、アドレス変換テーブル７を更新してこの論理アドレスをこの別の物理記憶位置に関連付けると共に、以前のデータを無効化する。
【００２２】
ブロック管理には、不良ブロック（バッドブロック）の管理と、ウェアレベリングと、ガベージコレクション等が含まれる。ウェアレベリングは、ブロックそれぞれの消耗を均一化するための動作である。
【００２３】
ガベージコレクションは、データを書き込むことが可能なフリーブロックの個数を増やすための動作である。ガベージコレクションにおいては、コントローラ４は、有効データと無効データとが混在する幾つかのブロック内の有効データを別のブロック（例えばフリーブロック）にコピーする。ここで、有効データとは、ある論理アドレスに関連付けられているデータを意味する。例えば、アドレス変換テーブル７から参照されているデータ(すなわち論理アドレスから最新のデータとして紐付けられているデータ)は有効データであり、後にホスト２からリードされる可能性がある。無効データとは、どの論理アドレスにも関連付けられていないデータを意味する。どの論理アドレスにも関連付けられていないデータは、もはやホスト２からリードされる可能性が無いデータである。そして、コントローラ４は、アドレス変換テーブル７を更新して、コピーされた有効データの論理アドレスそれぞれをコピー先の物理アドレスにマッピングする。有効データが別のブロックにコピーされることによって無効データのみになったブロックはフリーブロックとして解放される。これによって、このブロックは、このブロックに対する消去動作が実行された後に再利用することが可能となる。
【００２４】
ホスト２は、ストレージデバイス３に様々なコマンドを送出する。これらコマンドには、リードコマンド、ライトコマンド、アンマップコマンド、等が含まれる。リードコマンドは、ストレージデバイス３に対してデータのリードを要求するコマンドである。リードコマンドは、リードすべきデータに対応する論理アドレス（開始ＬＢＡ）と、リードすべきデータの長さとを含む。
【００２５】
コントローラ４がホスト２からリードコマンドを受信した時、コントローラ４は、アドレス変換テーブル７を参照して、リードコマンド内の開始ＬＢＡに対応する物理アドレスを得る。コントローラ４は、この得られた物理アドレスに対応するＮＡＮＤ型フラッシュメモリ５の物理記憶位置からデータをリードし、リードしたデータをホスト２に返す。
【００２６】
ライトコマンドは、ストレージデバイス３に対してデータの書き込みを要求するコマンドである。ライトコマンドは、ライトデータ（つまり書き込むべきデータ）の論理アドレス（開始ＬＢＡ）と、ライトデータの長さとを含む。コントローラ４は、ライトデータを、ＮＡＮＤ型フラッシュメモリ５内の利用可能な物理記憶位置に書き込む。さらに、コントローラ４は、アドレス変換テーブル７を更新することによって、ライトデータが書き込まれた物理記憶位置に対応する物理アドレスを、このライトデータに対応する論理アドレスにマッピングする。
【００２７】
例えば、あるＬＢＡ（ｘ）に対応するデータがＮＡＮＤ型フラッシュメモリ５内の物理アドレス（ｙ）にライトされた場合には、コントローラ４は、アドレス変換テーブル７を更新するためにリード・モディファイド・ライトを実行してもよい。
【００２８】
このリード・モディファイド・ライトでは、コントローラ４は、まず、ＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７から、ＬＢＡ（ｘ）に対応する現在の物理アドレスを含むテーブルデータをリードしてもよい。このテーブルデータは、所定サイズを有するデータ集合であり、連続する論理アドレスに対応する複数の物理アドレスを含んでいてもよい。
【００２９】
コントローラ４は、このリードされたテーブルデータ内の一部を更新する。このテーブルデータの更新では、コントローラ４は、このテーブルデータの一部分、つまりＬＢＡ（ｘ）に対応する現在の物理アドレスを、物理アドレス（ｙ）に更新する。例えば、物理アドレスが３２ビット（４バイト）のサイズで、テーブルデータが５１２バイトのサイズであるケースでは、コントローラ４は、サイズが５１２バイトのテーブルデータの内の４バイトだけを更新する。そして、コントローラ４は、更新されたテーブルデータをＮＡＮＤ型フラッシュメモリ５にライトしてアドレス変換テーブル７を更新する。
【００３０】
コントローラ４は、ホスト２のメインメモリ２２の記憶領域の一部を、ストレージデバイス３用の記憶領域として使用することができる。例えば、コントローラ４は、メインメモリ２２の記憶領域の一部を、コントローラ４によって使用されるデータ（ユーザデータまたは管理情報）の一部を格納するためのキャッシュとして使用してもよい。
【００３１】
ホスト２のメインメモリ２２は、ＤＲＡＭのようなランダムアクセスメモリである。メインメモリ２２は、ホスト使用領域２２Ａと、デバイス使用領域２２Ｂとを含む。ホスト使用領域２２Ａには、ホスト２によって実行されるべきオペレーティングシステム（ＯＳ）やユーザプログラムがロードされる。デバイス使用領域２２Ｂは、ストレージデバイス３に専用の記憶領域として使用される。ここでは、デバイス使用領域２２Ｂに格納（キャッシュ）されるデータの一例として、アドレス変換テーブル７を取り上げる。この場合、コントローラ４は、アドレス変換テーブル７の少なくとも一部を、アドレス変換テーブルキャッシュ３１としてデバイス使用領域２２Ｂに格納することができる。
【００３２】
デバイス使用領域２２Ｂの容量は、通常、ストレージデバイス３に設けられるデバイス内蔵ＲＡＭよりも遙かに大きい。したがって、ホスト２のデバイス使用領域２２Ｂを使用することにより、大容量のアドレス変換テーブルキャッシュ３１を容易に実現することができる。デバイス使用領域２２Ｂはこれらに限定されないが、例えば、ユニバーサル・フラッシュ・ストレージ（ＵＦＳ）のユニファイドメモリ（ＵＭ）によって実現されてもよいし、ＮＶＭｅのホストメモリバッファ（ＨＭＢ）によって実現されてもよい。
【００３３】
通常、ストレージデバイス３が電源オンされた直後のような初期状態では、アドレス変換テーブルキャッシュ３１は空である。論理物理アドレス変換に使用されたアドレス変換データ（テーブルデータ）だけがアドレス変換テーブルキャッシュ３１にキャッシュされていく。この初期状態の時点で、コントローラ４は、論理物理アドレス変換に使用されることが予想される特定のアドレス変換データ（例えば、特定の論理アドレス範囲に対応するアドレス変換データ）をアドレス変換テーブル７からアドレス変換テーブルキャッシュ３１に転送してもよい。これにより、特定のアドレス変換データを事前にアドレス変換テーブルキャッシュ３１にキャッシュすることができる。
【００３４】
ホスト２によって指定された論理アドレスに対応する物理アドレス（少なくともこの物理アドレスを含むテーブルデータ）がアドレス変換テーブルキャッシュ３１に存在する場合（キャッシュヒット）、コントローラ４は、ＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７をリードする代わりに、ホストメモリ（メインメモリ２２のデバイス使用領域２２Ｂ）内のアドレス変換テーブルキャッシュ３１からこの物理アドレス（テーブルデータ）をリードする。これにより、ホスト２からリードコマンドが受信された時に、またはアドレス変換テーブル７を更新するリード・モディファイド・ライトのために、ＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７をリードする回数を減らすことができるので、ストレージデバイス３の性能を改善することができる。
【００３５】
次に、コントローラ４の構成について説明する。
【００３６】
コントローラ４は、ホストインタフェース１１、ＣＰＵ１２、ＲＡＭ１３、バックエンド部１４、および専用ハードウェア（ＨＷ）１５等を含む。これらホストインタフェース１１、ＣＰＵ１２、ＲＡＭ１３、バックエンド部１４、および専用ハードウェア（ＨＷ）１５は、バス１０を介して相互接続される。
【００３７】
ホストインタフェース１１は、ホスト２からライトコマンド、リードコマンド、等の様々なコマンドを受信する回路として機能する。さらに、ホストインタフェース１１は、デバイス使用領域２２Ｂをライトアクセスするためのコマンド、デバイス使用領域２２Ｂをリードアクセスするためのコマンド等を、ホスト２に送信することができる。
【００３８】
ＣＰＵ１２は、ホストインタフェース１１、バックエンド部１４、および専用ハードウェア（ＨＷ）１５等の動作を制御するように構成されたプロセッサである。ＣＰＵ１２は、図示しないＲＯＭ等に格納されている制御プログラム（ファームウェア：ＦＷ）を実行することによって様々な処理を行う。このＣＰＵ１２は、上述のＦＴＬの処理に加え、ホスト２からの様々なコマンドを処理するためのコマンド処理等を実行する。ＣＰＵ１２の動作は、ＣＰＵ１２によって実行されるファームウェアによって制御される。上述のコマンド処理の一部または全部は、専用ハードウェア１５によって実行してもよい。
【００３９】
ＲＡＭ１３は、ストレージデバイス３内に設けられたデバイス内蔵ＲＡＭである。ＲＡＭ１３は、コントローラ４に内蔵されたスタティックＲＡＭ（ＳＲＡＭ）であってもよい。ＲＡＭ１３は、ＣＰＵ１２の作業エリアとして使用され、ロードされた所定の制御プログラムや各種テーブル等を格納するために使用される。
【００４０】
ストレージデバイス３の性能を改善するための典型的なアプローチの一つには、大容量のデバイス内蔵ＲＡＭを設け、処理に必要な情報をこのデバイス内蔵ＲＡＭ上に置くことである。しかし、このアプローチは、ストレージデバイス３（コントローラ４）のコストアップを招く要因となり得、またコントローラ４の小型化を阻害する要因にもなり得る。
【００４１】
第１実施形態では、コントローラ４はホスト２のデバイス使用領域２２Ｂをコントローラ４の作業メモリ（ここでは、アドレス変換テーブルキャッシュ３１）として利用するので、必要なデバイス内蔵ＲＡＭの容量を少なくすることができる。
【００４２】
第１実施形態では、ＲＡＭ１３は、アドレス変換テーブルキャッシュ３１を管理するためのアドレス変換テーブルキャッシュタグ３２として利用される。
【００４３】
アドレス変換テーブルキャッシュタグ３２は、アドレス変換テーブルキャッシュ３１のキャッシュヒット／ミスの判定等に必要なキャッシュ管理情報を格納する。
【００４４】
アドレス変換テーブルキャッシュタグ３２は、デバイス使用領域２２Ｂ上ではなく、コントローラ４内のＲＡＭ１３上に存在する。したがって、コントローラ４は、デバイス使用領域２２Ｂをアクセスすること無く、アドレス変換テーブルキャッシュ３１のキャッシュヒット／ミスを即座に判定することができる。
【００４５】
通常、アドレス変換テーブル７のサイズは、非常に大きい。典型的には、アドレス変換テーブル７のサイズは、ストレージデバイス３の容量の１０００分の１程度である。
【００４６】
例えば、ストレージデバイス３内のＮＡＮＤ型フラッシュメモリ５の容量が１２８Ｇバイトの場合には、必要なアドレス変換テーブル７のサイズは１２８Ｍバイト程度となる。したがって、アドレス変換テーブルキャッシュ３１のヒット率を高めるためには、大容量のアドレス変換テーブルキャッシュ３１が必要とされる。
【００４７】
デバイス使用領域２２Ｂに大容量のアドレス変換テーブルキャッシュ３１を置く場合においては、アドレス変換テーブルキャッシュ３１用のタグメモリ（アドレス変換テーブルキャッシュタグ３２）に必要とされる容量も増大される。
【００４８】
一般に、キャッシュラインサイズを拡大すれば、少ない容量のタグメモリ（アドレス変換テーブルキャッシュタグ３２）でも大容量のキャッシュを管理することができる。
【００４９】
しかし、キャッシュラインサイズが拡大された場合には、キャッシュミスが発生した時に、ＮＡＮＤ型フラッシュメモリ５からアドレス変換テーブルキャッシュ３１のキャッシュラインにデータを転送するためのキャッシュ・ライン・フィル（キャッシュ・ライン・リフィルとも称される）に膨大な時間がかかってしまう。
【００５０】
第１実施形態では、コントローラ４は、拡大された各キャッシュラインを複数の小さな細分化単位（複数のサブライン）に分割し、且つ、データが転送済みであるか否かをサブライン単位で管理する。この構成は、キャッシュミスが発生した時に、アドレス変換テーブルキャッシュ３１の一つのキャッシュライン全体をフィルするのではなく、この一つのキャッシュラインの一部（１サブライン）だけをフィルすることを可能にする。これにより、キャッシュミスが発生した時に必要となるキャッシュ・ライン・フィルのコスト（キャッシュミスペナルティー）を最小限に抑えることができる。アドレス変換テーブルキャッシュタグ３２の各エントリーは、データが転送済みであるか否かをサブライン単位で管理するために、対応するキャッシュラインに含まれる複数のサブラインに対応する複数のビットマップフラグを含む。ビットマップフラグを含むアドレス変換テーブルキャッシュタグ３２の構成の詳細については図３以降で後述する。
【００５１】
バックエンド部１４は、符号化／復号化部１４１と、ＮＡＮＤインタフェース１４２とを含む。符号化／復号化部１４１は、例えば、エラー訂正コード（ＥＣＣ）エンコーダおよびＥＣＣデコーダとして機能し得る。ＮＡＮＤ型フラッシュメモリ５にデータをライトすべき時、符号化／復号化部１４１は、データ（書き込むべきデータ）をエンコード（ＥＣＣエンコード）することによってこのデータにエラー訂正コード（ＥＣＣ）を冗長コードとして付加する。ＮＡＮＤ型フラッシュメモリ５からデータがリードされた時、符号化／復号化部１４１は、リードされたデータに付加されたＥＣＣを使用して、このデータのエラー訂正を行う（ＥＣＣデコード）。
【００５２】
ＮＡＮＤインタフェース１４２は、ＮＡＮＤ型フラッシュメモリ５を制御するように構成されたＮＡＮＤコントローラとして機能する。
【００５３】
専用ハードウェア１５は、アドレス変換テーブルキャッシュタグ３２を制御するように構成されたキャッシュタグ制御ロジック１５１を含んでいてもよい。キャッシュタグ制御ロジック１５１は、キャッシュヒット／ミスを判定する動作、アドレス変換テーブルキャッシュタグ３２に保持されるタグのようなキャッシュ制御情報を更新する動作等を実行する構成された回路を含んでいてもよい。
【００５４】
次に、ホスト２の構成について説明する。
【００５５】
ホスト２は、ＣＰＵ（ホストＣＰＵ）２１、メインメモリ２２、ホストコントローラ２３等を含む。これらＣＰＵ２１、メインメモリ２２、ホストコントローラ２３は、バス２０を介して相互接続される。
【００５６】
ＣＰＵ２１は、ホスト２内のコンポーネントを制御するプロセッサである。ＣＰＵ２１は、ストレージデバイス３または他のストレージデバイスからメインメモリ２２にロードされる様々なプログラムを実行する。これらプログラムには、オペレーティングシステム、ファイルシステム、および各種アプリケーションプログラムが含まれる。
【００５７】
ホストコントローラ２３は、ストレージデバイス３とインタフェースするように構成されたコントローラである。ファイルシステム、デバイスドライバといったホストソフトウェアの制御の下、ホストコントローラ２３は、ライトコマンドおよびリードコマンド等をストレージデバイス３に送出する。また、ホストコントローラ２３は、デバイス使用領域２２Ｂへのデータのライトを要求するデバイス使用領域ライト要求、およびデバイス使用領域２２Ｂからのデータのリードを要求するデバイス使用領域リード要求を、ストレージデバイス３から受信する。
【００５８】
図３は、ストレージデバイス３によって管理される、アドレス変換テーブルキャッシュ３１とアドレス変換テーブルキャッシュタグ３２との関係を示す。
【００５９】
アドレス変換テーブルキャッシュ３１は、複数（ｍ個）のエントリー、つまり複数のキャッシュラインＬ０〜Ｌｍ−１を含む。キャッシュラインＬ０〜Ｌｍ−１の各々は、複数のサブラインＳＬ０〜ＳＬｎ−１を含む。サブラインＳＬ０〜ＳＬｎ−１の各々は、所定サイズのテーブルデータを格納してもよい。この所定サイズのテーブルデータは、連続する複数の論理アドレスに対応する複数の物理アドレスを含んでいてもよい。
【００６０】
例えば、一つの物理アドレスのビット幅が３２ビット（４バイト）で、一つのサブラインのサイズが５１２バイトである場合には、一つのサブライン当たりに１２８個の物理アドレスを含むテーブルデータが格納される。一般に、ＮＡＮＤ型フラッシュメモリ５に対するアクセスは空間的局所性を有するので、複数のサブラインを有し、連続する複数の論理アドレスに対応する複数の物理アドレスを各々のサブラインが格納可能なキャッシュライン構成は、アドレス変換テーブルキャッシュ３１のヒット率を高めることを可能にする。
【００６１】
キャッシュラインＬ０〜Ｌｍ−１の各々のサイズ（キャッシュラインサイズ）は、一つのサブラインのみを含むキャッシュラインのｎ倍である。ｎ倍に拡大されたキャッシュラインを有するアドレス変換テーブルキャッシュ３１のキャッシュ構成は、必要なキャッシュラインの数（ｍ）を、１／ｎに削減することを可能にする。このことは、個々のキャッシュラインにアドレス変換テーブル７のどの領域の内容がキャッシュされているかを示すために必要なタグ（キャッシュタグ）の数を、１／ｎに削減できることを意味する。なお、このキャッシュ構成においては、複数のサブラインそれぞれに対応する複数のビットマップフラグを追加することが必要になるが、これらビットマップフラグを格納するために必要な容量はサブラインあたり1bitである。したがって、このキャッシュ構成は、各サブラインがタグを持つ構成よりも、容量が少なくて済む。
【００６２】
アドレス変換テーブル７とアドレス変換テーブルキャッシュ３１との間のマッピングにおいては、アドレス変換テーブル７は、アドレス変換テーブルキャッシュ３１のキャッシュラインサイズ（サブラインサイズ×ｎ）と同じサイズを各々が有する複数のライン（複数の領域）に論理的に分割されてもよい。アドレス変換テーブル７内の複数の領域内のｍ個の領域の内容が、アドレス変換テーブルキャッシュ３１にキャッシュされる。
【００６３】
アドレス変換テーブルキャッシュ３１は、セットアソシアティブ・キャッシュ、フルアソシアティブ・キャッシュのいずれであってよい。以下では、限定されないが、アドレス変換テーブルキャッシュ３１がフルアソシアティブ・キャッシュとして実現されている場合を主として説明する。
【００６４】
アドレス変換テーブルキャッシュタグ３２は、アドレス変換テーブルキャッシュ３１のキャッシュラインＬ０〜Ｌｍ−１に対応するｍ個のエントリーを含む。これらｍ個のエントリーにおいては、キャッシュラインＬ０〜Ｌｍ−１にアドレス変換テーブル７のどの領域の内容が格納されているかを示すｍ個のタグ３２Ａが格納されている。つまり、各タグは、対応するキャッシュラインにアドレス変換テーブル７のどのデータ（テーブルデータ）が格納されているかを示す。ｍ個のタグ３２Ａの各々は、対応するキャッシュラインに格納されているデータ（テーブルデータ）に対応するアドレスを含む。
【００６５】
さらに、アドレス変換テーブルキャッシュタグ３２の各エントリーは、対応するキャッシュラインに含まれる複数（ｎ個）のサブラインＳＬ０〜ＳＬｎ−１にそれぞれ対応する複数のビットマップフラグ（ｎビット）３２Ｂを含む。
【００６６】
各ビットマップフラグ３２Ｂは、対応するサブラインにデータ（テーブルデータ）が転送済みであるか否か、つまり対応するサブラインが有効であるか否かを示す。複数のキャッシュラインの各々に対応する複数のビットマップフラグ３２Ｂを格納するＲＡＭ１３内の記憶領域は、ビットマップメモリとしても参照される。
【００６７】
通常のキャッシュ制御においては、キャッシュライン単位でキャッシュにデータを転送することが必要とされる。
【００６８】
第１実施形態では、アドレス変換テーブルキャッシュタグ３２の各エントリーはタグと複数のビットマップフラグ３２Ｂとを含むので、コントローラ４は、タグと複数のビットマップフラグ３２Ｂとに基づいて、サブライン単位で、キャッシュヒット／ミスを判定することができる。したがって、キャッシュミスが発生した時には、コントローラ４は、変換されるべき論理アドレスに対応する物理アドレスを含むテーブルデータだけをキャッシュラインに転送するという部分的なキャッシュ・ライン・フィル動作（サブライン転送）を実行することができる。つまり、コントローラ４は、キャッシュライン単位ではなく、サブライン単位で、アドレス変換テーブルキャッシュ３１にデータ（テーブルデータ）を転送する。
【００６９】
なお、一つのサブラインに一つの物理アドレスだけを格納する構成が適用されてもよい。
【００７０】
コントローラ４がホスト２からリードコマンドを受信した時、コントローラ４は、アドレス変換テーブルキャッシュタグ３２内のタグとビットマップフラグとを参照することによって、以下のヒット／ミス判定処理を行う。
【００７１】
コントローラ４は、まず、アドレス変換テーブルキャッシュタグ３２を参照して、ホスト２から受信されるリードコマンドによって指定された論理アドレス（例えばＬＢＡ）の上位ビット部を含むタグに関連付けられている目的のキャッシュラインがアドレス変換テーブルキャッシュ３１に存在するか否かを判定する（キャッシュラインヒット／ミス判定）。ここで、目的のキャッシュラインとは、求める物理アドレスを含むテーブルデータの少なくとも一部が格納されているキャッシュラインを意味する。論理アドレスの上位ビット部を含むタグとは、論理アドレスの上位ビット部（タグフィールド）に一致するアドレスを含むタグを意味する。以下では、論理アドレスの上位ビット部を含むタグを、論理アドレスの上位ビット部（タグフィールド）に一致するタグと称する。
【００７２】
さらに、コントローラ４は、目的のキャッシュラインに対応する特定のビットマップフラグを参照して、この論理アドレスに対応する物理アドレスが格納されるべき特定のサブラインにデータ（テーブルデータ）が転送済みであるか否かを判定する（ビットマップヒット／ミス判定）。
【００７３】
ビットマップヒット／ミス判定は、キャッシュラインヒット／ミス判定によって目的のキャッシュラインがアドレス変換テーブルキャッシュ３１に存在することが判定された場合にのみ実行されてもよいし、キャッシュライン判定と同時に実行されてもよい。
【００７４】
アドレス変換テーブルキャッシュ３１がフルアソシアティプ・キャッシュであるならば、コントローラ４は、目的のキャッシュラインを、リードコマンドに含まれる論理アドレスのタグフィールドをアドレス変換テーブルキャッシュタグ３２内の全てのタグ３２Ａと比較することによって探索する。論理アドレスのタグフィールドに一致するタグが探索されたならば、コントローラ４は、このタグに関連付けられたキャッシュラインを、目的のキャッシュラインとして決定する。
【００７５】
一方、アドレス変換テーブルキャッシュ３１がセットアソシアティブ・キャッシュであるならば、コントローラ４は、リードコマンドに含まれる論理アドレスのタグフィールドを、この論理アドレスのインデックス（キャッシュラインインデックス）によって指定される幾つかのタグと比較する。この論理アドレスのタグフィールドがこれら幾つかのタグの内の一つのタグと一致したならば、コントローラ４は、この一つのタグに関連付けられたキャッシュラインを、目的のキャッシュラインとして決定する。
【００７６】
ビットマップヒット／ミス判定では、以下の処理が行われる。
【００７７】
いま、キャッシュラインＬ０が目的のキャッシュラインとして探索された場合を想定する。
【００７８】
この場合、コントローラ４は、この探索されたキャッシュラインＬ０内の特定のサブラインに関連付けられたビットマップフラグを参照して、この特定のサブラインにデータ（テーブルデータ）が転送済みであるか否かを判定する。キャッシュラインＬ０内の特定のサブラインとは、ホスト２から受信されるリードコマンドによって指定された論理アドレスに対応する物理アドレスが格納されるべきサブラインを意味する。このサブラインは、この論理アドレスの値によって特定することができる。
【００７９】
特定のサブラインに関連付けられたビットマップフラグが有効を示す値（例えば“１”）であるならば、コントローラ４は、この論理アドレスに対応する物理アドレスを含むテーブルデータがこのサブラインに転送済みであると判定することができる。一方、特定のサブラインに関連付けられたビットマップフラグが無効を示す値（例えば“０”）であるならば、コントローラ４は、この論理アドレスに対応する物理アドレスを含むテーブルデータがこのサブラインにまだ転送されていないと判定することができる。
【００８０】
例えば、キャッシュラインＬ０内の特定のサブラインがＳＬ２である場合には、コントローラ４は、キャッシュラインＬ０のサブラインＳＬ２に関連付けられたビットマップフラグを参照することによって、求める物理アドレスがキャッシュラインＬ０に存在するか否かを判定することができる。サブラインＳＬ２に関連付けられたビットマップフラグが無効を示す値（例えば“０”）ならば、コントローラ４は、この論理アドレスに対応する物理アドレスを含む１サブライン分のテーブルデータだけを、アドレス変換テーブル７からキャッシュラインＬ０のサブラインＳＬ２にのみ転送する。これにより、キャッシュラインＬ０の特定のサブラインＳＬ２のみがテーブルデータでフィルされる。そして、コントローラ４は、サブラインＳＬ２に関連付けられたビットマップフラグを、有効を示す値（例えば“１”）に更新する。
【００８１】
このようにして、キャッシュラインＬ０は、サブライン単位でリフィルされる。時間の経過に伴って、キャッシュラインＬ０の複数のサブラインがデータ（テーブルデータ）によって徐々に埋められて行く。
【００８２】
図４は、アドレス変換テーブルキャッシュタグ３２の構成例を示す。
【００８３】
ここでは、アドレス変換テーブルキャッシュ３１がフルアソシアティブ・キャッシュとして実現されている場合を想定する。アドレス変換テーブルキャッシュタグ３２が６４個のエントリーを含む場合、つまりアドレス変換テーブルキャッシュ３１のキャッシュラインの数（ｍ）が６４である場合を想定する。
【００８４】
アドレス変換テーブルキャッシュタグ３２の６４個のエントリーは、アドレス変換テーブルキャッシュ３１の６４個のキャッシュラインにそれぞれ対応する。アドレス変換テーブルキャッシュタグ３２の６４個のエントリーの各々は、バリッドビット（ＶＢ）１０１と、タグ１０２と、複数のビットマップフラグを含むビットマップフラグフィールド１０３とを含んでいてもよい。
【００８５】
バリッドビット（ＶＢ）１０１は、対応するキャッシュラインが有効であるか否かを示す。キャッシュラインが有効であるとは、このキャッシュラインがアクティブ状態であること、つまりこのキャッシュラインの少なくとも一つのサブラインにデータ（テーブルデータ）が格納されていることを示す。
【００８６】
ホスト２によってストレージデバイス３をアクセスするために使用される論理アドレスは、３つのフィールド、つまりタグフィールド、サブラインインデックス、およびサブライン内インデックスに分割される。
【００８７】
サブライン内インデックスは、一つのサブラインに含まれる複数の物理アドレスの一つを特定する。つまり、サブライン内インデックスは、同じサブライン内に格納された複数の物理アドレスの一つを選択（指定）するために使用される。論理アドレスの下位ビット部がこのサブライン内インデックスとして使用される。サブライン内インデックスのビットの数（ビット幅）は、一つのサブラインに含まれる物理アドレスの数に応じて決定される。例えば、サブラインサイズが５１２バイトで、物理アドレスが３２ビット幅である場合、各サブラインには、連続する１２８個の論理アドレスに対応する１２８個の物理アドレス（ＰＡ０〜ＰＡ１２７）が格納されるので、サブライン内インデックスのビットの数（ビット幅）は７ビットとなる。
【００８８】
サブラインインデックスは、一つのキャッシュラインに含まれるｎ個のサブラインの一つを特定する。つまり、サブラインインデックスは、同じキャッシュライン内に格納されたｎ個のサブラインの一つを選択（指定）するために使用される。例えば、キャッシュラインを、５１２個のサブラインを含むキャッシュラインサイズに拡大する場合には、サブラインインデックスのビットの数（ビット幅）は９ビットに設定される。この場合、各エントリーのビットマップフラグフィールド１０３は、５１２個のサブラインに対応する５１２個のビットマップフラグ（ｂ０〜ｂ５１１）を含む。論理アドレスの下位ビット部よりも上位側のビット部がサブラインインデックスとして使用される。
【００８９】
ビットマップフラグフィールド１０３を参照する場合においては、５１２個のビットマップフラグから、論理アドレスのサブラインインデックスによって特定される一つのビットマップフラグが選択される。
【００９０】
サブラインインデックスとサブライン内インデックスとを除いた残りの上位ビット部（１６ビット）がタグフィールドとして使用される。この場合、アドレス変換テーブルキャッシュタグ３２の各エントリーのタグ１０２には、論理アドレスの上位ビット部（１６ビット）が格納される。
【００９１】
図５は、アドレス変換テーブルキャッシュ３１がセットアソシアティブキャッシュである場合に対応するアドレス変換テーブルキャッシュタグ３２の構成例を示す。
【００９２】
ここでは、一例として、アドレス変換テーブルキャッシュ３１が２ウェイ・セットアソシアティブキャッシュである場合が想定されている。
【００９３】
アドレス変換テーブルキャッシュタグ３２の６４個のエントリーは、アドレス変換テーブルキャッシュ３１の６４個のキャッシュラインにそれぞれ対応する。６４個のエントリーは、Ｉｎｄｅｘ０〜３１のｗａｙ０／１（２ｗａｙ）に分割されている。ラインインデックスがＩｎｄｅｘと一致する２本のｗａｙの各々について、そのｗａｙに対応するエントリのタグとタグフィールドとが比較され、これによってキャッシュラインヒット／ミスが判定される。
【００９４】
サブラインインデックスよりも上位側の５ビットが３２個のインデックス（Ｉｎｄｅｘ０〜３１）を識別するためのラインインデックスとして使用されるので、タグフィールドは１１ビットとなる。
【００９５】
図６は、図４または図５のアドレス変換テーブルキャッシュタグ３２に対応するアドレス変換テーブルキャッシュ３１の構成を示す。
【００９６】
アドレス変換テーブルキャッシュ３１は、６４個のキャッシュラインＬ０〜Ｌ６３を含む。キャッシュラインＬ０〜Ｌ６３の各々は、５１２個のサブラインＳＬ０〜ＳＬ５１１を含む。アドレス変換テーブル７の各ライン（各領域）は、６４個のキャッシュラインＬ０〜Ｌ６３のいずれかに格納される。なお、アドレス変換テーブルキャッシュ３１が２ウェイ・セットアソシアティブキャッシュである場合には、６４本のキャッシュラインはＩｎｄｅｘ０〜３１のｗａｙ０／１（２ｗａｙ）に分割される。
【００９７】
図７は、データリード動作において、キャッシュヒットの場合にコントローラ４によって実行されるキャッシュ制御処理の処理シーケンスを示す。
【００９８】
ホストＣＰＵ２１は、リードコマンドを、ホストコントローラ２３を介してストレージデバイス３のコントローラ４に送出する（ステップＳ３０１、Ｓ３０２）。コントローラ４がホスト２からのリードコマンドを受信した時、コントローラ４は、アドレス変換テーブルキャッシュタグ３２を参照し（ステップＳ３０３）、この参照結果に基づいて、アドレス変換テーブルキャッシュ３１が、キャッシュヒット、キャッシュラインヒット（ビットマップミスとも云う）、キャッシュミスのいずれの状態であるかを判定する（ステップＳ３０４）。
【００９９】
キャッシュヒットとは、リードコマンド内の論理アドレスの上位ビット部に一致するタグに関連付けられているキャッシュラインが存在し、且つこの論理アドレスに対応する物理アドレスが格納されるべきサブラインにデータ（テーブルデータ）が転送済みである状態である。つまり、求める物理アドレスを含むアドレス変換テーブル７の領域がキャッシュラインにキャッシュされており、且つ求める物理アドレスが格納されるべきサブラインに、求める物理アドレスを含むテーブルデータが転送済みである状態がキャッシュヒットである。
【０１００】
キャッシュラインヒット（ビットマップミス）とは、リードコマンドの論理アドレスの上位ビット部に一致するタグに関連付けられているキャッシュラインが存在するものの、この論理アドレスに対応する物理アドレスが格納されるべきサブラインにデータ（テーブルデータ）がまだ転送されていない状態である。
【０１０１】
キャッシュミスとは、リードコマンドの論理アドレスの上位ビット部に一致するタグに関連付けられているキャッシュラインがアドレス変換テーブルキャッシュ３１に存在しない状態を意味する。
【０１０２】
キャッシュヒットの場合、コントローラ４は、この論理アドレスに対応する物理アドレスを含む１サブライン分のテーブルデータを、ホストコントローラ２３を介して、デバイス使用領域２２Ｂ上のアドレス変換テーブルキャッシュ３１からリードする（ステップＳ３０５，Ｓ３０６）。そして、コントローラ４は、アドレス変換テーブルキャッシュ３１からリードされたテーブルデータから、この論理アドレスのサブライン内インデックスの値によって特定される物理アドレスを抽出する。コントローラ４は、この物理アドレスを使用してＮＡＮＤ型フラッシュメモリ５をリードアクセスして、リードコマンド内の論理アドレスによって指定されるユーザデータをＮＡＮＤ型フラッシュメモリ５からリードする（ステップＳ３０７、Ｓ３０８）。コントローラ４は、ユーザデータをホストコントローラ２３を介してホストＣＰＵ２１に送出する（ステップＳ３０９、Ｓ３１０）。
【０１０３】
図８は、データリード動作において、キャッシュラインヒット（ビットマップミス）の場合にコントローラ４によって実行されるキャッシュ制御処理の処理シーケンスを示す。
【０１０４】
ホストＣＰＵ２１は、リードコマンドを、ホストコントローラ２３を介してストレージデバイス３のコントローラ４に送出する（ステップＳ４０１、Ｓ４０２）。コントローラ４がホスト２からのリードコマンドを受信した時、コントローラ４は、アドレス変換テーブルキャッシュタグ３２を参照し（ステップＳ４０３）、この参照結果に基づいて、アドレス変換テーブルキャッシュ３１が、キャッシュヒット、キャッシュラインヒット（ビットマップミスとも云う）、キャッシュミスのいずれの状態であるかを判定する（ステップＳ４０４）。
【０１０５】
キャッシュラインヒット（ビットマップミス）の場合、コントローラ４は、この論理アドレスに対応する物理アドレスを含む１サブライン分のテーブルデータをＮＡＮＤ型フラッシュメモリ５内のアドレス変換テーブル７からリードする（ステップＳ４０５、Ｓ４０６）。そして、コントローラ４は、このテーブルデータを、キャッシュラインヒットしたキャッシュライン内の特定のサブラインに転送する（ステップＳ４０７）。この特定のサブラインは、このサブラインのサブラインインデックスの値によって特定される。
【０１０６】
コントローラ４は、キャッシュラインヒットしたキャッシュライン内の特定のサブラインに関連付けられたビットマップフラグを有効を示す値（例えば“１”）に更新する（ステップＳ４０８）。
【０１０７】
コントローラ４は、アドレス変換テーブル７からリードされたテーブルデータから、この論理アドレスのサブライン内インデックスの値によって特定される物理アドレスを抽出する。コントローラ４は、この物理アドレスを使用してＮＡＮＤ型フラッシュメモリ５をリードアクセスして、リードコマンド内の論理アドレスによって指定されるユーザデータをＮＡＮＤ型フラッシュメモリ５からリードする（ステップＳ４０９、Ｓ４１０）。コントローラ４は、このユーザデータをホストコントローラ２３を介してホストＣＰＵ２１に送出する（ステップＳ４１１、Ｓ４１２）。
【０１０８】
図９は、キャッシュラインヒット（ビットマップミス）時に実行されるサブライン転送動作およびビットマップフラグ更新動作を示す。
【０１０９】
図９において、キャッシュラインにおいては、ハッチングされている部分はテーブルデータが転送済みのサブラインを表し、ハッチングされていない部分はテーブルデータがまだ転送されていないサブラインを表している。テーブルデータが転送済みのサブラインは、「転送済みサブライン」としても参照される。ビットマップフラグフィールド（ｂ０−ｂ５１１）においては、ハッチングされている部分は、有効を示す値（例えば“１”）に新たに更新されたビットマップフラグを表している。
【０１１０】
図９では、リードコマンド内の論理アドレス（例えばＬＢＡ）に対応するアドレス変換テーブル７内の特定のラインがキャッシュラインＬ１にマッピングされており、且つキャッシュラインＬ１のサブラインＳＬ０（ハッチングされている部分）のみが転送済みサブラインである場合が想定されている。コントローラ４は、アドレス変換テーブルキャッシュタグ３２を参照して、リードコマンド内の論理アドレスのタグフィールドと一致するタグを見つけ、これによってキャッシュラインＬ１を、リードコマンドの論理アドレスに対応する特定のラインの一部を格納しているキャッシュラインとして特定する。リードコマンドの論理アドレスに対応する物理アドレスを含むテーブルデータが格納されるべきサブラインＳＬ２には、テーブルデータは転送されていない。この場合、キャッシュラインＬ１のサブラインＳＬ２に対応するビットマップフラグ（ｂ２）は無効を示す値（例えば“０”）に設定されている。したがって、コントローラ４は、キャッシュラインＬ１のサブラインＳＬ２に対応するビットマップフラグ（ｂ２）を参照することによって、キャッシュラインヒット（ビットマップミス）であると判定することができる。
【０１１１】
コントローラ４は、リードコマンドの論理アドレスに対応する物理アドレスを含む１サブライン分のテーブルデータをＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７からリードして、このテーブルデータのみをキャッシュラインＬ１のサブラインＳＬ２に転送する。そして、コントローラ４は、キャッシュラインＬ１のサブラインＳＬ２に対応するビットマップフラグ（ｂ２）を無効を示す値（例えば“０”）から有効を示す値（例えば“１”）に更新する。
【０１１２】
図１０は、データリード動作において、キャッシュミスの場合にコントローラ４によって実行されるキャッシュ制御処理の処理シーケンスを示す。
【０１１３】
ホストＣＰＵ２１は、リードコマンドを、ホストコントローラ２３を介してストレージデバイス３のコントローラ４に送出する（ステップＳ５０１、Ｓ５０２）。コントローラ４がホスト２からのリードコマンドを受信した時、コントローラ４は、アドレス変換テーブルキャッシュタグ３２を参照し（ステップＳ５０３）、この参照結果に基づいて、アドレス変換テーブルキャッシュ３１が、キャッシュヒット、キャッシュラインヒット（ビットマップミスとも云う）、キャッシュミスのいずれの状態であるかを判定する（ステップＳ５０４）。
【０１１４】
キャッシュミスの場合、コントローラ４は、この論理アドレスに対応する物理アドレスを含む１サブライン分のテーブルデータをＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７からリードする（ステップＳ５０５、Ｓ５０６）。入れ替え対象となり得る全てのキャッシュライン（全ての入れ替え対象キャッシュライン候補）が使用中である場合、つまりどのテーブルデータも格納されていない未使用のキャッシュラインがこれら入れ替え対象キャッシュライン候補内に存在しない場合、コントローラ４は、これらキャッシュラインから入れ替え対象キャッシュラインを決定する。入れ替え対象キャッシュラインとは、リプレースすべきキャッシュライン、つまりアドレス変換テーブルキャッシュ３１から追い出すべきキャッシュラインを意味する。もしアドレス変換テーブルキャッシュ３１がフルアソシアティブ・キャッシュである場合には、アドレス変換テーブルキャッシュ３１内の全てのキャッシュラインが入れ替え対象キャッシュライン候補となる。一方、アドレス変換テーブルキャッシュ３１がｎウェイ・セット・アソシアティブキャッシュ（ｎ＞１）である場合には、この論理アドレスによって定められるある特定のセットに対応するｎ個のウェイが入れ替え対象キャッシュライン候補となる。
【０１１５】
コントローラ４は、入れ替え対象キャッシュラインに決定されたキャッシュラインをアドレス変換テーブルキャッシュ３１から追い出す。つまり、コントローラ４は、入れ替え対象キャッシュラインに決定されたキャッシュラインに対応するアドレス変換テーブルキャッシュタグ３２のエントリーを更新することによって、入れ替え対象キャッシュラインを無効化する（ステップＳ５０７）。この場合、入れ替え対象キャッシュライン内の全てのサブラインが無効化される。
【０１１６】
コントローラ４は、アドレス変換テーブル７からリードされた１サブライン分のテーブルデータのみを、アドレス変換テーブルキャッシュ３１内の入れ替え対象キャッシュラインの特定のサブラインに転送する（ステップＳ５０８）。
【０１１７】
コントローラ４は、入れ替え対象キャッシュラインに対応するアドレス変換テーブルキャッシュタグ３２のエントリーを更新することによって、この入れ替え対象キャッシュラインを有効化するための有効化処理を行う（ステップＳ５０９）。
【０１１８】
コントローラ４は、アドレス変換テーブル７からリードされたテーブルデータから、この論理アドレスのサブライン内インデックスの値によって特定される物理アドレスを抽出する。コントローラ４は、この物理アドレスを使用してＮＡＮＤ型フラッシュメモリ５をリードアクセスして、リードコマンド内の論理アドレスによって指定されるユーザデータをＮＡＮＤ型フラッシュメモリ５からリードする（ステップＳ５１０、Ｓ５１１）。コントローラ４は、このユーザデータをホストコントローラ２３を介してホストＣＰＵ２１に送出する（ステップＳ５１２、Ｓ５１３）。
【０１１９】
図１１は、キャッシュミス時に実行されるキャッシュライン無効化動作、サブライン転送動作およびキャッシュライン有効化動作を示す。
【０１２０】
図１１において、キャッシュラインにおいては、ハッチングされている部分はデータ（テーブルデータ）が転送済みのサブラインを表し、ハッチングされていない部分はデータ（テーブルデータ）がまだ転送されていないサブラインを表している。アドレス変換テーブルキャッシュタグ３２のエントリー（バリッドビットＶＢ、タグ、ビットマップフィールド）においては、ハッチングされている部分は、新たに更新された部分を表している。
【０１２１】
リードコマンド内の論理アドレスのタグフィールドと一致するタグがアドレス変換テーブルキャッシュタグ３２に存在しない場合、コントローラ４は、キャッシュミスの発生を検出する。コントローラ４は、リプレースすべきキャッシュライン（入れ替え対象キャッシュライン）を決定する。ここでは、キャッシュラインＬ２が入れ替え対象キャッシュラインに決定された場合を想定する。
【０１２２】
コントローラ４は、まず、キャッシュラインＬ２を無効化してもよい。この場合、コントローラ４は、キャッシュラインＬ２に対応するバリッドビットを無効を示す値（例えば“０”）に更新し、さらに、キャッシュラインＬ２に対応する全てのビットマップフラグを無効を示す値（例えば“０”）にクリアする。
【０１２３】
コントローラ４は、リードコマンド内の論理アドレスに対応する１サブライン分のテーブルデータをアドレス変換テーブル７からリードして、このテーブルデータを、このテーブルデータが格納されるべきキャッシュラインＬ２の特定のサブライン（例えばサブラインＳＬ５１１）に転送する。そして、コントローラ４は、キャッシュラインＬ２を有効化する。この場合、コントローラ４は、リードコマンド内の論理アドレスのタグフィールドの値を、キャッシュラインＬ２に対応するタグとしてアドレス変換テーブルキャッシュタグ３２にライトする。さらに、コントローラ４は、キャッシュラインＬ２のサブラインＳＬ５１１に関連付けられたビットマップフラグを有効を示す値（例えば“１”）に更新し、またキャッシュラインＬ２に対応するバリッドビットを有効を示す値（例えば“１”）に更新する。
【０１２４】
なお、アドレス変換テーブルキャッシュ３１は必ずしもホストメモリ上に存在しなくてもよく、アドレス変換テーブルキャッシュ３１は、図１２に示されているようにコントローラ４内のＲＡＭ（ＳＲＡＭ）１３上にアドレス変換テーブルキャッシュタグ３２と一緒に存在してもよいし、図１３に示されているように、コントローラ４の外部に設けられたダイナミックＲＡＭ（ＤＲＡＭ）１７上にアドレス変換テーブルキャッシュタグ３２と一緒に存在してもよい。図１３の構成においては、コントローラ４は、ＤＲＡＭ１７を制御するように構成された回路であるＤＲＡＭインタフェース１６を含む。
【０１２５】
次に、第１実施形態における入れ替え対象キャッシュライン決定動作について説明する。
【０１２６】
上述したように、キャッシュミスによってキャッシュラインの入れ替え（追い出し）が必要になった場合、コントローラ４は、アドレス変換テーブルキャッシュ３１の入れ替え対象キャッシュラインを決定する。
【０１２７】
入れ替え対象キャッシュラインを決定するための入れ替えポリシーとしては、最も最近使用されていないキャッシュラインを追い出すＬＲＵ（least recently used）ポリシーが知られている。
【０１２８】
しかし、このＬＲＵポリシーを使用すると、多数の転送済みサブラインが一度にまとめて無効化される場合がある。
【０１２９】
例えば、図３に示されているように、キャッシュラインＬ０が多くの転送済みサブラインを含み、キャッシュラインＬ１、Ｌ２が一つの転送済みサブラインだけを含む場合を想定する。もしキャッシュラインＬ１、Ｌ２が比較的最近使用されたならば、キャッシュラインＬ０が最も最近使用されていないキャッシュラインとなり、多くの転送済みサブラインを含むこのキャッシュラインＬ０が入れ替え対象キャッシュラインに決定されてしまう。この場合、このキャッシュラインＬ０内の多数の転送済みサブラインの全てが無効化されて、このキャッシュラインＬ０から追い出されてしまう。この結果、キャッシュヒット率が低下し、ストレージデバイス３の性能が低下する場合がある。
【０１３０】
このように、各キャッシュラインが複数のサブラインを含む構成においては、入れ替え対象キャッシュライン内の全ての転送済みサブラインがアドレス変換テーブルキャッシュ３１から追い出されてしまう。そこで、第１実施形態においては、コントローラ４は、キャッシュミスによって一つのキャッシュラインを入れ替える場合、入れ替え対象となり得るキャッシュラインの中で、テーブルデータが転送済みのサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定する。換言すれば、コントローラ４は、テーブルデータが転送済みのサブラインの数が最も少ないキャッシュラインを無効化して、アドレス変換テーブルキャッシュ３１から追い出す。そして、コントローラ４は、ＮＡＮＤ型フラッシュメモリ５から１サブライン分のテーブルデータをリードし、リードされたテーブルデータを入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送する。
【０１３１】
例えば、図３に示されているように、キャッシュラインＬ０が多くの転送済みサブラインを含み、キャッシュラインＬ１、Ｌ２が一つの転送済みサブラインのみを含む場合を想定する。この場合、コントローラ４は、キャッシュラインＬ１またはＬ２を入れ替え対象キャッシュラインに決定する。
【０１３２】
この結果、転送済みサブラインの数が多いキャッシュラインＬ０をアドレス変換テーブルキャッシュ３１に残すことができる。よって、キャッシュライン入れ替え後においても、アドレス変換テーブルキャッシュ３１が多くの転送済みサブラインを保持しているという状態を維持することができるので、アドレス変換テーブルキャッシュ３１のヒット率の向上を図ることができる。
【０１３３】
図１４のフローチャートは、入れ替え対象キャッシュライン決定動作の手順を示す。
【０１３４】
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ１１）。ステップＳ１１では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０１３５】
キャッシュライン入れ替えが必要であるならば（ステップＳ１１のＹＥＳ）、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインの中から、転送済みサブラインの数が最も少ないキャッシュラインを探す（ステップＳ１２）。
【０１３６】
なお、アドレス変換テーブルキャッシュ３１がフルアソシアティブ・キャッシュである場合には、アドレス変換テーブルキャッシュ３１の全キャッシュラインが入れ替え対象キャッシュライン候補となる。このため、ステップＳ１２では、コントローラ４は、アドレス変換テーブルキャッシュ３１の全キャッシュラインの中から、転送済みサブラインの数が最も少ないキャッシュラインを探す。また、アドレス変換テーブルキャッシュタグ３２の各エントリーは、ロックフラグをさらに有してもよい。この構成においては、ロックフラグに有効を示す値（例えば“１”）が設定されているエントリーに対応するキャッシュラインを、入れ替え対象から除外してもよい。
【０１３７】
ステップＳ１２では、コントローラ４は、入れ替え対象となり得るキャッシュライン間で、転送済みサブラインの数を比較することによって、転送済みサブラインの数が最も少ないキャッシュラインを特定する。
【０１３８】
コントローラ４は、転送済みサブラインの数が最も少ないこのキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ１３）。
【０１３９】
転送済みサブラインの数を特定する方法としては、各キャッシュラインに対応する複数のビットマップフラグをリードする方法が使用されてもよい。
【０１４０】
各ビットマップフラグは１サブラインに対応する。データが未転送のサブラインそれぞれに対応するビットマップフラグそれぞれは、無効を示す値（例えば“０”）に設定されている。コントローラ４は、あるサブラインにテーブルデータを転送したならば、このサブラインに対応するビットマップフラグを有効を示す値（例えば“１”）に設定する。キャッシュライン入れ替えの必要がある場合には、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインの各々に対応する複数のビットマップフラグを参照し、入れ替え対象となり得る全てのキャッシュラインの中から、有効を示す値（例えば“１”）のビットマップフラグの数が最も少ないキャッシュラインを探し、有効を示す値（例えば“１”）のビットマップフラグの数が最も少ないキャッシュラインを入れ替え対象とする。有効を示す値（例えば“１”）のビットマップフラグの数が最も少ないキャッシュラインは、転送済みサブラインの数が最も少ないキャッシュラインである。
【０１４１】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０１４２】
キャッシュライン入れ替えが必要ではないならば（ステップＳ１１のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ１４）。
【０１４３】
図１５のフローチャートは、各キャッシュラインに対応する複数のビットマップフラグを使用した入れ替え対象キャッシュライン決定動作の手順を示す。
【０１４４】
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ２１）。ステップＳ２１では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０１４５】
キャッシュライン入れ替えが必要であるならば（ステップＳ２１のＹＥＳ）、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインの各々に対応する複数のビットマップフラグを参照し、入れ替え対象となり得る全てのキャッシュラインの中から、有効を示す値（例えば“１”）のビットマップフラグの数が最も少ないキャッシュラインを探す（ステップＳ２２）。ステップＳ２２では、コントローラ４は、入れ替え対象となり得るキャッシュライン間で、“１”のビットマップフラグの数を比較することによって、“１”のビットマップフラグの数が最も少ないキャッシュラインを特定する。
【０１４６】
コントローラ４は、有効を示す値（例えば“１”）のビットマップフラグの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ２３）。
【０１４７】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０１４８】
キャッシュライン入れ替えが必要ではないならば（ステップＳ２１のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ２４）。
【０１４９】
図１６のフローチャートは、キャッシュライン入れ替え動作の手順を示す。
【０１５０】
コントローラ４は、入れ替え対象キャッシュラインに対応するバリッドビット（ＶＢ）を無効を示す値（例えば“０”）にして入れ替え対象キャッシュラインを無効化し、さらに、入れ替え対象キャッシュラインに対応する全てのビットマップフラグを無効を示す値（例えば“０”）にクリアして入れ替え対象キャッシュライン内の全てのサブラインを無効化する（ステップＳ３１）。コントローラ４は、ＮＡＮＤ型フラッシュメモリ５内のアドレス変換テーブル７から、求める物理アドレスを含む１サブライン分のテーブルデータをリードし、このリードした１サブライン分のテーブルデータを入れ替え対象キャッシュライン内の特定の一つのサブラインに転送する（ステップＳ３２）。この特定の一つのサブラインは、キャッシュミスが起きる要因となったリードコマンドに含まれる論理アドレスによって定められる。
【０１５１】
そして、コントローラ４は、入れ替え対象キャッシュラインに対応するタグの内容をリードコマンドに含まれる論理アドレス内のタグフィールドに更新する動作、入れ替え対象キャッシュライン内の特定のサブライン（テーブルデータが転送されたサブライン）に対応するビットマップフラグを有効を示す値（例えば“１”）に更新する動作、および入れ替え対象キャッシュラインに対応するバリッドビット（ＶＢ）を有効を示す値（例えば“１”）に更新する動作を実行する（ステップＳ３３）。
【０１５２】
図１７のフローチャートは、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作の手順を示す。
【０１５３】
コントローラ４は、ＮＡＮＤ型フラッシュメモリ５内のアドレス変換テーブル７から、求める物理アドレスを含む１サブライン分のテーブルデータをリードし、このリードした１サブライン分のテーブルデータを未使用のキャッシュライン内の特定の一つのサブラインに転送する（ステップＳ３２Ａ）。この特定の一つのサブラインは、キャッシュミスが起きる要因となったリードコマンドに含まれる論理アドレスによって定められる。
【０１５４】
そして、コントローラ４は、この未使用のキャッシュラインに対応するタグの内容をリードコマンドに含まれる論理アドレス内のタグフィールドに更新する動作、この未使用のキャッシュライン内の特定のサブライン（テーブルデータが転送されたサブライン）に対応するビットマップフラグを有効を示す値（例えば“１”）に更新する動作、およびこの未使用のキャッシュラインに対応するバリッドビット（ＶＢ）を有効を示す値（例えば“１”）に更新する動作を実行する（ステップＳ３３Ａ）。
【０１５５】
図１８は、ビットマップカウンタを含むアドレス変換テーブルキャッシュタグ３２の構成例を示す。
【０１５６】
図１８のアドレス変換テーブルキャッシュタグ３２の各エントリーは、タグ３２Ａ、複数のビットマップフラグ３２Ｂに加え、ビットマップカウンタ３２Ｃを保持する。
【０１５７】
アドレス変換テーブルキャッシュタグ３２の各エントリーのビットマップカウンタ３２Ｃは、対応するｎビットのビットマップフラグの中に含まれる、有効を示す値（例えば“１”）のビットマップフラグの数を示す。
【０１５８】
ビットマップカウンタ３２Ｃは、有効を示す値（例えば“１”）のビットマップフラグの数を完全に数えられる程度のビット数（ｌｏｇ２［ビットマップフラグのビット数ｎ］）を有していることが望ましいが、それより小さな一定の閾値（上限値）で飽和するカウンタであっても構わない。
【０１５９】
キャッシュライン入れ替えの必要がある場合には、コントローラ４は、入れ替え対象となり得る各キャッシュラインに対応するビットマップカウンタ３２Ｃを参照し、入れ替え対象となり得るキャッシュラインから、ビットマップカウンタ３２Ｃの値が最も小さいキャッシュラインを探し、ビットマップカウンタ３２Ｃの値が最も小さいキャッシュラインを入れ替え対象キャッシュラインに決定する。ビットマップカウンタ３２Ｃの値が最も小さいキャッシュラインは、転送済みサブラインの数が最も少ないキャッシュラインである。
【０１６０】
これにより、入れ替え対象となり得る各キャッシュラインに対応する複数のビットマップフラグをリードするよりも、効率よく入れ替え対象キャッシュラインを決定することができる。
【０１６１】
すなわち、各キャッシュラインに対応する複数のビットマップフラグを使用して入れ替え対象キャッシュラインを決定するケースにおいては、キャッシュライン入れ替えの度に、入れ替え対象となり得る全てのキャッシュラインの各々に対応するビットマップフラグ（キャッシュがフルアソシアティブ・キャッシュである場合は全てのキャッシュラインの各々に対応するビットマップフラグ）を検索する必要が生じる。１キャッシュラインに含まれるサブラインの数が多い場合は、入れ替え対象キャッシュラインを決めるためにリードしなければならないデータ量が増えるため、入れ替え対象キャッシュラインの決定までに時間がかかる場合がある。
【０１６２】
各キャッシュラインに対応するビットマップカウンタ３２Ｃを使用して入れ替え対象キャッシュラインを決定するケースにおいては、入れ替え対象キャッシュラインを決めるためにリードしなければならないデータ量を低減でき、入れ替え対象キャッシュラインの決定に要する時間を短くすることができる。
【０１６３】
図１９は、図１８のアドレス変換テーブルキャッシュタグ３２内の幾つかのビットマップカウンタ３２Ｃの値の例を示す。
【０１６４】
図１９では、図示の簡単化のために、各キャッシュラインが８個のサブラインＳＬ０〜ＳＬ７を含む場合が想定されている。
【０１６５】
キャッシュラインＬ０においては、サブラインＳＬ０、ＳＬ２、ＳＬ４、ＳＬ５が転送済みサブラインである。この場合、キャッシュラインＬ０のサブラインＳＬ０、ＳＬ２、ＳＬ４、ＳＬ５に対応する４個のビットマップフラグ３２Ｂが有効を示す値（例えば“１”）に設定され、キャッシュラインＬ０に対応するビットマップカウンタ３２Ｃの値は４に設定される。
【０１６６】
キャッシュラインＬ１においては、サブラインＳＬ１、ＳＬ２、ＳＬ５、ＳＬ６、ＳＬ７が転送済みサブラインである。この場合、キャッシュラインＬ１のサブラインＳＬ１、ＳＬ２、ＳＬ５、ＳＬ６、ＳＬ７に対応する５個のビットマップフラグ３２Ｂが有効を示す値（例えば“１”）に設定され、キャッシュラインＬ１に対応するビットマップカウンタ３２Ｃの値は５に設定される。
【０１６７】
キャッシュラインＬ２においては、サブラインＳＬ０、ＳＬ１、ＳＬ３、ＳＬ４、ＳＬ６、ＳＬ７が転送済みサブラインである。この場合、キャッシュラインＬ２のサブラインＳＬ０、ＳＬ１、ＳＬ３、ＳＬ４、ＳＬ６、ＳＬ７に対応する６個のビットマップフラグ３２Ｂが有効を示す値（例えば“１”）に設定され、キャッシュラインＬ２に対応するビットマップカウンタ３２Ｃの値は６に設定される。
【０１６８】
図２０のフローチャートは、各キャッシュラインに対応するビットマップカウンタを使用した入れ替え対象キャッシュライン決定動作の手順を示す。
【０１６９】
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ４１）。ステップＳ４１では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０１７０】
キャッシュライン入れ替えが必要であるならば（ステップＳ４１のＹＥＳ）、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインに対応するビットマップカウンタを参照し、入れ替え対象となり得る全てのキャッシュラインの中から、ビットマップカウンタの値が最小のキャッシュラインを探す（ステップＳ４２）。ステップＳ４２では、コントローラ４は、入れ替え対象となり得るキャッシュライン間で、ビットマップカウンタの値を比較することによって、ビットマップカウンタの値が最小のキャッシュラインを特定する。
【０１７１】
コントローラ４は、ビットマップカウンタの値が最小のキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ４３）。
【０１７２】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０１７３】
キャッシュライン入れ替えが必要ではないならば（ステップＳ４１のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ４４）。
【０１７４】
図２１のフローチャートは、アドレス変換テーブルキャッシュタグ３２が各キャッシュラインに対応するビットマップカウンタを含む構成に適用されるサブライン転送動作の手順を示す
キャッシュラインヒット（ビットマップミス）またはキャッシュミスが起きた場合、コントローラ４は、ＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７からリードされた１サブライン分のデータ（テーブルデータ）をあるキャッシュライン内の特定のサブラインに転送する（ステップＳ５１）。キャッシュラインヒット（ビットマップミス）が起きた場合には、このテーブルデータが転送されるキャッシュラインは、キャッシュラインヒットしたキャッシュラインである。キャッシュミスが起きた場合には、このテーブルデータが転送されるキャッシュラインは、入れ替え対象キャッシュラインである。
【０１７５】
コントローラ４は、テーブルデータが転送されたキャッシュライン内の特定のサブラインに対応するビットマップフラグの値を無効を示す値（例えば“０”）から有効を示す値（例えば“１”）に更新する（ステップＳ５２）。
【０１７６】
そして、コントローラ４は、このキャッシュラインに対応するビットマップカウンタを１だけインクリメントする（ステップＳ５３）。なお、何らかの理由（例えばキャッシュしていたテーブルデータの内容が変更され、その変更内容をアドレス変換テーブルキャッシュ３１上のテーブルデータにも反映させた場合など）でサブライン転送を行ってもビットマップフラグを“０”→“１”に更新しなかった場合は、コントローラ４は、対応するビットマップカウンタを１だけインクリメントする動作を実行しなくてもよい。
【０１７７】
図２２のフローチャートは、アドレス変換テーブルキャッシュタグ３２が各キャッシュラインに対応するビットマップカウンタを含む構成に適用されるキャッシュライン入れ替え動作の一連の手順を示す
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ６１）。ステップＳ６１では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０１７８】
キャッシュライン入れ替えが必要であるならば（ステップＳ６１のＹＥＳ）、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインに対応するビットマップカウンタを参照し、入れ替え対象となり得る全てのキャッシュラインの中から、ビットマップカウンタの値が最小のキャッシュラインを探す（ステップＳ６２）。ステップＳ６２では、コントローラ４は、入れ替え対象となり得るキャッシュライン間で、ビットマップカウンタの値を比較することによって、ビットマップカウンタの値が最小のキャッシュラインを特定する。
【０１７９】
コントローラ４は、ビットマップカウンタの値が最小のキャッシュラインを入れ替え対象キャッシュラインに決定する（ステップＳ６３）。
【０１８０】
コントローラ４は、（１）入れ替え対象キャッシュラインに対応するバリッドビット（ＶＢ）を無効を示す値（例えば“０”）にしてこの入れ替え対象キャッシュラインを無効化する動作と、（２）入れ替え対象キャッシュラインに対応する全てのビットマップフラグを無効を示す値（例えば“０”）にクリアして入れ替え対象キャッシュライン内の全てのサブラインを無効化する動作と、（３）入れ替え対象キャッシュラインに対応するビットマップカウンタの値を０にする動作を実行する（ステップＳ６４）。
【０１８１】
コントローラ４は、ＮＡＮＤ型フラッシュメモリ５内のアドレス変換テーブル７から、求める物理アドレスを含む１サブライン分のテーブルデータをリードし、このリードした１サブライン分のテーブルデータを入れ替え対象キャッシュライン内の特定の一つのサブラインに転送する（ステップＳ６５）。この特定の一つのサブラインは、キャッシュミスが起きる要因となったリードコマンドに含まれる論理アドレスによって定められる。
【０１８２】
そして、コントローラ４は、（１）入れ替え対象キャッシュラインに対応するタグの内容をリードコマンドに含まれる論理アドレス内のタグフィールドに更新する動作と、（２）入れ替え対象キャッシュラインの転送済みサブラインに対応するビットマップフラグを有効を示す値（例えば“１”）に更新する動作と、（３）入れ替え対象キャッシュラインに対応するビットマップカウンタの値を１だけインクリメントする動作と、（４）入れ替え対象キャッシュラインに対応するバリッドビット（ＶＢ）を有効を示す値（例えば“１”）に更新する動作を実行する（ステップＳ６６）。
【０１８３】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０１８４】
キャッシュライン入れ替えが必要ではないならば（ステップＳ６１のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ６７）。
【０１８５】
図２３は、タイムスタンプ／ビットマップカウンタ用の共用記憶領域を含むアドレス変換テーブルキャッシュタグ３２の構成例を示す。
【０１８６】
アドレス変換テーブルキャッシュタグ３２の各エントリーは、タグ３２Ａ、複数のビットマップフラグ３２Ｂに加え、タイムスタンプ／ビットマップカウンタ用の共用記憶領域３２Ｄを含む。
【０１８７】
共用記憶領域３２Ｄは、ＬＲＵポリシーによって入れ替え対象キャッシュラインを決定するために使用されるタイムスタンプまたは上述のビットマップカウンタを選択的に格納するために使用される。ＬＲＵポリシー用のタイムスタンプは、最近使用されたキャッシュラインほど大きな値（または小さな値）に設定されるように更新される。コントローラ４は、入れ替え対象キャッシュラインを決定するためのモード（リプレースモード）として、ＬＲＵモードとビットマップカウンタモードとを有する。ＬＲＵモードは、ＬＲＵポリシーによって入れ替え対象キャッシュラインを決定するリプレースモードである。ＬＲＵモードにおいては、コントローラ４は、タイムスタンプ用時計４１と、各キャッシュラインに対応する共用記憶領域３２Ｄとを使用して、各キャッシュラインに対応するタイムスタンプを管理する。一方、ビットマップカウンタモードは、ビットマップカウンタの値が最小のキャッシュラインを入れ替え対象キャッシュラインに決定するリプレースモードである。ビットマップカウンタモードにおいては、共用記憶領域３２Ｄは、ビットマップカウンタとして使用される。
【０１８８】
つまり、ＬＲＵモード（第１のリプレースモード）が使用される場合には、最近使用されたキャッシュラインほど大きな値（または小さな値）に設定されるように更新されるタイムスタンプが共用記憶領域３２Ｄに格納される。一方、ビットマップカウンタモード（第２のリプレースモード）が使用される場合には、対応する複数のビットマップフラグの中に含まれる、有効を示す値のビットマップフラグの数を示すビットマップカウンタが共用記憶領域３２Ｄに格納される。
【０１８９】
アドレス変換テーブルキャッシュタグ３２は、切り替えスイッチ４２を含む。切り替えスイッチ４２は、タイムスタンプまたはビットマップカウンタのどちらを各キャッシュラインに対応する共用記憶領域３２Ｄに格納するかを切り替えるように構成されたスイッチ回路である。コントローラ４は、切り替えスイッチ４２を制御することによって、ＬＲＵモードおよびビットマップカウンタモードを選択的に使用することができる。
【０１９０】
ＬＲＵモードにおいては、切り替えスイッチ４２は、タイムスタンプ用時計４１を選択する。一方、ビットマップカウンタモードにおいては、切り替えスイッチ４２は、各キャッシュラインに対応する複数のビットマップフラグ３２Ｂを保持するビットマップメモリを選択する。
【０１９１】
ＬＲＵモードにおいては、コントローラ４は、各キャッシュラインに対応する共用記憶領域３２Ｄに保持されるタイムスタンプを、以下のケース１、ケース２、またはケース３のいずれかが起きた時に更新する。
ケース１：対応するタグ３２Ａの内容を更新した
ケース２：対応するキャッシュラインのキャッシュヒットが起きた
ケース３：対応するキャッシュラインに新たなサブラインを転送した
ケース１は、次の（１）、（２）を含む。
（１）キャッシュライン入れ替え動作によって入れ替え対象キャッシュラインに対応するタグに新たなタグが格納された場合
（２）無効なキャッシュラインに対応するタグに新たなタグが格納されて無効なキャッシュラインが有効化された場合（つまり、対応するバリッドビットが“０”から“１”に変更された場合）
ケース２に関しては、キャッシュヒットが起きた場合、つまり、リードコマンドの論理アドレスの上位ビット部に一致するタグに関連付けられているキャッシュラインが存在し、且つこの論理アドレスに対応する物理アドレスが格納されるべきサブラインにテーブルデータが転送済みである場合に、コントローラ４は、このキャッシュラインに対応するタイムスタンプを更新する。キャッシュラインヒット（ビットマップミス）が起きた場合、つまり、リードコマンドの論理アドレスの上位ビット部に一致するタグに関連付けられているキャッシュラインが存在するものの、この論理アドレスに対応する物理アドレスが格納されるべきサブラインにテーブルデータがまだ転送されていない場合には、コントローラ４は、このキャッシュラインに対応するタイムスタンプを更新してもよいし、更新しなくてもよい。
【０１９２】
ケース３においては、コントローラ４は、タグ３２Ａの内容は更新せずに、新たに転送したサブラインに対応するビットマップフラグを無効を示す値から有効を示す値に変更し、さらにこのサブラインを含むキャッシュラインに対応するタイムスタンプを更新する。
【０１９３】
ある共用記憶領域３２Ｄに保持されているタイムスタンプを更新する動作においては、コントローラ４は、タイムスタンプ用時計４１の現在の値をこの共用記憶領域３２Ｄに格納し、そしてタイムスタンプ用時計４１の現在の値が１だけ進むようにタイムスタンプ用時計４１の現在の値を更新してもよい。あるいは、コントローラ４は、最初に、タイムスタンプ用時計４１の現在の値が１だけ進むようにタイムスタンプ用時計４１の現在の値を更新し、そしてタイムスタンプ用時計４１のこの更新された値を共用記憶領域３２Ｄに格納してもよい。
【０１９４】
なお、タイムスタンプ用時計４１として、イベントの発生の有無に関係なくカウント値を更新する時計（フリーランニングの時計）を使用する構成を適用することも可能である。この場合には、タイムスタンプを更新することが必要となるイベントが起きた時に、コントローラ４は、フリーランニングの時計の現在のカウント値をこの共用記憶領域３２Ｄに格納すればよい。
【０１９５】
この図２３の構成においては、各キャッシュラインに対応する共用記憶領域３２Ｄを切り替えスイッチ４２によってタイムスタンプの格納用に使用する場合（ＬＲＵモード）には、最も旧いタイムスタンプに対応するキャッシュライン（つまり、最も最近使用されていないキャッシュライン）を入れ替え対象キャッシュラインとすることができる。一方、各キャッシュラインに対応する共用記憶領域３２Ｄを切り替えスイッチ４２によってビットマップカウンタの格納用に使用する場合（ビットマップカウンタモード）には、転送済みサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインとすることができる。
【０１９６】
この場合、タイムスタンプの値は、その値が大きいほど新しい時間を示すように設定してもよい。これにより、ＬＲＵモードまたはビットマップカウンタモードのどちらが使用されるケースであっても、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインの中から、共用記憶領域３２Ｄに格納されている値が最も小さいキャッシュラインを探すという動作を実行すればよい。各共用記憶領域３２Ｄがタイムスタンプを保持している場合は、共用記憶領域３２Ｄの値が最も小さいキャッシュラインは、最も旧いタイムスタンプに対応するキャッシュライン、つまり最も最近使用されていないキャッシュラインである。各共用記憶領域３２Ｄがビットマップカウンタを保持している場合は、共用記憶領域３２Ｄの値が最も小さいキャッシュラインは、転送済みサブラインの数が最も少ないキャッシュラインである。
【０１９７】
図２４のフローチャートは、タイムスタンプ更新動作の手順を示す。
【０１９８】
ＬＲＵモードの期間中、コントローラ４は、「タグの内容を更新」、「キャッシュヒットが起きた」、または「新たなサブラインをキャッシュラインに転送」のいずれかのイベントが起きた時（ステップＳ７１のＹＥＳ、ステップＳ７２のＹＥＳ、またはステップＳ７３のＹＥＳ）に、対応する共用記憶領域３２Ｄ内のタイムスタンプを更新する（ステップＳ７４）。ステップＳ７４では、コントローラ４は、タイムスタンプ用時計４１の現在の値を共用記憶領域３２Ｄ（ＬＲＵモードにおいてはタイムスタンプ記憶領域として使用されている）にコピーし、タイムスタンプ用時計４１の現在の値を１だけ進めてもよい。
【０１９９】
図２５のフローチャートは、各キャッシュラインに対応する共用記憶領域３２Ｄの値（タイムスタンプ／ビットマップカウンタ）を使用した入れ替え対象キャッシュライン決定動作の手順を示す。
【０２００】
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ８１）。ステップＳ８１では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０２０１】
キャッシュライン入れ替えが必要であるならば（ステップＳ８１のＹＥＳ）、コントローラ４は、現在のモードがＬＲＵモードまたはビットマップカウンタモードのいずれであるかを判定する（ステップＳ８２）。
【０２０２】
現在のモードがビットマップカウンタモードであるならば、つまり各キャッシュラインに対応する共用記憶領域３２Ｄがビットマップカウンタの格納用に使用されているならば、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインに対応するビットマップカウンタ（記憶領域３２Ｄの値）を参照し、入れ替え対象となり得る全てのキャッシュラインの中から、ビットマップカウンタの値が最小のキャッシュラインを探す（ステップＳ８３）。ステップＳ８３では、コントローラ４は、入れ替え対象となり得るキャッシュライン間で、ビットマップカウンタの値を比較することによって、ビットマップカウンタの値が最小のキャッシュラインを特定する。
【０２０３】
コントローラ４は、ビットマップカウンタの値が最小のキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ８４）。
【０２０４】
一方、現在のモードがＬＲＵモードであるならば、つまり各キャッシュラインに対応する共用記憶領域３２Ｄがタイムスタンプの格納用に使用されているならば、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインに対応するタイムスタンプ（記憶領域３２Ｄの値）を参照し、入れ替え対象となり得る全てのキャッシュラインの中から、最も旧いタイムスタンプに対応するキャッシュラインを探す（ステップＳ８５）。ステップＳ８５では、コントローラ４は、入れ替え対象となり得るキャッシュライン間で、タイムスタンプを比較することによって、最も旧いタイムスタンプに対応するキャッシュラインを特定する。
【０２０５】
コントローラ４は、最も旧いタイムスタンプに対応するキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ８６）。
【０２０６】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０２０７】
キャッシュライン入れ替えが必要ではないならば（ステップＳ８１のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ８７）。
【０２０８】
以上説明したように、第１実施形態によれば、キャッシュライン入れ替えを実行する際、転送済みサブラインの数が最も少ないキャッシュラインを優先的に入れ替え対象キャッシュラインに決定することで、テーブルデータ（アドレス変換データ）がキャッシュされているサブラインの数が少ないキャッシュラインを優先してアドレス変換テーブルキャッシュ３１から追い出すことができる。よって、転送済みサブラインの数が多いキャッシュラインの内容を破棄することなく、アドレス変換テーブルキャッシュ３１内に維持することができる。この結果、キャッシュライン入れ替え後においても、アドレス変換テーブルキャッシュ３１が転送済みサブラインを多く保持している状態を維持することができるので、アドレス変換テーブルキャッシュ３１のヒット率の向上を図ることができる。
【０２０９】
（第２実施形態）
以下、タイムスタンプと転送済みサブラインの数の双方を使用して入れ替え対象キャッシュラインを決定する動作を第２実施形態として説明する。
【０２１０】
第２実施形態に係るストレージデバイス３のハードウェア構成は第１実施形態のストレージデバイス３と同様であり、第１実施形態と異なる点のみを中心に説明する。
【０２１１】
図２６に示されているように、第２実施形態においては、アドレス変換テーブルキャッシュタグ３２の各エントリーは、タグ３２Ａ、複数のビットマップフラグ３２Ｂに加え、タイムスタンプ３２Ｅを含む。
【０２１２】
複数のキャッシュラインそれぞれに対応する複数のタイムスタンプ３２Ｅの値は、上述の共用記憶領域３２Ｄに格納されるタイムスタンプと同様に、タイムスタンプ用時計４１の値に基づいて更新される。すなわち、コントローラ４は、第１実施形態で説明したタイムスタンプ更新動作と同様の手順で、タイムスタンプを、以下のケース１、ケース２、またはケース３のいずれかが起きた時に更新する。
ケース１：対応するタグ３２Ａの内容を更新した
ケース２：対応するキャッシュラインのキャッシュヒットが起きた
ケース３：対応するキャッシュラインに新たなサブラインを転送した
第２実施形態では、各キャッシュラインに対応するタイムスタンプは、最近使用された一つ以上のキャッシュラインを入れ替え対象から除外するために使用される。コントローラ４は、入れ替え対象となり得る全てのキャッシュラインから最近使用されたキャッシュラインを除いた残りのキャッシュラインの中で、転送済みサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定する。
【０２１３】
たとえ転送済みサブラインの数が少ないキャッシュラインであっても、タイムスタンプが新しいキャッシュライン（つまり、最近アクセスされたキャッシュライン）は、その後も比較的高い確率でアクセスされる可能性がある。第２実施形態では、最近使用されたキャッシュラインであると判定される１以上のキャッシュラインは入れ替え対象から除外される。したがって、たとえ転送済みサブラインの数が少ないキャッシュラインであっても、タイムスタンプが新しいキャッシュラインの内容は破棄されずに、アドレス変換テーブルキャッシュ３１に維持される。したがって、ヒット率をより改善することが可能となる。
【０２１４】
入れ替え対象から除外すべきキャッシュラインを判別する方法としては、対応するタイムスタンプとタイムスタンプ用時計４１の現在の値（現在の最新のタイムスタンプ）との差分が閾値よりも小さいキャッシュラインを入れ替え対象から除外する方法を使用することができる。
【０２１５】
タイムスタンプの値がタイムスタンプ用時計４１の現在の値に近いキャッシュラインは、最近アクセスされたキャッシュラインあると判定される。図２６では、キャッシュラインＬ０、Ｌ１、Ｌ２が入れ替え対象となり得るキャッシュライン（入れ替え対象キャッシュライン候補）であり、閾値が「２」に設定されている場合が想定されている。キャッシュラインＬ１に含まれる転送済みサブラインの数は入れ替え対象キャッシュライン候補の中で最も少ない。しかし、キャッシュラインＬ１に対応するタイムスタンプ（ここでは「７」）とタイムスタンプ用時計４１の現在の値（ここでは「８」）との差分（ここでは「１」）は閾値（ここでは「２」）よりも小さい。したがって、コントローラ４は、キャッシュラインＬ１を入れ替え対象から除外し、残りのキャッシュラインＬ０、Ｌ２の中で、転送済みサブラインの数が最も少ないキャッシュライン（ここでは、キャッシュラインＬ２）を入れ替え対象キャッシュラインに決定する。この結果、たとえ最近アクセスされたキャッシュラインＬ１の転送済みサブラインの数が少なくても、このキャッシュラインＬ１の内容は破棄されずに、アドレス変換テーブルキャッシュ３１に維持される。したがって、ヒット率をより改善することが可能となる。
【０２１６】
図２７のフローチャートは、各キャッシュラインに対応する複数のビットマップフラグと各キャッシュラインに対応するタイムスタンプとの双方を使用した入れ替え対象キャッシュライン決定動作の手順を示す。
【０２１７】
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ９１）。ステップＳ９１では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０２１８】
キャッシュライン入れ替えが必要であるならば（ステップＳ９１のＹＥＳ）、コントローラ４は、タイムスタンプとタイムスタンプ用時計４１の現在の値（最新のタイムスタンプ）との差分が閾値よりも小さいキャッシュラインを除く残りの入れ替え対象キャッシュライン候補の中から、転送済みサブラインの数が最も少ないキャッシュラインを探す（ステップＳ９２）。ステップＳ９２では、コントローラ４は、残りの各入れ替え対象キャッシュライン候補に対応するビットマップフラグを参照し、そして残りの入れ替え対象キャッシュライン候補間で、転送済みサブラインの数を比較することによって、残りの入れ替え対象キャッシュライン候補の中から、転送済みサブラインの数が最も少ないキャッシュラインを特定する。
【０２１９】
コントローラ４は、残りの入れ替え対象キャッシュライン候補の中で転送済みサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ９３）。
【０２２０】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０２２１】
キャッシュライン入れ替えが必要ではないならば（ステップＳ９１のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ９４）。
【０２２２】
図２７の入れ替え対象キャッシュライン決定動作によれば、たとえ転送済みサブラインの数が少ないキャッシュラインであっても、そのキャッシュラインが最近アクセスされたキャッシュラインである場合には、そのキャッシュラインを入れ替え対象から除外することができる。よって、アクセスされる可能性が高いキャッシュラインの内容を破棄することなく、キャッシュライン入れ替え後においても、アドレス変換テーブルキャッシュ３１が転送済みサブラインを多く保持している状態を維持することができる。
【０２２３】
なお、図２６のアドレス変換テーブルキャッシュタグ３２の各エントリーに図１８で説明したビットマップカウンタ３２Ｃを追加してもよい。この場合、ステップＳ９２では、コントローラ４は、タイムスタンプとタイムスタンプ用時計４１の現在の値との差分が閾値よりも小さいキャッシュラインを除く残りの入れ替え対象キャッシュライン候補の中から、ビットマップカウンタの値が最小のキャッシュラインを特定すればよい。
【０２２４】
図２８のフローチャートは、各キャッシュラインに対応する複数のビットマップフラグと各キャッシュラインに対応するタイムスタンプとの双方を使用した入れ替え対象キャッシュライン決定動作の別の手順を示す。
【０２２５】
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ９５）。ステップＳ９５では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０２２６】
キャッシュライン入れ替えが必要であるならば（ステップＳ９５のＹＥＳ）、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインの中から、転送済みサブラインの数が最も少ないキャッシュラインを探す（ステップＳ９６）。ステップＳ９６では、コントローラ４は、入れ替え対象となり得る各キャッシュラインに対応する複数のビットマップフラグを参照し、そして入れ替え対象となり得る全てのキャッシュライン間で転送済みサブラインの数を比較する。
【０２２７】
コントローラ４は、転送済みサブラインの数が最も少ないキャッシュラインの数が２以上存在するか否か、つまり転送済みサブラインの数が最も少ないキャッシュラインが一つのみではなく、転送済みサブラインの数が最も少ないキャッシュラインが複数探されたか否かを判定する（ステップＳ９７）。
【０２２８】
転送済みサブラインの数が最も少ないキャッシュラインが一つだけ存在する場合には（ステップＳ９７のＮＯ）、コントローラ４は、転送済みサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ９８）。
【０２２９】
一方、転送済みサブラインの数が最も少ないキャッシュラインが２以上存在する場合には、つまり転送済みサブラインの数が最も少ないキャッシュラインが複数探された場合には（ステップＳ９７のＹＥＳ）、コントローラ４は、転送済みサブラインの数が最も少ないこれら２以上のキャッシュライン（転送済みサブラインの数が同数であるキャッシュライン）の中で、タイムスタンプが最も旧いキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ９９）。
【０２３０】
これにより、転送済みサブラインの数が最も少ないキャッシュラインの数が１つではなく、複数存在する場合には、タイムスタンプがより旧いキャッシュラインを優先的に入れ替え対象キャッシュラインに決定することができる。
【０２３１】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０２３２】
キャッシュライン入れ替えが必要ではないならば（ステップＳ９５のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ１００）。
【０２３３】
なお、図２６のアドレス変換テーブルキャッシュタグ３２の各エントリーに図１８で説明したビットマップカウンタ３２Ｃを追加してもよい。この場合、ステップＳ９６では、コントローラ４は、ビットマップカウンタの値が最小のキャッシュラインを特定すればよい。
【０２３４】
（第３実施形態）
以下、ダーティーな転送済みサブラインの数を使用して入れ替え対象キャッシュラインを決定する動作を第３実施形態として説明する。
【０２３５】
第３実施形態に係るストレージデバイス３のハードウェア構成は第１実施形態のストレージデバイス３と同様であり、第１実施形態と異なる点のみを中心に説明する。
【０２３６】
第３実施形態ではダーティーなサブラインとは、ＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７にそのサブラインの内容が反映されていないサブラインを意味する。換言すれば、ダーティーなサブラインとは、ＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７に反映されていないデータ（テーブルデータ）を保持しているサブラインを意味する。例えば、ある転送済みサブラインのテーブルデータのみが更新され、アドレス変換テーブル７内の対応するテーブルデータがまだ更新されていない場合には、この転送済みサブラインはダーティーな転送済みサブラインである。
【０２３７】
ダーティーなサブラインの数が多いキャッシュラインを入れ替え対象にしてしまうと、キャッシュライン入れ替えを行なう際にＮＡＮＤ型フラッシュメモリ５に書き込むことが必要なデータ量が増え、これによってキャッシュライン入れ替え動作に要する時間が長くなる場合がある。
【０２３８】
第３実施形態では、コントローラ４は、ＮＡＮＤ型フラッシュメモリ５に反映されていないデータが格納されているサブライン（ダーティーなサブライン）の数を考慮して、入れ替え対象キャッシュラインに決定することができる。
【０２３９】
図２９に示されているように、第３実施形態においては、アドレス変換テーブルキャッシュタグ３２の各エントリーは、タグ３２Ａ、複数のビットマップフラグ３２Ｂに加え、複数のダーティーフラグ３２Ｆを含む。
【０２４０】
各ダーティーフラグ３２Ｆは、対応するサブラインに格納されているデータ（テーブルデータ）がＮＡＮＤ型フラッシュメモリ５に未反映のデータ（更新データ）であるか否か、つまり対応するサブライン内のデータがダーティーデータであるか否かを示す。コントローラ４が、ＮＡＮＤ型フラッシュメモリ５に未反映のデータ（更新データ）をあるサブラインに転送した時、コントローラ４は、このサブラインに対応するダーティーフラグ３２Ｆを例えば“０”から“１”に更新する。この場合、“１”のダーティーフラグ３２Ｆは、対応するサブラインがダーティーなサブラインであることを示す。コントローラ４が、ダーティーなサブライン内のデータをＮＡＮＤ型フラッシュメモリ５に書き込んだ時、コントローラ４は、このサブラインに対応するダーティーフラグ３２Ｆを例えば“１”から“０”に更新する。
【０２４１】
図２９のフローチャートは、各キャッシュラインに対応する複数のダーティーフラグを使用した入れ替え対象キャッシュライン決定動作の手順を示す。
【０２４２】
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ１０１）。ステップＳ１０１では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０２４３】
キャッシュライン入れ替えが必要であるならば（ステップＳ１０１のＹＥＳ）、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインの中から、転送済みサブラインの数が最も少ないキャッシュラインを探す（ステップＳ１０２）。ステップＳ１０２では、コントローラ４は、入れ替え対象となり得る各キャッシュラインに対応する複数のビットマップフラグを参照し、そして入れ替え対象となり得る全てのキャッシュライン間で転送済みサブラインの数を比較する。
【０２４４】
コントローラ４は、転送済みサブラインの数が最も少ないキャッシュラインの数が２以上存在するか否か、つまり転送済みサブラインの数が最も少ないキャッシュラインが一つのみではなく、転送済みサブラインの数が最も少ないキャッシュラインが複数探されたか否かを判定する（ステップＳ１０３）。
【０２４５】
転送済みサブラインの数が最も少ないキャッシュラインが一つだけ存在する場合には（ステップＳ１０３のＮＯ）、コントローラ４は、転送済みサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ１０４）。
【０２４６】
一方、転送済みサブラインの数が最も少ないキャッシュラインが２以上存在する場合には（ステップＳ１０３のＹＥＳ）、コントローラ４は、転送済みサブラインの数が最も少ないこれら２以上のキャッシュラインの中で、ダーティーなサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ１０５）。
【０２４７】
これにより、転送済みサブラインの数が最も少ないキャッシュラインの数が１つではなく、複数存在する場合には、ダーティーなサブラインの数がより少ないキャッシュラインを優先的に入れ替え対象キャッシュラインに決定することができる。
【０２４８】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０２４９】
キャッシュライン入れ替えが必要ではないならば（ステップＳ１０１のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ１０６）。
【０２５０】
なお、別の実施形態では、コントローラ４は、ダーティーな転送済みサブラインの数のみを考慮して、入れ替え対象キャッシュラインを決定することもできる。この場合、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインの中で、ダーティーな転送済みサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定してもよい。
【０２５１】
なお、図２９のアドレス変換テーブルキャッシュタグ３２の各エントリーに図１８で説明したビットマップカウンタ３２Ｃを追加してもよい。この場合、ステップＳ１０２では、コントローラ４は、ビットマップカウンタの値が最小のキャッシュラインを特定すればよい。また、図２９のアドレス変換テーブルキャッシュタグ３２の各エントリーに、“１”のダーティーフラグの数を示すダーティーフラグカウンタを追加してもよい。この場合、ステップＳ１０５では、コントローラ４は、ダーティーフラグカウンタの値が最小のキャッシュラインを特定すればよい。
【０２５２】
図３１のフローチャートは、アドレス変換テーブルキャッシュタグ３２が各キャッシュラインに対応する複数のダーティーフラグを含む構成に適用されるキャッシュライン入れ替え動作の手順を示す。
【０２５３】
コントローラ４は、まず、決定された入れ替え対象ラインに含まれ、且つダーティーフラグが有効の値（例えば“１”）のサブライン（ダーティーなサブライン）を特定する（ステップＳ１１１）。
【０２５４】
コントローラ４は、ダーティーフラグが有効の値（例えば“１”）の各サブライン内のテーブルデータをＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７に書き込む。すなわち、更新されている各テーブルデータをＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７に書き戻し、更新されている各テーブルデータの内容をアドレス変換テーブル７に反映させる（ステップＳ１１２）。
【０２５５】
コントローラ４は、（１）入れ替え対象キャッシュラインに対応するバリッドビット（ＶＢ）を無効を示す値（例えば“０”）にしてこの入れ替え対象キャッシュラインを無効化する動作と、（２）入れ替え対象キャッシュラインに対応する全てのビットマップフラグおよび全てのダーティーフラグを無効を示す値（例えば“０”）にクリアして入れ替え対象キャッシュライン内の全てのサブラインを無効化する動作を実行する（ステップＳ１１３）。
【０２５６】
コントローラ４は、ＮＡＮＤ型フラッシュメモリ５内のアドレス変換テーブル７から、求める物理アドレスを含む１サブライン分のテーブルデータをリードし、このリードした１サブライン分のテーブルデータを入れ替え対象キャッシュライン内の特定の一つのサブラインに転送する（ステップＳ１１４）。この特定の一つのサブラインは、キャッシュミスが起きる要因となったリードコマンドに含まれる論理アドレスによって定められる。
【０２５７】
そして、コントローラ４は、（１）入れ替え対象キャッシュラインに対応するタグの内容をリードコマンドに含まれる論理アドレス内のタグフィールドに更新する動作と、（２）入れ替え対象キャッシュラインの転送済みサブラインに対応するビットマップフラグを有効を示す値（例えば“１”）に更新する動作と、（３）入れ替え対象キャッシュラインに対応するバリッドビット（ＶＢ）を有効を示す値（例えば“１”）に更新する動作を実行する（ステップＳ１１５）。
【０２５８】
（第４実施形態）
以下、ビットマップフラグ、ダーティーフラグ、タイムスタンプを使用して入れ替え対象キャッシュラインを決定する動作を第４実施形態として説明する。
【０２５９】
第４実施形態に係るストレージデバイス３のハードウェア構成は第１実施形態のストレージデバイス３と同様であり、第１実施形態と異なる点のみを中心に説明する。
【０２６０】
図３２に示されているように、第４実施形態においては、アドレス変換テーブルキャッシュタグ３２の各エントリーは、タグ３２Ａ、複数のビットマップフラグ３２Ｂに加え、タイムスタンプ３２Ｅ、複数のダーティーフラグ３２Ｆを含む。
【０２６１】
図３３のフローチャートは、第４実施形態に係る入れ替え対象キャッシュライン決定動作の手順を示す。
【０２６２】
例えばキャッシュミスが発生した時、コントローラ４は、キャッシュライン入れ替えが必要であるか否かを判定する（ステップＳ１２１）。ステップＳ１２１では、コントローラ４は、入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するか否かを判定する。未使用のキャッシュラインが存在しないならば、コントローラ４は、キャッシュライン入れ替えが必要であると判定する。
【０２６３】
キャッシュライン入れ替えが必要であるならば（ステップＳ１２１のＹＥＳ）、コントローラ４は、入れ替え対象となり得る全てのキャッシュラインの中から、転送済みサブラインの数が最も少ないキャッシュラインを探す（ステップＳ１２２）。ステップＳ１２２では、コントローラ４は、入れ替え対象となり得る全てのキャッシュライン間で転送済みサブラインの数を比較する。
【０２６４】
コントローラ４は、転送済みサブラインの数が最も少ないキャッシュラインの数が２以上存在するか否か、つまり転送済みサブラインの数が最も少ないキャッシュラインが一つのみではなく、転送済みサブラインの数が最も少ないキャッシュラインが２以上探されたか否かを判定する（ステップＳ１２３）。
【０２６５】
転送済みサブラインの数が最も少ないキャッシュラインが一つだけ存在する場合には（ステップＳ１２３のＮＯ）、コントローラ４は、転送済みサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ１２４）。
【０２６６】
一方、転送済みサブラインの数が最も少ないキャッシュラインが２以上存在する場合には、つまり転送済みサブラインの数が最も少ないキャッシュラインが２以上探された場合には（ステップＳ１２３のＹＥＳ）、コントローラ４は、転送済みサブラインの数が最も少ないこれら２以上のキャッシュラインの中で、ダーティーなサブラインの数が最も少ないキャッシュラインを探す（ステップＳ１２５）。ステップＳ１２５では、コントローラ４は、転送済みサブラインの数が最も少ないこれら２以上のキャッシュライン間でダーティーなサブラインの数を比較する。
【０２６７】
コントローラ４は、ダーティーなサブラインの数が最も少ないキャッシュラインの数が２以上であるか否か、つまりダーティーなサブラインの数が最も少ないキャッシュラインが一つのみではなく、ダーティーなサブラインの数が最も少ないキャッシュラインが２以上探されたか否かを判定する（ステップＳ１２６）。
【０２６８】
ダーティーなサブラインの数が最も少ないキャッシュラインが一つだけ存在する場合には（ステップＳ１２６のＮＯ）、コントローラ４は、転送済みサブラインの数が最も少ない２以上のキャッシュラインの中で、ダーティーなサブラインの数が最も少ないキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ１２７）。
【０２６９】
一方、ダーティーなサブラインの数が最も少ないキャッシュラインが２以上存在する場合には、つまりダーティーなサブラインの数が最も少ないキャッシュラインが２以上探された場合には（ステップＳ１２６のＹＥＳ）、コントローラ４は、ダーティーなサブラインの数が最も少ないこれら２以上のキャッシュラインの中で、タイムスタンプが最も旧いキャッシュラインを入れ替え対象キャッシュラインに決定し、そして、ＮＡＮＤ型フラッシュメモリ５からリードされた１サブライン分のデータ（テーブルデータ）を入れ替え対象キャッシュライン内の複数のサブラインのうちの一つのサブラインに転送するキャッシュライン入れ替え動作を実行する（ステップＳ１２８）。
【０２７０】
これにより、転送済みサブラインの数が最も少ないキャッシュラインの数が１つではなく、複数存在する場合には、ダーティーなサブラインの数が最も少ないキャッシュラインを優先的に入れ替え対象キャッシュラインに決定することができる。また、ダーティーなサブラインの数が最も少ないキャッシュラインの数が１つではなく、ダーティーなサブラインの数が最も少ないキャッシュラインが複数探された場合には、タイムスタンプがより旧いキャッシュラインを優先的に入れ替え対象キャッシュラインに決定することができる。
【０２７１】
入れ替え対象となり得るキャッシュライン（全ての入れ替え対象キャッシュライン候補）の中に未使用のキャッシュラインが存在するならば、コントローラ４は、キャッシュライン入れ替えが必要ではないと判定する。
【０２７２】
キャッシュライン入れ替えが必要ではないならば（ステップＳ１２１のＮＯ）、コントローラ４は、（キャッシュライン入れ替えを伴わない）キャッシュライン転送動作、つまり未使用のキャッシュライン内の複数のサブラインのうちの一つのサブラインにテーブルデータを転送する動作を実行する（ステップＳ１２９）。
【０２７３】
なお、図３２のアドレス変換テーブルキャッシュタグ３２の各エントリーにビットマップカウンタ３２Ｃおよびダーティーフラグカウンタを追加してもよい。この場合、ステップＳ１２２では、コントローラ４は、ビットマップカウンタの値が最小のキャッシュラインを特定すればよい。また、ステップＳ１２５では、コントローラ４は、ダーティーフラグカウンタの値が最小のキャッシュラインを特定すればよい。
【０２７４】
（第５実施形態）
以下、ホストメモリ用のキャッシュを含むコントローラ４の構成を第５実施形態として説明する。
【０２７５】
図３４に示されているように、アドレス変換テーブルキャッシュ３１はホストメモリ（メインメモリ２２のデバイス使用領域２２Ｂ）に置かれている。デバイス使用領域２２Ｂは、アドレス変換テーブルキャッシュ３１のみならず、コントローラ４によって使用される他のデータを格納するためにも利用される。他のデータは、例えば、ＮＡＮＤ型フラッシュメモリ５に書き込まれたデータの消失復元用のパリティであってもよい。ホストメモリ（メインメモリ２２のデバイス使用領域２２Ｂ）においては、あるアドレス範囲（ここでは、アドレスＡからアドレスＢまでのアドレス範囲）に対応する記憶領域はアドレス変換テーブルキャッシュ３１を格納するために使用され、別のアドレス範囲（ここでは、アドレスＸからアドレスＹまでのアドレス範囲）に対応する記憶領域は他のデータを格納するために使用される。
【０２７６】
ストレージデバイス３においては、コントローラ４は、上述のホストインタフェース１１、ＣＰＵ１２、ＲＡＭ１３、バックエンド部１４に加え、ホストメモリ上のアドレス変換テーブルキャッシュ３１に対するアクセスを高速化するために、ホストメモリ用のキャッシュ５１を含んでいる。キャッシュ５１は、バス１０とホストインタフェース１１との間に配置されている。キャッシュ５１は、ホストメモリに書き込むべきデータ（テーブルデータ、パリティ、等）を自身のキャッシュ領域（ＳＲＡＭ５１Ａ）にキャッシュするように構成されている。キャッシュ５１は、ライトバックタイプのキャッシュとして実現されていてもよい。この場合、このキャッシュ５１内のキャッシュ領域に未使用のキャッシュラインが無くなった場合、キャッシュ５１は、このキャッシュ領域内の入れ替え対象キャッシュラインに格納されているデータを破棄またはホストメモリに書き戻し、そしてホストメモリに書き込むべき新たなデータをこの入れ替え対象キャッシュラインに格納する。
【０２７７】
コントローラ４は、さらに、幾つかのハードウェアアクセラレータ、例えば、ハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａ、ハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂ、を含んでいてもよい。ハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａは、論理アドレスを物理アドレスに変換するアドレス解決動作を実行するための専用ハードウェアである。ハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂは、上述のパリティをホストメモリにライトする動作およびホストメモリからパリティをリードする動作等を実行するための専用ハードウェアである。ハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａおよびハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂの各々は、メモリアクセスを実行可能なバスマスタとして実現されている。ハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａは、ホストメモリ上のアドレス変換テーブルキャッシュ３１にデータ（デーブルデータ）を格納するためのライト要求を発行することができ、またハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂは、ホストメモリ上にパリティのような他のデータを格納するためのライト要求を発行することができる。
【０２７８】
図３５は、キャッシュ５１の構成例を示す。
【０２７９】
キャッシュ５１は、キャッシュとして機能するＳＲＡＭ５１Ａと、このＳＲＡＭ５１Ａ（キャッシュ）を制御する回路であるキャッシュコントローラ５１Ｂとを含む。ＳＲＡＭ５１Ａは、複数のキャッシュラインＣＬ０、ＣＬ１、ＣＬ２、…を含むキャッシュ領域６１Ａと、複数のキャッシュラインに対応する複数のエントリーを含むキャッシュタグ領域６１Ｂとを含む。キャッシュラインＣＬ０、ＣＬ１、ＣＬ２、…の各々のサイズは、１サブラインのサイズと同じであってもよいし、１サブラインのサイズとは異なっていてもよい。
【０２８０】
キャッシュタグ領域６１Ｂの各エントリーは、バリッドビット（ＶＢ）と、タグと、ユーゼージ情報と、ダーティーフラグとを含んでいてもよい。各エントリーのユーゼージ情報は、キャッシュタグ領域６１Ｂ内の入れ替え対象キャッシュラインを決定するために使用される。キャッシュタグ領域６１Ｂ内の入れ替え対象キャッシュラインを決定するための入れ替えポリシーとしては、ＬＲＵが使用されてもよいし、別のポリシーが使用されてもよい。
【０２８１】
例えば、キャッシュ５１が５ウェイ・セットアソシアティブ・キャッシュとして実現されているケースにおいては、ある特定のセットに対応する５つのキャッシュライン（つまり、５つのウェイの５つのキャッシュライン）に対して異なる優先度のユーゼージ情報が与えられる。入れ替えポリシーがＬＲＵであるならば、最も最近アクセスされたキャッシュラインにはそのキャッシュラインを最も置換され難くするための優先度を有するユーゼージ情報（最も置換され難い優先度のユーゼージ情報）が与えられる。
【０２８２】
ダーティーフラグは、対応するキャッシュラインがダーティーなキャッシュラインであるか否かを示す。ダーティーなキャッシュラインとは、ホストメモリにそのキャッシュラインの内容が反映されていないキャッシュラインを意味する。換言すれば、ダーティーなキャッシュラインとは、ホストメモリに反映されていないデータが格納されているキャッシュラインを意味する。
【０２８３】
図３６のフローチャートは、ホスト２からのリード要求（リードコマンド）の受信時にＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａによって実行されるリード処理の手順を示す。
【０２８４】
ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａがホスト２からリード要求（リードコマンド）を受信した時（ステップＳ１３１）、ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａは、アドレス変換テーブルキャッシュタグ３２を参照して、ホストメモリ上のアドレス変換テーブルキャッシュ３１のキャッシュヒット／ミスを判定する（ステップＳ１３２）。
【０２８５】
リードコマンド内の論理アドレスに対応する物理アドレスを含むテーブルデータがホストメモリ上のアドレス変換テーブルキャッシュ３１に存在するならば（キャッシュヒット）（ステップＳ１３３のＹＥＳ）、ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａは、ホストメモリ上のアドレス変換テーブルキャッシュ３１からテーブルデータをリードするためのリード要求を発行して、この論理アドレスに対応する物理アドレスを含むテーブルデータを得る（ステップＳ１３４）。発行されたリード要求はキャッシュ５１に送られるので、もしこのテーブルデータがキャッシュ５１内のキャッシュ領域６１Ａに存在するならば、図３７のステップＳ１４３、Ｓ１４４を参照して詳細は後述するが、キャッシュ５１のキャッシュコントローラ５１Ｂは、キャッシュ領域６１Ａからこのテーブルデータをリードし、リードしたテーブルデータをＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａに返す。もしこのテーブルデータがキャッシュ５１内のキャッシュ領域６１Ａに存在しないならば、キャッシュコントローラ５１Ｂは、図３７のステップＳ１４３、Ｓ１４５〜Ｓ１５２を参照して詳細は後述するが、このリード要求をホストインタフェース１１を介してホスト２に送出する。
【０２８６】
ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａは、取得したテーブルデータに含まれる目的の物理アドレスを使用してＮＡＮＤ型フラッシュメモリ５をリードアクセスし、ＮＡＮＤ型フラッシュメモリ５からユーザデータをリードする（ステップＳ１３５）。
【０２８７】
リードコマンド内の論理アドレスに対応する物理アドレスを含むテーブルデータがホストメモリ上のアドレス変換テーブルキャッシュ３１に存在しないならば（キャッシュミスまたはビットマップミス）（ステップＳ１３３のＮＯ）、ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａは、ＮＡＮＤ型フラッシュメモリ５のアドレス変換テーブル７からこのテーブルデータをリードする（ステップＳ１３６）。そして、ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａは、このリードしたテーブルデータをホストメモリ上のアドレス変換テーブルキャッシュ３１に格納するためのライト要求を発行する（ステップＳ１３７）。そして、ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａは、リードしたテーブルデータに含まれる目的の物理アドレスを使用してＮＡＮＤ型フラッシュメモリ５をリードアクセスし、ＮＡＮＤ型フラッシュメモリ５からユーザデータをリードする（ステップＳ１３５）。なお、ここでは、ステップＳ１３７の処理を最初に実行し、次いでステップＳ１３５の処理を実行する、という処理順序を例示したが、ステップＳ１３５の処理を最初に実行し、次いでステップＳ１３７の処理を実行するという処理順序であってもよい。つまり、ホストメモリ上のアドレス変換テーブルキャッシュ３１へのテーブルデータ転送と、ＮＡＮＤ型フラッシュメモリ５からのユーザデータリードとは、どちらが先に実行されてもよい。図８、図１０で説明したキャッシュ制御処理においても、ホストメモリ上のアドレス変換テーブルキャッシュ３１へのテーブルデータ転送と、ＮＡＮＤ型フラッシュメモリ５からのユーザデータリードとは、どちらが先に実行されてもよい。
【０２８８】
図３７のフローチャートは、ホストメモリ上のアドレス変換テーブルキャッシュ３１からテーブルデータをリードするためのリード要求の受信時にキャッシュ５１（キャッシュコントローラ５１Ｂ）によって実行される動作の手順を示す。
【０２８９】
キャッシュ５１がホストメモリ上のアドレス変換テーブルキャッシュ３１からテーブルデータをリードするためのリード要求をＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａから受信した時（ステップＳ１４１のＹＥＳ）、キャッシュ５１のキャッシュコントローラ５１Ｂは、自身のキャッシュタグ領域６１Ｂを参照して、リード要求によって指定された１サブライン分のテーブルデータが自身のキャッシュ領域６１Ａに存在するか否かを判定する（ステップＳ１４２）。
【０２９０】
このテーブルデータが自身のキャッシュ領域６１Ａに存在するならば（キャッシュヒット）（ステップＳ１４３のＹＥＳ）、キャッシュコントローラ５１Ｂは、キャッシュ領域６１Ａからこのテーブルデータをリードし、リードしたテーブルデータをＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａに返す（ステップＳ１４４）。
【０２９１】
この１サブライン分のテーブルデータが自身のキャッシュ領域６１Ａに存在しないならば（キャッシュミス）（ステップＳ１４３のＮＯ）、キャッシュコントローラ５１Ｂは、このリード要求をホストインタフェース１１を介してホスト２に送出して、この１サブライン分のテーブルデータをホストメモリ上のアドレス変換テーブルキャッシュ３１からリードする（ステップＳ１４５）。
【０２９２】
キャッシュコントローラ５１Ｂは、このテーブルデータを格納可能な空きキャッシュライン（このテーブルデータを格納可能な一つ以上の空きキャッシュライン）が自身のキャッシュ領域６１Ａに存在するか否かを判定する（ステップＳ１４６）。
【０２９３】
このテーブルデータを格納可能な空きキャッシュライン（このテーブルデータを格納可能な一つ以上の空きキャッシュライン）が自身のキャッシュ領域６１Ａに存在しないならば（ステップＳ１４６のＮＯ）、キャッシュコントローラ５１Ｂは、キャッシュ領域６１Ａ内の入れ替え対象となり得る各キャッシュラインのユーゼージ情報（優先度）を参照して、キャッシュ領域６１Ａ内の入れ替え対象キャッシュラインを決定する（ステップＳ１４７）。
【０２９４】
キャッシュコントローラ５１Ｂは、入れ替え対象キャッシュラインに対応するダーティーフラグを参照して、入れ替え対象キャッシュラインがその内容がホストメモリに反映されていないダーティーなキャッシュラインであるか否かを判定する（ステップＳ１４８）。
【０２９５】
入れ替え対象キャッシュラインがダーティーなキャッシュラインであるならば（ステップＳ１４８のＹＥＳ）、キャッシュコントローラ５１Ｂは、入れ替え対象キャッシュラインの内容（テーブルデータ、またはパリティ）をホストメモリに書き戻す（ステップＳ１４９）。
【０２９６】
入れ替え対象キャッシュラインがダーティーなキャッシュラインではないならば（ステップＳ１４８のＮＯ）、キャッシュコントローラ５１Ｂは、入れ替え対象キャッシュラインの内容（テーブルデータ、またはパリティ）を破棄する（ステップＳ１５０）。
【０２９７】
ステップＳ１４９の処理またはステップＳ１５０の処理を実行した後、キャッシュコントローラ５１Ｂは、ホストメモリ上のアドレス変換テーブルキャッシュ３１からリードされたテーブルデータを自身のキャッシュ領域６１Ａの入れ替え対象キャッシュラインに格納する（ステップＳ１５１）。そして、キャッシュコントローラ５１Ｂは、このテーブルデータをＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａに返す（ステップＳ１５２）。
【０２９８】
テーブルデータを格納可能な空きキャッシュライン（このテーブルデータを格納可能な一つ以上の空きキャッシュライン）が自身のキャッシュ領域６１Ａに存在しているならば（ステップＳ１４６のＹＥＳ）、キャッシュコントローラ５１Ｂは、ステップＳ１４７〜Ｓ１５０の処理の実行をスキップする。
【０２９９】
図３８のフローチャートは、ホストメモリ上のアドレス変換テーブルキャッシュ３１にテーブルデータを格納するためのライト要求の受信時にキャッシュ５１（キャッシュコントローラ５１Ｂ）によって実行される動作の手順を示す。
【０３００】
キャッシュ５１のキャッシュコントローラ５１Ｂがホストメモリ上のアドレス変換テーブルキャッシュ３１に１サブライン分のテーブルデータを格納するためのライト要求をＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａから受信した時（ステップＳ１６１のＹＥＳ）、キャッシュコントローラ５１Ｂは、このテーブルデータを格納可能な空きキャッシュライン（このテーブルデータを格納可能な一つ以上の空きキャッシュライン）が自身のキャッシュ領域６１Ａに存在するか否かを判定する（ステップＳ１６２）。
【０３０１】
このテーブルデータを格納可能な空きキャッシュライン（このテーブルデータを格納可能な一つ以上の空きキャッシュライン）が自身のキャッシュ領域６１Ａに存在しないならば（ステップＳ１６２のＮＯ）、キャッシュコントローラ５１Ｂは、キャッシュ領域６１Ａ内の入れ替え対象となり得る各キャッシュラインのユーゼージ情報（優先度）を参照して、キャッシュ領域６１Ａ内の入れ替え対象キャッシュラインを決定する（ステップＳ１６３）。
【０３０２】
キャッシュコントローラ５１Ｂは、入れ替え対象キャッシュラインに対応するダーティーフラグを参照して、入れ替え対象キャッシュラインがその内容がホストメモリに反映されていないダーティーなキャッシュラインであるか否かを判定する（ステップＳ１６４）。
【０３０３】
入れ替え対象キャッシュラインがダーティーなキャッシュラインであるならば（ステップＳ１６４のＹＥＳ）、キャッシュコントローラ５１Ｂは、入れ替え対象キャッシュラインの内容（テーブルデータ、またはパリティ）をホストメモリに書き戻す（ステップＳ１６５）。
【０３０４】
入れ替え対象キャッシュラインがダーティーなキャッシュラインではないならば（ステップＳ１６４のＮＯ）、キャッシュコントローラ５１Ｂは、入れ替え対象キャッシュラインの内容（テーブルデータ、またはパリティ）を破棄する（ステップＳ１６６）。
【０３０５】
ステップＳ１６５の処理またはステップＳ１６６の処理を実行した後、キャッシュコントローラ５１Ｂは、ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａから受信したテーブルデータを入れ替え対象キャッシュラインに格納する（ステップＳ１６７）。
【０３０６】
図３９のフローチャートは、ＮＡＮＤ型フラッシュメモリ５に書き込まれたユーザデータの消失復元用のパリティをホストメモリに書き込む動作の手順を示す。
【０３０７】
ＮＡＮＤ型フラッシュメモリ５に書き込まれたユーザデータの消失復元用のパリティをホストメモリに書き込むことが必要な時（ステップＳ１７１のＹＥＳ）、ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂは、このパリティをホストメモリに格納するためのライト要求を発行する（ステップＳ１７２）。
【０３０８】
このライト要求をＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂから受信した時、キャッシュ５１（キャッシュコントローラ５１Ｂ）は、図３８で説明した処理と同様の手順で、パリティを自身のキャッシュ領域６１Ａに格納する動作、入れ替え対象キャッシュラインの内容を破棄またはホストメモリに書き戻す動作、等を実行する。
【０３０９】
また、ホストメモリからパリティをリードするためのリード要求をＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂから受信した時、キャッシュ５１（キャッシュコントローラ５１Ｂ）は、図３７で説明した処理と同様の手順で、自身のキャッシュ領域６１Ａまたはホストメモリからパリティをリードする動作、入れ替え対象キャッシュラインの内容を破棄またはホストメモリに書き戻す動作、等を実行する。
【０３１０】
このように、キャッシュ５１は、テーブルデータのみならず、パリティのような他のデータも自身のキャッシュ領域６１Ａにキャッシュするように構成されている。換言すれば、キャッシュ５１は、ホストメモリ内のアドレス変換テーブルキャッシュ３１に格納すべきデータ（テーブルデータ）と、ホストメモリに格納すべき他のデータ（例えばパリティ）とをキャッシュするように構成されている。
【０３１１】
しかし、パリティはデータ消失のような障害が起こらない限り利用されないデータであるので、たとえパリティがキャッシュ５１にキャッシュされても、このキャッシュされたパリティが利用されるケースは非常に少ない。また、通常、パリティのサイズは非常に大きい。したがって、ＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃２）５２がパリティをホストメモリに格納するためのライト要求を発行すると、キャッシュ３１内の多くのキャッシュラインが、利用頻度の少ないこのパリティによって占有されてしまう。このことは、キャッシュ５１におけるテーブルデータのヒット率を低下させる要因となる。
【０３１２】
そこで、キャッシュ５１のキャッシュコントローラ５１Ｂは、アドレス変換テーブル７のデータ（テーブルデータ）が格納されている自身のキャッシュラインよりもパリティのような他のデータが格納されている自身のキャッシュラインを優先的に入れ替え対象とするように構成されている。この場合、キャッシュ５１のキャッシュコントローラ５１Ｂは、自身の一つのキャッシュラインに格納されるべきデータのライトアドレスがパリティのような他のデータが格納されるべきホストメモリ上の記憶領域のアドレス範囲（アドレスＸ〜アドレスＹ）に属する場合、この一つのキャッシュラインに対応するキャッシュタグ領域６１Ｂのエントリーに、入れ替え（置換）されやすい値の優先度を格納する。例えば、当該他のデータに対応するアドレス範囲に書き込むべきデータをキャッシュ領域６１Ａのキャッシュラインに格納する時には、キャッシュコントローラ５１Ｂは、このキャッシュラインを優先的に入れ替え対象とするための優先度（このキャッシュラインを置換され易くする優先度）をこのキャッシュラインに対応するキャッシュタグ領域６１Ｂのエントリーに格納してもよい。これにより、パリティが格納されているキャッシュラインを優先的に入れ替え対象キャッシュラインに決定することが可能となる。この結果、ある新たなテーブルデータがキャッシュ５１（キャッシュ領域６１Ａ）にキャッシュされるべき時には、既にテーブルデータを格納しているキャッシュラインそれぞれをキャッシュ５１内に維持しつつ、パリティを格納しているキャッシュラインのみをキャッシュ５１から優先して追い出すことが可能となる。
【０３１３】
図４０は、ホストメモリ上の優先置換領域へのライトデータに対して、対応するキャッシュラインを置換されやすくする優先度（ユーゼージ情報）を割り当てる動作を示す。
【０３１４】
ホストメモリ上の優先置換領域とは、キャッシュ５１から優先して追い出すべきデータに対応するホストメモリ上の記憶領域である。第５実施形態では、特定のアドレス範囲（アドレスＸからアドレスＹまでのアドレス範囲）を有する記憶領域、つまりパリティのような他のデータが格納される記憶領域がホストメモリ上の優先置換領域となる。
【０３１５】
以下では、キャッシュ５１が５ウェイ・セットアソシアティブ・キャッシュである場合を想定する。各セットの５つのウェイに対応する５つのキャッシュラインの各々には、０から４の値（優先度）のいずれかを示すユーゼージ情報が割り当てられる。ここでは、ユーゼージ情報の値（優先度）が小さいほど、最近アクセスされたキャッシュライン（つまり、置換されにくいキャッシュライン）である場合を想定する。
【０３１６】
いま、あるセットの５つのウェイに対応する５つのキャッシュラインＡ，Ｂ，Ｃ，Ｄ，Ｅに対して、値０のユーゼージ情報、値２のユーゼージ情報、値３のユーゼージ情報、値４のユーゼージ情報、値１のユーゼージ情報が割り当てられている場合を想定する。優先置換領域へライトされるべきデータの格納先キャッシュライン（格納先ウェイ番号）がＣであるならば、このデータがキャッシュラインＣに格納されるとともに、このキャッシュラインＣのユーゼージ情報の値は、キャッシュラインＣを最も置換されやすくする最大値（ここでは４）に更新される。キャッシュラインＣの元のユーゼージ情報の値（ここでは３）よりも大きい値のユーゼージ情報が割り当てられているキャッシュラインＤについては、そのユーゼージ情報の値は、１つ新しい方に更新される。ここでは、キャッシュラインＤのユーゼージ情報は、その元の値４から１を引くことによって得られる値３に更新される。キャッシュラインＣの元のユーゼージ情報の値（ここでは３）よりも小さい値のユーゼージ情報が割り当てられているキャッシュラインＡ，Ｂ，Ｅについては、そのユーゼージ情報の値は更新されずに元の値に維持される。
【０３１７】
図４１に示されているように、優先置換領域へライトされるべきデータの格納先キャッシュライン（格納先ウェイ番号）がＢであるならば、このデータがキャッシュラインＢに格納されるとともに、このキャッシュラインＢのユーゼージ情報の値は、キャッシュラインＢを最も置換されやすくするための最大値（ここでは４）に更新される。キャッシュラインＢの元のユーゼージ情報の値（ここでは２）よりも大きい値のユーゼージ情報が割り当てられているキャッシュラインＣ、Ｄについては、そのユーゼージ情報の値は、１つ新しい方にそれぞれ更新される。ここでは、キャッシュラインＣのユーゼージ情報は、その元の値３から１を引くことによって得られる値２に更新される。キャッシュラインＤのユーゼージ情報は、その元の値４から１を引くことによって得られる値３に更新される。キャッシュラインＢの元のユーゼージ情報の値（ここでは２）よりも小さい値のユーゼージ情報が割り当てられているキャッシュラインＡ，Ｅについては、そのユーゼージ情報の値は更新されずに元の値に維持される。
【０３１８】
図４２は、優先置換領域以外のホストメモリ上の領域へのライトデータに対しては対応するキャッシュラインを置換され難くするユーゼージ情報を割り当てる動作を示す。
【０３１９】
第５実施形態では、特定のアドレス範囲（アドレスＡからアドレスＢまでのアドレス範囲）を有する記憶領域、つまりアドレス変換テーブルキャッシュ３１が格納される記憶領域がホストメモリ上の優先置換領域以外の領域となる。
【０３２０】
図４２に示されているように、優先置換領域以外の領域（アドレス変換テーブルキャッシュ３１が格納される記憶領域）へライトされるべきデータ（テーブルデータ）の格納先キャッシュライン（格納先ウェイ番号）がＣであるならば、このテーブルデータがキャッシュラインＣに格納されるとともに、このキャッシュラインＣのユーゼージ情報の値は、キャッシュラインＣを最も置換され難くする値（ここでは０）に更新される。キャッシュラインＣの元のユーゼージ情報の値（ここでは３）よりも小さい値のユーゼージ情報が割り当てられているキャッシュラインＡ、Ｂ、Ｅについては、そのユーゼージ情報の値は、１つ旧い方にそれぞれ更新される。ここでは、キャッシュラインＡのユーゼージ情報は、その元の値０に１を加算することによって得られる値１に更新される。キャッシュラインＢのユーゼージ情報は、その元の値２に１を加算することによって得られる値３に更新される。キャッシュラインＥのユーゼージ情報は、その元の値１に１を加算することによって得られる値２に更新される。キャッシュラインＣの元のユーゼージ情報の値（ここでは２）よりも大きい値のユーゼージ情報が割り当てられているキャッシュラインＤについては、そのユーゼージ情報の値は更新されずに元の値に維持される。
【０３２１】
キャッシュラインＣがアドレス範囲（アドレスＡからアドレスＢまでのアドレス範囲）に属するリードアドレスを含むリード要求によってリードアクセスされた場合も、上記と同様のユーゼージ情報更新動作が実行される。
【０３２２】
また、図４３に示されているように、優先置換領域以外の領域（アドレス変換テーブルキャッシュ３１が格納される記憶領域）へライトされるべきデータ（テーブルデータ）の格納先キャッシュライン（格納先ウェイ番号）がＢであるならば、このテーブルデータがキャッシュラインＢに格納されるとともに、このキャッシュラインＢのユーゼージ情報の値は、キャッシュラインＢを最も置換され難くする値（ここでは０）に更新される。キャッシュラインＢの元のユーゼージ情報の値（ここでは２）よりも小さい値のユーゼージ情報が割り当てられているキャッシュラインＡ、Ｅについては、そのユーゼージ情報の値は、１つ旧い方にそれぞれ更新される。ここでは、キャッシュラインＡのユーゼージ情報は、その元の値０に１を加算することによって得られる値１に更新される。キャッシュラインＥのユーゼージ情報は、その元の値１に１を加算することによって得られる値２に更新される。キャッシュラインＢの元のユーゼージ情報の値（ここでは２）よりも大きい値のユーゼージ情報が割り当てられているキャッシュラインＣ，Ｄについては、そのユーゼージ情報の値は更新されずに元の値に維持される。
【０３２３】
キャッシュラインＢがアドレス範囲（アドレスＡからアドレスＢまでのアドレス範囲）に属するリードアドレスを含むリード要求によってリードアクセスされた場合も、上記と同様のユーゼージ情報更新動作が実行される。
【０３２４】
図４４のフローチャートは、図３５のキャッシュ５１（キャッシュコントローラ５１Ｂ）によって実行されるユーゼージ情報更新動作の手順を示す。
【０３２５】
キャッシュ５１のキャッシュコントローラ５１ＢがＣＰＵ１２またはハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａからデータのライト要求を受信した時、キャッシュコントローラ５１Ｂは、キャッシュ領域６１Ａ内の或るキャッシュラインに、このデータを書き込む（ステップＳ１８１）。キャッシュコントローラ５１Ｂは、このライト要求によって指定されるライトアドレスが優先置換領域に対応する特定のアドレス範囲に属するか否かを判定する（ステップＳ１８２）。
【０３２６】
このライトアドレスが特定のアドレス範囲に属するならば（ステップＳ１８２のＹＥＳ）、キャッシュコントローラ５１Ｂは、データが書き込まれたキャッシュラインに対応するユーゼージ情報を最も旧い値（最大値）に更新する（ステップＳ１８３）。
【０３２７】
一方、このライトアドレスが特定のアドレス範囲に属さないならば（ステップＳ１８２のＮＯ）、キャッシュコントローラ５１Ｂは、データが書き込まれたキャッシュラインに対応するユーゼージ情報を最も新しい値（最小値）に更新する（ステップＳ１８４）。
【０３２８】
ステップＳ１８３またはＳ１８４の後、キャッシュコントローラ５１Ｂは、データが書き込まれたキャッシュラインが属するセット内の他のウェイ（他のキャッシュライン）にそれぞれ対応するユーゼージ情報を必要に応じて更新する（ステップＳ１８５）。
【０３２９】
図４５のフローチャートは、キャッシュ５１（キャッシュコントローラ５１Ｂ）によって実行されるユーゼージ情報更新動作の一連の手順の例を示す。
【０３３０】
図４５においても、キャッシュ５１が５ウェイ・セットアソシアティブ・キャッシュである場合が想定されている。つまり、ウェイ数は５であり、ウェイ番号は０〜４であり、ユーゼージ情報は０（新）〜４（旧）である。また、図４５において、ｖａｌｉｄ（ｉ）はウェイ番号ｉ（キャッシュラインｉ）の有効フラグ（バリッドビットＶＢ）を表し、ｕｓａｇｅ（ｉ）はウェイ番号ｉ（キャッシュラインｉ）のユーゼージ情報の値（優先度）を表している。
【０３３１】
ＣＰＵ１２またはハードウェアアクセラレータ５２Ａまたは５２Ｂからのライト要求を受け取ると、キャッシュ５１のキャッシュコントローラ５１Ｂは、ライトすべきデータ（ライトデータ）に対応するアドレス（ライトアドレス）によって定まる特定のセットの５つのウェイから、ライトデータが格納されるべきキャッシュライン（つまり、格納先ウェイ番号（ｎ））を決定する（ステップＳ１９１）。そして、キャッシュコントローラ５１Ｂは、ライトアドレスが優先置換領域に対応する特定のアドレス範囲に属するか否かを判定する（ステップＳ１９２）。
【０３３２】
ライトアドレスが優先置換領域に対応する特定のアドレス範囲に属さないならば、つまりライトデータがアドレス変換テーブルキャッシュに格納すべきデータ（テーブルデータ）であるならば（ステップＳ１９２のＮＯ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉがウェイ数（＝５）よりも小さいか否かを判定する（ステップＳ１９３）。現在のウェイ番号ｉがウェイ数よりも小さいならば（ステップＳ１９３のＹＥＳ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉを初期値０から１ずつインクリメントしながら、以下のステップＳ１９４〜Ｓ１９９の処理を繰り返し実行する。
【０３３３】
まず、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉが格納先ウェイ番号（ｎ）に一致するか否かを判定する（ステップＳ１９４）。
【０３３４】
現在のウェイ番号ｉが格納先ウェイ番号（ｎ）に一致するならば（ステップＳ１９４のＹＥＳ）、キャッシュコントローラ５１Ｂは、格納先ウェイ番号（ｎ）に対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｎ））を最小値（ここでは０）に更新する（ステップＳ１９５）。
【０３３５】
現在のウェイ番号ｉが格納先ウェイ番号（ｎ）に一致しないならば（ステップＳ１９４のＮＯ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのバリッドビットが“１”であるかどうか、つまり現在のウェイ番号ｉのキャッシュラインが有効であるか否かを判定する（ステップＳ１９６）。
【０３３６】
現在のウェイ番号ｉに対応するキャッシュラインが有効でないならば（ステップＳ１９６のＮＯ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉを１だけ増やし、ステップＳ１９３の処理に戻る。
【０３３７】
現在のウェイ番号ｉに対応するキャッシュラインが有効であるならば（ステップＳ１９６のＹＥＳ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｉ））がユーゼージ情報（ｕｓａｇｅ（ｉ））よりも小さく、且つこのユーゼージ情報（ｕｓａｇｅ（ｉ））が最大値（４）よりも小さい、という条件が満たされるか否かを判定する（ステップＳ１９７）。
【０３３８】
この条件が満たされるならば（ステップＳ１９７のＹＥＳ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｉ））を１つ旧い方に更新する（ステップＳ１９８）。ステップＳ１９８では、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｉ））を、「ｕｓａｇｅ（ｉ）＋１」に更新する。
【０３３９】
一方、この条件が満たされないならば（ステップＳ１９７のＮＯ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｉ））を更新せずに元の値に維持する（ステップＳ１９９）。
【０３４０】
ステップＳ１９８またはステップＳ１９９の処理を実行した後、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉを１だけ増やし、ステップＳ１９３の処理に戻る。
【０３４１】
このようにして、ライトデータのライトアドレスが優先置換領域に対応するアドレス範囲に属さない場合には、このライトデータが格納されるキャッシュラインに対しては最も置換され難い値（＝最小値）のユーゼージ情報が割り当てられる。
【０３４２】
次に、ライトアドレスが優先置換領域に対応するアドレス範囲に属する場合に実行されるユーゼージ情報更新動作について説明する。
【０３４３】
ライトアドレスが優先置換領域に対応するアドレス範囲に属するならば、つまりライトデータがアドレス変換テーブルキャッシュに格納すべきデータ（テーブルデータ）以外のデータ（例えばパリティ）であるならば（ステップＳ１９２のＹＥＳ）、キャッシュ５１は、現在のウェイ番号ｉがウェイ数よりも小さいか否かを判定する（ステップＳ２００）。現在のウェイ番号ｉがウェイ数よりも小さいならば（ステップＳ２００のＹＥＳ）、キャッシュコントローラ５１Ｂは、ウェイ番号ｉを初期値０から１ずつインクリメントしながら、以下のステップＳ２０１〜Ｓ２０６の処理を繰り返し実行する。
【０３４４】
まず、キャッシュ５１は、現在のウェイ番号ｉが格納先ウェイ番号（ｎ）に一致するか否かを判定する（ステップＳ２０１）。
【０３４５】
現在のウェイ番号ｉが格納先ウェイ番号（ｎ）に一致するならば（ステップＳ２０１のＹＥＳ）、キャッシュコントローラ５１Ｂは、格納先ウェイ番号（ｎ）に対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｎ））を最大値（ここでは４）に更新する（ステップＳ２０２）。
【０３４６】
現在のウェイ番号ｉが格納先ウェイ番号（ｎ）に一致しないならば（ステップＳ２０１のＮＯ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのバリッドビットが“１”であるかどうか、つまり現在のウェイ番号ｉのキャッシュラインが有効であるか否かを判定する（ステップＳ２０３）。
【０３４７】
現在のウェイ番号ｉに対応するキャッシュラインが有効でないならば（ステップＳ２０３のＮＯ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉを１だけ増やし、ステップＳ２００の処理に戻る。
【０３４８】
現在のウェイ番号ｉに対応するキャッシュラインが有効であるならば（ステップＳ２０３のＹＥＳ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｉ））がユーゼージ情報（ｕｓａｇｅ（ｉ））よりも大きいという条件が満たされるか否かを判定する（ステップＳ１９７）。
【０３４９】
この条件が満たされるならば（ステップＳ２０４のＹＥＳ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｉ））を１つ新しい方に更新する（ステップＳ２０５）。ステップＳ２０５では、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｉ））を、「ｕｓａｇｅ（ｉ）−１」に更新する。
【０３５０】
一方、この条件が満たされないならば（ステップＳ２０４のＮＯ）、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉに対応するキャッシュラインのユーゼージ情報（ｕｓａｇｅ（ｉ））を更新せずに元の値に維持する（ステップＳ２０６）。
【０３５１】
ステップＳ２０５またはステップＳ２０６の処理を実行した後、キャッシュコントローラ５１Ｂは、現在のウェイ番号ｉを１だけ増やし、ステップＳ２００の処理に戻る。
【０３５２】
このようにして、ライトデータのライトアドレスが優先置換領域に対応するアドレス範囲に属する場合には、このライトデータが格納されるキャッシュラインに対して、最も置換され易い値（＝最大値）のユーゼージ情報が割り当てられる。
【０３５３】
なお、第５実施形態では、キャッシュコントローラ５１Ｂは、指定されたアドレス範囲に対応する優先置換領域に書き込むべきデータをキャッシュ領域６１Ａのキャッシュラインに格納する時に、このキャッシュラインを最も置換され易くする値（このキャッシュラインを最も置換され易くする優先度）のユーゼージ情報をこのキャッシュラインに割り当てたが、このキャッシュラインに対してこのキャッシュラインを２番目に置換されやすくする値（＝３）を割り当ててもよい。
【０３５４】
また、キャッシュコントローラ５１Ｂは、優先置換領域内のデータを保持するキャッシュラインがリードされる場合には、このキャッシュラインのユーゼージ情報の値（優先度）を更新しなくてもよい。一方、優先置換領域に属さないデータ（アドレス変換テーブルキャッシュ３１のテーブルデータ）を保持するキャッシュラインがリードされる場合には、キャッシュコントローラ５１Ｂは、このキャッシュラインのユーゼージ情報の値（優先度）を最も置換され易い値（＝最大値）に更新してもよい。
【０３５５】
また、キャッシュコントローラ５１Ｂは、自身の一つのキャッシュラインに格納されるべき第１のデータ（ライトデータ）をハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂから受信した場合、この一つのキャッシュラインに対応するキャッシュタグ領域６１Ｂのエントリーに、入れ替え（置換）されやすい値の優先度を格納してもよい。この場合、キャッシュ５１は、パリティをホストメモリに書き込むように構成されたハードウェアアクセラレータ（ＨＷＡ＃２）５２Ｂからのライト要求に応じてデータをキャッシュ領域６１Ａのキャッシュラインに格納する時には、最も置換され易い値（最も置換され易い優先度）のユーゼージ情報をこのキャッシュラインに対応するキャッシュタグ領域６１Ｂのエントリーに格納し、アドレス変換テーブル７のテーブルデータをホストメモリ（アドレス変換テーブルキャッシュ３１）に書き込むように構成されたハードウェアアクセラレータ（ＨＷＡ＃１）５２Ａからのライト要求に応じてデータをキャッシュ領域６１Ａのキャッシュラインに格納する時には、最も置換され難い値（最も置換され難い優先度）のユーゼージ情報をこのキャッシュラインに対応するキャッシュタグ領域６１Ｂのエントリーに格納してもよい。
【０３５６】
また、第５実施形態においても、アドレス変換テーブルキャッシュ３１内の入れ替え対象キャッシュラインを決定する際には、第１実施形態〜第４実施形態で説明した構成および処理手順を適用することができる。
【０３５７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０３５８】
２…ホスト、３…ストレージデバイス、４…コントローラ、５…ＮＡＮＤ型フラッシュメモリ、７…アドレス変換テーブル（論理物理アドレス変換テーブル）、３１…アドレス変換テーブルキャッシュ、３２…アドレス変換テーブルキャッシュタグ、５１…ホストメモリ用のキャッシュ。
【図１】
2019133252.tif 000003
【図２】
2019133252.tif 000004
【図３】
2019133252.tif 000005
【図４】
2019133252.tif 000006
【図５】
2019133252.tif 000007
【図６】
2019133252.tif 000008
【図７】
2019133252.tif 000009
【図８】
2019133252.tif 000010
【図９】
2019133252.tif 000011
【図１０】
2019133252.tif 000012
【図１１】
2019133252.tif 000013
【図１２】
2019133252.tif 000014
【図１３】
2019133252.tif 000015
【図１４】
2019133252.tif 000016
【図１５】
2019133252.tif 000017
【図１６】
2019133252.tif 000018
【図１７】
2019133252.tif 000019
【図１８】
2019133252.tif 000020
【図１９】
2019133252.tif 000021
【図２０】
2019133252.tif 000022
【図２１】
2019133252.tif 000023
【図２２】
2019133252.tif 000024
【図２３】
2019133252.tif 000025
【図２４】
2019133252.tif 000026
【図２５】
2019133252.tif 000027
【図２６】
2019133252.tif 000028
【図２７】
2019133252.tif 000029
【図２８】
2019133252.tif 000030
【図２９】
2019133252.tif 000031
【図３０】
2019133252.tif 000032
【図３１】
2019133252.tif 000033
【図３２】
2019133252.tif 000034
【図３３】
2019133252.tif 000035
【図３４】
2019133252.tif 000036
【図３５】
2019133252.tif 000037
【図３６】
2019133252.tif 000038
【図３７】
2019133252.tif 000039
【図３８】
2019133252.tif 000040
【図３９】
2019133252.tif 000041
【図４０】
2019133252.tif 000042
【図４１】
2019133252.tif 000043
【図４２】
2019133252.tif 000044
【図４３】
2019133252.tif 000045
【図４４】
2019133252.tif 000046
【図４５】
2019133252.tif 000047