JPH0619794A - データのセット位置の予測装置 - Google Patents

Abstract

(57)【要約】 【目的】キャッシュ内のデータセット位置の予測機構で
あって、キャッシュアクセスパスの効率化のみならず、
一サイクル当たりの複数のアクセスを可能とするもの。 【構成】キャッシュ制御装置がキャッシュアクセスの目
的で、合同クラス内のライン入力の予測のため履歴テー
ブルＳＥＴＬＡＴを維持する。あるキャッシュアクセス
に対してＳＥＴＬＡＴのエントリが、その要求に係わる
論理アドレスビットに直接に基づいて選択される。ま
た、ＳＥＴＬＡＴエントリの選出は、他の情報とともに
そのような論理ビットのハッシングに基づいても可能で
ある。また、同時に類似のハッシング履歴テーブルが形
成され、高精度の仮想アドレス変換予測を可能にする．

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は一般にコンピュータ・シ
ステムのセット連想(set associative) キャッシュ、よ
り詳しくはアクセスのための合同(congruence)クラスの
セット数を決定する方式に関する。

【０００２】

【従来の技術】コンピュータ・システムで性能向上のた
めにキャッシュを使用することはよく知られており広く
利用されている。キャッシュは最近に用いられたメモリ
・データを保持する高速バッファである。プログラムの
参照の局所性(locality of reference nature)により、
大部分のデータのアクセスはキャッシュ内で行われ、大
容量メモリに対する低速のアクセスを回避できる。

【０００３】典型的な高性能プロセッサの設計では、キ
ャッシュ・アクセス経路はクリテイカルパス(critical
path) を形成する。すなわち、いかに速いキャッシュ・
アクセスを実行できるかにより、プロセッサのサイクル
・タイムが決定される。

【０００４】キャッシュは論理的にはデータ・ブロック
又はデータ・ライン(line)とみなすことができ、キャッ
シュ・テーブル・エントリはメモリ・データの特定のブ
ロック又はラインをカバーする。 (以下、キャッシュの
記憶装置はブロックよりはむしろラインと呼ばれる。)
キャッシュの実現は通常は３つの主要部分:ディレク
トリ、アレイ及び制御部分によって達成される。ディレ
クトリはキャッシュ・ライン・エントリのアドレス識別
子のほか、特定の実施例に適した所要の状況タグを含
む。(本明細書でときにはキャッシュ・メモリと呼ばれ
る)アレイは、実際のデータ・ビット、及び特定の実施
例に要求されるようなパリティ検査すなわちエラー修正
のための追加ビットを記憶する。制御回路はキャッシュ
内容及びアクセスの管理に必要なロジックを提供する。
キャッシュにアクセスする際、要求されたデータ・ライ
ンの所在位置を識別するためにディレクトリが索引(loo
k up) される。前記所在位置が見つかれば、キャッシュ
・ヒットが生じ、さもなければキャッシュ・ミスが生じ
る。キャッシュ・ヒットのときは、禁止状態 (例えば、
キー保護違反) がない場合はアレイからデータをアクセ
スできる。キャッシュ・ミスのときは、通常はデータ・
ラインが大容量メモリから取出され、キャッシュによる
アクセスを満足させるために、最初にキャッシュに挿入
され、それによってディレクトリが更新される。キャッ
シュは限られたライン数のエントリを記憶する容量しか
なく、大容量メモリと比較して相対的に小さいから、既
存のラインのエントリを置換することがしばしば必要と
なる。キャッシュ・エントリの置換は通常は最長時間未
使用(LRU) 方式のようなアルゴリズムに基づいている。
すなわち、キャッシュ・ライン・エントリの置換を必要
とするとき、最長時間アクセスされなかったライン・エ
ントリが選択される。

【０００５】効率的な実現を容易にするために、キャッ
シュは通常２次元のテーブルとして構成される(図１)。
行(row)の数はセット連想性(set associativity)と呼ば
れ、そして各列(column)は合同クラスと呼ばれる。デー
タをアクセスする毎に、そのアクセスの一定のメモリ・
アドレス・ビットを用いて合同クラスが選択され、もし
ヒットが存在すれば、選択された合同クラス内のライン
・エントリの１つでデータをアクセスできる。通常、最
初にキャッシュ・ディレクトリを (並列アドレス比較に
より) 探索させ、(関連した合同クラス内の)セット位置
を識別し、見つかったロケーションで、アレイからデー
タをアクセスさせる速度は遅すぎる。前記順次処理は普
通は連続する２計算機サイクルの実行を必要とする。こ
れはプロセッサ性能をかなり低下させる。後選択(late-
select) と呼ばれる広く普及しているアプローチは、下
記のように１サイクルでディレクトリ探索及びアレイ・
データ・アクセスを達成する。実行装置によるデータ単
位(例えば、ダブルワード)の取出しについて考える。ア
クセスのための正確なセット位置を知らずに、ディレク
トリが索引されている間に、アレイ制御は最初に合同ク
ラス内の全てのセット位置にあるラインから候補データ
単位を検索する。キャッシュ・ヒットの際に、ディレク
トリ制御はこれらの検索されたデータ単位の１つの最終
的な選択の信号を出し、それを要求元実行装置に送る。
従来の後選択手法はディレクトリ索引とアレイ・アクセ
スの間に多くのオーバラップを可能にするけれども、デ
ィレクトリ検索が行われ且つその結果が実行装置に引渡
された後にだけ最終的なデータ選択を実行できる。前記
後選択方法のもう１つの欠点は、アレイからアクセスさ
れた複数のデータ単位が多くても１つの実際に役立つデ
ータ単位しかカバーできず、アクセスされた単位の残り
の部分が無駄になることである。より高性能のプロセッ
サでは、I/E 装置からの複数の別個のアクセスをキャッ
シュがサポートすることが不可欠であることがよくあ
る。なぜなら、役立たないアレイ・アクセスによるI/O
の浪費が設計上のネックになるからである。

【０００６】キャッシュ設計を複雑にするもう１つの状
況は、コンピュータ・システムで一般に用いられる仮想
アドレス指定構造である。仮想メモリ・システム(例え
ば、IBM/3090構成)では、各ユーザ・プロセスがそれ自
身の仮想アドレス空間を有するビュー(view)を有するこ
とがある。プログラムを実行するとき、仮想アドレス・
ページにオペレーティングシステムが実メモリ・ページ
(例えば、４キロバイト／ページ)を動的に割振ることが
ある。プログラムからアクセスされたページがそれに割
振られた実メモリ・ページを有しないとき、例外(ペー
ジ不在)状態が起こり、実メモリ・ページ・フレームを
適切に割振るようにオペレーティングシステムをトリガ
する。ページ不在処理は通常は超高性能オーバーヘッド
に関連づけられ、ディスクのような低速の補助装置から
のデータ・アクセスを必要とすることがよくある。しか
しながら、強固なプログラム局所性の特性により、適切
なオペレーティングシステムはプログラム実行中非常に
低いページ不在率を維持できる。通常、オペレーティン
グシステムは特定の構成のソフトウェア・テーブルに実
ページ割振り情報を維持する。そのために、一般にセグ
メント及びページ・テーブルを有する２レベル変換テー
ブル構造が用いられる。各プログラム空間は、各エント
リがページ・テーブルを指す、それ自身のセグメント・
テーブルを有する。ページ・テーブルで、各エントリは
実ページ割振り情報と、特定の構造に必要な他の幾つか
の状況タグを記録する。

【０００７】オペレーティングシステムは前記変換テー
ブルをその設計アルゴリズムによって管理する。仮想ア
ドレス指定を採用した成果の１つは、異なるプログラム
・アドレス空間からの同じ仮想ページ・アドレスが記憶
装置内で論理的に関連させられず且つ異なる実ページ・
フレームに割振られることを可能にすることである。更
に、IBM/3090のような構成では、同じ実ページ・フレー
ムは異なるプログラム又はプロセッサから異なる仮想ア
ドレスを介してアクセスできる。これらの全ての構成上
の要求により、プロセッサからの記憶装置アクセスを処
理するために大部分のシステムは仮想アドレス変換と呼
ばれるステップを必要とする。仮想アドレス変換は仮想
ページ・アドレスを実ページ・アドレスに変換する。も
し実ページ・フレームが割振られていなければ、ページ
不在例外がトリガされる。その場合、オペレーティング
システムは割振りが終了すると変換情報を更新し、そし
てページ不在を生じたプログラムにその実行を再開始さ
せる。

【０００８】最近の大部分のシステムでは、仮想アドレ
ス変換プロセスを高速化するためにハードウェア機能が
用いられる。一般にプロセッサ毎に変換ルックアサイド
・バッファ(TLB = Translation Lookaside Buffer) が
用いられる。TLBは、能動的にアクセスされた仮想ペー
ジの変換情報を記録するハードウェア・ディレクトリ・
テーブルである。プログラム・アドレス指定の局所性に
より、(例えば、64〜1024ページ・エントリの) 比較的
小さいTLBは、プロセッサからの記憶装置アクセスの大
部分(例えば、99.95％以上)について変換情報を捕捉で
きる。TLBミス状態の場合 (即ち、TLBが特定の記憶装置
アクセスをカバーできないとき)にのみ、 (例えば、マ
イクロコード又はオペレーティングシステムを介して)
より遅い変換が実行される。ハードウェア実現の効率化
のために、通常、TLB はキャッシュ・ディレクトリのよ
うなセット連想テーブルとして構成される。 (一定のプ
ログラム空間識別子を含む) 所与の仮想ページ・アドレ
スについては、合同クラスを取出すために、ハードウェ
アは一定のアドレス・ビット (及び特定の設計に関する
他の特定の情報) を用いる。合同クラスの範囲内で、ハ
ードウェアはエントリの並行探索を実行し且つ変換の結
果を識別する。

【０００９】多くのプロセッサ設計では、記憶装置アク
セスはキャッシュ・アクセスの最終的な決定以前にTLB
変換を行なう必要がある。大部分の最近の設計では、TL
B索引はキャッシュ・ディレクトリ探索と並行して実行
され、その結果はアレイ・データの最終的な後選択と組
合わされる。図２はこのような設計を示す。キャッシュ
・アクセスを決定するための複数のディレクトリ探索に
関する前記要求は多くのキャッシュ設計の最適化を複雑
にする原因になっている。前記複雑さは全て、プロセッ
サが記憶装置アクセス要求を出すとき、従来のディレク
トリ索引の結果を知らずには、データの正確なロケーシ
ョンをキャッシュ・アレイが決定できないので信号遅延
を生じることに起因する。あいにく、種々の構成上の理
由及び計算機装置上の理由により、データ・アクセスの
ための前記正確なロケーションを容易に得ることができ
ない。従来の後選択機構の副作用は、１つのデータ単位
を選択するために複数のデータ単位を検索するので、プ
ロセッサ使用されなかったデータ単位のアレイI/O が無
駄になることである。その結果、非常に高い性能のコン
ピュータにおける同時複数の(独立した)キャッシュ・ア
クセスをサポートすることが困難になることがよくあ
る。

【００１０】キャッシュを実現するための多くの設計が
提案されている。図３はIBM/3090の31ビット論理アドレ
ス指定のための64キロバイト(KB)プロセッサ・キャッシ
ュの設計の概要を示す。このキャッシュは128 合同クラ
スを有する４ウェイ・セット連想方式である。ラインの
サイズは128 バイトである。キャッシュ・ディレクトリ
DIR、キャッシュ・メモリ・データ・アレイARR及び２ウ
ェイ・セット連想 TLBがある。プロセッサI/E 装置及び
マイクロコードは論理アドレスにより記憶装置アクセス
要求を出す。論理アドレスは、プロセッサにおける現在
のアドレス指定のモードにより、仮想又は実アドレスの
どちらかである。I/E 装置からの仮想アドレスによるダ
ブルワード(８バイト)取出し要求に関する更に複雑な場
合について以下に説明する。合同クラスの選択に用いら
れるビット18〜24のうち、２ビット(18〜19)はページ・
アドレスの部分である。予期しない変換結果により、こ
れらの２つのビットが４つの可能な組合せのどれかで２
実アドレス・ビットに変換されることが起こりうる。ア
クセス中であるラインをたぶん含みうる４つの合同クラ
ス中に、現にアクセスされた論理アドレスにおけるアド
レス・ビットにより決定された合同クラスは主合同クラ
ス(PCC = Principal Congruence Class)と呼ばれ、他の
３つはシノニム合同クラス(Synonym Congruence Class)
と呼ばれる。プログラム局所性によりキャッシュ・アク
セスの大多数が主合同クラスをヒットするけれども、ア
クセスされたラインが他の(シノニム)合同クラスの１つ
に属する可能性がなお存在する。これがいわゆるシノニ
ム問題である。IBM/3090システム設計では、下記のステ
ップが並行して実行される。 (1) 論理アクセス・アドレスのビット18〜31がARR 制御
部に引渡される。ビット18〜24が主キャッシュ合同クラ
スを決定するために用いられる。そしてキャッシュ・ア
レイの主合同クラス中の４つのライン・エントリの各々
から (ビット25〜28で示すような) ダブルワードが読み
出される。後選択信号が受信されるまで、これらの４つ
のダブルワードは要求元I/E 装置に送り出されない。 (2) キャッシュ・ディレクトリ索引のためにビット18〜
24がDIR に送られる。各DIR エントリは関連したライン
の実アドレスを記録する。主合同クラス及びシノニム合
同クラスの16のディレクトリ・エントリの全てが読み出
される。 (3) 合同クラスを選択するためにTLBにより一定の仮想
アドレス・ビット(本明細書では詳述しない)が用いら
れ、２つのTLBエントリ実アドレス変換情報が読み出さ
れる。

【００１１】次に、キャッシュ・ディレクトリから読み
出された16実ライン・アドレスは、32個の比較器を介し
てアドレス整合のためにTLB から読み出された２つの実
アドレスと組合わされる。(他の関連タグ整合もあるが
本明細書では詳述しない。)アクセスされたラインの変
換アドレスがキャッシュ・ディレクトリ実アドレスの１
つと一致することが分かると、キャッシュ・ヒット状態
が生じる。さもなければ、キャッシュ・ミスが起こり、
キャッシュ・ミス処理をトリガする。キャッシュ・ヒッ
ト状態が起きると、ラインを含む合同クラスが主合同ク
ラス中にあることもあり、ないこともある。次に下記が
キャッシュ制御部により実行される。 ・主合同クラス(PCC)ヒット：選択されたダブルワード
を要求元I/E装置にゲートする信号が後選択ロジックに
送られる。 ・シノニム合同クラス・ヒット：後のアレイ取出しによ
りシノニム合同クラスからダブルワードがアクセスされ
る適切なステップがとられる。これはアクセス遅延を大
きくする。

【００１２】キャッシュ・ミス状態では、キャッシュ制
御部は主記憶装置からのラインのコピーを要求する。ラ
インが戻ると、主合同クラス中の割振りキャッシュ・エ
ントリに入れられる。

【００１３】IBM/3090キャッシュ設計では下記の欠点が
明らかである。最初に、シノニム状態を効率的に決定す
るために32個の比較器が用いられる。キャッシュ・サイ
ズが大きくなるか又はTLB セット連想性が増す場合、更
に多くの比較器が必要になる。次の問題は、ディレクト
リ読取／比較のための後選択を待つことにより、キャッ
シュ・アクセス経路が長くなることである。

【００１４】前述の欠点を回避するために一定のタイプ
の予測方法を用いる設計が既にある。最もよく知られて
いる方法は直接写像(direct map)キャッシュ設計であ
る。直接写像キャッシュは１のセット連想によるもので
ある。キャッシュ合同クラス毎に１つのライン・エント
リしかないから、キャッシュ・アクセス可能性は極めて
限られている。図４はIBM/3090の方法の変更による直接
写像キャッシュ設計を示す。IBM/3090設計に類似して、
キャッシュ・ミスが起きると、主合同クラスにラインが
入れられる。I/E 装置から出された論理アドレス毎に、
キャッシュ制御部は主合同クラスを選択するために必要
なビットを取出し、要求元装置へのデータがそこに直に
読取られる。並行して、キャッシュ・ディレクトリ及び
TLB 索引が行われる。主合同クラスに対するキャッシュ
・ヒットの場合には、ディレクトリ比較ロジックは、ア
クセスを終了する信号を要求元I/E 装置に送る。さもな
ければ(キャッシュ・ミス又はシノニム合同クラスのヒ
ットの場合)、ARR から受取ったデータを取消し、適切
な活動をトリガする信号が要求元装置に送られる。IBM/
3090設計の場合のようにシノニム問題はなお存在する。
キャッシュ・ミスが起きると変換後の実アドレス・ビッ
トによって決定された合同クラスにキャッシュ・ライン
を挿入する実アドレス・キャッシュ設計も既にある。し
かしながら、前記方法はアレイ・アクセスとディレクト
リ探索の間の並行を失う。直接写像キャッシュ設計の最
も重大な欠点は不十分なキャッシュ・ヒット率である。
キャッシュ・サイズが同じならば、セット連想性が１か
ら２、２から４に増すにつれてキャッシュ・ヒット率が
かなり向上することはよく知られている。

【００１５】予測に基づいたキャッシュ設計に関して最
近に提案されたもう１つの手法は、J.H.Chang, H.Chao,
and K.So, "Cache Design of A Sub-Micron CMOS Syst
em/370," Proc. 14th Symposium on Computer Architec
ture, 1987, pp. 208-213 のMRU キャッシュ設計であ
る。キャッシュ置換は通常は合同クラス毎に管理され
る。各合同クラス内には、適切な置換状況タグで示され
たような最後に使用された(MRU = most recently used)
エントリ及び最長時間未使用(LRU = least recently us
ed)エントリがある。プログラム局所性によりキャッシ
ュ・アクセスはMRUライン・エントリをヒットする見込
みが最も大きい。新たなラインを合同クラスに挿入する
必要があるとき、LRUエントリが置換されるエントリと
して選択される。MRUキャッシュ方法は直接写像キャッ
シュとして全キャッシュのMRU ラインを表示する。その
基本原理は、アクセスされる一の合同クラスが決定され
る毎に、とりあえずMRU ライン・エントリからのデータ
を取り出すことである。ディレクトリ比較結果に基づい
たアクセスの確認又は取消しは、直接写像キャッシュ方
法と同じように動作する。MRU キャッシュ設計では、ミ
スしたラインが(変換後に)実アドレス・ビットに関連し
た合同クラスに挿入される、実アドレス・キャッシュが
提案された。仮想アドレスによりキャッシュ・アクセス
の決定を容易にする目的で、MRU キャッシュ設計はアド
レス変換情報を予測するために類似の手法を用いる。す
なわち、所与の仮想アドレスについて、関連したTLB合
同クラスのMRUエントリにおける実アドレス・ビットが
読み出されアレイ制御部に引渡されてから、実アドレス
が実際の変換として検査される。読取られたMRU エント
リ・データの(予測)合同クラスを選択するためにTLB か
らの予測実アドレス・ビットがアレイ制御部により用い
られるが、並行してTLB 装置は実アドレス予測の正しさ
を判定するための比較を行なう。図５はMRUキャッシュ
設計を示す。

【００１６】直接写像方法と比較して、MRU キャッシュ
設計は１ウェイよりも多くの・セット連想性を可能にす
ることによりキャッシュ・ミスの確率を低くする。しか
しながら、MRU 予測はキャッシュ・アクセス予測の精度
を低下させる。直接写像キャッシュの場合は、キャッシ
ュ・ヒットが起きると、100％の予測精度がある(キャッ
シュ・ミスはどのみち満足されない)。しかしMRU予測の
精度はMRU エントリに対するアクセス・ヒットが起きる
見込みによって制限される。IBM/3090設計の例で説明し
た64 KB キャッシュについて考えてみよう。一般的な商
用ワークロードについては、予測によって90％よりもや
や大きい実際のキャッシュ・ヒットが正しく決定され
る。異なるワークロードについては、予測の精度が低下
することがある。また、シミュレーションによる研究に
よれば、データ・キャッシュに MRUキャッシュ方法 (即
ち、オペランド・アクセスだけを処理し命令コード取出
しを処理しないキャッシュ)が用いられると、MRUエント
リ予測はずっと悪くなることが示されている。MRU キャ
ッシュ設計のもう１つの欠点は、アレイをアクセスする
前に (MRUエントリの) TLBをアクセスする必要があるこ
とである。これはキャッシュ・アクセスのクリティカル
パスに一定の遅延を生じさせる。更に、それを正しく実
現する際に複雑さを伴う。TLB は相対的に大きいディレ
クトリであるから、通常はキャッシュ・アレイに物理的
に極めて接近して配置することができない。TLB サイズ
の大きさのもう１つの影響は高速回路による TLBディレ
クトリを実現する際の費用である。高速コンピュータに
おいて、前記２つの要素は、実アドレス予測経路、従っ
てキャッシュ・アクセスクリテイカルパスのタイミング
を最適化することを困難にする。

【００１７】直接写像及びMRU キャッシュ方法で採用さ
れた予測方法の欠点は、前記２つの方法がキャッシュ又
はTLB の物理的な構造に基づいて実行されることに起因
する。直接写像設計は、物理的なキャッシュ外面形態を
(１次元構造に)平板化することにより究極の簡単さ及び
予測精度を達成するが、そのためにキャッシュ・ミスを
多くする。MRUキャッシュ方法は、(TLB及びキャッシュ
の)予測が物理的な MRUエントリに基づくことを必要と
するので、精度を低下させるとともに実現を困難にす
る。

【００１８】キャッシュ・アクセスに関する良好な予測
方法の真髄は適切な履歴を用いて高い精度及び効率的な
実現を達成することである。２次元構造を有するキャッ
シュをアクセスするために、２つのパラメータ：(1) 合
同クラス及び(2) 合同クラス内のライン・エントリ位置
(即ち、セット位置)を決める必要がある。２つのパラメ
ータは履歴テーブル又は、実際のキャッシュ外面形態に
関係なく有効に実現可能な、他の手段により正確に予測
できる。同様な原理が実アドレス変換の予測に当てはま
る。この着想を用い柔軟に実現できる有効なキャッシュ
・アクセスを可能にする従来の技術は知られていない。

【００１９】

【発明が解決しようとする課題】本発明の目的は効率的
なキャッシュ・アクセスの実現を可能にする高精度の予
測機構を提供することにある。予測方法は適切な履歴テ
ーブルに基づく。

【００２０】

【課題を解決するための手段】本発明によれば、キャッ
シュ制御は合同クラス内のライン・エントリ(即ち、セ
ット番号)を予測するSETLATを維持する。所与のキャッ
シュ・アクセスにおいては、論理アドレス・ビットに基
づいてSETLATエントリを直に選択できる。十分なランダ
ム化を達成するために、SETLATエントリの選択は、前記
論理アドレス・ビットと他の情報とのハッシング(hashi
ng) に基づくこともできる。同様のハッシング履歴テー
ブルが仮想アドレス変換情報を高精度で予測するために
考案されることもある。これは関連出願に詳細に記述さ
れている。前記予測機構はキャッシュ・アクセス経路の
効率的な実現を可能にするだけではなく、複数アクセス
／サイクルを達成する可能性も提供する。

【００２１】提案された予測方法は種々のディレクトリ
に基づいたテーブル・アクセスのための効率的な実現に
関する一般的な方法も提供する。

【００２２】より詳しくは、セット連想キャッシュにお
いて所与のアクセスのデータ・ロケーションを予測する
アレイ制御の機構が開示される。予測が正しいとき、パ
フォーマンスはロケーションが既知の場合と同じであ
る。間違った予測の場合は、データ・アクセスは打切ら
れ、適切な予測が再度行なわれる。高精度の予測機構に
より、キャッシュのデータ・アクセスは間違った予測の
最小のオーバーヘッドにより最適化させることができ
る。

【００２３】

【実施例】図６は、本発明を用いうるタイプのシステム
構造のブロック図を示す。プロセッサは命令及び実行(I
E)装置110 とキャッシュ装置60を備える。各IE装置は主
記憶装置(MS)80内のオペランドの取出し及び記憶を必要
とする命令を出すハードウェア及びマイクロコードを備
える。記憶制御装置(SC)70は、プロセッサ又は I/Oチャ
ネル90により要求された記憶関連活動を調整する。説明
を簡単にするため、IE装置110 はサイクル毎にせいぜい
１つの記憶取出し又は記憶要求を出すことができ、各記
憶要求はダブルワード(８バイト)の細粒(granule) 内に
あるものと仮定する。

【００２４】IE装置110 から要求されたダブルワードを
含むキャッシュ・ラインがキャッシュ装置60に存在する
ときは、キャッシュ・ヒットと呼ばれる状態である。さ
もなければ、キャッシュ・ミスと呼ばれる状態である。
キャッシュ・ミスが起きると、キャッシュ装置60は、一
定の非常に特殊な状態を除き、IE装置 110からの要求を
満たす前にSC 70を介してMS 80から前記ラインを要求す
る必要がある。

【００２５】図７はキャッシュ装置60のより詳細な図面
である。従来のキャッシュ設計の場合のように３つの主
要な素子がある。TLB 110 は仮想アドレスから実アドレ
スへの高速変換に用いられる変換ルックアサイド・バッ
ファである。DIR 120 は、キャッシュのライン・エント
リ毎に、アドレス識別及び他の必要な状況タグを含むキ
ャッシュ・ディレクトリである。ARR 130 は実際のキャ
ッシュ・データを保持するキャッシュ・メモリ・アレイ
である。これらの従来の３つの素子に加えて、本発明に
よる新たな設計は、データ・アクセスの合同クラス内の
ライン・エントリを予測するために用いられる履歴テー
ブルSETLAT 140も含む。説明の都合上、４ウェイ・セッ
ト連想キャッシュ及び２ウェイ・セット連想TLB が仮定
される。SETLAT 140は２ビット／エントリの１次元履歴
テーブルとみなしうる。

【００２６】図７に示すキャッシュ取出しアクセス動作
の高レベルの流れはIBM/3090キャッシュ設計の変更とみ
なしうる。DIR 130 のエントリ毎に、関連したラインの
実アドレスが(有効と表示された場合には)記録される。
IEから仮想アドレスA 150 として指定された所与のダブ
ルワード取出し要求については、並行して下記動作が生
じる。 (1) TLB 110から合同クラス (TLBCONG[A]) を選択する
ために経路171を介して仮想アドレスA 150の一定のビッ
トが 用いられる。TLBCONG[A]の２つのエントリで実ア
ドレスが (他の所要の状況タグとともに) 経路181 を介
してアドレス比較装置(CMP)161に引渡される。 (2) DIR 120で合同クラスのセットを選択するために、
仮想アドレスA 150の一定のビットが経路172 に沿って
引渡され使用される。ちょうどIBM/3090設計のように、
選択された合同クラスは主合同クラス及び全ての可能な
シノニム・クラスをカバーする。選択された合同クラス
内の全てのDIR エントリにおける実ライン・アドレスが
(他の所要の状況タグとともに) 経路182に沿ってCMP 1
61に引渡される。 (3) ARR 130で主合同クラス (CONG[A]) を選択するため
に、仮想アドレスA 150 の一定のビットが引渡され使用
される。選択された合同クラスから、４ダブルワード
が、合同クラスの各セット番号から１つずつ、アレイか
ら読み出される。読み出された４ダブルワードは後選択
装置162に引渡される。 (4) SETLAT 140でエントリ (SETLAT[A]) を選択するた
めに、仮想アドレスA 150の一定のビットが経路174に沿
って引渡され使用される。選択されたSETLAT[A]エント
リにおける２ビットが経路184に沿って後選択装置162に
引渡される。この２ビットは経路185に沿ってCMP 161に
も引渡される。CMP 161も追加の(例えば、ページ境界と
ライン境界の間のA 150の)アドレス・ビットを必要とす
るので、当該データ経路は図７には詳細には表示されな
い点に注意されたい。

【００２７】後選択装置162は、SETLAT[A]から得られた
２ビットに基づいて、アレイから読み出され装置162 に
保持された４ダブルワードのうちの１つを選択する。選
択されたダブルワードは経路192を介して要求元IEに直
接送られる。CMP 161の機能は、経路192 を介して要求
元IEに送られたダブルワードが正しいキャッシュ・ライ
ン・エントリからであるかどうかを決定することであ
る。CMP 161 はアクセスをより複雑にする他の異常な状
態(例えば、記憶キー違反)を判定することもできる。こ
の機能は本発明にはあまり重要ではないので無視するこ
とにする。 CMP 161からSETLAT 140へのライン193 はSE
TLAT更新ラインである。後に説明するように、このライ
ンはSETLAT 140でのセット位置(set-position)履歴の更
新に用いられる。本実施例では詳細には記述されない
が、多くの実施例では、所要の情報を効率的に決定し且
つ(例えば、SETLAT更新ライン193 による)信号引渡しを
有効に実行しうるようにCMP 161又はその周辺の装置に
他の機能(例えば、キャッシュ及びTLB 置換管理)があり
うる。経路192を介してIE 110に送られたデータは、下
記が起きるときにのみ正しい。 ・主合同クラス CONG[A] 内で SETLAT[A] により表示さ
れたDIR 120 のエントリ(DIR[A]と表示される)は有効な
(例えば、有効ビット V＝1 を有する)ラインを含む。 ・TLB 110から選択され経路181に沿って引渡された TLB
CONG[A] の２つのエントリのうちの１つが仮想アドレス
A 150 の実ページ変換を包含する。このようなTLB エン
トリは、それが存在するとき、TLB[A]として表示される
ようにする。 ・DIR[A]に記録された実ページはTLB[A]における変換結
果と一致する。更に、DIR[A]によって識別されたライン
のページ境界(仮想＝実)内のアドレス・ビットが仮想ア
ドレスA 150の対応するビットと一致する。CMP 161は一
般的な組合せロジックによりこれらの状態を検査し、経
路191に沿って確認信号(例えば、正しいアクセスの場合
はシングル・ビット C＝1、間違ったアクセスの場合は
C＝0)をIE 110要求側に送る。IE 110は、確認ライン191
から正の信号(C＝1)を受取ると、データ・ライン192
から受取ったダブルワード・データを通常(例えば、次
の計算機サイクル中に)用いる。さもなければ、IE 110
は経路192 で受取ったデータを無視し、後のサイクルで
正しいデータを得る動作が行なわれる。この特定の実施
例では、IE 110は、キャッシュ装置60に対する取出し要
求を出していれば、アクセス保留状態に留まるものと仮
定される。アクセス保留状態は確認ライン191 に正の確
認信号(C＝1)が現われるときにのみ消失する。別の実施
例は、特定の要求により、IE記憶アクセス状態に異なっ
た処理をすることがある。例えば、設計により、一定の
状況ではIE 110によってアクセス要求を再度出すことが
できる。

【００２８】下記の状態が起きると要求元IE 110で経路
192 に間違ったデータを受取ることがある。 (1) TLBミス：これはTLB 110が仮想アドレスA 150 の変
換情報を持たないときに起きる。一般的な変換プロセス
は所要の変換情報がTLB 110 に最初に取込まれるように
トリガされる。 (2) TLBヒット及びキャッシュ・ミス：これは、経路182
で受取ったDIR情報のどれもが、首尾よく変換された情
報TLB[A]により仮想アドレスA 150 と実ライン・アドレ
スとの一致を生じえないことを、CMP 161 が検出すると
起きる。該ラインのコピーがMS 80 からキャッシュに取
込まれるように普通のキャッシュ・ミス動作がトリガさ
れる。これはキャッシュ・ミス状態と呼ばれる。 (3) SETLAT予測と異なるエントリで主合同クラスに対す
るTLB ヒット及びキャッシュ・ヒット：これは、主合同
クラス中のライン・エントリが仮想アドレスA150の実ア
ドレスと一致するが、該エントリがSETLAT 140により経
路185に予測されたセット位置にないときに起きる。こ
れは誤りセット予測状態と呼ばれる。 (4) シノニム・キャッシュ合同クラスに対するTLB ヒッ
ト及びキャッシュ・ヒット：これは、CMP 161が(主合同
クラスCONG[A]と異なる)シノニム合同クラス中のDIR エ
ントリでアクセスされたラインの実アドレスの一致を見
出だすと起きる。(この場合、予測されたSETLAT[A]が実
際のラインが存在するセット位置(0〜3)と異なることも
起こりうる。) これはシノニム・ヒット状態と呼ばれ
る。

【００２９】TLB ミス状態の変換プロセスの詳細な説明
は行なわない。通常の手順によって所望の変換情報がTL
BCONG[A]の置換エントリにロードされるものと仮定す
る。しかしながら、いったんTLB ミス状態が消失すれ
ば、キャッシュ装置60は、前述のように、(一定のレジ
スタ又はスタックに記憶されている) 仮想アドレスA 15
0の待ちアクセスを再開始できるものと仮定する。

【００３０】キャッシュ・ミス状態は最初に該ラインが
MS 80 から取出されることを必要とする。ライン取出し
プロセスはIBM/3090記憶設計に類似するものと仮定す
る。キャッシュ装置60はSC 70にライン・ミス取出し要
求を出す。SC 70は適切な時点でMS 80からキャッシュ装
置60へのライン取出しをスケジュール(schedule) す
る。IBM/3090設計のように、新たに取出されたライン
は、 (変換後の実アドレス・ビットによる代わりに)仮
想アドレスA 150により決定された主合同クラス CONG
[A]内(の前記置換エントリ)に入れられる。新たに取出
されたライン・エントリの位置を、予測されたSETLAT
[A] 履歴によって正しく反映できないことが明白であ
る。履歴の調整は後に説明する。

【００３１】ここで詳細に説明する１つの事項は、キャ
ッシュ・ミスのときIE 110に対してより迅速に応答する
ために用いられている従来のミス・バイパス (miss byp
ass)機構である。キャッシュ・ライン・サイズ(例え
ば、64〜128バイト) は一般にIE要求細粒(例えば、８バ
イト・ダブルワード)の倍数である。IE 110により要求
されたダブルワードは関連記憶ラインにおける最初のダ
ブルワードではないことがよくある。周知のミス・バイ
パス機構により、MS 80 からキャッシュ装置60に転送さ
れたラインは、該要求されたダブルワードにより開始
し、回転式に順序づけられたデータ単位の残りのライン
とともに継続する。最初に転送されたダブルワード(IE
110により要求されたダブルワード)はキャッシュに戻る
と直ちに、要求元IE 110にも直接送られる。このよう
に、他のデータ単位の転送を待ち又はキャッシュ装置60
をアクセスする要求を再び出す必要なしに、IE 110は受
取ったデータによる再実行を再開始できる。本実施例に
おける設計はこのようなバイパス特性を有効にサポート
できる。CMP 161 は、キャッシュ・ミス状態を決定する
と、IE 110がアクセス保留状態にある間にミス処理をト
リガする。要求されたダブルワードがIE 110にバイパス
されると、アクセス保留状態は非活動化されるべきであ
る。これはライン191に C ＝１信号を出すことにより、
又はなにか他の簡単な方法により(例えば、特別にバイ
パスされるデータ使用可能信号により)達成できる。

【００３２】間違ったセット予測状態の場合、IE要求に
関連したキャッシュ・ラインは実際に主合同クラス内に
あるが、予測されたSETLAT[A] と異なるセット・エント
リにある。キャッシュ装置60が行なうことは、(例え
ば、後続する計算機サイクルで)正しいセット位置から
ダブルワードが下記のように選択されるようにすること
である。アドレス比較ステージで、CMP 161 は間違った
セット予測状態を検出するだけではなく、(主合同クラ
スCONG[A]で) IE要求を満足しうるライン・エントリの
正確なセット位置も決定する。また、経路191でIE 110
に C ＝ 0 信号を送るのと並行して、CMP 161はそれが
見出だす正しいセット位置(例えば、2ビット)をSETLAT
更新ライン193 を介してSETLAT 140の制御部に送る。SE
TLAT 140の制御ロジックは、ライン193 から受取った情
報を用いて、ダブルワードの次の再アクセスを(例え
ば、次のサイクルで)指示されたセット位置から正しく
取出し、それに従って履歴SETLAT[A] を更新する。履歴
更新動作の詳細は後に説明する。間違ったセット予測の
場合には、正しいダブルワード・データがARR 130から
経路183に読み出されており、通常のアクセスについて
説明したように (例えば、次のサイクルで)再読取りせ
ずに、経路184を介して受取った正しいセット位置によ
り直接選択できる。しかしながら、提案された機構を用
いる大部分のプロセッサ設計では、ARR 読取りがクリテ
イカルパスタイミングに既に組込まれている。その結
果、大部分の設計では、この場合に既に読み出されたデ
ータの後選択に関する特別なケースとして制御ロジック
を複雑にする必要はない。

【００３３】次に、間違ったデータ・アクセスのシノニ
ム・ヒット状態について説明する。この場合、CMP 161
は、アクセスされたダブルワードが主合同クラスCONG
[A]と異なるシノニム合同クラスをヒットすることを検
出する。更に、CMP 161 は目標ラインの正確なセット位
置が関連シノニム合同クラスであることを見出だす。発
見されたセット位置はSETLAT更新ライン193 を介してSE
TLAT 140の制御部に送られてSETLAT[A] が更新され、間
違ったセット予測状態の場合と全く同様に (後の再アク
セスのとき) 正しい位置からデータがアクセスされる。
説明の残りの部分は、次に正しい合同クラスからデータ
をアクセスする方法である。それに関しては、シノニム
・ヒットを処理する多くの既知の方法から任意の方法を
採用できる。IBM/3090設計で実現された前記方法の１つ
は下記のとおりである。シノニム・ヒットの際に、キャ
ッシュ制御部はシノニム合同クラスに関するデータを再
びアクセスするように指示する。この方法は各シノニム
・ヒットの(１サイクル以上の)遅延を生じるが、低い周
波数のシノニム・ヒットによるシステム全体の不利点は
些細なものである。本実施例に記述されたキャッシュ設
計は、その実現による複雑さを最小にするこの方法を利
用できる。例えば、後のサイクルでシノニム合同クラス
のアクセスが再度指示されると、(主合同クラスの代わ
りに)シノニム合同クラスから４ダブルワードを読み出
すために、一定の信号をARR 130 の制御部に引渡す必要
がある。次の再アクセスの際に、前述のSETLAT更新が
(ライン193を介して)自動的に正しいセット位置を与え
るので、後選択ロジック162はリセットされた保留アク
セス状態を有する正しいデータを確認信号(C＝１)を介
してCMP 161からIE 110に送ることができる。シノニム
・ヒットに関するもう１つの既知の方法は米国特許第44
00770号で提案された。この方法は主として(一定の特別
な状態を除き)、キャッシュ・ラインの別のコピーを、
(シノニム合同クラスへの取出しを再度指示する代わり
に)現にミスした主合同クラスCONG[A]に取込ませる。下
記の例外はあるが、この方法は本発明でも使用できる。
ここでSETLAT 140の制御部は(シノニム合同クラスで見
つかったラインの代わりに)主合同クラスに挿入された
新たなライン・エントリのセット位置を受取るべきであ
る。このように、間違ったセット位置予測は新たなライ
ンへの次のアクセスで回避できる。

【００３４】間違ったデータ・アクセスの処理について
説明したので、次にSETLAT履歴更新に関する動作につい
て説明する。SETLAT制御ロジックはCMP 161 から受取っ
た信号193によりその履歴を更新する。特定の実施例に
より、セット位置更新信号193は(４つの可能なセット位
置をコード化する)２ビット又は (各ビットが特定のセ
ットの選択を示す)４ビットである。多くの設計では、S
ETLAT更新ライン193はキャッシュ・アクセス(正しいア
クセス又は間違ったアクセス)毎に活動状態でありう
る。これは時折の履歴更新活動を指示するための追加の
信号ラインを節約できる。しかしながら、多くの他の実
施例では、SETLAT更新ライン193 が活動状態であるかど
うかを追加の状況信号に表示させることが望ましい。例
えば、SETLAT[A] が間違っており、次のサイクルでアレ
イの再アクセスのために更新を要する状況について考え
てみる。最初にSETLAT 140のエントリを更新させ、次い
で同じサイクルでそれを読み出させ且つ経路184を介し
て後選択装置162に送らせることは余りにも時間的に遅
すぎる。 (実施例によっては、これはSETLATディレクト
リを実現するためには２ポートのアレイを必要とするこ
とがある。) この場合、より効率的な実現は、SETLAT制
御部が (活動状態のSETLAT更新のための特別な状況ラッ
チを介して)現に必要なSETLAT[A]の更新が保留されるこ
とを実現し、新たに受取ったセット位置を経路184を介
して送出するのと並行してSETLAT[A]を更新することで
ある。

【００３５】以上、仮想アドレスによるIE記憶装置アク
セスに関する新たな設計について説明した。多くのアー
キテクチャ(例えば、IBM/3090)では、IEは実モードでも
同様に記憶装置をアクセスできる。その場合、TLB 変換
経路が無視される外は、基本的には同じように動作する
設計である。IBM/3090設計のように、これは、実モード
標識信号をCMP 161に送り、経路181 で受取ったTLB結果
との比較を無視するることにより容易に達成できる。

【００３６】本発明に従ってIE 110からの取出しアクセ
スを説明したので、IE 110からのオペランド記憶に関す
る動作について次に説明する。IBM/3090設計では、据置
き記憶(deffered store)機構が使用される。IE 110から
のオペランド記憶要求について考えてみる。この要求は
４個の記憶レジスタ(STRREG)の１つにラッチされ、先ず
ディレクトリ探索に関するディレクトリ優先順位を待
つ。ディレクトリ・サイクルでは、TLB 110及びDIR 120
が前述のようにCMP 161で比較された結果と並行して探
索される。ディレクトリ・サイクルの終りで、オペラン
ド記憶が ARR 130にプットアウェイ(putaway) され、そ
こで(合同クラス及びセット)を調整することが見出ださ
れる。アレイ優先順位が得られる後のサイクルで、許可
されると、ARR 130 への実際のオペランド記憶データ・
プットアウェイが実行される。これは通常、オペランド
記憶の終了を、記憶取出しと比較して少なくとも１計算
機サイクルだけ遅らせるが、全システム・パフォーマン
スに対する影響は、パイプライン及び記憶動作の種々の
重複により許容しうるものであることが分かった。本発
明のこの実施例では、予測されたキャッシュ・ラインに
オペランド記憶をプットアウェイできるときキャッシュ
・ラインのバックアップに関する複雑さを減らすために
も、このような据置き記憶方式を採用できる。据置きオ
ペランド記憶の実現はよく知られており、本発明との直
接の関連はない。

【００３７】前述の説明は、履歴テーブルSETLAT 140に
よりセット位置予測を高めるためのIBM/3090キャッシュ
設計に対する変更である。主な利点はキャッシュ・アク
セスクリテイカルパスのタイミングを短縮することであ
る。IBM/3090設計では、経路183 を介してアレイから読
み出された4個のダブルワードの１つは、CMP 161での比
較結果の受領後にのみ後選択できる。改良された設計で
は、本発明に従って、アレイからIE 110への経路 192を
介したデータ引渡しは、経路184上のセット予測SETLAT
[A]の結果を待つだけでよく、取出されたデータの確認
は代わりにIE装置で実行できる。適切な実現により、こ
のような変更は少なくとも１少ないレベルのMUX を生
じ、１少ないチップがキャッシュ取出しアクセスクリテ
イカルパスで交差することがよくある。一定の設計で
は、これはより長い計算機サイクル・タイムによらずに
１サイクル取出しアクセス・キャッシュの実現を可能に
する。

【００３８】前記新設計では、経路192を介してIE 110
に送られるデータは、経路183を介してARR 130から後選
択装置162に読み出されている４個のダブルワードから
後選択される。一定の設計では、４個のダブルワードの
読取りを回避できる。１つの実施例(図８)はセット位置
予測及びアレイ読取りを直列に行なう。図８で、セット
予測SETLAT[A]の結果は代わりに経路186を介してアレイ
読取り制御部に送られ、後選択装置162が除去される。
アレイ読取り制御部に入力されたSETLAT[A]により、予
測されたダブルワードだけが読取られ、経路194 を介し
てIE 110に直接送られる。アレイ読取り数の減少は一定
の設計にとって有利になることがある。この方法で１つ
の潜在的な問題は、SETLAT[A] を待つ間のアレイ読取り
の遅延である。ある設計では、キャッシュ・アクセス・
サイクルよりも早いサイクル (例えば、仮想アドレス生
成サイクル)でSETLAT[A]の読取りを実行できる。この場
合、前記問題は自動的に解消する。SETLAT予測がアレイ
読取りと同じ計算機サイクルにあるとき、図８の方法は
特注のアレイ設計による最適化することがなお可能であ
る。例えば、履歴テーブルSETLAT 140をキャッシュ・ア
レイ・チップ上に設けることができる。このように、ア
レイ・チップに埋め込まれた後選択の効果は最小の遅延
及び出力I/O 要求により達成できる。

【００３９】直接キャッシュ設計と比較して、本発明は
１よりも大きいセット連想性を可能にし、キャッシュ・
ヒット率をかなり高める。唯一の可能なタイミング差
は、直接写像キャッシュ方法が必要としない後選択装置
162 をこの新しい設計が必要とすることである。

【００４０】前述のMRU 方法の変更と比較して、前記新
設計はより早いセット予測をずっと高い精度で可能にす
る。前述のように、MRU キャッシュ・ラインの数は合同
クラスの数により制限される。その結果、MRU 設計は
(本発明が一層高い精度をもたらす大型のキャッシュを
除き) 十分に高い予測精度を達成できない。商用のワー
クロードに基づいたシミュレーション研究から、合同ク
ラスの数よりも多いエントリを有するSETLAT履歴テーブ
ルの使用によってもセット位置予測の精度がかなり高め
られることが判明した。例えば、IBM/3090の例で64KBキ
ャッシュについて考えてみる。全部で128合同クラスに
区分された512キャッシュ・ラインがある。SETLAT履歴
テーブルで512 のエントリが用いられたとき、セット位
置予測に関して99％よりも高い精度が全てのキャッシュ
・ヒットで達成された。これは間違った予測に関連した
不利点を事実上全て除去している。

【００４１】次に、本発明のより効率的な実現について
説明する。MRU 設計では、実アドレスに基づいたキャッ
シュが用いられる。即ち、 (IBM/3090の場合のような論
理アドレスによる代わりに) 関連した実アドレスにより
決定された合同クラスでのみキャッシュ・アクセスを満
足させうる。これは、当該合同クラス中のMRU ラインか
らのデータ読取りをアレイが開始できる前に、シノニム
関連実アドレス・ビットを知る必要がある。MRU方法
は、TLB合同クラス(TLBCONG[A])中のMRU エントリから
実アドレス・ビットを読取ることにより前記シノニム・
ビットを予測し、そして前記予測されたシノニム・ビッ
トとキャッシュ合同クラス選択の仮想アドレスA 150の
関連アドレス・ビットとを組合わせる。TLBからなにか
を読取る要求はクリテイカルパスのタイミングには重荷
である。最近の計算機ではTLBは大きく(例えば、128〜2
048エントリ)なりつつあるので、より高速の回路を実現
することは困難かつ高価である。また、一定の設計で
は、TLB ビットをキャッシュ・アレイ制御部に引渡すこ
とはチップ交差を必要とすることがある。本発明は仮想
アドレス・キャッシュの使用により前記負担を取り除
き、合同クラス選択前のシノニム・ビット決定を回避す
る。MRU 方法のもう１つの欠点は、セット位置予測が特
定の合同クラスのMRU情報に基づいている。その結果、T
LBの使用により合同クラスが決定されたのちにだけ、セ
ット位置を予測することができる。これは一定の設計に
ついてクリテイカルパスタイミングを最適化する際に問
題点を生じる。本発明によれば、SETLATは、実際のキャ
ッシュ構造を知らずに (論理的なアクセス・アドレス・
ビットにより) アクセスできる簡単な履歴テーブルであ
る。よって、論理アドレスによりSETLAT 140のエントリ
を直接選択することができ、MRU 設計方法と比較してよ
り効率的な実現をしばしば可能にする。

【００４２】本発明に関する前記説明では、シノニム状
態を検出する際に各可能なシノニム・キャッシュ・エン
トリとTLB 合同クラスから読み出された各実アドレスと
を突合わせるために多くの比較器の費用を負担してIBM/
3090方法が採用された。包含される比較器の数を予測情
報を用いて減らすことができる。例えば、アクセスのた
めの直接探索サイクルでは、使用する比較器を減らし、
TLB変換情報をPCCからのこれらの実ライン・アドレスと
だけ突合わせることができる。しかしながら、あるシノ
ニム・ヒットの場合、これは遅延(例えば、１サイクル)
を生じることがある。シノニム決定の最適化は本発明の
主要点ではないから、本実施例では更に詳細な説明は行
なわない。

【００４３】ミスした各キャッシュ・ラインが (論理的
なアクセス・アドレスにより決定された) 主合同クラス
に入れられる、IBM/3090設計に基づいたSETLAT予測を用
いるキャッシュ設計の実施例について説明したが、各DI
R エントリは実ライン・アドレスを記録する。既存のシ
ステム設計のうち、多くは純実ディレクトリ方法も採用
しており、ミスしたラインは実アドレスにより直接決定
された合同クラスに入れられる。このような純実ディレ
クトリの一定の実現に関する問題は、合同クラス選択の
時間遅延である。例えば、IE 110アクセスの実アドレス
を最初に決定し、そしてキャッシュ・アレイ・データ・
アクセスを実行する。しかしながら、このような実施例
は非常に長いキャッシュ・アクセスクリテイカルパスを
形成する。なぜなら、通常はTLB 索引及びキャッシュ・
アレイ・アクセスの動作はどちらも相対的に遅いからで
ある。

【００４４】次に、キャッシュ・アクセスクリテイカル
パスを短縮するために実アドレス変換の予測が用いられ
る、本発明のもう１つの実施例について説明する。SETL
ATの使用と同様に、仮想アドレス変換情報を予測するた
めに履歴テーブルTLBLATが使用可能である。これは関連
出願に詳細に記述されている。図９はこのような設計を
示す。これは図８の変形である。図８での参照番号に対
応する図９での参照番号は、一般に対応する図８の参照
番号に100 を加えたものである。図９には、TLBLAT 241
が付加されている。TLBLAT 241は１次元履歴テーブルで
ある。これは必ずしもSETLAT 240と同じエントリ数を持
たず、次元的にも合同クラスの数でもTLB 210 と対応し
ない。少なくとも、TLBLAT 241中の各エントリは、実ア
ドレス合同クラスの選択に必要とされる実ページ・アド
レス内のビットを含む。例えば、32ビット(0〜31)を有
する仮想アドレスA 250のアクセスの下に、256の合同ク
ラス及び128バイト／ラインを有するキャッシュについ
て考えてみる。下記で、A[m-n] (ここで 0≦m≦n≦31)
は仮想アドレスA 250のアドレス・ビットm-nを示す。a
[20-31]はページ境界内のページ・オフセットである。
これは変換による影響を受けない(即ち、仮想アドレス
は実アドレスに等しい)。ここで、データ・アクセスの
ために256合同クラスの１つを選択するライン・アドレ
スA[0-24]の８ビットが必要とされる。しかしながら、
もし合同クラスを選択するためにA[17-24]が取り上げら
れれば、３ビットA[17-19]を、３実アドレス・ビットの
８つの組合せのどれかに変換することができる。この実
施例では、各TLBLAT 241エントリは、過去のA[17-19]の
３ビット実変換の履歴を記録する３ビットを含む。例え
ば、64エントリを有するTLBLAT 241の場合、A[14-19]に
よりインデックスされたエントリ(TLBLAT[A]で示す)に
おける３ビットはA[17-19] の予測された実変換であ
る。この場合、TLBLAT[A]におけるこれらの３ビットはA
[20-24] と連結され、予測されたアクセスの256キャッ
シュ合同クラスの１つを選択する。

【００４５】次に、図９に示す実施例の仮想アドレスA
250 によるIE 110からのキャッシュ・アクセスの際の実
行の流れについて考える。最初に、図８に関して既に説
明した実行の流れに多くの類似性を有する下記の動作が
並行して行われる。 (1) TLB 210を読み出すためにA 250の適切なビットが経
路271を介してTLB 210に送られる。経路281を介して出
力が比較装置COMP 261に送られる。 (2) 実アドレス合同クラス選択の予測に関するTLBLAT
[A] の情報を選択するためにA 250の適切なビットが経
路277を介してTLBLAT 241の制御部に送られる。COMP 26
1、DIR 220及びARR 230の制御部にTLBLAT[A]の出力が送
られる。 (3) DIR 220及びARR 230の制御部にA 250の適切なビッ
ト(例えば、前記の例のA[20-24])が送られる。TLBLATの
出力ビットに連結された、 (ページ境界内の)これらの
アドレス・ビットが合同クラス選択の予測を決定する。
この合同クラス情報が使用可能なとき、下記の動作が実
行される。(a) 予測された合同クラスにおける４つのDI
Rエントリが経路282を介してCMP 261に読み出される。
(b) ARR 230から４つのダブルワードが読み出され、経
路283を介して後選択装置262に送られる。 (4) 経路274を介してA 250の適切なビットがSETLAT 240
の制御部に送られ、セット位置予測(SETLAT[A])が読み
出され、該予測の検査のために経路285を介してCMP 261
に送られる。

【００４６】経路284で受取ったセット位置予測に基づ
いて、後選択装置262 はARR 230からの経路283 で受取
ったダブルワードの１つを選択し、選択されたダブルワ
ードを前のように経路292を介して要求元IE 110に送
る。残された説明は、主にCMP 261で実行される、予測
されたアクセスの検査プロセスである。

【００４７】CMP 261 のロジックは下記の主要な機能を
実行する。これらの機能は最初の実施例(図７のバージ
ョン又は図８のバージョン)における機能に類似する
が、小さな変更を伴う。 (1) TLBヒット/ミス状態を検出し、TLBLAT[A] 予測を検
査する。IBM/3090設計の場合のような普通の比較器によ
りTLBヒット/ミス状態を決定できる。TLBLAT[A]予測の
検査はTLBLAT[A](例えば、３ビット)をこれらの改良さ
れた比較器に埋め込むことによって行われる。 (2) キャッシュ・ヒット/ミス状態を検出し、SETLAT[A]
予測を検査する。IBM/3090設計の場合に類似するがより
簡単な方法で (DIR 220からの実アドレスとTLBエントリ
から取出された実アドレスとを突合わせる) 対の比較器
によりキャッシュ・ヒット/ミス状態を決定することが
できる。 簡略化は、シノニム合同クラスを必要としな
い数まで所要比較器数を減少させることにより実現され
る。比較器ロジックの直截的な改良によりSETLAT[A] 予
測を検査することができる。前記２番目のステップで
は、DIR 220 に記録された実アドレス・ビットは間違っ
て予測された実アドレス合同クラスに基づいて時折間違
ったヒットを生じうることに注目されたい。経路292 を
介してIE 110に転送されたダブルワード・データは、CM
P 261 で検出される下記の条件が全て満たされるときに
のみ正しい。 ・TLB 210(例えば、TLBヒット) によりA 250の仮想ペー
ジ・アドレスがカバーされ、TLBLAT[A]予測が正しい。 ・予測された合同クラス内の予測されたセット位置でキ
ャッシュ・ヒットが検出される。これらの条件が満たさ
れると、CMP 261は確認信号ライン291に沿って正(C＝1)
の信号をIE 110に送り、さもなければ負(C＝0)の信号を
送る。最初の実施例と同様に、必要なときセット位置履
歴更新をSETLAT制御部に通知するためにSETLAT更新ライ
ン293 が用いられる。この二番目の実施例では、TLBLAT
241で履歴情報の更新を必要とする状況(例えば、TLBミ
ス又はTLBヒットの際の間違ったTLBLAT[A]予測)もあり
うる。そのために追加の信号経路294にTLBLAT更新が付
加される。最初の実施例と同様に、間違った予測により
経路292 に送られた間違ったデータ・アクセスにより、
後のサイクルで該要求を再びアクセスすることができ
る。

【００４８】SETLAT 240及びTLBLAT 241がともにA 250
の仮想アドレス・ビットに基づいてアクセスされるか
ら、各選択されたエントリでSETLAT[A]及びTLBLAT[A]の
両者を記録するためにこれらの２つの履歴テーブルを組
合せうることが明白である。一定の状況では、これは下
記の理由により望ましくないことがある。 ・シミュレーション研究から、SETLAT 240と比較して、
極めて高い精度の変換予測を達成するために相対的に少
ないエントリがTLBLAT 241に必要とされることが分かっ
た。その結果、これらの２つの履歴テーブルを分離する
ことにより回路を節約することが可能である。 ・多くの実施例では、TLBLAT 241アクセスのタイミング
要求はSETLATアクセスよりも臨界的なことがある。なぜ
なら、(TLBLAT[A]に基づいた後選択のため、又はCMP 26
1でより多くの比較器との直接の突合わせのために、特
定のDIRエントリよりも多くを読み出しえない限り)DIR
220のアクセスはTLBLAT 241の結果によるからである。
その結果、より高速の回路によるTLBLAT 241の実現を必
要とすることがある。その場合には、TLBLATのサイズを
最小にすることが望ましい。

【００４９】最初の実施例でSETLAT 140について説明し
たように、キャッシュ・ディレクトリ/アクセス・サイ
クルよりも早いサイクルでTLBLAT[A]を実行する特定の
実施例を選択できる。このような場合、それに応じてTL
BLAT 241アクセスのタイミング要求を緩和することがで
きる。同様に、実アドレス・アクセス・モードでは、CM
P 261でのアドレス比較中は経路281上のTLB情報を無視
することができる。

【００５０】前記説明で、TLBLAT 241が実アドレス合同
クラス選択の決定に必要なこれらのビット(例えば、256
合同クラスによる前述の例では３ビット) を各エントリ
に運ぶ最小限の要求が指定された。２番目の実施例の設
計(図９)は特定の実施例を最適化する際に他の柔軟性を
提供する。１つの例は代わりに全実ページ・アドレス履
歴を各TLBLAT 241に記録することである。即ち、TLBLAT
[A]はTLBLAT 241 の特定のエントリに関連したTLB 変換
の実ページ・アドレスを包含できる。この改良により、
費用効果のよい実施例が可能になる。図１０はこのよう
な設計変更を示す。

【００５１】図１０は図９を変更し、CMP 261を２つの
部分、CMPa 261a及びCMPb 261b に分割する。CMPa 261a
はTLB ヒット/ミス状態の検出及びTLBLAT 241における
履歴の修正を処理する。CMPb 261bはDIR探索及びSETLAT
240における履歴の修正を処理する。 (1) CMPa 261aはTLB 210からの入力ライン281及び経路2
11からA 250の(IBM/3090アーキテクチャのSTOを含む)仮
想ページ・アドレス情報を取込む。これらの入力によ
り、CMPa 261aは仮想アドレスがTLB 210をヒットするか
どうか、及びそれがヒットするときTLB 210 のどのエン
トリであるかを判定できる。更に、そのエントリの各々
がTLBLAT 241内の対応するエントリ(TLBLAT[A]) に記憶
された実アドレスを有するかどうかを示す情報により、
TLB 210 が改良されるものと仮定する。前記改良された
情報により、TLBヒットの際に、CMPa 261aはTLBLAT[A]
がA 250の実ページ・アドレスを含むかどうかを判定で
きる。もしそうなら、CMPa 261a は経路295でANDゲート
261cに正の信号(例えば、１ビットT＝1)を出力し、さも
なければ、負の信号(例えば、１ビットT＝0)を出力す
る。TLBLAT 241により間違った予測が検出される場合
は、履歴更新のために正しいTLBLAT[A] の値がTLBLAT更
新ライン294 に沿って送られる。 (2) CMPb 261bは、キャッシュ・ディレクトリから経路2
82に読み出された該選択された合同クラスの実ライン・
アドレスと、(TLBLAT 241から経路288で実ページ・アド
レス予測とページ境界内の未指定の入力アドレス・ビッ
トとの連結により形成された)要求A 250 の予測された
実アドレスとを比較する。経路285で予測されたセット
位置SETLAT[A]で一致が起きると、正の信号(例えば、１
ビットD＝1)が経路296でANDゲート261cに送られ、さも
なければ、負の信号(例えば、１ビットD＝0)が送られ
る。もしSETLAT 240から受取った該予測されたSETLAT
[A]以外のセット位置とのアドレス一致が起きれば、SET
LAT更新ライン293に沿ってSETLAT[A]の修正が通知され
る。(TLBLAT[A]予測が失敗するときのSETLAT[A] の修正
は任意の設計であることに注目されたい。) (3) ANDゲート261cは(例えば、受取ったT及びDビットを
ANDすることにより)CMPa 261a及びCMPb 261bからの結果
を組合わせ、適切な確認信号(例えば、C＝T&D)をIE 110
に送る。 (4) TLBLAT[A]予測に基づいてARR 230がアクセスされ、
経路292で後選択装置262からIE 110にダブルワードが送
られる。前記変更により、CMPa 261a及びCMPb 261bが明
確に結論づ付けられるときにだけIE 110 により経路292
で受取られたダブルワード・データが明確に確認され
る。この方法の１つの可能な利点は、比較のためにTLB
210及びDIR 220の両者からのデータを直接組合わせるこ
とを回避することである。これは、より容易に物理的に
分割される設計を可能にすることができる。

【００５２】前記説明で、TLBLAT 241に対応する領域を
エントリが有するかどうかを識別するTLB 210 の一定の
タグ方式が仮定されている。これは種々の方法で達成で
きる。TLB 210のサブセットとしてTLBLAT 241 が維持さ
れる設計例について考えてみる。各TLB 210エントリはT
LBLAT 241でその領域を示す特別のビットLにより改良で
きる。仮想ページ・エントリが(例えば、古いエントリ
の置換を介して)最初にTLB 210に生成されると、関連し
たLビットがオフ(0に)なる。LビットはTLBLAT 241で更
新されるとオン(1に) なる。しかしながら、古い値をセ
ットするエントリと異なるTLB エントリによりTLBLATエ
ントリが更新される可能性がなおある。よって、TLBLAT
241エントリが更新される毎に、予め前記値をセットし
たTLB エントリでLビットをオフにする必要がある。 こ
の手順は本明細書では詳細に説明されない種々の簡単な
TLB/TLBLATエントリ選択アルゴリズムにより容易にする
ことができる。

【００５３】最初の実施例で説明したように、CMPa 261
a及びCMPb 261bに必要な比較器を種々の方法で減少でき
る。例えば、CMPb 261b は１つの比較器を用いて予測セ
ット位置SETLAT[A] のライン・エントリの実アドレスを
検査できる。しかしながら、大部分の実施例では、これ
は大きな価値をもたらしえない。その理由は、選択され
た合同クラスの複数のDIR エントリの探索は間違ったセ
ット予測による遅延を減らし(即ち、TLBLATが正しく予
測するとき)、キャッシュ・ミス状態を迅速に解決する
見込みが大きいからである。

【００５４】図１０の設計に関する更にもう１つの可能
な改良は、 (IBM/3090アーキテクチャのSTOを含む)TLBL
ATエントリに仮想アドレス情報を含むことである。この
ように、TLBLAT 241は、通常のTLB 210 のサブセットと
して維持できる、１次元の全機能変換テーブルとなる。
図１１はこのような全機能TLBLAT 241を用いる図１０の
変形を示す。

【００５５】図１１で、CMPa 261aは、より大きいTLB 2
10からの代わりに、TLBLAT 241から変換情報を直接取込
む。ここでは、TLB 210は必要なとき(別個の比較装置26
3 からライン298を介して)TLBLAT 241に変換情報を供給
するためにのみ動作する。アクセス毎にTLB探索を直接
呼出すか又はTLBLATのミスのときのみTLB探索を呼出す
かは設計上の選択である。

【００５６】２番目の実施例(図９〜図１１)で用いられ
たTLBLAT 241が適切な時点で所要の仮想アドレス変換情
報の決定に用いられることに注目されたい。前記TLBLAT
241の機能はむしろそれ自身で独立しており、関連出願
記載のように、セット位置を予測するためにSETLAT 240
のない設計で使用可能である。

【００５７】前記実施例では、取出し(読取り)アクセス
記憶要求が詳細に検討されている。IE装置からのオペラ
ンド記憶(書込み)要求は従来の据置き記憶方法を用いる
ものと仮定されている。提案された予測方式はキャッシ
ュへの効率的な書込みを提供するためにも使用可能であ
る。予測に基づいたキャッシュ書込みで生じる１つの複
雑さは、間違った記憶位置(本発明ではキャッシュ・エ
ントリ)にデータがプットアウェイされるとき記憶の完
全性をいかに維持するかである。この状況がストアスル
ー(store-thru)・キャッシュ設計でいかに管理されるか
について以下に説明する。

【００５８】ストアスルーは周知の形式のキャッシュ設
計であり、多くの市販の製品 (例えば、IBM/3033システ
ム) で実用化されている。ストアスルー・キャッシュに
より、キャッシュ・アレイへの各書込みは下位記憶階層
(例えば、２番目のレベルのキャッシュ又は主記憶装
置) へも送られる。その結果、上位レベルのキャッシュ
階層のラインが間違って書込まれるときでもなお、下位
レベルの記憶階層からの最新(up-to-date)コピーを介し
て記憶の一貫性を維持できる。典型的なストアスルー設
計では、記憶されたデータは実アドレスにより (即ち、
仮想アドレスからの変換後に) 下位レベルの記憶階層に
送られる。よって、ストアスルーに指定されたアドレス
が正しい限り(例えば、TLBLAT予測の不確実性なしに)、
下位レベルの記憶階層はあいまいさなしに記憶更新を実
行する。よって、提案された予測方式がキャッシュ・ア
レイへの即時データ記憶に (即ち、据置き記憶方法での
ような事前検査なしに) 用いられると、(間違った予測
による)間違ったアレイ・プットアウェイは関連ライン
を取り除く(無効化する)ことにより容易に回復可能であ
る。オペランド記憶は正しいキャッシュ・ラインに書込
まれるまで再開始可能である。しかしながら、もし取り
除かれたラインが近い将来に再アクセスされるならば、
この簡単な方法は(下位レベルの記憶階層への)余分なキ
ャッシュ・ミス取出しを生じることがある。シミュレー
ション研究から、非常に高い精度のオペランド記憶が(S
ETLAT及びTLBLAT予測から)観察されている。これは、プ
ログラムが１個のデータを最初の読取り後に書込む傾向
にあるソフトウェアの特性によるものであり、よって前
記先行読取り(取出し)は通常不正確さを取込んでおり、
履歴を正しく更新している。その結果、前記余分なミス
による全性能に及ぼす不利点は割に小さい。

【００５９】多くの既存の(ストアイン(store-in))キャ
ッシュ設計では、ストアスルー方法は採用されていな
い。即ち、キャッシュへのデータ書込みは下位記憶階層
の更新によるバックアップがなされていない。前記設計
では、間違った予測により間違って記憶されたキャッシ
ュ・ラインは復元されなくてもよい。例えば、もし間違
って変更されたラインが最後の更新の前に(キャッシュ
内で)変更されなかったならば、それは単にストアスル
ー設計の場合のように単に取り除かれる。なぜなら、変
更されないコピーは下位レベルの記憶階層から回復しう
るからである。他方、もし間違って書込まれたライン
が、下位レベルの記憶階層にはまだ反映されいてない、
以前の変更を保持しているならば、該ラインは特別の支
援を介して復元される必要がある。前記特別のデータ回
復機構はJ.G Brenzaによる米国特許第4905141号に記述
されている。

【００６０】前述の実施例において提案されたキャッシ
ュ・アクセス予測機構の１つの特別な利点は、各IE装置
アクセス要求に関連したアレイ・チップI/O の減少であ
る。例えば、IE装置による各アクセスは、従来の後選択
方式による遅延なしに、アクセスするキャッシュ・アレ
イからよりタイミングよく選択することができる。図７
及び図９乃至図１１に示された後選択機構は、ディレク
トリ/TLB探索の結果を待つ必要なしに、適切なSETLAT実
施例により迅速に実行できる。更に、最初の実施例で説
明したように、もしSETLATからのセット位置の予測を早
いタイミングで(例えば、より早いサイクルで又は特注
のアレイ・チップにより)達成できるならば、アレイか
らのデータの後選択を完全に回避できる。この場合に、
個々のアクセス要求毎にキャッシュ・アレイから最小１
データ単位(例えば、ダブルワード)を読み出す必要があ
る。同様に、該利点はIE装置からの個々の記憶アクセス
要求毎にキャッシュ・ディレクトリ及びTLB エントリの
読取りの減少を示している。データ及びディレクトリ読
取りの前記最少化は、資源競合が以前から深刻な問題に
なっている、計算機サイクル毎の複数のアクセス要求を
有するキャッシュを実現する特別な利点を提供する。

【００６１】典型的なセット連想キャッシュ設計では、
同時読取りがサポートされるようにセット連想性により
データ・アレイが区画される。図１２は後選択原理を用
いた４ウェイ・セット連想キャッシュに関する前記区画
方式の１つを示す。データ・アレイ・ビットが４グルー
プ320A〜320Dに区画され、各グループは特定のセットA
〜Dのアレイ・データをカバーする。ダブルワード読取
りアクセス中、 (同じダブルワードのアドレス・ビット
を含む) 読取り制御信号310A〜310Dは、最初に並列に４
つのアレイ区画320A〜320Dから対応する４つのダブルワ
ードを読み出させる。340A〜340DのAND ゲートは４つの
ダブルワードのデータとそれぞれの後選択信号330A〜33
0D(多くても１つが値1を有する)との論理積(AND)を実行
する。もし対応するセットが選択されなければ、ANDゲ
ート340A〜340Dの各々は全0ビットを有するダブルワー
ド出力を生成する。選択されたAND ゲートは、キャッシ
ュ・アレイに記憶された正確なダブルワードを出力す
る。340A〜340Dの全ての出力はロジック装置350 でビッ
ト単位の論理和(OR)により互いに組合わされる。よっ
て、もしセットが(例えば、キャッシュ・ヒットにより)
後選択されていれば、ロジック装置350からの出力は、
アレイに記憶された所望のダブルワードである。(アレ
イへの書込みの制御はよく知られているので、詳細な説
明は行なわない。) この例は明らかに後選択によるアレ
イI/O のオーバーヘッドを示す。なぜなら、少なくとも
3/4 のデータ読取りが無駄になるからである。代わり
に、４つの独立した同時キャッシュ・アクセスまでサポ
ートするアレイ区画のI/O を利用できることが非常に望
ましい。

【００６２】前記米国特許第4905141 号は、図１２で説
明した従来のセット連想区画構成への複数の独立したキ
ャッシュ・アクセスを実行する。図１３はアレイ部分の
このような構成を示す。ここで、後選択信号が除去され
る。Brenzaは、 (IBM/3090の場合のように) キャッシュ
合同クラス選択が論理的なアドレスに基づいているキャ
ッシュで独立したIE装置記憶アクセスのセットを正確に
決定するPLAT (区画ルックアサイド・テーブル) を用い
る。各PLATは小さな論理アドレス・ディレクトリであ
り、所与の論理アドレスで、ライン・アドレスの一致を
見出だそうと試みる。PLATがヒットすると、関連したエ
ントリは、ダブルワード読み出しのライン要求を(例え
ば、アレイ区画420Aに関して、ライン410Aを介して)入
力すべきキャッシュ・セットを識別する。PLATミス状態
は、PLATで新たなエントリを初期化するためにキャッシ
ュ・ディレクトリに照会することにより解決される。複
数の独立したアクセスが(例えば、異なるIE装置から)同
時に同じアレイ区画での衝突を起こすことがある。この
場合、一定の優先順位ロジックがそれらの１つに該アレ
イ区画をアクセスする権利を与え、他のアクセスは後の
サイクルまで遅延される。この提案での１つの欠点はキ
ャッシュ・アクセスのセットを(正確に)決定するために
PLATでの比較を必要とすることである。これは多くの実
施例のクリテイカルパスでのタイミングに重荷を課す
る。一定の設計でPLATを実現することによる別の不利点
はPLATが全論理アドレス(例えば、アドレス・ビット及
びSTO) を保持することであり、PLATに高速回路を利用
することを困難又は高価なものにする。また、所要数の
回路のために、より多くのライン・エントリ数をPLATに
維持することは、更に高価なものになる。これはPLATの
ヒット率を望ましくない値に制限することがある。

【００６３】図１３に示すようにアレイがセットで区画
されるとき、複数のアクセス・キャッシュをずっと効率
的に実現するために、本発明の予測テーブルSETLATを利
用することができる。ここで、キャッシュ・アクセス要
求を独自に出しうる各IE装置は、PLAT比較による正確な
結果を要求する代わりにセット(例えば、区画)を正確に
予測するために、簡単なSETLAT(例えば、コピー)を用い
る。この方法により、各入力410A〜410Dは関連区画のヒ
ットが予測されるアレイ・アクセス要求を保持する。前
記Brenzaの特許の場合のように、同じアレイ区画に対す
る同時アクセスの衝突に適切な優先順位を付与すること
ができる。

【００６４】複数のアクセスをサポートするためにキャ
ッシュ・アレイを区画する種々の他の方法がある。１つ
の方法は、アドレス・ビットによりアレイを区画するこ
とであり、その周知の例はインターリービングである。
例えば、ダブルワード細分性での４ウェイ・インターリ
ーブ・キャッシュについて考えてみる(図１４)。32ビッ
ト・アクセス・アドレス毎に、４つのインターリーブ区
画520〜523の１つがアドレス・ビット27〜28により決定
される (ビット29〜31はダブルワード境界内にある)。
キャッシュ・ライン・サイズがダブルワードよりも小さ
い(これはかなり起こりにくい) 限り、ビット27〜28も
ページ境界内にあるのでアドレス変換による影響を少し
も受けないから、インターリーブ区画の選択は正確であ
ることが明白である。図１４は２つの独立した要求元装
置ｘ及びｙからのキャッシュ・アクセスを示す。優先順
位指定装置530はアレイ区画のアクセスを指名(dispatc
h) する責任がある。切換え装置570 は要求元装置にダ
ブルワードの結果を返送する。ここで、８ウェイ・セッ
ト連想キャッシュ (これはインターリーブされた４ウェ
イ・ダブルワードでもある) の実現について考えてみ
る。もし従来の後選択方法が用いられれば、各インター
リーブ区画520〜523を、区画内の８ダブルワード読取り
／サイクルをサポートするために更に区画することが必
要になる。その結果、任意のサイクルで全キャッシュ・
アレイから32ダブルワードを読取りできることが要求さ
れる。このような過剰なキャッシュ・アレイI/O 要求
は、各インターリーブ区画内のデータ読取りの量を制限
することにより、かなり減少させることができる。その
ために、SETLATを用いてセット位置を予測する手法を用
いうることは明らかである。例えば、要求元装置ｘは、
ダブルワード・アドレス・ビットに加えて、予測された
セット位置を経路510xを介して優先順位指定装置530 に
送る。各インターリーブ区画520〜523内で、入力された
セット位置の予測に基づいて１つのダブルワードがライ
ン560〜563に読み出される。 (タイミングが可能な一定
の設計環境では、インターリーブ区画520〜523自身内で
セット位置の予測を確実に実行することができる。)

【００６５】インターリーブされるキャッシュに関連し
た従来の１つの問題はディレクトリ探索の競合である。
例えば、図１４に示す４ウェイ・ダブルワードのインタ
ーリーブ・キャッシュでは、全て別の区画520〜523に対
する４つの同時アクセスがありうる。これは同じキャッ
シュ合同クラス又は同じキャッシュ・ラインとさえも衝
突する。その結果、独立した要求の間のディレクトリ競
合を複数のディレクトリ・コピー又は他の手段により解
決する必要がある。前記ディレクトリ競合を回避する１
つの可能な方法はキャッシュ・ラインの細粒でアレイを
区画することである。例えば、128 バイト・キャッシュ
・ラインでは、２つのアドレス・ビット23〜24をアレイ
区画の選択に使用できる (アドレス・ビット25〜31は該
ラインの境界内にある)。 この区画方式により、キャッ
シュ・ディレクトリ自身は対応しして、各々がアレイ区
画のアクセスに役立つ４つの区画に区画可能である。前
記ラインに基づいたキャッシュ区画により、SETLAT履歴
テーブルも一定の実施例で区画可能である。SETLATに1K
のエントリを有する設計を考えてみる。所与の論理アド
レスについて、SETLAT内のエントリを選択するためにビ
ット15〜24が用いられるが、アレイ区画を選択するため
にビット23〜24が用いられる。よって、SETLAT履歴エン
トリは異なるアレイ区画のアクセスのために互いに分離
される。

【００６６】本実施例では、アドレス情報を介して予測
テーブル・エントリの選択が行なわれる。典型的な設計
では、前記選択は下位アドレス・ビットによる索引によ
る。例えば２番目の実施例で256 合同クラスによるキャ
ッシュ例を考えてみる。一般に、アクセスのキャッシュ
合同クラス選択は８アドレス・ビット17〜24 (ライン・
アドレスの下位ビット) により決定される。同様に、10
24エントリを有するSETLATの索引は10アドレス・ビット
15〜24により決定される。より上位のアドレス・ビット
を有するキャッシュ合同クラス又は他の情報 (例えば、
IBM/3090アーキテクチャにおけるSTO識別)の選択をラン
ダム化する提案もなされている。前記ランダム化の利点
は、幾つかの合同クラスの激しい衝突による変則動作を
回避することである。前記ランダム化方法は、適切なと
き、(TLBLAT又はSETLATからの)履歴エントリの選択にも
適用可能である。

【００６７】前述の実施例では、各履歴テーブル(TLBLA
T又はSETLAT)の１つのコピーが図示されたけれども、実
施例にとって有利とみなされるとき前記テーブルはいつ
でも反復可能である。

【００６８】該実施例では、キャッシュ・アレイ読取り
を、アクセスのために予測されたセット位置に基づいた
セット位置にのみ、いかに制限するかに関する方法が説
明されている。前記予測情報はキャッシュ・ディレクト
リの読取りの制限にも採用しうることは明白である。セ
ット位置の予測の妥当性を検査するために、キャッシュ
・ディレクトリ内の対応する１つのエントリの読取りの
みを必要とすることがよくある。しかしながら、キャッ
シュ・ミス状態のより早い解決のために、大部分の実施
例は、従来のセット連想キャッシュ設計の場合のよう
に、関連した合同クラス内の全てのディレクトリ・エン
トリから読取るように選択できる。

【００６９】前述の実施例では、１つのキャッシュがプ
ロセッサとみなされたけれども、予測手法は明らかに種
々の他のタイプのプロセッサ・キャッシュ構成に適用可
能である。例えば、多くの設計では、プロセッサ毎にI/
D 分割キャッシュが用いられる。即ち、(Ｉ装置からの)
命令コードのアクセス及びオペランドのアクセスのため
に別個のＩキャッシュ及びＤキャッシュがそれぞれプロ
セッサで用いられる。たぶん異なる組合せを有する予測
機構をＩキャッシュ及びＤキャッシュへのアクセスに別
個に用いることができる。

【００７０】前述の実施例では、SETLAT内の各エントリ
は２ビットを用いて４ウェイ・セット連想キャッシュに
セット位置履歴を記録する。前記履歴情報を記録する方
法は任意の特定の実施例の都合による。例えば、設計に
よっては、(セット位置を)符号化及び復号する際の遅延
を減らすためにセット位置履歴を記録する (多くても１
ビットがオンの) ４ビットの使用を選択できる。

【００７１】コンピュータ設計では、(例えば、α粒子
損傷による)記憶された情報のエラーの検出及び修正の
ためのパリティ及びエラー修正ビットがよく用いられ
る。本発明の多くの実施例の履歴テーブルに関する前記
保護のための固有の要求はない。履歴情報はいつでも使
用の際に正確さを直ちに検査される。しかしながら、一
般にエラー検出及び(又は)修正能力は発明にとってRAS
(信頼性、可用度及びサービサビリティ)を高めるために
望ましい。

【００７２】実施例ではキャッシュ・アクセスのための
１つのライン・エントリのアクセスを予測する方法を示
しているけれども、提案された手法は、所望のとき、複
数のライン・エントリを予測するように一般化できるこ
とが明白である。例えば、図示のような４ウェイ・セッ
ト連想キャッシュを考えてみる。２ビット／エントリを
有するSETLATは毎回１つのセット位置を予測できる。も
し１ビット／エントリを有する類似のSETLATが用いられ
れば、アクセスのための合同クラスの半分 (２ライン・
エントリ) を予測することができる。複数のライン・エ
ントリの一回の前記予測は、一定の実施例での精度の向
上及び(又は)SETLATサイズの小型化のために有利になり
うる。

【００７３】本発明は前記実施例におけるプロセッサ・
キャッシュに関して説明しているけれども、提案された
手法は明らかに他の記憶階層設計に適用できる。例え
ば、２番目のレベルのキャッシュの設計を考えてみる。
通常、これは (例えば、最初のレベルのキャッシュ・ミ
ス又は更新から、ないしはI/Oチャネルから要求された)
実アドレスによりアクセスされる。(SETLATを用いる)セ
ット位置予測方式は前記２番目のレベルのキャッシュで
の高速データ・アクセスにも使用可能である。

【図面の簡単な説明】

【図１】典型的なキャッシュの２次元構造を示すブロッ
ク図である。

【図２】TLB 及びキャッシュ・ディレクトリ・エントリ
の読取り、アドレス比較、アレイ・データ読取り、及び
データの後選択の動作を示す従来の技術の方法のブロッ
ク図である。

【図３】IBM/3090キャッシュ設計を示すブロック図であ
る。

【図４】直接写像キャッシュ設計を示すブロック図であ
る。

【図５】MRUキャッシュ設計を示すブロック図である。

【図６】実施例で考慮された高レベル・システム構成を
示すブロック図である。

【図７】本発明に従ってセット位置を予測するためにSE
TLAT履歴テーブルを付加することによりIBM/3090キャッ
シュ設計の変更を示すブロック図である。

【図８】セット位置の予測がキャッシュ・アレイ読取り
に先行する設計を示すブロック図である。

【図９】合同クラス選択を高速決定するために本発明に
従って簡単なTLBLAT履歴テーブルを付加された実アドレ
ス・キャッシュ設計を示すブロック図である。

【図１０】全実ページ・アドレス・ビットにより改良さ
れたTLBLATによる図９の設計に対する変更を示すブロッ
ク図である。

【図１１】全仮想アドレス変換能力により更に改良され
たTLBLATによる図１０の設計に対する変更を示すブロッ
ク図である。

【図１２】従来の後選択キャッシュ・アクセス構造を示
すブロック図である。

【図１３】分割されたキャッシュ構造を示すブロック図
である。

【図１４】本発明に従って分割されたキャッシュ構造を
示すブロック図である。

【符号の説明】

60 キャッシュ装置 70 SC(記憶制御装置) 80 MS(主記憶装置) 90 I/Oチャネル 110 IE(命令及び実行)装置／TLB(変換ルックアサ
イド・バッファ) 120 DIR(キャッシュ・ディレクトリ) 130 ARR(キャッシュ・メモリ・データ・アレイ) 140 SETLAT(履歴テーブル) 150 仮想アドレスA 161 COMP(アドレス比較装置) 162 後選択(late-select)装置 210 TLB 220 DIR 230 ARR 240 SETLAT 241 TLBLAT 250 仮想アドレスA 261 COMP 262 後選択装置 261a CMPa 261b CMPb 261c ANDゲート 263 比較装置 320A アレイ区画 320B アレイ区画 320C アレイ区画 320D アレイ区画 340A ANDゲート 340B ANDゲート 340C ANDゲート 340D ANDゲート 350 ロジック装置 420A アレイ区画 420B アレイ区画 420C アレイ区画 420D アレイ区画 520 インターリーブ区画 521 インターリーブ区画 522 インターリーブ区画 523 インターリーブ区画 530 優先順位指定装置 570 切換え装置

Claims (3)

【特許請求の範囲】
1. 【請求項１】セット連想テーブルに記憶されることがあ
   る所望のデータのセット位置を予測する装置であって、 前記セット連想テーブルに対するアクセスのセット位置
   の最新の値を記憶する履歴テーブルであって、該記憶す
   る位置が、前記アクセスに関連した論理アドレス中の所
   定のアドレス・ビットのサブセットの値により決定され
   た前記履歴テーブル中の位置であることと、 前記履歴テーブルをアクセスし、かつ所望のデータの論
   理アドレス中のアドレス・ビットのサブセットの値に関
   連づけられている前記履歴テーブル中の場所にある該記
   憶されたセット位置の最新の値を検索することにより、
   前記論理アドレスを有する前記所望のデータの前記セッ
   ト位置を予測する手段とを含み、 前記予測されたセット位置は前記検索されたセット位置
   であることを特徴とする、 データのセット位置の予測装置。
2. 【請求項２】前記セット連想テーブルは実アドレスに基
   づいたキャッシュ・メモリである請求項１のデータのセ
   ット位置の予測装置。
3. 【請求項３】前記履歴テーブルは１つのサイクルで複数
   のロケーションに対する前記セット連想テーブルへの並
   列アクセスのための複数のセット位置を予測するために
   用いられる請求項１のセット連想テーブルに記憶される
   ことがある所望のデータのセット位置を予測する装置。