JPH0551936B2 - - Google Patents

Description

【発明の詳細な説明】 Ａ 産業上の利用分野 本発明は、コンピユータ・システムにおけるキ
ヤツシユ・メモリの分野に関する。キヤツシユ・
メモリは、機能に応じて様々なタイプがあるが、
一般的に言つて、コンピユータ・システムが直に
働きかける、情報の一時的な記憶機構であり、大
規模なメイン・メモリ・システムとは別個のもの
である。キヤツシユ・メモリがメイン・メモリに
接続されたり、働きかけたりする方法は、コンピ
ユータのパフオーマンスにとつと重要である。本
発明は、特にセクシヨンまたはパーテイシヨン
（区画）に分けられ、パーテイシヨン・ルツクア
サイド・テーブル（partion look−aside table、
以下、PLATと略す。）を備えたキヤツシユ・メ
モリに関する。PLATは、キヤツシユへのアクセ
スががなされるときに、情報を持つキヤツシユ区
画を識別する。アクセス対象の情報の場所を識別
できないとき、PLATは他の機能を開始する。

Ｂ 従来技術およびその問題点 高速の、ソフイステイケートされたコンピユー
タのパフオーマンスにおいて最も重要なフアクタ
の１つは、連想（associated）メモリ・システム
のパフオーマンスである。このようなコンピユー
タ・システムでは、入出力情報の処理はキヤツシ
ユ・メモリの使用を通じて促進されるであろうと
考えられている。キヤツシユ・メモリの容量が大
きくなればなるほど、そして動作速度が高速にな
るほど、コンピユータ・システム全体のパフオー
マンスが良くなることが知られている。キヤツシ
ユ・メモリのパフオーマンスを向上させる様々な
先行技術がある。その中には、種々の組織的関係
にあるマルチ・キヤツシユ・メモリの使用が含ま
れる。例えば、命令（インストラクシヨン）とデ
ータについて別個のキヤツシユ・メモリを使うこ
とが知られている。他のキヤツシユ・デザインに
よれば、２つのキヤツシユが奇偶インターリー
ブ・デザインにおいて並列に使用され、データ・
ストリング当りの、キヤツシユから情報をメモ
リ・アクセスする時間が改善される。また、他の
キヤツシユ・デザインでは、階層をなして並べら
れた様々なサイズのキヤツシユが用いられる。こ
れらの中には、２以上の処理要素または実行装置
によつて使用され、短い時間でいくつかの種々の
キヤツシユ・アクセスが開始され得ることを意図
しているものもある。

こういつた従来のデザインの典型的な問題点の
１つは、キヤツシユ・リクエストがなされたとき
に、キヤツシユがサーチを行つて情報がアベイラ
ブル（使用可能）か否かを決定しなければならな
いことである。キヤツシユ・アクセスが成功した
なら、リクエストを出している要求ユニツトへ情
報が渡される。情報が使用可能でないならば、続
いてキヤツシユ・ミス・ルーチンが呼ばれ、要求
ユニツトが待機したり他のことをしている間、メ
モリの他のレベルからリクエストされた情報を呼
び出す。ほとんどのキヤツシユ・デザインでは、
キヤツシユ・ミスが生じるとかなりの時間ペナル
テイがあるので、キヤツシユ・ミスが頻発するこ
とのないようにデザインが最適化されている。

従来、通常のマルチ（多重）プロセツサ環境
は、プロセツサ毎に独立したキヤツシユ・メモリ
を備えている。しかしながら、共通のメイン・メ
モリを使うにもかかわらず、プロセツサ毎に独立
したキヤツシユを備えることは、高価であり、非
効率的である。さらに、２以上のプロセツサが同
じ情報を使用する必要がある場合、異なるキヤツ
シユにおいて情報のマルチ・コピーを管理するこ
とは、困難、かつ複雑である。しかし、従来は、
マルチプロセツサ環境において、単一キヤツシユ
を管理する場合の複雑さまたは低効率と比べると
多重共有キヤツシユまたは独立したキヤツシユを
管理する場合の方が好ましいと示されている。

米国特許第4169284号明細書には、各プロセツ
サ記憶リクエスト・サイクルに際してキヤツシ
ユ・アクセス・タイミング・サイクルを２つ与え
るキヤツシユ・メモリ・コントロールが示されて
いる。このキヤツシユは１サイクルにつき２以上
のアクセスを可能にするけれども、時間インター
リーブ式キヤツシユを表わしており、真の同時ア
クセス式キヤツシユではない。

米国特許第4371929号明細書には、記憶域が区
画され、時間インターリーブ式に機能するキヤツ
シユ・メモリが示されている。

米国特許第4441155号明細書には、キヤツシ
ユ・ミス率を低くするためのキヤツシユ・アドレ
ツシング・コントロール・システムが示されてい
る。

米国特許第4442487号明細書には、異なるレベ
ルのキヤツシユ、およびキヤツシユがプライベー
ト・キヤツシユ・システムと共有キヤツシユ・シ
ステムに分かれている様子が示されている。プラ
イベートおよび共有キヤツシユ・システムは、互
いの間でのスイツチング機構を備えた、基本的に
は独立したキヤツシユであり、同一のキヤツシユ
の中の別個の部分ではない。このデザインは、マ
ルチプロセツサ・システムにおいて、他のデザイ
ンだと必要になる相互の間合せをなくしつつ、メ
モリ機構を共有することを可能にする。

米国特許第4463424号明細書では、キヤツシ
ユ・メモリを使用するプロセスの要請に基づいて
キヤツシユ・メモリを区画して空間を割り振るキ
ヤツシユ管理システムが示されている。区画の割
振りはスーパバイザ・プロセスが行い、物理的に
決まつているわけではない。

米国特許第4464712号明細書では、独立したペ
ージのサブセツトからなるキヤツシユ・メモリ・
システムが開示されている。ページ・サブセツト
は、キヤツシユ内容の交換（リプレースメント）
のためのアクセスを制御する交換フラグ機構に関
連している。

米国特許第4484267号明細書では、各プロセツ
サがプライベート・キヤツシユを持つマルチプロ
セツシング環境が示されている。各キヤツシユは
デイレクトリを持ち、デイレクトリは関連キヤツ
シユ・ラインがストア・スルーまたはストア・イ
ンのどちらのモードで動作するかを制御する共有
フラグを含んでいる。このため、２つの異なるタ
イプのキヤツシユ動作モードが可能になり、普通
のキヤツシユ・アクセス、および他のキヤツシユ
との相互間合せの両方の処理に使える。

また、米国特許第4503501号明細書では、スー
パバイザ・コントロール・システムによつて領域
へ区分されるキヤツシユ・メモリ空間が示されて
いる。米国特許第4493033号、第4195342号明細書
では、時間インタリーブ式で動作するデユアル・
ポート・キヤツシユが示されている。米国特許第
3618041号明細書では、命令とオペランドの異な
るキヤツシユへの分離が示されている。米国特許
第4502110号明細書では、オペランド用メモリと
命令用メモリのサイズが等しいスプリツト・キヤ
ツシユが示されている。

IBM Technical Disclosure Bulletin、
Vol.22、No.２，1979年７月、851〜852ページに掲
載された“Partitioned Memory And Split
SCE For Asymmetric Multiprocessor”という
題の論文には、スーパバイザのコントロールの
下、メモリを２つのセクシヨンに分け、アクセス
を２つのセクシヨンのうちの１つに制限する電子
的なフエンスが示されている。

キヤツシユ・メモリのデザインの改善の必要性
はひき続きあり、特に短時間の間にまたは実質的
に同時にきわめて多数のリクエストを処理するの
に使い易るキヤツシユ・デザインの必要性は高
い。

Ｃ 問題点を解決するための手段 本発明は、改善されたキヤツシユ・メモリ・シ
ステムである。この改善されたキヤツシユ・メモ
リは、多数の処理エレメントを持つ環境、または
マルチプロセツサ環境において、特に効果を奏す
るが、このような環境でなければ効果を提さない
というものでもない。

シングルCPUのコンテクストにおける多重処
理には、多数の命令処理ユニツトと多数の実行処
理ユニツトが関係する。オブジエクト・プログラ
ムの実行に要する時間を減らすために、該プログ
ラムからの多数の命令を並列に処理し、そして並
列に多数の実行ユニツトを呼び出すことが望まし
い。このようなやり方には、多数の命令デコー
ダ、並列命令ストリーム、および「アウト・オ
ブ・シーケンス」実行が関係する。通常、キヤツ
シユから命令とデータ・オペランドの両方がリク
エストされるので、多数のキヤツシユ・ポート、
およびシングルCPUマシン・サイクルの間での
多数の独立したキヤツシユ動作を提供することが
望ましい。

本発明のキヤツシユ・メモリは、Ｍ個のセクシ
ヨンに区分されている。ここで、Ｍは２の累乗、
例えば８であることが好ましい。キヤツシユは、
１サイクルにつき、１区画（パーテイシヨン）に
おいて１つのイベント（事象）を実行することが
できる。つまり、１サイクル当りＭ個のイベント
が実行可能である。キヤツシユはＮ個のポートを
持つ、ここで、ＮはＭ以下である。Ｎはマシンに
固有の数となるが、通常、Ｍ未満であり、２でフ
アクタ可能（factorable）である。本願の実施例
では、キヤツシユは８個の区画と６個のポートを
持つ。なぜなら、これらの数は、デザインの複雑
さおよびパフオーマンスの改善の適当な尺度を考
慮するとき、実現可能で有用なデザイン・フアク
タであると思われるからである。もちろん、区画
の数は８に限られない。４，16、または32であつ
て差し支えない。キヤツシユを制御するのには、
区画ルツク・アサイド・テーブル（partition
look−aside table、PLAT）が使われる。
PLATは、リクエストがキヤツシユに送られたと
きに情報を求めてアクセスすべき正しい区画を識
別する。

各区画は、独立して並列に動作する。各区画
は、各ママシン・サイクルで、ストアまたはフエ
ツチ動作を実行し得る。任意の区画が任意のポー
トに接続され得るように、アドレス・スイツチ、
データ・バス・スイツチ、および特別な制御シス
テムが提供される。したがつて、区画とポートの
多数の組合せをサイクル毎に制御することができ
るので、キヤツシユは各サイクルにおいてストア
とフエツチＮ個の組合せを実行することができ
る。キヤツシユは、区画の数が組連想式（set−
associative）ビンの数に等しくなるように設計
されている。キヤツシユ・データは、通常特定の
ビンに割り当てられる全データが対応する現実の
区画にも割り当てられるように、配置される。す
なわち、あるキヤツシユ・ラインはある単独の区
画の中に完全に含まれている。したがつて、リク
エストが異なるキヤツシユ区画へ向けられる場
合、多数の実行ユニツトを有する１つのプロセツ
サはいくつかのストアおよびフエツチを同時に実
行し得る。

PLATは、キヤツシユを制御するとともに、最
近アクセスされたキヤツシユ・ライン・リクエス
トのセツトを、そのライン・アドレスについての
区画割当識別子とともに記憶する。命令リクエス
ト用とオペランド・リクエスト用に、多数の
PLATを用意することができる。記憶された情報
を使つて、PLATは、マシンの生成したアドレス
を、該情報がキヤツシユに存在していると判断し
た場合、正しいキヤツシユ区画へ向ける。PLAT
におけるミスは、キヤツシユ・ミスを意味するわ
けではない。区画情報がPLATにないならば、グ
ローバル・リクエストを使つて、キヤツシユ・ク
リエストがすべての区画とキヤツシユ・デイレク
トリへ同時に向けられる。グローバル・リクエス
トの結果として情報がキヤツシユにおいて見つか
ると、ライン・アドレスと区画識別子を使つて
PLATが更新される。情報がキヤツシユで見つか
らないならば、既知のキヤツシユ・ミス・ルーチ
ンが使われる。例えば、デイレクトリ・ルツクア
サイド・テーブル（Directory Look−Aside
Table、DLAT）を使つて、メイン・メモリまた
はより高レベルのキヤツシユがアクセスされる。

キヤツシユ・ミス制御論理は、ある程度、
LRU（最近最も使われていない）アルゴリズムを
採用している。該アルゴリズムによつて、より高
レベルの記憶階層からフエツチされた新しいライ
ンがロードされる場所、つまりこのキヤツシユの
場合は区画番号を決定する。このように、新しい
キヤツシユ・ラインは、LRU式ですべての区画
へローテートされる。

区画（された）キヤツシユの実施例は、L1キ
ヤツシユと呼ばれ、プライベートなプロセツサ・
キヤツシユである。L2，L3キヤツシユは、L1キ
ヤツシユよりも大規模で、かつメイン・メモリに
近く、共有することも可能である。最初、この
L1キヤツシユは、新しいラインのロード動作に
先立つて古いラインのキヤスト・アウトを実行す
るわけではない。なぜなら、L1キヤツシユのス
トア・スルーがインプリメントされるからであ
る。つまり、すべてのストア・リクエストはL1
へ、そして少なくとも１つの高レベル記憶階層へ
送られる。新しいラインのデータをキヤツシユに
ロードする結果、Ｍ個の区画のうちの１個だけが
ビジーになる。

Ｄ 実施例 第１図に示すコンピユータ・システム１０は、
多重中央演算処理装置（CPU）１２，１４，…
…，１６を含む。各CPUは、システム制御要素
（SCE）１８に対する入出力接続を持つている。
システム制御要素（エレメント）１８は、記憶階
層２０の中のL2（レベル２）メモリへ接続され
る。これはさらに記憶階層の後続レベルL3（図で
は、22の番号を付している）、L4（図では24の番
号を付している）に接続される。レベルの順に容
量は大きくなり、かつプロセツサから遠くなる。
目的は、メモリ・サイズの割に命令とデータとで
きるだけ近づけることにある。コンピユータ・シ
ステムにおける多重記憶階層の使用は知られてい
る。上記レベルを示したのは、デザインのプラク
テイスを説明したまでであつて、区画キヤツシユ
の特定の要請に基づくものではない。システム制
御要素１８も、様々なチヤネル２６，２８，３０
を持つ。これらのチヤンネルは、ターミナル、プ
リンタ、およびデイスク・ドライブ等であり得る
入出力デバイスへ至る接続をもたらす。

各CPUは、命令および実行ハードウエア（符
号３２を付す）とハードウエア故障テスト論理
（番号40）を持つ。命令・実行ハードウエア３２
は、各CPUが従来の種類のコンピユータ操作を
実行することを可能にする。CPUに関連するの
はL1（レベル１）キヤツシユ・メモリ・システム
であり、これが本発明による区画されたキヤツシ
ユ・メモリ３４になる。このキヤツシユ３４は、
メモリがＭ個が区画され、データ・バス３６によ
つて命令・実行ハードウエア・ユニツト３２へ接
続される。命令・実行ユニツトのために意図され
た最適なデータ・フローの要請に応じて、デー
タ・バスはＮ本まで使用できる。

命令・実行ハードウエア３２によつて呼ばれた
記憶階層の中の情報の発見を容易にするために、
デイレクトリ３８が備えられる。デイレクトリ３
８は、制御パスおよびデータ・バス３９によつて
命令・実行ハードウエア３２に接続される。

ハードウエア故障テスト論理４０は、命令・実
行ハードウエア、デイレクトリ、およびキヤツシ
ユの間のアドレス、データ、および制御パスをモ
ニタする。これらのパスの何れかで万一故障が起
こると、診断、リカバリ、またはその他の訂正活
動のために、特定の故障に関連する故障ラツチが
セツトされ得る。

同じシステム制御要素１８に接続された他の
CPUも同様の内部構造を持つ。すなわち、命
令・実行ハードウエア、ローカルの区画キヤツシ
ユ・メモリ、記憶階層の内容にアクセスするため
の適当なデイレクトリを持つ。

第２図には、本発明に基づく区画キヤツシユと
PLATの構造が示される。Ｍ個のキヤツシユ区画
を持つキヤツシユ・メモリ５０が示されている。
この図の実施例では、簡単にするため、キヤツシ
ユ区画が８個示されている。これは、区画キヤツ
シユ・メモリの利点を得るのに加え制御を管理可
能にする上でも、多くの目的のために適切な数で
あると思われる。

様々なキヤツシユ区画５０が、データ・バス・
スイツチ機構５２を介してＮ個のデータ・バス・
ポートへ接続される。この場合、６個のデータ・
バス・ポートが使われる。なぜなら、８個の区画
を持つキヤツシユ・メモリと効率よく働くのに適
当な数であると思われるからである。

データ・バス・スイツチ５２は、入力制御バ
ス・ユニツト５４の制御下にある。該ユニツト５
４は、データ・バス・ポート用適当な制御信号を
出力する。キヤツシユは、出力制御バス・ユニツ
ト５６も持つ。該ユニツト５６は、出力データ・
バス構造体を制御する。入力制御バス・ユニツト
５４は入力アドレス・スイツチ５８に接続され
る。スイツチ５８は、アドレス・リクエスト・バ
ス６０による制御の下、要求されたアドレスを適
当な区画へ割り当てる。入力制御バス・ユニツト
５４はデータ・バス・スイツチ５２へも接続され
る。スイツチ５２は、データ・バス・ポートをア
ドレスされた区画へ割り当てる。

入力制御バス・ユニツト５４は、２本の制御バ
ス６２，６４と接続される。制御バス６２はC1
バスであり、キヤツシユ・ユニツトのグローバル
なリクエストを扱う。キヤツシユ・ユニツトのグ
ローバル・リクエストは、同時にキヤツシユの全
区画に向けられるリクエストである。このことは
後で詳しく説明する。制御バス６４はC2バスで
あり、特定の選ばれた区画へ向けられるキヤツシ
ユ・ユニツトのローカル・リクエストを扱う。キ
ヤツシユ・ユニツトのローカル・リクエストにつ
いても後で詳しく説明する。

出力制御バス・ユニツト５６は、キヤツシユか
らのローカル出力制御信号を扱うC3バス６６へ
接続される。ローカル出力リクエストの重要性は
後で説明するけれども、キヤツシユのどんな内容
もある特定の区画に存在しているわけだから、特
定の区画だけが出力リクエストを出すであろう
し、したがつて出力リクエストはすべてローカル
であつて、グローバルとなり得ないことがわかる
だろう。

各CPUは、それに関連して様々な演算および
論理ユニツトを持つ。第２図では、種々の要素
（エレメント）７０，７２，７４，……７６を持
つあるCPUが示されている。これらのユニツト
は望むどんなタイプのものであつてもよい。これ
らは、算術、論理、または命令処理要素の様々な
組合せによつて構成される。データ・バス・スイ
ツチ５２からのデータ・バスのそれぞれは、フエ
ツチ・バツフアと記憶（ストア）・バツフアの組
合せを介してこのCPUのグループへ接続される。
結果として、CPUへ至る複数の入力および出力
データ・パスが形成される。したがつて、デー
タ・バスが６本ある場合、そのうちの３本がフエ
ツチ・バツフア８０，８２，８４へ接続可能であ
り、２本がストア・バツフア８６，８８で接続可
能である。これらのバツフアのすべてが、CPU、
そしてその様々な要素へ接続される。

CPUは、メモリ階層へのリクエストを複数の
アドレス生成機構９０，９２，９４，９６、そし
て９８に対して起こす。アドレス生成ユニツトは
関連する（associated）PLATへ接続されてい
る。したがつて、CPUは複数のPLATユニツト
１００，１０２，１０４，１０６、そして１０８
を持つ。生成されたアドレスは、関連PLATへ行
くだけでなく、各アドレス生成機構についてのア
ドレス・バスにのせられ、アドレス・リクエス
ト・バス６０にのせられる。入力アドレスを受け
取ると、各PLATは、区画キヤツシユのグローバ
ル・リクエストをC1バスへ出力するか、または
区画キヤツシユのローカル・リクエストを、C2
バスのうちの選ばれたものを使つて出力する。

各PLATは、出力制御バス・ユニツト５６から
来る、ローカル入力制御信号がのる入力バネを持
つ。一般に、論理ユニツト７０のような中央プロ
セツサ論理ユニツトがメモリに対してリクエスト
を出すと、９０のようなアドレス生成ユニツトが
アドレス・リクエスト・バス６０にアドレス・リ
クエストを出力する。このリクエストはアドレ
ス・スイツチ５８とPLAT１００の両方へ行く。
PLATが、リクエストされた情報の置かれた区画
を識別できるならば、ローカル・リクエスト・バ
ス６４にリクエストが出され、入力制御バス・ユ
ニツト５４へ送られる。この結果、アドレス・ス
イツチ５８によつて、リクエストされたアドレス
が、キヤツシユの中のリクエストされた情報を含
む特定の区画だけへ向けられる。データ・バス・
スイツチ出力５２は切り換えられて、リクエスト
された情報をその位置する特定のパーテイシヨン
からそのために情報が獲得された特定の要求ユニ
ツトへ渡す。PLATが特定区画を識別できない場
合、グローバル・リクエスト・バス６２が活動化
され、アドレス・スイツチによつてアドレスがキ
ヤツシユ・メモリの全区画へ渡される。

ライン・フエツチ・バツフア１１０は、リクエ
ストされた情報がキヤツシユ５０にない場合に、
それを求めてリクエストが階層の中の次のレベル
のメモリへ回されるようにするためのものであ
る。したがつて、ライン・フエツチ・バツフア１
１０はキヤツシユのデータ・ポートの１つに接続
される。この例では、Ｎ番目、つまり最後のポー
トに接続されるものとして示されている。ライ
ン・フエツチ・バツフアは、アドレス・リクエス
ト・バス６０、および制御バス６４つまり制御信
号へも接続される。図では、記憶階層の次のレベ
ルからのデータ・バスが１１２として概略的に示
されている。ライン・フエツチ・バツフア１１０
は、その内容をキヤツシユに記憶するときに、選
ばれたただ１つのキヤツシユ区画にアクセスする
だけでよいことに注意することは重要である。ラ
イン・フエツチ・バツフアがキヤツシユに記憶さ
せているとき、他のキヤツシユ区画は普通に動作
し得る。第１３図も参照されたい。

一般的に言つて、第２図に示されるシステムは
次のように動作する。

キヤツシユは複数のセクシヨン、つまり区画
（パーテイシヨン）に分割される。各区画は独立
に、そして他の区画と並列に動作する。各区画は
マシン・サイクル毎に記憶動作またはフエツチ動
作を実行し得る。アドレス・スイツチ５８、デー
タ・バス・スイツチ５２および適当な制御システ
ムを備えたのは、任意の区画が任意の入力ポート
または出力ポートへ接続可能とするためである。
したがつて、メモリ動作の単一サイクルの間に、
区画とポート接続の多量の組合せが活動化し得
る。このため、キヤツシユは、単一のマシン・サ
イクルの間に、ポート数以下の数の記憶とフエツ
チの組合せを実行することができる。

区画の数は、キヤツシユ・デザイン用に選ばれ
たセツト連想（set−associative）ビンの数に等
しい。キヤツシユ・データの配置は、特定のビン
に通常割り当てられるすべてのデータが物理的な
区画に対応して現れるように割当てられる。

区画ルツクアサイド・テーブル（PLAT）は、
プロセツサ・デザインに組み込まれる。PLATの
厳密な論理的・物理的配置は設計者に関係し、マ
シンの編成に依存する。２以上のPLATにとつて
適切な配置は、プロセツサの中のアドレス生成ハ
ードウエアの近くである。典型的な中央プロセツ
サ・オーガニゼーシヨンを扱うために、多重
PLATを用いることができる。例えば、PLATの
あるタイプは命令リクエストの処理用に理想的に
設計されていてもよいし、またあるものはデー
タ・オペランド・リクエスト用に使つてもよい。
どちらかのタイプのマルチ・コピーがCPU論理
ユニツトによつて独立に使用され得る。

PLATは、最も新しくアクセスされたL1ライ
ン・アドレスのセツトを、かかる各ライン・アド
レスの区画識別子とともに記憶する。PLATは、
高いパーセントのL1キヤツシユ・アクセス要求
において、マシン生成アドレスを正しいL1キヤ
ツシユ区画へ向ける。このようなリクエストはロ
ーカル・リクエストと呼ばれ、ローカル制御ライ
ン・バス６４を使用する。PLATミスが生じる
と、対応するL1ラインに割り当てられた区画を
決定するために、生成されたアドレスをすべての
区画に同時に向ける必要がある。この場合、グロ
ーバル制御ライン・バス６２が使用される。この
とき、PLATの中に新しいエントリが設けられ、
ライン・アドレスと区画識別子が記憶される。同
じL1ラインに対する後続の記憶またはフエツチ
のリクエストは、該エントリがPLATからエージ
ングされる（aged）まで、正しい区画へ向けら
れる。

理想的には、本発明の区画キヤツシユ・メモリ
による最良のパフオーマンスは、ポートの数が区
画の数に等しく、しかもエクセス（excess）・サ
イクル毎に各ポートがある区画と接続される場合
に得られる。しかしながら、メモリ・アレイ・チ
ツプ当りの入出力接続数等の物理的な制約によ
り、ポートの最大数は制限される。

アドレス・ポートとデータ・ポートの間には直
接的な対応がある。つまり、アドレス・ポート１
はアドレス・スイツチ５８に接続されるが、それ
に対してデータ・バス・スイツチ５２へ接続され
るデータ・ポート１があるといつた具合である。
こういつたポートのペアは、ハードウエアにおい
て固定される。さらに、単方向のバス・ドライバ
を用いた場合、各データ・ポートはフエツチ・ポ
ートまたはストア・ポートのどちらかである。
CPUポートにて２重ドライバとデータ・スイツ
チを使う場合、各ポートはフエツチ・ポートとス
トア・ポートの両方の機能を果たし得る。しか
し、実施例では、ポートは単方向ポートとして、
フエツチ・ポートまたはストア・ポートのどちら
かであるとして、説明する。

上記のように、アドレス・スイツチは、グロー
バル・リクエスト・モードまたはローカル・リク
エスト・モードのどちらかで機能し得る。グロー
バル・リクエストの場合、アドレス・スイツチに
供されたアドレスがキヤツシユの全区画へ同時に
供される。したがつて、アドレスは、すべてのデ
イレクトリ・エレメントおよびすべてのキヤツシ
ユ・メモリ区画へ同時にスイツチされる。これ
は、グローバル制御バス６２の制御に基づいてい
る。グローバル制御サイクルは、キヤツシユの中
でデータが有効ならば８個のデイレクトリ・エレ
メントの１つの比較結果が正となり対応するキヤ
ツシユ区画へのゲートを開くという意味におい
て、従来のキヤツシユを使つた場合のように実行
される。この出力は要求データ・ポート・バスへ
スイツチされる。１つのグローバル・リクエスト
は単一のマシン・サイクルで実行され得る。

ローカル・リクエストの場合、アドレスはＭ個
のキヤツシユ区画のうちの選ばれた１つへスイツ
チされる。そして、ローカル・リクエスト処理用
にデイレクトリが使用されることはない。単一の
マシン・サイクルの間に、キヤツシユ・メモリへ
至るポートと同じ数のローカル・リクエスト・ア
ドレスがキヤツシユ区画へスイツチされ得る。こ
れは、各ローカル・リクエスト・アドレスがどの
区画に対するものかに依存する。したがつて、ア
ドレスされた区画のそれぞれが、単一のポートへ
一意的に接続され得る。連続するマシン・サイク
ルで、同じ区画へ多数のリクエストを出しても差
し支えない。入力制御バス６２，６４は、個々の
アドレス・ポート毎に、要求アドレスがグローバ
ル・リクエストまたはローカル・リクエストの何
れであるか、そしてどのポートがアクセスされる
かを決定する。リクエストがローカル・リクエス
トならば、制御バス６４によつて、ターゲツト・
キヤツシユ・ライン用に区画識別子が符号化され
る。

データ・バス・スイツチ５２を用いて、フエツ
チ・リクエストの度に区画キヤツシユ・アレイ５
０からの出力がデータ・バス・ポートへスイツチ
されるとともに、ストア・リクエストについては
データ・バス・ポートからの入力が区画キヤツシ
ユ・アレイへスイツチされる。要求アドレスがグ
ローバル・リクエストであるとき、つまりPLAT
ミスを示すときに、データが現実にキヤツシユの
中で見つかると、リクエストされたデータを
CPUへ返すだけでなく、区画識別子も制御バス
６６を経てCPUへ返される。その結果、PLAT
が該情報をそのアレイに追加する。PLATの中で
は新しいエントリが生成され、ターゲツト・キヤ
ツシユ・ラインアドレスと区画識別子の両方が記
憶される。該キヤツシユ・ラインが続いて参照さ
れるときは、PLATヒツトとなり、ローカル・リ
クエストが行われる。

この例では、キヤツシユがＮ個（６個）の直接
アクセス・ポートを持ち、CPUにはキヤツシユ
への直接アクセス・ポートが（Ｎ−１）個割り当
てられている。したがつて、プロセツサの持つキ
ヤツシユにアクセスするためのポートの数は、キ
ヤツシユのポートの数より１つ少ない。このケー
スでは、プロセツサには、キヤツシユへの直接ア
クセス・ポートが５個割り当てられている。最後
のポートは、ライン・フエツチ・バツフア１１０
のプツト・アウエイ（put−away）操作のために
予約されている。単方向バツフアの場合、各ポー
トはフエツチ・ポートまたはストア・ポートのど
ちらかである。今の例では、ポート１，２，３が
フエツチ、バツフア８０，８２，８４へ割り当て
られる一方、ポート４，５，６がストア・ポート
としてストア・バツフア８６，８８へ、そしてラ
イン・フエツチ・バツフア１１０へ割り当てられ
る。各ポートは、CPUのフエツチまたはスト
ア・バツフアが終端となつている。これらのバツ
フアのサイズはその最適デザインおよびバス転送
サイズに応じて、例えば８〜512バイトといつた
具合に、変化し得る。

CPUの個々の細部（サブデイビジヨン）は象
徴的なものであり、多くの動作が並列して実行さ
れ、したがつて１命令当りの平均サイクル数を減
らすべく１サイクル当りキヤツシユへの多数のア
クセスを要するような、そういつたCPUデザイ
ンを表現することを意図している。１以上の細部
を、コンピユータの可能な様々な機能を示す、命
令プロセツサ、固定小数点演算ユニツト、浮動小
数点演算ユニツト、ベクトル・プロセツサ等であ
ると考えてよい。キヤツシユ・ポートのCPU機
能への最適な割当ては、CPUデザインの最適化
に基づく。それには、キヤツシユに与えられたポ
ートの総数に対するストア・ポートとフエツチ・
ポートの組合せの最適化が含まれる。

７０，７２，７４，７６等の、中央プロセツサ
の各細部（サブデイビジヨン）は、そのプロセツ
サ機能に加えて、命令フエツチ、オペランド・フ
エツチ、またはオペランド・ストアに応じてキヤ
ツシユ・データが必要なときにアドレスを生成す
るハードウエア能力を持つ。これが、アドレス生
成ユニツト（ADDR）９０，９２，９４，９６，
９８として示されている。アドレス生成は、カウ
ンタのインクリメント、アレイ・スタツクからの
アドレスの読取、アドレス生成加算器からの結果
の受取等からなる。アドレスが与えられると、ア
ドレスはアドレス・リクエスト・バス６０にのせ
られる。バス６０は、アドレス・スイツチ５８の
みならず、１００，１０２，１０４，１０６，１
０８等のローカルPLAT、そしてライン・フエツ
チ・バツフア１１０につながつている。ライン・
アドレスはローカルPLATにおいてテストされ
る。PLATミスが生じると、PLATはグローバル
制御バス６２に該PLATについてはグローバル・
リクエストであることを示すビツトを出力する。
PLATヒツトが生じた場合は、ローカル・リクエ
スト制御バス６４のポジシヨンのうちの１つに、
アドレスが向けられるべき区画を示すビツトが出
力される。ローカル制御バスのポジシヨンにこの
ビツトを出すことによつて、ローカル・リクエス
トの存在の表示とリクエストされたデータに対応
するキヤツシユ区画の識別の両方が行われる。

第２図のシステムは各CPU論理ユニツトにつ
いて１つのPLATしか用意していないけれども、
デザインの要請に応じてPLATの様々な配列が可
能である。異なる機能のタイプ毎に異なるタイプ
のPLATを備えることが望ましい。どのタイプの
ものも、当該機能を営む各CPU論理にて複製可
能である。例えば、データ・オペランドのフエツ
チとストア用に理想的なタイプが備えられる。ど
のタイプのものも、マルチ・コピーをCPU論理
区画に戦略的に位置させてよい。各PLATは小さ
なレジスタ・アレイであり、例えば、１〜４個の
比較器を持つ。各PLATに必要なハードウエアの
量が比較的少ないので、ハードウエアの複製は難
しくない。PLATアレイの「組連想式（set−
associative）」配列はそのパフオーマンスを向上
させるので、多数の比較器を備えても差し支えな
い。

第３図は、第２図の区画キヤツシユ５０の具体
例を詳細に示している。グローバル・バス６２
は、中央プロセツサのポート１〜５をサービスす
る。グローバル制御バスの各ビツトは、CPUの
要求ユニツトを表示する。バス６２は、グローバ
ル・ポジシヨンを持ち得るのだけれども持たな
い。なぜなら、常に、ライン・フエツチ・バツフ
アのプツト・アウエイは、LRU論理に基づき、
アクセスを行う正確なキヤツシユ区画がわかつて
いるローカル・リクエストだからである。各
PLATタイプは、番号66で概略的に示される、ロ
ーカル制御出力バスＣ３を持つ。ここでは、１つ
のタイプが命令アドレス用であり、もう１つのタ
イプがデータ・アドレス用である。何れもが、多
重PLATコピーへ至る多重コネクシヨンを持つ。
この制御バス６６によつて、グローバル・デイレ
クトリ・サーチの結果決定された区画識別子が返
され、特定のPLATに新しいエントリとして記憶
される。ライン・プツト・アウエイ用には、第２
図に示されるポート６が使われローカルＣ３出力
制御バスは使用されない。なぜなら、ポート６
は、第１３図で詳しく示すように、最近最も使用
されなかつた（LRU）制御システムからスト
ア・リクエスト用の区画識別子を受け取るからで
ある。出力制御バスＣ３は、後述する有効スト
ア・ラインを含む。図面には、区画キヤツシユの
内部構造も示されている。各区画は、アドレス・
スイツチ、区画デイレクトリ、実際のキヤツシ
ユ・メモリ・アレイ、およびデータ・バス・スイ
ツチを含む。

第４Ａ，４Ｂ，４Ｃ、および第４Ｄ図には、第
２図に示すようなキヤツシユ・メモリ５０の８個
のキヤツシユ区画のそれぞれが示されている。そ
こでは、そのデイレクトリ・アレイ、メモリ・ス
タツク・エレメント、およびデイレクトリ・エレ
メントが、制御バス構造に接続されている様が示
されている。アドレスおよびデータのバスはこの
図では示されていないが、他の図で詳しく示され
ている。グローバル制御バス入力６２のすべての
ラインは、８個のデイレクトリ・エレメントのす
べて、つまりDIR.1〜DIR.8へ向けられている。
ローカル制御バスＣ２は６コンポーネント・グル
ープの制御ラインに分かれる。各コンポーネント
はメモリ・スタツク毎に１本のラインを持つ。し
たがつて、ローカル・バス入力６４のコンポーネ
ント・ラインのそれぞれは、メモリ・アレイのタ
ーゲツト区画メモリ・スタツク（STK）へ向け
られている。

ローカル制御バス出力６６のラインは、デイレ
クトリ・エレメントの各々の中のレジスタから導
かれる。この説明では、レジスタは３ビツトであ
り、各ビツトは次のような機能を持つている。す
なわち、ビツト１は、命令タイプPLATを示す区
画識別子である。ビツト２は、データ・タイプ
PLATを示す区画識別子である。ビツト３は、有
効ストア表示ラインである。デイレクトリ・エレ
メント用のレジスタは、メモリ構成の必要に応じ
て、他の構成をとつてもよいし、異なる機能を持
つてもよい。デイレクトリの中のレジスタの各ビ
ツトに対応させたローカル出力バスはユニークな
ラインを構成するので、信号を生成する特定キヤ
ツシユ区画デイレクトリの識別が可能である。こ
のようにして、ローカル出力バスは、グローバ
ル・リクエストの結果生じる区画識別子を受け取
る。デイレクトリ・エレメントの記憶問合せがポ
ジテイブならば、有効ストア（Ｖ／Ｓ）ラインも
そうである。記憶問合せ動作と有効ストア・ライ
ン生成は、グローバル・フエツチ・リクエストと
グローバル・ストア・フエツチの両方で実行され
ることに注意されたい。記憶問合せ動作には、有
効ビツト、排他ビツト、記憶キー・ビツト等のデ
イレクトリにおける様々な制御ビツトのテストが
関係する。

第５図に示すように、キヤツシユ・アドレス・
バス６０Ａは、本発明に従う８個の区画のそれぞ
れに接続される。同様に、出力データ・バスＤ
１，Ｄ２，Ｄ３ならびに入力データ・バスＤ４，
Ｄ５，Ｄ６も接続され、任意の区画からデータを
フエツチしたり、あるいは逆にストアしたりでき
るようになつている。各区画は独立したデイレク
トリ・エレメントを持つ。これは、例えば、スタ
ンド・アローンの連想アレイ・チツプとすること
ができる。デイレクトリとキヤツシユ区画が両方
ともアドレス・スイツチを持つのに対し、キヤツ
シユ区画だけがデータ・バス・スイツチを持つ。
様々な区画についての様々なアドレス・スイツチ
が概略的に示されている。

例えば、キヤツシユ５０の区画１は、アドレ
ス・バス６０Ａに接続されたアドレス・スイツチ
１５０を持つ。データ・バス・スイツチ１５２，
１５４も区画１に関連している。区画１に関連す
るデイレクトリ・エレメントは、デイレクトリ・
アドレス・バス６０Ｂに接続されたアドレス・ス
イツチ１５６を持つ。その他のキヤツシユ区画お
よびデイレクトリ・エレメントも同様に構成され
る。第２図および第３図のアドレス・バス６０
は、第５図のアドレス・バス６０Ａおよび６０Ｂ
という２つの部分から成り立つていることに注意
されたい。アドレス・バス６０の各ポートは、第
６図に示されるような３つのフイールドからな
る。デイレクトリ３８は、各アドレス・ポートか
ら中位および高位のビツトを要求する。一方、キ
ヤツシユは、各アドレス・ポートから中位および
下位のビツトを要求する。

第７図および第８図には、本発明で使う中央プ
ロセツサ・ポートの異なる２つの具体例が示され
ている。第７図では、命令または実行対象オペラ
ンドの一方のためのフエツチ・ポートとして使い
得る中央プロセツサ・ポート２００が示されてい
る。該ポートは、PLAT２０２、アドレス・リク
エスト論理ユニツト２０４、中央プロセツサの命
令、論理、または演算ユニツト２０６、入力バツ
フア２０８を持つ。さらにローカル記憶域（スト
ア）２１０を持つていてもよい。PLATは、C3
ローカル出力制御ライン２１２、C1グローバル
制御ライン２１４、およびローカルC2入力制御
ライン２１６を持つ。図面では、それぞれの動作
において必要とされるビツト数も各ラインと一緒
に示してある。アドレス生成ユニツト２０４は27
ビツトのアドレスを生成する。また、バツフア・
ユニツト２０８は144ビツトのカドワード
（quadword）を受け取るように設計されている。

第８図に示すCPUポート２２０はストア・ポ
ートとして構成されており、PLAT２２２、アド
レス・リクエスト論理ユニツト２２４、CPU論
理ユニツト２２６、データ・バツフア２２８、そ
してローカル記憶域２３０を持つ。ここでも、
PLATは、C3ローカル出力制御ライン２３２、
C1グローバル入力制御ライン２３４、C2ローカ
ル入力制御ライン２３６を持つ。さらに、PLAT
は、有効ストア（Ｖ／Ｓ）ライン２３８を持つ。
バツフア２２８は、144ビツトのカドワードを扱
うように設計されている。有効ストア・ライン２
３８はPLAT２２２に入力されるので、ポートが
ストア・リクエストを出すときに、PLATにて有
効ストア状態が判別され得る。

第９図には、PLAT３００の論理動作が示され
ている。C3ローカル出力バス３０２はスイツチ
ング・ゲート・システム３０４から始まる一方、
C2ローカル入力制御バス３０６はゲート３０８
に接続され、かつC1グローバル制御バス３１０
はゲート３１２に接続される。CPU３２０はア
ドレス生成機構３２２を持つ。該機構３２２は、
アドレス・バス３２４を介して区画キヤツシユ
へ、そしてバネ３２６を介してPLATへ、アドレ
スを送る。アドレスは比較器３２８へ送られる。
比較の結果、ヒツトはライン３３０を経てゲー
ト・ユニツト３０８へ記録される一方、ミスはラ
イン３３２を経てゲート・ユニツト３１２へ記録
される。PLATにおけるミスとヒツトのどちらが
記録されるかに応じて、C1ライン３１０へグロ
ーバル制御信号が送られたり、あるいはPLATの
見つけた区画メモリの中の場所を示すC2ローカ
ル制御信号がライン３０６へ送られたりする。

通常の動作時、CPU３２０はアドレス生成ハ
ードウエア３２２を起動して、出力アドレス・バ
ス３２４に要求アドレスを出させる。同時に、ア
ドレスはPLAT３００に送られ、そのクラスで一
致する１以上のアドレスがPLATアレイから読み
取られる。アドレスの残りの高位ビツトは、各
PLAT組連想エントリと比べられる。

PLATヒツトが生じた場合、PLATの区画識別
子アレイ・フイールドに記憶されている８ビツト
のうちの１つが、C2制御バス３０６の８個のポ
ジシヨンのうちの対応する１つへ出力される。こ
れによつて、指定されたキヤツシユ区画へのロー
カル・リクエストであることが表示される。

PLATミスが生じた場合、バス３１０上の単一
ビツトのC1グローバル・リクエスト・ラインが
立ち上げられる。PLATミスの場合、要求アドレ
スとC3制御バス３０２にのつて返される区画識
別子とを記憶するためのゲートの活動も開始され
る。このようにして、グローバル・リクエストに
応答して、PLATの中に新しいエントリが作られ
る。PLATの中のこの新しいストア・エントリの
生成は、新規ストア・ボツクス３３４がライン３
３２からミス表示を受け取るときに行われる。こ
のとき、ボツクス３３４は、バス３２４から受け
取るアドレスをPLAT３００のアドレス・アレイ
へ配置することができる。

一般に、PLATアレイ３００は、組連想式アレ
イである。多重セツト、つまりセツトＡ、セツト
Ｂ等において、それぞれ一致アドレスの有無が調
べられる。PLATのセツト・コンパートメントの
各々は、出力ゲート３０８、アドレス比較器３２
８、グローバル・ゲート３１２、入力ゲート３０
４、３３４のセツトを独自に持つている。ある
PLATサイクルではただ１つの一致アドレスがヒ
ツトし得るように、ゲート３０８の出力同士に
OR操作が施される。同様に、各セツトのゲート
３１２からの出力３１０は組み合わされて、単一
のC1リクエスト・ラインを形成する。この場合、
グローバル・リクエストＣ１がバス３１０へ出さ
れる前にすべての組連想比較器からミスが発生し
なければならないわけであるから、出力３１０同
士にAND操作が施される。PLATの入力側では、
アドレス・バス３２６と制御バス３０２が、新た
なPLATエントリが生成される際のLRU論理に
より決定される通りに、組連想コンパートメント
のうちの任意の１つへ、セツトＡまたはセツトＢ
へといつた具合に、ゲーテイングされる。

第１０図は、命令を扱うPLATデザイン用に使
い得るタイプのPLATエントリ・データ・フイー
ルドを示す。アドレス・フイールド４００はアド
レスを含み、区画識別子４０２は該アドレスを持
つキヤツシユの区画を示す。制御フイールド４０
４の中には、有効ビツト・フイールド４０６と、
パリテイその他の制御機能のためのフイールド４
０８がある。

第１１図は、データ・タイプPLAT用に使い得
るタイプのPLATエントリを示す。区画識別子４
０２とともにアドレス・フイールド４００が備え
られている。しかし、制御フイールド４１２は少
しばかり異なつている。有効ビツト・エントリ４
０６の他に、有効ストア（Ｖ／Ｓ）ビツト４１４
が備わつている。さらに、前記のようなパリテイ
その他の制御機能用のフイールド４１６がある。

第１０図と第１１図に示されるPLATタイプ
は、ローカル・キヤツシユ（L0）の形をとるこ
ともある拡張CPUバツフアが存在する場合にあ
り得る動作を意図している。この場合、PLATと
ローカル・キヤツシユ用のデイレクトリが並列に
動作し得る。アドレス生成機能が発生した後、ア
ドレスは、アドレス・クリエスト・バス、
PLAT、ローカル・キヤツシユ・デイレクトリ、
およびローカル・キヤツシユ・アレイへ送られ
る。

ローカル・キヤツシユ・デイレクトリにおいて
ヒツトすると、データがローカリ・キヤツシユ・
アレイから関連する中央処理エレメントへ送られ
るので、他のアドレス・パスは無視される。ロー
カル・キヤツシユ・デイレクトリにおいてミスし
てもPLATにおいてヒツトすれば、L1区画キヤ
ツシユへローカル・リクエストが出される。ロー
カル・キヤツシユ・デイレクトリ・ミスとPLAT
ミスが重なると、区画キヤツシユに対してグロー
バル・リクエストが出される。

第１０図と第１１図に示したPLATエントリの
２つのタイプの相違点は、データ・タイプPLAT
エントリにおいて有効ストア・ビツトがあること
である。このビツトは、グローバル・リクエスト
の後で、データ・タイプPLATの中で新しいエン
トリが生成されるときにオンにセツトされる。こ
のとき、記憶問合せ動作が区画キヤツシユ・デイ
レクトリで実行される。この動作には、記憶キ
ー、有効ビツト、排他ビツト、キヤツシユにおけ
る他の機能のテストが関係する。このテストが肯
定的ならば、区画キヤツシユ・デイレクトリの中
の有効記憶ビツトがデータ・タイプPLATの新し
いエントリに対応してオンにセツトされ、そうで
なければオフにセツトされる。その区画キヤツシ
ユ・ラインに対する後続の記憶リクエストは、
PLATにおいて該エントリが有効である間、単一
サイクル記憶として実行される。かかる記憶はロ
ーカル記憶リクエストとして区画キヤツシユへ転
送される。区画キヤツシユへの無効な発令は、関
連するPLATにも出されることに注意されたい。

第１２Ａ，１２Ｂ図には、区画キヤツシユがそ
の制御およびデータ・フローのパスとともに示さ
れている。デイレクトリ区画５００は、そのメモ
リ・ロケーシヨンのスタツクとともに示されてい
る単一キヤツシユ・アレイ区画５０２と関連して
いる。キヤツシユ・プライオリテイ・ゲート５０
４には、第４Ａ図にも示されるC2ローカル制御
バス５０６とC1グローバル制御バス入力５０８
が接続される。プライオリテイ論理５０４の出力
は、ORゲート５１０，５１２、そして読込ゲー
ト５１４、書出ゲート５１６へ供給される。アド
レス・バス・スイツチ５１８は、プライオリテイ
論理５０４から入力を受け取り、アドレスをキヤ
ツシユ・アレイ区画５０２へ向ける。ORゲート
５１０の出力は書出ゲート選択バス５２０へ送ら
れ、ORゲート５１２の出力は読込ゲート選択バ
ス５２２へ送られる。ORゲート５１０はデイレ
クトリ５００からの入力５６０を受け取り、OR
ゲート５１２はデイレクトリ５００からの入力５
５８を受け取る。

キヤツシユ・デイレクトリ５００は、アドレ
ス・バス・スイツチ５４２を通して入力アドレ
ス・バス６０Ｂと接続されている。アドレス・バ
ス・スイツチ５４２は、C1グローバル制御バス
５０８を入力とするプライオリテイ・ゲート５４
４によつて制御される。プライオリテイ・ゲート
５４４は、ゲート５４８へもその出力を送る。ゲ
ート５４８は、関連するPLATに接続されている
C3ローカル・バス５５０のための入力制御信号
を送る。キヤツシユ・デイレクトリ・アレイ５０
０の出力は、データ出力バス５５２、および論理
ユニツト５５４，５５６への入力によつて構成さ
れる。ユニツト５５４，５５６は、それぞれ有効
読込出力バス５５８、有効書出出力バス５６０へ
信号を送る。

キヤツシユ区画５０２の動作を説明すると、プ
ライオリテイ論理ユニツト５０４は、制御バス入
力５０６，５０８の信号を受け取る。C2制御入
力５０６に基づいてローカル・リクエストである
との判断がなされると、アドレス・スイツチ５１
８によつて、６個のアドレスのうちの１個がアド
レス・バスからキヤツシユ・アレイへスイツチさ
れる。読込動作の場合はバス選択制御ライン５３
０によつて、また書込動作の場合はバス選択ライ
ン５３２によつて、選択されたアドレスに対応す
るデータ・バスも選択される。読込ゲート選択ラ
イン５２２または書出ゲート選択ライン５２０の
活動も、ローカル読込および書出リクエストにつ
いてプライオリテイ論理によつて開始される。こ
のように、キヤツシユ・デイレクトリを使わない
で、キヤツシユ区画は単一サイクルのストアまた
はフエツチ動作を実行できる。フエツチ動作の場
合、第２のクロツク・サイクル・キヤツシユ動作
を用いて、リクエストされたデータを要求中央プ
ロセツサ・エレメントへ転送する。ストア動作の
場合、第２のキヤツシユ・サイクルは必要ない。

グローバル・リクエストであると判断される
と、デイレクトリ５００とキヤツシユ・アレイの
プライオリテイ論理５４４が、スイツチ５４２を
使つて共通アドレスを選択し、かつスイツチす
る。同様に、キヤツシユ・アレイは、前記のよう
にスイツチ５１８を使つて対応するアドレス・バ
スを選択する。しかし、この場合、読込ゲート制
御ライン５２２や書出ゲート制御ライン５２０を
アクテイブにすることはない。その代り、これら
のラインは、デイレクトリ５００の比較論理５５
６とテスト論理５５４によつてアクテイブにされ
る。グローバルの場合、有効読込ライン５５８に
よつて、選択されたデータ・バスへの選択された
読込ゲートの活動が開始される。有効書出ライン
５６０によつて選択された書出ゲートの活動が開
始されるので、キヤツシユ・アレイ５０２が続く
サイクルにおいてストア動作を実行し得る。この
ように、グローバル・リクエストの場合、キヤツ
シユ動作の第１サイクルでは、フエツチについて
はアレイ・アクセスとデータ・バス・スイツチが
行われ、ストア・リクエストについては記憶問合
せ機能が実行される。キヤツシユ動作の第２サイ
クル目では、フエツチの場合はリクエストされた
データが転送され、ストア・リクエストの場合は
キヤツシユ・アレイ５０２が循環（サイクル）さ
れる。グローバル・リクエストの場合、区画識別
子と有効ストア・ラインの生成はゲート５４８に
よつて可能となり、これらは新しいPLATエント
リを更新するためにC3バスで返される。

グローバル・リクエストのプライオリテイは、
他のどんなローカル・リクエストよりも高い。グ
ローバル・リクエストとローカル・リクエストの
両者についてのプライオリテイは、ポート・ポジ
シヨンの所定のシーケンスによつて決まる。

簡単のため、小さなPLATアレイが第１３図に
示されている。各エントリに第１０，１１図で説
明した内容を入れた状態で、８個のエントリを記
憶することができる。キヤツシユ・アレイの用語
を使うと、このアレイは８個の一致クラス・アド
レス・ポジシヨンを持ち、そして１組の連想性
（associativity）、セツトＡを持つ。このアレイ
は、（８×１）の次元を持つ。より大きなPLAT
は、第１３図のコンポーネントを複製することに
より構成することができる。水平方向に複数する
度に、８個のエントリが追加され、１セツトが追
加される。セツトＢの追加時には（８×２）とな
り、セツトＣの追加時は（８×３）になる。別の
方法では、垂直方向に複製する度に、８個のエン
トリが追加される。したがつて、一致クラス・ア
ドレスが８ずつ増えるものの連想性は単一セツ
ト、セツトＡのままである。このようなアレイの
次元は、（16×１）となる。例えば、エントリの
最適数が32であると決まれば、PLATアレイの配
列は、（８×４）、（16×２）、または（32×１）と
することができる。PLATの選ばれた配列が何で
あれ、必要な比較器（第１３図で言えば比較器６
３６）の数は、セツト連想性の数に等しい。つま
り、１セツトにつき１個である。

第１３図にさらに触れると、アドレス生成器６
００の出力は復号された組となつてアドレス・ラ
イン６０２を経てPLATへ渡されるが、復号され
るラインの数は一致クラスの数によつて決まる。
一致クラス選択ラインを復号するのに用いるアド
レス・ビツトは、区画L1キヤツシユのライン・
サイズで決まり、それは、第５図のL1デイレク
トリ・アドレス・バス６０Ｂをアドレスするのに
通常用いられるアドレスの最下位ビツト側の部分
である。一致クラス数が８であるPLATの場合、
下位３桁のビツトが８本の一致クラス選択ライン
の復号に使われる。一致クラス１６の場合は下位
４桁のビツトである。生成アドレスがAGEN加
算器から得られる場合、復号動作が必要になる符
号化された形ではなくて、復号された形である一
致クラス選択バス６０２を直接生成するようにし
てもよい。

第１３図と第５図を参照して、PLATの働きを
説明しよう。アドレス生成器６００は、リクエス
ト対象のアドレス６６４を生成し、そのビツトの
あるものを、キヤツシユ・アドレス・バス６０Ａ
を介してキヤツシユへ、デイレクトリ・アドレ
ス・バス６０Ｂを介してデイレクトリへ、そして
アドレス比較回路６３６へ送る。また、これと並
行して、アドレス生成器６００は、PLATに向け
て８ビツト一致ライン選択バス６０２にも出力す
る。要求アドレスが何であれ、バス６０２の８本
のラインのうちの１本だけがアクテイブである。
アクテイブなラインに応じて、PLATエントリ６
０４，６０６，６０８，６１０，６１２，６１
４，６１６または６１８から、８個のアドレスの
うちの１個だけが比較回路６３６へ至る共通バス
６６２にゲートされる。ゲート６２０，６２２，
６２４，６２６，６２８，６３０，６３２、また
は６３４は、アドレス・ゲーテイングを実行す
る。生成されたアドレス６６４と選択されたアド
レス６６２を比較した結果、両者が等しければ、
出力ライン６４０にポジテイブなヒツト信号が出
力される。次いで、ライン６４０の信号は、ゲー
ト６４２，６４４，６４６，６４８，６５０，６
５２，６５４、そして６５６へ送られて一致ライ
ン選択バス６０２と組み合わされ、PLATエント
リ６０４，６０６，６０８，６１０，６１２，６
１４，６１６、または６１８の区画Ｉ／Ｄフイー
ルドのうちの１つを共通バス６６０へ出力させ
る。バス６６０の信号は第４Ａ，４Ｂ，４Ｃ，４
Ｄ図の制御バス６４のローカル入力C2コンポー
ネントの１つとして、区画キヤツシユへ送られ
る。比較回路６３６での比較結果がイコールでな
いことを示す場合は、C1グローバル・リクエス
ト・バスにミス信号６３８が出される。信号６３
８は第４Ａ，４Ｂ，４Ｃ，４Ｄ図の制御バス６２
のグローバル入力C1コンポーネントの１つとし
て、区画キヤツシユおよびデイレクトリへ送られ
る。

第１４図のPLATは第１３図の変形例であり、
命令またはデータ・オペランド用のフエツチ・ポ
ートとして割り当てられるCPUポートにおいて
使用される。この例では、アドレス・フイールド
に加えて有効ビツトが、PLATエントリ６０４な
いし６１８から共通バス６６２へ、ゲート６２０
ないし６３４を経て出力される。比較回路６３６
によつて、前記のようなアドレス比較の実行に比
えて、有効ビツト入力ラインの吟味が行われる。
有効ビツトがイエス、つまり有効（キヤツシユの
取決めでは、普通、アツプ、つまり１の状態が無
効を示すのに使われ、ダウン、つまり０の状態が
有効に示すのに使われる）ならば、比較回路６３
６は、前記のようなアドレス比較動作に基づい
て、ヒツトを判別したらライン６４０へ出力し、
ミスを判別したらライン６３４へ出力する。有効
ビツトがノー（無効）ならば、ミス・ライン６３
８への出力が強制されて、アドレス比較動作は無
視される。

PLATで新しいエントリが作られるときはいつ
も、有効ビツトがイエス（ゼロ状態）にセツトさ
れる。しかし、通常のCPU処理事象に際し、
LRU論理によつてPLATからエントリをエージ
ングするのに先立つて、エントリを無効にセツト
することが必要になり得る。そのような事象の例
として、新たなキヤツシユ・ラインが区画L1キ
ヤツシユに取り入れられる場合がある。このと
き、PLATの中の古いラインを参照するどのエン
トリにも無効の印がつけられる。また、マルチ
CPU環境において、あるCPUが別のCPUに対し
てあるキヤツシユ・ラインを無効にするよう求め
ることは普通である。この場合、PLATの中のど
のエントリにも無効の印がつけられる。PLATエ
ントリを無効にする必要が生じる頻度はきわめて
少ないけれど、正確性と完全性を期す上で考慮さ
れる。

第１５図のPLATは第１３図の別の変形例であ
り、データ・オプランド用のストア・ポートとし
て割り当てられるCPUポートにおいて使用され
る。この例では、効ビツト(V)と有効ストア・ビツ
ト（Ｖ／Ｓ）の両方が、PLATエントリから比較
回路６３６へ向けてゲーテイングされる。この場
合、ライン６４０にヒツト状態、判別信号が出さ
れる前に、有効状態と有効ストア状態がともに存
在しなければならない。有効状態または有効記憶
（ストア）状態の一方が存在しないと、ここでも
ミス・ライン６３８への出力が強制されて、アド
レス比較は無視される。PLATミスのために新し
いエントリが作られるときはいつも、記憶問合せ
動作がL1デイレクトリにて行われる。このテス
ト結果がポジテイブならば、有効記憶状態が
PLATエントリに記録される。後続のストア・リ
クエストの結果ライン６４０にPLATヒツト信号
が送られ、かつデイレクトリ内で記憶問合せ動作
が必要とされない。

通常のキヤツシユ動作では、L1キヤツシユに
有効なリード・オンリー・データ・ラインを持つ
とともに、PLATの中に該ラインに対応する有効
エントリを持つことは珍しくない。L1キヤツシ
ユによつてラインの「リード・オンリー」リクエ
ストが行われていたならば、記憶問合せテストの
結果はネガテイブとなり、PLATの中の対応エン
トリにおいて無効記憶状態がセツトされよう。そ
して、該ラインに対する後続のストア・リクエス
トはPLATミスを招き、L1デイレクトリのグロ
ーバル・リクエストを引き起こすであろう。続い
てリード・オンリー状態が判別され、L1キヤツ
シユ制御により、第１図のSCEエレメントから記
憶特権（storage−privilege）状態がリクエスト
されるだろう。結局記憶特権が許されると、記憶
特権状態がL1デイレクトリに記録される。する
と、該ラインに対する後続のストア・リクエスト
において、記憶問合せテストの結果はポジテイブ
になり、PLATエントリにおいて有効ストアの標
識がセツトされる。

第１６図は、この区画キヤツシユの、特殊なフ
オールト・トレラントの特徴を示している。この
特徴によれば、システムの停止やコンピユータの
ユーザーに対するサービスの中断を避けつつ、キ
ヤツシユ・データ・アレイおよびデイレクトリの
コンポーネントの大きな故障を許容する。かかる
故障は、修理がなされるまでの間、キヤツシユ・
サブシステムのパフオーマンスの低下を招く。例
えば、デイレクトリ・エレメント全体が故障した
り（チツプ・キルと呼ばれる）、あるキヤツシユ
区画に関連する１以上のデータ・チツプが故障す
ることがある。こういつた場合、故障した区画は
キヤツシユ・サブシステムから論理的に外される
ので、８個の区画を持つキヤツシユにあつてはキ
ヤツシユ容量の12.5％のロスを招く。（キヤツシ
ユ容量の12.5％が失われても、サービスが12.5％
低下することにはつながらないことに注意された
い。容量の関数としてのキヤツシユ・パフオーマ
ンスの性質により、実質的にはより小さなパーセ
ントのサービス低下を招く。）修理に先立つてか
かる大きな故障が再び生じると、別の区画のロス
を招き、キヤツシユ容量は合わせて25％減少す
る。現在のキヤツシユ・サブシステムでは、上記
ケースにおいて、修理が完了するまで、CPUの
完全な機能は失われたままである。多くのユーザ
ーにとつて、クリテイカルな動作期間に際しての
パフオーマンスのわずかなロスは許容できても、
コンピユータの停止は重大な結果を招くので許容
できない。

フオールト・トレランスの基礎は、ある特定の
キヤツシユ・ラインに関連するキヤツシユ・デー
タが単一のキヤツシユ区画中に完全に含まれてお
り、かつそのアドレス制御情報が単一チツプ上に
あり得る単一デイレクトリ・エレメント内に完全
に含まれることである。そして、ストア・スルー
（store−through）L1キヤツシユも用いられる。
この結果、記憶階層の少なくとも１つ上のレベル
において、L1キヤツシユの全データの有効なコ
ピーが備えられる。したがつて、前記のような大
きな障害が起きると、ハードウエアが故障を検出
し、故障した区画を切り離すけれども、データは
全く失われない。実際、故障して切り離された区
画に常駐していたデータは、プロセツサの要請に
応じてL2からL1へ再フエツチされる。その際、
まだ機能している異なるキヤツシユ区画へ再フエ
ツチされる。要するに、故障した区画の中のデー
タは、CPUにとつて、L1ミスの際にフエツチし
なければならない非常駐キヤツシユ・データと全
く同じに見える。

第１６図には、フオールト・トレラント機構の
動作が示されている。キヤツシユ・トランザクシ
ヨンのすべてに際して、ハードウエア故障テスト
論理４０はアクテイブである。これには普通、例
えばアドレス、データおよび制御バス３６，３９
のパリテイ・チエツクが含まれる。無効区画表示
レジスタ７０２が備えられている。該レジスタは
８ビツトを記憶し、その各々が８個のキヤツシユ
区画の１つに対応している。大きな故障が生じた
場合、故障テスト・ハードウエア４０は、入力バ
ス７００を使つて、無効区画表示レジスタ７０２
の中の対応するビツトをオンにセツトする。ま
た、LRU論理・テーブル７０８も備えられてい
る。普通の事象では、LRU論理７０８はキヤツ
シユ・アドレス・バス６０Ａ、キヤツシユ制御バ
スＣ２（６４）、Ｃ２（６４）をモニターし、最
新のLRUアレイ７１２を維持する。C2制御バス
は、ローカル・キヤツシユ参照について、アクテ
イブな、アクセスされた区画番号を指示する。一
方、C3制御バスは、グローバル・キヤツシユ参
照について、アクテイブな、応答区画番号を指示
する。このアレイ７１２は、キヤツシユ３４とデ
イレクトリ３８の一致クラス毎に符号化されたエ
ントリを１つ記憶する。要するに、LRUアレイ
７１２の各エントリは、次回キヤツシユ・ミスが
生じた場合に新しいラインを記憶するのに使うこ
とになる区画のポインタ、あるいは区画番号を記
憶する。LRUアレイの中に現在のLRUエントリ
を維持するために、通常の区画LRUアルゴリズ
ムを使うこともできる。また、LRU論理７０８
は、バス７０４を使つて無効区画表示レジスタ７
０２の内容もモニターする。レジスタ７０２の何
れかのビツトがオンにセツトされると、該ビツト
は、LRU論理７０８に対するオーバーライドと
して作用し、無効区画はLRUアレイ７１２への
入力として選択されなくなる。むしろ、LRU７
０８が、レジスタ７０２の中の有効区画表示に基
づいて、アレイ７１２に対するLRUエントリを
選択する。L1キヤツシユ・ミスが生じるときは、
いつでも、要求するアドレスがバス７１４を経て
LRUアレイ７１２へ送られる。LRUアレイ７１
２は、要求アドレスの一致クラスに対応する区画
番号をバス７１６にロードする。これは、ライ
ン・フエツチ・バツフア１１０に送られ、区画番
号（PN）レジスタ７２０に記憶される。要求ア
ドレスはバツフア１１０へも送られ、アドレス・
レジスタ（AR）７２４に記憶される。新たなラ
イン・フエツチは、L2からバス１１２を経てバ
ツフア１１０へ送られ、バツフア７２６に記憶さ
れる。ライン・フエツチ動作に続いてライン・プ
ツト・アウエイ動作が行われる。ここでは、キヤ
ツシユ・リクエスト・アドレスＡ６がバス６０に
出力され、復号器７２２が区画識別をバス６４に
出力する。また、第２図および第１６図のスト
ア・バス・ポートＮに、ライン・データが供給さ
れる。

第１６図のハードウエアは、故障が修理される
まで、故障区画に将来新たなキヤツシユ・データ
が割り当てられることのないよう、これを切り離
す。修理動作（アクシヨン）の発生時間はユーザ
ーの都合に合わせて選択される。このとき、無効
区画指示レジスタ７０２の内容が有効状態へ戻さ
れる。また、故障発生検出時、あるハウスキーピ
ング・タスクが理解される。これらには、ライン
７１８で、LRUアレイのスキヤンの結果、無効
区画表示レジスタ７０２の新たな値に基づいて任
意の無効エントリをリセツトすることが含まれ
る。また、どの区画標識も故障区画を指さないよ
うに、そしてレジスタ７０２によつて決まるよう
にアドレス・バス６０Ａ，６０Ｂ上のアドレスが
故障区画へ向かわないように、全PLATアレイを
クリアすべきである。

本発明による区画キヤツシユとPLATの全体的
な付加的な動作の特徴をここで説明しておこう。

その１つは、大部分のストア動作が単一キヤツ
シユ・サイクルで完了することである。これは、
キヤツシユの各ローカル・ストア動作から記憶問
合せサイクルを除去することにより達成される。
記憶問合せ動作は、PLATミスが原因となるグロ
ーバル・ストアまたはフエツチ動作において１度
実行される。このとき、PLATの中に新しいエン
トリが生成され、有効または無効ストア・ビツト
が該エントリについてセツトされる。続くスト
ア・リクエストは、PLATの有効ストア・ビツト
がオンの場合、単一サイクルで実行される。スト
ア動作が単一サイクルで行われることによつて、
記憶命令に必要なサイクル数が減り、命令当りの
平均サイクル数が減るので、プロセツサの命令実
行速度が向上する。

ライン・プツト・アウエイ動作は、中央プロセ
ツサに対する区画キヤツシユの干渉を最小にして
達成される。ライン・フエツチ・バツフアからの
プツト・アウエイ区画キヤツシユ・ストア・サイ
クルは、（Ｍ個の）区画のうちの１つをビジーに
するだけであり、その区画がその他の点ではアイ
ドル状態であるサイクルについてのみ活動化され
る。このため、より大きなキヤツシユ・ラインを
都合よく利用することが可能になり、その結果、
ミス当りのキヤツシユ命令率が向上し、かつ
PLATヒツト率も高まる。

クリテイカルなキヤツシユ・アクセス・パス
は、すべての（Ｎ個の）並列動作ポートのすべて
について現在使用可能なチツプの２チツプ交差
（クロツシング）の中に含まれる。これは、Ｎ個
の同時に動作するポートのそれぞれが、１または
２アクセス・サイクルを持つことを意味する。ラ
イン・プツト・アウエイ動作を含むローカル・ス
トアは、ストア・ブロツク当り単一のサイクル・
アクセスで実行されるが、他の動作は２サイク
ル・アクセスになる。現在のシングル・ポート・
キヤツシユ構成の下では、ストアとフエツチの両
方ともに２サイクル・アクセスであり、１サイク
ル当り１動作に制限される。

高度のフオールト・トレラント構成により、区
画キヤツシユの可用性はさらに大きくなる。通常
のキヤツシユ構造では、パリテイ・チエツクは行
われるものの、エラー訂正は行われない。キヤツ
シユ・ラインまたはデイレクトリ・ビンに対して
単一ビツトのハード・エラーが生じた場合、修理
が行われるまでさらに使われないよう該キヤツシ
ユ・コンパートメントを切り離すべく、デイレク
トリの中に保持される削除ビツトがハードウエア
制御によつてセツトされ得る。従来のキヤツシユ
も区画キヤツシユも切り離される故障メカニズム
を使用する。しかし、キヤツシユ全体またはデイ
レクトリ・チツプが失われ、チツプ・キルが生じ
ると、従来型キヤツシユではシステム障害を招
く。区画キヤツシユは削除ビツトの概念を削除区
画へ展開した。したがつて、チツプ・キルの場
合、キヤツシユの１区画が失われるが、システム
障害は避けられる。

様々なデザインが可能であり、個々のキヤツシ
ユ・ポートやデータ・バスに関連して出力デー
タ・ブロツク・サイズが変化する。独立したL0
キヤツシユ構造を使用する中央プロセツサのデザ
インの用意を含めて、様々なベース・キヤツシ
ユ・デザインが可能である。

Ｅ 効果 本発明によれば、組連想式のＭ個の区画を持つ
キヤツシユ・メモリ・システムにおいて、最近リ
クエストされたデータが位置する区画を識別する
ためのテーブルを設け、所与のメモリ・リクエス
トに応じてまず該テーブルを検索し、選択すべき
区画が識別されたならば、該メモリ・リクエスト
をその識別された区画に導き、該テーブルによつ
ては区画を選択できなかつた場合に、上記所与の
リクエストを上記Ｍ個の区画全部へ導くようにし
たのであるから、区画を効率よく検索することが
可能になる。したがつて、本発明のキヤツシユ・
メモリ・システムを備えたコンピユータ・システ
ム全体のパフオーマンスが向上する。

【図面の簡単な説明】

第１図は、本発明による区画キヤツシユを備え
た、マルチCPUシステムの説明図である。第２
図は、本発明による区画キヤツシユ・メモリの具
体例の概略図である。第３図は、第２図に示され
た区画キヤツシユの、キヤツシユ・アレイ、デイ
レクトリ、そしてアドレス、データ、制御バスの
詳細な説明図である。第４Ａ，４Ｂ，４Ｃ，４Ｄ
図は、第２図に示される区画キヤツシユ・メモリ
に関連する制御バス構造体の詳細を、左から右へ
順を追つて示した説明図である。第５図は、第２
図に示されるような本発明によるキヤツシユ・メ
モリにおける、デイレクトリと区画構造の関係の
説明図である。第６図は、第５図に示されるアド
レス・バスからなるアドレス・ポートの１つの構
成を示す図である。第７図は、第２図に示される
実施例のキヤツシユ・メモリのフエツチ・ポート
の１つの詳細な説明図である。第８図は、第２図
の実施例のキヤツシユ・メモリのCPUストア・
ポートの詳細な説明図である。第９図は、第２図
に示されるキヤツシユ・メモリのPLATの構造の
詳細な説明図である。第１０図は、本発明による
命令タイプPLATにおけるデータ・フイールドの
構造の概略的な説明図である。第１１図は、本発
明によるデータ・タイプPLATにおけるデータ・
フイールドの構造の概略的な説明図である。第１
２Ａ図および第１２Ｂ図は、本発明によるある区
画キヤツシユ・デイレクトリと区画キヤツシユ・
データ・アレイ、および単独のキヤツシユ区画に
関する動作を、左から右へ順を追つて示した説明
図である。第１３図ないし第１５図は、それぞ
れ、本発明による区画キヤツシユ・メモリのアド
レス構造の異なる具体例を詳細に示した図であ
る。第１６図は、本発明による、故障区画を識別
してシヤツト・オフするフオールト・トレラント
構造の詳細な説明図である。

Claims (1)

1. 【特許請求の範囲】 １ 単一メモリ複合体の中の、互いに独立してア
   ドレツシングすることのできる、組連想式メモリ
   のＭ（Ｍは２以上の自然数）個の区画と、 上記Ｍ個の区画にアドレスを渡すＮ（ＮはＭ以
   下の自然数）本のアドレス・バスの各々の一端に
   一つずつ位置する合計Ｎ個のアドレス・ポートと
   上記Ｍ個の区画との間のスイツチングを行うアド
   レス・バス・スイツチ手段と、 上記Ｍ個の区画に関してデータを入出力するＮ
   本のデータ・バスの各々の一端に一つずつ位置す
   る合計Ｎ個のデータ・ポートと上記Ｍ個の区画と
   の間のスイツチングを行うデータ・バス・スイツ
   チ手段と、 最近リクエストされたデータが位置する区画を
   識別するためのテーブルを備え、所与のメモリ・
   リクエストに応じて該テーブルを検索し、該所与
   のメモリ・リクエストに対して選択すべき区画が
   識別されたならば、上記アドレス・バス・スイツ
   チ手段を制御して該メモリ・リクエストを該選択
   された区画へスイツチするとともに、上記デー
   タ・バス・スイツチ手段を制御して該選択された
   区画に関する入出力を選択されたデータ・バスへ
   スイツチし、 上記所与のメモリ・リクエストに応じて選択す
   べき区画が識別されなかつたならば、上記アドレ
   ス・バス・スイツチ手段を制御して該メモリ・リ
   クエストを上記Ｍ個の区画全部へ導く制御手段 を含むキヤツシユ・メモリ・システム。