JPS5856175B2 - バツフアメモリ制御方式 - Google Patents

Description

【発明の詳細な説明】 本発明はバッファメモリ制御方式に関し、特に、データ
のリプレースを行なう際に直前に主記憶からフェッチさ
れたブロックデータがリプレースの対象とならないよう
にしたバッファメモリ制御方式に関する。

バッファメモリのアドレスを、アクセスアドレスの下位
部分に対応する「セットアドレス、１と、アクセスアド
レスとは無関係な「ブロックアドレス−１とに分けて制
御するのが従来のセットアソシアティブ方式のバッファ
メモリであり、リプレース部が行うのはこの「ブロック
アドレス」の制御である。

主メモリよりバッファメモリにデータのコピーを入れる
時（これをブロックフェッチと呼ぶ）アクセスアドレス
に対応する１つのセットアドレスが決定される。

１つのセットアドレスには複数のブロックがありこのう
ち１つのブロックが１回のブロックフェッチで入れ替え
の対象となる部分である。

リプレース部はこの複数のブロックのうちから１つを選
択しデータの入れ替えの場所を指定する。

今、ブロックフェッチが行われ対応するセットアドレス
にある複数のブロックには全てデータがすでに入ってお
り空のブロックが１つもないとするとリプレース部では
その複数のブロックに入っているデータの全てについて
過去にアクセスがあった時の古さを調べ、最も古いデー
タの入っているブロックを入れ替えの対象ブロックとし
てそのブロックアドレスを指定する。

これをＬＲｕ法と言うのは周知のことである。

リプレースの入れ替え制御ビット、すなわちリプレース
メモリアレイに書込まれたビットをバッファメモリにア
クセスがあるたびにどの様に制御するかは、すでに知ら
れている。

完全なＬＲｕ法によって制御する場合１つのセットアド
レス部に対応するｎ個のデータブロックがあるとすれば
リプレース部は１つのセットアドレスに対しくｎ １
）ｎ／２ビツトの制御ビットラリプレースメモリに持つ
。

このうちの１ビツトはｎ個のブロックの中の２つのデー
タブロックの順序づけを示しており、１セツト分の全体
のビットはｎ個のデータブロックの配列すなわち順序づ
けを完全に示している。

今バッファメモリにアクセスがあったとするとそのアク
セスアドレスよりセットアドレスが決められ、そのセッ
トに対応するリプレースメモリの（ｎｌ）ｎ／２ビツト
が制御の対称として選択される。

このうちどこのデータブロックにアクセスがあったかと
いう通知によりその中の（ｎ−１）ビットが選択されて
そのデータブロックのアクセス順序が最新となる様に書
き変えられる。

これがリプレースの更新である。

この操作をくり返すことによりリプレースメモリは常に
全てのセットアドレスに対してｎ個のデータブロックの
アクセスの新しさ即ち古さの順序を記憶している。

ブロックフェッチの際アクセスアドレスよりセットアド
レスは決定されるのでリプレースメモリよりこの（ｎ−
１）ｎ／２ビツトの情報、即ちｎ個のデータブロック全
部のアクセスの古さの順序を示す情報が読み出される。

この中から最もアクセスの古いデータブロックのブロッ
クアドレスを取り出す論理は更新とは逆の論理である。

各ブロックアドレスに対応して、（ｎ−１）ｎ／２ビツ
トのリプレース情報のうちｎ−１ビツトの情報が割り当
てられており、更新の時の書込みパターンと全く逆即ち
全ビットを反転させたパターンの場合そのブロックが最
もアクセスの古いデータブロックである。

従って各ブロックごとに自分に割当てられたｎ１ビツト
がこの最古のパターンであるかどうかという論理を取れ
ばかならずどれか１つのブロックが該当する。

以上が従来からのリプレース制御ビットの働きである。

リプレースメモリより読出されたリプレース情報は１つ
のセットアドレスに対応するｎ個のデータブロックの全
ての古さの順序情報をもっている。

つまり各データブロックが何番目に古いか（即ち新しい
か）というｎ個全部の情報を含んでいる。

従って２番目あるいはｎ番目に古いデータブロックを取
出す回路も作ることがで□る。

例えば１セツトのブロックが４個の場合なら完全ＬＲｕ
ではｎ ＝ ４であるから（ｎ−４）ｎ／２６、従って
リプレース情報は６ビツトであり、各データブロックに
割当てられたビットはｎ−１−３ビツトである。

この６ビツトを各々Ｒｏｔ ２．ＲＯ２、Ｒｏ３ｔ Ｒ
１２ｔＲ１３７Ｒ２３として下表の様に定義すると、最
古の各ビ データ アクセス最新 割当てビットの各ビットパ ブロック パタ −ン ０Ｒｏ１．Ｒ０２，Ｒｏ３１１１０００ １Ｒ０１，Ｒ１２，Ｒ１３０１１１００ ２Ｒ０２，Ｒ１□、馬、 ００１ １１０３
ＲＯ３，Ｒ７３，Ｒ２３０００１１１ツトノくにンーン この場合ＲＯＩ Ｊ ＲＯ２Ｊ ＲＯ３ｊビットが全て
／、０“ならデータブロックびが最もアクセスの古いプ
ロ〃 ツクである。

２番目に古い場合の各ビットのパターンは、各データブ
ロックに割り当てられたビットが最古の場合に示すパタ
ーンとどれか１ビツトが反転しているパターンの場合で
ある。

例えばＲＯＩ 、ＲＯ２ｔ Ｒ０３が１００，０１０゜
００１ならデータブロック、α′が２番目アクセスの古
いブロックである。

同様に全ブロックの２番目に古い時の論理を作ることが
できる。

要するに完全ＬＲｕの場合釜ブロックに割当てられたｎ
−１ビツトのビットパターンが、最古の場合のパターン
と１ビツト異っていれば２番目、２ビツト異っていれば
３番目に古いことになり、ｎ−１ビット即ち全部具って
いればｎ番目に古い即ち最も新しくアクセスされたブロ
ックであることを示している。

以上の様に古いデータブロックでも取り出す論理を作る
ことが出来、従ってその回路も作成できる。

また完全ＬＲｕでない場合でもリプレース情報により１
セツトの全データブロックの順序が決定されるアルゴリ
ズムを持つ方式であればすべて同様に最古以外のデータ
ブロックを取出すことができ、むしろ論理としては簡単
になることが多い。

（ここで言うｎ番目に古いとはリプレースビットが表わ
すものを意味し完全ＬＲｕでない場合かならずしも真の
ｎ番目ではない） さてブロックフェッチの際、従来の方式ではブロックフ
ェッチしたデータをバッファメモリに書込む過程で、リ
プレースメモリアレイの内容も同時に書き変え、そのブ
ロックアドレスが最も新しくアクセスされた事を登録す
るようになっている。

この登録をリプレースの更新と言うがこれはブロックフ
ェッチのアクセスの終りの方のタイミングである。

にもかかわらずリプレースの読出しはブロックフェッチ
のアクセスが開始されるとすぐに行われ、あらかじめデ
ータを入れ替えるべきブロックの位置を記憶しておくよ
うになっている。

従。ってブロックフェッチのアクセスが連続して出され
た場合、１番目のアクセスによって指定された入れ替え
データブロックのアドレスと２番目のアクセスによって
指定されるブロックアドレスとは、リプレースメモリの
内容が更新されない限り同じアドレスが指定されてしま
う。

つまり全く同じ場所が入れ替えの対象となることになり
、１番目に主メモリより持って来られたブロックデータ
は、後で又使われる可能性力塙い（どもかかわらず２番
目の）゛ロ゛ンクデーク１こよりすぐ１こ上ぬりされ、
ｒ肖されてしまうこと（どなる。

すなわち従来の制御方式では同一のセットアドレスを示
すアクセスアドレスを持つブロックフェッチが連続して
出された場合、１番目のブロックデータはバッファメモ
リ上からすぐ１こｒ肖されてしまうという欠点があった
。

又、これをさけるために同一セットアドレスに対するブ
ロックフェッチは、前のブロックフェッチが完了するま
で、即ちリプレースメモリの内容が更新されて正しく次
のリプレースすべきブロックを決定できるようになるま
で待たすような方法もあったが、この場合待たせる分だ
け性能が低下することはさけられなかった。

本発明の目的は同一のセットアドレスを持つブロックフ
ェッチの連続アクセスの場合リプレースが最も古いデー
タブロックのみでなく２番目のアクセスの場合には２番
目あるいはｎ番目に古いデータブロックのアドレスを入
れ替え対象として指定することにより、１番目のアクセ
スが完了するまで２番目以降のアクセスを待たせたり、
先にフェッチしたブロックデータが重複書込みによって
消されるという欠点を解決し、性能を向上させることに
ある。

即ち成るブロックフェッチの結果としてリプレースメモ
リの内容を更新する以前に、同一セットアドレスに対し
て次のブ爾ツクフェッチが必要となった場合に現在ブロ
ックフェッチが進行中でその結果主メモリのデータを書
き込もう圭しているブロック位置を、次のブロックフェ
ッチの書き込み先ブロックとして指定しないようにする
ことにより性能改善を図ることを目的としている。

そして、上記目的を遠戚するために、本発明は、バッフ
ァメモリをアクセスするごとにリプレースメモリの内容
を更新してアクセスされたデータを含むブロックが最新
であることを記録し、必要とするデータがバッファメモ
リに存在しなかった場合はリプレースメモリの読出しデ
ータにもとづいて追い出すべきブロック番号を決定し、
新たなデータを当該ブロック番号のブロック位置へ主記
憶からブロック転送するバッファメモリ制御方式におい
て、 上記リプレースメモリの読出データに基づいて最古のデ
ータブロック番号を決定する第１のリプレー入決定回路
と、最古の次に新しいデータブロック番号を決定する第
２のリプレース決定回路とを有し、既に処理進行中のブ
ロック転送が無い場合は上記第１のリプレース決定回路
によってリプレースの対象となるブロック番号を決定し
、既に；処理進行中のブロック転送が有る場合は上記第
２のリプレース決定回路によってリプレースの対象とな
るブロック番号を決定することを特徴とする。

以下、本発明を実施例により説明する。

図は本発明による実施例のリプレース制御回路であり、
ン図中、１はリプレースメモリ部、２は最古のデータブ
ロックを決定する第１ＬＲＵ回路、３は２番目に古いデ
ータブロックを決定する第２ＬＲＵ回路、４はｎ番目に
古いデータブロックを決定する第ｎＬＲＵ回路、５は比
較回路、６は選択回路、７は第２レジスタ、８は第２レ
ジスタ、９は第ｎレジスタ、１０は最初のブロックフェ
ッチデータのバッファメモリ書込ブロック番号を指定す
る情報線、１１は２番目のブロックフェッチデータのバ
ッファメモリ書込ブ陥ツク番号を指定する情報線、１２
はｎ番目のブロックフェッチデータのバッファメモリ書
込ブロック番号を指定する情報線である。

リプレースメモリ部１から出力されるリプレース情報は
第１ＬＲＵ回路２、第２ＬＲＵ回路３、・・・・・・、
第ｎＬＲＵ回路４に同時に入力され、第１ＬＲＵ回路２
からは最古のデータブロック番号が出力され、第２ＬＲ
Ｕ回路３からは２番目に古いデータブロック番号が出力
され、以下同様にして、第ｎＬＲＵ回路４からはｎ番目
に古いデータブロック番号が出力される。

比較回路５は連続して発生するブロックフェッチのセッ
トアドレスを比較し、同一セットアドレスのものがある
か否かということおよび同一セットアドレスのものがあ
るとき同一のものがいくつあるかということを判別し、
選択回路６へ選択信号を送出するものである。

選択回路６は比較回路５からの選択信号；こもとづき、
第１ＬＲＵ回路２〜第ｎＬＲＵ回路４のいずれか１つと
、第ルジスタ７〜第ｎレジスタ９のいずれか１つとを選
択し、選択したＬＲＵ回路の出力を選択したレジスタに
送出する。

以前に発出されて未だ完了していないブロックフェッチ
がなく、最初のブロックフェッチである場合には、リプ
レースメモリ部１より出力されるリプレース情報にもと
づき第１ＬＲＵ回路２により得られる最も古いデータブ
ロックの位置情報が第２レジスタフ１こセットされる。

すなわち、比較回路５からの選択信号により選択回路６
は第１ＬＲＵ回路２の出力を第２レジスタフに導く。

一方、すでに発出されて未だ完了していないブロックフ
ェッチが存在し、その状態で２番目のブロックフェッチ
が発出された場合、前後のブロックフェッチのセットア
ドレスが比較回路５により比較される。

比較の結果両者のセットアドレスが一致しなかった場合
は、比較回路５からの選択信号により第１ＬＲＵ回路２
の出力が第２レジスタ８ヘセツトされる。

また、両者のセットアドレスが一致した場合は、比較回
路５からの選択信号により第２ Ｌ ＲＵ回路３の出力
が第２レジスク８ヘセツトされる。

同様１こして、以前の（ｎ−１）個のブロックフェッチ
が完了しない間にｎ番日のブロックフェッチが発生され
た場合、該ｎ番目のブロックフェッチのセットアドレス
が以前のいずれのセットアドレスとも一致しないとき第
１ＬＲＵ回路２の出力が第ｎレジスタ９ヘセツトされる
。

一方、１番目〜ｎ番目のブロックフェッチのセットアド
レスがすべて同一のとき第ｎＬＲＵ回路４の出力が第ｎ
レジスタ９ヘセツトされる。

これにより、重複するブロック転送の際、バッファメモ
リの同一のブロック位置が主記憶からのデータを入れる
場合として連続して指定されることはない。

本発明はすでに説明した様に従来の回路に２番目あるい
はｎ番目に古いテ゛−タブロ゛ンクをすブレース情報よ
り決定する回路を追加することにより同一セットアドレ
スの連続ブロックフェッチの除目−のエリアがバッファ
書込みブロックとして指定されることを防止してブロッ
クフェッチデータの消失を防ぐようにしたので、これに
より性能の向上、制御の簡略化を計ることができるとい
うすぐれた利点をもっている。

【図面の簡単な説明】

図は本発明による実施例のリプレース制御回路である。 図中、１はリプレースメモリ部、２〜４はＬＲＵ回路、
５は比較回路、６は選択回路、７〜９はレジスタ、１０
〜１２はバッファメモリ書込ブロック番号を指定する情
報線である。

Claims (1)

1. 【特許請求の範囲】 １ バッファメモリをアクセスするごとにリプレースメ
   モリの内容を更新してアクセスされたデータを含むブロ
   ックが最新であることを記録し、必要とするデータがバ
   ッファメモリに存在しなかった場合はリプレースメモリ
   の続出しデータにもとづいて追い出すべきブロック番号
   を決定し、新たなデータを当該ブロック番号のブロック
   位置へ主記憶からブロック転送するバッファメモリ制御
   方式において、 上記リプレースメモリの読出データに基づいて最古のデ
   ータブロック番号を決定する第１のリプレース決定回路
   と、最古の次に新しいデータブロック番号を決定する第
   ２のリプレース決定回路とを有し、既に処理進行中のブ
   ロック転送が無い場合は上記第１のリプレース決定回路
   によってリプレースの対象となるブロック番号を決定し
   、既に処理進行中のブロック転送が有る場合は上記第２
   のリプレース決定回路によってリプレースの対象となる
   ブロック番号を決定することを特徴とするバッファメモ
   リ制御方式。 ２ 既に処理進行中のブロック転送が有る場合でも該進
   行中のブロック転送と後続するブロックフェッチ要求の
   両アドレスのうち特定の部分の比較結果が不一致を示す
   場合は常に上記第１のリプレース決定回路に従ってリプ
   レース制御を行なうことを特徴とする特許請求の範囲第
   １項記載のバッファメモリ制御方式。