(57)【要約】データアレイ１０５，１０６のウェイ数よりもアドレスアレイ１０２，１０３，１０４のウェイ数を多くする。ミスヒット時に、ミスヒットしたアドレスのブロックデータをメモリ３から読み出すリクエストを発行するとともに、空いているアドレスアレイのアドレスエントリにミスヒットしたアドレスを格納する。その一方で、このミスヒット時には、読み出しリクエストに対応したブロックデータがメモリ３からキャッシュメモリシステム１に到着するまでは、置き換えられるブロックデータに対応するアドレスアレイのアドレスエントリとデータアレイのデータエントリは有効なまま保持する。この構成により、読み出しリクエストに対応したブロックデータがメモリ３からキャッシュメモリシステム１に到着する前に、置き換えられるブロックデータに対するＣＰＵ２からのアクセスがあっても、キャッシュヒットとして扱うことができる。
2010098152.tif 000002
【特許請求の範囲】
【請求項１】
演算装置および記憶装置と接続されるキャッシュメモリシステムであって、
前記記憶装置のアドレスを所定数ごとにまとめた多数のアドレス群のうち、前記多数のアドレス群よりも数が少ない複数のアドレス群を格納するアドレス格納手段と、
前記複数のアドレス群のそれぞれに対応する複数のブロックデータを格納するデータ格納手段と、
前記演算装置からの受付アドレスが前記アドレス格納手段内にない場合、前記複数のアドレス群の中から置き換え対象アドレス群を特定し、かつ、前記多数のアドレス群のうち前記受付アドレスを含む該当アドレス群を、前記アドレス格納手段に格納し、その後、前記該当アドレス群に対応する該当ブロックデータを前記記憶装置から読み出し、前記該当ブロックデータを前記データ格納手段に格納する制御手段と、を含み、
前記制御手段は、前記置き換え対象アドレス群を特定してから前記該当ブロックデータを前記記憶装置から読み出すまでの読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けた場合には、キャッシュヒットと判定し、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けなかった場合には、前記該当ブロックデータを、前記置き換え対象アドレス群に対応する対応ブロックデータに代えて、前記データ格納手段に格納すると共に、前記置き換え対象アドレス群を無効化する、キャッシュメモリシステム。
【請求項２】
前記制御手段は、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けた場合、さらに、前記置き換え対象アドレス群を、前記複数のアドレス群のうちの他のアドレス群に変更し、前記該当ブロックデータを、変更後の置き換え対象アドレス群に対応するブロックデータに代えて、前記データ格納手段に格納すると共に、前記変更後の置き換え対象アドレス群を無効化する、請求項１に記載のキャッシュメモリシステム。
【請求項３】
前記多数のアドレス群のそれぞれは、前記記憶装置の各アドレスを上位ビットと中位ビットと下位ビットに分けた際に、前記上位ビットの値および前記中位ビットの値が共通するアドレスからなるものであり、
前記データ格納手段は、前記中位ビットにて表現されうる値のそれぞれを示すインデックスごとに、当該インデックスに対応するＮ個（Ｎは２以上の整数）のデータ格納領域を有し、
前記複数のブロックデータのそれぞれは、前記データ格納領域のうち、当該ブロックデータに対応するアドレス群の中位ビットの値を示すインデックスに対応するデータ格納領域に個別に格納され、
前記アドレス格納手段は、前記インデックスごとに、当該インデックスに対応する前記Ｎよりも数が多いアドレス格納領域を有し、
前記複数のアドレス群のそれぞれは、前記アドレス格納領域のうち、当該アドレス群の中位ビットの値を示すインデックスに対応するアドレス格納領域に個別に格納され、
前記制御手段は、前記受付アドレスが前記アドレス格納手段内にない場合、前記置き換え対象アドレス群を、前記複数のアドレス群のうち前記受付アドレスと同じ中位ビットを含むアドレス群の中から特定し、かつ、前記該当アドレス群を、前記受付アドレスの中位ビットの値を示すインデックスに対応する前記アドレス格納領域のうち、未使用または無効化されているアドレス格納領域に格納し、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けなかった場合には、前記該当ブロックデータを、前記対応ブロックデータに代えて、前記対応ブロックデータを格納しているデータ格納領域に格納すると共に、前記置き換え対象アドレス群を無効化する、請求項１または２に記載にキャッシュメモリシステム。
【請求項４】
前記アドレス格納領域は、さらに、自己に格納されたアドレス群に対応するブロックデータを格納しているデータ格納領域を示す格納先情報を格納し、
前記制御手段は、前記格納先情報を参照して、前記対応ブロックデータを格納しているデータ格納領域を特定する、請求項３に記載のキャッシュメモリシステム。
【請求項５】
前記制御手段は、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けた場合、さらに、前記置き換え対象アドレス群を、前記複数のアドレス群のうち前記受付アドレスと同じ中位ビットを含むアドレス群のうちの他のアドレス群に変更し、前記該当ブロックデータを、変更後の置き換え対象アドレス群に対応する関連ブロックデータに代えて、前記関連ブロックデータを格納しているデータ格納領域に格納すると共に、前記変更後の置き換え対象アドレス群を無効化する、請求項３または４に記載のキャッシュメモリシステム。
【請求項６】
演算装置および記憶装置と接続されるキャッシュメモリシステムが行うキャッシュメモリ制御方法であって、
前記記憶装置のアドレスを所定数ごとにまとめた多数のアドレス群のうち、前記多数のアドレス群よりも数が少ない複数のアドレス群をアドレス格納手段に格納し、
前記複数のアドレス群のそれぞれに対応する複数のブロックデータをデータ格納手段に格納し、
前記演算装置からの受付アドレスが前記アドレス格納手段内にない場合、前記複数のアドレス群の中から置き換え対象アドレス群を特定し、かつ、前記多数のアドレス群のうち前記受付アドレスを含む該当アドレス群を、前記アドレス格納手段に格納し、その後、前記該当アドレス群に対応する該当ブロックデータを前記記憶装置から読み出し、前記該当ブロックデータを前記データ格納手段に格納する動作を実行すること、を含み、
前記動作を実行することは、前記置き換え対象アドレス群を特定してから前記該当ブロックデータを前記記憶装置から読み出すまでの読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けた場合には、キャッシュヒットと判定し、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けなかった場合には、前記該当ブロックデータを、前記置き換え対象アドレス群に対応する対応ブロックデータに代えて、前記データ格納手段に格納すると共に、前記置き換え対象アドレス群を無効化することを含む、キャッシュメモリ制御方法。
【請求項７】
前記動作を実行することは、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けた場合、さらに、前記置き換え対象アドレス群を、前記複数のアドレス群のうちの他のアドレス群に変更し、前記該当ブロックデータを、変更後の置き換え対象アドレス群に対応するブロックデータに代えて、前記データ格納手段に格納すると共に、前記変更後の置き換え対象アドレス群を無効化することを含む、請求項６に記載のキャッシュメモリ制御方法。
【請求項８】
前記アドレス群のそれぞれは、前記記憶装置の各アドレスを上位ビットと中位ビットと下位ビットに分けた際に、前記上位ビットの値および前記中位ビットの値が共通するアドレスからなるものであり、
前記データ格納手段は、前記中位ビットにて表現されうる複数の値のそれぞれを示すインデックスごとに、当該インデックスに対応するＮ個（Ｎは２以上の整数）のデータ格納領域を有し、
前記複数のブロックデータのそれぞれは、複数の前記データ格納領域のうち、当該ブロックデータに対応するアドレス群の中位ビットの値を示すインデックスに対応するデータ格納領域に個別に格納され、
前記アドレス格納手段は、前記インデックスごとに、当該インデックスに対応する前記Ｎよりも数が多いアドレス格納領域を有し、
前記複数のアドレス群のそれぞれは、複数の前記アドレス格納領域のうち、当該アドレス群の中位ビットの値を示すインデックスに対応するアドレス格納領域に個別に格納され、
前記動作を実行することは、前記受付アドレスが前記アドレス格納手段内にない場合、前記置き換え対象アドレス群を、前記複数のアドレス群のうち前記受付アドレスと同じ中位ビットを含むアドレス群の中から特定し、かつ、前記該当アドレス群を、前記受付アドレスの中位ビットの値を示すインデックスに対応する前記アドレス格納領域のうち、未使用または無効化されているアドレス格納領域に格納し、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けなかった場合には、前記該当ブロックデータを、前記対応ブロックデータに代えて、前記対応ブロックデータを格納しているデータ格納領域に格納すると共に、前記置き換え対象アドレス群を無効化することを含む、請求項６または７に記載のキャッシュメモリ制御方法。
【請求項９】
前記アドレス格納領域は、さらに、自己に格納されたアドレス群に対応するブロックデータを格納しているデータ格納領域を示す格納先情報を格納し、
前記動作を実行することは、前記格納先情報を参照して、前記対応ブロックデータを格納しているデータ格納領域を特定することを含む、請求項８に記載のキャッシュメモリ制御方法。
【請求項１０】
前記動作を実行することは、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けた場合、さらに、前記置き換え対象アドレス群を、前記複数のアドレス群のうち前記受付アドレスと同じ中位ビットを含むアドレス群のうちの他のアドレス群に変更し、前記該当ブロックデータを、変更後の置き換え対象アドレス群に対応する関連ブロックデータに代えて、前記関連ブロックデータを格納しているデータ格納領域に格納すると共に、前記変更後の置き換え対象アドレス群を無効化することを含む、請求項８または９に記載のキャッシュメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機システムで使用可能なキャッシュメモリシステムおよびキャッシュメモリ制御方法に関する。
【背景技術】
【０００２】
キャッシュメモリは、ＣＰＵ等の演算装置と主メモリとの間に設けられる。キャッシュメモリは、主メモリ内の一部のデータを格納する。キャッシュメモリは、演算装置とデータをやり取りする。【０００３】
キャッシュメモリは、１度アクセスされたデータは再度アクセスされる可能性が高いというアクセスの時間的な局所性（Temporal  Locality）と、１度アクセスされたデータの近傍のデータはアクセスされる可能性が高いというアクセスの空間的な局所性（Spatial  Locality）と、を用いて、コンピュータのメモリアクセス性能を向上させるために用いられる。【０００４】
しかしながら、実装されるキャッシュメモリの容量は、一般的に限られている。このため、限られた容量のキャッシュメモリを効率よく使ってキャッシュヒット率を向上させる手法が要求されている。【０００５】
主メモリから読み出された複数のデータからなるブロックデータが、キャッシュメモリ内の複数のデータ格納領域（以下「データエントリ」と称する）のうちのどのデータエントリに格納されるかは、キャッシュメモリのマッピング方式により異なる。なお、ブロックデータ内の複数のデータ主メモリでのアドレスは、連続している。【０００６】
最もキャッシュメモリを効率よく使用できる方式は、フルアソシアティブと呼ばれる方式である。フルアソシアティブ方式では、メモリから読み出されたブロックデータを、キャッシュメモリ内の複数のデータエントリのいずれにも格納することができる。【０００７】
しかしながら、フルアソシアティブ方式では、ＣＰＵから要求されたデータが、キャッシュメモリ内にあるかどうかを検索するとき、キャッシュメモリ内の全データエントリを、検索の対象にする必要がある。このため、検索の速度を短時間にすることが困難である。【０００８】
ＣＰＵから要求されたデータがキャッシュメモリ内にあるかどうかの検索を最も簡単に行える方式が、ダイレクトマップ方式である。【０００９】
ダイレクトマップ方式では、主メモリから読み出されたブロックデータは、キャッシュメモリ内の複数のデータエントリのうち、そのブロックデータのアドレスの中位ビットによって特定される１つのデータエントリに格納される。【００１０】
しかしながら、ダイレクトマップ方式では、アドレスの中位ビットが同一であるがアドレスの上位ビットが異なる複数のブロックデータ（以下「アドレス対応ブロックデータ」と称する）に対して、１つのデータエントリしか設定されていない。このため、この複数のアドレス対応ブロックデータを、同時にキャッシュメモリ内にキャッシュ（格納）することができない。【００１１】
これら２つ方式の中間にあたるのがＮ（Ｎは２以上の整数）ウェイセットアソシアティブと呼ばれる方式である。【００１２】
Ｎウェイセットアソシアティブ方式では、複数のアドレス対応ブロックデータを格納するためのＮ個のデータエントリがある。このため、Ｎ個のアドレス対応ブロックデータが、同時にキャッシュされることができる。また、各データエントリに１対１で対応する複数のアドレス格納領域（以下「アドレスエントリ」と称する）が設けられ、各アドレスエントリには、対応するデータエントリ内のブロックデータのアドレスが格納される。【００１３】
Ｎウェイセットアソシアティブ方式では、ＣＰＵから要求されたデータが、キャッシュメモリ内にあるかどうかを検索する場合には、その要求されたデータのアドレスの中位ビットに対応するＮ個のアドレスエントリが、検索される。【００１４】
特許文献１（特開平４−２７０４３１号公報）には、キャッシュミス時に他のブロックデータをキャッシュするために置き換えられたブロックデータ、つまり、キャッシュメモリから削除されたブロックデータ、を格納するヴィティムキャッシュメモリと呼ばれる装置が開示されている（段落００２３参照）。【００１５】
特許文献１に記載のヴィクティムキャッシュメモリは、フルアソシアティブ方式の小容量（数ブロック）のキャッシュメモリであり、キャッシュメモリによって置き換えられたブロックデータをキャッシュする。【００１６】
ヴィクティムキャッシュメモリ内のブロックデータがキャッシュヒットした場合は、ヒットされたブロックデータが、キャッシュメモリに戻される。【００１７】
ヴィクティムキャッシュメモリは、数ブロックデータの容量しか有していない。このため、ヴィクティムキャッシュメモリ内にブロックデータが留まっている時間は短いと考えられる。【００１８】
特許文献１が開示する技術は、一度キャッシュメモリにキャッシュされ、その後、置き換えられたブロックデータ、つまり、キャッシュメモリから削除されたブロックデータが、再び、しかも、置き換えられた直後に、アクセスされる可能性が高いことを利用して、キャッシュメモリのヒット率を向上させる技術である。【００１９】
一方、ＣＰＵにおけるマルチコア技術およびマルチスレッド技術の進歩により、ほぼ同時に実行される複数のスレッドによるメモリアクセス用に、キャッシュメモリが利用されるようになっている。【００２０】
これらのメモリアクセスは、複数の独立したスレッドにより行われ、メモリアクセスに関して因果関係はなく、ほぼ同時に複数のキャッシュミスが発生することになる。【００２１】
したがって、シングルコアまたはシングルスレッドの場合と比べると、ほぼ同時に発生しているキャッシュミスが多くなり、キャッシュミスによるメモリアクセスも同時に複数発行されている。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】特開平４−２７０４３１号公報
【発明の概要】
【発明が解決しようとする課題】
【００２３】
ヴィクティムキャッシュメモリを用いた技術では、複数のキャッシュミスがほぼ同時に発生するようなマルチコアまたはマルチスレッドによるＣＰＵからのメモリアクセスを効率よく処理することができない。【００２４】
なぜなら、まず、ヴィクティムキャッシュメモリは、小容量（数ブロック）のフルアソシアティブ方式のキャッシュメモリであるため、複数のキャッシュミスがほぼ同時に発生すると、キャッシュミスしたブロックデータの量が、ヴィクティムキャッシュメモリの容量を超えてしまう。また、複数のキャッシュミスに対処するために、ヴィクティムキャッシュメモリの容量を大きくすると、フルアソシアティブ方式を実現することが困難になる。また、キャッシュミスしたブロックデータを、ヴィクティムキャッシュメモリに移動する処理も必要となる。【００２５】
本発明の目的は、上述した課題を解決可能なキャッシュメモリシステムおよびキャッシュメモリ制御方法を提供することである。
【課題を解決するための手段】
【００２６】
本発明のキャッシュメモリシステムは、演算装置および記憶装置と接続されるキャッシュメモリシステムであって、前記記憶装置のアドレスを所定数ごとにまとめた多数のアドレス群のうち、前記多数のアドレス群よりも数が少ない複数のアドレス群を格納するアドレス格納部と、前記複数のアドレス群のそれぞれに対応する複数のブロックデータを格納するデータ格納部と、前記演算装置からの受付アドレスが前記アドレス格納部内にない場合、前記複数のアドレス群の中から置き換え対象アドレス群を特定し、かつ、前記多数のアドレス群のうち前記受付アドレスを含む該当アドレス群を、前記アドレス格納部に格納し、その後、前記該当アドレス群に対応する該当ブロックデータを前記記憶装置から読み出し、前記該当ブロックデータを前記データ格納部に格納する制御部と、を含み、前記制御部は、前記置き換え対象アドレス群を特定してから前記該当ブロックデータを前記記憶装置から読み出すまでの読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けた場合には、キャッシュヒットと判定し、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けなかった場合には、前記該当ブロックデータを、前記置き換え対象アドレス群に対応する対応ブロックデータに代えて、前記データ格納部に格納すると共に、前記置き換え対象アドレス群を無効化する。【００２７】
本発明のキャッシュメモリ制御方法は、演算装置および記憶装置と接続されるキャッシュメモリシステムが行うキャッシュメモリ制御方法であって、前記記憶装置のアドレスを所定数ごとにまとめた多数のアドレス群のうち、前記多数のアドレス群よりも数が少ない複数のアドレス群をアドレス格納部に格納し、前記複数のアドレス群のそれぞれに対応する複数のブロックデータをデータ格納部に格納し、前記演算装置からの受付アドレスが前記アドレス格納部内にない場合、前記複数のアドレス群の中から置き換え対象アドレス群を特定し、かつ、前記多数のアドレス群のうち前記受付アドレスを含む該当アドレス群を、前記アドレス格納部に格納し、その後、前記該当アドレス群に対応する該当ブロックデータを前記記憶装置から読み出し、前記該当ブロックデータを前記データ格納部に格納する動作を実行し、前記動作を実行することは、前記置き換え対象アドレス群を特定してから前記該当ブロックデータを前記記憶装置から読み出すまでの読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けた場合には、キャッシュヒットと判定し、前記読み出し期間中に、前記置き換え対象アドレス群内のアドレスを前記演算装置から受け付けなかった場合には、前記該当ブロックデータを、前記置き換え対象アドレス群に対応する対応ブロックデータに代えて、前記データ格納部に格納すると共に、前記置き換え対象アドレス群を無効化することを含む。
【発明の効果】
【００２８】
本発明によれば、キャッシュミスしたデータを含むブロックデータをメモリから読み出してデータ格納手段に格納するまでの間、キャッシュミスによって置き換え対象になったアドレス群およびブロックデータに対して、キャッシュヒットすることが可能になる。それにより、キャッシュヒット率を向上することが可能になる。
【図面の簡単な説明】
【００２９】
【図１】本発明の第１の実施の形態のキャッシュメモリシステムの構成を示す図である。
【図２】キャッシュメモリの状態を表すビット列を示す図である。
【図３】キャッシュメモリの制御アレイのビット列を示す図である。
【図４】キャッシュメモリの動作を説明するフローチャートである。
【図５】キャッシュメモリのブロックの置き換えとブロックの読み出しの動作を説明するフローチャートである。
【図６】キャッシュメモリの置き換え対象の変更とＬＲＵの更新の動作を説明するフローチャートである。
【図７Ａ】キャッシュメモリの動作を説明するための説明図である。
【図７Ｂ】キャッシュメモリの動作を説明するための説明図である。
【図７Ｃ】キャッシュメモリの動作を説明するための説明図である。
【図７Ｄ】キャッシュメモリの動作を説明するための説明図である。
【図７Ｅ】キャッシュメモリの動作を説明するための説明図である。
【図７Ｆ】キャッシュメモリの動作を説明するための説明図である。
【発明を実施するための形態】
【００３０】
以下、本発明の実施形態について図面を参照して詳細に説明する。
【００３１】
図１は、本発明の一実施形態のキャッシュメモリシステムを示したブロック図である。
【００３２】
図１において、キャッシュメモリシステム１は、ＣＰＵ２およびメモリ３と接続される。ＣＰＵ２は、一般的に演算装置と呼ぶことができる。ＣＰＵ２は、単一コアプロセッサ、マルチコアプロセッサ、または、マルチスレッドプロセッサでもよい。メモリ３は、一般的に記憶装置と呼ぶことができる。
【００３３】
キャッシュメモリシステム１は、アドレスレジスタ１０１、アドレスアレイ１０２〜１０４、データアレイ１０５〜１０６、制御アレイ１３２、比較器１０７〜１０９、および、キャッシュ制御ユニット１１０を含む。
【００３４】
アドレスアレイ１０２には、アドレスアレイ番号「０」が付与されている。アドレスアレイ１０３には、アドレスアレイ番号「１」が付与されている。アドレスアレイ１０４には、アドレスアレイ番号「２」が付与されている。
【００３５】
データアレイ１０５には、ウェイ番号「ウェイ０」が付与されている。データアレイ１０６には、ウェイ番号「ウェイ１」が付与されている。
【００３６】
アドレスアレイ１０２〜１０４と制御アレイ１３２は、アドレス格納部１１に含まれる。データアレイ１０５〜１０６は、データ格納部１２に含まれる。比較器１０７〜１０９とキャッシュ制御ユニット１１０は、制御部１３に含まれる。
【００３７】
アドレスレジスタ１０１は、ＣＰＵ２が要求したアドレス（以下「受付アドレス」と称する）を格納する。アドレスレジスタ１０１に格納されるアドレスは、上位ｍビット１２４のデータ（値）、中位ｎビット１２２のデータ（値）、および、下位ｋビット１２９のデータ（値）によって表される。
【００３８】
上位ｍビット１２４のデータは、比較器１０７〜１０９のそれぞれに提供され、中位ｎビット１２２のデータは、アドレスアレイ１０２〜１０４、データアレイ１０５〜１０６、および、制御アレイ１３２に、オフセット１２３として提供される。
【００３９】
アドレス格納部１１は、一般的にアドレス格納手段と呼ぶことができる。アドレス格納部１１は、メモリ３が有するアドレスを所定数ごとにまとめた多数のアドレス群のうち、多数のアドレス群よりも数が少ない複数のアドレス群を格納する。
【００４０】
データ格納部１２は、一般的にデータ格納手段と呼ぶことができる。データ格納部１２は、アドレス格納部１１内の複数のアドレス群のそれぞれに対応する複数のブロックデータを格納する。各ブロックデータは、複数のデータからなる。
【００４１】
制御部１３は、一般的に制御手段と呼ぶことができる。
【００４２】
制御部１３は、キャッシュメモリシステム１がＣＰＵ２から受け付けたアドレス（以下「受付アドレス」と称する）が、アドレス格納部１１内にない場合、つまり、キャッシュミスが発生した場合、アドレス格納部１１内の複数のアドレス群の中から、置き換え対象アドレス群を特定する。
【００４３】
また、制御部１３は、キャッシュミスが発生した場合、多数のアドレス群（具体的には、メモリ３が有するアドレスを所定数ごとにまとめた多数のアドレス群）のうち、受付アドレスを含むアドレス群（以下「該当アドレス群」と称する）を、アドレス格納部１１に格納する。
【００４４】
続いて、制御部１３は、該当アドレス群に対応するブロックデータ（以下「該当ブロックデータ」と称する）を、メモリ３から読み出す。
【００４５】
置き換え対象アドレス群を特定してから該当ブロックデータをメモリ３から読み出すまでの期間中（以下「読み出し期間中」と称する）では、置き換え対象アドレス群が、アドレス格納部１１内に存在し、かつ、置き換え対象アドレス群に対応するブロックデータ（以下「対応ブロックデータ」と称する）が、データ格納部１２内に存在する。
【００４６】
このため、読み出し期間中に、キャッシュメモリシステム１が、置き換え対象アドレス群内のアドレスをＣＰＵ２から受け付けた場合、制御部１３は、キャッシュヒットが発生したと判定する。
【００４７】
読み出し期間中に、キャッシュメモリシステム１が、置き換え対象アドレス群内のアドレスをＣＰＵ２から受け付けなかった場合、制御部１３は、メモリ３から読み出された該当ブロックデータを、対応ブロックデータに代えて、データ格納部１２に格納する。
【００４８】
制御部１３は、該当ブロックデータの格納に伴い、アドレス格納部１１内の置き換え対象アドレス群を無効化する。
【００４９】
また、制御部１３は、読み出し期間中に、キャッシュメモリシステム１が置き換え対象アドレス群内のアドレスをＣＰＵから受け付けた場合、さらに、置き換え対象アドレス群を、アドレス格納部１１内の複数のアドレス群のうちの他のアドレス群（ただし、該当アドレス群とは異なる）に変更する。
【００５０】
続いて、制御部１３は、メモリ３から読み出された該当ブロックデータを、変更後の置き換え対象アドレス群に対応するブロックデータに代えて、データ格納部１２に格納すると共に、アドレス格納部１２内の変更後の置き換え対象アドレス群を無効化する。
【００５１】
本実施形態では、メモリ３が有する複数のアドレスを所定数ごとにまとめた多数のアドレス群のそれぞれは、メモリ３の各アドレスを上位ビット１２４と中位ビット１２２と下位ビット１２９に分けた際に、上位ビット１２４の値および中位ビット１２２の値が共通する複数のアドレスからなるものである。
【００５２】
データ格納部１２は、中位ビット１２２にて表現されうる複数の値のそれぞれを示すインデックス（「オフセット」とも称する）ごとに、そのインデックスに対応するＮ個（Ｎは２以上の整数）のデータ格納領域（以下「データエントリ」と称する）を有する。本実施形態では、Ｎ＝２としている。
【００５３】
本実施形態では、データ格納部１２内のデータアレイ１０５および１０６のそれぞれは、インデックス（オフセット）ごとに、そのインデックスに対応する１個のデータエントリを有する。
【００５４】
データ格納部１２内の複数のブロックデータのそれぞれは、そのブロックデータに対応するアドレス群の中位ビット１２２の値を示すインデックスに対応するデータエントリに個別に格納されている。
【００５５】
アドレス格納部１１は、上述したインデックス（オフセット）ごとに、そのインデックスに対応するＭ（ＭはＮよりも大きい整数）個のアドレス格納領域（以下「アドレスエントリ」と称する）を有する。本実施形態では、Ｍ＝３としている。
【００５６】
本実施形態では、アドレス格納部１１内のアドレスアレイ１０２〜１０４のそれぞれは、インデックス（オフセット）ごとに、そのインデックスに対応する１個のアドレスエントリを有する。
【００５７】
また、アドレス格納部１１は、上述したインデックス（オフセット）ごとに、そのインデックスに対応する制御情報格納領域（以下「制御情報エントリ」と称する）を有する。
【００５８】
本実施形態では、アドレス格納部１１内の制御アレイ１３２は、インデックス（オフセット）ごとに、そのインデックスに対応する１個の制御情報エントリを有する。
【００５９】
アドレス格納部１１内の複数のアドレス群のそれぞれは、そのアドレス群の中位ビット１２２の値を示すインデックスに対応するアドレスエントリに個別に格納されている。
【００６０】
制御部１３は、キャッシュミスが発生した場合、置き換え対象アドレス群を、アドレス格納部１１内の複数のアドレス群のうち受付アドレスと同じ中位ビット１２２を含むアドレス群の中から特定する。
【００６１】
また、制御部１３は、キャッシュミスが発生した場合、該当アドレス群を、受付アドレスの中位ビット１２２の値を示すインデックス（オフセット）に対応する複数のアドレスエントリのうち、未使用または無効化されているアドレスエントリに格納する。
【００６２】
読み出し期間中に、キャッシュメモリシステム１が、置き換え対象アドレス群内のアドレスをＣＰＵ２から受け付けなかった場合、制御部１３は、該当ブロックデータを、対応ブロックデータに代えて、対応ブロックデータを格納しているデータエントリに格納すると共に、置き換え対象アドレス群を無効化する。
【００６３】
一方、読み出し期間中に、キャッシュメモリシステム１が、置き換え対象アドレス群内のアドレスをＣＰＵ２から受け付けた場合、制御部１３は、置き換え対象アドレス群を、アドレス格納部１１内の複数のアドレス群のうち受付アドレスと同じ中位ビット１２２を含むアドレス群の中の他のアドレス群に変更する。
【００６４】
続いて、制御部１３は、メモリ３から読み出された該当ブロックデータを、変更後の置き換え対象アドレス群に対応するブロックデータ（以下「関連ブロックデータ」）に代えて、関連ブロックデータを格納しているデータエントリに格納すると共に、アドレス格納部１１内の変更後の置き換え対象アドレス群を無効化する。
【００６５】
なお、アドレスエントリは、自己に格納されたアドレス群に対応するブロックデータを格納しているデータエントリを示す格納先情報も格納する。制御部１３は、アドレスエントリ内の格納先情報を参照して、対応ブロックデータを格納しているデータエントリを特定する。
【００６６】
アドレスアレイ１０２〜１０４のそれぞれは、２のｎ乗個のアドレスエントリを持つメモリである。なお、データアレイ１０５〜１０６のそれぞれも、２のｎ乗個のデータエントリを持つメモリである。ブロックデータが格納されているデータエントリは、複数のアドレスエントリのいずれかと１対１で対応している。データアレイ１０５〜１０６のそれぞれは、複数のワードからなる複数のデータエントリを有する。
【００６７】
アドレスアレイ１０２〜１０４は、データアレイ１０５〜１０６のデータエントリにブロック単位で格納されているブロックデータの索引として使用される。
【００６８】
アドレスアレイ１０２の各アドレスエントリは、中位ｎビット１２２に対応するオフセット（インデックス）ごとに、アドレスの上位ｍビット１１１と、対応するデータエントリ内のブロックデータの状態を表すビット列（以下「状態情報」とも称する。）１１２と、対応するデータエントリを有するデータアレイのウェイ番号を示すウェイ番号情報１１３と、を含む。
【００６９】
アドレスアレイ１０２は、アドレスの上位ｍビット１１１とオフセットを用いて、アドレス群を格納する。このアドレス群は、上位ｍビットと中位ｎビットのデータが規定され、かつ、下位ｋビットのデータが任意の値となる複数のアドレスを意味する。
【００７０】
アドレスアレイ１０３の各アドレスエントリは、中位ｎビット１２２に対応するオフセット（インデックス）ごとに、アドレスの上位ｍビット１１４と、対応するデータエントリ内のブロックデータの状態を表すビット列（状態情報）１１５と、対応するデータエントリを有するデータアレイのウェイ番号を示すウェイ番号情報１１６と、を含む。
【００７１】
アドレスアレイ１０３は、アドレスの上位ｍビット１１４とオフセットを用いて、アドレス群を格納する。このアドレス群は、上位ｍビットと中位ｎビットのデータが規定され、かつ、下位ｋビットのデータが任意の値となる複数のアドレスを意味する。
【００７２】
アドレスアレイ１０４の各アドレスエントリは、中位ｎビット１２２に対応するオフセット（インデックス）ごとに、アドレスの上位ｍビット１１７と、対応するデータエントリ内のブロックデータの状態を表すビット列（状態情報）１１８と、対応するデータエントリを有するデータアレイのウェイ番号を示すウェイ番号情報１１９と、を含む。
【００７３】
アドレスアレイ１０４は、アドレスの上位ｍビット１１７とオフセットを用いて、アドレス群を格納する。このアドレス群は、上位ｍビットと中位ｎビットのデータが規定され、かつ、下位ｋビットのデータが任意の値となる複数のアドレスを意味する。
【００７４】
なお、ウェイ番号情報１１３、１１６および１１９は、一般的に格納先情報と呼ぶことができる。
【００７５】
図２は、状態情報１１２、１１５および１１８を説明するための説明図である。なお、図２では、状態情報１１２、１１５および１１８を、状態情報２０１として示している。
【００７６】
状態情報２０１は、３ビットで構成される。具体的には、状態情報２０１は、１ビットのＶ２０２と、１ビットのＤ２０３と、１ビットのＦ２０４とからなる。
【００７７】
Ｖ２０２は、Ｖ２０２を含むアドレスエントリが有効かどうかを示す。本実施形態では、Ｖ＝０は、Ｖ２０２を含むアドレスエントリが無効化されていること、さらに言えば、Ｖ２０２を含むアドレスエントリ内のアドレス群が無効化されていることを示し、Ｖ＝１は、Ｖ２０２を含むアドレスエントリが有効であること、さらに言えば、Ｖ２０２を含むアドレスエントリ内のアドレス群が有効であるいることを示す。
【００７８】
Ｄ２０３は、データエントリ内のブロックデータのうち、Ｄ２０３を含むアドレスエントリ内のアドレス群に対応するブロックデータが、書き換えられたかどうかを示す。本実施形態では、Ｄ２０３＝０は、そのブロックデータが、書き換えられていないことを示し、Ｄ２０３＝１は、そのブロックデータが、書き換えられたことを示す。
【００７９】
Ｆ２０４は、Ｆ２０４を含むアドレスエントリ内のアドレス群に対応するブロックデータをメモリ３から読み出し中であるかどうかを示す。本実施形態では、Ｆ２０４＝０は、そのブロックデータを読み出し中でないことを示し、Ｆ２０４＝１は、そのブロックデータを読み出し中であることを示す。
【００８０】
図１に戻って、データアレイ１０５〜１０６内の各データエントリは、２のｋ乗バイトのブロックデータ１２０または１２１を格納する。
【００８１】
制御アレイ１３２は、２のｎ乗個の制御情報エントリを有するメモリである。各制御情報エントリは、ＬＲＵ（Least  Recently  Used）および他の情報を示す制御情報１３３を格納する。
【００８２】
図３は、制御情報１３３を説明するための説明図である。なお、図３では、制御情報１３３を、制御情報３０１として示している。
【００８３】
制御情報３０１は、ＬＲＵ３０２と、Ｒ３０３と、Ｗ０３０４と、Ｗ１３０５とからなる。
【００８４】
ＬＲＵ３０２は、ＬＲＵ３０２が対応するインデックスに対応するアドレスエントリの中で有効なアドレスエントリのうち、最長未使用時間を有するアドレスエントリを有するアドレスアレイの番号を格納する。
【００８５】
Ｒ３０３は、Ｒ３０３が対応するインデックスに対応するアドレスエントリの中で有効なアドレスエントリのうち、置き換え対象アドレス群を格納しているアドレスエントリを有するアドレスアレイの番号を格納する。
【００８６】
なお、Ｒ３０３＝３は、置き換え対象アドレス群を格納しているアドレスエントリがない（無効）を示す。
【００８７】
Ｗ０３０４は、Ｗ０３０４が対応するインデックスに対応するデータエントリのうち、ウェイ番号「ウェイ０」が付与されているデータアレイ１０５内のデータエントリが使用中かどうかを示す。
【００８８】
例えば、Ｗ０３０４＝１は、使用中を示し、Ｗ０３０４＝０は、未使用を示す。
【００８９】
Ｗ１３０５は、Ｗ１３０５が対応するインデックスに対応するデータエントリのうち、ウェイ番号「ウェイ１」が付与されているデータアレイ１０６内のデータエントリが使用中かどうかを示す。
【００９０】
例えば、Ｗ１３０５＝１は、使用中を示し、Ｗ０３０４＝０は、未使用を示す。
【００９１】
図１に戻って、比較器１０７は、アドレスアレイ１０２からの上位ｍビット１１１のデータと、アドレスレジスタ１０１からの上位ｍビット１２４のデータと、を比較する。
【００９２】
なお、比較器１０７に提供される上位ｍビット１１１のデータは、アドレスレジスタ１０１の中位ｎビット１２２をオフセット１２３として用いてアドレスアレイ１０２にアクセスした際に、アドレスアレイ１０２から出力されるデータである。
【００９３】
比較器１０８は、アドレスアレイ１０３からの上位ｍビット１１４のデータと、アドレスレジスタ１０１からの上位ｍビット１２４のデータと、を比較する。
【００９４】
なお、比較器１０８に提供される上位ｍビット１１４のデータは、アドレスレジスタ１０１の中位ｎビット１２２をオフセット１２３として用いてアドレスアレイ１０３にアクセスした際に、アドレスアレイ１０３から出力されるデータである。
【００９５】
比較器１０９は、アドレスアレイ１０４からの上位ｍビット１１７のデータと、アドレスレジスタ１０１からの上位ｍビット１２４のデータと、を比較する。
【００９６】
なお、比較器１０９に提供される上位ｍビット１１７のデータは、アドレスレジスタ１０１の中位ｎビット１２２をオフセット１２３として用いてアドレスアレイ１０４にアクセスした際に、アドレスアレイ１０４から出力されるデータである。
【００９７】
キャッシュ制御ユニット１１０は、比較器１０７からの比較結果１２５、比較器１０８からの比較結果１２６、比較器１０９からの比較結果１２７、ＣＰＵ２からの命令種別情報（例えば、load（読み出し）とstore（書き込み）のいずれか）１２８、アドレスアレイ１０２からの状態情報１１２、アドレスアレイ１０３からの状態情報１１５、アドレスアレイ１０４からの状態情報１１８、アドレスアレイ１０２からのウェイ番号情報１１３、アドレスアレイ１０３からのウェイ番号情報１１６、アドレスアレイ１０４からのウェイ番号情報１１９、制御アレイ１３２からの制御情報１３３に基づいて、キャッシュメモリ（具体的には、アドレス格納部１１とデータ格納部１２）を制御する。
【００９８】
状態情報１１２およびウェイ番号情報１１３は、アドレスアレイ１０１の中位ｎビット１２２をオフセット１２３として用いてアドレスアレイ１０２にアクセスした際に、アドレスアレイ１０２からキャッシュ制御ユニット１１０に出力される。
【００９９】
状態情報１１５およびウェイ番号情報１１６は、アドレスアレイ１０１の中位ｎビット１２２をオフセット１２３として用いてアドレスアレイ１０３にアクセスした際に、アドレスアレイ１０３からキャッシュ制御ユニット１１０に出力される。
【０１００】
状態情報１１８およびウェイ番号情報１１９は、アドレスアレイ１０１の中位ｎビット１２２をオフセット１２３として用いてアドレスアレイ１０４にアクセスした際に、アドレスアレイ１０４からキャッシュ制御ユニット１１０に出力される。
【０１０１】
制御情報１３３は、アドレスアレイ１０１の中位ｎビット１２２をオフセット１２３として用いて制御アレイ１３２にアクセスした際に、制御アレイ１３２からキャッシュ制御ユニット１１０に出力される。
【０１０２】
以下の説明では、アドレスレジスタ１０１に格納されるアドレスは、６４ビットとし、ｋ＝６、すなわちブロックデータのサイズを６４バイトとし、ｎ＝１０、すなわちアドレスアレイ１０２〜１０４のアドレスエントリ数、データアレイ１０５〜１０６のデータエントリ数、および、制御アレイ１３２の制御情報エントリ数を１０２４とし、ｍ＝４８とする。また、６４バイトのブロックデータは、８個のワードからなる。なお、１ワードは８バイトである。
【０１０３】
本実施形態では、２ウェイセットアソシアティブ方式のキャッシュメモリを示しているが、ウェイ数は任意である。
【０１０４】
また、本実施形態では、アドレスアレイの個数を「ウェイ数＋１」としているが、アドレスアレイの数をウェイ数より何個多く持つかも任意である。なお、比較器の個数は、アドレスアレイの個数と同数にする。
【０１０５】
次に、図１に示したキャッシュメモリシステム１の動作を説明する。
【０１０６】
キャッシュメモリシステム１へのアクセスがあった場合に、アドレスレジスタ１０１は、そのアドレスを格納する。なお、このアドレスは、論理アドレスでも物理アドレスでもよい。
【０１０７】
本実施形態では、このアドレスを、何らかのアドレス変換の手段により仮想アドレスから変換された物理アドレスとして説明を行う。
【０１０８】
ブロックデータのサイズは６４バイトなので、アドレスレジスタ１０１の下位６（ｋ）ビット１２９のデータは、データアレイ１０５および１０６内のブロックデータ内のワードのアドレスとなる。
【０１０９】
中位１０（ｎ）ビット１２２のデータが、アドレスアレイ１０２〜１０４のオフセット１２２として使用されて、アドレスアレイ１０２〜１０４のアドレスエントリ内のデータが読み出される。
【０１１０】
比較器１０７は、アドレスアレイ１０２から読み出されたデータのうちの上位４８（ｍ）ビット１１１のデータと、アドレスレジスタ１０１内の上位４８（ｍ）ビット１２４のデータと、を比較して、その比較結果１２５を、キャッシュ制御ユニット１１０に提供する。
【０１１１】
比較器１０８は、アドレスアレイ１０３から読み出されたデータのうちの上位４８（ｍ）ビット１１４のデータと、アドレスレジスタ１０１内の上位４８（ｍ）ビット１２４のデータと、を比較して、その比較結果１２６を、キャッシュ制御ユニット１１０に提供する。
【０１１２】
比較器１０９は、アドレスアレイ１０４から読み出されたデータのうちの上位４８（ｍ）ビット１１７のデータと、アドレスレジスタ１０１内の上位４８（ｍ）ビット１２４のデータと、を比較して、その比較結果１２７を、キャッシュ制御ユニット１１０に提供する。
【０１１３】
キャッシュ制御ユニット１１０は、比較結果１２５〜１２７と共に、命令種別情報（本実施形態では、loadまたはstore）１２８、状態情報１１２、１１５および１１８、ウェイ番号情報１１３、１１６および１１９、並びに、制御情報１３３を受け付け、これらの情報に基づいて、キャッシュメモリシステム１の動作を決定する。なお、命令種別情報１２８は、ＣＰＵ２から提供される。
【０１１４】
図４は、キャッシュ制御ユニット１１０の動作を説明するためのフローチャートである。
【０１１５】
アドレスレジスタ１０１が、キャッシュメモリシステム１にアクセスされたアドレスを格納すると、その後、そのアドレスの中位１０（ｎ）ビット１２２のデータが、アドレスアレイ１０２〜１０４、データアレイ１０５〜１０６、および、制御アレイ１３２のオフセット１２３として使用されて、アドレスアレイ１０２〜１０４のアドレスエントリ、データアレイ１０５〜１０６のデータエントリ、および、制御アレイ１３２の制御情報エントリが、アクセスされる。
【０１１６】
このとき、キャッシュ制御ユニット１１０は、ＣＰＵ２から、下位６（ｋ）ビット１２９のデータも受け付ける。また、キャッシュ制御ユニット１１０は、アクセスが書き込み（store）用である場合、ＣＰＵ２から、ストア命令に示された書き込み用データも受け付ける。
【０１１７】
キャッシュ制御ユニット１１０は、命令種別情報１２８が、ストア（store）命令かロード（load）命令かを判断する（ステップ４０１）。
【０１１８】
まず、命令種別情報１２８がストア（store）命令の場合（ステップ４０２）、キャッシュ制御ユニット１１０は、ステップ４０３を実行する。
【０１１９】
ステップ４０３では、キャッシュ制御ユニット１１０は、比較結果１２５〜１２７と、状態情報１１２、１１５および１１８と、に基づいて、アクセスされたデータがデータ格納部１２内にあるか、つまり、キャッシュヒットしたかどうかを判断する。
【０１２０】
比較結果１２５が一致を示すと共に状態情報１１２内のＶ２０２が１を示す場合、比較結果１２６が一致を示すと共に状態情報１１５のＶ２０２が１を示す場合、または、比較結果１２７が一致を示すと共に状態情報１１８のＶ２０２が１を示す場合には、キャッシュ制御ユニット１１０は、キャッシュヒットしたと判断する（ステップ４０４）。
【０１２１】
一方、以下の条件１〜３のすべてが満たされる場合には、キャッシュ制御ユニット１１０は、キャッシュミスしたと判断する（ステップ４０５）。
【０１２２】
条件１：比較結果１２５が一致を示していない、または、状態情報１１２内のＶ２０２が０を示す。
【０１２３】
条件２：比較結果１２６が一致を示していない、または、状態情報１１５内のＶ２０２が０を示す。
【０１２４】
条件３：比較結果１２７が一致を示していない、または、状態情報１１８内のＶ２０２が０を示す。
【０１２５】
キャッシュヒットと判断した場合は（ステップ４０４）、キャッシュ制御ユニット１１０は、制御情報１３３内のＲ３０３が示す値が、キャッシュヒットしたアドレスアレイ番号と一致するかどうかで、キャッシュヒットしたアドレスが、置き換え対象アドレス群内のアドレスであるかどうかを判断する（ステップ４０６）。
【０１２６】
キャッシュヒットしたアドレスが、置き換え対象アドレス群内のアドレスでない場合（ステップ４０７）、キャッシュ制御ユニット１１０は、まず、受け付けられた制御情報１３３内のＬＲＵ３０２を更新し、制御アレイ１３２内の更新前の制御情報１３３を、更新後の制御情報１３３に書き換える（ステップ４０８）。もし、更新前のＬＲＵ３０２が示しているアドレスアレイ番号が、キャッシュヒットしたアドレスを格納しているアドレスアレイの番号であるなら、キャッシュ制御ユニット１１０は、他のアドレスアレイ番号をＬＲＵ３０２に設定してＬＲＵ３０２を更新する。
【０１２７】
次に、キャッシュ制御ユニット１１０は、キャッシュヒットしたアドレスを含むアドレス群（以下「キャッシュヒットアドレス群」と称する）に対応するブロックデータが、メモリ３から読み出し中かどうかを、キャッシュヒットアドレス群を格納しているアドレスアレイからの状態情報２０１内のＦ２０４が示す値に基づいて判断する（ステップ４０９）。
【０１２８】
もし、Ｆ２０４が１を示す場合、つまり、キャッシュヒットアドレス群に対応するブロックデータがメモリ３から読み出し中である場合（ステップ４１０）、キャッシュ制御ユニット１１０は、読み出しが終了するまで待つ。
【０１２９】
一方、Ｆ２０４が０を示す場合、つまり、キャッシュヒットアドレス群に対応するブロックデータがメモリ３から読み出し中でない場合（ステップ４１１）、キャッシュ制御ユニット１１０は、キャッシュヒットアドレス群を格納しているアドレスアレイからのウェイ番号情報に基づいて、キャッシュヒットアドレス群に対応するブロックデータを格納しているデータエントリを特定する。
【０１３０】
続いて、キャッシュ制御ユニット１１０は、その特定されたデータエントリ内の、キャッシュヒットアドレス群に対応するブロックデータの中から、アドレスレジスタ１０１内の下位６（ｋ）ビット１２９のデータに基づいて、アクセスされたワードを特定し、そのワードに対して、書き込みデータを書き込む（ステップ４１２）。
【０１３１】
続いて、キャッシュ制御ユニット１１０は、キャッシュヒットアドレス群を格納しているアドレスエントリに含まれる状態情報２０１内のＤ２０３が示す値を１に設定する（ステップ４１３）。
【０１３２】
また、置き換え対象アドレス群に含まれるアドレスが、キャッシュヒットした場合（ステップ４１４）、つまり、置き換え対象アドレス群がキャッシュヒットアドレス群となった場合、キャッシュ制御ユニット１１０は、置き換え対象アドレス群の変更とＬＲＵの更新を行う（ステップ４１５）。なお、ステップ４１５については、後に、図６を使って詳細に説明する。
【０１３３】
そして、キャッシュ制御ユニット１１０は、キャッシュヒットアドレス群を格納しているアドレスアレイからのウェイ番号情報に基づいて、キャッシュヒットアドレス群に対応するブロックデータを格納しているデータエントリを特定する。
【０１３４】
続いて、キャッシュ制御ユニット１１０は、その特定されたデータエントリ内の、キャッシュヒットアドレス群に対応するブロックデータの中から、アドレスレジスタ１０１内の下位６（ｋ）ビット１２９のデータに基づいて、アクセスされたワードを特定し、そのワードに対して、書き込みデータを書き込む（ステップ４１６）。
【０１３５】
続いて、キャッシュ制御ユニット１１０は、キャッシュヒットアドレス群を格納しているアドレスエントリに含まれる状態情報２０１内のＤ２０３が示す値を１にする（ステップ４１７）。
【０１３６】
キャッシュミスと判断した場合は（ステップ４０５）、キャッシュ制御ユニット１１０は、制御情報１３３内のＷ０３０４およびＷＯ３０５を参照して、ブロック（つまり、ブロックデータと、そのブロックデータに対応するアドレス群）の置き換えが発生するかを判断する（ステップ４１８）。
【０１３７】
ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたデータエントリのすべてが、使用中である場合、つまり、Ｗ０３０４とＷ１３０５の両方が１を示す場合、キャッシュ制御ユニット１１０は、置き換えが発生すると判断する（ステップ４１９）。
【０１３８】
キャッシュ制御ユニット１１０は、置き換えが発生すると判断すると、ステップ４２２で、置き換え対象アドレス群を格納しているアドレスエントリを特定し、また、キャッシュミスしたアドレスを含むアドレス群（該当アドレス群）に対応するブロックデータ（該当ブロックデータ）を、メモリ３から読み出し、そのブロックデータ（該当ブロックデータ）をデータ格納部１２に書き込む。ステップ４２２については、後に、図５を使って詳細に説明する。
【０１３９】
一方、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたデータエントリのうち、空いているデータエントリが１つ以上ある場合、つまり、Ｗ０３０４とＷ１３０５のうち少なくともいずれか一方が０を示す場合、キャッシュ制御ユニット１１０は、置き換えが発生しないと判断する（ステップ４２０）。
【０１４０】
置き換えが発生しない場合は（ステップ４２０）、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたアドレスエントリの中に、無効または未使用なアドレスエントリ（以下「無効状態アドレスエントリ」と称する）が存在し、かつ、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたデータエントリの中に、無効または未使用なデータエントリ（以下「無効状態データエントリ」と称する）が存在することになる。
【０１４１】
キャッシュ制御ユニット１１０は、無効状態アドレスエントリ内の上位４８（ｍ）ビットに、キャッシュミスしたアドレスレジスタの上位４８（ｍ）ビット１２４を設定して、該当アドレス群を無効状態アドレスエントリに格納する。
【０１４２】
さらに、キャッシュ制御ユニット１１０は、無効状態アドレスエントリ内の状態情報内のＶ２０２に１を設定し、無効状態アドレスエントリ内の状態情報内のＤ２０３に０を設定し、無効状態アドレスエントリ内の状態情報内のＦ２０４に１を設定し、無効状態アドレスエントリ内のウェイ番号情報に、無効状態データエントリを有するデータアレイのウェイ番号を設定し、無効状態データエントリを使用中にする（具体的には、Ｗ０３０４またはＷ１３０５に１を設定）にする。
【０１４３】
続いて、キャッシュ制御ユニット１１０は、ＣＰＵ２からのアドレスを含むアドレス群（該当アドレス群）に対応するブロックデータ（該当ブロックデータ）を、メモリ３から読み出す。
【０１４４】
続いて、キャッシュメモリ制御ユニット１１０は、メモリ３から読み出されたブロックデータ（該当ブロックデータ）を、無効状態アドレスエントリ内のウェイ番号情報が示す、使用中に変更されたデータエントリに書き込む（ステップ４２１）。
【０１４５】
そして、キャッシュメモリ制御ユニット１１０は、使用中に変更されたデータエントリ内のワードのうち、ＣＰＵ２からのアドレスの下位６（ｋ）ビット１２９のデータで特定されるワードに対して、書き込みデータを書き込み（ステップ４１２）、そして、無効状態アドレスエントリ内の状態情報２０１内のＤ２０３に１を設定する（ステップ４１３）。
【０１４６】
一方、命令種別情報１２８がロード（load）命令の場合（ステップ４２３）、キャッシュ制御ユニット１１０は、ステップ４２４を実行する。
【０１４７】
ステップ４２４では、キャッシュ制御ユニット１１０は、比較結果１２５〜１２７と、状態情報１１２、１１５および１１８と、に基づいて、アクセスされたデータがデータ格納部１２内にあるか、つまり、キャッシュヒットしたかどうかを判断する。
【０１４８】
比較結果１２５が一致を示すと共に状態情報１１２内のＶ２０２が１を示す場合、比較結果１２６が一致を示すと共に状態情報１１５のＶ２０２が１を示す場合、または、比較結果１２７が一致を示すと共に状態情報１１８のＶ２０２が１を示す場合には、キャッシュ制御ユニット１１０は、キャッシュヒットしたと判断する（ステップ４２５）。
【０１４９】
一方、上述した条件１〜３のすべてが満たされる場合には、キャッシュ制御ユニット１１０は、キャッシュミスしたと判断する（ステップ４２６）。
【０１５０】
キャッシュヒットと判断した場合は（ステップ４２５）、キャッシュ制御ユニット１１０は、制御情報１３３内のＲ３０３が示す値が、キャッシュヒットしたアドレスアレイ番号と一致するかどうかで、キャッシュヒットしたアドレスが、置き換え対象アドレス群内のアドレスであるどうかを判断する（ステップ４２７）。
【０１５１】
キャッシュヒットしたアドレスが、置き換え対象アドレス群内のアドレスでない場合（ステップ４２８）、キャッシュ制御ユニット１１０は、まず、受け付けられた制御情報１３３内のＬＲＵ３０２を更新し、制御アレイ１３２内の更新前の制御情報１３３を、更新後の制御情報１３３に書き換える（ステップ４２９）。もし、更新前のＬＲＵ３０２が示しているアドレスアレイ番号が、キャッシュヒットしたアドレスを格納しているアドレスアレイの番号であるなら、キャッシュ制御ユニット１１０は、他のアドレスアレイ番号をＬＲＵ３０２に設定してＬＲＵ３０２を更新する。
【０１５２】
次に、キャッシュ制御ユニット１１０は、キャッシュヒットしたアドレスを含むアドレス群（キャッシュヒットアドレス群）に対応するブロックデータが、メモリ３から読み出し中かどうかを、キャッシュヒットアドレス群を格納しているアドレスアレイからの状態情報２０１内のＦ２０４が示す値に基づいて判断する（ステップ４３０）。
【０１５３】
もし、Ｆ２０４が１を示す場合、つまり、キャッシュヒットアドレス群に対応するブロックデータがメモリ３から読み出し中である場合（ステップ４３１）、キャッシュ制御ユニット１１０は、読み出しが終了するまで待つ。
【０１５４】
一方、Ｆ２０４が０を示す場合、つまり、キャッシュヒットアドレス群に対応するブロックデータがメモリ３から読み出し中でない場合（ステップ４３２）、キャッシュ制御ユニット１１０は、キャッシュヒットアドレス群を格納しているアドレスアレイからのウェイ番号情報に基づいて、キャッシュヒットアドレス群に対応するブロックデータを格納しているデータエントリを特定する。
【０１５５】
続いて、キャッシュ制御ユニット１１０は、その特定されたデータエントリ内の、キャッシュヒットアドレス群に対応するブロックデータの中から、アドレスレジスタ１０１内の下位６（ｋ）ビット１２９のデータに基づいて、アクセスされたワードを特定し、そのワード内のデータを読み出す（ステップ４３３）。キャッシュ制御ユニット１１０は、そのデータをＣＰＵ２に提供する。
【０１５６】
また、置き換え対象アドレス群に含まれるアドレスが、キャッシュヒットした場合（ステップ４３４）、つまり、置き換え対象アドレス群がキャッシュヒットアドレス群となった場合、キャッシュ制御ユニット１１０は、置き換え対象アドレス群の変更とＬＲＵの更新を行う（ステップ４３５）。なお、ステップ４３５については、後に、図６を使って詳細に説明する。
【０１５７】
そして、キャッシュ制御ユニット１１０は、キャッシュヒットアドレス群を格納しているアドレスアレイからのウェイ番号情報に基づいて、キャッシュヒットアドレス群に対応するブロックデータを格納しているデータエントリを特定する。
【０１５８】
続いて、キャッシュ制御ユニット１１０は、その特定されたデータエントリ内の、キャッシュヒットアドレス群に対応するブロックデータの中から、アドレスレジスタ１０１内の下位６（ｋ）ビット１２９のデータに基づいて、アクセスされたワードを特定し、そのワード内のデータを読み出す（ステップ４３６）。キャッシュ制御ユニット１１０は、そのデータをＣＰＵ２に提供する。
【０１５９】
キャッシュミスと判断した場合は（ステップ４２６）、キャッシュ制御ユニット１１０は、制御情報１３３内のＷ０３０４およびＷＯ３０５を参照して、ブロック（ブロックデータと、そのブロックデータに対応するアドレス群）の置き換えが発生するかを判断する（ステップ４３７）。
【０１６０】
ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたデータエントリのすべてが、使用中である場合、つまり、Ｗ０３０４とＷ１３０５の両方が１を示す場合、キャッシュ制御ユニット１１０は、置き換えが発生すると判断する（ステップ４３８）。
【０１６１】
キャッシュ制御ユニット１１０は、置き換えが発生すると判断すると、ステップ４３９で、置き換え対象アドレス群を格納しているアドレスエントリを特定し、また、キャッシュミスしたアドレスを含むアドレス群（該当アドレス群）に対応するブロックデータ（該当ブロックデータ）を、メモリ３から読み出し、そのブロックデータ（該当ブロックデータ）をデータ格納部１２に書き込む。ステップ４３９については、後に、図５を使って詳細に説明する。
【０１６２】
一方、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたデータエントリのうち、空いているデータエントリが１つ以上ある場合、つまり、Ｗ０３０４とＷ１３０５のうち少なくともいずれか一方が０を示す場合、キャッシュ制御ユニット１１０は、置き換えが発生しないと判断する（ステップ４４０）。
【０１６３】
置き換えが発生しない場合は（ステップ４４０）、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたアドレスエントリの中に、無効または未使用なアドレスエントリ（無効状態アドレスエントリ）が存在し、かつ、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたデータエントリの中に、無効または未使用なデータエントリ（無効状態データエントリ）が存在することになる。
【０１６４】
キャッシュ制御ユニット１１０は、無効状態アドレスエントリ内の上位４８（ｍ）ビットに、キャッシュミスしたアドレスレジスタの上位４８（ｍ）ビット１２４を設定して、該当アドレス群を無効状態アドレスエントリに格納する。
【０１６５】
さらに、キャッシュ制御ユニット１１０は、無効状態アドレスエントリ内の状態情報内のＶ２０２に１を設定し、無効状態アドレスエントリ内の状態情報内のＤ２０３に０を設定し、無効状態アドレスエントリ内の状態情報内のＦ２０４に１を設定し、無効状態アドレスエントリ内のウェイ番号情報に、無効状態データエントリを有するデータアレイのウェイ番号を設定し、無効状態データエントリを使用中にする（具体的には、Ｗ０３０４またはＷ１３０５に１を設定）にする。
【０１６６】
続いて、キャッシュ制御ユニット１１０は、ＣＰＵ２からのアドレスを含むアドレス群（該当アドレス群）に対応するブロックデータ（該当ブロックデータ）を、メモリ３から読み出す。
【０１６７】
続いて、キャッシュメモリ制御ユニット１１０は、メモリ３から読み出されたブロックデータ（該当ブロックデータ）を、無効状態アドレスエントリ内のウェイ番号情報が示す、使用中に変更されたデータエントリに書き込む（ステップ４４１）。
【０１６８】
そして、キャッシュメモリ制御ユニット１１０は、使用中に変更されたデータエントリ内のワードのうち、ＣＰＵ２からのアドレスの下位６（ｋ）ビット１２９のデータで特定されるワードからデータを読み出す（ステップ４３３）。キャッシュメモリ制御ユニット１１０は、そのデータを、ＣＰＵ２に提供する。
【０１６９】
次に、図５を参照して、図４に示したステップ４２２および４３９について説明する。
【０１７０】
まず、キャッシュ制御ユニット１１０は、制御情報１３３内のＬＲＵ３０２に従い、置き換え対象のアドレスアレイ（さらに言えば、置き換え対象アドレス群を格納している置き換え対象アドレスエントリ）を選択する（ステップ５０１）。
【０１７１】
次に、キャッシュ制御ユニット１１０は、制御情報１３３内のＬＲＵ３０２が示す値を更新する。具体的には、キャッシュ制御ユニット１１０は、アドレスアレイ１０２〜１０４のうち、最後にアクセスされた時刻が２番目に古いアドレスアレイが有する番号を、ＬＲＵ３０２に設定する（ステップ５２３）。
【０１７２】
続いて、キャッシュ制御ユニット１１０は、状態情報１１２、１１５および１１８内の各Ｖ２０２を参照して、空きのアドレスアレイ（具体的には、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたアドレスエントリのうちの無効状態アドレスエントリ）があるかどうかを判断する（ステップ５０２）。
【０１７３】
複数のＶ２０２のすべてが１を示す場合、空きのアドレスアレイ（無効状態アドレスエントリ）はなく、複数のＶ２０２のうちのひとつでも０を示す場合、空きのアドレスアレイ（無効状態アドレスエントリ）が存在する。
【０１７４】
空のアドレスアレイがない場合は（ステップ５０３）、キャッシュ制御ユニット１１０は、置き換え対象アドレスエントリ内の状態情報２０１内のＤ２０３が１を示すか０を示すかによって、置き換え対象アドレス群に対応するブロックデータ（対応ブロックデータ）が、書き換えられていたかどうかを判断する（ステップ５０４）。
【０１７５】
置き換え対象アドレス群に対応するブロックデータ（対応ブロックデータ）が、書き換えられていた場合（ステップ５０５）、キャッシュ制御ユニット１１０は、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたデータエントリのうち、置き換え対象アドレスエントリ内のウェイ番号情報で示されたウェイ内のデータエントリ（以下「置き換え対象データエントリ」と称する）を特定し、置き換え対象データエントリ内のブロックデータを、メモリ３にライトバックする（ステップ５０６）。
【０１７６】
一方、置き換え対象アドレス群に対応するブロックデータ（対応データブロック）が、書き換えられていない場合（ステップ５０７）、キャッシュ制御ユニット１１０は、ライトバックを行わない。
【０１７７】
次に、キャッシュ制御ユニット１１０は、アドレスレジスタ１０１の上位４８（ｍ）ビット１２４のデータを、置き換え対象アドレスエントリ内の上位４８（ｍ）ビットに書き込む。また、キャッシュ制御ユニット１１０は、置き換え対象アドレスエントリ内の状態情報２０１内のＶ２０２とＦ２０４に１を設定し、置き換え対象アドレスエントリ内の状態情報２０１内のＤ２０３に０を設定する（ステップ５０８）。
【０１７８】
続いて、キャッシュ制御ユニット１１０は、メモリ３に対して、キャッシュミスしたブロックデータの読み出しリクエストを発行し、メモリ３からのブロックデータ（該当ブロックデータ）を、置き換え対象データエントリに書き込む（ステップ５０９）。
【０１７９】
空のアドレスアレイがある場合（ステップ５１０）は、キャッシュ制御ユニット１１０は、置き換え対象アドレスエントリ内の状態情報２０１内のＤ２０３が１を示すか０を示すかによって、置き換え対象アドレス群に対応するブロックデータ（対応ブロックデータ）が、書き換えられていたかどうかを判断する（ステップ５１１）。
【０１８０】
置き換え対象アドレス群に対応するブロックデータ（対応ブロックデータ）が、書き換えられていた場合（ステップ５１２）、キャッシュ制御ユニット１１０は、ＣＰＵ２からのアドレスの中位１０（ｎ）ビット１２２に応じてアクセスされたデータエントリのうち、置き換え対象アドレスエントリ内のウェイ番号情報で示されたウェイ内のアドレスアレイ内のデータエントリ（置き換え対象データエントリ）を特定し、置き換え対象データエントリ内のブロックデータを、メモリ３にライトバックし、置き換え対象アドレスエントリ内の状態情報２０１内のＤ２０３に０を設定する（ステップ５１３）。
【０１８１】
一方、置き換え対象アドレス群に対応するブロックデータが、書き換えられていない場合（ステップ５１４）、キャッシュ制御ユニット１１０は、ライトバックを行わない。
【０１８２】
次に、キャッシュ制御ユニット１１０は、アドレスレジスタ１０１の上位４８（ｍ）ビット１２４のデータを、空きアドレスエントリ（無効状態アドレスエントリ）内の上位４８（ｍ）ビットに書き込む。このため、該当アドレス群が、未使用または無効化されているアドレスエントリに格納される。
【０１８３】
また、キャッシュ制御ユニット１１０は、キャッシュ制御ユニット１１０は、無効状態アドレスエントリ内の状態情報２０１内のＶ２０２とＦ２０４に１を設定し、無効状態アドレスエントリ内の状態情報２０１内のＤ２０３に０を設定する（ステップ５１５）。
【０１８４】
次に、キャッシュ制御ユニット１１０は、制御情報１３３内のＲ３０３の値を、置き換え対象アドレスエントリを有するアドレスアレイの番号に更新し、制御アレイ１３２内の更新前の制御情報１３３を、更新後の制御情報１３３に書き換える（ステップ５１６）。
【０１８５】
次に、キャッシュ制御ユニット１１０は、メモリ３に対して、キャッシュミスしたブロックデータの読み出しリクエストを発行する（ステップ５１７）。
【０１８６】
次に、キャッシュ制御ユニット１１０は、メモリ３からのブロックデータ（該当ブロックデータ）を待つ（ステップ５１８）。
【０１８７】
本実施形態では、ブロックデータが到着するまでの間、従来なら無効となっている置き換え対象のアドレス群がアドレスアレイ上で有効となる。
【０１８８】
メモリ３からのブロックデータ（該当ブロックデータ）が到着すると（ステップ５１９）、キャッシュ制御ユニット１１０は、まず、制御情報１３３内のＲ３０３を参照して、置き換え対象アドレスエントリを特定し、置き換え対象アドレスエントリ内の状態情報２０１内のＶ２０２に０を設定して、置き換え対象アドレスエントリ内の置き換え対象アドレス群を無効化する（ステップ５２０）。
【０１８９】
続いて、キャッシュ制御ユニット１１０は、置き換え対象アドレスエントリ内のウェイ番号情報を参照して、置き換え対象データエントリを特定し、置き換え対象データエントリに、対応ブロックデータの代わりに、メモリ３から読み出したブロックデータ（該当ブロックデータ）を書き込む（ステップ５２１）。
【０１９０】
次に、キャッシュ制御ユニット１１０は、状態情報２０１内のＦ２０４が１を示している置き換え対象アドレスエントリ内のウェイ番号情報に、ブロックデータが書き込まれたアドレスアレイのウェイ番号を書き込む。
【０１９１】
続いて、キャッシュ制御ユニット１１０は、置き換え対象アドレスエントリ内のＦ２０４に０を設定する（ステップ５２２）。
【０１９２】
最後に、キャッシュ制御ユニット１１０は、制御情報１３３内のＲ３０３に３を書き込み、置き換え対象アドレスエントリを指定する設定を、無効にする（ステップ５２３）。
【０１９３】
次に、図６を参照して、図４に示したステップ４１５および４３５について説明する。
【０１９４】
まず、キャッシュ制御ユニット１１０は、制御情報１３３内のＬＲＵ３０２に、制御情報１３３内のＲ３０３に示された値（置き換え対象アドレスエントリを含むアドレスアレイの番号）を設定する（ステップ６０１）。
【０１９５】
続いて、キャッシュ制御ユニット１１０は、アドレスアレイ１０２〜１０４のうち、最後にアクセスされた時刻が２番目に古いアドレスアレイが有する番号を、ＬＲＵ３０２に設定する（ステップ６０２）。
【０１９６】
図７Ａ〜図７Ｇは、キャッシュメモリシステム１の動作例、具体的には、キャッシュ制御ユニット１１０の動作例を説明するための説明図である。なお、図７Ａ〜図７Ｇにおいて、図１に示したものと同一構成のものには同一符号を付してある。
【０１９７】
ここでは、アドレスアレイを３個もち、データアレイを２ウェイもつキャッシュメモリシステム１を使って説明する。
【０１９８】
まず、図７Ａは、ロード（load）命令が発行された直後の状態を示している。
【０１９９】
アドレスレジスタ１０１の中位ｎビット１２２に、２進数である“000101011”が格納されている。
【０２００】
“000101011”をインデックスとして、制御アレイ１３２内の制御情報エントリと、アドレスアレイ１０２〜１０４内の各アドレスエントリと、図示していないが２ウェイのデータアレイの各データエントリとが、アクセスされる。
【０２０１】
以下では、アドレスアレイ１０２内のアドレスエントリのうち、アドレスエントリ７０１がアクセスされ、アドレスアレイ１０３内のアドレスエントリのうち、アドレスエントリ７０２がアクセスされ、アドレスアレイ１０４内のアドレスエントリのうち、アドレスエントリ７０３がアクセスされ、制御アレイ１３２内の制御情報アレイのうち、制御情報アレイ７０４がアクセスされたとする。
【０２０２】
まず、アドレスエントリ７０１では、状態情報７０７が１１０を示している。このため、アドレスエントリ７０１は有効であり、また、アドレスエントリ７０１内のアドレス群に対応するブロックデータは、ＣＰＵ２によって書き換えられていることになる。上位ｍビット７０８には、１６進数である“0x000001cc0002”が格納されている。そして、ウェイ番号情報７０９は、１を示している。
【０２０３】
次に、アドレスエントリ７０２では、状態情報７１０が１００を示している。このため、アドレスエントリ７０２は有効であり、また、アドレスエントリ７０２内のアドレス群に対応するブロックデータは、ＣＰＵ２によって書き換えられていないことになる。上位ｍビット７１１には、16進数である“0x000001cc0001”が格納されている。そして、ウェイ番号情報７１２は、０を示している。
【０２０４】
最後に、アドレスエントリ７０３では、状態情報７１３が０００を示している。このため、アドレスエントリ７０３は無効である。
【０２０５】
制御情報エントリ７０４では、ＬＲＵ７１４が０（アドレスアレイ１０２の番号）を示している。つまり、“000101011”をインデックスとして用いた際にキャッシュミスした場合に、置き換えの対象になるのは、アドレスアレイ１０２（さらに言えば、アドレスエントリ７０１）である。Ｒ７１５は無効を示している。また、Ｗ０７１６およびＷ１７１７はともに１になっている。
【０２０６】
アドレスレジスタ１０１の上位ｍビット１２４には、16進数である“0x000001cc0003”が格納されている。
【０２０７】
“0x000001cc0003”は、アドレスエントリ７０１の上位ｍビット７０８内のデータとも、アドレスエントリ７０２の上位ｍビット７１１内のデータとも異なる。このため、アドレスレジスタ１０１内のアドレスは、キャッシュミスとなる。
【０２０８】
また、データアレイは２ウェイとも使用中なので、置き換えが発生する。そして、ＬＲＵ７１４には０が格納されているので、置き換え対象は、アドレスエントリ７０１内のアドレス群となる。
【０２０９】
次に、図７Ｂと図７Ｃを用いて、置き換えを説明する。
【０２１０】
図７Ｂでは、まず、キャッシュ制御ユニット１１０は、ＬＲＵ７１４を更新して１に設定する。次に、置き換えられるアドレスエントリ７０１に格納されているアドレス群に対応するブロックデータが、ＣＰＵ２によって書き換えられているので、キャッシュ制御ユニット１１０は、“000101011”をインデックスとしてアクセスされたデータエントリのうち、アドレスエントリ７０１のウェイ番号情報７０９で示されたウェイ０のデータアレイ内のデータエントリに格納されているブロックデータを、メモリ３にライトバックする。そして、キャッシュ制御ユニット１１０は、アドレスエントリ７０１内の状態情報７０７を、１１０から１００に変更する。
【０２１１】
次に、図７Ｃでは、キャッシュ制御ユニット１１０は、空いていたアドレスエントリ７０３内に、キャッシュミスしたアドレスの上位ｍビットのデータ１２４を設定し、アドレスエントリ７０３内の状態情報７１３を１０１に設定する。つまり、未使用のアドレスエントリに、該当アドレス群が格納される。
【０２１２】
続いて、キャッシュ制御ユニット１１０は、置き換え対象になったアドレスアレイ１０２に付与されている番号０を、制御アレイ１３２内のＲ７１５に設定する。そして、キャッシュ制御ユニット１１０は、メモリ３に対して、キャッシュミスしたアドレスを含むアドレス群に対応するブロックデータ（該当ブロックデータ）の読み出しを要求する。
【０２１３】
図７Ｄは、キャッシュミスしたアドレスを含むアドレス群に対応するブロックデータがキャッシュメモリシステム１に到着する前に、置き換え対象のアドレスエントリ７０１に格納されているアドレス群内のアドレスがキャッシュヒットした場合を示している。
【０２１４】
アドレスレジスタ１０１の上位ｍビット１２４に格納されている１６進数である“0x000001cc0002”は、アドレスエントリ７０１内の上位ｍビット７０８に格納されている値と同じなので、キャッシュヒットとなる。
【０２１５】
この場合、キャッシュ制御ユニット１１０は、制御情報エントリ７０４内のＲ７１５に示されたアドレスアレイ番号を、０からＬＲＵ７１４の値である１に変更する。このため、置き換え対象のアドレスエントリが、アドレスエントリ７０１からアドレスエントリ７０２に変更される。そして、キャッシュ制御ユニット１１０は、ＬＲＵ７１４が示す値を１から２に更新する。
【０２１６】
図７Ｅと図７Ｆは、メモリ３から、キャッシュミスしたアドレスを含むアドレス群に対応するブロックデータが返ってきた時点の処理を示している。
【０２１７】
図７Ｅでは、まず、キャッシュ制御ユニット１１０は、制御情報エントリ７０４内のＲ７１５で示された置き換え対象のアドレスアレイ内のアドレスエントリ７０２内のアドレス群（変更後の置き換え対象アドレス群）を無効化する。
【０２１８】
キャッシュ制御ユニット１１０は、アドレスエントリ７０２内の状態情報７１０が示す値を、１００から０００に変更する。そして、キャッシュ制御ユニット１１０は、“000101011”をインデックスとしてアクセスされたデータエントリのうち、アドレスエントリ７０２内のウェイ番号情報７１２で示されたウェイ０のデータアレイ内のデータエントリに、変更後の置き換え対象アドレス群に対応する関連ブロックデータの代わりに、ＣＰＵ３から読み出されたブロックデータ（該当ブロックデータ）を書き込む。
【０２１９】
図７Ｆでは、キャッシュ制御ユニット１１０は、アドレスエントリ７０３内の状態情報７１３が示す値を、１０１から１００に変更する。そして、キャッシュ制御ユニット１１０は、ブロックデータが書き込まれたデータアレイのウェイ番号０を、アドレスエントリ７０３内のウェイ番号情報７１９に設定する。そして、キャッシュ制御ユニット１１０は、制御情報エントリ７０４内のＲ７１５が示す値を３に設定し、置き換え対象を無効にする。
【０２２０】
次に、本実施形態の効果を説明する。
【０２２１】
本実施形態によれば、制御部１３は、読み出し期間中に、置き換え対象アドレス群内のアドレスをＣＰＵ２から受け付けた場合には、キャッシュヒットと判定する。このため、キャッシュヒット率を向上することが可能になる。
【０２２２】
なお、本実施形態のキャッシュメモリシステム１において、アドレスレジスタ１０１が省略されても、上記と同様の作用効果を生じる。
【０２２３】
また、読み出し期間中、置き換え対象アドレス群を格納しておけるアドレスエントリの数を多くすれば、ほぼ同時に多数のキャッシュミスが発生しても、置き換え対象アドレス群を格納しておくことが可能になり、キャッシュヒット率の低下を防止することが可能になる。
【０２２４】
また、本実施形態では、セットアソシアティブ方式で、キャッシュヒットしたか否かを判定できるため、キャッシュヒットを判定する際に行う検索の速度が低下することを防止可能となる。
【０２２５】
また、本実施形態では、制御部１３は、読み出し期間中に、置き換え対象アドレス群内のアドレスをＣＰＵ２から受け付けた場合には、さらに、置き換え対象アドレス群を、複数のアドレス群のうちの他のアドレス群に変更し、受付アドレスを含むアドレス群に対応する該当ブロックデータを、変更後の置き換え対象アドレス群に対応するブロックデータに代えて、データ格納部１２に格納すると共に、アドレス格納部１１内の変更後の置き換え対象アドレス群を無効化する。
【０２２６】
この場合、置き換え対象アドレス群の選択ミスを防止可能になり、キャッシュヒット率を向上することが可能になる。
【０２２７】
また、本実施形態では、各アドレスエントリは、自己に格納されたアドレス群に対応するブロックデータを格納しているデータエントリを示す格納先情報も格納する。制御部１３は、格納先情報を参照して、対応ブロックデータを格納しているデータエントリを特定する。この場合、格納先情報を用いて、対応ブロックデータを格納しているデータエントリを特定することが可能になる。
【０２２８】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０２２９】
この出願は、２００９年２月２７日に出願された日本出願特願２００９−４５９８９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０２３０】
１      キャッシュメモリシステム
１１    アドレス格納部
１２    データ格納部
１３    制御部
１０１  アドレスレジスタ
１０２〜１０４  アドレスアレイ
１０５〜１０６  データアレイ
１０７〜１０９  比較器
１１０  キャッシュ制御ユニット
１３２  制御アレイ
２      ＣＰＵ
３      メモリ
【図１】
2010098152.tif 000003
【図２】
2010098152.tif 000004
【図３】
2010098152.tif 000005
【図４】
2010098152.tif 000006
【図５】
2010098152.tif 000007
【図６】
2010098152.tif 000008
【図７Ａ】
2010098152.tif 000009
【図７Ｂ】
2010098152.tif 000010
【図７Ｃ】
2010098152.tif 000011
【図７Ｄ】
2010098152.tif 000012
【図７Ｅ】
2010098152.tif 000013
【図７Ｆ】
2010098152.tif 000014
【国際調査報告】
2010098152.tif 000015
2010098152.tif 000016
2010098152.tif 000017