[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP3097941B2 - キャッシュメモリ制御装置 - Google Patents

キャッシュメモリ制御装置

Info

Publication number
JP3097941B2
JP3097941B2 JP05215299A JP21529993A JP3097941B2 JP 3097941 B2 JP3097941 B2 JP 3097941B2 JP 05215299 A JP05215299 A JP 05215299A JP 21529993 A JP21529993 A JP 21529993A JP 3097941 B2 JP3097941 B2 JP 3097941B2
Authority
JP
Japan
Prior art keywords
cache memory
processor
data
processor element
state
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP05215299A
Other languages
English (en)
Other versions
JPH0749809A (ja
Inventor
正俊 佐藤
浩一 武田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Oki Electric Industry Co Ltd
Original Assignee
Oki Electric Industry Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Oki Electric Industry Co Ltd filed Critical Oki Electric Industry Co Ltd
Priority to JP05215299A priority Critical patent/JP3097941B2/ja
Publication of JPH0749809A publication Critical patent/JPH0749809A/ja
Application granted granted Critical
Publication of JP3097941B2 publication Critical patent/JP3097941B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Landscapes

  • Memory System Of A Hierarchy Structure (AREA)

Description

【発明の詳細な説明】
【0001】
【産業上の利用分野】本発明はマルチプロセッサシステ
ムにおけるキャッシュメモリ制御装置に関し、特にその
キャッシュメモリのデータの無矛盾化方式に関する。
【0002】
【従来の技術】複数のプロセッサと、これらプロセッサ
が共有するメインメモリ(主記憶装置)とを共有バスを
介して接続したマルチプロセッサシステムでは、各プロ
セッサのアクセスが全て共有バスに集中することを避け
るため、各プロセッサはそれぞれキャッシュメモリを備
えているのが一般的である。一方、このようなマルチプ
ロセッサシステムでは、各プロセッサがそれぞれ個別に
キャッシュメモリを持つことから、同一のデータのコピ
ーが複数のキャッシュメモリに存在することになり、従
って、これらのデータの統一性を保つ必要がある。
【0003】そこで、マルチプロセッサシステムでは、
各プロセッサの有するキャッシュメモリのデータに変更
が生じた場合、メインメモリだけでなく、他のキャッシ
ュメモリにもそのデータ変更を知らせて、システム内の
データの統一性を保つようにしており、この制御の取り
決めをキャッシュメモリの無矛盾化(コヒーレンシ)プ
ロトコルといい、種々のプロトコルが提案されている。
そして、これらのプロトコルでは、その無矛盾化を行う
ために次のような構成をとっている。
【0004】即ち、各プロセッサがある操作を行う場合
は、その操作が終了するまで共有バスを専有し、かつ、
共有バス上にその操作に対応した信号を放送する。一
方、他のプロセッサは共有バスを監視することにより、
対応するブロックをキャッシュメモリに持っている場合
は、その信号に従ってブロックの状態を変更するといっ
た処理により無矛盾化を保証するものである。
【0005】例えば、このような無矛盾化のプロトコル
としてイリノイプロトコルにおけるプロセッサ・リード
・ミスの場合を以下に説明する。 (a)プロセッサがリード動作を行い、キャッシュミス
を起こすと、プロセッサはリードミス信号を有意にし、
共有バスにデータを要求する。 (b1)データが他のキャッシュメモリから送られてく
ると、データを「Shared Clean」の状態で
登録する(通常、メインメモリのデータよりも別のキャ
ッシュメモリからのデータの方が早くかつ優先的に届く
ようになっている)。 (b2)他のキャッシュメモリにデータが無い場合はメ
インメモリからデータが送られ、この場合はデータを
「Private Clean」の状態で登録する。
【0006】このように、従来の無矛盾化プロトコルで
は、(a)と(b1)または(b2)との二つの操作
を、一つの不可分の操作、即ち、(a)の操作が開始さ
れてから(b1)または(b2)の操作が終了するまで
を一つの同期単位とし、この間はバスの専有状態を解除
せずに行っていた。
【0007】
【発明が解決しようとする課題】しかしながら、上記従
来の無矛盾化方式における「いくつかの操作群をバス上
の不可分の操作として扱うこと」の制限は、マルチプロ
セッサが小規模なものではさほど問題は生じないもの
の、大規模なシステムやバスを汎用的なネットワーク結
合網に置き換えた場合は、大きな問題となる。例えば、
大規模なマルチプロセッサシステムを考えた場合、その
バスを流れる信号の伝搬遅延は無視できないものとな
る。また、汎用的なネットワーク結合網を考えた場合も
同様である。
【0008】即ち、このような大規模なシステムに従来
と同様の同期単位を設定することを考えた場合、キャッ
シュメモリの無矛盾化を保証するためには、伝搬遅延時
間を考慮し、そのシステムにおける最大遅延時間を同期
単位としなければならない。その結果、システムの規模
が大きくなればなるほど一つのプロセッサの操作による
ネットワークの専有時間が長くなってシステムの性能が
低下してしまうことから、このような構成は、到底採用
できるものではなかった。
【0009】一方、このような問題に対処するため、各
プロセッサがバスからの信号の遅れを考慮せず、それぞ
れが独自に同期単位を設定することが考えられる。即
ち、バスの専有を、各プロセッサの操作単位とする方法
である。しかしながら、このような方法を用いた場合、
これまでのキャッシュメモリの無矛盾化方式では、以下
のような問題が発生する。即ち、これまでのキャッシュ
メモリの無矛盾化方式では、各キャッシュメモリの状態
遷移の事象を、システムとしてのグローバルクロックに
より、事象発生と同時に放送していた。ところが、上記
のような同期単位を設定した場合、このような事象発生
の放送は遅れを伴い、しかも発生源からの距離により、
通知の逆転を伴って伝えられる場合が発生する。従っ
て、このような通知の逆転といったことから、キャッシ
ュメモリの無矛盾化を保証することができないといった
問題が発生する。
【0010】このような問題を、上述したイリノイプロ
トコルによるプロセッサ・リード・ミスを例にとって説
明する。先ず、従来では上述したように、(a)の操作
と(b1)または(b2)の操作を一つの不可分の操作
で行っていた。これに対し、操作を(a)、(b1)、
(b2)のそれぞれに分割し、各操作を独自に行うこと
を考える。
【0011】図2に、これを説明するためのマルチプロ
セッサシステムの要部を示す。尚、この図2において
は、煩雑さを避けるため、プロセッサ等の図示を省略し
ている。図において、1、2はキャッシュメモリを示し
ており、これらキャッシュメモリ1、2とメインメモリ
3とがバス4を介して接続されているとする。また、操
作がキャッシュメモリ1/メインメモリ3間を伝わる時
間をn、キャッシュメモリ2/メインメモリ3間を伝わ
る時間をmとし、n>mの関係がある。
【0012】このような構成において、キャッシュメモ
リ1がダーティの時、キャッシュメモリ2に対してプロ
セッサ・リード・ミスが生じ、キャッシュメモリ1のブ
ロックを読む場合を考える。そして、この時点では、キ
ャッシュメモリ1に正しいデータがあり、メインメモリ
3には古い正しくないデータがあるとする(キャッシュ
メモリ1でライトヒットが繰り返され、データが更新さ
れている)。
【0013】以下に、事象の流れを示す。 キャッシュメモリ2で、ブロックXに対して、プロセ
ッサ・リード・ミスが生じる。 上記と同時刻にキャッシュメモリ1で、ブロックX
に対して、スワップアウト(メインメモリ3へのデータ
の書き戻し)が生じる。 m時間後、キャッシュメモリ2はメインメモリ3より
データ(古い/正しくない)を受け取る。即ち、n>m
の関係により、この時点ではキャッシュメモリ1からの
データはメインメモリ3に届いていない。 n時間後、メインメモリ3は、キャッシュメモリ1か
らのデータ(正しい)を受け取る。 n+m時間後、キャッシュメモリ1はキャッシュメモ
リ2からのデータ要求を受けるがブロックXはスワップ
アウトのため既にない。尚、この場合、本来ならば、キ
ャッシュメモリ1がキャッシュメモリ2のデータ要求を
処理する。 従って、キャッシュメモリ2は正しいデータを受け取
ることができない。
【0014】上記のような操作において、従来の方式で
は、プロセッサ・リード・ミスまたはスワップアウトの
いずれか一方の事象がバス権を取り、プロセッサ・リー
ド・ミスがバス権を取った場合はスワップアウトが待た
され、キャッシュメモリ1からの正しいデータがキャッ
シュメモリ2に転送される。また、スワップアウトがバ
ス権を取った場合は、プロセッサ・リード・ミスが待た
され、スワップアウトがメインメモリ3に対して行われ
た後、メインメモリ3から正しいデータがキャッシュメ
モリ2に転送される。これに対して、上記のように操作
群を分割したものでは、別のキャッシュメモリからのデ
ータが早くかつ優先的に届くとは限らず、古いデータを
受け取ってしまい、キャッシュメモリの無矛盾化を保証
することができないといった問題点を有していた。
【0015】本発明は、上記従来の問題点を解決するた
めになされたもので、大規模なマルチプロセッサシステ
ムであっても性能の低下がなく、かつキャッシュメモリ
の無矛盾化を保証することのできるキャッシュメモリ制
御装置を提供することを目的とする。
【0016】
【課題を解決するための手段】本発明のキャッシュメモ
リ制御装置は、それぞれがプロセッサとキャッシュメモ
リとを備えたプロセッサエレメントを放送機能を有する
ネットワークに接続してなるマルチプロセッサシステム
のキャッシュメモリ制御装置において、前記それぞれの
プロセッサエレメントは、各プロセッサエレメントの信
号送出時のみ前記ネットワークを専有する同期単位制御
部と、前記プロセッサエレメントが前記ネットワークを
専有する権利を解放後、当該プロセッサエレメントから
の要求に対する応答が受信されるのに必要な最大時間だ
け前記ネットワークからの入力信号を監視する監視部
と、前記監視部による監視時間の間に、入力される信号
の内容と、予め決められた動作の優先順位と、前記複数
のプロセッサエレメントの各々の優先順位とに従って、
前記要求を発生させた自キャッシュメモリにおけるデー
タの状態を決定する状態管理部とを備えたことを特徴と
するものである。
【0017】
【作用】本発明のキャッシュメモリ制御装置において
は、プロセッサエレメントは、例えば、リードミスが発
生し、このリードミスに対するデータ要求が発生した場
合、同期単位制御部は、データ要求時のみ共有バスやネ
ットワークを専有する権利を要求する。監視部は、プロ
セッサエレメントが上記の専有する権利を解放後、予め
定めた、要求に対する応答が受信されるのに必要な最大
時間だけ共有バスやネットワークから入力される信号を
監視する。
【0018】状態管理部は、監視部が監視した時間に入
力された信号と、予め定められた優先順位のルールに基
づき、キャッシュメモリのデータの状態を決定する。例
えば、監視時間内に、リードミスに対するデータが入力
されると共に、優先度の高い他のプロセッサエレメント
からライトヒット信号が入力された場合、入力されたデ
ータと他のプロセッサエレメントでライトヒットしたデ
ータは一致しなくなるため、入力したデータは無効とな
り、キャッシュメモリの状態は「Invalid」とな
る。また、他の場合でも、状態管理部は予め定められた
優先順位のルールに従って監視時間後にそのキャッシュ
メモリの状態を決定する。従って、プロセッサエレメン
トは共有バスやネットワークを専有する権利を明け渡し
た状態でも、キャッシュメモリにおけるデータの無矛盾
化は保証することができる。
【0019】
【実施例】以下、本発明の実施例を図面を用いて詳細に
説明する。図1は本発明のキャッシュメモリ制御装置の
実施例を示すブロック図である。図の装置は、複数のプ
ロセッサエレメント10(10−1〜10−n)とメイ
ンメモリ20と、共有バス(ネットワーク)30とから
なる。プロセッサエレメント10は、各々プロセッサ1
1(11−1〜11−n)と、キャッシュメモリ12
(12−1〜12−n)とからなる。尚、プロセッサエ
レメント10−2〜10−nの構成は、プロセッサエレ
メント10−1と同様であるため、内部の構成は図示省
略し、各プロセッサエレメント10に共通の構成は、プ
ロセッサ11およびキャッシュメモリ12として説明す
る。
【0020】プロセッサ11は、各種の制御を司る制御
部であり、特に、共有メモリ型マルチプロセッサシステ
ムにおいて、キャッシュメモリ12とメインメモリ20
間のデータのライト/リード制御や各キャッシュメモリ
12間のデータ転送等の制御を行うものである。そし
て、プロセッサ11は、キャッシュメモリ12の制御装
置として、同期単位制御部13、監視部14、状態管理
部15とを有している。同期単位制御部13は、操作を
分割して同期単位とする機能を有している。尚、この分
割については後述する。
【0021】また、監視部14は、バッファメモリ14
aを備え、予め定められた監視時間にバッファリングさ
れたデータを監視するためのものである。尚、ここで予
め定められた監視時間とは、プロセッサエレメント10
からある要求が発生した場合に、その要求の開始から応
答を受け取るまでに必要なシステムとしての最大遅れ時
間を指している。更に、状態管理部15は、予め、定め
られた優先順位に基づくルールを有し、監視部14によ
る監視時間の間、何らかの応答信号が入力された場合
は、このルールに従って、キャッシュメモリ12の状態
を決定するものである。
【0022】キャッシュメモリ12は、キャッシュメモ
リとしての既知の機能を有すると共に、状態管理部15
によって格納されているデータブロックの状態が決定さ
れるものである。また、メインメモリ20は各プロセッ
サエレメント10が共有するメモリであり、共有バス3
0は、これらプロセッサエレメント10とメインメモリ
20とを接続するバスである。尚、本実施例では、複数
のプロセッサエレメント10と、これらプロセッサエレ
メント10の共有メモリであるメインメモリ20とを接
続するネットワークを共有バス30として説明するが、
この共有バス30は、複数のプロセッサエレメント10
間で放送機能を持つ汎用的なネットワークであっても同
様である。
【0023】次に、上記同期単位制御部13による操作
の分割例をイリノイプロトコルの場合を例にとって説明
する。図3にイリノイプロトコルの状態遷移を示す。
尚、図3中、括弧内の番号は、以下の番号に対応してい
る。
【0024】(1)プロセッサ・リード・ミス (a)プロセッサ11がリード動作を行い、キャッシュ
ミスを起こすと、リード・ミス信号を有意にし、共有バ
ス30にデータを要求する。 (b1)キャッシュメモリ12またはメインメモリ20
から送られてくるデータを待ち、データが別のキャッシ
ュメモリ12から送られてくると、データを「Shar
ed Clean」の状態で登録する。 (b2)メインメモリ20からデータが送られてきた場
合(他のキャッシュメモリ12にデータが無い場合)
は、データを「Private Clean」の状態で
登録する。
【0025】(2)バス・リード・ミス これは、共有バス30のスレーブとなっているプロセッ
サ11(他のプロセッサ11がリクエストを出している
状態でこのリクエストを受ける方のプロセッサ)がリク
エストされたデータのコピーを持っていて、「バス・リ
ード・ミス」を受け取った場合である。
【0026】状態が「Private Clean」
または「Shared Clean」の場合 (a)マスタ側のキャッシュメモリ12(リクエストを
出した方のプロセッサエレメントのキャッシュメモリ)
にリクエストされたデータをブロック転送し、キャッシ
ュメモリ12の状態を「Shared Clean」に
する。 状態が「Dirty」の場合 (a)マスタ側のキャッシュメモリ12およびメインメ
モリ20に、リクエストされたデータをブロック転送
し、キャッシュメモリ12の状態を「Shared C
lean」にする。
【0027】(3)プロセッサ・ライト・ヒット 状態が「Dirty」または「Private Cl
ean」の場合 (a)データは直ちにキャッシュメモリ12に書かれ、
状態を「Dirty」にする。 状態が「Shared Clean」の場合 (a)プロセッサ11は共有バス30に無効化信号を送
出する。また、データをキャッシュメモリ12に書き、
状態を「Dirty」にする。
【0028】(4)プロセッサ・ライト・ミス (a)キャッシュミスを起こすと、ライト・ミス信号を
有意にし、共有バス30にデータを要求する。 (b)キャッシュメモリ12またはメインメモリ20か
ら送られてくるデータを待ち、データを「Dirty」
の状態でキャッシュメモリ12に登録する。また、この
時、キャッシュメモリ12からのデータを優先し、登録
する。そしてプロセッサ11がキャッシュメモリ12に
書込みを行う。
【0029】(5)バス・ライト・ヒット 状態が「Shared Clean」の場合 (a)プロセッサ11は、対応するデータの状態を無効
化する。
【0030】(6)バス・ライト・ミス 共有バス30のスレーブとなっているプロセッサ11が
リクエストされたデータのコピーを持っていて、「バス
・ライト・ミス」を受け取った場合 状態が「Private Clean」または「Sh
ared Clean」の場合 (a)マスタ側のキャッシュメモリ12に、リクエスト
されたデータをブロック転送し、キャッシュメモリ12
の状態を無効化する。 状態が「Dirty」の場合 (a)マスタ側のキャッシュメモリ12およびメインメ
モリ20に、リクエストされたデータをブロック転送
し、キャッシュメモリ12の状態を無効化する。
【0031】以上、(a)、(b)、(b1)、(b
2)といった操作が、それぞれ個別に一つの同期単位、
即ち、バス権を要求する単位として行われる。
【0032】そして、上記(1)プロセッサ・リード・
ミスと、(4)プロセッサ・ライト・ミスの場合、他の
キャッシュメモリ12あるいはメインメモリ20から送
られてくるデータを待つ必要があり、これらからの順序
は保証されていない。そこで、監視部14は、システム
としての最大遅れ時間の間、バッファメモリ14aに共
有バス30からの信号をバッファリングする。
【0033】更に、状態管理部15は、監視部14によ
る監視時間内に送られてきた信号に基づき、キャッシュ
メモリ12の状態を決定する。また、その決定のルール
は優先順位順に次のようになっている。 (1)他のキャッシュメモリ12からのスワップアウト (2)他のキャッシュメモリ12からのデータブロック
転送 (3)メインメモリ20からのデータブロック転送 状態管理部15は、このような優先順位に従い、監視時
間後にキャッシュメモリ12の状態を書き込むものであ
る。尚、プロセッサエレメント10の操作の分割は、共
有バス30に対する操作の分割であり、上記のようなキ
ャッシュメモリ12の状態遷移に関する操作の分割の必
要は無い。
【0034】更に、信号の遅れ時間を考慮すると、同一
ブロックに対してあたかも同時に事象が発生したような
状態が存在する。このような場合の種々の状態遷移に関
して、二つのプロセッサエレメントを例にとって以下に
説明する。
【0035】図4〜図10は、その状態を示す図であ
る。これらの図において、Pi、Pjは、それぞれプロ
セッサエレメントであり、各プロセッサエレメントP
i、Pjの時間軸で太線で示した長さが、共有バス30
上を流れる(放送される)信号を、監視部14が監視す
る時間を示している。
【0036】[1]同一ブロックに対する複数のリード
・ミスが同時に起きた場合(図4) また、図4中、“read miss”とは、プロセッ
サがリードミスを起こしたことを表し、“RM”とはリ
ードミス信号、“SH”は共有応答、“shared”
はキャッシュメモリの状態がShared Clean
になったことを表している。(a)の場合は、プロセッ
サエレメントPiからリードミス信号がプロセッサエレ
メントPjに届かないうちに、プロセッサエレメントP
j側から同一ブロックに対してリードミス信号が出力さ
れた場合であり、(b)の場合は、プロセッサエレメン
トPiからリードミス信号がプロセッサエレメントPj
に届いた後、プロセッサエレメントPj側からリードミ
ス信号が出力された場合である。このような二つのパタ
ーンの場合、共にリードミス信号を受けたプロセッサP
iは共有にする応答SHを返し、自分の状態を「Sha
red Clean」にする。
【0037】即ち、これらプロセッサエレメントPi、
Pjは、リードミス信号を送出後、対応するデータのブ
ロックを他のプロセッサエレメントのキャッシュメモリ
12あるいはメインメモリ20から受け取るが、いずれ
の場合もこのブロックを共有し、かつメインメモリ20
のブロックとも一致しているため、「SharedCl
ean」となるものである。
【0038】[2]同一ブロックに対するリードミスと
ライトヒットが同時に起きた場合(図5) また、図5中、“write hit”とは、プロセッ
サがライトヒットを起こしたことを表し、“WH”とは
ライトヒット信号、“IV”は無効化応答を示してい
る。そして、“shared”はキャッシュメモリの状
態がSharedCleanであることを表し、更に、
“dirty”はキャッシュメモリの状態がdirty
になり、“invalid”は、キャッシュメモリの状
態がinvalidになったことを表している。
【0039】ここで、(a)は、プロセッサエレメント
Piからライトヒット信号がプロセッサエレメントPj
に届かないうちに、プロセッサエレメントPj側から同
一ブロックに対してリードミス信号が出力された場合で
あり、(b)の場合は、プロセッサエレメントPiから
ライトヒット信号がプロセッサエレメントPjに届いた
後、プロセッサエレメントPj側からリードミス信号が
出力された場合である。
【0040】このような二つのパターンの場合、共にリ
ードミス信号を受けたプロセッサPiは無効化する応答
IVを返し、自分の状態を「Dirty」にする。ま
た、プロセッサエレメントPjは、無効化応答を受けた
ら、自分の状態を「Invalid」にする。即ち、プ
ロセッサエレメントPiのキャッシュメモリ12には、
新しいデータが書き込まれたため、そのブロックはメイ
ンメモリ20のブロックとは一致しなくなり、また、同
一のブロックを他のキャッシュメモリ12が持っていた
場合、そのデータは無効となるものである。
【0041】尚、プロセッサエレメントPjは、監視時
間後には、キャッシュメモリ12の状態が「Inval
id」となるため、その後、再度リードミス信号を送出
することになる。
【0042】[3]同一ブロックに対するリードミスと
ライトミスが同時に起きた場合(図6) また、図6中、“write miss”はプロセッサ
がライトミスを起こしたことを表し、“WM”はライト
ミス信号を表している。ここで、(a)、(b)は、上
記[2]の場合と同様に、プロセッサエレメントPiか
らライトミス信号がプロセッサエレメントPjに届かな
いうちに、プロセッサエレメントPj側から同一ブロッ
クに対してリードミス信号が出力された場合、およびプ
ロセッサエレメントPiからライトミス信号がプロセッ
サエレメントPjに届いた後、プロセッサエレメントP
j側からリードミス信号が出力された場合である。ま
た、(c)は、プロセッサエレメントPjからのリード
ミス信号が先にプロセッサエレメントPiに届いた場合
である。
【0043】このような場合は、上記[2]の場合と同
様に、全て、プロセッサエレメントPiはプロセッサP
jを無効化する応答を返し、プロセッサエレメントPj
は無効化応答を受けたら、自分の状態を「Invali
d」にする。尚、この場合、プロセッサエレメントPj
は、監視時間の間に、プロセッサエレメントPi以外の
プロセッサエレメントあるいはメインメモリ20からリ
ードミスに対するデータを受け取ることが考えられる
が、プロセッサエレメントPi以外のデータは正しくな
いデータであるため、「Invalid」とするもので
ある。
【0044】また、プロセッサエレメントPiは、監視
時間内に、後述するような優先順位の高いプロセッサエ
レメントからのライトヒットまたはライトミスといった
事象発生の通知を受けなかった場合は、自分の状態を
「Dirty」とする。
【0045】[4]同一ブロックに対する複数のライト
ヒットまたはライトミスが同時に起きた場合(図7〜図
9) 図に示すように、(a)〜(h)の八つのパターンがあ
り、(a)とそれ以外に分類できる。即ち、(a)のパ
ターンは、ライトヒットの遷移中であるプロセッサPi
が、他のプロセッサエレメントであるプロセッサエレメ
ントPjからライトヒット信号を受けた場合で、この場
合は、プロセッサの優先度に従う。例えば、受けた信号
が自プロセッサエレメントより高い優先度の場合、自分
の状態を「Invalid」にし、受けた信号が自プロ
セッサエレメントより低い優先度の場合は、受けた信号
を無視する。
【0046】図7の(a)〜(h)に示す例では、プロ
セッサエレメントの優先度はPi>Pjとした場合であ
り、従って、(a)ではプロセッサエレメントPiは自
分の状態を「Dirty」とし、プロセッサエレメント
Pjは自分の状態を「Invalid」とする。
【0047】また、(b)のパターンは、プロセッサエ
レメントPiが「Shared Clean」の状態で
ライトヒットし、そのライトヒット信号をプロセッサエ
レメントPjが受け、その後、プロセッサエレメントP
jがライトミス信号を送出する場合である。この場合、
プロセッサエレメントPiは、監視時間内に自分より優
先度の高い他のプロセッサエレメントからライトヒット
やライトミスといった事象発生の通知を受けなければ、
自分の状態を「Dirty」とし、プロセッサエレメン
トPjは、監視時間後、自分の状態を「Invali
d」とする。
【0048】次に、(c)のパターンは、プロセッサエ
レメントPiがライトミス、プロセッサエレメントPj
がライトヒットした場合である。この場合、プロセッサ
エレメントPiの方が優先度が高いため、プロセッサエ
レメントPjに対して無効化信号を送出し、自分の状態
を「Dirty」とする。
【0049】また、(d)のパターンは、プロセッサエ
レメントPiがライトヒット、プロセッサエレメントP
jがライトミスであった例である。この場合も、優先度
の高いプロセッサエレメントPiが、プロセッサエレメ
ントPjに対して無効化応答を返し、自分の状態を「D
irty」とする。
【0050】そして、(e)のパターンは、上記(d)
の場合とは逆に、プロセッサエレメントPiがライトミ
ス、プロセッサエレメントPjがライトヒットであった
例である。しかし、この場合も、優先度によって状態遷
移が行われるため、優先度の高いプロセッサエレメント
Piが、プロセッサエレメントPjに対して無効化応答
を返し、自分の状態を「Dirty」とする。
【0051】更に、(f)、(g)、(h)のパターン
は、プロセッサエレメントPi、Pjが共にライトミス
の場合であり、(f)がほぼ同時に発生した場合、
(g)は、プロセッサエレメントPiの方が先に発生
し、そのライトミス信号がプロセッサエレメントPjの
ライトミス発生より早く届いた場合、(h)は(g)と
逆の場合である。これらの例でも、優先度の高いプロセ
ッサエレメントPiは相手のプロセッサエレメントPj
を無効化する応答を返し、自分の状態を「Dirty」
とする。
【0052】[5]同一ブロックに対するリードミスま
たはライトミスとスワップアウトが同時に起きた場合
(図10) (a)および(b)は、プロセッサエレメントPiにリ
ードミスまたはライトミスが起き、ほぼ同時刻にプロセ
ッサエレメントPjにスワップアウトが起きた例であ
る。このような場合は、プロセッサエレメントの優先度
には無関係に、スワップアウトの事象が優先されるた
め、プロセッサエレメントPiのリードミスまたはライ
トミスに対するメインメモリ20から転送されたデータ
ブロックは無効となり、監視時間の後、プロセッサエレ
メントPiは、再度リードミス信号またはライトミス信
号を送出することになる。尚、スワップアウトしたプロ
セッサエレメントPjは、そのキャッシュメモリ12に
データブロックが存在しない状態となる。
【0053】このように、上記実施例では、システムの
最大遅れ時間は、共有バス30からの信号を監視し、か
つ予め決められたルールに従ってキャッシュメモリ12
の状態遷移を決定するようにしたので、例えば、従来の
図2で示した例でもキャッシュメモリ2は正しいデータ
を受け取ることができる。即ち、図2の例ではキャッシ
ュメモリ2は、m時間後にメインメモリ3よりデータを
受け取るが、このデータは監視時間内に入力されるキャ
ッシュメモリ1からのスワップアウト信号により、無効
化される。そして、キャッシュメモリ2は、その後再度
リードミス信号を送出し、このリードミス信号によっ
て、メインメモリ3から正しいデータが送られてくるも
のである。
【0054】尚、上記実施例では、マルチプロセッサシ
ステムにおけるキャッシュメモリの無矛盾化プロトコル
としてイリノイプロトコルを例にとって説明したが、こ
れに限定されるものではなく、バークレイプロトコル
等、種々のプロトコルでも適用可能である。
【0055】
【発明の効果】以上説明したように、本発明のキャッシ
ュメモリ制御装置によれば、プロセッサエレメントの操
作群を分割し、信号送出時のみネットワークを専有する
同期単位とし、かつ、要求発生からその要求に対する応
答が受信されるのに必要な最大時間はネットワークから
の入力信号を監視し、この監視した時間内に入力される
信号と予め定められた優先順位に基づくルールに従って
キャッシュメモリのデータ状態を決定するようにしたの
で、ネットワークの利用効率が向上し、従って、大規模
なシステム用の大規模バスや汎用的なネットワーク結合
網に置き換え可能となり、システム全体の性能向上を期
待することができる。
【図面の簡単な説明】
【図1】本発明のキャッシュメモリ制御装置のブロック
図である。
【図2】従来の問題点を説明するためのマルチプロセッ
サシステムの要部構成図である。
【図3】本発明のキャッシュメモリ制御装置に関わるイ
リノイプロトコルの状態遷移の説明図である。
【図4】本発明のキャッシュメモリ制御装置における同
一ブロックに対する複数のリード・ミスが同時に起きた
場合の説明図である。
【図5】本発明のキャッシュメモリ制御装置における同
一ブロックに対するリードミスとライトヒットが同時に
起きた場合の説明図である。
【図6】本発明のキャッシュメモリ制御装置における同
一ブロックに対するリードミスとライトミスが同時に起
きた場合の説明図である。
【図7】本発明のキャッシュメモリ制御装置における同
一ブロックに対する複数のライトヒットまたはライトミ
スが同時に起きた場合(その1)の説明図である。
【図8】本発明のキャッシュメモリ制御装置における同
一ブロックに対する複数のライトヒットまたはライトミ
スが同時に起きた場合(その2)の説明図である。
【図9】本発明のキャッシュメモリ制御装置における同
一ブロックに対する複数のライトヒットまたはライトミ
スが同時に起きた場合(その3)の説明図である。
【図10】本発明のキャッシュメモリ制御装置における
同一ブロックに対するリードミスまたはライトミスとス
ワップアウトが同時に起きた場合の説明図である。
【符号の説明】
10−1〜10−n プロセッサエレメント 11−1〜11−n プロセッサ 12−1〜12−n キャッシュメモリ 13−1〜13−n 同期単位制御部 14−1〜14−n 監視部 15−1〜15−n 状態管理部
───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.7,DB名) G06F 12/08

Claims (1)

    (57)【特許請求の範囲】
  1. 【請求項1】 それぞれがプロセッサとキャッシュメモ
    リとを備えたプロセッサエレメントを放送機能を有する
    ネットワークに接続してなるマルチプロセッサシステム
    のキャッシュメモリ制御装置において、 前記それぞれのプロセッサエレメントは、 各プロセッサエレメントの信号送出時のみ前記ネットワ
    ークを専有する同期単位制御部と、 前記プロセッサエレメントが前記ネットワークを専有す
    る権利を解放後、当該プロセッサエレメントからの要求
    に対する応答が受信されるのに必要な最大時間だけ前記
    ネットワークからの入力信号を監視する監視部と、 前記監視部による監視時間の間に、入力される信号の内
    と、予め決められた動作の優先順位と、前記複数のプ
    ロセッサエレメントの各々の優先順位とに従って、前記
    要求を発生させた自キャッシュメモリにおけるデータの
    状態を決定する状態管理部とを備えたキャッシュメモリ
    制御装置。
JP05215299A 1993-08-06 1993-08-06 キャッシュメモリ制御装置 Expired - Fee Related JP3097941B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP05215299A JP3097941B2 (ja) 1993-08-06 1993-08-06 キャッシュメモリ制御装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP05215299A JP3097941B2 (ja) 1993-08-06 1993-08-06 キャッシュメモリ制御装置

Publications (2)

Publication Number Publication Date
JPH0749809A JPH0749809A (ja) 1995-02-21
JP3097941B2 true JP3097941B2 (ja) 2000-10-10

Family

ID=16670026

Family Applications (1)

Application Number Title Priority Date Filing Date
JP05215299A Expired - Fee Related JP3097941B2 (ja) 1993-08-06 1993-08-06 キャッシュメモリ制御装置

Country Status (1)

Country Link
JP (1) JP3097941B2 (ja)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP5722264B2 (ja) * 2012-03-23 2015-05-20 株式会社日立ハイテクノロジーズ データ処理装置、データ容量増加抑制方法

Also Published As

Publication number Publication date
JPH0749809A (ja) 1995-02-21

Similar Documents

Publication Publication Date Title
KR100465583B1 (ko) 판독 요청을 원격 처리 노드에 추론적으로 전송하는 비정형 메모리 액세스 데이터 처리 시스템 및 이 시스템에서의 통신 방법
US5958019A (en) Multiprocessing system configured to perform synchronization operations
US8190820B2 (en) Optimizing concurrent accesses in a directory-based coherency protocol
US5796977A (en) Highly pipelined bus architecture
US7177987B2 (en) System and method for responses between different cache coherency protocols
JP3696012B2 (ja) 書込み動作順序付けバスブリッジ
EP0640923A1 (en) System and method to notify an empty status from peer cache units to global storage control unit in a multiprocessor data processing system
KR20000005690A (ko) 잠재적인제3노드트랜잭션을버퍼에기록하여통신대기시간을감소시키는비균일메모리액세스(numa)데이터프로세싱시스템
US7818509B2 (en) Combined response cancellation for load command
KR20000022712A (ko) 노드 상호 접속망 상에서 요구를 예측 방식으로 발행하는 비균일 메모리 액세스 데이터 처리 시스템
US6922755B1 (en) Directory tree multinode computer system
US7149852B2 (en) System and method for blocking data responses
US6295583B1 (en) Method and apparatus for resolving probes in multi-processor systems which do not use external duplicate tags for probe filtering
US5701422A (en) Method for ensuring cycle ordering requirements within a hierarchical bus system including split-transaction buses
US6826643B2 (en) Method of synchronizing arbiters within a hierarchical computer system
JP3097941B2 (ja) キャッシュメモリ制御装置
EP1701267B1 (en) Address snoop method and multi-processor system
JP2734246B2 (ja) パイプラインバス
US6735654B2 (en) Method and apparatus for efficiently broadcasting transactions between an address repeater and a client
US6889343B2 (en) Method and apparatus for verifying consistency between a first address repeater and a second address repeater
US6877055B2 (en) Method and apparatus for efficiently broadcasting transactions between a first address repeater and a second address repeater
JP4424619B2 (ja) 情報処理装置
US20020133652A1 (en) Apparatus for avoiding starvation in hierarchical computer systems that prioritize transactions
JP2006209797A (ja) キャッシュコヒーレンス装置
JPH11120157A (ja) 並列コンピュータシステム内の高速通信のための方法及びこの方法によって操作される並列コンピュータシステム

Legal Events

Date Code Title Description
LAPS Cancellation because of no payment of annual fees