(57)【特許請求の範囲】
【請求項１】
以下のステップ(a)から(d)を設け、マルチノードシステム中の複数のノードからなるメモリ共用リストを更新する操作を実行する方法であって、
前記共用リストは前記ノードを逐次的に配列したものを有しており、
前記共用リスト中の各ノードはメモリデータのコピーをメモリ中にストアし、
前記マルチノードシステムはＳＣＩマルチノードシステムであり、
前記メモリはキャッシュであり、
前記メモリデータはメモリ列である：
(a) 更新操作のための更新コマンドを前記共用リスト中の第１のノードから前記共用リスト中の残りのノードへ発行する；
(b) データパケットを使ってシステム中に前記更新操作のためのコマンドを分配する；
(c) 前記複数のノードのうちのノードが前記更新コマンドを受信する前に前記共用リストから外れるのを防止する：前記防止するステップは、前記第１のノードによって発行された更新コマンドによって各ノードがインクリメントされたとき、前記共用リスト中の各ノードの位相値を反転するステップを含む；
(d) 前記第１のノードを前記共用リストの先頭の位置に維持する。
【請求項２】
以下の(a)から(d)を設け、複数のノードからなるメモリ共用リスト上での更新操作を実行するマルチノードシステムであって、
前記共用リストは前記ノードを逐次的に配列したものを有しており、
前記共用リスト中の各ノードはメモリデータのコピーをメモリ中にストアし、
前記システムはＳＣＩマルチノードシステムであり、
前記メモリはキャッシュであり、
前記メモリデータはメモリ列である：
(a) 更新操作のための更新コマンドを前記共用リスト中の第１のノードから前記共用リスト中の残りのノードへ発行する手段；
(b) データパケットを使ってシステム中に前記更新操作のためのコマンドを分配する手段；
(c) 前記複数のノードのうちのノードが前記更新コマンドを受信する前に前記共用リストから外れるのを防止する手段：前記防止する手段は、前記第１のノードによって発行された更新コマンドによって各ノードがインクリメントされたとき、前記共用リスト中の各ノードの位相値を反転する手段を含む：
(d) 前記第１のノードを前記共用リストの先頭の位置に維持する手段。
【請求項３】
以下のステップ(a)から(g)を設け、ＳＣＩマルチノードシステム中の複数のノードからなる共用リスト上で更新操作を行う方法であって、
前記共用リストは前記ノードを逐次的に配列したものを有しており、
前記共用リスト中の各ノードはメモリデータのコピーをメモリ中にストアする：
(a) 更新操作のための更新コマンドを前記共用リスト中の第１のノードから前記共用リスト中の残りのノードへ発行するステップであって、前記第１のノードから前記リスト中の次のノードへインクリメントコマンドを発行することを含む；
(b) データパケットを使ってシステム中に前記更新操作のためのコマンドを分配する；
(c) 前記複数のノードのうちのノードによって、前記第１のノードから前記インクリメントコマンドを受け取る；
(d) 前記インクリメントコマンドに従って、前記ノードのキャッシュを更新する；
(e) 前記ノードによって、前記第１のノードへ応答を送り返す；
(f) 前記複数のノードのうちのノードが更新コマンドを受け取る前に前記共用リストから外れるのを防止する：前記防止するステップは、前記第１のノードによって発行された更新コマンドによって各ノードがインクリメントされたとき、前記共用リスト中の各ノードの位相値を反転するステップを含む；
(g) 前記第１のノードを前記共用リストの先頭の位置に維持する。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は多ノード、多重プロセッサおよびキャッシュコヒーレント不均一アクセスコンピュータシステムに係り、とりわけこのようなシステムにおけるメモリ列のキャッシュコピーの更新に関する。
【０００２】
【従来の技術】
キャッシュ列の更新に関するスケーラブルコヒーレントインターフェース（Scaleable Coherent Interface：ＳＣＩ）規格は、基本的には１つのキャッシュのみが列のコピーを持つことがでる。これが更新、すなわち書き込みされるコピーであり、他の全てのキャッシュを書き込みの開始前にパージしなければならない無効化フローである。
【０００３】
バリアはコード内のこのポイントの全てのプロセッサおよび／またはスレッド（threads）を同期させる並列処理に使用される機構である。並列処理においては高速なバリアを備えることが非常に望ましい。バリアが高速であるほど同期に要する時間は短く、実際の作業の実行に長い時間をとることができる。したがって、バリアが高速であるほど、システム動作のきめ細かな並行性を得ることができる。バリアは一般的には結合と解放からなる。結合演算は一般的にはフェッチおよびインクリメント命令であるからここでは説明しない。バリア解放は新たな値を読み出し受け取ろうとしている多数のノードに関わる書き込みコマンドを用いるアプリケーションの１つである。
【０００４】
図２１〜図２３には簡単なＳＣＩ共用リストとこのＳＣＩ共用リストの値を実際に更新あるいは書き込むのに必要な動作を示す。これは、ＳＣＩ共用リスト中の全てのノードがこの新たな値を見る（see）ことを希望することを前提とする。この場合、ＳＣＩ共用リスト１００はメモリ１０１を有し、メモリは、メモリ中のデータが使用されていない（obsolete）ことを意味するマークである「ＧＯＮＥ」と示されている。このメモリはノード０  １０２を指すメモリポインタを含む。このメモリポインタは常にＳＣＩ共用リスト１００の先頭を指している。したがって、図２１に示すように、ノード０  １０２が現在先頭である。
【０００５】
この場合、ノード０  １０２は「先頭＿ダーティ（HEAD＿DIRTY）」と示され、これはこの列が共用されていても、ノード０は共用リストが破壊された場合にデータをメモリに返さなければならない。ノード０  １０２、すなわち先頭＿ダーティは「中間＿有効（MID＿VALID）」であるノード１  １０３を指す正方向ポインタを有する。ノード１  １０３はノード２  １０４を指す正方向ポインタを有し、ノード１  １０３はまたノード０  １０２を指す逆方向ポインタを有する。ノード２  １０４は、図２１においては「末尾＿有効（TAIL＿VALID）」であり、ノード１  １０３への逆方向ポインタを有する。
【０００６】
ノード０  １０２がＳＣＩ共用リスト１００によって共用される列の値をインクリメントしたい場合、まずノード１  １０３に有効＿無効（VALID＿INVALID）要求を送らねばならない。すると、ノード０  １０２は中間＿有効ノードであるノード１  １０３から正方向ポインタを受け取る。ノード０  １０２はこの正方向ポインタを用いて、ノード２  １０４に無効要求、VALID＿INVALIDを送る。ノード２  １０４から受け取った状態は末尾であり、これはリストの最後に達したことを意味する。このとき、ノード０  １０２は共用リストにある唯一のものであり、このリストはダーティリスト（dirty list）であるから、この値をインクリメントすることができる。
【０００７】
ところで、ノード１  １０３とノード２  １０４とはいずれもこの列を読み出してこの新たな値を見ようとしている。読み出しを行なうには、これらのノードはメモリ１０１に戻って共用リストを最結合しなければならない。ノード１  １０３がメモリ１０１に読み出し要求（MREAD）を送ると、ノード１  １０３はこの列が無くなっていることを知ることから、メモリ１０１はこの列を更新してノード１  １０３を指す。ノード１  １０３はこの列の唯一のコピーを有するノード０  １０２へのポインタを受け取る。また、ノード２  １０４がメモリ１０１に読み出し要求（MREAD）を送りリストを再結合する。ノード２  １０４はメモリ１０１が無くなり、ノード１  １０３を示していることを知ることから、ノード１  １０３に行ってこの列の新たなコピーを得なければならない。メモリ１０１はこのポインタをノード２  １０４に更新し、ノード２  １０４の正方向ポインタはノード１  １０３に変更される。
【０００８】
図２２にはメモリ１０１がＧＯＮＥと示されている。また、図２２はノード２１０４を指しているときのＳＣＩ共用リスト１００のキャッシュの状態を示す。ノード２  １０４は基本的にはキューに入れられており、その列のデータは有効ではないため「キュード＿ジャンク（QUEUED＿JUNK）」と示されている。ノード２  １０４は同じくキュード＿ジャンクと示されたノード１  １０３を指し、ノード１  １０３はこの列の唯一のコピーを有するノード０  １０２を指す。したがって、このときノード１  １０３はノード０  １０２にキャッシュ読み出し要求（CREAD）を送り、この列の新たなバージョンを受け取る。一方、ノード２１０４はノード１  １０３にキャッシュ読み出し要求（CREAD）を送っている。ノード１  １０３は新たな値を受け取ると、ノード２  １０４から適当なタイミングで次の要求を受けたとき、この新たな値をノード２  １０４に渡す。
【０００９】
図２３はＳＣＩ共用リスト１００の最終的な状態を示す。この場合、メモリ１０１はＧＯＮＥと示されており、ノード２  １０４を指している。ノード２  １０４は先頭として示され、有効なデータを有する。この先頭すなわちノード２  １０４はノード１  １０３を指しており、ノード１  １０３は中間であり、有効データを有する。中間すなわちノード１  １０３はノード０  １０２を指しており、ノード０  １０２はオリジナルライター（original writer）であり、現在は末尾である。
【００１０】
【発明が解決しようとする課題】
図２１〜図２３に示すシステムおよび方法の主たる問題点は、ＳＣＩ共用リストを完全に解体し再構築しなければならないことである。この処理には他のトランザクションに利用可能なシステムの時間および資源が大量に使用される。
【００１１】
【課題を解決するための手段】
上記の問題およびその他の問題は、標準ＳＣＩデータフローを改善したインクリメント更新フローを用い、ＳＣＩ共用リスト中の全てのキャッシュのワードをインクリメントしてバリアの解放速度を大幅に上昇させる技術によって解決される。このインクリメント更新を実行しているプロセッサ／ノードは、まず読み出し専用フローと同様に共用リストの先頭にならなければならない。ここで、このノードは共用リストを走査して各キャッシュ内のワードをインクリメントする。状態およびポインタが各キャッシュから戻り、先頭の処理装置はリストの走査を進めることができる。
【００１２】
先頭がリストを走査している間に共用リストからロールアウトしようとするノードがある場合には、特に注意が必要である。この場合、さらに別の状態を用いてリストの破壊が防止される。この方法のインクリメント更新フローの場合のみをここでは説明するが、この方法は書き込み更新動作全体に対しても有効である。
【００１３】
本発明の技術的利点は、共用リストの先頭のノードの位置を維持しながら、この先頭ノードから他のノードに更新コマンドが発せられることである。
【００１４】
本発明の他の技術的利点は、リストの末尾に達するまで先頭ノードに、リスト中の連続するノードのそれぞれにインクリメントコマンドを送らせることである。それぞれのノードがこのインクリメントコマンドを受け取ると、このキャッシュを更新し、先頭ノードに応答を送り返す。
【００１５】
本発明の他の技術的利点は、あるノードがこの更新コマンドを受け取るまでは、このノードが共用リストからロールアウトすることを防止することである。各ノードはノードがインクリメントされる際にトグルされる位相値を有する。したがって、ロールアウト要求はこのロールアウト要求の位相値がこのノードの位相値と一致しなければ無効とされる。
【００１６】
本発明のさらに別の技術的利点は、ロールアウトされるノードが適正な位相を有するロールアウト要求を発するまでは、このノードのインクリメントを禁止するデッドロックを提供することである。
【００１７】
以上は、本発明に関する以下の詳細な説明の理解を助けるために本発明の特徴および技術的利点を極めておおまかに説明したものである。以下に、本発明の他の特徴および利点がさらに説明され、これらは本発明の特許請求の対象となる。当業者には、ここに開示する概念および具体的実施形態を本発明の目的を達成するための改造や他の構造の設計の基礎として用いることは容易であろう。また、当業者にはかかる均等な構造は特許請求の範囲に定める本発明の精神および範囲を逸脱するものではないことは明らかであろう。
【００１８】
【発明の実施の形態】
図１および図２は、図２１に示す簡単なＳＣＩ共用リスト１００上での本発明に係るインクリメント更新フロー処理を示す。図１においても図２１と同様に「ＧＯＮＥ」と示されたメモリ１０１を有するＳＣＩ共用リスト１００を示し、メモリ１０１はノード０  １０２を指している。ノード０  １０２は先頭＿ダーティ状態であり、ノード１  １０３を指している。中間＿有効であるノード１  １０３はノード２  １０４を指しており、ノード２  １０４は末尾＿有効である。
【００１９】
この場合、ノード０  １０２はノード１  １０３にコヒーレントインクリメントコマンド（ＣＩＮＣ）を送る。ノード１  １０３はこの値をインクリメントし、該ノード１  １０３内のローカルプロセッサキャッシュをパージし、ノード１１０３の状態およびポインタをノード０  １０２に返す。ノード０  １０２はノード１  １０３からのこの応答を受け取り、この状態を調べ、それが中間＿有効であることを判定する。ノード０  １０２はこのポインタを取り、末尾＿有効ノードであるノード２  １０４にコヒーレントインクリメントコマンド（ＣＩＮＣ）を送る。この「末尾＿有効」を受け取ると、ノード０  １０２はＳＣＩ共用リスト１００の末尾に達したこと、つまりこのリストが完了したことを知る。次に、ノード０  １０２は自己の値をインクリメントし、インクリメント更新フローが完了する。図２には、その結果得られるＳＣＩ共用リスト２００は、各ノードの値がインクリメントされていることを除き変わっていないことを示す。
【００２０】
図２１〜図２３に示すシステムを図１および図２に示すシステムと比較すると、これらの図はそれぞれ基本的にはプログラムの観点からは同じ処理を示すものであることがわかる。しかしながら、図２１〜図２３のシステムは、図１および図２のシステムと同じ結果を得るためにかなり多量のトラフィックを有する。図２１〜図２３ではリストを解体し再構築するが、図１および図２は基本的にはリストに従い、必要に応じてこれをインクリメントする。解体と再構築にはかなり長い時間を要し、ＳＣＩ資源が使用され、これを行なわなければかかるＳＣＩ資源は他のトランザクションに利用することができる。
【００２１】
図３には、本発明のインクリメント更新処理の実行に用いられるＳＣＩコントローラ内の各種のハードウェア状態機械（hardware state machine）のタスクを記述する疑似コードを示す。図３には、メモリアクセスコントローラ（ＭＡＣ）がＳＣＩコントローラ（ＴＡＣ）に要求を送るときの動作を示す。図４には、各状態についてＳＣＩリングに対して行なう要求を示す。図５〜図９には、ある状態においてある応答に対する動作および次の動作を示す。すなわち、このＳＣＩリングに他の要求を送る、ＭＡＣに応答する、あるいはその両方を行なうといった動作を示す。図１０〜図１５には応答状態機械を示す。
【００２２】
図３はＭＡＣ要求状態機械のタスクを説明するコードである。このコードには、ＭＡＣがインクリメント更新要求のためにＴＡＣ、すなわちＳＣＩコントローラに送る可能性のある各状態についての事例文がある。この場合、ＳＣＩ書き込みサブルーチンは、基本的にはリング要求である。したがって、ＣＳ＿無効へのインクリメント更新がある最初の事例においては、状態が一時停止（pending）された状態でリング要求が送られる。
【００２３】
他の例としては、インクリメント更新が先頭＿ダーティの状態で実行される場合がある。この場合、状態は「先頭＿ダーティ＿更新  先頭＿ダーティ（HEAD＿DIRTY＿UPDATE HEAD＿DIRTY）」に変更され、リング要求が送られる。各状態のリング要求の詳細については図４に示す。図４では、状態が「一時停止の状態（STATE＿OF＿PENDING）」である場合、キャッシュダーティのサブ演算コードを用いたメモリ読み出しリング要求が行なわれる。これは、現在のメモリの内容が読み出され、書き込みが可能になるように「ＧＯＮＥ」とマークされることを意味する。
【００２４】
図５〜図９には、競合要求状態機械を示す。これは、ある特定のＴＡＣがインクリメント更新フローを実行しているとき、このＴＡＣは他のフローを実行している他のノードから同じ列に対する要求を受け取ることができる。図５〜図９には、他のノードから要求を受けたときどのような状態トランザクションが実行されるかを示す。例えば、中間＿有効状態のロールアウト、およびこのフローのインクリメント更新の部分の開始前に先頭に達しようとしていることを意味する「中間＿有効＿バック＿イン（MID＿VALID＿BACK＿IN）」状態では、ＣＰＵＲＧＥ、他のＣＩＮＣ、あるいは他の任意のものを受けることができる。ここにリストされていないものは全て自動的に無効化される。ここにリストする状態は上述したように変化する。この場合、中間＿有効＿バック＿インでは、ＣＰＵＲＧＥ要求を受け取ると、状態は「トゥー＿無効（TO＿INVALID）」に変わり、これは現在の要求に対する応答を受け取ったとき無効状態になり得ることを示す。
【００２５】
図１０〜図１５は応答状態機械を示す。これは要求に対する応答、および現在の状態を受け取り次の動作を決定する状態機械である。例えば、状態が一時停止（pending）であり、列が使用されておらず共用リストが存在しないことを意味するホームの非無効化応答を受け取った場合、ただちに「オンリー＿ダーティ（ONLY＿DIRTY）」状態としてこのフローを終了することができる。
【００２６】
図１６には「無効＿オンリー＿フレッシュ（INVALID＿ONLY＿FRESH）」、「オンリー＿ダーティ」、その他のＳＣＩの安定状態においてインクリメント要求を受け取ったときに発生するキャッシュの変化のテーブルを示す。
【００２７】
図１７にはＳＣＩの変化状態においてインクリメント要求を受け取ったときに発生するキャッシュ変化のテーブルを示す。これは図５〜図９のテーブルを簡略化したものである。このテーブルには現在のキャッシュ状態、着信キャッシュコマンド、および適正なローカルポインタが要求者のノードＩＤと等しいかどうかを示す。また、このテーブルは新たな状態がどのような状態であるかを説明し、応答が無効であるかどうかを示す。最も重要なタイプの要求の１つは、コヒーレントインクリメント（ＣＩＮＣ）要求である。例えば、オンリー＿フレッシュである列に対するＣＩＮＣ要求を受け取った場合、これは発生してはならないため、エラーである。他の例としては中間＿有効へのＣＩＮＣ要求がある。この場合、共用位相がトグルされ、キャッシュ列がインクリメントされ、状態は中間＿有効のままである。
【００２８】
インクリメント更新があらゆる場合に機能するには、２つの重要な問題を解決しなければならなかった。１番目の問題点は、ノードがキャッシュインクリメントコマンドを受け取る直前に共用リストからロールアウトすることができる点である。このとき、次のポインタが失われ、先頭からは共用リストが破壊されたように見える。その解決法として、共用位相の概念が導入された。
【００２９】
先頭＿ダーティ、先頭＿フレッシュ、その他の全ての共用状態は位相０あるいは１を有する。静的共用リスト内の全てのノードは、列に対して同じ位相を有する。先頭がリスト内の各ノードをインクリメントするとき、位相がトグルされる。「前＿Ｖ末尾（PRE＿VTAIL）」あるいは「前＿Ｖ中間（PRE＿VMID）」ロールアウト要求は、この要求パケット内の共用位相、したがって要求者の共用位相がその列のローカル共用位相と一致するまで無効化される。そのためには、先頭はロールアウトに関係する両方のノードをインクリメントしていなければならないことから、ロールアウトは安全である。
【００３０】
この一例として図５〜図９に示す処理がある。この場合、ある特定の列が「中間＿有効  後  中間＿有効（MID＿VALID FORWARD MID＿VALID）」状態にあり、共用リスト内の次の中間＿有効から「ＣＰＵＲＧＥ  前＿Ｖ中間（CPURGE PRE＿VMID」を受け取った場合、このローカルノードは前＿Ｖ中間コマンドを完了させる前に、この要求が正方向ポインタによって指されたノードからのものであり、共用位相が等しいことを確認する。
【００３１】
２番目の大きな問題点は、第１の問題の解決に用いられる共用位相がロールアウト競合の全ての場合を解決するものではないことである。ロールアウト要求が目標に到達するまでに長い時間がかかり、目標に到達する前にリストに対して２回目のインクリメント処理が実行中である場合がある。また、共用位相は２つの値しか持たないため、この目標の新たな値は元の値と等しくなる。ロールアウト要求は２回目のインクリメントの後に、そしてロールアウトするノードの２回目のインクリメントの前にその宛先に到達する。このロールアウトは完了し、先頭は無効なポインタを持つことになる。
【００３２】
この２番目の問題点に対する解決法は、ロールアウトにデッドロックを設けることである。共用リストからロールアウトしようとするノードは、現在の位相を有するロールアウト要求が行なわれるまではインクリメントすることはできない。これは、適正なロールアウト要求が行なわれるまで着信インクリメント要求を無効にすることによって達成される。このために必要な状態を図１８および図１９に示す。この状態機械の参照する要求はコヒーレントインクリメント要求、すなわちＣＩＮＣ要求である。この状態機械の参照する応答は前＿Ｖ中間あるいは前＿Ｖ末尾ロールアウト要求に対する応答である。
【００３３】
図１８には中間＿有効状態あるいは末尾＿有効  バック＿イン状態にあるキャッシュ列の状態図と、その生じた作用を示す。図１９には、共用リストの現在の先頭からインクリメント要求を受けたときの中間＿有効あるいは末尾＿有効  バック＿イン  ムーブスルー（move through）であるキャッシュのフロー状態を示す。ある列が中間＿有効  バック＿イン状態あるいは末尾＿有効＿バック＿イン状態になると、この列は状態機械５００の通常状態５０１にある。この通常状態５０１でこの要求に対する応答を受け取り、この応答が無効化されない（５０３）場合、このフローはコヒーレントインクリメント更新の途中ではないことになる。したがって、この応答は通常通りに完了する。
【００３４】
応答が無効化される場合（５０２）、このフローがインクリメント更新を実行中であることから新たな要求を必要とし、コヒーレントインクリメントあるいは最後の要求に対する非無効化応答を待っていることを意味する。通常状態５０１にあり、共用リスト５０４の先頭からコヒーレントインクリメント更新要求が受け取られると、そのローカル状態は応答待ち状態５０６に変化する。応答待ち状態５０６になると、このフローの共用位相も変化する。応答待ち状態５０６になると、フローはコヒーレントインクリメント更新の無効化を継続し、応答を待つ。無効化応答（null）５０７を受け取ると、フローは適正位相（correct phase）状態５０９に切り替わり、適正な位相を有する新たな要求５０８が行なわれる。
【００３５】
このとき、新たなコヒーレントインクリメントを受け取ると、このフローは通常状態５０１に移行し、非無効化応答（non＿null）５０３を待つことができる。適正位相状態５０９にあるとき、フローは新たなコヒーレントインクリメント要求を受ける前に非無効化応答（non＿null）５１０を受ける場合がある。この場合、フローは適正位相終了（correct phase done）状態５１１に移行し、この状態にとどまってコヒーレントインクリメント更新５１２が状態（５１３）になるのを待つ。５０２等の無効化応答（null）は逆方向ポインタによって指されたノードへの要求によってロールアウト要求が無効化されることから、このノードは新たな要求を行なわなければならないことを示す。５０３等の非無効化応答（non＿null）は、その要求が成功であったことを示す。状態５０１、５０６、５０９、５１１は、ＳＣＩ状態のｍｖ＿バック＿イン（MV＿BACK＿IN）あるいはｔｖ＿バック＿イン（TV＿BACK＿IN）の下位状態である。
【００３６】
適正位相終了状態でコヒーレントインクリメントを受け取ると、状態（５１３）となる。その後、ＳＣＩ状態は中間＿有効＿バック＿イン状態あるいは末尾＿有効＿バック＿イン状態からトゥー＿無効状態あるいはトゥー＿一時停止（TO＿PENDING）状態５１３に変化する。この場合、フローは逆方向ポインタによって指されたノードに対するカップデイト  前＿Ｖ中間（CUPDATE PRE＿VMID）要求からの応答を待っている。フローはその応答を受け取ると、無効状態または一時停止状態５１５に移行する（５１４）。これは、フローが終了して無効化状態となったこと、あるいはフローがこのフローの次の部分を開始可能である一時停止状態であることを意味する。トゥー＿無効状態５１３および無効状態５１５は標準的なＳＣＩ状態である。
【００３７】
これらの状態機械のそれぞれの異なった状態において、着信コヒーレントインクリメント要求には異なった処理が行なわれる。通常状態にある場合、コヒーレントインクリメント要求は無効化され、共用位相がトグルされる。応答待ち状態では、コヒーレントインクリメントが無効化される。適正位相終了状態あるいは適正位相状態では、コヒーレントインクリメントは通常の応答を受け取る。
【００３８】
この状態機械の使用形態の一例を図５〜図９に示す。中間＿有効＿バック＿インの場合、コヒーレントインクリメント要求を受け取ると、各状態は状態図に示したように変化することがわかる。例えば、通常状態では共用位相がトグルされ、ＣＩＮＣ応答を受け取ったとき無効化応答が送られる。通常の状態あるいは応答待ち状態において、ロールアウト位相がこの状態図にしたがってどのように変化するかがわかる。
【００３９】
図５〜図９には、コヒーレントインクリメント要求からの変化を示す。その応答からの変化については別途文書化する。図１０〜図１５の中間＿有効＿バック＿イン状態および末尾＿有効＿バック＿イン状態は、ロールアウト要求に対する無効化あるいは非無効化応答からの状態変化を示す。
【００４０】
図２０には、応答送出パケット６００内のＰで示す共用位相ビット（Ｐビット）６０１を示す。同様のビットが応答送出パケット内にも存在するが、これについては図示しない。要求パケット上ではＰビット６０１が要求とともに送られ、これによって位相が同じであることがわかり、ロールアウトの完了が可能となる。応答パケットにおいては、Ｐビット６０１は適正状態の初期設定のためのリストの構築に用いられる。
【００４１】
本発明およびその利点を詳細に説明したが、特許請求の範囲に定める本発明の精神および範囲から逸脱することなくさまざまな変更、代替および改変が可能であることを理解されたい。
【００４２】
以下に本発明の実施の形態を要約する。
１．  ノードの順次配列を有する共用リストとキャッシュにメモリ列のコピーを記憶する前記ノードとを含む多ノードシステム中の複数のノード（１０２、１０３、１０４）からなる前記共用リスト上で更新動作を実行する方法において、前記共用リスト中の第１のノード（１０２）から更新コマンドを前記共用リスト中の他のノードに発し、前記第１のノード（１０２）を前記共用リストの先頭位置に維持するＳＣＩシステムインクリメント更新方法。
【００４３】
２．  前記多ノードシステムはＳＣＩ多ノードシステムである上記１記載のＳＣＩシステムインクリメント更新方法。
【００４４】
３．  データパケット（６００）を用いて前記更新動作のためのコマンド（６０１）を前記多モードシステム内に送る上記１記載のＳＣＩシステムインクリメント更新方法。
【００４５】
４．  前記更新コマンドを発する前記ステップが、
前記第１のノード（１０２）から前記共用リストの次のノード（１０３）への第１のインクリメントコマンド（１）を発し、
複数のノード（１０２、１０３、１０４）の内の前記次のノード（１０３）が前記第１のノード（１０２）からの前記第１のインクリメントコマンド（１）を受け取り、
前記第１のインクリメントコマンド（１）にしたがって前記次のノード（１０３）のキャッシュを更新し、
前記次のノード（１０３）が前記第１のノード（１０２）に第一の応答を送る上記１記載のＳＣＩシステムインクリメント更新方法。
【００４６】
５．  前記次のノード（１０３）は前記共用リストの最終ノードではなく、
前記第１のノード（１０２）から前記後続ノード（１０４）への第２のインクリメントコマンド（２）を発し、
前記後続ノード（１０４）が前記第１のノード（１０２）からの前記第２のインクリメントコマンド（２）を受け取り、
前記第２のインクリメントコマンド（２）にしたがって前記後続ノード（１０４）のキャッシュを更新し、
前記後続ノード（１０４）が前記第１のノード（１０２）に第２の応答を送り、
前記第１のノード（１０２）が前記後続ノード（１０４）からの前記第２の応答を受け取り、
前記後続ノード（１０４）は前記共用リストの最終ノードであるかどうかを判定する上記４記載のＳＣＩシステムインクリメント更新方法。
【００４７】
６．  ノードの順次配列を有する共用リストとキャッシュにメモリ列のコピーを記憶する前記ノードとを含む複数のノード（１０２、１０３、１０４）からなる前記共用リスト上で更新動作を実行する多ノードシステムにおいて、
前記共用リスト中の第１のノード（１０２）から更新コマンドを前記共用リスト中の他のノードに発する更新コマンド発生手段と、
前記第１のノード（１０２）を前記共用リストの先頭位置に維持する手段とからなるＳＣＩシステムインクリメント更新システム。
【００４８】
７．  データパケット（６００）を用いて前記更新動作のためのコマンド（６０１）を前記多モードシステム内に送る手段を含む上記６記載のＳＣＩシステムインクリメント更新システム。
【００４９】
８．  前記更新コマンド発生手段は、前記第１のノード（１０２）から前記共用リストの次のノード（１０３）への第１のインクリメントコマンド（１）を発する手段を含む上記６記載のＳＣＩシステムインクリメント更新システム。
【００５０】
９．  前記複数のノード（１０２、１０３、１０４）の内のノードは、前記ノードが前記更新コマンドを受け取る前に前記共用リストからロールアウトすることを防止するロールアウト防止手段を含む上記６記載のＳＣＩシステムインクリメント更新システム。
【００５１】
１０．  前記ロールアウト防止手段は、前記ノードのそれぞれが前記第１のノード（１０２）から発せられた前記更新コマンドによってインクリメントされるとき前記共用リスト中の前記ノードのそれぞれの位相値（５０４）をトグルする手段を含む上記９記載のＳＣＩシステムインクリメント更新システム。
【００５２】
【発明の効果】
上述のように、本発明によれば、ＳＣＩ共用リストの先頭のノードの位置を維持しながら、この先頭ノードから他のノードに更新コマンドを発し、リストの末尾に達するまで先頭ノードにリスト中の連続するノードのそれぞれにインクリメントコマンドを送ることができる。
【００５３】
また、あるノードがこの更新コマンドを受け取るまではこのノードが共用リストからロールアウトすることを防止することができる。そして、ロールアウトされるノードが適正な位相を有するロールアウト要求を発するまではこのノードのインクリメントを禁止するデッドロックを提供することができる。
【図面の簡単な説明】
【図１】ＳＣＩ共用リストを更新する本発明の方法を示す図である。
【図２】ＳＣＩ共用リストを更新する本発明の方法を示す図である。
【図３】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内のテーブル初期設定状態機械を記述する疑似コードを示す図である。
【図４】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の要求状態機械を記述する疑似コードを示す図である。
【図５】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の競合要求状態機械を記述する疑似コードを示す図である。
【図６】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の競合要求状態機械を記述する疑似コードを示す図である。
【図７】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の競合要求状態機械を記述する疑似コードを示す図である。
【図８】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の競合要求状態機械を記述する疑似コードを示す図である。
【図９】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の競合要求状態機械を記述する疑似コードを示す図である。
【図１０】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の応答状態機械を記述する疑似コードを示す図である。
【図１１】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の応答状態機械を記述する疑似コードを示す図である。
【図１２】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の応答状態機械を記述する疑似コードを示す図である。
【図１３】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の応答状態機械を記述する疑似コードを示す図である。
【図１４】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の応答状態機械を記述する疑似コードを示す図である。
【図１５】本発明のインクリメント更新法を実行するためのＳＣＩコントローラ内の応答状態機械を記述する疑似コードを示す図である。
【図１６】キャッシュ状態のさまざまな変化を示す図である。
【図１７】キャッシュ状態のさまざまな変化を示す図である。
【図１８】ＭＶ＿バック＿イン状態あるいはＴＶ＿バック＿イン状態のキャッシュ列の状態図であり、併せてその挙動を示す図である。
【図１９】共用リストの現在の先頭からインクリメント要求を受けたときのＭＶ＿バック＿インあるいはＴＶ＿バック＿イン  ムーブスルーであるキャッシュのフロー状態を示す図である。
【図２０】応答パケット内のＰで示す共用位相ビットを示す図である。
【図２１】標準ＳＣＩ動作を用いてＳＣＩ共用リストを更新するステップを示す図である。
【図２２】標準ＳＣＩ動作を用いてＳＣＩ共用リストを更新するステップを示す図である。
【図２３】標準ＳＣＩ動作を用いてＳＣＩ共用リストを更新するステップを示す図である。
【符号の説明】
１００  ＳＣＩ共用リスト
１０１  メモリ
１０２  ノード０
１０３  ノード１
１０４  ノード２
５００  状態機械
６００  応答送出パケット
６０１  共用位相ビット
【図１】
0003671193.tif 000002
【図２】
0003671193.tif 000003
【図３】
0003671193.tif 000004
【図４】
0003671193.tif 000005
【図５】
0003671193.tif 000006
【図６】
0003671193.tif 000007
【図７】
0003671193.tif 000008
【図８】
0003671193.tif 000009
【図９】
0003671193.tif 000010
【図１０】
0003671193.tif 000011
【図１１】
0003671193.tif 000012
【図１２】
0003671193.tif 000013
【図１３】
0003671193.tif 000014
【図１４】
0003671193.tif 000015
【図１５】
0003671193.tif 000016
【図１６】
0003671193.tif 000017
【図１７】
0003671193.tif 000018
【図１８】
0003671193.tif 000019
【図１９】
0003671193.tif 000020
【図２０】
0003671193.tif 000021
【図２１】
0003671193.tif 000022
【図２２】
0003671193.tif 000023
【図２３】
0003671193.tif 000024