JPH0683711A

JPH0683711A - データ処理システムおよびデータ処理方法

Info

Publication number: JPH0683711A
Application number: JP5004313A
Authority: JP
Inventors: Ii U Ching-Fang; イー．ウチン−ファーン
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1992-03-02
Filing date: 1993-01-13
Publication date: 1994-03-25
Anticipated expiration: 2013-12-16
Also published as: US5668968A; JP2839060B2

Abstract

(57)【要約】【目的】２レベル仮想／実セット・アソシアティブ・
キャッシュを提供すること。【構成】本データ処理システムは第１メモリ１０４お
よび第２メモリ１０６を備え、第２メモリは第１メモリ
が第２メモリにストアされたデータのコピーを保持して
いるかどうかを示した同義語情報を含む。プロセッサ１
０２のオペランド・アドレスに対応するアドレスをもつ
データ・ブロックが第１メモリにあれば「ヒット」の出
力が生成されなければ「ミス」の出力が生成される。
「ヒット」ならば、データが第１メモリのロケーション
に入／出力される。一方、オペランド・アドレスは第２
メモリのアドレスとなる変換アドレスに変換され、比較
手段の出力が「ミス」ならば、第２メモリは同義語情報
を出力する。第１メモリがデータ・ブロックのコピーを
保持していることを同義語情報が示していれば、同義語
アドレスが第２メモリから第１メモリに出力される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般的には、データ・
プロセッサの分野に関し、具体的には、２レベル仮想／
実セット・アソシアティブ・キャッシュ・システム（ｔ
ｗｏ−ｌｅｖｅｌｖｉｒｔｕａｌ／ｒｅａｌｓｅｔ
−ａｓｓｏｃｉａｔｅｃａｃｈｅｓｙｓｔｅｍ）およ
び方法に関する。

【０００２】

【従来の技術】本明細書で論じている基本的概念のいく
つかは、いくつかの参考文献で詳しく説明されている。
その１つのとして、Ｈｅｎｎｅｓｓｙ，ＪｏｈｎＬ外
著の「コンピュータ・アーキテクチャ−量的解決手法
（ＣｏｍｐｕｔｅｒＡｒｃｈｉｔｅｃｔｕｒｅ−Ａ
ＱｕａｎｔｉｔａｔｉｖｅＡｐｐｒｏａｃｈ）」（Ｍ
ｏｒｇａｎＫａｕｆｍａｎｎＰｕｂｌｉｓｈｅｒ
ｓ，Ｉｎｃ．，ＳａｎＭａｔｅｏ，Ｃａｌｉｆｏｒｎ
ｉａ，１９９０）がある。同書は、特にその第８章は、
本発明が課題としているキャッシュ・メモリの問題を論
じたすぐれた文献である。

【０００３】キャッシュとは、比較的小型の高速メモリ
であり、主記憶域の中で最も最近に使用されたブロック
の内容を保持するために使用されるものである。キャッ
シュは、高速のプロセッサ・サイクル・タイムと低速の
メモリ・アクセス・タイムとの間のギャップを埋めるた
めに使用される。キャッシュは、主メモリと物理的に区
別され、プログラムがアドレス指定できないのが通常で
ある。キャッシュ・メモリ・システムをもつ従来のデー
タ処理システムは、中央処理装置（ＣＰＵまたはプロセ
ッサ）、キャッシュ・メモリ、および二次的メモリ（例
えば、上位レベル・キャッシュ・メモリまたは主メモ
リ）を備えている。プロセッサはオペランド・アドレス
を生成し、このアドレスは、変換される場合も、変換さ
れない場合も、キャッシュ・メモリのアドレスと比較さ
れる。キャッシュが「ヒット」すれば、キャッシュ・メ
モリ内のアドレス指定されたロケーションがアクセスさ
れる。キャッシュが「ミス」したときは、そのアドレス
は変換され、そのあとで二次的メモリに渡される。デー
タは二次的メモリから取り出され、キャッシュに置かれ
る。これが行われると、ＣＰＵはそのデータが使用可能
になるまで休止させられるのが普通である。

【０００４】キャッシュ・メモリは、「局所性の特性」
として知られる経験的観察から生まれたものである（Ｄ
ｅｎｎｉｎｇ，Ｐ．Ｊ．，「プログラム挙動のモデル化
について（Ｏｎｍｏｄｅｌｉｎｇｐｒｏｇｒａｍ
ｂｅｈａｖｉｏｒ）」、Ｐｒｏｃ．ＳｐｒｉｎｇＪｏ
ｉｎｔＣｏｍｐｕｔｅｒＣｏｎｆｅｒｅｎｃｅ，Ａ
ＦＩＰＳＰｒｅｓｓ，ｐｐ．９３７−９４４，１９７
２）。この「局所性の特性」は、近い将来に使用される
情報は現在使用中のその情報となる可能性があり（時間
による局所性）、その情報は現在使用中の情報と論理的
に隣接している（空間による局所性）と表現することが
できる。

【０００５】プログラムによって参照されるオブジェク
トのすべてを主メモリに置いておく必要はない。「仮想
メモリ」をもつコンピュータならば、一部のオブジェク
トをディスクなどに置いておくことが可能である。アド
レス空間は、通常、「ページ」と呼ばれる固定サイズの
ブロックに分割されている。どの時点でも、各ページは
主メモリかディスクのどちらかに置かれている。ＣＰＵ
があるページ内のあるエントリを参照し、そのエントリ
がキャッシュまたは主メモリに存在しないと、「ページ
不在（ｐａｇｅｆａｕｌｔ）」が起こり、そのページ
全体がディスクから主メモリに移されることになる。キ
ャッシュと主メモリとの関係は、主メモリとディスクと
の関係と同じである。

【０００６】メモリ階層は多数のレベルから構成されて
いるのが通常であるが、その管理は一度に２つの隣接す
るレベル間で行われる。「上位」レベル、つまり、ＣＰ
Ｕに近いレベルは、「下位」レベルよりも小さく、高速
である。２レベル階層に存在する場合も、存在しない場
合も、情報の最小単位は「ブロック」と呼ばれる。ブロ
ックのサイズには、固定長と可変長の２種類がある。あ
るブロックが固定長である場合は、メモリ・サイズはそ
のブロック・サイズの倍数になっている。上位レベルへ
のアクセスが成功したことをヒットといい、失敗したこ
とをミスという。

【０００７】メモリのアドレスはいくつかの部分に分割
され、それぞれが階層の各部分にアクセスする。「ブロ
ック・フレーム・アドレス」はアドレスの上位桁部分で
あり、階層のそのレベルに置かれているブロックを指定
している。「ブロック・オフセット・アドレス」はアド
レスの下位桁部分であり、ブロック内のエントリを指定
している。ブロック・オフセット・アドレスのサイズはｌｏｇ₂ （ブロックのサイズ）であるので、ブロック・フレーム・アドレスのサイズは
そのレベルにおけるアドレス全体のサイズからブロック
・オフセット・アドレスのサイズを差し引いたサイズと
なる。

【０００８】ＣＰＵは、情報が階層の最上位レベルにあ
るかどうかを、なんらかの方法で判断しなければならな
い。この検査はメモリをアクセスするたびに行われるの
で、ヒット・タイムに影響を与えることになる。パフォ
ーマンスを望ましいレベルに保つためには、通常、この
検査をハードウェアで実現する必要がある。メモリ階層
の決定的な制約は、ブロックを上位レベルのメモリと下
位レベルのメモリ間で転送するためのメカニズムをコン
ピュータに実装させる必要があることである。ブロック
転送が数１０クロック・サイクルで行われる場合は、ハ
ードウェアで制御される。ブロック転送が数千クロック
・サイクルで行われる場合は、ソフトウェアで制御する
ことが可能である。キャッシュの場合は、ブロックでは
なく、「ライン」（ｌｉｎｅ）の用語が用いられてい
る。

【０００９】ブロックを置く場所に制約があるために、
キャッシュ編成には３種類のものがある。各ブロックを
キャッシュに置いておくことができる場所が１つしかな
いときは、キャッシュは「直接マップ」される（ｄｉｒ
ｅｃｔｍａｐｐｅｄ）と言われる。このマッピング
は、通常、キャッシュ内のブロック数を法（モジュロ）
とするブロック・フレーム・アドレス（（ｂｌｏｃｋ−
ｆｒａｍｅａｄｄｒｅｓｓ）ｍｏｄｕｌｏ（ｎｕｍｂ
ｅｒｏｆｂｌｏｃｋｓｉｎｃａｃｈｅ））であ
る。ブロックをキャッシュ内の限れられたブロック・セ
ットに置くことができる場合は、キャッシュは「セット
・アソシアティブ」（ｓｅｔａｓｓｏｃｉａｔｉｖ
ｅ）であると言われる。「セット」とは、キャッシュ内
の２またはそれ以上のブロックの集まりである。ブロッ
クは最初にセット上にマップされ、そのあと、セット内
のどこにでもブロックを置くことができる。セットは、
通常、ビット選択によって選択される。つまり、キャッ
シュ内のセット数を法とするブロック・フレーム・アド
レス（（ｂｌｏｃｋ−ｆｒａｍｅａｄｄｒｅｓｓ）ｍ
ｏｄｕｌｏ（ｎｕｍｂｅｒｏｆｓｅｔｓｉｎｃ
ａｃｈｅ））である。セット内にｎ個のブロックがある
とき、キャッシュ配置は「ｎウェイ・セット・アソシア
ティブ」と呼ばれる。

【００１０】直接マップから完全アソシアティブまでの
キャッシュの範囲は、実際には、セット・アソシアティ
ブのレベルの連続体である。直接マップは単純に１ウェ
イ・セット・アソシアティブであるが、「ｍ」個のブロ
ックをもつ完全アソシアティブ・キャッシュは「ｍウェ
イ」セット・アソシアティブと呼ぶことができる。

【００１１】キャッシュでは、ブロック・フレーム・ア
ドレスを示したアドレス・タグが各ブロックに付いてい
る。必要とする情報を収めている可能性のあるすべての
キャッシュ・ブロックはそのタグが検査されて、それが
ＣＰＵからのブロック・フレーム・アドレスと一致して
いるかどうかが確かめられる。スピードは非常に重要で
あるので、可能な限りのタグは並列にサーチ（探索）さ
れる。サーチを順次に行うと、セット・アソシアティブ
が非生産的になるためである。

【００１２】キャッシュ・ブロックに有効な情報が入っ
ているかどうかを、なんらかの方法で確かめる必要があ
る。最もよく行われている方法は、そのエントリに有効
なアドレスが入っているかどうかを示した「有効ビッ
ト」をタグに付加することである。このビットがセット
されていなければ、このアドレスに一致する情報がない
ことを示す。このタグは、各ブロックごとに１つ必要で
ある。ブロック・サイズを大きくすると、キャッシュ・
エントリ当たりのタグ・オーバヘッド費用は、キャッシ
ュの総費用に占める割合が小さくなるという利点が得ら
れる。

【００１３】ＣＰＵアドレスは３つのフィールドに分割
されている。これらのフィールドはセット・アソシアテ
ィブ・キャッシュからデータを探すために使用される。
必要とするデータをブロックから選択するために使用さ
れる「ブロック・オフセット」フィールド、セットを選
択するために使用される「インデックス」フィールド、
および比較のために使用される「タグ」フィールドであ
る。比較を行うアドレスをタグよりも多くすることが可
能であるが、その必要はない。総サイズが同じに保たれ
ていれば、アソシアティブを大きくすると、セット当た
りのブロック数が増加するので、「インデックス」のサ
イズが減少し、「タグ」のサイズが増加する。

【００１４】直接マップによる配置の利点は、ハードウ
ェアによる判断が単純化されることである。実際に、非
常に程単純化されているので、選択が行われない。つま
り、１つのブロックだけがヒットしたかどうか検査さ
れ、そのブロックだけが置き換わることができる。完全
アソシアティブまたはセット・アソシアティブによる配
置では、ミスが起こったとき、いくつかのブロックから
選択する必要がある。どのブロックを置き換えるかを選
択する際に２つの基本的方式が採用されている。

【００１５】１つは、候補となるブロックをランダムに
選択する方式である。いくつかのシステムでは、データ
を擬似ランダム方式でブロック群間に分散させて、再現
性を可能にする方式を採用している。

【００１６】もう１つは、ＬＲＵ（ｌｅａｓｔ−ｒｅｃ
ｅｎｔｌｙｕｓｅｄ）法と呼ばれる方式である。すぐ
に必要になる情報が破棄される可能性を少なくするため
に、ブロックへのアクセスが記録される。置き換えられ
るブロックは、最も長時間使用されなかったブロックで
ある。当然の結果として、時間による局所性が利用され
る。つまり、最近に使用されたブロックが再び使用され
る可能性があれば、破棄される最有力の候補は、最近に
使用されなかったブロックとなる。

【００１７】どの時点でも、コンピュータでは複数のプ
ロセスが実行されているので、物理メモリの一部を多数
プロセス間で共用させる方法が必要になる。その１つの
方法が「仮想メモリ」である。この仮想メモリ方式で
は、物理メモリをいくつかのブロックに分割し、それら
のブロックをいくつかの異なるプロセスに割り振ってい
る。仮想メモリ方式によるときは、ＣＰＵは「仮想」ア
ドレスを生成し、これらはハードウェアとソフトウェア
の組み合わせにより「物理アドレス」に変換される。物
理アドレスは主メモリをアクセスするために使用され
る。このプロセスのことを、「メモリ・マッピング」ま
たは「アドレス変換」と呼んでいる。現在、仮想メモリ
によって制御されるメモリ階層レベルとしては、ＤＲＡ
Ｍと磁気ディスクの２つがある。

【００１８】キャッシュと仮想メモリとの間には、他に
も違いがある。キャッシュがミスしたときの置換は主に
ハードウェアによって制御されるのに対し、仮想メモリ
の置換は主にオペレーティング・システムによって制御
される。ミス時間が長くなると、そのペナルティとし
て、オペレーティング・システムが介入する機会が多く
なり、どれを置換すべきかを判断するために消費する時
間が多くなる。仮想メモリのサイズはＣＰＵアドレスの
サイズによって決まるが、キャッシュのサイズは通常Ｃ
ＰＵアドレスから独立している。二次的記憶装置は、階
層における主メモリの下位レベル・メモリとして働くほ
かに、通常では、アドレス空間に含まれないファイル・
システムのためにも使用される。二次的記憶装置の大部
分は、実際には、ファイル・システムが占有している。

【００１９】仮想メモリには、関連する手法がいくつか
ある。仮想メモリ・システムは次の２種類に分類するこ
とができる。１つは、「ページ」とよばれる固定サイズ
・ブロックからなるものであり、もう１つは、「セグメ
ント」と呼ばれる可変サイズ・ブロックからなるもので
ある。ページは５１２バイト〜８１９２バイトの範囲内
で固定しているのが代表的であるのに対し、セグメント
・サイズは可変になっている。どの計算機でもサポート
される最大セグメントは２¹⁶バイト〜２⁵²バイトまでの
範囲であり、最小セグメントは１バイトである。

【００２０】ページ化仮想メモリを使用するか、セグメ
ント化仮想メモリを使用するかによって、ＣＰＵは影響
される。ページ化アドレス指定では、単一の固定サイズ
・アドレスがページ番号とページ内のオフセットに分割
されている。セグメント化アドレスでは、アドレスが単
一になっていない。可変サイズのセグメントでは、セグ
メント番号用に１ワード、セグメント内のオフセット用
に１ワード、合計２ワードが必要である。アドレス空間
をセグメント化しない方がコンパイラが扱いやすくな
る。ページ化とセグメント化のどちらも、ページ番号ま
たはセグメント番号によってインデックス付けされるデ
ータ構造に依存する。このデータ構造にはブロックのア
ドレスが入っている。ページ化の場合は、オフセットは
この物理ページ・アドレスに連結されるだけである。セ
グメント化の場合は、オフセットがセグメントの物理ア
ドレスに加えられて、最終的な仮想アドレスが得られ
る。物理ページ・アドレスを収めているこのデータ構造
は、「ページ・テーブル」の形体になっているのが普通
である。仮想ページ番号によってインデックス付けされ
ると、テーブルのサイズは仮想アドレス空間内のページ
の数となる。アドレス変換時間を短縮するために、コン
ピュータは、アドレス変換専用のキャッシュを使用して
いる。このキャッシュは変換索引バッファ（ＴＬＢ）
（Ｔｒａｎｓｌａｔｉｏｎｌｏｏｋａｓｉｄｅｂｏ
ｆｆｅｒ）、簡略化して変換バッファと呼ばれている。

【００２１】ほとんどのオペレーティング・システムで
は、いずれも、ＬＲＵブロックを置き換えることを試み
ているが、このブロックは最も必要とされない可能性が
あるためである。オペレーティング・システムがＬＲＵ
を予測するのを容易にするために、多くの計算機では、
「使用ビット」または「参照ビット」が用意されてい
る。このビットは、あるページがアクセスされると、セ
ットされるようになっている。オペレーティング・シス
テムは使用ビットを定期的にクリアし、そのあと使用ビ
ットを記録しておき、ある特定の時間期間にどのページ
がタッチされたかの判断を行いやすくしている。このよ
うに記録にとっておくと、オペレーティング・システム
は最も長期間参照されなかったページを選択することが
できる。

【００２２】ＴＬＢエントリは、タグが仮想アドレスの
部分を保持し、データ部分が物理ページ・フレーム番
号、保護フィールド、使用ビット、およびダーティ（ｄ
ｉｒｔｙ）ビットを保持している点で、キャッシュ・エ
ントリと似ている。置換時にブロックを書き戻す回数を
減らすために、「ダーティ・ビット」と呼ばれる機能が
よく使用されている。このステータス（状況）ビット
は、ブロックがキャッシュに置かれているとき変更され
たか否かを示す。変更されていなければ、下位レベルに
キャッシュと同じ情報があるので、そのブロックを書か
ない。ページ・テーブル・エントリの物理ページ・フレ
ーム番号や保護を変更するときは、オペレーティング・
システムは旧エントリがＴＬＢにないことを確かめる必
要がある。これを怠ると、システムは正しく動作しない
ことになる。なお、このダーティ・ビットは、対応する
ページがダーティであることを意味し、ＴＬＢでのアド
レス変換がダーティであること、あるいはデータ・キャ
ッシュ内の特定のブロックがダーティであることを意味
するものではない。１つの例として、あるページがダー
ティでなければ、破棄されて、ＣＰＵが要求する新しい
ラインで置換されるだけである。

【００２３】アクセス時間を短縮するために、従来の解
決手法によれば、仮想アドレスをＴＬＢ経由で送ると
き、アドレスの物理部分を使用してキャッシュのインデ
ックス付け（インデクシング）を行っている。これに
は、直接マップ方式のキャッシュをページ・サイズより
大きくできないという制約がある。ＩＢＭシステム／３
７０では、キャッシュ・サイズを大きくして、４ＫＢペ
ージが収容できるようにするために、高度のアソシアテ
ィビィティを使用して、物理インデックスを付けてもキ
ャッシュがアクセスできるようにしている。例えば、Ｉ
ＢＭ３０３３では、１６ウェイ・セット・アソシアテ
ィブを使用し、ライン・サイズは６４バイトになってい
る。もっとも研究結果（Ｓｍｉｔｈ，Ａ．Ｊ．，「キャ
ッシュ・メモリ（ｃａｃｈｅｍｅｍｏｒｉｅｓ）」、
ＣｏｍｐｕｔｉｎｇＳｕｒｖｅｙ，Ｖｏｌ．１４，Ｎ
ｏ．３）によれば、セット・アソシアティブが８ウェイ
を越えると、ミス率にとって殆ど利点がないことを示し
ているが。（ＩＢＭ「ＩＢＭ３０３３プロセッサ：動作
の理論／ダイヤグラム・マニュアル（ＩＢＭ３０３３
ｐｒｏｃｅｓｓｏｒｃｏｍｐｌｅｘ：ｔｈｅｏｒｙ
ｏｆｏｐｅｒａｔｉｏｎ／ｄｉａｇｒａｍｓｍａ
ｍｖａｌ）Ｖｏｌ．４，ＩＢＭＰｏｕｇｈｋｅｅｐ
ｓｉｅ，ＮｅｗＹｏｒｋ，１９７８。）サイズの制約
を受けないでキャッシュ・ヒットを高速化する１つの方
法は、メモリ・アクセスをより多重度にパイプライン化
することであり、この場合、ＴＬＢはパイプラインの１
つのステップにすぎない。ＴＬＢはキャッシュよりも小
型の独立の機構であり、より短いアクセス時間を可能に
する。この方式はメモリ待ち時間を変化させないが、Ｃ
ＰＵパイプラインの効率性を利用して、メモリのバンド
幅を広くする。

【００２４】もう１つの方法は、仮想アドレスとの突き
合わせを直接に行うことである。この種のキャッシュは
「仮想キャッシュ」と呼ばれる。この方法によると、キ
ャッシュ・ヒットからＴＬＢ変換時間が不要になる。し
かるに、仮想アドレス方式のキャッシュは余り作られて
いない。なぜなのか。その理由の１つは、プロセスが切
り替わるたびに、仮想アドレスは異なる物理アドレスを
指すために、キャッシュをフラッシュする必要があるこ
とである。この解決法の１つは、プロセスＩＤタグ（Ｐ
ＩＤ）を使用してキャッシュ・アドレス・タグの幅を大
きくすることである。オペレーティング・システムがこ
れらのタグをプロセスに割り当てれば、ＰＩＤがリサイ
クルするときだけキャッシュをフラッシュすればよい
（ＰＩＤを使用すると、保護が得られる）。

【００２５】仮想キャッシュの採用が普及化しないもう
１つの理由は、オペレーティング・システムとユーザ・
プログラムが同じ物理アドレスに異なる仮想アドレスを
使用していることに係わりがある。このように重複する
アドレスは「同義語」（シノニム）または「別名」（ａ
ｌｉａｓ−エリアス）と呼ばれ、結果として、同じデー
タのコピーが２つ仮想キャッシュに置かれることにな
る。従って、一方のコピーを変更すると、他方のコピー
は正しい値が反映されないことになる。物理キャッシュ
では、アクセスが最初に同一物理キャッシュ・ブロック
に変換されるので、このようなことは起こらない。アン
チ・エリアス（ａｎｔｉ−ａｌｉａｓｉｎｇ）と呼ばれ
るハードウェア方式によれば、すべてのキャッシュ・ブ
ロックに固有の物理アドレスを保証することができる
が、別名（エリアス）にあるアドレス・ビットを共用さ
せることによってソフトウェアはこのことをさらに容易
にすることができる。

【００２６】従来のキャッシュはページ・オフセットを
使用して、キャッシュ・ラインを選択するのと同時に、
ＴＬＢを使用して仮想アドレスから実アドレスへの変換
を行っている。固定ページ・サイズとライン・サイズが
一定のとき、キャッシュ・データ・アレイをアクセスす
るとき利用できるビットの数は一定しており、通常は少
数である。技術が向上すれば、利用できるキャッシュ・
アレイのサイズも向上する。従って、アドレス変換を並
行に行うためには、キャッシュ・セット・アソシアティ
ブが大きくなることも必然である。

【００２７】ＩＢＭＲＳ／６０００（Ｂａｋｏｇｌｕ
外著「ＩＢＭＲＩＳＣシステム／６０００プロセッ
サ：ハードウェアの概要（ｈａｒｄｗａｒｅｏｖｅｒ
ｖｉｅｗ）」、ＩＢＭＪ．Ｒｅｓｅａｒｃｈａｎｄ
ＤｅｖｅｌｏｐｍｅｎｔＶｏｌ．３４，Ｎｏ．１，
ｐｐ．１２−２２，１９９０）のような他のシステムで
は、仮想アドレスと実アドレスの一部をデータ・キャッ
シュ内で同一に保つことを、ソフトウェアで行ってい
る。しかし、キャッシュ・サイズが大きくなり、６４Ｋ
Ｂを越えると、アドレス・ビットを仮想アドレスと実ア
ドレスとで同一に保つことは、主メモリにおいてデータ
割振りが制限されることを意味する。これは、キャッシ
ュ内での可能なロケーションを減少させ、従って、セッ
ト・アソシアティブ・キャッシュ構造により得られるミ
ス率の利点が失われる。

【００２８】キャッシュ構造における仮想アドレス・タ
グも提案されている（Ｉｂｂｅｔｔ外著「ＴｈｅＭＵ
５ｎａｍｅｓｔｏｒｅ」，ＣｏｍｐｕｔｅｒＪｏ
ｕｒｎａｌＶｏｌ．２０，Ｎｏ．３，ｐｐ．２２７−
２３１，１９７７）。仮想アドレス・キャッシュ・ディ
レクトリの各アドレスには、そのプロセスＩＤのタグを
付ける必要がある。さもなければ、タスク切替えが行わ
れるたびにキャッシュをパージ（消去）する必要があ
る。その場合でも、仮想アドレス・キャッシュは、同義
語について重大な問題がある。Ｂｅｄｅｒｍａｎ（Ｂｅ
ｄｅｒｍａｎ，Ｓ著「キャッシュ・ディレクトリに仮想
タグと実タグを使用したキャッシュ管理システム（Ｃａ
ｃｈｅｍａｎａｇｅｍｅｎｔｓｙｓｔｅｍｕｓｉ
ｎｇｖｉｒｔｖａｌａｎｄｒｅａｌｔａｇｓ
ｉｎｔｈｅｃｈａｃｈｅｄｉｒｅｃｔｏｒ
ｙ）」、ＩＢＭＴｅｃｈｎｉｃａｌＤｉｓｃｌｏｓ
ｕｒｅＢｕｌｌｅｔｉｎ，Ｖｏｌ．２１，Ｎｏ．１
１，ｐｐ．４５，４１，１９７９）は同義語を避けるた
めに仮想アドレス・タグと実アドレス・タグの両方を使
用したキャッシュ構造を提案している。Ｂｅｄｅｒｍａ
ｎは、実キャッシュおよび仮想キャッシュのインデック
ス付けに同じビットを使用している。従って彼の方法
は、サイズに制約があり、ページ・サイズにアソシアテ
ィブを掛けたものよりも小さくならざるを得ない。

【００２９】Ｂｅｄｅｒｍａｎは仮想アドレスの比較を
最初に行っているが、同義語が見つかると、ラインはキ
ャッシュ内で検出不能である。しかし、次のサイクル時
に、ＴＬＢが仮想アドレスを実アドレス（つまり、オフ
セットは実アドレスも、仮想アドレスも同じであり、オ
フセットは合計１２ビットであり、オフセットのＬＳＢ
はライン内のバイト・アドレスを示すので、実ページ番
号）に変換すると、ＴＬＢによって生成される実ページ
番号をキャッシュ内の実アドレス・タグと比較すること
ができ、同義語がないことを確かめることができる。

【００３０】

【発明が解決しようとする課題】同義語を効率よく見つ
けて、必要とする情報を得るためには、キャッシュ構造
をもっと綿密に調べる必要がある。同種の２レベル方式
が提案されている（Ｗａｎｇ外著「２レベル仮想−実キ
ャッシュ階層の編成とパフォーマンス（Ｏｒｇａｎｉｚ
ａｔｉｏｎａｎｄｐｅｒｆｏｒｍａｎｃｅｏｆ
ａｔｗｏ−ｌｅｖｅｌｖｉｒｔｖａｌ−ｒｅａｌ
ｃｈａｃｈｅｈｉａｒａｒｃｈｙ）」、Ｐｒｏｃ．ｏ
ｆ１６ｔｈＩｎｔｌ．Ｓｙｍｐｏｓｉｕｍｏｎ
ＣｏｍｐｕｔｅｒＡｒｃｈｉｔｅｃｔｕｒｅ，１４０
−１４８，１９８９）。この方式は、複雑化されたＬ１
／Ｌ２インタフェースを使用し、複雑なＬ１がＬ１内で
キャッシュ・ラインを移動できることを前提とする。Ｗ
ａｎｇのキャッシュ・システムは、Ｌ１キャッシュがＬ
１内でラインをあるロケーションから別のロケーション
へ転送できる。そのために、Ｌ１キャッシュはかなり複
雑なハードウェアが必要である。

【００３１】そこで本発明の目的は、同義語アドレスそ
のものを使用して、Ｌ１を直接にアドレス指定してＬ１
からラインを得るデータ処理システムおよびデータ処理
方法を提供することにある。

【００３２】

【課題を解決するための手段】このような目的を達成す
るために、請求項１に記載のデータ処理システムは、命
令を受け取り、その命令からオペランド・アドレスを生
成するプロセッサと、アドレス入力、データ入力、デー
タ出力、およびデータをストアするための複数のアドレ
ス指定可能な第１ロケーションを有する第１メモリと、
アドレス入力、データ入力、データ出力、およびデータ
をストアするための複数のアドレス指定可能な第２ロケ
ーションを有する第２メモリであって、第２メモリ内の
複数のアドレス指定可能な第２ロケーションの１つまた
は複数の各々は、さらに、第１メモリが第２メモリにス
トアされたデータのコピーを保持しているかどうかを示
している同義語（シノニム）情報を含んでいる第２メモ
リと、プロセッサからオペランド・アドレスを受け取る
ためのアドレス入力を有し、オペランド・アドレスを第
１メモリのロケーション・アドレスと比較し、オペラン
ド・アドレスに対応するアドレスをもつデータ・ブロッ
クが第１メモリにあれば、「ヒット」の出力を生成し、
オペランド・アドレスに対応するアドレスをもつデータ
・ブロックが第１メモリになければ、「ミス」の出力を
生成するための比較手段と、比較手段の出力を受け取
り、比較手段の出力が「ヒット」ならば、オペランド・
アドレスに対応するアドレスをもつデータ・ブロックを
ストアしている第１メモリのロケーションにデータを入
力し、あるいはそのロケーションからデータを出力する
ための手段と、比較手段の出力を受け取り、オペランド
・アドレスを第２メモリのアドレスとなる変換アドレス
に変換し、比較手段の出力が「ミス」ならば、同義語情
報および、変換アドレスに対応する第１メモリのアドレ
スを構成する同義語アドレスを出力するための手段と、
同義語情報を受け取り、第１メモリがデータ・ブロック
のコピーを保持していることを同義語情報が示していれ
ば、第１メモリのアドレス入力に同義語アドレスを出力
するための手段とを具えたことを特徴とする。

【００３３】請求項２に記載のデータ処理システムは、
請求項１に記載のデータ処理システムにおいて、第１メ
モリの複数のアドレス指定可能な第１ロケーションの１
つまたは複数の各々はさらに、データ・ブロックを保持
している第２メモリのロケーションを指す第１ポインタ
を有することを特徴とする。

【００３４】請求項３に記載のデータ処理システムは、
請求項１に記載のデータ処理システムにおいて、前記第
１メモリは仮想アドレスをベースとしたキャッシュ・メ
モリを有することを特徴とする。

【００３５】請求項４に記載のデータ処理システムは、
請求項１に記載のデータ処理システムにおいて、前記第
２メモリは実アドレスをベースとしたキャッシュ・メモ
リを有することを特徴とする。

【００３６】請求項５に記載のデータ処理システムは、
請求項２に記載のデータ処理システムにおいて、前記第
１メモリは仮想アドレスをベースとしたキャッシュ・メ
モリを有し、前記第２メモリは実アドレスをベースとし
たキャッシュ・メモリを有することを特徴とする。

【００３７】請求項６に記載のデータ処理システムは、
請求項１に記載のデータ処理システムにおいて、前記同
義語情報は、第１メモリがデータ・ブロックのコピーを
保持しているかどうかを示す１ビット・フラグを有する
ことを特徴とする。

【００３８】請求項７に記載のデータ処理システムは、
請求項６に記載のデータ処理システムにおいて、前記同
義語情報はさらに、第１メモリがデータ・ブロックのコ
ピーを保持しているとき、第１メモリのロケーションを
指している第２ポインタを有することを特徴とする。

【００３９】請求項８に記載のデータ処理システムは、
請求項７に記載のデータ処理システムにおいて、前記第
２ポインタは仮想ポインタを有することを特徴とする。

【００４０】請求項９に記載のデータ処理システムは、
請求項５に記載のデータ処理システムにおいて、オペラ
ンド・アドレスを変換アドレスに変換するための前記手
段は変換索引バッファ（ＴＬＢ）を有することを特徴と
する。

【００４１】請求項１０に記載のデータ処理方法は、デ
ータ処理システム上で実行されるデータ処理方法におい
て、命令を受け取り、その命令からオペランド・アドレ
スを生成するステップと、アドレス入力、データ入力、
データ出力、およびデータをストアするための複数のア
ドレス指定可能な第１ロケーションもつ第１メモリを用
意し、アドレス入力、データ入力、データ出力、および
データをストアするための複数のアドレス指定可能な第
２ロケーションをもつ第２メモリであって、第２メモリ
の複数のアドレス指定可能な第２ロケーションの１つま
たは複数の各々はさらに、第１メモリが第１メモリにス
トアされたデータのコピーを保持しているかどうかを示
した同義語（シノニム）情報を含んでいる第２メモリを
用意し、プロセッサからオペランド・アドレスを受け取
るためのアドレス入力をもつ比較手段を使用して、オペ
ランド・アドレスを第１メモリのロケーション・アドレ
スと比較し、オペランド・アドレスに対応するアドレス
をもつデータ・ブロックが第１メモリにあれば、「ヒッ
ト」の出力を生成し、オペランド・アドレスに対応する
アドレスをもつデータ・ブロックが第１メモリになけれ
ば、「ミス」の出力を生成するステップと、比較手段の
出力を受け取り、比較手段の出力が「ヒット」ならば、
オペランド・アドレスに対応するアドレスをもつデータ
・ブロックをストアしている第１メモリのロケーション
にデータを入力し、あるいはそのロケーションからデー
タを出力するステップと、比較手段の出力を受け取っ
て、オペランド・アドレスを第２メモリのアドレスとな
る変換アドレスに変換し、比較手段の出力が「ミス」な
らば、同義語と、変換アドレスに対応する第１メモリの
アドレスを構成する同義語アドレスとを出力するステッ
プと、同義語情報を受け取り、第１メモリがデータ・ブ
ロックのコピーを保持していることを同義語情報が示し
ていれば、第１メモリのアドレス入力に同義語アドレス
を出力するステップと具えたことを特徴とする。

【００４２】ここで、さらに、第１メモリの複数のアド
レス指定可能な第１ロケーションの１つまたは複数の各
々に対して第１ポインタを用意するステップを含み、第
１ポインタはデータ・ブロックを保持している第２メモ
リのロケーションを指していることとしてもよい。

【００４３】請求項１０に記載のデータ処理方法におい
て、前記第１メモリは仮想アドレス指定方式を使用して
もよい。

【００４４】請求項１０に記載のデータ処理方法におい
て、前記第２メモリは実アドレス指定方式を使用しても
よい。

【００４５】請求項１０に記載のデータ処理方法におい
て、前記同義語情報は、第１メモリがデータ・ブロック
のコピーを保持しているかどうかを示す１ビット・フラ
グを使用してもよい。

【００４６】前記同義語情報は第２ポインタを使用し、
該第２ポインタは、第１メモリがデータ・ブロックのコ
ピーを保持しているとき、第１メモリのロケーションを
指すこととしてもよい。

【００４７】オペランド・アドレスを変換アドレスに変
換するための前記手段は変換索引バッファ（ＴＬＢ）を
使用してもよい。

【００４８】前記仮想キャッシュ・メモリ、前記実キャ
ッシュ・メモリおよび前記ＴＬＢはＤＲＡＭとしてもよ
い。

【００４９】

【作用】他にも特徴があるが、本発明がＢｅｄｅｒｍａ
ｎの解決手法と異なっているのは、仮想／実ページ番号
の代わりにポインタをタグとして２レベル・セット・ア
ソシアティブ・キャッシュに使用している点である。

【００５０】二次的メモリの各ロケーションは、データ
の他に、第２メモリのロケーションに入っているのと同
じデータが入っている対応するロケーションが第１メモ
リにあれば、「存在」を表す同義語情報を、第２メモリ
のロケーションに入っているのと同じデータが入ってい
る対応するロケーションが第１メモリになければ、「不
在」を表す同義語情報を収容する。二次的メモリの各ロ
ケーションは、同義語情報が「存在」ならば、第１メモ
リの対応するロケーションのアドレスを表す同義語アド
レスも収容する。コンパレータの出力が「ミス」を示し
ていれば、同義語情報と同義語アドレスが第２メモリの
対応するロケーションから読み取られる。

【００５１】同義語コンパレータは同義語情報と同義語
アドレスを第２メモリの対応するロケーションから受け
取り、同義語情報が「存在」ならば、第１メモリのアド
レス入力に同義語アドレスを出力する。

【００５２】

【実施例】本発明の特徴および利点は上述したとおりで
あるが、これらの特徴および利点を他の特徴および利点
と共に、添付図面に図示した本発明の好適実施例を参照
して、以下により詳しく説明する。

【００５３】以下では、実下位レベル・キャッシュに
は、常に、仮想上位レベル・キャッシュのラインが含ま
れているものとして説明する。このようにラインを含め
るという特性（ｉｎｃｌｕｓｉｏｎｐｒｏｐｅｒｔｙ
−挿入特性）は、マルチプロセッサの場合のキャッシュ
・コヒーレンスの複雑さを軽減する上で不可欠である
（Ｂａｅｒ外著「Ｏｎｔｈｅｉｎｃｌｕｓｉｏｎ
ｐｒｏｐｅｒｔｉｅｓｆｏｒｍｕｌｔｉ−ｌｅｖｅ
ｌｃａｃｈｅｈｉｅｒａｃｈｉｅｓ」、Ｐｒｏｃ．
１５ｔｈＩｎｔｌ．ＳｙｍｐｏｓｉｕｍｏｎＣｏ
ｍｐｕｔｅｒＡｒｃｈｉｔｅｃｔｕｒｅ，ｐｐ．７３
−８０，１９８８）。

【００５４】Ｗａｎｇと異なり、本発明によれば、Ｌ１
キャッシュがオーバヘッドを軽減するように改良されて
いるので、必要とする情報に即時にアクセスできる。

【００５５】本発明の好適実施例では、仮想上位レベル
・キャッシュ（Ｌ１）の各ラインには、仮想アドレスの
ほかに、実ポインタと共にタグが付けられている。この
実ポインタは、対応するデータ・ラインを収容する、実
下位レベル・キャッシュ（Ｌ２）内のラインを指してい
る。各Ｌ２キャッシュ・ラインには、実アドレスのほか
に、仮想ポインタと共にタグが付けられている。この仮
想ポインタは、対応するラインがＬ１に存在すれば、そ
のラインを指している。従って、Ｌ１は仮想アドレス・
キャッシュであり、Ｌ２は実アドレス・キャッシュであ
る。Ｌ１キャッシュまたはＬ２キャッシュのサイズはア
ドレス空間よりもはるかに小さいので、タグ単独ではな
く、アドレス・タグよりもはるかに短いポインタがタグ
と一緒に使用されている。ポインタによるＬ１とＬ２内
のラインの関係づけは、Ｌ２ラインがＬ１キャッシュに
ロードされると、それぞれＬ１とＬ２のディレクトリに
セットアップされる。

【００５６】仮想アドレス（ＶＡ）の一部は、仮想キャ
ッシュＬ１をインデックス付けするために使用され、仮
想アドレスの残り部分は仮想キャッシュ・ディレクトリ
にストアされる仮想アドレス・タグ（仮想タグまたはＶ
Ｔ）となり、このタグは対応するデータ・ラインがＬ１
にあるかどうかを示す。

【００５７】実アドレス（ＲＡ）の一部は、実キャッシ
ュＬ２をインデックス付け（インデクシング）するため
に使用され、実アドレスの残り部分は実キャッシュ・デ
ィレクトリにストアされる実アドレス・タグ（実タグま
たはＲＴ）となり、このタグは対応するデータ・ライン
がＬ２にあるかどうかを示している。

【００５８】Ｌ１キャッシュ内の各エントリごとに仮想
アドレスと関連づけられた実ポインタ（ＲＰ）は、Ｌ２
キャッシュが２５６ＫＢの場合は、６ビットで表されて
いる。Ｌ２内の各エントリごとに実アドレスと関連づけ
られた仮想ポインタ（ＶＰ）は、Ｌ１キャッシュが１６
ＫＢの場合は、２ビットだけで表されている。これらの
ポインタの長さは、対応するキャッシュのサイズに直接
に依存している。

【００５９】１ビット挿入タグ“Ｉ”は、対応するライ
ンがＬ１に含まれていると、Ｌ２ディレクトリにセット
される。Ｌ１キャッシュとＴＬＢへの並行アクセスは、
仮想ページ番号を使用して行われる。Ｌ１にミスが起こ
ると、ＴＬＢはそのページの対応する実アドレスを生成
し、Ｌ１は置換のためのラインを選択し、選択したセッ
トからどのラインを選択するかをＬ２に通知する。その
あと、実アドレスを用いてＬ２キャッシュをアクセスす
る。Ｌ２ディレクトリは実アドレス・タグと仮想ポイン
タを含んでおり、これらは、それぞれ基準実アドレスお
よび基準仮想アドレスと比較される。これまでに説明し
た仮想／実キャッシュ・システムによる場合は、得られ
る比較結果は次の４通りがある。

【００６０】ケース１：Ｌ２にミスが起こり、選択し
たＬ２セットの中の実アドレス・タグのどれもが参照実
アドレスに一致していない場合は、Ｌ２は置換のための
ラインを選択する。

【００６１】ケース２：Ｌ２にヒットが起こり、挿入
タグＩが０の場合は、Ｌ２ラインはＬ１にないので、Ｌ
１にロードする必要がある。

【００６２】ケース３：Ｌ２にヒットが起こり、挿入
タグＩが１であり、仮想ポインタ比較に失敗した場合
は、別のセットの中のＬ１ラインは必要とする情報を保
持する必要がある。

【００６３】ケース４：Ｌ２にヒットが起こり、挿入
タグＩが１であり、仮想ポインタ比較に成功した場合
は、一致しているのでＬ１には、同じセットの中の必要
とするラインが実際に入っている。従って、Ｌ１はそれ
が存在すれば、置換えたラインのためにラインを書き戻
すことを取り消す。

【００６４】本発明の好適実施例では、２：１（ｔｗｏ
−ｔｏ−ｏｎｅ）マルチプレクサがＬ１キャッシュ・ア
クセス・パス（経路）の前に付設されており、これはＬ
２からの「同義語存在」信号によって制御される。通常
の動作時には、Ｌ１がヒットすると、選択されたデータ
・ラインがＣＰＵに送られる。同義語が見つかると、仮
想ポインタと部分的なオフセット・ビットで形成された
Ｌ２からのアドレスがＬ１キャッシュをアクセスするた
めに使用され、Ｌ１セット内の選択が仮想ポインタによ
って行われる。仮想ポインタはＬ１セットの中のライン
を指しているので、Ｌ２での比較には仮想ポインタの一
部だけが必要である。仮想ポインタは２つの部分からな
っている。「キャッシュ内のセット」と「セット内のラ
イン」である。前者は（部分的な）オフセット・ビット
と連結されて、仮想アドレスと全く同じようにＬ１キャ
ッシュをアクセスし、後者はＬ１キャッシュに置かれた
セット内のラインを選択するために使用される。これに
より、重複するラインがＬ１になくなるので、逆変換テ
ーブルがなくても同義語の問題を解決することができ
る。

【００６５】図１は、本発明のデータ処理システムの代
表的なハイ・レベル・ブロック図である。代表的なデー
タ処理システムは、マイクロプロセッサ（ＣＰＵ）１０
２、第１メモリまたはキャッシュ（Ｌ１）１０４、第２
メモリまたはキャッシュ（Ｌ２）１０６、変換索引バッ
ファ（ＴＬＢ）１０８、コンパレータ１１０、マルチプ
レクサ１１２および３ステート・バッファ／ラッチ機構
１１４を備えている。キャッシュ１０４と１０６および
ＴＬＢはＳＲＡＭ、ＤＲＡＭなどで構成することができ
る。

【００６６】本発明の目的を達成するために、ＣＰＵ１
０２はベクトル型、スカラー型、スーパ−スカラー型な
どとすることができる。仮想メモリまたはキャッシュ１
０４（Ｌ１）および実メモリまたはキャッシュ１０６
（Ｌ２）は同一基板上にＣＰＵ１０２と一体に実装する
ことも、あるいは別々のディスクリート・デバイスにす
ることも可能である。また、別の方法として、Ｌ１をオ
ン・チップにし、Ｌ２をオフ・チップにすることも可能
である。

【００６７】図１に示す例では、データ処理システムは
３２ビット・アドレス空間、４ＫＢページ・サイズ、６
４Ｂ（バイト）ライン・サイズ、１６ＫＢサイズの２ウ
ェイＬ１、および２５６Ｋサイズの４ウェイＬ２を具え
る。３２ビット・アドレス空間内の３２ビット仮想アド
レスは、１２ビット・ページ・オフセットと２０ビット
仮想ページ番号をもっている。仮想ページ番号は、破線
１１６で示したパス（経路）によって概略を示すよう
に、通常動作時にＴＬＢとＬ１キャッシュに並列にアク
セスするために使用される。データ・ライン書戻しのた
めの書込みバッファがＬ１にあり、ＬＲＵ法でラインを
置き換えるとすると、Ｌ１キャッシュは、Ｌ１にミスが
起こったとき、どのラインを置き換えるかの判断をＬＲ
Ｕビットを通してＬ２に送って、その仮想ポインタをど
のようにセットアップするかをＬ２に知らせる。この制
御の流れは、破線１１８で示したパスに概略が示されて
いる。データの流れは示されていない。Ｌ２ディレクト
リに入っているバッファ・タグ“Ｂ”（図示せず）は、
Ｌ１内の対応するラインが書込みバッファ（図示せず）
に入っているかどうかを示すために使用される。

【００６８】Ｌ１にミスが検出されると、ＴＬＢ変換で
得た実ページ番号が部分的オフセット・ビットと連結さ
れて、Ｌ２キャッシュをアクセスする。実タグが得られ
た実アドレスＲＡ［０：１５］と一致し、挿入タグＩが
１ならば、同義語が検出されている。そこで、同義語ア
ドレス１２０は、同義語存在信号を使用してＬ１に渡さ
れて、ＭＵＸ１１２を制御する。同義語アドレスは点線
１２４で概略を示すように、Ｌ１内のデータをインデッ
クス付けするために使用される。

【００６９】以下の説明から理解されるように、仮想ポ
インタ比較のための追加ハードウェアは非常に単純化さ
れている。上述した例では、４個の１ビット・コンパレ
ータおよびそれに関連するロジックのみが必要である。
ＬＲＵ情報（セット内のライン）に対して仮想ポインタ
ＶＰ［０］を想定すると、同義語検査のためにＬ２内の
４ラインに対してＶＰ［１］だけを仮想アドレスＶＡ
［１９］と比較すればよい。従って、セット内のライン
を選択するための図２に示した部分的仮想ポインタ（詳
細は後述する）はＶＰ［０］であり、所定のオーバヘッ
トは最小になる。

【００７０】キャッシュ・ライン置換にＬＲＵ法を使用
しているとき、置き換えようとするＬＲＵラインがダー
ティであると、そのラインは、主メモリを更新するため
にＬ１の書戻しバッファに置かれるのが普通である。し
かし、同義語の場合には、当然、現基準ラインが同じキ
ャッシュ・セットにまだ残っているので、書き戻す必要
はない。従って、Ｌ１は書戻しをキャンセルするだけで
ある。Ｗａｎｇのキャッシュ・システムと異なり、キャ
ッシュ・ラインを移動する必要がないので、資源が節約
される。本発明のこの主要な特徴を、図２および図３を
参照して、以下で詳しく説明する。

【００７１】次に、図２および図３を参照して、本発明
の仮想キャッシュの好適実施例の代表例について説明す
る。図２では、ＣＰＵがデータ要求を行い、仮想アドレ
スを仮想キャッシュＬ１に送ったことを想定している
（ブロックまたはステップ２０２を参照）。ブロック２
０２は仮想アドレスを示し、この仮想アドレスは２０個
の仮想ページ番号（ＶＰＮ）ビット［０：１９］と１２
個のオフセット・ビット［２０：３１］から構成されて
いる。バス２０４は、下述する個々のブロックが必要と
する各種ＶＡビットを転送することを表している。

【００７２】上述したように、Ｌ１にキャッシュ・ミス
が起こると、４つの別々のケースが呼び出され、挿入タ
グ（Ｉタグ）が同義語を見つけるために使用される。Ｖ
Ｐが比較されて、同義語ラインが現在参照しているのと
同じセットにあるかどうかが判断される。ＶＰにオフセ
ットを加えたものが使用されて、Ｌ１をインデックス付
けし、同義語のセットおよびアドレスが判断される。ケ
ース４だけは、ラインが現在参照しているのと同じＬ１
内のセットにあることを示している。

【００７３】この例では、実キャッシュＬ２のＶＰは２
ビット、ＶＰ［０：１］、だけからなり、１ビットはＬ
１キャッシュ・セットをアクセスするために使用され、
２番目のＶＰビットはセットのラインを選択するために
使用される。ビットの割当ては設計時に選択される。

【００７４】セットを選択するには、仮想ページ番号
（ＶＰＮ）のＬＳＢ［１９］が通常動作時にマルチプレ
クサ（ＭＵＸ）２０６を通って、キャッシュＬ１のセッ
トを選択する（ブロック２０８を参照）。ページ・オフ
セットからの他のインデックス・ビットは図示していな
い。通常動作時にＶＰＮビットの選択を行うために、
「同義語不在」信号がＭＵＸ２０６の選択入力端に入
力される。（ＭＵＸ２０６は、機能的には図１に示し
たＭＵＸ１１４と同じである。）この例ではキャッシ
ュのサイズの関係で、ＭＵＸ２０６は１ビットだけを
選択する。

【００７５】これに対して、同義語がＬ２に存在し、そ
のことがＬ２選択ラインからの「同義語存在」で示され
たときは、ＶＰのビット［１］がＬ１のセットを選択す
るために使用される。Ｌ２制御信号からの「同義語存
在」が肯定されると、ＶＰ［１］はＬ２からＭＵＸ２
０６を通して渡されて、Ｌ１内のセットをアクセスす
る。ＭＵＸ２０６の出力は、ブロックまたはステップ
２１０に示すように、仮想キャッシュＬ１のセットを選
択する。

【００７６】ＶＰの２番目のビット（ＶＰ［０］）は、
データ選択ブロック２１２への“部分的ＶＰ”入力とし
て使用されて、セット内でデータがストアされているラ
インを選択する。この例では、Ｌ１は２ウェイ・セット
・アソシアティブ・キャッシュである。つまり、２重ブ
ロック２１２が示すように、セットごとに２ラインがあ
ることを意味する。従って、セット内のラインを選択す
るには、１ビットだけが必要である。例えば、“０”が
セットの１番目のラインを選択し、“１”が２番目のラ
インを選択する。

【００７７】図２および図３の左側に示すように、ＶＰ
Ｎの下位ビットはＴＬＢをインデックスするために使用
される。ＴＬＢをインデックスするために必要なＶＰＮ
のビット数はそのサイズによって決まる。この例では、
ＶＰＮの下位ビット（ＬＳＢ）は７個（ＶＰＮ［１３：
１９］）が使用されているが、これは、ＴＬＢが１２８
個（つまり、２⁷ ）のセットから構成されるためであ
る。“ＴＬＢ選択”ブロック２１４を参照のこと。仮想
アドレス・ビット［０：１２］は、ブロック２１６に示
すように、ＶＰＮとインデックスされたＴＬＢと比較さ
れる。“一致”するものが見つかると、実ページ番号が
即時に使用可能になり、ブロック２１８で３ステート・
バッファに入れられ、ブロック２２０でオフセットと連
結されたあと、Ｌ２キャッシュに送られる。

【００７８】ブロック２１６でＴＬＢと比較した結果、
一致するのものがない（“不一致”）と、仮想アドレス
がブロック２２２で３ステート・バッファに入れられ
る。そのあと、ループ２２４で示すように、２レベル・
セグメントやページ・テーブルなどの、オペレーティン
グ・システムの変換メカニズム２２３によって実アドレ
スに変換される。ループ２２４が一巡すると、“一致”
が保証され、完成した実アドレスはブロック２１８と２
２０を通過したあとＬ２キャッシュに渡される。

【００７９】ブロック２１８と２２２は、コンパレータ
・ブロック２２６によってＬ１キャッシュがヒットしな
かったと判断されると、“ｎｏ”結果によって生成され
た選択信号のタイミングに従って、ブロック２１６の結
果を条件付きでバッファに入れるように機能するデバイ
スで構成することが可能である。言い換えれば、ＴＬＢ
情報は、Ｌ１キャッシュがミスしたときは不要である。
ブロック２１８と２２２は、機能的には図１のブロック
１１４と同じである。

【００８０】上述したように、オフセットの下位ビット
（ＬＳＢ）は、ライン内のバイト・アドレスを示すため
に使用される。オフセットの残りの６ビットはＶＰＮの
下位ビット（ＬＳＢ）（ＶＰＮ［１９］）と一緒に使用
されて、キャッシュをアクセスする。従って、仮想アド
レスの残りのビット［０：１８］は仮想アドレス・タグ
（ＶＴ）となる。受け取ったＶＡのＶＴは、コンパレー
タ・ブロック２２８に示すように、ブロック２１０で選
択されたセット内の２ラインのＶＴと比較される。ブロ
ック２２６に、キャッシュがヒットしたかどうかが示さ
れ、ヒットしていれば、“ｙｅｓ”、ヒットしていなけ
れば、“ｎｏ”の結果を出力する。ブロック２２６と２
２８は、機能的には図１のブロック１１０と同じであ
る。

【００８１】ブロック２２６がキャッシュがヒットした
ことを示す“ｙｅｓ”を出力するか、あるいは同義語が
Ｌ２によって検出されると、ブロック２３０に示すよう
にブロック２１２で選択されたデータがＬ１出力レジス
タにロードされ、ＣＰＵに送られる。ＯＲをとる機能が
ブロック２３２によって実行される。ブロック２３２は
制御信号を出力し、３ステート・バッファ２３４をイネ
ーブルにすることによってブロック２１２からのデータ
を出力レジスタに渡す。

【００８２】Ｌ１でキャッシュ・ミスが起こり、そのこ
とが条件付きブロック２２６で“ｎｏ”結果によって示
されると、置き換えるべきラインを選択しなければなら
ない。本発明の好適実施例では、ブロック２３６に概略
を示すようにＬＲＵ法を備えた手段が置換候補のライン
を選択するために使用される。

【００８３】次に、ステップまたはブロック２３８で、
本発明のキャッシュ・システムは置換候補となるライン
がダーティか否かを判断する。結果が“ｙｅｓ”なら
ば、ブランチしてブロック２４０と２４２に移る。ブロ
ック２４０では、置換候補のラインに入っているデータ
が書込みバッファに送られる。このデータは、のちに公
知のように主メモリに書かれる。ブロック２４２では、
Ｌ１の置換候補ラインに対応するＬ２ラインの実ポイン
タの中のバッファ・タグ（Ｂタグ）が１にセットされ
る。これは、置換候補ラインがＬ１の書込みバッファに
送られたことを意味する。

【００８４】最後に、データが書込みバッファに送られ
て、Ｌ２キャッシュのＢタグ情報が更新されたあと、Ｌ
１キャッシュはＬＲＵビットをＬ２キャッシュに渡さな
ければならない（ステップまたはブロック２４４を参
照）。このＬＲＵビットは、どのラインが現在空きいて
いるかを示す。Ｌ２キャッシュはＬＲＵビットを使用し
て、ＣＰＵ要求のために仮想ポインタをセットアップす
る。

【００８５】条件付きブロック２３８で結果が“ｎｏ”
ならば、置換候補ラインに対応するＬ２ラインの実ポイ
ンタの中の挿入タグＩは０にリセットされることによっ
て調整される。置換候補ラインは、ＣＰＵから要求され
たデータでやがて置換されるので、主メモリに書き戻す
必要がないためである。Ｉタグのリセットはブロック２
４６に示されている。Ｉタグ情報が更新されると、制御
の流れはブロック２４４に移り、そこでＬＲＵビット
が、前述したようにＬ２キャッシュに渡される。

【００８６】次に、図４に示すように、Ｌ１にミスが起
こる度毎に、ＴＬＢが呼び出されて、Ｌ２キャッシュを
インデックスするために実アドレスを生成する。ＴＬＢ
から得た実アドレスは、図３の上方のブロック３０２に
示されている。この例では、実アドレスは２０ビットの
実ページ番号と１２ビットのオフセットを有する。実ア
ドレスのオフセットは仮想アドレスのオフセットと同じ
である。

【００８７】本発明の好適実施例では、Ｌ２は２５６Ｋ
Ｂキャッシュ（すなわち、総計２¹⁸個のロケーション）
であり、ライン・サイズは６４Ｂ（すなわち２⁶ ）であ
る。これは４ウェイ・セット・アソシアティブ・キャッ
シュ（セット当たり２² ライン）である。従って、総計
からライン・サイズとセット・サイズを差し引くと、キ
ャッシュ・システムがＬ２キャッシュをインデックスす
るためには１８−６−２＝１０ビットが必要である。こ
の実施例では、Ｌ２キャッシュのインデックシングは、
実ページ番号の６ビット・オフセットと最下位４ビット
（ビット［１６：１９］）、すなわち総計１０ビットを
使用して行われる。Ｌ２の各エントリの実タグは実ペー
ジ番号の残りのビットである［０：１５］。

【００８８】実アドレスが実キャッシュＬ２によって受
信されると、ステップまたはブロック３０４に示すよう
に、セットが選択される。次に、実アドレス・タグ（Ｒ
Ｔ）ビット［０：１５］が選択したセットの各ラインに
入っている実アドレス・タグと比較される。ライン３０
６は、ビット［０：１５］が実アドレスから直接に得た
ことを示す。Ｌ２は、ブロック３０８に概略を示すよう
に、４ウェイ・アソシアティブ（つまり、セットごとに
４ライン）であるので、４つの比較が必要である。“ｎ
ｏ”結果が示すように一致するものが見つからないと、
ループ３１０に入る。ループ３１０内では、Ｌ２ライン
が選択され（ブロック３１２を参照）、ＴＬＢから受け
取った実アドレスが主メモリに送られ（ブロック３１４
を参照）、主メモリによりＬ２に返されたデータがＬ２
の選択されたラインにロードされ（ブロック３１６を参
照）、Ｌ２ディレクトリが更新される（ブロック３１８
を参照）。流れがブロック３０４に戻り、ブロック３１
０での比較が再び行われる。この時点では、データは主
メモリからすでに取り出されているので、ブロック３１
０の比較結果は“一致”となる。

【００８９】ライン“一致”が起こると、ブロック３２
０に示すように、挿入タグＩが評価される。Ｉ＝１の比
較が“ｎｏ”ならば（つまり、データがＬ１キャッシュ
に含まれていなければ）、流れはブロック３２２へ進
む。ブロック３２２では、キャッシュＬ２とＬ１との関
係付けがセットアップされ、データがキャッシュＬ１へ
送られる。（Ｌ１の実ポインタがセットされ、Ｌ２の仮
想ポインタがセットされ、Ｉタグが１にセットされ
る。）Ｉ＝１の比較が“ｙｅｓ”ならば（つまり、デー
タがＬ１キャッシュに含まれていれば）、同義語が検出
されており、「Ｌ１への同義語」信号がＬ１へ送られて
そのことを知らせる。言い換えれば、１つのデータ・エ
ントリに２つの仮想アドレスがあることを意味する。こ
の信号は、仮想ポインタ・コンパレータ・ブロック３２
８のセットにより生成された結果を受け渡す手段として
１対の３ステート・バッファ・ブロック３２４、３２６
をイネーブルするためにも使用される。

【００９０】ブロック３１０でのライン比較と並行し
て、キャッシュＬ２の選択されたセットの各ライン内の
仮想ポインタの２番目のビットＶＰ［１］が、コンパレ
ータ・ブロック３２８のセットに示すように、受信した
実アドレスに対応する仮想アドレスのビット［１９］と
比較される（仮想アドレスはＣＰＵからＬ２とＴＬＢに
同時に送られているので、この仮想アドレスは即時に使
用可能である。また、どの仮想ポインタ・ビットを比較
に使用するかは、単に設計時の選択である。これは、図
２および図３に示したライン選択では使用されないビッ
トである。従って、この例では、図２および図３に示し
た「部分的ＶＰ」は仮想ポインタのビット［０］であ
る）。

【００９１】ブロック３２８の比較結果は、上述したケ
ース３および４に対応する。仮想ポインタの比較が失敗
した場合（つまり、一致するものが見つからない場合）
は、このことは、実際には別のセットの中のＬ１ライン
が必要とするデータを有することを示す。仮想ポインタ
比較の結果が一致の場合は、Ｌ１は実際に必要とするラ
インを、同じセット内に有する。従って、Ｌ１は置換る
ラインのために主メモリヘ書き戻すことをキャンセル
し、それが存在すればＢタグが０にリセットされる（ブ
ロック３３０を参照）。どちらの場合も、２ビット仮想
ポインタ（ＶＰ［０：１］）を仮想アドレス・オフセッ
トの６ビット（ＶＡ［２０：２５］）と連結して作られ
た同義語仮想アドレスが、ブロック３３２に概略を示す
ように、Ｌ１キャッシュをインデックスするために送ら
れる。実際には、オフセットは変わらないので、仮想ポ
インタ・ビットだけをＬ１に送ればよい。

【００９２】上述したように、ブロック３２８からの比
較情報の転送は、「ＳＹＮ」信号の制御を受けて、３ス
テート・バッファ・ブロック３２４と３２６によって制
御される。同義語が見つからなかったときは、Ｌ１の書
戻しをキャンセルする必要はない。

【００９３】

【発明の効果】以上の説明から理解されるように、本発
明の２レベル実／仮想キャッシュ・システムによれば、
ＴＬＢとＬ１キャッシュを並行にアクセスすることがで
き、逆変換テーブルがなくても同義語の問題を解決する
ことができる。この手法は単純化されているので、仮想
アドレス・キャッシュに関連して通常起こる同義語の問
題は、ハードウェアのオーバヘッドをほとんど必要とし
ないで解決することができる。

【００９４】以上、本発明の各種実施例について説明し
てきたが、これらの実施例は単なる例であり、これらに
限定されるものではない。従って、本発明の範囲は上述
した実施例に限定されるものではなく、請求項に定義さ
れた特徴事項および等価的特徴事項に従ってのみ定義さ
れるものである。

【図面の簡単な説明】

【図１】本発明のデータ処理システムを示す代表的なハ
イ・レベル・ブロック図である。

【図２】本発明の好適実施例における仮想キャッシュ
（Ｌ１）を示す代表的なフローチャートである。

【図３】本発明の好適実施例における仮想キャッシュ
（Ｌ１）を示す代表的なフローチャートである。

【図４】本発明の好適実施例における実キャッシュ（Ｌ
２）を示す代表的なフローチャートである。

【符号の説明】

１０２マイクロプロセッサ１０４第１メモリ（キャッシュ）１０６第２メモリ（キャッシュ）１０８変換索引バッファ（ＴＬＢ）１１０コンパレータ１１２マルチプレクサ１１４３ステート・バッファ／ラッチ機構１２０同義語アドレス２０４バス２２３オペレーティング・システムの変換メカニズム２２４ループ２３４３ステート・バッファＩ挿入タグＬ１仮想キャッシュＬ２実キャッシュＲＡ実アドレスＲＰ実ポインタＲＴ実タグＶＡ仮想アドレスＶＰ仮想ポインタＶＴ仮想タグ

Claims

【特許請求の範囲】

【請求項１】命令を受け取り、その命令からオペラン
ド・アドレスを生成するプロセッサと、アドレス入力、データ入力、データ出力、およびデータ
をストアするための複数のアドレス指定可能な第１ロケ
ーションを有する第１メモリと、アドレス入力、データ入力、データ出力、およびデータ
をストアするための複数のアドレス指定可能な第２ロケ
ーションを有する第２メモリであって、第２メモリ内の
複数のアドレス指定可能な第２ロケーションの１つまた
は複数の各々は、さらに、第１メモリが第２メモリにス
トアされたデータのコピーを保持しているかどうかを示
している同義語（シノニム）情報を含んでいる第２メモ
リと、プロセッサからオペランド・アドレスを受け取るための
アドレス入力を有し、オペランド・アドレスを第１メモ
リのロケーション・アドレスと比較し、オペランド・ア
ドレスに対応するアドレスをもつデータ・ブロックが第
１メモリにあれば、「ヒット」の出力を生成し、オペラ
ンド・アドレスに対応するアドレスをもつデータ・ブロ
ックが第１メモリになければ、「ミス」の出力を生成す
るための比較手段と、比較手段の出力を受け取り、比較手段の出力が「ヒッ
ト」ならば、オペランド・アドレスに対応するアドレス
をもつデータ・ブロックをストアしている第１メモリの
ロケーションにデータを入力し、あるいはそのロケーシ
ョンからデータを出力するための手段と、比較手段の出力を受け取り、オペランド・アドレスを第
２メモリのアドレスとなる変換アドレスに変換し、比較
手段の出力が「ミス」ならば、同義語情報および、変換
アドレスに対応する第１メモリのアドレスを構成する同
義語アドレスを出力するための手段と、同義語情報を受け取り、第１メモリがデータ・ブロック
のコピーを保持していることを同義語情報が示していれ
ば、第１メモリのアドレス入力に同義語アドレスを出力
するための手段とを具えたことを特徴とするデータ処理
システム。
【請求項２】第１メモリの複数のアドレス指定可能な
第１ロケーションの１つまたは複数の各々はさらに、デ
ータ・ブロックを保持している第２メモリのロケーショ
ンを指す第１ポインタを有することを特徴とする請求項
１に記載のデータ処理システム。
【請求項３】前記第１メモリは仮想アドレスをベース
としたキャッシュ・メモリを有することを特徴とする請
求項１に記載のデータ処理システム。
【請求項４】前記第２メモリは実アドレスをベースと
したキャッシュ・メモリを有することを特徴とする請求
項１に記載のデータ処理システム。
【請求項５】前記第１メモリは仮想アドレスをベース
としたキャッシュ・メモリを有し、前記第２メモリは実
アドレスをベースとしたキャッシュ・メモリを有するこ
とを特徴とする請求項２に記載のデータ処理システム。
【請求項６】前記同義語情報は、第１メモリがデータ
・ブロックのコピーを保持しているかどうかを示す１ビ
ット・フラグを有することを特徴とする請求項１に記載
のデータ処理システム。
【請求項７】前記同義語情報はさらに、第１メモリが
データ・ブロックのコピーを保持しているとき、第１メ
モリのロケーションを指している第２ポインタを有する
ことを特徴とする請求項６に記載のデータ処理システ
ム。
【請求項８】前記第２ポインタは仮想ポインタを有す
ることを特徴とする請求項７に記載のデータ処理システ
ム。
【請求項９】オペランド・アドレスを変換アドレスに
変換するための前記手段は変換索引バッファ（ＴＬＢ）
を有することを特徴とする請求項５に記載のデータ処理
システム。
【請求項１０】データ処理システム上で実行されるデ
ータ処理方法において、命令を受け取り、その命令からオペランド・アドレスを
生成するステップと、アドレス入力、データ入力、データ出力、およびデータ
をストアするための複数のアドレス指定可能な第１ロケ
ーションもつ第１メモリを用意し、アドレス入力、データ入力、データ出力、およびデータ
をストアするための複数のアドレス指定可能な第２ロケ
ーションをもつ第２メモリであって、第２メモリの複数
のアドレス指定可能な第２ロケーションの１つまたは複
数の各々はさらに、第１メモリが第１メモリにストアさ
れたデータのコピーを保持しているかどうかを示した同
義語（シノニム）情報を含んでいる第２メモリを用意
し、プロセッサからオペランド・アドレスを受け取るための
アドレス入力をもつ比較手段を使用して、オペランド・
アドレスを第１メモリのロケーション・アドレスと比較
し、オペランド・アドレスに対応するアドレスをもつデ
ータ・ブロックが第１メモリにあれば、「ヒット」の出
力を生成し、オペランド・アドレスに対応するアドレス
をもつデータ・ブロックが第１メモリになければ、「ミ
ス」の出力を生成するステップと、比較手段の出力を受け取り、比較手段の出力が「ヒッ
ト」ならば、オペランド・アドレスに対応するアドレス
をもつデータ・ブロックをストアしている第１メモリの
ロケーションにデータを入力し、あるいはそのロケーシ
ョンからデータを出力するステップと、比較手段の出力を受け取って、オペランド・アドレスを
第２メモリのアドレスとなる変換アドレスに変換し、比
較手段の出力が「ミス」ならば、同義語と、変換アドレ
スに対応する第１メモリのアドレスを構成する同義語ア
ドレスとを出力するステップと、同義語情報を受け取り、第１メモリがデータ・ブロック
のコピーを保持していることを同義語情報が示していれ
ば、第１メモリのアドレス入力に同義語アドレスを出力
するステップと具えたことを特徴とするデータ処理方
法。