JPH04302044A - マルチプロセッサシステム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】［発明の目的］

【０００２】

【産業上の利用分野】本発明は、共有メモリのキャッシ
ュ装置を持つ複数のプロセッサをバスを通じて接続して
なるマルチプロセッサシステムに関する。

【０００３】

【従来の技術】マルチプロセッサシステムにおいて、共
有メモリのアクセスは共通のバスを通して行われる。こ
のバスは一度に１つのプロセッサしか使用できないこと
から、複数のプロセッサが同時に共有メモリをアクセス
しようとした時に、あるプロセッサがアクセスを待たさ
れる（アクセスの衝突）といった事態が起こる。これを
避けるために、プロセッサ毎にキャッシュ装置を設け、
共有メモリの内容をキャッシュ装置内のメモリに複写す
ることで、プロセッサによるメモリアクセスをキャッシ
ュ装置へのアクセスのみに止めてバスへのアクセスを抑
制することが行われる。この場合、複数のキャッシュ装
置に同一のアドレスの内容が保持される可能性があり、
これら同一アドレスの内容の一貫性を保持する必要があ
る。そこでキャッシュ装置内のメモリを複数のエリア（
キャッシュ単位）に分け、このキャッシュ単位毎に占有
か共有か、または有効か無効かの状態を保持し、占有状
態以外の状態のキャッシュ単位内のアドレスにｗｒｉｔ
ｅ　が行われた時はこのキャッシュ単位を占有状態にし
、かつ同一アドレスを含む他のプロセッサのキャッシュ
単位を無効にする命令をバス経由で伝達し、これらを無
効状態にするｗｒｉｔｅ−ｉｎｖａｌｉｄ型と呼ばれる
手法や、あるプロセッサのキャッシュにｗｒｉｔｅ　が
行われた時に他のプロセッサのキャッシュにｗｒｉｔｅ
　内容をバス経由で伝達し、同一アドレスを含む部分を
更新するｗｒｉｔｅ−ｕｐｄａｔｅ型と呼ばれる手法な
どが用いられている。

【０００４】このとき、プログラムのリードや連続アド
レスに割り当てられたデータの初期化時などにおいては
、あるアドレスのアクセス後、後続のアドレスへのアク
セスが行われる可能性が高い。このことから、キャッシ
ュブロックサイズが大きく、１キャッシュブロック内に
連続する複数ワードを含む方が、ヒット率が向上し、ア
クセス効率が高まる。

【０００５】しかしながら、複数のプロセッサが同一ブ
ロック内の別ワードへ頻繁にアクセスする場合、あるプ
ロセッサがデータをｗｒｉｔｅ　する度に他プロセッサ
の対応するキャッシュブロック全体が無効となってしま
い、該ワード自身は有効であるにも拘らず無効となって
しまう。また、キャッシュブロックを小さくすると、キ
ャッシュブロックの情報であるアドレスや、状態を格納
する領域の増大、あるいは連続領域へのアクセス時の効
率低下の問題なども生じる。

【０００６】このため、従来は、キャッシュブロックを
アクセスの単位であるワードなどのように小さくし、キ
ャッシュ装置にないアドレスをリードしたときに、共有
メモリとキャッシュ装置との間にある数ワード分のバッ
ファから連続の数ワードを読み込み、以降のリードで、
目的のデータがこのバッファにある場合には主メモリま
で読みに行かずにこのバッファからリードすることによ
り、バスへのアクセスを減らしバッファを含めてのヒッ
ト率を高める、などの手法がとられてきた。

【０００７】

【発明が解決しようとする課題】しかし、この手法でも
、キャッシュブロックの情報の増大、検索時間の増加、
と言った問題は解決されず、さらにバッファ内データの
有効／無効を保証する処理などが増えてしまうと言う問
題があった。

【０００８】本発明はこのような事情に対処してなされ
たもので、ヒット率の向上、検索時間の短縮を図ると同
時に、本来有効なデータを無効にしてしまうような事態
を阻止することのできるマルチプロセッサシステムの提
供を目的としている。

【０００９】［発明の構成］

【００１０】

【課題を解決するための手段】本発明のマルチプロセッ
サシステムは、上記した目的を達成するために、バスに
、共有メモリと、前記共有メモリのキャッシュ装置を有
する複数のプロセッサとを接続して構成されるマルチプ
ロセッサシステムにおいて、前記プロセッサのキャッシ
ュ装置が、連続ｎワードからなるキャッシュブロックご
とに、該キャッシュブロック内のワードがすべて有効で
あるか否かの情報を保持する手段と、前記キャッシュブ
ロック内のワードごとに、該キャッシュブロック内のワ
ードがすべて有効であるときは該ワードが占有か共有か
の情報、該キャッシュブロック内のワードがすべては有
効でないときは該ワードが有効か無効かの情報を保持す
る手段とを有することを特徴としている。

【００１１】

【作用】本発明では、連続ｎワードをキャッシュブロッ
クとすることにより、ヒット率の向上、検索時間の短縮
を図り、さらに、キャッシュブロックごとの、キャッシ
ュブロック内のワードがすべて有効であるか否かを示す
情報と、ワードごとの、キャッシュブロック内のワード
がすべて有効である場合の占有か共有を示す情報若しく
はキャッシュブロック内のワードがすべてが有効でない
場合の有効か無効かを示す情報を持つことにより、本来
有効なデータが無効として扱われたり、既に占有となっ
ているデータのライト時に無効化信号を送出したりする
ことを避けることができる。

【００１２】

【実施例】以下、本発明の実施例の詳細を図面に基づい
て説明する。

【００１３】図１は本発明に係る一実施例のマルチプロ
セッサシステムの構成を示すブロック図である。同図に
示すように、このマルチプロセッサシステムは複数のプ
ロセッサ１１ａ、１１ｂと共有メモリ１２とをそれぞれ
共通のバス１３を通じ接続して構成されている。但し、
各プロセッサ１１ａ、１１ｂは、それぞれ共有メモリ１
２の内容を複写し保持するキャッシュ装置１４ａ、１４
ｂを介してバス１３に接続されている。各キャッシュ装
置１４ａ、１４ｂは、それぞれキャッシュコントローラ
１５ａ、１５ｂとキャッシュメモリ１６ａ、１６ｂとか
ら構成されている。

【００１４】また、各キャッシュ装置１４ａ、１４ｂの
キャッシュコントローラ１５ａ、１５ｂは、図２に示す
ように、連続ｎワードからなるキャッシュブロックごと
の情報を登録する第１の情報テーブル２１と、ワードご
との情報およびデータを登録する第２の情報テーブル２
２とを管理している。第１の情報テーブル２１は、キャ
ッシュメモリ１６ａ、１６ｂ内のキャッシュブロックの
アドレス２１１とそのキャッシュブロックの有効／無効
を示す情報２１２とからなっている。また第２の情報テ
ーブル２２は、ワードの占有／共有を示す情報および有
効／無効を示す情報２２１と、そのワードのデータ２２
２とからなっている。

【００１５】次に、本実施例のマルチプロセッサシステ
ムにおいて、図３に示すアクセスパターンで各プロセッ
サ１１ａ、１１ｂによるアクセス（ｗｒｉｔｅ操作また
はｒｅａｄ操作）が行われた場合の各キャッシュ装置１
４ａ、１４ｂの動作を説明する。

【００１６】尚、図４は各プロセッサ１１ａ、１１ｂの
各情報テーブル２１、２２の初期状態を示している。

【００１７】まず図３のステップ１において、プロセッ
サ１１ａでアドレス１００に対するｒｅａｄアクセスが
発生すると、図５に示すように、まずプロセッサ１１ａ
からｒｅａｄアクセスを受けたキャッシュコントローラ
１５ａは、そのｒｅａｄアドレスを含むキャッシュブロ
ックがキャッシュメモリ１６ａに存在するかを第１の情
報テーブル２１を参照して調べる（ステップ５０１）。 すると、当該アドレス１００を含むキャッシュブロック
の先頭アドレスである１００は第１の情報テーブル２１
に登録されていないので、アドレス１００から始まるキ
ャッシュブロック分のデータをブロックリードしてこれ
を登録する（ステップ５０９）。ここで、キャッシュブ
ロックの先頭アドレスは（アクセスするワードのアドレ
ス）−（ワードのアドレス　ｍｏｄキャッシュブロック
サイズ）で決まる。次にこのキャッシュブロック全体を
有効とし（ステップ５１０）、全ワードを共有とする（
ステップ５１１）。最後にプロセッサ１１ａにこのワー
ドのデータを渡す（ステップ５０８）。

【００１８】一方、ブロックリードと共に出されたｒｅ
ａｄ信号を検出したキャッシュコントローラ１５ａは、
図６に示すように、第１の情報テーブル２１にアドレス
１００を含むキャッシュブロックが登録されているかを
調べる（ステップ６０１）。この場合、該当ブロックは
存在しないので何もしない。これにより、各情報テーブ
ル２１、２２は、図７に示すような内容に更新される。

【００１９】次に、図３のステップ２において、プロセ
ッサ１１ａでアドレス１０１に対するｒｅａｄアクセス
が発生すると、プロセッサ１１ａからｒｅａｄアクセス
を受けたキャッシュコントローラ１５ａは、ステップ１
の場合同様、図５に示すように、ｒｅａｄアドレス１０
１を含むキャッシュブロックがキャッシュメモリ１６ａ
に存在するかを調べる（ステップ５０１）。この場合、
該当するキャッシュブロックが存在し、しかもこのキャ
ッシュブロック全体が有効であるので（ステップ５０２
）、キャッシュメモリ１６ａに存在するｒｅａｄ　　ア
ドレス１０１のデータをプロセッサ１１ａに渡す（ステ
ップ５０８）。このステップでは、各情報テーブル２１
、２２に変化はない。

【００２０】次に図３のステップ３において、プロセッ
サ１１ｂでアドレス１００に対するｒｅａｄアクセスが
発生すると、プロセッサ１１ｂからｒｅａｄアクセスを
受けたキャッシュコントローラ１５ｂは、ステップ１の
場合と同様、図５に示すように、ｒｅａｄアドレス１０
０を含むキャッシュブロックがキャッシュメモリ１６ｂ
に存在しないことを判定して（ステップ５０１）、アド
レス１００から始まるキャッシュブロック分のデータを
ブロックリードし、これを登録する（ステップ５０９）
。そしてこのキャッシュブロック全体を有効とし（ステ
ップ５１０）、全ワードを共有とする（ステップ５１１
）。最後にプロセッサ１１ｂにこのワードのデータを渡
す（ステップ５０８）。

【００２１】一方、ブロックリードと共に出されたｒｅ
ａｄ信号を検出したキャッシュコントローラ１５ａは、
図６に示すように、第１の情報テーブル２１にアドレス
１００を含むキャッシュブロックが登録されていること
（ステップ６０１）、該キャッシュブロック全体が有効
であることを確認したものの（ステップ６０２）、該ワ
ード（アドレス１００）が占有でないため（ステップ６
０３）、この場合は何の処理も行わない。この結果、各
情報テーブル２１、２２の内容は、図８に示すように更
新される。

【００２２】図３のステップ４から８は、ステップ２と
まったく同様に処理が行われ、各情報テーブル２１、２
２の内容には変化はない。

【００２３】次のステップ９についてもステップ１と同
様に処理が行われ、その結果、各情報テーブル２１、２
２の内容は、図９に示すように更新される。

【００２４】さらにステップ１０はステップ３と同様に
処理が行われ、その結果、各情報テーブル２１、２２の
内容は、図１０に示すように更新される。

【００２５】次に図３のステップ１１において、プロセ
ッサ１１ａでアドレス１００に対するｗｒｉｔｅ　アク
セスが発生すると、プロセッサ１１ａからｗｒｉｔｅ　
アクセスを受けたキャッシュコントローラ１５ａは、図
１１に示すように、ｗｒｉｔｅ　アドレス１００を含む
キャッシュブロックがキャッシュメモリ１６ａに存在し
（ステップ１１０１）、さらに該キャッシュブロック全
体が有効であることを判定するものの（ステップ１１０
２）、アドレス１００の該ワードが占有でないため（ス
テップ１１０６）、アドレス１００に対して無効化信号
をバス１３に送出し（ステップ１１０７）、該ワードを
占有とする（ステップ１１０８）。最後にキャッシュメ
モリ１６ａの該当ワード部分をプロセッサ１１ａから渡
されたデータで更新する（ステップ１１０９）。

【００２６】一方、バス１３より無効化信号を検出した
キャッシュコントローラ１５ｂは、図１２に示すように
、第１の情報テーブル２１にアドレス１００を含むキャ
ッシュブロックが登録されていること（ステップ１２０
１）、さらに該キャッシュブロック全体が有効であるこ
とを確認して（ステップ１２０２）、該キャッシュブロ
ックの全ワードは有効でないものとし（ステップ１２０
３）、該ワード（アドレス１００）を無効として、他の
ワード（アドレス１０１、１０２、１０３）を有効にす
る（ステップ１２０４）。この結果、各情報テーブル２
１、２２は、図１３に示すように更新される。

【００２７】次に図３のステップ１２において、プロセ
ッサ１１ｂでアドレス１０１に対するｒｅａｄアクセス
が発生すると、これを受けたキャッシュコントローラ１
５ｂは、図５に示すように、ｒｅａｄアドレス１０１を
含むアドレス１００からキャッシュブロックがキャッシ
ュメモリ１６ａに存在し（ステップ５０１）、このキャ
ッシュブロック全体が有効ではないものの（ステップ５
０２）、アドレス１０１のワードは有効であるので（ス
テップ５０３）、キャッシュメモリ１６ａに存在するｒ
ｅａｄアドレス１０１のデータをプロセッサ１１ｂに渡
す（ステップ５０８）。このステップでは各情報テーブ
ル２１、２２に変化はない。

【００２８】この後、図３のステップ１３において、同
じくプロセッサ１１ｂでアドレス１０１に対するｗｒｉ
ｔｅ　アクセスが発生すると、これを受けたキャッシュ
コントローラ１５ｂは、図１１に示すように、ｗｒｉｔ
ｅ　アドレス１０１を含むキャッシュブロックがキャッ
シュメモリ１６ｂに存在するものの（ステップ１１０１
）、該キャッシュ全体が有効ではないので（ステップ１
１０２）、キャッシュブロック内の無効ワードであるア
ドレス１００のワードをリードする（ステップ１１０３
）。そしてアドレス１０１に対して無効化信号を送出し
（ステップ１１０４）、アドレス１０１のワードを占有
にして他のアドレス１００、１０２、１０３のワードを
共有にする（ステップ１１０５）。そして最後にキャッ
シュメモリ１６ｂの該当ワード部分をプロセッサ１１ｂ
から渡されたデータで更新する（ステップ１１０９）。

【００２９】一方、無効化信号を検出したキャッシュコ
ントローラ１５ａは、図１２に示すように、第１の情報
テーブル２１にアドレス１０１を含むキャッシュブロッ
クが登録され（ステップ１２０１）、さらに該キャッシ
ュブロック全体が有効であることを確認して（ステップ
１２０２）、該キャッシュブロックを全ワードは有効で
ないものとし（ステップ１２０３）、該ワード（アドレ
ス１０１）を無効にして、他のワード（アドレス１００
，１０２，１０３）を有効にする（ステップ１２０４）
。この結果、情報テーブル２１、２２は、図１４に示す
ような内容に更新される。

【００３０】図３のステップ１４は、ステップ１２とま
ったく同様に自プロセッサ１１ａのキャッシュメモリ１
６ａからリードされる。

【００３１】図３のステップ１５において、プロセッサ
１１ｂでアドレス１０２に対するｗｒｉｔｅ　アクセス
が発生すると、これを受けたキャッシュコントローラ１
５ｂは、図１１に示すように、ｗｒｉｔｅ　アドレス１
０２を含むキャッシュブロックがキャッシュメモリ１６
ｂに存在し（ステップ１１０１）、しかも該キャッシュ
ブロック全体が有効であるものの（ステップ１１０２）
、該アドレス１０２のワードが共有なので（ステップ１
１０６）、アドレス１０２に対して無効化信号を送出し
（ステップ１１０７）、このワードを占有にして（ステ
ップ１１０８）、キャッシュメモリ１６ｂの該当ワード
部分をプロセッサ１１ｂから渡されたデータで更新する
（ステップ１１０９）。

【００３２】一方、無効化信号を検出したキャッシュコ
ントローラ１５ａは、図１２に示すように、第１の情報
テーブル２１にアドレス１０２を含むキャッシュブロッ
クが登録されているものの（ステップ１２０１）、該キ
ャッシュブロック全体が有効でないので（ステップ１２
０２）、該ワード（アドレス１０２）を無効にする（ス
テップ１２０５）。この結果、情報テーブル２１、２２
の内容は、図１５に示すように更新される。

【００３３】次に図３のステップ１６において、プロセ
ッサ１１ａでアドレス１０１に対するｒｅａｄアクセス
が発生すると、これを受けたキャッシュコントローラ１
５ａは、図５に示すように、ｒｅａｄ　　アドレス１０
１を含むキャッシュブロックがキャッシュメモリ１６ａ
に存在するものの（ステップ５０１）、このキャッシュ
ブロック全体が有効ではなく（ステップ５０２）、アド
レス１０１のワードが無効であるので（ステップ５０３
）、該アドレス１０１のワードをリードすると共にｒｅ
ａｄ信号を送出し（ステップ５０４）、該ワードを有効
とする（ステップ５０５）。ところが、この段階でこの
ワードを含むアドレス１００から始まるキャッシュブロ
ックの全ワードが有効にはなっていないので、キャッシ
ュブロックの情報の全体は有効でないままとする（ステ
ップ５０６）。 最後にリードしたデータをプロセッサ１１ａに渡す（ス
テップ５０８）。

【００３４】一方、リードと共に出されたｒｅａｄ信号
を検出したキャッシュコントーラ１５ｂは、図６に示す
ように、第１の情報テーブル２１にアドレス１０１を含
むキャッシュブロックが登録され（ステップ６０１）、
該キャッシュブロック全体が有効で（ステップ６０２）
、しかも該ワード（アドレス１０１）が占有なので（ス
テップ６０３）、該ワードを共有とする（ステップ６０
４）。この結果、情報テーブルの内容は、図１６に示す
ように更新される。

【００３５】図１７は本実施例によるバスへの操作を、
従来のｗｒｉｔｅ−ｉｎｖａｌｉｄ　方式（従来方式１
）、およびキャッシュブロックサイズを１ワードとして
４バイトの入力バッファを設けた従来方式２とそれぞれ
比較して示す図である。

【００３６】これによると、従来方式１の場合、ステッ
プ１２、１４などで本来は有効なワードが無効と判断さ
れ、不要なブロックリードが生じてしまうのに対し、本
実施例の場合はこのような事態を避けられるため、バス
へのアクセスが減ってマルチプロセッサシステム全体の
効率を高めることができる。また従来方式２は、バスの
使用などは本実施例の場合と同等であるが、キャッシュ
ブロックが小さいために、あるアドレスのデータがどの
キャッシュブロックに格納されているかを検索する時間
が増加し、バッファの追加によるハードウェアの複雑化
やブロックの情報量の増加といった問題が生じる。

【００３７】

【発明の効果】以上説明したように本発明によれば、連
続ｎワードをキャッシュブロックとすることにより、ヒ
ット率の向上、検索時間の短縮を図れる。また、本来有
効なデータが無効として扱われたり、既に占有となって
いるデータのライト時に無効化信号を送出したりするこ
とを避けることができる。

【図面の簡単な説明】

【図１】本発明に係る一実施例のマルチプロセッサシス
テムの構成を示すブロック図である。

【図２】図１におけるキャッシュ装置が保持する第１お
よび第２の情報テーブルの構造を示す図である。

【図３】本実施例のマルチプロセッサシステムにおける
各プロセッサ間でのアクセスパターンの例を示す図であ
る。

【図４】図２の各情報テーブルの初期状態を示す図であ
る。

【図５】プロセッサのワードリード時の処理の流れを示
すフローチャートである。

【図６】プロセッサのリード信号検出時の処理の流れを
示すフローチャートである。

【図７】図３におけるステップ１実行後の各情報テーブ
ルの内容を示す図である。

【図８】ステップ３実行後の各情報テーブルの内容を示
す図である。

【図９】ステップ９実行後の各情報テーブルの内容を示
す図である。

【図１０】ステップ１０実行後の各情報テーブルの内容
を示す図である。

【図１１】プロセッサのワードライト時の処理の流れを
示すフローチャートである。

【図１２】プロセッサの無効化信号検出時の処理の流れ
を示すフローチャートである。

【図１３】ステップ１１実行後の各情報テーブルの内容
を示す図である。

【図１４】ステップ１３実行後の各情報テーブルの内容
を示す図である。

【図１５】ステップ１５実行後の各情報テーブルの内容
を示す図である。

【図１６】ステップ１６実行後の各情報テーブルの内容
を示す図である。

【図１７】本実施例によるバスへの操作を従来方式と比
較して示す図である。

【符号の説明】

１１ａ、１１ｂ……プロセッサ １２……共有メモリ １３……バス １４ａ、１４ｂ……キャッシュ装置 １５ａ、１５ｂ……キャッシュコントローラ１６ａ、１
６ｂ……キャッシュメモリ

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　バスに、共有メモリと、前記共有メモ
   リのキャッシュ装置を有する複数のプロセッサとを接続
   して構成されるマルチプロセッサシステムにおいて、前
   記プロセッサのキャッシュ装置が、連続ｎワードからな
   るキャッシュブロックごとに、該キャッシュブロック内
   のワードがすべて有効であるか否かの情報を保持する手
   段と、前記キャッシュブロック内のワードごとに、該キ
   ャッシュブロック内のワードがすべて有効であるときは
   該ワードが占有か共有かの情報を、該キャッシュブロッ
   ク内のワードがすべては有効でないときは該ワードが有
   効か無効かの情報を保持する手段と、を有することを特
   徴とするマルチプロセッサシステム。