JPH0371355A - キヤツシユ検索装置および検索方法 - Google Patents
キヤツシユ検索装置および検索方法Info
- Publication number
- JPH0371355A JPH0371355A JP2205332A JP20533290A JPH0371355A JP H0371355 A JPH0371355 A JP H0371355A JP 2205332 A JP2205332 A JP 2205332A JP 20533290 A JP20533290 A JP 20533290A JP H0371355 A JPH0371355 A JP H0371355A
- Authority
- JP
- Japan
- Prior art keywords
- cache
- line
- address
- directory
- page
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0877—Cache access modes
- G06F12/0882—Page mode
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/10—Address translation
- G06F12/1027—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
- G06F12/1045—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] associated with a data cache
- G06F12/1063—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] associated with a data cache the data cache being concurrently virtually addressed
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
Ａ、産業上の利用分野
本発明は情報ハンドリング・システムにおいてキャッシ
ュ装置にミスが発生した際、主記憶装置からデータを得
るに必要なサイクル数を減少させようとするものである
。
ュ装置にミスが発生した際、主記憶装置からデータを得
るに必要なサイクル数を減少させようとするものである
。
Ｂ、従来技術および課題
一般的な多重レベル・データ記憶装置ではキャッシュ・
ディレクトリはコラムおよび行からなるハードウェア配
列として構成されている。ディレクトリの行はクラスの
適合を示し、行中のコラム数はキャッシュの関連性を示
す。キャッシュ・ディレクトリの各エントリはキャッシ
ュ・メモリ中の記憶データのラインについての情報を含
む。仮想アドレス・キャッシュにおいては、ディレクト
リは仮想アドレスの最上位ビット、主記憶装置中のデー
タ入力位置を示すページ・アドレスおよび記憶保護ビッ
ト等を含む。
ディレクトリはコラムおよび行からなるハードウェア配
列として構成されている。ディレクトリの行はクラスの
適合を示し、行中のコラム数はキャッシュの関連性を示
す。キャッシュ・ディレクトリの各エントリはキャッシ
ュ・メモリ中の記憶データのラインについての情報を含
む。仮想アドレス・キャッシュにおいては、ディレクト
リは仮想アドレスの最上位ビット、主記憶装置中のデー
タ入力位置を示すページ・アドレスおよび記憶保護ビッ
ト等を含む。
仮想アドレス・キャッシュにおいてデータ要求があった
場合、キャッシュ・ディレクトリのアドレスには仮想ア
ドレス位置が使用される。適当なコングルエンド・クラ
スがディレクトリから選択され、現アドレスの最上位ビ
ットとディレクトリ中の対応仮想アドレス・ビットとの
比較が実行される。一致がない場合はキャッシュにデー
タがなく、主記憶装置からのフェッチが必要となる。
場合、キャッシュ・ディレクトリのアドレスには仮想ア
ドレス位置が使用される。適当なコングルエンド・クラ
スがディレクトリから選択され、現アドレスの最上位ビ
ットとディレクトリ中の対応仮想アドレス・ビットとの
比較が実行される。一致がない場合はキャッシュにデー
タがなく、主記憶装置からのフェッチが必要となる。
主記憶装置からのフェッチにはキャッシュのアドレスに
使用される仮想アドレスを実アドレスに変換することが
必要となる。変換処理は一般的に主記憶装置からのアク
セスが可能となる以前に１つ、あるいはそれ以上のテー
ブル検索を必要とする。
使用される仮想アドレスを実アドレスに変換することが
必要となる。変換処理は一般的に主記憶装置からのアク
セスが可能となる以前に１つ、あるいはそれ以上のテー
ブル検索を必要とする。
キャッシュにおける処理の改善の１つとして変換索引緩
衝機構（ＴＬＢ）の使用がある。これはキャッシュにお
けるミスの発生の際にＴＬＢが所望データの変換アドレ
スを有しているというものである。これによればアドレ
ス変換に要する時間を削減でき、データは即座に主記憶
装置からフェッチできる。しかし、ＴＬＢはハードウェ
ア・コストの増大を招くこととなり、常に望ましい形態
であるとは言えない。
衝機構（ＴＬＢ）の使用がある。これはキャッシュにお
けるミスの発生の際にＴＬＢが所望データの変換アドレ
スを有しているというものである。これによればアドレ
ス変換に要する時間を削減でき、データは即座に主記憶
装置からフェッチできる。しかし、ＴＬＢはハードウェ
ア・コストの増大を招くこととなり、常に望ましい形態
であるとは言えない。
Ｃ６発明の概要および解決ｎ題
本発明はＴＬＢを使用せずにキュツシュの実効を改善す
るものである。
るものである。
本発明の１つの実施例はキャッシュ・ディレクトリの各
エントリがデータの入力された主記憶装置のページの実
アドレスおよび仮想アドレスの最上位ビット両者を含む
仮想アドレス・キャッシュを用いたコンピュータ・シス
テムである。キャッシュのパフォーマンスは所定のシー
ケンスに従って主記憶装置の同一ページからのラインを
エントリとして置くことで、ページごとのライン検索を
可能として改善したものである。これによって希望のラ
インが発見できなくても、すでにキャッシュ中にある同
じページの異なるラインを検索することが可能となる。
エントリがデータの入力された主記憶装置のページの実
アドレスおよび仮想アドレスの最上位ビット両者を含む
仮想アドレス・キャッシュを用いたコンピュータ・シス
テムである。キャッシュのパフォーマンスは所定のシー
ケンスに従って主記憶装置の同一ページからのラインを
エントリとして置くことで、ページごとのライン検索を
可能として改善したものである。これによって希望のラ
インが発見できなくても、すでにキャッシュ中にある同
じページの異なるラインを検索することが可能となる。
この場合、第２ラインの実アドレスが第１ラインのアド
レス形成に使用され、これによってアドレス変換処理が
省略できる。その後、希望データが主記憶装置から直接
フェッチされる。
レス形成に使用され、これによってアドレス変換処理が
省略できる。その後、希望データが主記憶装置から直接
フェッチされる。
Ｄ、実施例
第１図に２レベル・キャッシュを持つ従来のプロセッサ
・システム１０のブロック図を示す。プロセッサＣＰＵ
１４はＬ１キャッシュ１３とＬ２キャッシュ１２を介し
て主記憶装置（ＭＳ）１１に接続されている。主記憶装
置１１はさらにＩ１０装置１５に接続されている。Ｌ２
キャッシュ１２はアレイ１２ａとコントロール部１２ｂ
とを含む。主記憶装置１１とＬ２キャッシュ間には制御
パスおよびデータ・バスがある。ＣＰＵ１４がデータ要
求をする時は仮想アドレスを持っＬ１キャッシュ１３ヘ
データ要求を行う。Ｌ１キャッシュ１３では要求データ
の検索がなされる。データがＬ１キャッシュ１３中に存
在するときはＣＰＵに転送され処理が再開される。デー
タがＬ１キャッシュ１３に無いときはＬ１キャッシュ１
３はＬ２キャッシュ１２にデータ要求を行う。仮想アド
レスＬ２キャッシュ１２においてデータ検索が実行され
る。データが見つかるとＬ１キャッシュ１３に戻され、
ここからＣＰＬＩ １４に送られる。Ｌ２キャッシュ中
にデータが無いときは主記憶装置１１からのフェッチが
必要となる。主記憶装置１１からのフェッチに際しては
Ｌ２キャッシュ１２で使用した仮想アドレスの実アドレ
スへの変換が必要となる。変換処理は一般的に主記憶装
置からデータ・アクセスが実行される前に１つ、あるい
はそれ以上のテーブル検索を必要とする。
・システム１０のブロック図を示す。プロセッサＣＰＵ
１４はＬ１キャッシュ１３とＬ２キャッシュ１２を介し
て主記憶装置（ＭＳ）１１に接続されている。主記憶装
置１１はさらにＩ１０装置１５に接続されている。Ｌ２
キャッシュ１２はアレイ１２ａとコントロール部１２ｂ
とを含む。主記憶装置１１とＬ２キャッシュ間には制御
パスおよびデータ・バスがある。ＣＰＵ１４がデータ要
求をする時は仮想アドレスを持っＬ１キャッシュ１３ヘ
データ要求を行う。Ｌ１キャッシュ１３では要求データ
の検索がなされる。データがＬ１キャッシュ１３中に存
在するときはＣＰＵに転送され処理が再開される。デー
タがＬ１キャッシュ１３に無いときはＬ１キャッシュ１
３はＬ２キャッシュ１２にデータ要求を行う。仮想アド
レスＬ２キャッシュ１２においてデータ検索が実行され
る。データが見つかるとＬ１キャッシュ１３に戻され、
ここからＣＰＬＩ １４に送られる。Ｌ２キャッシュ中
にデータが無いときは主記憶装置１１からのフェッチが
必要となる。主記憶装置１１からのフェッチに際しては
Ｌ２キャッシュ１２で使用した仮想アドレスの実アドレ
スへの変換が必要となる。変換処理は一般的に主記憶装
置からデータ・アクセスが実行される前に１つ、あるい
はそれ以上のテーブル検索を必要とする。
第２図はプロセッサ１４（ＣＰＵ）に接続された第１レ
ベルＬ１キヤツシユ１３と、これに対するサービスを実
行する１メガバイト（ＩＭＢ ）の第２レベル・キャッ
シュ上２に基づく本発明の動作を示す図である。Ｌ２キ
ャッシュ１２は１キロバイト（ＩＫＢ）の大きさを有し
、キャッシュ中のデータの各１キロブロツクに対応する
のは仮想アドレス２１（０：２９）および主記憶装置か
らのデータアドレスである実４ＫＢページアドレス２３
（１８：３５）の最上位ビットを含むディレクトリ２０
のエントリとなる。
ベルＬ１キヤツシユ１３と、これに対するサービスを実
行する１メガバイト（ＩＭＢ ）の第２レベル・キャッ
シュ上２に基づく本発明の動作を示す図である。Ｌ２キ
ャッシュ１２は１キロバイト（ＩＫＢ）の大きさを有し
、キャッシュ中のデータの各１キロブロツクに対応する
のは仮想アドレス２１（０：２９）および主記憶装置か
らのデータアドレスである実４ＫＢページアドレス２３
（１８：３５）の最上位ビットを含むディレクトリ２０
のエントリとなる。
ディレクトリ２０の１０２４個のエントリは２５６のア
ドレスのアレイ、および４セツト（Ａ。
ドレスのアレイ、および４セツト（Ａ。
Ｂ、Ｃ，Ｄ）のコングルエンド・クラスに整理される。
ディレクトリは仮想アドレスのビット３０から３７によ
ってアドレスされているので、どの仮想アドレスがディ
レクトリ中のどの列あるいはコングルエンド・クラスに
置かれているかを判別するのは容易である。仮想アドレ
ス領域の最初のＩＫＢブロックの仮想アドレスは最初の
列あるいはコングルエンド・クラス（クラス０またはア
ドレスＯ）に配置されている。仮想アドレス領域の第２
のＩＫＢブロックの仮想アドレスは第２コングルエンド
・クラスに配置される。同様に仮想アドレス領域の２５
５番目のＩＫＢブロックまでがコングルエンド・クラス
２５５まで配される。マツピングはその後ブロック２５
６がコングルエンド・クラスＯとなるように繰り返され
る。これを第３図に示す。
ってアドレスされているので、どの仮想アドレスがディ
レクトリ中のどの列あるいはコングルエンド・クラスに
置かれているかを判別するのは容易である。仮想アドレ
ス領域の最初のＩＫＢブロックの仮想アドレスは最初の
列あるいはコングルエンド・クラス（クラス０またはア
ドレスＯ）に配置されている。仮想アドレス領域の第２
のＩＫＢブロックの仮想アドレスは第２コングルエンド
・クラスに配置される。同様に仮想アドレス領域の２５
５番目のＩＫＢブロックまでがコングルエンド・クラス
２５５まで配される。マツピングはその後ブロック２５
６がコングルエンド・クラスＯとなるように繰り返され
る。これを第３図に示す。
アドレスが特定のコングルエンド・クラスに配分される
と、仮想アドレスはセットＡ、セットＢ５セットＣおよ
びセットＤの４つの場所のいずれかに置かれる。これは
このキャッシュが４つの関連セットからなることに基づ
く。コングルエンド・クラスの１つあるいはそれ以上が
空または無効であるとき、セットはそれらすべてが使用
可能となるまで予め定められた順序に満たされる。セッ
トがすべて満たされているとき、あるいは使用されてい
るときは最新の使用セットは追い出され（データは主記
憶装置に戻される）、仮想アドレスがセット中に置かれ
る。
と、仮想アドレスはセットＡ、セットＢ５セットＣおよ
びセットＤの４つの場所のいずれかに置かれる。これは
このキャッシュが４つの関連セットからなることに基づ
く。コングルエンド・クラスの１つあるいはそれ以上が
空または無効であるとき、セットはそれらすべてが使用
可能となるまで予め定められた順序に満たされる。セッ
トがすべて満たされているとき、あるいは使用されてい
るときは最新の使用セットは追い出され（データは主記
憶装置に戻される）、仮想アドレスがセット中に置かれ
る。
Ｌ１キャッシュ１３がＬ２キャッシュ１２の要求を生じ
させるときの通常のシーケンスはＬ２キャッシュ１２の
ディレクトリ２０のエントリ検索である。Ｌ２キャッシ
ュ・ディレクトリ２０は４８ビツト仮想アドレス中の３
０から３７までのビットで第１アドレツシングによって
検索される。
させるときの通常のシーケンスはＬ２キャッシュ１２の
ディレクトリ２０のエントリ検索である。Ｌ２キャッシ
ュ・ディレクトリ２０は４８ビツト仮想アドレス中の３
０から３７までのビットで第１アドレツシングによって
検索される。
アドレス・クラスの４つのセットが読み取られ、クラス
中の各セットの記憶仮想アドレスである３Ｏビツトが保
護ビットとともに比較される。一致があれば、所望デー
タはキャッシュ中に存在し、「ヒツト」信号がヒツト／
ミス・ロジック６６から送られる。一致が無い場合は「
ミス」信号が送られ、Ｌ２キャッシュ１２は主記憶装置
へのデータ要求を続行する。
中の各セットの記憶仮想アドレスである３Ｏビツトが保
護ビットとともに比較される。一致があれば、所望デー
タはキャッシュ中に存在し、「ヒツト」信号がヒツト／
ミス・ロジック６６から送られる。一致が無い場合は「
ミス」信号が送られ、Ｌ２キャッシュ１２は主記憶装置
へのデータ要求を続行する。
Ｌ２キャッシュ１２の主記憶装置１１へのデータ要求に
際しては、Ｌ２キャッシュ１２でのアドレスに使用した
仮想アドレスをアドレス変換アルゴリズムを介して実ア
ドレスへ変換することが必要となる。このアルゴリズム
は、まず主記憶装置に対してページ・テーブル・エント
リに続くハツシュ・テーブル・エントリを要求する。ペ
ージ・フレーム・テーブルの要求の数はページ・テーブ
ル・エントリの連鎖が発生したかどうかに依存する。最
終的にデータが主記憶装置に存在するときは、所望のＩ
Ｋライン・データの要求が主記憶装置になされる。
際しては、Ｌ２キャッシュ１２でのアドレスに使用した
仮想アドレスをアドレス変換アルゴリズムを介して実ア
ドレスへ変換することが必要となる。このアルゴリズム
は、まず主記憶装置に対してページ・テーブル・エント
リに続くハツシュ・テーブル・エントリを要求する。ペ
ージ・フレーム・テーブルの要求の数はページ・テーブ
ル・エントリの連鎖が発生したかどうかに依存する。最
終的にデータが主記憶装置に存在するときは、所望のＩ
Ｋライン・データの要求が主記憶装置になされる。
本発明の第１、第２Ｌ２キヤツシユ・ディレクトリ検索
方法および装置においては、同じ４にページからの他の
ＩＫラインがＬ２キャッシュ１２に存在するとき、主記
憶装置に対するハツシュ・テーブル・エントリおよびペ
ージ・フレーム・テーブル・エントリの要求を省略でき
る。Ｌ２キャッシュ１２中の各エントリは主記憶装置１
１に対して有効な４にページの実アドレスを含んでいる
。従って、所望ラインがＬ２キャッシュ１２中にある同
一ページの異なるラインであるときは、主記憶装置１１
に対してハツシュ・テーブルおよびページ・フレーム・
テーブル・エントリの要求を発する必要がないのである
。これはＬ２キャッシュ・ディレクトリ２０中に互いに
特定の関連を持つ実記憶の同一４にページからのライン
・エントリを置くことで達成される。
方法および装置においては、同じ４にページからの他の
ＩＫラインがＬ２キャッシュ１２に存在するとき、主記
憶装置に対するハツシュ・テーブル・エントリおよびペ
ージ・フレーム・テーブル・エントリの要求を省略でき
る。Ｌ２キャッシュ１２中の各エントリは主記憶装置１
１に対して有効な４にページの実アドレスを含んでいる
。従って、所望ラインがＬ２キャッシュ１２中にある同
一ページの異なるラインであるときは、主記憶装置１１
に対してハツシュ・テーブルおよびページ・フレーム・
テーブル・エントリの要求を発する必要がないのである
。これはＬ２キャッシュ・ディレクトリ２０中に互いに
特定の関連を持つ実記憶の同一４にページからのライン
・エントリを置くことで達成される。
この特定の関連とは、例えば検索される順番の列にコン
グルエンド・クラス中の同一の４にページからのＩＫラ
インを配置することである０例えば、所定ページの第１
１にラインは第１列２１ａに、ベージＯの第２１ＫＢラ
インは第２列２１ｂに、ベージＯの第３ラインは第３列
２１ｃに、べ一ジＯの第４ラインは列２１ｄに配置され
る。
グルエンド・クラス中の同一の４にページからのＩＫラ
インを配置することである０例えば、所定ページの第１
１にラインは第１列２１ａに、ベージＯの第２１ＫＢラ
インは第２列２１ｂに、ベージＯの第３ラインは第３列
２１ｃに、べ一ジＯの第４ラインは列２１ｄに配置され
る。
第４図は同一の４にページからのＩＫバイト・ラインが
いかにしてディレクトリのＡセットに配置されるかを示
すディレクトリの１つのタイプの詳細を示したものであ
る。各セットには６４（Ｏ〜６３）ページがある。ペー
ジの４つのＩＫバイト・ラインは同時にデコード・ロジ
ック４１〜４４およびコンパレータ５１〜５４の出力へ
供給される。
いかにしてディレクトリのＡセットに配置されるかを示
すディレクトリの１つのタイプの詳細を示したものであ
る。各セットには６４（Ｏ〜６３）ページがある。ペー
ジの４つのＩＫバイト・ラインは同時にデコード・ロジ
ック４１〜４４およびコンパレータ５１〜５４の出力へ
供給される。
例えば、ビット３０〜３５がすべてゼロのページゼロの
ライン１１０．２１０．３１０および４１０はデコード
・ロジック４１〜４４およびコンパレータ５１〜５４の
出力へ供給される。このディレクトリにおけるデータの
配置はディレクトリの他のセット（Ｂ、ＣおよびＤ）に
おいても同様である。第４図から、Ｌ２ディレクトリに
おいて所望のＩＫバイト・ラインの検索がされる際、デ
ィレクトリに存在するであろうデータの同じ４にバイト
・ページからの他のＩＫバイト・ラインがあるすべての
コングルエンド・クラスは同時に検索されることが分か
る。これらの検索対象となる他のコングルエンド・クラ
スは他の４にバイト・ページからのデータを含むもので
ある。しかし、同じ４にバイト・ページからの他のライ
ンがキャッシュ中に存在するときは、そのラインに関す
る情報はディレクトリ中において検索されるディレクト
リ位置の１つにのみ存在しうることとなる。仮想アドレ
スの３６および３７ビツトは検索対象となる第１ライン
・アドレスを決定する。残りの３つのコングルエンド・
クラスは同じ４にページからの他の可能なライン（第２
ライン）が配置される位置を示す。
ライン１１０．２１０．３１０および４１０はデコード
・ロジック４１〜４４およびコンパレータ５１〜５４の
出力へ供給される。このディレクトリにおけるデータの
配置はディレクトリの他のセット（Ｂ、ＣおよびＤ）に
おいても同様である。第４図から、Ｌ２ディレクトリに
おいて所望のＩＫバイト・ラインの検索がされる際、デ
ィレクトリに存在するであろうデータの同じ４にバイト
・ページからの他のＩＫバイト・ラインがあるすべての
コングルエンド・クラスは同時に検索されることが分か
る。これらの検索対象となる他のコングルエンド・クラ
スは他の４にバイト・ページからのデータを含むもので
ある。しかし、同じ４にバイト・ページからの他のライ
ンがキャッシュ中に存在するときは、そのラインに関す
る情報はディレクトリ中において検索されるディレクト
リ位置の１つにのみ存在しうることとなる。仮想アドレ
スの３６および３７ビツトは検索対象となる第１ライン
・アドレスを決定する。残りの３つのコングルエンド・
クラスは同じ４にページからの他の可能なライン（第２
ライン）が配置される位置を示す。
キャッシュ中に記憶された仮想アドレス・ビットはコン
パレータ５１〜５４のディレクトリ・アドレス・レジス
タ（ＤＡＲ）中に記憶された仮想アドレス・ビット（０
：２９）と比較される。もしこれら２つのビットのセッ
トが一致すれば、比較出力は活性化され、データの希望
のＩＫバイト・ラインがキャッシュ中に存在し、および
／またはデータの同一４にページからのＩＫラインがキ
ャッシュ中に存在することを示す。この情報は第２図に
示すヒツト／ミス・ロジック６６に転送される。第１ク
ラスにおいてヒツトがあると「ヒツト第１クラス」ライ
ンが活性化される。「ヒツト第１クラス」の制動に必要
なロジックの詳細については第６図で示す。第６図から
、ヒツト・クラス０，１．２または３ラインが活性化さ
れ、対応アドレス・ビット（３６および３７）が活性化
されると、「ヒツト第１クラス」ラインが活性化される
ことが理解される。
パレータ５１〜５４のディレクトリ・アドレス・レジス
タ（ＤＡＲ）中に記憶された仮想アドレス・ビット（０
：２９）と比較される。もしこれら２つのビットのセッ
トが一致すれば、比較出力は活性化され、データの希望
のＩＫバイト・ラインがキャッシュ中に存在し、および
／またはデータの同一４にページからのＩＫラインがキ
ャッシュ中に存在することを示す。この情報は第２図に
示すヒツト／ミス・ロジック６６に転送される。第１ク
ラスにおいてヒツトがあると「ヒツト第１クラス」ライ
ンが活性化される。「ヒツト第１クラス」の制動に必要
なロジックの詳細については第６図で示す。第６図から
、ヒツト・クラス０，１．２または３ラインが活性化さ
れ、対応アドレス・ビット（３６および３７）が活性化
されると、「ヒツト第１クラス」ラインが活性化される
ことが理解される。
もし、第１クラスに関してミスとなり、コンパレータ５
１〜５４（第２クラス・ビット）関してヒツトとなった
ときは第２図に示す「ヒツト第２クラス」のラインが活
性化される。この「ヒツト第２クラス」の活性化に必要
なロジックについては第６図に詳細を示す。第２ライン
の実アドレスは第１のＩＫラインのアドレスの構成に使
用され、これによってハツシュ・テーブルおよびページ
・フレーム・テーブルのエントリのために主記憶装置に
おいて実行される２つあるいはそれ以上のアクセスが省
略できる。主記憶装置に対する唯一のアクセスは所望の
データのＩＫラインのために実行される。
１〜５４（第２クラス・ビット）関してヒツトとなった
ときは第２図に示す「ヒツト第２クラス」のラインが活
性化される。この「ヒツト第２クラス」の活性化に必要
なロジックについては第６図に詳細を示す。第２ライン
の実アドレスは第１のＩＫラインのアドレスの構成に使
用され、これによってハツシュ・テーブルおよびページ
・フレーム・テーブルのエントリのために主記憶装置に
おいて実行される２つあるいはそれ以上のアクセスが省
略できる。主記憶装置に対する唯一のアクセスは所望の
データのＩＫラインのために実行される。
以下は本発明で適用されるフェッチ処理の詳細例である
。この例のハードウェアについては第２図で、タイミン
グ相関については第５図で理解できる。
。この例のハードウェアについては第２図で、タイミン
グ相関については第５図で理解できる。
ディレクトリ・アドレス・レジスタ（ＤＡＲ）３１およ
びキャッシュ・アドレス・レジスタ（ＣＡＲ）３３はロ
ー・レベルＬ１キャッシュの要求によって第１仮想アド
レスとともにロードされる。
びキャッシュ・アドレス・レジスタ（ＣＡＲ）３３はロ
ー・レベルＬ１キャッシュの要求によって第１仮想アド
レスとともにロードされる。
第１クラスの４つのセットのディレクトリ２０中の仮想
アドレス・ビット（０：２９’）および第２クラスの１
２セツトはＤＡＦＬ３１中の仮想アドレス・ビット（０
：２９）とコンパレータ５０〜６５において比較される
。
アドレス・ビット（０：２９’）および第２クラスの１
２セツトはＤＡＦＬ３１中の仮想アドレス・ビット（０
：２９）とコンパレータ５０〜６５において比較される
。
もし、Ｌ２ディレクトリ比較・サイクル（第５図におけ
るクロック３）において、ミス（一致なし）が第１クラ
スにおいて発生し、ヒツト（一致あり）が第２クラスに
おいて発生した場合は、ＣＡＲレジスタ３３における第
１アドレスは第２りラス・アドレスに更新（例えばビッ
ト３６．３７が第１アドレスに更新）される。第２クラ
ス・アドレスのビット３６．８７は第７図の構成により
、以下の表に示すように決定される。
るクロック３）において、ミス（一致なし）が第１クラ
スにおいて発生し、ヒツト（一致あり）が第２クラスに
おいて発生した場合は、ＣＡＲレジスタ３３における第
１アドレスは第２りラス・アドレスに更新（例えばビッ
ト３６．３７が第１アドレスに更新）される。第２クラ
ス・アドレスのビット３６．８７は第７図の構成により
、以下の表に示すように決定される。
第１クラスからの２つのビット３６．３７は再使用のた
めに２つのビット・ラッチ６８に保持される。クロック
４において、ＣＡＦｔレジスタ３３に関する制御ビット
は、ＣＡＲ３３が優先権を確認したときに線７０１：介
してＤＡＲ３１にロードされる第２クラス・アドレスを
発生させる。上述のラッチに保持された２つの第１ビツ
ト３６．３７はＣＡＲレジスタ３３に再ロードされる。
めに２つのビット・ラッチ６８に保持される。クロック
４において、ＣＡＦｔレジスタ３３に関する制御ビット
は、ＣＡＲ３３が優先権を確認したときに線７０１：介
してＤＡＲ３１にロードされる第２クラス・アドレスを
発生させる。上述のラッチに保持された２つの第１ビツ
ト３６．３７はＣＡＲレジスタ３３に再ロードされる。
ＣＡＲレジスタ３３は主記憶装置１１からＬ２キャッシ
ュ１２ヘデータをロードするため使用される第１クラス
の仮想アドレスを有することとなる。
ュ１２ヘデータをロードするため使用される第１クラス
の仮想アドレスを有することとなる。
ＤＡＲ３１の第２クラス・アドレスはディレクトリ２０
のアドレスに使用される。ヒツト第１クラスおよびヒツ
ト第２クラスラインは除かれる。
のアドレスに使用される。ヒツト第１クラスおよびヒツ
ト第２クラスラインは除かれる。
クロック５において、ディレクトリからの実アドレス（
Ｒ，Ａ）ビット（１８〜３５）がメモリ・アドレス・レ
ジスタ（ＭＡＲ）７１に置かれる。ビット（３６〜４３
）はＣＡＲ３３からＭＡＲ７１にロードされる。最初の
データ組がＬ２キャッシュ１２のアレイ１２ａに到着す
ると、第１ページ・アドレスを含むＣＡＲは６３回イン
クリメントされる。これはデータのＩＫバイト・ライン
がＬ２キャッシュ・アレイ１２ａ中に読み取られること
を意味する。
Ｒ，Ａ）ビット（１８〜３５）がメモリ・アドレス・レ
ジスタ（ＭＡＲ）７１に置かれる。ビット（３６〜４３
）はＣＡＲ３３からＭＡＲ７１にロードされる。最初の
データ組がＬ２キャッシュ１２のアレイ１２ａに到着す
ると、第１ページ・アドレスを含むＣＡＲは６３回イン
クリメントされる。これはデータのＩＫバイト・ライン
がＬ２キャッシュ・アレイ１２ａ中に読み取られること
を意味する。
本発明は他のキャッシュ構成（任意のライン・サイズ、
仮想アドレス）においても適用できる。
仮想アドレス）においても適用できる。
また、主記憶装置のページ・サイズにも制限されるもの
ではない。第１および第２ラインの検索は同時でなく連
続的でもよいが同時実行のほうがキャッシュ・パフォー
マンスの向上に役立つ。
ではない。第１および第２ラインの検索は同時でなく連
続的でもよいが同時実行のほうがキャッシュ・パフォー
マンスの向上に役立つ。
Ｅ０発明の効果
以上のように本発明によればＴＬＢｅ使用せずにキャッ
シュ効率を向上させることが可能となる。
シュ効率を向上させることが可能となる。
第１図は第２レベル（Ｌ２）キャッシュを持つ一般的な
コンピュータのブロック図、第２図は第１図のシステム
において第２レベル（Ｌ２）キャッシュ・ディレクトリ
を採用した本発明の構成を示すブロック図、第３図はＬ
２キャッシュのアドレスとして使用される仮想アドレス
・ビットをＬ２キヤツシユ・ディレクトリに配置する方
法を示す図、第４図は同一の４にバイト・ページからの
ＩＫバイト・ラインのキャッシュ・ディレクトリでの処
理態様を示す図、第５図はフェッチ処理における第１／
第２検索実行のタイミングを示す図、第６図は第２図の
ヒツト／ミス・ロジックの論理図、第７図は第６図の第
２アドレス部の論理図である。 １１・・・・主記憶装置、１２・・・・Ｌ２キャッシュ
、１３・・・・Ｌ１キャッシュ、１４・・・・ＣＰＵ、
２０・・・・Ｌ２キャッシュ・ディレクトリ、３１・・
・・ディレクトリ・アドレス・レジスタ（ＤＡＲ）、３
３・・・・キャッシュ・アドレス・レジスタ（ＣＡＲ）
、６６・・・・ヒツト／ミス・ロジック、７１・・・・
メモリ・アドレスメレジスタ。
コンピュータのブロック図、第２図は第１図のシステム
において第２レベル（Ｌ２）キャッシュ・ディレクトリ
を採用した本発明の構成を示すブロック図、第３図はＬ
２キャッシュのアドレスとして使用される仮想アドレス
・ビットをＬ２キヤツシユ・ディレクトリに配置する方
法を示す図、第４図は同一の４にバイト・ページからの
ＩＫバイト・ラインのキャッシュ・ディレクトリでの処
理態様を示す図、第５図はフェッチ処理における第１／
第２検索実行のタイミングを示す図、第６図は第２図の
ヒツト／ミス・ロジックの論理図、第７図は第６図の第
２アドレス部の論理図である。 １１・・・・主記憶装置、１２・・・・Ｌ２キャッシュ
、１３・・・・Ｌ１キャッシュ、１４・・・・ＣＰＵ、
２０・・・・Ｌ２キャッシュ・ディレクトリ、３１・・
・・ディレクトリ・アドレス・レジスタ（ＤＡＲ）、３
３・・・・キャッシュ・アドレス・レジスタ（ＣＡＲ）
、６６・・・・ヒツト／ミス・ロジック、７１・・・・
メモリ・アドレスメレジスタ。
Claims (8)
- （１）キャッシュ・ディレクトリ中の各エントリがデー
タを取り出す主記憶装置中のページの実アドレスおよび
仮想アドレス最上位ビットを含む仮想アドレス・キャッ
シュを使用するコンピュータ装置におけるキャッシュ・
アクセス方法であり、 （イ）ページごとのライン検索を可能とする所定順序に
従つてキャッシュのディレクトリ中に主記憶装置の同一
ページからライン・エントリを配置し、 （ロ）同一ページからの所望ラインおよび第２ライン両
者のディレクトリ検索を行ない、所望ラインがキャッシ
ュ中に存在せず、同一ページからのラインに一致がある
場合、主記憶装置から直接データをフエツチするに際し
てアドレス変換をすることなく第２ラインの実アドレス
を使用することを特徴とするキャッシュ検索方法。 - （２）同一ページの上記ラインはディレクトリの連続的
配列に従つて配置されていることを特徴とする請求項１
のキャッシュ検索方法。 - （３）キャッシュ・ディレクトリ中の各エントリがデー
タを取り出す主記憶装置中のページの実アドレスおよび
仮想アドレス最上位ビットを含む仮想アドレス・キャッ
シュを使用するコンピュータ装置におけるキャッシュ検
索方法であり、 （イ）同時に検索されるキャッシュのディレクトリ中に
連続的に主記憶装置の同一ページからのライン・エント
リを配置し、 （ロ）同一ページからの所望ラインおよび第２ライン両
者のディレクトリ検索を行ない、所望ラインがキャッシ
ュ中に存在せず、同一ページからのラインに一致がある
場合、主記憶装置から直接データをフエツチするに際し
てアドレス変換をすることなく第２ラインの実アドレス
を使用することを特徴とするキャッシュ検索方法。 - （４）プロセッサ、 主記憶装置、 仮想アドレスの最上位ビット、実記憶装置中からのデー
タ読み取り用の実ページ・アドレスを持つディレクトリ
を有する仮想アドレス・キャッシュ、 および仮想アドレスを実アドレスに変換する手段とを有
し、 （イ）上記キャッシュ・ディレクトリは記憶装置の同一
ページからのライン・エントリをページごとのライン検
索可能な順序に有し、さらに、 （ロ）同一ページからの所望ラインと第２ライン両者の
キャッシュ・ディレクトリ検索を実行する手段と、 （ハ）キャッシュ・ディレクトリ・データを使用して所
望ラインにおける一致の識別を実行する手段と、 （ニ）アドレス変換を行うことなく第２ラインの実アド
レスを使用して主記憶装置から直接所望データをフエツ
チする第２ラインの一致を識別する手段と、 を有することを特徴とするキャッシュ検索装置。 - （５）プロセッサ、 主記憶装置、 仮想アドレスの最上位ビット、実記憶装置中からのデー
タ読み取り用の実ページ・アドレスを持つディレクトリ
を有する仮想アドレス・キャッシュ、 および仮想アドレスを実アドレスに変換する手段とを有
し、 （イ）上記キャッシュ・ディレクトリは記憶装置の同一
ページからのライン・エントリを同時にライン検索可能
な順序に有し、さらに、 （ロ）同一ページからの所望ラインと第２ライン両者の
キャッシュ・ディレクトリ検索を実行する手段と、 （ハ）キャッシュ・ディレクトリ・データを使用して所
望ラインにおける一致の識別を実行する手段と、 （ニ）アドレス変換を行うことなく第２ラインの実アド
レスを使用して主記憶装置から直接所望データをフエツ
チする第２ラインの一致を識別する手段と、 を有することを特徴とするキャッシュ検索装置。 - （６）同一ページからのラインは連続的配列に従つて配
置されていることを特徴とする請求項５のキャッシュ検
索装置。 - （７）上記キャッシュは受領アドレス・ビットをディレ
クトリ中の仮想アドレス・ビットと比較する比較手段を
有し、第２ラインとの一致があるときに主記憶装置のア
ドレスとして記憶装置の同一ページからの実アドレスを
第２ラインからの仮想アドレス・ビットともに使用する
ように構成されていることを特徴とする請求項６のキャ
ッシュ検索装置。 - （８）上記キャッシュはディレクトリ・アドレス・レジ
スタ（ＤＡＲ）、キャッシュ・アドレス・レジスタ（Ｃ
ＡＲ）、メモリ・アドレス・レジスタ（ＭＡＲ）および
ロジック手段とを含み、上記受領ビットは上記ＤＡＲに
保持され、上記比較手段によつてディレクトリ内の比較
が実行され、ＤＡＲ中の第２ラインに関して一致があつ
た場合に、ＣＡＲおよびＭＡＲビットが該第２ライン・
アドレスに置き換えられるように構成されていることを
特徴とする請求項７のキャッシュ検索装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US391763 | 1989-08-09 | ||
| US07/391,763 US5077826A (en) | 1989-08-09 | 1989-08-09 | Cache performance in an information handling system employing page searching |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0371355A true JPH0371355A (ja) | 1991-03-27 |
| JPH0529942B2 JPH0529942B2 (ja) | 1993-05-06 |
Family
ID=23547835
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2205332A Granted JPH0371355A (ja) | 1989-08-09 | 1990-08-03 | キヤツシユ検索装置および検索方法 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5077826A (ja) |
| EP (1) | EP0412949A3 (ja) |
| JP (1) | JPH0371355A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008268386A (ja) * | 2007-04-18 | 2008-11-06 | Tokyo Electric Power Co Inc:The | 立体模型 |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02205953A (ja) * | 1989-02-03 | 1990-08-15 | Nec Corp | アドレス変換装置 |
| US5249282A (en) * | 1990-11-21 | 1993-09-28 | Benchmarq Microelectronics, Inc. | Integrated cache memory system with primary and secondary cache memories |
| US5479630A (en) * | 1991-04-03 | 1995-12-26 | Silicon Graphics Inc. | Hybrid cache having physical-cache and virtual-cache characteristics and method for accessing same |
| GB9205551D0 (en) * | 1992-03-13 | 1992-04-29 | Inmos Ltd | Cache memory |
| US5446854A (en) * | 1993-10-20 | 1995-08-29 | Sun Microsystems, Inc. | Virtual memory computer apparatus and address translation mechanism employing hashing scheme and page frame descriptor that support multiple page sizes |
| US5721863A (en) * | 1996-01-29 | 1998-02-24 | International Business Machines Corporation | Method and structure for accessing semi-associative cache memory using multiple memories to store different components of the address |
| US5781922A (en) * | 1996-11-19 | 1998-07-14 | International Business Machines Corporation | Page boundary caches |
| US6279082B1 (en) * | 1998-10-14 | 2001-08-21 | Telefonaktiebolaget Lm Ericsson (Publ) | System and method for efficient use of cache to improve access to memory of page type |
| US7257279B2 (en) * | 2004-09-20 | 2007-08-14 | 3M Innovative Properties Company | Systems and methods for biosensing and microresonator sensors for same |
| US11561906B2 (en) * | 2017-12-12 | 2023-01-24 | Advanced Micro Devices, Inc. | Rinsing cache lines from a common memory page to memory |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4441155A (en) * | 1981-11-23 | 1984-04-03 | International Business Machines Corporation | Page controlled cache directory addressing |
| JPS5898893A (ja) * | 1981-12-09 | 1983-06-11 | Toshiba Corp | 情報処理装置 |
| US4612612A (en) * | 1983-08-30 | 1986-09-16 | Amdahl Corporation | Virtually addressed cache |
| US4577293A (en) * | 1984-06-01 | 1986-03-18 | International Business Machines Corporation | Distributed, on-chip cache |
| US4985829A (en) * | 1984-07-31 | 1991-01-15 | Texas Instruments Incorporated | Cache hierarchy design for use in a memory management unit |
| US4991081A (en) * | 1984-10-31 | 1991-02-05 | Texas Instruments Incorporated | Cache memory addressable by both physical and virtual addresses |
| US4737909A (en) * | 1985-04-01 | 1988-04-12 | National Semiconductor Corp. | Cache memory address apparatus |
| US4785398A (en) * | 1985-12-19 | 1988-11-15 | Honeywell Bull Inc. | Virtual cache system using page level number generating CAM to access other memories for processing requests relating to a page |
| US4953073A (en) * | 1986-02-06 | 1990-08-28 | Mips Computer Systems, Inc. | Cup chip having tag comparator and address translation unit on chip and connected to off-chip cache and main memories |
| US4797814A (en) * | 1986-05-01 | 1989-01-10 | International Business Machines Corporation | Variable address mode cache |
| JPH07120312B2 (ja) * | 1987-10-07 | 1995-12-20 | 株式会社日立製作所 | バッファメモリ制御装置 |
-
1989
- 1989-08-09 US US07/391,763 patent/US5077826A/en not_active Expired - Fee Related
-
1990
- 1990-07-04 EP EP19900850262 patent/EP0412949A3/en not_active Withdrawn
- 1990-08-03 JP JP2205332A patent/JPH0371355A/ja active Granted
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008268386A (ja) * | 2007-04-18 | 2008-11-06 | Tokyo Electric Power Co Inc:The | 立体模型 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5077826A (en) | 1991-12-31 |
| EP0412949A2 (en) | 1991-02-13 |
| JPH0529942B2 (ja) | 1993-05-06 |
| EP0412949A3 (en) | 1992-02-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4785398A (en) | Virtual cache system using page level number generating CAM to access other memories for processing requests relating to a page | |
| EP0036110B1 (en) | Cache addressing mechanism | |
| US5956756A (en) | Virtual address to physical address translation of pages with unknown and variable sizes | |
| JP2618175B2 (ja) | キャッシュ・アクセスのための仮想アドレス変換予測の履歴テーブル | |
| US5426750A (en) | Translation lookaside buffer apparatus and method with input/output entries, page table entries and page table pointers | |
| US5475827A (en) | Dynamic look-aside table for multiple size pages | |
| JP3666689B2 (ja) | 仮想アドレス変換方法 | |
| JP2014078248A (ja) | キャッシュされたメモリデータを伴うキャッシュメモリ属性インジケータ | |
| JPH02189659A (ja) | 仮想記憶動的アドレス変換システム | |
| JP7062695B2 (ja) | 論理ディレクトリを使用したキャッシュ構造 | |
| US6901540B1 (en) | TLB parity error recovery | |
| US5539892A (en) | Address translation lookaside buffer replacement apparatus and method with user override | |
| JPH0371355A (ja) | キヤツシユ検索装置および検索方法 | |
| US8015361B2 (en) | Memory-centric page table walker | |
| US5479629A (en) | Method and apparatus for translation request buffer and requestor table for minimizing the number of accesses to the same address | |
| JPH0695972A (ja) | ディジタルコンピュータシステム | |
| CN101326499A (zh) | 更新多级翻译旁视缓冲器（tlb）字段 | |
| US7171540B1 (en) | Object-addressed memory hierarchy that facilitates accessing objects stored outside of main memory | |
| JPH03211643A (ja) | 並行例外検査及び更新バイパスを有する変換索引バッファ | |
| US20030149858A1 (en) | Object addressed memory hierarchy | |
| JPH035851A (ja) | バッファ記憶装置 | |
| JPS623354A (ja) | キヤツシユメモリ・アクセス方式 | |
| JP2507785B2 (ja) | ペ―ジテ―ブルエントリ無効化装置 | |
| JPS6324337A (ja) | キャッシュ・メモリ管理方式 | |
| JPH02113355A (ja) | キャッシュメモリ |