JPH0762836B2

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

Info

Publication number: JPH0762836B2
Application number: JP3268665A
Authority: JP
Inventors: フィリップ・ジョージ・エマ; ジョシュア・ウィルソン・ナイト; ケビン・パトリック・マコウリフィー; ジェイムス・ハーバート・ポメレーヌ; ルドルフ・ネイザン・リヒトシャーフェン; フランク・ジョン・スパラシオ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1990-10-31
Filing date: 1991-09-20
Publication date: 1995-07-05
Anticipated expiration: 2010-07-05
Also published as: US5291442A; JPH04260146A

Description

【発明の詳細な説明】

【０００１】

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

【０００２】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【００２５】

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

【００２６】

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

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

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

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

【００３０】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【０１０１】

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

【図面の簡単な説明】

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

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

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

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

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

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

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

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

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

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

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

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

【符号の説明】

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

───────────────────────────────────────────────────── フロントページの続き (72)発明者ジョシュア・ウィルソン・ナイトアメリカ合衆国ニューヨーク州モヒガンレイクサガモアアベニュー 3490 (72)発明者ケビン・パトリック・マコウリフィーアメリカ合衆国ニューヨーク州ピークスキルロームコート７ (72)発明者ジェイムス・ハーバート・ポメレーヌアメリカ合衆国ニューヨーク州チャッパカノースベッドフォードロード 403 (72)発明者ルドルフ・ネイザン・リヒトシャーフェンアメリカ合衆国ニューヨーク州スカースデールインズロード 24 (72)発明者フランク・ジョン・スパラシオアメリカ合衆国フロリダ州サラソタトレイパインズウェイ 3726 (56)参考文献特開平２−240764（ＪＰ，Ａ) 特開昭57−167189（ＪＰ，Ａ) 特開平２−247751（ＪＰ，Ａ) 特開平２−186456（ＪＰ，Ａ) 特開昭63−259748（ＪＰ，Ａ) 特開昭63−254543（ＪＰ，Ａ)

Claims

【特許請求の範囲】

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