(57)【要約】  キャッシュメモリ装置は、キャッシュミス時に行うリフィル処理に先立って、リフィルすべきラインサイズを決定するラインサイズ決定処理を行う。このラインサイズ決定処理では、あるセットに属する管理対象ラインのリードライト回数を取得し（Ｓ５１）、リード回数同士及びライト回数同士がすべて一致した場合には（Ｓ５２：Ｙｅｓ）、リフィルすべきラインサイズを大きいサイズに決定する（Ｓ５４）。すべては一致していない場合には（Ｓ５２：Ｎｏ）、リフィルすべきラインサイズを小さいサイズに決定する（Ｓ５５）。
2010116735.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュデータを格納する格納手段と、
アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、
アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、
それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、
前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、
前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、
特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、
すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、
すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、
決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、
を備えることを特徴とするキャッシュメモリ装置。
【請求項２】
前記複数のラインセットのそれぞれは、インデクスが連続する値で並んだ複数のラインからなり、
前記特定手段は、前記アドレス抽出手段が抽出したインデクスの値よりも小さく、かつ、最も近い値の所定インデクスを含むラインセットを特定する
ことを特徴とする請求項１に記載のキャッシュメモリ装置。
【請求項３】
前記格納手段が格納するキャッシュデータは、プログラムが読み出しおよび書き込みを行うためのページ単位で管理された主メモリのデータであって、
前記複数のラインセットのそれぞれは、前記主メモリにおけるページ単位毎に、一対一に対応しており、
各ラインセットの先頭のインデクスの値は、前記主メモリにおけるページ単位の先頭に対応する値である
ことを特徴とする請求項２に記載のキャッシュメモリ装置。
【請求項４】
前記格納手段は、前記キャッシュデータを、このデータの主メモリにおける所在を示すタグに関係付けてライン単位で格納し、前記インデクスは前記格納手段におけるラインを指定するものであって、
前記決定手段は、特定されたラインセットを構成する全ラインそれぞれに対応するすべてのタグを前記格納手段から取得し、
前記特定されたラインセットを構成する全ラインそれぞれのアクセス回数のすべてが一致している場合において、
取得されたすべてのタグのすべてが一致しているのでなければ、リフィルすべきラインサイズを前記第１ラインサイズと決定し、
取得されたすべてのタグのすべてが一致していれば、リフィルすべきラインサイズを前記第２ラインサイズと決定する
ことを特徴とする請求項１に記載のキャッシュメモリ装置。
【請求項５】
前記アクセス要求には、リード要求とライト要求の２種類が有り、
前記管理手段が管理する前記アクセス回数は、リード回数とライト回数とを含み、
前記カウント手段は、前記ヒット判定手段によりヒットと判定されると、この判定の基としたアクセス要求がリード要求であれば対応するインデクスのリード回数を１回増やし、判定の基としたアクセス要求がライト要求であれば対応するライト回数を１回増やし、
前記決定手段は、
特定されたラインセットを構成する全ラインそれぞれのライト回数がすべてが一致しており、かつ、特定されたラインセットを構成する全ラインそれぞれのリード回数がすべてが一致している場合には、リフィルすべきラインサイズを前記第２ラインサイズと決定し、
特定されたラインセットを構成する全ラインそれぞれのライト回数がすべて一致しているのでない場合、
または、特定されたラインセットを構成する全ラインそれぞれのリード回数がすべて一致しているのでない場合には、
リフィルすべきラインサイズを前記第１ラインサイズと決定する
ことと特徴とする
請求項１に記載のキャッシュメモリ装置。
【請求項６】
前記カウント手段は、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記アクセス要求に含まれるインデクスに対応するラインのリード回数とライト回数とを含むアクセス回数をリセットし、
リセット後、アクセス要求がリード要求かライト要求かに応じて、対応するインデクスのリード回数またはライト回数を１回増やす
ことを特徴とする請求項５に記載のキャッシュメモリ装置。
【請求項７】
前記格納手段は、前記キャッシュデータを、このデータの主メモリにおける所在を示すタグに関係付けてライン単位で格納し、前記インデクスは前記格納手段におけるラインを指定するものであって、
前記ヒット判定手段は、前記アドレス抽出手段により抽出されたインデクスに対応するインデクスを前記格納手段が格納するデータの中から特定し、特定されたインデクスに関係付けられたタグと、アドレス抽出手段により抽出されたタグとを比較し、両タグが一致してしればヒットと判定し不一致であればミスと判定する
ことを特徴とする請求項１に記載のキャッシュメモリ装置。
【請求項８】
キャッシュデータを格納する格納ステップと、
アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出ステップと、
アドレス抽出ステップが抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定ステップと、
それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理ステップと、
前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定ステップによりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウントステップと、
前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定ステップによりミスと判定されると、前記管理ステップで管理しているラインの中からこのインデクスに対応するラインセットを特定する特定ステップと、
特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、
すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、
すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定ステップと、
決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィルステップと、
を含む
ことを特徴とするキャッシュメモリ制御方法。
【請求項９】
キャッシュメモリ装置に、キャッシュメモリ制御処理を実行させるプログラムであって、
前記キャッシュメモリ制御処理は、
キャッシュデータを格納する格納ステップと、
アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出ステップと、
アドレス抽出ステップが抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定ステップと、
それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理ステップと、
前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定ステップによりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウントステップと、
前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定ステップによりミスと判定されると、前記管理ステップで管理しているラインの中からこのインデクスに対応するラインセットを特定する特定ステップと、
特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、
すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、
すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定ステップと、
決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィルステップと、
を含むことを特徴とするプログラム。
【請求項１０】
キャッシュデータを格納する格納手段と、
アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、
アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、
それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、
前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、
前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、
特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、
すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、
すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、
決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、
を備えることを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
キャッシュメモリのデータをリフィルする技術に関する。
【背景技術】
【０００２】
キャッシュメモリは、プロセッサと主メモリとの間に配されて、主メモリより容量は小さいが高速にアクセスできる記憶装置である。【０００３】
キャッシュメモリにおいては、プロセッサが要求するデータがあることをヒット（hit）、ないことをミス（miss）と呼ぶ。そして、このミス時には、キャッシュメモリ上のデータを入れ替えるリフィル（refill, replacement）という処理を行う。【０００４】
一般にメモリの分野においては、空間的局所性（spatial locality，ある項目が参照された場合、その項目の近くにある項目が再び参照される確率が高いこと。）という性質が知られており、リフィル対象とするデータのサイズ（以下、「リフィルサイズ」と呼ぶ。）をある程度大きくすれば、ヒット率（hit rate,hit ratio）を高くできる。【０００５】
もっとも、キャッシュメモリの容量は限られているので、リフィルサイズをあまりに大きくすると、プロセッサが必要とするデータまでも入れ替えてしまいヒット率が低くなる（ミス率（miss rate）が高くなる）こともある。このような事態は、特にプログラムがキャッシュがミスとなったデータに後続するデータをすぐには使用しないような場合などに生じやすい。【０００６】
このようなリフィルサイズの最適化に関する技術としては、特許文献１が知られている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−２５９１０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ところで、キャッシュメモリは並行して動作する多種多様なプログラムにより使用される傾向にある。したがって、キャッシュメモリ上のある項目がプログラムにより参照されたとしても、続けて近くの項目が参照されるかどうかについては予想は困難である。この予想を誤って多くのラインサイズをリフィルしてしまうと、結果的にリフィルしたデータの大半が使用されない事態を招き、処理の遅延につながる。【０００９】
本発明は、このような背景の下になされたものであって、プログラムの挙動に応じて、リフィルサイズを、空間局所性を活用できる適切なサイズに制御することに貢献できるキャッシュメモリ装置の提供を目的とする。
【課題を解決するための手段】
【００１０】
本発明のキャッシュメモリ装置は、キャッシュデータを格納する格納手段と、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、を備えることを特徴とする。
【発明の効果】
【００１１】
上記アクセス回数が一致していれば、プログラムがメモリを局所的に参照しているであろうという推定が働く。本発明のキャッシュメモリ装置によれば、このアクセス回数の一致を条件として、リフィルサイズを大きくすることで、ヒット率を向上させ、キャッシュメモリに関するデータ転送を低減することができる。もってプログラムの動作性能を高めることができる。
【図面の簡単な説明】
【００１２】
【図１】キャッシュメモリ装置を含む情報処理装置の構成を示す図
【図２】キャッシュメモリ装置の構成を示すブロック図
【図３】アドレス解析部が取得するアドレス情報の一例を示す図
【図４】キャッシュデータ格納部が管理するキャッシュデータの一例を示す図
【図５】リードライト回数管理部が管理する情報の一例を示す図
【図６】キャッシュメモリ装置の動作を示すフロー図
【図７】回数カウントに関する動作を示すフロー図
【図８】回数リセットに関する動作を示すフロー図
【図９】ラインサイズ決定に関する動作を示すフロー図
【図１０】管理対象ラインを設定する例を説明するための図
【発明を実施するための形態】
【００１３】
以下、実施の形態について、図面を参照しながら説明する。
＜構成＞
図１は、キャッシュメモリ装置を含む情報処理装置１０００の構成を示す図である。
【００１４】
情報処理装置１０００は、例えば、ＰＣ（Personal Computer）等の汎用のコンピュータから構成される。
【００１５】
この情報処理装置１０００は、プロセッサ１、メモリ装置２、通信装置３４、入力装置４０、表示装置４５、タイマ回路５１及び割り込みコントローラ５５を備えている。これらの装置は、バスライン５０を通じて互いに接続されている。
【００１６】
また、バスライン５０には、ＨＤＤ（Hard Disk Drive）２５，読取装置３２，入力装置４０及び表示装置４５が、それぞれＩ／Ｆ（インタフェース）２６，３５，４１及び４６を通じて接続されている。
【００１７】
プロセッサ１は、３つのプロセッサ１１，１２，１３から構成されている。各プロセッサは、ＣＰＵ（Central Processing Unit，中央演算処理装置）と呼ばれるものである。
【００１８】
メモリ装置２は、ＲＯＭ（Read Only Memory）２１及びＲＡＭ（Random Access Memory）２２を備えている。
【００１９】
ＲＯＭ２１は、プロセッサ１の動作を規定するコンピュータプログラム及びデータを記憶する機能を有し、例えばフラッシュＲＯＭのように書き込みが可能で電源を切っても記憶内容を保持できる不揮発性のメモリから構成される。ＲＡＭ２２は、プロセッサ１が処理を実行するのに伴って発生するデータを一時的に記憶する機能を有し、例えば電源を切ると記憶内容が保持されない揮発性のメモリから構成される。なお、コンピュータプログラム及びデータは、ＲＯＭ２１に代えてＨＤＤ２５に記憶させることもできる。
【００２０】
プロセッサ１は、ＲＯＭ２１またはＨＤＤ２５が格納するコンピュータプログラム及びデータを、必要に応じてＲＡＭ２２に書き込みつつ、コンピュータプログラムが規定する処理を実行する。
【００２１】
ＨＤＤ２５は、コンピュータプログラムやデータを記憶する装置である。
【００２２】
読取装置３２は、記録媒体３１（例えばＣＤ、ＤＶＤ、メモリカードなど）に記録されたコンピュータプログラムあるいはデータを読み取る装置である。
【００２３】
通信装置３４は、電話回線、ネットワーク線、無線、赤外線通信等の通信回線３３を通じて、外部と自身との間で、コンピュータプログラムやデータを交換する装置である。
【００２４】
入力装置４０は、ユーザの操作によりデータ等を入力する装置であり、キーボード、マウスや各種入力ボタンから構成される。
【００２５】
表示装置４５は、データ、画像等を画面に表示したり、データ等を音声で出力したりする装置であり、例えば19インチの液晶ディスプレイ(LCD:Liquid Crystal Display)とスピーカとから構成される。
【００２６】
タイマ回路５１は、一定の周期でタイマ割り込み信号を出力する装置である。
【００２７】
割り込みコントローラ５５は、タイマ回路５１、入力装置４０、プロセッサ１、ネットワークデバイスである通信装置３４、ＨＤＤ２５、読取装置３２などから送られる割り込み要求信号を、プロセッサ１へ中継する装置である。各装置からの割り込み要求信号には優先度が付けられている。この割り込みコントローラ５５は、同時に複数の装置から割り込みが発生した場合には、それらの要求を上記優先度に応じて調停する機能（arbitration）を有している。
【００２８】
図２は、キャッシュメモリ装置１０の構成を示すブロック図である。キャッシュメモリ装置１０は、プロセッサ１と外部メモリ２３１と協同して動作する。外部メモリ２３１としては、典型的には、図１に示すメモリ装置２に含まれるＲＡＭ２２が用いられる。
【００２９】
キャッシュメモリ装置１０は、アドレス解析部２０１、管理ライン判定部２０２、回数管理部２０３、ラインサイズ決定部２０４、ヒット／ミス判定部２０５、リフィル部２０６、キャッシュデータ格納部２０７を備えている。なお、キャッシュデータは、キャッシュライン(以下、単に「ライン」と呼ぶ。）と呼ばれる、一定のサイズのデータごとに管理される。また、キャッシュデータの各ラインは、インデクスの値により一意に識別しアクセスすることができる。
【００３０】
アドレス解析部２０１は、プロセッサ１から要求するデータの格納先を示すアドレスを受け取る。アドレス解析部２０１は、受け取ったアドレスから、ヒットを判定するために使用するタグと、キャッシュデータの格納オフセットを示すインデクスとに分離する。アドレス解析部２０１は、分離して得られたインデクスを管理ライン判定部２０２に渡し、タグとインデクスをヒット／ミス判定部２０５に渡す。
【００３１】
管理ライン判定部２０２は、プロセッサ１が要求するデータへのアクセスが、回数管理部２０３（後述するように回数管理部２０３はキャッシュメモリにおける全ラインのうちの、一部の所定のラインを管理している。）が管理対象としているラインへのアクセスであるかどうかを判定する機能を有している。
【００３２】
管理ライン判定部２０２は、管理対象ラインに対応付けられたインデクスを保持する。管理ライン判定部２０２は、アドレス解析部２０１からインデクスを受け取ると、そのインデクスが保持したインデクスにあたるかどうか判定する。管理ライン判定部２０２の典型的な構成としては、キャッシュメモリ装置として管理対象のインデクスが事前に定められ、そのインデクスでアクセスが発生した場合に、アサートされるような回路を備えていればよい。
【００３３】
また、管理ライン判定部２０２は、管理対象のラインであると判定すると、回数管理部２０３に管理対象のラインであることを通知する。これに対して、管理対象のラインではないと判定すると、回数管理部２０３及びラインサイズ決定部２０４に管理対象のラインではないことを通知する。
【００３４】
ヒット／ミス判定部２０５は、プロセッサ１が要求するデータがキャッシュデータとして存在するか（ヒット）、存在しないか（ミス）を判定する機能を有している。ヒット／ミス判定部２０５は、アドレス解析部２０１からタグとインデクスを受け取ると、インデクスをキャッシュデータ格納部２０７に渡す。次に、ヒット／ミス判定部２０５は、キャッシュデータ格納部２０７から、渡したインデクスに対応するキャッシュデータのタグを受け取る。ヒット／ミス判定部２０５は、アドレス解析部２０１から取得したタグと、キャッシュデータ格納部２０７に問い合わせて取得したタグを比較する。
【００３５】
そして、比較の結果、タグ同士が一致すればヒットと判定し、ヒット／ミス判定部２０５は、キャッシュデータ格納部２０７から該当するラインのデータを取得し、プロセッサ１に渡す。また、ヒット／ミス判定部２０５は、ヒットの旨を回数管理部２０３及びラインサイズ決定部２０４に通知する。これに対して比較の結果、タグ同士が一致しなければミスと判定し、ヒット／ミス判定部２０５は、ミスであることを回数管理部２０３及びラインサイズ決定部２０４に通知する。
【００３６】
また、ヒット／ミス判定部２０５は、ヒットかミスかに関わらず、回数管理部２０３及びラインサイズ決定部２０４に、アドレス解析部２０１から受け取ったタグとインデクスを渡す。
【００３７】
回数管理部２０３は、キャッシュメモリにおける全ラインのうちの、一部の所定のラインにおけるアクセス回数（リード回数及びライト回数）を記憶し、管理する機能を有する。この管理対象とするラインの決め方については後述する。
【００３８】
回数管理部２０３は、管理ライン判定部２０２から管理対象のラインへのアクセスであると通知を受けると、次にヒット／ミス判定部２０５から受け取ったインデクスに基づいて該当する管理対象のラインを特定する。
【００３９】
回数管理部２０３には、プロセッサ１からリード要求またはライト要求があった場合に通知する線が接続されている。回数管理部２０３は、この線を経由して通知されたリード要求またはライト要求と、ヒット／ミス判定部２０５からの通知がヒットかミスかに応じて管理するリード回数またはライト回数を更新する。
【００４０】
また、回数管理部２０３は、ヒット／ミス判定部２０５からミスであるという通知を受けた場合、回数管理部２０３は、アドレス解析部２０１から受け取ったタグとインデクスをリフィル部２０６に渡す。また、回数管理部２０３は、ラインサイズをリフィル部２０６に渡す。
【００４１】
また、回数管理部２０３は、ヒット／ミス判定部２０５からミスであるという通知を受けた場合で、管理対象のラインではないと判定の通知を受けていれば、その管理対象のラインではないインデクスの値に基づいて、管理対象のラインである代わりのインデクスを特定する。そして、特定したインデクスをラインサイズ決定部に通知する。
【００４２】
ラインサイズ決定部２０４は、回数管理部２０３から通知されたインデクスの、リードライト回数を参照して、リフィルすべきラインサイズを、１ラインサイズとするか複数ライン（例えば４ライン分）サイズとするかのいずれにするかを決定する機能を有している。
【００４３】
このラインを決定する処理は、ラインサイズ決定部２０４は、管理ライン判定部２０２から管理対象のラインではないと通知を受け、かつヒット／ミス判定部２０５からミスであると通知を受けたときに行われる。
【００４４】
この処理を詳しく述べると、ラインサイズ決定部２０４は、回数管理部２０３から管理対象のラインのインデクスを取得する。次に、ラインサイズ決定部２０４は、取得した全てのインデクスに対応するタグを、キャッシュデータ格納部２０７から取得する。また、ラインサイズ決定部２０４は、取得した全てのインデクスに対応するリードライト回数を回数管理部２０３から取得する。
【００４５】
ラインサイズ決定部２０４は、取得したタグ同士、リード回数同士及びライト回数同士が全て一致する場合、リフィルすべきラインサイズを大きな４ラインサイズと決定する。また、いずれかが一致しない場合、リフィルすべきラインサイズは通常の１ラインサイズと決定する。そして、決定したラインサイズと、リフィルするデータのアドレスとをリフィル部２０６に通知する。
【００４６】
リフィル部２０６は、回数管理部２０３あるいはラインサイズ決定部２０４からリフィル対象のデータが存在するアドレスと、リフィルすべきラインサイズを取得し、取得したアドレスに存在するデータを、取得したラインサイズで外部メモリ２３１から読み込む。
【００４７】
読み込み後、リフィル部２０６は、読み込んだデータと、そのデータのアドレスと、データのサイズの三者をキャッシュデータ格納部２０７に受け渡す。なお、リフィル部２０６は、上記データのアドレスとデータのサイズの代わりに、回数管理部２０３やラインサイズ決定部２０４からリフィルするタグとインデクスを取得し、キャッシュデータ格納部２０７に渡してもかまわない。
【００４８】
キャッシュデータ格納部２０７は、キャッシュのデータを格納・管理する機能を有する。キャッシュデータ格納部２０７は、格納したデータをライン単位で管理し、各ラインはインデクスによりどのラインかを一意に特定できるようになっている。また、キャッシュデータ格納部２０７は、各ライン毎に、各ラインにおけるデータが外部メモリ２３１においてどのアドレスのデータであるかを示すタグを関連づけて管理している。
【００４９】
キャッシュデータ格納部２０７は、ヒット／ミス判定部２０５からインデクスを受け取ると、インデクスによりラインを特定し、そのラインと対応付けて管理しているタグをヒット／ミス判定部２０５に返す。
【００５０】
キャッシュデータ格納部２０７は、リフィル部２０６からデータのサイズを受け取ると、管理するラインサイズからそのデータが何ライン分のデータであるか把握する。そして、リフィル部２０６からデータのアドレスを受け取ると、データのアドレスをアドレス解析部２０１に渡してタグとインデクスを受け取り、受け取ったインデクスによりラインを特定し、リフィル部２０６から受け取ったデータを、特定したラインのデータとして管理する。また、キャッシュデータ格納部２０７は、アドレス解析部２０１から受け取ったタグを、特定したラインに対応するタグとして管理する。なお、キャッシュデータ格納部２０７は、リフィル部２０６からデータのアドレスとデータのサイズを取得する代わりに、リフィルするタグとインデクスを取得し、キャッシュデータを更新してもかまわない。
【００５１】
キャッシュデータ格納部２０７は、リフィル部２０６から数ライン分のデータを受け取っている場合、後続するインデクスのラインに対応させてラインサイズ分のデータを管理する。キャッシュデータ格納部２０７は、アドレス解析部２０１から受け取ったタグを、後続するインデクスのラインに対応するタグとして管理する。キャッシュデータ格納部２０７は、リフィル部２０６から受け取った、全てのラインのデータに関して前述の動作を行い、キャッシュデータを管理する。
続いて、プロセッサ１がアドレス解析部２０１に渡すアドレスの例について説明する。図３には、一例として３２ビットにより構成されるアドレス４０１を示している。０から３１までの数値４０２は、アドレス４０１を構成する各ビットを、下位０ビット目から３１ビット目まで便宜上示すものである（３１ビット目が、最上位ビット）。
【００５２】
アドレス４０１は、１５ビット目から３１ビット目の上位アドレス４０３、５ビット目から１４ビット目の下位アドレス４０４を含んでいる。
【００５３】
アドレス解析部２０１は、アドレス４０１を受け取ると、ラインサイズ、キャッシュブロックサイズに応じて、アドレス４０１から、上位アドレス４０３をタグ、下位アドレス４０４をインデクスとして切り出す。
【００５４】
図３は一例として、ラインサイズが３２バイト、キャッシュブロックサイズ３２ＫＢの場合を示している。もっとも、例に挙げたラインサイズやキャッシュブロックサイズはあくまで一例に過ぎず、キャッシュメモリの構成に応じて変更可能である。
続いて、キャッシュデータ格納部２０７が管理するキャッシュデータの例について説明する。
【００５５】
図４の例では、キャッシュデータ格納部２０７は、「キャッシュデータ」２０７ｃと、このデータのラインを示す「インデクス」２０７ａ，このデータが外部メモリ２３１においてどのアドレスのデータであるかを示す「タグ」２０７ｂを管理している。
【００５６】
上述のように、このキャッシュデータ格納部２０７が格納しているデータのライン（インデクス）のうちの一部が回数管理部２０３が管理する管理対象ラインとなる。具体例を図５に示す。
【００５７】
回数管理部２０３は、管理対象ラインを示す「インデクス」２０３ａ、インデクスに対応する「リード回数」２０３ｂ，「ライト回数」２０３ｃを含む。
【００５８】
図５の例では、インデクス0x000〜0x003の４ラインの「セット１」と、インデクス0x200〜0x203の４ラインの「セット２」とが管理対象となっている。上述のように、各セットの先頭のインデクス0x000, 0x200は、プログラムが使用するページ単位上においてインデクスが先頭になるラインである。
＜動作＞
以下、実施の形態に係るキャッシュメモリ装置の動作について説明する。
【００５９】
図６に示すように、まず、アドレス解析部２０１は、プロセッサ１からアドレスを受け取ると、そのアドレスをタグとインデクスに分離（抽出）する（Ｓ１１）。
【００６０】
次に、ヒット／ミス判定部２０５は、アドレス解析部２０１からタグとインデクスを受け取ると、キャッシュデータ格納部２０７に問い合わせてヒットかミスかを判定する（Ｓ１２）。この判定は、ヒット／ミス判定部２０５が、キャッシュデータ格納部２０７からインデクスに対応するキャッシュデータのタグを取得し、アドレス解析部２０１が分離したタグと比較し、両タグが一致していれば、ヒットと判定し（Ｓ１２：ヒット）、一致していなければミスと判定する（Ｓ１２：ミス）。
【００６１】
ヒットと判定すると（Ｓ１２：ヒット）、ヒット／ミス判定部２０５は、キャッシュデータ格納部２０７から、ステップＳ１１で分離したアドレスに対応するキャッシュデータを取得し、プロセッサ１に返す（Ｓ１３）。
【００６２】
そして、管理ライン判定部２０２は、ステップＳ１１で分離したアドレスに含まれるインデクスが、管理対象ラインのインデクスであるかどうかを判定する（Ｓ１４）。
【００６３】
管理対象ラインのインデクスであれば（Ｓ１４：Ｙｅｓ）、回数カウントの処理に移る（Ｓ１５，図７）。管理対象ラインのインデクスでなければ（Ｓ１４：Ｎｏ）、処理を終了する。
【００６４】
図７に示すように、回数カウント処理では、回数管理部２０３はアクセス対象のラインを特定し（Ｓ３１）、アクセスがリード要求であれば（Ｓ３２：リード）、該当する管理対象ラインのリード回数を１回加算する（Ｓ３３）。
【００６５】
アクセスがリード要求であれば（Ｓ３２：ライト）、回数管理部２０３は、該当する管理対象ラインのライト回数を１回加算する（Ｓ３４）。
【００６６】
具体的な例を挙げると、アクセス対象のラインが"0x000"でアクセスがリード要求であれば、回数管理部２０３は、管理対象ラインのインデクス"0x000"のリード回数2回（図５参照）に１回加算して3回へと更新する。また、アクセス対象のラインが"0x001"でアクセスがライト要求であれば、回数管理部２０３は、管理対象ラインのインデクス"0x001"のリード回数0回（図５参照）に１回加算して1回へと更新する。
【００６７】
このように、キャッシュヒット場合で（Ｓ１２：ヒット）、かつ管理対象ラインへのアクセスであれば（Ｓ１４：Ｙｅｓ）、回数管理部２０３は対応する管理対象ラインの回数をカウントすることとなる（Ｓ３１〜Ｓ３４）。
【００６８】
さて、ヒット／ミス判定部２０５がミスと判定すると（Ｓ１２：ミス）、管理ライン判定部２０２は、ステップＳ１１で分離したアドレスに含まれるインデクスが、管理対象ラインのインデクスであるかどうかを判定する（Ｓ１６）。
【００６９】
管理対象ラインのインデクスであれば（Ｓ１６：Ｙｅｓ）、回数リセットの処理に移る（Ｓ１７，図８）。
【００７０】
図８に示すように、回数リセット処理では、回数管理部２０３は、アクセス対象のラインの、リードライト回数を無効化（リセット）する（Ｓ４１）。そして、アクセスがリード要求であれば（Ｓ４２：リード）、該当する管理対象ラインのリード回数を１回に設定する（Ｓ４３）。
【００７１】
これに対して、アクセスがライト要求であれば（Ｓ４２：ライト）、回数管理部２０３は、該当する管理対象ラインのライト回数を１回に設定する（Ｓ４４）。
【００７２】
具体的な例を挙げると、アクセス対象のラインが"0x000"でアクセスがリード要求であれば、回数管理部２０３は、管理対象ラインのインデクス"0x000"のリード回数2回、ライト回数3回（図５参照）を共に0回へとリセットし、その後、リード回数を1回に再設定する。
【００７３】
このような回数のリセット処理を終えると、リフィル部２０６は、外部メモリ２３１から該当するライン（ステップＳ１１で分離したアドレスに含まれるインデクスに対応するライン）のデータを取得し、キャッシュデータ格納部２０７のキャッシュデータにリフィルする（Ｓ１９）。
【００７４】
具体的には、リフィル部２０６は回数管理部２０３から受け取ったリフィル対象のアドレスに対応するデータを外部メモリ２３１から読み込む。そして、リフィル部２０６は、読み込んだデータをキャッシュデータ格納部２０７に渡し、キャッシュデータとして格納させる。次に、リフィル部２０６は、外部メモリ２３１から読み込んだデータをプロセッサ１に返す。
【００７５】
管理対象ラインのインデクスでなければ（Ｓ１６：Ｎｏ）、管理ライン判定部２０２は、その旨を管理回数部２０３に通知する。通知を受けた回数管理部２０３は、自己が管理する管理対象ラインの中から、ステップＳ１１で取得したインデクスより小さく、かつ、最も近いインデクスのセットを特定する。例えば、ステップＳ１１で分離したアドレスに含まれるインデクスが、"0x280"（図４）とすると、このインデクス"0x280"より小さく、最も近いインデクスのセット２（図５："0x200"〜"0x203"の４ラインのセット）と特定する（Ｓ２０）。
【００７６】
そして、ラインサイズ決定処理に移る（Ｓ２１，図９）。
【００７７】
ラインサイズ決定処理では、ラインサイズ決定部２０４は、管理ライン判定部２０２から特定されたセットを示す情報を受信すると、受信したセットに対応するリードライト回数を回数管理部２０３から取得するとともに、取得したセットに属する管理対象ラインのタグをキャッシュデータ格納部２０７から取得する（Ｓ５１）。
【００７８】
そして、取得した全ての管理対象ラインのリード回数同士・ライト回数同士がすべて一致するかどうかを判定する（Ｓ５２）。例えば、インデクスのセットがセット２と特定されたのであれば、セット２に属する"0x200"〜"0x203"の４ラインのリード回数は0回、ライト回数は2回とすべて一致する（図５参照）ので肯定的に判定する。これに対して、インデクスのセットがセット１と特定されたのであれば、セット１に属する"0x000"〜"0x003"の４ラインのリード回数は、2回，2回，0回，1回とまちまちである（図５参照）ので、否定的に判定する。
【００７９】
ステップＳ５２で一致と判定すると（Ｓ５２：Ｙｅｓ）、続いて、ラインサイズ決定部２０４は、取得したすべての管理対象ラインのタグ同士がすべて一致するかどうかを判定する（Ｓ５３）。例えば、インデクスのセットがセット２と特定されたのであれば、セット２に属する"0x200"〜"0x203"の４ラインのタグは、"0x02000"とすべて一致している（図４参照）ので、肯定的に判定する。これに対して、インデクスのセットがセット１と特定されたのであれば、セット１に属する"0x000"〜"0x003"の４ラインのタグは、0x01c80,0x01c80,0x10000,0x00040と一部の２つが一致しているに過ぎず、全一致ではないので、否定的に判定する。
【００８０】
ラインサイズ決定部２０４は、取得した全ての管理対象ラインのリード回数同士・ライト回数同士がすべて一致し（Ｓ５２：Ｙｅｓ）、かつ、取得したすべての管理対象ラインのタグ同士がすべて一致した場合（Ｓ５３：Ｙｅｓ）には、リフィルすべきラインサイズを４ライン分のサイズに決定する（Ｓ５４）。
【００８１】
ステップＳ５２，Ｓ５３の両判定のいずれかを満たさなければ（Ｓ５２：Ｎｏ，or Ｓ５３：Ｎｏ）、ラインサイズ決定部２０４は通常のリフィルすべきラインサイズを１ライン分のサイズに決定する。
【００８２】
このようなラインサイズ決定処理を終えると、リフィル部２０６は、外部メモリ２３１から該当するライン（ステップＳ１１で分離したアドレスに含まれるインデクスに対応するライン）のデータを取得し、キャッシュデータ格納部２０７のキャッシュデータにリフィルする（Ｓ１９）。
【００８３】
特に、リフィル部２０６は、リフィルサイズが４ラインであれば（Ｓ５４）、対応するラインのみならず、このラインよりインデクッスが後続する３ラインについても、合わせてリフィルを行う。例えば、ステップＳ１１で分離したアドレスに含まれるインデクスが"0x280"ならば、リフィル部２０６は"0x280"のみならず後続する"0x281"〜"0x283"の３ラインの合計４ラインをリフィル対象とすることとなる。
【００８４】
一般にプログラムはメモリをページ単位で使用・管理するものである。このため、同じページ単位に対応するインデクスのリード回数及びライト回数が一致していれば、プログラムが連続的な（シーケンシャルな）ふるまいをしていることが推定できる。このため、リード回数及びライト回数の一致を条件として通常より大きなラインサイズをリフィルすると、このリフィルしたデータが後々使用される可能性が高くなる（ヒット率が高くなる）ことが期待できる。
【００８５】
本実施の例を用いて説明すると、管理対象ライン"0x200"〜"0x203"はリード回数・ライト回数がすべて一致している（図５参照）ため、プログラムが連続的な挙動をしている可能性が高い。このため、"0x280"のみならず"0x281"〜"0x283"をもリフィルすることで、リフィル後にライン"0x281"〜"0x283"へのアクセスが発生して（プログラムが"0x281"〜"0x283"参照して）キャッシュヒットとなる確率を高くすることできる。
【００８６】
また、ある同じページ単位に対応するインデクスに関しては、その先頭部分のインデクスがプログラムの挙動が最も良く現れる。このため、"0x200"〜"0x203"などのような先頭部分を管理対象ラインとして回数の一致を見ることで、プログラムの挙動を的確に反映したリフィルサイズとすることができる。
＜補足１＞
以上、本実施の形態について説明したが、本発明は上記の内容に限定されず、本発明の目的とそれに関連又は付随する目的を達成するための各種形態においても実施可能であり、例えば、以下であっても構わない。
【００８７】
（１）図９の例では、回数の一致を判定した後でタグの一致を判定するという順番であったが、この順番はこれに限らず反転させてもよい（ステップＳ５３の次にＳ５２としてもよい）。
【００８８】
また、ステップＳ５３の処理は、データが外部メモリ２３１においてどのアドレスのデータであるかを示すタグ同士の一致を判断している。この判断により、タグが不一致で偶然リード回数・ライト回数が一致していたものに過ぎない、言い換えるとプログラムのふるまいを鮮明に反映しない回数の一致を排除でき、より適切なリフィルサイズの決定に寄与することができる。もっとも、ステップＳ５３の処理は必須ではなくステップＳ５３をスキップするやり方も考え得る。
【００８９】
（２）実施の形態では詳細は述べなかったが、一般的なキャッシュ技術と同様に、キャッシュデータ格納部２０７においては、データの有効（valid）・無効（invalid）を示す有効タグや、データの一貫性（consistency）を保証するためのダーティ(dirty)タグを、ライン毎に管理するようにしてもよい。
【００９０】
また、特に、有効タグを管理する場合には、ヒット／ミス判定部２０５は、タグの一致に加えて、有効タグが有効を示す場合を条件にヒットと判定するようにしてもよい。
【００９１】
（３）実施の形態では、ラインサイズ決定部２０４は、リフィルのラインサイズを大きくするときにライン数は、管理対象ラインの１セットに含まれるライン数と同じ４ライン（図９：Ｓ５４）に決定するとしたが、これに限られない。例えば２ライン、８ラインとすることもできる。
【００９２】
要は、管理対象ラインのリード回数・ライト回数が一致している場合のラインサイズＡが、一致していない場合のラインサイズＢより相対的に大きければ（Ａ＞Ｂ）、ラインサイズの最適化に役立てることができる。
【００９３】
（４）実施の形態では、外部メモリ２３１としては、ＲＡＭ２２を挙げたが、外部メモリ２３１の要件としてはＲＡＭ２２に限らず、キャッシュメモリ装置１０より記憶階層（memory hierarchy）がより下位層のメモリであれば足りる。例えば、ＨＤＤ２５や読取装置３２から読み込まれる記録媒体３１を外部メモリ２３１として用いてもよい。
【００９４】
（５）管理回数部２０３における管理対象ラインを、どのように設定するかについて述べる。実施の形態のように、インデクスの値が連続する複数のラインからなるラインセットを複数セット分構成し、ラインセット同士は一定間隔空けるようにする。この一定間隔は、プログラムが使用するメモリ単位（メモリにおけるプログラムの管理単位）の間隔に合わせ、各ラインセットは、メモリ単位の先頭に相当するように設けることが好ましい。なお、プログラムの挙動を精度良く推定するためには、先頭に設けることが最良であるものの、場合によってはメモリ単位の中程に各ラインセットが位置するようにしても構わない。
【００９５】
管理対象ラインのさらなる具体例を図１０に示す。図１０に示すように、プログラムが使用するメモリ単位が４キロバイトで、キャッシュラインサイズが３２バイトであれば、インデクス０ｘ８０（１２８）間隔でラインセットを設ける。そして各ラインセットは、インデクス0x000、0x080、0x100などから、それぞれ後続する４ライン分をセットとすることが考えられる。
【００９６】
なお、セットとするラインの数は、複数（２ライン以上）であれば足り、例えば、８ラインとしてもよい。
【００９７】
（６）図９のステップＳ５２のＹｅｓは、リード回数同士がすべて０回かつライト回数同士がすべて０回の場合を除くとしても構わない。なぜならば、両者が共にすべて０回ならば、プログラムの挙動を推定する材料としては最適でない場合があるからである。
【００９８】
（７）実施の形態では、情報処理装置１０００はＰＣとして説明したが、これに限らず、ＰＤＡ（Personal Digital Assistance）や携帯電話機等の携帯通信端末でもよい。また、情報処理装置１０００は、それ自体としてユーザの使用に供するものでもよいし、様々な電子機器に組み込まれている態様でもよい。
【００９９】
（８）実施の形態では、プロセッサ１は、ＣＰＵとして説明したが、これに限らず、メディア処理用やグラフィック処理用のプロセッサ、ＤＳＰ（Digital Signal Processor）などであってもよい、また、プロセッサは、単一のプロセッサで構成されてもよく、複数のプロセッサで構成されてもよい。
【０１００】
（９）図２の各機能ブロックは、典型的にはプロセッサと外部メモリとの間に存在するキャッシュメモリとして実現されるが、集積回路であるＬＳＩとしてもよい。これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用してもよい。さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。
【０１０１】
（１０）実施の形態で示した動作などを各種情報処理装置のプロセッサ、及びそのプロセッサに接続された各種回路に実行させるためのプログラムコードからなる制御プログラムを、記録媒体に記録すること、又は各種通信路等を介して流通させ頒布することもできる。このような記録媒体には、ICカード、HDD,光ディスク、フレキシブルディスク、ROMなどの非一時的な(non-transitory)な記録媒体が含まれる。流通、頒布された制御プログラムはプロセッサに読み出され得るメモリ等に格納されることにより利用に供され、そのプロセッサがその制御プログラムを実行することにより実施の形態で示したような各種機能が実現されることになる。
【０１０２】
（１１）実施の形態や、本補足１で挙げた具体的なスペック値（ラインサイズ、キャッシュブロックサイズなど）はあくまで一例に過ぎず、キャッシュメモリの構成に応じて適宜変更可能である。
＜補足２＞
本実施の形態は、次の態様を含むものである。
（１）本実施の形態に係るキャッシュメモリ装置は、キャッシュデータを格納する格納手段と、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、を備えることを特徴とする。
（２）前記複数のラインセットのそれぞれは、インデクスが連続する値で並んだ複数のラインからなり、前記特定手段は、前記アドレス抽出手段が抽出したインデクスの値よりも小さく、かつ、最も近い値の所定インデクスを含むラインセットを特定するとしても構わない。
（３）前記格納手段が格納するキャッシュデータは、プログラムが読み出しおよび書き込みを行うためのページ単位で管理された主メモリのデータであって、
前記複数のラインセットのそれぞれは、前記主メモリにおけるページ単位毎に、一対一に対応しており、各ラインセットの先頭のインデクスの値は、前記主メモリにおけるページ単位の先頭に対応する値であるとしても構わない。
（４）前記格納手段は、前記キャッシュデータを、このデータの主メモリにおける所在を示すタグに関係付けてライン単位で格納し、前記インデクスは前記格納手段におけるラインを指定するものであって、前記決定手段は、特定されたラインセットを構成する全ラインそれぞれに対応するすべてのタグを前記格納手段から取得し、前記特定されたラインセットを構成する全ラインそれぞれのアクセス回数のすべてが一致している場合において取得されたすべてのタグのすべてが一致しているのでなければ、リフィルすべきラインサイズを前記第１ラインサイズと決定し、取得されたすべてのタグのすべてが一致していれば、リフィルすべきラインサイズを前記第２ラインサイズと決定するとしても構わない。
【０１０３】
この構成によれば、より確実にプログラムの挙動を推定でき、適切なリフィルサイズの決定に資する。
（５）前記アクセス要求には、リード要求とライト要求の２種類が有り、
前記管理手段が管理する前記アクセス回数は、リード回数とライト回数とを含み、前記カウント手段は、前記ヒット判定手段によりヒットと判定されると、この判定の基としたアクセス要求がリード要求であれば対応するインデクスのリード回数を１回増やし、判定の基としたアクセス要求がライト要求であれば対応するライト回数を１回増やし、前記決定手段は、特定されたラインセットを構成する全ラインそれぞれのライト回数がすべてが一致しており、かつ、特定されたラインセットを構成する全ラインそれぞれのリード回数がすべてが一致している場合には、リフィルすべきラインサイズを前記第２ラインサイズと決定し、特定されたラインセットを構成する全ラインそれぞれのライト回数がすべて一致しているのでない場合、または、特定されたラインセットを構成する全ラインそれぞれのリード回数がすべて一致しているのでない場合には、
リフィルすべきラインサイズを前記第１ラインサイズと決定するとしても構わない。
（６）前記カウント手段は、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記アクセス要求に含まれるインデクスに対応するラインのリード回数とライト回数とを含むアクセス回数をリセットし、リセット後、アクセス要求がリード要求かライト要求かに応じて、対応するインデクスのリード回数またはライト回数を１回増やすとしても構わない。
（７）前記格納手段は、前記キャッシュデータを、このデータの主メモリにおける所在を示すタグに関係付けてライン単位で格納し、前記インデクスは前記格納手段におけるラインを指定するものであって、前記ヒット判定手段は、前記アドレス抽出手段により抽出されたインデクスに対応するインデクスを前記格納手段が格納するデータの中から特定し、特定されたインデクスに関係付けられたタグと、アドレス抽出手段により抽出されたタグとを比較し、両タグが一致してしればヒットと判定し不一致であればミスと判定するとしても構わない。
（８）本実施の形態に係るキャッシュメモリ制御方法は、  キャッシュデータを格納する格納ステップと、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出ステップと、アドレス抽出ステップが抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定ステップと、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理ステップと、前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定ステップによりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウントステップと、前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定ステップによりミスと判定されると、前記管理ステップで管理しているラインの中からこのインデクスに対応するラインセットを特定する特定ステップと、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定ステップと、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィルステップと、を含むことを特徴とする。
（９）本実施の形態に係るプログラムは、キャッシュメモリ装置に、キャッシュメモリ制御処理を実行させるプログラムであって、前記キャッシュメモリ制御処理は、キャッシュデータを格納する格納ステップと、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出ステップと、アドレス抽出ステップが抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定ステップと、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理ステップと、前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定ステップによりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウントステップと、前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定ステップによりミスと判定されると、前記管理ステップで管理しているラインの中からこのインデクスに対応するラインセットを特定する特定ステップと、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定ステップと、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィルステップと、を含むことを特徴とする。
（１０）本実施の形態に係る集積回路は、キャッシュデータを格納する格納手段と、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、を備えることを特徴とする。
【産業上の利用可能性】
【０１０４】
本発明にかかるキャッシュメモリ装置は、プログラムの動作に応じて即時にリフィルするラインサイズを変更する機能を有し、情報処理装置として有用である。また、情報機器、ＡＶ機器、通信機器、家電機器などの組み込み機器などのコンピュータを搭載する機器において有用である。
【符号の説明】
【０１０５】
１，１１，１２，１３  プロセッサ
２  メモリ装置
１０  キャッシュメモリ装置
２１  ＲＯＭ
２２  ＲＡＭ
２５  ＨＤＤ
２６，３５，４１，４６  インタフェース（Ｉ／Ｆ）
３１  記録媒体
３２  読取装置
３３  通信回線
３４  通信装置
４０  入力装置
４５  表示装置
５０  バスライン
５１  タイマ回路
５５  割込コントローラ
２０１  アドレス解析部（アドレス抽出部）
２０２  管理ライン判定部
２０３  回数管理部
２０４  ラインサイズ決定部
２０５  ヒット／ミス判定部
２０６  リフィル部
２０７  キャッシュデータ格納部
２３１  外部メモリ
【図１】
2010116735.tif 000003
【図２】
2010116735.tif 000004
【図３】
2010116735.tif 000005
【図４】
2010116735.tif 000006
【図５】
2010116735.tif 000007
【図６】
2010116735.tif 000008
【図７】
2010116735.tif 000009
【図８】
2010116735.tif 000010
【図９】
2010116735.tif 000011
【図１０】
2010116735.tif 000012
【手続補正書】
【提出日】平成22年11月30日(2010.11.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
キャッシュメモリのデータをリフィルする技術に関する。
【背景技術】
【０００２】
キャッシュメモリは、プロセッサと主メモリとの間に配されて、主メモリより容量は小さいが高速にアクセスできる記憶装置である。
【０００３】
キャッシュメモリにおいては、プロセッサが要求するデータがあることをヒット（hit）、ないことをミス（miss）と呼ぶ。そして、このミス時には、キャッシュメモリ上のデータを入れ替えるリフィル（refill,replacement）という処理を行う。
【０００４】
一般にメモリの分野においては、空間的局所性（spatial locality，ある項目が参照された場合、その項目の近くにある項目が再び参照される確率が高いこと。）という性質が知られており、リフィル対象とするデータのサイズ（以下、「リフィルサイズ」と呼ぶ。）をある程度大きくすれば、ヒット率（hitrate,hit ratio）を高くできる。
【０００５】
もっとも、キャッシュメモリの容量は限られているので、リフィルサイズをあまりに大きくすると、プロセッサが必要とするデータまでも入れ替えてしまいヒット率が低くなる（ミス率（missrate）が高くなる）こともある。このような事態は、特にプログラムがキャッシュがミスとなったデータに後続するデータをすぐには使用しないような場合などに生じやすい。
【０００６】
このようなリフィルサイズの最適化に関する技術としては、特許文献１が知られている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−２５９１０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ところで、キャッシュメモリは並行して動作する多種多様なプログラムにより使用される傾向にある。したがって、キャッシュメモリ上のある項目がプログラムにより参照されたとしても、続けて近くの項目が参照されるかどうかについては予想は困難である。この予想を誤って多くのラインサイズをリフィルしてしまうと、結果的にリフィルしたデータの大半が使用されない事態を招き、処理の遅延につながる。
【０００９】
本発明は、このような背景の下になされたものであって、プログラムの挙動に応じて、リフィルサイズを、空間局所性を活用できる適切なサイズに制御することに貢献できるキャッシュメモリ装置の提供を目的とする。
【課題を解決するための手段】
【００１０】
本発明のキャッシュメモリ装置は、キャッシュデータを格納する格納手段と、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、を備えることを特徴とする。
【発明の効果】
【００１１】
上記アクセス回数が一致していれば、プログラムがメモリを局所的に参照しているであろうという推定が働く。本発明のキャッシュメモリ装置によれば、このアクセス回数の一致を条件として、リフィルサイズを大きくすることで、ヒット率を向上させ、キャッシュメモリに関するデータ転送を低減することができる。もってプログラムの動作性能を高めることができる。
【図面の簡単な説明】
【００１２】
【図１】キャッシュメモリ装置を含む情報処理装置の構成を示す図
【図２】キャッシュメモリ装置の構成を示すブロック図
【図３】アドレス解析部が取得するアドレス情報の一例を示す図
【図４】キャッシュデータ格納部が管理するキャッシュデータの一例を示す図
【図５】リードライト回数管理部が管理する情報の一例を示す図
【図６】キャッシュメモリ装置の動作を示すフロー図
【図７】回数カウントに関する動作を示すフロー図
【図８】回数リセットに関する動作を示すフロー図
【図９】ラインサイズ決定に関する動作を示すフロー図
【図１０】管理対象ラインを設定する例を説明するための図
【発明を実施するための形態】
【００１３】
以下、実施の形態について、図面を参照しながら説明する。
＜構成＞
図１は、キャッシュメモリ装置を含む情報処理装置１０００の構成を示す図である。
【００１４】
情報処理装置１０００は、例えば、ＰＣ（Personal Computer）等の汎用のコンピュータから構成される。
【００１５】
この情報処理装置１０００は、プロセッサ１、メモリ装置２、通信装置３４、入力装置４０、表示装置４５、タイマ回路５１及び割り込みコントローラ５５を備えている。これらの装置は、バスライン５０を通じて互いに接続されている。
【００１６】
また、バスライン５０には、ＨＤＤ（Hard Disk Drive）２５，読取装置３２，入力装置４０及び表示装置４５が、それぞれＩ／Ｆ（インタフェース）２６，３５，４１及び４６を通じて接続されている。
【００１７】
プロセッサ１は、３つのプロセッサ１１，１２，１３から構成されている。各プロセッサは、ＣＰＵ（Central Processing Unit，中央演算処理装置）と呼ばれるものである。
【００１８】
メモリ装置２は、ＲＯＭ（Read Only Memory）２１及びＲＡＭ（Random Access Memory）２２を備えている。
【００１９】
ＲＯＭ２１は、プロセッサ１の動作を規定するコンピュータプログラム及びデータを記憶する機能を有し、例えばフラッシュＲＯＭのように書き込みが可能で電源を切っても記憶内容を保持できる不揮発性のメモリから構成される。ＲＡＭ２２は、プロセッサ１が処理を実行するのに伴って発生するデータを一時的に記憶する機能を有し、例えば電源を切ると記憶内容が保持されない揮発性のメモリから構成される。なお、コンピュータプログラム及びデータは、ＲＯＭ２１に代えてＨＤＤ２５に記憶させることもできる。
【００２０】
プロセッサ１は、ＲＯＭ２１またはＨＤＤ２５が格納するコンピュータプログラム及びデータを、必要に応じてＲＡＭ２２に書き込みつつ、コンピュータプログラムが規定する処理を実行する。
【００２１】
ＨＤＤ２５は、コンピュータプログラムやデータを記憶する装置である。
【００２２】
読取装置３２は、記録媒体３１（例えばＣＤ、ＤＶＤ、メモリカードなど）に記録されたコンピュータプログラムあるいはデータを読み取る装置である。
【００２３】
通信装置３４は、電話回線、ネットワーク線、無線、赤外線通信等の通信回線３３を通じて、外部と自身との間で、コンピュータプログラムやデータを交換する装置である。
【００２４】
入力装置４０は、ユーザの操作によりデータ等を入力する装置であり、キーボード、マウスや各種入力ボタンから構成される。
【００２５】
表示装置４５は、データ、画像等を画面に表示したり、データ等を音声で出力したりする装置であり、例えば19インチの液晶ディスプレイ(LCD:Liquid Crystal Display)とスピーカとから構成される。
【００２６】
タイマ回路５１は、一定の周期でタイマ割り込み信号を出力する装置である。
【００２７】
割り込みコントローラ５５は、タイマ回路５１、入力装置４０、プロセッサ１、ネットワークデバイスである通信装置３４、ＨＤＤ２５、読取装置３２などから送られる割り込み要求信号を、プロセッサ１へ中継する装置である。各装置からの割り込み要求信号には優先度が付けられている。この割り込みコントローラ５５は、同時に複数の装置から割り込みが発生した場合には、それらの要求を上記優先度に応じて調停する機能（arbitration）を有している。
【００２８】
図２は、キャッシュメモリ装置１０の構成を示すブロック図である。キャッシュメモリ装置１０は、プロセッサ１と外部メモリ２３１と協同して動作する。外部メモリ２３１としては、典型的には、図１に示すメモリ装置２に含まれるＲＡＭ２２が用いられる。
【００２９】
キャッシュメモリ装置１０は、アドレス解析部２０１、管理ライン判定部２０２、回数管理部２０３、ラインサイズ決定部２０４、ヒット／ミス判定部２０５、リフィル部２０６、キャッシュデータ格納部２０７を備えている。なお、キャッシュデータは、キャッシュライン(以下、単に「ライン」と呼ぶ。）と呼ばれる、一定のサイズのデータごとに管理される。また、キャッシュデータの各ラインは、インデクスの値により一意に識別しアクセスすることができる。
【００３０】
アドレス解析部２０１は、プロセッサ１から要求するデータの格納先を示すアドレスを受け取る。アドレス解析部２０１は、受け取ったアドレスから、ヒットを判定するために使用するタグと、キャッシュデータの格納オフセットを示すインデクスとに分離する。アドレス解析部２０１は、分離して得られたインデクスを管理ライン判定部２０２に渡し、タグとインデクスをヒット／ミス判定部２０５に渡す。
【００３１】
管理ライン判定部２０２は、プロセッサ１が要求するデータへのアクセスが、回数管理部２０３（後述するように回数管理部２０３はキャッシュメモリにおける全ラインのうちの、一部の所定のラインを管理している。）が管理対象としているラインへのアクセスであるかどうかを判定する機能を有している。
【００３２】
管理ライン判定部２０２は、管理対象ラインに対応付けられたインデクスを保持する。管理ライン判定部２０２は、アドレス解析部２０１からインデクスを受け取ると、そのインデクスが保持したインデクスにあたるかどうか判定する。管理ライン判定部２０２の典型的な構成としては、キャッシュメモリ装置として管理対象のインデクスが事前に定められ、そのインデクスでアクセスが発生した場合に、アサートされるような回路を備えていればよい。
【００３３】
また、管理ライン判定部２０２は、管理対象のラインであると判定すると、回数管理部２０３に管理対象のラインであることを通知する。これに対して、管理対象のラインではないと判定すると、回数管理部２０３及びラインサイズ決定部２０４に管理対象のラインではないことを通知する。
【００３４】
ヒット／ミス判定部２０５は、プロセッサ１が要求するデータがキャッシュデータとして存在するか（ヒット）、存在しないか（ミス）を判定する機能を有している。ヒット／ミス判定部２０５は、アドレス解析部２０１からタグとインデクスを受け取ると、インデクスをキャッシュデータ格納部２０７に渡す。次に、ヒット／ミス判定部２０５は、キャッシュデータ格納部２０７から、渡したインデクスに対応するキャッシュデータのタグを受け取る。ヒット／ミス判定部２０５は、アドレス解析部２０１から取得したタグと、キャッシュデータ格納部２０７に問い合わせて取得したタグを比較する。
【００３５】
そして、比較の結果、タグ同士が一致すればヒットと判定し、ヒット／ミス判定部２０５は、キャッシュデータ格納部２０７から該当するラインのデータを取得し、プロセッサ１に渡す。また、ヒット／ミス判定部２０５は、ヒットの旨を回数管理部２０３及びラインサイズ決定部２０４に通知する。これに対して比較の結果、タグ同士が一致しなければミスと判定し、ヒット／ミス判定部２０５は、ミスであることを回数管理部２０３及びラインサイズ決定部２０４に通知する。
【００３６】
また、ヒット／ミス判定部２０５は、ヒットかミスかに関わらず、回数管理部２０３及びラインサイズ決定部２０４に、アドレス解析部２０１から受け取ったタグとインデクスを渡す。
【００３７】
回数管理部２０３は、キャッシュメモリにおける全ラインのうちの、一部の所定のラインにおけるアクセス回数（リード回数及びライト回数）を記憶し、管理する機能を有する。この管理対象とするラインの決め方については後述する。
【００３８】
回数管理部２０３は、管理ライン判定部２０２から管理対象のラインへのアクセスであると通知を受けると、次にヒット／ミス判定部２０５から受け取ったインデクスに基づいて該当する管理対象のラインを特定する。
【００３９】
回数管理部２０３には、プロセッサ１からリード要求またはライト要求があった場合に通知する線が接続されている。回数管理部２０３は、この線を経由して通知されたリード要求またはライト要求と、ヒット／ミス判定部２０５からの通知がヒットかミスかに応じて管理するリード回数またはライト回数を更新する。
【００４０】
また、回数管理部２０３は、ヒット／ミス判定部２０５からミスであるという通知を受けた場合、回数管理部２０３は、アドレス解析部２０１から受け取ったタグとインデクスをリフィル部２０６に渡す。また、回数管理部２０３は、ラインサイズをリフィル部２０６に渡す。
【００４１】
また、回数管理部２０３は、ヒット／ミス判定部２０５からミスであるという通知を受けた場合で、管理対象のラインではないと判定の通知を受けていれば、その管理対象のラインではないインデクスの値に基づいて、管理対象のラインである代わりのインデクスを特定する。そして、特定したインデクスをラインサイズ決定部に通知する。
【００４２】
ラインサイズ決定部２０４は、回数管理部２０３から通知されたインデクスの、リードライト回数を参照して、リフィルすべきラインサイズを、１ラインサイズとするか複数ライン（例えば４ライン分）サイズとするかのいずれにするかを決定する機能を有している。
【００４３】
このラインを決定する処理は、ラインサイズ決定部２０４は、管理ライン判定部２０２から管理対象のラインではないと通知を受け、かつヒット／ミス判定部２０５からミスであると通知を受けたときに行われる。
【００４４】
この処理を詳しく述べると、ラインサイズ決定部２０４は、回数管理部２０３から管理対象のラインのインデクスを取得する。次に、ラインサイズ決定部２０４は、取得した全てのインデクスに対応するタグを、キャッシュデータ格納部２０７から取得する。また、ラインサイズ決定部２０４は、取得した全てのインデクスに対応するリードライト回数を回数管理部２０３から取得する。
【００４５】
ラインサイズ決定部２０４は、取得したタグ同士、リード回数同士及びライト回数同士が全て一致する場合、リフィルすべきラインサイズを大きな４ラインサイズと決定する。また、いずれかが一致しない場合、リフィルすべきラインサイズは通常の１ラインサイズと決定する。そして、決定したラインサイズと、リフィルするデータのアドレスとをリフィル部２０６に通知する。
【００４６】
リフィル部２０６は、回数管理部２０３あるいはラインサイズ決定部２０４からリフィル対象のデータが存在するアドレスと、リフィルすべきラインサイズを取得し、取得したアドレスに存在するデータを、取得したラインサイズで外部メモリ２３１から読み込む。
【００４７】
読み込み後、リフィル部２０６は、読み込んだデータと、そのデータのアドレスと、データのサイズの三者をキャッシュデータ格納部２０７に受け渡す。なお、リフィル部２０６は、上記データのアドレスとデータのサイズの代わりに、回数管理部２０３やラインサイズ決定部２０４からリフィルするタグとインデクスを取得し、キャッシュデータ格納部２０７に渡してもかまわない。
【００４８】
キャッシュデータ格納部２０７は、キャッシュのデータを格納・管理する機能を有する。キャッシュデータ格納部２０７は、格納したデータをライン単位で管理し、各ラインはインデクスによりどのラインかを一意に特定できるようになっている。また、キャッシュデータ格納部２０７は、各ライン毎に、各ラインにおけるデータが外部メモリ２３１においてどのアドレスのデータであるかを示すタグを関連づけて管理している。
【００４９】
キャッシュデータ格納部２０７は、ヒット／ミス判定部２０５からインデクスを受け取ると、インデクスによりラインを特定し、そのラインと対応付けて管理しているタグをヒット／ミス判定部２０５に返す。
【００５０】
キャッシュデータ格納部２０７は、リフィル部２０６からデータのサイズを受け取ると、管理するラインサイズからそのデータが何ライン分のデータであるか把握する。そして、リフィル部２０６からデータのアドレスを受け取ると、データのアドレスをアドレス解析部２０１に渡してタグとインデクスを受け取り、受け取ったインデクスによりラインを特定し、リフィル部２０６から受け取ったデータを、特定したラインのデータとして管理する。また、キャッシュデータ格納部２０７は、アドレス解析部２０１から受け取ったタグを、特定したラインに対応するタグとして管理する。なお、キャッシュデータ格納部２０７は、リフィル部２０６からデータのアドレスとデータのサイズを取得する代わりに、リフィルするタグとインデクスを取得し、キャッシュデータを更新してもかまわない。
【００５１】
キャッシュデータ格納部２０７は、リフィル部２０６から数ライン分のデータを受け取っている場合、後続するインデクスのラインに対応させてラインサイズ分のデータを管理する。キャッシュデータ格納部２０７は、アドレス解析部２０１から受け取ったタグを、後続するインデクスのラインに対応するタグとして管理する。キャッシュデータ格納部２０７は、リフィル部２０６から受け取った、全てのラインのデータに関して前述の動作を行い、キャッシュデータを管理する。
続いて、プロセッサ１がアドレス解析部２０１に渡すアドレスの例について説明する。図３には、一例として３２ビットにより構成されるアドレス４０１を示している。０から３１までの数値４０２は、アドレス４０１を構成する各ビットを、下位０ビット目から３１ビット目まで便宜上示すものである（３１ビット目が、最上位ビット）。
【００５２】
アドレス４０１は、１５ビット目から３１ビット目の上位アドレス４０３、５ビット目から１４ビット目の下位アドレス４０４を含んでいる。
【００５３】
アドレス解析部２０１は、アドレス４０１を受け取ると、ラインサイズ、キャッシュブロックサイズに応じて、アドレス４０１から、上位アドレス４０３をタグ、下位アドレス４０４をインデクスとして切り出す。
【００５４】
図３は一例として、ラインサイズが３２バイト、キャッシュブロックサイズ３２ＫＢの場合を示している。もっとも、例に挙げたラインサイズやキャッシュブロックサイズはあくまで一例に過ぎず、キャッシュメモリの構成に応じて変更可能である。
続いて、キャッシュデータ格納部２０７が管理するキャッシュデータの例について説明する。
【００５５】
図４の例では、キャッシュデータ格納部２０７は、「キャッシュデータ」２０７ｃと、このデータのラインを示す「インデクス」２０７ａ，このデータが外部メモリ２３１においてどのアドレスのデータであるかを示す「タグ」２０７ｂを管理している。
【００５６】
上述のように、このキャッシュデータ格納部２０７が格納しているデータのライン（インデクス）のうちの一部が回数管理部２０３が管理する管理対象ラインとなる。具体例を図５に示す。
【００５７】
回数管理部２０３は、管理対象ラインを示す「インデクス」２０３ａ、インデクスに対応する「リード回数」２０３ｂ，「ライト回数」２０３ｃを含む。
【００５８】
図５の例では、インデクス0x000〜0x003の４ラインの「セット１」と、インデクス0x200〜0x203の４ラインの「セット２」とが管理対象となっている。上述のように、各セットの先頭のインデクス0x000,0x200は、プログラムが使用するページ単位上においてインデクスが先頭になるラインである。
＜動作＞
以下、実施の形態に係るキャッシュメモリ装置の動作について説明する。
【００５９】
図６に示すように、まず、アドレス解析部２０１は、プロセッサ１からアドレスを受け取ると、そのアドレスをタグとインデクスに分離（抽出）する（Ｓ１１）。
【００６０】
次に、ヒット／ミス判定部２０５は、アドレス解析部２０１からタグとインデクスを受け取ると、キャッシュデータ格納部２０７に問い合わせてヒットかミスかを判定する（Ｓ１２）。この判定は、ヒット／ミス判定部２０５が、キャッシュデータ格納部２０７からインデクスに対応するキャッシュデータのタグを取得し、アドレス解析部２０１が分離したタグと比較し、両タグが一致していれば、ヒットと判定し（Ｓ１２：ヒット）、一致していなければミスと判定する（Ｓ１２：ミス）。
【００６１】
ヒットと判定すると（Ｓ１２：ヒット）、ヒット／ミス判定部２０５は、キャッシュデータ格納部２０７から、ステップＳ１１で分離したアドレスに対応するキャッシュデータを取得し、プロセッサ１に返す（Ｓ１３）。
【００６２】
そして、管理ライン判定部２０２は、ステップＳ１１で分離したアドレスに含まれるインデクスが、管理対象ラインのインデクスであるかどうかを判定する（Ｓ１４）。
【００６３】
管理対象ラインのインデクスであれば（Ｓ１４：Ｙｅｓ）、回数カウントの処理に移る（Ｓ１５，図７）。管理対象ラインのインデクスでなければ（Ｓ１４：Ｎｏ）、処理を終了する。
【００６４】
図７に示すように、回数カウント処理では、回数管理部２０３はアクセス対象のラインを特定し（Ｓ３１）、アクセスがリード要求であれば（Ｓ３２：リード）、該当する管理対象ラインのリード回数を１回加算する（Ｓ３３）。
【００６５】
アクセスがリード要求であれば（Ｓ３２：ライト）、回数管理部２０３は、該当する管理対象ラインのライト回数を１回加算する（Ｓ３４）。
【００６６】
具体的な例を挙げると、アクセス対象のラインが"0x000"でアクセスがリード要求であれば、回数管理部２０３は、管理対象ラインのインデクス"0x000"のリード回数2回（図５参照）に１回加算して3回へと更新する。また、アクセス対象のラインが"0x001"でアクセスがライト要求であれば、回数管理部２０３は、管理対象ラインのインデクス"0x001"のリード回数0回（図５参照）に１回加算して1回へと更新する。
【００６７】
このように、キャッシュヒット場合で（Ｓ１２：ヒット）、かつ管理対象ラインへのアクセスであれば（Ｓ１４：Ｙｅｓ）、回数管理部２０３は対応する管理対象ラインの回数をカウントすることとなる（Ｓ３１〜Ｓ３４）。
【００６８】
さて、ヒット／ミス判定部２０５がミスと判定すると（Ｓ１２：ミス）、管理ライン判定部２０２は、ステップＳ１１で分離したアドレスに含まれるインデクスが、管理対象ラインのインデクスであるかどうかを判定する（Ｓ１６）。
【００６９】
管理対象ラインのインデクスであれば（Ｓ１６：Ｙｅｓ）、回数リセットの処理に移る（Ｓ１７，図８）。
【００７０】
図８に示すように、回数リセット処理では、回数管理部２０３は、アクセス対象のラインの、リードライト回数を無効化（リセット）する（Ｓ４１）。そして、アクセスがリード要求であれば（Ｓ４２：リード）、該当する管理対象ラインのリード回数を１回に設定する（Ｓ４３）。
【００７１】
これに対して、アクセスがライト要求であれば（Ｓ４２：ライト）、回数管理部２０３は、該当する管理対象ラインのライト回数を１回に設定する（Ｓ４４）。
【００７２】
具体的な例を挙げると、アクセス対象のラインが"0x000"でアクセスがリード要求であれば、回数管理部２０３は、管理対象ラインのインデクス"0x000"のリード回数2回、ライト回数3回（図５参照）を共に0回へとリセットし、その後、リード回数を1回に再設定する。
【００７３】
このような回数のリセット処理を終えると、リフィル部２０６は、外部メモリ２３１から該当するライン（ステップＳ１１で分離したアドレスに含まれるインデクスに対応するライン）のデータを取得し、キャッシュデータ格納部２０７のキャッシュデータにリフィルする（Ｓ１９）。
【００７４】
具体的には、リフィル部２０６は回数管理部２０３から受け取ったリフィル対象のアドレスに対応するデータを外部メモリ２３１から読み込む。そして、リフィル部２０６は、読み込んだデータをキャッシュデータ格納部２０７に渡し、キャッシュデータとして格納させる。次に、リフィル部２０６は、外部メモリ２３１から読み込んだデータをプロセッサ１に返す。
【００７５】
管理対象ラインのインデクスでなければ（Ｓ１６：Ｎｏ）、管理ライン判定部２０２は、その旨を管理回数部２０３に通知する。通知を受けた回数管理部２０３は、自己が管理する管理対象ラインの中から、ステップＳ１１で取得したインデクスより小さく、かつ、最も近いインデクスのセットを特定する。例えば、ステップＳ１１で分離したアドレスに含まれるインデクスが、"0x280"（図４）とすると、このインデクス"0x280"より小さく、最も近いインデクスのセット２（図５："0x200"〜"0x203"の４ラインのセット）と特定する（Ｓ２０）。
【００７６】
そして、ラインサイズ決定処理に移る（Ｓ２１，図９）。
【００７７】
ラインサイズ決定処理では、ラインサイズ決定部２０４は、管理ライン判定部２０２から特定されたセットを示す情報を受信すると、受信したセットに対応するリードライト回数を回数管理部２０３から取得するとともに、取得したセットに属する管理対象ラインのタグをキャッシュデータ格納部２０７から取得する（Ｓ５１）。
【００７８】
そして、取得した全ての管理対象ラインのリード回数同士・ライト回数同士がすべて一致するかどうかを判定する（Ｓ５２）。例えば、インデクスのセットがセット２と特定されたのであれば、セット２に属する"0x200"〜"0x203"の４ラインのリード回数は0回、ライト回数は2回とすべて一致する（図５参照）ので肯定的に判定する。これに対して、インデクスのセットがセット１と特定されたのであれば、セット１に属する"0x000"〜"0x003"の４ラインのリード回数は、2回，2回，0回，1回とまちまちである（図５参照）ので、否定的に判定する。
【００７９】
ステップＳ５２で一致と判定すると（Ｓ５２：Ｙｅｓ）、続いて、ラインサイズ決定部２０４は、取得したすべての管理対象ラインのタグ同士がすべて一致するかどうかを判定する（Ｓ５３）。例えば、インデクスのセットがセット２と特定されたのであれば、セット２に属する"0x200"〜"0x203"の４ラインのタグは、"0x02000"とすべて一致している（図４参照）ので、肯定的に判定する。これに対して、インデクスのセットがセット１と特定されたのであれば、セット１に属する"0x000"〜"0x003"の４ラインのタグは、0x01c80,0x01c80,0x10000,0x00040と一部の２つが一致しているに過ぎず、全一致ではないので、否定的に判定する。
【００８０】
ラインサイズ決定部２０４は、取得した全ての管理対象ラインのリード回数同士・ライト回数同士がすべて一致し（Ｓ５２：Ｙｅｓ）、かつ、取得したすべての管理対象ラインのタグ同士がすべて一致した場合（Ｓ５３：Ｙｅｓ）には、リフィルすべきラインサイズを４ライン分のサイズに決定する（Ｓ５４）。
【００８１】
ステップＳ５２，Ｓ５３の両判定のいずれかを満たさなければ（Ｓ５２：Ｎｏ，or Ｓ５３：Ｎｏ）、ラインサイズ決定部２０４は通常のリフィルすべきラインサイズを１ライン分のサイズに決定する。
【００８２】
このようなラインサイズ決定処理を終えると、リフィル部２０６は、外部メモリ２３１から該当するライン（ステップＳ１１で分離したアドレスに含まれるインデクスに対応するライン）のデータを取得し、キャッシュデータ格納部２０７のキャッシュデータにリフィルする（Ｓ１９）。
【００８３】
特に、リフィル部２０６は、リフィルサイズが４ラインであれば（Ｓ５４）、対応するラインのみならず、このラインよりインデクッスが後続する３ラインについても、合わせてリフィルを行う。例えば、ステップＳ１１で分離したアドレスに含まれるインデクスが"0x280"ならば、リフィル部２０６は"0x280"のみならず後続する"0x281"〜"0x283"の３ラインの合計４ラインをリフィル対象とすることとなる。
【００８４】
一般にプログラムはメモリをページ単位で使用・管理するものである。このため、同じページ単位に対応するインデクスのリード回数及びライト回数が一致していれば、プログラムが連続的な（シーケンシャルな）ふるまいをしていることが推定できる。このため、リード回数及びライト回数の一致を条件として通常より大きなラインサイズをリフィルすると、このリフィルしたデータが後々使用される可能性が高くなる（ヒット率が高くなる）ことが期待できる。
【００８５】
本実施の例を用いて説明すると、管理対象ライン"0x200"〜"0x203"はリード回数・ライト回数がすべて一致している（図５参照）ため、プログラムが連続的な挙動をしている可能性が高い。このため、"0x280"のみならず"0x281"〜"0x283"をもリフィルすることで、リフィル後にライン"0x281"〜"0x283"へのアクセスが発生して（プログラムが"0x281"〜"0x283"参照して）キャッシュヒットとなる確率を高くすることできる。
【００８６】
また、ある同じページ単位に対応するインデクスに関しては、その先頭部分のインデクスがプログラムの挙動が最も良く現れる。このため、"0x200"〜"0x203"などのような先頭部分を管理対象ラインとして回数の一致を見ることで、プログラムの挙動を的確に反映したリフィルサイズとすることができる。
＜補足１＞
以上、本実施の形態について説明したが、本発明は上記の内容に限定されず、本発明の目的とそれに関連又は付随する目的を達成するための各種形態においても実施可能であり、例えば、以下であっても構わない。
【００８７】
（１）図９の例では、回数の一致を判定した後でタグの一致を判定するという順番であったが、この順番はこれに限らず反転させてもよい（ステップＳ５３の次にＳ５２としてもよい）。
【００８８】
また、ステップＳ５３の処理は、データが外部メモリ２３１においてどのアドレスのデータであるかを示すタグ同士の一致を判断している。この判断により、タグが不一致で偶然リード回数・ライト回数が一致していたものに過ぎない、言い換えるとプログラムのふるまいを鮮明に反映しない回数の一致を排除でき、より適切なリフィルサイズの決定に寄与することができる。もっとも、ステップＳ５３の処理は必須ではなくステップＳ５３をスキップするやり方も考え得る。
【００８９】
（２）実施の形態では詳細は述べなかったが、一般的なキャッシュ技術と同様に、キャッシュデータ格納部２０７においては、データの有効（valid）・無効（invalid）を示す有効タグや、データの一貫性（consistency）を保証するためのダーティ(dirty)タグを、ライン毎に管理するようにしてもよい。
【００９０】
また、特に、有効タグを管理する場合には、ヒット／ミス判定部２０５は、タグの一致に加えて、有効タグが有効を示す場合を条件にヒットと判定するようにしてもよい。
【００９１】
（３）実施の形態では、ラインサイズ決定部２０４は、リフィルのラインサイズを大きくするときにライン数は、管理対象ラインの１セットに含まれるライン数と同じ４ライン（図９：Ｓ５４）に決定するとしたが、これに限られない。例えば２ライン、８ラインとすることもできる。
【００９２】
要は、管理対象ラインのリード回数・ライト回数が一致している場合のラインサイズＡが、一致していない場合のラインサイズＢより相対的に大きければ（Ａ＞Ｂ）、ラインサイズの最適化に役立てることができる。
【００９３】
（４）実施の形態では、外部メモリ２３１としては、ＲＡＭ２２を挙げたが、外部メモリ２３１の要件としてはＲＡＭ２２に限らず、キャッシュメモリ装置１０より記憶階層（memoryhierarchy）がより下位層のメモリであれば足りる。例えば、ＨＤＤ２５や読取装置３２から読み込まれる記録媒体３１を外部メモリ２３１として用いてもよい。
【００９４】
（５）管理回数部２０３における管理対象ラインを、どのように設定するかについて述べる。実施の形態のように、インデクスの値が連続する複数のラインからなるラインセットを複数セット分構成し、ラインセット同士は一定間隔空けるようにする。この一定間隔は、プログラムが使用するメモリ単位（メモリにおけるプログラムの管理単位）の間隔に合わせ、各ラインセットは、メモリ単位の先頭に相当するように設けることが好ましい。なお、プログラムの挙動を精度良く推定するためには、先頭に設けることが最良であるものの、場合によってはメモリ単位の中程に各ラインセットが位置するようにしても構わない。
【００９５】
管理対象ラインのさらなる具体例を図１０に示す。図１０に示すように、プログラムが使用するメモリ単位が４キロバイトで、キャッシュラインサイズが３２バイトであれば、インデクス０ｘ８０（１２８）間隔でラインセットを設ける。そして各ラインセットは、インデクス0x000、0x080、0x100などから、それぞれ後続する４ライン分をセットとすることが考えられる。
【００９６】
なお、セットとするラインの数は、複数（２ライン以上）であれば足り、例えば、８ラインとしてもよい。
【００９７】
（６）図９のステップＳ５２のＹｅｓは、リード回数同士がすべて０回かつライト回数同士がすべて０回の場合を除くとしても構わない。なぜならば、両者が共にすべて０回ならば、プログラムの挙動を推定する材料としては最適でない場合があるからである。
【００９８】
（７）実施の形態では、情報処理装置１０００はＰＣとして説明したが、これに限らず、ＰＤＡ（Personal Digital Assistance）や携帯電話機等の携帯通信端末でもよい。また、情報処理装置１０００は、それ自体としてユーザの使用に供するものでもよいし、様々な電子機器に組み込まれている態様でもよい。
【００９９】
（８）実施の形態では、プロセッサ１は、ＣＰＵとして説明したが、これに限らず、メディア処理用やグラフィック処理用のプロセッサ、ＤＳＰ（DigitalSignal Processor）などであってもよい、また、プロセッサは、単一のプロセッサで構成されてもよく、複数のプロセッサで構成されてもよい。
【０１００】
（９）図２の各機能ブロックは、典型的にはプロセッサと外部メモリとの間に存在するキャッシュメモリとして実現されるが、集積回路であるＬＳＩとしてもよい。これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（FieldProgrammable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用してもよい。さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。
【０１０１】
（１０）実施の形態で示した動作などを各種情報処理装置のプロセッサ、及びそのプロセッサに接続された各種回路に実行させるためのプログラムコードからなる制御プログラムを、記録媒体に記録すること、又は各種通信路等を介して流通させ頒布することもできる。このような記録媒体には、ICカード、HDD,光ディスク、フレキシブルディスク、ROMなどの非一時的な(non-transitory)な記録媒体が含まれる。流通、頒布された制御プログラムはプロセッサに読み出され得るメモリ等に格納されることにより利用に供され、そのプロセッサがその制御プログラムを実行することにより実施の形態で示したような各種機能が実現されることになる。
【０１０２】
（１１）実施の形態や、本補足１で挙げた具体的なスペック値（ラインサイズ、キャッシュブロックサイズなど）はあくまで一例に過ぎず、キャッシュメモリの構成に応じて適宜変更可能である。
＜補足２＞
本実施の形態は、次の態様を含むものである。
（１）本実施の形態に係るキャッシュメモリ装置は、キャッシュデータを格納する格納手段と、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、を備えることを特徴とする。
（２）前記複数のラインセットのそれぞれは、インデクスが連続する値で並んだ複数のラインからなり、前記特定手段は、前記アドレス抽出手段が抽出したインデクスの値よりも小さく、かつ、最も近い値の所定インデクスを含むラインセットを特定するとしても構わない。
（３）前記格納手段が格納するキャッシュデータは、プログラムが読み出しおよび書き込みを行うためのページ単位で管理された主メモリのデータであって、
前記複数のラインセットのそれぞれは、前記主メモリにおけるページ単位毎に、一対一に対応しており、各ラインセットの先頭のインデクスの値は、前記主メモリにおけるページ単位の先頭に対応する値であるとしても構わない。
（４）前記格納手段は、前記キャッシュデータを、このデータの主メモリにおける所在を示すタグに関係付けてライン単位で格納し、前記インデクスは前記格納手段におけるラインを指定するものであって、前記決定手段は、特定されたラインセットを構成する全ラインそれぞれに対応するすべてのタグを前記格納手段から取得し、前記特定されたラインセットを構成する全ラインそれぞれのアクセス回数のすべてが一致している場合において取得されたすべてのタグのすべてが一致しているのでなければ、リフィルすべきラインサイズを前記第１ラインサイズと決定し、取得されたすべてのタグのすべてが一致していれば、リフィルすべきラインサイズを前記第２ラインサイズと決定するとしても構わない。
【０１０３】
この構成によれば、より確実にプログラムの挙動を推定でき、適切なリフィルサイズの決定に資する。
（５）前記アクセス要求には、リード要求とライト要求の２種類が有り、
前記管理手段が管理する前記アクセス回数は、リード回数とライト回数とを含み、前記カウント手段は、前記ヒット判定手段によりヒットと判定されると、この判定の基としたアクセス要求がリード要求であれば対応するインデクスのリード回数を１回増やし、判定の基としたアクセス要求がライト要求であれば対応するライト回数を１回増やし、前記決定手段は、特定されたラインセットを構成する全ラインそれぞれのライト回数がすべてが一致しており、かつ、特定されたラインセットを構成する全ラインそれぞれのリード回数がすべてが一致している場合には、リフィルすべきラインサイズを前記第２ラインサイズと決定し、特定されたラインセットを構成する全ラインそれぞれのライト回数がすべて一致しているのでない場合、または、特定されたラインセットを構成する全ラインそれぞれのリード回数がすべて一致しているのでない場合には、
リフィルすべきラインサイズを前記第１ラインサイズと決定するとしても構わない。
（６）前記カウント手段は、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記アクセス要求に含まれるインデクスに対応するラインのリード回数とライト回数とを含むアクセス回数をリセットし、リセット後、アクセス要求がリード要求かライト要求かに応じて、対応するインデクスのリード回数またはライト回数を１回増やすとしても構わない。
（７）前記格納手段は、前記キャッシュデータを、このデータの主メモリにおける所在を示すタグに関係付けてライン単位で格納し、前記インデクスは前記格納手段におけるラインを指定するものであって、前記ヒット判定手段は、前記アドレス抽出手段により抽出されたインデクスに対応するインデクスを前記格納手段が格納するデータの中から特定し、特定されたインデクスに関係付けられたタグと、アドレス抽出手段により抽出されたタグとを比較し、両タグが一致してしればヒットと判定し不一致であればミスと判定するとしても構わない。
（８）本実施の形態に係るキャッシュメモリ制御方法は、  キャッシュデータを格納する格納ステップと、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出ステップと、アドレス抽出ステップが抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定ステップと、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理ステップと、前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定ステップによりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウントステップと、前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定ステップによりミスと判定されると、前記管理ステップで管理しているラインの中からこのインデクスに対応するラインセットを特定する特定ステップと、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定ステップと、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィルステップと、を含むことを特徴とする。
（９）本実施の形態に係るプログラムは、キャッシュメモリ装置に、キャッシュメモリ制御処理を実行させるプログラムであって、前記キャッシュメモリ制御処理は、キャッシュデータを格納する格納ステップと、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出ステップと、アドレス抽出ステップが抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定ステップと、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理ステップと、前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定ステップによりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウントステップと、前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定ステップによりミスと判定されると、前記管理ステップで管理しているラインの中からこのインデクスに対応するラインセットを特定する特定ステップと、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定ステップと、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィルステップと、を含むことを特徴とする。
（１０）本実施の形態に係る集積回路は、キャッシュデータを格納する格納手段と、アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、を備えることを特徴とする。
【産業上の利用可能性】
【０１０４】
本発明にかかるキャッシュメモリ装置は、プログラムの動作に応じて即時にリフィルするラインサイズを変更する機能を有し、情報処理装置として有用である。また、情報機器、ＡＶ機器、通信機器、家電機器などの組み込み機器などのコンピュータを搭載する機器において有用である。
【符号の説明】
【０１０５】
１，１１，１２，１３  プロセッサ
２  メモリ装置
１０  キャッシュメモリ装置
２１  ＲＯＭ
２２  ＲＡＭ
２５  ＨＤＤ
２６，３５，４１，４６  インタフェース（Ｉ／Ｆ）
３１  記録媒体
３２  読取装置
３３  通信回線
３４  通信装置
４０  入力装置
４５  表示装置
５０  バスライン
５１  タイマ回路
５５  割込コントローラ
２０１  アドレス解析部（アドレス抽出部）
２０２  管理ライン判定部
２０３  回数管理部
２０４  ラインサイズ決定部
２０５  ヒット／ミス判定部
２０６  リフィル部
２０７  キャッシュデータ格納部
２３１  外部メモリ
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
キャッシュデータを格納する格納手段と、
アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、
アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、
それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、
前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、
前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、
特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、
すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、
すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、
決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、
を備えることを特徴とするキャッシュメモリ装置。
【請求項２】
前記複数のラインセットのそれぞれは、インデクスが連続する値で並んだ複数のラインからなり、
前記特定手段は、前記アドレス抽出手段が抽出したインデクスの値よりも小さく、かつ、最も近い値の所定インデクスを含むラインセットを特定する
ことを特徴とする請求項１に記載のキャッシュメモリ装置。
【請求項３】
前記格納手段が格納するキャッシュデータは、プログラムが読み出しおよび書き込みを行うためのページ単位で管理された主メモリのデータであって、
前記複数のラインセットのそれぞれは、前記主メモリにおけるページ単位毎に、一対一に対応しており、
各ラインセットの先頭のインデクスの値は、前記主メモリにおけるページ単位の先頭に対応する値である
ことを特徴とする請求項２に記載のキャッシュメモリ装置。
【請求項４】
前記格納手段は、前記キャッシュデータを、このデータの主メモリにおける所在を示すタグに関係付けてライン単位で格納し、前記インデクスは前記格納手段におけるラインを指定するものであって、
前記決定手段は、特定されたラインセットを構成する全ラインそれぞれに対応するすべてのタグを前記格納手段から取得し、
前記特定されたラインセットを構成する全ラインそれぞれのアクセス回数のすべてが一致している場合において、
取得されたすべてのタグのすべてが一致しているのでなければ、リフィルすべきラインサイズを前記第１ラインサイズと決定し、
取得されたすべてのタグのすべてが一致していれば、リフィルすべきラインサイズを前記第２ラインサイズと決定する
ことを特徴とする請求項１に記載のキャッシュメモリ装置。
【請求項５】
前記アクセス要求には、リード要求とライト要求の２種類が有り、
前記管理手段が管理する前記アクセス回数は、リード回数とライト回数とを含み、
前記カウント手段は、前記ヒット判定手段によりヒットと判定されると、この判定の基としたアクセス要求がリード要求であれば対応するインデクスのリード回数を１回増やし、判定の基としたアクセス要求がライト要求であれば対応するライト回数を１回増やし、
前記決定手段は、
特定されたラインセットを構成する全ラインそれぞれのライト回数がすべてが一致しており、かつ、特定されたラインセットを構成する全ラインそれぞれのリード回数がすべてが一致している場合には、リフィルすべきラインサイズを前記第２ラインサイズと決定し、
特定されたラインセットを構成する全ラインそれぞれのライト回数がすべて一致しているのでない場合、
または、特定されたラインセットを構成する全ラインそれぞれのリード回数がすべて一致しているのでない場合には、
リフィルすべきラインサイズを前記第１ラインサイズと決定する
ことと特徴とする
請求項１に記載のキャッシュメモリ装置。
【請求項６】
前記カウント手段は、前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記アクセス要求に含まれるインデクスに対応するラインのリード回数とライト回数とを含むアクセス回数をリセットし、
リセット後、アクセス要求がリード要求かライト要求かに応じて、対応するインデクスのリード回数またはライト回数を１回増やす
ことを特徴とする請求項５に記載のキャッシュメモリ装置。
【請求項７】
前記格納手段は、前記キャッシュデータを、このデータの主メモリにおける所在を示すタグに関係付けてライン単位で格納し、前記インデクスは前記格納手段におけるラインを指定するものであって、
前記ヒット判定手段は、前記アドレス抽出手段により抽出されたインデクスに対応するインデクスを前記格納手段が格納するデータの中から特定し、特定されたインデクスに関係付けられたタグと、アドレス抽出手段により抽出されたタグとを比較し、両タグが一致してしればヒットと判定し不一致であればミスと判定する
ことを特徴とする請求項１に記載のキャッシュメモリ装置。
【請求項８】
キャッシュデータを格納する格納ステップと、
アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出ステップと、
アドレス抽出ステップが抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定ステップと、
それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理ステップと、
前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定ステップによりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウントステップと、
前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定ステップによりミスと判定されると、前記管理ステップで管理しているラインの中からこのインデクスに対応するラインセットを特定する特定ステップと、
特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、
すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、
すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定ステップと、
決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィルステップと、
を含む
ことを特徴とするキャッシュメモリ制御方法。
【請求項９】
キャッシュメモリ装置に、キャッシュメモリ制御処理を実行させるプログラムであって、
前記キャッシュメモリ制御処理は、
キャッシュデータを格納する格納ステップと、
アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出ステップと、
アドレス抽出ステップが抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定ステップと、
それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理ステップと、
前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定ステップによりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウントステップと、
前記アドレス抽出ステップで抽出したインデクスが、前記管理ステップで管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定ステップによりミスと判定されると、前記管理ステップで管理しているラインの中からこのインデクスに対応するラインセットを特定する特定ステップと、
特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、
すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、
すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定ステップと、
決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィルステップと、
を含むことを特徴とするプログラム。
【請求項１０】
キャッシュデータを格納する格納手段と、
アドレスの指定を含むアクセス要求を受けると、このアドレスからタグとインデクスとを抽出するアドレス抽出手段と、
アドレス抽出手段が抽出したタグとインデクスに基づき、前記キャッシュデータに関してヒットかミスかを判定するヒット／ミス判定手段と、
それぞれインデクスの値が並んだ複数のラインからなる複数のラインセットについて、各ラインセットを構成するライン毎のアクセス回数を管理する管理手段と、
前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しており、このインデクスに関して前記ヒット／ミス判定手段によりヒットと判定されると、このインデクスに対応するラインのアクセス回数を１回増やすカウント手段と、
前記アドレス抽出手段が抽出したインデクスが前記管理手段が管理しているラインのインデクスを示しておらず、このインデクスに関して前記ヒット／ミス判定手段によりミスと判定されると、前記管理手段が管理するラインの中からこのインデクスに対応するラインセットを特定する特定手段と、
特定されたラインセットを構成する全ラインそれぞれのアクセス回数が、
すべてが一致しているのでなければリフィルすべきラインサイズを第１ラインサイズと決定し、
すべてが一致していればリフィルすべきラインサイズを前記第１ラインサイズより大きい第２ラインサイズと決定する決定手段と、
決定されたラインサイズに基づいて、前記キャッシュデータのリフィルを行うリフィル手段と、
を備えることを特徴とする集積回路。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2010116735.tif 000013
【図２】
2010116735.tif 000014
【図３】
2010116735.tif 000015
【図４】
2010116735.tif 000016
【図５】
2010116735.tif 000017
【図６】
2010116735.tif 000018
【図７】
2010116735.tif 000019
【図８】
2010116735.tif 000020
【図９】
2010116735.tif 000021
【図１０】
2010116735.tif 000022
【国際調査報告】
2010116735.tif 000023
2010116735.tif 000024
2010116735.tif 000025
2010116735.tif 000026