JPH086851A - キャッシュメモリ制御装置 - Google Patents

Abstract

(57)【要約】 【目的】大容量のキャッシュメモリ中のダーティエント
リを高速に検索する。 【構成】メインメモリ12のデータの一部を保持するキャ
ッシュメモリ13の更新情報を検索するキャッシュメモリ
制御装置において、該キャッシュメモリ13のライン領域
毎に設けられ、該ライン領域がメインメモリの対応デー
タと異なる更新されたデータを保持する際に、その直前
にデータが更新されたライン領域の情報を示すライン情
報を記憶する線形リスト構成情報格納領域13ｃと、上記
線形リスト構成情報格納領域13ｃに記憶される最新の更
新されたライン領域の情報を示すルート情報を記憶する
ルート処理部14ｄと、上記ルート処理部14ｄのルート情
報と上記線形リスト構成情報格納領域13ｃのライン情報
とに基づいて上記キャッシュメモリ13のライン領域を線
形リスト状に検索し、各該当ラインのデータを上記メイ
ンメモリへ書戻すフラッシュ処理を実行する制御回路14
ａとを備える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、比較的大規模なキャッ
シュメモリを使用した計算機システムに適用され、該キ
ャッシュメモリの更新情報を検索するキャッシュメモリ
制御装置に関する。

【０００２】

【従来の技術】電子計算機システムにおいて、プロセッ
サの処理能力が大きく向上した現在では、比較的低速で
動作するメインメモリとプロセッサとの間でのデータ転
送速度の差異がデータ処理上のネックとなっている。そ
こで、プロセッサとメインメモリとの間に比較的高速で
動作可能なキャッシュメモリを介在させ、プロセッサは
キャッシュメモリに対してアクセスを行なわせること
で、その処理能力を充分に発揮することができるように
なる。

【０００３】しかるに、キャッシュメモリを備えた計算
機システムでは、プロセッサからの書込みデータが一旦
キャッシュメモリ内に蓄えられるため、メインメモリ内
に最新のデータが反映されない期間が生ずる。そして、
このメインメモリ内に最新のデータが反映されていない
状態でプロセッサあるいはキャッシュメモリに障害が発
生した際にも最新データの消失を最小限に止めるために
は、キャッシュメモリ内のダーティエントリ（更新項
目）を適宜消去してキャッシュメモリ内のデータとメイ
ンメモリ内のデータの内容を一致させておく必要があ
り、キャッシュメモリ内の上記ダーティエントリをサー
チする機能が必要である。

【０００４】従来のキャッシュメモリの構成では図１４
に示すように例えばライン単位で設定される各キャッシ
ュ項目に１対１で対応して項目部分のダーティ（更新）
／クリーン（未更新）の情報が格納されたタグ領域が設
けられており、ソフトウェアによって全てのタグ領域を
順次走査してダーティエントリを検索する。図１４中、
「ラインＮｏ．」はキャッシュメモリ内における各ブロ
ックの配置を示すライン情報を示し、また「キャッシュ
エントリ」は実際に当該ラインに配置されている情報を
示すものであり、図中ではそのエントリ内のデータがダ
ーティなのかクリーンなのかを示す。さらに、「タグ領
域」は計算機システムに依存した、キャッシュメモリ操
作に必要なビット列を格納する領域であり、この中にあ
るダーティ／クリーンビットはタグ領域に対応するキャ
ッシュエントリがダーティかどうかを示すものである。

【０００５】

【発明が解決しようとする課題】上記図１４に示した従
来の方法では、キャッシュメモリ内のタグ領域全てをソ
フトウェアによって順次走査してダーティエントリを検
索するため、ダーティエントリの検索処理に時間がかか
る。この傾向は、キャッシュメモリの容量すなわち走査
領域が広いほど顕著であり、一方、キャッシュメモリは
年々広域化の一途を辿っているので、検索に要する時間
はこれからさらに増大するものと思われる。

【０００６】本発明は上記のような実情に鑑みてなされ
たもので、その目的とするところは、容量の大きなキャ
ッシュメモリであってもダーティエントリをより高速に
検索することが可能なキャッシュメモリ制御装置を提供
することにある。

【０００７】

【課題を解決するための手段】すなわち本発明は、メイ
ンメモリのデータの一部を保持するキャッシュメモリの
更新情報を検索するキャッシュメモリ制御装置におい
て、該キャッシュメモリのライン領域毎に設けられ、該
ライン領域がメインメモリの対応データと異なる更新さ
れたデータを保持する際に、その直前にデータが更新さ
れたライン領域の情報を示すライン情報を記憶する更新
記憶手段と、上記更新記憶手段に記憶される最新の更新
されたライン領域の情報を示すルート情報を記憶するル
ート記憶手段と、上記ルート記憶手段のルート情報と上
記更新記憶手段のライン情報とに基づいて上記キャッシ
ュメモリのライン領域を線形リスト状に検索し、各該当
ラインのデータを上記メインメモリへ書戻すフラッシュ
処理を実行するキャッシュ制御手段とを備えるようにし
たものである。

【０００８】

【作用】上記のような構成とすることにより、必要なラ
イン領域のみ線形リスト状に検索するため、容量の大き
なキャッシュメモリであってもダーティエントリをより
高速に検索することが可能となる。

【０００９】

【実施例】

［第１実施例］以下本発明をキャッシュメモリの全領域
を対象としてその制御を行なう制御装置に適用した場合
の第１実施例について図面を参照して説明する。

【００１０】図１はその回路構成を示すもので、11は演
算を実行するＣＰＵ、12はバス接続されたメインメモ
リ、13は上記ＣＰＵ11と上記メインメモリ12が接続され
たバスとの間に介在されたキャッシュメモリである。

【００１１】キャッシュメモリ13は、ＣＰＵ11の書込み
によって上記メインメモリ12のデータの一部を保持する
データ領域13ａ、このキャッシュメモリ13の操作に必要
なビット列を格納する領域であるタグ領域13ｂ及び各キ
ャッシュエントリ毎に追加された情報であり、その直前
にダーティとなった他のライン情報を格納する領域であ
る線形リスト構成情報格納領域13ｃを有する。

【００１２】そして、このキャッシュメモリ13のタグ領
域13ｂ及び線形リスト構成情報格納領域13ｃを制御する
ものとして、キャッシュメモリ制御回路14が設けられ
る。このキャッシュメモリ制御回路14は、線形リストの
構成および線形リストを用いたフラッシュ処理を実現す
るための制御回路14ａ、上記タグ領域13ｂの書込み／読
出しに用いられるタグ情報バッファ14、上記線形リスト
構成情報格納領域13ｃの書込み／読出しに用いられるリ
スト情報バッファ14ｃ及び、線形リストの構築、フラッ
シュ処理操作のための作業領域であるルート処理部14ｄ
を有する。

【００１３】次に上記第１実施例の具体的な動作につい
て説明する。図２（Ａ）は線形リストによるダーティエ
ントリの検索を行なう上記キャッシュメモリ13の具体構
成を例示するものである。図中、「ライン番号（Ｎ
ｏ．）」は各キャッシュエントリのラインを、「キャッ
シュエントリ」はデータ自身を示し、共に上記データ領
域13ａを構成するものであるが、図２（Ａ）ではそのデ
ータがキャッシュに格納されてから更新されたかどうか
をダーティ（更新）／クリーン（未更新）として表記し
てある。ここで括弧内の回数値は、各データが更新され
た時の順番を示している。また、「タグ領域」は上述し
た如く計算機システムに依存した、キャッシュメモリ13
操作に必要なビット列を格納する領域であり、「線形リ
スト」は、各キャッシュエントリ毎に追加された情報で
あり、ダーティとなったキャッシュエントリの１つ前に
ダーティとなった他のライン領域の情報を示している。
図中のヌル（Ｎｕｌｌ）は初期値を示す。

【００１４】また、図２（Ｂ）に示す「ルート」は、上
記キャッシュメモリ制御回路14のルート処理部14ｄの具
体構成を例示するもので、線形リストを構築するための
作業領域として、具体的には１ラインの配置情報を格納
できるメモリで構成される。

【００１５】図３に線形リストの構築処理内容を示すフ
ローチャートを、図４に線形リストを基にしたダーティ
エントリの検索処理内容を示すフローチャートをそれぞ
れ示す。

【００１６】ＣＰＵ11がキャッシュメモリ13のデータ領
域13ａへデータを書込む際には、前回ダーティとなった
キャッシュエントリのライン情報であるルートの値を現
キャッシュラインに対応した線形リスト構成情報格納領
域に保存し、ルートを現ラインのライン番号で更新す
る。この一連の操作を図３に示す。すなわち、図３で
は、ダーティとなった現ラインの線形リスト構成情報格
納領域13ｃ該当部分をルート処理部14ｄの内容で更新設
定し（ステップＡ1 ）、次いでルート処理部14ｄの内容
をダーティとなった現ラインのラインＮｏ．で更新設定
する（ステップＡ2）というものである。

【００１７】以上の処理内容について具体的に図２に沿
って動作を追認するものとする。ルート処理部14ｄには
初期値としてヌル（Ｎｕｌｌ）情報が格納されており、
例えばキャッシュメモリ13のデータ領域13ａのラインＮ
ｏ．３が最初にダーティとなると、ルート処理部14ｄの
内容が同キャッシュエントリのラインＮｏ．である
“３”に更新される。続いてルート処理部14ｄの最初の
格納内容であるヌル情報が代わってラインＮｏ．３の線
形リスト構成情報格納領域13ｃに格納される。

【００１８】続いてデータ領域13ａのラインＮｏ．２が
ダーティとなると、ルート処理部14ｄの現情報“３”が
ラインＮｏ．２の線形リスト構成情報格納領域13ｃへ格
納される。続いてルート処理部14ｄの内容が同キャッシ
ュエントリのラインＮｏ．である“２”に更新される。

【００１９】このような操作を繰返すことで図２に示す
に如く例えば合計５箇所のキャッシュエントリがダーテ
ィとなった時点で、次にキャッシュメモリ13のフラッシ
ュ処理を行なうものとする。

【００２０】キャッシュメモリ13のフラッシュ処理を行
なうには、図４に示す如く最初にルート処理部14ｄの値
を参照し（ステップＢ1 ）、その値がヌルであるか否か
の判断を行なう（ステップＢ2 ）。ヌルであればフラッ
シュ処理を終了し、そうでなければルート処理部14ｄに
よって示されるラインのフラッシュ処理へ進み（ステッ
プＢ3 ）、そのラインをフラッシュし（ステップＢ4
）、対応する線形リスト構成情報格納領域13ｃの内容
でルート処理部14ｄを更新した（ステップＢ5 ）後に、
線形リスト構成情報格納領域13ｃの当該ラインをヌル情
報で更新する（ステップＢ6 ）。

【００２１】以上の処理内容についても具体的に図２に
沿って動作を追認するものとする。キャッシュメモリ13
のデータ領域13ａのフラッシュ処理のためにダーティエ
ントリを検索するには、最初にルート処理部14ｄの内容
を参照する（ステップＢ1 ）。ルート処理部14ｄの値が
ヌルであると判断すると（ステップＢ2 ）その時点でこ
のフラッシュ処理を終了するが、ここでは最初にルート
処理部14ｄが示した値が“６”であるため、ラインＮ
ｏ．６のフラッシュ操作へ進む（ステップＢ3 ）。

【００２２】ラインＮｏ．６のラインをフラッシュ処理
し（ステップＢ4 ）、次にフラッシュ処理するキャッシ
ュエントリのラインＮｏ．である、線形リスト構成情報
格納領域13ｃの内容“１”でルート処理部14ｄを更新設
定してから（ステップＢ5 ）、線形リスト構成情報格納
領域13ｃの当該ラインをヌルで初期化する（ステップＢ
6 ）。

【００２３】続いてラインＮｏ．１のキャッシュライン
をフラッシュし、次にフラッシュ処理するキャッシュエ
ントリのラインＮｏ．である、線形リスト構成情報格納
領域13ｃの内容“５”でルート処理部14ｄを初期化して
からヌルによる線形リスト構成情報格納領域13ｃの初期
化を行なう。

【００２４】以上のようなフラッシュ処理の操作をルー
ト処理部14ｄからヌルが戻るまで繰返すことにより、キ
ャッシュメモリ13のデータ領域13ａにおけるダーティエ
ントリを全てフラッシュ処理することができる。

【００２５】［第２実施例］以下本発明をキャッシュメ
モリ内のある特定された限定範囲のダーティエントリの
みを対象としてその制御を行なう制御装置に適用した場
合の第２実施例について図面を参照して説明する。

【００２６】図５はその回路構成を示すもので、基本的
には上記図１に示したものと同様であるので、同一部分
には同一符号を付してその説明は省略する。しかして、
キャッシュメモリ制御回路内には、制御回路14ａ、タグ
情報バッファ14ｂ、リスト情報バッファ14ｃ及びルート
処理部14ｄの他に、フラッシュ処理中のライン位置を示
す現ラインポインタ14ｅ、フラッシュ処理を行なうライ
ンの直前のフラッシュ範囲外ダーティライン位置を示す
バックアップポインタ14ｆ、フラッシュ処理するキャッ
シュメモリの領域の終了ライン位置を示す終了ラインポ
インタ（図では「Ｕラインポインタ」と示す）14ｇ、フ
ラッシュ処理するキャッシュメモリの領域の開始ライン
を示す開始ラインポインタ（図では「Ｌラインポイン
タ」と示す）14ｈを有する。

【００２７】次に上記第１実施例の具体的な動作につい
て説明する。図６（Ａ）は線形リストによるダーティエ
ントリの検索を行なう上記キャッシュメモリ13の具体構
成を例示するものである。図中、「ライン番号（Ｎ
ｏ．）」は各キャッシュエントリのラインを、「キャッ
シュエントリ」はデータ自身を示し、共に上記データ領
域13ａを構成するものであるが、図６（Ａ）ではそのデ
ータがキャッシュに格納されてから更新されたかどうか
をダーティ（更新）／クリーン（未更新）として表記し
てある。ここで括弧内の回数値は、各データが更新され
た時の順番を示している。また、「タグ領域」13ｂは上
述した如く計算機システムに依存した、キャッシュメモ
リ13操作に必要なビット列を格納する領域であり、「線
形リスト」13ｃは、各キャッシュエントリ毎に追加され
たライン情報であり、ダーティな状態にあるキャッシュ
エントリの線形リストを構成するための直前にダーティ
となったライン領域の情報が格納される。図中のヌル
（Ｎｕｌｌ）は初期値を示す。

【００２８】また、図６（Ｂ）に示す「ルート」は、上
記キャッシュメモリ制御回路14のルート処理部14ｄの具
体構成を例示するもので、線形リストを構築するための
作業領域として、具体的には１ラインの配置情報を格納
できるメモリで構成される。

【００２９】ＣＰＵ11がキャッシュメモリ13のデータ領
域13ａへデータを書込む際には、前回ダーティとなった
キャッシュエントリのライン情報であるルートの値を現
キャッシュラインに対応した線形リスト構成情報格納領
域に保存し、ルートを現ラインのライン番号で更新す
る。この一連の操作を図７に示す。

【００３０】すなわち、図７は上記線形リスト構成情報
格納領域13ｃを構築するための処理内容を示すものであ
り、まずダーティとなった現ラインの線形リスト構成情
報格納領域13ｃ該当部分をルート処理部14ｄの内容で更
新設定し（ステップＣ1 ）、次いでルート処理部14ｄの
内容をダーティとなった現ラインのラインＮｏ．で更新
設定する（ステップＣ2 ）というものである。

【００３１】以上の処理内容について具体的に図６に沿
って動作を追認するものとする。ルート処理部14ｄには
初期値としてヌル（Ｎｕｌｌ）情報が格納されており、
例えばキャッシュメモリ13のデータ領域13ａのラインＮ
ｏ．３が最初にダーティとなると、ルート処理部14ｄの
内容が同キャッシュエントリのラインＮｏ．である
“３”に更新される。続いてルート処理部14ｄの最初の
格納内容であるヌル情報が代わってラインＮｏ．３の線
形リスト構成情報格納領域13ｃに格納される。

【００３２】続いてデータ領域13ａのラインＮｏ．２が
ダーティとなると、ルート処理部14ｄの現情報“３”が
ラインＮｏ．２の線形リスト構成情報格納領域13ｃへ格
納される。続いてルート処理部14ｄの内容が同キャッシ
ュエントリのラインＮｏ．である“２”に更新される。

【００３３】このような操作を繰返すことで図６に示す
に如く例えば合計５箇所のキャッシュエントリがダーテ
ィとなった時点で、次にキャッシュメモリ13の範囲を限
定したフラッシュ処理を行なうものとする。

【００３４】しかるに、範囲限定のフラッシュ処理を実
行した後に、この範囲限定のフラッシュ処理前に最後に
ダーティとなったキャッシュエントリから連続した線形
リスト構成情報格納領域13ｃを構築するためには、該最
後にダーティとなったキャッシュエントリのライン情報
を保存しておかなければならない。そのために、限定範
囲内のダーティエントリ検索では、限定範囲の開始ライ
ン位置を記憶する開始ラインポインタ14ｈ、同終了ライ
ン位置を記憶する終了ラインポインタ14ｇ、フラッシュ
処理中のライン情報を記憶する現ラインポインタ14ｅ及
びライン情報をバックアップするためのバックアップポ
インタ14ｆをキャッシュメモリ制御回路14内に設けるも
のである。

【００３５】図８（Ａ）は線形リスト構成情報格納領域
13ｃにしたがった範囲限定でのダーティエントリの検索
を行なう上記キャッシュメモリ13の具体構成を例示する
ものである。ここでは、フラッシュ処理の範囲を限定す
るものとして、例えばラインＮｏ．１とラインＮｏ．２
のみをフラッシュ処理するものとする。

【００３６】また、この図８（Ａ）のキャッシュメモリ
13の内容に対応した現ラインポインタ14ｅ、バックアッ
プポインタ14ｆの記憶内容の具体構成を図８（Ｂ），
（Ｃ）に例示する。

【００３７】以下、図９により上記のようにして構築し
た線形リスト構成情報格納領域13ｃを基にしたダーティ
エントリの検索及びキャッシュメモリ13の限定された範
囲を対象とするフラッシュ処理について述べる。

【００３８】その処理当初には、まず初期設定として最
初にルート処理部14ｄの値による現ラインポインタ14ｅ
の更新（ステップＤ1 ）及びバックアップポインタ14ｆ
のヌルによる初期化（ステップＤ2 ）を行ない、以後の
フラッシュ処理操作は全て現ラインポインタ14ｅを使用
して行なうものとする。

【００３９】すなわち、現ラインポインタ14ｅの値を参
照し（ステップＤ3 ）、その値がヌルであるか否か判断
するもので（ステップＤ4 ）、ヌルであればキャッシュ
フラッシュを終了し、そうでなければ現ラインポインタ
14ｅの示すキャッシュメモリ13のライン領域の線形リス
ト構成情報格納領域13ｃからライン情報を読出し、これ
をあらたに現ラインポインタ14ｅに更新設定する（ステ
ップＤ5 ）。

【００４０】続いてこの更新設定した現ラインポインタ
14ｅのライン情報が開始ラインポインタ14ｈ及び終了ラ
インポインタ14ｇで指定される範囲内にあるか否か判断
し（ステップＤ6 ）、範囲外であればこの現ラインポイ
ンタ14ｅのライン情報をバックアップポインタ14ｆに更
新設定した後（ステップＤ7 ）、上記ステップＤ5 と同
様にこの現ラインポインタ14ｅの示すキャッシュメモリ
13のライン領域の線形リスト構成情報格納領域13ｃから
ライン情報を読出し、これをあらたに現ラインポインタ
14ｅに更新設定し（ステップＤ8 ）、再び上記ステップ
Ｄ3 からの処理を繰返す。

【００４１】また、上記ステップＤ6 で現ラインポイン
タ14ｅのライン情報が開始ラインポインタ14ｈ及び終了
ラインポインタ14ｇで指定される範囲内にあると判断し
た際には、キャッシュメモリ13の当該ラインをフラッシ
ュ処理し（ステップＤ9 ）、このフラッシュ処理した当
該ラインの線形リスト構成情報格納領域13ｃのライン情
報で現ラインポインタ14ｅを更新設定した後に（ステッ
プＤ10）、該線形リスト構成情報格納領域13ｃをヌルに
より更新設定する（ステップＤ11）。

【００４２】その後、バックアップポインタ14ｆの示す
値がヌルであるか否か判断し（ステップＤ12）、ヌルで
なければバックアップポインタ14ｆの内容が示すキャッ
シュメモリ13の当該ラインの線形リスト構成情報格納領
域13ｃを現ラインポインタ14ｅの値で更新した後（ステ
ップＤ14）、上記ステップＤ3 からの処理に戻る。

【００４３】また、ステップＤ12でバックアップポイン
タ14ｆの内容がヌルであった場合には、最後にダーティ
となったキャッシュメモリのライン領域が上記開始ライ
ンポインタ14ｈ及び終了ラインポインタ14ｇで指定され
る指定範囲内に含まれていたことを示すので、現ライン
ポインタ14ｅの値でルート処理部14ｄを更新し、最後に
ダーティとなったライン情報を更新した後（ステップＤ
13）、上記ステップＤ3 からの処理に戻る。

【００４４】以上の処理内容についても具体的に図８に
沿って動作を追認するものとする。キャッシュメモリ13
のデータ領域13ａのフラッシュ処理のためにダーティエ
ントリを検索するには、検索を開始するキャッシュメモ
リのライン領域のラインＮｏ．“６”をルート処理部14
ｄから現ラインポインタ14ｅへコピーし（ステップＤ1
）、バックアップポインタ14ｆの内容をヌルで初期化
する（ステップＤ2 ）。

【００４５】次にルート処理部14ｄの内容を参照して値
がヌルであればこのフラッシュ処理を終了するが、最初
に現ラインポインタ14ｅの示す値が“６”であるため、
これを判断し（ステップＤ4 ）、さらにこのラインＮ
ｏ．６のライン領域が指定範囲外であることを判断して
（ステップＤ6 ）、現キャッシュラインのラインＮｏ．
“６”をバックアップポインタ14ｆに退避させ（ステッ
プＤ7 ）、対応する線形リストのライン情報“１”で現
ラインポインタ14ｅを更新する（ステップＤ8 ）。

【００４６】次いで、キャッシュメモリのフラッシュ処
理のために次のダーティエントリを検索するべく、現ラ
インポインタ14ｅの内容を参照し（ステップＤ3 ）、現
ラインポインタ14ｅの値が“１”であるためキャッシュ
メモリ13のラインＮｏ．１のライン領域の操作へ進む。

【００４７】現ラインが指定範囲内であるためにこれを
判断し（ステップＤ6 ）、ラインＮｏ．１のライン領域
のフラッシュ処理を実行し（ステップＤ9 ）、このライ
ンＮｏ．１の対応する線形リストの内容“５”で現ライ
ンポインタ14ｅを更新し（ステップＤ10）、さらに該線
形リストの内容をヌルで更新した後（ステップＤ11）、
現在のバックアップの値が“６”であるのでこれがヌル
でないと判断してから（ステップＤ12）、ラインＮｏ．
６のライン領域の線形リストを現ラインポインタ14ｅの
示す“５”で更新する。

【００４８】このような操作を線形リストからヌルが戻
るまで繰返すことにより、指定された範囲内、ここでは
ラインＮｏ．１とラインＮｏ．２にある全てのダーティ
エントリをフラッシュ処理することができるようにな
る。

【００４９】［第３実施例］以下本発明の第３実施例に
ついて図面を参照して説明する。図１０はその回路構成
を示すもので、21は演算を実行するＣＰＵ、22はバス接
続されたメインメモリ、23は上記ＣＰＵ21と上記メイン
メモリ22が接続されたバスとの間に介在されたキャッシ
ュメモリである。

【００５０】キャッシュメモリ23は、ＣＰＵ21の書込み
によって上記メインメモリ22のデータの一部を保持する
データ領域23ａと、このキャッシュメモリ23の操作に必
要なビット列を格納する領域であるタグ領域23ｂとを有
する。

【００５１】そして、このキャッシュメモリ23を制御す
るものとして、キャッシュメモリ制御回路24が設けられ
る。このキャッシュメモリ制御回路24は、フラッシュ処
理を実現するための統括的な制御を行なう制御回路24
ａ、上記ＣＰＵ21への割込み要求を発生する割込み要求
発生回路24ｂ、上記キャッシュメモリ13におけるライン
領域がメインメモリ22の対応データと異なる更新された
データを保持する際にそのライン領域を示すライン情報
をテーブルとして保持するテーブル領域24ｃ、上記テー
ブル領域24ｃの書込み／読出しの際にそのポイント位置
を指示するテーブルポインタ24ｄ及びテーブル領域24ｃ
の記憶容量に応じたテーブルポインタ24ｄの指示ポイン
トの限界位置を保持する限界ポインタ24ｅを有する。

【００５２】次に上記第３実施例の具体的な動作につい
て説明する。図１１（Ａ）はダーティエントリを有する
上記キャッシュメモリ23の状態を、図１１（Ｂ）は上記
キャッシュメモリ23に対応したキャッシュメモリ制御回
路のテーブル領域24ｃ及びテーブルポインタ24ｄの状態
を例示するものである。

【００５３】図１１（Ａ）中、「ライン番号（Ｎ
ｏ．）」は各キャッシュエントリのライン位置を示して
いる。また、「キャッシュエントリ」はデータ自身を示
し、図１１（Ａ）でデータがキャッシュメモリ23に格納
されてから更新されたかどうかをダーティ（更新）／ク
リーン（未更新）として図中に表記してある。ここで、
括弧内の回数値は、各データが更新された時の順番を示
している。また、「タグ領域」23ｂは上述した如く計算
機システムに依存した、キャッシュメモリ23操作に必要
なビット列を格納する領域である。

【００５４】これに対して図１１（Ｂ）のテーブル領域
24ｃは、ダーティエントリのライン情報を格納するため
の記憶領域であり、ｍ個のテーブルエントリから構成さ
れ、テーブルポインタ24ｄが該テーブル領域24ｃ内での
変位をポイント指示している。ここでテーブル領域24ｃ
のテーブルエントリ数ｍは、キャッシュメモリ23の全ラ
イン数ｎ分のダーティエントリを対象とした場合では
「ｍ＝ｎ」となり、特定ライン数分のダーティエントリ
を対象とした場合では、限界ポインタ24ｅに設定されて
いる特定数と等しいものとなる。

【００５５】図１２は上記テーブル領域24ｃを構築する
ための処理内容を示すフローチャートであり、主として
上記制御回路24ａの動作制御により実行されるものであ
る。ＣＰＵ21がキャッシュメモリ23へデータを書込む際
には、テーブルポインタ24ｄの指示するテーブル領域24
ｃのテーブルエントリへダーティとなったラインＮｏ．
を格納させ（ステップＥ1 ）、テーブルポインタ24ｄを
インクリメントした後に（ステップＥ2 ）、テーブルポ
インタ24ｄの値が限界ポインタ24ｅのポイント指示する
テーブル領域24ｃの特定数となったかを判定する（ステ
ップＥ3 ）。

【００５６】限界ポインタ24ｅの特定数に達していない
場合であれば、このダーティエントリに関する処理は終
了するが、限界ポインタ24ｅの特定数に達しており、フ
ラッシュ処理を行なう範囲を超過していると判定した場
合には、ＣＰＵ21からキャッシュメモリ23へこれ以上の
書込みが行なわれないように割込み要求発生回路24ｂか
らＣＰＵ21に対して割込み要求の信号を発生させる。こ
の割込みに対する一連の処理操作を図１３に示す。

【００５７】図１３は上記図１２の処理により構築され
た上記テーブル領域24ｃに基づくキャッシュメモリ13の
フラッシュ処理その他の処理内容を示すフローチャート
であり、主として上記制御回路24ａの動作制御により実
行されるものである。

【００５８】割込み要求発生回路24ｂによりＣＰＵ21へ
割込み要求の信号を発生させ（ステップＦ1 ）、ＣＰＵ
21からキャッシュメモリ23へこれ以上の書込みが行なわ
れないようにした制御回路24ａは、次いでテーブルポイ
ンタ24ｄをデクリメントした後に（ステップＦ2 ）、テ
ーブルポインタ24ｄの値が“０”（図では「Ｎｕｌｌ」
と示す）となったおらず、したがってまだフラッシュ処
理その他の処理が終了していないことを確認する（ステ
ップＦ3 ）。

【００５９】その上で制御回路24ａは、このテーブルポ
インタ24ｄの指示ポイントに従ってテーブル領域24ｃか
らライン情報を読出し、このライン情報に従ったキャッ
シュメモリ23の当該ライン領域をフラッシュ処理する
（ステップＦ4 ）。

【００６０】その後、テーブルポインタ24ｄの指示ポイ
ントに従ってテーブル領域24ｃの当該テーブルエントリ
を初期化して“０”（Ｎｕｌｌ）を設定し、再び上記ス
テップＦ1 からの処理を繰返す。

【００６１】そして、ステップＦ3 でテーブルポインタ
24ｄの値が“０”（Ｎｕｌｌ）となった時点で、この図
１３の処理をすべて終了するものである。上記した動作
を図１１（Ａ），（Ｂ）の内容に沿って追認するものと
する。

【００６２】テーブルポインタ24ｄには最初“０”が格
納されており、キャッシュメモリ23のラインＮｏ．３が
最初にダーティとなると、テーブルポインタ24ｄによっ
て指定されたテーブル領域24ｃのＮｏ．０のテーブルエ
ントリに、ダーティエントリのラインＮｏ．であるライ
ン情報“３”が格納され（ステップＥ1 ）、テーブルポ
インタ24ｄがインクリメントされて“１”となる（ステ
ップＥ2 ）。

【００６３】続いてキャッシュメモリ23のラインＮｏ．
２がダーティとなると、テーブルポインタ24ｄによって
指定されたテーブル領域24ｃのＮｏ．１のテーブルエン
トリにダーティエントリのラインＮｏ．であるライン情
報“２”が格納され（ステップＥ1 ）、テーブルポイン
タ24ｄがインクリメントされて“２”となる（ステップ
Ｅ2 ）。

【００６４】このような操作を繰返すことで丁度図１１
に示す如くキャッシュメモリ23の合計５箇所のキャッシ
ュエントリがダーティとなった時点で、テーブルポイン
タ24ｄの値“５”が限界ポインタ24ｅに予め設定されて
いる特定数“５”と等しくなったと判定されると（ステ
ップＥ3 ）、ＣＰＵ21からキャッシュメモリ23へこれ以
上の書込みが行なわれないように割込み要求発生回路24
ｂからＣＰＵ21に対して割込み要求の信号を発生させ
（ステップＥ4 ）、図１３によるキャッシュメモリ23の
キャッシュ処理を実行する。

【００６５】すなわち図１３においては、まずＣＰＵ21
からキャッシュメモリ23へこれ以上の書込みが行なわれ
ないように上述した書込み抑制の割込み要求をかけた後
（ステップＦ1 ）、続いてテーブルポインタ24ｄをデク
リメントする（ステップＦ2）。デクリメントされたテ
ーブルポインタ24ｄの値が“０”（Ｎｕｌｌ）を示せば
（ステップＦ3 ）、フラッシュ処理は終了となるが、こ
こでデクリメントされたテーブルポインタ24ｄの値は
“５”を示し、テーブル領域24ｃのＮｏ．５のエントリ
Ｎｏ．に対応するライン情報は“６”を示すので、キャ
ッシュメモリ23のラインＮｏ．６のライン領域をフラッ
シュ処理し（ステップＦ4 ）、続けてテーブル領域24ｃ
のエントリＮｏ．５に対応するライン情報“６”を初期
化して“０”（Ｎｕｌｌ）とし（ステップＦ5 ）、再び
ステップＦ1 に戻る。

【００６６】引続き割込み要求をかけた後（ステップＦ
1 ）に、テーブルポインタ24ｄをデクリメントして
“４”とし（ステップＦ2 ）、ステップＦ3 を介してテ
ーブル領域24ｃのＮｏ．４のエントリＮｏ．に対応する
ライン情報“１”によりキャッシュメモリ23のラインＮ
ｏ．１のライン領域をフラッシュ処理し（ステップＦ4
）、続けてテーブル領域24ｃのエントリＮｏ．４に対
応するライン情報“１”を初期化して“０”（Ｎｕｌ
ｌ）とし（ステップＦ5 ）、再びステップＦ1 に戻る。

【００６７】このような操作をテーブルポインタ24ｄの
値が“０”（Ｎｕｌｌ）になるまで繰返すことにより、
キャッシュメモリ23内に存在するダーティエントリを高
速にフラッシュ処理することができる。

【００６８】なお、上記実施例ではテーブルポインタ24
ｄのエントリＮｏ．４が限界ポインタ24ｅの特定数に達
した時点でキャッシュメモリ23のフラッシュ処理を行な
うこととしたが、特にこの限界ポインタ24ｅを設けず、
テーブル領域24ｃの全エントリＮｏ．である値“ｍ”と
なった時点でＣＰＵ21へ割込み要求をかけ、図１３の処
理を行なうものとしてもよい。

【００６９】

【発明の効果】以上詳記した如く本発明によれば、容量
の大きなキャッシュメモリであってもダーティエントリ
をより高速に検索することが可能なキャッシュメモリ制
御装置を提供することができる。

【図面の簡単な説明】

【図１】本発明の第１実施例に係る回路構成を示すブロ
ック図。

【図２】図１のキャッシュメモリ及びルート処理部の記
憶状態を例示する図。

【図３】同実施例の動作を説明するためのフローチャー
ト。

【図４】同実施例の動作を説明するためのフローチャー
ト。

【図５】本発明の第２実施例に係る回路構成を示すブロ
ック図。

【図６】図５のキャッシュメモリ及びルート処理部の記
憶状態を例示する図。

【図７】同実施例の動作を説明するためのフローチャー
ト。

【図８】図５のキャッシュメモリ、現ラインポインタ及
びバックアップポインタの記憶状態を例示する図。

【図９】同実施例の動作を説明するためのフローチャー
ト。

【図１０】本発明の第３実施例に係る回路構成を示すブ
ロック図。

【図１１】図１０のキャッシュメモリ、テーブル領域及
びテーブルポインタの記憶状態を例示する図。

【図１２】同実施例の動作を説明するためのフローチャ
ート。

【図１３】同実施例の動作を説明するためのフローチャ
ート。

【図１４】従来のキャッシュメモリの構成を例示する
図。

【符号の説明】

11，21…ＣＰＵ、12，22…メインメモリ、13，23…キャ
ッシュメモリ、13ａ，23ａ…データ領域、13ｂ，23ｂ…
タグ領域、13ｃ…線形リスト構成情報格納領域、14，24
…キャッシュメモリ制御回路、14ａ，24ａ…制御回路、
14ｂ…タグ情報バッファ、14ｃ…リスト情報バッファ、
14ｄ…ルート処理部、14ｅ…現ラインポインタ、14ｆ…
バックアップポインタ、14ｇ…終了ラインポインタ、14
ｈ…開始ラインポインタ、24ｂ…割込み要求発生回路、
24ｃ…テーブル領域、24ｄ…テーブルポインタ、24ｅ…
限界ポインタ。

Claims (5)

【特許請求の範囲】
1. 【請求項１】 メインメモリのデータの一部を保持する
   キャッシュメモリの更新情報を検索するキャッシュメモ
   リ制御装置において、 該キャッシュメモリのライン領域毎に設けられ、該ライ
   ン領域がメインメモリの対応データと異なる更新された
   データを保持する際に、その直前にデータが更新された
   ライン領域の情報を示すライン情報を記憶する更新記憶
   手段と、 上記更新記憶手段に記憶される最新の更新されたライン
   領域の情報を示すルート情報を記憶するルート記憶手段
   と、 上記ルート記憶手段のルート情報と上記更新記憶手段の
   ライン情報とに基づいて上記キャッシュメモリのライン
   領域を線形リスト状に検索し、各該当ラインのデータを
   上記メインメモリへ書戻すフラッシュ処理を実行するキ
   ャッシュ制御手段とを具備することを特徴とするキャッ
   シュメモリ制御装置。
2. 【請求項２】 フラッシュ処理するキャッシュメモリの
   範囲の開始ラインを示すポイントを記憶する開始ライン
   ポイント記憶手段と、 フラッシュ処理するキャッシュメモリの範囲の終了ライ
   ンを示すポイントを記憶する終了ラインポイント記憶手
   段とをさらに具備し、 上記キャッシュ制御手段は、上記開始ラインポイント記
   憶手段と上記終了ラインポイント記憶手段の記憶内容で
   示されるキャッシュメモリの範囲のみをフラッシュ処理
   の対象とすることを特徴とする請求項１記載のキャッシ
   ュメモリ制御装置。
3. 【請求項３】 上記キャッシュ制御手段は該キャッシュ
   メモリのメインメモリの対応データと異なる更新された
   データを保持するライン領域の数が特定値となった時点
   でフラッシュ処理を実行することを特徴とする請求項１
   記載のキャッシュメモリ制御装置。
4. 【請求項４】 メインメモリのデータの一部を保持する
   キャッシュメモリの更新情報を検索するキャッシュメモ
   リ制御装置において、 上記キャッシュメモリのライン領域のデータがメインメ
   モリの対応データと異なる更新されたデータを保持する
   際にそのライン領域の情報を示すライン情報をテーブル
   として記憶するテーブル記憶手段と、 上記テーブル記憶手段の最新記憶位置をポイント指示す
   るポイント指示手段と、 このポイント指示手段に従って上記テーブル記憶手段に
   記憶されたライン情報を読出し、そのライン情報に従っ
   て上記キャッシュメモリの当該ライン領域を検索してそ
   のデータを上記メインメモリへ書戻すフラッシュ処理を
   実行するキャッシュ制御手段とを具備することを特徴と
   するキャッシュメモリ制御装置。
5. 【請求項５】 上記テーブル記憶手段に記憶可能な位置
   をポイント指示する限界ポイント指示手段をさらに具備
   し、 上記キャッシュ制御手段は上記ポイント指示手段の指示
   ポイントが上記限界ポイントの指示ポイントと等しくな
   った時点でフラッシュ処理を実行することを特徴とする
   請求項４記載のキャッシュメモリ制御装置。