JPH0561664B2

JPH0561664B2 -

Info

Publication number: JPH0561664B2
Application number: JP2037533A
Authority: JP
Inventors: Ryu Rishiingu
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1989-02-22
Filing date: 1990-02-20
Publication date: 1993-09-06
Also published as: EP0384102A3; JPH02247751A; EP0384102A2

Description

【発明の詳細な説明】Ａ産業上の利用分野本発明は、一般に多重プロセツサ（MP）デー
タ処理システム内のキヤツシユ・メモリの制御に
関し、具体的には多重プロセツサ・キヤツシユに
おける排他性（EX）の大粒度（large
granularity）ロツキングの実施に関する。

Ｂ従来の技術別々のプロセツサで並列に実行できる動作を並
列に実行してスループツトを増加させる、高性能
MPコンピユータ・システムが開発されている。
このような高性能MPコンピユータ・システム
は、多数の中央演算処理装置（CP）が独立かつ
並列に動作し、しかもデータを交換する必要があ
る時は相互間でまたは主記憶装置（MS）との間
で時々通信することが、その特徴である。各CP
及びMSは、入出力ポートを備え、それらのポー
トはデータを交換できるように相互に接続され
る。

緊密結合多重プロセツサ・システムと呼ばれ
る、各CPがそれぞれキヤツシユを有するタイプ
のMPシステムでは、システムの様々なレベル
で、整合性の問題が生じる。具体的には、記憶階
層の隣り合つたレベル間で不整合が生じることが
ある。たとえば、CPの１つがそのデータのコピ
ーを修正したために、多数のキヤツシユが所有す
る同じデータのバージヨンが異なることがあり得
る。したがつて、各プロセツサのキヤツシユが、
同時にいくつかのキヤツシユに入つている行に起
こつたかを知る必要がある。多数のCPが同じ主
記憶装置を共用するMPシステムでは、各CPが、
アクセスが発行されるときのアーキテクチヤ仕様
に応じて、最も最適に更新されたバージヨンのデ
ータを獲得する必要がある。この要件から、キヤ
ツシユ間でのデータの整合性を常に監視すること
が必要となる。

このキヤツシユ整合性の問題に対して、いくつ
かの解決方法が提案されている。早期の解決方法
は、C.K.タング（Tang）の論文「緊密結合多重
プロセツサ・システムにおけるキヤツシユ・シス
テムの設計（Cache System Design in the
Tightly Coupled Multiprocessor System）」、
Proceedings of the AFIPS（1976年）、及びL.M.
サンシエ（Censier）とP.フオートリエ
（Feautrier）の論文「多重キヤツシユ・システム
における整合性の問題の新しい解決策（Ａ
New Solution to Coherence Problems in
Multicache Systems）」、IEEE Transactions
on Computers、1978年12日号、pp.1112−1118に
記載されている。サンシエ等は、集中大域アクセ
ス許可テーブルを使用する、多重キヤツシユ内で
共用書込み可能データが存在できる体系を記載し
ている。しかし、前記著者等はその結論部分で、
２年前にはタング等が記載したのと類似の方法を
知つていなかつたことを認めている。タングは、
キヤツシユのコピー・デイレクトリを使つて状況
を維持することを提唱したが、サンシエ等は同様
の状況ビツトで各メモリ・ブロツクをタグ付けす
ることを提唱した。

こうした早期の手法は、必要なとき相互問合せ
（XI）を実施するためにどのように記帳を行なう
べきかに関するものである。その考え方は、どの
プロセツサ・キヤツシユがある行のコピーを所有
するか、及びどのキヤツシユがその行を修正した
かに関する情報を大域デイレクトリ（コピーまた
はメモリ・タグ）に記録するというものであつ
た。基本動作は、プロセツサがある行に記憶する
とき、大域テーブルに（MODIFIEDビツトで）
状況を記録させることである。ストア・イン型キ
ヤツシユが使われるので、プロセツサ・キヤツシ
ユ制御装置は、そのキヤツシユ・デイレクトリか
らどの行が修正されているかそれとも専用である
かを知る。プロセツサの未修正の行に記憶するに
は、記憶制御装置との同期、及びまず
MODIFIED状況を獲得することが必要である。
したがつて、プロセツサが実際にそれへの記憶を
発行したのでない限り、キヤツシユがシステム内
にその行のコピーだけを有する時でも、記憶ブロ
ツクはそのプロセツサに対して排他的または修正
可能となり得ない。

米国特許第4394731号明細書に記載されている
ような、より一般的な意味でのEX状況を用いる
と、その行がキヤツシユに記憶されたことがない
時でも、記憶制御要素（SCE）にアドレスせず
に、プロセツサがキヤツシユに記憶することが可
能になる。これは些細な違いがあるが、たとえば
IBM／3081システムで、後続の記憶が到来「し
そうな」時にあるプロセツサである行のEX状況
を獲得することができるので、概念上かなり重要
である。

従来技術のMPシステムでは、様々なタイプの
キヤツシユがある。１つのタイプのキヤツシユ
は、IBMシステム／370 3033型MPについて米国
特許第4142234号明細書に記載されているような、
ストア・スルー（ST）型キヤツシユである。ST
キヤツシユの設計は、主記憶装置に対するデータ
の変更を常に更新するため、CPがデータを主記
憶装置に直接記憶することを妨げない。主記憶装
置へのストア・スルーの更新時に、適切な相互問
合せ（XI）処置を行なつて、記憶された行の遠
隔コピーを無効にすることができる。記憶制御要
素（SCE）が適切な記憶スタツクを維持して、主
記憶装置（MS）記憶要求を待ち行列に入れ、バ
ツフア制御要素（BCE）とSCEの間の標準の通
信により、記憶スタツクのふれ状態が回避され
る。SCE記憶スタツクが満杯になると、その状態
がクリアされるまで、関連するBCEはそのMS記
憶を保持する。

もう１つのタイプのキヤツシユ設計は、たとえ
ば米国特許第3735360号及び第4771137号明細書に
記載されているような、ストア・イン型キヤツシ
ユ（SIC）である。SICキヤツシユ・デイレクト
リは、前掲の米国特許第4394731号明細書に詳し
く記載されている。上記特許では、ストア・イン
型キヤツシユ内の各行が、その多重プロセツサ制
御可能性を排他的／読取専用（EX／RO）フラ
グ・ビツトによつて制御される。STキヤツシユ
とSICキヤツシユの主な違いは、SIC内のすべて
の記憶がキヤツシユ自体に向けられ（そのため、
記憶された行がそのSICキヤツシユにない場合は
キヤツシユ・ミスになることがあ）ることであ
る。また、米国特許第4503497号明細書では、遠
隔キヤツシユにコピーがある場合、取出しミス時
にキヤツシユ間転送（CTC）バスを介してデー
タ転送が行なえることが提唱されている。各キヤ
ツシユ内のデイレクトリのコピーを含むSCEが使
用される。そのため、相互問合せ（XI）判断を
SCEで下すことが可能となる。通常、キヤツシユ
行の修正は、それらの行がそのキヤツシユから置
換される時だけ、主記憶装置に対して更新され
る。

通常の相互間合せ（XI）法では、ブロツクＢ
がCP Piに関してEXにロツクされているとき、
遠隔キヤツシユ内のブロツクＢでカバーされる既
存の第１段の各行に無効にされる。ブロツク・サ
イズが第１レベルの行のサイズよりも大きい時
は、しばしば冗長XI無効化が生じる。すなわち、
行は他のCPで修行されずに無効にされる。ブロ
ツク・サイズが行のサイズよりもずつと大きい
（たとえば、16倍）時は、余分のキヤツシユ・ミ
スとデイレクトリ操作とによるオーバヘツドが許
容できないほどになる。

実験によれば、取出しについても記憶について
も、著しい空間的局在性が認められている。粒度
のより大きなブロツクでEXのロツキングを行な
うと、非EX記憶の率を著しく低下させることが
できる。したがつて、上記の性能上のオーバヘツ
ドを生じることなく、大粒度のEXロツクを行な
えることは価値がある。

Ｃ発明が解決しようとする課題本発明の目的は、多重プロセツサ・キヤツシユ
において大粒度の排他性ロツクを行なうための実
施態様を提供することにある。

Ｄ課題を解決するための手段本発明によれば、ブロツクＢの若干の行がまだ
キヤツシユ中に存在していたとしても、他の中央
演算処理装置（CP）にブロツクＢ上で一時的無
効（TI）状態を与えることにより、プロセツサ
Piのアクセス権が主張（enforce）される。CPが
TI状態のブロツクにアクセスしようと試みるに
は、記憶制御要素（SCE）にアドレスして、その
ブロツクに対する適切な許可（たとえば、RO状
態またはEX状態）を得る必要がある。CPがブロ
ツクＢ上で一時的無効状態TI_Bと読取り専用状態
RO_Bと独占状態EX_Bの３つの状態を持つことがで
きると仮定すると、一時的無効状態TI_Bが、すべ
てのCPにあるすべてのブロツクＢの初期状態と
なる。本発明に基づく大粒度のロツク機構の基本
的動作は、次の通りである。

(1) プロセツサPiがブロツクＢの行Ｌに記憶し、
PiがEX_B状態を取らない場合、バツフア制御要
素（BCE）はSCEからEX_B状態を要求すべきで
ある。PiがEX_B状態を得て以降にそれがＬへの
最初の記憶がある場合、SCEは遠隔キヤツシユ
からの行Ｌに対するXI無効化信号をやり取り
する。このXI無効化は、SCEがPiにEX_Bを与
える時にも行なわれる。記憶を意図した取出し
要求も同様に処理される。

(2) プロセツサPiがＢ中のTI_B状態のデータを取
り出す時、BCEは、キヤツシユ・ヒツトの場
合でもアクセスする前にSCEからRO_B状態を要
求する。

(3) SCEがプロセツサPiからEX_B要求を受け取る
時、SCEはPiにEX_Bを与える前に、すべての遠
隔CPにTI_B状態を通知する。遠隔CP Pj（ｊ≠
ｉ）がたまたまEX_B状態をとつている場合、
SCEは、プロセツサPiにEX_B要求を許可する前
に、プロセツサPjがTI_B状態を得たことを確認
する。

(4) SCEがプロセツサPiからRO_B要求を受け取る
と、どの遠隔CPもEX_B状態をとつていない場
合、SCEはその要求をただちに許可する。そう
でない場合は、SCEは、CP PjがそのEX_B状態
をRO_B状態に変えたことを確認した後で始めて
その要求を許可する。

(1)から、ある行がキヤツシユからXI無効化さ
れるのは、その行が実際に遠隔で修正される時で
あることがわかる。その結果、本発明による過程
は、過剰の無効化によるオーバヘツドがない。こ
のことは容易に理解できる。SCEで、EX状態に
（たとえばプロセツサPiに対してロツクされてい
るブロツクＢのそれぞれについて、ビツト・ベク
トルCH（局所変更）が維持されるのは、プロセ
ツサPiに最後にEX_B状態が許可されて以降にこれ
がPiによつて実際に記憶されるときである。CH
ビツトは、PiがEX_B状態を得た時、０ビツトに初
期設定される。ブロツクＢの行Ｌの記憶をSCEが
受け取ると、次の動作が行なわれる。Ｌに関連す
るCHビツトがオフの場合、SCEは遠隔キヤツシ
ユにXI無効化信号を送出する。次いで、Ｌに対
するCHビツトがオンになる。

本発明の好ましい実施例による大粒度ロツク方
式の実施態様で重要なフアクタは、CPに対する
ブロツクの状態をSCE及びBCEに記録すること
である。SCEでは、ロツク・テーブル｛Ti｜１
≦ｉ≦ｋ｝；と仮定されている。すなわち、SCE
はEX状態の所有権（ownership）だけを記録す
る。

Ｅ実施例ここで図面、特に第１図を参照すると、本発明
が適用できるタイプの多重プロセツサ（MP）シ
ステムの構成図が示されている。MPシステムは
４台の中央演算処理装置（CP₀，CP₁，CP₂，
CP₃）１０，１１，１２，１３を含み、各CPは
それぞれ命令実行（IE）ユニツト１４，１５，
１６，１７とバツフア制御ユニツト（BCE）２
０，２１，２２，２３を含んでいる。各IEユニ
ツトは、主記憶装置（MS）５０からのオペラン
ドの取出し及びMSへのオペランドの記憶を要求
する命令を出す、ハードウエアとマイクロコード
を含んでいる。

IEユニツト１４ないし１７は、当該のキヤツ
シユ制御ユニツト２０ないし２３に取出しコマン
ドまたは記憶コマンドを出すことによつて、取出
し動作または記憶動作を開始する。各BCEは、
プロセツサ・ストア・スルー型（ST）キヤツシ
ユとそれに関連するプロセツサ・キヤツシユ・デ
イレクトリ（PD）、及び関連するCP１０ないし
１３が独占使用するすべてのプロセツサ・キヤツ
シユ制御機構を含んでいる。CPは一般にあるオ
ペランドが必要とする各ダブルワード（DW）単
位ごとに取出しコマンドまたは記憶コマンドを発
行する。そのDWを含むキヤツシユ・ヒツトのキ
ヤツシユ行がPD内にある場合、そのコマンドに
従つてそのDWがキヤツシユ中で取り出されまた
は記憶される。キヤツシユ中でのオペランド取出
しヒツトの場合は、BCEから外に出る必要なく、
記憶装置アクセスが完了する。時には、必要な
DWがキヤツシユ内になく、キヤツシユ・ミスと
なることもある。IE取出しコマンドまたは記憶
コマンドが完了できるには、その前に主記憶装置
からDWを取り出さなければならない。そうする
ため、BCEは対応する取出しミスまたは記憶ミ
ス・コマンドを生成して、記憶制御要素（SCE）
３０に、IEユニツトが必要とするDWをもつ行単
位のデータを主記憶装置５０から得ることを要求
する。その行単位は主記憶装置５０内の行境界上
にくるが、必要なDWは、失販した行転送の完了
前にIE要求が向かうようにするために要求側
BCEに戻すべき、取り出された行中の最初のDW
となる。

SCE３０は、CP１０ないし１３と主記憶装置
５０に接続されている。主記憶装置５０は、複数
の基本記録モジユール（BSM）制御装置BSC₀，
BSC₁，BSC₂，BSC₃それぞれ５１，５２，５３，
５４から構成され、各基本記憶制御装置は２つの
BSM０，６０，６２，６４，６６と１，６１，
６３，６５，６７に接続されている。４つの
BSC５１ないし５４は、それぞれSCE３０に接
続されている。

従来のシステムでは、SCE３０は４つのコピ
ー・デイレクトリ（CD）３１，３２，３３，３
４を含み、各CDは、米国特許第4394731号明細書
に記載されているのと同様の方式で、１つの
BCE中の対応するプロセツサ・キヤツシユ・デ
イレクトリ（PD）の内容のイメージを含んでい
る。下記の説明から明らかになるように、本発明
は、他のデイレクトリで行存在情報を記憶するこ
とによつてXI無効化の量をさらに減少させるこ
とが可能なものの、CDを使用する必要はない。

主記憶装置の各BSM６０〜６７と対応する
SCEポートの間、及びSCEポートから入出力チヤ
ネル・プロセツサ４０及び対応する各CP１０〜
１３への間に、ダブルワード幅両方向データ・バ
スが設けてある。データ・バスと共に、制御信号
及びアドレス信号用の別々の数組のコマンド・バ
スもある。CPがDWアクセス要求に対するキヤ
ツシユ・ミスに出会うと、そのBCEは、SCE３
０にミス・コマンドを送ることにより、主記憶装
置に対する行アクセス要求を開始し、次いでSCE
３０は主記憶装置内の要求さたBSMにそのコマ
ンドを再発行する。BSM使用中状態の場合、
SCE３０はその要求をコマンド待ち行列にセーブ
し、後で要求されたBSM６０〜６７が利用可能
になつたときにそれを再発行する。SCE３０はま
た、そのXI論理回路によつてキヤツシユ衝突が
検出された場合以外は、特定のBSMに対するす
べてのコマンドが先入れ先出し（FIFO）方式で
発行されるように、主記憶装置コマンドを規則的
に順序づける。主記憶装置要求の正常な取扱いシ
ーケンスの間、SCE３０は主記憶装置の状況を絶
えず監視し、保護キー及び全キヤツシユ・デイレ
クトリの問合せ結果を分析し、現在SCE３０に保
持されている未処理のすべてのコマンドの更新済
み状況を検査し、またBCE２０〜２３中でSCE
３０による受領を持つている新しいBCEコマン
ドがあるかどうか調べる。

SCE３０は、複数の記憶スタツク（SS₀，SS₁，
SS₂，SS₃）３５，３６，３７，３８を維持する。
各記憶スタツクは、対応するCPに対する最大
16DWまでの主記憶装置記憶要求を保持すること
ができる。SCE３０は、それらの記憶スタツクに
対して、主記憶装置アドレス及び有効性を示すの
に十分なデイレクトリ情報を保持する。記憶スタ
ツクがオーバフローする危険が生じると、SCE３
０は、BCEが後でSCE３０から記憶スタツク満
杯状態をクリアする信号を受け取るまで、記憶要
求の送出を保留するようにとの優先順位信号を関
連するBCE２０〜２３に送る。記憶スタツク中
のデータは、主記憶装置に合わせて更新され、適
切なスケジユーリングによつて各記憶スタツク内
の着信順序が維持される。CPからの行取出し要
求は、記憶スタツク中のその行に対する既存の記
憶がすべて関連するBSM６０〜６７に送られた
ことをSCEが確認するまで、SCE３０によつて保
持される。

キヤツシユ・デイレクトリ項目にEX状態を記
録する従来の方法は、コストが非常に高くつくこ
とがある。たとえば、32Kの項目を含む第２段キ
ヤツシユを考えてみる。SCEがEX状況に対する
第２段項目１個当たり３ビツトを維持するものと
すると、100Kビツト＋第１段デイレクトリで必
要なビツトが必要となる。第２図に示すような比
較的小さなロツク・テーブルT₁〜T_oを使つて、
こうした回路コストを削減することが可能であ
る。第２図のMPシステムでは、各プロセツサPi
｛Pi｜１≦ｉ≦ｎ｝について、SCEはロツク・テ
ーブルTiを維持する。ロツク・テーブルは通常、
アドレスによつてインデツクス（またはハツシ
ユ）されるセツト連想式テーブルとして構成さ
れ、また単純な先入れ先出し（FIFO）スタツク
として実施することもできる。第３図に一般的に
示すように、Tiの各項目ごとに、ブロツクＢの
アドレスを記憶するIDフイールド（及び適切な
妥当性タグ）がある。SCEはまた、ロツク・テー
ブルに対する置換操作のために必要な状況アレイ
を維持する。ロツク・テーブルTiの各項目は、
プロセツサPiに対するあるブロツクのEXロツク
を表す。ロツク・テーブルの全項目は最初無効で
ある。ブロツク・サイズｂは必ずしも第１段キヤ
ツシユまたは第２段キヤツシユの行のサイズと同
じである必要はないが、通常は第１段キヤツシユ
行のサイズの整数倍である。

CPからの各記憶をSCEと同期させる必要のあ
る、典型的なSTキヤツシユ用のSCEにある記憶
同期化機構について考えてみる。SCEでの基本動
作は下記の通りである。まず、プロセツサPiから
の（ブロツクＢ上の）記憶同期化要求のSCEによ
る処理について考察する。

（a.1）ブロツクＢがロツク・テーブルTi中で
ヒツトしたときは、プロセツサPiにただちに記
憶同期化が許可される。

（a.2）どのロツク・テーブルにもブロツクＢ
がないときは、SCEはロツク・テーブルTi中
にＢに対する新しい項目を作成し、プロセツサ
Piに記憶同期化を許可する。上記処理と並列し
て、SCEはまた遠隔キヤツシユ内のＢをXI無
効化させる信号を（ブロツクＢのデータを含む
可能性のあるCPに）送り出す。

（a.3）ブロツクＢがロツク・テーブルTj（ｊ≠
ｉ）にヒツトしたときは、SCEでの遠隔EXヒ
ツトと類似している。この場合は、ブロツクＢ
の項目がロツク・テーブルTjから削除され、
ロツク・テーブルTiに新しい項目が作成され
（XI無効化信号がプロセツサPjに送られ）る。

次に、SCEがプロセツサPiからのブロツクＢ
中の行に対する取出し要求（たとえば第１段キ
ヤツシユ・ミス）を受け取つた時の動作につい
て考察する。

（a.4）ブロツクＢが遠隔CPによつてEXロツ
クされないときは、その取出しは遅延なしで開
始できる。

（a.5）ブロツクＢがロツク・テーブルTj（ｊ≠
ｉ）にヒツトしたときは、ロツク・テーブル
Tjから最初にブロツクＢの項目が無効にされ
る。

ストアスルー型キヤツシユ設計では、記憶スタ
ツク内の未処理の行への記憶なしに、行（ミス）
取出しが実行されることが重要である。SCEによ
るこの種の検査が必要なのは、行取出し要求を受
け取つた時である。

上記の諸ステツプのうちで、（a.1）は、異なる
CPからの複数の記憶について並列して行なうこ
とができる。他のステツプの実行時にSCEで適切
な直列化が必要となる場合もあるが、そのために
同一サイクルで複数の記憶同期化要求を実行する
可能性が排除されることはない。ロツキング粒度
ｂが大きくなる（たとえば4K）とき、ステツプ
（a.2）及び（a.3）からのXI無効化によつて重大
な第１段キヤツシユ・ミスが生じる。

上記の重大なXI無効化は、S_Bビツト・ベクト
ルを用いて、同じ行に対する連続した無効化を排
除することにより、大幅に減少させることができ
る。そのフオーマツトを第４図に示す。このベク
トルは無効化同報通信用のBIAS（バツフア無効
化アドレス・スタツク）様フイルタとして使用さ
れる。このベクトルの各ビツトは、ブロツクＢの
複数の（たとえば２）行を表すことができ、その
場合、各XI信号は関連する各遠隔キヤツシユ内
の複数の行を無効にすることができる。ビツト・
ベクトルでフイルタリングを行なう場合、たとえ
ばロツク・テーブルTiにある関連するビツト・
ベクトルが、プロセツサPiの要求に応じて関連す
る行に対して以前に記憶が行われたことを示さな
い時に、キヤツシユ「行」無効化が遠隔BCEに
送られるように、ステツプ（a.1）を修正するこ
とができる。

第５図及び第６図は、こうしたビツト・ベクト
ルに基づくSCE無効化フイルタリングのための論
理を図示した流れ図である。処理は第５図から始
まり、機能ブロツク７０で、ブロツクＢに対する
新しい項目がロツク・テーブルTiに挿入される。
そうなつた時、機能ブロツク７２で、挿入された
項目のビツト・ベクトルのすべてのS_Bビツトがゼ
ロにリセツトされる。次に、第６図に関連して、
機能ブロツク７４で、SCEはプロセツサPiからブ
ロツクＢに対する記憶要求を受け取る。判断ブロ
ツク７６でテストを行なつて、ロツク・テーブル
Ti中のブロツクＢの項目にあるビツト・ベクト
ルの関連する記憶対象とされた行に対応するS_Bビ
ツトが１かどうか判定する。１である場合は、機
能ブロツク７８で、その記憶要求が処理される。
そうでない場合は、機能ブロツク８０で、SCEは
遠隔中央演算処理装置に行無効化信号を送り出
す。次いで、機能ブロツク８２で、SCEは関連す
るS_Bビツトを１にし、その記憶要求を処理する。

上記のロツクアツプ機構は、前掲の米国特許第
4142234号明細書に記載されている、 IBM3033MPシステムで使用されているバツフア
無効化アドレス・スタツク（BIAS）フイルタ・
メモリ法とは異なつている。BIASそれ自体は、
BCEが受け取る無効化信号のスタツクにすぎな
い。BIASフイルタ・メモリ方式では、SCEは、
各プロセツサPiごとに、プロセツサPiから最近に
無効にされたブロツクを再取出しなしで記録する
テーブルIiを維持する。プロセツサPiからの各記
憶要求を、同時にテーブルIj（ｊ≠ｉ）中のすべ
ての項目と突き合わせて、XI無効化の可能性が
あるかどうか検査する必要がある。プロセツサの
数が増すにつれて、この同時検査は重い負担にな
る。ロツク・テーブル法では、大部分の記憶は
CP Piに関連するロツク・テーブルTiにヒツト
し、したがつて、SCE処理の並列度がずつと高く
なる。さらに、任意の時点で、最近に記憶された
ブロツクIDは、BIASフイルタ・メモリ法では大
部分の遠隔テーブルIj中に存在する。ロツク・テ
ーブルTjは、当該の各CPからの最近の記憶だけ
を記録し、（無効の項目以外は）互いにばらばら
である。その結果、ロツク・テーブルTjは回路
をより有効に利用できる。

パイプライン化がずつと進む将来のプロセツサ
では、記憶同期化の遅延が、パイプラインの性能
をかなり損なうことがあり得る。したがつて、
SCEに対する記憶同期化の頻度が低下するよう
に、BCEレベルで適切なEXロツクを行なうのが
好都合である。上記のSCEロツクアツプ設計で
は、ロツク・テーブルTiにロツクされたブロツ
クは、実際には、それが（ｊ≠ｉのPjに対する）
どの遠隔キヤツシユにも存在できないことを意味
する。こうしたロツキング情報がBCEに渡され
る場合、局所的にロツクされたブロツクへの記憶
のためのSCEとの初期接続手順をなくすことが可
能である。第７図で、局所ロツク・テーブルLiが
各プロセツサPiごとにBCEによつて維持される。
局所ロツク・テーブルLiの各項目は、プロセツサ
PiによつてEXにロツクされるブロツクのIDを記
録する。通常、局所ロツク・テーブルLiの項目は
ロツク・テーブルTiの項目よりも少ない。記憶
及びロツクのための動作は次の通りである。

（b.1）局所ロツク・テーブルLi中の全項目が、
最初は無効である。

（b.2）プロセツサPiからの記憶要求に対して、
局所ロツク・テーブルLi中でロツクされたブロ
ツクＢにヒツトした時は、その記憶は遅延なし
に実行できる。

（b.3）プロセツサPiからのブロツクＢに対す
る記憶が、局所ロツク・テーブル中でミスした
時は、BCEはSCEに同期化要求を送る。SCE
から許可信号を受け取ると、ブロツクＢに対す
る有効項目が局所ロツク・テーブルLi中で作成
される。

（b.4）プロセツサPiがSCEからブロツクＢに
対する解除要求を受け取つた時は、局所ロツ
ク・テーブルLiからブロツクＢの項目が見つか
つた場合、プロセツサPiのBCEがその項目を
無効にする。次いで、肯定応答信号がSCEに送
られる。

BCEに関しては、通常の（非EX型）取出し
に特別の取扱いは必要でない。SCEに関して、
主要な違いの１つは、遠隔EXヒツトの取扱い
にある。プロセツサPiからブロツクＢへのアク
セスがロツク・テーブルTj（ｊ≠１）にヒツト
するという状況を考察する。

（b.5）ブロツクＢが局所ロツク・テーブルLj
中でロツクされている可能性がある場合、SCE
はプロセツサPjに、ブロツクＢに対するEXロ
ツクを解除するように指示する信号を送る（ロ
ツク・テーブルTjは、局所ロツク・テーブル
Ljより多くのロツク項目をもつことを妨げられ
ない）。この信号は、（たとえば、プロセツサPi
からのアクセスがEX状況に対するものである
時に）適当なXI無効化要求と結合されること
がある。SCEは、プロセツサPjから肯定応答信
号を受け取つて始めて、このXI動作を完了す
る（ステツプ（b.4）参照）。

局所ロツク・テーブルLi内のロツク情報を、ロ
ツク・テーブルTi内のロツク情報のサブセツト
にすることが望ましい。第８図に示すような余分
のＬビツトをTiテーブル項目１つにつき１個ず
つ追加することによつて、SCEは、SCE EXロツ
ク・テーブルTi内のあるブロツクが対応する
BCE局所ロツク・テーブルLi中にあるか否かを
検出することができる。しかし、局所ロツク・テ
ーブルLiとロツク・テーブルTiが同じサイズの
場合は、そうする必要はなく、ロツク・テーブル
Tiからある項目が削除された時に、局所ロツ
ク・テーブルLi中にそれに対応するブロツクが存
在しないように保証するだけで十分である。ロツ
ク・テーブルTiの項目がテーブルTiから削除さ
れる理由としては、相互問合せと局所要求による
置換の２つが考えられる。XI処理（たとえば上
記のステツプ（b.5））は、このサブセツト則を適
切に維持する。局所置換の場合、ロツク・テーブ
ルTiから項目が置換される理由としては、プロ
セツサPiからEX要求しかないことは明らかであ
る。以上の議論は、通常のXI無効化法を前提と
したものである。すなわち、ブロツクＢがプロセ
ツサPiからEXにロツクされるとき、遠隔キヤツ
シユ内のブロツクＢでカバーされる既存の第１段
キヤツシユ行は無効になる。そのブロツク・サイ
ズが第１段ブロツク・サイズより大きい時は、そ
の結果しばしば冗長XI無効化が生じる（すなわ
ち、行が別のCPで修正されないのに無効にな
る。）ブロツク・サイズが行のサイズよりずつと
大きい（たとえば、16倍）時は、余分のキヤツシ
ユ・ミス及びデイレクトリ処理によるオーバヘツ
ドは許容できないものになる。

実験から、取出しについても記憶についても、
大きな空間的局在性が観察されている。より大き
な粒度のブロツクでEXロツツクを実行する時、
非EX記憶の速度が著しく低下する可能性がある。
したがつて、上記の性能上のオーバヘツドを生じ
ずに大粒度のEXロツクが実行できれば価値があ
る。以下の説明では、話を簡単にするため、排他
的ロツクの粒度を、多重プロセツサ・システムに
おいて各キヤツシユ行当たり128バイトの4Kブロ
ツクで例示する。こうした場合、各ブロツクに32
行あることになる。ただし、これらの数字は例と
して示したものにすぎず、本発明の実施に際し
て、異なるサイズのブロツク、行、キヤツシユも
使用できることを了解されたい。また、この説明
では、SCEがシステム中の複数のプロセツサそれ
ぞれにより記憶ブロツクの排他的（EX）所有権
を記録する、ストア・スルー型（ST）キヤツシ
ユ設計であると仮定する。また、各中央演算処理
装置（CP）に、ブロツク情報を記録するための
デイレクトリD_Pがあるものと仮定する。デイレ
クトリD_P内のブロツクＢに対する各項目には、
少なくとも概念上、排他的EX_B、一時無効TI_B、
読取り専用RO_Bの３つの状態がある。実際には、
システムは、容量が限られているEXロツク・テ
ーブルによつて各プロセツサごとにEX状態とTI
状態だけを明示的に維持している。BCEは、ブ
ロツクＢがTIまたはEXではないことを検出した
時は、単にそのブロツクをROとして扱う。した
がつて、デイレクトリD_Pは、TI状態とEX状態を
記録するものと見なせる。ある実施態様では、
INV_B状態も使用されることがある。

BCEが許可情報を獲得する方法の１つは、
SCEからすべてのCPのEXロツク情報を複製する
ものである。プロセツサPiは、別のCPがEX_B状
態をとるとき、TI_B状態をとる。プロセツサPiの
BCEで維持されている｛Lj｜１≦ｊ≦Ｋ｝のコ
ピーを｛Lj(i)｜１≦ｊ≦Ｋ｝で示すことにする。
プロセツサPiでは、ロツク・テーブルLi(i)が前記
の局所ロツク・テーブルとして機能する。プロセ
ツサPiで、ブロツクＢがテーブルLi(i)で見つかつ
た場合は、ブロツクＢはEX_B状態であり、ロツ
ク・テーブルLj(i)（ｊ≠ｉ）で見つかつた場合は
TI_B状態であり、その他の場合はRO_B状態である。
プロセツサPiがTI_B状態からRO_B状態またはEX_B
状態に切り替わると、BCEは、ロツク・テーブ
ルLj(i)（ｊ≠ｉ）に記録されている以前の遠隔
EX_B状態を無効にしなければならない。SCEは、
プロセツサPiにEX_B状態を与える時、やはり局所
ロツク・テーブルLi中のブロツクＢの項目の座標
を送ることによつて、各プロセツサPj（ｊ≠ｉ）
にTi_B状態をとるようにとの信号を送る。TI_B信
号を受け取ると、プロセツサPjのBCEは、ロツ
ク・テーブルLi(j)の指定された座標にその状況を
記録する。プロセツサPjが、プロセツサPi（ｉ≠
ｊ）からのRO_B要求によつてそのEX_B状態を放棄
し（RO_B状態になる）時、SCEがその状態変化を
他のCPに通知するのが有用であるが、必ずしも
必要ではない。

本発明の別の実施例では、「局所」ロツク・テ
ーブルLj(i)はSCEでテーブルTj(i)として維持す
ることができる。ただし、TiテーブルをLiテー
ブルよりもずつと大きくすると、性能及び設計上
何らかの利点がある。すなわち、EX状況の解釈
が、SCEとBCEの間で異なることがあり得る。
テーブルLiはテーブルTiのサブセツトとして維
持されるので、EX状況が局所ロツク・テーブル
Liに記録されている限り、SCEもBCEもEX状況
を理解するはずである。しかし、実施態様によつ
ては、BCEがロツク・テーブルTiの情報をすべ
て知つている必要はない。このより大きなTiテ
ーブルをSCEが使つてBCにEX状況を許可する際
の並列性を高め、状況、たとえば無効化フイルタ
リング用のS_Bビツト・ベクトルを記録する。

局所ロツク・テーブルLiに記録されたEX状況
は、相互問合せ（XI）活動の対象となる唯一の
項目である。ロツク・テーブルTiは、本質上
SCEの記帳用のものにすぎない。アーキテクチヤ
の整合性は、プロセツサ及び入出力チヤンネルか
らの記憶装置へのアクセスに対してのみ維持すれ
ばよい。この場合、ブロツクＢが遠隔ロツク・テ
ーブルTjに記録されている時でも、ブロツクＢ
が遠隔BCEの局所ロツク・テーブルLjに割り当
てられていない限り、そのブロツクＢはあるプロ
セツサに対するRO状態となることができる。

本発明による処理の論理を、第９図、第１０図
及び第１１図に流れ図で示す。第９図に示したケ
ースでは、機能ブロツク８２で、SCEはプロセツ
サPiからEX_B要求を受け取る。判断ブロツク８４
でテストを行なつて、ブロツクＢがロツク・テー
ブルTiに記録されているかどうか判定する。記
録されている場合は、機能ブロツク９８に進む。
そうでない場合は、判断ブロツク８６でさらにテ
ストを行なつて、ブロツクＢが遠隔テーブルTj
（ｊ≠ｉ）に記録されているかどうか判定する。
記録されていない場合は機能ブロツク９６に進む
が、そうでない場合は、判断ブロツク８８で再度
テストを行なつて、ブロツクＢが遠隔局所ロツ
ク・テーブルLjに記録されているかどうか判定す
る。記録されている場合、SCEはプロセツサPj
に、そのロツク・テーブルLjからブロツクＢを削
除するように指示し、次いで、機能ブロツク９２
で、プロセツサPjからの肯定応答を待つ。肯定応
答を受け取つた時、あるいは判断ブロツク８８で
のテスト結果がノーの場合、機能ブロツク８４
で、SCEはロツク・テーブルTjからブロツクＢ
を削除する。ブロツクＢが削除された時、あるい
は判断ブロツク８６でのテスト結果がノーの場
合、機能ブロツク９６で、SCEはブロツクＢに対
する新しい項目をテーブルTiに挿入する。次い
で機能ブロツク９８で、SCEは遠隔中央演算処理
装置にHOLD_B信号を送り出す。最後に機能ブロ
ツク１００で、SCEはプロセツサPiにEX_B状況を
許可するよう指示する。

第１０図に示したケースでは、機能ブロツク１
０２で、SCEはプロセツサPiからEX_B解除要求を
受け取る。それにより、機能ブロツク１０４で、
SCEはすべての遠隔プロセツサにCLEAR_B信号を
送り出す。次いで機能ブロツク１０６で、SCE
は、ブロツクＢがもはや局所ロツク・テーブルLi
に記録されていないことを示すように、ロツク・
テーブルTiにおけるブロツクＢの項目の状況を
更新する。

第１１図には、RO状況要求のケースが示され
ている。この場合、機能ブロツク１０８で、SCE
はプロセツサPiからRO_B状況要求を受け取る。判
断ブロツク１１０でテストを行なつて、ブロツク
Ｂが遠隔ロツク・テーブルTj（ｊ≠ｉ）に記録さ
れているかどうか判定する。記録されている場
合、判断ブロツク１１２でさらにテストを行なつ
て、ブロツクＢが遠隔局所ロツク・テーブルLjに
記録されているかどうか判定する。記録されてい
ない場合、SCEはロツク・テーブルTjからブロ
ツクＢの項目を削除する。ブロツクＢの項目が削
除されている時、あるいは判断ブロツク１１０で
のテスト結果がノーである場合、機能ブロツク１
１６で、SCEはプロセツサPiにRO_B状況を許可す
るよう指示する。

判断ブロツク１１２に戻ると、ブロツクＢが遠
隔局所ロツク・テーブルLjに記録されている場
合、機能ブロツク１１８で、SCEはプロセツサPj
にその局所ロツク・テーブルLjからEX_Bを解除す
るように指示する。次いで、SCEはプロセツサPj
の肯定応答を待つ。プロセツサPjから肯定応答を
受け取ると、機能ブロツク１２０で、SCEはプロ
セツサPj以外のプロセツサにCLEAR_B信号を送り
出す。プロセツサPjは、CLEAR_B信号を受け取る
と自動的にRO_B状況となる。

CP Piが（記憶のためのアクセスによつて、あ
るいはプロセツサPiがまもなくブロツクＢに記憶
すると予想される時）SCEに対してブロツクＢの
排他的制御権を要求する（CPがEX_B状況をとる
ことで示される）と、SCEは下記の適切な動作を
実行する。まず、遠隔CP、たとえばPjがその局
所ロツク・テーブルLjでEX_B状態を所有すること
をSCEが検出した場合、SCEは、プロセツサPiに
EX_Bを許可する前に、プロセツサPjがそのEX_B状
態を放棄するようにさせる。そうしないと、ただ
ちにEX_BがプロセツサPiに許可されてしまうこと
がある。次に、SCEは、そのキヤツシユにブロツ
クＢの行を所有する可能性のある遠隔CPに
HOLD_B信号を送り出す。このHOLD_B信号を受け
取つた後、遠隔CP、たとえばPjは（ロツク・テ
ーブルLi(j)にブロツクＢを記録することにより）
ブロツクＢをTI_B状態でマークする。ただし、
TI_B状態とは、ブロツクＢがそのCPに対して一時
的に無効となることを意味する。

プロセツサPiは、取出し要求によつてTI_B状態
のブロツクＢにアクセスする際、SCEはアクセス
権を求める必要がある。取出し要求は、インタク
ロツク命令からの取出し後修正要求でもよいこと
に留意されたい。SCEはEX_B状態を保持している
CPにそれを放棄させる。EX_B状態がどの遠隔CP
によつても所有されなくなつた後、SCEはプロセ
ツサPiに適切なアクセス権を許可する信号を送
る。プロセツサPiは、SCEからの許可を受け取つ
た後、TI_B状態を適当な状態、たとえばPO_Bまた
はEX_Bに変更して、ブロツクＢのデータへのアク
セスを開始する。キヤツシユ・ミス状況の場合、
SCEはある時点でプロセツサPiにその行の有効コ
ピーを転送して、プロセツサPiがアクセス権獲得
後にミスを再発行しなくてもすむようにすること
ができる。

プロセツサPiは、何らかの理由でEX_B状態を放
棄する時、その事象についてSCEに知らせる。
EX_B状態がCPから要求されていない場合、SCE
は、TI_B状態を保持している可能性のある遠隔CP
にCLEAR_B信号を送る。このCLEAR_B信号を受け
取つた後、CP、たとえばPjは、後でブロツクＢ
にアクセスできるように、Ti(j)からブロツクＢ
を削除することによつて）そのTI_B状態をクリア
する。

CP PiがEX_B状態のもとでブロツクＢ内のある
行に記憶する時、SCEは、自分のキヤツシユにそ
の行のコピーを所有している可能性のあるCPに、
XI（相互無効化）信号を同報通信する。

SCEは、CP、たとえばPiが排他的に（EX_B）
所有する各ブロツクごとに、下記の情報を維持す
ることができる。(a)どのCPがEX_B状態をとつて
いるか。これは、遠隔EXヒツト相互問合せを取
り扱うために使用される。(b)Piが最後にEX_B状態
を獲得して以降、Ｂのどの行に以前にPiによつて
記憶が行なわれたか。これは、前述のように、ビ
ツト・ベクトルS_Bを使つて実施できる。

CP Piにおいて、その局所ロツク・テーブルLi
中の（たとえばブロツクＢに対する）各項目は、
Piが最後にEX_B状態を獲得して以降、ブロツクＢ
のどの行に以前にプロセツサPiによつて記憶が行
なわれたかに関する情報を保持することができ
る。これは、SCEについて説明したのと同様のビ
ツト・ベクトルを使つて実施できる。こうしたベ
クトルが局所CPで実施されるときは、必ずしも
上記のベクトルを使用する必要はない。この実施
態様は、ストア・イン型キヤツシユ設計に最も好
都合である。

CPがそのEX_B制御権を放棄する時、SCEはた
だちに他のCPにCLEAR_B信号を送り出す必要は
ない。このため、他のCPが、後でＢを最初に参
照する際にSCEを相談できるようになる。

SCEは、EX_B状態の許可及び相互無効化の処理
を適切に直列化しなければならない。

この状態の実施には様々なビツトが使用でき
る。たとえば、TI_B状態は独立のフラグ・ビツト
を使つて実施できる。場合によつては、そうする
のが好都合である。

遠隔キヤツシユ行無効化信号の有効なフイルタ
リングを行なえることが重要である。上記のビツ
ト・ベクトル以外に他のフイルタリング手段を設
けるのが有利なことがある。上記のS_Bビツト・ベ
クトルで遠隔無効化をなくすることができない時
は、たとえば、C.K.タングが提唱したコピー・
デイレクトリ（CD）技術や、L.M.センシエ他が
提唱した存在タグが２次フイルタリング手段とし
て使用できる。局所テーブルによつて保証される
記憶のためのEX状況を用いると、データの整合
性の問題を引き起こさずに、SCEが２次フイルタ
リングの実行により多くの時間をかけることがで
きるようになる。

あらゆる記憶装置、すなわちキヤツシユに対す
るアクセスで、すべてのロツク・テーブルLj(i)を
探索するとなると、重大な性能上の問題が生じる
恐れがあるが、そのような探索の必要はない。そ
の代わりに、これらのロツク・テーブルLj(i)は、
BCEが必要とする時、バツクアツプ状況デイレ
クトリとして働くことができる。たとえば、プロ
セツサBCEは、各項目ごとに適切な状況（ROま
たはEX）を記録して、最初にアクセスされたブ
ロツクに対するデイレクトリを小さくすることが
できる。大粒度のブロツクでは、このようなデイ
レクトリに対するヒツト率は非常に高くなると予
想される。ロツク・テーブルLj(i)を探索する必要
があるのは、アクセスされたブロツクがデイレク
トリ中で見つからない時だけである。こうする
と、BCEは、大部分の時間、IE装置からの実際
の記憶装置アクセスと並列して、ロツク・テーブ
ルLj(i)に作用することができる。

Ｆ発明の効果本発明によれば、多重プロセツサ・キヤツシユ
における大粒度の排他性ロツクを、オーバヘツド
を生じさせることなしに行なうことが可能とな
る。

【図面の簡単な説明】

第１図は、本発明を適用できるプロセツサ・シ
ステムの構成図である。第２図は、第１図の多重
処理システムの、複数のプロセツサと記憶制御要
素（SCE）とを含む部分を示し、各プロセツサ用
のロツク・テーブルを図示した構成図である。第
３図は、本発明の一態様に基づくロツク・テーブ
ルのある項目のフオーマツトを示す構成図であ
る。第４図は、本発明の別の態様に基づくロツ
ク・テーブルのある項目のフオーマツトを示す構
成図である。第５図及び第６図は、S_Bビツト・ベ
クトルを用いて記憶の同期化を行なう本発明の実
施態様の論理を示す流れ図である。第７図は、プ
ロセツサにある局所ロツク・テーブルを示す、第
２図と類似の構成図である。第８図は、本発明の
別の態様に基づくロツク・テーブルのある項目の
フオーマツトを示す、第３図と類似の構成図であ
る。第９図、第１０図及び第１１図は、本発明の
実施態様の論理を示す流れ図である。１０〜１３……中央演算処理装置（CP）、１４
〜１７……命令実行（IE）ユニツト、２０〜２
３……バツフア制御ユニツト（BCE）、３０……
記憶制御要素（SCE）、３５〜３８……記憶スタ
ツク（SS）、４０……入出力チヤンネル・プロセ
ツサ、５０……主記憶装置、５１〜５４……基本
記憶モジユール制御装置（BSC）、６０〜６７…
…基本記憶モジユール（BSM）。

Claims

【特許請求の範囲】１それぞれがキヤツシユを有する多重プロセツ
サを含むデータ処理システムにおいて排他性の大
粒度ロツキングを行なう方法であつて、所与のプロセツサにキヤツシユ中の所与のブロ
ツクのデータに対する唯一のアクセス権を与える
ために、当該ブロツクをキヤツシユに含む他のプ
ロセツサにおいて当該ブロツクのデータを一時的
無効状態とすることを指示するステツプと、上記他のプロセツサが上記所与のプロセツサに
によつて唯一のアクセス権が主張されている一時
的無効状態のブロツク中のデータを取り出す時、
キヤツシユ・ヒツトの場合でも上記他のプロセツ
サが自身のキヤツシユにアクセスする前に該一時
的無効状態のブロツクに対する読取り専用アクセ
ス権を求めるステツプを含む方法。２それぞれがキヤツシユ・メモリとバツフア制
御要素を有する複数の中央演算処理装置、主記憶
装置及び記憶制御要素を有する多重プロセツサシ
ステムにおいて、キヤツシユ・メモリに記憶されたデータ・ブロ
ツクの排他性の大粒度ロツキングを行なうための
装置であつて、すべてのキヤツシユ・メモリに記憶されている
データ・ブロツクの排他的状況の記録を維持する
ための、記憶制御要素内にある上記の各プロセツ
サごとのロツク・テーーブル手段と、各バツフア制御要素内にあつて、対応するプロ
セツサによつてアクセスされるデータ・ブロツク
の排他的状況の記録のサブセツトを維持するため
の、局所ロツク・デーブル手段とを含む装置。３複数のプロセツサ、主記憶装置及び記憶制御
要素を含む緊密結合多重プロセツサ・システム用
のストア・スルー型キヤツシユ・アーキテクチヤ
において、上記プロセツサによるデータの大粒度記憶同期
化を行なうための方法であつて、下記のステツプ
を含む方法。 (a) 上記記憶制御要素内に、上記各プロセツサご
とに１つずつ、上記各プロセツサに許可された
データ・ブロツクについての排他的状態の記録
を維持するためのロツク・テーブルを設けるス
テツプ。上記各ロツク・テーブルにはビツト・ベクト
ルが含まれ、それに含まれるビツトと当該ロツ
ク・テーブルに関連するブロツクに含まれる行
とは一対一に対応する。 (b) 上記プロセツサに対して新しく排他的状態が
許可されたデータ・ブロツクに対応する項目を
関連するロツク・テーブルに新設し、かつ当該
ブロツクに対応するビツト・ベクトルのすべて
のビツトは０にリセツトする。 (c) 上記記憶制御要素が所与のプロセツサから所
与のブロツクに対する記憶を要求されたことに
応答して、下記のサブ・ステツプを実行する。（c1）上記所与のプロセツサに対応するロツ
ク・テーブルにおいて、記憶対象とされた行
に対応するビツトが１であるか否かをテスト
する。（c2）上記テストの結果が１であることに応
答して、上記要求された記憶を実行する。（c3）上記テストの結果が０であることに応
答して、上記記憶制御要素から他のプロセツ
サに対して行無効化信号を送り、その後、上
記テスト結果が０であつたビツトを１にセツ
トし、上記要求された記憶を実行する。４緊密結合多重プロセツサ・システムにおいて
排他性の大粒度ロツキングを行なう方法であつ
て、多重プロセツサ・システム用の記憶制御要素内
に、複数のプロセツサのそれぞれに１つずつ、局
所キヤツシユ・メモリに記憶されたデータ・ブロ
ツクの排他的状況の記録を維持するためのロツ
ク・テーブルを設けるステツプと、上記各プロセツサごとに、バツフア制御要素内
に、対応するプロセツサによつてアクセスされる
データ・ブロツクの排他的状況の記録のサブセツ
トを維持するための局所ロツク・テーブルを設け
るステツプとを含む方法。