(57)【特許請求の範囲】
【請求項１】
コンピュータにおけるキャッシュシステムであって、
オペレーティングシステムによって複数のビンに論理的に分割されたアドレススペースを有し、前記複数のビンのうちの特定のビン内の特定のデータ項目に対する前記コンピュータ内のプロセッサからの要求を受け取る第１のキャッシュと、
前記第１のキャッシュに電子的に結合された競合キャッシュと、
前記複数のビンに１対１で対応する前記競合キャッシュ内の複数のカウンタとを設け、
前記複数のカウンタのうち前記特定のビンに対応するカウンタは前記特定のデータ項目に対する前記要求の結果、前記第１のキャッシュにキャッシュミスが発生し、前記競合キャッシュ内でキャッシュヒットが発生したときにのみインクリメントされる、
キャッシュシステム。
【請求項２】
前記第１のキャッシュは前記特定のデータ項目のアドレスと競合するアドレスを有する競合データ項目を含み、
前記特定のデータ項目に対する前記要求の結果前記第１のキャッシュにキャッシュミスが発生するとき、前記競合データ項目が前記第１のキャッシュから追い出されて前記競合キャッシュに記憶される、
請求項１に記載のキャッシュシステム。
【請求項３】
相対的に高いレベルのキャッシュを含み、前記相対的に高いレベルのキャッシュと前記第１のキャッシュは、前記相対的に高いレベルのキャッシュが前記第１のキャッシュより高いレベルにあるメモリ階層の一部を成し、
前記相対的に高いレベルのキャッシュは前記競合データ項目のコピーを含み、
前記特定のデータ項目に対する前記要求の結果前記競合データ項目が前記第１のキャッシュから追い出され、前記競合データ項目の前記コピーは前記相対的に高いレベルのキャッシュから追い出されない、
請求項２に記載のキャッシュシステム。
【請求項４】
コンピュータにおけるキャッシュシステムであって、
相対的に高いレベルのキャッシュと、
相対的に低いレベルのキャッシュとを設け、
前記相対的に高いレベルのキャッシュと前記相対的に低いレベルのキャッシュは、前記相対的に高いレベルのキャッシュが前記相対的に低いレベルのキャッシュより高いレベルにあるメモリ階層の一部を成し、前記相対的に高いレベルのキャッシュと前記相対的に低いレベルのキャッシュはそれぞれ競合データ項目のコピーを含み、
前記キャッシュシステムは更に前記相対的に低いレベルのキャッシュに電子的に接続され、前記相対的に低いレベルのキャッシュにおける競合ミスの結果前記競合データ項目が追い出されるとき前記競合データを記憶する競合キャッシュを有し、
競合ミスの結果前記競合データ項目が前記相対的に低いレベルキャッシュから前記競合キャッシュに追い出されるとき、前記競合データ項目は前記相対的に高いレベルキャッシュから追い出されない、
キャッシュシステム。
【請求項５】
キャッシュメモリシステムにおけるキャッシュミスを低減する方法であって、
第１のキャッシュ及び競合キャッシュがプロセッサからのあるデータ項目に対する要求を受け取り、
前記データ項目が特定の論理メモリビン内のアドレスを有し、前記データ項目に対する前記要求の結果前記第１のキャッシュ内にキャッシュミスが発生し、前記競合キャッシュ内にキャッシュヒットが発生するときにのみ、前記競合キャッシュがカウンタをインクリメントし、
前記カウンタが予め定められた値を越えると、オペレーティングシステムによって前記特定の論理メモリビン内のページをマッピングし直す、
キャッシュミスを低減する方法。
【請求項６】
以下のステップを含む、コンピュータキャッシュシステムにおける包含の方法：
メモリ階層における相対的に低いレベルのキャッシュと相対的に高いレベルのキャッシュがプロセッサからの特定のデータ項目に対する要求を受け取る；
前記相対的に低いレベルのキャッシュと前記相対的に高いレベルのキャッシュはそれぞれ前記特定のデータ項目と競合する競合データ項目のコピーを含む；
前記相対的に低いレベルのキャッシュが前記相対的に低いレベルのキャッシュから競合キャッシュに前記競合データ項目を追い出す；
前記相対的に高いレベルのキャッシュが前記相対的に高いレベルのキャッシュに前記競合データ項目が残ることを許容する。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は一般的にはデジタルコンピュータメモリシステムに関し、より詳細にはキャッシュメモリシステムにおける競合ミスを低減するためのシステムに関する。
【０００２】
【従来技術及びその問題点】
ほとんどのコンピュータシステムには多階層のメモリシステムが採用され、この階層の最高レベルには高速であるが容量の小さいメモリが用いられ、最低レベルには低速であるが容量の大きいメモリが用いられる。通常、この階層構造にはキャッシュと呼ばれる小型の高速メモリが含まれ、これはプロセッサ集積回路に物理的に一体化されるか、あるいは高速化のためにプロセッサに物理的に近接して設けられる。命令キャッシュとデータキャッシュが別々に設けられることもある。また、キャッシュが多レベルに設けられることもある。
【０００３】
メモリ階層はメモリに対して要求された項目が要求時に高いパーセンテージで階層の最高レベルに存在しなければ有用ではない。プロセッサがキャッシュの項目を要求し、その項目がキャッシュに存在した場合、この事象をキャッシュヒットと呼ぶ。プロセッサがキャッシュの項目を要求し、その項目がキャッシュに存在しなかった場合、この事象をキャッシュミスと呼ぶ。キャッシュミスが発生した場合、要求された項目はメモリ階層のより下にあるレベルから取り出される。これは性能に大きな影響を与える。一般に、キャッシュミスの発生とその影響を最少限にすることは、コンピュータシステム全体の性能を左右する最も重要な設計パラメータの一部をなす。
【０００４】
キャッシュとメモリ階層のその１つ下のレベルとの間で転送可能な最小のメモリ量をラインと呼ぶ（ブロックと呼ぶこともある）。通常、メモリはワード（たとえば、32ビット/ワード）に構成され、１ラインは通常複数のワード（たとえば、16ワード/ライン）からなる。また、メモリはページに分割することができ、各ページは多数のラインからなる。
【０００５】
もしキャッシュがあるラインアドレス全体をデータとともに記憶するなら、任意のラインをそのキャッシュの任意の場所に入れることができる。スペースを節約するための代案として次のものがある。キャッシュに128ラインが入るものとする。１２８ラインに対して、７ビットを使ってこのキャッシュ内のあるライン位置を指定することができる。ラインアドレス中の最下位の７ビットを用いてキャッシュ内のラインを指定するとすれば、各物理的アドレス中の残りの上位側ビットの集合だけがデータとともに記憶されなければならない。キャッシュ内のラインを指定するのに用いられる数は通常インデクスと呼ばれ、ラインの物理アドレスを定義するのに必要な残りのビット集合は通常タグと呼ばれる。
【０００６】
インデクス付けを行ったキャッシュにおいては、特定のアドレスを有する項目はインデクスによって指定されるキャッシュ内の１つの場所にのみ入れることができる。更に、アドレス空間内の同一のインデクスビットを有する各項目は潜在的にはそのキャッシュ内の同じラインスペースを必要とする。従って、キャッシュ内の既存のラインと同じスペースを必要とする新たなラインがフェッチされ、その既存のラインはキャッシュ内に残らなければならない場合がある。この状況を競合(conflict)と呼び、次により詳細に説明する。
【０００７】
あるラインがキャッシュ内の１つの場所にしか存在しえない場合、そのキャッシュはダイレクトマッピングされているものと言われる（また、連想度が低いと言われる）。他の設計では、キャッシュが、それぞれが２ライン以上を有するセット群に構成されることがある。あるラインをこのようなセット群のうちの１つにしか入れることができない場合、そのキャッシュはセットアソシアティヴであるとされる。あるラインをキャッシュの任意の場所に入れることができる場合、そのキャッシュはフルアソシアティヴであると言われる。一般に、連想度の低いキャッシュは連想度の高いキャッシュより単純、高速であり、必要なスペースも小さい。しかし、ダイレクトマッピングされたキャッシュ、あるいは他の連想度の低いキャッシュは、次に説明する競合に起因する性能上の問題点を有する。
【０００８】
ダイレクトマッピングされたキャッシュあるいは他の連想度の低いキャッシュにおいては、新しいラインが既存のラインと同じスペースを必要とすることがある。すなわち、ラインを無作為に置換したり、最近もっとも長期間使用されていなかったラインを置換するかわりに、この新しいラインがキャッシュ内の同じインデクスを有するラインを置換する。置換されたラインは有用であったり、またキャッシュに残る必要がある場合がある。有用なラインが同じインデクスを有するラインで置換されたことに起因するミスを競合ミスと呼ぶ。ソフトウエアによっては、第１のラインから第２のラインへの置換が起こると、その後すぐに第２のラインが第１のラインでまた置換されてしまうものもある。このような単一のキャッシュラインでのスラッシングは、キャッシュサイズがその特定のソフトウエアに適当なものであってもシステム性能の低下につながることがある。そこで、競合ミスに起因するシステム性能に対する悪影響を最小限にしながら、連想度の低いキャッシュに固有の速度及びスペース上の利点を生かすことが必要とされる。
【０００９】
ダイレクトマッピングされたキャッシュにおける競合ミスの影響を低減する方法の１つに、小さなフルアソシアティヴ２次キャッシュを追加する方法がある。たとえば、Proceedings of the 17th Annual International Symposium On Computer Architecture（1990年５月）、364-373ページのJouppi、N.P.の“Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers”及び米国特許5,261,066号を参照されたい。Jouppiはミスキャッシュと呼ばれる小さな（２ないし５ラインの）のフルアソシアティヴキャッシュを追加することを提案している。１次キャッシュ内にキャッシュミスが発生した場合、要求された項目は１次キャッシュとミスキャッシュの両方に入れられる。ミスキャッシュに入れられた項目は最近もっとも長い間使用されていなかった項目に置き換わる。改良点としてJouppiが提案していることは、小さな２次キャッシュに、要求されたラインの代わりにミスによる置換のために犠牲になったラインを入れることであり、このような２次キャッシュをビクティムキャッシュと呼ぶ。他の設計では、アシストキャッシュと呼ばれる先入れ先出し置き換えを行う小さな追加キャッシュが、Digest of Papers Spring COMPCON 94（1994年）、373-382ページのKurpanek, G他の“PA7200; A PA-RISC Processore With Integrated High Performance MP Bus Interface”に開示されている。
【００１０】
複数レベルのキャッシュがある場合、低レベルのキャッシュは通常高レベルのキャッシュより大きく、また低レベルのキャッシュは通常高レベルのキャッシュにあるすべての情報を含んでいる。低レベルのキャッシュが高レベルのキャッシュにある情報のすべてを含んでいるとき、この低レベルのキャッシュは包含性を有するといわれる。包含性の主な利点は、キャッシュメモリ内の項目が階層構造の他の場所にある項目と同じであるかどうかを判定するためのチェック（コヒーレンシーチェックと呼ばれる）が必要であるとき、最低レベルのキャッシュだけをチェックすればよいことにある。一般に、上述したビクティムキャッシュあるいはアシストキャッシュを有するシステムでは、低レベルのキャッシュからビクティムキャッシュあるいはアシストキャッシュに項目が移されたとき、それより高レベルのキャッシュ内の対応する項目がその高レベルのキャッシュから除去される。この場合、置換の犠牲となったこの項目が再度要求されると、高レベルのキャッシュにキャッシュミスが発生し、性能上の影響が生じる。
【００１１】
ダイレクトマッピングされたキャッシュ内での競合ミスの影響を低減する他の方法として、競合ミスのアドレス分布をモニタし、メモリページングをマッピングし直す方法がある。オペレーティングシステムがキャッシュ競合の分布に関する情報を持っていれば、他のページと競合するページをこのような競合のないページにマッピングし直すことができる。このような再マッピングは静的（実行の前に判定される）でも動的（ソフトウエアの実行中の競合ミスに基づいて変更する）でもよい。静的な方法は、ページのアドレス変換（ページマッピング）を決定するとき、オペレーテンィグシステムは所与のキャッシュラインにマッピングされるページの数を知っていると想定している。静的な方法の例としては、ACM Transactions on Computer Systems、Vol. No.4、（1992年11月）338-359ページのKesslaer R.他の“Page Placement Algorithms for Large Real-Indexed Caches”を参照されたい。動的なページリマッピングの例としては、ASLOS VI Proceedings （1994年１０月）、158-170ページのBershad B.他の“Avoiding Conflict Misses Dynamically in Large Direct Mapped Caches”を参照されたい。Bershad他の場合、キャッシュミスの履歴を検出及び記録する（キャッシュミスルックアサイドバッファと呼ばれる）追加ハードウエアが設けられる。キャッシュミスはページ毎に検出される。ミスの多いページは異なる物理アドレスにマッピングし直される。キャッシュミスルックアサイドバッファにはキャッシュミスから連想的に検索されたページ番号タグが記憶される。また、このバッファはカウンタを含む。キャッシュミスが検出され、このバッファ内にそのページ番号タグがすでに存在する場合、対応するカウンタがインクリメントされる。キャッシュミスが検出され、そのページ番号タグがこのバッファに存在しない場合、最近もっとも長い間使用されていなかったアドレスが置換される。カウンタがあるしきい値を越えると、このバッファは割り込みを発生し、オペレーティングシステムがこの割り込みカウンタに対応するページをマッピングし直す。
【００１２】
ビクティムキャッシュとアシストキャッシュは、競合ミスが比較的短い時間間隔内に発生する場合にはこれを低減する。長い時間間隔内に発生するミスについては、被置換ラインはソフトウエアが次にそれを要求する前にビクティムキャッシュから置換されるかもしれない。動的ページリマッピングは競合ミスを低減するが比較的時間がかかる。リマッピングが行なわれる前にソフトウエアコンテキストが変わる可能性がある。更に、動的なページリマッピングは、ミスの多いページをマッピングし直すための多数の代替ターゲットページを提供するための大きなキャッシュを必要とする。最後に、Bershad他の具体的実施態様においては、すべてのキャッシュミスがカウントされ、キャッシュからラインを置換しないミスまでカウントされる。小さいフルアソシアティブ補助キャッシュによって提供される競合ミスの短期的な影響の低減及び動的ページリマッピングによるミスの低減更にその他の利点を有するダイレクトマッピングされたキャッシュの速度及びスペース上の利点を提供する改善されたキャッシュシステムが必要とされている。
【００１３】
【概要】
改良されたキャッシュシステム（競合キャッシュと呼ぶ）は早い立ち上がりとキャッシュミスの低減のためのハードウエア及びオペレーティングシステムが動的ページリマッピングを用いてキャッシュ競合を除去するのを助けるカウンタを有する。短期の立ち上げと長期的な除去との両方を提供することには相乗効果がある。これは、動的ページリマッピングによって一部の競合ミスが除去されると、より時間的に離れた他の競合ミスを検出し、これを許容し、最終的には同じ処理を用いて除去することができるためである。更に、補助キャッシュとカウンタを組み合わせることによってある程度のハードウエアの共用が可能になる。本発明の一側面では、多レベルのキャッシングを行なうシステムにおいて、競合キャッシュを最高レベルキャッシュについての改善された包含法と組み合わせて、最高レベルキャッシュについての一層のミスの低減を行なう。
【００１４】
一実施例において、連想度の低いキャッシュに競合ミスが発生すると、置換された項目は競合キャッシュに移される。オペレーティングシステムはこの連想度の低いキャッシュを論理的にビンに区分されたものとみなす。１つのビンのアドレス範囲は１ページあるいは複数ページである。連想度の低いキャッシュ内の各論理ビンは競合キャッシュ内に対応するカウンタを有する。あるアドレスがこの連想度の低いキャッシュにはなく競合キャッシュ内でヒットした場合、ソフトウエアは競合により連想度の低いキャッシュから追い出されたラインにアクセスし直す。このような競合ミスが発生するたびに対応するビンカウンタがインクリメントされる。
【００１５】
多レベルキャッシュ階層を有する一実施例において、最高レベルのキャッシュ（L1キャッシュ）は下のレベルの連想度の低いキャッシュ（L2キャッシュ）と競合キャッシュとの合併集合の部分集合である。すなわち、下のレベルのキャッシュから競合キャッシュに追い出されたラインは最高レベルのキャッシュに残ることができる。この新しい包含特性によって、競合ミスがある状況下での最高レベルのキャッシュ内のキャッシュラインが寿命が伸び、最高レベルキャッシュの性能が向上する。更に、最高レベルキャッシュ（及び競合キャッシュ）は下のレベルのキャッシュ内の同じインデクスにマッピングされるラインをいくつか持つことができ、これによって下のレベルのキャッシュのスラッシングの可能性が低減される。
【００１６】
本発明の諸相において、ビクティムキャッシングと動的リマッピングの相乗作用及び多レベルキャッシュ階層における新しい包含特性によって、これら２つの方法の両方の性能上の利点及びそれ以外の性能上の利点が提供される。競合キャッシュカウンタは、すべてのミスをカウントせず競合ミスのみをカウントするために、従来の動的リマッピングシステムに比べて動的リマッピングを行なうためのより有効な情報をオペーレーティングシステムに供給する。多レベルキャッシュ階層構造において、競合キャッシュに包含特性を持たせることによって、ビクティムキャッシュに比べてより優れた性能を得ることができる。これは置換されたキャッシュラインが最高レベルのキャッシュにとどまることができるためである。本実施例では、新規な設計によってキャッシュと計数にタグメモリを共用できるようにすることによって、キャッシング及び計数機能の組み合わせに必要なハードウエアを低減している。
【００１７】
【発明の実施例】
図１には多レベルキャッシュメモリ階層を有するコンピュータシステムの一例を示す。一般に、キャッシュメモリ及びメインメモリのためのアドレスバス構造及びデータバス構造はさまざまであるが、本発明はその態様には無関係である。図１に示すシステムでは、第１の中央処理装置（CPU）100はその一部として一体化された第１レベルのデータキャッシュメモリ（L1データキャッシュ）102を含む。第２レベルのデータキャッシュ（L2データキャッシュ）104は外部に設けられたものとして示されている。また、CPU 100には別個の命令キャッシュ（図示せず）を設けることもできる。図１において、第２のCPU 106もまた第１レベルのデータキャッシュ108及び第２レベルのデータキャッシュ110を含む。これら２つのCPUはバス112によって接続されている。これら２つのCPUは１つあるいは複数のメインメモリ114を共用する。また、このシステムには仮想アドレスを実アドレスに変換するためのトランザクションルックアサイドバッファ（TLB）（図示せず）を設けることもできる。オペレーティングシステムソフトウエア116はメインメモリ114内に設けられる。
【００１８】
本発明は競合キャッシュ118、120と呼ばれるハードウエア構造を含む。競合キャッシュ118及び120は図１にはCPU内部にあるものとして示すが外部に設けることもできる。キャッシュがプロセッサの内部にあるか外部にあるかは本発明にとっては重要ではない。競合キャッシュを任意の連想度の低いキャッシュに用いて競合ミスを低減することができる。包含についての説明を容易にするために、競合キャッシュ118及び120をL2キャッシュ104、110に設けるものとして説明するが、一般にはこのコンピュータシステムのキャッシュは１つだけとすることもできるし、また３つ以上のレベルのキャッシュを設けることもできる。また、競合キャッシュは任意の連想度の低いキャッシュの性能を向上させることができる。以下の説明では、L2キャッシュ104、110はダイレクトマッピングされるものとする。従って、オペレーティングシステム116はページ配置を注意深く行なうことによって競合ミスを改善することができる。従って、オペレーティングシステム116はL2キャッシュ104及び110をビンに論理的に分割されたものとみなす。ここで、ビンとはメモリの１ページあるいは複数のページである。
【００１９】
図２には競合キャッシュ118をより詳細に示す。競合キャッシュ118にはアドレスタグを記憶するための内容アドレシング可能メモリ（CAM）202、データラインを記憶するためのデータRAM 204及び競合ミスをカウントするための競合カウンタ群206が設けられる。競合カウンタ群206にはL2キャッシュ104内の各論理ビン毎に１つのカウンタがある。更に、デジタルマルチプレクサ208及び210が設けられ、また実施態様によってはデジタルデマルチプレクサ212が設けられる。
【００２０】
図３には、L1キャッシュ102、L2キャッシュ104、競合キャッシュ内のCAM 202及びRAM 204、及びL1キャッシュ102内の例としてのデータ項目ITEM 1 300を示す。図３から図６において、L1キャッシュ102は２方向連想キャッシュとして示されている。これは説明の都合上に過ぎない。L1キャッシュ102の具体的構成は本発明にとって重要ではない。L2キャッシュ104にもITEM1 300がそのアドレスタグTAG1 302とともに含まれている。L2キャッシュ104内のITEM1 300のロケーションはアドレスインデクスINDEX1 304によって決定されるロケーションに制限される。
【００２１】
図４にはL2キャッシュ104からある項目が追い出された後の図３と同じブロックを示す。L2キャッシュ104からあるラインが追い出されると、この追い出されたラインのアドレスがCAM 202に記憶され、そのデータがデータRAM 204に記憶される。図４において、ITEM2 400がL1キャッシュ102及びL2キャッシュ104に入れられる。ITEM2 400はITEM1 300と同じインデクス304を有し、従ってL2キャッシュ104内で同じ場所を占めなければならない。ITEM1 300はITEM2 400によってL2キャッシュ104から置換され、競合キャッシュに入れられている。コヒーレンシーについていえば、L1キャッシュ102までのコヒーレンスチェックをパスするには、L1キャッシュ102内でITEM1 300が変更されている場合、競合キャッシュ118内でも変更されていなければならないことに注意されたい。そのかわりに、コヒーレンスチェックで３つのキャッシュをすべてチェックすることもできる。
【００２２】
また、図４には（図５及び図６とともに）本発明の包含特性が示されている。従来技術の部分で説明したように、多レベルキャッシュシステムを有する多くのシステムにおいて、各キャッシュはそれより高いレベルのキャッシュのすべてのラインを含む。通常、低レベルキャッシュ内でミスが発生すると、最高レベルキャッシュ内の対応するラインが追い出される。その結果、通常高レベルのキャッシュは低レベルのキャッシュよりはるかに高速であるため性能上の損失が発生する。図４に戻って、従来のシステムでは、ITEM2 400がL2キャッシュ104に入れられ、ITEM1 300が置換されると、L1キャッシュ102内のITEM1 300が除去される。これはL2はL1内のすべての項目を含んでいなければならないためである。これに対して、図３から図６に示す２レベルのシステムでは、L2キャッシュ104はL1キャッシュ102のすべてのラインを含んでいるわけではない。その代わり、本発明の一側面によれば、L2キャッシュ104と競合キャッシュ（図１及び図２の118）の合併集合がL1キャッシュ102のすべてのラインを含む。あるラインがL2キャッシュ104から競合キャッシュ118に追い出されるとき、L1キャッシュ102には（新しいラインを加える余裕があれば）対応するラインが（L1キャッシュ102に存在すれば）残る。図４において、ITEM1 300はL2キャッシュ104から追い出されているが、L1キャッシュ102にはITEM1 300が残っていることに注意されたい。
【００２３】
図５に示すように、あるラインをL1キャッシュ102から追い出して新しいラインを追加する場所を作ることができる。図５において、新しいデータ項目ITEM3 500がL1キャッシュ102及びL2キャッシュ104に入れられた。ITEM3 500はITEM2 400をL2キャッシュ104（同じインデクス）から追い出し、ITEM1 300をL1キャッシュ102から追い出す（たとえば、どのラインが最近もっとも長い間使用されていなかったかに基づく置換）。図５において、ITEM2 400はL2キャッシュ104から追い出されるが、L1キャッシュ102には残ることが許されていることに注意されたい。
【００２４】
図６に示すように、L1キャッシュ102からあるラインを追い出して競合キャッシュ118からのラインを入れる場所を作ることができる。あるいは、競合キャッシュ118からあるラインを追い出してL2キャッシュ104から新たに追い出させるラインのための場所を作る場合に、競合キャッシュから追い出されるラインをL1キャッシュ102から追い出すことができる。競合キャッシュ118内でヒットが起こった場合、そのラインがL1キャッシュ102にキャッシュできる場合にはL1キャッシュ102に持ち上げられる。図６において、ITEM1 300がL1キャッシュ102に持ち上げられてITEM2 400を置換していることに注意されたい。
【００２５】
上述したような本発明の包含方式によって、L2キャッシュ104内に競合ミスがある状況下でL1キャッシュ102内の一部のキャッシュラインの寿命が延び、それによってL1キャッシュ102の性能が向上する。図５及び図６において、L1キャッシュ102と競合キャッシュ118はそれぞれ、L2キャッシュ104内の同じインデクスにマッピングされる少なくとも２つの項目を含み、それによってL2キャッシュ104のスラッシングが低減されていることに注意されたい。
【００２６】
また、図６は、ページのリマッピングを助けるために競合キャッシュ118内のカウンタ206を用いることを示している。図６にはプロセッサからのITEM1 300に対する次の要求に続いて発生する図５に示すデータ位置の変更が示されている。L2キャッシュ104にないアドレスが競合キャッシュ118内のCAM 202中のアドレスと比較され、要求されたラインが以前に追い出されているかどうかが調べられる。図５において、ITEM1 300は競合キャッシュ118にあり、L2キャッシュ104からの追い出しがあったことを示していることに注意されたい。要求されたラインが競合キャッシュ118中にあった場合は、そのラインは競合キャッシュからマルチプレクサ210（図２）を介してプロセッサに供給される。ヒット/ミス信号（図示せず）を用いてプロセッサ（図１の100）にヒットの発生が知らせられる。L2キャッシュ104でミスがあり、それが競合キャッシュ118でヒットした場合、これはL2キャッシュ104内の（そのラインについての）キャッシュインデクスに競合が存在することを意味する。あるラインがL2キャッシュ104にはなかったが競合キャッシュ118ではヒットしたとき、競合カウンタ群206中の対応するカウンタがインクリメントされ、L2キャッシュ104内のその特定の論理キャッシュビンに関する競合を表わす。オペレーティングシステム（図１の116）はL2キャッシュ104をビン（ビンはメモリの１つあるいは複数のページ）に論理的に分割されたものとみなすことを思い出されたい。図６において、L2キャッシュ104はオペレーティングシステムによって論理ビンBIN1 602等の複数のビンに分割されている。論理ビンBIN1 602内のページはITEM2 400のINDEX1 304を含む。図６において、COUNTER1 600は論理ビンBIN1 602に対応する。競合カウンタヒット/ミス信号（図示せず）は（図２に示すデマルチプレクサ212を用いて）適切な競合カウンタ600のインクリメント信号として用いられる。オペレーティングシステム（図１の116）は競合カウンタ群206中のすべてのカウンタの内容を読み出すことができる。
【００２７】
競合キャッシュ118はデュアルポートあるいはフルラインバッファとし、競合キャッシュへの読み出しと書き込みの同時アクセスができるようにするのが好ましい。あるアクセスがL2キャッシュ104でミスした場合、L2キャッシュ104内のミスしたインデクスにあるラインはいかなるものでも競合キャッシュ118に移される。図６において、ITEM3（500）がL2キャッシュ104から競合キャッシュ118に移されていることに注意されたい。L2キャッシュ104はミスしたが競合キャッシュ118がヒットした（それらのラインが異なる物理アドレスを持っている）場合、L2キャッシュ104から競合キャッシュ118に１つのラインを書き込み、競合キャッシュ118から１つのラインを読み出して実行中のアクセスに応えなければならない。図６において、プロセッサからの１つの要求の結果、ITEM1 300が競合キャッシュ118からL1キャッシュ102とL2キャッシュ104の両方に移され、ITEM2 400がL2キャッシュ104から競合キャッシュ118に移されたことに注意されたい。好適には、最適な性能を得るために、競合キャッシュ118内の１つのエントリを空にして新しいL2キャッシュラインのためにとっておき、古いラインを掃き出すのを待つことなくラインを競合キャッシュ118に移動できるようにする。
【００２８】
図３から図６において、図及び説明を簡略化するために、アドレスタグ（たとえばTAG1 302）は各種のキャッシュに渡って同一なもの（同一参照符号）として示されていることに注意されたい。しかし、一般的には、アドレスタグの長さはキャッシュ毎に異なる。たとえば、TAG1 302はITEM1 300のフルアドレスを構成するビットの部分集合である。L2キャッシュ104に記憶される部分集合はL1キャッシュ102あるいは競合キャッシュ118に記憶される部分集合と異なるかもしれない。一般に、それぞれのキャッシュは連想度の程度によって決まる異なる物理的アドレス指定条件及び本発明の諸相には無関係な他のシステム条件を有する。
【００２９】
ある特定の実施例においては、L2キャッシュ104は市販のSRAMによって外部に設けられ、制御回路はプロセッサ100にその一部として集積化される。競合キャッシュ118は比較的小さく、たとえば８ないし３２のキャッシュラインを有する。競合キャッシュ118はL2キャッシュ104と同じタイミングで並列アクセスが可能である。
【００３０】
従来技術の項で説明したように、ミスキャッシュ、ビクティムキャッシュ及びアシストキャッシュ等のフルアソシアティヴバッファはダイレクトマッピングされたキャッシュの競合ミスを改善することができるが、それは比較的短い期間に発生する競合ミスに限られる。容量が限られているため、置換されたラインはソフトウエアが次にそれを必要とする前にフルアソシアティヴキャッシュから失われるかもしれない。ダイレクトマッピングされるキャッシュにおけるより長い期間での競合ミスはページリマッピングによって除去することができる。異なるビンには当然異なるインデクスアドレスが含まれるため、異なるキャッシュビンにマッピングされたページには競合ミスは発生しえない。オペレーティングシステムがキャッシュ競合の分布に関する情報を持っている場合、オペレーティングシステムは競合するページをこのような競合のない他のキャッシュビンにマッピングし直すことによって競合部分を除去することができる。競合キャッシュ118には、オペレーティングシステムによる動的リマッピングのための競合カウンタ群が設けられる。
【００３１】
すべてのキャッシュミスがカウントされる動的ページリマッピングによって競合ミスを低減するという、他のシステムで開示されているカウンタとは異なり、競合キャッシュ118内のカウンタは競合ミス、具体的にはダイレクトマッピングされたL2キャッシュ104内のミスであって競合キャッシュ118でヒットするミス、のみをカウントする。キャッシュの競合を短期的には許容することと長期的に除去することの両方を行なうことには相乗効果がある。というのは、動的ページリマッピングによって一部の競合ミスが除去されると、より時間的に離れた他の競合ミスを検出し、これを許容し、最終的には同じ処理を用いて除去することができるからである。たとえば、図６において、ITEM1 300に対するL2 104ミスは短期的に許容され、ITEM1のBIN1 602に対応するカウンタ600があらかじめ定められたしきい値を越えると、ITEM1に対応する仮想メモリページがスワップされる。更に、図２に示す設計では、２次キャッシュとカウンタを組み合わせることによって、ハードウエア（たとえば内容アドレシング可能メモリ202）の共用が可能になる。
【００３２】
本発明の以上の説明は例示及び説明のためにのみ行なったものである。以上の説明は本発明を開示された態様によって厳密に網羅しようとするものでもなく、またそれに限定しようとするものでもなく、以上の原理に照らした他の改変や変更態様が可能である。実施例は本発明の原理とその実際の用途について最良の説明を与え、当業者が本発明を特定の用途に適したさまざまな実施態様及び変更態様で最も良く利用しうるように選択及び説明したものである。特許請求の範囲は従来技術によって限定されるものを除き本発明の他の代替実施例を含むものと理解されたい。
【００３３】
以下に本発明の実施の態様の例を列挙する。
【００３４】
［実施の態様１］コンピュータにおけるキャッシュシステムであって、
オペレーティングシステムによって複数のビンに論理的に分割されたアドレススペースを有し、前記複数のビンのうちの特定のビン内の特定のデータ項目に対する前記コンピュータ内のプロセッサからの要求を受け取る第１のキャッシュと、
前記第１のキャッシュに電子的に結合された競合キャッシュと、
前記複数のビンに１対１で対応する前記競合キャッシュ内の複数のカウンタとを設け、
前記複数のカウンタのうち前記特定のビンに対応するカウンタは前記特定のデータ項目に対する前記要求の結果、前記第１のキャッシュにキャッシュミスが発生し、前記競合キャッシュ内でキャッシュヒットが発生したときにのみインクリメントされることを特徴とするキャッシュシステム。
【００３５】
［実施の態様２］実施の態様１に記載のキャッシュシステムであって、
前記第１のキャッシュは前記特定のデータ項目のアドレスと競合するアドレスを有する競合データ項目を含み、
前記特定のデータ項目に対する前記要求の結果前記第１のキャッシュにキャッシュミスが発生するとき、前記競合データ項目が前記第１のキャッシュから追い出されて前記競合キャッシュに記憶される
ことを特徴とするキャッシュシステム。
【００３６】
［実施の態様３］実施の態様２に記載のキャッシュシステムであって、
相対的に高いレベルのキャッシュを含み、前記相対的に高いレベルのキャッシュと前記第１のキャッシュは、前記相対的に高いレベルのキャッシュが前記第１のキャッシュより高いレベルにあるメモリ階層の一部を成し、
前記相対的に高いレベルのキャッシュは前記競合データ項目のコピーを含み、
前記特定のデータ項目に対する前記要求の結果前記競合データ項目が前記第１のキャッシュから追い出され、前記競合データ項目の前記コピーは前記相対的に高いレベルのキャッシュから追い出されないことを特徴とするキャッシュシステム。
【００３７】
［実施の態様４］コンピュータにおけるキャッシュシステムであって、
相対的に高いレベルのキャッシュと、
相対的に低いレベルのキャッシュと
を設け、
前記相対的に高いレベルのキャッシュと前記相対的に低いレベルのキャッシュは、前記相対的に高いレベルのキャッシュが前記相対的に低いレベルのキャッシュより高いレベルにあるメモリ階層の一部を成し、
前記相対的に高いレベルのキャッシュと前記相対的に低いレベルのキャッシュはそれぞれ競合データ項目のコピーを含み、
前記キャッシュシステムは更に前記相対的に低いレベルのキャッシュに電子的に接続され、前記相対的に低いレベルのキャッシュにおける競合ミスの結果前記競合データ項目が追い出されるとき前記競合データを記憶する競合キャッシュを有し、
競合ミスの結果前記競合データ項目が前記相対的に低いレベルキャッシュから前記競合キャッシュに追い出されるとき、前記競合データ項目は前記相対的に高いレベルキャッシュから追い出されないことを特徴とするキャッシュシステム。
【００３８】
［実施の態様５］キャッシュメモリシステムにおけるキャッシュミスを低減する方法であって、
第１のキャッシュ及び競合キャッシュがプロセッサからのあるデータ項目に対する要求を受け取り、
前記データ項目が特定の論理メモリビン内のアドレスを有し、前記データ項目に対する前記要求の結果前記第１のキャッシュ内にキャッシュミスが発生し、前記競合キャッシュ内にキャッシュヒットが発生するときにのみ、前記競合キャッシュがカウンタをインクリメントし、
前記カウンタが予め定められた値を越えると、オペレーティングシステムによって前記特定の論理メモリビン内のページをマッピングし直す
ことを特徴とする方法。
【００３９】
［実施の態様６］以下のステップを含むことを特徴とするコンピュータキャッシュシステムにおける包含の方法：
メモリ階層における相対的に低いレベルのキャッシュと相対的に高いレベルのキャッシュがプロセッサからの特定のデータ項目に対する要求を受け取る：前記相対的に低いレベルのキャッシュと前記相対的に高いレベルのキャッシュはそれぞれ前記特定のデータ項目と競合する競合データ項目のコピーを含む；
前記相対的に低いレベルのキャッシュが前記相対的に低いレベルのキャッシュから競合キャッシュに前記競合データ項目を追い出す；
前記相対的に高いレベルのキャッシュが前記相対的に高いレベルのキャッシュに前記競合データ項目が残ることを許容する。
【図面の簡単な説明】
【図１】本発明を含むコンピュータシステムのブロック図。
【図２】本発明及びコンピュータシステムの関係部分をより詳細に示すブロック図。
【図３】キャッシュ内のデータ及びアドレスの位置を示す図１及び図２の一部分のブロック図。
【図４】図３において競合ミスが発生した後のデータの位置及び本発明の包含特性を示すブロック図。
【図５】図４において更に競合ミスが発生した後のデータの位置及び本発明の包含特性を示すブロック図。
【図６】図５において更に競合ミスが発生した後のデータの位置及び競合カウンタ群と論理ビンの機能を示すブロック図。
【符号の説明】
100, 106：CPU
102, 108：L1データキャッシュ
104, 110：L2データキャッシュ
112：バス
114：メインメモリ
116：オペレーティングシステムソフトウエア
118、120：競合キャッシュ
202：CAM
204：データRAM
206：競合カウンタ群
208, 210：デジタルマルチプレクサ
212：デジタルデマルチプレクサ
304：アドレスインデクス
600：カウンタ
602：論理ビン
【図１】
0003795985.tif 000002
【図２】
0003795985.tif 000003
【図３】
0003795985.tif 000004
【図４】
0003795985.tif 000005
【図５】
0003795985.tif 000006
【図６】
0003795985.tif 000007