JPS58205975A - 緩衝記憶機構 - Google Patents

Abstract

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

Description

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

データ処理システムは、迅速なアクセスのためのデーダ
または命令を一時的に保持するために高速度の緩衝記憶
機構即ちキャッシュを使用し、低速度で動作する主記憶
装置即ち補助記憶装置に対する取り出し要求を回避して
いる。キャッシュに質問してその要求されているデータ
がないことがわかった後にそのデータが主記憶装置から
キャッシュに転送される。必要なデータは、直後のおよ
び将来の使用のために主記憶装置がちキャッシュの割り
当てられに部分に取り出されろ。主記憶°装置は通常キ
ャッシュよりもずっと大きいので、主記憶装置からのデ
ータをキャッシュ中に効果的に写像するために、かなり
の努力が払われてきた。

［ＩＥＥＥコンピュータ・グループ・ニュース−１１９
６９年３月刊、第９〜１３頁記載の［Ｃｏｎｃｅｐｔｓ
　　ｆｏｒ　　ｌ１ｕｆｆｅｒ　　Ｓｔｏｒａｇｅ　Ｊ
ど題するＣ、　Ｊ、コンティの論文には、４種の技術が
記述されている。

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

第２の技術、即ちキャッシュの直接零像法では、要求ご
とに１データ・ブロックしか転送されず、それは、キャ
ッシュ内の１つのタグ・アドレスに事前指定されている
。キャッシュ中にＮ個のブロックかめる場合、主記憶装
置からのＮ番目ごとのブロックが同じタグ・アドレスに
事前指定さオしる。

ブロックをセクターにグループ分けする瑚えは、最イ必
要でない。この構成は、ハードウェア土は効率的である
が、柔軟性匹欠ける。（下記の４番目の技術のような）
他のキャッシュ法は、この方法を拡張して柔軟性を高め
たものでめ１゜緩衝記憶機構の第３の技術は、完全に連
想的でめり、この方式では任意データを主記憶装置から
キャッシュ中め任意のデータ・ブロックに写像すること
ができる。これは競合の難点を回避するけれども、全デ
ータ・ブロックのタグを探索しなけれはならない゛ため
、多くのハードウェア捷りは多くの探索時間が必要でめ
る。次に第４の方式でろるセット連想方式では、事前指
定されたブロックが直接写像技術を使って１セツトのキ
ャッシュ位置に写像されろ。この方式でに完全に連想的
なキャッシュが必要とする・・−ドウエアの多く、およ
び競合の問題が軽減されるが、各記憶ブロックに対して
１つのタグ・アドレスを必要とするという欠点かめる。

゛　これらの今までのキャッシュ機構の試みは一般的に
、両極端にまで進んでしまっており、余分のデータを転
送するか、またにキャッシュ中に記憶されている各デー
タ・ブロックに対して１つのタグを使用して多数のタグ
をもたらすかでめった。

即ち、これらのキャッシュが不充分であるか、あるいは
回路が複雑になり、そのコストが飛躍的に増大する。別
の見方をすれば、セクターの転送は太きすぎることが多
い。セクターよりはずっと小さいが典型的なブロックＩ
りは犬きく１．１つのタグ・アドレスと関、連させるこ
とができろ中程度の量のデータに対する必要性が残って
いる。

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

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

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

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

〔発明の概略〕

不発明によれは、タグ・アレイ及びデータ・アレイを持
った緩衝記憶機構が設けられ、各タグ・アレイ位ｔ！／
は複数個の連続したデータ・プレイ缶１ａと関連づけら
れ、それらデータ・アレイ位１ｉ７の各々に主記憶装置
δの同じセクターからの１ブロツクのデータを貯蔵する
ように構成される。そのデータ・ブロックのグループは
直接にデータ・アレイ位１６′に写像されるが、主記憶
装置の書りターは単に連想的に写像される。データ・ブ
ロックのグループは直接写像されるので、各ブロック位
置は、セクターにはかかわりなく、その事前指定された
データ・アレイ位１ｄにしか記憶されず、従って取り出
し中の所望のブロック・グループが存在するか否かを決
定するためにはそのグループ識別をもつ１つのタグ・ア
ドレスのみを探索すればよい。

１つのグループ内での各個々のブロックの存在は個々の
妥当性ビットに基づく。そのブロック・グループがキャ
ッシュ中に存在し且つ必要とされる特定のブロックが有
効なものでろる場合、キャッシュ内の所望のワードの探
索は成功して、「ヒツト１」と呼ばれろ。そうでない場
合は、「ミス」が検出される。複数のデーテ：ブ、ロッ
クが主記憶装置から取り出されてキャッシュに転送され
ろとき、それらの妥当性はタグ・ワードと関連して記憶
される適当な妥当性ビットによって表わされる。１？？
換されるべき最も以前に使用されたタグ・ワードおよび
ブロック・グループを定義するために、１ｂ゛換アレイ
をそのセット連想セクター・キャッシュ□と共に使用す
ることもできる。

各タグ・ワードは、データ・アレイ中の初数の位置をア
クセスできるので、必要なタグ記ｔｌｊ容量が少なく、
従って回路が少なくコストが安くなるという利点かめる
。セット連想緩衝記憶機構の場合と同じく、タグ・アレ
イならびにデータ・アレイの探索は同時に行なわれる。

即ち「ヒツト」又ハ「ミス」に従って、その指定された
データ・ブ　：ロックをデータ・アレイ−からゲートし
、または抑１１ｈ１することができる。主記憶装置から
複数ブロックを一括して取り出すことができるため、か
なりの数のアクセスおよびより大きなキャッシュｎ［ｒ
憶データの装置に必要なそのための転送時間の多くが除
かれる。もう一つ便利な点は、ブロック掟当性ビントヲ
タグ中のセクター識別（コード）と共に記憶し、情報の
信頼性が早期に決定できることでめろ。この方式は、さ
らに必要なレジスタの数が減少し、回路の単純化が可能
となる・〔良好な実施例の説明〕 第１図を参照すると、緩衝記憶機構を使用した典型的な
データ演算処理システムが概略的に示してろる。−これ
は、一般に主記憶装置１２中に命令およびオペランドが
常駐する中央処理装置１１用の高速度緩衝機構として役
立つ不発明のセット連想セクター・キャッシュ１０を含
んでいる。探索すべき命令またはデータの取り出しアド
レスが、母線１３ａによってメモリ・アドレス・レジス
タ１５に送られる。メモリから読み取られまたはそれに
書き込捷れた°データは、母線１４によってメモリ・デ
ータ・レジスタ１６に送られる。キャッジ″ユ１０はま
た中央処理装置１１または主記憶装置近１２からアドレ
スまたはデニタを受は取るために、母線１３Ｂおよび１
４ａを介してこれらの母線の各々（１３および１４）に
接続されている。

キャッシュ１０は、安来されたデータがその中に存在す
るときにそのデータをプロセッサに送る。

全体的Ｖこ１７として示しに制御回路が、中央処理装置
１１から取り出し要求を受は取ってぞの要求をキャッシ
ュにまたはアドレス・レジスタおよびデータ・レジスタ
にゲートする。

帆Ｊｌ！ｌ！装置１１がメモリ・アクセスを必要とする
場合、それはその命令−１にはデータのアドレスをアド
レス母線１３ａに載せ、同時にメモリ要求を制御論理装
置１７に出す。アドレスがキャッシュ１０に送られ、メ
モリ・アドレス・レジメタ１５中に記憶される。キャッ
シュはランダム・アクセス・メモリであり、以前に主記
憶装置から得Ｔニデータ■の高速度レボジトリ−として
鋤く。アドレスを受は取ると、キャッシュがその要求さ
れ１こデータを含んでいるかどうかについての決定が行
われる。要求データがキャッシュから入手可能な場合、
「ヒツト」が信号化され、論理装置１７か閥求データを
データ母線１０ａを介して処理装置１１にゲートする。

これは主記憶装置１２をアクセスすることなしに、メモ
リ・データ転送を完了させる。キャッシュ１０が要求デ
ータを含まない場合、「ミス」が信号化され、制御論理
装置１７がメモリ・アドレス・レジスタ１５をゲートシ
て、主記憶装置からのメモリ取出しつ゛イクルを開始す
る。主記憶装置から得られたデータが次にメモリ・デー
タ・レジスタ１６に運ばれ、データ母１ｉ！１４ａを介
して処理装置１１およびキャッシュ１０に置かれ、将来
の要求に備えてそのキャッシュにｍｌ憶される。

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

第２図は、セット連想セクター・キャッシュと今詠べ１
こいくつかのデータ単位の関係を図示しｆこものでめる
。−例として、有効アトυス１８Ｖ［、左から右に大き
さの順に示した５２個の２進ビン）ＡＯ〜Ａ３１からな
るものと仮定する。主記憶装置中の記憶セクターは、大
きい方から順に１４個のビットＡ１８〜Ａ３１によって
識別され、この１４個のビットはキャッシュのタグ・ア
レイ中の１つの明憶位置のタグ・アドレスとして使用す
る。第２の１０個のビットのグループ八８〜Ａ１７は、
セクター内のセット即ちブロック・グループを識別する
。この例では、タグ・アレイは、各タグ・アドレスに対
して、１０２４の記憶位置をもつものと仮定する。もう
２個のビットＡ６〜Ａ７（ｌ″１１各タグ・アドレスに
対応するデータ・アレイ中に記憶されているブロック用
のデータ・ブロック識別（コード）を形成する。かかる
各アドレスについて、４個のデータ・ブロックが記憶さ
れ、従って２個の２進ビツトでその特定タグ・アドレス
に対する４個の各々を識別することができる。

ワードおよびバイト識別（コード）はそれぞれ３個のビ
ットＡ５〜Ａ５およびＡＯ〜Ａ２を必要とし、ブロック
内にそれぞれ８バイトを含む８個のワードが存在するこ
とを示す。

主記憶装置中 ッシュ中のデータ・アレイΩ間の対応関係を第２図に示
す。ブロック・グループ０を形成するブロック１３０〜
１３３や、ブロック・グループ１を形成する０４〜Ｂ７
などのように４つのブロックより成るブロック・グルー
プを主記憶装置内に構成していることがわがイ）。主ｏ
１’４１：ｌＪ、装置からのデータ・ブロック・グルー
プは、キャッシュ中のどこにそれが常駐できるかに関し
て事前相定された位置を持っている。ブロック・グルー
プ０は、セット口のために留保されている位置にしか常
駐できず、ブロック・グループ１はセット１のために留
保された位置にしか常駐できず、ブロック・グループ１
はセット１のために留保された位置にしか常駐できず、
以下同様でめる。「キャッシュ」中のセットは、全て同
じグループおよび同じセクターからの連続するデータ・
プ°ロックから構成されていｄ。各セクターには０と識
別される多数のブロック・グループがめり、全てがキャ
ッシュのセット０に常駐しようと競合する。キャッシュ
・データ・アレイは１つのセクターからの全てのブロッ
クを記憶するのに充分な容量をもっており、−ｆｙ、二
必要ならば、各ブロック・セットが異なるセクタ一番号
わすようにすることもできる。タグ・アドレスがセクタ
ーを定義するが、後者はそれぞれ特定の瞬間に異なるこ
とができる。各タグ・アドレスは、指定されたブロック
とのみ関連しているた八′）、タグＶ１当該ブロック・
グループを含むキ、ヤツシュ中に常駐するセクターを定
義するようセクタ一番号だけを含めばよい。この仮定の
例では、１０２４個のタグ・アドレスがあり、各タグ・
アドレ、子は２１１Ｍのブロック・ヒントを含むので４
個のブロックを識別することができ、データ・アレイは
、４０９６個のアドレス可能なブロック記憶装（４゛を
誉むことができる。

第２図かられかるように、キャッシュの各基不下位部分
は、１個のタグ・アドレス４個の妥当性ビットおよび４
個のデータ・ブロックからなって　・いる。各妥当性ビ
ット位置が、データ・アレイ中のブロック・グループ中
の当該ブロックの妥当性を指定する。データ・ブロック
が主記憶装置から取り出され、キャッシュ・ケータ・プ
レイ中に置かれる場合、その妥当性ビットは（°有効状
態ないし論理１にセットされる。そのセットないしブロ
ック・グループ内の他のブロックは、要求されない限り
取り出さなくてよい。従来の装置では妥当性ビットは典
型的な場合データ・アレイ中にデータ・アレイ中にデー
タ・ブロックと共に記憶さオｌていたが、タグ・アレイ
中にそれらを記憶するのはより迅速でより大きな柔軟性
をもγこらす。１＋１１えば初期設定または他のセクタ
ーによる使用のたＭ）にキャッシュ中の１グループを消
去するには、４個の妥当性ビットがタグと関連している
場合、１動作サイクルだけしか必要ない。それらが、デ
ータ・ワードと関連している場合にに１消−入に１１回
の操作ブイクルが必要となるはずでろる＠ただし、ｎ二
１セット当りのデータ・ブロックの数。その上妥当性（
ビット）がデータ・ワードと関連していない場合、設計
者は低速でより安くより高密度のデータ・アレイを使用
する柔軟性をもつ。妥当性ヒツト八、機能的にはタグ・
アドレス・・ビットに関係し、ヒツトまたにミス条件を
決定する１こめ面速度ビットでなければならない キャッシュおよび読み書き動作を実施する定めのその湘
１１１回路が第３図に示される。動作を開始する前に、
全ての妥当性ビットがセットされて、その当該データ・
ブロックが無効でめること金車すように、キャッシュが
初期設定さ、ｒｔ、る。全てのキャッシュ・データ・ブ
ロックの無効化は、「ノくワーオン」信号または［キャ
ッシュ・リセット］指令が初期設定制御回路１９に送ら
れると起こる。

回路１９は、初期設定カウンター２０を０にセットさせ
る。カウンター出力がアドレス選択回路２−１によって
選択されタグ・アレイ即ちインデックス・アレイ２２に
対する一時アドレスとして働く。

初期設定回路１９に、さらにゲート５８および変換器３
８ａで書込み使用可能信号を発生し、第４図に示す妥当
性ビット改訂回路２６から来る４個の妥当性ヒーット制
御（ビット）の全てに０値を設定する。後の図かられか
るように、２−４解読器２４は、第３図のタグ・アレイ
２２中の妥当性ビット中に書き込むべき、当該データで
りる０出力をゲート２５ａ〜２５ｄに送るよう強制され
ろ。同時に、ゲート６６ａ〜３６ｄもゲート３７および
インバータ３７ａによってゼロにされる。再び第５図を
参照すると、刻時ステ゛ン“ブ信号力（カウーンタ−２
０に印加され、そどでタグ・・アレイ中のアドレス順序
によってステツプされ、強１１ｊｌ１２進ゼロが全体ア
レイ中に記録されてキャッシュ中の無効データを示す。

初期設定カウンター２０が回路２１によってタグ・プレ
イ・アドレス順序を完了すると、主記憶装置およびキャ
ッシュ制叫１論理１７（第１図）で使用するために「キ
ャッシュ作動可１１シ」”信号を出す。

キャッシュはタグ・アレイないし°インデックス・アレ
イ２２およびデータ・アレイを含めて、第６図のアドレ
スｆｉＪ線１５ａ：ヒに＋ａ−Ａ・れた各アドレーによ
ってアクセスされる。有効アドレスは、ｔｅｌｌえは５
２ビツトヲ・含み、そのうち上位１４ビツトは、セクタ
ー・アドレス識別（コード）、′ｌＯビットは、セット
ないしブロック・グループ識別（コード）、２ピツトは
、データ・ブロック識別（ニア−）’）、３ビツトはブ
ロック内のワード識別（コード）であり、５ピントはワ
ード内のビット識別（コード）を形成する。アドレスが
現わオＬγことき、１０ピツトのセットないしブロック
・グループ・アドレスが、母＃ｉ！２７上でタグ・アレ
イ２２およびデータ・アレイ２６に送られる。ｐこれら
のビットは、１４ビツトの当該タグ・ワードにアドレス
して、それをセクター比較回路に読み出させる。また、
母線２８ａを介して回路２８には、有効アドレスからの
１４セクター識別ビツトが現われる。２つの１４ビツト
・ワードが等しいと、常駐するブロック・グループが有
効アドレスによってアドレス中のセクターからのもので
るることを示す、セクター・ヒツト・ラッチ２９が使用
可能となる。等しくないと、セクター・ミスが定義され
る。この比較出力は、ヒツトまたはミスを検出するため
のゲ、−）　５０の１人力としても働く。

タグ・アｌレイ２２からのセクターまたはタグ・リード
の取り出しと同時にｊグ・ワードの１部である４個の妥
当性ビット、ｖ　ｉ〜ｖ４も、妥当性選択回路３１およ
び妥当性レジスター３２に取り出される。妥当性選択回
路３１への第２の入力は、アドレスからのブロック識別
ピットで′ろる。この２ビツトは、４つのデータ・ブロ
ックのうち１つか定義するので、所期のデータ・ブロッ
クに対応する妥当性ビットｖ１〜■４のうちの１つを選
択する。この例では、タグ・アレイ中の妥当性ビットは
、全てのブロック・グループに関して無効化されており
、°２進０がゲニ・）３０の第２人力に送られる。ゲー
ト３０の出力は低レベルのままで、変換器３０ａを通じ
てミスを示す。即ち、データ２６中に存在するデータ・
ブロックは無効でろる。

ゲート３０からの低出力が、そうでない場合は要求され
たブロック情報をデータ母線１４ａに１６ぐ、ゲート３
４を抑制する。

有効アドレスを受は取ったとき、１０ビツトのセットな
いしブロック・グループ八８〜Ａ１７・もデータ・アレ
イ２６に送られγこことを思い出して戴きたい。このｔ
＃報に、データ・アレイ中の’ＩＩ定　。

ブロック・グループに対するアドレスとして働き、２ピ
ントのブロック情報Ａ６〜へ７がそれと一緒になって、
グループ内の特定データ・ブロックの識別（コード）と
して働く。その結果、特定のデータ・ブロックが、ワー
ド選択マルチプレフカ゛６５な送られる。そこで５つの
ワード・ビットＡ３〜Ａ５に応じて、１つのワードが選
越されて、３ビツトのバイト識別（コード）ＡＯ〜Ａ２
による将来の解読のために、バイト選択マルチプレクサ
３５ａに送られる。即ちめろデータ・ブロックからの特
定バイトがゲート′５４に存在するが、ゲート３０から
のミス信号によってさらに伝送される□　ことを閉止さ
れている。

り・ブロックは、無効でろるかまたにキャッシュに不在
でめ威。セクター比較回路２８から等化信号が生じるが
、第５図の妥当性選択回路３１からは出力がない場合、
そのブロックは無効でめる。

１これに、セクター・ヒツトを示し、またキャッジ−中
に既に門しいデータ′・７゛ロツクを受は取るｋｅ’イ
ｌ＃機しているスロットがろること、を示す。新しいブ
ロックは、予約されたスロット中にロードしなければな
らず、その妥当性ピッドは、１にセットしなければなら
ない。タグ・ワード中の他の５つの妥当性ビットは、変
化゛しないま捷でなけれはならず、それに第４図に示す
妥当性ビット改訂回路によって実施される。

′第４図において、そのブロックを識別する不動アドレ
スの２ビツトが現在ロード中の特定データ・ブロック締
定義するｋめ、回路２４で解読８オ（る。１に等しい出
力が、解読器２４からの回線１不だけに現われ、ゲート
２５　ａ−２５ｄのうち当該のものに印ＪＪ口される。

このゲートは、ｉｌａ＞’ｌ　１を生成し、従って今や
新データ・ブロックに対すイ）妥当性ビットは、タグ・
アレイ中で１に変わることかで゛きる。残りの５つの妥
当性ビットは、第６図の妥当性レジスタ６２から第４図
の一致ゲート３６　ａ　−５６ｄに信号が印加されても
変化しな（＾ま捷でめった。これらのゲートは、セクタ
ー・ミスまたはＯＲゲート５７および変換器３７１Ｌ　
＋’こまって決定される初期設定妥当性条体がろる場合
以外ｉｄ、　イツモ妥当性レジスタの状態をゲート２５
ａ−２５ｄにパスする。従って、これらの条件（りどち
らも存在しないのでゲート５＋５ａ−３６ｄは、この例
では、解読器２４か′らの選択ブロックの１こめにルベ
ルをもたらす１つのゲート以外は′ゼロ・レベルの尚該
ＯＲ回路２５ａ−２５ｄに送信する。再び第３図を参照
すると１、新データ・ブロックがデータ母線１４ａから
データ・アレイ２６中にロードされ、新しい妥当性ビッ
ト改訂回路からタグ・アレイ２２中にロードされる。タ
イミングは゛、第１図の主記憶装置およびキャッシュ制
御論理１７によって、尚該時間に書込みパルスを用いて
制御される。書込みパルスは、第３図のＯＲゲート６８
がゲート３３から受は取、！ｌ）、３８ａで変換されて
、タグ・アレイおよびデータ・アレイで曹込み可能にす
る。・ キャッシュのアクセス中にラッチ２９がセクター・ミス
を′記録する場合には、別の型式のロード操°作が起こ
る。この瞬間、砺°換操作が要求される即ち新セクター
からのブロック・グループがキャッシュに指定されて、
そこに常駐していた他のブロック・グループを置換する
ことになる。新しいブロック・グループから１つのブロ
ックだけが、このときロードされイノこと′ｆ：ｔＭ摘
しておく。これは、妥当＋Ｊ１ビットが論Ｊ＋１！１に
ならなければならない、ロードされる１つのデータ・ブ
ロック以外の全ての妥当性ビットが０にならなければな
らないことを要求する。これもま１こ第４図の妥当性ビ
ット改訂回路によって実施される。所期のブロックを論
理１にセットするための論理径路は上記の場合と同じで
、解読器回路２４瀘当該線を活動化する。しかし、残り
の妥当性ピントは、Ｏ１（ケート５７および変換器３７
ａにセクター・ミス信−υが存在することによって０に
セントさ第１、従ってゲー′Ｆ、　３６　ａ〜３６ｄは
条件付けられない。即ち、ゲート２５ａ−２５ｄからの
改訂ビット線の１つは、論理１を出力とし、残りの線は
、論理０である。有効アドレスからの新しいセクター・
ビットは、同時に新しい妥当性構成をもつタグ・アレイ
２２中に口ｒドされ、−力士記憶装置から取り出された
データ・ブロックに、やはりゲート５５からゲート３８
への曹込みパルスの制御下で、データ・アレイ２６中に
ロードされる。

以上のキャッシュをロードする１こめの操作の５５ｄ明
から、所期のセクターがタグ・アレイ中１６す、所期の
データ・７゛ロツクに対する妥当性ビット中に論理１が
ある場合、回路２８でセクターが比較され、回路３１で
妥当性がチェックされろと、ゲート３０に等化出力が生
じ、ヒツト信号を生成することがわかる。１０ピントの
セットないしプロ゛ツク・グループおよびブロック識別
ビット対は、現在データ・アレイをアドレス中なので、
るるデータ・ブロックがワード選択マルチプレクサ３５
およびバイト選択マルチプレクサに送られている。

即ち、一致ゲート５０からの信号がゲート３４を活動化
させ、選択１れにバイトをデータ母線１４ａおよび処理
装置に送ることが可能になる。　　、。

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

本発明のセット連想セクター・キャッシュは、一定のデ
ータ容量をもつものとして説明してきたが、異なるニー
ズに順応するように変えることができる。その中には、
イブ数を変更すること、各タグと関連するデータ・ブロ
ックめ数を変更すイ）こと、るるいは全キャッシュを複
製して多方向キャッシュを作ることといった別法かろる
。上記の説明では、本例のタグ・アレイは１０２４ワー
ドでめった。１タグ・ワード当シのデータ・ブロック数
は同じままでタグ数を倍にすると、データ・アレイも倍
になるはずでめる。もう一つの別法として、１タグ・ワ
ード当りのデータ・ブロック数を増減することができる
。１タグ・ワード当りのデータ・ブロック数を８に変え
ると、データ・−ノルレイのサイ・ズが倍になる。もち
ろん、タグ・ワード中のピット数も、１タグ・ワード当
り４だけ増えることＶＣなる。この１タグ当りのデータ
・ブロック数を増加するのは、タグ・ワード数を増加す
るよりも、少しのハードウェアでよい。

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

第５図を参照すると、第１のキャッシュは、タグ・アレ
イ５０およびそのデータ・アレイ５１で衣わされ、８Ｒ
２のキャッシュは、タグ・アレイ６０およびその対応す
るデータ・アレイ６１で表わされる。各キャッシュのタ
グおよびデータ・アレイは、処理装置によって出される
アドレスを同時に受は取るように、適当にアドレス母線
１３ａに接続される。各タグ・アレイは、上記で第６図
に関して説明したように、それぞれヒツト／ミス−□理
回＆！６５２．６２および委尚Ｙト制御論１１！回路５
３．６３をもっている。各回路５２または６２は、第３
図の妥当＋′１選択回路３１、妥当性レジスタ５２、お
よび第４図の妥当性改訂回路の１ブロック人現ツシュ１
セクターまたは＋キャッシュ２セクター・ヒツト（信号
）を出すとき、タグ・アレイ中のラッチ２９でセクター
・ヒツトの表示をもたらす。

検索されたデータ・ブロックが回路５３１には６６によ
って有効と決定され、第５図の各キャッシュに対してセ
クター・ヒツトがろる場合、ゲート３０の出力信号十キ
ャッシュ１ヒツトまたは＋キャッシュ２ヒツトがゲート
信号として働き、各データ・アレイに対するゲート５４
または６４か生成されろ。

処理装置が読み取り操作を実施するとき、両方のキャッ
シュは同じ有効アドレスを受は取り、ヒツト／ミス検査
を実施する。例えば処理装置がセット０をアドレス中の
場合、所期のセクターおよびブロック・グループは、ど
ちらかのキャッシュに含まれていることも、どちらにも
含まれていないこともめり得るが、両方に含まれること
はない。

個別ヒツト／ミス検査の結果が、ＯＲゲート７０お゛よ
び変換器７０ａで分析され、合成ヒツト／ミス信号をも
たらす。処理装置に戻る伝送用に有効なデータ・ブロッ
クがみつかった場合には、ヒラ）（Ｉｉｉ号）をもつキ
ャッシュだけが、その当該ゲート回路５４またに６４を
介して、デニタ母線り４ａ土にデータをゲートする。ど
ちらのキャッシュも、その当該回路５２または６２から
ＯＲゲードア０に論理１出力を送らない場合に、ミス信
Ｙすが出され、データを主記憶装置から運ばねばならな
いＯ ミス信号か出るとはいえ、一方のキャッシュがセクター
・ヒツト（信号）をもち、両方がセクター・ミスを経験
した尤とはめり得る。１つのキャッシュがセクター・ヒ
ントを示す場合、そのキヤ７シュハ、新しいデータ・ブ
ロックのために予約されたスロットをもっており、その
データ・ブロックのロードを受諾する。この条件が表示
され、電う上方のキャッシュにロードするのをｌ５１１
止するｋめの禁止信号が生成される。例えばキャンシュ
１のｆｉｊｌ路５２からの＋士ヤツシュ１セクター・ヒ
ツト信号は、キャッシュ２をロードすることにえすする
禁止信号でろる出力を、０Ｒ７２で生成する。

同Ｑに、Ｉ！ｌ！回路６２からのキャッシュ２セクター
・ヒツト信号は、０１１ゲート７６に入力を与え、敵者
がキャッシュ１に対する禁止信号を出力として生成する
。キャッシュをロードすることを禁止する信号は、第３
図の変換器３３ａ丸・よびＡ　Ｎ　ｉ＞ゲート３３に送
られ、曹込みパルスが県、止されたキャッシュに書込み
可能信号を発生させるのを使用禁止する。

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

交換アレイ７７は、どちらかのタグ・プレイと同様に、
母線１３ａ上の有効アドレスから、１０個のセットない
しブロック・グループ・ピッ）Ａ８〜Ａ１７によって同
時にアドレスてれる。次に交換アレイをアドレスすると
、選択されＬピットおよび８０に印ＩＪ１１される。ラ
ッチ゛がオンでめり両方のタグ・アレイがセクター・ミ
スを示す場合には、一致ゲート７９が出力として交換ゲ
ート信号を出し、ランチ７８がオフのままであり、両方
のタグ・プレイがセクター・ミスを示す場合には、ゲー
ト８０が出力ゲート信号を出すぎ 例えは、交換アレイからアドレスされたセント内で、キ
ャッシュ２が最も最近に使用’ｇオｔｙ、−ことを示す
論理１が出た場合、ラッチ７８がセットキれて、ゲート
７９がキャッシュ１中のブロック・グループの交換を示
すその出力信号を出す。交換アルゴリズムは、最も最近
に使用されたデータが最も再使用されやすいという原Ｆ
１−を使っている。

従って、最も以前に使用されたデー１．夕が交換される
。ゲート７９またに８０のどちらかからの交換信号が入
力として当該のＯＲゲート７２および７６に送られ、各
キャッシュにロードすることを禁止する信号を生成する
。

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

正常なキャッシュ操作中に、キャン’／−”−１カｍｔ
み取り操１作中のセクター・ヒツトを経験し１こ場合、
ゲート７は論：ｐｌｊ　１にセットされ、ゲート７５に
論理０にセットされて、論理０でめ６人力■１ｆ：交換
アレイにロードさせる。キャッシュ１中のセクター・ヒ
ントが、交換−アレイ中にキャッシュが最゛、近に使用
ｊされたことを示す、論理０をロードさせることを指摘
しておく。同様にキ゛ヤノシュ２がセクター・ヒツトを
経験した場合は、入力Ｉ２が選択され、論理が交換アレ
イ中にロードさＪｔろ。

どちらのキャンシュもセクター・ヒツトを経験しない場
合は、現在交換アレイ中に記憶さ第１ていイ。

ビットの逆転が、入力ＩＯｋ介して選択さオ【る。

例えば、′どちらのキャッシュもセクター・ヒントを経
験仕ず、交換アレイからラッチ７８中ｐｃ　ｉが読み取
られると仮定する。これにより、ゲート７９が活動状態
になり、キャッシュ１虫のブロック・グループを交換し
、こうしてキャッシュ１ｆ：最近使用されたものにする
。従ってランチ７８の逆転部、ＴＩｌ！０が交換アレイ
中にロードされ、キャッシュ１を最近に使用されたもの
として定義する。

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

【図面の簡単な説明】

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

Claims (1)

1. 【特許請求の範囲】 各々が複数のデータ・ブロックを記憶し得る複数のセク
   ターに分けられた主記憶装置とデータを処理し且つ前記
   主記憶装置からデータ・ブロックを取り出すための主記
   憶装置アドレス−を発生するプロセッサとを有するデー
   タ処理システムにおいて、 ・グル！プに分けられ１こ複数の記憶位置を有するデー
   タ・アレイにして、該記憶位置の各々は前記データ・ブ
   ロックの１つを記憶し、前記主記憶装置アドレスを構成
   するグループ・アドレス及びブロック・アドレスに応答
   して前記記憶され１こデータ・ブロックが読出されるよ
   うなデータ・アレイと、 複数の記憶位置を有するタグ・アレイにして、該記憶位
   置の各々は前記データ・アレイに貯蔵されたデータ・ブ
   ロックの各グループに対するセクター・アドレスを含ん
   だタグ・ワードを貯蔵し、前記グループ・アドレスの発
   生に応答して前記セクター・アドレスが読出されるよう
   なタグ・アレイと、 前記タグ・ワードにおけるセクター・アドレスと前記主
   記憶装置アドレスにおけるセクター・アドレス部分との
   一致に応答して前記グループ・アドレス及びブロック・
   アドレスに対応するデータ・ブロックの少くとも一部分
   を前記データ・アレイからゲートするゲート手段と、 より成る緩衝記憶機構。