JPH04233643A - バッファメモリ用制御装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は「命令」タイプの情報及
び「データ」タイプの情報を区別する再構成可能パーテ
ィショニング手段と、記憶されている情報を少なくとも
１つの置換えアルゴリズムに従って現情報と置き換える
置換え手段とを具えるバッファメモリ用制御装置に関す
るものである。

【０００２】

【従来の技術】置換え法は現在の殆どのコンピュータに
使われている階層構造メモリ及び／又は仮想メモリを具
えるデータ処理システムに通用されている。これらの置
換え法はこのようなコンピュータのページメモリ（中央
メモリ）、キャッシュメモリ及びアドレス変換器　（ｔ
ｒａｎｓｌａｔｉｏｎ　Ｌｏｏｋ−ａｓｉｄｅ　Ｂｕｆ
ｆｅｒｓ　ＴＬＢ）　の制御に用いられている。

【０００３】階層構造メモリシステムはプロセッサと大
容量バックグラウンドメモリとを具えている。後者のメ
モリの本質的な低速度のために、プロセッサとバックグ
ラウンドメモリとの間に１以上の中間メモリレベルを介
挿する必要がある。一般に、メモリレベルがプロセッサ
に近づけば近づくほどその動作速度が速くなるが、その
記憶容量が小さくなる。この理由のために、各メモリレ
ベルはマスメモリ側の直前のレベルが含む情報の一部し
か含まない。これがため、プロセッサが特定のメモリレ
ベルに存在しないアドレスを供給する場合、メモリ管理
システムが下流レベルの情報をサーチし、その情報を原
アドレスレベルにロードする必要がある。しかし原アド
レスレベルが満杯の場合、メモリ管理システムが予め決
められた置換えアルゴリズムに従って当該レベルのメモ
リエレメントのうちの１つに存在する情報を除去しその
スペースに新しい情報を割り当てる必要がある。一般に
、プロセッサに最も有用な情報をプロセッサに最も近い
レベルに記憶する必要がある。これは遠く離れたレベル
の情報の取り出しは時間がかかるためである。

【０００４】同様の置換え問題が仮想メモリシステムに
おいて生ずる。各アクセス毎に仮想ページナンバを物理
ページナンバに変換するのを避けるために、使用された
数個の「仮想ページ、物理ページ」対をアドレス変換器
　（Ｔｒａｍｓｌａｔｉｏｎ　Ｌｏｏｋ−ａｓｉｄｅ　
Ｂｕｆｆｅｒｓ　ＴＬＢ）　と称されている小さなバッ
ファレジスタに保持しておく。新しいページがアドレス
されると、アドレス変換器から除去すべき１つのベージ
対を選択する必要がある。

【０００５】種々の置換えアルゴリズムが提案されてい
る（「”Ｃｏｍｐｕｔｉｎｇ　Ｓｕｒｖｅｙｓ”，　Ｖ
ｏｌ．１４，　Ｎｏ．３，　１９８２；　”Ｃａｃｈ　
ｍｅｍｏｒｉｅｓ”　Ａ．Ｊ．　Ｓｍｉｔｈ　著」参照
）　。最も代表的なアルゴリズムは次の３つである。Ｌ
ＲＵ　（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ）　
：このアルゴリズムは最も長い時間使用されてないメモ
リエレメントの内容を置換える。ＦＩＦＯ　（Ｆｉｒｓ
ｔ　Ｉｎ　Ｆｉｒｓｔ　Ｏｕｔ）　：このアルゴリズム
は最も長い時間存在しているメモリエレメントの内容を
置換える。ランダム：このアルゴリズムはランダムにメ
モリエレメントの内容を置換える。

【０００６】これらのアルゴリズムを、ミス率、即ちプ
ロセッサがアクセスしたアドレスが該当するメモリレベ
ルに存在しない割合を測定して比較すると、殆どの場合
ＬＲＵアルゴリズムが最良の結果を示すことが証明され
た。

【０００７】一般に、バッファメモリは命令も数値デー
タも格納する。ここでは「情報」なる語を、２つのタイ
プの情報、即ち「命令」又は「データ」を区別しないで
示すために用いる。バッファメモリの内容（その内容が
データと命令に割当てられる割合）は、入力端子に供給
されるアドレスを考慮するが使用情報のタイプは一般に
考慮しない置換えアルゴリズムに従って時間の経過につ
れて変化する。この理由のために最適な性能が得られず
、ミスを生ずるメモリアクセスの割合がかなり高くなる
。この結果は次のように説明することができる。多くの
プログラムの実行中、プロセッサによるメモリのアクセ
スは殆どが命令に関係し、データに関係するアクセスは
数個である。このような場合には、メモリ内に含まれる
データが命令により頻繁に置換えられ、これらデータを
再び使用する必要があるときこれらデータはメモリから
除去されているのでミスを生ずることになる。逆に、他
の所定のプログラムに対しては、メモリが多量のデータ
と極く僅かの命令を含むためにミス率が高くなり得る。

【０００８】命令とデータを区別してバッファメモリ内
の情報を管理する方法が「　”ＩＢＭＴｅｃｈｎｉｃａ
ｌ　Ｄｉｓｃｌｏｓｕｒｅ　Ｂｕｌｌｅｔｉｎ”；Ｖｏ
ｌ．２１，　Ｎｏ．２，　１９７８；　”Ｆａｓｔ　ｍ
ｅｍｏｒｙ　ｏｒｇａｎｉｚａｔｉｏｎ”，　Ｐ．　Ｆ
ａｖｒｅ　及び　Ｒ．　Ｋｕｈｎｅ　」に提案されてい
る。この方法は複数のモジュールから成るバッファメモ
リを用い、２つの情報バスによりこれらモジュールのい
くつかを命令に割当て、他のモジュールをデータに割当
てるものである。モジュール制御ユニットがこの割当て
を決定する。

【０００９】

【発明が解決しようとする課題】しかし、このような管
理方法には欠点がある。実際上所定の構成例では命令及
びデータにそれぞれ割当てられたバッファメモリの各セ
クションが固定容量であり、各モジュールは割当てられ
たタイプの情報しか受信できない。ところで、命令及び
データに対するアクセスの割合は実行するプログラムに
従って大きく変化し得る。この理由のために、殆どのプ
ログラムに対し、２つのセクションに割当てられる容量
が良好に適応せず、その結果ミス率が単一バッファメモ
リの場合より高くなることさえある。

【００１０】従って、このようなバッファメモリメモリ
の割当てを変える必要があるときは、各変更モジュール
の全情報を保存する必要がある。このような処理に必要
な時間はこのタイプの構造の無視し得ない欠点を構成す
る。更にルーティングゲートを再構成する必要がある。 ルーティングゲートが多数の場合、この処理はバッファ
メモリの動作を遅くする。この従来技術によるバッファ
メモリはデータから命令を分離して動作するが、メモリ
エレメントをいくつかのクラスにしたがって編成し（各
クラスはタグで参照する）記憶情報を参照するのに必要
な比較器の数を減少させるようにしていない。従って、
この従来のバッファメモリはアソシアティブモードで動
作するようにしたものであってクラスモードで動作する
ものでない。

【００１１】更に、バッファメモリを所定の割当ての２
つのブロックに分割する手段は２つのブロックの内容の
間のコヒーレンスに問題を生ずる。実際上、バッファメ
モリの各メモリエレメントは連続アドレスを有する一群
のワードを含む。しかし、実際にはこのようなワード群
はしばしば命令とワードの両方を含んでいる。このこと
は、特定のワード群が２回ロードされ得ること、即ち最
初に命令の要求時に“命令”メモリエレメントにロード
され次いで最初のローティングが除去される前に、デー
タの要求時に“データ”メモリエレメントにロードされ
ることがあることを意味する。従って、進行中のオペレ
ーションに含まれるタイプと反対のタイプの情報アイテ
ムがこれに割当てられてないセクションにロードされ得
る。今、このような２重ローディングの場合において情
報ブロックの値を変更する必要がある場合、更新を両セ
クションにおいて同時に実施する必要がある。これがた
め、バッファメモリを２つのセクションに分割しない場
合よりシステムが一層複雑になる。更に、同一の情報が
バッファメモリの両セクションに存在することはその総
容量を潜在的に減少する。従って、発明が解決しようと
する問題は情報のタイプを考慮に入れてミス率を減少さ
せると共に上述した置換えモードに関する欠点を除去す
ることにある。

【００１２】

【課題を解決するための手段】この問題を解決するため
に、本発明のバッファメモリ用制御装置においては、前
記パーティショニング手段が前記情報タイプの少なくと
も一つのタイプ（以後限定タイプという）の情報をバッ
ファメモリ内に散在するたかだか予め決めた限定記憶容
量のメモリ領域に満たし得るようにし、前記限定記憶容
量が限定タイプの記憶情報により超過されている状態に
おいて現情報アイテムをロードする必要があるとき、前
記置換え手段がこの情報アイテムを置換え可能な限定タ
イプの記憶情報アイテムと優先的に置換えることにより
ロードするようにしたことを特徴とする。

【００１３】このように情報のタイプを考慮に入れるこ
とによりミス率が低下し、また情報を複写する必要がな
く実施が容易になると共にコヒーレンスが得られる。前
記置換手段は−前記限定記憶容量が超過され且つ少なく
とも１つの限定タイプ情報がアドレスされた現クラスに
対し存在するとき限定タイプ情報の置換えを制御するブ
ロックＲＬと、−その他の場合に任意の情報の置換えを
制御するブロックＲＴとを具えるものとするのが有利で
ある。このようなディストリビュート編成は実現に便利
である。バッファメモリは数クラスのメモリエレメント
で構成するのが有利である。

【００１４】情報のパーティショニングを再構成するの
が望ましいときは、前記限定記憶容量の新しい値をロー
ドするだけで充分であり、既に記憶されている情報を保
存する必要なしにバッファメモリは置換えにより新しい
パーティショニングに進化していく。従って、バッファ
メモリの再構成は限定記憶容量の新しい値のローディン
グ以外に何も外部的介在を必要としないため極めて高速
に行われる。

【００１５】前記限定記憶容量は更新し得る値をロード
することにより決定する。このようにすると、このよう
なバッファメモリと関連する言葉で表わされたプログラ
ムの実行において命令及び／又はデータに割当てられる
それぞれのセクションの寸法を指定することができる。 この値はプログラムの実行前に固定し、この割当てを実
行するパーティショニング手段にロードすることができ
る。パーティショニング手段は一連の予め決めた値に従
って予めプログラムすることができ、或いはプログラム
の実行中にプログラムのシーケンスに最適な値を決定す
るようにすることもできる。

【００１６】限定記憶容量が超過された際の限定タイプ
の記憶情報の置換えアルゴリズムはバッファメモリ内に
記憶されている任意の他の情報を置換えるのに使用され
ている汎用置換えアルゴリズム（限定タイプのメモリエ
レメントに限定）とすることができる。これは既知のア
ルゴリズムの１つ、ＬＲＵ，ＦＩＦＯ、ランダム又は他
の任意のアルゴリズムとすることができる。限定モード
では、特別のアルゴリズムを用いることができる。例え
ばチャネルを順に増大するインデックスの順序シーケン
スに従って分類することにによって、限定モードにおい
て置換えを実施する必要のあるチャネル（及び従ってメ
モリエレメント）の選択を例えば最低のチャネルインデ
ックスを決定することにより急速に実施することができ
る。

【００１７】本発明によれば命令又はデータを制限する
ことができる。また、両タイプの情報に割当てるそれぞ
れの限定記憶容量の値を同時に定めることができる。例
えば両限定記憶容量の割合をそれらの和が　１００％以
下となるように定めることができる。この場合にはバッ
ファメモリの容量の利用率が低い。両限定記憶容量の割
合はそれらの和が　１００％以上になるように定めるの
が好適である。このようにすると、一方のタイプの情報
が一時的に少なく存在するときにこのタイプの情報に使
用し得るメモリスペースを他方のタイプの情報に移すこ
とができる。これがためバッファメモリは両タイプの情
報を同時に一層良好に考慮するものとなる。

【００１８】

【実施例】以下、図面を参照して本発明を実施例につき
詳細に説明する。図１はバッファメモリの必須の素子を
示す簡略図を示すものであるが、これに限定されるもの
でない。このバッファメモリは各々４つのクラスＫ０，
　Ｋ１，　Ｋ２，　Ｋ３のメモリエレメントを含む２つ
のチャネルＶ０，　Ｖ１を具える。各クラスは各チャネ
ルごとに１つのメモリエレメントを含み、図示の例では
２つのメモリエレメントを含む。チャネルＶ０はメモリ
エレメント５００，　５１０，　５２０，　５３０を含
む。チャネルＶ１はメモリエレメント５０１，　５１１
，　５２１，　５３１を含む。クラスＫ０はメモリエレ
メント５００，　５０１を含み、以下同様である。

【００１９】各メモリエレメント、例えば５００　は数
個の記憶位置： −プレゼンスビットＰ用の記憶位置、 −記憶タグ用の記憶位置、 −連続アドレスを有する均等な複数のワードのような情
報を含むデータブロックＢＬ用の記憶位置、を具える。 各クラスＫ０，　Ｋ１，　Ｋ２，Ｋ３にそれぞれ関連フ
ィールドＥＲＴ０，ＥＲＴ１，ＥＲＴ２，ＥＲＴ３は使
用する置換えエルゴリズムに従って各クラスのメモリエ
レメントの占有状態を決定するものである。これらフィ
ールドＥＲＴはバッファメモリのメモリエレメントの各
々に固有のものとすることもできる。

【００２０】データはデータフィールドＢＬを供給する
データバス５Ｄにより伝送される。アドレスは３つのフ
ィールド：入力アドレスタグフィールドＣＥ、入力アド
レスクラスインデックスフィールドＫ、データフィール
ドＢＬ内のワードを識別するワードインデックスフィー
ルドＩＭ、を供給するアドレスバス５Ａにより供給され
る。フィールドＩＭ及びプレゼンスビットＰはなくても
よい。プレゼンスビットＰがないときは各クラスと関連
するフラグを用いる別の解決法がある。

【００２１】ペロセッサ（図示せず）はバッファメモリ
と協働しアドレスをバス５Ａに供給する。プロセッサは
データワードをバス５Ｄに供給し、或いは又バス５Ｄ上
のデータワードを受信することができる。デコーダ５５
が入力アドレスからクラスインデックスを抽出し、対応
するクラスを選択する。この場合、このクラスのメモリ
エレメントが駆動される。例えば、クラスＫ０が選択さ
れると、メモリエレメント５００　及び５０１　が駆動
される。このときこれらメモリエレメントはそれらのプ
レゼンスビットＰ（もしあれば）及びそれらの記憶タグ
ＣＳを制御装置１０に伝送する。この制御装置は入力ア
ドレスの入力タグＣＥも受信する。図１では単一の制御
装置１０をバッファメモリ全体に対し設けている。これ
はハードウエアの複雑化が最低になる利点を有する。１
つもしくはそれ以上のクラスに対し別々の制御装置を用
いることもでき、これは実行速度が向上する利点を有す
る。

【００２２】アドレスのサーチがサクセス（成功）の場
合、サクセスを生じたメモリエレメント内のデータＢＬ
の読出し又は該メモリエレメントへのデータＢＬの書込
みが実行されると共に関連するＥＲＴフィールドが更新
される。アドレスのサーチがミス（失敗）の場合には、
置換えがＥＲＴフィールドを考慮してそのタグＣＳ及び
そのプレゼンスビットＰ（もしあれば）を有するデータ
フィールドＢＬを書込むことにより実行される。制御装
置１０が有効な置換えアルゴリズムに従って置換えるべ
きメモリエレメントを選択する。

【００２３】本発明においては、各メモリエレメント（
例えばメモリエレメント５００）に関連する種々のフィ
ールドのビットを図２に示すように変更する。フィール
ドＰ，ＣＳ，ＢＬ及びＥＲＴに加えてフィールドＥＲＬ
及びＴを用いる。フィールドＴはＢＬに記憶されている
情報が命令タイプかデータタイプかを示すビットである
。 このフィールドはバッファメモリに情報を供給するプロ
セッサから到来する。フィールドＥＲＬは置換えの実行
中における対応するメモリエレメントの占有状態を示す
ものであるが、本発明に特有の限定モードに関連するオ
ペレーションのみを考慮したものである。

【００２４】図３は、バス５Ａによりアドレスされるメ
モリエレメント５００，　５０１，　５０２，　５０３
に関連する単一のクラスＫ０に割当てられた制御装置１
０を示す。各メモリエレメントはその記憶タグを比較器
１２０，　１２１，　１２２，　１２３にそれぞれ伝送
し、これら比較器はこれらタグを入力アドレスタグとそ
れぞれのペレゼンスビットＰ０〜Ｐ３の制御の下で比較
する。

【００２５】ミスの場合には全ての比較器の出力（ＳＶ
０〜ＳＶ３）が非活動状態になる。サクセスの場合には
これら比較器の１つの出力が活動状態になる。信号　Ｓ
Ｖ０〜ＳＶ３　を受信するＮＯＲゲート１６は現在与え
られたアドレスがミスの場合にこれを信号する信号Ｓ／
Ｅを出力する。

【００２６】制御はパーティショニング手段３０及び置
換え手段４０により実行される。パーティショニング手
段３０はプロセッサ（図２）から到来するバス５Ａから
現アドレスに属するタイプビットＴｃを受信するカウン
タ３０１　を具える。このカウンタ３０１　は予め決め
た限定タイプの情報に割当てる。

【００２７】カウンタの値により表わされる、バッファ
メモリに実際に格納されている限定タイプの情報の量を
比較器３０３　において、レジスタ３０５　に格納され
ているこの限定タイプのために用意された限定記憶容量
の値と比較する。この最大値が超過されるときこの比較
器は低出力信号を発生する。この最大値が超過されない
ときこの比較器は高出力信号を発生する。比較器３０３
　の出力をＯＲゲート３０９　に供給する。このＯＲゲ
ートは、現アドレスにより活動化されたクラスＫのタイ
プビットＴｋの全てを受信するＮＯＲゲート３０７　の
出力も受信する。ＮＯＲゲート３０７　は活動化された
クラスのメモリエレメントのどれも限定タイプの情報を
記憶してない場合にのみ高出力信号を発生し、他の全て
の状態では低出力信号を発生する。

【００２８】ＯＲゲート３０９　は、置換えを活動クラ
スのメモリエレメントの全体（Ｗ）に亘って実施する必
要があるのか、該クラスの限定セクション（Ｌ）に亘っ
て実施する必要があるのかを決定する信号Ｗ／Ｌを出力
する。この信号Ｗ／Ｌを全体に対する置換えを行うユニ
ット４０１　と、限定セクションに対する置換えを行う
ユニット４０３　とを具える置換え手段４０に供給する
。信号Ｗ／Ｌが低の場合、この信号はインバータ４０５
　を介してユニット４０３　のみを活動化する。これが
ため、限定タイプの情報の量がその最大値をまだ越えな
い場合、又は活動クラスのメモリエレメントのどれも限
定情報を含んでいない場合には活動クラスの全体がサー
チされる。

【００２９】ユニット４０１　は慣例の置換アルゴリズ
ム、例えばＬＲＵ，ＦＩＦＯ又はランダムアルゴリズム
を選択されたクラスの全メモリエレメントに対し実行す
る。 この目的のために、このユニットはＥＲＴフィールドを
受信する。例えばこのＥＲＴフィールドによりＬＲＵア
ルゴリズムの場合には、そのメモリエレメントが最も長
時間使用されてないものか否かを決めることができる。 ユニット４０１　はミスの場合にのみ活動状態になる信
号Ｓ／Ｅにより活動化される。ユニット４０１　はバス
３２０　に置換え用に選択したメモリエレメントのアド
レスを供給する。この置換えステップは前記限定記憶容
量にまだ到達してないとき又は選択されたクラス内のメ
モリエレメントのどれも限定タイプの情報を含んでいな
いときに実行される。

【００３０】ユニット４０３　は、バッファメモリ内の
限定タイプの情報量が限定タイプ情報に使用し得る限定
記憶容量を越え且つ選択されたクラスが少なくとも１つ
の限定タイプのメモリエレメントを含むときに動作する
。ユニット４０３　はミスの場合に活動状態のＳ／Ｅ信
号を受信すると共に、活動化されたクラスの全メモリエ
レメントからＥＲＬフィールド及びそれらのタイプビッ
トＴｋを受信する。ＥＲＬフィールドは置換えを使用す
るアルゴリズムに従って実行する必要がある順序を示し
、ビットＴｋにより正しいタイプＴを有するメモリエレ
メントを決定する。選択したメモリエレメントのアドレ
スをバス３２０　によりメモリエレメントに伝送する。 このアドレスはカウンタ３０１　にも到達し、このカウ
ンタはバスＴｋから、選択したメモリ素子のタイプも受
信する。この置換えを考慮に入れるために、この選択し
たメモリエレメントの現タイプが限定タイプであり、且
つ新しい情報が限定タイプでない場合にはこのカウンタ
は１だけデクメントされる。他方、現アドレスのビット
Ｔｃが限定タイプでないことを示し、且つ新しい情報が
限定タイプである場合にはこのカウンタは１だけインク
リメントされる。旧及び新情報が同一タイプの場合には
カウンタの位置は変化しない。

【００３１】図３においても図１と同様に図を簡単且つ
明瞭にするために種々の素子の同期回路は図示してない
。このようにしてバッファメモリを限定タイプに割当て
られた情報量まで限定タイプの情報アイテムで満たすこ
とができる。実際にはこの情報量を一時的に僅かに越え
てもよい。実際上、種々のプログラムにおいてデータブ
ロックＢＬは両タイプの情報を含み得る。メモリ素子に
割当てられるタイプは置換えを生じた情報のタイプにな
る。これがため、限定タイプの最大量に僅かな追加の残
留レベルを付加することができる。

【００３２】限定タイプの情報が十分多量に存在しない
場合には他方のタイプの情報がバッファメモリ内に、こ
のメモリが　１００％満たされるまで自動的にロードさ
れる。２つのタイプの情報の各々に関し２つの限定記憶
容量値を定めることができる。（別のタイプの情報が与
えられない場合には）バッファメモリ内に未使用スペー
スが残らないようにするために、２つの限定記憶容量の
和を　１００％より大きくするのが好ましい。このよう
にすると、バッファメモリの一層良好なダイナミック管
理が得られる。限定記憶容量の値はレジスタ３０５　（
図３）　内の値を変えることにより容易に更新させるこ
とができる。 ２つの値を発生させる必要があるときは、パーティショ
ニング手段及び置換え手段の一部分を二重化すればよい
。こさらの値は時間の経過につれて変更することもでき
る。

【００３３】図４はプログラムの実行中における命令Ｉ
とデータＤの割合の変化の一例を示すものである。プロ
セッサによるプログラムの実行の開始時には命令Ｉの割
合が高く、データの割合が低い。この相対的割合は時間
とともに変化し、次いで逆になる。このとき限定記憶容
量の値の更新を実行し得る。これは予め決めた値の外部
シーケンスから又はプロセッサにより実行されるプログ
ラムと関連してダイナミックにプログラムされた値の中
から新しい限定記憶容量をバッファメモリ内に導入する
ことにより実行するとができる。

【００３４】図５は限定タイプの情報を特定の処理アル
ゴリズムに従って処理するユニット４０３　の簡単な実
施例を示し、本例では１クラス当り４メモリエレメント
である。本例では置換え順序はこのユニットの構造に固
有であり、ＥＲＬフィールドは存在しない。１クラス４
メモリエレメントを具える本例ではユニット４０３　は
活動化されたクラスＫに対しタイプビットＴ１Ｋ　，　
Ｔ２Ｋ　，　Ｔ３Ｋ　及び　Ｔ４Ｋを受信する。第１Ｎ
ＯＲゲート６１がＴ１Ｋ　及び　Ｔ２Ｋの反転を受信す
る。第２ＮＯＲゲート６２が　Ｔ１Ｋ　，Ｔ２Ｋ　及び
Ｔ３Ｋ　の反転を受信する。第３ＮＯＲゲート６５がＴ
１Ｋ　，　Ｔ２Ｋ　，　Ｔ３Ｋ　及びＴ４Ｋ　の反転を
受信する。

【００３５】各々３つの状態を有する４つの出力段６０
，　６２，　６４，　６６はそれぞれ −Ｔ１Ｋ　 −ＮＯＲゲート６１の出力 −ＮＯＲゲート６３の出力 −ＮＯＲゲート６５の出力 を受信する。

【００３６】Ｗ／Ｌ信号が活動状態（限定モード）であ
り、信号Ｓ／Ｅが活動状態である場合（ミス）は、これ
ら４つの出力段はそれぞれの入力端子に存在する信号を
通過させる。逆の場合にはこれら出力段は高インピーダ
ンス状態になる。この回路構成によればこの回路は順序
付けられた一連のメモリ素子のうちの最初の選択可能メ
モリエレメントを選択する（最低チャネルインデックス
の決定）。このように、メモリエレメントを置換えが所
望の順序で実行されるように順序づけることができる。

【００３７】上述のバッファメモリに使用する情報管理
方法を図５にフローチャートで示してある。 ステップ１：初期化：カウンタ３０１　の値ＣＬを零に
リセットし；限定記憶容量の値を記憶し；各メモリエレ
メントに対しそのプレゼンスビットＰを非占有状態（例
えば０）にセットすると共にそのタイプビットＴを非限
定状態（例えば０）にセットする。

【００３８】ステップ２：入力アドレスのエントリ；ス
テップ３：クラスの選択及び出力アドレスタグの決定： ステップ４：このアドレスに対するサクセスのサーチ：
クラスのメモリエレメントに対しそれらの記憶タグと現
アドレスのタグＣＥの比較及びプレゼンスビットＰの検
査が行われる。

【００３９】サクセスである場合（ブランチ１０）、サ
クセス条件を満足するメモリエレメントの選択（ステッ
プ１１）、データの読出し又は書込み（ステップ１２）
、次いで置換え装置内のバッファメモリの状態の更新が
行われる。クラスの全メモリエレメントに対しミスであ
る場合、置換えプロシージャを実施する必要がある（ブ
ランチ２０）。

【００４０】ステップ２１：カウンタに含まれる値と限
定記憶容量の値との比較及び現アドレスで選択されたク
ラスのメモリエレメントのタイプの検査；カウンタの値
が限定記憶容量より低いとき、又はどのメモリエレメン
トも限定タイプでないとき、置換えモードを基本置換ア
ルゴリズムＲＴにより決定する（ブランチ２５）（ステ
ップ２１１）。カウンタの値が限定記憶容量の値より高
く且つ選択し得る少なくとも１つの限定タイプのメモリ
エレメントが存在するとき、置換えモードを限定モード
ＲＬにより決定する（ブランチ２６）（ステップ２１２
）。一方又は他方の置換えアルゴリズムの実行後、種々
の更新処理が必要である（カウンタ、タイプビット−−
−−）（ステップ２２）　。ステップ５は（必要に応じ
）限定記憶容量の値を変更するステップを示す。これら
の値は個々に、又は順次に入力することができ、またプ
ログラムすることができる。

【００４１】パーティショニング手段及び／又は置換え
手段はプログラムすることができる。最も一般的な場合
には中央処理装置がソフトウエアを用いて現在の限定タ
イプの情報量を決定し、次いでこれをこの限定タイプに
対し用意された限定記憶容量と比較するようにする。現
在の限定タイプの情報量を（バッファメモリ又は他のメ
モリ）の記憶位置に書込む。ソフトウエアは選択された
クラス内の限定タイプのメモリエレメントの存在の検出
も実行する。

【００４２】本発明により得られるミス率に対する性能
を各メモリ素子が各４バイトの４ワードを具える総容量
が　２５６バイトのバッファメモリについて測定した。 基本置換えアルゴリズムとしてＬＲＵ置換えアルゴリズ
ムを用いて全体モードの置換えを実行した。最小チャネ
ルインデックスの決定を実施する置換えアルゴリズムを
用いて限定モードの置換えを実行した。結果を表Ｉに示
す。 この表において限定記憶容量の値ＱＬはバッファメモリ
の総容量の分数値で表わしてある。結果も１クラス当り
のメモリ素子の数Ｅの関数で示してある。

【００４３】表　　Ｉ

【００４４】

【００４５】本発明を適用してないＬＲＵ基本アルゴリ
ズムの結果は１６／１６に等しい限定記憶容量の値ＱＬ
に対応する列に示す結果に等価である。他の列は　０／
１６〜１５／１６のＱＬに対する結果を示す。所定の値
の限定記憶容量に対し結果が最適になる。これらの最適
結果を表ＩＩに、ＬＲＵにより得られるミス率と対比し
て示す。１クラス当りのメモリエレメントの数Ｅを多く
すると、本発明による改善が大きくなり、例えばＥ＝１
６のときミス率が半分以下になることが観測された。

【図面の簡単な説明】

【図１】バッファメモリの全体的構成を示す簡略図であ
る。

【図２】本発明によるメモリエレメントに関連する情報
フィールドの全体図である。

【図３】本発明バッファメモリの制御装置の構成図であ
る。

【図４】プログラムの実行における命令とデータの相対
的割合の変化を時間の関数として示す図である。

【図５】簡単化した実施例において限定タイプの情報の
置換えに用い得るチャネル選択回路の回路図である。

【図６】本発明バッファメモリの管理方法の種々のステ
ップを示すフローチャートである。

【符号の説明】

５Ａ　　アドレスバス ５Ｄ　　データバス １０　　制御装置 ５００，　５０１，−−−５３０，　５３１　　メモリ
エレメント５５　　アドレスデコーダ ３０　　パーティショニング手段 ３０１　　　カウンタ ３０３　　　比較器 ３０５　　　レジスタ ３０７　　　ＮＯＲゲート ３０９　　　ＯＲゲート ４０　　置換え手段 ４０１，　４０３　　置換えユニット

Claims (10)

【特許請求の範囲】
1. 【請求項１】　　「命令」タイプの情報及び「データ」
   タイプの情報を区別する再構成可能パーティショニング
   手段（３０）と、記憶されている情報を少なくとも１つ
   の置換えアルゴリズムに従って現情報と置き換える置換
   え手段（４０）とを具えるバッファメモリ用制御装置お
   いて、この問題を解決するために、本発明のバッファメ
   モリ用制御装置においては、前記パーティショニング手
   段（３０）が前記情報タイプの少なくとも一つのタイプ
   （以後限定タイプという）の情報をバッファメモリ内に
   散在するたかだか予め決めた限定記憶容量のメモリ領域
   に満たし得るようにし、前記限定記憶容量が限定タイプ
   の記憶情報により超過されている状態において現情報ア
   イテムをロードする必要があるとき、前記置換え手段（
   ４０）がこの情報アイテムを置換え可能な限定タイプの
   記憶情報アイテムと優先的に置換えることによりロード
   するようにしたことを特徴とするバッファメモリ用制御
   装置。
2. 【請求項２】　　前記置換え手段は−前記限定記憶容量
   が超過され且つ少なくとも１つの限定タイプ情報がアド
   レスされた現クラスに対し存在するとき限定タイプ情報
   の置換えを制御するブロックＲＬと、−その他の場合に
   任意の情報の置換えを制御するブロックＲＴとを具える
   ことを特徴とする請求項１記載の制御装置。
3. 【請求項３】　　限定タイプの記憶情報の置換えを特定
   の置換えアルゴリズムに従って実施することを特徴とす
   る請求項１又は２記載の制御装置。
4. 【請求項４】　　前記限定記憶容量の値を更新可能にし
   たことを特徴とする請求項１，２又は３記載の制御装置
   。
5. 【請求項５】　　前記限定記憶容量の少なくとも１つの
   値をパーティショニング手段にロードするようにしたこ
   とを特徴とする請求項１〜４の何れかに記載の制御装置
   。
6. 【請求項６】　　前記パーティショニング手段（３０）
   が限定記憶容量の値を決定するようプログラムしたこと
   を特徴とする請求項１〜４の何れかに記載の制御装置。
7. 【請求項７】　　両タイプの情報に割当てた限定記憶容
   量の割合の和を　１００％より大きくしたことを特徴と
   する請求項１〜６の何れかに記載の制御装置。
8. 【請求項８】　　前記対応する限定記憶容量が超過され
   た場合に、限定タイプの情報アイテムの置換えを、順序
   づけた一連のチャネルインデックスの第１チャネルイン
   デックスを有する選択可能メモリエレメントを選択する
   ことにより実施するようにしたことを特徴とする請求項
   １〜７の何れかに記載の制御装置。
9. 【請求項９】　　前記パーティショニング手段（３０）
   及び／又は置換え手段（４０）はプログラムド装置であ
   ることを特徴とする請求項１〜８の何れかに記載の制御
   装置。
10. 【請求項１０】　　プロセッサ手段と、二次記憶手段と
    、前記プロセッサ手段と前記二次記憶手段との間に介挿
    されたバッファメモリとを具えると共に請求項１〜９の
    何れかに記載の制御装置を具えることを特徴とするデー
    タ処理システム。