(57)【特許請求の範囲】
【請求項１】
複数のノードと、前記複数のノードを接続する相互結合網と、前記複数のノードがアクセスするメインメモリを有するマルチプロセッサシステムにおいて、
前記複数のノードの各々は、
前記メインメモリとの間で授受されるデータを保持するキャッシュメモリと、
前記メインメモリに対して自ノードが行なった第１のリード要求の要求先メインメモリアドレスを格納する第１の記憶部と、
あるノードが前記メインメモリに対して第２のリード要求を行なった時、前記第２のリード要求よりも以前に実行されていた同一のメインメモリアドレスに対する第１のリード要求が終了していなかった為に前記第２のリード要求がリトライ待機中となったことを示すステータス情報、前記第２のリード要求の要求元情報、および前記第２のリ−ド要求の要求先メインメモリアドレスを格納する第２の記憶部と、
前記メインメモリに対するリード要求によるトランザクション、および他ノードからリード要求されたデータに対する自ノードのキャッシュデータの有効性を示すキャッシュ状態情報を送受信する第１の通信部とを設け、
前記相互結合網は、
前記複数のノードの各々から送信された前記トランザクションおよび前記キャッシュ状態情報を受信する第２の通信部と、
前記第２の通信部が受信した前記キャッシュ状態情報を集約する論理部とを設け、
前記第２の通信部は前記論理部が集約した集約結果および前記トランザクションを全ノードに送信し、
前記複数のノードの各々は、自ノードの第３のリード要求のデータが自ノードの前記キャッシュメモリにない場合に、前記第２の記憶部に格納した情報を参照し、前記メインメモリに対しての前記第３のリード要求と同一のメインメモリアドレスの前記第２のリード要求がリトライ待機中であるかどうかを判断し、前記第３のリード要求を行なうか否かを決定する制御部を備えることを特徴とするマルチプロセッサシステム。
【請求項２】
請求項１に記載のマルチプロセッサシステムにおいて、
各ノードの前記第１の通信部が前記相互結合網からの前記トランザクションおよび前記集約結果を受信し、
前記トランザクションのデータであるリードアクセス対象のアドレスおよび前記集約結果により、前記第２の記憶部に格納された情報を更新することを特徴とするマルチプロセッサシステム。
【請求項３】
請求項１に記載のマルチプロセッサシステムにおいて、
同一のアドレスに対して複数のリード要求がされている場合に、前記第２の記憶部に前記複数のリード要求の優先順位をさらに格納することを特徴とするマルチプロセッサシステム。
【請求項４】
複数のプロセッサモジュールであって、
前記複数のプロセッサモジュールの各々は、
データ処理を行なうプロセッサと、
自モジュール及び他モジュールのプロセッサが処理するデータを格納するメインメモリと、
前記プロセッサが処理するデータを一時格納するキャッシュメモリとを有し、
前記メインメモリに対して自モジュールのプロセッサが行なった第１のリード要求の要求先メインメモリアドレスを格納する第１の記憶部と、
あるモジュールのプロセッサが前記メインメモリに対して第２のリード要求を行なった時、前記第２のリード要求よりも以前に実行されていた同一のメインメモリアドレスに対する第１のリード要求が終了していなかった為に前記第２のリード要求がリトライ待機中となったことを示すステータス情報、前記第２のリード要求の要求元情報、および前記第２のリ−ド要求の要求先メインメモリアドレスを格納する第２の記憶部と、
前記メインメモリに対するリード要求によるトランザクションおよび他モジュールのプロセッサが行なったリード要求に対する自モジュールのキャッシュ状態情報を送受信する通信部とを設け、
自モジュールのプロセッサが前記キャッシュメモリに格納されていないデータに対する第３のリード要求をする場合に、
前記第２の記憶部に格納されている情報を参照し、前記メインメモリに対しての前記第３のリード要求と同一のメインメモリアドレスの前記第２のリード要求がリトライ待機中であるかどうかを判断し、前記第３のリード要求をするか否かを決定するキャッシュメモリ制御部を有する複数のプロセッサモジュールと、
前記複数のプロセッサモジュールを接続する相互結合網であって、
前記複数のプロセッサモジュールが出力したキャッシュ状態情報を集約した集約結果およびトランザクションを全てのプロセッサモジュールに通知する相互結合網を有することを特徴とするマルチプロセッサシステム。
【請求項５】
相互結合網を介して接続された他のノードとメインメモリを共有し、
前記メインメモリのデータを一時格納するキャッシュメモリと、ノードが行なったリード要求の処理状態を保持する記憶部を有する複数のノードに対するキャッシュ・コヒーレンシ制御方法において、
前記記憶部は、前記メインメモリに対して自ノードが行なった第１のリード要求の要求先メインメモリアドレスを格納する第１の記憶部と、
あるノードが前記メインメモリに対して第２のリード要求を行なった時、前記第２のリード要求よりも以前に実行されていた同一のメインメモリアドレスに対する第１のリード要求が終了していなかった為に前記第２のリード要求がリトライ待機中となったことを示すステータス情報、前記第２のリード要求の要求元情報、および前記第２のリ−ド要求の要求先メインメモリアドレスを格納する第２の記憶部とから成り、
前記キャッシュメモリにデータがない場合には、
前記第２の記憶部に格納した情報を参照し、
前記他のノードの前記データに対する第２のリード要求がリトライ待機中となっている場合は自ノードからの第３のリード要求を中止し、
前記他のノードの前記データに対する第２のリード要求がリトライ待機中となっていない場合は第３のリード要求を発行することを特徴とするキャッシュ・コヒーレンシ制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数のプロセッサを有するマルチプロセッサシステムに関する。
【０００２】
【従来の技術】
計算機システムの処理速度を向上させるために、キャッシュメモリの使用が有効であることはよく知られている。キャッシュメモリは、プロセッサとメインメモリの間に位置する高速、小容量のメモリのことをいう。キャッシュメモリは、メインメモリのデータの一部を保持し、メインメモリの代わりにプロセッサとのデータの送受信を行い、メインメモリよりも高速なデータアクセスを実現する。
【０００３】
このようなキャッシュメモリを使用した計算機システムでは、プロセッサがリード要求を発行したときにキャッシュメモリにデータが格納されている（すなわちヒットした）場合、キャッシュメモリ内のデータが直ちにプロセッサに送信され、高速な動作を実現することができる。
【０００４】
プロセッサからのメインメモリへのリード要求に対し、キャッシュメモリにそのデータがなかった（すなわちミスした）場合は、キャッシュメモリはプロセッサが要求したデータをメインメモリから読み込んで、これをプロセッサに供給する。
【０００５】
ここで、複数のキャッシュメモリを有する計算機システムにおいては、メインメモリからキャッシュメモリにデータを読み込む際にキャッシュ・コヒーレンシ一貫性制御が要求される。キャッシュ・コヒーレンシ一貫性制御とは、メインメモリ上の同一アドレスにあるデータのコピーを二つ以上のキャッシュメモリが保持する場合に同一の値を持つこと（キャッシュ・コヒーレンシ一貫性）を保証するための制御である。
【０００６】
キャッシュ・コヒーレンシ一貫性制御の例を図１２に示されるシステムで説明する。図１２のシステムは、ノード（１００）を複数（ｘＮＤ０〜ｘＮＤｎ）有し、それらが相互結合網１（１１１）と相互結合網２（１１２）によって相互に接続されている構成である。
【０００７】
ノード（１００）は、プロセッサ（１０１）とキャッシュメモリ（１０３）、キャッシュタグ（１０４）、メインメモリ（１０５）とキャッシュ・メインメモリ制御装置（１０２）を有する。キャッシュ・メインメモリ制御装置（１０２）は、プロセッサ（１０１）や相互結合網１（１１１）を介した他ノードからの要求に応じて、キャッシュメモリ（１０３）、キャッシュタグ（１０４）、メインメモリ（１０５）のデータの読み出し、書き込みを行なう。
【０００８】
キャッシュ・メインメモリ制御装置（１０２）は、よく知られたＭＥＳＩキャッシュ・コヒーレンシ・プロトコルに従ったキャッシュ・コヒーレンシ一貫性制御を行なうものとする。すなわち、キャッシュ状態として、（ａ）Ｉｎｖａｌｉｄ（当該データは無効）、（ｂ）Ｓｈａｒｅｄ−Ｕｎｍｏｄｉｆｉｅｄ（当該データは他のプロセッサのキャッシュメモリ内にも存在し、主記憶内のデータと同一）、（ｃ）Ｅｘｃｌｕｓｉｖｅ‐Ｍｏｄｉｆｉｅｄ（当該データは、当該キャッシュメモリ内にのみ存在し、しかも主記憶内のデータとは同一ではない）、（ｄ）Ｅｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ（当該データは、当該キャッシュメモリ内にのみ存在し、主記憶内のデータとは同一）を定義する。任意のノードにおいてリード要求が発生し、当該データが自ノード内のキャッシュメモリにない（リードミス）の場合には、相互結合網１にリード・トランザクションをブロードキャスト（同報送信）し、全ノードがそれを受信する。
【０００９】
この時、いずれかのノード内キャッシュメモリにヒットした場合には、当該ノードから要求元のノードにデータを転送する。一方、いずれのノード内のキャッシュメモリにもヒットしなかった場合には、要求されたデータを保持するメインメモリからデータリターンを行なう。また、キャッシュメモリ内の置換（キャッシュメモリ内に空き領域を作るために既存のデータを追い出す操作）対象となったデータラインがＥｘｃｌｕｓｉｖｅ‐Ｍｏｄｉｆｉｅｄの場合には、メインメモリに反映させるべく、相互結合網１にライト・トランザクションを送出する。
【００１０】
相互結合網１はノード間でやり取りされるトランザクションを配信する。相互結合網２は、リード・トランザクションを受信したノードがキャッシュ・コヒーレンシ一貫性制御を行なう際の応答メッセージをノード間で配信する。
【００１１】
図１３は、このようなシステムにおいて、メインメモリからキャッシュメモリにデータを読み込み、プロセッサにそのデータを供給する動作を図示するタイミングチャートである。図１３において、縦方向は動作に関係する各ノードまたはノード内の構成要素を示し、横方向は各ノードの動作の時間軸を示す。また、図１３におけるシステムは、ｘＮＤ０〜ｘＮＤ２の３ノードの構成とする。
【００１２】
図１３において、まず、ノードｘＮＤ０のプロセッサがメモリリード要求を発行する。この要求のデータが自ノードのキャッシュメモリにおいて、キャッシュ状態Ｉｎｖａｌｉｄであり、すなわちキャッシュミスを起こしたとする。すると、ｘＮＤ０のキャッシュ・メインメモリ制御装置は、相互結合網１にこのアドレスのデータを要求するリード・トランザクションを発行する。相互結合網１はこのリード・トランザクションを全ノードに配信する。
【００１３】
ｘＮＤ１とｘＮＤ２はこのリード・トランザクションを受信すると、リード要求のアドレスのデータが自ノードのキャッシュ上にどのような状態で格納されているかを調べる。ｘＮＤ１、ｘＮＤ２ともに要求されたデータは自ノードのキャッシュ上でＩｎｖａｌｉｄ状態であったとすると、ｘＮＤ１とｘＮＤ２はそれぞれ、キャッシュ・コヒーレンシ一貫性制御結果として、メッセージ’Ｉｎｖ’を相互結合網２に送信する。ここで、’Ｉｎｖ’は要求されたデータが自ノードのキャッシュ上でＩｎｖａｌｉｄ状態であることを示すメッセージであるとする。相互結合網２はこの’Ｉｎｖ’メッセージをｘＮＤ０に配信する。
【００１４】
’Ｉｎｖ’を受信したｘＮＤ０は、他ノードのキャッシュ状態が全てＩｎｖａｌｉｄ状態であることを判定し、メインメモリからのデータを使用することを決定する。要求されたデータがｘＮＤ０のメインメモリのデータであるとすると、ｘＮＤ０のキャッシュ・メインメモリ制御装置は自ノードのメインメモリから要求されたデータを読み出し、これをキャッシュメモリにＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ状態で格納し、プロセッサにこのデータを供給して、リードの処理を完了させる。
【００１５】
このようなキャッシュ・コヒーレンシ一貫性制御の例としては、例えば特開平１０−１６１９３０号公報に示されるようなシステムが知られている。特開平１０−１６１９３０号公報では、複数のキャッシュメモリを有する計算機システムにおいて、あるキャッシュメモリからメインメモリへの書き込み要求と、同一メインメモリアドレスからの他のキャッシュへの読み出し要求が時間的に近接して発生した場合に、キャッシュ一貫性を保証しつつ、この競合を解決する方法について示している。
【００１６】
【発明が解決しようとする課題】
特開平１０−１６１９３０号公報では、ライトとリードが競合したときの解決方法を示しているが、リードと同一アドレスに対する別のリードが競合したときの解決方法については何も述べていない。前述の従来技術の場合には、リードと同一アドレスに対する別のリードが時間的に近接して発行されるような場合に、キャッシュ一貫性に問題が生じる可能性がある。これを示したのが図１４である。
【００１７】
図１４はｘＮＤ０のプロセッサがデータのリードを発行し、その処理が完了する前にｘＮＤ１のプロセッサも同じアドレスのデータのリードを発行したときの動作を示している。図１4において、縦方向は動作に関係する各ノードまたはノード内の構成要素を示し、横方向は各ノードの動作の時間軸を４つのフェーズに分けたものを示している。
【００１８】
（フェーズ１）
ｘＮＤ０のプロセッサがリード要求を発行する。要求されたデータのキャッシュ状態はＩｎｖａｌｉｄであり、キャッシュミスを起こす。キャッシュ・メインメモリ制御装置は相互結合網１にリード・トランザクションを発行する。相互結合網１は全ノードにリード・トランザクションを配信する。ｘＮＤ１とｘＮＤ２はリード・トランザクションを受けると、自ノードのキャッシュ状態を調べ、Ｉｎｖａｌｉｄ状態であることを示すメッセージ’Ｉｎｖ’を相互結合網２に送信したとする。相互結合網２はｘＮＤ１とｘＮＤ２から送信された’Ｉｎｖ’メッセージをｘＮＤ０に送信する。
【００１９】
（フェーズ２）
ｘＮＤ１のプロセッサがリード要求を発行する。リード要求のアドレスは（フェーズ１）でｘＮＤ０のプロセッサが発行したリード要求のアドレスと同一であるとする。ｘＮＤ１はキャッシュミスを起こす。キャッシュ・メインメモリ制御装置は相互結合網１にリード・トランザクションを発行する。相互結合網１は全ノードにリード・トランザクションを配信する。ｘＮＤ０とｘＮＤ２はリード・トランザクションを受けると、自ノードのキャッシュ状態を調べ、Ｉｎｖａｌｉｄ状態であることを示すメッセージ’Ｉｎｖ’を相互結合網２に送信する。相互結合網２はこの’Ｉｎｖ’メッセージをｘＮＤ１に配信する。
【００２０】
（フェーズ３）
ｘＮＤ０は（フェーズ１）のリード要求の処理を継続し、メインメモリからのデータを受信する。ｘＮＤ０は（フェーズ１）においてｘＮＤ１とｘＮＤ２の双方からキャッシュ・コヒーレンシ一貫性制御の結果のメッセージ’Ｉｎｖ’を受信しているので、このメインメモリからのデータをキャッシュメモリにＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ状態で登録して、プロセッサにデータを供給して、リード処理を完了する。
【００２１】
（フェーズ４）
ｘＮＤ１は（フェーズ２）のリード要求の処理を継続し、メインメモリからのデータを受信する。ｘＮＤ０も（フェーズ２）においてｘＮＤ０とｘＮＤ２の双方からキャッシュ・コヒーレンシ一貫性制御の結果のメッセージ’Ｉｎｖ’を受信しているので、このメインメモリからのデータをキャッシュメモリにＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ状態で登録して、プロセッサにデータを供給して、リード処理を完了する。
【００２２】
このように、Ｅｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄの状態でデータを保持するキャッシュはシステム内でただひとつでなければならないにもかかわらず、上記の動作では二つのキャッシュメモリがＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄの状態でデータを保持することになる。従って以後のプロセッサのデータ書き込み動作によってはキャッシュ一貫性が保証されない可能性がある。
【００２３】
上記の問題はキャッシュメモリがメインメモリからのデータの読み込みの処理を実行中であり、キャッシュの状態が確定していないにもかかわらず、別のキャッシュメモリからのキャッシュ・コヒーレンシ一貫性制御要求に応答して、キャッシュ・コヒーレンシ一貫性制御結果を出力してしまうことにより発生する。
【００２４】
本発明の目的は複数のキャッシュメモリが時間的に近接してメインメモリからのデータの読み込みの処理を実行した場合にも、正しいキャッシュ・コヒーレンシ一貫性制御を実現することが可能なマルチプロセッサシステムを提供することである。
【００２５】
また、本発明の別の目的はキャッシュ・コヒーレンシ一貫性を保つために、キャッシュ・コヒーレンシ一貫性制御要求に対する中止と再実行を要求しても、キャッシュ・コヒーレンシ一貫性制御要求の沈み込みを防ぐことが可能なマルチプロセッサシステムを提供することにある。  その他の目的については、以下の説明であきらかになるであろう。
【００２６】
【課題を解決するための手段】
本発明では、各ノードはシステムにおいて発信されたリードアクセス要求に関する情報を備える。各ノードは、自ノードにおいてキャッシュミスが生じた場合に、この情報を参照して、必要とするデータに対して現在すでにリードアクセス要求がされているかどうかを判断し、自ノードがリード要求することができるかどうかを判断する。
【００２７】
また、本発明では、このリードアクセス要求に関する情報には、自ノードが発信したアクセス要求の状態情報を含む。他ノードから発信されたリードアクセス要求を受信すると、この情報を参照して自ノードにおいてすでにリードアクセス要求をしたものであるかどうかを判断し、その結果を出力する。
【００２８】
また、本発明では、このリードアクセス要求に関する情報には、各リードアクセス要求が行なわれる優先順位についての情報も含まれる。これらの情報を用いて、次に行なわれるリードアクセス要求が決定される。
【００２９】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００３０】
図１は、本発明に関する第１の実施の形態であるマルチプロセッサ１１システムの全体構成の一例を示す概念図である。
【００３１】
図１に例示されるように、本実施の形態のマルチプロセッサ１１システムは、複数のノードＮＤ０〜ＮＤｎ（１０）が、相互結合網A（２０）と相互結合網Ｂ（３０）を介して結合された構成となっている。ノードとは、各々が独立してデータ処理を行なうプロセッサ１１モジュールのことをいう。本実施例において、各ノードＮＤＯ〜ＮＤｎは、クロスバスバスイッチによって実現するものとするが、これに限らず、バスを用いる構成としてもよいことはいうまでもない。
【００３２】
図２はノード（１０）の構成を示す概念図である。図２に例示されるように、個々のノード１０は、プロセッサ１１、キャッシュ・メインメモリ制御部１２、キャッシュメモリ１３ａ、キャッシュタグ１３ｂ、メインメモリ１３ｃ、リクエスト管理テーブル１４、ＣＣＣ受信部１５、トランザクション受信部１６、ＣＣＣ送信部１７、トランザクション送信部１８、スターベーション管理部１９を備えている。
【００３３】
プロセッサ１１は、各種データを演算するものであり、汎用のマイクロプロセッサ１１で構成されるものである。メインメモリ１３ｃは、プロセッサ１１が処理するためのデータ、プログラムがロードされる。キャッシュメモリ１３ａは、このプロセッサ１１とメインメモリ１３ｃまたはノード１０の外部との間で授受されるデータを一時的に保持する。キャッシュ・メインメモリ制御部１２は、メインメモリ１３ｃ、キャッシュメモリ１３ａのデータ転送等の制御を行なう。キャッシュタグ１３ｂは、キャッシュ・メインメモリ制御部１２がキャッシュメモリ１３ａを制御する際に用いる制御情報を格納する。トランザクション受信部１６、トランザクション送信部１８は、相互結合網A（２０）を介して他のノードとの間における情報の授受を行なう。ＣＣＣ受信部１５、ＣＣＣ送信部１７は、相互結合網Ｂ（３０）を介してキャッシュ・コヒーレンシ一貫性制御結果（ＣＣＣ）を送信又は受信をする。
【００３４】
さらに個々のノード（１０）は、自ノードが相互結合網Aを介してノードに発行したメモリアクセスを管理するためのリクエスト管理テーブル部（１４）と、キャッシュ・コヒーレンシ一貫性制御結果がリトライとなったメモリアクセス要求のアドレスと要求元を記録するためのスターベーション管理部（１９）を備えている。
【００３５】
なお、本実施形態においては、キャッシュ・メインメモリ制御部１２はよく知られたＭＥＳＩキャッシュ・コヒーレンシ・プロトコルに従ったキャッシュ・コヒーレンシ一貫性制御を行なうものとする。すなわち、キャッシュ状態として、（ａ）Ｉｎｖａｌｉｄ（当該データは無効）、（ｂ）Ｓｈａｒｅｄ−Ｕｎｍｏｄｉｆｉｅｄ（当該データは他のプロセッサ１１のキャッシュメモリ１３ａ内にも存在し、主記憶内のデータと同一）、（ｃ）Ｅｘｃｌｕｓｉｖｅ‐Ｍｏｄｉｆｉｅｄ（当該データは、当該キャッシュメモリ１３ａ内にのみ存在し、しかも主記憶内のデータとは同一ではない）、（ｄ）Ｅｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ（当該データは、当該キャッシュメモリ１３ａ内にのみ存在し、主記憶内のデータとは同一）を定義する。
【００３６】
任意のノードにおいてリード要求が発生し、当該データが自ノード内のキャッシュメモリ１３ａにない（リードミスの）場合には、相互結合網A（２０）にリード・トランザクションをブロードキャスト（同報送信）し、他のノード（ＮＤ）がそれを受信する。この時、ノード内キャッシュメモリ１３ａにヒットした場合には、当該ノードから要求元のノードにデータを転送し、一方、いずれのノード内のキャッシュメモリ１３ａにもヒットしなかった場合には、メインメモリからデータリターンが行なわれる。また、キャッシュメモリ１３ａ内の置換（キャッシュメモリ１３ａ内に空き領域を作るために既存のデータを追い出す操作）対象となったデータラインがＥｘｃｌｕｓｉｖｅ‐Ｍｏｄｉｆｉｅｄの場合には、メインメモリに反映させるべく、相互結合網Aにライト・トランザクションを送出する。
【００３７】
図３は相互結合網A（２０）の構成図である。図３に例示されるように、相互結合網A（２０）は、各ノード間で、１：１または１：多（同報送信）の接続制御を行なうスイッチ結合論理２３を有する。スイッチ結合論理２３と各ノードとは、各ポート２２ａ、２２ｂで接続される。各ノードが接続されるポート２２ａ、２２ｂの間の接続を切り替えることにより、１：１または１：多（同報送信）の接続制御が行なわれる。また、各ポート２２ａ、ｂには、トランザクションキュー２１ａ、２１ｂを備えている。
【００３８】
図４は相互結合網Ｂ（３０）の構成図である。図４に例示されるように、ノードから出力されたＣＣＣ信号を受信するＣＣＣ受信キュー３１ａと、各ノードから受信したＣＣＣ信号をまとめてノード全体のコヒーレンシ一貫性制御の結果を集計する集計論理部（３３）、集計されたＣＣＣ信号を各ノードに送信するＣＣＣ送信キュー３１ｂで構成される。
【００３９】
ここで、ノードの出力するＣＣＣ信号としては、次の４種を定義する。
‘Ｉｎｖ’：要求されたデータ（キャッシュライン）は当該ノード内では無効（ＩＮＶＡＬＩＤ）である。
'Ｓｕｐ'：要求されたキャッシュラインは自キャッシュメモリ１３ａに"ＥＸＣＬＵＳＩＶＥ−ＭＯＤＩＦＩＥＤ"で存在し、当該データを要求元に転送供給（ＳＵＰＰＬＹ）し、転送した当該キャッシュラインは"ＩＮＶＡＬＩＤ"とする。要求元のノードは、当該キャッシュラインを受領後"ＥＸＣＬＵＳＩＶＥ−ＭＯＤＩＦＩＥＤ"として扱う。
'Ｓｈｒ'：要求されたデータ（キャッシュライン）は当該ノード内では（Ｓｈａｒｅｄ−Ｕｎｍｏｄｉｆｉｅｄ）である。
'Ｒｔｙ'：要求されたデータ（キャッシュライン）は他のトランザクションによるキャッシュ・コヒーレンシ一貫性制御を実行中であり、キャッシュ状態が確定していないため、データ要求の中止と再実行を要求する。
【００４０】
上記４種のＣＣＣ信号を各ノードから受信して、ＣＣＣ信号が集まったところで（キャッシュ・コヒーレンシ一貫性制御を要求したノードを除く）、集計論理部（３３）は集計結果を決定する。その方法は下記の通りである。
全てのＣＣＣ信号が’Ｉｎｖ’であったとき：集計結果は’Ｉｎｖ’。
'Ｓｈｒ'がひとつ以上存在し、'Ｒｔｙ'が含まれていなかったとき：集計結果は 'Ｓｈｒ'。
'Ｓｕｐ'が含まれていたとき：集計結果は'Ｓｕｐ'。
'Ｒｔｙ'が含まれていたとき：集計結果は'Ｒｔｙ'。ただし、同時に'Ｓｕｐ'が含まれていたときは'Ｓｕｐ'を優先し、集計結果は'Ｓｕｐ'になるものとする。
【００４１】
上記以外の組み合わせが出現しないようにキャッシュは制御される。集計論理部（３３）の出力した集計結果は、ＣＣＣ送信キュー３１ｂを経由して、全ノードに同報送信される。ＣＣＣ信号はイン・オーダで処理するものとする。
【００４２】
図５は、リクエスト管理テーブル部１４の構成図である。図５に示されるように、リクエスト管理テーブル部１４は、自ノード外のメモリに対して自ノードのキャッシュ・メインメモリ制御部１２が行なったアクセスリクエストのアドレスを保持する複数のレジスタ１４ｂで構成され、キャッシュ・メインメモリ制御部１２により、パス１４ａを介して、アドレスの登録、アドレス登録の抹消などが行われる。
【００４３】
図６はトランザクション受信部１６を説明するための構成図である。図６で示されるように、トランザクション受信部１６は、バス１６aを介して、相互結合網Ａから他ノードが発信したトランザクションを受信する。また受信したトランザクションを、キャッシュ・メインメモリ制御部１２へ送信する。トランザクション受信部１６は、キャッシュ・コヒーレンシ一貫性制御を要求するトランザクションを格納するキュー１６ｄ、キュー１６ｄのライトポインタ１６ｆとリードポインタ１６ｅを有する。
【００４４】
ライトポインタ１６ｆは、キャッシュ・コヒーレンシ一貫性制御を要求するトランザクションを順次キュー１６ｄへの格納する制御に用いられるものである。リードポインタ１６ｅは、ＣＣＣ受信部１５からＣＣＣ信号が到着したことを示す信号１５ｃを受け、そのＣＣＣ信号に対応するトランザクションをスターベーション管理部１９にパス１６ｃを介して送信する制御に用いられる。このＣＣＣ信号は、図４を用いて説明したように、各モードからのＣＣＣ信号結果を集約したものである。
【００４５】
本実施の形態においては、このリクエスト管理テーブルを参照することによって、自ノードが発行したリード・トランザクションが、発行されているのか、発行されていないのか、処理中であるのか、などのステータス情報を他ノードに提供することが可能となる。
【００４６】
図７は、スターベーション管理部１９の構成図である。図７に示されるように、スターベーション管理部１９はスターベーション・レジスタ１９ｃ、スターベーション・レジスタ読み出し制御部１９ｄとスターベーション・レジスタ書き込み制御部１９ｅを有する。スターベーション・レジスタ１９ｃは、ノード毎にリード・トランザクションが要求するデータのアクセス先であるアドレスを保持するレジスタ１９ｃｂと保持された値の有効性を示すバリッドビット１９ｃａを有する。
【００４７】
本実施の形態におけるスターベーション・レジスタ書き込み制御部１９ｅは、主に他のノードが発信したトランザクションの管理を行なうものである。パス１５ｂからＣＣＣ信号を、そのＣＣＣ信号に対応するトランザクションをパス１６ｃから受信する。このとき、スターベーション・レジスタ書き込み制御部１９ｅは以下のように動作する。
ＣＣＣ信号がＲｔｙの場合：パス１６ｃから受け取ったトランザクションに埋め込まれた情報からトランザクションの発行元ノードを判定し、そのノードに対応するバリッドビット１９ｃａを読み出す。バリッドビッドが点灯していない場合は点灯させ、トランザクションに埋め込まれているアドレスをレジスタ１９ｃｂに書き込む。バリッド信号の点灯は、対象となるアドレスについて、このノードがリトライ待機中であるということを示す。リトライ待機中のノードとは、現在処理中の他ノードのリード・トランザクションが終了後に、そのデータに関する次のリード・トランザクションのリトライをするノードのことをいう。
ＣＣＣ信号がＲｔｙ以外の場合：パス１６ｃから受け取ったトランザクションに埋め込まれた情報からトランザクションの発行元ノードを判定し、そのノードに対応するバリッドビット１９ｃａとレジスタ１９ｃｂを読み出す。バリッドが点灯していたなら、レジスタ１９ｃｂから読み出した値と、トランザクションに埋め込まれているアドレスとを比較し、一致したなら、バリッドビット１９ｃａを消灯させる。ＣＣＣ信号がＲｔｙではないことは、発行元のノードによるトランザクションのリトライが成功したことを意味する。従って、バリッドビッド１９ｃａを消灯は、次にリトライすべきノードの特定を解除するためのものである。
【００４８】
本実施の形態のスターベーション・レジスタ読み出し制御部１９ｄは、主に自ノードがキャッシュミスをした後に、リード・トランザクション発行する際に必要な処理を行なうものである。すなわち、プロセッサからリクエストが出されたデータに関してキャッシュミスが生じた場合に、そのデータに関する各ノードのステータスをチェックするものである。その際のスターベーション・レジスタ読み出し制御部１９ｄの動作は、以下の通りである。
【００４９】
キャッシュ・メインメモリ制御部１２（１２）からパス１９ｂを経由して、発信しようとしているリード・トランザクションの対象となるアドレス値を受信する。まず、自ノードに対応するバリッドビット１９ｃａとレジスタ１９ｃｂを読み出す。バリッドビットが消灯しているか、または自ノードのレジスタ１９ｃｂとパス１９ｂから受けたアドレスが一致しない場合は、対象となるデータに対してまだ自ノードからリード・トランザクションが発行されていないか、もしくは、リトライ待ちでない状態を示す。次に、自ノード以外のレジスタ１９ｃｂの中にパス１９ｂから受けたアドレスと一致するレジスタがないかどうか検索する。もし一致するレジスタがあり、さらにそのレジスタのバリッドビット１９ｃａが点灯している場合は、そのレジスタのノードが、そのアドレスに対してリトライ待機中であることを意味する。従って、パス１９ｂを介して受けたアドレスに対し、プロセッサ１１に対してリトライをすべき旨を示す信号を、１９ａを経由してキャッシュ・メインメモリ制御部１２に送信する。キャッシュ・メインメモリ制御部１２は、その旨をプロセッサ１１に対して通知する。
【００５０】
次に、本実施の形態で使用されるトランザクションのタイプについて、図８を参照して説明する。ノード間の情報の授受は、基本的には、図８に例示される６４ビット幅のデータ単位（トランザクション）を相互結合網Ａ（２０）の動作サイクル単位に時系列的に、相互結合網Ａ（２０）に送り出し、あるいは、相互結合網Ａ（２０）から受け取ることによって行われる。各トランザクションのデータ構成は、各トランザクションのタイプを示す領域（ＴＹＰＥ）、各々のトランザクションに関係するノード（要求元、転送先等）の識別情報等が格納される領域（ＰＯＲＴ）、相手先で各々のトランザクションを処理するときに使用される情報が格納される領域（ＭＩＳＣ）、リードアクセス対象のアドレスを格納する領域（ＡＤＤＲＥＳＳ）、さらに必要に応じて伝送されるデータを格納する領域（ＤＡＴＡ）を有している。次に、各々のトランザクションのデータ構成について説明する。
【００５１】
図８の（ａ）は、メモリモジュールと全プロセッサ１１モジュールにブロードキャスト（同報送信）されるリード・トランザクションを示している。８ビット幅のＴＹＰＥフィールドには、本トランザクションがリード・トランザクションであることを示すビットパターンが設定される。次の８ビットのＰＯＲＴフィールドには、宛て先情報として、要求先のメインメモリを保持するノードのポート番号と同時に他の全てのノードに同報送信すべきことを相互結合網A（２０）に指示する特定のビットパターンが設定される。次の１６ビットのＭＩＳＣフィールドには、たとえば、要求元であるノードのポート番号等の識別情報が設定さる。残りの３２ビットのＡＤＤＲＥＳＳフィールドは、リード対象のアドレスが設定される。
【００５２】
図８の（ｂ）は、メインメモリから読み出したデータを要求元に返すためのリターン・トランザクションを示す。ＴＹＰＥフィールドには、リターン・トランザクションを示す特定のビットパターンが設定され、ＰＯＲＴフィールドにはリード要求元のノードのポート番号が設定され、ＭＩＳＣフィールドには、たとえばデータ長（サイクル数）等のパラメータが設定され、残りのフィールドは未使用である。
【００５３】
図８の（ｃ）は、リード要求に対して、他ノードのキャッシュメモリ１３ａが更新された最新データを保持していたときに、これをリード要求元に転送する転送トランザクションを示している。ＴＹＰＥフィールドには、転送トランザクションを示す特定のビットパターンが設定され、ＰＯＲＴフィールドには転送先のノードのポート番号が設定され、ＭＩＳＣフィールドには、たとえばデータ長（サイクル数）等のパラメータが設定され、残りのフィールドは未使用である。
【００５４】
図８の（ｄ）は、メモリライトを要求するライト・トランザクションを示している。ＴＹＰＥフィールドには、ライト・トランザクションを示す特定のビットパターンが設定され、ＰＯＲＴフィールドには要求先のメインメモリを保持するノードのポート番号が設定され、ＭＩＳＣフィールドには、たとえばデータ長（サイクル数）等のパラメータが設定され、残りのフィールドは未使用である。
【００５５】
次に図９、図１０、図１１のタイミングチャートを参照して、本実施の形態のマルチプロセッサ１１システムおよびトランザクション制御の作用の一例を説明する。なお、図９と図１０、図１１において、縦方向には、動作に関係する各ノードまたはノード内の構成要素が配置され、横方向は各ノードの動作の時間軸を示す。時間軸は、行なわれる処理のまとまり毎に、フェーズ１〜６に区切られている。本実施の形態におけるマルチプロセッサ１１システムのノード数はＮＤ０〜ＮＤ２の３ノードとする。また、初期状態として、全ノードのリクエスト管理部１４に登録はなく、またスターベーション管理部１９のバリッドビット１９ｃａは全て消灯しているものとする。
【００５６】
（フェーズ１）
図９において、ＮＤ０のプロセッサ１１がリード要求を発行する。要求されたデータのキャッシュ状態はＩｎｖａｌｉｄであり、キャッシュミスを起こす。キャッシュ・メインメモリ制御装置は、アドレスをリクエスト管理テーブル１４に登録し、相互結合網Aにリード・トランザクションを発行する。相互結合網Aは全ノードにＮＤ０の発行したリード・トランザクションを配信する。ＮＤ１とＮＤ２はリード・トランザクションを受けると、自ノードのキャッシュ状態を調べ、Ｉｎｖａｌｉｄ状態であることを示すメッセージ’Ｉｎｖ’を相互結合網Ｂに送信する。相互結合網ＢはＮＤ１とＮＤ２から送信された’Ｉｎｖ’メッセージを受信し、これを集計して、集計結果’Ｉｎｖ’メッセージを全ノードに配信する。
【００５７】
（フェーズ２）
ＮＤ１のプロセッサ１１がリード要求を発行する。リード要求のアドレスは（フェーズ１）でＮＤ０のプロセッサ１１が発行したリード要求のアドレスと同一であるとする。従って、フェーズ１は、リード・トランザクションが処理中の状態において、同じアクセスに対するリード要求が発行された場合の具体的な処理を示している。
【００５８】
ＮＤ１はキャッシュミスを起こす。キャッシュ・メインメモリ制御装置はアドレスをリクエスト管理テーブル１４に登録し、相互結合網Aにリード・トランザクションを発行する。相互結合網Aは全ノードにＮＤ１の発行したリード・トランザクションを配信する。ＮＤ２は、トランザクション受信部１６において、リード・トランザクションを受ける。受け取った結果、キャッシュ・メインメモリ制御部１２が自ノードのキャッシュ状態を調べ、Ｉｎｖａｌｉｄ状態であることを示すメッセージ’Ｉｎｖ’を、ＣＣＣ送信部１７から相互結合網Ｂに送信する。
【００５９】
一方、このリード・トランザクションをトランザクション受信部１６で受信したＮＤ０は、キャッシュ・メインメモリ制御部１２がリクエスト管理テーブル１４を調べ、要求されたデータのアドレスが登録されているか否かをチェックする。ＮＤ０にはフェーズ１で要求されたデータのアドレスに対して、リード・トランザクションを発信しているため、このアドレスが登録されており、同一アドレスに対する自ノードのリード処理が実行中であることが判明する。ＮＤ０のリード処理は実行途中であり、キャッシュの状態が確定していないため、ＮＤ１のリード要求に対してキャッシュの状態を応答することができない。
【００６０】
この問題に対しては、たとえば、キャッシュメモリ１３ａがメインメモリからのデータの読み込みの処理を実行中で、キャッシュの状態が確定していない場合には、別のキャッシュメモリ１３ａからのキャッシュ・コヒーレンシ一貫性制御要求に対してはキャッシュ・コヒーレンシ一貫性制御要求の中止と再実行（リトライ）を要求する方法が考えられる。
【００６１】
このとき、次のような問題が生じる。例えば、ある第一のキャッシュメモリ１３ａがメインメモリからのデータの読み込みの処理を実行中であり、第二のキャッシュメモリ１３ａからのキャッシュ・コヒーレンシ一貫性制御要求に対してリトライを要求したとする。ここで、第一のキャッシュメモリ１３ａの処理が完了し、第二のキャッシュメモリ１３ａがキャッシュ・コヒーレンシ一貫性制御要求を再実行する直前に第三のキャッシュメモリ１３ａがキャッシュ・コヒーレンシ一貫性制御要求を発行したとする。すると、これより遅れてキャッシュ・コヒーレンシ一貫性制御要求の再実行をした第二のキャッシュメモリ１３ａは第三のキャッシュメモリ１３ａによって再びリトライを要求される。このようなことが繰り返されると、第二のキャッシュメモリ１３ａのキャッシュ・コヒーレンシ一貫性制御要求がいつまでも処理されず、沈み込み（スターベーション）を起こす可能性がある。この問題に関しては、（フェーズ４）で本発明により解決方法が示されるであろう。
【００６２】
ＮＤ０はキャッシュ・コヒーレンシ一貫性制御の結果として、ＮＤ１のリード要求の中止と再実行（リトライ）を要求するメッセージ'Ｒｔｙ'をＣＣＣ送信部１７から相互結合網Ｂに送信する。このように、各ノードは、自ノードの発信したリード・トランザクションが処理中の状態であるかどうかということに関して、他ノードにその情報を通知する。
【００６３】
次に、相互結合網Ｂは、ＮＤ２の発行した’Ｉｎｖ’メッセージとＮＤ０の発行した'Ｒｔｙ' メッセージを集計して、集計結果'Ｒｔｙ'メッセージを全ノードに配信する。
【００６４】
各ノードのＣＣＣ受信部１５は、このＣＣＣ信号を受け取り、スターベーション管理部１９に出力する。スターベーション管理部１９では、前述のように、ＮＤ１の発行したリード・トランザクションが送信されている。この処理では、前述のスターベーション・レジスタ書込み制御部１９ｅが処理を行なう。スターベーション・レジスタ書込み制御部１９ｅがスターベーション・レジスタ１９ｃのＮＤ１のバリッドビット１９ｃａを点灯させ、レジスタ１９ｃｂにリード・トランザクションのアドレスを登録する。このようにして、スターベーション・管理部を参照すれば、格納されたリード・トランザクションのアドレスに対して、現在処理中のＮＤ０のリード・トランザクションが終了した場合、次にＮＤ１のリード・トランザクションが処理される予定であることを、処理中のリード・トランザクションを発行したＮＤ０、リトライを要求されたリード・トランザクションを発行したＮＤ１を含めた各々のノードで把握することが可能となる。
【００６５】
一方、ＮＤ１は'Ｒｔｙ'メッセージを受信すると、プロセッサ１１に対してリード要求の再実行（リトライ）を要求し、リクエスト管理テーブル１４のアドレスの登録を抹消して、リード処理を完了する。その後、プロセッサ１１からリトライがされると、再度リード・トランザクションが実行されることとなる。
【００６６】
このように、ＮＤ０がリード処理を実行中であり、リクエスト管理テーブル１４に登録されているアドレスへの他ノードのリード要求に対して'Ｒｔｙ'を返答することにより、キャッシュメモリ１３ａの状態が確定していないアドレスに対して誤ったキャッシュ・コヒーレンシ一貫性制御結果を返答することを防ぐことができ、さらには正しくキャッシュ一貫性を保つことができる。
【００６７】
（フェーズ３）
ＮＤ０は（フェーズ１）のリード要求の処理を継続し、メインメモリのデータをキャッシュメモリ１３ａにＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ状態で登録して、プロセッサ１１にデータを供給する。また、リクエスト管理テーブル１４のアドレスの登録を抹消して、リード処理を完了する。
【００６８】
（フェーズ４）
図１０は図９の処理の続きを図示している。図１０のタイミングチャートの開始時点では、全ノードのスターベーション・レジスタ１９ｃのＮＤ１に対応するバリッドビット１９ｃａが点灯しており、またレジスタ１９ｃｂには（フェーズ２）でＮＤ１のプロセッサ１１が要求したリードアドレスが登録されている。
【００６９】
ここで、ＮＤ２のプロセッサ１１がリード要求を発行する。リード要求のアドレスは（フェーズ１）でＮＤ０のプロセッサ１１が発行したリード要求のアドレスおよび、（フェーズ２）でＮＤ１のプロセッサ１１が発行したリード要求のアドレスと同一であるとする。従って、リトライ待機中のノードがある場合に、それ以外のノードのプロセッサ１１が、同じアドレスに対してリクエストをした場合の説明である。
【００７０】
ＮＤ２のキャッシュはキャッシュミスを起こす。ＮＤ２のキャッシュ・メインメモリ制御部１２はパス１９ｂを経由して、スターベーション管理部１９に対して、リード要求のアドレスを送信する。ここで、図７で説明したように、スターベーション管理部１９のスターベーション・レジスタ読み出し制御部１９ｄはパス１９ｂから受信したアドレスに対して、スターベーション・レジスタ１９ｃの検索を行なう。ＮＤ２に対応するバリッドビットは点灯しておらず、ＮＤ１に対応するバリッドビットが点灯し、さらにレジスタ１９ｃａに登録されているアドレスはパス１９ｂから受信したアドレスに一致する。
【００７１】
上記の判定から、ＮＤ２のスターベーション管理部１９はパス１９ａを経由して、キャッシュ・メインメモリ制御部１２を経由して、プロセッサ１１から当該アドレスへのアクセスの中止および再実行（リトライ）を要求する信号を送信する。パス１９ａからリトライの要求を受けたＮＤ２のキャッシュ・メインメモリ制御部１２は相互結合網Aにリード・トランザクションを発行することなく、プロセッサ１１に対してリード要求の再実行を要求して、リード処理を完了する。
【００７２】
（フェーズ５）
次に、リード要求のリトライを要求されたＮＤ１のプロセッサ１１は再び、同一アドレスに対するリード要求を発するものとする。これは、次に処理される予定のリード・トランザクションを発行するべきノードが、リトライをする処理を示すものである。
【００７３】
ＮＤ１はキャッシュミスを起こす。キャッシュ・メインメモリ制御装置はアドレスをリクエスト管理テーブル１４に登録し、相互結合網Aに向かってリード・トランザクションを発行する。
【００７４】
相互結合網Aは全ノードにリード・トランザクションを配信する。ＮＤ２はリード・トランザクションを受けると、自ノードのキャッシュ状態を調べ、Ｉｎｖａｌｉｄ状態であることを示すメッセージ’Ｉｎｖ’を相互結合網Ｂに送信する。
【００７５】
リード・トランザクションを受信したＮＤ０は自ノードのキャッシュ状態を調べ、要求されたデータがＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ状態で登録されていることを認識する。ＮＤ０のキャッシュ・メインメモリ制御部１２はキャッシュの状態をＩｎｖａｌｉｄに変更した後、キャッシュ・コヒーレンシ一貫性制御結果として、’Ｉｎｖ’メッセージを相互結合網Ｂに送信する。また、ＮＤ０はリード・トランザクションの要求するアドレスが自ノードのメインメモリのデータを要求していることを判定し、メインメモリからデータを読み出して、相互結合網Aに送信する。
【００７６】
相互結合網ＢはＮＤ０とＮＤ２の’Ｉｎｖ’メッセージを集計して、集計結果’Ｉｎｖ’メッセージを全ノードに配信する。
【００７７】
このとき、各ノードのスターベーション管理部１９にはこの’Ｉｎｖ’メッセージとＮＤ１の発行したリード・トランザクションが送信されている。各ノードのスターベーション管理部１９はスターベーション・レジスタ１９ｃのＮＤ１のバリッドビット１９ｃａが点灯していることと、レジスタ１９ｃｂに登録されているアドレスがリード・トランザクションのアドレスと一致することを判定し、ＮＤ１のバリッドビット１９ｃａを消灯する。
【００７８】
相互結合網Ｂからの’Ｉｎｖ’メッセージと、ＮＤ０からのデータを受信したＮＤ１は、データをＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ状態でキャッシュメモリ１３ａに登録して、プロセッサ１１にデータを供給する。また、リクエスト管理テーブル１４のアドレスの登録を抹消して、リード処理を完了する。
【００７９】
このように、スターベーション管理部１９に'Ｒｔｙ'のキャッシュ・コヒーレンシ一貫性制御結果を受けたアドレスとメモリアクセスの要求元を登録して、該要求元以外からの該アドレスに対するメモリアクセスを抑止することによって、該要求元の優先度を上げて、要求の沈み込みを防ぐことができる。
【００８０】
（フェーズ６）
図１１は図１０の処理の続きを図示している。図１１のタイミングチャートの開始時点では、全ノードのスターベーション・レジスタのバリッドビット１９ｃａは全て消灯しており、また、どのノードでもリクエスト管理テーブル１４部にアドレスの登録はない。
【００８１】
リード要求のリトライを要求されたＮＤ２のプロセッサ１１は再び、同一アドレスに対するリード要求を発する。これは、次に処理されるべきリード・トランザクションがある場合に、リード・トランザクションを発行しなかったノードが、リトライをする処理を示す。
【００８２】
ＮＤ２はキャッシュミスを起こす。（フェーズ４）においては、ＮＤ２のキャッシュ・メインメモリ制御部１２はスターベーション管理部１９のリトライ指示により、相互結合網Aにリード・トランザクションを発行することなく、プロセッサ１１に対してリード要求の再実行を要求して、リード処理を完了した。ここでは、スターベーション・レジスタのバリッドビットは点灯していないため、キャッシュ・メインメモリ制御部１２はアドレスをリクエスト管理テーブル１４に登録し、相互結合網Aにリード・トランザクションを発行する。
【００８３】
相互結合網Aは全ノードにリード・トランザクションを配信する。
【００８４】
ＮＤ０はリード・トランザクションを受けると、自ノードのキャッシュ状態を調べ、Ｉｎｖａｌｉｄ状態であることを示すメッセージ’Ｉｎｖ’を相互結合網Ｂに送信する。リード・トランザクションを受信したＮＤ１は自ノードのキャッシュ状態を調べ、要求されたデータがＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ状態で登録されていることを判定する。ＮＤ１のキャッシュ・メインメモリ制御部１２はキャッシュの状態をＩｎｖａｌｉｄに変更した後、キャッシュ・コヒーレンシ一貫性制御結果として、’Ｉｎｖ’メッセージを相互結合網Ｂに送信する。また、ＮＤ０はリード・トランザクションの要求するアドレスが自ノードのメインメモリのデータを要求していることを判定し、メインメモリからデータを読み出して、相互結合網Aに送信する。
【００８５】
相互結合網ＢはＮＤ０とＮＤ１の’Ｉｎｖ’メッセージを集計して、集計結果’Ｉｎｖ’メッセージを全ノードに配信する。
【００８６】
相互結合網Ｂからの’Ｉｎｖ’メッセージとＮＤ０からのデータを受信したＮＤ２は、データをＥｘｃｌｕｓｉｖｅ−Ｕｎｍｏｄｉｆｉｅｄ状態でキャッシュメモリ１３ａに登録して、プロセッサ１１にデータを供給する。また、リクエスト管理テーブル１４のアドレスの登録を抹消して、リード処理を完了する。
【００８７】
このように、本実施の形態では、各ノードは、自ノードが発行したリード・トランザクションについてはリクエスト管理テーブル１４を用いて管理する。このリクエスト管理テーブル１４を用いて、他ノードからのリード・トランザクションを受け取った場合に、自ノードの発行状態を通知することが可能となる。また、相互結合網においては、いずれかのノードから発行されたリード・トランザクションに対応して各ノードから自己のキャッシュ状態に関する情報を集計し、いずれかのノードが発行したトランザクションが処理中であるかどうかを決定し、その決定結果を各ノードに通知する。このようにして、あるノードに対するリード・トランザクションが処理中であるのに、別のノードからリード・トランザクションが発行され、そのノードに対してキャッシュメモリが応答してしまうという事態を防止することが可能となる。
【００８８】
本実施の形態においては、さらに、相互結合網からの通知は、アドレスとともに各ノードのスターベーション管理部１９に登録され、次にリード・トランザクションをすることが可能なノードを決めることできる。さらには、このスターベーション管理部１９を用いて、自ノードからリード・トランザクションを発行すべきか否かを判断することが可能となる。このように、処理中のリード・トランザクションがある場合に、次に処理されるべきノードを定めることができ、それ以外のノードは、そのノードの処理が完了するまでは、同一アドレスに対するリード・トランザクションを発行しないことにより、処理の沈みこみを防ぐことができる。
【００８９】
なお、本実施の形態においては、リクエスト管理テーブル１４を参照し、自ノードのＣＣＣ信号として‘Ｒｔｙ’を出力する場合に、併せてスターベーション・レジスタ１９ｃに対する登録を行なうようにしてもよい。すなわち、一つでも‘Ｒｔｙ’が出力される場合は、各ノードがその旨を認識する必要があるので、集計結果を出さずに、そのまま他のノードに対して‘Ｒｔｙ’信号を出力する構成としてもよい。または、自ノードのスターベーション・レジスタ１９ｃに対してはすぐに書き込みを行なうような構成とすることも可能である。
【００９０】
次に、第二の実施の形態について説明する。第一の実施の形態では、自ノードが発行したトランザクションに関しては、リクエスト管理テーブル１４を参照するようにしていたが、スターベーション管理部１９を併用する構成としてもよい。この場合は、リクエスト管理テーブル１４の構成を全くなくし、リクエスト管理テーブル１４で行なう処理をすべてスターベーション管理部１９で統括させる構成としてもよいし、他ノードからのトランザクションを受け取った場合にどのＣＣＣ信号を出力するかを決める場合にのみスターベーション管理部１９を用いる構成としてもよい。
【００９１】
前者の構成では、図９〜１１において、リクエスト管理テーブルへのアドレスの登録、抹消処理は、すべてスターベーション管理部１９で行なわれることとなる。その場合は、バリッドビッド19のほかに、各々のノードに対して、処理中であることを示すペンディングビットを格納する構成とする。受信したＣＣＣ信号が’Ｉｎｖ’であったときは、その他にそのアドレスがあり、そのレジスタのバリッドビッド１９ｃが点灯してない場合に、自ノードのレジスタにそのアドレスを格納し、対応するペンティングビットを立てる。このようにして、現在トランザクションが処理中であることが各ノードにおいて登録される。自ノードが発行したトランザクションが終了した場合は、ペンディングビッドを倒し、レジスタの値を消去する。
【００９２】
また、後者の場合は、自ノードのみ処理中であることを把握しておけばよいので、前者のような構成でなく、第一の実施の形態においてリクエスト管理テーブル１４にアドレスを格納するのに合わせて、スターベーション・レジスタの自ノードのレジスタにそのアドレスを格納し、ペンディングビットを立てる構成とする。
【００９３】
このように、スターベーション・レジスタを処理中のノードとリトライ待機中のノードを登録する構成とした場合の、各ノードにおけるキャッシュ・コヒーレンシ一貫性制御について説明する。本実施の形態では、図９のフェーズ２において、他ノードからのトランザクションを受けると、スターベーション・レジスタを用いて、自ノードのトランザクションが処理中であるか否かを識別する点が異なる。自ノードに対して、他ノードのトランザクションのアドレスと同一アドレスに対して、ペンディングビットがたっている場合は、ＣＣＣ信号として‘Ｒｔｙ’信号を出力する。このような構成により、自ノードが処理中の場合であるのに関わらず、キャッシュメモリが別のキャッシュメモリからのキャッシュ・コヒーレンシ一貫性要求に応答してしまうことを防止することができる。
【００９４】
また、本実施の形態において、前者の構成、すなわち、処理中のリード・トランザクションを全てのノードのスターベーション・レジスタに登録可能な構成においては、図９のフェーズ２において自ノードがトランザクションを発行する場合に、スターベーション・レジスタを参照し、すでに処理中のリード・トランザクションがあることを認識することが可能となる。従って、自ノードがトランザクションを発行する前に参照することで、第二のトランザクションが発行されることを防ぐことができる。その場合は、リトライ待機中のノードに対しては、沈み込みは防止することができないが、相互結合網の不要なトランザクションを削減することが可能となる。
【００９５】
次に、第３の実施の形態について説明する。本実施の形態では、スターベーション・レジスタにおいて、リトライ待機中のノードを複数登録することができるものとする。すなわち、スターベーション管理部１９を、各ノードのエントリに対して、優先順位をつけるための領域を有する構成とする。このようにして、処理されるべきリード・トランザクションを複数個登録するものとする。次に、本実施の形態における処理を説明する。
【００９６】
まず、複数個のノードを登録可能とするために、本実施の形態においては、プロセッサ１１からリクエストが出され、スターベーション・レジスタにリトライ待機中のノードがあったとしても、プロセッサ１１に対してリトライを要求するのではなく、他ノードに対してリード・トランザクションを発行する構成となる。また、本実施の形態では、他ノードからのトランザクションを受け取った場合に、リクエスト管理テーブル１４だけでなく、スターベーション管理部１９が、スターベーション・レジスタも参照するものとする。
【００９７】
例えば、図１０のフェーズ４を例に説明すると、ＮＤ２がキャッシュミスを起こした場合にスターベーション・レジスタを参照すると、ＮＤ１がリトライ待機中であることが判明する。その場合に、リード・トランザクションを発行すると、ＮＤ０は、リクエスト管理テーブル１４とスターベーション・レジスタの自ノードのレジスタを確認し、自ノードが、処理中又はリトライ待機中であるか否かを判断する。ＮＤ０の場合は、処理中でも、リトライ待機中でもないので、ＣＣＣ信号として’Ｉｎｖ’信号を出力する。ＮＤ１は、リクエスト管理テーブル１４を参照すると自ノードが処理中でないことがわかるが、スターベーション・レジスタを参照すると、自ノードがリトライ待機中であることが判明する。この場合に、ＮＤ１は、‘Ｒｔｙ’信号をＣＣＣ信号として出力する。すると、相互結合網の集計結果により、‘Ｒｔｙ’信号が通知され、ＮＤ２についてもリトライ待機中であることを各ノードで判断することが可能である。ＮＤ２がリトライ待機中であることをスターベーション・レジスタに登録する場合に、現状のスターベーション・レジスタに登録されているリトライ待機中のノードを計数し、ＮＤ２は優先順位を格納するビットにその中で最後の優先順位を登録するものとする。このような構成により、複数のリトライ待機中のノードを登録することが可能となる。
【００９８】
次に、リトライ待機中であってノードがリトライを行なう場合の処理について説明する。優先順位をきめて複数個のリトライ待機中のノードを登録可能とする場合は、リトライ待機中のノードの優先順位に従って処理を行なわないと、沈み込みを防止することができない。まず、自ノードのプロセッサ１１からリトライがリクエストされた場合に、スターベーション・レジスタを参照する。本実施の形態のスターベーション・レジスタにおいては、自ノードのリトライ待機中のノードが、各優先順位とともに登録されている。従って、リトライ待機中の他のノードが登録されていたとしても、自ノードの優先順位が最優先となっている場合は、リード・トランザクションを出力する。反対に、自ノードよりも、他のノードの方が高い優先順位の場合は、第１の実施の形態におけるフェーズ４と同様に、プロセッサへリトライの指示をだす。このような構成により、本実施の形態においては、複数のリトライ待機中の他ノード間での、スターベーションを防止することが可能となる。
【００９９】
【発明の効果】
本発明によれば複数のキャッシュメモリが時間的に近接してメインメモリからのデータの読み込みの処理を実行した場合にも、正しいキャッシュ・コヒーレンシ一貫性制御を実現することが可能なマルチプロセッサシステムを得ることができる。
【０１００】
また、本発明によればキャッシュ一貫性を保つために、キャッシュ・コヒーレンシ一貫性制御要求に対する中止と再実行を要求しても、キャッシュ・コヒーレンシ一貫性制御要求の沈み込みを防ぐことが可能なマルチプロセッサシステムを得ることができる。
【０１０１】
また、本発明によればリトライの要求を受けたプロセッサがメモリアクセスの再実行を行なう間、該メモリアクセスのアドレスに対するその他のプロセッサのメモリアクセス要求が相互結合網に発行されることを抑止するので、相互結合網が処理するトランザクション数を削減する効果もある。
【図面の簡単な説明】
【図１】本発明の一実施の形態であるマルチプロセッサシステム全体の構成の一例を示す構成図である。
【図２】本発明の一実施の形態であるマルチプロセッサシステムにおけるノードの構成の一例を詳細に例示した構成図である。
【図３】本発明の一実施の形態であるマルチプロセッサシステムにおける相互結合網Aの構成の一例を詳細に例示した構成図である。
【図４】本発明の一実施の形態であるマルチプロセッサシステムにおける相互結合網Ｂの構成の一例を詳細に例示した構成図である。
【図５】本発明の一実施の形態であるマルチプロセッサシステムにおけるノード内のリクエスト管理テーブル部の一例を例示した構成図である。
【図６】本発明の一実施の形態であるマルチプロセッサシステムにおけるノード内のトランザクション受信部の一例を例示した構成図である。
【図７】本発明の一実施の形態であるマルチプロセッサシステムにおけるノード内のスターベーション管理部の一例を例示した構成図である。
【図８】本発明の一実施の形態であるマルチプロセッサシステムに用いられるトランザクションの構成の一例を示す構成図である。
【図９】本発明の一実施形態におけるメモリリード処理の作用の一例を示すタイミングチャートである（フェーズ１〜３）。
【図１０】本発明の一実施形態におけるメモリリード処理の作用の一例を示すタイミングチャートである（フェーズ４〜５）。
【図１１】本発明の一実施形態におけるメモリリード処理の作用の一例を示すタイミングチャートである（フェーズ６）。
【図１２】従来技術を説明するためのマルチプロセッサシステム全体の構成の一例を示す構成図である。
【図１３】従来技術を説明するためのマルチプロセッサシステムにおけるメモリリード処理の動作を示すタイミングチャートである。
【図１４】従来技術を説明するためのマルチプロセッサシステムにおいて、二つのプロセッサが同一アドレスに対するリード処理を時間的に近接して行なうときの動作を示すタイミングチャートである。
【符号の説明】
１０…ノード（ＮＤ０〜ＮＤｎ）
１１…プロセッサ
１２…キャッシュ・メインメモリ制御部
１３ａ…キャッシュメモリ
１３ｂ…キャッシュタグ
１３ｃ…メインメモリ
１４…リクエスト管理テーブル部
１４ａ…キャッシュ・メインメモリ制御部とリクエスト管理テーブル間のパス
１４ｂ…アドレス登録レジスタ
１５…ＣＣＣ受信部
１５ａ…相互結合網ＢからＣＣＣ受信部へのパス
１５ｂ…ＣＣＣ受信部からキャッシュ・メインメモリ制御部とスターベーション管理部へのパス
１５ｃ…ＣＣＣ受信部からトランザクション受信部へのパス
１６…トランザクション受信部
１６ａ…相互結合網Aからトランザクション受信部へのパス
１６ｂ…トランザクション受信部からキャッシュ・メインメモリ制御部へのパス
１６ｃ…トランザクション受信部からスターベーション管理部へのパス
１６ｄ…キャッシュ・コヒーレンシ一貫性制御を要求するトランザクションを保持するキュー
１６ｅ…キュー（１６ｄ）のリードポインタ
１６ｆ…キュー（１６ｄ）のライトポインタ
１７…ＣＣＣ送信部
１７ａ…ＣＣＣ送信部から相互結合網Ｂへのパス
１７ｂ…キャッシュ・メインメモリ制御部からＣＣＣ送信部へのパス
１８…トランザクション送信部
１８ａ…トランザクション送信部から相互結合網Aへのパス
１８ｂ…キャッシュ・メインメモリ制御部からトランザクション送信部へのパス
１９…スターベーション管理部
１９ａ…スターベーション管理部からキャッシュ・メインメモリ制御部へのパス
１９ｂ…キャッシュ・メインメモリ制御部からスターベーション管理部へのパス、
１９ｃ…スターベーション・レジスタ
１９ｃａ…スターベーション・レジスタのバリッドレジスタ
１９ｃｂ…スターベーション・レジスタのアドレスレジスタ
１９ｄ…スターベーション・レジスタ読み出し制御部
１９ｅ…スターベーション・レジスタ書き込み制御部
２０…相互結合網A（ＸＢ１）
２０ａ…リード・トランザクション
２０ｂ…リターン・トランザクション
２０ｃ…転送トランザクション
２０ｅ…ライト・トランザクション
２１ａ…トランザクション受信キュー
２１ｂ…トランザクション送信キュー
２２ａ…トランザクション受信ポート
２２ｂ…トランザクション送信ポート
３０…相互結合網Ｂ（ＸＢ２）
３１ａ…ＣＣＣ信号受信キュー
３１ｂ…ＣＣＣ信号送信キュー
３２ａ…ＣＣＣ信号受信キューから集計論理部へのパス、
３２ｂ…集計論理部からＣＣＣ信号送信キューへのパス
３３…集計論理部
１００…ノード
１０１…プロセッサ
１０２…キャッシュ・メインメモリ制御部
１０３…キャッシュメモリ
１０４…キャッシュタグ
１０５…メインメモリ
１１１…相互結合網A
１１２…相互結合網Ｂ
【図１】
0003714235.tif 000002
【図２】
0003714235.tif 000003
【図３】
0003714235.tif 000004
【図４】
0003714235.tif 000005
【図５】
0003714235.tif 000006
【図６】
0003714235.tif 000007
【図７】
0003714235.tif 000008
【図８】
0003714235.tif 000009
【図９】
0003714235.tif 000010
【図１０】
0003714235.tif 000011
【図１１】
0003714235.tif 000012
【図１２】
0003714235.tif 000013
【図１３】
0003714235.tif 000014
【図１４】
0003714235.tif 000015