(57)【特許請求の範囲】
【請求項１】
キャッシュコヒーレンスのための方法であって、
ローカルプロセッサ上にある複数のキャッシュのうちの第１のリクエスタキャッシュ（ＲＣ）のキャッシュエージェントによって、前記ローカルプロセッサの一方向性リングからなるリクエストネットワークを通して、キャッシュラインに対する第１のピアツーピア（Ｐ２Ｐ）リクエストを、前記ローカルプロセッサ上にある複数のキャッシュのうちの前記第１のＲＣとは異なるキャッシュである、複数のスレーブキャッシュの複数のキャッシュエージェントにブロードキャストすることと、
前記第１のＲＣの前記キャッシュエージェントによって、前記リクエストネットワークを通して、前記第１のＰ２Ｐリクエストがペンディングである間に、前記キャッシュラインに関連する転送リクエストを、前記ローカルプロセッサ上のローカルゲートウェイから受信することとを含み、
前記ローカルゲートウェイは、外部プロセッサ上の外部ゲートウェイに動作可能に接続されるとともに、前記外部ゲートウェイから転送されたプロセッサ間リクエストに応答して、前記転送リクエストを発行し、
前記第１のＲＣの前記キャッシュエージェントは、前記第１のＰ２Ｐリクエストがペンディングであることを理由に、前記転送リクエストに対する応答を遅延させ、さらに、
前記第１のＲＣの前記キャッシュエージェントによって、前記転送リクエストの受信後に、前記第１のＰ２Ｐリクエストに対する複数のレスポンスを、前記複数のスレーブキャッシュの前記複数のキャッシュエージェントから受信することと、
前記第１のＲＣの前記キャッシュエージェントによって、前記複数のレスポンスの受信後に、前記第１のＲＣ内の前記キャッシュラインのプロセッサ内状態を設定することとを含み、
前記プロセッサ内状態は、前記ローカルプロセッサおよび前記外部プロセッサに関連する前記キャッシュラインのプロセッサ間状態も特定し、さらに、
前記第１のＲＣの前記キャッシュエージェントによって、前記転送リクエストに対するレスポンスを、前記プロセッサ内状態の設定後かつ前記第１のＰ２Ｐリクエストの完了後に発行することと、
前記第１のＲＣの前記キャッシュエージェントによって、前記プロセッサ内状態を、前記転送リクエストに対する前記レスポンスの発行に応じて変更することとを含む、方法。
【請求項２】
前記ローカルゲートウェイによって、前記第１のＰ２Ｐリクエストを、前記リクエストネットワークを通して受信することと、
前記ローカルゲートウェイによって、前記第１のＰ２Ｐリクエストによって要求されるプロセッサ内状態の前記キャッシュラインを前記ローカルプロセッサが保持しているか否かを前記ローカルゲートウェイが判断できないことに応じて、前記キャッシュラインに対するプロセッサ間リクエストを発行することとをさらに含む、請求項１に記載の方法。
【請求項３】
前記ローカルゲートウェイによって、前記第１のＰ２Ｐリクエストを、前記リクエストネットワークを通して受信することと、
前記ローカルゲートウェイによって、前記キャッシュラインに対するゲートウェイタグにアクセスすることにより、前記ローカルプロセッサが前記キャッシュラインを保持していると判断することとをさらに含む、請求項１に記載の方法。
【請求項４】
前記ローカルゲートウェイによって、前記外部ゲートウェイから前記キャッシュラインを無効化するプロセッサ間リクエストを受信することと、
前記ローカルゲートウェイによって、前記第１のＰ２Ｐリクエストの受信前に、前記転送リクエストを、前記リクエストネットワーク上で、前記複数のスレーブキャッシュの前記複数のキャッシュエージェントおよび前記第１のＲＣの前記キャッシュエージェントに、ブロードキャストすることとをさらに含み、
前記転送リクエストは前記キャッシュラインを無効化するリクエストであり、さらに、
前記ローカルゲートウェイによって、前記第１のＰ２Ｐリクエストの受信後に、前記リクエストネットワーク上での前記転送リクエストのリターンを受信することと、
前記ローカルゲートウェイによって、前記第１のＰ２Ｐリクエストの失敗の予測誤りを防止するために、前記リクエストネットワーク上での前記転送リクエストのリターンの受信後に、前記ゲートウェイタグを無効化することとを含む、請求項３に記載の方法。
【請求項５】
前記ローカルプロセッサ上の第２のＲＣのキャッシュエージェントによって、前記キャッシュラインに対する第２のＰ２Ｐリクエストを、前記リクエストネットワークを通してブロードキャストすることと、
前記第２のＲＣの前記キャッシュエージェントによって、前記第２のＰ２Ｐリクエストの失敗を識別することと、
前記第２のＲＣの前記キャッシュエージェントによって、前記キャッシュラインに対する仲介リクエストを、前記第２のＰ２Ｐリクエストの失敗の識別に応じて、発行することとをさらに含み、
前記第２のＲＣの前記キャッシュエージェントは、前記第２のＲＣがプロセッサ内状態ＩＣの前記キャッシュラインを保持しているとき、前記第２のＲＣが前記第２のＰ２Ｐリクエストを前記仲介リクエストの発行前にブロードキャストしたので、前記キャッシュラインに対する前記仲介リクエストを発行することを許可され、前記仲介リクエストが完了するまで前記キャッシュラインに対する次のＰ２Ｐリクエストに否定応答し、さらに、
前記ローカルゲートウェイによって、前記仲介リクエストを受信したことに応じて、前記転送リクエストを前記リクエストネットワークを通して発行することを含む、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記第１のＲＣの前記キャッシュエージェントによって発行された前記転送リクエストに対するレスポンスは、前記第２のＲＣの前記キャッシュエージェントによって受信される、請求項５に記載の方法。
【請求項７】
前記第１のＰ２Ｐリクエストがペンディングである間に前記キャッシュラインに対するＰ２Ｐ読取アクセスリクエスト（ｐＲＴＳ）を前記第１のリクエスタキャッシュの前記キャッシュエージェントが受信したことに応じて、前記第１のＰ２Ｐリクエストが失敗であるとみなすことをさらに含み、前記第１のＰ２Ｐリクエストは、前記キャッシュラインに対する読取−書込アクセスリクエスト（ｐＲＴＯ）である、請求項１〜６のいずれか１項に記載の方法。
【請求項８】
キャッシュコヒーレンスのための方法であって、
ローカルプロセッサ上にある複数のキャッシュのうちの追い出しキャッシュ（ＥＣ）のキャッシュエージェントによって、ローカルプロセッサ上の一方向性リングからなるリクエストネットワークを通して、キャッシュラインに対するピアツーピア（Ｐ２Ｐ）ライトバックリクエストを、前記ローカルプロセッサ上にある複数のキャッシュのうちの前記ＥＣとは異なるキャッシュである、複数のスレーブキャッシュの複数のキャッシュエージェントにブロードキャストすることと、
前記ＥＣの前記キャッシュエージェントによって、前記リクエストネットワークを通して、前記Ｐ２Ｐライトバックリクエストがペンディングである間に、前記キャッシュラインに対する第１の転送リクエストを、前記ローカルプロセッサ上のローカルゲートウェイから受信することとを含み、
前記ローカルゲートウェイは、外部プロセッサ上の外部ゲートウェイに動作可能に接続されるとともに、前記外部ゲートウェイから転送されたプロセッサ間リクエストに応答して、前記第１の転送リクエストを発行し、
前記ＥＣの前記キャッシュエージェントは、前記Ｐ２Ｐライトバックリクエストがペンディングである間、前記第１の転送リクエストに対する応答を遅延させて、前記ローカルプロセッサ上で前記キャッシュラインに対して１つのＰ２Ｐライトバックリクエストのみがアクティブであることを保証し、さらに、
前記ＥＣの前記キャッシュエージェントによって、複数のレスポンスを前記複数のスレーブキャッシュの前記キャッシュエージェントから受信することと、
前記ＥＣの前記キャッシュエージェントによって、前記第１の転送リクエストに対するレスポンスを、前記複数のレスポンスを前記複数のスレーブキャッシュの前記キャッシュエージェントから受信した後、かつ、前記Ｐ２Ｐライトバックリクエストが完了した後に、発行することと、
前記ＥＣの前記キャッシュエージェントによって、前記第１の転送リクエストに対するレスポンスを発行した後に、複数のレスポンスを前記複数のスレーブキャッシュの前記キャッシュエージェントに対して発行することとを含む、方法。
【請求項９】
前記第１の転送リクエストは無効化リクエストであり、前記複数のスレーブキャッシュの前記キャッシュエージェントに対する前記複数のレスポンスはすべて否定応答（Ｎａｃｋ）である、請求項８に記載の方法。
【請求項１０】
前記ＥＣの前記キャッシュエージェントによって、前記複数のスレーブキャッシュの前記キャッシュエージェントからの前記複数のレスポンスの中の、第１のスレーブキャッシュからのプルライトバック（ＰｕｌｌＷＢ）を識別することをさらに含む、請求項８または９に記載の方法。
【請求項１１】
前記ＥＣの前記キャッシュエージェントによって、前記複数のスレーブキャッシュの前記キャッシュエージェントからの前記複数のレスポンスの中の、第２のスレーブキャッシュからの確認応答ライトバック（ＡｃｋＷＢ）を識別することをさらに含み、
前記複数のスレーブキャッシュの前記キャッシュエージェントに対する前記複数のレスポンスは、
前記ＥＣ内の前記キャッシュラインのプロセッサ内状態に基づく前記第２のスレーブキャッシュのキャッシュエージェントに対する一種の確認応答と、
前記第１のスレーブキャッシュのキャッシュエージェントに対する否定応答（Ｎａｃｋ）とを含む、請求項１０に記載の方法。
【請求項１２】
前記複数のスレーブキャッシュの前記キャッシュエージェントに対する前記複数のレスポンスは、前記第１のスレーブキャッシュのキャッシュエージェントに対する前記ＥＣ内の前記キャッシュラインのプロセッサ間状態に基づくキャッシュラインを含む、請求項１０または１１に記載の方法。
【請求項１３】
前記複数のスレーブキャッシュのうちのスレーブキャッシュのキャッシュエージェントによって、前記Ｐ２Ｐライトバックリクエストを、前記リクエストネットワークを通して受信することと、
前記スレーブキャッシュのキャッシュエージェントによって、前記スレーブキャッシュ内の前記キャッシュラインのプロセッサ内状態に基づいて、前記Ｐ２Ｐライトバックリクエストに対する確認応答ライトバック（ＡｃｋＷＢ）を、前記リクエストネットワークを通して発行することと、
前記スレーブキャッシュのキャッシュエージェントによって、前記リクエストネットワークを通して、前記ＡｃｋＷＢがペンディングである間に前記第１の転送リクエストを受信することとをさらに含み、
前記スレーブキャッシュの前記キャッシュエージェントは、前記ＡｃｋＷＢがペンディングである間前記第１の転送リクエストに対する応答を遅延させ、さらに、
前記スレーブキャッシュの前記キャッシュエージェントによって、前記第１の転送リクエストの受信後に、一種の確認応答を前記ＥＣの前記キャッシュエージェントから受信することと、
前記スレーブキャッシュの前記キャッシュエージェントによって、前記確認応答の種類に基づいて、前記スレーブキャッシュ内の前記キャッシュラインのプロセッサ内状態をアップデートすることと、
前記スレーブキャッシュの前記キャッシュエージェントによって、前記プロセッサ内状態のアップデート後、かつＡｃｋＷＢの完了後に、前記第１の転送リクエストに対して応答することとを含む、請求項８〜１２のいずれか１項に記載の方法。
【請求項１４】
前記複数のスレーブキャッシュのうちのスレーブキャッシュのキャッシュエージェントによって、前記Ｐ２Ｐライトバックリクエストを、前記リクエストネットワークを通して受信することと、
前記スレーブキャッシュの前記キャッシュエージェントによって、前記スレーブキャッシュ内の前記キャッシュラインのプロセッサ内状態に基づいて、前記Ｐ２Ｐライトバックリクエストに対するプルライトバック（ＰｕｌｌＷＢ）を、前記リクエストネットワークを通して発行することと、
前記スレーブキャッシュの前記キャッシュエージェントによって、前記ＰｕｌｌＷＢがペンディングである間に、前記キャッシュラインに対する第２の転送リクエストを、前記リクエストネットワークを通して受信することとをさらに含み、前記第２の転送リクエストは前記ローカルゲートウェイからのものであり、
前記スレーブキャッシュの前記キャッシュエージェントは、前記ＰｕｌｌＷＢがペンディングであることを理由に、前記第２の転送リクエストに対する応答を遅延させ、さらに、
前記スレーブキャッシュの前記キャッシュエージェントによって、前記第２の転送リクエストの受信後、前記ＥＣの前記キャッシュエージェントから前記キャッシュラインを受信することと、
前記スレーブキャッシュの前記キャッシュエージェントによって、前記スレーブキャッシュ内の前記ＥＣの前記キャッシュエージェントからの前記キャッシュラインをインストールすることと、
前記スレーブキャッシュの前記キャッシュエージェントによって、前記キャッシュラインのインストール後に、前記第２の転送リクエストに対して応答することとを含む、請求項８〜１２のいずれか１項に記載の方法。
【請求項１５】
キャッシュコヒーレンスのためのシステムであって、
外部プロセッサと、
ローカルプロセッサとを備え、前記ローカルプロセッサは、
前記外部プロセッサ上の外部ゲートウェイに動作可能に接続されたローカルゲートウェイと、
複数のキャッシュのうちの複数のローカルスレーブキャッシュの複数のキャッシュエージェントと、
前記複数のローカルスレーブキャッシュの前記複数のキャッシュエージェントを動作可能に接続する一方向性リングからなる第１のリクエストネットワークと、
前記複数のキャッシュのうちの前記複数のローカルスレーブキャッシュとは異なるキャッシュである、リクエスタキャッシュ（ＲＣ）のキャッシュエージェントとを含み、前記リクエスタキャッシュのキャッシュエージェントは、
第１のキャッシュラインに対するピアツーピア（Ｐ２Ｐ）リクエストを、前記第１のリクエストネットワークを通して、前記複数のローカルスレーブキャッシュの前記複数のキャッシュエージェントにブロードキャストし、
前記Ｐ２Ｐリクエストがペンディングである間に、前記第１のキャッシュラインに関連する転送リクエストを、前記第１のリクエストネットワークを通して、受信し、前記転送リクエストは、前記ローカルゲートウェイが前記外部ゲートウェイから転送されたプロセッサ間リクエストに応答して発行したものであり、
前記ＲＣにおいて、前記転送リクエストを受信した後に、前記Ｐ２Ｐリクエストに対するレスポンスに基づいて前記第１のキャッシュラインのプロセッサ内状態を設定するように構成され、
前記プロセッサ内状態は、前記ローカルプロセッサおよび前記外部プロセッサに関連する前記第１のキャッシュラインのプロセッサ間状態も特定し、さらに
前記転送リクエストに対するレスポンスを、前記プロセッサ内状態の設定後、かつ、前記Ｐ２Ｐリクエストの完了後に発行するように構成され、
前記転送リクエストに対するレスポンスは、前記Ｐ２Ｐリクエストがペンディングである間遅延される、システム。
【請求項１６】
前記ローカルゲートウェイは、前記第１のキャッシュラインに対応するゲートウェイタグを含み、
前記ゲートウェイタグは、前記ローカルゲートウェイによって、前記ローカルプロセッサが前記第１のキャッシュラインを保持していると判断するために使用される、請求項１５に記載のシステム。
【請求項１７】
前記外部プロセッサは、
前記ローカルゲートウェイに動作可能に接続された外部ゲートウェイと、
複数の外部スレーブキャッシュに対する複数のキャッシュエージェントと、
前記外部ゲートウェイと前記複数の外部スレーブキャッシュの前記複数のキャッシュエージェントを動作可能に接続する一方向性リングからなる第２のリクエストネットワークとを含み、
前記外部ゲートウェイは、前記第１のキャッシュラインに対するプロセッサ間無効化リクエストを前記ローカルゲートウェイに対して発行するように構成され、
前記ローカルゲートウェイは、前記プロセッサ間無効化リクエストに応答して前記第１のリクエストネットワーク上に前記転送リクエストを発行し、
前記ローカルゲートウェイは、前記第１のリクエストネットワーク上で前記転送リクエストのリターンを見た後に、前記ゲートウェイタグを無効化する、請求項１６に記載のシステム。
【請求項１８】
前記ローカルプロセッサはローカルゲートウェイをさらに含み、
前記ローカルゲートウェイは、
前記Ｐ２Ｐリクエストを前記第１のリクエストネットワークを通して受信し、
前記Ｐ２Ｐリクエストによって要求されるプロセッサ内状態の前記第１のキャッシュラインを前記ローカルプロセッサが保持しているか否か判断できないことに応じて、前記第１のキャッシュラインに対するプロセッサ間リクエストを前記外部プロセッサに対して発行するように、構成される、請求項１５〜１７のいずれか１項に記載のシステム。
【請求項１９】
前記ＲＣの前記キャッシュエージェントはさらに、
前記Ｐ２Ｐリクエストがペンディングである間に前記第１のキャッシュラインに対するＰ２Ｐ読取アクセスリクエスト（ｐＲＴＳ）を受信したことに応じて前記Ｐ２Ｐリクエストが失敗であるとみなすように構成され、前記Ｐ２Ｐリクエストは、前記第１のキャッシュラインに対する読取−書込アクセスリクエスト（ｐＲＴＯ）である、請求項１５〜１８のいずれか１項に記載のシステム。
【請求項２０】
前記ＲＣの前記キャッシュエージェントは、仲介ライトバックを発行して前記ＲＣに格納されている第２のキャッシュラインを追い出す、請求項１５〜１９のいずれか１項に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
背景
計算において、キャッシュコヒーレンスまたはキャッシュコヒーレンシとは、１つの共有リソースの複数のローカルキャッシュに格納されているデータの一貫性を指す。あるシステムにおける複数のクライアントが、共通のメモリリソースのキャッシュを維持するとき、データに一貫性がないという問題が生じ得る。これは特に、マルチプロセッシングシステムにおけるＣＰＵについて言える。キャッシュコヒーレンスは、キャッシュ間の一貫性とキャッシュとメモリの間の一貫性双方を保って、キャッシュの存在が、性能に対するこれらキャッシュの影響を除いて、システムプログラマーには実質的に不可視となるようにすることを、意図する。
【発明の概要】
【課題を解決するための手段】
【０００２】
概要
概して、ある局面において、本発明はキャッシュコヒーレンスのための方法に関する。この方法は、第１のリクエスタキャッシュ（ＲＣ）のキャッシュエージェントによって、ローカルプロセッサの部分的に順序付けされたリクエストネットワークを通して、キャッシュラインに対する第１のピアツーピア（Ｐ２Ｐ）リクエストを、上記ローカルプロセッサ上の複数のスレーブキャッシュの複数のキャッシュエージェントにブロードキャストすることと、上記第１のＲＣの上記キャッシュエージェントによって、上記部分的に順序付けされたリクエストネットワークを通して、上記第１のＰ２Ｐリクエストがペンディングである間に、上記キャッシュラインに関連する転送リクエストを、上記ローカルプロセッサ上のローカルゲートウェイから受信することとを含み、上記ローカルゲートウェイは、外部プロセッサ上の外部ゲートウェイに動作可能に接続され、上記第１のＲＣの上記キャッシュエージェントは、上記第１のＰ２Ｐリクエストがペンディングであることを理由に、上記転送リクエストに対する応答を遅延させ、さらに、上記第１のＲＣの上記キャッシュエージェントによって、上記転送リクエストの受信後に、上記第１のＰ２Ｐリクエストに対する複数のレスポンスを、上記複数のスレーブキャッシュの上記複数のキャッシュエージェントから受信することと、上記第１のＲＣの上記キャッシュエージェントによって、上記複数のレスポンスの受信後に、上記第１のＲＣ内の上記キャッシュラインのプロセッサ内状態を設定することとを含み、上記プロセッサ内状態は、上記ローカルプロセッサおよび上記外部プロセッサに関連する上記キャッシュラインのプロセッサ間状態も特定し、さらに、上記第１のＲＣの上記キャッシュエージェントによって、上記転送リクエストに対するレスポンスを、上記プロセッサ内状態の設定後かつ上記第１のＰ２Ｐリクエストの完了後に発行することと、上記第１のＲＣの上記キャッシュエージェントによって、上記プロセッサ内状態を、上記転送リクエストに対する上記レスポンスの発行に応じて変更することとを含む。
【０００３】
概して、ある局面において、本発明はキャッシュコヒーレンスのための方法に関する。この方法は、追い出し（evicting）キャッシュ（ＥＣ）のキャッシュエージェントによって、ローカルプロセッサ上の部分的に順序付けされたリクエストネットワークを通して、キャッシュラインに対するピアツーピア（Ｐ２Ｐ）ライトバックリクエストを、上記ローカルプロセッサ上の複数のスレーブキャッシュの複数のキャッシュエージェントにブロードキャストすることと、上記ＥＣの上記キャッシュエージェントによって、上記部分的に順序付けされたリクエストネットワークを通して、上記Ｐ２Ｐライトバックリクエストがペンディングである間に、上記キャッシュラインに対する第１の転送リクエストを、上記ローカルプロセッサ上のローカルゲートウェイから受信することとを含み、上記ローカルゲートウェイは、外部プロセッサ上の外部ゲートウェイに動作可能に接続され、上記ＥＣの上記キャッシュエージェントは、上記Ｐ２Ｐライトバックリクエストがペンディングである間、上記第１の転送リクエストに対する応答を遅延させて、上記ローカルプロセッサ上で上記キャッシュラインに対して１つのＰ２Ｐライトバックリクエストのみがアクティブであることを保証し、さらに、上記ＥＣの上記キャッシュエージェントによって、複数のレスポンスを上記複数のスレーブキャッシュの上記キャッシュエージェントから受信することと、上記ＥＣの上記キャッシュエージェントによって、上記第１の転送リクエストに対するレスポンスを、上記複数のレスポンスを上記複数のスレーブキャッシュの上記キャッシュエージェントから受信した後、かつ、上記Ｐ２Ｐライトバックリクエストが完了した後に、発行することと、上記ＥＣの上記キャッシュエージェントによって、上記第１の転送リクエストに対するレスポンスを発行した後に、複数のレスポンスを上記複数のスレーブキャッシュの上記キャッシュエージェントに対して発行することとを含む。
【０００４】
概して、ある局面において、本発明はキャッシュコヒーレンスのためのシステムに関する。このシステムは、外部プロセッサと、ローカルプロセッサとを備え、ローカルプロセッサは、複数のローカルスレーブキャッシュの複数のキャッシュエージェントと、上記複数のローカルスレーブキャッシュの上記複数のキャッシュエージェントを動作可能に接続する第１の部分的に順序付けされたリクエストネットワークと、リクエスタキャッシュ（ＲＣ）のキャッシュエージェントとを含み、リクエスタキャッシュのキャッシュエージェントは、第１のキャッシュラインに対するピアツーピア（Ｐ２Ｐ）リクエストを、上記第１の部分的に順序付けされたリクエストネットワークを通して、上記複数のローカルスレーブキャッシュの上記複数のキャッシュエージェントにブロードキャストし、上記Ｐ２Ｐリクエストがペンディングである間に、上記第１のキャッシュラインに関連する転送リクエストを、上記部分的に順序付けされたリクエストネットワークを通して、受信し、上記ＲＣにおいて、上記転送リクエストを受信した後に、上記Ｐ２Ｐリクエストに対するレスポンスに基づいて上記キャッシュラインのプロセッサ内状態を設定するように構成され、上記プロセッサ内状態は、上記ローカルプロセッサおよび上記外部プロセッサに関連する上記キャッシュラインのプロセッサ間状態も特定し、さらに、上記転送リクエストに対するレスポンスを、上記プロセッサ内状態の設定後、かつ、上記Ｐ２Ｐリクエストの完了後に発行するように構成され、上記転送リクエストに対するレスポンスは、上記Ｐ２Ｐリクエストがペンディングである間遅延される。
【０００５】
本発明のその他の局面は、以下の説明およびそれに続く請求項から明らかになるであろう。
【図面の簡単な説明】
【０００６】
【図１】本発明の１つ以上の実施形態に従うシステムを示す。
【図２Ａ】本発明の１つ以上の実施形態に従うキャッシュエージェントおよびキャッシュを示す。
【図２Ｂ】本発明の１つ以上の実施形態に従うゲートウェイタグを示す。
【図３Ａ】本発明の１つ以上の実施形態に従うフローチャートを示す。
【図３Ｂ】本発明の１つ以上の実施形態に従う一組のテーブルを示す。
【図４Ａ】本発明の１つ以上の実施形態に従うフローチャートを示す。
【図４Ｂ】本発明の１つ以上の実施形態に従うフローチャートを示す。
【図４Ｃ】本発明の１つ以上の実施形態に従うフローチャートを示す。
【図５】本発明の１つ以上の実施形態に従う一組のテーブルを示す。
【図６Ａ】本発明の１つ以上の実施形態に従うフローチャートを示す。
【図６Ｂ】本発明の１つ以上の実施形態に従うフローチャートを示す。
【図６Ｃ】本発明の１つ以上の実施形態に従う一組のテーブルを示す。
【図７】本発明の１つ以上の実施形態に従う計算システムを示す。
【発明を実施するための形態】
【０００７】
詳細な説明
次に、本発明の具体的な実施形態について、添付の図面を参照しながら詳細に説明する。異なる図面における同様の要素は、一貫性を持たせるために同様の参照番号で示している。
【０００８】
本発明の実施形態の以下の詳細な説明では、本発明がより深く完全に理解されるよう、数多くの具体的な詳細事項について述べている。しかしながら、当業者にとって、これら具体的な詳細事項がなくても本発明を実施し得ることは、明らかであろう。それ以外の場合では、説明が不必要に複雑にならないよう、周知の特徴は詳しく説明していない。
【０００９】
概して、本発明の実施形態は、キャッシュコヒーレンスのためのシステムおよび方法を提供する。具体的には、複数のプロセッサが存在し各プロセッサは複数のキャッシュを有する。各プロセッサはまた、他のプロセッサのゲートウェイに接続されたゲートウェイを有する。プロセッサ間のキャッシュコヒーレンシは、プロセッサ間コヒーレンスプロトコルを用いて保たれる。１つのプロセッサ上において、このプロセッサの複数のキャッシュ間のキャッシュコヒーレンシは、順序付け特性を有するリクエストネットワークを用いて保たれる。この順序付け特性を用いることによって、キャッシュラインへのアクセス権（たとえば読取のみ、読取／書込等）取得のリクエストの前進（forward progress）を保証する。加えて、各プロセッサ上にキャッシュが複数あることに気付いていないプロセッサ間コヒーレンスプロトコルに対して、統一されたキャッシュビューを示す。
【００１０】
図１は、本発明の１つ以上の実施形態に従うシステム（１００）を示す。図１に示されるように、複数のプロセッサ（たとえばプロセッサＸ（１０１Ｘ）、プロセッサＹ（１０１Ｙ））が存在する。これら複数のプロセッサは、同一チップ上に位置していても別々のチップ上に位置していてもよい。各プロセッサ（１０１Ｘ，１０１Ｙ）は、複数のキャッシュに動作可能に接続された複数のコアを含む。たとえば、プロセッサＸ（１０１Ｘ）は、キャッシュＡ（１２０Ａ）に動作可能に接続されたコアＡ１（１２４Ａ）およびコアＡ２（１２６Ａ）、キャッシュＢ（１２０Ｂ）に動作可能に接続されたコアＢ１（１２４Ｂ）およびコアＢ２（１２６Ｂ）、ならびに、キャッシュＣ（１２０Ｃ）に動作可能に接続されたコアＣ１（１２４Ｃ）およびコアＣ２（１２６Ｃ）を含む。同様に、プロセッサＹ（１０１Ｙ）において、コアＦ１（１２４Ｆ）およびコアＦ２（１２６Ｆ）はキャッシュＦ（１２０Ｆ）に動作可能に接続され、コアＥ１（１２４Ｅ）およびコアＥ２（１２６Ｅ）はキャッシュＥ（１２０Ｅ）に動作可能に接続されている。各プロセッサ（１０１Ｘ，１０１Ｙ）はまた、他のプロセッサ（１０１Ｘ，１０１Ｙ）のゲートウェイ（１５２Ａ，１５２Ｂ）に動作可能に接続されたゲートウェイ（たとえばゲートウェイＡ（１５２Ａ），ゲートウェイＢ（１５２））（以下で説明する）を含む。
【００１１】
引続き図１を参照して、プロセッサＸ（１０１Ｘ）は、１つ以上の外部（すなわちプロセッサ外の）装置に動作可能に接続されたダイレクトメモリアクセス（ＤＭＡ）キャッシュ（１３０）と、プロセッサ外のメインメモリと通信するための１つ以上のメモリコントローラユニット（ＭＣＵ）（たとえばＭＣＵ  Ａ（１４４），ＭＣＵ  Ｂ（１４６））とを含む。プロセッサＹ（１０１Ｙ）も、ＤＭＡ（図示せず）と、１つ以上のＭＣＵ（図示せず）とを含み得る。
【００１２】
命令を首尾よく実行するために、プロセッサコア（１２４Ａ〜Ｃ，１２４Ｅ，１２４Ｆ，１２６Ａ〜Ｃ，１２６Ｅ，１２６Ｆ）および／または外部装置は、メインメモリ内の１つ以上のメモリアドレスに対するアクセス（たとえばメモリアドレスからの読取および／またはメモリアドレスへの書込）を頻繁に行なう。これら命令の実行を迅速化するために、いくつかのメモリアドレスの内容を、メインメモリよりもアクセス時間が短いキャッシュ（１２０Ａ〜Ｃ，１２０Ｅ，１２０Ｆ）にローカル保存してもよい。あるキャッシュ（１２０Ａ〜Ｃ，１２０Ｅ，１２０Ｆ）が、必要なメモリアドレスの内容を保存していない場合、または、メモリアドレスの内容が、必要な状態（以下で説明する）でキャッシュ（１２０Ａ〜Ｃ，１２０Ｅ，１２０Ｆ）に保存されていない場合、キャッシュミスが生じている。
【００１３】
本発明の１つ以上の実施形態において、各プロセッサ（１０１Ｘ，１０１Ｙ）は、キャッシュ（１２０Ａ〜Ｃ，１２０Ｅ，１２０Ｆ）に動作可能に接続された複数のキャッシュエージェントを含む。具体的に、プロセッサＸ（１０１Ｘ）は、キャッシュＡ（１２０Ａ）に動作可能に接続されたキャッシュエージェントＡ（１２２Ａ）と、キャッシュＢ（１２０Ｂ）に動作可能に接続されたキャッシュエージェントＢ（１２２Ｂ）と、キャッシュＣ（１２０Ｃ）に動作可能に接続されたキャッシュエージェントＣ（１２２Ｃ）とを含む。同様に、プロセッサＹ（１０１Ｙ）は、キャッシュＦ（１２０Ｆ）に動作可能に接続されたキャッシュエージェントＦ（１２２Ｆ）と、キャッシュＥ（１２０Ｅ）に動作可能に接続されたキャッシュエージェントＥ（１２２Ｅ）とを含む。キャッシュエージェントＤ（１２２Ｄ）はＤＭＡキャッシュ（１３０）に動作可能に接続されている。
【００１４】
本発明の１つ以上の実施形態において、キャッシュエージェント（１２２Ａ〜Ｅ）は、キャッシュミスに応答して、または、キャッシュラインの制御転送のために、さまざまな種類のピアツーピア（peer-to-peer）リクエストを、同一プロセッサ（１０１Ｘ，１０１Ｙ）上の他のキャッシュエージェント（１２２Ａ〜Ｅ）にブロードキャストし、このＰ２Ｐリクエストに対する（他のキャッシュエージェントからの）レスポンスを処理するように構成される。同様に、キャッシュエージェント（１２２Ａ〜Ｅ）はまた、ブロードキャストされたさまざまな種類のＰ２Ｐリクエストを聞き（すなわち受信し）、このＰ２Ｐリクエストに対するレスポンスを発行するように構成される。
【００１５】
本発明の１つ以上の実施形態において、Ｐ２Ｐリクエスト、転送リクエスト、および／または仲介リクエストの発生元であるプロセッサを、ローカルプロセッサと呼ぶ。ローカルプロセッサ上のキャッシュおよびゲートウェイを、それぞれローカルキャッシュおよびローカルゲートウェイと呼ぶ。このシステム（１００）内の他のプロセッサを、外部プロセッサと呼ぶ。外部プロセッサ上のキャッシュおよびゲートウェイを、それぞれ外部キャッシュおよび外部ゲートウェイと呼ぶ。
【００１６】
本発明の１つ以上の実施形態において、キャッシュエージェント（１２２Ａ〜Ｅ）は、さまざまな種類の仲介リクエストを、このキャッシュエージェントと同一のプロセッサ上のローカルゲートウェイに対して発行するように構成される。たとえば、キャッシュエージェント（１２２Ａ〜Ｄ）は、さまざまな種類の仲介リクエストを、ゲートウェイＡ（１５２Ａ）に対して発行する。同様に、キャッシュエージェントＥ（１２２Ｅ）およびキャッシュエージェントＦ（１２２Ｆ）は、さまざまな種類の仲介リクエストを、ゲートウェイＢ（１５２Ｂ）に対して発行する。キャッシュエージェント（１２２Ａ〜Ｅ）はまた、このキャッシュエージェント（１２２Ａ〜Ｅ）と同一のプロセッサ上のゲートウェイ（１５２Ａ，１５２Ｂ）から転送されたリクエストを聞く（すなわち受信する）ように構成される。
【００１７】
引続き図１を参照して、プロセッサＸ（１０１Ｘ）上で、ゲートウェイＡ（１５２Ａ）、ＭＣＵエージェント（１４２）、および複数のキャッシュエージェント（１２２Ａ〜Ｄ）は、リクエストネットワークＸ（１８０Ｘ）によって、動作可能に接続されている。プロセッサＹ（１０１Ｙ）上で、ゲートウェイＢ（１５２Ｂ）および複数のキャッシュエージェント（１２２Ｅ，１２２Ｆ）は、リクエストネットワークＹ（１８０Ｙ）によって接続されている。本発明の１つ以上の実施形態において、リクエストネットワークＸ（１８０Ｘ）およびリクエストネットワークＹ（１８０Ｙ）は同一である。リクエストネットワークＸ（１８０Ｘ）およびリクエストネットワークＹ（１８０Ｙ）はいずれも、Ｐ２Ｐリクエストおよび転送リクエストをブロードキャストするために使用し得る。各リクエストネットワーク（１８０Ｘ，１８０Ｙ）は、順序付け特性、すなわち、あるキャッシュエージェントがパケットＢを同一のキャッシュラインアドレスに対するパケットＡを見た後で送信した場合、このリクエストネットワーク上のキャッシュエージェントはいずれもパケットＡの前にパケットＢを見ることはないという特性を有する。したがって、各リクエストネットワーク（１８０Ｘ，１８０Ｙ）について可能な１つの実装例は、１つ以上の一方向性リングである。
【００１８】
本発明の１つ以上の実施形態において、各プロセッサ（１０１Ｘ，１０１Ｙ）は、Ｐ２Ｐリクエストに対するレスポンスおよびいくつかのレスポンスに関連するデータ（すなわちキャッシュライン）を送信するための、データおよびレスポンスネットワーク（１６０Ｘ，１６０Ｙ）を含む。本発明の１つ以上の実施形態において、データおよびレスポンスネットワーク（１６０Ｘ，１６０Ｙ）における少なくとも１つのネットワークは、二地点間の（point-to-point）レスポンスのための、１トラック当たりドライバが１つのフリーランニングパイプラインネットワークである。本発明の１つ以上の実施形態において、データおよびレスポンスネットワーク（１６０Ｘ，１６０Ｙ）は同一である。データおよびレスポンスネットワーク（１６０Ｘ，１６０Ｙ）は、リクエストネットワーク（１８０Ｘ，１８０Ｙ）と論理的には別のものであるが、レスポンスおよびデータの送信を、リクエストと同一の物理ネットワークを通して行なってもよい。
【００１９】
本発明の１つ以上の実施形態において、各プロセッサ（１０１Ｘ，１０１Ｙ）は、キャッシュからの仲介リクエストをゲートウェイ（１５２Ａ，１５２Ｂ）に送信するためのネットワークを含む。これらのネットワークは、リクエストネットワーク（１８０Ｘ，１８０Ｙ）および／またはデータおよびレスポンスネットワーク（１６０Ｘ，１６０Ｙ）と、リソースを共有してもよい。
【００２０】
図１は２つのプロセッサ（すなわちプロセッサＸ（１０１Ｘ），プロセッサＹ（１０１Ｙ））しか示していないが、システム（１００）は、任意の数のプロセッサを有し得る。さらに、プロセッサＸ（１０１Ｘ）は３つのキャッシュ（すなわちキャッシュＡ（１２０Ａ），キャッシュＢ（１２０Ｂ），キャッシュＣ（１２０Ｃ））しか示していないが、各プロセッサは任意の数のキャッシュを有し得る。加えて、図１は、各キャッシュに動作可能に接続されたコアを２つしか示していないが、各キャッシュには任意の数のコアを装着し得る。また、それぞれのキャッシュが装着されるコアの数は異なっていてもよい。
【００２１】
さらに、図１はプロセッサ１つ当たり１つのゲートウェイしか示していないが、本発明の１つ以上の実施形態において、１つのプロセッサは複数のゲートウェイを有する。このような実施形態において、プロセッサ上の複数のゲートウェイのうちの各ゲートウェイは、キャッシュラインの一部を担当する。言い換えると、所与のキャッシュラインに関連するリクエストは、プロセッサ上の複数のゲートウェイのうちの予め定められた１つのゲートウェイのみによって処理される。
【００２２】
図２Ａは、本発明の１つ以上の実施形態に従う、キャッシュエージェントＭ（２２２Ｍ）、キャッシュＭ（２２０Ｍ）、および複数のコア（すなわちコアＭ１（２２４Ｍ），コアＭ２（２２６Ｍ））を示す。キャッシュエージェントＭ（２２２Ｍ）は、図１を参照しながら先に述べたキャッシュエージェント（１２２Ａ〜Ｃ，１２２Ｅ，１２２Ｆ）のうちのいずれかに相当し得る。さらに、キャッシュＭ（２２０Ｍ）は、図１を参照しながら先に述べたキャッシュ（１２０Ａ〜Ｃ，１２０Ｅ，１２０Ｆ）のうちのいずれかに相当し得る。また、コア（２２４Ｍ，２２６Ｍ）は、図１を参照しながら先に述べたコア（２２４Ａ〜Ｃ，２２４Ｅ，２２４Ｆ，２２６Ａ〜Ｃ，２２６Ｅ，２２４Ｆ）のうちのいずれかに相当し得る。
【００２３】
キャッシュＭ（２２０Ｍ）は、複数のキャッシュライン（すなわちキャッシュラインＭ１（２１１），キャッシュラインＭ２（２１２），キャッシュラインＭ３（２１３））を格納する。各キャッシュライン（２１１，２１２，２１３）は、メインメモリ内の１つ以上のメモリアドレスに対応する。さらに、各キャッシュライン（２１１，２１２，２１３）は、システム（１００）内の別のキャッシュによっても保持されてもよい。本発明の１つ以上の実施形態において、キャッシュエージェントＭ（２２２Ｍ）は、あるキャッシュラインに対する（ローカルゲートウェイによって発行された）転送リクエストを、同一のキャッシュラインに対するＰ２Ｐリクエストがペンディングの間格納するリクエストテーブル（２０４）を含む（以下で説明する）。
【００２４】
上記のように、システム（１００）は複数のプロセッサを含む。また、上記のように、プロセッサ間のキャッシュコヒーレンシは、プロセッサ間コヒーレンスプロトコルを用いて（たとえばＭＯＥＳＩ状態を用いることによって）維持される。図２Ａのテーブル２．１は、各ＭＯＥＳＩ状態について可能なプロセッサ間状態を示す。
【００２５】
プロセッサ内の個々のキャッシュ各々（たとえばキャッシュＭ（２２０Ｍ））について、その他の状態（すなわちプロセッサ内状態）を用いて、このキャッシュが、キャッシュラインを保持しているプロセッサ内の唯一のキャッシュであるか否かを示す。キャッシュＭ（２２０Ｍ）は、各キャッシュラインについてプロセッサ内状態（２５４）を記録する。これは、プロセッサ間状態ＭおよびＥには必要である。なぜなら、キャッシュラインの内容の変更前に、このキャッシュラインは、プロセッサ内で、かつ複数のプロセッサ間で、排他的に保持されなければならないからである。本発明の１つ以上の実施形態において、ライトバック処理中プロセッサ間状態ＯおよびＳにも、対応するさらに他の状態が必要である。
【００２６】
図２Ａのテーブル２．２は、プロセッサのプロセッサ間キャッシュ状態を定めるプロセッサ内キャッシュ状態を示す。これら状態は「サプライヤ」状態として知られている。キャッシュラインがプロセッサ内で排他的に保持されているか否かを区別するために、各プロセッサ間状態について２つのプロセッサ内状態がある。たとえば、テーブル２．２に示されているように、プロセッサ間状態Ｍに対してプロセッサ内状態ＭＣおよびＤＣを用いて、キャッシュラインがプロセッサ内で排他的に保持されているか否かを区別する。キャッシュは、状態ＳＣのキャッシュラインを保持してもよく、この場合、キャッシュラインが別のキャッシュにおいて非排他的サプライヤ状態で保持されるか、またはキャッシュラインがこのキャッシュラインを非排他的サプライヤ状態で保持していたキャッシュから別のキャッシュに移動する。図２Ａには示されていないが、プロセッサ内状態ＩＣは、キャッシュがキャッシュラインを保持していないことを示す。
【００２７】
プロセッサ内において、１つのキャッシュ（サプライヤキャッシュ）のみが、プロセッサ間状態を示す状態のキャッシュラインを保持し、この状態がプロセッサ内で非排他的であれば（すなわち状態ＤＣ，ＯＣ，ＸＣ，またはＱＣ）、同一のプロセッサ上の他のキャッシュは、（Ｉではないことを除いて）プロセッサ間状態情報を伝えない状態ＳＣのキャッシュラインを保持し得る。
【００２８】
ゲートウェイタグ
本発明の１つ以上の実施形態において、ゲートウェイは、ゲートウェイタグを用いて、キャッシュラインについてのプロセッサ間状態の、ゲートウェイ自身のコピーを維持することができる。図２Ｂのテーブル２．３は、異なるプロセッサ間状態に対応する異なるゲートウェイタグ状態を示す。ゲートウェイタグ状態は、プロセッサ間の排他性を記録してもしなくてもよい。上記のように、本発明の１つ以上の実施形態において、１つのプロセッサは複数のゲートウェイを有する。このような実施形態では、キャッシュラインに対応するゲートウェイのみが、このキャッシュラインについてのゲートウェイタグを保持する。
【００２９】
ピアツーピア（Ｐ２Ｐ）リクエスト
本発明の１つ以上の実施形態において、プロセッサ上のキャッシュは、キャッシュライン（２１１，２１２，２１３）を、キャッシュ間コヒーレンスを維持するＰ２Ｐプロトコルを介して、これらキャッシュの間で転送することができるが、プロセッサの集約アクセス権を変更することも、前進を保証することもできない。本発明の１つ以上の実施形態において、集約アクセス権を変更するために、または、前進を保証するために、キャッシュは、ローカルゲートウェイ（すなわちこのキャッシュと同一のプロセッサ上のゲートウェイ）を通してリクエストを行なう。ローカルゲートウェイは、必要なプロセッサ間リクエストを行ないプロセッサ上の他のキャッシュにブロードキャストする（以下で説明する）。
【００３０】
図３Ａは、本発明の１つ以上の実施形態に従うフローチャートを示す。図３Ａのフローチャートは、キャッシュラインに対するＰ２Ｐリクエストと、ゲートウェイからの転送リクエストとこのＰ２Ｐリクエストのインタラクションについて説明する。図３Ａに示されるプロセスは、たとえば、図１を参照しながら先に述べたシステム（１００）の中の１つ以上の構成要素によって実行されてもよい。図３Ａに示される１つ以上のステップを、省略してもよく、繰返してもよく、および／または本発明の異なる実施形態間で順序が異なるように実行してもよい。したがって、本発明の実施形態は、図３Ａに示されるステップの特定の数および並びに限定されるとみなされてはならない。
【００３１】
ピアツーピア割当トランザクションは、キャッシュラインへのアクセス権を、同一のプロセッサ上の別のキャッシュからこのアクセス権を取得することによって、取得しようと試みる。このため、ピアツーピアリクエストは、所望のアクセス権があるキャッシュラインを他のキャッシュが有していない場合があるので、失敗に終わることがある。また、プロトコルは意欲的にブロードキャストするので、同一のキャッシュラインに対するリクエストに直列化ポイントがない状態では、異なるキャッシュによって同時に発行されたリクエスト間のコンフリクトが、たとえ他のキャッシュが所望のアクセス権を有していても、リクエストの失敗を引起す場合がある。
【００３２】
最初に、リクエスタキャッシュのキャッシュエージェントが、キャッシュラインに対するＰ２Ｐリクエストを、プロセッサ上のその他のキャッシュ（すなわちスレーブキャッシュ）にブロードキャストする（ステップ３０２）。このＰ２Ｐリクエストは、プロセッサの、部分的に順序付けされたリクエストネットワークを通してブロードキャストされる。Ｐ２Ｐリクエストはまた、プロセッサ上のローカルゲートウェイによって受信されてもよい。図３Ｂのテーブル３．１は、起こり得る２種類のＰ２Ｐリクエストを示す。
【００３３】
ステップ３０４で、リクエスタキャッシュのキャッシュエージェントは、キャッシュラインに対する、転送リクエストを受信する。この転送リクエストは、プロセッサ上のローカルゲートウェイからのものである。加えて、この転送リクエストは、キャッシュラインに対するＰ２Ｐリクエストがまだペンディング中である間に受信される。キャッシュエージェントは、後の処理のために、この転送リクエストを格納してもよい（すなわちキャッシュエージェントは転送リクエストに対するレスポンスを遅延させる）。転送リクエストはゲートウェイによって生成されたものなので、キャッシュエージェントは、転送リクエストをいつ受信するかについては制御できない。スレーブキャッシュからのレスポンス前に受信するか、またはいくつかのレスポンスの受信後に受信する可能性がある。
【００３４】
ステップ３０６で、スレーブキャッシュのキャッシュエージェントは、Ｐ２Ｐリクエストに対するレスポンスを発行する。具体的に、各スレーブキャッシュのキャッシュエージェントは、Ｐ２Ｐリクエストに対して１つのレスポンスを発行する。この１つのレスポンスは、Ｐ２Ｐリクエストの種類に基づくものであってもよく、および／またはスレーブキャッシュがキャッシュラインを保持するプロセッサ内状態に基づくものであってもよい。加えて、キャッシュの／キャッシュエージェントのレスポンスに続いて、スレーブキャッシュ内のキャッシュラインについてのプロセッサ内状態は、Ｐ２Ｐリクエストの種類に基づいてアップデートされてもよい。図３Ｂのテーブル３．３は、スレーブキャッシュのキャッシュエージェントによる、Ｐ２Ｐリクエストへのレスポンスを示す。図３Ｂのテーブル３．３はまた、レスポンス後のスレーブキャッシュ内のキャッシュラインの新たな状態を示す。たとえば、Ｐ２ＰリクエストがｐＲＴＳでスレーブキャッシュがＸＣのキャッシュラインを保持している場合、スレーブキャッシュのキャッシュエージェントはＤａｔａＥで応答し、スレーブキャッシュ内のキャッシュラインのプロセッサ内状態はＳＣに設定される。図３Ｂのテーブル３．２は、さまざまな種類のレスポンスを説明する。
【００３５】
本発明の１つ以上の実施形態において、スレーブが、キャッシュラインに対するペンディングのリクエストを、同一のキャッシュラインに対するリクエストを別のキャッシュから受信したときに有している場合、スレーブは、否定応答（Ｎａｃｋ）によって応答し状態は変化しない。スレーブは、リソースのコンフリクト、または、ペンディングのリクエストの存在の判定が不正確である等の、他の理由で、Ｎａｃｋによる応答を行なってもよい。データ搬送レスポンス（たとえばＤａｔａＭ，ＤａｔａＯ，ＤａｔａＥ，ＤａｔａＳ）は、スレーブキャッシュによって保持されるキャッシュラインの内容を搬送する。
【００３６】
Ｐ２Ｐリクエストに対する応答は、スレーブキャッシュのキャッシュエージェントによるスコア表示を必要とせず、スレーブキャッシュのキャッシュエージェントが発行したかもしれないリクエストのサービスを待つことなく、無条件で行なわれる。
【００３７】
ステップ３０８で、リクエストキャッシュのキャッシュエージェントがスレーブキャッシュからＰ２Ｐリクエストに対するすべてのレスポンスを一旦受信すると、データ搬送レスポンスが受信されたか否かが判断される。データ搬送レスポンスが受信されたと判断された場合、このプロセスはステップ３１０に進む。データ搬送レスポンスが受信されていないと判断された場合（たとえばＰ２ＰリクエストはｐＲＴＯでありリクエスタキャッシュはサプライヤ状態のキャッシュラインを既に保持）、このプロセスはステップ３１２に進む。
【００３８】
ステップ３１０で、キャッシュラインデータがリクエスタキャッシュにインストールされ、キャッシュラインについて初期プロセッサ内状態が設定される。この新たな状態は、スレーブキャッシュから受信したデータ搬送レスポンスの種類、または、リクエスタがサプライヤ状態の場合はリクエスタの元の状態（たとえばリクエスタキャッシュはプロセッサ内状態ＸＣのキャッシュラインを既に保持しておりｐＲＴＯを発行して状態ＥＣに到達）に基づく。図３Ｂのテーブル３．４は、スレーブキャッシュから受信したデータ搬送レスポンスの種類に基づくキャッシュラインの新たな状態を示す。たとえば、図３Ｂに示されるように、データ搬送レスポンスがＤａｔａＥであれば、新たな状態はＸＣである。
【００３９】
ステップ３１２において、Ｐ２ＰリクエストがｐＲＴＯでありＮａｃｋレスポンスを受信しなかった場合、このプロセスはステップ３１３に進む。しかしながら、Ｐ２ＰリクエストがｐＲＴＳであった場合、または、Ｐ２ＰリクエストがｐＲＴＯでＮａｃｋレスポンスを受信した場合、このプロセスはステップ３１６に進む。
【００４０】
ステップ３１３において、Ｐ２ＰリクエストがｐＲＴＯでありリクエスタキャッシュがＰ２Ｐリクエスト（すなわちｐＲＴＯ）のペンディング中にｐＲＴＳを受信したか否かが判断される。ステップ３１３の条件が真であれば、ステップ３１４をスキップして（以下で説明する）排他性を妨害しないようにし、Ｐ２Ｐリクエスト（すなわちｐＲＴＯ）は失敗とみなされる。このプロセスは次にステップ３１６に進む。しかしながら、ステップ３１３の条件が偽であれば、このプロセスはステップ３１４に進む。
【００４１】
ステップ３１４において、リクエスタキャッシュ内のキャッシュラインのプロセッサ内状態への補助アップデートが実行される。キャッシュラインの新たなプロセッサ内状態は、キャッシュラインの現在の（すなわちステップ３１０）プロセッサ内状態に基づく。図３Ｂのテーブル３．５は、補助アップデート後の、現在のプロセッサ内状態に基づくキャッシュラインの新たな状態を示す。この詳細な説明のおかげで、当業者にとって、ステップ３１０およびステップ３１４のアップデートを１つのアップデートにマージできることは明白であるはずである。
【００４２】
ステップ３１６において、Ｐ２Ｐリクエストはもはやペンディングではなく（すなわちＰ２Ｐリクエストは完了しているまたは失敗とみなされる）、リクエスタキャッシュのキャッシュエージェントは転送リクエストに応答する。
【００４３】
図３Ａに示されるプロセスおよび図３Ｂのテーブルに鑑みると、１つのキャッシュが同一のプロセッサの別のキャッシュからキャッシュラインを取得するとき、（１）データおよびプロセッサ間状態が、サプライ側のキャッシュから宛先キャッシュへのレスポンスにおいて転送され、（２）ソースキャッシュはそのサプライヤステータスを失い、（３）宛先キャッシュがサプライヤになる。したがって、常に、プロセッサ間状態は、サプライヤキャッシュに格納されているか、または、一方のキャッシュから他方のキャッシュへのレスポンスに格納されている。Ｐ２Ｐトランザクションはそれ自体、プロセッサ間状態を変更しない。
【００４４】
状態ＭＣ、ＲＣ、ＥＣ、またはＰＣに保たれるキャッシュラインは、このキャッシュラインがプロセッサ上の他のキャッシュに保持されないことを示す。Ｐ２Ｐリクエストはこの特性を次のように維持する：（１）キャッシュラインをプロセッサ内排他的状態にすることができるＰ２Ｐリクエストのみが、成功したｐＲＴＯであり、（２）成功したｐＲＴＯはその他のキャッシュをすべて無効にし、（３）キャッシュラインを取り戻すためのスレーブによるリクエストは、リクエストネットワーク順序付け特性によって、すべてのキャッシュにおいて、ｐＲＴＯの後に順序付けられて、リクエストがｐＲＴＯの結果に影響を及ぼすことができないようにし、（４）ｐＲＴＯが成功すれば、プロセッサ上の別のキャッシュによるキャッシュラインへのアクセス権の再取得は、ｐＲＴＯの完了後リクエストをサービスするときにその排他的状態を失うｐＲＴＯリクエスタを介さねばならず、（５）このため、ｐＲＴＯリクエスタがキャッシュラインを状態ＭＣ、ＲＣ、ＥＣ、またはＰＣに保っている間、プロセッサの他のキャッシュはこのキャッシュラインを保持しない。
【００４５】
ローカルおよび外部転送リクエスト
図４Ａは、本発明の１つ以上の実施形態に従うフローチャートを示す。図４Ａのフローチャートは、キャッシュラインに対するローカル転送リクエストについて説明する。図４Ａに示されるプロセスは、たとえば、図１を参照しながら先に述べたシステム（１００）の中の１つ以上の構成要素によって実行されてもよい。図４Ａに示される１つ以上のステップを、省略してもよく、繰返してもよく、および／または本発明の異なる実施形態間で順序が異なるように実行してもよい。したがって、本発明の実施形態は、図４Ａに示されるステップの特定の数および並びに限定されるとみなされてはならない。
【００４６】
最初に、ローカルゲートウェイが、キャッシュラインに対するリクエストを、リクエスタキャッシュのキャッシュエージェントから受信する（ステップ４０２）。本発明の１つ以上の実施形態において、このリクエストは、Ｐ２Ｐリクエストであり、したがって、プロセッサ上のゲートウェイとスレーブキャッシュのキャッシュエージェントとによって、部分的に順序付けされたリクエストネットワークを通して受信される。本発明の１つ以上の実施形態において、このリクエストは、リクエスタキャッシュのキャッシュエージェントによって、ローカルゲートウェイに対し直接発行された、仲介リクエストである。仲介リクエストをリクエスタキャッシュが発行し得る理由は、キャッシュラインに対する前のＰ２Ｐリクエストはコンフリクトが原因で失敗したことにあり、または、リクエスタキャッシュが必要とするキャッシュラインへの十分なアクセス権をプロセッサが有していないことにある。代表的な仲介リクエストは、ｍＲＴＳ（すなわちキャッシュラインへの読取アクセスに対するリクエスト）およびｍＲＴＯ（すなわちキャッシュラインへの読取／書込アクセスに対するリクエスト）を含む。
【００４７】
キャッシュラインに対するリクエストを受信すると、ローカルゲートウェイは、ローカルプロセッサが適切な状態のキャッシュラインを保持しているか否か判断しようと試みる（ステップ４０６）。ローカルゲートウェイが、ローカルプロセッサが適切な状態のキャッシュラインを保持していると判断した場合、このプロセスはステップ４１４に進む。しかしながら、ローカルプロセッサが適切な状態のキャッシュラインを保持していないとゲートウェイが判断した場合、または、ローカルプロセッサが適切な状態のキャッシュラインを保持しているか否かをゲートウェイが判断できない場合（ステップ４０６）、このプロセスはステップ４０７に進む。
【００４８】
上記のように、本発明の１つ以上の実施形態において、ローカルゲートウェイは、キャッシュラインに対するゲートウェイタグを維持する。ゲートウェイタグは、ローカルプロセッサ内のキャッシュラインのプロセッサ間状態を示す。したがって、ゲートウェイは、キャッシュラインに対するゲートウェイタグにアクセスすることにより、ローカルプロセッサが適切な状態のキャッシュラインを保持しているか否か判断し得る。しかしながら、ゲートウェイタグがなければ、または、キャッシュラインに対する既存のゲートウェイタグ上に関連するＥＳＩ状態がなければ、ローカルプロセッサが適切な状態のキャッシュラインを保持しているか否かをローカルゲートウェイが判断できない場合がある。ＥＳＩ状態がなければ、ローカルゲートウェイは、ｐＲＴＳに適した状態のキャッシュラインをローカルプロセッサが保持しているか否か識別することができる。ｐＲＴＯについては、キャッシュラインが保持されていないことをゲートウェイタグが示すのであれば、適切な状態のキャッシュラインを保持していないことしか識別できない。
【００４９】
ステップ４０７において、プロセッサ間リクエスト（たとえばｍＲＴＯまたはｐＲＴＯについてはＲＴＯ，ｍＲＴＳまたはｐＲＴＳについてはＲＴＳ）が発行される。このプロセッサ間リクエストが発行され得る理由は、（ｉ）ローカルゲートウェイがキャッシュラインに対するゲートウェイタグを維持していないのでローカルゲートウェイはローカルプロセッサが適切な状態のキャッシュラインを保持しているか否かを判断することができなかったことにあるか、または、（ｉｉ）ローカルゲートウェイはキャッシュラインに対するゲートウェイタグを維持しておりゲートウェイタグはローカルプロセッサが適切な状態のキャッシュラインを保持していないことを示しおよび／またはゲートウェイタグには関連するＥＳＩ状態がないことに、ある。正確なディレクトリを備えたプロセッサ間プロトコルが適所にあり各キャッシュラインを保持する一組のプロセッサが正確にわかっていると想定して、プロセッサ間リクエストは、プロセッサがキャッシュラインを既に保持しているのであれば確認応答（acknowledgement）をリターンする。
【００５０】
ステップ４０８において、プロセッサ間リクエストの発行後、ローカルゲートウェイは、メモリからまたは外部プロセッサ上の外部スレーブキャッシュから、適切なプロセッサ間状態を受信する。プロセッサがキャッシュラインデータを既に保持しているのでなければ、キャッシュラインデータも受信する場合がある。
【００５１】
ＲＴＳに対し、ローカルゲートウェイは、リクエスタキャッシュのキャッシュエージェントに、ＤａｔａＳを提供することができる（ステップ４１０）。このデータリターンは、プロセッサが、キャッシュラインの排他的ホルダになり、ローカルゲートウェイがＤａｔａＥを提供できるようにしているか否かの表示を含み得る。プロトコルは、変更されたコピーをプロセッサが取得することを要求するかもしれない。ＲＴＯに対し、同様のインタラクションが可能であるが、この場合、データは常に、排他的コピーを示し、プロセッサがそのコピーの変更を必要としていることを示し得る。したがって、ローカルゲートウェイからリクエスタキャッシュに提供されるどのデータも、ＤａｔａＥかＤａｔａＭのいずれかである（ステップ４１０）。
【００５２】
ステップ４１４において、ローカルゲートウェイは、ローカル転送リクエストを、部分的に順序付けされたリクエストネットワークを通して、ローカルプロセッサ上のスレーブキャッシュにブロードキャストする。ステップ４１４は、たとえば、リクエストが仲介リクエストのときに実行され、ゲートウェイタグから、必要なプロセッサ内状態のキャッシュラインをプロセッサが保持していると、判断される。ステップ４１４は、たとえば、プロセッサ間リクエストが確認応答をリターンしたときに実行される。図５のテーブル５．１は、起こり得る２つのローカル転送リクエストを示す。ＲＴＳの場合、ｆＲＴＳがブロードキャストされる。ＲＴＯの場合、ｆＲＴＯがブロードキャストされる。
【００５３】
ステップ４１６において、スレーブキャッシュのキャッシュエージェントは、順序付けされたリクエストネットワークを通して、キャッシュラインに対するローカル転送リクエストを受信する。スレーブキャッシュのキャッシュエージェントは、リクエスタキャッシュのキャッシュエージェントに直接応答してもよい。各レスポンスは、スレーブキャッシュ内のキャッシュラインの現在のプロセッサ内状態に基づく。加えて、スレーブキャッシュ内のキャッシュラインのプロセッサ内状態は、ローカル転送リクエストの種類および現在のプロセッサ内状態に基づいてアップデートされる。図５のテーブル５．２は、ローカル転送リクエストに対するスレーブキャッシュのキャッシュエージェントのレスポンス、およびそれに続く、プロセッサ内状態のアップデートを示す。たとえば、ローカル転送リクエストがｆＲＴＳでありスレーブキャッシュ内のキャッシュラインの現在のプロセッサ内状態がＱＣであれば、スレーブキャッシュのキャッシュエージェントはＤａｔａＳで応答し、スレーブキャッシュ内のキャッシュラインの新たなプロセッサ内状態はＳＣに設定される。
【００５４】
ステップ４１２において、リクエスタキャッシュのキャッシュエージェントは、データが受信された場合、リクエスタキャッシュ内にキャッシュラインデータをインストールし、リクエスタキャッシュ内のキャッシュラインのプロセッサ内状態をアップデートする。
【００５５】
上記のように、ＲＴＯに応答してローカルゲートウェイが確認応答を受信する場合がある。この場合、確認応答は、常に排他的コピーを示し、プロセッサがそのコピーの変更を必要とすることを示すことができる。ｆＲＴＯのブロードキャストに加えて、ローカルゲートウェイも、ＡｃｋＥまたはＡｃｋＭを転送して、変更されたステータスを示す。キャッシュラインがローカルプロセッサによって状態Ｏで保持されている場合、リクエスト側のキャッシュは、ゲートウェイからＡｃｋＥにおいて伝えられる排他性を、ｆＲＴＯからＤａｔａＯによって与えられた変更されたステータスと組合わせて、状態Ｍのキャッシュラインをインストールする。
【００５６】
本発明の１つ以上の実施形態において、ステップ４０２に関し、Ｐ２Ｐリクエストの失敗後に明示的な仲介リクエストをキャッシュが送信する代わりに、部分的に順序付けされたリクエストネットワークを通したＰ２Ｐリクエストのブロードキャストにゲートウェイを含めることができる。これは、次に、ピアツーピアリクエストが成功したか失敗したかについての情報を、リクエスト側のキャッシュから送信された明示的なパケットを介して、または、ゲートウェイによって、取得することができ、このゲートウェイは、キャッシュに対するレスポンスを受信し成功したか失敗したかを独立して判断するものである。ゲートウェイは、失敗を検出すると、あたかも明示的な仲介リクエストを受信したかのように振る舞う。
【００５７】
本発明の１つ以上の実施形態において、ゲートウェイは、一回につき、キャッシュライン１つ当たり転送リクエストを１つしか発行せず、同じキャッシュラインに対する別のリクエストを発行する前に、すべてのレスポンスが受信されるのを待つ。本発明の１つ以上の実施形態において、キャッシュのキャッシュエージェントがキャッシュライン１つ当たり２つ以上の転送リクエストを格納することができ部分的に順序付けされたリクエストネットワークがゲートウェイと各キャッシュエージェント間の転送リクエストの順序付けを維持するとき、ゲートウェイは、最初の転送リクエストの完了前に同一のキャッシュラインに対する複数の転送リクエストを発行してもよい。
【００５８】
図４Ｂは、本発明の１つ以上の実施形態に従うフローチャートを示す。図４Ｂのフローチャートは、キャッシュラインに対する外部転送リクエストについて説明する。図４Ｂに示されるプロセスは、たとえば、図１を参照しながら先に述べたシステム（１００）の中の１つ以上の構成要素によって実行されてもよい。図４Ｂに示される１つ以上のステップを、省略してもよく、繰返してもよく、および／または本発明の異なる実施形態間で順序が異なるように実行してもよい。したがって、本発明の実施形態は、図４Ｂに示されるステップの特定の数および並びに限定されるとみなされてはならない。
【００５９】
最初に、ローカルゲートウェイが、外部プロセッサ上の外部ゲートウェイから、キャッシュラインに対するプロセッサ間リクエストを受信する（ステップ４２２）。このプロセッサ間リクエストが外部ゲートウェイによって発行される理由は、外部プロセッサ上のリクエスタキャッシュまたはＤＭＡが必要とする、必要なプロセッサ内状態のキャッシュラインを、外部プロセッサが有していないからである。代表的なプロセッサ間リクエストは、ＲＴＳ、ＲＴＯ、キャッシュライン無効化リクエスト、およびキャッシュラインの一回読取スナップショットを含む。
【００６０】
ステップ４２４において、ローカルゲートウェイが、部分的に順序付けされたリクエストネットワークを通して、ローカルプロセッサ上のすべてのキャッシュに、キャッシュラインに対する外部転送リクエストをブロードキャストする。外部転送リクエストの種類は、ローカルゲートウェイが受信したプロセッサ間リクエストの種類によって決まる。図５のテーブル５．３は、さまざまな種類のプロセッサ間リクエストについて、さまざまな外部転送リクエストを示す。たとえば、キャッシュラインに対するｆＣＰＩは、ローカルゲートウェイによってブロードキャストされて、キャッシュラインに対するプロセッサ間リクエストＲＴＯをサービスしてもよい。
【００６１】
ステップ４２６において、各ローカルキャッシュのキャッシュエージェントは、外部転送リクエストに対するレスポンスを発行し、および／または、ローカルキャッシュ内のキャッシュラインのプロセッサ内状態をアップデートする。このレスポンスおよび新しいプロセッサ内状態は、外部転送リクエストの種類および／またはキャッシュ内のキャッシュラインの現在のプロセッサ内状態に基づく。図５のテーブル５．４は、外部転送リクエストに対する、キャッシュによるさまざまなレスポンスを示す。たとえば、図５．４に示されるように、ローカルキャッシュ内のキャッシュラインの現在のプロセッサ内状態がＲＣであり、かつ、外部転送リクエストの種類がｆＣＰＢである場合、ローカルキャッシュのキャッシュエージェントが発行するレスポンスは、ＤａｔａＯである。テーブル５．５は、外部転送リクエストの種類およびキャッシュラインの現在のプロセッサ内状態に基づく、ローカルキャッシュ内のキャッシュラインの新たなプロセッサ内状態を示す。たとえば、テーブル５．５に示されるように、外部転送リクエストの種類がｆＣＰＢでありキャッシュラインの現在のプロセッサ内状態がＥＣである場合、キャッシュラインの新たなプロセッサ内状態はＳＣに設定される。
【００６２】
ステップ４２８で、ローカルゲートウェイが一旦ローカルキャッシュからレスンポンスを受信すると、ローカルゲートウェイは、プロセッサ間リクエストに対するレスポンスを発行する。本発明の１つ以上の実施形態において、キャッシュラインに対するゲートウェイタグをローカルゲートウェイが格納するとき、このゲートウェイタグはアップデートされて、ローカルプロセッサ上のキャッシュラインの新たなプロセッサ間状態を反映する。
【００６３】
テーブル５．５に示されるように、他の外部転送リクエストとは異なり、ｆＣＰＢおよびｆＣＰＤは、キャッシュラインを提供するいずれのスレーブキャッシュもサプライヤ状態のままにしない。これにより、キャッシュラインを、キャッシュがｆＣＰＢまたはｆＣＰＤをサービスする前に、別のキャッシュに転送することができる。次に、この別のキャッシュもキャッシュラインを提供する。ｆＣＰＢの場合、最初のサプライヤはキャッシュラインへの書込アクセスを失うので、すべてのコピーのデータが整合していなければならない。これはｆＣＰＤには当てはまらない。ｆＣＰＤの場合、介在する記憶装置がキャッシュラインの値を変更する可能性がある。ゲートウェイは、データを搬送するレスポンスのうち１つだけを選択し他は廃棄しなければならない。
【００６４】
上記のように、ローカルゲートウェイは、ゲートウェイタグを用いて、Ｐ２Ｐリクエストの失敗時に、プロセッサ間リクエストは必要ないと判断して、即時、対応する転送リクエストの発行に進むことができる。しかしながら、この失敗はコンフリクトが原因であったはずであり、比較的まれであると予測される。Ｐ２Ｐリクエストの失敗を誤って予測した場合、キャッシュラインを送るペンディングリクエストがない状態でキャッシュラインを送ることになる可能性がある。
【００６５】
たとえば、このような失敗の予測誤りが発生し得るのは、外部リクエストによるゲートウェイタグの無効化またはダウングレードが早過ぎてピアツーピアリクエストがサプライヤキャッシュへのレースに勝利ししたがって成功したものの、ゲートウェイがピアツーピアリクエストを見たときにはゲートウェイタグは既に無効化またはダウングレードされていて、そのためプロセッサ間リクエストを早くトリガする場合である。
【００６６】
図４Ｃは、本発明の１つ以上の実施形態に従うフローチャートを示す。図４Ｃのフローチャートは、ローカルゲートウェイによるＰ２Ｐ失敗の予測誤りに対する解決策について説明する。図４Ｃに示されるプロセスは、たとえば、図１を参照しながら先に述べたシステム（１００）の中の１つ以上の構成要素によって実行されてもよい。図４Ｃに示される１つ以上のステップを、省略してもよく、繰返してもよく、および／または本発明の異なる実施形態間で順序が異なるように実行してもよい。したがって、本発明の実施形態は、図４Ｃに示されるステップの特定の数および並びに限定されるとみなされてはならない。
【００６７】
最初に、リクエスタキャッシュのキャッシュエージェントが、キャッシュラインに対するＰ２Ｐリクエスト（たとえばｐＲＴＳ）を、部分的に順序付けされたリクエストネットワーク上でブロードキャストする（ステップ４５０）。部分的に順序付けされたリクエストネットワークは、順序付け特性、すなわち、あるリクエスタが自身のリクエストＡを同一のキャッシュラインに対する別のリクエストＢよりも前に見る場合、リクエストＡよりも前にリクエストＢを見るエージェントはないという特性を有する。この順序付け特性を有するネットワークとして可能なものとして、一方向性リングが挙げられる。
【００６８】
ステップ４５２で、ローカルゲートウェイは、キャッシュラインに対する外部転送無効化リクエスト（ｆＩＮＶ）を、キャッシュラインに対するゲートウェイタグを無効化せずに、部分的に順序付けされたリクエストネットワーク（たとえば一方向性リング）上でブロードキャストする。ｆＩＮＶは、ローカルゲートウェイが受信したキャッシュラインに対するプロセッサ間無効化リクエストに対する応答である。
【００６９】
ステップ４５４で、ローカルゲートウェイは、外部転送無効化リクエストのリターン前に、部分的に順序付けされたリクエストネットワークを通してＰ２Ｐリクエスト（たとえばｐＲＴＳ）を受信する。ローカルゲートウェイは、ｐＲＴＳを受信すると、キャッシュラインに対するゲートウェイタグがまだ有効であることから、ｐＲＴＳは成功するであろうと想定する。
【００７０】
ステップ４５６で、ｆＩＮＶが、部分的に順序付けされたリクエストネットワーク（たとえば一方向性リング）から完全移行しローカルゲートウェイにリターンされた後になって初めて、ローカルゲートウェイは、キャッシュラインに対するゲートウェイタグを無効化する。ゲートウェイが自身の転送リクエスト（たとえばｆＩＮＶ）を部分的に順序付けされたリクエストネットワーク上で見るまで、外部リクエストに対するゲートウェイタグアップデートは実行されないので、失敗の予測誤りは回避される。
【００７１】
本発明の１つ以上の実施形態において、キャッシュラインに対するローカルまたは外部転送リクエストは常に成功する。キャッシュラインに対するプロセッサ間状態がＩでなく、常に、サプライヤ状態のキャッシュラインをキャッシュが保持しているか、または、キャッシュラインが状態搬送レスポンスを介して移行中であるか、いずれかであると想定する。加えて、ピアツーピアリクエストを介してキャッシュ間で転送されているキャッシュラインについて、転送リクエストがキャッシュに到着する時間に関する不運が原因で、キャッシュラインを提供するキャッシュがないと想定する。このことは、リクエスト送信前のある瞬間において、キャッシュラインについてサプライヤであるキャッシュがあり、リクエストがキャッシュラインの取得に失敗したことが原因で、リクエストの完了後のある瞬間において、サプライヤであるキャッシュがあることを意味する。
【００７２】
プロセッサがキャッシュラインを（ゲートウェイを介して、必ず転送リクエストの前に）取得したときと、これを（ゲートウェイを介して、必ず転送リクエストの後に）放棄したときの間の、プロセッサキャッシュにおけるキャッシュラインの全履歴について考察する。この履歴は、キャッシュがキャッシュラインのサプライヤであったのはいつかを示すキャッシュ−（時間）間隔の（順序付けされた）リストとして表わされる。このリストの要素は次のように分類できる。（Ａ）上記時間間隔の後に転送リクエストをキャッシュがサービスした要素、および（Ｂ）上記時間間隔の前に転送リクエストをキャッシュがサービスした要素、である。
【００７３】
当業者は、この詳細な説明のおかげで、キャッシュラインがプロセッサによって放棄されることは決してなくその場合リストは無限に長くなるかまたはリストの最後の要素が間隔ではなく準間隔であることを、理解するであろう。前者の場合、リストを、転送リクエストの完了後に間隔が全体的に存在している点から切離せばよい。後者の場合は以下の論点を裏付ける。
【００７４】
最初の要素はクラスＡでなければならず、最後の要素はクラスＢでなければならない。リストには、クラスＡおよびＢの要素ｘおよびｙに対応する少なくとも２つのキャッシュＸおよびＹが存在してｘとｙが隣合う（ＸはＹにキャッシュラインを直接提供する）ようにしなければならない。このため、Ｘは、キャッシュラインの放棄後に転送リクエストをサービスし、Ｙは、キャッシュラインの受信前に転送リクエストをサービスする。
【００７５】
しかしながら、Ｙが、キャッシュライン受信前にリクエストをサービスするためには、転送リクエストを見てから、キャッシュラインに対するそのピアツーピアリクエストを送信しなければならない。さもなければ、転送リクエストのサービスは、そのリクエストの完了まで遅延されるであろう。そのリクエストは転送リクエスト後に送信されたので、Ｘは、（リクエストネットワークの順序付け特性により）転送リクエストを見た後にＹのリクエストも見るはずである。よって、ＸはＹへのキャッシュラインの放棄前に転送リクエストを見るはずであり、ＸはクラスＡに入れない。このように、不運の想定は矛盾しているので有効でない。
【００７６】
仲介リクエスト
キャッシュは、キャッシュラインへのアクセス権を取得するために割当仲介リクエストをゲートウェイに送信する。Ｐ２Ｐリクエストと異なり、仲介リクエストの成功は保証されている。ゲートウェイによって実行される具体的な動作は、プロセッサ間コヒーレンスプロトコルに強く依存する。
【００７７】
図４Ａを参照しながら先に述べたように、仲介リクエストの例は、（１）キャッシュラインへの読取アクセスに対する仲介リクエスト（ｍＲＴＳ）、（２）キャッシュラインへの読取−書込アクセスに対する仲介リクエスト（ｍＲＴＯ）、および（３）仲介ライトバック（以下で説明する）を含む。
【００７８】
これも先に述べたように、プロセッサ内においてキャッシュがキャッシュラインの単独の保持部であることを示すキャッシュ状態が、プロセッサ上の他のキャッシュがこのキャッシュラインを保持しないことを保証することにはならないということを、Ｐ２Ｐプロトコルは保証する。この論点について非常に重要なのは、キャッシュが一旦ｐＲＴＯによって無効化されると、キャッシュラインを取り戻すためには、ピアツーピアリクエストを発行するしかないこと、および、ピアツーピアリクエストは、リクエストネットワークの順序付け特性によってすべてのキャッシュのｐＲＴＯの後ろに順序付けされることである。
【００７９】
仲介リクエストは、Ｐ２Ｐリクエストを発行せずにキャッシュラインを取得するための「裏口」を提供する。プロトコルに対する制限も変更もない仲介リクエストは、プロセッサ内排他特性を壊す可能性がある。
【００８０】
同一のキャッシュラインについて同時リクエストを発行する３つのキャッシュ、すなわち、キャッシュＡ、キャッシュＢ、およびキャッシュＣを伴なう以下のシナリオについて考える。最初にキャッシュラインを保持しているキャッシュはない。キャッシュＡはｐＲＴＯを実行している。キャッシュＢはｐＲＴＳを実行している。キャッシュＣはｍＲＴＯを実行している（ｍＲＴＳでも違いはない）。
【００８１】
以下のイベントのシーケンスが保証するものは下記の通りである。
１．キャッシュＢはｐＲＴＳを送信する。
【００８２】
２．キャッシュＡはｐＲＴＯを送信する。
３．キャッシュＣはｐＲＴＯに対しＡｃｋで応答する。
【００８３】
４．キャッシュＣはｍＲＴＯを送信する。
５．ゲートウェイは、ｍＲＴＯを処理し、ＤａｔａＥをキャッシュＣに送信する。
【００８４】
６．キャッシュＣは、ＤａｔａＥを受信しこれを状態ＥＣでインストールする。
７．キャッシュＣは、ｐＲＴＳに対しＤａｔａＥで応答し、その状態をＳＣにダウングレードする。
【００８５】
８．キャッシュＡはｐＲＴＳに対しＮａｃｋで応答する。
９．キャッシュＢは、レスポンスを受信し、キャッシュラインを状態ＸＣでインストールする。
【００８６】
１０．キャッシュＢは、ｐＲＴＯに対しＤａｔａＥで応答し、その状態をＩＣにダウングレードする。
【００８７】
１１．キャッシュＡは、レスポンスを受信し、キャッシュラインを状態ＥＣでインストールする。
【００８８】
この時点で存在するのは状態ＥＣのキャッシュであり、別のキャッシュは状態ＳＣであり、排他的特性を妨害する。
【００８９】
Ｐ２Ｐリクエストが最初に送信されず（別のキャッシュエージェントによる／からの）他のＰ２Ｐリクエストが仲介リクエストの完了まで否定応答されないのであれば、仲介リクエストがプロセッサ状態ＩＣから送信されないようにすることが、可能な１つの解決策である。もう１つの解決策はより繊細である。キャッシュＢがｐＲＴＳを発行することに注目する。ｐＲＴＯにこの効果はないであろう。なぜなら、キャッシュＣを無効化するであろうからである。（より多くのキャッシュを含めて）同様の反例を生じさせる一系統のリクエストが存在し得るが、サプライヤを状態ＳＣにしたままでキャッシュラインを転送するためには、この系統の中の１つのリクエストがｐＲＴＳでなければならない。
【００９０】
ｐＲＴＯは「サプライヤ系統」においてｐＲＴＳよりも後ろであるため、ｐＲＴＯが完了する前にｐＲＴＳはそのレスンポンスをすべて受信しているはずである。また、ｐＲＴＳは、ｐＲＴＯの送信後にｐＲＴＯのリクエスタでサービスされるはずである。ｐＲＴＳがｐＲＴＯの送信前にサービスされた場合、（ネットワークの順序付け特性により）ｐＲＴＳはすべてのキャッシュにおいてｐＲＴＯの前に見られるであろう。ｐＲＴＳは、キャッシュを、このキャッシュがｐＲＴＯに応答した後に、状態ＳＣのままにしておくことはできない（そうなるためにはｐＲＴＯがｐＲＴＳよりも前に見られていなければならない）。
【００９１】
したがって、ｐＲＴＯのペンディング中にｐＲＴＯリクエスタがｐＲＴＳをサービスすることは明らかである。このサービスに、図３Ｂのテーブル３．５に示される最終アップデートもキャンセルさせた場合（すなわちステップ３１４をスキップ）、ｐＲＴＯは失敗に終わり（この例では状態ＥＣではなく状態ＸＣになる）、排他的特性は妨害されない。
【００９２】
犠牲化およびライトバック
キャッシュエントリがキャッシュラインを格納しなければならず空いている適切なエントリがないとき、エントリの内容を追い出す必要がある。この追い出しを「犠牲化（Victimization）」と呼ぶ。追い出されたキャッシュラインのデータを他の場所に転送させるのであれば、犠牲化はライトバックである。プロトコル定義という観点からすると、犠牲化の理由は無視される。
【００９３】
図６Ａは、本発明の１つ以上の実施形態に従うフローチャートを示す。図６Ａに示されるプロセスは、犠牲化および起こり得るライトバックに対応する。図６Ａに示されるプロセスは、追い出しプロセスと、キャッシュラインに対する転送リクエストの間のインタラクションも示す。図６Ａに示されるプロセスは、たとえば、図１を参照しながら先に述べたシステム（１００）の中の１つ以上の構成要素によって実行されてもよい。図６Ａに示される１つ以上のステップを、省略してもよく、繰返してもよく、および／または本発明の異なる実施形態間で順序が異なるように実行してもよい。したがって、本発明の実施形態は、図６Ａに示されるステップの特定の数および並びに限定されるとみなされてはならない。
【００９４】
最初に、追い出しキャッシュのためのキャッシュエージェントは、キャッシュラインに対するＰ２Ｐライトバックリクエスト（ｐＷＢ）を、部分的に順序付けされたリクエストネットワークを通して、ローカルプロセッサ上のスレーブキャッシュにブロードキャストする（ステップ６０２）。上記のように、ステップ６０２を引起すのは、追い出しキャッシュに空いている適切なエントリがないことである可能性がある。加えて、追い出しキャッシュは今まではリクエスト側のキャッシュであった可能性があり、最近取得されたキャッシュラインを格納するためには追い出しが必要である。キャッシュが状態ＳＣのキャッシュラインを保持している場合、このキャッシュは静かにこの状態をＩＣにダウングレードしてもよい。これにより、効果的にエントリに空きができ、図６Ａに示されるプロセスを実行する必要はなくなる。しかしながら、追い出しキャッシュがキャッシュラインをサプライヤ状態で保持する場合、静かに犠牲化することは許可されない。
【００９５】
ステップ６０３で、追い出しキャッシュのキャッシュエージェントは、キャッシュラインに対する転送リクエストを受信する。この転送リクエストは、プロセッサ上のローカルゲートウェイからのものである（キャッシュエージェントは転送リクエストをいつ受信するかについては制御できない）。加えて、転送リクエストは、キャッシュラインに対するｐＷＢリクエストがまだペンディングである間に受信される。追い出しキャッシュのキャッシュエージェントは、転送リクエストを、後の処理のために格納してもよい（すなわちキャッシュエージェントは転送リクエストに対する応答を遅延させる）。
【００９６】
ステップ６０４で、ローカルプロセッサ上のスレーブキャッシュの各キャッシュエージェントは、ｐＷＢリクエストに対するレスポンスを発行し、および／またはスレーブキャッシュ内のキャッシュラインのプロセッサ内状態をアップデートする。ｐＷＢに対するレスポンスは、スレーブキャッシュ内のキャッシュラインの現在のプロセッサ内状態に基づく。図６Ｃのテーブル６．１は、スレーブキャッシュのキャッシュエージェントによる、ｐＷＢへの起こり得るレスポンスを示す。たとえば、図６．１に示されるように、スレーブキャッシュがプロセッサ内状態ＳＣのキャッシュラインを保持している場合、スレーブキャッシュのキャッシュエージェントは、ｐＷＢに応答して確認応答ライトバック（ＡｃｋＷＢ）を発行してもよい。ＡｃｋＷＢもＰｕｌｌＷＢも、部分的に順序付けされたリクエストネットワーク上で伝搬する。スレーブキャッシュ内のキャッシュラインの新たなプロセッサ内状態は、ＳＣに設定される。
【００９７】
ステップ６０５で、スレーブキャッシュからすべてのレスポンスを一旦受信すると、追い出しキャッシュは、（図４Ａおよび図４Ｂを参照しながら先に述べた）転送リクエストに応答する。当業者は、この詳細な説明のおかげで、ステップ６０５がステップ６０３と結び付いておりしたがってステップ６０５は任意であってもよいことを理解するであろう。
【００９８】
ステップ６０６で、キャッシュラインの追い出しがまだ必要であるか否かが判断される。具体的には、転送リクエストは、追い出すべきキャッシュラインのプロセッサ内状態を、ＳＣまたはＩＣに変更した可能性がある。上記のように、キャッシュは、状態ＳＣのキャッシュラインを保持する場合、この状態を静かにＩＣにダウングレードし得る。追い出しはもはや必要でないと判断された場合、このプロセスはステップ６１８に進む。しかしながら、追い出しキャッシュからのキャッシュラインの追い出しがまだ必要であると判断された場合は、プロセスはステップ６０８に進む。
【００９９】
ステップ６０８で、ｐＷＢに対する少なくとも１つのＡｃｋＷＢを、スレーブキャッシュのキャッシュエージェントから、部分的に順序付けされたリクエストネットワークを通して受信したか否かが判断される。少なくとも１つのＡｃｋＷＢを受信したと判断された場合、このプロセスはステップ６１０に進む。ＡｃｋＷＢレスポンスは受信していないと判断された場合、このプロセスはステップ６１２に進む。
【０１００】
ステップ６１２において、ｐＷＢに対する少なくとも１つのＰｕｌｌＷＢレスポンスを、スレーブキャッシュのキャッシュエージェントから、部分的に順序付けされたリクエストネットワークを通して受信したか否かが判断される。少なくとも１つのＰｕｌｌＷＢを受信したと判断された場合、このプロセスはステップ６１４に進む。ＰｕｌｌＷＢレスポンスは受信していないと判断された場合、このプロセスはステップ６２０に進む。
【０１０１】
ｐＷＢは、プロセッサ上のすべてのスレーブキャッシュからＮａｃｋを受信した場合、失敗である。前進を保証するために、追い出しキャッシュは、ゲートウェイに対して仲介ライトバック（ｍＷＢ）を発行することができる（ステップ６２０）。仲介割当リクエストについて、これは、ｐＷＢの失敗が伝えられているゲートウェイによって暗黙的に行なわれてもよい。割当仲介リクエストとは異なり、仲介ライトバックは、状態ＭＣ、ＲＣ、ＥＣ、またはＰＣからしか発行されないであろう（すなわち、追い出しキャッシュがサプライヤ状態でありプロセッサ内でキャッシュラインを保持するキャッシュが他にないとき）。
【０１０２】
他のサプライヤ状態で仲介ライトバックをサポートするには、他のキャッシュ内のキャッシュラインの無効化（より複雑である）か、または、ゲートウェイが転送ライトバックをブロードキャストすることが必要であろう。ゲートウェイは、キャッシュラインが変更された場合に（プロセッサ間状態ＭまたはＯ）キャッシュラインをメモリにライトバックするといったような、プロセッサ間プロトコルで必要なものは何でも実行する。
【０１０３】
ステップ６１４において、部分的に順序付けされたリクエストネットワークを通して２つ以上のＰｕｌｌＷＢが受信された場合、追い出しキャッシュのキャッシュエージェントは、ＰｕｌｌＷＢを発行したスレーブキャッシュを選択し、選択されたスレーブキャッシュにレスポンスを送信し、追い出しキャッシュ内のキャッシュラインをプロセッサ内状態ＩＣにダウングレードする。選択されたスレーブキャッシュに送信されるレスポンスは、ダウングレード前の追い出しキャッシュ内のキャッシュラインのプロセッサ内状態によって決まる。図６Ｃのテーブル６．２は、異なるプロセッサ内状態について選択されたスレーブキャッシュに送信されるレスポンスを示す。たとえば、追い出しキャッシュがＤＣのキャッシュラインを保持する場合、追い出しキャッシュのキャッシュエージェントは、選択されたスレーブキャッシュに、ＤａｔａＭを送信する。
【０１０４】
ステップ６１０において、部分的に順序付けされたリクエストネットワークを通して２つ以上のＡｃｋＷＢが受信された場合、追い出しキャッシュのキャッシュエージェントは、ＡｃｋＷＢを発行したスレーブキャッシュを選択し、選択されたスレーブキャッシュにレスポンスを送信し、追い出しキャッシュ内のキャッシュラインをプロセッサ内状態ＩＣにダウングレードする。選択されたスレーブキャッシュに送信されるレスポンスは、ダウングレード前の追い出しキャッシュ内のキャッシュラインのプロセッサ内状態によって決まる。図６Ｃのテーブル６．２は、異なるプロセッサ内状態について選択されたスレーブキャッシュに送信されるレスポンスを示す。たとえば、追い出しキャッシュがＯＣのキャッシュラインを保持する場合、追い出しキャッシュのキャッシュエージェントは、選択されたスレーブキャッシュに、ＡｃｋＯを送信する。
【０１０５】
ステップ６１８において、選択されなかったすべてのスレーブキャッシュのキャッシュエージェントにＮａｃｋが送信される。
【０１０６】
図６Ａに鑑みると、追い出しキャッシュのキャッシュエージェントは、レスポンスの受信だけを待ち、次に、受信した転送リクエストに応答し、転送リクエスト後に受信したＡｃｋＷＢまたはＰｕｌｌＷＢに応答する前に、必要な状態変更を実施する。ｐＷＢのペンディング中に転送リクエストに対するレスポンスを遅延させる理由は、プロセッサ上のキャッシュライン１つ当たりアクティブであるｐＷＢが１つだけになることを保証することにある。同一のキャッシュラインに対して複数のｐＷＢをアクティブにすると、最初のｐＷＢに対してＡｃｋＷＢで応答したキャッシュが第２のｐＷＢに対して同じことをするためのリソースを持っていない場合に、問題が生じる。そのキャッシュラインを無効化してＮａｃｋで応答することが必要であるが、そのキャッシュラインを未処理のＡｃｋＷＢで無効化することは禁じられている。他の手段によってこの問題に対処することは可能であるが、プロトコルを複雑にするよりも、めったに発生しない厄介な状況をスローダウンさせる方が良いと思われる。
【０１０７】
図６Ｂは、本発明の１つ以上の実施形態に従うフローチャートを示す。図６Ｂに示されるプロセスは、犠牲化中にスレーブキャッシュが行なう動作および起こり得るライトバックを説明する。図６Ｂに示されるプロセスはまた、追い出しプロセスと、キャッシュラインに対する転送リクエストの間のインタラクションも説明する。図６Ｂに示されるプロセスは、たとえば、図１を参照しながら先に述べたシステム（１００）の中の１つ以上の構成要素によって実行されてもよい。図６Ｂに示される１つ以上のステップを、省略してもよく、繰返してもよく、および／または本発明の異なる実施形態間で順序が異なるように実行してもよい。したがって、本発明の実施形態は、図６Ｂに示されるステップの特定の数および並びに限定されるとみなされてはならない。
【０１０８】
最初に、キャッシュラインに対するＰ２Ｐライトバックリクエスト（ｐＷＢ）を、スレーブキャッシュのキャッシュエージェントが、部分的に順序付けされたリクエストネットワークを通して受信する。上記のように、ｐＷＢは、追い出しキャッシュに空いている適切なエントリがないときに、発行される。
【０１０９】
ステップ６３４において、スレーブキャッシュのキャッシュエージェントは、スレーブキャッシュ内のキャッシュラインのプロセッサ内状態に応じて、このｐＷＢに対し、Ｎａｃｋ、ＡｃｋＷＢ、またはＰｕｌｌＷＢで、順序付けされたリクエストネットワークを通して応答する。加えて、スレーブキャッシュ内のキャッシュラインのプロセッサ内状態は、ｐＷＢに応じてアップデートされる。図６Ｃのテーブル６．１は、ｐＷＢに対するスレーブキャッシュのさまざまなレスポンス、およびキャッシュラインに割当てられる新たなプロセッサ内状態を示す。たとえば、テーブル６．１に示されるように、ｐＷＢを受信したときにスレーブキャッシュ内のキャッシュラインの現在のプロセッサ内状態がＩＣであれば、スレーブキャッシュのキャッシュエージェントは、部分的に順序付けされたリクエストネットワークを通してＰｕｌｌＷＢで応答し得る。スレーブキャッシュ内のキャッシュラインの新たな状態は依然としてＩＣである。
【０１１０】
ステップ６３６において、スレーブキャッシュが順序付けされたリクエストネットワークを通してｐＷＢに対して応答した後に、スレーブキャッシュは、ローカルまたは外部転送リクエストを受信する。この転送リクエストは、プロセッサ上のローカルゲートウェイからのものである（転送リクエストはローカルゲートウェイによって発行されるので、スレーブキャッシュのキャッシュエージェントは、転送リクエストがいつ到着するかについては制御できない）。加えて、この転送リクエストは、キャッシュラインに対するＡｃｋＷＢまたはＰｕｌｌＷＢがまだペンディングである間に受信される。スレーブキャッシュのキャッシュエージェントは、後の処理のために、この転送リクエストを格納してもよい（すなわち、キャッシュエージェントは、キャッシュラインに対するＡｃｋＷＢまたはＰｕｌｌＷＢが依然としてペンディングの間はキャッシュラインに対する転送リクエストへの応答を遅延させる）。
【０１１１】
ステップ６３８において、ＡｃｋＷＢまたはＰｕｌｌＷＢに対するレスポンスを、スレーブキャッシュは追い出しキャッシュから受信する。図６Ｃのテーブル６．２に示されるように、このレスポンスは、追い出しキャッシュ内のキャッシュラインのプロセッサ内状態に基づく。たとえば、スレーブキャッシュは、追い出しキャッシュから、ＡｃｋＷＢおよびＰｕｌｌＷＢそれぞれに応じてＡｃｋＭまたはＤａｔａＥを受信し得る。
【０１１２】
ステップ６４０において、データレスポンス（たとえばＤａｔａＭ，ＤａｔａＯ，ＤａｔａＥ，ＤａｔａＳ）の場合、キャッシュラインはスレーブキャッシュにインストールされる。加えて、データレスポンスおよび応答確認（たとえばＡｃｋＭ，ＡｃｋＯ，ＡｃｋＥ，ＡｃｋＳ）双方について、スレーブキャッシュ内のキャッシュラインのプロセッサ内状態は、図６Ｃのテーブル６．３に従ってアップデートされる。
【０１１３】
ステップ６４２において、この時点でＡｃｋＷＢまたはＰｕｌｌＷＢはスレーブキャッシュにとってペンディングではない（すなわちＡｃｋＷＢまたはＰｕｌｌＷＢは完了している）ので、スレーブキャッシュは転送リクエストに応答する。
【０１１４】
図３Ａ、図６Ａ、および図６Ｂに鑑みると、同一のキャッシュラインに対するアクティブなＰ２Ｐ割当リクエストを有するキャッシュはいずれも、ｐＷＢに対しＮａｃｋで応答する（図６Ｃのテーブル６．１において特定された状態変更を行なう）。ペンディング中のｐＷＢを有するキャッシュはいずれも、同一のキャッシュラインに対する受信したＰ２Ｐ割当リクエストに対して、同一のキャッシュラインに対する第２の同時のｐＷＢを防止するために、Ｎａｃｋで応答する。ペンディング中のＡｃｋＷＢまたはＰｕｌｌＷＢを有するキャッシュはいずれも、受信したピアツーピア割当リクエストに対して、Ｎａｃｋで応答する。
【０１１５】
全キャッシュライン書込リクエスト
キャッシュライン全体の書込が意図されている場合、元のキャッシュラインデータを書込み側のキャッシュに送信することは、ネットワークの帯域幅の浪費である。キャッシュラインデータを伴なわないキャッシュ間でアクセス権を転送するにすぎない「ｐＲＴＷ」リクエストは、機能しない。Ｎａｃｋを受信したことが原因で、または、ｐＲＴＳを見たことが原因で、リクエスタが書込アクセスを取得できない場合、キャッシュラインデータは失われる。したがって、ｐＲＴＷリクエストの挙動は、ｐＲＴＯリクエストと全く同じでなければならない。ｐＲＴＷがある１つの理由は、自動ｍＲＴＷを可能にするためである。
【０１１６】
プロセッサ間プロトコルが、キャッシュラインデータを転送せずに書込アクセスの転送をサポートするのであれば、ｍＲＴＷは、全キャッシュライン書込について、プロセッサ間の帯域幅要求を減じることにつながり得る。
【０１１７】
ゲートウェイタグに関連するその他の動作
上記のように、本発明の１つ以上の実施形態において、ゲートウェイは、ゲートウェイタグを用いることにより、ピアツーピアリクエストの失敗を正確に予測し、ピアツーピアリクエストそのものから失敗が示されるのを見る前に、失敗のプロセッサ間サービスを開始することができる。これによって、全キャッシュミス処理におけるピアツーピアリクエスト処理のレイテンシをなくすことができる。
【０１１８】
また、上記のように、本発明の１つ以上の実施形態において、ゲートウェイはまた、ゲートウェイタグを用いることにより、ピアツーピアリクエストが失敗した時点でプロセッサ間リクエストは不要であると判断して、その後すぐに対応する転送リクエストの発行に進むことができる。しかしながら、この失敗は、コンフリクトが原因で生じたはずである。
【０１１９】
本発明の１つ以上の実施形態において、ゲートウェイタグの追い出しに関し、ゲートウェイタグ構造をキャッシュの構造を正確に模倣したものにすることは不可能であろう−ゲートウェイタグの結合性（associativity）は過剰になるであろう。十分な結合性がなければ、割当プロセッサ間リクエストを実行するときにゲートウェイタグエントリを割当てることは不可能かもしれない。この場合は、ゲートウェイタグにスペースを作るためにキャッシュからの別のキャッシュラインを追い出すことが必要であろう。
【０１２０】
本発明の１つ以上の実施形態において、これは、プロセッサ間ライトバックまたは犠牲化が行なわれている間に、ゲートウェイがｆＣＰＩをキャッシュにブロードキャストしキャッシュラインをゲートウェイ内のバッファに格納することによって実現可能である（典型的なプロセッサ間プロトコルは、犠牲化の効果が他のプロセッサのリクエストに対して可視になるまで、他のプロセッサによって行なわれ得るアクセスについてキャッシュラインを保持することを必要とする）。
【０１２１】
本発明の１つ以上の実施形態において、もう１つの方策は、（ｐＷＢの変形である特別なｐＷＢＡを用いて）プロセッサ上での別のキャッシュへのキャッシュラインの転送を抑制する一方で、サプライヤキャッシュに犠牲化を強制的に開始させることである。
【０１２２】
ｐＷＢに対する犠牲キャッシュ指定
本発明の１つ以上の実施形態において、ｐＷＢの処理は、複数のキャッシュがＰｕｌｌＷＢおよび／またはＡｃｋＷＢで応答するとき、非常に高いコストがかかる。また、ＰｕｌｌＷＢの発行はＰｕｌｌＷＢ発行側のキャッシュを汚染する可能性がある。これを軽減するためには、ＰｕｌｌＷＢで応答することを許可される唯一のキャッシュである特定のキャッシュをｐＷＢのターゲットにできることが有用である。
【０１２３】
ｐＷＢの変形であるｐＷＢＡも、指定された犠牲キャッシュを除いてすべてのキャッシュからのＡｃｋＷＢを抑制することができる。
【０１２４】
本発明の１つ以上の実施形態において、どの犠牲キャッシュも全く指定することができず、すべてのキャッシュをＮａｃｋに強制し共有コピーを無効化することも有用であろう。これは、プロセッサ上のすべてのキャッシュからキャッシュラインを強制排出させるｍＷＢ（すなわち仲介ライトバック）との関連で使用することができる。
【０１２５】
本発明の実施形態は、使用されているプラットフォームとは関係なく事実上どのような種類の計算システム上でも実現し得る。たとえば、計算システムは、１つ以上のモバイル装置（たとえばラップトップコンピュータ、スマートフォン、携帯情報端末、タブレットコンピュータ、またはその他のモバイル装置）、デスクトップコンピュータ、サーバ、サーバシャーシ内のブレード、または、少なくとも、最小の処理能力、メモリ、および入出力装置を備えて本発明の１つ以上の実施形態を実行するその他の種類の１つまたは複数の計算装置であってもよい。たとえば、図７に示されるように、計算システム（７００）は、１つ以上のコンピュータプロセッサ（７０２）、関連するメモリ（７０４）（たとえばランダムアクセスメモリ（ＲＡＭ）、キャッシュメモリ、フラッシュメモリ等）、１つ以上の記憶装置（７０６）（たとえばハードディスク、コンパクトディスク（ＣＤ）ドライブまたはデジタル多用途ディスク（ＤＶＤ）ドライブ等の光学ドライブ、フラッシュメモリスティック等）、および多数のその他の要素および機能を含み得る。コンピュータプロセッサ（７０２）は、命令を処理するための集積回路であってもよい。たとえば、コンピュータプロセッサは、プロセッサの１つ以上のコアまたはマイクロコアであってもよい。計算装置（７００）はまた、タッチスクリーン、キーボード、マウス、マイク、タッチパッド、電子ペン、またはその他の種類の入力装置等の１つ以上の入力装置（７１０）を含み得る。さらに、計算システム（７００）は、スクリーン（たとえば液晶表示装置（ＬＣＤ）、プラズマディスプレイ、タッチスクリーン、陰極線管（ＣＲＴ）モニタ、プロジェクタ、またはその他の表示装置）、プリンタ、外部記憶装置、またはその他の種類の出力装置等の、１つ以上の出力装置（７０８）を含み得る。出力装置のうちの１つ以上は、入力装置と同一であっても異なっていてもよい。計算システム（７００）はネットワーク（７１４）（たとえばローカルエリアネットワーク（ＬＡＮ）、インターネット等のワイドエリアネットワーク（ＷＡＮ）、モバイルネットワーク、またはその他の種類のネットワーク）に、ネットワークインターフェイス接続（図示せず）を介して接続されてもよい。入出力装置は、コンピュータプロセッサ（７０２）、メモリ（７０４）、および記憶装置（７０６）に、（たとえばネットワーク（７１２）を介して）ローカルまたは遠隔接続されてもよい。多様な種類の計算システムがあり、上記入出力装置はその他の形態を取るものであってもよい。
【０１２６】
本発明の実施形態を実行するためのコンピュータ読取可能なプログラムコードの形態のソフトウェア命令は、その全体または一部が、一時的にまたは恒久的に、ＣＤ、ＤＶＤ、記憶装置、ディスケット、テープ、フラッシュメモリ、物理メモリ、またはその他任意のコンピュータ読取可能な記憶媒体等の、非一時的なコンピュータ読取可能な媒体上に格納されてもよい。具体的に、上記ソフトウェア命令は、プロセッサによって実行されると本発明の実施形態を実行するように構成されたコンピュータ読取可能なプログラムコードに相当するものであってもよい。
【０１２７】
さらに、上記計算システム（７００）の１つ以上の要素は、遠隔場所に位置しネットワーク（７１４）を通してその他の要素に接続されてもよい。さらに、本発明の実施形態は、複数のノードを有する分散システム上で実現されてもよい。この分散システムでは、本発明の各部分を分散システム内の異なるノード上に配置してもよい。本発明の一実施形態において、このノードは別個の計算装置に相当する。これに代えて、このノードは、関連する物理メモリを有するコンピュータプロセッサに相当するものであってもよい。これに代えて、このノードは、共有メモリおよび／またはリソースを有するコンピュータプロセッサまたはコンピュータプロセッサのマイクロコアに相当するものであってもよい。
【０１２８】
本発明を限られた数の実施形態について説明してきたが、当業者は、この開示のおかげで、本明細書に開示されている発明の範囲から外れていないその他の実施形態を考案できることを理解するであろう。したがって、本発明の範囲は、以下の請求項によってのみ限定されるはずである。
【図１】
0005986307.tif 000002
【図２Ａ】
0005986307.tif 000003
【図２Ｂ】
0005986307.tif 000004
【図３Ａ】
0005986307.tif 000005
【図３Ｂ】
0005986307.tif 000006
【図４Ａ】
0005986307.tif 000007
【図４Ｂ】
0005986307.tif 000008
【図４Ｃ】
0005986307.tif 000009
【図５】
0005986307.tif 000010
【図６Ａ】
0005986307.tif 000011
【図６Ｂ】
0005986307.tif 000012
【図６Ｃ】
0005986307.tif 000013
【図７】
0005986307.tif 000014