(57)【要約】  アクセス頻度が高いデータのみをキャッシュストレージに登録する。  キャッシュストレージは、メインストレージに記憶されるデータの一部を記憶する。キャッシュ管理部は、キャッシュストレージのキャッシュエントリ毎に、アクセス頻度を保持する。候補キャッシュ管理部は、キャッシュストレージに登録されていない候補エントリ毎に、アクセス頻度を保持する。キャッシュ更新部は、発行されたアクセスコマンドのアドレスに応じてアクセス頻度を更新して、アクセス頻度に基づいてキャッシュエントリおよび前記候補エントリを更新する。
2020021791.tif 000002
【特許請求の範囲】
【請求項１】
メインストレージに記憶されるデータの一部を記憶するキャッシュストレージのキャッシュエントリ毎にアクセス頻度を保持するキャッシュ管理部と、
前記キャッシュストレージに登録されていない候補エントリ毎に前記アクセス頻度を保持する候補キャッシュ管理部と、
発行されたアクセスコマンドのアドレスに応じて前記アクセス頻度を更新して、前記アクセス頻度に基づいて前記キャッシュエントリおよび前記候補エントリを更新するキャッシュ更新部と
を具備する記憶制御装置。
【請求項２】
前記キャッシュ更新部は、前記発行されたアクセスコマンドのアドレスが前記キャッシュエントリおよび前記候補エントリの何れにも登録されていない場合には、そのアドレスを前記候補エントリに登録して、その候補エントリの前記アクセス頻度に初期値を設定する
請求項１記載の記憶制御装置。
【請求項３】
前記キャッシュ更新部は、前記候補エントリの前記アクセス頻度が所定のキャッシュイン閾値よりも高くなると、前記候補エントリを前記キャッシュストレージの前記キャッシュエントリとして登録させて、前記メインストレージの対応するデータを前記キャッシュストレージに記憶させる
請求項１記載の記憶制御装置。
【請求項４】
前記キャッシュ更新部は、前記アクセス頻度が前記キャッシュイン閾値よりも高くなった前記候補エントリを前記キャッシュストレージの前記キャッシュエントリとして登録させる際に、元の前記候補エントリを削除する
請求項３記載の記憶制御装置。
【請求項５】
前記キャッシュ更新部は、前記キャッシュエントリの前記アクセス頻度が所定のキャッシュアウト閾値よりも低くなると、そのキャッシュエントリを前記キャッシュストレージからの削除候補とする
請求項１記載の記憶制御装置。
【請求項６】
前記キャッシュ更新部は、前記キャッシュエントリの前記アクセス頻度が所定のライトバック開始閾値よりも低くなると、そのキャッシュエントリの前記キャッシュストレージにおけるデータが前記メインストレージと不一致であれば、そのデータを前記キャッシュストレージから前記メインストレージに転送する
請求項１記載の記憶制御装置。
【請求項７】
前記キャッシュ更新部は、前記候補エントリの前記アクセス頻度が所定の候補キャッシュアウト閾値よりも低くなると、その候補エントリを削除候補とする
請求項１記載の記憶制御装置。
【請求項８】
前記キャッシュ更新部は、前記発行されたアクセスコマンドのアドレスが前記キャッシュエントリまたは前記候補エントリの何れかに登録されている場合には、そのエントリの前記アクセス頻度の値をより高くして、それ以外のエントリの前記アクセス頻度の値をより低くする
請求項１記載の記憶制御装置。
【請求項９】
メインストレージと、
前記メインストレージに記憶されるデータの一部を記憶するキャッシュストレージと、
前記キャッシュストレージのキャッシュエントリ毎にアクセス頻度を保持するキャッシュ管理部と、
前記キャッシュストレージに登録されていない候補エントリ毎に前記アクセス頻度を保持する候補キャッシュ管理部と、
発行されたアクセスコマンドのアドレスに応じて前記アクセス頻度を更新して、前記アクセス頻度に基づいて前記キャッシュエントリおよび前記候補エントリを更新するキャッシュ更新部と
を具備する記憶装置。
【請求項１０】
前記キャッシュストレージは、書込み回数に上限を有する不揮発性メモリである
請求項９記載の記憶装置。
【請求項１１】
ホストコンピュータと、
メインストレージと、
前記メインストレージに記憶されるデータの一部を記憶するキャッシュストレージと、
前記キャッシュストレージのキャッシュエントリ毎にアクセス頻度を保持するキャッシュ管理部と、
前記キャッシュストレージに登録されていない候補エントリ毎に前記アクセス頻度を保持する候補キャッシュ管理部と、
前記ホストコンピュータによって発行されたアクセスコマンドのアドレスに応じて前記アクセス頻度を更新して、前記アクセス頻度に基づいて前記キャッシュエントリおよび前記候補エントリを更新するキャッシュ更新部と
を具備する情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、記憶制御装置に関する。詳しくは、キャッシュストレージを制御する記憶制御装置、および、その記憶制御装置を含む記憶装置および情報処理システムに関する。
【背景技術】
【０００２】
キャッシュメモリ（キャッシュストレージ）のキャッシュエントリを管理するために、最も長く参照されていないキャッシュエントリをリプレース対象とするＬＲＵ（Least Recently Used）方式が知られている。このＬＲＵ方式では、キャッシュメモリの直近の参照順序のみを考慮しているため、アクセス頻度の高いデータであってもリプレース対象にされるおそれがある。そのため、アクセス頻度を考慮したキャッシュメモリの制御方法が提案されている。例えば、あるウェイに連続してアクセスがあった場合にそのウェイのアクセス頻度ビットをセットして、それ以外のウェイをリプレースするように制御するキャッシュメモリ制御装置が提案されている（例えば、特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０００−０４７９４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述の従来技術では、キャッシュメモリに残すべきデータを決定しており、キャッシュメモリに新たに登録されるデータとしては、最も直近にアクセスの発生したデータが選択される。しかしながら、新たに登録されたデータがキャッシュヒットするか否かは不明であり、もしキャッシュヒットが期待できないデータをキャッシュメモリに登録してしまうと、メモリとキャッシュメモリとの間で煩雑なデータの移動が生じることになる。そして、これにより、ホストコンピュータからのキャッシュメモリへのアクセスを妨げてしまい、アクセス低下の要因となり得る。また、キャッシュメモリとして不揮発性メモリを使用した場合、書込み回数に上限を有するため、煩雑なデータの移動が繰り返されると、書込み回数が増加して、寿命を短くしてしまうおそれがある。【０００５】
本技術はこのような状況に鑑みて生み出されたものであり、キャッシュストレージに登録する前にアクセス頻度を確認し、アクセス頻度が高いデータのみをキャッシュストレージに登録することを目的とする。
【課題を解決するための手段】
【０００６】
本技術は、上述の問題点を解消するためになされたものであり、その第１の側面は、メインストレージに記憶されるデータの一部を記憶するキャッシュストレージのキャッシュエントリ毎にアクセス頻度を保持するキャッシュ管理部と、上記キャッシュストレージに登録されていない候補エントリ毎に上記アクセス頻度を保持する候補キャッシュ管理部と、発行されたアクセスコマンドのアドレスに応じて上記アクセス頻度を更新して、上記アクセス頻度に基づいて上記キャッシュエントリおよび上記候補エントリを更新するキャッシュ更新部とを具備する記憶制御装置、記憶装置および情報処理システムである。これにより、アクセス頻度に基づいてキャッシュストレージのキャッシュエントリおよび候補キャッシュの候補エントリを更新するという作用をもたらす。【０００７】
また、この第１の側面において、上記キャッシュ更新部は、上記発行されたアクセスコマンドのアドレスが上記キャッシュエントリおよび上記候補エントリの何れにも登録されていない場合には、そのアドレスを上記候補エントリに登録して、その候補エントリの上記アクセス頻度に初期値を設定するようにしてもよい。これにより、アクセスコマンドのアドレスが未登録の場合には、まず候補エントリに登録するという作用をもたらす。【０００８】
また、この第１の側面において、上記キャッシュ更新部は、上記候補エントリの上記アクセス頻度が所定のキャッシュイン閾値よりも高くなると、上記候補エントリを上記キャッシュストレージの上記キャッシュエントリとして登録させて、上記メインストレージの対応するデータを上記キャッシュストレージに記憶させるようにしてもよい。これにより、アクセス頻度がキャッシュイン閾値よりも高くなった際に、データをキャッシュストレージに記憶させるという作用をもたらす。【０００９】
また、この場合において、上記キャッシュ更新部は、上記アクセス頻度が上記キャッシュイン閾値よりも高くなった上記候補エントリを上記キャッシュストレージの上記キャッシュエントリとして登録させる際に、元の上記候補エントリを削除するようにしてもよい。【００１０】
また、この第１の側面において、上記キャッシュ更新部は、上記キャッシュエントリの上記アクセス頻度が所定のキャッシュアウト閾値よりも低くなると、そのキャッシュエントリを上記キャッシュストレージからの削除候補とするようにしてもよい。これにより、アクセス頻度がキャッシュアウト閾値よりも低くなった際に、キャッシュストレージからの削除予定とするという作用をもたらす。【００１１】
また、この第１の側面において、上記キャッシュ更新部は、上記キャッシュエントリの上記アクセス頻度が所定のライトバック開始閾値よりも低くなると、そのキャッシュエントリの上記キャッシュストレージにおけるデータが上記メインストレージと不一致であれば、そのデータを上記キャッシュストレージから上記メインストレージに転送するようにしてもよい。これにより、キャッシュストレージから削除される前の段階において、ライトバック開始閾値よりも低くなった際に、キャッシュストレージへのライトバックを行うという作用をもたらす。【００１２】
また、この第１の側面において、上記キャッシュ更新部は、上記候補エントリの上記アクセス頻度が所定の候補キャッシュアウト閾値よりも低くなると、その候補エントリを削除候補とするようにしてもよい。これにより、アクセス頻度が所定の候補キャッシュアウト閾値よりも低くなった際に、候補キャッシュからの削除予定とするという作用をもたらす。【００１３】
また、この第１の側面において、上記キャッシュ更新部は、上記発行されたアクセスコマンドのアドレスが上記キャッシュエントリまたは上記候補エントリの何れかに登録されている場合には、そのエントリの上記アクセス頻度の値をより高くして、それ以外のエントリの上記アクセス頻度の値をより低くするようにしてもよい。これにより、キャッシュストレージまたは候補キャッシュにおけるキャッシュヒットの状態に応じてアクセス頻度の値を更新するという作用をもたらす。【００１４】
また、この第１の側面において、上記キャッシュストレージは、書込み回数に上限を有する不揮発性メモリであってもよい。この場合、キャッシュストレージにおけるキャッシュヒットが期待されるデータを選んで登録することにより、書込み回数を減らして、寿命を延ばすという作用をもたらす。
【発明の効果】
【００１５】
本技術によれば、アクセス頻度が高いデータのみをキャッシュストレージに登録することができるという優れた効果を奏し得る。なお、ここに記載された効果は必ずしも限定されるものではなく、本開示中に記載されたいずれかの効果であってもよい。
【図面の簡単な説明】
【００１６】
【図１】本技術の実施の形態における情報処理システムの全体構成の一例を示す図である。
【図２】本技術の実施の形態におけるストレージコントローラ２００の構成の一例を示す図である。
【図３】本技術の実施の形態におけるキャッシュ管理テーブル２１０およびキャッシュアドレス比較部２２０の構成の一例を示す図である。
【図４】本技術の実施の形態における候補キャッシュ管理テーブル２７０および候補キャッシュアドレス比較部２８０の構成の一例を示す図である。
【図５】本技術の実施の形態におけるキャッシュストレージ４００および候補キャッシュとアクセス頻度との関係例を示す図である。
【図６】本技術の実施の形態のキャッシュリプレースアルゴリズムにおける設定値の例を示す図である。
【図７】本技術の実施の形態のキャッシュリプレースアルゴリズムにおける閾値の例を示す図である。
【図８】本技術の実施の形態におけるストレージコントローラ２００のアクセス動作の処理手順例を示す流れ図である。
【図９】本技術の実施の形態におけるキャッシュ管理テーブル更新部２５０のキャッシュ更新処理の処理手順例を示す流れ図である。
【図１０】本技術の実施の形態におけるキャッシュ管理テーブル更新部２５０のライトバック判定処理の処理手順例を示す流れ図である。
【図１１】本技術の実施の形態における候補キャッシュ管理テーブル更新部２９０の候補キャッシュ更新処理の処理手順例を示す流れ図である。
【図１２】本技術の実施の形態におけるキャッシュ管理テーブル更新部２５０のキャッシュ登録処理の処理手順例を示す流れ図である。
【発明を実施するための形態】
【００１７】
以下、本技術を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．ハードウェア構成
２．キャッシュリプレースアルゴリズム
３．動作
【００１８】
＜１．ハードウェア構成＞
［情報処理システム］
図１は、本技術の実施の形態における情報処理システムの全体構成の一例を示す図である。この情報処理システムは、ホストコンピュータ１００と、ストレージコントローラ２００と、メインストレージ３００と、キャッシュストレージ４００とから構成される。ストレージコントローラ２００、メインストレージ３００およびキャッシュストレージ４００は、記憶装置５００を構成する。
【００１９】
ホストコンピュータ１００は、ストレージシステムに対してデータのリード処理やライト処理等を要求するコマンドを発行するものである。このホストコンピュータ１００は、信号線１０２により、ストレージコントローラ２００の動作を指示するコマンドとそのコマンドの操作対象を示すアドレスとをストレージコントローラ２００に送信する機能を有する。また、このホストコンピュータ１００は、図示しない信号線により、ストレージコントローラとの間のデータ送受信を行う機能を有する。
【００２０】
ストレージコントローラ２００は、ホストコンピュータ１００と通信してコマンドを受信し、メインストレージ３００またはキャッシュストレージ４００に対してリード処理またはライト処理を要求するものである。このストレージコントローラ２００は、信号線２０３により、メインストレージ３００の動作を指示するリクエストとそのリクエストの操作対象を示すアドレスとをメインストレージ３００に送信する。また、このストレージコントローラ２００は、信号線２０４により、キャッシュストレージ４００の動作を指示するリクエストとそのリクエストの操作対象を示すアドレスとをキャッシュストレージ４００に送信する。また、このストレージコントローラ２００は、図示しない信号線により、メインストレージ３００またはキャッシュストレージ４００とのデータ送受信を行う。
【００２１】
メインストレージ３００は、記憶装置５００としての全てのデータを記憶するストレージである。このメインストレージ３００は、キャッシュストレージ４００より大容量かつ応答速度が遅い記憶装置であり、例えば、ハードディスクや、ＮＡＮＤ型フラッシュメモリ等の不揮発性メモリが想定される。このメインストレージ３００は、ストレージコントローラ２００から信号線２０３を介して受けたリクエストに従ってデータの読出しまたは書込みを行う。
【００２２】
キャッシュストレージ４００は、アクセス頻度の高いデータを保持するストレージである。このキャッシュストレージ４００は、メインストレージ３００より小容量かつ応答速度が速い記憶装置であり、メインストレージ３００のキャッシュとして動作する。すなわち、このキャッシュストレージ４００には、メインストレージ３００のデータの一部が格納される。このキャッシュストレージ４００としては、例えば、抵抗変化型メモリ等の高速な不揮発性メモリが想定される。不揮発性メモリにおいては書込み回数に上限を有することが多いが、この実施の形態によりキャッシュヒットが期待されるデータを選んでキャッシュストレージ４００に登録することにより、キャッシュストレージ４００の書込み回数を減らして、寿命を延ばすことができる。このキャッシュストレージ４００は、ストレージコントローラ２００から信号線２０４を介して受けたリクエストに従ってデータの読出しまたは書込みを行う。
【００２３】
このようなシステム構成において、キャッシュストレージ４００にデータを登録する前に、アクセス頻度を確認し、アクセス頻度が高いデータのみをキャッシュストレージ４００に登録する。そのために、候補キャッシュを導入し、アクセス頻度を計測する。この候補キャッシュは、データを記憶せずに、アドレス情報やアクセス頻度を記憶する候補エントリを記憶する。
【００２４】
［ストレージコントローラ］
図２は、本技術の実施の形態におけるストレージコントローラ２００の構成の一例を示す図である。
【００２５】
このストレージコントローラ２００は、キャッシュ管理テーブル２１０と、キャッシュアドレス比較部２２０と、メインストレージ制御部２３０と、キャッシュストレージ制御部２４０と、キャッシュ管理テーブル更新部２５０と、キャッシュデータ更新部２６０と、候補キャッシュ管理テーブル２７０と、候補キャッシュアドレス比較部２８０と、候補キャッシュ管理テーブル更新部２９０とを備える。
【００２６】
キャッシュ管理テーブル２１０は、キャッシュストレージ４００を管理するためのキャッシュエントリを保持するテーブルである。なお、キャッシュ管理テーブル２１０は、特許請求の範囲に記載のキャッシュ管理部の一例である。
【００２７】
キャッシュアドレス比較部２２０は、ホストコンピュータ１００から指定されたアドレスと、キャッシュ管理テーブル２１０のキャッシュエントリのアドレスとを比較して、キャッシュヒットまたはミスヒットの判定を行うものである。
【００２８】
メインストレージ制御部２３０は、キャッシュアドレス比較部２２０における判定結果がキャッシュミスであった場合に、ホストコンピュータ１００から指定されたアドレスに基づいてメインストレージ３００にアクセスを行うものである。
【００２９】
キャッシュ管理テーブル更新部２５０は、キャッシュアドレス比較部２２０の判定結果に基づいてキャッシュ管理テーブル２１０上の該当するセットのキャッシュ管理情報を更新するものである。
【００３０】
キャッシュストレージ制御部２４０は、キャッシュ管理テーブル更新部２５０が出力するキャッシュアドレスに基づいて、キャッシュストレージ４００上のデータにアクセスを行うものである。
【００３１】
キャッシュデータ更新部２６０は、キャッシュ管理テーブル更新部２５０からの指示に基づいて、メインストレージ３００とキャッシュストレージ４００との間でデータ転送を行うものである。
【００３２】
候補キャッシュ管理テーブル２７０は、キャッシュストレージ４００に登録する前の、候補キャッシュの候補エントリを保持するテーブルである。なお、候補キャッシュ管理テーブル２７０は、特許請求の範囲に記載の候補キャッシュ管理部の一例である。
【００３３】
候補キャッシュアドレス比較部２８０は、ホストコンピュータ１００から指定されたアドレスと、候補キャッシュ管理テーブル２７０の候補キャッシュ管理情報（候補エントリ）に登録されたアドレスとを比較して、候補キャッシュに登録済か否かの判定を行うものである。
【００３４】
候補キャッシュ管理テーブル更新部２９０は、候補キャッシュアドレス比較部２８０による判定結果に基づいて、候補キャッシュ管理テーブル２７０上の該当するセットの候補キャッシュ管理情報を更新するものである。この候補キャッシュ管理テーブル更新部２９０は、候補キャッシュ管理情報に保持されるアクセス頻度を参照して、その候補エントリをキャッシュ管理テーブル２１０に登録するか否かを判定する。この候補キャッシュ管理テーブル更新部２９０による判定結果に基づいて、キャッシュ管理テーブル更新部２５０は、新たなアドレス情報をキャッシュ管理テーブル２１０に登録する。
【００３５】
なお、キャッシュ管理テーブル更新部２５０、候補キャッシュ管理テーブル更新部２９０、および、キャッシュデータ更新部２６０は、特許請求の範囲に記載のキャッシュ更新部の一例である。
【００３６】
図３は、本技術の実施の形態におけるキャッシュ管理テーブル２１０およびキャッシュアドレス比較部２２０の構成の一例を示す図である。
【００３７】
この例では、キャッシュストレージ４００の構成として４ウェイセットアソシアティブメモリを想定する。そして、キャッシュストレージ４００の総容量を６４ＭＢとし、４ＫＢ毎のページにより管理する。このキャッシュストレージ４００は、アドレスの一部をセットアドレスとして、アクセスされる。この例では、各セットには最大４つのキャッシュエントリが保持される。すなわち、１セット（ｓｅｔ）当たり４ウェイ（ｗａｙ）であるため、キャッシュストレージ４００全体で４０９６セットとなる。
【００３８】
メインストレージ３００の総容量を８ＧＢと想定し、これを４０９６セットで管理すると、１セット当たり２０４８ページとなる。すなわち、２０４８ページのうち最大４つのページがキャッシュストレージ４００に保持されることになる。
【００３９】
キャッシュ管理テーブル２１０の各ウェイに対応して記憶されるキャッシュエントリのキャッシュ管理情報は、例えば、１ビットの有効フラグ２１１と、２０ビットのアドレス情報２１２と、８ビットのアクセス頻度情報２１３と、１ビットのダーティフラグ２１４とを備える。
【００４０】
有効フラグ２１１は、そのキャッシュエントリが有効（バリッド）か否かを示すフラグである。例えば、有効フラグ２１１が「１」を示していればキャッシュエントリが「有効」であることを表し、「０」を示していればキャッシュエントリが「無効」であることを表す。
【００４１】
アドレス情報２１２は、そのキャッシュエントリに対応するアドレス部分（連想アドレス）を保持するものである。このアドレス情報２１２は、キャッシュアドレス比較部２２０によって参照され、ホストコンピュータ１００から指定されたアドレスのアドレス部分と比較される。
【００４２】
アクセス頻度情報２１３は、そのキャッシュエントリにおけるアクセス頻度を示す値を保持するものである。キャッシュエントリのリプレースの際には、この値が参照される。例えば、このアクセス頻度情報２１３の値がキャッシュアウト閾値を下回った場合には、そのキャッシュエントリはキャッシュ管理テーブル２１０からの削除候補（削除予定）となる。
【００４３】
ダーティフラグ２１４は、そのキャッシュエントリにおけるデータがメインストレージ３００と一致しているか否かを示すフラグである。例えば、ダーティフラグ２１４が「１」を示していれば不一致（ダーティ）であることを表し、「０」を示していれば一致していることを表す。メインストレージ３００とキャッシュストレージ４００との一致性（コヒーレンシ）を維持するためには、不一致状態にあるキャッシュエントリのデータをキャッシュストレージ４００からメインストレージ３００にライトバックする必要がある。このライトバックのタイミングについては後述する。
【００４４】
キャッシュアドレス比較部２２０は、４つの比較器２２１と、ヒット判定部２２２とを備える。比較器２２１は、ホストコンピュータ１００から指定されたアドレスのセットアドレスに従ってキャッシュ管理テーブル２１０から読み出された４つのアドレス情報２１２と、ホストコンピュータ１００から指定されたアドレスの一部である連想アドレスとを比較する。ヒット判定部２２２は、４つの比較器２２１の何れかにおいて一致が検出されると、キャッシュヒットである旨の判定結果を出力する。一方、４つの比較器２２１の何れにおいても一致が検出されない場合にはキャッシュミスである旨の判定結果を出力する。この判定結果は、キャッシュストレージ制御部２４０およびキャッシュ管理テーブル更新部２５０に供給される。なお、キャッシュアドレス比較部２２０において比較対象となるのは有効フラグ２１１が「有効」なキャッシュエントリのみであり、有効フラグ２１１が「無効」であることを示しているキャッシュエントリについては、アドレスが一致してもキャッシュヒットとは判定されない。
【００４５】
図４は、本技術の実施の形態における候補キャッシュ管理テーブル２７０および候補キャッシュアドレス比較部２８０の構成の一例を示す図である。
【００４６】
この例では、候補キャッシュの構成として８ウェイセットアソシアティブメモリを想定する。この候補キャッシュは、アクセス頻度を監視するためのものであるため、データの記憶領域は不要である。候補キャッシュ管理テーブル２７０は、１セット当たり８つの候補キャッシュ管理情報（候補エントリ）を保持する。
【００４７】
候補キャッシュ管理テーブル２７０の各ウェイに対応して記憶される候補エントリの候補キャッシュ管理情報は、例えば、１ビットの有効フラグ２７１と、２０ビットのアドレス情報２７２と、８ビットのアクセス頻度情報２７３とを備える。これらは、上述のキャッシュ管理テーブル２１０のキャッシュ管理情報と同様であるが、データ記憶領域がないため、ダーティフラグは備えていない。
【００４８】
候補キャッシュアドレス比較部２８０は、８つの比較器２８１と、ヒット判定部２８２とを備える。これらは、上述のキャッシュアドレス比較部２２０と同様である。ヒット判定部２８２は、８つの比較器２８１の何れかにおいて一致が検出されると、候補キャッシュに登録済である旨の判定結果を出力する。一方、８つの比較器２８１の何れにおいても一致が検出されない場合には、候補キャッシュに登録されていない旨の判定結果を出力する。
【００４９】
候補キャッシュに登録されていないアドレスが発生した場合には、候補キャッシュ管理テーブル２７０の該当するセットにおける候補エントリに新たに登録される。このとき、有効フラグ２７１が「無効」を示している候補エントリ、または、削除予定の候補エントリが使用される。
【００５０】
また、候補キャッシュに登録されている間に、アクセス頻度情報２７３がキャッシュイン閾値を超えた場合には、その候補エントリはキャッシュ管理テーブル２１０のキャッシュエントリに新たに登録される。このとき、有効フラグ２１１が「無効」を示しているキャッシュエントリ、または、削除予定のキャッシュエントリが使用される。また、キャッシュ管理テーブル２１０に登録されたキャッシュエントリについては、候補キャッシュから削除される。すなわち、有効フラグ２７１が「無効」に設定される。
【００５１】
一方、候補キャッシュに登録されている間に、アクセス頻度情報２７３が候補キャッシュアウト閾値を超えた場合には、その候補エントリはキャッシュ管理テーブル２１０に登録されることなく、候補キャッシュ管理テーブル２７０からの削除候補（削除予定）となる。
【００５２】
＜２．キャッシュリプレースアルゴリズム＞
［アクセス頻度情報］
図５は、本技術の実施の形態におけるキャッシュストレージ４００および候補キャッシュとアクセス頻度との関係例を示す図である。図６は、本技術の実施の形態のキャッシュリプレースアルゴリズムにおける設定値の例を示す図である。図７は、本技術の実施の形態のキャッシュリプレースアルゴリズムにおける閾値の例を示す図である。
【００５３】
この実施の形態においては、ホストコンピュータ１００から発行されたコマンドにおいて指定されたアドレスについて、すぐにはキャッシュストレージ４００に登録せずに、アクセス頻度を監視する。そのために、最初は候補キャッシュの候補キャッシュ管理テーブル２７０に登録される。このとき、アクセス頻度情報２７３の初期値として、例えば候補キャッシュ初期値「３２」が設定される。
【００５４】
候補キャッシュ管理テーブル２７０に登録された後、その候補エントリに合致するアクセスがあるたびにアクセス頻度情報２７３の値は増加する。例えば、キャッシュヒット時加算値「４」が加算されていく。一方、その候補エントリに合致しないアクセスがあるたびにアクセス頻度情報２７３の値は減少する。例えば、キャッシュミス時減算値「１」が減算されていく。
【００５５】
その結果、アクセス頻度情報２７３の値が増加してキャッシュイン閾値を超えると、その候補エントリはキャッシュ管理テーブル２１０のキャッシュエントリとして登録される。その場合、その候補エントリは候補キャッシュ管理テーブル２７０から削除される。アクセス頻度情報２７３の値は、アクセス頻度情報２１３としてそのまま引き継がれる。なお、このキャッシュイン閾値としては、例えば「４０」とする。
【００５６】
一方、アクセス頻度情報２７３の値が減少して候補キャッシュアウト閾値を下回ると、その候補エントリは候補キャッシュ管理テーブル２７０からの削除候補（削除予定）となる。候補キャッシュ管理テーブル２７０から速やかに削除するようにしてもよいが、他に登録されるものが発生するまで有効にしておいても問題はない。なお、この候補キャッシュアウト閾値としては、例えば「１６」とする。
【００５７】
キャッシュ管理テーブル２１０に登録された後も、そのキャッシュエントリに合致するアクセスがあるたびにアクセス頻度情報２１３の値は増加する。例えば、「４」が加算されていく。一方、そのキャッシュエントリに合致しないアクセスがあるたびにアクセス頻度情報２１３の値は減少する。例えば、「１」が減算されていく。
【００５８】
その結果、アクセス頻度情報２１３の値が減少してキャッシュアウト閾値を下回ると、その候補エントリはキャッシュ管理テーブル２１０からの削除候補（削除予定）となる。キャッシュ管理テーブル２１０から速やかに削除するようにしてもよいが、他に登録されるものが発生するまで有効にしておいても問題はない。なお、このキャッシュアウト閾値としては、例えば「８」とする。
【００５９】
また、キャッシュアウト閾値を下回る前に、ライトバック開始閾値を下回ったタイミングで、不一致状態にあるキャッシュエントリのデータをキャッシュストレージ４００からメインストレージ３００にライトバックする。これにより、キャッシュ管理テーブル２１０から削除する準備を予め行うことができる。なお、このライトバック開始閾値としては、例えば「１６」とする。
【００６０】
このように、アクセス頻度に応じてキャッシュストレージ４００および候補キャッシュにおけるエントリのリプレースが行われる。
【００６１】
［設定値］
ここで、上述の設定値について考察する。キャッシュストレージ４００のヒット率を８０％と想定すると、４ウェイセットアソシアティブメモリにおいては、４０回のアクセスのうち、１ウェイ当たりの平均ヒット回数は８回である。すなわち、４０回のアクセスのうち、８回キャッシュヒット、３２回ミスヒットとなる。この場合、候補キャッシュへの登録時の初期値を「３２」として、ミスヒットとなるたびに「１」を減算する一方で、キャッシュヒットの時の加算値Ｎとして、
Ｎ＝３２／８＝４
を設定することにより、想定するバランスが得られる。
【００６２】
なお、この実施の形態において示した設定値および閾値の数値例は、あくまで一例であり、適宜適切な値を用いてよいことはいうまでもない。また、アクセス頻度が高い場合にアクセス頻度情報の値が大きくなるように数値例を示したが、逆にアクセス頻度が低い場合にアクセス頻度情報の値が大きくなるようにしてもよい。ただし、その場合、閾値との大小関係も逆になる。
【００６３】
［アクセス頻度情報］
この実施の形態においては、アクセス頻度情報を新たに保持することになる。上述のように８ビット（１バイト）ずつの容量を想定すると、キャッシュ管理テーブル２１０においてセット毎に４ウェイ、候補キャッシュ管理テーブル２７０おいてセット毎に８ウェイであるため、
アクセス頻度情報の総量＝４０９６×（４＋８）＝４８Ｋバイト
となる。これは、キャッシュ全体のデータ量としては比較的少ないと考えられる。
【００６４】
＜３．動作＞
［アクセス動作］
図８は、本技術の実施の形態におけるストレージコントローラ２００のアクセス動作の処理手順例を示す流れ図である。
【００６５】
ホストコンピュータ１００からメモリアクセスコマンドが発行されると、ストレージコントローラ２００においてキャッシュ管理テーブル２１０が参照されて、キャッシュ管理テーブル更新部２５０によりキャッシュ更新処理が行われる（ステップＳ９１０）。キャッシュヒットした場合には（ステップＳ９２１：Ｙｅｓ）、キャッシュアドレスがキャッシュストレージ制御部２４０に出力される（ステップＳ９２２）。これにより、キャッシュストレージ４００にアクセスが行われる（ステップＳ９２３）。そして、候補キャッシュについても更新処理が行われる（ステップＳ８０１）。
【００６６】
一方、キャッシュミスヒットした場合には（ステップＳ９２１：Ｎｏ）、入力アドレスがメインストレージ制御部２３０に出力される（ステップＳ９２４）。これにより、メインストレージ３００にアクセスが行われる（ステップＳ９２５）。そして、候補キャッシュについても更新処理が行われる（ステップＳ８０２）。その結果、候補キャッシュからキャッシュストレージ４００への登録が発生した場合には（ステップＳ９２６：Ｙｅｓ）、以下のようにデータのコピー処理が行われる。すなわち、入力アドレスがメインストレージ制御部２３０に出力され（ステップＳ９２７）、キャッシュアドレスがキャッシュストレージ制御部２４０に出力される（ステップＳ９２８）。そして、メインストレージ３００からキャッシュストレージ４００にデータがコピーされる（ステップＳ９２９）。
【００６７】
その後、キャッシュストレージ４００においてライトバックを行う必要があるか否かが判定される（ステップＳ９３０）。その結果、ライトバックが発生した場合には（ステップＳ９４１：Ｙｅｓ）、以下のライトバック処理が行われる。すなわち、キャッシュアドレスがキャッシュストレージ制御部２４０に出力され（ステップＳ９４２）、入力アドレスがメインストレージ制御部２３０に出力される（ステップＳ９４３）。そして、キャッシュストレージ４００からメインストレージ３００にデータがコピーされる（ステップＳ９４４）。
【００６８】
［キャッシュ更新］
図９は、本技術の実施の形態におけるキャッシュ管理テーブル更新部２５０のキャッシュ更新処理（ステップＳ９１０）の処理手順例を示す流れ図である。
【００６９】
まず、ホストコンピュータ１００から発行されたアドレスからセットアドレスが算出される（ステップＳ９１１）。そして、このセットアドレスによりキャッシュ管理テーブル２１０のキャッシュ管理情報が参照される（ステップＳ９１２）。この例では、キャッシュストレージ４００として４ウェイセットアソシアティブメモリを想定しているため、４つのキャッシュエントリのキャッシュ管理情報が取得される。
【００７０】
取得された４つのキャッシュ管理情報のうち、ホストコンピュータ１００から発行されたアドレスと一致するウェイがあれば（ステップＳ９１３：Ｙｅｓ）、一致したウェイのアクセス頻度情報２１３の値に「４」を加算する（ステップＳ９１５）。この「４」は、上述のキャッシュヒット時加算値の一例である。そして、この一致したウェイ以外の３つのウェイのアクセス頻度情報２１３の値から「１」を減算する（ステップＳ９１６）。この「１」は、上述のキャッシュミス時減算値の一例である。なお、減算の際、アクセス頻度情報２１３が既に「０」であれば、減算は不要である。また、有効フラグ２１１が「無効」を示しているキャッシュ管理情報については、アクセス頻度情報２１３の更新は不要である。
【００７１】
一方、ホストコンピュータ１００から発行されたアドレスと一致するウェイがなければ（ステップＳ９１３：Ｎｏ）、４つのキャッシュ管理情報のアクセス頻度情報２１３の値からキャッシュミス時減算値の「１」を減算する（ステップＳ９１４）。なお、減算の際、アクセス頻度情報２１３が既に「０」であれば、減算は不要である。また、有効フラグ２１１が「無効」を示しているキャッシュ管理情報については、アクセス頻度情報２１３の更新は不要である。
【００７２】
なお、ホストコンピュータ１００から発行されたアドレスと一致するウェイがあれば（ステップＳ９１３：Ｙｅｓ）キャッシュヒットであり、一致するウェイがなければ（ステップＳ９１３：Ｎｏ）ミスヒットである。それぞれの結果がキャッシュストレージ制御部２４０およびキャッシュ管理テーブル更新部２５０に報告される。
【００７３】
［ライトバック判定］
図１０は、本技術の実施の形態におけるキャッシュ管理テーブル更新部２５０のライトバック判定処理（ステップＳ９３０）の処理手順例を示す流れ図である。
【００７４】
キャッシュ更新に伴い、キャッシュ管理テーブル２１０のキャッシュ管理情報が参照される（ステップＳ９３１）。そして、４つのキャッシュ管理情報のアクセス頻度情報２１３のうち、ライトバック開始閾値を下回るウェイがあるか否かが判断される（ステップＳ９３２）。
【００７５】
ライトバック開始閾値を下回るウェイがあり（ステップＳ９３２：Ｙｅｓ）、そのウェイのダーティフラグ２１４が「不一致」（ダーティ）を示している場合には（ステップＳ９３３：Ｙｅｓ）、ライトバックが発生したものと判定する。一方、ライトバック開始閾値を下回るウェイがなく（ステップＳ９３２：Ｎｏ）、または、ライトバック開始閾値を下回るウェイがあってもそのウェイのダーティフラグ２１４が「一致」を示している場合には（ステップＳ９３３：Ｎｏ）、ライトバックは発生しないものと判定する。
【００７６】
［候補キャッシュ更新］
図１１は、本技術の実施の形態における候補キャッシュ管理テーブル更新部２９０の候補キャッシュ更新処理（ステップＳ８０１、Ｓ８０２）の処理手順例を示す流れ図である。
【００７７】
まず、ホストコンピュータ１００から発行されたアドレスからセットアドレスが算出される（ステップＳ８１１）。そして、このセットアドレスにより候補キャッシュ管理テーブル２７０の候補キャッシュ管理情報が参照される（ステップＳ８１２）。この例では、候補キャッシュとして８ウェイセットアソシアティブメモリを想定しているため、８つの候補エントリの候補キャッシュ管理情報が取得される。
【００７８】
取得された８つの候補キャッシュ管理情報のうち、ホストコンピュータ１００から発行されたアドレスと一致するウェイがあれば（ステップＳ８１３：Ｙｅｓ）、一致したウェイのアクセス頻度情報２７３の値にキャッシュヒット時加算値の「４」を加算する（ステップＳ８１４）。その結果、アクセス頻度情報２７３の値がキャッシュイン閾値を超えると（ステップＳ８１５：Ｙｅｓ）、その候補エントリをキャッシュ管理テーブル２１０に登録する（ステップＳ９５０）。キャッシュ管理テーブル２１０への登録が完了すると（ステップＳ８１６：Ｙｅｓ）、元の候補エントリを候補キャッシュ管理テーブル２７０から削除する（ステップＳ８１７）。すなわち、有効フラグ２７１を「無効」にクリアする。また、一致したウェイ以外の７つのウェイのアクセス頻度情報２７３の値からキャッシュミス時減算値の「１」を減算する（ステップＳ８１８）。なお、減算の際、アクセス頻度情報２７３が既に「０」であれば、減算は不要である。また、有効フラグ２７１が「無効」を示しているキャッシュ管理情報については、アクセス頻度情報２７３の更新は不要である。
【００７９】
一方、ホストコンピュータ１００から発行されたアドレスと一致するウェイがなければ（ステップＳ８１３：Ｎｏ）、候補キャッシュへの登録を試みる。このとき、８つの候補キャッシュ管理情報の中に有効フラグ２７１が「無効」を示すウェイがあれば（ステップＳ８２１：Ｙｅｓ）、そのウェイに新たに登録を行う（ステップＳ８２２）。その際、その候補キャッシュ管理情報において、アドレス情報２７２には入力アドレスが設定され、アクセス頻度情報２７３には例えば候補キャッシュ初期値「３２」が設定され、有効フラグ２７１が「有効」に設定される。
【００８０】
８つの候補キャッシュ管理情報の中に有効フラグ２７１が「無効」を示すウェイがない場合には（ステップＳ８２１：Ｎｏ）、アクセス頻度情報２７３が「０」を示すウェイがあれば（ステップＳ８２３：Ｙｅｓ）、そのウェイに新たに登録を行う（ステップＳ８２４）。その際、その候補キャッシュ管理情報において、アドレス情報２７２には入力アドレスが設定され、アクセス頻度情報２７３には例えば候補キャッシュ初期値「３２」が設定される。
【００８１】
８つの候補キャッシュ管理情報の中に有効フラグ２７１が「無効」を示すウェイがなく（ステップＳ８２１：Ｎｏ）、アクセス頻度情報２７３が「０」を示すウェイもなければ（ステップＳ８２３：Ｎｏ）、候補キャッシュへの登録は行わない。
【００８２】
以上において、ホストコンピュータ１００から発行されたアドレスと一致するウェイがない場合（ステップＳ８１３：Ｎｏ）、アクセス頻度情報２７３の値がキャッシュイン閾値を超えない場合（ステップＳ８１５：Ｎｏ）、キャッシュ登録が完了しない場合（ステップＳ８１６：Ｎｏ）には、各ウェイのアクセス頻度情報２７３の値からキャッシュミス時減算値の「１」を減算する（ステップＳ８２８）。なお、減算の際、アクセス頻度情報２７３が既に「０」であれば、減算は不要である。また、有効フラグ２７１が「無効」を示しているキャッシュ管理情報については、アクセス頻度情報２７３の更新は不要である。
【００８３】
［キャッシュ登録］
図１２は、本技術の実施の形態におけるキャッシュ管理テーブル更新部２５０のキャッシュ登録処理（ステップＳ９５０）の処理手順例を示す流れ図である。
【００８４】
まず、ホストコンピュータ１００から発行されたアドレスからセットアドレスが算出される（ステップＳ９５１）。そして、このセットアドレスによりキャッシュ管理テーブル２１０のキャッシュ管理情報が参照される（ステップＳ９５２）。この例では、キャッシュストレージ４００として４ウェイセットアソシアティブメモリを想定しているため、４つのキャッシュエントリのキャッシュ管理情報が取得される。
【００８５】
取得された４つのキャッシュ管理情報のうち、有効フラグ２１１が「無効」を示すウェイがあれば（ステップＳ９５３：Ｙｅｓ）、そのウェイに登録が行われる（ステップＳ９５５）。その際、アドレス情報２１２には入力アドレスが設定され、アクセス頻度情報２１３には候補キャッシュのアクセス頻度情報２７３の値がコピーされる。
【００８６】
有効フラグ２１１が「無効」を示すウェイがない場合（ステップＳ９５３：Ｎｏ）、アクセス頻度情報２１３が「０」を示すウェイがあれば（ステップＳ９５４：Ｙｅｓ）、そのウェイに登録が行われる（ステップＳ９５５）。アクセス頻度情報２１３が「０」を示すウェイもなければ（ステップＳ９５４：Ｎｏ）、キャッシュ管理テーブル２１０への登録は行われない。
【００８７】
このように、本技術の実施の形態では、データをキャッシュストレージ４００に登録する前に、候補キャッシュ管理テーブル２７０を用いてアクセス頻度を監視して、キャッシュイン閾値を超えた際にキャッシュストレージ４００に登録する。これにより、キャッシュヒットが期待できるデータのみをキャッシュストレージ４００に登録することができる。
【００８８】
なお、上述の実施の形態は本技術を具現化するための一例を示したものであり、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本技術の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本技術は実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【００８９】
また、上述の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disc）、メモリカード、ブルーレイディスク（Blu-ray（登録商標）Disc）等を用いることができる。
【００９０】
なお、本明細書に記載された効果はあくまで例示であって、限定されるものではなく、また、他の効果があってもよい。
【００９１】
なお、本技術は以下のような構成もとることができる。
（１）メインストレージに記憶されるデータの一部を記憶するキャッシュストレージのキャッシュエントリ毎にアクセス頻度を保持するキャッシュ管理部と、
前記キャッシュストレージに登録されていない候補エントリ毎に前記アクセス頻度を保持する候補キャッシュ管理部と、
発行されたアクセスコマンドのアドレスに応じて前記アクセス頻度を更新して、前記アクセス頻度に基づいて前記キャッシュエントリおよび前記候補エントリを更新するキャッシュ更新部と
を具備する記憶制御装置。
（２）前記キャッシュ更新部は、前記発行されたアクセスコマンドのアドレスが前記キャッシュエントリおよび前記候補エントリの何れにも登録されていない場合には、そのアドレスを前記候補エントリに登録して、その候補エントリの前記アクセス頻度に初期値を設定する
前記（１）に記載の記憶制御装置。
（３）前記キャッシュ更新部は、前記候補エントリの前記アクセス頻度が所定のキャッシュイン閾値よりも高くなると、前記候補エントリを前記キャッシュストレージの前記キャッシュエントリとして登録させて、前記メインストレージの対応するデータを前記キャッシュストレージに記憶させる
前記（１）または（２）に記載の記憶制御装置。
（４）前記キャッシュ更新部は、前記アクセス頻度が前記キャッシュイン閾値よりも高くなった前記候補エントリを前記キャッシュストレージの前記キャッシュエントリとして登録させる際に、元の前記候補エントリを削除する
前記（３）に記載の記憶制御装置。
（５）前記キャッシュ更新部は、前記キャッシュエントリの前記アクセス頻度が所定のキャッシュアウト閾値よりも低くなると、そのキャッシュエントリを前記キャッシュストレージからの削除候補とする
前記（１）から（４）のいずれかに記載の記憶制御装置。
（６）前記キャッシュ更新部は、前記キャッシュエントリの前記アクセス頻度が所定のライトバック開始閾値よりも低くなると、そのキャッシュエントリの前記キャッシュストレージにおけるデータが前記メインストレージと不一致であれば、そのデータを前記キャッシュストレージから前記メインストレージに転送する
前記（１）から（５）のいずれかに記載の記憶制御装置。
（７）前記キャッシュ更新部は、前記候補エントリの前記アクセス頻度が所定の候補キャッシュアウト閾値よりも低くなると、その候補エントリを削除候補とする
前記（１）から（６）のいずれかに記載の記憶制御装置。
（８）前記キャッシュ更新部は、前記発行されたアクセスコマンドのアドレスが前記キャッシュエントリまたは前記候補エントリの何れかに登録されている場合には、そのエントリの前記アクセス頻度の値をより高くして、それ以外のエントリの前記アクセス頻度の値をより低くする
前記（１）から（７）のいずれかに記載の記憶制御装置。
（９）メインストレージと、
前記メインストレージに記憶されるデータの一部を記憶するキャッシュストレージと、
前記キャッシュストレージのキャッシュエントリ毎にアクセス頻度を保持するキャッシュ管理部と、
前記キャッシュストレージに登録されていない候補エントリ毎に前記アクセス頻度を保持する候補キャッシュ管理部と、
発行されたアクセスコマンドのアドレスに応じて前記アクセス頻度を更新して、前記アクセス頻度に基づいて前記キャッシュエントリおよび前記候補エントリを更新するキャッシュ更新部と
を具備する記憶装置。
（１０）前記キャッシュストレージは、書込み回数に上限を有する不揮発性メモリである
前記（９）に記載の記憶装置。
（１１）ホストコンピュータと、
メインストレージと、
前記メインストレージに記憶されるデータの一部を記憶するキャッシュストレージと、
前記キャッシュストレージのキャッシュエントリ毎にアクセス頻度を保持するキャッシュ管理部と、
前記キャッシュストレージに登録されていない候補エントリ毎に前記アクセス頻度を保持する候補キャッシュ管理部と、
前記ホストコンピュータによって発行されたアクセスコマンドのアドレスに応じて前記アクセス頻度を更新して、前記アクセス頻度に基づいて前記キャッシュエントリおよび前記候補エントリを更新するキャッシュ更新部と
を具備する情報処理システム。
【符号の説明】
【００９２】
１００  ホストコンピュータ
２００  ストレージコントローラ
２１０  キャッシュ管理テーブル
２１１  有効フラグ
２１２  アドレス情報
２１３  アクセス頻度情報
２１４  ダーティフラグ
２２０  キャッシュアドレス比較部
２２１  比較器
２２２  ヒット判定部
２３０  メインストレージ制御部
２４０  キャッシュストレージ制御部
２５０  キャッシュ管理テーブル更新部
２６０  キャッシュデータ更新部
２７０  候補キャッシュ管理テーブル
２７１  有効フラグ
２７２  アドレス情報
２７３  アクセス頻度情報
２８０  候補キャッシュアドレス比較部
２８１  比較器
２８２  ヒット判定部
２９０  候補キャッシュ管理テーブル更新部
３００  メインストレージ
４００  キャッシュストレージ
５００  記憶装置
【図１】
2020021791.tif 000003
【図２】
2020021791.tif 000004
【図３】
2020021791.tif 000005
【図４】
2020021791.tif 000006
【図５】
2020021791.tif 000007
【図６】
2020021791.tif 000008
【図７】
2020021791.tif 000009
【図８】
2020021791.tif 000010
【図９】
2020021791.tif 000011
【図１０】
2020021791.tif 000012
【図１１】
2020021791.tif 000013
【図１２】
2020021791.tif 000014
【国際調査報告】
2020021791.tif 000015
2020021791.tif 000016
2020021791.tif 000017