JPS605021B2 - バッファメモリ装置 - Google Patents

Description

【発明の詳細な説明】 本発明はデータ処理装置に於けるバッファメモリ装置に
関する。

一般に、複数個のブロック単位の記憶領域からなるバッ
ファにおいて新規のデータをそのバッフア上に登録しよ
うとするときは、以前バッファ内に格納されていたデー
タの１つを置換対象として追い出さなければなら．ない
。

このとき、どのデータを追い出すかを決定する方法とし
て、１つの方法はバッファのいずれかを何の規則性もな
くランダムに決定して追い出す方法があり、他の方法と
して一般にＦＩＦ○（ＦｉｒｓｔｌｎＦｉｒｓｔＯｕｔ
）方式と呼ばれる方法があり、この方法では最初に登録
されたデータを追い出すようにしている。

さらに他の方法として一般にＬＲＵ（ＬｅａｓｔＲｅｃ
ｅｎｔｒｙＵｓｅｄ）方式と呼ばれる方法があり、この
方法ではバッファ内のデータの参照された状況により、
最も長い間使用されなかったデータを追い出す方法等が
用いられている。バッファに登録されていても長い間使
用されなかったデー外きど今後も使用される確率が低い
という点からＬＲＵ方式が最も有効である。一方、デー
タ処理装置において、その性能を向上させるための手段
として読出し書込みメモリを使用し、主記憶装置のデー
タの写しを保持するキャッシュメモリまたは仮想記憶計
算機における仮想アドレスと実アドレスとの変換テーブ
ルの写しを中央処理装置内に有するＴＬＢ（Ｔｒａｎｓ
ｌａｔｉｏｎ功ｏＫａｓｉｄｅＢ山ｆｅｒ）等のバッ
ファメモリが用いられているが、これらのバッファメモ
リにおいてその追い出し制御方式としてＬＲＵ方式を採
用する場合、ＬＲＵ制御ビットを格納するＬＲＵメモリ
を持ち、バッファメモリ上のデータを参照した時、ＬＲ
Ｕメモリの参照されたデ−夕の格納位置を最高の優先度
を持つように設定し、バッファメモ川こ新規のデータを
登録しようとする場合はＬＲＵメモリの内容により最も
優先度の低い、すなわち、最も長く参照されなかったデ
ータ位置を決定し、そのデータを追い出すことを行なっ
ている。

また複数の中央処理装置からなるマルチプロセッサシス
テムにおいて、たとえばキヤツシユメモリにおいては一
方の中央処理装置が主記憶装置上のデータを書替えた時
、他方の中央処理装置上のキャッシュメモリ内にそのデ
ータが登録されていると、そのデータも新デー外こ暦換
えるか、またはキャッシュメモリ上のそのデータを無効
とする処理を行なう必要がある。

本処理は一般には各中央処理装置間で主記憶のアドレス
を送信する通信手段を設け、中央処理装置が主記憶装置
に書込みアクセスを行なった時、他の中央処理装置にそ
のアドレスを送り、それを受取った中央処理装置はキャ
ッシュメモリを調べそのアドレスのブロックデータが登
録されているとそのブロックの有効性を示す有効ビット
をリセットすることにより実現している。

このとき、キャッシュメモリ上にはデータの登録されて
いない空ブロックが生じることになる。このキャッシュ
メモリに新規にデータを登録しようとする場合、ＬＲＵ
メモリの内容だけにより追い出すべきブロックを決定す
るのでは無く、まず有効ビットの状態を調べ、もしデー
タの登録されていない空ブロックが有る場合には、その
ブロックに優先的にデータを登録する方法が有利となる
。

したがって追い出すべきブロック位置を決定する論理と
しては、まず第１に有効ビットの状態により空ブロック
の有無を調べもし空ブロックが有る場合にはそのブロッ
クに優先的に割り付け、もし空ブロックが無い場合、Ｌ
ＲＵメモリの内容を調べ、その内容により最も低い優先
度をもつブロックを追い出すという手順が必要となり、
追い出し決定用の論理を複雑にすると共にそれを実現す
るハードウェア量が増加するという欠点があった。

本発明の目的は、あるブロック上のデータを無効とする
時、有効ビットをリセットするとともに、無効としたブ
ロックを最も優先度が低くなるようにＬＲＵメモリの内
容を書替えることにより、上記欠点を解決し、追い出す
べきブロックを決定する時に、ＬＲＵメモリの内容だけ
で従来と同じ機能を少ないハードウェア量で実現したＬ
ＲＵ方式を用いたバッファメモリ装置を提供することに
ある。

本発明によれば、ブロック単位の記憶領域を有するデー
タ記憶用のデータ記憶手段と、このデータ記憶手段の各
ブロックに対応してデータが前記データ記憶手段に格納
されている場合を示す有効情報を記憶する有効情報記憶
手段と、前記データ記憶手段の記憶位置に対応した前記
ブロック単位の優先順位を示す優先順位指示情報を記憶
する優先順位指示情報記憶手段と、データがアクセスさ
れた時に前記データ記憶手段内のアクセスされた記憶ブ
ロックに対応する前記優先順位指示情報を最優先順位と
するように前記優先順位指示情報記憶手段の内容を更新
する更新手段と、前記有効情報記憶手段の任意の有効情
報をリセットする手段と、そのリセット時にリセットさ
れた有効情報に対応する記憶ブロックの前記優先順位指
示情報を最も低い優先順位とするように前記優先順位指
示情報記憶手段の内容を更新する更新手段と、前記デー
タ記憶手段に記憶されたデータを他のデータと入れ換え
るために前記優先順位指示情報記憶手段に記憶された優
先順位指示情報だけにより最も低い優先順位の記憶ブロ
ックをデータの入れ換えを行なうべき記憶ブロックとし
て決定する手段とを備えたことを特徴とするバッファメ
モリ装置が得られる。

次に本発明について図面を参照しながら詳細に説明する
。

まず、本発明で用いられる置換アルゴＩＪズムについて
、４個のブロックからなるバッファの場合について説明
する。

第１図におけるメモリ１は２５６×４のブロックを持つ
データ記憶用のメモリで、メモリ２は２５６の各ワード
に対して６ビットのＬＲＵ制御ビット（すなわちブロッ
ク単位の優先順位を示す優先順位指示情報）を記憶する
メモリである。ＬＲＵ制御ビットは４個の各ブロック内
データがアクセスされた時間的な関係を示すビットで、
ある制御ビットｌｉｊ（ここでｉおよびｉはブロック番
号を意味する）についてみると、制御ビットｌｉｊ＝論
理い１″のとき、フロツクｉのデータがブロックｉのデ
ータよりも後にアクセスされたことを示し、制御ビット
ｌｉｊ＝論理”０″のとき、ブロックｉのデータがブロ
ックｉのデータよりも以前にアクセスされたことを示す
。

この６ビットのＬＲＵ制御ビット、ｌｏ，，ｌｏ２，ち
３，１，２，１，３および１豹により４個のブロックの
参照された順序を表わすことができるが、あるブロック
を他のブロックよりも後でアクセスされたことを示す、
すなわち最高位の優先度を示すように書替える方法、お
よび逆にあるブロックを最も低い優先度を示すように書
替える方法を第２図を参照しながら説明する。

第２図において、４個のブロックのうち、ある＊ブロッ
クを最も高い優先度を持つように設定するには、そのブ
ロック番号の行方向のビットを論理”１″に、列方向の
ビットを論理け０″に書替えることにより実現できる。

たとえば、ブロック１を最高位の優先度に設定するには
、行方向のビット１，２および１，３を論理”１″に、
列方向のビットＬ，を論理ぃ０″に書替える。反対に、
あるブロックを最も低い優先度を持つように設定するに
は上記とは逆に、そのブロック番号の行方向のビットを
論理”０″に、列方向のビットを論理”１″に書替える
ことにより実現できる。

各ブロックに対して、そのブロックを最高位に設定する
場合、および最低位に設定する場合に更新すべきＬＲＵ
制御ビットの関係を以下に示す。

次に新規データを本バッファに登録するとき、４個のブ
ロックのいずれかのデータを追い出さなければならない
が、その追い出し優先度の最も高いブロック、すなわち
、最も低い優先度を持つブロックを検出する論理式を以
下に示す。フロツク０＝Ｌ．・１の・１。

３ ブロック１＝Ｌ．・１８・１，３ フロツク２＝し２・１，２・１２３ フロツク３＝Ｌ３・１，３．１２３ 第３図は本発明の一実施例を示す図である。

本実施例は４レベルのセットアソシェィティブ方式のキ
ャッシュメモ川こついて示している。第３図において、
メモリ３２は主記憶装置６上のデータをブロック単位で
記憶するデータ記憶メモリで２５６セット×４コンバー
トメントのエントリを持っている。メモリー４はメモリ
３２の各ェントリに対応して、そのブロックデータの有
効性（すなわちブロックデータがメモリ３２に格納され
ているかどうか）を示す有効ビットとブロックデータの
主記憶装置上のアドレスを記憶するためのメモリで、有
効ビットが論理ｕｌ″の時に、データ記億メモリ３２の
対応するブロックにデータが格納されていることを示す
。メモリ２３はメモリ１４および３２の各セットに対応
して４個のブロック間の優先順位を示す６ビットのＬＲ
Ｕビットを記憶するメモリである。中央処理装置４から
のキャッシュメモリのアクセスはパス１００１こよるア
ドレス情報と書込みアクセスの場合はパス１０１による
書込みデータとにより行なわれる。

中央処理装置４からのアクセス動作について説明する。
中央処理装置４からの議出しアクセスの場合、パス１０
０上のアドレス情報はしジスタ１０‘こセットされ、そ
の下位ビット２０２が選択回路１２により選択され、パ
ス２０５によりメモリ１４のアドレスとして与えられ、
メモリ１４の議出しを行なう。メモリ１４から読出され
た４個の各ブロックに対する有効ビットとアドレス情報
はパス２１０，２１１，２１２および２１３は比較回路
１５，１６，１７および１８に入力される。各比較回路
の他方の入力にはしジスタ１０の上位ビットがパス２０
１により入力されており、両データが比較される。メモ
ＩＪ１４からの議出しデータの有効ビットが論理い１″
で、かつ、そのアドレス情報とパス２０１の内容が等し
いとき、そのブロックに中央処理装置４からアクセスさ
れたデータが記憶されている（キャッシュヒットと称す
る）ことを意味し、比較回路の出力２１４〜２１７の対
応する信号が論理ぃ１″となる。

すべての比較回路で上記一致がとれないとき（キャッシ
ュミスヒットと称する）はメモリ３２に目的のデータが
記憶されていないことを示し、主記憶装置６に対する読
出しアクセスを行なう。

メモリ３２のアクセスは／ぐス２０２のアドレスにより
上記動作とは並行して行なわれ、各ブロックの出力デー
タはパス２３２〜２３５により選択回路３３に入力され
ている。キャッシュヒットの場合、パス２１４〜２１７
のデータは選択回路１９により選択され、レジス夕２０
もこセットされると共に、選択回路３３においてパス２
３２〜２３５のデータのうちヒットしたブロックデータ
を選択し、パス２３６によりレジスタ３４にセットする
。

レジスタ３４のデータはパス１０２により中央処理装置
４に送られる。キャッシュヒットの場合、４ビットのレ
ジスタ２０‘こはヒットしたブロックに対するビットの
み論理い１″で、他のビットは論理い０″のデータがセ
ットされており、そのヒットしたブロックを最も最近に
参照されたことを示すための最高位の優先度を持つよう
にメモリ２３のＬＲＵビットの更新処理を行なう。そこ
で、ＬＲＵメモリ制御回路２２においてはしジスタ２０
の内容により論理い１″のブロックを最高位優先度とな
るよう先に述べたアルゴリズムにしたがってメモリ２３
の書込みデータを発生し、レジスタ２１のアドレス情報
で示されるメモリ２３のアドレス位置に書込む。

中央処理装置４からの読出しアクセスによりキャッシュ
ヒットとなった場合は常に上記動作により参照されたブ
。

ックを最高位の優先度となるように設定する。キャッシ
ュミスヒットの場合はしジスタ１０のアドレス情報を選
択回路３５により選択し、レジスタ３６を介して主記憶
装置６に送り、主記憶装置に対する議出しアクセスを行
なう。

本アクセスにより主記憶装置６からの議出しデータがバ
ス１０５により送られてくると、選択回路３０により選
択し、レジスタ３１にセットするとともに、パス２３０
から選択回路３３を介してレジスタ３４にセットし、パ
ス１０２により中央処理装置４に送る。

主記憶装置６からの議出しデータは中央処理装置４に送
ると共に、メモリ３２にも格納する。このとき、データ
の格納は４個のフロツクのうちメモリ２３内のＬＲＵビ
ットにより最も低い優先度を持つブロックすなわち最も
以前に参照されたブロック位置に対して行なう。中央処
理装置４からのアクセス要求のアドレスはしジスタ１０
およびレジスタ２１に保持されており、パス２２５のア
ドレスにより読出されたメモリ２３のＬＲＵビットはし
ジスタ２４にセットされ、その内容により追い出しブロ
ック検出回路２５で最も低い優先度のブロックを決定す
る。追い出しブロック検出回路の出力は迫に出すブロッ
ク位置に対するビットのみ論理”１″となっており、パ
ス２２４により選択回路１９を介してレジスタ２川こセ
ットされる。レジセタ２０の内容はパス２２０によりメ
モリ１４、メモリ３２およびＬＲＵメモリ制御回路２２
に入力されており、各メモリの更新処理に用いられる。
まずメモリ３２においてはパス２０２のアドレスとパス
２２０のブロック位置状報で示されるブロックに対して
レジスタ３１の主記憶装置６からの議出しデータを書込
む。

メモリ１４ではパス２０５のアドレスとパス２２０で示
されるブロックに対してパス２０１の上位アドレス情報
を書込み、有効ビットは論理”１″を書込む。

メモリ２３に対しては、上記データを登録したフロック
を最高位の優先度を持つように設定するため、キャッシ
ュヒットの場合と同様に、ＬＲＵメモリ制御回路２２に
より設定データを発生し、メモリ２３に書込む。

中央処理装置４からのアクセスに対しては以上に示した
ごとく、キャッシュメモリの最も最近に参照したブロッ
クに対するＬＲＵビットの優先度を最高位に設定し、新
たにデータを登録する場合には最も優先度の低いブロッ
クのデータを追い出して新データを登録している。

次にブロック無効化制御部５からの要求に対する動作を
示す。

ブロック無効化制御部５はメモリ１４と構造が等しく、
その内容の写しを記憶するメモリを持っており、両メモ
リは常に内容が一致するように制御されている。

またブロック無効化制御部５はマルチプロセッサを構成
する他の中央処理装置が主記憶装置６に書込みアクセス
を行なった時に送ってくる主記憶アドレスを受取り、制
御部５内のメモリを検索し、もし、その主記憶アドレス
で示されるブロックが登録されていると、そのブロック
を無効とするための要求をパス１０３によりバッファメ
モリ装置３に対して送ってくる。フロック無効化制御部
５の動作は本発明とは関係が無いため省略する。

パス１０３には無効とすべきブロック位置を示すアドレ
ス情報と、そのブロック位置に対するビットだけ論理ぃ
１″となっている４ビットのデータを含んでおり、レジ
スタ１１にセットされる。

レジスタ１１のアドレス情報部３０３は選択回路ｊ２で
選択されパス２０５によりメモリ１４のアドレスを指定
すると共に、レジスタ２１にセットされ、パス２２５に
よりメモリ２３のアドレスを指定する。ブロック位置情
報はパス２０４により有効ビット制御回路１３に入力さ
れ、かつ、選択回路１９を介してレジスタ２０１こセッ
トされる。メモリ１４においては制御回路１３において
パス２０４の論理ぃ１″のブロック位置に対する入力デ
ータとして論理”０′′のデータを発生し、書込み処理
を行なうことにより、指定されたブロック位置の有効ビ
ットをリセットする。ＬＲＵメモリ制御回路２２におい
てはしジスタ２０の内容により論理、、１″のビット位
置のブロックを最も低い優先度に設定するためのデ−夕
を先に示したアルゴリズムにより発生し、メモリ２３の
更新処理を行なう。

本処理によりデータが無効となった、すなわちデータの
登録されていないブロックは他のブロックに比べて最も
優先度が低くなり、中央処理装置からのアクセスにより
主記憶装置６からのデータを登録するときはデータの登
録されていない空のブロックが優先的に使用されること
になる。

次にＬＲＵメモリ制御回路２２によるメモリ２３の更新
動作および追い出しブロック検出回路２５の構成を第４
図を参照しながら説明する。第４図において、メモリ２
３は各ＬＲＵビット単位に書込み動作が行なえるメモリ
セル２３０１，２３０２，２３０３，２３１２，２３１
３および２３２３により構成され、各メモリセルはＬＲ
Ｕビットｌｏ，，ｌｏ２，ｌｏ３，１，２，１，３およ
び１２３をそれぞれ記憶している。各メモリセルはパス
２２５のアドレス情報とパス２２１６の書込み制御信号
と各メモリセル毎に入力される入力データ信号２２１×
１（×＝０〜５）と書込み有効信号２２１×２とにより
制御される。たとえばメモリセル２３０１についてみる
と、書込み制御信号２２１６が論理リ１″で、かつ書込
み有効信号２２１０２が論理”１″だとパス２２５のア
ドレス位置に入力データ信号２２１０１の内容が書込ま
れる。

書込み制御信号２２１６は書込み信号Ｌ２２６０１と書
込み信号日２２６０２のいずれかが論理い１″になった
時、書込みパルス２２６０３が論理ぃ１″のタイミング
で発生する。

信号Ｌ２２６０１はしジスタ２０で示すブロック位置を
最も低い優先度に設定することを指定する制御信号でブ
ロック無効化制御部５からの要求により発生し、信号日
２２６０２はしジスタ２０で示すブロック位置を最高位
の優先度を持つように設定することを指定する制御信号
で中央処理装置４からのアクセスにより発生する。レジ
スタ２川こは優先度を変更するブロックに対するビット
だけが論理い１″であるブロック指定ビットが設定され
ており、信号Ｌ２２６０１または信号日２２６０２によ
り書込み制御信号２２１６が論理い１″となった時、レ
ジスタ２０の内容によりゲート２２×１（×＝０〜５）
および２２×２部で入力データと書込み有効信号が決定
され対応する書込み動作が行なわれる。

いま信号Ｌ２２６０１による書込み動作についてみると
、この時レジスタ２０の内容が”０１００″であると、
ゲート２２０２，２２３２および２２４２の出力２２１
０２，２２１３２および２２１４２が論理い１″となり
メモリセル２３０１，２３１２および２３１３に対して
書込み動作が行なわれる。

このとき、各メモリセルの入力データはゲート２２０１
，２２３１および２２４１で信号Ｌ２２６０１との排他
的ＯＲが取られるため２０からのデータの負論理が各メ
モリセルの入力データとなる。

すなわち信号２２１０１は論理い１″に、信号２２１３
１と２２１４１は論理い０″になりメモリセル２３０１
，２３１２および２３１３に論理い１″，”０″，い０
″がそれぞれ書込まれ、本パターンは先に示したごと〈
ブロック１を最も低い優先度を持つように設定するもの
である。

レジスタ２０が他のブロックを指定した場合も上記同様
に、そのブロックを最も低い優先度を持つようにＬＲＵ
メモリの書込み動作を行なう。

次に書込み信号日２２６０２による書込み動作の場合に
は書込み有効信号発生用のゲートは上記同様に動作し、
入力データ発生用のゲ−ト２２×１はその入力２２６０
１が論理ぃ０″であるため、レジス夕２０の入力状態が
そのまま各メモリセルの入力データとなる。レジスタ２
０の内容が上記同様い０１００″の場合についてみると
、メモリセル２３０１，２３１２および２３１３の入力
データはい０１１″となり、先に示したごとくブロック
ーを最も高い優先度を持つように設定する。

追い出しブロック検出回路２５の構成は第４図に示すご
とく、レジスタ２４の内容だけで非常に簡単に構成され
る。第４図で信号２２４０が論理”１″の時はブロック
０が、信号２２４１が論理い１″の時はブロックーが、
信号２２４２が論理い１″の時はブロック２が、信号２
２４３が論理”１″の時はブロック３が追い出すべきブ
ロックであることを示す。

以上示したごとく、あるブロックを最高位の優先度を持
つように設定するための回路と、最も低い優先度を持つ
ブロックを追い出しブロックとして検出する回路は非常
に簡単に、かつ、少ないハードウェア量により実現でき
る。

本実施例ではキャッシュメモリの場合について示したが
、本発明はＴＬＢ等のバッファメモリにおいてＬＲＵの
暦換えアルゴリズムを適用したバッファメモリ制御に対
して簡単に適用できる。

本発明は以上説明したようにブロックデータを無効とし
たとき、そのブロック位置を最も低い優先度に優先順位
指示情報（ＬＲＵビット）を設定するように構成するこ
とにより、新規データを登録するときの追い出しブロッ
クを決定する手段を非常に簡単に、かつ少ないハードウ
ェアにより実現できるという効果がある。

【図面の簡単な説明】

第１図は４レベルのバッファメモリと対応するＬＲＵメ
モリを示す図、第２図は４個のブロックから構成される
バッファに対するＬＲＵビットのマトリクス図、第３図
は本発明の一実施例を示すキャッシュメモリの構成を示
すブロック図、第４図は第３図におけるＬＲＵメモリ２
３、ＬＲＵメモリ制御回路２２および追い出しブロック
検出回路２５の詳細な構成を示す図である。 第１図から第４図において、１……バッファメモリ、２
……ＬＲＵメモリ、３…・・・バツフアメモリ装置、４
・・・・・・中央処理装置、５・・・・・・フロツク無
効化制御部、６・・・・・・主記憶装置、１０，１１，
２０，２１，２４，３１，３４……レジスタ、３２．．
・．．・キャッシュメモリ、１４・・…・アドレス、有
効ビット格納用メモリ、２３…・・・ＬＲＵメモリ、１
３・・・・・・有効ビット制御回路、１２，１９，３０
，３３，３５・・・・・・選択回路、１５，１６，１７
，１８……比較回路、２２……ＬＲＵメモリ制御回路、
２５・・・…追い出しブロック検出回路、２２０１，２
２０２，２２１１，２２１２，２２２１，２２２２，２
２３１，２２３２，２２４１，２２４２，２２５１，２
２５２，２２６１，２２６２，２５０，２５１，２５２
，２５３・・…・論理ゲート、２３０１，２３０２，２
３０３，２３１２，２３１３，２３２３……メモリセル
、１００，１０１，１０３〜１０５，２００〜２０６，
２１０〜２１８，２２０〜２２５，２３０〜２３６，２
４０，２２００〜２２０３，２２１×１（ｘ＝０〜５）
，２２１×２，２２６００〜２２６０３，２２１６，２
２２０〜２２２５，２２３０〜２２３５，２２４０〜２
２４３……接続ライン。 第１図 第２図 第３図 図 寸 鮭

Claims (1)

【特許請求の範囲】
1. １ ブロツク単位の記憶領域を有するデータ記憶用のデ
   ータ記憶手段と、このデータ記憶手段の各ブロツクに対
   応してデータが前記データ記憶手段に格納されている場
   合を示す有効情報を記憶する有効情報記憶手段と、前記
   データ記憶手段の記憶位置に対応した前記ブロツク単位
   の優先順位を示す優先順位指示情報を記憶する優先順位
   指示情報記憶手段と、データがアクセスされた時に前記
   データ記憶手段内のアクセスされた記憶ブロツクに対応
   する前記優先順位指示情報を最優先順位とするように前
   記優先順位指示情報記憶手段の内容を更新する更新手段
   と、前記有効情報記憶手段の任意の有効情報をリセツト
   する手段と、そのリセツト時にリセツトされた有効情報
   に対応する記憶ブロツクの前記優先順位指示情報を最も
   低い優先順位とするように前記優先順位指示情報記憶手
   段の内容を更新する更新手段と、前記データ記憶手段に
   記憶されたデータを他のデータと入れ換えるために前記
   優先順位指示情報記憶手段に記憶された優先順位指示情
   報だけにより最も低い優先順位の記憶ブロツクをデータ
   の入れ換えを行なうべき記憶ブロツクとして決定する手
   段とを備えたことを特徴とするバツフアメモリ装置。