JPH0619739B2 - 多重プロセツサ・システムのキヤツシユを制御する方法 - Google Patents

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 この発明はデータ処理の分野に関するものであり、特
に、多重プロセツサシステムにおいて、専用キヤツシユ
を有する複数の中央処理装置間で共用されるデータの一
致性の制御に関するものである。

Ｂ．従来技術および発明が解決しようとする問題点 高性能処理装置（ＣＰ）は多くの場合、キヤツシユとし
て知られている専用の高速ハードウエア管理バツフアを
有している。キヤツシユは通常システムのユーザに透過
である。多重プロセツサ（ＭＰ）システムでは、多数Ｃ
Ｐが同一の主記憶装置（ＭＳ）を共用し、各ＣＰはアク
セスが出されると、常に最新の更新されたデータを得る
必要がある。このため、しばしばキヤツシユコヒーレン
ス問題として知られているキヤツシユ間のデータの一致
性をハードウエアで管理する。

従来のＭＰシステムには、多種類のキヤツシユがある。
キヤツシユの種類の１つは、下位レベルの記憶階層への
データの変更を常に更新するために、ＣＰが直接主記憶
装置（または第２のレベルのキヤツシユ）にデータを記
憶することを妨害しないストアスルー（ＳＴ）キヤツシ
ユである。主記憶装置への記憶を更新する際に、記憶を
開始するＣＰにあるキヤツシユ以外のキヤツシユから必
要とされるキヤツシユラインのコピーを無効にするた
め、適当な相互照会（以下、ＸＩという）動作を行うこ
とができる。通常のＳＴの設計では、データ記憶を取り
入れるため、相当の主記憶のバンド幅、いわゆる処理能
力（通常は平均で全ＣＰ記憶要求の１０〜２０％）を必
要とする。

他の種類のキヤツシユの設計は、ストアインキヤツシユ
（ＳＩＣ）である。ＳＩＣは、米国特許第３７３５３６
０号明細書、および米国特許第３７７１１３７号明細書
に開示されている。ＳＩＣキヤツシユデイレクトリ（キ
ヤツシユブロツクと主記憶ブロツクとの対応を表す）に
ついては、米国特許第４３９４７３１号明細書に詳述さ
れており、ＳＩＣの各ラインは、排他状態／読出し専用
状態（ＥＸ／ＲＯ）のフラグビツトによつて制御される
ＭＰの共用可能性を有する。ＳＴキヤツシユとＳＩＣキ
ヤツシユとの主な相違点は、ＳＩＣ中の記憶がすべてキ
ヤツシユ自体に向けられていることである（このキヤツ
シユ自体は、記憶されたラインがＳＩＣキヤツシユ中に
ない場合は、キヤツシユミスを生じさせる）。通常、キ
ヤツシユラインの修正は、ラインがキヤツシユから置き
換えられた場合のみ、主記憶装置（ＭＳ）で更新され
る。その結果、ＳＩＣの設計は、より複雑なコヒーレン
ス制御およびＸＩの追放の不利を犠牲にして（ＸＩの追
放は、１つのＣＰからのデータアクセスが、他のＣＰの
キヤツシユで修正されたラインを見出されるときに起
る）主記憶装置の必要なバンド幅を減少する。

これまでに開発されたキヤツシユコヒーレンス制御機構
には種々のものがある。代表的な例として、グローバル
デイレクトリ法、ブロードキヤスト法、およびメモリタ
グ付け法がある。グローバルデイレクトリ法では、記憶
制御エレメント（ＳＣＥ）が、ＣＰのキヤツシユデイレ
トクリのコピーを含んでいる。したがつてＸＩの決定は
むしろ効率よく解決される。ブロードキヤスト法では、
アクセスがローカルキヤツシユで解決できない場合、Ｃ
Ｐからの記憶要求を、他の全ＣＰに送る。メモリタグ付
け法では、どのＣＰが現在キヤツシユ内にそのラインを
有しているかを指示するために、主記憶装置内の各ライ
ンにタグ付けを行う。

全ての上記キヤツシユコヒーレンス制御法は、ＣＰの数
が増大した場合、またはＣＰクラスタ間に物理的分割が
ある場合、特に高性能ＣＰを考慮中の場合、欠点があ
る。

代りの方法して、効率の良いＸＩ制御の実施が抑制され
ているある種のデータの一致をソフトウエア制御させる
方法がある。その考え方は、他のＣＰからの記憶による
データ汚染の危険がある場合、専用キヤツシユからライ
ンを無効にする、いわゆるフラツシユすることである。
このような汚染は、たとえばオブジエクトが、ＣＰ上で
実行されるタスクによつて解放される時に生じ、したが
つて他のＣＰ上のタスクが資源を得て、これを修正す
る。いくつかのコンピユータアーキテクチユアでは（た
とえばＩＢＭ８０１）、キヤツシユからデータラインを
フラツシユするために提供された命令が設けられてい
る。このようなキヤツシユフラツシユ命令は、そのライ
ンがキヤツシユから置換されるべきアドレスの範囲を指
定することによつて設計される。これらの方法では、ソ
フトウエア（たとえばコンパイラまたはプログラマ）
に、フラツシユするためのアドレス範囲を追跡させる。
アドレス範囲は、ソフトウエアにおける論理オブジエク
トの意味論上の仕様でない。したがつて、このようなキ
ヤツシユフラツシユ命令は、記憶装置をソフトウエアに
対して透過にしない。

キヤツシユコヒーレンス制御法には、いくつかの公知の
方法があるが、ロツキング法に基づくキヤツシユコヒー
レンスを目指した方法は公知でない。下記はキヤツシユ
制御機構の代表的な方法である。

米国特許第４４８４２６７号明細書は、従来のキヤツシ
ユコヒーレンス制御機構のある種の変形に関するもので
ある。この方法は、キヤツシユ行が将来、相互照会を受
ける可能性の有無を動的に決定しようとし、ピンポン動
作をする欠点を減少させるためにこのようなラインでス
トアスルーを行なおうとしている。この方法では、従来
のグローバルＳＣＥデイレクトリ制御が無効化を行なう
ために必要とされる。しかしながら、本願発明では、密
に結合された多重プロセツサが、適切なソフトウエア制
御により相互照会について全く心配する必要がないよう
に、グローバルＸＩ制御が除去されるキヤツシユ設計
（適切なシステム設計を加える）について記載されてい
る。

米国特許第４２９３９１０号明細書は保護キー制御に関
するものである。保護キーは、記憶データに対する無許
可のアクセスまたは修正を検出するために使用されてい
る。しかしながら、本願発明では、記憶タグがキヤツシ
ユコヒーレンス動作を簡単にするために使用される。保
護キーと提案された記憶タグ法は直接関係ない。

米国特許第４４００７７０号明細書は、データの共有を
許す結果として、異なる仮想アドレスが同一の物理アド
レスを共用するいわゆる「同義語問題」に関するもので
ある。この同義語問題は、同一物理（絶対）ラインアド
レスを表す「仮想」アドレスによつて選択された２つ以
上（たとえば４つ）のキヤツシユ一致クラスの可能性に
よつて引き起こされる。この問題は、ページサイズ、キ
ヤツシユサイズ、およびキヤツシユラインサイズと何ら
かの関係がある。これは、多重プロセツサにおけるキヤ
ツシユコヒーレンス問題に向けられるものではない。

米国特許第４４００７７３号明細書は、入出力チヤネル
の直列化問題に関するものである。この方法は、ある種
のロツクビツトを記憶するのにソフトウエア制御ブロツ
クを使用し、直列化状態を試験するためにテストサブチ
ヤネル(Test Subchannel)命令を使用する。しかしなが
ら、本願発明は、キヤツシユに関するもので、特に、特
定の入出力装置上のチヤネル操作の直列化問題に関する
ものではない。

米国特許第４３９９５０４号明細書は多重システムにお
けるデータベースのロツキング法に関するものである。
その焦点は、ソフトウエアパツケージのためのアルゴリ
ズム法に合わせられる。しかしながら、本願発明は、あ
る種のソフトウエアの同期法（たとえばデータベースの
ロツキング法）の実施を仮定し、実際に、ソフトウエア
のロツキング法がいかに実施されたかに関するものでは
ない。

米国特許第４０９９２４３号明細書は、ロツクアウト方
式により異なる装置からの記憶ブロツクの操作の直列化
を扱つたものである。これは、記憶ブロツクに関するも
のである。これは、記憶ブロツクを扱つたもので、主と
してハードウエアによつて実施されることを除き、デー
タベースのロツキング法に類似している。この特許は前
述の米国特許第４４００７７３号および第４３９９５０
４号と同様に装置の直列化に関し、ロツキングに類似し
た装置を与えている。

この発明の目的は、ロツキング法に基づく改良されたキ
ヤツシユコヒーレンス機構を提供することにある。

この発明の他の目的は、各キヤツシユ行でカバーされる
ソフトウエアの制御定義域識別（ＣＤＩＤ）を使用する
ことによつて、改良されたキヤツシユコヒーレンス機構
を提供することにある。

この発明の他の目的は、従来の相互照会（ＸＩ）が行な
われない改良されたキヤツシユコヒーレンス機構を提供
することにある。

Ｃ．問題点を解決するための手段 本願発明は、システムソフトウエアにおけるある種の現
存のオブジエクトの同期を仮定している。オブジエクト
はシステムソフトウエア（たとえば、オペレーテイング
システム（ＯＳ）、フアイルシステム等）によつてより
正確に制御される資源である。オブジエクトは使用され
るアプリケーシヨンによつて異なる。例えば、フアイル
システムでは、オブジエクトはフアイルまたはインデツ
クスデイレクトリである。汎用ＯＳの場合、オブジエク
トは、いかにシステムがその資源を制御するかによつて
ページフレーム、統合データ構造（たとえば、待ち行
列、テーブル、ロツクワード）、ユーザプロセス、メモ
リのクラス等である。ソフトウエアの同期が正しいと仮
定するキヤツシユコヒーレンスを保証するキヤツシユプ
ロトコル（キヤツシユの規約）が扱われている。したが
つて、米国特許第４０９９２４３号の発明と、本願発明
とは、異なる問題を異なる方法で取り扱つている。

本願発明によると、新規装置が、キヤツシユデイレクト
リでソフトウエアオブジエクトおよびユーザタスクの論
理的見出しを結合させるために設けられている。したが
つて、意味プロトコルはキヤツシユコヒーレンスを維持
するためにキヤツシユフラツシユを実行するためにソフ
トウエアによつて使用される。これは、有効な実施が達
成するのが困難である或る種の状況でＸＩ制御の必要性
を除いている。

本発明はキヤツシユデイレクトリで、各キヤツシユ・ラ
インによつてカバーされるソフトウエアの制御定義域識
別（ＣＤＩＤ）を関連づける方法および装置を提供す
る。このような装置、および、活発にラインを使用する
ユーザの識別の追加のいずれか、または両方によつて、
ある種のデータのキヤツシユコヒーレンスは、このよう
なオブジエクトへのアクセスが、ロツキング型の同時制
御装置と正しく同期化されているとき、従来の相互照会
（ＸＩ）を実行せずに制御される。キヤツシユに対する
ソフトウエアプロトコルは、解放されたキヤツシユ・ラ
インのフラツシユを制御するために資源の中心部に設け
られる。これらのプロトコルのパラメータは、高水準の
定義域識別およびタスク識別である。

Ｄ．実施例 この発明は、キヤツシユデイレクトリで、ソフトウエア
オブジエクトおよびユーザタスクのいずれかまたは両方
のある種の論理見出しを結合させるための新規の装置お
よび制御方法を提供するものである。このような装置
で、意味プロトコルはキヤツシユコヒーレンスを維持す
るためにキヤツシユフラツシユを実行するようにソフト
ウエアによつて使用される。これは、有効な実施を達成
することが困難である或る種の状況で、ＸＩ制御の必要
性を除去する。

ロツキング法に基づくキヤツシユコヒーレンス制御の基
本的な考え方は下記のとおりである。共用データへのソ
フトウエアアクセスは、しばしばある種の許可機構によ
つて制御される。ロツキング法は、このようなソフトウ
エア同期制御の典型的な技術である。ユーザはオブジエ
クトにアクセスするために、ロツクを許可される必要が
ある。オブジエクトを使用した後は、ユーザはロツクを
解除する。ロツキング法には異なる種類のものがある。
ここでは、主として、ユーザがオブジエクトを修正する
時、オブジェクトのロツキングが排他性を保証すべきで
あるようなロツキング（すなわち、このユーザは、オブ
ジエクトがそのユーザによつて解除される前に、このオ
ブジエクトにアクセスできる唯一の人である）である。
その結果、ユーザは、他の全ユーザがこのオブジエクト
に対するロツクを解除した場合のみ、オブジエクトに対
してＥＸＣＬＵＳＩＶＥが許可される。

ＭＳが２の累乗（たとえば２５６バイト）のサイズのブ
ロツクに分割されていると仮定する。ブロツクサイズ
は、必要とされる全キヤツシユラインのサイズと少なく
とも同じでなければならない。したがつて、１ラインは
２つのブロツクに分割することはできない。ここでは、
ブロツク解体特性を有するオブジエクトについて考え
る。瞬時に、かりにこのオブジエクトを含むように割り
当てられたＭＳブロツクが、このオブジエクトに属さな
いアクセス可能なデータを含まないならば、オブジエク
トはブロツク解体特性を有する。キヤツシユコヒーレン
スに関する限りでは、キヤツシユのラインが他のＣＰに
よつて修正される可能性がある場合は、キヤツシユのラ
インがキヤツシユから追い出されたことを確認し、この
ラインが他のＣＰからアクセスされることができないう
ちに、キヤツシユのラインの修正が常にＭＳで更新され
ていることを確認しなければならない。これらの条件
は、このブロツクをカバーするオブジエクトになおロツ
クを保持するＣＰを使用可能なユーザがもはやいなくな
ると、ブロツクに属するラインがキヤツシユ（ＭＳで更
新された修正ラインを有する）から追い出される場合に
満足される。ＩＢＭ８０１コンピユータ等、キヤツシユ
からラインを追い出すための命令を有するアーキテクチ
ユアはあつた。しかしながら、このようなキヤツシユ・
ラインのフラツシユ命令は、フラツシユされるべきライ
ンを指定するためにアドレス範囲を使用する。これは、
記憶装置をソフトウエアに透過しないソフトウエアオブ
ジエクトのアドレス範囲を追跡するためにソフトウエア
に負担をかける。

ここで採用する新規の方法は、キヤツシユデイレクトリ
にオブジエクトの識別を埋め込むものである。これによ
り、ターゲツトオブジエクトの意味仕様をとるキヤツシ
ユフラツシユ命令が提供される。同一ＣＰを使用してい
る多数のユーザによつて同時に共用されるラインを不必
要にフラツシユするためにキヤツシユミス頻度を減少さ
せるための方法も提供される。

まず第１に、ＭＳのラインを２種類に分類する。第Ｉ種
のラインは、キヤツシユコヒーレンスがＦＬＵＳＨプロ
トコル（フラツシユの規約）によつて制御されるもので
ある。一つは第II種のラインで、第II種のラインのキヤ
ツシユコヒーレンスは、他の手段によつて制御される。
他に指定しない限り、第Ｉ種のみを取扱う。また、他に
示さない限り、この発明は以後、ＭＯＤＩＦＩＥＤビツ
トがキヤツシユデイレクトリで使用されるＳＩＣを使用
して説明される。修正ビツトＯＮを有するキヤツシユ・
ラインは、まだＭＳで更新されていない修正を含む。

各ＭＳのブロツクは、制御定義域（ＣＤ）と動的に関連
付けられている。ＣＤは共用オブジエクトから引き出さ
れたオブジエクトのクラスである。

制御定義域（ＣＤ）の概念は実記憶装置の分割に関連し
ている。例えば、システムは３つのオブジエクトＯ_１、
Ｏ_２およびＯ_３を有していると仮定する。オブジエクト
Ｏ_１は、ＶＰ１およびＶＰ２とラベルを付けられる２つ
の隣接する仮想ページをカバーする。また、オブジエク
トＯ_２およびＯ_３はそれぞれ仮想ページＶＰ３およびＶ
Ｐ４によつてカバーされ、オブジエクトＯ_１およびＯ_２
は制御定義域Ａに属し、一方、オブジエクトＯ_３は制御
定義域Ｂに属すると仮定する。

仮想ページＶＰ１〜ＶＰ４は、特定の時間に実ページＲ
Ｐ１〜ＲＰ４に変換される。ＯＳは、どのオブジエクト
がどの制御定義域にあるべきであるかを決定する。実ペ
ージフレームが特定の仮想ページに割り当てられた後、
ＯＳは実ページフレームにＣＤＩＤ（すなわち、制御定
義域識別）をセツトする。したがつて、この例では、Ｒ
Ｐ１〜ＲＰ３のＣＤＩＤは制御定義域Ａを反映し、一方
制御定義域ＢはＲＰ４で反映される。システムのハード
ウエアはアクセスの際オブジエクトのためのＣＤＩＤを
識別することができる。例えば、オブジエクトＯ１がア
クセスされると、メモリ制御ハードウエアはＲＰ１およ
びＲＰ２のＣＤＩＤタグからＣＤＩＤＡを検出する。各
ＣＤは独特の識別（ＣＤＩＤ）を有する。ＭＰシステム
にあるＣＤの最大数は、各ＣＤＩＤを表わすのに使用可
能なビツト数によつて決定される。多くのブロツクは同
一のＣＤに属する。ＣＰからの各記憶アクセス毎に、対
応するＣＤＩＤをハードウエアに知らされるべきであ
る。ＣＤＩＤはアドレス変換テーブル（たとえばセグメ
ントテーブル、ページテーブル）に記憶させるか、また
はハードウエア（たとえば１メガバイトのＭＳ記憶装置
当たり８タグビツト）によつて直接実施される。各キヤ
ツシユ（ＳＴでもＳＩＣでもよい）のデイレクトリ内に
は、（ＶＡＬＩＤビツト、ＭＯＤＩＦＩＥＤビツトのよ
うな他の必要な状況標識のほかに）キヤツシユの各ライ
ンのためにＣＤＩＤフイールドがあり、そこに、現ライ
ンのためのＣＤＩＤが記憶される。必要な場合、独特の
ＣＤＩＤ（ＣＤＩＤ０で表わす）が、第II種のデータラ
イン（共用可能性は明示キヤツシユ・ラインフラツシユ
法で制御されないもの）を指示するために割り当てられ
る。ＭＳからキヤツシユへのラインの取出しの際に、記
憶アクセスハードウエアにより得られるＣＤＩＤは、キ
ヤツシユデイレクトリのＣＤＩＤフイールドへ自動的に
ゲートされる。ＰＡＧＥは仮想アドレス変換の粒度（タ
スクの大きさ）で、変換索引バツフア（ＴＬＢ）が変換
の高速化のために使用されると仮定すると、使用される
各ＰＡＧＥのためのＣＤＩＤも、それらに対応するＴＬ
Ｂエントリに記憶される。

キヤツシユデイレクトリにユーザ識別（ＵＩＤ）を結合
するオプシヨンも提供される。ＵＩＤは、プロセス、例
えばネツトワークのシステムユーザおよびアプリケーシ
ヨンプログラムまたは共用メモリを使用する他のシステ
ムでさえ識別する。このオプシヨンにより、必要とされ
るオブジエクトにロツクを保持しているＣＰのユーザが
まだいる間、キヤツシユからラインをフラツシユするオ
ーバーヘツドを減らすことができる。考慮されるユーザ
は、共用オブジエクトのロツクとアクセスとを両立でき
なければならない。どの時点でも、同一のＵＩＤの下で
は、同一の共用オブジエクトに保持される複数（２つ以
上）のロツクがあつてはならない。ＵＩＤの下で実行さ
れる共用オブジエクトをアクセスするプログラムは、同
一のＵＩＤの下で得られたロツクによりアクセス権を許
可されるべきである。また、ＵＩＤの下で得られる共用
オブジエクトのロツクは、同一ＵＩＤの下で解除される
べきである。ＵＩＤの規定は、特定システムの実施に対
して行なわれる。このオプシヨンが実行されると、ＵＩ
Ｄは、記憶アクセスハードウエアに使用可能であるべき
である。ＵＩＤは、プログラムが開始される前に、シス
テムにより、ＬＣＴＬ型の命令を介して、制御レジスタ
にロードされる。下記に、キヤツシユデイレクトリでの
関連するＵＩＤのオプシヨンと共に、本発明を説明す
る。

キヤツシユデイレクトリの各ラインのエントリには、一
定数（たとえば２つ）のＵＩＤフイールドがある。各Ｕ
ＩＤＣは、一定数（例えば４ビツト）のビツトからな
る。ＵＩＤは、表わすのにそれに対応するＵＩＤよりも
多くのビツト（たとえば３２ビツト）を要するＵＩＤＣ
はＵＩＤよりビツト数が少ない傾向にあるので、このＵ
ＩＤＣは回路を節約するためキヤツシユデイレクトリの
ＵＩＤの代りに使用されるＵＩＤのクラス識別子であ
る。ＵＩＤのためのＵＩＤＣ（“ｕｉｄｃ（ＵＩＤ）”
で表わす）は、ある種の規則（たとえば、ＵＩＤからあ
る種のビツトの抽出）により、ハードウエアにより得ら
れる。各デイレクトリのエントリに、２つ以上のＵＩＤ
Ｃフイールドがある場合は、下記の説明で仮定するよう
に、ある種のＬＲＵ（ｌｅａｓｔ−ｒｅｃｅｎｔｌｙ
ｕｓｅｄ）型の置き換えハードウエアは、キヤツシユラ
インへのアクセスに関連するＫ個（Ｋは整数）までの使
用可能ＵＩＤＣを獲得するために提供される。（ＣＤＩ
Ｄ０に等しくないＣＤＩＤを有する）キヤツシユライン
へのアクセスがＣＰから出されると、ハードウエアは、
現在のＵＩＤＣがすでにキヤツシユデイレクトリのエン
トリのＵＩＤＣフイールドにあるかどうかをチエツクす
る。一致が見つかり、このＵＩＤＣが、すでにＵＩＤＣ
フイールドにないならば、このＵＩＤＣは最新使用（Ｍ
ＲＵ）にされる。そうでない場合は、ＵＩＤＣは、必要
な置き換えにより、ＭＲＵとして挿入される。独特のＵ
ＩＤＣは、どの有効ＵＩＤのＵＩＤＣでもあり得ないＤ
ＵＭＭＹと称される。また、どの実行プログラムに対し
てもＵＩＤであり得ないＵＩＤ（またＤＵＭＭＹと呼ば
れる）が仮定される。両ＵＩＤＣ値が、キヤツシユライ
ンのエントリのＵＩＤＣのフイールドでＤＵＭＭＹであ
る場合、そのキヤツシユラインは、ＩＮＶＡＬＩＤとし
て扱われる。（したがつてこの場合、有効性を示すため
に、キヤツシユデイレクトリのエントリに他のＶビツト
は必要ではない。システムセツト中、キヤツシユデイレ
クトリの全ＵＩＤＣフイールドはＤＵＭＭＹを含むよう
に初期設定される。

キヤツシユコヒーレンスの制御は、下記の形のＦＬＵＳ
Ｈ命令によつて実行される。

ＦＬＵＳＨ ＵＩＤ，ＣＤＩＤ，Ｍ，Ｉ 修正された（Ｍ）フラグおよび無効（Ｉ）フラグは、そ
れぞれ１ビツトを使用して表わされる。命令の正確なフ
オーマツトは、特定のアーキテクチユア設計に対して行
なわれる。ＣＰからＦＬＵＳＨ命令が出力されると、パ
ラメータＵＩＤ、ＣＤＩＤおよびＭはキヤツシユ動作の
目標ラインと突き合わされるために使用される。ＵＩＤ
とＣＤＩＤの意味は、前述より明らかである。Ｍフラグ
がオンの場合は、ＦＬＵＳＨ命令は、キヤツシユの修正
ラインでのみ作動し、そうでない場合は、未修正ライン
をまたカバーする。指定されたＵＩＤパラメータがＤＵ
ＭＭＹでない場合、ＦＬＵＳＨ命令は、キヤツシユデイ
レクトリのＵＩＤＣフイールドで検出された“ｕｉｄｃ
（ＵＩＤ）”を有するラインのみをカバーし、そうでな
い場合は、ＵＩＤＣの突き合わせは実行されない。ＵＩ
Ｄ，ＣＤＩＤおよびＭ仕様によつて突き合わされたすべ
てのキヤツシユ・ラインに対して、ＦＬＵＳＨ命令の実
行により、ＭＳで修正ラインが更新され、対応するＭＯ
ＤＩＦＩＥＤビツトがオフにされる。ＵＩＤが汎用レジ
スタ（ＧＰＲ）を用いて指定されるＦＬＵＳＨ命令の実
行を考え、ＧＰＲＯ（ＲＯ）が、ＤＵＭＭＹ ＵＩＤを
指示すると仮定する。Ｉフラグがオンで、ＵＩＤがＲＯ
によつて指定されないならば、ＦＬＵＳＨ命令の実行は
また、突き合わされたデイレクトリのエントリの“ｕｉ
ｃｄ（ＵＩＤ）”をＤＵＭＭＹに変える。Ｉフラグがオ
ンであり、ＵＩＤがＲＯで指定されるならば、突き合わ
されたキヤツシユラインは実際に（デイレクトリのエン
トリのＵＩＤＣのフイールドにＫＤＵＭＭＹを入れるこ
とにより）無効化される。

ＦＬＵＳＨ命令の実行は、ＭＳの更新と同期しているべ
きである。修正キヤツシユ・ラインが、フラツシユの実
行によりＭＳで更新されると、ＦＬＵＳＨ命令は、これ
らの更新がＭＳシステムで肯定応答されるまで、実行さ
れない。

ＭＳによる更新の肯定応答は、特定のＭＳアーキテクチ
ユアによるところが大きい。保留中の記憶バツフアが実
行されているＭＳシステムの場合、更新の肯定応答は、
更新がバツフアされると直ちに出力される。実行のこの
部分については、これ以上の説明は行なわない。

ＦＬＵＳＨ命令は、上記の形式に限定されるものではな
い。ＭＯＤＩＦＩＥＤビツト（たとえばＳＴ中）なしの
キヤツシユ機構の場合、ＦＬＵＳＨ命令にＭパラメータ
が存在する必要はない。Ｉフラグにより指示される操作
を行うことが常に望ましい場合は、Ｉパラメータは命令
フオーマツトから省略される。ＵＩＤが、ＦＬＵＳＨ命
令の実行時に常にハードウエアに知られていると、ＵＩ
Ｄパラメータも省略される。ＣＤＩＤ０以外にＣＤＩＤ
が１つしかない場合は、ＣＤＩＤパラメータも省略され
る。すべての共用オブジエクトを指示するために、他の
パラメータビツトＳを提供することも有利である。Ｓビ
ツトがオンであると、すべての共用オブジエクト（第Ｉ
種）がＦＬＵＳＨ命令に含まれる（この場合、ＣＤＩＤ
のパラメータ値は無視される）。

本発明は主として、システムの中心部が適切なロツキン
グ制御下でアクセスされるある種の共用データオブジエ
クトのキヤツシユコヒーレンスを保証するために論理Ｆ
ＬＵＳＨ命令のプロトコルを発行する設計を提供するよ
うにされる。ユーザが共用オブジエクトにアクセスを開
始する前に、ロツキングのプロトコルはアクセスの許可
を得るために発行される。このような共用オブジエクト
へのアクセスが、ロツクを解除するためにユーザの要求
を完了した後、システムの中心部は、ロツクが実際に他
のユーザへの使用可能性に対して解除される前に、必要
なキヤツシユフラツシユ動作を行うためにＦＬＵＳＨ命
令を使用する。また、ユーザのためのＣＰの切換えの可
能性がある場合は、このシステムは、ユーザの最後が実
行したＣＰのキヤツシユの作業ラインを一掃するために
ＦＬＵＳＨ命令を出力する。ＦＬＵＳＨ命令は、特権シ
ステム状態でのみ実行されるべきである。このようにし
て、記憶状態の整合性は、問題プログラムによつて破壊
されず、この問題プログラムはキヤツシユコヒーレンス
を維持する負担から解放される。

ＦＬＵＳＨ命令が高い頻度で実行されるならば、性能の
低下が生じる。本発明を使用する良好なシステム設計
は、ソフトウエアに基づくキヤツシユコヒーレンス制御
を、効率の良いＸＩ実行が容易に達成されない共用オブ
ジエクトに比較的まれなアクセスのみに限定する。この
状況は、ＭＰシステムに多数のＣＰがある場合、または
ＣＰ群間に物理的な分離がある場合に生じる。このよう
な状況が発生すると、従来の方法を使用する完全に一般
的なキヤツシユコヒーレンス制御を得るのはむしろ困難
である。このような環境で、ＭＳの共用を提供する妥当
な方法は、システム活動のほとんどが個々のＣＰ（また
はＣＰ群）で実行されるように、システムを区分し、Ｃ
Ｐ（またはＣＰ群）を、共用オブジエクトへの簡単なア
クセスにより、相互に通信させることである。このよう
な共用オブジエクトの、可能性のある例はメツセージで
ある。本発明は、ＣＰ（またはＣＰ群）の間で共用する
オブジエクトのアクセスのためにデータの一致性の制御
への洗練された方法を提供する。

ＣＤに対する共用オブジエクトの割り当ては、キヤツシ
ユの性能に影響力を有する。ユーザが２つの異なる共用
オブジエクトにアクセスする許可が与えられる場合の状
況を考察する。ユーザにより、このオブジエクトの１つ
が解放されると、システムは、これらの２つのオブジエ
クトが同一ＣＤにたまたま割り当てられているならば、
キヤツシユのもう一方のオブジエクトのために有効な作
業ラインを無効にして追い出す。これにより、記憶の更
新およびキヤツシユミスに不要な記憶のオバーヘツドを
生じる。したがつて、ＣＤに対する共用オブジエクトの
割り当ての主な原理は、上記の現象が頻繁に起りがちに
ならないように、使用可能共用オブジエクト間でのＣＤ
ＩＤの妥当なランダム化を提供することにある。

第２図は、本発明が実施されるＭＰ構成を示す。同一Ｍ
Ｓ１０を共用するＭＰにＮ個（Ｎは整数）のＣＰ２、
４、６および８がある。各ＣＰは、命令復号実行エレメ
ント（ＩＥ）１２、１４、１６および１８、ならびにバ
ツフア制御エレメント（ＢＣＥ）２０、２２、２４およ
び２６をそれぞれ有している。ＢＣＥは、専用ＣＰデイ
レクトリ、ならびにそれぞれのキヤツシユおよび制御装
置を含む。各ＢＣＥは、記憶制御装置（ＳＣ）２８また
は３０を介して、共用種記憶装置（ＭＳ）１０にアクセ
スする。このＳＣ２８および３０は、それぞれチヤネル
装置２９および３１に接続されている。それよりもＭＳ
１０は、全ＣＰに共用される第２のレベル（Ｌ２）のキ
ヤツシユで、このＣＰではこのＬ２キヤツシユは順番に
ＭＳをアクセスするこのようなＬ２キヤツシユの動作は
下記のＭＳの動作と同様である。

第３図は、第２図に示されるＢＣＥ２０、２２、２４ま
たは２６のうちの１つの内部を示す。このＢＣＥは、４
ウエイ連想キヤツシユ４０、そのデイレクトリ４２、デ
イレクトリ置き換え選択回路４４を含み、またＣＤＩ
Ｄ、ＵＩＤＣ１、ＵＩＤＣ２フイールドおよびそれらの
制御回路を除いて、前述の米国特許第４３９４７３１号
明細書に記載された形式の各ＣＰに関連する他の論理を
含む。米国特許第４３９４７３１号の全ＢＣＥの明細書
全体をここに引用する。この特許のプロセツサデイレク
トリは、本発明では、先行技術のＶビツト位置をＵＩＤ
Ｃ１、ＵＩＤＣ２に置き換え第４図に示されるようなデ
イレクトリの各ラインのエントリに２つの新しいフイー
ルドＵＲ（１ビツト）およびＣＤＩＤを追加することに
より、ＣＰのキヤツシユデイレクトリを提供するように
修正されている。また、この発明の実施例のためにここ
で記載されるＣＰデイレクトリのための制御装置は、米
国特許第４３９４７３１号明細書記載のものとは異なる
ものである。

各キヤツシユデイレクトリのエントリのＵＲビツトは、
そのラインのためのＵＩＤＣ１およびＵＩＤＣ２上でＬ
ＲＵを実行するために役立つ。キヤツシユデイレクトリ
のエントリで、ＵＲが１であればＵＩＤＣ１が、ＵＲが
０であればＵＩＤＣ２が、それぞれＬＲＵである。新し
い（別個の）ＵＩＤＣがデイレクトリのエントリに挿入
されるべきであると、新しいＵＩＤＣを含むためにエン
トリのＵＩＤＣフイールドは、ＬＲＵである。説明のた
め、ＢＬＯＣＫの粒度はＰＡＧＥであり、各ページテー
ブルのエントリは、現在のＰＡＧＥと関連するＣＤＩＤ
を含むと仮定される。仮想アドレス変換の際変換機構
は、関連するＰＡＧＥのＣＤＩＤを得て、これをＢＣＥ
の内部レジスタＣＤＩＤにゲートする。また、プログラ
ムがＣＰ上で実行するためにタスク指名されると、その
“ｕｉｄｃ（ＵＩＤ）”が、これもＢＣＥの内部レジス
タＵＩＤＣＲにロードされる。この説明において、“内
容（ＣＤＩＤＲ）”および“（内容（ＵＩＤＲ））”は
それぞれ、レジスタＣＤＩＤＲ、およびＵＩＤＲの現在
の内容を指示するのに使用される。

第４図は、出力レジスタ１００すなわちＣＰキヤツシユ
デイレクトリの選択された一致クラスの４つの連想エン
トリの関連情報のエントリフオーマツトを示す。従来の
ＸＯＲ回路１０４Ａ−１０４Ｄは、４つの連想エントリ
のうち（ある場合）どれかが選択可能であるかを判定
し、ＵＩＤＣは、１０１Ａ−１０１Ｄ、１０２Ａ−１０
２Ｄ続いてＮＯＲゲート１０５Ａ−１０５Ｄを比較し
（＝ＤＵＭＭＹ）、有効ラインのエントリの選択１０６
Ａ−１０６Ｄだけが、ＩＥ１０３からの要求アドレスに
よるキヤツシユヒツトまたはミスの有無を判定できるよ
うにする。レジスタ１００の一致クラスでのキヤツシユ
ヒツトは、キヤツシユヒツトライン１０８を付勢するた
めにＯＲ回路１０７への入力ラインの１つを付勢する。
ＯＲ回路１０７への入力ラインのいずれも付勢されない
ならば、キヤツシユミスライン１１０はＯＲ回路１０７
からの信号を受信しないインバータ１０９によつて付勢
される。

キヤツシユミスの場合、ＢＣＥは、現在のキヤツシユ要
求のためのＣＤＩＤがＣＤＩＤ０であるかどうかをチエ
ツクするために内部レジスタＣＤＩＤＲ（変換機構によ
つてセツトされる）を使用する。現在のキヤツシユ要求
がＣＤＩＤ０に対するものであるとわかつた場合、（た
とえば、ＸＩ決定および変換アレイ更新時に）とられる
処置は、（遠隔）キヤツシユ・ラインの無効化が無効化
された遠隔キヤツシユデイレクトリのエントリのＵＩＤ
Ｃ１およびＵＩＤＣ２の両方にＤＵＭＭＹと入れること
によつて表わされることを除いて、米国特許第４３９４
７３１号明細書に記載されたものと同様である。キヤツ
シユヒツトがＣＤＩＤ０に対する場合ないことが検出さ
れると、選択されたキヤツシユ行は、ＩＥによるアクセ
スのための準備であると見なされる（それ以上のＸＩに
関する考察はされない。）いずれの場合も、選択された
デイレクトリのエントリのＵＩＤＣフイールドは、キヤ
ツシユのアクセスが終了する前に、第Ｉ表に指定する規
則により更新される。

選択されたデイレクトリのエントリのＣＨビツトは、Ｉ
Ｅが記憶動作を要求するならばオンにされる。また、キ
ヤツシユミスの場合、“内容（ＣＤＩＤＲ）”は、新し
く取出されたラインに対してエントリのＣＤＩＤのフイ
ールドにゲートされる。“内容（ＣＤＩＤＲ）”≠ＣＤ
ＩＤ０によりＩＥ１０３からのキヤツシユアクセス要求
に対するキヤツシユミスの際、選択された一致クラスに
ＬＲＵラインを置き換える決定がなされる。置き換える
ためのＬＲラインの選択は、米国特許第４３９４７３１
号に採用された方法と同様である。置き換えられたライ
ンが米国特許第４３９４７３１号明細書に特定されるよ
うなそのデイレクトリのエントリにオンのＣＨビツトを
有しているならば、ＭＳの更新がまず実行される。ＩＥ
からの要求に対して、ＭＳから新しく取り出されたライ
ンは、置き換えが選択されたキヤツシユ・ラインの位置
に転送される。この新しく取り出された行のデイレクト
リのエントリは、ＣＤＩＤ←“内容（ＣＤＩＤＲ）”、
ＵＩＤＣ１←“内容（ＵＩＤＣＲ）”、ＵＩＤＣ２←Ｄ
ＵＭＭＹ、ＵＲ←０となるようにリセツトされる。変更
ビツトＣＨもまた、ＩＥ要求が記憶動作に対するもので
ある場合、１にセツトされる。

ＩＥから出されるＦＬＵＳＨ命令の実行のための可能な
実施は第１図のフローチヤートに示されている。第１図
に示されるアルゴリズムは下記のとおりである。キヤツ
シユの一致クラスは、ＦＬＵＳＨ命令のパラメータによ
り示される仕様に合致するデイレクトリのエントリを
（ある場合）探すことにより１つずつ検索される。突き
合わされたデイレクトリのエントリが一致クラスで見つ
かると、ＦＬＵＳＨ命令を実行するため、適当な動作が
とられる。

第１図のデイレクトリのエントリのマツチング１２８の
ための論理図が第６図に示されている。（ＦＬＵＳＨ命
令の入力パラメータＵＩＤから計算された）ＵＩＤＣ１
１２は、ＸＯＲゲート１１６Ａ−１１６Ｄおよび１１７
Ａ−１１７Ｄを使用して、４つの連想性のＵＩＤＣフイ
ールドと比較される。次に、ＯＲゲート１１８Ａ−１１
８Ｄは、一致クラスの４つのエントリのそれぞれが、突
き合わされたＵＩＤＣフイールドを有するかどうかを判
定する。ＸＯＲ回路１１５は、入力ＵＩＤＣがＤＵＭＭ
Ｙであるかどうかを判定し、出力ビツト（入力がＤＵＭ
ＭＹであれば０）をＮＯＲゲート１１８Ａ−１１８Ｄに
供給する。同様に、ＣＤＩＤの入力パラメータは、ＸＯ
Ｒゲート１２０Ａ−１２０Ｄを使用して、一致クラスの
４つのエントリのＣＤＩＤのフイールドに対して突き合
わされる。ＸＯＲゲート１１９は、入力のＣＤＩＤがＣ
ＤＩＤ０であるかどうかを判定するのに使用され出力ビ
ツト（入力がＣＤＩＤである場合は０）はＮＯＲゲート
１２１Ａ−１２１Ｄにゲートされる。ＦＬＵＳＨ命令の
Ｍのパラメータビツトはまずインバータ１２２で反転さ
れ、次にＯＲゲート１２３Ａ−１２３Ｄに入力される。
次に、ＡＮＤゲート１２４Ａ−１２４Ｄは、入力のパラ
メータＵＩＤＣ，ＣＤＩＤおよびＭに対して、一致され
た値を有する一致クラスの全エントリを選択する。

所定の一致クラスの場合、１２８で、１２５Ａ−１２５
Ｄから選択されたエントリがあるならば、各選択された
ラインは、ＦＬＵＳＨ動作１２９にを受けやすい。第７
図は、１２９のためのフローチヤートを提供する。第７
図は、選択ラインのエントリ１２５Ａ−１２５Ｄはそれ
ぞれ、まず１３４で変更フラグＣＨに対してチエツクさ
れる。ＣＨ＝１であると、１３５でライン（またはその
変更）がＭＳに対して更新され（１３５）、ＭＳの更新
の肯定応答を受け取ると、ＣＨビツトはオフにされる。
その後、１３６でＩフラグがＦＬＵＳＨ命令で指定され
るならば、選択されたエントリに対して適当な無効化ス
テツプ１３７がとられる。無効化ステツプ１３７は、第
II表の規則により、ＵＲ，ＵＩＤＣ１およびＵＩＤＣ２
のフイールドを適当に変更することにより実行される。

この発明のキヤツシユの基本操作命令（ＵＩＤ，ＵＩＤ
Ｃ，ＣＤＩＤ，ＣＤＩＤＣ，ＵＲ）およびＦＬＵＳＨ命
令は、ＢＣＥレベル以下の各種の公知の記憶階層設計に
よつて実施されるので、本発明の前述の説明はＢＣＥレ
ベル以下の記憶制御設計の明細について行なう。低レベ
ルの記憶設計は、本発明の良好な実施を提供するのに合
うようになされる。

ユーザおよびデータのためのＵＩＤおよびＣＤＩＤの規
定は、特定のシステム設計に対して行なわれる。

ＳＥＴＵＩＤ ＵＩＤ ＳＥＴＣＤＩＤ ＣＤＩＤ，ＰＡＧＥＩＤ 等の特別な命令、または他の変形命令は、ソフトウエア
規定のために供給される。望むならば、内部レジスタＵ
ＩＤＣＲは、（“ｕｉｄｃ（ＵＩＤ）”の代りにＣＩＤ
を含む他のレジスタＵＩＤＲで置き換えられる。

本発明は、ＳＩＣを用いて説明される。ＳＴキヤツシユ
を有するＭＰまで説明を拡張するのは簡単である。ＳＴ
キヤツシユを使用すれば、ＣＨフラグと関連するすべて
の動作、ならびにキヤツシユ・ラインの置き換えおよび
無効化の際のＭＳ更新は放棄される。

第１図で、ＦＬＵＳＨ命令の実行は、一致フラスに基づ
いて逐次行なわれる。各一致クラスに対して、第６図の
ＰＤのエントリ選択回路は、一致クラスの４つのエント
リのＦＬＵＳＨ命令の仕様のマツチングを並列に実行す
る。ＦＬＵＳＨ命令の実行の良好な実施は、ＦＬＵＳＨ
命令のパラメータに対して、キヤツシユデイレクトリの
エントリの並列マツチングを最適化すべきである。キヤ
ツシユデイレクトリのエントリは、ＦＬＵＳＨ命令の状
態のマツチングに必要なタグは、主としてＣＨ，ＣＤＩ
Ｄ，ＵＩＤＣ１およびＵＩＤＣ２である。設計のこの部
分を最適化する可能性のある方法は、突き合わされるデ
イレクトリのエントリの検索が、個々の一致クラスの読
出しに限定されないように、回路を分離（またはこれら
のタグの余分なコピーを維持）するためにこれらのタグ
のいくつかまたは全部を移動することである。特別に設
計された回路は、より多く（たとえば１６）のデイレク
トリのエントリに対して、同時に並行して第５図の突合
わせ動作を行う。

キヤツシユデイレクトリのエントリのＣＤＩＤタグは、
主としてＦＬＵＳＨ動作のために保持される。ＭＰで
は、余分のキヤツシユ・ラインをＦＬＵＳＨすることは
常に（性能に対して最適ではないけれども）安全であ
る。デイレクトリビツトを節約する１つの実際的な方法
は、各キヤツシユ・ラインのエントリで、ＣＤＩＤタグ
の代りにＣＤＩＤクラス（ＣＤＩＤＣ）タグを使用する
ことである。ＣＤＩＤの場合、８ビツト表示、ＣＤＩＤ
Ｃの場合、４ビツト表示を考察する。２つ以上のＣＤＩ
Ｄは、同一のＣＤＩＤＣと関連づけられる。ＣＤＩＤの
場合、対応するＣＤＩＤＣ（“ｃｄｉｄｃ（ＣＤＩ
Ｄ）”で示す）は、ＣＤＩＤ表示から、ある種のビツト
を抜き取る（または排他的オアをとる）ことにより、計
算される。ＣＤＩＤタグがキヤツシユデイレクトリで使
用されると、ＦＬＵＳＨ命令のエントリ選択回路の入力
線１１３（第６図）は、予め計算され、内部レジスタに
記憶される。“ｃｄｉｄｃ（ＣＤＩＤ）”を（ＣＳＩＤ
の代りに）送るべきである。ＣＤＩＤの計算、およびＣ
Ｄへの共用オブジエクトの割り当ての設計に重要な要素
は、ＦＬＵＳＨ命令の実行が、ＦＬＵＳＨを生じさせる
共用オブジエクトの一部ではないキヤツシユ・ラインに
大きな影響を与えないように、十分なランダム化を提供
することである。

以上、本発明は、実施するＵＩＤおよびＵＩＤＣのオプ
シヨンで説明された。このオプシヨンが必要とされない
場合、キヤツシユデイレクトリのエントリ当たり１つの
明示のＶビツトは、キヤツシユ・ラインの有効性を指示
するために（米国特許第４３９４７３１号明細書に記載
されているように）必要とされる。開示した実施の他の
部分は、ＵＩＤおよびＵＩＤＣの検査および更新に関す
るすべての回路およびステツプを単に除去することによ
り修正される。

本発明は、特に米国特許第４３９４７３１号明細書のＳ
ＩＣキヤツシユ構成フレームワークに基づいて説明され
ている。

Ｅ．発明の効果 本発明は、前述の従来の方法で生じる問題点を解決し、
キヤツシユコヒーレンスを維持するためにキヤツシユの
フラツシユ動作を行なうことにより、効率的な実施が困
難なある種の状態で、ＸＩ制御の必要を除くようにする
という効果がある。

【図面の簡単な説明】

第１図は、ＦＬＵＳＨ実行手順全体のフローチヤート、
第２図は、多重処理構成におけるキヤツシユおよびデイ
レクトリを示すブロツクダイアグラム、第３図は、修正
した従来の四元セツト連想キヤツシユの詳細なブロツク
ダイアグラムである。この図には、デイレクトリのエン
トリの新しいフイールドＣＤＩＤ，ＵＩＤＣ１およびＵ
ＩＤＣ２、ならびに関連する一部の制御回路、第４図は
ＣＰのキヤツシユデイレクトリのヒツト／ミス検出回
路、第５図は、各ＣＰのキヤツシユデイレクトリのエン
トリのタグビツト、第６図は、各一致クラスでのＦＬＵ
ＳＨ実行のための制御回路、第７図は、ＦＬＵＳＨ命令
のパラメータによつて指定された条件に一致することが
わかつた一致クラスにキヤツシユ行のエントリがある場
合の、キヤツシユ一致クラスでのＦＬＵＳＨ実行のフロ
ーチヤートを示す。 １１５、１１９……ＸＯＲ回路、１２２……インバー
タ、１２８……デイレクトリのエントリ突き合わせ部。

Claims (1)

【特許請求の範囲】
1. 【請求項１】複数の中央処理装置と、この中央処理装置
   によつて共用される主記憶装置とを有し、各中央処理装
   置はキヤツシユ及びデイレクトリを有し、このデイレク
   トリは複数の情報のラインエントリを有し、この情報の
   ブロツクは少なくとも１ラインから構成され、制御定義
   域は少なくとも１つの情報のブロツクとして、規定さ
   れ、各ラインエントリはラインが属する前記制御定義域
   を識別する制御定義域識別フラグと、前記主記憶装置へ
   の最後の更新以後前記ラインが変更されたことを示す１
   方の状態及び前記主記憶装置への最後の更新以後前記ラ
   インが変更されなかったことを示す他方の状態を有する
   変更フラグを含む多重プロツセサシステムのキヤツシユ
   を制御する方法において、 前記主記憶装置から前記キヤツシユに転送される情報の
   任意のブロツクの各情報ラインの前記制御定義域フラグ
   を情報の前記任意のブロツクの前記制御定義域を識別す
   るように設定し、 所与の中央処理装置に関連した前記キヤツシユから所定
   の制御定義域識別フラグを有する情報ラインを取除くた
   めに前記所定の制御定義域識別フラグを含むＦＬＵＳＨ
   コマンドを前記所与の中央処理装置によつて発行し、 前記ＦＬＵＳＨコマンドの前記制御定義域識別フラグと
   前記関連キヤツシユの情報ラインの前記制御定義域識別
   フラグとを比較し、前記制御定義域識別フラグが一致す
   れば、前記関連キヤツシユから一致した前記制御定義域
   識別フラグを有するラインを取除き、 前記キヤツシユの変更されたラインのみに前記ＦＬＵＳ
   Ｈコマンドが作動する１方の状態及び前記ＦＬＵＳＨコ
   マンドが変更されたライン及び変更されないラインに作
   動する他方の状態を示す修正フラグが前記１方の状態を
   示すと共に前記変更フラグが前記１方の状態を示す場合
   のみ前記キヤツシユから前記情報ラインを取除くように
   したことを特徴とする多重プロセツサシステムのキヤツ
   シユを制御する方法。