(57)【要約】【課題】  データの部分が、低速メイン・メモリに格納され、１つ又は複数のプロッセサと該メイン・メモリとの間の高速メモリに転送されるキャッシングを提供すること。【解決手段】  データの部分が、低速メイン・メモリに格納され、１つ又は複数のプロッセサと該メイン・メモリとの間の高速メモリに転送されるキャッシングである。キャッシュは、個々のキャッシュ・システムが、他の関連したキャッシュ・システムに通信するか又はこうしたキャッシュ・システムに問い合わせを行い、所定のキャッシュ位置におけるデータの修正又は取得時に、或いはその前に、該キャッシュ・システムが所定のキャッシュ位置のコピーを含むかどうかを判断するというものである。キャッシュは、特定の記憶位置に格納されたデータを置き換えることができる時点を判断するための備えをさらに含む。【選択図】      図１
2007200292.tif 000002
【特許請求の範囲】
【請求項１】
１つ又は複数のプロセッサ、メイン・メモリ、及び前記１つ又は複数のプロセッサと前記メイン・メモリとの間に設けられた高速メモリを含むシステムにおけるデータ・キャッシング方法であって、
前記高速メモリとの間で転送を行うために、データを前記メイン・メモリに格納するステップと、
個々のキャッシュが、データの読み出し、データの書き込み、又はキャッシュされたデータの変更の前に、他の関連するキャッシュに通信して、前記他の関連するキャッシュが所与のキャッシュ位置のコピーを含むかどうかを判断するステップと、
特定のキャッシュ記憶位置に格納されたデータを置き換えることができる時点を判断するステップと
を含む方法。
【請求項２】
Ｌ１キャッシュにおいてラインが置き換えられるとき、Ｌ２キャッシュにおけるラインの状態に変更を書き込むステップを含む、請求項１に記載の方法。
【請求項３】
前記ラインの前記状態を、特定の識別されたプロセッサ専用からどのプロセッサにも専用でないものに変更するステップを含む、請求項２に記載の方法。
【請求項４】
関連するＬ１キャッシュを有する複数のプロセッサと、
前記Ｌ１キャッシュと関連付けられたＬ２キャッシュと、
メイン・メモリとを備え、
個々のキャッシュが、データの読み出し、データの書き込み、又はキャッシュされたデータの変更の前に、他の関連するキャッシュに通信して、前記他のキャッシュが所与のキャッシュ位置のコピーを含むかどうかを判断し、特定のキャッシュ記憶位置に格納されたデータを置き換えることができる時点を判断するように構成された、
コンピュータ・システム。
【請求項５】
関連するＬ１キャッシュを有する複数のプロセッサ、前記Ｌ１キャッシュと関連付けられたＬ２キャッシュ、及びメイン・メモリを備えるコンピュータ・システムを構成し、制御するためのコンピュータ可読プログラム・コードを含むプログラムであって、
前記プロッセサ及び前記メイン・メモリとの間の転送のために、前記キャッシュにデータを格納させる手順と、
個々のキャッシュに、データの読み出し、データの書き込み、又はキャッシュされたデータの変更の前に、他の関連するキャッシュへの通信を行わせ、前記他の関連するキャッシュが所与のキャッシュ位置のコピーを含むかどうかを判断する手順と、
特定のキャッシュ記憶位置に格納された前記データを置き換えることができる時点を判断する手順と、
を前記コンピュータ・システムに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データが低速メイン・メモリに格納され、１つ又は複数のプロッセサと該メイン・メモリとの間の高速メモリに転送されるキャッシングに関する。システムは、個々のキャッシュ・システムが、所与のキャッシュ位置のコピーを含む可能性のある他のキャッシュ・システムに対し、該所与のキャッシュ位置におけるデータを変更又は取得する前に、或いはデータを変更又は取得する時点で、告知を行うか又は問い合わせを行うように構成され、特定の記憶位置に格納されたデータを置き換えることができる時点を判断するための備えを含む。
【背景技術】
【０００２】
例えば、レベル２（Ｌ２）キャッシュのような共有の２次キャッシュを備えたマルチプロセッサ・システムにおいて、共有キャッシュは、例えばレベル１（Ｌ１）キャッシュのような下位キャッシュにおけるキャッシュの実際の記憶量を超えたラインを保持している。これが２次キャッシュの重要性であり、２次キャッシュは、全ての下位キャッシュのスーパーセットを含む。このことにより、メイン・メモリからのトラフィックが低減される。
【０００３】
例えば、プロセッサＡが、格納のためのラインを要求するとき（「ＥＸ」すなわち排他要求）、そのラインは、プロセッサＡ専用として、Ｌ１キャッシュ及びＬ２キャッシュの両方にインストールされる。別のプロセッサＢがそのラインを要求したとき、該ラインがプロセッサＡ専用に保持されている場合、処理が長引くことになる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、プロセッサＡが、そのラインをもはや使用しておらず、実際には、該ラインがＬ１において時間経過し、Ｌ２内にのみ存在していることがよくある。それにもかかわらず、ラインは依然としてプロセッサＡ専用とマーキングされている。したがって、このラインをＬ１キャッシュから除去するために、相互調査及び相互無効化のような追加の処理が必要とされる。
【０００５】
ここに説明されるように、多くの場合、このラインはもはやＬ１内に存在しない。このことが、プロセッサＢの取り出し要求を不必要に長引かせ、性能を低減させることになる。したがって、このプロセスを加速するための必要性が存在する。
【課題を解決するための手段】
【０００６】
ここに説明される方法及びシステムは、データが、低速メイン・メモリに格納され、１つ又は複数のプロッセサと該メイン・メモリとの間の高速メモリに転送されるキャッシングを提供するものである。一般に、キャッシュは、個々のキャッシュ・システムが、他の関連したキャッシュ・システムに通信するか、又はこうしたキャッシュ・システムに問い合わせを行い、所与のキャッシュ位置におけるデータの変更又は取得時に、或いはその前に、それらのキャッシュ・システムが所与のキャッシュ位置のコピーを含むかどうかを判断しなければならないというものである。このキャッシュは、特定の記憶位置に格納されたデータを置き換えることができる時点を判断するための備えをさらに含む。
【０００７】
背景として、ラインは、いずれかのプロセッサが使用することになるＬ１キャッシュ内になければならない。ここで、ラインがＬ１及びＬ２の両方の中に存在するとき、両方のキャッシュにおいてラインの状態が合致すると言われる。つまり、ラインは、両方のレベルで同じように、専用、共有、または変更とマーク付けされる。ラインがＬ１において時間経過し、Ｌ２内だけに存在する場合、そのラインは、もはや元のプロセッサによって使用されていない。より最近使用されたラインが、そのラインと置き換わっている。しかしながら、Ｌ２キャッシュは、ラインをそのプロセッサ「専用」の状態に保持し続ける。
【０００８】
ここに説明される方法及びシステムは、Ｌ１キャッシュにおいてラインが置き換えられるときに、Ｌ２キャッシュにおけるラインの状態を変更するというものである。状態は、特定の識別されたプロセッサ専用から、どのプロセッサにも専用でないものに変更される。このように、専用ラインが特定のプロセッサにおいて時間経過したとき、Ｌ２におけるそのラインの状態が、特定の識別されたプロセッサ専用から「非専用」に変わり、いずれのＬ１キャッシュについても相互調査又は相互無効化が必要でなくなり、これによりシステムの性能全体が改善される。
【発明を実施するための最良の形態】
【０００９】
データが、低速メイン・メモリに格納され、１つ又は複数のプロセッサと該メイン・メモリとの間の高速メモリに転送されるキャッシングである。このキャッシュは、個々のキャッシュ・システムが、他の関連したキャッシュ・システムに通信するか、又はこうしたキャッシュ・システムに問い合わせを行い、所与のキャッシュ位置におけるデータの変更又は取得時に、或いはその前に、それらのキャッシュ・システムが所与のキャッシュ位置のコピーを含むかどうかを判断しなければならないというものである。このキャッシュは、特定の記憶位置に格納されたデータを置き換えることができる時点を判断するための備えをさらに含む。
【００１０】
ここで説明されるように、専用ラインがＬ１キャッシュにおいて時間経過したとき、Ｌ１はＬ２キャッシュに信号を送り、そのラインが、もはやＬ１キャッシュ内に存在しないことを示す。これにより、このラインの「所有権喪失」を示すように、Ｌ２キャッシュが更新される。つまり、所有権が、特定のプロセッサから「非所有」に変更される。
【００１１】
背景として、技術の進歩にもかかわらず、マイクロプロセッサは、依然としてメイン・メモリよりはるかに高速である。メモリ・アクセス時間が、ますます、アプリケーションの性能全体の障害になっている。その結果、アプリケーションは、データを待つのに相当な時間を費やすことになる。このことは、性能全体に悪影響を与えるだけでなく、プロセッサのクロック速度の向上から、アプリケーションが多くの利益を得ることもできなくなる。
【００１２】
この問題を克服するための１つの方法は、プロセッサとメイン・メモリとの間に小さい高速バッファ・メモリを挿入することである。こうしたバッファは、通常、キャッシュ・メモリ又は略してキャッシュと呼ばれる。こうしたバッファ又はキャッシュが、図１に示されている。
【００１３】
図１は、プロセッサ１１１、Ｌ１キャッシュ１１３、Ｌ２キャッシュ１２１、及びメイン・メモリ１３１を含むプロセッサ・システム１０１を示す。システム上で動作しているアプリケーションは、メイン・メモリの代わりにキャッシュからデータを取り出すことによって、この機能向上を利用する。キャッシュへのアクセス時間が短くなるおかげで、アプリケーションの性能が改善される。勿論、依然としてメモリとキャッシュとの間にトラフィックはあるが、それは最小限のものである。
【００１４】
システム１０１は、まず、プロッセサ１１１が必要とするデータを、メイン・メモリ１３１からＬ２キャッシュ１２１にコピーし、次いで、Ｌ２キャッシュ１２１からＬ１キャッシュ１１３に、そしてプロッセサ１１１内のレジスタ（図示せず）にコピーする。結果の格納は、反対の方向に行われる。まず、システムは、データを、プロッセサ１１１からＬ１キャッシュ１１３にコピーし、Ｌ１キャッシュ１１３からＬ２キャッシュ１２１にコピーする。次に、キャッシュ・アーキテクチャの詳細によって、データが直ちにメモリ１３１にコピーされるか（ライト・スルー）又は遅らせられる（ライト・バック）。アプリケーションが再び同じデータを必要とする場合、データが依然としてＬ１キャッシュ１１３及びＬ２キャッシュ１２１内にあるか又はＬ２キャッシュ１２１内だけにある場合には、データ・アクセス時間が著しく低減される。メモリ転送のコストをさらに減少させるために、１つより多い要素が、キャッシュ内にロードされる。転送の単位は、キャッシュ・ブロック又はキャッシュ・ラインと呼ばれる。単一のデータ要素へのアクセスにより、ライン全体がキャッシュに入れられる。このラインは、要求された要素を含むことが保証される。
【００１５】
待ち時間及び帯域幅は、キャッシュ及びメモリと関連した２つのメトリクスである。どちらも一定ではなく、メモリ階層の特定のコンポーネントに特有のものである。待ち時間は、多くの場合、プロセッサ・サイクル又はナノ秒で表され、帯域幅は、通常、メガバイト／秒又はギガバイト／秒で与えられる。
【００１６】
実際には、メモリ・コンポーネントの待ち時間は、転送の単位（一般的には、キャッシュ・ライン）の最初の部分を取り出すのに要する時間として測定される。コンポーネントの速度は、階層内の相対的位置によって決まるので、待ち時間は一定でない。大まかに言えば、Ｌ１キャッシュ１１３からＬ２キャッシュ１２１、メイン・メモリ１３１に向かうにつれて待ち時間が増大すると言える。
【００１７】
例えば、Ｌ１キャッシュ１１３のような一部のメモリ・コンポーネントを、プロセッサ１１１上に物理的に配置することができる。この利点は、これらのメモリ・コンポーネントの速度がプロセッサ・クロックによって増減されることである。したがって、こうしたコンポーネントの待ち時間を、ナノ秒の代わりにプロセッサ・クロック・サイクルで表すことは、意味のあることである。
【００１８】
幾つかのマイクロプロセッサにおいては、Ｌ１キャッシュ１１３のような統合された（オンチップ）キャッシュが常にプロセッサの速度で動作するとは限らない。これらは、プロセッサ・クロックの整数比率（１／２、１／３等）のクロック速度で作動する。
【００１９】
プロセッサの外部にあるキャッシュ・コンポーネントは、通常、プロセッサ・クロックの向上から恩恵を受けないか、又は部分的に恩恵を受けるにすぎない。これらの待ち時間は、ナノ秒で与えられることが多い。メイン・メモリの待ち時間は、ほとんどの場合、ナノ秒で表される。
【００２０】
帯域幅は、メモリ・コンポーネントの漸近速度の尺度である。この値は、大量のデータをどれだけ速く出し入れできるかを反映する。待ち時間と同様に、帯域幅は一定でない。一般に、帯域幅は、プロッセサ１１１から遠ざかるにつれて減少する。
【００２１】
データ取り出しにおけるステップ数を減らすことができる場合、待ち時間が低減される。
【００２２】
図２は、Ｌ１キャッシュ２１３ａ、２１３ｂを備えた２つのプロセッサ２１１ａ、２１１ｂ、共有のＬ２キャッシュ２２１、及びメイン・メモリ２３１を含むシステム２０１を示す。データ・ライン２４１及び制御ライン２５１は、通常の機能を果たす。図２に関しては、専用ラインがＬ１キャッシュ２１３ａ又は２１３ｂにおいて時間経過したとき、Ｌ１キャッシュ２１３ａ又は２１３ｂは、信号をＬ２キャッシュ２２１に送り、そのラインが、もはやＬ１キャッシュ２１３ａ又は２１３ｂ内に存在しないことを示す。これにより、そのラインの所有権が失われたことを示すように、Ｌ２キャッシュ２２１が更新される。つまり、所有権が、特定のプロセッサから「非所有」に変更される。
【００２３】
図３は、制御ライン及びデータ・ライン、並びに例示的なキャッシュ・ライン内の有効性ブロック３２３、アドレス・ブロック３２５、及びデータ・ブロック３２７と共に、システム３０１のコンポーネント、すなわちＬ１キャッシュ３１３、プロセッサ・ユニット３１１、Ｌ２キャッシュ３２１、書き込みバッファ３３０、メイン・メモリ３３１、及びＭＵＸ３３３を示す。
【００２４】
専用ラインがＬ１キャッシュ３１３において時間経過したとき、Ｌ１キャッシュ３１３は、Ｌ２キャッシュ３２１に信号を送り、このラインが、もはやＬ１キャッシュ３１３内に存在しないことを示す。これにより、このラインの所有権が失われたことを示すように、Ｌ２キャッシュ３２１が更新される。つまり、所有権が、特定のプロセッサから「非所有」に変更される。
【００２５】
図３に示されるキャッシュについて考慮する。プロセッサ３１１は、タグの比較のために、物理アドレスをＬ２キャッシュ３２１に提示する。Ｌ２キャッシュ３２１に入ってくるアドレスは、２つのフィールド、すなわちブロック・アドレス及びオフセット・アドレスを有し、ブロック・アドレスは、アドレス・タグ、キャッシュ索引の表示、及び制御データを含む。
【００２６】
キャッシュ索引は、所望のブロックがキャッシュ内にあるかどうかを確かめるために試験されることになるタグを選択する。次のステップは、索引の選択である。ダイレクト・マッピングの場合は、タグの読み込み及びチェックと並行して、データが読み込まれ、プロセッサ３１１に送られる。
【００２７】
キャッシュ３２１からタグを読み込んだ後、プロセッサ３１１からのブロック・アドレスのタグ部分と比較される。タグ及びデータ・ラインの両方が有効な情報を含むことを確認するために、（プロセッサ専用又は「非所有」のような）有効性データを読み込み、検証しなければならない。キャッシュ・データが有効である場合、プロセッサ３１１は、信号を送り、Ｌ２キャッシュ３２１からデータをロードする。
【００２８】
書き込みの場合、メイン・メモリに書き込むために、書き込みバッファ３３０にもデータが書き込まれる。
【００２９】
キャッシュ・ミスの場合、Ｌ１キャッシュ３１３は、停止信号をプロセッサ３１１に送り、読み取りをＬ２キャッシュ３２１に、さらにメイン・メモリ３３１に送る。メイン・メモリから読み取ることにより、キャッシュ中のライン、例えばデータ、タグ、及び有効性情報を含む、典型的には最も長い間使用されなかったラインが置き換えられる。
【００３０】
本発明の方法及びシステムによると、専用ラインがＬ１キャッシュにおいて時間経過し、Ｌ１キャッシュが信号をＬ２キャッシュに送ると、そのラインが、もはやＬ１キャッシュ内に存在せず、これにより該ラインの所有権が失われたことを示すようにＬ２キャッシュが更新される。つまり、所有権が、特定のプロセッサから「非所有」に変更される。
【００３１】
図２を見ると、このことは、相互調査処理を減少させ、場合によっては、さらに排除することによって、性能を改善させる。相互調査処理を排除することにより、Ｌ１の置き換え又は時間経過による置き換えのため、Ｌ１キャッシュ２１３ａ又は２１３ｂ内にもはや存在しないラインについて、Ｌ１キャッシュ２１３ａ又は２１３ｂに相互調査を送ることが回避される。これにより、次に別のプロセッサがラインを要求するときの待ち時間が短くなり、他方のＬ１キャッシュにおける無益なディレクトリ検索が回避される。
【００３２】
さらに、相互調査処理を排除することにより、Ｌ２キャッシュ２２１において置き換えられることになるラインに対して、相互無効化をＬ１キャッシュ２１３ａ又は２１３ｂに送ることが回避される。通常、ラインがＬ２キャッシュ２２１において時間経過したとき、Ｌ１キャッシュ２１３ａ又は２１３ｂにおいても、そのラインを無効化しなければならない。このことが、Ｌ１キャッシュ２１３ａ又は２１３ｂとＬ２キャッシュ２２１との間のサブセット・ルールを維持する。これらの２つの無効化は、Ｌ１キャッシュ２１３ａ又は２１３ｂにおける通常の処理を中断させる。ラインがもはやＬ１キャッシュ２１３ａ又は２１３ｂ内に存在しない場合には、この中断は不必要なものであり、性能に悪影響を及ぼす。
【００３３】
本発明の方法及びシステムが専用ライン（排他ライン）に関して説明されたが、ここに説明される方法及びシステムは、Ｌ１キャッシュ２２１ａ又は２２１ｂにおいて時間経過する共有ラインについて、Ｌ２キャッシュ・ディレクトリ２２１を更新するとき、該共有ラインに対する相互調査及び相互無効化を回避することも理解すべきである。
【００３４】
どのＬ１キャッシュがラインを保持しているかを識別するために、Ｌ１共有キャッシュ実装が各々のプロセッサについて別個のビットを維持する場合には、ラインがＬ１キャッシュ２１３ａ又は２１３ｂにおいて時間経過するたびに、Ｌ２キャッシュ２２１におけるそれぞれの「ＣＰがラインを保持している」ビットをリセットすることができる。アクティブな「ＣＰがラインを保持している」ビットを有するＣＰに対してのみ、相互調査及び相互無効化を行うことが必要である。全てのビットが非アクティブである場合には、相互調査及び相互無効化が回避される。このように、Ｌ２キャッシュ２２１の時間経過による置き換えにより、Ｌ１キャッシュ２１３ａ又は２１３ｂに対する不必要な相互無効化が回避される。このことによっても、Ｌ１キャッシュ２１３ａ又は２１３ｂにおける不必要な中断を回避することにより、性能が改善される。
【００３５】
本発明の更に別の態様は、コンピュータ・システムを構成し、制御するためのコンピュータ可読プログラム・コードを含むプログラムである。このコンピュータ・システムは、各々が、関連するＬ１キャッシュ２１３ａ又は２１３ｂ、Ｌ１キャッシュ２１３ａ又は２１３ｂと関連付けられたＬ２キャッシュ２２１、及びメイン・メモリ２３１を有する、複数のマイクロプロセッサを含む。プログラムは、プロッセサ及びメイン・メモリとの間の転送のために、キャッシュにデータを格納させ、さらに、個々のキャッシュに、データの読み出し、データの書き込み、またはキャッシュされたデータの変更の前に、他のキャッシュへの通信を行わせ、それらのキャッシュが所与のキャッシュ位置のコピーを含むかどうかを判断する。コンピュータ・コードは、特定のキャッシュ記憶位置に格納されたデータを置き換えることができる時点も判断する。
【００３６】
具体的には、コンピュータ・コードは、Ｌ１キャッシュにおいてラインが置き換えられることになるとき、Ｌ２キャッシュにおけるラインの状態に変更を書き込み、ラインの状態を特定の識別されたプロセッサ専用から、どのプロセッサにも専用でないものに変更する。
【００３７】
本発明は、特定の好ましい実施形態及び例証を用いて説明されたが、本発明の範囲を制限するように意図されるものではなく、特許請求の範囲によってのみ制限される。
【図面の簡単な説明】
【００３８】
【図１】プロセッサ、Ｌ１キャッシュ、Ｌ２キャッシュ、及びメイン・メモリを含むシステム示す。
【図２】Ｌ１キャッシュを有する２つのプロセッサ、共有のＬ２キャッシュ、及びメイン・メモリを含むシステムを示す。
【図３】制御ライン及びデータ・ライン、並びに例示的なキャッシュ・ラインにおける有効性ブロック、アドレス・ブロック、及びデータ・ブロックと共に、キャッシュ、プロセッサ、及びメイン・メモリを示す。
【図１】
2007200292.tif 000003
【図２】
2007200292.tif 000004
【図３】
2007200292.tif 000005