JP4101907B2 - コンピュータ・システム中でキャッシュされるべきデータを選択する方法，コンピュータ・システム，及びコンピュータ・システム用キャッシュ化装置 - Google Patents
コンピュータ・システム中でキャッシュされるべきデータを選択する方法，コンピュータ・システム，及びコンピュータ・システム用キャッシュ化装置 Download PDFInfo
- Publication number
- JP4101907B2 JP4101907B2 JP18460097A JP18460097A JP4101907B2 JP 4101907 B2 JP4101907 B2 JP 4101907B2 JP 18460097 A JP18460097 A JP 18460097A JP 18460097 A JP18460097 A JP 18460097A JP 4101907 B2 JP4101907 B2 JP 4101907B2
- Authority
- JP
- Japan
- Prior art keywords
- cache
- data
- subsystem
- miss
- computer system
- 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.)
- Expired - Lifetime
Links
Images
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/0888—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches using selective caching, e.g. bypass
-
- 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/0806—Multiuser, multiprocessor or multiprocessing cache systems
- G06F12/0813—Multiuser, multiprocessor or multiprocessing cache systems with a network or matrix configuration
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)
- Multi Processors (AREA)
Description
【０００１】
【発明の属する技術分野】
この発明は、コンピュータ・システムのキャッシュ、特にコンピュータ・システムのキャッシュ・メモリ空間を効率良く割当てることに関するものである。
【０００２】
【従来の技術】
小さな第１レベルのキャッシュ及び大きな第２レベルのキャッシュを有するマルチレベルのキャッシュ・コンピュータ・システムの簡単なキャッシュ空間割当て技術では、全てのデータ構造が両方のレベルのキャッシュに自動的にキャッシュされる。もしデータ構造のサイズがより小さい低レベルのキャッシュよりも大きければ、即ちデータ構造が低レベルのキャッシュに合わないなら、データ構造は低レベルのキャッシュから置き換えられる。もしデータ構造がより大きい高レベルのキャッシュよりも小さいならば、データ構造の内容の大部分は高レベルのキャッシュにとどまる。
【０００３】
残念なことに、幾らかのデータ構造は頻繁にアクセスされるが、他のデータ構造は１回しかアクセスされないということがある。そして幾らかの統計分析とデータ構造を所有するコンピュータ・プログラムの知識との少なくとも一方無しに特定の構造への将来のアクセスを予測するのは容易でない。例えば、コンピュータ・プログラムは、アレイの各エレメントをアクセスすることにより、大きいアレイを使用するかもしれない。各エレメントは、一時変数を含むかなり複雑な計算に使用される。この例では、大きなアレイの全エレメントをキャッシュ化することは計算速度を実質的に速めない。対照的に、一時変数をキャッシュ化するとプログラムの実行を速めることになる。
【０００４】
従って、マルチレベルのキャッシュ中に空間を割当てるための上述した方法は簡単であるが、この方法はデータ構造のサイズだけに基づき、ひいてはデータ構造の相当数が不必要にキャッシュされるので効率が悪い。過剰なキャッシュ化は、他の有用なデータ構造を早目に元の場所に戻させる（置き換える）、即ち後続のアクセス前にキャッシュから追い出すことになる。
【０００５】
【発明が解決しようとする課題】
キャッシュ・メモリが無限に大きくないので、キャッシュの使用を最大限にすると共にデータへの全アクセス時間を最短にするためには制限されたキャッシュ・リソースを効率良く割当てる必要がある。従って、マルチレベルのキャッシュ・コンピュータ・システム中でキャッシュ・メモリ空間の割当てを最適にするキャッシュ化用データ構造を選択するための効率の良い機構の必要性がある。
【０００６】
この発明は、少なくとも１個のキャッシュを有するユニプロセッサとマルチプロセッサの両方のコンピュータ・システム用の効率の良いキャッシュ割当て技術を提供する。
【０００７】
【課題を解決するための手段】
１つの実施態様では、キャッシュ・ミスが検出された時に、そのキャッシュ・ミスが“避けられ得た”ものかどうかが決定される。換言すれば、もしデータが以前にキャッシュされてしかもキャッシュ中にまだ残っていたなら、それでも現在のキャッシュ・ミスが起こったかどうかが決定される。
【０００８】
分散型メモリ・アーキテクチャを有するマルチプロセッサ・システム中での避けられ得るキャッシュ・ミスの一例は、過剰なキャッシュ・ミスである。過剰なキャッシュ・ミスは、容量ミスかコンフリクト・ミスである。容量ミスはキャッシュのサイズ不足で起こる。コンフリクト・ミスはキャッシュの結合性の深さ不足で起こる。過剰なキャッシュ・ミスを決定するには、種々のプロセッサによるデータのリード／ライト・リクエストを追跡すること、及びテーブル又はリンク済みリスト中でのリード／ライト・リクエストの記録をストアすることが含まれる。例えば、データ構造の最後のライタの識別を追跡すると、現在のキャッシュ・ミスよりも以前にデータが置き換えられなかったら、現在のキャッシュ・ミスが避けられたかどうかについての指示が与えられる。
【０００９】
簡単なユニプロセッサ・システムの場合には、唯一のプロセッサがキャッシュへアクセスするだけなので、避けられ得るキャッシュ・ミスは、以前にアクセスされたデータ、即ち現在のキャッシュ・ミス以前にキャッシュされて置き換えられたデータに適用される。
【００１０】
この発明によれば、避けられ得るキャッシュ・ミスが起こった後でだけデータはキャッシュされる。アクセスする毎にの代わりに、少なくとも１つの避けられ得るキャッシュ・ミスの後でだけキャッシュ化することにより、キャッシュ空間を極めて効率の良い仕方で割当てることができ、それによってキャッシュ・ミスのせいで起こったデータ・フェッチの数を最少にする。これは、データが以前に少なくとも２回アクセスされたならば、データが再びアクセスされる統計的な見込みが劇的に増大するためである。
【００１１】
キャッシュ・コヒーレンシイ・プロトコルによっては、ディスプレースされた（displaced ）データを捨てる前に、そのディスプレースされたデータを置き換えること、即ちデータを主メモリ／オーナ・システムへライトバックすることが必要になるかもしれない。
【００１２】
【発明の実施の形態】
この発明のコンピュータ・システムの目的、特徴及び利点は、以下の説明から明らかになろう。
以下の説明中の符号は発明を完全に理解する為に付けた。符号を付けたものの中には、コンピュータ・システム内でキャッシュ・メモリ空間を割当てる効率の良い方法の実施を支援するための機能ブロック及び例示的なキャッシュ・アーキテクチャがある。加えて、マルチプロセッサ・コンピュータ・システムの分散型キャッシュのための特定のキャッシュ割当て方法についてこの発明を説明するが、広範囲のキャッシュ及びコンピュータのアーキテクチャにこの発明を適用できる。なお、この発明を必要以上に不明瞭にしないために周知の回路や構成は詳しく説明しない。
【００１３】
本願出願人の先行出願には、ネットワーク化されたコンピュータ・システム用の共有主記憶アドレス空間及びコヒーレントなキャッシュ化装置を有するハイブリッド・キャッシュオンリ・メモリ・アーキテクチャ／非一様メモリ・アーキテクチャ（ＣＯＭＡ／ＮＵＭＡ）が開示されており、上述したネットワーク化されたコンピュータ・システムはこの発明を実施するための適当な例示的ハードウェア環境を提供する。
【００１４】
図１は、そのようなハイブリッドＣＯＭＡ／ＮＵＭＡコンピュータ・システム１００を示すブロック図である。このコンピュータ・システム１００は、グローバル・インターコネクト１９０を介して互いに結合された複数のサブシステム１１０，１２０，…１８０を含む。各サブシステムには特有のネットワーク・ノード・アドレスが割当てられる。各サブシステムは、１個以上のプロセッサ、対応する数のメモリ管理ユニット（ＭＭＵ）及び第２レベルのハイブリッド・キャッシュ（Ｌ２＄）、ＣＯＭＡキャッシュ／メモリ、グローバル・インターフェイス、第３レベルのキャッシュ（Ｌ３＄）及びローカル・インターコネクトを含む。例えば、サブシステム１１０はプロセッサ１１１ａ，１１１ｂ，…１１１ｉ，ＭＭＵ１１２ａ，１１２ｂ，…１１２ｉ，Ｌ２＄１１３ａ，１１３ｂ，…１１３ｉ，ＣＯＭＡキャッシュ／メモリ１１４、グローバル・インターフェイス１１５，Ｌ３＄１１８，及びローカル・インターコネクト１１９を含む。各プロセッサ１１１ａ，１１１ｂ，…１１１ｉは第１レベルの任意でコンパクトなキャッシュを含み得る。
【００１５】
ディレクトリに基づいたキャッシュ・コヒーレンス方法を支持するために、サブシステム１１０，１２０，…１８０は、グローバル・インターフェイス１１５，１２５，…１８５とそれぞれ結合されたディレクトリ１１６，１２６，…１８６も含む。ＣＯＭＡキャッシュ／メモリ１１４，１２４，…１８４のどれかにある“ホーム”ロケーションから発するデータは、コンピュータ・システム１００のアトラクション・メモリ（ＡＭ）中で複製される。例えば、ＣＯＭＡモードでは、サブシステムのキャッシュはＣＯＭＡキャッシュ／メモリ１１４、１２４、．．．１８４とＬ２＄１１３ａ．．．１１３ｉ、１２３ａ．．．１２３ｉ、１８３ａ．．．１８３ｉの双方を含む。そして“ホーム”ロケーションがサブシステム１１０のキャッシュ・メモリ１１４にあるデータは、キャッシュ・メモリ１２４，…１８４のうちの１個又は２個以上にて複製されて良く、且つ又複数のキャッシュＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉのうちの１個又は２個以上にて複製されても良い。逆に、ＮＵＭＡモードでは、サブシステムのキャッシュはＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉを含む。そして“ホーム”ロケーションがサブシステム１１０のキャッシュ・メモリ１１４中にあるデータは、複数のＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉのうちの１個又は２個以上にて、そしてＬ３＄１１８にて複製されてよい。
【００１６】
図１の例示的なハイブリッドＣＯＭＡ／ＮＵＭＡコンピュータ・システム１００で実施されたようなこの発明の一実施形態では、データの“ホーム”ロケーションはサブシステム１２０のＣＯＭＡキャッシュ／メモリ１２４中にある。即ちサブシステム１２０はデータのホーム及びオーナの両方のサブシステムである。ＣＯＭＡキャッシュ・メモリ１１４と第２レベルのハイブリッド・キャッシュ（Ｌ２＄）１１３ａ，１１３ｂ，…１１３ｉとの少なくとも一方に空間を割当てることにより、１つ又は２つ以上のリクエスト中のサブシステムのアトラクション・メモリ（ＡＭ）空間例えばリクエスト中のサブシステム１１０のＡＭ空間にデータのコピーもストアできる。これに関連して、本願出願人の先行出願である１９９５年１２月２２日付け出願の出願番号０８／５７７，２８３（整理番号Ｐ１００３）、発明者ハガースタン（Ｈａｇｅｒｓｔｅｎ）等、発明の名称「ハイブリッドＮＵＭＡコマ・キャッシュ化装置及び複数のキャッシ化モードを選択する方法」を参照されたい。又、１９９５年１２月２２日付け出願の出願番号０８／５７５，７８７（整理番号Ｐ１００４）、発明者ウッド（Ｗｏｏｄ）等、発明の名称「ハイブリッドＮＵＭＡコマ・キャッシュ化装置及び複数のキャッシュ化モードを選択する方法」も参照されたい。これら出願には、ハイブリッドＣＯＭＡ／ＮＵＭＡアーキテクチャ及びハイブリッド・キャッシュ・アーキテクチャを開発する方法が述べられている。
【００１７】
ホーム・ディレクトリ１２６は、コンピュータ・システム１００全体に亘るホーム・ページの現存するコピーのマスター記録を維持することに対して責任がある。その上、それぞれのＡＭディレクトリ例えばディレクトリ１１６及び１８６に関連した複数のメモリ・タグ（ＭＴＡＧ）は、４つの例示的な状態のうちの１つを使用してリクエスト中の各サブシステム内のローカル・コピーの状態を追跡する。無効（“Ｉ”）状態は、特定のサブシステムが対象となるデータ・ラインの（キャッシュされた）コピーを持たないことを示す。共有した（“Ｓ”）状態は、そのサブシステム及び他の幾つかのサブシステムが対象となるデータ・ラインの共有した（キャッシュされた）コピーを有することを示す。所有した（“Ｏ”）状態は、そのサブシステム及び他の幾つかのサブシステムが対象となるデータ・ラインの（キャッシュされた）コピーを有することを示す。Ｏコピーを持つサブシステムは、置き換えの時にライトバックすることを必要とされる。変更した（“Ｍ”）状態は、サブシステムが対象となるデータ・ラインの（キャッシュされた）コピーだけを有する、即ちサブシステムがデータ・ラインの唯一のオーナであり、他のサブシステムにＳコピーが無いことを示す。
【００１８】
この例では、図１に示したように、ＣＯＭＡキャッシュ／メモリ１１４，１２４，…１８４は第３レベルのキャッシュＬ３＄１１８，１２８，…１８８から隔てられており、そしてプロセッサ１１１ａ，１１１ｂ，…１１１ｉ，１２１ａ，１２１ｂ，…１２１ｉ，及び１８１ａ，１８１ｂ，…１８１ｉの各々は、第１レベルの内部キャッシュ（Ｌ１＄）（図１には示さない）を含む。
【００１９】
この発明の一面によれば、複数のＬ１＄とＬ２＄の間には内包が維持されるが、Ｌ２＄と第３レベルのキャッシュの間には内包を維持する必要が無い。換言すれば、Ｌ１＄にあるデータはそれぞれのＬ２＄にもあるが、Ｌ１＄又はＬ２＄にあるデータは必ずしもＬ３＄にある必要は無い。従って、Ｌ２＄中のデータのキャッシュ・ラインに空間が割当てられようとも、Ｌ３＄はデータのキャッシュ・ライン用に割当てなくても良い。
【００２０】
図３は、マルチプロセッサ・コンピュータ・システム１００に実施されたようなこの発明の一実施形態を示すフローチャート２００である。
【００２１】
以下の説明において、選択方法は、特定のデータ構造がハイブリッドＣＯＭＡ／ＮＵＭＡ環境内のリクエスト中のサブシステム１１０のＬ３＄１１８にストアされるべきかストアされるべきでないかを決定するのに使用される。しかしながら、この選択方法は、全てのレベルのキャッシュにも様々なキャッシュ及びシステムのアーキテクチャにも適用できると理解される。例えば、Ｌ３＄及びＣＯＭＡキャッシュが以下の説明中では分離型キャッシュとして一緒に存在するが、この発明は、ＮＵＭＡオンリ（ＣＯＭＡキャッシュ１１４無し）にも、もっと汎用のＬ３＄有りのＣＯＭＡオンリ（ＮＵＭＡキャッシュ化モード無し）にも、又はＬ１＄と一緒に存在するＬ２＄にも適用できる。
【００２２】
リクエスト中のサブシステム１１０のプロセッサ１１１ａがデータをリクエストする時に、データのサーチはＬ２＄１１３ａで、次にＬ３＄１１８で行われる（ステップ２１０）。もしリクエスト中のサブシステム１１０内でデータが見い出されないなら、即ちキャッシュ・ミスがサブシステム１１０で検出されるなら、ホーム・サブシステム１２０にリクエストされてデータをフェッチする（ステップ２２０）。本出願人による上述した先行出願である出願番号０８／５７７，２８３（整理番号Ｐ１００３）には、ホーム・サブシステムのディレクトリに最初に割込むことによってオーナ・サブシステムからデータがどのようにしてフェッチされるかが開示されている。
【００２３】
リクエスト中のサブシステム１１０は、キャッシュ・ミスが“避けられ得る”キャッシュ・ミスかどうかを決定しようとする（ステップ２３０）。もしキャッシュ・ミスが避けられ得たならデータがＬ３＄１１８に残ったことにより、キャッシュ・ミスは避けられ得る。避けられ得るキャッシュ・ミスの一例が“過剰な”キャッシュ・ミスであって、これは容量ミス又はコンフリクト・ミスが先行したキャッシュ・ミスとして定義される。避けられ得るキャッシュ・ミスの他の原因も考察する。これらキャッシュ・ミスは、古いデータを置き換える代わりに、Ｌ３＄１１８を置き換えて、Ｌ３＄１１８に新しいキャッシュ空間を“フリーアップ（ｆｒｅｅ ｕｐ）”する、例えばＬ３＄をダイナミックに再サイズ化すれ（Ｌ３＄のサイズを大きくする）ば避けることができたキャッシュ・ミスをも含む。
【００２４】
この実施形態では、ホーム・サブシステム１２０のホーム・ディレクトリ１２６は、例えばアレイｄｉｒ＿ｓｈａｒｅ＿ｂｉｔ〔ノード〕（ただしノード＝１…ｎであって、ｎはサブシステムの総数である。）中の各キャッシュ・ラインにストアされたデータの共有した（Ｓ）コピーを有するリクエスト中のサブシステムのリストを維持する。その上、ホーム・ディレクトリ１２６は、各キャッシュ・ライン中のデータの現在のオーナ（ｏｗｎｅｒ＿ｉｄ）の識別を含む。現在のオーナが無い場合には、ｏｗｎｅｒ＿ｉｄは最後のオーナを識別する。ホームディレクトリ１２６は、最新のオーナがデータをメモリにライトバックしたかどうか、或はそれが未だオーナかどうかを示すライトバック・ビット（ｗｂ＿ｂｉｔ）も含む。データの最後のライタ（ｌａｓｔ＿ｗｒｉｔｅｒ）は、ディレクトリ１２６中のそれぞれのｏｗｎｅｒ＿ｉｄ及びｗｂ＿ｂｉｔフィールドから決定できる。従って、過剰なキャッシュ・ミスはブール式で下記のように表わされる。
【００２５】
(RTS & dir_share_bit〔ノード〕＝１）OR(RTO & last_write ＝ノード）
【００２６】
ただし、ＲＴＳはリード−ツ−シェア（read-to-share ）であり、そしてＲＴＯはリード−ツ−オーン（read-to-own）である。
【００２７】
過剰なキャッシュ・ミスを検出する例示的な方法の詳しい説明は、上述した出願番号０８／５７７，２８３（整理番号Ｐ１００３）の先行出願を参照されたい。この発明の一変形例では、ディレクトリ１２６が最近アクセスされたキャッシュ・ラインの状態情報を保持するディレクトリ・キャッシュである。（同日出願の「ディレクトリレス・プロトコル及び関連したディレクトリ・キャッシュＰ１５３１も参照されたい）。この変形例では、このディレクトリ・キャッシュにそれぞれのエントリを有する避けられ得るミスだけがＬ３＄１１８内にリクエスト中のサブシステム１１０によって空間を割当てることができる。
【００２８】
もしリクエスト中のサブシステム１１０が避けられ得るミスを検出するなら、データをストアするために適当なロケーションがＬ３＄１１８中に割当てられる（ステップ２５０）。アイドル・ロケーション又は無効データもしくはステール（stale ）・データを含むロケーションをまず探す（ステップ２６０）ことにより、適当なロケーションを割当てることができる。もしアイドル・ロケーションも無効ロケーションも見つからなければ、使用されたロケーションが割当てられてディスプレースされたデータを置き換える必要がある。１つの使用されたロケーションは幾つかの使用されたロケーションの中からランダムに選べる。或は、最も最近用いられた（ＬＲＵ）又は最も頻繁に用いられた（ＬＦＵ）のような選択規準を使用して多くの使用されたロケーションの中から或るロケーションを選べる。
【００２９】
もし選択された使用済みロケーションからディスプレースされたデータを置き換える必要があれば、リクエスト中のサブシステム１１０はディスプレースされたデータをそのオーナ・サブシステムにライトバックする（ステップ２６５）。上述した出願番号０８／５７７，２８３（整理番号Ｐ１００３）の先行出願は、ディスプレースされたを置き換える一例を提供する。
【００３０】
逆に、もしキャッシュ・ミスが避けられ得るキャッシュ・ミスではなくてキャッシュ１１８中にアイドル・ロケーションがある（ステップ２３０及び２４０）ならば、キャッシュ１１８中のアイドル・ロケーションが割当てられ且つデータが割当てられたロケーションにストアされる（ステップ２５５及び２７０）。もしキャッシュ・ミスが避けられ得るキャッシュ・ミスでない上にキャッシュ１１８が一杯である（ステップ２３０及び２４０）なら、データはキャッシュ１１８にキャッシュされない。
【００３１】
上述した場合の各々にて、データはリクエスト中のプロセッサ１１１ａへ提供される（ステップ２８０）。データがオーナ・サブシステム１２０からフェッチされた後はいつでもデータをリクエスト中のプロセッサ１１１ａに提供できる、即ち所要のキャッシュ化ステップの前後でデータを提供できることに注目されたい。
【００３２】
図４は、ユニプロセッサ・コンピュータ・システムにて実施されたこの発明の他の実施形態を示すフローチャート３００である。ユニプロセッサに関する実施形態についての以下の説明はプロセッサ・キャッシュ及び主メモリを有するコンピュータ・システムに基づくものであるが、選択方法は沢山のキャッシュとメモリの少なくとも一方を有するどんなユニプロセッサ・コンピュータ・システムにも適用できる。例えば、主メモリは高レベルのキャッシュで良い。
【００３３】
プロセッサがデータをリクエストする時に、キャッシュ中でデータがサーチされる（ステップ３１０）。もしデータが見つからなければ、即ちキャッシュ・ミスが検出されるなら、プロセッサは主メモリからデータをフェッチする（ステップ３２０）。
【００３４】
その後、プロセッサはキャッシュ・ミスが“避けられ得る”キャッシュ・ミスであるかどうかを決定しようとする（ステップ３３０）。ユニプロセッサ環境中の避けられ得るキャッシュ・ミスの一例は、何時、同一データがプロセッサによって以前に要求されて主メモリからキャッシュへフェッチされたかである。
【００３５】
もしプロセッサが避けられ得るミスを検出したなら、適当なロケーションがデータをストアするためのキャッシュ中で割当てられる（ステップ３５０）。アイドル・ロケーション又は無効データもしくはステール・データを含むロケーションをまず探す（ステップ３６０）ことにより、適当なロケーションを割当てることができる。もしアイドル・ロケーションも無効ロケーションも見つからなければ、使用されたロケーションが割当てられてディスプレースされたデータを置き換える必要がある。使用されたロケーションはアットランダムに或はＬＲＵもしくはＬＦＵのようなアルゴリズムを使用して選べる。
【００３６】
もし選択された使用済みロケーションからディスプレースされたデータを置き換える必要があれば、プロセッサはデータを主メモリにライトバックする（ステップ３６５）。キャッシュの強制的な“ライトスルー”がしいられるユニプロセッサ及びマルチプロセッサ・システムの両方において、キャッシュ及びメモリの内容が常にコヒーレントであるので、ディスプレースされたデータは簡単に捨てられ得る。“コピーバック”キャッシュも、もしディスプレースされたデータが変更されなかったならば、このディスプレースされたデータを簡単に捨てることができる。
【００３７】
逆に、もしキャッシュ・ミスが避けられ得るキャッシュ・ミスではなく且つキャッシュが一杯でもない（ステップ３３０及び３４０）ならば、プロセッサはキャッシュ中でアイドル・ロケーションを割当て且つデータは割当てられたロケーションにストアされる（ステップ３５５及び３７０）。もしキャッシュ・ミスが避けられ得るキャッシュ・ミスでなく且つキャッシュが一杯である（ステップ３３０及び３４０）なら、データはキャッシュされない。
【００３８】
上述した場合の各々にて、データはリクエスト中のプロセッサへ提供される（ステップ３８０）。どのキャッシュ化ステップ３７０の前後でもデータをリクエスト中のプロセッサへ提供できることに注目されたい。
【００３９】
この発明の精神から逸脱しない限り他の変形例や不可例が可能である。例えば、１つの避けられ得るキャッシュ・ミスの後でデータ構造をキャッシュ化する代わりに、避けられ得るキャッシュ・ミスの数が閾値を超えた後でデータ構造をキャッシュしても良い。他の変形例では、より若いデータ構造の過剰ミスの数が転置用に選ばれたより古いデータ構造のキャッシュ・ヒットの数を超える時だけ、より若いデータ構造をキャッシュしても良い。
【図面の簡単な説明】
【図１】 ハイブリッド・キャッシュ・オンリ・メモリ・アーキテクチャ／非一様メモリ・アーキテクチャ（ＣＯＭＡ／ＮＵＭＡ）を有するネットワーク化されたコンピュータ・システムを示すブロック図である。
【図２】 図１のネットワーク化されたコンピュータ・システムのための例示的なメモリ・マップである。
【図３】 マルチプロセッサ・コンピュータ・システム用のこの発明の一実施形態を示すフローチャートである。
【図４】 ユニプロセッサ・コンピュータ・システム用のこの発明の他の実施形態を示すフローチャートである。
【符号の説明】
１００…コンピュータ・システム、１１０，１２０，１８０…サブシステム、１１１ａ〜１８１ｉ…プロセッサ、１１３ａ〜１８３ｉ…第２レベルのハイブリッド・キャッシュ、１１４，１２４，１８４…ＣＯＭＡキャッシュ／メモリ、１１８，１２８，１８８…Ｌ３＄。
【発明の属する技術分野】
この発明は、コンピュータ・システムのキャッシュ、特にコンピュータ・システムのキャッシュ・メモリ空間を効率良く割当てることに関するものである。
【０００２】
【従来の技術】
小さな第１レベルのキャッシュ及び大きな第２レベルのキャッシュを有するマルチレベルのキャッシュ・コンピュータ・システムの簡単なキャッシュ空間割当て技術では、全てのデータ構造が両方のレベルのキャッシュに自動的にキャッシュされる。もしデータ構造のサイズがより小さい低レベルのキャッシュよりも大きければ、即ちデータ構造が低レベルのキャッシュに合わないなら、データ構造は低レベルのキャッシュから置き換えられる。もしデータ構造がより大きい高レベルのキャッシュよりも小さいならば、データ構造の内容の大部分は高レベルのキャッシュにとどまる。
【０００３】
残念なことに、幾らかのデータ構造は頻繁にアクセスされるが、他のデータ構造は１回しかアクセスされないということがある。そして幾らかの統計分析とデータ構造を所有するコンピュータ・プログラムの知識との少なくとも一方無しに特定の構造への将来のアクセスを予測するのは容易でない。例えば、コンピュータ・プログラムは、アレイの各エレメントをアクセスすることにより、大きいアレイを使用するかもしれない。各エレメントは、一時変数を含むかなり複雑な計算に使用される。この例では、大きなアレイの全エレメントをキャッシュ化することは計算速度を実質的に速めない。対照的に、一時変数をキャッシュ化するとプログラムの実行を速めることになる。
【０００４】
従って、マルチレベルのキャッシュ中に空間を割当てるための上述した方法は簡単であるが、この方法はデータ構造のサイズだけに基づき、ひいてはデータ構造の相当数が不必要にキャッシュされるので効率が悪い。過剰なキャッシュ化は、他の有用なデータ構造を早目に元の場所に戻させる（置き換える）、即ち後続のアクセス前にキャッシュから追い出すことになる。
【０００５】
【発明が解決しようとする課題】
キャッシュ・メモリが無限に大きくないので、キャッシュの使用を最大限にすると共にデータへの全アクセス時間を最短にするためには制限されたキャッシュ・リソースを効率良く割当てる必要がある。従って、マルチレベルのキャッシュ・コンピュータ・システム中でキャッシュ・メモリ空間の割当てを最適にするキャッシュ化用データ構造を選択するための効率の良い機構の必要性がある。
【０００６】
この発明は、少なくとも１個のキャッシュを有するユニプロセッサとマルチプロセッサの両方のコンピュータ・システム用の効率の良いキャッシュ割当て技術を提供する。
【０００７】
【課題を解決するための手段】
１つの実施態様では、キャッシュ・ミスが検出された時に、そのキャッシュ・ミスが“避けられ得た”ものかどうかが決定される。換言すれば、もしデータが以前にキャッシュされてしかもキャッシュ中にまだ残っていたなら、それでも現在のキャッシュ・ミスが起こったかどうかが決定される。
【０００８】
分散型メモリ・アーキテクチャを有するマルチプロセッサ・システム中での避けられ得るキャッシュ・ミスの一例は、過剰なキャッシュ・ミスである。過剰なキャッシュ・ミスは、容量ミスかコンフリクト・ミスである。容量ミスはキャッシュのサイズ不足で起こる。コンフリクト・ミスはキャッシュの結合性の深さ不足で起こる。過剰なキャッシュ・ミスを決定するには、種々のプロセッサによるデータのリード／ライト・リクエストを追跡すること、及びテーブル又はリンク済みリスト中でのリード／ライト・リクエストの記録をストアすることが含まれる。例えば、データ構造の最後のライタの識別を追跡すると、現在のキャッシュ・ミスよりも以前にデータが置き換えられなかったら、現在のキャッシュ・ミスが避けられたかどうかについての指示が与えられる。
【０００９】
簡単なユニプロセッサ・システムの場合には、唯一のプロセッサがキャッシュへアクセスするだけなので、避けられ得るキャッシュ・ミスは、以前にアクセスされたデータ、即ち現在のキャッシュ・ミス以前にキャッシュされて置き換えられたデータに適用される。
【００１０】
この発明によれば、避けられ得るキャッシュ・ミスが起こった後でだけデータはキャッシュされる。アクセスする毎にの代わりに、少なくとも１つの避けられ得るキャッシュ・ミスの後でだけキャッシュ化することにより、キャッシュ空間を極めて効率の良い仕方で割当てることができ、それによってキャッシュ・ミスのせいで起こったデータ・フェッチの数を最少にする。これは、データが以前に少なくとも２回アクセスされたならば、データが再びアクセスされる統計的な見込みが劇的に増大するためである。
【００１１】
キャッシュ・コヒーレンシイ・プロトコルによっては、ディスプレースされた（displaced ）データを捨てる前に、そのディスプレースされたデータを置き換えること、即ちデータを主メモリ／オーナ・システムへライトバックすることが必要になるかもしれない。
【００１２】
【発明の実施の形態】
この発明のコンピュータ・システムの目的、特徴及び利点は、以下の説明から明らかになろう。
以下の説明中の符号は発明を完全に理解する為に付けた。符号を付けたものの中には、コンピュータ・システム内でキャッシュ・メモリ空間を割当てる効率の良い方法の実施を支援するための機能ブロック及び例示的なキャッシュ・アーキテクチャがある。加えて、マルチプロセッサ・コンピュータ・システムの分散型キャッシュのための特定のキャッシュ割当て方法についてこの発明を説明するが、広範囲のキャッシュ及びコンピュータのアーキテクチャにこの発明を適用できる。なお、この発明を必要以上に不明瞭にしないために周知の回路や構成は詳しく説明しない。
【００１３】
本願出願人の先行出願には、ネットワーク化されたコンピュータ・システム用の共有主記憶アドレス空間及びコヒーレントなキャッシュ化装置を有するハイブリッド・キャッシュオンリ・メモリ・アーキテクチャ／非一様メモリ・アーキテクチャ（ＣＯＭＡ／ＮＵＭＡ）が開示されており、上述したネットワーク化されたコンピュータ・システムはこの発明を実施するための適当な例示的ハードウェア環境を提供する。
【００１４】
図１は、そのようなハイブリッドＣＯＭＡ／ＮＵＭＡコンピュータ・システム１００を示すブロック図である。このコンピュータ・システム１００は、グローバル・インターコネクト１９０を介して互いに結合された複数のサブシステム１１０，１２０，…１８０を含む。各サブシステムには特有のネットワーク・ノード・アドレスが割当てられる。各サブシステムは、１個以上のプロセッサ、対応する数のメモリ管理ユニット（ＭＭＵ）及び第２レベルのハイブリッド・キャッシュ（Ｌ２＄）、ＣＯＭＡキャッシュ／メモリ、グローバル・インターフェイス、第３レベルのキャッシュ（Ｌ３＄）及びローカル・インターコネクトを含む。例えば、サブシステム１１０はプロセッサ１１１ａ，１１１ｂ，…１１１ｉ，ＭＭＵ１１２ａ，１１２ｂ，…１１２ｉ，Ｌ２＄１１３ａ，１１３ｂ，…１１３ｉ，ＣＯＭＡキャッシュ／メモリ１１４、グローバル・インターフェイス１１５，Ｌ３＄１１８，及びローカル・インターコネクト１１９を含む。各プロセッサ１１１ａ，１１１ｂ，…１１１ｉは第１レベルの任意でコンパクトなキャッシュを含み得る。
【００１５】
ディレクトリに基づいたキャッシュ・コヒーレンス方法を支持するために、サブシステム１１０，１２０，…１８０は、グローバル・インターフェイス１１５，１２５，…１８５とそれぞれ結合されたディレクトリ１１６，１２６，…１８６も含む。ＣＯＭＡキャッシュ／メモリ１１４，１２４，…１８４のどれかにある“ホーム”ロケーションから発するデータは、コンピュータ・システム１００のアトラクション・メモリ（ＡＭ）中で複製される。例えば、ＣＯＭＡモードでは、サブシステムのキャッシュはＣＯＭＡキャッシュ／メモリ１１４、１２４、．．．１８４とＬ２＄１１３ａ．．．１１３ｉ、１２３ａ．．．１２３ｉ、１８３ａ．．．１８３ｉの双方を含む。そして“ホーム”ロケーションがサブシステム１１０のキャッシュ・メモリ１１４にあるデータは、キャッシュ・メモリ１２４，…１８４のうちの１個又は２個以上にて複製されて良く、且つ又複数のキャッシュＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉのうちの１個又は２個以上にて複製されても良い。逆に、ＮＵＭＡモードでは、サブシステムのキャッシュはＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉを含む。そして“ホーム”ロケーションがサブシステム１１０のキャッシュ・メモリ１１４中にあるデータは、複数のＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉのうちの１個又は２個以上にて、そしてＬ３＄１１８にて複製されてよい。
【００１６】
図１の例示的なハイブリッドＣＯＭＡ／ＮＵＭＡコンピュータ・システム１００で実施されたようなこの発明の一実施形態では、データの“ホーム”ロケーションはサブシステム１２０のＣＯＭＡキャッシュ／メモリ１２４中にある。即ちサブシステム１２０はデータのホーム及びオーナの両方のサブシステムである。ＣＯＭＡキャッシュ・メモリ１１４と第２レベルのハイブリッド・キャッシュ（Ｌ２＄）１１３ａ，１１３ｂ，…１１３ｉとの少なくとも一方に空間を割当てることにより、１つ又は２つ以上のリクエスト中のサブシステムのアトラクション・メモリ（ＡＭ）空間例えばリクエスト中のサブシステム１１０のＡＭ空間にデータのコピーもストアできる。これに関連して、本願出願人の先行出願である１９９５年１２月２２日付け出願の出願番号０８／５７７，２８３（整理番号Ｐ１００３）、発明者ハガースタン（Ｈａｇｅｒｓｔｅｎ）等、発明の名称「ハイブリッドＮＵＭＡコマ・キャッシュ化装置及び複数のキャッシ化モードを選択する方法」を参照されたい。又、１９９５年１２月２２日付け出願の出願番号０８／５７５，７８７（整理番号Ｐ１００４）、発明者ウッド（Ｗｏｏｄ）等、発明の名称「ハイブリッドＮＵＭＡコマ・キャッシュ化装置及び複数のキャッシュ化モードを選択する方法」も参照されたい。これら出願には、ハイブリッドＣＯＭＡ／ＮＵＭＡアーキテクチャ及びハイブリッド・キャッシュ・アーキテクチャを開発する方法が述べられている。
【００１７】
ホーム・ディレクトリ１２６は、コンピュータ・システム１００全体に亘るホーム・ページの現存するコピーのマスター記録を維持することに対して責任がある。その上、それぞれのＡＭディレクトリ例えばディレクトリ１１６及び１８６に関連した複数のメモリ・タグ（ＭＴＡＧ）は、４つの例示的な状態のうちの１つを使用してリクエスト中の各サブシステム内のローカル・コピーの状態を追跡する。無効（“Ｉ”）状態は、特定のサブシステムが対象となるデータ・ラインの（キャッシュされた）コピーを持たないことを示す。共有した（“Ｓ”）状態は、そのサブシステム及び他の幾つかのサブシステムが対象となるデータ・ラインの共有した（キャッシュされた）コピーを有することを示す。所有した（“Ｏ”）状態は、そのサブシステム及び他の幾つかのサブシステムが対象となるデータ・ラインの（キャッシュされた）コピーを有することを示す。Ｏコピーを持つサブシステムは、置き換えの時にライトバックすることを必要とされる。変更した（“Ｍ”）状態は、サブシステムが対象となるデータ・ラインの（キャッシュされた）コピーだけを有する、即ちサブシステムがデータ・ラインの唯一のオーナであり、他のサブシステムにＳコピーが無いことを示す。
【００１８】
この例では、図１に示したように、ＣＯＭＡキャッシュ／メモリ１１４，１２４，…１８４は第３レベルのキャッシュＬ３＄１１８，１２８，…１８８から隔てられており、そしてプロセッサ１１１ａ，１１１ｂ，…１１１ｉ，１２１ａ，１２１ｂ，…１２１ｉ，及び１８１ａ，１８１ｂ，…１８１ｉの各々は、第１レベルの内部キャッシュ（Ｌ１＄）（図１には示さない）を含む。
【００１９】
この発明の一面によれば、複数のＬ１＄とＬ２＄の間には内包が維持されるが、Ｌ２＄と第３レベルのキャッシュの間には内包を維持する必要が無い。換言すれば、Ｌ１＄にあるデータはそれぞれのＬ２＄にもあるが、Ｌ１＄又はＬ２＄にあるデータは必ずしもＬ３＄にある必要は無い。従って、Ｌ２＄中のデータのキャッシュ・ラインに空間が割当てられようとも、Ｌ３＄はデータのキャッシュ・ライン用に割当てなくても良い。
【００２０】
図３は、マルチプロセッサ・コンピュータ・システム１００に実施されたようなこの発明の一実施形態を示すフローチャート２００である。
【００２１】
以下の説明において、選択方法は、特定のデータ構造がハイブリッドＣＯＭＡ／ＮＵＭＡ環境内のリクエスト中のサブシステム１１０のＬ３＄１１８にストアされるべきかストアされるべきでないかを決定するのに使用される。しかしながら、この選択方法は、全てのレベルのキャッシュにも様々なキャッシュ及びシステムのアーキテクチャにも適用できると理解される。例えば、Ｌ３＄及びＣＯＭＡキャッシュが以下の説明中では分離型キャッシュとして一緒に存在するが、この発明は、ＮＵＭＡオンリ（ＣＯＭＡキャッシュ１１４無し）にも、もっと汎用のＬ３＄有りのＣＯＭＡオンリ（ＮＵＭＡキャッシュ化モード無し）にも、又はＬ１＄と一緒に存在するＬ２＄にも適用できる。
【００２２】
リクエスト中のサブシステム１１０のプロセッサ１１１ａがデータをリクエストする時に、データのサーチはＬ２＄１１３ａで、次にＬ３＄１１８で行われる（ステップ２１０）。もしリクエスト中のサブシステム１１０内でデータが見い出されないなら、即ちキャッシュ・ミスがサブシステム１１０で検出されるなら、ホーム・サブシステム１２０にリクエストされてデータをフェッチする（ステップ２２０）。本出願人による上述した先行出願である出願番号０８／５７７，２８３（整理番号Ｐ１００３）には、ホーム・サブシステムのディレクトリに最初に割込むことによってオーナ・サブシステムからデータがどのようにしてフェッチされるかが開示されている。
【００２３】
リクエスト中のサブシステム１１０は、キャッシュ・ミスが“避けられ得る”キャッシュ・ミスかどうかを決定しようとする（ステップ２３０）。もしキャッシュ・ミスが避けられ得たならデータがＬ３＄１１８に残ったことにより、キャッシュ・ミスは避けられ得る。避けられ得るキャッシュ・ミスの一例が“過剰な”キャッシュ・ミスであって、これは容量ミス又はコンフリクト・ミスが先行したキャッシュ・ミスとして定義される。避けられ得るキャッシュ・ミスの他の原因も考察する。これらキャッシュ・ミスは、古いデータを置き換える代わりに、Ｌ３＄１１８を置き換えて、Ｌ３＄１１８に新しいキャッシュ空間を“フリーアップ（ｆｒｅｅ ｕｐ）”する、例えばＬ３＄をダイナミックに再サイズ化すれ（Ｌ３＄のサイズを大きくする）ば避けることができたキャッシュ・ミスをも含む。
【００２４】
この実施形態では、ホーム・サブシステム１２０のホーム・ディレクトリ１２６は、例えばアレイｄｉｒ＿ｓｈａｒｅ＿ｂｉｔ〔ノード〕（ただしノード＝１…ｎであって、ｎはサブシステムの総数である。）中の各キャッシュ・ラインにストアされたデータの共有した（Ｓ）コピーを有するリクエスト中のサブシステムのリストを維持する。その上、ホーム・ディレクトリ１２６は、各キャッシュ・ライン中のデータの現在のオーナ（ｏｗｎｅｒ＿ｉｄ）の識別を含む。現在のオーナが無い場合には、ｏｗｎｅｒ＿ｉｄは最後のオーナを識別する。ホームディレクトリ１２６は、最新のオーナがデータをメモリにライトバックしたかどうか、或はそれが未だオーナかどうかを示すライトバック・ビット（ｗｂ＿ｂｉｔ）も含む。データの最後のライタ（ｌａｓｔ＿ｗｒｉｔｅｒ）は、ディレクトリ１２６中のそれぞれのｏｗｎｅｒ＿ｉｄ及びｗｂ＿ｂｉｔフィールドから決定できる。従って、過剰なキャッシュ・ミスはブール式で下記のように表わされる。
【００２５】
(RTS & dir_share_bit〔ノード〕＝１）OR(RTO & last_write ＝ノード）
【００２６】
ただし、ＲＴＳはリード−ツ−シェア（read-to-share ）であり、そしてＲＴＯはリード−ツ−オーン（read-to-own）である。
【００２７】
過剰なキャッシュ・ミスを検出する例示的な方法の詳しい説明は、上述した出願番号０８／５７７，２８３（整理番号Ｐ１００３）の先行出願を参照されたい。この発明の一変形例では、ディレクトリ１２６が最近アクセスされたキャッシュ・ラインの状態情報を保持するディレクトリ・キャッシュである。（同日出願の「ディレクトリレス・プロトコル及び関連したディレクトリ・キャッシュＰ１５３１も参照されたい）。この変形例では、このディレクトリ・キャッシュにそれぞれのエントリを有する避けられ得るミスだけがＬ３＄１１８内にリクエスト中のサブシステム１１０によって空間を割当てることができる。
【００２８】
もしリクエスト中のサブシステム１１０が避けられ得るミスを検出するなら、データをストアするために適当なロケーションがＬ３＄１１８中に割当てられる（ステップ２５０）。アイドル・ロケーション又は無効データもしくはステール（stale ）・データを含むロケーションをまず探す（ステップ２６０）ことにより、適当なロケーションを割当てることができる。もしアイドル・ロケーションも無効ロケーションも見つからなければ、使用されたロケーションが割当てられてディスプレースされたデータを置き換える必要がある。１つの使用されたロケーションは幾つかの使用されたロケーションの中からランダムに選べる。或は、最も最近用いられた（ＬＲＵ）又は最も頻繁に用いられた（ＬＦＵ）のような選択規準を使用して多くの使用されたロケーションの中から或るロケーションを選べる。
【００２９】
もし選択された使用済みロケーションからディスプレースされたデータを置き換える必要があれば、リクエスト中のサブシステム１１０はディスプレースされたデータをそのオーナ・サブシステムにライトバックする（ステップ２６５）。上述した出願番号０８／５７７，２８３（整理番号Ｐ１００３）の先行出願は、ディスプレースされたを置き換える一例を提供する。
【００３０】
逆に、もしキャッシュ・ミスが避けられ得るキャッシュ・ミスではなくてキャッシュ１１８中にアイドル・ロケーションがある（ステップ２３０及び２４０）ならば、キャッシュ１１８中のアイドル・ロケーションが割当てられ且つデータが割当てられたロケーションにストアされる（ステップ２５５及び２７０）。もしキャッシュ・ミスが避けられ得るキャッシュ・ミスでない上にキャッシュ１１８が一杯である（ステップ２３０及び２４０）なら、データはキャッシュ１１８にキャッシュされない。
【００３１】
上述した場合の各々にて、データはリクエスト中のプロセッサ１１１ａへ提供される（ステップ２８０）。データがオーナ・サブシステム１２０からフェッチされた後はいつでもデータをリクエスト中のプロセッサ１１１ａに提供できる、即ち所要のキャッシュ化ステップの前後でデータを提供できることに注目されたい。
【００３２】
図４は、ユニプロセッサ・コンピュータ・システムにて実施されたこの発明の他の実施形態を示すフローチャート３００である。ユニプロセッサに関する実施形態についての以下の説明はプロセッサ・キャッシュ及び主メモリを有するコンピュータ・システムに基づくものであるが、選択方法は沢山のキャッシュとメモリの少なくとも一方を有するどんなユニプロセッサ・コンピュータ・システムにも適用できる。例えば、主メモリは高レベルのキャッシュで良い。
【００３３】
プロセッサがデータをリクエストする時に、キャッシュ中でデータがサーチされる（ステップ３１０）。もしデータが見つからなければ、即ちキャッシュ・ミスが検出されるなら、プロセッサは主メモリからデータをフェッチする（ステップ３２０）。
【００３４】
その後、プロセッサはキャッシュ・ミスが“避けられ得る”キャッシュ・ミスであるかどうかを決定しようとする（ステップ３３０）。ユニプロセッサ環境中の避けられ得るキャッシュ・ミスの一例は、何時、同一データがプロセッサによって以前に要求されて主メモリからキャッシュへフェッチされたかである。
【００３５】
もしプロセッサが避けられ得るミスを検出したなら、適当なロケーションがデータをストアするためのキャッシュ中で割当てられる（ステップ３５０）。アイドル・ロケーション又は無効データもしくはステール・データを含むロケーションをまず探す（ステップ３６０）ことにより、適当なロケーションを割当てることができる。もしアイドル・ロケーションも無効ロケーションも見つからなければ、使用されたロケーションが割当てられてディスプレースされたデータを置き換える必要がある。使用されたロケーションはアットランダムに或はＬＲＵもしくはＬＦＵのようなアルゴリズムを使用して選べる。
【００３６】
もし選択された使用済みロケーションからディスプレースされたデータを置き換える必要があれば、プロセッサはデータを主メモリにライトバックする（ステップ３６５）。キャッシュの強制的な“ライトスルー”がしいられるユニプロセッサ及びマルチプロセッサ・システムの両方において、キャッシュ及びメモリの内容が常にコヒーレントであるので、ディスプレースされたデータは簡単に捨てられ得る。“コピーバック”キャッシュも、もしディスプレースされたデータが変更されなかったならば、このディスプレースされたデータを簡単に捨てることができる。
【００３７】
逆に、もしキャッシュ・ミスが避けられ得るキャッシュ・ミスではなく且つキャッシュが一杯でもない（ステップ３３０及び３４０）ならば、プロセッサはキャッシュ中でアイドル・ロケーションを割当て且つデータは割当てられたロケーションにストアされる（ステップ３５５及び３７０）。もしキャッシュ・ミスが避けられ得るキャッシュ・ミスでなく且つキャッシュが一杯である（ステップ３３０及び３４０）なら、データはキャッシュされない。
【００３８】
上述した場合の各々にて、データはリクエスト中のプロセッサへ提供される（ステップ３８０）。どのキャッシュ化ステップ３７０の前後でもデータをリクエスト中のプロセッサへ提供できることに注目されたい。
【００３９】
この発明の精神から逸脱しない限り他の変形例や不可例が可能である。例えば、１つの避けられ得るキャッシュ・ミスの後でデータ構造をキャッシュ化する代わりに、避けられ得るキャッシュ・ミスの数が閾値を超えた後でデータ構造をキャッシュしても良い。他の変形例では、より若いデータ構造の過剰ミスの数が転置用に選ばれたより古いデータ構造のキャッシュ・ヒットの数を超える時だけ、より若いデータ構造をキャッシュしても良い。
【図面の簡単な説明】
【図１】 ハイブリッド・キャッシュ・オンリ・メモリ・アーキテクチャ／非一様メモリ・アーキテクチャ（ＣＯＭＡ／ＮＵＭＡ）を有するネットワーク化されたコンピュータ・システムを示すブロック図である。
【図２】 図１のネットワーク化されたコンピュータ・システムのための例示的なメモリ・マップである。
【図３】 マルチプロセッサ・コンピュータ・システム用のこの発明の一実施形態を示すフローチャートである。
【図４】 ユニプロセッサ・コンピュータ・システム用のこの発明の他の実施形態を示すフローチャートである。
【符号の説明】
１００…コンピュータ・システム、１１０，１２０，１８０…サブシステム、１１１ａ〜１８１ｉ…プロセッサ、１１３ａ〜１８３ｉ…第２レベルのハイブリッド・キャッシュ、１１４，１２４，１８４…ＣＯＭＡキャッシュ／メモリ、１１８，１２８，１８８…Ｌ３＄。
Claims (6)
- キャッシュ及び主メモリを有するコンピュータ・システム中でキャッシュされるべきデータを選択する方法であって、
前記キャッシュ中の前記データをサーチするステップと、
前記キャッシュ中で前記データを見い出すことができない時に、キャッシュ・ミスを検出するステップと、そして
前記キャッシュ・ミスが検出されたときに、
前記主メモリから前記データをフェッチするステップと、
前記キャッシュ・ミスが避けられ得るキャッシュ・ミスかどうかを決定するステップと、そして
前記キャッシュ・ミスが前記避けられ得るキャッシュ・ミスであると決定されるとき、または前記キャッシュ中にアイドル・ロケーションがあるとき、そのときのみ前記キャッシュ中に前記データをキャッシュするステップと
を含み、
前記避けられ得るキャッシュ・ミスは、要求されたデータがその前にキャッシュされたことがありかつその要求されたデータがそのキャッシュにとどまるときには生じないキャッシュ・ミスとして、定義される、
コンピュータ・システム中でキャッシュされるべきデータを選択する方法。 - 前記データをキャッシュ化する結果として、前記キャッシュから前記主メモリへ置き換えられた古いデータをライトバックするステップを更に含む請求項１のコンピュータ・システム中でキャッシュされるべきデータを選択する方法。
- 少なくとも第１のサブシステム及び第２のサブシステムを備え、前記サブシステムの各々がキャッシュを含み、前記第２のサブシステムがデータのホーム・サブシステムであるコンピュータ・システム中でキャッシュされるべきデータを選択する方法であって、
前記第１のサブシステムの前記キャッシュ中の前記データをサーチするステップと、
前記第１のサブシステムの前記キャッシュ中で前記データを見い出さない時に、キャッシュ・ミスを検出するステップと、
前記キャッシュ・ミスが検出されたときに、
前記第２のサブシステムから前記第１のサブシステムへ前記データをフェッチするステップと、
前記キャッシュ・ミスが避けられ得るキャッシュ・ミスかどうかを決定するステップと、そして
前記キャッシュ・ミスが前記避けられ得るキャッシュ・ミスであると決定されるとき、または前記キャッシュ中にアイドル・ロケーションがあるとき、そのときのみ前記第１のサブシステムの前記キャッシュ中に前記データをキャッシュするステップと
を含み、
前記避けられ得るキャッシュ・ミスは、要求されたデータがその前にキャッシュされたことがありかつその要求されたデータがそのキャッシュにとどまるときには生じないキャッシュ・ミスとして、定義される、
コンピュータ・システム中でキャッシュされるべきデータを選択する方法。 - 前記データをキャッシュ化する結果として、前記第１のサブシステムから前記第２のサブシステムへ置き換えられたどの古いデータもライトバックするステップを更に含む請求項３のコンピュータ・システム中でキャッシュされるべきデータを選択する方法。
- キャッシュと、
このキャッシュに結合された主メモリと、そして
前記キャッシュと前記主メモリの間に結合され、データの避けられ得るキャッシュ・ミスが前記キャッシュ中で起こる時に前記主メモリから前記キャッシュへ前記データをフェッチし、そしてキャッシュ・ミスが前記避けられ得るキャッシュ・ミスであると決定されるとき、または前記キャッシュ中にアイドル・ロケーションがあるとき、そのときのみ前記キャッシュ中に前記データをキャッシュするように構成されたフェッチャと
を備え、
前記避けられ得るキャッシュ・ミスは、要求されたデータがその前にキャッシュされたことがありかつその要求されたデータがそのキャッシュにとどまるときには生じないキャッシュ・ミスとして、定義される、
コンピュータ・システム。 - コンピュータ・システム用キャッシュ・システムであって、
前記コンピュータ・システムの第１のサブシステムに関連付けられた第１のキャッシュと、
前記コンピュータ・システムの、データのホーム・サブシステムである第２のサブシステムに関連付けられた第２のキャッシュと、そして
前記第１のキャッシュと前記第２のキャッシュとの間に結合され且つデータの避けられ得るキャッシュ・ミスが前記第１のキャッシュ中で起こる時に前記第２のキャッシュから前記第１のキャッシュへ前記データをフェッチし、そしてキャッシュ・ミスが前記避けられ得るキャッシュ・ミスであると決定されるとき、または前記第１のキャッシュ中にアイドル・ロケーションがあるとき、そのときのみ前記第１のサブシステムの前記第１のキャッシュ中に前記データをキャッシュするように構成されたフェッチャと
を備え、
前記避けられ得るキャッシュ・ミスは、要求されたデータがその前にキャッシュされたことがありかつその要求されたデータがそのキャッシュにとどまるときには生じないキャッシュ・ミスとして、定義される、
コンピュータ・システム用キャッシュ・システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US675306 | 1996-07-01 | ||
| US08/675,306 US5893150A (en) | 1996-07-01 | 1996-07-01 | Efficient allocation of cache memory space in a computer system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH10214229A JPH10214229A (ja) | 1998-08-11 |
| JP4101907B2 true JP4101907B2 (ja) | 2008-06-18 |
Family
ID=24709903
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP18460097A Expired - Lifetime JP4101907B2 (ja) | 1996-07-01 | 1997-06-26 | コンピュータ・システム中でキャッシュされるべきデータを選択する方法，コンピュータ・システム，及びコンピュータ・システム用キャッシュ化装置 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5893150A (ja) |
| EP (1) | EP0817078A3 (ja) |
| JP (1) | JP4101907B2 (ja) |
Families Citing this family (47)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5978379A (en) | 1997-01-23 | 1999-11-02 | Gadzoox Networks, Inc. | Fiber channel learning bridge, learning half bridge, and protocol |
| US7430171B2 (en) | 1998-11-19 | 2008-09-30 | Broadcom Corporation | Fibre channel arbitrated loop bufferless switch circuitry to increase bandwidth without significant increase in cost |
| US6532520B1 (en) * | 1999-09-10 | 2003-03-11 | International Business Machines Corporation | Method and apparatus for allocating data and instructions within a shared cache |
| US20020178330A1 (en) * | 2001-04-19 | 2002-11-28 | Schlowsky-Fischer Mark Harold | Systems and methods for applying a quality metric to caching and streaming of multimedia files over a network |
| US7287649B2 (en) * | 2001-05-18 | 2007-10-30 | Broadcom Corporation | System on a chip for packet processing |
| US6766389B2 (en) | 2001-05-18 | 2004-07-20 | Broadcom Corporation | System on a chip for networking |
| US6574708B2 (en) | 2001-05-18 | 2003-06-03 | Broadcom Corporation | Source controlled cache allocation |
| US7212534B2 (en) | 2001-07-23 | 2007-05-01 | Broadcom Corporation | Flow based congestion control |
| US6775745B1 (en) * | 2001-09-07 | 2004-08-10 | Roxio, Inc. | Method and apparatus for hybrid data caching mechanism |
| US7295555B2 (en) | 2002-03-08 | 2007-11-13 | Broadcom Corporation | System and method for identifying upper layer protocol message boundaries |
| US7266587B2 (en) * | 2002-05-15 | 2007-09-04 | Broadcom Corporation | System having interfaces, switch, and memory bridge for CC-NUMA operation |
| US7114043B2 (en) | 2002-05-15 | 2006-09-26 | Broadcom Corporation | Ambiguous virtual channels |
| US7269709B2 (en) * | 2002-05-15 | 2007-09-11 | Broadcom Corporation | Memory controller configurable to allow bandwidth/latency tradeoff |
| US7934021B2 (en) | 2002-08-29 | 2011-04-26 | Broadcom Corporation | System and method for network interfacing |
| US7346701B2 (en) | 2002-08-30 | 2008-03-18 | Broadcom Corporation | System and method for TCP offload |
| EP1554842A4 (en) | 2002-08-30 | 2010-01-27 | Corporation Broadcom | SYSTEM AND METHOD FOR TREATING FRAMES OUTSIDE THE ORDER |
| US8180928B2 (en) | 2002-08-30 | 2012-05-15 | Broadcom Corporation | Method and system for supporting read operations with CRC for iSCSI and iSCSI chimney |
| US7313623B2 (en) | 2002-08-30 | 2007-12-25 | Broadcom Corporation | System and method for TCP/IP offload independent of bandwidth delay product |
| US8165993B2 (en) | 2002-09-06 | 2012-04-24 | Oracle International Corporation | Business intelligence system with interface that provides for immediate user action |
| US7941542B2 (en) * | 2002-09-06 | 2011-05-10 | Oracle International Corporation | Methods and apparatus for maintaining application execution over an intermittent network connection |
| US7945846B2 (en) | 2002-09-06 | 2011-05-17 | Oracle International Corporation | Application-specific personalization for data display |
| US7412481B2 (en) | 2002-09-16 | 2008-08-12 | Oracle International Corporation | Method and apparatus for distributed rule evaluation in a near real-time business intelligence system |
| US8255454B2 (en) | 2002-09-06 | 2012-08-28 | Oracle International Corporation | Method and apparatus for a multiplexed active data window in a near real-time business intelligence system |
| US7899879B2 (en) * | 2002-09-06 | 2011-03-01 | Oracle International Corporation | Method and apparatus for a report cache in a near real-time business intelligence system |
| US7912899B2 (en) * | 2002-09-06 | 2011-03-22 | Oracle International Corporation | Method for selectively sending a notification to an instant messaging device |
| US7401158B2 (en) | 2002-09-16 | 2008-07-15 | Oracle International Corporation | Apparatus and method for instant messaging collaboration |
| US8185602B2 (en) | 2002-11-05 | 2012-05-22 | Newisys, Inc. | Transaction processing using multiple protocol engines in systems having multiple multi-processor clusters |
| US7058773B1 (en) | 2003-01-16 | 2006-06-06 | Cisco Technology, Inc. | System and method for managing data in a distributed system |
| US7904823B2 (en) * | 2003-03-17 | 2011-03-08 | Oracle International Corporation | Transparent windows methods and apparatus therefor |
| US7978716B2 (en) | 2003-11-24 | 2011-07-12 | Citrix Systems, Inc. | Systems and methods for providing a VPN solution |
| US8739274B2 (en) * | 2004-06-30 | 2014-05-27 | Citrix Systems, Inc. | Method and device for performing integrated caching in a data communication network |
| US8495305B2 (en) | 2004-06-30 | 2013-07-23 | Citrix Systems, Inc. | Method and device for performing caching of dynamically generated objects in a data communication network |
| US7757074B2 (en) | 2004-06-30 | 2010-07-13 | Citrix Application Networking, Llc | System and method for establishing a virtual private network |
| CN101199187A (zh) | 2004-07-23 | 2008-06-11 | 茨特里克斯系统公司 | 用于网络节点之间通信最优化的系统和方法 |
| US7808906B2 (en) | 2004-07-23 | 2010-10-05 | Citrix Systems, Inc. | Systems and methods for communicating a lossy protocol via a lossless protocol using false acknowledgements |
| US8954595B2 (en) | 2004-12-30 | 2015-02-10 | Citrix Systems, Inc. | Systems and methods for providing client-side accelerated access to remote applications via TCP buffering |
| US8549149B2 (en) * | 2004-12-30 | 2013-10-01 | Citrix Systems, Inc. | Systems and methods for providing client-side accelerated access to remote applications via TCP multiplexing |
| US7810089B2 (en) | 2004-12-30 | 2010-10-05 | Citrix Systems, Inc. | Systems and methods for automatic installation and execution of a client-side acceleration program |
| US8706877B2 (en) | 2004-12-30 | 2014-04-22 | Citrix Systems, Inc. | Systems and methods for providing client-side dynamic redirection to bypass an intermediary |
| US8255456B2 (en) | 2005-12-30 | 2012-08-28 | Citrix Systems, Inc. | System and method for performing flash caching of dynamically generated objects in a data communication network |
| US8301839B2 (en) | 2005-12-30 | 2012-10-30 | Citrix Systems, Inc. | System and method for performing granular invalidation of cached dynamically generated objects in a data communication network |
| US7921184B2 (en) | 2005-12-30 | 2011-04-05 | Citrix Systems, Inc. | System and method for performing flash crowd caching of dynamically generated objects in a data communication network |
| US8504774B2 (en) * | 2010-10-13 | 2013-08-06 | Microsoft Corporation | Dynamic cache configuration using separate read and write caches |
| US8751751B2 (en) | 2011-01-28 | 2014-06-10 | International Business Machines Corporation | Method and apparatus for minimizing cache conflict misses |
| US10642709B2 (en) | 2011-04-19 | 2020-05-05 | Microsoft Technology Licensing, Llc | Processor cache tracing |
| US9612972B2 (en) * | 2012-12-03 | 2017-04-04 | Micron Technology, Inc. | Apparatuses and methods for pre-fetching and write-back for a segmented cache memory |
| CN108832909A (zh) * | 2018-06-21 | 2018-11-16 | 重庆兆洲科技发展有限公司 | 时差法信号采集中数字滤波的处理方法 |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5625793A (en) * | 1991-04-15 | 1997-04-29 | International Business Machines Corporation | Automatic cache bypass for instructions exhibiting poor cache hit ratio |
| GB2273181A (en) * | 1992-12-02 | 1994-06-08 | Ibm | Cache/non-cache access control. |
| US5535116A (en) * | 1993-05-18 | 1996-07-09 | Stanford University | Flat cache-only multi-processor architectures |
-
1996
- 1996-07-01 US US08/675,306 patent/US5893150A/en not_active Expired - Lifetime
-
1997
- 1997-06-26 JP JP18460097A patent/JP4101907B2/ja not_active Expired - Lifetime
- 1997-06-30 EP EP97304723A patent/EP0817078A3/en not_active Withdrawn
Also Published As
| Publication number | Publication date |
|---|---|
| EP0817078A3 (en) | 1998-01-21 |
| US5893150A (en) | 1999-04-06 |
| EP0817078A2 (en) | 1998-01-07 |
| JPH10214229A (ja) | 1998-08-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4101907B2 (ja) | コンピュータ・システム中でキャッシュされるべきデータを選択する方法，コンピュータ・システム，及びコンピュータ・システム用キャッシュ化装置 | |
| EP0780769B1 (en) | Hybrid numa coma caching system and methods for selecting between the caching modes | |
| US6826651B2 (en) | State-based allocation and replacement for improved hit ratio in directory caches | |
| US5893144A (en) | Hybrid NUMA COMA caching system and methods for selecting between the caching modes | |
| US6304945B1 (en) | Method and apparatus for maintaining cache coherency in a computer system having multiple processor buses | |
| JP3866447B2 (ja) | マルチプロセッサ・ノードデータ処理システムに使用するディレクトリエントリ割当てシステム及び方法 | |
| US8015365B2 (en) | Reducing back invalidation transactions from a snoop filter | |
| US8281079B2 (en) | Multi-processor system receiving input from a pre-fetch buffer | |
| US6725341B1 (en) | Cache line pre-load and pre-own based on cache coherence speculation | |
| US6647466B2 (en) | Method and apparatus for adaptively bypassing one or more levels of a cache hierarchy | |
| US12093177B2 (en) | Multi-level partitioned snoop filter | |
| JP4068185B2 (ja) | コンピュータ・システムでのメモリ・ストレージ・モードの効果的な選択 | |
| JP4447580B2 (ja) | 分散共有メモリマルチプロセッサシステムのための分割疎ディレクトリ | |
| US5903907A (en) | Skip-level write-through in a multi-level memory of a computer system | |
| GB2318657A (en) | Cache consistency in multiprocessor systems | |
| CN119883947B (zh) | 数据中心多层次解聚合内存系统 | |
| US8078818B2 (en) | Method and system for migrating memory segments |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20040608 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20070724 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070807 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20071107 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20071112 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20071207 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20071212 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20071228 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20080122 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20080201 |
|
| 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: 20080219 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20080321 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110328 Year of fee payment: 3 |
|
| 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: 20110328 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120328 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130328 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130328 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140328 Year of fee payment: 6 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |