キャッシュ・コヒ―レンシの維持方法及びペ―ジ割当解除方法
【課題】 各ノードが、それ自体、共用メモリ・マルチプロセッサである複数のノードを備える共用メモリ・マルチプロセッサ装置において、キャッシュ・コヒーレンシを維持する方法を提供する。
【解決手段】 本発明によれば、共用メモリ・マルチプロセッサ装置内の最上位レベルのキャッシュメモリのキャッシュが、共用メモリ・プロセッサ装置の最上位キャッシュ・レベルをミスするキャッシュラインに対して、リードまたはライト・リクエストを発すると、キャッシュ・ラインのオーナが、キャッシュ・ラインを最上位レベルのキャッシュ・メモリを相互接続するバス上に出力する。
【解決手段】 本発明によれば、共用メモリ・マルチプロセッサ装置内の最上位レベルのキャッシュメモリのキャッシュが、共用メモリ・プロセッサ装置の最上位キャッシュ・レベルをミスするキャッシュラインに対して、リードまたはライト・リクエストを発すると、キャッシュ・ラインのオーナが、キャッシュ・ラインを最上位レベルのキャッシュ・メモリを相互接続するバス上に出力する。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、マルチレベル共用メモリ・マルチプロセッサ・システムにおけるキャッシュ・コヒーレンシを維持する方法および装置に関する。
【０００２】
【従来の技術】共用メモリ・マルチプロセッサは、プログラミングが容易で、性能が改善されているために非常に一般的である。事実、１本のバスを介してメモリおよび関連するディスクと相互接続された多数のプロセッサ（１６または３２個に及ぶ）からなる市販の多くの共用メモリ・マルチプロセッサが存在する。プロセッサは、典型的には、それらと関係する専用キャッシュを有し、共用メモリ・マルチプロセッサは、バスベースのコヒーレンス・プロトコルを使用してキャッシュ・コヒーレントとなっている。このアーキテクチャは、多段相互接続ネットワーク（ＭＩＮ）［文献１参照］により相互接続された複数のノード（各ノードは、それ自体、１６〜３２ノード共用メモリ・マルチプロセッサである）からなるスケーラブル共用メモリ・プロセッサにおいて、急速に単一の要素となりつつある。しかし、このタイプの共用メモリ・マルチプロセッサ・アーキテクチャは、１つのノード上に存在しないデータに対しては、潜在的に極めて大きいアクセス待ち時間を免れることができない。この問題に対する１つの解決策は、メモリを高レベル・キャッシュとして各ノード上で使用することによって、キャッシュ・オンリ・メモリ・アーキテクチャ［文献２参照］を実現することである。このタイプのアーキテクチャによれば、要求に応じて、データをそれらノードへ自動的に移動させ複写することが容易になる。
【０００３】ＣＯＭＡアーキテクチャの主要な問題点は、高価で複雑なハードウェアであるという点である。しかし、この問題点を最小限にするために、従来より簡易ＣＯＭＡアーキテクチャ〔文献３参照〕が提案されてきた。簡易ＣＯＭＡアーキテクチャでは、ページング・ソフトウェアが、ページング・レベルでのキャッシュ空間の割り当てと割り当て解除とを管理し、キャッシュ・コヒーレンスを維持するためには余り複雑でないハードウェアが使用されている。しかし、ノード全体にわたってキャッシュ・コヒーレンスを維持する方法は、ディレクトリ・ベースで行われるため、ノード全体のデータ・アクセスと制御とに伴うペナルティは（このようなアクセスの頻度は、可能性として少いとはいえ）相当なものになる可能性がある。
【０００４】
【発明が解決しようとする課題】本発明の目的は、スケーラブル共用メモリ・マルチプロセッサ装置においてノード・ホップをもたらすようなキャッシュ・ミスに伴う待ち時間を最小限にすることにある。
【０００５】本発明の他の目的は、コヒーレントなディレクトリの必要のないスケーラブル共用メモリ・マルチプロセッサを構築する費用効果的な方法を提供することにある。
【０００６】
【課題を解決するための手段】従って、本発明は、各ノードが共用メモリ・マルチプロセッサである複数のノードを有する共用メモリ・マルチプロセッサ装置において、マルチレベルのキャッシュ全体にわたってキャッシュ・コヒーレンシを維持する方法を提供する。本発明によれば、共用メモリ・マルチプロセッサ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、ステータス・オーナ情報は、リード・オンリ・ラインのノードのいずれが最初にリード・オンリ・ラインを読み取ったかを指示し、リード／ライト・ラインのノードのいずれが、最初にリード／ライト・ラインを読み取り、最後に変更したかを指示し、その際、各キャシュラインの指示されたノードがキャッシュ・ラインを所有するノードである。共用メモリ・マルチプロセッサ装置内の最上位レベルのキャッシュ・メモリのノードの１つのキャッシュが、共用メモリ・プロセッサ装置の最上位レベル・キャッシュでミスするラインに、リードまたはライト・アクセス命令を発すると、キャッシュ・ラインのオーナは、最上位レベルのキャッシュ・メモリを相互接続するバス上にキャッシュ・ラインを出力する。この場合、命令を発するキャッシュは、ラインのオーナによりバス上に出力されたキャッシュ・ラインを用いて、そのキャッシュ・ラインをそれぞれ読み取り、または変更する。
【０００７】
【発明の実施の形態】図１は、２ノード共用メモリ・マルチプロセッサ・システムであって、各ノードがそれ自体、４ノード共用メモリ・マルチプロセッサＨ１であるものの論理図表である。このノードには、キャッシュ１，２が示され、低レベルＬ２キャッシュ１は、１個のプロセッサと関係するものとする。この簡易ＣＯＭＡアーキテクチャは、主メモリを含んではいないが、ディスク５、およびそれと関係するディスク・コントローラ６が、ノードＨ１（ディスクのホーム・ノードとして示す）上に物理的に常駐するものとする。提案された２つのアーキテクチャ（バス・オンリ（図１）とバス／ＭＩＮ（図２））のプロトコル・アクティビティの基本的な相違は、バス・オンリ（図１）が、制御とデータ転送の双方にノード間バス４を使用する一方、バス／ＭＩＮアーキテクチャ（図２）が、制御にはノード間バス４を、データ転送にはノード間ＭＩＮ７を使用する点である。これら２つの提案アーキテクチャに必要とされるコヒーレンス・アクティビティの大部分は、同一である。それ故、我々は、説明をバス・オンリ・アーキテクチャ案（図１）に集中することにする。しかし、バス／ＭＩＮアーキテクチャのプロトコル・アクティビティ（図２）は、それがバス・オンリ・プロトコル・アクティビティと異なる場合に特に説明することにする。
【０００８】キャッシュ・コヒーレンスを維持するために、Ｌ２（１）とＬ３（２）のキャッシュは、共に、それぞれのキャッシュ・ライン・エントリに関する状態情報を含んでいる。コヒーレンス・プロトコルは、ジェネリックＭ，Ｅ，Ｓ，Ｉ（変更、専用、共用、無効）プロトコルであるとする。Ｌ２キャッシュ１の場合、このジェネリック・プロトコルは、典型的な階層バス・プロトコル［文献４参照］と共に使用することができる。我々の提案においては、主メモリの概念は存在しないので、共用オーナ状態と称されるもう１つの状態を使用して、リード・オンリ・ラインのオーナを指定する。リード・ミスでキャッシュ・ラインをキャッシュへ転送するリクエストが存在する場合、ラインのオーナがデータを供給する。ラインが変更、専用、または共用オーナの状態にある場合には、そのラインを含むキャッシュが、そのオーナである。
【０００９】我々の提案の本質は、Ｌ３コヒーレンス・プロトコルを階層バス簡易ＣＯＭＡアーキテクチャに対して実施する時に必要とされる特別なアクションである。例えば、キャッシュ置換ストラテジはページ置換ストラテジとなり、本発明はこのページ置換ストラテジがＬ３キャッシュ・コヒーレンスとどのように一体化されているかを開示する。
【００１０】Ｌ３キャッシュ・ラインは、以下に概説し図３に示されるような５つの状態の１つをとることができる。
・Ｅ−専用（８） ラインは、Ｌ３キャッシュ（２）および／またはその関連する低レベル・キャッシュに常駐するのみで、変更されていない。
・ＳＯ−共用オーナ（９Ｂ） ラインは、幾つかのＬ３キャッシュ（２）に常駐し、変更されていない。このキャッシュ・ラインは、リモートＬ３キャッシュ（２）がラインに対してミスを有する場合には常に、このＬ３バス（４）上に出力される。
・Ｓ−共用（９Ａ） ラインは、幾つかのＬ３キャッシュ（２）に常駐し、変更されていない。
・Ｍ−変更（１０） ラインは、Ｌ３キャッシュ（２）および／またはその関連する低レベル・キャッシュに常駐するのみで、変更されている。
・Ｉ−無効（１１） キャッシュのラインに対して空間が割り当てられたが、データが無効である、すなわちラインに対してキャッシュに空間が割り当てられていない。
【００１１】専用状態と変更状態を１つの状態に組み合わせることができる。
【００１２】Ｌ３キャッシュ（２）のコヒーレンス・アクションを引き起こす幾つかの事象がある。それらは、Ｌ２バス・リード（ＡＲ）またはバス・ライト（ＡＷ）、Ｌ３バス・リード（ＢＲ）またはバス・ライト（ＢＷ）、Ｌ２またはＬ３無効化（それぞれＩＮＶ−ＡおよびＩＮＶ−Ｂ）、Ｌ３キャッシュ・フラッシュ（ＦＬ−Ｂ）を含む。我々は、簡易ＣＯＭＡアーキテクチャを想定しているから、Ｌ３キャッシュ・ラインに対して空間が割り当てられていなければ、空間は、ラインを含むページに対しても割り当てられていない。そのため、ページ・ミスによって、ページ置換ストラテジの開始と、Ｌ２およびＬ３のキャッシュ・ミスの処理とが必要になる。以下のページ置換の説明を参照されたい。以下に説明するのは、Ｌ３キャッシュ・ラインが以下に説明する５つの状態の１つにある時に、これら事象の結果としてとられるアクションである。図３を参照されたい。
【００１３】・無効（Ｉ）１１ ラインが無効状態にあり、Ｌ３バス・リード（ＢＲ）またはバス・ライト（ＢＷ）が行われると、ラインはＩ状態に留まる。図３の１２を参照されたい。、Ｌ２バス・リード（ＡＲ）が行われると、Ｌ３キャッシュ２は、バス・リード信号をＬ３バス４上に出力し、空間が既にキャッシュに割り当てられていれば、データをリクエストする。空間が割り当てられていなければ、ページ置換ストラテジが実行され（リクエストされたページを割り当てる）、データはオーナからＬ３キャッシュへ転送される。また、Ｌ２バス・リード（ＡＲ）の結果、他のキャッシュがラインのコピーを有しなければ、Ｅ（８）へ変化し（ライン１３上のＡＲ／ＢＲを参照）、少なくとも１つのリモートＬ３キャッシュ（オーナ）にコピーが存在すれば、Ｓ（９Ａ）へと変化する。ライン１４上のＡＲ／ＢＲを参照されたい。Ｌ２キャッシュの書き込みが行われると、Ｌ３キャッシュは、リード・ウィズ・インテント・トゥ・モディファイ（ｒｅａｄ−ｗｉｔｈ−ｉｎｔｅｎｔ−ｔｏ−ｍｏｄｉｆｙ）信号を、Ｌ３バス４上に出力する。その結果、データはオーナ・キャッシュであるリモートＬ３からリクエスト中のＬ３キャッシュへ転送され、Ｌ３バス４上には無効化信号が現れる。無効化信号の結果、リモート・ノードがラインのコピーを有していれば、そのラインは無効化される。最後に、キャッシュ・ラインの状態は、Ｌ２キャッシュ（１）ライト（ＡＷ）の結果、Ｍ（１０）に変化し、Ｌ３キャッシュが、ラインの専用オーナとなる。ＡＷライン１５を参照されたい。
【００１４】リード・ウィズ・インテント・トゥ・モディファイ信号は、リモート・キャッシュに対して、或るキャッシュが、まさにデータを変更しようとしていることを知らせるために使用される典型的なタイプの信号である。それはまた、これらキャッシュに対して、データの有効なコピーを有しないことを知らせることによって、それがデータの有効なコピーを得た後（この場合にはリモートＬ３キャッシュから）、そのコピーを変更できるようにするものである。
【００１５】・専用（Ｅ）（８） Ｌ２バス・リード（ＡＲ）がこの状態にある時に行われれば、Ｌ３キャッシュ・ラインは、この状態に留まる。ライン１６を参照されたい。Ｌ３バス・リード（ＢＲ）がこの状態にある時に行われれば、Ｌ３キャッシュ・ラインの状態は、ＳＯに変化し（ライン２１を参照）、Ｌ３キャッシュは、ラインをリクエスト中のＬ３キャッシュへ転送する。Ｌ２バスの書き込みが行われれば、Ｌ３ラインの状態は、Ｍ（１０）に変化する。ライン１７を参照されたい。
【００１６】Ｌ３のリード・ウィズ・インテント・トゥ・モディファイ・バス信号が発生すると、Ｌ３キャッシュは、無効化信号をＬ２バス上に出力し、Ｌ２キャッシュ（１）のキャッシュ・ラインを無効化する。また、Ｌ３キャッシュは、ラインをＬ３バス（４）上に出力し、リクエスト先に送る。ラインの状態は、Ｉ（１１）へ変化する。ライン１８上のＢＷ、ＩＮＶ−Ａを参照されたい。
【００１７】・共用オーナ（ＳＯ）（９Ｂ）または共用（Ｓ）（９Ａ） Ｌ２またはＬ３バス・リードがこれらの状態にある間に行われると、Ｌ３キャッシュ・ラインは、それぞれの状態に留まる。ライン２２，２３上のＡＲ，ＢＲを参照されたい。Ｌ３キャッシュ・ラインの状態がＳＯであれば、Ｌ３バス・リードの結果、Ｌ３キャッシュは、Ｌ３バス上のＬ３キャッシュ・ライン・データを、Ｌ３リクエスト先に転送する。Ｌ２リード・ウィズ・インテント・トウ・モディファイ・バス信号が発生すると、Ｌ３キャッシュ２は、リモートＬ３コピーが無効化されるように、無効化信号をＬ３バス上に出力する。キャッシュ・ラインの状態は、その後、Ｍ（１０）に変化する。ライン２４，２８を参照されたい。
【００１８】Ｌ３リード・ウィズ・インテント・トウ・モディファイ・バス信号が発生すると、Ｌ３キャッシュ２は、無効化信号をラインのＬ２キャッシュ・バス上に出力する。キャッシュ・ラインがＳＯ状態にあれば、Ｌ３キャッシュ（２）は、Ｌ３バスを介してデータをリクエスト先に転送し、その後、ラインの状態はＩ（１１）へ変化する。ライン２６，２７を参照されたい。
【００１９】共用オーナは、同時に幾つかのキャッシュに存在する（従って、共用される）１本のラインのオーナを指定するために使用される。これは、リード・オンリ・ラインと、キャッシュ内に常駐する間のある時点で変更され（従って、専用的に所有される）、他の時間に共用されるラインとを含む。リード／ライト・ラインがいずれかのキャッシュにある場合、それはそのキャッシュ内にのみ存在する（１ラインのリード／ライト・コピーを有する１個のキャッシュのみが存在することができる）。それ故、デフォルトにより、そのキャッシュはラインの専用オーナである。さて、続くノードが、リモート・ノードのリード／ライト状態にあるラインを読み取りたい場合、そのライン（専用オーナ）の専用コピーを有するキャッシュは、データをリクエスト中のキャッシュへ供給する。従って、両キャッシュのキャッシュ・ラインの状態が共用される。これはラインが、現在、２ノードのキャッシュに存在し、それが共用されるからである。それは以前に変更されたものであるが、一旦、ラインの専用変更コピーを有するキャッシュが、この変更ラインを、リード命令を発したリクエスト中のキャッシュへ転送すると、両キャッシュのラインの状態は共用されることになる。この時点で、ラインの同じコピー（共用コピー）を有する２個のキャッシュが存在する。この状態で、我々は、ラインの専用リード／ライト・コピーを本来有したキャッシュ（従って、専用オーナであった）が、今、ラインの共用オーナとなることを主張しているのである。
【００２０】・変更（Ｍ）（１０） Ｌ２バス・リード（ＡＯ）またはライト（ＡＷ）が発生すると、Ｌ２キャッシュ・ラインは、ラインのＬ２キャッシュ・オーナからリクエスト中のＬ２キャッシュ１へ転送される。Ｌ２キャッシュ・オーナが存在しない場合には、Ｌ３キャッシュ２が、データを供給する。ラインの状態は不変である。ライン１９を参照されたい。Ｌ３バス・リード信号が発生すると、Ｌ２バス・リードが発生し、キャッシュ・フラッシュによって、変更データは、Ｌ２キャッシュ（１）からＬ３キャッシュ（２）へ転送される。次に、ラインは、Ｌ３バス（４）上へフラッシュし、リクエスト中のＬ３キャッシュ（２）へ戻る。Ｌ３キャッシュ・ラインの状態はＳＯ（９Ｂ）に変化する。ライン２０を参照されたい。Ｌ３リード・ウィズ・インテント・トウ・モディファイ・バス信号が発生すると、Ｌ３キャッシュ（２）は、無効化信号をＬ２バス（３）上に出力する。その結果、Ｌ２キャッシュ（１）からＬ３キャッシュ（２）への変更データのキャッシュ・フラッシュが発生する。一旦フラッシュがＬ３キャッシュ（２）へと転送されると、Ｌ３バス（４）上へフラッシュされ、リクエスト中のＬ３キャッシュへ転送される。Ｌ３キャッシュ・ラインの状態は、Ｉ（１１）へ変更される。ライン２０を参照されたい。
【００２１】ページ置換ストラテジは、Ｌ３キャッシュの多数のキャッシュ・ラインからなるページの割り当て解除を含んでいる。このストラテジは、また、Ｌ２（従って、Ｌ３）キャッシュにおいてリクエストされたキャッシュ・ラインを含むページの割り当てを含んでいる。図３のライン１３〜１５上のＤＡを参照されたい。
【００２２】ページ割り当ての最初の段階では、ページの選択を割り当て解除することが必要である（例えば、最近一番使用されていない、すなわちＬＲＵページ）。次に、ページを構成する各ライン毎に、無効化信号をＬ２バス上に出力する。この無効化信号の結果、Ｌ２キャッシュ１の変更ラインは、いずれも、Ｌ３キャッシュ２へフラッシュされる。また、Ｌ２キャッシュ１内に存在するページを構成するキャッシュ・ラインは、全て、無効化される。次に、割り当て解除されるページ内の変更された専用ラインは、ページを割り当てられたリモートＬ３キャッシュへ書き込む必要がある。ページを割り当てられたリモートＬ３キャッシュが存在しない場合には、変更ラインのみがホーム・ディスクヘ書き戻される。リモートＬ３キャッシュがページを割り当てられたかどうかを判別するために、ページの最初のラインのグローバル・アドレスがＬ３バス４上に出力される。（グローバル・アドレスの判別については、以下の説明を参照されたい。）このアドレスは、割り当て照会すなわちＡＩバス信号を伴う。Ｌ３キャッシュ（２）がページを割り当てられていれば、バス上に割り当てフラグを立てる。バス／ＭＩＮアーキテクチャ（図２）の場合には、また、ノード識別子がバス上に出力される。リモートＬ３キャッシュがページを割り当てられていれば、割り当て解除されるキャッシュ・ラインの変更された専用コピーは、全て、Ｌ３バス４（または図２のバス／ＭＩＮアーキテクチャの場合、ＭＩＮ７）上に転送され、ページが割り当てられたＬ３キャッシュ２は、変更された専用ラインの各々のコピーを取得する。幾つかのＬ３キャッシュ２がページを割り当てられていれば、ラインの変更コピーを受け取るために、いずれか１つのＬ３キャッシュがランダムに選ばれるか、あるいはリモートＬ３キャッシュの全てが、専用ラインを受け取ることができる。１つのリモートＬ３しかページを割り当てられていなければ、転送されたラインの状態は、それぞれ変更状態と専用状態において割り当て解除されたページにあったラインの場合、Ｍ（１０）とＥ（８）である。
【００２３】幾つかのＬ３キャッシュがページを割り当てられると、変更ラインの状態は、１つのＬ３キャッシュ（２）がこれらラインのコピーを取得する限り、Ｍ（１０）に留まる。その状態は、次の場合に、Ｓ（９Ａ）へと変化する。すなわち、Ｌ３キャッシュ（２）の１つが状態ＳＯでラインのコピーを取得する場合を除いて、他の全てのＬ３キャッシュ（２）が変更ラインのコピーを受け取る場合である。しかし、ページが割り当てられた全てのＬ３キャッシュ（２）は、専用ラインのコピーを取得する。その結果、これらラインの状態は、Ｌ３キャッシュにおいてＳとなる。また、変更ラインを受け取るキャッシュは、専用ラインの共用オーナＳＯ（９Ｂ）のコピーを取得する（変更ラインが存在しなければ、Ｓ０状態の専用ラインを取得するために、１キャッシュが選択される）。
【００２４】ページを割り当てられたリモートＬ３キャッシュが存在しなければ、割り当て解除されるページの変更ラインのみが、ホーム・ディスクへ書き戻されるか、あるいはホーム・ノードのリモートＬ３キャッシュに出力される。割り当て解除されたページを含むＬ３キャッシュが、ホームディスクと同じノード上に配置されていれば、変更ラインは、ディスク５ヘ書き戻される。さもなければ、変更ラインを含むページについては、ホーム・ディスクを含むノードのリモートＬ３キャッシュ２に空間が割り当てられる。変更データは、このリモートＬ３キャッシュ２へ転送される。変更ページは、リモート（ホーム）Ｌ３キャッシュ２内に、最優先の置換順位をもってマークされる。ページ置換ポリシーの実現のため、このリモートＬ３キャッシュにおいて割り当て解除するために、ページが一旦選択されると、変更データが、ノードＨ１上のディスク５ヘ書き戻される。我々はこの方法を「変更ライン・ポリシー」と表現する。
【００２５】ページ割り当てが完了すると、新しいページがＬ３キャッシュに割り当てられ、リクエストされたライン（および／またはページ内の他のライン）のキャッシュ内へ転送する処理が開始する。バス・リードまたはバス・ライト信号が、リクエストされたラインのＬ３バス４上に出力される。Ｌ３キャッシュ（２）がキャッシュラインのコピーを有する場合には、それはバス（４）（シングル・バス・アーキテクチャ、図１）またはＭＩＮ（７）（バス／ＭＩＮアーキテクチャ、図２）を介して、リクエスト中のＬ３キャッシュへ転送される。他のライン（ページの残りのラインに対して）のライン転送は必要ない。それ故、これら残りのラインに対して空間が割り当てられているが、それらはキャッシュには常駐しない。これらキャッシュ・ラインの状態は、従って、無効である（Ｉ）（１１）。
【００２６】キャッシュ・ラインのコピーを有するＬ３キャッシュが存在しない（従って、関連するページが割り当てられたＬ３キャッシュが存在しない）場合には、ページは、ホーム・ディスクから読み込まれる。ホーム・ディスクが、リクエスト中のＬ３キャッシュと同じノード上に存在するならば、ディスク５からＬ３キャッシュへのページ転送は、スムーズに行われる。ホーム・ディスクが別のノード上にある場合には、ページは、ディスク・ホーム・ノードのＬ３キャッシュに割り当てられなければならず（その結果、そのキャッシュにページ割り当て解除が生ずる可能性がある）、ホーム・ディスクからディスク・ホームノードのＬ３キャッシュへ転送される。リクエストされたラインは、そのＬ３キャッシュからリクエスト中のＬ３キャッシュへと転送される（シングル・バス・アーキテクチャ、図１）。バス／ＭＩＮアーキテクチャ（図２）の場合、ホーム・ディスク・ノードのＬ３キャッシュにページを割り当てる必要はない。ページは、ディスクからバッファへ転送された後、バッファからＭＩＮを介してリモートＬ３キャッシュへ転送することができる。
【００２７】簡易ＣＯＭＡアーキテクチャでは、各個別ＳＭＰ構成ブロックＨ１（すなわち、図１に鎖線のブロックで識別されるＳＭＰ）は、それ自身のアドレス空間を有する。しかし、全体の機構は、ＳＭＰ構成ブロックＨ１どうしの間の通信を容易にするために、グローバル・アドレス空間を有する必要がある。しかし、ＳＭＰ構成ブロックＨ１の仮想アドレス空間は、少なくともブロックのディスク容量より大きなオーダーの大きさであることが想定されている。その結果、各ノードの仮想アドレス空間は、共用メモリ・マルチプロセッサ・システムのグローバル・アドレス空間として使用することもできる。このグローバルアドレス空間は、Ｎ個のサブアドレス空間に分割されるものとする。但し、Ｎはシステム内のノードの総数である。従って、或るページについて、そのページの仮想アドレスは、各ノード上の同じグローバル・アドレスをマップする。
【００２８】まとめとして、本発明の構成に関して以下の事項を開示する。
（１）各ノードが共用メモリ・マルチプロセッサである複数のノードと、キャッシュメモリの階層とを備える共用メモリ装置において、リードまたはライト・アクセス・コマンドに応答して前記共用メモリ装置におけるキャッシュ・コヒーレンシを維持する方法であって、ａ．前記共用メモリ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、前記ステータス・オーナ情報は、リード・オンリ・ラインのノードのいずれが、最初に前記リード・オンリ・ラインを読み取ったかを指示し、リード／ライト・ラインのノードのいずれが、前記リード／ライト・ラインを最初に読み取り、または、前記リード／ライト・ラインを最後に変更したかを指示し、その際、各キャッシュ・ラインのそれぞれの指示されたノードが、前記各キャッシュ・ラインを所有するノードであり、ｂ．前記共用メモリ装置内の前記最上位レベルのキャッシュ・メモリにおける前記ノードの１つにおけるキャッシュが、前記共用メモリ装置の最上位レベル・キャッシュでミスするラインに対して、リードまたはライト・アクセスを発すると、前記キャッシュ・ラインを所有するノードによって、前記キャッシュ・ラインを前記最上位レベルのキャッシュ・メモリを相互接続するバス上に出力する、キャッシュ・コヒーレンシ維持方法。
（２）各ノードが共用メモリ・マルチプロセッサである複数のノードを有する共用メモリ装置において、前記共用メモリ装置内の少なくとも３レベルのキャッシュにわたってキャッシュ・コヒーレンシを維持する方法であって、ａ．前記共用メモリ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、前記ステータス・オーナ情報が、リード・オンリ・ラインのいずれのキャッシュが、前記リード・オンリ・ラインを最初に読み取ったかを指示し、リード／ライト・ラインのいずれのノードが、前記リード／ライト・ラインを最後に変更したかを指示し、前記指示されたキャッシュがオーナ・ノードであり、ｂ．前記共用メモリ装置内の前記最上位レベルのキャッシュ・メモリにおける非所有キャッシュが、前記各ラインに対してリード・アクセスを発すると、前記オーナ・ノードの１つが、前記キャッシュ・ラインを前記最上位レベルのキャッシュ・メモリを相互接続するバス上に出力し、ｃ．前記共用メモリ装置の下位レベル・キャッシュが、キャッシュ・ラインに対してライト・リクエストを発すると、上位レベル・キャッシュが、無効化信号を上位レベル・バス上に送り、前記下位レベル・キャッシュ内の情報が無効であることを指示し、前記上位レベル・キャッシュが、前記ライト・リクエストのデータを、前記上位レベル・バス上のリクエスト先に転送し、ｄ．前記高レベルキャッシュ・ラインを所有したノード内の前記高レベル・キャッシュ・ラインの状態を無効に変更する、キャッシュ・コヒーレンシ維持方法。
（３）各ノードが共用メモリ・マルチプロセッサである複数のノードと、キャッシュ・メモリの階層とを備える共用メモリ装置において、最上位レベル・キャッシュにおけるキャシュ・ライン・アクセスの結果、ページ・ミスが発生した場合に、ページを割り当て解除する方法であって、ａ．前記ページの各ラインについて、無効化信号を下位レベル・キャッシュに送り、ｂ．前記下位レベル・キャッシュのいずれかが、前記ページの前記ラインを変更すると、前記変更されたラインを、前記最上位レベル・キャッシュに転送し、ｃ．前記最上位レベル・キャッシュ内の全ての変更されたラインを、他の最上位レベル・キャッシュに転送し、ｄ．前記ページを前記他の最上位レベル・キャッシュ内に割り当てて、前記他の最上位レベル・キャッシュ内に空間を与えて、前記ページの各ラインを格納する、ページの割り当て解除方法。
参考文献１．Ｔ．Ｆｅｎｇ，“Ａ Ｓｕｒｖｅｙ ｏｆ Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ Ｎｅｔｗｏｒｋｓ，”Ｃｏｍｐｕｔｅｒ，ｖｏｌ．１４，ｎｏ．１２，ｐｐ．１２−２７，１９８１．
２．Ｅ．Ｈａｇｅｒｓｔｅｎ，Ａ．Ｌａｎｄｉｎ，ａｎｄ Ｓ．Ｈａｒｉｄｉ，“ＤＤＭ−Ａ Ｃａｃｈｅ−Ｏｎｌｙ Ｍｅｍｏｒｙ Ａｒｃｈｉｔｅｃｔｕｒｅ，”Ｃｏｍｐｕｔｅｒ，ｐｐ４４−５４，Ｓｅｐｔｅｍｂｅｒ １９９２．
３．Ａ．Ｓａｕｌｓｂｕｒｙ，Ｔ．Ｗｉｌｋｉｎｓｏｎ，Ｊ．Ｃａｒｔｅｒ，ａｎｄ Ａ．Ｌａｎｄｉｎ，“Ａｎ Ａｒｇｕｍｅｎｔ ｆｏｒ ＳｉｍｐｌｅＣＯＭＡ，”Ｆｉｒｓｔ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ，ｐｐ２７６−２８５，１９９５．
４．Ａ．Ｗ．Ｗｉｌｓｏｎ，“Ｈｉｅｒａｒｃｈｉｃａｌ Ｃａｃｈｅ／ＢｕｓＡｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｓｈａｒｅｄ Ｍｅｍｏｒｙ Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ，”Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １４ｔｈＡｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ，ｐｐ．２４４−２５２，Ｊｕｎｅ１９８７．
【図面の簡単な説明】
【図１】本発明で使用される階層バス簡易ＣＯＭＡアーキテクチャの概略図である。
【図２】本発明で使用される階層バス多段相互接続ネットワーク・アーキテクチャの概略図である。
【図３】本発明によるキャッシュ・コヒーレンス状態の概略線図を示す図である。
【符号の説明】
１，２ キャッシュ
４ ノード間バス
５ ディスク
６ ディスク・コントローラ
Ｌ２（１），Ｌ３（２） キャッシュ・ライン
Ｈ１ ４ノード共用メモリ・マルチプロセッサ
【０００１】
【発明の属する技術分野】本発明は、マルチレベル共用メモリ・マルチプロセッサ・システムにおけるキャッシュ・コヒーレンシを維持する方法および装置に関する。
【０００２】
【従来の技術】共用メモリ・マルチプロセッサは、プログラミングが容易で、性能が改善されているために非常に一般的である。事実、１本のバスを介してメモリおよび関連するディスクと相互接続された多数のプロセッサ（１６または３２個に及ぶ）からなる市販の多くの共用メモリ・マルチプロセッサが存在する。プロセッサは、典型的には、それらと関係する専用キャッシュを有し、共用メモリ・マルチプロセッサは、バスベースのコヒーレンス・プロトコルを使用してキャッシュ・コヒーレントとなっている。このアーキテクチャは、多段相互接続ネットワーク（ＭＩＮ）［文献１参照］により相互接続された複数のノード（各ノードは、それ自体、１６〜３２ノード共用メモリ・マルチプロセッサである）からなるスケーラブル共用メモリ・プロセッサにおいて、急速に単一の要素となりつつある。しかし、このタイプの共用メモリ・マルチプロセッサ・アーキテクチャは、１つのノード上に存在しないデータに対しては、潜在的に極めて大きいアクセス待ち時間を免れることができない。この問題に対する１つの解決策は、メモリを高レベル・キャッシュとして各ノード上で使用することによって、キャッシュ・オンリ・メモリ・アーキテクチャ［文献２参照］を実現することである。このタイプのアーキテクチャによれば、要求に応じて、データをそれらノードへ自動的に移動させ複写することが容易になる。
【０００３】ＣＯＭＡアーキテクチャの主要な問題点は、高価で複雑なハードウェアであるという点である。しかし、この問題点を最小限にするために、従来より簡易ＣＯＭＡアーキテクチャ〔文献３参照〕が提案されてきた。簡易ＣＯＭＡアーキテクチャでは、ページング・ソフトウェアが、ページング・レベルでのキャッシュ空間の割り当てと割り当て解除とを管理し、キャッシュ・コヒーレンスを維持するためには余り複雑でないハードウェアが使用されている。しかし、ノード全体にわたってキャッシュ・コヒーレンスを維持する方法は、ディレクトリ・ベースで行われるため、ノード全体のデータ・アクセスと制御とに伴うペナルティは（このようなアクセスの頻度は、可能性として少いとはいえ）相当なものになる可能性がある。
【０００４】
【発明が解決しようとする課題】本発明の目的は、スケーラブル共用メモリ・マルチプロセッサ装置においてノード・ホップをもたらすようなキャッシュ・ミスに伴う待ち時間を最小限にすることにある。
【０００５】本発明の他の目的は、コヒーレントなディレクトリの必要のないスケーラブル共用メモリ・マルチプロセッサを構築する費用効果的な方法を提供することにある。
【０００６】
【課題を解決するための手段】従って、本発明は、各ノードが共用メモリ・マルチプロセッサである複数のノードを有する共用メモリ・マルチプロセッサ装置において、マルチレベルのキャッシュ全体にわたってキャッシュ・コヒーレンシを維持する方法を提供する。本発明によれば、共用メモリ・マルチプロセッサ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、ステータス・オーナ情報は、リード・オンリ・ラインのノードのいずれが最初にリード・オンリ・ラインを読み取ったかを指示し、リード／ライト・ラインのノードのいずれが、最初にリード／ライト・ラインを読み取り、最後に変更したかを指示し、その際、各キャシュラインの指示されたノードがキャッシュ・ラインを所有するノードである。共用メモリ・マルチプロセッサ装置内の最上位レベルのキャッシュ・メモリのノードの１つのキャッシュが、共用メモリ・プロセッサ装置の最上位レベル・キャッシュでミスするラインに、リードまたはライト・アクセス命令を発すると、キャッシュ・ラインのオーナは、最上位レベルのキャッシュ・メモリを相互接続するバス上にキャッシュ・ラインを出力する。この場合、命令を発するキャッシュは、ラインのオーナによりバス上に出力されたキャッシュ・ラインを用いて、そのキャッシュ・ラインをそれぞれ読み取り、または変更する。
【０００７】
【発明の実施の形態】図１は、２ノード共用メモリ・マルチプロセッサ・システムであって、各ノードがそれ自体、４ノード共用メモリ・マルチプロセッサＨ１であるものの論理図表である。このノードには、キャッシュ１，２が示され、低レベルＬ２キャッシュ１は、１個のプロセッサと関係するものとする。この簡易ＣＯＭＡアーキテクチャは、主メモリを含んではいないが、ディスク５、およびそれと関係するディスク・コントローラ６が、ノードＨ１（ディスクのホーム・ノードとして示す）上に物理的に常駐するものとする。提案された２つのアーキテクチャ（バス・オンリ（図１）とバス／ＭＩＮ（図２））のプロトコル・アクティビティの基本的な相違は、バス・オンリ（図１）が、制御とデータ転送の双方にノード間バス４を使用する一方、バス／ＭＩＮアーキテクチャ（図２）が、制御にはノード間バス４を、データ転送にはノード間ＭＩＮ７を使用する点である。これら２つの提案アーキテクチャに必要とされるコヒーレンス・アクティビティの大部分は、同一である。それ故、我々は、説明をバス・オンリ・アーキテクチャ案（図１）に集中することにする。しかし、バス／ＭＩＮアーキテクチャのプロトコル・アクティビティ（図２）は、それがバス・オンリ・プロトコル・アクティビティと異なる場合に特に説明することにする。
【０００８】キャッシュ・コヒーレンスを維持するために、Ｌ２（１）とＬ３（２）のキャッシュは、共に、それぞれのキャッシュ・ライン・エントリに関する状態情報を含んでいる。コヒーレンス・プロトコルは、ジェネリックＭ，Ｅ，Ｓ，Ｉ（変更、専用、共用、無効）プロトコルであるとする。Ｌ２キャッシュ１の場合、このジェネリック・プロトコルは、典型的な階層バス・プロトコル［文献４参照］と共に使用することができる。我々の提案においては、主メモリの概念は存在しないので、共用オーナ状態と称されるもう１つの状態を使用して、リード・オンリ・ラインのオーナを指定する。リード・ミスでキャッシュ・ラインをキャッシュへ転送するリクエストが存在する場合、ラインのオーナがデータを供給する。ラインが変更、専用、または共用オーナの状態にある場合には、そのラインを含むキャッシュが、そのオーナである。
【０００９】我々の提案の本質は、Ｌ３コヒーレンス・プロトコルを階層バス簡易ＣＯＭＡアーキテクチャに対して実施する時に必要とされる特別なアクションである。例えば、キャッシュ置換ストラテジはページ置換ストラテジとなり、本発明はこのページ置換ストラテジがＬ３キャッシュ・コヒーレンスとどのように一体化されているかを開示する。
【００１０】Ｌ３キャッシュ・ラインは、以下に概説し図３に示されるような５つの状態の１つをとることができる。
・Ｅ−専用（８） ラインは、Ｌ３キャッシュ（２）および／またはその関連する低レベル・キャッシュに常駐するのみで、変更されていない。
・ＳＯ−共用オーナ（９Ｂ） ラインは、幾つかのＬ３キャッシュ（２）に常駐し、変更されていない。このキャッシュ・ラインは、リモートＬ３キャッシュ（２）がラインに対してミスを有する場合には常に、このＬ３バス（４）上に出力される。
・Ｓ−共用（９Ａ） ラインは、幾つかのＬ３キャッシュ（２）に常駐し、変更されていない。
・Ｍ−変更（１０） ラインは、Ｌ３キャッシュ（２）および／またはその関連する低レベル・キャッシュに常駐するのみで、変更されている。
・Ｉ−無効（１１） キャッシュのラインに対して空間が割り当てられたが、データが無効である、すなわちラインに対してキャッシュに空間が割り当てられていない。
【００１１】専用状態と変更状態を１つの状態に組み合わせることができる。
【００１２】Ｌ３キャッシュ（２）のコヒーレンス・アクションを引き起こす幾つかの事象がある。それらは、Ｌ２バス・リード（ＡＲ）またはバス・ライト（ＡＷ）、Ｌ３バス・リード（ＢＲ）またはバス・ライト（ＢＷ）、Ｌ２またはＬ３無効化（それぞれＩＮＶ−ＡおよびＩＮＶ−Ｂ）、Ｌ３キャッシュ・フラッシュ（ＦＬ−Ｂ）を含む。我々は、簡易ＣＯＭＡアーキテクチャを想定しているから、Ｌ３キャッシュ・ラインに対して空間が割り当てられていなければ、空間は、ラインを含むページに対しても割り当てられていない。そのため、ページ・ミスによって、ページ置換ストラテジの開始と、Ｌ２およびＬ３のキャッシュ・ミスの処理とが必要になる。以下のページ置換の説明を参照されたい。以下に説明するのは、Ｌ３キャッシュ・ラインが以下に説明する５つの状態の１つにある時に、これら事象の結果としてとられるアクションである。図３を参照されたい。
【００１３】・無効（Ｉ）１１ ラインが無効状態にあり、Ｌ３バス・リード（ＢＲ）またはバス・ライト（ＢＷ）が行われると、ラインはＩ状態に留まる。図３の１２を参照されたい。、Ｌ２バス・リード（ＡＲ）が行われると、Ｌ３キャッシュ２は、バス・リード信号をＬ３バス４上に出力し、空間が既にキャッシュに割り当てられていれば、データをリクエストする。空間が割り当てられていなければ、ページ置換ストラテジが実行され（リクエストされたページを割り当てる）、データはオーナからＬ３キャッシュへ転送される。また、Ｌ２バス・リード（ＡＲ）の結果、他のキャッシュがラインのコピーを有しなければ、Ｅ（８）へ変化し（ライン１３上のＡＲ／ＢＲを参照）、少なくとも１つのリモートＬ３キャッシュ（オーナ）にコピーが存在すれば、Ｓ（９Ａ）へと変化する。ライン１４上のＡＲ／ＢＲを参照されたい。Ｌ２キャッシュの書き込みが行われると、Ｌ３キャッシュは、リード・ウィズ・インテント・トゥ・モディファイ（ｒｅａｄ−ｗｉｔｈ−ｉｎｔｅｎｔ−ｔｏ−ｍｏｄｉｆｙ）信号を、Ｌ３バス４上に出力する。その結果、データはオーナ・キャッシュであるリモートＬ３からリクエスト中のＬ３キャッシュへ転送され、Ｌ３バス４上には無効化信号が現れる。無効化信号の結果、リモート・ノードがラインのコピーを有していれば、そのラインは無効化される。最後に、キャッシュ・ラインの状態は、Ｌ２キャッシュ（１）ライト（ＡＷ）の結果、Ｍ（１０）に変化し、Ｌ３キャッシュが、ラインの専用オーナとなる。ＡＷライン１５を参照されたい。
【００１４】リード・ウィズ・インテント・トゥ・モディファイ信号は、リモート・キャッシュに対して、或るキャッシュが、まさにデータを変更しようとしていることを知らせるために使用される典型的なタイプの信号である。それはまた、これらキャッシュに対して、データの有効なコピーを有しないことを知らせることによって、それがデータの有効なコピーを得た後（この場合にはリモートＬ３キャッシュから）、そのコピーを変更できるようにするものである。
【００１５】・専用（Ｅ）（８） Ｌ２バス・リード（ＡＲ）がこの状態にある時に行われれば、Ｌ３キャッシュ・ラインは、この状態に留まる。ライン１６を参照されたい。Ｌ３バス・リード（ＢＲ）がこの状態にある時に行われれば、Ｌ３キャッシュ・ラインの状態は、ＳＯに変化し（ライン２１を参照）、Ｌ３キャッシュは、ラインをリクエスト中のＬ３キャッシュへ転送する。Ｌ２バスの書き込みが行われれば、Ｌ３ラインの状態は、Ｍ（１０）に変化する。ライン１７を参照されたい。
【００１６】Ｌ３のリード・ウィズ・インテント・トゥ・モディファイ・バス信号が発生すると、Ｌ３キャッシュは、無効化信号をＬ２バス上に出力し、Ｌ２キャッシュ（１）のキャッシュ・ラインを無効化する。また、Ｌ３キャッシュは、ラインをＬ３バス（４）上に出力し、リクエスト先に送る。ラインの状態は、Ｉ（１１）へ変化する。ライン１８上のＢＷ、ＩＮＶ−Ａを参照されたい。
【００１７】・共用オーナ（ＳＯ）（９Ｂ）または共用（Ｓ）（９Ａ） Ｌ２またはＬ３バス・リードがこれらの状態にある間に行われると、Ｌ３キャッシュ・ラインは、それぞれの状態に留まる。ライン２２，２３上のＡＲ，ＢＲを参照されたい。Ｌ３キャッシュ・ラインの状態がＳＯであれば、Ｌ３バス・リードの結果、Ｌ３キャッシュは、Ｌ３バス上のＬ３キャッシュ・ライン・データを、Ｌ３リクエスト先に転送する。Ｌ２リード・ウィズ・インテント・トウ・モディファイ・バス信号が発生すると、Ｌ３キャッシュ２は、リモートＬ３コピーが無効化されるように、無効化信号をＬ３バス上に出力する。キャッシュ・ラインの状態は、その後、Ｍ（１０）に変化する。ライン２４，２８を参照されたい。
【００１８】Ｌ３リード・ウィズ・インテント・トウ・モディファイ・バス信号が発生すると、Ｌ３キャッシュ２は、無効化信号をラインのＬ２キャッシュ・バス上に出力する。キャッシュ・ラインがＳＯ状態にあれば、Ｌ３キャッシュ（２）は、Ｌ３バスを介してデータをリクエスト先に転送し、その後、ラインの状態はＩ（１１）へ変化する。ライン２６，２７を参照されたい。
【００１９】共用オーナは、同時に幾つかのキャッシュに存在する（従って、共用される）１本のラインのオーナを指定するために使用される。これは、リード・オンリ・ラインと、キャッシュ内に常駐する間のある時点で変更され（従って、専用的に所有される）、他の時間に共用されるラインとを含む。リード／ライト・ラインがいずれかのキャッシュにある場合、それはそのキャッシュ内にのみ存在する（１ラインのリード／ライト・コピーを有する１個のキャッシュのみが存在することができる）。それ故、デフォルトにより、そのキャッシュはラインの専用オーナである。さて、続くノードが、リモート・ノードのリード／ライト状態にあるラインを読み取りたい場合、そのライン（専用オーナ）の専用コピーを有するキャッシュは、データをリクエスト中のキャッシュへ供給する。従って、両キャッシュのキャッシュ・ラインの状態が共用される。これはラインが、現在、２ノードのキャッシュに存在し、それが共用されるからである。それは以前に変更されたものであるが、一旦、ラインの専用変更コピーを有するキャッシュが、この変更ラインを、リード命令を発したリクエスト中のキャッシュへ転送すると、両キャッシュのラインの状態は共用されることになる。この時点で、ラインの同じコピー（共用コピー）を有する２個のキャッシュが存在する。この状態で、我々は、ラインの専用リード／ライト・コピーを本来有したキャッシュ（従って、専用オーナであった）が、今、ラインの共用オーナとなることを主張しているのである。
【００２０】・変更（Ｍ）（１０） Ｌ２バス・リード（ＡＯ）またはライト（ＡＷ）が発生すると、Ｌ２キャッシュ・ラインは、ラインのＬ２キャッシュ・オーナからリクエスト中のＬ２キャッシュ１へ転送される。Ｌ２キャッシュ・オーナが存在しない場合には、Ｌ３キャッシュ２が、データを供給する。ラインの状態は不変である。ライン１９を参照されたい。Ｌ３バス・リード信号が発生すると、Ｌ２バス・リードが発生し、キャッシュ・フラッシュによって、変更データは、Ｌ２キャッシュ（１）からＬ３キャッシュ（２）へ転送される。次に、ラインは、Ｌ３バス（４）上へフラッシュし、リクエスト中のＬ３キャッシュ（２）へ戻る。Ｌ３キャッシュ・ラインの状態はＳＯ（９Ｂ）に変化する。ライン２０を参照されたい。Ｌ３リード・ウィズ・インテント・トウ・モディファイ・バス信号が発生すると、Ｌ３キャッシュ（２）は、無効化信号をＬ２バス（３）上に出力する。その結果、Ｌ２キャッシュ（１）からＬ３キャッシュ（２）への変更データのキャッシュ・フラッシュが発生する。一旦フラッシュがＬ３キャッシュ（２）へと転送されると、Ｌ３バス（４）上へフラッシュされ、リクエスト中のＬ３キャッシュへ転送される。Ｌ３キャッシュ・ラインの状態は、Ｉ（１１）へ変更される。ライン２０を参照されたい。
【００２１】ページ置換ストラテジは、Ｌ３キャッシュの多数のキャッシュ・ラインからなるページの割り当て解除を含んでいる。このストラテジは、また、Ｌ２（従って、Ｌ３）キャッシュにおいてリクエストされたキャッシュ・ラインを含むページの割り当てを含んでいる。図３のライン１３〜１５上のＤＡを参照されたい。
【００２２】ページ割り当ての最初の段階では、ページの選択を割り当て解除することが必要である（例えば、最近一番使用されていない、すなわちＬＲＵページ）。次に、ページを構成する各ライン毎に、無効化信号をＬ２バス上に出力する。この無効化信号の結果、Ｌ２キャッシュ１の変更ラインは、いずれも、Ｌ３キャッシュ２へフラッシュされる。また、Ｌ２キャッシュ１内に存在するページを構成するキャッシュ・ラインは、全て、無効化される。次に、割り当て解除されるページ内の変更された専用ラインは、ページを割り当てられたリモートＬ３キャッシュへ書き込む必要がある。ページを割り当てられたリモートＬ３キャッシュが存在しない場合には、変更ラインのみがホーム・ディスクヘ書き戻される。リモートＬ３キャッシュがページを割り当てられたかどうかを判別するために、ページの最初のラインのグローバル・アドレスがＬ３バス４上に出力される。（グローバル・アドレスの判別については、以下の説明を参照されたい。）このアドレスは、割り当て照会すなわちＡＩバス信号を伴う。Ｌ３キャッシュ（２）がページを割り当てられていれば、バス上に割り当てフラグを立てる。バス／ＭＩＮアーキテクチャ（図２）の場合には、また、ノード識別子がバス上に出力される。リモートＬ３キャッシュがページを割り当てられていれば、割り当て解除されるキャッシュ・ラインの変更された専用コピーは、全て、Ｌ３バス４（または図２のバス／ＭＩＮアーキテクチャの場合、ＭＩＮ７）上に転送され、ページが割り当てられたＬ３キャッシュ２は、変更された専用ラインの各々のコピーを取得する。幾つかのＬ３キャッシュ２がページを割り当てられていれば、ラインの変更コピーを受け取るために、いずれか１つのＬ３キャッシュがランダムに選ばれるか、あるいはリモートＬ３キャッシュの全てが、専用ラインを受け取ることができる。１つのリモートＬ３しかページを割り当てられていなければ、転送されたラインの状態は、それぞれ変更状態と専用状態において割り当て解除されたページにあったラインの場合、Ｍ（１０）とＥ（８）である。
【００２３】幾つかのＬ３キャッシュがページを割り当てられると、変更ラインの状態は、１つのＬ３キャッシュ（２）がこれらラインのコピーを取得する限り、Ｍ（１０）に留まる。その状態は、次の場合に、Ｓ（９Ａ）へと変化する。すなわち、Ｌ３キャッシュ（２）の１つが状態ＳＯでラインのコピーを取得する場合を除いて、他の全てのＬ３キャッシュ（２）が変更ラインのコピーを受け取る場合である。しかし、ページが割り当てられた全てのＬ３キャッシュ（２）は、専用ラインのコピーを取得する。その結果、これらラインの状態は、Ｌ３キャッシュにおいてＳとなる。また、変更ラインを受け取るキャッシュは、専用ラインの共用オーナＳＯ（９Ｂ）のコピーを取得する（変更ラインが存在しなければ、Ｓ０状態の専用ラインを取得するために、１キャッシュが選択される）。
【００２４】ページを割り当てられたリモートＬ３キャッシュが存在しなければ、割り当て解除されるページの変更ラインのみが、ホーム・ディスクへ書き戻されるか、あるいはホーム・ノードのリモートＬ３キャッシュに出力される。割り当て解除されたページを含むＬ３キャッシュが、ホームディスクと同じノード上に配置されていれば、変更ラインは、ディスク５ヘ書き戻される。さもなければ、変更ラインを含むページについては、ホーム・ディスクを含むノードのリモートＬ３キャッシュ２に空間が割り当てられる。変更データは、このリモートＬ３キャッシュ２へ転送される。変更ページは、リモート（ホーム）Ｌ３キャッシュ２内に、最優先の置換順位をもってマークされる。ページ置換ポリシーの実現のため、このリモートＬ３キャッシュにおいて割り当て解除するために、ページが一旦選択されると、変更データが、ノードＨ１上のディスク５ヘ書き戻される。我々はこの方法を「変更ライン・ポリシー」と表現する。
【００２５】ページ割り当てが完了すると、新しいページがＬ３キャッシュに割り当てられ、リクエストされたライン（および／またはページ内の他のライン）のキャッシュ内へ転送する処理が開始する。バス・リードまたはバス・ライト信号が、リクエストされたラインのＬ３バス４上に出力される。Ｌ３キャッシュ（２）がキャッシュラインのコピーを有する場合には、それはバス（４）（シングル・バス・アーキテクチャ、図１）またはＭＩＮ（７）（バス／ＭＩＮアーキテクチャ、図２）を介して、リクエスト中のＬ３キャッシュへ転送される。他のライン（ページの残りのラインに対して）のライン転送は必要ない。それ故、これら残りのラインに対して空間が割り当てられているが、それらはキャッシュには常駐しない。これらキャッシュ・ラインの状態は、従って、無効である（Ｉ）（１１）。
【００２６】キャッシュ・ラインのコピーを有するＬ３キャッシュが存在しない（従って、関連するページが割り当てられたＬ３キャッシュが存在しない）場合には、ページは、ホーム・ディスクから読み込まれる。ホーム・ディスクが、リクエスト中のＬ３キャッシュと同じノード上に存在するならば、ディスク５からＬ３キャッシュへのページ転送は、スムーズに行われる。ホーム・ディスクが別のノード上にある場合には、ページは、ディスク・ホーム・ノードのＬ３キャッシュに割り当てられなければならず（その結果、そのキャッシュにページ割り当て解除が生ずる可能性がある）、ホーム・ディスクからディスク・ホームノードのＬ３キャッシュへ転送される。リクエストされたラインは、そのＬ３キャッシュからリクエスト中のＬ３キャッシュへと転送される（シングル・バス・アーキテクチャ、図１）。バス／ＭＩＮアーキテクチャ（図２）の場合、ホーム・ディスク・ノードのＬ３キャッシュにページを割り当てる必要はない。ページは、ディスクからバッファへ転送された後、バッファからＭＩＮを介してリモートＬ３キャッシュへ転送することができる。
【００２７】簡易ＣＯＭＡアーキテクチャでは、各個別ＳＭＰ構成ブロックＨ１（すなわち、図１に鎖線のブロックで識別されるＳＭＰ）は、それ自身のアドレス空間を有する。しかし、全体の機構は、ＳＭＰ構成ブロックＨ１どうしの間の通信を容易にするために、グローバル・アドレス空間を有する必要がある。しかし、ＳＭＰ構成ブロックＨ１の仮想アドレス空間は、少なくともブロックのディスク容量より大きなオーダーの大きさであることが想定されている。その結果、各ノードの仮想アドレス空間は、共用メモリ・マルチプロセッサ・システムのグローバル・アドレス空間として使用することもできる。このグローバルアドレス空間は、Ｎ個のサブアドレス空間に分割されるものとする。但し、Ｎはシステム内のノードの総数である。従って、或るページについて、そのページの仮想アドレスは、各ノード上の同じグローバル・アドレスをマップする。
【００２８】まとめとして、本発明の構成に関して以下の事項を開示する。
（１）各ノードが共用メモリ・マルチプロセッサである複数のノードと、キャッシュメモリの階層とを備える共用メモリ装置において、リードまたはライト・アクセス・コマンドに応答して前記共用メモリ装置におけるキャッシュ・コヒーレンシを維持する方法であって、ａ．前記共用メモリ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、前記ステータス・オーナ情報は、リード・オンリ・ラインのノードのいずれが、最初に前記リード・オンリ・ラインを読み取ったかを指示し、リード／ライト・ラインのノードのいずれが、前記リード／ライト・ラインを最初に読み取り、または、前記リード／ライト・ラインを最後に変更したかを指示し、その際、各キャッシュ・ラインのそれぞれの指示されたノードが、前記各キャッシュ・ラインを所有するノードであり、ｂ．前記共用メモリ装置内の前記最上位レベルのキャッシュ・メモリにおける前記ノードの１つにおけるキャッシュが、前記共用メモリ装置の最上位レベル・キャッシュでミスするラインに対して、リードまたはライト・アクセスを発すると、前記キャッシュ・ラインを所有するノードによって、前記キャッシュ・ラインを前記最上位レベルのキャッシュ・メモリを相互接続するバス上に出力する、キャッシュ・コヒーレンシ維持方法。
（２）各ノードが共用メモリ・マルチプロセッサである複数のノードを有する共用メモリ装置において、前記共用メモリ装置内の少なくとも３レベルのキャッシュにわたってキャッシュ・コヒーレンシを維持する方法であって、ａ．前記共用メモリ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、前記ステータス・オーナ情報が、リード・オンリ・ラインのいずれのキャッシュが、前記リード・オンリ・ラインを最初に読み取ったかを指示し、リード／ライト・ラインのいずれのノードが、前記リード／ライト・ラインを最後に変更したかを指示し、前記指示されたキャッシュがオーナ・ノードであり、ｂ．前記共用メモリ装置内の前記最上位レベルのキャッシュ・メモリにおける非所有キャッシュが、前記各ラインに対してリード・アクセスを発すると、前記オーナ・ノードの１つが、前記キャッシュ・ラインを前記最上位レベルのキャッシュ・メモリを相互接続するバス上に出力し、ｃ．前記共用メモリ装置の下位レベル・キャッシュが、キャッシュ・ラインに対してライト・リクエストを発すると、上位レベル・キャッシュが、無効化信号を上位レベル・バス上に送り、前記下位レベル・キャッシュ内の情報が無効であることを指示し、前記上位レベル・キャッシュが、前記ライト・リクエストのデータを、前記上位レベル・バス上のリクエスト先に転送し、ｄ．前記高レベルキャッシュ・ラインを所有したノード内の前記高レベル・キャッシュ・ラインの状態を無効に変更する、キャッシュ・コヒーレンシ維持方法。
（３）各ノードが共用メモリ・マルチプロセッサである複数のノードと、キャッシュ・メモリの階層とを備える共用メモリ装置において、最上位レベル・キャッシュにおけるキャシュ・ライン・アクセスの結果、ページ・ミスが発生した場合に、ページを割り当て解除する方法であって、ａ．前記ページの各ラインについて、無効化信号を下位レベル・キャッシュに送り、ｂ．前記下位レベル・キャッシュのいずれかが、前記ページの前記ラインを変更すると、前記変更されたラインを、前記最上位レベル・キャッシュに転送し、ｃ．前記最上位レベル・キャッシュ内の全ての変更されたラインを、他の最上位レベル・キャッシュに転送し、ｄ．前記ページを前記他の最上位レベル・キャッシュ内に割り当てて、前記他の最上位レベル・キャッシュ内に空間を与えて、前記ページの各ラインを格納する、ページの割り当て解除方法。
参考文献１．Ｔ．Ｆｅｎｇ，“Ａ Ｓｕｒｖｅｙ ｏｆ Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ Ｎｅｔｗｏｒｋｓ，”Ｃｏｍｐｕｔｅｒ，ｖｏｌ．１４，ｎｏ．１２，ｐｐ．１２−２７，１９８１．
２．Ｅ．Ｈａｇｅｒｓｔｅｎ，Ａ．Ｌａｎｄｉｎ，ａｎｄ Ｓ．Ｈａｒｉｄｉ，“ＤＤＭ−Ａ Ｃａｃｈｅ−Ｏｎｌｙ Ｍｅｍｏｒｙ Ａｒｃｈｉｔｅｃｔｕｒｅ，”Ｃｏｍｐｕｔｅｒ，ｐｐ４４−５４，Ｓｅｐｔｅｍｂｅｒ １９９２．
３．Ａ．Ｓａｕｌｓｂｕｒｙ，Ｔ．Ｗｉｌｋｉｎｓｏｎ，Ｊ．Ｃａｒｔｅｒ，ａｎｄ Ａ．Ｌａｎｄｉｎ，“Ａｎ Ａｒｇｕｍｅｎｔ ｆｏｒ ＳｉｍｐｌｅＣＯＭＡ，”Ｆｉｒｓｔ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ，ｐｐ２７６−２８５，１９９５．
４．Ａ．Ｗ．Ｗｉｌｓｏｎ，“Ｈｉｅｒａｒｃｈｉｃａｌ Ｃａｃｈｅ／ＢｕｓＡｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｓｈａｒｅｄ Ｍｅｍｏｒｙ Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ，”Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １４ｔｈＡｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ，ｐｐ．２４４−２５２，Ｊｕｎｅ１９８７．
【図面の簡単な説明】
【図１】本発明で使用される階層バス簡易ＣＯＭＡアーキテクチャの概略図である。
【図２】本発明で使用される階層バス多段相互接続ネットワーク・アーキテクチャの概略図である。
【図３】本発明によるキャッシュ・コヒーレンス状態の概略線図を示す図である。
【符号の説明】
１，２ キャッシュ
４ ノード間バス
５ ディスク
６ ディスク・コントローラ
Ｌ２（１），Ｌ３（２） キャッシュ・ライン
Ｈ１ ４ノード共用メモリ・マルチプロセッサ
【特許請求の範囲】
【請求項１】各ノードが共用メモリ・マルチプロセッサである複数のノードと、キャッシュメモリの階層とを備える共用メモリ装置において、リードまたはライト・アクセス・コマンドに応答して前記共用メモリ装置におけるキャッシュ・コヒーレンシを維持する方法であって、ａ．前記共用メモリ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、前記ステータス・オーナ情報は、リード・オンリ・ラインのノードのいずれが、最初に前記リード・オンリ・ラインを読み取ったかを指示し、リード／ライト・ラインのノードのいずれが、前記リード／ライト・ラインを最初に読み取り、または、前記リード／ライト・ラインを最後に変更したかを指示し、その際、各キャッシュ・ラインのそれぞれの指示されたノードが、前記各キャッシュ・ラインを所有するノードであり、ｂ．前記共用メモリ装置内の前記最上位レベルのキャッシュ・メモリにおける前記ノードの１つにおけるキャッシュが、前記共用メモリ装置の最上位レベル・キャッシュでミスするラインに対して、リードまたはライト・アクセスを発すると、前記キャッシュ・ラインを所有するノードによって、前記キャッシュ・ラインを前記最上位レベルのキャッシュ・メモリを相互接続するバス上に出力する、キャッシュ・コヒーレンシ維持方法。
【請求項２】各ノードが共用メモリ・マルチプロセッサである複数のノードを有する共用メモリ装置において、前記共用メモリ装置内の少なくとも３レベルのキャッシュにわたってキャッシュ・コヒーレンシを維持する方法であって、ａ．前記共用メモリ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、前記ステータス・オーナ情報が、リード・オンリ・ラインのいずれのキャッシュが、前記リード・オンリ・ラインを最初に読み取ったかを指示し、リード／ライト・ラインのいずれのノードが、前記リード／ライト・ラインを最後に変更したかを指示し、前記指示されたキャッシュがオーナ・ノードであり、ｂ．前記共用メモリ装置内の前記最上位レベルのキャッシュ・メモリにおける非所有キャッシュが、前記各ラインに対してリード・アクセスを発すると、前記オーナ・ノードの１つが、前記キャッシュ・ラインを前記最上位レベルのキャッシュ・メモリを相互接続するバス上に出力し、ｃ．前記共用メモリ装置の下位レベル・キャッシュが、キャッシュ・ラインに対してライト・リクエストを発すると、上位レベル・キャッシュが、無効化信号を上位レベル・バス上に送り、前記下位レベル・キャッシュ内の情報が無効であることを指示し、前記上位レベル・キャッシュが、前記ライト・リクエストのデータを、前記上位レベル・バス上のリクエスト先に転送し、ｄ．前記高レベルキャッシュ・ラインを所有したノード内の前記高レベル・キャッシュ・ラインの状態を無効に変更する、キャッシュ・コヒーレンシ維持方法。
【請求項３】各ノードが共用メモリ・マルチプロセッサである複数のノードと、キャッシュ・メモリの階層とを備える共用メモリ装置において、最上位レベル・キャッシュにおけるキャシュ・ライン・アクセスの結果、ページ・ミスが発生した場合に、ページを割り当て解除する方法であって、ａ．前記ページの各ラインについて、無効化信号を下位レベル・キャッシュに送り、ｂ．前記下位レベル・キャッシュのいずれかが、前記ページの前記ラインを変更すると、前記変更されたラインを、前記最上位レベル・キャッシュに転送し、ｃ．前記最上位レベル・キャッシュ内の全ての変更されたラインを、他の最上位レベル・キャッシュに転送し、ｄ．前記ページを前記他の最上位レベル・キャッシュ内に割り当てて、前記他の最上位レベル・キャッシュ内に空間を与えて、前記ページの各ラインを格納する、ページの割り当て解除方法。
【請求項１】各ノードが共用メモリ・マルチプロセッサである複数のノードと、キャッシュメモリの階層とを備える共用メモリ装置において、リードまたはライト・アクセス・コマンドに応答して前記共用メモリ装置におけるキャッシュ・コヒーレンシを維持する方法であって、ａ．前記共用メモリ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、前記ステータス・オーナ情報は、リード・オンリ・ラインのノードのいずれが、最初に前記リード・オンリ・ラインを読み取ったかを指示し、リード／ライト・ラインのノードのいずれが、前記リード／ライト・ラインを最初に読み取り、または、前記リード／ライト・ラインを最後に変更したかを指示し、その際、各キャッシュ・ラインのそれぞれの指示されたノードが、前記各キャッシュ・ラインを所有するノードであり、ｂ．前記共用メモリ装置内の前記最上位レベルのキャッシュ・メモリにおける前記ノードの１つにおけるキャッシュが、前記共用メモリ装置の最上位レベル・キャッシュでミスするラインに対して、リードまたはライト・アクセスを発すると、前記キャッシュ・ラインを所有するノードによって、前記キャッシュ・ラインを前記最上位レベルのキャッシュ・メモリを相互接続するバス上に出力する、キャッシュ・コヒーレンシ維持方法。
【請求項２】各ノードが共用メモリ・マルチプロセッサである複数のノードを有する共用メモリ装置において、前記共用メモリ装置内の少なくとも３レベルのキャッシュにわたってキャッシュ・コヒーレンシを維持する方法であって、ａ．前記共用メモリ装置内の最上位レベルのキャッシュ・メモリの各ラインについてステータス・オーナ情報を維持し、前記ステータス・オーナ情報が、リード・オンリ・ラインのいずれのキャッシュが、前記リード・オンリ・ラインを最初に読み取ったかを指示し、リード／ライト・ラインのいずれのノードが、前記リード／ライト・ラインを最後に変更したかを指示し、前記指示されたキャッシュがオーナ・ノードであり、ｂ．前記共用メモリ装置内の前記最上位レベルのキャッシュ・メモリにおける非所有キャッシュが、前記各ラインに対してリード・アクセスを発すると、前記オーナ・ノードの１つが、前記キャッシュ・ラインを前記最上位レベルのキャッシュ・メモリを相互接続するバス上に出力し、ｃ．前記共用メモリ装置の下位レベル・キャッシュが、キャッシュ・ラインに対してライト・リクエストを発すると、上位レベル・キャッシュが、無効化信号を上位レベル・バス上に送り、前記下位レベル・キャッシュ内の情報が無効であることを指示し、前記上位レベル・キャッシュが、前記ライト・リクエストのデータを、前記上位レベル・バス上のリクエスト先に転送し、ｄ．前記高レベルキャッシュ・ラインを所有したノード内の前記高レベル・キャッシュ・ラインの状態を無効に変更する、キャッシュ・コヒーレンシ維持方法。
【請求項３】各ノードが共用メモリ・マルチプロセッサである複数のノードと、キャッシュ・メモリの階層とを備える共用メモリ装置において、最上位レベル・キャッシュにおけるキャシュ・ライン・アクセスの結果、ページ・ミスが発生した場合に、ページを割り当て解除する方法であって、ａ．前記ページの各ラインについて、無効化信号を下位レベル・キャッシュに送り、ｂ．前記下位レベル・キャッシュのいずれかが、前記ページの前記ラインを変更すると、前記変更されたラインを、前記最上位レベル・キャッシュに転送し、ｃ．前記最上位レベル・キャッシュ内の全ての変更されたラインを、他の最上位レベル・キャッシュに転送し、ｄ．前記ページを前記他の最上位レベル・キャッシュ内に割り当てて、前記他の最上位レベル・キャッシュ内に空間を与えて、前記ページの各ラインを格納する、ページの割り当て解除方法。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開平１１−３１６７５０
【公開日】平成１１年（１９９９）１１月１６日
【国際特許分類】
【出願番号】特願平１１−３０４３５
【出願日】平成１１年（１９９９）２月８日
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレイション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【公開日】平成１１年（１９９９）１１月１６日
【国際特許分類】
【出願日】平成１１年（１９９９）２月８日
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレイション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
[ Back to top ]