(57)【特許請求の範囲】
【請求項１】
キャッシュを備えたプロセッサとメモリが相互結合網で複数接続されたマルチプロセッサシステムにおけるディレクトリ方式のデータ一貫性維持制御方法において、
キャッシュにおいて、保持しているブロックが複数のプロセッサのキャッシュに保持されている共有状態にあるのか当該プロセッサのキャッシュにのみ存在する非共有状態にあるのかブロック毎に管理し、
メモリにおいて、どのプロセッサがブロックを保持しているか、最新のデータがメモリに存在するかどうかブロック毎に管理し、
プロセッサがキャッシュのあるブロックに対して書き込みを行った際に、当該キャッシュのブロックの状態が非共有状態の場合は当該キャッシュのブロックに書き込みを反映し、当該キャッシュのブロックの状態が共有状態にあり、メモリで管理している情報が他のプロセッサのキャッシュがブロックを保持していることを示している場合、当該キャッシュおよびメモリのブロックに書き込みを反映し、他のプロセッサのキャッシュがブロックを保持していた場合、当該ブロックを無効化し、書き込みが行われたキャッシュのブロックの状態を共有状態のままとし、
当該キャッシュのブロックの状態が共有状態にあり、メモリで管理している情報が他のプロセッサのキャッシュがブロックを保持していないことを示している場合、当該キャッシュおよびメモリのブロックに書き込みを反映し、書き込みが行われたキャッシュのブロックの状態を非共有状態に遷移させることを特徴とするデータ一貫性維持制御方法。
【請求項２】
キャッシュを備えたプロセッサとメモリが相互結合網で複数接続されたマルチプロセッサシステムにおけるディレクトリ方式のデータ一貫性維持制御方法において、
キャッシュにおいて、保持しているブロックが複数のプロセッサのキャッシュに保持されている共有状態にあるのか当該プロセッサのキャッシュにのみ存在する非共有状態にあるのかブロック毎に管理し、
メモリにおいて、どのプロセッサがブロックを保持しているか、最新のデータがメモリに存在するかどうか、更新頻度値、をブロック毎に管理し、
前記更新頻度値は、メモリで管理している情報がある１プロセッサのキャッシュがブロックを保持し最新のデータがメモリに存在することを示している場合にブロックをキャッシュに保持する当該プロセッサから書き込みの反映が行われた回数を記録し、他のプロセッサからアクセスがあった場合は回数を０に戻し、
当該キャッシュのブロックの状態が非共有状態の場合は当該キャッシュのブロックに書き込みを反映し、
当該キャッシュのブロックの状態が共有状態にあり、メモリで管理している情報が他のプロセッサのキャッシュがブロックを保持していることを示している場合は、当該キャッシュおよびメモリのブロックに書き込みを反映し、他のプロセッサのキャッシュがブロックを保持していた場合、当該ブロックを無効化し、書き込みが行われたキャッシュのブロックの状態を共有状態のままとし、
当該キャッシュのブロックの状態が共有状態にあり、メモリで管理している情報が他のプロセッサのキャッシュがブロックを保持していないことを示し、更新頻度値がある一定値より小さい場合は、当該キャッシュおよびメモリのブロックに書き込みを反映し、更新頻度値をインクリメントし、書き込みが行われたキャッシュのブロックの状態を共有状態のままとし、
当該キャッシュのブロックの状態が共有状態にあり、メモリで管理している情報が他のプロセッサのキャッシュがブロックを保持していないことを示し、更新頻度値がある一定値と一致する場合は、当該キャッシュおよびメモリのブロックに書き込みを反映し、書き込みが行われたキャッシュのブロックの状態を非共有状態に遷移させる、ことを特徴とするデータ一貫性維持制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、各プロセッサがキャッシュを備えたマルチプロセッサシステムにおける、データ一貫性維持制御方法に関する。
【０００２】
【従来の技術】
マルチプロセッサシステムでは、システムに複数存在するキャッシュ上に、同一のアドレスのデータが存在し得る。そのため、同一アドレスのデータを保持するキャッシュ間でデータの一貫性を維持するための制御、データの一貫性維持制御が必要である。
【０００３】
このデータ一貫性維持制御は、各プロセッサがあるブロックに対して書き込みを行ったときにはそれを排他的に行うことができ、読み出し時には最新の値が得られる、ということを保証するための制御である。従って、まず、書き込みの対象となっているブロックがどのキャッシュに存在しているかを特定することができなければならない。そして、読み出し時のミスの際に、どこに最新のブロックが存在するかを特定できなければならない。ここで、ブロックとはデータ管理の最小単位であり、大きさは例えば６４バイトになる。
【０００４】
例えば、文献（「Ａ  Ｎｅｗ  Ｓｏｌｕｔｉｏｎ  ｔｏ  ＣｏｈｅｒｅｎｃｙＰｒｏｂｌｅｍｓ  ｉｎ  Ｍｕｌｔｉｃａｃｈｅ  Ｓｙｓｔｅｍｓ」ＬＵＣＩＥＮ  Ｍ．ＣＥＮＳＩＥＲ  ａｎｄ  ＰＡＵＬ  ＦＥＡＵＴＲＩＥＲ，ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，ｐ１１１２−１１１８，Ｄｅｃｅｍｂｅｒ  １９７８）に開示されている方法は、次の３つの特徴を持つ。まず第１の特徴は、キャッシュにおいてブロック単位にそのブロックが共有されているかどうかの情報を保持することにある。また第２の特徴は、メモリにおいてブロック単位にそのブロックを保持しているキャッシュを特定する情報、およびメモリに最新のブロックが存在するかどうかの情報、を保持することにある。また第３の特徴は、プロセッサが共有しているブロックに対して書き込みを行ったときに、他キャッシュのブロックを無効化して共有状態を解消し、当該キャッシュにのみ最新のブロックが存在する状態とすることにある。
【０００５】
以降、この方法の動作を説明する。
【０００６】
図１を参照すると、従来および本発明に係わるマルチプロセッサシステムは、命令を実行しメモリアクセスを行うプロセッサＰＲｉ、各プロセッサＰＲｉに接続されプロセッサＰＲｉがアクセスしたデータを一時的に保持するキャッシュＣＭｉ、データを保持するメモリＭＭｉ、キャッシュＣＭｉおよびメモリＭＭｉを接続する相互結合網１２からなる。図１に示したシステムでは、相互結合網１２は８つのポートを有しており、ポート０にはキャッシュＣＭ１が、ポート１にはキャッシュＣＭ２が、ポート２にはキャッシュＣＭ３が、ポート３にはキャッシュＣＭ４が、ポート４にはメモリＭＭ１が、ポート５にはメモリＭＭ２が、ポート６にはメモリＭＭ３が、ポート７にはメモリＭＭ４が、それぞれ接続されている。
【０００７】
以降、プロセッサＰＲ１がメモリＭＭ２のデータをアクセスした場合を例にとり、そのアクセスによって行われるデータ一貫性維持のための一連の動作を説明する。
【０００８】
プロセッサＰＲ１があるブロックのデータに対してアクセスを行ったが、そのブロックがキャッシュＣＭ１に存在しなかった場合（以降この場合をキャッシュミスと記す）の動作を説明する。この場合、まずキャッシュＣＭ１からメモリＭＭ２に読み出し要求メッセージが発行される。読み出し要求を受けたメモリＭＭ２は、最新のブロックが当該メモリに存在するかどうかを検査し、存在すれば当該ブロックを、キャッシュＣＭ１に送信する。存在しなければ、最新のブロックを保持するキャッシュが唯一存在するので、そのキャッシュ、例えばキャッシュＣＭ３に書き戻し要求メッセージを発行する。書き戻し要求を受けたキャッシュＣＭ３は、メモリＭＭ２に対して当該ブロックの書き戻しを行う。メモリＭＭ２は、キャッシュＣＭ３から書き戻されたブロックをキャッシュＣＭ１に送信する。ブロックを受けたキャッシュＣＭ１は、再度、プロセッサＰＲ１が行ったメモリアクセスを評価し、データ一貫性維持のために必要な処理を行う。
【０００９】
上記の処理の結果、以前ブロックを保持していたキャッシュに加えて、新たにキャッシュＣＭ１も最新のブロックを保持することになる。また、メモリＭＭ２にも最新のブロックが存在する状態となる。
【００１０】
次に、プロセッサＰＲ１があるブロックのデータに対して読み出しを行い、そのブロックがキャッシュＣＭ１に存在した場合（以降この場合をリードヒットと記す）の動作を説明する。この場合、キャッシュＣＭ１はそのブロックのデータをプロセッサＰＲ１に渡すことで、処理は完了する。
【００１１】
次に、プロセッサＰＲ１があるブロックのデータに対して書き込みを行い、そのブロックがキャッシュＣＭ１に存在しかつ共有状態にない場合（以降この場合をライトヒットと記す）の動作を説明する。この場合、キャッシュＣＭ１にプロセッサＰＲ１が行った書き込みをキャッシュＣＭ１が保持するブロックに反映し、書き込みが完了したことをプロセッサＰＲ１に通知することで、処理は完了する。
【００１２】
次に、プロセッサＰＲ１があるブロックのデータに対して書き込みを行い、そのブロックがキャッシュＣＭ１に存在しかつ共有状態にある場合（以降この場合をライトシェアードと記す）の動作を説明する。この場合、キャッシュＣＭ１にプロセッサＰＲ１が行った書き込みを反映し、またメモリＭＭ２に対して書き込み要求メッセージが発行される。書き込み要求を受けたメモリＭＭ２は、例えばキャッシュＣＭ１以外にキャッシュＣＭ３およびキャッシュＣＭ４がブロックを保持していたとすると、キャッシュＣＭ３およびキャッシュＣＭ４に対して無効化要求メッセージを発行する。無効化要求を受けたキャッシュＣＭ３およびキャッシュＣＭ４はそれぞれ当該ブロックを無効化し無効化完了メッセージをメモリＭＭ２に対して送信する。メモリＭＭ２は、キャッシュＣＭ３およびキャッシュＣＭ４の両方から無効化完了メッセージを受け取ると、完了応答メッセージをキャッシュＣＭ１に対して送信する。キャッシュＣＭ１は、完了応答メッセージを受け取ると、プロセッサＰＲ１に対して書き込みが完了したことを通知し、処理を完了する。上記の処理の結果、書き込みを行ったキャッシュにのみが最新のブロックを保持しており、メモリには最新のブロックが存在していない状態となる。
【００１３】
上記の処理の結果、キャッシュＣＭ１にのみ最新のブロックが存在することになり、他のキャッシュＣＭｉおよびメモリＭＭ２には最新のブロックが存在しない状態となる。
【００１４】
以上の、データ一貫性維持のための動作の説明では、例えばメモリＭＭ２が、キャッシュＣＭ１からの読み出し要求を受けキャッシュＣＭ３に対して書き戻し要求を発行し、ブロックが書き戻されるのを待っている状態で、キャッシュＣＭ２から読み出し要求があった場合の動作などが省略されている。
【００１５】
【発明が解決しようとする課題】
第１の問題点は、プロセッサの読み出しによりキャッシュミスが発生した場合に、キャッシュからプロセッサにデータが応答されるまでにかかる時間が長いということである。
【００１６】
例えば、キャッシュＣＭ１とキャッシュＣＭ３にメモリＭＭ２のブロックが存在し共有されている状態で、プロセッサＰＲ１が書き込みを行い、次いでプロセッサＰＲ４が読み出しを行った場合の動作を考える。プロセッサＰＲ１が書き込みを行うことで、キャッシュＣＭ１にのみ最新のブロックが存在する状態となり、メモリＭＭ２にも最新のデータは存在しなくなる。次いでプロセッサＰＲ４が読み出しを行うと、キャッシュＣＭ４にブロックが存在しないのでキャッシュミスとなる。これにより、メモリＭＭ２に対して読み出し要求メッセージが送信されるが、メモリＭＭ２にも最新のデータは存在しないので、最新のデータを保持するキャッシュＣＭ１に対して書き戻しを要求することとなる。メモリＭＭ２はキャッシュＣＭ１からのブロックの書き戻しを受け、その後ブロックをキャッシュＣＭ４に送信する。ブロックを受けたキャッシュＣＭ４は、再度、プロセッサＰＲ４が行った読み出しを評価し、ブロックが存在するのでプロセッサＰＲ４にデータを渡し、処理を完了する。
【００１７】
このように、上記問題の理由は、プロセッサが書き込みを行った後に、メモリに最新のブロックが存在しなくなることにある。
【００１８】
第２の問題点は、データ一貫性維持制御のためにキャッシュおよびメモリ間でやり取りされるメッセージが多いということである。
【００１９】
その理由は、プロセッサが書き込みを行った後に、メモリに最新のブロックが存在しなくなることにある。即ち、あるプロセッサが書き込みを行った後、別のキャッシュにおいてキャッシュミスが発生した場合に、メモリへの読み出し要求メッセージおよびキャッシュへのブロック転送の他に、最新のデータを保持するキャッシュに対する書き戻し要求メッセージおよびそのキャッシュからのブロックの書き戻しが必要となるためである。
【００２０】
本発明の目的は、読み出しによるキャッシュミスが発生した場合のデータ一貫性維持制御に要する時間を短縮した、データ一貫性維持制御方法を提供することにある。
【００２１】
本発明の他の目的は、データ一貫性維持制御によって生成されるメッセージの数の増加を防ぐデータ一貫性一方制御方法を提供することにある。
【００２２】
【課題を解決するための手段】
本発明の第１のデータ一貫性維持制御方法は、プロセッサが共有しているブロックに対して書き込みを行ったときに、当該キャッシュおよびメモリのブロックに対して書き込みを反映し、他キャッシュのブロックに関しては無効化を行い、書き込みが行われたキャッシュのブロックの状態を共有状態のままとする、データ一貫性維持制御をキャッシュおよびメモリにおいて行う手段（図２の２３と図３の４４）を有する。
【００２３】
本発明の第２のデータ一貫性維持制御方法は、プロセッサが共有しているブロックに対して書き込みを行ったときに、当該キャッシュおよびメモリにのみ最新のブロックが存在する状態であり他のキャッシュが最新のブロックを保持していなければ、当該キャッシュおよびメモリのブロックに対して書き込みを反映するが、書き込みが行われたキャッシュのブロックの状態を共有状態から非共有状態に遷移させる、データ一貫性維持制御をキャッシュおよびメモリにおいて行う手段（図２の２３と図３の４４）を有する。
【００２４】
本発明の第３のデータ一貫性維持制御方法は、メモリにおいてブロック単位にカウンタを設け、ブロックが新たにキャッシュに取り込まれたときはカウンタの値を０に初期化し、プロセッサが共有しているブロックに対して書き込みを行ったときはそのブロックのカウンタの値をインクリメントし、またプロセッサが共有しているブロックに対して書き込みを行ったときに、当該キャッシュおよびメモリにのみ最新のブロックが存在する状態であり他のキャッシュが最新のブロックを保持しておらずまたカウンタの値がある値になっていれば、当該キャッシュおよびメモリのブロックに対して書き込みを反映するが、書き込みが行われたキャッシュのブロックの状態を共有状態から非共有状態に遷移させる、データ一貫性維持制御をキャッシュおよびメモリにおいて行う手段（図２の２３と図３の４４）を有する。
【００２５】
本発明の第１のデータ一貫性維持制御方法におけるデータ一貫性維持制御手段は、プロセッサが共有しているブロックに対して書き込みを行ったときに、書き込みが行われたキャッシュおよびメモリに、最新のブロックが存在する状態とする。
【００２６】
本発明の第２のデータ一貫性維持制御方法におけるデータ一貫性維持制御手段は、プロセッサが実際に複数のキャッシュで共有されているブロックに対して連続して書き込みを行い、またその間他キャッシュがアクセスを行わなかった場合に、最初の２回の書き込みはメモリにも反映するが、２回目の書き込み後からブロックの共有状態は解消され、３回目の書き込み以降は当該キャッシュに対してのみ行われる。
【００２７】
本発明の第３のデータ一貫性維持制御方法におけるデータ一貫性維持制御手段は、プロセッサが実際に複数のキャッシュで共有されているブロックに対して連続して書き込みを行い、またその間他のキャッシュがアクセスを行わなかった場合に、一定回数の書き込みはメモリにも反映するが、それ以降の書き込みは当該キャッシュに対してのみ行われる。
【００２８】
【発明の実施の形態】
次に、本発明について図面を用いて説明する。
【００２９】
再び、図１を参照すると、本発明に関わるマルチプロセッサシステムは、命令を実行しメモリアクセスを行うプロセッサＰＲｉ、各プロセッサＰＲｉに接続されプロセッサＰＲｉがアクセスしたデータを一時的に保持するキャッシュＣＭｉ、データを保持するメモリＭＭｉ、キャッシュＣＭｉおよびメモリＭＭｉを接続する相互結合網１２からなる。図１に示したシステムでは、相互結合網１２は８つのポートを有しており、ポート０にはキャッシュＣＭ１が、ポート１にはキャッシュＣＭ２が、ポート２にはキャッシュＣＭ３が、ポート３にはキャッシュＣＭ４が、ポート４にはメモリＭＭ１が、ポート５にはメモリＭＭ２が、ポート６にはメモリＭＭ３が、ポート７にはメモリＭＭ４が、それぞれ接続されている。
【００３０】
ここで、各キャッシュＣＭｉおよびメモリＭＭｉには相互結合網１２に接続されたポート番号に対応して３ビットの装置番号が付けられており、キャッシュＣＭ１は‘０００’、キャッシュＣＭ２は‘００１’、キャッシュＣＭ３は‘０１０’、キャッシュＣＭ４は‘０１１’、メモリＭＭ１は‘１００’、メモリＭＭ２は‘１０１’、メモリＭＭ３は‘１１０’、メモリＭＭ４は‘１１１’となっている。また、各メモリＭＭｉは、アドレスの上位２ビットが自装置番号の下位２ビットと一致する領域を管理している。例えばメモリＭＭ２はアドレスの上位２ビットが‘０１’の領域を管理している。
【００３１】
次に、図２を参照すると、本発明に関わるキャッシュＣＭｉは、タグステート等のブロックに関する情報を保持するタグメモリ２２と、データをブロック単位で保持するキャッシュメモリ２５と、プロセッサＰＲｉからのメモリアクセスを保持、管理するメモリアクセス管理部２１と、相互結合網１２によって配送されたメッセージを受信する第１メッセージ受信部２６と、相互結合網１２へのメッセージの送信を行う第１メッセージ送信部２７と、キャッシュメモリ２５のアクセスを行う第１データ制御部２４と、メモリアクセス管理部２１で保持しているメモリアクセスおよび第１メッセージ受信部２６で保持しているメッセージに関してデータ一貫性維持制御のための処理を行うために、タグメモリ２２に格納されている情報の読み出しおよび書き込みを行う機能と、制御機能として、第１データ制御部２４に対してキャッシュメモリ２５のアクセスを指示する機能と、第１メッセージ送信部２７にメッセージの送信を指示する機能とを有する第１一貫性維持制御部２３とから構成される。
【００３２】
次に、図３を参照すると、本発明に関わるメモリＭＭｉは、ディレクトリステートおよびディレクトリマップ等のブロックに関する情報を保持するディレクトリメモリ４３と、データを保持するメインメモリ４６と、相互結合網１２によって配送されたメッセージを受信する第２メッセージ受信部４１と、相互結合網１２へのメッセージの送信を行う第２メッセージ送信部４２と、メインメモリ４６のアクセスを行う第１データ制御部２４と、第２メッセージ受信部４１で保持しているメッセージに関してデータ一貫性維持制御のための処理を行うために、ディレクトリメモリ４３に格納されている情報の読み出しおよび書き込みを行う機能と、制御機能として、第２データ制御部４５に対してメインメモリ４６のアクセスを指示する機能と、第２メッセージ送信部４２にメッセージの送信を指示する機能とを有する第２一貫性維持制御部４４とから構成される。
【００３３】
次に、第１の実施の形態におけるデータ一貫性維持制御方法では、タグメモリ２２に保持されるタグステートは、キャッシュメモリ２５に格納されているブロックの状態を表すもので、Ｉ，Ｓ，Ｅ，Ｄの４つの状態からなり、それぞれ次のような意味を持つ。Ｉ状態は、最新のブロックが当該キャッシュメモリ２５に存在しないことを表す。Ｓ状態は、最新のブロックが当該キャッシュメモリ２５に存在し、また他のキャッシュメモリ２５にも存在する可能性、即ちブロックが共有されている可能性を示唆する。Ｅ状態は、最新のブロックが当該キャッシュメモリ２５に存在し、メインメモリ４６にも最新のブロックが存在するが、他のキャッシュメモリ２５には存在しないことを表す。Ｄ状態は、最新のブロックが当該キャッシュメモリ２５に存在し、他のキャッシュメモリ２５にもメインメモリ４６にも最新のブロックは存在しないことを表す。また、キャッシュメモリ２５においてタグステートの初期値はＩとなり、キャッシュメモリ２５に最新のブロックが存在しない状態となる。
【００３４】
また、第１の実施の形態におけるデータ一貫性維持制御方法では、ディレクトリメモリ４３に保持されるディレクトリマップは、メインメモリ４６の該当するブロックを保持しているキャッシュＣＭｉを表すもので、例えば文献（「Ａ  Ｎｅｗ  Ｓｏｌｕｔｉｏｎ  ｔｏ  Ｃｏｈｅｒｅｎｃｙ  Ｐｒｏｂｌｅｍｓ  ｉｎＭｕｌｔｉｃａｃｈｅ  Ｓｙｓｔｅｍｓ」ＬＵＣＩＥＮ  Ｍ．ＣＥＮＳＩＥＲａｎｄ  ＰＡＵＬ  ＦＥＡＵＴＲＩＥＲ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，ｐ１１１２−１１１８，Ｄｅｃｅｍｂｅｒ  １９７８）に開示されている、フルマップ方式で構成される。フルマップ方式は、各キャッシュＣＭｉに対応するビットを設け、そのビットによりキャッシュＣＭｉがブロックを保持しているか保持していないかを示すものであり、図１のシステムでは、ディレクトリマップは４ビットで構成される。図４にディレクトリマップの値と、どのキャッシュＣＭｉがブロックを保持しているかの関係を示す。図４において、○は保持していることを示し、×は保持していないことを示す。図より明らかなように、ディレクトリマップの第０ビットが１の場合キャッシュＣＭ１がブロックを保持していることを示し、第１ビットが１の場合キャッシュＣＭ２が、第２ビットが１の場合キャッシュＣＭ３が、第３ビットが１の場合キャッシュＣＭ４がそれぞれブロックを保持していることを示す。また、ディレクトリメモリ４３において、ディレクトリマップの初期値は‘００００’となり、どのキャッシュＣＭｉもブロックを保持していない状態となる。
【００３５】
また、第１の実施の形態におけるデータ一貫性維持制御方法では、ディレクトリメモリ４３に格納されるディレクトリステートは、メインメモリ４６に格納されている該当するブロックの状態を表すもので、Ｃ，Ｍ，ＲＭＰ，ＷＳＰの４つの状態からなり、それぞれ次のような意味を持つ。Ｃ状態は、メインメモリ４６に最新のブロックが存在し、ディレクトリマップで示されるキャッシュＣＭｉがデータを保持している可能性を示唆する。この状態の時、ディレクトリマップは図４に示した１６種全ての値を取り得る。Ｍ状態は、メインメモリ４６に最新のブロックが存在しない可能性を示唆し、ディレクトリマップで示されるただ１つのキャッシュＣＭｉが最新のブロックを保持している可能性を示唆する。この状態の時、ディレクトリマップは‘０００１’，‘００１０’，‘０１００’，‘１０００’の４種の値しか取り得ない。ＲＭＰ状態は、Ｍ状態の時に後述するＲＭメッセージを受け取り、ディレクトリマップで示されたただ１つのキャッシュＣＭｉにＦＲメッセージを発行して、そのキャッシュＣＭｉからのＦＤまたはＡＣＫメッセージが到着するのを待っていることを表す。この状態の時、ディレクトリマップは‘０００１’，‘００１０’，‘０１００’，‘１０００’の４種の値しか取り得ない。ＷＳＰ状態は、Ｃ状態の時に後述するＷＳメッセージを受け取り、ＷＳメッセージを発行したキャッシュＣＭｉを除く、ディレクトリマップで示されたデータを保持している可能性のあるキャッシュＣＭｉ全てに対してＩＶメッセージを発行して、それらキャッシュＣＭｉ全てからのＡＣＫメッセージが到着するのを待っていることを表す。この状態の時、ディレクトリマップは‘００１１’または‘００１０’または‘０００１’の３種類の値のみを取り得る。また、この値は保持するキャッシュＣＭｉを表すものではなく、‘００１１’は３個のＡＣＫの到着を待っていることを表し、‘００１０’は２個のＡＣＫの到着を待っていることを表し、‘０００１’は１個のＡＣＫの到着を待っていることを表す。また、ディレクトリメモリ４３においてディレクトリステートの初期値はＣとなり、メインメモリ４６に最新のブロックが存在する状態となる。
【００３６】
また、第１の実施の形態におけるデータ一貫性維持制御方法では、キャッシュＣＭｉとメモリＭＭｉの間でやり取りされるメッセージには、ＲＭ，ＷＳ，ＷＢ，ＦＲ，ＩＶ，ＦＤ，ＡＣＫ，ＳＤＲ，ＥＤＲ，ＣＲ，ＮＣＲの１１種類のメッセージが存在し、それぞれ次のような意味を持つ。
【００３７】
ＲＭメッセージは、キャッシュミスが発生した場合に、キャッシュＣＭｉからメモリＭＭｉに対して発行される読み出し要求メッセージである。ＷＳメッセージは、ライトシェアードが発生した場合に、キャッシュＣＭｉからメモリＭＭｉに対して発行される書き込み要求メッセージである。このＷＳメッセージには、プロセッサが行った書き込みのデータが付加される。ＷＢメッセージは、置き換え対象となったブロックを書き戻す場合に発せられる書き戻しメッセージである。このＷＢメッセージには、置き換え対象となったブロックが付加される。ＦＲメッセージは、ＲＭメッセージを受信したメモリＭＭｉが、最新のブロックを保持するキャッシュＣＭｉに対して発行する、書き戻し要求メッセージである。ＩＶメッセージは、ＷＳメッセージを受信したメモリＭＭｉが、ブロックを保持するキャッシュＣＭｉに対して発行する、無効化要求メッセージである。ＦＤメッセージは、ＦＲメッセージを受信したキャッシュＣＭｉが、メモリＭＭｉに対して発行する、書き戻しメッセージである。このＦＤメッセージには、キャッシュＣＭｉが保持していた最新のブロックが付加される。ＡＣＫメッセージは、ＦＲまたはＩＶメッセージを受信したキャッシュＣＭｉが、メモリＭＭｉに対して発行する応答メッセージである。ＳＤＲおよびＥＤＲメッセージは、メモリＭＭｉが、ＲＭメッセージを発行したキャッシュＣＭｉに対して、ＲＭメッセージのためのデータ一貫性維持制御のための処理がメモリＭＭｉで完了したことを通知する応答メッセージである。このＳＤＲおよびＥＤＲメッセージには、最新のブロックが付加される。ＣＲメッセージは、メモリＭＭｉが、ＷＳメッセージを発行したキャッシュＣＭｉに対して、ＷＳメッセージのための処理がメモリＭＭｉで完了したことを通知する応答メッセージである。ＮＣＲメッセージは、メモリＭＭｉにおいて、ＲＭまたはＷＳメッセージを処理できなかった場合に、ＲＭまたはＷＳメッセージを発行したキャッシュＣＭｉに対してその旨を通知するメッセージである。
【００３８】
また、メッセージはヘッダ部とデータ部とで構成され、ＲＭ，ＦＲ，ＩＶ，ＡＣＫ，ＣＲ，ＮＣＲの６種類のメッセージはヘッダ部のみで構成される。また、ＷＳメッセージは、ヘッダ部と、プロセッサが行った書き込みのデータからなるデータ部とで構成される。また、ＷＢ，ＦＤ，ＳＤＲ，ＥＤＲの４種類のメッセージは、ヘッダ部とブロック単位のデータからなるデータ部とで構成される。
【００３９】
図５を参照しながら、メッセージヘッダ部の構成を説明する。
【００４０】
メッセージヘッダは、宛先装置番号、メッセージ識別子、アドレス、要求元装置番号の５つのフィールドから構成される。宛先装置番号フィールドは、相互結合網１２のどのポートに接続されたキャッシュＣＭｉまたはメモリＭＭｉに配送するメッセージであるかを示すもので、例えば‘１０１’の場合、ポート５に接続されたメモリＭＭ２宛にメッセージが配送される。メッセージ識別子フィールドは、当該メッセージが１１種類のメッセージの内どのメッセージであるかを示すものである。１１種類のメッセージを識別する。アドレスフィールドは、各メッセージがどのアドレスに対するメッセージであるかを示すものである。要求元装置番号フィールドは、各メッセージがどのプロセッサＰＲｉで行われたメモリアクセスに起源するものかを、そのプロセッサＰＲｉに接続されているキャッシュＣＭｉの装置番号で示すものである。例えば、プロセッサＰＲ１で行われたメモリアクセスを起源とするメッセージであれば、そのメッセージの要求元装置番号は‘０００’となる。
【００４１】
次に、第１の実施の形態におけるデータ一貫性維持制御方法で、プロセッサＰＲ１がメモリＭＭ２のデータをアクセスした場合を例にとり、そのアクセスによって行われるデータ一貫性維持制御のための一連の動作を図を参照しながら説明する。
【００４２】
まず、プロセッサＰＲ１がメモリアクセスを発行すると、メモリアクセス管理部２１はそのメモリアクセスを内部に取り込む。取り込まれるのは、読み出しアクセスか書き込みアクセスかを識別するメモリアクセスコマンド、アクセス対象を示すアドレス、書き込みアクセスの場合はデータ、である。コマンドおよびアドレスは第１一貫性維持制御部２３に供給され、データは第１データ制御部２４に供給されている。
【００４３】
第１一貫性維持制御部２３は、メモリアクセス管理部２１にメモリアクセスが取り込まれたのを検知し、メモリアクセス管理部２１に格納されているメモリアドレスから、対応するブロックのタグステートをタグメモリ２２から読み出し、その値によりどのような処理をするかを判断する。
【００４４】
まず、タグステートが‘Ｉ’であった場合、即ちキャッシュミスの場合の動作を説明する。
【００４５】
この場合に、キャッシュメモリ２５にメモリアクセスのあったアドレスのブロックを取り込むための空きスペースが無かった場合、既にキャッシュメモリ２５に存在する他のブロックと置き換える必要が生じる。置き換えの必要がなかった場合は、第１一貫性維持制御部２３はアドレスから特定されるメモリＭＭｉ（ここではメモリＭＭ２である）に対してＲＭメッセージを送信する処理から開始する。
【００４６】
置き換えが必要であり、置き換えの対象となったブロックのタグステートが‘Ｄ’であった場合、このブロックがシステムで唯一最新のブロックであるので、そのブロックを管理するメモリＭＭｉに対して書き戻しの処理をまず行う必要がある。図６および図７にこの場合のシーケンスフローを示す。図は、置き換え対象となったブロックがメモリＭＭ３で管理されているブロックの場合を示している。
【００４７】
第１一貫性維持制御部２３は、まずＷＢメッセージのヘッダ部を生成し第１メッセージ送信部２７に供給する。この時生成されるメッセージヘッダの宛先装置番号はメモリＭＭ３を表す‘１１０’となり、メッセージ識別子はＷＢを表す識別子に、アドレスは置き換えの対象となったブロックのアドレスに、要求元装置番号は当該キャッシュＣＭ１の装置番号を表す‘０００’になる。また、第１一貫性維持制御部２３は、第１データ制御部２４に対してキャッシュメモリ２５から置き換えの対象となったブロックを読み出すように指示し、読み出されたブロックは第１メッセージ送信部２７にＷＢメッセージのデータ部として供給される。第１メッセージ送信部２７は、第１一貫性維持制御部２３から供給されるヘッダ部と第１データ制御部２４から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第１一貫性維持制御部２３は、タグメモリ２２の書き込みを行い、置き換えの対象となったブロックのタグステートを‘Ｉ’に更新する。
【００４８】
送出されたＷＢメッセージは、相互結合網１２によって配送され、メモリＭＭ３の第２メッセージ受信部４１に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部が第２データ制御部４５に供給されている。
【００４９】
メモリＭＭ３の第２一貫性維持制御部４４は、第２メッセージ受信部４１にＷＢメッセージが取り込まれたのを検出し、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップをディレクトリメモリ４３から読み出し、その値によりどのような処理をするかを判断する。この時、ディレクトリステートが取り得る値は、方法上‘Ｍ’または‘ＲＭＰ’に限定される。
【００５０】
ディレクトリステートがＭであった場合、図６に示すシーケンスとなる。第２一貫性維持制御部４４はディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＣに、ディレクトリマップをどのキャッシュＣＭｉもブロックを保持していないことを表す‘００００’に更新する。また、第２一貫性維持制御部４４は、第２データ制御部４５にＷＢメッセージに付加されていたブロックをメインメモリ４６の対応するブロックへ書き込ませる。
【００５１】
ディレクトリステートがＲＭＰであった場合、図７に示すシーケンスとなる。第２一貫性維持制御部４４は、第２データ制御部４５にＷＢメッセージに付加されていたブロックをメインメモリ４６の対応するブロックへ書き込ませるのみとし、ディレクトリメモリ４３の更新は行わない。
【００５２】
以上が、置き換えが必要であり、置き換えの対象となったブロックのタグステートが‘Ｄ’であった場合のシーケンスである。
【００５３】
次に、置き換えが必要であり、置き換えの対象となったブロックのタグステートが‘Ｄ’以外であった場合、第１一貫性維持制御部２３はタグメモリ２２の書き込みを行い、書き換えの対象となったブロックのタグステートを‘Ｉ’に更新する。
【００５４】
第１一貫性維持制御部２３において、上記置き換えのための処理が完了すると、第１一貫性維持制御部２３はＲＭメッセージのヘッダ部を生成し第１メッセージ送信部２７に供給する。この時生成されるメッセージヘッダの宛先装置番号はメモリＭＭ２を表す‘１０１’となり、メッセージ長はＲＭメッセージの長さに、メッセージ識別子はＲＭを表す識別子に、アドレスはメモリアクセス管理部２１に格納されているアドレスに、要求元装置番号は当該キャッシュＣＭ１の装置番号を表す‘０００’になる。第１メッセージ送信部２７は、第１一貫性維持制御部２３から供給されるヘッダ部をメッセージとして相互結合網１２に送出する（図８，図９，図１０，図１１，図１２に共通のシーケンス）。
【００５５】
送出されたＲＭメッセージは、相互結合網１２によって配送され、メモリＭＭ２の第２メッセージ受信部４１に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給されている。
【００５６】
メモリＭＭ２の第２一貫性維持制御部４４は、第２メッセージ受信部４１にＲＭメッセージが取り込まれたのを検出し、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップをディレクトリメモリ４３から読み出し、その値によりどのような処理をするかを判断する。
【００５７】
ディレクトリステートがＣで、かつディレクトリマップの値がＲＭメッセージを発行したキャッシュＣＭｉ（メッセージに付加されていた要求元装置番号から特定され、この場合はキャッシュＣＭｉとなる）以外にブロックを保持するキャッシュＣＭｉが存在しないことを表す場合（ここでは、ディレクトリマップが‘００００’または‘０００１’の場合である）図８に示すシーケンスとなる。
【００５８】
第２一貫性維持制御部４４は、まずＥＤＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されていうメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＥＤＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。また、第２一貫性維持制御部４４は、第２データ制御部４５に対して、メインメモリ４６から第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスで特定されるブロックの読み出しを指示する。第２データ制御部４５は読み出したブロックをＥＤＲメッセージのデータ部として第２メッセージ送信部４２に供給する。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部と第２データ制御部４５から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＭに、またディレクトリマップを‘０００１’に遷移させる。このディレクトリマップの値は、ＲＭメッセージを発行したキャッシュＣＭ１に対応するビットを‘１’とし、他のビットを‘０’とする操作を行った結果得られる値である。
【００５９】
送出されたＥＤＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部は第１データ制御部２４に供給されている。
【００６０】
キャッシュＣＭ１の第１一貫性維持制御部２３は、第１メッセージ受信部２６にＥＤＲメッセージが取り込まれたのを検出し、第１データ制御部２４に対してキャッシュメモリ２５へのＥＤＲメッセージに付加されていたブロックデータの取り込みを指示する。また、第１一貫性維持制御部２３は、タグメモリ２２の書き込みを行い、対応するブロックのタグステートを‘Ｅ’に更新する。
【００６１】
第１一貫性維持制御部２３はその後、再度メモリアクセス管理部２１に格納されているメモリアクセスを評価し、データ一貫性維持のために必要な処理を行う。
【００６２】
次に、ＲＭメッセージを受け取ったメモリＭＭ２の第２一貫性維持制御部４４が、ディレクトリメモリ４３の対応するブロックのディレクトリステートおよびディレクトリマップを読み出した結果、ディレクトリステートがＣで、かつディレクトリマップの値がＲＭメッセージを発行したキャッシュＣＭｉ（ここではキャッシュＣＭ１である）以外にブロックを保持するキャッシュＣＭｉが存在することを表す場合（ここでは、キャッシュＣＭ１がＲＭメッセージを発行しているので、ディレクトリマップが‘００００’または‘０００１’以外の場合である）、図９に示すシーケンスとなる。
【００６３】
第２一貫性維持制御部４４は、まずＳＤＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＳＤＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。また、第２一貫性維持制御部４４は、第２データ制御部４５に対して、メインメモリ４６から第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスで特定されるブロックの読み出しを指示する。第２データ制御部４５は読み出したブロックをＳＤＲメッセージのデータ部として第２メッセージ送信部４２に供給する。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部と第２データ制御部４５から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＣに、ディレクトリマップの値を‘１１０１’に遷移させる。このディレクトリマップの値は、ＲＭメッセージを受け取る直前のディレクトリマップの値に対して、第２メッセージ受信部４１に格納されている要求元装置番号から特定されるキャッシュＣＭ１に対応するビットを‘１’にする操作を行った結果得られる値である。
【００６４】
送出されたＳＤＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部は第１データ制御部２４に供給されている。
【００６５】
キャッシュＣＭ１の第１一貫性維持制御部２３は、第１メッセージ受信部２６にＳＤＲメッセージが取り込まれたのを検出し、第１データ制御部２４に対してキャッシュメモリ２５へのＳＤＲメッセージに付加されていたブロックデータの取り込みを指示する。また、第１一貫性維持制御部２３は、タグメモリ２２の書き込みを行い、対応するブロックのタグステートを‘Ｓ’に更新する。
【００６６】
第１一貫性維持制御部２３はその後、再度メモリアクセス管理部２１に格納されているメモリアクセスを評価し、データ一貫性維持のために必要な処理を行う。
【００６７】
次に、ＲＭメッセージを受け取ったメモリＭＭ２の第２一貫性維持制御部４４が、ディレクトリメモリ４３の対応するブロックのディレクトリステートおよびディレクトリマップを読み出した結果、ディレクトリステートがＭであった場合、図１０または図１１に示すシーケンスとなる。この場合、ディレクトリマップにより、最新のブロックを保持するキャッシュＣＭｉが唯一定まる。図１０および図１１に示した例では、ディレクトリマップの値は‘０１００’であるので、キャッシュＣＭ３が唯一最新のデータを保持していることが確認できる。
【００６８】
第２一貫性維持制御部４４は、まずＦＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、最新のブロックを保持するキャッシュＣＭ３を表す‘０１０’となり、メッセージ識別子はＦＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして、相互結合網１２に送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＲＭＰに更新するが、ディレクトリマップはそのままとする。
【００６９】
送出されたＦＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ３の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給されている。
【００７０】
キャッシュＣＭ３の第１一貫性維持制御部２３は、第１メッセージ受信部２６にＦＲメッセージが取り込まれたのを検出し、第１メッセージ受信部２６に格納されているヘッダ部のアドレスから、対応するブロックのタグステートをタグメモリ２２から読み出し、その値によりどのような処理をするかを判断する。この時、タグステートが取り得る値は、‘Ｉ’または‘Ｅ’または‘Ｄ’であり、‘Ｓ’であることはあり得ない。
【００７１】
タグステートが‘Ｅ’または‘Ｄ’で最新のブロックが存在した場合、図１０に示すシーケンスとなる。
【００７２】
第１一貫性維持制御部２３は、まずＦＤメッセージのヘッダ部を生成し第１メッセージ送信部２７に供給する。この時生成されるメッセージヘッダの宛先装置番号は第１メッセージ受信部２６に格納されているヘッダ部のアドレスから特定されるメモリＭＭｉを表す装置番号となり（ここではアドレスからメモリＭＭ２が特定され宛先装置番号は‘１０１’となる）、メッセージ識別子はＦＤを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）になる。また、第１一貫性維持制御部２３は、第１データ制御部２４に対してキャッシュメモリ２５から第１メッセージ受信部２６に格納されているアドレスから特定されるブロックを読み出すように指示し、読み出されたブロックは第１メッセージ送信部２７にＦＤメッセージのデータ部として供給される。第１メッセージ送信部２７は、第１一貫性維持制御部２３から供給されるヘッダ部と第１データ制御部２４から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第１一貫性維持制御部２３は、タグメモリ２２の書き込みを行い、対応するブロックのタグステートを‘Ｓ’に更新する。
【００７３】
送出されたＦＤメッセージは相互結合網１２によって配送され、メモリＭＭ２の第２メッセージ受信部４１に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部は第２データ制御部４５に供給される。
【００７４】
メモリＭＭ２の第２一貫性維持制御部４４は、第２メッセージ受信部４１にＦＤメッセージが取り込まれたのを検出し、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップをディレクトリメモリ４３から読み出す。この時、ディレクトリステートが取り得る値は、方法上‘ＲＭＰ’に限定される。
【００７５】
第２一貫性維持制御部４４は、まずＳＤＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＳＤＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。また、第２一貫性維持制御部４４は、第２データ制御部４５に対して、ＦＤメッセージに付加されていたブロックをメインメモリ４６の対応するブロックへ書き込ませる。第２データ制御部４５はメインメモリ４６への書き込みを行うと同時に、ＦＤメッセージに付加されていたブロックをＳＤＲメッセージのデータ部として第２メッセージ送信部４２にも供給する。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部と第２データ制御部４５から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＣに、ディレクトリマップの値を‘１１０１’に遷移させる。このディレクトリマップの値は、ＦＤメッセージを受け取る直前のディレクトリマップの値に対して、第２メッセージ受信部４１に格納されている要求元装置番号から特定されるキャッシュＣＭ１に対応するビットを‘１’にする操作を行った結果得られる値である。
【００７６】
送出されたＳＤＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第１一貫性維持制御部２３に供給され、データ部は第１データ制御部２４に供給される。
【００７７】
キャッシュＣＭ１の第１一貫性維持制御部２３が、第１メッセージ受信部２６にＳＤＲメッセージが取り込まれたのを検出した場合の動作は、図９に示すシーケンスでキャッシュＣＭ１がＳＤＲメッセージを受け取った場合と同一である。
【００７８】
次に、ＦＲメッセージを受け取ったキャッシュＣＭ３の第１一貫性維持制御部２３が、タグメモリ２２の対応するブロックのタグステートを読み出した結果、タグステートが‘Ｉ’であった場合、図１１に示すシーケンスとなる。
【００７９】
第１一貫性維持制御部２３は、まずＡＣＫメッセージのヘッダ部を生成し第１メッセージ送信部２７に供給する。この時生成されるメッセージヘッダの宛先装置番号は第１メッセージ受信部２６に格納されているヘッダ部のアドレスから特定されるメモリＭＭｉを表す装置番号となり（ここではアドレスからメモリＭＭ２が特定される宛先装置番号は‘１０１’となる）、メッセージ識別子はＡＣＫを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）になる。第１メッセージ送信部２７は、第１一貫性維持制御部２３から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。
【００８０】
送出されたＡＣＫメッセージは相互結合網１２によって配送され、メモリＭＭ２の第２メッセージ受信部４１に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給される。
【００８１】
メモリＭＭ２の第２一貫性維持制御部４４は、第２メッセージ受信部４１にＡＣＫメッセージが取り込まれたのを検出し、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップをディレクトリメモリ４３から読み出す。この時、ディレクトリステートが取り得る値は、方法上‘ＷＳＰ’と‘ＲＭＰ’に限定されるが、ここでは図１１に示すシーケンスでディレクトリステートが‘ＲＭＰ’の場合を記す。
【００８２】
第２一貫性維持制御部４４は、まずＥＤＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＥＤＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。また、第２一貫性維持制御部４４は、第２データ制御部４５に対して、メインメモリ４６から第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスで特定されるブロックの読み出しを指示する。第２データ制御部４５は読み出したブロックをＥＤＲメッセージのデータ部として第２メッセージ送信部４２に供給する。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部と第２データ制御部４５から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＭに、またディレクトリマップを‘０００１’に遷移させる。このディレクトリマップの値は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号で特定されるキャッシュＣＭｉ（ここではキャッシュＣＭ１である）に対応するビットを‘１’とし、他のビットを‘０’とする操作を行った結果得られる値である。
【００８３】
送出されたＥＤＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部は第１データ制御部２４に供給されている。
【００８４】
キャッシュＣＭ１の第１一貫性維持制御部２３が、第１メッセージ受信部２６にＥＤＲメッセージが取り込まれたのを検出した場合の動作は、図８に示すシーケンスでキャッシュＣＭ１がＥＤＲメッセージを受け取った場合と同一である。
【００８５】
次に、ＲＭメッセージを受け取ったメモリＭＭ２の第２一貫性維持制御部４４が、ディレクトリメモリ４３の対応するブロックのディレクトリステートおよびディレクトリマップを読み出した結果、ディレクトリステートが‘ＲＭＰ’または‘ＷＳＰ’であった場合、図１２に示すシーケンスとなる。
【００８６】
第２一貫性維持制御部４４は、まずＮＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＮＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に供給されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。
【００８７】
送出されたＮＣＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第１一貫性維持制御部２３に供給される。
【００８８】
キャッシュＣＭ１の第１一貫性維持制御部２３は、第１メッセージ受信部２６にＮＣＲメッセージが取り込まれたのを検出し、再度メモリアクセス管理部２１に格納されているメモリアクセスを評価し、データ一貫性維持のために必要な処理を行う。
【００８９】
以上が、キャッシュミスの場合のデータ一貫性維持のための動作である。
【００９０】
次に、メモリアクセス管理部２１にメモリアクセスが取り込まれたのを検知し、メモリアクセス管理部２１に格納されているアクセスから、対応するブロックのタグステートをタグメモリ２２から読み出した結果、メモリアクセス管理部２１に取り込まれたメモリアクセスが読み出しで、タグステートが‘Ｓ’または‘Ｅ’または‘Ｄ’であった場合（リードヒットの場合）の動作を説明する。
【００９１】
第１一貫性維持制御部２３は、第１データ制御部２４に対してキャッシュメモリ２５からメモリアクセス管理部２１に格納されているアドレスで特定されるデータを読み出せる。読み出されたデータはメモリアクセス管理部２１に供給され、取り込まれる。メモリアクセス管理部２１に取り込まれたデータはプロセッサＰＲ１に供給される。また、第１一貫性維持制御部２３はプロセッサＰＲ１に対してメモリアクセスの完了応答を行い、プロセッサＰＲ１にメモリアクセス管理部２１が供給するデータの取り込みを行わせ、読み出しアクセスを完了させる。
【００９２】
次に、メモリアクセス管理部２１にメモリアクセスが取り込まれたのを検知し、メモリアクセス管理部２１に格納されているアドレスから、対応するブロックのタグステートをタグメモリ２２から読み出した結果、メモリアクセス管理部２１に取り込まれたメモリアクセスが書き込みで、タグステートが‘Ｅ’または‘Ｄ’であった場合の動作を説明する（ライトヒットの場合）。
【００９３】
第１一貫性維持制御部２３は、第１データ制御部２３に、キャッシュメモリ２５のメモリアクセス管理部２１が出力するアドレスから特定されるデータを、メモリアクセス管理部２１が供給するデータに書き換えさせる。また、第１一貫性維持制御部２３は、タグメモリ２２の書き込みを行い、タグステートを‘Ｄ’に更新する。また、第１一貫性維持制御部２３はプロセッサＰＲ１に対してメモリアクセスの完了応答を行い、書き込みアクセスを完了させる。
【００９４】
次に、メモリアクセス管理部２１にメモリアクセスが取り込まれたのを検知し、メモリアクセス管理部２１に格納されているアドレスから、対応するブロックのタグステートをタグメモリ２２から読み出した結果、メモリアドレス管理部２１に取り込まれたメモリアクセスが書き込みで、タグステートが‘Ｓ’であった場合の動作を説明する（ライトシェアードの場合）。
【００９５】
第１一貫性維持制御部２３は、まずＷＳメッセージのヘッダ部を生成し第１メッセージ送信部２７に供給する。この時生成されるメッセージヘッダの宛先装置番号はメモリＭＭ２を表す‘１０１’となり、メッセージ識別子はＷＳを表す識別子に、アドレスはメモリアクセス管理部２１に格納されているアドレスに、要求元装置番号は当該キャッシュＣＭ１の装置番号を表す‘０００’になる。また、第１一貫性維持制御部２３は、第１データ制御部２４に、キャッシュメモリ２５のメモリアクセス管理部２１が出力するアドレスから特定されるデータを、メモリアクセス管理部２１が供給するデータに書き換えさせる。この時、第１データ制御部２４はメモリアクセス管理部２１が供給するデータをキャッシュメモリ２５に書き込むと同時に、第１メッセージ送信部２７にも供給する。第１メッセージ送信部２７は、第１一貫性維持制御部２３から供給されるヘッダ部と第１データ制御部２４から供給されるデータ部を合わせて、相互結合網１２にメッセージを送出する。
【００９６】
送出されたＷＳメッセージは相互結合網１２によって配送され、メモリＭＭ２の第２メッセージ受信部４１に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部は第２データ制御部４５に供給される。
【００９７】
メモリＭＭ２の第２一貫性維持制御部４４は、第２メッセージ受信部４１にＷＳメッセージが取り込まれたのを検出し、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップをディレクトリメモリ４３から読み出す。この時、ディレクトリステートが取り得る値は、方法上‘Ｃ’または‘ＷＳＰ’に限定される。また、ディレクトリステートがＣの場合は、ＷＳメッセージを発行したキャッシュＣＭ１に対応するディレクトリマップのビットは必ず‘１’である。
【００９８】
ディレクトリステートが‘Ｃ’で、かつディレクトリマップの値がＷＳメッセージを発行したキャッシュＣＭｉ以外にブロックを保持するキャッシュＣＭｉが存在しないことを表す場合（ここでは、キャッシュＣＭ１がＷＳメッセージを発行しているので、ディレクトリマップが‘０００１’の場合である）図１３に示すシーケンスとなる。
【００９９】
第２一貫性維持制御部４４は、まずＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。また、第２一貫性維持制御部４４は、第２データ制御部４５に、メインメモリ４６の第２メッセージ受信部４１が出力するアドレスから特定されるデータを、第２メッセージ受信部４１が供給するデータに書き換えさせる。
【０１００】
送出されたＣＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第１一貫性維持制御部２３に供給される。
【０１０１】
キャッシュＣＭ１の第１一貫性維持制御部２３は、第１メッセージ受信部２６にＣＲメッセージが取り込まれたのを検出し、プロセッサＰＲ１に対してメモリアクセスの完了応答を行い、書き込みアクセスを完了させる。
【０１０２】
次に、ＷＳメッセージを受け取ったメモリＭＭ２の第２一貫性維持制御部４４が、ディレクトリメモリ４３の対応するブロックのディレクトリステートおよびディレクトリマップを読み出した結果、ディレクトリステートがＣであり、かつディレクトリマップの値がＷＳメッセージを発行したキャッシュＣＭｉ以外にブロックを保持するキャッシュのＣＭｉが存在することを表す場合（ここでは、キャッシュＣＭ１がＷＳメッセージを発行しているので、ディレクトリマップの値が‘０００１’以外の場合である）図１４に示すシーケンスとなる。以降では、また図１４に示した例では、ＷＳメッセージを受け取ったときのディレクトリマップの値が例えば‘１１０１’であった場合を説明する。
【０１０３】
第２一貫性維持制御部４４はまず、キャッシュＣＭ１が最新のブロックを保持しておりかつＷＳメッセージを発行したキャッシュＣＭｉではないかどうかを検査する。この時、キャッシュＣＭ１は、第２メッセージ受信部４１に格納された要求元装置番号よりＷＳメッセージを発行したキャッシュＣＭｉであるのでこの場合は何も行わない。
【０１０４】
次に、第２一貫性維持制御部４４は、キャッシュＣＭ２が最新のブロックを保持しておりかつＷＳメッセージを発行したキャッシュＣＭｉではないかどうかを検査する。この時、ディレクトリマップの値‘１１０１’より、キャッシュＣＭ２は最新のデータを保持していないのでこの場合も何も行わない。
【０１０５】
次に、第２一貫性維持制御部４４は、キャッシュＣＭ３が最新のブロックを保持しておりかつＷＳメッセージを発行したキャッシュＣＭｉではないかどうかを検査する。この時、キャッシュＣＭ３は最新のブロックを保持しておりまたＷＳメッセージを発行したキャッシュＣＭｉではないので、次のような処理をする。第２一貫性維持制御部４４は、ＩＶメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、キャッシュＣＭ３を表す‘０１０’となり、メッセージ識別子はＩＶを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして、相互結合網１２に送出する。
【０１０６】
次に、第２一貫性維持制御部４４は、キャッシュＣＭ４が最新のブロックを保持しておりかつＷＳメッセージを発行したキャッシュＣＭｉではないかどうかを検査する。この時、キャッシュＣＭ４は最新のブロックを保持しておりまたＷＳメッセージを発行したキャッシュＣＭｉではないので、前記したキャッシュＣＭ３の場合と同じくＩＶメッセージのヘッダ部を生成する。ただし、宛先装置番号はキャッシュＣＭ４を表す‘０１１’となる。
【０１０７】
最後に、第２一貫性維持制御部４４は、第２データ制御部４５に、メインメモリ４６の第２メッセージ受信部４１が出力するアドレスから特定されるデータを、第２メッセージ受信部４１が供給するデータに書き換えさせる。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートを‘ＷＳＰ’に、またディレクトリマップを‘００１０’に遷移させる。このディレクトリマップの値は、送信したＩＶメッセージの数を表すものである。
【０１０８】
送出された２つのＩＶメッセージは相互結合網１２によって配送され、それぞれキャッシュＣＭ３およびキャッシュＣＭ４の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部は第１データ制御部２４に供給されている。
【０１０９】
キャッシュＣＭ３の第１一貫性維持制御部２３は、第１メッセージ受信部２６にＩＶメッセージが取り込まれたのを検出し、第１メッセージ受信部２６に格納されているヘッダ部のアドレスから、対応するブロックのタグステートをタグメモリ２２から読み出し、その値によりどのような処理をするかを判断する。この時、タグステートが取り得る値は、‘Ｉ’または‘Ｓ’に限定される。
【０１１０】
タグステートが‘Ｉ’であった場合、第１一貫性維持制御部２３は、まずＡＣＫメッセージのヘッダ部を生成し第１メッセージ送信部２７に供給する。この時生成されるメッセージヘッダの宛先装置番号は第１メッセージ受信部２６に格納されているヘッダ部のアドレスから特定されるメモリＭＭｉを表す装置番号となり（ここではアドレスからメモリＭＭ２が特定され宛先装置番号は‘１０１’となる）、メッセージ識別子はＡＣＫを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）になる。第１メッセージ送信部２７は、第１一貫性維持制御部２３から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。
【０１１１】
また、タグステートが‘Ｓ’であった場合、第１一貫性維持制御部２３は、まずＡＣＫメッセージのヘッダ部を生成し第１メッセージ送信部２７に供給する。この時生成されるメッセージヘッダの宛先装置番号は第１メッセージ受信部２６に格納されているヘッダ部のアドレスから特定されるメモリＭＭｉを表す装置番号となり（ここではアドレスからメモリＭＭ２が特定され宛先装置番号は‘１０１’となる）、メッセージ識別子はＡＣＫを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）になる。第１メッセージ送信部２７は、第１一貫性維持制御部２３から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。また、第１一貫性維持制御部２３は、タグメモリ２２の書き込みを行い、対応するブロックのタグステートを‘Ｉ’に更新する。
【０１１２】
送出されたＡＣＫメッセージは相互結合網１２によって配送され、メモリＭＭ２の第２メッセージ受信部４１に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給される。
【０１１３】
メモリＭＭ２の第２一貫性維持制御部４４は、第２メッセージ受信部４１にＡＣＫメッセージが取り込まれたのを検出し、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップをディレクトリメモリ４３から読み出す。この時、ディレクトリステートが取り得る値は、方法上‘ＷＳＰ’と‘ＲＭＰ’に限定されるが、ここでは図１４に示すシーケンスでディレクトリステートが‘ＷＳＰ’の場合を記す。また、この時、ディレクトリマップの値が‘０００１’であるかそうでないかにより異なる処理をする。
【０１１４】
ディレクトリステートが‘ＷＳＰ’で、ディレクトリマップが‘０００１’でない場合（ここでは‘００１０’とする。この場合は図１４に示すシーケンスでキャッシュＣＭ３が発行したＡＣＫメッセージを受け取った場合である）、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートはそのまま‘ＷＳＰ’とするが、ディレクトリマップは、全ディレクトリマップの値をデクリメントした値（ここでは‘０００１’である）に更新する。
【０１１５】
次にディレクトリステートが‘ＷＳＰ’で、ディレクトリマップの値が‘０００１’であった場合（図１４に示すシーケンスでキャッシュＣＭ４が発行したＡＣＫメッセージを受け取った場合である）、第２一貫性維持制御部４４はまず、ＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＭに、またディレクトリマップを‘０００１’に遷移させる。このディレクトリマップの値は、第２メッセージ受信部４１に格納されたヘッダ部の要求元装置番号から特定されるキャッシュＣＭｉ（ここではキャッシュＣＭ１である）に対応するビットを‘１’とし、他のビットを‘０’とする操作を行った結果得られる値である。
【０１１６】
送出されたＣＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部は第１データ制御部２４に供給されている。
【０１１７】
キャッシュＣＭ１の第１一貫性維持制御部２３が、第１メッセージ受信部２６にＣＲメッセージが取り込まれたのを検出した場合の動作は、図１３に示すシーケンスでキャッシュＣＭ１がＣＲメッセージを受け取った場合と同一である。
【０１１８】
次に、ＷＳメッセージを受け取ったメモリＭＭ２の第２一貫性維持制御部４４が、ディレクトリメモリ４３の対応するブロックのディレクトリステートおよびディレクトリマップを読み出した結果、ディレクトリステートが‘ＷＳＰ’であった場合、図１５に示すシーケンスとなる。この時、同ブロックにおいて既に他のキャッシュＣＭｉからのＷＳメッセージを受付け処理している最中であり、そのＷＳメッセージを処理したときに、メモリＭＭ２はキャッシュＣＭ１に対してＩＶメッセージを送信している。これにより、キャッシュＣＭ１においてタグメモリ２２に格納されている当該ブロックのタグステートは‘Ｓ’から‘Ｉ’に更新されている。
【０１１９】
第２一貫性維持制御部４４は、まずＮＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＮＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。
【０１２０】
送出されたＮＣＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第１一貫性維持制御部２３に供給される。
【０１２１】
キャッシュＣＭ１の第１一貫性維持制御部２３が、第１メッセージ受信部２６にＮＣＲメッセージが取り込まれたのを検出した場合の動作は、図１２に示すシーケンスでキャッシュＣＭ１がＮＣＲメッセージを受け取った場合と同一である。
【０１２２】
次に、本発明の第１の実施の形態の効果について説明する。
【０１２３】
例えば、キャッシュＣＭ１とキャッシュＣＭ３にメモリＭＭ２のブロックが存在し共有されている状態で、プロセッサＰＲ１が書き込みを行い、次いでプロセッサＰＲ４が読み出しを行った場合の動作を考える。プロセッサＰＲ１が行った書き込みは、キャッシュＣＭ１およびメモリＭＭ２に反映されるので、キャッシュＣＭ１およびメモリＭＭ２に最新のデータが存在する状態となる。
【０１２４】
そのため、次いでプロセッサＰＲ４が読み出しを行った場合、メモリＭＭ２に対して読み出し要求メッセージが送信されるが、メモリＭＭ２に最新のデータが存在するため、メモリＭＭ２はすぐさまキャッシュＣＭ１に対して最新のブロックを付加したメッセージを送信することができる。このため、メモリＭＭ２において最新のブロックを唯一保持するキャッシュＣＭｉに対して書き戻しを要求してその応答を受け取る処理がなくなり、プロセッサＰＲ４の読み出しに対してデータを応答するまでの時間を短縮することができる。また、書き戻しを要求する必要がなくなることから、データ一貫性維持のためにキャッシュおよびメモリ間でやり取りされるメッセージ数を少なくすることができる。
【０１２５】
次に第２の実施の形態におけるデータ一貫性維持制御方法では、第１の実施の形態におけるデータ一貫性維持制御方法と同様に、タグメモリ２２に格納されるタグステートはＩ，Ｓ，Ｅ，Ｄの４状態からなる。また、ディレクトリメモリ４３に格納されるディレクトリマップも４ビットからなるフルマップ方式で構成される。またディレクトリステートもＣ，Ｍ，ＲＭＰ，ＷＳＰの４状態からなる。
【０１２６】
第２の実施の形態におけるデータ一貫性維持制御方法で、キャッシュＣＭｉとメモリＭＭｉの間でやり取りされるメッセージには、第１の実施の形態におけるデータ一貫性維持制御方法での、ＲＭ，ＷＳ，ＷＢ，ＦＲ，ＩＶ，ＦＤ，ＡＣＫ，ＳＤＲ，ＥＤＲ，ＣＲ，ＮＣＲの１１種類のメッセージに、新たにＥＣＲメッセージが加えられ、１２種類のメッセージが存在する。ＥＣＲメッセージは、ＣＲメッセージ同様、メモリＭＭｉがＷＳメッセージを発行したキャッシュＣＭｉに対して、ＷＳメッセージのための処理がメモリＭＭｉで完了したことを通知する応答メッセージである。
【０１２７】
次に、第２の実施の形態におけるデータ一貫性維持制御方法で、プロセッサＰＲ１がメモリＭＭ２のデータをアクセスした場合を例にとり、そのアクセスによって行われるデータ一貫性維持のための一連の動作を、第１の実施の形態におけるデータ一貫性維持制御方法と異なる点のみを示す。
【０１２８】
第２の実施の形態におけるデータ一貫性維持制御方法で、第１の実施の形態におけるデータ一貫性維持制御方法と動作を異にするのは、ＷＳメッセージを受け取ったメモリＭＭ２の第２一貫性維持制御部４４が、ディレクトリメモリ４３の対応するブロックのディレクトリステートおよびディレクトリマップを読み出した結果、ディレクトリステートがＣであり、かつディレクトリマップの値がＷＳメッセージを発行したキャッシュＣＭｉ以外にブロックを保持するキャッシュＣＭｉが存在しないことを表す場合（ここでは、キャッシュＣＭ１がＷＳメッセージを発行しているので、ディレクトリマップの値が‘０００１’の場合である）である。即ち、第１の実施の形態におけるデータ一貫性維持制御方法では、図１３に示すシーケンスとなる場合である。
【０１２９】
この場合、第２の実施の形態におけるデータ一貫性維持制御方法では図１６に示すシーケンスをとる。
【０１３０】
第２一貫性維持制御部４４は、まずＥＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＥＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。また、第２一貫性維持制御部４４は、第２データ制御部４５に、メインメモリ４６の第２メッセージ受信部４１が出力するアドレスから特定されるデータを、第２メッセージ受信部４１が供給するデータに書き換えさせる。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＭに、またディレクトリマップを‘０００１’に遷移させる。このディレクトリマップの値は、ＲＭメッセージを発行したキャッシュＣＭ１に対応するビットを‘１’とし、他のビットを‘０’とする操作を行った結果得られる値である。
【０１３１】
送出されたＥＣＲメッセージは相互結合網１２によって配送され、キャッシュＣＭ１の第１メッセージ受信部２６に取り込まれる。取り込まれたメッセージのヘッダ部は第２一貫性維持制御部４４に供給され、データ部は第１データ制御部２４に供給されている。
【０１３２】
キャッシュＣＭ１の第１一貫性維持制御部２３は、タグメモリ２２の書き込みを行い、対応するブロックのタグステートを‘Ｓ’から‘Ｅ’に更新する。また、第１一貫性維持制御部２３は、プロセッサＰＲ１に対してメモリアクセスの完了応答を行い、書き込みアクセスを完了させる。
【０１３３】
次に、本発明の第２の実施の形態の効果について説明する。
【０１３４】
例えば、キャッシュＣＭ１のブロックの状態が共有状態でありキャッシュＣＭ１とメモリＭＭ２にのみ最新のブロックが存在する状態で、プロセッサＰＲ１が連続して書き込みを行い、その間他のプロセッサＰＲｉがアクセスを行わなかった場合を考える。この場合、第１の実施の形態におけるデータ一貫性維持制御方法では、書き込みの度に書き込み要求メッセージがキャッシュＣＭ１からメモリＭＭ２に発行され、この場合のデータ一貫性維持制御のためのメッセージ数が増加するという問題がある。
【０１３５】
第２の実施の形態におけるデータ一貫性維持制御方法では、上記のような場合に、最初の２回の書き込みに関してはキャッシュＣＭ１からメモリＭＭ２に対して書き込み要求メッセージが発行されるが、続く３回目からの書き込みに関してはデータ一貫性維持制御のためのメッセージは発行されず、この場合のメッセージの増加を防ぐことができる。
【０１３６】
次に第３の実施の形態におけるデータ一貫性維持制御方法では、第２の実施の形態におけるデータ一貫性維持制御方法と同様に、タグメモリ２２に格納されるタグステートはＩ，Ｓ，Ｅ，Ｄの４状態からなる。また、ディレクトリメモリ４３に格納されるディレクトリマップも４ビットからなるフルマップ方式で構成される。またディレクトリステートもＣ，Ｍ，ＲＭＰ，ＷＳＰの４状態からなる。
【０１３７】
第３の実施の形態におけるデータ一貫性維持制御方法では、ディレクトリステートおよびディレクトリマップに加えて、更新頻度値がブロックに関する情報としてディレクトリメモリ４３に保持される。更新頻度値は、ある１つのキャッシュＣＭｉとメモリＭＭｉが最新のブロックを保持している状態で、メモリＭＭｉが、他のキャッシュＣＭｉからのＲＭメッセージを受け取るまでに、何回最新のブロックを保持するキャッシュＣＭｉからＷＳメッセージを受け取ったかをカウントした値である。
【０１３８】
また、第３の実施の形態におけるデータ一貫性維持制御方法では、新たにパラメータとして更新頻度上限値が定義される。
【０１３９】
また、第３の実施の形態におけるデータ一貫性維持制御方法で、キャッシュＣＭｉとメモリＭＭｉの間でやり取りされるメッセージには、第２の実施の形態におけるデータ一貫性維持制御方法でのメッセージ同様、ＲＭ，ＷＳ，ＷＢ，ＦＲ，ＩＶ，ＦＤ，ＡＣＫ，ＳＤＲ，ＥＤＲ，ＣＲ，ＮＣＲ，ＥＣＲの１２種類のメッセージが存在する。
【０１４０】
次に、第３の実施の形態におけるデータ一貫性維持制御方法で、プロセッサＰＲ１がメモリＭＭ２のデータをアクセスした場合を例にとり、そのアクセスによって行われるデータ一貫性維持のための一連の動作を説明する。
【０１４１】
第３の実施の形態におけるデータ一貫性維持制御方法でのキャッシュＣＭｉの動作は、第２の実施の形態におけるデータ一貫性維持制御方法でのキャッシュＣＭｉの動作と同一であるので、ここではその説明を省略する。以降第３の実施の形態におけるデータ一貫性維持制御方法でのメモリＭＭｉの動作を、ＲＭ，ＷＳ，ＷＢ，ＦＤ，ＡＣＫの５種類のメッセージを受け取った場合の順に説明する。
【０１４２】
メモリＭＭ２の第２一貫性維持制御部４４は、第２メッセージ受信部４１にＲＭメッセージが取り込まれたのを検出すると、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップおよび更新頻度値をディレクトリメモリ４３から読み出し、その値によりどのような処理をするかを判断する。
【０１４３】
ディレクトリステートがＣで、かつディレクトリマップの値がＲＭメッセージを発行したキャッシュＣＭｉ（メッセージに付加されていた要求元装置番号から特定され、この場合はキャッシュＣＭ１となる）以外にブロックを保持するキャッシュＣＭｉが存在しないことを表す場合（ここでは、ディレクトリマップが‘００００’または‘０００１’の場合である）、更新頻度値の値に関わらず、図１７に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ１からのＲＭメッセージを受け取った場合の処理をする。
【０１４４】
第２一貫性維持制御部４４は、まずＥＤＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＥＤＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。また、第２一貫性維持制御部４４は、第２データ制御部４５に対して、メインメモリ４６から第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスで特定されるブロックの読み出しを指示する。第２データ制御部４５は読み出したブロックをＥＤＲメッセージのデータ部として第２メッセージ送信部４２に供給する。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部と第２データ制御部４５から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＭに、またディレクトリマップを‘０００１’に、更新頻度値を‘０’に更新する。このディレクトリマップの値は、ＲＭメッセージを発行したキャッシュＣＭ１に対応するビットを‘１’とし、他のビットを‘０’とする操作を行った結果得られる値である。
【０１４５】
ディレクトリステートがＣで、かつディレクトリマップの値がＲＭメッセージを発行したキャッシュＣＭｉ（ここではキャッシュＣＭ１である）以外にブロックを保持するキャッシュＣＭｉが存在することを表す場合（ここでは、キャッシュＣＭ１がＲＭメッセージを発行しているので、ディレクトリマップが‘００００’または‘０００１’以外の場合である）、更新頻度値の値に関わらず、図１８に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ１からのＲＭメッセージを受け取った場合の処理をする。
【０１４６】
第２一貫性維持制御部４４は、まずＳＤＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＳＤＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。また、第２一貫性維持制御部４４は、第２データ制御部４５に対して、メインメモリ４６から第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスで特定されるブロックの読み出しを指示する。第２データ制御部４５は読み出したブロックをＳＤＲメッセージのデータ部として第２メッセージ送信部４２に供給する。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部と第２データ制御部４５から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＣに、ディレクトリマップの値を‘１１０１’に、更新頻度値を‘０’に更新する。このディレクトリマップの値は、ＲＭメッセージを受け取る直前のディレクトリマップの値に対して、第２メッセージ受信部４１に格納されている要求元装置番号から特定されるキャッシュＣＭ１に対応するビットを‘１’にする操作を行った結果得られる値である。
【０１４７】
ディレクトリステートがＭであった場合、更新頻度値の値に関わらず、図１９および図２０に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ１からのＲＭメッセージを受け取った場合の処理をする。この場合、ディレクトリマップより、最新のブロックを保持するキャッシュＣＭｉが唯一定まる。図１９および図２０に示した例では、ディレクトリマップの値は‘０１００’であるので、キャッシュＣＭ３が唯一最新のデータを保持していることが確認できる。
【０１４８】
第２一貫性維持制御部４４は、まずＦＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、最新のブロックを保持するキャッシュＣＭ３を表す‘０１０’となり、メッセージ識別子はＦＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして、相互結合網１２に送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＲＭＰに、更新頻度値を‘０’に更新するが、ディレクトリマップはそのままとする。
【０１４９】
ディレクトリステートが‘ＲＭＰ’または‘ＷＳＰ’であった場合、ディレクトリマップおよび更新頻度値の値に関わらず、図２１に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ１からのＲＭメッセージを受け取った場合の処理をする。
【０１５０】
第２一貫性維持制御部４４は、まずＮＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＮＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。
【０１５１】
次に、メモリＭＭ２の第２一貫性維持制御部４４が、第２メッセージ受信部４１にＷＳメッセージが取り込まれたのを検出した場合、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップおよび更新頻度値をディレクトリメモリ４３から読み出し、その値によりどのような処理をするかを判断する。
【０１５２】
ディレクトリステートが‘Ｃ’で、かつディレクトリマップの値がＷＳメッセージを発行したキャッシュＣＭｉ以外にブロックを保持するキャッシュＣＭｉが存在しないことを表し（ここでは、キャッシュＣＭ１がＷＳメッセージを発行しているので、ディレクトリマップが‘０００１’の場合である）、更新頻度値が更新頻度上限値と一致しなかった場合、図２２に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ１からのＷＳメッセージを受け取った場合の処理をする。
【０１５３】
第２一貫性維持制御部４４は、まずＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）。メッセージ識別子はＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。また、第２一貫性維持制御部４４は、第２データ制御部４５に、メインメモリ４６の第２メッセージ受信部４１が出力するアドレスから特定されるデータを、第２メッセージ受信部４１が供給するデータに書き換えさせる。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートおよびディレクトリマップはそのままとし、更新頻度値は１足した値に更新する。図２２に示すシーケンスでは、更新頻度値は‘０’から‘１’に更新されている。
【０１５４】
ディレクトリステートが‘Ｃ’で、かつディレクトリマップの値がＷＳメッセージを発行したキャッシュＣＭｉ以外にブロックを保持するキャッシュＣＭｉが存在しないことを表し（ここでは、キャッシュＣＭ１がＷＳメッセージを発行しているので、ディレクトリマップが‘０００１’の場合である）、更新頻度値が更新頻度上限値と一致した場合、図２３に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ１からのＷＳメッセージを受け取った場合の処理をする。図２３に示したシーケンスは、更新頻度上限値を‘２’に設定した場合である。
【０１５５】
第２一貫性維持制御部４４は、まずＥＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＥＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。また、第２一貫性維持制御部４４は、第２データ制御部４５に、メインメモリ４６の第２メッセージ受信部４１が出力するアドレスから特定されるデータを、第２メッセージ受信部４１が供給するデータに書き換えさせる。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＭに、またディレクトリマップを‘０００１’に、更新頻度値を‘０’に更新する。このディレクトリマップの値は、ＲＭメッセージを発行したキャッシュＣＭ１に対応するビットを‘１’とし、他のビットを‘０’とする操作を行った結果得られる値である。
【０１５６】
ディレクトリステートがＣであり、かつディレクトリマップの値がＷＳメッセージを発行したキャッシュＣＭｉ以外にブロックを保持するキャッシュＣＭｉが存在することを表す場合（ここでは、キャッシュＣＭ１がＷＳメッセージを発行しているので、ディレクトリマップの値が‘０００１’以外の場合である）、更新頻度値に関わらず、図２４に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ１からのＷＳメッセージを受け取った場合の処理をする。以降では、また図２４に示した例では、ＷＳメッセージを受け取ったときのディレクトリマップの値が例えば‘１１０１’であった場合を説明する。
【０１５７】
第２一貫性維持制御部４４はまず、キャッシュＣＭ１が最新のブロックを保持しておりかつＷＳメッセージを発行したキャッシュＣＭｉではないかどうかを検査する。この時、キャッシュＣＭ１は、第２メッセージ受信部４１に格納された要求元装置番号よりＷＳメッセージを発行したキャッシュＣＭｉであるのでこの場合は何も行わない。
【０１５８】
次に、第２一貫性維持制御部４４は、キャッシュＣＭ２が最新のブロックを保持しておりかつＷＳメッセージを発行したキャッシュＣＭｉではないかどうかを検査する。この時、ディレクトリマップの値‘１１０１’より、キャッシュＣＭ２は最新のデータを保持していないのでこの場合も何も行わない。
【０１５９】
次に、第２一貫性維持制御部４４は、キャッシュＣＭ３が最新のブロックを保持しておりかつＷＳメッセージを発行したキャッシュＣＭｉではないかどうかを検査する。この時、キャッシュＣＭ３は最新のブロックを保持しておりまたＷＳメッセージを発行したキャッシュＣＭｉではないので、次のような処理をする。第２一貫性維持制御部４４は、ＩＶメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、キャッシュＣＭ３を表す‘０１０’となり、メッセージ識別子はＩＶを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして、相互結合網１２に送出する。
【０１６０】
次に、第２一貫性維持制御部４４は、キャッシュＣＭ４が最新のブロックを保持しておりかつＷＳメッセージを発行したキャッシュＣＭｉではないかどうかを検査する。この時、キャッシュＣＭ４は最新のブロックを保持しておりまたＷＳメッセージを発行したキャッシュＣＭｉではないので、前記したキャッシュＣＭ３の場合と同じくＩＶメッセージのヘッダ部を生成する。ただし、宛先装置番号はキャッシュＣＭ４を表す‘０１１’となる。
【０１６１】
最後に、第２一貫性維持制御部４４は、第２データ制御部４５に、メインメモリ４６の第２メッセージ受信部４１が出力するアドレスから特定されるデータを、第２メッセージ受信部４１が供給するデータに書き換えさせる。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートを‘ＷＳＰ’に、またディレクトリマップを‘００１０’に、更新頻度値を‘０’に更新する。このディレクトリマップの値は、送信したＩＶメッセージの数を表すものである。
【０１６２】
ディレクトリステートが‘ＷＳＰ’であった場合、ディレクトリマップおよび更新頻度値に関わらず、図２５に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ１からのＷＳメッセージを受け取った場合の処理をする。
【０１６３】
第２一貫性維持制御部４４は、まずＮＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＮＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。
【０１６４】
次に、メモリＭＭ２の第２一貫性維持制御部４４が、第２メッセージ受信部４１にＷＢメッセージが取り込まれたのを検出した場合、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップおよび更新頻度値をディレクトリメモリ４３から読み出し、その値によりどのような処理をするかを判断する。この時、ディレクトリステートが取り得る値は、方法上‘Ｍ’または‘ＲＭＰ’に限定される。
【０１６５】
ディレクトリステートが‘Ｍ’の場合、更新頻度値の値に関わらず、図２６に示すシーケンスで、メモリＭＭ３がキャッシュＣＭ１からのＷＢメッセージを受け取った場合の処理をする。第２一貫性維持制御部４４はディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＣに、ディレクトリマップをどのキャッシュＣＭｉもブロックを保持していないことを表す‘００００’に、更新頻度値を‘０’に更新する。また、第２一貫性維持制御部４４は、第２データ制御部４５にＷＢメッセージに付加されていたブロックをメインメモリ４６の対応するブロックへ書き込ませる。
【０１６６】
ディレクトリステートがＲＭＰであった場合、ディレクトリマップおよび更新頻度値の値に関わらず、図２７に示すシーケンスで、メモリＭＭ３がキャッシュＣＭ１からのＷＢメッセージを受け取った場合の処理をする。第２一貫性維持制御部４４は、第２データ制御部４５にＷＢメッセージに付加されていたブロックをメインメモリ４６の対応するブロックへ書き込ませるのみとし、ディレクトリメモリ４３の更新は行わない。
【０１６７】
次に、メモリＭＭ２の第２一貫性維持制御部４４が、第２メッセージ受信部４１にＦＤメッセージが取り込まれたのを検出した場合、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップおよび更新頻度値をディレクトリメモリ４３から読み出し、更新頻度値に関わらず、図１９に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ３からのＦＤメッセージを受け取った場合の処理をする。この時、ディレクトリステートが取り得る値は、方法上‘ＲＭＰ’に限定される。
【０１６８】
第２一貫性維持制御部４４は、まずＳＤＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＳＤＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。また、第２一貫性維持制御部４４は、第２データ制御部４５に対して、ＦＤメッセージに付加されていたブロックをメインメモリ４６の対応するブロックへ書き込ませる。第２データ制御部４５はメインメモリ４６への書き込みを行うと同時に、ＦＤメッセージに付加されていたブロックをＳＤＲメッセージのデータ部として第２メッセージ送信部４２にも供給する。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部と第２データ制御部４５から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＣに、ディレクトリマップの値を‘１１０１’に、更新頻度値を‘０’に更新する。このディレクトリマップの値は、ＦＤメッセージを受け取る直前のディレクトリマップの値に対して、第２メッセージ受信部４１に格納されている要求元装置番号から特定されるキャッシュＣＭ１に対応するビットを‘１’にする操作を行った結果得られる値である。
【０１６９】
次に、メモリＭＭ２の第２一貫性維持制御部４４が、第２メッセージ受信部４１にＡＣＫメッセージが取り込まれたのを検出した場合、第２メッセージ受信部４１に格納されたヘッダ部のアドレスから、対応するブロックのディレクトリステートおよびディレクトリマップおよび更新頻度値をディレクトリメモリ４３から読み出し、その値によりどのような処理をするかを判断する。この時、ディレクトリステートが取り得る値は、方法上‘ＷＳＰ’または‘ＲＭＰ’に限定される。
【０１７０】
ディレクトリステートが‘ＲＭＰ’の場合、更新頻度値に関わらず、図２０に示すシーケンスで、メモリＭＭ２がキャッシュＣＭ３からのＡＣＫメッセージを受け取った場合の処理をする。
【０１７１】
第２一貫性維持制御部４４は、まずＥＤＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＥＤＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。また、第２一貫性維持制御部４４は、第２データ制御部４５に対して、メインメモリ４６から第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスで特定されるブロックの読み出しを指示する。第２データ制御部４５は読み出したブロックをＥＤＲメッセージのデータ部として第２メッセージ送信部４２に供給する。第２メッセージ送信部４２は、第２一貫性維持制御部４４から供給されるヘッダ部と第２データ制御部４５から供給されるデータ部をあわせて、相互結合網１２にメッセージを送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＭに、またディレクトリマップを‘０００１’に、更新頻度値を‘０’に更新する。このディレクトリマップの値は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号で特定されるキャッシュＣＭｉ（ここではキャッシュＣＭ１である）に対応するビットを‘１’とし、他のビットを‘０’とする操作を行った結果得られる値である。
【０１７２】
ディレクトリステートが‘ＷＳＰ’で、ディレクトリマップが‘０００１’でない場合、更新頻度値の値に関わらず、図２４に示すシーケンスでメモリＭＭ２がキャッシュＣＭ３が発行したＡＣＫメッセージを受け取った場合の処理をする。
【０１７３】
第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートはそのままの‘ＷＳＰ’とするが、ディレクトリマップは前ディレクトリマップの値をデクリメントした値（ここでは‘０００１’である）に、更新頻度値は‘０’に更新する。
【０１７４】
次にディレクトリステートが‘ＷＳＰ’で、ディレクトリマップの値が‘０００１’であった場合、更新頻度値の値に関わらず、図２４に示すシーケンスでメモリＭＭ２がキャッシュＣＭ４が発行したＡＣＫメッセージを受け取った場合の処理をする。
【０１７５】
第２一貫性維持制御部４４はまず、ＣＲメッセージのヘッダ部を生成し第２メッセージ送信部４２に供給する。この時生成されるメッセージヘッダの宛先装置番号は、第２メッセージ受信部４１に格納されているメッセージヘッダ部の要求元装置番号となり（この場合は‘０００’である）、メッセージ識別子はＣＲを表す識別子に、アドレスおよび要求元装置番号は第２メッセージ受信部４１に格納されているメッセージヘッダ部のアドレスおよび要求元装置番号（ここでは‘０００’である）となる。第２メッセージ送信部４２、第２一貫性維持制御部４４から供給されるヘッダ部をメッセージとして相互結合網１２に送出する。また、第２一貫性維持制御部４４は、ディレクトリメモリ４３の書き込みを行い、ディレクトリステートをＭに、またディレクトリマップを‘０００１’に、更新頻度値は‘０’に更新する。このディレクトリマップの値は、第２メッセージ受信部１に格納されたヘッダ部の要求元装置番号から特定されるキャッシュＣＭｉ（ここではキャッシュＣＭ１である）に対応するビットを‘１’とし、他のビットを‘０’とする操作を行った結果得られる値である。
【０１７６】
次に、本発明の第３の実施の形態の効果について説明する。
【０１７７】
例えば、キャッシュＣＭ１のブロックの状態が共有状態でありキャッシュＣＭ１とメモリＭＭ２にのみ最新のブロックが存在する状態で、プロセッサＰＲ１が連続して書き込みを行い、その間他のプロセッサＰＲｉがアクセスを行わなかった場合を考える。この場合、第１の実施の形態におけるデータ一貫性維持制御方法では、書き込みの度に書き込み要求メッセージがキャッシュＣＭ１からメモリＭＭ２に発行される。そのため、この場合のデータ一貫性維持制御のためのメッセージ数が増加するという問題がある。また、第２の実施の形態におけるデータ一貫性維持制御方式では、最初の２回の書き込みはメモリにも反映されるが、３回目以降の書き込みはメモリに反映されない。そのため実質上２回目の書き込み以降はメモリＭＭ２に最新のブロックが存在しない状態となる。そのため、その後に他のプロセッサＰＲｉがアクセスを行った場合に、メモリＭＭ２に最新のブロックが存在しないので、この場合、キャッシュミスが発生してからプロセッサにデータが応答されるまでにかかる時間が長くなる。
【０１７８】
第３の実施の形態におけるデータ一貫性維持制御方法では、パラメータである更新頻度上限値をＮに設定した場合、最初のＮ＋１回の書き込みはメモリＭＭ２にも反映される。そのためＮ＋１回の書き込みが行われるまで、最新のブロックがメモリＭＭ２に存在する状態となる。そのため、その間に他のプロセッサＰＲｉがアクセスを行った場合、最新のブロックがメモリＭＭ２に存在するので、キャッシュミスが発生してからプロセッサにデータが応答されるまでにかかる時間を短縮できる。また、その間アクセスがなかった場合、Ｎ＋２回目からは書き込みはメモリＭＭ２に反映されない。そのため、この場合のメッセージの増加を防ぐことができる。
【０１７９】
【発明の効果】
第１の効果は、プロセッサの読み出しによりキャッシュミスが発生した場合に、キャッシュからプロセッサにデータが応答されるまでにかかる時間を短縮できることにある。
【０１８０】
その理由は、プロセッサが共有しているブロックに対して書き込みを行ったときに、メモリにも書き込みを反映し最新のブロックが存在する状態としているためである。
【０１８１】
第２の効果は、プロセッサの読み出しによりキャッシュミスが発生した場合に生成されるデータ一貫性維持制御のためのメッセージを削減できることにある。
【０１８２】
その理由は、プロセッサが共有しているブロックに対して書き込みを行ったときに、メモリにも書き込みを反映し最新のブロックが存在する状態としているためである。
【０１８３】
第３の効果は、プロセッサの書き込みにより発生するメッセージの数の増加を抑えることができることにある。
【０１８４】
その理由は、プロセッサが実際に複数のキャッシュで共有されているブロックに対して連続して書き込みを行い、またその間他のキャッシュがアクセスを行わなかった場合に、書き込みをメモリに反映するのを途中で打ち切るためである。
【０１８５】
第４の効果は、第１および第２の効果を強くするか、第３の効果を強くするかを調整できることにある。
【０１８６】
その理由は、プロセッサが実際に複数のキャッシュで共有されているブロックに対して連続して書き込みを行い、またその間他キャッシュがアクセスを行わなかった場合に、書き込みをメモリに反映するのを何回で打ち切るかパラメータで設定できるためである。
【図面の簡単な説明】
【図１】従来および本発明に関わるマルチプロセッサシステムの構成説明図である。
【図２】本発明に関わるキャッシュの構成説明図である。
【図３】本発明に関わるメモリの構成説明図である。
【図４】ディレクトリマップの値と保持しているキャッシュの関係を表す図。
【図５】第１の実施の形態におけるデータ一貫性維持制御方法のメッセージヘッダの構成を説明する図。
【図６】第１の実施の形態におけるデータ一貫性維持制御方法でキャッシュミスの場合に置き換えの対象となったブロックをメモリに書き戻す場合のシーケンスフローである。
【図７】第１の実施の形態におけるデータ一貫性維持制御方法でキャッシュミスの場合に置き換えの対象となったブロックをメモリに書き戻す場合のシーケンスフローである。
【図８】第１の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図９】第１の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１０】第１の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１１】第１の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１２】第１の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１３】第１の実施の形態におけるライトシェアードの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１４】第１の実施の形態におけるライトシェアードの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１５】第１の実施の形態におけるライトシェアードの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１６】第２の実施の形態におけるデータ一貫性維持制御方法の動作を説明する図。
【図１７】第３の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１８】第３の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図１９】第３の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図２０】第３の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図２１】第３の実施の形態におけるキャッシュミスの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図２２】第３の実施の形態におけるライトシェアードの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図２３】第３の実施の形態におけるライトシェアードの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図２４】第３の実施の形態におけるライトシェアードの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図２５】第３の実施の形態におけるライトシェアードの場合にキャッシュとメモリの間でやり取りされるメッセージのシーケンスフローである。
【図２６】第３の実施の形態におけるデータ一貫性維持方法でキャッシュミスの場合に置き換えの対象となったブロックをメモリに書き戻す場合のシーケンスフローである。
【図２７】第３の実施の形態におけるデータ一貫性維持方法でキャッシュミスの場合に置き換えの対象となったブロックをメモリに書き戻す場合のシーケンスフローである。
【符号の説明】
ＰＲｉ    プロセッサ
ＣＭｉ    キャッシュ
ＭＭｉ    メモリ
１２    相互結合網
２１    メモリアクセス管理部
２２    タグメモリ
２３    第１一貫性維持制御部
２４    第１データ制御部
２５    キャッシュメモリ
２６    第１メッセージ受信部
２７    第１メッセージ送信部
４１    第２メッセージ受信部
４２    第２メッセージ送信部
４３    ディレクトリメモリ
４４    第２一貫性維持制御部
４５    第２データ制御部
４６    メインメモリ
【図１】
0003678620.tif 000002
【図２】
0003678620.tif 000003
【図３】
0003678620.tif 000004
【図４】
0003678620.tif 000005
【図５】
0003678620.tif 000006
【図６】
0003678620.tif 000007
【図７】
0003678620.tif 000008
【図８】
0003678620.tif 000009
【図９】
0003678620.tif 000010
【図１０】
0003678620.tif 000011
【図１１】
0003678620.tif 000012
【図１２】
0003678620.tif 000013
【図１３】
0003678620.tif 000014
【図１４】
0003678620.tif 000015
【図１５】
0003678620.tif 000016
【図１６】
0003678620.tif 000017
【図１７】
0003678620.tif 000018
【図１８】
0003678620.tif 000019
【図１９】
0003678620.tif 000020
【図２０】
0003678620.tif 000021
【図２１】
0003678620.tif 000022
【図２２】
0003678620.tif 000023
【図２３】
0003678620.tif 000024
【図２４】
0003678620.tif 000025
【図２５】
0003678620.tif 000026
【図２６】
0003678620.tif 000027
【図２７】
0003678620.tif 000028