JPH02247751A - 多重プロセッサ・キヤツシユにおける大粒度排他性ロツキング方法及び装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ０Ｍ業上０利用分野 本発明は、一般に多重プロセッサ（ＭＰ）データ処理シ
ステム内のキャッシュ・メモリの制御に関し、具体的に
は多重プロセッサ・キャッシュにおける排他性（ＥＸ）
の大粒度（ｌａｒｇｅｇｒａｎｕ　ｔａｒ　１ｔｙ）　
　ロッキングの実施に関するＯＢ、従来の技術 別々のプロセッサで並列に実行できる動作を並列に実行
してスループットを増加させる、高性能ＭＰコンビｊ−
タ・システムが開発されている。

このような高性能ＭＰコンビエータ・システムは、多数
の中央演算処理装置（ＣＰ）が独立かつ並列に動作し、
しかもデータを交換する必要がある時は相互間でまたは
主記憶装置（ＭＳ）との間で時々通信することが、その
特徴である。各ＣＰ及びＭＳは、入出力ボートを備え、
それらのポートはデータを交換できるように相互に接続
される。

緊密結合多重プロセッサ・システムと呼ばれる、各ＣＰ
がそれぞれキャッシュを有するタイプのＭＰシステムで
は、システムの様々なレベルで、整合性の問題が生じる
。具体的には、記憶階層の隣り合ったレベル間で不整合
が生じることがある。

たとえば、ＣＰの１つがそのデータのコピーを修正した
ために、多数のキャッシュが所有する同じデータのバー
ジ１ンが異なることがあり得る。したがって、各プロセ
ッサのキャッシュが、同時にいくつかのキャッシュに入
っている行に何が起こったかを知る必要がある。多数の
ＣＰが同じ主記憶装置を共用するＭＰシステムでは、各
ＣＰが、アクセスが発行されるときのアーキテクチャ仕
様に応じて、最も最適に更新されたバージョンのデータ
を獲得する必要がある。この要件から、キャッシュ間で
のデータの整合性を常に監視することが必要となる。

このキャッシュ整合性の問題に対して、いくつかの解決
方法が提案されている。早期の解決方法は、Ｃ，に、タ
ング（Ｔａｎｇ）の論文「緊密結合多重プロセッサ・シ
ステムにおけるキャッシュ・システムの設計（Ｃａｃｈ
ｅ　Ｓｙｓｔｅｍ　Ｄｅｓｉｇｎ　ｉｎ　ｔｈｅＴｉｇ
ｈｔｌｙ　Ｃｏｕｐｌｅｄ　Ｍｕｌｔｉｐｒｏｃｅｓｓ
ｏｒ　Ｓｙｓｔｅｍ）　ｊ、Ｐｒｏｃｅｅｄｉｎｇｓ　
ｏｆ　ｔｈｅ　ＡＦＩＰＳ　（１９７８年）、及びり、
Ｍ、サンシエ（Ｃｅｎｓｉｅｒ）とＰ、フォートリエ（
Ｆｅａｕｔｒ　ｉｅｒ　）の論文「多重キャッシュ・シ
ステムにおける整合性の問題の新しい解決策（ＡＮｅｗ
　５ｏｌｕｔｉｏｎ　ｔｏ　Ｃｏｈｅｒｅｎｃｅ　Ｐｒ
ｏｂｌｅｍｓ　ｉｎＭｕｌｔｉｃａｃｈｅ　Ｓｙｓｔｅ
ｍｓ）　Ｊ　ｓ　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ
　ｏｎＣｏｍｐｕｔｅｒｓｓ　１９７８年１２月号、ｐ
ｐ、ｔｔｔ２−１１１８に記載されている。サンシエ等
は、集中大域アクセス許可テーブルを使用する、多重キ
ャッシュ内で共用書込み可能データが存在できる体系を
記載している。しかし、前記著者等はその結論部分で、
２年前にはタング等が記載したのと類似の方法を知って
いなかったことを認めている。タングは、キャッシュの
コピー・ディレクトリを使って状況を維持することを提
唱したが、サンシエ等は同様の状況ビットで各メモリ・
ブロックをタグ付けすることを提唱した。

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

米国特許第４３９４７３１号明細書に記載されているよ
うな、より一般的な意味でのＥＸ状況を用いると、その
行がキャッシュに記憶されたことがない時でも、記憶制
御要素（ＳＣＥ）にアドレスせずに、プロセッサがキャ
ッシュに記憶することが可能になる。これは些細な違い
であるが、たとえばＩＢＭ／３０８１システムで、後続
の記憶が到来「しそうな」時にあるプロセッサである行
のＥＸ状況を獲得することができるので、概念上かなり
重要である。

従来技術のＭＰシステムでは、様々なタイプのキャッシ
ュがある。１つのタイプのキャッシュは、ＩＢＭシステ
ム／３７０　３０３３型ＭＰについて米国特許第４１４
２２３４号明細書に記載されているような、ストア・ス
ルー（ＳＴ）型キャッシュである。ＳＴキャッシュの設
計は、主記憶装置に対するデータの変更を常に更新する
ため、ＣＰがデータを主記憶装置に直接記憶することを
妨げない。主記憶装置へのストア・スルーの更新時に、
適切な相互間合せ（ＸＩ）処置を行なって、記憶された
行の遠隔コピーを無効にすることができる。記憶制御要
素（ＳＣＥ）が適切な記憶スタックを維持して、主記憶
装置（ＭＳ）記憶要求を待ち行列に入れ、バッファ制御
要素（ＢＣＥ）とＳＣＥの間の標準の通信により、記憶
スタックのあふれ状態が回避される。ＳＣＥ記憶スタッ
クが満杯になると、その状態がクリアされるまで、関連
するＢＣＥはそのＭＳ記憶を保持する。

もう１つのタイプのキャッシュ設計は、たとえば米国特
許第３７３５３８０号及び第４７７１１３７号明細書に
記載されているような、ストア・イン型キャッシュ（Ｓ
ＩＣ）である。ＳＩＣキャッシュ・ディレクトリは、前
掲の米国特許第４３９４７３１号明細書に詳しく記載さ
れている。上記特許では、ストア・イン型キャッシュ内
の各行が、その多重プロセッサ制御可能性を排他的／読
取専用（ＥＸ／ＲＯ）フラグ・ビットによって制御され
る。ＳＴキャッシュとＳＩＣキャッシュの主な違いは、
ＳＩＣ内のすべての記憶がキャッシュ自体に向けられ（
そのため、記憶された行がそのＳＩＣキャッシュにない
場合はキャッシュ・ミスになることかあ）ることである
。また、米国特許第４５０３４９７号明細書では、遠隔
キャッシュにコピーがある場合、取出しミス時にキャッ
シュ間転送（ＣＴＣ）バスを介してデータ転送が行なえ
ることが提唱されている。各キャッシュ内のディレクト
リのコピーを含むＳＣＥが使用される。そのため、相互
間合せ（ＸＩ）判断をＳＣＥで下すことが可能となる。

通常、キャッシュ行の修正は、それらの行がそのキャッ
シュから置換される時だけ、主記憶装置に対して更新さ
れる。

通常の相互間合せ（ＸＩ）法では、ブロックＢがＣＰ　
　Ｐｉに関してＥＸにロックされているとき、遠隔キャ
ッシュ内のブロックＢでカバーされる既存の第１段の各
行は無効にされる。ブロック・サイズが第ルベルの行の
サイズよりも大きい時は、しばしば冗長ＸＩ無効化が生
じる。すなわち、行は他のＣＰで修正されずに無効にさ
れる。ブロワ、り・サイズが行のサイズよりもずっと大
きい（たとえば、１６倍）時は、余分のキャッシュ・ミ
スとディレクトリ操作とによるオーバヘッドが許容でき
ないほどになる。

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

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

００課題を解決するための手段 本発明によれば、ブロックＢの若干の行がまだキャッシ
ュ中に存在していたとしても、他の中央演算処理装置（
ＣＰ）にブロックＢ上で一時的無効（ＴＩ）状態を与え
ることにより、プロセッサＰｉのアクセス権が主張（ｅ
ｎｆｏｒｃｅ）　　される。ＣＰがＴＩ状態のブロック
にアクセスしようと試みるには、記憶制御要素（Ｓ　Ｃ
Ｅ）にアドレスして、そのブロックに対する適切な許可
（たとえば、ＲＯ状態またはＥＸ状態）を得る必要があ
る。ＣＰがブロックＢ上で一時的無効状態ＴＩａと読取
り専用状態ＲＯｓと独占状態ＥＸａの３つの状態を持つ
ことができると仮定すると、−時的無効状態ＴＩ。が、
すべてのＣＰにあるすべてのブロックＢの初期状態とな
る。本発明に基づく大粒度のロック機構の基本的動作は
、次の通りである。

（１）プロセッサＰｉがブロックＢの行りに記憶し、Ｐ
ｉがＥＸａ状態を取らない場合、バッファ制御要素（Ｂ
ＣＥ）はＳＣＥからＥＸａ状態を要求すべきである。Ｐ
ｉがＥＸＢ状態を得て以降にそれがＬへの最初の記憶で
ある場合、ＳＣＥは遠隔キャッシュからの行りに対する
ＸＩ無効化信号をやり取りする。このＸＩ無効化は、Ｓ
ＣＥがＰｉにＥＸＢを与える時にも行なわれる。記憶を
意図した取出し要求も同様に処理される。

（２）プロセッサＰｉがＢ中のＴＩｅ状態のデータを取
り出す時、ＢＣＥは、キャッシュ・ヒットの場合でもア
クセスする前にＳＣＥからＲＯＢ　状態を要求する。

（３）ＳＣＥがプロセッサＰｉからＥＸＢ要求を受は取
る時、ＳＣＥはＰｉにＥＸｓを与える前に、すべての遠
隔ＣＰにＴＩａ状態を通知する。遠隔ＣＰ　　Ｐｊ（ｊ
＃ｉ）がたまたまＥＸａ状態をとっている場合、ＳＣＥ
は、プロセッサＰｉにＥＸｅ要求を許可する前に、プロ
セッサＰｊがＴＩｅ状態を得たことを確認する。

（４）ＳＣＥがプロセッサＰｉからＲｏｅ要求を受は取
ると、どの遠隔ＣＰもＥＸａ状態をとっていない場合、
ＳＣＥはその要求をただちに許可する。そうでない場合
は、ＳＣＥは、ＣＰ　ＰｊがそのＥＸｅ状態をＲｏｅ状
態に変えたことを確認した後で始めてその要求を許可す
る。

（１）から、ある行がキャッシュからＸＩ無効化される
のは、その行が実際に遠隔で修正される時であることが
わかる。その結果、本発明による過程は、過剰の無効化
によるオーバヘッドがない。

このことは容易に理解できる。ＳＣＥで、各ブロックＢ
ごとにたとえばプロセッサＰｉに対するビット・ベクト
ルＯＨ（局所変更）が維持されるのは、プロセッサＰｉ
に最後にＥＸａ状態が許可されて以降にれがＰｉによっ
て実際に記憶されるときである。ＣＨビットは、Ｐｉが
ＥＸａ状態を得た時、０ビットに初期設定される。ブロ
ックＢの行りの記憶をＳＣＥが受は取ると、次の動作が
行なわれる。

Ｌに関連するＣＨビットがオフの場合、ＳＣＥは遠隔キ
ャッシュにＸＩ無効化信号を送出する。次いで、Ｌに対
するＣＨビットがオンになる。

本発明の好ましい実施例による大粒度ロック方式の実施
態様で重要なファクタは、ＣＰに対するブロックの状態
をＳＣＥ及びＢＣＥに記録することである。ＳＣＥでは
、ロック・テーブル（Ｔｉ１１≦１　：ａ　ｋ　）　；
と仮定されている。すなわち、ＳＣＥはＥＸ状態の所有
権（ｏｗｎｅｒｓｈ　ｉｐ）　だけを記録する。

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

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

５ＣＥ３０は、ＣＰｌｏないし１３と主記憶装置５０に
接続されている。主記憶装置５０は、複数の基本記録モ
ジュール（ＢＳＭ）制御装置Ｂ５Ｃｏ１ＢＳＣ＋、Ｂ５
Ｃ２、Ｂ５Ｃ３（それぞれ５１．５２．５３．５４）か
ら構成され、各基本記憶制御装置は２つのＢＳＭＯ（８
０，６２，６４，６６）と１　（６Ｌ　６３．６５．６
７）に接続されている。、４つのＢ５Ｃ５１ないし５４
は、それぞれ５ＣＥ３０に接続されている。

従来のシステムでは、５ＣＥ３０は４つのコピー・ディ
レクトリ（ＣＤ）３１．３２．３３．３４を含み、各Ｃ
Ｄは、米国特許第４３９４７３１号明細書に記載されて
いるのと同様の方式で、１つのＢＣＥ中の対応するプロ
セッサ・キャッシュ・ディレクトリ（ＰＤ）の内容のイ
メージを含んでいる。下記の説明から明らかになるよう
に、本発明は、他のディレクトリで行存在情報を記録す
ることによってＸＩ無効化の量をさらに減少させること
が可能なものの、ＣＤを使用する必要はない。

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

５ＣＥ３０は、複数の記憶スタック（ＳＳｏ１ＳＳ＋、
ＳＳ２．５Ｓ３）３５．３Ｂ、３７．３８を維持する。

各記憶スタックは、対応するＣＰに対する最大１６ＤＷ
までの主記憶装置記憶要求を保持することができる。５
ＣＥ３０は、それらの記憶スタックに対して、主記憶装
置アドレス及び有効性を示すのに十分なブイレフ）　Ｉ
Ｊ情報を保持する。記憶スタックがオーバフローする危
険が生じると、５ＣＥ３０は、ＢＣＥが後で５ＣＥ３０
から記憶スタック満杯状態をクリアする信号を受は取る
まで、記憶要求の送出を保留するようにとの優先順位信
号を関連するＢＣＥ２０〜２３に送る。記憶スタック中
のデータは、主記憶装置に合わせて更新され、適切なス
ケジューリングによって各記憶スタック内の着信順序が
維持される。ＣＰからの行取出し要求は、記憶スタック
中のその行に対する既存の記憶がすべて関連するＢ　５
Ｍ６０〜６７に送られたことをＳＣＥが確認するまで、
５ＣＥ３０によって保持される。

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

ＣＰからの各記憶をＳＣＥと同期させる必要のある、典
型的なＳＴキャッシュ用のＳＣＥにある記憶同期化機構
について考えてみる。ＳＣＥでの基本動作は下記の通り
である。まず、プロセッサＰｉからの（ブロックＢ上の
）記憶同期化要求のＳＣ，Ｈによる処理について考察す
る。

（ａ、１）ブロックＢがロック・テーブルＴｉ中でヒツ
トしたときは、プロセッサＰｉにただちに記憶同期化が
許可される。

（ａ、２）どのロック・テーブルにもブロックＢがない
ときは、ＳＣＥはロック・テーブルＴｉ中にＢに対する
新しい項目を作成し、プロセッサＰｉに記憶同期化を許
可する。上記処理と並列して、ＳＣＥはまた遠隔キャッ
シュ内のＢをＸＩ無効化させる信号を（ブロックＢのデ
ータを含む可能性のあるＣＰに）送り出す。

（ａ、３）ブロックＢがロック・テーブルＴｊ（ｊ＃ｉ
）にヒツトしたときは、ＳＣＥでの遠隔ＥＸヒツトと類
似している。この場合は、ブロックＢの項目がロック・
テーブルＴｊから削除され、ロック・テーブルＴｉに新
しい項目が作成され（ＸＩ無効化信号がプロセッサＰｊ
に送られ）る。

次に、ＳＣＥがプロセッサＰｉからのブロックＢ中の行
に対する取出し要求（たとえば第１段キャッシュ・ミス
）を受は取った時の動作について考察する。

（ａ、４）ブロックＢが遠隔ＣＰによってＥＸロックさ
れないときは、その取出しは遅延なしで開始できる。

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

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

上記の諸ステップのうちで、（ａ−１）は、異なるＣＰ
からの複数の記憶について並列して行なうことができる
。他のステップの実行時にＳＣＥで適切な直列化が必要
となる場合もあるが、そのために同一サイクルで複数の
記憶同期化要求を実行する可能性が排除されることはな
い。ロッキング粒度すが大きくなる（たとえば４Ｋ）と
き、ステップ（ａ、２）及び（ａ、３）からのＸＩ無効
化によって重大な第１段キャッシュ・ミスが生じる。

上記の重大なＸＩ無効化は、ＳＢビット・ベクトルを用
いて、同じ行に対する連続した無効化を排除することに
より、大幅に減少させることができる。そのフォーマッ
トを第４図に示す。このベクトルは無効化同報通信用の
ＢＩＡＳ（バッファ無効化アドレス・スタック）様フィ
ルタとして使用される。このベクトルの各ビットは、ブ
ロックＢの複数の（たとえば２）行を表すことができ、
その場合、各ＸＩ倍信号関連する各遠隔キャッシュ内の
複数の行を無効にすることができる。ビット・ベクトル
でフィルタリングを行なう場合、たとえばロック・テー
ブルＴｉにある関連するビット・ベクトルが、プロセッ
サＰｉからの行中での以前の記憶を指示しない時に、キ
ャッシュ「行」無効化が遠隔ＢＣＥに送られるように、
ステップ（ａ。

１）を修正することができる。

第５図及び第６図は、こうしたビット・ベクトルに基づ
＜ＳＣＥ無効化フィルタリングのための論理を図示した
流れ図である。処理は第５図から始まり、機能ブロック
７０で、ブロックに対する新しい項目がロック・テーブ
ルＴｉに挿入される。

そうなった時、機能ブロック７２で、ビット・ベクトル
のすべてのＳｓビットがゼロにリセットされる。次に、
第６図に関連して、機能ブロック７４で、ＳＣＥはプロ
セッサＰｉからブロックＢに対する記憶要求を受は取る
。判断ブロック７６でテストを行なって、ロック・テー
ブルＴｉ中のそのブロック項目にあるビット・ベクトル
の関連する８８ビットが１かどうか判定する。１である
場合は、機能ブロック７８で、その記憶要求が処理され
る。そうでない場合は、機能ブロック８０で、ＳＣＥは
遠隔中央演算処理装置に行無効化信号を送り出す。次い
で、機能ブロック８２で、ＳＣＥは関連するＳＢビット
を１にし、その記憶要求を処理する。

上記のロックアツプ機構は、前掲の米国特許第４１４２
２３４号明細書に記載されている、ＩＢＭ３０３３ＭＰ
システムで使用されているバッファ無効化アドレス・ス
タック（ＢＩＡＳ）フィルタ・メモリ法とは異なってい
る。ＢＩＡＳそれ自体は、ＢＣＥが受は取る無効化信号
のスタックにすぎない。ＢＩＡＳフィルタ・メモリ方式
では、ＳＣＥは、各プロセッサＰｉごとに、プロセッサ
Ｐｉから最近に無効にされたブロックを再取出しなしで
記録するテーブルＩｉを維持する。プロセッサＰｉから
の各記憶要求を、同時にテーブルＩｊ（ｊ≠ｉ）中のす
べての項目と突き合わせて、ＸＩ無効化の可能性がある
かどうか検査する必要がある。プロセッサの数が増すに
つれて、この同時検査は重い負担になる。ロック・テー
ブル法では、大部分の記憶はＣＰ　　Ｐｉに関連するロ
ック・テーブルＴｉにヒツトし、したがって、ＳＣＥ処
理の並列度がずっと高（なる。さらに、任意の時点で、
最近に記憶されたブロックＩＤは、ＢＩＡＳフィルタ・
メモリ法では大部分の遠隔テーブルＬｉ中に存在する。

ロック・テーブルＴｊは、当該の各ＣＰからの最近の記
憶だけを記録し、（無効の項目以外は）互いにばらばら
である。その結果、ロック・テーブルＴｊは回路をより
有効に利用できる。

パイプライン化がずっと進む将来のプロセッサでは、記
憶同期化の遅延が、パイプラインの性能をかなり損なう
ことがあり得る。したがって、ＳＣＥに対する記憶同期
化の頻度が低下するように、ＢＣＥレベルで適切なＥＸ
ロックを行なうのが好都合である。上記のＳＣＥＣフロ
アップ設計では、ロック・テーブルＴｉにロックされた
ブロックは、実際には、それが（ｊ＃ｉのＰｊに対する
）どの遠隔キャッシュにも存在できないことを意味する
。

こうしたロッキング情報がＢＣＥに渡される場合、局所
的にロックされたブロックへの記憶のためのＳＣＥとの
初期接続手順をなくすことが可能である。第７図で、局
所ロック・テーブルＬｉが各プロセッサＰｉごとにＢＣ
Ｅによって維持される。

局所ロック・テーブルＬｉの各項目は、プロセッサＰｉ
によってＥＸにロックされるブロックのＩＤを記録する
。通常、局所ロック・テーブルＬｉの項目はロック・テ
ーブルＴｉの項目よりも少ない。記憶及びロックのため
の動作は次の通りである。

（ｂ、１）局所ロック・テーブルＬｉ中の全項目が、最
初は無効である。

（ｂ、２）プロセッサＰｉからの記憶が、局所ロック・
テーブルＬｉ中でロックされたブロックＢにヒツトした
時は、その記憶は遅延なしに実行できる。

（ｂ、３）プロセッサＰｆからのブロックＢに対する記
憶が、局所ロック・テーブル中でミスした時は、ＢＣＥ
はＳＣＥに同期化要求を送る。ＳＣＥから許可信号を受
は取ると、ブロックＢに対する有効項目が局所ロック・
テーブルＬｉ中で作成される。

（ｂ、４）プロセッサＰｉがＳＣＥからブロックＢに対
する解除要求を受は取った時は、局所ロック・テーブル
ＬｉからのブロックＢの項目が見つかった場合、プロセ
ッサＰｉのＢＣＥがその項目を無効にする。次いで、肯
定応答信号がＢＣＥに送られる。

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

（ｂ、５）ブロックＢが局所ロック・テーブルＬｉ中で
ロックされている可能性がある場合、ＳＣＥはプロセッ
サＰｊに、ブロックＢに対するＥＸロックを解除するよ
うに指示する信号を送る（ロック・テーブルＴｊは、局
所ロック・テーブルＬｊより多くのロック項目をもつこ
とを妨げられない）。この信号は、（たとえば、プロセ
ッサＰｉからのアクセスがＥＸ状況に対するものである
時に）適当なＸＩ無効化要求と結合されることがある。

ＳＣＥは、プロセッサＰｊから肯定応答信号を受は取っ
て始めて、このＸＩ動作を完了する（ステップ（ｂ、４
）参照）。

局所ロック・テーブルＬｉ内のロック情報を、ロック・
テーブルＴｉ内のロック情報のサブセットにすることが
望ましい。第８図に示すような余分のＬビットをＴｉテ
ーブル項目１つにつき１個ずつ追加することによって、
ＳＣＥは、５ＣＥＥＸロツク・テーブルＴｉ内のあるブ
ロックが対応するＢＣＥ局所ロック・テーブルＬｉ中に
あるか否かを検出することができる。しかし、局所ロッ
ク・テーブルＬｉとロック・テーブルＴｉが同じサイズ
の場合は、そうする必要はなく、ロック・テーブルＴｉ
からある項目が削除された時に、局所ロック・テーブル
Ｌｉ中にそれに対応するブロックが存在しないように保
証するだけで十分である。ロック・テーブルＴｉの項目
がテーブルＴｉから削除される理由としては、相互間合
せと局所要求による置換の２つが考えられる。ＸＩ処理
（たとえば上記のステップ（ｂ、５））は、このサブセ
ット則を適切に維持する。局所置換の場合、ロック・テ
ープルＴｆから項目が置換される理由としては、プロセ
ッサＰｉからのＥＸ要求しかないことは明らかである。

以上の議論は、通常のＸＩ無効化法を前提としたもので
ある。すなわち、ブロックＢがプロセッサＰｉからＥＸ
にロックされるとき、遠隔キャッシュ内のブロックＢで
カバーされる既存の第１段キャッシュ行は無効になる。

そのブロック・サイズが第１段ブロック・サイズより大
きい時は、その結果しばしば冗長ＸＩ無効化が生じる（
すなわち、行が別のＣＰで修正されないのに無効になる
）。ブロック・サイズが行のサイズよりずっと大きい（
たとえば、１６倍）時は、余分のキャッシュ・ミス及び
ディレクトリ処理によるオーバヘッドは許容できないも
のになる。

実験から、取出しについても記憶についても、大きな空
間的局在性が観察されている。より大きな粒度のブロッ
クでＥＸロックを実行する時、非ＥＸ記憶の速度が著し
く低下する可能性がある。

したがって、上記の性能上のオーバヘッドを生じずに大
粒度のＥＸロックが実行できれば価値がある。以下の説
明では、話を簡単にするため、排他的ロックの粒度を、
多重プロセッサ・システムにおいて各キャッシュ行当た
り１２８バイトの４にブロックで例示する。こうした場
合、各ブロックに３２行あることになる。ただし、これ
らの数字は例として示したものにすぎず、本発明の実施
に際して、異なるサイズのブロック、行、キャッシュも
使用できることを了解されたい。また、この説明では、
ＳＣＥがシステム中の複数のプロセッサそれぞれによる
記憶ブロックの排他的（ＥＸ）所有権を記録する、スト
ア・スルー型（ＳＴ）キャッシュ設計であると仮定する
。また、各中央演算処理装置（ＣＰ）に、ブロック情報
を記録するためのディレクトリＤ、があるものと仮定す
る。ディレクトリＤｐ内のブロックＢに対する各項目に
は、少なくとも概念上、排他的ＥＸＢ１−時無効ＴＩａ
、読取り専用ＲＯａの３つの状態がある。実際には、シ
ステムは、容量が限られているＥＸロック・テーブルに
よって各プロセッサごとにＥＸ状態とＴＩ状態だけを明
示的に維持している。ＢＣＥは、ブロックＢがＴＩまた
はＥＸではないことを検出した時は、単にそのブロック
をＲＯとして扱う。したがって、ディレクトリＤｐは、
ＴＩ状態とＥｘ状態を記録するものと見なせる。ある実
施態様では、■Ｎ■８状態も使用されることがある。

ＢＣＥが許可情報を獲得する方法の１つは、ＳＣＥから
すべてのＣＰのＥＸロック情報を複製するものである。

プロセッサＰｉは、別のＣＰがＥＸ８状態をとるとき、
ＴＩＢ状態をとる。プロセッサＰｉのＢＣＥで維持され
ている（Ｌｊ１１≦ｊ≦ｋ）のコピーをＨ，ｊ（ｉ）　
Ｉ　１≦ｊ：ａｋ）で示すことにする。プロセッサＰｉ
では、ロック・テーブルＬｉ（ｉ）が前記の局所ロック
・テーブルとして機能する。プロセッサＰｉで、ブロッ
クＢがテーブルＬｉ（ｉ）で見つかった場合は、ブロッ
クＢはＥＸｅ状態であり、ロック・テーブルＬｊ（ｉ）
（ｊ≠ｉ）で見つかった場合はＴＩａ状態であり、その
他の場合はＲＯｓ状態である。プロセッサＰｉがＴＩａ
状態からＲｏＢ状態またはＥＸｅ状態に切り替わると、
ＢＣＥは、ロック・テーブルＬｊ（ｆ）　（ｊ　ｆ−ｉ
）に記録されている以前の遠隔ＥＸＢ状態を無効にしな
ければならない。ＳＣＥは、プロセッサＰｉにＥＸｅ状
態を与える時、やはり局所ロック・テーブルＬｉ中のブ
ロックＢの項目の座標を送ることによって、各プロセッ
サＰｊ（ｊ≠Ｉ）にＴＩ。状態をとるようにとの信号を
送る。ＴＩＢ信号を受は取ると、プロセッサＰｊのＢＣ
Ｅは、ロック・テーブルＬｉ（ｊ）の指定された座標に
その状況を記録する。プロセッサＰｊが、プロセッサＰ
ｉ（ｉ≠ｊ）からのＲＯｅ要求によってそのＥＸａ状態
を放棄しく　ＲＯａ状態になる）時、ＳＣＥがその状態
変化を他のＣＰに通知するのが宵月であるが、必ずしも
必要ではない。

本発明の別の実施例では、「局所」ロック・テーブルＬ
ｊ（ｉ）はＳＣＥでテーブルＴｊ　（ｉ）として維持す
ることができる。ただし、ＴｉテーブルをＬｉテーブル
よりもずっと大きくすると、性能及び設計上何らかの利
点がある。すなわち、ＥＸ状況の解釈が、ＳＣＥとＢＣ
Ｅの間で異なることがあり得る。

テーブルＬｉはテーブルＴｉのサブセットとして維持さ
れるので、ＥＸ状況が局所ロック・テーブルＬｉに記録
されている限り、ＳＣＥもＢＣＥもＥＸ状況を理解する
はずである。しかし、実施態様によっては、ＢＣＥがロ
ック・テーブルＴｉの情報をすべて知っている必要はな
い。このより大きなＴｉテーブルをＳＣＥが使ってＢＣ
ＥにＥＸ状況を許可する際の並列性を高め、状況、たと
えば無効化フィルタリング用のＳｓビット・ベクトルを
記録する。

局所ロック・テーブルＬｉに記録されたＥＸ状況は、相
互間合せ（ＸＩ）活動の対象となる唯一ノ項目である。

ロック・テーブルＴｉは、本質上ＳＣＥの記帳用のもの
にすぎない。アーキテクチャの整合性は、プロセッサ及
び入出力チャネルからの記憶装置へのアクセスに対して
のみ維持すればよい。この場合、ブロックＢが遠隔ロッ
ク・テーブルＴｊに記録されている時でも、ブロックＢ
が遠隔ＢＣＥの局所ロック・テーブルＬｊに割り当てら
れていない限り、そのブロックＢはあるプロセッサに対
するＲＯ状態となることができる。

本発明による処理の論理を、第９図、第１０図及び第１
１図に流れ図で示す。第９図に示したケースでは、機能
ブロック８２で、ＳＣＥはプロセッサＰｉからＥＸｓ要
求を受は取る。判断ブロック８４でテストを行なって、
ブロックＢがロック・テーブルＴｉに記録されているか
どうか判定する。記録されている場合は、機能ブロック
９８に進む。

そうでない場合は、判断ブロック８６でさらにテストを
行なって、ブロックＢが遠隔テーブルＴｊ（ｊ≠ｉ）に
記録されているかどうか判定する。

記録されていない場合は機能ブロック９６に進むが、そ
うでない場合は、判断ブロック８８で再度テストを行な
って、ブロックＢが遠隔局所ロック・テーブルＬｊに記
録されているかどうか判定する。

記録されている場合、ＳＣＥはプロセッサＰｊに、その
ロック・テーブルＬｊからブロックＢを削除するように
指示し、次いで、機能ブロック９２で、プロセッサＰｊ
からの肯定応答を待つ。肯定応答を受は取った時、ある
いは判断ブロック８８でのテスト結果がノーの場合、機
能ブロック８４で、ＳＣＥはロック・テーブルＴｊから
ブロックＢを削除する。ブロックＢが削除された時、あ
るいは判断ブロック８６でのテスト結果がノーの場合、
機能ブロック９８で、ＳＣＥはブロックＢに対する新し
い項目をテーブルＴｉに挿入する。次いで機能ブロック
９８で、ＳＣＥは遠隔中央演算処理装置にＨＯＬ　Ｄ　
ｅ信号を送り出す。最後に機能ブロック１００で、ＳＣ
ＥはプロセッサＰｉにＥＸｅ状況を許可するよう指示す
る。

第１０図に示したケースでは、機能ブロック１０２で、
ＳＣＥはプロセッサＰｉからＥＸｓ解除要求を受は取る
。それにより、機能ブロック１０４で、ＳＣＥはすべて
の遠隔プロセッサにＣＬＥＡＲ３信号を送り出す。次い
で機能ブロック１０６で、ＳＣＥは、ブロックＢがもは
や局所ロック・テーブルＬｉに記録されていないことを
示すように、ロック・テーブルＴｉにおけるブロックＢ
の項目の状況を更新する。

第１１図には、ＲＯ状況要求のケースが示されている。

この場合、機能ブロック１０８で、ＳＣＥはプロセッサ
ＰｉからＲＯｅ状況要求を受は取る。

判断ブロック１１０でテストを行なって、ブロックＢが
遠隔ロック・テーブルＴｊ（ｊ≠ｉ）に記録されている
かどうか判定する。記録されている場合、判断ブロック
１１２でさらにテストを行なっテ、フロックＢが遠隔局
所ロック・テーブルＬｊに記録されているかどうか判定
する。記録されていない場合、ＳＣＥはロック・テーブ
ルＴｊからブロックＢの項目を削除する。ブロックＢの
項目が削除されている時、あるいは判断ブロック１１０
でのテスト結果がノーである場合、機能ブロック１１６
で、ＳＣＥはプｏ　セラ＋　Ｐ　ｉ　ニＲＯＢ状況を許
・可するよう指示する。

判断ブロック１１２に戻ると、ブロックＢが遠隔局所ロ
ック・テーブルＬｊに記録されている場合、機能ブロッ
ク１１８で、ｓｃＥはプロセッサＰｊにその局所ロック
・テーブルＬｊからＥＸＢを解除するように指示する。

次いで、ＳＣＥはプロセッサＰｊの肯定応答を待つ。プ
ロセッサＰｊがら肯定応答を受は取ると、機能ブロック
１２０で、ＳＣＥはプロセッサＰｊ以外のプロセッサに
ＣＬＥ　Ａ　Ｒｓ信号を送り出す。プロセッサＰｊは、
ＣＬＥ　Ａ　Ｒｅ信号を受は取ると自動的にＲＯｅ状況
となる。

ＣＰ　　Ｐｉが（記憶のためのアクセスによって、ある
いはプロセッサＰｉがまもなくブロックＢに記憶すると
予想される時）ＳＣＥに対してブロックＢの排他的制御
権を要求する（ＣＰがＥＸＢ状況をとることで示される
）と、ＳＣＥは下記の適切な動作を実行する。まず、遠
隔ＣＰまたとえばＰｊがその局所ロック・テーブルＬｊ
でＥＸｅ状態を所有することをＳＣＥが検出した場合、
ＳＣＥは、プロセッサＰｉにＥＸａを許可する前に、プ
ロセッサＰｊがそのＥＸｅ状態を放棄するようにさせる
。そうしないと、ただちにＥＸａがプロセッサＰｉに許
可されてしまうことがある。次に、ＳＣＥは、そのキャ
ッシュにブロックＢの行を所有する可能性のある遠隔Ｃ
ＰにＨＯＬＤｅ信号を送り出す。このＨＯＬ　Ｄ　ｅ信
号を受は取った後、遠隔ＣＰまたとえばＰｊは（ロック
・テーブルＬｉ（ｊ）にブロックＢを記録することによ
り）ブロックＢをＴＩ。状態でマークする。ただし、Ｔ
ＩＢ状態とは、ブロックＢがそのＣＰに対して一時的に
無効となることを意味する。

プロセッサＰｉは、取出し要求によってＴＩｅ状態のブ
ロックＢにアクセスする際、ＳＣＥにアクセス権を求め
る必要がある。取出し要求は、インタロック命令からの
取出し後修正要求でもよいことに留意されたい。ＳＣＥ
はＥＸａ状態を保持しているＣＰにそれを放棄させる。

ＥＸＢ状態がどの遠隔ＣＰによっても所存されなくなっ
た後、ＳＣＥはプロセッサＰｆに適切なアクセス権を許
可する信号を送る。プロセッサＰｉは、ＳＣＥからの許
可を受は取った後、ＴＩＢ状態を適当な状態、たとえば
ＲｏｅまたはＥＸａに変更して、ブロックＢのデータへ
のアクセスを開始する。キャッシュ・ミス状況の場合、
ＳＣＥはある時点でプロセッサＰｉにその行の有効コピ
ーを転送して、プロセ。

すＰｉがアクセス権獲得後にミスを再発行しなくてもす
むようにすることができる。

プロセッサＰｉは、何らかの理由でＥＸａ状態を放棄す
る時、その事象についてＳＣＨに知らせる。

ＥＸａ状態が現在別のＣＰから要求されていない場合、
ＳＣＥは、ＴＩＢ状態を保持している可能性のある遠隔
ＣＰにＣＬＥＡＲａ信号を送る。このＣＬＥＡＲＢ信号
を受は取った後、ｃｐ、たとえばＰｊは、後でブロック
Ｂにアクセスできるように、（Ｔｉ（ｊ）からブロック
Ｂを削除することによって）そのＴＩｓ状態をクリアす
る。

ＣＰ　　ＰｉがＥＸｓ状態のもとてブロックＢ内のある
行に記憶する時、ＳＣＥは、自分のキャッシュにその行
のコピーを所存している可能性のあるＣＰに、ＸＩ（相
互無効化）信号を同報通信する。

ＳＣＥは、ＣＰまたとえばＰｉが排他的に（Ｅ　ＸＢ）
所存する各ブロックごとに、下記の情報を維持すること
ができる。（ａ）どのＣＰがＥＸＢ状態をとっているか
。これは、遠隔ＥＸＸヒツト相互台せを取り扱うために
使用される。（ｂ）Ｐｉが最後にＥＸＢ状態を獲得して
以降、Ｂのどの行に以前にＰｌによって記憶が行なわれ
たか。これは、前述のように、ビット・ベクトルＳＢを
使って実施できる。

ＣＰ　　Ｐｉにおいて、その局所ロック・テーブルＬｔ
中の（たとえばブロックＢに対する）各項目は、Ｐｉが
最後にＥＸＢ状態を獲得して以降、ブロックＢのどの行
に以前にプロセッサＰｉによって記憶が行なわれたかに
関する情報を保持することができる。これは、ＳＣＥに
ついて説明したのと同様のビット・ベクトルを使って実
施できる。

こうしたベクトルが局所ＣＰで実施されるときは、必ず
しも上記のベクトルを使用する必要はない。

この実施態様は、ストア・イン型キャッシュ設計に最も
好都合である。

ＣＰがそのＥＸａ制御権を放棄する時、ＳＣＥはただち
に他のＣＰにＣＬＥＡＲｓ信号を送り出す必要はない。

このため、他のＣＰが、後でＢを最初に参照する際にＳ
ＣＥと相談できるようになる。

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

この状態の実施には様々なビットが使用できる。

たとえば、ＴＩ８状態は独立のフラグ・ビットを使って
実施できる。場合によっては、そうするのが好都合であ
る。

遠隔キャッシュ行無効化信号の有効なフィルタリングを
行なえることが重要である。上記のビット・ベクトル以
外に他のフィルタリング手段を設けるのが育利なことが
ある。上記のＳｓビット・ベクトルで遠隔無効化をなく
することができない時は、たとえば、Ｃ，に、タングが
提唱したコピー・ディレクトリ（ＣＤ）技術や、Ｌ、Ｍ
、センシエ他が提唱した存在タグが２次フィルタリング
手段として使用できる。局所テーブルによって保証され
る記憶のためのＥＸ状況を用いると、データの整合性の
問題を引き起こさずに、ＳＣＥが２次フィルタリングの
実行により多くの時間をかけることができるようになる
。

あらゆる記憶装置、すなわちキャッシュに対するアクセ
スで、すべてのロック・テーブルＬｊ（ｉ）を探索する
となると、重大な性能上の問題が生じる恐れがあるが、
そのような探索の必要はない。

その代わりに、これらのロック・テーブルＬｊ（ｉ）は
、ＢＣＥが必要とする時、バックアップ状況ディレクト
リとして働くことができる。たとえば、プロセッサＢＣ
Ｅは、各項目ごとに適切な状況（ＲＯまたはＥＸ）を記
録して、最初にアクセスされたブロックに対するディレ
クトリを小さくすることができる。大粒度のブロックで
は、このようなディレクトリに対するヒツト率は非常に
高くなると予想される。ロック・テーブルＬｊ（ｉ）を
探索する必要があるのは、アクセスされたブロックがデ
ィレクトリ中で見つからない時だけである。こうすると
、ＢＣＥは、大部分の時間、ＩＥ装置からの実際の記憶
装置アクセスと並列して、ロック・テーブルＬｊ（ｉ）
に作用することができる。

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

【図面の簡単な説明】

第１図は、本発明を適用できる多重プロセッサ・システ
ムの構成図である。 第２図は、第１図の多重処理システムの、複数のプロセ
ッサと記憶制御要素（ＳＣＥ）とを含む部分を示し、各
プロセッサ用のロック・テーブルを図示した構成図であ
る。 第３図は、本発明の一態様に基づくロック・テーブルの
ある項目のフォーマットを示す構成図である。 第４図は、本発明の別の態様に基づくロック・テーブル
のある項目のフォーマットを示す構成図である。 第５図及び第６図は、ＳＢビット・ベクトルを用いて記
憶の同期化を行なう本発明の実施態様の論理を示す流れ
図である。 第７図は、プロセッサにある局所ロック・テーブルを示
す、第２図と類似の構成図である。 第８図は、本発明の別の態様に基づくロック・テーブル
のある項目のフォーマットを示す、第３図と類似の構成
図である。 第９図、第１０図及び第１１図は、本発明の実施態様の
論理を示す流れ図である。 １０〜１３・・・・中央演算処理装置（ＣＰ）、１４〜
１７・・・・命令実行（ＩＥ）ユニット、２０〜２３・
・・・バッファ制御ユニット（ＢＣＥ）、３０・・・・
記憶制御要素（ＳＣＥ）、３５〜３８・・・・記憶スタ
ック（８８）、４０・・・・入出力チャネル・プロセッ
サ、５０・・・・主記憶装置、５１〜５４・・・・基本
記憶モジュール制御装置（ＢＳＣ）、Ｅ３０〜６７・・
・・基本記憶モジュール（ＢＳＭ）。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション 代理人　　弁理士　　頓　　宮　　孝 （外１名） 第 図 第３図 駕 笛８図 Ｊ″′　５０ ＣＥ １Ｍ２図 ＣＥ 第７図 第 図

Claims (4)

【特許請求の範囲】
1. （１）多重プロセッサ・キャッシュにおいて排他性の大
   粒度ロッキングを行なう方法であって、他のプロセッサ
   にあるブロックのデータについて一時的無効状態を与え
   ることにより、まだキャッシュに残っている当該ブロッ
   ク中の行が存在するとしても、あるプロセッサに唯一の
   アクセス権を与えるステップと、 別のプロセッサが一時的無効状態のブロック中のデータ
   を取り出す時、キャッシュ・ヒットの場合でも別のプロ
   セッサがアクセスする前に読取り専用アクセス権を求め
   る要求を必要とすることにより、唯一のアクセス権を主
   張するステップを含む方法。
2. （２）それぞれがキャッシュ・メモリとバッファ制御要
   素を有する複数の中央演算処理装置、主記憶装置及び記
   憶制御要素を有する多重プロセッサ・システムにおいて
   、 キャッシュ・メモリに記憶されたデータ・ブロックの排
   他性の大粒度ロッキングを行なうための装置であって、 すべてのキャッシュ・メモリに記憶されているデータ・
   ブロックの排他的状況の記録を維持するための、記憶制
   御要素内にある上記の各プロセッサごとのロック・テー
   ブル手段と、 各バッファ制御要素内にあって、対応するプロセッサに
   よってアクセスされるデータ・ブロックの排他的状況の
   記録のサブセットを維持するための、局所ロック・テー
   ブル手段と を含む装置。
3. （３）複数のプロセッサ、主記憶装置及び記憶制御要素
   を含む緊密結合多重プロセッサ・システム用のストア・
   スルー型キャッシュ・アーキテクチャにおいて、 上記プロセッサによるデータの大粒度記憶同期化を行な
   うための方法であって、 上記記憶制御要素内に、上記各プロセッサごとに１つず
   つ、上記各プロセッサに許可されたデータ・ブロックに
   ついての排他的状態の記録を維持するためのロック・テ
   ーブルを設けるステップと、上記各ロック・テーブル中
   に、あるブロックの同じ行で連続する無効化を排除する
   ための、各ブロック項目ごとに１ビットから構成される
   Ｓ＿Ｂビット・ベクトルを設けるステップと、 ブロックの新しい項目がロック・テーブルに挿入される
   ごとに、すべてのＳ＿Ｂビットを０にリセットするステ
   ップと を含む方法。
4. （４）緊密結合多重プロセッサ・システムにおいて排他
   性の大粒度ロッキングを行なう方法であって、多重プロ
   セッサ・システム用の記憶制御要素内に、複数のプロセ
   ッサのそれぞれに１つずつ、局所キャッシュ・メモリに
   記憶されたデータ・ブロックの排他的状況の記録を維持
   するためのロック・テーブルを設けるステップと、 上記各プロセッサごとに、バッファ制御要素内に、対応
   するプロセッサによってアクセスされるデータ・ブロッ
   クの排他的状況の記録のサブセットを維持するための局
   所ロック・テーブルを設けるステップと を含む方法。