JPH0743670B2 - ストアスルーキャッシュ管理システム - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、一般的にはマルチプ
ロセッサシステムのストアスルーキャッシュメモリ管理
に関し、より詳細には、大きな細分単位（例えば、ペー
ジ）で排他性が許可される、例えば排他的ライトスルー
・ライトアロケート（ＷＴＷＡＸ）管理を用いて排他的
に管理されるストアスルー環境に関する。この発明は、
排他性が解除されたときに、単一の伝送によって、全て
の変更されたラインに対してＸＩ（相互無効化）を実現
する。

【０００２】

【従来の技術】別々のプロセッサ上で同時に実行するこ
とができる動作を並列的に実行することによりスループ
ットの向上を図るために、高性能のマルチプロセッサ
（ＭＰ）コンピュータシステムが開発されている。この
ような高性能のＭＰコンピュータシステムは、独立にそ
して並列的に動作するが、互いに通信したり、或いはデ
ータを交換する必要があるときに主記憶装置（ＭＳ）と
通信したりすることもある多重中央処理装置（ＣＰ）に
よって特徴付けられる。これらのＣＰ及びＭＳは、デー
タを交換するために接続されなければならない入出力
（Ｉ／Ｏ）ポートを有する。

【０００３】複数のＣＰのそれぞれが自分のキャッシュ
を有する密結合マルチプロセッサシステムとして知られ
ているタイプのＭＰシステムにおいては、システムの種
々のレベルに同一性の問題が存在する。すなわち、メモ
リ階層の隣接レベル間に不一致が生じることがあり得
る。例えば、あるＣＰが自身のキャッシュのコピーを変
更したために、同じデータであっても内容の異なるもの
が複数のキャッシュに存在することがある。従って、そ
れぞれのプロセッサのキャッシュは、同時に幾つかのキ
ャッシュに存在するラインに起こッたことを知る必要が
ある。同一の主記憶装置を共用する多くのＣＰが存在す
るＭＰシステムにおいては、それぞれのＣＰは、アクセ
スが行われるときにアーキテクチャ仕様に従って最も最
近に更新された最新版のデータを得る必要がある。この
要求により、キャッシュ間のデータの同一性を絶えずモ
ニターする必要が生じる。

【０００４】このキャッシュの同一性の問題に対して多
くの解決法が提案されてきた。初期の解決法は、C.K. T
ang 著“Cache System Design in the Tightly Coupled
Multiprocessor System”、Proceedings of the AFIPS
（1976）及びL.M. Censier及びP. Feautrier“A New So
lution to Coherence Problems in Multicache System
s”、IEEE Transactions on Computers、Dec. 1978 、p
p.1112-1118に記載されている。 Censierらは、集中型
グローバルアクセス許可テーブルを用いて、書き込み可
能な共用データを複数のキャッシュに存在させることが
できる方式について述べている。しかし、著者らがその
結論の部分において述べているように、その二年前にTa
ngによって述べられたものと類似のアプローチには気が
ついていなかった。Tangはキャッシュのコピーディレク
トリを用いて状態を保持することを提案したが、 Censi
erらは各メモリブロックに類似の状態ビットでタグを付
けることを提案した。

【０００５】これらの初期のアプローチは、必要なとき
に相互照会（ＸＩ）を達成するための管理方法に関する
ものである。この概念は、プロセッサキャッシュがライ
ンのコピーを有し、複数のキャッシュのうちの一つがそ
のラインを変更した情報をグローバルディレクトリに記
録することであった。基本動作は、プロセッサがライン
に記憶を行ったときに、その状態をグローバルテーブル
に（変更ビットで）記録させることである。ストアイン
キャッシュが用いられているので、プロセッサキャッシ
ュ制御装置は、そのキャッシュディレクトリから、どの
ラインが変更されたものか、あるいは私用であるかがわ
かる。プロセッサにおける変更されていないラインへの
記憶は、記憶制御装置との同期と変更状態を最初に得る
こととを必要とするであろう。従って、記憶ブロック
は、キャッシュがシステムにおけるラインの唯一のコピ
ーを有しているときでさえ、プロセッサが実際にそれに
記憶を行わなかったならば、プロセッサに対して排他的
または変更可能とはなり得ない。

【０００６】より一般的な意味でのＥＸ状態は、米国特
許第４、３９４、７３１号に記載されているように、ラ
インがキャッシュに記憶されなかったときでさえ、記憶
制御エレメント（ＳＣＥ）と対話することなく、プロセ
ッサがキャッシュに記憶を行わせることを可能とする。
これは、細かな相違ではあるが、例えばＩＢＭ／３０８
１システムにおいて、次の記憶が来そうなときにプロセ
ッサでラインのＥＸ状態を得ることを可能にするので、
概念的な観点からはかなり重要なことである。

【０００７】従来技術によるＭＰシステムには、種々の
タイプのキャッシュがある。一つのタイプのキャッシュ
は、米国特許第４、１４２、２３４号に記載されている
ようなストアスルー（ＳＴ）キャッシュである。ＳＴキ
ャッシュの設計は、主記憶装置に対するデータの変更を
いつも最新のものとするために、主記憶装置（または第
２レベルキャッシュ）にデータを直接記憶するＣＰと抵
触するものではない。主記憶装置に対するストアスルー
の更新時には、適当な相互照会（ＸＩ）アクションが起
きて、記憶されたキャッシュラインの可能な遠隔コピー
を無効化する。記憶制御エレメント（ＳＣＥ）は、適当
なストアスタックを維持して主記憶装置（ＭＳ）の記憶
要求をキューし、バッファ制御エレメント（ＢＣＥ）と
ＳＣＥとの間の標準的な通信は、記憶スタックオーバー
フロー条件を避けるであろう。ＳＣＥの記憶スタックが
一杯になったときには、関連するＢＣＥは、条件がクリ
アされるまでそのＭＳ記憶を保持する。

【０００８】他のタイプのキャッシュの設計は、例えば
米国特許第３、７３５、３６０号及び第４、７７１、１
３７号に記載されているようなストアイン（ＳＩ）キャ
ッシュである。ＳＩキャッシュディレクトリは、上述の
米国特許第４、３９４、７３１号に詳細に述べられてい
る。そこでは、ストアインキャッシュにおける各ライン
が排他／読み出し専用（ＥＸ／ＲＯ）フラグビットによ
りマルチプロセッサの共用可能性を制御される。ＳＴ及
びＳＩキャッシュの間の主な相違は、後者の全ての記憶
はキャッシュそれ自身に向かって行われることである
（このため、記憶されたラインがＳＩキャッシュに存在
しなければキャッシュミスを生じる）。米国特許第４、
５０３、４９７号においては、コピーが遠隔キャッシュ
にあるならば、ミスフェッチが生じたときのデータ転送
がキャッシュ間転送（ＣＴＣ）によって起こり得ること
も提案されている。ＳＣＥとしては、各キャッシュのデ
ィレクトリのコピーを含むものが用いられる。これによ
って、相互照会（ＸＩ）決定をＳＣＥにおいて解決する
ことができる。通常、キャッシュラインの変更は、ライ
ンがキャッシュから置き換えられるときにだけ、主記憶
装置に対して更新される。

【０００９】

【発明が解決しようとする課題】従来の相互照会（Ｘ
Ｉ）方法においては、ブロックＢがＣＰ Ｐ_i に対して
排他状態（ＥＸ）にロックされたとき、遠隔キャッシュ
においてブロックＢによりカバーされるどのような第１
レベルのラインも無効化される。ブロックのサイズが第
１レベルのラインのサイズよりも大きいときには、しば
しば冗長相互照会（ＸＩ）が生じる。すなわち、ライン
は、他のＣＰにおいて変更されることなく無効化され
る。付加的なキャッシュミスやディレクトリの処理によ
るオーバーヘッドは、ブロックのサイズがラインのサイ
ズよりもずっと（例えば、１６倍）大きいときには許容
し難いものとなる。

【００１０】実験より、フェッチとストアとの両方に対
して著しい空間的局所性が観測された。より大きな細分
単位のブロックでＥＸロックを行うことにより、非排他
的ストアの割合を著しく減少させることができる。その
結果、上述の性能のオーバーヘッドを生じることなく、
大きな細分単位でＥＸロックを行うことができることは
重要である。特願平２−３７５３３号においては、大き
な細分単位の排他的ロックにより実現される性能の向上
について詳細に述べられている。この発明は、マルチプ
ロセッサシステムにおけるキャッシュ管理の性能をより
向上させるためにその環境の上になされたものである。

【００１１】従って、この発明の目的は、大きな細分単
位の排他的ロックを用いるストアスルー環境において、
排他性が解除されたときに、単一の伝送によって全ての
変更されたラインに対して相互無効化を行うことにあ
る。

【００１２】この発明の他の目的は、大きな細分単位で
排他性が許可され、あるプロセッサがページを排他的に
保持する間にラインの遠隔コピーをそのまま（ただしア
クセスはできない）にすることができ、これによって変
更されないページを有するラインに対する将来のミスを
避けることができるキャッシュ管理システムを提供する
ことにある。

【００１３】この発明の更に他の目的は、ラインの遠隔
コピーをそのままにすることができるが、プロセッサが
ページを排他的に保持する間はアクセスが可能でなく、
排他性が解除されたときに、一組の局所変更ビットが全
てのプロセッサに伝送されて変更されたラインを無効化
し、遠隔プロセッサにおけるページの状態が、この遠隔
プロセッサにおけるページの前の状態がどのようなもの
であるかに応じて読み出し専用または排他に変更される
キャッシュ管理システムを提供することにある。

【００１４】

【課題を解決するための手段】この発明によれば、時に
は変換索引バッファ（ＴＬＢ）と呼ばれるディレクトリ
索引テーブル（ＤＬＡＴ）と共に動作するダイナミック
テーブルが、同時に排他的に保持することができるペー
ジの数を決定する。すなわち、このテーブルに有効なエ
ントリがあると、それは、対応するページが排他状態に
あることを示す。このテーブルのエントリは、実ページ
アドレスと、「有効エントリ」ビットと、一組の「局所
変更」ビット（ＬＣＢ）とを含む。適切な動作速度のた
め、この特別なテーブルは、フルアソシアティブまたは
少なくともセットアソシアティブでなければならない。
このダイナミックテーブルは、ＤＬＡＴに取り込むこと
もできる。

【００１５】この発明は、排他性が許容されるときのミ
スの減少及びＸＩの複雑性の減少という付加的な利点を
与える、遠隔ＤＬＡＴにおける「有効不在」状態に基づ
くものである。より詳細には、各ＤＬＡＴエントリもま
た、一組の「存在」ビットと「有効不在」ビットとを含
むように拡張される。排他性はページ単位で許可され
る。最初は全てのＬＣＢはオフされる。キャッシュにお
けるラインの存在は、ＤＬＡＴにおける対応する存在ビ
ットとキャッシュディレクトリにおける有効ビットとの
結合（例えば論理積）により示される。排他状態でのラ
インへの記憶により、対応する局所変更ビットがセット
される。排他性が解除されるとき、局所変更ビットの組
は全てのプロセッサに伝送される。そのような伝送を受
けたとき、適切なアクションは、「有効不在」標識を読
み出し専用に変更すること及び対応する局所変更ビット
がセットされている存在ビットをクリアすることであ
る。もし経歴ビットが付加されてページの前の状態（例
えば、読み出し専用または排他）を記録するならば、そ
のページは、排他性が解除されたときに遠隔プロセッサ
における前の状態を回復することができる。

【００１６】この発明は、この発明が仮想キャッシュに
おいて実現される好ましい実施例によって説明される。
しかし、当業者ならば、この発明がどのような実キャッ
シュインプリメンテーションにも直接容易に適用可能で
あることを理解することができるであろう。

【００１７】

【実施例】以下、図面、特に図１を参照すると、図１に
は、この発明を使用できるタイプの密結合マルチプロセ
ッサ（ＭＰ）システムのブロック図が示される。このＭ
Ｐシステムは、４個の中央処理装置（ＣＰ０、ＣＰ１、
ＣＰ２、ＣＰ３）１０、１１、１２および１３を含み、
各々が命令実行（ＩＥ）ユニット１４、１５、１６およ
び１７と、バッフア制御ユニット（ＢＣＥ）２０、２
１、２２および２３とをそれぞれ含む。各ＩＥユニット
は、主記憶装置（ＭＳ）５０中のオペランドのフェッチ
と記憶とを要求する命令を出すハードウエアとマイクロ
コードを有している。

【００１８】ＩＥユニット１４〜１７は、それらの各キ
ャッシュ制御ユニット２０〜２３に対して、フェッチ或
いは格納のコマンドを出すことにより、フェッチ或いは
記憶の動作を開始する。キャッシュ制御ユニットは、関
連するプロセッサキャッシュディレクトリ（ＰＤ）を有
するプロセッサストアスルー（ＳＴ）キャッシュと、関
連するＣＰ１０〜１３により排他的に使用される全ての
プロセッサキャッシュ制御を含む。ＣＰは、通常、オペ
ランドにより要求される各ダブルワード（ＤＷ）ユニッ
トのフェッチ或いは記憶のコマンドを出す。若し、ＤＷ
を含むキャッシュラインがＰＤ中にあれば、これは、キ
ャッシュヒットであり、このＤＷがコマンドに従ってキ
ャッシュにおいてフェッチ或いは記憶される。キャッシ
ュにおけるオペランドのフェッチヒットにより、ＢＣＥ
だけで記憶装置のアクセスが完了する。要求されたＤＷ
がキャッシュ内に無いと、キャッシュミスとなる。ＩＥ
のフェッチ或いは記憶コマンドが終了する以前に、ＤＷ
は、主記憶装置からフェッチされねばならない。これを
行うのに、ＢＣＥは、対応するフェッチ或いは記憶ミス
コマンドを発生する。このミスコマンドは、記憶制御エ
レメント（ＳＣＥ）３０がＩＥユニットで要求されたＤ
Ｗを持つデータユニットを主記憶装置５０から得ること
を要求する。このデータユニット（例えば１ページ）は
主記憶装置５０でユニット境界上に位置する。しかしな
がら、要求されたＤＷは、ミスした転送の完了前に、Ｉ
Ｅの要求に応答するために、要求元のＢＣＥへ最初に戻
される。

【００１９】ＳＣＥ３０は、ＣＰ１０〜１３と主記憶装
置５０とに接続される。主記憶装置５０は、複数の基本
記憶モジュール（ＢＳＭ）コントローラＢＳＣ０、ＢＳ
Ｃ１、ＢＳＣ２およびＢＳＣ３（それぞれ、５１、５
２、５３および５４）を含み、ここでは、各基本記憶モ
ジュールコントローラが２個のＢＳＭ、すなわちＢＳＭ
０（６０、６２、６４および６６）とＢＳＭ１（６１、
６３、６５および６７）に接続される。４個のＢＳＣ５
１〜５４がそれぞれＳＣＥ３０に接続される。

【００２０】従来のシステムでは、ＳＣＥ３０が４個の
コピーディレクトリ（ＣＤ）３１、３２、３３および３
４を含み、米国特許第４，３９４，７３１号明細書に記
載のものと同様にして、ＢＣＥの一つの中にある対応す
るプロセッサキャッシュディレクトリ（ＰＤ）の内容の
イメージを各ＣＤが有している。前述の特願平２−３７
５３３号明細書に記載されているように、ライン存在情
報を記録する他のディレクトリを介するＸＩ無効化の量
をより低減することが可能であるが、必ずしもＣＤを採
用しなくて良い。

【００２１】ダブルワード幅の双方向データバスが主記
憶装置の各ＢＳＭ６０〜６７と対応するＳＣＥポートと
の間、ＳＣＥポートとＩ／Ｏチャンネルプロセッサ４０
との間、およびＳＣＥポートと各ＣＰ１０〜１３との間
に設けられている。これらのデータバスと共に、コント
ロールおよびアドレス信号用のコマンドバスのセットが
分離して設けられる。ＣＰでＤＷアクセス要求に関して
キャッシュミスが生じると、そのＢＣＥがＳＣＥ３０に
ミスコマンドを送ることにより主記憶装置に対するライ
ンアクセス要求を開始し、そして、ＳＣＥ３０が主記憶
装置の要求されたＢＳＭに対するコマンドを再発行す
る。ＢＳＭがビジー状態の場合には、ＳＣＥ３０がコマ
ンド待ち行列中に要求をセーブし、そのＢＳＭが後で使
用可能になる時にそれを再発行する。また、ＳＣＥ３０
は、主記憶装置コマンドを規則的に順番に並べ、従っ
て、そのＸＩロジックによりキャッシュの衝突が検出さ
れた時を除いて、特定のＢＳＭに対する全てのコマンド
が先入れ先出し（ＦＩＦＯ）の順で出される。主記憶装
置要求を扱う通常のシーケンスの間、ＳＣＥ３０が主記
憶装置の状態を絶えずモニタし、保護キーとの照会結
果、および全てのキャッシュディレクトリを分析し、現
にＳＣＥ３０に保持されている保留中の全てのコマンド
の更新された状態を試験し、また、ＳＣＥ３０で受信さ
れるためにＢＣＥ２０〜２３で待機している新たなＢＣ
Ｅコマンドを捜す。

【００２２】ＳＣＥ３０は、複数のストアスタック（Ｓ
Ｓ０、ＳＳ１、ＳＳ２およびＳＳ３）３５、３６、３７
および３８を保持する。これらは、対応するＣＰのため
に、１６個のダブルワードまでの主記憶装置記憶要求を
保持するためのものである。ＳＣＥ３０は、主記憶装置
アドレスおよび有効性を示すための、ストアスタックに
とって充分なディレクトリ情報を保持する。ストアスタ
ックがオーバーフローするおそれがある時には、ＳＣＥ
３０が関連するＢＣＥ２０〜２３に優先要求を送り、ス
トアスタックが一杯の状態をクリアする信号をあとでＳ
ＣＥ３０からＢＣＥが受け取るまで、それ以上の記憶要
求の送出がホールドされる。ストアスタックのデータは
各ストアスタックへの入力順序を維持しながら適切なス
ケジュールでもって主記憶装置において更新される。ス
トアスタックにある全てのライン記憶要求が関連するＢ
ＳＭ６０〜６７へ送られたことをＳＣＥが確信するま
で、ＣＰからのラインフェッチ要求はＳＣＥ３０により
ホールドされる。

【００２３】キャッシュディレクトリのエントリにＥＸ
状態を記録する従来の方法は、頗る無駄が多い。例えば
３２Ｋのエントリを持つ第２レベルのキャッシュを考え
る。若し、ＳＣＥがＥＸ状態のために第２レベルエント
リ毎に３ビットを保持するならば、１００Ｋビットに加
えて第１レベルのディレクトリでの同様なビットが必要
である。先の特願平２−３７５３３号明細書でより詳細
に開示されているように、比較的小さなロックテーブル
を使用することによりそのような回路コストを低減する
ことが可能である。各プロセッサＰｉ（１≦ｉ≦ｎ）に
関して、ＳＣＥはロックテーブルを保持する。ロックテ
ーブルは、通常、アドレスを介して索引付け（或いはハ
ッシュ）されたセットアソシアティブテーブルとして構
成される。或いはこれは単純な先入れ先出し（ＦＩＦ
Ｏ）スタックとして実現可能である。ロックテーブルの
各エントリに関して、ブロックＢのアドレスを記録する
ＩＤフィールド（適切な有効タグが付加されている）が
ある。また、ＳＣＥはロックテーブルの置換動作のため
に必要な状態アレイを保持する。ロックテーブルの各エ
ントリが対応するプロセッサのブロックのＥＸロックを
表す。初期的には、ロックテーブル中の全てのエントリ
が無効である。ブロックの大きさｂは、第１レベル或い
は第２レベルのキャッシュのラインの大きさと同一であ
る必要はない。通常は、これは、第１レベルのキャッシ
ュのラインの大きさの整数倍である。

【００２４】典型的なＳＴキャッシュのためのＳＣＥに
おける記憶同期機構を考える。ここでは、ＣＰからの各
記憶がＳＣＥと同期している必要がある。ＳＣＥにおけ
る基本的な動作は、以下のものである。最初にプロセッ
サＰｉからの記憶同期要求（ブロックＢについて）をＳ
ＣＥにより取り扱うことを考える。

【００２５】（ａ．１）ブロックＢがロックテーブルＴ
ｉでヒットする時は、その記憶同期が対応するプロセッ
サＰｉに直ちに許可される。

【００２６】（ａ．２）ブロックＢがどのロックテーブ
ルにもない時には、ＳＣＥは、ロックテーブルＴｉ中に
Ｂのための新たなエントリを作成し、プロセッサＰｉに
記憶同期を許可する。上述の処理と並行して、ＳＣＥ
は、遠隔キャッシュ中のＢをＸＩ−無効化するために信
号を（データブロックＢを含んでいるかも知れないＣＰ
へ）送る。

【００２７】（ａ．３）ブロックＢがロックテーブルＴ
ｊ（ｊ≠ｉ）にヒットする時は、ＳＣＥにおける遠隔Ｅ
Ｘヒットと同様である。この場合、新たなエントリがロ
ックテーブルＴｉで作成されると共に、ブロックＢのエ
ントリがロックテーブルＴｊから削除される（ＸＩ−無
効化信号がプロセッサＰｊへ送られる）。

【００２８】次に、ＳＣＥがプロセッサＰｉからブロッ
クＢ中のラインに関して、フェッチ要求を受け取る時
（例えば第１レベルのキャッシュのミス）の動作を考え
る。

【００２９】（ａ．４）ブロックＢが遠隔ＣＰによりＥ
Ｘロックされていない時は、このフェッチを遅延なく開
始できる。

【００３０】（ａ．５）ブロックＢがロックテーブルＴ
ｊにヒットする時（ここでｊ≠ｉ）、ブロックＢのエン
トリが最初にロックテーブルＴｊから無効とされる。

【００３１】ストアスルーキャッシュ設計では、ストア
スタックに保留中のライン記憶要求がない状態で、ライ
ン（ミス）フェッチが実行されうることが重要である。
ＳＣＥによるこの種の検査は、ラインフェッチの要求が
受信される時に必要とされる。

【００３２】上述のステップにおいて、（ａ．１）は、
異なるＣＰからの複数の記憶に関して並列になされるこ
とができる。同一のサイクルで一以上の記憶同期要求を
実行する可能性を排除するものではないが、適当な直列
化が他のステップが実行される時にＳＣＥにおいて必要
かもしれない。ロックの細分単位ｂがより大きくなると
（例えば４Ｋ）、ステップ（ａ．２）および（ａ．３）
からのＸＩ無効化が厳しい第１レベルキャッシュミスを
引き起こすであろう。

【００３３】ストアスルーキャッシュは、排他制御を持
つ必要がない。ストアスルーキャッシュには３つの基本
的な方式がある。すなわち、ＷＴＷＡＸ（「排他管理の
ライトスルー、ライトアロケート」）、ＷＴＷＡ（「ラ
イトスルー、ライトアロケート」（排他管理でな
い））、並びにＷＴＮＷＡ（「ライトスルー、ノーライ
トアロケート」（排他管理でない））がある。

【００３４】どの点から見ても、ＷＴＷＡＸキャッシュ
動作は、ストアインキャッシュと頗る類似しているが、
記憶動作は主記憶装置へのストアスルーであり、従っ
て、キャッシュからの書戻し（キャストアウト）がない
点で相違している。各記憶要求は独立した事象として主
記憶装置に出されるので、ＳＣＥは、所与のプロセッサ
からの記憶要求をそれらが出された順序で処理する必要
がある（異なるプロセッサからの記憶要求の順序付けは
不要）。なお、ストアインキャッシュでは、個々の記憶
の間の順序付けが本質的にキャストアウトで扱われるの
で、ＳＣＥはこれに関与する必要がない。

【００３５】ＷＴＷＡキャッシュは、排他管理がない点
を除けば、ＷＴＷＡＸキャッシュのように動作する。Ｗ
ＴＮＷＡキャッシュは、ＷＴＷＡキャッシュと同じく、
排他管理を有しない。そのような管理がないので、プロ
セッサは、キャッシュ間の同一性を確立するために、よ
り厳しい規則に従わねばならない。この発明は、排他的
に管理されるストアスルー環境で実現され、従って、こ
の記述の目的のために、ＷＴＷＡＸキャッシュが想定さ
れている。

【００３６】この発明の理解のために、最近のコンピュ
ータシステムにおける仮想アドレスから実アドレスへの
変換の処理を述べる必要がある。図２に示すように、Ｉ
ＢＭ３０９０シリーズのコンピュータで使用されている
ような３１ビットのアドレスバッフア６０が１９ビット
の仮想アドレスと１２ビットの変位に分割される。この
変位は、ページ中の所望バイトのアドレスである。上位
の１９ビットは、そのバイトの実アドレスを得るために
変換されねばならない。これは、ディレクトリ索引テー
ブル（ＤＬＡＴ、変換検索バッフア（ＴＬＢ）ともい
う）６１により遂行される。ＤＬＡＴは、最新のページ
変換を有するキャッシュ内のキャッシュである。ＤＬＡ
Ｔでエントリが発見されると、その出力が実ページアド
レス（ＲＰＡ）である。これは、レジスタ６２でアドレ
スバッフア６０からの下位の１２ビットと結合され、実
アドレスを形成する。

【００３７】ＤＬＡＴは、実ページアドレスに加えて、
有効ビット、記憶ＩＤ（ＳＴＯ ＩＤ）およびアドレス
タグ（仮想アドレスの一部）を含む。有効ビット、ＳＴ
ＯＩＤおよびアドレスタグは、全てヒットを認識するの
に必要である。ＤＬＡＴのエントリがセットアソシアテ
ィブであるため、アドレスタグが必要とされる。また、
ＤＬＡＴでエントリと共に貯えられる他のオプションの
記憶キーがあっても良い。

【００３８】若し、ＤＬＡＴにエントリがないならば、
仮想アドレスが変換されねばならない。これは、図３に
示すアーキテクチャでなされる。仮想アドレスがバッフ
ア６５に一時的に記憶される。仮想アドレスがセグメン
ト部とページ部とに分割される。セグメントテーブル起
点レジスタ（ＳＴＯＲ）６６がセグメントテーブル起点
を含む。レジスタ６６の出力がレジスタ６７の仮想アド
レスのセグメントデータと結合され、セグメントテーブ
ルアドレスが生成される。セグメントテーブルアドレス
がセグメントテーブル７０のページテーブル起点を参照
するのに使用される。ページテーブル起点がページアド
レスを生成するために、レジスタ７１で仮想アドレスの
ページデータと結合される。このページアドレスは、ペ
ージフレーム番号を参照するのに使用され、ページフレ
ーム番号或いは実ページアドレス（ＲＰＡ）が実アドレ
スを生成するために、レジスタ７３でレジスタ６５から
の変位と結合される。更に、ページテーブル７２からの
ＲＰＡがＬＲＵアルゴリズムを使用してＤＬＡＴ６１へ
加えられる。

【００３９】図４がＤＬＡＴ６１の他にディレクトリ７
５およびアレイ７６を含むようなキャッシュのアーキテ
クチャを示す。各ディレクトリエントリがアレイの１ラ
インに対応する。ディレクトリエントリは、有効ビット
と、ヒットの認識に関連するＥＸ／ＲＯビットおよびタ
グと、アレイセットＩＤとを含む。アレイセットＩＤ
は、アレイ７６でデータが格納される場所を識別する。
各ＤＬＡＴエントリは、１ページと対応する。ＩＢＭ３
０９０シリーズのコンピュータの例では、ページ当り３
２ラインあり、１ラインが１２８ビットである。アドレ
スバッフア６０からの仮想アドレスがＤＬＡＴ６１、デ
ィレクトリ７５およびキャッシュアレイ７６の各々をア
ドレスする。アレイ７６は、また、アドレスバッフア６
０からの下位の変位ビットでアドレスされる。ディレク
トリ７５は、セットアソシアティブであるので、数個の
ＲＰＡキャッシュプレースメント候補を提供する。４個
のかかる候補が図示されているが、個数は、特定のアプ
リケーションに依存して変化しうる。ＤＬＡＴ６１から
のＲＰＡが比較回路７７で各候補と比較され、また、比
較回路７７からのキャッシュプレースメント出力がアレ
イ７６からの正しい出力を選択するのに使用される。

【００４０】ここまで述べたアーキテクチャおよび動作
が従来のものであることは、当業者が分かるであろう。
しかし、この発明を理解するためには、背景としてこの
アーキテクチャを理解することが必要である。仮想アド
レス変換のより詳細は、"AnIntroduction to Operating
Systems", Harvey M. Deitel著，Addison-Wesley(198
4)、並びに "Operating Systems", Harold Lorinおよび
M. Deitel著, Addison-Wesley(1981)を参照されたい。

【００４１】この発明に特有の改良は、各ＤＬＡＴエン
トリと共に、ライン対応の３２個の存在ビットページの
「不在」を示すビットおよびライン対応の３２個の局所
変更ビット（ＬＣＢ）が含まれていることである。「不
在」ビットは、ページ全体の３２個の存在ビットを無効
にする。このビットを「有効不在」ビットと称する。こ
の結果、アクセスはできないが、ラインをキャッシュに
保持することができる。このビットは単一ビットでもよ
いが、以下の説明では、複数の状態ビットの特定の組み
合わせによって「有効不在」状態が示される。

【００４２】図５は、有効ビット（Ｖ）、タグ（仮想ア
ドレスの一部）および実ページアドレス（ＲＰＡ）から
なる旧い形のＤＬＡＴエントリ８０の一例を示す。この
発明の一態様として、図６に示すように、ＤＬＡＴエン
トリ８１は、タグおよびＲＰＡに加えて、状態ビット
（ＳＴ）、存在ビット（ＲＢ）および局所変更ビット
（ＬＣＢ）を持つように、変形される。他の態様として
は、図７に示すように、ＤＬＡＴエントリ８２は、状態
ビット、タグ、ＲＰＡおよびＲＢだけを有し、より小さ
なテーブルが有効ビット（Ｖ）、ＲＰＡおよびＬＣＢか
らなるエントリ８３を含む。図６および図７に示される
二つの態様は、全く等価である。後者は、やや複雑であ
るが、必要なメモリの合計が低減される利点がある。

【００４３】この発明によれば、キャッシュの動作は、
下記の例外を除けば、普通で言うＷＴＷＡＸである。す
なわち、 １．所与のプロセッサにおいて排他性がページベースで
許可されるとともに、上述したテーブルへの関連情報の
挿入により排他性が示される。これは、前述の特願平２
−３７５３３号明細書に記載のような、大きな細分単位
のロックの一形式である。最初は、全ての局所変更ビッ
トは、オフにされる。他のプロセッサのＤＬＡＴ中で
は、排他ページに対応するエントリにおいて「有効不
在」状態がセットされる。

【００４４】２．ラインの存在は、ＤＬＡＴエントリ中
の対応する存在ビットとキャッシュディレクトリ中の有
効ビットとの結合（例えば論理積）で示される。

【００４５】３．排他状態でのラインへの記憶により対
応する局所変更ビットがセットされる。

【００４６】４．排他性が解除される時（ＣＥＲＯ（排
他を読み出し専用へ変更）或いは上述のテーブルのエン
トリのエージングのいずれかにより）には、局所変更ビ
ットの組が全てのプロセッサに同報通信される。この同
報通信が受信されたときの適切な動作は、「有効不在」
標識を読み出し専用へ変更し、セットされていた局所変
更ビットに対応する存在ビットをクリアすることであ
る。（存在ビットは、要求元のプロセッサではクリアさ
れる必要がない。）

【００４７】このプロセスが図８に示される。図８は、
プロセッサＰ１のＤＬＡＴエントリ８５とプロセッサＰ
２の対応するＤＬＡＴエントリ８６とを示す。プロセッ
サＰ１がページを排他的に保持し、そして、排他状態を
解除したとすると、ＤＬＡＴエントリ８５からのＬＣＢ
の単一の同報通信は、プロセッサＰ１により書かれた全
てのラインに対応するＤＬＡＴエントリ８６中の存在ビ
ット（ＲＢ）をリセットすることにより、それらのライ
ンを無効にする。プロセッサＰ１による排他状態の解除
は、Ｐ１でのエージングの結果、又はプロセッサＰ２か
らの相互照会（ＸＩ）またはＣＥＲＯの結果である。排
他状態または読み出し専用の状態がプロセッサＰ２に許
可されると、状態ビットが有効不在（ＶＮ）から場合に
応じてＥＸまたはＲＯへ変わる。プロセッサＰ１のＤＬ
ＡＴエントリ中の対応する状態ビットがＶＮ又はＲＯに
変わる。

【００４８】一般的な場合では、状態ビットＳＴは、下
記のページ状態をエンコードする２ビットからなる。 ００−無効 ０１−有効不在 １０−読み出し専用 １１−排他 若し、エージングのために、あるプロセッサにより排他
状態が解除され、且つ他のプロセッサが以前にそのペー
ジを排他または読み出し専用に保持していたならば、排
他性の解除の時の適切な動作は、後者のプロセッサにお
いて有効不在状態を読み出し専用の状態へセットするこ
とである。しかしながら、若し、他のプロセッサが以前
にページを排他に保持していたならば、読み出し専用よ
りも、むしろ、状態が排他に戻されるようなアプリケー
ションがありうる。このために、「経歴」ビットと称さ
れるもう１つのビットが必要である。このビットは、ペ
ージが排他に保持されるならば、“１”にセットされ
る。その結果、排他性が解除される時に、“１”の経歴
ビットによって有効不在状態を読み出し専用でなくて、
排他に変化する。

【００４９】

【発明の効果】この発明による利点は、二つある。第１
に、ページ内で変更されている全てのラインを無効にす
るのに単一の伝送で十分である。第２に、「有効不在」
状態により、あるプロセッサがページを排他に保持して
いる間に、ラインの遠隔コピーを存在のままにしておく
ことができる。従って、ページ内の変更されていないラ
インに関して将来のミスが避けられる。

【図面の簡単な説明】

【図１】この発明を使用できるマルチプロセッシングシ
ステムのブロック図である。

【図２】ＤＬＡＴアーキテクチャを示すとともに、キャ
ッシュアクセス経路を示すブロック図である。

【図３】セグメントおよびページテーブルアクセスを示
すとともに、仮想アドレスから実アドレスへの変換を示
すブロック図である。

【図４】ＤＬＡＴ、ディレクトリおよびアレイのアーキ
テクチャを示すともに、アレイ中の所望のワードをアク
セスする方法を示すブロック図である。

【図５】従来技術のＤＬＡＴエントリのブロック表現の
図である。

【図６】この発明によるＤＬＡＴエントリのブロック表
現の図である。

【図７】この発明の他の例のＤＬＡＴエントリおよびテ
ーブルエントリのブロック表現の図である。

【図８】排他性の解除の時のこの発明の動作を示すブロ
ック図である。

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

Claims (1)

【特許請求の範囲】
1. 【請求項１】複数のプロセッサおよび主記憶装置を含む
   マルチプロセッサシステムのストアスルーキャッシュ管
   理システムであって、前記複数のプロセッサのそれぞれ
   が、ストアスルーキャッシュと、該キャッシュをアクセ
   スするためのディレクトリと、仮想アドレスに応答して
   実ページアドレスを出力する索引テーブルとを含み、前
   記索引テーブルの各エントリが、前記実ページアドレス
   の他に、当該ページが読み出し専用であること、排他性
   であること、または存在はしているがアクセスできない
   有効不在の状態にあることを示す状態ビットと、当該ペ
   ージ内の個々のラインの存在を示す存在ビットと、排他
   状態の間に書き込みが行われたラインを示す局所変更ビ
   ット、及び、以前の状態が排他であったことを示す経歴
   ビットを含み、 （ａ）特定のページを排他状態にしていたプロセッサが
   その排他状態を解除する際に、前記索引テーブルの対応
   するエントリ中の前記局所変更ビットを他のプロセッサ
   に送って、該他のプロセッサの索引テーブルにおいて前
   記特定のページに対応するエントリ中の前記存在ビット
   を前記局所変更ビットに従って選択的に無効にし、 （ｂ）前記他のプロセッサの索引テーブルにおいて存在
   ビットが無効にされる時に、そのエントリの状態を読み
   出し専用に変更し、 （ｃ）前記存在ビットが無効にされる時に該経歴ビット
   がセットされている場合に、対応するエントリの状態を
   排他状態に変更する、 ことを特徴とするストアスルーキャッシュ管理システ
   ム。