JPH04260146A

JPH04260146A - データ・アクセス管理装置および方法

Info

Publication number: JPH04260146A
Application number: JP3268665A
Authority: JP
Inventors: Philip G Emma; フィリップ・ジョージ・エマ; Joshua W Knight; ジョシュア・ウィルソン・ナイト; Kevin P Mcauliffe; ケビン・パトリック・マコウリフィー; James H Pomerene; ジェイムス・ハーバート・ポメレーヌ; Rudolph N Rechtschaffen; ルドルフ・ネイザン・リヒトシャーフェン; Frank J Sparacio; フランク・ジョン・スパラシオ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1990-10-31
Filing date: 1991-09-20
Publication date: 1992-09-16
Anticipated expiration: 2010-07-05
Also published as: US5291442A; JPH0762836B2

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般にキャッシュ・メ
モリ管理方法に係り、特に各々のプロセッサが専用キャ
ッシュを備えると共に共通主メモリ（ＭＭ）を共有する
多重プロセッサ（ＭＰ）データ処理システムにおけるキ
ャッシュ・メモリの制御に関する。

【０００２】

【従来の技術】キャッシュ・メモリは、コンピュータ・
システムにおいて処理ユニットの一体要素としてパッケ
ージされており、その大きさは主メモリよりはるかに小
さいのが一般的である。このキャッシュ・メモリの目的
は、プロセッサと主メモリの間でバッファとして働き、
主メモリをそれよりはるかに速いアクセス時間でエミュ
レートすることにある。キャッシュ・メモリは、主メモ
リより小さいので、キャッシュ・メモリは単に任意の時
点で主メモリの記憶内容のサブセットを収容することに
のみ用いられる。主メモリのどの部分がキャッシュ・メ
モリ内にあるかを識別するディレクトリがキャッシュ内
で使用される。

【０００３】キャッシュ内にいかなるデータを保持する
かを選択する方法は、次の２つの観測可能な現象の経験
的な観測に基づく発見的なものである。すなわち、それ
らの現象の１つは、参照される項目がある一時的ウイン
ド内で１度以上参照され易いという観測である“参照の
一時的局所性”という現象であり、他の１つは、参照項
目に近い（アドレスによる）項目がそれぞれ一時的ウイ
ンド内で参照され易い観測である“参照の空間的局所性
”という現象である。参照の時間的局所性とはキャッシ
ュ中の最も最近参照された項目を保持する合理性、例え
ば新たに参照された項目が最近参照された可能性が最も
少ない項目に置き代わるようにキャッシュが管理される
合理性を意味するものである。空間的参照局所性は単に
実際に参照されている特定項目よりむしろ、キャッシュ
中のデータの連続する“固まり（ｃｈｕｎｋｓ）”（キ
ャッシュ・ラインと呼ばれる）を格納するための理論的
根拠を与えるものである。例えば、キャッシュ・ミスに
応じて全ライン（例えば３２ワード）は主メモリからキ
ャッシュに転送されるのが普通である。命令を含むライ
ンはより一層空間的参照の局所性を示そうとし、データ
を収容するラインは一層時間的参照の局所性を示そうと
するのが普通である。

【０００４】キャッシュの容量が固定されている場合は
、キャッシュ設計時の最も重要なパラメータはライン・
サイズ（すなわち、各々のキャッシュ・ライン中のワー
ド数）とキャッシュ管理ストラテジィである。ライン・
サイズの選択は利用している参照の時間的および空間的
局所性の間の妥協に基づいてなされる。大きなライン・
サイズは空間的局所性を促進するが、固定されたキャッ
シュ容量に対して格納されるラインがメモリに戻される
前の時間長を短縮し、時間的局所性を犠牲にするもので
ある。

【０００５】大きなライン・サイズはキャッシュ・ミス
・ペナルティを増加させる。このキャッシュ・ミス・ペ
ナルティには、キャッシュ・ミス（キャッシュに現在格
納されていない項目へのプロセッサによる参照）を認識
し、主メモリからキャッシュにラインを転送するのに必
要な時間量が含まれる。このライン・サイズを、空間的
な参照の局所性を促進するのに必要なものより大きくす
ることは望ましくない。一方、ライン・サイズが小さす
ぎるときは、空間的局所性が犠牲になり、キャッシュ・
ミスがしばしば発生するようになる。その場合、キャッ
シュ・ディレクトリの大きさがライン・サイズの選択に
際して問題になる。一般に、キャッシュ・ディレクトリ
の大きさは、キャッシュ中のライン数に比例して与えら
れる。

【０００６】単一プロセッサ・システムにおけるキャッ
シュ・ミス・ペナルティを低減させる従来の方法は、キ
ャッシュのセクタ化により与えられる。この方法はＩＢ
Ｍ３／３６０　　Ｍｏｄｅｌ（商標）などの初期の市販
キャッシュ・システムで用いられたものである。しかし
ながら、この方式におけるライン・サイズは今日のマシ
ンに比して比較的大きく、キャッシュ・ミス・ペナルテ
ィが過剰になる可能性があった。上記セクタ化法におい
ては、キャッシュ・ラインは“セクタ”からなると考え
られ、このセクタにおいてはセクタ・サイズは、キャッ
シュと主メモリの間のバスの幅の倍数となすのが普通で
ある。キャッシュ・ミスが生じると、キャッシュ内には
十分なスペースが留保されて全体のラインを保持するが
、参照項目を収容するセクタのみはキャッシュに転送さ
れる。この方法によると、小さなディレクトリは大きな
ライン・サイズで維持され、過剰なミス・ペナルティを
受けることはない。

【０００７】単一プロセッサ・システムにおいてセクタ
化キャッシュを実施することが要求されるキャッシュ・
ディレクトリに対する唯一の変更は、各々のディレクト
リ・エントリ（ラインに対応する）がライン中にセクタ
あたり１“常駐”ビットを含むという点にある。これら
のビットは、ライン中のセクタのいずれかがキャッシュ
に常駐しているかを示すものである。

【０００８】単一プロセッサ・システムにおけるセクタ
化も、一方が大きな空間的局所性（例えば命令ライン）
を有し、他方がより小さな空間的局所性（例えばデータ
ライン）を有する２種類のラインが存在する環境で動機
付けを行うことができる。このような環境においては、
命令ラインに対するミスは全体のラインの転送をもたら
し、これにより将来の不要なミスを回避でき、またデー
タ・ラインに対するミスは関係するセクタのみの転送を
もたらし、したがって不要なミス・ペナルティを回避す
ることができる。

【０００９】キャッシュ管理ストラテジィには通常は最
低使用頻度（ＬｅａｓｔＲｅｃｅｎｔｌｙ　　Ｕｓｅｄ
（ＬＲＵ））ストラテジィの変形としての置換えアルゴ
リズムが知られている。多重プロセッサ・システムの場
合は、キャッシュ管理ストラテジィには、システム中の
プロセッサが記憶のコヒーレントな視野を共有するよう
にラインのオーナシップを決定するアルゴリズムも含ま
れている。コヒーレンシィとは、所与のプロセッサによ
りなされるメモリ位置への格納動作が他のプロセッサに
よる同じメモリ位置に対してなされるフェッチ動作によ
り観測されることを意味する。コヒーレンシィは、所与
のプロセッサでキャッシュされたデータが他のプロセッ
サによりなされる格納動作の結果として使用されなくな
る時点を決定する手段を与えるものである。

【００１０】多くのシステムにおいて、コヒーレンスは
“排他的”ビットを用いて実現される。キャッシュ・デ
ィレクトリ内の各々のエントリは排他的ビットを含んで
いる。このビットが所与のプロセッサのキャッシュ・デ
ィレクトリにセットされたときは、他のいかなるプロセ
ッサもそのキャッシュ内に対応するラインを有する必要
はない。また、このビットがキャッシュ・ディレクトリ
にセットされていないときは、他のプロセッサは対応す
るラインのコピーを有してもよいが、いかなるプロセッ
サもラインにデータを格納することはできない。

【００１１】ラインは、そのディレクトリのエントリが
排他的ビットの組を有するときは“排他的に保持される
”といわれる。この場合、プロセッサは排他的に保持さ
れるラインに単に格納できるだけである。格納動作が生
じると、ラインはこのラインに対するディレクトリ・エ
ントリに“変更された”ビットを設定することにより“
変更された”とマークされる。常駐ラインに対して排他
的ビットが設定されないときは、ラインは“読出し専用
に保持される”といわれる。

【００１２】キャッシュにより変更されたラインが主メ
モリに書き込まれたときは、それは“キャストアウト”
といわれ、またこの動作も「キャストアウト」といわれ
る。“相互無効（ｃｒｏｓｓ　　ｉｎｖａｌｉｄａｔｅ
）ＸＩ”とは、リモート・プロセッサのキャッシュ中の
ラインを無効にする作用、すなわちそのラインを非常駐
とマークする作用である。“読出し専用動作に排他的な
変更（ｃｈａｎｇｅ　　ｅｘｃｌｕｓｉｖｅ　　ｔｏ　
　ｒｅａｄ　　ｏｎｌｙ（ＣＥＲＯ）”とは、排他的ビ
ットをリセットすることによりラインの状態を読出し専
用に排他的に保持されることからリモート・プロセッサ
を変化させることである。ＸＩまたはＣＥＲＯが、キャ
ッシュ内に配置されてから変化したラインに対して行わ
れるとき、このラインはキャストアウトされなければな
らない。排他的ビットを用いた通常のコヒーレンシィ・
スキームは、次のように、すなわちフェッチ動作が全て
の常駐ラインから許容されるように行われる。ミスを発
生するフェッチ・リクエストは、最終的にはラインが読
出し専用に保持されることをもたらす。ミスの時点でリ
モート・プロセッサによりラインが排他的に保持される
ときは、そのプロセッサにＣＥＲＯが送出され、要求し
ているプロセッサに対してラインのコピーを送出する前
にキャストアウトが行われる。これにより、ミスを発生
するプロセッサはラインの現在のコピーを受信すること
が保証される。

【００１３】格納動作は排他的に保持された常駐ライン
に対して単に許容されるのみである。ミスを発生する格
納リクエストは、最後には、要求されたラインが排他的
に保持されることをもたらす。この要求されたラインが
ミスの発生時にリモート・プロセッサにより排他的に保
持されるときは、そのプロセッサに対してＸＩが送出さ
れ、そのプロセッサは要求しているプロセッサにライン
のコピーを送出する前にラインに対してキャストアウト
動作を行う。ミスの発生時に任意のリモート・プロセッ
サによりラインが読出し専用に保持されたときは、要求
しているプロセッサに対してラインのコピーを送出する
以前に全ての上記のようなプロセッサに対してＸＩＳ　
が発生される。これらのＸＩＳ　によりリモート・プロ
セッサはラインを無効にマークする。このステップによ
り、他のいかなるプロセッサもミスなしにこのラインか
ら取り出すことはできないことが保証される。リモート
・プロセッサが引き続いてミスするときは、それはロー
カル・プロセッサによりなされている任意の記憶装置を
観測することを可能にする。

【００１４】読出し専用に保持される常駐ラインに対し
て試みられる格納動作は、先ず、ラインを読出し専用に
保持するリモート・プロセッサにＸＩＳ　を送出させ、
この手順はラインを排他的に保持するときになされる手
順に類似している。しかし、この場合は、共に起動され
るローカル・プロセッサにこのラインが常駐しているの
で、他のいかなるプロセッサもこのラインを排他的に保
持することはできない。この意味で排他的ラインを得る
動作は“いかなるデータも取り出さない（ｆｅｔｃｈ　
　ｎｏ　　ｄａｔａ）”すなわちＦＮＤと呼ばれる。

【００１５】以上の説明はストアイン・キャッシュの動
作に対するものである。ストアイン・キャッシュとは、
キャッシュ内に常駐しないラインに対しては格納動作は
行うことができないものである。格納リクエストが非常
駐ラインに対してなされるときは、ミスが発生され、ラ
インは、格納が許容される前にキャッシュ中にもたらさ
れる。さらに、ラインに対して、その常駐動作時になさ
れるその格納動作およびその他の格納動作は、ラインが
キャストアウトされるまで主メモリに反映されることは
ない。多重格納動作はラインに対して、それが常駐して
いるときなされるので、このラインに対して格納動作が
なされる順序はキャストアウトの時点では決定できない
。全ての格納動作はシステムに対してはキャストアウト
の時点で同時になされているように見える。

【００１６】ストアイン・キャッシュにおいてコヒーレ
ンシィを保証するためには、排他的制御が要求される。プロセッサがデータを格納しているとき、他のプロセッ
サがこれらの変化を観測することは不可能であり、した
がってこれらの変化は偶然の順に観測することはできな
い。他のプロセッサが変化を観測しようとするときは（
キャストアウトを強制するＣＥＲＯリクエストを介して
）、論理的に行われている全ての変化を観測することが
保証される。このようにして、排他的制御は任意のスト
アイン・キャッシュに対しては暗黙的なものである。

【００１７】一方、ストアスルー・キャッシュは排他的
制御は必要としない。ストアスルー・キャッシュは、格
納動作が生じるごとに主メモリが更新されるものである
。格納動作が生じたとき主メモリは整合状態になされる
ので、ストアスルー・キャッシュではキャストアウトは
必要とされない。ストアスルー・キャッシュには次のよ
うな基本的な３種類のものがある。

【００１８】Ｗｒｉｔｅ−Ｔｈｒｏｕｇｈ，　　排他的
管理のあるＷｒｉｔｅ　　Ａｌｌｏｃａｔｅ　　（ＷＴ
ＷＡＸ），Ｗｒｉｔｅ−Ｔｈｒｏｕｇｈ，　　排他的管
理のないＷｒｉｔｅ　　Ａｌｌｏｃａｔｅ　　（ＷＴＷ
Ａ），Ｗｒｉｔｅ−Ｔｈｒｏｕｇｈ，　　排他的管理の
ないＮｏ　　Ｗｒｉｔｅ　　Ａｌｌｏｃａｔｅ　　（Ｗ
ＴＮＷＡ）。

【００１９】ＷＴＷＡＸキャッシュはストアイン・キャ
ッシュと同様に動作するが、格納動作が、これらが発行
された時点で主メモリを通して格納し、したがっていか
なるキャストアウトも存在しないという点で異なってい
る。各々の格納動作は個別事象として主メモリに発され
るので、所定ラインには１度に１つのプロセッサのみを
格納することができる。各プロセッサのキャッシュ・メ
モリからの全てのメモリ動作はシステム制御要素（ＳＣ
Ｅ）を通してチャネル化される。このＳＣＥは、所与の
プロセッサからの格納動作命令が出される順に常にそれ
らの格納動作を受けるものである。この順序を留保する
特定の作用は何もなされない。

【００２０】ＷＴＷＡキャッシュはＷＴＷＡＸキャッシ
ュと同様に動作するが、排他的管理が存在しない点で異
なっている。このように排他的管理がないとキャッシュ
間のコヒーレンシィを保証するために、プロセッサは一
層厳しい規則に従わなければならない。例えば、プロセ
ッサによるＳＣＥに対する格納リクエストにしたがって
、ＳＣＥはラインが他のキャッシュに常駐するか否かを
決定しなければならない。もしそうなら、ＳＣＥは他の
キャッシュに指令を出してそれらのラインのコピーを無
効にし、主メモリに新しいデータを格納する前に上記コ
ピーが無効にされた旨の肯定応答を待たなければならな
い。この時ＳＣＥは開始プロセッサに、格納動作が生じ
た旨を通知しなければならない。

【００２１】ＷＴＮＷＡキャッシュはＷＴＷＡキャッシ
ュに類似しているが、ラインが記憶装置上に割り付けら
れないという点でさらに簡単化される。すなわち、非常
駐ラインに対する記憶装置はミスを発生しない（これは
、変化がストアスルーされる前にラインが主メモリから
検索されることをもたらす）。

【００２２】上記のキャッシュ管理ストラテジィの全て
において、ラインを格納する作用は、コヒーレンシィを
維持するために、そのラインのコピーをリモート・キャ
ッシュにおいて無効にする。リモート・プロセッサが、
ローカル・プロセッサと同じラインに格納することを逐
次試みるときは、ミスが発生し、またローカル・プロセ
ッサのキャッシュ・メモリにおけるラインの現在のコピ
ーは無効にされる。これは、２つ以上のプロセッサが同
じライン内を異なるワードで動作しているときは（以後
クローズ書込みシェアリング（ｃｌｏｓｅ　　ｗｒｉｔ
ｅ　　ｓｈａｒｉｎｇ）と呼ぶ）、キャッシュの使用を
非効率的にする。２つのプロセッサは同一ワードでは動
作していないが、ラインは、異なるプロセッサがライン
に対して取出しまたは格納するごとにミスおよびＸＩＳ
　を介してキャッシュ間を“ピン・ポン”することにな
る。

【００２３】米国特許第４，４４５，１７４号明細書に
は、上記のような多重処理システムに対するクローズ書
込みシェアリングの問題を解消する方法がその特徴とし
て示されている。この特許においては、各々のプロセッ
サはそれ自身のキャッシュを有しており、また共有キャ
ッシュが付加されている。同一ラインの読出し専用コピ
ーが全ての私用キャッシュに同時に存在する。共有され
、変更されるラインは、各々のプロセッサが格納し、取
り出すことができる共通の共有キャッシュに格納される
。局所的な私用キャッシュにミスがあると、リモート私
用キャッシュから共有キャッシュへのライン転送がもた
らされる。このような場合は、転送によるミス・ペナル
ティは主メモリからラインを検索することに起因するミ
ス・ペナルティより小さい。

【００２４】米国特許第４，４８４，２６７号明細書に
はハイブリッド・キャッシュ・システムが示してあり、
このシステムにおいては“共有（ｓｈａｒｅｄ）”ライ
ンはＷＴＷＡＸストアスルー・キャッシュにおけるもの
として処理される。一方“非共有（ｎｏｎ−ｓｈａｒｅ
ｄ）”ラインはストアイン・キャッシュにおけるものと
して処理される。キャッシュに付加された新しいライン
はストアインとして処理される。第２プロセッサがこの
ラインからの取出しまたはこのラインへの格納を開始す
ると、このラインはストアスルー・ラインに変更される
。このハイブリッド・システムは、非共有ラインが最小
数のキャストアウトと共にストアイン・キャッシュの性
能的な利点を得ることを許容する。共有ラインに対して
は、ラインをストアインからストアスルーに変化させる
第１ＣＥＲＯまたはＸＩがキャストアウトをもたらす。続くＣＥＲＯおよびＸＩは排他的制御を変化させるが、
キャストアウトおよび関連する遅延はもたらさない。こ
のシステムの欠点は、キャッシュへの格納に続いて、ラ
インが、これが主メモリにストアスルーされるまでロー
カル・プロセッサまたはリモート・プロセッサによりア
クセスされ得ないことにある。さらに、ラインが共有さ
れるときは、プロセッサによるラインへの格納は全ての
リモート・プロセッサのキャッシュ・メモリ中のライン
を無効にし、リモート・プロセッサに次の参照に際して
主メモリからラインを取り出させる。

【００２５】

【発明が解決しようとする課題】すでに説明したように
、ストアイン・キャッシュを有する多重プロセッサ・シ
ステムにおいては、コヒーレンシィの維持は一度にただ
１つのプロセッサがライン内のダブルワード（ＤＷ）に
対して排他的制御を得ることを許容することによりなさ
れた。クローズ書込み共有の場合には、２つ以上のプロ
セッサは、例えこれらのプロセッサが同一ワードに対し
て動作してなくても同じラインをキャストアウトし検索
する遅延に繰り返して遭遇する。

【００２６】

【課題を解決するための手段】本発明はダイナミックな
キャッシュ・セクタ化システムにおいて具体化され、こ
のシステムにおいては多重処理システムの各プロセッサ
は排他的管理を有する私用キャッシュを備えており、さ
らに共有の共通主メモリが設けてある。このシステムで
は、多重プロセッサにより同一ラインの異なるワードに
対して同時的格納および取り出し動作が可能になる。

【００２７】ダイナミック・キャッシュ・セクタ化シス
テムに結合された各々のプロセッサは、変更ライン・ス
タック（ＭＬＳ）を有しており、その内容はローカル・
プロセッサが最近データを格納したキャッシュ中のライ
ンを識別するものである。ラインがキャッシュにもたら
された後、ローカル・プロセッサによるそのラインに対
する第１の逐次格納動作により、そのラインが最近変更
されたと識別するＭＬＳにエントリを形成する。このＭ
ＬＳはさらに、ＭＬＳに入力された後各々のライン内の
どのダブルワードが変更されているかを識別する。

【００２８】各々のプロセッサはさらに、異なるプロセ
ッサがディスジョイントな組のＤＷに対してフェッチ動
作または格納動作を行うラインを記録するセクタ化ライ
ン・ディレクトリを保持する。最近変更されたライン（
すなわち、ＭＬＳ内にエントリが存在するライン）にリ
モート・プロセッサがアクセスすると、このリモート・
プロセッサがローカル・プロセッサにより変更された同
じＤＷまたは異なるＤＷをアクセスしているか否かを判
定するチェックがなされる。後者の場合にのみラインは
セクタ化に対して資格を有する。

【００２９】ラインは、それぞれが１つ以上のＤＷを含
むセクタに分割することができる。本発明のシステムは
、個々のセクタが異なるプロセッサにより排他的に保持
される（格納アクセスに対して）ようにセクタ化ライン
が“排他的に共有”保持されることを可能にする。多重
プロセッサによるフェッチおよび格納動作は、リモート
・プロセッサにより排他的に保持されるセクタに対して
プロセッサがフェッチまたは格納動作を試みないときは
共有排他的ラインがキャストアウトさせない。

【００３０】

【実施例】次に、本発明によるダイナミック・キャッシ
ュ・セクタ化方式について例示する。

【００３１】本発明は図１に示した多重プロセッサ・シ
ステムにおいて具体化される。この多重プロセッサ・シ
ステムにおいては、各々のプロセッサは私用キャッシュ
・メモリを有し、また各プロセッサはシステム制御要素
と主メモリを有している。各々の私用キャッシュは変更
ライン・スタックおよびセクタ化ライン・ディレクトリ
を有している。

【００３２】単一データ・ラインに使用するプロセッサ
間の競合がない場合は、このシステムは従来のストアイ
ン・キャッシュと同様に機能する。ラインがキャッシュ
に常駐し、さらにキャッシュ制御・ディレクトリ２２ま
たは２４で有効とマークされたときはキャッシュ・アレ
イ１８または２０からダブルワードが取り出され、さら
にラインが有効であり各ローカル・プロセッサ２または
４の排他的制御下にあるとしてマークされたときはＤＷ
エントリが格納される。

【００３３】従来技術に含まれてない付加的なステップ
が行われる。すなわち、キャッシュ中のラインが変更さ
れると、そのアドレスは変更ライン・スタック（ＭＬＳ
）３４または３６に入力され、さらに変更されたＤＷＳ
　はＭＬＳ３４または３６で変更されたと識別される。リモート・プロセッサがＸＩを介してローカル・キャッ
シュのラインをアクセスしようとするときは、変更ライ
ン・スタック３４または３６の対応するエントリがチェ
ックされる。このアクセスの試みが最近変更されてない
（クローズ・ライト共有）セクタのＤＷに対するもので
あるときは、ラインはセクタ化されたとマークされる。このラインは各々のプロセッサのセクタ化されたライン
・ディレクトリに入力され、各々のプロセッサに対する
読出し・書込みおよび読出し専用アクセスに対して上記
セクタの識別が可能になされる。

【００３４】本発明は従来技術との比較により最良に理
解される。図２は多重プロセッサ構成における従来のス
トアイン・キャッシュを示すブロック図である。このシ
ステムのプロセッサ２および４の各々は、それぞれのキ
ャッシュ制御・ディレクトリ（ＣＣＤ）７４および８０
と共にそれぞれ私用キャッシュ・メモリ１８および２０
を有する。このシステムは単一システム制御要素（ＳＣ
Ｅ）９０および共有主メモリ９６を有する。

【００３５】キャッシュ１８の各々のバス１８ａはキャ
ッシュ制御・ディレクトリ７４に関連するエントリを有
する。ＣＣＤエントリはバス７４ａのアドレス（Ａ）お
よびキャッシュ常駐ラインの状態を示す３つのフラグ・
ビット７４ｂ〜ｄを含んでいる。これらのフラグ・ビッ
トは“有効”（Ｖ）ビット７４ｂ、“変更”ビット（Ｃ
）７４ｃ、および“排他的”ビット（Ｅ）７４ｄである
。Ｖビット７４ｂが１にセットされると、ラインが使用
可能になる。Ｖビット７４ｂが０のときは、ラインはフ
ェッチまたは格納に対してアクセスされない。システム
の初期化に際しては全てのＶビットは０にリセットされ
る。キャッシュのラインが格納動作により変更されると
Ｃビット７４ｄがセットされる。

【００３６】システム制御要素９０は私用キャッシュ制
御・ディレクトリの全てのコピーを有している。例えば
、９０Ａおよび９０Ｂとマークされた項目は、それぞれ
のＣＣＤ７４および８０のコピーである。

【００３７】図５および図６は、図２に示した従来のキ
ャッシュ・システムにおいてフェッチ，格納，ＣＥＲＯ
，およびＸＩ動作が通常行われるプロセスを示す図であ
る。ステップ２００において、プロセッサ２はバス７０
を介してデータのためのリクエストをキャッシュ制御・
ディレクトリ７４に送出する。このリクエストは要求さ
れたデータのアドレス７４およびリクエストの種類（フ
ェッチまたは格納）の両者を含んでいる。ステップ２０
２において、このリクエストが格納リクエストでないと
きは、それはフェッチ・リクエストでなければならない
。

【００３８】ステップ２０４においてＣＣＤ７４は要求
されたデータを含むラインがキャッシュ１８に常駐する
か否かを決定する。要求されたラインに対するＶビット
７４ｃがセットされたときは、ラインはキャッシュ１８
中に常駐し、使用可能になる。これはフェッチ・ビット
である。この場合、バス１８ａはステップ２０６でバス
６を通してキャッシュ１８からプロセッサ２に転送され
る。

【００３９】ステップ２０４でラインが非常駐のときは
、キャッシュ制御・ディレクトリはキャッシュ１８中の
ラインを選択してステップ２４０で要求されたラインと
置き換えられる。この置き換えられたラインがステップ
２４２で変化されたとマークされると（変更ビット７４
ｄにより示される）、キャッシュ制御・ディレクトリ７
４はアドレスおよびバス５６を通じシステム制御要素９
０に対してキャストアウトが必要とされる旨の情報を送
出し、続いてステップ２４４でバス４２を通してデータ
を転送する。ＳＣＥは主メモリ９６に（バス５８を介し
て）アドレスを、さらに（バス５６を介して）データを
送出する。主メモリに対してキャストアウト・ラインが
コピーされると、キャストアウト・ラインはステップ２
４６で無効にされる（Ｖビット７４ｂが０にリセットさ
れる。）。

【００４０】置き換えられるラインがステップ２４２（
Ｃビット７４ｄは０に等しい。）で変更されないときは
、Ｖビット７４ｂは直ちに０にリセットされ、さらに廃
棄されたラインを主メモリ９６に書き戻す必要はなくな
る。

【００４１】キャッシュ１８でスペースが得られるよう
になされると、ステップ２４８でＣＣＤ７４は要求され
たデータを含むラインに対するリクエストをバス８２を
通してＳＣＥ９０に送出する。ステップ２０８において
、ＳＣＥ９０はその他のキャッシュ・メモリ（例えば９
０ｂ）に対するそのディレクトリを調べ、ラインが他の
キャッシュ７６で排他的に保持されたか否かを知ること
になる。もしそうなら、ＳＣＥ９０はリモート・キャッ
シュ制御・ディレクトリに８０に要求してステップ２１
０でラインに対して読出専用に排他的な変更を行う（ａ
　　ｃｈａｎｇｅ−ｅｘｃｌｕｓｉｖｅ−ｔｏ−ｒｅａ
ｄ−ｏｎｌｙ（ＣＥＲＯ））。

【００４２】ステップ２１２でラインが変更されると、
変更されたデータはバス４４を介してリモート・キャッ
シュ・アレイ２０からＳＣＥ９０に送出され、さらにス
テップ２１４で、ＳＣＥはバス５８を通してアドレスを
、さらにバス５６を通してデータを主メモリ９６に送出
する。ラインがキャストアウトされた後、リモート・キ
ャッシュ制御・ディレクトリ８０はキャストアウト・ラ
インに対するＣＣＤエントリでＶ，ＥおよびＣビットを
０にリセットする。次に、ステップ２１６で、ＳＥＣ９
０は、いかなるキャッシュもラインを排他的に保持しな
いときは、そのまま進み、ラインに対するバス５８を通
して主メモリ９６にリクエストを送出する。

【００４３】フェッチ・リクエストに応じて、データは
バス５６を通してＳＣＥに、次にバス４２を通してキャ
ッシュ・アレイ１８に転送され、さらにＳＣＥはその内
部テーブル９０ａ〜ｂを更新する。次に、ＣＣＤはライ
ンに対する対応するＣＣＤエントリにおいてＶビットを
１にセットし、ＥおよびＣビットを０にセットする。次
に、要求されたデータはバス６を通してプロセッサ２に
送出される。

【００４４】ステップ２０２において、リクエストが格
納のときは、要求された位置のアドレスおよびリクエス
トの種類がフェッチ・リクエストに関してＣＣＤ７に送
出される。格納のためバス１８ａにアクセスするために
は、Ｖビットはステップ２２０で１でなければならず、
またＥビットもステップ２２２で１でなければならない
。

【００４５】ステップ２２２においてＶビットは１にセ
ットされるが、Ｅビットは０にセットされたときは、他
のキャッシュはラインの読出し専用コピーを有してもよ
い。この場合には、フェッチ・ノー・データ（ＦＮＤ）
コマンドがステップ２２４で送出され、キャッシュ１８
がラインを通して排他的制御を得ることを許容する。こ
のコマンドに応じて、ＣＣＤ７４はリモート・キャッシ
ュ２０中のラインに対するＸＩをバス８２を通してＳＣ
Ｅ９０に送出する。ＳＣＥ９０は他のディレクトリ８０
のその内部コピーから、ラインが他のキャッシュ２で読
出し専用に保持されたか否かを決定する。この場合、リ
モート・キャッシュ２０中のそのラインを無効にするこ
とが必要になる。ＣＣＤ８０のラインに対するＶビット
が１のときは、ラインはプロセッサ４により読出し専用
に保持され、またＳＣＥ９０はステップ２２４において
バス４４を通してリモートＣＣＤ８０にリクエストを送
出する。ＣＣＤ７４におけるラインに対するＶビットは
１にセットされているので、リモート・プロセッサはこ
のラインの排他的制御を持つことはできず、またプロセ
ッサ４はこのラインを変更することもできない。

【００４６】リモートＣＣＤ８０が要求されたラインに
対してＥビットをリセットすると、ＳＣＥ９０はそのデ
ィレクトリの内部コピーを更新し、バス８２を通してＣ
ＣＤ７４に通知する。ステップ２３６でＣＣＤ７４のラ
インに対するＥビットが１にセットされ、さらにプロセ
ッサ２はラインを通して排他的制御を有するようになる
。ここでプロセッサ２はステップ２３８においてバス６
を通してキャッシュ１８にデータを転送することができ
る。

【００４７】ステップ２２０において要求されたライン
がローカル・キャッシュ１８中にないときは、キャッシ
ュ制御・ディレクトリはステップ２５０でキャッシュ１
８中のラインを選択して要求されたラインと置き換える
ように作用する。置き換えられるラインがステップ２５
２で変更されると（ラインに対するＣビットにより示さ
れるように）、キャッシュ制御・ディレクトリはアドレ
スおよびキャストアウトが必要とされる旨の情報をバス
５６を通してシステム制御要素９０に送出し、ステップ
２５４でバス４２を通してデータを引き続き転送する。さらに、ＳＣＥはアドレス（バス５８を介して）および
データ（バス５６を介して）主メモリ９６に送出する。キャストアウト・ラインが主メモリにコピーされると、
このキャストアウト・ラインはステップ２５６で無効に
される（すなわち、そのＶビットが０にリセットされる
。）。

【００４８】ステップ２５２で置き換えられるべきライ
ンが変更されたとしてマークされたことが見出されない
ときは（すなわち、そのＣビットが０に等しいときは）
、廃棄されたラインを主メモリ９６に書き込む必要はな
いので、ラインに対するＶビットは直ちに０にリセット
される。

【００４９】キャッシュ１８でスペースが得られるよう
になされると、ステップ２５８でキャッシュ制御・ディ
レクトリ７４は、バス８２を通して、要求されたデータ
を含むラインに対するリクエストを送出する。ＳＣＥは
、ステップ２２５でそのディレクトリ９０ｂを調べて、
他のキャッシュ７６にラインが常駐するか否かを検討す
る。もしそうなら、ステップ２２ｂではリモート・キャ
ッシュ８０に対して相互無効（ＸＩ）動作が行われ、リ
モート・キャッシュ８０がラインを、このラインが排他
的に保持されると共にそのＶビットをリセットするよう
に変更されたとき、キャストアウトすることをもたらす
。

【００５０】次に、ＳＣＥ９０は、いかなるキャッシュ
もラインを保持しないといはそのまま進み、ステップ２
３４でラインに対してバス５８を通して主メモリ９６に
リクエストを発する。このデータはバス５６を通してＳ
ＣＥに、次にバス４２を通してキャッシュ・アレイ１８
に転送される。ステップ２３４で、ＳＣＥはまた内部テ
ーブル９０ａ〜ｂを更新する。さらに、ステップ２３６
で、キャッシュ制御・ディレクトリ８０はＶ，Ｅおよび
Ｃビットを１にセットする。次に、格納されるべきデー
タ値がバス６を通してプロセッサ２からキャッシュ１８
に送出される。

【００５１】図１は、本発明の実施例を含む改良された
多重プロセッサ・システムを示すブロック線図である。このシステムのプロセッサ２および４の各々は、それぞ
れの私用キャッシュ・メモリ１８および２０を有する。キャッシュ・メモリ１８および２０の各々は、それぞれ
のキャッシュ制御・ディレクトリ（ＣＣＤ）２２，２４
、変更ライン・スタック（ＭＬＳ）３４，３６、および
セクタ化ライン・ディレクトリ（ＳＬＤ）３０，３２に
結合される。さらに、このシステムは単一システムの制
御要素（ＳＣＥ）５４および共有主メモリ６０を有する
。

【００５２】ＣＣＤ２２，２４は、これらがそれぞれの
キャッシュ・アレイ１８，２０中の各ラインに対して付
加的なフィールドＳを有するという点でＣＣＤ７４，８
０とは異なるものである。このフィールドＳ（２２ｅ）
はラインが“共有排他的（ｓｈａｒｅｄ　　ｅｘｃｌｕ
ｓｉｖｅ）”であることを示している。ＣＣＤ２２，２
４、ＳＣＥ５４、および主メモリもそれぞれのＣＣＤ７
４，８０、ＳＣＥ９０、およびメモリ９６とは、これら
の装置の各々に部分的なキャストアウトおよびセクタの
無効果を与える付加的論理が設けられた点で異なってい
る。さらに、ＳＣＥ９０の内部キャッシュ・ディレクト
リ・テーブルは、多重キャッシュが同じラインの一部の
排他的使用を持つ可能性を与えるように拡張される。

【００５３】図３は変更ライン・スタック（ＭＬＳ）３
４の構成要素をさらに詳細に示した図である。このＭＬ
Ｓは入力アドレス・格納論理回路９８、アクセス論理１
１０、ＭＬＳ制御・ディレクトリ（ＭＳＬＤＣ）１０６
、および変更ダブルワード・アレイ（ＣＤＷＡ）１０８
を備えている。ＭＬＳＤＣ１０６装置ＣＤＷＡ１０８は
、それぞれ、キャッシュ制御・ディレクトリおよびキャ
ッシュ・アレイと同様に動作する。ＭＬＳＤＣに格納さ
れ、エントリにアクセスするために用いられるアドレス
はＣＣＤ２２に格納されたアドレスと同じである。ＣＤ
ＷＡ１０８（ＭＬＳ３４内の）内の各々のエントリに対
して維持された対応する“データ”は、ＭＬＳ３４内の
要素のエントリの後キャッシュ・アドレス１８内の対応
するライン内のどのＤＷが変更されたかを識別する変更
ビット・ベクトル（ＣＤＷ）１０８ａ〜ｎである。ＣＤ
ＷＡ１０８は単に、共有排他的に保持されない（すなわ
ち、ＣＣＥ２２のライン・エントリのビットＳが０であ
る。）ラインに対するエントリを有する。ＤＤＷＡ１０
８における変更ダブルワード・ビット・ベクトルＣＤＷ
１０８ａ〜ｎは、キャッシュ制御・ディレクトリ２２の
格納動作に応じて変形され、ＳＣＥ５４からのＸＩリク
エストの処理中に取り出される。

【００５４】入力アドレス・格納論理回路９８は次の２
つの機能を行う。１）共有排他的に保持されないライン
に対してＣＣＤ２２により格納が与えられないとき論理
回路９８はアクセス論理回路１１０に格納アドレスを与
え、さらに２）この入力アドレス格納論理回路９８は、
変更ダブルワード・アレイ１０８に変更されているＤＷ
のライン内に記憶場所を与える。この記憶場所は、変更
ワード・ビット・ベクトルＣＤＷ１０８ａ〜ｎの更新の
ために用いられる。

【００５５】ローカル・プロセッサ２により行われる格
納動作に対して、アクセス論理回路１１０は、入力アド
レス格納論理回路９８から変更されているラインのアド
レスを受けると共にＭＬＳＤＣ１０６にアドレスを与え
る。リモート・プロセッサ４からのＸＩに対して、無効
にされているラインのアドレスがＳＣＥ５４からアクセ
ス論理回路１１０に与えられ、さらにこのアクセス論理
１１０はこのアドレスをＭＬＳＤＣ１０６に与える。

【００５６】図４はセクタ化ライン・ディレクトリ３０
をさらに詳細に示した図である。このＳＬＤ３０は、入
力アドレス・リクエスト論理回路１１４、データ入力・
セレクト論理回路１１６・セクタ化ライン・ディレクト
リ・制御（ＳＬＤＣ）論理回路１２４、および有効排他
的変更ビット・アレイ（ＶＥＣＢＡ）１２６を備えるも
のである。ＳＬＤＣ１２４およびＶＥＣＢＡ１２６は、
それぞれ、キャッシュ制御・ディレクトリおよびキャッ
シュ・アレイと同様に動作する。ＳＬＤＣ１２４に格納
され、エントリにアクセスするために使用されるアドレ
スはＣＣＤ２２に格納されたものと同じアドレスである
。ＶＥＣＢＡ１２６（ＳＬＤ３０内の）中の各々のエン
トリに対して維持された対応する「データ」は、ライン
内の各々のセクタに対する有効ビット（ＶＤＷ）１２６
ａ、排他的ビット（ＥＸＤＷ）１２６ｂ、および変更ビ
ット（ＣＨＤＷ）１２６ｃを識別するベクトル１２６ａ
〜ｃである。ＶＥＣＢＡ１２６は単に共有排他的に保持
されるラインに対するエントリを有する（すなわち、Ｃ
ＣＤ２２内のライン・エントリのビットＳは１にセット
される。）。ＶＥＣＢＡ１２６内のＶＤＷ，ＥＸＤＷ，
およびＣＨＤＷデータは、プロセッサ２からのキャッシ
ュ・リクエストおよびキャッシュ制御・ディレクトリ２
２からのキャッシュ・リクエストに応じて取り出され、
変更される。

【００５７】入力アドレス・リクエスト論理回路１１４
は次の２つの機能を果たす。すなわち、１）共有排他的
に保持されるラインに対してＣＣＤ２２により格納が与
えられたとき、ラインのアドレスは入力アドレス・リク
エスト論理回路に与えられ、この論理回路は当該アドレ
スをデータ入力・セレクト論理回路１１６およびＳＬＤ
Ｃ１２４に与え、さらに、２）リモート・プロセッサ４
からのＸＩに対して、ＣＣＤ２２はラインのアドレスを
入力アドレス・リクエスト論理回路１１６に与え、この
論理回路は上記アドレスをＶＥＣＢＡ１２６に与えて影
響を受けたラインの状態を更新する。

【００５８】ローカル・プロセッサ２により要求された
格納動作に対して、入力アドレス・リクエスト論理回路
１１４は変更されているラインのアドレスをデータ入力
・セレクト論理回路１１６に与え、この論理は上記アド
レスをＶＥＣＢＡ１２６に与える。リモート・プロセッ
サ４からのＸＩに対して、無効にされているラインのア
ドレスがキャッシュ制御・ディレクトリ２２からデータ
入力・セレクト論理回路１１６に与えられ、さらにデー
タ入力・セレクト論理回路はＸＩコマンドによりもたら
されるＶＥＣＢＡ１２６に対してＶＤＷ，ＥＸＤＷ，お
よびＣＨＤＷテーブルの変化を制御する。

【００５９】変更ライン・スタック３４およびセクタ化
ライン・ディレクトリ３０のエントリ数は性能要件およ
び可能な技術により決定される。両者の数はキャッシュ
１８中のライン数よりはるかに小さくなることが意図さ
れる。例えば、５１２ラインを有するキャッシュは変更
ライン・スタック内およびセクタ化ライン・ディレクト
リ内に４および８の間のエントリを有してもよい。ＭＬ
Ｓ３４およびＳＬＤ３０により多くのエントリを付加す
ることによりシステムの性能が改良されるときは、参照
の空間的局所性の仮定は無視され、さらにより小さなサ
イズのキャッシュがより適切に用いられることになる。

【００６０】図７は、本発明の実施例を含む装置により
実施されたときの格納動作（図５のステップ２３８）の
変更方法を示す図である。図１に示したように、任意の
ラインが先ずキャッシュ１８にもたらされると、そのＣ
ビットおよびＳビットは０になる。このラインはＭＬＳ
３４またはＳＬＤ３９に入力されることはない。ライン
に対する格納動作がステップ２６０において０でＳビッ
トのラインに対して与えられると、格納動作のアドレス
はバス３８′を通して（図３に示されるように）入力ア
ドレスおよび格納論理回路９８に与えられる。ステップ
２６２において、入力アドレス・格納動作はラインのア
ドレスをバス１０４を介してアクセス論理回路１１０に
与える。次に、アクセス論理回路１１０は、ＳＣＥ５４
により要求されるアドレスが何ら進行していないときは
、バス１１２を通して変更ライン・スタック・ディレク
トリ・制御回路１０６に供給する。ステップ２６６にお
いて、変更されているライン内のターゲットＤＷがバス
１０２を介して入力アドレス・格納論理９８によりＣＤ
ＷＡ１０８に供給される。

【００６１】このようにしてＭＬＳ３４は、ＭＬＳにお
いて対応するリセットを有するキャッシュ・アレイ１８
の各々のラインでダブルワードが最近変更されているＭ
ＬＳ３４のレコードを保持する。

【００６２】図８および図９は、変更ラインがセクタ化
ライン・ディレクトリ３０でセクタ化され識別されるプ
ロセスを示す図である。ラインがＭＬＳ３４に入力され
ると、エントリはローカル・プロセッサ２によるライン
への各々の格納動作により更新される。これらは、ライ
ン中のＤＷが変更されているトラックを更新する。ステ
ップ３００において、リモート・プロセッサ４から相互
無効（ＸＩ）が受信されると、ＳＣＥ５０はバス５０を
介して相互無効化ラインのアドレスをアクセス論理回路
１１０に与える。アクセス論理回路１１０はこのアドレ
スをＭＬＳＤＣ１０６に与える。要求されたラインに対
してＭＬＳ３４に有効エントリが存在するときは、この
有効エントリは最近変更されたものである。ラインが最
近変更されているときは、アドレス・変更ビット・ベク
トル（ＣＤＷ）１０８ａ〜ｎはＣＤＷＡ１０８によりＣ
ＣＤ２２に与えられる。ステップ３００の最終サブステ
ップとして、ラインは主メモリにキャストアウトされる
。

【００６３】この時点で、ＭＬＳエントリが最早必要と
されなくなったときＭＬＳのエントリは無効とマークさ
れ、さらにＣＤＷ１０８ａ〜ｎは０にリセットされる。このようにして、ＭＬＳ３４は、ＭＬＳの内容がこれら
を他の構成要素にコピーすることなしに廃棄されるスト
アスルー・キャッシュとして処理される。

【００６４】ＭＬＳ３４においてエントリを有するライ
ンは、リモート・プロセッサ４により関連するラインが
アクセスされる前にキャストアウトされなければならな
い。このキャストアウトにより、リモート・プロセッサ
はライン中のデータの最新のコピーを有することが保証
される。ステップ３０４において、ＭＬＳ３４により予
め与えられるＣＤＷ値１０８ａ〜ｎにより示されるよう
に、ＣＣＤ２２は、要求されたＤＷが最近変更されてい
るかを知るためにＸＩ要求アクセスをチェックする。要
求されたＤＷが最近変更されているときは、ステップ３
０４において、ＭＬＳエントリからの情報は単に廃棄さ
れる。これは、次のアクセスが生じたとき全体のライン
を通してリモート・プロセッサ４１に排他的制御を与え
る。この機構は、ラインのセクタ化が不要になることか
ら従来技術とほぼ同じであるが、これはクローズ・ライ
ト共有の場合とは異なるものである。同一のＤＷアクセ
スが異なるプロセッサにより格納動作に使用されるごと
に、コヒーレンシィを保持するキャストアウトが必要と
されることから、このラインをセクタ化するいかなる理
由も存在しない。

【００６５】しかしながら、ラインが最近変更されてい
るが、ＸＩコマンドにより示される要求されたＤＷが変
更されていないときは、ＣＣＤ２２は、ＸＩコマンドが
発行されたラインのアドレスおよびダブルワードが最近
変更されている情報をバス２６を介してＳＬＤ３０に与
える。このアドレスはさらに、ステップ３０６において
、バス４６を介してＳＣＥ５０に与えられる。このＸＩ
動作は“ＭＬＳＩにおいてヒット”を有するといわれる
。これはクローズ・ライト共有の場合である。

【００６６】ＭＬＳ内でＸＩがヒットすると、セクタ化
されているラインのアドレスは、図４に示したようにス
テップ３０６においてＣＣＤ２２によりバス２６′を介
して入力アドレス・リクエスト論理回路１１４に与えら
れる。ステップ３０８において、ラインがセクタ化ライ
ン・ディレクトリ３０から置き換えられるときは、ステ
ップ３１０において、変更ＤＷのアドレスおよびベクト
ルがバス２６′′′および２６′′′′を介してＣＣＤ
２２に送出される。ステップ３１２においてＳＬＤ３０
において置き換えられているライン中のＤＷのいずれか
が変更されていると、ステップ３１４でＣＣＤ２２は主
メモリ６０に変更されたＤＷを書き込む部分キャストア
ウトを行い、さらにＣＣＤ２２においてラインに対する
Ｖビットを０にリセットする。ＳＬＤ３０の情報はキャ
ッシュ・アレイ１８に格納された“データ”ではないが
、ＳＬＤはストアイン・キャッシュのように動作する。ＳＬＤからエントリを削除する前に、ライン内の全ての
変更ＤＷをキャストアウトしてコヒーレンシィを保証す
ることが必要である。

【００６７】ステップ３１６において、ＳＬＤ３０内に
スペースが得られ、新しいエントリを格納する。新たに
セクタ化されたラインのＤＷが最近変更されているとい
う情報およびＸＩ動作により要求されたダブルワードの
アドレスがＣＣＤ２２によりバス２６″を介してデータ
入力・セレクト論理回路１１６に与えられる。データ入
力・セレクト論理回路１１６はライン１２２を介してＶ
ＥＣＢＡ１２６にＶＤＷ，ＥＸＤＷ，およびＣＤＷ情報
を与え、さらに入力アドレス・リクエスト論理回路１１
４はライン１２０を介して共有インディレクトリ・制御
（ＳＬＤＣ）回路１２４にアドレスおよび格納リクエス
トを与える。

【００６８】上記のように、ＭＬＳ３４およびＳＬＤ３
０は、これらがデータに対抗するものとしてポインタお
よび制御情報を含むが、キャッシュ・メモリと同様に動
作する。ＭＳＬ３４またはＳＬＤ３０のいずれかが一杯
であり、エントリが付加される予定のときは、最低使用
頻度（ＬＲＵ）アルゴリズムが用いられ、置き換えるべ
きエントリを選択する。このようなＬＲＵ方式は従来技
術で示したものである。

【００６９】本発明の好適な実施例において、ミスおよ
びキャストアウトの発生数は、セクタＥＸＤＷビットを
、これが格納動作に必要なときにのみ１にセットするこ
とにより最小になされる。このようにして、ステップ３
１８でラインがセクタ化される前にローカル・キャッシ
ュによりＤＷが最近変更されたときは、ステップ３２２
でこのＤＷに対するＥＸＤＷビットがローカルＶＥＣＢ
Ａ１２６において１２にセットされ、さらにＶＤＷビッ
トがリモートＶＥＣＢＡで０にセットされる。

【００７０】ラインがセクタ化されようとし、またステ
ップ３１８でこのラインがセクタ化される前にこのライ
ンのＤＷがローカル・キャッシュにより最近変更されて
いない場合は、ステップ３２０でそのＤＷに対するＥＸ
ＤＷビットがローカルＶＥＣＢＡ１２６で０にリセット
され、またＶＤＷビットがリモートＶＥＣＢＡで１にセ
ットされる。

【００７１】ステップ３２４でリモート・プロセッサ４
により発生されたＸＩ動作がＤＷに対して格納アクセス
を要求するときは、ステップ３２８で、そのＤＷに対す
るＥＸＤＷビットがリモート・プロセッサ４に対するＶ
ＥＣＢＡで１にセットされ、さらにＶＤＷビットが０に
リセットされてローカルＶＥＣＢＡ１２６のＤＷを無効
にする。ステップ３２４において、ＤＷを取り出すため
にＸＩが開始されていることが決定されたときは、ステ
ップ３６２でそのＤＷに対するＥＸＤＷビットがリモー
ト・プロセッサ４に対するＶＥＣＢＡで０にセットされ
、さらにＶＤＷビットがローカルＶＥＣＢＡ１２６のＤ
Ｗに対して１にセットされたままになる。ステップ３２
６または３２８のいずれかのステップの後、ＣＣＤ２２
内のＳビット２２ｅが１にセットされて、このラインが
ここで共有排他的に保持されたことを示す。

【００７２】当業者には明らかなように、この規則の組
は単にセクタ化キャッシュにおけるコヒーレンシィを実
施するキャッシュ管理アルゴリズムを単に例示したに過
ぎないものである。このキャッシュ管理アルゴリズムの
他の変形アルゴリズムを用いてもよいことは勿論である
。例えば、よりアグレッシブにセクタに対する排他的ス
テータスを得ることによりセクタ化ＦＮＤをもたらすセ
クタ化ＸＩの頻度を減らすことも可能である。セクタ化
ＸＩを発行するプロセッサは、上記のように、データが
同時に与えられるセクタに対して単に排他的制御を与え
る代わりに、リモート・プロセッサにより排他的に保持
されない全てのセクタにわたって排他的制御が許容され
る。

【００７３】図１０および図１１は、フェッチ，格納，
およびＸＩ動作に対して共有排他的ラインがアクセスさ
れる方法を示す図である。ステップ３５０ではプロセッ
サ２によりフェッチ・リクエストがバス１４を介してＣ
ＣＤ２２およびＳＬＤ３０の両者に与えられる。ＳＬＤ
３０は、ＣＣＤ２２を調整して要求されたＤＷに対して
ＶＤＷ１２６ａとＥＸＤＷ１２６ｂにビットを検討する
ことによりリクエストに応答する。ＶＤＷビットがステ
ップ３５４で１にセットされると、それはヒットであり
（ＶＤＷが１に等しいときは、Ｖ２２ｂも１でなければ
ならない。）、またＣＣＤ２２はステップ３５６でライ
ン６を介してデータをプロセッサ２に送出するようにキ
ャッシュ・アレイ１８に指示する。

【００７４】ただし、Ｖビット２２ｂは１であるが、Ｓ
ビット２２ｅが１に等しくかつビットＶＤＷが０のとき
は、ＤＷは他のプロセッサ４により排他的に保持され、
アクセスは許容されない。これは、プロセッサ２および
プロセッサ４が共に同一ワードをアクセスし、これらの
プロセッサの一方がデータを変更している場合に生じる
。この場合は、コヒーレンシィを維持するためキャスト
アウトが要求される。

【００７５】キャストアウト動作の第１ステップにおい
て、ラインのアドレスおよび変更ダブルワード・ビット
がステップ３５８でＳＬＤ３０によりＣＣＤ２２に与え
られる。次に、ＣＣＤ２２はバス４６および４２を介し
てアドレスおよび変更ＤＷ情報をそれぞれＳＣＥ５４に
与える。ＳＣＥ５４はキャストアウトされるべきＤＷの
アドレスをバス５８を介して主メモリ６０に与え、バス
５６を介して変更ＤＷを与える。ステップ３６０で、ラ
インはＳＬＤで無効にされ（すなわち、ラインに対応す
るＶＤＷビットがリセットされる。）、これによりＣＣ
Ｄ２２はビットＶおよびＳを０にリセットする。

【００７６】ステップ３６２において、ＣＣＤ２２はプ
ロセッサ２により要求されたデータを含むラインに対す
るミスを報告する。これによりＳＣＥ５４はＸＩコマン
ドを他の全てのプロセッサ４に送出する。これらのコマ
ンドにより、ラインを必然的にセクタ化されて保持する
プロセッサは、プロセッサ２がデータを再び取り出す前
に変更ＤＷを主メモリ６０に書き込む。ステップ３６４
において、主メモリ６０によりデータがＳＣＥ５４に与
えられ、このＳＥ５４はこのデータをキャッシュ・アレ
イ１８に与え、キャッシュ・アレイ１８は次にこのデー
タをプロセッサ２に与える。

【００７７】ステップ３５２における動作が格納動作の
とき、ＶＤＷビット１２６ａおよびＥＸＤＷビット１２
６ｂが共に１の値を有さない場合は、プロセッサ２はデ
ータに対するアクセスを否定される。ＶＤＷおよびＥＸ
ＤＷが共に１にセットされたときは、それはヒットであ
り、データはステップ３８８でプロセッサ２によりキャ
ッシュに与えられる。

【００７８】ステップ３７８でＶＤＷは１であるがＥＸ
ＤＷは０のときは、ステップ３８０でフェッチ・ノー・
データ・リクエストが開始される。このリクエストによ
り、セクタ化ＸＩコマンドがＣＣＤ２２によりバス４６
を通してＳＣＥ５４に送出される。他のいかなるキャッ
シュ２０もステップ３８２でセクタ化されたラインを保
持しないときは、ステップ３８４でＣＣＤ２２に対して
排他的制御が直ちに与えられる。しかし、その他のキャ
ッシュ２０のいずれかがセクタ化されたアクセスを保持
するときは、ステップ３８６でＳＣＥ５４は、バス４８
を介してセクタ化ラインを保持する全てのリモート・キ
ャッシュ制御・ディレクトリ７４にセクタ無効化リクエ
ストを送出する。次に、リモートＣＣＤ２４はリモート
ＳＬＤ３２に無効化リクエストを送出し、これはリモー
トＶＥＣＢＡにおいて適当なＶＤＷビット０をセットす
る。ＸＩコマンドが送出された後、ＣＣＤ２２はＳＬＤ
３０においてＤＷを排他的とマークし、格納動作は進行
する。

【００７９】ステップ３５２における動作が格納動作で
あり、さらに要求されたＤＷがＳＬＤ３２で無効とマー
クされたときは、ＤＷは他のプロセスにより排他的に保
持され、ラインはもはやＳＬＤに残留することはない。ステップ３９０において、ライン中の変更ＤＷの全てが
キャストアウトされ、ＸＩが他の全てのプロセッサに送
出される。これらの動作は、ステップ３５８，３６０，
３６２，および３６４でリモート・プロセッサにより排
他的に保持されたワードに対するフェッチに対して取ら
れたものに類似している。ＸＩコマンドが送出された後
、ＳＣＥはライン中のデータに対するフェッチ・リクエ
ストを送出する。このデータはキャッシュ１８に格納さ
れ、ラインに対するＶおよびＥビットはＣＣＤ２２にヒ
ットされ、さらにプロセッサ２はアドレス指定されたＤ
Ｗにデータを格納することが許容される。

【００８０】ステップ３５２において、ラインがセクタ
化され、要求された動作がリモート・プロセッサからの
ＸＩコマンドであるときは、ステップ３６６でＣＣＤ２
２はバス２６′を介して要求されたラインのアドレスを
ＳＬＤ入力アドレス・リクエスト論理回路１１４に与え
る。このＣＣＤ２２はさらに、ステップ３６６で、リク
エストがＸＩであることも表示する。ＸＩが送出された
ＤＷのアドレスはバス２６″を介してＳＬＤ入力・セレ
クト論理回路１１６に送出される。次に、ライン中のＤ
Ｗに対するＣＨＤＷビット１２６ｃがバス２６′′′を
介してＣＣＤ２２に送出される。ステップ３６８で、Ｃ
ＣＤ２２が、リクエストは変更されているＤＷに対して
であると判定したときは、ＣＣＤ２２はラインに対する
無効リクエストをＳＬＤ３０に送出し、部分キャストア
ウトを行う（すなわち、変更ＤＷをメモリ６０に書き込
む。）。さらに、ＣＣＤ２２は、ステップ３７０でＣＣ
Ｄ２２中のラインに対するＶビットを０にリセットする
。要求されたラインはここではリモート・プロセッサ４
の排他的制御下に置かれ、主メモリ６０から取り出され
る。

【００８１】要求されたＤＷがステップ３６８で変更さ
れいないときは、ラインに対するＶＤＷビットはステッ
プ３７４で０にリセットされる。ラインが有効であるこ
とを示すＶビット、およびラインが共有排他的に保持さ
れたことを示すＳビットはＣＣＤ２２によりセットされ
る。これらのステップが行われると、要求されたＤＷは
リモート・プロセッサ４を要求する排他的制御の下で配
置される。

【００８２】本発明はＷＴＷＡＸを用いたストアスルー
・キャッシュ管理システムに対する第２実施例に容易に
拡張可能である。図１は、ＣＣＤ２２，ＳＬＤ３０，Ｍ
ＬＳ３４，ＳＣＥ５４，および主メモリ６０内のハード
ウェア論理は異なるが、なお本実施例を正確に示すもの
である。ＷＴＷＡＸシステムにおいては、フルライン（
セクタ化されない）およびセクタ（変更され、セクタ化
されたラインから）の両者が、格納動作が指令された時
点で主メモリ６０に格納されることを除いて、殆ど同等
である。これは、単にＸＩおよびＣＥＲＯにのみ応じて
データがメモリ６０に格納される上記実施例と対照をな
すものである。このＷＴＷＡＸシステムにはキャストア
ウトは何ら存在しない。ＸＩまたはＣＥＲＯは、ライン
またはセクタの排他的状態に対して変化をもたらすが、
何らかのデータを主メモリに書き込ませるものではない
。

【００８３】本発明の第２実施例は第１実施例と殆ど同
様に動作する。第１実施例の場合と同様に、ＭＬＳ３４
内のラインを書き込むためにリモート・プロセッサがＸ
Ｉコマンドを発行するとき、ローカル・プロセッサが要
求されたＤＷまたはライン中の他のＤＷを変更している
か否かを（また再び変更しようとする）判定するチェッ
クがなされる。同じＤＷがローカル・プロセッサ２によ
り変更されているときは、ラインはローカル・キャッシ
ュ１８で無効にされ、これはセクタ化されない。ローカ
ル・プロセッサ２が同じＤＷを変更していないときは、
ラインはＳＬＤＤ３０に付加され、ＭＬＳ３４から廃棄
される。本発明のＷＴＷＡＸ実施例に対するＸＩコマン
ドとストアイン・キャッシュ実施例との主要は差異は、
前者の場合は、無効にされたラインが主メモリに書き戻
されるのを待つ間の遅延が存在しないことにある。

【００８４】ストアイン・キャッシュの代わりにＷＴＷ
ＡＸキャッシュを用いる利点および欠点は、従来のキャ
ッシュに関するダイナミックにセクタ化されたキャッシ
ュに対するものと同じである。このストアイン・キャッ
シュはＸＩの間に遅延されるが、変更ＤＷは主メモリに
対してキャストアウトされる。ストアスルー・キャッシ
ュは遅延をそれ程発生しないが、このストアスルー・キ
ャッシュは、各々の格納動作が主メモリ６０に対する書
込みをもたらすことから、付加的トラヒックを受容する
ためにキャッシュと主メモリ６０の間ではるかに大きな
帯域幅を必要とする。

【００８５】発明の背景および図２に関連して説明した
従来のシステムにおいては、プロセッサが同じラインを
交互にアクセスするときは、異なるプロセッサがライン
をアクセスするごとにキャストアウトおよびフェッチ動
作が発生する。このアクセス特権の“ピン・ポン動作”
は性能を低下させるが、それはコヒーレンシィを維持す
る働きをする。本発明の第３実施例は、プロセッサが同
じＤＷまたは異なるＤＷを維持するかに拘らず、コヒー
レンシィを維持し、“ピン・ポン動作”を排除する機構
を与えるものである。

【００８６】米国特許第４，４４５，１７４号明細書に
は、多重プロセッサの間で共有される付加的なキャッシ
ュ・メモリを用いた機構が示されている。各々のプロセ
ッサは私用ストアイン・バッファ・キャッシュを有し、
他のプロセッサと共通キャッシュおよび主メモリを共有
している。２つのプロセッサにより共有され変更される
ラインは共通の共有キャッシュに格納され、各々のプロ
セッサはフェッチおよび格納動作の両者に対して直接に
共有キャッシュ内の任意のラインにアクセスできる。こ
の特許の方法は、両プロセッサが同じＤＷをアクセスし
ているときはダイナミックにセクタ化された私用キャッ
シュより良好な性能を与え、さらにダイナミックにセク
タ化されたキャッシュは異なるＤＷがアクセスされたと
きより良好な性能を与える。

【００８７】図１２は、共有キャッシュの環境における
本発明の特徴を実施する本発明の第３実施例を示す図で
ある。この実施例においては、図１に示した回路に対し
て共有キャッシュ制御・ディレクトリ（ＳＣＣＤ）１３
２および共有キャッシュ・アレイ（ＳＣＡ）１３０が付
加してある。さらに、私用ＣＣＤ１３８，１４０，ＳＣ
Ｅ１３４，および主メモリ１３６は、これらが共有キャ
ッシュ１３０とデータを交換することを許容する付加的
論理回路を有する。

【００８８】ＳＣＡ１３０は、これがデータを格納し、
状態情報は格納しないという点で、従来のキャッシュ・
メモリと同様に動作する。本発明のこの実施例で使用す
るＳＣＡ１３０は単に４から８ラインに供するスペース
を有しているだけであり、したがって私用キャッシュ・
メモリ１８，２０よりはるかに小さい。ストアイン・キ
ャッシュであるキャッシュ・アレイ１８とは異なりＳＣ
Ａ３０はストアスルー・キャッシュである。このＳＣＡ
１３０の目的は、多重プロセッサが、ピン・ポン作用な
しに、またラインを各々のアクセスとキャストアウトす
る必要性なしに、同じＤＷにアクセスすることを許容す
ることにある。この目的に対して、ストアスルー方式は
より効率的である。排他的管理は望まれず、したがって
各々のプロセッサはＳＣＡデータに容易にアクセスする
ことができる。各々のプロセッサＳＣＡ１３０に直接ア
クセスするので、同一のデータ・ラインの多重読出し専
用コピーの必要性がなくなり、全てのプロセッサによる
ＳＣＡのコヒーレント・ビュー（ｃｏｈｅｒｅｎｔ　　
ｖｉｅｗ）を維持するタスクが簡単になる。ＳＣＡ１３
０とキャッシュ・アレイ１８とのその他の差異は、ＳＣ
Ａ１３０の同一ラインをアクセスする同時リクエストが
生じたとき、プロセッサ２または４またはＳＣＥ１３４
のいずれが優先度を受けるかを判定するＣＰＵ優先度論
理回路網１３８にある。

【００８９】先ず、ラインがプロセッサ２により参照さ
れると、それは私用キャッシュ１８に配置される。ロー
カル私用キャッシュ１８に対する格納およびそれからの
取り出しは本発明の第１実施例の場合と同様に処理され
る。キャッシュ１８中のラインが変更されると、ＭＬＳ
３４にエントリが生成され、変更されている特定のＤＷ
を識別する。

【００９０】ＭＬＳ３４でラインに対するエントリが生
成されると、これはローカル・プロセッサ２により各々
の格納内容と共に更新され、どのＤＷが変更されている
かを追跡する。リモート・プロセッサ４から相互無効（
ＸＩ）信号が受信されると、ＳＣＥ５０はＭＬＳ３４に
無効化ラインのアドレスを提供する。ラインが最近変更
されていると、第１実施例の場合と同様に、アドレスお
よび変更ビット・ベクトル（ＣＤＷ）１０８ａ〜ｎがＭ
ＬＳによりＣＣＤ２２に与えられる。

【００９１】この時点で、ＭＬＳのエントリは、それが
最早必要とされなくなると（ＣＣＤ２２はＣＤＷ情報を
有し、必要に応じてそれをＳＬＤまたはＳＣＣＤに与え
ることができる。）、無効とマークされ、ＣＤＷ１８ａ
〜ｎは０にリセットされる。

【００９２】ＣＣＤ２２は、ＭＬＳ３４によりすでに与
えられたＣＤＷ値１０８ａ〜ｎにより示されるように、
要求されたＤＷが最近変更されているか否かを知る。要
求されたＤＷが最近変更されてないときは、ラインは本
発明の第１実施例の場合と同様にアクセス化される。

【００９３】しかし、要求されたＤＷが最近変更されて
いるとき、ＣＣＤ２２はＳＣＥ５４に対してＸＩが送出
されたラインのアドレスを通過させる。次に、ＳＣＥ５
４はデータのラインの転送を共有キャッシュ制御・ディ
レクトリ（ＳＣＣＤ）１３２にまた共有キャッシュ・ア
レイ（ＳＣＡ）１３０に向けて指示する。

【００９４】ラインがＳＣＡ１３９およびＳＣＣＤ１３
２から置き換えられる予定のときは、ＬＲＵ方式が用い
られてどのラインをＳＣＡから削除するべきかを判定す
る。有効ビットはＳＣＣＤ１３２で選択されたラインに
対して０にリセットされる。次に、新しいラインを格納
するスペースがＳＣＡ１３０で得られる。このアドレス
はＳＣＣＤ１３２に入力され、またデータのラインはＳ
ＣＡ１３０に入力される。次に、このラインはＣＣＤ２
２で無効にされている。ＳＣＡ１３０に格納されたライ
ンは、私用キャッシュ１８または２０のいずれにおいて
も保持されない。

【００９５】ローカル・プロセッサ２が、ラインから取
り出し、あるいはラインに格納することを望むときは、
それは、第１実施例の場合と同様に、ＣＣＤ２２からそ
のラインを要求する。この第３実施例における殆どの動
作は、第１実施例の場合と同様に進行する。ラインが私
用キャッシュ１８に格納されたときは、格納およびフェ
ッチ動作は同様に処理される。ラインがセクタ化される
と、これらの動作も第１実施例の場合と同様に処理され
る。しかしながら、私用キャッシュ１８にキャッシュミ
スがある場合は、動作が格納であってもフェッチであっ
ても、この第３実施例は第１実施例で与えられたもの以
上の追加的な能力を与える。

【００９６】ＸＩリクエストがリモート・プロセッサに
送出される前にミスが検出されたときは、ローカル・プ
ロセッサ２はＳＣＣＤ１３２に直接質問することができ
る。要求されたアドレスがＳＣＣＤ１３２に常駐し有効
であるときは、要求されたデータ・ラインはプロセッサ
２に与えられ、フェッチおよび格納動作に供される。ラ
インは任意のプロセッサによる格納動作に対して得られ
るので、また格納動作を要求するプロセッサは、ＸＩコ
マンドを他の私用キャッシュに送出する前にＳＣＣＤ１
３２に質問するので、共有キャッシュによるＸＩコマン
ドの処理はなされない。

【００９７】本発明の第１実施例においては、ラインが
セクタ化されたときは、ライン内の各々のＤＷは単に１
つのプロセッサにより変更されてもよく、または共有排
他的に保持されてもよい。ラインＤＷ中の所定のＤＷが
ローカル・プロセッサにより変更されており、また第２
プロセッサがそのＤＷに対して排他的制御を得ようとす
るときは、全ラインはＳＬＤ３０でキャストアウトされ
無効にされる。共有キャッシュが使用可能なときは、セ
クタ化ラインは、ラインが共有キャッシュ１８から共有
キャッシュに移動された場合と同様にＳＣＡ１３０に転
送される。

【００９８】ラインがＳＣＡ１３０に入力されると、こ
のラインは、それが最も少なく最近参照された共有ライ
ンとして置き換えられるまでそこに格納されている。私
用キャッシュ１８，２０から共有キャッシュへのライン
の転送は一方向転送である。この制限はキャッシュ１８
，２０中のセクタ化および非セクタ化ラインの両者に適
用される。

【００９９】性能の増大は、ディスジョイントな組のＤ
Ｗへの多重プロセッサの記憶装置に対するセクタ化され
た私用キャッシュ・ラインの使用および同一のＤＷへの
多重プロセッサの記憶装置に対する共有キャッシュ・ラ
インの使用により実現される。この性能の増大はいずれ
かの構成要素システムのみでは実現されない。

【０１００】当業者には明らかなように、以上に示した
実施例について多くの変形例が可能である。例えば、プ
ロセッサの個数を変えてもよく、変更ライン・スタック
のサイズ、セクタ化ライン・ディレクトリ・サイズ、共
有キャッシュ・アレイ・サイズ、キャッシュ置き換えア
ルゴリズム、さらにキャッシュ管理アルゴリズムを変え
てもよい。このような変形例のいずれも当業者には容易
に理解されるものであろう。

【０１０１】

【発明の効果】複数のプロセッサによって、同一ライン
の異なるワードに対して同時に格納および取り出し動作
を行うことが可能になる。

【図面の簡単な説明】

【図１】変更ライン・スタックおよびセクタ化ライン・
ディレクトリを有してダイナミック・キャッシュ・セク
タ化を許容するストアイン・キャッシュ・システムのブ
ロック図である。

【図２】従来のストアイン・キャッシュ・システムの概
略機能図である。

【図３】図１に示した変更ライン・スタックのブロック
図である。

【図４】図１に示したセクタ化ライン・ディレクトリの
ブロック図である。

【図５】図２に示したキャッシュ・システムにおいてフ
ェッチ，格納，ＣＥＲＯ，およびＸＩ動作が通常実施さ
れるプロセスを示すフロー図である。

【図６】図２に示したキャッシュ・システムにおいてフ
ェッチ，格納，ＣＥＲＯ，およびＸＩ動作が通常実施さ
れるプロセスを示すフロー図である。

【図７】図１に示したキャッシュ・システムにおけるラ
インをキャッシュに付加する動作の変更方法を示すフロ
ー図である。

【図８】キャッシュ・ラインをセクタ化して図１に示し
たキャッシュ・システムにおける共有排他制御を許容す
る方法を示すフロー図である。

【図９】キャッシュ・ラインをセクタ化して図１に示し
たキャッシュ・システムにおける共有排他制御を許容す
る方法を示すフロー図である。

【図１０】図１に示したキャッシュ・システムにおける
セクタ化ラインに対してフェッチ，格納，および相互無
効化動作を行う方法を示す流れ図である。

【図１１】図１に示したキャッシュ・システムにおける
セクタ化ラインに対してフェッチ，格納，および相互無
効化動作を行う方法を示す流れ図である。

【図１２】私用キャッシュおよび共有キャッシュを共に
含む本発明の他の実施例のブロック図である。

【符号の説明】

２，４　　ローカル・プロセッサ１８，２０　　私用キャッシュ・メモリ２２，２４，７
４，８０　　キャッシュ制御・ディレクトリ（ＣＣＤ）３０，３２　　セクタ化ライン・ディレクトリ（ＳＬＤ
）３４，３６　　変更ライン・スタック（ＭＬＳ）１８
ａ，４２，４４，５６，５８，８２　　バス９０　　シ
ステム制御要素（ＳＣＥ）９６　　共有主メモリ９８　　入力アドレス・格納論理回路１０６　　ＭＬＳ制御・ディレクトリ１０８　　変更ダブルワード・アレイ（ＣＤＷＡ）１１
０　　アクセス論理回路１１４　　入力アドレス・リクエスト論理回路１２４　
　セクタ化ラインディレクトリ・制御（ＳＬＤＣ）論理
回路１２６　　有効排他的変更ビット・アレイ（ＶＥＣＢＡ
）１３０　　共有キャッシュ・アレイ（ＳＣＡ）１３２
　　共有キャッシュ制御・ディレクトリ（ＳＣＣＤ）

Claims

【特許請求の範囲】

【請求項１】共有主メモリと、各々がそれぞれのキャッ
シュ・メモリに結合された少なくとも２つのプロセッサ
と、キャッシュ・メモリを共有主メモリに結合するシス
テム制御回路とを備えるコンピュータ・システムにおけ
るキャッシュ・メモリ中のデータへのアクセスを管理す
る装置であって、前記キャッシュメモリの１つにおいて
、プロセッサの少なくとも２つにより参照されているデ
ータ・ラインを、このデータ・ラインの各々のデータ・
ワードがプロセッサの多くとも１つにより参照されるよ
うに識別する手段と、識別されたラインにおけるデータ
・ワードをアクセスしているプロセッサに書込みアクセ
スを与える手段と、１つ以上のプロセッサが前記ライン
の１ワードに対して同時的な書込みアクセスを得ること
を防止する手段とを備えたデータ・アクセス管理装置。
【請求項２】共有主メモリと、システム制御要素と、各
々がメモリ・ワードのラインを保持するそれぞれの専用
キャッシュ・メモリを有する少なくとも２つのプロセッ
サとを備えるコンピュータ・システムにおけるキャッシ
ュ・メモリ中のワードへのアクセスを管理する装置は、
プロセッサの２つにより参照されているキャッシュ・メ
モリの１つのラインを、このラインの各々のワードがプ
ロセッサの多くとも１つにより参照されるように識別す
る手段と、前記２つのプロセッサにより参照された前記
ライン内の各々のプロセッサにより変更されているワー
ドに対する各々のプロセッサへの排他的制御を与える手
段と、他のプロセッサにより変更されている各々の私用
キャッシュ・メモリ中のワードを無効にする手段と、前
記キャッシュ・メモリのいずれかに常駐された後、任意
のプロセッサにより変更されてないワードに対して全て
のプロセッサに読出し専用アクセスを与える手段とを備
えるワード・アクセス管理装置。
【請求項３】複数のプロセッサと、共有主メモリと、シ
ステム制御要素とを備え、各々のプロセッサがそれぞれ
のキャッシュ・メモリを有し、各々のキャッシュ・メモ
リがメモリ・ワードのラインを保持するコンピュータ・
システムにおけるメモリ・ワードへのアクセスを管理す
る装置であって、各々のプロセッサに結合され、プロセ
ッサにより変更されているキャッシュ・メモリ中のデー
タ・ラインを識別する第１識別手段と、各々のプロセッ
サに結合され、前記プロセッサのうちの第１のプロセッ
サにより変更されている第１ワードと前記プロセッサの
うちの第２のプロセッサによりアクセスされている第２
ワードとを格納する各々のキャッシュ・メモリ中の各々
のデータ・ラインを識別する第２識別手段と、前記シス
テム制御要素に結合され、前記プロセッサの１つからの
リクエストに応じて前記キャッシュ・メモリの１つのラ
イン中のワードに対するアクセスを得て、前記第１識別
手段から、前記プロセッサのうちの他のプロセッサがア
クセス中のワードを前記ラインが格納できるか否かを決
定し、前記プロセッサのうちの１つによるアクセスは前
記ワードを変更する第１制御手段と、この第１制御手段
による決定に応答して、第１識別手段から第２識別手段
にラインを転送し、２つのプロセッサの一方がワードに
対する書込みアクセスを持つとき２つのプロセッサがラ
イン中の１ワードに対する同時アクセスを得ないように
する第２制御手段とを備えるメモリ・ワード・アクセス
装置。
【請求項４】前記第１識別手段は、前記キャッシュ・メ
モリの１つに常駐された後、変更されたメモリ・ワード
を識別する変更ワード識別手段をさらに備え、前記第２
識別手段は、排他制御の下にあるか、または読出し専用
制御の下にあるか、または前記複数のプロセッサの１つ
によるアクセスに対して有効でないかのいずれかである
ライン内の個別ワードを識別するセクタ化ライン・ディ
レクトリ手段をさらに備え、前記第２制御手段は、前記
第１プロセッサにより変更されている第１ワードと、前
記第１プロセッサおよび第２プロセッサのそれぞれのキ
ャッシュ・メモリに常駐された後、第２プロセッサによ
り参照されている第２ワードとを含むラインを前記セク
タ化ライン・ディレクトリ手段で識別するセクタ化手段
を備える請求項３記載のメモリ・ワード・アクセス装置
。
【請求項５】前記第２制御手段は、前記セクタ化ライン
・ディレクトリ手段が前記複数のプロセッサのうちの１
つを除く他のいかなるプロセッサもワードに対する排他
的制御を有さないことを示すとき、前記複数のプロセッ
サのうちの１つに係るキャッシュ・メモリに常駐するラ
イン内のワードの排他的制御を前記１つのプロセッサに
与える共有排他的制御手段と、前記１つのプロセッサが
排他的制御を有するワードを前記１つのプロセッサに係
るキャッシュ・メモリに格納するアクセスを与える手段
と、前記いかなる他のプロセッサも排他的制御を有さな
いワードを前記１つのプロセッサに係るキャッシュ・メ
モリから取り出すアクセスを与える手段と、他のプロセ
ッサに係るキャッシュ・メモリ内のワードを無効にする
前記１つのプロセッサのための手段とをさらに備える請
求項４記載のメモリ・ワード・アクセス装置。
【請求項６】前記第２制御手段は、複数のプロセッサの
うちの１つのプロセッサのキャッシュ・メモリに常駐す
るラインで、他のいかなるプロセッサも選択されたワー
ドに対する排他的制御を有さないとき、他のプロセッサ
のキャッシュ・メモリに常駐する前記ライン内の前記選
択されたワードに対する排他的制御を前記１つのプロセ
ッサに与える共有排他的制御手段と、前記ラインが他の
プロセッサのキャッシュ・メモリに常駐したままのとき
、前記１つのプロセッサに対するアクセスを与えてこの
プロセッサが排他的制御を有するワードにデータを格納
する手段と、前記１つのプロセッサに対するアクセスを
与えて、前記ラインが他のプロセッサのキャッシュ・メ
モリに常駐したままのとき、いかなる他のプロセッサも
排他的制御を持たないワードを取り出す手段と、他のプ
ロセッサのキャッシュ・メモリのワードが含まれる全体
のラインを無効にすることなしに前記ワードを無効にす
る前記１つのプロセッサのための手段とをさらに備える
請求項３記載のメモリ・ワード・アクセス装置。
【請求項７】複数のプロセッサと、共有主メモリと、シ
ステム制御要素とを備え、各々のプロセッサがメモリ・
ワードのラインを保持するキャッシュ・メモリを有する
システムにおけるキャッシュ・メモリ中のデータへのア
クセスを管理する装置であって、データ・ワードを含む
ラインが前記キャッシュ・メモリの１つに常駐された後
、変更されているデータ・ワードとを識別する変更ライ
ン識別手段と、第１ワードが１つのプロセッサにより変
更されており、また第２ワードがキャッシュに常駐され
た後、少なくとも１つの他のプロセッサにより参照され
ているラインをマークするセクタ化手段と、このセクタ
化手段に応答して、このセクタ化手段により排他的制御
下にあるとして、特定プロセッサの読出し専用制御下に
あるまたは無効であるとしてマークされたライン内の個
別ワードを識別するセクタ化ライン・ディレクトリ手段
と、マークされたライン内のワードが前記プロセッサの
排他的制御下にあるときにのみ前記ワードに各々のプロ
セッサが情報を格納することを許容し、さらに排他的制
御または読出し専用制御の下にあるとしてマークされた
前記ライン内のワードからのみ各々のプロセッサが情報
を取り出すことを許容する共有排他的制御手段とを備え
たデータ・アクセス管理装置。
【請求項８】前記変更ワード識別手段は、ワードが格納
動作のために参照されたとき、これらのワードのそれぞ
れのキャッシュ・アドレスが格納されるメモリ要素を備
える請求項７記載のデータ・アクセス管理装置。
【請求項９】前記セクタ化ライン・ディレクトリ手段は
、データを格納するメモリ要素を備え、ライン内のそれ
ぞれのワードが読出しアクセスに対して有効か否か、そ
れぞれのワードが書込みアクセスのために排他的制御の
下で保持されるか否か、さらにそれぞれのワードがキャ
ッシュに常駐しているとき変更されたか否かを識別する
請求項７記載のデータ・アクセス管理装置。
【請求項１０】複数のプロセッサと、共有主メモリと、
システム制御要素と、共有キャッシュ・メモリとを備え
、各々のプロセッサがメモリ・ワードのラインを保持す
るそれぞれの私用キャッシュ・メモリを有するシステム
におけるキャッシュ・メモリ中のデータへのアクセスを
管理する装置であって、私用キャッシュ・メモリ中のデ
ータ・ラインに対して、このデータ・ライン中の各々の
データ・ワードがプロセッサの多くとも１つにより参照
されるように、少なくとも１つの私用キャッシュ・メモ
リ内に常駐しているときプロセッサの少なくとも２つに
より参照される前記データ・ラインを識別する識別手段
と、この識別手段に応答して識別されたライン内のデー
タ・ワードをアクセスしているプロセッサに対するアク
セスを与える制御手段と、私用キャッシュ・メモリ中の
データ・ラインに対して、このデータ・ライン内の少な
くとも１つのデータ・ワードがプロセッサの少なくとも
２つにより参照されるように、私用キャッシュ・メモリ
内に常駐しているときプロセッサの少なくとも２つによ
り参照される前記データ・ラインを共有されたとしてマ
ークする他の識別手段と、この他の識別手段に応答して
、この他の識別手段により共有されたとしてマークされ
た前記データ・ラインを共有キャッシュ・メモリに格納
し、私用キャッシュ・メモリに共有されたとしてマーク
された前記データ・ラインの全てのコピーを無効にする
他の制御手段とを備えるデータ・アクセス管理装置。
【請求項１１】共有主メモリと、システム制御要素と、
各々がそれぞれの私用キャッシュ・メモリを有する少な
くとも２つのプロセッサとを備えるコンピュータ・シス
テムにおけるキャッシュ・メモリ中のデータへのアクセ
スを管理する方法であって、キャッシュ・メモリ中のデ
ータ・ラインに対して、このデータ・ライン中の各々の
データ・ワードがプロセッサの多くとも１つにより参照
されるようにプロセッサの少なくとも２つにより参照さ
れる前記データ・ラインを識別するステップと、識別さ
れたライン中のデータ・ワードをアクセスしているプロ
セッサに対して書込みアクセスを与えるステップと、１
つ以上のプロセッサが前記データ・ライン中の１ワード
に対する同時的書込みアクセスを得ないようにするステ
ップとを含むデータ・アクセス管理方法。
【請求項１２】共有主メモリと、システム制御要素と、
各々がメモリ・ワードのラインを保持するそれぞれの専
用キャッシュ・メモリを有する少なくとも２つのプロセ
ッサとを備えるコンピュータ・システムにおけるキャッ
シュ・メモリ中のワードへのアクセスを管理する方法で
あって、プロセッサの２つにより参照されているキャッ
シュ・メモリの１つのラインを、このラインの各々のワ
ードがプロセッサの多くとも１つにより参照されるよう
に識別するステップと、前記２つのプロセッサにより参
照された前記ライン内の各々のプロセッサにより変更さ
れているワードに対する各々のプロセッサへの排他的制
御を与えるステップと、他のプロセッサにより変更され
ている各々の私用キャッシュ・メモリ中のワードを無効
にするステップと、前記キャッシュ・メモリのいずれか
に格納された後、プロセッサにより変更されていないワ
ードに対して全てのプロセッサに読出し専用アクセスを
与えるステップとを含むデータ・アクセス管理方法。
【請求項１３】共有主メモリと、システム制御要素と、
各々がメモリ・ワードのラインを保持する私用キャッシ
ュ・メモリを有する少なくとも２つのプロセッサとを備
えるコンピュータ・システムにおけるキャッシュ・メモ
リ中のデータへのアクセスを管理する方法であって、デ
ータ・ワードを収容するラインが前記キャッシュメモリ
に常駐された後、変更された前記データ・ワードを識別
するステップと、プロセッサの１つにより変更され、キ
ャッシュに配置されてから少なくとも１つの他のプロセ
ッサにより参照されている各々のラインであって、この
ラインに対してその中のいかなる信号ワードもプロセッ
サの１つ以上により参照されていない各々のラインをセ
クタ化されたものとして識別するステップと、各々が前
記プロセッサの１つの排他的制御下にあり、また前記プ
ロセッサの１つの読出し専用制御下にあるかまたは無効
である前記セクタ化ライン内の個別ワードの制御状態を
識別するステップと、前記セクタ化ライン内のワードが
プロセッサの排他的制御下にあるとして識別されたとき
にのみ各々のプロセッサが前記ワードに格納することを
可能にし、さらにプロセッサの排他的または読出し専用
制御下にあるとして識別される前記セクタ化ライン内の
ワードのみから、各々のプロセッサが取り出すことを可
能にするステップとを含むデータ・アクセス管理方法。
【請求項１４】共有主メモリと、システム制御要素と、
各々がメモリ・ワードのラインを保持する私用キャッシ
ュ・メモリを有する少なくとも２つのプロセッサとを備
えるコンピュータ・システムにおけるキャッシュ・メモ
リ中のメモリ・ワードへのアクセスを管理する方法であ
って、（ａ）各々のプロセッサのキャッシュ・メモリに
常駐された後、変更されたラインのアドレスを記録する
ステップと、（ｂ）前記記録されたライン内で変更され
ている各々のデータ・ワードの位置を記録するステップ
と、（ｃ）システム制御要素により状態フラグを設定し
て、キャッシュに配置された後１つのプロセッサにより
変更され少なくとも１つの他のプロセッサにより参照さ
れているラインであって、これに対してその中のいかな
る単一ワードも１つ以上のプロセッサにより参照されて
いない前記ラインをセクタ化されたとして識別するステ
ップと、（ｄ）セクタ化されたとして識別されている各
々のライン内の個別ワードに対して、各々のワードが前
記プロセッサの１つの排他的制御下にあり、前記プロセ
ッサの１つの読出し専用制御下にあるか無効であること
を示すアクセス制限を記録するステップと、（ｅ）前記
セクタ化ライン内のロードが各々のプロセッサの排他的
制御下にあることをアクセス制限が示したときにのみ各
々のプロセッサがワードに格納することを可能にし、前
記ワードが各々のプロセッサの排他的または読出し専用
制御の下にあることをアクセス制限が示したときにのみ
各々のプロセッサが前記セクタ化ライン内のワードから
取り出すことを可能にするステップと、（ｆ）前記プロ
セッサの１つが他のプロセッサのキャッシュ・メモリ中
の全体のラインを無効にすることなしに前記他のプロセ
ッサのキャッシュ・メモリに保持されるワードの排他的
制御を要求することを可能にするステップと、（ｇ）シ
ステム制御要素を用いて、１つのプロセッサによる排他
的制御に対するリクエストに応じて他のプロセッサのキ
ャッシュ・メモリ中のワードを無効にするステップとを
含むデータ・アクセス管理方法。
【請求項１５】前記ステップ（ｄ）は、前記１つのプロ
セッサのキャッシュ・メモリに常駐された後このプロセ
ッサにより変更されている各々のワードに対する排他的
制御をこのプロセッサが有することを示す排他的フラグ
を設定するステップと、前記１つのプロセッサのキャッ
シュ・メモリに格納されて他のプロセッサにより変更さ
れていない各ワードの有効コピーを前記プロセッサが有
することを示す有効フラグを設定するステップとを含む
請求項１３記載のデータ・アクセス管理方法。
【請求項１６】変更されたラインおよびセクタ化された
ラインのアドレスを、置き換えられるべきアドレスを選
択する最低使用頻度アルゴリズムを用いて、より最近変
更されたラインおよびセクタ化されたラインのアドレス
と置き換える請求項１４記載のデータ・アクセス管理方
法。
【請求項１７】共有主メモリと、共有キャッシュ・メモ
リと、システム制御要素と、各々がメモリ・ワードのラ
インを保持する私用キャッシュ・メモリを有する複数の
プロセッサとを含むコンピュータ・システムにおけるキ
ャッシュ・メモリ中のワードへのアクセスを管理する方
法であって、私用キャッシュ・メモリ中のデータ・ライ
ンが、少なくとも１つの専用キャッシュ・メモリに常駐
しているとき複数のプロセッサの２つにより私用キャッ
シュ・メモリ中のどのデータ・ラインが参照されている
かを識別するステップであって、前記参照が前記識別さ
れたデータ・ライン中の各々のデータ・ワードが複数の
プロセッサの１つだけにより参照されるようになされる
ステップと、２つのプロセッサに対して、これらの２つ
のプロセッサにより参照される前記データ・ラインの１
つのアクセスを与えるステップであって、前記データ・
ライン中の各々のデータ・ワードが唯一のプロセッサに
より参照されているステップと、私用キャッシュ・メモ
リに常駐しているとき複数のプロセッサの２つにより、
前記データ・ラインの各々の少なくとも１つのデータ・
ワードが２つのプロセッサにより参照されているように
、参照されているキャッシュ・メモリ内のデータ・ライ
ンを共有されたとしてマークするステップと、前記共有
されたとしてマークされたデータ・ラインを共有キャッ
シュ・メモリに格納するステップと、前記私用キャッシ
ュ・メモリの共有されたとしてマークされた前記データ
・ラインの全てのコピーを無効にするステップとを含む
ワード・アクセス管理方法。