(57)【要約】競合解決手法は、各ノードが要求全てを、そのノードがそれ自体の要求を行った後に監視する場合に、競合する要求側のうちの少なくとも１つによって競合全てを検知し得るような整合性を備える。ラインが排他的状態、修正状態又はフォワード状態にある場合、一意の複製を保持しているノードで競合が解決される。競合の解決の勝者と場合によっては敗者が、競合をホーム・ノードに通知し、ホーム・ノードは競合通知を対にし、転送命令を出して、全ての要求ノードが最終的には要求データを受信するようにする。要求キャッシュ・ラインが非キャッシュ状態にあるか、共有状態にのみ存在する場合、ホーム・ノードはキャッシュ・ノードの複製を備え、競合を解決する。一実施例では、全ての応答の後の、応答メッセージが受信されるまでのブラックアウト期間は、競合ノード全てが関係する競合を競合ノードの全てが分かることを可能にする。【特許請求の範囲】
【請求項１】
方法であって：
第１ピア・ノードから、マルチノード・システムにおける複数のノードに、データ・ブロックの複製の要求を送信する工程；
該第１ピア・ノードによって、データ・ブロックの複製の要求を第２ピア・ノードから受信する工程；
該受信要求が該送信要求と競合しているか否かを判定する工程；及び
該受信要求が該送信要求と競合している場合に、競合が存在しているということを示すメッセージを該データ・ブロックのホーム・ノードに送信する工程；
を備えることを特徴とする方法。
【請求項２】
請求項1記載の方法であって、該受信要求が該送信要求と競合しているか否かを判定する工程が：
該受信要求と該送信要求が同じデータを要求しているか否かを判定する工程；
を備えることを特徴とする方法。
【請求項３】
請求項1記載の方法であって、更に：
該受信要求が該送信要求と競合している場合に、競合が存在しているということを示すメッセージを該データ・ブロックの第３ピア・ノードに送信する工程；
を備えることを特徴とする方法。
【請求項４】
請求項1記載の方法であって、該ホーム・ノードへの該メッセージが：
メッセージを第３ピア・ノードに送信することを該ホーム・ノードに行わせて、該要求データを該第１ピア・ノードに送信することを該第３ピア・ノードに行わせる工程；
を備えることを特徴とする方法。
【請求項５】
請求項1記載の方法であって：
該第１ピア・ノードが該第２ピア・ノードと、複数のピア・ノードを表すピア・エージェントを介して通信することを特徴とする方法。
【請求項６】
請求項1記載の方法であって：
該第１ピア・ノードが該ホーム・ノードと、複数ノードを表すピア・エージェントを介して通信することを特徴とする方法。
【請求項７】
装置であって：
複数ピア・エンティティとホーム・エンティティとを有するシステムにおける複数のシステム・エンティティと結合される対象のインタフェース；及び
該インタフェースと結合されて、データ・ブロックの複製の要求を該ピア・エンティティのうちの1つ又は複数に送信する制御回路；
を備え；
該制御回路は、別のピア・エンティティから受信される競合要求メッセージを検知する対象であり；
競合要求メッセージに応じて、該制御回路は、競合を示すメッセージを該データ・ブロックに相当するホーム・ノードに送出することを特徴とする装置。
【請求項８】
請求項7記載の装置であって、該ピア・エンティティが：
1つ又は複数のピア・ノード；及び
複数のピア・ノードを表す1つ又は複数のピア・エージェント；
を備えることを特徴とする装置。
【請求項９】
請求項7記載の装置であって、該ホーム・エンティティが：
ホーム・ノード；  
を備えることを特徴とする装置。
【請求項１０】
請求項7記載の装置であって、該ホーム・エンティティが：
複数ノードを表すホーム・エージェント；  
を備えることを特徴とする装置。
【請求項１１】
請求項7記載の装置であって、更に：
該インタフェースと結合されるプロセッサ；  
を備えることを特徴とする装置。
【請求項１２】
請求項11記載の装置であって、該制御回路が：
該プロセッサ内部に含まれることを特徴とする装置。
【請求項１３】
請求項7記載の装置であって、該制御回路が：
要求データの複製を要求側ピア・ノードに、該要求が該制御回路によって行われる要求と競合しない場合に備えることを特徴とする装置。
【請求項１４】
方法であって：
第１ピア・ノードによって、第１要求メッセージを送信して、データ・ブロックの複製を、少なくとも、ピア・ノードと、該要求データ・ブロックに相当するホーム・ノードとに要求する工程；
第２ピア・ノードによって、第２要求メッセージを送信して、該データ・ブロックの複製を、少なくとも、該第１ピア・ノードと、該ホーム・ノードに要求し、かつ第３ピア・ノードに要求する工程；
該第３ピア・ノードから該第１ピア・ノードに、該データ・ブロックの複製を送信する工程；
該第１ピア・ノードから該ホーム・ノードに、該第３ピア・ノードからの該データ・ブロックの受信を示すメッセージを送信する工程；
該第１ピア・ノードから該第２ピア・ノードに、該データ・ブロックの複製を送信する工程；及び
該第２ピア・ノードから該ホーム・ノードに、該第２ピア・ノードからの該データ・ブロックの受信を示すメッセージを送信する工程；
を備えることを特徴とする方法。
【請求項１５】
請求項14記載の方法であって、該データ・ブロックが：
キャッシュ・ライン；
を備えることを特徴とする方法。
【請求項１６】
請求項14記載の方法であって：
該第１要求メッセージが、複数ノードを表すエージェントに送信されることを特徴とする方法。
【請求項１７】
請求項14記載の方法であって：
該第２要求メッセージが、複数ノードを表すエージェントに送信されることを特徴とする方法。
【請求項１８】
請求項14記載の方法であって、該第３ピア・ノードから該第１ピア・ノードに、該データ・ブロックの複製を送信する工程が：
該第３ピア・ノードによって確保される該データ・ブロックがある場合に、該データ・ブロックの状態を変える工程；
を備えることを特徴とする方法。
【請求項１９】
請求項14記載の方法であって、該第１ピア・ノードから該第２ピア・ノードに、該データ・ブロックの複製を送信する工程が：
該第１ピア・ノードによって確保される該データ・ブロックがある場合に、該データ・ブロックの状態を変える工程；
を備えることを特徴とする方法。
【請求項２０】
方法であって：
第１ピア・ノードからのデータ・ブロックの複製を要求する第１要求メッセージを、少なくとも、第２ピア・ノードと、第３ピア・ノードと、該データ・ブロックに相当するホーム・ノードとに送信する工程；及び
第２ピア・ノードから、該データ・ブロックの複製の第２要求を、該第１ピア・ノード、該第３ピア・ノード及び該ホーム・ノードに送信する工程；
を備え；
該第２要求メッセージは該第２ノードが該第１要求メッセージを受信する前に送信され；
更に、該第１ピア・ノードから該第２ピア・ノードに、該第１要求メッセージと該第２要求メッセージとの間の競合を示すメッセージを送信する工程；
該第３ピア・ノードから該第１ピア・ノードに、該データ・ブロックの複製を送信する工程；
該第１ピア・ノードから該ホーム・ノードに、該第１要求メッセージと該第２要求メッセージとの間の競合を示すメッセージを送信する工程；及び
該ホーム・ノードから該第１ピア・ノードに、該データ・ブロックの複製を該第２ノードに送信することを該第１ピア・ノードに行わせる工程；
を備えることを特徴とする方法。
【請求項２１】
請求項20記載の方法であって、更に：
該第１ピア・ノードから該第２ピア・ノードに、該データ・ブロックの複製を送信する工程；
を備えることを特徴とする方法。
【請求項２２】
請求項21記載の方法であって、更に：
該第２ピア・ノードから該第１ピア・ノードに、該第２要求メッセージと該第１要求メッセージとの間の競合を示すメッセージを送信する工程；
を備えることを特徴とする方法。
【請求項２３】
請求項21記載の方法であって、該第１ピア・ノードから該第２ピア・ノードに、該データ・ブロックの複製を送信する工程が：
該第１ピア・ノードによって確保される該データ・ブロックがある場合に、該データ・ブロックの状態を変える工程；
を備えることを特徴とする方法。
【請求項２４】
請求項20記載の方法であって、該データ・ブロックが：
キャッシュ・ライン；
を備えることを特徴とする方法。
【請求項２５】
請求項20記載の方法であって：
該第１要求メッセージが、複数ノードを表すエージェントに送信されることを特徴とする方法。
【請求項２６】
請求項20記載の方法であって：
該第２要求メッセージが、複数ノードを表すエージェントに送信されることを特徴とする方法。
【請求項２７】
方法であって：
第１ピア・ノードからのデータ・ブロックの複製を要求する第１要求メッセージを、第２ピア・ノードと、第３ピア・ノードと、該データ・ブロックに相当するホーム・ノードとに送信する工程；
を備え；
該第３ピア・ノードへの該メッセージは遅延しており；
更に、第２ピア・ノードから、該第１ピア・ノード、該第３ピア・ノード及び該ホーム・ノードに、該データ・ブロックの複製を要求する第２要求を、送信する工程；
を備え；
該第２要求メッセージは、該遅延第１メッセージが該第３ピア・ノードによって受信される前に該第２ピア・ノードによって送信され；
更に、該第２ピア・ノードから該第１ピア・ノードに、該第１メッセージと該第２メッセージとの間の競合を示すメッセージを送信する工程；
該第３ピア・ノードから該第２ピア・ノードに、該データ・ブロックの複製を送信する工程；
該第２ピア・ノードから該ホーム・ノードに、該第１要求メッセージと該第２要求メッセージとの間の競合を示すメッセージを送信する工程；及び
該ホーム・ノードから該第２ピア・ノードに、該データ・ブロックの複製を該第１ピア・ノードに送信することを該第２ピア・ノードに行わせる工程；
を備えることを特徴とする方法。
【請求項２８】
請求項27記載の方法であって、更に：
該第２ピア・ノードから該第１ピア・ノードに、該データ・ブロックの複製を送信する工程；
を備えることを特徴とする方法。
【請求項２９】
請求項27記載の方法であって、該データ・ブロックが：
キャッシュ・ライン；
を備えることを特徴とする方法。
【請求項３０】
請求項27記載の方法であって：
該第１ノードが該第１要求メッセージを、複数ノードを表すエージェントに送信することを特徴とする方法。
【請求項３１】
請求項27記載の方法であって：
該第２ノードが該第２要求メッセージを、複数ノードを表すエージェントに送信することを特徴とする方法。
【請求項３２】
請求項27記載の方法であって、該第３ピア・ノードから該第２ピア・ノードに、該データ・ブロックの複製を送信する工程が：
該第１ピア・ノードによって確保される該データ・ブロックがある場合に、該データ・ブロックの状態を変える工程；
を備えることを特徴とする方法。
【請求項３３】
方法であって：
データ・ブロックの複製を要求する第１メッセージを、第１ピア・ノードから、第２ピア・ノードとホーム・ノードとに送信する工程；
第２ピア・ノードから、該第１ピア・ノード及び該ホーム・ノードに、該データ・ブロックの複製の第２要求を送信する工程；
該第１ピア・ノードから該第２ピア・ノードに、該第１メッセージと該第２メッセージとの間の競合を示すメッセージを送信する工程；
該第２ピア・ノードから該第１ピア・ノードに、該第２ノードが該データ・ブロックの有効な複製を有しないということを示すメッセージを送信する工程；
該ホーム・ノードから該第１ピア・ノードに、該データ・ブロックの複製を送信する工程；及び
該ホーム・ノードから該第１ピア・ノードに、該データ・ブロックの複製を該第２ノードに送信することを該第１ピア・ノードに行わせる工程；
を備えることを特徴とする方法。
【請求項３４】
請求項33記載の方法であって、更に：
該第２ピア・ノードから該第１ピア・ノードに、該第２メッセージと該第１メッセージとの間の競合を示すメッセージを送信する工程；
を備えることを特徴とする方法。
【請求項３５】
請求項33記載の方法であって、更に：
該第１ピア・ノードから該第２ピア・ノードに、該第１ピア・ノードが該データ・ブロックの有効な複製を有しないということを示すメッセージを送信する工程；
を備えることを特徴とする方法。
【請求項３６】
請求項35記載の方法であって、更に：
該第２ピア・ノードから該ホーム・ノードに、該第１要求と該第２要求との間の競合を示すメッセージを送信する工程；
を備えることを特徴とする方法。
【請求項３７】
請求項33記載の方法であって、該データ・ブロックが：
キャッシュ・ライン；
を備えることを特徴とする方法。
【請求項３８】
請求項33記載の方法であって：
該ホーム・ノードが該データ・ブロックの複製と該メッセージとを送信して、該データ・ブロックの複製を単一のメッセージとして送信することを該第１ピア・ノードに行わせることを特徴とする方法。
【請求項３９】
請求項33記載の方法であって：
該第１メッセージが、複数ノードを表すエージェントに送信されることを特徴とする方法。
【請求項４０】
請求項39記載の方法であって：
該第２メッセージが、複数ノードを表す該エージェントに送信されることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、キャッシュ・メモリに関し、特に、マルチキャッシュのマルチプロセッサ・システムにおける分散競合解決に関する。
【背景技術】
【０００２】
電子システムが複数のキャッシュ・メモリを含む場合、利用可能なデータの有効性を維持しなければならない。このことは通常、キャッシュ・コヒーレント・プロトコルによってデータを操作することによって実現される。キャッシュ数及び/又はプロセッサ数が増加するにつれ、キャッシュ・コヒーレント状態を維持するうえでの複雑度も増大する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
複数の構成部分（例えば、キャッシュ・メモリ、プロセッサ）が同じデータ・ブロックを要求する場合、複数の構成部分間の競合を、データの有効性を維持する方法で解決しなければならない。現行のキャッシュ・コヒーレント・プロトコルは通常、競合解決の役目を担う単一の構成部分を有する。しかし、システムの複雑度が増大するにつれ、競合解決を行ううえでの単一構成部分に対する依存は全体的なシステム性能を低下させ得る。
【０００４】
図1a乃至図1eは、マルチノード・システムにおける競合解決の概念を図示する。ノード110、120及び130は、キャッシュ・メモリにおける要求データ（例えば、キャッシュ・ライン）の複製を記憶することが可能なピア・ノードである。ホーム・ノード140は、要求データのホーム（H）ノードである。図1a乃至図1eの例では、ピア・ノード110及び120は要求データの無効な複製を記憶するか、複製を何ら記憶せず、ピア・ノード130はメモリにもう一度書き込まれていない、要求データの修正複製を記憶する。ホーム・ノードはメモリにおけるデータの元の複製を記憶するか、修正がもう一度メモリに書き込まれる場合にはデータの修正バージョンを記憶する。
【０００５】
図1aに示すように、ピア・ノード120はデータ要求メッセージを送信してデータ・ブロック、例えば、キャッシュ・ライン、の複製を要求する。データ要求メッセージは、ピア・ノード110とピア・ノード130とに送信される。しかし、ピア・ノード130へのデータ要求メッセージには遅延が生じる。この遅延は、例えば、利用可能な帯域幅の不足、バッファリングの考慮点などによってもたらされ得る。
【０００６】
ピア・ノード110は、ピア・ノード110が要求データの有効な複製を有しない旨をピア・ノード120に示す有効な複製なしのメッセージによってピア・ノード120からのデータ要求メッセージに応答する。ピア・ノード120がデータ要求メッセージを送信してからある程度経過した時点で、ピア・ノード110は、図1cに示すように、ピア・ノード120によって要求されたデータと同様なデータを要求するデータ要求メッセージをピア・ノード120及び130に送信する。
【０００７】
ピア・ノード120は、有効複製なしのメッセージをピア・ノード110に、データ要求メッセージに応じて備える。ピア・ノード130は要求データをピア・ノード110に備える。ピア・ノード130によって保持されている、データの複製があれば、その複製は無効とマーキングされ、ピア・ノード110によって記憶されるデータの複製は修正としてマーキングされる。
【０００８】
ピア・ノード130がピア・ノード110からのデータ要求に応答し、データの複製を無効化した時点からある程度経過した時点で、ピア・ノード130は、図1cに示すように、ピア・ノード120からの遅延データ要求メッセージを受信する。データ要求メッセージに応じて、ピア・ノード130は、有効な複製なしのメッセージをピア・ノード120に備える。なお、ピア・ノード130が記憶しているデータの状態は、元のデータ要求メッセージの時点からデータ要求メッセージにピア・ノード130が応答する時点まで変動している。
【０００９】
ピア・ノード110及び130はピア・ノード120からのデータ要求メッセージに有効な複製なしのメッセージによって応答するので、要求データの有効なキャッシュ複製が何らないことが分かっているピア・ノード120は、ホーム・ノード140にデータの複製を要求する。よって、図1dに示すように、ピア・ノードは読み取りメッセージをホーム・ノード140に送信する。ホーム・ノード140は要求データをメモリから取り出し、データをピア・ノード120に備える。ピア・ノード120は更に、要求データを排他的状態において記憶する。
【００１０】
図1eに示すように、図1a乃至1eに示すメッセージのシーケンスは２つの非互換の、データ・ラインの複製をもたらす。記載例では、ピア・ノード110はデータの複製を修正状態において記憶し、ピア・ノード120はデータを排他的状態において記憶する。しかし、ピア・ノード120によって記憶される複製はピア・ノード120に排他的でない。よって、マルチノード・システムは、キャッシュ競合を解決する機構を備えない限り、特定の状況下で非互換のデータ複製をもたらし得る。
【課題を解決するための手段】
【００１１】
マルチノード・システムにおける分散キャッシュ・コヒーレント競合解決の手法について説明する。下記明細書では、説明の目的で、数多くの特定の詳細を表して、本発明を徹底的が分かるようにしている。しかし、本発明はこれらの特定の詳細の一部なしで実施可能であるということは当業者に明らかとなる。別の場合には、構造及び装置を構成図形式で表して本発明を分かりにくくしないようにしている。
【００１２】
要求メッセージ
以下のメッセージは、要求側ノードからのデータ/動作要求である。これらのメッセージは、システムのノード全てにブロードキャストされる。
【００１３】
ポート読み取りライン（PRL）：これは、例えばキャッシュ・ラインなどのデータ・セグメントの複製の要求である。
【００１４】
ポート読み取り無効化ライン（PRIL）：これは、データの、提供側のノードの複製が無効化されるデータ・セグメントの複製の要求である。これは、「request-for-ownership」としても表すことが可能である。
【００１５】
ポート書き込みライン（PWL）：このメッセージは、データ（例えば、修正キャッシュ・ライン）をメモリに書き込ませる。このメッセージは、「dirty  eviction」としても表し得る。
【００１６】
ポート無効化ライン（PIL）：このメッセージは、指定データの状態を共有から排他的に変更させる。
【００１７】
ポート書き込み無効化ライン（PWIL）：このメッセージは、データをメモリに書き込ませ、データの標的複製を無効化させる。
【００１８】
応答メッセージ
以下のメッセージは、ピア（すなわち、非ホーム）・ノードから要求側ノードに上記要求に応じて送出されるメッセージである。
【００１９】
無効状態応答（IACK）：このメッセージは、応答を送出するノードが、要求データの無効複製を有するか、要求データの複製を何ら有していない場合の要求（PRL、PRIL、PWL、PIL、PWIL）への応答である。
【００２０】
共有状態応答（SACK）：このメッセージは、応答を送出するノードが共有状態における要求データの複製を有する場合の要求への応答である。
【００２１】
データ受信の応答（DACK）：このメッセージは、要求側ノードがデータを受信したノードに対して要求側ノードによって送出される。これは、READメッセージ又はCNCLメッセージを要求側ノードがホーム・ノードに送出し、ホーム・ノードからXFR/XFRIメッセージ又はACKメッセージを受信した後に送出される。
【００２２】
競合：このメッセージは、要求キャッシュ・ラインに対して同時に待ち状態にある要求が存在しているということを示す。
【００２３】
ホーム・ノードへのメッセージ
このメッセージはホーム・ノードにピア・ノードによって送信される。
【００２４】
読み取り（競合）：このメッセージは、ホーム・ノードからデータを要求し、競合がある場合には競合を全て示す。このメッセージは、受信メッセージの何れもDATAメッセージでない場合に、全ての応答がピア・ノードによって受信された後に送出される。
【００２５】
CNCL（競合）：このメッセージは、ピア・ノードにおけるヒットに応じてホーム・ノードに送出され、競合がある場合には競合を全て示す。このメッセージはホーム・ノードのプリフェッチ動作を取り消す。このメッセージは、全ての応答がピア・ノードによって受信され、それらのうちの１つがDATAメッセージであった後に送出される。
【００２６】
データ：このメッセージは、PWL要求とPWIL要求とのデータをもう一度書き込むのに用いられる。
【００２７】
ホーム・ノードからのメッセージ
このメッセージはホーム・ノードからピア・ノード及び/又は要求側ノードに送出される。
【００２８】
データ：このメッセージは要求データを含み、要求側ノードによって用いられる対象のデータの状態（M/E/F/S）を示し得る。
【００２９】
転送（XFR）：このメッセージは、受信ノードに、メッセージに示すノードにデータを転送させる。ホーム・ノードはこのメッセージを、データの現行オーナがデータを標的ノードに転送することを要求する競合条件をホーム・ノードが通知された場合に要求データの現行オーナにホーム・ノードがこのメッセージを送出する。未解決競合要求が、データ転送を開始する場合に現行オーナがラインを無効化しなければならないということを表すPRILメッセージであるということをホーム・ノードが判定する場合にXFRメッセージの代わりにXFRIメッセージが送出される。一実施例では、エポックにおいて最初にCNCLメッセージを送出するノードは現行オーナである。エポックは、第１データ要求とデータ要求全ての解決との間の期間である。ホーム・ノードがメモリからのデータをノードに送出する場合、そのノードが現行オーナである。XFR/XFRIメッセージの送出は標的ノードを現行オーナにさせる。一実施例では、標的ノードは、READメッセージ又はCNCLメッセージにおけるホーム・ノードに備えられる競合リストから選択される。
【００３０】
応答（ACK）：このメッセージは、要求データが要求側ノードに送出されたということを示す。ホーム・ノードがACKメッセージを送出する場合、現行エポックは終結する。
【００３１】
ウェイト：このメッセージは、受信ノードに、更にメッセージを送出する前に停止させる。
【００３２】
MESIFプロトコルの概要
キャッシュ・コヒーレント状態を備える、スヌーピング（現在は多くの場合対称マルチプロセッシングSMPと呼ばれている）とディレクトリ（多くの場合分散共有メモリDSMと呼ばれている）との、2つの基本的な手法がある。基本的な違いは、メタ情報、すなわちキャッシュ・ラインの複製が記憶されている場所に関する情報の配置及びアクセスに関する。
【００３３】
キャッシュをスヌーピングするよう、情報は、キャッシュ複製自体とともに配布される、すなわち、キャッシュ・ラインの各有効複製は、新たな方法でキャッシュ・ラインをアクセスする上での許可を何れかのノードが要求する際にはいつでもその役目を認識しなければならないそのユニットによって保持される。データがキャッシュされない場合に記憶されるレポジトリは特定の場所、通常は固定の場所にある。この場所はラインがキャッシュされる場合でも有効な複製を含み得る。しかし、このノードの場所は通常、要求側ノードには既知でない、すなわち、要求側ノードは単に、要求キャッシュ・ラインのアドレスを、必要な許可とともにブロードキャストし、複製を有し得るノードは全て、一貫性が維持されるようにするよう、応答しなければならず、非キャッシュ複製を含むノードは、別のノード（ピア・ノード）が何れも応答しない場合に応答する。
【００３４】
ディレクトリ・ベース手法の場合、非キャッシュ・データが記憶されている固定場所に加えて、キャッシュ複製が存在する場所を示す固定場所、ディレクトリがある。キャッシュ・ラインを新たな方法でアクセスするために、ノードは、通常、非キャッシュ・データ・リポジトリを含むノードと同じノードである、ディレクトリを含むノードと通信しなければならず、これによって、主記憶複製が有効である場合にデータを応答側ノードが備えることを可能にする。そのようなノードはホーム・ノードとして表す。
【００３５】
ディレクトリは2つの方法で配布される。第１に、主記憶データ（非キャッシュ・レポジトリ）は多くの場合、ノード間で配布され、ディレクトリも同様に配布される。第２に、ラインがキャッシュされているか否かに関する情報と、ラインがキャッシュされている場合には単一複製が存在する場所に関する情報との、できる限り少ないものをホーム・ノードで保持して、メタ情報自体も配布し得る。例えば、SCIはこの手法を用い、キャッシュ複製を含む各ノードは、キャッシュ複製を備えている別のノードに対するリンクを維持し、よって併せて完全なディレクトリを維持する。
【００３６】
メタ情報が保持されている単一の場所はなく、スヌーピング手法はブロードキャストに依存するので、ノードは全て、各照会について通知されなければならず、各ノードはその役目を担ってコヒーレント状態が維持されるようにする。このことは、別のノードがデータを備えている際に応答しないようにホーム・ノードに通知する介入メッセージを含む。
【００３７】
スヌーピング手法は、応答が直接的でありかつすばやいという効果を有するが、ノード全てが照会全てを見る必要があるのでスケーリングは良好でない。ディレクトリ手法は、元来、よりスケーリング可能であるが、多くの場合、ポイント・ツー・ポイント通信において3つのノードが関係する、より高度な応答を必要とする。
【００３８】
本明細書及び特許請求の範囲記載の基本MESIFプロトコルは、単一の直列化バスの制約なしでスヌーピング・プロトコルを備える。スヌーピング・キャッシュ・プロトコルのように、MESIFは、コヒーレント状態を維持するよう、データのキャッシュ複製を備えているノードに依存する。同期・集中ブロードキャストではなくポイント・ツー・ポイント・リンクを用いることは、タイム・ワープ、すなわち別のノードから視るとイベントが別の順序で生じているように見えるということ、の課題をもたらす。MESIFプロトコルは、潜在的なエラーが発生する可能性がある時点を認識し、そのエラーが正しく処理されるということを確かめて、ターム・ワープを正しく処理する。ホーム・ノードの考え方は主に、非キャッシュ複製が存在している場所を判定するものであるが、ホーム・ノードは、競合とタイム・ワープの課題を解決するために、全てのトランザクションにおいて、すなわちクリティカル・パス上にない場合でも、参加する。この手法の同時ブロードキャスト特性のために、MESIFは、データのキャッシュ可能な複製を大半の場合に、考えられる最小のレーテンシ、すなわち単一の、要求と応答との往復において取得して、スヌーピング・プロトコルに関連した低レーテンシを達成する。
【００３９】
基本MESIFプロトコルでは、ピア・ノード全てとホーム・ノードとに初期要求をブロードキャストする。複製は、状態E、状態F、又は状態Mにキャッシュされる場合、応答に含まれる。要求が満たされた旨をホーム・ノードに通知する第２メッセージが更にホーム・ノードに送出される。要求ラインがキャッシュされていない場合又はS状態の複製しか存在しない場合には、ホーム・ノードに送出される第２要求が、ホーム・ノードがこの時点では既にそのメモリからフェッチした場合がある先行要求を確認するのに用いられる。いずれの場合でも、ホーム・ノードは、同期化の目的と競合解決の目的で第２要求に応答しなければならない（。ホーム・ノードは、更に、同様に第１要求に応答しなければならないが、これらは場合によっては組み合わせることが可能である。）なお、ホーム・ノードは、1つ又は複数のキャッシュを有し得るので、何れかの別のノードと同様に初期の要求に応答し得る。
【００４０】
競合は分散的な方法で処理される。タイム・ワープの課題は競合を検知することを困難にするが、それは個々の要求を、任意の長時間、遅延させることが可能であるからである。競合は、しかし、各ノードが、要求を行った後に競合を監視する場合に検知することになる。何れのノードも競合を検知する場合も検知しない場合もあるが、少なくとも一方は検知することになる。ノードは全て、データを供給するか、複製を有していない（か、一部の場合には、自らが有している複製を供給していない）旨を示すことによってブロードキャスト要求に応答しなければならないので、応答は競合の表示を含み得るものであり、競合ノードは競合を検知することになる。
【００４１】
全ての応答を待つのではなくデータが到着するとすぐにデータをノードが用いることを可能にすることによって問題が生じる。よって、データの複製を受信するノードは、受信するとすぐに内部でデータを用いることが可能であるが、データを用いる効果が、ノードがホームから確認を受信するまでシステムの残りに対して視える状態にされない場合がある。確認は、ノードがそのコピーを別のノードに転送しなければならないという旨の命令と、ノードをそれ自体のキャッシュから場合によっては取り戻す命令を含む場合もある。
【００４２】
最後に、ノードが、キャッシュ・データを供給することによって、別のノードからの要求に応答する場合、データを転送したということに応答する、ホーム・ノードからの応答を受信するまで、同じキャッシュ・ラインに受信する全ての別の要求を据え置き、それによって、全てのノードが（場合によっては書き込み可能な）キャッシュ・ラインの転送の同じ順序に従うようにする。
【００４３】
ホーム・ノードは、非キャッシュ・データのリポジトリであるが、要求を生成するプロセッサを有し、1つ又は複数のキャッシュを含む場合もある。何れかの別のノードのように、ホーム・ノード・プロセッサが失敗する場合、ホーム・ノードは、要求を全ての別の（ピア）ノードにブロードキャストしなければならず、ホーム・ノードに到着する何れかの別の要求を処理することになるように、要求を内部で処理しなければならない。なお、これは、ホーム・ノードがメッセージをそれ自体（ホーム・ノード）に明示的に送出しないという点で特別な場合である。更に、局所でキャッシュされているデータの外部要求が到着する場合、ホーム・ノードは、ホーム・ノードからの後の応答があいまいでないようにする方法で応答しなければならない。すなわち、ホーム・ノードは、データを供給することによって初期の要求に応答する場合があるが、ホーム・ノードは第２要求にホーム・ノードとして応答しなければならないということもある。
【００４４】
本明細書及び特許請求の範囲記載の利用に適したMESIFプロトコルの種々の実施例の更に詳細の、擬似コード・ベースの記述は添付書類Aとして、本明細書及び特許請求の範囲に添付する。
【００４５】
投機的分散競合解決の概要
一般的に、キャッシュ・コヒーレント・プロトコルは、種々のキャッシュ・ラインやその他のデータ・ブロックの状態を規則正しく変化させるために競合解決を必要とする。本明細書及び特許請求の範囲記載の競合解決手法はシーケンスの整合性を備える、すなわち、キャッシュ・ラインのうちの単一の、修正可能な複製のみが何れかの時点で存在することが可能であり、別の複製が読み取り可能である場合には、キャッシュ・ラインの複製は何れも修正することが可能でない。キャッシュ・ラインの複製を修正する競合要求は、したがって、シーケンスの整合性を維持するために解決されなければならない。
【００４６】
一実施例では、競合は時間の特性を用いて解決される。すなわち、遅延に係わらず、２つのノードは何れも、他方の前にキャッシュ・ラインを要求することが可能でない。よって、競合は、各ノードが要求全てを、そのノードがそれ自体の要求を行った後に監視する場合に競合する要求側のうちの少なくとも１つによって検知することが可能である。
【００４７】
一実施例では、ラインが排他的（E）状態、修正（M）状態又はフォワード（F）状態にある場合、競合は、一意の複製を保持しているノードで解決される。競合解決の勝者と、場合によっては競合解決の敗者は、競合をホーム・ノードに通知し、ホーム・ノードは競合通知を対にして、転送命令を出して、全ての要求側ノードが最終的に要求データを受信するようにする。一実施例では、要求キャッシュ・ラインが非キャッシュ状態にあるか、共有（S）状態にしかない場合、要求キャッシュ・ラインのホーム・ノードが要求データの複製を備え、競合を解決する。
【００４８】
一実施例では、本明細書及び特許請求の範囲記載の分散競合解決は、5つの状態（修正、排他的、共有、無効及びフォワード）のうちの１つがキャッシュ・ラインのキャッシュ複製に関連しているMESIFプロトコルとして表すキャッシュ・プロトコルの一部である。一実施例では、応答メッセージがホーム・ノードから受信されるまでの、要求に対する応答全ての後のブラックアウト期間は、ノードが関係している競合を競合ノード全てが分かることが可能になる。ブラックアウト期間は、キャッシュにおけるデータの利用を制限しないが、データが別のキャッシュに伝搬することは妨げる。
【００４９】
以下では、マルチノード・システム内部のノードに関して記載する。一実施例では、ノードは、内部キャッシュ・メモリ、外部キャッシュ・メモリ及び/又は外部メモリを有するプロセッサを含む。別の実施例では、ノードは、別の電子システムと相互接続される電子システム（例えば、コンピュータ・システム、移動体機器）である。別の種類のノード構成も用い得る。以下の例では、破線は先行して送出したメッセージを表し、実線は説明しているメッセージを表す。図面を明瞭化を図るために、メッセージ群（例えば、PRIL及び、相当するIACK）が解決される場合、メッセージを表す線はもう図面には含めていない。
【発明を実施するための最良の形態】
【００５０】
本発明は制約ではなく例として、添付図面の図において図示し、同様な参照数字は同様な構成要素を表す。
【実施例】
【００５１】
図２a乃至図2dは、共有ライン競合の概念を示す図である。図2a乃至図2dの例では、ピア・ノード210もピア・ノード220もデータ・ブロック（例えば、キャッシュ・ライン）の複製を要求する。ピア・ノード230は要求データ・ブロックの利用可能な複製をM状態において記憶する。上記処理は、ピア・ノード230が要求データをS状態又はF状態において記憶させる場合にも該当する。
【００５２】
図2a乃至図2dの種々のメッセージに関連した番号付け（例えば、1.PRIL、7.IACK）は競合の例を備える目的で適切な順序付けを備える。図2a乃至図2dに示すまさにそのタイミング関係やその他の記載例（すなわち、図3a乃至図3d、図4a乃至図4d、図5a乃至図5d、図6a乃至図6d）は必要でない。
【００５３】
図2aに示すように、ピア・ノード210は、PRILメッセージをピア・ノード220並びに230、及びホーム・ノード240に送信することによってデータ・ブロックを要求する。ピア・ノード210は、PRLメッセージを用いて同じデータ・ブロックを要求することも可能であり、その場合には、ピア・ノード230はその複製を要求メッセージに応じて無効化しないことになる。ピア・ノード220は、ピア・ノード220が要求データ・ブロックの有効な複製を記憶していない旨を示すIACKメッセージによってPRILメッセージに応答する。
【００５４】
ホーム・ノード240は要求対象データのホーム・ノードとしての役目を担う、すなわち、ノード240は、要求対象データがキャッシュされない場合に記憶される非キャッシュ・メモリ（例えば、主メモリ）に関連する。例えば、ホーム・ノード240はプロセッサ、キャッシュ・メモリ及びランダム・アクセス・メモリ（RAM）であり得るものであり、RAMはデータの非キャッシュ記憶場所を備える。
【００５５】
図2bは、ピア・ノード210によって先行して要求されるデータ・ブロックを要求するピア・ノード210並びに230及びホーム・ノード240にPRILメッセージを送信するピア・ノード220を示す。上記のように、データはPRLメッセージを用いて要求することも可能である。図2a乃至図2dの競合をPRILメッセージによって示しているが、不整合な結果が起こり得る、要求メッセージの何れかの組み合わせは競合をもたらす。
【００５６】
ピア・ノード220によるPRILメッセージの送信とほぼ同時に、ピア・ノード230は、DataMメッセージをピア・ノード210に送信することによってピア・ノード210からのPRILメッセージに応答する。DataMメッセージは、ピア・ノード210に、要求データの複製を備え、データを修正（M）状態においてピア・ノード210に記憶させる。別の状態、例えば、フォワード（F）状態を規定し得る。ピア・ノード230によって記憶される要求データの複製の状態は、M状態から無効（I）状態に変更される。
【００５７】
図2cに示すように、DataMメッセージのピア・ノード230からの受信に応じて、ピア・ノード210はCNCL()メッセージをホーム・ノード240に送出する。CNCL()メッセージは、メモリからの要求データ・ブロックの取り出しを、取り出しが開始された場合、取り消す。ホーム・ノード240は、CNCL()メッセージの受信に応答するACKメッセージによってピア・ノード210に応答し、そのことはピア・ノード210からのPRILメッセージの処理の完了を示す。
【００５８】
ACKメッセージのホーム・ノード240からの受信に応じて、ピア・ノード210は、ピア・ノード230からの要求データの受信に応答するDACKメッセージをピア・ノード230に送信する。ピア・ノード230からのデータの受信と、DACKメッセージのピア・ノード230への送信との間の期間が、データ・ブロックが別のノードに送信されないブラックアウト期間である。ブラックアウト期間中には、ピア・ノード210はピア・ノード220からのPRILメッセージには応答しない。同様に、ピア・ノード230は、ブラックアウト期間中にはピア・ノード220からのPRILメッセージに応答しない。
【００５９】
図2dに示すように、ピア・ノード210はDataMメッセージをピア・ノード220に送信して、要求データの複製をピア・ノード220に備え、データの複製をM状態においてピア・ノード220に記憶させる。別の種類のメッセージ（例えばDataF、DataS）を用いて要求データをピア・ノード220に備えることが可能である。ピア・ノード210は、DataMメッセージがPRILメッセージに対する応答であるので、確保されるデータの複製があればその複製をI状態にあるものとしてマーキングするものでもある。確保される要求データ複製は、例えばPRLメッセージによって無効化されないことになる。ピア・ノード220は、CNCL()メッセージをホーム・ノード240に送出して、非キャッシュ・メモリからの要求データの何れかの取り出しを取り消すものでもある。ホーム・ノード240は、更なるメッセージを送出する前にピア・ノード220に停止させるWAITメッセージによって応答する。
【００６０】
上記処理の間の何れかの時点で、ピア・ノード230及びエージェント290は、ピア・ノード230に記憶されていないか、IACKメッセージをピア・ノード220にI状態において記憶されているデータ・ブロックを要求するPRILメッセージに応じて送出する。ピア・ノード220は、DACKメッセージをピア・ノード210に送信することによってピア・ノード210からのDataMメッセージに応答する。DACKメッセージは、ピア・ノード210及びピア・ノード220からの競合PRILメッセージの解決を終了する。
【００６１】
図3a乃至図3dは、ほぼ同時に（互角の条件で）要求を出すことによってもたらされる共有ライン競合の概念を示す。図3aに示すように、ピア・ノード210は、ピア・ノード220並びに230及びホーム・ノード240にデータ・ブロックを要求するPRILメッセージを送信する。特定の短い時間の後か、同時に、ピア・ノード220は、同じデータ・ブロックを要求するPRILメッセージをピア・ノード210並びに230及びホーム・ノード240に送出する。
【００６２】
要求データを受信する前に別のピア・ノードからPRILメッセージを受信することに応じて、ピア・ノード210は、競合するPRILメッセージのソースであるピア・ノード220にCONFLICTメッセージを送出する。CONFLICTメッセージは、競合に関係している1つ又は複数の別のピア・ノードに、競合を識別するピア・ノードからの要求競合の存在を通信する。同様に、ピア・ノード220は、PRILメッセージの受信に応じてピア・ノード210にCONFLICTメッセージを、要求データを受信する前に送出する。図3bはピア・ノード210とピア・ノード220との間のCONFLICTメッセージの送信を示す。
【００６３】
図3cに示すように、ピア・ノード230は要求データをピア・ノード210にDataMメッセージにおいて備え、確保されるデータの複製があればその複製をI状態にマーキングする。ピア・ノード210は要求データを受信し、それをM状態において記憶する。ピア・ノード210は更に、CNCL(220)メッセージをホーム・ノード240に送出する。CNCL(220)メッセージはホーム・ノード240に、メモリからの要求データの取り出しを取り消させ、送出側ノード（すなわち、ピア・ノード210）とピア・ノード220との間で競合が存在する旨をホーム・ノード240に示す。
【００６４】
CNCL(220)メッセージに応じて、ホーム・ノード240はXFER(220)メッセージをピア・ノード210に送出する。XFER(220)メッセージは、データの複製をピア・ノード220に転送することをピア・ノード210に行わせる。一実施例では、ピア・ノード210はデータの複製をピア・ノード220に送出する前に要求データ・ブロックの利用及び/又は修正を行う。別の実施例では、ピア・ノード210はデータの複製をピア・ノード220に直ちに送出する。XFER(220)メッセージのホーム・ノード240からの受信に応じて、ピア・ノード210は、要求データの受信を応答するDACKメッセージをピア・ノード230に送出する。
【００６５】
図3dに示すように、ピア・ノード210からのDACKメッセージの受信に応じて、ピア・ノード230は、ピア・ノード230が要求データの有効な複製を記憶しない旨を示すIACKメッセージをピア・ノード220に送出する。ピア・ノード230は、第１PRILメッセージ（すなわち、ピア・ノード210からのPRILメッセージ）が解決されるまで第２PRILメッセージ（すなわち、ピア・ノード220からのPRILメッセージ）に応答しない。ホーム・ノード240からのXFER(220)メッセージに応じて、ピア・ノード210は要求データの複製をピア・ノード220にDataMメッセージにおいて送出する。ピア・ノード210はI状態において確保されるデータの何れかの複製をマーキングして、ピア・ノード220はM状態に受信されるデータの複製を記憶する。
【００６６】
ピア・ノード220はREAD(210)メッセージを送出して、メモリからの要求データの取り出しを停止し、ピア・ノード220がピア・ノード210との競合を検知した旨を示す。ホーム・ノード240は、ピア・ノード220に送信されるWAITメッセージによってREAD(210)メッセージに応答する。WAITメッセージは、何れかの後続メッセージを送信する前に所定の期間、ピア・ノード220に停止させる。ピア・ノード220はピア・ノード210にDACKメッセージを送出して要求データの受信を示す。
【００６７】
図4a乃至図4dは、複数の要求のうちの１つの遅延によってもたらされる競合ライン競合の概念の図を備える。図4aに示すように、ピア・ノード220は、データ・ブロックを要求するPRILメッセージをピア・ノード210並びに230及びホーム・ノード240に送信する。ピア・ノード230を対象とするPRILメッセージには遅延が生じている。遅延は、システム・レーテンシ、パケット損傷、又は何れかの別の理由の結果であり得る。ピア・ノード210は、ピア・ノード210が要求データの有効な複製を記憶しない旨を示すIACKメッセージによってPRILメッセージに応答する。
【００６８】
図4bに示すように、ピア・ノード210は、同じデータ・ブロックを要求するPRILメッセージをピア・ノード220並びにピア・ノード230及びホーム・ノード240に送信する。ピア・ノード220からの遅延PRILメッセージは、ピア・ノード210からのPRILメッセージと同時かその後にピア・ノード230によって受信される。ピア・ノード230は、要求データの複製をピア・ノード210に備え、データをM状態においてピア・ノード210に記憶させるDataMメッセージによってピア・ノード210からのPRILメッセージに応答する。ピア・ノード230は要求データの確保複製があれば、その複製をI状態においてマーキングする。ピア・ノード220は、ピア・ノード220が２つのノードによる要求の間での競合を検知した旨をピア・ノード210に示すCONFLICTメッセージによってピア・ノード210からのPRILメッセージに応答する。
【００６９】
図4cに示すように、ピア・ノード210はCNCL(220)メッセージをホーム・ノード240に送出して、メモリからの要求データの取り出しを取り消す。CNCL(220)メッセージは、ピア・ノード210とピア・ノード220との間で競合が存在する旨をホーム・ノード240に示すものでもある。ホーム・ノード240は、要求データの複製をピア・ノード220に送出することをピア・ノード210に行わせるXFER(220)メッセージによってCNCL(220)メッセージに応答する。一実施例では、ピア・ノード210は、データの複製をピア・ノード220に送出する前に要求データ・ブロックの利用及び/又は修正を行う。別の実施例では、ピア・ノード210はデータの複製をピア・ノード220に直ちに送出する。
【００７０】
ピア・ノード210はDACKメッセージをピア・ノード230に送信して要求データの受信に応答する。ピア・ノード210はDataMメッセージをピア・ノード220に送出して要求データの複製を備えるものでもある。ピア・ノード220は要求データをM状態において記憶する一方、ピア・ノード210は要求データの何れかの残りの複製をI状態においてマーキングする。
【００７１】
図4dに示すように、ピア・ノード230は、ピア・ノード210からのDACKメッセージの受信に応じてIACKメッセージをピア・ノード220に送出する。IACKメッセージは、ピア・ノード230が要求データの有効な複製を記憶していない旨を示す。ピア・ノード220はREAD(210)メッセージをホーム・ノード240に送出する。READ(210)メッセージはメモリからの要求データの取り出しを取り消し、ピア・ノード220がピア・ノード210との競合を有する旨をホーム・ノード240に示す。
【００７２】
ホーム・ノード240は、何れかの後続メッセージを送出する前に所定の期間、ピア・ノード220に停止させるWAITメッセージによってREAD(210)メッセージに応答する。ピア・ノード220はピア・ノード210からのDataMメッセージに、ピア・ノード210からの要求データの受信に応答するDACKメッセージによって応答する。
【００７３】
図5a乃至図5dは無効なライン競合の概念を示す。図5aに示すように、ピア・ノード210はPRILメッセージを送信してデータ・ブロックを、ピア・ノード220並びに230及びホーム・ノード240に要求する。図5bに示すように、ピア・ノード210からのPRILメッセージと同時か、その直後に、ピア・ノード220は、ピア・ノード210及び230と、ホーム・ノード240とに同じデータを要求するPRILメッセージを送信する。
【００７４】
図5cに示すように、ピア・ノード230は、ピア・ノード230が要求データの有効な複製を記憶していない旨を示すIACKメッセージによってピア・ノード210からのPRILメッセージに応答する。同様に、ピア・ノード230は、IACKメッセージによってピア・ノード220からのPRILメッセージに応答する。ピア・ノード220は、CONFLICTメッセージによってピア・ノード210からのPRILメッセージに応答して、ピア・ノード210とピア・ノード220との間の競合の識別を通信する。同様に、ピア・ノード210は、CONFLICTメッセージによってピア・ノード220からのPRILメッセージに応答する。
【００７５】
図5dに示すように、ピア・ノード210はREAD(220)メッセージをホーム・ノード240に送出する。READ(220)メッセージは、要求データをメモリから取り出したホーム・ノード240から先行して要求されたデータを読み取る。ホーム・ノード240は、DataXFER(220)メッセージによってピア・ノード210に要求データを備える。一実施例では、ホーム・ノード240は2つの種類のメッセージ（すなわち、Data及びXFER）からの情報を単一のメッセージ・パケットに含める。この「piggybacking」手法は競合を解決するのに必要な帯域幅を削減することが可能である。
【００７６】
DataXFER(220)メッセージは、ピア・ノード210に要求データを備え、更に、要求データをピア・ノード220に転送することをピア・ノード210に行わせる。ピア・ノード210が要求データを受信する場合、要求データはM状態において記憶される。
【００７７】
要求データを受信した後、ピア・ノード210は要求データの複製をDataMメッセージによってピア・ノード220に送出する。ピア・ノード210によって確保される要求データの何れかの複製はI状態においてマーキングされる。ピア・ノード220は要求データをM状態において記憶し、DACKメッセージによって要求データの受信にピア・ノード210に対して応答する。
【００７８】
図6a乃至図6dは、複数の要求のうちの１つの遅延によってもたらされる無効ライン競合の概念を示す。図6aに示すように、ピア・ノード220は、データ・ブロックを要求するPRILメッセージをピア・ノード210並びに230及びホーム・ノード240に送信する。ピア・ノード230宛てのPRILメッセージは遅延している。遅延は例えば、システム・レーテンシ、パケット損傷、又は何れかの別の理由の結果であり得る。ピア・ノード210は、ピア・ノード210が要求データの有効複製を記憶しない旨を示すIACKメッセージによってPRILメッセージに応答する。
【００７９】
図6bに示すように、ピア・ノード210は、同じデータ・ブロックを要求するPRILメッセージをピア・ノード220並びに230及びホーム・ノード240に送信する。ピア・ノード220からの遅延PRILメッセージは、ピア・ノード210からのPRILメッセージと同時かその後にピア・ノード230によって受信される。ピア・ノード220は、ピア・ノード220が2つのノードによる要求の間の競合を検出した旨をピア・ノード210に示すCONFLICTメッセージによってピア・ノード210からのPRILメッセージに応答する。
【００８０】
図6cに示すように、ピア・ノード230は、ピア・ノード230がピア・ノード210による要求データの有効複製を記憶していない旨を示すIACKメッセージによってピア・ノード210からのPRILメッセージに応答する。同様に、ピア・ノード230は、ピア・ノード230がピア・ノード220による要求データの有効複製を記憶していない旨を示すIACKメッセージによってピア・ノード220からのPRILメッセージに応答する。
【００８１】
図6dに示すように、ピア・ノード210はホーム・ノード240にREAD(220)メッセージを送出する。READ(220)メッセージは、メモリから要求データを取り出したノード240から先行して要求されたデータを読み取る。ホーム・ノード240はDataXFER(220)メッセージによってピア・ノード210に要求データを備える。
【００８２】
要求データを受信した後、ピア・ノード210は要求データの複製をピア・ノード220にDataMメッセージとともに送出する。ピア・ノード210によって確保される要求データの何れかの複製はI状態においてマーキングされる。ピア・ノード220は要求データをM状態において記憶し、DACKメッセージによって要求データの受信にピア・ノード210に対して応答する。
【００８３】
投機的分散競合解決をサポートするシステム例
図7は、ノードの一実施例の構成図である。ノード700は、単一プロセッサ、キャッシュ・メモリ、メモリ・コントローラ及びメモリとともに示す。しかし、何れかの数の、構成部分のうちの何れかをノードに含むことが可能である。更に、別の構成部分及び/又は異なる構成部分（例えば、バス・ブリッジ）をノードに含めることも可能である。
【００８４】
プロセッサ710は、公知の何れかの種類のプロセッサであり得る。一実施例では、プロセッサ710はキャッシュ・メモリ720を含む。別の実施例では、プロセッサ510の外部にあるキャッシュ・メモリ720及び/又は、プロセッサ710の内部又は外部にある別のキャッシュ・メモリを含み得る。
【００８５】
メモリ・コントローラ730はキャッシュ・メモリ720及びメモリ740と結合される。メモリ・コントローラ730は、プロセッサ710、キャッシュ・メモリ720及びメモリ740の間のインタフェースとして動作する。一実施例では、メモリ・コントローラ730は、本明細書及び特許請求の範囲記載のキャッシュ・コヒーレント・プロトコルによってキャッシュ・コヒーレント状態を維持する。メモリ・コントローラ730は別のノードとノード・リンク750を介して相互作用する。別の実施例では、プロセッサ710はメモリ・コントローラ730と相互作用して本明細書及び特許請求の範囲記載のキャッシュ・コヒーレント状態を維持し、プロセッサ710は別のノードと別のノード・リンク755を介して相互作用する。
【００８６】
マルチプロセッサ・システムの例示的実施例
図8は、マルチプロセッサ・システムの一実施例である。マルチプロセッサ・システム800は、例えば、コンピュータ・システム、リアルタイム監視システムなどの、複数のプロセッサを有する種々のシステムを表すことが意図されている。別のマルチプロセッサ・システムの構成部分は、より多い構成部分、より少ない構成部分、及び/又は異なる構成部分を含み得る。特定の場合には、本明細書及び特許請求の範囲記載のキャッシュ管理手法は、単一プロセッサ・システムにもマルチプロセッサ・システムにも適用し得る。マルチプロセッサ・システム800は、マルチノード・システムとして動作するよう構成し得る。
【００８７】
マルチプロセッサ・システム800は、情報を伝達するよう、バス・システム810又は別の通信装置を含む。バス・システム810は、何れかの数の、バスと、関連した相互接続回路、例えばバス・ブリッジを含み得る。プロセッサ820はバス・システム810と結合されて情報を処理する。プロセッサ820は、キャッシュ・メモリ822、例えばレベル・ゼロ(L0)キャッシュ・メモリとキャッシュ・コントローラ824とを含み得る。一実施例では、プロセッサ820は、何れかの種類のキャッシュ・メモリであり得るキャッシュ825とも結合される。別の実施例では、キャッシュ825は、バス・システム810と結合し得る。別の種類のプロセッサ・キャッシュ構成を用い得るものでもある。
【００８８】
一実施例では、キャッシュ・コントローラ824は、例えば、プロセッサ820内部のバスであり得るキャッシュ・メモリ・インタフェース828を介してキャッシュ・メモリ822に結合される。キャッシュ・コントローラは、プロセッサ820と外部キャッシュ・メモリとの間のインタフェースを備えるキャッシュ・インタフェース826を介してキャッシュ・メモリ825と結合される。
【００８９】
マルチプロセッサ・システム800は更に、キャッシュ・メモリ832とキャッシュ・コントローラ834とを備えているプロセッサ830を含む。キャッシュ・コントローラ834は、キャッシュ・インタフェース838を介してキャッシュ・メモリ832と結合される。同様に、キャッシュ・コントローラ834はキャッシュ・インタフェース836を介してキャッシュ・メモリ835と結合される。一実施例では、キャッシュ・メモリ835はプロセッサ830と結合される。
【００９０】
マルチプロセッサ・システム800は２つのプロセッサによって示しているが、マルチプロセッサ・システム800は、何れかの数のプロセッサ及び/又はコプロセッサを含み得る。マルチプロセッサ・システム800は更に、バス・システム810と結合されるメモリ・システム840を含む。メモリ・システム840は、動的メモリ装置（例えば、ランダム・アクセス・メモリ）並びに静的メモリ装置（例えば、読み取り専用メモリ、CD-ROM、ディスク記憶機構、フラッシュ・メモリ）及び、適宜、関連したドライブを含み得る。メモリ・システム840のメモリ装置は、マルチプロセッサ・システム800のプロセッサによって実行される対象の情報及び命令を記憶するのに用いる。メモリ・システム840は、プロセッサによる命令の実行中に一時変数又は別の中間的な情報を記憶するのに用い得るものでもある。
【００９１】
命令は、磁気ディスク、読み取り専用メモリ（ROM）集積回路、CD-ROM、DVDなどの静的記憶装置又は動的記憶装置から有線又は無線などの遠隔接続を介してメモリ・システム840に備え得る。別の実施例では、配線回路を、ソフトウェア命令の代わりに用いるかソフトウェア命令と組み合わせて用いることが可能である。よって、命令シーケンスの実行は、ハードウェア回路とソフトウェア命令との何れかの特定の組み合わせに限定されるものでない。
【００９２】
マルチプロセッサ・システム800は更に、ローカル・エリア・ネットワーク及び/又はインターネットなどのネットワークにアクセスを備えるネットワーク・インタフェース850を含む。ネットワーク・インタフェース850は、遠隔の電子的にアクセス可能な媒体との間で命令を通信することを含み得る無線ネットワーク・インタフェース及び/又は有線ネットワーク・インタフェースを備え得る。電子的にアクセス可能な媒体は、電子機器（例えば、コンピュータ、携帯情報端末、セルラ電話機）によって判読可能な形式におけるコンテンツ（例えば、コンピュータ実行可能命令）を備える（すなわち、記憶及び/又は伝送する）何れかの機構を含む。
【００９３】
例えば、マシン・アクセス可能媒体は：読み取り専用メモリ（ROM）；ランダム・アクセス・メモリ（RAM）；磁気ディスク記憶媒体；光記憶媒体；フラッシュ・メモリ装置；伝搬信号（例えば、搬送波、赤外線信号、ディジタル信号）の電気形態、光形態、音響形態又は別の形態を含む。
【００９４】
マルチプロセッサ・システム800は、情報を表示するよう、陰極線管（ＣＲＴ）ディスプレイ又は液晶（ＬＣＤ）ディスプレイなどのディスプレイ装置860を含み得るものでもある。例えば英数字キーやその他のキーを有するキーボードを含む入力装置870は、通常、バス810に結合されて、プロセッサ820及び/又は830に情報及びコマンド選択を通信する。別の種類のユーザ入力装置は、プロセッサ820及び830に方向情報及びコマンド選択を通信し、ディスプレイ装置860上でカーソルの動きを制御する、マウス、トラックボール、又はカーソル方向キーなどのカーソル制御装置である。
【００９５】
結論
本明細書における「one  embodiment」又は「an  embodiment」への言及は、実施例に関して記載されている特定の特徴、構造又は特性が本発明の少なくとも１つの実施例に含まれているということを表す。本明細書の種々の箇所に「in  one  embodiment」の句が出てくることは、必ずしも全て同じ実施例を表すわけではない。
【００９６】
上記明細書では、本発明はその特定の実施例を参照しながら記載されている。しかし、その特定の実施例には種々の修正及び変更を、本発明の、より広い範囲に及ぶ趣旨及び範囲から逸脱することなく行い得るということは明らかとなる。よって、本明細書及び添付図面は制約ではなく例として解されることとする。F状態は、バス・ベースのマルチプロセッサ・システムにおいて用い得る。
【００９７】
添付書類A
以下に、MESIFアルゴリズムの記述例を擬似コード形式で示す。記述はパケット・ベースである、すなわち、各ルーチンは着信パケット又は発信パケットに応じて実行される。あるいは、アルゴリズムは、受信されるパケット又は生成されるパケットによる状態変更に対する応答として表し得る。
【００９８】
記述を単純化するよう、以下の点が前提とされる：
1.  各ピア・ノード/要求側ノードは単一のキャッシュ・エージェントを有する；
2.  ホーム・ノードはキャッシュ・エージェントを有しない；
3.  ホーム・ノードにおけるメモリ要求のアルゴリズムは記載のものより複雑なものになり得るものであり、MESIFのコーナー・ケースの全てを処理し得る（2つ以上の読み取り、複数のエポック、書き込み転送など）
（一部の実施例において存在し得る）キャッシュ・エージェントを有するホーム・ノードのケースは、特定のアルゴリズムから、すなわち、局所のキャッシュ・エージェント（又はプロキシ）によるホーム・ノードとの間の伝送に関するルーチンを内部化することによって受信パケットのルーチンを組み合わせることによって導き出される。
【００９９】
一実施例では、キャッシュは以下の制約に従う：
1.  キャッシュはラインがI状態にある場合のみPRLを生成することになる。
2.  キャッシュはラインがI又はSの状態にある場合のみPRILを生成することになる。
3.  キャッシュはラインがM状態にある場合のみPWLを生成することになる。
4.  キャッシュはS状態、F状態、及びE状態からI状態に自由に移り得る。
5.  キャッシュは（書き込みが行われたとすると）E状態からM状態に自由に移り得る。
6.  キャッシュは、さもなければ、それが出した要求の完了又はピアからの要求の受信によって移り得る。
【０１００】
以下に記載するベース・プロトコルは、PRL要求、PRIL要求、及びPWL要求のみに及ぶものであり、転送データとともに転送される競合リストに関する競合解決方法を用いる。このベース・プロトコルに対する拡張及びオプションは、以下にて取り扱うこととする。
【０１０１】
ベースMESIFプロトコル
要求生成
呼び出し：
（非アクティブ状態にある）アドレスの新要求をキャッシュが生成
アルゴリズム：
Mark  address  as  being  active
If  request  is  PRL  or  PRIL
Send  request  to  all  other  peer  nodes  and  to  home  node
If  request  is  PWL
Send  request  to  home  node
ホーム・ノードによる要求受信
呼び出し：
ホーム・ノードで要求を受信
アルゴリズム：
If  request  is  PWL
Initiate  write  to  memory
(Handle  forwarding,  canceling  outstanding  reads,  etc.)
Send  ACK  back  to  requester
If  request  is  PRL  or  PRIL
Initiate  read  from  memory
(Buffer  data  if  read  finishes  before  a  READ  is  received,  etc.)
ピア・ノードによる要求受信
呼び出し：
ピア・ノードで要求（PRL又はPRIL）を受信
アルゴリズム：
If  address  is  being  forwarded
Buffer  incoming  request
Else  if  address  is  not  active
Snoop  cache
Else  if  address  is  active
If  active  request  is  a  PWL
Buffer  incoming  request
--End  If
If  incoming  request  is  in  active  request's  conflict  list
If  active  request  is  a  PRL
Respond  with  CNFL
Else  (active  request  is  a  PRIL)
Respond  with  CNFLI
Else  if  active  request  is  in  "data  phase"  (see  Gathering  Responses  below)  
Buffer  incoming  request
Else
Add  requester  to  conflict  list  (of  active  request)
If  incoming  request  is  a  PRIL
Mark  requester  in  conflict  list  as  a  PRIL  conflictor
If  active  request  is  a  PRL
Respond  with  CNFL
Else  (active  request  is  a  PRIL)
Respond  with  CNFLI
スヌープ応答
呼び出し：
適切な応答を生成するよう、要求が（スヌープとして）キャッシュに投入される
アルゴリズム：
現行キャッシュ状態と着信要求種類に基づいて以下の表における応答と次状態とのルックアップを行う（S/Iの次状態は、キャッシュが何れかの状態にラインを移動させることが可能であることを表す。なお、局所複製を無効化する場合でもPRLにDATA＿Fをなお送出する。以下の、PRL  DATA＿E/M応答オプションを参照。）
【０１０２】
【表１】
2006516058.tif 000002
【０１０３】
If  PRL  snoop  hits  cache  line  in  M  state
Initiate  PWL  request
Buffer  snoop  (hold  off  sending  DATA_F  until  writeback  completes)
Else
If  snoop  hit  cache  line  (in  M,  E,  or  F  state)
Mark  address  as  being  forwarded
Change  cache  line  to  next  state
Send  response  to  requester
応答の収集
呼び出し：
PRL/PRIL要求が応答をピア・ノードから受信
アルゴリズム：
If  response  is  a  SACK  (PRL  only)
Record  existence  of  shared  copy  in  system
Else  if  response  is  a  DATA
Record  receipt  of  forwarded  data  from  responding  node
Send  cache  line  and  new  state  to  cache  (note:  line  is  not  yet
globally  observable!)
Else  if  response  is  CNFL
Add  repsonding  node  to  conflict  list
Else  if  response  is  CNFLI
Add  responding  node  to  conflict  list
Mark  responding  node  as  PRIL  conflictor
--End  If
If  all  peer  nodes  have  responded
Mark  request  as  being  in  "data  phase"
If  a  data  response  was  received
Send  CNCL,  forwarding  node,  and  conflict  list  to  home  node
Else
Send  READ  and  conflict  list  to  home  node
ホーム・ノードでの取り消し
呼び出し：
ホーム・ノードが（転送ノード及び競合リストを含む）CNCLを受信
アルゴリズム：
Cancel  outstanding  read  (if  any)
Mark  requesting  node  as  "current  owner"  for  this  address
Send  DACK  to  forwarding  node
If  no  conflicts
Send  ACK  to  requesting  node
--conflictless  cached  epoch  is  complete
Else
Incorporate  conflict  list  as  "outstanding  requests"  for  this  address
--  wait  for  READs  to  XFR  data  to
ホーム・ノードでの読み取り要求
呼び出し：
ホーム・ノードが（競合リストを含む）READを受信
アルゴリズム：
If  no  current  owner
If  data  not  available
Wait  for  read  to  complete
Send  DATA_E  to  requesting  node
If  conlict  list  is  empty
Send  ACK  to  requesting  node
--conflictless  uncached  epoch  is  complete
Else
Incorporate  conflict  list  as  "outstanding  nodes"  for  this  address
Else
Add  outstanding  conflicts  to  "outstanding  nodes"  for  this  address
Remove  requesting  node  from  "outstanding  nodes"
If  no  (remaining)  outstanding  nodes
Send  XFR  (target:  requesting  node)  to  "current  owner"
Send  ACK  to  requesting  node
--epoch  is  complete
Else
If  one  or  more  outstanding  nodes  (including  requester)  is  a  PRIL
Send  XFRI  (target:  requesting  node)  to  "current  owner"
Else
Send  XFR  (target:  requesting  node)  to  "current  owner"
Mark  requesting  node  as  "current  owner"
転送受信
呼び出し：
要求側が（標的ノードを含む）XFR又はXFRIを受信
アルゴリズム：
Wait  for  data  if  not  yet  received
If  received  XFRI
Send  PRIL  snoop  to  cache
Else
Send  PRL  snoop  to  cache
Add  conflict  list  (sans  receiving  node)  to  DATA  packet
Send  DATA  packet  to  target  node
転送データ受信
呼び出し：
要求側がXFRの結果、（競合リストを含む）DATAを受信
アルゴリズム：
Send  data  to  processor
Incorporate  conflict  list  into  current  conflict  list
If  buffering  requests  matching  entry  in  conflict  list
Respond  with  CNFL  to  each  matching  request
DACK転送
呼び出し：
転送ノードがDACKを受信
アルゴリズム：
Unmark  address  as  being  forwarded
Service  buffered  requests  per  algorithm  for  receiving  peer  requests
ACK要求
呼び出し：
要求側がACKをホーム・ノードから受信
アルゴリズム：
If  active  request  is  a  PWL
Switch  cache  line  to  desired  next  state  (E  or  I)
If  buffered  snoop  (PRL  hit  line  in  M  state)
Send  DATA_F  to  requester
Change  cache  line  to  next  state  (S)  or  to  I  state
Else  (request  is  a  PRL  or  PRIL)
Release  buffered  requests  (i.e.,  treat  them  as  though  they
just  arrived  at  the  node)
Wait  for  data  if  not  yet  received
Send  ACK  to  processor
<<<===  END  OF  BASE  PROTOCOL  ===>>>
【０１０４】
PIL要求
上記プロトコル・アルゴリズムでは、ノードがキャッシュ・ラインをF状態からE状態に移す唯一の方法は、ラインを無効化させ（ラインをI状態に変え）、更にPRILを要求するというものである。これにはDATA転送が関係する。
【０１０５】
FからEまでの直接の移行をサポートするよう、PIL要求を用い得る。この要求は、ピア・ノードとホーム・ノードとの全てに送出され、別のキャッシュに、その、ラインの共有複製を無効化させる。伝送途上のPRIL及び/又はPRLが移行に干渉することを妨げるよう、PILには高優先度が付与され得る。
【０１０６】
ベース・プロトコルへの変更
要求生成
呼び出し：
キャッシュが（非アクティブ状態にある）アドレスの新要求を生成
アルゴリズム：
Mark  address  as  being  active
If  request  is  PRL  or  PRIL
Send  request  to  all  other  peer  nodes  and  to  home  node
>>  If  request  is  PIL
>>  Send  request  to  all  other  peer  nodes
If  request  is  PWL
Send  request  to  home  node
ピア・ノードによる要求受信
呼び出し：
要求（PIL又はPRIL）をピア・ノードで受信
アルゴリズムへの唯一の変更点は、アクティブ状態ないるPWLに行われるのと同様に、アクティブ状態にあるPIL要求が存在する場合に要求をバッファするというものである。
ピア・ノードによるPIL要求受信
呼び出し：
PIL要求をピア・ノードで受信
アルゴリズム：
PILスヌープをキャッシュに送出
スヌープ応答
新応答/次状態テーブルに同じアルゴリズムを使用（F状態にある要求側、E状態にある要求側、及びM状態にある要求側は相互排除的であるので、PILではF状態、E状態、及びM状態の場合は、エントリは何らない）
【０１０７】
【表２】
2006516058.tif 000003
【０１０８】
応答の収集
呼び出し：
PIL要求が応答をピア・ノードから受信
アルゴリズム：
If  all  peer  nodes  have  responded
Tell  cache  to  move  line  to  E  state
Release  any  buffered  requests
--PIL  request  is  complete
MからSへのPWL、及び即時応答
M状態におけるラインをヒットするPRLの性能上の課題は、データを転送する前に書き戻す（PWLを出す）必要がある。ある程度の微妙な変化によって、データの転送と書き戻しとを同時に行い得る。ホーム・ノードは、PWL要求とCNCLとの両方を要求側/勝者から受信するまでDACKを送出しない。
【０１０９】
ベース・プロトコルへの変更
ホーム・ノードによる要求受信
呼び出し：
要求のホーム・ノードでの受信
アルゴリズム：
If  request  is  PWL
Initiate  write  to  memory
(Handle  forwarding,  canceling  outstanding  reads,  etc.)
>>    If  PWL  was  for  PRL-hit-M
>>      If  CNCL  received
>>        Send  DACK  to  forwarding  node  indicated  in  CNCL
>>      Else
>>        Mark  address  as  being  written  back
>>    Else
>>      Send  ACK  back  to  requester
If  request  is  PRL  or  PRIL
Initiate  read  from  memory
(Buffer  data  if  read  finishes  before  a  READ  is  received,  etc.)
スヌープ応答
呼び出し：
適切な応答生成を行うよう、キャッシュに（スヌープとして）要求を投入
アルゴリズム：
Do  response/next-state  look  up  as  in  base  protocol
If  snoop  hit  cache  line  (in  M,  E,  or  F  state)
Mark  address  as  being  forwarded
Change  cache  line  to  next  state
If  PRL  snoop  hits  cache  line  in  M  state
Initiate  PWL  marked  as  PRL-hit-M  writeback
Send  DATA_F  to  requester,  marked  as  PRL-hit-M
Else
Send  response  to  requester
応答の収集
アルゴリズム：
Differences  are  in  recording  PRL-hit-M  data  and  notifying  home  node  of  the  special  forwarding  when  sending  the  CNCL:
Else  if  response  is  a  DATA
Record  receipt  of  forwarded  data  from  responding  node
If  PRL  request  and  hit  M  (indicated  via  DATA)
Mark  forwarding  node  as  PRL-hit-M
Send  cache  line  and  new  state  to  cache  (note:  line  is  not  
yet  globally  observable!)
If  all  peer  nodes  have  responded
If  a  data  response  was  received
Send  CNCL,  forwarding  node  (marked  as  PRL-hit-M  if  it  was),
and  conflict  list  to  home  node
ホーム・ノードでの取り消し
呼び出し：
ホーム・ノードが（転送ノード及び競合リストを含む）CNCLを受信
アルゴリズム：
DACKを送出するか否かを判定することのみが異なる：
If  forwarding  node  did  PRL-hit-M  writeback
If  PWL  has  been  received
Send  DACK  to  forwarding  node
Else
Mark  address  as  needing  writeback
Else
Send  DACK  to  forwarding  node
DACKの転送
相違点なし。PWLを出すことはワンショット・パケット（又はDACKによって終結される要求）によって処理される。
FM状態
M状態におけるラインをヒットするPRLの別の代替策は、FM状態をMESIFに導入するというものである。この状態は、修正ラインの共有複製を示す。M状態と同様に、データは、キャッシュから取り戻される場合、書き戻し（PWL）が行われなければならない。F状態と同様に、データを変更することは可能でなく、ノードは、ライン上の読み取り要求に対するヒットによって応答する。
【０１１０】
M状態にあるラインを備えているノードは、PRLを受信する場合、PWLを出し、DATA＿Fによって応答する代わりにDATA＿FMによって応答する。
【０１１１】
FMからMへの移行はPILを介して以外は可能でない。FMからEに直接移行することは可能でない。
【０１１２】
ベース・プロトコルへの変更：
【０１１３】
スヌープ応答
呼び出し：
適切に応答を生成するよう要求を（スヌープとして）キャッシュに投入
アルゴリズム：
現行キャッシュ状態と着信要求種類に基づいて以下のテーブルにおける応答と次状態とのルックアップを行う（S/Iの次状態は、キャッシュが何れかの状態にラインを移動させることが可能であることを表す。なお、局所複製を無効化する場合でもPRLにDATA＿F（M）をなお送出する、以下のPRL  DATA＿E/M応答のオプションを参照。））：
【０１１４】
【表３】
2006516058.tif 000004
【０１１５】
競合のないデータ
転送データを競合リストとともに送出することはハードウェアにとっては問題である。転送チェーンの途上にある要求が、自らが途上にあることが分かっており、転送データを受信した後に（IACK/SACKによって）バッファ要求に応答することが可能である場合には、この競合リストがなくてよいことが考えられる。これは、別の競合ノード全てが更に進み、よって、残りのREADをホーム・ノードに進めることを可能にする。
【０１１６】
このオプションによって、要求（PRL及びPRIL、すなわち読み取り要求）は4つの段階を経る：
1)  送出段階：要求を送出する
2)  収集段階：応答を収集する（READ又はCNCLを送出することが続く）
3)  データ段階：データを待つ
4)  保持段階：競合チェーンの途上で、データをXFRまで保持し、IACK/SACKをバッファ要求及び着信要求に送出する
この実施例では、要求は、転送DATA上にピギーバックACKがない場合にチェーンの途上にあることが分かることになる。この保持段階のみがベース・プロトコルと異なる。実際に、ベース・プロトコルのデータ段階は（競合のない要求又はエポック/競合チェーンの終わりでの要求の場合）同じ状態にとどまるか、２つの段階に分割され、第１段階はなおデータ段階であり、第２段階はその場合、XFRが受信される場合に終了する保持段階である。
【０１１７】
ベース・プロトコルへの変更：
ピア・ノードによる要求受信
アルゴリズムに対する変更は、アクティブ状態にある要求がその保持段階にあるかを検査するというものである：
If  address  is  being  forwarded
[same  as  before]
Else  if  address  is  not  active
[same  as  before]
Else  if  address  is  active
If  active  request  is  a  PWL
[same  as  before]
If  incoming  request  is  in  active  request's  conflict  list
[same  as  before]
Else  if  active  request  is  in  "hold  phase"
If  incoming  request  is  a  PRL
Respond  with  SACK  (or  IACK  if  previous  PRIL  got  an  IACK)
Else  --  incoming  request  is  a  PRIL
Mark  active  request  as  needing  to  invalidate
Respond  with  IACK
Else  if  active  request  is  in  "data  phase"
[same  as  before]
Else
[same  as  before]
応答の収集
このアルゴリズムに対する変更は、要求が、CNCLを送出し、その競合リストが空き状態にある場合に完了するという点である。すなわち、システムはキャッシュ間転送を行っており、競合は存在しなかったということである。未処理事項はホーム・ノードに通知するということだけであり、このことは応答されなくてよい。
【０１１８】
なお、（競合を備えている）CNCL要求は、XFRを待って、データ段階に留まる、すなわち、保持段階に入らない。
ホーム・ノードでの取り消し
呼び出し：
ホーム・ノードが（転送ノードと競合リストとを含む）CNCLを受信
アルゴリズム：
Cancel  outstanding  read  (if  any)
Mark  requesting  node  as  "current  owner"  for  this  address
Send  DACK  to  forwarding  node
If  no  conflicts
--  conflictless  cached  epoch  is  complete
Else
Incorporate  conflict  list  as  "outstanding  requests"  for  this  address
--  wait  for  READs  to  XFR  data  to
ホーム・ノードでの読み取り要求
呼び出し：
ホーム・ノードは（競合リストを含む）READを受信
アルゴリズム：
If  no  current  owner
If  data  not  available
Initiate  read  if  necessary
Wait  for  read  to  complete
Send  DATA_E  to  requesting  node
If  conlict  list  is  empty
--  conflictless  uncached  epoch  is  complete
Else
Incorporate  conflict  list  as  "outstanding  nodes"  for  this  address
--  wait  for  READs  to  XFR  data  to
Else
Add  outstanding  conflicts  to  "outstanding  nodes"  for  this  address
Remove  requesting  node  from  "outstanding  nodes"
If  no  (remaining)  outstanding  nodes
Send  XFR+ACK  (target:  requesting  node)  to  "current  owner"
--  epoch  is  complete
Else
If  one  or  more  outstanding  nodes  (including  requester)  is  a  PRIL
Send  XFRI  (target:  requesting  node)  to  "current  owner"
Else
Send  XFR  (target:  requesting  node)  to  "current  owner"
Mark  requesting  node  as  "current  owner"
転送受信
（XFRとACKとを処理することに加え、）ここでの変更は、保持段階中にIACK応答はPRILにスプーフィングされたかを判定するという点である。その場合には、ラインがスヌープを用いて無効化される。
呼び出し：
要求側がXFR、XFR及びACK、又は（標的ノードを含む）XFRIを受信する
アルゴリズム：
Wait  for  data  if  not  yet  received
If  received  XFRI  or  request  is  marked  as  needing  to  invalidate
Send  PRIL  snoop  to  cache
Else
Send  PRL  snoop  to  cache
--  End  If
If  received  XFR+ACK
Send  DATA+ACK  packet  to  target  node
Else
Send  DATA  packet  to  target  node
転送データ受信
呼び出し：
DATA、又はDATA及びACKをXFRの結果、受信（要求者は、データ段階にあるので、XFRを介したものであることが分かっている）
アルゴリズム：
Send  data  to  processor
If  received  DATA  packet
Move  request  to  hold  phase
Foreach  buffered  request
If  buffered  request  is  a  PRL
Respond  with  SACK  (or  IACK  if  previous  PRIL  got  an  IACK)
Else  --  buffered  request  is  a  PRIL
Mark  local  request  as  needing  to  invalidate
Respond  with  IACK
Else  --  received  DATA+ACK
--  request  is  complete  and  epoch  is  complete
PRL  DATA  E/M応答
PRLは、キャッシュ・ラインのスヌープ・ヒットを行う場合、キャッシュがラインをS状態又はI状態に移行させるか否かにかかわらず、正確性を維持するようDATA＿Fによって応答する必要がある。Iに移行する場合にDATA＿Eを送出することをサポートすることが考えられるが、PRLは、それが受信したE状態をFに格下げすることを必要とするということをキャッシュに知らせるよう、キャッシュとの別の通信が必要である。基本的には、アルゴリズムは、ノードが既にDATA＿Eを受信し、更にSACKを受信する場合、キャッシュ状態をEからFに変更しなければならないというものである。
【図面の簡単な説明】
【０１１９】
【図１ａ】マルチノード・システムにおける競合解決の概念を示す図である。
【図１ｂ】マルチノード・システムにおける競合解決の概念を示す別の図である。
【図１ｃ】マルチノード・システムにおける競合解決の概念を示す更に別の図である。
【図１ｄ】マルチノード・システムにおける競合解決の概念を示す更に別の図である。
【図１ｅ】マルチノード・システムにおける競合解決の概念を示す更に別の図である。
【図２ａ】共有ライン競合の概念を示す図である。
【図２ｂ】共有ライン競合の概念を示す別の図である。
【図２ｃ】共有ライン競合の概念を示す更に別の図である。
【図２ｄ】共有ライン競合の概念を示す更に別の図である。
【図３ａ】おおよそ同時に出される要求によってもたらされる共有ライン競合の概念を示す図である。
【図３ｂ】おおよそ同時に出される要求によってもたらされる共有ライン競合の概念を示す別の図である。
【図３ｃ】おおよそ同時に出される要求によってもたらされる共有ライン競合の概念を示す更に別の図である。
【図３ｄ】おおよそ同時に出される要求によってもたらされる共有ライン競合の概念を示す更に別の図である。
【図４ａ】複数の要求のうちの１つの遅延によってもたらされる共有ライン競合の概念を示す図である。
【図４ｂ】複数の要求のうちの１つの遅延によってもたらされる共有ライン競合の概念を示す別の図である。
【図４ｃ】複数の要求のうちの１つの遅延によってもたらされる共有ライン競合の概念を示す更に別の図である。
【図４ｄ】複数の要求のうちの１つの遅延によってもたらされる共有ライン競合の概念を示す更に別の図である。
【図５ａ】無効ライン競合の概念を示す図である。
【図５ｂ】無効ライン競合の概念を示す別の図である。
【図５ｃ】無効ライン競合の概念を示す更に別の図である。
【図５ｄ】無効ライン競合の概念を示す更に別の図である。
【図６ａ】無効ライン競合の概念を示す図である。
【図６ｂ】無効ライン競合の概念を示す別の図である。
【図６ｃ】無効ライン競合の概念を示す更に別の図である。
【図６ｄ】無効ライン競合の概念を示す更に別の図である。
【図７】ノードの一実施例の構成図である。
【図８】マルチプロセッサ・システムの一実施例の図である。
【図１ａ】
2006516058.tif 000005
【図１ｂ】
2006516058.tif 000006
【図１ｃ】
2006516058.tif 000007
【図１ｄ】
2006516058.tif 000008
【図１ｅ】
2006516058.tif 000009
【図２ａ】
2006516058.tif 000010
【図２ｂ】
2006516058.tif 000011
【図２ｃ】
2006516058.tif 000012
【図２ｄ】
2006516058.tif 000013
【図３ａ】
2006516058.tif 000014
【図３ｂ】
2006516058.tif 000015
【図３ｃ】
2006516058.tif 000016
【図３ｄ】
2006516058.tif 000017
【図４ａ】
2006516058.tif 000018
【図４ｂ】
2006516058.tif 000019
【図４ｃ】
2006516058.tif 000020
【図４ｄ】
2006516058.tif 000021
【図５ａ】
2006516058.tif 000022
【図５ｂ】
2006516058.tif 000023
【図５ｃ】
2006516058.tif 000024
【図５ｄ】
2006516058.tif 000025
【図６ａ】
2006516058.tif 000026
【図６ｂ】
2006516058.tif 000027
【図６ｃ】
2006516058.tif 000028
【図６ｄ】
2006516058.tif 000029
【図７】
2006516058.tif 000030
【図８】
2006516058.tif 000031