JPS58501645A - 最下位プライオリテイ置換え回路を使用するキヤツシユ・メモリ - Google Patents

Abstract

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

Description

【発明の詳細な説明】 最下位プライオリティ置換え回路を使用するキャッシュ・メモリ 技術分野 本発明は計算機システムに、細目的には新らしい情報を記憶するロケーションが キャッシュ・メモリ中の最下位プライオリティを有するワードのロケーションで あるキャッシュ・メモリを使用するシステムに関する。

発明の背景 最近の計算機システムは単一の大容量メモリが追従し得ないような高速度−の動 作が可能なプロセッサを使用している。このため小容量の高速キャッシュ・メモ リがプログラムの実行速度を改善するために大容量のメイン・メモリと共に使用 されているのが普通である。キャッシュ・メモリは限定された個数のインストラ クションまたはデータ・ワードを記憶しており、メモリの読み出し操作毎にキャ ッシュ・メモリ中に情報が存在するか否かが調べられる。情報が存在する場合に はその情報はキャッシュ・メモリから読み出される。もしキャッシュ・メモリ中 に情報が存在しない場合にはメイン・メモリから読み出される。情報がメイン・ メモリから読み出されねばならない場合には、新らしい情報はキャッシュ・メモ リ中の既存の情報と置き換えられねばならない。キャッシュ・メモリ中の新らし い情報を記憶するのに適したロケーションは幾つかの広く使用されている置き換 えアルゴリズム（例えばランダム置き換え、最も以前に使用されたものと置き換 える等）の内の１つにより定められる。

一般に最も以前に使用されたものと置き換えるアルゴリズムは最も効率のよいア ルゴリズムであると考えられている。しかしどのロケーションが最も以前に使用 されたワードを含んでいるかの決定を、多大の時間を要することなく経済的に引 き合う仕方で実現することは困難であるとされていた。

発明の要旨 本発明に従うキャッシュ・メモリ・システムはデータ・ワードのグループを含む 幾つかのセクションに分割されている。各セクションはその中に記憶されたワー ドが最後に使用された時刻に従って決定される相対的プライオリティを保持して いるプライオリティ回路を有している。

キャッシュ・メモリ中に挿入されねばならないメイン・メモリ・ワードを受け取 ったときキャッシュ・メモリを更新するのに要求される時間は、該ワードを１つ のセクション中に記憶させると同時に最も低いプライオリティ・ワードをより高 いプライオリティ・セクションからより低いプライオリティ・セクションに移動 することにより減少させることが出来る。

本発明の一実施例では、データ処理システムはメイン・メモリ・アドレス信号を 発生することによりデータ・ワードを要求するプロセッサと、メイン・メモリと キャッシュ・メモリ・システムより成っている。キャッシュ・メモリ・システム はキャッシュ制御回路と第１および第２のキャッシュ・メモリより成る。１つ以 上のキャッシュ・メモリを有するキャッシュ・メモリ・システムは現場でシステ ムを拡張することを許容する。また各々のキャッシュ・メモリは一つのＬＳＩ回 路として実現することが可能である。各キャッシュ・メモリはキャッシュ・デー タ・ワード（これはメイン・メモリ中に記憶されたワードの複製である）と相応 するメイン・メモリ・アドレスを記憶している。プロセサはメイン・メモリ・ア ドレス信号を伝送することによりデータ・ワードを要求する。第１および第２の キャッシュ・メモリの内容を調べて要求されたワードがその中に存在するか否か が決定される。キャッシュ・メモリが所望のワードを含んでいる場合には、該キ ャッシュ・メモリはキャッシュ制御回路に整合信号を伝送する。もし所望のワー ドが含まれていない場合にはキャッシュ・メモリは不整合信号を伝送する。キャ ッシュ制御回路が両方のキャッシュ・メモリから不整合信号を受信すると、該制 御回路は２つの動作を実行させる。第１の動作期間中、メイン・メモリはメイン ・メモリ・アドレス信号に応動して所望のメイン・メモリ・ワードにアクセスし てプロセッサおよび第１のキャッシュ・メモリに伝送する。またこの第１の動作 期間中、第１のキャッシュ・メモリは記憶された関連するメイン・メモリ・アド レスを有する最もプライオリティの低いキャッシュ・データ・ワードにアクセス して、該ワードを第２のキャッシュ・メモリに伝送する。第２の動作期間中、第 １のキャッシュ・メモリはアクセスされたメイン・メモリ・ワードとメイン・メ モリ・アドレス信号を先にアクセスされた第１のキャッシュ・メモリ・ロケーシ ョン中に記憶し、第２のキャッシュ・メモリは第１のキャッシュ・メモリからの 最もプライオリティの低いキャッシュ・データ・ワードと記憶されたメイン・メ モリ・アドレスを先にアクセスされた第２のキャッシュ・メモリのロケーション 中に記憶する。

キャッシュ制御手段は第１のキャッシュ・メモリからの不整合信号および第２の キャッシュ・メモリからの整合信号に応動してキャッシュ・メモリ内で実行すべ き２つの動作を実行させる。第１の動作期間中、第１のキャッシュ・メモリは最 も低いプライオリティのキャッシュ・データ・ワードおよび関連するメイン・メ モリ・アドレスにアクセスして第２のキャッシュ・メモリに伝送し、第２のキャ ッシュ・メモリは整合した記憶されているメモリ・アドレスと関連するキャッシ ュ・データ・ワードを第１のキャッシュ・メモリおよびプロセッサに伝送する。

第２の動作期間中、第１のキャッシュ・メモリは第２のキャッシュ・メモリから のキャッシュ・データ・ワードとアドレスをそれより以前には最もプライオリテ ィの低いキャッシュ・データ・ワードおよびメモリ・アドレスによって使用され ていたメモリ・ロケーション中に記憶する。また第２の動作期間中、第２のキャ ッシュ・メモリは第１のキャッシュ・メモリから伝送されたキャッシュ・データ ・ワードと関連するアドレスを記憶する。

各々のキャッシュ・メモリは整合メモリおよびデータ・メモリを含んでいる。整 合メモリはメイン・メモリ・アドレスを記憶しており、データ・メモリはキャッ シュ・データ・ワードを記憶している。整合メモリはプロセッサが送出するメイ ン・メモリ・アドレス信号の各々の組を比較し、整合または不整合を指示する。

整合が生じると、整合メモリはアドレスをデータ・メモリに伝送し、それによっ て所望のキャッシュ・データ・ワードにアクセスし、伝送する。コンテント・ア ドレッサブル・メモリが整合メモリを実現するのに使用出来る。

更に、各々のキャッシュ・メモリは各キャッシュ・データ・ワードが第１のキャ ッシュ・メモリ内において何時アクセスされたかに関する各キャッシュ・データ ・ワードのプライオリティを保持するプライオリティ回路を有している。該プラ イオリティ回路により保持されているプライオリティはキャッシュ・データ・ワ ードの使用時刻に関する履歴である。最もプライオリティの低いキャッシュ・デ ータ・ワードは最も以前に使用されたワードである。

キャッシュ・メモリ・システムは第１のセクションカ１第２のセクション中に記 憶されているワードより高いプライオリティを有するワードを含むようにキャ゛ ンシュ・データ・ワードをキャッシュ・メモリ・システム中に記憶することによ りアクセスされ、更新される。プロセッサがデータ・ワードにアクセスするとき 、各セクションは所望のワードがそのセクション中に含まれているかどうかがチ ェックされる。所望のワードがいずれのセクション中にも含まれていない場合に は、メイン・メモ「ツカ−アクセスされ、所望のワードはプロセッサおよび第１ のセクションに伝送される。アクセスされたメイン・メモリ・ワードは第１のセ クションの最もプライオリティの低いキャッシュ・データ・ワードを置き換える のに使用され、最もプライオリティの高いキャッシュ・データ・ワードとなる。

このとき２番目のプライオリティの低いワードは最もプライオリティの低いキャ ッシュ・データ・ワードとなる。それより前に最もプライオリティが低かったキ ャッシュ・データ・ワードは第２のセクションに伝送され、そこで該データ・ワ ードは第２のセクションの最もプライオリティの低いワードと入れ替わり、該セ クションにおける最もプライオリティの高いワードとなる。このとき第２のセク ション中で２番目に低いプライオリティを有していたワードは最もプライオリテ ィの低いワードとなる。

要求されたワードが第２のセクション中に存在することが分ると、第２のセクシ ョンからのワードがプロセッサに伝送され、第１のセクションの最もプライオリ ティの高いワードとして第１のセクション中に記憶される。

このとき第１のセクションの最もプライオリティの低いワードは第２のセクショ ンに転送され、そこで該ワードは第２のセクションの最もプライオリティの高い ワードとなる。最もプライオリティの低いワードは最も以前に使用されたワード で、最もプライオリティの高いワードは最も最近使用されたワードである。

第１図は本発明のデータ処理システムのブロック図、第２および３図は第１図の ＬＲＵ回路１０５を更に詳細に示す図、第４図は第１図のＬＲＵ回路１０４のコ ンテント・アドレッサブル・メモリを更に詳細に示す図、第５図は第３図のプラ イオリティ回路の動作例を示す表である。

詳細な説明 第１図に示すデータ処理システムにおいてデータおよびインストラクション・ワ ードはメイン・メモリ１０２およびキャッシュ・システム１００のメモリ・ロケ ーション中に記憶されている。プロセッサ１０１はアドレス・バス１１２を介し てアドレスを、制御バス１１３を介して制御信号を伝送することによりこれらの メモリ・ロケーションの内容を読み出す。キャッシュ・システム１００は制御シ ーケンサ１０３、ＬＲＵ回路１０４．１０５および１０６、キャッシュ・データ ・メモリ１０７．１０８および１０９、ならびにキャッシュ・データ・ゲート回 路１１０１り成る。ＬＲＵ回路およびキャッシュ・データ・メモリは対を成して おり、各対はキャッシュ・メモリ・ユニットを形成している。例えばＬＲＵ回路 １０４およびキャッシュ・データ・メモリ１０７が１つのキャッシュ・メモリ・ ユニットを形成している。

キャッシュ・データ・メモリ中に記憶されたキャッシュ・データ・ワードはグル ープに分割されており、各グループは同じ時点においてプロセッサ１０１により 最後に読み出されたキャッシュ・データ・ワードを含んでいる。各グループはキ ャッシュ・データ・メモリの内の１つに記憶されている。例えば最も最近使用さ れたワードのグループはキャッシュ・データ・メモリ１０７中に記憶されており 、最も以前に使用されたワードのグループはキャッシュ・データ・メモリ１０９ 中に記憶されている。プロセッサ１０１が読み出しを行うとき、キャッシュ・デ ータ・ワードは、メモリの使用時刻履歴を保持するためキャッシュ・データ・メ モリ間で転送される。例えばメイン・メモリ１０２から１つのワードを読み出す 必要がある場合、このメイン・メモリ・ワードはキャッシュ・データ・メモリ１ ０４の最も以前に使用されたキャッシュ・データ・ワードの位置を占め、置き換 えられたキャッシュ・データ・ワードはキャッシュ・データ・メモリ１０８に転 送される。

読み出し操作期間中、プロセッサ１０１により伝送されたアドレスはＬＲＵ回路 １０４．１０５、および１０６によってチェックされ、アドレス指定されたワー ドがキャッシュ・データ・メモリ１０７．１０Ｂまたは１０９中に夫々含まれて いるか否かが決定される。

例えばＬＲＵ回路１０４がアドレス指定されたワードはキャッシュ・データ・メ モリ１０７中に含まれていると判定すると、該回路１０７はこのワードのアドレ スをケーブル１３１を介してキャッシュ・データ・メモリ１０７に伝送する。キ ャッシュ・データ・メモリ１０１はこのアドレスに応動して所望のワードにアク セスし、これをキャッシュ・データ・ゲート回路１１０に伝送する。キャッシュ ・データ・ゲート回路１１０から所望のデータ・ワードはデータ・バス１１１を 介してプロセッサ１０１に伝送される。ＬＲＵ回路１０４がアドレス・バス１１ ２を介してプロセッサ１０１により伝送されたアドレスと整合しないと判定する と、該回路１０４は制御シーケンサ１０３に導線１１４を介して“ｌ“信号を伝 送し、不整合であったことを指示する。他のＬＲＵ回路も同様な仕方で動作する 。

関連するキャッシュ・データ・メモリが所望のメモリ・ワードを有しているか否 かをチェックすることに加えて、ＬＲＵ回路は関連するキャッシュ・データ・メ モリ中の各ワードのプライオリティを保持する。このプライオリティ情報は関連 するキャッシュ・データ・メモリにアクセスする毎にＬＲＵ回路によって自動的 に更新され、キャッシュ・メモリ中のどのワードが最も以前に使用されたワード であるかを規定する。

システムの動作を以下に述べる３つの例によって更に説明する。第１の例では所 望のワードはキャッシュ・システム１００中には存在せずメイン・メモリ１０２ から読み出さねばならないものと仮定している。所望のワードがキャッシュ・シ ステム１００中に存在しないと、すべてのＬＲＵ回路は整合線路１１４．１１５ および１１６を介してゝゝ１”信号を伝送する。これら信号に応動して制御シー ケンサ１０３はメイン・メモリ１０２にアクセスし所望のワードを入手する。メ イン・メモリ１０２から読み出されたワードは最も最近使用されたワードである ので、該ワード、はキャッシュ・データ・メモリ１０１中に加えられ、キャッシ ュ・データ・メモリ１０７からの最も以前に使用されたワードはキャッシュ・デ ータ・メモリ１０８中に書き込まれ、キャッシュ・データ・メモリ１０８の最も 以前に使用されたワードはキャッシュ・データ・メモリ１０９中に書き込まれる 。キャッシュ・データ・メモリ１０９の最も以前に使用されたワードは前述の動 作が完了した時点においては最早キャッシュ・メモリ１００中に存在しない。

キャッシュ・メモリ・システム１００の動作の第２の例にあっては所望のワード はキャッシュ・データ・メモリ１０７中に存在するものと仮定する。所望のワー ドはキャッシュ・データ・メモリ１０７中に存在するので、メイン・メモリ１０ ２中のワードにアクセスしたりキャッシュ・データ・メモリ１０１からキャッシ ュ・データ・メモリ１０８にメモリ・ワードを転送する必要はない。

その代りにＬＲＵ回路１０４はデータ・メモリ１０７中のメモリ・ワードの使用 順序を適切に反映するよう回路１０４の内部に記憶されたプライオリティ情報を 単に更新することになる。

第３の例にあっては、所望のメモリ・ワードはデータ・メモリ１０８中に存在す るものと仮定する。この場合、。

ＬＲＵ回路１０５はアドレス・バス１１２を介してプロセッサ１０１に伝送され たアト１ノスと整合し、データ・メモリ１０８をして所望のワードにアクセスし 、データ・ゲート回路１１０に該ワードを伝送させる。制御シーケンサ１０３は 次にこの所望のデータ・ワードをデータ・ゲート回路１１０によりデータ・バス １１１を介してプロセッサ１０１に伝送させる。この所望のワードが最も最近使 用されたワードであるので、該ワードはデータ・メモリ１０７中に書き込捷ねば なら々い。データ・メモリ１０７の最も以前に使用されたワードはデータ・メモ リ１０８中の所望のメモリ・ワードがそれまで使用していたメモリ　ロケーショ ン中に書き込寸れねばならない。

ＬＲＵ回路１０５が第２および３図に示されているカベＬ　ＲＵ回路１０６も同 様な構成を有している。Ｌ　ＲＵ回路１０４は第４図に示されている。第２図Ｇ ′！アドレス・バス１１２を介してプロセッサ１０１により伝送されたアドレス をチェックして所望のワードがキャッシュ・データ・メモリ１０８中に存在する かどうかを判定するのに使用される回路を示しており、第３図はキャッシュ・デ ータ・メモリ１０８中の最も以前に使用されたワードを追尾するのに使用される プライオリティ回路の詳細を示している。プロセッサ１０１が１つのワードを読 み出すとき、プロセッサはまずＣＡ　Ｇ　Ｏ信号およびクロック信号を制御バス １１３を介して制御シーケンサ１０３に伝送し、プロセッサ１０１はアドレス・ バス１１２を介してアドレスを伝送する。制御シーケンサ１０３はこれら信号に 応動してＣ信号およびＳ信号を発生し、該信号は導線１２２および１２３を介し てＬ　Ｒ０回路に伝送される。データ・セレクタ２０２は導線１２２上のＣ信号 に応動してアドレス・バス１１２を介して伝送されたアドレス・ビットを選択し 、これらのアドレス・ビットを導線２１６〜２２３を介してコンテント・アドレ ッサブル・メモリ（ＣＡＭ）２０１のデータ　イン入力に加える。ＣＡＭは各々 ８ビツトより成る４つのワードを含んでいる。ＣＡＭは導線１２３を介して伝送 された入力およびデータ・イン人力で受信されるアドレス・ビットに応動してこ れらアドレス・ビットと内部に記憶すＪ］−だ４つのワードの各々の内容とを比 較する。４つのワードの内の１つがアドレス・ビットと整合すると　％Ｓ　１　 ／／が関連する導線２１２．２１３．２１４または２１５を介して伝送される。

整合しない場合にはゝＸ１″が導線２３６を介して伝送され、Ｔ１時刻において フリップ・フロップ２０６中に記憶される。整合した場合には導線２１２〜２１ ５の状態は導線１２３を介して伝送されるＳ信号の立下りによってラッチ２０４ 中に記憶される。データ・セレクタ２０５はラッチ２０４の内容を選択し、該選 択されたラッチ２０４の内容は導線２２４〜２２７を介して加えられ、次いで導 線２２８〜２３１、ケーブル１３２を介してキャッシュ・データ・メモリ１０８ に伝送される。キャッシュ・データ・メモリ１０８はケーブル１３２を介して伝 送されたアドレスに応動して所望のワードにアクセスし、前述の如くこのワード をデータ・ゲート回路１１０に伝送する。所望のワードがデータ・メモリ１０８ 中に記憶されていたと仮定すると、このときそのワードが最も最近使用されたワ ードとなり、従ってデータ・メモリ１０１に転送されねばならず、データ・メモ リ１０７の最も以前に使用されたワードはデータ・メモリ１０８に転送され、こ のワードのアドレスはＣＡＭ２０１中に書き込まれる。

第４図はアドレス・バス１１２を介してプロセッサ１０１により伝送されたアド レスをチェックして所望のワードがキャッシュ・データ・メモリ１０７中に存在 するか否かを決定するのに使用さり、る回路を示しており、第３図はキャッシュ ・データ・メモリ１０８中の最も以前に使用されたワードを追尾するのに使用さ れるプライオリティ回路の詳細を示している。第４図の回路は第２図のデータ・ セレクタ２０２と類似したデータ・セレクタを含丑す、プライオリティ回路４４ ４を含んでいる点を除いて第２図の回路と動作は同一である。プライオリティ回 路４４４は第３図を参照して述べるプライオリティ回路と同一である。データ・ セレクタが不要な理由は第４図の回路は常にアドレス・バス１１２を介して伝送 されるアドレスを使用するからである。第４図の回路がデータ・セレクタを必要 としないのは、この回路はキャッシュ・メモリ１００中の最も最近使用されたワ ードと関連しており、従って第２図に示す回路のようにアドレス・バス１１２か らのデータを使用するか、または最も高いプライオリティを有するＬＲＵ回路か らのデータを使用するか判定する必要がないためである。この点に関しては以下 に示す例により更に明白となろう。

第２および４図に示す回路の動作を説明するため、先に述べた例３を使用する。

例３は所望のワードがデータ・メモリ１０８中に存在するときに実行すべき動作 を与えたものである。この例に関する更に詳細な説明をここでは丑ずＬＲＵ回路 １０５の観点から述べ、次いでＬＲＵ回路１０４中の相応する動作に関して述べ ることにより行う。データ・メモリ１０８中のワード１およびデータ・メモリ１ ０７中のワード２が最も以前に使用されたワードであるものと仮定する。これら の異なる動作を実行するため、制御シーケンサ１０３は多数のタイミング信号を 発生するが、その中で最も重要なものはＴＯ〜Ｔ４でちる。、ＴＯ期間中、アド レス　ハス１１２上のアドレス・ビットはデータ・セレクタ２０２によって選択 され、ＣＡ　Ｍ　２０１で整合するかどうか探索するのに使用される。これらの アドレス・ピットがＣＡＭ２０１中のワード２の内容と整合するものと仮定する と、９１“が導線２１３上に発生されるが、導線２１２．２１４および２１５は ゝＸＯ″である。この動作は導線１２３を介してＣＡＭ２０１に伝送されたＳ信 号および導線１２２を介してＣＡＭ２０１に伝送されたＣ信号の制御の下で実行 される。導線２１２〜２１５上の情報はＳ信号の終了時点においてラッチ２０４ 中に記憶される。更にＳ信号はまたＣＡＭ２０１の整合出力端子をフリップ・７ ０ツブ２０６中に加えるクロックとして作用する。フリップ・フロップ２０６の 出力のＭ２信号は導線１１５を介して制御シーケンサ、１０３に伝送される。

Ｔ１期間中、データ・セレクタ２０３はＭ２信号に応動してラッチ２０４の出力 をアドレスとして選択し、該アドレスは導線２０８〜２１１を介してＣＡＭ２０ １に伝送され、データ・セレクタ２０５はＭ２信号に応動してラッチ２０４の出 力をアドレスとして選択し、該アドレスはケーブル１３２を介してデータ・メモ リ１０Ｂに伝送さｆする。導線２０８〜２１１上のアドレスに応動して、ＣＡＭ ２０１は第２のワードの内容を読み出し、これらの内容をラッチ２０７に伝送し 、Ｔ１の終了時点においてこれらの内容は該ランチ２０７中に記憶される。

データ・メモリ１０８はケーブル１３２を介して伝送されたアドレスに応動して その第２のワードの内容を読み出す。これらの内容はデータ・メモリ１０Ｂの内 部に記憶され、データ・ゲート回路１１０に伝送される。Ｔ１期間中、ＬＲＵ回 路１０４は最も以前に使用されたワードのアドレスにアクセスし、該アドレスを ケーブル１１７を介してＬＲＵ回路１０５に伝送し、データ・メモリ１０１は最 も以前に使用されたワードにアクセスし、該ワードをケーブル１４０を介してデ ータ・メモリ１０８に伝送するが、これについては以下で述べる。

ＬＲＵ回路１０４からのアドレスはＣＡＭ２０１中に書き込まれ、相応するデー タ・ワードはデータ・メモリ１０８中に書き込まれる。Ｔ２期間中、データ・セ レクタ２０３はＣＡＭ２０１に対するアドレスとして使用されるワード２のアド レスを含むラッチ２０４の出力を再び選択する。ＬＲＵ回路からの最も以前に使 用されたアドレス・ワードはワード２中に記憶される。Ｔ２期間中、制御シーケ ンサ１０３は導線１２４を介してＷ信号を、導線１２０を介してＲＰＬ２信号を 伝送し、それによってＣＡＭ２０１はデータ入力端子」二に存在する情報をワー ド２中に書き込む。それと同時Ｖこ、データ・メモリ１０７の最も以前に使用さ れたワードはデータ・メモリ１０８のワード２中に書き込寸れる。このときアド レスはデータ・セレクタ２０５およびケーブル１３２を介してラッチ２０４の出 力により供給される。以下で述べるように、第；（図１〆ζ示すプライオリティ 回路は、ワード２がＬＲＵ回路１０５中の最も以前に使用されたワードでなく最 も最近使用されたワードであるという事実を反映するようＴ３期間中に更新され る。Ｔ４期間中にフリップ・フロップ２０６はリセットされる。

ここで例３を第４図を参照してＬＲＵ回路１０４に関して記述する。ＴＯ期間中 、ＣＡＭ４０１の探索が行われる。しかし整合しないので整合出力端子は１０″ となり、このゝゝ０“はフリップ・フロップ４０６中に記憶さ力、、Ｍｌ信号は 制御シーケンサ１０３には伝送されない。

Ｔ１期間中、Ｍ１信号は存在しないので、ＣＡＭ４０１はプライオリティ回路４ ４４からのアドレスによりアトＬ／　ス指定さｎる。このアドレスは導ｆｌＪ４ ３２〜４３５、データ・セレクタ４０３および導線４０８〜４１１を介してＣＡ Ｍ４０１のアドレス・イン端子に加えられる。

このアドレス・ビットはＣＡＭ４０１およびデータ・メモリ１０７の最も以前に 使用されたワードのアドレスである。またＴ１期間中、データ・メモリ１０７は データ・セレクタ４０５およびケーブル１３１を介してプライオリティ回路４４ ４の出・力によってアドレス指定される。

Ｔ１の終了時点において、ＣＡＭ４０１の出力データはラッチイ０１中に書き込 まれる。ランチ４０７の内容はケーブル１１１を介してＬＲＵ回路１０５に伝送 される。

Ｔ２期間中制御シーケンサ１０３は導線１１９および１２４を介してＬＲＵ回路 １０４およびデータ・メモリ１０７　＝−ＲＰ　Ｊ−１およびＷ信刊を夫々伝送 する。これら４０１中の導線４３２〜４３５１０ビツトにより決定された最も以 前に使用されたワードのロケーション中に書き込まれる。それと同時に、データ ・バス１１１上に存在するワードはケーブル１３１を介して伝送されたアドレス のデータ・メモリ１０７中に書き込まれる。

Ｔ３期間中にプライオリティ回路４４４は更新される。

ここで述べた例ではＬＲＵ回路１０６捷たはデータ・メモリ１０９と関連する情 報は変更する必要がなかったことに注意されたい。

考察すべき他の例は所望のワードがデータ・メモリ１０７〜１０９中に含まれて おらず、メイン・メモリ１０２から読み出さねばならない例１に相応する場合で ある。この例の場合、ＬＲＵ回路はいずれもＴＯ期間中に整合が成立せず、ＴＯ の終了時点において制御シーケンサ１０３はメイン・メモリ１０２にアクセスし て所望のワードを入手する。制御シーケンサ１０３は導線１２５を介してメイン ・メモリ読み出し信号を伝送することによりメイン・メモリ１０２にアクセスす る。メイン・メモリ１０２が所望のワードにアクセスすると、該メモリは導線１ ２６を介してメ〈ン・メモリ・レディ信号を伝送し、所望のメモリ・ワードをデ ータ・ハス１１１上に加えることにより応動する。制御シーケンサ１０３はメイ ン・メモリ・レディ信号に応動してキャッシュ・データ・レディ信列ヲ介−生（ 、プロセッサ１０１に対しデータかデータ・ハス１１１上に存在し、ＬＲＵ回路 およびデータ・メモリを更新するだめの次のステップを実行すべきことを知らせ る。

メイン・メモリ・レディ信号の受信後、制御シーケンサ１０３はＴ１信号を送信 する。Ｔ１信号が送信されたことにより生じる結果をまず第２図を参照して述べ る。

即ちＭ２信号は導線１１５を介して伝送されず、データ・セレクタ２０３はＣＡ Ｍ２０１を読み出すために導線２３２〜２３５を介して第３図のプライオリティ 回路から伝送された最も以前に使用されたワードのアドレスを選択する。ＣＡＭ ２０１から読み出されたワードはデータ・メモリ１０８中に記憶された最も以前 に使用されたデータ・ワードのアドレスである。それと同時に再び最も以前に使 用されたワードのアドレスであるケーブル１３２を介して伝送されたアドレスに 基づいてデータ・メモリ１０８に対し読み出しが実行される。Ｔ１の終了時点に おいて、最も以前に使用されたワードのアドレスはラッチ２０７中に加えられ、 データ・メモリ１０８からアクセスされているデータは同様にデータ・メモリ１ ０８中の同様なラッチの組の中に加えられる。同じ型の動作がＬＲＵ回路１０４ および１０６およびデータ・メモリ１０７および１０９中で実行される。

Ｔ２期間中、ＬＲＵ回路１０４からケーブル１１１を介して伝送されるアドレス は、第３図のプライオリテ′４回路から導線２３２〜２３５を介して伝送される アドレスによって規定される最も以前に使用されたワードのアドレスに相当する ＣＡＭ２０１のロケーション中に書キ込まれる。同様に、データ・メモリ１０７ からアクセスされていたデータはデータ・メモリ１０８中に書き込まれる。

ＬＲＵ回路１０４に関しては、アドレス・バス１１２上のアドレスは最も以前に 使用されたワードのアドレスを指示するプライオリティ回路４４４から導線４３ ２〜４３５を介して伝送された情報によりアドレス指定されるＣＡＭ４０１のロ ケーション中に書き込まれる。データ・バス１１１上に存在するデータは最も以 前に使用されたワードのアドレスにおいて最も以前に使用されたデータ・メモリ １０７のワード中に書き込まれる。同様の動作がＬＲＵ回路１０６およびデータ ・メモリ１０９においても実行される。Ｔ３期間中、ＬＲＵ回路１０４．１０５ および１０６のプライオリティ回路は先の最も以前に使用されたワードが現在は 最も最近に使用されたワードであるという事実を反映するために更新される。

第３図に示すプライオリティ回路の動作を説明するため、所望のワードがデータ ・メモリ１０８中に含まれている場合の動作を記述する例３を参照する。第３図 のプライオリティ回路の動作は第４図のプライオリティ回路４４４およびＬＲＵ 回路１０６のプライオリティ回路の動作と類似している。以前の例では最も以前 に使用されたワードはデータ・メモリ１０８中のワード１であり、ＬＲＵ回路１ ０５のＣＡＭロケーション１中の相応するアドレスであった。ＴＯ期間中に実行 された整合操作期間内に、ＣＡＭ２０１のワード２が、プロセッサ１０１が読み 出したいアドレスを含んでいることが見出された。

Ｔ３期間中、第５図に示すプライオリティ回路はワード２が現在量も最近使用さ れたワードであるという事実を反映するよう更新されねばならない。しかし、ワ ード１は尚最も以前に使用したワードを一保持している。フリップ・フロップ３ ２２〜３２７はＣＡＭ２０１およびデータ・メモリ１０８中に含まれているワー ドの使用順序に関するプライオリティを保持するのに使用される。ＮＯＲゲート ３２８〜３３１はフリップ・フロップ３２２）３２７中に含まれた情報をデコー ドしてどのワードが最も以前に使用されたワードであるかを指示する。例えば、 ＮＯＲゲート３２８が導線２３２を介して“１″を伝送している場合、これはワ ード０が最も以前に使用されたワードであることを指示している。ＯＲゲート３ ０９〜３１５およびＡＮＤゲート３１６〜３２１はプライオリティ回路の更新期 間中にフリップ・フロップ３２２〜３２７の内どれを変更すべきかを決定するの に使用される。表１はセットされているこれらフリップ・フロップの意味を表わ している。例えばフリップ・フロップ３２２がセットされているとすると、フリ ップ・フロップ３２２はゝゝ１″なるＭＯ倍信号導線３０１を介してＮＯＲケー ト３２８に伝送する。フリップ・フロップ３２２がセットされているということ はワード０がワード１よりもより最近使用されたことを意味する。

ＮＯＲゲート３２８〜３３１により実行される機能は表２に示されている。

ゝゝ１″が導線２３２を介して伝送される場合、ｓｏ倍信号伝送されていると呼 ぶことにする。フリップ・フロップ３２２がセットされていると表２のＭＯＬの 値はゝゝ１“であり、ＭＯ１Ｏ値は０である。フリップ・フロップ３２２がリセ ットされていると、ＭＯｌの値は０であり、１了］の値は１である。例えばフリ ップ・フロップ３２２．３２３および３２４がリセットされていると、ＳＯ倍信 号導線２３２を介して伝送されることになる。

ＯＲゲート３０９〜３１５およびＡＮＤゲート３１６〜３２１０更新時点におけ る動作を表３に示す。

更新はＲＰＬ２信号が導線１２０を介して制御シーケンサ１０３から伝送される 時刻Ｔ３において行なわれる。

Ｔ３およびＲＰＬ２のＡＮＤゲート３０８によってとられ、これによってＯＲゲ ート３０９〜３１５およびＡＮＤゲート３１６〜３２１がエネイブルされる。例 えば更新期間中にゝゝ１″が導線２３１を介して伝送されると、フリップ・フロ ップ３２４．３２６および３２７がリセットされる。導線２３１を介して伝送さ れる１“はワード３が現在量も最近使用されたワードであることを示し、従って 表１によりフリップ・フロップ３２４．３２６および３２７はセット出来ない。

何故ならばこれらフリップ・フロップはワード０１ワード１およびワード２が芙 々ワード３よりもより最近アクセスされたことを指示するからである。

第３図に示す回路の動作を更に明解に説明するため、時刻ＴＯにおける動作期間 中にワード２の整合が行われる以前に示した例を第５図を参照して記述する。行 ５０１はフリップ・フロップ３２２〜３２１の初期状態を示している。ワード２ が所望のワードを含んでいると決定されると、ワード２の内容はＣＡＭ２０１お よびデータ・メモリ１０８の両方においてアクセスされ、伝送されてＬＲＵ回路 １０４およびデータ・メモリ１０７中に記憶される。ＬＲＵ回路１０４およびデ ータ・メモリ１０７からの最も以前に使用されたワードはＬＲＵ回路１０５およ びデータ・メモリ１０８に伝送され、これらメモリの各々のワード２・中に記憶 される。この情報がワード２中に記憶された後、ワード２は最も最近使用された ワードとなり、フリップ・フロップ３２２〜３２７はそれに応じて更新されねば ならない。ワード２が選択されたワードであったので、第２図のデータ・セレク タ２０５は導線２３０を介してＸ１″を伝送する。ＯＲゲート３０９〜３１５お よびＡＮＤゲート３１６〜３２１は導線２３０を介して伝送されたゝゝ１”に応 動してフリップ・フロップ３２７をセットし、フリップ・フロップ３２３および ３２５をリセットする。これが第５図の行５０２に示さり、ている。最も以前に 使用されたワードは同行５０２中のワード１であることに注意されたい。次の探 索操作において所望のワードがワード３である場合、フリップ・フロップ３２２ 〜３２７は行５０３に示す状態を反映するべく７３期間中に更新される。次の探 索操作において、ワード１が所望の情報を含んでいることが見出されると、フリ ップ・フロップ３２２〜３２７が行５０４に示す状態を反映するべく更新される 。ここで最も以前に使用されたワードは３回の探索操作期間中（この期間中にワ ード２．３および１はアクセスされている）にアクセスされなかったワードＯで あることに注意されたい。

前述の実施例は本発明の原理を例示するものであり、本発明の精神および範囲を 逸脱することなく当業者にあっては他の装置を考案し得ることを理解されたい。

ＦＩ６．１ 国゛際調査報告

Claims (1)

1. 【特許請求の範囲】 ｌ　データ処理システムの記憶能力を増強する装置であって、該システムは： メイン・メモリ（１０２）と： キャッシュ・メモリ・システム（１００１と；該キャッシュ・メモリ・システム およびメイン・メモリをアドレス指定する手段（１０１Ｊとを含み：前記キャッ シュ・メモリ・システム（１００）は：各々がメイン・メモリ（１０２）中にも 重複して存在するワード・グループを含む複数個のキャッシュ・メモリ（１０７ −１０９３と： メイン・メモリ中に記憶された第１のワードがキャッシュ・メモリの１つにもま た記憶されているか否かを決定する手段（１０４−１０６３と： 第１のワードがキャッシュ・メモリの１つに記憶されていないという前記決定手 段（１０４−１０６３からの指示に応動して第１のワードの第１のキャッシュ・ メモリへの記憶を行わせる制御回路（１０３）とを含み；該第１のメモリは第１ のワードの受信に応動して最も以前に使用された先に記憶されているワードを第 ２のキャッシュ・メモリに転送することを特徴とするデータ処理システムの記憶 能力を増強する装置。 ２　データ処理システムの記憶能力を増強する方法であって、該システムは。 メイン・メモリ（１０２１と； キャッシュ・メモリ・システム（１００１と；キャッシュ・メモリ・システムお よびメイン・メモリへのアドレス指定を行う手段（１０１）とを含み：読方法は ： キャッシュ・メモリ・システム（１００）中に記憶されたワードを使用された相 対時刻に従って順序づけ、メイン・メモリ中に記憶されたワードがまだキャッシ ュ・メモリ・システム（１００）を形成するキャッシュ・メ該ワードを第１のキ ャッシュ・メモリ中に記憶させ、最も以前に使用された先に記憶されているワー ドの第１のメモリから第２のキャッシュ・メモリへの転送を行わせる階程より成 ることを特徴とするデータ処理システムの記憶能力を増強する方法。 ３　データ処理システムにおいて、該システムは：メイン・メモリ・アドレス信 号を発生するプロセッサ手段と； メイン・メモリ・ワードを記憶する複数個のメモリ・ロケーションを有するメイ ン・メモリと；キャッシュ制御手段と； 各々メイン・メモリ・アドレスおよび相応するキャッシュ・データ・ワードを記 憶する複数個のメモリ・ロケーションを有し、その中に記憶されたすべてのメイ ン・メモリ・アドレスと不整合なメイン・メモリ・アドレス信号に応動してキャ ッシュ制御手段に不整合信号を発生して伝送する第１および第２のキャッシュ・ メモリを含み： キャッシュ制御手段は第１および第２のキャッシュ・メモリにより不整合信号が 同時に発生されることに応動して第１の制御信号をメイン・メモリおよび第１な らびに第２のキャッシュ・メモリに対し発生して伝送し；メイン・メモリは前記 第１の制御信号および不整合であったメイン・メモリ・アドレス信号に応動して メイン・メモリ・ワードを第１のキャッシュ・メモリに伝送し；第１のキャッシ ュ・メモリは第１の制御信号に応動して最も以前に使用されたキャッシュ・デー タ・ワードおよびこれと相応する記憶されたメイン・メモリ・アドレスを第２の キャッシュ・メモリに伝送し、伝送されたメイン・メモリ・ワードおよびメイン ・メモリ・アドレス信号を記憶し； 第２のキャッシュ・メモリは第１の制御信号に応動して伝送されたキャッシュ・ データ・ワードおよびこれと相応するメイン・メモリ・アドレスを記憶すること を特徴とするデータ処理システム。 ４　請求の範囲第３項記載のデータ処理システムにおいて、 第２のキャッシュ・メモリは更にメイン・アドレスを記憶する複数個のメモリ・ ロケーションを有する整合メモリと、キャッシュ・データ・ワードを記憶する複 数個のメモリ・ロケーションを有するデータ・メモリより成り　；　− 前記整合メモリは整合したメイン・メモリ・アドレス信号に応動してその内容が データ・メモリに対する整合したメイン・アドレス信号と整合したメモリ・ロケ ーションのキャッシュ・メモリ・アドレスを発生して伝送し、不整合となったメ イン・メモリ・アドレス信号に応動して不整合信号を発生して伝送し； データ・メモリはキャッシュ・メモリ・アドレスに応動して相応するキャッシュ ・データ・ワードにアクセスして伝送することを特徴とするデータ処理システム 。