JPH0625984B2 - マルチプロセツサ・システム - Google Patents

Description

【発明の詳細な説明】

以下の順でこの発明を説明する。 Ａ．産業上の利用分野 Ｂ．従来の技術 Ｃ．産業上の利用分野 Ｄ．問題点を解決するための手段 Ｅ．実施例 Ｅ１．実施例の構成（第１図〜第４図） Ｅ２．実施例の動作（第１図〜第４図） Ｅ３．実施例の有効性（第５図〜第１０図） Ｆ．発明の効果 Ａ．産業上の利用分野 この発明は複数のプロセッサがプライベート・キャッシ
ュを介して共有バスおよび共有メモリに接続されている
マルチプロセッサ・システムに関し、とくに各プライベ
ート・キャッシュ側に制御装置を設け共有バス上の信号
を監視することによってプライベート・キャッシュにお
けるデータの操作、たとえばプライベート・キャッシュ
間のデータの一貫性を維持する操作を行う、いわゆるス
ヌープ・キャッシュを有するマルチプロセッサ・システ
ムに関する。 Ｂ．従来の技術 複数台のプロセッサがそれぞれプライベート・キャッシ
ュを持ち、共有バスによって相互接続される密結合マル
チプロセッサ・システムが提案され、実用化されつつあ
る。 複数のプロセッサは、同じく共有バスに接続される共有
メモリをリード・ライトする。もし、プライベート・キ
ャッシュが無い場合を考えると、各プロセッサの発生す
る共有メモリへのリード・ライトはすべて共有バスを介
して行なわれる。そのため共有バスの使用率が高くな
り、プロセッサの台数を増やしてもシステムの性能はあ
る限界以上に向上しない。 そこで各プロセッサにプライベート・キャッシュを搭載
することによって、共有メモリ内データの一部をコピー
をキャッシュ・メモリに持ち、データのリード・ライト
をキャッシュ内で処理して、共有バスと共有メモリをで
きるだけ使わずに済ませる方式がある（マルチキャッシ
ュ・システム）。ところで、この方式では、各プロセッ
サがそれぞれのキャッシュ内で、同じアドレスのデータ
を勝手に書き替えてしまうと、同一時刻に同一アドレス
のデータが異なる値をとる可能性が生じる。そして同一
時刻、同一アドレスのデータ間で値が異ならないように
する工夫が必要であった。ここで、どのプロセッサから
見ても同じアドレスには同じ値が入っているように見え
ることをデータの一貫性（コンシステンシ）と呼ぶ。 一貫性を保証するひとつの方法としてスヌープ・キャッ
シュ方式がある。スヌープ・キャッシュ方式は、各プロ
セッサのキャッシュ制御装置は共有バスを常時監視する
ことによって、キャッシュ間の一貫性を保つものであ
る。即ち、あるプロセッサが自分のキャッシュ内にある
データを更新するとき、他のプロセッサのキャッシュに
もそのコピーがあると、どのアドレスのデータをどう書
き替えたかという情報を共有バス上の流す。他のプロセ
ッサのキャッシュ制御装置はそれを見て、自分のキャッ
シュ内にあるデータを更新（アップデート）するか、も
しくは無効化（インバリデート）することによって一貫
性を保つ。 従来のスヌープ・キャッシュ方式では、共有データに対
する書き込みが起こったとき、他のキャッシュに存在す
るコピーを更新するか無効化するか、どちらか一方の方
式をとっていた。以後、更新する方式をアップデート方
式、無効化する方式をインバリデート方式と呼ぶことに
する。例えば、米国ゼロックス社のＤｒａｇｏｎ（“Th
e Dragon Processor”，Proceedings of Second Intern
ational Conference on ASPLOS,1987,pp.65-69,R.R.Atk
inson他）や米国デジタル・イクイップメント社のＦｉ
ｒｅＦｌｙ（“Firefly:a Multiprocessor Workstatio
n”，Proceedings of Second International Conferenc
e on ASPLOS,1987,pp.164-172,C.P.Thacker他）はアッ
プデート方式、カリフォルニア大学のＳＰＵＲ（“Desi
gn Decision in SPUR”，IEEE computer,pp.8-22,1986,
Nov.,M.Hill他）はインバリデート方式を用いている。
また本出願人は、アップテート方式とインバリデート方
式とをプログラムで選択的に切り換えることができるよ
うに設計されたマルチプロセッサについてすでに出願し
ている（特願平１−４７９９号、平成１年１月１３
日）。 ところで、この２方式は、複数のキャッシュ間の一貫性
を保つという意味では等価で、キャッシュ内でデータを
更新（アップデート）しても無効化（インバリデート）
しても一貫性上はかまわないが、性能という観点からは
一長一短がある。 まずアップデート方式は、複数のプロセッサが、非常に
密に共有するデータ（共有しているプロセッサの当該デ
ータに対するアクセス頻度にあまりばらつきがない）を
扱うのに適している。つまり、密に共有するデータに対
してインバリデート方式を用いると、１台のプロセッサ
がその領域をライトするたびに他のキャッシュ内のコピ
ーを無効化していまい、他のキャッシュがその領域をリ
ード・ライトするときに必ずキャッシュ・ミスになって
共有バスにアクセスが必要となる。その点アップデート
方式では、コピーを持つキャッシュすべてが同時に更新
されるので、共有バスを使うことなく当該データを読む
ことができる。例えば、一般的にアップデート方式は、
生産者−消費者モデルの並列プログラムに用いられるバ
ッファや、プロセッサ間の同期に使われるセマフォアな
どに適している。 他方、インバリデート方式は、ある１台のプロセッサで
排他的に使用されるデータや他のプロセッサによるアク
セスがあまり発生しない共有データに応用するのが望ま
しい。本来、ある１台のプロセッサにおいて専有されて
いたデータであるにもかかわらず、ページングやプロセ
ス・マイグレーションによって見かけ上共有データにな
ってしまった場合には、不要な共有データがシステム中
に残ることになり、性能低下の原因となる。このような
環境ではインバリデート方式が有効に働く。 ゆえに、どちらの方式をとるのが望ましいかは一概に決
まらず、実行されるプログラムの性質や個々のプロセッ
サの動作状況に依存する。いろいろなデータアクセスの
状況において、いつも良い性能を提供するプロトコルは
実現困難であった。 前述のＤｒａｇｏｎ、ＦｉｒｅＦｌｙ、ＳＰＵＲはどち
らか一方の方式のみ実現されている。したがって場合に
よっては好ましい性能を提供できない。また、特願平１
−４７９９号の発明では上記の２方式を選択的に切り換
えることができるようにっているが、ソフトウェアで２
方式を制御している。したがってどのように切替るかの
問題が残っており、その態様によっては十分な性能を引
きだせない場合も考えられる。 なお本出願人はキャッシュ・プロトコルをワーキング・
セット情報に基づいて自動的に切り換える手法について
すでに出願している（平成２年１月１６日、特願平２−
４６６８）。 Ｃ．発明が解決しようとする問題点 この発明は以上の事情を考慮してなされたものであり、
インバリデート方式とアップデート方式との２つのプロ
トコルを動的に最適に切り換える制御機構を提供するこ
とを目的としている。これにより、共有バスのトラフィ
ックを減少させ、システムの性能を向上させることがで
きる。 Ｄ．問題点を解決するための手段 この発明では以上の目的を達成するために、各プライベ
ート・キャッシュの各共有データについて採用するプロ
トコルを、当該プライベート・キャッシュに対応するプ
ロセッサが当該共有データをアクセスする可能性ないし
は頻度と、対応するプロセッサ以外のプロセッサが当該
共有データをアクセスする可能性ないしは頻度とに基づ
いて自動的に切換るようにする。 プロトコルがインバリデート型とアップデート型の例で
は、当該プライベート・キャッシュに対応するプロセッ
サが当該共有データをアクセスする可能性が大きくなれ
ばなるほどアップデート型のプロトコルを採用する方
が、キャッシュ・ヒットを増大させるうえで好ましい。
また対応するプロセッサ以外のプロセッサが当該共有デ
ータをアクセスする可能性が大きくなければなるほどイ
ンバリデート型のプロトコルを採用する方が、共有デー
タの更新手続き用のバス・トラフィックを減ずる上で好
ましい。 具体的な例では、各プライベート・キャッシュの各共有
データについて、当該プライベート・キャッシュに対応
するプロセッサが当該共有データをアクセスした頻度
と、対応するプロセッサ以外のプロセッサが当該共有デ
ータを更新書込みしたことを示す信号が共有バスに送出
された頻度との差を求め、この値を所定の基準値と比較
し、この比較結果に基づいて、当該プライベート・キャ
ッシュの当該共有データで採用するプロトコルを自動的
に切換るようにする。 Ｅ．実施例 Ｅ１．実施例の構成 以下この発明の実施例を説明する。 第１図はマルチプロセッサ・システムの全体図である。
この図において、複数のプロセッサP1、P2、・・、Pnがキ
ャッシュC1,C2、・・、Cnを経由して共有バス１および共
有メモリ２に接続されている。これらのキャッシュC1、C
2、‥、Cnは、プロセッサP1、P2、・・、Pnの平均メモリ・
アクセススピードをはやめるだけでなく、共有バス１の
信号をモニタ（以後これをスヌープと呼ぶ）することに
より、キャッシュC1、C2、‥、Cn相互間の一貫性を保つ機
能を持っている。 各キャッシュＣは第２図のように構成される。この第２
図においてキャッシュ制御部３は、キャッシュＣがプロ
セッサＰからアクセスされたとき、およびバス１のスヌ
ープを行うときのキャッシュＣ全体の基本的な制御を行
う。キャッシュ・データ・メモリ４は、主記憶（共有メ
モリ２）の一部のコピーを記憶する高速なメモリであ
る。このキャッシュ・データ・メモリ４はたとえば６４
ビットのデータ・ブロックを１６Ｋ個記憶できる。プロ
セッサＰはほとんどの場合、主記憶にアクセスすること
なく、このデータ・メモリ４から必要なデータの読み書
きができる（データのアクセスはデータ・ブロック単位
で行なわれる）。このため、プロセッサＰの平均メモリ
・アクセスが速くなる。キャッシュ・タグ・メモリ５は
キャッシュ・データ・メモリ４にストアされているデー
タ・ブロックの各々のために第３図に示すようなキャッ
シュ・タグをストアする。キャッシュ・タグは後に詳述
するようにＶ，Ｓ，Ｄ，アクセス・カウントおよびアド
レス情報の各フィールドからなる。基準値レジスタ６は
キャッシュ・タグ・メモリ５にストアされているキャッ
シュ・タグのアクセス・カウントに関連して基準値をス
トアするものである。比較器７はアドレス情報で特定さ
れたキャッシュ・タグのアクセス・カウントを基準値レ
ジスタ６の基準値に比較しその比較結果をキャッシュ制
御部３に供給する。 つぎにキャッシュ・タグについて説明する。 第３図に示すようにキャッシュ・タグはＶ，Ｓ，Ｄ，ア
クセス・カウントおよびアドレス情報の各フィールドか
らなる。アドレス情報は当該キャッシュ・タグが対応す
るデータ・ブロックで用いるのと同じアドレスである。
Ｖ，ＳおよびＤはそれぞれ有効フラグ、共有フラグおよ
びデーティ・フラグであり、アドレス情報で特定される
データ・ブロックがそれぞれつぎのような状態であるこ
とを示す。 Ｖ：有効フラグ ０：無効 １：有効 Ｓ：共有フラグ ０：専有 １：共有 Ｄ：ダーティ・フラグ ０：クリーン（共有メモリと同一内容） １：ダーティ（共有メモリと異なる内容） アクセス・カウントは所定ビットのアップダウン・カウ
ンタをなすものであり、その管理方法については後述す
る。 つぎにキャッシュ・データ・メモリ４のデータ・ブロッ
クの状態について説明する。なおキャッシュ制御部３は
個々のデータ・ブロックをこれら状態およびアクセス・
カウントに基づいて管理する。またデータ・ブロックの
状態の遷移についてはのちに実施例の動作との関連で詳
述する。 第４図に示すようにキャッシュ・データ・メモリ４の個
々のデータ・ブロックの状態はつぎの５とおりである。 （１）無効 （２）クリーン専有：システム内における唯一のコピー
であり、共有メモリと同じ値を保持している。 （３）クリーン共有：システム内に複数のコピーが存在
する可能性があり、リプレースに対してライト・バック
の必要はない。 （４）ダーティ専有：システム内における唯一のコピー
であるが、共有メモリとは違うデータの値を保持してい
る。リプレースに対してライト・バックしなければなら
ない。 （５）ダーティ共有：システム内に複数のコピーが存在
する可能性があり、リプレースに対してタイト・バック
しなければならない。 上述の５つの状態は第３図に示すキャッシュ・タグ内の
３つのフラグによって管理され、その対応関係は表１に
示されるとおりである。なお、表中のＸは「無意味」を
表す。 つぎにアクセス・カウントの管理方法について説明す
る。 通常、スヌープ・プロトコルでは、キャッシュ・タグの
中にＤ（ダーティ）フラグ、Ｓ（共有）フラグおよびＶ
（有効）フラグの３ビットを付加することによって、デ
ータ・ブロックの状態が管理される。 この実施例では、これらのフラグに加えて、アクセス・
カウント・フィールドが付加される（第３図）。前述の
基準値レジスタ６とこの追加されたフィールドの値の関
係によって、キャッシュ中の共有コピー（クリーン共有
あるいはダーティ共有状態）に対する制御方式が最適化
される。すなわち、本アクセス・カウント、フィールド
は、正の値のみ保持するカウンタであり、つぎのような
規約で、増加，減少される。 アクセス・カウントの規約 （１）バスライトが生じるたびに、１だけ増加される。
ただし、所定値Ｍを超えない。 （２）自分自身のプロセッサからのアクセスが生じる毎
に、１だけ減少される。但し、０以下にはならない。 要約するならば、本アクセス・カウント・フィールド
は、当該ブロックに対して発生したバスからのライト要
求と自プロセッサＰからのアクセス要求の数の差を保持
する。 そして、本フィールドの値がある基準値（Ｍ）に達して
いる状態を以下の説明中では、“Ｒ（Ｒｅａｃｈｅ
ｄ）”状態と表記する（具体的には、アクセス・カウン
ト・フィールドの値＝Ｍレジスタの値）。Ｍは第２図に
示した基準値レジスタ６に保持され、プログラムによっ
てその値を書き替えることも可能である。 キャッシュ制御部３は、Ｒ状態のときにはインバリデー
ト型プロトコルのごとく動作し、Ｒ状態（Ｒ状態でな
い）のときには、アップデート型プロトコルのごとく動
作する。基準値（Ｍ）が“０”の場合は通常のインバリ
デート型プロトコルとなるし、基準値（Ｍ）が、無限大
（実際にはアクセス・カウント・フィールドのビット幅
の物理的制約より不可能）のときには、通常のアップデ
ート型プロトコルとして動作する。 基準値（Ｍ）が、いくつかのときに最適なキャッシュ性
能が得られるかは、キャッシュの構成（ブロック・サイ
ズ、プロセッサＰのアクセス幅）、バス使用時のペナル
ティ（バスリードとバスライトのサイクル比）、システ
ムを構成するキャッシュの数などに依存する。これにつ
いては後に検討する。 Ｅ２．実施例の動作 第４図の状態遷移図を用いてこの実施例の動作を説明す
る。 キャッシュ制御部３はプロセッサＰからのアクセスおよ
びバス１からのスヌープが発生するたびにキャッシュ・
タグを参照し、動作を決定する。それと同時に、アクセ
ス・カウント、フィールドの値と基準値レジスタ６の値
を比較器７によって比較し、Ｒ状態かどうかを判断す
る。 前述のようにデータ・ブロックは５つの状態で管理され
る。ＣＨ（Ｃａｃｈｅ−Ｈｉｔ）信号線１ＣＨはキャッ
シュ間のブロックの専有・共有の状態を示すために、バ
ス１上に設けられている特別の信号線である。バス１か
らキャッシュ制御部３にリードもしくはライトが入り、
自分のキャッシュＣ内にそのコピーを持っているときは
このＣＨをアサートし、要求元のキャッシュＣに自分が
そのコピーを保持していることを知らせる。これら５つ
の状態自体は、特願平１−４７９９号で用いているアッ
プデート型プロトコルのそれらと基本的には同じであ
る。 この実施例にユニークな点は、これら５つの状態の間の
状態遷移の方法と、その状態遷移のために用いるキャッ
シュ・タグ中のアクセス・カウント・フィールドが付加
されていることである。第３図に示すように、この実施
例のキャッシュ・タグは通常のキャッシュＣで用いられ
るアドレス情報の他に有効、共有、ダーティの３つのフ
ラグとアップダウン・カウンタとして動作するアクセス
・カウント・フィールドから構成される。 各遷移が生じる条件と、そのときに行なう動作は以下の
ようである。 ◆遷移１《無効→クリーン専有》 自プロセッサＰがリード動作を行ない、自分のキャッシ
ュＣの中にコピーがなく、キャッシュミスを起こした。
さらに、ＣＨ信号がアサートされないため他のキャッシ
ュＣに同じコピーが存在せず、システム内で唯一自分だ
けがコピーを持っている。 ◆遷移２《無効→クリーン共有》 自プロセッサＰがリード動作を行ない、自分のキャッシ
ュＣの中にコピーがなくキャッシュミスを起こした。さ
らに、ＣＨ信号がアサートされたため他のキャッシュＣ
に同じコピーが存在している。 ◆遷移３《クリーン共有→クリーン専有》 自プロセッサＰがライトを行ない、キャッシュヒットし
た。他のどのキャッシュＣもＣＨ信号をアサートしてい
ないので、このブロックを専有状態に変更する。 ◆遷移４《クリーン専有→ダーティ専有》 自プロセッサＰがライトを行ない、キャッシュヒットし
た。システム内では自分だけそのコピーを持っているの
で、そのコピーを他のキャッシュＣに伝えることなく書
き替えてよい。その結果、共有メモリ２と異なる内容を
保持するのでブロックの状態をダーティに変更する。 ◆遷移５《ダーティ専有→ダーティ専有》 自プロセッサＰがライトを行ない、キャッシュヒットし
た。システム内では自分だけそのコピーを持っているの
で、そのコピーを書き替える。 ◆遷移６《クリーン専有→クリーン共有》 他プロセッサＰがリードミスを起こし、共有バス１上に
リードが発生した。自分はそのコピーをシステム内でた
だひとり持っていたが、他のキャッシュＣに同じコピー
が置かれることになったので、ＣＨ信号をアサートして
共有の状態に遷移する。 ◆遷移７《ダーティ専有→ダーティ共有》 他プロセッサＰがリードミスを起こし、共有バス１上に
リードが発生し、自分はそのコピーをシステム内でただ
ひとり持っており、かつ共有メモリ２とは違った最新の
値を保持しているので、他のキャッシュＣにその最新の
データを供給し、ＣＨ信号をアサートして共有の状態に
遷移する。 ◆遷移８《ダーティ共有→ダーティ共有》 他プロセッサＰがリードミスを起し、共有バス１上にリ
ードが発生した。自分はそのコピーの最新値を保持して
いるので、要求元キャッシュＣにそのデータを供給し、
ＣＨをアサートする。 ◆遷移９《クリーン共有→無効》 バスライト要求がクリーン共有状態のブロックに対して
生じた。かつ、本ブロックはアクセス・カウント・フィ
ールドがＲ状態であるので、本ブロックをインバリデー
トし、ＣＨのアサートは行なわない。 ◆遷移１０《クリーン共有→クリーン専有》 自プロセッサＰがライトヒットした。他のキャッシュＣ
にもコピーが存在する可能性があるので、共有バス１上
にライト要求を出力する。同時に共有メモリ２を更新す
る。結果として、他のどのキャッシュＣもＣＨをアサー
トしなかったので、状態をクリーン専有に変更する。ア
クセス・カウント・フィールドを０に初期化する。 ◆遷移１１《ダーティ共有→無効》 バスライト要求がダーティ共有状態のブロックに対して
生じた。かつ、本ブロックはＲ状態であるので、本ブロ
ックをインバリデートし、ＣＨのアサートは行なわな
い。 ◆遷移１２《ダーティ共有→クリーン共有》 本遷移は次の２つの条件で生じる。 （１）自プロセッサＰがライトヒットした。他のキャッ
シュＣにもコピーが存在する可能性があるので、共有バ
ス１上にライト要求を出力する。同時に共有メモリを更
新する。結果として、他のキャッシュＣによってＣＨが
アサートされたので、状態をクリーン共有に変更する。
アクセス・カウント・フィールドを１だけ減少する。 （２）バスライト要求がダーティ共有状態のブロックに
対して生じた。かつ、本ブロックは、Ｒ状態であるの
で本ブロックの更新を行ない、状態をクリーン共有に変
更する。アクセス・カウント・フィールドを１だけ増加
する。 ◆遷移１３《クリーン共有→クリーン共有》 本遷移は次の３つの条件で生じる。 （１）自プロセッサＰがライトヒットした。他のキャッ
シュＣにもコピーが存在する可能性があるので、共有バ
ス１にライト要求を出力する。同時に共有メモリに更新
する。結果として、他のキャッシュＣによってＣＨがア
サートされたので、状態の変更は行なわない。アクセス
・カウント・フィールドを１だけ減少する。 （２）バスリード要求が生じた。 （３）バスライト要求が生じた。かつ、本ブロックは、
Ｒ状態であるので、本ブロックの更新を行ない、ＣＨ
をアサートする。アクセス・カウント・フィールドを１
だけ増加する。 上記状態遷移では、自プロセッサＰよりのリードヒット
に関する記述は、説明の簡略化の目的より省略した。自
プロセッサＰよりのリードヒットに対しては、何らの状
態遷移も生じないことは自明である。但し、共有状態の
ブロックに対するリードヒットの際には、アクセス・カ
ウント・フィールドが減少される。 Ｅ３．実施例の有効性 前述の様に、本発明の動作の特徴は共有データの取り扱
いにある。あるプロセッサＰが共有データを書き替えよ
うとするとき、他のキャッシュＣに存在するコピーをア
ップデートもしくはインバリデートして一貫性を保つ。 本発明の方式では、共有データはキャッシュＣ内にクリ
ーン共有，ダーティ共有のいずれかの状態で存在する。
その意味では、通常のスヌーププロトコルと同じである
が、共有データに対するオーバヘッドを最小化するため
に、アクセス・カウント・フィールドがキャッシュ・タ
グ中に付加され、共有状態のブロックはこのフィールド
がある基準値（Ｍ）に達しているか否かを示すＲ属性が
追加される。あるプロセッサＰが共有データにキャッシ
ュヒットし、バスライト要求を発生した時、他のキャッ
シュＣ中の共有コピーは、Ｒ状態ならばアップデート
される。そして、アップデートが生じたことを記録する
為に、アクセス・カウントは１だけ増加される（第５
図）。一方、Ｒ状態の共有コピーはインバリデートされ
る（第６図）。また、共有コピーに対して自プロセッサ
Ｐよりアクセスが生じた時には、アクセス・カウントは
１だけ減少される（第７図）。即ち、キャッシュＣ内の
ある共有ブロックに対する他のプロセッサＰよりのアッ
プデートの回数と、自プロセッサＰよりのアクセスの回
数の差がある基準値（Ｍ）に達したかどうかによって、
当該ブロックをアップデートするのか、インバリデート
するのかが自動的に決定される。 基準値（Ｍ）が、“１”の場合、その動作により明確で
あり、次のようになる。即ち、キャッシュＣ内のある共
有ブロックが他のプロセッサＰによってアップデートさ
れた後、一度も自分のプロセッサＰからアクセスされる
ことなく再びアップデートされようとした場合に、その
ブロックはインバリデートされる。逆に、他のプロセッ
サＰからのアップデート要求と次のアップデート要求の
間に一度でも自プロセッサＰからアクセスされたならば
そのブロックはキャッシュＣ内に生き残る。 この実施例の動作および有効性をまとめると、つぎのよ
うになる。共有データであって、しかも複数台のプロセ
ッサＰから頻繁に読み書きされるものに関しては、従来
のアップデート方式と同じく動作する。即ち、共有デー
タにライトアクセスが発生したときは、複数のキャッシ
ュＣに保持されているコピーをインバリデートすること
なしに即座にアップデートする（第８図）。しかし、本
来共有データであっても、１台のプロセッサＰからしか
頻繁にアクセスされないデータに対しては、その頻繁に
アクセスするプロセッサＰのキャッシュＣにだけそのコ
ピーを残し、他のキャッシュＣ内のコピーはインバリデ
ートしてしまう（第９図）。すると、インバリデートし
たあとは他のキャッシュＣにコピーがないので、自分の
キャッシュＣ内だけで処理できる（第１０図）。 以上説明の通り、この実施例のスヌープキャッシュＣ
は、ある時点で本当の共有データとして、複数のキャッ
シュＣ上にコピーが存在する方が望ましいときには、ア
ップデート方式と同じ動作をする。また、本来共有しな
くてもよいデータ、もしくは長い目で見れば共有データ
ではあるが、ある時点ではひとつのプロセッサＰが専有
してリード・ライトした方が性能的に望ましい場合はイ
ンバリデート方式として動作する。 アップデート方式とインバリデート方式切り換えの境目
を決定するＭの値の最適値は、プロセッサＰ、キャッシ
ュＣのブロックサイズ、プログラムのリード・ライトの
パターンなどに依存し、一概には決められない。そこ
で、ここではキャッシュＣのブロックサイズとプログラ
ムの性質を仮定し、Ｍの値のシステムに対する影響を明
らかにする。 以下に、例を挙げて考える。 （１）プログラムは生産者−消費者モデルを考える。生
産者はあるデータ構造を次々と作り出し、共有メモリ上
に実現されたデータバッファに書き込む。消費者はデー
タバッファからデータ構造を読み込んで何らかの処理を
する。生産者と消費者はそれぞれ別のプロセッサＰに割
り付けられている。 （２）生産者、消費者のデータアクセスは１ワードずつ
行なわれる。 （３）キャッシュＣのブロックサイズは８ワードとす
る。 （４）共有バス１はキャッシュＣの１ブロック８ワード
を１サイクルで転送する。 （５）キャッシュＣのインバリデートを行うときは共有
バス１を１サイクル使用する。 以上の仮定の下で２通りの状況を想定し、共有バス１の
使用サイクル数でシステムの性能を評価する。即ち、使
用サイクル数が少ないほど性能が良いものとする。

【状況１】まず、生産者が８ワード分のデータを作り出
し、キャッシュＣに書き込み、消費者がその８ワードの
データを読み込んで処理する場合を考える（一つのデー
タ構造が８ワードから成っていると考えてもよい）。Ｍ
＝０のときはインバリデート方式と同じように動作する
ので、生産者が８ワードの最初のワードを書き込んだと
きに消費者のもつキャッシュＣのブロックがインバリデ
ートされる。このとき、バス１が１サイクル使われる。
残りの７ワードは生産者のキャッシュＣのみに存在して
いるので、そのデータのみ書き替えればよく、バス１を
使う必要はない。続いて、消費者が８ワードの最初のワ
ードを読み込んだとき１ブロック８ワードが転送され、
バス１が１サイクル使われる。従って、バス１は合計２
サイクル使われる。次に、Ｍ＝８のときはアップデート
方式と同じように動作するので、生産者が８ワード連続
して書き込むときに、１ワードごとに８回バス１を使
う。しかし、消費者の持つデータ・ブロックはアップデ
ートされてそのまま残っており、消費者がデータを読み
込むときはキャッシュＣから読み込めばよいので、バス
１は使わない。結局、バス１は合計８サイクル使われる
ことになる。Ｍが０から８まで変化したときのバス使用
回数を表２に示す。この状況ではＭ＝０、即ちインバリ
デート方式がバス１の使用回数が２回と、一番少なくて
済み、最大の性能が得られる。

【状況２】別の状況として、生産者が１ワードのデータ
を書き込む毎に消費者がその１ワードのデータを読み込
んで処理する場合を考えてみる。Ｍ＝０のときは、生産
者が１ワード目のデータを書き込むときに、消費者のデ
ータ・ブロックをインバリデートするのでバス１を１回
使う。続いて、消費者が１ワード目のデータを読み込む
ときに、キャッシュＣ内のデータがインバリデートされ
てしまっているので、最新のデータを取り込むためにバ
ス１を１回使う。さらに、生産者が２ワード目のデータ
を書き込むときにインバリデートのため、バス１を１回
使う。消費者は２ワード目のデータを読み込むのに１回
バス１を使う。これをキャッシュＣの１ブロック、即ち
８ワード分を行ったとすると、８ワードのデータを受け
渡すのに合計２×８＝１６回バス１を使うことになる。
つぎに、Ｍ＝８のときは、生産者が１ワード書き込むご
とに消費者のデータ・ブロックをアップデートするの
で、バス１を１回使うが、消費者のキャッシュＣはアッ
プデートされているので、消費者がデータを読み込むと
きにはバス１を使わなくてもよい。従って、バス１は１
×８＝８回使われる。状況１と同様にＭが０から８まで
変化したときのバス１の使用回数を表３に示す。この状
況では、Ｍが１から８のときバス１を８回使うが、０の
ときバス１を１６回使うことがわかる。 実際には状況１だけが生じる処理や、逆に状況２だけが
生じる処理はまれで、通常のプログラムはいろいろな状
況を作り出している。今、簡単のために状況１と状況２
が、１対１の比率で、実際の処理上に出現したと仮定す
ると、バス１の使用回数は、表２と表３をさらに足し合
わせた値になり、表４に示すようになる。 以上の仮定の下では、表４から、Ｍ＝１のときにバス使
用回数が１１回と最小となる。これは、アップデート方
式と同じ動作をするＭ＝８のときのバス使用回数１６
回、インバリデート方式と同じ動作をするＭ＝０のとき
のバス使用回数１８回に比べ少なく、従って最良のシス
テム性能が得られることがわかる。 上記の仮定のように、状況１と状況２がいつも１対１の
頻度で出現するとは必ずしもいない。しかし、両極端の
２つの状況が発生しても、本発明のキャッシュ制御方式
を用いることによって、アップデート方式とインバリデ
ート方式それぞれの得意・不得意な状況に柔軟に対応で
きることがわかる。 Ｆ．発明の効果 以上説明したようにこの発明のキャッシュ制御部では、
共有データであって、しかも複数台のプロセッサＰから
頻繁に読み書きされるものに関しては、従来のアップデ
ート方式と同じく動作する。すなわち共有データにライ
トアクセスが発生したときは、複数のキャッシュＣに保
持されているコピーをインバリデートすることなしに即
座にアップデートする。他方本来共有データであって
も、１台のプロセッサＰからしか頻繁にアクセスされな
いデータに対しては、従来のインバリデート型と同様に
動作する。すなわち頻繁にアクセスするプロセッサＰの
キャッシュＣにだけそのコピーを残し、他のキャッシュ
Ｃ内のコピーはインバリデートする。したがってキャッ
シュのバスの性能を最大限に引きだすことができる。 しかもキャッシュ・プロトコルの切り換えは状況の変化
に基づいて自動的に実行されるので常に最適化されたキ
ャッシュ制御が可能となる。またプロセッサごとにキャ
ッシュ・プロトコルが設定されるのでプロセッサごとに
最適な動作を実現できる。またキャッシュ制御が自動的
にプロトコルを切り換えるので従来のプロセッサやメモ
リ管理ユニットをそのまま用いることができ、さらにコ
ンパイラ、スケジューラ等のソフトウェアによりプロト
コルを切り換える必要がないのでこれらソフトウェアも
従来のものを用いることができる。

【図面の簡単な説明】

第１図はこの発明の１実施例の全体構成を示すブロック
図、第２図は第１図例のプライベート・キャッシュの構
成を示すブロック図、第３図は第２図のキャッシュ・タ
グ・メモリ５のキャッシュ・タグのフォーマットを示す
図、第４図は第２図のキャッシュ制御におけるデータ・
ブロックの状態遷移図、第５図、第６図、第７図、第８
図、第９図および第１０図は上述実施例の動作を説明す
る図である。 Ｐ…プロセッサ、Ｃ…プライベート・キャッシュ、１…
共有バス、２…共有メモリ、３…キャッシュ制御部、４
…キャッシュ・データ・メモリ、５…キャッシュ・タグ
・メモリ、６…基準値レジスタ、７…比較器。

Claims (6)

【特許請求の範囲】
1. 【請求項１】複数のプロセッサがそれぞれのプライベー
   ト・キャッシュを介して共有バスおよび共有メモリに接
   続され、かつ上記プライベート・キャッシュの各々に設
   けられた制御装置の各々が上記共有バス上の信号を監視
   して、当該プライベート・キャッシュを含む２以上のプ
   ライベート・キャッシュで共有される共有データについ
   て上記２以上のプライベート・キャッシュのいずれかで
   更新書込みがあったときにそれら共有データの間の不一
   致を解消するように当該プライベート・キャッシュの当
   該共有データに対してデータ一貫性維持手続きを実行す
   るマルチプロセッサ・システムにおいて、 上記プライベート・キャッシュのそれぞれに、 当該プライベート・キャッシュに記憶されているデータ
   ごとに、当該データのアドレス情報と、当該データの状
   態情報と、当該プライベート・キャッシュで当該共有デ
   ータにアクセスがあるたびに１だけ減少され、当該プラ
   イベート・キャッシュ以外のプライベート・キャッシュ
   で当該共有データに更新書込みがあったことを表示する
   信号が上記共有バス上を伝送されるたびに１だけ増加さ
   れる計数値とを記憶するデータ制御情報記憶手段と、 上記計数値に関連して所定の基準値を記憶する基準値記
   憶手段と、 上記計数値と上記基準値とを比較する比較手段と、 当該データに関する上記比較手段の比較結果および上記
   状態情報に基づいて当該データに対してデータ一貫性手
   続きを実行する一貫性手続き実行手段とを設けたことを
   特徴とするマルチプロセッサ・システム。
2. 【請求項２】上記計数値は、所定の上限値および下限値
   を有する特許請求の範囲第１項記載のマルチプロセッサ
   ・システム。
3. 【請求項３】上記計数値の上限値を上記基準値とした特
   許請求の範囲第２項記載のマルチプロセッサ・システ
   ム。
4. 【請求項４】上記プライベート・キャッシュの各々に設
   けられた上記一貫性維持手続き実行手段の各々は、 当該プライベート・キャッシュを含む２以上のプライベ
   ート・キャッシュで共有される共有データについて当該
   プライベート・キャッシュ以外のプライベート・キャッ
   シュにおいて更新書込みがあったときに、対応する比較
   手段から出力される一致信号に応じて、当該共有データ
   を無効にし、かつ上記対応する比較手段から出力される
   不一致信号に応じて当該プライベート・キャッシュの当
   該共有データの内容を変更するとともにその状態表示を
   共有のままにするようにした特許請求の範囲第１項、第
   ２項または第３項記載のマルチプロセッサ・システム。
5. 【請求項５】複数のプロセッサがそれぞれのプライベー
   ト・キャッシュを介して共有バスおよび共有メモリに接
   続され、かつ上記プライベート・キャッシュの各々に設
   けられた制御装置が上記共有バス上の信号を監視して、
   当該プライベート・キャッシュを含む２以上のプライベ
   ート・キャッシュで共有される共有データについて上記
   ２以上のプライベート・キャッシュのいずれかで更新書
   込みがあったときに共有データ間の不一致を解消するよ
   うにデータ一貫性維持手続きを実行するマルチプロセッ
   サ・システムにおいて、 上記プライベート・キャッシュのそれぞれに、 当該プライベート・キャッシュに記憶されているデータ
   ごとに、当該プライベート・キャッシュ以外のプライベ
   ート・キャッシュが当該データを記憶しているかどうか
   を表す共有状態表示を記憶する共有状態表示記憶手段
   と、 当該プライベート・キャッシュおよび当該プライベート
   ・キャッシュ以外のプライベート・キャッシュの双方に
   記憶されている上記データごとに、当該データについて
   採用するデータ一貫性維持手続きの種類を、当該プライ
   ベート・キャッシュに対応するプロセッサが当該データ
   をアクセスする尤度と、対応するプロセッサ以外のプロ
   セッサが当該データをアクセスする尤度とに基づいて決
   定するデータ一貫性維持手続き決定手段と、 少なくとも２種類のデータ一貫性維持手続きを選択的に
   実行でき、上記データ一貫性維持手続き決定手段により
   決定された種類の一貫性維持手続きを実行する一貫性維
   持手続き実行手段とを設けたことを特徴とするマルチプ
   ロセッサ・システム。
6. 【請求項６】上記データ一貫性維持手続きは、１のプラ
   イベート・キャッシュで共有データに更新書込みがあっ
   たときに当該プライベート・キャッシュの当該共有デー
   タの状態表示を専有に変え、かつ他のプライベート・キ
   ャッシュの当該共有データを無効にする無効型のデータ
   一貫性維持手続きと、１のプライベート・キャッシュで
   共有データに更新書込みがあったときに他のプライベー
   ト・キャッシュに当該共有データがあればこれを変更す
   るとともに当該プライベート・キャッシュの当該共有デ
   ータ・データの状態表示を共有のままにし、他のプライ
   ベート・キャッシュに共有データがなければ当該プライ
   ベート・キャッシュの当該共有データの状態表示を専有
   に変える更新型のデータ一貫性維持手続きである特許請
   求の範囲第５項記載のマルチプロセッサ・システム。