(57)【要約】  本発明は、マルチノード・システムにおいてホーム・ノードで衝突を解決する分散キャッシュ・コヒーレンシ・プロトコルに関する。
2007535037.tif 000002
【特許請求の範囲】
【請求項１】
マルチノード・システムにおける第１ピア・ノードからデータ・ブロックのコピーの要求を複数のノードへ送信する段階と、
第２ピア・ノードから、データ・ブロックの前記コピーを前記第１ピア・ノードへおよび肯定応答をホーム・ノードへ、送信する段階と、
前記ホーム・ノードから完了メッセージを前記第１ピア・ノードへ送信し、前記要求に対する完了を前記第１ピア・ノードから示す段階と、
を含むことを特徴とする方法。
【請求項２】
データ・ブロックのコピーの要求を第１ピア・ノードから複数のノードへ送信する段階は、前記要求を前記第１ノードからインオーダ・ホーム・チャネルを経由して前記ホーム・ノードへ送信する段階を含むことを特徴とする請求項１記載の方法。
【請求項３】
前記第２ピア・ノードから前記第１ピア・ノードへ送られたデータ・ブロックの前記コピーは、データ・ブロックの排他的なコピーであることを特徴とする請求項１記載の方法。
【請求項４】
マルチノード・システムにおける第１ピア・ノードからデータ・ブロックのコピーの要求を複数のノードへ送信する段階と、
第２ピア・ノードから、データ・ブロックの前記コピーを前記第１ピア・ノードへおよび肯定応答をホーム・ノードへ、送信する段階と、
前記ホーム・ノードから完了メッセージを前記第１ピア・ノードへ送信し、前記要求に対する完了を前記第１ピア・ノードから示し、データ・ブロックの前記コピーに関連したキャッシュ・ラインの割り当てを解除する段階と、
を含むことを特徴とする方法。
【請求項５】
データ・ブロックのコピーの要求を第１ピア・ノードから複数のノードへ送信する段階は、前記要求を前記第１ノードからインオーダ・ホーム・チャネルを経由して前記ホーム・ノードへ送信する段階を含むことを特徴とする請求項４記載の方法。
【請求項６】
前記第２ピア・ノードから前記第１ピア・ノードへ送られたデータ・ブロックの前記コピーは、データ・ブロックの排他的なコピーであることを特徴とする請求項４記載の方法。
【請求項７】
ホーム・ノードに結合され、複数のピア・ノード間の衝突を前記ホーム・ノードによって解決することに少なくとも部分的に基づくキャッシュ・コヒーレンシ・プロトコルによって管理される複数のピア・ノードであって、前記ホーム・ノードは、下記条件、すなわち、
すべての複数の肯定応答メッセージが受け取られる、および
転送（Ｘｆｅｒ）メッセージまたはフォワード・メッセージが受け取られる、および
転送（Ｘｆｅｒ）メッセージが送られる、または、それが衝突チェーン中の最終メッセージである、が生じる場合、
衝突要求を退かせ、かつ衝突チェーンから衝突対象を取り除く、複数のピア・ノード、を含むことを特徴とするシステム。
【請求項８】
下記条件、すなわち、
すべての複数の肯定応答メッセージが受け取られる、および
すべての複数の衝突が発見される、および
前記チェーン内の複数の保留中の衝突が転送、または、ファワードのターゲットではない、および
転送（Ｘｆｅｒ）メッセージが送信され、または、それが前記衝突チェーン中の前記最後のメッセージである、が生じる場合、
衝突要求を退かせ、かつ衝突チェーンから衝突対象を取り除く前記ホーム・ノードをさらに含むことを特徴とする請求項７記載のシステム。
【請求項９】
前記衝突メッセージのみが、オリジナル・トランザクションのトランザクションＩＤを含むことを特徴とする請求項７記載のシステム。
【請求項１０】
前記衝突メッセージは、オリジナル・トランザクションのトランザクションＩＤおよび衝突トランザクションのトランザクションＩＤを含むことを特徴とする請求項７記載のシステム。
【請求項１１】
複数のピア・ノードに結合された少なくとも１つのソース・ノードであって、ホーム・ノードに結合された前記複数のピア・ノードは前記複数のピア・ノード間の衝突を前記ホーム・ノードによって解決することに少なくとも部分的に基づくキャッシュ・コヒーレンシ・プロトコルによって管理され、ソース・ノードは少なくとも１つのキャッシュ・ラインのコピーを要求し、前記ソース・ノードは、下記条件、すなわち、
前記キャッシュ・ラインがフォワード、排他的、または修正された状態のいずれか、少なくとも１つの衝突が検出され、および転送（Ｘｆｒ）メッセージなしに完了が受け取られる場合、が生じる場合、
データ肯定応答メッセージを表明する、少なくとも１つのソース・ノード、
を含むことを特徴とするシステム。
【請求項１２】
前記キャッシュ・コヒーレンシ・プロトコルは、衝突の間、衝突チェーン中のすべてのトランザクションがデータ肯定応答サイクルを開始することを促進させることを特徴とする請求項１１記載のシステム。
【請求項１３】
データ肯定応答サイクルは、Ｅ＿ＣＭＰ＿ＸＦＥＲメッセージをＥ＿ＣＭＰ＿Ｃｏｎｆｌｉｃｔメッセージに変更することを含むことを特徴とする請求項１２記載のシステム。
【請求項１４】
下記条件、すなわち、
すべての入来する要求がデータ肯定応答メッセージの表明とデータ肯定応答のための完了の受信との間でブロックされること、が生じる場合に、
データ肯定応答メッセージを表明する前記ソース・ノードをさらに含むことを特徴とする請求項１２記載のシステム。
【請求項１５】
マルチノード・システムにおける第１ピア・ノードからデータ・ブロックのコピーの要求を複数のノードへ送信する段階と、
第２ピア・ノードからメモリ（ライトバック・ライン）に書かれるべきデータ・ブロックの前記コピーの修正キャッシュ・ラインに対する要求をホーム・ノードへ送信する段階と、
前記第１ピア・ノードと第２ピア・ノードとの間のライトバックの競合衝突を前記ホーム・ノードで解決する段階と、
を含むことを特徴とするライトバック競合衝突を解決する方法。
【請求項１６】
前記第２ピア・ノードから前記ホーム・ノードへの前記ライトバック要求は、インオーダ・ホーム・チャネルを経由して送信されることを特徴とする請求項１５記載の方法。
【請求項１７】
前記第２ピア・ノードおよび第３ピア・ノードは、前記第１ノードの要求に応答してＩ＿ＡＣＫメッセージを生成することを特徴とする請求項１５記載の方法。
【請求項１８】
前記ライトバック競合衝突を解決する段階は、
メモリへの修正データのライトバックの完了を示す完了ＣＭＰメッセージで前記第２ピア・ノードに応答する段階と、
前記データ・ブロックの前記コピーを含み、かつ前記第１ピア・ノードからの前記要求の前記完了を示すＩ＿ＤＡＴＡ＿ＣＭＰメッセージで前記第１ピア・ノードに応答する段階と、によって、
前記ホーム・ノードが前記衝突を解決することを特徴とする請求項１５記載の方法。
【請求項１９】
２つの実質的に同時のオーナーシップに対する要求の競合衝突を解決する方法において、
マルチノード・システムにおける第１ピア・ノードからデータ・ブロックのコピーの要求を複数のノードへ送信する段階と、
マルチノード・システムにおける第２ピア・ノードからデータ・ブロックの前記同じコピーの要求を複数のノードへ送信する段階と、
前記第１ピア・ノードと第２ピア・ノードとの間の前記競合衝突を前記ホーム・ノードで解決する段階と、
を含むことを特徴とする方法。
【請求項２０】
前記第１および第２ピア・ノードから前記ホーム・ノードへの前記要求は、インオーダ・ホーム・チャネルを経由して送信されることを特徴とする請求項１９記載の方法。
【請求項２１】
前記競合衝突を解決する段階は、
前記第１および第２ピア・ノードからのＩ＿ＡＣＫ＿Ｃｏｎｆｌｉｃｔメッセージを前記ホーム・ノードで受け取り、前記要求されたキャッシュ・ラインに対して並存する要求があることを示す段階と、
第３ピア・ノードから前記第１ピア・ノードへＥ＿Ｄａｔａメッセージを送信し、前記第３ピア・ノードは前記要求されたデータの排他的なコピーを有すること、前記第３ピア・ノードは前記データの前記排他的なコピーを前記第１ピア・ノードへ転送すること、前記第３ピア・ノードはＥ＿ＡＣＫメッセージを前記ホーム・ノードへ送信し、前記要求されたデータの前記排他的なコピーを前記第１ピア・ノードへ転送したことを示す段階と、
前記データの前記排他的なコピーを前記第１ピア・ノードへ送信した後前記要求されたデータを無効にし、前記ホーム・ノードがＩ＿ＣＭＰメッセージを前記第２ピア・ノードへ送出することによって、およびＥ＿ＣＭＰ＿ＸＦＥＲ（ｓｅｃｏｎｄｎｏｄｅＩＤ）メッセージを前記第１ピア・ノードへ送出することによって前記競合衝突を解決することにより、前記第２ピア・ノードへの要求に応答して、前記第３ピア・ノードから前記ホーム・ノードへＩ＿ＡＣＫメッセージを送信する段階であって、前記Ｅ＿ＣＭＰ＿ＸＦＥＲ（ｓｅｃｏｎｄｎｏｄｅＩＤ）メッセージによって前記第１ピア・ノードが前記データの排他的なコピーを前記第２ピア・ノードに転送させる、段階と、によって
前記ホーム・ノードが前記衝突を解決することを特徴とする請求項１９記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ・メモリに関する。さらに詳しくは、本発明は、マルチキャッシュ・マルチプロセッサ・システム中に分散された競合の解消（conflict resolution）に関する。
【背景技術】
【０００２】
関連出願
本米国特許出願は、次の米国特許出願に関連する。
【０００３】
（１）「SPECULATIVE DISTRIBUTED CONFLICT RESOLUTION FOR A CACHE COHERENCY PROTOCOL（キャッシュ・コヒーレンシ・プロトコルのために推量的な分散型競合解消）」と題する２００３年に出願された出願番号１０／ＸＸＸ，ＸＸＸ（ドケット番号Ｐ１３９２３）。
【０００４】
電子システムが複数のキャッシュ・メモリを含む場合、使用可能なデータの妥当性が維持されなければならない。これは、典型的にはキャッシュ・コヒーレンシ・プロトコルに従ってデータを操作することにより達成される。キャッシュおよび／またはプロセッサの数が増加するにつれ、キャッシュのコヒーレンシ（一貫性）を維持する複雑さも増加する。
【０００５】
複数のコンポーネント（例えば、キャッシュ・メモリ、プロセッサ）が同じデータ・ブロックを要求するとき、複数のコンポーネント間の衝突は、データの妥当性を維持するような方法で解決されなければならない。現在のキャッシュ・コヒーレンシ・プロトコルは、典型的には競合解消（conflict resolution）に責任のある単一のコンポーネントを有する。しかしながら、システムの複雑さが増大するにつれ、競合解消のための単一コンポーネントに対する信頼は、システム性能全体に亘って減少する。
【０００６】
キャッシュ・コヒーレンス、スヌープ（しばしば対称型マルチプロセシングＳＭＰと称される）、およびディレクトリ（しばしば分散共同利用メモリＤＳＭと称される）を提供する２つの基本スキームがある。その基本的な差は、メタ情報、すなわちキャッシュ・ラインのコピーがどこに格納されるかに関する情報への配置とアクセスに関係する。
【０００７】
キャッシュをスヌープするために、キャッシュされたコピー自体で情報が配布される、すなわち、いずれかのノードが新しい方法でキャッシュ・ラインにアクセスするための許可を要求する場合はいつでも、キャッシュ・ラインの有効な各コピーは、その応答を認識しなければならないユニットによって保持される。いずれかの場所、通常は固定位置に、キャッシュに入れられていないときにデータが格納されるリポジトリ（repository）がある。そのラインがキャッシュに入れられるときさえ、この位置に有効なコピーが含んでいてもよい。しかしながら、このノードの位置は、一般に要求ノードに知られておらず、その要求ノードは、単に必要とされる許可と共に、要求されたキャッシュ・ラインのアドレスを同報するに過ぎず、また、コピーを有するすべてのノードは、もし他の（ピア）ノードが応答しない場合に応答するキャッシュされていないコピーを収容するノードと共に、一貫性が維持されることを保証するために応答しなければならない。
【０００８】
キャッシュされていないデータが格納される固定場所に加えて、ディレクトリに基づくスキームのために、キャッシュされたコピーがどこに存在するかを示す固定位置、ディレクトリがある。新しい方法でキャッシュ・ラインにアクセスするために、ノードはディレクトリを含むノードと通信しなければならない、それは通常キャッシュに入れられていないデータのリポジトリを含む同じノードである、したがって、主格納装置のコピーが有効なときに、その応答ノードがそのデータを提供することを可能にする。このようなノードはホーム・ノードと称される。
【０００９】
ディレクトリは、２つの方法で配布される。第１に、主格納装置のデータ（キャッシュに入れられていないリポジトリ）は、多くの場合ノード間で配布され、そのディレクトリは同じ方法で配布される。第２に、メタ情報それ自身は、できるだけ小さな情報をラインがキャッシュされるように維持してホーム・ノードで配布され、そうならば、ここに単一のコピーが存在する。例えば、ＳＣＩはこのスキームを使用し、キャッシュに入れられたコピーを収容する各ノードは、キャッシュに入れられたコピーを有する他のノードへのリンクを維持し、それにより、総体として完全なディレクトリを維持する。
【００１０】
スヌープ方式は、メタ情報が保持される単一の場所がないので、同報に依存する、したがって、すべてのノードは、各クエリー（照会）を通知されなければならず、各ノードはコヒーレンスが維持されることを保証するためにその役割を果たすために応答を受けることができる。これは、介入メッセージを含み、別のノードがデータを提供するとき、ホーム・ノードが応答しないように通知する。
【００１１】
スヌープ方式は、すべてのノードがすべてのクエリーを観察することを要求されるので、応答（レスポンス）が直接かつ迅速であるが、スケールしないという長所を有する。ディレクトリ方式は、本質的により大きくまたは小さくすることができるが、より複雑な応答を要求し、多くの場合ポイント間通信による３つのノードを含む。
【発明の開示】
【００１２】
マルチノード・システムにおける分散型キャッシュ・コヒーレンシの競合解消のための技術が説明される。以下の記述では、本説明の目的のために、多くの特定の詳細事項が本発明の完全な理解を提供するために述べられる。しかしながら、本発明はこれらの特定の詳細事項がなくても実施できることを当業者は理解するであろう。他の例では、本発明を不明瞭にしないようにするために、構造と装置をブロック図の形式で示す。
【００１３】
以下の議論は、マルチノード・システム内のノードの観点から提供される。ある実施例において、ノードは、内部キャッシュ・メモリ、外部キャッシュ・メモリおよび／または外部メモリを有するプロセッサを含む。別の実施例では、ノードは、他の電子システムと相互接続された電子システム（例えば、コンピュータ・システム、モバイル装置）である。他のタイプのノード構成が使用されてもよい。
【００１４】
以下の図中で描かれるホーム・ノードは、データを要求するホーム・ノードとして役立ち、それはホーム・ノードがキャッシュに入れられなかった場合に要求されたデータが格納される非キャッシュ・メモリ（例えば、メインメモリ）と関係しることを意味する。例えば、ホーム・ノードは、プロセッサ、キャッシュ・メモリおよびランダム・アクセス・メモリ（ＲＡＭ）であってもよく、そのＲＡＭはデータ用の非キャッシュの格納位置を提供する。
【００１５】
請求項記載の主題は、マルチノード・システムにおける分散型キャッシュ・コヒーレンシの競合解消を容易にする。ある実施例において、競合解消はホーム・ノードで解決される。ある側面では、請求項記載の主題は、ノード間で通信されるメッセージの数に関して競合解消プロトコルを効率的にする。例えば、ノードは、以下のように、ソース・ノード、ホーム・ノードおよびピア・ノードに分類される。請求項記載の主題は、ソース・ノードおよびホーム・ノードのためのプロトコルについて記述する。ある実施例において、請求項記載の主題は、関連出願に関して議論されるようなピア・ノード・プロトコルを利用してもよい。ソース・ノードのためのアルゴリズムは、図５に関して議論されるであろう。同様に、ホーム・ノードのためのアルゴリズムは、図６に関して議論されるであろう。
【００１６】
要求メッセージ
以下のメッセージは、要求ノードからのデータ／アクションの要求である。
【００１７】
ポート読取り無効ライン（ＰＲＩＬ）：これは、供給者ノードのデータのコピーが無効にされる場合、データ・セグメントのコピーを求める要求である。このメッセージも「オーナーシップの要求（request for ownership）」と称することができる。ある実施例において、ＰＲＩＬは、ホーム・ノードを含むすべてのノードに報知される。
【００１８】
ポート書込みライン（ＰＷＬ）：このメッセージによって、データ（例えば、修正済のキャッシュ・ライン）がメモリ、したがってライトバック・ラインに書き込まれる。このメッセージは、「ダーティ・エビクション（dirty eviction）」と称することができる。ある実施例において、ＰＷＬはホーム・ノードに送られる。
【００１９】
応答メッセージ
次のメッセージは、上述の要求に応答して、ピア（つまり、非ホーム）ノードから要求ノードへのメッセージである。
【００２０】
排他的データ（Ｅ＿ＤＡＴＡ）：このメッセージは、レスポンスを送るノードが要求されたデータの排他的なコピー（exclusive copy）を有する場合、要求（ＰＲＩＬ）に対するレスポンスである。ある実施例において、そのノードは、要求ノードへそのデータの排他的なコピーを転送する。
【００２１】
ホーム・ノードへのメッセージ
これらのメッセージは、ピア・ノードによってホーム・ノードへ送信される。
【００２２】
無効ステート肯定応答（Ｉ＿ＡＣＫ）：このメッセージは、レスポンスを送るノードが要求されたデータの無効コピーを有するか、要求されたデータのコピーを有さない場合、要求（ＰＲＩＬおよびＰＷＬ）に対するレスポンスである。
【００２３】
排他的ステート肯定応答（Ｅ＿ＡＣＫ）：このメッセージは、レスポンスを送るノードが要求されたデータの排他的なコピーを有するか、要求されたデータのコピーを有さない場合、要求（ＰＲＩＬおよびＰＷＬ）に対するレスポンスである。
【００２４】
データ受信肯定応答（ＤＡＣＫ）：このメッセージは、要求ノードによってホーム・ノードへ送信される。
【００２５】
Ｉ＿ＡＣＫ＿Ｃｏｎｆｌｉｃｔ：このメッセージは、要求されたキャッシュ・ラインに対して共存中の要求があることを示す。
【００２６】
ホーム・ノードからのメッセージ
これらのメッセージは、ホーム・ノードからピアおよび／または要求ノードへ送られる。
【００２７】
排他的完了（Ｅ＿ＣＭＰ）：このメッセージは、要求ノードが排他的データを受け取ったので、要求ノードの要求が完了したことを排他的キャッシュ・ステートで示す。ある実施例では、ホーム・ノードは、このメッセージを送出した後にラインの割り当てを解除する。
【００２８】
無効データ完了（Ｉ＿ＤＡＴＡ＿ＣＭＰ）：このメッセージは、要求ノードに送られるべき要求されたデータを含み、要求ノードのＰＲＩＬ要求が完了したことを「無効」キャッシュ・ステータスで示す。
【００２９】
完了（ＣＭＰ）−このメッセージは、メモリへ修正済データのライトバックを完了したことを示すためにＰＷＬを要求したノードに送られる。
【００３０】
Ｉ＿ＣＭＰ−このメッセージは、衝突したラインが割り当て解除されたことを示すために衝突状態にある２つのノードの１つに送信される。
【００３１】
ＸＦＥＲ＿（ＮｏｄｅＩＤ）：このメッセージによって、受信ノードはメッセージ中に示されたノードにデータを転送する。データの現在の所有者がそのデータをターゲット・ノードに転送することを要求するという衝突状態がホーム・ノードに通知される場合、ホーム・ノードは、要求されたデータの現在の所有者へこのメッセージを送る。未解決の衝突する要求がＰＲＩＬメッセージであるとホーム・ノードが判断する場合、データ転送を始めるとき現在の所有者がラインを無効にしなければならないことを意味して、ＸＦＲＩメッセージがＸＦＲメッセージの代わりに送信される。
【００３２】
Ｅ＿ＣＭＰ＿ＸＦＥＲ（ＮｏｄｅＩＤ）：Ｅ＿ＣＭＰ＿ＸＦＥＲは、Ｅ＿ＣＭＰおよびＸＦＥＲメッセージで作成される合成メッセージである。したがって、このメッセージは、このトランザクションがホーム・ノードで行われ、さらに受信ノードがメッセージ中で示されたノードにデータを転送させることを示す。データの現在の所有者がそのデータをターゲット・ノードに転送することを要求するという衝突状態がホーム・ノードに通知される場合、ホーム・ノードは、要求されたデータの現在の所有者へこのメッセージを送る。
【００３３】
これは、ホーム・ノードおよび要求ノードから、および、ホーム・ノードおよび要求ノードへのメッセージの議論が終了したことを示す。
【００３４】
以下の議論は、マルチノード・システム内のノードの観点から提供される。ある実施例において、ノードは、内部キャッシュ・メモリ、外部キャッシュ・メモリおよび／または外部メモリを有するプロセッサを含む。別の実施例では、ノードは、他の電子システムと相互接続された電子システム（例えば、コンピュータ・システム、モバイル装置）である。他のタイプのノード構成が使用されてもよい。以下の例において、メッセージに先行する数は、相対的な時間を示す。「１」で始まるメッセージは「１．１」または「２」あるいは「３」、で始まるメッセージの前に送信される。例えば、その数は、２つのノード間のラフな時間シーケンスを表示する。しかしながら、その数は、異なる対のノード間のタイミングを判断するために使用することができない。例えば、ノードＡとＢとの間の「４」は、ノードＣとＤとの間の「２」に先行する。点線を具備するメッセージは、インオーダ・ホーム・チャネル（in-order home channel）を示す。例えば、要求ノードからの第１のメッセージが同じ要求ノードからの第２のメッセージに先立って送られ、その順で受け取られること保証するために、インオーダ・ホーム・チャネルは、同じペアのノード間で同じ方向にある（第１のメッセージが受信ノードによって最初に受け取られ、そして、第２のメッセージが受信ノードによって続いて受け取られる）。
【００３５】
図１は、リード・トランザクションをサポートするためのプロトコルの一実施例を示す概念図を提供する。この実施例では、複数のノードＡ，Ｂ，Ｃは、ホーム・ノードＨに結合される。明らかに、請求項記載の主題は３つのノードに制限されるのではなく、異なる数のノードを考慮に入れる。
【００３６】
ある局面では、この図はリード・トランザクションを示す。まず、ノードの状態（ステート）は以下のとおりである。ノードＡ，Ｂは、データの無効なコピーを有している。対照的に、ノードＣは、データの排他的なコピーを有している（これはノードの第１ステートとして図中に示される（無効に対してはＩ、排他的に対してはＥ））。
【００３７】
最初に、要求ノードＡは、ＰＲＩＬ要求をノードＢ，Ｃおよびホーム・ノードへ送出する。ある実施例において、ＰＲＩＬ要求はインオーダ・ホーム・チャネルでホーム・ノードに伝えられる。
【００３８】
次に、ノードＣは、ノードＡのＰＲＩＬ要求に対してＥ＿ＤＡＴＡで応答し、排他的なデータのコピーを返す。同様に、ノードＣは、ホーム・ノードにＥ＿ＡＣＫで応答し、ノードＣが要求されたデータの排他的なコピーを転送したことを示す。一方、ノードＢは、要求されたデータの無効のコピーを有することを示すためにＩ＿ＡＣＫを転送する。
【００３９】
その結果、ホーム・ノードは、要求ノードが排他的データを受け取ったので、ノードＡの排他的データの要求が完了したことを示すために、Ｅ＿ＣＭＰをノードＡへ送出する。ある実施例において、ホーム・ノードは、このメッセージを出した後にラインの割り当てを解除する。したがって、ホーム・ノードは、他のノードからの受信メッセージに基づいて、リード・トランザクションを監督し制御する。
【００４０】
図２は、ライトバックの競合衝突（race conflict）をサポートするためのプロトコルの一実施例を示す概念図を提供する。この実施例では、複数のノードＡ，Ｂ，Ｃは、ホーム・ノードＨに結合される。明らかに、請求項記載の主題は３つのノードに制限されるのではなく、異なる数のノードを考慮に入れる。
【００４１】
ある局面では、この図はライトバック競合衝突を示す。まず、ノードの状態は以下のとおりである。ノードＡ，Ｂは、データの無効なコピーを有している。対照的に、ノードＣは、データの修正されたコピーを有している（これはノードの第１ステートとして図中に示される（無効に対してはＩ、修正に対してはＭ））。
【００４２】
最初に、要求ノードＡは、ＰＲＩＬ要求をノードＡ，Ｂおよびホーム・ノードへ送出する。ある実施例において、ＰＲＩＬ要求は、インオーダ・ホーム・チャネルでホーム・ノードに伝えられる。一方、ノードＣは、修正データをメモリへライトバックするためにＰＷＬ要求をホーム・ノードへ送出する。ある実施例において、ＰＲＩＬ要求は、インオーダ・ホーム・チャネルでホーム・ノードに伝えられる。したがって、ライトバック競合衝突は、ＣのＰＷＬ（ライトバック）要求と衝突する修正データに対するＡの要求により存在する。ある実施例において、ライトバックはホーム・チャネル上に送られ、ＡのＰＲＩＬ要求をノードＣでブロック（阻止）しない。
【００４３】
次に、ノードＣ，Ｂは、ＡのＰＲＩＬ要求に応答してＩ＿ＡＣＫメッセージを送出する。Ｉ＿ＡＣＫメッセージは、ＡのＰＲＩＬ要求に対する応答としてホーム・ノードに送られ、それらが要求されたデータの無効なコピーを有するか、要求されたデータのコピーを有しないことを示す。
【００４４】
ホーム・ノードは、衝突を解決するであろう。最初に、ホーム・ノードは、ノードＢ，ＣからのＩ＿ＡＣＫメッセージを受け取ると、ＣのＰＷＬ要求およびＡのＰＲＩＬ要求に応答する。ホーム・ノードは、ＣＭＰメッセージでノードＣへ応答し、修正データのメモリへのライトバックが完了したことを示す。さらに、ホーム・ノードは、要求されたデータを含み、かつノードＡのＰＲＩＬ要求が完了したことを示すＩ＿ＤＡＴＡ＿ＣＭＰメッセージでノードＡに応答する。
【００４５】
図３は、オーナーシップを要求する２つのリクエスト間の競合衝突をサポートするためのプロトコルの一実施例を示す概念図を提供する。例えば、ほぼ同時に送出する要求によって引き起こされる共有ラインの衝突をサポートするためのプロトコルを示す。最初に、ノードＡは、データ・ブロックを要求するＰＲＩＬメッセージをノードＢ，Ｃへおよびホーム・ノード２４０へ送信する。ある実施例において、ＰＲＩＬメッセージは、インオーダ・ホーム・チャネルを経由してホーム・ノードに送られる。ある短期間後に、または、同時でさえ、ノードＢは、ＰＲＩＬメッセージをノードＡ，Ｃへおよび同じデータ・ブロックを要求するホーム・ノードに送信する。ある実施例において、ＰＲＩＬメッセージは、インオーダ・ホーム・チャネルを経由してホーム・ノードに送られる。
【００４６】
現在、２つの競争するＰＲＩＬ要求、すなわち１つはノードＡからおよび１つはノードＢからとする。まず、この段落でＡのＰＲＩＬ要求に対する処理について説明し、次の段落でＢのＰＲＩＬ要求に対する処理が続く。ノードＡおよびノードＢの両方は、Ｉ＿ＡＣＫ＿Ｃｏｎｆｌｉｃｔメッセージをホーム・ノードに送り、要求されたキャッシュ・ラインに対する並存する要求があることを示す。
【００４７】
ＡのＰＲＩＬ要求について、ノードＣは、Ｅ＿ＤａｔａメッセージをノードＡのＰＲＩＬ要求に対する応答としてノードＡに送り、ノードＣが要求されたデータの排他的なコピーを有することを示す。さらに、ある実施例において、ノードＣは、そのデータの排他的なコピーをノードＡへ転送する。一方、ノードＣはＥ＿ＡＣＫメッセージをホーム・ノードに送り、それが要求されたデータの排他的なコピーを転送したことを示す。ある実施例において、Ｅ＿ＡＣＫメッセージは、インオーダ・ホーム・チャネルを経由してホーム・ノードに送られる。
【００４８】
ＢのＰＲＩＬ要求について、データの排他的なコピーをノードＡに送った後に要求されたデータが無効にされたので、ノードＣはＩ＿ＡＣＫをホーム・ノードに送る。
【００４９】
従って、ホーム・ノードは、Ｉ＿ＣＭＰメッセージをノードＢへ送出することにより、またＥ＿ＣＭＰ＿ＸＦＥＲ（Ｂ）メッセージをノードＡへ送出することにより並存するＰＲＩＬ要求を解決する。Ｅ＿ＣＭＰ＿ＸＦＥＲ（Ｂ）メッセージによって、受信ノードであるノードＡは、データの排他的なコピーをメッセージ中に示されたノードであるノードＢへ転送させる。データの現在の所有者がそのデータをターゲット・ノードへ、この例におけるノードＢへ転送することを要求する衝突状態がホーム・ノードに通知されると、ホーム・ノードは、要求されたデータの現在の所有者であるこの例におけるノードＡへこのメッセージを送る。
【００５０】
その結果、ノードＡは、Ｅ＿ＤＡＴＡメッセージをノードＢに送ることによりＥ＿ＣＭＰ＿ＸＦＥＲ（Ｂ）メッセージを受け取った後に、データの排他的なコピーをノードＢに転送する。
【００５１】
図４は、オーナーシップを要求する２つのリクエスト間の遅延衝突をサポートするためのプロトコルの一実施例を示す概念図を提供する。例えば、ノードＡはＰＲＩＬメッセージをノードＢ，Ｃおよびデータ・ブロックを要求するホーム・ノードに送信する。ノードＢがＡのＰＲＩＬ要求を肯定応答した後にＰＲＩＬ要求を送出する場合、遅延衝突が発生することがある。
【００５２】
最初に、要求ノードＡは、ＰＲＩＬ要求をノードＢ，Ｃおよびホーム・ノードに送出する。ある実施例において、ＰＲＩＬ要求は、インオーダ・ホーム・チャネルでホーム・ノードに伝えられる。
【００５３】
第２に、ノードＣが要求されたデータの排他的なコピーを転送したことを示すために、ノードＣは、ホーム・ノードへのＥ＿ＡＣＫでＡのＰＲＩＬに応答する。一方、ノードＢはＡのＰＲＩＬにＩ＿ＡＣＫで応答、それが要求されたデータの無効のコピーを有することを示す。
【００５４】
第３に、ノードＢは、ＰＲＩＬ要求をノードＢ，Ｃおよびホーム・ノードへ送出する。ある実施例において、ＰＲＩＬ要求はインオーダ・ホーム・チャネルでホーム・ノードに伝えられる。
【００５５】
第４に、ノードＣは、Ｅ＿ＤＡＴＡでＡのＰＲＩＬ要求に応答する。さらに、ノードＣは、ホーム・ノードへのＩ＿ＡｃｋメッセージでＢのＰＲＩＬに応答する。一方、ノードＡは、ホーム・ノードへのＩ＿Ａｃｋ＿ＣｏｎｆｌｉｃｔメッセージでＢのＰＲｌＬに応答する。
【００５６】
第５に、ホーム・ノードは、衝突があるという事実にもかかわらずノードＡにＥ＿ＣＭＰを送る。理想的には、衝突が検出されると、ＸＦＥＲメッセージはちょうど図３のようにＣＭＰで添付される。ホーム・ノードがＡのＰＲＩＬに対する応答のすべて集めるとき、衝突の指示がないので、このようなことは起こらない。衝突指示Ｉ＿Ａｃｋ＿Ｃｏｎｆｌｉｃｔ（ＢのＰＲＩＬに対するＡの応答）は、まだ伝送中で、ホーム・ノードによって受け取られていない。この場合、ノードＡは、ノードＡがラインの所有者であり、ホーム・ノードが衝突およびＸｆｅｒコマンドを送る必要性を見逃していることを示すために、ホーム・ノードからのＥ＿ＣＭＰを受け取るとＤＡＣＫメッセージをホーム・ノードに送る、なぜならＤＡＣＫはインオーダ・ホーム・チャネル上で送られ、それは、同じホーム・チャネル上で送られるそれに先立つＩ＿Ａｃｋ＿Ｃｏｎｆｌｉｃｔをプッシュするであろう。ある実施例において、ＤＡＣＫメッセージは、インオーダ・ホーム・チャネルでホーム・ノードに伝えられる。
【００５７】
従って、ホーム・ノードは、第１の受信ＤＡＣＫによって２つの要求者間の遅延衝突を解決し、次に、Ｉ＿ＣＭＰメッセージをノードＢへ、Ｘｆｅｒ（Ｂ）をノードＡ送出する。ＸＦＥＲ（Ｂ）メッセージによって、受信ノード、ノードＡ）は、データの排他的なコピーをメッセージ中に示されたノード、ノードＢに転送させる。ホーム・ノードは、ホーム・ノードにそのデータの現在の所有者がそのデータをターゲット・ノード、この例におけるノードＢへ転送することを要求する衝突条件が通知されると、このメッセージを要求されたデータの現在の所有者、この例におけるノードＡへ送る。その結果、そのホーム・ノードからＸｆｅｒ（Ｂ）メッセージを受け取ると、ノードＡは、データの排他的なコピーをＥ＿Ｄａｔａメッセージを備えるノードＢに送る。
【００５８】
図５は、ソース・ノード・アルゴリズムの方法のためのフローチャートの一実施例である。すでに議論されたように、ノードは次のように分類される。すなわち、ソース・ノード、ホーム・ノードおよびピア・ノードである。請求項記載の主題は、ソース・ノードで使用されるアルゴリズムについて記述する。ある実施例において、請求項記載の主題は、関連アプリケーションに関して議論されるようなピア・ノード・プロトコルを利用する。
【００５９】
図５は、ソース・ノード・アルゴリズムのための１つの方法を示す。例えば、下記条件は、Ｄａｃｋメッセージを主張することになる。
【００６０】
ある実施例において、Ｄａｃｋが要求するキャッシュ・ラインであると主張する１つの条件は、フォワード、排他的、あるいは修正のような予め定義された状態であり、少なくとも１つの衝突は検出され、また、完了が転送（Ｘｆｒメッセージ）なしに受け取られる。
【００６１】
別の実施例では、衝突中、衝突チェーン中のすべてのトランザクションは、ＤＡＣＫフェーズを経験するために要求されるように、本プロトコルは修正される。換言すれば、図３中のＥ＿ＣＭＰ＿ＸＦＥＲは、Ｅ＿ＣＭＰ＿Ｃｏｎｆｌｉｃｔに変更される。Ｅ＿ＣＭＰ＿Ｃｏｎｆｌｉｃｔ（衝突完了）を受け取ると、ノードＡは、ＤＡＣＫをホーム・ノードへ送出する。ホーム・ノードは、ＤＡＣＫを受け取った後にＸＦＥＲを送出する。衝突処理フローは比較的図３および図４に類似するので、これはハードウェア実行を単純化することができる。しかしながら、それは、すべての衝突のためにＤＡＣＫを利用し、競合解消を少し遅延させる。これは、通常衝突がまれであることによる問題ではない。
【００６２】
ある実施例において、すべての入来する要求は、ＤＡＣＫの主張と、ＤＡＣＫのためのＣＭＰの受信との間で阻止される。これによって、ホーム・ノードは衝突チェーンの終了が到達しているかどうかの決定を促進させることができる。
【００６３】
ある実施例において、ＤＡＣＫのためのＣＭＰまたはＸＦＥＲが受け取られるとき、阻止条件が取り除かれる。そのノードは、ピア・ノードのように振舞うであろう。
【００６４】
図６は、ホーム・ノード・アルゴリズムの方法のためのフローチャートの一実施例である。すでに議論されたように、ノードは次のように分類される。すなわち、ソース・ノード、ホーム・ノードおよびピア・ノードである。請求項記載の主題は、ソース・ノードおよびホーム・ノードで使用されるアルゴリズムについて記述する。ある実施例において、請求項記載の主題は、関連アプリケーションに関して議論されるようなピア・ノード・プロトコルを利用する。
【００６５】
図６は、ホーム・ノード・アルゴリズムのための１つの方法を示す。例えば、ホーム・ノード・アルゴリズムは、他のノード間の衝突を解決するために使用されてもよい。
【００６６】
例えば、ある実施例において、下記条件／イベントは、衝突を退かせるために使用される。ホーム・ノードは、次の場合、衝突要求を退かせて（終了させ）、衝突チェーンから衝突対象（conflictor）を取り除くであろう。すなわち、
すべての肯定応答メッセージが受け取られる、および、
Ｘｆｅｒまたはフォワード・メッセージが受け取られる、および、
Ｘｆｅｒが送られ、または、それが衝突チェーン中の最後のメッセージである。
【００６７】
さもなければ、別の実施例では、下記条件／イベントは衝突を退かせるために使用される。すなわち、
すべての肯定応答メッセージが受け取られる、および、
すべての衝突が発見される、および、
チェーン中の保留中の衝突が転送またはフォワードのための目標ではない、および、
Ｘｆｅｒが送られ、または、それが衝突チェーン中の最後のメッセージである。
【００６８】
また、ホーム・ノード・アルゴリズムは、衝突メッセージのフォーマットおよび記録を管理し決定する。例えば、ノードからの衝突メッセージは、オリジナル処理の処理ＩＤを含む。あるいは、別の実施例では、ノードからの衝突メッセージは、オリジナル処理の処理ＩＤおよび衝突処理の処理ＩＤを含んでもよい。２つの処理ＩＤは、衝突のリンク・リストを構築するために使用することができる。オリジナルおよび衝突処理ＩＤの両方が存在するので、衝突チェーンは両方の処理のそれぞれの記録エントリで記録できる。ちょうどＹＡＰ（特許番号―――）のように、このプロトコルは、伝送中の各処理を格納するための実質的な記録テーブルを要求する。要求がホーム・ノードに到着すると、それは、遅くて高価なアドレスＣＡＭを要求せずに、衝突をすべて見つけるために衝突チェーンを単に調べることができる。例えば、図２中のＣからホームへのＩ＿ＡＣｋは、Ｉ＿Ａｃｋ＿Ｃｏｎｆｌｉｃｔに最適化される。このＩ＿Ａｃｋ＿Ｃｏｎｆｌｉｃｔは、ＡのＰＲＩＬ処理ＩＤ（オリジナル）およびＰＷＬ処理ＩＤ（衝突対象）を有する。ＡのＰＲＩＬがホームに到着すると、遅くて高価なアドレスＣＡＭのサーチの代わりに、それは、ＰＷＬの記録エントリを見つけるために、Ｉ＿Ａｃｋ＿Ｃｏｎｆｌｉｃｔから記録されるＰＷＬの処理ＩＤを単に使用することができる。
【００６９】
分散型キャッシュ・コヒーレンシの競合解消をサポートするシステム例
図７は、ノードの一実施例のブロック図である。ノード７００は、単一のプロセッサ、キャッシュ・メモリ、メモリ制御器およびメモリで図示されるが、しかしながら、これらのいずれのコンポーネントもノード中に任意の個数で含めることができる。さらに、追加および／または異なるコンポーネント（例えば、バスブリッジ）をノードに含めることもできる。
【００７０】
プロセッサ７１０は、当技術分野で既知のあらゆるタイプのプロセッサでよい。ある実施例において、プロセッサ７１０は、キャッシュ・メモリ７２０を含む。別の実施例では、キャッシュ・メモリ７２０はプロセッサ７１０の外部にあってもよく、また、プロセッサ７１０の内部または外部に追加のキャッシュ・メモリは含めてもよい。
【００７１】
メモリ制御器７３０は、キャッシュ・メモリ７２０およびメモリ７４０に結合される。メモリ制御器７３０は、キャッシュ・メモリ７２０とメモリ７４０との間のインターフェイスとして動作する。ある実施例において、メモリ制御器７３０は、ここに記述されたキャッシュ・コヒーレンシ・プロトコルに従ってキャッシュ・コヒーレンシを維持する。メモリ制御器７３０は、ノード・リンク７５０を介して他のノードと相互に作用する。別の実施例では、プロセッサ７１０は、ここに記述されるようなキャッシュ・コヒーレンシを維持するためにメモリ制御器７３０と相互に作用し、また、プロセッサ７１０は、他のノード・リンク７５５を介して他のノードと相互に作用する。
【００７２】
ある実施例において、ノード・リンク７５０は、ノード７００が相互に作用する各ノードのための専用インターフェイスを含む。別の実施例では、ノード・リンク７５０は、ノード７００が相互に作用するノード数と異なるインターフェイスの数を含む。ある実施例において、ノード７００は、複数のノードを表わす１またはそれ以上のエージェントと相互に作用する。
【００７３】
図８は、マルチプロセッサ・システムの一実施例である。マルチプロセッサ・システム８００は、複数のプロセッサ、例えばコンピュータ・システム、リアルタイム監視システムなどを有する一連のシステムを表わすように意図される。他のマルチプロセッサ・システムは、より多くの、より限定した、および／または、異なるコンポーネントを含めることができる。ある状況では、ここに記述されたキャッシュ管理技術が単一プロセッサおよびマルチプロセッサ・システムに適用できる。マルチプロセッサ・システム８００は、マルチノード・システムとして動作するために形成することができる。
【００７４】
マルチプロセッサ・システム８００は、情報を交換するためにバス・システム８１０または他の通信装置を含む。バス・システム８１０は、あらゆる数のバスおよび関連する相互接続回路、例えば、バスブリッジを含めることができる。プロセッサ８２０は、情報を処理するためにバス・システム８１０に結合される。プロセッサ８２０は、キャッシュ・メモリ８２２、例えばレベル０（Ｌ０）のキャッシュ・メモリ、およびキャッシュ・コントローラ８２４を含めることができる。ある実施例において、プロセッサ８２０は、キャッシュ８２５と結合されてもよく、それはあらゆるタイプのキャッシュ・メモリでありえる。別の実施例では、キャッシュ８２５は、バス・システム８１０と結合される。他のタイプのプロセッサ−キャッシュ構成を使用することもできる。
【００７５】
ある実施例において、キャッシュ・コントローラ８２４は、例えばプロセッサ８２０に内部バスであるキャッシュ・メモリ・インターフェイス８２８を経由してキャッシュ・メモリ８２２に結合される。キャッシュ・コントローラは、プロセッサ８２０と外部キャッシュ・メモリとの間のインターフェイスを提供するキャッシュ・インターフェイス８２６を経由してキャッシュ・メモリ８２５に結合される。
【００７６】
マルチプロセッサ・システム８００は、キャッシュ・メモリ８３２およびキャッシュ・コントローラ８３４を備えるプロセッサ８３０をさらに含む。キャッシュ・コントローラ８３４は、キャッシュ・インターフェイス８３８を経由してキャッシュ・メモリ８３２に結合される。同様に、キャッシュ・コントローラ８３４は、キャッシュ・インターフェイス８３６を経由してキャッシュ・メモリ８３５に結合される。ある実施例において、キャッシュ・メモリ８３５は、プロセッサ８３０に結合される。
【００７７】
マルチプロセッサ・システム８００は２つのプロセッサで図示されているが、マルチプロセッサ・システム８００はあらゆる数のプロセッサおよび／またはコプロセッサを含めることができる。マルチプロセッサ・システム８００は、さらにバス・システム８１０に結合されたメモリ・システム８４０を含む。メモリ・システム８４０は、ダイナミック（例えば、ランダム・アクセス・メモリ）およびスタティック（例えば、リード・オンリ・メモリ、ＣＤ−ＲＯＭ、ディスク装置、フラッシュ・メモリ）メモリ装置の任意の組合せ、および関連する適切なドライブをさらに含むことができる。メモリ・システム８４０のメモリ装置は、マルチプロセッサ・システム８００のプロセッサによって実行される情報および命令を格納するために使用される。さらに、メモリ・システム８４０は、プロセッサによる命令実行中の一時変数または他の中間情報を格納するために使用することができる。
【００７８】
命令は、有線またはワイヤレスなどのいずれかのリモート接続を介して、磁気ディスク、リード・オンリ・メモリ（ＲＯＭ）集積回路、ＣＤ−ＲＯＭ、ＤＶＤのようなスタティックまたは遠隔格納装置から、メモリ・システム８４０に提供される。他の実施例では、ハードワイヤード回路は、ソフトウェア命令の代わりに、またはその命令と結合して使用することができる。このように、命令の実行シーケンスは、ハードウェア回路およびソフトウェア命令のあらゆる特定の組合せに制限されることはない。
【００７９】
マルチプロセッサ・システム８００は、ローカル・エリア・ネットワークおよび／またはインターネットのようなネットワークへのアクセスを提供するためのネットワーク・インターフェイス８５０をさらに含む。ネットワーク・インターフェイス８５０は、ワイヤレスおよび／または有線ネットワーク・インターフェイスを提供することができ、それは遠隔の電子的アクセス可能な媒体からまたはそれへの通信命令を含む。電子的アクセス可能な媒体は、電子装置（例えば、コンピュータ、個人用デジタル情報処理端末（携帯電話））によって読取ることのできる形式内の内容（例えば、コンピュータ実行可能な命令）を提供（つまり、格納および／または送信）するあらゆるメカニズムを含む。
【００８０】
例えば、マシンアクセス可能な媒体は、リード・オンリ・メモリ（ＲＯＭ）；ランダム・アクセス・メモリ（ＲＡＭ）；磁気ディスク格納装置媒体；光格納装置媒体；フラッシュ・メモリ装置；電気的、光学的、音響的あるいは他の形式の伝播信号（例えば、搬送波、赤外線信号、デジタル信号）を含む。
【００８１】
マルチプロセッサ・システム８００は、情報を表示するために陰極線管（ＣＲＴ）または液晶ディスプレイ（ＬＣＤ）のような表示装置８６０をさらに含めることができる。入力装置８７０は、例えば、英数字および他のキーを有するキーボードを含み、典型的にはプロセッサ８２０および／または８３０に情報と命令選択を伝えるバス８１０を結合される。別のタイプのユーザ入力装置は、プロセッサ８２０,８３０に指示情報および命令選択を伝え、さらに表示装置８６０上のカーソル移動を制御するマウス、トラックボール、または、カーソル指示キー、のようなカーソル制御装置である。
【００８２】
明細書中の「ある実施例」または「実施例」への参照は、本実施例に関して記述された特定の特徴、構造または特性が少なくとも本発明の一実施例に含まれることを意味する。本明細書中の様々な場所に現れる「ある実施例において」なる語句は、必ずしもすべてが同じ実施例を参照するものではない。
【００８３】
前述の明細書では、本発明がその特定の実施例に関連して記述された。しかしながら、様々な修正および変更は本発明のより広い思想および範囲から逸脱せずに成されるであろう。従って、明細書および図面は、限定的に意図する表現ではないと考えるべきである。
【図面の簡単な説明】
【００８４】
本発明は、実施例によって図示され、それは限定するものではなく、添付図面中同じ参照数字は類似の要素を参照する。
【図１】読取りトランザクションをサポートするためのプロトコルの一実施例を示す概念図を提供する。
【図２】ライトバック競合衝突をサポートするためのプロトコルの一実施例を示す概念図を提供する。
【図３】オーナーシップを要求する２つのリクエスト間の競合衝突をサポートするためのプロトコルの一実施例を示す概念図を提供する。
【図４】オーナーシップを要求する２つのリクエスト間の遅延衝突をサポートするためのプロトコルの一実施例を示す概念図を提供する。
【図５】ソース・ノード・アルゴリズムのためのフローチャートを示す一実施例である。
【図６】ホーム・ノード・アルゴリズムのためのフローチャートを示す一実施例である。
【図７】ノードの一実施例であるブロック図である。
【図８】マルチプロセッサ・システムの一実施例である。
【図１】
2007535037.tif 000003
【図２】
2007535037.tif 000004
【図３】
2007535037.tif 000005
【図４】
2007535037.tif 000006
【図５】
2007535037.tif 000007
【図６】
2007535037.tif 000008
【図７】
2007535037.tif 000009
【図８】
2007535037.tif 000010
【国際調査報告】
2007535037.tif 000011
2007535037.tif 000012
2007535037.tif 000013
2007535037.tif 000014