JPH02236749A - キャッシュ制御装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 本発明は、一般にマルチプロセッサ・システムにおける
キャッシェ、さらに具体的には、キャッシュ中の変更さ
れた行がそのキャッシュによって変更されたのか、それ
とも他のキャッシュによって変更されたのかを示す変更
ビットを、キャッシュ・ディレクトリ中に追加して使用
することに関する。

Ｂ．従来技術及びその問題点 現代の高性能プログラム記憶式ディジタル・コンピュー
タは、通常、命令及びデータを主記憶装置から取り出し
、取り出した命令及びデータをキャッシュに記憶する。

キャッシュとは、コンピュータの主記憶装置よりも普通
ずっと小さくかつずっと速い局所記憶装置である。ほぼ
すべての高性能ディジタル・コンビュータは、キャッシ
ュを使用しており、市販のマイクロプロセッサにも局所
キャッシュを備えたものがある。

キャッシェが開発されたのは、最新のパイプライン方式
プロセッサにふさわしいアクセス時間で動作する、極め
て大型の記憶装置を手頃なコストで製作するのが不可能
だったからである。しかし、プロセッサに遅れずに動作
できる、安価な小型の記憶装置を製作することは可能で
ある。キャッシュ中の命令はプロセッサがただちにアク
セスできるので、コンピュータの速度を上げるためにキ
ャッシュが使われて来た。

一度参照された項目（命令またはデータ）は近い将来再
度参照される傾向があることが認められている。この性
質は「参照の時間的局所性」と呼ばれ、最近に参照した
項目をキャッシュに記憶しておく理論的根拠である。ま
た、ある項目が参照された場合、その参照項目に物理的
に近接している他の項目も参照される可能性が大きいこ
とも認められている。この第２の性質は、「参照の空間
的局所性」と呼ばれ、連続する諸項目のブロックである
キャッシュ行を記憶しておく理論的根拠である。

キャッシュは、多重プロセッサ・システムでも単一プロ
セッサ・システムでも使用可能である。

共通のオペレーティング・システム及び記憶装置を共用
するいくつかのプロセッサ（ＣＰ）がそれ自体のキャッ
シュを有する、緊密結合多重プロセッサ・システムと呼
ばれる型式の多重プロセッサ（ＭＰ）システムでは、各
キャッシュが、いくつかのキャッシュ中に同時に存在す
るキャッシュ行に何が起こったかを知る必要があるので
、さらに別の問題が生じる。多数のＣＰが同じ主記憶装
置を共用する多重プロセッサ・システムでは、アクセス
が出されたとき、各ＣＰがアーキテクチャ仕様に基づい
てデータの最近に更新されたバージロンを得ることが必
要である。この要件のため、キャッシュのコヒーレンス
問題としばしば呼ばれる、キャッシュ相互間のデータ整
合性を常に監視する必要がある。

従来技術の多重プロセッサ・システムには、様々な型式
のキャッシュが存在する。第１の型式のキャッシュはス
トアスルー（ＳＴ）型キャッシュであり、常に主記憶装
置に対するデータ変更を更新するために、ＣＰが直接主
記憶装置（または第２段キャッシュ）にデータを記憶す
るのに干渉しない。主記憶装置へのストアスルーが更新
されると、その記憶を開始したＣＰのキャッシュ以外の
キャッシュ中にあるキャッシュ行のコピーを無効化する
ため、適当な相互間合せ（ＸＩ）動作を行なわれること
ができる。通常、ストアスルー型キャッシュ設計では、
データ記憶を組み込むためにかなりの主記憶装置の帯域
幅を必要とする。

もう一つの型式のキャッシュ設計は、ストアイン型キャ
ッシュ（Ｓ　Ｉ　Ｃ）である。ストアイソ型キャッシュ
は、米国特許第３７３５３８０号明細書及び第３７７１
１３７号明細書に記載されている。ＳＩＣキャッシュ・
ディレクトリは、米国特許第４３９４７３１号明細書に
詳説されている。

この開示では、ストアイソ型キャッシュ内の各行が、独
占／読取り専用（ＥＸ／ＲＯ）フラグ・ビットで制御さ
れる多重プロセッサ共用可能性を有する。ストアスルー
型キャッシュとストアイソ型キャッシュの主な違いは、
ストアイン型キャッシュでは記憶がすべてキャッシュ自
体を対象している（したがって、記憶されたキャッシュ
行がストアイン型キャッシュ中にない場合にはキャッシ
ュ・ミスとなる）ことである。ストアイン型キャッシュ
設計では、コピーが遠隔キャッシュにある場合、取出し
ミスのとき、キャッシュ間転送バス（ＣＴＣ）を介して
データ転送が行なえる。各キャッシュ内のディレクトリ
のコピーを含む記憶制御エレメントが使用される。この
ため、相互間合せ（ＸＩ）決定をかなり効率良く解決す
ることが可能となる。

通常、キャッシュ行の変更は、そのキャッシュ行がキャ
ッシュから置換されたときにだけ主記憶装置に対して更
新される。

キャッシュ内のキャッシュ行は、典型的には、通常ＬＲ
Ｕ行をエージ・アウトする交換アルゴリズムに従って置
換される。ストアイン型キャッシュ設計では、このよう
な修正／変更済みキャッシュ行が、エージ・アウトされ
るとき、記憶装置にも書き込まれる。その結果、ストア
イン型キャッシュ設計では、主記憶装置の帯域幅が減少
する代わりに、コヒーレンス制御がより複雑となり、相
互問合せの廃棄によって不利が生じる。相互問合せが廃
棄されるのは、一方のＣＰからのデータ・アクセスで、
もう一方のＣＰのキャッシュ中で変更されたキャッシュ
行が見つかったときである。

キャッシュ・ディレクトリは、そのキャッシュ行が読取
り専用（ＲＯ）か、独占（ＥＸ）か、変更済み（ＣＨ）
か、それとも無効（ＩＮＶ）かに関する情報を含んでい
る。

ＲＯとなっているキャッシュ行は、読取り専用状態でだ
け有効である。プロセッサは、そのキャッシュ行からは
取出ししかできない。キヤ，シュ行への記憶は禁止され
ている。このキャッシュ行は、異なるキャッシュ間で同
時に共用することができる。

’ＥＸとなっているキャッシュ行は、有効であるが、あ
るプロセッサのキャッシュ中にだけ現われ、他のどの（
遠隔）キャッシュにも常駐しない。その１つの（所有）
プロセッサだけが、そのキャッシュ行に記憶することを
許されている。

ＣＨとなっているキャッシュ行は、その行が有効かつＥ
Ｘであることを示すだけでなく、それに記憶が行なわれ
たことも示す。すなわち、主記憶装置中のコピーが最新
のものではない可能性がある。ＣＨ行が置換されるとき
、廃棄動作を介して、そのコピーが主記憶装置に送られ
る。

ＩＮＶキャッシュ行は、無効となっている行である。

典型的なコンピュータφシステムでは、第１のプロセッ
サＰ，がキャッシュ中のあるキャッシェ行から命令また
はデータを要求することがある。

それ自体のキャッシュが検査され、要求した特定のキャ
ッシュ行が読取り専用（ＲＯ）状態の場合は、記憶要求
を行なうことができ、記憶制御エレメント（ＳＣＥ）を
介して、そのキャッシュ行を独占（ＥＸ）状態にする。

そのキャッシュ行が独占状態になると、記憶制御エレメ
ント（ＳＣＥ）は、他のキャッシュに、そのキャッシュ
行が無効であり、第１のキャッシュがそのキャッシュ行
に自由に書き込めると指示する。そのキャッシュ行が一
度書き込まれると、そのキャッシュ行が変更済みである
ことを示すＣＨビットがセットされる。

その後、第２のプロセッサＰ２がそのキャッシュ行を要
求した場合、変更ビットはセットされたままであり、Ｐ
２がこのキャッシュ行に記憶を行なわなくても、変更ビ
ットはセットされたままになる。これは、キャッシュ間
パスを使ってキャッシュ行が転送されるからである。Ｃ
Ｈビットがオンのままなのは、そのキャッシュ行が主記
憶装置を通過していない（すなわち、ＣＨビットのオン
は、主記憶装置が最新の状態でないことを示す）からで
ある。ただし、変更ビットがセットされたままになって
いる限り、このキャッシュ行は、いつでもただ１つのキ
ャッシュ専用でなければならない。

上記の手法では、異なる中央演算処理装置からの取出し
によって同時に共用できるはずのキャッシュ行が大部分
の時間、強制的に１つのキャッシュ中に常駐することに
なるので、並行性が不必要に失われる。たとえば、より
頻繁にアクセスされ、ある時間間隔の間に比較的たまに
しか変更されないキャッシュ行Ｌを考えてみる。Ｌがプ
ロセッサによって変更されると、これはＬＲＵ置換によ
って実際にキャッシュから置換されるまで、異なるキャ
ッシュの間で大体ＣＨであり続けることとなる。Ｌが遠
隔キャッシュ中にある場合には、プロセッサがキャッシ
ュ行Ｌ上でデータ取出しを出すごとに相互間合せ（ＸＩ
）が必要となる。

上記のような異常が生じるのは、ディレクトリ項目中の
ＣＨビットが、このような変更済みキャッシュ行がもは
や近いうちに変更を受ける可能性がないのかどうかを示
すことができないためである。

このような問題は、たとえば、キャッシェに対して最初
に変更が加えられる電源投入時にしばしば生じ、その後
は、通常このキャッシェ行に対する読取り専用（ＲＯ）
状態だけが必要である。変更ビットは、そのキャッシュ
行がエージ・アウトされて主記憶装置にダンプされるま
で、リセットされない。

キャッシュが大型になり、多重プロセッサ・システム内
のＣＰＵの数が増加するにつれて、この問題はさらに大
きくなる。キャッシュが大型になると、キャッシュ行は
それほど速くエージ・アウトしなくなり、またＣＰＵの
数が増加するにつれて、キャッシュ行が、エージ・アウ
トする機会を得ないうちに、ＣＰＵの間を次々にまわさ
れる傾向が増す。

当技術分野では、様々なキャッシュ管理技法が知られて
いる。しかし、変更ピットの使用が制限されているため
、キャッシュの並行性の喪失を最小限に抑えることを対
象とする既知の技術はない。

以下は、キャッシュ制御機構に関する代表的な従来技術
である。

米国特許第４４８４７１２号明細書は、２段キャッシュ
階層（ＬＬ／Ｌ２）における第２段キャッシュ置換の方
策を扱っている。Ｌ１はプロセッサ専用（局所）キャッ
シュであり、Ｌ２は全プロセッサが第２段で共用する。

Ｒビット及びＬ２ブロック項目を、そのブロックを置換
優先順位に入れるべきかどうかの指標として使用する。

この開示では、ＤＬＡＴヒット／ミス時にＲビットを操
作する方法をいくつか提案している。本発明は、第２段
キャッシュ（Ｌ２）階層から独立しており、第１段のプ
ロセッサ局所キャッシュにおけるデータ行の並行性にの
み関する。

米国特許第４４４５１７４号明細書では、共通キャッシ
ュを使用し、共用オーバーヘッドを減少させることに基
づく性能の利点が特許請求されている。共通手ャッシュ
は、第２段キャッシュとしてでなく、プロセッサの専用
キャッシュの最上部にある第１段キャッシュとして使用
される。この開示では、主として、相互間合せ（ＸＩ）
が観察され、キャッシュ行へのアクセスで、その行が別
のプロセッサの専用キャッシュ中でＣＨになっているこ
とが判明するかどうかに基づいて、そのキャッシュ行を
共用キャッシュに移動すべきがどうか決定することを提
案している。損害を与える共用が遠隔ＣＨ状態を介して
検出され、次いで、そのキャッシュ行が、すべてのプロ
セッサにとって速いと考えられる共用キャッシュに入れ
られる。

本発明では、損害を与える共用特性が消えるとき、異な
るキャッシュ中のキャッシュ行を読取り専用状態にさせ
ることによって、並行性が実現される。

米国特許第４１８１９３７号明細書には、２段キャッシ
ュ階層における多重プロセッサ（ＭＰ）キャッシュ置換
方式が教示されている。全プロセ，サが共用するＬ２か
らのブロックの置換を決定するとき、第１段プロセッサ
・キャッシュ内のコピーの数がより少ないブロックによ
り高い優先順位が与えられる。これは、より良好なＬ２
置換の方策であり、Ｌｌでの並行性を増大させるものと
思われる。本発明は、Ｌ２置換には関係しない。

米国特許第４５０３４９７号明細書では、ＣＨ行が遠隔
プロセッサによってアクセスされたとき、その行がＣＨ
かつ独占コピーとして、主記憶装置にアクセスすること
なく転送されるという、キャッシュ間転送の多重プロセ
ッサ設計が論じられている。本発明はこの設計に対する
改良であり，ＣＨビットに対する変更を必要とする。

米国特許第４３９４７３　１号明細書には、相互間合せ
状況（すなわち、キャッシュ行が遠隔でＥＸまたはＣＨ
にされる）で、キャッシュ行が、遠隔キャッシュ中で変
更されたことが判明したときにだけ、（ＣＨでな＜）Ｅ
Ｘとして取り出される。

この開示では、キャッシュ間転送環境は論じられていな
い。本発明は、遠隔変更状況で、キャッシュ間転送環境
に対して、この種のＥＸ（ただしＣＨも）取出しを行な
う能力を提供する。これは、キャッシュ間転送機能を使
うと、ＣＨ行をＥＸ及びＣＨとして直接別のキャッシュ
に転送でき、したがって、主記憶装置の更新（廃棄）ト
ラフィックが不要となるので、いくつかの利点を有する
。

さらに、このシステムでは、ＣＨ行の状態（すなわち、
変更が最近の記憶によるものかどうか、あるいは変更が
やりとりされて並行性を不必要に失ったかどうか）を決
定できない。

Ｃ．発明が解決しようとする問題点 したがって、本発明の目的は、キャッシュ行がどのくら
い最近に変更されたかを明らかにするキャッシュ・コヒ
ーレンス機構を提供することにある。

本発明のもう一つの目的は、キャッシュ行が遠隔の過去
の事象として変更されることによる、その並行性に対す
る不必要な制限を避けることにある。

本発明のもう一つの目的は、キャッシュ行が最近変更さ
れていない場合、そのキャッシュ行を読取り専用にして
、すべてのプロセッサにとって使用可能にさせることで
ある。

Ｄ．問題点を解決するための手段 本発明は、ＣＨ状態がＣＨ１ｏｃとＣＨｒｅｍの２つの
副状態に分けられるという、キャッシュ・コヒーレンス
機構を記載している。ＣＨｌｏｃ状態とは、キャッシュ
が局所プロセッサによって最近に記憶されたことを意味
する。ＣＨ　　状態とは、キャッｒｅー シュ行が、変更済みデータ、すなわち別のキャッシュか
ら受け取ったもので、そのキャッシュによって変更され
、最後の取出し時に継承されたデータだけを含むことを
意味する。本発明は、ＣＨ１ｏｃ状況ビットを使って、
キャッシュ行Ｌを上例の両方のキャッシュ中で読取り専
用に保つべきかどうかを決定するものである。

Ｅ．実施例 ＩＢＭ社３０９０シリーズなどの多重プロセッサ・メイ
ンフレーム・コンピュータでは、ストアイソ型キャッシ
ュが使用されている。各プロセッサＰ１ごとに、ストア
イン型キャッシュＣＩがある。

各キャッシュにディレクトリが付随し、ディレクトリ中
の各項目は、可能な３つの状態、ＩＮＶ１ＲＯ．ＥＸの
うちの１つをとることができる。

ＩＮＶ　　−　これは、キャッシュ項目が無効なことを
示す。

ＲＯ　−　これは、キャッシュ項目が読取り専用状態で
育効なことを示す。プロセッサは、このキャッシュ行か
ら取り出すことしかできず、このキャッシュ行への記憶
は禁止されている。

ＥＸ　　一　これは、キャッシュ行が有効であり、それ
が現在入っているキャッシュ以外のキャッシュには常駐
していないこと（すなわち、独占）を示す。他のキャッ
シュは、遠隔キャッシュと見なされる。このキャッシュ
行を所有するキャッシュを所有しているプロセッサは、
このキャッシュ行への記憶を許されるが、所有していな
いプ、ロセッサは許されない。

各キャッシュ・ディレクトリ項目に関連するＣＨビット
（変更ビット）もある。キャッシュ中の有効なキャッシ
ュ行について、ＣＨビットは、その項目がＥＸ状態にあ
る場合にだけオンになる。

ＣＨビットがオンのとき、キャッシュ行がＣＨ状態にあ
ると言われる。ＣＨは、そのキャッシュ行が有効かつ独
占であるだけでなく、その行に記憶が行なわれたことも
示す。すなわち、共用される主メモリ（主記憶装置ＭＳ
）内のそのキャッシュ行のコピーが、プロセッサの１つ
によって行なわれた最近の変更を反映していないことが
ある。このキャッシュ行が置換されると、キャッシュ行
に対する変更が廃棄（ｃａｓｔｏｕｔ）動作と呼ばれる
機構によって主メモリに送られる。

システム内の複数のプロセッサが、共通記憶装置制御エ
レメン｝　（ＳＣＥ）に接続されている。

また、各プロセッサごとに、そのプロセッサのキャッシ
ュ用ディレクトリを維持するバッファ制御エレメン｝　
（ＢＣＥ）もある。あるプロセッサからの主要なメモリ
・アクセスは、すべてそのキャッシュに対して行なわれ
る。キャッシュ・ミスのとき（すなわち、キャッシュ行
がキャッシュ中で見つからないとき）、バッファ制御エ
レメントは記憶制御エレメントに、キャッシュ行のコピ
ーを獲得し、そのキャッシュ行にとって適正な状態（Ｒ
ＯまたはＥＸ）にするよう要求する。プロセッサからの
記憶で、そのキャッシュにおいてキャッシュ行がＥＸま
たはＣＨ杖態になっていないとき、バッフ１制御エレメ
ントは、記憶制御エレメントに独占杖態にせよとの要求
を送る必要が生じる。

プロセッサがキャッシュ中の有効な（ＥＸ）キャッシュ
行中に記憶を行なうとき、そのキャッシュ行がＣＨ状態
にセットされる。

プロセッサから要求を受け取ると、記憶制御エレメント
２４は、アーキテクチャ上の整合性を維持するために適
切な許可を与えるのに必要な処置を決定する。上記のＩ
ＢＭ３０９０などのコンビュータ・システムでは、記憶
制御エレメント２４が、プロセッサ・キャッシュ用ディ
レクトリのフビーを維持する。その後、記憶制御エレメ
ント２４は、別のキャッシュ中にそのキャッシュ行のコ
ピーがあるかどうか、及びそのコピーがどのキャッシュ
中に入っているかを決定することができ、さらに、その
キャッシュ行がＲＯ伏態かそれともＥＸ状態かを決定す
ることができる。記憶制御エレメントで、あるプロセッ
サにとってキャッシュ行がＥＸであると指示されたとき
、そのキャッシュ行は、特定の瞬間にそのキャッシュ中
でＣＨ状態にあることもないこともある。

ＩＢＭ３０９０システムには、キャッシュ間転送（ＣＴ
Ｃ）バス（２２）がある。したがって、キャッシュ行は
、直接主メモリを通過せず、キャッシュ間転送バス２２
を介して異なるキャッシュ間で転送される。従来技術の
装置からのメモリ・アクセスには、大別して、■取出し
（命令取出し）、Ｄ取出し（データまたはオペランド取
出し）、Ｄ記憶（データまたはオペランド記憶）の３種
がある。Ｉ取出し及びＤ取出しアクセスではデータが読
み取られ、Ｄ記憶ではメモリ内容が変更される。

ある種の状況（インターロック命令の場合など）では、
Ｄ取出して独占（ＥＸ）状態が必要となることがある。

キャッシュにアクセスするための動作は、次の通りであ
る。まず、プロセッサがそのキャッシュ中のキャッシュ
行Ｌに適正な許可を得てアクセスする場合、そのアクセ
スは、追加の動作なしに許可される。ＥＸ状態をとるキ
ャッシュ行には、３つの要求タイプ、■取出し、Ｄ取出
し、Ｄ記憶のどれもがアクセスできる。ただし、Ｄ記憶
では、記憶後にＣＨビットがオンになったＥＸ状態が必
要である。

プロセッサＰＬが命令取出しによってキャッシュ行Ｌを
要求し、キャッシュ行Ｌが遠隔プロセッサＰＪでＥＸで
ある場合、記憶制御エレメントはＰ１に、そのＥＸ状況
を解除するようにと通知する。

ＰＪのバッファ制御エレメントは、その信号を受け取る
と、キャッシュ間転送バスを介してそのキャッシュ行を
Ｐｌに転送する。ＰＪのバッファ制御エレメントｌθは
、キャッシュ行の主記憶装置２６への廃棄を実行させる
。それが終わったとき、プロセッサｉ（１０）のキャッ
シュ１８とプロセッサｊ（１２）のキャッシュ２０は、
共に読取り専用（ＲＯ状態）のキャッシュ行を有する。

プロセッサＰ＋（１０）がデータ取出し（Ｄ取出しまた
はオペランド取出し）によってキャッシュ行Ｌを要求し
、Ｌが遠隔プロセッサＰＪで独占状態のとき、記憶制御
エレメント２４はＰＪに、そのキャッシュ行Ｌに対する
ＥＸ状況を解除するように通知する。ＰＪのバッファ制
御エレメントは、その信号を受け取ると、上記と同様に
、キャッシュ間転送によってバス２２を介してキャッシ
ュ行ＬをＰ，に転送させる。キャッシュ行Ｌがキャッシ
ュｊ（２０）で変更されていない場合、キャッシュｌ（
１８）とキャッシュｊ　（２０）は共に、上記（■取出
しの場合）と同様に読取り専用状態のキャッシュ行Ｌを
獲得する。しかし、ＬがキャッシュｊでＣＨ（変更済み
）の場合には、プロセッサｉ（１０）はＣＨ杖態のキャ
ッシュ行（ＣＨヒットがオンになったＥＸ行）を受け取
り、プロセッサｊ（１２）のバッファ制御エレメント１
６はそれ自体のキャッシュからしを無効化する。最後の
状況は、遠隔ＣＨヒット時の条件付きＤ取出しＣＨと呼
ばれる。

プロセッサＩが■取出しまたはＤ取出しによってキャッ
シュ行Ｌについてキャッシュ・ミスとなり、記憶制御エ
レメント２４が、そのキャッシュ行がどの遠隔キャッシ
ュ（たとえば、プロセッサｊ）でもＥＸでないことを検
出したとき、記憶制御エレメント２４は、遠隔キャッシ
ュに常駐していることがわかった場合はその遠隔キャッ
シュからのキャッシュ行の転送をスケジューリングする
ことができ、実施態様によっては、主制御装置（２６）
からのキャッシュ行の取出しをスケジューリングするこ
ともできる。それが終わったとき、Ｄ取止しミスのため
行Ｌかどのキャッシュにもないことを記憶制御エレメン
ト２４が検出したとき以外は、プロセッサｉ（１０）は
、キャッシュ行Ｌを読取り専用状態で獲得する。Ｄ取出
してキャッシュ・ミスとなったキャッシュ行がどのキャ
ッシュにもないときは、ＩＢＭ３０９０などのメインフ
レーム・コンビ二一夕はＰ，に、主記［Ｌｉｌｉｔ２８
から新たに取り出したキャッシュ行に対する独占一状態
を許可する。

プロセッサｌがそれ自体のキャッシェ中で読取り専用の
キャッシュ行に対して独占状況を要求する場合、記憶制
御エレメント２４は、キャッシュ行Ｌが他の遠隔キャッ
シュ、たとえばプロセッサｊ（１２）に属するキャッシ
ュ２　（２０）中に常駐しているかどうか判定しなけれ
ばならない。

キャッシュ行Ｌが見つかった場合、記憶制御エレメント
はそれらの遠隔キャッシュ（キャッシュ２）に、そのコ
ピーを無効にするように通知する。次いで、記憶制御エ
レメント２４は、遠隔コピーがすべて無効にされたこと
を確認すると、プロセッサｉ　（１０）にキャッシュ行
Ｌに対するＥＸ状態を許可する。

プロセッサｉ（１０）がそのキャッシュに常駐していな
いキャッシュ行Ｌに対する独占状況を要求する場合、記
憶制御エレメント２４は、そのキャッシュ行が遠隔キャ
ッシュ（たとえばプロセッサｊ（１２）など）中でＥＸ
であるかどうか判定する。そうでない場合、そのキャッ
シュ行が遠隔キャッシュまたは主記憶装置２６からプロ
セッサｊ　（１０）に取り出され、キャッシュ行Ｌのあ
らゆる可能な遠隔なコピーに無効にするようにと通知す
る。あるいはまた、そのキャッシュ行が独占杖態の遠隔
キャッシュからプロセッサｌ（１０）に取り出される。

それには、遠隔キャッシ：Ｌ２０からのキャッシェ行の
無効化が必要である。後者の場合、プロセッサｉ（１０
）に転送されたキャッシュ行は、それが遠隔キャッシュ
中でもＣＨになっている場合には、やはりＣＨ状態にな
る。

上記の動作を、第２図ないし第４図に示す。第２図には
、プロセッサからの命令取出しアクセスを示す。ステッ
プ１００で、局所バッフ１制御エレメント１４は、プロ
セッサによってアクセスされているキャッシュ行がキャ
ッシュ中にあるかどうか調べるためテストする。イエス
の場合、キャッシュ・アクセスが許可され、そうでない
場合は、ステップ１０１で、バッファ制御エレメントが
記憶制御エレメント２４にミス要求を行なう。ステップ
１０２で、記憶制御エレメント２４は、キャッシュ行が
遠隔で独占かどうか決定する。そうでない場合、記憶制
御エレメント２４は主記憶装置または遠隔コピーからの
キャッシュ行取出しのスケジェーリングを行ない、読取
り専用状況が許可される。キャッシュ行が遠隔で独占的
に保持されている場合には、ステップ１０３で、記憶制
御エレメント２４は遠隔バッフ１制御エレメントに通知
する。ステップ１０４で、遠隔パッフ１制御エレメント
は、そのキャッシュ行が変更されている（ＣＨ）かどう
か決定する。そうでない場合には、遠隔バッファ制御エ
レメント１６は、キャッシェ行をキャッシェ間転送によ
って（キャッシュ間転・送バス２２を介し）要求側キャ
ッシュにコピーし、キャッシュ行を両方のキャッシュ読
取り専用（ＲＯ）であると指定する。しかし、キャッシ
ュ行が変更されている場合には、遠隔分岐制御エレメン
トがキャッシュ行を主記憶装置に廃棄する。

第３図は、プロセッサからのデータ取出しアクセスの流
れ図である。ステップ２００で、バッファ制御エレメン
ト１４は、プロセッサが要求しているキャッシュ行が局
所キャッシェ１８中に局所的に含まれているかどうかを
決定する。そうである場合、キャッシュ・アクセスが許
可される。しかし、そうでない場合には、ステップ２０
１で、バッファ制御エレメントは、記憶制御エレメント
２４にミス要求を行なう。ステップ２０２で、キャッシ
ュ行が遠隔で独占状態かどうかが決定される。

そうでない場合、記憶制御エレメント２４は主記憶装置
または別のキャッシュ中の遠隔コピーからのキャッシュ
行取出しのスケジューリングを行ない、読取り専用状況
が許可される。しかし、キャッシュ行は遠隔で独占吠態
である場合は、ステップ２０３で記憶制御エレメント２
４は遠隔バッファ制御エレメント１θに通知し、ステッ
プ２０４で、遠隔バッファ制御エレメント１８は、キャ
ッシェ行が変更されているかどうかを決定する。変更さ
れていない場合には、遠隔バッファ制御エレメント１８
は、キャッシュ行を要求側キャッシュ（１８）にコピー
し、そのキャッシュ行を主記憶装置に廃棄し、両方のキ
ャッシュ（１８及び２０）中でそのキャッシュ行を読取
り専用状況に指定する。

しかし、キャッシェ行が変更されている場合には、遠隔
バッファ制御エレメント１θはキャッシュ行を要求側キ
ャッシュ（１８）に移し、それを独占／変更済み（ＥＸ
／ＣＨ）にし、次いで自身のキャッシュ行のコピーを無
効にする。

第４図は、データ記憶アクセスのための処理を示す。ス
テップ３００で、パッファ制御エレメント１４は、プロ
セッサが要求しているキャッシュ行が局所キャッシュ１
８中にあるかどうかを決定する。そうである場合は、キ
ャッシュ・ヒットである。ステップ３０１で、パッファ
制御エレメント１４は、そのキャッシュ行が局所キャッ
シュ（１８）にとって独占状態かどうか決定する。そう
である場合、バッファ制御エレメント１４は、キャッシ
ュ・アクセスを許可し、ＣＨビットがオンになる。しか
し、そうでない場合には、ステップ３０２で、バッフ１
制御エレメント１４は記憶制御エレメント２４に、キャ
ッシュ行を独占状態にするよう要求する。次いで、記憶
制御エレメント２４は、遠隔コピーを無効にし、要求側
キャッシュ１８中のキャッシュ行に対する独占状況を許
可する。

しかし、キャッシュ・ヒットでない場合には、ステップ
３０３で、バッファ制御エレメント１４は記憶制御エレ
メントにそのキャッシュ行に対する要求を行ない、キャ
ッシュ行を独占状況に指定する。次いで、ステップ３０
４で、記憶制御エレメントは、そのキャッシュ行が遠隔
キャッシュ、たとえばキャッシュ２０中で独占状態かど
うか決定する。そうでない場合、記憶制御エレメント２
４は主記憶装置または遠隔キャッシュからのキャッシュ
行の取出しのスケジューリングを行ない、遠隔コピーを
無効にする。次いで、さらに、要求側キャッシュ中のキ
ャッシュ行に対する独占状況を許可する。しかし、キャ
ッシュ行が遠隔キャッシュ２０中で独占状態の場合には
、ステップ３０５で、記憶制御エレメント２４は遠隔バ
ッファ制御エレメント１６に通知する。次いで、遠隔バ
ッフ１制御エレメント１６は、キャッシュ行を要求側キ
ャッシュ１８に移し、独占／変更済み状態を割り当て、
次いで、それ自体のコピーを無効にする。

プロセッサｉからのデータ取出しキャッシュ◆ミスにつ
いて上記の説明から明らかなように、要求されたキャッ
シュ行は、特定のＤ取出しがキャッシュ行を読み取るこ
とを望むだけであるが、それが遠隔プロセッサｊ（１２
）中で変更されていることがわかった場合、変更済み（
ＣＨ）として転送される。後で、そのキャッシュ行がプ
ロセッサｉ（１０）によって変更される前に、プロセッ
サＪ　（１２）がそのキャッシュ行にアクセスしようと
望む場合には、キャッシュｌからキャッシュｊへのキャ
ッシュ行転送がもう１回必要となる。

プロセッサｉ　（１０）のデータ取出しミスのとき、キ
ャッシュ行が、主記憶装置への廃棄（すなわち、キャッ
シュ行を主記憶装置２６に再度記憶する）という犠牲を
払って、両方のキャッシュ中で読取り専用（共用）にさ
れる場合、この不必要なキャッシュ行転送というオーバ
ーヘッド及び関連する相互間合せ（ＸＩ）動作が節減で
きる。変更済みのデータ行は、データが取り出された後
まもなく変更される傾向があるので、この条件付きデー
タ取出しのＣＨ判定基準は、妥当な選択であることが以
前から分かっていた。その結果、ＣＨ状態を伴うデータ
取出しでは、主記憶装置廃棄トラフィック及びそれに続
＜ＥＸ状態の要求（キャッシュ行がＲＯ状態で記憶され
ているとき）がおそらくは避けられるはずである。

しかし、環境の変化によって、上記のデータ取出しＣＨ
判定基準が異常な挙動をもたらすようになってきた。Ｃ
Ｈ行は、これが命令取出しされる（あまりないと思われ
る）か、またはキャッシュからエージ・アウトし（置換
され）あとでミスにより再参照される場合にのみ、複数
キャッシュにより並行して（ＲＯ状態で）共用されるこ
ともできる。キャッシュがより大型となり、また多重プ
ロセッサ・システムに追加されるプロセッサの数が増加
するのにつれて、ＣＨ行が他のどのプロセッサによって
もアクセスされずにエージ・アウトする機会は、かなり
減少する。その結果、ＣＨ状況のキャッシュ行は、もは
や長い時間記憶されないときや、異なるプロセッサから
繰り返し読み取られるときでさえ、共用可能にならない
可能性が大きくなる。こうした並行性の無用な喪失は、
応用分野によっては、重大な性能上のネックになること
がある。

その理由は、ＣＨビットがデータ汚染（すなわち主記憶
装置の内容２８が最新のものでない）をも、キャッシュ
行が記憶され得る傾向をもつことをも示すためである。

ＣＨ行が異なるキャッシュの間を次々に回されるので、
ＣＨビットは、キャッシュ行がもはや変更されないとい
うことを反映できなくなる。

しかし、本発明では、キャッシュ行が最近プロセッサに
よって変更されたかどうかを示す、追加の状態をキャッ
シュ・ディレクトリ中でキャッシュ行に割り当てる。こ
の追加の状態を、本明細書ではＣＨＩＯｃ（局所変更）
と呼ぶ。キャッシュ行Ｌは、キャッシュｉが最後にその
行のコピーを受け取って以降に変更された場合、プロセ
ッサＩに対してＣＨＩｏｃ吠態にある。キャッシュが行
Ｌのコピーを得たとき、それはＣＨｌｏｃ状態にはない
が、プロセッサがその行に記憶を行なうとき、ＣＨ１ｏ
ｃ状態に入る。ＣＨ１。。状態は、ある行の変更される
傾向に関する指標として使用され、様々な多重プロセッ
サ・キャッシニの最適化に使用することができる。

第１図ないし第４図に示した、上記で論じた設計の修正
と考えられる実施例では、キャッシュ・ディレクトリ項
目当り１個の追加ビット（ＬＣＨビット）をバッファ制
御エレメント中で使用する。

ＬＣＨビットの操作について、以下で説明する。

ある行がキャッシェ中に取り出されるきき、関連するＬ
ＣＨビットがオフになる。しかし、ある行がプロセッサ
から記憶されるときは、関連するＣＨビットとＬＣＨビ
ットが共にオンになる。

ここで、多重プロセッサの動作を、主として、データ取
出しキャッシュ・ミスが遠隔に保たれている独占キャッ
シュ行に関係する状況に合わせて修正する。すなわち、
プロセッサｉ（１０）からのデータ取出しが、記憶制御
エレメント２４によって遠隔プロセッサｊ（１２）で独
占状態であることが判明した行Ｌに対してキャッシュ・
ミスになったとき、記憶制御エレメント２４はプロセッ
サｊ（１２）の遠隔バッフ１制御エレメントｊ（１８）
に、キャッシュ行Ｌに対するその独占状況を解除するよ
う通知する。プロセッサｊ（１２）のバッファ制御エレ
メントｊ　（１８）は、その信号を受け取ると、その行
がＣＨ１。。状態にあるかどうか（すなわち、関連する
ＬＣＨビットがオンかどうか）検査する。そうである場
合、その行が独占（ＥＸ）かつ変更（ＣＨ）状態をとる
プロセッサｉに（キャッシュ間転送バス２２を介して）
送られる。そうでない場合は、読取り専用（ＲＯ）状態
をとるプロセッサｉ（１０）が、その行Ｌを受け取る。

これは、行Ｌがキャッシェｊ　（２０）でＣＨ状況を有
する場合、主記憶装置２６への廃棄を伴う。

第５図は、ＬＣＨピットに関係する動作に関する、第３
図の論理ステップを示す。したがって、第３図の流れ図
は、行が遠隔キャッシュでもＣＨ１ｏｃ状態にある場合
は、ＥＸ取出し時に遠隔ＣＨ行に対してデータ取出しミ
スとなり、そうでない場合はＲＯ共用状態をもたらすよ
うに修正される。

そのため、行がもはや変更される傾向がないとき、若干
の余分のメモリ廃棄と引き換えに、行共用の並行性が増
加する。

第３図及び第５図を参照する。第３図のステップ２０２
で、記憶制御エレメント２４が、キャッシュ・ミスがあ
った後、アクセスまたは要求された行が遠隔で独占状態
であると判定した場合、第３図のステップ２０３に進ま
ず、第５図のステップ２０４のように修正された動作が
続行される。

このステップで、遠隔バッファ制御エレメント（１６）
は、その行がＣＨの杖況をとっているかどうか判定する
。ＣＨの状況をとらない場合、遠隔パッファ制御エレメ
ント１６がその行を要求側キャッシュにコピーし、主記
憶装置への廃棄を行ない、行を両方のキャッシュ・メモ
リ中で読取り専用状況にセットする。しかし、遠隔バツ
ファ制御エレメン｝（１Ｂ）が、行が変更されていると
判定した場合には、次に、ステップ２０５で、ＬＣＨビ
ットがオンになっているかどうかを判定する。ＬＣＨビ
ットがオンになっていない場合、遠隔バッファ制御エレ
メントは、行を要求側キャッシュにコピーし、主記憶装
置２６への廃棄を行ない、行を両方のキャッシュ中で読
取り専用にセットする。しかし、バッファ制御エレメン
トが、ＬＣＨビットがオンであると判定した場合には、
行をＥＸ／ＣＨ状態で要求側キャッシュに移動させ、そ
れ自体のコピーを無効にする。次いで、要求側キャッシ
ュがＬＣＨビットをオフにする。

上記の設計修正では、ＣＨ状態が２つの副状態ＣＨｌｏ
ｃ及びＣＨ，８一区分されていると考えることができる
。ただし、ＣＨ　　は別のキャッシュｒｅ諷 から運ばれた変更のために行が汚染されていることを意
味し、ＣＨＩｏｃはキャッシュ行が局所プロセッサから
の最近の記憶のために行が汚染されていることを意味す
る。

ＣＨＩｏｃ状態は、主として多重プロセッサ・キャッシ
ュ管理の支援に使われ、適切に実現されているならば、
アーキテクチャの正しさにとって重要ではない。したが
って、ＬＣＨビットに関する一時エラーを訂正するため
にＦＣＣを設ける必要はない。実施態様によっては、Ｌ
ＣＨビットをキャッシュ・アクセス（たとえば記憶）の
ためのクリティカル・パスに設ける必要もない。実施態
様によっては、単にＣＨｌｏｃ状態を近似して、、設計
の複雑さを減少させることも可能である。

この局所変更のコンセプトは、様々な多重プロセッサ・
キャッシュ設計に適用できる。たとえば、独占状態をと
るストアスルー型多重プロセッサ・キャッシュ設計で使
用できる。ストアイン設計の場合のように、ＣＨピット
を使用する必要はない。

ただし、ＣＨ１ｏｃ履歴は、依然として、データ取出し
キャッシュ・ミスでＥＸ状態が獲得されるかどうか決定
するために使用できる。

Ｆ．発明の効果 本発明によれば、プロセッサごとに局所キヤ，シュを持
つマルチプロセッサ・システムにおいて、キャッシュ行
がどのくらい最近に変更されたかに関する情報を獲得し
、最近変更されたものでないならば当該キャッシュ行を
読取り専用にしてすべてのプロセッサにとって使用可能
にするので、システムのパフォーマンスが向上する。

【図面の簡単な説明】

第１図は、本発明を使用する多重プロセッサ・システム
の構成図である。 第２図ないし第４図は、従来技術のキャッシュ動作を記
述する流れ図である。 第５図は、本発明の動作を示す流れ図である。 １０、１２・・・・プロセッサ、１４、１Ｂ・・・・バ
ッファ制御エレメント、１８、２０・・・・キャッシュ
、２４・・・・記憶制御エレメント、２６・・・・主記
憶装置。

Claims (1)

1. 【特許請求の範囲】 複数のプロセッサと主記憶装置を具備し、各プロセッサ
   は自身に関連づけられた局所キャッシュを具備している
   マルチプロセッサ・システムにおいて、キャッシュ行の
   取出を制御するための方法であって、 キャッシュ行に対する要求が当該キャッシュにとっての
   遠隔プロセッサによって行われた際に、当該キャッシュ
   行が当該キャッシュにとっての局所プロセッサによって
   変更されたか否かを判断し、判断結果が肯定的であるな
   らば、当該キャッシュ行に独占状態を割り当て、判断結
   果が否定的であるならば、当該キャッシュ行に読取り専
   用状態を割り当てる ことを特徴とする方法。