JPH0470656B2 - - Google Patents

Description

【発明の詳細な説明】 プログラムの実行中にCPUにより実施される
諸操作の大きさ部分はデータを主記憶装置から検
索し、又データを主記憶装置に記憶することを含
む。いくつかのCPUの全てが１つの共通の記憶
装置を共用する多重プロセサ・システムにおいて
は、１つ以上のプロセサが主記憶装置に対するア
クセスを待機するように強制され、別のプロセサ
がこの記憶装置を読出し又は書込み操作と連結さ
せることが屡々生じる。もし各プロセスが情報を
引出すことができるそれ自体の専用データ・カツ
シエを有する場合には全処理速度は改善すること
ができることが明らかになつた。

このようにしてカツシエ・メモリーが生れた。

本発明の譲受人に譲渡された米国特許第
3866183号に記載された如き早期の諸態様では、
メモリー・アクセス・サイクルが開始される間同
時にカツシエが検査される「同時進行」形態をと
つていた。従つて、もしカツシエ内に所望のデー
タが存在した場合、記憶サイクルは打切られてこ
のデータがカツシエから検索された。この方式で
はメモリー・アクセスの開始に先立つたカツシエ
の探索には時間的損失がなかつた。カツシエのこ
の操作はCPUにとつて「不可視」であると呼ば
れる。

これも又本願の譲受人に譲渡された米国特許第
3845474号に示された後願の形態は、多重プロセ
サ・システムに使用されるクリア装置を備えたカ
ツシエを教示している。このカツシエは、そのプ
ロセサが全てのプロセサにより共用される共通オ
ペレーテイングシステムモジユールに入る度毎に
それ自体を完全にクリアするものであつた。又、
データが補助ストアから主記憶装置へ入れられる
場合等のプロセサが外部割込みをサービスする度
に全カツシエがクリアされた。この構成のため、
カツシエの過度のクリアを招き、「ヒツト」率が
低いため主記憶装置に対する多くのアクセスを必
要とすることによりプロセサの操作速度が遅くな
つた。即ち、カツシエにおいて所望のデータの発
見の可能性は、カツシエの完全クリアの頻度の故
に低かつた。この文献は又、カツシエ・ストアの
書込み操作を制御する「ラウンド・ロビン」カウ
ンタについて記載している。カツシエに書込まれ
た最初のデータ片はカツシエ・ストアの特定ブロ
ツクの第１のセクシヨンに記憶され、その関連す
るタツグ・アドレス・ビツトは登録簿の対応列の
対応する第１のレベルに記憶される。その後、連
続する入力データの各片が次の順の場所に記憶さ
れる。このように、４レベルカツシエの場合に
は、入力データはセクシヨン１，２，３，４，１
…に記憶される。容易に理解されるように、この
方式は、ブロツクの特定列内の最も瀕繁に使用さ
れたデータ・ワードがカツシエのビツト失敗の後
１つの入力データ・ワードにより置換され得るよ
うに、４レベルの相対的使用瀕度を斟酌しない。

更に最近になつて、カツシエの不必要なクリア
を除く装置について、本願の譲受人に譲渡された
1978年12月11日出願の米国特許出願第968223号
「カツシエ・ストアを選択的にクリアする装置」
に記載された。米国特許出願は、カツシエにおけ
るデータのタツグ・アドレスを、システム内の別
のプロセサにより変更された主記憶装置内のデー
タのタツグ・アドレスと比較するため複写登録簿
を用いる装置について記載する。マツチングが見
出されたならば、カツシエにおけ古いデータの場
所は空白として表示された。この方式は、カツシ
エの必要性の遥かに低いクリア動作の除去による
進歩を示し、その分だけ操作速度が早くなつた。
しかし、カツシエに対する新らしいエントリを行
うラウンド・ロビン方式が本例に用いられたた
め、カツシエから屡々用いたデータを置換する問
題は依然として未解決の侭である。

カツシエのヒツト失敗と同時にメモリーから取
出されたデータの階層的記憶のための装置が米国
特許第3967247号に記載されている。カツシエの
不的中の後主記憶装置からの検索と同時にカツシ
エからデータを転置するため「殆んど使用されな
かつた」方式が本特許において記載されている。
１つの２ビツト・エージ・タツグが、各データ片
に対する最後の照合の相対時間を表示するためカ
ツシエの４レベルの各々に割当てられる。各突合
せ後に、コンパレータ回路網が突合せられたレベ
ルと各レベルからのエージ・ビツトを検査する。
この時回路網は、加算回路網を用いて各レベルに
対するエージビツトを更新する。この算法は本発
明のそれとは異なり、構成のハードウエアは更に
複雑であり、速度が遅く、コストも高い。

このように、別のプロセサが主記憶装置におけ
るデータ・ワードを変更する度毎に完全にクリア
されることがなく、カツシエのヒツト失敗の後あ
るデータ列における殆んど使用されない項目を転
置する多重プロセサ・システムにおける使用に適
するカツシエ・メモリーに対する需要がある。

本発明はハードウエア素子の複雑な構成で実施
されるが、思想それ自体は簡単である。基本的に
は、この思想は、ヒツト率を高め、カツシエにお
ける記憶に続いて主記憶装置において変更された
カツシエ内の情報のみを選択することによつて従
来技術のカツシエ・メモリー構成の速度および精
度を向上することである。ヒツト率の増進とは、
高速カツシエ・メモリーに見出される中央処理装
置によるデータへのアクセス要求の比率の増加を
意味し、これにより比較的遅い主記憶装置に対す
るアクセスを不必要にする。選択的なクリア動作
は、２個以上の中央処理装置が共通の一主記憶装
置を共用する多重プロセサ・システムにおいての
み有意義である。このような場合、１つのCPU
は、システムにおける１つ以上の他のCPUのカ
ツシエ・メモリーに記憶される主記憶装置内のデ
ータ片を更新することができる。もはや主記憶装
置とカツシエにおけるこのデータ項目間の合致が
ないため、古いデータはそれが記憶されるカツシ
エには存在しないものとして表示されねばならな
い。従つて、このデータの使用を欲するCPUは
主記憶装置をアクセスするよう強制され、これに
より最も最近のデータを受取る。

速度のこれ以上の増加は、CPUの他の装置に
対してカツシエを「同時進行」（look−aside）の
関係に構成することにより達成される。「同時進
行」とは、CPUの残部に対するカツシエの関係
が、カツシエ登録簿の質疑が１つのポートを選定
してこれを介して主記憶のアクエスを行うCPU
による準備動作と同時に生じる如きものであるこ
とを意味する。カツシエ登録簿が質疑される間の
主記憶装置のアクセスの遅れがないことはこのよ
うな構成により生じねばならない。実際に、カツ
シエ内で「ヒツト」が生じる場合、この事実を表
示する信号は、メモリーのアクセスが全く開始さ
れないようにするため使用される。このような構
成の効果は、カツシエ・メモリー装置の操作を
CPUにとつて判らないようにすることで、この
場合カツシエの存在の御蔭でCPUによるデータ
検索において殆んどあるいは全く時間的損失がな
い。

ヒツト率が向上すれば、カツシエ・メモリー装
置が主記憶装置に使用されるものよりも高速のチ
ツプで構成されるため、CPUによるデータ検索
速度の増加をもたらす。このヒツト率の増加は、
カツシエを更新する「殆んど使用されない」方式
の使用および選択クリア装置の使用によつて提供
される。従来技術のラウンド・ロビン・カウンタ
がもたらす問題は、「殆んど使用されなかつた」
（LRU）カツシエ内のレベルの記録を保持するこ
とによつて解決される。この時入力データが前記
のLRUレベルに記憶される。ヒツト率はこの方
式を用いて向上する筈である。

選択的クリア装置によつて速度および精度の更
なる向上が得られる。本発明においては、別の
CPUにより変更された主記憶装置におけるデー
タのアドレスを受取りこれ等アドレスをカツシ
エ・ストアに存在するデータのアドレスと比較す
る選択的クリア装置の理念を得ることによつて、
過大のクリアの問題が除去される。全ての突合せ
成功に対してクリア信号が生成され、カツシエ・
ストアにおける前記データ場所を充／空アレーに
おいて空として表示させる。この構成は、一たん
カツシエに記憶されたデータ片が依然としてカツ
シエ内にある可能性を増大することによつてヒツ
ト率を増加するものである。

単一CPUデータ処理スステムに使用する本発
明の最も単純な実施態様においては、CPUによ
りその操作中に使用される複数のデータ・ワード
を記憶しアクセスするため使用されるカツシエ・
ストア装置が提供される。これ等のデータ・ワー
ドは命令OPコード、オペランドおよびアドレス
であり得、各セクシヨンが複数のブロツクに分割
される複数のセクシヨンに記憶される。

登録簿装置は、データの主記憶装置の場所を識
別する絶対アドレスの13のタツグ・アドレス・ビ
ツトを記憶することによりカツシエ・ストア装置
に記憶されるデータを指標付けするため使用され
る。これ等のタツグ・アドレス・ビツトは、関連
するデータが記憶される特定のブロツクと関連し
かつこれと対応する登録簿装置におけるある場所
に記憶される。13ビツト以上又はそれ以下が使用
できる。登録簿装置は、各レベルがカツシエ・ス
トア装置の１つのセクシヨンと対応する複数のレ
ベルに構成される。各レベルは、更に、各々がカ
ツシエ・ストア装置の１組のブロツクと対応する
複数の列に分割される。即ち、カツシエ・ストア
の１つのセクシヨンには基本登録簿の１つのレベ
ルにおける列数と同数のブロツクがある。１つの
列のレベル数は、カツシエ・ストア装置における
セクシヨン数と正確に対応する。基本登録簿装置
の目的は、カツシエ・ストア装置に記憶される各
データ・ワードのタツグ・アドレスビツトを記憶
し、これ等のタツグ・アドレス・ビツトをCPU
により要求されつつあるデータの絶対アドレスの
タツグ・アドレス・ビツトと比較することであ
る。次に、要求されたデータがカツシエ・ストア
装置に存在する時突合せ信号が生成される。

最後に、突合せが生じない時、全ての列のレベ
ルの使用に関する更新データを受取つて記憶し、
基本登録装置における「殆んど使用されない」レ
ベルを決定する制御装置がある。本装置も又、カ
ツシエのヒツトと同時に所要の情報を主記憶装置
から検索させてCPUに対して供給させられる。
CPUに与えられると同時に、検索されたデータ
はカツシエ・ストア装置に記憶され、その対応す
るタツグ・アドレス・ビツトは基本登録簿の
LRUレベルに記憶される。

多重プロセサ・システムにおいては、本発明
は、選択されたクリア装置の付加により前に述べ
た諸要素により実施される。この機構は基本登録
簿に対して同様に構成された複写された登録簿を
含む。その目的は、基本登録簿に記憶されたもの
と同じ指標付けされた情報を記憶し、これ等のタ
ツグ・アドレス・ビツトを本システム内の別の
CPUにより変更された主記憶装置内のデータの
絶対アドレスのタツグアドレスと比較することで
ある。マツチングが見出されてカツシエ・ストア
装置におけるデータ・ワードがこの時古いことを
表示する時、この選択的クリア装置は古いデータ
の場所を空として表示するクリア信号を生成す
る。

今日のコンピユータ・システムにおいては、マ
ルチプロセサは非常に屡々スループツトを増大す
るため第１図に示す如く信号システムコントロー
ラと接続される。プロセサ１および２はそれぞ
れ、これ等プロセサを主記憶装置２０とリンクす
るシステム・コントローラ１０と接続される。各
プロセサは又、その時使用中のデータ、アドレス
および命令を記憶するそれ自信の別個のカツシ
エ・メモリー３０を含む。各カツシエ・メモリー
と関連しているのは複写登録簿３１で、これは、
プロセサ１がそのカツシエ・メモリーからは古い
データを検索せず主記憶装置２０からそのデータ
の最新のバージヨンを検索するように、プロセサ
１のカツシエメモリーにおけるデータとプロセサ
２によりメモリー２０において変更されたデータ
間の比較を許容するよう作用する。各プロセサは
又、１つのプログラムにおけるオペランドについ
て演算論理操作を実施するオペレーシヨン装置を
含む。これ等のオペランドは最初主記憶装置から
検索記憶されるが、最初に検索される時カツシ
エ・メモリー３０に書込まれる。その後、これ等
オペランドは、記憶される場所が選択的クリア操
作の故に空白として表示される迄、あるいはカツ
シエのヒツト失敗の結果主記憶装置２０から検索
され他のデータにより転置される迄はカツシエ・
メモリーから検索することができる。

各プロセサは又、プロセサ、主記憶装置２０と
入出力コントローラ３４により制御される他の入
出力周辺装置間の通信と連係するように作用する
ポート制御装置３３を有する。

本発明のブロツク図は第２図に示される。
CPUにより用意される所要データの絶対アドレ
スはスイツチ５７を介してカツシエ・アドレスラ
ツチ５６に切換えられる。本発明の中枢部は３つ
の主なサブシステムの組合せからなる。第１のサ
ブシステムは、その操作においてCPUによつて
使用される多くのデータ・ワードを記憶しアクセ
スするために使用される。カツシエ・ストア４
０、第１のスイツチ４１、第２のスイツチ４２、
データ・ラツチ４３は第１のサブシステムの一団
を構成する。

この第１のサブシステムの構成は下記の如くで
ある。第３図によれば、カツシエ・ストア４０は
４つのセクシヨンからなり各セクシヨンは各々が
４ワードを含む512個々にアドレス指定可能なブ
ロツクに再分割される。各ワードは36ビツトの長
さである。カツシエ・ストア４０は、必要なデー
タの絶対アドレスのビツト１３乃至２３からなる
回線４４上にカツシエ・ストアアドレス信号を受
取るための11ビツト・アドレス入力を有する。第
２図に示す別の入力は回線４５上のレベル・スト
ローブ信号を受取る。この信号はカツシエ・スト
ア・アドレス信号と共に、どのセクシヨンとどの
ブロツクがデータ入力４６において入力データを
受取るべきかを決定する。

回線４６上の入力データは、２つの入力を有す
る第１のスイツチ４１を通過する。カツシエ・ス
トア４０に記憶されるべきデータは、カツシエの
ヒツト失敗の後のCPUの記憶操作から又は主記
憶装置からの取出しのいずれかから生じるデータ
である。CPUの記憶装置と同時に、データは回
線４７に入り、主記憶装置取出しサイクルから生
じたデータは回線４８に入る。スイツチ４１の目
的は、「第１のスイツチへ」と表示された回線上
の制御信号を介してカツシエ制御装置４９の制御
下で選択が行われたカツシエストア４０のデータ
入力とどの回線が接続されるべきかを選択するこ
とである。

第２のスイツチ４２は、カツシエ・ストア４０
の各セクシヨンのデータ出力側と接続された別個
のデータ入力を有する。これも又、カツシエのヒ
ツト失敗と同時に主記憶装置から取出されたデー
タを受取るため回線４８と接続されたデータ入力
を有する。第２のスイツチ４２は、72ビツト巾の
単一データ出力回線５０とカツシエ制御装置４９
から回線５０上のブロツク選択信号を受取る制御
入力を有する。スイツチ４２の目的と回線５１上
のブロツク選択信号の機能は、前述のどの入力回
線が単一出力回線に切換えられるかを制御するこ
とである。即ち、カツシエ制御装置４９は、その
レベルの的中が生じるならば、カツシエ・ストア
４０の４つのセクシヨンの内のどれかの72ビツト
の２倍ワード対出力を第２のスイツチ４２の出力
側に切換えることができる。もしヒツト失敗の場
合は、主記憶装置から険索されたデータは回線４
８を介して第２のスイツチ４２の出力側へ切換え
られ、同時に第１のスイツチ４１の出力側と記憶
するためカツシエ・ストア４０へ切換えられる。
このデータがカツシエ・ストア４０の正確にどこ
に記憶されるかは、以下に更に詳細に説明する
LRU算法に従つて回線４４と４５上の信号によ
つて制御される。

データ・ラツチ４３は、データCPUに与える
ためデータ入力を第２のスイツチ４２とデータ出
力回線５２から回線５０に接続させている。この
ラツチは又カツシエ制御装置４９からの回線５３
上のロード信号と接続された制御入力を有する。
データ・ラツチ４３の目的は、CPUが読出す迄
カツシエ・ストア４０からの、又は主記憶装置か
ら検索されたデータを保持する。データ・ラツチ
４３のローデイングは回線５３上のロード信号に
よつて制御される。

第２のサブシステムは、基本登録簿５４、コン
パレータ５５およびこれ等素子の目的を達成させ
るため必要な関連回路である。基本登録簿５４の
目的は、これも又カツシエ・ストア４０に記憶さ
れる主記憶装置におけるデータ・ワードを識別す
るタツグ・アドレスを記憶することである。コン
パレータ５５は、基本登録簿５４に記憶されたタ
ツグ・アドレスをCPUにより要求されたデー
タ・ワードのタツグ・アドレスと比較し、又要求
されたデータ・ワードがカツシエ・ストア４０に
存在する時突合せ情報を生成するよう作用する。
この突合せ情報はカツシエのどのレベルが所要の
データ・ワードを含むかを表示する。

語句「カツシエのレベル」については、基本登
録簿５４とカツシエ・ストア４０の全体的構成を
参照されたい。第３図に示す如く、カツシエスト
ア４０が４つのセクシヨンに分割されるため、基
本登録簿５４も又４つのレベルに分割される。第
３図によれば、基本登録簿５４の、レベルＡはカ
ツシエ・ストア４０のセクシヨン０と対応する…
等が判る。又、カツシエ・ストア４０の各セクシ
ヨンが複数のブロツクに分割されるため、基本登
録簿５４の各レベルも同様に複数の列に分割され
る。更に又あるレベルの各列も対応するセクシヨ
ンにおける特定のブロツクと対応する。このよう
に、基本登録簿５４の各列が、その各々がカツシ
エ・ストア４０の４つのセクシヨンの内の１つに
おける１つのブロツクと対応する４つのレベルを
有する。

各ブロツクは４つの36ビツト・ワードを記憶す
る。望ましい実施態様において、カツシエ・スト
ア４０の各セクシヨンには512のブロツクがある。
このように、各セクシヨンには2048ワードが記憶
され、各ワードは１つの11ビツト・アドレスを有
する。

CPUにより用意される如き要求されたデータ
の絶対アドレスの書式は第３図の左下隅部に示さ
れる。この絶対アドレスは第２図のスイツチ５７
を介してカツシエ・アドレス・ラツチ５６に切換
えられる。このアドレスはカツシエ・メモリー装
置における各素子により使用されるため一時的
に、ここに記憶される。スイツチ５７は、絶対ア
ドレスを保守パネル又は仮想記憶モードにおける
仮想装置の如きデータ処理システムの他の部分か
らカツシエ・アドレス・ラツチ５６に与えさせる
よう作用する。この絶対アドレスの最上位の13ビ
ツトはタツグ・アドレスビツトである。これ等の
13ビツト（０〜12）は、これも又カツシエ・スト
ア４０に記憶されたデータ・ワード数である8192
個の個々のデータ・ワードを識別するのに十分で
ある。次の９ビツト即ちビツト１３乃至２１はブ
ロツク／列アドレスとして作用する。これ等の９
ビツトは、カツシエストアと基本登録簿における
ブロツクと列の数とその数が対応する512の異な
る場所を識別するのに十分である。24ビツト・ア
ドレスの最後の２ビツトはビツト２２と２３であ
る。これ等のビツトは、どのワード対が又はどの
個々のワードがCPUにより要求されるかを識別
する。このように、第２図のカツシエ・アドレス
ラツチは３つの部分に分割される如く考えること
ができる。第１の部分はタツグ・アドレスの13ビ
ツトを記憶する。第２と第３の部分はそれぞれブ
ロツク／列アドレスと２ビツト・ワードの記述子
を記憶する。

基本登録簿５４は、そのデータ入力をカツシ
エ・アドレス・ラツチ５６の第１の部分に接続す
る回線５７を介してタツグ・アドレスでロードさ
れる。カツシエ・ストア４０は、データが回線４
８を介して主記憶装置から検索される時又は
CPUの回線４７を介する記憶操作において４ワ
ードでロードされるブロツクである。カツシエの
ヒツト失敗と同時にデーが主記憶装置から検索さ
れCPUの記憶装置は種々のプログラム命令から
生じる。CPU記憶操作は、１ブロツクのデータ
の主記憶装置とカツシエストア４０相方への同時
転送を含む。いずれのタイプのローデイングにお
いても、CPUにより１つの絶対アドレスがこの
ブロツクのデータを記憶する主記憶装置のアドレ
ス又は要求されるデータの主記憶装置におけるア
ドレスとして用意されることになる。各ブロツク
がカツシエ・ストア４０にロードされるため、こ
のデータに対する絶対アドレスの最上位の13ビツ
トが同時に基本登録簿５４にロードされる。この
タツグアドレスがロードされる基本登録簿５４の
列は、カツシエ・アドレス・ラツチ５６の第２の
部分に記憶された絶対アドレスの列アドレス・ビ
ツト１３〜２１によつて決定される。この等のビ
ツトは、回線５８を介して基本登録簿５４の読出
し／書込みアドレス入力側に与えられる。タツグ
アドレスが記憶される選択された列のレベルは、
回線５９上のレベル・ストローブ信号を介してカ
ツシエ制御装置４９により制御される。同様に、
入力データがカツシエ・ストア４０に記憶される
ブロツクは、カツシエ・アドレス・ラツチ５６の
第２の部分をカツシエ・ストア４０の読出し／書
込みアドレス入力に結合するカツシエ・ストア・
アドレス回線４４により制御される。このセクシ
ヨンはカツシエ制御装置４９からの回線４５上の
レベル・ストローブ信号により制御される。

カツシエ・メモリー装置の検索は、CPUが要
求するデータのタツグ・アドレスの基本登録簿５
４におけるタツグ・アドレスとの比較を含む。カ
ツシエ・アドレス５６の第２の部分は要求された
データの列アドレスからなり、回線５８を介して
基本登録簿５４の読出し／書込みアドレス入力と
接続される。これにより基本登録簿の選択された
列の４つのレベルに記憶されたタツグ・アドレス
が４つのデータ出力回線１２０を介してコンパレ
ータ５５の第１のデータ入力側に与えられる。コ
ンパレータ５５の第２のデータ入力は回線６０を
介してカツシエ・アドレス・ラツチ５６の第１の
部分と接続される。コンパレータ５５は所要のデ
ータのタツグ・アドレスを選択された列の４つの
レベルに記憶されたタツグ・アドレスと比較し、
マツチングが見出されるどのレベルに対しても突
合せ信号を生成する。これ等の突合せ信号はカツ
シエ制御装置４９と接続され、この制御装置が回
線５１にブロツク選択信号を生成するために使用
される。このブロツク選択信号は、突合せたレベ
ルと対応するブロツクとセクシヨンのデータがカ
ツシエ・ストア４０のデータ出力からデータ・ラ
ツチ４３に切換えられるように第２のスイツチ４
２を付勢する。

コンパレータ５５からの突合せ信号が存在しな
い場合は、カツシエ制御装置４９は回線６２上に
ヒツト失敗信号を生成する。この信号はポート制
御装置６３に対し回線６４上にストローブ割込み
信号を生成することを通知して、主記憶装置に要
求されたデータを検索させる。この信号は、
CPUと主記憶装置間でインターフエース装置と
して作用するシステム制御装置に行く。

データが主記憶装置から検索される時、このデ
ータは回線４８上の第１のスイツチ４１に対する
入力側に現われる。同時に、これは回線４８の延
長路を介して第２のスイツチ４２に対する別のデ
ータ入力側に転送される。データが検索された
時、回線６５上の信号Ｓ｜DAはポート制御装置６
３からカツシエ制御装置４９へ送られる。この時
カツシエ制御装置は回線４８上のデータを回線５
１上のブロツク選択信号を介して第２のスイツチ
４２に切換える。又このためこのデータは回線５
３上のロード信号を介してデータラツチ４３にロ
ードされる。最後に、この制御装置は、所要デー
タがデータ・ラツチ４３にあることをCPUに通
知する回線６６上のデータ使用可信号を生成す
る。

今ここで、ヒツト失敗が生じたこと、および要
求されたデータが主記憶装置から検索されてカツ
シエ・ストアに記憶される用意があることとしよ
う。その対応するタツグ・アドレスは基本登録簿
において記憶される用意がある。基本登録簿およ
びカツシエ・ストアにおけるこれ等２つの項目を
記憶する列は、列アドレス部即ちカツシエ・アド
レス・ラツチ５６の第２の部分により決定され
る。回線５８は基本登録簿５４に対して列選択情
報を送り、回線４４は同じ情報をカツシエ・スト
ア４０に送る。基本登録簿におけるレベルおよび
カツシエ・ストアにおけるセクシヨンも又選択さ
れねばならない。LRUハードウエア・サブシス
テムに構成された手続は、空白レベルを探査する
ことおよびもし空白レベルが見出されればここに
データを記憶することである。もし空白レベルが
なければ、カツシエ制御装置はLRUレベルを決
定し、このデータを主記憶装置から検索されたデ
ータで置換する。統計的な分析によれば、このよ
うな方式は、あるメモリー・アクセス数に対する
ヒツト失敗の比率が減少するため、ラウンド・ロ
ビン方式の転置よりもCPUの全操作速度を増進
することが判つた。コンピユータのプログラムに
対するオペレーシヨンを調べた結果、他のデータ
ワードより更に瀕繁に使用される１つのデータ・
ワードが再び使用される確率が高いことが判る。
カツシエ装置のメモリー・チツプが主記憶装置の
それよりも早いため、ヒツト率が高いと云うこと
は操作が早いと云うことになる。

「殆んど使用されない」ハードウエア・システ
ムについては第４図に詳細を示す。第２図、第４
図および第５図によれば、システムは下記の如く
作用する。カツシエ制御装置４９がしなければな
らない第１の事柄は、基本登録簿５４の選択され
た列におけるレベルが空白表示されるかどうかを
知るため検査することである。このためには、カ
ツシエ制御装置は充／空アレー６６を検査する。
望ましい実施例においては、この装置は４×512
ビツトのランダム・アクセ・メモリーアレーであ
る。スイツチ６７はその一方の出力を充／空アレ
ー６６のアドレス・入力側に接続させ、他の出力
をこのアレーのデータ入力側に接続させる。この
スイツチに対する入力は、カツシエ・アドレス・
ラツチ５６に記憶された絶対アドレスのビツト１
３乃至２１からなる充／空アドレス信号からな
る。カツシエ・アドレス・ラツチの第２の部分か
らのこれ等のビツトは回線６９によつて前記スイ
ツチに接続される。このスイツチに対する他の入
力はカツシエ制御装置からの回線６８上のクリア
信号である。この信号は２つの部分、即ち充／空
アレーの512行のどれがアドレス指足されるかを
表示する９ビツトと、この選定された行のどのビ
ツトがクリアするかを示す２ビツトからなる。ス
イツチ６７の目的は、充／空アレーアドレスかク
リア信号のいずれかを充／空アレーのアドレス入
力側に切換えることである。充／空列のデータ入
力は選定されたビツトをクリアするように条件付
けされている。

前記アレーのデータ出力はカツシエ制御装置４
９と接続された回線７０上のLEVEL Ｆ／Ｆ信
号である。充／空アレー６６の各行は基本登録簿
５４の１つの列と対応する。特定の列の空白状態
レベルについて検査するため、カツシエ制御装置
４９は回線６９上の充／空アドレスをスイツチ６
７を介して充／空アレーのアドレス入力側に切換
えさせる。この時この列はデータ出力側の選定列
におけるデータをLEVEL Ｆ／Ｆ信号として提
供する。これ等４つのビツトの各状態は次にカツ
シエ制御装置４９により読出され、基本登録簿５
４の対応する列に空白状態のレベルが存在するか
どうかについて決定する。もし空白レベルが存在
すれば、回線５９にLEVEL STROBE信号が生
成されて、回線５８上のアドレスにより選定され
た列の空白レベルに回線５７を介して指向される
カツシエ・アドレス・ラツチ５６の第１の部分の
タツグ・アドレスを案内する。

前述の動作後空白レベルが見出せなければ、カ
ツシエ制御装置４９はLRUアレー７２を読出し
てLRUレベルを決定する。このLRUアレーは本
実施例においては６×512ビツトのランダム・ア
クセス・メモリーである。その目的は、基本登録
簿５４における各列のLRUレベルを符号化した
複数のビツトを記憶することである。望ましい実
施態様においては、各行が基本登録簿５４の特定
の列と対応する512行がある。各行の６ビツトは、
一時に２つ宛取上げる４つの事象の組合せ数を表
わす。各ビツト、基本登録簿５４の特定の列にお
ける４レベルの内の２つの間の如き最後の使用の
相対的時間を表わす。

第５図によればこの相対的使用の概念が更に詳
細に理解されよう。LRU法で用いられた基本登
録簿の異なるレベルを表わすいくつかのビツト・
パターンが示される。どの行における第１のビツ
トも、基本登録簿とカツシエ・ストアのレベルＡ
とＢ（即ち、１と２）間の如き状態を表わしてい
る。この第２のビツトはレベルＡとＣ間の如き状
態を、又第３のビツトはレベルＡとＤ間の如き状
態を示す…と云う具合である。ある特定のビツト
における零は、第２のレベルが最後に使用されて
以来最初のレベルが使用されたことを意味する。
１は逆の状態を示す。このように、与えられたコ
ードの１段目においては、レベルＢが最後に使用
されて以来レベルＡが使用され、レベルＣが最後
に使用されて以来Ａが使用され、ＡはＤより最近
使用され、ＢはＣより、ＢはＤより、ＣはＤより
最近使用されたことを示す。このコードはＤが
LRUレベルで使用されることを示す。コードの
第２段目は、Ｂ又はＣ又はＤが最後に使用されて
以来Ａが使用されなかつたことを最初の３ビツト
の１が意味するため、ＡがLRUレベルであるこ
とを表示する。

特定のレベルにおいて１つのマツチングが見出
される度に、このレベルに対するコードが更新さ
れてこれが最も後で使用されたことを表示する。
このためには、適当なビツト・パターンがその列
と対応する行に対するLRU列内の３ビツトに強
制されることになる。記憶されたビツト・パター
ンは突合せたレベルと他の全てのレベル間の状態
を表わす。このため、レベルＢにおける突合せの
ためには、１がビツトABに強制され、零がその
BCとBDに強制されることになる。このことは、
レベルＢが最後に使用されて以来レベルＡが使用
されなかつたこと、およびレベルＣとＤが最後に
使用されて以来レベルＢが使用されたことを示
す。

LRUビツトはカツシエのビツト失敗と同時に
更新されるが操作のシーケンスは若干異なる。最
初にカツシエ制御装置４９が充／空アレーを読出
して選定された列内の空白レベルがあるかどうか
を確認する。もしあれば、空白レベルが充填され
LRUコードが更新されてこのレベルを最も後で
使用したものと表示する。もし空白レベルがなけ
れば、カツシエ制御装置４９が選択された列に対
してLRUビツトを読出し、そのLRUレベルを決
定する。データが主記憶装置から来る時、これは
前記LRUレベルと対応するカツシエ・ストア４
０のセクシヨンに記憶されることになる。この対
応するタツグ・アドレス・ビツトはこの時基本登
録簿５４のLRUレベルに記憶され、カツシエ制
置装置４９は選定された列に対してLRUビツト
を更新して最も後で使用されたものとして記憶さ
れた許りのレベルを表示する。

LRUシステムに対するハードウエアはそれ自
体は簡単である。第４図によれば、LRUラツチ
７３は回線７４を介してカツシエ・アドレス・ラ
ツチ５６に記憶された絶対アドレスの第２の部分
からLRUアドレス信号（ビツト１３乃至２１）
を受取る。LRUラツチは回線７６を介してLRU
アレー７２のアドレス入力７５側にLRUアドレ
スを保持するように作用する。このLRUアレー
のデータ出力はカツシエ制御装置４９と接続され
る回線７７上のLRUレベル信号である。カツシ
エ制御装置４９は、16進フリツプフロツプ７８に
アドレス指定された行に対する６つのLRUビツ
トを一時的に記憶する。フイールド・プログラム
可能な論理アレー７９は、回線８１上のBLOCK
LOAD信号により信号されるカツシエのヒツト
失敗と同時に、前記６つのLRUビツトをバス５
９上のLEVEL STROBE信号に交換する。しか
し、もし回線７０上のLEVEL Ｆ／Ｅ信号が空
白レベルの存在を表示すれば、バス５９上の
LEVEL STROBE信号は検索されたデータを空
白レベルへガイドする。FPLA７９は又丁度記憶
した許りのレベルと対応するLRUビツトを更新
する。この更新は適正ビツト・パターンをバス８
０上のLRUデータ更新信号を介してLRUアレー
に書込むことにより達成される。影響を受けた状
態で記憶された列に対するLRUビツトはこの時
このレベルが最も後で使用されたことを表示す
る。回線５９上のLEVEL STROBE信号はどの
空白レベルにも指向されるが、回線７０上の
LEVEL Ｆ／Ｅ信号が空白レベルの存在を表示
することを前提とする。フイールド・プログラム
可能なロジツクアレー７９は回線８１上の
LOAD BLOCK信号を介してヒツト失敗があつ
たことを通知する。この信号は図示しないカツシ
エ制御装置の別の部分におけるヒツト／ヒツト失
敗フラツグから生じる。

本出願は、カツシエ制御装置の他の部分は当業
者にとつては明らかであるものと信じる。更に、
これ迄に述べたシステムに対する一連の事象を実
行するゲート、フリツプフロツプ、その他の素子
の構成もいかなる構成でもよい。

回線８２におけるチツプ選択出力は、LRUア
レーの個々のメモリー・チツプを選択するため
FPLAによつて使用される。

回線８３と８４上の信号ENABLE１および
ENABLE２はそれぞれ第４図のFPLA７９を構
成する２つの別個のFPLAチツプに対するチツプ
選択信号である。これ等の信号はカツシエ制御装
置の他の各部から入る。

突合せができた場合は、回線８５上の突合せ信
号がFPLAに入り、回線８０上で適正なLRU更
新ビツト・パターンに変換されて突合されたレベ
ルに対するLRUビツトを更新してこれを最も後
で使用されたものとして表示する。

第６図はFPLAチツプ７９の内部構成を示す論
理回路図である。各チツプは16の入力と８つの出
力を有する。各出力は48迄のプログラム可能な
AND機能のプログラム可能なOR機能であり、
ORゲート８６と８７はチツプ内の８つの48入力
ORゲートの内の２つを表わす。各ORゲートの
各入力は溶断可能なリンクを介して48のANDゲ
ートの内の１つの出力側に接続される。各AND
ゲートは32入力を有し、各入力は溶断可能なリン
クを介して16の入力の各々の反転および非反転バ
ージヨンと接続される。FPLA内のある溶断可能
リンクを選択的に破壊することにより、手早くで
きる安価な優先回路網が形成できる。

第７図および第８図はカツシエ制御装置４９の
FPLAチツプ７９の真理値表を示し、これから破
壊すべきリンクを選択するため使用される論理式
を得ることができる。第８図の真理値表の左方の
HIT、LRU、HCLRと表示された３つのセクシ
ヨンはあらゆるレベルの的中を処理し、LRUレ
ベルを決定し、ある状況の下でカツシエを完全に
クリアすることにそれぞれ対応する諸機能を表わ
す。真理値を理解するため、カツシエ・メモリー
が２つの半部に分割され、レベル１と２が最初半
部を、又レベル３と４が２番目の半部を構成する
ことを理解しなければならない。この構成のた
め、カツシエの半部における不測の故障において
も各動作が続行し得るようにCPUがカツシエの
片方の半部とは独立的に他の半部を使用すること
ができる。このように、レベル１におけるヒツト
に対する出力機能番号１に対応する第８図の機能
線０がビツトＳ1/2に対する１のハイ状態のみを
含む。この機能の入力がBLOCK LOADと
ENABLE２が不能条件にありENABLE１がハイ
であることを示している。更に、1入力にお
けるローにより示される如きレベル１においてヒ
ツトが存在した。この入力パターンは、カツシエ
の最初の半部が使用状態にあることおよびレベル
１においてヒツトがあつたことを示す。従つて、
FPLAの機能はレベル２よりも更に最初使用され
たものとしてレベル１を更新することである。こ
れを生じる出力のパターンは下記の如くである。
第７図および第８図の両図における線Ｏについて
見れば、２つのFPLAチツプに対する出力機能は
全ての６チツプ選択出力についてローとなること
が判る。これ等の信号はLRUアレーの全てのメ
モリー・チツプを使用可能状態にする。又、第８
図の出力機能１のＳ1/2においてもハイの状態が
存在する。このハイの状態は、レベル１がレベル
２よりも最近使用され、バス８０を介して第４図
のLRUアレー７２にジヤムされることを示す。

第７図および第８図の線４はカツシエの両方の
半部が作動中である場合を示す。BLOCK
LOADはローの状態で、ヒツトが生じたことを
表示し、ENABLE１と２は共にハイの状態でカ
ツシエの両半部が作動中であることを示す。
HIT1入力におけるローの状態は、レベル１にお
けるヒツトを表示する。ビツトＳ1/2、1/3および
１／４における３つのハイの状態は、レベル２、３
および４が最後に使用されたためレベル１が使用
されたことを表示する。ここで、LRUコーデイ
ングの一例としての第５図の論議においては零は
他のレベルが最後に使用されたためレベル１が使
用されたことを表示するため使用されたことに注
目すべきである。この条件に対して零と１のどち
らを選択するかは全く任意である。

多重プロセサ・システムはスループツトを高め
るために構成される。このような構成において
は、システムにおける一方のプロセサは、１つ以
上の他のプロセサのカツシエに同時に記憶される
主記憶装置のデータを変更することができる。こ
のような場合、その古いデータをそのカツシエに
有するプロセサがその操作中にこのデータを照会
する場合にシステムのエラーが生じ得る。カツシ
エのアクセス操作速度を下げることなくこのよう
なシステムのエラーを防止するため、本発明にお
いては選択的クリア装置が使用される。前述の如
く、従来技術のシステムは、別のプロセサにより
カツシエ内のあるデータが古くなつたある条件下
でカツシエ全体をクリアすることになるクリア装
置を用いていた。古いデータを含む場所のみをク
リアすることによつて、この過度のクリア動作は
除くことができる。

従来技術は選択的クリア装置を開示するが
LRUサブシステムと関連づけたものではない。
第２図に示した選択的クリア・サブシステムは複
写登録簿９５、コンパレータ９６およびその関連
する入出力スタツクからなる。複写登録簿９５は
基本登録簿と同じ方法で構成される。これはカツ
シエ・ストア４０に記憶された全データについて
複写タツグ・アドレスを含む。これ等のタツグ・
アドレスは、これ等が基本登録簿５４にロードさ
れると同時に複写登録簿９５のロードされる。こ
れは回線９７とバツフア９８と書込みスタツク９
９により達成される。回線９７はカツシエ・アド
レス・ラツチ５６の第１と第２の部分をバツフア
９８に接続する。即ち、この回線はバツフア９８
を所要のデータに対する絶対アドレスのビツト０
乃至２１でロードする。バツフア９８はこのアド
レスが書込みスタツク９９に記憶できる迄これを
保持する。書込みスタツクは記憶されたアドレス
を２つの部分に分割するための２つの出力を有す
る。第１の出力は、回線１００を介して複写登録
簿９５のデータ入力側にタツグ・アドレス・ビツ
ト０乃至１２を送る。第２の出力は、回線１０１
を介して複写登録簿９５のアドレス入力に対して
複写列アドレス即ち絶対アドレスのビツト１３乃
至２１を送る。カツシエ制御装置４９からの回線
１０２における複写LEDEL STROBE信号はこ
のタツグ・アドレスを回線１０１上の複写列アド
レス信号により選択された複写登録簿９５の列の
適正なアドレスに指向させるように作用する。

データの変化の場所をフラツグするため、他の
プロセサによつて変更された主記憶装置における
全データの絶対アドレスを知ることが必要であ
る。これ等の変化の通知アドレスは回線１０３上
をバツフア１０４に入る。これ等のアドレスは、
その処理がカツシエの他の部分の処理と同時に生
じ得るように変更通知スタツク１０５に記憶され
る。変更通知スタツク１０５も又アドレスを２つ
の部分に分割する目的のための２つの出力を有す
る。回線１０６上の第１の出力は変更されたアド
レスのタツグ・アドレス・ビツト０乃至１２をコ
ンパレータ９６の第１のデータ入力側に送る。回
線１０１の第２の出力は、列アドレス・ビツト１
３乃至２１を複写登録簿９５のアドレス入力側に
送る。このように、各々の変更通知アドレスがス
タツク１０５から処理される時、そのビツト１３
乃至２１は検査のため複写登録簿９５の特定の列
を選択する。この列の４つのレベルのタツグ・ア
ドレスは回線１０７を介してコンパレータ９６の
第２のデータ入力側に接続される。コンパレータ
はこれ等のタツグ・アドレスを変更通知アドレス
のタツグ・アドレスと比較し、もしマツチングが
見出されれば、突合されたタツグ・アドレスは回
線１０９上の複写突合せ信号として列変更スタツ
ク１０８に対して送られる。列変更スタツク１０
８はこのタツグ・アドレスと回線１０１上の変更
通知アドレスのビツト１３乃至２１を記憶する。
この時この２つの部分は１つのアドレスとして記
憶される。カツシエ制御装置４９は回線１１０を
介して変更されたアドレスを読出し、この情報か
ら回線６８上にクリア信号を生成する。クリア信
号は、カツシエ・ストア４０における古いデータ
を指示する基本登録簿５４におけるレベルと対応
する充／空白アレー６６におけるビツトをクリア
するため使用される。

本発明は本文に開示された特定の望ましい実施
態様により記述したが、当業者にとつては多くの
変更が可能であることは明らかであろう。同様な
方法で同様な装置を用いて同じ目的を達成するこ
れ等の変更例は当書の特許請求の範囲内に包含さ
れるべきものである。

【図面の簡単な説明】

第１図は１つの主記憶装置を共用する２プロセ
サ・データ処理システムを示す図、第２図は各プ
ロセサのカツシエ・メモリーのブロツク図、第３
図は基本登録簿内の場所とカツシエ・ストアの場
所間の対応性を示すメモリー・マツプ、第４図は
LRU更新サブシステムを実施した回路図、第５
図はLRU符号化方式を示す表、第６図はFPLA
チツプの論理回路図、および第７図および第８図
はFPLAチツプの転送機能を示す真理値表であ
る。 １０……システム・コントローラ、２０……主
記憶装置、３０……カツシエ装置、３１，９５…
…複写登録簿、３２……オペレーシヨン装置、３
３，６３……ポート制御装置、３４……Ｉ／Ｏ制
御装置、４０……カツシエ・ストア、４１，４
２，５７，６７……スイツチ、４３……データ・
ラツチ、４９……カツシエ制御装置、５４……基
本登録簿、５５……コンパレータ、５６……カツ
シエ・アドレス・ラツチ、６６……充／空アレ
ー、７２……LRUアレー、７８……16進フリツ
プフロツプ、７９……ロジツクアレー、８６，８
７……ORゲート、９６……コンパレータ、９
８，１０４……バツフア、９９……書込みスタツ
ク、１０５……変更通知スタツク、１０８……列
変更スタツク。

Claims (1)

1. 【特許請求の範囲】 １ 主記憶装置と、プログラムの実行に必要な時
   前記主記憶装置内に記憶されたデータワードを要
   求する中央処理装置（CPU）とを有するデータ
   処理システムにおける、前記CPUに対するカツ
   シエ・メモリー装置であつて、 (a) 前記CPUにより使用される複数のデータワ
   ードを記憶しアクセスするための、各々が前記
   データ・ワードを記憶する複数のブロツクに
   夫々分割された複数のセクシヨンを有する記憶
   装置と、 (b) 各々が前記記憶装置の１つのブロツクと対応
   する複数の列に分割され、各々前記記憶装置の
   １つのセクシヨンと対応する複数のレベルを有
   し、前記記憶装置に記憶されている主記憶装置
   におけるデータ・ワードを識別するアドレスを
   記憶するための装置と、前記記憶されたアドレ
   スを前記CPUにより要求されるデータ・ワー
   ドのアドレスと比較するための装置と、要求さ
   れたデータ・ワードが前記記憶装置に存在して
   前記データがどのレベルにおいて見出されたか
   を表示する時、突合せ情報を生成するための装
   置とを含む、登録簿装置と、 (c) マツチングが生じた時要求されたデータワー
   ドを前記記憶装置から前記CPUへ供給させる
   ための装置と、マツチングミスが生じた時要求
   されたデータ・ワードを前記主記憶装置から検
   索させるための装置と、該検査されたデータ・
   ワードをCPUに対して供給させるための装置
   と、前記検索されたデータ・ワードを前記記憶
   装置に記憶させるための装置と、検索されたデ
   ータ・ワードを指標付けするアドレスが前記登
   録簿装置のLRUレベルに記憶されるべきこと
   を指令するための装置と、マツチングが生じた
   時新らしい最も後で使用されたレベルにおいて
   更新データを生成してこれを記憶するための装
   置とを含む、制御装置と、から成り、 前記制御装置の前記指令するための装置が、そ
   れぞれが前記登録薄装置の１つの列を表し、それ
   ぞれが前記対応する列の前記レベルの時間的使用
   順序を符号化するためのLRUビツトを記憶し、
   該LRUビツトの読み出しと更新されたLRUビツ
   トの書き込みのために独立にアドレス指定可能
   な、複数の行に分解されたランダム・アクセス・
   メモリーLRUアレーを含み、 前記行のLRUビツトのそれぞれが前記登録簿
   装置の１対のレベルを表し、LRUビツトの１つ
   の２進状態は前記複数のレベルの内の１つが前記
   順序以前に使用されたことを意味し、反対の２進
   状態は逆の状況を意味し、LRUビツトは前記登
   録簿装置の前記複数のレベルの使用の総ての可能
   な組み合わせを表すために十分な数を有すること
   を特徴とする、 カツシエ・メモリー装置。