(57)【特許請求の範囲】
【請求項１】
マルチレベルの階層ツリー構造状に配設された複数の相互接続部のうち上位レベルの相互接続部に接続された複数のプロセッサが下位レベルの相互接続部に接続されたメモリに結合されるようにしたコンピュータ・ネットワークにおいて、複数のプロセッサが情報を共用する場合にキャッシュ・コヒーレンシを維持するためのコンピュータ・システムであって、
前記上位レベルの相互接続部のうち互いに異なる相互接続部にそれぞれ接続され、前記メモリへの第１及び第２のアクセス・パス上にある各レベルの相互接続部を介して前記メモリからの１つの情報ユニットにアクセスして共用し、それぞれの関連する第１及び第２のキャッシュ内に当該情報ユニットを格納する第１及び第２のプロセッサを含み、
前記第１及び第２のアクセス・パス上にある少なくとも２つの相互接続部のそれぞれが
関連するプロセッサ又は他のレベルの相互接続部のグロ−バル・ポートに接続するための少なくとも１つのローカル・ポート、他のレベルの相互接続部のローカル・ポート又は入出力デバイスに接続するための少なくとも１つのグロ−バル・ポート、相互接続キャッシュ又は前記メモリに接続するためのメモリ・ポートと、
前記ローカル・ポート、前記グロ−バル・ポート、及び前記メモリ・ポートの相互間のトラフィックを経路指定するための相互接続スイッチと、
１組のレコードを含み、各レコードが１つの情報ユニットに関連付けられ、各レコードが前記ローカル及びグロ−バル・ポートの各々ごとに１つの項目を含み、当該項目の値が当該各ポートにより到達可能なプロセッサによって当該情報ユニットのコピーが保持されているか否かを個別に表すためのパス・インジケータとして機能するコヒーレンシ・ディレクトリと、
前記コヒーレンシ・ディレクトリに結合され、当該相互接続部を通過するアクセス要求に応答して、前記コヒーレンシ・ディレクトリ内の前記項目の値の異なる組み合わせを表す少なくとも２つのコヒーレンシ状態を、当該アクセス要求によって要求された１つの情報ユニットのすべてのコピーが活動的な値をセットされている単一の前記項目に関連する単一のローカル・ポートにより到達可能であり且つグロ−バル・ポートにより到達不能であることを示すローカル所有者状態、及び前記情報ユニットの少なくとも１つのコピーが少なくとも１つのローカル・ポートにより到達可能であり且つグローバル・ポートによっても到達可能であることを示すグローバル共用状態として選択的に設定し、当該設定されたコヒーレンシ状態及び前記項目の値によって個別に表される前記パス・インジケータに従って前記情報ユニットを前記相互接続スイッチを介して経路指定するためのコヒーレンシ状態マシンとを含み、
前記第１及び第２のプロセッサによって共用されている１つの情報ユニットに新しい値を書き込むための前記第１又は第２のプロセッサからのアクセス要求に応答するために、前記第１又は第２のアクセス・パス上にある相互接続部の前記コヒーレンシ状態マシンが、
前記第１又は第２のプロセッサが前記情報ユニットに前記新しい値を書き込めるように、当該情報ユニットに関連する前記コヒーレンシ状態及び前記パス・インジケータに従って当該情報ユニットの他のコピーを無効化するとともに、当該コヒーレンシ状態を前記グローバル共用状態から前記ローカル所有者状態に変更することにより、前記情報ユニットへの排他アクセスを獲得するための論理とを含むことを特徴とするシステム。
【請求項２】
相互接続部の各ポートに関連する前記項目が、単一ビットの値を保持することを特徴とする、請求項１に記載のシステム。
【請求項３】
階層ツリー構造の各レベルに同一構成の相互接続部を含むことを特徴とする、請求項１に記載のシステム。
【請求項４】
前記アクセス要求に関連する前記項目が前記コヒーレンシ・ディレクトリ内に存在せず且つ当該アクセス要求によって要求された情報ユニットが前記相互接続キャッシュ内に保持されていない場合、当該アクセス要求が前記グローバル・ポートにより他のレベルの相互接続部のローカル・ポートに経路指定されることを特徴とする、請求項１に記載のシステム。
【請求項５】
前記情報ユニットの他のコピーの無効化を完了する前に、前記情報ユニットへの排他アクセスが獲得されることを特徴とする、請求項１に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、各プロセッサが関連キャッシュを有するマルチプロセッシング・システムにおけるデータ処理に関する。より具体的には、本発明は、プロセッサが同じ相互接続部に直接結合されないように複数の相互接続部によってメモリに結合されたマルチプロセッシング・システムで使用するためのスケーリング可能なキャッシュ・コヒーレンシを維持するためのシステムに関する。
【０００２】
【従来の技術】
一般に、先行技術のキャッシュ・コヒーレンシ・プロトコルは、共用資源方法とディレクトリ・ベース・プロトコルに分類することができる。共用資源方法では、すべてのアドレス操作がシステム全体のキャッシュから見えることを保証することにより、コヒーレンシが維持される。これは、共用アドレス・バスを使用し、共用アドレス・バスに接続する下位レベルのキャッシュへの包含を要求することにより達成される。もう一方の手法は、システム全体に及ぶ情報の位置についてグローバルまたは分散いずれかのディレクトリを維持することである。
【０００３】
従来の共用メモリ・マルチプロセッシング・システムは、すべてのメモリ・コヒーレント要求側に対して単一の共用アドレス・バスを用いている。この手法の欠点は、システム・スループットがこの単一アドレス・バスによって制限されることである。他の共用メモリ・マルチプロセッサ・システムでは、単一レベルのスイッチを使用し、アドレス帯域幅に関する同様の制限がある。
【０００４】
ウィルソン・ジュニア（Wilson, Jr.）他に対して発行された米国特許第４７５５９３０号（「ウィルソン」）では、階層キャッシュ・メモリ・コヒーレンシに関する方法を開示しているが、キャッシュ・ライトスルーを使用しなければならない。すなわち、すべてのキャッシュ書込み操作は中央メモリ内の対応する位置を更新する。ウィルソン特許では、キャッシュ包含を要求し、且つすべてのキャッシュ書込みに対して中央メモリへのライトスルーを要求することにより、コヒーレンシを維持する。キャッシュ包含を要求するとキャッシュ空間の使用効率が悪くなり、ライトスルーを使用すると相互接続帯域幅の使用効率が悪くなる。したがって、包含またはライトスルーを要求しないコヒーレンシ方法の必要性が存在する。本発明はこのような必要性に対処するものである。
【０００５】
キャッシュ・コヒーレンシに対するディレクトリベースの手法に関する検討は、D.チャイケン（Chaiken）、C.フィールズ（Fields）、K.クリハラ（Kurihara）、A.アガルワル（Agarwal）による「Directory-Based Cache Coherence in Large-Scale Multiprocessors」（Computer Magazine、１９９０年６月）に記載されている。このような先行技術のディレクトリ方式は、全マップ・ディレクトリ、限定ディレクトリ、連鎖ディレクトリという３つのカテゴリに分類される。全マップ・ディレクトリは、キャッシュ・ラインがプロセッサによって保持されているかどうかを識別するためにすべてのプロセッサ用に１ビットずつ用意されているときに存在するものである。限定ディレクトリでは、限られた数のプロセッサが所与のキャッシュ・ラインを保持することができる。連鎖ディレクトリでは、所与のキャッシュ・ラインを保持するプロセッサの連係リストを使用する。プロセッサ毎のディレクトリ項目を必要とせず、キャッシュ済みコピーの数を限定せず、連係リスト・システムに関連する待ち時間または複雑さがない方法の必要性が存在する。本発明はこのような必要性に対処するものである。
【０００６】
ドナルドソン（Donaldson）他に対して発行された米国特許第５２９７２６９号では、中央メモリでグローバル全マップ・ディレクトリ方式を使用する、マルチプロセッサ・キャッシュ・コヒーレンシ・プロトコルを開示している。すべてのメモリ・アクセスは単一ディレクトリ内で探索を実行するはずである。このような単一ディレクトリ・システムに関する懸念の１つは、それがシステムのボトルネックを生む可能性があることである。単一ディレクトリの制限のない方法が望ましい。本発明はこのような必要性に対処するものである。
【０００７】
ベイラー（Baylor）他に対して発行された米国特許第５３１３６０９号では、グローバル・ディレクトリを使用するコヒーレンシ方法を開示している。これは、単一ディレクトリへのアクセスが限定されているという点で、ドナルドソン特許と同様の制限がある。また、単一グローバル・ディレクトリはシステムのスケーリングも妨げる。というのは、より大規模なシステムの場合、ディレクトリ・サイズとそのディレクトリへのアクセス・トラフィックを増加しなければならないからである。グローバル・ディレクトリを使用しない方法が望ましい。本発明はこのような必要性に対処するものである。
【０００８】
分散ディレクトリを使用すると、グローバル・ディレクトリに関連する制限の一部が回避される。全マップ分散ディレクトリ手法の一例は、D.レノスキ（Lenoski）、J.ラウドン（Laudon）、T.ジョー（Joe）、D.ナカヒラ（Nakahira）、L.ステーブンス（Stevens）、A.ガプタ（Gupta）、J.ヘネシー（Hennessy）による「The DASH Prototype: Logic Overhead and Performance」（IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 1、１９９３年１月（「レノスキ」））に記載されている。このシステムは、すべてのプロセッサ用の全ディレクトリを維持し、システム内のすべてのプロセッサ用としてキャッシュ・ライン当たり１つずつのディレクトリ・ビットを使用する。したがって、このシステムでは、各ディレクトリはキャッシュ・ラインの数にシステム内のプロセッサの数を掛けた数に等しい数のビット項目を有する。したがって、より小さいディレクトリ・サイズを使用し、各ディレクトリがシステム内のすべてのプロセッサ用の項目を必要としない、キャッシュ・コヒーレンシ・ディレクトリの必要性が存在する。本発明はこのような必要性に対処するものである。
【０００９】
ディレクトリが分散され、同じくキャッシュを含む階層スイッチ・エレメントに関連付けられている分散ディレクトリ・システムは、H.ミズラヒー（Mizrahi）、E.パエル（Baer）、J.ザボルジャン（Zahorjan）による「Extending the Memory Hierarchy into Multiprocessor Interconnection Networks: A Performance Analysis」（1989 International Conference on Parallel Processing（「ミズラヒー」））に開示されている。このシステムでは、キャッシュをツリー構造に配置し、それらをグローバル・メモリに接続する。システム内のディレクトリは、所望のキャッシュ済みコピーへのパスを提供するスイッチ・ポートを記録する。このシステムの制限は、一度にシステム内に存在することができるのは各メモリ位置の単一コピーだけであるという点である。したがって、コヒーレンシの実施の難しさが完全に回避される。この方式は実施するのは簡単であるが、読み取った情報を共用する必要がある場合にパフォーマンス上の問題が発生する可能性がある。各メモリ位置の単一コピーというこの制限を克服する方法が必要である。本発明はこのような必要性に対処するものである。
【００１０】
オムラン（Omran）およびアブーラビ（Aboelaze）は、ミズラヒーの研究を発展させ、スイッチ内にキャッシュおよびディレクトリを備えたマルチステージ・スイッチ・ネットワークについて記載している。R.オムラン（Omran）およびM.アブーラビ（Aboelaze）による「An Efficient Single Copy Cache Coherence Protocol for Multiprocessors with Multistage Interconnection Networks」（Proceedings of the 1994 Conference for Scalable High Performance Computing、１〜８ページ、１９９４年５月）を参照されたい。この技術も、キャッシュ・コヒーレンシ問題を防止するために単一コピー要件に依存している。システム内で可能なのは１つのコピーだけなので、様々なレベルのキャッシュでのキャッシュ包含は不要である。したがって、スイッチ・ベース・ネットワーク内で複数のコピーが可能であるが、各スイッチ・ディレクトリにおいてすべてのプロセッサ用の全ディレクトリを要求しないような、グローバル・ディレクトリを使用しないキャッシュ・コヒーレンシ・プロトコルの必要性が依然として存在する。本発明はこのような必要性に対処するものである。
【００１１】
マルチステージ相互接続ネットワーク用のコヒーレンス方法の最新技術に関する調査の概要は、オムランおよびリー（Lee）の文献にも記載されている。R.オムランおよびD.リーによる「A Multi-cache Coherence Scheme for Shuffle-Exchange Network based Multiprocessors」（Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation、１９９５年２月を参照されたい。記載されている技法としては全マップを含むが、これはシステム内の各キャッシュごとに１ビットずつ提供するものであり、スケーリング可能ではない。オムランおよびリーの文献には、マルチステージ相互接続ネットワーク内でディレクトリ方式を使用すると、膨大なコヒーレンス・トラフィックが発生し、より多くの競合および待ち時間の問題が発生すると記載されている。オムランおよびリーは、単一コピーのみが可能なシャッフル・ネットワーク・トポロジを提案している。単一コピーの制限がなく、このようなシステムで通常予想される大量のコヒーレンス・トラフィックが発生しない解決策が望ましい。本発明はこのような必要性に対処するものである。
【００１２】
【発明が解決しようとする課題】
本発明は、これまで述べてきたグローバル・ディレクトリおよび分散ディレクトリの問題点を解決する、キャッシュ・コヒーレンシを維持するためのコンピュータ・システムを提供する。
【００１３】
【課題を解決するための手段】
前述の必要性により、本発明は、大規模マルチプロセッシング・システムで使用するためのキャッシュ・コヒーレンス維持方法および装置に関する。本発明の特徴を有するシステムは複数の相互接続部からなる階層ツリーを含み、少なくとも２つの相互接続部はシステム・メモリ内の記憶域の各ラインごとに１つずつの経路指定レコードを備えたキャッシュ・コヒーレンシ・ディレクトリを有する。各経路指定レコードは、ポート毎に１つの項目を含み、当該ポートを通って到達するプロセッサがラインのコピーを保持しているかどうかを示す。通常、プロセッサまたは他の相互接続部のいずれかに接続する複数（Ｎ）のローカル・ポートと、他の相互接続部のローカル・ポートに接続されている１つのグローバル・ポートとが存在する。したがって、通常、最下位レベルには１つの相互接続部、次のレベルにはＮ個の相互接続部、その次のレベルにはＮ＊＊２個の相互接続部が存在する。プロセッサは、通常、最上位レベルの相互接続部に接続されるので、最上位レベルの相互接続部のポートに接続されたバスにＭ個のプロセッサを接続できる場合、Ｌ通りのレベルがあれば、最高Ｍ＊Ｎ＊＊Ｌ個のプロセッサを相互接続することができる。また、キャッシュは、通常、グローバル・ポートから出るトラフィックを低減するために相互接続部に関連付けられる。
【００１４】
本発明の特徴を有する、キャッシュ間で情報を共用するための方法は、システム・メモリと共用に関与するキャッシュとの間のパス上のスイッチ内のディレクトリでコピーの位置を示すことを含む。キャッシュは、排他コピーを獲得するとき、ディレクトリ内に格納されたパス情報を使用し、排他コピーに書き込むことができるように他のキャッシュ済みコピーのすべてを無効にする。このような特徴により、相互無効化トラフィックは、関与する共用メモリ・マルチプロセッシング・システムの領域に限定されるので有利であり、また、大規模共用メモリ・マルチプロセッシング・システムへのスケーラビリティも得られる。さらに、同じ相互接続構築ブロックを様々な相互接続レベルのすべてに使用できるので、システムを構築するために設計する必要があるチップの数が最小限になる。
【００１５】
【発明の実施の形態】
本発明は、複数の相互接続部を備えた共用メモリ・マルチプロセッサ・システムにおいてキャッシュ・コヒーレンシを維持するためのシステムおよび方法に関する。図１は、本発明の特徴を有するシステムのブロック図を示している。図示の通り、このシステムは、複数の相互接続部１−１〜１−３によりメモリ９に接続された複数のプロセッサ１３−１〜１３−８を含む。本発明は、各プロセッサ関連キャッシュごとに個別の項目を必要としない分散ディレクトリ・コヒーレンシ方式を使用するので、多数のプロセッサまでスケーリング可能である。
【００１６】
本発明によれば、個々のコヒーレンシ・ディレクトリ１１はシステム内の異なった相互接続部に関連付けられている。１つの相互接続部は、２つまたはそれ以上の外部相互接続ポート３、４、５間のトラフィックを経路指定するためにスイッチ、バス、リング、その他の手段を使用することができる。本発明では、各相互接続ポートごとに１つずつの項目を備え、メモリ・セグメントまたはキャッシュ・ラインを基礎として追跡される、メモリ９の全マップであるコヒーレンシ・ディレクトリ１１を使用する。説明のため、メモリ・セグメントまたはキャッシュ・ラインは情報ユニットと総称する。各ディレクトリ１１はメモリ９のローカル・ビューを提供し、全ディレクトリが集合するとメモリのグローバル・ビューを提供する。コヒーレンシ操作は、影響を受けないポート上での操作の流れを妨げずに影響を受けるポートにのみ向けることができるので有利である。本発明のこの特徴により、相互無効化トラフィックは、関与する共用メモリ・マルチプロセッシング・システムの領域に限定される。したがって、大規模共用メモリ・マルチプロセッシング・システムへのスケーラビリティも達成される。さらに、同じ相互接続構築ブロックを様々な相互接続レベルのすべてに使用することができる。たとえば、１−１、１−２、１−３は、同じ構成要素でよく、接続されたメモリのみが異なる（キャッシュまたはメイン・メモリとしての役割やサイズが異なる）。
【００１７】
本発明の特徴を有する相互接続部１のより詳細な例を図２に示す。相互接続部１は、接続されたポート間のトラフィックを経路指定し、頻繁にアクセスされる情報をキャッシュし、システム内のキャッシュ済みコピーの位置を示すコヒーレンシ・ディレクトリ１１を維持するという諸機能を実行する。システム内の相互接続部の全セットは相互接続ネットワークと呼ぶ。たとえば、図１では、相互接続部１−１〜１−３が相互接続ネットワークを構成する。従来通り、相互接続ネットワークによって経路指定されるトラフィックは、プロセッサおよびプロセッサ・キャッシュ用のデータおよび命令と、入出力操作と、１組のプロセッサ間で単一のメモリ・イメージを維持するために使用するコヒーレンシ・トランザクションとを含む。プロセッサ用のデータおよび命令は、プロセッサ、プロセッサ・キャッシュ、相互接続キャッシュ、メモリ間を移動する、読取りまたは書込みなどのメモリ・トランザクションを使用して相互接続ネットワーク内を移動する。プロセッサから発信される読取り要求は、要求された情報の状況を入手しその情報の位置を突き止めるために相互接続部内のディレクトリを使用して、相互接続ネットワークを横切る。
【００１８】
もう一度図２を参照すると、相互接続部１は、スイッチ、バスまたはその他の経路指定手段２（以下、スイッチで代表させる）と、外部ポート３、４、５と、メモリ・ポート６と、コヒーレンシ状態マシン１０と、任意のキャッシュまたはメモリ７とを含む。相互接続スイッチ２は、外部ポート３、４、５とメモリ・ポート６との間のトラフィックを経路指定することができる。本発明によれば、相互接続部１は、コヒーレンシ・ディレクトリ１１とコヒーレンシ状態マシン１０も含む。コヒーレンシ状態マシン１０（図３に関連して説明する）は、コヒーレンシ・ディレクトリ１１を維持し、コヒーレンシ操作を伝播することにより、システム内のコヒーレンシを保持する。コヒーレンシ・ディレクトリ１１は、システム内のキャッシュ済みコピーの位置を示すローカル情報を維持するために使用する。本発明の特徴を有するコヒーレンシ・ディレクトリ１１の一例は図４に示す。
【００１９】
相互接続部１のポートは、ローカル・ポート（Ｌポート）３と、グローバル・ポート（Ｇポート）４および５と、メモリ・ポート（Ｍポート）６とに分類することができる。図１に示すように、メモリ・ポート６は、任意選択の相互接続キャッシュ８またはメモリ９のいずれかを接続するために使用することができる。任意選択キャッシュは、相互接続レベルで頻繁に使用する情報のコピーを維持するために使用することができるので、アクセス待ち時間が最小限になる。ローカル・ポート３は、プロセッサ・モジュールを接続するか、または他の相互接続部を接続することにより、より大規模なトポロジを作成するために使用することができる。グローバル・ポート４および５は、ツリーの残りの部分に相互接続部を接続するか、またはルート相互接続部１−３に入出力デバイス１７を接続するために使用する。通常、相互接続部が要求を受け取り、情報の位置がローカルに把握されていない場合、その要求はグローバル・ポートから送出され、トポロジの大部分にその要求が知らされる。したがって、グローバル・ポートは各相互接続部のデフォルト経路指定ポートである。
【００２０】
従来通り、相互接続部上に追加のグローバル・ポートを代替グローバル・ポート５として設けることができる。任意選択の第２のグローバル・ポート５を図１および図２に示すが、実施態様によってはこのポートが存在しない場合もある。代替グローバル・ポート５により、フォールト・トレランスのためにツリー内に冗長度を構築することができる。相互接続部１内には複数の代替グローバル・ポート５が存在する場合もある。トラフィックは、一時に基本グローバル・ポート４または代替ポートの一方のみを通るか、あるいはグローバル・ポートの全セット間で分割することができる。
【００２１】
図４は、本発明の特徴を有するコヒーレンシ・ディレクトリ１１の一例を示している。コヒーレンシ・ディレクトリ１１は、システム内のキャッシュ済みコピーの位置を示すローカル情報を維持するためにコヒーレンシ状態マシン１０によって管理される。コヒーレンシ・ディレクトリ１１は、メモリ内の関連オフセット１８に位置する各情報ユニットごとにコヒーレンシ・レコード２１を１つずつ有し、そしてこのレコードは、相互接続部の各外部ポートごとに関連項目１９および２０を有する。各ローカル・ポート３ごとにＬ項目２０という項目が１つずつ存在し、グローバル・ポート４用としてＧ項目１９という１つの項目が存在する。代替グローバル・ポート５用として追加項目が存在する場合もある。通常、各項目は１ビットである。１つの項目がセットされると、関連ポートにより到達可能なプロセッサまたはデバイスによってその情報ユニットが使用中であることを示す。単一情報ユニットについて複数の項目がセットされている場合、その情報ユニットは複数の位置にキャッシュされている。
【００２２】
コヒーレンシ・ディレクトリ１１は、情報ユニットがキャッシュとメモリとの間で転送されるときに、転送操作およびコヒーレンシ操作時にたどるパスを示すために使用する。コヒーレンシ・ディレクトリ１１の各種項目は、個別にパス情報を示し、まとまると図３に示すコヒーレンシ状態マシン１０の状態を表す。コヒーレンシ状態マシン１０のインスタンスは、メモリの各情報ユニットごとに管理される。コヒーレンシ・ディレクトリ１１の各種項目は、図３に示す状態遷移図に応じて機能する。情報ユニットは、読取り操作への応答がたどるパスに留意し、図１に示すように相互接続リンク１２を介して他のコヒーレンシ情報を伝播するためにコヒーレンシ操作を使用することにより、システム全体においてキャッシュ間でコヒーレントな状態に維持される。
【００２３】
各種操作およびそれらが引き起こすコヒーレンシ状態マシンの遷移を図３に示す。概要として、読取り操作は、情報ユニットを共用するための要求（共用読取り）であって共用データ応答を受け取る要求か、または情報ユニットの排他読取りのための要求（排他読取り）であって排他データ応答を受け取る要求のいずれかにすることができる。コヒーレンス状態マシンの状態は読取り要求時には変更されないが、読取りへの応答時に変化する。無効化操作は、プロセッサが情報ユニットの排他所有権を獲得しようと試みたときにその情報ユニットの他のキャッシュ済みコピーを無効にするために伝播される。無効化操作が受け入れられ、完了したことを示すために、無効化操作への確認応答（ＡＣＫ）が必要になる。共用データ、排他データ、無効化の各操作によりコヒーレンシ状態マシン１０内で遷移が発生する。特定の状態マシン遷移はどのコヒーレンシ操作が伝播されるかを示す。
【００２４】
各情報ユニットに関連するコヒーレンシ・レコード２１はコヒーレンシ状態マシン１０に関する状態情報を提供し、項目値のすべての異なる組合せは、図３に示すように、非所有者状態、ローカル所有者状態、ローカル共用状態、グローバル共用状態という４通りの基本コヒーレンシ状態によって表すことができる。この４通りの状態により、キャッシュまたはメモリ階層全体でグローバル・コヒーレンシを維持することができる。
【００２５】
コヒーレンシ状態マシン１０の各種の状態と状態遷移との関係は図３に示す。状態マシンの説明では、任意選択の相互接続キャッシュ８内の情報ユニットの存在については明示的に説明しない。というのは、相互接続キャッシュ８は、それ自体のディレクトリを保持し、相互接続スイッチ２からのトラフィックをスヌープすることにより、それ自体のコヒーレンシを維持しているからである。
【００２６】
非所有者状態では、コヒーレンシ・ディレクトリ１１は情報ユニットのキャッシュ済みコピーに関する知識を一切持っていない。非所有者状態はシステム・コールド・スタート後に存在する初期状態である。非所有者状態は、すべてのＬ項目２０とＧ項目１９がセットされていないときに存在する。
【００２７】
ローカル所有者状態では、キャッシュ内に存在する情報ユニットのすべてのコピーが単一ローカル・ポートにより到達可能である。ローカル所有者状態では、セットされたＬ項目２０の総数は１になり、Ｇ項目１９はセットされない。ローカル所有者状態は、以下の状況のいずれかを示すことができる。すなわち、ａ）Ｌポートにより到達可能な単一キャッシュ内に非共用情報が存在すること、ｂ）Ｌポートにより到達可能な複数のキャッシュ内に共用情報が存在すること、ｃ）変更済み情報がＬポートにより到達可能であることである。
【００２８】
ローカル共用状態では、キャッシュ内に存在する情報ユニットのすべてのコピーが相互接続部のローカル・ポートにより到達可能であり、各種コピーのすべてに到達するには複数のローカル・ポートが必要になる。ローカル共用状態はセットされた複数のＬ項目２０とセットされていないＧ項目１９によって表される。ローカル共用状態は、セットされた関連Ｌ項目を備えたＬポートにより到達可能な１組のキャッシュによって情報が共用されることを示している。
【００２９】
グローバル共用状態では、情報ユニットの１つまたは複数のコピーがローカル・ポートにより到達可能であり、１つまたは複数のコピーがグローバル・ポートにより到達可能である。グローバル共用状態では、１つまたは複数のＬ項目２０がセットされ、Ｇ項目１９がセットされる。
【００３０】
本発明による方法について、図１のシステムを使用して説明する。情報ユニットがシステム内のいずれのプロセッサ１３−１・・・１３−８によってもアクセスされていない場合、それはシステム内の相互接続部１−１、１−２、１−３内のすべてのコヒーレンシ・ディレクトリ１１に非所有者状態で存在する。第１のプロセッサ１３−１が情報ユニットに関する初期読取り要求を実行すると、読取り要求はプロセッサ１３−１から介在相互接続部１−１および１−３を通ってメモリ９まで移動する。メモリ・ラインは、排他データ操作を使用して、排他データとしてプロセッサ１３−１と関連キャッシュ１４−１および１５−１に返される。排他データ操作が相互接続部１−３および１−１内の戻りパス上のＬポートを通過すると、相互接続部１−３および１−１内のディレクトリ状態はローカル所有者状態に遷移する。これにより、相互接続部１−３および１−１において、情報が存在するポートのＬ項目がセットされる。相互接続部１−２では、情報ユニットの状態は非所有者状態のままである。というのは、情報の位置がそれに通知されないからである。
【００３１】
第２のプロセッサ１３−８が共用読取り操作を使用して同じ情報を読み取って共用することを要求した場合、共用読取り要求は要求側プロセッサ１３−８から相互接続部１−２を通ってローカル所有者状態の情報ユニットを有する相互接続部１−３まで移動する。相互接続部１−３がローカル所有者状態になっていて、唯一のポートによって保持される情報に関して右端のＬポート上に共用読取り要求を受け取ると、相互接続部１−３はこの共用読取り要求を、現時点で排他状態の情報を所有し、同じ状態にとどまっている左端のＬポートに転送する。次にこの共用読取り要求は相互接続部１−１を通ってプロセッサ１３−１に関連するキャッシュ１４−１および１５−１まで移動し、そこで共用読取り要求を満足することができる。キャッシュが保持する情報は、変更されていてもいなくても構わない。いずれの場合もその情報は、ローカル・キャッシュ内で共用というマークが付けられ、共用データ操作を使用して元のパスに沿って第２のプロセッサ１３−８に返される。共用データ操作はＧポート上で相互接続部１−１を出るので、情報がＧポートにより到達するキャッシュと共用されることを認識するために、相互接続部１−１の状態はグローバル共用状態に変化する。相互接続部１−３では、共用データ操作が左端のＬポートから右端のＬポートまで移動し、その状態をローカル共用状態に遷移させる。相互接続部１−２はそのＧポート上で共用データ操作を受け取り、それを右端のＬポートに送信し、非所有者状態からグローバル共用状態への遷移を生じさせる。これで情報はプロセッサ１３−１および１３−８に関連するキャッシュによって共用され、相互接続部１−１、１−２、１−３は情報の共用を示す。
【００３２】
書込み操作を実行するプロセッサ（ここではもう１つのプロセッサ１３−５として示すが、第１のプロセッサ１３−１または第２のプロセッサ１３−８であってもよい）は、まず情報への排他アクセスを要求し、次に書込み操作を実行する。排他アクセスを獲得するプロセスについて以下に説明する。排他情報アクセスを要求するためにプロセッサ１３−５によって排他読取り操作が出される。排他読取り操作により、相互接続部１−２は情報の他のコピーを無効にするプロセスを開始し、それがキャッシュしている場合に情報を返すか、またはその情報を含むパス上で読取り操作を送信する。情報はグローバル共用状態になっているので、その情報のコピーはシステム内の他の場所にあり、無効化操作が相互接続部１−２のＧポートから相互接続部１−３の右端のＬポートへ伝播される。
【００３３】
相互接続部１−３は、無効化操作を受け取ると、それを受け取ったポート上に無効化ＡＣＫを出し、その情報を含む他のＬポート、この場合は左端のＬポート上に無効化操作を送出する。相互接続部１−３はこの情報を含むすべてのキャッシュのための共通相互接続部であるので、相互接続部１−３は、無効化要求の順序付けとアトミック性を保存することにより、早期に無効化を確認することができる。無効化コマンドの送信が完了すると、相互接続部１−３は相互接続部１−２に接続された右端のＬポート上に排他データを提示する。右端のＬポート上から排他データを送信すると、相互接続部１−３はグローバル共用からローカル所有者状態に遷移する。相互接続部１−２は、排他データをプロセッサ１３−５とその関連キャッシュ１４−５および１５−５に渡し、ローカル所有者状態に遷移する。相互接続部１−１は、無効化操作を受け取り、Ｌ項目が１にセットされたポートに無効化操作を渡し、非所有者状態に遷移する。
【００３４】
プロセッサ１３−５が無効化ＡＣＫを受け取ることは、そのプロセッサが排他状態の情報を有し、情報ユニットに書き込むことができることを示している。情報ユニットへの排他アクセスを獲得するプロセスは、無効化の伝播が完了したときに完了する。
【００３５】
この相互接続部を使用するトポロジ例を図５、図６、図７、図８に示す。図５は、相互接続部１−４〜１−９のレベル間の相互接続が２地点間リンク１２として構成されているマルチレベル階層ツリー・トポロジを示している。図５の相互接続部１−４〜１−９は、複数のプロセッサ・モジュール１３−９〜１３−１８を共用メモリ９および入出力デバイス１７に接続するために使用する。各プロセッサ・モジュールは、１つのプロセッサ（Ｐ）とその関連ローカル・キャッシュ（Ｃ１、Ｃ２）から構成される。各共用プロセッサ・バス１６に接続された１組のプロセッサ・モジュールはプロセッサ・グループと呼ぶ。プロセッサ・グループは相互接続ポート３に接続される。プロセッサは、相互接続ツリー内の下位レベルに接続することもできる（プロセッサ１３−１５〜１３−１８参照）。
【００３６】
図５のルート相互接続部１−９にはメモリ９と入出力デバイス１７とが接続されている。第２のレベルの相互接続部１−６、１−７、１−８はキャッシュ８を有し、ルート相互接続部１−９を上位レベルに接続している。第３のレベルの相互接続部１−４および１−５はキャッシュなしの状態で示されているが、このレベルでもキャッシュを接続することができる。相互接続部１−４〜１−９はシステム全体で諸機能および同じ汎用機構を共用するので、システム内のすべての相互接続部１−４〜１−９を実現するために同じコンポーネントまたはモジュールを使用することができる。各相互接続部が４つのローカル・ポートを有し、各プロセッサ・グループが４つのプロセッサを含むこのような３レベル構成は、最高２５６個のプロセッサをサポートすることができる。より多くの相互接続レベルを使用すると、より多くのプロセッサをサポートすることができる。
【００３７】
図５に示すように、相互接続部上の各種ポートは様々な方法で使用することができる。相互接続部１−８のローカル・ポートは、単一プロセッサ・バスを使用して単一プロセッサ・モジュール１３−１５〜１３−１８に接続された状態で示されている。相互接続部１−４のローカル・ポートは、共用バス１６により複数プロセッサ・モジュール１３−９〜１３−１２に接続された状態で示されている。図示の通り、相互接続部のグローバル・ポートは、他の相互接続部に接続するか、相互接続部が相互接続ツリーのルートにある場合には入出力デバイス１７またはプロセッサに直接接続することができる。メモリ・ポート６は、任意選択のキャッシュ８に接続するか、相互接続部が相互接続ツリーのルートであるときにメモリ９を接続するために使用することができる。
【００３８】
図６は、異なったレベルの相互接続部を接続するために共用バス１６を使用する、マルチレベル階層ツリー・トポロジを示している。異なったレベルの相互接続部間に共用バス１６を使用すると、ツリーは所与の数の相互接続レベルについてより多くのプロセッサをサポートすることができる。図６は、各組のキャッシュＣ１およびＣ２に１対のプロセッサ１３が接続されている、共用キャッシュの使用も示している。
【００３９】
図７は、相互接続部１−１３、１−１４、１−１５を単一リングで接続するためにツリー内で２地点間リンクを使用する、ツリー・トポロジのリングを示している。ツリーは、リング内にある相互接続部１−１３、１−１４、１−１５のそれぞれの上に存在することができる。システム・メモリ９は、図７に示すようにリング内の複数の相互接続部に接続するか、リング内の単一相互接続部にすべて接続することができる。
【００４０】
図８は、１組の相互接続部１を接続するために縦方向のリンクと横方向のリンクとを使用する、２次元メッシュ・ネットワークを示している。２次元メッシュ・ネットワークの場合、システム内のいずれの相互接続部１にもプロセッサを接続することができる。ローカルおよびグローバル・ポートの数を増加すると、次元数の多いメッシュを構築することができ、より多くのプロセッサを接続することができる。プロセッサは、そのメッシュのすべての相互接続部に接続するか、そのメッシュのエッジのみに接続することができる。システム・メモリ９と入出力デバイス１７は、図８に示すように、メッシュのエッジに沿って配置するか、メッシュの隅にある１つの相互接続部に接続することができる。
【００４１】
図示の通り、プロセッサをメモリに接続するために１組の相互接続部を使用する。相互接続部は、２地点間リンクまたは共用バスを使用する任意の相互接続ネットワーク・トポロジを使用して相互接続することができる。図５、図６、図７、図８は、相互接続部を使用して形成される可能なトポロジのうちの僅かな例だけを示している。
【００４２】
代替実施例とともに本発明の詳細な説明を示してきたが、当業者には様々な改良点が明らかになるだろう。したがって、詳細な説明は限定ではなく一例として解釈すべきである。本発明の範囲は特許請求の範囲によって適切に定義される。
【図面の簡単な説明】
【図１】本発明の特徴を有するシステムを示す図である。
【図２】図１の相互接続部の一例を示す図である。
【図３】図１のコヒーレンシ状態マシンの一例を示す図である。
【図４】図１のコヒーレンシ・ディレクトリの構造の一例を示す図である。
【図５】本発明の特徴を有する階層ツリー構成の一例を示す図である。
【図６】本発明の特徴を有する階層ツリー・トポロジの他の例を示す図である。
【図７】本発明の特徴を有するツリー・トポロジのリングの一例を示す図である。
【図８】本発明の特徴を有する２次元メッシュ・トポロジの一例を示す図である。
【符号の説明】
１  相互接続部
２  スイッチ（ＳＷ）
３  ローカル・ポート
４  グローバル・ポート
５  代替グローバル・ポート
６  メモリ・ポート
７  キャッシュまたはメモリ
８  相互接続キャッシュ
９  メモリ
１０  コヒーレンシ状態マシン
１１  コヒーレンシ・ディレクトリ
１３  プロセッサ
１７  入出力デバイス
【図１】
0003686221.tif 000002
【図２】
0003686221.tif 000003
【図３】
0003686221.tif 000004
【図４】
0003686221.tif 000005
【図５】
0003686221.tif 000006
【図６】
0003686221.tif 000007
【図７】
0003686221.tif 000008
【図８】
0003686221.tif 000009