JPH0555899B2

JPH0555899B2 -

Info

Publication number: JPH0555899B2
Application number: JP2123225A
Authority: JP
Inventors: Ryuu Rishiingu
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1989-05-17
Filing date: 1990-05-15
Publication date: 1993-08-18
Also published as: EP0397994A3; EP0397994A2; EP0397994B1; DE69027253T2; US5130922A; JPH036756A; DE69027253D1

Description

【発明の詳細な説明】Ａ産業上の利用分野本発明は、一般に多重プロセツサ・データ処理
システムの中のキヤツシユ・メモリに関し、具体
的には、データがストアイン・キヤツシユ・メモ
リを介してどのようにアクセスできるかを示すた
めに一時的アクセス状態を使用することに関す
る。

Ｂ従来技術現代の高性能プログラム記憶式デイジタル・コ
ンピユータでは、従来から、キヤツシユ・メモリ
を使用して主記憶装置に存在する命令とデータに
アクセスしている。キヤツシユ・メモリとは、コ
ンピユータの主記憶装置より通常はるかに小型で
高速の、プロセツサにきわめて近い位置にあるメ
モリである。ほとんどすべての高性能デイジタ
ル・コンピユータは、キヤツシユ・メモリを使用
し、市販のマイクロプロセツサでさえそのアーキ
テクチヤにキヤツシユ・メモリを含んでいる。

キヤツシユ・メモリが開発されたのは、デー
タ・アクセス時間が現在のパイプライン式プロセ
ツサと整合する、きわめて大きなメモリを妥当な
価格で構築するのが不可能だつたが、プロセツサ
の速度についていける安価で小さなメモリをつく
るのは可能だからである。

キヤツシユ・メモリの設計は、データ処理シス
テムで認められる２つの特徴を利用する。第１の
特徴は、参照の時間的局所性と呼ばれている。こ
の特性は、プロセツサが比較的小さい時間間隔内
に繰り返してある命令またはデータ値にアクセス
する傾向を言う。第２の特徴は、参照の空間的局
所性と呼ばれている。この特性は、プロセツサが
小さな時間間隔内に主記憶装置内のアドレスが比
較的小さい値だけ異なるデータまたは命令にアク
セスする傾向を言う。こうした第１及び第２の特
性が、最近にアクセスされたデータ及び命令を含
むメモリ・ワードと、プロセツサのアドレス空間
中で最近にアクセスされたワードにすぐ隣接する
各メモリ行を、キヤツシユ・メモリに保持するこ
との理論的根拠である。

キヤツシユ・メモリは、単一プロセツサでも多
重プロセツサ・システムでも使用されている。緊
密結合システムとして知られているあるタイプの
多重プロセツサでは、それぞれ独自のキヤツシ
ユ・メモリをもついくつかの中央プロセツサが共
通のオペレーテイング・システムと共通の主記憶
装置を共用する。緊密結合システムでは、各キヤ
ツシユ・メモリが、他のすべてのキヤツシユ・メ
モリと協調して動作することが望ましい。特に、
各プロセツサが、主記憶装置にあろうとまた他の
プロセツサのキヤツシユ・メモリにあろうと、デ
ータ値の最近に更新されたバージヨンを獲得でき
なければならない。したがつて、キヤツシユ間で
データの整合性を絶えず監視することが望まし
い。この監視動作はキヤツシユ整合性制御と呼ば
れている。

従来技術では様々な形式のキヤツシユ・メモリ
がある。１つの形式は、ストアスルー（ST）キ
ヤツシユであり、データ記憶命令は、命令を起動
するプロセツサに関連するキヤツシユ・メモリへ
の記憶、主記憶装置への記憶、及びシステムの他
のキヤツシユ・メモリ中のデータの局所コピーを
無効にする一連の相互照会（XI）動作の３つの
部分をもつ。通常、STキヤツシユ・メモリ設計
では、実質的な主記憶帯域幅が効率的に機能する
ことが必要である。

もう１つの形式の設計は、ストアイン（SI）キ
ヤツシユである。SIキヤツシユ設計及び多重プロ
セツサ・システムによるその使用は、米国特許第
450497号明細書に記載されている。この明細書を
引用により本明細書に合体する。SIキヤツシユで
は、データ値がキヤツシユ間（CTC）転送バス
を介して様々なキヤツシユ・メモリ間で転送され
る。この形式のキヤツシユも、様々なキヤツシ
ユ・メモリの内容を調整するためにXI動作を使
用する。すべてのメモリ・アクセスを制御する中
央記憶制御装置は、様々なキヤツシユ・メモリの
内容のデレクトリを含んでいる。上記の特許に記
載されたシステムでは、キヤツシユ・メモリによ
つて保持された隣接するメモリ・ワードの各行
（ライン）が、そのアクセスが、排他的／読取り
専用（EX／RO）フラグ・ビツトによつて制御
される。通常、データ値は、メモリ・ワードの行
がキヤツシユ・メモリから置換され、それらの行
のデータが修正されたときだけ、主記憶装置で更
新される。

メモリ・ワードの行は、たとえばLRU方式に
したがつてキヤツシユから置換され主記憶装置に
書き込まれる。キヤツシユから主記憶装置へのメ
モリ・ワードの行の転送は、キヤストアウト動作
として呼ばれている。データが主記憶装置に書き
込まれるのは、それがキヤツシユからキヤストア
ウトされるときだけなので、SIキヤツシユ・メモ
リを使用する多重プロセツサ・システムの記憶帯
域幅要件は、STキヤツシユ・メモリを使用する
対応するシステムのそれより小さい。しかし、帯
域幅要件のこの低下を得るためには、キヤツシユ
整合性制御システムがより複雑になり、キヤツシ
ユ間コピー動作と付属XI事象によつてプロセツ
サの実行速度が犠牲になる。

SIキヤツシユ・メモリを使用した代表的な多重
プロセツサ・システムでは、各キヤツシユは、メ
モリ・ワードの行へのアクセスが読取り専用
（RO）か、排他的（EX）か、それとも無効
（INV）かに関する情報を含むキヤツシユ・デイ
レクトリを含む。さらに、メモリ・ワードの行が
EX状況の場合、そのデイレクトリは、その行中
のデータが変更されたかどうかを示す情報（CH
ビツト）を含む。

行の状況がROの場合、その行のデータは読取
りしかできない。一般に、命令ワードの行はこの
状況をとる。ROキヤツシユ行は様々なキヤツシ
ユ・メモリで同時に存在することができる。

メモリ・ワードの行がEXの状況をとる場合、
その行は１つのプロセツサのキヤツシユのみに現
れる。そのキヤツシユ中にこの行をもつプロセツ
サだけが、メモリ・ワードの行からデータを取り
出し、またはその行にデータを記憶することがで
きる。さらに、その行に対するデイレクトリ項目
CHが、行中のデータが変更されたことを示す場
合、そのキヤツシユ行中のデータは、主記憶装置
中の対応するデータと一致しない。CHビツトが
セツトされた行がキヤツシユ中で置換されると、
キヤストアウト動作によつてコピーが主記憶装置
に送られる。

メモリ・ワードの行は、それが無効のとき、
INV状況をとる。１つのキヤツシユ・メモリ中
のある行のEXまたはROの状況は、その行が他
のキヤツシユ・メモリによつてEX状況で獲得さ
れたとき、INVに変わる。

SIキヤツシユ・メモリ（たとえば、上記の米国
特許第4503497号におけるような）を使用する代
表的な多重プロセツサ・システムは、以下のよう
に動作する。まず、あるプロセツサが、たとえば
データ取出し命令を使つてデータ・ワードを要求
する。この要求に応えて、そのプロセツサはそれ
自体のキヤツシユを検査して、そのワードを含む
行を探す。キヤツシユがその行を含む場合、その
データ・ワードが通常の命令実行中にプロセツサ
に送られる。しかし、プロセツサがそれ自体のキ
ヤツシユ中にその行を見つけられなかつた場合
は、その要求が記憶制御装置に渡される。記憶制
御装置は、その要求をすべてのキヤツシユの内容
を示すデイレクトリと突き合わせて検査する。目
標行が遠隔キヤツシユで見つかり、その状況が
ROである場合、それが要求側キヤツシユにコピ
ーされる。その状況がEXであり、CHビツトが
リセツトされている場合は、その行がRO状況で
要求側キヤツシユにコピーされ、遠隔キヤツシユ
中のその行の状況がROに変更される。CHビツ
トがセツトされている場合は、その行が、EX状
況でCHビツトがセツトされて要求側キヤツシユ
にコピーされる。遠隔キヤツシユ中のその行のコ
ピーは無効になる。その行をEX状況のままにし
CHビツトをセツトされたままに保持することに
より、システムは、プロセツサは、近い将来にそ
の行にデータを記憶することを予期する。最後
に、データの目標行がどのキヤツシユにも見つか
らない場合、その行は、主記憶装置からアクセス
され、ROの状況が割り当てられる。

上記に概略を述べた方法の結果、多重プロセツ
サ・キヤツシユ・メモリ・システムの並行性が不
必要に失われることがある。たとえば、ある行の
データが頻繁にアクセスされ、稀にしか修正され
ないときにこのことが起こる。ある行がプロセツ
サによつて修正されると、それはEX状況をとり、
そのCHビツトがセツトされる。この状態は、そ
の行がLRU置換アルゴリズムによつてキヤツシ
ユから置換されるまで続く。この例では、その行
に対する頻繁な取出しの１回ごとに、XI事象が
遠隔キヤツシユ中のその行のコピーを無効にす
る。

この異常が発生するのは、EXの状況をもつ行
のデータが変わつた後、その行が主記憶装置にキ
ヤストアウトされるまで、そのCHビツトがセツ
トされたままの状態となるためである。キヤツシ
ユが大きくなり、多重プロセツサ・システムで使
用されるプロセツサの数が増大するにつれて、こ
の問題は大きくなる。キヤツシユが大きくなつて
も、行の寿命はそれほど迅速に進まず、プロセツ
サの数が増加するにつれて、ある行の寿命が尽き
る機会がないままに、XI事象によつてプロセツ
サ間で回される傾向が大きくなる。

米国特許第4484267号明細書は、ある行のデー
タがある状況ではストアイン・キヤツシユ内と同
様に扱われ、他の状況ではストアスルー・キヤツ
シユ内と同様に扱われる、混成キヤツシユ・アー
キテクチヤに関するものである。上記特許に記載
されているシステムでは、キヤツシユ・デイレク
トリ中のEX／ROビツトの代りに共用（SH）ビ
ツトが使用される。あるデータ行が最初にアクセ
スされるとき、その行に対するSHビツトがゼロ
にセツトされる。このため、その行は、SIキヤツ
シユ中にあり、EX状況をもつかのように扱われ
る。他のプロセツサがその行のデータにアクセス
する場合、記憶制御要素がSHビツトを１にセツ
トして、他のプロセツサに結合されたキヤツシユ
がCTCバスを介してその行をコピーできるよう
にする。次にどちらかのプロセツサがその行のデ
ータに対する記憶動作を要求する場合、新しいデ
ータがSTキヤツシユ内と同様に要求側キヤツシ
ユ及び主記憶装置中の行に記憶される。同時に、
XI事象が他のキヤツシユ中のその行のすべての
コピーを無効にする。しかし、要求側キヤツシユ
中のSHビツトはセツトされたままであり、その
結果、他のキヤツシユがそのデータにアクセスす
る場合には、CTCバスを介してその行をコピー
することにより、その要求が満たされる。

米国特許第4394731号明細書は、多重プロセツ
サSIキヤツシユ・メモリ・システムに関するもの
である。このシステムでは、EX状況をもつある
行が２つの場合に獲得できる。第１に、いずれか
の遠隔キヤツシユにその行のコピーがないとき、
第２に、その行が遠隔キヤツシユにあり、EX状
況という状況をもち、そのCHビツトがセツトさ
れているときである。このキヤツシユ・システム
はキヤツシユ間バスを含まないので、上記の第２
のケースでは、CH行は主記憶装置にキヤストア
ウトされ、次いで要求側キヤツシユにEX状況で
割り当てられる。遠隔キヤツシユ中のデータ行が
EXの状況をとりCHビツトがリセツトされてい
る場合、遠隔キヤツシユの状況はROに格下げさ
れ、その行は主記憶装置から要求側キヤツシユに
RO状況でコピーされる。

米国特許第4503497号明細書は、キヤツシユ間
転送バスを含む多重プロセツサSIキヤツシユ・メ
モリ・システムに関するものである。このシステ
ムは、その行の状況またはそのCHビツトの状態
を変えることなく、また主記憶装置にアクセスす
ることなく、EX状況をもちCHビツトがセツト
されている目標行を遠隔キヤツシユから要求キヤ
ツシユに転送する。遠隔キヤツシユ中の目標行は
無効にされる。

Ｃ発明が解決しようとする課題本発明の目的は、不必要なXI及び無効化事象
を回避することにより、予期される排他的状況の
獲得を有効に利用する、多重プロセツサ・キヤツ
シユ・メモリ・システムを提供することにある。

Ｄ課題を解決するための手段本発明は、キヤツシユ・ミスに応えてアクセス
されるデータ行に一時的排他的（TEX）状況が
割り当てられる、多重プロセツサ・キヤツシユ・
メモリ・システムで具体化される。この状況は寿
命が迅速に進む。状況の寿命が尽きる前にTEX
行への記憶が試みられる場合、その状況がEX（排
他的、専有）に格上げされる。その行の寿命が尽
きる前に行への記憶が試みられない場合、その状
況はRO（リード・オンリ）に格下げされる。本
発明の他の特徴によると、アクセスされた行が遠
隔キヤツシユ中に存在するとき、遠隔キヤツシユ
中のその状況は一時的読取り専用（TRO）に設
定され、その行は要求側キヤツシユ中ではTEX
状況をとる。TEX状況がEXに格上げされる場
合、遠隔キヤツシユ中の行は無効とマークされ
る。TEX状況がROの格下げされる場合、TRO
状況はROの格上げされる。

Ｅ実施例以下に、本発明による例示的ストアイン・キヤ
ツシユ・メモリ・システムについて説明を示す。
本明細書で記載するシステムは、米国特許第
4503497号明細書に記載されたシステムの改良で
ある。上記明細書を引用により本明細書に合体す
る。

キヤツシユイン・メモリ・システムは、IBM
社製の3090システムなど最新の多重プロセツサ・
メインフレーム・コンピユータで通常使用されて
いる。こうしたシステムでは、各プロセツサごと
に１個ずつキヤツシユ・メモリがある。

各キヤツシユ・メモリにデイレクトリが付随
し、デイレクトリの各項目は、INV，RO及び
EXの３つの可能な状況のうちの１つをとること
ができる。INV状況は、デイレクトリ中のその
項目が無効であることを示す。この状況は、たと
えば、あるキヤツシユ中でRO状況をとる行が
EX状況をもつ他のキヤツシユによつて獲得され
るとき、最初のキヤツシユ中のデータ行に割り当
てられる。

RO状況は、そのデータ行が読取り専用状態で
有効なことを示す。そのプロセツサは、その行か
らデータの取出ししかできない。データの行は、
各キヤツシユ・デイレクトリ中でRO状況をとる
場合、複数のキヤツシユ中に同時に存在すること
ができる。

データ行がそのキヤツシユ・デイレクトリ項目
でEX状況をもつときは、その行は、他のキヤツ
シユに存在することができない。そのキヤツシユ
を所有するプロセツサだけが、XI事象の介入な
しでデータをその行に記憶することができる。

キヤツシユ・デイレクトリ中のCHビツトは、
EX状況をもつデータ行に対してのみ働く。CH
ビツトは、セツトされると、データがその行に記
憶されていることを示す。このビツトがある行の
デイレクトリ項目でセツトされると、キヤツシユ
中のデータ行が主記憶装置中の対応するデータ行
と同じでない可能性があることを示す。CHビツ
トがセツトされた行がキヤツシユ中で置換される
と、その行に対する修正がキヤストアウト動作に
よつて主記憶装置に送られる。

本発明によるシステムは、一時的排他的
（TEX）及び一時的読取り専用（TRO）の２つ
の状況を追加することにより、SIキヤツシユ設計
の機能を高める。TEX状況は、EX状況をもち
CHビツトがセツトされた遠隔キヤツシユ中で見
つかり、要求側キヤツシユにコピーされた、ある
行に割り当てられる。遠隔キヤツシユ中の行は無
効にならず、その状況がTROに設定される。

TEXの状況は過渡的状況にすぎない。行が
TEX状況をもつ間にデータをその行に記憶する
試みが行なわれない場合、要求側キヤツシユ中の
その行の状況はROに格下げされ、遠隔キヤツシ
ユ中のその状況はROに格上げされる。その状況
がTEXである間にその行にデータが記憶された
場合は、要求側の行の状況はEXに格上げされ、
遠隔行の状況はINVに設定される。その行にEX
状況を割り当てることにより、データ取出し要求
に応えてアクセスされた行への記憶を予期すると
いうこの戦略は、多重プロセツサ・システムで認
められる傾向を活用したものである。本発明者の
観察によると、あるプロセツサが、取出し要求で
最初にデータにアクセスした後でデータを変更す
るとき、そのプロセツサは、取出し要求の後で比
較的速やかにその変更を行なう。

この戦略は、不必要なXI事象及び無効化動作
を減らす。というのは、そのデータ行は、一時的
EX状況が割り当てられるとき、依然として遠隔
キヤツシユ・メモリと要求側キヤツシユ・メモリ
の両方に存在しているからである。すなわち、あ
る行のデータが頻繁に取り出されるが、稀にしか
変更されない場合、その行はROの状況をとり、
大部分の取出し要求で複数のプロセツサがそのデ
ータを共用できるようにする。その行は、その行
のデータが変更されるとき、稀にしかEX状況を
とらない。

第１図は、本発明の実施例を含む２プロセツ
サ・システムの構成図である。以下に示す例で
は、一方のプロセツサ１０が要求側プロセツサ
で、他方のプロセツサ１２が遠隔プロセツサであ
る。以下に掲示する例は２プロセツサ・システム
の状況におけるものであるが、当業者なら、より
多数のプロセツサを含むように、このシステムを
容易に拡張することができる。

第１図を参照すると、キヤツシユ・メモリ１８
と２０が、共通記憶制御装置（SC）２４に接続
されている。キヤツシユ１８と２０は、それぞれ
バツフア制御装置（BC）１４と１６を介して当
該のプロセツサ１４と１６に接続されている。バ
ツフア制御装置１４と１６は、その関連するキヤ
ツシユ・メモリに対するデイレクトリを維持す
る。記憶制御装置２４は、バツフア制御装置１８
と２０のそれぞれからのデイレクトリの一部分の
コピーを保持する。

プロセツサ１０と１２によつて生成されるすべ
てのメモリ・アクセスは、その関連するキヤツシ
ユ・メモリ１８と２０を介して処理される。ある
データ項目がキヤツシユ中で見つからない場合
（すなわち、キヤツシユ・ミス時）、バツフア制御
装置は、記憶制御装置２４に対するそのデータへ
のアクセス要求を生成するように、キヤツシユを
条件付ける。記憶制御装置２４は、要求されたデ
ータ項目を含むデータの行のコピーを得るのに必
要な処置を講じる。この行は遠隔キヤツシユから
得られることもあり、遠隔キヤツシユ中で見つか
らない場合は、主記憶装置２６から獲得される。
要求されたデータが遠隔キヤツシユ中で見つかる
と、主記憶装置２６にアクセスすることなく、キ
ヤツシユ間（CTC）バス２２を介してそのデー
タが要求側キヤツシユに送られる。キヤツシユ・
メモリ２８と２０は、それぞれ一時スタツク・メ
モリ１９と２０に接続されている。記憶制御装置
２４は、一時デイレクトリ・メモリ２５に結合さ
れている。これらのメモリの機能について次に述
べる。

キヤツシユ１８または２０からの要求を受け取
ると、記憶制御装置２４は、要求されたデータへ
の要求されたアクセスを許可するのにどんな動作
が必要かを決定する。記憶制御装置２４は、プロ
セツサ・キヤツシユに対するデイレクトリの部分
コピーを維持しているので、他のキヤツシユ中に
要求されたデータを含む目標行のコピーがあるか
どうか判定することができる。さらに、記憶制御
装置２４は、どのキヤツシユが目標行を含み、そ
れにどんな状況が割り当てられているかを判定す
る。

本発明にとつて、命令取出し（Ｉ取出し）、デ
ータまたはオペランド取出し（Ｄ取出し）及びデ
ータまたはオペランド記憶（Ｄ記憶）の３つの形
式のメモリ・アクセスが重要である。Ｉ取出しと
Ｄ取出しはデータへの読取りアクセスを要求し、
Ｄ記憶は書込みアクセスを要求するものである。
したがつて、Ｉ取出しでアクセスされたデータ行
は一般にRO状況を割り当てられ、Ｄ記憶でアク
セスされたデータ行はEX状況を割り当てられる。
Ｄ取出し要求でアクセスされたデータ行は、RO
状況を割り当てられることも、EX状況を割り当
てられることもある。

たとえば、IBM社製の3081型コンピユータで
は、Ｄ取出し要求時にキヤツシユ・ミスが発生
し、そのデータを含む行が、EX状況でCHビツ
トがセツトされて遠隔キヤツシユ中にあるとき、
要求側キヤツシユは要求側プロセツサからの将来
の記憶要求を予期してEX状況を割り当てる。こ
の戦略は、１つのプロセツサによつて修正された
データ行が、最初のアクセス要求がＤ取出しであ
るときでさえ再び修正される傾向があるという知
見に基づいている。ただし、この予期戦略の結
果、その行に対する記憶要求が生成されなくなつ
とき、上記のように、不必要な相互照会（XI）
事象と不必要な無効化動作が生じることがある。
次に第２図ないし第４図に関して様々な取出し動
作及び記憶動作について説明する。第２図のステ
ツプ100で、プロセツサ１０はＩ取出し要求を行
なう。ステツプ102で、バツフア制御装置１４は、
要求されたデータを含む行を探してキヤツシユ１
８のデイレクトリを検査する。その行がキヤツシ
ユ１８中に存在することがわかると、ステツプ
104で、そのデータへのアクセスが許可される。
ステツプ106で、キヤツシユ１８中にそのデータ
行が見つからなかつた場合（すなわち、キヤツシ
ユ・ミス時）、バツフア制御装置１４は、記憶制
御装置２４からデータを要求する。ステツプ108
で、記憶制御装置２４は、要求された行が遠隔キ
ヤツシユ２０にあるかどうか判定する。その行が
遠隔キヤツシユにない場合、ステツプ110で、記
憶制御装置２４は、主記憶装置（MS）２６から
のデータを要求する。要求された行が遠隔キヤツ
シユ２０中に見つかつた場合、それはRO状況で
ある。というのは、そのデータ行はＩ取出し要求
に応えて獲得されたからである。この検査は、判
断ブロツク114からのＮ分岐で表される。この場
合、ステツプ118で、その行がCTCバス２２を介
して遠隔キヤツシユ２０から要求側キヤツシユ１
８にコピーされる。その状況は変更されない。

しかし、Ｉ取出し要求に応えてアクセスされた
行が遠隔キヤツシユ２０中にEX状況をもつこと
もあり得る。この場合、CHビツトはセツトされ
ていることもリセツトされていることもある。そ
の遠隔行がEX状況をもちCHビツトがリセツト
されている場合、判断ブロツク114からＮ分岐を
とつてステツプ118に進む。ステツプ118で、その
行が遠隔キヤツシユ２０からCTCバス２２を介
して要求側キヤツシユ１８にコピーされ、両方の
キヤツシユ中の行の状況がROに変更される。判
断ブロツク114でＹ分岐をとる場合は、ステツプ
116で、変更された行を主記憶装置２６にキヤツ
シユアウトするように遠隔バツフア制御装置を条
件付けし、ステツプ118を実行する。ステツプ110
または118の結果としてデータ行がROの状況で
要求キヤツシユ中にあるとき、プロセツサ１０は
要求された命令を取り出すことができる。

第３図は、ステツプ200でプロセツサ１０がキ
ヤツシユ・メモリへのＤ取出し要求を開始すると
き、第１図に示したシステムが取るステツプを示
したものである。ステツプ202で、バツフア制御
装置１４は、要求されたデータがキヤツシユ・メ
モリ１８中にあるかどうか判定する。そのデータ
がキヤツシユ１８中で見つからない場合は、ステ
ツプ204で、バツフア制御装置１４は、遠隔キヤ
ツシユ２０または主記憶装置２６からのデータへ
のアクセス要求を記憶制御装置２４に送る。この
要求に応えて、ステツプ206で、記憶制御装置２
４は、要求されたデータを含む行が遠隔キヤツシ
ユ２０中にあるかどうか判定する。そのデータが
遠隔キヤツシユ中にない場合は、ステツプ208で、
記憶制御装置２４は、TEX状況をもつキヤツシ
ユ１８にデータを供給するため、主記憶装置２６
からのデータの取出し要求を発行する。この状況
指定では、要求された行のワードが、キヤツシユ
にもたらされた直後に記憶されるものと仮定す
る。この仮定が誤つている場合、TEX状況は自
動的にRO状況に格下げされる。

ステツプ206で記憶制御装置２４が遠隔キヤツ
シユ１８中に要求されたデータを見つけた場合、
次にステツプ24で、その行の状況を決定する。状
況がROである場合、ステツプ212で、記憶制御
装置２４はその行を要求側キヤツシユにコピー
し、要求側キヤツシユ中でそれにROの状況を割
り当てる。

遠隔キヤツシユ中のその行の状況が、EXまた
はTEXであるとステツプ210で判定された場合、
ステツプ218で、記憶制御装置２４は、その行へ
のアクセスを望んでいるとバツフア制御装置１６
に知らせる。ステツプ220で、バツフア制御装置
１６は、その行のCHビツトを検査する。CHビ
ツトがリセツトされている場合、ステツプ224で、
制御装置１６は、行の状況をROに変更して、そ
の行をRO状況で要求側キヤツシユ１８にコピー
する。要求側キヤツシユ中の状況はROである。
CHビツトがセツトされている場合、遠隔バツフ
ア制御装置１６は、要求側キヤツシユ１８にその
行をTEX状況でコピーするように記憶制御装置
２４に知らせる。CHビツトはセツトされたまま
である。要求側キヤツシユはその行のそのコピー
の状況をTROに変更する。

ステツプ202で、要求側バツフア制御装置１４
が要求側キヤツシユ１８中でその行を見つけた場
合は、ステツプ226に進む。ステツプ226で、制御
装置１４はその行の状況を検査する。その行の状
況がRO，EXまたはTEXである場合、そのプロ
セツサがその行にアクセスすることができる。こ
の条件は判断ブロツク226のＮ分岐で表される。
この分岐をとると、ステツプ228が実行されて、
要求されたデータをプロセツサ１０に供給する。

しかし、要求側キヤツシユ中のその行の状況が
TROであると判定された場合、バツフア制御装
置１４はデータへのアクセスをすぐには許可しな
い。というのは、この状況は、その行がTEX状
況で遠隔キヤツシユ中にある可能性があることを
示しているからである。したがつて、制御装置１
４は、ステツプ226，230，232及び234を含むルー
プを実行する。このループは、遠隔キヤツシユ中
のその行の状況を検査するよう記憶制御装置２４
に指示し、その状況の寿命が尽きてEXまたは
ROに変わるのを待つ。以下に述べるように、そ
の寿命は迅速に進み、かつTEX状況は比較的稀
にしか発生しないので、このループは、行中のデ
ータへのアクセスを許可する際に大きな遅延を引
き起さないはずである。遠隔行の状況がROに変
わつた場合、記憶制御装置２４は、要求側状況を
ROに変更し、要求側キヤツシユがデータにアク
セスできるようになる。一方遠隔キヤツシユ中の
状況がEXである場合は、ステツプ232からステツ
プ218に移り、上記のように要求側キヤツシユの
その行へのアクセスを許可する。

あるプロセツサによつて生成されるデータ要求
の最後の形式はＤ記憶である。第４図のステツプ
300で、プロセツサ１０がＤ記憶要求を生成する。
この要求に応えて、ステツプ302で、バツフア制
御装置１４は、そのデイレクトリを検査して、デ
ータを含む行がキヤツシユ１８中に存在するかど
うか判定する。存在する場合、判断ブロツク318
で、バツフア制御装置１４は、その行の状況が
TEXであるかどうか検査する。TEXの状況を見
出した場合、ステツプ320で、バツフア制御装置
は状況をEXに変更して、その行へのアクセスを
許可し、ステツプ324で記憶動作が行なえるよう
にする。一方、その行の状況がTEXでないこと
を見出した場合、バツフア制御装置１４は、判断
ブロツク322で、行の状況がEXであるかどうか検
査する。EX状況を見出した場合、ステツプ324
で、バツフア制御装置は記憶動作が行なえるよう
にする。その行の状況がEXでない場合は、RO
またはTROである。どちらの場合でも、ステツ
プ326で、バツフア制御装置は、その行にEX状況
を与えるように記憶制御装置２４に要求する。こ
の要求に応えて、制御装置２４は、遠隔キヤツシ
ユ・メモリ中のその行のコピーを無効にし、次い
で要求キヤツシユ１８中のその行の状況をEXに
設定する。

ブロツク302での初期検査でキヤツシユ１８中
にその行が見つかると、ステツプ304で、バツフ
ア制御装置１４は、EX状況をもつ行に対する要
求を記憶制御装置２４に発行する。この要求に応
えて、ステツプ306で、記憶制御装置２４は、デ
ータをそこに記憶すべきメモリ位置を含む行がメ
モリ・キヤツシユ２０中に存在するかどうか判定
する。その行が遠隔キヤツシユ中にない場合、記
憶制御装置２４は主記憶装置２６からその行を取
り出して、それをEX状況で要求側キヤツシユに
割り当てる。記憶制御装置２４が遠隔キヤツシユ
中でその行を見つけた場合、ステツプ310で、行
の状況を検査する。ステツプ310でEXまたは
TEX状況が見つかつた場合、ステツプ314で、記
憶制御装置２４は、その行を要求側キヤツシユ１
８に転送し、その行の遠隔コピーの状況をINV
に変更する（ステツプ316）ように遠隔バツフア
制御装置１６に指示する。

記憶制御装置２４が、ROまたはTROの状況を
もつ遠隔行を見つけた場合、ステツプ312で、遠
隔キヤツシユから要求キヤツシユへの行のコピー
を開始し、その行の遠隔コピーがあればそれを無
効にし、要求側キヤツシユ中のその行の状況を
EXに設定する。

ステツプ308，312，316、または328の任意のス
テツプの後で、要求側キヤツシユがEX状況の行
を持つとき、そのキヤツシユは、そのデータに対
する要求側プロセツサ１０のアクセスを許可す
る。

上記の流れ図には明らかに示してないが、記憶
制御装置２４が、バツフア制御装置１４と１６の
一方から発行された要求を修正することが可能で
ある。この形式の修正が行なわれるのは、その要
求が発行されてからそれにシステム制御装置２４
が作用するまでの間に、その行の状況が変更され
るときである。たとえば、第３図のステツプ226
で行の状況がTROであると判定され、バツフア
制御装置１４が、記憶制御装置２４にその行の遠
隔状況を検査するように要求するものと仮定す
る。この要求が行なわれる前に、要求側キヤツシ
ユ中のその行の状況がINVに変更されて、その
行がそのキヤツシユからアクセス不能になつてい
ることがあり得る。この場合、システム制御装置
２４は、その要求を、ステツプ230の遠隔状況検
査要求ではなく、（たとえば、ステツプ206の）ミ
ス要求として扱う。

上記の説明は、多重プロセツサ環境中の１つの
プロセツサからのＩ取出し、Ｄ取出し及びＤ記憶
要求を処理する際の、記憶制御装置２４及びバツ
フア制御装置１４と１６を通る制御フローに関す
るものである。第３図の命令ループを除いて、こ
の説明は、TEX状況およびTRO状況に寿命を設
けることには関係しない。しかし、これらの状況
に寿命を設けることは、本発明にしたがつて動作
するSIキヤツシユ・メモリ・システムの動作にお
ける重要な要因である。

本発明のこの実施例では、記憶制御装置２４及
びバツフア制御装置１４と１６が、別々のデータ
構造を使つてTEX状況及びTRO状況に寿命を設
けかつ記録する。これらのデータ構造は、それぞ
れ一時デイレクトリ２５及び一時スタツク１９と
２１である。一時スタツク１９と２１はそれぞ
れ、たとえば小さなスタツクの対を含む。各バツ
フア制御装置中の一方のスタツクは、どの行が
TEXの状況をもつかを示すデータを保持し、他
方のスタツクは、どの行がTROの状況をもつか
を示すデータを保持する。各スタツクは、連想メ
モリとして配列されたＮ個のレジスタを含む。一
時デイレクトリは、Ｐ×Ｎ個の項目をもつ連想メ
モリであり、Ｐは多重プロセツサ・システム中の
プロセツサの数である。このデイレクトリは、複
数のプロセツサ・システム中でTEX状況をもつ
各行ごとに１つずつ項目を保持するのに十分な空
間をもつ。本発明の実施例では、Ｎが１で、Ｐは
２である。

ある行が、たとえばTEX状況をもつキヤツシ
ユ１８中に取り出されるとき、バツフア制御装置
１４の局所デイレクトリ中のその状況が、たとえ
ばROに設定され、その行を識別するトークン
（たとえば、その行アドレスまたはキヤツシユ座
標）が制御装置１４のTEXスタツクに押し込ま
れる。さらに、その行に対する項目が記憶制御装
置２４の一時デイレクトリ中に作成される。同様
に、すでにキヤツシユ１８中にある行にTRO状
況が与えられると、そのデイレクトリ項目に
INV状況が与えられ、その行を識別するトーク
ンがTROスタツクに押し込まれる。

上記の例では、その状況を決定するために、あ
る行へのどのアクセスもどちらかのスタツクに自
動的に捕捉される（すなわち、関連スタツク中を
通る経路が設定される）。この動作方法は、ある
行の寿命が尽きたときの省略時状況値を確立す
る。TEX行はRO行になり、TRO行はINV行に
なる。この状況指定は、TROスタツクからある
行が削除されてからそのデイレクトリ項目が変更
されるまでの間に、プロセツサがその行への許可
不能なアクセスを得ることを妨げる、フエイルセ
ーフ機能をもたらす。これらの例では、ある項目
に対するデイレクトリ項目が変更されるのは、
TEX状況がEXに格上げされたとき、または
TRO状況がROに格上げされたときだけである。

TEX状況をもつ行にデータが記憶されると、
TEXスタツク中のその行の項目を削除し、デイ
レクトリ項目を変更することにより、その行に対
する状況は直ちにEXに変更される。同時に、一
時デイレクトリから対応する項目を除去し、遠隔
キヤツシユ中にその行のコピーがあればそれを無
効にするようにと記憶制御装置２４に指示が行な
われる。この動作により、当該のTROスタツク
から対応する項目を単に削除するだけで、遠隔プ
ロセツサに関連するキヤツシユ制御装置デイレク
トリ中のその行が無効にされる。

TEX状況及びTRO状況は置換動作により寿命
が尽きる。スタツクへの新しい項目が作成される
とき、古い項目の１つが削除（置換）される。た
とえば、制御装置１４のTROスタツク中のある
項目が置換されるとき、制御装置１４の局所デイ
レクトリ中の対応する項目中の状況が自動的に
INVになる。バツフア制御装置１４のTEXスタ
ツク中のある項目が置換されるとき、対応する行
に自動的にROの状況が与えられる。この場合、
遠隔キヤツシユに存在する以前のTEX項目のコ
ピーがあればその状況をTROからROに変更する
ことが望ましい。このステツプは多重プロセツ
サ・システムの全体的効率にとつて有益である
が、このステツプがなくとも、遠隔TRO項目は
省略時の値としてINVをとるので、不必要であ
る。

第３図のステツプ222で、EXの状況をもちCH
ビツトがセツトされている行が、要求側キヤツシ
ユ中でTEXの状況をもち、遠隔キヤツシユ中で
TROの状況をもつように変更することができる。
それ以上の介入なしに寿命が尽きる場合は、その
結果、状況がROでCHビツトがセツトされた行
のコピーが２つできることになる。すなわち、主
記憶装置２６中の対応するデータとは異なるデー
タを含む読取り専用行が２行できる。この異常な
状況を防止するため、この実施例では、TEX状
況をもちCHビツトがセツトされた行が、その寿
命が尽きてそのTEXスタツクから押し出される
ときに、キヤストアウト動作を実行する。

本発明者は、一時的状況に寿命を設けるこの方
法が、取出し要求の後に変更される行を十分な時
間排他的状況に保持し、予期される排他的状況を
使用しないシステムに比べて大きな性能の改良を
もたらすものと判断した。しかし、本明細書に記
載した方法はまた、不必要なXI及び無効化事象
の数を、予想に基づいてEX状況を割り当てる従
来のシステムに比べて減少させる。

一時的状況に寿命を設け記録するこの方法が好
ましいが、それが本発明者が企図する唯一の方法
ではない。たとえば、その行に対するデイレクト
リ項目中の追加ビツトで一時的状況の存在を示す
ことができる。この項目は、記憶制御装置のデイ
レクトリ中だけにあつても、また記憶制御装置と
バツフア制御装置の両方のデイレクトリ中にあつ
てもよい。この代替実施例では、あるデイレクト
リ中のすべての一時ビツトを定期的にリセツト
し、必要に応じて対応する項目の状況を変更する
ことにより、状況の寿命を進める。この動作は、
たとえばある行がTEX状況でキヤツシユ中に取
り出される度に、またはすでにキヤツシユ中にあ
る行の状況がTROに変わる度に実行される。一
時スタツクから一時的状況（特にTEX）の寿命
を定期的に進める他の方法は、タイマでそれをト
リガするものである。バツフア制御装置にTEX
状況があるときにタイマがセツトされ、タイマが
鳴る度に１つのTEX状況が解放される。

特定のアプリケーシヨンでTROとTEXの両方
の状態を使用する必要はない。たとえば、ある設
計ではTEX状態だけを使用する。第３図のステ
ツプ222で、Ｄ取出し要求にTEX状況が与えられ
るときは、遠隔EXコピーが、TRO状況に変更さ
れず、従来の設計と同様に無効になる。ある
TEX状況を早期に解放する（ROに変更する）こ
とにより、不必要なXI動作をさらに減らすこと
ができる。こうすると、他のバツフア制御装置が
TEX状況をRO状況に変えるときに、TRO状況
をRO状況に変更するように遠隔バツフア制御装
置に指示する必要がなくなる。一方、不必要なキ
ヤツシユ行無効化を回避する利点が失われる。

上記のシステムはストアイン（SI）キヤツシ
ユ・メモリ・システムに関するものであるが、同
じ形式のシステムがストアスルー・キヤツシユ・
メモリ・システムでも有利に使用できることが企
図されている。ストアスルー・キヤツシユ・シス
テム用の実施態様での唯一の重要な違いは、キヤ
ストアウト動作がなくせることである。というの
は、ストアスルー・キヤツシユ・システムでは、
データは自動的にキヤツシユを介して主記憶装置
に記憶されるからである。

【図面の簡単な説明】

第１図は、本発明の実施例を含む多重プロセツ
サ・システムの構成図である。第２図ないし第４
図は、第１図に示した多重プロセツサ・システム
で使用されるキヤツシユ・メモリ・システムの動
作を記述する流れ図である。１０，１２……プロセツサ、１４，１６……バ
ツフア制御装置（BC）、１８，２０……キヤツシ
ユ、１９，２１……一時スタツク・メモリ、２２
……キヤツシユ間（CTC）バス、２４……記憶
制御装置（SC）、２５……一時デイレクトリ・メ
モリ、２６……主記憶装置（MS）。

Claims

【特許請求の範囲】１主メモリ、複数のプロセツサおよびこれら複
数のプロセツサにそれぞれ設けられたキヤツシ
ユ・メモリを含むマルチプロセツサ・コンピユー
タ・システムにおいて、各プロセツサが、対応す
るキヤツシユ・メモリにおいて見つからないデー
タをアクセスする際につぎのステツプ(a)〜(d)を当
該キヤツシユ・メモリに対して実行することを特
徴とするキヤツシユ・メモリ制御方法。 (a) 当該プロセツサによる第１の形式のメモリ・
アクセス要求に応じて、上記データを含むメモ
リ・ワード・ラインを、主メモリまたは他のプ
ロセツサのキヤツシユ・メモリから、当該プロ
セツサのキヤツシユ・メモリに転送するステツ
プ。 (b) 上記第１の形式のメモリ・アクセス要求に応
じて、上記メモリ・ワード・ラインに第１の状
況値を割り当てるステツプ。上記第１の状況値
は、上記第１の形式のメモリ・アクセスと異な
る第２の形式のメモリ・アクセスが可能なこと
を示し、かつ以下のステツプ(c)またはステツプ
(d)に応じて異なる状況値に設定され直される。 (c) 上記第１の形式のメモリ・アクセスののち所
定の寿命期間内に上記第２の形式のメモリ・ア
クセスがないときに、上記メモリ・ワード・ラ
インに第２の状況値を割り当てるステツプ。上
記第２の状況値は、上記第１の形式のメモリ・
アクセスのみが可能なことを示す。 (d) 上記第１の形式のメモリ・アクセスののち上
記寿命期間内に上記第２の形式のメモリ・アク
セスがあつたときに、上記メモリ・ワード・ラ
インに第３の状況値を割り当てるステツプ。上
記第３の状況値は、上記第２の形式のメモリ・
アクセスが可能なことを示す。２第１のプロセツサ、第２のプロセツサ、なら
びにこれら第１のプロセツサおよび第２のプロセ
ツサにそれぞれ設けられた第１のキヤツシユ・メ
モリおよび第２のキヤツシユ・メモリを含むデー
タ処理装置において、上記第１のプロセツサのキ
ヤツシユ・メモリになく、上記第２のプロセツサ
のキヤツシユ・メモリにあるデータに対して、上
記第１のプロセツサが第１の形式のメモリ・アク
セスを行う際に、つぎのステツプを実行すること
を特徴とするキヤツシユ・メモリ制御方法。 (a) 上記データを上記第２のキヤツシユ・メモリ
から上記第１のキヤツシユ・メモリにコピーす
るステツプ。 (b) 上記第１のキヤツシユ・メモリの上記コピー
されたデータに第１の一時的状況値を割り当
て、かつ上記第２のキヤツシユ・メモリの上記
データに第２の一時的状況値を割り当てるステ
ツプ。上記第１の一時的状況値は第１の形式の
メモリ・アクセスと異なる第２のメモリ・アク
セスが可能なことを示す。上記第２の一時的状
況値は上記第１の形式のメモリ・アクセスのみ
が可能なことを示す。上記第１および第２の一
時的状況値は以下のステツプ(c)またはステツプ
(d)に応じて異なる状況値に設定され直される。 (c) 上記第１の形式のメモリ・アクセスののち所
定の寿命期間内に上記第１のプロセツサが上記
データについて上記第２の形式のメモリ・アク
セスを行わないときに、上記第１のキヤツシ
ユ・メモリの上記データの状況値を、上記第１
の一時的状況値から第１の確定状況値に変更
し、かつ上記第２のキヤツシユ・メモリの上記
データの状況値も、上記第２の一時的状況値か
ら上記第１の確定状況値に変更するステツプ。
上記第１の確定状況値は、上記第１の形式のメ
モリ・アクセスのみが可能なことを示す。 (d) 上記第１の形式のメモリ・アクセスののち上
記寿命期間内に上記第１のプロセツサが上記デ
ータについて上記第２の形式のメモリ・アクセ
スを行つたときに、上記第１のキヤツシユ・メ
モリの上記データの状況値を、上記第１の一時
的状況値から第２の確定状況値に変更し、上記
第２のキヤツシユ・メモリの上記データの状況
値を、上記第２の一時的状況値から第３の確定
状況値に変更するステツプ。上記第２の確定状
況値は、上記第２の形式のメモリ・アクセスが
可能なことを示す。上記第３の確定状況値は、
上記データが無効であることを示す。３複数のプロセツサ、主メモリおよび上記複数
のプロセツサのそれぞれに設けられたキヤツシ
ユ・メモリを含み、さらに、各プロセツサが、対
応するキヤツシユ・メモリにおいて見つからない
データをアクセスするために以下の手段を有する
ことを特徴とするマルチプロセツサ・コンピユー
タ・システム。 (a) 当該プロセツサによる第１の形式のメモリ・
アクセス要求に応じて、上記データを含むメモ
リ・ワード・ラインを、主メモリまたは他のプ
ロセツサのキヤツシユ・メモリから、当該プロ
セツサのキヤツシユ・メモリに転送する手段。 (b) 上記第１の形式のメモリ・アクセス要求に応
じて、上記メモリ・ワード・ラインに第１の状
況値を割り当てる手段。上記第１の状況値は、
上記第１の形式のメモリ・アクセスと異なる第
２の形式のメモリ・アクセスが可能なことを示
し、かつ以下の手段(c)または手段(d)によつて異
なる状況値に設定され直される。 (c) 上記第１の形式のメモリ・アクセスののち所
定の寿命期間内に上記第２の形式のメモリ・ア
クセスがないときに、上記メモリ・ワード・ラ
インに第２の状況値を割り当てる手段。上記第
２の状況値は、上記第１の形式のメモリ・アク
セスのみが可能なことを示す。 (d) 上記第１の形式のメモリ・アクセスののち上
記寿命期間内に上記第２の形式のメモリ・アク
セスがあつたときに、上記メモリ・ワード・ラ
インに第３の状況値を割り当てる手段。上記第
３の状況値は、上記第２の形式のメモリ・アク
セスが可能なことを示す。