JPH0628263A - データ・キャッシュのための制御器において最近に用いられたデータを更新する方法および装置 - Google Patents

Abstract

(57)【要約】 【目的】 ウエイごとに２つのセクタがあるようなデー
タ・キャッシュのための制御器内のＬＲＵポインタを更
新する方法と装置を得ることである。 【構成】 キャッシュ制御器ｔａｇｒａｍが２ウエイに
構成される。各ウエイはタグと、キャッシュ・アレイ・
アドレスのためのディレクトリを連想的にサーチするた
めの有効ビット記憶装置とを含む。右ウエイと左ウエイ
の２つの各ウエイがタグ・アドレスを記憶する。ウエイ
の１つに対するライン充填中に選択される２つのライン
がある。最初に用いられた（ＬＲＵ）ポインタが、ライ
ン充填サイクルでどのウエイを充填するかを選択する。
ＬＲＵポインタが右ウエイを指すならば、右ヒット信号
に応じてライン充填に対して右ウエイが選択される。右
ウエイの右ラインが充填された時に、ＬＲＵポインタは
左ウエイを指すためにフリップされる。ＬＲＵポインタ
が左ウエイを指すならば、左ヒット信号に応じてライン
充填のために左ウエイが選択される。左ウエイの左ライ
ンが充填された時に、ＬＲＵポインタは右ウエイを指す
ためにフリップされる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はデータ処理装置に関する
ものであり、更に詳しくいえば、データ・キャッシュの
ための制御器において最近に用いられた（ＬＲＵ）（ｌ
ｅａｓｔ ｒｅｃｅｎｔｌｙ ｕｓｅｄ）データ・ポイ
ンタを更新する方法および装置に関するものである。

【０００２】

【従来の技術】キャッシュは、大容量の、比較的低速の
主記憶装置（バッキング記憶装置）の頻繁にアクセスさ
れる記憶場所のためのローカル記憶装置（バッファ記憶
装置）を構成するために用いられる、比較的高速の小容
量ローカル記憶装置である。情報または情報の写をロー
カルに記憶することにより、キャッシュは、システム・
バスを介して主記憶装置へ要求を行うことなしに、メモ
リの参照を傍受して、それを直接取り扱うことができ
る。結果としてメモリ・バスのトラフィック量が減少
し、要求を行うプロセッサまでのＣＰＵバスにおける待
ち時間が短くなる。１９９０年１１月２８日付の米国特
許出願ＳＮ０７／６１８，７０８には、２つのウエイで
構成されるタグＲＡＭを有するキャッシュ制御器が開示
されている。各ウエイはタグと、キャッシュ・データ・
アレイ・アドレスのためのディレクトリを連想的にサー
チするための有効ビット記憶装置とを含む。システム内
のいくつかの利用可能なメモリ・モジュールに対して両
方のウエイを同時に利用できるように外部キャッシュ・
メモリを編成することにより、ウエイのアクセス時間を
タグのルックアップと並列に生ずることができるように
する。１９９１年４月１２日付の米国特許出願ＳＮ０７
／６８４，１８０には、前記米国特許出願ＳＮ０７／６
１８，７０８の制御器において複雑なタイミング・サイ
クルを管理する方法と手段が開示されている。

【０００３】バッファ／バッキング記憶装置の階層にお
いては、要求されているデータはより高速のバッファ記
憶装置には現在は存在しないことがあるから、データを
検索するためにはバッキング記憶装置に対してアクセス
せねばならない。新しいデータのためのスペースをバッ
ファ内に設ける必要があるから、バッファ内のある場所
におけるデータを新しいデータにより移動させねばなら
ない。そうすると新しいデータはバッファ内の選択され
た場所におけるデータに代わり、その場所を占めていた
データは移動させられる。これは今フェッチされたデー
タはおそらく再び必要とされるであろうという仮定によ
っている。どの場所を移動させるかの選択は、最近に、
すなわち最後に用いられた（ＭＲＵ）（ｍｏｓｔ ｒｅ
ｃｅｎｔｌｙ ｕｓｅｄ）データ、いいかえるとバッフ
ァに最後に加えられたデータ、はおそらく再び必要とさ
れるであろうから、保持せねばならないという仮定によ
ってなされる。これに反して、最初に用いられた（ＬＲ
Ｕ）データはおそらくもはや必要とされないので、バッ
ファから除去でき、もし再び必要になった時はバッキン
グ記憶装置からバックアップ・コピーをフェッチするこ
とができる。ＬＲＵポインタと呼ばれるポインタが、交
換されるために論理によって選択される次の場所を常に
指している。そのＬＲＵポインタがどのようにして選択
されるかはシステムの効率に大きく影響し、与えられた
時間内にバッキング記憶装置に対して行わねばならない
アクセスの回数を増加または減少する。

【０００４】従来のバッファ／バッキング記憶装置にお
いては、最初に用いられた（ＬＲＵ）ポインタは、最初
に用いられたバッファ内のデータを指す。そのデータは
バッキング記憶装置からの新しいデータで置き換えられ
るデータである。前記米国特許出願ＳＮ０７／６１８，
７０８に開示されている制御器においては、各ウエイご
とに２つのセクタがある。このことは、与えられたセッ
ト・アドレスに、行選択（ＬＳ）によりドライブされる
２つのラインのデータがあることを意味する。しかし、
１度に１つのラインだけ充たされる。したがって、１つ
のラインに有効なデータを置くことができるが、他のラ
インには有効なデータが置かれないことがある。有効な
データは１度に１つのラインだけに置くことができるか
ら、そのラインはＭＲＵデータを含み、ＬＲＵポインタ
はそのラインを指すべきではないことを従来のＬＲＵア
ルゴリズムは常に指定する。しかし、これは上記２セク
タ構造中のスペースを効率的に使用するものではない。

【０００５】

【発明が解決しようとする課題】したがって、本発明の
目的は、ウエイ毎に２つのセクタがあるデータ・キャッ
シュのための制御器におけるＬＲＵポインタを更新する
方法および装置を得ることである。

【０００６】

【課題を解決するための手段】この目的は、キャッシュ
・データ・アレイ・アドレスのためのディレクトリを連
想的にサーチするためのタグおよび有効ビット記憶装置
をおのおの含む２つのウエイへ構成されるキャッシュ制
御器タグラム（２４）を提供することにより達成され
る。右ウエイと左ウエイの２つのウエイはそれぞれタグ
・アドレスをおのおの記憶する。ウエイの一方に対する
行充填中に選択される２行がある。ＬＲＵポインタが右
ウエイを指すならば、右ヒット信号に応じて行充填のた
めに右ウエイが選択される。ＬＲＵポインタが左ウエイ
を指すならば、左ヒット信号に応じて行充填のために左
ウエイが選択される。ＬＲＵポインタは、左ウエイの左
行が充填された時に右ウエイを指すように向きを変えら
れる。本発明の１つの面によれば、ＬＲＵポインタは読
出しミス・サイクルおよび書込みヒット・サイクルのと
きにだけ更新され、読出しヒット・サイクルではそのま
まにされる。読出しヒットの時にＬＲＵポインタを更新
しないことにより、アルゴリズムは、バスのトラフィッ
クが主として書込みサイクルであるようなバッファ／バ
ッキング記憶装置を支持する、ということが本発明の利
点である。

【０００７】

【実施例】まず、米国特許出願ＳＮ０７／６１８，７０
８に記載されている２ウエイ、セット連想キャッシュの
ブロック図が示されている図１を参照する。ＲＬＳ論理
１０がｔａｇａｃｃ論理１４をドライブする。ｔａｇａ
ｃｃ論理１４は連想メモリ左タグＲＡＭ１６と左データ
・キャッシュ１８、および右タグＲＡＭ２０と右データ
・キャッシュ２２をドライブする。左タグＲＡＭ１６と
左データ・キャッシュ１８はウエイ０を構成し、右タグ
ＲＡＭ２０と右データ・キャッシュ２２はウエイ１を構
成する。

【０００８】図２に示すように、各タグＲＡＭすなわち
ウエイは３４個のタグ・ビット２書込み保護ビットと４
個の有効ビットを有する。また、左タグＲＡＭはＬＲＵ
ポインタを構成する２ＬＲＵビットを有する。左ヒット
論理２６と右ヒット論理２８は、タグ・サーチ引数１２
と連想メモリ内のタグ・アドレスが一致した時に、ｔａ
ｇｉｆｃインターフェイス制御論理３０へ出力を供給す
る比較回路である。ｔａｇｉｆｃ３０は、メモリ・アド
レス／データ・バス３４に置くべき情報を保持するＡＤ
Ｓラッチ３２をドライブする。制御論理２４は、書込み
可能化（ＷＥ０）、出力可能化（ＯＥ）、スタート等の
ような必要な制御機能を上記論理ブロックへ供給するた
めに、各論理ブロックへ接続される。

【０００９】従来は、ＬＲＵポインタは最も先に用いら
れて、置き換えるべきデータを指す。米国特許ＳＮ０７
／６１８，７０８に記載されている制御器においては、
各ウエイに２つのセクタがある。このことは、２つのデ
ータ行があることを意味する。１つの行は有効なデータ
を有することができ、別の行は有効なデータを有するこ
とができないことがある。有効なデータは１度に１つの
行だけに置くことができる。データが行に置かれると、
それは最後に用いられたデータであるから、ＬＲＵポイ
ンタはそれを指すべきではない。したがって、ｚＰＴＲ
ＤＡＴ行は逆の向きを指すようにＬＲＵの向きを変え
る。タグＲＡＭに対する任意のアクセスに対して、信号
ｚＷＡＹＳＥＬは左側または右側に対して行うべきかを
判定する。正常なサイクル中は、信号ｚＷＡＹＳＥＬ
は、充填のために行を選択すべき行充填においてのみ意
味を有する。図３に示されている情報に従って信号ｚＷ
ＡＹＳＥＬの値を決定するために、タグ・ヒット信号が
ＬＲＵビットとともに用いられる。

【００１０】読出しミス、書込みヒットおよびスヌープ
（ｓｎｏｏｐ）・ヒットの時にＬＲＵは更新される。ス
ヌープ・サイクルにおいて、左ウエイでヒットが生じた
とすると、ＬＲＵは左ウエイを指させられる。行充填で
はこれとは全く逆の事が行われる。行充填が左側に対し
てであるとすると、ＬＲＵは右側へ指すことを強制され
る。この理由は、定義により、ヒットが新しいデータを
入れるものとすると、最初に用いられたデータが反対側
にあるからである。現在の行を確認すべき時に、ＬＲＵ
ビットを他のウエイへ変えるべきである。これはＴＡＧ
ＩＦＣ３０において自動的に行われる。しかし、たとえ
ばＳＫＥＮ＃のピンポン操作のために行を無効にすべき
であるとすると、ＬＲＵビットを古いウエイへ指すよう
に元に戻される。信号ｒＬＲＵＦＬＰはＬＲＵビットを
フリップするためのデータを供給する。そのデータが零
であれば、タグ更新中はｚＰＴＲＤＡＴと同じウエイを
ＬＲＵは指すようにされる。そのデータが１であれば、
タグ更新中はＬＲＵは元の値へセットされる。

【００１１】ＲＬＳ１０からＴＡＧＡＣＣ１４への信号
ＷＲＬＲＵと、ｒＷＲＳＴＳと、ｒＷＲＴＡＧとは、タ
グＲＡＭを更新する時を決定するタグ書込み指令であ
る。状態書込み指令は下記の時刻に活動化する。 １．論理が委ねられた行充填サイクル中のＴＯ２１にあ
る。 ２．委ねられた行充填サイクル中のＴＯ２４に論理があ
り、行の状態を変えねばならない時。 ３．外部サイクルが終わったが、論理は早期の書込み要
求に対する確認応答を見なかった時。 ４．外部サイクルはまだ終わらず、早期の書込み要求に
対する確認応答を論理がいぜんとして待っている時。 ５．読出しサイクルが終わる前にＢＯＦＦ＃が起こり、
行が有効である時。 ６．サイクルが自己テスト書込みの時。 ７．論理が読出しヒット・サイクルにあり、ＢＯＦＦ＃
が起きた時。

【００１２】ＬＲＵビットは下記の状況において書込ま
ねばならない。 １．委ねられている行充填サイクルのＴＯ２４に論理が
あり、行の状態を変えねばならない時。 ２．外部サイクルが終わったが、早期の書込み要求に対
する確認応答を論理が見なかった時。 ３．外部サイクルはまだ終わらず、早期の書込み要求に
対する確認応答をいぜんとして待っている時。 ４．行が有効であるが、ＢＯＦＦ＃が起きた時。 論理は読出しヒットの時にＬＲＵビットを更新すること
もできる。

【００１３】状態ビットが書かれる時はタグ・ビットが
常に書かれる。書込み指令のための確認応答はＴＡＧＡ
ＣＣ１４から来る。そのＴＡＧＡＣＣ１４は、タグＲＡ
ＭがＲＬＳ１０から書込み指令を受ける状況にある時
に、信号ｚＳＴＳＡＣＴを発生する。書込み指令は、確
認応答が見られない限り、存続する。ＲＬＳ（ｒＷＲ
（ＳＴＳ，ＴＡＧ，ＬＲＵ））からの書込み要求をＳＡ
ＣＬＫにおけるタグ・アクセスへ変換できるならば、信
号ｚＳＴＳＡＣＫはそのＳＡＣＬＫにおいて発生され
る。タグＲＡＭそのクロックにおいてスヌープ・アクセ
スで使用中であるならば、信号ｚＳＴＳＡＣＫは発生さ
れない。

【００１４】キャッシュ・ディレクトリ ディレクトリ２４の機能は、キャッシュ・メモリの左デ
ータ・キャッシュ１８と右データ・キャッシュ２３に格
納されているデータに対応するアドレスを格納すること
である。ディレクトリは２つのウエイ（ＷＡＹ０，ＷＡ
Ｙ１）へ構成される。行は、キャッシュと主メモリの間
で転送されるデータの基本単位である。行は１６バイト
のデータで構成される。行は転送ブロックとしても知ら
れている。特定のアドレスに対応するデータをキャッシ
ュに格納するものとすれば、キャッシュはデータを供給
でき、したがって主記憶装置のアクセスを避けることが
できる。これは、左ウエイ（ＬＨ）または右ウエイ（Ｒ
Ｈ）からのキャッシュ・ヒットと呼ばれる。ヒットかミ
スかの判定は行ごとに決定される。アドレス・ブロック
はキャッシャ・アドレッシングの基本単位である。各ア
ドレス・ブロックは、データの２つの隣接するラインの
うちの１つのラインの物理的アドレスである。

【００１５】アドレス・ブロック内の各ラインに組み合
わされる有効なビットがある。キャッシュにラインが存
在するものとすると、有効なビットがターン・オンされ
る。キャッシュ・ディレクトリの左タグＲＡＭ１６と右
タグＲＡＭ２０に保持されているアドレス情報はタグと
呼ばれる。多くのアドレスは１つのアドレス・ブロック
へマップするから、アドレス・ブロックに現在組み合わ
されている正確なメモリ場所を識別するためにタグ情報
が用いられる。連想記憶装置内のアドレス・ブロックの
タグが、サーチ引数１２として連想記憶装置へ供給され
たバス・アドレスに一致し、希望のライン有効ビットが
オンの時にヒットが起こる。

【００１６】各ウエイ１６，２０はタグおよび有効なビ
ットのための記憶装置を提供する。比較回路においてバ
ス・アドレス１２とタグ・フィールドの間で、データが
キャッシュ・データ・アレイにあるかどうかを判定する
やり方で、多くの比較が同時に行われる。セットは各ウ
エイからの１つのアドレス・ブロックより成るアドレス
・ブロックのまとまりである。あるセット内の全てのア
ドレス・ブロックは、ＣＰＵバス・アドレスのセット部
分が、ＲＬＳ論理１０内のデコーダによりセット・アド
レス１２へ復号された時に、同時に選択される。

【００１７】ＣＰＵバスにおける書込みトランザクショ
ンが、キャッシュにない（キャッシュ・ミス）アドレス
を含むと、対応するデータをキャッシュに格納する試み
は行われない。しかし、ＣＰＵバスにおける書込みトラ
ンザクションが、キャッシュ内にある（キャッシュ・ヒ
ット）アドレスを含むと、ディレクトリは書通しポリシ
ーを用いる。このことは、キャッシュ・ヒットになる結
果をもたらすＣＰＵバス書込みが、主記憶装置はもちろ
ん、キャッシュへも書込まれる。これにより、主記憶装
置はキャッシュの全てのデータ場所の有効なコピーを常
に確実に保持するようにされる。

【００１８】機能についての説明 起こるサイクルには、４つの正常なサイクルとスヌープ
・サイクルの５種類のサイクルがある。 １．読出しミス（ライン充填） ２．読出しヒット ３．書込みミス ４．書込みヒット ５．スヌープ

【００１９】読出しミス（ライン充填） 読出しミス・サイクルはｚＡＤＳＣＹＣとｚＲＤＳＣＹ
Ｃでスタートする。タグ・ルックアップは最初のＳＨＣ
ＬＫでミスを生ずる。ＳＴＡＲＴ＃は活動状態になって
ミスを示す。それから、ＳＫＥＮ＃が活動状態になるま
で論理は待つ。最初の転送の前にＳＫＥＮ＃が活動状態
であると、ラインはコミットされているといわれる。図
３に示すように、タグＲＡＭ中のラインは信号ｚＡＤＳ
ＬＲＵ，ｚＡＤＳＨＬ，ｚＡＤＳＨＲを用いて選択され
る。ラインを無効にするためにタグ書込み指令が発せら
れる。また、対応する最初の書込み可能化が発せられ
る。

【００２０】活動状態にあるＳＫＥＮ＃は、ラインが既
に有効でなければ、ラインを有効にするためにタグＲＡ
Ｍに対する要求が行われる結果となる。ＳＫＥＮ＃が非
活動状態にあると、ラインが既に無効でなければ、ライ
ンを無効にするための要求が行われる結果となる。その
ような各書込みにおいて書込み防止ピン（ＷＰ）が書込
まれる。ラインが有効な状態に放置されるならば、ＬＲ
Ｕビットは他のウエイを指すようにされる。ラインが有
効であり、かつサイクルがＢＯＦＦ＃でサイクルが放棄
されると、ラインを無効にするためにタグＲＡＭに対し
て要求が行われる。

【００２１】読出しヒット 読出しヒット・サイクルはｚＡＤＳＣＹＣおよびｚＲＤ
ＳＣＹＣでスタートする。タグ・ルックアップは最初の
ＳＨＣＬＫにおいてヒットを生ずる。ＢＲＤＹＯ＃は活
動状態になってヒットを示す。また、最初の出力可能化
（ＯＥ１）が活動状態になる。最初の可能化は、米国特
許出願ＳＮ０７／６８４，１８０に記載されているバー
スト・アドレス・シーケンスを用いて、４つの可能性か
ら拾われる。キャッシュ制御器はあらゆるクロックにお
ける転送をＢＲＤＹＯ＃で合図するから、論理はあらゆ
るクロックにおいてＴＯ２２，ＴＯ２３，ＴＯ２４を通
って進む。各転送ごとに適切な可能化が生じさせられ
る。ＢＯＦＦ＃が転送に割り込むとすると、ラインを無
効にするためにタグＲＡＭに対して要求が行われる。読
み出しヒットではＬＲＵビットは更新されない。

【００２２】書込みミス 直接プロセッサ書込みサイクルはｚＡＤＳＣＹＣおよび
ｚＷＲＳＣＹＣでスタートする。ＳＴＡＲＴ＃は最初の
ＳＨＣＬＫにおいて終わる。最初のＳＨＬＣＫにおいて
それがヒットであれば、適切な可能化が送出される。ミ
スでは、ＬＲＵビットに対して何も行われず、ＳＴＡＲ
Ｔ＃だけを活動状態であると見ることができる。

【００２３】書込みヒット 直接プロセッサ書込みサイクルはｚＡＤＳＣＹＣおよび
ｚＷＲＳＣＹＣでスタートする。ＳＴＡＲＴ＃は最初の
ＳＨＣＬＫにおいて終わる。最初のＳＨＬＣＫにおいて
それがヒットであるとすると、適切な可能化が送出され
る。ＬＲＵビットは書込みヒットにおいて他のウエイを
指すようにされる。

【００２４】スヌープ マルチプロセッサ環境においては、同じメモリ空間を共
用する２つ以上のプロセッサが存在することがある。１
つのプロセッサのキャッシュにデータが記憶され、同じ
データに対して他のプロセッサが外部メモリへ進むと仮
定する。第２のプロセッサがデータを変えるとすると、
第１のプロセッサのキャッシュ内のデータはだめにされ
る。スヌープ信号があらゆるプロセッサへ送られ、各プ
ロセッサによりモニタされる。スヌープ信号により示さ
れているラインのアドレスにおけるデータの私用コピー
をどのプロセッサも有するとすると、それはそれのキャ
ッシュに入ってそのラインを無効にせねばならない。ス
ヌープ信号に関連するバスにはアドレスがある。したが
って、バスにアドレスがあり、スヌープ信号が高レベル
にされたとすると、プロセッサは入り、そのデータのロ
ーカル私用コピーを無効にせねばならない。スヌープ・
サイクルは独立に取り扱われ、正常サイクルと呼ばれる
他の４つのサイクルでスヌープ・サイクルをオーバーレ
イできる。スヌープ・ヒットはＬＲＵビットを選択され
たウエイを指すことを自動的に強制する。ウエイはｚＷ
ＡＹＳＥＬで選択される。

【００２５】信号についての説明 内部信号の詳細な説明が米国特許出願ＳＮ０７／６８
４，１８０において行われている。その米国特許出願に
おいては、各内部信号の名称がそれの属する信号源を識
別する特性文字で始まる、と記述されている。最初の文
字は｛ｒ，ｔ，ｘ，ｙ，ｚ｝のうちの１つにできる。信
号名の残りの部分は大文字である。「ｎｎ」で終わる信
号は、それが低い真の信号であることを意味する。外部
信号のための対応する記法は代わりに「＃」を有する。
また、中かっこ｛｝はかっこ内にサブストリングを含ん
でいる信号名を記述するために用いられる。たとえば、
ｒＷＲ｛ＳＴＳ，ＴＡＧ，ＬＲＵ｝はそれぞれｒＷＲＳ
ＴＳ，ｒＷＲＴＡＧ，ｒＷＲＬＲＵを表わす。サブスト
リングの長さが１文字であると、複数の文字をコンマで
分離することなしに一対のかっこが用いられる。たとえ
ば、［ｙｚ］ＡＤＳｎｎはｙＡＤＳｎｎとｚＡＤＳｎｎ
を意味する。かっこは範囲を示すためにも用いられる。
たとえば、ｚＳＡＩ｛０・・１０｝はｚＳＡＩ０、ｚＳ
ＡＩ１、・・・ｚＳＡＩ１０を表わす。そのような多ビ
ット信号を参照する場合には、範囲指定子が削除され
る。たとえば、１１個のｚＳＡＩ［０〜１０］信号をｚ
ＳＡＩと記す。

【００２６】ＴＡＧＩＦＣ３０論理は、サイクルを始め
る最初のＡＤＳ＃の後の最初のＳＨＣＬＫにおけるタグ
ＲＡＭの出力を捕らえる。捕らえられた出力はサイクル
が終わるまでＡＤＳラッチ３２に保持される。セット内
の他のラインのための有効な情報はＡＤＳラッチ３２か
ら得られる。それから両方のラインのための情報がタグ
ＲＡＭへ書込まれる。そのラインがサイクル中に明らか
なスヌープを介して、またはフラッシュを用いて無効に
された時に、ＲＬＳ１０からのｒＣＬＲＶ［ＬＲ］信号
（ｒＣＬＲＶＬとｒＣＬＲＶＲ）がこの「別の」ライン
情報をクリヤするために用いられる。

【００２７】信号ｔＨＬ，ｔＨＲ，ｔＲＬＵ，ｔＶＬ
０，ｔＶＬ１，ｔＶＲ０，ｔＶＲ１，ｔＬＷＰ，ｔＲＷ
Ｐは、現在のアクセスがヒットであるか、ミスであるか
を示すために、論理ＢＲＤＹＯ，ＭＵＸＣＯＮ，ＯＥ，
ＳＴＡＲＴ，ＴＡＧＩＦＣおよびＷＥを進ませるタグＲ
ＡＭからの出力である。ヒットの場合は、タグ・ビット
（ｔＨＬまたはｔＨＲ）と対応する有効なビット（ｔＶ
Ｌ［０１］またはｔＶＲ［０１］）を同時にヒットせね
ばならない。ｔＬＷＰとｔＲＷＰはそれぞれ左側と右側
からの書込み防止ビットである。ＯＥ回路と、ＷＥ回路
と、ＢＲＤＹＯ回路と、ＳＴＡＲＴ回路とは、ヒット・
サイクルかミス・サイクルであるかを判定するためにそ
れらの信号を直接用いる。スヌープ・サイクル中に、ス
ヌープがヒットであるかどうかを判定するために、ＭＵ
ＸＣＯＮはそれらを用いる。正常なサイクルの場合に
は、信号ｚＡＤＳ（ＨＬ，ＨＲ，ＶＬ０，ＶＬ１，ＶＲ
０，ＶＲ１）とｚＲＬＳ［ＬＲ］ＷＰを生ずるために、
ＴＡＧＩＦＣ３０はそれらの信号をＡＤＳラッチ３２に
捕らえる。スヌープ中は、それらの信号はスヌープ・ラ
ッチに捕らえられる。スヌープ・ラッチからの出力はＴ
ＡＧＩＦＣ３０にローカルなままである。

【００２８】ＴＡＧＩＦＣ３０から論理ＲＬＳとＷＡＹ
ＣＯＮへの信号ｚＡＤＳＬＲＵはｚＡＤＳＣＹＣの後の
最初のＳＨＣＬＫに捕らえられた信号ｔＬＲＵである。
サイクルが終わるまで値は保持される。ラッチは、ｚＡ
ＤＳＣＹＣとｚＡＤＳＣＳにより可能状態にされたＳＨ
ＣＬＫの終わりによりクロックされる。ＲＬＳにおいて
は、ｚＡＤＳＬＲＵによりクロックされ、それからｒＬ
ＲＵＦＬＰを生ずるために用いられる。ＷＡＹＣＯＮに
おいては、それはｚＷＥＳＥＬ，ｚＷＡＹＳＥＬ，ｚＩ
ＷＡＹＳＥＬを発生するために用いられる。

【００２９】ＴＡＧＩＦＣ３０からＲＬＳ，ＷＡＹＣＯ
Ｎ，ＴＡＧＡＣＣ１４論理への信号ｚＡＤＳＶ［ＬＲ］
［０１］とｚＡＤＳＨ［ＬＲ］は、ｚＡＤＳＣＹＣの後
の最初のＳＨＣＬＫに捕らえられた信号ｔＶ［ＬＲ］
［０１］とｔＨ［１ｒ］である。ラッチはｚＡＤＳＣＳ
とｚＡＤＳＣＹＣにより可能状態にされる。ローカル・
ヒット／ミス情報を生ずるためにＲＬＳ１０論理はそれ
らを用いる。ｚＷＥＳＥＬ，ｚＷＡＹＳＥＬ，ｚＩＷＡ
ＹＳＥＬを生ずるためにＷＡＹＣＯＮはｚＡＤＳＨＲを
用いる。ＴＡＧＡＣＣ１４においては、それらの信号は
直接プロセッサ書込みヒット・サイクル中にｚＷＲＬＲ
Ｕを発生する。

【００３０】ＴＡＧＩＦＣ３０からＴＡＧＲＡＭへの信
号ｚＰＴＲＤＡＴはタグＲＡＭへ書込まれるＬＲＵビッ
トである。正常なサイクル中の全てのタグＲＡＭの更新
においては、ｚＰＴＲＤＡＴはｚＡＤＳＬＲＵの逆であ
る。しかし、ｒＬＲＵＦＬＰが活動状態にあると、ｚＰ
ＴＲＤＡＴはｚＡＤＳＬＲＵと同じ値をとる。スヌープ
・ヒット中は、スヌープの無効化が行われる場合とは逆
のウエイへｚＰＴＲＤＡＴはセットされる。ＷＡＹＣＯ
Ｎ論理からＴＡＧＩＦＣ３０論理へのｚＰＴＲＤＶＲに
よりスヌープ中にＬＲＵポインタのオーバライドが許さ
れる。活動状態にあると、それは、スヌープの無効化が
行われるウエイとは逆のウエイをＬＲＵに指させる。そ
れはＳＡＣＬＫラッチにより捕らえられるｚＳＮＰＷＡ
ＩＴである。ＴＡＧＩＦＣ３０論理からＷＡＹＣＯＮ論
理へのｚＳＮＰＨＲ信号は、ｚＳＮＰＣＹＣの後の最初
のＳＨＣＬＫに捕らえられたタグＲＡＭの右側からのタ
グ・ヒット信号である。ｚＷＮＰＷＡＩＴとともに、そ
れはスヌープ無効化のためのウエイを選択する。

【００３１】ＴＡＧＩＦＣ３０論理からＴＡＧＲＡＭへ
の信号ｚＶＬ０，ｚＶＬ１，ｚＶＲ０，ｚＶＲ１は、あ
らゆる書込み要求においてタグＲＡＭへ書込まれる状態
ビットである。書込み防止ビット値とＬＲＵビット値は
それぞれｚＷＰ０とｚＰＴＲＤＡＴにおいてけた上げさ
れる。４つの値は各時刻に全て計算される。任意の時刻
に、ただ１つのラインを任意の１つのウエイで更新でき
る。入来する４つの有効な信号のうちのどの２つを更新
のために用いるかを決定するために、タグＲＡＭはｚＷ
ＡＹＳＥＬを用いる。しかし、制御論理は、ＷＡＹＳＥ
Ｌにより選択された２つの信号のための状態情報を正し
く発生する責任がある。現在のラインに対しては、有効
なビットを計算できる（ｒＶ）。他のラインのための有
効な情報はＡＤＳラッチ（ｚＡＤＳＶ［ＬＲ］［０
１］）から得られる。他のラインがスヌープ・アウトさ
れるものとすると、適切なＡＤＳラッチ３２が信号ｒＣ
ＬＲＶ［ＬＲ］信号によりリセットされているであろ
う。

【００３２】ＷＡＹＣＯＮ論理からＴＡＧＩＦＣ３０と
ＴＡＧＲＡＭへのｚＷＡＹＳＥＬ信号がウエイを選択す
る。タグＲＡＭに対する任意のアクセスに対して、ｚＷ
ＡＹＳＥＬはそれが左側と右側のいずれであるかを判定
する。正常なサイクル中は、ラインを充填のために選択
せねばならないライン充填においてのみｚＷＡＹＳＥＬ
は意味を有する。ＴＡＧＩＦＣにおいては、ｚＷＡＵＳ
ＥＬは、特定のウエイのための状態ビットを再計算すべ
きか、再循環すべきかを判定する。ＴＡＧＲＡＭにおい
ては、それは更新のためのウエイを選択するために用い
られる。

【００３３】ＷＡＹＣＯＭ論理からＲＬＳ１０および書
込み可能化（ＷＥ）論理へのｚＷＥＳＥＬ信号は、サイ
クルの初めにヒット／ミス情報によりウエイ選択がひと
たび決定されると、スヌープがウエイの選択を決定しな
いことを除き、ｚＷＡＹＳＥＬと同じである。タグＲＡ
Ｍだけはどのウエイがスヌープ・アウトされるかを知る
必要がある。ＷＥとＲＬＳに対しては、ウエイ情報はサ
イクル全体にわたって一定のままでなくてはならない。

【００３４】ＴＡＧＡＣＣ１４とＴＡＧＲＡＭ論理から
の信号ｚＷＲＳＴＳ，ｚＷＲＬＲＵ，ｚＷＲＴＡＧは書
込み指令である。状態ビット（有効および書込み防止）
ＬＲＵおよびタグ・ビットは、対応する書込み指令が活
動状態である時に、選択されたセット・アドレスに書込
まれる。指令はｚＦＬＵＳＨｎｎによりオーバライドさ
れる。

【図面の簡単な説明】

【図１】本発明が具体化される２ウエイ、セット連想キ
ャッシュのブロック図である。

【図２】図１の各タグＲＡＭ内のビット・フィールドの
図である。

【図３】ライン充填のためのタグ選択を示す表である。

【図４】ＬＲＵポインタ更新手順の流れ図である。

【符号の説明】

１０ ＲＬＳ論理 １４ ｔａｇａｃｃ論理 １６，２０ タグＲＡＭ １８，２２ データ・キャッシュ

フロントページの続き (72)発明者 ジェイムズ・ナディア アメリカ合衆国 95118 カリフォルニア 州・サン ホゼ・ホールクレスト ドライ ブ・1548

Claims (3)

【特許請求の範囲】
1. 【請求項１】 キャッシュ・データ・アレイ・アドレス
   のためのディレクトリを連想的にサーチするためにタグ
   および有効なビット記憶装置をおのおの含む右ウエイと
   左ウエイの２つのウエイへ構成されたキャッシュ制御器
   ｔａｇｒａｍにおいて、 前記ウエイの１つに対するライン充填サイクル中に２つ
   のラインを選択する第１の手段と、 最近に用いられたポインタが右ウエイを指すのであれ
   ば、右ヒット信号に応じて前記右ウエイがライン充填の
   ために選択されるように、前記ライン充填サイクル中に
   どのウエイを充填するかを選択するための最近に用いら
   れたポインタと、 前記最近に用いられたポインタが前記左ウエイを指すな
   らば、左ヒット信号に応じてライン充填のために前記左
   ウエイを選択する第２の手段と、 前記左ウエイの左ラインが充填された時に前記最近に用
   いられたポインタに前記右ウエイを指させ、前記右ウエ
   イの右ラインが充填された時に前記最近に用いられたポ
   インタに前記左ウエイを指させる第３の手段と、を備え
   る組み合わせ。
2. 【請求項２】 タグ・アドレスをおのおの格納し、１つ
   のウエイに対するライン充填中に選択される２つのライ
   ンが存在するような右ウエイと左ウエイの２つのウエイ
   へ分割されるキャッシュ・ディレクトリにおいて、 前記ディレクトリの右ウエイと左ウエイに格納されてい
   る前記タグ・アドレスとあるタグを比較するために、前
   記ディレクトリの前記右ウエイと前記ディレクトリの前
   記左ウエイへ接続される第１の手段と、 前記右ウエイに格納されている前記タグ・アドレスの１
   つと前記タグの間に一致が存在するという条件で、右ヒ
   ット信号を発生するために前記第１の手段へ接続される
   第２の手段と、 前記左ウエイに格納されている前記タグ・アドレスの１
   つと前記タグの間に一致が存在するという条件で、左ヒ
   ット信号を発生するために前記第１の手段へ接続される
   第３の手段と、 前記最近に用いられたポインタが前記右ウエイを指すと
   いう条件で、前記右ヒット信号に応じてライン充填のた
   めの前記右ウエイを選択するために前記第２の手段へ接
   続される第４の手段と、 前記右ウエイの前記右ラインが充填された時に、前記最
   初に用いられたポインタに前記左ウエイを指させる第５
   の手段と、 前記最近に用いられたポインタが前記左ウエイを指すと
   いう条件で、前記左ヒット信号に応じてラインを充填す
   るための前記左ウエイを選択する第６の手段と、 前記左ウエイの前記左ラインが充填された時に、前記最
   近に用いられたポインタに前記右ウエイを指させる第７
   の手段と、を備える、ライン充填サイクルにおいてどの
   ウエイが充填するかを、最初に用いられたポインタによ
   り選択する装置。
3. 【請求項３】 タグ・アドレスをおのおの格納し、１つ
   のウエイに対するライン充填中に選択される２つのライ
   ンが存在するような右ウエイと左ウエイの２つのウエイ
   へ分割されるキャッシュ・ディレクトリにおいて、 Ａ．前記ディレクトリの前記右ウエイと前記左ウエイに
   格納されている前記タグ・アドレスとタグを比較する過
   程と、 Ｂ．前記右ウエイに格納されている前記タグ・アドレス
   の１つと前記タグの間に一致が存在するという条件で、
   右ヒット信号を発生する過程と、 Ｃ．前記左ウエイに格納されている前記タグ・アドレス
   の１つと前記タグの間に一致が存在するという条件で、
   左ヒット信号を発生する過程と、 Ｄ．前記最近に用いられたポインタが前記右ウエイを指
   すという条件で、前記右ヒット信号に応じてライン充填
   のための前記右ウエイを選択する過程と、 Ｅ．前記右ウエイの前記右ラインが充填された時に、前
   記左ウエイを指すように前記最近に用いられたポインタ
   をフリップする過程と、 Ｆ．前記最近に用いられたポインタが前記左ウエイを指
   すという条件で、前記左ヒット信号に応じてライン充填
   のために前記左ウエイを選択する過程と、 Ｇ．前記左ウエイの前記左ラインが充填された時に、前
   記右ウエイを指すように前記最近に用いられたポインタ
   をフリップする過程と、を備える、ライン充填サイクル
   でどのウエイが充填するかを、最近に用いられたポイン
   タにより選択する方法。