(57)【特許請求の範囲】
【請求項１】
メインメモリ内データのコピーを格納することができ、ＣＰＵによりアクセスされるキャッシュメモリと、
ＣＰＵによるアクセス結果が、アクセス対象であるメインメモリ内データのコピーが前記キャッシュメモリ内に存在するキャッシュヒットであるか、前記キャッシュメモリ内に存在しないキャッシュミスであるかを判定するキャッシュ制御手段と
を有し、
キャッシュミス時に、アクセス対象であるメインメモリ内データのコピーを前記キャッシュメモリに書き込むキャッシュ回路において、
メインメモリ内データのコピーを前記キャッシュメモリに書き込むときに、前記キャッシュメモリから追い出されたデータのアドレス情報を登録するリプレース・アドレス・メモリと、
前記キャッシュメモリに格納されたデータをライン単位で置換対象外のデータに設定することができる凍結制御手段と
を有し、
＜１Ａ＞  キャッシュミス時に、前記キャッシュメモリから追い出されたデータのアドレス情報が前記リプレース・アドレス・メモリに未登録であれば、前記キャッシュメモリから追い出されたデータのアドレス情報を前記リプレース・アドレス・メモリに登録し、
＜１Ｂ＞  キャッシュミス時に、前記キャッシュメモリに書き込まれたデータのアドレス情報が前記リプレース・アドレス・メモリに登録されていれば、前記キャッシュメモリに書き込まれたデータを置換対象外のデータに設定し、この置換対象外に設定されたデータのアドレス情報を前記リプレース・アドレス・メモリから削除する
ことを特徴とするキャッシュ回路。
【請求項２】
前記リプレース・アドレス・メモリに登録されているデータのアドレス情報が登録されるプリフェッチ・アドレス・バッファと、
前記プリフェッチ・アドレス・バッファに登録されたアドレス情報のデータを登録できるプリフェッチ・バッファと
を有し、
＜２Ａ＞  ＣＰＵからのメモリアクセス要求が無いときに、前記プリフェッチ・バッファに有効なデータが無ければ、前記プリフェッチ・アドレス・バッファに登録されたアドレス情報を持つラインのデータをメインメモリからフェッチして前記プリフェッチ・バッファに登録し、
＜２Ｂ＞  前記プリフェッチ・バッファに有効なデータが有れば、前記プリフェッチ・バッファのデータを前記キャッシュメモリに登録する
ことを特徴とする請求項１に記載のキャッシュ回路。
【請求項３】
メインメモリ内データのコピーを格納することができ、ＣＰＵによりアクセスされるキャッシュメモリと、
ＣＰＵによるアクセス結果が、アクセス対象であるメインメモリ内データのコピーが前記キャッシュメモリ内に存在するキャッシュヒットであるか、前記キャッシュメモリ内に存在しないキャッシュミスであるかを判定するキャッシュ制御手段と
を有し、
キャッシュミス時に、アクセス対象であるメインメモリ内データのコピーを前記キャッシュメモリに書き込むキャッシュ回路において、
メインメモリ内データのコピーを前記キャッシュメモリに書き込むときに、前記キャッシュメモリから追い出されたデータのアドレス情報を登録するリプレース・アドレス・メモリと、
前記キャッシュメモリに格納されたデータをライン単位で置換対象外のデータに設定することができる凍結制御手段と
を有し、
＜３Ａ＞  キャッシュミス時に、前記キャッシュメモリから追い出されたデータのアドレス情報が前記リプレース・アドレス・メモリに未登録であれば、前記キャッシュメモリから追い出されたデータのアドレス情報を前記リプレース・アドレス・メモリに登録し、前記アドレス情報はカウンタ値＝１という情報を含み、
＜３Ｂ＞  キャッシュミス時に、前記キャッシュメモリに書き込まれたデータのアドレス情報が前記リプレース・アドレス・メモリに登録されていれば、当該登録されているアドレス情報に含まれるカウンタ値が所定の最大値であるか否かを判断し、
＜３Ｂ．１＞  前記所定の最大値より小さければカウンタ値を１だけ増加させ、
＜３Ｂ．２＞  前記所定の最大値であれば前記キャッシュメモリに書き込まれたデータを置換対象外のデータに設定し、この置換対象外に設定されたデータのアドレス情報を前記リプレース・アドレス・メモリから削除する
ことを特徴とするキャッシュ回路。
【請求項４】
前記リプレース・アドレス・メモリに登録されているデータであって、カウンタ値が前記所定の最大値であるアドレス情報が登録されるプリフェッチ・アドレス・バッファと、
前記プリフェッチ・アドレス・バッファに登録されたアドレス情報のデータを登録できるプリフェッチ・バッファと
を有し、
＜４Ａ＞  ＣＰＵからのメモリアクセス要求が無いときに、前記プリフェッチ・バッファに有効なデータが無ければ、前記プリフェッチ・アドレス・バッファに登録されたアドレス情報を持つラインのデータをメインメモリからフェッチして前記プリフェッチ・バッファに登録し、
＜４Ｂ＞  前記プリフェッチ・バッファに有効なデータが有れば、前記プリフェッチ・バッファのデータを前記キャッシュメモリに登録する
ことを特徴とする請求項３に記載のキャッシュ回路。
【請求項５】
＜５Ａ＞  ＣＰＵからのメモリアクセス要求が有り、アクセス結果がキャッシュヒットであるときに、前記プリフェッチ・バッファに有効なデータが無ければ、前記プリフェッチ・アドレス・バッファに登録されたアドレス情報を持つラインのデータをメインメモリからフェッチして前記プリフェッチ・バッファに登録する
ことを特徴とする請求項２又は４のいずれかに記載のキャッシュ回路。
【請求項６】
前記処理＜２Ｂ＞又は前記処理＜４Ｂ＞が、ＣＰＵからのメモリアクセス要求が無いときに実行されることを特徴とする請求項２又は４のいずれかに記載のキャッシュ回路。
【請求項７】
前記処理＜２Ｂ＞又は前記処理＜４Ｂ＞が、ＣＰＵからのメモリアクセス要求が有り、アクセス結果がキャッシュミスであるときに実行されることを特徴とする請求項２、４、５、及び６のいずれかに記載のキャッシュ回路。
【請求項８】
前記処理＜２Ａ＞又は前記処理＜４Ａ＞において、前記プリフェッチ・アドレス・バッファに登録されたアドレス情報のインデックス部と同じインデックス部を持つラインのデータであって置換対象外のものが前記キャッシュメモリ内に登録されている場合には、前記プリフェッチ・アドレス・バッファに登録されているアドレス情報を削除して、前記プリフェッチ・バッファへのデータの登録を行わないことを特徴とする請求項２、４、５、６、及び７のいずれかに記載のキャッシュ回路。
【請求項９】
前記処理＜１Ｂ＞又は前記処理＜３Ｂ．２＞において、前記キャッシュメモリに書き込まれた置換対象外のデータのアドレス情報を前記プリフェッチ・アドレス・バッファから削除することを特徴とする請求項２、４、５、６、７及び８のいずれかに記載のキャッシュ回路。
【請求項１０】
前記リプレース・アドレス・メモリにアドレス情報を登録するときに、前記リプレース・アドレス・メモリに空きエントリがある場合には、空きエントリにアドレス情報を登録し、空きエントリがない場合には、乱数により決定されたエントリにアドレス情報を登録することを特徴とする請求項１から９までのいずれかに記載のキャッシュ回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、メインメモリ内データのコピーを格納することができ、ＣＰＵ（中央演算装置）によりアクセスされるキャッシュメモリを備えたキャッシュ回路に関するものである。
【０００２】
【従来の技術】
一般に、コンピュータシステムにおいては、相対的に処理速度が遅いメインメモリと相対的に処理速度が速いＣＰＵとの間に、メインメモリより記憶容量は小さいがメインメモリより処理速度の早いキャッシュメモリが備えられている。キャッシュメモリは、ＣＰＵから見たメインメモリの見かけ上の処理速度を高めるために、メインメモリ内データの一部のコピーを一時的に格納する。
【０００３】
ＣＰＵによるアクセス（ＣＰＵによる読み込み動作、即ち、フェッチ）の結果が、アクセス対象であるメインメモリ内データのコピーがキャッシュメモリ内に存在するキャッシュヒット（Cache Hit）であれば、ＣＰＵによるキャッシュメモリへのアクセスが実行される。キャッシュヒット時のアクセス時間（ヒットタイム）は、キャッシュメモリの処理速度に依存するので、短く（通常、ＣＰＵクロックの１サイクル）、アクセスの高速化が図れ、結果的にＣＰＵの処理速度は向上する。
【０００４】
一方、ＣＰＵによるアクセス結果が、アクセス対象であるメインメモリ内データのコピーがキャッシュメモリ内に存在しないキャッシュミス（Cache Miss）（又はヒットミス）であれば、キャッシュメモリ内のデータのライン（又はブロック）とメインメモリ内のデータのライン（又はブロック）とを置き換える（ブロック置換する）ことによって、メインメモリ内データをキャッシュメモリに書き込んでから、ＣＰＵによるキャッシュメモリへのアクセスが実行される。したがって、キャッシュミス時のアクセス時間（ミスペナルティ）は長く（通常、ＣＰＵクロックの８〜３２サイクル）、結果的にＣＰＵの処理速度は低下する。
【０００５】
【発明が解決しようとする課題】
上記したように、従来のキャッシュ回路においては、キャッシュミス時には、自動的にブロック置換を実行していた。しかしながら、キャッシュミス時にブロック置換を実行すると、ブロック置換によりキャッシュメモリから追い出されるデータが存在する。仮に、この追い出されたデータがＣＰＵから頻繁に参照されていたデータであるならば、その後、この追い出されたデータを含むラインに再度アクセスがなされる可能性は高いと考えられる。したがって、ＣＰＵから頻繁に参照されていたデータをキャッシュメモリから追い出した場合には、その後のブロック置換の回数が増大してしまい、結果的にＣＰＵの処理速度が低下することが予想される。
【０００６】
そこで、本発明は、上記したような従来技術の課題を解決するためになされたものであり、その目的とするところは、キャッシュヒット率を向上させることによりＣＰＵ処理速度の向上を図ることができるキャッシュ回路を提供することにある。
【０００７】
【課題を解決するための手段】
本発明のキャッシュ回路は、メインメモリ内データのコピーを格納することができ、ＣＰＵによりアクセスされるキャッシュメモリと、ＣＰＵによるアクセス結果が、アクセス対象であるメインメモリ内データのコピーが前記キャッシュメモリ内に存在するキャッシュヒットであるか、前記キャッシュメモリ内に存在しないキャッシュミスであるかを判定するキャッシュ制御手段とを有し、キャッシュミス時に、アクセス対象であるメインメモリ内データのコピーを前記キャッシュメモリに書き込むものであって、
メインメモリ内データのコピーを前記キャッシュメモリに書き込むときに、前記キャッシュメモリから追い出されたデータのアドレス情報を登録するリプレース・アドレス・メモリと、前記キャッシュメモリに格納されたデータをライン単位で置換対象外のデータに設定することができる凍結制御手段とを有し、
＜１Ａ＞  キャッシュミス時に、前記キャッシュメモリから追い出されたデータのアドレス情報が前記リプレース・アドレス・メモリに未登録であれば、前記キャッシュメモリから追い出されたデータのアドレス情報を前記リプレース・アドレス・メモリに登録し、
＜１Ｂ＞  キャッシュミス時に、前記キャッシュメモリに書き込まれたデータのアドレス情報が前記リプレース・アドレス・メモリに登録されていれば、前記キャッシュメモリに書き込まれたデータを置換対象外のデータに設定し、この置換対象外に設定されたデータのアドレス情報を前記リプレース・アドレス・メモリから削除することを特徴としている。
【０００８】
また、前記リプレース・アドレス・メモリに登録されているデータのアドレス情報が登録されるプリフェッチ・アドレス・バッファと、前記プリフェッチ・アドレス・バッファに登録されたアドレス情報のデータを登録できるプリフェッチ・バッファとをさらに備え、
＜２Ａ＞  ＣＰＵからのメモリアクセス要求が無いときに、前記プリフェッチ・バッファに有効なデータが無ければ、前記プリフェッチ・アドレス・バッファに登録されたアドレス情報を持つラインのデータをメインメモリからフェッチして前記プリフェッチ・バッファに登録し、
＜２Ｂ＞  前記プリフェッチ・バッファに有効なデータが有れば、前記プリフェッチ・バッファのデータを前記キャッシュメモリに登録するように構成してもよい。
【０００９】
また、他の発明のキャッシュ回路は、メインメモリ内データのコピーを格納することができ、ＣＰＵによりアクセスされるキャッシュメモリと、ＣＰＵによるアクセス結果が、アクセス対象であるメインメモリ内データのコピーが前記キャッシュメモリ内に存在するキャッシュヒットであるか、前記キャッシュメモリ内に存在しないキャッシュミスであるかを判定するキャッシュ制御手段とを有し、キャッシュミス時に、アクセス対象であるメインメモリ内データのコピーを前記キャッシュメモリに書き込むキャッシュ回路において、
メインメモリ内データのコピーを前記キャッシュメモリに書き込むときに、前記キャッシュメモリから追い出されたデータのアドレス情報を登録するリプレース・アドレス・メモリと、前記キャッシュメモリに格納されたデータをライン単位で置換対象外のデータに設定することができる凍結制御手段とを有し、
＜３Ａ＞  キャッシュミス時に、前記キャッシュメモリから追い出されたデータのアドレス情報が前記リプレース・アドレス・メモリに未登録であれば、前記キャッシュメモリから追い出されたデータのアドレス情報を前記リプレース・アドレス・メモリに登録し、前記アドレス情報はカウンタ値＝１という情報を含み、
＜３Ｂ＞  キャッシュミス時に、前記キャッシュメモリに書き込まれたデータのアドレス情報が前記リプレース・アドレス・メモリに登録されていれば、当該登録されているアドレス情報に含まれるカウンタ値が所定の最大値であるか否かを判断し、
＜３Ｂ．１＞  前記所定の最大値より小さければカウンタ値を１だけ増加させ、
＜３Ｂ．２＞  前記所定の最大値であれば前記キャッシュメモリに書き込まれたデータを置換対象外のデータに設定し、この置換対象外に設定されたデータのアドレス情報を前記リプレース・アドレス・メモリから削除することを特徴としている。
【００１０】
また、前記リプレース・アドレス・メモリに登録されているデータであって、カウンタ値が前記所定の最大値であるアドレス情報が登録されるプリフェッチ・アドレス・バッファと、前記プリフェッチ・アドレス・バッファに登録されたアドレス情報のデータを登録できるプリフェッチ・バッファとをさらに備え、
＜４Ａ＞  ＣＰＵからのメモリアクセス要求が無いときに、前記プリフェッチ・バッファに有効なデータが無ければ、前記プリフェッチ・アドレス・バッファに登録されたアドレス情報を持つラインのデータをメインメモリからフェッチして前記プリフェッチ・バッファに登録し、
＜４Ｂ＞  前記プリフェッチ・バッファに有効なデータが有れば、前記プリフェッチ・バッファのデータを前記キャッシュメモリに登録するように構成してもよい。
【００１２】
【発明の実施の形態】
第１の実施形態
図１は、本発明の第１の実施形態に係るキャッシュ回路の構成を概略的に示すブロック図である。
【００１３】
図１に示されるように、第１の実施形態に係るキャッシュ回路は、メインメモリ（図示せず）内データのコピーを格納することができるキャッシュメモリ１１と、キャッシュメモリ１１に格納された４個のワードデータ（Ｗｏｒｄ１〜４）のいずれかを選択するワード選択回路１２と、トライステートバッファ１３と、ＣＰＵ（図示せず）からのアクセス（ＣＰＵによる読み込み動作、即ち、フェッチ）結果がキャッシュヒットであるかキャッシュミスであるかを判定するヒット判定回路（キャッシュ制御手段）１４とを有する。
【００１４】
また、第１の実施形態に係るキャッシュ回路は、キャッシュミス時にキャッシュメモリ１１から追い出された（即ち、上書きにより削除された）データのアドレス情報を記憶するリプレース・アドレス・メモリ（Replace Address Memory）（以下「ＲＰＡＭ」と記す。）１５と、キャッシュメモリ１１の凍結ビットＦの値を当該ラインのデータが置換対象外であることを示す“１”に変更することができる凍結制御回路（凍結制御手段）１６とを有する。
【００１５】
また、図１において、符号２１は、ＣＰＵからのアドレス（以下「ＣＰＵアドレス」と記す。）を示し、符号２２は、有効ビットクリア指示レジスタ（ＶＣＬＲ＿ｒｅｇ）を示し、符号２３は、凍結ビットクリア指示レジスタ（ＦＣＬＲ＿ｒｅｇ）を示す。
【００１６】
第１の実施形態においては、ＣＰＵのアドレス幅は３２ビット（図１に、ビット位置３１〜０として示す。）である。ＣＰＵアドレス２１の幅は、キャッシュメモリ１１の容量及びリードブロックサイズ（メインメモリから読み取り、キャッシュメモリに書き込むデータのサイズ）に基づいて決定される。ＣＰＵアドレス２１は、タグデータ部（以下「ＴＡＧ部」と記す。）２１Ｔと、インデックスデータ部（以下「ＩＮＤＥＸ部」と記す。）２１Ｉと、ワードオフセット（Word Offset）と、バイトオフセット（Byte Offset）とから構成される。ＣＰＵアドレス２１においては、ＴＡＧ部２１Ｔを１６ビット、ＩＮＤＥＸ部２１Ｉを１２ビット、ワードオフセットを２ビット、バイトオフセットを２ビットとしている。例えば、リードブロックサイズが４ワードであり、キャッシュ容量が６４ＫＢである場合には、ＩＮＤＥＸ部２１Ｉは１２ビットとなり、ＴＡＧ部２１Ｔは１６ビットとなり、キャッシュメモリ１１のエントリ数は４０９６となる。なお、以上の数値例は例示に過ぎず、他の値を採用することができる。
【００１７】
キャッシュメモリ１１は、ＣＰＵから見たメインメモリの見かけ上の処理速度を高めるために、メインメモリ内データの一部のコピーを一時的に格納する。図１に示されるキャッシュメモリ１１は、ダイレクトマップ（Direct Map）方式（１ウェイのセットアソシアティブ（One Way Set Associative）方式に相当する。）のメモリである。キャッシュメモリ１１の１ライン（又は１ブロック）は、タグデータ部（ＴＡＧ部）１１Ｔ、有効ビットＶ、凍結ビットＦ、４ワード（Ｗｏｒｄ１〜４）分のデータ（ＤＡＴＡ）から構成されている。キャッシュメモリ１１内のＴＡＧ部１１Ｔ、有効ビットＶ、及び凍結ビットＦを記憶する領域を、タグＲＡＭ（以下「ＴＡＧＭ」と記す。）１１ＴＭと言い、キャッシュメモリ１１内のデータ（ＤＡＴＡ）を記憶する領域をデータＲＡＭ（以下「ＤＡＴＡ部」と記す。）１１ＤＭと言う。なお、キャッシュメモリ１１として、２ウェイ以上のセットアソシアティブ方式のメモリ等を採用することもできる。
【００１８】
ワード選択回路１２は、ＣＰＵアドレス２１のワードオフセットを選択指示信号として、ＣＰＵアドレス２１のワードオフセットに基づいて所望のワードデータ（Ｗｏｒｄ１〜４のいずれか）を選択する。
【００１９】
トライステートバッファ１３は、３つの状態、即ち、キャッシュメモリ１１からデータを読み出すときの読出し状態、キャッシュメモリ１１にデータを書き込むときの書込み状態、及び非接続状態のいずれかを選択できる。
【００２０】
ヒット判定回路１４は、ＣＰＵからのアクセス結果がキャッシュヒットであるかキャッシュミスであるかを判定する。ＣＰＵアドレス２１がキャッシュメモリ１１に入力されると、ＣＰＵアドレス２１のＩＮＤＥＸ部２１Ｉ（図１のＣＰＵアドレス２１におけるビット位置１５からビット位置４までの１２ビット）がアドレスデコードされ、キャッシュメモリ１１内におけるリード対象となるエントリ１１Ｅが決まる。ヒット判定回路１４は、キャッシュメモリ１１内におけるリード対象となったエントリ１１ＥのＴＡＧＭ１１ＴＭ内のタグデータ（ＴＡＧ部）１１ＴとＣＰＵアドレス２１のＴＡＧ部２１Ｔとが一致すればキャッシュヒットと判定し、さらに有効ビットＶが有効を示すビット“１”であるかどうかを判定する。
【００２１】
ＲＰＡＭ１５は、連想メモリ（Associative Memory）であるＣＡＭ（Contents Addressable Memory）により構成される。ＣＡＭは、ＣＡＭ内に入力検索データと一致するデータが存在する場合には、即座に登録データを読み出す機能を持つ。
【００２２】
凍結制御回路１６は、ヒット判定回路１４の判定結果及びＲＰＡＭ１５に登録されているアドレス情報に基づいて、キャッシュメモリ１１の凍結ビットＦの値を当該ラインのデータが置換可能であることを示す“０”から当該ラインのデータが置換対象外であることを示す“１”に変更する。
【００２３】
有効ビットクリア指示レジスタ（ＶＣＬＲ＿ｒｅｇ）２２は、ソフトウェアによりキャッシュメモリ１１の有効ビットＶをクリアする。凍結ビットクリア指示レジスタ（ＦＣＬＲ＿ｒｅｇ）２３は、ソフトウェアによりキャッシュメモリ１１の凍結ビットＦをクリアする。
【００２４】
図２は、図１のＲＰＡＭ１５及び凍結制御回路１６の構成を詳細に示す図である。
【００２５】
図２に示されるＲＰＡＭ１５のインターフェースの説明を以下の表１に示す。なお、表１の２列目の欄において、「Ｉ」は入力を示し、「Ｏ」は出力を示す。
【表１】
0004266605.tif 000002
【００２６】
また、図２に示される凍結制御回路１６のインターフェースの説明を以下の表２に示す。なお、表２の２列目の欄において、「Ｉ」は入力を示し、「Ｏ」は出力を示す。
【表２】
0004266605.tif 000003
【００２７】
さらに、図２に示されるＲＰＡＭ１５のコマンドを以下の表３に示す。
【表３】
0004266605.tif 000004
【００２８】
さらにまた、図２に示される凍結制御回路１６の機能を以下の表４に示す。
【表４】
0004266605.tif 000005
【００２９】
図３は、カウンタ値Ｒ１のビット数ｎが１である場合のＲＰＡＭ１５のコンテンツ部の構成例（初期状態）（２進表記）を示す図である。図３に示されるように、ＲＰＡＭ１５のコンテンツ部は、１６ビットのＴＡＧ部１５Ｔと、１２ビットのＩＮＤＥＸ部１５Ｉと、１ビットのカウンタ値Ｒ１とを含む。
【００３０】
図４は、第１の実施形態に係るキャッシュ回路の動作を示すフローチャートである。図４に基づいて、第１の実施形態に係るキャッシュ回路の動作を説明する。
【００３１】
図４に示されるように、ＣＰＵアドレス２１のアクセスがあると、先ず、ＣＰＵアドレス２１のＩＮＤＥＸ部２１Ｉに一致するＩＮＤＥＸを持つキャッシュメモリ１１のエントリ１１Ｅについて、ヒット判定回路１４がＣＰＵアドレス２１のＴＡＧ部２１Ｔに一致するＴＡＧ部１１Ｔを検索する。一致するＴＡＧ部１１Ｔがキャッシュメモリ１１内の検索されたエントリ１１Ｅに存在するキャッシュヒットであれば（ステップＳ１０１におけるＹＥＳ）、ＣＰＵによりキャッシュメモリ１１内のデータがワード選択回路１２を通して読み出される。ＣＰＵアドレス２１のＴＡＧ部２１Ｔに一致するＴＡＧ部１１Ｔがメインメモリ内データのコピーがキャッシュメモリ１１内の検索されたエントリ１１Ｅに存在しないキャッシュミスであれば（ステップＳ１０１におけるＮＯ）、置換対象エントリの凍結ビットＦが置換対象外を示す“１”であるか否かを判定する（ステップＳ１０２）。
【００３２】
凍結ビットＦが“１”であれば（ステップＳ１０２におけるＹＥＳ）、キャッシュメモリ１１におけるブロック置換は実行しない。一方、凍結ビットＦが“０”であれば（ステップＳ１０２におけるＮＯ）、置換対象エントリの有効ビットＶが有効を示す“１”であるか否かを判定する（ステップＳ１０３）。
【００３３】
有効ビットＶが無効を示す“０”であれば（ステップＳ１０３におけるＮＯ）、キャッシュメモリ１１の当該エントリ（有効ビットＶが“０”であるエントリ）にメインメモリ内データを書き込む（ステップＳ１０４）。有効ビットＶが有効を示す“１”であれば（ステップＳ１０３におけるＹＥＳ）、キャッシュメモリ１１の置換対象エントリからデータを追い出し、メインメモリ内データを書き込む（ステップＳ１０５）。
【００３４】
次に、キャッシュメモリ１１に書き込まれたデータのアドレス情報がＲＰＡＭ１５にある（即ち、登録済み）か否かを判断する（ステップＳ１０６）。キャッシュメモリ１１に書き込まれたデータのアドレス情報がＲＰＡＭ１５に無い場合には（ステップＳ１０６におけるＮＯ）、キャッシュメモリ１１から追い出されたデータのアドレス情報を登録する空きエントリがＲＰＡＭ１５にあるか否かを判断する（ステップＳ１０７）。ここで、ＲＰＡＭ１５に空きエントリがあれば（ステップＳ１０７におけるＹＥＳ）、このＲＰＡＭ１５の空きエントリに、キャッシュメモリ１１から追い出されたデータのアドレス情報（即ち、アドレスとカウンタ値Ｒ１＝１）を登録する（ステップＳ１０９）。一方、キャッシュメモリ１１から追い出されたデータのアドレス情報を登録する空きエントリがＲＰＡＭ１５に無ければ（ステップＳ１０７におけるＮＯ）、ＲＰＡＭ１５内の乱数により決定されたエントリ１５Ｅに、キャッシュメモリ１１から追い出されたデータのアドレス情報（即ち、アドレスとカウンタ値Ｒ１＝１）を登録（上書き）する（ステップＳ１０８）。
【００３５】
また、図４のステップＳ１０６において、キャッシュメモリ１１に書き込まれたデータのアドレス情報がＲＰＡＭ１５に登録されていれば（ステップＳ１０６におけるＹＥＳ）、キャッシュメモリ１１に書込まれたデータの凍結ビットＦを“1”に設定し（ステップＳ１１０）、凍結ビットＦが“１”に設定されたキャッシュメモリ１１のエントリ１１ＥのＩＮＤＥＸと同じＩＮＤＥＸ部１５ＩのＲＰＡＭ１５内のエントリ１５Ｅの内容をクリアする（ステップＳ１１１）。
【００３６】
図５は、キャッシュメモリ１１のアドレス（１６進表記）と、そこに格納されるデータの例（１６進表記）を示す図である。また、図６は、１０個のアクセス例（１）〜（１０）（１６進表記）からなるアクセスパターン（図５のアドレスに相当する）を示す図である。また、図７は、ＲＰＡＭ１５のＴＡＧ部及びＩＮＤＥＸ部の２進表記と１６進表記の対応を示す図である。さらに、図８から図１８までは、第１の実施形態に係るキャッシュ回路の動作をより具体的に説明するための図である。なお、キャッシュメモリ１１においてＴＡＧＭ１１ＴＭとＤＡＴＡ部１１ＤＭの登録は一緒に実行されるが、図８から図１８においては、ＤＡＴＡ部１１ＤＭは図示しない。
【００３７】
以下に、図１、及び、図４から図１８までを参照しながら、第１の実施形態に係るキャッシュ回路の動作（アクセス例（１）〜（１０）の順の動作）をより具体的に説明する。
【００３８】
≪アクセス例（１）≫
＜図８：フェッチ“０ｘ００００＿００００”：キャッシュミス＞
図８に示されるように、アクセス例（１）のフェッチは“０ｘ００００＿００００”（１６進表記）であり、フェッチアドレスは“００００＿０００” （１６進表記）である。フェッチアドレス“００００＿０００”の中の右側の３つのビット“０００”はＩＮＤＥＸ部を示す。また、フェッチアドレス“００００＿０００”の中の左側の４つのビット“００００”はＴＡＧ部を示す。
【００３９】
フェッチ“０ｘ００００＿００００”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであり、ＴＡＧＭ１１ＴＭにメインメモリ内データを登録する（図８におけるＴＡＧＭ１１ＴＭ及び図４におけるステップＳ１０１〜Ｓ１０４）。このとき、キャッシュメモリ１１から追い出されるデータは無いので、ＲＰＡＭ１５は何も処理を実行せず、初期状態のままである（図８におけるＲＰＡＭ１５）。
【００４０】
≪アクセス例（２）≫
＜図９：フェッチ“０ｘ０００１＿００００”：キャッシュミス＞
図９に示されるように、アクセス例（２）のフェッチは“０ｘ０００１＿００００”（１６進表記）であり、フェッチアドレスは“０００１＿０００” （１６進表記）である。フェッチ“０ｘ０００１＿００００”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであり、ＴＡＧＭ１１ＴＭにメインメモリ内データを登録する（図９におけるＴＡＧＭ１１ＴＭ及び図４におけるステップＳ１０１〜Ｓ１０３、Ｓ１０５）。アクセス例（２）のフェッチアドレスのＩＮＤＥＸ部とＴＡＧＭ１１ＴＭのＩＮＤＥＸとは同じであるので、上記アクセス例（１）の際に登録されたアドレス情報“００００＿０００”はＴＡＧＭ１１ＴＭから追い出される（“０００１＿０００”が上書きされる）。
【００４１】
次に、ＲＰＡＭ１５を検索し、ＴＡＧＭ１１ＴＭから追い出されるアドレス情報“００００＿０００”がＲＰＡＭ１５に存在するか否かを判断する。ＲＰＡＭ１５にアドレス情報“００００＿０００”は存在しないので、このアドレス情報をＲＰＡＭ１５に登録し、カウンタ値Ｒ１を“１”にセットする（カウンタ値を１インクリメントする）。このＲＰＡＭ１５への登録は、ＲＰＡＭ１５がフルではない（即ち、空きが有る）ので、即座に実行できる（図９におけるＲＰＡＭ１５及び図４におけるステップＳ１０１〜Ｓ１０３、Ｓ１０５〜Ｓ１０７、Ｓ１０９）。
【００４２】
≪アクセス例（３）≫
＜図１０及び図１１：“０ｘ００００＿００００”：キャッシュミス＞
図１０に示されるように、アクセス例（３）のフェッチは“０ｘ００００＿００００”（１６進表記）であり、フェッチアドレスは“００００＿０００” （１６進表記）である。フェッチ“０ｘ００００＿００００”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであり、ＴＡＧＭ１１ＴＭにメインメモリ内データを登録する（図１０におけるＴＡＧＭ１１ＴＭ及び図４におけるステップＳ１０１〜Ｓ１０３、Ｓ１０５）。ＴＡＧＭ１１ＴＭにおいては、アクセス例（３）のフェッチアドレスのＩＮＤＥＸ部とＴＡＧＭ１１ＴＭのＩＮＤＥＸ部とは同じであるので、上記アクセス例（２）の際に登録されたアドレス情報（“０００１＿０００”）はＴＡＧＭ１１ＴＭから追い出される（“００００＿０００”が上書きされる）。
【００４３】
次に、ＲＰＡＭ１５を検索し、ＴＡＧＭ１１ＴＭから追い出されるアドレス情報“０００１＿０００”がＲＰＡＭ１５に存在するか否かを判断する。アドレス情報“０００１＿０００”は存在し（登録済みである）、且つ、カウンタ値Ｒ１＝１であるので、ＴＡＧＭ１１ＴＭの凍結ビットＦを “１”に設定する（図１０におけるＴＡＧＭ１１ＴＭ及び図４におけるステップＳ１１０）。
【００４４】
次に、図１１に示されるように、ＴＡＧＭ１１ＴＭの凍結ビットＦが “１”に設定されたエントリのアドレス情報をＲＰＡＭ１５から削除する（オール０クリアする）（図４におけるＳ１１１）。
【００４５】
≪アクセス例（４）≫
＜図１２：“０ｘ００００＿０００２”：キャッシュミス＞
図１２に示されるように、アクセス例（４）のフェッチは“０ｘ００００＿０００２”（１６進表記）であり、フェッチアドレスは“００００＿０００” （１６進表記）である。フェッチ“０ｘ００００＿０００２”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであるが、登録すべきキャッシュメモリ１１のエントリの凍結ビットＦが“１”に設定されているので、キャッシュメモリ１１に登録しないで、フェッチを直接ＣＰＵへ返す。また、凍結ビットＦが“１”に設定されたエントリに対するアクセスなのでＲＰＡＭ１５は何も処理を実行しない。
【００４６】
≪アクセス例（５）≫
＜図１３：“０ｘ０００４＿００４０”：キャッシュミス＞
図１３に示されるように、アクセス例（５）のフェッチは“０ｘ０００４＿００４０”（１６進表記）であり、フェッチアドレスは“０００４＿００４” （１６進表記）である。フェッチ“０ｘ０００４＿００４０”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであるので、ＴＡＧＭ１１ＴＭに登録される。キャッシュメモリ１１から追い出されるデータがないので、ＲＰＡＭ１５は何も処理を実行しない。
【００４７】
≪アクセス例（６）≫
＜図１４：“０ｘ００００＿００００”：キャッシュヒット＞
図１４に示されるように、アクセス例（６）のフェッチは“０ｘ００００＿００００”（１６進表記）であり、フェッチアドレスは“００００＿０００” （１６進表記）である。フェッチ“０ｘ００００＿００００”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュヒットであるので、データをキャッシュメモリ１１からＣＰＵに送る。また、キャッシュヒットであるので、ＲＰＡＭ１５は何も処理を実行しない。
【００４８】
≪アクセス例（７）≫
＜図１５：“０ｘ０００１＿００００”：キャッシュミス＞
図１５に示されるように、アクセス例（７）のフェッチは“０ｘ０００１＿００００”（１６進表記）であり、フェッチアドレスは“０００１＿０００” （１６進表記）である。フェッチ“０ｘ０００１＿００００”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであるが、キャッシュメモリ１１の登録すべきエントリの凍結ビットＦが“１”に設定されているので、キャッシュメモリ１１に登録しないで、フェッチアドレスをＣＰＵに返す。また、凍結ビットＦが“１”に設定されたエントリ１１Ｅに対するアクセスなので、ＲＰＡＭ１５は何も処理を実行しない。
【００４９】
≪アクセス例（８）≫
＜図１６：“０ｘ００００＿００００”：キャッシュヒット＞
図１６に示されるように、アクセス例（８）のフェッチは“０ｘ００００＿００００”（１６進表記）であり、フェッチアドレスは“００００＿０００”（１６進表記）である。フェッチ“０ｘ００００＿００００”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュヒットであるので、データをキャッシュメモリ１１からＣＰＵに送る。キャッシュヒットなので、ＲＰＡＭ１５は何も処理を実行しない。
【００５０】
≪アクセス例（９）≫
＜図１７：“０ｘ００００＿０００２”：キャッシュミス＞
図１７に示されるように、アクセス例（９）のフェッチは“０ｘ００００＿０００２”（１６進表記）であり、フェッチアドレスは“００００＿０００”（１６進表記）である。フェッチ“０ｘ００００＿０００２”が実行されたキャッシュ回路においては、ヒット判定回路１４によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであるが、キャッシュメモリ１１内の登録すべきエントリの凍結ビットＦが“１”に設定されているので、メインメモリ内データをキャッシュメモリ１１に登録せず、フェッチをＣＰＵに返す。凍結ビットＦが“１”に設定されたエントリ１１Ｅに対するアクセスなので、ＲＰＡＭ１５は何も処理を実行しない。
【００５１】
≪アクセス例（１０）≫
＜図１８：“０ｘ０００４＿００４０”：キャッシュヒット＞
図１８に示されるように、アクセス例（１０）のフェッチは“０ｘ０００４＿００４０”（１６進表記）であり、フェッチアドレスは“０００４＿００４”（１６進表記）である。フェッチ“０ｘ０００４＿００４０”が実行されたキャッシュ回路においては、ヒット判定回路１４によりヒット判定が実行される。この場合の判定結果はキャッシュヒットであるので、キャッシュメモリ１１からデータをＣＰＵに送る。キャッシュヒットであるので、ＲＰＡＭ１５は何も処理を実行しない。
【００５２】
以上のアクセス例（１）〜（１０）について、凍結制御回路１６及びＲＰＡＭ１５による第１の実施形態の制御を適用した場合と、適用しない比較例（従来例）とを比較すると、以下の表５のようになる。
【表５】
0004266605.tif 000006
【００５３】
表５に示されるように、比較例におけるキャッシュヒット率は０．１であるが、第１の実施形態によるキャッシュヒット率は０．３であり、キャッシュヒット率が向上している。
【００５４】
以上説明したように、第１の実施形態に係るキャッシュ回路においては、頻繁に参照されるデータをキャッシュメモリ１１に登録しておき、１度のみしか参照されないようなデータは、キャッシュミス時であってもリプレースを行わないアルゴリズムを採用している。このようにしてキャッシュメモリ１１におけるブロック置換の回数の低減（即ち、キャッシュヒット率の向上）を図り、結果的にＣＰＵの処理速度の向上を図っている。より具体的に言えば、ブロック置換によってキャッシュメモリ１１から追い出されたデータのアドレス情報をＲＰＡＭ１５に登録しておき、ある一定数以上（第１の実施形態においては１回）のキャッシュ登録が確認された場合に、キャッシュメモリ１１のラインを凍結して、置換の対象外としている。このようにすることで、参照頻度の高いデータをキャッシュメモリ１１に留めておくことが可能となり、結果としてキャッシュヒット率が向上し、システム性能の改善が達成できる。
【００５５】
なお、上記説明においては、ダイレクトマップ方式のキャッシュメモリ１１について説明したが、本発明は、２ウェイ以上のセットアソシアティブ方式のキャッシュメモリ１１等の他のメモリにも適用可能である。
【００５６】
第２の実施形態
図１９は、本発明の第２の実施形態に係るキャッシュ回路の動作を示すフローチャートである。第２の実施形態に係るキャッシュ回路は、ＲＰＡＭ１５のカウンタ値Ｒ１のビット数ｎが２以上である（図７はカウンタ値Ｒ１のビット数ｎが１の場合を示す。）点が第１の実施の形態に係るキャッシュ回路と相異する。また、図１９に示されるように、第２の実施形態に係るキャッシュ回路の動作は、ＲＰＡＭ１５のカウンタ値Ｒ１が最大値（２以上）に達したときにキャッシュメモリ１１内の該当するエントリの凍結ビットＦを“１”に設定する点が、ＲＰＡＭ１５のカウンタ値Ｒ１が１であるときにキャッシュメモリ１１内の該当するエントリの凍結ビットＦを“１”に設定する上記第１の実施形態に係るキャッシュ回路の動作と相異する。したがって、第２の実施形態に係るキャッシュ回路の説明においては、図１をも参照する。以下に、図１及び図１９に基づいて、第２の実施形態に係るキャッシュ回路の動作を説明する。
【００５７】
図１９に示されるように、ＣＰＵアドレス２１のアクセスがあると、先ず、ＣＰＵアドレス２１のＩＮＤＥＸ部２１Ｉに一致するＩＮＤＥＸを持つキャッシュメモリ１１のエントリ１１Ｅについて、ヒット判定回路１４がＣＰＵアドレス２１のＴＡＧ部２１Ｔに一致するＴＡＧ部１１Ｔを検索する。一致するＴＡＧ部１１Ｔがキャッシュメモリ１１内に存在するキャッシュヒットであれば（ステップＳ２０１におけるＹＥＳ）、ＣＰＵによりキャッシュメモリ１１内のデータが読み出される。メインメモリ内データのコピーがキャッシュメモリ１１内に存在しないキャッシュミスであれば（ステップＳ２０１におけるＮＯ）、置換対象エントリの凍結ビットＦが置換対象外を示す“１”であるか否かを判定する（ステップＳ２０２）。
【００５８】
凍結ビットＦが“１”であれば（ステップＳ２０２におけるＹＥＳ）、キャッシュメモリ１１におけるブロック置換は実行しない。一方、凍結ビットＦが“０”であれば（ステップＳ２０２におけるＮＯ）、置換対象エントリの有効ビットＶが有効を示す“１”であるか否かを判定する（ステップＳ２０３）。
【００５９】
有効ビットＶが無効を示す“０”であれば（ステップＳ２０３におけるＮＯ）、キャッシュメモリ１１の当該エントリにメインメモリ内データを書き込む（ステップＳ２０４）。有効ビットＶが有効を示す“１”であれば（ステップＳ２０３におけるＹＥＳ）、キャッシュメモリ１１の置換対象エントリからデータを追い出し、メインメモリ内データを書き込む（ステップＳ２０５）。
【００６０】
次に、キャッシュメモリ１１に書き込まれたデータのアドレス情報がＲＰＡＭ１５に登録済みか否かを判断する（ステップＳ２０６）。キャッシュメモリ１１に書き込まれたデータのアドレス情報がＲＰＡＭ１５に無い場合には（ステップＳ２０６におけるＮＯ）、追い出されたデータのアドレス情報を登録する空きエントリがＲＰＡＭ１５にあるか否かを判断する（ステップＳ２０７）。ここで、ＲＰＡＭ１５に空きエントリがあれば（ステップＳ２０７におけるＹＥＳ）、このＲＰＡＭ１５の空きエントリに、キャッシュメモリ１１から追い出されたデータのアドレス情報（即ち、アドレスとカウンタ値Ｒ１＝１）を登録する（ステップＳ２０９）。一方、追い出されたデータのアドレス情報を登録する空きエントリがＲＰＡＭ１５に無ければ（ステップＳ２０７におけるＮＯ）、乱数により決定されたエントリに、キャッシュメモリ１１から追い出されたデータのアドレス情報（即ち、アドレスとカウンタ値Ｒ１＝１）を登録する（ステップＳ２０８）。
【００６１】
また、図１９のステップＳ２０６において、キャッシュメモリ１１に書き込まれたデータのアドレス情報がＲＰＡＭ１５に登録されていれば（ステップＳ２０６におけるＹＥＳ）、キャッシュメモリ１１から追い出されたデータのアドレス情報に含まれるカウンタ値Ｒ１が所定の最大値であるか否かを判断し（ステップＳ２１０）、所定の最大値より小さければカウンタ値を１だけ増加させる（ステップＳ２１１）。図１９のステップＳ２１０において、所定の最大値であればキャッシュメモリ１１に書き込まれたデータの凍結ビットＦを“１”に設定し（ステップＳ２１２）、このラインのデータを置換対象外のデータに設定し、凍結ビットＦが“１”に設定されたエントリ１１ＥのＩＮＤＥＸと同じＩＮＤＥＸ部のＲＰＡＭ１５内のエントリ１５Ｅの内容をクリアする（ステップＳ２１３）。
【００６２】
以上説明したように、第２の実施形態に係るキャッシュ回路においては、頻繁に参照されるデータをキャッシュメモリ１１に登録しておき、１度のみしか参照されないようなデータは、キャッシュミスしてもリプレースを行わないアルゴリズムを採用している。このようにすることによってキャッシュメモリ１１におけるブロック置換の回数を低減（即ち、キャッシュヒット率の向上）を図り、結果的にＣＰＵの処理速度の向上を図っている。具体的に言えば、ブロック置換によってキャッシュメモリ１１から追い出されたデータのアドレス情報をＲＰＡＭ１５に登録しておき、ある一定数以上のキャッシュ登録が確認された場合に、このラインを凍結し、置換の対象外としている。このようにすることで、参照頻度の高いデータをキャッシュに留めることが可能となり、結果としてキャッシュヒット率が向上し、システム性能の改善が達成できる。
【００６３】
なお、第２の実施形態において、上記以外の点は、上記第１の実施形態と同じである。
【００６４】
第３の実施形態
図２０は、本発明の第３の実施形態に係るキャッシュ回路３００の構成を概略的に示すブロック図である。また、図２０において、３０１は、プログラムやデータが格納されるメインメモリ、３０２は、キャッシュメモリ３１１を経由してメインメモリ３０１とアクセスを行うＣＰＵ、３０３は、データバス、３０４は、アドレスバスを示す。
【００６５】
図２０に示されるように、第３の実施形態に係るキャッシュ回路３００は、キャッシュメモリ３１１と、ワード選択回路３１２と、ＣＰＵデータ入力選択用マルチプレクサ（ＭＵＸ）３１３と、リプレース・アドレス・メモリ（ＲＰＡＭ）３１５と、キャッシュ／凍結制御部（キャッシュ制御手段及び凍結制御手段））３１６とを有する。また、第３の実施形態に係るキャッシュ回路３００は、アドレス選択用マルチプレクサ（ＭＵＸ）３２１と、プリフェッチ・アドレス・バッファ（ＰＦＡＢ：Pre Fetch Address Buffer）３２２と、データ方向切替制御部３２３と、プリフェッチ・バッファ（ＰＦＢ：Pre Fetch Buffer）３２４と、キャッシュ登録データ用マルチプレクサ（ＭＵＸ）３２５とを有する。
【００６６】
第３の実施形態においては、第１の実施形態の場合と同様に、ＣＰＵ３０２のアドレス幅は３２ビットである。ＣＰＵ３０２のアドレス幅は、キャッシュメモリ３１１の容量及びリードブロックサイズに基づいて決定される。ＣＰＵアドレスは、タグデータ部（ＴＡＧ部）と、インデックスデータ部（インデックス（ＩＮＤＥＸ）部）と、ワードオフセット（Word Offset）と、バイトオフセット（Byte Offset）とから構成される。ＣＰＵアドレスにおいては、ＴＡＧ部を１６ビット、ＩＮＤＥＸ部を１２ビット、ワードオフセットを２ビット、バイトオフセットを２ビットとしている。例えば、リードブロックサイズが４ワードであり、キャッシュ容量が６４ＫＢである場合には、ＩＮＤＥＸ部は１２ビットとなり、ＴＡＧ部は１６ビットとなり、キャッシュメモリ３１１のエントリ数は４０９６となる。なお、以上の数値例は例示に過ぎず、他の値を採用することができる。
【００６７】
キャッシュメモリ３１１は、メインメモリ３０１内データのコピーを格納することができる。ＣＰＵ３０２は、キャッシュメモリ３１１を経由して、メインメモリ３０１とアクセスを行う。キャッシュメモリ３１１は、ＣＰＵ３０２から見たメインメモリ３０１の見かけ上の処理速度を高めるために、メインメモリ３０１内データの一部のコピーを一時的に格納する。図２０に示されるキャッシュメモリ３１１は、ダイレクトマップ方式のメモリである。キャッシュメモリ３１１の１ライン（又は１ブロック）は、タグデータ部（ＴＡＧ部）、有効ビットＶ、凍結ビットＦ、４ワード（Ｗｏｒｄ１〜４）分のデータ（ＤＡＴＡ）から構成されている。キャッシュメモリ３１１内のＴＡＧ部、有効ビットＶ、及び凍結ビットＦを記憶する領域は、タグＲＡＭ（ＴＡＧＭ）であり、キャッシュメモリ３１１内のデータ（ＤＡＴＡ）を記憶する領域をデータＲＡＭ（ＤＡＴＡ部）である。なお、キャッシュメモリ３１１として、２ウェイ以上のセットアソシアティブ方式のメモリ等を採用することもできる。
【００６８】
ワード選択回路３１２は、キャッシュメモリ３１１に格納された複数個（例えば、４個）のワードデータのいずれかを選択して出力する。ＣＰＵデータ入力選択用ＭＵＸ３１３は、ＣＰＵ３０２の入力データをワード選択回路３１２の出力又はデータ方向切替制御部３２３の出力のいずれかに切替える。
【００６９】
ＲＰＡＭ３１５は、キャッシュミス時にキャッシュメモリ３１１から追い出された（即ち、上書きにより削除された）データのアドレス情報を記憶する。ＲＰＡＭ３１５は、連想メモリであるＣＡＭにより構成される。ＣＡＭは、ＣＡＭ内に入力検索データと一致するデータが存在する場合には、即座に登録データを読み出す機能を持つ。
【００７０】
キャッシュ／凍結制御部３１６は、ＣＰＵ３０２からのアクセス（ＣＰＵ３０２による読み込み動作、即ち、フェッチ）結果がキャッシュヒットであるかキャッシュミスであるかを判定する。また、キャッシュ／凍結制御部３１６は、キャッシュメモリ３１１、ＲＰＡＭ３１５、アドレス選択用ＭＵＸ３２１、ＰＦＡＢ３２２、ＰＦＢ３２４、及びキャッシュ登録データ用ＭＵＸ３２５の制御を行う。キャッシュ／凍結制御部３１６は、キャッシュメモリ３１１の凍結ビットＦの値を当該ラインのデータが置換対象外であることを示す“１”に変更することができる。また、キャッシュ／凍結制御部３１６は、ＣＰＵ３０２からのアクセス結果がキャッシュヒットであるかキャッシュミスであるかの判定結果及びＲＰＡＭ３１５に登録されているアドレス情報に基づいて、キャッシュメモリ３１１の凍結ビットＦの値を当該ラインのデータが置換可能であることを示す“０”から当該ラインのデータが置換対象外（凍結状態）であることを示す“１”に変更する。
【００７１】
アドレス選択用ＭＵＸ３２１は、キャッシュミス時のアドレス（キャッシュ／凍結制御部３１６からのアドレス）とプリフェッチ時のアドレス（ＰＦＡＢ３２２からのアドレス）のいずれかを選択して、アドレスバス３０４に出力する。
【００７２】
ＰＦＡＢ３２２は、プリフェッチするアドレスを保持するレジスタである。ＰＦＡＢ３２２には、ＲＰＡＭ３１５に登録されているデータのアドレス情報（プリフェッチ・アドレス）が登録される。また、ＰＦＡＢ３２２は、アドレス有効信号（有効ビット）ＡＶ（Address Valid）を保持する。有効ビットＡＶは、保持されたプリフェッチ・アドレスが有効であるとき（利用が許可されているとき）に“１”、無効であるとき（利用が不許可のとき）に“０”となる。
【００７３】
データ方向切替制御部３２３は、メインメモリ３０１とのデータの入出力制御を行う。データ方向切替制御部３２３は、メインメモリ３０１へのライトデータをキャッシュ／凍結制御部３１６からデータバス３０３に送り、メインメモリ３０１からのリードデータをキャッシュ登録データ用ＭＵＸ３２５及びＰＦＢ３２４に送る。
【００７４】
ＰＦＢ３２４は、メインメモリ３０１からプリフェッチしてきたデータを保持するレジスタである。ＰＦＢ３２４は、キャッシュ／凍結制御部３１６からの制御信号により制御される。ＰＦＢ３２４は、ＰＦＡＢ３２２に登録されたアドレス情報のデータが登録される。
【００７５】
キャッシュ登録データ用ＭＵＸ３２５は、キャッシュミス時のデータとプリフェッチ・データのいずれかを選択してキャッシュメモリ３１１に出力する。
【００７６】
また、キャッシュメモリ３１１の有効ビットＶ及び凍結ビットＦは、ソフトウェアによりクリアできる。
【００７７】
図２１は、図２０のＲＰＡＭ３１５及びキャッシュ／凍結制御部３１６の構成を詳細に示す図である。
【００７８】
図２１に示されるＲＰＡＭ３１５のインターフェースの説明は、第１の実施形態の説明に用いた表１の通りである。また、図２１に示されるキャッシュ／凍結制御部３１６のインターフェースの説明は、第１の実施形態の説明に用いた表２の通りである。さらに、図２１示されるＲＰＡＭ３１５のコマンドは、第１の実施形態の説明に用いた表３の通りである。さらにまた、図２１に示されるキャッシュ／凍結制御部３１６の機能は、第１の実施形態の説明に用いた表４の通りである。また、カウンタ値Ｒ１のビット数ｎが１である場合のＲＰＡＭ３１５のコンテンツ部の構成例（初期状態）（２進表記）は、第１の実施形態の説明に用いた図３に示す通りである。
【００７９】
上記構成を有する第３の実施形態に係るキャッシュ回路３００は、以下のように動作する。
▲１▼キャッシュミス時に、キャッシュメモリ３１１から追い出されたデータのアドレス情報がＲＰＡＭ３１５に未登録であれば、キャッシュメモリ３１１から追い出されたデータのアドレス情報をＲＰＡＭ３１５に登録する。
▲２▼キャッシュミス時に、キャッシュメモリ３１１に書き込まれたデータのアドレス情報がＲＰＡＭ３１５に登録されていれば、キャッシュメモリ３１１に書き込まれたデータを置換対象外のデータに設定し、この置換対象外に設定されたデータのアドレス情報をＲＰＡＭ３１５から削除する。
▲３▼ＣＰＵ３０２からのメモリアクセス要求が無いときに、ＰＦＢ３２４内に有効なデータが無ければ、ＰＦＡＢ３２２に登録されたアドレス情報を持つラインのデータをメインメモリ３０１からフェッチしてＰＦＢ３２４内に登録する。
▲４▼ＰＦＢ３２４内に有効なデータが有れば、ＰＦＢ３２４内のデータをキャッシュメモリ３１１に登録する。
▲５▼ＣＰＵ３０２からのメモリアクセス要求が有り、アクセス結果がキャッシュヒットであるときに、ＰＦＢ３２４内に有効なデータが無ければ、ＰＦＡＢ３２２に登録されたアドレス情報を持つラインのデータをメインメモリ３０１からフェッチしてＰＦＢ３２４内に登録する。
【００８０】
図２２は、第３の実施形態に係るキャッシュ回路３００の動作を示すフローチャートである。図２０及び図２２に基づいて、第３の実施形態に係るキャッシュ回路の動作（即ち、キャッシュ制御方法）を詳細に説明する。
【００８１】
図２２に示されるように、ＣＰＵ３０１からメモリアクセス要求が無ければ（ステップＳ４０１におけるＮＯ）、ＰＦＢ３２４に有効なデータ（有効ビットＰＶが“１”であるデータ）があるか否かを判断する（ステップＳ４０２）。ＰＦＢ３２４に有効なデータがあれば（ステップＳ４０２におけるＹＥＳ）、ＰＦＢ３２４内のデータをキャッシュメモリ３１１に登録し、キャッシュメモリ３１１の凍結ビットＦ及び有効ビットＶを“１”に設定し、ＰＦＡＢ３２２の内容を全てクリアする（ステップＳ４０３）。また、ＰＦＢ３２４に有効なデータがない場合には（ステップＳ４０２におけるＮＯ）、プリフェッチ・データをＰＦＢ３２４に登録し、さらにキャッシュメモリ３１１に登録するための処理であるプリフェッチ・アクセス・フロー（後述の図２３のＰＦ  ＦＬＯＷ）に移行する。
【００８２】
また、ＣＰＵ３０２からのメモリアクセス要求があり（ステップＳ４０１におけるＹＥＳ）、キャッシュヒットした場合には、プリフェッチ・データをＰＦＢ３２４に登録し、さらにキャッシュメモリ３１１に登録するための処理であるプリフェッチ・アクセス・フロー（後述の図２３のＰＦ  ＦＬＯＷ）に移行する。
【００８３】
また、ＣＰＵ３０２からのメモリアクセス要求があり（ステップＳ４０１におけるＹＥＳ）、キャッシュミスした場合には（ステップＳ４０２におけるＮＯ）、ＰＦＢ３２４に有効なデータ（即ち、有効ビットＰＶが“１”であるデータ）があるか否かを判断する（ステップＳ４０５）。ＰＦＢ３２４に有効なデータがあれば（ステップＳ４０５におけるＹＥＳ）、ＰＦＢ３２４内のデータをキャッシュメモリ３１１に登録し、凍結ビットＦ及び有効ビットＶを“１”に設定し、ＰＦＡＢ３２２の内容を全てクリアする（ステップＳ４０６）。
【００８４】
ＰＦＢ３２４に有効なデータがない場合（ステップＳ４０５におけるＮＯ）、又は、ＰＦＢ３２４内のデータをキャッシュメモリ３１１に登録し、ＰＦＡＢ３２２の内容を全てクリアした後に（ステップＳ４０６の後に）、キャッシュメモリ３１１内の置換対象エントリの凍結ビットＦが“１”であれば（ステップＳ４０７におけるＹＥＳ）、キャッシュメモリ３１１におけるブロック置換は実行せず、キャッシュミスした１ワードデータのみをＣＰＵ３０２に返送する（ステップＳ４０８）。一方、置換対象エントリの凍結ビットＦが“０”であれば（ステップＳ４０７におけるＮＯ）、置換対象エントリの有効ビットＶが有効を示す“１”であるか否かを判定する（ステップＳ４０９）。
【００８５】
置換対象エントリの有効ビットＶが無効を示す“０”であれば（ステップＳ４０９におけるＮＯ）、キャッシュメモリ３１１の当該エントリ（有効ビットＶが“０”であるエントリ）にＰＦＢ３２４内データを初登録する（ステップＳ４１０）。置換対象エントリの有効ビットＶが有効を示す“１”であれば（ステップＳ４０９におけるＹＥＳ）、キャッシュメモリ３１１の置換対象エントリからデータを追い出し、メインメモリ３０１内データを書き込む（ステップＳ４１１）。
【００８６】
次に、キャッシュメモリ３１１に書き込まれたデータのアドレス情報がＲＰＡＭ３１５にある（即ち、登録済み）か否かを判断する（ステップＳ４１２）。キャッシュメモリ３１１に書き込まれたデータのアドレス情報がＲＰＡＭ３１５に無い場合には（ステップＳ４１２におけるＮＯ）、キャッシュメモリ３１１から追い出されたデータのアドレス情報を登録する空きエントリがＲＰＡＭ３１５にあるか否かを判断する（ステップＳ４１３）。ここで、ＲＰＡＭ３１５に空きエントリがあれば（ステップＳ４１３におけるＹＥＳ）、このＲＰＡＭ３１５の空きエントリに、キャッシュメモリ３１１から追い出されたデータのアドレス情報（即ち、アドレスとカウンタ値Ｒ１＝１）を登録する（ステップＳ４１５）。一方、キャッシュメモリ３１１から追い出されたデータのアドレス情報を登録する空きエントリがＲＰＡＭ３１５に無ければ（ステップＳ４１３におけるＮＯ）、ＲＰＡＭ３１５内の乱数により決定されたエントリに、キャッシュメモリ３１１から追い出されたデータのアドレス情報（即ち、アドレスとカウンタ値Ｒ１＝１）を登録（上書き）する（ステップＳ４１４）。
【００８７】
また、ステップＳ４１２において、キャッシュメモリ３１１に書き込まれたデータのアドレス情報がＲＰＡＭ３１５に登録されていれば（ステップＳ４１２におけるＹＥＳ）、キャッシュメモリ３１１に書込まれたデータの凍結ビットＦを“1”に設定し（ステップＳ４１６）、凍結ビットＦが“１”に設定されたキャッシュメモリ３１１のエントリのＩＮＤＥＸ部と同じＩＮＤＥＸ部のＲＰＡＭ３１５内のエントリの内容をクリアし、また、ＰＦＡＢ３２２内エントリがあれば、クリアする。（ステップＳ４１７）。
【００８８】
図２３は、第３の実施形態に係るキャッシュ回路３００のプリフェッチ・アクセス・フローを示すフローチャートである。図２３に基づいて、第３の実施形態に係るキャッシュ回路３００においてプリフェッチ・データをキャッシュメモリ３１１に登録する処理を説明する。
【００８９】
図２３に示されるように、先ず、ＰＦＡＢ３２２のアドレスの有効ビットＡＶが有効、即ち、“１”であり、且つ、ＰＦＢ３２４のデータの有効ビットＰＶが無効、即ち、“０”であるか否かを判断する（ステップＳ４２１）。ＰＦＡＢ３２２のアドレスの有効ビットＡＶが無効、即ち、“０”である場合、又は、ＰＦＢ３２４のデータの有効ビットＰＶが有効、即ち、“１”である場合には（ステップＳ４２１におけるＮＯ）、プリフェッチ・アクセスを行わない。
【００９０】
ＰＦＡＢ３２２のアドレスの有効ビットＡＶが“１”であり、且つ、ＰＦＢ３２４のデータの有効ビットＰＶが“０”である場合には（ステップＳ４２１におけるＹＥＳ）、ＰＦＡＢ３２２のアドレスのＩＮＤＥＸ部と同じＩＮＤＥＸ部のキャッシュメモリ３１１のラインの凍結ビットＦが“１”か否かを判断する（ステップＳ４２２）。この凍結ビットＦが“１”であれば（ステップＳ４２２におけるＹＥＳ）、ＰＦＡＢ３２２の内容をクリアし、プリフェッチ・アクセスは行わない（ステップＳ４２３）。この凍結ビットＦが“０”であれば（ステップＳ４２２におけるＮＯ）、プリフェッチ・アクセスを開始し、フェッチしたデータをＰＦＢ３２４に登録し、ＰＦＢ３２４の有効ビットＰＶを“１”にする。このとき、プリフェッチが完了するまでの期間、ＣＰＵ３０２に対してはＨＩＴ信号の反転信号をウエイト信号としてアサートする（ステップＳ４２４）。
【００９１】
図２４は、第３の実施形態に係るキャッシュ回路３００のＰＦＡＢ３２２にアドレスを登録するフローを示すフローチャートである。図２４に基づいて、第３の実施形態に係るキャッシュ回路３００のアドレスを登録するフローを説明する。
【００９２】
ＰＦＡＢ３２２に有効ビットＡＶが有効、即ち、“１”に設定されているか否かの判断を行い（ステップＳ４３１）、“１”が設定されていれば、ＰＦＡＢ３２２に有効なアドレス・データが登録されているので、ＰＦＡＢ３２２に対するアドレス登録処理を行わない（ステップＳ４３１におけるＹＥＳ）。
【００９３】
ＰＦＡＢ３２２の有効ビットＡＶが無効、即ち、“０”に設定されていれば（ステップＳ４３１におけるＮＯ）、ＰＦＢ３２４の有効ビットＰＶが有効、即ち、“１”に設定されているか否かの判断を行う（ステップＳ４３２）。ＰＦＢ３２４の有効ビットＰＶが有効、即ち、“１”に設定されていれば（ステップＳ４３２におけるＹＥＳ）、ＰＦＢ３２４に有効なデータが登録されているので、ＰＦＢ３２４に対するデータの登録は行わない。
【００９４】
ＰＦＢ３２４の有効ビットＰＶが無効、即ち、“０”に設定されていれば（ステップＳ４３２におけるＮＯ）、ＲＰＡＭ３１５のカウンタ値Ｒ１が最大値（第３の実施形態においてはＲ１＝１）になっているアドレスがあるかを判定する（ステップＳ４３３）。
【００９５】
ＲＰＡＭ３１５のカウンタ値Ｒ１が最大値（Ｒ１＝１）になっているアドレスがある場合には（ステップＳ４３３におけるＹＥＳ）、ＲＰＡＭ３１５のカウンタ値Ｒ１が最大値になっているアドレスを選択し、ＰＦＡＢ３２２に登録し、ＰＦＡＢ３２２の有効ビットＡＶを“１”に設定する。さらに、ＰＦＡＢ３２２に登録したＲＰＡＭ３１５のアドレスデータをクリアする（ステップＳ４３４）。
【００９６】
図２５は、キャッシュメモリ３１１のアドレス（１６進表記）と、そこに格納されるデータの例（１６進表記）を示す図である。また、図２６は、１２個のアクセス例（１）〜（１２）（１６進表記）からなるアクセスパターン（図２５のアドレスに相当する）を示す図である。また、図２７から図３８までは、第３の実施形態に係るキャッシュ回路３００の動作をより具体的に説明するための図である。なお、キャッシュメモリ３１１においてＴＡＧＭとＤＡＴＡ部の登録は一緒に実行されるが、図２７から図３８においては、ＤＡＴＡ部は図示しない。
【００９７】
以下に、図２２から図３８までを参照しながら、第３の実施形態に係るキャッシュ回路３００の動作（アクセス例（１）〜（１２）の順の動作）をより具体的に説明する。なお、図２３に示されるプリフェッチ・アクセス処理は、常に動作し、ＰＦＡＢ３２２が空の場合にカウンタ値が最大値（第３の実施形態においては、カウンタ値Ｒ１＝１が最大値である。）であるアドレスデータを選択して登録しておく。ＲＰＡＭ３１５内のアドレスデータにおいて、カウンタ値が最大値であるアドレスデータを選択して、ＰＦＡＢに登録し、有効ビットＡＶも“１”に設定する。ＣＰＵ３０２からのメモリアクセス要求があるときに、以下のアクセス例（１）〜（１２）のような処理を実行する。
【００９８】
≪アクセス例（１）≫
＜図２７：フェッチ“０ｘ００００＿００００”：キャッシュミス＞
図２７に示されるように、アクセス例（１）のフェッチは“０ｘ００００＿００００”（１６進表記）であり、フェッチアドレスは“００００＿０００” （１６進表記）である。フェッチアドレス“００００＿０００”の中の右側の３つのビット“０００”はＩＮＤＥＸ部を示す。また、フェッチアドレス“００００＿０００”の中の左側の４つのビット“００００”はＴＡＧ部を示す。
【００９９】
フェッチ“０ｘ００００＿００００”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであり、ＴＡＧＭにメインメモリ内データを登録する（図２７における処理（１−１）及び図２２におけるステップＳ４０１、Ｓ４０４、Ｓ４０５、Ｓ４０７、Ｓ４０９、Ｓ４１０）。このとき、キャッシュメモリ３１１から追い出されるデータは無いので、ＲＰＡＭ３１５は何も処理を実行せず、初期状態のままである（図２７におけるＲＰＡＭ３１５）。
【０１００】
≪アクセス例（２）≫
＜図２８：フェッチ“０ｘ０００５＿００５０”：キャッシュミス＞
図２８に示されるように、アクセス例（２）のフェッチは“０ｘ０００５＿００５０”（１６進表記）であり、フェッチアドレスは“０００５＿００５” （１６進表記）である。フェッチ“０ｘ００５０＿００５０”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであり、ＴＡＧＭにメインメモリ内データを登録する（図２８における処理（２−１）及び図２２におけるステップＳ４０１、Ｓ４０４、Ｓ４０５、Ｓ４０７、Ｓ４０９、Ｓ４１０）。このとき、キャッシュメモリ３１１から追い出されるデータは無いので、ＲＰＡＭ３１５は何も処理を実行せず、初期状態のままである（図２８におけるＲＰＡＭ３１５）。
【０１０１】
≪アクセス例（３）≫
＜図２９：“０ｘ０００１＿００００”：キャッシュミス＞
図２９に示されるように、アクセス例（３）のフェッチは“０ｘ０００１＿００００”（１６進表記）であり、フェッチアドレスは“０００１＿０００” （１６進表記）である。フェッチ“０ｘ０００１＿００００”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであり、ＴＡＧＭにメインメモリ内データを登録する（図２９における処理（３−１）及び図２２におけるステップＳ４０１、Ｓ４０４、Ｓ４０５、Ｓ４０７、Ｓ４０９、Ｓ４１１）。ＴＡＧＭにおいては、アクセス例（３）のフェッチアドレスのＩＮＤＥＸ部とＴＡＧＭのＩＮＤＥＸ部とは同じであるので、上記アクセス例（２）の際に登録されたアドレス情報（“０００１＿０００”）はＴＡＧＭから追い出される（“００００＿０００”が上書きされる）。
【０１０２】
次に、ＲＰＡＭ３１５を検索し、ＴＡＧＭから追い出されるアドレス情報“００００＿０００”がＲＰＡＭ３１５に存在するか否かを判断する。アドレス情報“００００＿０００”は存在しないので、ＲＰＡＭ３１５に登録し、カウンタ値Ｒ１を“１”に設定する（図２９における処理（３−２）及び図２２におけるステップＳ４１２、Ｓ４１３，Ｓ４１４）。
【０１０３】
次に、ＲＰＡＭ３１５に登録されているアドレスデータの最大カウント値であるアドレス“０ｘ００００＿００００”がＲＰＡＭ３１５に存在するかを検索する。ヒットしないので、ＲＰＡＭ３１５に登録し、カウント値Ｒ１のビットを“１”に設定する。ここでは、ＲＰＡＭ３１５はフルではない（即ち、空きがある）ので、即時登録できる（図２９における処理（３−２）及び図２２におけるステップＳ４０１、Ｓ４０２、Ｓ４０３）。
【０１０４】
ＲＰＡＭ３１５に登録されているアドレスデータの最大カウント値であるアドレス（０ｘ００００＿０００）をＰＦＡＢ３２２に登録する。ＰＦＡＢ３２２への登録後は、ＲＰＡＭ３１５のラインをクリアする（図２９における処理３−３）。
【０１０５】
また、キャッシュミスなので、プリフェッチはしない。
【０１０６】
≪アクセス例（４）≫
＜図３０：“０ｘ０００３＿００５０”：キャッシュミス＞
図３０に示されるように、アクセス例（４）のフェッチは“０ｘ０００３＿００５０”（１６進表記）であり、フェッチアドレスは“０００３＿００５” （１６進表記）である。フェッチ“０ｘ０００３＿００５０”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであり、ＴＡＧＭにメインメモリ内データを登録する（図３０における処理（４−１）及び図２２におけるステップＳ４０１、Ｓ４０４、Ｓ４０５、Ｓ４０７、Ｓ４０９、Ｓ４１１）。ＴＡＧＭにおいては、アクセス例（４）のフェッチアドレスのＩＮＤＥＸ部とＴＡＧＭのＩＮＤＥＸ部とは同じであるので、上記アクセス例（２）の際に登録されたアドレス情報（“０００５＿００５”）はＴＡＧＭから追い出される（“０００３＿００５”が上書きされる）（図３０における処理（４−１））。
【０１０７】
次に、ＲＰＡＭ３１５を検索し、ＴＡＧＭから追い出されるアドレス情報“０００５＿００５”がＲＰＡＭ３１５に存在するか否かを判断する。アドレス情報“０００５＿００５”は存在しないので、ＲＰＡＭ３１５に登録し、カウンタ値Ｒ１を“１”に設定する（図３０における処理（４−２）及び図２２におけるステップＳ４１２、Ｓ４１３，Ｓ４１４）。
【０１０８】
ＰＦＡＢ３２２の有効ビットＡＶが“１”にセットされているので、ＰＦＡＢ３２２への登録を行わない（図２４のＳ４３１）。
【０１０９】
また、キャッシュミスなので、プリフェッチはしない。
【０１１０】
≪アクセス例（５）≫
＜図３１：“０ｘ００００＿００００”：キャッシュミス＞
図３１に示されるように、アクセス例（５）のフェッチは“０ｘ００００＿００００”（１６進表記）であり、フェッチアドレスは“００００＿０００” （１６進表記）である。フェッチ“０ｘ００００＿００００”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスであり、ＴＡＧＭにメインメモリ内データを登録する（図３１におけるＴＡＧＭ及び図２２におけるステップＳ４０１、Ｓ４０４、Ｓ４０５、Ｓ４０７、Ｓ４０９、Ｓ４１１）。
【０１１１】
ＴＡＧＭにおいては、アクセス例（４）のフェッチアドレスのＩＮＤＥＸ部とＴＡＧＭのＩＮＤＥＸ部とは同じであるので、上記アクセス例（２）の際に登録されたアドレス情報（“０００１＿００１”）はＴＡＧＭから追い出される（“００００＿０００”が上書きされる）。
【０１１２】
同じに、ＲＰＡＭ３１５において新しくＴＡＧＭに登録したデータのアドレスが既に存在するかチェックする。登録済みであり、且つ、カウント値Ｒ１は“１”なので、ＴＡＧＭのビットを“１”に設定する。（凍結ビットセット）（図２２におけるステップＳ４１７）。
【０１１３】
ＲＰＡＭ３１５に登録されているアドレスデータの最大カウント値であるアドレス（０ｘ０００５＿００５０）をＰＦＡＢ３２２に登録する。ＰＦＡＢ３２２への登録後は、ＲＰＡＭ３１５のラインをクリアする。（図２４におけるステップＳ４３１〜Ｓ４３３）
【０１１４】
キャッシュミスなので、プリフェッチはしない。
【０１１５】
≪アクセス例（６）≫
＜図３２：“０ｘ０００２＿００００”：キャッシュミス＞
図３２に示されるように、アクセス例（６）のフェッチは“０ｘ０００２＿００００”（１６進表記）であり、フェッチアドレスは“０００２＿０００” （１６進表記）である。フェッチ“０ｘ０００２＿００００”が実行されたキャッシュ回路においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスである。この場合の判定結果はキャッシュミスであるが、登録すべきキャッシュメモリ３１１のエントリの凍結ビットＦが“１”に設定されているので、キャッシュメモリ３１１に登録しないで、フェッチを直接ＣＰＵへ返す。また、凍結ビットＦが“１”に設定されたエントリに対するアクセスなのでＲＰＡＭ３１５は何も処理を実行しない（図２２におけるステップＳ４０１、Ｓ４０５、Ｓ４０７、Ｓ４０８）。
【０１１６】
ＰＦＡＢ３２２の有効ビットＡＶが“１”に設定されているので、ＰＦＡＢ３２２への登録はしない（図２４におけるＳ４３１）。
【０１１７】
キャッシュミスなので、プリフェッチはしない。
【０１１８】
≪アクセス例（７）≫
＜図３３：“０ｘ０００４＿０００４”：キャッシュミス＞
図３３に示されるように、アクセス例（７）のフェッチは“０ｘ０００４＿００４０”（１６進表記）であり、フェッチアドレスは“０００４＿００４” （１６進表記）である。フェッチ“０ｘ０００４＿００４０”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスである。この場合の判定結果はキャッシュミスであり、ＴＡＧＭにメインメモリ内データを登録する（図２２におけるステップＳ４０１、Ｓ４０４、Ｓ４０５、Ｓ４０７、Ｓ４０９、Ｓ４１１）。
【０１１９】
キャッシュメモリ３１１から追い出されるデータがないので、ＲＰＡＭ３１５は何もしない。
【０１２０】
ＲＰＡＭ３１５の有効ビットＡＶが“１”に設定されているので、ＰＦＡＢへの登録はしない（図２４におけるステップＳ４３１）。
【０１２１】
キャッシュミスなので、プリフェッチはしない。
【０１２２】
≪アクセス例（８）≫
＜図３４：“０ｘ００００＿００００”：キャッシュヒット＞
図３４に示されるように、アクセス例（８）のフェッチは“０ｘ００００＿００００”（１６進表記）であり、フェッチアドレスは“００００＿０００” （１６進表記）である。フェッチ“０ｘ００００＿００００”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュヒットである。
【０１２３】
この場合の判定結果はキャッシュヒットであるので、データをキャッシュメモリ１１からＣＰＵ３０２に送る（図２２におけるステップＳ４０１，４０４）。また、キャッシュヒットであるので、ＲＰＡＭ３１５は何も処理を実行しない。
【０１２４】
ＰＦＡＢ３２２の有効ビットＡＶが“１”に設定されているので、ＰＦＡＢ３２２への登録はしない（図２４におけるステップＳ４３１）。
【０１２５】
キャッシュヒットなので、ＰＦＡＢ３２２に登録されているアドレスが有効であることを確認する。プリフェッチアドレスのＩＮＤＥＸ部と同じＩＮＤＥＸ部のキャッシュメモリ３１１のラインの凍結ビットＦが“１”に設定されているかチェックする。ここでは、セットされていないので、そのアドレスに対するブロックリードを行い、ＰＦＢ３２４へ登録する。ＰＦＢ３２４の有効ビットＰＶを“１”に設定する（図２３におけるステップＳ４２１，Ｓ４２２，Ｓ４２３）。
【０１２６】
≪アクセス例（９）≫
＜図３５：“０ｘ０００１＿００００”：キャッシュミス＞
図３５に示されるように、アクセス例（９）のフェッチは“０ｘ０００１＿００００”（１６進表記）であり、フェッチアドレスは“０００１＿０００” （１６進表記）である。フェッチ“０ｘ０００１＿００００”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。この場合の判定結果はキャッシュミスである。
【０１２７】
この場合の判定結果はキャッシュミスであり、且つ、ＰＦＢ３２４に有効なデータがあるので、このデータをキャッシュメモリ３１１に登録し、同時に、ＰＦＡＢ３２２のデータをクリアする（図３５における処理（９−１）。
【０１２８】
次に、キャッシュミスであるアドレスのキャッシュのラインに凍結ビットＦが“１”に設定されているブロックリードはしない。１ワードのみのリードをしてきて、直接ＣＰＵ３０２に返す（図３５における処理（９−２）、図２２におけるステップＳ４０１、Ｓ４０４〜Ｓ４０８）。
【０１２９】
キャッシュメモリ３１１の凍結ビットＦが“１”に設定されたＩＮＤＥＸアドレスに対するアクセスなのでＲＰＡＭ３１５は何もしない。
【０１３０】
ＰＦＡＢ３２２の内容がクリアされているが、ＲＰＡＭ３１５の最大カウント値になっているデータがないので、ＰＦＡＢ３２２への登録はしない（図２４におけるステップＳ４３１、Ｓ４３２、４３３）。
【０１３１】
キャッシュミスなのでプリフェッチはしない。
【０１３２】
≪アクセス例（１０）≫
＜図３６：“０ｘ００００＿００００”：キャッシュヒット＞
図３６に示されるように、アクセス例（１０）のフェッチは“０ｘ００００＿００００”（１６進表記）であり、フェッチアドレスは“００００＿０００” （１６進表記）である。フェッチ“０ｘ００００＿００００”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。
【０１３３】
この場合の判定結果はキャッシュヒットなのれＲＰＡＭ３１５は何も処理を行わない。
【０１３４】
ＰＦＡＢ３２２がクリアされているが、ＲＰＡＭ３１５の最大カウント値になっているデータがないので、ＰＦＡＢ３２２への登録はしない（図２４におけるステップＳ４３１、Ｓ４３２、Ｓ４３３）。
【０１３５】
キャッシュヒットなので、ＰＦＡＢ３２２に登録されているアドレスが有効であることを確認する。ビットＡＶは“０”であり、有効部ットＡＶは有効でないので、プリフェッチは行わない（図２３におけるステップＳ４２１）。
【０１３６】
≪アクセス例（１１）≫
＜図３７：“０ｘ０００４＿００４０”：キャッシュヒット＞
図３７に示されるように、アクセス例（１１）のフェッチは“０ｘ０００４＿００４０”（１６進表記）であり、フェッチアドレスは“０００４＿００４” （１６進表記）である。フェッチ“０ｘ０００４＿００４０”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。
【０１３７】
この場合の判定結果はキャッシュヒットであるので、ＲＰＡＭ３１５は何も処理を行わない。
【０１３８】
ＰＦＡＢ３２２がクリアされているが、ＲＰＡＭ３１５の最大カウント値になっているデータがないので、ＰＦＡＢ３２２への登録はしない（図２４におけるステップＳ４３１，Ｓ４３２，Ｓ４３３）。
【０１３９】
キャッシュヒットなので、ＰＦＡＢ３２２に登録されているアドレスが有効であることを確認する。有効ではないので、プリフェッチは行わない。（図２３におけるステップＳ４２１）
【０１４０】
≪アクセス例（１２）≫
＜図３８：“０ｘ０００５＿００５０”：キャッシュヒット＞
図３８に示されるように、アクセス例（１２）のフェッチは“０ｘ０００５＿００５０”（１６進表記）であり、フェッチアドレスは“０００５＿００５” （１６進表記）である。フェッチ“０ｘ０００５＿００５０”が実行されたキャッシュ回路３００においては、キャッシュ／凍結制御部３１６によりフェッチアドレスに対するヒット判定が実行される。
【０１４１】
この場合の判定結果はキャッシュヒットであるので、ＲＰＡＭ３１５は何も処理を行わない。
【０１４２】
ＰＦＡＢ３２２がクリアされているが、ＲＰＡＭ３１５の最大カウント値になっているデータがないので、ＰＦＡＢ３２２への登録はしない（図２４におけるステップＳ４３１、Ｓ４３２、Ｓ４３３）。
【０１４３】
キャッシュヒットなので、ＰＦＡＢ３２２に登録されているアドレスが有効であることを確認する。有効ではないので、プリフェッチは行わない。（図２３におけるステップＳ４２１）
【０１４４】
以上のアクセス例（１）〜（１２）について、第３の実施形態の制御を適用した場合と、適用しない比較例（従来例）とを比較すると、以下の表６のようになる。なお、参考のために、第１の実施形態との比較結果をも示す。
【表６】
0004266605.tif 000007
【０１４５】
表６に示されるように、比較例におけるキャッシュヒット率は０．０８３であるが、第３の実施形態によるキャッシュヒット率は０．３３３であり、キャッシュヒット率が向上している。なお、同じアクセス例に対する第１の実施形態によるキャッシュヒット率は０．２５である。
【０１４６】
以上説明したように、第３の実施形態に係るキャッシュ回路３００においては、頻繁に参照されるデータをキャッシュメモリ３１１に登録しておき、１度のみしか参照されないようなデータは、キャッシュミス時であってもリプレースを行わないアルゴリズムを採用している。このようにしてキャッシュメモリ３１１におけるブロック置換の回数の低減（即ち、キャッシュヒット率の向上）を図り、結果的にＣＰＵの処理速度の向上を図っている。より具体的に言えば、ブロック置換によってキャッシュメモリ３１１から追い出されたデータのアドレス情報をＲＰＡＭ３１５に登録しておき、ある一定数以上（第３の実施形態においては１回）のキャッシュ登録が確認された場合に、キャッシュメモリ３１１のラインを凍結して、置換の対象外としている。
【０１４７】
さらに、第３の実施形態に係るキャッシュ回路３００においては、ＲＰＡＭ３１５の登録データの内、カウンタ値Ｒ１が最大になっているアドレスをＰＦＡＢ３２２に登録しておき、ＣＰＵ３０２の外部バスアクセス要求がない場合又はキャッシュヒットしている場合においては、このアドレスを元に外部バス経由でプリフェッチを行い、ＰＦＢ３２４に登録しておく。ＰＦＢ３２４に登録されたデータは、次のＣＰＵ３０２のアクセス要求がないとき又はキャッシュミス時にキャッシュメモリ３１１に登録する。このように、キャッシュミスが起きてから初めてフェッチしたキャッシュ制御方法ではなく、外部バスアクセスがない時にプリフェッチしておくことにより、キャッシュヒット率のより一層の改善を図ることができ、参照頻度の高いデータをキャッシュメモリ３１１に留めておくことが可能となり、結果としてキャッシュヒット率が向上し、システム性能の改善が達成できる。
【０１４８】
なお、上記説明においては、ダイレクトマップ方式のキャッシュメモリ３１１について説明したが、本発明は、２ウェイ以上のセットアソシアティブ方式のキャッシュメモリ等の他のメモリにも適用可能である。
【０１４９】
第４の実施形態
図３９は、本発明の第４の実施形態に係るキャッシュ回路の動作を示すフローチャートである。第４の実施形態に係るキャッシュ回路は、ＲＰＡＭ３１５のカウンタ値Ｒ１のビット数ｎが２以上である（図２２はカウンタ値Ｒ１のビット数ｎが１の場合を示す。）点が第３の実施形態に係るキャッシュ回路と相異する。また、図３９に示されるように、第４の実施形態に係るキャッシュ回路の動作は、ＲＰＡＭ３１５のカウンタ値Ｒ１が最大値（２以上）に達したときにキャッシュメモリ３１１内の該当するエントリの凍結ビットＦを“１”に設定する点が、ＲＰＡＭ３１５のカウンタ値Ｒ１が１であるときにキャッシュメモリ３１１内の該当するエントリの凍結ビットＦを“１”に設定する上記第３の実施形態に係るキャッシュ回路の動作と相異する。したがって、第４の実施形態に係るキャッシュ回路の説明においては、図２０をも参照する。
【０１５０】
上記構成を有する第４の実施形態に係るキャッシュ回路は、以下のように動作する。
▲１▼キャッシュミス時に、キャッシュメモリ３１１から追い出されたデータのアドレス情報がＲＰＡＭ３１５に未登録であれば、キャッシュメモリ３１１から追い出されたデータのアドレス情報をＲＰＡＭ３１５に登録し、アドレス情報はカウンタ値＝１という情報を含む。
▲２▼キャッシュミス時に、キャッシュメモリ３１１に書き込まれたデータのアドレス情報がＲＰＡＭ３１５に登録されていれば、キャッシュメモリ３１１から追い出されたデータのアドレス情報に含まれるカウンタ値が所定の最大値であるか否かを判断し、所定の最大値より小さければカウンタ値を１だけ増加させ、所定の最大値であればキャッシュメモリ３１１に書き込まれたデータを置換対象外のデータに設定し、この置換対象外に設定されたデータのアドレス情報をＲＰＡＭ３１５から削除する。
▲３▼ＣＰＵ３０２からのメモリアクセス要求が無いときに、ＰＦＢ３２４内に有効なデータが無ければ、ＰＦＡＢ３２２に登録されたアドレス情報を持つラインのデータをメインメモリ３０１からフェッチしてＰＦＢ３２４内に登録する。
▲４▼ＰＦＢ３２４内に有効なデータが有れば、ＰＦＢ３２４内のデータをキャッシュメモリ３１１に登録する。
▲５▼ＣＰＵ３０２からのメモリアクセス要求が有り、アクセス結果がキャッシュヒットであるときに、ＰＦＢ３２４内に有効なデータが無ければ、ＰＦＡＢ３２２に登録されたアドレス情報を持つラインのデータをメインメモリ３０１からフェッチしてＰＦＢ３２４内に登録する。
【０１５１】
以下に、図２０及び図３９に基づいて、第４の実施形態に係るキャッシュ回路の動作（即ち、キャッシュ制御方法）を説明する。
【０１５２】
図３９に示されるように、ＣＰＵ５０１からメモリアクセス要求がなければ（ステップＳ５０１におけるＮＯ）、ＰＦＢ３２４に有効なデータ（有効ビットＰＶが“１”であるデータ）があるか否かを判断する（ステップＳ５０２）。ＰＦＢ３２４に有効なデータがあれば（ステップＳ５０２におけるＹＥＳ）、ＰＦＢ３２４内のデータをキャッシュメモリ３１１に登録し、キャッシュメモリ３１１の凍結ビットＦ及び有効ビットＶを“１”に設定し、ＰＦＡＢ３２２の内容を全てクリアする（ステップＳ５０３）。また、ＰＦＢ３２４に有効なデータがない場合には（ステップＳ５０２におけるＮＯ）、プリフェッチ・データをＰＦＢ３２４に登録し、さらにキャッシュメモリ３１１に登録するための処理であるプリフェッチ・アクセス・フロー（図２３のＰＦ  ＦＬＯＷ）に移行する。
【０１５３】
また、ＣＰＵ３０２からのメモリアクセス要求があり（ステップＳ５０１におけるＹＥＳ）、キャッシュヒットした場合には、プリフェッチ・データをＰＦＢ３２４に登録し、さらにキャッシュメモリ３１１に登録するための処理であるプリフェッチ・アクセス・フロー（図２３のＰＦ  ＦＬＯＷ）に移行する。
【０１５４】
また、ＣＰＵ３０２からのメモリアクセス要求があり（ステップＳ５０１におけるＹＥＳ）、キャッシュミスした場合には（ステップＳ５０２におけるＮＯ）、ＰＦＢ３２４に有効なデータ（即ち、有効ビットＰＶが“１”であるデータ）があるか否かを判断する（ステップＳ５０５）。ＰＦＢ３２４に有効なデータがあれば（ステップＳ５０５におけるＹＥＳ）、ＰＦＢ３２４内のデータをキャッシュメモリ３１１に登録し、凍結ビットＦ及び有効ビットＶを“１”に設定し、ＰＦＡＢ３２２の内容を全てクリアする（ステップＳ５０６）。
【０１５５】
ＰＦＢ３２４に有効なデータがない場合（ステップＳ５０５におけるＮＯ）、又は、ＰＦＢ３２４内のデータをキャッシュメモリ３１１に登録し、ＰＦＡＢ３２２の内容を全てクリアした後に（ステップＳ５０６の後に）、キャッシュメモリ３１１内の置換対象エントリの凍結ビットＦが“１”であれば（ステップＳ５０７におけるＹＥＳ）、キャッシュメモリ３１１におけるブロック置換は実行せず、キャッシュミスした１ワードデータのみをＣＰＵ３０２に返送する（ステップＳ５０８）。一方、置換対象エントリの凍結ビットＦが“０”であれば（ステップＳ５０７におけるＮＯ）、置換対象エントリの有効ビットＶが有効を示す“１”であるか否かを判定する（ステップＳ５０９）。
【０１５６】
置換対象エントリの有効ビットＶが無効を示す“０”であれば（ステップＳ５０９におけるＮＯ）、キャッシュメモリ３１１の当該エントリ（有効ビットＶが“０”であるエントリ）にＰＦＢ３２４内データを初登録する（ステップＳ５１０）。置換対象エントリの有効ビットＶが有効を示す“１”であれば（ステップＳ５０９におけるＹＥＳ）、キャッシュメモリ３１１の置換対象エントリからデータを追い出し、メインメモリ３０１内データを書き込む（ステップＳ５１１）。
【０１５７】
次に、キャッシュメモリ３１１に書き込まれたデータのアドレス情報がＲＰＡＭ３１５にある（即ち、登録済み）か否かを判断する（ステップＳ５１２）。キャッシュメモリ３１１に書き込まれたデータのアドレス情報がＲＰＡＭ３１５に無い場合には（ステップＳ５１２におけるＮＯ）、キャッシュメモリ３１１から追い出されたデータのアドレス情報を登録する空きエントリがＲＰＡＭ３１５にあるか否かを判断する（ステップＳ５１３）。ここで、ＲＰＡＭ３１５に空きエントリがあれば（ステップＳ５１３におけるＹＥＳ）、このＲＰＡＭ３１５の空きエントリに、キャッシュメモリ３１１から追い出されたデータのアドレス情報（即ち、アドレスとカウンタ値Ｒ１＝１）を登録する（ステップＳ５１５）。一方、キャッシュメモリ３１１から追い出されたデータのアドレス情報を登録する空きエントリがＲＰＡＭ３１５に無ければ（ステップＳ５１３におけるＮＯ）、ＲＰＡＭ３１５内の乱数により決定されたエントリに、キャッシュメモリ３１１から追い出されたデータのアドレス情報（即ち、アドレスとカウンタ値Ｒ１＝１）を登録（上書き）する（ステップＳ５１４）。
【０１５８】
また、ステップＳ５１２において、キャッシュメモリ３１１に書き込まれたデータのアドレス情報がＲＰＡＭ３１５に登録されていれば（ステップＳ５１２におけるＹＥＳ）、キャッシュメモリ３１１から追い出されたデータのアドレス情報に含まれるカウンタ値Ｒ１が所定の最大値であるか否かを判断し（ステップＳ５１６）、所定の最大値より小さければカウンタ値を１だけ増加させる（ステップＳ５１７）。ステップＳ５１６において、カウンタ値が所定の最大値であればキャッシュメモリ３１１に書き込まれたデータの凍結ビットＦを“１”に設定し（ステップＳ５１８）、このラインのデータを置換対象外のデータに設定し、凍結ビットＦが“１”に設定されたエントリのＩＮＤＥＸ部と同じＩＮＤＥＸ部のＲＰＡＭ３１５内のエントリの内容をクリアし、また、ＰＦＡＢ３２２内エントリがあれば、クリアする（ステップＳ５１９）。
【０１５９】
以上説明したように、第４の実施形態に係るキャッシュ回路においては、頻繁に参照されるデータをキャッシュメモリ３１１に登録しておき、１度のみしか参照されないようなデータは、キャッシュミスしてもリプレースを行わないアルゴリズムを採用している。このようにすることによってキャッシュメモリ３１１におけるブロック置換の回数を低減（即ち、キャッシュヒット率の向上）を図り、結果的にＣＰＵの処理速度の向上を図っている。具体的に言えば、ブロック置換によってキャッシュメモリ３１１から追い出されたデータのアドレス情報をＲＰＡＭ１５に登録しておき、ある一定数以上のキャッシュ登録が確認された場合に、このラインを凍結し、置換の対象外としている。このようにすることで、参照頻度の高いデータをキャッシュに留めることが可能となり、結果としてキャッシュヒット率が向上し、システム性能の改善が達成できる。
【０１６０】
また、第４の実施形態に係るキャッシュ回路３００においては、ＲＰＡＭ３１５の登録データの内、カウンタ値Ｒ１が最大になっているアドレスをＰＦＡＢ３２２に登録しておき、ＣＰＵ３０２の外部バスアクセス要求がない場合又はキャッシュヒットしている場合においては、このアドレスを元に外部バス経由でプリフェッチを行い、ＰＦＢ３２４に登録しておく。ＰＦＢ３２４に登録されたデータは、次のＣＰＵ３０２のアクセス要求がないとき又はキャッシュミス時にキャッシュメモリ３１１に登録する。このように、キャッシュミスが起きてから初めてフェッチしたキャッシュ制御方法ではなく、外部バスアクセスがない時にプリフェッチしておくことにより、キャッシュヒット率のより一層の改善を図ることができ、参照頻度の高いデータをキャッシュメモリ３１１に留めておくことが可能となり、結果としてキャッシュヒット率が向上し、システム性能の改善が達成できる。なお、第４の実施形態において、上記以外の点は、上記第３の実施形態と同じである。
【０１６１】
第５の実施形態
図４０は、本発明の第５の実施形態に係るキャッシュ回路６００の構成を概略的に示すブロック図である。また、図４０において、６０１は、プログラムやデータが格納されるメインメモリ、６０２は、キャッシュメモリ６１１を経由してメインメモリ６０１とアクセスを行うＣＰＵ、６０３は、データバス、６０４は、アドレスバスを示す。
【０１６２】
図４０に示されるように、第５の実施形態に係るキャッシュ回路６００は、キャッシュメモリ６１１と、ワード選択回路６１２と、ＣＰＵデータ入力選択用ＭＵＸ６１３と、リプレース・データ・バッファ６１４と、リプレース・アドレス／データ・メモリ（ＲＰＡＤＭ）６１５と、ワード選択回路６１６と、キャッシュ／凍結制御部（キャッシュ制御手段）６１７と、データ方向切替制御部６２３とを有する。
【０１６３】
第５の実施形態においては、ＣＰＵ６０２のアドレス幅は３２ビットである。ＣＰＵ６０２のアドレス幅は、キャッシュメモリ６１１の容量及びリードブロックサイズに基づいて決定される。ＣＰＵアドレスは、タグデータ部（ＴＡＧ部）と、インデックスデータ部（インデックス（ＩＮＤＥＸ）部）と、ワードオフセット（Word Offset）と、バイトオフセット（Byte Offset）とから構成される。ＣＰＵアドレスにおいては、ＴＡＧ部を１６ビット、ＩＮＤＥＸ部を１２ビット、ワードオフセットを２ビット、バイトオフセットを２ビットとしている。例えば、リードブロックサイズが４ワードであり、キャッシュ容量が６４ＫＢである場合には、ＩＮＤＥＸ部は１２ビットとなり、ＴＡＧ部は１６ビットとなり、キャッシュメモリ３１１のエントリ数は４０９６となる。なお、以上の数値例は例示に過ぎず、他の値を採用することができる。
【０１６４】
キャッシュメモリ６１１は、メインメモリ６０１内データのコピーを格納することができる。ＣＰＵ６０２は、キャッシュメモリ６１１を経由して、メインメモリ６０１とアクセスを行う。キャッシュメモリ６１１は、ＣＰＵ６０２から見たメインメモリ６０１の見かけ上の処理速度を高めるために、メインメモリ６０１内データの一部のコピーを一時的に格納する。図４０に示されるキャッシュメモリ６１１は、ダイレクトマップ方式のメモリである。キャッシュメモリ６１１の１ライン（又は１ブロック）は、タグデータ部（ＴＡＧ部）、有効ビットＶ、４ワード（Ｗｏｒｄ１〜４）分のデータ（ＤＡＴＡ）から構成されている。キャッシュメモリ６１１内のＴＡＧ部、及び有効ビットＶを記憶する領域は、タグＲＡＭ（ＴＡＧＭ）であり、キャッシュメモリ６１１内のデータ（ＤＡＴＡ）を記憶する領域をデータＲＡＭ（ＤＡＴＡ部）である。なお、キャッシュメモリ６１１として、２ウェイ以上のセットアソシアティブ方式のメモリ等を採用することもできる。
【０１６５】
ワード選択回路６１２は、キャッシュメモリ６１１に格納された複数個（例えば、４個）のワードデータのいずれかを選択して出力する。ワード選択回路６１２は、ＣＰＵ６０１が要求するアドレスのワードオフセットにより制御される。
【０１６６】
リプレース・データ・バッファ６１４は、キャッシュメモリ６１１から追い出されたデータを一時的に保持する。また、ＲＰＡＤＭ６１５は、キャッシュメモリ６１１から追い出されたデータを、リプレース・データ・バッファ６１４を経由して受け取り、キャッシュメモリ６１１から追い出されたデータのアドレス情報及びデータを保持する。ワード選択回路６１６は、ＲＰＡＤＭ６１５に格納された複数個（例えば、４個）のデータのいずれかを選択して出力する。ワード選択回路６１６は、ＣＰＵ６０１が要求するアドレスのワードオフセットにより制御される。
【０１６７】
ＣＰＵデータ入力選択用ＭＵＸ６１３は、キャッシュヒット時のデータ（ワード選択回路６１２からのデータ）と、ＲＰＡＤＭ６１５のヒット時のデータ（ワード選択回路６１６からのデータ）と、キャッシュミス時のデータ（データ方向切替制御部６２３からのデータ）のいずれかを選択してＣＰＵ６０２へ返す。ＣＰＵデータ入力選択ＭＵＸ６１３は、キャッシュ／凍結制御部６１７により制御される。
【０１６８】
ＲＰＡＤＭ６１５は、キャッシュミス時にキャッシュメモリ６１１から追い出された（即ち、上書きにより削除された）データのアドレス情報及びデータを記憶する。
【０１６９】
キャッシュ／凍結制御部６１７は、ＣＰＵ６０２からのアクセス（ＣＰＵ６０２による読み込み動作、即ち、フェッチ）結果がキャッシュヒットであるかキャッシュミスであるかを判定する。また、キャッシュ／凍結制御部６１７は、キャッシュメモリ６１１及びＲＰＡＤＭ６１５の制御を行う。
【０１７０】
キャッシュミス時にキャッシュメモリ６１１から追い出されたデータは、ＲＰＡＤＭ６１５に保持され、キャッシュ／凍結制御部６１７によるヒット判定は、キャッシュメモリ６１１内のアドレス情報及びＲＰＡＤＭ６１５内のアドレス情報について行われる。このため、キャッシュメモリ６１１からデータが追い出された直後に同一アドレスへのアクセスがあった場合には、外部から再度リードすることなくＲＰＡＤＭ６１５内からデータを即座にＣＰＵ６０２に返送可能である。また、ＲＰＡＤＭ６１５内におけるラインの参照回数が規定値を超えた場合に、このラインを凍結するための凍結ビットＦを備えている。これにより参照頻度の高いデータを保持することができる。
【０１７１】
図４１は、ｍアドレスのＲＰＡＤＭ６１５のメモリ構成例（初期状態）を示す説明図である。また、図４２は、本発明の第５の実施形態に係るキャッシュ回路６００の動作を示すフローチャートである。図４２に基づいて、第５の実施形態に係るキャッシュ回路６００の動作（即ち、キャッシュ制御方法）を説明する。
【０１７２】
図４２に示されるように、ＣＰＵ６０１からのアクセス要求アドレスから、キャッシュメモリ６１１のキャッシュヒット判定、及び、ＲＰＡＤＭ６１５におけるヒット判定を行う（ステップＳ７０１）。いずれかの判定において、ヒットした場合は、ヒットしたメモリからデータを取り出しＣＰＵ６０２へ返す。
【０１７３】
キャッシュミスした場合には（Ｓ７０１におけるＮＯ）、外部メモリ（メインメモリ６０１）にリード・アドレスを出力し、外部メモリからデータを取り込む（ステップＳ７０２）。
【０１７４】
次に、置換対象エントリの有効ビットＶが“１”であるか“０”であるかを判断し、“０”であれば（ステップＳ７０３におけるＮＯ）、外部メモリから取り込んだデータを、キャッシュメモリ６１１に初登録する（ステップＳ７０４）。
【０１７５】
置換対象エントリの有効ビットＶが“１”であれば（ステップＳ７０３におけるＹＥＳ）、置換対象データをリプレース・データ・バッファ６１４に登録した後に、キャッシュメモリ６１１の有効ビットＶを“１”にして、キャッシュメモリ６１１に外部メモリからのデータとタグを登録する。
【０１７６】
次に、リプレース・データ・バッファ６１４に登録されたデータのアドレス情報（即ち、リプレース・アドレス情報）ＴＡＧ＿ＩＮＤＥＸが、ＲＰＡＤＭ６１５に有るか否かを判断する（ステップＳ７０６）。
【０１７７】
リプレース・アドレス情報がＲＰＡＤＭ６１５に無い場合には（ステップＳ７０６におけるＮＯ）、ＲＰＡＤＭ６１５にリプレースされるアドレス情報を登録する空きエントリがあるかを判断する（ステップＳ７０７）。
【０１７８】
空きエントリが無ければ（ステップＳ７０７におけるＮＯ）、ＲＰＡＤＭ６１５において凍結ビットＦが“１”に設定されていないラインにおいて、乱数により決定されたエントリに、カウンタ値をインクリメントた上で、リプレースデータを登録する。全てのラインについて凍結ビットＦが“１”に設定されていた場合には、全てのラインの中から乱数により決定されたエントリに、リプレースデータを登録する。
【０１７９】
ステップＳ７０７において、空きエントリがあれば（ステップＳ７０７におけるＹＥＳ）、ＲＰＡＤＭ６１５の空きエントリのカウンタ値をインクリメントして、リプレースアドレス及びリプレースデータを登録する（ステップＳ７０９）。
【０１８０】
ステップＳ７０６において、リプレース・アドレス情報がＲＰＡＤＭ６１５に有れば（ステップＳ７０６におけるＹＥＳ）、ＲＰＡＤＭ６１５のカウンタ値が最大値に設定されているかを判断する（ステップＳ７１０）。最大値でなければ（ステップＳ７１０におけるＮＯ）、ＲＰＡＤＭのカウンタをインクリメントした値を登録する。最大値であれば（ステップＳ７１０におけるＹＥＳ）、ＲＰＡＤＭ６１５の凍結ビットＦを“１”に設定する。即ち、このデータは参照頻度が高いので、ＲＰＡＤＭ６１５において凍結しておく。
【０１８１】
第５の実施形態によれば、ＲＰＡＤＭ６１５をデータを格納できるように構成し、キャッシュメモリ６１１から追い出されたデータを一時的に保持し、ＲＰＡＤＭ６１５もヒット判定（ステップＳ７０１）の対象とすることで、追い出された直後に同一アドレスへのアクセスがあった場合には、外部から再度リードすることなくＲＰＡＤＭ６１５内からデータを即座に返送可能なように構成した。また、ＲＰＡＤＭ６１５内におけるラインの参照回数が規定値を超えた場合に、このラインを凍結することで、より参照頻度の高いデータを保持するようにし、システムの性能を上げるようにしている。
【０１８２】
【発明の効果】
以上説明したように、請求項１、２、５から１０までのキャッシュ回路によれば、キャッシュミス時に、キャッシュメモリから追い出されたデータのアドレス情報がＲＰＡＭに未登録であれば、キャッシュメモリから追い出されたデータのアドレス情報をＲＰＡＭに登録し、キャッシュミス時に、キャッシュメモリに書き込まれたデータのアドレス情報がＲＰＡＭに登録されていれば、キャッシュメモリに書き込まれたデータを置換対象外のデータに設定し、この置換対象外に設定されたデータのアドレス情報をＲＰＡＭから削除する。このように、２度以上のアクセスがあったデータをキャッシュメモリから削除されないようにすることができ、結果的に、キャッシュヒット率を向上させ、ＣＰＵのアクセス速度を向上させることができる。
【０１８３】
また、請求項３から１０までのキャッシュ回路によれば、キャッシュミス時に、キャッシュメモリから追い出されたデータのアドレス情報がＲＰＡＭに未登録であれば、キャッシュメモリから追い出されたデータのアドレス情報をＲＰＡＭに登録し、アドレス情報はカウンタ値＝１という情報を含む。さらに、キャッシュミス時に、キャッシュメモリに書き込まれたデータのアドレス情報がＲＰＡＭに登録されていれば、キャッシュメモリから追い出されたデータのアドレス情報に含まれるカウンタ値が所定の最大値であるか否かを判断し、所定の最大値より小さければカウンタ値を１だけ増加させ、所定の最大値であればキャッシュメモリに書き込まれたデータを置換対象外のデータに設定し、この置換対象外に設定されたデータのアドレス情報をＲＰＡＭから削除する。このように、一定数以上のアクセスがあったデータをキャッシュメモリから削除されないようにすることにより、結果的に、キャッシュヒット率を向上させ、ＣＰＵのアクセス速度を向上させることができる。
【０１８４】
また、請求項２、４から１０までのキャッシュ回路によれば、ＲＰＡＭの登録データのアドレスをＰＦＡＢに登録することができ、このアドレスを元にプリフェッチを行い、データをキャッシュメモリに登録しておくので、キャッシュミスが起きてから初めてフェッチを開始するキャッシュ回路よりも、キャッシュヒット率のより一層の改善を図ることができ、ＣＰＵのアクセス速度を向上させることができる。
【図面の簡単な説明】
【図１】  本発明の第１の実施形態に係るキャッシュ回路の構成を概略的に示すブロック図である。
【図２】  図１のＲＰＡＭ及び凍結制御回路の構成を示す図である。
【図３】  カウンタ値Ｒ１のビット数ｎが１である場合のＲＰＡＭのコンテンツ部の構成例（初期状態）を示す図である。
【図４】  第１の実施形態に係るキャッシュ回路の動作（キャッシュ制御方法）を示すフローチャートである。
【図５】  キャッシュメモリの構成例（１６進表記）を示す図である。
【図６】  図５のキャッシュメモリに対するアクセスパターン（１６進表記）を示す図である。
【図７】  ＲＰＡＭのＴＡＧ部及びＩＮＤＥＸ部の２進表記と１６進表記の対応を示す図である。
【図８】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（１）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図９】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（２）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１０】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（３）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１１】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（３）であるときのＲＰＡＭにおけるクリア処理後（１６進表記）を示す図である。
【図１２】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（４）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１３】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（５）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１４】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（６）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１５】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（７）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１６】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（８）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１７】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（９）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１８】  第１の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図６のアクセス例（１０）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図１９】  本発明の第２の実施形態に係るキャッシュ回路の動作（キャッシュ制御方法）を示すフローチャートである。
【図２０】  本発明の第３の実施形態に係るキャッシュ回路の構成を概略的に示すブロック図である。
【図２１】  図２０のＲＰＡＭ及びキャッシュ／凍結制御部の構成を示す図である。
【図２２】  第３の実施形態に係るキャッシュ回路の動作（キャッシュ制御方法）を示すフローチャートである。
【図２３】  第３の実施形態においてプリフェッチ・データをＰＦＢに登録し、さらにキャッシュメモリに登録する処理（プリフェッチ・アクセス）を示すフローチャートである。
【図２４】  第３の実施形態においてＰＦＡＢにアドレスを登録する処理を示すフローチャートである。
【図２５】  第３の実施形態におけるキャッシュメモリの構成例（１６進表記）を示す図である。
【図２６】  第３の実施形態におけるキャッシュメモリに対するアクセスパターン（１６進表記）を示す図である。
【図２７】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（１）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図２８】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（２）であるときのＲＰＡＭ及びキャッシュメモリ内ＴＡＧＭの設定例（１６進表記）を示す図である。
【図２９】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（３）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、及びＰＦＡＢの設定例（１６進表記）を示す図である。
【図３０】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（４）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、及びＰＦＡＢの設定例（１６進表記）を示す図である。
【図３１】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（５）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、及びＰＦＡＢの設定例（１６進表記）を示す図である。
【図３２】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（６）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、及びＰＦＡＢの設定例（１６進表記）を示す図である。
【図３３】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（７）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、ＰＦＡＢ、及びＰＦＢの設定例（１６進表記）を示す図である。
【図３４】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（８）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、ＰＦＡＢ、及びＰＦＢの設定例（１６進表記）を示す図である。
【図３５】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（９）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、ＰＦＡＢ、及びＰＦＢの設定例（１６進表記）を示す図である。
【図３６】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（１０）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、及びＰＦＡＢの設定例（１６進表記）を示す図である。
【図３７】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（１１）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、及びＰＦＡＢの設定例（１６進表記）を示す図である。
【図３８】  第３の実施形態に係るキャッシュ回路においてアクセス対象アドレスが図２６のアクセス例（１２）であるときのＲＰＡＭ、キャッシュメモリ内ＴＡＧＭ、及びＰＦＡＢの設定例（１６進表記）を示す図である。
【図３９】  本発明の第４の実施形態に係るキャッシュ回路の動作（キャッシュ制御方法）を示すフローチャートである。
【図４０】  本発明の第５の実施形態に係るキャッシュ回路の構成を概略的に示すブロック図である。
【図４１】  第５の実施形態におけるリプレース・アドレス／データ・メモリ（ＲＰＡＤＭ）のコンテンツ部の構成例（初期状態）を示す図である。
【図４２】  第５の実施形態に係るキャッシュ回路の動作（キャッシュ制御方法）を示すフローチャートである。
【符号の説明】
１１  キャッシュメモリ
１１Ｔ  キャッシュメモリのＴＡＧ部
１１ＴＭ  キャッシュメモリのＴＡＧＭ
１１ＤＭ  キャッシュメモリのＤＡＴＡ部
１１Ｅ  キャッシュメモリのエントリ
１２  ワード選択回路
１３  トライステートバッファ
１４  ヒット判定回路
１５  リプレース・アドレス・メモリ（ＲＰＡＭ）
１５Ｔ  ＲＰＡＭのＴＡＧ部
１５Ｉ  ＲＰＡＭのＩＮＤＥＸ部
１５Ｅ  ＲＰＡＭのエントリ
Ｒ１  ＲＰＡＭのカウンタ値
１６  凍結制御回路
２１  ＣＰＵアドレス
２１Ｔ  ＣＰＵアドレスのＴＡＧ部
２１Ｉ  ＣＰＵアドレスのＩＮＤＥＸ部
２２  有効ビットクリア指示レジスタ
２３  凍結ビットクリア指示レジスタ
３００  キャッシュ回路
３０１  メインメモリ
３０２  ＣＰＵ
３０３  データバス
３０４  アドレスバス
３１１  キャッシュメモリ
３１２  ワード選択回路
３１３  ＣＰＵデータ入力選択用ＭＵＸ
３１５  リプレース・アドレス・メモリ（ＲＰＡＭ）
３１６  キャッシュ／凍結制御部
３２１  アドレス選択用ＭＵＸ
３２２  プリフェッチ・アドレス・バッファ（ＰＦＡＢ）
３２３  データ方向切替制御部
３２４  プリフェッチ・バッファ（ＰＦＢ）
３２５  キャッシュ登録データ用ＭＵＸ
６００  キャッシュ回路
６０１  メインメモリ
６０２  ＣＰＵ
６０３  データバス
６０４  アドレスバス
６１１  キャッシュメモリ
６１２  ワード選択回路
６１３  ＣＰＵデータ入力選択用ＭＵＸ
６１４  リプレース・データ・バッファ
６１５  リプレース・アドレス／データ・メモリ（ＲＰＡＤＭ）
６１６  ワード選択回路
６１７  キャッシュ／凍結制御部
６２３  データ方向切替制御部
Ｖ  キャッシュメモリ又はＲＰＡＤＭの有効ビット
Ｆ  キャッシュメモリ又はＲＰＡＤＭの凍結ビット
ＡＶ  ＰＦＡＢの有効ビット
ＰＶ  ＰＦＢの有効ビット
【図１】
0004266605.tif 000008
【図２】
0004266605.tif 000009
【図３】
0004266605.tif 000010
【図４】
0004266605.tif 000011
【図５】
0004266605.tif 000012
【図６】
0004266605.tif 000013
【図７】
0004266605.tif 000014
【図８】
0004266605.tif 000015
【図９】
0004266605.tif 000016
【図１０】
0004266605.tif 000017
【図１１】
0004266605.tif 000018
【図１２】
0004266605.tif 000019
【図１３】
0004266605.tif 000020
【図１４】
0004266605.tif 000021
【図１５】
0004266605.tif 000022
【図１６】
0004266605.tif 000023
【図１７】
0004266605.tif 000024
【図１８】
0004266605.tif 000025
【図１９】
0004266605.tif 000026
【図２０】
0004266605.tif 000027
【図２１】
0004266605.tif 000028
【図２２】
0004266605.tif 000029
【図２３】
0004266605.tif 000030
【図２４】
0004266605.tif 000031
【図２５】
0004266605.tif 000032
【図２６】
0004266605.tif 000033
【図２７】
0004266605.tif 000034
【図２８】
0004266605.tif 000035
【図２９】
0004266605.tif 000036
【図３０】
0004266605.tif 000037
【図３１】
0004266605.tif 000038
【図３２】
0004266605.tif 000039
【図３３】
0004266605.tif 000040
【図３４】
0004266605.tif 000041
【図３５】
0004266605.tif 000042
【図３６】
0004266605.tif 000043
【図３７】
0004266605.tif 000044
【図３８】
0004266605.tif 000045
【図３９】
0004266605.tif 000046
【図４０】
0004266605.tif 000047
【図４１】
0004266605.tif 000048
【図４２】
0004266605.tif 000049