(57)【要約】【課題】キャッシュメモリのハッシュ衝突を容易に発生させるキャッシュメモリ装置を提供する。【解決手段】ハッシュ回路２は、第１アドレスからキャッシュメモリ７のインデックスを示す第１インデックスをハッシュ関数により求め、第１インデックスが示すインデックスにタグを格納する。プリフェッチ部３は、第１アドレスとタグが異なる第２アドレスを生成する。ハッシュ回路４は、第２アドレスから前記キャッシュメモリ７のインデックスを示す第２インデックスをハッシュ関数により求める。衝突検出部５は、第１インデックスと第２インデックスとが一致するか否かを判定する。一致しない場合、ハッシュ値変更部６は、第２インデックスを第１インデックスと一致するように変更し、キャッシュメモリ７における変更した第２インデックスが示すインデックスで、且つ第１アドレスのタグを格納したウェイとは異なる列にタグを格納する。【選択図】図１
2014186397.tif 000002
【特許請求の範囲】
【請求項１】
複数のウェイを有するキャッシュメモリと、
前記主記憶メモリのアドレスである第１アドレスを取得する第１アドレス取得部と、
前記第１アドレスから前記キャッシュメモリのインデックスを示す第１インデックスをハッシュ関数により求め、前記キャッシュメモリにおける前記第１インデックスが示すインデックスに前記第１アドレスのタグを格納する第１インデックス管理部と、
前記第１アドレスから前記第１アドレスとタグが異なる第２アドレスを生成する第２アドレス生成部と、
前記第２アドレスから前記キャッシュメモリのインデックスを示す第２インデックスを前記ハッシュ関数により求める第２インデックス算出部と、
前記第１インデックスと前記第２インデックスとが一致するか否かを判定する判定部と、
前記判定部により一致しないと判定された場合、前記第２インデックスを前記第１インデックスと一致するように変更し、前記キャッシュメモリにおける変更した前記第２インデックスが示すインデックスで、且つ前記第１アドレスのタグを格納したウェイとは異なるウェイに前記第２アドレスのタグを格納する第２インデックス管理部と、
を備えたことを特徴とするキャッシュメモリ装置。
【請求項２】
前記第１インデックス管理部及び前記第２インデックス算出部は、前記ハッシュ関数として排他的論理和を取る関数を用い、
前記判定部は、前記第１インデックスと前記第２インデックスの排他的論理和を求め、
前記第２インデックス管理部は、前記第２インデックスと前記判定部が求めた排他的論理和との排他的論理和を求め、前記第２インデックスを求めた排他的論理和に変更する
ことを特徴とする請求項１に記載のキャッシュメモリ装置。
【請求項３】
前記第２アドレス生成部は、前記第１アドレスに対する事前先読みを行い、前記第２インデックスを生成することを特徴とする請求項１又は２に記載のキャッシュメモリ装置。
【請求項４】
前記第２アドレス生成部は、前記第１アドレスのタグを１つずつインクリメントしていくことで前記第１アドレスに対する事前先読みを行い、前記第２インデックスを生成することを特徴とする請求項３に記載のキャッシュメモリ装置。
【請求項５】
前記第１インデックス管理部は、前記列毎に予め決められたハッシュ関数を用いて、前記列のそれぞれ対応する前記第１インデックスを求め、且つ求めた第１インデックスのいずれか一つが示すインデックスに、該インデックスに対応する第１アドレスのタグを格納し、
前記第２インデックス算出部は、前記ウェイ毎に予め決められたハッシュ関数を用いて、第２アドレスを前記ウェイ毎に順次求め、
前記判定部は、各前記第２インデックスと、各前記第２インデックスに対応するウェイに対応するハッシュ関数を用いて求められた前記第１インデックスとが一致するか否かを判定し、
前記第２インデックス管理部は、各前記第２インデックスを各前記第２インデックスに対応するウェイに対応するハッシュ関数を用いて求められた前記第１インデックスと一致するように変更し、前記キャッシュメモリにおける変更した各前記第２インデックスが示すインデックスで、且つ各前記第２インデックスに対応するウェイに各前記第２アドレスのタグを格納する
ことを特徴とする請求項１〜４のいずれか一つに記載のキャッシュメモリ装置。
【請求項６】
タグを含むアドレスでデータの格納場所が指定される主記憶メモリと、
複数のウェイを有するキャッシュメモリと、
前記主記憶メモリのアドレスである第１アドレスを取得する第１アドレス取得部と、
前記第１アドレスから前記キャッシュメモリのインデックスを示す第１インデックスをハッシュ関数により求め、前記キャッシュメモリにおける前記第１インデックスが示すインデックスに前記第１アドレスのタグを格納する第１インデックス管理部と、
前記第１アドレスから前記第１アドレスとタグが異なる第２アドレスを生成する第２アドレス生成部と、
前記第２アドレスから前記キャッシュメモリのインデックスを示す第２インデックスを前記ハッシュ関数により求める第２インデックス算出部と、
前記第１インデックスと前記第２インデックスとが一致するか否かを判定する判定部と、
前記判定部により一致しないと判定された場合、前記第２インデックスを前記第１インデックスと一致するように変更し、前記キャッシュメモリにおける変更した前記第２インデックスが示すインデックスで、且つ前記第１アドレスのタグを格納したウェイとは異なるウェイに前記第２アドレスのタグを格納する第２インデックス管理部と、
を備えたことを特徴とする情報処理装置。
【請求項７】
前記主記憶メモリのアドレスである第１アドレスを取得し、
複数のウェイを有するキャッシュメモリのインデックスを示す第１インデックスを、前記第１アドレスからハッシュ関数により求め、前記キャッシュメモリにおける前記第１インデックスが示すインデックスに前記第１アドレスのタグを格納し、
前記第１アドレスから前記第１アドレスとタグが異なる第２アドレスを生成し、
前記第２アドレスから前記キャッシュメモリのインデックスを示す第２インデックスを前記ハッシュ関数により求め、
前記第１インデックスと前記第２インデックスとが一致するか否かを判定し、
一致しない場合、前記第２インデックスを前記第１インデックスと一致するように変更し、前記キャッシュメモリにおける変更した前記第２インデックスが示すインデックスで、且つ前記第１アドレスのタグを格納したウェイとは異なるウェイに前記第２アドレスのタグを格納する
ことを特徴とするキャッシュメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリ装置、情報処理装置及びキャッシュメモリ制御方法に関する。
【背景技術】
【０００２】
近年、コンピュータの高速化の一手段として、主記憶メモリ（主記憶装置）とは別に、ＣＰＵにキャッシュメモリと呼ばれる数キロバイトから数メガバイトにも及ぶ高速メモリを配置し処理のスピードアップが図られている。キャッシュメモリは、ＣＰＵがデータや命令などの情報を取得/更新する際に主記憶装置やバスなどによる遅延を隠蔽化させ、ＣＰＵなどと記憶装置との性能差を埋めるために用いる高速小容量メモリである。キャッシュメモリを使用した場合、ＣＰＵは、主記憶メモリからキャッシュメモリに読み込んだデータを、主記憶メモリ上にあるデータに比べて高速で処理することができる。
【０００３】
例えば、キャッシュメモリを用いたシステムとして、ダイレクトマップ方式の１次キャッシュメモリ及び１次キャッシュよりも小規模かつ高速なダイレクトマップ方式の２次キャッシュメモリを有する従来技術が提案されている（例えば、特許文献１参照）。
【０００４】
キャッシュメモリの容量は、キャッシュを検索するアドレス範囲とキャッシュの連想数の積で表される。ここで、キャッシュを検索するアドレス範囲とは、キャッシュのインデックス範囲である。以下では、キャッシュを検索するアドレス範囲を、単に「アドレス範囲」という。また、連想数は、ウェイ数とも呼ばれる。一般的に、設計上の物理的制約から、連想数はアドレス範囲より小さくなる。そして、キャッシュのアドレスが衝突する複数のデータは、キャッシュメモリのウェイ数の上限まで格納することができる。
【０００５】
ソフトウェアは、キャッシュの構造を意識して、キャッシュメモリのアドレスが異なる方向（インデックス方向）にデータを格納したり、ウェイが異なる方向（ウェイ方向）にデータを格納したりすることができる。
【０００６】
情報処理装置においては、キャッシュメモリが適切に動作しているか否かを判定するための試験が行われる。このような試験では、キャッシュメモリに負荷をかけて正常な動作が行われるか否かが判定される。例えば、キャッシュメモリへの負荷は、キャッシュメモリのアドレスが衝突するメモリアクセスを多発させ、外部メモリからキャッシュメモリへのアクセスを発生させたり、キャッシュメモリのデータの置き換え処理を発生させたりすることで増加する。キャッシュメモリのデータの置き換え処理は、「リプレース」とも呼ばれる。
【０００７】
さらに、近年、キャッシュメモリにおけるウェイ数がアドレス範囲の数より小さいという制約を克服するため、キャッシュメモリのアドレスの生成回路にハッシュ関数を導入することで、見かけ上の連想数を増加させる手法が採用されている。アドレス生成回路にハッシュ関数を導入した装置は、導入しない装置に比べてキャッシュのヒット率が高く、外部のメモリ参照の頻度が低くなる傾向がある。
【０００８】
図６は、従来のハッシュ関数を用いない場合のインデックス計算を説明する図である。また、図７は、従来のハッシュ関数を用いた場合のインデックス計算を説明する図である。
【０００９】
図６に示すように、ＣＰＵから指定されたメモリアドレス９０１は、タグ及びインデックスを有する。そして、キャッシュは、キャッシュタグアレイ９０２とキャッシュデータアレイ９０３とを有する。ｐ−１〜ｐ−５は、「ａ」を先頭とする一連のインデックスに対応するように並んでいるタグである。また、ｑ−１〜ｑ−５も、「ａ」を先頭とする一連のインデックスに対応するように並んでいるタグである。ハッシュ関数を用いない場合、タグがｐ−１〜ｐ−５のデータのそれぞれと、タグがｑ−１〜ｑ−５のデータのそれぞれとは、同じインデックス番号の異なるウェイのエントリに格納される。すなわち、キャッシュタグアレイ９０２では、図６に示すようにウェイ方向にｐ−１〜ｐ−５とｑ−１〜ｑ−５とが並ぶ。このため、図６の場合、ハッシュ関数を用いない場合、同じインデックスを有するアドレスのデータが５つ指定されればキャッシュミスヒットを起こす。
【００１０】
一方、ハッシュ関数を使用した場合、図７のキャッシュタグアレイ９０４に示すように、ｐ−１〜ｐ−５とｑ−１〜ｑ−５とがそれぞれ一致していても、異なるインデックスのエントリに格納される。そのため、ハッシュ前に同じインデックスを有するアドレスのデータが５つ指定されても、キャッシュミスヒットを起こさない確率が図６の場合と比べて高くなる。
【００１１】
ただし、キャッシュメモリに使用されるハッシュ関数は、ハッシュ関数から逆関数を直接求めることができない。そのため、アドレスの生成にハッシュ関数を導入したキャッシュメモリの試験を行う場合、試験プログラムは、予め用意したハッシュ衝突が発生する多数のメモリアドレスを用いてキャッシュメモリに対して負荷をかけることが考えられる。
【００１２】
ハッシュ関数が公開されており且つアルゴリズムが簡単な場合は、ソフトウェアによりハッシュ関数を使用してハッシュ衝突が発生するアドレスのリストを予めピックアップすることができる。そのため、試験プログラムは、予めピックアップされたアドレスを用いてメモリアクセス命令を実行することで、キャッシュメモリに負荷をかけることができる。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開平５−３２４４７３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、ハッシュ関数を公開していない場合や、ハッシュ関数のアルゴリズムが複雑な場合はソフトウェアからハッシュ衝突を発生するアドレスを生成することが困難となり、このような方法によるキャッシュメモリのテストを行うことは困難である。
【００１５】
例えば、ダイレクトマップ方式の１次キャッシュメモリ及び小規模なダイレクトマップ方式の２次キャッシュメモリを用いた従来技術では、ハッシュを用いた場合のキャッシュメモリの試験については考慮しておらず、上記の問題を解決することは困難である。
【００１６】
開示の技術は、上記に鑑みてなされたものであって、キャッシュメモリの負荷試験を行う際に、キャッシュメモリのハッシュ衝突を容易に発生させるキャッシュメモリ装置、情報処理装置及びキャッシュメモリ制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本願の開示するキャッシュメモリ装置、情報処理装置及びキャッシュメモリ制御方法は、一つの態様において、キャッシュメモリは、複数のウェイを有する。第１アドレス取得部は、前記主記憶メモリのアドレスである第１アドレスを取得する。第１インデックス管理部は、前記第１アドレスから前記キャッシュメモリのインデックスを示す第１インデックスをハッシュ関数により求め、前記キャッシュメモリにおける前記第１インデックスが示すインデックスに前記第１アドレスのタグを格納する。第２アドレス生成部は、前記第１アドレスから前記第１アドレスとタグが異なる第２アドレスを生成する。第２インデックス算出部は、前記第２アドレスから前記キャッシュメモリのインデックスを示す第２インデックスを前記ハッシュ関数により求める。判定部は、前記第１インデックスと前記第２インデックスとが一致するか否かを判定する。第２インデックス管理部は、前記判定部により一致しないと判定された場合、前記第２インデックスを前記第１インデックスと一致するように変更し、前記キャッシュメモリにおける変更した前記第２インデックスが示すインデックスで、且つ前記第１アドレスのタグを格納したウェイとは異なるウェイに前記第２アドレスのタグを格納する。
【発明の効果】
【００１８】
本願の開示するキャッシュメモリ装置、情報処理装置及びキャッシュメモリ制御方法の一つの態様によれば、キャッシュメモリの負荷試験を行う際に、キャッシュメモリのハッシュ衝突を容易に発生させることができるという効果を奏する。
【図面の簡単な説明】
【００１９】
【図１】図１は、実施例１に係るキャッシュメモリ装置のブロック図である。
【図２】図２は、メモリアドレスの詳細を表す図である。
【図３】図３は、実施例１に係るキャッシュメモリ装置におけるデータ書込みの試験のフローチャートである。
【図４】図４は、実施例２に係るキャッシュメモリ装置のブロック図である。
【図５】図５は、キャッシュメモリ装置のハードウェア構成図である。
【図６】図６は、従来のハッシュ関数を用いない場合のインデックス計算を説明する図である。
【図７】図７は、従来のハッシュ関数を用いた場合のインデックス計算を説明する図である。
【発明を実施するための形態】
【００２０】
以下に、本願の開示するキャッシュメモリ装置、情報処理装置及びキャッシュメモリ制御方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例により本願の開示するキャッシュメモリ装置、情報処理装置及びキャッシュメモリ制御方法が限定されるものではない。
【実施例１】
【００２１】
図１は、実施例１に係るキャッシュメモリ装置のブロック図である。本実施例に係るキャッシュメモリ装置は、図１に示すように、アドレス取得部１、ハッシュ回路２、プリフェッチ部３、ハッシュ回路４、衝突検出部５、ハッシュ値変更部６を有する。さらに、本実施例に係るキャッシュメモリ装置は、キャッシュメモリ７、比較回路８１〜８４、ヒット判定部９、選択回路１０を有する。
【００２２】
アドレス取得部１は、メモリテストを実施するプログラムが生成したデータを読み出す主記憶メモリ上のアドレスを取得する。以下では、アドレス取得部１がメモリテスト用のプログラムから取得したアドレスを「デマンドアドレス」という。そして、アドレス取得部１は、デマンドアドレスを、タグ１１及びインデックス１２に分ける。タグ１１とは、そのアドレスで指定された主記憶メモリ上のデータがキャッシュに格納されているか否かを判断するための情報である。
【００２３】
タグ１１及びインデックス１２のビット数は予め決められており、アドレス取得部１は、予め決められたビット数に合わせてデマンドアドレスをタグ１１及びインデックス１２に分ける。
【００２４】
アドレス取得部１は、タグ１１の値をプリフェッチ部３へ出力する。また、アドレス取得部１は、タグ１１の値及びインデックス１２の値をハッシュ回路２へ出力する。
【００２５】
ハッシュ回路２は、タグ１１の値及びインデックス１２の値の入力をアドレス取得部１から受ける。そして、ハッシュ回路２は、受信したタグ１１の値及びインデックス１２の値に対してハッシュ関数を用いてハッシュ値を算出する。ここで、本実施例における、ハッシュ回路２によるハッシュ演算の一例について説明する。図２は、メモリアドレスの詳細を表す図である。図２に示すメモリアドレスは、タグ２０１及びインデックス２０２を有している。各領域に対応するようにメモリアドレスの下に記載した数字は、各領域が使用するメモリアドレスを表す。すなわち、タグ２０１は、メモリアドレスの１９〜６３ビットを使用する。また、インデックス２０２は、メモリアドレスの７〜１８ビットを使用する。この場合の、ラインサイズは、０〜６ビットとなる。ハッシュ回路２は、タグ２０１のインデックス２０２側から３ビットずつ５つの値２１１〜２１５を取得する。さらに、ハッシュ回路２は、インデックス１２から値２２１を取得する。そして、ハッシュ回路２は、値２１１〜２１５及び値２２１の各ビットの排他的論理和（ＸＯＲ）を求めることでハッシュ値を算出する。
【００２６】
ハッシュ回路２は、キャッシュメモリ７のキャッシュタグアレイ７１における、求めたハッシュ値を有するインデックスにタグが格納されているか否か、すなわちキャッシュヒットが発生するか否かの判定を、比較回路８１〜８４の比較結果に指示する。例えば、ハッシュ回路２は、３ビットのハッシュ値にインデックス１２の先頭の３ビットを除いた値を付加するなどして１２ビットのインデックスを作成する。そして、ハッシュ回路２は、求めた１２ビットのインデックスをキャッシュタグアレイ７１を検索するためのインデックス番号として用いる。キャッシュヒットが発生しなかった場合、ハッシュ回路２は、比較回路８１〜８４にタグが格納されていないことを通知する。また、ハッシュ回路２は、求めたハッシュ値をデータ書込部１０１へ出力する。
【００２７】
また、ハッシュ回路２は、求めたハッシュ値を衝突検出部５へ出力する。
【００２８】
プリフェッチ部３は、デマンドアドレス、すなわちタグ１１及びインデックス１２の入力をアドレス取得部１から受ける。そして、プリフェッチ部３は、受信したタグ１１を１つずつインクリメントしていき、インクリメントした結果にインデックス１２を付加して、プリフェッチアドレスを生成する。プリフェッチアドレスは、図１に示すように、タグ３１及びインデックス３２を有する。ここで、タグ３１は、タグ１１を１ずつインクリメントしていくことで生成される値である。また、インデックス３２は、インデックス１２と一致する。
【００２９】
プリフェッチ部３は、タグ３１及びインデックス３２をハッシュ回路４へ出力する。
【００３０】
また、プリフェッチ部３は、ハッシュ値変更部６により変更されたハッシュ値を有するインデックスにタグが格納されている場合、比較回路８１〜８４にタグの情報を出力する。
【００３１】
ハッシュ回路４は、タグ３１及びインデックス３２をプリフェッチ部３から受信する。そして、ハッシュ回路４は、タグ３１及びインデックス３２を用いてハッシュ値を求める。ここで、本実施例では、例えば、ハッシュ回路４は、ハッシュ回路２と同様にタグ１１から取得した５つの３ビットの値及びインデックス１２から取得した３ビットの値の各ビットの排他的論理和を求めることでハッシュ値を算出する。
【００３２】
ハッシュ回路４は、算出したハッシュ値を衝突検出部５及びハッシュ値変更部６へ出力する。
【００３３】
衝突検出部５は、デマンドアドレスのハッシュ値の入力をハッシュ回路２から受ける。さらに、衝突検出部５は、プリフェッチアドレスのハッシュ値の入力をハッシュ回路２から受ける。そして、衝突検出部５は、デマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値との各ビットの排他的論理和を求める。図１中の四角で囲われた数字の列が、アドレスの遷移の一例を示している。例えば、デマンドアドレスのハッシュ値が「１１１」であり、プリフェッチアドレスのハッシュ値が「１０１」であれば、衝突検出部５は、各ビットの排他的論理和をもとめ、「０１０」を取得する。ここで、デマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値が一致している場合、すなわち、ハッシュが衝突している場合は、衝突検出部５は、排他的論理和として「０００」を取得する。
【００３４】
そして、衝突検出部５は、求めた排他的論理和をハッシュ値変更部６へ出力する。
【００３５】
ハッシュ値変更部６は、プリフェッチアドレスのハッシュ値の入力をハッシュ回路４から受ける。また、ハッシュ値変更部６は、衝突検出部５が求めたデマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値との各ビットの排他的論理和の結果の入力を衝突検出部５から受ける。
【００３６】
そして、ハッシュ値変更部６は、プリフェッチアドレスのハッシュ値とデマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値との各ビットの排他的論理和の結果との各ビットの排他的論理和を求める。例えば、デマンドアドレスのハッシュ値が「１１１」であり、プリフェッチアドレスのハッシュ値が「１０１」であり、衝突検出部５により求められた排他的論理和が「０１０」の場合で説明する。この場合、ハッシュ値変更部６は、「１０１」と「０１０」との排他的論理和を求め、「１１１」を取得する。ここで、ハッシュ値変更部６の算出結果である「１１１」は、デマンドアドレスのハッシュ値「１１１」と一致する。すなわち、ハッシュ値変更部６は、デマンドアドレスのハッシュ値と衝突するハッシュ値を取得する。
【００３７】
また、デマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値が衝突している場合は、ハッシュ値変更部６は、衝突検出部５から「０００」を受信する。この場合、ハッシュ値変更部６は、プリフェッチアドレスのハッシュ値と「０００」との排他的論理和を求めることになり、プリフェッチアドレスのハッシュ値をそのまま取得することになる。すなわち、デマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値が衝突している場合は、ハッシュ値変更部６は、プリフェッチアドレスのハッシュ値を変更しない。
【００３８】
このようにして、ハッシュ値変更部６は、プリフェッチアドレスのハッシュ値を、デマンドアドレスのハッシュ値と衝突する値に変更する。さらに、ハッシュ値変更部６は、他のプリフェッチアドレスの生成をプリフェッチ部３に指示する。
【００３９】
選択回路１０３は、デマンドアドレスのハッシュ値の入力をハッシュ回路２から受ける。また、選択回路１０３は、プリフェッチアドレスのハッシュ値の入力をハッシュ値変更部６から受ける。また、選択回路１０３は、格納用のデータの入力をデータ書込部１０１から受ける。そして、選択回路１０３は、ハッシュ回路２から受信したデマンドアドレスのハッシュ値及びハッシュ値変更部６から受信したプリフェッチアドレスのハッシュ値を有するインデックスをデータ書込部１０１へ送信する。また、選択回路１０３は、データ書込部１０１から受信したデータのインデックスをキャッシュメモリ７へ出力する。
【００４０】
データ書込部１０１は、ハッシュ回路２が求めたハッシュ値を用いた検索においてヒット判定部９によってキャッシュミスヒットと判定された場合、ハッシュ回路４からハッシュ値を含むインデックスの情報の入力を受ける。また、データ書込部１０１は、デマンドアドレスの入力をアドレス取得部１から受ける。次に、データ書込部１０１は、主記憶メモリ２００のデマンドアドレスからデータを取得する。そして、データ書込部１０１は、キャッシュタグアレイ７１における、ハッシュ回路４から受信したインデックスの空いているウェイのエントリにタグをセットする。さらに、データ書込部１０１は、タグをセットしたインデックス及びウェイに対応するキャッシュデータアレイ７２のエントリに取得したデータを書込む。
【００４１】
ここで、データ書込部１０１は、キャッシュタグアレイ７１にタグをセットする場合、求めたハッシュ値を有するインデックスに対応する各ウェイのエントリに空きがあるか否かを判定する。全てのウェイにおいて求めたハッシュ値を有するインデックスに対応するエントリに空きがない場合、すなわち、エントリが枯渇している場合、データ書込部２は、そのインデックスに対応するエントリにセットされているタグから一つをリプレース対象として選ぶ。例えば、データ書込部１０１は、Least  Recently  Used（ＬＲＵ）方式によってリプレース対象を選択する。そして、データ書込部１０１は、選択したタグがセットされているエントリからそのタグを削除し、現在セットしようとしているタグ１１をセットする。
【００４２】
また、ハッシュ値変更部６が求めたハッシュ値を用いた検索においてヒット判定部９によってキャッシュミスヒットと判定された場合、データ書込部１０１は、ハッシュ値変更部６からハッシュ値を含むインデックスの情報の入力を受ける。また、データ書込部１０１は、プリフェッチアドレスの入力をアドレス取得部１から受ける。次に、データ書込部１０１は、主記憶メモリ２００のプリフェッチアドレスからデータを取得する。そして、データ書込部１０１は、キャッシュタグアレイ７１における、ハッシュ値変更部６から受信したインデックスの空いているウェイのエントリにタグをセットする。さらに、データ書込部１０１は、タグをセットしたインデックス及びウェイに対応するキャッシュデータアレイ７２のエントリに取得したデータを書込む。
【００４３】
データ書込部１０１は、この場合も、キャッシュタグアレイ７１にタグをセットする場合、求めたハッシュ値を有するインデックスに対応する各ウェイのエントリに空きがあるか否かを判定する。そして、全てのウェイにおいて求めたハッシュ値を有するインデックスに対応するエントリに空きがない場合、すなわち、エントリが枯渇している場合、データ書込部１０１は、そのインデックスに対応するエントリにセットされているタグから一つをリプレース対象として選ぶ。そして、データ書込部１０１は、選択したタグがセットされているエントリからそのタグを削除し、現在セットしようとしているタグ３１をセットする。
【００４４】
ここで、デマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値が一致するため、デマンドアドレスのタグとプリフェッチアドレスのタグとが同じインデックス番号のエントリにセットされることになる。例えば、デマンドアドレスが「ｐ−１」でプリフェッチアドレスが「ｐ−２」〜「ｐ−５」とする。この場合、「ｐ−１」〜「ｐ−５」のハッシュ値が一致する。そこで、図１に示すように、「ｐ−１」〜「ｐ−４」は、同じインデックス番号のエントリにタグがセットされる。図１では、「ｐ−１」〜「ｐ−４」のタグがセットされているエントリを、「ｐ−１」〜「ｐ−４」で表している。この場合、ｐ−５も同じインデックス番号を有するエントリにタグがセットされることになるが、既に、そのインデックス番号の全てのウェイが埋まっている。これにより、置き換え、すなわちリプレースが発生する。このように、ハッシュ関数を用いてインデックス番号を生成している場合でも、本実施例に係るキャッシュメモリ装置であれば、容易に衝突を発生させてリプレースを起こすことができ、キャッシュメモリの試験を迅速に行うことができる。
【００４５】
比較回路８１〜８４は、キャッシュタグアレイ７１の各ウェイに対応するように、配置されている。図１では、比較回路８１はウェイ＃０に対応し、比較回路８２はウェイ＃１に対応し、比較回路８３はウェイ＃２に対応し、比較回路８４はウェイ＃３に対応している。
【００４６】
比較回路８１〜８４は、デマンドアドレスのタグ１１及びプリフェッチ部３が算出した各プリフェッチアドレスのタグ３１の入力を受ける。さらに、比較回路８１〜８４は、ハッシュ回路２又はハッシュ値変更部６から比較の指示を受ける。そして、比較回路８１〜８４は、入力されたタグ１１又はタグ３１に一致するタグが対応するウェイに有るか否かを判定する。一致するタグがある場合、比較回路８１〜８４は、一致したタグがセットされているインデックス及びウェイの情報をヒット判定部９及び選択回路１０に出力する。
【００４７】
また、比較回路８１〜８４は、ハッシュ値変更部６が生成したアドレスにより、変更したハッシュ値を有するインデックスにタグが格納されているか否かを判定する。
【００４８】
ヒット判定部９は、タグ１１又はタグ３１に一致するタグがある場合、その一致するタグがセットされているインデックス及びウェイの情報を比較回路８１〜８４から受ける。インデックス及びウェイの情報の入力を比較回路８１〜８４のいずれかから受けると、ヒット判定部９は、キャッシュメモリに格納されているデータがヒットしたと判定する。これに対して、比較回路８１〜８４のいずれからもインデックス及びウェイの情報の入力がない場合、ヒット判定部９は、キャッシュメモリに格納されているデータがヒットしなかったと判定する。
【００４９】
選択回路１０は、タグ１１又はタグ３１に一致するタグがある場合、その一致するタグがセットされているインデックス及びウェイの情報の入力を比較回路８１〜８４から受ける。そして、選択回路１０は、受信したインデックス及びウェイに一致するキャッシュメモリのエントリからデータを取得する。そして、選択回路１０は、取得したデータを出力する。
【００５０】
次に、図３を参照して、本実施例に係るキャッシュメモリ装置によるキャッシュテストの流れについて説明する。図３は、実施例１に係るキャッシュメモリ装置におけるキャッシュテストのフローチャートである。
【００５１】
アドレス取得部１は、デマンドアドレスを取得する（ステップＳ１０１）。アドレス取得部１は、デマンドアドレスのタグ及びインデックスをハッシュ回路２へ出力する。また、アドレス取得部１は、デマンドアドレスをプリフェッチ部３へ出力する。
【００５２】
ハッシュ回路２は、デマンドアドレスの入力をアドレス取得部１から受ける。次に、ハッシュ回路２は、デマンドアドレスのタグ及びイデックスからハッシュ値を算出する（ステップＳ１０２）。そして、ハッシュ回路２、比較回路８１〜８４及びヒット判定部９は、ハッシュ回路２が求めたハッシュ値を用いてキャッシュメモリ７を検索し、キャッシュヒットしたか否かを判定する（ステップＳ１０３）。具体的には、比較回路８１〜８４は、ハッシュ回路２により生成されたアドレスがキャッシュタグアレイ７１におけるハッシュ値を有するインデックスにタグが格納されているか否かを判定する。タグが格納されていない場合、ヒット判定部９は、キャッシュミスヒットと判定する。タグが格納されている場合、比較回路８１〜８４は、ハッシュ回路２が求めたハッシュ値を有するインデックスの各ウェイの値とタグの値とを比較する。ヒット判定部９は、比較結果を基にキャッシュヒットが発生したか否かを判定する。キャッシュヒットした場合（ステップＳ１０３：肯定）、キャッシュメモリ７に格納されているデータが、キャッシュデータアレイ７２から読み出され出力される（ステップＳ１０４）。
【００５３】
ヒット判定部９がキャッシュミスヒットと判定した場合（ステップＳ１０３：否定）、データ書込部１０１は、ハッシュ値を有するインデックスの情報をハッシュ回路２から受信する。さらに、データ書込部１０１は、アドレス取得部１からデマンドアドレスを取得する（ステップＳ１０５）。そして、データ書込部１０１は、主記憶メモリ２００における受信したデマンドアドレスに格納されているデータを読み出す（ステップＳ１０６）。次に、データ書込部１０１は、キャッシュデータを格納する（ステップＳ１０７）。具体的には、データ書込部１０１は、ハッシュ回路２が算出したハッシュ値を有するインデックスのエントリにタグをセットする。さらに、データ書込部１０１は、タグをセットしたキャッシュタグアレイ７１の位置に対応するキャッシュデータアレイ７２のエントリにデータを格納する。
【００５４】
さらに、ハッシュ回路２は、算出したハッシュ値を衝突検出部５へ出力する。プリフェッチ部３は、デマンドアドレスの入力をアドレス取得部１から受ける。そして、プリフェッチ部３は、デマンドアドレスのタグをインクリメントし、プリフェッチアドレスを生成する（ステップＳ１０８）。プリフェッチ部３は、生成したプリフェッチアドレスをハッシュ回路４へ出力する。
【００５５】
ハッシュ回路４は、プリフェッチアドレスの入力をプリフェッチ部３から受ける。次に、ハッシュ回路４は、受信したプリフェッチアドレスのタグ及びイデックスからハッシュ値を算出する（ステップＳ１０９）。そして、ハッシュ回路４は、算出したハッシュ値を衝突検出部５及びハッシュ値変更部６へ出力する。
【００５６】
衝突検出部５は、アドレス取得部１により生成されたデマンドアドレスのハッシュ値の入力をハッシュ回路２から受ける。また、衝突検出部５は、プリフェッチ部３により算出されたプリフェッチアドレスのハッシュ値の入力をハッシュ回路４から受ける。そして、衝突検出部５は、デマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値との各ビットの排他的論理和を求める（ステップＳ１１０）。ここで、衝突検出部５は、排他的論理和の算出結果が「０００」であれば、ハッシュが衝突しており、それ以外であれば、ハッシュは衝突していないと判定する。そして、衝突検出部５は、排他的論理和の算出結果をハッシュ値変更部６へ出力する。
【００５７】
ハッシュ値変更部６は、デマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値との各ビットの排他的論理和の算出結果の入力を衝突検出部５から受ける。また、ハッシュ値変更部６は、プリフェッチアドレスのハッシュ値の入力をハッシュ回路４から受ける。ハッシュ値変更部６は、デマンドアドレスのハッシュ値とプリフェッチアドレスのハッシュ値との各ビットの排他的論理和の算出結果とプリフェッチアドレスのハッシュ値との各ビットの排他的論理和を算出し、ハッシュ値の変更を行う（ステップＳ１１１）。そして、ハッシュ値変更部６、比較回路８１〜８４及びヒット判定部９は、ハッシュ値変更部６が求めたハッシュ値、すなわち変換後のハッシュ値を用いてキャッシュメモリ７を検索し、キャッシュヒットが発生したか否かを判定する（ステップＳ１１２）。具体的には、ハッシュ値変更部６は、キャッシュタグアレイ７１における求めたハッシュ値を有するインデックスにタグが格納されているか否かを判定する。タグが格納されていなかった場合、ヒット判定部９はキャッシュミスヒットと判定する。また、タグが格納されている場合、比較回路８１〜８４は、ハッシュ回路２が求めたハッシュ値を有するインデックスの各ウェイの値とタグの値とを比較する。ヒット判定部９は、比較結果を基にキャッシュヒットが発生したか否かを判定する。
【００５８】
ヒット判定部９がキャッシュミスヒットと判定した場合（ステップＳ１１２：否定）、データ書込部１０１は、プリフェッチアドレスに対するデータの格納により、リプレースが発生するか否かを判定する（ステップＳ１１３）。具体的にはハッシュ値変更部６は、算出した排他的論理和の値を有するインデックスにおいて空いているウェイが無ければ、リプレース発生と判定する。リプレースが発生した場合（ステップＳ１１３：肯定）、ハッシュ値変更部６は、キャッシュデータのリプレース処理を行う（ステップＳ１１４）。
【００５９】
これに対して、リプレースが発生しない場合（ステップＳ１１３：否定）、データ書込部１０１は、キャッシュデータを格納する（ステップＳ１１５）。
【００６０】
そして、データ書込部１０１は、ハッシュ値を有するインデックスの情報をハッシュ値変更部６から取得する。また、データ書込部１０１は、プリフェッチ部３からプリフェッチアドレスを取得する（ステップＳ１１６）。そして、データ書込部１０１は、主記憶メモリ２００における受信したプリフェッチアドレスに格納されているデータを読み出す（ステップＳ１１７）。
【００６１】
一方、キャッシュヒットが発生している場合（ステップＳ１１２：肯定）、処理はステップＳ１０８へ戻る。
【００６２】
プリフェッチ部３は、規定数のプリフェッチアドレスの算出が完了したか否かを判定する（ステップＳ１１８）。完了していない場合（ステップＳ１１８：否定）、プリフェッチ部３は、ステップＳ１０８へ戻る。
【００６３】
これに対して、規定数のプリフェッチアドレスの算出が完了した場合（ステップＳ１１８：肯定）、プリフェッチ部３は、プリフェッチアドレスの算出を終了する。
【００６４】
ここで、図３のフローチャートでは、１組のデマンドアドレスに対するプリフェッチアドレスの算出及びそれらを用いたテストの流れを説明したが、実際には、複数のデマンドアドレスを生成し、それら全てに対して図３のフローを繰り返すことでテストを行う。
【００６５】
また、図３では、デマンドアドレスへのデータの格納の後に、プリフェッチアドレスの生成及びプリフェッチアドレスへのデータの格納を行うように説明したが、これらは並行して行われてもよい。また、主記憶メモリ２００へのアクセスとプリフェッチアドレスの生成及びプリフェッチアドレスへのデータの格納も並行して行うことが可能である。
【００６６】
ここでは、ハッシュ衝突を起こさせるテストの場合について主に説明したが、この情報処理装置は、テスト以外の通常動作も行う。すなわち、テスト時以外には、情報処理装置は以下の動作を行う。情報処理装置は、受け付けたデータ要求に対してキャッシュに格納されているか否かを判定し、キャッシュに格納されている場合には、キャッシュからデータを読み出す。また、キャッシュに格納されていない場合には、情報処理装置は、メモリからデータを読み出し、読み出したデータをキャッシュに格納しておく。この場合、情報処理装置では、プリフェッチ部３などをディセーブルにしておくことが好ましい。また、受け付けたデマンドアドレスは、ハッシュ回路２においてハッシュが求められ、比較回路８１〜８４に送られキャッシュヒットの有無が判定される。
【００６７】
以上に説明したように、本実施例に係るキャッシュメモリ装置は、生成した一つのデマンドアドレスに対して複数のプリフェッチアドレスを生成する。次に、キャッシュメモリ装置は、ハードウェアを用いて生成したアドレス同士の排他的論理和を求めることで衝突を検出し、衝突していない場合にはプリフェッチアドレスのハッシュ値をデマンドアドレスのハッシュ値に一致させる。その後、キャッシュメモリ装置は、ハッシュ値を一致させたデマンドアドレス及びプリフェッチアドレスを順次そのハッシュ値に一致するインデックスを有するエントリにタグをセットしていく。これにより、キャッシュメモリの負荷試験を行う際に、容易にハッシュ値の衝突を発生することができ、迅速にキャッシュメモリのテストを行うことができる。
【実施例２】
【００６８】
図４は、実施例２に係るキャッシュメモリ装置のブロック図である。本実施例に係るキャッシュメモリ装置は、ウェイ毎に異なるハッシュ関数を使用することが実施例１と異なるものである。さらに、本実施例に係るキャッシュメモリ装置では、あるインデックスにおけるエントリが枯渇した状態で、ハッシュ衝突が発生した場合、主記憶メモリに対するリプレースを行わずに、キャッシュのウェイ間で同じインデックスを有するエントリにデータの置き換え処理を行う。このキャッシュのウェイ間でのデータの置き換え処理は「Ｖｉｃｔｉｍ処理」と呼ばれる場合がある。以下では、実施例１と同じ機能を有する各部については説明を省略する。
【００６９】
本実施例では、図４に示すように、キャッシュメモリのウェイ毎にハッシュ回路２１〜２４が配置されている。ここで、本実施例では、４ウェイのキャッシュメモリを例に説明しているため、ハッシュ回路２１〜２４という４つが設けられている。また、本実施例に係るキャッシュメモリ装置には、ハッシュ回路２１〜２４のそれぞれに対応するように、ハッシュ回路４１〜４４、衝突検出部５１〜５４及びハッシュ値変更部６１〜６４が配置されている。さらに、本実施例に係るキャッシュメモリ装置には、選択回路３１０及びハッシュ回路３２１〜３２４が配置されている。
【００７０】
アドレス取得部１は、生成したデマンドアドレスのタグ１１及びインデックス１２を、ハッシュ回路２１〜２４へ出力する。本実施例では、デマンドアドレスはウェイ＃０に格納される場合で説明する。また、アドレス取得部１は、生成したデマンドアドレスをプリフェッチ部３へ出力する。
【００７１】
ハッシュ回路２１〜２４は、予め記憶しているハッシュ関数を用いて、デマンドアドレスのハッシュ値を算出する。ハッシュ回路２１〜２４は、算出したハッシュ値をそれぞれ対応する衝突検出部５１〜５４へ出力する。そして、キャッシュミスヒットの場合、データ書込部１０１は、ウェイ＃０のハッシュ値を有するインデックスのエントリにデマンドアドレスのタグ１１をセットし、デマンドアドレスのデータをウェイ＃０に格納する。本実施例では、デマンドアドレスのデータをウェイ＃０に格納する場合で説明しているが、デマンドアドレスのデータはどのウェイに格納されても良い。データ書込部１０１は、デマンドアドレスのデータが格納されるウェイに対応するハッシュ回路２１〜２４が求めたハッシュ値を有するインデックスのエントリにタグをセットする。また、ハッシュ回路２１〜２４は、求めたハッシュ値を選択回路１３１〜１３４へ出力する。
【００７２】
プリフェッチ部３は、デマンドアドレスの入力をアドレス取得部１から受ける。次に、プリフェッチ部３は、受信したデマンドアドレスのタグ１１を１つずつインクリメントしてプリフェッチアドレスを算出する。そして、プリフェッチ部３は、最初のプリフェッチアドレスをウェイ＃１に対応するハッシュ回路４２に出力する。また、プリフェッチ部３は、２番目のプリフェッチアドレスをウェイ＃２に対応するハッシュ回路４３に出力する。また、プリフェッチ部３は、３番目のプリフェッチアドレスをウェイ＃３に対応するハッシュ回路４４に出力する。また、プリフェッチ部３は、４番目のプリフェッチアドレスをウェイ＃０に対応するハッシュ回路４１に出力する。このようにして、プリフェッチ部３は、データを格納するウェイを順次変更するようにプリフェッチアドレスの出力先をハッシュ回路４１〜４４の中から選択し、プリフェッチアドレスを出力していく。
【００７３】
ハッシュ回路４１〜４４は、それぞれハッシュ回路２１〜２４と同じハッシュ関数を記憶している。ここで、ハッシュ回路４１〜４４はそれぞれ同様の動作を行うので、以下では、ハッシュ回路４１を例に説明する。ハッシュ回路４１は、プリフェッチアドレスの入力をプリフェッチ部３から受ける。そして、ハッシュ回路４１は、受信したプリフェッチアドレスのタグ３１及びインデックス３２に対してハッシュ関数を用いてハッシュ値を算出する。その後、ハッシュ回路４１は、算出したハッシュ値を衝突検出部５１及びハッシュ値変更部６１へ出力する。
【００７４】
衝突検出部５１〜５４はそれぞれ同様の動作を行うので、以下では、衝突検出部５１を例に説明する。衝突検出部５１は、プリフェッチアドレスのハッシュ値の入力をハッシュ回路４１から受ける。また、衝突検出部５１は、デマンドアドレスのハッシュ値の入力をハッシュ回路２１から受ける。
【００７５】
衝突検出部５１は、プリフェッチアドレスのハッシュ値とデマンドアドレスのハッシュ値との各ビットの排他的論理和を求め、求めた結果をハッシュ値変更部６１へ出力する。ここで、例えばハッシュ値が３ビットで表される場合、衝突検出部５１は、排他的論理和が「０００」であればハッシュが衝突しており、排他的論理和がそれ以外であればハッシュの衝突が起こっていないと判定できる。
【００７６】
ハッシュ値変更部６１〜６４はそれぞれ同様の動作を行うので、以下では、ハッシュ値変更部６１を例に説明する。ハッシュ値変更部６１は、ハッシュを行う前のプリフェッチアドレスの入力をプリフェッチ部３から受ける。また、ハッシュ値変更部６１は、プリフェッチアドレスのハッシュ値とデマンドアドレスのハッシュ値との各ビットの排他的論理和の算出結果の入力を衝突検出部５１から受ける。そして、ハッシュ値変更部６１は、プリフェッチアドレスと衝突検出部５１による算出結果との各ビットの排他的論理和を求める。これにより、ハッシュ値変更部６１は、デマンドアドレスとハッシュ衝突を起こすプリフェッチアドレスが求められる。そして、ハッシュ値変更部６１は、ハッシュ衝突を起こすプリフェッチアドレスである排他的論理和の結果を選択回路３１０へ入力する。同様に、ハッシュ値変更部６２〜６４も、求めたハッシュ衝突を起こすプリフェッチアドレスを選択回路３１０へ出力する。
【００７７】
選択回路３１０は、ハッシュ衝突を起こすプリフェッチアドレスの入力をハッシュ値変更部６１〜６４から受ける。そして、選択回路３１０は、入力されたプリフェッチアドレスの中から１つずつ選択し、選択したプリフェッチアドレスを順次ハッシュ回路３２１〜３２４へ出力する。
【００７８】
ハッシュ回路３２１〜３２４は、それぞれ異なったハッシュ関数を記憶している。ハッシュ回路３２１〜３２４は、プリフェッチアドレスの入力を受ける。ハッシュ回路３２１〜３２４は、予め記憶しているハッシュ関数を用いて、受信したプリフェッチアドレスのハッシュ値を算出する。そして、ハッシュ回路３２１〜３２４それぞれの対応するウェイのいずれかでキャッシュがヒットしない場合、データ書込部１０１は、次の動作を行う。すなわち、データ書込部１０１は、ハッシュ回路３２１〜３２４のうちのいずれかに対応するウェイにおけるそのハッシュ値を有するインデックスに応じたエントリにプリフェッチアドレスのタグ３１をセットする。
【００７９】
このようにすることで、デマンドアドレスのハッシュ値と各プリフェッチアドレスのハッシュ値が一致する。すなわち、いずれも同じ値を用いて算出されるハッシュ値となる。そのため、例えば、図４のように４ウェイの場合、１つのデマンドアドレス及び３つのプリフェッチアドレスを格納することで、４ウェイにおける同じ値を用いて算出されるハッシュ値を有するエントリは一応枯渇する。ただし、ウェイ毎にハッシュ関数が異なっているため、ウェイ毎に算出されるハッシュ値は異なり使用しているインデックスは異なっている。そこで、本実施例では、同じ値を用いて算出されるハッシュ値を有するエントリが枯渇しても他のウェイの同じインデックスのエントリにデータが置き換えられる。例えば、図４におけるｐ−１〜ｐ−４は、同じ値を用いて計算されたハッシュ値をインデックスとしているエントリに格納されている場合で考える。この場合、ｐ−２と同じエントリにｐ−５のタグをセットしようとした場合、ｐ−２が既にセットされているので、そのままではセットできない。また、他のウェイにおいても同じ値で算出されたハッシュ値を有するエントリには既にタグがセットされているので、そのままではｐ−５のタグをセットできない。そこで、本実施例に係るデータ書込部１０１は、ｐ−２をウェイ＃０、＃２〜＃３のいずれかの同じインデックスを有するエントリに移動させることで、ｐ−２のタグが格納されていたエントリにｐ−５のタグを格納する。このようなことから、１つのデマンドアドレス及び３つのプリフェッチアドレスを格納しても、未だ主記憶メモリ２００との間でのデータのリプレースは起こらない。そこで、プリフェッチ部３は、最大で１５個のプリフェッチアドレスを生成し、その生成された１５個のプリフェッチアドレスがハッシュ値変更部６１〜６４により格納されれば、キャッシュメモリに格納できないデータが発生し、データのリプレースが発生する。すなわち、本実施例に係るキャッシュメモリ装置は、デマンドアドレスとの間でハッシュ衝突を発生させるプリフェッチアドレスの生成及びデータの格納を繰り返すことで、最終的にキャッシュメモリのウェイ間置き換え処理ができない状況に達することができる。これにより、本実施例に係るキャッシュメモリ装置は、主記憶メモリに対するデータのリプレースを発生させることができる。
【００８０】
さらに、ハッシュ回路３２１〜３２４は、求めた排他的論理和の結果をプリフェッチアドレスのハッシュ値として選択回路１０２へ出力する。また、ハッシュ回路３２１〜３２４は、求めた排他的論理和の結果をプリフェッチアドレスのハッシュ値として選択回路１３１〜１３４のへそれぞれ出力する。
【００８１】
選択回路１３１〜１３４は、デマンドアドレスのハッシュ値の入力をハッシュ回路２から受ける。また、選択回路１３１〜１３４は、プリフェッチアドレスのハッシュ値の入力をハッシュ回路３２１〜３２４からそれぞれ受ける。また、選択回路１３１〜１３４は、格納用のデータの入力をデータ書込部１０１から受ける。そして、選択回路１３１〜１３４は、ハッシュ回路２から受信したデマンドアドレスのハッシュ値及びハッシュ回路３２１〜３２４から受信したプリフェッチアドレスのハッシュ値を有するインデックスをキャッシュタグアレイ７１へ出力する。また、選択回路１０３は、データ書込部１０１から受信したデータのインデックスをキャッシュタグアレイ７１へ出力する。
【００８２】
選択回路１０２は、プリフェッチアドレスのハッシュ値であるハッシュ回路３２１〜３２４が求めた排他的論理和の算出結果をハッシュ回路３２１〜３２４から受信する。さらに、選択回路１０２は、ヒットしたウェイの情報を比較回路８１〜８４から受信する。そして、選択回路１０２は、キャッシュデータアレイ７２内のヒットしたウェイの情報及びハッシュ回路３２１〜３２４から受信したハッシュ値の中で、ヒットしたウェイに対応するハッシュ値をデータ書込部１０１へ出力する。
【００８３】
例えば、ハッシュ回路３２１から出力されたハッシュ値を有するインデックスにプリフェッチアドレスのタグ３１がセットされた場合、ウェイ＃０においてタグがヒットする。そこで、選択回路１０２は、ウェイ＃０の情報を比較回路８１から受信する。そして、選択回路１０２は、ハッシュ値変更部６１から受信したハッシュ値及びウェイ＃０の情報をデータ書込部１０１へ出力する。
【００８４】
データ書込部１０１は、選択回路１０２からハッシュ値及びウェイの情報の入力を受ける。また、データ書込部１０１は、デマンドアドレスで指定されたデータがキャッシュミスヒットの場合、デマンドアドレスの入力をアドレス取得部１から受ける。また、データ書込み部１０１は、プリフェッチアドレスで指定されたデータがキャッシュミスヒットの場合、プリフェッチアドレスの入力をプリフェッチ部３から受ける。次に、データ書込部１０１は、主記憶メモリ２００のデマンドアドレス又はプリフェッチアドレスからデータを取得する。そして、データ書込部１０１は、選択回路１０２から受信したインデックス及びウェイが示すキャッシュデータアレイ７２のエントリに取得したデータを書込む。
【００８５】
比較回路８１〜８４は、デマンドアドレスのタグ及びプリフェッチアドレスのタグのうち現在セットされたタグの情報の入力をプリフェッチ部３から受ける。そして、比較回路８１〜８４は、受信したタグが対応するウェイに存在するか否かを判定する。存在する場合には、比較回路８１〜８４は、タグが存在するウェイの情報を選択回路１０２へ出力する。
【００８６】
以上に説明したように、実施例２に係るキャッシュメモリ装置は、ウェイ毎に異なるハッシュ関数を持っている場合でもハッシュ衝突を容易に発生することができ、キャッシュメモリの試験を迅速に実行することができる。
【００８７】
また、以上の実施例２の説明では、キャッシュメモリのウェイ間でデータの置き換え処理を行う場合を例に説明したが、この処理を行わず、単にウェイ毎にハッシュ関数が異なるキャッシュメモリにおいても、本実施例における各機能は同様の効果を有する。その場合、キャッシュメモリの試験の際に、キャッシュメモリのウェイ間でのデータの置き換え処理が行われる場合に比べて、より早くデータのリプレースを発生させることができる。
【００８８】
（ハードウェア構成）
次に、図５を参照して、以上で説明した各実施例に係るキャッシュメモリ装置のハードウェア構成について説明する。図５は、キャッシュメモリ装置のハードウェア構成図である。
【００８９】
本実施例に係るキャッシュメモリ装置は、ＣＰＵ（Central  Processing  Unit）４０１、メモリ４０２及びキャッシュ４０３を有している。また、キャッシュメモリ装置は、ハッシュ回路４０４、衝突検出回路４０５、ハッシュ値変更回路４０６、比較回路４０７及び選択回路４０８を有している。
【００９０】
ハッシュ回路４０４は、図１に例示したハッシュ回路２及び４、並びに、図４に例示したハッシュ回路２１〜２４及び４１〜４４などの機能を実現する。衝突検出回路４０５は、図１に例示した衝突検出部５及び図４に例示した衝突検出部５１〜５４などの機能を実現する。ハッシュ値変更回路４０６は、図１に例示したハッシュ値変更部６及び図４に例示したハッシュ値変更部６１〜６４などの機能を実現する。比較回路４０７は、図１及び図４に例示した比較回路８１〜８４などの機能を実現する。選択回路４０８は、図１及び図４に例示した選択回路１０などの機能を実現する。
【００９１】
メモリ４０２は、図１及び図４に例示した主記憶メモリ２００の機能を実現する。
【００９２】
また、キャッシュ４０３は、図１及び図４に例示したキャッシュメモリ７の機能を実現する。ここで、本実施例では、ＣＰＵ４０１の外部にキャッシュ４０３を配置しているが、キャッシュ４０３は、ＣＰＵ４０１の内部に配置されてもよい。
【００９３】
さらに、ＣＰＵ４０１、メモリ４０２及びキャッシュ４０３は、図１及び図４に示したアドレス取得部１、プリフェッチ部３及びデータ書込部１０１の機能を実現する。具体的には、メモリ４０２は、上規各機能などを実現するための各種プログラムを格納している。そして、ＣＰＵ４０１は、メモリ４０２から各種プログラムを読出し実行することで、アドレス取得部１、プリフェッチ部３及びデータ書込部１０１などの各機能を実現する。
【符号の説明】
【００９４】
１  アドレス取得部
２  ハッシュ回路
３  プリフェッチ部
４  ハッシュ回路
５  衝突検出部
６  ハッシュ値変更部
７  キャッシュメモリ
９  ヒット判定部
１０  選択回路
２１〜２４  ハッシュ回路
４１〜４４  ハッシュ回路
５１〜５４  ハッシュ衝突検出部
６１〜６４  ハッシュ値変更部
７１  キャッシュタグアレイ
７２  キャッシュデータアレイ
８１〜８４  比較回路
１０１  データ書込部
１０２  選択回路
２００  主記憶メモリ
【図１】
2014186397.tif 000003
【図２】
2014186397.tif 000004
【図３】
2014186397.tif 000005
【図４】
2014186397.tif 000006
【図５】
2014186397.tif 000007
【図６】
2014186397.tif 000008
【図７】
2014186397.tif 000009