(57)【要約】【課題】キャッシュ・ミス発生時の主記憶装置へのアクセス回数を低減する。【解決手段】主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた主記憶装置の所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである主記憶装置の別の所定のアドレスを相互に関連付けて記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、主記憶装置の別の所定のアドレスと同一であるならば、別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとする。【選択図】図１
2014209392.tif 000002
【特許請求の範囲】
【請求項１】
主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである前記主記憶装置の別の所定のアドレスを相互に関連付けて自リプレースメントデータメモリ装置に記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、前記主記憶装置の前記別の所定のアドレスと同一であるならば、自リプレースメントデータメモリ装置に前記別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとするリプレースメントデータメモリ装置。
【請求項２】
請求項１に記載のリプレースメントデータメモリ装置であって、
リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータに対応していたアドレスである前記主記憶装置の別の所定のアドレスは、アクセス元から出力されたアドレスに含まれていたＣＬＩＮＥ、ＴＡＧ及びＣＳＥＬのうちの前記ＣＬＩＮＥ及び前記ＣＳＥＬに対応したアドレスであることを特徴とするリプレースメントデータメモリ装置。
【請求項３】
請求項２に記載のリプレースメントデータメモリ装置であって、
前記キャッシュメモリにおいて前記ＣＬＩＮＥにより指定されたラインに記憶されているＴＡＧが、アクセス元から出力された前記ＴＡＧと一致しない場合に、キャッシュミスが発生したと判断されることを特徴とするリプレースメントデータメモリ装置。
【請求項４】
請求項３に記載のリプレースメントデータメモリ装置であって、
リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータとは、前記キャッシュメモリにおいて前記ＣＬＩＮＥにより指定されたラインに記憶されていたデータのうちの、前記ＣＳＥＬにより選択されたデータであることを特徴とするリプレースメントデータメモリ装置。
【請求項５】
請求項１乃至４の何れか１に記載のリプレースメントデータメモリ装置であって、
前記主記憶装置の複数のアドレスに対して、自リプレースメントデータメモリ装置に記憶するべきデータが共通である場合、前記主記憶装置の複数のアドレスの間で共通なデータと、前記主記憶装置の複数のアドレスとを相互に関連付けて記憶する記憶手段と、
前記別のキャッシュミスに係る前記主記憶装置のアドレスが、前記記憶手段に記憶されている前記主記憶装置の複数のアドレスのうちの何れかのアドレスと一致した場合には、前記記憶手段に前記主記憶装置の複数のアドレスに関連付けて記憶されている前記共通なデータをロードデータとするロード手段と、
を備えることを特徴とするリプレースメントデータメモリ装置。
【請求項６】
請求項５に記載のリプレースメントデータメモリ装置であって、
前記記憶手段は、前記主記憶装置の複数のアドレスを関連づけて記憶するアバンドメントアドレスバッファと、前記主記憶装置の複数のアドレスのうちの１つのアドレスと前記共通なデータとを関連づけて記憶する第１のエントリとを備えることを特徴とするリプレースメントデータメモリ装置。
【請求項７】
請求項６に記載のリプレースメントデータメモリ装置であって、
前記ロード手段は、前記別のキャッシュミスに係る前記主記憶装置のアドレスが、前記記憶手段に記憶されている前記主記憶装置の複数のアドレスのうちの何れかと一致したか否かを、前記別のキャッシュミスに係る前記主記憶装置のアドレスが前記アバンドメントアドレスバッファに格納されている何れかのアドレスと一致するか否かを調べることにより検出することを特徴とするリプレースメントデータメモリ装置。
【請求項８】
請求項６又は７に記載のリプレースメントデータメモリ装置であって、
前記ロード手段は、前記別のキャッシュミスに係る前記主記憶装置のアドレスが、前記主記憶装置に記憶されている前記主記憶装置の複数のアドレスのうちの何れかと一致したならば、前記第１のエントリに記憶されている前記共通なデータをロードデータとすることを特徴とするリプレースメントデータメモリ装置。
【請求項９】
請求項１乃至８の何れか１項に記載のリプレースメントデータメモリ装置を含むことを特徴とする中央演算装置。
【請求項１０】
主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである前記主記憶装置の別の所定のアドレスを相互に関連付けてリプレースメントデータメモリ装置に記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、前記主記憶装置の前記別の所定のアドレスと同一であるならば、前記リプレースメントデータメモリ装置に前記別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとするリプレースメントデータ処理方法をコンピュータに行なわせるためのリプレースメントデータ処理用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ・ミス発生時にキャッシュメモリから追い出されたリプレースメントデータを記憶するリプレースメントデータメモリ装置及びこれを含む中央演算装置並びにリプレースメントデータ処理用プログラムに関する。
【背景技術】
【０００２】
主記憶装置として利用されるＤＲＡＭ(Dynamic Random Access Memory)は構造的に高速化しにくく、マイクロ・プロセッサが主記憶装置にアクセスすることで発生するレイテンシは、コンピュータ・システム性能を著しく抑制する。一方で、近年のマイクロ・プロセッサの多くは、キャッシュメモリの役割を果たすＳＲＡＭ(Static Random Access Memory)を内包しており、予め主記憶装置のデータの一部をキャッシュメモリに格納しておくことで、主記憶装置へのアクセス・レイテンシを短縮し、マイクロ・プロセッサの処理能力の向上が図られている。
【０００３】
前述のキャッシュメモリの特徴として、キャッシュ・ミスを起こしたときに、新しいデータをキャッシュブロックに格納する必要があるが、このとき、データを入れるべきキャッシュブロック上に更新されたデータが入っている場合、そのキャッシュブロック上のデータを主記憶装置に書き戻し、その後に新しいデータを格納する必要性が生じる。これをリプレースメントと呼ぶ。
【０００４】
リプレースメントが発生した際に、主記憶装置との間で行われるキャッシュブロックのリプレース方法としては、リプレース対象となる複数の連想度(WAY)を有するキャッシュブロックのうち最も古くに使用されたキャッシュブロックをリプレース対象として選択するＬＲＵ(Least Recently Used)方式や、最初にデータが格納されたキャッシュブロックを更新対象とするＦＩＦＯ(First In First Out)方式等がある。ＦＩＦＯは、プログラムの処理は逐次的に進められるという推測に基づいて、最も古く読み込んだキャッシュブロックを置き換える。一方ＬＲＵは、長い時間参照されていないキャッシュブロックは、近い将来にも参照される可能性が低いという推測に基づいて、最後に参照されてから最も長い時間が経過したキャッシュブロックを置き換える。リプレースメントした後に、キャッシュ・ミスを低減し、主記憶装置へのアクセスを回避するために、上述したアルゴリズムが多くのプロセッサで採用されている。
【０００５】
一方で、近年の研究、例えば非特許文献１によると、キャッシュ・ミスを引き起こすロード命令の多くは、プログラム実行中に一旦ストアされたデータをロードするものであることが複数のベンチマーク結果により報告されている。即ち、一旦はキャッシュメモリに格納した経験のあるデータが、後にキャッシュメモリからリプレースメントもしくは無効化されてしまい、必要とする時に該データがキャッシュメモリに存在しなかったことを意味する。
【０００６】
大抵のプログラムにはループ制御が多く含まれており、同じ命令列やデータは繰り返しアクセスされる可能性が高くなるために、ロード対象データを事前にストアする頻度は高くなると推測される。
【０００７】
また、特開平０９−１９０３８２号公報（特許文献１）、特開平０９−２８８６１６号公報（特許文献２）では、ダイレクト・マップ方式のキャッシュメモリで発生するスラッシングによる処理速度低下を改善するために、キャッシュメモリから追い出されるラインのアドレスを監視し、追い出されるアドレス、データをメモリまたはバッファに格納する手段が提示されている。
【０００８】
また、プロセッサによる主記憶装置に対するアクセス速度の向上のためにキャッシュメモリが設けられるが、キャッシュメモリだけではその向上が十分に図られない場合に、そのキャッシュメモリを一次キャッシュメモリとして、一次キャッシュメモリと主記憶装置との間に二次キャッシュメモリを設ける。
【０００９】
特開平１０−３０７７５２号公報（特許文献３）には、ダイレクトマップ方式の二次キャッシュメモリを用いたシステムにおいて、二次キャッシュメモリに類似したバッファメモリを用いて動作速度を速くする発明が記載されている。
【００１０】
特開２００３−２８８２６９号公報（特許文献４）には、キャッシュミス時に追い出されたデータのアドレス情報がリプレースアドレスメモリに未登録であれば、キャッシュメモリから追い出されたデータのアドレス情報をリプレースアドレスメモリに登録し、キャッシュミス時にキャッシュメモリに書き込まれたデータのアドレス情報がリプレースアドレスメモリに登録されていれば、キャッシュメモリに下記扱かれたデータをリプレースメント対象外のデータに設定し、そのリプレースメント対象外に設定されたデータのアドレス情報をリプレースアドレスメモリから削除する発明が記載されている。また、特開２００３−２８８２６９号公報（特許文献４）には、リプレースアドレスメモリに登録されているデータのアドレス情報が登録されるプリフェッチアドレスバッファと、プリフェッチアドレスバッファに登録されたアドレス情報のデータを登録できるプリフェッチバッファとを更に備え、ＣＰＵからのメモリアクセス要求がないときに、プリフェッチバッファに有効なデータがなければ、プリフェッチアドレスバッファに登録されたアドレス情報を持つラインのデータをメインメモリからフェッチしてプリフェッチバッファに登録し、プリフェッチバッファに有効なデータがあれば、プリフェッチバッファのデータをキャッシュメモリに登録する発明が記載されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開平０９−１９０３８２号公報
【特許文献２】特開平０９−２８８６１６号公報
【特許文献３】特開平１０−３０７７５２号公報
【特許文献４】特開２００３−２８８２６９号公報
【非特許文献】
【００１２】
【非特許文献１】三輪英樹、堂後靖博、井上弘士、村上和彰  著「キャッシュ・ミス頻発ロード命令の特徴解析」情報処理学会ＡＲＣ研究会、２００５年１１月
【発明の概要】
【発明が解決しようとする課題】
【００１３】
通常のキャッシュブロックのリプレースメントには以下のような問題点があった。即ち、上述したリプレース方法に基づいて動作するエントリ・リプレース手段では、プログラム実行中に一旦ストアされたデータが、後にキャッシュ・ミスを引き起こすロード対象データとなる場合、即ち、後に必要となるデータがキャッシュメモリに一旦格納されていたにも関わらず、その特定のリプレース・ルールに基づいてリプレースの対象となり、キャッシュメモリから消失してしまい、キャッシュ・ミスが発生する場合がある。このような場合には、大きなレイテンシを必要とする外部主記憶装置に対するアクセスが発生し、システム全体のスループットが著しく低下するという問題点があった。また、連想度（ＷＡＹ）を増やすことで、前述した競合性のキャッシュ・ミスを減らす試みは取られているが、ＷＡＹの数だけ同一アドレスのキャッシュブロックを有するキャッシュメモリを増やすことにより、アクセス時間や不要なコストの増大に繋がるという問題点があった。
【００１４】
キャッシュメモリから追い出されるアドレス、データを主記憶装置またはバッファに格納する時、例えば、アドレスは異なるが、データ内容が同じラインが多数存在している場合でも、異なるアドレスの分だけ、アドレス＋データを格納するコスト(容量)が必要なため、効率的な運用ができなかった。
【００１５】
また、特開平１０−３０７７５２号公報（特許文献３）には、二次キャッシュメモリ又はそれに類似したメモリのデータ容量の効率的利用についての記載がない。
【００１６】
特開２００３−２８８２６９号公報（特許文献４）には、プリフェッチバッファの容量を効率的に利用することについての記載がない。また、特開２００３−２８８２６９号公報（特許文献４）の発明は、リプレースメント自体の回数を減らしたり、キャッシュメモリがヒットする確率自体を増加させるものである。
【００１７】
本発明の目的は、キャッシュ・ミス発生時の主記憶装置へのアクセス回数を低減するリプレースメントデータメモリ装置及びこれを含む中央演算装置並びにリプレースメントデータ処理用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明の第１の観点によれば、主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである前記主記憶装置の別の所定のアドレスを相互に関連付けて自リプレースメントデータメモリ装置に記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、前記主記憶装置の前記別の所定のアドレスと同一であるならば、自リプレースメントデータメモリ装置に前記別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとするリプレースメントデータメモリ装置が提供される。
【００１９】
また、本発明によれば、上記のリプレースメントデータメモリ装置を含むことを特徴とする中央演算装置が提供される。
【００２０】
更に、本発明によれば、主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである前記主記憶装置の別の所定のアドレスを相互に関連付けてリプレースメントデータメモリ装置に記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、前記主記憶装置の前記別の所定のアドレスと同一であるならば、前記リプレースメントデータメモリ装置に前記別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとするリプレースメントデータ処理方法が提供される。
【００２１】
更に、本発明によれば、主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである前記主記憶装置の別の所定のアドレスを相互に関連付けてリプレースメントデータメモリ装置に記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、前記主記憶装置の前記別の所定のアドレスと同一であるならば、前記リプレースメントデータメモリ装置に前記別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとするリプレースメントデータ処理方法をコンピュータに行なわせるためのプログラムが提供される。
【発明の効果】
【００２２】
本発明によれば、二次キャッシュメモリを利用した場合よりも少ないメモリ容量の当該リプレースメントデータメモリ装置を用いて主記憶装置へのアクセス回数を減らすことができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施形態による中央演算装置及びその周辺部のブロック図である。
【図２】本発明の実施形態によるリプレースメントデータメモリの構成を示すブロック図である。
【図３】本発明の実施形態によるキャッシュメモリの構成を示すブロック図である。
【図４】図２に示す記憶部及びその周辺部の構成を示すブロック図である。
【図５】本発明の実施形態によるリプレースメントデータメモリ装置のストア命令実行時の動作を説明するためのフローチャートである。
【図６】図５に示すステップ５０４の詳細を示すフローチャートである。
【図７】本発明の実施形態によるリプレースメントデータメモリ装置のロード命令実行時の動作を説明するためのフローチャートである。
【図８】本発明の実施形態によるキャッシュヒット／キャッシュミスとリプレースメントデータメモリヒット／リプレースメントデータメモリミスとの各組合わせにおけるロード元を示す表である。
【発明を実施するための形態】
【００２４】
以下、図面を参照して本発明を実施するための形態について詳細に説明する。
【００２５】
［第１の実施形態］
図１は、本発明の実施形態による中央演算装置の構成例を示すブロック図である。中央演算装置１００は、ロード命令及びストア命令の実行機能を備えたＣＰＵ＿ＣＯＲＥ１０１と、ダイレクト・マップ方式のキャッシュメモリ１０２と、リプレースメントデータメモリ（Replacement Data Memory；以下、「ＲＤＭ」という。）１０３と、メモリコントローラ１０４とを含む。中央演算装置１００は、主記憶装置１０５に接続されている。ＲＤＭ１０３は、本発明により提供されたものである。「ロード」とは、主記憶装置１０５、キャッシュメモリ１０２、ＲＤＭ１０３等に格納されているデータをＣＰＵ＿ＣＯＲＥ１０１に格納することであり、「ストア」とは、ＣＰＵ＿ＣＯＲＥ１０１に格納されているデータを主記憶装置１０５、キャッシュメモリ１０２、ＲＤＭ１０３等に格納することである。
【００２６】
図２は、ＲＤＭ１０３の内部構成例を示すブロック図である。ＲＤＭ１０３は、調停部２０１と、制御／監視部２０２と、記憶部２０３を含む。調停部２０１は、ロード時にキャッシュメモリ１０２内部のデータとＲＤＭ１０３内部のデータとを調停する。制御／監視部２０２は、ＣＰＵ＿ＣＯＲＥ１０１を監視してロード命令及びストア命令の指定アドレスを取り込み、また、キャッシュメモリ１０２から追い出されたリプレースメントデータをＲＤＭ１０３へ格納する。記憶部２０３は、キャッシュメモリ１０２から追い出されたデータの格納先である。なお、制御／監視部２０２は、ＲＤＭ１０３内でデータが同じ内容になっているエントリのアドレスを関連づけして一時保持するアバンドメントアドレスバッファ（Abandonment Address Buffer；以下、「ＡＡＢ」という。）２０４を含む。
【００２７】
図３は、ＲＤＭ１０３に係るキャッシュメモリ１０２の一実施形態の内部構成を示すブロック図である。図３に示すキャッシュメモリ１０３は、入力アドレスの中位ビット列（ＣＬＩＮＥ）３０２でキャッシュブロックの置き換え候補が一意に決まるダイレクト・マップ構成のキャッシュメモリである。 
【００２８】
図３のキャッシュメモリ１０２は、大きく分けて、データメモリ３０７と、タグメモリ３０６と、Ｍｏｄｉｆｙビット３０４と、ＶＡＬＩＤビット３０５と、比較器３０８と、セレクタ３０９とを含む。データメモリ３０７は、１つのキャッシュブロックに対応する１エントリ上にデータをｍ個格納することが可能である。タグメモリ３０６は、各データのアドレス情報を格納する。Ｍｏｄｉｆｙビット３０４は、キャッシュメモリ・エントリ・データと主記憶装置１０５のデータが一致しているか否かを示す。ＶＡＬＩＤビット３０５は、キャッシュメモリ・エントリ・データが有効であるか否かを示す。比較器３０８は、キャッシュメモリブロックに対応するタグメモリ３０６に記憶されているタグとＣＰＵにより指定されるアドレス中のＴＡＧ３０１とを比較して一致・不一致を判定する。選択器３０９は、ｍ個のキャッシュメモリ・エントリ・データ３０７の内、エントリ・オフセット指定ビット（ＣＳＥＬ）３０３に応じたデータを取り出す。
【００２９】
図４は、キャッシュメモリ１０２から追い出されたリプレースメントされたデータを制御し、また、格納することが可能なＲＤＭ１０３の一例を示した構成図である。ＲＤＭ１０３には、合計１６のエントリが存在する。各ラインの固定領域は、プライオリティ領域４０１と、アドレス領域４０２と、データ領域４０３を含む。プライオリティ領域４０１は、プライオリティ（優先順位）を表す数値を格納する。数値の小さい順にプライオリティが高くなる。数値がゼロであればプライオリティは最高である。アドレス領域４０２は、リプレースメントによりキャッシュメモリ１０２から追い出されたアドレス（ｔａｇ、ｃｌｉｎｅ、ｃｓｅｌの全て）を格納する。データ領域４０３は、リプレースメントによりキャッシュメモリ１０２から追い出されたアドレス（ｔａｇ、ｃｌｉｎｅ、ｃｓｅｌの全て）に対応するデータを格納する。
【００３０】
また、ＲＤＭ１０３は、更に、各ライン上のプライオリティ領域４０１にあるプライオリティの値を１だけ増加させ又は１だけ減少させるカウンタ機能部４０４と、各ライン上のプライオリティ領域４０１にあるプライオリティの値をゼロにするリセット機能部４０５と、各ライン上のプライオリティ領域４０１にあるプライオリティの値を最大値にするセット機能部４０６と含む。
【００３１】
次に、図５、図６に示すフローチャートを用いて、キャッシュメモリ１０２から追い出されたリプレースメントデータをＲＤＭ１０３に格納する処理フローを示す。図５は、中央演算装置１００がストア命令を実行した際の動作手順を示すフローチャートであり、図６は、図５のリプレースメントデータをＲＤＭ１０３に格納するステップ５０４の詳細な動作手順を示すフローチャートである。
【００３２】
ＣＰＵ＿ＣＯＲＥ１０１からストア命令が発行されたならば、ヒットするキャッシュブロックがキャッシュメモリ１０２に存在するか否かの検索を行う（ステップ５０１）。具体的には、ＣＰＵ＿ＣＯＲＥ１０１により指定されたアドレスのうちのＣＬＩＮＥ３０２で指定されるキャッシュブロックにあるＴＡＧ３０６とＣＰＵ＿ＣＯＲＥ１０１により指定されたアドレスのうちのＴＡＧ３０１とが一致すればヒットとし、ヒットしなければミスヒットとする。
【００３３】
ヒットするキャッシュブロックがキャッシュメモリ１０２に存在する場合には（キャッシュがヒットした場合には）（ステップ５０１でＹＥＳ）、ヒットしたキャッシュブロックにあるｍ個のデータ３０７のうち、ＣＰＵ＿ＣＯＲＥ１０１により指定されたアドレスのうちのＣＳＥＬ３０３で指定されるアドレスに対応するデータを上書きする（ステップ５０２）。
【００３４】
ヒットするキャッシュブロックがキャッシュメモリ１０２に存在しない場合には（キャッシュがミスヒットした場合には）（ステップ５０１でＮＯ）、キャッシュブロックのリプレースメントを行う（ステップ５０５）。
【００３５】
また、ヒットするキャッシュブロックがキャッシュメモリ１０２に存在しない場合には（キャッシュがミスヒットした場合には）（ステップ５０１でＮＯ）、リプレースメントデータのうちのミスヒットしたアドレスのデータをキャッシュメモリ１０２から読み出してから（ステップ５０３）、リプレースメントデータメモリ１０３の処理を行なう（ステップ５０４）。
【００３６】
ステップ５０４、５０５が終了したならば、ＣＰＵ＿ＣＯＲＥ１０１により指定されたアドレスに対応するデータを上書きする（ステップ５０６）。
【００３７】
前述のように、ＲＤＭ１０３には、キャッシュメモリ１０２から追い出されるリプレースメントデータを常時監視する機構が含まれる。ＣＰＵ＿ＣＯＲＥ１０１がキャッシュ・ミス時にデータのストアを実行するためには、１キャッシュブロック分のデータのリプレースメントをする必要があるが、リプレースメントにより追い出されるデータの内、図３に示すキャッシュメモリ１０２のＣＬＩＮＥ３０２とＣＳＥＬ３０３にて、一意に決定されるデータを必要に応じてＲＤＭ１０３へ格納する。
【００３８】
ここで、プライオリティの調整について説明をする。長い時間参照されていないアドレスは、近い将来も参照される可能性が低いという推測（時間的局所性）に基づいて、最後に参照されてから最も長い時間が経過したアドレスのエントリを廃棄する。このために、以下に説明する構成及び動作では、プライオリティを設け、エントリが参照される度に、そのエントリの優先順位を上げて、他のエントリのプライオリティを下げている。
【００３９】
図６を参照すると、リプレースメントデータに係るアドレス（ストア命令で指定されるアドレスに含まれるＴＡＧとＣＬＩＮＥとＣＳＥＬで特定されるアドレス。以下、「リプレースメントアドレス」という。）と同一のアドレスが、ＲＤＭ１０３の何れかのエントリのアドレス領域４０２に存在するか否かを判断する（ステップ６０１）。リプレースメントアドレスと同一のアドレスがＲＤＭ１０３の何れかのエントリのアドレス領域４０２に存在する場合には（ステップ６０１でＹＥＳ）、リプレースメントアドレスと同一のアドレスが存在するエントリにリプレースメントデータを格納し、そのエントリのプライオリティを最高（数値でいうとゼロ）にする。更に、そのエントリのプライオリティを最高にする前に、そのエントリよりもプライオリティが高かったエントリが１以上あったならば、それらのエントリのプライオリティを１だけ下げる（数値を１だけ増加させる）（ステップ６０２）。
【００４０】
リプレースメントアドレスと同一のアドレスがＲＤＭ１０３のどのエントリのアドレス領域４０２にも存在しない場合には（ステップ６０１でＮＯ）、リプレースメントアドレスと同一のアドレスがＡＡＢ２０４に存在するか否かを判断する（ステップ６０３）。
【００４１】
リプレースメントアドレスと同一のアドレスがＡＡＢ２０４に存在する場合には（ステップ６０３でＹＥＳ）、リプレースメントデータをＲＤＭ１０３に格納しない。そして、ＡＡＢ２０４においてリプレースメントアドレスと関連づけられているアドレスであって何れかのエントリのアドレス領域４０２に格納されているアドレスを探し、アドレス領域４０２にある探したアドレスをリプレースメントアドレスに書き替える（ステップ６０４）。そして、アドレスを書き替えたエントリのプライオリティを最高（数値でいうとゼロ）にする。更に、そのエントリのプライオリティを最高にする前に、そのエントリよりもプライオリティが高かったエントリが１以上あったならば、それらのエントリのプライオリティを１だけ下げる（数値を１だけ増加させる）（ステップ６０５）。
【００４２】
リプレースメントアドレスと同一のアドレスがＡＡＢ２０４に存在しない場合には（ステップ６０３でＮＯ）、プライオリティが最低であるエントリのデータ領域４０３にリプレースメントデータとリプレースメントアドレスを格納する（ステップ６０６）。これにより、プライオリティが最低であったデータが廃棄される。そして、リプレースメントデータとリプレースメントアドレスを格納したエントリのプライオリティを最高（数値でいうとゼロ）にする。更に、他の全てのエントリのプライオリティを１だけ下げる（数値を１だけ増加させる）（ステップ６０７）。
【００４３】
そして、リプレースメントデータと同一のデータをデータ領域４０３に格納しているエントリがあるか否かを判断する（ステップ６０８）。ある場合には（ステップ６０８でＹＥＳ）、そのようなエントリのプライオリティを最低（数値でいうと最大値）にする。ここで、リプレースメントデータと同一のデータをデータ領域４０３に格納しているエントリが複数あるならば、それらのエントリのプライオリティが最低のプライオリティからそれらのエントリの数の範囲を占めるようにする。そして、そのようなエントリのプライオリティを最低にする前に、そのようなエントリよりもプライオリティが低かったエントリが１以上あったならば、それらのエントリのプライオリティを上げる（数値を減少させる）。ここで、減少前後の数値の差分は、リプレースメントデータと同一のデータをデータ領域４０３に格納しているエントリの数値と同一とする（ステップ６０９）。
【００４４】
そして、ステップ６０６でリプレースメントデータとリプレースメントアドレスを格納したエントリのアドレス（すなわち、リプレースメントアドレス）とリプレースメントデータと同一のデータをデータ領域４０３に格納しているエントリのアドレスを関連づけて、ＡＡＢ２０４に格納する（ステップ６１０）。
【００４５】
次に、図７に示すフローチャートを用いて、ロード時の動作について説明をする。ＣＰＵ＿ＣＯＲＥ１０１がロード命令を実行し、ＣＰＵ＿ＣＯＲＥ１０１が指定したロード元アドレスが存在するか否か、キャッシュメモリ１０２とＲＤＭ１０３に対して検索を行う。
【００４６】
キャッシュメモリ１０２にロード元アドレスと同一のアドレスが存在し、ＲＤＭ１０３の何れかのエントリのアドレス領域４０２にもロード元アドレスと同一のアドレスが存在する場合には（ステップ７０１でＹＥＳ）、キャッシュメモリ１０２から出力されるデータをロードし（ステップ７０２）、ＲＤＭ１０３のロード元アドレスと同一のアドレスがアドレス領域４０２に存在するエントリのプライオリティを最高（数値でいうとゼロ）にする。また、そのエントリのプライオリティを最高にする前に、そのエントリよりもプライオリティが高かったエントリが１以上あったならば、それらのエントリのプライオリティを１だけ下げる（数値を１だけ増加させる）（ステップ７０３）。
【００４７】
キャッシュメモリ１０２にロード元アドレスと同一のアドレスが存在するが、ＲＤＭ１０３の何れのエントリのアドレス領域４０２にもロード元アドレスと同一のアドレスが存在しない場合には（ステップ７０４でＹＥＳ）、キャッシュメモリ１０２から出力されるデータをロードする（ステップ７０５）。
【００４８】
キャッシュメモリ１０２にロード元アドレスと同一のアドレスが存在せず、ＲＤＭ１０３の何れかのエントリのアドレス領域４０２にロード元アドレスと同一のアドレスが存在する場合には（ステップ７０６でＹＥＳ）、そのエントリのデータ領域４０３に存在するデータをロードし（ステップ７０７）、そのエントリのプライオリティを最高に設定する。そして、そのエントリのプライオリティを最高にする前に、そのエントリよりもプライオリティが高かったエントリが１以上あったならば、それらのエントリのプライオリティを１だけ下げる（数値を１だけ増加させる）（ステップ７０８）。
【００４９】
キャッシュメモリ１０２にロード元アドレスと同一のアドレスが存在せず、ＲＤＭ１０３の何れのエントリのアドレス領域４０２にもロード元アドレスと同一のアドレスが存在しないが、ＲＤＭ１０３のＡＡＢ２０４にロード元アドレスが存在する場合には（ステップ７０９でＹＥＳ）、ＡＡＢ２０４でロード元アドレスに関連づけされていて、アドレス領域４０２に存在するアドレスを含むエントリのデータ領域４０３に存在するデータをロードする（ステップ７１０）。
【００５０】
キャッシュメモリ１０２、ＲＤＭ１０３のアドレス領域４０２、ＡＡＢ２０４全てにロード元アドレスと同一のアドレスが存在しない場合には（ステップ７１１でＹＥＳ）、メモリコントローラ１０４に対してデータ・ロード要求を出力する（ステップ７１２）。
【００５１】
図８に、キャッシュメモリ１０２とＲＤＭ１０３のアドレス検索結果に基づくデータアクセスプライオリティを示す。
【００５２】
図８に示すように、キャッシュメモリ１０２とＲＤＭ１０３のアドレス検索を行って、キャッシュメモリ１０２側のみにＣＰＵ＿ＣＯＲＥ１０１が指定したロード元アドレスが存在する場合（即ち、キャッシュ・ヒット且つＲＤＭミス時）、またはキャッシュメモリ１０２側とＲＤＭ１０３の双方にＣＰＵ＿ＣＯＲＥ１０１が指定するロード元アドレスが存在する場合（即ち、キャッシュ・ヒット且つＲＤＭヒット時）には、図２の調停部２０１は、キャッシュメモリ１０２に存在するデータをＣＰＵ＿ＣＯＲＥ１０１に対して送出する制御を行う。
【００５３】
また、キャッシュメモリ１０２にＣＰＵ＿ＣＯＲＥ１０１が指定するロード元アドレスが存在せず、且つＲＤＭ１０３側にＣＰＵ＿ＣＯＲＥ１０１が指定するロード元アドレスが存在する場合（即ち、キャッシュ・ミス且つＲＤＭヒット時）には、図２の調停部２０１は、ＲＤＭ１０３に存在するデータをＣＰＵ＿ＣＯＲＥ１０１に対して送出する制御を行う。
【００５４】
キャッシュメモリ１０２側とＲＤＭ１０３側の双方にＣＰＵ＿ＣＯＲＥ１０１が指定するロード元アドレスが存在しない場合（即ち、キャッシュ・ミス且つＲＤＭミス時）には、図２の調停部２０１は、ＣＰＵ＿ＣＯＲＥ１０１が主記憶装置１０５のロード元アドレスにあるデータを取得するための制御を行う。
【００５５】
本実施形態によれば、以下の効果が奏される。すなわち、一旦、キャッシュメモリに記憶されながらも、リプレースメントによりキャッシュメモリから削除されたデータのうち、リプレースメントの起因となったキャッシュミスに係るアドレスにあったデータは、再度、ロードされる可能性が高いため、そのアドレスにあったデータのみをリプレースメントデータメモリに格納するだけであっても、リプレースメントデータメモリは、将来発生するキャッシュミスに係るデータを格納する確率が高くなる。
【００５６】
［第２の実施形態］
次に、本発明の第２の実施形態について説明する。第１の実施形態に係るキャッシュメモリ１０２では説明を簡単にするため、連想度（ＷＡＹ）の概念を考えないダイレクト・マップ方式のキャッシュメモリとしているが、これに代えて、例えば２ＷＡＹ、４ＷＡＹといったセット・アソシアティブ方式のキャッシュメモリとすることもできる。なお、図３に示すキャッシュメモリからリプレースされたデータを格納する図４のＲＤＭにおいては、キャッシュメモリがセット・アソシアティブ方式のキャッシュメモリであっても同様の構成を有するため、これらの説明は省略する。
【００５７】
本実施形態によれば、プログラム実行中にキャッシュメモリから外部主記憶装置へ一旦ストアされたデータが、後にキャッシュ・ミスを引き起こすロード対象データとなる場合において、外部主記憶装置アクセスの低減が期待できる。その理由は、後に必要となるキャッシュ・データであっても、リプレースの対象となってしまった、ロード対象データのみを、別途格納することを可能とするプロセッサに内蔵されたリプレースメントデータメモリ（ＲＤＭ）およびＲＤＭのコスト（容量）を抑えるためのアバンドメントアドレスバッファ（ＡＡＢ）を有するためである。大抵のプログラムにはループ制御が含まれており、同じ命令列やデータは繰り返しアクセスされる可能性が高いため、このような時間的局所性が高いプログラム処理時に於いて、特に高い効果が期待できる。 
【００５８】
更に、リプレースメントデータメモリ（ＲＤＭ）に格納されている、アドレスは異なるがデータ内容が同じエントリについては、関連づけしたアドレス情報だけをアバンドメントアドレスバッファ（ＡＡＢ）に保持、管理し、ＲＤＭには1エントリだけ残して他のエントリは優先的に廃棄候補にしていくことにより、ＲＤＭを少ないコスト(容量)で効率的に運用できる効果を有する。
【００５９】
リプレースメントデータメモリが行なう上記の方法は、ハードウェア、ファームウェア又はこれらの組合わせによって実現することができる。
【００６０】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６１】
（付記１）
主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである前記主記憶装置の別の所定のアドレスを相互に関連付けて自リプレースメントデータメモリ装置に記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、前記主記憶装置の前記別の所定のアドレスと同一であるならば、自リプレースメントデータメモリ装置に前記別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとするリプレースメントデータメモリ装置。
【００６２】
（付記２）
付記１に記載のリプレースメントデータメモリ装置であって、
リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータに対応していたアドレスである前記主記憶装置の別の所定のアドレスは、アクセス元から出力されたアドレスに含まれていたＣＬＩＮＥ、ＴＡＧ及びＣＳＥＬのうちの前記ＣＬＩＮＥ及び前記ＣＳＥＬに対応したアドレスであることを特徴とするリプレースメントデータメモリ装置。
【００６３】
（付記３）
付記２に記載のリプレースメントデータメモリ装置であって、
前記キャッシュメモリにおいて前記ＣＬＩＮＥにより指定されたラインに記憶されているＴＡＧが、アクセス元から出力された前記ＴＡＧと一致しない場合に、キャッシュミスが発生したと判断されることを特徴とするリプレースメントデータメモリ装置。
【００６４】
（付記４）
付記３に記載のリプレースメントデータメモリ装置であって、
リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータとは、前記キャッシュメモリにおいて前記ＣＬＩＮＥにより指定されたラインに記憶されていたデータのうちの、前記ＣＳＥＬにより選択されたデータであることを特徴とするリプレースメントデータメモリ装置。
【００６５】
（付記５）
付記１乃至４の何れか１に記載のリプレースメントデータメモリ装置であって、
前記主記憶装置の複数のアドレスに対して、自リプレースメントデータメモリ装置に記憶するべきデータが共通である場合、前記主記憶装置の複数のアドレスの間で共通なデータと、前記主記憶装置の複数のアドレスとを相互に関連付けて記憶する記憶手段と、
前記別のキャッシュミスに係る前記主記憶装置のアドレスが、前記記憶手段に記憶されている前記主記憶装置の複数のアドレスのうちの何れかのアドレスと一致した場合には、前記記憶手段に前記主記憶装置の複数のアドレスに関連付けて記憶されている前記共通なデータをロードデータとするロード手段と、
を備えることを特徴とするリプレースメントデータメモリ装置。
【００６６】
（付記６）
付記５に記載のリプレースメントデータメモリ装置であって、
前記記憶手段は、前記主記憶装置の複数のアドレスを関連づけて記憶するアバンドメントアドレスバッファと、前記主記憶装置の複数のアドレスのうちの１つのアドレスと前記共通なデータとを関連づけて記憶する第１のエントリとを備えることを特徴とするリプレースメントデータメモリ装置。
【００６７】
（付記７）
付記６に記載のリプレースメントデータメモリ装置であって、
前記ロード手段は、前記別のキャッシュミスに係る前記主記憶装置のアドレスが、前記記憶手段に記憶されている前記主記憶装置の複数のアドレスのうちの何れかと一致したか否かを、前記別のキャッシュミスに係る前記主記憶装置のアドレスが前記アバンドメントアドレスバッファに格納されている何れかのアドレスと一致するか否かを調べることにより検出することを特徴とするリプレースメントデータメモリ装置。
【００６８】
（付記８）
付記６又は７に記載のリプレースメントデータメモリ装置であって、
前記ロード手段は、前記別のキャッシュミスに係る前記主記憶装置のアドレスが、前記主記憶装置に記憶されている前記主記憶装置の複数のアドレスのうちの何れかと一致したならば、前記第１のエントリに記憶されている前記共通なデータをロードデータとすることを特徴とするリプレースメントデータメモリ装置。
【００６９】
（付記９）
付記６乃至８の何れか１に記載のリプレースメントデータメモリ装置であって、
プライオリティとアドレスとデータとを相互に関連づけて記憶するための第２のエントリを１以上備え、該１以上の第２のエントリは、その１つとして、アドレスとデータに加えてプライオリティも関連づけて記憶するための前記第１のエントリを含み、
前記リプレースメントデータの前記主記憶装置でのストア先であるリプレースメントアドレスが何れかの前記第２のエントリにあるアドレスと一致していれば、前記リプレースメントアドレスが存在する第２のエントリにリプレースメントデータを格納すると共に、その第２のエントリのプライオリティを最高にする手段と、
前記リプレースメントアドレスが何れの前記第２のエントリにあるアドレスとも一致しないが、前記アバンドメントアドレスバッファに記憶されていれば、前記アバンドメントアドレスバッファにおいて前記リプレースメントアドレスと関連づけられているアドレスであって何れかの前記第２のエントリにあるアドレスを前記リプレースメントアドレスに書き替え、アドレスを書き替えたその第２のエントリのプライオリティを最高にする手段と、
前記リプレースメントアドレスが何れの前記第２のエントリにあるアドレスとも一致せず、前記アバンドメントアドレスバッファに記憶されていなければ、プライオリティが最低の第２のエントリに前記リプレースメントデータを格納し、該リプレースメントデータを格納した第２のエントリのプライオリティを最高にし、その上で、リプレースメントデータと同一のデータを有する第２のエントリがあれば、その第２のエントリのプライオリティを最低にし、前記リプレースメントデータを格納した第２のエントリにあるアドレスと前記リプレースメントデータと同一のデータを有する第２のエントリにあるアドレスとを関連づけて前記アバンドメントアドレスバッファに格納する手段と、
を更に備えることを特徴とするリプレースメントデータメモリ装置。
【００７０】
（付記１０）
付記９に記載のリプレースメントデータメモリ装置であって、
前記別のキャッシュミスに係るロード元アドレスが前記キャッシュメモリに存在し、何れかの前記第２のエントリにあるアドレスと一致していれば、前記キャッシュメモリのデータをロードし、前記ロード元アドレスと一致するアドレスを有する前記第２のエントリのプライオリティを最高にする手段と、
前記別のキャッシュミスに係るロード元アドレスが前記キャッシュメモリに存在し、何れの前記第２のエントリにあるアドレスとも一致しないならば、前記キャッシュメモリのデータをロードする手段と、
前記別のキャッシュミスに係るロード元アドレスが前記キャッシュメモリに存在せず、何れかの前記第２のエントリにあるアドレスと一致していれば、前記別のキャッシュミスに係るロード元アドレスと一致したアドレスを有する前記第２のエントリにあるデータをロードし、そのエントリのプライオリティを最高にする手段と、
前記別のキャッシュミスに係るロード元アドレスが前記キャッシュメモリに存在せず、何れの前記第２のエントリにあるアドレスとも一致せず、前記アバンドメントアドレスバッファに記憶されているならば、前記アバンドメントアドレスバッファにおいて前記別のキャッシュミスに係るロード元アドレスに関連づけられているアドレスを有する前記第２のエントリにあるデータをロードする手段と、
前記別のキャッシュミスに係るロード元アドレスが前記キャッシュメモリに存在せず、何れの前記第２のエントリにあるアドレスとも一致せず、前記アバンドメントアドレスバッファに記憶されていなければ、主記憶装置にあるデータをロードする手段と、
を更に備えることを特徴とするリプレースメントデータメモリ装置。
【００７１】
（付記１１）
付記１乃至１０の何れか１に記載のリプレースメントデータメモリ装置を含むことを特徴とする中央演算装置。
【００７２】
（付記１２）
主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである前記主記憶装置の別の所定のアドレスを相互に関連付けてリプレースメントデータメモリ装置に記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、前記主記憶装置の前記別の所定のアドレスと同一であるならば、前記リプレースメントデータメモリ装置に前記別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとするリプレースメントデータ処理方法。
【００７３】
（付記１３）
主記憶装置の所定のアドレスに対するアクセスを行う際に発生したキャッシュミスに起因して、キャッシュメモリ内の或るラインについてリプレースメントが発生した時に、リプレースメント対象のラインに記憶されていた１ライン分のデータのうちの、アクセスされようとしていた前記主記憶装置の前記所定のアドレスに対応するエントリ内オフセットに記憶されていたデータ及び該データに対応していたアドレスである前記主記憶装置の別の所定のアドレスを相互に関連付けてリプレースメントデータメモリ装置に記憶し、ロードにおいて別のキャッシュミスが発生した時に、該別のキャッシュミスにおけるアクセス先のアドレスが、前記主記憶装置の前記別の所定のアドレスと同一であるならば、前記リプレースメントデータメモリ装置に前記別の所定のアドレスと相互に関連付けて記憶されているデータをロードデータとするリプレースメントデータ処理方法をコンピュータに行なわせるためのリプレースメントデータ処理用プログラム。
【符号の説明】
【００７４】
１０１  ＣＰＵ＿ＣＯＲＥ
１０２  キャッシュメモリ
１０３  ＲＤＭ
１０４  メモリコントローラ
１０５  主記憶装置
【図１】
2014209392.tif 000003
【図２】
2014209392.tif 000004
【図３】
2014209392.tif 000005
【図４】
2014209392.tif 000006
【図５】
2014209392.tif 000007
【図６】
2014209392.tif 000008
【図７】
2014209392.tif 000009
【図８】
2014209392.tif 000010