(57)【特許請求の範囲】
【請求項１】
低レベルのキャッシュ（ＬＬＣ）及び高レベルのキャッシュ（ＨＬＣ）を有するコンピュータ・システム中のメモリ空間を使用する方法であって、
前記低レベルのキャッシュ中のデータのブロックの複数のデータ部分を増分的にストアするステップと、
前記低レベルのキャッシュにストアされた前記複数のデータ部分の数が閾値を超えるときを検出するステップと、そして  前記検出時に、
前記データのブロックから前記複数のデータ部分をストアするために前記高レベルのキャッシュ中にデータの前記ブロックのためのメモリ空間を割り当てるステップと、そして  前記データのブロックの前記複数のデータ部分を前記高レベルのキャッシュの前記割り当てられたメモリ空間にストアするステップと、を含むコンピュータ・システム中のメモリ空間を使用する方法。
【請求項２】
プロセッサと、
データの複数のブロックであって、その各々のブロックが複数のデータ部分を含むものをストアする主メモリと、前記データ部分のコピーをキャッシュするための低レベルのキャッシュ（ＬＬＣ）と、
データの前記複数のブロックのコピーをキャッシュするための高レベルのキャッシュ（ＨＬＣ）と
を備えたコンピュータ・システム用キャッシュ・リソース・アロケータであって、
前記低レベルのキャッシュ（ＬＬＣ）に結合され、且つ前記低レベルのキャッシュ（ＬＬＣ）中にキャッシュされている前記複数のブロックの１つと関連付けられたデータ部分の数が閾値を超えるときを決定するように構成されたカウンタであって、前記決定のときに、前記複数のブロックの前記１つと関連付けられた前記キャッシュされたデータ部分をストアするために、前記高レベルのキャッシュ（ＨＬＣ）中にメモリ空間を割り当て、そして更に前記複数のブロックの前記１つと関連付けられた前記キャッシュされたデータ部分を前記高レベルのキャッシュ（ＨＬＣ）の前記割り当てられたメモリ空間にストアさせるカウンタ、
を備えるコンピュータ・システム用キャッシュ・リソース・アロケータ。
【請求項３】
プロセッサと、
このプロセッサに結合され且つデータの複数のブロックをストアするように配置され、その各々のブロックが複数のデータ部分を含む主メモリと、
前記プロセッサに結合され且つ前記データ部分のコピーをキャッシュするように配置された低レベルのキャッシュ（ＬＬＣ）と、
このＬＬＣに結合され且つ前記データのブロックのコピーをキャッシュするように配置された高レベルのキャッシュ（ＨＬＣ）と、
前記ＬＬＣに結合され且つ前記ＬＬＣ中でキャッシュされた前記ブロックの１つと関連付けられたデータ部分の数が何時閾値を超えるかを決定するように配置され、前記決定のときに、前記複数のブロックの前記１つと関連付けられた前記キャッシュされたデータ部分をストアするために、前記高レベルのキャッシュ（ＨＬＣ）中にメモリ空間を割り当て、そして更に前記複数のブロックの前記１つと関連付けられた前記キャッシュされたデータ部分を前記高レベルのキャッシュ（ＨＬＣ）の前記割り当てられたメモリ空間にストアさせるカウンタと、
を備えたコンピュータ・システム。
【請求項４】
コンピュータ・システム中のキャッシュ・リソースを割り当てるためのコード・モジュールを有するコンピュータで読取り可能な記録媒体であって、
前記コンピュータ・システムは、
プロセッサと、
データの複数のブロックであって、その各々のブロックが複数のデータ部分を含む、複数のブロックをストアするための主メモリと、
前記複数のデータ部分のコピーをキャッシュするための低レベルのキャッシュ（ＬＬＣ）と、
データの前記複数のブロックのコピーをキャッシュするための高レベルのキャッシュ（ＨＬＣ）と、を備え、
前記コード・モジュールは、前記コンピュータ・システムに、前記低レベルのキャッシュ（ＬＬＣ）中にキャッシュされた前記複数のブロックの１つと関連付けられた複数のデータ部分の数が閾値を超えるときを決定し、そしてその決定に応答して、データの前記１つのブロックの前記複数のデータ部分をストアするために前記高レベルのキャッシュ中にメモリ空間を割り当て、そしてデータの前記１つのブロックの前記複数のデータ部分を前記高レベルのキャッシュの前記割り当てられたメモリ空間にストアする処理を実行させるためのものである、
コンピュータで読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、コンピュータ・システムのメモリに関し、詳細にはコンピュータ・システム中でメモリ・ストレージ・モードを効率良く選択することに関するものである。
【０００２】
【従来の技術】
小さな第１レベルのキャッシュ及び大きな第２レベルのキャッシュを有するマルチレベルのキャッシュ・コンピュータ・システムの簡単なキャッシュ空間割当て技術では、全てのデータ構造が両方のレベルのキャッシュに自動的にキャッシュされる。もしデータ構造のサイズがより小さい低レベルのキャッシュよりも大きければ、即ちデータ構造が低レベルのキャッシュに合わないなら、データ構造は低レベルのキャッシュから置き換えられる。もしデータ構造がより大きい高レベルのキャッシュよりも小さいならば、データ構造の内容の大部分は高レベルのキャッシュに残る。
【０００３】
残念なことに、データ構造の幾らかの成分ないし部分は頻繁にアクセスされるが、他は１回しかアクセスされない。そして統計分析とデータ構造を所有するプログラムの知識との少なくとも一方がなければ特定の部分への将来のアクセスを予測するのは容易でない。例えば、コンピュータ・プログラムは、アレイの各エレメントをアクセスすることにより、大きいアレイを使用するかもしれない。各エレメントは、一時変数を含むかなり複雑な計算に使用される。この例では、大きなアレイの全エレメントをキャッシュ化することは計算速度を実質的に速めない。対照的に、一時変数をキャッシュ化するとプログラムの実行を速めることになる。
【０００４】
従って、上述した方法は簡単であるが、再びアクセス中の特定の部分の可能性が親データ構造のサイズに必ずしも関連付けられないので、その方法は効率が悪い。キャッシュ・メモリは無限に大きくないので、キャッシュ・メモリ空間を効率良く使用しないと、他の有用なデータ構造を早目に置き換える、即ち後続のアクセス前にキャッシュから追い出すことになる。
【０００５】
【発明が解決しようとする課題】
従って、キャッシュの用い方を最大にすると共にデータへの全アクセス時間を最短にするために、マルチレベルのキャッシュ・コンピュータ・システム中で高レベルのキャッシュ・メモリ空間の割当を最適化し、キャッシュ化即ちキャッシュイング用データ構造を選択するための効率の良い機構の必要性がある。
【０００６】
【課題を解決するための手段】
本発明は、少なくとも低レベルのキャッシュ（ＬＬＣ）と高レベルのキャッシュ（ＨＬＣ）を有するコンピュータ・システムのマルチレベルのキャッシュ階層のメモリ・ストレージ・モードを選択するための効率の良い方法を提供する。
【０００７】
１つの実施態様では、低レベルのキャッシュ（ＬＬＣ）のメモリ空間はキャッシュ・ライン・サイズのユニット中で割当てられるが、高レベルのキャッシュ（ＨＬＣ）のメモリ空間はページ・サイズ化されたユニット中で割当てられ、各ページは２つ以上のキャッシュ・ラインを含む。しかしながら、データの複数の部分及びブロックをストアするのに用いられた例示的なメモリ・ユニットがそれぞれキャッシュ・ライン及びページであるが、この発明は他のメモリ・ユニットやサブユニットにも適用できる。
【０００８】
従って、プログラムを実行中、データのページ・サイズのブロックのキャッシュ・ライン・サイズの部分は、複数のＬＬＣのキャッシュ・ラインに増分的にストアされる。その後、コンピュータ・システムは、それがキャッシュ・リソースの割当て即ちＬＬＣとＨＬＣへの割当てを再検討するための機会であることを決定する。リビュー（再検討）・トリガはプロセッサの各部機器例えばプロセッサに周期的に割込むタイマで良い。或は、このリビュー・トリガは、例えばＬＬＣが一杯の時又はＨＬＣの使用がある百分率よりも低下する時に、ＬＬＣから又はＨＬＣからで良い。
【０００９】
割当ての再検討は、データのそれぞれのブロックに関連した部分を識別して、ブロックで識別されたキャッシュド（キャッシュされた）部分の数が閾値を超えたかどうかを決定することを含む。もし閾値が特定のブロックに関連したキャッシュド部分に対して超えたら、空間はブロックからの部分をストアするためにＨＬＣ中で割当てられる。この方法は、ＨＬＣを最適に使用してメモリのブロックにかなりの数の有用な部分をストアすることにより、将来のキャッシュのヒットの見込みを好都合に増加させる。
【００１０】
ＣＯＭＡ／ＮＵＭＡコンピュータ・システムで実施されたような一実施形態では、メモリ・ストレージ・ロケーション即ちＨＬＣ対ＬＬＣを選択することは、ＣＯＭＡ及びＮＵＭＡキャッシュイング・モードを選択することに相当する。しかしながら、選択方法は、ＣＯＭＡオンリ又はＮＵＭＡオンリ・キャッシュを含めてこれだけに制限されない全てのレベルのキャッシュにも、そして広範囲のキャッシュ及びシステム・アーキテクチャにも適用できる。
【００１１】
【発明の実施の形態】
この発明のコンピュータ・システムの目的、特徴及び利点は、以下の説明から明らかになろう。
以下の説明中の符号は発明を完全に理解するために付けた。符号を付けたものの中には、コンピュータ・システムのメモリ・リソース例えばキャッシュを割当てる安価な方法の実施を支援する機能ブロック及び例示的なキャッシュ・アーキテクチャがある。加えて、ＮＵＭＡ／ＣＯＭＡマルチプロセッサ・コンピュータ・システム用のモード選択を含む特定のキャッシュ割当て方法についてこの発明を説明するが、広範囲のキャッシュ及びシステムのアーキテクチャにこの発明を適用できる。なお、この発明を必要以上に不明瞭にしないために周知の回路や構成は詳しく説明しない。
【００１２】
本願出願人の先行出願には、ネットワーク化されたコンピュータ・システム用の共有主記憶アドレス空間及びコヒーレントなキャッシュイング・システムを有するハイブリッド・キャッシュオンリ・メモリ・アーキテクチャ／非一様メモリ・アーキテクチャ（ＣＯＭＡ／ＮＵＭＡ）が開示されており、上述したネットワーク化されたコンピュータ・システムはこの発明を実施するための適当な例示的ハードウェア環境を提供する。
【００１３】
図１はそのようなハイブリッドＣＯＭＡ／ＮＵＭＡコンピュータ・システム１００を示すブロック図である。このコンピュータ・システム１００は、グローバル・インターコネクト１９０を介して互いに結合された複数のサブシステム（ノード）１１０，１２０，…１８０を含む。各サブシステムには特有のネットワーク・ノード・アドレスが割当てられる。各サブシステムは、１個以上のプロセッサ、対応する数のメモリ管理ユニット（ＭＭＵ）及び第２レベルのハイブリッド・キャッシュ（Ｌ２＄）、ＣＯＭＡキャッシュ／メモリ、グローバル・インターフェイス、第３レベルのキャッシュ（Ｌ３＄）及びローカル・インターコネクトを含む。例えば、サブシステム１１０はプロセッサ１１１ａ，１１１ｂ，…１１１ｉ，ＭＭＵ１１２ａ，１１２ｂ，…１１２ｉ，Ｌ２＄１１３ａ，１１３ｂ，…１１３ｉ，ＣＯＭＡキャッシュ／メモリ１１４、グローバル・インターフェイス１１５，Ｌ３＄１１８，及びローカル・インターコネクト１１９を含む。この例では、各プロセッサ１１１ａ，１１１ｂ，…１１１ｉがコンパクトで任意の第１レベルのキャッシュ（Ｌ１＄）（図１に示さない）を含み得る。
【００１４】
ディレクトリに基づいたキャッシュ・コヒーレンス方法を支持するために、サブシステム１１０，１２０，…１８０は、グローバル・インターフェイス１１５，１２５，…１８５とそれぞれ結合されたディレクトリ１１６，１２６，…１８６も含む。ＣＯＭＡキャッシュ／メモリ１１４，１２４，…１８４のどれかにある“ホーム”ロケーションから発するデータは、コンピュータ・システム１００のアトラクション・メモリ（ＡＭ）中で複製することができる。例えば、ＣＯＭＡモードでは、サブシステムのキャッシュはＣＯＭＡキャッシュ／メモリ１１４，１２４，…１８４並びにＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉを含み、そして“ホーム”ロケーションがサブシステム１１０のＣＯＭＡキャッシュ／メモリ１１４にあるデータは、ＣＯＭＡキャッシュ／メモリ１２４，…１８４のうちの１個又は２個以上にて複製されてよく、かつ又複数のＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉのうちの１個又は２個以上にて複製されても良い。逆に、ＮＵＭＡモードでは、サブシステムのキャッシュはＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉを含み、そして“ホーム”ロケーションがサブシステム１１０のＣＯＭＡキャッシュ／メモリ１１４中にあるデータは、複数のＬ２＄１１３ａ…１１３ｉ，１２３ａ…１２３ｉ，及び１８３ａ…１８３ｉのうちの１個又は２個以上にて、そしてＬ３＄１１８，１２８，…１８８にて複製されてもよい。
【００１５】
図１の例示的なハイブリッドＣＯＭＡ／ＮＵＭＡコンピュータ・システム１００で実施されたようなこの発明の一実施形態では、データの“ホーム”ロケーションはサブシステム１２０のＣＯＭＡキャッシュ／メモリ１２４中にある。即ちサブシステム１２０はデータのホーム及びオーナ・サブシステムである。ＣＯＭＡキャッシュ・メモリ１１４と第２レベルのハイブリッド・キャッシュ（Ｌ２＄）１１３ａ，１１３ｂ，…１１３ｉとの少なくとも一方に空間を割当てることにより、１つ又は２つ以上のリクエスト中のサブシステムのアトラクション・メモリ（ＡＭ）空間、例えばリクエスト中のサブシステム１１０のＡＭ空間にデータのコピーもストアできる。これに関連して、本願出願人の先行出願である１９９５年１２月２２日付け出願の出願番号０８／５７７，２８３（整理番号Ｐ１００３）、発明者ハガースタン（Ｈａｇｅｒｓｔｅｎ）等、発明の名称「ハイブリッドＮＵＭＡコマ・キャッシュイング・システム及び複数のキャッシュイング・モードを選択する方法」を参照されたい。又、１９９５年１２月２２日付け出願の出願番号０８／５７５，７８７（整理番号Ｐ１００４）、発明者ウッド（Ｗｏｏｄ）等、発明の名称「ハイブリッドＮＵＭＡコマ・キャッシュイング・システム及び複数のキャッシュイング・モードを選択する方法」も参照されたい。これらの出願には、ハイブリッドＣＯＭＡ／ＮＵＭＡアーキテクチャ及びハイブリッド・キャッシュ・アーキテクチャを開発する方法が述べられている。
【００１６】
ホーム・ディレクトリ１２６は、コンピュータ・システム１００全体に亘るホーム・ページの現存するコピーのマスター記録を維持することに対して責任がある。その上、それぞれのＡＭディレクトリ例えばディレクトリ１１６及び１８６に関連した複数のメモリ・タグ（ＭＴＡＧ）は、４つの例示的な状態のうちの１つを使用してリクエスト中の各サブシステム内のローカル・コピーの状態を追跡する。無効（“Ｉ”）状態は、特定のサブシステムが対象となるデータ・ラインの（キャッシュされた）コピーを持たないことを示す。共有した（“Ｓ”）状態は、そのサブシステム及び他の幾つかのサブシステムが対象となるデータ・ラインの共有した（キャッシュド）コピーを有することを示す。所有した（オーナした）（“Ｏ”）状態は、そのサブシステム及び可能性としては他の幾つかのサブシステムが対象としたデータ・ラインの（キャッシュされた）コピーを有することを示す。Ｏコピーを持つサブシステムは、再置（置き換え）時にライトバックすることを必要とされる。変更した（“Ｍ”）状態は、サブシステムが対象とするデータ・ラインの（キャッシュされた）コピーだけを有する、即ちサブシステムがデータ・ラインの唯一のオーナであり、他のサブシステムにＳコピーが無いことを示す。
【００１７】
この実施の形態では、複数のＬ１＄とＬ２＄の間に内包が維持されるが、Ｌ２＄と第３レベルのキャッシュの間に内包を維持する必要は無い。換言すれば、Ｌ１＄にあるデータはそれぞれのＬ２＄にもあるが、Ｌ１＄又はＬ２＄にあるデータは必ずしもそれぞれのＬ３＄にある必要は無い。従って、Ｌ２＄中のデータのキャッシュ・ラインに空間が割当てられようとも、Ｌ３＄はデータのキャッシュ・ラインに割当てなくても良い。
【００１８】
以下の説明において、この発明の選択方法は、特定のデータ構造（低レベルのキャッシュ（ＬＬＣ）例えばＬ２＄１１３ａ又はＬ３＄１１８に現在ストアされている）がハイブリッドＣＯＭＡ／ＮＵＭＡ環境内のリクエスト中のサブシステム１１０の高レベルのキャッシュ（ＨＬＣ）例えばＣＯＭＡキャッシュ／メモリ１１４にストアされるべきか、ストアされるべきでないかを決定する。従って、この選択方法は、ＮＵＭＡモードで現在ストアされているデータが何時ＣＯＭＡモードでストアされるべきかを決定するのに使用されることができる。しかしながら、この選択方法は、全てのレベルのキャッシュにも様々なキャッシュ及びシステム・アーキテクチャにも適用できると理解される。
【００１９】
図３は、マルチプロセッサ・コンピュータ・システム１００に実施されたようなこの発明の一面を示すフローチャート２００である。
【００２０】
リクエスト中のサブシステム１１０のプロセッサ１１１ａがデータをリクエストする時に、データのサーチはＬ２＄１１３ａで、次にＬ３＄１１８で行われる（ステップ２１０）。もしリクエスト中のサブシステム１１０内でデータが見い出されないなら、即ちキャッシュ・ミスがサブシステム１１０で起こるなら、ホーム・サブシステム１２０にリクエストされてデータをフェッチする（ステップ２２０）。本出願人による上述した出願番号０８／５７７，２８３（整理番号Ｐ１００３）には、ホーム・サブシステムのディレクトリに最初に割込むことによってオーナ・サブシステムからデータがどのようにしてフェッチされるかが開示されている。
【００２１】
リクエスト中のサブシステム１１０は、キャッシュ・ミスが“避けられ得る”キャッシュ・ミスかどうかを決定しようとする（ステップ２３０）。もしキャッシュ・ミスが避けられ得たならデータがＬ３＄１１８に残ったことにより、キャッシュ・ミスはさけられ得る。避けられ得るキャッシュ・ミスの一例が“過剰な”キャッシュ・ミスであって、これは容量ミス又はコンフリクト・ミスが先行したキャッシュ・ミスとして定義される。避けられ得るキャッシュ・ミスの他の原因も検討される。これらキャッシュ・ミスは、古いデータを置き換える代わりに、Ｌ３＄１１８を再配置してＬ３＄１１８に新しいキャッシュ空間を“フリーアップ（ｆｒｅｅ  ｕｐ）”することにより、例えばＬ３＄をダイナミックに再サイズ化する（Ｌ３＄のサイズを大きくする）ことにより、避けられ得たキャッシュ・ミスを含む。
【００２２】
この実施形態では、ホーム・サブシステム１２０のホーム・ディレクトリ１２６は、例えばアレイｄｉｒ＿ｓｈａｒｅ＿ｂｉｔ〔ノード〕（ただしノード＝１…ｎであって、ｎはサブシステムの総数である。）中の各キャッシュ・ラインにストアされたデータの共有した（Ｓ）コピーを有するリクエスト中のサブシステムのリストを維持する。その上、ホーム・ディレクトリ１２６は、各キャッシュ・ライン中のデータの現在のオーナの識別（ｏｗｎｅｒ＿ｉｄ）を含む。現在のオーナが無い場合には、ｏｗｎｅｒ＿ｉｄは最後のオーナを識別する。ホームディレクトリ１２６は、最新のオーナがデータをメモリにライトバックしたかどうか、或はそれが未だオーナかどうかを示すライトバック・ビット（ｗｂ＿ｂｉｔ）も含む。データの最後のライタ（ｌａｓｔ＿ｗｒｉｔｅ）は、ディレクトリ１２６中のそれぞれのｏｗｎｅｒ＿ｉｄ及びｗｂ＿ｂｉｔフィールドから決定できる。従って、過剰なキャッシュ・ミスはブール式で下記のように表わされる。
【００２３】
（RTS & dir_share_bit〔ノード〕＝１）OR(RTO & last_write＝ノード）
【００２４】
ただし、ＲＴＳはリード−ツ−シェア（read-to-share ）であり、そしてＲＴＯはリード−ツ−オーン（read-to-own）である。
【００２５】
過剰なキャッシュ・ミスを検出する例示的な方法の詳しい説明は、上述した出願番号０８／５７７，２８３（整理番号Ｐ１００３）の先行出願を参照されたい。この発明の一変形例では、ディレクトリ１２６が最近にアクセスされたキャッシュ・ラインの状態情報を保持するディレクトリ・キャッシュである。（同日出願の「ディレクトリレス・プロトコル及び関連したディレクトリ・キャッシュＰ１５３１も参照されたい）。この変形例では、このディレクトリ・キャッシュにそれぞれのエントリを有する避けられ得るミスだけがリクエスト中のサブシステム１１０をしてＬ３＄１１８に空間を割当てさせることができる。
【００２６】
もしリクエスト中のサブシステム１１０が避けられ得るミスを検出するなら、データをストアするために適当なロケーションがＬ３＄１１８中に割当てられる（ステップ２５０）。アイドル・ロケーション又は無効データもしくはステール（ｓｔａｌｅ）・データを含むロケーションをまず探す（ステップ２６０）ことにより、適当なロケーションを割当てることができる。もしアイドル・ロケーションも無効ロケーションも見つからなければ、使用されたロケーションが割当てられてディスプレースされたデータ（displaced data）を置き換える必要がある。１つの使用されたロケーションは幾つかの使用されたロケーションの中からアットランダムに選べる。或は、最近に用いらた（ＬＲＵ）又は最も頻繁に（ＬＦＵ）のような選択規準を使用して沢山の使用されたロケーションの中から或るロケーションを選べる。
【００２７】
もし選択された使用済みロケーションからディスプレースされたデータを置き換える必要があれば、リクエスト中のサブシステム１１０はディスプレースされたデータをそのオーナ・サブシステムにライトバックする（ステップ２６５）。上述した出願番号０８／５７７，２８３（整理番号Ｐ１００３）の先行出願は、ディスプレースされたデータを置き換える一例を提供する。
【００２８】
逆に、もしキャッシュ・ミスが避けられ得るキャッシュ・ミスではなくてキャッシュ１１８中にアイドル・ロケーションがある（ステップ２３０及び２４０）ならば、キャッシュ１１８中のアイドル・ロケーションが割当てられ且つデータが割当てられたロケーションにストアされる（ステップ２５５及び２７０）。もしキャッシュ・ミスが避けられ得るキャッシュ・ミスでない上にキャッシュ１１８が一杯である（ステップ２３０及び２４０）なら、データはキャッシュ１１８にキャッシュされない。
【００２９】
上述した場合の各々にて、データはリクエスト中のプロセッサ１１１ａへ提供される（ステップ２８０）。データがオーナ・サブシステム１２０からフェッチされた後はいつでもデータをリクエスト中のプロセッサ１１１ａに提供できる、即ち所要のキャッシュイング・ステップの前後でデータを提供できることに注目されたい。
【００３０】
図４は、ユニプロセッサ・コンピュータ・システムにて実施されたこの発明の他の実施形態を示すフローチャート３００である。ユニプロセッサに関する実施形態についての以下の説明はプロセッサ・キャッシュ及び主メモリを有するコンピュータ・システムに基づくものであるが、選択方法は沢山のキャッシュとメモリの少なくとも一方を有するどんなユニプロセッサ・コンピュータ・システムにも適用できる。例えば、主メモリは高レベルのキャッシュで良い。
【００３１】
プロセッサがデータをリクエストする時に、キャッシュ中でデータがサーチされる（ステップ３１０）。もしデータが見つからなければ、即ちキャッシュ・ミスが検出されるなら、プロセッサは主メモリからデータをフェッチする（ステップ３２０）。
【００３２】
その後、プロセッサはキャッシュ・ミスが“避けられ得る”キャッシュ・ミスであるかどうかを決定しようとする（ステップ３３０）。ユニプロセッサ環境中の避けられ得るキャッシュ・ミスの一例は、何時、同一データがプロセッサによって以前にリクエストされて主メモリからキャッシュへフェッチされたかである。
【００３３】
もしプロセッサが避けられ得るミスを検出したなら、適当なロケーションがデータをストアするためのキャッシュ中で割当てられる（ステップ３５０）。アイドル・ロケーション又は無効データもしくはステール・データを含むロケーションをまず探す（ステップ３６０）ことにより、適当なロケーションを割当てることができる。もしアイドル・ロケーションも無効ロケーションも見つからなければ、使用されたロケーションが割当てられてディスプレースされたデータを置き換える必要がある。使用されたロケーションはアットランダムに或はＬＲＵもしくはＬＦＵのようなアルゴリズムを使用して選べる。
【００３４】
もし選択された使用済みロケーションからディスプレースされたデータを置き換える必要があれば、プロセッサはデータを主メモリにライトバックする（ステップ３６５）。キャッシュの強制的な“ライトスルー”がしいられるユニプロセッサ及びマルチプロセッサ・システムの両方において、キャッシュ及びメモリの内容が常にコヒーレントであるので、ディスプレースされたデータは簡単に捨てられ得る。“コピーバック”キャッシュも、もしディスプレースされたデータが変更されなかったならば、このディスプレースされたデータを簡単に捨てられる。
【００３５】
逆に、もしキャッシュ・ミスが避けられ得るキャッシュ・ミスではなく且つキャッシュが一杯でもない（ステップ３３０及び３４０）ならば、プロセッサはキャッシュ中でアイドル・ロケーションを割当て且つデータは割当てられたロケーションにストアされる（ステップ３５５及び３７０）。もしキャッシュ・ミスが避けられ得るキャッシュ・ミスでなく且つキャッシュが一杯である（ステップ３３０及び３４０）なら、データはキャッシュされない。
【００３６】
上述した場合の各々にて、データはリクエスト中のプロセッサへ提供される（ステップ３８０）。どのキャッシュイング・ステップ３７０の前後でもデータをリクエスト中のプロセッサへ提供できることに注目されたい。
【００３７】
上述したように、この発明によれば、図５〜図８に示したように、低レベルのキャッシュ（ＬＬＣ）内のキャッシュ・ライン・サイズのサブユニット例えばＬ２＄１１３ａとＬ３＄１１８の少なくとも一方にて割当てられる代わりに、高レベルのキャッシュ（ＨＬＣ）内のページ・サイズ化されたユニット例えばＣＯＭＡキャッシュ１１４にてもし空間が割当てられるならば、データがもっと効率良くストアされ得るかどうかについての決定がされる。換言すれば、選択方法は、データのどのページがＮＵＭＡモードではなくてＣＯＭＡモードでのアクセスから利益を得ることを決定する。
【００３８】
この実施の形態では、ＣＯＭＡキャッシュ１１４のサイズは、プログラムの実行中絶えず変化でき且つ最大ではノードのローカル・メモリ空間に等しい。ＣＯＭＡキャッシュのサイズが容易に増加され得るので且つＣＯＭＡキャッシュ１１４でのデータのアクセスをサポートするためのハードウェア・オーバヘッドがＬ３＄１１８でのデータのアクセスをサポートするためのハードウェア・オーバヘッドよりもはるかに低くされ得るので、ＮＵＭＡモードからＣＯＭＡモードへページを変換することは、Ｌ３＄１１８でのデータ・アクセス・デマンドを下げ得る。
【００３９】
図５を参照すれば、データのブロックの諸部分例えばデータのページからのキャッシュ・ラインは、連続してストアされ且つ低レベルのキャッシュ中で変動するキャッシュド部分の数と置き換えられる（ステップ４１０）。この実施の形態では、ＬＬＣ中の個々のキャッシュ・ラインをキャッシュするかどうかの決定は、上述して図３及び図４に示した例示的な態様で行われる。しかしながら、キャッシュ・ラインは、他の規準に基づいてＬＬＣ中でキャッシュされても良いし、或はそれぞれのキャッシュ・ラインがサブシステムによってリクエストされる毎に簡単にキャッシュされても良い。
【００４０】
最終的に、サブシステム１１０は、ＬＬＣ中での空間の割当てを再検討するためのトリガを検出する（ステップ４２０）。ＬＬＣ空間の割当てを再検討することは多数のやり方でトリガされることに注目されたい。例えば、高レベルのキャッシュ（ＨＬＣ）であるＣＯＭＡキャッシュ１１４の利用が閾値よりも下がる時、ＬＬＣがあまりにも多くのデータ置き換えで沢山のプレッシャを受ける時、又はコンピュータ・システム１００のタイマがタイムアウトする時にはいつでも、割当ての再検討はトリガされ得る。
【００４１】
メモリ再検討のトリガを検出する時には、サブシステム１１０がＬＬＣの内容を再検討して（ステップ４３０）ＬＬＣ中にある相当な数のキャッシュ・ラインを有するデータのページを識別する（ステップ４４０）。もしデータの新しいブロックが再検討規準を満たすなら、例えばもしページのキャッシュ・ラインの数が閾値を超えるなら、空間（ページ）のブロックはデータの新しいブロックに対してＨＬＣ中で割当てられる（ステップ４５０）。この閾値はソフトウェアにより予め決定ないし選択できる。
【００４２】
ＨＬＣが一杯なら、データの古いブロックが置き換えのために選択される（ステップ４６０）。ブロック選択方法のいくつかの変形例が可能である。例えば、データの選択された古いブロックはデータのＬＲＵブロックで良い。他の周知のメモリ置換規準はＬＦＵを含む。
【００４３】
置き換えのためにデータの古いブロックを選択したので、ＨＬＣ中で実施された置き換えプロトコルに依存してデータの古いブロックのライトバック動作が必要とされ得る。この例では、ＨＬＣ例えばＣＯＭＡキャッシュ１１４がコピーバック・キャッシュであるので、データの置き換えられたブロックがそれぞれのホーム・ロケーションにライトバックされる（ステップ４７０）。逆に、もしＨＬＣがライトスルー・キャッシュなら、データの置き換えられたブロックは単に捨てられ得る。どちらの場合も、データの新しいブロックの諸部分はＨＬＣ中の空間の新しく割当てられたブロックにキャッシュされ得る（ステップ４８０）。コピーバック・キャッシュからのデータのブロック（ページ）をフラッシュするための例示的な方法は、本願と同日付で出願されたハガースタン（Ｈａｇｅｒｓｔｅｎ）等の出願「コンピュータ・システム中でのキャッシュ・メモリのフラッシュイング」（整理番号Ｐ１４１６）に述べられている。
【００４４】
図６に示されたようなこの発明の他の実施形態を示すフローチャート５００では、データのブロックからの部分に関連したキャッシュ・ミスがあった後に、メモリ割当ての再検討がトリガされ得る。従って、キャッシュ・ミスが有る時、即ちデータのブロックに関連した部分がＬＬＣでもＨＬＣでも見い出されない（ステップ５１０）時に、その部分はホーム・ロケーションからフェッチされる（ステップ５２０）。データの同一ブロックと関連した他の部分がＨＬＣに現在ストアされているなら、即ちデータの関連したブロックのための空間がＨＬＣ中で既に割当てられていたなら、その部分はＨＬＣ中の空間の割当てられた同一ブロック内にストアされる（ステップ５７０）。
【００４５】
逆に、もし関連したブロックのための空間がＨＬＣ中でまだ割当てられておらず（ステップ５３０）且つサブシステム１１０によりＨＬＣとＬＬＣの間でのキャッシュ割当ての再検討が時機を得たものであると決定される（ステップ５４０）と、サブシステム１１０はＬＬＣ中でキャッシュされた関連部分の総数が閾値を超えるかどうかを決定する（ステップ５５０）。この閾値は所定値又は絶えず選択できる値とすることができる。閾値を超えると、関連ブロックのための空間はＨＬＣ中で割当てられる（ステップ５６０）。
【００４６】
図７は図６のＨＬＣ割当てステップ５６０をもっと詳しく示す。ＨＬＣがコピーバック・キャッシュかライトスルー・キャッシュかに依存して、もしＨＬＣが一杯である（ステップ５６１）なら、ディスプレースされたデータのホーム・ロケーションへのライトバックが必要かもしれない。この例では、ＨＬＣ即ちＣＯＭＡキャッシュ１１４がコピーバック・キャッシュなので、ＨＬＣ中の空間のフリードアップ（ｆｒｅｅｄ−ｕｐ）・ブロックが書き込まれる前に置き換えられたブロックのライトバックが開始される（ステップ５６２及び５６３）。逆に、ＨＬＣ中にアイドル空間があれば、アイドル空間のブロックはデータの新しいブロックに対して割当てられる（ステップ５６１及び５６４）。
【００４７】
図６へ戻れば、データの新しいブロックに対してＨＬＣ中に空間を割当てたので、新しいブロックに関連した部分がＨＬＣにストアされ得る（ステップ５７０）。この実施形態では、その部分はＬＬＣに任意にストアされる（ステップ５８０）。
【００４８】
図８を参照すれば、この発明は、本願と同日付で出願されたハガースタン等の出願「コンピュータ・システム中のキャッシュ・メモリ空間の有効な割当て方法」（整理番号Ｐ１５７６）の選択的キャッシュイング方法で実施され得る。従って、全てのキャッシュ・ミスが生じる毎にＬＬＣ中で簡単なキャッシュイングをする代わりに、“避けられる”ミスがある場合だけ部分がキャッシュされる（ステップ５８１）。避けられ得るミスの一例は容量ミス又はコンフリクト・ミスのような“過剰な”ミスである。
【００４９】
もしキャッシュ・ミスが避けられ得るミスなら、空間はその部分のためにＬＬＣ中で割当てられる（ステップ５８３）。ＬＬＣがコピーバック・キャッシュかライトスルー・キャッシュかにより、置き換えられた部分の、そのホーム・ロケーションへのライトバックが必要かもしれない。この例では、ＬＬＣ例えばＬ２＄１１３ａがコピーバック・キャッシュであるので、新しい部分がＬＬＣにストアされ得る前に置き換えられた部分のライトバックが開始される（ステップ５８４，５８６及び５８７）。逆に、ＬＬＣ中にアイドル空間が在れば、空間は割当てられて新しい部分はＬＬＣにストアされる（ステップ５８２，５８５及び５８７）。
【００５０】
図６に戻れば、上述した場合の各々にて、データの部分はリクエスト中のプロセッサに提供される（ステップ５９０）。その部分がホーム・ロケーションからフェッチされた後ではいつでも、即ちその部分がＨＬＣとＬＬＣの少なくとも一方にてキャッシュされる前又は後で、データをリクエスト中のプロセッサへ提供できることに注目されたい。
【００５１】
上述したメモリ選択機構を最大限に種々活用することが可能である。例えば、低レベルのキャッシュ中でキャッシュされた関連部分の数が閾値を超える時にはいつでも高レベルのキャッシュ中のデータの新しいブロックと関連付けられた諸部分を自動的にキャッシュする代わりに、ＬＬＣ中のキャッシュされた部分の数がＨＬＣ中の現在キャッシュされた古いブロックと関連付けられたキャッシュ・ヒットの数を超え且つこれが置き換えのために選択された時だけ新しいブロックはＨＬＣにキャッシュされる。この発明の精神から逸脱しない限り他の変形例等も可能であるので、この発明の範囲は特許請求の範囲で決定されるべきである。
【図面の簡単な説明】
【図１】  この発明を実施するための適当なハードウェア環境を提供するハイブリッド・キャッシュ・オンリメモリ・アーキテクチャ／非一様メモリ・アーキテクチャ（ＣＯＭＡ／ＮＵＭＡ）を有するネットワーク化されたコンピュータ・システムを示すブロック図である。
【図２】  図１のネットワーク化されたコンピュータ・システムのための例示的なメモリ・マップである。
【図３】  マルチプロセッサ・コンピュータ・システム中でキャッシュ空間を割当てるためのこの発明の一実施形態の一部を示すフローチャートである。
【図４】  ユニプロセッサ・コンピュータ・システム中でキャッシュ空間を割当てるためのこの発明の他の実施形態の一部を示すフローチャートである。
【図５】  図３の割当て方法の実施形態を示すフローチャートである。
【図６】  この発明に係る他の実施形態を示すフローチャートである。
【図７】  図６の一部を示すフローチャートである。
【図８】  図６の他の一部を示すフローチャートである。
【符号の説明】
１００…コンピュータ・システム、１１０，１２０，１８０…サブシステム、１１１ａ〜１８１ｉ…プロセッサ、１１３ａ〜１８３ｉ…第２レベルのハイブリッド・キャッシュ、１１４，１２４，１８４…ＣＯＭＡキャッシュ／メモリ、１１８，１２８，１８８…Ｌ３＄。
【図１】
0004068185.tif 000002
【図２】
0004068185.tif 000003
【図３】
0004068185.tif 000004
【図４】
0004068185.tif 000005
【図５】
0004068185.tif 000006
【図６】
0004068185.tif 000007
【図７】
0004068185.tif 000008
【図８】
0004068185.tif 000009