JPS624745B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の背景〕 本発明は、データ処理システム、さらに具体的
に言えば、１つ又は複数個のプロセツサが利用し
得る主記憶装置と組合せて高速度緩衝記憶機構即
ちキヤツシユを使用するシステムに関するもので
ある。

データ処理システムは、迅速なアクセスのため
のデータまたは命令を一時的に保持するために高
速度の緩衝記憶機構即ちキヤツシユを使用し、低
速度で動作する主記憶装置即ち補助記憶装置に対
する取り出し要求を回避している。キヤツシユに
質問してその要求されているデータがないことが
わかつた後にそのデータが主記憶装置からキヤツ
シユに転送される。必要なデータは、直後のおよ
び将来の使用のために主記憶装置からキヤツシユ
の割り当てられた部分に取り出される。主記憶装
置は通常キヤツシユよりもずつと大きいので、主
記憶装置からのデータをキヤツシユ中に効果的に
写像するために、かなりの努力が払われてきた。
「IEEEコンピユータ・グループ・ニユーズ」
1969年３月刊、第９〜13頁記載の「Concepts
for Buffer Storage」と題するC.J.コンテイの論
文には、４種の技術が記述されている。

その第１のセクター技術では、主記憶装置から
の多数のブロツクからなるデータ・セクターが一
度に１ブロツクずつキヤツシユのいずれか１つの
セクター中に写像される。キヤツシユは、通常少
数のセクターしか保持できず、各キヤツシユ・セ
クターはいつも主記憶装置の同一セクター内から
のブロツクしか含むことができない。キヤツシユ
内にどのデータがあるかを覚えているために必要
な論理は簡単である。このシステムでは、キヤツ
シユを探索して「ヒツト」（所望のブロツクが存
在する）を決定するのに、１セクター当り１つの
タグ、１ブロツク当り１つの妥当性ビツトしか必
要としない。主記憶装置の任意のセクターをキヤ
ツシユの任意のセクター中に転送できるけれども
各キヤツシユ・セクターは別のセクターで置換さ
れるまでその記憶されたセクターの不在ブロツク
のために開けておかれなければならない。この方
法は、データの転送が幾分厄介になり、いくつか
のセクター中から少数の必要なデータ・ブロツク
を選択するには柔軟さを欠いている。

第２の技術、即ちキヤツシユの直接写像法で
は、要求ごとに１データ・ブロツクしか転送され
ず、それは、キヤツシユ内の１つのタグ・アドレ
スに事前指定されている。キヤツシユ中にＮ個の
ブロツクがある場合、主記憶装置からのＮ番目ご
とのブロツクが同じタグ・アドレスに事前指定さ
れる。ブロツクをセクターにグループ分けする考
えは、最早必要でない。この構成は、ハードウエ
ア上は効率的であるが、柔軟性に欠ける。（下記
の４番目の技術のような）他のキヤツシユ法は、
この方法を拡張して柔軟性を高めたものである。
緩衝記憶機構の第３の技術は、完全に連想的であ
り、この方式では任意データを主記憶装置からキ
ヤツシユ中の任意のデータ・ブロツクに写像する
ことができる。これは競合の難点を回避するけれ
ども、全データ・ブロツクのタグを探索しなけれ
ばならないため、多くのハードウエアまたは多く
の探索時間が必要である。次に第４の方式である
セツト連想方式では、事前指定されたブロツクが
直接写像技術を使つて１セツトのキヤツシユ位置
に写像される。この方式では完全に連想的なキヤ
ツシユが必要とするハードウエアの多く、および
競合の問題が軽減されるが、各記憶ブロツクに対
して１つのタグ・アドレスを必要とするという欠
点がある。

これらの今までのキヤツシユ機構の試みは一般
的に、両極端にまで進んでしまつており、余分の
データを転送するか、またはキヤツシユ中に記憶
されている各データ・ブロツクに対して１つのタ
グを使用して多数のタグをもたらすかであつた。
即ち、これらのキヤツシユが不充分であるか、あ
るいは回路が複雑になり、そのコストが飛躍的に
増大する。別の見方をすれば、セクターの転送は
大きすぎることが多い。セクターよりはずつと小
さいが典型的なブロツクよりは大きく、１つのタ
グ・アドレスと関連させることができる中程度の
量のデータに対する必要性が残つている。

従つて、本発明の主たる目的は、各タグ・アド
レスがデータ・アレイ中の複数のデータ・ブロツ
クへのアクセスがもたらすタグ・アレイとデー
タ・アレイとのセツト連想緩衝記憶機構即ちキヤ
ツシユ・システムを提供することにある。

本発明の第２の重要な目的はタグ・アレイがデ
ータ・アレイに比べて小さく、従つて回路効率の
改良およびコストの低減が可能となるデータ演算
処理システム用のキヤツシユ機構を提供すること
である。

本発明の第３の目的は、単一タグ・アドレスに
対して複数のブロツクの一つにアクセスするため
に、そのタグ・アドレスをデータ・ブロツク識別
ビツトと組み合せるキヤツシユ機構を提供するこ
とである。

本発明の第４の目的は多重プロセツサ・システ
ムに容易に適合できるキヤツシユ機構を提供する
ことである。

〔発明の概略〕

本発明によれば、タグ・アレイ及びデータ・ア
レイを持つた緩衝記憶機構が設けられ、各タグ・
アレイ位置は複数個の連続したデータ・アレイ位
置と関連づけられ、それらデータ・アレイ位置の
各々は主記憶装置の同じセクターからの１ブロツ
クのデータを貯蔵するように構成される。そのデ
ータ・ブロツクのグループは直接にデータ・アレ
イ位置に写像されるが、主記憶装置のセクターは
単に連想的に写像される。データ・ブロツクのグ
ループは直接写像されるので、各ブロツク位置
は、セクターにはかかわりなく、その事前指定さ
れたデータ・アレイ位置にしか記憶されず、従つ
て取り出し中の所望のブロツク・グループが存在
するか否かを決定するためにはそのグループ識別
をもつ１つのタグ・アドレスのみを探索すればよ
い。１つのグループ内での各個々のブロツクの存
在は個々の妥当性ビツトに基づく。そのブロツ
ク・グループがキヤツシユ中に存在し且つ必要と
される特定のブロツクが有効なものである場合、
キヤツシユ内の所望のワードの探索は成功して、
「ヒツト」と呼ばれる。そうでない場合は、「ミ
ス」が検出される。複数のデータ・ブロツクが主
記憶装置から取り出されてキヤツシユに転送され
るとき、それらの妥当性はタグ・ワードと関連し
て記憶される適当な妥当性ビツトによつて表わさ
れる。置換されるべき最も以前に使用されたタ
グ・ワードおよびブロツク・グループを定義する
ために、置換アレイをそのセツト連想セクター・
キヤツシユと共に使用することもできる。

各タグ・ワードは、データ・アレイ中の複数の
位置をアクセスできるので、必要なタグ記憶容量
が少なく、従つて回路が少なくコストが安くなる
という利点がある。セツト連想緩衝記憶機構の場
合と同じく、タグ・アレイならびにデータ・アレ
イの探索は同時に行なわれる。即ち「ヒツト」又
は「ミス」に従つて、その指定されたデータ・ブ
ロツクをデータ・アレイからゲートし、または抑
制することができる。主記憶装置から複数ブロツ
クを一括して取り出すことができるため、かなり
の数のアクセスおよびより大きなキヤツシユ記憶
データの装置に必要なそのための転送時間の多く
が除かれる。もう一つ便利な点は、ブロツク妥当
性ビツトをタグ中のセクター識別（コード）と共
に記憶し、情報の信頼性が早期に決定できること
である。この方式は、さらに必要なレジスタの数
が減少し、回路の単純化が可能となる。

〔良好な実施例の説明〕

第１図を参照すると、緩衝記憶機構を使用した
典型的なデータ演算処理システムが概略的に示し
てある。これは、一般に主記憶装置１２中に命令
およびオペランドが常駐する中央処理装置１１用
の高速度緩衝機構として役立つ本発明のセツト連
想セクター・キヤツシユ１０を含んでいる。探索
すべき命令またはデータの取り出しアドレスが、
母線１３ａによつてメモリ・アドレス・レジスタ
１５に送られる。メモリから読み取られまたはそ
れに書き込まれたデータは、母線１４によつてメ
モリ・データ・レジスタ１６に送られる。キヤツ
シユ１０はまた中央処理装置１１または主記憶装
置１２からアドレスまたはデータを受け取るため
に、母線１３ａおよび１４ａを介してこれらの母
線の各々１３および１４に接続されている。キヤ
ツシユ１０は、要求されたデータがその中に存在
するときにそのデータをプロセツサに送る。全体
的に１７として示した制御回路が、中央処理装置
１１から取り出し要求を受け取つてその要求をキ
ヤツシユにまたはアドレス・レジスタおよびデー
タ・レジスタにゲートする。

処理装置１１がメモリ・アクセスを必要とする
場合、それはその命令またはデータのアドレスを
アドレス母線１３ａに載せ、同時にメモリ要求を
制御論理装置１７に出す。アドレスがキヤツシユ
１０に送られ、メモリ・アドレス・レジスタ１５
中に記憶される。キヤツシユはランダム・アクセ
ス・メモリであり、以前に主記憶装置から得たデ
ータ用の高速度レポジトリーとして働く。アドレ
スを受け取ると、キヤツシユがその要求されたデ
ータを含んでいるかどうかについての決定が行わ
れる。要求データがキヤツシユから入手可能な場
合、「ヒツト」が信号化され、論理装置１７が要
求データをキヤツシユ１０からデータ母線１４ａ
を介して処理装置１１にゲートする。これは主記
憶装置１２をアクセスすることなしに、メモリ・
データ転送を完了させる。キヤツシユ１０が要求
データを含まない場合、「ミス」が信号化され、
制御論理装置１７がメモリ・アドレス・レジスタ
１５をゲートして、主記憶装置からのメモリ取出
しサイクルを開始する。主記憶装置から得られた
データが次にメモリ・データ・レジスタ１６に運
ばれ、データ母線１４ａを介して処理装置１１お
よびキヤツシユ１０に置かれ、将来の要求に備え
てそのキヤツシユに記憶される。

以下の説明では、主記憶装置のセグメントを記
述するため、次の語を使用する。例えば、「セク
ター」は主記憶装置の最大の区分で大きなメモリ
位置グループである。「データ・ブロツク」また
は「ブロツク」は、セクターの小部分であるが、
１回のメモリ取出しでアクセスされるデータ量な
ど、主記憶装置中の基本単位を意味するものとす
る。「ワード」は、データ・ブロツクの下位区分
であり、「バイト」はデータ・ワードのさらに下
位区分である。一例として主記憶装置は、16384
セクターを含み、各セクターは4096ブロツクを含
み、各ブロツクは８ワード、各ワードは８バイト
を含む。「ブロツク・グループ」の語は、主記憶
装置および本発明のセツト連想セクター・キヤツ
シユの記憶の単位を定義する。各ブロツク・グル
ープは、キヤツシユ・メモリの基本単位であり、
妥当性ビツトやパリテイ・ビツトなどの補助的２
進ビツトを含む１個のタグ・ワードによつてアク
セスできる複数のデータ・ブロツクの全てを含
む。パリテイ・ビツトの使用はよく知られている
ので、この考察ではこれ以上触れないことにす
る。

第２図は、セツト連想セクター・キヤツシユと
今述べたいくつかのデータ単位の関係を図示した
ものである。一例として、有効アドレス１８は、
左から右に大きさの順に示した32個の２進ビツト
Ａ０〜Ａ３１からなるものと仮定する。主記憶装
置中の記憶セクターは、大きい方から順に14個の
ビツトＡ１８〜Ａ３１によつて識別され、この14
個のビツトはキヤツシユのタグ・アレイ中の１つ
の記憶位置のタグ・アドレスとして使用する。第
２の10個のビツトのグループＡ８〜Ａ１７は、セ
クター内のセツト即ちブロツク・グループを識別
する。この例では、タグ・アレイは、各タグ・ア
ドレスのための1024の記憶位置をもつものと仮定
する。もう２個のビツトＡ６〜Ａ７は、各タグ・
アドレスに対応するデータ・アレイ中に記憶され
ているブロツク用のデータ・ブロツク識別（コー
ド）を形成する。かかる各アドレスについて、４
個のデータ・ブロツクが記憶され、従つて２個の
２進ビツトでその特定タグ・アドレスに対する４
個の各々の識別することができる。ワードおよび
バイト識別（コード）はそれぞれ３個のビツトＡ
３〜Ａ５およびＡ０〜Ａ２を必要とし、ブロツク
内にそれぞれ８バイトを含む８個のワードが存在
することを示す。

主記憶装置のあるセクター内のブロツクとキヤ
ツシユ中のデータ・アレイの間の対応関係を第２
図に示す。ブロツク・グループ０を形成するブロ
ツクＢ０〜Ｂ３や、ブロツク・グループ１を形成
するＢ４〜Ｂ７などのように４つのブロツクより
成るブロツク・グループを主記憶装置内に構成し
ていることがわかる。主記憶装置からのデータ・
ブロツク・グループは、キヤツシユ中のどこにそ
れが常駐できるかに関して事前指定された位置を
持つている。ブロツク・グループ０は、セツト０
のために留保されている位置にしか常駐できず、
ブロツク・グループ１はセツト１のために留保さ
れた位置にしか常駐できず、ブロツク・グループ
１はセツト１のために留保された位置にしか常駐
できず、以下同様である。「キヤツシユ」中のセ
ツトは、全て同じグループおよび同じセクターか
らの連続するデータ・ブロツクから構成されてい
る。各セクターには０と識別される多数のブロツ
ク・グループがあり、全てがキヤツシユのセツト
０に常駐しようと競合する。キヤツシユ・デー
タ・アレイは１つのセクターからの全てのブロツ
クを記憶するのに充分な容量をもつており、また
必要ならば、各ブロツク・セツトが異なるセクタ
ーを表わすようにすることもできる。タグ・アド
レスがセクターを定義するが、後者はそれぞれ特
定の瞬間に異なることができる。各タグ・アドレ
スは、指定されたブロツクとのみ関連しているた
め、タグは当該ブロツク・グループを含むキヤツ
シユ中に常駐するセクターを定義するようセクタ
ー番号だけを含めばよい。この仮定の例では、
1024個のタグ・アドレスがあり、各タグ・アドレ
スは４個のブロツクを識別し得る２個のブロツ
ク・ビツトをも含んでいるので、データ・アレイ
は、4096個のアドレス可能なブロツク記憶装置を
含むことができる。

第２図からわかるように、キヤツシユの各基本
区分は、１個のタグ・アドレス４個の妥当性ビツ
トおよび４個のデータ・ブロツクからなつてい
る。各妥当性ビツト位置が、データ・アレイ中の
ブロツク・グループ中の当該ブロツクの妥当性を
指定する。データ・ブロツクが主記憶装置から取
り出され、キヤツシユ・データ・アレイ中に置か
れる場合、その妥当性ビツトは、有効状態即ち論
理１にセツトされる。そのブロツク・グループ内
の他のブロツクは、要求されない限り取り出さな
くてよい。従来の装置では妥当性ビツトは典型的
な場合データ・アレイ中にデータ・ブロツクと共
に記憶されていたが、タグ・アレイ中にそれらを
記憶するのはより迅速でより大きな柔軟性をもた
らす。例えば初期設定または他のセクターによる
使用のためにキヤツシユ中の１グループを消去す
るには、４個の妥当性ビツトがタグと関連してい
る場合、１動作サイクルだけしか必要ない。それ
らが、データ・ワードと関連している場合には、
消去にｎ回の操作サイクルが必要となるはずであ
る。ただし、ｎ＝１セツト当りのデータ・ブロツ
クの数。その上妥当性（ビツト）がデータ・ワー
ドと関連していない場合、設計者は低速でより安
くより高密度のデータ・アレイを使用する柔軟性
をもつ。妥当性ビツトは、機能的にはタグ・アド
レス・ビツトに関係し、ヒツトまたはミス条件を
決定するため高速度ビツトでなければならない キヤツシユおよび読み書き動作を実施するため
のその制御回路は第３図に示される。動作を開始
する前に、全ての妥当性ビツトがセツトされて、
その当該データ・ブロツクが無効であることを示
すように、キヤツシユが初期設定される。全ての
キヤツシユ・データ・ブロツクの無効化は、「パ
ワーオン」信号または「キヤツシユ・リセツト」
指令が初期設定制御回路１９に送られると起こ
る。回路１９は、初期設定カウンター２０を０に
セツトさせる。カウンター出力がアドレス選択回
路２１によつて選択されタグ・アレイ即ちインデ
ツクス・アレイ２２に対する一時アドレスとして
働く。初期設定回路１９は、さらにゲート３８お
よびインバータ３８ａで書込み使用可能信号を発
生し、第４図に示す妥当性ビツト改訂回路２３か
ら来る４個の妥当性ビツト制御（ビツト）の全て
に０値を設定する。後の図からわかるように、２
−４解続器２４は、第３図のタグ・アレイ２２中
の妥当性ビツト中に書き込むべき当該データであ
る０出力をゲート２５ａ〜２５ｄに送るよう強制
される。同時に、ゲート３６ａ〜３６ｄもゲート
３７およびインバータ３７ａによつてゼロにされ
る。再び第３図を参照すると、刻時ステツプ信号
がカウンター２０に印加され、そこでタグ・アレ
イ中のアドレス順序によつてステツプされ、強制
２進ゼロが全体アレイ中に記憶されてキヤツシユ
中の無効データを示す。初期設定カウンター２０
が回路２１によつてタグ・アレイ・アドレス順序
を完了すると、主記憶装置およびキヤツシユ制御
論理１７（第１図）で使用するために「キヤツシ
ユ作動可能」信号を出す。

キヤツシユはタグ・アレイ２２およびデータ・
アレイを含めて、第３図のアドレス母線１３ａ上
に置かれた各アドレスによつてアクセスされる。
有効アドレスは、例えば32ビツトを含み、そのう
ち上位14ビツトは、セクター・アドレス識別（コ
ード）、10ビツトは、セツトないしブロツク・グ
ループ識別（コード）、２ビツトは、データ・ブ
ロツク識別（コード）、３ビツトはブロツク内の
ワード識別（コード）であり、３ビツトはワード
内のバイト識別（コード）を形成する。アドレス
が現われたとき、10ビツトのセツトないしブロツ
ク・グループ・アドレスが、母線２７上でタグ・
アレイ２２およびデータ・アレイ２６に送られ
る。これらのビツトは、14ビツトの対応するタ
グ・ワードをアドレスして、それをセクター比較
回路２８へ読み出させる。また、母線２８ａを介
して回路２８には、有効アドレスからの14セクタ
ー識別ビツトが現われる。２つの14ビツト・ワー
ドが等しいと、常駐するブロツク・グループが有
効アドレスによつてアドレス中のセクターからの
ものであることを示す、セクター・ヒツト・ラツ
チ２９が使用可能となる。等しくないと、セクタ
ー・ミスが定義される。この比較出力は、ヒツト
またはミスを検出するためのゲート３０の１入力
としても働く。

タグ・アレイ２２からのセクターまたはタグ・
ワードの取り出しと同時に、タグ・ワードの１部
である４個の妥当性ビツトＶ１〜Ｖ４も、妥当性
選択回路３１および妥当性レジスター３２に取り
出される。妥当性選択回路３１への第２の入力
は、アドレスからのブロツク識別ビツトである。
この２ビツトは、４つのデータ・ブロツクのうち
１つを定義するので、所期のデータ・ブロツクに
対応する妥当性ビツトＶ１〜Ｖ４のうちの１つを
選択する。この例では、タグ・アレイ中の妥当性
ビツトは、全てのブロツク・グループに関して無
効化されており、２進０がゲート３０の第２入力
に送られる。ゲート３０の出力は低レベルのまま
で、インバータ３０ａを通じてミスを示す。即
ち、データ２６中に存在するデータ・ブロツクは
無効である。ゲート３０からの低出力が、そうで
ない場合は要求されたブロツク情報をデータ母線
１４ａに置く、ゲート３４を抑制する。

有効アドレスを受け取つたとき、10ビツトのセ
ツトないしブロツク・グループＡ８〜Ａ１７もデ
ータ・アレイ２６に送られたことを思い出して戴
きたい。この情報は、データ・アレイ中の特定ブ
ロツク・グループに対するアドレスとして働き、
２ビツトのブロツク情報Ａ６〜Ａ７がそれと一緒
になつて、グループ内の特定データ・ブロツクの
識別（コード）として働く。その結果、特定のデ
ータ・ブロツクが、ワード選択マルチプレクサ３
５へ送られる。そこで３つのワード・ビツトＡ３
〜Ａ５に応じて、１つのワードが選択されて、３
ビツトのバイト識別（コード）Ａ０〜Ａ２による
将来の解読のために、バイト選択マルチプレクサ
３５ａに送られる。即ちあるデータ・ブロツクか
らの特定バイトがゲート３４に存在するが、ゲー
ト３０からのミス信号によつてさらに伝送される
ことを阻止されている。

ミスが起こると、新しいデータ・ブロツク・キ
ヤツシユにロードされる。この例では所期のデー
タ・ブロツクは、無効であるかまたはキヤツシユ
に不在である。セクター比較回路２８から等化信
号が生じるが、第３図の妥当性選択回路３１から
は出力がない場合、そのブロツクは無効である。
これは、セクター・ヒツトを示し、またキヤツシ
ユ中に既に新しいデータ・ブロツクを受け取るた
め待機しているスロツトがあることを示す。新し
いブロツクは、予約されたスロツト中にロードし
なければならず、その妥当性ビツトは、１にセツ
トしなければならない。タグ・ワード中の他の３
つの妥当性ビツトは、変化しないままでなければ
ならず、それは第４図に示す妥当性ビツト改訂回
路によつて実施される。

第４図において、そのブロツクを識別する有効
アドレスの２ビツトが現在ロード中の特定デー
タ・ブロツクを定義するため、回路２４で解読さ
れる。１に等しい出力が、解読器２４からの回線
１本だけに現われ、ゲート２５ａ−２５ｄのうち
当該のものに印加される。このゲートは、論理１
を生成し、従つて今や新データ・ブロツクに対す
る妥当性ビツトは、タグ・アレイ中で１に変わる
ことができる。残りの３つの妥当性ビツトは、第
３図の妥当性レジスタ３２から第４図の一致ゲー
ト３６ａ〜３６ｄに信号が印加されても変化しな
いままであつた。これらのゲートは、セクター・
ミスまたはORゲート３７およびインバータ３７
ａによつて決定される初期設定妥当性条件がある
場合以外は、いつも妥当性レジスタの状態をゲー
ト２５ａ−２５ｄにパスする。従つて、これらの
条件のどちらも存在しないときゲート３６ａ〜３
６ｄは、この例では、解読器２４からの選択ブロ
ツクのために１レベルをもたらす１つのゲート以
外はゼロ・レベルの当該OR回路２５ａ−２５ｄ
に送信する。再び第３図を参照すると、新デー
タ・ブロツクがデータ母線１４ａからデータ・ア
レイ２６中にロードされ、新しい妥当性ビツト改
訂回路からタグ・アレイ２２中にロードされる。
タイミングは、第１図の主記憶装置およびキヤツ
シユ制御論理１７によつて、当該時間に書込みパ
ルスを用いて制御される。書込みパルスは、第３
図のORゲート３８がゲート３３から受け取り、
３８ａで変換されて、タグ・アレイおよびデー
タ・アレイで書込み可能にする。

キヤツシユのアクセス中にラツチ２９がセクタ
ー・ミスを記録する場合には、別の形式のロード
操作が起こる。この瞬間、置換操作が要求され
る。即ち新セクターからのブロツク・グループが
キヤツシユに指定されて、そこに常駐していた他
のブロツク・グループを置換することになる。新
しいブロツク・グループから１つのブロツクだけ
が、このときロードされることを指摘しておく。
これは、妥当性ビツトが論理１にならなければな
らない、ロードされる１つのデータ・ブロツク以
外の全ての妥当性ビツトが０にならなければなら
ないことを要求する。これもまた第４図の妥当性
ビツト改訂回路によつて実施される。同期のブロ
ツクを論理１にセツトするための論理径路は上記
の場合と同じで、解読器回路２４が当該線を活動
化する。しかし、残りの妥当性ビツトは、ORゲ
ート３７およびインバータ３７ａにセクター・ミ
ス信号が存在することによつて０にセツトされ、
従つてゲート３６ａ〜３６ｄは条件付けられな
い。即ち、ゲート２５ａ−２５ｄからの改訂ビツ
ト線の１つは、論理１を出力とし、残りの線は、
論理０である。有効アドレスからの新しいセクタ
ー・ビツトは、同時に新しい妥当性構成をもつタ
グ・アレイ２２中にロードされ、一方主記憶装置
から取り出されたデータ・ブロツクは、やはりゲ
ート３３からゲート３８への書込みパルスの制御
下で、データ・アレイ２６中にロードされる。

以上のキヤツシユをロードするための操作の説
明から、所期のセクターがタグ・アレイ中にあ
り、所期のデータ・ブロツクに対する妥当性ビツ
ト中に論理１がある場合、回路２８でセクターが
比較され、回路３１で妥当性がチエツクされる
と、ゲート３０に等化出力が生じ、ヒツト信号を
生成することがわかる。10ビツトのセツトないし
ブロツク・グループおよびブロツク識別ビツト対
は、現在データ・アレイをアドレス中なので、あ
るデータ・ブロツクがワード選択マルチプレクサ
３５およびバイト選択マルチプレクサに送られて
いる。即ち、一致ゲート３０からの信号がゲート
３４を活動化させ、選択されたバイトをデータ母
線１４ａおよび処理装置に送ることが可能にな
る。

第１図の中央処理装置１１がデータを記憶する
たためメモリー・システムに送るとき、データお
よびそのアドレスが同時に主記憶装置およびキヤ
ツシユに送られて、両方の場所に記憶される。主
記憶装置は、全てのデータを記憶する。しかし、
セツト連想セクター・キヤツシユは、セクター・
ヒツトが検出されるデータのみを記憶する。操作
は、上記でセクター・ヒツトが起こる場合につい
て説明したように、新データ・ブロツクをキヤツ
シユに加えることと同じである。

本発明のセツト連想セクター・キヤツシユは、
一定のデータ容量をもつものとして説明してきた
が、必要に応じて変えることができる。その中に
は、タグ数を変更すること、各タグと関連するデ
ータ・ブロツクの数を変更すること、あるいは全
キヤツシユを複製して多方向キヤツシユを作るこ
とといつた別法がある。上記の説明では、本例の
タグ・アレイは1024ワードであつた。１タグ・ワ
ード当りのデータ・ブロツク数は同じままでタグ
数を倍にすると、データ・アレイも倍になるはず
である。もう一つの別法として、１タグ・ワード
当りのデータ・ブロツク数を増減することができ
る。１タグ・ワード当りのデータ・ブロツク数を
８に変えると、データ・アレイのサイズが倍にな
る。もちろん、タグ・ワード中のビツト数も、１
タグ・ワード当り４だけ増えることになる。この
１タグ当りのデータ・ブロツク数を増加するの
は、タグ・ワード数を増加するよりも、少しのハ
ードウエアでよい。

コンテイーによつて体系４として提示された、
キヤツシユのサイズを増加するための一般的技術
は、全キヤツシユをセツト連想的やり方で倍化す
ることである。その結果得られるキヤツシユは２
方向セツト連想キヤツシユと呼ばれる。もちろ
ん、拡張を続けて、４方向および８方向キヤツシ
ユにすることができる。本発明のセツト連想セク
ター・キヤツシユはかかる拡張に容易に適合でき
るもので、２方向キヤツシユの例を第５図に示
す。この方法では、新しい技術に出会う、「ヒツ
ト」技術である。セツトは、異なるキヤツシユ中
に常駐する、対応するキヤツシユの基本単位（タ
グ・ワードおよびそのブロツク・グループ）であ
る。例えばセクター０からブロツク・グループ０
を、今やキヤツシユ中の１セツトの位置の何れか
に、１つをキヤツシユ１に、１つをキヤツシユ２
に記憶することができる。ブロツク・グループ０
を受け取ることのできる多重位置はセツト０と呼
ばれる。

第５図を参照すると、第１のキヤツシユは、タ
グ・アレイ５０およびそのデータ・アレイ５１で
表わされ、第２のキヤツシユは、タグ・アレイ６
０およびその対応するデータ・アレイ６１で表わ
される。各キヤツシユのタグおよびデータ・アレ
イは、処理装置によつて出されるアドレスを同時
に受け取るように、適当にアドレス母線１３ａに
接続される。各タグ・アレイは、上記で第３図に
関して説明したように、それぞれヒツト／ミス論
理回路５２，６２および妥当性制御論理回路５
３，６３をもつている。各回路５２または６２
は、第３図の妥当性選択回路３１、妥当性レジス
タ３２、および第４図の妥当性改訂回路の１ブロ
ツク表現である。各回路５２または６２は、セク
ター識別（コード）が同等性に関して比較し、出
力＋キヤツシユ１セクターまたは＋キヤツシユ２
セクター・ヒツト（信号）を出すとき、タグ・ア
レイ中のラツチ２９でセクター・ヒツトの表示を
もたらす。検索されたデータ・ブロツクが回路５
３または６３によつて有効と決定され、第５図の
各キヤツシユに対してセクター・ヒツトがある場
合、ゲート３０の出力信号＋キヤツシユ１ヒツト
または＋キヤツシユ２ヒツトがゲート信号として
働き、各データ・アレイに対するゲート５４また
は６４が生成される。

処理装置が読み取り操作を実施するとき、両方
のキヤツシユは同じ有効アドレスを受け取り、ヒ
ツト／ミス検査を実施する。例えば処理装置がセ
ツト０をアドレス中の場合、所期のセクターおよ
びブロツク・グループは、どちらかのキヤツシユ
に含まれていることも、どちらにも含まれていな
いこともあり得るが、両方に含まれることはな
い。個別ヒツト／ミス検査の結果が、ORゲート
７０およびインバータ７０ａで分析され、合成ヒ
ツト／ミス信号をもたらす。処理装置に戻る伝送
用に有効なデータ・ブロツクがみつかつた場合に
は、ヒツト（信号）をもつキヤツシユだけが、そ
の当該ゲート回路５４または６４を介して、デー
タ母線１４ａ上にデータをゲートする。どちらの
キヤツシユも、その当該回路５２または６２から
ORゲート７０に論理１出力を送らない場合は、
ミス信号が出され、データを主記憶装置から運ば
ねばならない。

ミス信号が出るとはいえ、一方のキヤツシユが
セクター・ヒツト（信号）をもち、両方がセクタ
ー・ミスを経験したことはあり得る。１つのキヤ
ツシユがセクター・ヒツトを示す場合、そのキヤ
ツシユは、新しいデータ・ブロツクのために予約
されたスロツトをもつており、そのデータ・ブロ
ツクのロードを受諾する。この条件が表示され、
もう一方のキヤツシユにロードするのを阻止する
ための禁止信号が生成される。例えばキヤツシユ
１の回路５２からの＋キヤツシユ１セクター・ヒ
ツト信号は、キヤツシユ２をロードすることに対
する禁止信号である出力を、OR７２で生成す
る。同様に、回路６２からのキヤツシユ２セクタ
ー・ヒツト信号は、ORゲート７６に入力を与
え、後者がキヤツシユ１に対する禁止信号を出力
として生成する。キヤツシユをロードすることを
禁止する信号は、第３図のインバータ３３ａおよ
びANDゲート３３に送られ、書込みパルスが禁
止されたキヤツシユに書込み可能信号を発生させ
るのを使用禁止する。

キヤツシユ１とキヤツシユ２のどちらもセクタ
ー・ヒツトを経験しない場合、２つの可能なブロ
ツク・グループ（各キヤツシユ中に１個）の一方
を置換して、新しいデータ・ブロツクのための余
地をあけなくてはならない。この決定は、交換ア
レイ７７と名付けたランダム・アクセス・メモリ
から行われる。交換アレイは、２方向キヤツシユ
内の各セツトに対して１個の２進ビツト位置を含
み、同じビツトがキヤツシユ１とキヤツシユ２の
両方に適用される。そのビツトは各セツトについ
て、最も最近にそのセツトから読み取られたデー
タ・ブロツクを含んでいたキヤツシユを示す。一
方のキヤツシユに対するビツト・レベルを任意に
指定することができる。例えば論理０はキヤツシ
ユ１が最も最近に使用されたことを示し、論理１
はキヤツシユ２について同じことを表すことがで
きる。

交換アレイ７７は、どちらかのタグ・アレイと
同様に、母線１３ａ上の有効アドレスから、10個
のセツトないしブロツク・グループ・ビツトＡ８
〜Ａ１７によつて同時にアドレスされる。次に交
換アレイをアドレスすると、選択されたビツト・
レベルが読み出され、ラツチ７８中にその状況を
示す。ラツチ出力は、それぞれ一致ゲート７９お
よび８０に印加される。ラツチがオンであり両方
のタグ・アレイがセクター・ミスを示す場合に
は、一致ゲート７９が出力として交換ゲート信号
を出し、ラツチ７８がオフのままであり、両方の
タグ・アレイがセクター・ミスを示す場合には、
ゲート８０が出力ゲート信号を出す。

例えば、交換アレイからアドレスされたセツト
内で、キヤツシユ２が最も最近に使用されたこと
を示す論理１が出た場合、ラツチ７８がセツトさ
れて、ゲート７９がキヤツシユ１中のブロツク・
グループの交換を示すその出力信号を出す。交換
アルゴリズムは、最も最近に使用されたデータが
最も再使用されやすいという原理を使つている。
従つて、最も以前に使用されたデータが交換され
る。ゲート７９または８０のどちらかからの交換
信号が入力として当該のORゲート７２および７
６に送られ、各キヤツシユにロードすることを禁
止する信号を生成する。

アドレスされているセツトと関連された交換ア
レイ７７の内容が、各読み取り操作の後にロード
され、従つて常に最も最近に読み取られたデータ
を反映するようになつている各読み取り操作の終
りに、主記憶装置およびキヤツシユ制御論理１７
（第１図）から、ロード交換アレイ・パルスが出
され、OR８１をゲート通過してゲート７９ａで
逆転され、最も最近のデータを交換アレイ中に書
き込ませる。交換アレイへの適当な入力選択は、
マルチプレクサ７３による。このマルチプレクサ
は、交換アレイ中にロードされるべき４つの値Ｉ
０〜Ｉ３のうち何れがを選択することができる。
その選択は、ORゲート７１および７５からくる
制御入力ＡおよびＢにもとづく。初期設定の間、
ゲート７１および７５は、強制的に論理１にな
り、論理０を含む入力Ｉ３を選択させる。即ち、
キヤツシユの初期設定中単に人工的出発的をもた
らすために、論理０が各交換アレイ位置にロード
される。

正常なキヤツシユ操作中に、キヤツシユ１が読
み取り操作中のセクター・ヒツトを経験した場
合、ゲート７は論理１にセツトされ、ゲート７５
は論理０にセツトされて、論理０である入力Ｉ１
を交換アレイにロードさせる。キヤツシユ１中の
セクター・ヒツトが、交換アレイ中にキヤツシユ
が最近に使用されたことを示す、論理０をロード
させることを指摘しておく。同様にキヤツシユ２
がセクター・ヒツトを経験した場合は、入力Ｉ２
が選択され、論理が交換アレイ中にロードされ
る。

どちらのキヤツシユもセクター・ヒツトを経験
しない場合は、現在交換アレイ中に記憶されてい
るビツトの逆転が、入力Ｉ０を介して選択され
る。

例えば、どちらのキヤツシユもセクター・ヒツ
トを経験せず、交換アレイからラツチ７８中に１
が読み取られると仮定する。これにより、ゲート
７９が活動状態になり、キヤツシユ１中のブロツ
ク・グループを交換し、こうしてキヤツシユ１を
最近使用されたものにする。従つてラツチ７８の
逆転論理０が交換アレイ中にロードされ、キヤツ
シユ１を最近に使用されたものとして定義する。

以上の説明から、より効率的なキヤツシユ記憶
装置が開示されたことがわかる。１タグ当りのデ
ータ・ブロツク数が増加すると、検索時間の損失
なしにキヤツシユ・メモリの１ブロツク当りの回
路コストを減らすことが可能になる。本発明は、
複雑な制御回路を加えることなく、容易にキヤツ
シユ設計に適合させ、サイズを変えることができ
る。

【図面の簡単な説明】

第１図は、キヤツシユ・メモリを含む通常のデ
ータ処理システムの、単純化したブロツク・ダイ
ヤグラム、第２図は、本発明に基づいて構成し
た、主記憶装置およびキヤツシユ・メモリのデー
タ・ブロツク間の写像関係を示す図、第３図は、
本発明のキヤツシユ・メモリならびにキヤツシユ
から読み取りまたはキヤツシユに主メモリ母線か
ら書き込むための回路の概略図、第４図は、第３
図に示した妥当性ビツト改訂回路の詳細図、第５
図は、本発明のキヤツシユを使用した多重キヤツ
シユ配置の概略図である。 １０……セツト連想セクター・キヤツシユ、１
１……中央処理装置、１２……主記憶装置、１５
……メモリ・アドレス・レジスタ、１６……メモ
リ・データ・レジスタ、１７……主記憶装置及び
キヤツシユ制御論理装置。

Claims (1)

1. 【特許請求の範囲】 １ 複数のセクターより成る主記憶装置であつて
   該セクターの各々は複数のブロツク・グループよ
   り成り且つ該ブロツク・グループの各々は複数の
   ブロツクより成る主記憶装置と、前記主記憶装置
   をアクセスするためにセクター・アドレス、ブロ
   ツク・グループ・アドレス及びブロツク・アドレ
   スを含む主記憶装置アドレスを発生し得るプロセ
   ツとを有するデータ処理システムにおいて、 各々が１ブロツクのデータを記憶し得る複数の
   記憶位置を有し、該記憶位置の各々が前記ブロツ
   ク・グループ・アドレス及びブロツク・アドレス
   によりアクセスされるデータ・アレーと、 複数の記憶位置を有し、該記憶位置の各々が前
   記ブロツク・グループ・アドレスによりアクセス
   可能であり、前記データ・アレーにデータが記憶
   されたブロツクを含むセクターを表わすセクタ
   ー・アドレスと該セクターにおける１つのブロツ
   ク・グループ内の各ブロツクが前記データ・アレ
   ーに存在するか否かを表わす妥当性ビツトとを記
   憶するためのタグ・アレーと、 前記プロセツサにより発生された主記憶装置ア
   ドレスにおけるセクター・アドレスと前記タグ・
   アレーをアクセスすることにより得られたセクタ
   ー・アドレスとの一致を表わす信号及び前記タ
   グ・アレーをアクセスすることにより得られた妥
   当性ビツトに従つて、前記データ・アレーをアク
   セスすることにより得られた１ブロツクのデータ
   を前記プロセツサへゲートするための手段と、 より成る緩衝記憶装置。