JPH03217963A

JPH03217963A - マルチプロセッサ・システムおよびそのプライベート・キャッシュ制御方法

Info

Publication number: JPH03217963A
Application number: JP2004668A
Authority: JP
Inventors: Shigenori Shimizu; 清水　茂則; Morimiki Obara; 盛幹小原
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1990-01-16
Filing date: 1990-01-16
Publication date: 1991-09-25
Anticipated expiration: 2009-01-05
Also published as: DE69130580D1; EP0438211A2; EP0438211B1; DE69130580T2; US5228136A; EP0438211A3; JPH061463B2

Abstract

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

Description

【発明の詳細な説明】以下の順でこの発明を説明する。

Ａ．産業上の利用分野Ｂ．従来の技術Ｃ．産業上の利用分野Ｄ．問題点を解決するための手段Ｅ．実施例Ｅｌ．実施例の構成（第１図〜第４図）Ｅ２．実施例の
動乍（第１図〜第４図）Ｅ３、実施例の効果（第５図〜
第７図）Ｅ４．実施例の変形Ｆ．発明の効果Ａ．産業上の利用分野この発明は複数のプロセッサがプライベート・キャッシ
ュを介して共有バスおよび共有メモリに接続されている
マルチプロセッサ・システムに関し、とくに各プライベ
ート・キャッシュがわに制御装置を設け共有バス上の信
号を監視することにまってプライベート・キャッシュに
おけるデータの操作、たとえばプライベート・キャッシ
ュ間のデータの一貫性を維持する操作を行う、いわゆる
スヌープ・キヤ・νシュを有するマルチプロセッサ・シ
ステムおまびそのプライベート・キャッシュ制御方法に
関する。

Ｂ．従来の技術複数台のプロセッサがそれぞれプライベート・キャッシ
ュを持ち、共有パスによって相互接続される密結合マル
チプロセッサ・システムが提案され、実用化されつつあ
る。

複数のプロセ・νサは、同じく共有バスに接続される共
有メモリをリード・ライトする。もし、プライベート・
キャッシュが無い場合を考えると、各プロセッサの発生
する共有メモリへのリード・ライトはすべて共有バスを
介して行なわれる。そのため共有バスの使用率が高くな
り、プロセッサの台数を増やしてもシステムの性能はあ
る限界以上に向上しない。

そこで各プロセッサにプライベート・キャッシュを搭載
することによって、共有メモリ内データの一部のコピー
をキャッシュ・メモリに持ち、データのリード・ライト
をキャッシュ内で処理して、共有バスと共有メモリをで
きるだけ使わずに済ませる方式がある（マルチキャッシ
ュ・システム）。ところで、この方式では、各プロセ・
νサがそれぞれのキャッシュ内で、同じアドレスのデー
タを勝手に書き替えてしまうと、同一時刻に同一アドレ
スのデータが異なる値をとる可能性が生じる。そして同
一時刻、同一アドレスのデータ間で値がことならないよ
うにする工夫が必要であった。ここで、どのプロセッサ
から見ても同じアドレスには同じ値が入っているように
見えることをデータの一致牲（コンシステンシ）と呼ぶ
。

コンシステンシを保証するひとつの方法としてスヌープ
・キャッシュ方式がある。スヌープ・キャッシュ方式は
、各プロセッサのキャッシュ制御装置が共有バスを常時
監視することによって、キャッシュ間のコンシステンシ
を保つものである。即ち、あるプロセッサが自分のキャ
ッシュ内にあるデータを更新するとき、他のプロセッサ
のキャッシュにもそのコピーがあると、とのアドレスの
データをどう書き替えたかという情報を共有バス上に流
す。他のプロセッサのキャッシュ制御装置はそれを見て
、自分のキャッシュ内にあるデータを更新（アツプデー
ト）するか、もしくは無効化（インバリデート）するこ
とによってコンシステンシを保つ。

従来のスヌープ・キャッシュ方式では、共有データに対
する書き込みが起こったとき、他のキャッシュに存在す
るコピーを更新するか無効化するか、どちらか一方の方
式をとっていた。以後、更新する方式をアツプデート方
式、無効化する方式をインバリデート方式と呼ぶことに
する。

例えば、米国ゼロックス社のＤｒａｇｏｎや米国デジタ
ル・イクイップメント・コーポレーション社のＦｉｒｅ
Ｆｌｙはアップデート方式、カリフォルニア大学のＳＰ
ＵＲはインバリデート方式を用いている。日本アイ・ビ
ー・エム社の東京基礎研究所で開発されたＴＯＰ−１　
＜開発雛形）は、アップテート方式とインバリデート方
式とをプログラムで選択的に切り換えることができるは
うに設計されている。

ところで、この２方式は、複数のキャッシュ間のコンシ
ステンシを保つという意味では等価で、キャッシュ内の
データを更新（アップデート）しても無効化（インバリ
デート）してもコンシステンシ上はかまわないが、性能
という観点からは一長一短がある。

まずアツプデート方式は、複数のプロセッサが、非常に
密に共有するデータを扱うのに適している。つまり、密
に共有するデータに対してインパリデート方式を用いる
と、１台のプロセッサがその領域をライトするたびに他
のキャッシュ内のコピーを無効化してしまい、他のキャ
ッシュがその領域をリード・ライトするときに必ずキャ
ッシュ・ミスになって共有バスにアクセスが必要となる
。その点ア・νプデート方式では、コピーを持つキャッ
シュすべてが同時に更新されるので、共有バスを使うこ
となく当該データを読むことができる。例えば、一般的
にア・ンプデート方式は、生産者一消費者モデルの並列
プログラムに用いられるバッファや、プロセッサ間の同
期に使われるセマフォアなどに適している。

他方、インバリデート方式は、ある１台のプロセッサで
排他的に使用されるデータや共有アクセスがあまり発生
しない共有データに応用するのが望ましい。本来、ある
１台のプロセッサにおいて専有されていたデータである
にもかかわらず、ページングやプロセス・マイグレーシ
ョンによって見かけ上共有データになってしまった場合
には、不要な共有データがシステム中に残ることになり
、性能低下の原因となる。このような環境ではインバリ
デート方式が有効に働く。

ゆえに、どちらの方式をとるのが望ましいかは一概に決
まらず、実行されるプログラムの性質や個々のプロセッ
サの動作状況に依存する。いろいろなデータアクセスの
状況において、いつも良い性能を提供するプロトコルは
実現因難であった。

前述のＤｒａｇｏｎ，ＦｉｒｅＦｌｙ，ＳＰＵＲはどち
らか一方の方式のみ実現されている。したがって場合に
よっては好ましい性能を提供できない。また、ＴＯＰ−
１では上記の２方式を選択的に切り換えることができる
ようにっているが、ソフトウエアで２方式を制御してい
る。したがってとのまうに切替るかの問題が残っており
、その態様によっては十分な性能を引きだせない場合も
考えられる。

Ｃ．発明が解決しようとする問題点この発明は以上の事情を考慮してなされたものであり、
インバリデート方式とアツプデート方式の２つのプロト
コルを動的に最適に切り換える制御機構を提供すること
を目的としている。これにより、共有バスのトラフィッ
クを減少させ、システムの性能を向上させることが出来
る。

さらに、同じ機構を応用して、新たなキャッシュ゜プロ
トコルを導入して、共有バスのトラフィックをさらに減
少させるキャッシュの制御を行うことも目的としている
。

Ｄ．問題点を解決するための手段通常、プロセッサは短い時間では限られた領域のメモリ
をくりかえしアクセスしている。この領域をワーキング
・セットという。この発明では、共有データに書きこみ
が発生したとき、そのデータがワーキング・セットに含
まれているかどうか検出し、含まれていればア・ンプデ
ート方式、含まれていなければインバリデート方式でキ
ャッシュのコンシステンシを制御する。ワーキング・セ
ット内のデータは、プロセッサにより使われる確率が高
い。そこで、ワーキング・セット内のデータをアップデ
ートすることにより、そのプロセッサはバスを使用する
ことなく、最新のデータにアクセスできる。逆に、ワー
キング・セット外のデータは、プロセッサにより使われ
る確率が低い。ところが、このデータはキャッシュの中
に存在する以上、他のプロセッサが書きこみを行うたび
にバスを使ってアップデートされなければならない。

以上の点を考慮して、ワーキング・セット外のデータを
インバリデートすることにより、不必要なアップデート
のためのバス・トラフィックを少なくする。

さらに、上記のワーキング・セットの検出機構を利用し
て、オール・リード（ＡＬＬ　ＲＥＡＤ）という新たな
キャッシュ・プロトコルを導入し、システムの性能を向
上させる。スヌープ・キャッシュを用いたマルチプロセ
ッサ・システムでは、同一番地のデータやコードをいく
つかのプロセッサで共有することが頻繁にある。この場
合、通常のスヌープ・キャッシュ・プロトコルでは、そ
れぞれのプロセッサがパスを使用して、同一番地のデー
タやコードを繰返し各自のキャッシュ中にロードするこ
とになる。あるプロセ・ｙサがある番地のデータあるい
はコードに対してリード・ミスを起こして，バスを使用
してキャッシュ中にロードする時、そのデータあるいは
コードを使用するであろう他のキャッも自動的に自キャ
ッシュ中に取り込むことができれば、システム性能が大
幅に向上するが、従来方式では、そのデータあるいはコ
ードの使用性を、他のキャッシュが先見的に予測するこ
とができないため、リード・データのブロードキャスト
を効率よく実現することは不可能である。この発明では
、上述のワーキング・セット検出機構を使って、ワーキ
ング・セット内のデータのみオール・リードを適用する
。これにより、効率良くオール・リードを実現し、バス
のトラフイツクを減少させシステムの性能を向上させる
。

Ｅ．実施例Ｅｌ．実施例の構成以下この発明の実施例を説明する。第１図はマルチプロ
セッサ・システムの全体図である。この図において、複
数のプロセッサＰ１、Ｐ２、・・Ｐ，，がキャッシュＣ
１、Ｃ２、・・、Ｃｎを経由して共有バス１および共有
メモリ２に接続されている。これらのキャッシュＣ１、
Ｃ２、・・、Ｃイは、プロセッサＰ１、Ｐ２、・・、Ｐ
１の平均メモリ・アクセススピードをはやめるだけだけ
でなく、共有バス１の信号をモニタ（以後これをスヌー
プと呼ぶ）することにより、キャッシュＣ１、Ｃ２、・
・、Ｃ１相互間のコンシステンシを保つ機能を持ってい
る。

各キャッシュＣは第２図のまうに構成される。

キャッシュ基本制御部３は、キャッシュＣがプロセッサ
Ｐからアクセスされたとき、およびパス１のスヌープを
行うときのキャッシュＣ全体の基本的な制御を行う。デ
ータ・メモリ４は、主記憶（共有メモリ２）の一部のコ
ピーを記憶する高速なメモリである。プロセッサＰはほ
とんどの場合、主記憶にアクセスすることなく、このデ
ータ・メモリ４から必要なデータの読み書きができる（
データのアクセスはたとえば４バイト単位で行なわれる
）。このため、プロセッサＰの平均メモリ・アクセスが
速くなる。モード切換制御部５が、この発明に一り新た
に考案された部分である。このモード切換制御部５は、
プロセッサＰのメモリ・アクセスとバス１上のメモリ・
アクセスをモニタすることにより、キャッシュ基本制御
部３がキャッシュＣ間のコンシステンシを効率よくを保
てるまうに、キャッシュＣのモードを切換る。

第３図にキャッシュ基本制御部３の内部を示す。この制
御部３には、プロセッサＰとバス１の両方からそれぞれ
、アクセス制御信号とアドレス信号が入力される。キャ
ッシュ基本制御部３にはタグ・メモリ６があり、このキ
ャッシュＣがコピーを持っている主記憶のアドレスが保
持されている。この制御部５は、プロセッサＰからアク
セスされたときや、バス１のスヌープを行うときに、そ
のアドレスのデータがキャッシュＣにａ己憶されている
かどうか調べ、キャッシュＣの適当な制御を行う。

第４図にモード切換制御部５の内部を示す。この制御部
壮、ｎ個のワーキング・セット・メモリ（以下ＷＳＭ，
、ＷＳＭ．、・・、ＷＳＭ．，または総じてＷＳＭと呼
ぶ）とｎ入力のＯＲ回路７からなる。ＷＳＭはカウンタ
８、アドレス・タグ９、バリッド・フラグ１０、２つの
コンバレータ１１、１２と、ＷＳＭの制御を行う制御回
路１３から構成される。各ＷＳＭには、ワーキング・セ
ットに含まれる１つの記憶ブロック（たとえば４Ｋバイ
ト単位）が登録されている。モード切換制御部５は、プ
ロセッサＰやバス１上のアクセスのアドレスがワーキン
グ・セットの記憶ブロックに含まれるかどうか調べる。

ワーキング・セット中のｎ個の記憶ブロックのいずれか
に含まれていれば、ＯＲ回路７の出力が１になり、前述
のキャッシュ基本制御部３のモードをアップデートにし
、そうでなければＯＲ回路７の出力が０になり、キャッ
シュ基本制御部３のモードをインバリデートにする。

プロセッサＰは短い時間で見ると、非常にかぎられたメ
モリ空間（限られた数の記憶ブロック）を頻繁にアクセ
スしている。この空間をワーキング・セットという。Ｗ
ＳＭは、このワーキング・セットを検出して、それに属
する記憶ブロックを登録する。プロセッサＰやバス１上
のメモリ・アクセスに対して、そのアドレスが登録した
ワーキング・セットにあるかどうか調べる。また、ワー
キング・セットは長い時間では変化しているので、使わ
れなくなった記憶ブロックはＷＳＭから削除される。以
下、第４図を使ってモード切換制御部５の動作について
説明する。

第４図のアドレス・タグ９は、ワーキング・セットに登
録されている記憶ブロックのアドレスを保持している。

ここでは、プロセッサＰのアドレス空間を２のＭ乗バイ
ト、ワーキング・セットの記憶ブロックの管理区画の大
きさを２のＷ乗バイトとすると、アドレス・タグは、ア
ドレスの上位＜Ｍ−ｗ）ビットを記憶している。バリッ
ド・フラグ１０は、ＷＳＭがワーキング・セットとして
有効な記憶ブロックのアドレスを記憶しているかどうか
を示す。プロセッサＰかバス１でメモリ・アクセス要求
を行うと、各ＷＳＭはそのアドレスの上位＜Ｍ−ｗ）ビ
ットとアドレス・タグ９の内容とをコンバレータ１１で
比較する。上位アドレスが一致して、かつパリッド・フ
ラグ１０のビットが１であれば、そのアクセスはワーキ
ング・セット内へのものであり、ＯＲ回路７の出力が１
になる。

ワーキング・セットに属する記憶ブロックの登録は以下
のようにして行なわれる。プロセッサＰからのメモリ・
アクセス要求があり、それがワーキング・セットのいず
れの記憶ブロックにも含まれない場合、そのアドレスは
新たなワーキング・セットの記憶ブロックのアドレスと
して登録される。これには、ｎ個のＷＳＭの内、バリッ
ド・フラグ１０のビットが０であるＷＳＭの一つについ
て、アドレス・タグ９にアドレスの上位＜Ｍ−Ｗ）ビッ
トを書きこみ、バリッド・フラグ１０を１にするだけで
良い。もしこの時、すべてのＷＳＭのパリッド・フラグ
１０のビットが１のときは、新たなワーキング・セット
は登録されない。

つぎに、ワーキング・セットからの記憶ブロックの削除
について述べる。ワ“−キング・セットは、一度登録さ
れても、それがプロセッサＰによって使われなくなれば
、ＷＳＭから削除される。

これにはＷＳＭのカウンタ８が使われる。このカウンタ
８は、プロセッサＰからのメモリ・アクセス要求がある
とインクリメントされる。さらに、プロセッサＰからの
メモリ・アクセス要求がそのＷＳＭのワーキング・セッ
トの記憶ブロック内であれば、カウンタ８はクリアされ
る。すなわち、このカウンタ８はプロセッサＰがワーキ
ング・セット中の対応する記憶ブロックに最後にアクセ
スレてから、何回その記憶ブロック以外の記憶領域にア
クセス捨ているかを示している。このカウンタ８がオー
バーフローしたとき、もはやそのワーキング・セット中
の記憶ブロックはプロセッサＰに使われなくなっとと見
なされ、パリツド・フラグ１０のビット１をクリアして
、その記憶ブロックをワーキソグ・セットからを削除す
る。

この実施例では、以上のようにして、ワーキング・セッ
トをＷＳＭ上に記憶する。以下では、モード切換制御部
５の出力（第４図のＯＲ回路の出力）によってプロトコ
ルの動的な最適化とリード・ブロードキャストの制御を
行う方法を述べる。

《２）プロトコルの動的な最適化制御第１図の各キャッシュＣは、パス１をスヌープしている
。キャッシュ基本制御部３（第２図）は、自分がコピー
を持つデータへの書込みをバス１上に発見すると、その
コピーをインバリデートするか、アップデートすること
によって、キャッシュＣ相互間のフンシステンシを保つ
。自分がコビーを持つデータへの書込みがある場合、こ
の実施例では、モード切換制御部５にまり、そのデータ
がワーキング・セットに含まれているかどうかわかる。

もしそのデータが自分のワーキング・セットに入ってい
れば、キャッシュ基本制御部３はアップデート方弐で処
理を行う。また、ワーキング・セ・νトに入っていなけ
れば、インバリデート方式で処理を行う。ワーキング・
セット内のデータは頻繁に使われるので、アップデート
方式の方が効率がまく、ワーキング・セット外のデータ
は頻繁にアクセスされないので、インバリデート方式の
方が効率がよい。このように、共有データへの書込みが
ワーキング・セット中へかどうかによってプロトコルを
切り換え、効率良くキャッシュＣ間のコンシステンシを
保持する。

（３）オール・リードの制御通常のキャッシュを使ったバス結合マルチプロセ・ンサ
・システムでは、キャッシュ・ミスが発生すると、各プ
ロセッサＰは個別にバス１を使用してメモリ２からデー
タをキャッシュＣに読みこむ。このため、各プロセッサ
Ｐが大量の同じデータを共有して処理を進める場合には
、異なるプロセッサＰがそれぞれバス１を使用して同じ
データを読むことになる。この場合、一つのプロセッサ
Ｐがデータを読んだとき他のプロセ・νサＰのキャッシ
ュＣにもデータを転送できれば、パス１の使用率を大幅
に下げシステムの性能を向上させることができる。この
方式を、オール・リードと呼ぶことにする。

この方式は、但し、他のプロセッサＰのキャッシュＣ内
にすでにストアされたデータを追い出して、新しいデー
タをストアするので、以下の点で注意が必要である。

ｉ）　ブロードキャストを行うプロセッサの選択一つの
バス１で結合されたプロセッサＰはすべてが、同じ共有
データで処理を行うとは限らないので、共有データの転
送が必要なプロセッサＰのみにブロードキャストを行う
必要がある。

ｉｊ）プロセッサＰ間の同期同じ共有データを処理しているプロセッサＰ問でも、プ
ログラム上でいつも同期がとられているとは限らないの
で、一つのプロセッサＰがオール・リードを実行したと
きに、他のプロセ・ンサＰがそのデータを必要としてい
るかどうか一般には明らかでない。このため、共有デー
タの転送を必要とするプロセッサＰを動的に選択してブ
ロードキャストを行う必要がある。

以上のような注意を払わないと、このオール・リードは
キャッシュＣ中の本来必要なデータを追い出して、シス
テムの性能をかえって低下させる可能性もある。

この実施例では、ワーキング・セットの検出機能を使っ
て、このオール・リードを効率よく実現する。あるプロ
セッサＰがオール・リードを実行すると、オール・リー
ド要求がバス１に出力される。このとき、他のプロセッ
サＰのモード切換制御部５はそのアドレスがワーキング
・セ・νトの記憶ブロックに含まれているかどうか調べ
る。もしそのアドレスが自分のワーキング・セットの記
憶ブロックに入っていれば、キャッシュ基本制御部３は
そのデータをデータ・メモリ４に取り込む。

決だ、ワーキング・セットに入っていなければ取り込ま
ない。この方式にまり、ブロードキャストされた共有デ
ータを使用しないプロセッサＰは、データを取り込まな
いので、ｉ）で述べたような問題が解決される。またｉ
ｉ）に関しても、ブロードキャストが実行されたとき、
そのデータを使用していないプロセ・νサＰはデータを
取り込まない。これに対して、複数のプロセッサＰが同
じ共有データの大きなブロックを必要としているときに
は、つぎのまうにしてオール・リードが実現される。

１）最初の共有データへのアクセスは、それぞれのプロ
セッサＰがバス１を使用してデータを読みこむく通常の
アクセス）。このときそのデータを含むワーキング・ブ
ロックが各プロセ・νサのワーキング・セットに登録さ
れる。

２）つぎに、いずれかのプロセッサＰが同じ共有データ
・ブロックの次のデータをオール・リードで読みこむ。

このデータは、１）で登録されたワーキング・セット内
にあるので、他のプロセッサＰはそのデータを取り込む
。

このようにして、最初のリードは通常のアクセスで行な
われるが、それ以降の同じワーキング・ブロックへのリ
ードについては、オール・リードを効率よく使って、バ
スのトラフィックを減し、システムの性能を向上させる
ことができる。

Ｅ３．実施例の効果この実施例によれば、プロトコルの動的な最適化制御や
オール・リードの制御により、マルチプロセッサにおけ
るバスのトラッフィックを減らし、システムの効率を向
上させることができる。

以下では、マルチプロセッセで見られる典型的な事例を
使って、実施例の効果を具体的に示す。

スピン・ロックは、マルチプロセッサでクリティカル・
セクションの排他制御のために用いられる典型的な手法
である。第５図に、スピン・ロックの慨念図を示す。こ
の場合、各プロセッサＰはクリティカル・セクションに
入るときに、ある共有変数の値を１にセットし、出ると
きに０にリセットする。各プロセッサＰは、クリティ力
ル・セクションに入る前にその共有変数の値を調へ、１
であれば０になるまで待つ。第５図のプロダラムを説明
すると、（１）共有変数Ｘを読む（２）読みこんだＸを１と比較する（３）比較した結果、Ｘが１であれば、ｌｏｏｐにジャ
ンプする（４）（３）でＸがＯであれば、Ｘをもう一度１かどう
か調べ、１にセットする。（４）の命令は、比較とセッ
トを不可分に実行する。

（５）＜４）で、Ｘが０でなければ、１　ｏｏｐにジャ
ンプする（６）クリティカル・セクションの本体を実行する（７）最後に、ＸをＯにリセットする今、１０台のプロセッサＰ（第１図でｎを１０とする）
を結合したマルチプロセッサについて、１台のプロセッ
サＰ１がクリティカル・セクションを実行中で、その他
の９台のプロセッサＰ２〜Ｐ，。クリティカル・セクシ
ョンに入るために、Ｘが０になるのを待っているとする
。ここで、共有変数ＸについてのキャッシュＣの動作を
考える。

プロセッサＰ１が（７）でＸに書きこむ。このとき、他
のキヤ・νシュＣはＸのコピーを持っているので、キャ
ッシュ制御回路はキャッシュＣのコンシステンシを保つ
ように動咋する。インパリデーション方式では、プロセ
ッサＰ２〜Ｐ１。のＸのコピーはインバリデートされる
。このとき、これらのプロセッサＰは｛１）〜（３）の
プログラムを実行しているので、（１）でキャッシュの
リード・ミスが発生し、バスを使ってＸのコピーが読み
こまれる。このため、プロセッサＰ１の（７）での書き
こみと、プロセッサＰ２〜Ｐ１。の（１）でのリード・
ミスにまり、合計１０回のバス・トラフイックが発生す
る。これに対して、アツプデート方式では、、プロセッ
サＰ，が《７）で書きこみを行ったとき、プロセッサＰ
２〜Ｐ１。

のＸのコピーはアップデートされる。このため、プロセ
ッサＰ２〜ｐ　ｔｏは、（１）でリード・ミスを発生し
ない。よって、合計のパス・トラフィックはプロセッサ
Ｐ１の（７）での書きこみ１回のみである。

実施例によると、プロセッサＰ２〜Ｐ１。が（１）〜（
３）のループを実行している間は、ＸはプロセッサＰ２
〜Ｐ１０のワーキング・セットに含まれている。そこで
、プロセッサＰ１が（７）でＸに書きこんだとき、プロ
セッサＰ２〜Ｐ１。のモード切換制御部５は、キャッシ
ュ基本制御部３に対して、アップデート方式でキャッシ
ュＣ間のコンシステンシを保つように指示する。このた
め、上で述べたように、全体のバス・トラフィックが減
り、システムの効率が向上する。

ｂ．プロセス・マイグレーション前述の例は、アップデート方式がインバリデート方式よ
りすぐれている場合であるが、その逆の例もある。汎用
のマルチプロセッサでは、プログラムはマルチプロセス
環境で実行される。通常、プロセスの個数よりプロセ・
νサＰの個数の方が少ないので、マルチプロセッサの制
御プログラムは、プロセッサＰに割当てるプロセスを一
定の条件の下に切り換ている。これをプロセスに注目し
て考えると、プロセスはあるプロセッサＰに割当てられ
た後、制御プログラムによって実行を中断され、誌だあ
る時に再度プロセッサＰに割当てられ実行を再開する。

このとき、一般的には、プロセスは以前に割当てられて
いたプロセッサＰと異なるプロセッサＰに割当てられる
ことがある。このようにして、プロセスがプロセス切り
換えによって、プロセッサＰ間を移っていくことをプロ
セス・マイグレーションと呼ぶ。

アップデート方式では、共有データへの書き込みはバス
１に出力され、他のプロセッサＰのキャッシュＣのコピ
ーを更新する。そこで、共有データが大変多くなると、
バス１の使用率が高くなってしまう。プロセス・マイグ
レーションがおこるとプロセスは異なるプロセッサＰで
実行されるが、以前にそのプロセスが実行されていたプ
ロセッサＰのキャッシュＣは、そのプロセスの使ってい
たデータのコピーを持ったままである。このため、その
プロセスの使うデータは現在のプロセッサＰと以前のプ
ロセッサＰのキャッシュ間で共有されてレ味う。このよ
うな共有データを疑似共有データと呼ぶことにする。プ
ロセス・マイグレーションがおこるとこのようにして共
有データが大変多くなり、アツプデート方式のプロトコ
ルではバス使用率が高くなるため、システムの性能に影
響を与える。

一方、インバリデート方式のキャッシュＣでは、プロセ
ス・マイグレーションによるシステムの性能の低下は非
常に少ない。それというのは、疑似共有データに一度書
き込みが発生すると、プロセスが以前に実行されていた
プロセッサＰのキャッシュＣにある疑似共有データは、
無効化されてしまい、非共有データとなるからである。

よって、各疑似共有データについては、最初の一回の書
き込みはバスに出力されるが、以降はバス１を使用しな
いですむ。

この実施例にはれば、ワーキング・セット内のデータは
アツプデート方式、それ以外はインバリデート方式で、
キャッシュＣのコンシステンシを制御する。さらに、プ
ロセス・マイグレーションがおこると、プロセスのワー
キング・セットは、以前にそのプロセスを実行していた
プロセッサＰのキャッシュＣのワーキング・セット・メ
モリから削除される。このため、疑似共有データはイン
バリデート方式で処理される。

以上のように、キャッシュのコンシステンシを制御する
プロトコルは、インバリデート方式がよい場合と、ア・
νプデート方式がよい場合がある。

この実施例によると、これらのプロトコルを効率のよい
方に自動的に切り換えることができるため、システムの
性能を向上させることができる。

２）オール・リードにまる効果ここでは、２次元行列の掛算の場合について、オール・
リードが有効であることを示す。ここでは、第６図に示
したように、１２０ｘｌ２０の行列２つをそれぞれ９個
の部分行列に分割し、掛算を行う。９台のプロセッサＰ
，〜Ｐ９は第７図に示したように、部分行列の掛算を行
う。また、行列の１つの要素は３２ビット（４バイト）
で、パス１の１回の転送で３２ビットのデータが転送さ
れるとする。

ｉ．通常のプロトコルを使った場合第７図に示された通り、各プロセッサＰは部分行列の掛
算を３回行うので、６個の部分行列を読みこむ。各部分
行列は１６００個の要素を持ち、一回の転送で１個の要
素が転送されるので、各プロセッサＰは９６００　（＝
１６００ｘ６）回ノハス転送を要求する。さらに、９台
のプロセッサＰが独立にバス転送を行うので、システム
全体では、８６４００　（＝９６００ｘ９）回のパス転
送が必要である。

ｉｉ．オール・リードを使った場合第７図に止ると、各部分行列は３つのプロセッサＰから
参照される。オール・リードを使うと、ワーキンング・
セット含まれるデータについては、１回の転送で複数の
キャッシュＣに読みこむことができる。ここでは、各部
分行列の要素は連続したメモリ領域に配置されているも
のとする。

例えば、Ａｌｌについて考えてみると、Ａｌｌはプロセ
ッサＰ１、プロセッサＰ２、プロセッサＰ３の３プロセ
ッサＰから参照される。Ａｌｌの最初の要素については
、個別にバスを使ってデータを読みこむ。このとき、Ａ
ｌｌの配置されているメモリ領域がこれらのプロセッサ
Ｐのワーキング・セットとして登録される。このため、
２番目以降のＡｌｌの要素は、これらのプロセッサＰの
一つがバス１を使って読みこむと他の２つのプロセッサ
Ｐのキャッシュにも読みこまれる。このため、Ａｌｌを
３つのプロセッサＰが読み′こむために必要なバス転送
回数は、１６０２　（＝３＋１５９９）回となる。他の
８個の部分行列についても同様である。よって、行列の
掛算に必要なバス転送回数の合計は、１４４１８　（＝
１６０２ｘ９）回となる。

このように、通常のプロトコルでは８６４００回必要で
あったバス転送を、オール・リードを使うことによって
１４４１８回に減らすことができる。

Ｅ４．実施例の変形以上実施例に即してこの発明を詳述したが、この発明は
実施例に限定されるものではなく種々の変形が可能であ
る。たとえばアクセス・データがワーキング・セットに
属するかどうかの判別に変えてＬＲＵの手法を採用して
もよい。要するに局所性のあるデータについてはアップ
デート手法を採り、局所性のないデータについてはイン
バリデート手法を採ればよい。

Ｆ．発明の効果以上説明したようにこの発明によれば、インバリデート
方式とアップデート方式の２つのプロトコルを動的に最
適に切り換える制御機構を提供することができる。これ
にまり、共有バスのトラフィックを減少させ、システム
の性能を向上させることができる。さらに、同し機構を
応用して、新たなキャッシュ・プロトコルを導入して、
共有バスのトラフィックをさらに減少させることができ
る。

【図面の簡単な説明】

第１図はこの発明の１実施例の全体構成を示すブロック
図、第２図は第１図例のプライベート・キャッシュの構
成を示すブロック図、第３図は第２図のキャッシュ基本
制御部の構成を示すブロック図、第４図は第２図のモー
ド切換制御部の構成を示すブロック図、第５図、第６図
および第７図は上述実施例の応用例を示す図である。Ｐ・・・プロセッサ、Ｃ・・・プライベート・キャッシ
ュ、１・・・共有パス、２−・・共有メモリ、３・・・
キャッシュ基本制御部、４・・・データ・メモリ、５・
・・モード切換制御部、ＷＳＭ・・・ワーキング・セッ
ト・メモリ。ＰＩＰ２プロセッサよりバスよりＰｎ

Claims

【特許請求の範囲】

（１）複数のプロセッサがそれぞれのプライベート・キ
ャッシュを介して共有バスおよび共有メモリに接続され
、かつ上記プライベート・キャッシュの各々に設けられ
た制御装置が上記共有バス上の信号を監視して、当該プ
ライベート・キャッシュを含む２以上のプライベート・
キャッシュで共有される共有データについて上記２以上
のプライベート・キャッシュのいずれかで更新書込みが
あったときに共有データ間の不一致を解消するようにデ
ータ一貫性維持手続きを実行するマルチプロセッサ・シ
ステムにおいて、上記プライベート・キャッシュのそれぞれに、当該プラ
イベート・キャッシュのデータに対して上記一貫性維持
手続きが必要なときにそのデータがワーキング・セット
に属する記憶ブロックに含まれるかどうかを判別する判
別手段と、少なくとも２種類のデータ一貫性維持手続きを選択的に
実現でき、上記判別手段の判別結果に応じた種類の一貫
性維持手続きを実行する一貫性維持手続き実行手段とを
設けることを特徴とするマルチプロセッサ・システム。
（２）上記判別手段は、上記ワーキング・セットに含まれる複数の記憶ブロック
の識別子を記憶する記憶手段と、当該プライベート・キ
ャッシュに対応するプロセッサまたは他のプロセッサに
よりアクセスされるデータを含む記憶ブロックの識別子
が上記記憶手段に記憶されている識別子かどうかを判別
する手段とを有する特許請求の範囲第１項記載のマルチ
プロセッサ・システム。
（３）当該プライベート・キャッシュのワーキング・セ
ットに属しない任意の記憶ブロックに含まれるデータが
、当該プライベート・キャッシュに対応するプロセッサ
によってアクセスされたときに、上記任意の記憶ブロッ
クを上記ワーキング・セットに属させるようにし、さら
に当該プライベート・キャッシュのワーキング・セット
に属する任意の記憶ブロックの他の記憶ブロックに含ま
れるデータが、当該プライベート・キャッシュに対応す
るプロセッサによって所定回数アクセスされ、かつその
間に上記任意の記憶ブロックに含まれるデータが上記プ
ロセッサによってアクセスされないときに、上記任意の
記憶ブロックを上記ワーキング・セットから外すように
する特許請求の範囲第２項記載のマルチプロセッサ・シ
ステム。
（４）上記データ一貫性維持手続きは、１のプライベー
ト・キャッシュで共有データに更新書込みがあったとき
に当該プライベート・キャッシュの当該共有データの状
態表示を占有に変え、かつ他のプライベート・キャッシ
ュの当該共有データを無効にする無効型のデータ一貫性
維持手続きと、１のプライベート・キャッシュで共有デ
ータに更新書込みがあったときに他のプライベート・キ
ャッシュに当該共有データがあればこれを変更するとと
もに当該プライベート・キャッシュの当該共有データの
状態表示を共有のままにし、他のプライベート・キャッ
シュに共有データがなければ当該プライベート・キャッ
シュの当該データの状態表示を占有に変える更新型のデ
ータ一貫性維持手続きである特許請求の範囲第１項、第
２項または第３項記載のマルチプロセッサ・システム。
（５）上記データ一貫性維持手続きの対象データが上記
ワーキング・セットに属する記憶ブロックに含まれるこ
とを上記判別手段が判別したときに上記更新型のデータ
一貫性維持手続きを実行し、上記データ一貫性維持手続
きの対象データが上記ワーキング・セットに属する記憶
ブロックに含まれないことを上記判別手段が判別したと
きに上記無効型のデータ一貫性維持手続きを実行する特
許請求の範囲第４項記載のマルチプロセッサ・システム
。
（６）複数のプロセッサがそれぞれのプライベート・キ
ャッシュを介して共有バスおよび共有メモリに接続され
、かつ上記プライベート・キャッシュの各々に設けられ
た制御装置が上記共有バス上の信号を監視して、当該プ
ライベート・キャッシュを含む２以上のプライベート・
キャッシュで共有される共有データについて上記２以上
のプライベート・キャッシュのいずれかで更新書込みが
あったときに共有データ間の不一致を解消するようにデ
ータ一貫性維持手続きを実行するマルチプロセッサ・シ
ステムにおいて、上記プライベート・キャッシュのそれぞれに、当該プラ
イベート・キャッシュのデータに対して上記一貫性維持
手続きが必要なときにそのデータがアクセス局所性を有
する記憶ブロックに含まれるかどうかを判別する判別手
段と、少なくとも２種類のデータ一貫性維持手続きを選択的に
実現でき、上記判別手段の判別結果に応じた種類の一貫
性維持手続きを実行する一貫性維持手続き実行手段とを
設けることを特徴とするマルチプロセッサ・システム。
（７）複数のプロセッサがそれぞれのプライベート・キ
ャッシュを介して共有バスおよび共有メモリに接続され
、かつ上記プライベート・キャッシュの各々に設けられ
た制御装置が上記共有バス上の信号を監視して、当該プ
ライベート・キャッシュを含む２以上のプライベート・
キャッシュで共有されるべきデータについて上記２以上
のプライベート・キャッシュのうちの他のプライベート
・キャッシュへ読み込みがあったときに当該プライベー
ト・キャッシュへも上記共有バスを介して同時に当該デ
ータの読み込みを行えるようにしたマルチプロセッサ・
システムにおいて、上記プライベート・キャッシュのそれぞれに、他のプラ
イベート・キャッシュが読み込むデータが当該プライベ
ート・キャッシュのワーキング・セットに属する記憶ブ
ロックに含まれるときに、当該プライベート・キャッシ
ュもそのデータを読み込む必要があると判別する判別手
段と、上記判別結果に基づいて上記データを当該プライ
ベート・キャッシュに読み込む手段とを設けることを特
徴とするマルチプロセッサ・システム。
（８）特許請求の範囲第７項記載のマルチプロセッサ・
システムのプライベート・キャッシュ制御方法において
、複数のプライベート・キャッシュに個別のアクセスで同
一のデータを読み込み、このデータを含む記憶ブロック
を上記複数のプライベート・キャッシュのワーキング・
セットに含ませるステップと、上記ワーキング・セットに含まされた記憶ブロックに含
まれるデータを上記複数のプライベート・キャッシュの
１つへの読み込みアクセスを行ない、同時に上記プライ
ベート・キャッシュの他のものにも読み込みを行うステ
ップとを有することを特徴とするマルチプロセッサ・シ
ステムのプライベート・キャッシュ制御方法。