JP2000200221A - キャッシュメモリ装置及びその制御方法 - Google Patents

Abstract

(57)【要約】 【課題】 簡素な回路構成を備えながらも、キャッシュ
メモリのスループットを低下させることなく２以上のウ
エイを対象に円滑なフリーズ処理が実行でき、ニーズに
対応したキャッシュメモリ機能が実現できるキャッシュ
メモリ装置及びその制御方法を提供する。 【解決手段】 ＬＲＵデコード方式を採用し、Ｎを２以
上の整数としたＮウエイ・セット・アソシアティブ方式
のキャッシュメモリ装置１１は、キャッシュメモリの各
ウエイのアクセス履歴情報を記憶するＬＲＵメモリ部３
５と、各ウエイのフリーズ情報を記憶するフリーズメモ
リ部３６と、記憶されたアクセス履歴情報を修正するこ
となく該アクセス履歴情報とフリーズ情報とに基づい
て、特定のウエイをフリーズするためのリプレース信号
を生成するリプレース判定部３７とを備えている。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、キャッシュメモリ
装置及びその制御方法に関し、特に、フリーズ機能を改
善したキャッシュメモリ装置及びその制御方法に関す
る。

【０００２】

【従来の技術】コンピュータシステムの分野における大
容量の主記憶装置は、その動作速度がマイクロプロセッ
サの動作速度に比して遅い。このため、最近のマイクロ
プロセッサでは、例えばＳＲＡＭ（Static Random Acce
ss Memory）等から成る小容量で高速なキャッシュメモ
リをマイクロプロセッサの内部、もしくはその近傍に配
置し、データの一部をキャッシュメモリに記憶すること
によって、マイクロプロセッサの速度を低下させること
なく作動させている。

【０００３】上記コンピュータシステムでは、中央処理
装置からキャッシュメモリへのリードアクセス又はライ
トアクセスがミスヒットした場合に、主記憶装置から新
たに読み出したデータの一部が、エントリ（登録項目）
としてキャッシュメモリの空きブロックに格納される。
このとき、空きブロックが存在しない場合には、複数の
ブロックのいずれか１つを選択し、選択されたブロック
に格納されているエントリを主記憶装置に戻してブロッ
ク内を空き状態にし、この空きブロックに新たに読み出
したデータを格納するエントリ置換処理が必要になる。

【０００４】上記エントリ置換処理では、最も以前に参
照したデータを格納しているブロックを選択する手法、
即ち、ＬＲＵ（Least Recently Used）デコード方式が
一般的に採用されている。このＬＲＵデコード方式によ
ってキャッシュメモリの使用効率が向上し、その結果、
マイクロプロセッサの実行速度が向上する。

【０００５】しかし、マイクロプロセッサが処理するプ
ログラムの中には、アクセス頻度は少ないものの、ひと
たび起動された場合には高速に処理しなければならない
ような特殊な処理も存在する。例えば、自動車の制御用
にマイクロプロセッサを使用し、表示パネルの制御やブ
レーキの制御を行う場合を考える。

【０００６】表示パネルの制御は、運転中であれば速度
や走行距離などの状況が時々刻々と変化するので、絶え
ず所定のプログラムが実行される。これに対して、急ブ
レーキをかけたときにタイヤがロックされないように制
御するプログラムは、それほど頻繁に処理されることは
ない。従来のキャッシュメモリを使用した場合、表示用
プログラムはキャッシュメモリに取り込まれるが、ブレ
ーキ制御用プログラムは取り込まれている確率が低くな
る。このため、急ブレーキをかけても、ブレーキ制御用
プログラムの実行開始までに時間がかかることが予想さ
れる。

【０００７】一方、走行距離を表示するプログラムは、
実行に多少時間がかかっても問題とならないにも拘わら
ず、キャッシュメモリを占有することになり、キャッシ
ュメモリの利用効率を悪くし、或いは、プログラム全体
の処理速度を低下させるという問題を引き起こす。

【０００８】上記問題を解決するため、キャッシュメモ
リにフリーズ機能やパージ機能を設けることが知られて
いる。フリーズ機能は、アクセス頻度は少ないものの、
ひとたび起動された場合には高速に処理しなければなら
ないようなプログラムを予めキャッシュメモリ内にコピ
ーしておき、その領域を書き換え禁止にしておく機能で
ある。この機能を有することで、コンピュータシステム
は、必要なときに所定のプログラムをキャッシュメモリ
から読み出して実行することができ、これにより実行時
間が短縮する。

【０００９】逆に、パージ機能は、アクセス頻度は多い
が、実行速度がそれほど要求されないようなプログラム
をキャッシュメモリ内に保存しておくことなく、その領
域を解放する機能である。この機能を有することで、キ
ャッシュメモリに余裕ができ、優先度の高い他のプログ
ラムやデータをキャッシュメモリに取り込むことがで
き、これにより、キャッシュメモリの利用効率が向上
し、総合的な実行時間が短縮する。

【００１０】従来のセット・アソシアティブ・キャッシ
ュで、１ウエイのみのフリーズを可能にした半導体記憶
装置が、特開平６−１１０７８７号公報に記載されてい
る。図１３は、この公報に対応する半導体記憶装置のフ
リーズ制御部分の構成を示すブロック図である。

【００１１】図１３に示すように、フリーズ制御部分
は、タグメモリ５１、データメモリ５２、パージ・フリ
ーズレジスタ４３、ＬＲＵパージ・フリーズ制御部４
２、ＬＲＵメモリ優先順位情報更新制御部４４、ＬＲＵ
メモリ４０、アドレスコンパレータ５７、制御部５８、
及びセレクタ５９を備えている。

【００１２】タグメモリ５１は、ウエイ５１Ａ〜５１Ｄ
を有し、キャッシュデータのキャッシュメモリにおける
記憶アドレスをそのデータとして記憶するもので、本来
のタグデータの他にバリッドビットが追加されている。
データメモリ５２は、ウエイ５２Ａ〜５２Ｄを有し、キ
ャッシュデータを記憶するものであり、高速アクセスが
可能なＳＲＡＭ等の半導体メモリで構成されている。

【００１３】パージ・フリーズレジスタ４３は、ＣＰＵ
の指示に従って、データメモリ５２に記憶されたデータ
を無効化（パージ）するか書換え禁止（フリーズ）にす
るかを設定するとともに、ＣＰＵが指定する優先順位を
設定する。ＬＲＵパージ・フリーズ制御部４２は、パー
ジ・フリーズレジスタ４３に設定されたデータを用い
て、ＬＲＵアルゴリズムに基づきタグメモリ５１のバリ
ッドビットの書換えを行なう。

【００１４】ＬＲＵメモリ優先順位情報更新制御部４４
は、ＬＲＵパージ・フリーズ制御部４２の制御により、
ＬＲＵメモリ４０に記憶された優先順位情報の書換えを
行なう。ＬＲＵメモリ４０は、優先順位情報を記憶す
る。アドレスコンパレータ５７は、ＣＰＵやＤＭＡコン
トローラから与えられるアドレスと、このアドレスに従
ってタグメモリ５１から読み出されたアドレスデータと
を比較し、キャッシュヒットか否かを判定する。

【００１５】制御回路５８は、アドレスコンパレータ５
７の比較結果、ＬＲＵメモリ４０から出力された優先順
位情報、及び、外部からのタイミング制御用のリードイ
ネーブル信号等に応答して、キャッシュメモリ５２やセ
レクタ５９の入出力を制御する。セレクタ５９は、外部
からのデータをキャッシュメモリ５２のどのウエイに入
力するか、又はどのウエイのデータを出力するかを切り
換える。

【００１６】次に、上記公報に記載の半導体記憶装置の
動作について説明する。ＣＰＵ、ＤＭＡコントローラ等
によりアドレスが外部から与えられると、このアドレス
は、タグメモリ５１に与えられ、ここでデータメモリ５
２のアドレスに変換されるとともに、アドレスコンパレ
ータ５７に入力される。

【００１７】また、各データの優先順位情報は、ＬＲＵ
メモリ４０に記憶される。アドレスコンパレータ５７
は、外部から入力されたアドレスとタグメモリ５１のア
ドレスとを比較し、ＣＰＵのリード動作においてキャッ
シュヒットかミスヒットかを判定する。キャッシュヒッ
トであれば、データメモリ５２のデータを外部のＣＰＵ
に出力し、ミスヒットであれば、主記憶装置（図示せ
ず）の記憶内容をデータメモリ５２に読み込む。

【００１８】また、ＣＰＵからのパージ・フリーズ命令
及びＣＰＵの命令に応じて指定する優先順位は、パージ
・フリーズレジスタ４３に書き込まれる。ＬＲＵパージ
・フリーズ制御部４２は、優先順位の情報に従って、Ｌ
ＲＵメモリ優先順位情報更新制御部４４を制御すること
により、ＬＲＵメモリ４０内の優先順位情報を操作し、
最適なパージ・フリーズ状態を自動的に設定する。パー
ジ処理の場合、ＬＲＵパージ・フリーズ制御部４２は、
タグメモリ５１内にあるバリッドビットを同時に操作
し、タグアドレスに対応するデータを無効にする。

【００１９】図１４は、ＬＲＵパージ・フリーズ制御部
４２のフリーズ処理を示す流れ図である。まず、フリー
ズの対象となる優先順位をパージ・フリーズレジスタ４
３から読み出す（ステップＳ１）。次に、図示しないＬ
ＲＵメモリの全エントリから順に優先順位情報を読み出
し（ステップＳ２）、該当する優先順位のウエイが必ず
他のウエイよりも高い優先順位となるように設定する
（ステップＳ３、Ｓ４）。

【００２０】ただし、その際、優先順位が高くなるよう
に毎回設定するのではなく、優先順位情報を読み出すと
きにのみ疑似的に優先順位が高いかのようにみせる処理
を施す。例えば、ウエイＡにフリーズしておきたいデー
タがあるとき、ウエイＤがヒットしたとしてもウエイＡ
の優先順位を疑似的に高めておくことにより、ウエイＡ
のデータにプロテクトをかけることができる。これは、
使用しないデータは優先順位が自動的に下がるというハ
ードウエア上の制約があるからである。

【００２１】一方、ＬＲＵパージ・フリーズ制御部４２
のパージ処理では、まず、パージの対象となる優先順位
をパージ・フリーズレジスタ４３から読み出す。次に、
ＬＲＵメモリの全エントリから優先順位情報を順に読み
出し、該当する優先順位のウエイが最下位の優先順位と
なるように優先順位情報を操作し更新する。更に、タグ
メモリ５１内にあるバリッドビット（有効ビット）をイ
ンバリッドにし、該当するデータを無効にする。

【００２２】以上のような記憶制御手順を実行すること
により、図１５における斜線を付した部分、即ち、この
例では、ウエイ５２Ａ、５２Ｂ、５２Ｃのうちの優先順
位３に該当するエントリ５２Ｂｂ、５２Ｂｃ、５２Ｃ
ａ、…のみをパージ／フリーズすることができ、上述し
た頻繁に参照されるデータ群のようなデータのみをパー
ジ／フリーズすることが可能となる。図１５は、従来の
各記憶データの優先順位を考慮したパージ／フリーズ制
御の概要を示す図である。

【００２３】このように、上記公報に記載の半導体記憶
装置では、ＬＲＵ制御によってフリーズ命令を考慮して
おり、パージ／フリーズ命令と指定する優先順位とがパ
ージ・フリーズレジスタ４３に書き込まれると、ＬＲＵ
パージ／フリーズ制御部４２が、ＬＲＵメモリ優先順位
情報の更新制御部４４を制御することによって、ＬＲＵ
メモリ４０内の優先順位情報を操作し、所定のパージ／
フリーズ状態を設定する。

【００２４】

【発明が解決しようとする課題】上記従来の半導体記憶
装置では、優先順位情報を読み出すときにのみ所定の処
理を施せばよいものの、その都度に、ＬＲＵメモリ４０
内の全エントリに対して優先順位を書き換える処理を行
わなければならない。また、ＣＰＵがキャッシュメモリ
の所定のアドレスをアクセスしてミスヒットした場合、
キャッシュメモリは、ＬＲＵメモリ４０を参照して、最
も古くアクセスされたウエイを選択し、この選択したウ
エイのデータメモリ５２に新しいデータを書き込むとと
もに、ＬＲＵメモリ４０の記憶内容を書き換える。

【００２５】図１５に示すように、ＬＲＵメモリ４０
は、エントリ４０ａ、４０ｂ、４０ｃ・・・を有してい
る。また、データメモリ５２のウエイ５２Ａはエントリ
５２Ａａ〜５２Ａｃ、ウエイ５２Ｂはエントリ５２Ｂａ
〜５２Ｂｃ、ウエイ５２Ｃはエントリ５２Ｃａ〜５２Ｃ
ｃを夫々有している。例えば、エントリ４０ｂのウエイ
Ｂ（ＷＡＹ−Ｂ）をフリーズして、ＬＲＵメモリ４０を
Ｃ＞Ａ＞Ｂとなるように書き換えたとする。この場合、
Ｃが最も最近にアクセスされたものであり、Ｂが最も古
くアクセスされたことを示す。この後に、ミスヒットが
生じた場合、ＷＡＹ−Ｂに新しいデータが書き込まれる
ことになり、優先度の高いＷＡＹ−Ｃが書き換えられる
ことはない。このとき、ＷＡＹ−Ｂが直近にアクセスさ
れたことになるので、キャッシュメモリはＬＲＵメモリ
４０を書き換えて、Ｂ＞Ｃ＞Ａとする。

【００２６】このように、上述のフリーズ処理を行って
いても、ミスヒットするたびにＬＲＵメモリ４０の内容
が書き換えられるので、ミスヒットのたびにフリーズ処
理を実行しなければ、ウエイ数に相当する回数のミスヒ
ットの発生により、フリーズ処理したはずの記憶内容が
消えることになる。逆に、ミスヒットするたびにフリー
ズ処理を実行することにすると、エントリ数に相当する
回数のフリーズ処理を実行しなければならないので、キ
ャッシュメモリに余分な負荷がかかり、キャッシュメモ
リのスループットが低下するという問題を引き起こす。

【００２７】上記問題を回避するため、前述の公報に記
載の半導体記憶装置では、ＬＲＵメモリ４０に記憶する
ウエイのアクセス履歴の数を（総ウエイ数−１）に制限
している。例えば４ウエイのときには、３ウエイ分だけ
のアクセス履歴を記憶するように構成されている。この
ため、アクセス履歴が最も古くなっても、３番目より古
くなることはないので、フリーズ処理したウエイが他の
データで置き換えられることはない。しかし、これは、
ミスヒットした場合、残りの１ウエイのみを使って書き
換えることを意味しており、複数のウエイを設けた本来
の価値が発揮できない。

【００２８】例えば、図１５では、ＷＡＹ−Ａ〜ＷＡＹ
−Ｃまでのアクセス履歴をＬＲＵメモリ４０に記憶し、
残りのＷＡＹ−Ｄのアクセス履歴については何ら考慮し
ないようになっている。従って、ＷＡＹ−Ａ〜ＷＡＹ−
Ｃのいずれかのウエイがヒットした場合には、アクセス
履歴を書き換えるが、ＷＡＹ−Ｄがヒットした場合の処
理については何ら考慮されていない。仮に、ＷＡＹ−Ａ
〜ＷＡＹ−Ｄのいずれにもヒットしなかった（ミスヒッ
トした）場合、上記従来の半導体記憶装置では、上述の
理由により、ＷＡＹ−Ａ〜ＷＡＹ−Ｃを書き換えること
ができないので、ＷＡＹ−Ｄに新しいデータを取り込む
と推察される。言い換えれば、４ウエイのキャッシュメ
モリでありながら、１ウエイのキャッシュメモリとして
のみ機能することになる。これは、データのヒット確率
を低下させるとともに、ＣＰＵからみたデータのスルー
プットを著しく低下させることになる。

【００２９】更に、複数ウエイのうち１ウエイのみのフ
リーズ処理にしか対応できないので、複数ウエイにまた
がるような中規模のプログラムをキャッシュメモリに取
り込みたい場合、中規模のプログラム複数の一部分のみ
フリーズ処理することになる。このため、残りのプログ
ラム部分は、必要なときに再度取り込まなければなら
ず、十分なフリーズ機能を果たせない。

【００３０】本発明は、上記に鑑み、簡素な回路構成を
備えながらも、キャッシュメモリのスループットを低下
させることなく２以上のウエイを対象に円滑なフリーズ
処理が実行でき、ニーズに対応したキャッシュメモリ機
能が実現できるキャッシュメモリ装置及びその制御方法
を提供することを目的とする。

【００３１】本発明は更に、上記目的を達成した上で、
複数のウエイを対象としたフリーズ処理を可能とし、比
較的規模が大きいデータでも格納が可能となるキャッシ
ュメモリ装置を提供することを目的とする。

【００３２】

【課題を解決するための手段】上記目的を達成するため
に、本発明のキャッシュメモリ装置は、ＬＲＵデコード
方式を採用し、Ｎを２以上の整数としたＮウエイ・セッ
ト・アソシアティブ方式のキャッシュメモリ装置におい
て、キャッシュメモリの各ウエイのアクセス履歴情報を
記憶するＬＲＵメモリと、各ウエイのフリーズ情報を記
憶するフリーズメモリと、記憶されたアクセス履歴情報
を修正することなく該アクセス履歴情報と前記フリーズ
情報とに基づいて、特定のウエイをフリーズするための
リプレース信号を生成するリプレース判定手段とを備え
ることを特徴とする。

【００３３】本発明のキャッシュメモリ装置では、アク
セス履歴情報の書込み後にＬＲＵメモリから読み出した
アクセス履歴情報とフリーズメモリから読み出したフリ
ーズ情報とに基づいてリプレース信号を生成する。この
ため、従来の半導体記憶装置の場合のようにアクセス履
歴情報（ライトデータ）の書換えの度にパージ・フリー
ズレジスタを参照してヒット情報を加味しつつ行うよう
な処理が不要となり、複数種類のフリーズ情報を適宜選
択することで、複数ウエイに対応するリプレース信号が
容易に生成できる。これにより、キャッシュメモリのス
ループットを低下させず２以上のウエイを対象とした円
滑なフリーズ処理が可能になり、ニーズに応じたキャッ
シュメモリ機能を簡素な回路構成で得ることが可能とな
る。また、ＬＲＵの元データを破棄することがないの
で、フリーズ状態を解除したとき、それまでのアクセス
履歴に基づいた通常のＬＲＵ方式に直ちに復帰できる。

【００３４】ここで、前記リプレース判定手段が、前記
フリーズ情報と前記アクセス履歴情報とを取り込んで中
間情報を生成するフリーズ制御回路と、前記フリーズ制
御回路からの前記中間情報に対応して前記リプレース信
号を生成するＬＲＵデコード回路とを備えることが好ま
しい。この場合、リプレース判定手段を簡素な回路構成
で実現することができる。

【００３５】また、前記フリーズ情報としてＮ−１ウエ
イに対応する記憶容量を備えることが好ましい。この場
合、Ｎウエイの内の１ウエイのみをリプレース対象とし
て残し、他のウエイを全てフリーズ対象とすることがで
きるので、従来に比して書換え回数が大幅に減少する。
例えば、１つのサブルーチンを１ウエイ相当のメモリに
格納しようとしてもデータ量が多くて格納できないよう
な場合でも、Ｎ−１のウエイの活用が実現することによ
り、複数のウエイを対象としたフリーズ処理が可能とな
り、比較的規模が大きいデータでも格納することが可能
となる。

【００３６】更に好ましくは、前記リプレース信号が、
各ウエイに夫々対応して出力されるビット値から成る。
この場合、ＬＲＵデコード回路を簡素な回路構成から得
ることができる。

【００３７】本発明のキャッシュメモリ装置の制御方法
は、ＬＲＵデコード方式を採用し、Ｎを２以上の整数と
したＮウエイ・セット・アソシアティブ方式のキャッシ
ュメモリ装置を制御する制御方法において、キャッシュ
メモリの各ウエイのアクセス履歴情報を記憶し、キャッ
シュメモリの各ウエイのフリーズ情報を記憶し、記憶さ
れた前記アクセス履歴情報を修正することなく該アクセ
ス履歴情報と前記フリーズ情報とに基づいてリプレース
対象のウエイを算出することを特徴とする。

【００３８】本発明のキャッシュメモリ装置の制御方法
では、アクセス履歴情報の書込み後に読み出したアクセ
ス履歴情報とフリーズ情報とに基づいてリプレース対象
のウエイを算出するので、複数種類のフリーズ情報を適
宜選択することで、複数ウエイに対応するリプレース信
号を容易に生成することができ、ニーズに応じたキャッ
シュメモリ機能が実現できる。また、ＬＲＵの元データ
を破棄することがないので、フリーズ状態を解除したと
き、それまでのアクセス履歴に基づいた通常のＬＲＵ方
式に直ちに復帰できる。

【００３９】ここで、本発明では、前記アクセス履歴情
報と前記フリーズ情報とに基づいてリプレース対象のウ
エイを算出する際に、前記フリーズ情報に対応して前記
アクセス履歴情報を中間情報に変換した後にリプレース
対象のウエイを算出することが好ましい。この場合、既
に設計済みのキャッシュメモリ装置の資産を継承しなが
ら、簡単な論理回路を付加するだけで、フリーズ機能付
きのキャッシュメモリ装置を実現できる。また、ＬＲＵ
の元データを破棄することがないので、フリーズ状態を
解除したとき、それまでのアクセス履歴に基づいた通常
のＬＲＵ方式に即座に復帰できる。

【００４０】更に好ましくは、前記アクセス履歴情報と
前記フリーズ情報とに基づいてリプレース対象のウエイ
を算出する際に、Ｎウエイのアクセス順序を最近アクセ
スされたウエイから順に並べたとき、フリーズ対象のウ
エイが１乃至Ｎ−１のいずれかのアクセス順序になるよ
うな中間情報を生成した後にリプレース対象のウエイを
算出する。この場合、ＬＲＵの機能を損なうことなく、
リプレース対象のウエイを算出することができる。

【００４１】具体的には、ウエイＡに対するウエイＢの
アクセス順序を表すアクセス履歴情報をＷ［Ａ，Ｂ］と
し、ウエイＡ及びウエイＢのフリーズ情報を夫々ＦＲＺ
［Ａ］及びＦＲＺ［Ｂ］とするとき、前記中間情報とし
てのＭ［Ａ，Ｂ］への変換が、 M［A,B］＝ W［A,B］+FRZ［A］ （但し、0≦A
＜B＝（N-1）） M［A,B］＝（W［A,B］+FRZ［A］）×!FRZ［B］ （但し、0≦A＜B＜（N-1）であり、!FRZ［］はFRZ［］
の反転値を示す）に基づいて行われる。この場合、簡単
な論理で、フリーズ対象のウエイがリプレース対象のウ
エイにならないように変換処理することができるので、
小規模な論理回路を追加するだけでフリーズ機能付きの
キャッシュメモリ装置が実現できる。

【００４２】具体的には、リプレース対象のウエイをＸ
とするとき、該ウエイＸの算出は、次式

【数２】 に基づいて行われる。この場合、上記中間情報を生成す
ることにより、従来のリプレース対象ウエイの算出回路
をそのまま利用することも可能となる。

【００４３】

【発明の実施の形態】図面を参照して本発明を更に詳細
に説明する。図１は、本発明の一実施形態例におけるコ
ンピュータシステムの構成を示すブロック図である。

【００４４】本実施形態例におけるコンピュータシステ
ムは、ＣＰＵ１０と、コピーバック方式を採用したキャ
ッシュメモリ装置１１と、バスコントロールユニット
（以下、ＢＣＵと呼ぶ）１２と、主記憶装置１４と、シ
ステムバス１３とから概略構成されている。ここでは、
ＬＲＵアルゴリズムに基づく４ウエイ・セット・アソシ
アティブ方式のキャッシュメモリ装置１１を例に説明す
るが、本発明は４ウエイに限定されるものではない。

【００４５】ＣＰＵ１０は、コンピュータシステムの各
部を制御してデータ処理を行うと共に、キャッシュメモ
リ装置１１に対し、所定のアドレス信号ＡＤを供給し
て、所望の命令やデータ等（以下、記憶データと呼ぶ）
の授受を行う。

【００４６】キャッシュメモリ装置１１は、要求された
アドレス信号ＡＤに対応する記憶データＤＴＭ［］が自
己装置内に存在するとき（以下、ヒットと呼ぶ）、ＣＰ
Ｕ１０に対して記憶データＤＴを供給する。

【００４７】一方、要求されたアドレス信号ＡＤに対応
する記憶データＤＴＭ［］が自己装置内に存在しないと
き（以下、ミスヒットと呼ぶ）、キャッシュメモリ装置
１１は、当該記憶データＤＴＭ［］を主記憶装置１４か
ら取得するために、ＢＣＵ１２に対しアドレス信号ＢＡ
Ｄを送ってメモリリードサイクルの発行を要求する。こ
こで、各信号名の後の［］内にはウエイの番号が入る
が、その記載を省略している。

【００４８】ＢＣＵ１２は、システムバス１３を介して
アドレス信号ＢＡＤを主記憶装置１４に送り、主記憶装
置１４から記憶データＢＤＴを取得する。その後、ＢＣ
Ｕ１２は、キャッシュメモリ装置１１に記憶データＢＤ
Ｔを供給し、キャッシュメモリ装置１１は、記憶データ
ＢＤＴを、所定の場所に記憶するとともにＣＰＵ１０に
対して供給する。同時に、キャッシュメモリ装置１１
は、読み込んだ記憶データＢＤＴを自装置内に記憶す
る。このとき、自装置内に書き込む領域が空いていない
ときには、前回のアクセス履歴が最も古いウエイの記憶
データを主記憶装置１４に書き戻し（コピーバック）し
てから、新たに読み出した記憶データＢＤＴで書き換え
る。

【００４９】このようにして、ＣＰＵ１０は、所望のア
ドレスの記憶データをキャッシュメモリ装置１１との間
で授受することができる。

【００５０】図１に示すように、キャッシュメモリ装置
１１は、タグメモリ部３１、比較部３２、データメモリ
部３３、セレクタ部３４、ＬＲＵ部３５、フリーズメモ
リ部３６、リプレース判定回路３７、及びコントローラ
３８から概略構成されている。

【００５１】本実施形態例では、主記憶装置１４の記憶
容量を１ＭＢ（Ｂはバイトを意味する）であるとし、デ
ータメモリ部３３の記憶容量を１ｋＢであるとする。デ
ータメモリ部３３は４個のウエイから成り、各ウエイは
夫々６４個のエントリに分割され、各エントリは４Ｂ
（３２ビット）の記憶データＤＴＭ［］を記憶してい
る。１ウエイの記憶容量は２５６Ｂ（＝６４×４）であ
り、４ウエイでは１ｋＢとなる。そして、主記憶装置１
４もこのようなデータメモリ部３３の構成に対応して、
２５６Ｂ毎の４０９６（１ＭＢ／２５６Ｂ）個のブロッ
クに分割されている。

【００５２】各記憶データＤＴＭ［］をアクセスするた
めにＣＰＵ１０から供給されるアドレス信号ＡＤのビッ
ト長は２０ビットであり、下位２ビット｛１：０｝は、
４バイトのデータのうち１バイトを選択するためのバイ
トアドレスである。また、アドレス信号ＡＤの中位６ビ
ット｛７：２｝は、６４個のエントリのいずれか１つを
選択するためのインデックスアドレスＩＡＤであり、上
位１２ビット｛１９：８｝は、主記憶装置１４の４０９
６個あるブロックのいずれか１つを選択するためのタグ
アドレスＴＡＤである。

【００５３】タグメモリ部３１は、各ウエイの各エント
リに対応するタグアドレスＴＡＤと、主記憶装置１４と
データメモリ部３３との記憶内容が一致しているか否か
を示すダーティビットＤＲＴとを記憶している。タグメ
モリ部３１は、コントローラ３８が供給するアドレス信
号ＡＤＴの中位６ビットのインデックスアドレスＩＡＤ
Ｔに基づいてタグメモリをアクセスし、そこに記憶され
ているタグアドレスＴＡＤを比較部３２に出力する。ミ
スヒットして新たな記憶データＤＴＭ［］がデータメモ
リ部３３に取り込まれたときには、タグメモリ部３１
は、新しいタグアドレスＴＡＤを所定のウエイと所定の
エントリに対応した位置に記憶する。

【００５４】また、データメモリ部３３の記憶内容を更
新する前に、コントローラ３８はタグメモリ部３１から
ダーティビットＤＲＴＯ［］を読み取り、ＤＲＴＯ［］
が“１”であれば、キャッシュメモリ内部のデータを追
い出し、データメモリ部３３の記憶データＤＴＭ［］を
主記憶装置１４にコピーバックする。ダーティビットＤ
ＲＴＯ［］が“０”であれば、コントローラ３８は新た
な記憶データＤＴＭ［］でデータメモリ部３３を上書き
する。

【００５５】比較部３２はウエイ数分の比較回路を有す
る。各比較回路は、コントローラ３８から出力されるア
ドレス信号ＡＤＴの上位１２ビットのタグアドレスＴＡ
Ｄと、タグメモリ部３１から出力されるタグアドレスＴ
ＡＭ［］とを比較して、一致した場合にはヒット信号
（ＨＩＴ）として“１”を出力し、不一致の場合にはミ
スヒット信号として“０”を出力する。ここで、各ウエ
イ０〜３に対応したヒット信号を夫々ＨＩＴ［０］〜Ｈ
ＩＴ［３］とする。

【００５６】データメモリ部３３は、６４エントリ×４
ウエイ分の記憶データＤＴＭ［］を有しており、インデ
ックスアドレスＩＡＤＤが入力されると、そのアドレス
に対応した４ウエイ分の記憶データＤＴＭ［］を出力又
は入力する。

【００５７】セレクタ部３４は、ヒット信号ＨＩＴ［］
に対応した選択信号ＤＳＬ［］により、データメモリ部
３３から読み出された記憶データＤＴＭ［］のうちでヒ
ットしたウエイの記憶データＤＴＭ［］を選択し、ＤＴ
Ｄ［］としてコントローラ３８に出力し、或いは、リプ
レース信号ＯＵＴ［］に対応した選択信号ＤＳＬ［］に
より、コントローラ３８から供給される記憶データＤＴ
Ｄ［］を置き換えるウエイを選択してデータメモリ部３
３に出力する。

【００５８】ＬＲＵメモリ部３５は、データメモリ部３
３内の各ウエイにアクセスした順序である履歴情報を各
エントリ毎に記憶しており、コントローラ３８から供給
されるインデックスアドレスＩＡＤＬが入力されると、
そのアドレスに対応した６ビットの履歴情報Ｗ［］を出
力する。キャッシュにヒットした場合、比較部３２から
ヒット信号ＨＩＴ［］が出力されるたびに、コントロー
ラ３８からヒット信号ＨＩＴ［］に対応した新規アクセ
スウエイ信号ＮＡＷ［］がＬＲＵメモリ部３５に供給さ
れる。これに基づいてＬＲＵメモリ部３５は、新たな履
歴情報としてＬＲＵメモリ内の記憶内容を更新する。こ
のときは、ＮＡＷ［ｎ］＝ＨＩＴ［ｎ］（ｎ＝０〜３）
である。

【００５９】一方、ミスヒットしたとき、ＬＲＵメモリ
部３５は、リプレース信号ＯＵＴ［］に対応した新規ア
クセスウエイ信号ＮＡＷ［］がコントローラ３８から供
給される。これに基づいてＬＲＵメモリ部３５は、ＬＲ
ＵメモリからインデックスアドレスＩＡＤＴに対応する
履歴情報を読み出し、最も過去にアクセスされたウエイ
の情報ＤＳＬ［］をセレクタ部３４に出力し、そのウエ
イのデータメモリ部３３に新たな記憶データＤＴＭ［］
を書き込む。このときは、ＮＡＷ［ｎ］＝ＯＵＴ［ｎ］
（ｎ＝０〜３）である。

【００６０】フリーズメモリ部３６は、各エントリ毎に
該当ウエイのフリーズの有無を記憶しており、コントロ
ーラ３８から供給されるインデックスアドレスＩＡＤＬ
が入力されると、そのアドレスに対応した３ビットのフ
リーズ情報ＦＲＺ［］を出力する。また、フリーズメモ
リ部３６は、コントローラ３８からフリーズ書込データ
（ＦＲＺライトデータ）ＦＷ［］とフリーズ書込許可信
号（ＦＲＺライトイネーブル信号）ＦＥ［］とが入力さ
れると、インデックスアドレスＩＡＤＬに対応した位置
にフリーズ情報ＦＲＺ［］を書き込む。３ビットのＦＲ
Ｚ［］は、４つのウエイのうち任意の３ウエイに対応さ
せることができる。以下の説明では、ウエイ０〜２をフ
リーズ可能なウエイとして、これらのフリーズ情報をＦ
ＲＺ［０］〜ＦＲＺ［２］に夫々対応させている。

【００６１】リプレース判定部３７は、ＬＲＵメモリ部
３５から出力される履歴情報Ｗ［］と、フリーズメモリ
部３６から出力されるフリーズ情報ＦＲＺ［］とに基づ
いて、どのウエイを新たな情報で置き換えるかを表すリ
プレース信号ＯＵＴ［］を出力する。リプレース信号Ｏ
ＵＴ［］は、各ウエイ０〜３に対応してＯＵＴ［０］〜
ＯＵＴ［３］がある。

【００６２】次に、キャッシュメモリ装置１１の全体的
な動作を図１を参照して説明する。

【００６３】［キャッシュ・ヒット動作］ＣＰＵ１０か
ら供給されたアドレス信号ＡＤは、一旦、コントローラ
３８に保持される。アドレス信号ＡＤのうち中位６ビッ
トのインデックスアドレスＩＡＤＤ及びＩＡＤＴが夫
々、データメモリ部３３及びタグメモリ部３１に供給さ
れる。この場合、インデックスアドレスＩＡＤＤとＩＡ
ＤＴとは同一の値である。このインデックスアドレスＩ
ＡＤＴに対応するタグメモリ部３１の内容が各ウエイ０
〜３から読み出され、比較部３２内の４つの比較回路に
夫々入力される。これと同時に、インデックスアドレス
ＩＡＤＤに対応する４ウエイ分の記憶データＤＴＭ［］
がセレクタ部３４に読み出される。

【００６４】一方、コントローラ３８から出力されたア
ドレス信号ＡＤＴのうち、タグアドレスＴＡＤは、比較
部３２のもう一方の入力端子に入力され、タグメモリ３
１から読み出されたタグアドレスＴＡＭ［］と比較され
る。比較部３２は、４ウエイのうちいずれか１つのウエ
イが一致したことを示す信号ＨＩＴ［］＝“１”を出力
する。その他のウエイに対応するヒット信号ＨＩＴ［］
は“０”（ミスヒット）となる。

【００６５】コントローラ３８は、上記ＨＩＴ［］に基
づいて選択信号ＤＳＬ［］と新規アクセスウエイ信号Ｎ
ＡＷ［］とを生成し、選択信号ＤＳＬ［］をセレクタ部
３４に、新規アクセスウエイ信号ＮＡＷ［］をＬＲＵメ
モリ部３５に夫々供給する。セレクタ部３４は、選択信
号ＤＳＬ［］に対応するウエイの記憶データＤＴＭ［］
を選択し、ＣＰＵ１０に対して出力する。

【００６６】その後、ＬＲＵメモリ部３５は、ヒット信
号ＨＩＴ［］に対応する新規アクセスウエイ信号ＮＡＷ
［］に基づいて、ヒットしたウエイのアクセスが最近さ
れたかのように履歴情報を書き換える。このとき、ＮＡ
Ｗ［］＝ＨＩＴ［］である。

【００６７】［キャッシュ・ミスヒット動作］次に、ミ
スヒットした場合の動作を説明する。比較処理まではヒ
ット時と同じである。

【００６８】比較部３２が、４ウエイのうちいずれのウ
エイも一致しなかったことを示す信号ＨＩＴ［０］〜Ｈ
ＩＴ［３］＝“０”を出力すると、コントローラ３８は
保持していたアドレス信号ＢＡＤをＢＣＵ１２に送り、
ＢＣＵ１２はそのアドレスＢＡＤに対応する記憶データ
ＢＤＴを主記憶装置１４から読み出す。

【００６９】コントローラ３８は、記憶データＢＤＴの
読出しと同時に、アドレス信号ＢＡＤに対応したインデ
ックスアドレスＩＡＤＬをＬＲＵメモリ部３５とフリー
ズメモリ部３６とに出力する。これに応答して、ＬＲＵ
メモリ部３５が履歴情報Ｗ［］を、フリーズメモリ部３
６がフリーズ情報ＦＲＺ［］をリプレース判定部３７に
夫々出力する。リプレース判定部３７は、履歴情報
Ｗ［］とフリーズ情報ＦＲＺ［］とに基づいてリプレー
ス信号ＯＵＴ［］を算出し、コントローラ３８に出力す
る。これにより、コントローラ３８は、リプレース信号
ＯＵＴ［］に対応した選択信号ＤＳＬ［］をセレクタ部
３４に供給する。

【００７０】ＢＣＵ１２を介して読み出された記憶デー
タＢＤＴは、コントローラ３８に入力され、ＣＰＵ１０
に対して出力される。また、コントローラ３８は、アド
レス信号ＢＡＤに対応するインデックスアドレスＩＡＤ
Ｄをデータメモリ部３３に供給するとともに、記憶デー
タＢＤＴをＤＴＤとしてセレクタ部３４に供給する。こ
のとき、コントローラ３８は、タグメモリ部３１に含ま
れるダーティビット情報ＤＲＴＯ［］を確認し、データ
メモリ部３３の記憶内容が主記憶装置１４の記憶内容と
異なるときには、データメモリ部３３の記憶内容を主記
憶装置１４に書き戻す。その後、セレクタ部３４が、デ
ータメモリ部３３内の選択信号ＤＳＬ［］で指定された
ウエイに記憶データＤＴＭ［］（＝ＤＴＤ）を出力す
る。データメモリ部３３は、インデックスアドレスＩＡ
ＤＤで指定された位置に記憶データＤＴＭ［］を記憶す
る。

【００７１】次いで、コントローラ３８は、書き換えた
ウエイの情報である新規アクセスウエイ信号ＮＡＷ［］
をＬＲＵメモリ部３５に出力する。ＬＲＵメモリ部３５
は、ＮＡＷ［］に基づいて、書き換えたウエイのアクセ
スが最近されたかのように履歴情報を書き換える。ここ
では、ＮＡＷ［ｎ］＝ＯＵＴ［ｎ］（ｎ＝０〜３）であ
る。

【００７２】以上は、キャッシュメモリ装置１１から記
憶データを読み出す場合を説明したが、書き込む場合
も、ほぼ同様に行われる。

【００７３】次に、ＬＲＵメモリ部３５の基礎技術につ
いて詳細に説明する。まず、ＬＲＵメモリが記憶してい
る履歴情報について説明する。図２は、Ｎウエイ分のア
クセス履歴を示す模式図であり、（a）はＮ＝２の場
合、（b）はＮ＝３の場合、（c）はＮ＝４の場合、
（d）はＮ＝５の場合を夫々示す。各図において、矢印
の基点側に位置するウエイが矢印の終端側に位置するウ
エイよりも最近にアクセスされたとき、ＬＲＵメモリに
“０”を記憶し、アクセスの順序関係が逆の場合には
“１”を記憶する。

【００７４】図２（a）における２ウエイでは、ＬＲＵ
メモリは、１ビットの履歴情報×エントリ数のメモリで
構成される。例えば、履歴情報W［0,1］に“０”が記憶
されているとき、ＬＲＵメモリ部３５は、ウエイ１がウ
エイ０よりも最新アクセスされたと判定し、逆に、履歴
情報W［0,1］に“１”が記憶されているとき、ウエイ０
がウエイ１よりも最新アクセスされたと判定する。

【００７５】また、履歴情報W［0,1］に“０”が記憶さ
れているときに、ウエイ０がヒットすると、履歴情報W
［0,1］は“１”に書き換えられ、ウエイ１がヒットす
ると、履歴情報W［0,1］は“０”のままである。逆に、
履歴情報W［0,1］に“１”が記憶されているときに、ウ
エイ１がヒットすると、履歴情報W［0,1］は“０”に書
き換えられ、ウエイ０がヒットすると、履歴情報W［0,
1］は“１”のままである。

【００７６】図２（b）における３ウエイでは、ＬＲＵ
メモリは、３ビットの履歴情報W［0,1］、W［0,2］、W
［1,2］を記憶している。例えば、各ウエイが「２←１
←０」の順にアクセスされたとき、ＬＲＵメモリは、履
歴情報（W［0,1］、W［0,2］、W［1,2］）として、
（０，０，０）を記憶している。即ち、ウエイ０よりも
ウエイ１の方が最近アクセスされているのでW［0,1］は
“０”であり、ウエイ０よりもウエイ２の方が最近アク
セスされているのでW［0,2］は“０”であり、ウエイ１
よりもウエイ２の方が最近アクセスされているのでW
［1,2］は“０”である。

【００７７】この状態でウエイ１がヒットすると、アク
セス履歴は「１←２←０」となり、履歴情報（W［0,
1］、W［0,2］、W［1,2］）は、（０，０，１）に書き
換えられる。即ち、ウエイ２よりウエイ１の方が最近ア
クセスされたことになるのでW［1,2］は“１”になる。
なお、３ウエイのＬＲＵメモリの容量は、３ビットの履
歴情報×エントリ数である。

【００７８】図２（c）における４ウエイ・セットアソ
シエイティブ・キャッシュのＬＲＵ方式では、ＬＲＵメ
モリ部３５内のＬＲＵメモリは、図３に示すように、６
ビットの履歴情報W［0,1］、W［0,2］、W［0,3］、W
［1,2］、W［1,3］、W［2,3］でアクセス履歴を記憶し
ている。図３は、４ウエイの全てのアクセス順序と履歴
情報の関係を、ヒットしたウエイを基準に示す履歴情報
図である。

【００７９】例えば、各ウエイが「２←１←３←０」の
順にアクセスされたとき、ＬＲＵメモリは、履歴情報
（W［0,1］、W［0,2］、W［0,3］、W［1,2］、W［1,
3］、W［2,3］）として、（０，０，０，０，１，１）
を記憶している。この状態でウエイ１がヒットすると、
アクセス履歴は「１←２←３←０」となり、履歴情報
（W［0,1］、W［0,2］、W［0,3］、W［1,2］、W［1,
3］、W［2,3］）は、（０，０，０，１，１，１）に書
き換えられる。なお、４ウエイのＬＲＵメモリの容量
は、６ビットの履歴情報×エントリ数である。図２
（d）における５ウエイも、同様にして１０ビットの履
歴情報で記憶している。

【００８０】図２（a）〜（d）の各場合において履歴情
報として夫々必要なビット数は、ウエイ数をＮとしたと
き、次式

【数３】 で表され、Ｎ＝２のときに１ビットとなり、Ｎ＝３のと
きに１＋２＝３ビットとなり、Ｎ＝４のときに１＋２＋
３＝６ビットとなり、Ｎ＝５のときに１＋２＋３＋４＝
１０ビットとなる。

【００８１】図５は、図１に示したタグメモリ部３１と
比較部３２との詳細な構成を示すブロック図である。タ
グメモリ部３１は、ＴＡＧアドレスデコーダ６１、ＴＡ
Ｇ書込み制御回路６２、及び、４ウエイ分のタグメモリ
３１ａ〜３１ｄで構成され、比較部３２は、４つの比較
回路３２ａ〜３２ｄで構成される。

【００８２】タグメモリ３１ａ〜３１ｄは、各ウエイの
各エントリに対応するタグアドレスＴＡＤと、主記憶装
置１４とデータメモリ部３３との記憶内容が一致してい
るか否かを示すダーティビットＤＲＴとを記憶してい
る。タグメモリ３１ａ〜３１ｄは、ウエイ数×エントリ
数×（アドレス線数＋１ビット）分の記憶容量を有し、
本実施形態例では、４ウエイ×６４エントリ×（１４ビ
ット＋１ビット）＝３８４０ビットの記憶容量のＳＲＡ
Ｍ（Static Random Access Memory）で構成される。

【００８３】ＴＡＧアドレスデコーダ６１は、コントロ
ーラ３８（図１）から供給されるアドレス信号ＡＤＴの
中位６ビットであるインデックスアドレスＩＡＤＴが入
力され、これをデコードしてタグメモリ３１ａ〜３１ｄ
のワード線（エントリに相当）の１つを活性化する。タ
グメモリ３１ａ〜３１ｄは、選択されたエントリのＴＡ
Ｇ情報ＴＡＭ［０］〜ＴＡＭ［３］を比較部３２に出力
するとともに、ダーティビットＤＲＴＯ［］をコントロ
ーラ３８に出力する。

【００８４】ＴＡＧ書込制御回路６２は、コントローラ
３８からインデックスアドレスＩＡＤＴ、選択信号ＤＳ
Ｌ［］、及び、ダーティビット書込み情報ＤＲＴＩ［］
が入力される。ミスヒットしたときに、ＴＡＧ書込み制
御回路６２は、選択信号ＤＳＬ［］で指定されるウエイ
のインデックスアドレスＩＡＤＴで指定されるエントリ
に、新たなタグアドレスＴＡＤを書き込むとともに、ダ
ーティビットＤＲＴに“０”を書き込む。ヒットしたと
きには、ＴＡＧ書込み制御回路６２は、タグアドレスＴ
ＡＤはもとのままで、ダーティビットＤＲＴに“１”を
書き込む。

【００８５】タグメモリ３１ａ〜３１ｄは、コントロー
ラ３８（図１）が供給するアドレス信号ＡＤＴの中位６
ビットのインデックスアドレスＩＡＤＴで指定されるタ
グアドレスＴＡＭ［０］〜ＴＡＭ［３］を比較回路３２
ａ〜３２ｄに夫々出力し、ＴＡＧ書込み制御回路６２か
ら供給されるタグアドレスＴＡＤを記憶する。同様に、
ダーティビットＤＲＴを読み書きする。読み出されたダ
ーティビットＤＲＴは、ダーティビット読出情報ＤＲＴ
Ｏ［］として上記のようにコントローラ３８に出力され
る。

【００８６】コントローラ３８は、読み出したダーティ
ビット読出情報ＤＲＴＯ［］を確認し、ＤＲＴＯ［］が
“１”であれば、データメモリ部３３の内容を更新する
前に、データメモリ部３３(図１)の記憶データＤＴＤを
主記憶装置１４にコピーバックする。ＤＲＴＯ［］が
“０”であれば、コントローラ３８は新たな記憶データ
ＤＴＤでデータメモリ部３３を上書きする。コントロー
ラ３８は更に、上記機能に加え、ＣＰＵ１０が出力する
アドレス信号ＡＤＴを保持して、アドレスデータの上位
ビットであるタグアドレスＴＡＤと、中位ビットである
インデックスアドレスＩＡＤと、下位ビットであるバイ
トアドレス（ワードアドレス）とを出力する。

【００８７】図６は、図１に示したデータメモリ部３３
の詳細な構成を示すブロック図である。データメモリ部
３３は、ＤＭ(データメモリ)アドレスデコーダ６４と、
４ウエイ分のデータメモリ３３ａ〜３３ｄとで構成さ
れ、タグメモリ３１に記憶されたタグアドレスＴＡＤ
と、インデックスアドレスＩＡＤに対応する主記憶装置
１４の記憶データＤＴとを記憶している。

【００８８】データメモリ３３ａ〜３３ｄは、タグメモ
リ３１ａ〜３１ｄに記憶されたタグアドレスＴＡＤとイ
ンデックスアドレスＩＡＤＤとで指定される主記憶装置
１４の記憶データＤＴＤを記憶している。このインデッ
クスアドレスＩＡＤＤは、前述のインデックスアドレス
ＩＡＤＬと、アクセスのタイミングの点で異なる。デー
タメモリ３３ａ〜３３ｄは、ウエイ数×エントリ数×バ
イト数分の記憶容量を有し、本実施形態例では、４ウエ
イ×６４エントリ×４バイト≒１ｋＢの記憶容量のＳＲ
ＡＭで構成される。

【００８９】ＤＭアドレスデコーダ６４は、コントロー
ラ３８から供給されるアドレス信号の中位６ビットであ
るインデックスアドレスＩＡＤＤが入力され、これをデ
コードしてデータメモリ３３ａ〜３３ｄのワード線（エ
ントリに相当）の１つを活性化する。データメモリ３３
ａ〜３３ｄは選択されたエントリの記憶データＤＴＭ
［０］〜ＤＴＭ［３］をセレクタ部３４に出力する。

【００９０】セレクタ部３４は、インデックスアドレス
で指定される位置のデータメモリ部３３から読み出した
４ウエイ分の記憶データＤＴＭ［］のうち、比較回路３
２ａ〜３２ｄで一致が検出されたウエイに対応する記憶
データＤＴＭ［］を１つ選択し、記憶データＤＴＤとし
てコントローラ３８に出力する。ミスヒットしてデータ
メモリ部３３の内容を新しい記憶データに書き換えると
きも、同様に書き込み位置を選択して、主記憶装置１４
から読み出した記憶データＤＴＤを書き込む。

【００９１】つまり、セレクタ部３４は、データメモリ
３３ａ〜３３ｄから記憶データＤＴＭ［０］〜ＤＴＭ
［３］が入力され、コントローラ３８から選択信号ＤＳ
Ｌ［］が入力された際にヒットすると、選択信号ＤＳＬ
［］で指定されるウエイの記憶データＤＴＤを１つ選択
してコントローラ３８に出力する。ミスヒットしたとき
には、セレクタ部３４は、主記憶装置１４から読み込ん
だ記憶データＢＤＴを、選択信号ＤＳＬ［］で指定され
るウエイのインデックスアドレスＩＡＤＤで指定される
エントリに、新たな記憶データＤＴＭ［］として書き込
む。

【００９２】コントローラ３８はセレクタ６５を内蔵し
ている。セレクタ６５は、ヒット信号ＨＩＴ［］又はリ
プレース信号ＯＵＴ［］のいずれか一方を選択し、選択
信号ＤＳＬ［］としてセレクタ部３４に出力する。ヒッ
トしたときは、ＤＳＬ［ｎ］＝ＨＩＴ［ｎ］（ｎ＝０〜
３）であり、ミスヒットしたときは、ＤＳＬ［ｎ］＝Ｏ
ＵＴ［ｎ］（ｎ＝０〜３）である。

【００９３】図７は、図１に示したＬＲＵメモリ部３５
の詳細なブロック図である。ＬＲＵメモリ部３５は、Ｌ
ＲＵメモリ１５、ＬＲＵ書込データ生成回路１６、ＬＲ
Ｕアドレスデコーダ６６、及びＬＲＵ書込み制御回路６
７で構成されている。

【００９４】ＬＲＵメモリ１５は、各エントリ毎に、キ
ャッシュメモリの各ウエイのアクセスした順序を６ビッ
トの履歴情報Ｗ［］で記憶している。各ウエイのアクセ
ス順序と履歴情報Ｗ［］との関係は、図３及び図４に示
す通りである。図４は、図３のアクセス履歴の表示順を
並べ換えて、最も過去にアクセスされたウエイがまとま
るようにしたものである。

【００９５】図７に示すように、ＬＲＵメモリ１５は、
エントリ数×履歴情報数分の記憶容量を有しており、本
実施形態例では、６４エントリ数×６ビット＝３８４ビ
ットの記憶容量のＳＲＡＭで構成される。

【００９６】ＬＲＵアドレスデコーダ６６は、コントロ
ーラ３８から供給されるアドレス信号の中位６ビットで
あるインデックスアドレスＩＡＤＬが入力され、これを
デコードしてＬＲＵメモリ１５のワード線（エントリに
相当）の１つを活性化する。ＬＲＵメモリ１５は、選択
されたエントリの履歴情報Ｗ［０，１］〜Ｗ［２，３］
をリプレース判定部３７に出力する。

【００９７】コントローラ３８内のセレクタ６８は、ヒ
ット信号ＨＩＴ［］又はリプレース信号ＯＵＴ［］のい
ずれか一方を選択し、新規アクセスウエイ情報ＮＡ
Ｗ［］としてＬＲＵ書込データ生成回路１６に出力す
る。ヒットしたときは、ＮＡＷ［ｎ］＝ＨＩＴ［ｎ］
（ｎ＝０〜３）であり、ミスヒットしたときは、ＮＡＷ
［ｎ］＝ＯＵＴ［ｎ］（ｎ＝０〜３）である。

【００９８】ＬＲＵ書込みデータ生成回路１６は、新規
アクセスウエイ情報ＮＡＷ［］に基づいて、ＬＲＵメモ
リ１５の内容を更新するために、６ビットのＬＲＵライ
トデータＬＷ［］と、ＬＲＵライトイネーブル信号ＬＥ
［］とを生成し、ＬＲＵ書込み制御回路６７に出力し
て、ＬＲＵメモリ１５への書込みを制御する。

【００９９】いま、ＬＲＵメモリ１５に対するＬＲＵラ
イトイネーブル信号をＬＥ［Ａ，Ｂ］と表記し、ＬＲＵ
ライトデータをＬＷ［Ａ，Ｂ］と表記することにする。
ウエイＬ（Ｌは０≦Ｌ≦３の整数）がヒットした場合、
ＬＲＵライトデータは、ＬＷ［Ａ，Ｌ］＝０、ＬＷ
［Ｌ，Ｂ］＝１（但しＡ＜Ｌ＜Ｂ）として定義し、この
ときＬＲＵライトイネーブル信号を、ＬＥ［Ａ，Ｌ］＝
ＬＥ［Ｌ，Ｂ］＝１として定義する。ＬＥ［Ａ，Ｂ］及
びＬＷ［Ａ，Ｂ］におけるＡ，Ｂは夫々にウエイを示し
ている。

【０１００】ＬＲＵデコード論理では、「任意の２つの
ウエイＡ，Ｂのうち、どちらが最後に使用されたか」を
全ウエイの組み合わせに対応して保持させる必要があ
る。一般に、Ｎウエイの場合には、N（N-1）/2ビットの
情報で全ウエイのアクセス順を表現できることが知られ
ている。このアクセス順は、ＬＲＵメモリ部３５内のＬ
ＲＵメモリ１５に記憶されており、アクセス順を表す６
ビットの履歴情報W［0,1］〜W［2,3］として保持されて
いる。

【０１０１】この履歴情報Ｗ［］は、キャッシュメモリ
がアクセスされる毎に更新され、常に最新の履歴情報に
書き換えられる。キャッシュにヒットしたときには、履
歴情報は、ヒットしたウエイが一番最近にアクセスされ
た状態となるように書き換えられ、ミスヒットしたとき
には、新しいデータに置き換えられたウエイが一番最近
にアクセスされた状態となるように書き換えられる。但
し、最近ヒットしたデータに再ヒットしたときには書き
換えなくても良い。

【０１０２】履歴情報を書き換えるとき、ヒット又は置
き換えられたウエイの情報がＬＲＵ書込みデータ生成回
路１６に入力されると、ＬＲＵ書込みデータ生成回路１
６は、表１に示すように、ヒットしたウエイに対応する
ＬＲＵライトデータＬＷ［Ａ，Ｂ］を生成し、ＬＲＵ書
込み制御回路６７を介してＬＲＵメモリ１５に出力す
る。

【０１０３】

【表１】

【０１０４】ＬＲＵ書込み制御回路１６は、６ビットの
ＬＲＵライトデータＬＷ［Ａ，Ｂ］をすべて書き込むわ
けではなく、所定の３ビットを書き換えるようにしてい
る。表２に示すＬＲＵライトイネーブル信号ＬＥ［Ａ，
Ｂ］によって、どのビットを書き換えるかを指定する。
なお、ＬＥ［Ａ，Ｂ］に対応するビット値の“０”は書
込みをマスクすることを意味し、“１”は書込みを実行
することを意味する。つまり、ＬＲＵ書込み制御回路１
６は、ＬＲＵライトイネーブル信号ＬＥ［Ａ，Ｂ］が
“１”であるＬＲＵライトデータＬＷ［Ａ，Ｂ］をＬＲ
Ｕメモリ１５に書き込む。

【０１０５】

【表２】

【０１０６】このように、ウエイＬがヒットし又は書き
換えられると、ＬＲＵ書込みデータ生成回路１６は、表
１と表２とに従ってＬＷ［Ａ，Ｂ］とＬＥ［Ａ，Ｂ］と
を生成し、ＬＲＵ書込み制御回路６７は、ＬＥ［Ａ，
Ｂ］が“１”となっている位置に対応するＬＲＵメモリ
１５の履歴情報Ｗ［Ａ，Ｂ］のビット位置に、ＬＷ
［Ａ，Ｂ］のビット値を書き込む。

【０１０７】例えば、ウエイ１がヒットした場合には、
ＬＲＵライトイネーブル信号LE［0,1］、LE［1,2］、LE
［1,3］が“１”であるので、ＬＲＵ書込み制御回路６
７は履歴情報W［0,1］、W［1,2］、W［1,3］にＬＲＵラ
イトデータ（LW［0,1］、LW［1,2］、LW［1,3］）とし
て（０，１，１）を書き込む。この結果、図３の破線で
囲んだ領域に示すように、ウエイ１がヒットする前の状
態がどのような履歴であっても、履歴情報W［0,1］、W
［0,2］、W［0,3］、W［1,2］、W［1,3］、W［2,3］
は、（０，ｄ，ｄ，１，１，ｄ）となる。ここで、ｄは
“don't care”を意味し、更新する前のビット値が保持
される。

【０１０８】図８は、図１に示したフリーズメモリ部３
６の詳細なブロック図を示す。フリーズメモリ部３６
は、フリーズメモリ２０と、ＦＲＺアドレスデコーダ６
９と、ＦＲＺ書込み制御回路７０とで構成される。

【０１０９】フリーズメモリ２０は、各エントリ毎に書
き換え禁止にするウエイの情報を３ビットのフリーズ情
報ＦＲＺ［］で記憶している。ウエイ０〜２のフリーズ
情報は夫々ＦＲＺ［０］〜ＦＲＺ［２］に対応してい
る。フリーズ情報ＦＲＺ［ｎ］が“１”であるとき、そ
のウエイｎは書き換えが禁止されていることを意味し、
“０”であるとき、そのウエイｎは新規の記憶データで
書き換えが可能であることを意味する。

【０１１０】フリーズメモリ２０は、（ウエイ数−１）
×エントリ数分の記憶容量を有し、本実施形態例では、
３ウエイ×６４エントリ＝１９２ビットの記憶容量のＳ
ＲＡＭ（Static Random Access Memory）で構成され
る。この記憶容量は、フリーズする領域に応じて適宜変
更しても良い。例えば、４ウエイともフリーズするとき
には４×６４ビットが必要であるし、また、１×６４ビ
ットでも良い。

【０１１１】ＦＲＺアドレスデコーダ６９は、コントロ
ーラ３８から供給されるアドレス信号の中位６ビットで
あるインデックスアドレスＩＡＤＬが入力され、これを
デコードしてフリーズメモリ２０のワード線（エントリ
に相当）の１つを活性化する。フリーズメモリ２０は、
選択されたエントリのフリーズ情報ＦＲＺ［０］〜ＦＲ
Ｚ［２］をリプレース判定部３７に出力する。なお、Ｆ
ＲＺアドレスデコーダ６９は、ＬＲＵアドレスデコーダ
６６と共用してもよく、或いは、ＬＲＵメモリ１５とＦ
ＲＺメモリ２０とを共通のワード線で接続したＳＲＡＭ
で構成してもよい。

【０１１２】ＦＲＺ書込み制御回路７０は、コントロー
ラ３８から供給されるＦＲＺライトデータＦＷ［］とＦ
ＲＺライトイネーブル信号ＦＥ［］とに基づいて、フリ
ーズメモリ２０内のインデックスアドレスＩＡＤＬで指
定される位置にフリーズ情報を書き込む。

【０１１３】いま、フリーズメモリ２０に対するＦＲＺ
ライトイネーブル信号をＦＥ［Ａ］と表記し、ＦＲＺラ
イトデータをＦＷ［Ａ］と表記することにする。ウエイ
Ｋ（Ｋは０≦Ｋ≦２の整数）をフリーズする場合、コン
トローラ３８（図１）は、ＦＲＺライトデータＦＷ
［Ｋ］＝１とし、ＦＲＺライトイネーブル信号をＦＥ
［Ｋ］＝１、ＦＥ［Ａ］＝０（但し、Ａ≠Ｋ）としてＦ
ＲＺ書込み制御回路７０に出力する。ＦＥ［Ａ］及びＦ
Ｗ［Ａ］におけるＡはウエイを示している。

【０１１４】逆に、ウエイＫ（Ｋは０≦Ｋ≦２の整数）
のフリーズを解除する場合、コントローラ３８は、ＦＲ
ＺライトデータＦＷ［Ｋ］＝０、ＦＲＺライトイネーブ
ル信号ＦＥ［Ｋ］＝１をＦＲＺ書込み制御回路７０に出
力し、フリーズメモリ２０に書き込む。

【０１１５】図９は、フリーズ情報をフリーズメモリ２
０に書き込む手順を示す流れ図である。同図に示す手順
は、プログラム起動時に、主記憶装置１４の所定の領域
に記憶された記憶データを、フリーズＩ／Ｏ命令によっ
てキャッシュメモリ装置１１の所定のウエイにコピーし
てフリーズする方法である。

【０１１６】また、図１０は、主記憶装置１４のアドレ
ス空間の配置例を示す図である。アドレスＡＤＲ０〜
（ＡＤＲ４−１）はプログラム領域、ＡＤＲ４以上はデ
ータ領域とする。プログラム領域中のアドレスＡＤＲ１
とアドレスＡＤＲ２〜（ＡＤＲ３−１）の領域に、フリ
ーズしたいプログラムが記述されているとする。

【０１１７】データ領域中のアドレスＡＤＲ５〜（ＡＤ
Ｒ６−１）の領域は、ウエイ０にフリーズしたいプログ
ラムを転送するため、予め一時的にコピーしておくため
の作業領域である。同様に、アドレスＡＤＲ６〜（ＡＤ
Ｒ７−１）、ＡＤＲ７〜（ＡＤＲ８−１）領域は夫々、
ウエイ１及びウエイ２用のデータ転送作業領域である。

【０１１８】次に、図１、及び図８〜図１０を参照し
て、フリーズメモリ２０へのフリーズ情報の書込み手順
を説明する。ここでは、アドレスＡＤＲ２〜（ＡＤＲ３
−１）に存在するフリーズ対象プログラムをウエイ１に
転送する場合を例に挙げて説明する。

【０１１９】先ず、ステップＳ１１で、アドレスＡＤＲ
２〜（ＡＤＲ３−１）に存在するフリーズ対象プログラ
ムを、ウエイ１用データ転送作業領域ＡＤＲ６〜（ＡＤ
Ｒ７−１）にブロック・コピーする。これは、予め組み
込まれた標準のフリーズＩ／Ｏ命令によって、キャッシ
ュメモリ装置１１の所定のウエイにコピーするためであ
る。

【０１２０】ステップＳ１２で、ＣＰＵ１０は、フリー
ズＩ／Ｏ命令を実行し、フリーズ対象プログラムの開始
／終了アドレスＡＤＲ２／（ＡＤＲ３−１）、コピー先
のウエイ“１”をコントローラ３８に設定する。ここ
で、ＣＰＵ１０は、データ転送作業領域ＡＤＲ６〜（Ａ
ＤＲ７−１）のアドレス情報をコントローラ３８に別途
供給してもよく、或いは、ウエイと１対１に対応してい
てウエイの情報“１”に基づいて生成できれば改めて設
定しなくてもよい。

【０１２１】ステップＳ１３で、コントローラ３８は、
ＢＣＵ１２にアドレスＢＡＤを出力し、フリーズ対象の
記憶データＢＤＴを主記憶装置１４から読み込む。読出
しアドレスＢＡＤはアドレスＡＤＲ６から（ＡＤＲ７−
１）まで変化する。

【０１２２】ステップＳ１４で、コントローラ３８は、
データメモリ部３３にステップＳ１３の読出しアドレス
ＢＡＤに対応するインデックスアドレスＩＡＤＤを出力
し、セレクタ部３４に記憶データＢＤＴと選択信号ＤＳ
Ｌ［１］＝１とを出力することで、データメモリ部３３
のウエイ１に記憶データＢＤＴを記憶する。

【０１２３】ステップＳ１５で、コントローラ３８は、
ＬＲＵメモリ部３５とフリーズメモリ部３６とに、前記
読出しアドレスＢＡＤに対応するインデックスアドレス
ＩＡＤＬを出力し、ＬＲＵメモリ部３５に新規アクセス
ウエイ情報ＮＡＷ［１］＝１を出力する。コントローラ
３８は更に、フリーズメモリ部３６にＦＲＺライトデー
タＦＷ［１］＝１、ＦＲＺライトイネーブル信号ＦＥ
［１］＝１を出力することで、フリーズメモリ２０のア
ドレスＩＡＤＬにＦＲＺ［１］＝１を書き込み、ウエイ
１の該当アドレスをフリーズ状態に設定する。

【０１２４】ステップＳ１６で、コントローラ３８は、
アドレスＡＤＲをインクリメントする。ステップＳ１７
で、コントローラ３８は、アドレスＡＤＲが転送終了ア
ドレスＡＤＲ７未満であるかを判断し、ＡＤＲ７未満で
あればステップＳ１３〜Ｓ１６を繰り返し、ＡＤＲ７以
上であればフリーズ転送処理を終了する。

【０１２５】図１１は、フリーズ情報をフリーズメモリ
２０に書き込むための更に別の手順を示す流れ図であ
る。同図に示す手順は、プログラム実行中に、主記憶装
置１４の所定の領域に記憶された記憶データをフリーズ
設定命令によってキャッシュメモリ装置１１の所定のウ
エイにコピーしてフリーズする方法である。

【０１２６】次に、図１、図８、図１０及び図１１を参
照して、フリーズメモリ２０へのフリーズ情報の書込み
手順を説明する。ここでは、図１０のアドレスＡＤＲ１
に存在するフリーズ対象プログラムをウエイ２に取り込
み、フリーズ設定命令によってフリーズする例を説明す
る。

【０１２７】先ず、ステップＳ２１において、ＣＰＵ１
０（図１）は、主記憶装置１４の所定のアドレスＡＤＲ
１に存在するプログラムを１行読み込む命令（以下、ロ
ード命令とも呼ぶ）と、アドレスＡＤＲ１とをコントロ
ーラ３８に渡す。

【０１２８】ステップＳ２２では、コントローラ３８
が、アドレスＡＤＲ５に対応するインデックスアドレス
ＩＡＤＴをタグメモリ部３１に出力するとともに、タグ
アドレスＴＡＤを比較部３２に出力する。

【０１２９】ステップＳ２３において、コントローラ３
８は、比較部３２がヒット信号ＨＩＴ［］＝１（ヒッ
ト）を出力すればステップＳ３５の処理に進み、ＨＩＴ
［］＝０（ミスヒット）であればステップＳ２４の処理
に進む。

【０１３０】ステップＳ２４では、コントローラ３８
が、ＢＣＵ１２にＢＡＤ＝ＡＤＲ１を出力し、フリーズ
対象記憶データＢＤＴを主記憶装置１４から読み込む。

【０１３１】ステップＳ２５では、コントローラ３８
が、アドレスＡＤＲ１に対応するインデックスアドレス
ＩＡＤＬをフリーズメモリ部３６に出力し、フリーズ情
報ＦＲＺ［０］〜ＦＲＺ［２］を取得する。

【０１３２】ステップＳ２６では、コントローラ３８
が、フリーズ可能か否かを判断する。フリーズ情報ＦＲ
Ｚ［０］〜ＦＲＺ［２］のいずれか１つが“０”であれ
ば、フリーズ可能であるとしてステップＳ２７に進む。
フリーズ情報ＦＲＺ［０］〜ＦＲＺ［２］が全て“１”
であれば、フリーズ不可能として処理を終了する。

【０１３３】ステップＳ２７では、コントローラ３８
が、アドレスＡＤＲ１に対応するインデックスアドレス
ＩＡＤＬをＬＲＵメモリ部３５に出力し、リプレース信
号ＯＵＴ［０］〜ＯＵＴ［３］を取得する。

【０１３４】ステップＳ２８では、コントローラ３８
が、ＯＵＴ［０］〜ＯＵＴ［２］のいずれかが“１”で
あればステップＳ３０に進み、ＯＵＴ［３］が“１”で
あればステップＳ２９に進む。

【０１３５】ステップＳ２９では、コントローラ３８
が、ＦＲＺ［２］→ＦＲＺ［１］→ＦＲＺ［０］の順に
フリーズ情報を検証し、ＦＲＺ［Ｆ］が“０”でフリー
ズ対象となっていないウエイを探す。最初に検出したウ
エイ“Ｆ”をリプレース対象と決定し、ステップＳ３１
に進む。

【０１３６】ステップＳ３０では、“１”となったＯＵ
Ｔ［Ｆ］に対応するウエイ“Ｆ”をリプレース対象と決
定し、ステップＳ３１に進む。

【０１３７】ステップＳ３１では、コントローラ３８
が、アドレスＡＤＲ１に対応するインデックスアドレス
ＩＡＤＴをタグメモリ部３１に出力し、ダーティビット
読出情報ＤＲＴ０［Ｆ］を取得する。

【０１３８】ステップＳ３２では、コントローラ３８
が、ダーティビット読出情報ＤＲＴ０［Ｆ］が“１”か
否かを判断し、“１”であればステップＳ３３に進み、
“０”であればステップＳ３４に進む。

【０１３９】ステップＳ３３では、コントローラ３８
が、アドレスＡＤＲ１に対応するインデックスアドレス
ＩＡＤＤをデータメモリ部３３に出力し、リプレース対
象のウエイの記憶データＤＴＭ［Ｆ］を取得し、ＢＣＵ
１２に出力するとともに、アドレスＡＤＲ１に対応する
インデックスアドレスＩＡＤＴをタグメモリ部３３に出
力する。コントローラ３８は更に、リプレース対象のウ
エイのタグアドレスＴＡＭ［］を取得し、アドレス信号
ＢＡＤをＢＣＵ１２に出力し、データメモリ部３３の内
容を主記憶装置１４にコピーバックする。その後、タグ
メモリ部３１内の対応するダーティビットを“０”に書
き換える。

【０１４０】ステップＳ３４では、コントローラ３８
が、ステップＳ２４で読出したフリーズ対象記憶データ
ＢＤＴをリプレース対象のウエイＦのデータメモリ部３
３に書き込む。

【０１４１】ステップＳ３５では、ＣＰＵ１０がフリー
ズ設定命令を実行することにより、コントローラ３８
が、ＬＲＵメモリ部３５とフリーズメモリ部３６とにア
ドレスＡＤＲ１に対応するインデックスアドレスＩＡＤ
Ｌを出力し、ＬＲＵメモリ部３５に新規アクセスウエイ
情報ＮＡＷ［Ｆ］＝１を出力する。コントローラ３８は
更に、フリーズメモリ部３６にＦＲＺライトデータＦＷ
［Ｆ］＝１、ＦＲＺライトイネーブル信号ＦＥ［Ｆ］＝
１を出力することで、フリーズメモリ２０のアドレスＩ
ＡＤＬにＦＲＺ［Ｆ］＝１を書き込み、ウエイＦの該当
アドレスをフリーズ状態に設定する。

【０１４２】フリーズ情報をフリーズメモリ２０に書き
込む手順としては、図９に示す手順以外にプリセット方
式とオンデマンド方式などがある。プリセット方式は、
高速実行したい特定のプログラムや高速参照した特定の
数値データを、プログラムを起動する段階や特定のプロ
グラムを実行する直前に予めキャッシュメモリ装置１１
に取り込み、フリーズしておく方式である。具体的に
は、ＣＰＵが主記憶領域の所定のアドレスから記憶デー
タを読み出し、Ｉ／Ｏ命令で、キャッシュメモリ装置１
１のデータメモリと、タグメモリと、フリーズメモリと
に夫々直接書き込むことにより行われる。

【０１４３】オンデマンド方式は、高速実行したい特定
のプログラムや高速参照した特定の数値データをキャッ
シュメモリ装置１１に取り込み、プログラム実行中にこ
れをフリーズし、或いは、フリーズ解除する方式であ
る。具体的には、ＣＰＵが通常のロード命令により所定
のアドレスをアクセスすることで、主記憶領域の所定の
アドレスから記憶データが読み出され、キャッシュメモ
リ装置１１にキャッシュされると共に、ＣＰＵに渡され
る。ＣＰＵは、上記記憶データがキャッシュされたウエ
イ情報をキャッシュメモリ装置１１から読み出し、この
キャッシュされたデータのエントリアドレスと、ウエイ
に対応するフリーズメモリのビットとに、フリーズ状態
又はフリーズ解除状態のデータを書き込む。

【０１４４】図１２は、図１に示したリプレース判定部
３７の詳細なブロック図である。リプレース判定部３７
は、フリーズ制御回路２１と、ＬＲＵデコード回路２２
とで構成される。リプレース判定部３７のフリーズ制御
回路２１及びＬＲＵデコード回路２２は夫々論理回路で
構成される。なお、フリーズ制御回路２１及びＬＲＵデ
コード回路２２を夫々、ソフトウエアのプログラムで実
施できるように構成しても良い。この場合、オリジナル
のアクセス履歴は、例えばＬＲＵメモリ部３５に格納さ
れ、中間情報の生成のために用いられる。

【０１４５】フリーズ制御回路２１は、ＬＲＵメモリ部
３５から６ビットの履歴情報Ｗ［０，１］〜Ｗ［２，
３］と、３ビットのフリーズ情報ＦＲＺ［０］〜ＦＲＺ
［２］とが入力され、６ビットの中間情報Ｍ［０，１］
〜Ｍ［２，３］を出力する。

【０１４６】ＬＲＵデコード回路２２は、６ビットの中
間情報Ｍ［０，１］〜Ｍ［２，３］に基づいてリプレー
ス信号ＯＵＴ［０］〜ＯＵＴ［３］を出力する。

【０１４７】ここで、リプレース判定部３７の動作の概
要を説明する。まず、フリーズ情報ＦＲＺ［０］〜ＦＲ
Ｚ［２］が全て“０”で、フリーズ処理を行わない場合
のリプレース判定部３７の処理について説明する。この
とき、Ｍ［Ａ，Ｂ］＝Ｗ［Ａ，Ｂ］であるので、以下の
説明ではＷ［Ａ，Ｂ］を使って説明する。

【０１４８】ＬＲＵデコード回路２２は、ＬＲＵメモリ
部３５（図７）から読み出された、履歴情報W［0,1］〜
W［2,3］の全６ビットに基づいて、最も過去に使われた
ウエイを検出し、ウエイ０〜３に夫々対応するリプレー
ス信号ＯＵＴ［0］〜ＯＵＴ［3］を出力する。リプレー
ス信号ＯＵＴ［０］〜ＯＵＴ［３］の値のうちいずれか
１つのみが“１”となり、他の値は“０”となる。ビッ
ト値が“１”のウェイがリプレース対象となる。

【０１４９】図４に示したアクセス履歴表から判るよう
に、ウエイ０が最も過去にアクセスされていた場合（最
上段のグループを参照）には、履歴情報W［0,1］、W
［0,2］、W［0,3］が共に“０”である。ウエイ１が最
も過去にアクセスされていた場合（２段目のグループを
参照）には、履歴情報W［0,1］が“１”で、W［1,2］及
びW［1,3］が“０”である。また、ウエイ２が最も過去
にアクセスされていた場合（３段目のグループを参照）
には、履歴情報W［0,2］及びW［1,2］が“１”で、W
［2,3］が“０”である。ウエイ３が最も過去にアクセ
スされていた場合（最下段のグループを参照）には、履
歴情報W［0,3］及びW［1,3］、W［2,3］が共に“１”で
ある。

【０１５０】上記関係を式で表現すると次のようにな
る。即ち、ウエイＤに対応する出力値ＯＵＴ［Ｄ］（０
≦Ｄ≦３を満たす整数）は、次の各論理式(1)〜(4)によ
って定まる。 OUT［0］＝（!W［0,1］）×（!W［0,2］）×（!W［0,3］） ……(1) OUT［1］＝（ W［0,1］）×（!W［1,2］）×（!W［1,3］） ……(2) OUT［2］＝（ W［0,2］）×（ W［1,2］）×（!W［2,3］） ……(3) OUT［3］＝（ W［0,3］）×（ W［1,3］）×（ W［2,3］） ……(4)

【０１５１】本明細書において、例えば「！Ｗ」は
「Ｗ」の反転値（ＮＯＴ論理）を示す。つまり、先頭部
分に「！」を付した数又は符号の値は「！」を付さない
対応する数又は符号の反転値を示す。

【０１５２】例えば、図３に示すように、アクセス履歴
が「０←１←２←３」であるとき（同図「ウエイ０ヒッ
ト」内の最上段）、ウエイ２がヒットすると、アクセス
履歴は「２←０←１←３」になり（同図「ウエイ２ヒッ
ト」内の最上段）、履歴情報（Ｗ［0,1］、Ｗ［0,2］、
Ｗ［0,3］、Ｗ［1,2］、Ｗ［1,3］、Ｗ［2,3］）は、
（１，０，１，０，１，１）となる。この値を上記(1)
〜(4)に代入すると、リプレース信号ＯＵＴ［０］〜Ｏ
ＵＴ［３］は、 ＯＵＴ［０］ ＝ ！１×！０×！１ ＝ ０、 ＯＵＴ［１］ ＝ １×！０×！１ ＝ ０、 ＯＵＴ［２］ ＝ ０× ０×！１ ＝ ０、 ＯＵＴ［３］ ＝ １× １× １ ＝ １ となり、最も過去にアクセスされたウエイ３がリプレー
スされることになる。

【０１５３】次に、図１２を参照して、中間情報につい
て詳細に説明する。例えば、Ｎ＝４の場合に、フリーズ
制御前のウエイＡ及びウエイＢ間における参照の前後関
係を示す“０”又は“１”の中間情報をＭ［Ａ，Ｂ］と
表記し、ウエイＣ（０≦Ｃ≦Ｎ−２の整数）のフリーズ
情報（“０”又は“１”）をＦＲＺ［Ｃ］と表記し、ウ
エイＤ（０≦Ｄ≦Ｎの整数）に対する出力値であるリプ
レース信号をＯＵＴ［Ｄ］と表記する。

【０１５４】ここでは、フリーズメモリ２０（図８）
は、Ｎー１ウエイ、つまり３ウエイ分のフリーズ情報Ｆ
ＲＺ［０］、ＦＲＺ［１］及びＦＲＺ［２］のみを有す
る。これにより、例えば４ウエイの場合に、全てのウエ
イをフリーズするとキャッシュメモリ装置が機能できな
くなるような不都合を防止している。即ち、全ウエイを
フリーズすると、以降のリプレース処理が不可能になる
ので、少なくとも１つのウエイはリプレース可能にして
おく必要がある。従って、後述の場合分けが必要にな
る。

【０１５５】ＬＲＵメモリ１５（図５）に格納された各
履歴情報Ｗ［Ａ，Ｂ］は、任意に指定された２ウエイ
Ａ、Ｂのどちらが最近アクセスされたかという内容を保
持している。履歴情報Ｗ［Ａ，Ｂ］が“０”の場合、ウ
エイＡがウエイＢより前にアクセスされたことを表し、
“１”の場合、ウエイＡがウエイＢより後にアクセスさ
れたことを表す。

【０１５６】フリーズメモリ２０に格納された各ＦＲＺ
［Ｃ］のビット値であるフリーズ情報は、“１”のとき
「該当するウエイＣをフリーズする」ことを示し、
“０”のときには「該当するウエイＣをフリーズしな
い」ことを示す。

【０１５７】各履歴情報Ｗ［Ａ，Ｂ］に対応するビット
値“０”、“１”に対し、フリーズメモリ２０（図８）
からのフリーズ情報ＦＲＺ［Ｃ］に従ってフリーズ制御
回路２１（図１２）がフリーズ制御した結果である中間
情報をＭ［Ａ，Ｂ］と表記する。フリーズ制御回路２１
は、記憶された履歴情報Ｗ［Ａ，Ｂ］を修正することな
く、該履歴情報Ｗ［Ａ，Ｂ］とフリーズ情報ＦＲＺ
［Ｃ］とに基づいて演算を行い、フリーズ指定されたウ
エイＣがリプレース対象にならないように、履歴情報Ｗ
［Ａ，Ｂ］を中間情報Ｍ［Ａ，Ｂ］に変換する。

【０１５８】ここで、中間情報Ｍ［Ａ，Ｂ］を正論理で
表すと、 M［A,B］＝W［A,B］+FRZ［A］ （但し、0≦A＜B＝（N-1））…(5) M［A,B］＝（W［A,B］+FRZ［A］）×!FRZ［B］ （但し、0≦A＜B＜（N-1））…(6) となり、上記(5)、(6)式によって一意にフリーズ論理を
決定することができる。これにより、ウエイ数が４以上
に増加した場合でも対処することができる。上記(5)、
(6)式にＮ＝４の場合の具体値を夫々代入すると、 M［0,1］＝（W［0,1］＋FRZ［0］）×（!FRZ［1］） （B≠3） M［0,2］＝（W［0,2］＋FRZ［0］）×（!FRZ［2］） （B≠3） M［0,3］＝（W［0,3］＋FRZ［0］） （B＝3） M［1,2］＝（W［1,2］＋FRZ［1］）×（!FRZ［2］） （B≠3） M［1,3］＝（W［1,3］＋FRZ［1］） （B＝3） M［2,3］＝（W［2,3］＋FRZ［2］） （B＝3） となる。

【０１５９】ＬＲＵデコード回路２２（図１２）は、フ
リーズ制御回路２１からの各中間情報に基づいて、ＯＵ
Ｔ［０］〜ＯＵＴ［３］に夫々対応する“０”、“１”
をリプレース信号として出力する。リプレース信号とし
て“０”が出力された場合には「該当するウエイをリプ
レース対象とせずにフリーズする」ことを意味し、
“１”が出力された場合には「該当するウエイをリプレ
ース対象としフリーズしない」ことを意味する。

【０１６０】各ウエイＤにおけるＯＵＴ［Ｄ］に夫々対
応して出力されるリプレース信号ＯＵＴ［０］〜ＯＵＴ
［３］は、次の各論理式(7)〜(10)によって決定され
る。 OUT［0］＝!M［0,1］×!M［0,2］×!M［0,3］ ……(7) OUT［1］＝ M［0,1］×!M［1,2］×!M［1,3］ ……(8) OUT［2］＝ M［0,2］× M［1,2］×!M［2,3］ ……(9) OUT［3］＝ M［0,3］× M［1,3］× M［2,3］ ……(10)

【０１６１】ここで、所望のウエイをフリーズする際の
具体例を説明する。例えば、アクセス履歴が「３←１←
２←０」であるとき（図３の「ウエイ３ヒット」の上か
ら４段目）、ミスヒットが生じてキャッシュメモリが新
たな記憶データで書き換えられる場合を考える。フリー
ズ情報がないと、前述のように、最も過去にアクセスさ
れたウエイ０が新しい記憶データで書き換えられる。

【０１６２】いま、ウエイ０がフリーズ設定されている
とする。このとき、フリーズメモリ２０は、フリーズ制
御回路２１にフリーズ情報FRZ［0］＝１、FRZ［1］＝
０、FRZ［2］＝０を送信する。また、履歴情報（Ｗ［0,
1］、Ｗ［0,2］、Ｗ［0,3］、Ｗ［1,2］、Ｗ［1,3］、
Ｗ［2,3］）は、図３に示すように、（０，０，０，
１，０，０）となっている。これら具体値を夫々、ウエ
イＢによって、つまりＢが(N-1)であるか否かによって
上記(5)、(6)式の対応する方に代入すると、 M［0,1］＝（W［0,1］＋1）×!0＝1×1＝１ M［0,2］＝（W［0,2］＋1）×!0＝1×1＝１ M［0,3］＝（W［0,3］＋1） ＝１ M［1,2］＝（W［1,2］＋0）×!0＝1×1＝１ M［1,3］＝（W［1,3］＋0） ＝０ M［2,3］＝（W［2,3］＋0） ＝０ となる。これは、図３に示すように、アクセス履歴が
「０←３←１←２」（ウエイ０ヒット」の上から５段
目）に相当する。つまり、ＬＲＵメモリ１５にはウエイ
０が最も過去にアクセスされたことになっているが、中
間情報Ｍ［Ａ，Ｂ］では、ウエイ０が最も最近アクセス
されたかのように変換される。

【０１６３】ＬＲＵデコード回路２２は、上記結果に基
づき、上記式(7)〜(10)を用いてリプレース信号OUT
［0］〜OUT［3］を算出し、以下のように出力する。 OUT［0］＝!M［0,1］×!M［0,2］×!M［0,3］＝０ OUT［1］＝ M［0,1］×!M［1,2］×!M［1,3］＝０ OUT［2］＝ M［0,2］× M［1,2］×!M［2,3］＝１ OUT［3］＝ M［0,3］× M［1,3］× M［2,3］＝０ これらのリプレース信号の出力により、ウエイ０の次に
古くアクセスされたウエイ２がリプレースされるので、
フリーズされているウエイ０が書き換えられることはな
い。

【０１６４】次いで、所望のウエイをフリーズする際の
別の具体例を説明する。例えば、アクセス履歴が「３←
１←２←０」であるとき（図３の「ウエイ３ヒット」の
上から４段目）、ミスヒットが生じてキャッシュメモリ
が新たな記憶データで書き換えられる場合を考える。フ
リーズ情報がないと、前述したように、最も過去にアク
セスされたウエイ０が新しい記憶データで書き換えられ
ることになる。

【０１６５】いま、ウエイ０及びウエイ１がフリーズ設
定されているとする。このとき、フリーズメモリ２０
は、フリーズ制御回路２１にフリーズ情報FRZ［0］＝
１、FRZ［1］＝１、FRZ［2］＝０を送信する。また、履
歴情報（Ｗ［0,1］、Ｗ［0,2］、Ｗ［0,3］、Ｗ［1,
2］、Ｗ［1,3］、Ｗ［2,3］）は、図３に示すように、
（０，０，０，１，０，０）である。これら具体値を、
上記(5)、(6)式の対応する方に代入すると、 M［0,1］＝（W［0,1］＋1）×!1＝1×0＝0 M［0,2］＝（W［0,2］＋1）×!0＝1×1＝1 M［0,3］＝（W［0,3］＋1） ＝1 M［1,2］＝（W［1,2］＋1）×!0＝1×1＝1 M［1,3］＝（W［1,3］＋1） ＝1 M［2,3］＝（W［2,3］＋0） ＝0 となる。

【０１６６】上記履歴情報（０，１，１，１，１，０）
は、図３に示すように、アクセス履歴が「１←０←３←
２」に相当する。つまり、ＬＲＵメモリ１５には「３←
１←２←０」の順にアクセスされたことになっている
が、中間情報Ｍ［Ａ，Ｂ］では、ウエイ１とウエイ０と
が最近アクセスされたかのように変換されることにな
る。

【０１６７】ＬＲＵデコード回路２２は、上記結果に基
づき、上記式(7)〜(10)を用いてリプレース信号OUT
［0］〜OUT［3］を算出し、以下のように出力する。 OUT［0］＝!M［0,1］×!M［0,2］×!M［0,3］＝０ OUT［1］＝ M［0,1］×!M［1,2］×!M［1,3］＝０ OUT［2］＝ M［0,2］× M［1,2］×!M［2,3］＝１ OUT［3］＝ M［0,3］× M［1,3］× M［2,3］＝０ これらにより、実際にはウエイ０の次にアクセス履歴が
古いウエイ２がリプレースされることになるので、フリ
ーズされているウエイ０とウエイ１が書き換えられるこ
とはない。

【０１６８】以上、本実施形態例では、４ウエイの場合
を中心に説明したが、Ｎが２以上の整数であるＮウエイ
・セット・アソシアティブ・キャッシュの場合には次の
ようになる。つまり、ＯＵＴ［X］の一般式は、Ｘ＝０
の場合、

【数４】 ０＜X＜Nー１の場合、

【数５】 X＝Nー１の場合、

【数６】 となる。ここで、記号Πは、関数Ｆ（Ｘ）に対して以下
のように定義される。

【数７】

【０１６９】式(11)〜(13)を具体的に記述すると次のよ
うになる。 OUT［0］＝!M［0,1］×!M［0,2］×……×!M［0,N-1］ OUT［1］＝ M［0,1］×!M［1,2］×……×!M［1,N-1］ OUT［2］＝ M［0,2］× M［1,2］×……×!M［0,N-1］ ・ ・ OUT［N-1］＝M［0,N-1］×M［1,N-1］×……×M［N-2,N
-1］

【０１７０】以上の演算を行うことで、いずれか１つの
リプレース信号ＯＵＴ［Ｒ］が“１”となり、そのウエ
イＲがリプレース対象のウエイと判定されることにな
る。

【０１７１】なお、本実施形態例では、正論理を用いて
説明したが、これに限らず負論理を用いることもでき
る。また、記憶された情報に基づいてＬＲＵ自身がＬＲ
Ｕ情報を得られれば良いので、アクセスした情報を必ず
しもＬＲＵ方式で記憶しなくても良い。

【０１７２】以上のように、本実施形態例では、ＬＲＵ
メモリ１５における格納状態を表す方法として、任意に
指定した２つのウエイ間の情報のみを保持する方式を利
用し、この方式にフリーズ論理を組み合わせた。従っ
て、極めて小規模な回路構成の追加でフリーズ論理を実
現することができる。

【０１７３】本実施形態例では、ユーザがフリーズアド
レス出力回路１９に対して設定を行うことにより所望の
ウエイをフリーズできるので、例えば、利用頻度は少な
いが、高速に処理しなければならないプログラムやデー
タをフリーズした状態で実行又は演算を行うことができ
る。このため、重要な処理プログラムの実行速度が低下
することがない。

【０１７４】また、従来は１ウエイのみをフリーズ対象
としていたが、本実施形態例では、Ｎウエイのうちの１
ウエイのみをリプレース対象として残しておくことによ
り、他のウエイを全てフリーズ対象とすることもでき
る。これにより、比較的サイズの大きいプログラムをフ
リーズすることが可能になり、従来に比してミスヒット
の確率が低減する。その場合、キャッシュの書き換え回
数が大幅に減少する。

【０１７５】本実施形態例では、ＬＲＵメモリ３３ａ〜
３３ｄには常に最新のアクセス履歴情報が保持されてお
り、データメモリ部３３のリプレースが必要になったと
きには、フリーズ情報とアクセス履歴情報とに基づいて
リプレース信号を演算によって求め、フリーズ対象を除
いたウエイで、一番過去にアクセスがあったウエイをリ
プレース対象のウエイとして出力する構成とした。この
ため、本願方式によれば、フリーズ機能を有しながら
も、ＬＲＵ方式の有効性を損なうことなくキャッシュメ
モリ装置を実現することができる。

【０１７６】また、フリーズメモリ２０は、フリーズ情
報を１エントリに（Ｎ−１）ビットで記憶しており、必
要なメモリ量が少ないので、フリーズメモリ２０をＲＡ
Ｍではなくレジスタから構成することも可能になる。フ
リーズメモリ２０のメモリ容量は、４ウエイの場合に３
ビット×エントリ数であるので、例えば、１ウエイに６
４個のエントリが存在する際には、１９２ビットのメモ
リ量があれば足りる。このため、フリーズを実行するた
めのロジックが極めて小規模で足りるので、必要な回路
構成を簡素化することができる。また、従来例のよう
に、フリーズ情報に基づいてＬＲＵメモリを書き換える
ことがないので、従来の書換えに要していた時間がなく
なり、キャッシュメモリ装置の負荷が軽減されるととも
に、キャッシュメモリ装置の応答時間が短縮できる。

【０１７７】本実施形態例では、フリーズ機能を使わな
い場合には、フリーズメモリ２０の記憶内容を全て
“０”にするだけで、従来と同じキャッシュメモリ装置
１１として機能させることができる。また、フリーズ動
作を終了したときには、それまでのアクセス履歴がフリ
ーズ情報で書き換えられることなくＬＲＵメモリ部３５
に記憶されているので、ＬＲＵ方式の機能を損なうこと
がない。このため、ミスヒットが生じた場合、最も過去
にアクセスされたウエイがリプレース対象になり、キャ
ッシュメモリのヒット確率が低減することがない。

【０１７８】本実施形態例におけるキャッシュメモリ装
置１１では、上記効果に加えて次のような効果をも奏す
る。例えば、１つのサブルーチンを１ウエイ相当のメモ
リに格納しようとしても、データ量が多くて格納できな
い場合がある。この場合、従来例では、１ウエイのみを
活用する構成であるため、ウエイを２つ跨ってデータ格
納することはできなかった。しかし、本実施形態例で
は、Ｎ−１の複数ウエイを活用することができるので、
比較的規模の大きいデータでも容易に格納することがで
きる。

【０１７９】以上、本発明をその好適な実施形態例に基
づいて説明したが、本発明のキャッシュメモリ装置及び
その制御方法は、上記実施形態例の構成にのみ限定され
るものではなく、上記実施形態例の構成から種々の修正
及び変更を施したキャッシュメモリ装置及びその制御方
法も、本発明の範囲に含まれる。

【０１８０】

【発明の効果】以上説明したように、本発明のキャッシ
ュメモリ装置及びその制御方法によると、簡素な回路構
成を備えながらも、キャッシュメモリのスループットを
低下させることなく２以上のウエイを対象に円滑なフリ
ーズ処理が実行でき、ニーズに対応したキャッシュメモ
リ機能を実現することができる。マイクロコンピュータ
の用途は拡大しており、低価格化が要求されている。し
かし、用途毎にマイクロコンピュータを開発していたの
では、低価格化は実現できない。本願発明のように、フ
リーズ機能付きのキャッシュメモリ装置を採用すること
で、同一構成のマイクロコンピュータで色々な用途に対
応することが可能になる。例えば、フリーズ機能なしの
キャッシュメモリ装置、フリーズ機能付きのキャッシュ
メモリ装置、或いは、キャッシュメモリ装置の一部を高
速読出し専用メモリ（ＲＯＭ）または高速ＲＡＭとして
利用したマイクロコンピュータ・システムなどに対応す
ることができる。従って、顧客の多様な要求に対して、
ハードウエアを設計変更することなく、ソフトの変更だ
けで応じることが可能になり、短期間で低価格のマイク
ロコンピュータを顧客に提供することが可能になる。

【０１８１】また、フリーズ情報に対応してアクセス履
歴情報を中間情報に変換した後にリプレース対象のウエ
イを算出することにより、既に設計済みのキャッシュメ
モリ装置の資産を継承しつつ、簡単な論理回路を付加す
るだけで、フリーズ機能付きのキャッシュメモリ装置が
実現できる。この場合、ＬＲＵの元データを破棄するこ
とがないので、フリーズ状態を解除したとき、それまで
のアクセス履歴に基づいた通常のＬＲＵ方式に即座に復
帰できる。

【０１８２】更に、Ｎウエイのアクセス順序を最近アク
セスされたウエイから順に並べたとき、フリーズ対象の
ウエイが１乃至Ｎ−１のいずれかのアクセス順序になる
ような中間情報を生成してからリプレース対象のウエイ
を算出すると、ＬＲＵの機能を損なうことなくリプレー
ス対象のウエイ算出することができる。

【０１８３】また、中間情報としてのＭ［Ａ，Ｂ］への
変換を、 M［A,B］＝ W［A,B］+FRZ［A］ M［A,B］＝（W［A,B］+FRZ［A］）×!FRZ［B］ に基づいて行うことにより、簡単な論理で、フリーズ対
象のウエイがリプレース対象のウエイにならないように
変換処理することができる。これにより、小規模な論理
回路を追加するだけでフリーズ機能付きのキャッシュメ
モリ装置を実現することができる。

【０１８４】更に、リプレース対象のウエイＸの算出
を、次式

【数８】 に基づいて行うことにより、中間情報を生成することに
よって、従来のリプレース対象ウエイの算出回路をその
まま利用することが可能になる。

【図面の簡単な説明】

【図１】本発明に係るキャッシュメモリ装置を備えたコ
ンピュータシステムの一実施形態例を示すブロック図で
ある。

【図２】Ｎウエイ分のアクセス履歴を示す模式図であ
り、（a）はＮ＝２の場合、（b）はＮ＝３の場合、
（c）はＮ＝４の場合、（d）はＮ＝５の場合を夫々示
す。

【図３】４ウエイの全てのアクセス順序と履歴情報との
関係を、ヒットしたウエイを基準に示した履歴情報図で
ある。

【図４】４ウエイの全てのアクセス順序と履歴情報との
関係を、最も古くにアクセスされたウエイを基準に示し
た履歴情報図である。

【図５】本実施形態例におけるタグメモリ部及びその周
辺の構成を示すブロック図である。

【図６】本実施形態例におけるデータメモリ部及びその
周辺の構成を示すブロック図である。

【図７】本実施形態例におけるＬＲＵメモリ部及びその
周辺の構成を示すブロック図である。

【図８】本実施形態例におけるフリーズメモリ部及びそ
の周辺の構成を示すブロック図である。

【図９】本実施形態例におけるフリーズＩ／Ｏ命令によ
るフリーズ設定手順を示す流れ図である。

【図１０】本実施形態例におけるフリーズ設定手順を説
明するための主記憶装置のアドレス配置例を示す図であ
る。

【図１１】本実施形態例におけるフリーズ設定命令によ
るフリーズ設定手順を示す流れ図である。

【図１２】本実施形態例におけるリプレース判定部及び
その周辺の構成を示すブロック図である。

【図１３】従来の半導体記憶装置に対応するキャッシュ
メモリ装置の構成を示すブロック図である。

【図１４】従来のＬＲＵパージ／フリーズ制御部のフリ
ーズ処理を示す流れ図である。

【図１５】従来の各記憶データの優先順位を考慮したパ
ージ／フリーズ制御の概要を示す図である。

【符号の説明】

１０：ＣＰＵ １１：キャッシュメモリ装置 １２：バスコントロールユニット（ＢＣＵ） １３：システムバス １４：主記憶装置 １５：ＬＲＵメモリ １６：ＬＲＵ書込みデータ生成回路 １９：フリーズアドレス出力回路 ２０：フリーズメモリ ２１：フリーズ制御回路 ２２：ＬＲＵデコード回路 ３１：タグメモリ部 ３１ａ〜３１ｄ：タグメモリ ３２：比較部 ３２ａ〜３２ｄ：比較回路 ３３：データメモリ部 ３３ａ〜３３ｄ：データメモリ ３４：セレクタ ３５：ＬＲＵメモリ部 ３６：フリーズメモリ部 ３７：リプレース判定部 ６１：ＴＡＧアドレスデコーダ ６２：ＴＡＧ書込み制御回路 ６４：ＤＭアドレスデコーダ ６５、６８：セレクタ ６６：ＬＲＵアドレスデコーダ ６７：ＬＲＵ書込み制御回路 ６９：ＦＲＺアドレスデコーダ ７０：ＦＲＺ書込み制御回路

Claims (9)

【特許請求の範囲】
1. 【請求項１】 ＬＲＵデコード方式を採用し、Ｎを２以
   上の整数としたＮウエイ・セット・アソシアティブ方式
   のキャッシュメモリ装置において、 キャッシュメモリの各ウエイのアクセス履歴情報を記憶
   するＬＲＵメモリと、 各ウエイのフリーズ情報を記憶するフリーズメモリと、 記憶されたアクセス履歴情報を修正することなく該アク
   セス履歴情報と前記フリーズ情報とに基づいて、特定の
   ウエイをフリーズするためのリプレース信号を生成する
   リプレース判定手段とを備えることを特徴とするキャッ
   シュメモリ装置。
2. 【請求項２】 前記リプレース判定手段が、前記フリー
   ズ情報と前記アクセス履歴情報とを取り込んで中間情報
   を生成するフリーズ制御回路と、 前記フリーズ制御回路からの前記中間情報に対応して前
   記リプレース信号を生成するＬＲＵデコード回路とを備
   えることを特徴とする請求項１に記載のキャッシュメモ
   リ装置。
3. 【請求項３】 前記フリーズ情報としてＮ−１ウエイに
   対応する記憶容量を備えることを特徴とする請求項１又
   は２に記載のキャッシュメモリ装置。
4. 【請求項４】 前記リプレース信号が、各ウエイに夫々
   対応して出力されるビット値から成ることを特徴とする
   請求項１乃至３の内の何れか１項に記載のキャッシュメ
   モリ装置。
5. 【請求項５】 ＬＲＵデコード方式を採用し、Ｎを２以
   上の整数としたＮウエイ・セット・アソシアティブ方式
   のキャッシュメモリ装置を制御する制御方法において、 キャッシュメモリの各ウエイのアクセス履歴情報を記憶
   し、 キャッシュメモリの各ウエイのフリーズ情報を記憶し、 記憶された前記アクセス履歴情報を修正することなく該
   アクセス履歴情報と前記フリーズ情報とに基づいてリプ
   レース対象のウエイを算出することを特徴とするキャッ
   シュメモリ装置の制御方法。
6. 【請求項６】 前記アクセス履歴情報と前記フリーズ情
   報とに基づいてリプレース対象のウエイを算出する際
   に、前記フリーズ情報に対応して前記アクセス履歴情報
   を中間情報に変換した後にリプレース対象のウエイを算
   出することを特徴とする請求項５に記載のキャッシュメ
   モリ装置の制御方法。
7. 【請求項７】 前記アクセス履歴情報と前記フリーズ情
   報とに基づいてリプレース対象のウエイを算出する際
   に、Ｎウエイのアクセス順序を最近アクセスされたウエ
   イから順に並べたとき、フリーズ対象のウエイが１乃至
   Ｎ−１のいずれかのアクセス順序になるような中間情報
   を生成した後にリプレース対象のウエイを算出すること
   を特徴とする請求項５に記載のキャッシュメモリ装置の
   制御方法。
8. 【請求項８】 ウエイＡに対するウエイＢのアクセス順
   序を表すアクセス履歴情報をＷ［Ａ，Ｂ］とし、ウエイ
   Ａ及びウエイＢのフリーズ情報を夫々ＦＲＺ［Ａ］及び
   ＦＲＺ［Ｂ］とするとき、前記中間情報としてのＭ
   ［Ａ，Ｂ］への変換が、 M［A,B］＝ W［A,B］+FRZ［A］ （但し、0≦A
   ＜B＝（N-1）） M［A,B］＝（W［A,B］+FRZ［A］）×!FRZ［B］ （但し、0≦A＜B＜（N-1）であり、!FRZ［］はFRZ［］
   の反転値を示す）に基づいて行われることを特徴とする
   請求項６又は７に記載のキャッシュメモリ装置の制御方
   法。
9. 【請求項９】 リプレース対象のウエイをＸとすると
   き、該ウエイＸの算出は、次式 【数１】 に基づいて行われることを特徴とする請求項５乃至８の
   内の何れか１項に記載のキャッシュメモリ装置の制御方
   法。