JPH09190382A - コンピュータメモリシステムの競合キャッシュ - Google Patents
コンピュータメモリシステムの競合キャッシュInfo
- Publication number
- JPH09190382A JPH09190382A JP8347400A JP34740096A JPH09190382A JP H09190382 A JPH09190382 A JP H09190382A JP 8347400 A JP8347400 A JP 8347400A JP 34740096 A JP34740096 A JP 34740096A JP H09190382 A JPH09190382 A JP H09190382A
- Authority
- JP
- Japan
- Prior art keywords
- cache
- contention
- line
- miss
- misses
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0864—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches using pseudo-associative means, e.g. set-associative or hashing
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0893—Caches characterised by their organisation or structure
- G06F12/0897—Caches characterised by their organisation or structure with two or more cache hierarchy levels
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】
【目的】ダイレクトマッピングやセットアソシアティヴ
方式のキャッシュメモリにおける、同一のキャッシュラ
インの要求の競合によるキャッシュのスラッシング防
止。 【構成・作用】キャッシュ１０４から追い出されたから
追い出されたキャッシュラインは競合キャッシュ１１８
中のデータＲＡＭ中に待避される。キャッシュ１０４へ
のアクセス要求は競合キャッシュでも処理され、競合キ
ャッシュ側でヒットしたらキャッシュ１０４の代わりに
競合キャッシュ側へのアクセスが行われる。
方式のキャッシュメモリにおける、同一のキャッシュラ
インの要求の競合によるキャッシュのスラッシング防
止。 【構成・作用】キャッシュ１０４から追い出されたから
追い出されたキャッシュラインは競合キャッシュ１１８
中のデータＲＡＭ中に待避される。キャッシュ１０４へ
のアクセス要求は競合キャッシュでも処理され、競合キ
ャッシュ側でヒットしたらキャッシュ１０４の代わりに
競合キャッシュ側へのアクセスが行われる。
Description
【０００１】
【産業上の利用分野】本発明は一般的にはデジタルコン
ピュータメモリシステムに関し、より詳細にはキャッシ
ュメモリシステムにおける競合ミスを低減するためのシ
ステムに関する。
ピュータメモリシステムに関し、より詳細にはキャッシ
ュメモリシステムにおける競合ミスを低減するためのシ
ステムに関する。
【０００２】
【従来技術及びその問題点】ほとんどのコンピュータシ
ステムには多階層のメモリシステムが採用され、この階
層の最高レベルには高速であるが容量の小さいメモリが
用いられ、最低レベルには低速であるが容量の大きいメ
モリが用いられる。通常、この階層構造にはキャッシュ
と呼ばれる小型の高速メモリが含まれ、これはプロセッ
サ集積回路に物理的に一体化されるか、あるいは高速化
のためにプロセッサに物理的に近接して設けられる。命
令キャッシュとデータキャッシュが別々に設けられるこ
ともある。また、キャッシュが多レベルに設けられるこ
ともある。
ステムには多階層のメモリシステムが採用され、この階
層の最高レベルには高速であるが容量の小さいメモリが
用いられ、最低レベルには低速であるが容量の大きいメ
モリが用いられる。通常、この階層構造にはキャッシュ
と呼ばれる小型の高速メモリが含まれ、これはプロセッ
サ集積回路に物理的に一体化されるか、あるいは高速化
のためにプロセッサに物理的に近接して設けられる。命
令キャッシュとデータキャッシュが別々に設けられるこ
ともある。また、キャッシュが多レベルに設けられるこ
ともある。
【０００３】メモリ階層はメモリに対して要求された項
目が要求時に高いパーセンテージで階層の最高レベルに
存在しなければ有用ではない。プロセッサがキャッシュ
の項目を要求し、その項目がキャッシュに存在した場
合、この事象をキャッシュヒットと呼ぶ。プロセッサが
キャッシュの項目を要求し、その項目がキャッシュに存
在しなかった場合、この事象をキャッシュミスと呼ぶ。
キャッシュミスが発生した場合、要求された項目はメモ
リ階層のより下にあるレベルから取り出される。これは
性能に大きな影響を与える。一般に、キャッシュミスの
発生とその影響を最少限にすることは、コンピュータシ
ステム全体の性能を左右する最も重要な設計パラメータ
の一部をなす。
目が要求時に高いパーセンテージで階層の最高レベルに
存在しなければ有用ではない。プロセッサがキャッシュ
の項目を要求し、その項目がキャッシュに存在した場
合、この事象をキャッシュヒットと呼ぶ。プロセッサが
キャッシュの項目を要求し、その項目がキャッシュに存
在しなかった場合、この事象をキャッシュミスと呼ぶ。
キャッシュミスが発生した場合、要求された項目はメモ
リ階層のより下にあるレベルから取り出される。これは
性能に大きな影響を与える。一般に、キャッシュミスの
発生とその影響を最少限にすることは、コンピュータシ
ステム全体の性能を左右する最も重要な設計パラメータ
の一部をなす。
【０００４】キャッシュとメモリ階層のその１つ下のレ
ベルとの間で転送可能な最小のメモリ量をラインと呼ぶ
（ブロックと呼ぶこともある）。通常、メモリはワード
（たとえば、32ビット/ワード）に構成され、１ライン
は通常複数のワード（たとえば、16ワード/ライン）か
らなる。また、メモリはページに分割することができ、
各ページは多数のラインからなる。
ベルとの間で転送可能な最小のメモリ量をラインと呼ぶ
（ブロックと呼ぶこともある）。通常、メモリはワード
（たとえば、32ビット/ワード）に構成され、１ライン
は通常複数のワード（たとえば、16ワード/ライン）か
らなる。また、メモリはページに分割することができ、
各ページは多数のラインからなる。
【０００５】もしキャッシュがあるラインアドレス全体
をデータとともに記憶するなら、任意のラインをそのキ
ャッシュの任意の場所に入れることができる。スペース
を節約するための代案として次のものがある。キャッシ
ュに128ラインが入るものとする。１２８ラインに対し
て、７ビットを使ってこのキャッシュ内のあるライン位
置を指定することができる。ラインアドレス中の最下位
の７ビットを用いてキャッシュ内のラインを指定すると
すれば、各物理的アドレス中の残りの上位側ビットの集
合だけがデータとともに記憶されなければならない。キ
ャッシュ内のラインを指定するのに用いられる数は通常
インデクスと呼ばれ、ラインの物理アドレスを定義する
のに必要な残りのビット集合は通常タグと呼ばれる。
をデータとともに記憶するなら、任意のラインをそのキ
ャッシュの任意の場所に入れることができる。スペース
を節約するための代案として次のものがある。キャッシ
ュに128ラインが入るものとする。１２８ラインに対し
て、７ビットを使ってこのキャッシュ内のあるライン位
置を指定することができる。ラインアドレス中の最下位
の７ビットを用いてキャッシュ内のラインを指定すると
すれば、各物理的アドレス中の残りの上位側ビットの集
合だけがデータとともに記憶されなければならない。キ
ャッシュ内のラインを指定するのに用いられる数は通常
インデクスと呼ばれ、ラインの物理アドレスを定義する
のに必要な残りのビット集合は通常タグと呼ばれる。
【０００６】インデクス付けを行ったキャッシュにおい
ては、特定のアドレスを有する項目はインデクスによっ
て指定されるキャッシュ内の１つの場所にのみ入れるこ
とができる。更に、アドレス空間内の同一のインデクス
ビットを有する各項目は潜在的にはそのキャッシュ内の
同じラインスペースを必要とする。従って、キャッシュ
内の既存のラインと同じスペースを必要とする新たなラ
インがフェッチされ、その既存のラインはキャッシュ内
に残らなければならない場合がある。この状況を競合(c
onflict)と呼び、次により詳細に説明する。
ては、特定のアドレスを有する項目はインデクスによっ
て指定されるキャッシュ内の１つの場所にのみ入れるこ
とができる。更に、アドレス空間内の同一のインデクス
ビットを有する各項目は潜在的にはそのキャッシュ内の
同じラインスペースを必要とする。従って、キャッシュ
内の既存のラインと同じスペースを必要とする新たなラ
インがフェッチされ、その既存のラインはキャッシュ内
に残らなければならない場合がある。この状況を競合(c
onflict)と呼び、次により詳細に説明する。
【０００７】あるラインがキャッシュ内の１つの場所に
しか存在しえない場合、そのキャッシュはダイレクトマ
ッピングされているものと言われる（また、連想度が低
いと言われる）。他の設計では、キャッシュが、それぞ
れが２ライン以上を有するセット群に構成されることが
ある。あるラインをこのようなセット群のうちの１つに
しか入れることができない場合、そのキャッシュはセッ
トアソシアティヴであるとされる。あるラインをキャッ
シュの任意の場所に入れることができる場合、そのキャ
ッシュはフルアソシアティヴであると言われる。一般
に、連想度の低いキャッシュは連想度の高いキャッシュ
より単純、高速であり、必要なスペースも小さい。しか
し、ダイレクトマッピングされたキャッシュ、あるいは
他の連想度の低いキャッシュは、次に説明する競合に起
因する性能上の問題点を有する。
しか存在しえない場合、そのキャッシュはダイレクトマ
ッピングされているものと言われる（また、連想度が低
いと言われる）。他の設計では、キャッシュが、それぞ
れが２ライン以上を有するセット群に構成されることが
ある。あるラインをこのようなセット群のうちの１つに
しか入れることができない場合、そのキャッシュはセッ
トアソシアティヴであるとされる。あるラインをキャッ
シュの任意の場所に入れることができる場合、そのキャ
ッシュはフルアソシアティヴであると言われる。一般
に、連想度の低いキャッシュは連想度の高いキャッシュ
より単純、高速であり、必要なスペースも小さい。しか
し、ダイレクトマッピングされたキャッシュ、あるいは
他の連想度の低いキャッシュは、次に説明する競合に起
因する性能上の問題点を有する。
【０００８】ダイレクトマッピングされたキャッシュあ
るいは他の連想度の低いキャッシュにおいては、新しい
ラインが既存のラインと同じスペースを必要とすること
がある。すなわち、ラインを無作為に置換したり、最近
もっとも長期間使用されていなかったラインを置換する
かわりに、この新しいラインがキャッシュ内の同じイン
デクスを有するラインを置換する。置換されたラインは
有用であったり、またキャッシュに残る必要がある場合
がある。有用なラインが同じインデクスを有するライン
で置換されたことに起因するミスを競合ミスと呼ぶ。ソ
フトウエアによっては、第１のラインから第２のライン
への置換が起こると、その後すぐに第２のラインが第１
のラインでまた置換されてしまうものもある。このよう
な単一のキャッシュラインでのスラッシングは、キャッ
シュサイズがその特定のソフトウエアに適当なものであ
ってもシステム性能の低下につながることがある。そこ
で、競合ミスに起因するシステム性能に対する悪影響を
最小限にしながら、連想度の低いキャッシュに固有の速
度及びスペース上の利点を生かすことが必要とされる。
るいは他の連想度の低いキャッシュにおいては、新しい
ラインが既存のラインと同じスペースを必要とすること
がある。すなわち、ラインを無作為に置換したり、最近
もっとも長期間使用されていなかったラインを置換する
かわりに、この新しいラインがキャッシュ内の同じイン
デクスを有するラインを置換する。置換されたラインは
有用であったり、またキャッシュに残る必要がある場合
がある。有用なラインが同じインデクスを有するライン
で置換されたことに起因するミスを競合ミスと呼ぶ。ソ
フトウエアによっては、第１のラインから第２のライン
への置換が起こると、その後すぐに第２のラインが第１
のラインでまた置換されてしまうものもある。このよう
な単一のキャッシュラインでのスラッシングは、キャッ
シュサイズがその特定のソフトウエアに適当なものであ
ってもシステム性能の低下につながることがある。そこ
で、競合ミスに起因するシステム性能に対する悪影響を
最小限にしながら、連想度の低いキャッシュに固有の速
度及びスペース上の利点を生かすことが必要とされる。
【０００９】ダイレクトマッピングされたキャッシュに
おける競合ミスの影響を低減する方法の１つに、小さな
フルアソシアティヴ２次キャッシュを追加する方法があ
る。たとえば、Proceedings of the 17th Annual Inter
national Symposium On Computer Architecture（1990
年５月）、364-373ページのJouppi、N.P.の“Improving
Direct-Mapped Cache Performance by the Addition o
f a Small Fully-Associative Cache and Prefetch Buf
fers”及び米国特許5,261,066号を参照されたい。Joupp
iはミスキャッシュと呼ばれる小さな（２ないし５ライ
ンの）のフルアソシアティヴキャッシュを追加すること
を提案している。１次キャッシュ内にキャッシュミスが
発生した場合、要求された項目は１次キャッシュとミス
キャッシュの両方に入れられる。ミスキャッシュに入れ
られた項目は最近もっとも長い間使用されていなかった
項目に置き換わる。改良点としてJouppiが提案している
ことは、小さな２次キャッシュに、要求されたラインの
代わりにミスによる置換のために犠牲になったラインを
入れることであり、このような２次キャッシュをビクテ
ィムキャッシュと呼ぶ。他の設計では、アシストキャッ
シュと呼ばれる先入れ先出し置き換えを行う小さな追加
キャッシュが、Digest of Papers Spring COMPCON 94
（1994年）、373-382ページのKurpanek, G他の“PA720
0; A PA-RISC Processore With Integrated High Perfo
rmance MP Bus Interface”に開示されている。
おける競合ミスの影響を低減する方法の１つに、小さな
フルアソシアティヴ２次キャッシュを追加する方法があ
る。たとえば、Proceedings of the 17th Annual Inter
national Symposium On Computer Architecture（1990
年５月）、364-373ページのJouppi、N.P.の“Improving
Direct-Mapped Cache Performance by the Addition o
f a Small Fully-Associative Cache and Prefetch Buf
fers”及び米国特許5,261,066号を参照されたい。Joupp
iはミスキャッシュと呼ばれる小さな（２ないし５ライ
ンの）のフルアソシアティヴキャッシュを追加すること
を提案している。１次キャッシュ内にキャッシュミスが
発生した場合、要求された項目は１次キャッシュとミス
キャッシュの両方に入れられる。ミスキャッシュに入れ
られた項目は最近もっとも長い間使用されていなかった
項目に置き換わる。改良点としてJouppiが提案している
ことは、小さな２次キャッシュに、要求されたラインの
代わりにミスによる置換のために犠牲になったラインを
入れることであり、このような２次キャッシュをビクテ
ィムキャッシュと呼ぶ。他の設計では、アシストキャッ
シュと呼ばれる先入れ先出し置き換えを行う小さな追加
キャッシュが、Digest of Papers Spring COMPCON 94
（1994年）、373-382ページのKurpanek, G他の“PA720
0; A PA-RISC Processore With Integrated High Perfo
rmance MP Bus Interface”に開示されている。
【００１０】複数レベルのキャッシュがある場合、低レ
ベルのキャッシュは通常高レベルのキャッシュより大き
く、また低レベルのキャッシュは通常高レベルのキャッ
シュにあるすべての情報を含んでいる。低レベルのキャ
ッシュが高レベルのキャッシュにある情報のすべてを含
んでいるとき、この低レベルのキャッシュは包含性を有
するといわれる。包含性の主な利点は、キャッシュメモ
リ内の項目が階層構造の他の場所にある項目と同じであ
るかどうかを判定するためのチェック（コヒーレンシー
チェックと呼ばれる）が必要であるとき、最低レベルの
キャッシュだけをチェックすればよいことにある。一般
に、上述したビクティムキャッシュあるいはアシストキ
ャッシュを有するシステムでは、低レベルのキャッシュ
からビクティムキャッシュあるいはアシストキャッシュ
に項目が移されたとき、それより高レベルのキャッシュ
内の対応する項目がその高レベルのキャッシュから除去
される。この場合、置換の犠牲となったこの項目が再度
要求されると、高レベルのキャッシュにキャッシュミス
が発生し、性能上の影響が生じる。
ベルのキャッシュは通常高レベルのキャッシュより大き
く、また低レベルのキャッシュは通常高レベルのキャッ
シュにあるすべての情報を含んでいる。低レベルのキャ
ッシュが高レベルのキャッシュにある情報のすべてを含
んでいるとき、この低レベルのキャッシュは包含性を有
するといわれる。包含性の主な利点は、キャッシュメモ
リ内の項目が階層構造の他の場所にある項目と同じであ
るかどうかを判定するためのチェック（コヒーレンシー
チェックと呼ばれる）が必要であるとき、最低レベルの
キャッシュだけをチェックすればよいことにある。一般
に、上述したビクティムキャッシュあるいはアシストキ
ャッシュを有するシステムでは、低レベルのキャッシュ
からビクティムキャッシュあるいはアシストキャッシュ
に項目が移されたとき、それより高レベルのキャッシュ
内の対応する項目がその高レベルのキャッシュから除去
される。この場合、置換の犠牲となったこの項目が再度
要求されると、高レベルのキャッシュにキャッシュミス
が発生し、性能上の影響が生じる。
【００１１】ダイレクトマッピングされたキャッシュ内
での競合ミスの影響を低減する他の方法として、競合ミ
スのアドレス分布をモニタし、メモリページングをマッ
ピングし直す方法がある。オペレーティングシステムが
キャッシュ競合の分布に関する情報を持っていれば、他
のページと競合するページをこのような競合のないペー
ジにマッピングし直すことができる。このような再マッ
ピングは静的（実行の前に判定される）でも動的（ソフ
トウエアの実行中の競合ミスに基づいて変更する）でも
よい。静的な方法は、ページのアドレス変換（ページマ
ッピング）を決定するとき、オペレーテンィグシステム
は所与のキャッシュラインにマッピングされるページの
数を知っていると想定している。静的な方法の例として
は、ACMTransactions on Computer Systems、Vol. No.
4、（1992年11月）338-359ページのKesslaer R.他の“P
age Placement Algorithms for Large Real-Indexed Ca
ches”を参照されたい。動的なページリマッピングの例
としては、ASLOS VI Proceedings （1994年１０月）、1
58-170ページのBershad B.他の“Avoiding Conflict Mi
sses Dynamically in Large Direct Mapped Caches”を
参照されたい。Bershad他の場合、キャッシュミスの履
歴を検出及び記録する（キャッシュミスルックアサイド
バッファと呼ばれる）追加ハードウエアが設けられる。
キャッシュミスはページ毎に検出される。ミスの多いペ
ージは異なる物理アドレスにマッピングし直される。キ
ャッシュミスルックアサイドバッファにはキャッシュミ
スから連想的に検索されたページ番号タグが記憶され
る。また、このバッファはカウンタを含む。キャッシュ
ミスが検出され、このバッファ内にそのページ番号タグ
がすでに存在する場合、対応するカウンタがインクリメ
ントされる。キャッシュミスが検出され、そのページ番
号タグがこのバッファに存在しない場合、最近もっとも
長い間使用されていなかったアドレスが置換される。カ
ウンタがあるしきい値を越えると、このバッファは割り
込みを発生し、オペレーティングシステムがこの割り込
みカウンタに対応するページをマッピングし直す。
での競合ミスの影響を低減する他の方法として、競合ミ
スのアドレス分布をモニタし、メモリページングをマッ
ピングし直す方法がある。オペレーティングシステムが
キャッシュ競合の分布に関する情報を持っていれば、他
のページと競合するページをこのような競合のないペー
ジにマッピングし直すことができる。このような再マッ
ピングは静的（実行の前に判定される）でも動的（ソフ
トウエアの実行中の競合ミスに基づいて変更する）でも
よい。静的な方法は、ページのアドレス変換（ページマ
ッピング）を決定するとき、オペレーテンィグシステム
は所与のキャッシュラインにマッピングされるページの
数を知っていると想定している。静的な方法の例として
は、ACMTransactions on Computer Systems、Vol. No.
4、（1992年11月）338-359ページのKesslaer R.他の“P
age Placement Algorithms for Large Real-Indexed Ca
ches”を参照されたい。動的なページリマッピングの例
としては、ASLOS VI Proceedings （1994年１０月）、1
58-170ページのBershad B.他の“Avoiding Conflict Mi
sses Dynamically in Large Direct Mapped Caches”を
参照されたい。Bershad他の場合、キャッシュミスの履
歴を検出及び記録する（キャッシュミスルックアサイド
バッファと呼ばれる）追加ハードウエアが設けられる。
キャッシュミスはページ毎に検出される。ミスの多いペ
ージは異なる物理アドレスにマッピングし直される。キ
ャッシュミスルックアサイドバッファにはキャッシュミ
スから連想的に検索されたページ番号タグが記憶され
る。また、このバッファはカウンタを含む。キャッシュ
ミスが検出され、このバッファ内にそのページ番号タグ
がすでに存在する場合、対応するカウンタがインクリメ
ントされる。キャッシュミスが検出され、そのページ番
号タグがこのバッファに存在しない場合、最近もっとも
長い間使用されていなかったアドレスが置換される。カ
ウンタがあるしきい値を越えると、このバッファは割り
込みを発生し、オペレーティングシステムがこの割り込
みカウンタに対応するページをマッピングし直す。
【００１２】ビクティムキャッシュとアシストキャッシ
ュは、競合ミスが比較的短い時間間隔内に発生する場合
にはこれを低減する。長い時間間隔内に発生するミスに
ついては、被置換ラインはソフトウエアが次にそれを要
求する前にビクティムキャッシュから置換されるかもし
れない。動的ページリマッピングは競合ミスを低減する
が比較的時間がかかる。リマッピングが行なわれる前に
ソフトウエアコンテキストが変わる可能性がある。更
に、動的なページリマッピングは、ミスの多いページを
マッピングし直すための多数の代替ターゲットページを
提供するための大きなキャッシュを必要とする。最後
に、Bershad他の具体的実施態様においては、すべての
キャッシュミスがカウントされ、キャッシュからライン
を置換しないミスまでカウントされる。小さいフルアソ
シアティブ補助キャッシュによって提供される競合ミス
の短期的な影響の低減及び動的ページリマッピングによ
るミスの低減更にその他の利点を有するダイレクトマッ
ピングされたキャッシュの速度及びスペース上の利点を
提供する改善されたキャッシュシステムが必要とされて
いる。
ュは、競合ミスが比較的短い時間間隔内に発生する場合
にはこれを低減する。長い時間間隔内に発生するミスに
ついては、被置換ラインはソフトウエアが次にそれを要
求する前にビクティムキャッシュから置換されるかもし
れない。動的ページリマッピングは競合ミスを低減する
が比較的時間がかかる。リマッピングが行なわれる前に
ソフトウエアコンテキストが変わる可能性がある。更
に、動的なページリマッピングは、ミスの多いページを
マッピングし直すための多数の代替ターゲットページを
提供するための大きなキャッシュを必要とする。最後
に、Bershad他の具体的実施態様においては、すべての
キャッシュミスがカウントされ、キャッシュからライン
を置換しないミスまでカウントされる。小さいフルアソ
シアティブ補助キャッシュによって提供される競合ミス
の短期的な影響の低減及び動的ページリマッピングによ
るミスの低減更にその他の利点を有するダイレクトマッ
ピングされたキャッシュの速度及びスペース上の利点を
提供する改善されたキャッシュシステムが必要とされて
いる。
【００１３】
【概要】改良されたキャッシュシステム（競合キャッシ
ュと呼ぶ）は早い立ち上がりとキャッシュミスの低減の
ためのハードウエア及びオペレーティングシステムが動
的ページリマッピングを用いてキャッシュ競合を除去す
るのを助けるカウンタを有する。短期の立ち上げと長期
的な除去との両方を提供することには相乗効果がある。
これは、動的ページリマッピングによって一部の競合ミ
スが除去されると、より時間的に離れた他の競合ミスを
検出し、これを許容し、最終的には同じ処理を用いて除
去することができるためである。更に、補助キャッシュ
とカウンタを組み合わせることによってある程度のハー
ドウエアの共用が可能になる。本発明の一側面では、多
レベルのキャッシングを行なうシステムにおいて、競合
キャッシュを最高レベルキャッシュについての改善され
た包含法と組み合わせて、最高レベルキャッシュについ
ての一層のミスの低減を行なう。
ュと呼ぶ）は早い立ち上がりとキャッシュミスの低減の
ためのハードウエア及びオペレーティングシステムが動
的ページリマッピングを用いてキャッシュ競合を除去す
るのを助けるカウンタを有する。短期の立ち上げと長期
的な除去との両方を提供することには相乗効果がある。
これは、動的ページリマッピングによって一部の競合ミ
スが除去されると、より時間的に離れた他の競合ミスを
検出し、これを許容し、最終的には同じ処理を用いて除
去することができるためである。更に、補助キャッシュ
とカウンタを組み合わせることによってある程度のハー
ドウエアの共用が可能になる。本発明の一側面では、多
レベルのキャッシングを行なうシステムにおいて、競合
キャッシュを最高レベルキャッシュについての改善され
た包含法と組み合わせて、最高レベルキャッシュについ
ての一層のミスの低減を行なう。
【００１４】一実施例において、連想度の低いキャッシ
ュに競合ミスが発生すると、置換された項目は競合キャ
ッシュに移される。オペレーティングシステムはこの連
想度の低いキャッシュを論理的にビンに区分されたもの
とみなす。１つのビンのアドレス範囲は１ページあるい
は複数ページである。連想度の低いキャッシュ内の各論
理ビンは競合キャッシュ内に対応するカウンタを有す
る。あるアドレスがこの連想度の低いキャッシュにはな
く競合キャッシュ内でヒットした場合、ソフトウエアは
競合により連想度の低いキャッシュから追い出されたラ
インにアクセスし直す。このような競合ミスが発生する
たびに対応するビンカウンタがインクリメントされる。
ュに競合ミスが発生すると、置換された項目は競合キャ
ッシュに移される。オペレーティングシステムはこの連
想度の低いキャッシュを論理的にビンに区分されたもの
とみなす。１つのビンのアドレス範囲は１ページあるい
は複数ページである。連想度の低いキャッシュ内の各論
理ビンは競合キャッシュ内に対応するカウンタを有す
る。あるアドレスがこの連想度の低いキャッシュにはな
く競合キャッシュ内でヒットした場合、ソフトウエアは
競合により連想度の低いキャッシュから追い出されたラ
インにアクセスし直す。このような競合ミスが発生する
たびに対応するビンカウンタがインクリメントされる。
【００１５】多レベルキャッシュ階層を有する一実施例
において、最高レベルのキャッシュ（L1キャッシュ）は
下のレベルの連想度の低いキャッシュ（L2キャッシュ）
と競合キャッシュとの合併集合の部分集合である。すな
わち、下のレベルのキャッシュから競合キャッシュに追
い出されたラインは最高レベルのキャッシュに残ること
ができる。この新しい包含特性によって、競合ミスがあ
る状況下での最高レベルのキャッシュ内のキャッシュラ
インが寿命が伸び、最高レベルキャッシュの性能が向上
する。更に、最高レベルキャッシュ（及び競合キャッシ
ュ）は下のレベルのキャッシュ内の同じインデクスにマ
ッピングされるラインをいくつか持つことができ、これ
によって下のレベルのキャッシュのスラッシングの可能
性が低減される。
において、最高レベルのキャッシュ（L1キャッシュ）は
下のレベルの連想度の低いキャッシュ（L2キャッシュ）
と競合キャッシュとの合併集合の部分集合である。すな
わち、下のレベルのキャッシュから競合キャッシュに追
い出されたラインは最高レベルのキャッシュに残ること
ができる。この新しい包含特性によって、競合ミスがあ
る状況下での最高レベルのキャッシュ内のキャッシュラ
インが寿命が伸び、最高レベルキャッシュの性能が向上
する。更に、最高レベルキャッシュ（及び競合キャッシ
ュ）は下のレベルのキャッシュ内の同じインデクスにマ
ッピングされるラインをいくつか持つことができ、これ
によって下のレベルのキャッシュのスラッシングの可能
性が低減される。
【００１６】本発明の諸相において、ビクティムキャッ
シングと動的リマッピングの相乗作用及び多レベルキャ
ッシュ階層における新しい包含特性によって、これら２
つの方法の両方の性能上の利点及びそれ以外の性能上の
利点が提供される。競合キャッシュカウンタは、すべて
のミスをカウントせず競合ミスのみをカウントするため
に、従来の動的リマッピングシステムに比べて動的リマ
ッピングを行なうためのより有効な情報をオペーレーテ
ィングシステムに供給する。多レベルキャッシュ階層構
造において、競合キャッシュに包含特性を持たせること
によって、ビクティムキャッシュに比べてより優れた性
能を得ることができる。これは置換されたキャッシュラ
インが最高レベルのキャッシュにとどまることができる
ためである。本実施例では、新規な設計によってキャッ
シュと計数にタグメモリを共用できるようにすることに
よって、キャッシング及び計数機能の組み合わせに必要
なハードウエアを低減している。
シングと動的リマッピングの相乗作用及び多レベルキャ
ッシュ階層における新しい包含特性によって、これら２
つの方法の両方の性能上の利点及びそれ以外の性能上の
利点が提供される。競合キャッシュカウンタは、すべて
のミスをカウントせず競合ミスのみをカウントするため
に、従来の動的リマッピングシステムに比べて動的リマ
ッピングを行なうためのより有効な情報をオペーレーテ
ィングシステムに供給する。多レベルキャッシュ階層構
造において、競合キャッシュに包含特性を持たせること
によって、ビクティムキャッシュに比べてより優れた性
能を得ることができる。これは置換されたキャッシュラ
インが最高レベルのキャッシュにとどまることができる
ためである。本実施例では、新規な設計によってキャッ
シュと計数にタグメモリを共用できるようにすることに
よって、キャッシング及び計数機能の組み合わせに必要
なハードウエアを低減している。
【００１７】
【発明の実施例】図１には多レベルキャッシュメモリ階
層を有するコンピュータシステムの一例を示す。一般
に、キャッシュメモリ及びメインメモリのためのアドレ
スバス構造及びデータバス構造はさまざまであるが、本
発明はその態様には無関係である。図１に示すシステム
では、第１の中央処理装置（CPU）100はその一部として
一体化された第１レベルのデータキャッシュメモリ（L1
データキャッシュ）102を含む。第２レベルのデータキ
ャッシュ（L2データキャッシュ）104は外部に設けられ
たものとして示されている。また、CPU 100には別個の
命令キャッシュ（図示せず）を設けることもできる。図
１において、第２のCPU 106もまた第１レベルのデータ
キャッシュ108及び第２レベルのデータキャッシュ110を
含む。これら２つのCPUはバス112によって接続されてい
る。これら２つのCPUは１つあるいは複数のメインメモ
リ114を共用する。また、このシステムには仮想アドレ
スを実アドレスに変換するためのトランザクションルッ
クアサイドバッファ（TLB）（図示せず）を設けること
もできる。オペレーティングシステムソフトウエア116
はメインメモリ114内に設けられる。
層を有するコンピュータシステムの一例を示す。一般
に、キャッシュメモリ及びメインメモリのためのアドレ
スバス構造及びデータバス構造はさまざまであるが、本
発明はその態様には無関係である。図１に示すシステム
では、第１の中央処理装置（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及び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が設けられる。
示す。競合キャッシュ118にはアドレスタグを記憶する
ための内容アドレシング可能メモリ（CAM）202、データ
ラインを記憶するためのデータRAM 204及び競合ミスを
カウントするための競合カウンタ群206が設けられる。
競合カウンタ群206にはL2キャッシュ104内の各論理ビン
毎に１つのカウンタがある。更に、デジタルマルチプレ
クサ208及び210が設けられ、また実施態様によってはデ
ジタルデマルチプレクサ212が設けられる。
【００２０】図３には、L1キャッシュ102、L2キャッシ
ュ104、競合キャッシュ内のCAM 202及びRAM 204、及びL
1キャッシュ102内の例としてのデータ項目ITEM 1 300を
示す。図３から図６において、L1キャッシュ102は２方
向連想キャッシュとして示されている。これは説明の都
合上に過ぎない。L1キャッシュ102の具体的構成は本発
明にとって重要ではない。L2キャッシュ104にもITEM1 3
00がそのアドレスタグTAG1 302とともに含まれている。
L2キャッシュ104内のITEM1 300のロケーションはアドレ
スインデクスINDEX1 304によって決定されるロケーショ
ンに制限される。
ュ104、競合キャッシュ内のCAM 202及びRAM 204、及びL
1キャッシュ102内の例としてのデータ項目ITEM 1 300を
示す。図３から図６において、L1キャッシュ102は２方
向連想キャッシュとして示されている。これは説明の都
合上に過ぎない。L1キャッシュ102の具体的構成は本発
明にとって重要ではない。L2キャッシュ104にもITEM1 3
00がそのアドレスタグTAG1 302とともに含まれている。
L2キャッシュ104内のITEM1 300のロケーションはアドレ
スインデクスINDEX1 304によって決定されるロケーショ
ンに制限される。
【００２１】図４にはL2キャッシュ104からある項目が
追い出された後の図３と同じブロックを示す。L2キャッ
シュ104からあるラインが追い出されると、この追い出
されたラインのアドレスがCAM 202に記憶され、そのデ
ータがデータRAM 204に記憶される。図４において、ITE
M2 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内でも変更されていなければならないことに
注意されたい。そのかわりに、コヒーレンスチェックで
３つのキャッシュをすべてチェックすることもできる。
追い出された後の図３と同じブロックを示す。L2キャッ
シュ104からあるラインが追い出されると、この追い出
されたラインのアドレスがCAM 202に記憶され、そのデ
ータがデータRAM 204に記憶される。図４において、ITE
M2 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キャッシュ10
4から競合キャッシュ118に追い出されるとき、L1キャッ
シュ102には（新しいラインを加える余裕があれば）対
応するラインが（L1キャッシュ102に存在すれば）残
る。図４において、ITEM1 300はL2キャッシュ104から追
い出されているが、L1キャッシュ102にはITEM1 300が残
っていることに注意されたい。
本発明の包含特性が示されている。従来技術の部分で説
明したように、多レベルキャッシュシステムを有する多
くのシステムにおいて、各キャッシュはそれより高いレ
ベルのキャッシュのすべてのラインを含む。通常、低レ
ベルキャッシュ内でミスが発生すると、最高レベルキャ
ッシュ内の対応するラインが追い出される。その結果、
通常高レベルのキャッシュは低レベルのキャッシュより
はるかに高速であるため性能上の損失が発生する。図４
に戻って、従来のシステムでは、ITEM2 400がL2キャッ
シュ104に入れられ、ITEM1 300が置換されると、L1キャ
ッシュ102内のITEM1 300が除去される。これはL2はL1内
のすべての項目を含んでいなければならないためであ
る。これに対して、図３から図６に示す２レベルのシス
テムでは、L2キャッシュ104はL1キャッシュ102のすべて
のラインを含んでいるわけではない。その代わり、本発
明の一側面によれば、L2キャッシュ104と競合キャッシ
ュ（図１及び図２の118）の合併集合がL1キャッシュ102
のすべてのラインを含む。あるラインがL2キャッシュ10
4から競合キャッシュ118に追い出されるとき、L1キャッ
シュ102には（新しいラインを加える余裕があれば）対
応するラインが（L1キャッシュ102に存在すれば）残
る。図４において、ITEM1 300はL2キャッシュ104から追
い出されているが、L1キャッシュ102にはITEM1 300が残
っていることに注意されたい。
【００２３】図５に示すように、あるラインをL1キャッ
シュ102から追い出して新しいラインを追加する場所を
作ることができる。図５において、新しいデータ項目IT
EM3500がL1キャッシュ102及びL2キャッシュ104に入れら
れた。ITEM3 500はITEM2 400をL2キャッシュ104（同じ
インデクス）から追い出し、ITEM1 300をL1キャッシュ1
02から追い出す（たとえば、どのラインが最近もっとも
長い間使用されていなかったかに基づく置換）。図５に
おいて、ITEM2 400はL2キャッシュ104から追い出される
が、L1キャッシュ102には残ることが許されていること
に注意されたい。
シュ102から追い出して新しいラインを追加する場所を
作ることができる。図５において、新しいデータ項目IT
EM3500がL1キャッシュ102及びL2キャッシュ104に入れら
れた。ITEM3 500はITEM2 400をL2キャッシュ104（同じ
インデクス）から追い出し、ITEM1 300をL1キャッシュ1
02から追い出す（たとえば、どのラインが最近もっとも
長い間使用されていなかったかに基づく置換）。図５に
おいて、ITEM2 400はL2キャッシュ104から追い出される
が、L1キャッシュ102には残ることが許されていること
に注意されたい。
【００２４】図６に示すように、L1キャッシュ102から
あるラインを追い出して競合キャッシュ118からのライ
ンを入れる場所を作ることができる。あるいは、競合キ
ャッシュ118からあるラインを追い出してL2キャッシュ1
04から新たに追い出させるラインのための場所を作る場
合に、競合キャッシュから追い出されるラインをL1キャ
ッシュ102から追い出すことができる。競合キャッシュ1
18内でヒットが起こった場合、そのラインがL1キャッシ
ュ102にキャッシュできる場合にはL1キャッシュ102に持
ち上げられる。図６において、ITEM1 300がL1キャッシ
ュ102に持ち上げられてITEM2 400を置換していることに
注意されたい。
あるラインを追い出して競合キャッシュ118からのライ
ンを入れる場所を作ることができる。あるいは、競合キ
ャッシュ118からあるラインを追い出してL2キャッシュ1
04から新たに追い出させるラインのための場所を作る場
合に、競合キャッシュから追い出されるラインをL1キャ
ッシュ102から追い出すことができる。競合キャッシュ1
18内でヒットが起こった場合、そのラインがL1キャッシ
ュ102にキャッシュできる場合にはL1キャッシュ102に持
ち上げられる。図６において、ITEM1 300がL1キャッシ
ュ102に持ち上げられてITEM2 400を置換していることに
注意されたい。
【００２５】上述したような本発明の包含方式によっ
て、L2キャッシュ104内に競合ミスがある状況下でL1キ
ャッシュ102内の一部のキャッシュラインの寿命が延
び、それによってL1キャッシュ102の性能が向上する。
図５及び図６において、L1キャッシュ102と競合キャッ
シュ118はそれぞれ、L2キャッシュ104内の同じインデク
スにマッピングされる少なくとも２つの項目を含み、そ
れによってL2キャッシュ104のスラッシングが低減され
ていることに注意されたい。
て、L2キャッシュ104内に競合ミスがある状況下でL1キ
ャッシュ102内の一部のキャッシュラインの寿命が延
び、それによってL1キャッシュ102の性能が向上する。
図５及び図６において、L1キャッシュ102と競合キャッ
シュ118はそれぞれ、L2キャッシュ104内の同じインデク
スにマッピングされる少なくとも２つの項目を含み、そ
れによってL2キャッシュ104のスラッシングが低減され
ていることに注意されたい。
【００２６】また、図６は、ページのリマッピングを助
けるために競合キャッシュ118内のカウンタ206を用いる
ことを示している。図６にはプロセッサからのITEM1 30
0に対する次の要求に続いて発生する図５に示すデータ
位置の変更が示されている。L2キャッシュ104にないア
ドレスが競合キャッシュ118内のCAM 202中のアドレスと
比較され、要求されたラインが以前に追い出されている
かどうかが調べられる。図５において、ITEM1 300は競
合キャッシュ118にあり、L2キャッシュ104からの追い出
しがあったことを示していることに注意されたい。要求
されたラインが競合キャッシュ118中にあった場合は、
そのラインは競合キャッシュからマルチプレクサ210
（図２）を介してプロセッサに供給される。ヒット/ミ
ス信号（図示せず）を用いてプロセッサ（図１の100）
にヒットの発生が知らせられる。L2キャッシュ104でミ
スがあり、それが競合キャッシュ118でヒットした場
合、これはL2キャッシュ104内の（そのラインについて
の）キャッシュインデクスに競合が存在することを意味
する。あるラインがL2キャッシュ104にはなかったが競
合キャッシュ118ではヒットしたとき、競合カウンタ群2
06中の対応するカウンタがインクリメントされ、L2キャ
ッシュ104内のその特定の論理キャッシュビンに関する
競合を表わす。オペレーティングシステム（図１の11
6）はL2キャッシュ104をビン（ビンはメモリの１つある
いは複数のページ）に論理的に分割されたものとみなす
ことを思い出されたい。図６において、L2キャッシュ10
4はオペレーティングシステムによって論理ビンBIN1 60
2等の複数のビンに分割されている。論理ビンBIN1 602
内のページはITEM2 400のINDEX1 304を含む。図６にお
いて、COUNTER1 600は論理ビンBIN1 602に対応する。競
合カウンタヒット/ミス信号（図示せず）は（図２に示
すデマルチプレクサ212を用いて）適切な競合カウンタ6
00のインクリメント信号として用いられる。オペレーテ
ィングシステム（図１の116）は競合カウンタ群206中の
すべてのカウンタの内容を読み出すことができる。
けるために競合キャッシュ118内のカウンタ206を用いる
ことを示している。図６にはプロセッサからのITEM1 30
0に対する次の要求に続いて発生する図５に示すデータ
位置の変更が示されている。L2キャッシュ104にないア
ドレスが競合キャッシュ118内のCAM 202中のアドレスと
比較され、要求されたラインが以前に追い出されている
かどうかが調べられる。図５において、ITEM1 300は競
合キャッシュ118にあり、L2キャッシュ104からの追い出
しがあったことを示していることに注意されたい。要求
されたラインが競合キャッシュ118中にあった場合は、
そのラインは競合キャッシュからマルチプレクサ210
（図２）を介してプロセッサに供給される。ヒット/ミ
ス信号（図示せず）を用いてプロセッサ（図１の100）
にヒットの発生が知らせられる。L2キャッシュ104でミ
スがあり、それが競合キャッシュ118でヒットした場
合、これはL2キャッシュ104内の（そのラインについて
の）キャッシュインデクスに競合が存在することを意味
する。あるラインがL2キャッシュ104にはなかったが競
合キャッシュ118ではヒットしたとき、競合カウンタ群2
06中の対応するカウンタがインクリメントされ、L2キャ
ッシュ104内のその特定の論理キャッシュビンに関する
競合を表わす。オペレーティングシステム（図１の11
6）はL2キャッシュ104をビン（ビンはメモリの１つある
いは複数のページ）に論理的に分割されたものとみなす
ことを思い出されたい。図６において、L2キャッシュ10
4はオペレーティングシステムによって論理ビンBIN1 60
2等の複数のビンに分割されている。論理ビンBIN1 602
内のページはITEM2 400のINDEX1 304を含む。図６にお
いて、COUNTER1 600は論理ビンBIN1 602に対応する。競
合カウンタヒット/ミス信号（図示せず）は（図２に示
すデマルチプレクサ212を用いて）適切な競合カウンタ6
00のインクリメント信号として用いられる。オペレーテ
ィングシステム（図１の116）は競合カウンタ群206中の
すべてのカウンタの内容を読み出すことができる。
【００２７】競合キャッシュ118はデュアルポートある
いはフルラインバッファとし、競合キャッシュへの読み
出しと書き込みの同時アクセスができるようにするのが
好ましい。あるアクセスがL2キャッシュ104でミスした
場合、L2キャッシュ104内のミスしたインデクスにある
ラインはいかなるものでも競合キャッシュ118に移され
る。図６において、ITEM3（500）がL2キャッシュ104か
ら競合キャッシュ118に移されていることに注意された
い。L2キャッシュ104はミスしたが競合キャッシュ118が
ヒットした（それらのラインが異なる物理アドレスを持
っている）場合、L2キャッシュ104から競合キャッシュ1
18に１つのラインを書き込み、競合キャッシュ118から
１つのラインを読み出して実行中のアクセスに応えなけ
ればならない。図６において、プロセッサからの１つの
要求の結果、ITEM1 300が競合キャッシュ118からL1キャ
ッシュ102とL2キャッシュ104の両方に移され、ITEM2 40
0がL2キャッシュ104から競合キャッシュ118に移された
ことに注意されたい。好適には、最適な性能を得るため
に、競合キャッシュ118内の１つのエントリを空にして
新しいL2キャッシュラインのためにとっておき、古いラ
インを掃き出すのを待つことなくラインを競合キャッシ
ュ118に移動できるようにする。
いはフルラインバッファとし、競合キャッシュへの読み
出しと書き込みの同時アクセスができるようにするのが
好ましい。あるアクセスがL2キャッシュ104でミスした
場合、L2キャッシュ104内のミスしたインデクスにある
ラインはいかなるものでも競合キャッシュ118に移され
る。図６において、ITEM3（500）がL2キャッシュ104か
ら競合キャッシュ118に移されていることに注意された
い。L2キャッシュ104はミスしたが競合キャッシュ118が
ヒットした（それらのラインが異なる物理アドレスを持
っている）場合、L2キャッシュ104から競合キャッシュ1
18に１つのラインを書き込み、競合キャッシュ118から
１つのラインを読み出して実行中のアクセスに応えなけ
ればならない。図６において、プロセッサからの１つの
要求の結果、ITEM1 300が競合キャッシュ118からL1キャ
ッシュ102とL2キャッシュ104の両方に移され、ITEM2 40
0がL2キャッシュ104から競合キャッシュ118に移された
ことに注意されたい。好適には、最適な性能を得るため
に、競合キャッシュ118内の１つのエントリを空にして
新しいL2キャッシュラインのためにとっておき、古いラ
インを掃き出すのを待つことなくラインを競合キャッシ
ュ118に移動できるようにする。
【００２８】図３から図６において、図及び説明を簡略
化するために、アドレスタグ（たとえばTAG1 302）は各
種のキャッシュに渡って同一なもの（同一参照符号）と
して示されていることに注意されたい。しかし、一般的
には、アドレスタグの長さはキャッシュ毎に異なる。た
とえば、TAG1 302はITEM1 300のフルアドレスを構成す
るビットの部分集合である。L2キャッシュ104に記憶さ
れる部分集合はL1キャッシュ102あるいは競合キャッシ
ュ118に記憶される部分集合と異なるかもしれない。一
般に、それぞれのキャッシュは連想度の程度によって決
まる異なる物理的アドレス指定条件及び本発明の諸相に
は無関係な他のシステム条件を有する。
化するために、アドレスタグ（たとえばTAG1 302）は各
種のキャッシュに渡って同一なもの（同一参照符号）と
して示されていることに注意されたい。しかし、一般的
には、アドレスタグの長さはキャッシュ毎に異なる。た
とえば、TAG1 302はITEM1 300のフルアドレスを構成す
るビットの部分集合である。L2キャッシュ104に記憶さ
れる部分集合はL1キャッシュ102あるいは競合キャッシ
ュ118に記憶される部分集合と異なるかもしれない。一
般に、それぞれのキャッシュは連想度の程度によって決
まる異なる物理的アドレス指定条件及び本発明の諸相に
は無関係な他のシステム条件を有する。
【００２９】ある特定の実施例においては、L2キャッシ
ュ104は市販のSRAMによって外部に設けられ、制御回路
はプロセッサ100にその一部として集積化される。競合
キャッシュ118は比較的小さく、たとえば８ないし３２
のキャッシュラインを有する。競合キャッシュ118はL2
キャッシュ104と同じタイミングで並列アクセスが可能
である。
ュ104は市販のSRAMによって外部に設けられ、制御回路
はプロセッサ100にその一部として集積化される。競合
キャッシュ118は比較的小さく、たとえば８ないし３２
のキャッシュラインを有する。競合キャッシュ118はL2
キャッシュ104と同じタイミングで並列アクセスが可能
である。
【００３０】従来技術の項で説明したように、ミスキャ
ッシュ、ビクティムキャッシュ及びアシストキャッシュ
等のフルアソシアティヴバッファはダイレクトマッピン
グされたキャッシュの競合ミスを改善することができる
が、それは比較的短い期間に発生する競合ミスに限られ
る。容量が限られているため、置換されたラインはソフ
トウエアが次にそれを必要とする前にフルアソシアティ
ヴキャッシュから失われるかもしれない。ダイレクトマ
ッピングされるキャッシュにおけるより長い期間での競
合ミスはページリマッピングによって除去することがで
きる。異なるビンには当然異なるインデクスアドレスが
含まれるため、異なるキャッシュビンにマッピングされ
たページには競合ミスは発生しえない。オペレーティン
グシステムがキャッシュ競合の分布に関する情報を持っ
ている場合、オペレーティングシステムは競合するペー
ジをこのような競合のない他のキャッシュビンにマッピ
ングし直すことによって競合部分を除去することができ
る。競合キャッシュ118には、オペレーティングシステ
ムによる動的リマッピングのための競合カウンタ群が設
けられる。
ッシュ、ビクティムキャッシュ及びアシストキャッシュ
等のフルアソシアティヴバッファはダイレクトマッピン
グされたキャッシュの競合ミスを改善することができる
が、それは比較的短い期間に発生する競合ミスに限られ
る。容量が限られているため、置換されたラインはソフ
トウエアが次にそれを必要とする前にフルアソシアティ
ヴキャッシュから失われるかもしれない。ダイレクトマ
ッピングされるキャッシュにおけるより長い期間での競
合ミスはページリマッピングによって除去することがで
きる。異なるビンには当然異なるインデクスアドレスが
含まれるため、異なるキャッシュビンにマッピングされ
たページには競合ミスは発生しえない。オペレーティン
グシステムがキャッシュ競合の分布に関する情報を持っ
ている場合、オペレーティングシステムは競合するペー
ジをこのような競合のない他のキャッシュビンにマッピ
ングし直すことによって競合部分を除去することができ
る。競合キャッシュ118には、オペレーティングシステ
ムによる動的リマッピングのための競合カウンタ群が設
けられる。
【００３１】すべてのキャッシュミスがカウントされる
動的ページリマッピングによって競合ミスを低減すると
いう、他のシステムで開示されているカウンタとは異な
り、競合キャッシュ118内のカウンタは競合ミス、具体
的にはダイレクトマッピングされたL2キャッシュ104内
のミスであって競合キャッシュ118でヒットするミス、
のみをカウントする。キャッシュの競合を短期的には許
容することと長期的に除去することの両方を行なうこと
には相乗効果がある。というのは、動的ページリマッピ
ングによって一部の競合ミスが除去されると、より時間
的に離れた他の競合ミスを検出し、これを許容し、最終
的には同じ処理を用いて除去することができるからであ
る。たとえば、図６において、ITEM1 300に対するL2 10
4ミスは短期的に許容され、ITEM1のBIN1 602に対応する
カウンタ600があらかじめ定められたしきい値を越える
と、ITEM1に対応する仮想メモリページがスワップされ
る。更に、図２に示す設計では、２次キャッシュとカウ
ンタを組み合わせることによって、ハードウエア（たと
えば内容アドレシング可能メモリ202）の共用が可能に
なる。
動的ページリマッピングによって競合ミスを低減すると
いう、他のシステムで開示されているカウンタとは異な
り、競合キャッシュ118内のカウンタは競合ミス、具体
的にはダイレクトマッピングされたL2キャッシュ104内
のミスであって競合キャッシュ118でヒットするミス、
のみをカウントする。キャッシュの競合を短期的には許
容することと長期的に除去することの両方を行なうこと
には相乗効果がある。というのは、動的ページリマッピ
ングによって一部の競合ミスが除去されると、より時間
的に離れた他の競合ミスを検出し、これを許容し、最終
的には同じ処理を用いて除去することができるからであ
る。たとえば、図６において、ITEM1 300に対するL2 10
4ミスは短期的に許容され、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：論理ビン
Claims (1)
- 【請求項１】コンピュータにおけるキャッシュシステム
であって、 オペレーティングシステムによって複数のビンに論理的
に分割されたアドレススペースを有し、前記複数のビン
のうちの特定のビン内の特定のデータ項目に対する前記
コンピュータ内のプロセッサからの要求を受け取る第１
のキャッシュと、 前記第１のキャッシュに電子的に結合された競合キャッ
シュと、 前記複数のビンに１対１で対応する前記競合キャッシュ
内の複数のカウンタとを設け、 前記複数のカウンタのうち前記特定のビンに対応するカ
ウンタは前記特定のデータ項目に対する前記要求の結
果、前記第１のキャッシュにキャッシュミスが発生し、
前記競合キャッシュ内でキャッシュヒットが発生したと
きにのみインクリメントされることを特徴とするキャッ
シュシステム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/582,542 US5860095A (en) | 1996-01-02 | 1996-01-02 | Conflict cache having cache miscounters for a computer memory system |
| US582,542 | 1996-01-02 |
Publications (3)
| Publication Number | Publication Date |
|---|---|
| JPH09190382A true JPH09190382A (ja) | 1997-07-22 |
| JPH09190382A5 JPH09190382A5 (ja) | 2004-12-09 |
| JP3795985B2 JP3795985B2 (ja) | 2006-07-12 |
Family
ID=24329546
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP34740096A Expired - Fee Related JP3795985B2 (ja) | 1996-01-02 | 1996-12-26 | コンピュータメモリシステムの競合キャッシュ |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5860095A (ja) |
| JP (1) | JP3795985B2 (ja) |
Cited By (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1011049A3 (en) * | 1998-12-15 | 2001-03-14 | Nec Corporation | Cache system and cache processing method |
| US6792498B2 (en) | 2001-01-22 | 2004-09-14 | Hitachi, Ltd. | Memory system with mechanism for assisting a cache memory |
| JP2008016033A (ja) * | 2006-07-06 | 2008-01-24 | Internatl Business Mach Corp <Ibm> | 階層テーブルを管理するための方法およびコンピュータ・システム |
| JP2010079361A (ja) * | 2008-09-24 | 2010-04-08 | Nec Corp | プロセッサ、プロセッサのデータ処理方法、情報処理装置 |
| JP2012181863A (ja) * | 2004-10-21 | 2012-09-20 | Microsoft Corp | システムパフォーマンスを改善するための外部メモリデバイスの使用 |
| JP2012194742A (ja) * | 2011-03-16 | 2012-10-11 | Nec Engineering Ltd | リプレースメントデータメモリ装置、中央演算装置及びリプレースメントデータ処理方法 |
| JP2014067250A (ja) * | 2012-09-26 | 2014-04-17 | Nec Corp | メモリアクセス制御装置、メモリアクセス制御システム、及び、メモリアクセス制御方法 |
| JP2014209392A (ja) * | 2014-08-13 | 2014-11-06 | Ｎｅｃエンジニアリング株式会社 | リプレースメントデータメモリ装置、中央演算装置及びリプレースメントデータ処理用プログラム |
| US8914557B2 (en) | 2005-12-16 | 2014-12-16 | Microsoft Corporation | Optimizing write and wear performance for a memory |
| US9032151B2 (en) | 2008-09-15 | 2015-05-12 | Microsoft Technology Licensing, Llc | Method and system for ensuring reliability of cache data and metadata subsequent to a reboot |
| US9361183B2 (en) | 2008-09-19 | 2016-06-07 | Microsoft Technology Licensing, Llc | Aggregation of write traffic to a data store |
| US10216637B2 (en) | 2004-05-03 | 2019-02-26 | Microsoft Technology Licensing, Llc | Non-volatile memory cache performance improvement |
| JP2024500824A (ja) * | 2020-12-28 | 2024-01-10 | アドバンスト・マイクロ・ディバイシズ・インコーポレイテッド | キャッシュディレクトリを管理するための方法及び装置 |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6105108A (en) * | 1997-10-24 | 2000-08-15 | Compaq Computer Corporation | Method and apparatus for releasing victim data buffers of computer systems by comparing a probe counter with a service counter |
| US5996055A (en) * | 1997-11-26 | 1999-11-30 | Digital Equipment Corporation | Method for reclaiming physical pages of memory while maintaining an even distribution of cache page addresses within an address space |
| US6397296B1 (en) * | 1999-02-19 | 2002-05-28 | Hitachi Ltd. | Two-level instruction cache for embedded processors |
| US6397300B1 (en) | 1999-06-25 | 2002-05-28 | International Business Machines Corporation | High performance store instruction management via imprecise local cache update mechanism |
| US6385694B1 (en) | 1999-06-25 | 2002-05-07 | International Business Machines Corporation | High performance load instruction management via system bus with explicit register load and/or cache reload protocols |
| US6405285B1 (en) * | 1999-06-25 | 2002-06-11 | International Business Machines Corporation | Layered local cache mechanism with split register load bus and cache load bus |
| US6418513B1 (en) * | 1999-06-25 | 2002-07-09 | International Business Machines Corporation | Queue-less and state-less layered local data cache mechanism |
| US6446166B1 (en) | 1999-06-25 | 2002-09-03 | International Business Machines Corporation | Method for upper level cache victim selection management by a lower level cache |
| US6434667B1 (en) * | 1999-06-25 | 2002-08-13 | International Business Machines Corporation | Layered local cache with imprecise reload mechanism |
| US6463507B1 (en) | 1999-06-25 | 2002-10-08 | International Business Machines Corporation | Layered local cache with lower level cache updating upper and lower level cache directories |
| US6539457B1 (en) * | 2000-02-21 | 2003-03-25 | Hewlett-Packard Company | Cache address conflict mechanism without store buffers |
| US6434672B1 (en) | 2000-02-29 | 2002-08-13 | Hewlett-Packard Company | Methods and apparatus for improving system performance with a shared cache memory |
| US6748558B1 (en) | 2000-05-10 | 2004-06-08 | Motorola, Inc. | Performance monitor system and method suitable for use in an integrated circuit |
| US7010788B1 (en) * | 2000-05-19 | 2006-03-07 | Hewlett-Packard Development Company, L.P. | System for computing the optimal static schedule using the stored task execution costs with recent schedule execution costs |
| US6574710B1 (en) * | 2000-07-31 | 2003-06-03 | Hewlett-Packard Development Company, L.P. | Computer cache system with deferred invalidation |
| US6842180B1 (en) * | 2000-09-20 | 2005-01-11 | Intel Corporation | Opportunistic sharing of graphics resources to enhance CPU performance in an integrated microprocessor |
| US6654859B2 (en) | 2001-07-26 | 2003-11-25 | International Business Machines Corporation | NUMA page selection using coloring |
| US7062607B2 (en) * | 2001-09-24 | 2006-06-13 | Intel Corporation | Filtering basic instruction segments in a processor front-end for power conservation |
| US6820170B1 (en) * | 2002-06-24 | 2004-11-16 | Applied Micro Circuits Corporation | Context based cache indexing |
| US7085890B2 (en) * | 2004-02-19 | 2006-08-01 | International Business Machines Corporation | Memory mapping to reduce cache conflicts in multiprocessor systems |
| US20060037017A1 (en) * | 2004-08-12 | 2006-02-16 | International Business Machines Corporation | System, apparatus and method of reducing adverse performance impact due to migration of processes from one CPU to another |
| US20060036810A1 (en) * | 2004-08-12 | 2006-02-16 | International Business Machines Corporation | System, application and method of reducing cache thrashing in a multi-processor with a shared cache on which a disruptive process is executing |
| US7721292B2 (en) * | 2004-12-16 | 2010-05-18 | International Business Machines Corporation | System for adjusting resource allocation to a logical partition based on rate of page swaps and utilization by changing a boot configuration file |
| US7395373B2 (en) * | 2005-09-20 | 2008-07-01 | International Business Machines Corporation | Set-associative cache using cache line decay counts and set overflow |
| US8769221B2 (en) * | 2008-01-04 | 2014-07-01 | International Business Machines Corporation | Preemptive page eviction |
| US20110131381A1 (en) * | 2009-11-27 | 2011-06-02 | Advanced Micro Devices, Inc. | Cache scratch-pad and method therefor |
| KR20150096226A (ko) * | 2014-02-14 | 2015-08-24 | 삼성전자주식회사 | 멀티미디어 데이터 프로세싱 방법 및 그에 따른 멀티미디어 데이터 프로세싱 시스템 |
| US20190050342A1 (en) * | 2017-08-08 | 2019-02-14 | Honeywell International Inc. | Selective page tracking for process controller redundancy |
| GB2578574B (en) | 2018-10-30 | 2021-03-10 | Advanced Risc Mach Ltd | Circuitry and method |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5261066A (en) * | 1990-03-27 | 1993-11-09 | Digital Equipment Corporation | Data processing system and method with small fully-associative cache and prefetch buffers |
| US5317718A (en) * | 1990-03-27 | 1994-05-31 | Digital Equipment Corporation | Data processing system and method with prefetch buffers |
| US5386547A (en) * | 1992-01-21 | 1995-01-31 | Digital Equipment Corporation | System and method for exclusive two-level caching |
| US5423016A (en) * | 1992-02-24 | 1995-06-06 | Unisys Corporation | Block buffer for instruction/operand caches |
| WO1994003856A1 (en) * | 1992-08-07 | 1994-02-17 | Massachusetts Institute Of Technology | Column-associative cache |
| US5465342A (en) * | 1992-12-22 | 1995-11-07 | International Business Machines Corporation | Dynamically adaptive set associativity for cache memories |
| US5603004A (en) * | 1994-02-14 | 1997-02-11 | Hewlett-Packard Company | Method for decreasing time penalty resulting from a cache miss in a multi-level cache system |
| US5577227A (en) * | 1994-08-04 | 1996-11-19 | Finnell; James S. | Method for decreasing penalty resulting from a cache miss in multi-level cache system |
-
1996
- 1996-01-02 US US08/582,542 patent/US5860095A/en not_active Expired - Lifetime
- 1996-12-26 JP JP34740096A patent/JP3795985B2/ja not_active Expired - Fee Related
Cited By (21)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1011049A3 (en) * | 1998-12-15 | 2001-03-14 | Nec Corporation | Cache system and cache processing method |
| US6792498B2 (en) | 2001-01-22 | 2004-09-14 | Hitachi, Ltd. | Memory system with mechanism for assisting a cache memory |
| US10216637B2 (en) | 2004-05-03 | 2019-02-26 | Microsoft Technology Licensing, Llc | Non-volatile memory cache performance improvement |
| US9317209B2 (en) | 2004-10-21 | 2016-04-19 | Microsoft Technology Licensing, Llc | Using external memory devices to improve system performance |
| JP2012181863A (ja) * | 2004-10-21 | 2012-09-20 | Microsoft Corp | システムパフォーマンスを改善するための外部メモリデバイスの使用 |
| US9690496B2 (en) | 2004-10-21 | 2017-06-27 | Microsoft Technology Licensing, Llc | Using external memory devices to improve system performance |
| US8909861B2 (en) | 2004-10-21 | 2014-12-09 | Microsoft Corporation | Using external memory devices to improve system performance |
| US11334484B2 (en) | 2005-12-16 | 2022-05-17 | Microsoft Technology Licensing, Llc | Optimizing write and wear performance for a memory |
| US9529716B2 (en) | 2005-12-16 | 2016-12-27 | Microsoft Technology Licensing, Llc | Optimizing write and wear performance for a memory |
| US8914557B2 (en) | 2005-12-16 | 2014-12-16 | Microsoft Corporation | Optimizing write and wear performance for a memory |
| JP2008016033A (ja) * | 2006-07-06 | 2008-01-24 | Internatl Business Mach Corp <Ibm> | 階層テーブルを管理するための方法およびコンピュータ・システム |
| US9032151B2 (en) | 2008-09-15 | 2015-05-12 | Microsoft Technology Licensing, Llc | Method and system for ensuring reliability of cache data and metadata subsequent to a reboot |
| US10387313B2 (en) | 2008-09-15 | 2019-08-20 | Microsoft Technology Licensing, Llc | Method and system for ensuring reliability of cache data and metadata subsequent to a reboot |
| US9361183B2 (en) | 2008-09-19 | 2016-06-07 | Microsoft Technology Licensing, Llc | Aggregation of write traffic to a data store |
| US9448890B2 (en) | 2008-09-19 | 2016-09-20 | Microsoft Technology Licensing, Llc | Aggregation of write traffic to a data store |
| US10509730B2 (en) | 2008-09-19 | 2019-12-17 | Microsoft Technology Licensing, Llc | Aggregation of write traffic to a data store |
| JP2010079361A (ja) * | 2008-09-24 | 2010-04-08 | Nec Corp | プロセッサ、プロセッサのデータ処理方法、情報処理装置 |
| JP2012194742A (ja) * | 2011-03-16 | 2012-10-11 | Nec Engineering Ltd | リプレースメントデータメモリ装置、中央演算装置及びリプレースメントデータ処理方法 |
| JP2014067250A (ja) * | 2012-09-26 | 2014-04-17 | Nec Corp | メモリアクセス制御装置、メモリアクセス制御システム、及び、メモリアクセス制御方法 |
| JP2014209392A (ja) * | 2014-08-13 | 2014-11-06 | Ｎｅｃエンジニアリング株式会社 | リプレースメントデータメモリ装置、中央演算装置及びリプレースメントデータ処理用プログラム |
| JP2024500824A (ja) * | 2020-12-28 | 2024-01-10 | アドバンスト・マイクロ・ディバイシズ・インコーポレイテッド | キャッシュディレクトリを管理するための方法及び装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5860095A (en) | 1999-01-12 |
| JP3795985B2 (ja) | 2006-07-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3795985B2 (ja) | コンピュータメモリシステムの競合キャッシュ | |
| US6223256B1 (en) | Computer cache memory with classes and dynamic selection of replacement algorithms | |
| US5155824A (en) | System for transferring selected data words between main memory and cache with multiple data words and multiple dirty bits for each address | |
| US6725337B1 (en) | Method and system for speculatively invalidating lines in a cache | |
| US6766419B1 (en) | Optimization of cache evictions through software hints | |
| US8782348B2 (en) | Microprocessor cache line evict array | |
| USRE45078E1 (en) | Highly efficient design of storage array utilizing multiple pointers to indicate valid and invalid lines for use in first and second cache spaces and memory subsystems | |
| JP4298800B2 (ja) | キャッシュメモリにおけるプリフェッチ管理 | |
| US6874077B2 (en) | Parallel distributed function translation lookaside buffer | |
| US7809889B2 (en) | High performance multilevel cache hierarchy | |
| US6732238B1 (en) | Set-associative cache memory having variable time decay rewriting algorithm | |
| EP2017738A1 (en) | Hierarchical cache tag architecture | |
| CN1093961C (zh) | 增强存储器性能的方法及数据处理系统 | |
| US8621152B1 (en) | Transparent level 2 cache that uses independent tag and valid random access memory arrays for cache access | |
| JP2019096309A (ja) | メンテナンス動作の実行 | |
| US6332179B1 (en) | Allocation for back-to-back misses in a directory based cache | |
| US6240489B1 (en) | Method for implementing a pseudo least recent used (LRU) mechanism in a four-way cache memory within a data processing system | |
| US20080301371A1 (en) | Memory Cache Control Arrangement and a Method of Performing a Coherency Operation Therefor | |
| US5860097A (en) | Associative cache memory with improved hit time | |
| US6792498B2 (en) | Memory system with mechanism for assisting a cache memory | |
| KR20230075361A (ko) | 메모리 어드레스들과 연관된 데이터를 캐싱하도록 캐시 저장소를 동작시키기 위한 기법 | |
| US5619673A (en) | Virtual access cache protection bits handling method and apparatus | |
| US7461212B2 (en) | Non-inclusive cache system with simple control operation | |
| US12423236B2 (en) | Coherency control | |
| US7685372B1 (en) | Transparent level 2 cache controller |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20060330 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20060411 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20060414 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090421 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100421 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100421 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110421 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120421 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120421 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130421 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130421 Year of fee payment: 7 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130421 Year of fee payment: 7 |
|
| R360 | Written notification for declining of transfer of rights |
Free format text: JAPANESE INTERMEDIATE CODE: R360 |
|
| R360 | Written notification for declining of transfer of rights |
Free format text: JAPANESE INTERMEDIATE CODE: R360 |
|
| R371 | Transfer withdrawn |
Free format text: JAPANESE INTERMEDIATE CODE: R371 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130421 Year of fee payment: 7 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130421 Year of fee payment: 7 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140421 Year of fee payment: 8 |
|
| LAPS | Cancellation because of no payment of annual fees |