(57)【特許請求の範囲】
【請求項１】
相互接続に結合された少なくとも２つのノードを含み、前記少なくとも２つのノードがそれぞれローカル・システム・メモリ及びコヒーレンス・ディレクトリを含む、不均等メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムにおいて、キャッシュ・ラインのエントリを保持して疎ディレクトリを構成する前記コヒーレンス・ディレクトリにエヴィクション・プロトコルを提供するための方法であって、
キャッシュ・ラインのエントリを前記コヒーレンス・ディレクトリからエヴィクトするための要求に応答し、前記エントリが修正されたキャッシュ・ラインに関連付けられている場合に、前記修正されたキャッシュ・ラインのホーム・ノードから非介入書き戻し要求を前記修正されたキャッシュ・ラインを持つリモート・ノードに送信し、前記リモート・ノードにおいて非介入書き戻し要求を再発行している間に前記修正されたキャッシュ・ラインを書き戻すために前記リモート・ノードから前記ホーム・ノードに書き戻し要求を発行するステップと、
前記修正されたキャッシュ・ラインをホーム・ノードのローカル・システム・メモリに書き戻した後、前記エントリを前記コヒーレンス・ディレクトリからエヴィクトするステップと、を含み、
前記不均等メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムは、前記修正されたキャッシュ・ラインが前記ホーム・ノードのローカル・システム・メモリに書き戻されるまで、エヴィクトされるキャッシュ・ラインのアドレスを保持するエヴィクション・バッファを備えており、
前記非介入書き戻し要求は、前記修正されたキャッシュ・ラインを所有しているプロセッサに対して、ホーム・ノードで発行される予定の、メモリに対するトランザクションを強制的に生成させ、前記修正されたキャッシュ・ラインをホーム・ノードのローカル・システム・メモリに書き戻せるようにするものであり、前記修正されたキャッシュ・ラインが前記ホーム・ノードのシステム・メモリに書き戻されたことが保証された時点で完全に終了するまで試行を継続するAutoRetryを備えたものであることを特徴とする方法。
【請求項２】
前記非介入書き戻し要求が、前記修正されたキャッシュ・ラインが前記ホーム・ノードのシステム・メモリに書き戻されたことが保証された時点で完全に終了するまで試行を継続するAutoRetryを備えたものである、請求項１に記載の方法。
【請求項３】
前記非介入書き戻し要求が、非介入の修正を意図した読取りトランザクションである、請求項１に記載の方法。
【請求項４】
相互接続に結合された少なくとも２つのノードを含み、前記少なくとも２つのノードがそれぞれローカル・システム・メモリ及びコヒーレンス・ディレクトリを含み、キャッシュ・ラインのエントリを保持して疎ディレクトリを構成する前記コヒーレンス・ディレクトリにエヴィクション・プロトコルを提供する不均等メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムであって、
キャッシュ・ラインのエントリを前記コヒーレンス・ディレクトリからエヴィクトするための要求に応答し、前記エントリが修正されたキャッシュ・ラインに関連付けられている場合に、前記修正されたキャッシュ・ラインのホーム・ノードから非介入書き戻し要求を前記修正されたキャッシュ・ラインを持つリモート・ノードに送信し、前記リモート・ノードにおいて非介入書き戻し要求を再発行している間に前記修正されたキャッシュ・ラインを書き戻すために前記リモート・ノードから前記ホーム・ノードに書き戻し要求を発行する手段と、
前記修正されたキャッシュ・ラインをホーム・ノードのローカル・システム・メモリに書き戻した後、前記エントリを前記コヒーレンス・ディレクトリからエヴィクトする手段と、を含み、
前記不均等メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムは、前記修正されたキャッシュ・ラインが前記ホーム・ノードのローカル・システム・メモリに書き戻されるまで、エヴィクトされるキャッシュ・ラインのアドレスを保持するエヴィクション・バッファを備えており、
前記非介入書き戻し要求は、前記修正されたキャッシュ・ラインを所有しているプロセッサに対して、ホーム・ノードで発行される予定の、メモリに対するトランザクションを強制的に生成させ、前記修正されたキャッシュ・ラインをホーム・ノードのローカル・システム・メモリに書き戻せるようにするものであり、前記修正されたキャッシュ・ラインが前記ホーム・ノードのシステム・メモリに書き戻されたことが保証された時点で完全に終了するまで試行を継続するAutoRetryを備えたものであることを特徴とするＮＵＭＡコンピュータ・システム。
【請求項５】
前記非介入書き戻し要求は、前記修正されたキャッシュ・ラインが前記ホーム・ノードのシステム・メモリに書き戻されたことことが保証された時点で完全に終了するまで試行を継続するAutoRetryを備えたものである、請求項４に記載のＮＵＭＡコンピュータ・システム。
【請求項６】
前記非介入書き戻し要求が、非介入の修正を意図した読取りトランザクションである、請求項４に記載のＮＵＭＡコンピュータ・システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般にデータ処理の方法およびシステム、詳細には疎ディレクトリ用のエヴィクション・プロトコルを提供するための方法およびシステムに関する。さらに詳細には、本発明は、不均等メモリ・アクセス・コンピュータ・システムにおいて、疎ディレクトリからキャッシュ・ラインをエヴィクトするための方法およびシステムに関する。
【０００２】
【従来の技術】
多重プロセッサ（ＭＰ）コンピュータ・システムを形成するために、いくつかの個別プロセッサの処理能力を組み合わせることによって、より高いコンピュータ・システムの性能が達成できるということは、コンピュータ技術分野ではよく知られている。ＭＰコンピュータ・システムは、特定アプリケーションの性能要件に応じて、いくつかの異なるトポロジーで設計することができる。たとえば、対称的多重プロセッサ（ＳＭＰ）構成は、システム・メモリなどの資源が複数のプロセッサによって共用されており一般的に使用される、より単純なＭＰコンピュータ・システム・トポロジーの１つである。トポロジーの「対称的」という名前は、ＳＭＰコンピュータ・システム内のすべてのプロセッサが、システム内のすべての資源に対して対称的なアクセスを有するという事実に由来する。
【０００３】
ＳＭＰトポロジーは比較的単純なプロセッサ間通信およびデータ共用プロトコルを使用することができるが、ＳＭＰトポロジー全体で、特にシステムのスケールが大きくなるほどシステム・メモリ・レベルで、制限されたスケーラビリティおよび帯域幅を有する。その結果、ある程度複雑さが増すことを犠牲にし、ＳＰＭトポロジーの多くの制限を解決する代替設計として、不均等メモリ・アクセス（ＮＵＭＡ）として知られる別のＭＰコンピュータ・システム・トポロジーが出現した。
【０００４】
一般的なＮＵＭＡコンピュータ・システムは、いくつかの相互接続されたノードを含む。各ノードが少なくとも１つのプロセッサおよびローカル「システム」メモリを含む。ＮＵＭＡトポロジーという名前は、プロセッサが有するアクセス待ち時間が、そのローカル・ノードのシステム・メモリ内に保管されたデータに関する方が、リモート・ノードのシステム・メモリ内に保管されたデータに関するよりも少ないという事実に由来する。ＮＵＭＡコンピュータ・システムは、データ・コヒーレンスが異なるノードのキャッシュ間で維持されるか否かに応じて、非キャッシュ・コヒーレントまたはキャッシュ・コヒーレントのいずれかとしてさらに分類できる。ＮＵＭＡトポロジーは、ＮＵＭＡコンピュータ・システム内の各ノードを小規模なＳＭＰシステムとして実装することにより、従来のＳＭＰトポロジーが持つスケーラビリティの制限を解決している。したがって、各ノード内の共用構成要素は、ほんのわずかなプロセッサが使用するように最適化できる一方で、システム全体が比較的少ない待ち時間で大規模並列処理が使用可能となるという恩恵を受ける。
【０００５】
ＮＵＭＡコンピュータ・システムの疎ディレクトリに使用するエヴィクション・プロトコルの開発には、関連する問題がいくつかある。第１に、エヴィクトするために選択されるエントリの管理から発生する問題、第２に、エヴィクションを発生させるのに使用されるリモート・トランザクションの生成から発生する問題、そして第３に、ローカル・メモリに実際のデータの書き戻しを引き起こすトランザクションの生成から発生する問題である。
【０００６】
【発明が解決しようとする課題】
したがって、ＮＵＭＡコンピュータ・システムの疎ディレクトリからキャッシュ・ラインをエヴィクトするための改良された方法を提供することが望ましい。
【０００７】
【課題を解決するための手段】
本発明の方法およびシステムにより、ＮＵＭＡコンピュータ・システムは相互接続に結合された少なくとも２つのノードを含む。２つのノードはそれぞれ、ローカル・システム・メモリを含む。疎ディレクトリからのエントリをエヴィクトするための要求に応答して、エントリが修正されたキャッシュ・ラインに関連付けられている場合にその修正されたキャッシュ・ラインを有するノードに、非介入書き戻し要求が送信される。修正されたキャッシュ・ラインからのデータがノードのローカル・システム・メモリに書き戻しされた後、エントリを疎ディレクトリからエヴィクトすることができる。エントリが共用ラインに関連付けられると、表示されているディレクトリ・エントリがラインのコピーを保持できるすべてのノードに、無効化要求が送信される。すべての無効化が確認されると、エントリを疎ディレクトリからエヴィクトすることができる。
【０００８】
【発明の実施の形態】
Ｉ．ＮＵＭＡシステム
Ａ．システムの概要
ここで図面、特に図１を参照すると、本発明の好ましい実施形態による、不均等メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムの構成図が示されている。図の実施形態は、たとえば、ワークステーション、サーバ、またはメインフレーム・コンピュータとして実現することができる。図からわかるように、ＮＵＭＡコンピュータ・システム８は、ノード相互接続２２によって相互接続されたいくつか（Ｎ個）の処理ノード１０ａ〜１０ｄを含む。処理ノード１０ａ〜１０ｄは、それぞれ少なくとも１つ、最高Ｍ個までのプロセッサ１２を含む。プロセッサ１２ａ〜１２ｄは同一であり、米国ニューヨーク州アーモンクのインターナショナル・ビジネス・マシーンズ・コーポレイション（ＩＢＭ）から市販のPowerPCTMラインのプロセッサを備えることが好ましい。プロセッサ１２ａ〜１２ｄはそれぞれ、レジスタ、命令フロー論理、およびプログラム命令を実行するのに使用される実行ユニットに加えて、それぞれがレベル２（Ｌ２）キャッシュ１４ａ〜１４ｄと共に、システム・メモリ１８から関連するプロセッサ１２にデータをステージングする際に使用される、オンチップのレベル１（Ｌ１）キャッシュ（図示せず）を含む。つまり、Ｌ１キャッシュおよびＬ２キャッシュ１４ａ〜１４ｄは、関連するプロセッサ１２によってアクセスされることの多いデータを一時的にバッファする、システム・メモリ１８とプロセッサ１２との間の中間記憶装置として機能する。Ｌ２キャッシュ１４は一般にＬ１キャッシュよりも記憶域が大きいが、アクセス待ち時間は長くなる。たとえば、Ｌ２キャッシュ１４ａ〜１４ｄの記憶容量は１〜１６メガバイト（ＭＢ）であり、オンチップのＬ１キャッシュの記憶容量は８〜３２キロバイトである。Ｌ２キャッシュ１４ａ〜１４ｄは、図１ではプロセッサ１２の外部にあるものとして図示されているが、別法として、追加レベルのオンチップ・キャッシュ・メモリとして、関連するプロセッサ１２中に組み込むこともできることを理解されたい。さらに、追加のデータ記憶域を提供するために、１つまたは複数の追加レベルのキャッシュ・メモリ（Ｌ３、Ｌ４等）が使用できることも理解されたい。以下の考察では、プロセッサ１２およびその関連するキャッシュ階層（Ｌ１、Ｌ２等）が、それぞれ単一のスヌーパであるとみなされる。
【０００９】
図からわかるように、処理ノード１０ａ〜１０ｄはそれぞれ、システム・メモリ１８およびＬ２キャッシュ１４ａ〜１４ｄと共にローカル相互接続１６に結合されたノード制御装置２０をさらに含む。各ノード制御装置２０は、少なくとも２つの機能を実行することにより、リモート処理ノード１０に対するローカル・エージェントとして働く。第１に各ノード制御装置２０は、リモート処理ノード１０へのローカル通信トランザクションの伝送を容易にするために、関連するローカル相互接続１６をスヌープする。第２に、各ノード制御装置２０は、ノード相互接続２２上の通信トランザクションをスヌープし、関連するローカル相互接続１６上の関連する通信トランザクションのマスタとなる。各ローカル相互接続１６上での通信は、アービタ２４によって制御される。以下で詳述するように、アービタ２４は、プロセッサ１２により生成されたバス要求信号に基づいてローカル相互接続１６へのアクセスを規制し、ローカル相互接続１６上でスヌープされた通信トランザクションに関するコヒーレンス応答をコンパイルする。
【００１０】
もちろん、ＮＵＭＡコンピュータ・システム８は、追加装置をさらに含むことができる。これらの追加装置は、本発明を理解するのに必要でなく、したがって本発明を不明瞭にするのを避けるために省略される。たとえば各ノード１０は、入出力装置（たとえば、表示装置、キーボード、またはグラフィカル・ポインタ）、オペレーティング・システムおよびアプリケーション・ソフトウェアを格納するための不揮発性記憶装置、ならびにネットワークまたは付属装置に接続するためのシリアル・ポートおよびパラレル・ポートもサポートすることができる。
【００１１】
Ｂ．メモリ構成
ＮＵＭＡコンピュータ・システム８のすべてのプロセッサ１２は、単一の物理メモリ領域を共用しており、これは、各物理アドレスがいずれか１つのシステム・メモリ１８内で単一のロケーションのみに関連付けられていることを意味する。したがって、一般にＮＵＭＡコンピュータ・システム８内の任意のプロセッサ１２によるアクセスが可能なシステム・メモリ全体の内容を、４つのシステム・メモリ１８間で区分されているものと見なすことができる。たとえば、図１に示された本発明の例示的実施形態では、プロセッサ１２は、汎用メモリ領域および未使用領域の両方を含む、１６ギガバイトのアドレス領域をアドレス指定する。汎用メモリ領域は、５００メガバイトのセグメントに分割され、４つの各処理ノード１０が４番目ごとのセグメントに割り振られる。未使用領域はおよそ２ギガバイトを含むことが可能であり、システム制御、ならびにそれぞれがいずれか１つの各処理ノード１０に割り振られている周辺のメモリおよび入出力領域を含む。
【００１２】
この考察では、特定のデータをそのシステム・メモリ１８に格納する処理ノードを、そのデータのホーム・ノードと呼び、他の処理ノードを特定のデータに関するリモート・ノードと呼ぶ。
【００１３】
Ｃ．メモリのコヒーレンス
各システム・メモリ１８内に格納されたデータは、ＮＵＭＡコンピュータ・システム８内の任意のプロセッサ１２による要求、アクセス、および修正が可能であるため、ＮＵＭＡコンピュータ・システム８は、同じ処理ノード内のキャッシュ間および異なる処理ノード内のキャッシュ間の両方でコヒーレンスを維持するために、キャッシュ・コヒーレンス・プロトコルを実装する。したがって、ＮＵＭＡコンピュータ・システム８は、ＣＣ−ＮＵＭＡコンピュータ・システムとして分類するのが適切である。実装されるキャッシュ・コヒーレンス・プロトコルは実装依存型であり、たとえば周知の修正（Ｍ）、排他的（Ｅ）、共用（Ｓ）、無効（Ｉ）（ＭＥＳＩ）プロトコルまたはその変形を備えることができる。以下では、Ｌ１キャッシュ、Ｌ２キャッシュ１４、およびアービタ２４が従来のＭＥＳＩプロトコルを実装するが、そのノード制御装置２０はＭ、Ｓ、およびＩ状態を認識し、Ｅ状態は正確さのためにＭ状態にマージされるとみなされる。すなわちノード制御装置２０は、リモート・キャッシュによって排他的に保持されるデータが実際に修正されたかどうかにかかわらず、そのデータを修正されたと想定する。
【００１４】
Ｄ．相互接続アーキテクチャ
ローカル相互接続１６およびノード相互接続２２は、それぞれ任意のバス・ベースの同報通信アーキテクチャ、スイッチ・ベースの同報通信アーキテクチャ、またはスイッチ・ベースの非同報通信アーキテクチャを使って実装することができる。ただし、好ましい実施形態では、少なくともノード相互接続２２は、ＩＢＭコーポレイションによって開発された６ｘｘ通信プロトコルによって制御されるスイッチ・ベースの非同報通信相互接続として実装されている。ローカル相互接続１６およびノード相互接続２２では分割トランザクションが可能であるが、これはアドレスと通信トランザクションを備えたデータ保有期間との間に固定されたタイミング関係がなく、データ・パケットに対して関連するアドレス・パケットとは異なった命令を出すことができることを意味する。ローカル相互接続１６およびノード相互接続２２の使用度を、通信トランザクションのパイプライン化によって定めることも好ましい。そうすると、前の通信トランザクションのマスタが各受信者からのコヒーレンス応答を受け取る前に、後続の通信トランザクションがソースとなることが可能となる。
【００１５】
ノード相互接続２２を介した処理ノード１０間で、およびローカル相互接続１６を介したスヌーパ間で情報を搬送するために、実装される相互接続アーキテクチャのタイプにかかわらず、アドレス、データ、およびコヒーレンス応答という、少なくとも３タイプの「パケット」（ここで使用されるパケットとは、一般に情報の個別単位を指す）が使用される。ここで表１および表２を参照すると、アドレスおよびデータ・パケットに関する関連フィールドの要約および定義がそれぞれ与えてある。
【表１】
0003661764.tif 000002
【表２】
0003661764.tif 000003
【００１６】
表１および表２に示すように、受信者ノードまたはスヌーパが各パケットが属する通信トランザクションを判定できるようにするために、通信トランザクション内の各パケットはトランザクション・タグで識別される。追加のフロー制御論理および関連するフロー制御信号を使用して、有限の通信資源の使用が規制できることを、当業者であれば理解されよう。
【００１７】
各処理ノード１０内では、状態およびコヒーレンス応答が各スヌーパとローカル・アービタ２４との間で通信される。状態およびコヒーレンス通信に使用されるローカル相互接続１６内の信号ラインを、以下の表３にまとめて示す。
【表３】
0003661764.tif 000004
【００１８】
ローカル相互接続１６のARespラインおよびAStatラインを介して伝送される状態およびコヒーレンス応答は、関連するアドレス・パケットとの間に、固定されているがプログラム可能なタイミング関係を有することが好ましい。たとえば、ローカル相互接続１６上で伝送されるアドレス・パケットを各スヌーパが首尾よく受け取ったか否かに関する予備表示を与えるAStatOutボートが、アドレス・パケットを受け取った後の第２サイクルで要求される場合がある。アービタ２４は、AStatOutボートをコンパイルし、次いで、固定されているがプログラム可能な数のサイクル（たとえば１サイクル）後に、AStatInボートを発行する。可能なAStatボートを、以下の表４にまとめて示す。
【表４】
0003661764.tif 000005
【００１９】
AStatIn期間に続き、固定されているがプログラム可能な数のサイクル（たとえば２サイクル）後に、ARespOutボートが要求される場合がある。アービタ２４は、好ましくは次のサイクル中に、各スヌーパのARespOutボートをコンパイルしてARespInボートも送達する。可能なARespボートは、降順の優先順位でARespボートなどをリスト表示した、以下の表５にまとめて示すコヒーレンス応答を含むことが好ましい。
【表５】
0003661764.tif 000006
【００２０】
通常はノード制御装置２０によって発行されるReRun ARespボートは、スヌープされた要求が長い待ち時間を有し（たとえば、リモート処理ノード側のプロセッサ１２またはシステム・メモリ１８によって要求が提供される）、要求のソースが後でトランザクションを再発行するように命令されることを示す。したがって、Retry ARespボートとは対照的に、ReRunは、ReRunをボートしたトランザクションの受信者（トランザクションの発信者ではない）に、通信トランザクションを後で再発行させる義務を負わせる。
【００２１】
次に図２を参照すると、相互接続２２上のノード制御装置２０間で応答およびコマンドを通信する際に使用される、Ｉコマンドの例示的実施形態が示されている。図からわかるように、Ｉコマンド３６は、コマンド・タイプ・フィールド３３、ターゲット・ノード・フィールド３５、ソース・ノード・フィールド３７、トランザクション・タグ・フィールド３８、および有効（Ｖ）フィールド３９という、５つのフィールドを含む。コマンド・タイプ・フィールド３３は、Ｉコマンド３６のタイプの符号化表示を提供する。コマンド・タイプ・フィールド３３内で符号化できる可能なＩコマンドのいくつかを、以下の表６にまとめて示す。
【表６】
0003661764.tif 000007
【００２２】
各タイプのＩコマンドについて、受信者はターゲット・ノード・フィールド３５に指定され、送信側ノードはソース・ノード・フィールド３７に指定され、Ｉコマンドが関係するトランザクションはトランザクション・タグ・フィールド３８内に指定される。Ｉコマンド３６の妥当性は、有効（Ｖ）フィールド３９によって示される。
【００２３】
Ｅ．ノード制御装置
次に図３を参照すると、図１のＮＵＭＡコンピュータ・システム８のノード制御装置２０をより詳細に表した構成図が例示されている。図３からわかるように、ローカル相互接続１６とノード相互接続２２との間に結合されている各ノード制御装置２０は、トランザクション受信ユニット（ＴＲＵ）４０、トランザクション送信ユニット（ＴＳＵ）４２、データ受信ユニット（ＤＲＵ）４４、およびデータ送信ユニット（ＤＳＵ）４６を含む。ＴＲＵ４０、ＴＳＵ４２、ＤＲＵ４４、およびＤＳＵ４６は、たとえばフィールド・プログラム可能ゲート配列（ＦＰＧＡ）またはアプリケーション特有の集積回路（ＡＳＩＣ）を使って実装することができる。図に示すように、ノード・コントローラ２０を介したアドレス・パスおよびデータ・パスは、アドレス信号はＴＲＵ４０およびＴＳＵ４２で処理され、データ信号はＤＳＵ４４およびＤＲＵ４６で処理されるように、２つに分岐する。
【００２４】
ノード相互接続２２のトランザクション・フロー・オフを示すように指定されているＴＲＵ４０は、Ｉコマンド・チャネルを介して他のノードからＩコマンドを受信すること、ノード相互接続２２の共用アドレス・バスからトランザクションを受け入れること、ローカル相互接続１６上でトランザクションを発行すること、およびＴＳＵ４２に応答を転送することに対する責任を負っている。ＴＲＵ４０は、ノード相互接続２２からトランザクションを受信し、ＴＳＵ４２内のマスタ５４およびコヒーレンス応答論理５６の両方に選択したトランザクションを渡す、応答マルチプレクサ５２を含む。応答マルチプレクサ５２からの通信トランザクションの受信に応答して、バス・マスタ５４は、受信された通信トランザクションと同じか、またはエヴィクションなどディレクトリ保守のためにＴＳＵ内でディレクトリ制御用に生成される、そのローカル相互接続１６上での通信トランザクションを開始することができる。
【００２５】
ノード相互接続２２上でトランザクションを流すためのコンジットであるＴＳＵ４２は、その名称が示すように、ＴＲＵ４０と対話してメモリ要求トランザクションを処理し、ＤＲＵ４４およびＤＳＵ４６にコマンドを発行してローカル相互接続１６とノード相互接続２２との間のデータ伝送を制御する。ＴＳＵ４２はさらに、コヒーレンス応答論理５６を備えたノード相互接続２２のために選択した（すなわちＭＳＩ）コヒーレンス・プロトコルを実装し、ディレクトリ制御論理５８を備えたコヒーレンス・ディレクトリ５０を維持する。
【表７】
0003661764.tif 000008
【００２６】
コヒーレンス・ディレクトリ５０は、ローカル処理ノードがホーム・ノードであるリモート・ノード内でキャッシュに対して確認されたデータのシステム・メモリ・アドレスの表示（たとえばキャッシュ・ライン）を格納する。各データに関するこのアドレス表示は、こうした各リモート処理ノードでのデータのコピーおよびデータのコヒーレンス状態を有する、各リモート処理ノードの識別子に関連して格納される。コヒーレンス・ディレクトリ５０のエントリに関する可能なコヒーレンス状態を、表７にまとめて示す。表７に示すように、リモート処理ノードによって保持されるキャッシュ・ラインのコヒーレンス状態に関する知識は不正確である。この不正確さは、リモートに保持されたキャッシュ・ラインが、ホーム・ノードのノード制御装置２０に通知せずに、ＳからＩ、ＥからＩ、またはＥからＭへの移行を実行できるという事実による。
【００２７】
ＩＩ．疎ディレクトリのエヴィクションの概要
ここで図４を参照すると、本発明の好ましい実施形態による、ＮＵＭＡコンピュータ・システム内の疎ディレクトリ用のエヴィクション論理の構成図が示されている。図からわかるように、エヴィクション論理６０は、エヴィクション選択論理６１、エヴィクト生成論理６２、およびエヴィクション・バッファ６３の３つの構成要素を含む。エヴィクション選択論理６１は、（図３のコヒーレンス・ディレクトリ５０のような）コヒーレンス・ディレクトリ内にある現在のエントリの状態を利用して、エヴィクションに「最高の」選択を決定する。コヒーレンス・ディレクトリ内にあるすべてのエントリが保留状態にある場合、エヴィクション・ビジー・フラグが設定される。エヴィクション・ビジー・フラグが設定されると、コヒーレンス・ディレクトリで失敗し、コヒーレンス・ディレクトリにエントリを必要とするすべてのトランザクションは再試行される。エヴィクト生成論理６２は、エヴィクション用に選択されたエントリ（または候補）を受け入れ、エヴィクションを完了させるのに必要な正しい相互接続トランザクションを生成する。エヴィクションを完了させるのにどんな応答が必要であるかに関する情報を保持するのに加えて、エヴィクション・バッファ６３はエヴィクトされるメモリ・ラインのアドレスを保持する。エヴィクトされるメモリ・ライン用に新しい要求が受信されると、その要求は再試行される。エヴィクションがいったん完了すると、エントリはエヴィクション論理６０から削除される。コヒーレンス・ディレクトリは、メイン・コヒーレンス・ディレクトリ内にあるエントリが新しいエントリに更新されるまでは、エヴィクトされるエントリがアクセスされないことを保証する。
【００２８】
さらに、エヴィクト選択論理６１は、エヴィクションのためにコヒーレンス・ディレクトリからエントリを選択する場合に、優先順ランダム方式を使用する。優先順ランダム方式の優先順位は、コヒーレンス・ディレクトリの状態に基づいている。一般に共用エントリが第１に選択され、修正エントリがその次に選択されるが、保留されているエントリはエヴィクトできない。共用状態または修正状態のいずれかで同じ状態のエントリ・グループでは、エヴィクトするエントリを選択するのに連続カウンタが使用される。
【００２９】
次に図５を参照すると、本発明の好ましい実施形態による、疎ディレクトリ内でのエントリの構成図が示されている。図からわかるように、エントリ７０は、インデックス・フィールド７１、ビット・ベクトル・フィールド７２、および状態フィールド７３を含む。インデックス・フィールド７１は、キャッシュ・ラインのタグを格納する。ビット・ベクトル・フィールド７２は、どのノードがインデックス・フィールド７１を有するラインを含んでいるかを示す。ベクトル・フィールド７２内のサイズ（すなわちベクトル数）は、ＮＵＭＡコンピュータ・システム内のノード数に対応していなければならない。ビットＶｉとはノードｉを表している。状態フィールド７３は、インデックス・フィールド７１に格納されたタグを有するラインの状態を示す。
【００３０】
ＩＩＩ．疎ディレクトリのエヴィクション・プロトコル
共用エントリを無効にするために、エヴィクション論理６０は無効化トランザクションを生成するが、この例では、コヒーレンス・ディレクトリがその中に共用コピーが格納されている可能性があることを示す、ＮＵＭＡコンピュータ・システム内のすべてのノードに転送されるDClaimトランザクションである。トランザクションには、宛先ノードにある（図３のトランザクション受信ユニット４０のような）トランザクション受信ユニットを、トランザクションが消去応答で完了するまで継続してローカルで強制的に再試行させる、AutoRetryビットが設定されて発行される。トランザクションが完了すると、応答はエヴィクション・バッファ６３に返信される。エヴィクション・バッファ６３がすべてのDClaimトランザクションに関する確認を受信すると、エントリはエヴィクション・バッファ６３から削除される。この時点で、ラインは疎ディレクトリから削除されている。
【００３１】
ただし、修正エントリを無効にする場合、ローカル・メモリはエヴィクトされたデータがあれば受け入れる必要がある。これを実行するには、この例では修正を意図した読取り（Read-with-intent-to-modify）（ＲＷＩＴＭ）である、介入が禁止された無効化読取りとAutoRetryビットのセットが使用される。AutoRetryビットは、前述のDClaimトランザクションと同様に機能する。非介入モードは、データを所有しているプロセッサに対して、ホーム・ノードで発行される予定のメモリにトランザクションを強制的に生成させ、データをホーム・ノードのローカル・メモリに書き戻せるようにする必要がある。エヴィクション論理６０は、データがローカル・メモリに書き戻されるまで、エントリがエヴィクション・バッファ６３から消去されないことも保証しなければならない。非介入フラッシング要求を使用すると、所有しているプロセッサは、書き戻しトランザクションを生成し、システムはそれに適切な衝突検出規則を適用する。エヴィクション論理は、修正されたデータがホーム・ノードのシステム・メモリに書き戻されたことが保証された時点で完全に終了するまで、ＲＷＩＴＭ要求の試行を継続するためにだけ必要である。
【００３２】
たとえば、図６ないし図８に示すように、ホーム・ノード１０ａは、ラインがリモート・ノード１０ｂで修正状態に保持される可能性のある、ディレクトリ・エントリのエヴィクションを試行している。エヴィクション論理（図４から）は、図６に示すように、AutoRetryビットがアサートされ、介入可能ビットがアサートされていないＲＷＩＴＭトランザクション（すなわち非介入ＲＷＩＴＭトランザクション）を生成する。リモート・ノード１０ｂでＲＷＩＴＭトランザクションが発行されると、以下の３つのシナリオのうち１つが可能になる。第１のシナリオは、修正されたデータをシステム・メモリに戻そうとするとプロセッサが再試行を生成する以外の理由で、ＲＷＩＴＭトランザクションが再試行できるものである。このシナリオでは、AutoRetryモードが、トランザクション受信ユニットにＲＷＩＴＭトランザクションをノード１０ｂで強制的に再発行させる。第２のシナリオは、リモート・ノード１０ｂに修正されたキャッシュ・ラインがない可能性があり、ＲＷＩＴＭが消去応答を受信するというものである。ノード制御装置２０ｂの（図３のトランザクション受信ユニット４０のような）トランザクション受信ユニットは、その後エヴィクション論理に応答を返信し、エヴィクションが完了する。第３のシナリオは、キャッシュに修正されたキャッシュ・ラインがある可能性があり、介入が禁止されているので、プロセッサはＲＷＩＴＭを再試行した後、書き戻しキル（write-back-kill）（ＷＢＫ）要求で、データをローカル・メモリに戻そうとする。
【００３３】
次いでノード１０ｂのノード制御装置２０は、このトランザクションをリモート・メモリへの要求としてReRunする。その間、ノード制御装置２０ｂ内のトランザクション受信ユニットは、図７に示すようにエヴィクションＲＷＩＴＭトランザクションの再試行を継続するが、ノード制御装置２０ｂ内のトランザクション受信ユニットがＷＢＫトランザクションをReRunしたので、ノード制御装置２０ｂ内のトランザクション送信ユニットはエヴィクションＲＷＩＴＭトランザクションを再試行する。ホーム・ノード１０ａでＷＢＫ要求が完了し、データ転送が完了すると、ホーム・ノード１０ａは応答をリモート・ノード１０ｂに返信し、図８に示すように、ノード制御装置２０ｂ内のトランザクション送信ユニットにある保留バッファからＷＢＫ要求を消去する。ノード制御装置２０ｂ内のトランザクション送信ユニットがエヴィクション・トランザクションを再度発行しようとすると、所有しているプロセッサに修正されたキャッシュ・ラインがなくなるので、ノード制御装置２０ｂ内のトランザクション受信ユニットが消去応答を受信する。ノード制御装置２０ｂ内のトランザクション受信ユニットは、保留バッファを消去するノード１０ａ内のエヴィクション論理に応答を転送によって戻す。修正されたキャッシュ・ライン用のエントリを格納しているディレクトリ・エントリは、これでノードのコヒーレンス・ディレクトリから首尾よくエヴィクトされ、ローカル・メモリには有効なデータが格納される。
【００３４】
以上述べてきたように、本発明は、ＮＵＭＡコンピュータ・システム内で、疎ディレクトリにエヴィクション・プロトコルを提供するための方法を提供する。
【００３５】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００３６】
（１）相互接続に結合された少なくとも２つのノードを含み、前記少なくとも２つのノードがそれぞれローカル・システム・メモリを含む、不均等メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムにおいて、疎ディレクトリにエヴィクション・プロトコルを提供するための方法であって、
エントリを疎ディレクトリからエヴィクトするための要求に応答し、前記エントリが修正されたキャッシュ・ラインに関連付けられており、非介入書き戻し要求を前記修正されたキャッシュ・ラインを持たないノードに送信するステップと、
前記ノードのローカル・システム・メモリに書き戻しされた後、前記エントリを前記疎ディレクトリからエヴィクトするステップとを含む方法。
（２）前記非介入書き戻し要求が、AutoRetryを備えた非介入書き戻しである、上記（１）に記載の方法。
（３）前記非介入書き戻し要求が、非介入の読取りを意図した修正トランザクションである、上記（１）に記載の方法。
（４）相互接続に結合された少なくとも２つのノードを含み、前記少なくとも２つのノードがそれぞれローカル・システム・メモリを含む、疎ディレクトリにエヴィクション・プロトコルを提供できる不均等メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムであって、
エントリを疎ディレクトリからエヴィクトするための要求に応答し、ここで前記エントリが修正されたキャッシュ・ラインに関連付けられており、非介入書き戻し要求を前記修正されたキャッシュ・ラインを持つノードに送信する手段と、前記ノードのローカル・システム・メモリに書き戻しされた後、前記エントリを前記疎ディレクトリからエヴィクトする手段とを含むＮＵＭＡコンピュータ・システム。
（５）前記非介入書き戻し要求が、AutoRetryを備えた非介入書き戻しである、上記（４）に記載のＮＵＭＡコンピュータ・システム。
（６）前記非介入書き戻し要求が、非介入の読取りを意図した修正トランザクションである、上記（４）に記載のＮＵＭＡコンピュータ・システム。
【図面の簡単な説明】
【図１】本発明の好ましい実施形態による、不均等メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムの構成図である。
【図２】Ｉ−コマンドの例示的実施形態を示す図である。
【図３】図１に示されたノード制御装置のさらに詳細な構成図である。
【図４】本発明の好ましい実施形態による、疎ディレクトリに関するエヴィクション論理の構成図である。
【図５】本発明の好ましい実施形態による、疎ディレクトリ内にあるエントリの構成図である。
【図６】本発明の好ましい実施形態による、ＮＵＭＡコンピュータ・システムの疎ディレクトリからキャッシュ・ラインをエヴィクトするための方法を示す図である。
【図７】本発明の好ましい実施形態による、ＮＵＭＡコンピュータ・システムの疎ディレクトリからキャッシュ・ラインをエヴィクトするための方法を示す図である。
【図８】本発明の好ましい実施形態による、ＮＵＭＡコンピュータ・システムの疎ディレクトリからキャッシュ・ラインをエヴィクトするための方法を示す図である。
【符号の説明】
１０ａ  処理ノード
１０ｂ  処理ノード
１２ａ  プロセッサ
１６  ローカル相互接続
１８  メモリ
２０ａ  ノード制御装置
２０ｂ  ノード制御装置
２４  アービタ
【図１】
0003661764.tif 000009
【図２】
0003661764.tif 000010
【図３】
0003661764.tif 000011
【図４】
0003661764.tif 000012
【図５】
0003661764.tif 000013
【図６】
0003661764.tif 000014
【図７】
0003661764.tif 000015
【図８】
0003661764.tif 000016