JPH0313616B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明はバツフア記憶方式をとる情報処理装置
におけるバツフア・ストレージのリプレース制御
方式に関する。

〔発明の背景〕

バツフア記憶方式をとる情報処理装置におい
て、主記憶装置内のデータの写しを格納しておく
バツフア・ストレージのリプレースメント・アル
ゴリズムは、一般にLRU（Least Recently
Used）制御方式が用いられる。この方式は、バ
ツフア・ストレージ内の或るブロツクの内容を主
記憶装置から送られてきた新しいデータで置き換
える場合、該当ブロツク内の最古にアクセスされ
たデータを追い出すというものである。この
LRU制御方式を用いた場合、バツフア・ストレ
ージの或るブロツクが参照されると、リプレース
メント・アレイ（バツフア・ストレージ内のブロ
ツクのリプレースされる優先順位を格納しておく
アレイ）には、該当ブロツクのリプレース優先順
位が最低になる情報が書込まれる。

ところで、システムによつては、バツフア・ス
トレージは演算処理装置（CPU）と入出力チヤ
ネル（CH）の両方からアクセス可能である。こ
のチヤネルが大容量のデータを転送するような場
合、最後のデータを転送すべくバツフア・ストレ
ージの或るブロツクを参照すると、以後、該ブロ
ツクの参照される可能性は極めて少ない。この場
合、LRU制御方式を採用すると、この参照され
る可能能性の極めて少ないブロツクのリプレース
優先順位が最低に設定されるため、バツフア・ス
トレージのリプレース時、該ブロツクのリプレー
スされる確率が低下し、参照される可能性の高い
ブロツクがリプレースされることになり、バツフ
ア・ストレージのヒツト率を低下させる。

従来、かゝる問題を解決する方法の一つに、演
算処理装置がバツフア・ストレージをアクセスす
る場合は該当ブロツクのリプレース優先順位を最
低に設定し、入出力チヤネルがアクセスする場合
は逆に最高に設定する方式がある（特願昭51−
131740号）。しかし、この従来方式は、チヤネル
がバツフア・ストレージをアクセスした場合、一
義的に該当ブロツクのリプレース優先順位を最高
にするというものであり、チヤネルが近い将来に
更び参照する必要のあるデータまでもリプレース
される欠点がある。

〔発明の目的〕

本発明の目的は、上記従来方式の欠点を解決し
て、バツフア・ストレージのヒツト率を更に向上
させる融通性に富むリプレース制御方式を提供す
ることにある。

〔発明の概要〕

本発明は、一連のデータ転送処理において、バ
ツフア・ストレージの或るブロツクに対する最終
アクセスであり、近い将来に該ブロツクを更びア
クセスする予定がない場合、該当ブロツクリプレ
ース優先順位を最高にして、積極的に該ブロツク
をリプレースするものである。

〔発明の実施例〕

以下、本発明の一実施例について図面により詳
細に説明する。

第１図はバツフア記憶方式の概念図で、主記憶
装置とバツフアメモリの間に中間バツフア（ワー
ク・ストレージ）を持つ３レベルのメモリ階層を
形成した例を示す。第１図において、１０１は主
記憶装置（MS）であり、その記憶内容の一部の
写しがワーク・ストレージ（WS）１０２に格納
される。このWS１０２を演算処理装置（CPU）
１０３，１０４及び入出力チヤネル（CH）１０
５で共用する。CPU１０３，１０４には高速バ
ツフアメモリ（BS）があり、WS１０２のデータ
の一部が格納される。CPU１０３，１０４はメ
モリアクセスが発生すると、自装置内のBSを参
照し、目的のデータがBSにあれば、該BSより直
ちに取得し、なければWS１０２から読み出す。
又、WS１０２にも目的のデータがない場合は、
MS１０１より当該データを含むブロツクをWS
１０２に転送し、該WS１０２からあらためて読
み出す。CH１０５についてもほゞ同様である。

第２図にWSとそのアドレス・アレイ（WAA）
及びリプレースメント・アレイ（WRA）を示
す。WS１０２は多数のカラムに分かれ、１つの
カラムには複数のローが存在する。第２図は４ロ
ー構成の場合を示す。１ローの大きさは例えば16
バイトからなり、MS１０１の連続した16バイト
のデータを格納することができる。MS１０１も
該WS１０２と同様のカラムに分かれるが、各カ
ラムに含まれるロー数は、該MS１０１の記憶容
量によつて異なる。このMS１０１の各カラムに
含まれるロー群のうち、任意の４つのローのデー
タがそれぞれWS１０２の対応するカラムの４ロ
ーのうちのどれか１つに格納される。

WAA１０２−１は、WS１０２に格納されて
いるデータのMS１０１上のアドレスを登録して
おくもので、カラム、ローともにWS１０２の同
じカラム、ローに対応している。WRA１０２−
２は、WS１０２の各カラム対応にリプレースす
べきローの優先順位を覚えておくものである。後
述するように、４ロー構成の場合、WRA１０２
−２は各カラム毎に６ビツトで構成される。

第２図において、例えばWS１０２のカラムＢ
に属するアドレスに対するメモリアクセスで
“Not in WS”が発生した場合、WRA１０２−
２の該当カラムの内容により、４つのロー（B0，
B1，B2，B3）中の追出すべきローを決定し、
WS１０２のカラムＢの該当ローにMS１０１か
ら読み出した新しいデータを格納する。同時に、
WAA１０２−１のカラムＢの該当ローに新デー
タのMS上のアドレスを登録し、WRA１０２−
２の該当カラムの内容を更新する。

WRA１０２−２の更新アルゴリズムはLRU方
式が一般によく使用されており、各カラム毎に、
アクセスされたローのリプレース（WS１０２か
ら追出す）される優先順位が最も低くなるように
更新されるが、本発明では、メモリアクセスが
WS１０２の該当ローに対する最終アクセスで、
以後、該ローの参照される可能性が極めて少ない
場合、該ローのリプレース優先順位が最高となる
ように更新するものである。

第３図はWSが第２図の如き４ロー構成の場合
のリプレースアルゴリズムを説明する図である。
第３図において、０〜３はロー番号を示し、
WRA１０２−２はこの０〜３を結ぶ６本の線に
対応したア〜カの６ビツトのリプレース優先順位
決定情報を各カラム毎に有する。０〜３の各ロー
に着目するに、各ロー共、ア〜カの６本のうち３
本が集まつており、それらの矢印が最も多く向い
ているローがリプレース優先順位が最高であるこ
とを示している。WSの或るカラムの例えばロー
０がアクセスされた場合、通常は該ロー０に集ま
つている３本の線ア、エ、オの矢印を自分とは反
対側に向ける。これにより、該ロー０のリプレー
ス優先順位は最低となる。このロー０に集まつて
いないイ、ウ、カの線の矢印の向きは変えない。
第３図ａはこの場合を示したものである。一方、
ロー０に対するメモリアクセスはこれで最後であ
り、近い将来に該ローを再びアクセスする予定が
ない場合、ロー０に集まつている３本の線ア、
エ、オの矢印をいずれも自分の方に向ける。これ
により、該ロー０のリプレース優先順位が最高に
なる。第３図ｂはこの場合を示したものである。

次に具体例により説明する。第４図はCHが
MS上のＳ番地からＥ番地までの連続したアドレ
スについてアクセスする時、従来方式を実施した
場合のMSとWAAの関係を示したものである。
第４図において、MS１０１上の破線はカラム境
界である。又、WAA１０２−１内のアドレスは
便宜上、左によせているが、一般には４つのロー
にランダムに分散している。

さて、CA０〜CZ０のカラムに対するCHから
のメモリアクセスが全て終了した状態に注目した
場合、従来方式においては、WRAはWAA１０
２−１の各カラムについて、リプレースの最高優
先順位としてCA０〜CZ０の登録されたロー０を
指しているとは限らない。従つて、CA１〜CX１
のカラムがアクセスされると、そのアドレスは、
CA０〜CX０をリプレースせずに、別のローに登
録されることがある。第４図はCA０〜CX０がロ
ー０に残つた状態で、CA１〜CX１がロー１に登
録された例を示している。

こゝで、高速の半導体メモリフアイルなどが使
用される場合を考えると、最悪のケースは、WS
のデータが全てCHの入出力によるデータに置き
換えられてしまうこともあり得る。ところがCH
のアクセスするデータは、一般にCHが一担デバ
イスに書込んだり、メモリに書込んだりした後は
WS上に留まつている必要はないものである。こ
のように、WS上に残つている必要のないCHの
アクセスデータが残つていると、WS上に残つて
いてほしいCPUの使用データを追い出してしま
う不都合が生じる。

第５図は同じくCHがMS上のＳ番地からＥ番
までの連続したアドレスについてアクセスする
時、本発明を実施した場合のMSとWAAの関係
を示したものである。第５図において、CA０Ｅ
〜CW１Ｅは各カラムの最終アドレスを示す。

CHからのメモリアクセス時、本発明では次の
原則にしたがつてリプレースの優先順位を決め
る。

(1) 各カラムの最終アドレスCA０Ｅ〜CW１Ｅ
では、WAA１０２−１のリプレース優先順位
を通常のアクセスとは逆にCA０〜CW１の登
録されたローが最高位となるようにWRAを更
新する (2) カラムの途中であつても、ＥのようにCHリ
エストの最終アクセスでは、(1)と同様にCX１
の登録されたローが最高位となるようにWRA
を更新する。

(3) 上記(1)，(2)以外のアクセスでは通常通りのリ
プレース優先順位とし、アクセスされたローが
最低位となるようにWRAを更新する。

従つて、CA０〜CZ０のカラムに対するCHか
らのメモリアクセスが全て終了した場合、WAA
１０２−１の各カラムについて、リプレースの最
高優先順位はCA０〜CZ０の登録されたロー０を
指している。このため、次にCA１〜CX１のカラ
ムがアクセスされると、そのアドレスは、それぞ
れCA０〜CX０をリプレースして、WAA１０２
−１の各カラム共ロー０に登録される。しかも、
WAA１０２−１の各カラムについて、CA１〜
CX１の登録されたロー０のリプレース優先順位
は、これ又、最高位に指定されている。リプレー
スされないで残つているCYO、CZOのリプレー
ス優先順位も最高位となつている。従つて、WS
のデータが全てCHの入出力によるデータに置き
換えられることはなく、CPUの使用しているデ
ータをWSから追い出す量が低減される。又、例
えばCBOカラムのアクセス途中では、WAA１０
２−１の該当ローは最低位のリプレース優先順位
となつているため、アクセスが全て終了していな
いCBOカラムがCPUのWSアクセスによつて追い
出されることはない。

第６図はMS上のＳ番地からＥ番地までアドレ
ス逆方向に、CHによるデータ転送が発生した場
合の本発明によるMSとWAAの関係を示したも
のである。この場合は、各カラムの先頭アドレス
CX１Ｓ、CSW１Ｓ、…CB０Ｓ及びCHによる最
終リクエスト・アドレスＥのアクセスでは、
WAA１０２−１の該当ローが最高位となるよう
にリプレース優先順位を指定し、その他のアクセ
スでは通常通りの最低優先順位を指定すればよ
い。これにより、CX１〜CA１に対するCHから
メモリアクセスが全て終了した時、WAA１０２
−１の各カラムについて、リプレースの最高優先
順位はCX１〜CA１の登録されたローを指定して
おり、このため、次にCZ０、CY０とアクセスさ
れた後、CX０〜CA０のカラムがアクセスされる
と、そのアドレスは、それぞれCX１〜CA１をリ
プレースしてWAA１０２−１の各カラムの該当
ローに登録される。

第７図は本発明のリプレース制御方式の一実施
例のブロツク図である。便宜上、第７図では
WAA、WRAの１つのカラムに対する構成のみ
を示す。第７図において、７０１はWSの或るカ
ラムでアクセスされるロー番号に対応するラツチ
群で、その４本の出力線７０５のうち、“in WS”
となつたローに対する１本のみが“１”となる。
エンコーダ７０２は第３図ａのアルゴリズムにも
とづき、ア〜カの書込みデータ（Ｄア〜Ｄカ）７
０６と書込み信号（Ｗア〜Ｗカ）７０７のうち、
“in WD”となつたローに関係するものを“１”
とする。エンコーダ７０２の書込データＤア〜Ｄ
カはインバータ７０３を経由してリプレースメン
ト・アレイ部７０４に入力される。インバータ７
０３は、リプレース最高優先順位指定信号（HP
信号）７０９が“１”のときには、入力データ７
０６を反転して出力データ７０８とし、HP信号
７０９が“０”のときには入力データ７０６をそ
のまま出力データ７０８とするものである。リプ
レースメント・アレイ部７０４では、インバータ
７０３からの出力データ７０８のうち、書込み信
号７０７が“１”となつているビツトについての
み書き込みが行なわれる。即ち、第７図の構成と
することにより、HP７０９が“０”のときには
第３図ａの通常のLRUリプレースメント・アル
ゴリズムが実行され、HP７０９が“１”のとき
には、これとは逆の第３図ｂに示すリプレースメ
ント・アルゴリズムが実行される。

第８図はHP信号の生成論理を示したものであ
る。第８図では、メモリのカラムサイズは256バ
イトからなり、メモリアドレス情報は０〜31ビツ
トの32ビツト構成をとり、CHのアクセスは８バ
イト単位で行うと仮定している。従つて、アドレ
ス情報の24ビツトがカラム境界、29ビツトが８バ
イト境界を表わし、24〜28ビツトがオール“１”
の場合、該アドレスはカラムの最終８バイトを示
し、オール“０”の場合は先頭８バイトを示す。

第８図において、CHからMSに対する読出し
あるいは書込みリクエストが発生すると、オア回
路８０１の出力が“１”となる。アドレス情報の
24〜28ビツトはラツチ回路８０２〜８０６にラツ
チされ、それらがオール“１”の場合はアンド回
路８０７の出力が“１”となり、オール“０”の
場合はアンド回路８０８の出力が“１”となる。
メモリのアドレス順方向にデータ転送が行われる
場合（FORWARD）、オア回路８０１とアンド
回路８０７の出力がいずれも“１”の時、アンド
回路８０９の出力が“１”となり、オア回路８１
１を介してHP信号７０９は“１”となる。これ
は第５図でCA０Ｅ〜CW１Ｅをアクセスした場
合に該当する。又、メモリのアドレス逆方向にデ
ータ転送が行われる場合（BACK）、オア回路８
０１とアンド回路８０８の出力がいずれも“１”
の時、アンド回路８１０の出力が“１”となり、
オア回路８１１を介してHP信号７０９は“１”
となる。これは第６図でCB０Ｓ〜CX１Ｓをアク
セスした場合に該当する。更に、当該データ転送
の最終アクセスを示す信号（LAST ACC）が出
される場合も、オア回路８１１を介してHP信号
７０９は“１”となる。これは、第５図ではＥ、
第６図ではＳをアクセスした場合に該当する。

以上、CPUによるアクセスは従来通りの優先
順位とし、CHによるメモリアクセスの場合には
逆にする場合について説明したが、CPUのメモ
リアクセスにおいても、あるカラム、ブロツクに
対する最終アクセスで、以後、該カラム、ブロツ
クが参照される可能性が極めて少ない場合には同
様に適用可能である。又、実施例ではWSのリプ
レースについて説明したが、BSでも同様である
ことは云うまでもない。

又、実施例は３レベルのメモリ階層を形成した
場合の中間バツフア（WS）のリプレースについ
て説明したが、第１図においてCPU１０３，１
０４内にBSを持たないような２レベルのメモリ
構成、あるいはCPU１０３，１０４内のBSを
CHがアクセスする場合にBSに適用する構成であ
つても同様である。

〔発明の効果〕

以上の説明から明らかな如く、本発明によれ
ば、一連のデータ処理において、あるブロツクに
対する最終アクセスであるか否か判断し、最終ア
クセスの場合、そのブロツクのリプレース優先順
位を最高順位にしておくことにより、近い将来に
更びアクセスする予定の無いブロツクが優先的に
バツフア・ストレージから追出されるため、有用
なブロツクの追出しが防止でき、バツフア・スト
レージの使用効率を一層高めることができる。

【図面の簡単な説明】

第１図はバツフア記憶方式の概念図、第２図は
バツフア・ストレージ（ワークストレージ）とア
ドレス・アレイとリプレースメント・アレイの関
係を示す図、第３図はリプレース・アルゴリズム
の説明図、第４図は従来方式によるアドレス・ア
レイの登録状態を示す図、第５図及び第６図は本
発明によるアドレス・アレイの登録状態を示す
図、第７図は本発明の一実施例のブロツク図、第
８図は第７図におけるリプレース最高優先順位指
定信号の生成論理の具体例を示す図である。 １０１……主記憶装置、１０２……ワークスト
レージ（バツフア・ストレージ）、１０３，１０
４……中央処理装置、１０５……入出力チヤネ
ル、１０２−１……ワークストレージ・アドレ
ス・アレイ、１０２−２……ワークストレージ・
リプレースメント・アレイ。

Claims (1)

【特許請求の範囲】
1. １ バツフア記憶方式をとる情報処理装置におい
   て、バツフア・ストレージのブロツク間のリプレ
   ース順位を示すリプレースメント・アレイを有
   し、バツフア・ストレージのアクセス時、当該ブ
   ロツクに対する最終アクセスか否か判定し、最終
   アクセスの場合は当該ブロツクのリプレース順位
   が最高位となるように前記リプレースメント・ア
   レイを更新し、それ以外の場合は最低位となるよ
   うに更新することを特徴とするバツフア・ストレ
   ージのリプレース制御方式。