JPH0467242A - プロセッサおよびそのキャッシュメモリ制御方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明はキャッシュメモリ制御方式、特に複数の機器が
メモリを共有するシステムにおけるプロセッサのキャッ
シュメモリ制御方式に関するものである。

［従来の技術］ 計算機システムにおける性能の向上を得るために、プロ
セッサを複数個備えて並列処理を行うマルチプロセッサ
システムが使われるようになってきている。マルチプロ
セッサシステムの中でも、複数のプロセッサがメモリを
共有し、この共有メモリによってジョブのスケジューリ
ングやデータの共有を行なう共有メモリ型マルチプロセ
ッサシステム（以下、単にマルチプロセッサと言う）が
、従来のマルチプログラミングにおけるプログラミング
・モデルとの親和性の高さから広く受は入れられている
。

この型のマルチプロセッサでは、共有のメモリに対する
アクセスがシステムのボトルネックになり易い。このボ
トルネックを解消するために、共有メモリのコピーをプ
ロセッサ毎にキャッシュメモリに置き、共有メモリへの
アクセスをキャッシュメモリへのアクセスで代替して、
実際の共有メモリへのアクセスを低減する方法がとられ
ることが普通である。この時、複数のプロセッサが同一
のデータブロックのコピーを各々のキャッシュメモリに
置くため、全部のプロセッサが共有メモリを基準として
矛盾のないメモリイメージを持つようにしなければなら
ない、これはマルチプロセッサにおけるキャッシュのコ
ンシステンシ問題といわれるものであり、各種の解決案
が提案されている。例えば、ライト・ワンス（ｗｒｉｔ
ｅ−ｏｎｃｅ）方式、バークレイ（Ｂｅｒｋｅｌｅｙ）
方式、イリノイ（Ｉｌｌｉｎｏｉｓ）方式、ドラボン（
Ｄｒａｇｏｎ）方式、ファイヤフライ（Ｆｉｒｅｆｌｙ
）方式などがアーチボルド。

バエル（Ａｒｃｈｉｂａｌｄ、　Ｂａｅｒ）他の論文「
キャッシュ・コンシテンシ・プロトコル：マルチプロセ
ッサ・シミュレーションを使った評価」　（“Ｃａｃｈ
ｅＣｏｎｓｉｓｔｅｎｃｙ　Ｐｒｏｔｏｃｏｌｓ：Ｅｖ
ａｌｕａｔｉｏｎ　ｌｏｓｉｎｇ　ａ　Ｍｕｌｔｉｐｒ
ｏｃｅｓｓｏｒ　　Ｓｉｍｕｌａｔｉｏｎ　　、ＡＣＭ
　Ｔｒａｎｓａｃｔｉｏｎｓ　　ｏｎＣｏｍｐｕｔｅｒ
　　Ｓｙｓｔｅｍｓ、Ｖｏｌ、４．Ｎｏ、４．Ｎｏｖ、
１９８６．Ｐａｇｅｓ２７３−２９８）に記載されてい
る。

これらの方式を大別とすると、インバリデート（Ｉｎｖ
ａｌｉｄａｔｅ）方式（以下、ＩＮＶ方式と記す）と、
ブロードキャスト（Ｂｒｏａｄｃａｓｔ）方式（以下・
ＢＣ方式と記す）とに分けられる。ＩＮＶ方式は次のよ
うな方式である。同一データブロックのコピーが複数プ
ロセッサのキャッシュメモリにある場合、それに書き込
みを起こすプロセッサから他のプロセッサへ、そのブロ
ックのインバリデート（無効化）を指令する信号とその
データブロックのアドレスとをバス上へ送出する。他の
プロセッサのバス監視装置は、送出された上記データブ
ロックのアドレスから自キャッシュのタグメモリを参照
して、自キャッシュに同一データブロックがある場合、
そのブロックを無効化して誤ったデータを使わないよう
にする方式である。一方、ＢＣ方式は、書き込みを起こ
すプロセッサが、書き込まれるデータブロックのアドレ
スとデータとをバス上に送出して他のプロセッサに取り
込ませ、他プロセツサにある該データブロックを常に最
新の状態にしてデータの一貫性を保つ方式である。

［発明が解決しようとしている課題］ しかしながら、上述したＩＮＶ方式では、無効化された
ブロックを持つどのプロセッサにおいても、その無効化
されたブロックを再度アクセスしようとした際にキャッ
シュのミスを引きおこし、そのデータを共有メモリ又は
有効なコピーを持ったキャッシュから読み出す必要があ
り、性能が低下する場合があった。一方、ＢＣ方式では
、更新されたデータブロックを逐一全体にブロードキャ
ストするので、そのオーバヘッドが大となる欠点があっ
た。

つまり、更新されたデータが頻繁に多くのプロセッサに
よって使われるソフトウェア・アーキテクチャの場合は
、ＢＣ方式の方が優れ、同じデータがあまり多くのプロ
セッサには使われないソフトウェア・アーキテクチャの
場合はＩＮＶ方式の方が優れているという一長一短があ
った。

本発明は、かかる問題点に鑑みてなされたものであって
、その目的とするところは、あらゆるソフトウェア・ア
ーキテクチャにおいて共有メモリのアクセス及びプロセ
ッサ間のオーバヘッドを考慮に入れて最適なキャッシュ
メモリの制御を行なうキャッシュメモリ制御方法を提供
することである。

［課題を解決するための手段］ この課題を解決するために、本発明のキャッシュメモリ
制御方法は、複数機器がメモリを共有するシステムにお
いて各プロセッサに附属するキャッシュメモリを制御す
るキャッシュメモリ制御方式であって、 各キャッシュメモリの各エントリ毎に、該エントリのデ
ータの無効を指示可能とし、各プロセッサが、システム
バス上に他の機器が発生させるトランザクションを監視
して、無効を指示されたエントリに対応するタグメモリ
のアドレスに一致するアドレスを検知した時には、その
トランザクションにおけるデータ部分を、当該エントリ
のデータとしてバスから取り込むようにする。

ここで、前記無効の指示は、各エントリにおいて、デー
タをバス上の他の機器と共有している共有状態のときに
、バス上の他の機器による当該エントリのデータに対す
る書き込み動作のためにバス上に出された書き込み通知
の信号により実行され、無効を指示されたエントリに対
応したタグメモリのアドレスに一致するアドレスを検知
し、前記トランザクションにおけるデータ部分をバスか
ら取り込んで、該エントリに対応するキャッシュメモリ
へデータとして格納した時に、前記共有状態に遷移する
。

又、前記他の機器は他のプロセッサである。

又、前記他のプロセッサがバスに発生させるトランザク
ションは、当該プロセスサに附属するキャッシュメモリ
の無効を指示されたエントリに関して、該エントリに対
応するタグメモリのアドレスと、主記憶上で同一なアド
レスのブロックのエントリからデータを読み出すために
バスに起こすトランザクションである。

又、システムの初期化の時点で、過去の履歴をもとに主
記憶のアドレスをタグメモリにロードし、各エントリの
状態を前記無効を指示された状態に設定する。

又、システムの初期化の時点で、あらかじめ設定した主
記憶のアドレスをタグメモリにロードし、各エントリの
状態を無効を指示された状態に設定する。

又、システムの初期化の時点で、無作為に設定した主記
憶のアドレスをタグメモリにロードし、各エントリの状
態を無効を指示された状態に設定する。

［作用］ 以上の構成によれば、他のプロセッサなどにより発生し
たバス上のトランザクションを監視し、必要と思われる
データをシステムの動作時間に影響を及ぼさずにキャッ
シュに取り込んで将来の使用に供することができ、シス
テムの動作速度を向上させる。また、ＩＮＶ方式、ＢＣ
方式のコンシステンシ・プロトコルの長所を兼ね備える
ことができるので、より広範なアプリケーションに対し
て有効なキャッシュ制御方式を提供することができる。

［実施例コ 以下、図面を参照して本発明の詳細な説明する。

第１図は本発明のキャッシュ制御方式の状態遷移図の一
例を示す。

本状態遷移図は、イリノイ大学で提案されたキャッシュ
・コンシステンシ・プロトコル（前述の参考文献；　Ａ
ｒｃｈｉｂａｌｄ、Ｊ、　ａｎｄ　Ｂａｅｒ、Ｊ、−Ｌ
、。

”Ｃａｃｈｅ　Ｃｏｎ５ｉｓｔｅｎｃｙ　Ｐｒｏｔｏｃ
ｏｌｓ：Ｅｖａｌｕａｔｉｏｎ　Ｕｓｉｎｇ　ａ　Ｍｕ
ｌｔｉｐｒｏｃｅｓｓｏｒ　Ｓｉｍｕｌａｔｉｏｎ　　
、ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎＣｏｍｐｕ
ｔｅｒ　Ｓｙｓｔｅｍｓ、Ｖｏｌ、４．Ｎｏ、４．Ｎｏ
ｖ、１９８６、　Ｐａｇｅｓ２７３−２９８）に、本発
明の状態（旧共有状態；５ｈａｒｅｄＳｔａ　ｌｅ）を
付加したものである。尚、遷移条件において、リードミ
ス（ｒ−ｏ＋１ｓｓ）とライトミス（ｗ−ｍｉｓｓ）と
はキャッシュ内に所望のデータが無い場合、リートヒツ
ト（ｒ−ｂｉｔ）とライトヒツト（ｗ−ｂｉｔ）はキャ
ッシュ内に所望のデータが有る場合を示す。又、リード
ステイル（ｒ−ｓｔａｌｅ）とライトステイル（ｗ−ｓ
ｔａｌｅ）とは旧共有状態でのリード／ライトである。

又、遷移条件の内、実線矢印で表わしたのは自分の動作
による遷移、破線で表わしたのは他の動作による遷移で
ある。

以下、本実施例では、本発明の旧共有状態（Ｓｈａｒｅ
ｄ　５ｔａｌｅ）の利点を明瞭にする為、リードミスと
リードステイル、ライトミスとライトステイルを分別し
て示しているが、本来これらは同じ条件であり、特に分
別される必要はない。各状態はキャッシュメモリのエン
トリ毎に保持されるもので、通常タグメモリと呼ばれる
制御用のメモリにコード化されて格納される。

１はエントリが無効（Ｉｎｖａｌｉｄ）であることを示
すＩｎｖａｌｉｄ状態（以下、ＩＮＶ状態）である。

システムの初期状態では全エントリがＩＮＶ状態である
。

２はこの状態を持つエントリを持つキャッシュが、その
エントリを占有（Ｅｘｃｌｕｓｉｖｅ）することを示す
Ｅｘｃｌｕｓｉｖｅ状態（以下、ＥＸ状態）である。

ＥＸ状態では、他のキャッシュにはそのエントリのブロ
ックは存在していない。

３はこの状態を持つエントリを持ったキャッシュがその
エントリのブロックを他のキャッシュと共有（Ｓｈａｒ
ｅ）　していることを示す５ｈａｒｅｄ状態（以下、Ｓ
Ｈ状態）である。この時、複数のキャッシュにこのエン
トリのブロックが同一のデータを保持している。

４はこの状態を持つエントリを持つキャッシュがそのエ
ントリを占有し、かつ書き込みを行なって主記憶との一
致がとれなくなった（ＥｘｃｌｕｓｉｖｅＤｉｒｔｙ）
ことを示すＥｘｃｌｕｓｉｖｅ　Ｄｉｒｔｙ状態（以下
、ＥＸＤ状態）である。

５は本発明で導入された旧共有状態で、この状態のエン
トリを持つキャッシュが以前そのブロックを他のプロセ
ッサのキャッシュと共有していた（Ｓｈａｒｅｄ）が、
他のプロセッサによるそのブロックへの書き込みによっ
てそのブロックが古い（Ｓｔａｌｅ）ものになったこと
を示す５ｈａｒｅｄＳｔａｌｅ状態（以下、ＳＨＳ状態
）である。この時、書き込みを行なったプロセッサのキ
ャッシュでは、そのエントリはＥＸＤ状態になっている
。

第２図は本発明を用いるマルチプロセッサのブロック図
の一例を示す。２１，２２，２３゜２４は本発明のキャ
ッシュ制御方式を用いるキャッシュ３１〜３４を持つプ
ロセッサであり、システムバス２５を介して主記憶２６
と接続されている。この構成をもとに、更に具体的に本
キャッシュ制御方式の動作を説明する。尚、本実施例で
は、他のプロセッサの動作に基づく、ＳＨ状態とＳＨ３
状態との間の遷移を中心に述べるが、ＳＨＳ状態からの
、リードステイルによるＳＨ状態への遷移やライトステ
イルによるＥＸＤ状態への遷移等は、従来のＩＮＶ状態
からの遷移に対応して付加されるものであり、本発明の
ＳＨ３状態の付加を最も特徴付ける遷移は上記ＳＨ状態
とＳＨＳ状態間の破線の遷移である。

第３図はある時点での第２図のマルチプロセッサのキャ
ッシュの状態を示す図である。

第３図の（ａ）は、キャッシュ３１，３２゜３３３４に
主記憶２６の同じアドレスのデータ“Ａ”が共有されて
いる状態を示す。今、このデータを保持しているアドレ
スを例えば１０００番地として説明を行なう。キャッシ
ュのタグメモリには、図示しないアドレス情報が格納さ
れており、この場合アドレス情報は１０００番地を示す
。１０００番地のデータ“Ａ”は共有されているので、
各キャッシュのこのデータはＳＨ状態である。

この第３図の（ａ）の状態から、プロセッサ２１がこの
エントリのデータ“Ａ”を更新して“Ａ′”に書き替え
る場合、第３図の（ｂ）に示すようにプロセッサ２１は
、自分のキャッシュにデータ“Ａ′　を書き込んでキャ
ッシュをＥＸＤ状態とする（第１図の遷移条件■に対応
する）と同時に、プロセッサ２１のキャッシュ制御装置
は、キャッシュ３１の“Ａ”のデータがＳＨ状態なので
他に共有するキャッシュがあると判断し、バス２５を通
じて他のキャッシュをＳＨ３状態にする信号とそのアド
レスとを送出する。

各プロセッサのキャッシュ制御装置はバス監視を行なっ
ており、キャッシュをＳＨＳ状態にする信号を受信する
と、その時点のバス上のアドレスを用いて自分のタグメ
モリ内にそのアドレスのエントリがある場合に、そのエ
ントリの状態をＳＨ３状態に書き換える（第１図の遷移
条件■に対応する）。ＳＨ３状態は、過去にそのデータ
が複数のキャッシュによって共有されていたが、現在は
誰かにより書き換えられたため古いデータとなってしま
ったことを示す。従来の技術ではＳＨＳ状態という状態
がなかったため、このエントリはＩＮＶ状態にしていた
。ＳＨ３状態はＩＮＶ状態に似ているが、そのアドレス
のエントリは少なくとも過去にそのプロセッサによって
使用されたという情報を持っていることになる。

この第３図の（ｂ）の状態から、次にプロセッサ２２が
再び１０００番地のデータを処理するために読み出しを
行なおうとすると、タグメモリには１０００番地のエン
トリが入っているが、このエントリはＳＨ５状態なので
そのデータは古いことがわかり、キャッシュミスとして
バス２５上にトランザクションを発生させる（本例では
リードステイルと表現している）。この場合、プロセッ
サ２１のキャッシュ制御装置がそのトランザクションを
監視しているので、キャッシュメモリ３１に存在する有
効なｔｏｏｏ番地のデータ“Ａ′”を主記憶２６に書き
込んでＳＨ状態とする（第１図の遷移条件■に対応する
）。

主記憶２６に書き込む時には、このアドレスとデータと
がバス２５上に出るので、このバストランザクションを
起こす契機を与えたプロセッサ２２はそのデータをバス
上から取り込み、キャッシュのデータを“Ａ′に書き換
えてＳＨ状態とする（第１図の遷移条件■）。

この時、プロセッサ２３．２４のキャッシュ制御装置も
このトランザクションを監視しているので、バス上に出
るアドレス、データを検知することができる。プロセッ
サ２３．２４のキャッシュ制御装置はバス上に出たアド
レスをタグメモリの内容と比較し、この場合各々のキャ
ッシュにある同じアドレスでＳＨＳ状態のエントリの最
新データがバス上に出ていることを検知できるので、こ
のエントリのデータをバス上の最新データ“Ａ′　で更
新してＳＨ状態とする（第１図の遷移条件■）。この動
作は、もともとプロセッサ２１がプロセッサ２２のキャ
ッシュミスに応えて起こしたパストランザクションと並
行して行なわれるので、余分に時間を消費するものでは
ない、この結果、キャッシュの状態は第３図の（Ｃ）の
ように変化し、その後にプロセッサ２３．２４が１００
０番地のデータを処理するために読み出しを行なおうと
した場合には、リードヒツトとなり、余分なパストラン
ザクションを省くことができる。

一方、従来のＩ’　Ｎ　Ｖ方式では第６図のようにＳＨ
Ｓ状態が存在しないため、第３図の（ａ）と同じ第７図
の（ａ）の状態でキャッシュ３１て書き換えがあった場
合には、キャッシュ３２゜３３．３４の１０００番地の
エントリは第７図の（ｂ）のようにＩＮＶ状態とされて
いた（第６図の遷移条件■）　従って、プロセッサ２２
のキャッシュミスによるトランザクションが起っても、
プロセッサ２３．２４の１０００番地のアドレスの内容
はＩＮＶ状態のままになっており、このバストランザク
ションでキャッシュのデータを取り込むことはしない。

この結果、従来の方式では第７図の（ｃ）のように“Ａ
′のコピーはキャッシュメモリ３２にしか送られない。

第７図の（Ｃ）から、例えばプロセッサ２３が１０００
番地をアクセスしたとすると、このアクセスはキャッシ
ュミスになるので、このキャッシュミスを解決するため
には、バスを使ってプロセッサ２１か２２の優先度の高
い方がデータを転送しなければならない。これは余分な
バスサイクルを必要とするのでシステムの処理速度が低
下する。

本実施例によれば、過去に使ったキャッシュのエントリ
が他のプロセッサによる書き込みにより古くなっても、
古くなったデータを持つあるプロセッサが本当に必要に
なった時に起きるキャッシュミスによるデータの転送時
に、他のキャッシュにもデータが取り込まれるので、ヒ
ツト率に関して有利になる。もし、そのエントリが将来
に亙ってどのプロセッサによっても使われないときは、
そのデータは決してアクセスされないのでバスにトラン
ザクションを起こすことなく、然るべき時間のうちにキ
ャッシュ置換アルゴリズムによりキャッシュから消され
るだけであり、このためにシステムの性能を低下させる
ことはない。また、いわゆるＢＤ方式のキャッシュ・コ
ンシステンシ・プロトコルを採用すると、すべての書き
込みに対してアドレスのみでなく変更データもバス上に
出すので、無駄なパストランザクションが多発する危険
があったが、本発明のキャッシュメモリ制御方式によれ
ば、そのブロードキャストを実際に他のプロセッサでデ
ータが必要になった時点で行なうので、そのような無駄
を行なわずにすむ。

次に、本発明の第２の実施例を示す。第１の実施例はコ
ピーバック（ｃｏｐｙ−ｂａｃｋ）　　つまりキャッシ
ュに書き込みがヒツトした時は、データの更新はキャッ
シュ上だけで行ない、主記憶へのデータの書き込みは、
そのエントリがキャッシュから追い出された時や、第１
の実施例のように他のプロセッサによってキャッシュミ
スが起こった時に行なう方式についての例であった。第
２の実施例はライトスルー（ｗｒｉｔｅ−ｔｈｒｏｕｇ
ｈ）　、つまりどのプロセッサによる書き込みであって
もすべて主記憶にも同時に反映させる方式についての例
である。

第４図に第２の実施例の本キャッシュ制御方式を適用し
た状態遷移図を示す。第１の実施例と同様に、Ｉｎｖａ
ｌｉｄ（Ｉ　Ｎ　Ｖ　）状態４１は初期状態であり、す
べてのキャッシュのエントリは無効である。Ｅｘｃｌｕ
ｓｉｖｅ　（Ｅ　Ｘ　）状態４２はあるキャッシュに唯
一主記憶のコピーがある場合である。

５ｈａｒｅｄ　（Ｓ　Ｈ）状態４３は複数のキャッシュ
に同一の番地のコピーが存在する場合である。

５ｈａｒｅｄ　５ｔａｌｅ　（Ｓ　ＨＳ　）状態４５は
共有されていたエントリが他のプロセッサからの書き込
みによって古くなった状態である。第２の実施例では、
第１図にあった、書き込みによりキャッシュと主記憶が
不一致になった状態であるＥｘｃｌｕｓｉｖｅＤｉｒｔ
ｙ　（Ｅ　Ｘ　Ｄ　）状態４は存在しない。

本実施例では、ＳＨＳ状態への遷移は、（１）唯一の主
記憶のコピーを持っていたキャッシュにおいて、他のプ
ロセッサの同じエントリのブロックへのライトミス（ラ
イトステイル）により、そのエントリのデータの内容が
古くなった場合と、（２）複数のプロセッサがキャッシ
ュに主記憶のコピーを共有している時、その内の１つの
プロセッサによるライトヒツト、またはそのエントリの
データをキャッシュに持たない別のプロセッサによるラ
イトミスが起こり、他のプロセッサのキャッシュでその
エントリのデータの内容が古くなった場合とに、発生す
る。

ＳＨ３状態になったキャッシュを持つプロセッサがその
エントリのデータをアクセスする必要が生じ、リードス
テイルとしてバス上にトランザクションを出した時、あ
るいはそのエントリのデータを持たないプロセッサがリ
ードミスとしてトランザクションを出した場合に、第１
の実施例と同じように、アクセスされようとしているブ
ロックのエントリがＳＨ３状態である他のキャッシュは
、リードミスあるいはリードステイルを起こしたキャッ
シュのデータ読み出しを監視し、自分のキャッシュのブ
ロックデータも最新のものに更新する。この場合も全て
のキャッシュの同じブロックで更新が同時に起こるので
、後から繰り返し同じブロックを読み出す必要がなくな
り、第１の実施例と同様にシステムの高速化に貢献する
ところ大である。

次に、第３の実施例を説明する。第３の実施例では、第
５図に示すように第２の実施例からＩｎｖａｌｉｄ　（
Ｉ　Ｎ　Ｖ　）状態を取り去ったものである。

第２の実施例では、ＩＮＶ状態はシステムの初期状態で
のみ必要であるので、これをＳＨ３状態に書き換えるこ
とが可能である。これまでは、ＳＨ３状態は、そのブロ
ックのデータは現在無効であるが、かつてそのブロック
のデータがキャッシュに入れられたことがあるという履
歴を示していた。システムに電源を入れた初期状態では
、厳密にいえばどのキャッシュのエントリも使われた履
歴はないのであるが、磁気ディスクなどの不揮発性の記
憶手段に以前に使用した時のキャッシュの履歴を記録し
ておき、システムの初期化の時点でタグメモリに過去の
履歴で最も゛もっともらしい°履歴を書き込んでおけば
、他のプロセッサによるバストランザクションで、使用
する可能性の高いデータを、他のプロセッサの動作を遅
延させずに最初からキャッシュに読み込むことができる
。

また、第５図ではＥＸ状態がなくなっているが、ＥＸ状
態は唯一のキャッシュに主記憶のコピーがある状態を示
していたので、ＳＨ状態の意味を拡張して、１つ以上の
キャッシュに主記憶のコピーがあるとしておけば良い、
このＳＨとＳＨ３の２状態の状態遷移では、初期化の時
点ではシステムがキャッシュのタグメモリを適当な履歴
でロードし、そのプロセッサが実際にリードミス（リー
ドステイル）を起こしてそのブロックをバスから取り入
れればＳＨ状態に移行させる。

他のプロセッサによって、ＳＨ３状態にあるブロックが
バス上から取り込まれようとする時は、そのデータを同
じくバス上から取り入れてキャッシュにロードしておく
ことにより、高いヒツト率を得ることができる。

なお、本発明はここに挙げた実施例の他にも種々変形し
て用いることが可能である。例えば、キャッシュのエン
トリを持つタグメモリがプロセッサからのキャッシュの
アクセスとバス側からの監視のためのアクセスとで共有
されるような場合や、ＳＨＳ状態にあるエントリを持つ
タグメモリがたまたまその最新データがバス上にあるに
も拘らず、プロセッサ側からのアクセスで占有されてい
るような場合は、そのキャッシュのエントリはバスのデ
ータを取り込まずにＳＨＳ状態のままにしておいてもキ
ャッシュのコンシンテンシは保たれる。こうすることで
、バス上にトランザクションを起こしたプログラムを待
たせずに処理を進めることが可能である。また、メモリ
空間のある範囲だけ本キャッシュメモリ制御方法を実施
し、他の部分は従来の技術のキャッシュメモリ制御方式
を適用することも可能である。要するに、本発明はその
技術思想を逸脱しない範囲で種々で変形して実施するこ
とが可能である。

［発明の効果］ 本発明により、あらゆるソフトウェア・アーキテクチャ
において共有メモリのアクセス及びプロセッサ間のオー
バヘッドを考慮に入れて、最適なキャッシュメモリの制
御を行なうキャッシュメモリ制御方法を提供できる。

すなわち、本発明はかつて使用したデータが無効となっ
た旧共有（Ｓｈａｒｅｄ　５ｔａｌｅ）状態をキャッシ
ュのエントリの状態の１つとして持たせ、以前キャッシ
ュに存在していたが他のプロセッサの書き込みによって
古くなったデータを、同じデータが他のプロセッサによ
り読まれる際にキャッシュにロードしておくことにより
、いわゆるインバリデート方式のキャッシュ・コンシス
テンシ・プロトコルの持つキャッシュの書き込み時の効
率上の利点と、ブロードキャスト方式の持つ高いヒツト
率の利点を兼ね備えたキャッシュメモリ制御方式を実現
した。

【図面の簡単な説明】

第１図は本発明の第１の実施例の状態遷移図を表す図、 第２図は本発明が適用される対象となるマルチプロセッ
サの構成例を示す図、 第３図は本発明の説明のためのキャッシュの内容を示す
図、 第４図は本発明の第２の実施例の状態遷移図を表す図、 第５図は本発明の第３の実施例の状態遷移図を表す図、 第６図は従来の状態遷移図を表す図、 第７図は第３図に対ｚして従来のキャッシュの内容を示
す図である。 図中、１　・−Ｉｎｖａｌｉｄ状態、２”−Ｅｘｃｌｕ
ｓｉｖｅ状態、３　・＝　５ｈａｒｅｄ状態、４−　Ｅ
ｘｃｌｕｓｉｖｅ　Ｄｉｒｔｙ状態、５−３ｈａｒｅｄ
　５ｔａｌｅ状態、２１〜２４−・・プロセッサ、２５
・・・バス、２６・・・主記憶、３１・・・プロセッサ
２１のキャッシュ、３２・・・プロセッサ２２のキャッ
シュ、３３・・・プロセッサ２３のキャッシュ、３４・
・・プロセッサ２４のキャッシュ、４１−Ｉｎｖａｌｉ
ｄ状態、４２　・Ｅｘｃｌｕｓｉｖｅ状態、４３−・５
ｈａｒｅｄ状態、４５−３ｈａｒｅｄ　５ｔａｌｅ状態
、５３−３ｈａｒｅｄ状態、５５−５ｈａｒｅｄ　５ｔ
ａｌｅ状態である。

Claims (7)

【特許請求の範囲】
1. （１）複数機器がメモリを共有するシステムにおいて各
   プロセッサに附属するキャッシュメモリを制御するキャ
   ッシュメモリ制御方式であつて、各キャッシュメモリの
   各エントリ毎に、 該エントリのデータの無効を指示可能とし、各プロセッ
   サが、システムバス上に他の機器が発生させるトランザ
   クションを監視して、無効を指示されたエントリに対応
   するタグメモリのアドレスに一致するアドレスを検知し
   た時には、そのトランザクションにおけるデータ部分を
   、当該エントリのデータとしてバスから取り込むように
   することを特徴とするキャッシュメモリ制御方式。
2. （２）前記無効の指示は、各エントリにおいて、データ
   をバス上の他の機器と共有している共有状態のときに、
   バス上の他の機器による当該エントリのデータに対する
   書き込み動作のためにバス上に出された書き込み通知の
   信号により実行され、 無効を指示されたエントリに対応したタグメモリのアド
   レスに一致するアドレスを検知し、前記トランザクショ
   ンにおけるデータ部分をバスから取り込んで、該エント
   リに対応するキャッシュメモリへデータとして格納した
   時に、前記共有状態に遷移することを特徴とする請求項
   第１項記載のキャッシュメモリ制御方式。
3. （３）前記他の機器は他のプロセッサであることを特徴
   とする請求項第１項又は第２項記載のキャッシュメモリ
   制御方式。
4. （４）前記他のプロセッサがバスに発生させるトランザ
   クションは、当該プロセスサに附属するキャッシュメモ
   リの無効を指示されたエントリに関して、該エントリに
   対応するタグメモリのアドレスと、主記憶上で同一なア
   ドレスのブロックのエントリからデータを読み出すため
   にバスに起こすトランザクションであることを特徴とす
   る請求項第３項記載のキャッシュメモリ制御方式。
5. （５）システムの初期化の時点で、過去の履歴をもとに
   主記憶のアドレスをタグメモリにロードし、各エントリ
   の状態を前記無効を指示された状態に設定することを特
   徴とする請求項第２項記載のキャッシュメモリ制御方式
   。
6. （６）システムの初期化の時点で、あらかじめ設定した
   主記憶のアドレスをタグメモリにロードし、各エントリ
   の状態を無効を指示された状態に設定することを特徴と
   する請求項第２項記載のキャッシュメモリ制御方式。
7. （７）システムの初期化の時点で、無作為に設定した主
   記憶のアドレスをタグメモリにロードし、各エントリの
   状態を無効を指示された状態に設定することを特徴とす
   る請求項第２項記載のキャッシュメモリ制御方式。