JPH05120139A - キヤツシユメモリ装置 - Google Patents

Abstract

(57)【要約】 【目的】本発明は情報処理装置のキャッシュメモリ装置
に関し、無効となったエントリを置換動作において優先
して選択し、かつ高速に置換するエントリを選択する方
法を提供することである。 【構成】インバリッド信号（１１）により、エントリ無
効化時に該エントリを最も以前に参照したエントリとす
る情報をＬＲＵ用メモリ（１０４）に書き込むＬＲＵ書
き込み制御回路（１１０）を特に具備する。 【効果】無効エントリは最も以前に参照したことを示す
情報がＬＲＵ用メモリに書き込まれているため、置換要
求が起きた時に必ず選択され、無効なデータが格納され
たエントリを優先して選択する制御回路を設けることな
く置換動作を高速に実行できる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、キャッシュメモリ装置
に係り、特に、情報処理装置のキャッシュメモリ装置に
格納したデータを高速に置換する制御方式に関する。

【０００２】

【従来の技術】大型計算機、マイクロプロセッサ等の計
算機システムの分野では、キャッシュメモリは小容量か
つ高速なメモリで構成され、大容量かつ低速な主記憶装
置にあるデータの一部を一時的に保持することで、計算
機システムの動作速度を向上させている。大容量の主記
憶装置は中央処理装置の速度に対し十分に速くはなく、
そのため小容量ではあるが高速なキャッシュメモリを中
央処理装置の近傍に置き、データの一部をキャッシュメ
モリに記憶することで、中央処理装置の速度を落さずに
動作させる方法がとられている。

【０００３】キャッシュメモリは複数のエントリを持つ
複数のウエイから構成されているが、例えばプロセッサ
からキャッシュへのリード・アクセスがミスとなった
時、主記憶装置からの読み出しデータはキャッシュ内の
空きエントリーに格納される。しかし、キャッシュが一
杯であり空きエントリーが無い場合は、例えば複数のエ
ントリーのいずれかひとつのエントリーのデータを主記
憶装置へ戻すことによってこのエントリーを空きエント
リーとした後、この空きエントリーに上述の主記憶装置
からの読み出しデータを格納すると言うエントリーの置
換が必要となる。主記憶装置からの読み出しデータを格
納するエントリーとして最も以前に参照されたデータを
格納したエントリーを選択すると言うエントリー置換の
方法、すなわちＬＲＵ(Least Recently Used)法が通常
行われ、キャッシュメモリの使用効率向上を図ってい
る。

【０００４】一方、特開平１−１２５６４１号公報に記
載のように、置換すべきエントリをＬＲＵ法により選択
するとともに、主記憶装置のデータとの一致性が取れな
くなった無効なデータを格納したキャッシュのエントリ
を優先して置換する制御回路を持つものが知られてい
る。

【０００５】

【発明が解決しようとする課題】ところで、キャッシュ
メモリが動作を開始した時点では全てのエントリが無効
である。一方、また複数のプロセッサと各プロセッサ毎
にキャッシュメモリとを持つプライベートキャッシュの
マルチプロセッサ方式の計算機システムにおいて、通常
動作時でも共有したデータの一致性を保つために無効な
エントリが生じる。従って、無効となったエントリを優
先して置換することで、使用頻度の高いエントリが置換
される可能性を低くし、性能を向上させることができ
る。

【０００６】一方、従来のキャッシュメモリは、前述の
ように無効なエントリを優先して置換する制御回路を持
っていたため、置換すべきエントリを高速に選択する点
について十分な配慮がなされておらず、書換えのあった
エントリが置換される際に主記憶装置に書き戻すコピー
バック動作を遅らせるという問題点があった。

【０００７】本発明は、置換するエントリを高速に選択
する方法を得ることを目的とし、置換エントリ選択時に
無効なエントリを優先すると共に複雑な制御を必要とし
ないキャッシュメモリ装置を提供することを目的とす
る。

【０００８】

【課題を解決するための手段】上記目的は、エントリー
に格納されたデータの有効または無効を示すバリッド信
号を出力するバリッド記憶手段と、ＬＲＵ信号を出力す
るＬＲＵ記憶手段と、外部からのエントリ無効化信号が
入力された時にこのエントリを最も以前に参照されたエ
ントリとしする如く対応する情報をＬＲＵ記憶手段に書
き込む制御手段を設けることにより達成される。

【０００９】

【作用】無効となったデータを格納しているエントリは
該当するＬＲＵ記憶手段に最も以前に参照されたことを
示す情報が書き込まれているため、置換要求が起きた時
点で優先的に置換されるように動作する。これは、無効
なエントリが複数ある場合でも不都合は生じず、最も最
近に無効となったエントリから置換される。

【００１０】本発明におけるキャッシュメモリ制御方式
は、無効なエントリを優先して選択する制御回路を持た
ないため、高速に置換ウエイ選択信号を出力することが
可能となり、主記憶装置へ書き戻すコピーバック動作を
高速にすることができる。一方、外部からのエントリ無
効化信号によるＬＲＵ記憶手段への書き込み動作は、エ
ントリが無効となった事を示すインバリッド信号をバリ
ッド記憶手段に書き込む動作と並行して行うことで速度
は低下しない。

【００１１】

【実施例】以下、本発明の実施例を図面を用いて詳細に
説明する。

【００１２】図１は、本発明に一実施例による４ウエイ
セットアソシアティブのキャッシュメモリ装置を示すブ
ロック図である。図１において、１０１は検索アドレス
に従って該当するエントリを選択するための行デコー
ダ、１０２は該データに対応しそのアドレスの一部を記
憶するタグメモリ、１０３は該データが有効か無効かを
記憶するバリッドメモリ、１０４は該エントリの置換情
報を保持するＬＲＵ用メモリ、１０５はデータを記憶す
るデータメモリ、１０６は前記タグメモリ１０７に記憶
されたアドレスと外部から入力された検索アドレスとの
一致を判定する比較回路、１０７は前記比較回路１０６
により一致が検出されたウエイのエントリを出力する選
択回路、１０８はエントリの中から所望のデータを選択
する列デコーダ、１１０は前記ＬＲＵ用メモリ１０４に
参照履歴を書き込む制御回路、１１は外部からエントリ
を無効化するインバリッド信号、１２は外部から入力さ
れた検索アドレスが前記タグメモリに記憶されているこ
とを示すキャッシュ・ヒット信号を示している。

【００１３】本実施例によるキャッシュメモリ装置は外
部から入力されるインバリッド信号１１がＬＲＵ書き込
み制御回路１１０に入力され、エントリの無効化時に該
エントリを最も以前に参照されたエントリとする如き情
報をＬＲＵ用メモリ１０４に書き込むことに特徴があ
る。図２は４ウエイのＬＲＵ書き込み制御回路１１０の
動作説明図であり、これを参照しながら動作を説明す
る。尚、図１に示すように、タグメモリ１０２、バリッ
トビットメモリ１０３、データメモリ１０５がそれぞれ
４面有することにより、４ウエイセットアソシアティブ
のキャッシュメモリ装置が実現されている。

【００１４】ＬＲＵ用メモリ１０４には、例えば、図２
（ａ）に示すようにウエイの参照履歴を図中の矢印の向
きで表し、矢印が向けられた方のエントリが以前に参照
されたと定義し、図２（ａ）の矢印の向きを１と定義し
た６ビットの情報ａ、ｂ、ｃ、ｄ、ｅ、ｆが記憶され
る。置換要求が起きた場合には、全ての矢印が向けられ
たウエイを選択する。

【００１５】いま、タグメモリ１０２に記憶されたアド
レスと中央処理装置から入力された検索アドレスとが一
致して比較回路１０６からヒット信号１２が送られた場
合を考える。図２（ａ）では、ヒットに該当するウエイ
に向けられた矢印の向きを全て反転することで最も最近
参照されたウエイであることが示され、ＬＲＵ用メモリ
１０４には、図２（ｂ）のインバリッド信号無の該当す
る情報、例えばウエイ０がヒットの場合ａ＝ｂ＝ｄ＝０
を書き込む。

【００１６】一方、外部よりエントリを無効にするイン
バリッド信号１１が送られた場合を考える。図２（ａ）
では、該当するウエイから出ていく矢印の向きを全て反
転することで最も以前に参照されたウエイであることが
示され、ＬＲＵ用メモリ１０４には、図２（ｂ）のイン
バリッド信号有の該当する情報、例えばウエイ０が無効
化する場合にはａ＝ｂ＝ｄ＝１を書き込むとともに、バ
リッドメモリ１０３に無効なデータが格納されているエ
ントリであることを示す情報を書き込む。

【００１７】以上の動作により、エントリの置換時に
は、ＬＲＵ法により最も以前に参照されたエントリが置
換されるとともに、無効エントリが存在する場合には該
エントリが優先して置換されることとなり、キャッシュ
メモリの使用効率を高めることができる。

【００１８】図３はＬＲＵ書き込み制御回路１１０の具
体例を示す回路図である。図３において、１１０はＬＲ
Ｕ書き込み制御回路、１０４はＬＲＵ用メモリを示し、
図１における番号と対応している。また、１１１、１１
２はタグメモリ１０２に記憶されたアドレスと外部から
入力された検索アドレスの一致をそれぞれ示すウエイ０
信号、ウエイ１信号、１１３はインバリッド信号が無い
場合の書き込み信号１、１１４はインバリッド信号が有
る場合の書き込み信号２を示す。図３では、６ビットあ
るＬＲＵ情報のうちａビットのＬＲＵ書き込み制御回路
およびＬＲＵ用メモリを示すが、他のビットもウエイ信
号の入力が異なるが同じ回路で構成される。

【００１９】ヒット信号１２によるＬＲＵ用メモリ１０
４に書き込むビット位置と、インバリッド信号１１によ
るＬＲＵ用メモリ１０４に書き込むビット位置は等し
く、また、各値は否定の関係にあるため、ＬＲＵ書き込
み制御回路１１０は図３のように簡単な回路構成にする
ことができる。

【００２０】

【発明の効果】本発明によれば、エントリ無効化時に該
エントリを最も以前に参照されたエントリとする情報を
ＬＲＵ記憶手段へ書き込むことで、無効なエントリを優
先して置換することが可能であり、置換すべきエントリ
を選択する際に、無効となったデータを格納したエント
リを優先して選択する制御回路を必要とせず、ＬＲＵ法
でのみ選択信号を出力することができ、置換動作をより
高速に実行できるキャッシュメモリ装置がもたらせる。

【００２１】さらに、ＬＲＵ記憶手段に書き込む、最も
以前に参照されたエントリとする情報は、従来行われて
いるデータを参照した時に書き込む、最も最近参照され
たことを示す情報と否定の関係にあり、その書き込み制
御回路は簡単にすることができるという効果もある。

【図面の簡単な説明】

【図１】本発明の一実施例によるキャッシュメモリ装置
を示すブロック図である。

【図２】図１のキャッシュメモリ装置で参照履歴を説明
するとともに参照履歴を書き替える動作を説明する図で
ある。

【図３】図１のキャッシュメモリ装置のＬＲＵ書き込み
制御回路１１０の具体例を示す回路図である。

【符号の説明】

１０１…行デコーダ、１０２…タグメモリ、１０３…バ
リッドメモリ、１０４…ＬＲＵ用メモリ、１０５…デー
タメモリ、１０６…比較回路、１０７…選択回路、１０
８…列デコーダ、１１０…ＬＲＵ書き込み制御回路、１
１…インバリッド信号、１２…ヒット信号、１１１…ウ
エイ０信号、１１２…ウエイ１信号、１１３…書き込み
信号１、１１４…書き込み信号２。

Claims (1)

【特許請求の範囲】
1. 【請求項１】データを記憶する複数のエントリからなる
   データメモリと、該データメモリの記憶データに対応し
   そのアドレスの一部を記憶する複数のエントリからなる
   タグメモリと、上記データメモリの記憶データに対応し
   そのデータが有効であることを記憶するバリッドメモリ
   と、上記データメモリの記憶データに対応しそのデータ
   の参照情報を記憶する複数のエントリからなるＬＲＵ用
   メモリとを具備してなり、上記ＬＲＵメモリ法の参照情
   報によりデータを置換するキャッシュメモリ装置であっ
   て、 上記データメモリの記憶データが無効となることを指示
   するインバリッド信号に従ってＬＲＵ用メモリの参照情
   報を書き換える制御手段をさらに具備してなることを特
   徴とするキャッシュメモリ装置。