JPH0564816B2

JPH0564816B2 -

Info

Publication number: JPH0564816B2
Application number: JP2251670A
Authority: JP
Inventors: Orajio Serutoruuda Josefu; Aan Fuaa Kien; Heritsuku Hanto Andaason; Riu Rishin; Piaa Jiiuon; Reimondo Puruetsuto Deibitsudo; Resutaa Tenpuru Za Saad Josefu
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1989-10-20
Filing date: 1990-09-20
Publication date: 1993-09-16
Also published as: EP0424163A2; EP0424163A3; US5148538A; JPH03194632A

Description

【発明の詳細な説明】〔産業上の利用分野〕この発明は、デイジタルコンピユータシステム
のキヤツシユメモリからの情報のアクセス方式に
おける改良に関する。

〔従来の技術およびその問題点〕

デイジタルコンピユータのキヤツシユメモリア
クセスシステムは、通常、変換バツフア、キヤツ
シユデイレクトリおよびキヤツシユメモリを含ん
でいる。変換バツフアは、そのメモリ内に含まれ
るデータの論理アドレス（仮想アドレスともい
う）と組み合わされた全部の物理アドレス（実ア
ドレスともいう）のリストを含んでいる。コンピ
ユータがキヤツシユからデータを要求すると、コ
ンピユータはそのキヤツシユ変換バツフアに論理
アドレスを送り、その後変換バツフアはその論理
アドレスをキヤツシユデイレクトリの論理アドレ
スのリストと比較する。変換バツフアが一致を確
認すると、変換バツフアはその論理アドレスに対
応する物理アドレスをデイレクトリおよびキヤツ
シユメモリに送る。キヤツシユデイレクトリは、
キヤツシユメモリ内に現在あるデータバイトの全
部のライン（例えば、１ライン当たり128バイト
に分けられている2Kのライン）およびそれらの
関係する実アドレスのリストを含んでいる。デイ
レクトリは実アドレスを受け取り、命令によつて
要求されたそのデータがキヤツシユ内に現在ある
かどうかを判断する。データがキヤツシユ内にな
ければ、キヤツシユアクセスシステムは直接には
キヤツシユにアクセスせず、要求されたデータは
この発明の範囲外である別の独立した機構によつ
て検索される。データがキヤツシユ内にあれば、
キヤツシユメモリはそのデータを実アドレスから
検索し、データを要求しているコンピユータシス
テムの適切な部分に送る。

コンピユータシステムが論理アドレスをキヤツ
シユアクセスシステムに送るためには、初めに、
論理アドレスを生成し、その生成アドレスがいつ
有効であるかを判断しなければならない。論理ア
ドレスは、コンピユータシステムからの命令が解
読され、それが引き続いて、データおよび論理ア
ドレス生成を要求する時に生成される。論理アド
レス生成は、要求データのアドレスを持つ解読さ
れた命令の部分を受け取り、対応する論理アドレ
スを生成するキヤツシユアクセスシステムによつ
て行われる。アドレスの有効性のタイミング、従
つてキヤツシユメモリアクセスシステムの速度
は、パイプライン構造として知られる一連のコン
ピユータシステムのマシンサイクルによつて決ま
る。このようなサイクルは、様々な命令に対する
共通段がデイジタルコンピユータの各種部分をア
イドル状態にさせることなく迅速に完了できるよ
うに、デイジタルコンピユータのオペレーシヨン
を分割する。キヤツシユメモリアクセスシステム
の通常のパイプライン構造は、命令解読サイク
ル、アドレス生成サイクル、キヤツシユアクセス
サイクル、実行サイクルという順になつている。
こうしたサイクルはキヤツシユメモリアクセスシ
ステムのオペレーシヨンを分割するのに役立つ、
第２図は、特にこの発明で用いている一般的なパ
イプライン構造を示す（また、各段で実行される
主な動作を要約してある）。

キヤツシユアクセスシステムの速度は、２通り
の方法で速めることができる。第１に、アドレス
生成サイクルは論理アドレスの生成を速めること
によつて短縮することができる。アドレス生成
は、通常、加算器によつて行われるので、これ
は、より高速の加算器を実施することを意味す
る。しかし、これは、キヤツシユのすべてのアク
セス方法にとつて同一のハードウエア上の解決で
あり、いずれのシステムでも実施できる。加算器
が高速であつても、アドレス要求が増えるにつれ
て増す加算器に関係した遅延が必ずある。第２
に、キヤツシユアクセスのマシンサイクルは、デ
イレクトリが特定のデータバイトのアドレスを発
見し、そのバイトが完全にキヤツシユ内にあるか
どうかを判断する前に行わなければならない比較
回数を減らすことによつて短縮できる。これは、
一般に、メモリのキヤツシユサイズが拡大するた
びに、より大きく複雑な論理回路を必要としてい
る。論理回路が大きくなればなるほど、そして、
設計が複雑になればなるほど、システムの設計時
間は長くかかる。

キヤツシユメモリの速度を上げるための先行技
術の試みは、キヤツシユメモリアクセスシステム
がセツトアソシエイテイブという概念にもとづい
て作動できるという事実に頼つている。すなわ
ち、キヤツシユメモリおよびデイレクトリは、複
数の組またはコングルエンスクラスに分割され
る。例えば、256Kバイトのキヤツシユメモリは、
それぞれが128バイトの４ラインを含む512のコン
グルエンスクラスに分割できる。その後、キヤツ
シユメモリは、１コングルエンスクラスのすべて
の４ラインを同時にアドレス指定し、そのコング
ルエンスクラスから選択されたラインが正しいも
のであるかどうかを順次判断することによつてア
クセスされる。この方法は、キヤツシユデイレク
トリ（つまり大きな組）の全部のアドレスを探索
する従来の方法に比べ、必要な比較回数が少なく
なるので、高速になる。１ライン128バイトの2K
のラインを比較する代わりに、そのデイレクトリ
は512ラインを比較するだけである。

上記の方法の問題は、この方法が、キヤツシユ
アクセスシステムによつて生成され、メモリにア
クセスするための変換バツフアに送られる論理ア
ドレスにもとづいていることである。これは、同
一の物理アドレスに対して２つの論理アドレスが
割り当てられることが可能なので問題となる。こ
れはシノニムの問題と呼ばれる。従つて、セツト
アソシエイテイブ方式は、論理アドレスを使用す
る以上、（命令によつて要求されたデータとは異
なるデータにアクセスする）潜在的なエラーを含
んでいる。この潜在的なエラーは検査しなければ
ならない。検査によつてエラーが発見されると、
その解決法は正しいアドレスのメモリに再アクセ
スすることである。選択が十分な回数正しい（正
しくない場合の“ミス”に対して“ヒツト”であ
る）としても、無駄な時間が多数の命令に対して
均分にされ、この問題は依然として論理アドレス
生成の性質上存在する。さらに、この問題のため
に検査するための論理は、キヤツシユメモリが大
きくなるにつれて、より大きくなり、その機能を
果たすのにかかる時間も長くなる。デイレクトリ
および論理アドレスに関するヒツト／ミス率を高
めることは、キヤツシユメモリアクセスシステム
の速度を増すが、キヤツシユアクセスシステムに
関する設計を単純にすることには役立たない。

その問題を例示するキヤツシユメモリにアクセ
スする先行技術の方法は、１つのコングルエンス
クラス内にラインの選択が、そのコングルエンス
クラスから使用された最後のラインにもとづいて
いる時間である。この選択は、コングルエンスク
ラスから使用された最後のラインがやはりそこに
データバイトを持つている最も確実性の高いライ
ンであるという（すぐれた推測ではあるが）推測
にすぎない。この推測はその時間の相当部分正し
いが、推測はやはりキヤツシユアクセスシステム
のアドレス生成部分からの論理（仮想）アドレス
にもとづいて行われる。このことは、この技法
が、２つの論理アドレスが同一の物理アドレスに
関係し得る（シノニムの問題）という事実に関す
るエラーを排除できないことを意味する。その検
査論理はやはり、このエラーのために、キヤツシ
ユメモリが大きくなるたびに拡大せざるをえな
い。このシノニムの問題を解決する他の先行技術
の方法は、潜在的なシノニムが生じた場合、潜在
的なアドレスにフラグを立て、そのアドレスを格
納することを中心としている。システムはその
後、物理アドレスを一度検索するだけである。こ
の手法は、シノニムの問題を避けているだけで、
解決してはおらず、依然としてキヤツシユメモリ
が大きくなるごとに拡大しなければならない論理
を必要とする。

この発明の目的は、アドレスにアクセスできる
速度を増すキヤツシユメモリアクセスシステムを
提供することにある。

この発明の第２の目的は、キヤツシユメモリに
関係したコンピユータのマシンサイクルを短縮す
ることによつて、アドレスにアクセスできる速度
を増すキヤツシユメモリアクセスシステムを提供
することにある。

この発明の第３の目的は、セツトアソシエイテ
イブキヤツシユメモリに関係したシノニムの問題
を避けるキヤツシユメモリアクセスシステムを提
供することにある。

この発明の第４の目的は、命令に応答してアク
セスされたアドレスがその命令によつて選択され
るアドレスの一部のみにもとづいて予測される、
キヤツシユメモリアクセスシステムを提供するこ
とにある。

この発明の第５目的は、予測されたアドレスが
迅速にかつ低水準の間違つた予測によつて生成さ
れる、キヤツシユメモリアクセスシステムを提供
することにある。

この発明の第６の目的は、予測された実アドレ
スが、キヤツシユメモリがその予測された実アド
レスに関係したデータを検索している間に検査さ
れる、キヤツシユメモリアクセスシステムを提供
することにある。

この発明の第７の目的は、予測された実アドレ
スの検査が、次に正確な実アドレスの表にアクセ
スするために使用される仮想アドレスにもとづい
ている、キヤツシユメモリアクセスシステムを提
供することにある。

この発明の第８の目的は、予測された実アドレ
スの出所が間違つた予測実アドレスの頻度を最小
限にするために更新される、キヤツシユメモリア
クセスシステムを提供することにある。

〔問題点を解決するための手段〕

この発明は、ハードウエアの改良とは関係な
く、アドレス生成マシンサイクルを短縮し、キヤ
ツシユアクセスマシンサイクルを短縮しながら論
理アドレス指定のシノニムの問題を避けるキヤツ
シユアクセスシステムを実施するものである。こ
の発明は、論理アドレスの生成とは無関係に実ア
ドレスがいずれになるかを予測するという概念に
もとづいている。これにより、キヤツシユメモリ
は、仮想アドレスが生成させるのを待ち、その仮
想アドレスを実アドレスを変換するよりも高速に
情報を検索することができる。これは、第１に、
アドレス生成の加算器がバイパスされるので遅延
を生じず、変換バツフアおよびデイレクトリもバ
イパスされるので遅延を生じないという２点で高
速になる。

実アドレスの予測は、たとえ極めて良好なもの
であつても、予測にすぎないので、検査を必要と
する。この検査は、キヤツシユメモリの予測アド
レスからのデータの検索と平行して行われる。検
査経路は、加算器、変換バツフアおよびデイレク
トリに関係した機能を実行するが、これらの機能
はキヤツシユアクセスと平行して実行されるの
で、予測アドレスが正しければデイレクトリ検索
を遅らせることはない。予測アドレスが正しくな
い場合、キヤツシユは再びアクセスされ、１マシ
ンサイクルが無駄になる。このキヤツシユの再ア
クセスは、予測実アドレスを検査するために以前
のマシンサイクルで正しいアドレスがすでに生成
されているので、２の余分なマシンサイクル（正
しいアドレスを生成するためのサイクルとキヤツ
シユメモリを再アクセスするためのサイクル）を
必要とすることはない。さらに、キヤツシユが１
マシンサイクルを無駄にしなければならないとし
ても、こうした無駄なサイクルの発生は、予測実
アドレスの推測を仮想アドレスにもとづかせない
ことによつて最低限に抑えられる。これによつて
シノニムの問題は避けられ、無駄になつた各サイ
クルは多数の正確な推測に均分にすることがで
き、従つて、キヤツシユアクセスシステムの全体
の速度は高まる。

〔実施態様」この発明のキヤツシユアクセスシステムは、ア
クセス部と検査部の２つの部分に分かれる。キヤ
ツシユアクセスシステムは、コンピユータシステ
ム内のプロセツサから命令を受け取り、解読す
る。解読された命令はキヤツシユメモリ内のデー
タビツトにアクセスするために使用されるアドレ
ス情報を含むものである。解読された命令からの
情報は、レジスタインジケータの形式をしてい
る。これらのインジケータは、コンピユータ内部
のどのレジスタがキヤツシユメモリにアクセスす
るために必要なアドレス情報を含んでいるかをキ
ヤツシユアクセスシステムに指示する。この発明
のキヤツシユアクセスシステムには、16の汎用レ
ジスタがある。解読された命令によつて指示され
たレジスタの１つは、基底レジスタと呼ばれ、現
在のアドレスを含んでいる。キヤツシユアクセス
システムのアクセス部は、予測実アドレスを生成
するために基底レジスタの内容の一部（現在のア
ドレス）を使用する。この予測実アドレスは、名
目上、キヤツシユアクセスシステムの検査部が生
成するアドレスと同一であり、解読された命令に
よつて与えられた全部のアドレス情報にもとづく
実アドレスと呼ばれる。予測実アドレスが検査部
によつて生成されたアドレスと同一でない場合、
その予測実アドレスは実アドレスに置き換えら
れ、キヤツシユメモリは再アクセスされる。予測
実アドレスが実アドレスと同一である場合は、予
測実アドレスによつてアクセスされたデータが、
解読された命令による要求通りに実行されるため
に算術論理演算装置（ALU）に送られる。

予測実アドレスは、キヤツシユアクセスシステ
ムのアクセス部において、ヒストリテーブルから
生成される。ヒストリテーブルは、最も新しく使
用された現在アドレスおよび、それらの現在アド
レスについてキヤツシユメモリアクセスシステム
の検査部によつて生成された対応する実アドレス
のリストである。現在アドレスの一部は、ヒスト
リテーブルの現在アドレスのリストの各アドレス
の対応する部分と比較される。現在アドレスのそ
の部分がヒストリテーブルの現在アドレスの部分
と一致した場合、対応する最も新しく使用された
実アドレスが予測実アドレスになる。このアドレ
スはその後、キヤツシユアクセスシステムの検査
部が解読された命令によつて要求された実アドレ
スを生成している間に、キヤツシユメモリにアク
セスするために使用される。

キヤツシユメモリアクセスシステムの検査部
は、現在アドレスの全部から仮想アドレスを生成
するために加算器を使用する。この仮想アドレス
はその後、変換索引緩衝機構（TLB）の仮想ア
ドレスのリストと比較される。このTLBアドレ
スリストは、ヒストリテーブルが加算器によつて
処理されていない現在アドレスの部分によつてア
クセスされるのに対し、TLBが加算器によつて
生成された仮想アドレスによつてアクセスされる
ことから、ヒストリテーブルとは異なるものであ
る。TLBは、各仮想アドレスについて対応する
実アドレスを含んでおり、加算器からの仮想アド
レスとTLBの仮想アドレスとの間に一致が見ら
れた場合、対応する実アドレスはその後、キヤツ
シユアクセスシステムのアクセス部ですでに生成
されている予測実アドレスと比較される。予測実
アドレスが実アドレスと一致すれば、アクセスシ
ステムは、キヤツシユアクセスマシンサイクルの
後に再アクセスされない。予測実アドレスが実ア
ドレスと一致しない場合、キヤツシユメモリは、
そのキヤツシユアクセスのマシンサイクルの後の
マシンサイクルで再アクセスされる。

予測実アドレスと実アドレスとの比較が一致し
ない場合、キヤツシユアクセスシステムは、２つ
の機能を実行しなければならない。第１が、前述
の通りキヤツシユへの再アクセスであり、第２
が、予測実アドレスの出所の更新である。これ
は、予測実アドレスの出所が命令の最新状態を反
映させるためである。予測実アドレスの出所の更
新は、ヒストリテーブルが、ヒストリテーブルで
比較される現在アドレスの部分に対応する最新の
実アドレスを反映しなければならないことを意味
する。従つて、ヒストリテーブルは、ヒストリテ
ーブルの現在アドレスの部分に対応する実アドレ
スをTLBからの実アドレスと置き換えるか、ま
たは、ヒストリテーブルは、現在アドレスおよび
対応する実アドレスの両部分をTLBおよび基底
レジスタからの値に置き換える。エラーがあるた
びにヒストリテーブルを更新することは、誤つた
予測実アドレスの発生を低水準に維持し、それに
よつて、再アクセス状態の必要が少なくなるの
で、キヤツシユメモリアクセス速度を高めるのに
役立つ。

予測実アドレスの出所は、ヒストリテーブルと
組み合わせて変換予見テーブル（TLAT）とす
ることもできる。TLATは、ヒストリテーブル
と同様、最も新しく使用された現在アドレスおよ
び、TLBによつて生成された対応する実アドレ
スのリストである。しかし、ヒストリテーブルに
比べて小さく、予測実アドレスと実アドレスとの
間の比較における各エラーではなく各命令解読マ
シンサイクルで更新されるという点で、ヒストリ
テーブルと異なつている。TLATは、現在アド
レスの部分とTLATの現在アドレスを比較し、
一致すれば、TLATの対応する実アドレスが予
測実アドレスになる。TLATは、最も確からし
い最新アドレスだけがTLATにあることを保証
するためにヒストリテーブルとともに作業する
（すなわち、TLATはヒストリテーブルの窓であ
る）。これは、TLATがヒストリテーブルよりも
小さいためであり、このことはTLATが少ない
比較を行い、高速の予測実アドレス生成をもたら
すことを意味している。しかし、小さいTLAT
もやはり、誤つた予測実アドレスの生成数が増え
るのを避けるために高められた正確さを要求す
る。TLATが現在アドレスの部分とその現在ア
ドレスを比較している間、ヒストリテーブルも同
じ比較を行つている。ヒストリテーブルの出力は
その後、次の解読マシンサイクルの最後に
TLATに置かれる。これは、TLATが各解読マ
シンサイクルで更新され、それによつてその正確
さを最大にしている。大きなヒストリテーブル
は、実アドレスと予測実アドレスとの間で誤つた
比較があつた場合にのみ更新される。ヒストリテ
ーブルと組み合わせたTLATは、予測実アドレ
スの高速生成を可能にすると同時に、誤つた予測
実アドレスを最小にし、それによつてキヤツシユ
アクセスシステムの全体の速度を高める。

開示されたこの発明の好ましい実施態様を第１
図に示す。デイジタルコンピユータシステムが命
令レジスタ（IR）１０に命令を送ると、第１の
記憶装置がその命令をIR１０に格納する。この
第１の記憶装置は、命令が格納された時を確実に
規定するためのラツチまたは同様の標準形式の装
置である。命令は、通常、コンピユータに記憶さ
れ、処理のために命令レジスタに順に送られる命
令のスタツクからのいくつかの命令のうちの一つ
である。命令は一連の連結されたビツトから構成
される。また、命令コード部とオペランド部の２
つの部分に分かれる。命令の上位ビツトは命令の
命令コード部に割り当てられる。命令は解読さ
れ、解読された命令コード部は算術論理演算装置
（ALU）５００に何らかの機能を実行するように
要求する。その機能がコンピユータの記憶装置か
らデータを要求する場合、コンピユータはその機
能を実行する前にそのデータを検索しなければな
らない。命令のオペランド部は、コンピユータの
メモリまたは記憶装置内にあつて、オペランドに
よつて要求されたデータの位置を指示するアドレ
ス情報を含んでいる。

命令のオペランドは、３区分に分けられる一連
のビツトであり、これらの区分のうちの２つがキ
ヤツシユメモリ内のデータの希望のアドレスを生
成する際に使用される情報を保持するコンピユー
タ内のレジスタを指定する。第３の区分はそれ自
体で希望のアドレスの生成に使用される。上位ビ
ツトは指標レジスタを指定し、中間部のビツトは
基底レジスタを指定する。指標レジスタおよび基
底レジスタは、コンピユータの汎用レジスタ
（GRP）３２０の一部である。下位群は変位ビツ
ト１６と呼ばれる。指標レジスタおよび基底レジ
スタの内容は、仮想アドレスを生成するために加
算器３１０によつて変位アドレス１６に加算され
る。仮想アドレスは、仮想アドレスレジスタ
（VAR）４０に入れられ、キヤツシユメモリのデ
ータの希望のまたは実アドレスを内容とする変換
索引緩衝機構（TLB）４２０と呼ばれる表に指
標を付けるために使用される。

キヤツシユメモリアクセスシステム５は、命令
が解読された後、要求されたデータがコンピユー
タのキヤツシユメモリ４１０内にあるかどうかを
判断する。データは通常、ワードと呼ばれる一群
のデータビツトとしてアクセスされる。データが
キヤツシユメモリ４１０にある場合、キヤツシユ
メモリアクセスシステム５は、命令の解読の後の
マシンサイクルでALU５００によつて使用され
るデータを検索する。データがコンピユータのキ
ヤツシユメモリにない場合、ALU５００は、主
記憶装置アクセスシステムからデータを受け取る
が、それはこの出願の範囲ではない。キヤツシユ
メモリアクセスシステム５は、アクセス部と検査
部の２つの部分に分かれる。アクセス部はキヤツ
シユデイレクトリ４３０、キヤツシユメモリ装置
４００およびALU５００を含んでいる。アクセ
ス部は、予測アドレス生成装置２００の使用によ
つて、キヤツシユメモリ４１０からデータを直接
検索する。検査部は、キヤツシユメモリによつて
検索されたデータが命令によつて要求されたデー
タであることを保証する。検査部は、仮想アドレ
ス生成装置３００、変換索引緩衝機構（TLB）
４２０および、（キヤツシユシステムのアクセス
部によつて生成された）予測実アドレスを検査部
内でTLB４２０によつて生成された実アドレス
と比較するための比較装置４４０とを含んでい
る。

キヤツシユメモリアレイ４１０は、それぞれ４
ラインの５１２のコングルエンスクラスに分かれ
ており、各ラインは、128バイトのデータを含み、
従つて、256Kバイトのキヤツシユメモリアレイ
となる。すべてのコングルエンスクラスのうちの
１ラインは１組を成し、従つて、メモリは、組、
コングルエンスクラスおよびライン内のバイトに
対応したビツトを選択することによつてアクセス
される。予測実アドレス生成装置（PRAGM）
２００は、その組、コングルエンスクラスの部
分、アドレスの識別を保持するためのアドレスタ
グに関係したビツトを選択する。これらの19ビツ
トは予測実アドレスの上位部分を成し、予測実ア
ドレスレジスタ（PRAR）３０の上位部分に置
かれる。仮想アドレス生成装置（VAGM）３０
０は仮想アドレスを生成し、その仮想アドレスの
一部12ビツト（ページオフセツトビツト）は、そ
のライン内のデータバイトおよびコングルエンス
クラスの部分に関係したビツトを内容としてい
る。これらのビツトは予測実アドレスの下位部分
を成し、予測実アドレスレジスタ（PRAR）３
０の下位部分に置かれる。予測実アドレス生成装
置および仮想アドレス生成装置の両方とも、その
結果を命令解読マシンサイクル中にPRAR３０
に入れる。キヤツシユメモリ装置（CMM）４０
０は、キヤツシユメモリアレイ４１０内部で、
PRAR３０にあるその予測実アドレスの位置か
らデータを順に検索する。データの検索は、命令
解読サイクルの後の、キヤツシユアクセスマシン
サイクルとも呼ばれる、マシンサイクルで実行さ
れる。

キヤツシユメモリ装置（CMM）４００が予測
実アドレスを生成し、その予測実アドレスによつ
て指定された位置のデータを検索している間、キ
ヤツシユメモリアクセスシステム５は、その予測
実アドレスが命令によつて要求されたアドレスで
あることを検査する。この検査は、命令解読マシ
ンサイクルにおいて、仮想アドレス生成装置
（VAGM）３００によつて仮想アドレスを生成す
ることによつて行われる。この仮想アドレスは仮
想アドレスレジスタ（VAR）４０に入れられ、
そのレジスタの内容は変換索引緩衝機構（TLB）
４２０のエントリと順次比較される。TLB４２
０は、VAGM３００によつて生成された潜在的
アドレスおよび、各潜在的仮想アドレスについて
の対応する実アドレス（命令によつて要求された
実際のアドレス）を含んでいる。潜在的仮想アド
レスがVAR４０の仮想アドレスと一致した場合、
TLB４２０は、一致した潜在的仮想アドレスに
対応した実アドレスを選択する。仮想アドレスに
対応する実アドレスのTLB４２０のエントリか
らの選択は、キヤツシユアクセスマシンサイクル
において行われる。

TLB４２０によつて選択された実アドレスは、
CMM４００内の比較装置に順次送られる。
CMM４００の比較装置は、PRAR３０の予測実
アドレスをTLB４２０によつて生成された実ア
ドレスと比較するためのものである。比較装置
は、その２つのアドレスをそれらが同一であるか
どうかを判断するためにビツトごとに比較する。
予測実アドレスと実アドレスの比較は、TLB４
２０の実アドレス選択の後のキヤツシユアクセス
マシンサイクルにおいて行われる。実アドレスと
予測実アドレスとの比較は、キヤツシユアクセス
マシンサイクルにおいてキヤツシユメモリアレイ
にアクセスするために使用される予測実アドレス
の検査となる。予測実アドレスと実アドレスの比
較が一致した場合、CMM４００はそのデータを
検索し、キヤツシユアクセスマシンサイクル後の
実行のためにALU５００に送る。比較が一致し
ない場合は、CMM４００は、キヤツシユメモリ
アレイ４１０内の、TLB４２０から得た実アド
レスの位置からデータを検索する。CMM４００
は、キヤツシユアクセスマシンサイクルの次のマ
シンサイクルでTLBの実アドレスからデータを
検索する。CMM４００がTLB４２０の実アドレ
スからデータを検索すると、CMM４００は実行
のためにALU５００にそのデータを送る。

CMM４００は、図示されていないが受信装置
を有しており、これが実アドレスまたは予測実ア
ドレスを受け取る。CMM４００は、自己に送ら
れたアドレスの形式（予測実アドレスまたは実ア
ドレス）にかかわらず、同一の機能を実行する。
受信装置は、受け取つたアドレスをキヤツシユデ
イレクトリ４３０内に含まれるアドレスと比較す
る。キヤツシユデイレクトリは、このデイレクト
リに登録された2Kの実アドレスに対応する512の
コングルエンスクラスを含んでいる。コングルエ
ンスクラスは、各コングルエンスクラス内に含ま
れる４の実アドレスの同一の９ビツト部分によつ
て識別される。受信装置は、デイレクトリ４３０
内の４の実アドレスの９ビツト部分を、受け取つ
たアドレスの対応する９ビツト部分と比較する。
その後、受信装置は、デイレクトリで選択された
４のアドレス値を、受け取つたアドレスがいずれ
の組に含まれているかを判断するために、受け取
つた（実または予測実）アドレスと比較する。

受信装置が受け取つたアドレスがいずれの組に
含まれているかを判断している間に、キヤツシユ
メモリは、受け取つたアドレスの一部によつてア
クセスされている。キヤツシユメモリは、１コン
グルエンスクラス内部の関係する全部のアドレス
内のデータを検索する検索装置を有している。こ
の検索装置は、デイレクトリが潜在的な４組のう
ちのいずれにデータが実際に存在するかを判断し
ている間に、すべての４のデータ位置にアクセス
する。これは、256Kのアドレスの最初の16ビツ
トにアクセスすることによつて行われる。この16
ビツトは、９ビツトのコングルエンスクラス情報
および、コングルエンスクラスの各要素内のバイ
トアドレスの７ビツトから成つている。組を判断
するための比較が完了すると、受信装置は選択信
号を検索装置に送る。その後、検索装置がデイレ
クトリから４の実アドレス位置内のデータを検索
すると、検索装置は、受け取つた（実または予測
実）アドレスについて正しいデータを検索する。
選択装置４１５を含んでいる検索装置に送られた
選択信号は、データの４バイトのうちのいずれを
選択するかを決定する。この選択はキヤツシユア
クセスサイクル後のマシンサイクルで行われ、選
択信号は、受信装置によつて検索装置に送られた
４のアドレスから独立して送信される。選択され
たデータは、キヤツシユアクセスマシンサイクル
後の第２のマシンサイクルで機能を実行する際に
そのデータを使用するALU５００に送られる。

CMM４００は、PRAGM２００および
VAGM３００から予測実アドレスを構成するビ
ツトを受け取つていたPRAR３０から予測実ア
ドレスを受け取る。PRAGM２００は、ヒスト
リテーブル２１０からPRAR３０のためのビツ
トを生成する。ヒストリテーブル２１０は、最近
の命令によつて要求された多数の最新の実アドレ
ス（ここでは128アドレス）を、命令レジスタに
指定された基底レジスタの対応する内容とともに
格納する。PRAGM２００は、IR１０に指定さ
れた基底レジスタの内容を、使用後にセーブされ
たヒストリテーブル２１０に格納された最も新し
く使用された基底レジスタの内容と比較する。比
較がヒストリテーブル２１０のこれらのエントリ
のうちの一つに一致した場合、一致した基底レジ
スタの内容に対応する、ヒストリテーブル２１０
に格納された19ビツトは、第３の記憶装置によつ
てPRAR３０の上位部分に格納される。この第
３の記憶装置は、データをレジスタに転送するた
めのラツチまたは類似形式の装置である。これら
の上位19ビツトは、アドレスタグのほか、組の選
択に関係したビツトおよび、予測実アドレスに関
係したコングルエンスクラスビツト９ビツトのう
ちの４ビツトを含む。

VAGM３００は、加算器３１０および汎用レ
ジスタ（GPR）３２０によつて予測実アドレス
に関係したビツトを生成する。加算器３１０は、
IR１０で指定されたアドレスの３の部分を加算
する装置である。変位ビツトと、基底レジスタの
内容およびIR１０で指定された指標レジスタの
内容との加算は、仮想アドレスレジスタ（VAR）
４０に入れられる31ビツトの仮想アドレスを生成
する。この仮想アドレスの下位12ビツトはページ
オフセツトビツトであり、次の上位６ビツトは仮
想アドレスのページアドレスビツトである。加算
器３１０は、IR１０から命令レジスタ（現在ア
ドレス）の変位ビツトを直接受け取り、GPR３
２０からは基底レジスタおよび指標レジスタの内
容を受け取る。PRAGMもまた、汎用レジスタ
（GPR）である基底レジスタの内容を受け取る。
加算器は初めに、１ライン内のバイトを選択する
全７ビツトと、コングルエンスクラスの選択に関
係した９ビツトのうちの５ビツトにも対応する下
位12ビツトを分解する。これらの12ビツトは
PRAR３０に送られ、第２の記憶装置は予測実
アドレスの下位部分のビツトを格納する。第２の
記憶装置は、データをレジスタに転送するための
標準のラツチまたは類似の標準装置である。

キヤツシユアクセスシステム５の効率的な動作
は、ヒストリテーブル２１０が最も新しく使用さ
れた実アドレスおよび対応する基底レジスタの内
容を持つていることを必要とする。これは、キヤ
ツシユアクセスシステム５のヒストリテーブルの
更新によつて得られる。TLB４２０によつて生
成された予測実アドレスがPRAR３０の予測実
アドレスと一致しない場合、更新装置がヒストリ
テーブル２１０を更新する。これは、そうした状
態が最新の予測アドレスが間違つており、従つて
ヒストリテーブル２１０から生成された値が誤つ
ていたことになるからである。ヒストリテーブル
２１０が更新を必要とする状況は２つある。第１
は、IR１０によつて指定された基底レジスタの
内容がヒストリテーブルのエントリと一致する
が、対応する実アドレスがTLB４２０によつて
与えられたアドレスと一致しないというヒストリ
テーブル２１０のエントリをPRAGM２００が
発見した場合である。この場合、ヒストリテーブ
ルの対応する実アドレスはTLB４２０によつて
生成された実アドレスを反映するために更新され
る。ヒストリテーブルの更新を要求する第２の状
況は、ヒストリテーブル２１０のエントリのいず
れも基底レジスタの内容と一致しない場合であ
る。この状況では、ヒストリテーブル２１０の最
低使用頻度エントリがIR１０で指定された基底
レジスタの内容およびTLB４２０によつて生成
された対応する実アドレスで置き換えられる。ヒ
ストリテーブル２１０を更新する上記の方法は、
ヒストリテーブル２１０が完全に連想型であるこ
と、すなわち唯一の組を含むことを前提とする。
ヒストリテーブル２１０が複数の組を含むセツト
アソシエイテイブであり、さらに、基底レジスタ
とヒストリテーブル２１０の内容の間にまつたく
一致が見られない場合、基底レジスタの部分的な
内容によつて選択された組の最低使用頻度エント
リは、むしろ全体のヒストリテーブル２１０の最
低使用頻度エントリで置き換えられる。

開示された発明のこの実施態様は、キヤツシユ
メモリアレイ４１０に２つの別なアドレスによつ
てアクセスする。第１は、命令が要求するデータ
の位置の“最善の推測”である予測実アドレスで
ある。この推測は、ヒストリテーブル２１０およ
び加算器３１０によつて生成される。ヒストリテ
ーブル２１０は、実アドレスおよび、GPR３２
０からのその対応する基底レジスタ内容をリスト
にする。ヒストリテーブル２１０は、最近使用さ
れた基底レジスタのリストからの最近使用された
基底レジスタの内容を、IR１０で指定された現
在の基底レジスタの内容と突き合わせる。ヒスト
リテーブル２１０はその後、その最近使用された
基底レジスタの内容に対応する実アドレスを選択
し、それをPRAR３０の上位ビツトに入れる。
加算器３１０は、現在の基底レジスタの内容、指
標レジスタの内容および、IR１０からの変位ビ
ツトを加算し、これらの31ビツトをVAR２０に
入れる。これはまた、加算器からの、初期に分解
された下位12ビツトも受け取り、それらを
PRAR３０の下位12ビツトに入れる。PRARの
この31ビツトはその後、キヤツシユアレイにアク
セスするために使用される。“推測”が正しけれ
ば、キヤツシユメモリはそのデータを実行のため
にALU５００に送る。推測が間違つている場合、
TLB２１０から生成された実アドレスがキヤツ
シユアレイにアクセスするために使用される。

PRAR３０からの推測は、比較装置４２５に
おいて、予測実アドレスとTLB２１０によつて
生成された実アドレスを比較することによつて検
査される。この比較は、キヤツシユアレイが予測
実アドレス位置にあるデータを検索している間に
行われる。実アドレスは、VAR４０の仮想アド
レスを、VAGM３００によつて生成される可能
な仮想アドレスおよびその対応する実アドレスを
含むTLBのエントリと突き合わせることによつ
て生成される。VAR４０の仮想アドレスがTLB
４２０のエントリと一致しない場合、対応する実
アドレスをコンパイルするために処理が開始され
なければならない。これは仮想記憶装置計算機に
おける従来の段階であり、この出願の範囲ではな
い。ALU５００に送られたデータは、“推測”が
間違つていた場合、１マシンサイクル遅れる。メ
モリアレイがその間違つた“推測”（予測実）ア
ドレスでアクセスされた後に、実アドレスによつ
てメモリが再アクセスされなければならないため
である。間違つた推測は、TLB４２０からの新
しい現在アドレスおよび対応する実アドレスによ
つてヒストリテーブル２１０を更新することによ
つて最低限に抑えられる。ヒストリテーブルは、
推測が間違つていると判断された場合に更新され
る。ヒストリテーブルにすでにある現在アドレス
は、単にその置き換えられた実アドレスを持つて
いるにすぎず、一方、ヒストリテーブルにない現
在アドレスは、ヒストリテーブルが更新されなけ
ればならない場合、存在する現在の命令およびそ
の対応する実アドレスを置き換える。

この発明の別な実施態様を第３図に示す。この
実施態様は、PRAGM２００が変換予見テーブ
ル（TLAT）２２０も有していることを除き、
第１の実施態様と同様である。このTLAT２２
０は、コンピユータシステムで使用可能な、この
発明では16ある、各GPRについて最近使用され
た実アドレスエントリを有する小さいヒストリテ
ーブルである。基底レジスタがIR１０によつて
指定されると、指定された基底レジスタに対応す
る、TLAT２２０の最近使用された実アドレス
エントリに関係する19ビツトは、PRAR３０の
上位位置に置かれる。これは、４ビツトの基底レ
ジスタ識別子にもTLAT２２０のエントリを指
定させることによつて、第３図に示す。これらの
19ビツトは、PRAR３０の予測実アドレスを形
成するために、加算器３１０からの（PRAR３
０の下位位置に置かれた）12ビツトのページオフ
セツトビツトと連結される。

この実施態様では、より大きなヒストリテーブ
ル２１０は、マシンサイクルごとにTLAT２２
０を更新するために使用される。TLATは、そ
のサイクルにおいて更新できるように、解読マシ
ンサイクルの期間内で読み書きできるアレイを必
要とする。GPR（潜在的な基底レジスタ）の内容
が命令の実行の結果として修正された場合、この
変更されたGPRの新しい内容は、ヒストリテー
ブル２１０の対応する予測実アドレスエントリを
検索するために使用される。この予測実アドレス
はその後、このGPRに対応するTLAT２２０の
エントリを置き換えるために使用される。ヒスト
リテーブル２２０の更新処理は、第１の実施態様
に説明した処理と同様である。予測実アドレスが
TLB４２０からの実アドレスと一致しない場合、
ヒストリテーブルはTLB４２０からの実アドレ
スによつて更新されなければならない。TLAT
２２０もまた、ヒストリテーブル２１０の変更を
反映するために、上述の処理と同様に更新されな
ければならない。

TLAT２２０は、本質的に、大きなヒストリ
テーブル２１０への窓として作用する。計算機は
固定された組のGPR３２０を持つことしかでき
ず、TLAT２２０は必ず各GPRについての予測
実アドレスを持つているので、この技法は、いず
れのGPRが現在の基底レジスタとして使用され
ているかにかかわらず、第１の実施態様で説明し
た方法と同じ正確さで実アドレスを予測できる。
さらに、TLATは非常に小さいアレイであり、
そのアクセスはGPRのアクセスと平行して行わ
れるので、アレイへのアクセスを極めて高速に可
能にする。従つて、この実施態様で説明された二
重テーブル（TLATおよびヒストリテーブル）
方式は、同じ正確さをもつて、第１の実施態様で
説明した技法よりも高速の実アドレス予測方法を
提供する。

【図面の簡単な説明】

第１図は、この発明に従つたキヤツシユアクセ
スシステムの第１の実施態様を示す図、第２図
は、この発明のデイジタルコンピユータシステム
で実施される一般的なパイプライン構造を示す
図、第３図は、この発明に従つたキヤツシユアク
セスシステムの別な実施態様を示す図である。５……キヤツシユメモリアクセスシステム、１
０……命令レジスタ、３０……予測実アドレスレ
ジスタ、４０……仮想アドレスレジスタ、２００
……予測実アドレス生成装置、２１０……ヒスト
リテーブル、２２０……変換予見テーブル、３０
０……仮想アドレス生成装置、３１０……加算
器、３２０……汎用レジスタ、４００……キヤツ
シユメモリ装置、４１０……キヤツシユメモリ、
４１５……選択装置、４２０……変換索引緩衝機
構、４２５……比較装置、４３０……キヤツシユ
デイレクトリ、５００……算術論理演算装置。

Claims

【特許請求の範囲】１キヤツシユメモリと、命令レジスタと、仮想
アドレスレジスタと、予測実アドレスレジスタ
と、算術論理回路と、ベースレジスタとインデツ
クスレジスタの用途で用いることができる複数の
汎用レジスタと、を具備するキヤツシユメモリア
クセスシステムであつて、前記命令レジスタに受け入れられた命令を解読
して、前記ベースレジスタに含まれる現在アドレ
スと前記インデツクスレジスタと前記命令レジス
タの変位ビツトから前記仮想アドレスを生成し、
それを前記仮想アドレスレジスタに記憶する仮想
アドレス生成手段と、前記ベースレジスタにおいてすでに使用された
現在アドレスの一群とそれに対応する実アドレス
の一群を格納するヒストリーテーブルと、前記ベ
ースレジスタに含まれる前記現在アドレスと前記
すでに使用された現在アドレスの一群とを比較す
る第一の比較手段と、を有する予測実アドレス発
生手段であつて、前記第一の比較手段による比較
の結果前記一致した時には、対応する実アドレス
を予測実アドレスとして前記予測実アドレスレジ
スタに格納し、第一マシンサイクル中に前記予測実アドレスレ
ジスタから前記予測実アドレスを受取り、第一マ
シンサイクルが終了する以前に前記予測実アドレ
スの位置にあるデータをアクセスするキヤツシユ
メモリ手段と、第一の仮想アドレス群に対応する第二の実アド
レス群を有し、前記仮想アドレスレジスタに格納
された仮想アドレスを第一の実アドレスに変換す
る変換索引バツフア機構と、前記第一の実アドレスを前記予測実アドレスと
比較する第二の比較手段と、を含み、前記キヤツシユメモリ手段は前記第二の比較手
段による比較の結果、一致した時には前記予測実
アドレスに基づいてアクセスしたデータを前記算
術論理回路に送り、一致しなかつた場合には前記
第一の実アドレスを受け取つて第二のマシンサイ
クル中に前記実アドレスに基づいてデータをアク
セスし、該データを第三のマシンサイクル中に前
記算術論理回路に送ることを特徴としたキヤツシ
ユメモリアクセスシステム。２キヤツシユメモリアクセスシステムをアクセ
スする方法であつて、与えられた命令を解読して前記命令に関するア
ドレス情報を含んでいる汎用レジスタを特定する
ステツプと、前記汎用レジスタに記憶された内容の一部であ
る現在アドレスと最近使用された前記現在アドレ
スおよびそれに対応する実アドレスを含むヒスト
リーテーブルの内容とを比較して予測実アドレス
を生成するステツプと、前記予測実アドレスに基づいて第一のマシンサ
イクル中に前記キヤツシユメモリをアクセスして
第一のデータを得るステツプと、前記アドレス情報に基づいて仮想アドレスを生
成し、加算器・変換索引バツフア機構を介してそ
れに対応する実アドレスを生成するステツプと、前記予測実アドレスと前記実アドレスを比較
し、一致を見た場合においては前記第一のデータ
を前記命令の実行に使用するデータとして採用
し、一致しない場合においては第二のマシンサイ
クル中に前記実アドレスに基づいて前記キヤツシ
ユメモリをアクセスし、そのデータを前記命令の
実行に使用するデータとして採用するステツプ
と、を具備する方法。