JPH06100979B2 - 物理アドレス及び仮想アドレスによりアドレス指定可能なキヤツシユ・メモリ - Google Patents

Description

【発明の詳細な説明】 （発明の技術分野） 本発明は全般としてキヤツシユ・メモリに関し、特に仮
想アドレス及び物理アドレスによるキヤツシユ・メモリ
のアドレス指定方法に関するものである。

（発明の背景） キヤツシユ・メモリは、最近のコンピユータ装置におい
て主メモリが支援可能とする大容量によりかなり高速度
で装置を動作できるように利用されて来た。このキヤツ
シユ・メモリは中央処理装置により容易にアクセスされ
る限定的なある数の命令又はデータを記憶する。メモリ
からデータ又は命令を読出す際は、キヤツシユ・メモリ
をまず調べ、情報がそこから得られるかの判断をする。
情報が得られるときはキヤツシユ・メモリの読出しを実
行し、否のときは主メモリから読出しを実行する、情報
を主メモリから読出さなければならないときは、キヤツ
シユ・メモリに既に存在する情報に代つてこの新しいデ
ータを記憶させる。置換すべきキヤツシユ・メモリのデ
ータを判断するために、キヤツシユ・メモリに記憶した
どのデータ又は命令が最新にアクセスされたか、即ち
「最低使用頻度（LRU）」であるかを判断する。このよ
うにして、最も一般的に用いられるデータ又は命令をキ
ヤツシユ・メモリから統計的に得ることにより、与えら
れた装置の実行速度を増加することができる。

LRU装置を初期化設定するときには、与えられたキヤツ
シユ・メモリにおける種々のレジスタ間の優先順位を決
定する必要がある。これを達成するために従来用いられ
ていた種々の方法、例えばシー・イエー・チヤンに発行
され、ATTベル研究所に譲渡された米国特許第4,458,310
号に開示された方法がある。本質的には、種々のレジス
タの優先順位に対応する情報を記憶するために付加的な
メモリを用いることが必要である。これはポインタ等に
より容易に達成される。しかし、LRU装置の実現には困
難があり、多くの回路と時間の掛かる処理技術となるこ
とが明らかにされている。

キヤツシユの与えられたメモリ位置の優先順位を決定す
ることに加えて、キヤツシユ・メモリのアドレス指定も
多重キヤツシユを有する多重プロセツサ装置に用いる
と、問題が発生する。このような形式の装置において
は、主メモリ及びキヤツシユは物理アドレス指定媒体に
おいて動作し、一方多重プロセツサは仮想アドレス指定
媒体において動作する。従つて、プロセツサはその関連
のキヤツシユをアクセスするために仮想アドレスから物
理アドレスに変換する必要がある。これには、このよう
な変換の実行に所定量の処理時間が必要であり、これに
より処理速度を低下させるという欠点がある。従つて、
仮想アドレス及び物理アドレスのうちのいずれかの型式
をキヤツシユ・メモリに直接用いることができるように
仮想アドレス及び物理アドレスの両方を識別するキヤツ
シユ・メモリを備えることにより、仮想アドレスから物
理アドレスへの変換時間をなくすことが望ましいことに
なる。

キヤツシユ・メモリの製造においては、キヤツシユ・メ
モリを処理装置に備えるときに誤りが導入されないよう
にアクセス可能な全てのメモリ位置が動作可能であるこ
とが必要である。Ｎ通りの連想セツトにおいて一欠陥位
置を許容したとしても、これにデータを書込んだり、こ
れからデータを読出さないようにこの欠陥位置を不活性
にすることがまず必要である。従来は装置の電源投入時
においてどのデータ・レジスタに欠陥があるのかを判断
し、この情報をメモリに記憶することにより、解決を図
つていた。更に、キヤツシユ・メモリの不良部分に対す
るアクセスを禁止するために回路が用いられる。この型
式の装置は、1983年６月13日〜16日、第10回コンピユー
タ・アーキテクチヤ国際シンポジウムにおいてパターソ
ンほかによる「RISC用VLSI命令キヤツシユのアーキテキ
チヤ」に説明されている。しかし、これには複雑な回路
が必要であり、かつ装置を起動させる前に装置を走査す
る必要がある。

このような欠点から見ると、信頼性があり、かつ能率的
な方法にて物理アドレス又は仮想アドレスによりキヤツ
シユと直接通信すると共に、与えられたキヤツシユにお
けるどのデータ・レジスタが最新アクセス・データであ
るのかの判断を装置に行なわせるアーキテクチヤの必要
性が存在する。

（発明の要約） 開示し、かつ特許請求の範囲とする本発明は、仮想アド
レス及び物理アドレスの両者によりアドレス指定可能な
キヤツシユ・メモリを備えている。キヤツシユ・メモリ
にあるデータをアドレス指定するアドレスはLSB部及び
タグ部に分割され、このLSB部は所定数の最下位ビツト
からなり、またMSB部はその残り即ち最上位ビツトから
なる。仮想及び物理アドレスのLSB部はアドレス指定し
た全てのデータに共通である。選択データを記憶するた
めのキヤツシユ・データ・メモリが備えられているが、
この選択データはこのメモリに関連する仮想アドレス及
び物理アドレスを有するものである。このキヤツシユ・
データ・メモリは受取つたアドレスのLSB部によりアド
レス指定可能であり、そのアドレス位置に記憶している
アドレス指定データを出力する。仮想タグ・メモリ及び
物理タグ・メモリからなるタグ・メモリも備えられてい
る。この仮想タグ・メモリはキヤツシユ・データ・メモ
リに記憶しているデータに関連する仮想アドレスのタグ
部を記憶し、物理タグ・メモリはキヤツシユ・データ・
メモリに記憶しているデータに関連する物理アドレスを
記憶する。この仮想及び物理タグ・メモリは受取つたア
ドレスのLSBによりアドレス指定可能である。受取つた
アドレスが仮想アドレスか物理アドレスかを判断し、こ
の判断に対応して制御信号を発生する仲裁装置が備えら
れている。マルチプレクサが仮想及び物理タグ・メモリ
の出力に接続され、仲裁装置により制御され、前記タグ
・メモリの対応する一つを選択し、仮想又は物理タグ部
のいずれかを出力する。比較器は選択した仮想又は物理
アドレスのタグ部を受取つたタグ部と比較して一致する
かの判断をする。一致があるときは、出力スイツチを制
御してキヤツシユ・データ・メモリからアドレス指定さ
れたデータを出力させる。

本発明の他の実施例において、キヤツシユ・データ・メ
モリに記憶されている更新データに関連したアドレスの
仮想及び物理タグ部は、仮想及び物理タグ・メモリに選
択的に記憶される。マルチプレクサ回路は双方向性であ
り、仲裁装置に入力されている更新データの仮想又は物
理アドレスのいずれかに応答して、仮想及び物理タグ部
の両方を発生する。次に、仲裁装置はマルチプレクサを
制御してそれぞれ仮想及び物理タグ・メモリにある適応
な位置に物理及び仮想タグ部の両者を記憶させる。

本発明及びその効果を更に詳細に理解するため、付図と
関連させて次の説明をここで参照する。

（実施例の詳細な説明） 第１図を参照すると、キヤツシユに関連された複数のマ
イクロプロセツサを用いているコンピユータ装置のブロ
ツク図が示されている。このコンピユータ装置はNUバス
と呼ぶ型式のバス10を介して通信をする。バス10は32ビ
ツトの物理アドレスを転送する32ビツトのバスである。
しかし、あらゆる型式のシステム・バスを用いることが
できる。メモリ12はバス14を介してバス10に接続され、
メモリ16は接続バス18を介してバス10にも接続される。
メモリ12〜16間における一連の点線により複数の付加的
なメモリを示している。各メモリ12〜16は、そのアクセ
スをするための物理アドレスを必要とする大容量メモリ
のあらゆる形式のものでよい。

キヤツシユ・メモリ20はデータ・バス24を介してバス・
インタフエース22に接続されている。バス・インタフエ
ース22は接続バス26を介してバス10に接続されている。
キヤツシユ・メモリ20は接続バス30を介してプロセツサ
28にも接続されている。接続バス24上を転送されるアド
レスは物理アドレスであり、一方接続バス30上を転送さ
れるアドレスは仮想アドレスであり、プロセツサ28は仮
想アドレスのみによりインタフエース接続をする。

仮想実アドレス変換器（V/R変換器）32は接続バス34を
介して接続バス24にその実入力を接続し、接続バス36を
介して接続バス30にその仮想入力を接続している。V/R
変換器32はプロセツサ28がバス・インターフエイス22を
介してバス10と通信できるようにしている。

動作において、プロセツサ28から出力された仮想アドレ
スはキヤツシユ・メモリ20により直接処理され、これに
データが記憶されているかの判断をするために比較され
る。キヤツシユ・メモリ20がバス10によりアドレス指定
されると、物理アドレスが接続バス24を介してキヤツシ
ユ・メモリ20に入力され、データがキヤツシユ・メモリ
20に記憶されているかについての判断をする。従つて、
プロセツサ28からキヤツシユ・メモリ20をアドレス指定
する前に、仮想アドレスから物理アドレスへの変換を行
なう必要はない。これは、キヤツシユ・メモリ20が通常
主メモリをアドレス指定する前に指定されるので、処理
時間を低減させるものである。

V/R変換器32はメモリ・キヤツシユ20をアドレス指定す
る必要はないが、プロセツサ28が物理アドレスをバス10
に直接転送できるようにすることは必要なことに変りは
ない。この転送は、キヤツシユ・アドレス20がアドレス
指定されないとき、例えば他の周辺処理をプロセツサ28
が実行しているときに利用される。

第２のキヤツシユ・メモリ38は接続バス42を介してバス
・インタフエース40に接続されており、接続バス44を介
してバス10にインフエース接続される。キヤツシユ・メ
モリ38は接続バス48を介してプロセツサ46により相互接
続もされる。プロセツサ46はプロセツサ28と同じような
ものである。V/R変換器50は接続バス52を介して接続バ
ス48にその仮想入力を接続し、接続バス54を介して接続
バス42にその実出力に接続し、これに物理アドレスを転
送する。V/R変換器50はV/R変換器32と同じものであり、
これらは通常の回路を用いて変換を実行する。

第１図の装置は任意数の主メモリ及びキヤツシユと関連
されるプロセツサを備えることができる。この規模の装
置が動作するときは、キヤツシユ・メモリ20及び38は統
計的な見地から最も頻繁に用いられるデータを記憶す
る。従つて、メモリ12又は16からデータがアクセスされ
ると、後の利用のために各自のキヤツシユに記憶され
る。その後、バスに送出されてデータ及び／又は命令を
読出すアドレスがまず関連のキヤツシユ・メモリに入力
され、そこにデータが記憶されているかの判断を行な
う。否となつたときは、データが主メモリから読出さ
れ、アドレスを生成したプロセツサにより用いられ、こ
のデータは関連のキヤツシユ・メモリにも記憶される。
このデータを記憶する際に、キヤツシユ・メモリにおけ
るLRUデータ・レジスタは書き替えられる。

データが読出されると、データが相手側のキヤツシユ・
メモリ及び主メモリの両者に存在し得るという問題が発
生する。従つて、正しいデータをアクセスしているとい
うことを確認する何らかのアルゴリズムを用いなければ
ならない。これには通常その装置における全てのキヤツ
シユ内容を調べることが含まれる。例えば、プロセツサ
28がバス10からデータを読出したときは、読出したデー
タがキヤツシユ・メモリ38に記憶されているかの判断が
必要である。これにはキヤツシユ・メモリ20及び38が物
理アドレスに応答して装置データの保全性を確認するこ
とが必要となる。しかし、キヤツシユ・メモリ20及び38
は、仮想アドレス指定を用いる関連プロセツサ28又は46
のうちの一つによつても直接アドレス指定される。装置
のパフオーマンスを高めるために、V/R変換器を用いる
ことなく、仮想又は物理アドレスのいずれかと直接イン
タフエース接続をするキヤツシユ・メモリが利用され
る。

第２図をここで参照すると、仮想及び物理アドレスの概
要構成と、これらのアドレスにより直接アドレス指定さ
れるキヤツシユ・アドレス装置のフオーマツトが示され
ている。仮想アドレスは所定パターンに従つてフイール
ドに配列されている任意数のビツトであればよい。更
に、物理アドレスもある所定の順序に配列することがで
きる。このデータを複数単位のメモリである「ページ」
に配列する。これにより、メモリにおける種々の位置を
メモリの他の位置にマツピングすることができる。この
アドレスの最初の８ビツトは仮想メモリ及び物理メモリ
におけるページ内の位置を指定する。共通の構成を用い
ることにより、両者を互に直接マツピングさせることが
できる。例えば、８ビツトはメモリの一ページ当り256
ワードとなる。しかし、他の大きさのページを用いても
よいことを理解すべきである。ページの長さを指定する
８ビツトはアドレスの最下位ビツト「LSB」である。最
上位ビツト（MSB）はアドレスの残部を形成している。
仮想メモリの容量は大きくすることができるが、ある装
置では仮想アドレスが比較的小さいために、仮想及び物
理アドレスのMSBの長さが同一である必要はない。ペー
ジ数はアドレスのMSB複数ビツトにより決定される。

通常のキヤツシユ・メモリでは、アドレスが８ビツトの
LSBフイールドと、残りのMSBビツトとに分割される。８
ビツトのLSBフイールドは３ビツトのフイールド56と、
５ビツトのフイールド58に分割される。両フイールド56
及び58はキヤツシユ・メモリのブロツクを指定するもの
で、各ブロツクが所定数のメモリ位置に分割される。５
ビツトのフイールド58はキヤツシユ・メモリ内のブロツ
クに対応しており、32個のブロツクを指定する。一方、
３ビツトのフイールド56は与えられたブロツク内の各レ
ジスタに対応しており、各ブロツク内の８メモリ位置を
指定する。与えられたブロツクにおけるこれらの各位置
はデータ記憶用のものである。

キヤツシユ・アドレスにおいて、MSB部は２型式に分類
され、第１の型式60は仮想タグと定義され、第２の型式
62は物理タグと定義される。各型式60及び62はキヤツシ
ユ・アドレスの同一部分を占有する。即ち、キヤツシユ
・アドレスのMSBは仮想又は物理アドレス装置から受取
つたものである。第３図を参照して以下で説明している
が、キヤツシユ・メモリのデータ部に存在するキヤツシ
ユ・アドレスのMSBは32個のメモリ位置に分割されてい
るタグ・メモリに記憶される。

ここで第３図を参照すると、第１図のキヤツシユ・メモ
リ20及び38の概要ブロツク図が示されている。各キヤツ
シユ・メモリはデータ・メモリ64及びタグ・メモリ66に
分割されている。データ・メモリ64は「０」〜「31」よ
り表わした32ブロツクに分割されている。各ブロツクは
「０」〜「７」により表わした８個のメモリ位置に分割
されている。従つて、データ・メモリ64は256ワードを
有し、メモリの最大１ページを記憶する。しかし、デー
タ・メモリ64に記憶されるデータは、明確にメモリの１
ページに対応させる必要はないが、データ・メモリ64に
おける各ブロツクを任意のメモリ・ページの８ワード・
ブロツクに対応させることができる。データ・メモリ64
内の位置は8LSBビツトにのみ依存する。以下で説明して
いるように、タグ・メモリ66に記憶されているMSBビツ
トはデータ・メモリ64の１データ・ワードにのみ対応す
る。しかし、これに関連した全てのデータは３ビツトの
セグメント56により指定されるデータ・メモリ64の同一
ブロツクに記憶される。

タグ・メモリ66は２個のメモリ、即ち仮想タグ・メモリ
68及び物理タグ・メモリ70に分割される。仮想タグ・メ
モリ68及び物理タグ・メモリ70は「０」〜「31」により
表わす32メモリ位置を有する。このメモリ幅は仮想タグ
部60又は物理タグ部62のいずれかにおけるMSB幅に等し
い。例えば、物理アドレスは32ビツト長であり、MSBビ
ツトは24ビツト長であるので、物理タグ・メモリ70は24
ビツト幅となる。一方、仮想タグ・メモリ68はそのMSB
の長さに従つて、別の長さとすることができる。

タグ・メモリ66に記憶されている各MSBは与えられた仮
想アドレス又は物理アドレスのMSBビツトに対応する。
また、このメモリ位置は、データ・メモリ64の１ブロツ
クに対応した５ビツトのフイールド58に依存している。
従つて、５ビツトのフイールド58により、データに対応
したデータ・メモリのどのブロツクが記憶され、またタ
グ・メモリ66のどの位置にタグのMSBが記憶されている
かが判断される。また、アドレスの３ビツトのフイール
ド56により、そのアドレスに対応する与えられたブロツ
ク・データのどの８ビツト位置に記憶されているのかが
判断される。

データ・メモリ64及びタグ・メモリ66をアドレス指定す
るときは、キヤツシユ・アドレスのLSBビツトがそのキ
ヤツシユ・アドレスから読出され、かつLSBアドレス・
バス72上に送出される。キヤツシユ・アドレスの５ビツ
トのフイールド58はLSBアドレス・バス72から読出さ
れ、５ビツトのバス74上に送出される。バス74は仮想タ
グ・メモリ68及び物理タグ・メモリ70の両者に分岐して
入力されており、アドレスを供給する、仮想タグ・メモ
リ68の出力はバス76を介してスイツチ78に入力され、ま
た物理タグ・メモリ70はバス80を介してスイツチ78の残
りの入力に供給される。スイツチ78は２つのメモリ68及
び70の出力間で選択をする。

データ・メモリ64はキヤツシユ・アドレスのフイールド
56及び58を形成し、LSBアドレス・バス72から読出され
る8LSBビツトによりアドレス指定される。LSBアドレス
の場合は、データ・メモリ64の256位置から１位置が選
択され、スイツチ84に入力するように出力される。スイ
ツチ84は通常開放型のスイツチであり、その出力をバス
86に接続し、装置の残りの部分に供給している。

スイツチ78は仲裁装置88により制御されており、仲裁装
置88は制御線90上に制御信号を出力してスイツチ78の制
御入力に入力させる。仲裁装置88は２入力を有し、その
一方はバス94を介して仮想アドレス機構92に接続され、
他方はバス98を介して物理アドレス機構96に接続されて
いる。仲裁装置88は仮想アドレスと物理アドレスとの間
を識別し、タグ・メモリ68又は70のいずれを選択すべき
かの選択をする機能がある。

スイツチ78の出力はバス102を介して比較回路100に供給
される。比較回路100の他方の入力はMSB104に接続され
ており、MSBバス104は第２図で型式60及び62により示す
ように、仮想アドレス又は物理アドレスのいずれかに対
してキヤツシユ・アドレスのMSBを転送する、アドレス
・バス104は仲裁装置88の出力に接続されている。アド
レス・バス104は接続バス102にも接続されており、スイ
ツチ78にアドレス・データを入力させている。比較回路
100は仮想アドレス機構92又は物理アドレス機構96から
供給されたアドレスのMSBとタグ・メモリ66に記憶され
ているMSBとの間で比較をする。この比較が真となつた
ときは、制御信号が制御線106上に出力されてスイツチ8
4を制御し、データ・バス82のデータをバス86に出力さ
せる。例えば、仮想アドレスが仲裁装置88に入力される
と、スイツチ78は出力バス76を選択する。５ビツトのフ
イールド58が論理“4"に対応するアドレスの場合は、
「４」により示すメモリ位置を仮想タグ・メモリ68から
選択してバス102に出力する。これと同時に、データ・
メモリ64はアドレスの8LSBビツトを受取り、256データ
・ワードのうちの一つをデータ・バス82に出力する。仮
想タグ・メモリ68の位置「４」に記憶されているアドレ
スMSBが仮想アドレス機構92から供給されるMSBビツトに
対応するときは、比較回路100は線106に制御信号を出力
してデータ・バス82上のデータをデータ・バス86に導
き、装置の残りの部分に転送する。しかし、一致が検出
されなかつたときは、「ミス」が装置の他の部分で表示
され、データが主メモリから読出されてアドレス装置に
より用いられる。更に、このアドレスのMSBビツトがメ
モリ66に書込まれ、これに関連するデータがデータ・メ
モリ64に書込まれる。しかし、Ｎ通りの連想セツトに構
成されているキヤツシユは、以下で説明しているよう
に、メモリ位置を判断するためにある種の優先順位イン
ジケータを必要とする。タグ・メモリ68及び70にデータ
を書込むためには、MSBデータをバス102に送出し、スイ
ツチ78が仲裁装置88に応答して仮想タグ・メモリ68及び
物理タグ・メモリ70から選択な方を選択する。仲裁装置
88はスイツチ78を介して対応する仮想タグ・メモリ68又
は物理タグ・メモリ70に仮想アドレスのMSB部分及び物
理アドレスのMSB部分の両者を書込む機能がある。

第４図をここで参照すると、LRUデータ位置を判断する
回路に関連させて４通りの連想キヤツシユ・メモリのブ
ロツク図が示されている。簡単にするため、以上で説明
した仮想アドレスと、物理アドレスとの間を識別する回
路は含まれていない。このデータ・メモリは４つのデー
タ・メモリ108、110及び114からなり、またこのタグ・
メモリは４つのタグ・メモリ116、118、120及び122から
なる。各データ・メモリ108〜114はタグ・メモリ116〜1
22の一つと関連され、これらはそれぞれ「１」、
「２」、「３」及び「４」の数字が付けられている。

キヤツシユ・メモリのアドレスはアドレス・バス124を
介して転送され、データはデータ・バス126を介して転
送される。データ・バス126はライン・ドライバ125を介
してデータ・メモリ108に接続されてそのデータを読出
し、またライン・ドライバ128を介してデータ・メモリ1
08に接続されてそのデータを受取る。同様にして、ライ
ン・ドライバ130、132及び134を介してデータ・バス126
からデータ・メモリ110、112及び114へそれぞれデータ
を読込む。ライン・ドライバ136、138及び140を介して
メモリ110、112及び114からそれぞれデータ・バス126に
データを読出す。前述のように、データ・バス108〜114
のアドレスはLSBデータ・バス142を介してアドレス入力
に入力されるアドレス・バス124の8LSBビツトからな
る。キヤツシユ・メモリで用いられるデータは通常の方
法でメモリ108〜114に書込まれ、かつこれから読出され
る。

タグ・メモリ116、118、120及び122はそれぞれ比較器14
4、146、148及び150と関連される。各比較器144〜150は
２入力を有し、その一方はタグ・メモリ116〜120の関連
する一つに接続され、その他方はアドレス・バス124の
アドレスのMSBビツトに接続されている。比較器144はデ
ータ・バス152を介してタグ・メモリ116に接続され、ま
たMSBデータ・バス154を介してアドレス・バス124に接
続されている。同様にして、比較器146、148及び150は
関連するデータ・バス156、158及び160を介してそれぞ
れ関連するタグ・メモリ118、120及び122に接続されて
いる。比較器146、148及び150の他の入力はそれぞれMSB
データ・バス162、164及び166に接続されている。タグ
・メモリ116〜122はその入力をLSBデータ・バス168に接
続され、LSBデータ・バス168はキヤツシユ・アドレスの
８ビツトのLSB部のうちの最上位８ビツトに接続されて
いる。図示していないが、MSBデータ・バス154、162、1
64及び166は各バツフアを介してタグ・メモリ116〜122
のデータ・入力に接続され、データがタグ・メモリ116
〜122に書込むことができるようにしている。

比較器144〜150の入力は４入力NORゲート170の各入力に
接続されている。更に、各比較器144〜150の出力はそれ
ぞれライン・ドライバ128、136、138及び140の制御入力
に接続されており、データ・メモリ108〜114からデータ
を読出せるようにしている。NORゲート170の出力はキヤ
ツシユ・メモリのデータに関して「ヒツト」であつた
が、又は「ミス」であつたかの判断である。「ヒツト」
とはデータがキヤツシユ・メモリキヤツシユ・メモリか
らアクセスされたことを示し、「ミス」とはデータがキ
ヤツシユ・メモリに記憶されておらず、主メモリからア
クセスされなければならないことを示す。主メモリから
のデータの読出しには通常技術が用いられる。しかし、
データが読出されたときは、そのデータはデータ・メモ
リのLRUメモリ・ブロツクに記憶されなければならな
い。前述のように、アドレスにおける最下位ビツトに対
応した８ワードのブロツクでデータが読出される。

メモリのLRUブロツクを決定するため、比較回路144〜15
0の出力は線174を介してLRUコントローラ172に入力され
る。LRUコントローラ172は双方向データ・バス178を介
してLRUメモリ176によりインタフエース接続されてい
る。従つて、LRUメモリ176はLSBデータ・バス180を介し
てアドレス・バス124からアドレスを受取る。このアド
レスには８ビツトのLSBの最上位の５ビツトが含まれて
いる。

データ・メモリ108〜114に記憶されていないデータがア
ドレス指定されたときは、主メモリからアクセスされ、
かつ「キヤツシユ」されなければならない。データをキ
ヤツシユする際は,LRUコントローラ172はまずLRUメモリ
176を調べ、データ・メモリ108〜114のいずれがアドレ
スの与えられた８ビツトのLSB部分として最新に利用さ
れたのかを判断する。これが判断されると、線182を介
して信号がデータ・メモリ108〜114及びタグ・メモリ11
6〜122に出力される。書込み／エネーブルはWEにより表
わされている。キヤツシユ・メモリと関連され、与えら
れたデータ・メモリ及びタグ・メモリにデータを書込む
ための回路は通常の回路である。

LRUメモリ176からデータを受取り、いずれのキヤツシユ
・メモリが最新に利用されたかを判断することに加え
て、LRUコントローラ172も各キヤツシユのアクセスのた
めにLRUメモリ176を更新する。しかし、これは関連のキ
ヤツシユ・メモリ内の各メモリ位置が有効であり、従つ
てこれからデータを読出し、またこれにデータを書込む
ことを前提としている。メモリ位置の一つが不良のとき
は、記憶データをアクセスしないか、又が誤りデータを
アクセスするかの誤りが発生する。不良の存在がＮ通り
の連想キヤツシユ・メモリにとつて不都合とならなくて
もいずれのメモリ位置が不良であり、このメモリ位置に
データを書込むこと又はこれよりデータを読出すのを阻
止する判断が必要である。これは、本発明の場合、LSB
データ・バス186を介してアドレス・バス124にアドレス
入力を接続して８ビツトのLSBフイールドの最上位５ビ
ツトを受取ると共に、データ・バス188を介してLRUコン
トローラ172に出力を接続している不良メモリ184によ
り、達成される。不良メモリ184にはキヤツシユ・メモ
リの各メモリ位置の不良ステータスを表示するデータが
含まれているので、LRU172はLRUキヤツシユ位置として
このメモリ位置を指定するのが禁止される。更に、不良
メモリ184の出力は各比較回路144〜150に入力されてお
り、その１ビットが比較器の出力を禁止するように接続
されている。不良位置をアクセスしたときは、不良メモ
リ184に記憶されているデータは「ヒツト」を登録する
のを禁止する。

好ましい実施例においては、不良メモリ184はキヤツシ
ユ・メモリ内の全てのメモリ位置の不良ステータスを永
久記録するように工場にてプログラムされている。従っ
て、LRUコントローラ172の援用により、以下で説明され
ているように、Ｎ通り連想キヤツシユ・メモリに対して
不適当な処理を実行することなく、それにデータをキヤ
ツシユするのを制御することが可能である。

第３図及び第４図を参照して、この装置の動作を詳細に
説明しよう。まず、複数のプロセツサ又はアドレス装置
のうちの１つが仮想アドレス又は物理アドレスのいずれ
かを仲裁装置に、またアドレス・バス124に送出する。
次に、アドレスのLSBはタグ・メモリ116〜122に入力さ
れ、これに記憶されていた適当なMSBが比較回路144〜15
0に出力される。第３図のスイツチ78は、比較回路144〜
150に出力されるのは仮想タグか物理タグかを判断す
る。比較回路144〜150が第３図の比較回路100と同一で
あることは理解されるべきである。

選択したタグ位置からMSBビツトを出力すると同時に、
データ・メモリ108〜114のデータもアドレス指定され、
このデータが出力される。比較回路144〜150のいずれか
において比較が真となつたときは、トランシーバ128、1
36又は140の適当な一つが比較回路144、146、148及び15
0の一つにより付勢され、データがデータ・バス126上に
出力される。更に、NORゲート170の出力は論理「ロー」
にされて「ヒツト」を登録する。

与えられた８ビツトのLSBフイールドに対応するMSBがタ
グ・メモリ116〜122に検出できなかつたときは、NORゲ
ート170の出力は「ミス」を表わす論理「ハイ」とな
る。次に、この装置は主メモリをアクセスしてそのアド
レス位置に存在する所望データを得る。更に、このデー
タはキヤツシユ・メモリにおける適当な位置に書込まな
ければならない。前述のように、各データ・ワードが１
ブロツクのデータに関連されているので、キヤツシユ・
アドレスの５ビツトのフイールド58により指定されてい
るブロツクがアドレス指定されたワードと共に読出され
て記憶される。例えば、５ビツトのフイールド58がブロ
ツク「31」に論理的に等しく、かつ３ビツトのフイール
ド56がブロツク「31」の第４セグメントに論理的に等し
いときは、同一のMSB及び同一の５ビツトのフイールド5
8を有する全データがブロツク「31」に記録される。即
ち、第４セグメントのデータ・ワードを囲む全データ・
ワードはブロツク「31」に記憶される。更に、そのアド
レスに関連するMSBフイールドは関連のタグ・メモリに
記録される。データ・メモリ108〜114及びタグ・メモリ
116〜122にこのデータ及び関連のタグを書込む処理は通
常のものである。更に、現存するキヤツシユ・データ上
に書込みをする前に、主メモリにある関連のデータを調
べ、更新をすべきかについて判断をする。

データ・メモリ108〜114にデータを書込む前に、どのデ
ータ・メモリがLRUデータを有するのかについての判断
をしなければならない。これは、LRUメモリ176及びLRU
コントローラ172を用いることにより得られる。データ
が書込まれた後、LRUメモリ176が更新され、次のアドレ
スをキヤツシユ・メモリに供給することができる。

第５図を参照すると、LRUコントローラ172の概要ブロツ
ク図が示されており、これはツリー構造にて作成される
と共に、ツリーの分岐がそれぞれ別個のタグ・メモリ及
び関連の比較回路に接続されている。両図において、同
一符号は同一部分を示している。連想セツトにおいて２
つのキヤツシユ・メモリはコントロール回路190により
インタフエース接続されており、残りの２つのキヤツシ
ユ・メモリはコントロール回路192に接続されている。
２つのコントロール回路190及び192は上位のコントロー
ル回路194によりインタフエース接続されている。この
型式の構造はＮ通りの連想セツトにあるキヤツシユ・メ
モリの数に従つて多重レベルを有する階級構造である。
例えば、連想セツトにおいて８個のキヤツシユ・メモリ
があつたときは、４レベルのコントロール回路が用いら
れ、２つの中間コントロール回路が用いられ、かつ１つ
の上位レベル回路が用いられることになり、総計７回路
となる。従つて、Ｎ通りの連想セツトの場合は、Ｎ−１
個のコントロール回路が存在することになる。各コント
ロール回路は１ビツトのメモリに関連され、それに接続
されているどの分岐がLRU分岐であるのかを判断するこ
とにより、Ｎ通りの連想セツトはLRUメモリ位置を判断
するためにタグ・メモリにおけるアドレス指定可能な位
置に対してＮ−１ビツトのメモリを必要とすることにな
る。

下位の各コントロール回路190及び192は、比較回路144
〜150が出力する２つのアクセス信号ACCを線174から、
また不良メモリ184から２つの不良信号FIをその入力に
導入している。各コントロール回路190及び192も「WE」
により表わすLRU信号LRUを線182も介して出力してい
る。更に、アクセス出力信号ACC及び不良出力信号FOも
次に高位のコントロール回路194に出力され、一方これ
からLRUにより表わす入力にLRU信号を受取つている。高
位のコントロール回路194は下位のコントロール回路190
及び192と同じである。

データ・バス178はビツト線をそれぞれトランシーバ19
6、198及び200を介して各コントロール回路190〜194に
接続している。各トランシーバ196〜200はデータ・バス
178からデータを読出すか、又はデータ・バス178にデー
タを書込むのかを決定するエネーブル入力ENを有する。
トランシーバ196〜200の出力はLRUMENIN及びLRUMEMOUT
により表わす入力に接続されている。

第５図のLRU構成及びその構造は、LRU部分を決定する効
果的な方法を与えることにより、Ｎ通りの連想セツトに
ある多数のキヤツシユ部材を容易なものにする。これ
は、アドレス及び物理アドレスにより直接アドレス指定
可能なキヤツシユ部分を用いたときは、もつときわどい
ものとなる。その理由はページ大きさに対して各自の大
きさに限界があるためである。例えば、ページの大きさ
が256ワードのときは、仮想アドレス及び物理アドレス
は８ビツトの共通フイールドを有する。これは大きなＮ
通りの連想セツトを用いることが必要となる個々のキヤ
ツシユ・メモリ容量を増大しないようにするものであ
る。

第６図を参照すると、コントローラ回路190〜194の一つ
の概要ブロツク図である。LRU MEN ENにより表わす入力
は接続点202に接続され、これに印加されるデータの状
態は論理「１」か又は論理「０」のいずれかである。論
理「１」の場合は、コントローラ回路は一の方向に切換
えられて一の分岐がLRU装置であることを示す。論理
「０」の場合は、コントロール回路は他方向に切換えら
れて他の分岐がLRU装置であることを示す。ORゲート204
は一方の入力を接続点202に接続し、他方の入力を図示
の都合上FI1により表わす故障入力に接続している。OR
ゲート204の出力はANDゲート206の一方の入力に接続さ
れ、その出力はANDゲート208の一方の入力に接続されて
いる。ANDゲートの他方の入力はインバータ210を介して
他方の故障入力FI2に入力されている。ANDゲート208は
その出力をLRU2により表わす出力に接続され、出力LRU2
はWEにより表わす線182に接続されている。ANDゲート20
8の他方の入力は上位のコントロール回路からLRU1によ
り表わすLRU入力に接続されている。

ANDゲート208は、LRUI入力の信号及びANDゲート206の出
力の両方を受取ると、LRU2線を付勢する機能がある。こ
のような条件は、上位のコントロール回路がLRU分岐と
して分岐を選択をし、かつLRUメモリ176から受取つたデ
ータ・ビツトがこのモードでは論理「１」の正しい論理
状態にあることによる。ORゲート204の入力が論理
「１」、かつインバータ210が出力する論理「１」によ
つて、AND206はANDゲート208の入力に論理「１」を供給
する。LRU1入力に論理「１」が入力されると、LRU2出力
が付勢される。

LRU1により表わす他方のLRU出力はANDゲート212の出力
に接続されており、ANDゲート212の一方の入力にはLRU1
信号が供給され、その他方の入力にはANDゲート214の出
力が供給されている。ANDゲート214はその一方の入力を
インバータ216を介してFI1により表わす他方の不良信号
に接続し、他方の入力をORゲート218の出力に接続して
いる。ORゲート218の一方の入力はインバータ220を介し
て接続点202に接続され。またその他方の入力は他方の
不良信号F12に接続されている。ANDゲート212を付勢す
るためには、LRUメモリ176から受取るデータ・ビツト
は、論理「０」、即ちインバータ220から論理「１」を
出力するものでなければならない。

LRUメモリ176に記憶したデータがLRU信号をLRU1出力又
はLRU2出力に送出するためには、不良信号FI1及びFI2は
論理「０」でなければならない。しかし、与えられた分
岐に対応した不良メモリ184に不良が記憶されていると
きは、この不良信号は反対側のコントロール回路にLRU
信号を印加させる。例えば、LRU1信号により制御された
キヤツシユ・メモリに不良が存在するときは、FI1入力
に論理「１」に信号が入力される。これはORゲート204
の出力を論理「１」にし、インバータ216の出力を論理
「０」にする。これによりANDゲート212が禁止されるの
で、LRU1信号が出力されるのを阻止し、かつANDゲート2
08に印加されるので、LRU2入力を付勢するために必要と
するのはLRUI信号だけである。

LRU1信号に関連しているアクセス信号はACC1により表わ
されており、これをANDゲート224の入力に接続し、その
他の入力はインバータ216の出力に接続されている。AND
224の出力はORゲート226の一方の入力に接続され、その
出力はLRU MEM OUT端子に接続されている。LRU2出力に
関連している他のアクセス信号は、ANDゲート228の一方
の入力に供給され、その他方の入力はインバータ210の
出力に接続されている。ANDゲート228の出力はインバー
タ232を介してANDゲート230の一方の入力に接続されて
いる。ANDゲート230の他方の入力はLRU MEM IN入力に接
続されており、ANDゲート230の出力はORゲート226の他
方の入力に接続されている。ANDゲート224及び228の出
力はORゲート234の各入力に接続されており、その出力
はACCにより表わすコントロール回路の出力アクセス信
号に接続されている。

動作において、FI1及びF12の不良信号が論理「０」のと
きは、ACC1か、又はACC2のアクセス信号が各ANDゲート2
24又は228を付勢する。ACC1が付勢されると、ORゲート2
26の出力は論理「１」となる。ACC2入力が付勢され、か
つ不良信号F12が論理「０」であるときは、ANDゲート22
8が付勢されてインバータ232の出力を論理「０」にする
結果、LRU MEM OUT出力を論理「０」となる。ACC1又はA
CC2にのみアクセス信号が存在し得ると共に、両入力は
同時には付勢されないことを理解すべきである。

ACC1及びACC2が共に付勢されなかつたときは、ANDゲー
ト224及び228の出力は論理「０」となる。この結果、AN
Dゲート224から論理「０」がORゲート226の一方の入力
に印加され、またインバータ232から論理「１」がAND23
0に入力される。ANDゲート230はその他方の入力をLRU M
EN IN入力に接続しているので、これが「０」になる
と、ANDゲート230から論理「０」を出力させることにな
る。ACC2信号が存在していないときに、LRU MEN IN入力
が論理「１」になると、ANDゲート230の出力が論理
「１」になる。

アクセス信号が存在すると、メモリ・ビットの状態を変
化させ、キヤツシユ・メモリのコントロール回路を反対
の分岐に切換える。例えば、KRU MEM IN入力が論理
「０」にあるときは、LRU1信号が付勢されるので、これ
が２分岐のうちのLRUであることを表示する。ACC1信号
に関連した分岐が付勢されると、LRU MEM OUTは論理
「１」に変化しなければならない。次いで、このビツト
はLRUメモリ176に記憶される。これは、上位のコントロ
ール回路のLRU1入力の状態に従い、コントローラ回路か
らLRU2出力を送出させることになる。次のアクセスのと
きにLRU2入力に関連した分岐がアクセスされると。ACC2
信号が付勢されるので、インバータ232の出力を論理
「０」にする。これにより、ORゲート226の入力を論理
「０」にし、コントロール回路からLRU1出力をするよう
にさせる。

不良信号FI1及びFI2が共にANDゲート236に入力され、そ
の出力がFO出力になる。この出力は上位のコントロール
回路の第１分岐に入力される。前述のように、不良の存
在によりLRUメモリ176に記憶されているデータ・ビツト
を無効にし、与えられたコントローラ回路の反対側の分
岐にLRU信号を常時印加させる。このようにして、関連
した不良を有する分岐が常時２つのうち最後にアクセス
された分岐となるので、この分岐に対するデータの書込
みが阻止される。

要するに、仮想アドレスか、又は物理アドレスのいずれ
かにより直接アドレス指定可能なキヤツシユ・メモリが
提供された。階層ツリー構造を用い、記憶したメモリの
Ｎ−１ビツトを用いることにより、Ｎ通りの連想セツト
におけるLRUメモリ位置を判断する。LRUアルゴリスム
は、どの装置がLRUビツトであるかを表わす記憶メモリ
・ビツトに基づいており、かつ不良メモリ位置がLRUメ
モリ位置として指定されるのを阻止する不良ビツトに基
づいているので、これにデータを書き込むのを阻止する
ものである。

本発明の実施態様を詳細に説明したが、特許請求の範囲
に記載したように、本発明の精神及び範囲を逸脱するこ
となく、これに対して種々の変更、交換及び置換が可能
なことを理解すべきである。

【図面の簡単な説明】

第１図は関連のキヤツシユを有する多重プロセツサを用
いた本発明による多重プロセツサ装置の概要ブロツク
図、第２図は与えられたキヤツシユ用のタグ・メモリに
おける仮想アドレス及び物理アドレスのマツピング図、
第３図は仮想アドレス及び物理アドレスの両方を識別す
るキヤツシユのタグ・メモリ及びデータ・メモリを示す
ブロツク図、第４図は連想セツトのキヤツシユの概要ブ
ロツク図、第５図はLRUコントローラ回路の概要ブロツ
ク図、第６図はLRUコントローラ回路の一ブロツクにつ
いての概要ブロツク図である。 64、108、110、112、114……データ・メモリ、66、11
6、118、120、122……タグ・メモリ、68……仮想タグ・
メモリ、70……物理タグ・メモリ、72……LSBアドレス
・バス、78、84……スイツチ、88……仲裁装置、100、1
44、146、148、150……比較回路、172……LRUコントロ
ーラ、176……LRUメモリ、184……不良メモリ。

Claims (3)

【特許請求の範囲】
1. 【請求項１】物理アドレス及び仮想アドレスによりアド
   レス可能なキャッシュ・メモリにおいて、 仮想又は物理アドレスからなり、所定数の最下位ビット
   からなるLSB部及び残りの最上位ビットからなるMSB部を
   有すると共に、前記仮想及び物理アドレスのLSB部を全
   てのアドレス・データに共通にしている所望のデータの
   アドレスを受取るバス手段と、 データを記憶すると共に、前記データに関連した仮想及
   び物理アドレスを有し、受取った前記アドレスのLSB部
   によりアドレス指定可能とし、受取った前記アドレスの
   LSB部が記憶した前記データに関連するアドレスのLSB部
   に対応したときに出力するキャッシュ・メモリ手段と、 記憶した前記データに関連する仮想及び物理アドレスの
   MSB部を記憶するとともに、記憶した前記仮想及び物理
   アドレスを受取った前記LSB部によりアドレス指定可能
   にし、受取った前記LSB部が記憶した前記データのう
   ち、関連する、一つのアドレスのLSB部分に対応したと
   きに出力するタグ・メモリ手段と、 受取った前記アドレスが仮想アドレスのときは、記憶し
   た前記仮想アドレスのMSB部を選択し、受取った前記ア
   ドレスが物理アドレスのときは前記物理アドレスのMSB
   部を選択する仲裁手段と、 受取った前記MSB部を前記タグ・メモリ手段から選択し
   た前記MSB部とを比較する比較手段と、 前記比較手段が有効な比較をしたときは前記キャッシュ
   ・メモリ手段よりデータを出力するスイッチ手段と、 を含む物理アドレス及び仮想アドレスによりアドレス指
   定可能なキャッシュ・メモリ。
2. 【請求項２】仮想アドレス及び物理アドレスによりアド
   レス指定可能なキャッシュ・メモリにおいて、 所望のデータを表す外部ソースからLSB部及びタグ部を
   有するアドレスを受取ると共に、前記LSB部に前記アド
   レスの所定数の最下位ビットを備え、かつ前記タグ部に
   前記アドレスの残りのビットを備え、前記データを一つ
   の物理アドレス及び仮想アドレスと関連させ、かつ前記
   仮想アドレス及び物理アドレスのLSB部を同一にしたバ
   ス手段と、 受取った前記アドレスのLSBによりアドレス指定可能に
   し、LSBアドレス位置にて選択データを記憶すると共
   に、前記LSBアドレス位置を前記選択データと関連する
   前記アドレスのLSB部に対応させているキャッシュ・デ
   ータ・メモリと、 受取った前記アドレスのLSB部によりアドレス指定可能
   にし、記憶した物理アドレスのタグ部におけるLSB部に
   対応したLSBアドレス位置に前記選択データに関連する
   前記物理アドレスのタグ部を記憶する物理タグメモリ
   と、 受取った前記アドレスのLSB部によりアドレス指定可能
   にし、記憶した仮想アドレスのタグ部におけるLSB部に
   対応したLSBアドレス位置に前記選択データに関連する
   前記仮想アドレスのタグ部を記憶する仮想タグメモリ
   と、 前記バス手段に接続され、受取った前記アドレスが物理
   アドレスであるか又は仮想アドレスであるかを判断し、
   受取った前記アドレスが仮想アドレスであるときは第１
   状態にて、また受取った前記アドレスが物理アドレスで
   あるときは第２状態にて制御信号を出力するようにした
   仲裁手段と、 前記制御信号により制御され、かつ前記仮想及び物理タ
   グ・メモリによりインターフェース接続され、前記第１
   状態のときは前記仮想アドレスのタグ部を出力し、また
   前記第２状態のときは前記物理アドレスのタグ部を出力
   するようにしたマルチプレクサ手段と、 前記マルチプレクサ手段により出力された仮想アドレス
   のタグ部を受取った前記アドレスのタグ部と比較する比
   較器と、 前記キャッシュ・メモリの出力に接続され、かつ前記比
   較器により制御され、前記比較器により比較が真となっ
   たときは前期キャッシュ・メモリのアドレス・データを
   出力するように制御されたスイッチと、 を備え、前記キャッシュ・メモリは受取った前記アドレ
   スのLSB部によりアドレス指定されたときは、前記選択
   データを出力し、かつ、前記仮想及びタグ・メモリは受
   取った前記アドレスのLSB部によりアドレス指定された
   ときは、前記キャッシュ・メモリにより出力された前記
   選択データに対応する前記仮想アドレス及び物理アドレ
   スのタグ部を出力することを含む仮想アドレス及び物理
   アドレスによりアドレス指定可能なキャッシュ・メモ
   リ。
3. 【請求項３】仮想アドレス及び物理アドレスによりキャ
   ッシュ・データ・メモリをアドレス指定する方法におい
   て、 所定数の最下位ビットからなるLSB部及び残りのビット
   からなるタグ部を有するデータに関連したアドレスを外
   部ソースから受取ると共に、前記データを仮想アドレス
   及び物理アドレスに関連させ、前記仮想及び物理アドレ
   スのLSBを同一にする処理と、 受取った前記アドレスのLSB部によりアドレス可能なメ
   モリ位置にキャッシュ・データを記憶すると共に、記憶
   した前記データに関連したアドレスのLSB部に前記LSB部
   のアドレス位置を対応させる処理と、 記憶した前記キャッシュ・データに関連した物理及び仮
   想アドレスのタグ部を記憶すると共に、記憶した前記物
   理及び仮想アドレスの前記タグ部を受取った前記データ
   のLSB部によりアドレス指定可能とする処理と、 受取ったアドレスが仮想アドレスのときは記憶した前記
   仮想タグ部を選択し、また受取ったアドレスが物理アド
   レスのときは記憶した前記物理タグ部を選択する処理
   と、 選択した前記タグ部と受取ったタグ部を比較する処理
   と、 受取った前記タグ部と選択した前記タグ部との間で有効
   な比較が成立したときは前記キャッシュ・データ・メモ
   リから受取った前記アドレスのLSB部によりアドレス指
   定することによりデータを出力する処理と、 を含む仮想アドレス及び物理アドレスによりキャッシュ
   ・データ・メモリをアドレス指定する方法