データのセット位置の予測装置
【目的】キャッシュ内のデータセット位置の予測機構であって、キャッシュアクセスパスの効率化のみならず、一サイクル当たりの複数のアクセスを可能とするもの。
【構成】キャッシュ制御装置がキャッシュアクセスの目的で、合同クラス内のライン入力の予測のため履歴テーブルＳＥＴＬＡＴを維持する。あるキャッシュアクセスに対してＳＥＴＬＡＴのエントリが、その要求に係わる論理アドレスビットに直接に基づいて選択される。また、ＳＥＴＬＡＴエントリの選出は、他の情報とともにそのような論理ビットのハッシングに基づいても可能である。また、同時に類似のハッシング履歴テーブルが形成され、高精度の仮想アドレス変換予測を可能にする．
【構成】キャッシュ制御装置がキャッシュアクセスの目的で、合同クラス内のライン入力の予測のため履歴テーブルＳＥＴＬＡＴを維持する。あるキャッシュアクセスに対してＳＥＴＬＡＴのエントリが、その要求に係わる論理アドレスビットに直接に基づいて選択される。また、ＳＥＴＬＡＴエントリの選出は、他の情報とともにそのような論理ビットのハッシングに基づいても可能である。また、同時に類似のハッシング履歴テーブルが形成され、高精度の仮想アドレス変換予測を可能にする．
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は一般にコンピュータ・システムのセット連想(set associative) キャッシュ、より詳しくはアクセスのための合同(congruence)クラスのセット数を決定する方式に関する。
【０００２】
【従来の技術】コンピュータ・システムで性能向上のためにキャッシュを使用することはよく知られており広く利用されている。キャッシュは最近に用いられたメモリ・データを保持する高速バッファである。プログラムの参照の局所性(locality of reference nature)により、大部分のデータのアクセスはキャッシュ内で行われ、大容量メモリに対する低速のアクセスを回避できる。
【０００３】典型的な高性能プロセッサの設計では、キャッシュ・アクセス経路はクリテイカルパス(critical path) を形成する。すなわち、いかに速いキャッシュ・アクセスを実行できるかにより、プロセッサのサイクル・タイムが決定される。
【０００４】キャッシュは論理的にはデータ・ブロック又はデータ・ライン(line)とみなすことができ、キャッシュ・テーブル・エントリはメモリ・データの特定のブロック又はラインをカバーする。 (以下、キャッシュの記憶装置はブロックよりはむしろラインと呼ばれる。) キャッシュの実現は通常は３つの主要部分:ディレクトリ、アレイ及び制御部分によって達成される。ディレクトリはキャッシュ・ライン・エントリのアドレス識別子のほか、特定の実施例に適した所要の状況タグを含む。(本明細書でときにはキャッシュ・メモリと呼ばれる)アレイは、実際のデータ・ビット、及び特定の実施例に要求されるようなパリティ検査すなわちエラー修正のための追加ビットを記憶する。制御回路はキャッシュ内容及びアクセスの管理に必要なロジックを提供する。キャッシュにアクセスする際、要求されたデータ・ラインの所在位置を識別するためにディレクトリが索引(look 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変換を行なう必要がある。大部分の最近の設計では、TLB索引はキャッシュ・ディレクトリ探索と並行して実行され、その結果はアレイ・データの最終的な後選択と組合わされる。図２はこのような設計を示す。キャッシュ・アクセスを決定するための複数のディレクトリ探索に関する前記要求は多くのキャッシュ設計の最適化を複雑にする原因になっている。前記複雑さは全て、プロセッサが記憶装置アクセス要求を出すとき、従来のディレクトリ索引の結果を知らずには、データの正確なロケーションをキャッシュ・アレイが決定できないので信号遅延を生じることに起因する。あいにく、種々の構成上の理由及び計算機装置上の理由により、データ・アクセスのための前記正確なロケーションを容易に得ることができない。従来の後選択機構の副作用は、１つのデータ単位を選択するために複数のデータ単位を検索するので、プロセッサ使用されなかったデータ単位のアレイ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 System/370," Proc. 14th Symposium on Computer Architecture, 1987, pp. 208-213 のMRU キャッシュ設計である。キャッシュ置換は通常は合同クラス毎に管理される。各合同クラス内には、適切な置換状況タグで示されたような最後に使用された(MRU = most recently used)エントリ及び最長時間未使用(LRU = least recently used)エントリがある。プログラム局所性によりキャッシュ・アクセスは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エントリの選択は、前記論理アドレス・ビットと他の情報とのハッシング(hashing) に基づくこともできる。同様のハッシング履歴テーブルが仮想アドレス変換情報を高精度で予測するために考案されることもある。これは関連出願に詳細に記述されている。前記予測機構はキャッシュ・アクセス経路の効率的な実現を可能にするだけではなく、複数アクセス／サイクルを達成する可能性も提供する。
【００２１】提案された予測方法は種々のディレクトリに基づいたテーブル・アクセスのための効率的な実現に関する一般的な方法も提供する。
【００２２】より詳しくは、セット連想キャッシュにおいて所与のアクセスのデータ・ロケーションを予測するアレイ制御の機構が開示される。予測が正しいとき、パフォーマンスはロケーションが既知の場合と同じである。間違った予測の場合は、データ・アクセスは打切られ、適切な予測が再度行なわれる。高精度の予測機構により、キャッシュのデータ・アクセスは間違った予測の最小のオーバーヘッドにより最適化させることができる。
【００２３】
【実施例】図６は、本発明を用いうるタイプのシステム構造のブロック図を示す。プロセッサは命令及び実行(IE)装置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 161に引渡される。
(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 はSETLAT更新ラインである。後に説明するように、このラインは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に沿って引渡された TLBCONG[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 ミス状態の変換プロセスの詳細な説明は行なわない。通常の手順によって所望の変換情報がTLBCONG[A]の置換エントリにロードされるものと仮定する。しかしながら、いったんTLB ミス状態が消失すれば、キャッシュ装置60は、前述のように、(一定のレジスタ又はスタックに記憶されている) 仮想アドレスA 150の待ちアクセスを再開始できるものと仮定する。
【００３０】キャッシュ・ミス状態は最初に該ラインがMS 80 から取出されることを必要とする。ライン取出しプロセスはIBM/3090記憶設計に類似するものと仮定する。キャッシュ装置60はSC 70にライン・ミス取出し要求を出す。SC 70は適切な時点でMS 80からキャッシュ装置60へのライン取出しをスケジュール(schedule) する。IBM/3090設計のように、新たに取出されたラインは、 (変換後の実アドレス・ビットによる代わりに)仮想アドレスA 150により決定された主合同クラス CONG[A]内(の前記置換エントリ)に入れられる。新たに取出されたライン・エントリの位置を、予測されたSETLAT[A] 履歴によって正しく反映できないことが明白である。履歴の調整は後に説明する。
【００３１】ここで詳細に説明する１つの事項は、キャッシュ・ミスのときIE 110に対してより迅速に応答するために用いられている従来のミス・バイパス (miss bypass)機構である。キャッシュ・ライン・サイズ(例えば、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の制御部に送る。SETLAT 140の制御ロジックは、ライン193 から受取った情報を用いて、ダブルワードの次の再アクセスを(例えば、次のサイクルで)指示されたセット位置から正しく取出し、それに従って履歴SETLAT[A] を更新する。履歴更新動作の詳細は後に説明する。間違ったセット予測の場合には、正しいダブルワード・データがARR 130から経路183に読み出されており、通常のアクセスについて説明したように (例えば、次のサイクルで)再読取りせずに、経路184を介して受取った正しいセット位置により直接選択できる。しかしながら、提案された機構を用いる大部分のプロセッサ設計では、ARR 読取りがクリテイカルパスタイミングに既に組込まれている。その結果、大部分の設計では、この場合に既に読み出されたデータの後選択に関する特別なケースとして制御ロジックを複雑にする必要はない。
【００３３】次に、間違ったデータ・アクセスのシノニム・ヒット状態について説明する。この場合、CMP 161は、アクセスされたダブルワードが主合同クラスCONG[A]と異なるシノニム合同クラスをヒットすることを検出する。更に、CMP 161 は目標ラインの正確なセット位置が関連シノニム合同クラスであることを見出だす。発見されたセット位置はSETLAT更新ライン193 を介してSETLAT 140の制御部に送られてSETLAT[A] が更新され、間違ったセット予測状態の場合と全く同様に (後の再アクセスのとき) 正しい位置からデータがアクセスされる。説明の残りの部分は、次に正しい合同クラスからデータをアクセスする方法である。それに関しては、シノニム・ヒットを処理する多くの既知の方法から任意の方法を採用できる。IBM/3090設計で実現された前記方法の１つは下記のとおりである。シノニム・ヒットの際に、キャッシュ制御部はシノニム合同クラスに関するデータを再びアクセスするように指示する。この方法は各シノニム・ヒットの(１サイクル以上の)遅延を生じるが、低い周波数のシノニム・ヒットによるシステム全体の不利点は些細なものである。本実施例に記述されたキャッシュ設計は、その実現による複雑さを最小にするこの方法を利用できる。例えば、後のサイクルでシノニム合同クラスのアクセスが再度指示されると、(主合同クラスの代わりに)シノニム合同クラスから４ダブルワードを読み出すために、一定の信号をARR 130 の制御部に引渡す必要がある。次の再アクセスの際に、前述のSETLAT更新が(ライン193を介して)自動的に正しいセット位置を与えるので、後選択ロジック162はリセットされた保留アクセス状態を有する正しいデータを確認信号(C＝１)を介してCMP 161からIE 110に送ることができる。シノニム・ヒットに関するもう１つの既知の方法は米国特許第4400770号で提案された。この方法は主として(一定の特別な状態を除き)、キャッシュ・ラインの別のコピーを、(シノニム合同クラスへの取出しを再度指示する代わりに)現にミスした主合同クラスCONG[A]に取込ませる。下記の例外はあるが、この方法は本発明でも使用できる。ここでSETLAT 140の制御部は(シノニム合同クラスで見つかったラインの代わりに)主合同クラスに挿入された新たなライン・エントリのセット位置を受取るべきである。このように、間違ったセット位置予測は新たなラインへの次のアクセスで回避できる。
【００３４】間違ったデータ・アクセスの処理について説明したので、次にSETLAT履歴更新に関する動作について説明する。SETLAT制御ロジックはCMP 161 から受取った信号193によりその履歴を更新する。特定の実施例により、セット位置更新信号193は(４つの可能なセット位置をコード化する)２ビット又は (各ビットが特定のセットの選択を示す)４ビットである。多くの設計では、SETLAT更新ライン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〜2048エントリ)なりつつあるので、より高速の回路を実現することは困難かつ高価である。また、一定の設計では、TLB ビットをキャッシュ・アレイ制御部に引渡すことはチップ交差を必要とすることがある。本発明は仮想アドレス・キャッシュの使用により前記負担を取り除き、合同クラス選択前のシノニム・ビット決定を回避する。MRU 方法のもう１つの欠点は、セット位置予測が特定の合同クラスのMRU情報に基づいている。その結果、TLBの使用により合同クラスが決定されたのちにだけ、セット位置を予測することができる。これは一定の設計についてクリテイカルパスタイミングを最適化する際に問題点を生じる。本発明によれば、SETLATは、実際のキャッシュ構造を知らずに (論理的なアクセス・アドレス・ビットにより) アクセスできる簡単な履歴テーブルである。よって、論理アドレスによりSETLAT 140のエントリを直接選択することができ、MRU 設計方法と比較してより効率的な実現をしばしば可能にする。
【００４２】本発明に関する前記説明では、シノニム状態を検出する際に各可能なシノニム・キャッシュ・エントリとTLB 合同クラスから読み出された各実アドレスとを突合わせるために多くの比較器の費用を負担してIBM/3090方法が採用された。包含される比較器の数を予測情報を用いて減らすことができる。例えば、アクセスのための直接探索サイクルでは、使用する比較器を減らし、TLB変換情報をPCCからのこれらの実ライン・アドレスとだけ突合わせることができる。しかしながら、あるシノニム・ヒットの場合、これは遅延(例えば、１サイクル)を生じることがある。シノニム決定の最適化は本発明の主要点ではないから、本実施例では更に詳細な説明は行なわない。
【００４３】ミスした各キャッシュ・ラインが (論理的なアクセス・アドレスにより決定された) 主合同クラスに入れられる、IBM/3090設計に基づいたSETLAT予測を用いるキャッシュ設計の実施例について説明したが、各DIR エントリは実ライン・アドレスを記録する。既存のシステム設計のうち、多くは純実ディレクトリ方法も採用しており、ミスしたラインは実アドレスにより直接決定された合同クラスに入れられる。このような純実ディレクトリの一定の実現に関する問題は、合同クラス選択の時間遅延である。例えば、IE 110アクセスの実アドレスを最初に決定し、そしてキャッシュ・アレイ・データ・アクセスを実行する。しかしながら、このような実施例は非常に長いキャッシュ・アクセスクリテイカルパスを形成する。なぜなら、通常はTLB 索引及びキャッシュ・アレイ・アクセスの動作はどちらも相対的に遅いからである。
【００４４】次に、キャッシュ・アクセスクリテイカルパスを短縮するために実アドレス変換の予測が用いられる、本発明のもう１つの実施例について説明する。SETLATの使用と同様に、仮想アドレス変換情報を予測するために履歴テーブル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 261、DIR 220及びARR 230の制御部にTLBLAT[A]の出力が送られる。
(3) DIR 220及びARR 230の制御部にA 250の適切なビット(例えば、前記の例のA[20-24])が送られる。TLBLATの出力ビットに連結された、 (ページ境界内の)これらのアドレス・ビットが合同クラス選択の予測を決定する。この合同クラス情報が使用可能なとき、下記の動作が実行される。(a) 予測された合同クラスにおける４つのDIRエントリが経路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に転送されたダブルワード・データは、CMP 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 261でより多くの比較器との直接の突合わせのために、特定のDIRエントリよりも多くを読み出しえない限り)DIR 220のアクセスはTLBLAT 241の結果によるからである。その結果、より高速の回路によるTLBLAT 241の実現を必要とすることがある。その場合には、TLBLATのサイズを最小にすることが望ましい。
【００４９】最初の実施例でSETLAT 140について説明したように、キャッシュ・ディレクトリ/アクセス・サイクルよりも早いサイクルでTLBLAT[A]を実行する特定の実施例を選択できる。このような場合、それに応じてTLBLAT 241アクセスのタイミング要求を緩和することができる。同様に、実アドレス・アクセス・モードでは、CMP 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及び経路211から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は、キャッシュ・ディレクトリから経路282に読み出された該選択された合同クラスの実ライン・アドレスと、(TLBLAT 241から経路288で実ページ・アドレス予測とページ境界内の未指定の入力アドレス・ビットとの連結により形成された)要求A 250 の予測された実アドレスとを比較する。経路285で予測されたセット位置SETLAT[A]で一致が起きると、正の信号(例えば、１ビットD＝1)が経路296でANDゲート261cに送られ、さもなければ、負の信号(例えば、１ビットD＝0)が送られる。もしSETLAT 240から受取った該予測されたSETLAT[A]以外のセット位置とのアドレス一致が起きれば、SETLAT更新ライン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エントリはTLBLAT 241でその領域を示す特別のビットLにより改良できる。仮想ページ・エントリが(例えば、古いエントリの置換を介して)最初にTLB 210に生成されると、関連したLビットがオフ(0に)なる。LビットはTLBLAT 241で更新されるとオン(1に) なる。しかしながら、古い値をセットするエントリと異なるTLB エントリによりTLBLATエントリが更新される可能性がなおある。よって、TLBLAT 241エントリが更新される毎に、予め前記値をセットしたTLB エントリでLビットをオフにする必要がある。 この手順は本明細書では詳細に説明されない種々の簡単なTLB/TLBLATエントリ選択アルゴリズムにより容易にすることができる。
【００５３】最初の実施例で説明したように、CMPa 261a及びCMPb 261bに必要な比較器を種々の方法で減少できる。例えば、CMPb 261b は１つの比較器を用いて予測セット位置SETLAT[A] のライン・エントリの実アドレスを検査できる。しかしながら、大部分の実施例では、これは大きな価値をもたらしえない。その理由は、選択された合同クラスの複数のDIR エントリの探索は間違ったセット予測による遅延を減らし(即ち、TLBLATが正しく予測するとき)、キャッシュ・ミス状態を迅速に解決する見込みが大きいからである。
【００５４】図１０の設計に関する更にもう１つの可能な改良は、 (IBM/3090アーキテクチャのSTOを含む)TLBLATエントリに仮想アドレス情報を含むことである。このように、TLBLAT 241は、通常のTLB 210 のサブセットとして維持できる、１次元の全機能変換テーブルとなる。図１１はこのような全機能TLBLAT 241を用いる図１０の変形を示す。
【００５５】図１１で、CMPa 261aは、より大きいTLB 210からの代わりに、TLBLAT 241から変換情報を直接取込む。ここでは、TLB 210は必要なとき(別個の比較装置263 からライン298を介して)TLBLAT 241に変換情報を供給するためにのみ動作する。アクセス毎にTLB探索を直接呼出すか又はTLBLATのミスのときのみTLB探索を呼出すかは設計上の選択である。
【００５６】２番目の実施例(図９〜図１１)で用いられたTLBLAT 241が適切な時点で所要の仮想アドレス変換情報の決定に用いられることに注目されたい。前記TLBLAT 241の機能はむしろそれ自身で独立しており、関連出願記載のように、セット位置を予測するためにSETLAT 240のない設計で使用可能である。
【００５７】前記実施例では、取出し(読取り)アクセス記憶要求が詳細に検討されている。IE装置からのオペランド記憶(書込み)要求は従来の据置き記憶方法を用いるものと仮定されている。提案された予測方式はキャッシュへの効率的な書込みを提供するためにも使用可能である。予測に基づいたキャッシュ書込みで生じる１つの複雑さは、間違った記憶位置(本発明ではキャッシュ・エントリ)にデータがプットアウェイされるとき記憶の完全性をいかに維持するかである。この状況がストアスルー(store-thru)・キャッシュ設計でいかに管理されるかについて以下に説明する。
【００５８】ストアスルーは周知の形式のキャッシュ設計であり、多くの市販の製品 (例えば、IBM/3033システム) で実用化されている。ストアスルー・キャッシュにより、キャッシュ・アレイへの各書込みは下位記憶階層 (例えば、２番目のレベルのキャッシュ又は主記憶装置) へも送られる。その結果、上位レベルのキャッシュ階層のラインが間違って書込まれるときでもなお、下位レベルの記憶階層からの最新(up-to-date)コピーを介して記憶の一貫性を維持できる。典型的なストアスルー設計では、記憶されたデータは実アドレスにより (即ち、仮想アドレスからの変換後に) 下位レベルの記憶階層に送られる。よって、ストアスルーに指定されたアドレスが正しい限り(例えば、TLBLAT予測の不確実性なしに)、下位レベルの記憶階層はあいまいさなしに記憶更新を実行する。よって、提案された予測方式がキャッシュ・アレイへの即時データ記憶に (即ち、据置き記憶方法でのような事前検査なしに) 用いられると、(間違った予測による)間違ったアレイ・プットアウェイは関連ラインを取り除く(無効化する)ことにより容易に回復可能である。オペランド記憶は正しいキャッシュ・ラインに書込まれるまで再開始可能である。しかしながら、もし取り除かれたラインが近い将来に再アクセスされるならば、この簡単な方法は(下位レベルの記憶階層への)余分なキャッシュ・ミス取出しを生じることがある。シミュレーション研究から、非常に高い精度のオペランド記憶が(SETLAT及び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〜330D(多くても１つが値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はアレイ区画のアクセスを指名(dispatch) する責任がある。切換え装置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 (ライン・アドレスの下位ビット) により決定される。同様に、1024エントリを有するSETLATの索引は10アドレス・ビット15〜24により決定される。より上位のアドレス・ビットを有するキャッシュ合同クラス又は他の情報 (例えば、IBM/3090アーキテクチャにおけるSTO識別)の選択をランダム化する提案もなされている。前記ランダム化の利点は、幾つかの合同クラスの激しい衝突による変則動作を回避することである。前記ランダム化方法は、適切なとき、(TLBLAT又はSETLATからの)履歴エントリの選択にも適用可能である。
【００６７】前述の実施例では、各履歴テーブル(TLBLAT又はSETLAT)の１つのコピーが図示されたけれども、実施例にとって有利とみなされるとき前記テーブルはいつでも反復可能である。
【００６８】該実施例では、キャッシュ・アレイ読取りを、アクセスのために予測されたセット位置に基づいたセット位置にのみ、いかに制限するかに関する方法が説明されている。前記予測情報はキャッシュ・ディレクトリの読取りの制限にも採用しうることは明白である。セット位置の予測の妥当性を検査するために、キャッシュ・ディレクトリ内の対応する１つのエントリの読取りのみを必要とすることがよくある。しかしながら、キャッシュ・ミス状態のより早い解決のために、大部分の実施例は、従来のセット連想キャッシュ設計の場合のように、関連した合同クラス内の全てのディレクトリ・エントリから読取るように選択できる。
【００６９】前述の実施例では、１つのキャッシュがプロセッサとみなされたけれども、予測手法は明らかに種々の他のタイプのプロセッサ・キャッシュ構成に適用可能である。例えば、多くの設計では、プロセッサ毎にI/D 分割キャッシュが用いられる。即ち、(Ｉ装置からの)命令コードのアクセス及びオペランドのアクセスのために別個のＩキャッシュ及びＤキャッシュがそれぞれプロセッサで用いられる。たぶん異なる組合せを有する予測機構をＩキャッシュ及びＤキャッシュへのアクセスに別個に用いることができる。
【００７０】前述の実施例では、SETLAT内の各エントリは２ビットを用いて４ウェイ・セット連想キャッシュにセット位置履歴を記録する。前記履歴情報を記録する方法は任意の特定の実施例の都合による。例えば、設計によっては、(セット位置を)符号化及び復号する際の遅延を減らすためにセット位置履歴を記録する (多くても１ビットがオンの) ４ビットの使用を選択できる。
【００７１】コンピュータ設計では、(例えば、α粒子損傷による)記憶された情報のエラーの検出及び修正のためのパリティ及びエラー修正ビットがよく用いられる。本発明の多くの実施例の履歴テーブルに関する前記保護のための固有の要求はない。履歴情報はいつでも使用の際に正確さを直ちに検査される。しかしながら、一般にエラー検出及び(又は)修正能力は発明にとってRAS(信頼性、可用度及びサービサビリティ)を高めるために望ましい。
【００７２】実施例ではキャッシュ・アクセスのための１つのライン・エントリのアクセスを予測する方法を示しているけれども、提案された手法は、所望のとき、複数のライン・エントリを予測するように一般化できることが明白である。例えば、図示のような４ウェイ・セット連想キャッシュを考えてみる。２ビット／エントリを有するSETLATは毎回１つのセット位置を予測できる。もし１ビット／エントリを有する類似のSETLATが用いられれば、アクセスのための合同クラスの半分 (２ライン・エントリ) を予測することができる。複数のライン・エントリの一回の前記予測は、一定の実施例での精度の向上及び(又は)SETLATサイズの小型化のために有利になりうる。
【００７３】本発明は前記実施例におけるプロセッサ・キャッシュに関して説明しているけれども、提案された手法は明らかに他の記憶階層設計に適用できる。例えば、２番目のレベルのキャッシュの設計を考えてみる。通常、これは (例えば、最初のレベルのキャッシュ・ミス又は更新から、ないしはI/Oチャネルから要求された)実アドレスによりアクセスされる。(SETLATを用いる)セット位置予測方式は前記２番目のレベルのキャッシュでの高速データ・アクセスにも使用可能である。
【図面の簡単な説明】
【図１】典型的なキャッシュの２次元構造を示すブロック図である。
【図２】TLB 及びキャッシュ・ディレクトリ・エントリの読取り、アドレス比較、アレイ・データ読取り、及びデータの後選択の動作を示す従来の技術の方法のブロック図である。
【図３】IBM/3090キャッシュ設計を示すブロック図である。
【図４】直接写像キャッシュ設計を示すブロック図である。
【図５】MRUキャッシュ設計を示すブロック図である。
【図６】実施例で考慮された高レベル・システム構成を示すブロック図である。
【図７】本発明に従ってセット位置を予測するためにSETLAT履歴テーブルを付加することにより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 切換え装置
【０００１】
【産業上の利用分野】本発明は一般にコンピュータ・システムのセット連想(set associative) キャッシュ、より詳しくはアクセスのための合同(congruence)クラスのセット数を決定する方式に関する。
【０００２】
【従来の技術】コンピュータ・システムで性能向上のためにキャッシュを使用することはよく知られており広く利用されている。キャッシュは最近に用いられたメモリ・データを保持する高速バッファである。プログラムの参照の局所性(locality of reference nature)により、大部分のデータのアクセスはキャッシュ内で行われ、大容量メモリに対する低速のアクセスを回避できる。
【０００３】典型的な高性能プロセッサの設計では、キャッシュ・アクセス経路はクリテイカルパス(critical path) を形成する。すなわち、いかに速いキャッシュ・アクセスを実行できるかにより、プロセッサのサイクル・タイムが決定される。
【０００４】キャッシュは論理的にはデータ・ブロック又はデータ・ライン(line)とみなすことができ、キャッシュ・テーブル・エントリはメモリ・データの特定のブロック又はラインをカバーする。 (以下、キャッシュの記憶装置はブロックよりはむしろラインと呼ばれる。) キャッシュの実現は通常は３つの主要部分:ディレクトリ、アレイ及び制御部分によって達成される。ディレクトリはキャッシュ・ライン・エントリのアドレス識別子のほか、特定の実施例に適した所要の状況タグを含む。(本明細書でときにはキャッシュ・メモリと呼ばれる)アレイは、実際のデータ・ビット、及び特定の実施例に要求されるようなパリティ検査すなわちエラー修正のための追加ビットを記憶する。制御回路はキャッシュ内容及びアクセスの管理に必要なロジックを提供する。キャッシュにアクセスする際、要求されたデータ・ラインの所在位置を識別するためにディレクトリが索引(look 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変換を行なう必要がある。大部分の最近の設計では、TLB索引はキャッシュ・ディレクトリ探索と並行して実行され、その結果はアレイ・データの最終的な後選択と組合わされる。図２はこのような設計を示す。キャッシュ・アクセスを決定するための複数のディレクトリ探索に関する前記要求は多くのキャッシュ設計の最適化を複雑にする原因になっている。前記複雑さは全て、プロセッサが記憶装置アクセス要求を出すとき、従来のディレクトリ索引の結果を知らずには、データの正確なロケーションをキャッシュ・アレイが決定できないので信号遅延を生じることに起因する。あいにく、種々の構成上の理由及び計算機装置上の理由により、データ・アクセスのための前記正確なロケーションを容易に得ることができない。従来の後選択機構の副作用は、１つのデータ単位を選択するために複数のデータ単位を検索するので、プロセッサ使用されなかったデータ単位のアレイ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 System/370," Proc. 14th Symposium on Computer Architecture, 1987, pp. 208-213 のMRU キャッシュ設計である。キャッシュ置換は通常は合同クラス毎に管理される。各合同クラス内には、適切な置換状況タグで示されたような最後に使用された(MRU = most recently used)エントリ及び最長時間未使用(LRU = least recently used)エントリがある。プログラム局所性によりキャッシュ・アクセスは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エントリの選択は、前記論理アドレス・ビットと他の情報とのハッシング(hashing) に基づくこともできる。同様のハッシング履歴テーブルが仮想アドレス変換情報を高精度で予測するために考案されることもある。これは関連出願に詳細に記述されている。前記予測機構はキャッシュ・アクセス経路の効率的な実現を可能にするだけではなく、複数アクセス／サイクルを達成する可能性も提供する。
【００２１】提案された予測方法は種々のディレクトリに基づいたテーブル・アクセスのための効率的な実現に関する一般的な方法も提供する。
【００２２】より詳しくは、セット連想キャッシュにおいて所与のアクセスのデータ・ロケーションを予測するアレイ制御の機構が開示される。予測が正しいとき、パフォーマンスはロケーションが既知の場合と同じである。間違った予測の場合は、データ・アクセスは打切られ、適切な予測が再度行なわれる。高精度の予測機構により、キャッシュのデータ・アクセスは間違った予測の最小のオーバーヘッドにより最適化させることができる。
【００２３】
【実施例】図６は、本発明を用いうるタイプのシステム構造のブロック図を示す。プロセッサは命令及び実行(IE)装置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 161に引渡される。
(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 はSETLAT更新ラインである。後に説明するように、このラインは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に沿って引渡された TLBCONG[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 ミス状態の変換プロセスの詳細な説明は行なわない。通常の手順によって所望の変換情報がTLBCONG[A]の置換エントリにロードされるものと仮定する。しかしながら、いったんTLB ミス状態が消失すれば、キャッシュ装置60は、前述のように、(一定のレジスタ又はスタックに記憶されている) 仮想アドレスA 150の待ちアクセスを再開始できるものと仮定する。
【００３０】キャッシュ・ミス状態は最初に該ラインがMS 80 から取出されることを必要とする。ライン取出しプロセスはIBM/3090記憶設計に類似するものと仮定する。キャッシュ装置60はSC 70にライン・ミス取出し要求を出す。SC 70は適切な時点でMS 80からキャッシュ装置60へのライン取出しをスケジュール(schedule) する。IBM/3090設計のように、新たに取出されたラインは、 (変換後の実アドレス・ビットによる代わりに)仮想アドレスA 150により決定された主合同クラス CONG[A]内(の前記置換エントリ)に入れられる。新たに取出されたライン・エントリの位置を、予測されたSETLAT[A] 履歴によって正しく反映できないことが明白である。履歴の調整は後に説明する。
【００３１】ここで詳細に説明する１つの事項は、キャッシュ・ミスのときIE 110に対してより迅速に応答するために用いられている従来のミス・バイパス (miss bypass)機構である。キャッシュ・ライン・サイズ(例えば、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の制御部に送る。SETLAT 140の制御ロジックは、ライン193 から受取った情報を用いて、ダブルワードの次の再アクセスを(例えば、次のサイクルで)指示されたセット位置から正しく取出し、それに従って履歴SETLAT[A] を更新する。履歴更新動作の詳細は後に説明する。間違ったセット予測の場合には、正しいダブルワード・データがARR 130から経路183に読み出されており、通常のアクセスについて説明したように (例えば、次のサイクルで)再読取りせずに、経路184を介して受取った正しいセット位置により直接選択できる。しかしながら、提案された機構を用いる大部分のプロセッサ設計では、ARR 読取りがクリテイカルパスタイミングに既に組込まれている。その結果、大部分の設計では、この場合に既に読み出されたデータの後選択に関する特別なケースとして制御ロジックを複雑にする必要はない。
【００３３】次に、間違ったデータ・アクセスのシノニム・ヒット状態について説明する。この場合、CMP 161は、アクセスされたダブルワードが主合同クラスCONG[A]と異なるシノニム合同クラスをヒットすることを検出する。更に、CMP 161 は目標ラインの正確なセット位置が関連シノニム合同クラスであることを見出だす。発見されたセット位置はSETLAT更新ライン193 を介してSETLAT 140の制御部に送られてSETLAT[A] が更新され、間違ったセット予測状態の場合と全く同様に (後の再アクセスのとき) 正しい位置からデータがアクセスされる。説明の残りの部分は、次に正しい合同クラスからデータをアクセスする方法である。それに関しては、シノニム・ヒットを処理する多くの既知の方法から任意の方法を採用できる。IBM/3090設計で実現された前記方法の１つは下記のとおりである。シノニム・ヒットの際に、キャッシュ制御部はシノニム合同クラスに関するデータを再びアクセスするように指示する。この方法は各シノニム・ヒットの(１サイクル以上の)遅延を生じるが、低い周波数のシノニム・ヒットによるシステム全体の不利点は些細なものである。本実施例に記述されたキャッシュ設計は、その実現による複雑さを最小にするこの方法を利用できる。例えば、後のサイクルでシノニム合同クラスのアクセスが再度指示されると、(主合同クラスの代わりに)シノニム合同クラスから４ダブルワードを読み出すために、一定の信号をARR 130 の制御部に引渡す必要がある。次の再アクセスの際に、前述のSETLAT更新が(ライン193を介して)自動的に正しいセット位置を与えるので、後選択ロジック162はリセットされた保留アクセス状態を有する正しいデータを確認信号(C＝１)を介してCMP 161からIE 110に送ることができる。シノニム・ヒットに関するもう１つの既知の方法は米国特許第4400770号で提案された。この方法は主として(一定の特別な状態を除き)、キャッシュ・ラインの別のコピーを、(シノニム合同クラスへの取出しを再度指示する代わりに)現にミスした主合同クラスCONG[A]に取込ませる。下記の例外はあるが、この方法は本発明でも使用できる。ここでSETLAT 140の制御部は(シノニム合同クラスで見つかったラインの代わりに)主合同クラスに挿入された新たなライン・エントリのセット位置を受取るべきである。このように、間違ったセット位置予測は新たなラインへの次のアクセスで回避できる。
【００３４】間違ったデータ・アクセスの処理について説明したので、次にSETLAT履歴更新に関する動作について説明する。SETLAT制御ロジックはCMP 161 から受取った信号193によりその履歴を更新する。特定の実施例により、セット位置更新信号193は(４つの可能なセット位置をコード化する)２ビット又は (各ビットが特定のセットの選択を示す)４ビットである。多くの設計では、SETLAT更新ライン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〜2048エントリ)なりつつあるので、より高速の回路を実現することは困難かつ高価である。また、一定の設計では、TLB ビットをキャッシュ・アレイ制御部に引渡すことはチップ交差を必要とすることがある。本発明は仮想アドレス・キャッシュの使用により前記負担を取り除き、合同クラス選択前のシノニム・ビット決定を回避する。MRU 方法のもう１つの欠点は、セット位置予測が特定の合同クラスのMRU情報に基づいている。その結果、TLBの使用により合同クラスが決定されたのちにだけ、セット位置を予測することができる。これは一定の設計についてクリテイカルパスタイミングを最適化する際に問題点を生じる。本発明によれば、SETLATは、実際のキャッシュ構造を知らずに (論理的なアクセス・アドレス・ビットにより) アクセスできる簡単な履歴テーブルである。よって、論理アドレスによりSETLAT 140のエントリを直接選択することができ、MRU 設計方法と比較してより効率的な実現をしばしば可能にする。
【００４２】本発明に関する前記説明では、シノニム状態を検出する際に各可能なシノニム・キャッシュ・エントリとTLB 合同クラスから読み出された各実アドレスとを突合わせるために多くの比較器の費用を負担してIBM/3090方法が採用された。包含される比較器の数を予測情報を用いて減らすことができる。例えば、アクセスのための直接探索サイクルでは、使用する比較器を減らし、TLB変換情報をPCCからのこれらの実ライン・アドレスとだけ突合わせることができる。しかしながら、あるシノニム・ヒットの場合、これは遅延(例えば、１サイクル)を生じることがある。シノニム決定の最適化は本発明の主要点ではないから、本実施例では更に詳細な説明は行なわない。
【００４３】ミスした各キャッシュ・ラインが (論理的なアクセス・アドレスにより決定された) 主合同クラスに入れられる、IBM/3090設計に基づいたSETLAT予測を用いるキャッシュ設計の実施例について説明したが、各DIR エントリは実ライン・アドレスを記録する。既存のシステム設計のうち、多くは純実ディレクトリ方法も採用しており、ミスしたラインは実アドレスにより直接決定された合同クラスに入れられる。このような純実ディレクトリの一定の実現に関する問題は、合同クラス選択の時間遅延である。例えば、IE 110アクセスの実アドレスを最初に決定し、そしてキャッシュ・アレイ・データ・アクセスを実行する。しかしながら、このような実施例は非常に長いキャッシュ・アクセスクリテイカルパスを形成する。なぜなら、通常はTLB 索引及びキャッシュ・アレイ・アクセスの動作はどちらも相対的に遅いからである。
【００４４】次に、キャッシュ・アクセスクリテイカルパスを短縮するために実アドレス変換の予測が用いられる、本発明のもう１つの実施例について説明する。SETLATの使用と同様に、仮想アドレス変換情報を予測するために履歴テーブル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 261、DIR 220及びARR 230の制御部にTLBLAT[A]の出力が送られる。
(3) DIR 220及びARR 230の制御部にA 250の適切なビット(例えば、前記の例のA[20-24])が送られる。TLBLATの出力ビットに連結された、 (ページ境界内の)これらのアドレス・ビットが合同クラス選択の予測を決定する。この合同クラス情報が使用可能なとき、下記の動作が実行される。(a) 予測された合同クラスにおける４つのDIRエントリが経路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に転送されたダブルワード・データは、CMP 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 261でより多くの比較器との直接の突合わせのために、特定のDIRエントリよりも多くを読み出しえない限り)DIR 220のアクセスはTLBLAT 241の結果によるからである。その結果、より高速の回路によるTLBLAT 241の実現を必要とすることがある。その場合には、TLBLATのサイズを最小にすることが望ましい。
【００４９】最初の実施例でSETLAT 140について説明したように、キャッシュ・ディレクトリ/アクセス・サイクルよりも早いサイクルでTLBLAT[A]を実行する特定の実施例を選択できる。このような場合、それに応じてTLBLAT 241アクセスのタイミング要求を緩和することができる。同様に、実アドレス・アクセス・モードでは、CMP 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及び経路211から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は、キャッシュ・ディレクトリから経路282に読み出された該選択された合同クラスの実ライン・アドレスと、(TLBLAT 241から経路288で実ページ・アドレス予測とページ境界内の未指定の入力アドレス・ビットとの連結により形成された)要求A 250 の予測された実アドレスとを比較する。経路285で予測されたセット位置SETLAT[A]で一致が起きると、正の信号(例えば、１ビットD＝1)が経路296でANDゲート261cに送られ、さもなければ、負の信号(例えば、１ビットD＝0)が送られる。もしSETLAT 240から受取った該予測されたSETLAT[A]以外のセット位置とのアドレス一致が起きれば、SETLAT更新ライン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エントリはTLBLAT 241でその領域を示す特別のビットLにより改良できる。仮想ページ・エントリが(例えば、古いエントリの置換を介して)最初にTLB 210に生成されると、関連したLビットがオフ(0に)なる。LビットはTLBLAT 241で更新されるとオン(1に) なる。しかしながら、古い値をセットするエントリと異なるTLB エントリによりTLBLATエントリが更新される可能性がなおある。よって、TLBLAT 241エントリが更新される毎に、予め前記値をセットしたTLB エントリでLビットをオフにする必要がある。 この手順は本明細書では詳細に説明されない種々の簡単なTLB/TLBLATエントリ選択アルゴリズムにより容易にすることができる。
【００５３】最初の実施例で説明したように、CMPa 261a及びCMPb 261bに必要な比較器を種々の方法で減少できる。例えば、CMPb 261b は１つの比較器を用いて予測セット位置SETLAT[A] のライン・エントリの実アドレスを検査できる。しかしながら、大部分の実施例では、これは大きな価値をもたらしえない。その理由は、選択された合同クラスの複数のDIR エントリの探索は間違ったセット予測による遅延を減らし(即ち、TLBLATが正しく予測するとき)、キャッシュ・ミス状態を迅速に解決する見込みが大きいからである。
【００５４】図１０の設計に関する更にもう１つの可能な改良は、 (IBM/3090アーキテクチャのSTOを含む)TLBLATエントリに仮想アドレス情報を含むことである。このように、TLBLAT 241は、通常のTLB 210 のサブセットとして維持できる、１次元の全機能変換テーブルとなる。図１１はこのような全機能TLBLAT 241を用いる図１０の変形を示す。
【００５５】図１１で、CMPa 261aは、より大きいTLB 210からの代わりに、TLBLAT 241から変換情報を直接取込む。ここでは、TLB 210は必要なとき(別個の比較装置263 からライン298を介して)TLBLAT 241に変換情報を供給するためにのみ動作する。アクセス毎にTLB探索を直接呼出すか又はTLBLATのミスのときのみTLB探索を呼出すかは設計上の選択である。
【００５６】２番目の実施例(図９〜図１１)で用いられたTLBLAT 241が適切な時点で所要の仮想アドレス変換情報の決定に用いられることに注目されたい。前記TLBLAT 241の機能はむしろそれ自身で独立しており、関連出願記載のように、セット位置を予測するためにSETLAT 240のない設計で使用可能である。
【００５７】前記実施例では、取出し(読取り)アクセス記憶要求が詳細に検討されている。IE装置からのオペランド記憶(書込み)要求は従来の据置き記憶方法を用いるものと仮定されている。提案された予測方式はキャッシュへの効率的な書込みを提供するためにも使用可能である。予測に基づいたキャッシュ書込みで生じる１つの複雑さは、間違った記憶位置(本発明ではキャッシュ・エントリ)にデータがプットアウェイされるとき記憶の完全性をいかに維持するかである。この状況がストアスルー(store-thru)・キャッシュ設計でいかに管理されるかについて以下に説明する。
【００５８】ストアスルーは周知の形式のキャッシュ設計であり、多くの市販の製品 (例えば、IBM/3033システム) で実用化されている。ストアスルー・キャッシュにより、キャッシュ・アレイへの各書込みは下位記憶階層 (例えば、２番目のレベルのキャッシュ又は主記憶装置) へも送られる。その結果、上位レベルのキャッシュ階層のラインが間違って書込まれるときでもなお、下位レベルの記憶階層からの最新(up-to-date)コピーを介して記憶の一貫性を維持できる。典型的なストアスルー設計では、記憶されたデータは実アドレスにより (即ち、仮想アドレスからの変換後に) 下位レベルの記憶階層に送られる。よって、ストアスルーに指定されたアドレスが正しい限り(例えば、TLBLAT予測の不確実性なしに)、下位レベルの記憶階層はあいまいさなしに記憶更新を実行する。よって、提案された予測方式がキャッシュ・アレイへの即時データ記憶に (即ち、据置き記憶方法でのような事前検査なしに) 用いられると、(間違った予測による)間違ったアレイ・プットアウェイは関連ラインを取り除く(無効化する)ことにより容易に回復可能である。オペランド記憶は正しいキャッシュ・ラインに書込まれるまで再開始可能である。しかしながら、もし取り除かれたラインが近い将来に再アクセスされるならば、この簡単な方法は(下位レベルの記憶階層への)余分なキャッシュ・ミス取出しを生じることがある。シミュレーション研究から、非常に高い精度のオペランド記憶が(SETLAT及び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〜330D(多くても１つが値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はアレイ区画のアクセスを指名(dispatch) する責任がある。切換え装置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 (ライン・アドレスの下位ビット) により決定される。同様に、1024エントリを有するSETLATの索引は10アドレス・ビット15〜24により決定される。より上位のアドレス・ビットを有するキャッシュ合同クラス又は他の情報 (例えば、IBM/3090アーキテクチャにおけるSTO識別)の選択をランダム化する提案もなされている。前記ランダム化の利点は、幾つかの合同クラスの激しい衝突による変則動作を回避することである。前記ランダム化方法は、適切なとき、(TLBLAT又はSETLATからの)履歴エントリの選択にも適用可能である。
【００６７】前述の実施例では、各履歴テーブル(TLBLAT又はSETLAT)の１つのコピーが図示されたけれども、実施例にとって有利とみなされるとき前記テーブルはいつでも反復可能である。
【００６８】該実施例では、キャッシュ・アレイ読取りを、アクセスのために予測されたセット位置に基づいたセット位置にのみ、いかに制限するかに関する方法が説明されている。前記予測情報はキャッシュ・ディレクトリの読取りの制限にも採用しうることは明白である。セット位置の予測の妥当性を検査するために、キャッシュ・ディレクトリ内の対応する１つのエントリの読取りのみを必要とすることがよくある。しかしながら、キャッシュ・ミス状態のより早い解決のために、大部分の実施例は、従来のセット連想キャッシュ設計の場合のように、関連した合同クラス内の全てのディレクトリ・エントリから読取るように選択できる。
【００６９】前述の実施例では、１つのキャッシュがプロセッサとみなされたけれども、予測手法は明らかに種々の他のタイプのプロセッサ・キャッシュ構成に適用可能である。例えば、多くの設計では、プロセッサ毎にI/D 分割キャッシュが用いられる。即ち、(Ｉ装置からの)命令コードのアクセス及びオペランドのアクセスのために別個のＩキャッシュ及びＤキャッシュがそれぞれプロセッサで用いられる。たぶん異なる組合せを有する予測機構をＩキャッシュ及びＤキャッシュへのアクセスに別個に用いることができる。
【００７０】前述の実施例では、SETLAT内の各エントリは２ビットを用いて４ウェイ・セット連想キャッシュにセット位置履歴を記録する。前記履歴情報を記録する方法は任意の特定の実施例の都合による。例えば、設計によっては、(セット位置を)符号化及び復号する際の遅延を減らすためにセット位置履歴を記録する (多くても１ビットがオンの) ４ビットの使用を選択できる。
【００７１】コンピュータ設計では、(例えば、α粒子損傷による)記憶された情報のエラーの検出及び修正のためのパリティ及びエラー修正ビットがよく用いられる。本発明の多くの実施例の履歴テーブルに関する前記保護のための固有の要求はない。履歴情報はいつでも使用の際に正確さを直ちに検査される。しかしながら、一般にエラー検出及び(又は)修正能力は発明にとってRAS(信頼性、可用度及びサービサビリティ)を高めるために望ましい。
【００７２】実施例ではキャッシュ・アクセスのための１つのライン・エントリのアクセスを予測する方法を示しているけれども、提案された手法は、所望のとき、複数のライン・エントリを予測するように一般化できることが明白である。例えば、図示のような４ウェイ・セット連想キャッシュを考えてみる。２ビット／エントリを有するSETLATは毎回１つのセット位置を予測できる。もし１ビット／エントリを有する類似のSETLATが用いられれば、アクセスのための合同クラスの半分 (２ライン・エントリ) を予測することができる。複数のライン・エントリの一回の前記予測は、一定の実施例での精度の向上及び(又は)SETLATサイズの小型化のために有利になりうる。
【００７３】本発明は前記実施例におけるプロセッサ・キャッシュに関して説明しているけれども、提案された手法は明らかに他の記憶階層設計に適用できる。例えば、２番目のレベルのキャッシュの設計を考えてみる。通常、これは (例えば、最初のレベルのキャッシュ・ミス又は更新から、ないしはI/Oチャネルから要求された)実アドレスによりアクセスされる。(SETLATを用いる)セット位置予測方式は前記２番目のレベルのキャッシュでの高速データ・アクセスにも使用可能である。
【図面の簡単な説明】
【図１】典型的なキャッシュの２次元構造を示すブロック図である。
【図２】TLB 及びキャッシュ・ディレクトリ・エントリの読取り、アドレス比較、アレイ・データ読取り、及びデータの後選択の動作を示す従来の技術の方法のブロック図である。
【図３】IBM/3090キャッシュ設計を示すブロック図である。
【図４】直接写像キャッシュ設計を示すブロック図である。
【図５】MRUキャッシュ設計を示すブロック図である。
【図６】実施例で考慮された高レベル・システム構成を示すブロック図である。
【図７】本発明に従ってセット位置を予測するためにSETLAT履歴テーブルを付加することにより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 切換え装置
【特許請求の範囲】
【請求項１】セット連想テーブルに記憶されることがある所望のデータのセット位置を予測する装置であって、前記セット連想テーブルに対するアクセスのセット位置の最新の値を記憶する履歴テーブルであって、該記憶する位置が、前記アクセスに関連した論理アドレス中の所定のアドレス・ビットのサブセットの値により決定された前記履歴テーブル中の位置であることと、前記履歴テーブルをアクセスし、かつ所望のデータの論理アドレス中のアドレス・ビットのサブセットの値に関連づけられている前記履歴テーブル中の場所にある該記憶されたセット位置の最新の値を検索することにより、前記論理アドレスを有する前記所望のデータの前記セット位置を予測する手段とを含み、前記予測されたセット位置は前記検索されたセット位置であることを特徴とする、データのセット位置の予測装置。
【請求項２】前記セット連想テーブルは実アドレスに基づいたキャッシュ・メモリである請求項１のデータのセット位置の予測装置。
【請求項３】前記履歴テーブルは１つのサイクルで複数のロケーションに対する前記セット連想テーブルへの並列アクセスのための複数のセット位置を予測するために用いられる請求項１のセット連想テーブルに記憶されることがある所望のデータのセット位置を予測する装置。
【請求項１】セット連想テーブルに記憶されることがある所望のデータのセット位置を予測する装置であって、前記セット連想テーブルに対するアクセスのセット位置の最新の値を記憶する履歴テーブルであって、該記憶する位置が、前記アクセスに関連した論理アドレス中の所定のアドレス・ビットのサブセットの値により決定された前記履歴テーブル中の位置であることと、前記履歴テーブルをアクセスし、かつ所望のデータの論理アドレス中のアドレス・ビットのサブセットの値に関連づけられている前記履歴テーブル中の場所にある該記憶されたセット位置の最新の値を検索することにより、前記論理アドレスを有する前記所望のデータの前記セット位置を予測する手段とを含み、前記予測されたセット位置は前記検索されたセット位置であることを特徴とする、データのセット位置の予測装置。
【請求項２】前記セット連想テーブルは実アドレスに基づいたキャッシュ・メモリである請求項１のデータのセット位置の予測装置。
【請求項３】前記履歴テーブルは１つのサイクルで複数のロケーションに対する前記セット連想テーブルへの並列アクセスのための複数のセット位置を予測するために用いられる請求項１のセット連想テーブルに記憶されることがある所望のデータのセット位置を予測する装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開平６−１９７９４
【公開日】平成６年（１９９４）１月２８日
【国際特許分類】
【出願番号】特願平５−７５８６７
【出願日】平成５年（１９９３）４月１日
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレイション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【公開日】平成６年（１９９４）１月２８日
【国際特許分類】
【出願日】平成５年（１９９３）４月１日
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレイション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
[ Back to top ]