JPH0315965A - マルチプロセッサコンピュータシステムにおいて複数のキャッシュメモリとメインメモリとの間のデータの一貫性を確保する改良機構 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、これと同時に出願された次のような米国特許
出願に開示されているコンピュータシステムの幾つかの
特徴を有するものである。エバンス氏等の「デジタルコ
ンピュータのシステム制御ユニットとサービス処理ユニ
ットとの間のインターフェイス（ＡＮ　ＩＮＴＥＲＦＡ
ＣＥ　ＢＥＴＷＥＥＮ　Ａ　ＳＹＳＴＥＭＣＯＮＴＲＯ
Ｌ　ＵＮＩＴ　ＡＮＤ　Ａ　ＳＹＳＴＥＭ　ＰＲＯＣＥ
ＳＳＩＮＧ　ＵＮＩＴＯＦ　Ａ　ＤＩＧＩＴＡＬ　ＣＯ
ＭＰＵＴＥＲ），Ｉ　　；アーノルド氏等の「マイクロ
プロセッサシステムのシステム制御ユニットと中央処理
ユニットとをインターフエイスする方法及び装置（ＭＥ
Ｔ｝ＩＯＤ　ＡＮＤ　ＡＰＰＡＲＡＴＵＳ　ＦＯＲＩＮ
ＴＥＲＦＡＣＩＮＧ　Ａ　ＳＹＳＴＥＭ　ＣＯＮＴＲＯ
Ｌ　ＵＮＩＴ　ＦＯＲ　ＡＭＵＬＴＩＰＲＯＣＥＳＳＯ
Ｒ　ＳＹＳＴＥＭ　ＷＩＴＨ　ＴＨＥ　ＣＥＮＴＲＡＬ
ＰＲＯＣＥＳＳＩＮＧ　ＵＮＩＴＳ）Ｊ　　；ガグリア
ード氏等の「マルチプロセッサシステムのシステム制御
ユニットをシステムメインメモリとインターフエイスす
るための方法及び手段（ＭＥＴＨＯＤ　ＡＮＤ　ＭＥＡ
ＮＳ　ＦＯＲＩＮＴＥＲＦＡＣＩＮＧ　Ａ　ＳＹＳＴＥ
Ｍ　ＣＯＮＴＲＯＬ　ＵＮＩＴ　ＦＯＲ　ＡＭＵＬＴＩ
ＰＲＯＣＥＳＳＯＲＳＹＳＹＴＥＭＷＩＴＨＴＨＥＳＹ
ＳＹＴＥＭＭＡＩＮＭＥＭＯＲＹ）Ｊ　　；　Ｄ．フィ
ット氏等の「パイプライン式コンピュータシステムにお
いて考えられる種々の数のメモリアクセス競合を分析す
る方法と装置（ＭＥＴＨＯＤ　ＡＮＤ　ＡＰＰＡＲＡＴ
ＵＳ　ＦＯＲ　ＲＥＳＯＬＶＩＮＧ　ＡＶＡＲＩＡＢＬ
Ｅ　ＮＵＭＢＥＲ　ＯＦ　ＰＯＴＥＮＴＩＡＬ　ＭＥＭ
ＯＲＹ　ＡＣＣＥＳＳＣＯＮＦＬＩＣＴＳ　ＩＮ　Ａ　
ＰＩＰＥＬＩＮＥＤ　ＣＯＭＰＵＴＥＲ　ＳＹＳＹＴＥ
Ｍ）Ｊ　　；Ｄ．フィット氏等の「可変長さの命令アー
キテクチャにおいて多数の指定子をデコードする方法（
ＤＥＣＯＤＩＮＧ　ＭＵＬＴＩＰＬＥ　ＳＰＥＣＩＦＩ
ＥＲＳ　ＩＮ　Ａ　ＶＡＲＩＡＢＬＥＬＥＮＧＴＨ　Ｉ
ＮＳＴＲＵＣＴＩＯＮ　ＡＲＣＨＩＴＥＣＴＵＲＥ）Ｊ
　　；　Ｄ，フィット氏等の「仮想命令キャッシュリフ
ィルアルゴリズム（ＶＩＲＴＵＡＬ　ＩＮＳＴＲＵＣＴ
ＴＯＮ　ＣＡＣＨＥ　ＲＥＦＩＬＬＡＬＧＯＲＩＴＨＭ
）Ｊ　　；マーレイ氏等の「同じ命令内でのレジスタ及
びレジスタ変更指定子のパイプライン処理（ＰＩＰＥＬ
ＩＮＥ　ＰＲＯＣＥＳＳＩＮＧ　ＯＦ　ＲＥＧＩＳＴＥ
Ｒ　ＡＮＤＲＥＧ４ＳＴＥＲ　ＭＯＤＩＦＹＩＮＧＴ　
ＳＰＥＣＩＦＩＥＲＳ　ＷＩＴＩ｛ＩＮ　ＴＨＥＳＡＭ
Ｅ　ＩＮＳＴＲＵＣＴＩＯＮ）Ｊ　　；マーレイ氏等の
デジタルコンピュータ用のデータ依存性分析を行なう多
命令予備処理システム（ＭＵＬＴＩＰＬＥ　ＩＮＳＴＲ
ＵＣＴＩＯＮ　ＰＲＥ−ＰＲＯＣＥＳＳＩＮＧ　　ＳＹ
ＳＴＥＭ　ＷＩＴＨ　　ＤＡＴＡ　　ＤＥＰＥＮＤＥＮ
ＣＹＲＥＳＯＬＵＴＩＯＮ　ＦＯＲ　ＤＩＧＩＴＡＬ　
ＣＰＭＰＵＴＥＲ）Ｊ　　；　Ｄ，　フィット氏等の「
バイブラインプロセッサにおいて暗示された指定子を予
め処理する方法（ＰＲＥ−ＰＲＯＣＥＳＳＩＮＧ　ＩＭ
ＰＬＩＥＤ　ＳＰＥＣＩＦＩＥＲＳ　ＩＮＡ　ＰＩＰＥ
ＬＩＮＥＤＰＲＯＣＥＳＳＥＲ）Ｊ　　；　Ｄ，フィッ
ト氏等の「ブランチ予想（ＢＲＡＮＣＨ　ＰＲＥＤＩＣ
ＴＩＯＮ）Ｊ　　；フォッサム氏等の「デジタルコンピ
ュータのパイプライン式フローティングポイント加算器
（ＰＩＰＥＬＩＮＥＤ　ＦＬＯＡＴＩＮＧＰＯＩＮＴ　
ＡＤＤＥＲ　ＦＯＲ　ＤＩＧＩＴＡＬ　ＣＯＭＰＵＴＥ
Ｒ）Ｊ　　．グランドマン氏等の「自己計時式レジスタ
ファイル（ＳＡＬＦ　ＴＩＭＥＤ　ＲＥＧＩＳＴＥＲＦ
ＩＬＥ）Ｊ　　；べベン氏等の「パイプライン式コンピ
ュータシステムにおいてエラーを検出して修正する方法
及び装置（ＭＥＴＨＯＤＡＮＤ　ＡＰＰＡＲＡＴＵＳ　
ＦＯＲ　ＤＥＴＥＣＴＩＮＧ　ＡＮＤ　ＣＯＲＲＥＣＴ
ＩＮＧＥＲＲＯＲＳ　　ＩＮ　　Ａ　　ＰＩＰＥＬＩＮ
ＥＤ　　Ｃｏ閃ＰＵＴＥＲ　　ＳＹＳＴＥＭ）Ｊ　　；
　　フリン氏等の「マルチプロセッサシステムにおいて
システム制御ユニットを用いて通信要求を仲裁する方法
及び手段（ＭＥＴ｝｛ＯＤ　ＡＮＤ　ＭＥＡＮＳ　ＦＯ
Ｒ　ＡＲＢＩＴＲＡ−ＴＩＮＧ　ＣＯＭＭＵＮＩＣＡＴ
ＩＯＮ　ＲＥＱＵＥＳＴＳ　ＵＳＩＮＧ　Ａ　ＳＹＳＴ
ＥＭＣＯＮＴＲＯＬ　ＵＮＩＴ　　ＩＮ　Ａ　ＭＵＬＴ
Ｔ−ＰＲＯＣＥＳＳＯＲ　ＳＹＳＴＥＭ）Ｊ　　；Ｅ．
フィット氏等のｒマイクロコード化実行ユニットにおい
て並列動作で多機能ユニットを制御する方法（ＣＯＮＴ
ＲＯＬＯＦ　ＭＵＬＴＩＰＬＥ　ＦＬＩＮＣＴＩＯＮ　
ＵＩＮＴＳＷＩＴＩ−Ｉ　ＰＡＲＡＬＬＥＬ　ＯＰＥＲ
ＡＴＩＯＮ　ＩＮ　Ａ　ＭＩＣＲＯＣＯＤＥＤＥＸＥＣ
ＵＲＩＯＮ　ＵＩＮＴ）Ｊ　　；ウェブ二世氏等の「仮
想メモリシステムをベースとするデジタルコンピュータ
の命令パイプライン内において予めフェッチした命令で
メモリアクセス例外を処理する方法（ＰＲＯＣＥＳＳＩ
ＮＧ　ＯＦ　ＭＥＭＯＲＹ　ＡＣＣＥＳＳ　ＥＸＣＥＰ
ＴＩＯＮＳ　ＷＩＴＨＰＲＥ−ＦＥＴＣＨＥＤ　ＩＮＳ
ＴＲＵＣＴＩＯＮＳ　ＷＩＴＨＩＮ　ＴＨＥ　ＩＮＳＴ
ＲＵＣ−ＴＩＯＮ　ＰＩＰＥＬＩＮＥ　ＯＦ　Ａ　ＶＩ
ＲＴＵＡＬＭＥＭＯＲＹ　ＳＹＳＴＥＭ−ＢＡＳＥＤ　
ＤＩＧＩＴＡＬ　ＣＯＭＰＵＴＥＲ）Ｊ　　；ヘザリン
トン氏等の「デジタルコンピュータシステムにおいて仮
想−物理メモリアドレスの変換を制御する方法及び装置
（ＭＥＴＨＯＤ　ＡＮＤ　ＡＰＰＡＲＡＴＵＳ　ＦＯＲ
　ＣＯＮＴＲＯＬＬＩＮＧＴＨＥ　ＣＯＮＶＥＲＳＩＯ
Ｎ　ＯＦ　ＶＩＲＴＵＡＬ　Ｔｏ　ＰＨＹＳＩＣＡＬ　
ＭＥＭＯＲＹＡＤＤＲＥＳＳＥＳ　ＩＮ　Ａ　ＤＩＧＩ
ＴＡＬ　ＣＯＮＰＵＴＥＲ　ＳＹＳＹＴＥＭ）４　　；
ヘザリントン氏等のｒエラー修正機能を有するライトパ
ックバッファ（ＷＲＩＴＥ　ＢＡＣＫ　ＢＵＦＦＥＲ　
ＷＩＴＨ　ＥＲＲＯＲ　ＣＯＲＲＥＣＴＩＮＧＣＡＰＡ
ＢＩＬＩＴＩＥＳ）Ｊ　　；フリン氏等の「マルチプロ
セッサシステムにおいてシステム制御ユニットを用いて
通信要求を仲裁する方法及び手段（ＭＥＴＨＯＤ　ＡＮ
Ｄ　ＭＥＡＮＳ　ＦＯＲ　ＡＲＢＩＴＲＡＴＩＮＧ　Ｃ
ＯＭＭＵ−ＮＩＣＡＴＩＯＮ　　ＲＥＱＵＥＳＴＳ　　
ＵＳＩＮＧ　　Ａ　　ＳＹＳＴＥＭ　　ＣＯＮ丁ＲＯＬ
ＵＮＩ丁ＴＮ　Ａ　ＭＵＬＴＩ−ＰＲＯＣＥＳＳＯＲ　
ＳＹＳＴＥＭ）Ｊ　　；チナスウェイ氏等の「マルチプ
ロセッサシステムにおいてシステムユニット間でデータ
トランザクションを行なうモジュール式クロスバー相互
接続ネットワーク（ＭＯＤＵＬＡＲ　ＣＲＯＳＳＢＡＲ
　ＩＮＴＥＲＣＯＮＮＥＣＴＩＯＮＮＥＴＷＯＲＸ　Ｆ
ＯＲ　ＤＡＴＡ　ＴＲＡＮＳＡＣＴＩＯＮＳ　ＢＥＴＷ
ＥＥＮ　ＳＹＳ−ＴＥＭ　ＵＮＩＴＳ　ＩＮ　Ａ　ＭＵ
ＬＴＩ−ＰＲＯＣＥＳＳＯＲ　ＳＹＳＴＥＭ）Ｊ　，ボ
ルジン氏等の「入力／出力ユニットとマルチプロセッサ
システムのシステム制御ユニットとをインターフエイス
する方法及び装置（ＮＥＴ！ＩＯＤ　ＡＮＤＡＰＰＡＲ
ＡＴＵＳ　ＦＯＲ　ＩＮＴＥＲＦＡＣＩＮＧ　Ａ　ＳＹ
ＳＹＴＥＭ　ＣＯＮＴＲＯＬＵＮＩＴ　ＦＯＲ　Ａ　Ｍ
ＵＬＴＩ−ＰＲＯＣＥＳＳＯＲ　ＳＹＳＹＴＥＭ　ＷＩ
ＴＨＩＮＰＵＴ／ＯＵＴＰＵＴ　ＵＮＩＴＳ）Ｊ　　；
ガグリアード氏等の「マルチプロセッサシステムのシス
テム制御ユニットとシステムメインメモリとをインター
フエイスする手段に用いるメモリ構成（ＭＥＭＯＲＹ　
ＣＯＮＦＩＧＵＲＡＴＩＯＮ　ＦＯＲ　ＵＳＥ　ＷＩＴ
Ｈ　ＭＥＡＮＳ　ＦＯＲ　ＩＮＴＥＲＦＡＣＩＮＧ　Ａ
ＳＹＳＴＥＮ　ＣＯＮＴＲＯＬ　ＵＮＩＴ　ＦＯＲ　Ａ
　ＭＵＬＴＩ−ＰＲＯＣＥＳＳＯＲ　ＳＹＳＴＥＭ　Ｗ
ＩＴＨ　ＴＨＥ　ＳＹＳＴＥＭ　ＭＡＩＮ　ＭＥＭＯＲ
Ｙ）Ｊ　　；ガグリアード氏等の『システムモジュール
間のＤＲＡＭ制御信号のエラーチェックのための方法及
び手段（ＭＥＴＨＯＤ　ＡＮＤ　ＭＥＡＮＳ　ＦＯＲ　
ＥＲＲＯＲ　（：ｌ｛ＥＣＫｒＮＧ　ＯＦ　ＤＲＡＭ−
ＣＯＮＴＲＯＬＳＩＧＮＡＬＳ　ＢＥＴＷＥＥＮ　ＳＹ
ＳＴＥＭ　ＭＯＤＵＬＥＳ）Ｊ　；　７一ノルド氏等の
マルチプロセッサシステムにおけるメモリアクセス動作
の同期及び処理（ＳＹＮＣＩ｛ＲＯ−ＮＩＺＩＮＧ　Ａ
ＮＤ　ＰＲＯＣＥＳＳＩＮＧ　ＯＦ　ＭＥＭＯＲＹ　Ａ
ＣＣＥＳＳ　ＯＰＥ−ＲＡＴＩＯＮＳ　ＩＮ　ＭＵＬＴ
Ｉ−ＰＲＯＣＥＳＳＯＲ　ＳＹＳＴＥＭ）Ｊ　　；ヘサ
リントン氏等の「所定のデータ路巾を有するコンピュー
タシステムのデータ記憶速度を高める方法及び装置（Ｍ
ＥＴＨＯＤ　ＡＮＤ　ＡＰＰＡＲＡＴＵＳ　ＦＯＲ　Ｉ
ＮＣＲＥＡＳＩＮＧＴＨＥ　ＤＡＴＡ　ＳＴＯＲＡＧＥ
　ＲＡＴＥ　ＯＦ　Ａ　ＣＯＭＰＵＴＥＲ　ＳＹＳＴＥ
Ｍ１｛ＡＶＩＮＧ　Ａ　ＰＲＥＤＥＦＩＮＥＤ　ＤＡＴ
Ａ　ＰＡＴＨ　ＷＩＤＴＨ）Ｊ　；　及びヘザリントン
氏等の「多数のメモリ要求を順序付けして待ち行列に入
れる方法及び装置（ＭＥＴＨＯＤＡＮＤ　ＡＰＰＡＲＡ
ＴＵＳ　ＦＯＲ　　ＯＲＤＥＲＩＮＧ　ＡＮＤ　ＱＵＥ
ＵＴＮＧＭＵＬＴ■ＰＬＥ　ＭＥＭＯＲＹ　ＲＥＱＵＥ
ＳＴＳ）Ｊ　　。

本発明は、一般に、キャッシュをベースとするマルチプ
ロセッサシステムに係る。より詳細には、本発明は、マ
ルチプロセッサコンピュータシステムにおいてメインメ
モリと個々のプロセッサキャッシュメモリとの間のデー
タの一貫性を確保する改良された技術に係る。

従来の技術 キャッシュメモリは、システムメモリとプロセッサとの
速度の比を最適なものにするために高性能のコンピュー
タシステムに通常使用されている。小型で高速度のバッ
ファメモリの形態で典型的に実施されるキャッシュは、
当該システムプロセッサが現在オペレーションを実行す
る際に必要となり勝ちなデータ（典型的には、最も最近
使用された命令及びデータ項目）を連続的に得てそれを
一時的に保持する。コンピュータシステムのメインメモ
リは、一般に、論理的な類序でそしてしばしば逐次の形
態でアクセスされる。その典型例として、アレイ構造体
の処理や、特定のプログラムを実行する際の命令のシー
ケンシングが含まれる。或いは又、プログラムが局部領
域へ制御を移す前に命令ループを繰返し実行することが
できる。

これらの両方の場合に、低速度のシステムメモリへの繰
返しの参照を回避するに充分なデータを保持することの
できる補助メモリが設けられていれば、個々のプロセッ
サ、ひいては、全コンピュータシステムの実行速度を実
質的に高めることができる。システムメモリに関連した
キャッシュがこの機能を果たす。

典型的なキャッシュ構成においては、プロセッサとシス
テムメモリ（一次又はメインメモリ）との間にキャッシ
ュメモリが存在する。メモリアドレスは、要求されたア
ドレス位置とキャッシュの内容との間の一致を定める連
想メモリマップを用いることによって解釈される。要求
されたデータ項目がキャッシュ内に存在する場合には、
メインメモリへの要求が連想メモリによって禁止され、
所望のデータがキャッシュからその要求を発しているプ
ロセッサへ送られる。システムメモリは、要求されたデ
ータ項目がキャッシュ内にない場合だけアクセスされ、
このような場合には、必要なデータがシステムメモリか
らフェッチされ、次いで、その要求を発しているプロセ
ッサへ供給される。このようなキャッシュメモリ機構の
動作は、アドレス及びメモリ使用の発生においてプログ
ラムによって示される局部の現象に基づいている。

本質的に、キャッシュメモリは、関連するプロセッサの
ためのシステムメモリへのウィンドウを備え、空間的及
び一時的な位置でのデータ参照のために高速アクセスを
行なうことができる。

然し乍ら、キャッシュは、システムメモリに存在するデ
ータ項目を複製するので、システムメモリとシステムの
種々のキャッシュメモリとの間でデータの一貫性を維持
することが重要である。

個々のプロセッサに個々の別々のキャッシュメモリが設
けられているときには、キャッシュが共有データの異な
ったバージョンを保持することになり、このような全て
の異なったバージョンを更新するためのステップを実行
しなければならなくなる。更に、特定のプロセッサがそ
のキャッシュで情報を変更するときには、その変更され
た情報をメインメモリにおいて取り換えて、種々のキャ
ッシュとメインメモリとが記憶されたデータの有効なコ
ピーを常に保持しなければならない。

発明が解決しようとする課題 キャッシュの一貫性は、「スマート」メモリ及びより一
般的なソフトウェア制御の使用を含む多数の技術によっ
て達成されている。例えば、パスをベースとする一貫性
機構は、全てのシステムプロセッサによって共有された
メインメモリへの共通の経路を使用しており、これは、
他の全てのキャッシュによるメモリへの書き込みやミス
を共通のバスを介して監視することにより各キャッシュ
がトランザクションデータ情報の更新されたディレクト
リを維持するようにすることによってデータの非一貫性
を検出することを＠提とする。この共通バス解決策は、
非常に複雑で且つ特殊なＶＬＳＩチップを必要とするの
に加えて、共有バスを介して所期の量のデータが転送さ
れることがら重大な問題が生じるために、限定された数
のプロセッサでしか動作することができない。

ソフトウェアで制御される一貫性機構は、マルチプロセ
ッサ機構において益々使用されるようになってきており
、これはシステム制御されるマイクロコードの使用に基
づくものであり、このマイクロコードは、共有されたメ
モリの領域を追跡し，種々のプロセッサキャッシュにコ
マンドを中継し、共有されたデータの一貫性が保持され
るよう確保する。このコマンドは、例えば、共有された
メモリが別のプロセッサによって変更されたと分かった
場合にプロセッサキャッシュのパージを開始する。これ
らの機構においては、キャッシュの同期が重要であり、
プロセッサキャッシュのパージがあまり頻繁である必要
がある場合にシステム速度を不当に制約することが考え
られる。

キャッシュー貫性機構において２つの最も一般的に使用
されている技術は、「ライトバック」方法と、「ライト
スルー」方法である。ライトバック方法では、変更され
たデータ又は新たなデータが個々のキャッシュにのみ書
き込まれ、メインメモリには書き込まれない。各キャッ
シュタグには追加ビットが組み合わされており、これは
、当該キャッシュ入力が変更されるときにセットされる
。変更されたデータをキャッシュにおいて取り換えるべ
きときには、識別ビットがセットされたと分かった場合
だけその値がメインメモリに書き込まれて戻される。こ
の方法は、個々のキャッシュ内のデータ項目を変更する
ときしかメインメモリへの書き込みが必要とされないの
で非常に効率的であるが、メモリに駐留するデータを常
時監視して更新することが必要であり、メインメモリが
多数のプロセッサ感で共有されるときに問題が生じる。

書き込まれているセグメントを含む完全なブロックをメ
インメモリからリフィルせずにプロセッサがキャッシュ
のセグメントへ書き込みできるようなシステムでは、こ
れらの問題が顕著なものとなる。

ライトスル一方法では、メインメモリへの全てのキャッ
シュ書き込みを直ちに伝播すると共に、全てのシステム
リソースにアクセスできる供給プロセッサーキャッシュ
インターフエイスを設けることによりデータの一貫性が
確保される。しかしながら、この方法では、複数の書き
込みが同時に生じた場合にメインメモリへの不必要な要
求されるためにキャッシュの性能が著しく低下すること
がある。

最も一般的なキャッシュー貫性に関連した共通の問題は
、データトランザクション要求の受け入れが共有メモリ
の現在状態で決まることである。

換言すれば、プロセッサ又は他のシステムユニットから
の入ってくるデータ要求は、その要求がデータの非一貫
性を発生しないことが確立されない限り受け入れられな
いし又実行もされない。特定の要求がプロセッサキャッ
シュ及びメインメモリによって供給されたデータ間に非
一貫性を生じるかどうかに拘りなく、入ってくる全ての
プロセス要求が実行についてスケジュール決めされるこ
とが重要である高性能システムではこの制約によってか
なりの制限がもたらされる。

課題を解決するための手段 簡単に述べると、本発明のシステムによれば、１）デー
タトランザクション要求が処理されるにつれて１組の所
定のデータ非一貫性状態の１つが生じたときを検出する
ことができ、そして２）オペレーションを正しく且つ一
貫したやり方で実行できるようにデータの非一貫性を修
正できるような改良されたキャッシュー貫性機構が提供
される。

好ましい実施例によれば、本発明のキャッシュー貫性機
構は、次の２種類のデータ非一貫性状態に向けられる。

即ちｌ）書き込まれるべき俟置があるプロセッサユニッ
トのキャッシュに存在するときのシステムユニットから
メインメモリへの書き込み動作の要求（この場合は、キ
ャッシュのデータが「古い」ものであり、それに関連し
たプロセッサは、この古いデータの使用が阻止されねば
ならない）；及び２）システムユニットによりメインメ
モリの読み取り動作が要求されそして読み取られるべき
位置があるプロセッサのキャッシュに書き込みできるか
又は既に書き込まれているとき（この場合は、メインメ
モリのデータが「古い』ものであり、要求を発している
ユニットへ返送されるデータはキャッシュからの更新さ
れたデータでなければならない）。

このキャッシュー貫性機構は、システム制御ユニット（
ＳＣＵ）を有するマルチプロセッサシステムに特に使用
されるものであり、このＳＣＵは、プロセッサシステム
を構威する複数の中央処理ユニット（ＣＰＵ）の並列動
作をメインシステムメモリ、Ｉ／Ｏ装置及びコンピュー
タシステムの他の要素に関連して調整するためのもので
ある。

ＳＣＵの主たる機能の１つは、全てのシステムユニット
を最も効率的に並列動作できるようにメモリアクセスを
管理することである。本発明の１つの特徴によれば、上
記したデータ非一貫性状態の１つが存在することは、Ｓ
ＣＵをベースとするマルチプロセッサシステムにおいて
、各プロセッサキャッシュに対するキャッシュディレク
トリのコピーを維持する手段をＳＣＵに設けることによ
り検出される。ＳＣＵによって要求が処理されるたびに
、アドレスデータがディレクトリに記憶されたものと比
較され、一致の存在が判断される。ディレクトリは、キ
ャッシュ位置におけるメモリデータの物理的なアドレス
と、メインシステムメモリを更新せずにデータがキャッ
シュに書き込まれたかどうかを表わす追加状態ビットと
を含む。書き込み動作の場合、一致が見つかると、即ち
メモリ書き込みがキャッシュ内の位置に「ヒット」する
（当たる）と、ＳＣＵは所定の固定シーケンスを実行す
るようにされる。書き込み状態ビットがセットされない
場合には、ＳＣＵがそのキャッシュ位置を無効とするコ
マンドを当該プロセッサに中継する。しかしながら、書
き込み状態ビットがセットされた場合には、ＳＣＵは、
最初にデータをメインメモリに書き込んで戻しそしてそ
のキャッシュコビーを無効にするようにプロセッサに指
令する。

メインメモリから全ブロックをリフイルせずにキャッシ
ュブロックのセグメントへプロセッサユニットが書き込
みできるようにされたコンビュ一タシステムでは付加的
な複雑さが存在する。その結果、部分的に有効なキャッ
シュブロックが存在することになる。これらのブロック
がキャッシュリフィル要求に応答してメインメモリへ書
き込まれて戻されるか又は別のプロセッサへ送られると
きには、セグメント化されたデータを適当に合流させる
ことが必要となる。本発明のキャッシュ一致機構は、こ
のような状態の存在を検出し、それに応答して、メモリ
システムの前端に設けられたバッファにおいて必要な合
流動作を実行するようにされる。

改良されたキャッシュー貫性機構のここに示す実施例で
は、ＳＣＵをベースとするプロセッサシステムは、６４
バイト書き込みのキャッシュブロックで動作するように
され、そしてプロセッサは、メインメモリからのりフィ
ルなしにキャッシュブロック内に選択されたロングワー
ドを書き込みできるようにされる。ＳＣＵは、このよう
な事象の発生を確認し、それに応じてキャッシュディレ
クトリをマークし、そしてその後に他のキャッシュディ
レクトリをチェックして、特定のキャッシュブロックが
他のプロセッサのキャッシュにおいて無効にされる必要
があるかどうか判断される。

要求が処理されたときには、ＳＣＵがその要求を発して
いる元のプロセッサへ応答を中継する。本発明の機構は
、要求された動作が別のＣＰＵのキャッシュブロックへ
の書き込みであることがＳＣＵによって決定されない限
り、要求を発しているプロセッサがＳＣＵからの応答を
待機せずにその動作を進めることができる。別のキャッ
シュブロックが実際に関与する場合には、その要求を発
しているプロセッサが処理を進める前にＳＣＵの応答を
強制的に待機するようにされ、これは、他のシステムプ
ロセッサから見た同じ順序でメモリ書き込みが生じるこ
とを確保する。

又、本発明によれば、メモリリフィル動作は、２つの別
々のトランザクションとして処理され、その第１は、Ｓ
ＣＵがプロセッサから入ってくるデータトランザクショ
ン要求を処理するときに生じ、そしてその第２は、ＳＣ
Ｕがその後にメモリからの要求を受け取ってその要求デ
ータをプロセッサへ中継するときに生じる。データの非
一貫性状態及び他の競合の存在に対するチェックは、各
トランザクションごとに行なわれ、従って、ＳＣＵは、
繰返し周期中に他のデータ要求を自由に処理する。この
ような機構では、キャッシュ競合が検出された場合だけ
ＳＣＵがデータトランザクションの固定シーケンスを実
行しなければならない。

データ非一貫性の修正は、最小のハードウエアを使用す
るだけで正しい実行シーケンスを制御できるようにマイ
クロコード制御のもとで行なわれる．本発明の更に別の
目的及び項かは、添付図面を参照した以下の詳細な説明
より明らかとなろう。

実施例 本発明は、種々の変更及び修正が考えられるが、一例と
して添付図面を参照してその特定の実施例について詳細
に説明する。然し乍ら、本発明は、ここに開示する特定
の形態に限定されるものではなく、特許請求の範囲で規
定した本発明の精神及び範囲内に入る全ての変更や修正
を網羅するものとする。

添付図面の特に第１図は、マルチプロセッサシステム１
０の簡単なブロック図であり、該システムは、複数の中
央処理ユニット（ＣＰＵ）１２を用いており、これらの
システムＣＰＵがシステムに対して共通のメモリｌ６を
共有できるようにすることによりこれらＣＰＵの同時の
即ち並列の動作を行なえるようになっている。メインメ
モリ１６自体は、典型的に、複数のメモリユニットｌ６
Ａ及び１６Ｂを備えている。システム制御ユニット（Ｓ
ＣＵ）１４は、ＣＰＵ１２をメインメモリ１６にリンク
すると共に、入力／出力（Ｉ／Ｏ）制御器ｌ８にリンク
する。このＩ／Ｏ制御器は、一般的にはプロセッサシス
テムがそしてより詳細にはＣＰＵがシステムの適当なＩ
／Ｏインターフェイス２０及び当該Ｉ／Ｏユニット２０
Ａを経て外界と通信できるようにする。又、ＳＣＵ１４
は、種々のシステムモジュールをサービスプロセッサ／
コンソールユニット（ＳＰＵ）２２ヘリンクし、このユ
ニットは、プロセッサシステムの全オペレーションにつ
いての状態の決定及び制御を含む通常のコンソール機能
を実行する。特に、ＳＣＵＩ４は、複数のＣＰＵ１２と
通信する手段をＳＰＵ２２に与えると共に、ＣＰＵ内の
全ての記憶素子へのアクセスを与える。

ＳＣＵｌ４及びメインメモリ１６にボートで結合された
全てのシステムユニット間の、より詳細には、各ＣＰＵ
１２とメインメモリｌ６との間の効率的な通信は、プロ
セッサシステムの効率的な並列動作を確保する上で重要
である。この動作は、ＳＣＵ１４及びメインメモリｌ６
をリンクする専用のインターフエイス手段３０によって
与えられる。このインターフエイス３０は、ＳＣＵにボ
ート結合されたＣＰＵｌ２又はＩ／Ｏユニット２０Ａの
各々から受け取ったメモリ対話コマンド又は信号に応答
して、メインメモリｌ６を構或する種々のモジュールを
インターフエイス及び制御する手段をＳＣＵ１４に与え
る。

又、第１図に示すように、各々のＣＰＵ１２は、典型的
に、メモリ、Ｉ／Ｏユニット及び他のＣＰＵユニットへ
のＣＰＵインターフエイスを与えるメモリユニット（Ｍ
ユニット）２４を備えている。特に、このＭユニットモ
ジュールは、通常は仮想のメモリ参照を受け入れ、この
参照を物理アドレスに変換し、そしてＳＣＵ１４及びイ
ンターフェイス手段３０を介してメインメモリ内にある
メモリデータへのアクセスを開始するか、より重要なこ
とは、ＣＰＵに関連したローカルキャッシュ内にあるメ
モリデータへのアクセスを開始するための手段として働
く。第１図に示すシステムは、パイプライン式の仮想メ
モリをベースとするコンピュータシステムである。パイ
プラインの考え方によれば、ＣＰＵ１２は非均等プロセ
ッサであって、これは、個々の命令が実行前に分割され
るところの特定のタスクを専用に実行し且つそれに最も
適するようにされた１組の特殊機能ユニットを備えてい
る。従って、各ＣＰＵ１２は、命令ユニット（Ｉユニッ
ト）２６も備えており、これは、命令をフエツチし、オ
ペレーションコード（ＯＰコード）及び指定子をデコー
ドし、オペランドをフェッチしそしてシステムプログラ
ムカウンタ及び実行ユニット（Ｅユニット）２８を更新
する。この実行ユニットは、他のＣＰＵモジュールによ
って送られたデコードされた命令及びフエッチされたオ
ペランドに対する実行段として働くものである。このよ
うなシステムの実施例では、ＳＣＵの制御のもとでメイ
ンメモリ１４を効率的に共有することにより４つまでの
ＣＰＵが同時に並列に動作される。

第１図において、各ＣＰＵｌ２のＭユニット２４は、メ
インキャッシュ２５を備えており、これは、■ユニット
２６及びＥユニット２８が、メインメモリｌ４の通常の
アクセス時間によって許されるものよりも相当に高い速
度でデータを各々アクセス及び処理できるようにする。

メインキャッシュ２５は、プロセッサが現在オペレーシ
ョンの実行に必要としがちなデータ（典型的には、最も
最近使用された命令及びデータ項目）を一時的に保持す
る。キャッシュは、必要とされるアドレス位置とキャッ
シュの内容との間の対応を定める連想メモリマップを用
いることによりメモリアドレスを解読する。システムは
、要求されたデータ項目がキャッシュ内に存在すること
が分かった場合に、メインメモリへの要求を禁止しそし
てプロセッサにより要求されたデータをキャッシュから
供給することによって動作する。メインメモリｌ６は、
要求されたデータ項目がキャッシュ２５にない場合にの
みＳＣＵ１４によってアクセスされ、この場合、データ
はシステムメモリからフエツチされそしてその要求を発
しているユニットへ供給される。キャッシュ２５は、コ
ンピュータプログラムにおけるローカリテイの現象に基
づいて動作し、システムメインメモリ１６に対するウイ
ンドウを与えると共に、空間的及び一時的の両方のロー
カリテイでデータ参照への高速アクセスを許す。

キャッシュ２５は、平均ベースで、ＣＰＵＩ２がメイン
メモリｌ６のアクセス時間よりも相当に高い速度でデー
タを処理できるようにする。キャッシュ２５は、典型的
に、データエレメントの選択された所定のブロックを記
憶するための手段を備えており、そしてＭユニット２４
と共に、指定のデータエレメントをアクセスするために
システムユニットから要求を受け取る手段、データエレ
メントがキャッシュにブロックとして記憶されるかどう
かをチェックする手段、そして指定のデータエレメント
を含むブロックのデータがこのように記憶されないとき
に動作して、ＳＣＵを経て、メインメモリ１６からのデ
ータの指定のブロックを要求しそしてそのデータブロッ
クをキャッシュ２５に記憶するための手段を形成する。

換言すれば、キャッシュは、メインメモリに対する「ウ
インドウ」を与え、ＣＰＵｌ２が最も必要とするであろ
うデータを含むことになる。ＣＰＵｌ２によって必要と
されたデータエレメントがキャッシュ２５内に見つから
ない場合には、データエレメントがメインメモリｌ６か
ら得られるが、このプロセス中には、付加的なデータを
含む全ブロックがメインメモリｌ６から得られてキャッ
シュ２５へ書き込まれる。時間及びメモリ空間について
のローカリテイの原理により、ＣＰＵがデータエレメン
トを次に所望するときには、既にアドレスされたデータ
エレメントを含むブロックにこのデータエレメントが見
つかる見込みが高くなる。それ故，キャッシュ２５がＣ
ＰＵにより所望されるデータエレメントを既に含む見込
みが高くなる。一般に、キャッシュ２５はメインメモリ
１６よりも相当に高い速度でアクセスされるので、メイ
ンメモリ１６は、キャッシュ２５よりも比例的にゆっく
りとしたアクセス時間をもつことになり、ＣＰＵの平均
性能を著しく低下することはない。それ故、メインメモ
リ１６は、低速で且つ安価なメモリエレメントでよく且
つこれで一般的に構或できる。

’ＶＡＸ−　１　１’デジタルコンピュータのキャッシ
ュ及びメインメモリと同様のキャッシュ２５及びメイン
メモリｌ６に対する例示的な構或が、参考としてここに
取り上げるデジタルエクイツプメント社発行のレビ−氏
及びエクハウス二世氏著の「コンピュータプログラミン
グ及びアーキテクチャーＶＡＸ−１１４　　（１９８０
年）の第ｌｌ章、第３５１−３６８頁に掲載されている
。このような’ＶＡＸ’　ブランドのデジタルコンピュ
ータは、米国、マサチューセッツ州、メイナード、パウ
ダーミル・ロード、１１１のデジタルエクイップメント
社から入手できる。

メインメモリｌ６は、「マルチプロセッサシステムのシ
ステム制御ユニットをシステムメモリとインターフェイ
スする方法及び手段』と題する上記ガグリアード氏等の
米国特許出願に開示された形式のセグメントベースの構
成を有するのが好ましい。そこに開示されたように、メ
インメモリ１６は、４つの拡張ｌ６進サイズのメモリモ
ジュールで形成された少なくとも１つのメインメモリユ
ニット（ＭＭＵ）を備えており、その各々は、ＩＭビッ
トＤＲＡＭを用いて６４メガビットの記憶容量を与える
のが好ましい。メモリへの又はメモリからの全てのＣＰ
Ｕアクセスは、選択されたバイト数（典型的に６４バイ
ト）より成るブロック増分でＳＣＵｌ４　（第１図）を
介して行なわれる。

第２図は、ＣＰＵキャッシュ２５及びメインメモリ１６
の記憶区分の好ましい編成を示すブロック図である。図
示されたように、メインメモリ１６のＭＭＵのデータ記
憶区分は、一対のセグメント３４、３６より成り，その
各々は一対のメモリバンクを構威する。４つのメモリバ
ンクが各々３８、４０、４２及び４４で示されている。

これらのメモリバンクはＤＲＡＭベースのものであり、
例えば、６４メガバイトのデータを各々記憶することが
できる。このようなセグメントベースのメモリの一般的
な編成は、通常のものであるが、メモリバンクに対する
メモリアドレスがブロックの境界においてインターリー
ブされていることが重要である。このような構成が第２
図に示されており、ここでは６４バイトの好ましいデー
タブロックサイズについてのインターリーブが示されて
いる。第１ブロック（ＢＬＯＣＫＯ）は、バイトアドレ
スＯ−６３が組み合わされ、第１メモリセグメント３４
の第ｌバンク３８に記憶され；次に続くブロックはバイ
トアドレス６４−１２７を構成し、即ち第２ブロック（
ＢＬＯＣＫＩ）を構成するもので、第２メモリセグメン
ト３６の第ｌメモリバンク４２に記憶され；第３ブロッ
ク（ＢＬＯＣＫ２）はバイトアドレス１２８−１９１が
組み合わされ、第ｌメモリセグメント３４の第２メモリ
バンク４０に記憶され；第４メモリブロック（ＢＬＯＣ
Ｋ３）はバイトアドレス１９２−２５５が組み合わされ
、第２メモリセグメント３６の第２メモリブロック４４
に記憶され；そして第５ブロック（ＢＬＯＣＫ４）はバ
イトアドレス２５６−３　１　９が組み合わされ、第１
メモリセグメント３４の第１メモリバンク３８に記憶さ
れ、等々となる。

又、第２図に示すように、キャッシュ２５は、一般的に
４５で示された入力アドレスレジスタと、一般的に４６
で示されたタグ記憶部と、一般的に４７で示されたデー
タ記憶部とを備えている。データ記憶部４７は、データ
エレメントの所定のブロックの選択された１つを記憶す
るように構成される。指定のブロックのデータがデータ
記憶部４７に記憶されるかどうかを指示するために，タ
グ記憶部４６は、ブロックに関連した各タグを記憶する
ように構威される。更に、キャッシュ２４は、指定のブ
ロックに対するデータがキャッシュメモリに記憶される
かどうかをチェックするための比較器４８のような手段
を備えている。

第２図に特に示すように、タグは、ブロックアドレスの
上部を構成する。フィル要求に応答して、メインメモリ
のアドレスされたブロックは、データ記憶部４７の１つ
以上の所定のスロットに転送される。所与のブロックに
関連したスロットは、インデックスｊでインデックスさ
れる。特定のブロックに対するインデックスｊ及びタグ
は、そのブロックのブロックアドレスを指定する。それ
故、所望のバイ１・のアドレスが入力レジスタ４５に受
け取られたときには、インデックス部分ｊがタグ記憶部
４６の少なくとも１つの対応するスロットを指し、アド
レスされたタグが比較器４８に送られて、バイトアドレ
スで指定されたタグと比較される。

比較器４８が一致を検出すると、「ヒット」が指示され
、インデックスｊでインデックスされたデータ記憶部４
７のブロックに所望のバイトが含まれたことを示す。さ
もなくば、比較器４８は「政ス」を指示し、それに対応
するフィル要求をＳＣＵに入れる。次いで、フィル要求
は４つのメモリバンク３　８−４　２の対応する１つに
送られ、これは、入力レジスタ４５からのブロックアド
レスにより指定されたブロックを記憶する。

第２図に更に示すように、タグ記憶部４６及びデータ記
憶部４７は、２０４８個の別々のスロットか或いは各々
ＩＫの別々のスロットの２つの個別のバンクかのいずれ
かを備えていて、これらは１１個の２進ビットを有する
インデックスｊによって指定されるのが好ましい。これ
らの２進ビットは、バイトアドレスのビット６ないしｌ
６に配置される。バイトアドレスのビットＯ−５は、ア
ドレスされたブロック４５のバイトｉの特定の位置を指
定する。典型的に、各データエレメントは、「クオドワ
ードｊを形成する８個の隣接バイトを含んでいる。クオ
ドワードにおけるバイトの位置は、バイトアドレスのビ
ットＯ−２を含む「バイト残部」によって指定される。

ブロックにおけるクオドワードの位置は、バイトアドレ
スのビット３−５により指定された「クオドワード残部
］によって指示される。

第４図は、第１図に示した形式のマルチプロセッサシス
テムを構或する複数のＣＰＵのキャッシュ状態を維持す
るためにＳＣＵ内に定められたグローバルなキャッシュ
タグディレクトリの好ましい構造を示している。

第３図に示すように、グローバルなタグ構造体１００は
、ＲＡＭＯ％ＲＡＭ１、ＲＡＭ２及びＲＡＭ３と指定さ
れた４つの別々のＲＡＭ構造体を備えており、これらは
、対応するＣＰＵＯ，ＣＰＵＩ、ＣＰＵ２及びＣＰＵ３
内のキャッシュに対応するものである。各々のＲＡＭ構
造体は、１つのＣＰＵ専用にされ、好ましい実施例によ
れば、４キロバイト（４Ｋ）の容量を有し、４つの別々
のｌ−Ｋ区分を定めることができる。第１区分１０２は
、ＣＰＵに対してセットＯ状態を保持し、一方、第２区
分１０４は、セットｌ状態を保持する。第３及び第４区
分１０６及び１０８は、タグのディレクトリに対して各
々必要とされず、従って、未使用のま）である。然し乍
ら、未使用のＲＡＭ区分は、他の保護目的で効果的に使
用することができる。これらの区分は、ＳＣＵによって
しばしばアクセスする必要のあるロックディレクトリの
ような他の参照ディレクトリを維持するのに特に有用で
ある。これについては、本発明の譲受人によって譲渡さ
れた「マルチプロセッサシステムにおいてメモリアクセ
スオペレーションを同期及び処理する方法Ｊと題するア
ーノルド氏等の米国特許出願第３５６，５４１号に開示
されている。

該特許出願には、ロックディレクトリを維持するための
グローバルなタグ構造体１００における未使用ＲＡＭ区
分のｌつと、ロック要求を含むメモリアクセストランザ
クションの競合のない処理を確保するための関連リザー
ブリストとの使い方が開示されている。

第３図を参照すれば、書き込みイネーブル（ＷＥ）ライ
ン１１０、１１２、１１４及びｌ１６は、４つのＲＡＭ
構造体ＲＡＭＯ−３に対応するタグの書き込みをイネー
ブルするために設けられている。アクセス要求を伴うメ
モリアドレスは、マルチブレクサ構成体１１８を経て送
られ、その「選択」信号１２２は、特定のＣＰＵのセッ
トＯ及びＩに対するキャッシュ状ｆａＭをブックアップ
するのに用いられる。第２図には、各々のＲＡＭ構造体
に対して１組のＲＡＭ　Ｌ，か示されていない。

実際には、各々のＲＡＭ構造体に対して典型的に複数の
ＲＡＭが設けられる。第１図に示す実施例においては、
例えば、各ＲＡＭグループに対して６個のＲＡＭが設け
られている。又、３ビットのタグ「状態Ｊ入力１２４が
ＲＡＭ構造体の各々に送られ、キャッシュ状態は繰返し
の読み取りサイクル中に出力データとして順次に読み取
られ，方、対応するメモリアドレスも出力に発生される
。

これらのアドレスは比較ユニットに通され、メモリアク
セス要求に対応するメモリアドレスと、対応するキャッ
シュブロックの内容との間の一致が存在するかどうかの
判断が行なわれる。

上記したグローバルなタグ構造体は、個々のＣＰＵ内の
キャッシュブロックの状態を維持し且つ読み出すのに特
に用いられることが重要である。

典型的に、キャッシュ状態は、特定のキャッシュブロッ
クが、無効であるか読み取りであるか部分書き込みであ
るか全書き込みであるかのデータを含むかどうかを指示
する。

ＳＣＵは、各ＣＰＵキャッシュの状態を監視し、それに
応じて状態ビットを調整することによりキャッシュの状
態を維持する。従って、キャッシュタグディレクトリは
、所与のメモリアクセストランザクションに対し要求を
発しているユニットとターゲットユニットとの両方のキ
ャッシュ状態を確認するための便利な手段をＳＣＵに与
える。

ＳＣＵは、メモリのブロックがＣＰＵキャッシュ内に存
在するかどうかを判断するためにアドレスの比較を行な
うだけでよい。更に，アドレスされたブロックに対応す
るタグ状態を読み取ることにより、ＳＣＵは、ブロック
に存在するデータが無効であるか読み取りであるか部分
書き込みであるか完全書き込みであるかを迅速に判断す
ることができる。全てのメモリトランザクションは当然
ながらＳＣＵを経て流れねばならないので、ＳＣＵのキ
ャッシュタグディレクトリは、各ＣＰＵの現在キャッシ
ュ状態を維持するためのフールプルーフ手段として働く
。この情報を用いると、ＳＣＵは、以下で詳細に述べる
ように、データの非一貫性状態を検出しそして修正でき
るようになる。

第４図には、本発明のキャッシュー貫性機構に基づいて
メモリアクセス要求を最初に処理するのに含まれる事象
シーケンスを示すフローチャートが示されている。この
手順は、ＳＣＵ及びＣＰＵを「無効』状態にセットする
ことによりこれらに関連したタグＲＡＭを初期化するこ
とによって開始される。この初期化は、ステップ１５１
において行なわれる。次いで、ステップ１５２において
、ＣＰＵより発生されたメモリアクセス要求がそれに対
応するＭユニットにおいて受け入れられる。次のステッ
プ１５３において、その要求が読み取り動作に対するも
のか書き込み動作に対するものであるかの判断がなされ
る。その要求が読み取りに対するものである場合には、
ステップｌ５４がアクセスされ、その要求に関連したメ
モリアドレスがＣＰＵキャッシュ内のブロック「ヒット
」に対応するものであるかどうかの判断がなされ、即ち
ＣＰＵチェックが行なわれて、メモリアドレスがキャッ
シュのメモリブロック内に配置されているかどうかの判
断がなされる。

ブロック「ヒット」がある場合には、ステップ１５５が
アクセスされ、ＳＣＵの参照が必要とされないので、要
求が直接実行される。換言すれば、Ｍユニットは要求を
発しているボートに応答し、そのキャッシュ内からの要
求されたデータをそこに供給する。然し乍ら、ステップ
１５４の答えが否定である場合、即ちキャッシュ内にブ
ロック「ヒット」がない場合には、ステップ１５６がア
クセスされ、Ｍユニットは読み取りリフイル要求をＳＣ
Ｕに発生し、メインメモリから要求された読み取りデー
タを得るように試みる。その後、ステップ１５７におい
て、ＳＣＵのタグＲＡＭは、それらの状態が読み取りリ
フィル要求に対応する入力のための元の無効状態から読
み取り入力の状態へと変えられる。

ステップ１５７の終わりに、タグＲＡＭの状態を無効入
力から読み取り入力へ変化させた事象は、メモリから必
要なデータをフェッチしてそれを要求を発しているＣＰ
Ｕのキャッシュへ送るＳＣＵの動作であることに注意さ
れたい。この時点で、ＳＣＵのキャッシュタグディレク
トリの対応する入力が読み取り入力を有するものとして
マークされる。その後、他のＣＰＵがそのデータを参照
する場合には、ＣＰＵがそのデータを読み取りの目的で
のみそのキャッシュ内に保持することを確認することが
できる。この構成は、メモリ内の同じ位置が他のあるＣ
ＰＵによって書き込まれるべき場合にそのキャッシュの
内容を無効にするためにＣＰＵを後で指示する際に効果
的である。キャッシュタグの状態が重要になるのはこの
ような後の固定動作の場合である。

ステップ１５３の判断が、処理されている要求が書き込
み要求であることを指示する場合には、ステップ１５８
に進み、アドレスされたメモリ位置がＣＰＵキャッシュ
内に存在するかどうかのチェックが行なわれ、即ちキャ
ッシュにブロック「ヒット」があるかどうかの判断がな
される。このような「ヒットＪがないことが分かると、
ステップ１５９がアクセスされる。

ステップ１５８において、ＣＰＵキャッシュ内にブロッ
ク「ヒット」があることが分かった場合には、ステップ
１５９がアクセスされ、そのブロックに対する対応書き
込みビットがセットされたかどうかのチェックが行なわ
れる。この質問に対する答えがイエスの場合には、ＳＣ
Ｕから既に書き込み許可を得ているブロックにＭユニッ
トが書き込みすることが指示される。従って、ＳＣＵの
観点から、ＳＣＵの参照は必要とされず、ＣＰＵキャッ
シュのメモリブロックに書き込みすることによってメモ
リアクセス要求を実行することができる。然し乍ら、ス
テップ１５９においてキャッシュ内のブロック「ヒット
Ｊがその書き込みビットをセットしないことが分かった
場合には、ＣＰＵが読み取りの目的のみでメモリブロッ
クを既にフェッチしており、従って、そのブロックへの
書き込みが許可されていないことが指示される。

この点において、Ｍユニットは、ステップ１６１でＳＣ
Ｕに書き込みリフィル要求を発生する。

ステップ１６２において、メインメモリへのアクセスの
後に、要求された書き込みデータがＳＣＵから受け取ら
れる。ＳＣＵにとって、これは、要求を発しているＣＰ
Ｕのキャッシュに返送されて記憶されるデータがそこに
書き込めることを意味する。その後、ステップ１６３に
おいて、ＣＰＵは、ＳＣＵから受け取ったデータの少な
くとも一部分の上部に新たなデータを書き込む。次いで
、ステップ１６４に達し、ＳＣＵタグＲＡＭの状態が更
新されて、手前の読み取り入力から全書き込み入力へと
変換される。この点において、その前は読み取りブロッ
クのみであったキャッシュブロックがその状態を変化し
、ここでブロック内にデータが完全に書き込まれたこと
を指示する。既に読み取り許可されたデータブロックは
新たなデータが上に書き込まれているので，この書き込
まれたデータブロックが完全に有効であることを指示す
るようにＳＣＵタグＲＡＭの状態が調整される。

Ｍユニットが書き込み要求を処理しておりそしてステッ
プ１５８における判断がキャッシュ内にブロック「ヒッ
ト」がないことを指示し、即ちブロック「ミス」である
ことを指示する場合には、ステップ１６５において、メ
モリに書き込むべきワードがロングワード整列されるか
どうかについての判断がなされる。ロングワード当たり
１つの有効ビットが与えられるのが好ましいので、ロン
グワードの識別は重要である。この構成によれば、Ｍユ
ニットが特定のバイトを書き込まねばならない場合に、
その特定のバイトを含むブロック全体をメインメモリか
らフエツチし、フエツチされたブロック内の１つ以上の
バイトを新たなデータバイトと交換しなければならない
。これは、Ｍユ二ットがメモリからのりフィルを行なう
ときに、メモリから全てのデータを得て、それをキャッ
シュに入れるからであり、全ブロックが有効であるから
、全ての有効ビットがセットされる。Ｍユニットがバイ
トを書き込むべき場合には、そのバイトを含むロングワ
ードが選択され、そのバイトの古い値の上に新たな値が
書き込まれる一方、全ての有効ビットがセット状態とし
て保持されて、全ブロックが有効状態に保たれる。整列
されたロングワードの形態でないもの、例えば、ロング
ワード境界に整列されないバイト又はロングワードをＣ
ＰＵが書き込むべきときにこの逐次の手順をたどるもの
とする。

Ｍユニットがキャッシュミスを有するが、整列されたロ
ングワード又は多数の整列されたロングワードを書き込
んでいる場合には、メモリからデータを実際にフェッチ
する必要がない。むしろ、ＣＰＵは空ブロックという有
効なものでスタートすることができる。ＳＣＵは、キャ
ッシュ内の空位置でスタートし、ロングワードをその位
置に書き込み、そしてそのロングワードに対応する有効
ビットのみを発生時にセットする。これらの状態のもと
で、ＳＣＵは、ブロックを部分書き込みとして指定し、
これは，ブロック内の全てのロングワードが有効である
のではないことを意味する。

書き込まれているデータの量が完全なロングワードの全
部ではない場合には、この機構が遮断し、システムは、
書き込みリフイル機構に進み、メインメモリから全ブロ
ックをリフイルする。実際の観点において、書き込みリ
フイル要求は、メモリから全ブロックをフエッチするこ
と、即ち非常に時間浪費な動作を必要とする。整列ロン
グワードの場合には、Ｍユニットは、要求されたデータ
がメインメモリから送られるのを待機する必要なくその
動作サイクルを続ける。従って、メモリ参照がメモリの
整列されたロングワードを含むときに最適な性能が得ら
れる。

第４図を参照すれば、ステップ１６５のテストにおいて
、メモリ参照に１つ以上の整列されたロングワードが含
まれることが指示されると、Ｍユニットは、ステップ１
６６において、ロングワード書き込み更新をＳＣＵに送
る。次のステップ１６７において、Ｍユニットは新たデ
ータをそのキャッシュに直ちに書き込む。次いで、ステ
ップ１６８において、対応する単一の又は多数のロング
ワード有効ビットがセットされる。同時に、ＳＣＵタグ
ＲＡＭは、それらの状態が無効入力から部分書き込み入
力に変化されている。これは、全てのロングワードがそ
のブロック内で有効ではないことを指示する。

ステップ１６５のテストにおいて、参照されているロン
グワードが整列されたワードでないことが指示された場
合に、ステップ１６９がアクセスされ、Ｍユニットはス
テップ１６０において書き込みリフイル要求をＳＣＵに
発生する。要求されたデータがＳＣＵによって返送され
ると、データはステップ１７０においてＣＰＵキャッシ
ュに書き込まれる。その後に，ステップ１７１において
、メインメモリからＳＣＵによって早期に返送された書
き込みデータの上に新たなデータが書き込まれる。書き
込みリフイル要求を処理する際に、ＳＣＵタグＲＡＭ状
態は、無効状態から完全書き込み状態に変えられる。Ｓ
ＣＵタグＲＡＭのこの更新は、ステップ１７２において
生じる。従って、たとえ全ブロックがＳＣＵによってメ
インメモリから返送されてその後にキャッシュ内に部分
的にオーバーライトされたとしても、ＣＰＵキャッシュ
内のデータの完全なブロックはこの時点で有効である。

メインメモリ自体については、読み取りリフィル要求と
書き込みリフイル要求との間に区別はないことに注意さ
れたい。タグＲＡＭの状態が読み取り又は書き込み状態
のいずれかとして維持される場合にＳＣＵ段においてこ
の相違が生じ、これは、キャッシュの一貫性競合を決定
する上で重要である。第４図のフローチャートについて
与えられた上記の説明は、Ｍユニット内のキャッシュの
状態により決定された小象の基本的な流れ（読み取り／
書き込み、ブロック「ヒット」等）を定める。種々のキ
ャッシュ状態から生じる種々のオプションの各々では、
対応するコマンドがＳＣＵに中継されて、これらコマン
ドの受け取りによりＳＣＵタグＲＡＭに対して行われる
動作が決定される。

好ましくは、ＳＣＵタグＲＡＭの状態を指定するのに２
ビットコードが使用される。より詳細には、ｒｏＯＪの
コードは「無効』状態を表わし、ｒ０１Ｊのコードは「
読み取り」状態を表わし、ｒｌＯＪのコードは「部分書
き込み」状態を表わし、モして「１１」のコードは「完
全書き込み」状態を表わす。タグ状態を指定する２ビッ
トフィールドにおいて、値「ｌ」の指定は対応するビッ
トの「書き込み」特性を表わす。

部分書き込み動作は、同時処理ユニット間のデータの転
送に使用されたときには、２つのメモリサイクルを含み
、その１つは、ＳＣＵが指定のデータを対応するメモリ
位置に書き込むためのものであり、そして別のサイクル
は、ターゲットプロセッサへ中継されるべきメモリ内の
同じ位置から書き込まれたデータをその後に読み出すた
めのものである。これに対し、完全書き込み動作は、単
一のメモリサイクルしか必要としない。というのは、メ
モリに書き込まれるべきデータは、夕一ゲットプロセッ
サにその後に中継されるべき全く同じデータだからであ
る。従って、ＳＣＵは、書き込み動作を介してメモリに
データを記憶しそして読み取り動作によってそれを検索
する必要がなく、むしろ、　「書き込みバス」動作と称
するものは、ＳＣＵがメモリへのデータの書き込みを開
始しそして同じサイクルにおいて同じデータをターゲッ
トプロセッサへ中継するように使用される。

従って、メモリアクセス要求は、全ての書き込みが部分
書き込みの種類のものであると考えることにより処理さ
れるが、部分書き込み動作と完全書き込み動作との区別
により重要なメモリアクセス要求を保持することができ
る。例えば、１つのプロセッサの動作により、そのキャ
ッシュ内の完全書き込み状態のデータ又は部分書き込み
状態のデータが別のプロセッサによって要求される場合
を考える。ターゲットＣＰＵ内のデータが部分書き込み
である場合には、ターゲットＣＰＵ内のデータが全ブロ
ックとして完全に有効ではなく、ＳＣＵは、そのブロッ
ク内のどのロングワードが有効であるかを判断する状態
にない。然し、リフィル要求を発しているＣＰＵは、完
全に有効なブロックを有していなければならないので、
ＳＣＵは、ターゲットＣＰＵがデータブロックをメモリ
に書き込みそしてメモリからデータをフェッチして第１
プロセッサのりフィル要求を満足するように確保しなけ
ればならない。このシーケンスは、データが部分的に書
き込まれる全ての場合に生じなければならないが、デー
タが完全に書き込まれる場合には、メモリ内のデータの
記憶をバイパスすることができる。というのは、ターゲ
ットＣＰＵ内の全データブロックが有効であり、ＳＣＵ
によって直接中継されて、リフィル要求を満たすことが
できるからである。従って、書き込みパス動作のみが要
求され、１つのメモリアクセスサイクルの実行が必要と
されるだけである。上記説明は、２プロセッサキャッシ
ュ内のＭユニットによって開始されたメモリアクセス要
求に適用される。然し乍ら、個々のプロセッサに関連し
たキャッシュは典型的にライトバック形式のものである
から、プロセッサは、メモリ内の対応位置に書き込むこ
となくそのキャッシュ内で更新されたデータを含むこと
が常に考えられる。マルチプロセッサシステムにおいて
、特に、Ｉ／Ｏ装置が公平にアクティブである場合には
、メモリデータに対するシステムユニットからの要求が
時々生じ、その最も最新のバージョンはメモリ内にはな
いがあるＣＰＵキャッシュ内に存在する。これらの状態
のもとでは、ＳＣＵは、要求を発しているシステムユニ
ットにデータを中継するために、キャッシュに最も最新
のデータバージョンを含むＣＰＵがデータを適時に対応
メモリ位置に書き込むように確保しなければならない。

データの非一貫性又はキャッシュの競合を検出して固定
する際に、典型的に、ＳＣＵから個々のＣＰＵのＭユニ
ットへ中継される例示的なメモリトランザクションコマ
ンドのリスト及び説明について以下に示す。これらのコ
マンドは、ＳＣＵとＭユニットとの間の通信信号と共に
中継されるコマンドフィールド内の特定のビットコード
によって指定される。好ましくは、コマンドフィールド
は、４ビットコードの形態で実施され、少なくとも１６
個の種々のメモリトランザクションコマンドが定められ
る。

ゲットデータ書き込みコマンド これは、アドレスされたＣＰＵのＭユニットがそのキャ
ッシュ内に存在するデータをシステムメモリ内の対応位
置に中継する一方、そのキャッシュの状態を書き込み状
態に保持することを要求するＳＣＵからのコマンドであ
る。

ゲットデータ読み取りコマンド これは、ＣＰＵキャッシュ内のデータが書き込み形態で
存在し且っ又読み取りの目的でのみ別のＣＰＵによって
要求されるときにＳＣＵによってＭユニットに中継され
るコマンドである。この場合、ＳＣＵは、指定のデータ
ブロックをそのキャッシュからメモリに書き込むように
第ＩＣＰＵに要求を出して、その要求を発しているＣＰ
Ｕがそれに読み取りアクセスを行なえるようにする。

同時に、第１のＣＰ［Ｊは、そのキャッシュ内のデータ
を読み取り状態に保持することができる。というのは，
要求を発しているプロセッサがそれに書き込みを行なう
ことによってデータを無効状態にするおそれがないから
である。その結果、元々そのキャッシュに書き込み形態
でデータを所有している第ＩＣＰＵは、ここでＳＣＵが
データを読み取り形態のみで保持するように強制される
。従って．ＣＰＵがこのブロックデー夕を書き込む必要
がある場合には、これを行なうためにＳＣＵからの許可
を再び得なければならない。これらのコマンドを実行す
る際に、ＳＣＵは、適当なキャッシュタグを参魚するこ
とによってＣＰＵキャッシュタグディレクトリのコピー
を探し、メモリアクセス要求に含まれたＣＰＵキャッシ
ュが正確な状態（無効、読み取り、部分書き込み又は完
全書き込み）であるかどうかを判断するだけでよい。

ここに示す実施例では、そのときＣＰＵＯに対して無効
状態を有する特定のメモリブロックについて、ＳＣＵが
例えばＣＰＵＯからの読み取りリフイルコマン要求を受
け取るときに、ＳＣＵは、そのキャッシュタグディレク
トリ内でタグの探索を行ない、アドレスされたブロック
が例えば別のプロセッサＣＰＵＩのキャッシュにおいて
完全書き込みであることを判断する。従って、ＳＣＵは
、ゲットデータ読み取りコマンドをＣＰＵＩに中継し、
これにより、ＣＰＵＩは要求されたデータをデータライ
トバック動作によってＳＣＵに中継するようにする。こ
れと同時に、ＳＣＵは、ＣＰＵｌのキャッシュのデータ
ブロックの状態を読み取り状態に変え、これにより、こ
れがそのキャッシュに書き込まれないようにする。

ＣＰＵＩからの書き込んで戻されるデータは、ＣＰＵＩ
内のデータの元の状態が完全書き込みであったことを考
慮すれば、書き込みパス動作によってメモリを経てその
要求を発しているプロセッサＣＰＵＯに中継される。然
し乍ら、データが元々部分書き込み形態であった場合に
は、データをメモリに書き込みそしてそれを要求を発し
ているＣＰＵに転送するのに１つの完全な書き込み／読
み取りサイクルが含まれねばならない（上記で詳細に述
べたように）。その後、ＳＣＵは、ＣＰＵＯのキャッシ
ュ内のデータの状態を元の無効状態から読み取り状態へ
変更する。その結果、ＣＰＵＯからの読み取りリフィル
要求が満足されると、両方のプロセッサＣＰＵＯ及びＣ
　Ｐ　Ｕ　ｌのキャッシュ状態が読み取り状態にセット
される。

ゲットデータ書き込みコマンド このコマンドは、タグルックアップサイクルに続いてＳ
ＣＵによりＣＰＵＩ内で完全書き込み状態にあると決定
されたｃｐｕｏからの書き込みリフイル要求によって最
も良く示される。ＳＣＵは、ＣＰＵＩにコマンド（より
詐細には、ゲットデータ無効コマンド）を発生し、ＣＰ
ＵＩにそのキャッシュからＳＣＵにデータを返送するこ
とを尋ねると同時に、ＣＰＵＩキャッシュの状態を無効
状態にセットする。その後に、データは、書き込みバス
コマンドによりＣＰＵＩＯに返送される。

この場合も、ＣＰＵＩのデータが部分書き込み形態であ
った場合にはデータの転送に含まれるメモリサイクルが
書き込み一読み取りサイクルとなる。

データトランザクションの終わりに、ＳＣＵはＣＰＵＯ
キャッシュの状態を完全書き込みに変える。

Ｉ／Ｏユニットからのデータ要求を含むゲットデータ書
き込みコマンドの場合には、上記手順が木質的に適用さ
れる。然し乍ら、要求は、ＳＣＵの直接メモリアクセス
（ＤＭＡ）読み取り要求の形態でＩ／Ｏユニットにより
開始される。この場合、ＳＣＵは、ターゲットプロセッ
サＣＰＵＩがそのキャッシュ内からのデータを書き戻し
て、その後にＳＣＵがメモリを経てその要求を発してい
るＩ／Ｏユニットへそれを中継できるように指示する。

然し乍ら、この場合、ＣＰＵＩのキャッシュ状態は、Ｓ
ＣＵによって変更されない。というのは、要求を発する
ことによってＳＣＵから受け取ったデータを操作するＩ
／Ｏユニットによってデータ非一貫性の問題が生じない
からである。

又、キャッシュの考え方はＩ／Ｏユニットに適用されな
いので、ＳＣＵがその要求を発しているユ　　応答を表
わしており、これは、要求されたデータニットのキャッ
シュ状態を監視又は変更する必要　　の転送準備ができ
たときにターゲットＣＰＵに中がない。　　　　　　　
　　　　　　　　　　　　　　継される。

リターンデータ読み取りコマンド このコマンドは、読み取りリフイル動作によって要求さ
れて中継準備できたべきデータをＳＣＵが有するときに
ＳＣＵがＭユニットに対して行なう応答を表わしている
。読み取りリフイル動作が完了すると、ＳＣＵは、ター
ゲットプロセッサのキャッシュを読み取り状態に入れる
。然し乍ら、ターゲットプロセッサにおけるデータの元
の状態が部分書き込みである場合には、プロセッサキャ
ッシュの状態がリターンデータ読み取りコマンドの後に
常に無効状態に入れられ、ブロック内の部分的に無効の
データに対するその後の部分的な書き込み又は読み取り
からキャッシュ競合が生じるおそれを除外する。

リターンデータ書き込みコマンド このコマンドは、上記コマンドに類似しており、書き込
みリフィルコマンドに対するＳＣＵの書き込みＯＫコマ
ンド このコマンドは、プロセッサＣＰＵＩがそのキャシュに
読み取り状態でデータブロックを有すると共に、そのデ
ータブロックに書き込みを行なおうとする状態によって
最も良く説明される。これは、ＳＣＵがこのように実行
するための許可を得なければならず、従って、書き込み
リフィル要求をＳＣＵに発生しなければならない。ＳＣ
Ｕは、そのタグルックアップを実行するときに、ＣＰＵ
ｌが既に読み取り許可を得ていることを通知し、従って
、書き込みリフイル要求が書き込み許可を得る目的であ
ると解釈する。それに応答して、ＳＣＵは、即時のキャ
ッシュ一貫性競合があるかどうかを判断するためのチェ
ックを行なう。このような競合がない場合には、メモリ
サイクルが実行されず、ＳＣＵは、書き込みＯＫコマン
ドをＣＰＵに送って、ブロックに書き込む許可を得たこ
とを指示する。一貫性の競合がある場合には、その競合
が最初に分析され、次いで、書き込みＯＫコマンドがＣ
ＰＵＩに中継される。

無効化読み取りブロックコマンド このコマンドは、ＣＰＵＩが読み取り状態のデータブロ
ックを有しそしてＳＣＵがｃｐｕｏからの書き込みリフ
ィル要求を受け取りそしてこのＣＰＵＩがそのデータを
無効状態で有している場合を考慮することによって最も
良く説明される。

タグルックアップを実行することによってこの状態を判
断すると、ＳＣＵは、そのブロックの状態を読み取りか
ら無効に変更することを必要とするコマンドをＣＰＵＩ
に送信する。これは、要求を発しているＣＰＵＯがブロ
ックに書き込みを行なうと、ＣＰＵＩのキャッシュ内に
ある対応するデータがストールされそして無効にされる
からである。その後、ＳＣＵは、要求されたデータをメ
モリから検索し、ＣＰＵＯの書き込みリフィルコマンド
を満足し、又、ＣＰＵＯキャッシュの状態を完全書き込
み状態に変更する。

無効化書き込みブロックコマンド これは、例えば、ＣＰＵＩのようなプロセッサがデータ
ブロックを完全書き込み状態で有しそしてＳＣＵがその
後にメモリの完全ブロック（６４バイト）のＤＭＡ書き
込みをＩ／Ｏユニットから受け取る場合について考慮す
ることにより説明される。このような要求が満足される
と、ＣＰＵキャッシュ内の対応するブロックがストール
状態にされ、従って、ＳＣＵは、その書き込みブロック
を無効化するコマンドをＣ，ＰＵＩに中継する。

ゲットデータオペレーションを必要とするメモリアクセ
ストランザクションの全ての場合に、ＳＣＵは、ゲット
データコマンドをターゲットプロセッサのＭユニットに
最初に中継するが、ＳＣＵは、この点で必要なデータ路
をリザーブするようにして進行しない。そうではなくて
、必要なリソースのリザーブは、要求データの転送準Ｏ
ｉｉｆができたことを指示するデータレディコマンドを
ターゲットＭユニットが返送するまで延期される。この
信号に応答して、ＳＣＵは、送゛信データ信号を中継し
、これはターゲットＭユニットからのデータのライトバ
ックを開始する。同時に、ＳＣＵは、それに関連した書
き込み要求を中継することによってメモリサイクルを開
始する。この構成は、アクセス要求の開始に続いてメモ
リアクセス動作に実際に至るに必要な時間中にＳＣＵ、
メモリ及びデータ路リソースが不必要に結合されるのを
なくす。

又、リフィル要求を受け取るたびに、ＳＣＵはメモリサ
イクルを開始し、タグルックアップ動作を進める。一貫
性の競合が検出されない場合には、確認信号がメモリに
送られ、メモリサイクルを進めることが要求される。然
し乍ら、−ｉ性の競合が検出された場合には、ＳＣＵが
アボート信号を中継し、これはメモリが既に開始された
メモリサイクルをアボートすることを必要とし、その後
、もちろん、要求された固定コマンド（上記した稚々の
コマンドの１つ、例えば、書き込み一読み取り、又は書
き込みバスコマンド）が開始されて競合が修正される。

第５図は、本発明の好ましい実施例によりＳＣＵによっ
てデータの非一貫性状態又はキャッシュの競合を検出及
び修正する際に含まれる機能ブロックを示すブロック図
である。図示されたように、キャッシュ競合検出構成体
２００は、システムユニットの１つによって発生された
複数の要求を受け入れるための仲裁論理回路２０２を備
えており、所定のハイアラーキアルゴリズムに基づいて
選択された要求をこの回路から発生する。要求を発して
いるポートによって発生されたメモリアクセス要求は、
要求と、それに関連したコマンド及びアドレスとを備え
ており、これらは後に対応ＳＣＵボートにラッチされる
。入ってくる要求の仲裁と並列に、これらの要求に関連
したアドレスがアドレスバッファ２０４のグループに受
け入れられ、その出力はマルチプレクサ２０６に送られ
る。

仲裁論理回路２０２からの仲裁された要求は、それ自体
を５ビットインデックスの形態で表わし、これは、マル
チプレクサ２０６の選択入力とじて用いられ、選択され
た要求に対応するアドレスを発生する。入ってくる要求
に関連したコマンドは、コマンドバッファ２０８のグル
ープに受け入れられ、その出力はコマンドマルチプレク
サ２１０へ送られ、該マルチプレクサは、選択された要
求について定められた５ビットインデックスをその選択
入力に受け取る。マルチプレクサ２０６によって選択さ
れたアドレスは、■組のＲＡＭ　２　０　７へ送られ、
これは、選択されたアドレスに対応するメインメモリの
特定のユニット、セグメント及びバンクを識別する信号
を発生する。

ＲＡＭ　２　０　７、仲裁論理回路２０２及びコマンド
マルチプレクサ２１０の出力は、リソース要求論理モジ
ュール２１２へ送られ、該モジュールは、仲裁された要
求を実行するのに必要とされる全てのリソースを定める
出力にリソース要求ベクトルＲＲを発生するために種々
の受け入れられる要求とそれに付隨するコマンド及びア
ドレスのリストを記憶するテーブルの形態で実施される
。

コマンドバッファ２０８及びアドレスバッフア２０４は
、ＳＣＵがこれらの信号に作用する準備ができるまでこ
れらの信号をバッファする手段として働く。リソース要
求ベクトルＲＲは、仲裁された要求を実行するのに必要
な特定のリソースを各々のビットに対応するように定め
る２８ビット信号の形態であるのが好ましい。このベク
トルＲＲは、リソースチェック論理回路２１４に送られ
、該論理回路は、リソース使用可能モジュール２１６か
らの入力も受け入れ、このモジュールは、所与の時間に
使用できるリソースを表わす出力を発生するためにシス
テムリソースを本質的に追跡する。

リソースチェック論理回路は、ＲＲベクトルをＲＡベク
トルと比較して、必要なリソースが使用可能なリソース
のサブセットを形成するかどうかを判断する。全ての必
要なリソースが実際に使用可能であることが分かった場
合には、リソースチェック論理回路２１４が信号を発生
し、これは始動論理回路２１４へ送られ、該回路は、次
いでメモリサイクルをスタートするための信号を発生す
る。然し乍ら、全ての必要なリソースがそのとき使用で
きないことが分かった場合には、信号が仲裁論理モジュ
ール２０２へ返送され、仲裁のために新たな要求の選択
を開始する。この信号（第５図にｌ　Ｂ　＋　で示す）
は、入ってくる要求のプールに非リザーブ要求を戻して
次の仲裁で考慮できるようにすべきであることを仲裁論
理回路に指示する。

第５図において、要求に対する必要なリソースが使用可
能であると分かった場合には、始動論理回路２１８がメ
モリのアドレスされた部分の状態を確認するためにＳＣ
Ｕによって使用されるルックアップサイクルの開始動作
を始める。より詐細には、選択された要求に関連した情
報が始動論理回路２１８によってルックアップ待ち行列
２２０内に入れられ、この待ち行列２２０は、好ましい
実施例によれば、一度に４つの別々の入力を記憶するこ
とができる。ルックアップ待ち行列は、仲裁論理回路２
０２及びリソースチェック論理回路２１４が、各々、仲
裁要求を選択しそしてｌサイクル当たり１つのトランザ
クションという割合でリソースチェック比較を実行でき
ることから必要とされる。然し乍ら、ＳＣＵによるルッ
クアップ動作は、２サイクルの実行を必要とする。従っ
て、要求の選択とルックアップ動作との間の対応を維持
することが必要となる。ルックアップ待ち行列２２０は
、この機能を与える。

選択された要求に対する必要なリソースが使用できずそ
れらの要求を仲裁論理回路２０２へ返送させることがリ
ソースチェック論理回路２１４により決定されると、そ
れらの返送される要求は、対応するリソースが使用でき
ないために既に返送された要求の分離リザーブリストに
配置される。

これと同時に、リザーブリストに入れられた要求は、そ
れらに対してリザーブされた使用不能なリソースを有す
る。ベクトルのリソース発生を実行すると共にリザーブ
リストに拒絶された要求を配置するための例示的な構成
体が、参考としてここに取り上げる前記フリン氏等の「
マルチプロセッサシステムにおいてシステム制御ユニッ
トを用いて通信要求を仲裁する方法及び手段」と題する
米国特許出願に開示されている。

選択された要求に対してルックアップ待ち行列２２０に
ロードされる情報は、選択されたコマンドに対応する要
求インデックス及びコマンドフィールドを備えている。

換言すれば、リソース論理回路２１４へ送られる同じ情
報がルックアップ待ち行列２２０にロードされる。この
ルックアップ待ち行列２２０の入力は、時間順に送り出
され、タグ論理モジュール２２２へ送られる。このモジ
ュールは、ルックアップ動作の結果として発生された情
報を探索し、固定動作が必要とされるかどうかを判断し
そしてそれを表わす信号を発生する．固定動作が必要と
されない場合には、メモリサイクルが続き、その要求が
実行される。タグ論理モジュール２２２は、選択された
要求に対応するタグアドレスを受け取る。バッファ２０
４からのアドレスは、別のマルチブレクサ２２４へ送ら
れ、そしてマルチブレクサ２２４の選択入力の作用によ
り決定された適当なタグアドレスがタグモジュ一ル２２
２へ送られる。

タグ論理モジュール２２２は、選択された要求を伴うメ
モリアドレスのためのタグ状態を構成する信号を発生し
、この情報はマイクロシーケンサ２２６へ送られる。ル
ックアップ待ち行列２２０からアンロードされた情報は
、タグ論理回路２２２によって使用されて、必要なルッ
クアップ動作を実行すると共に、マイクロシーケンサ２
２６は、論理モジュールによって発生されたタグ状態を
、選択された要求に関連した特定のコマンド形式を表わ
す信号と組み合わせて用いて、ＳＣＵが固定動作を実行
する必要があるかどうかの判断をする。マイクロシーケ
ンサは、マイクロコードで実施され、これに送られる信
号に対して組み合わされるビットフィールドを検査し、
予め記憶された値との比較を行なって、固定動作を必要
とするキャッシュー貫性競合が存在するがどうかの判断
が行なわれる。マイクロシーケンサ２２６によって行な
われるこの判断は、上記した種々のデータ非一貫性状態
をベースとするもので、これは、ＳＣＵからＭユニット
へ送られるコマンドに関連したものである。固定動作が
必要であることがマイクロシーケンサ２２６により決定
されると、ＳＣＵが適当なシステムユニットに中継しな
ければならない対応する固定シーケンス又はコマンドが
固定待ち行列２２８にロードされる。固定待ち行列の各
々に対応して、固定シーケンスを実行するのに必要な対
応する１組のリソースが発生される。

これが第６図に示されており、これは、固定待ち行列人
力２２８Ａ，２２８Ｂ及び２２８Ｃがそれに対応するリ
ソース要求論理モジュール２３ＯＡ，２３０Ｂ及び２３
０Ｃに送られることを示しており、その出力は、固定リ
ソース要求ベクトル（ＦＲＶ）を形成するように組み合
わされる。このベクトルＦＲＶは、第５図のリソースチ
ェック論理モジュール２１４にリンクされ、それによっ
て定められた必要なリソースが実際に使用可能であるか
どうかの判断するためにリソースチェック動作を受ける
。

第７図に示すように、リソースチェックモジュール２３
２Ａ，２３２Ｂ及び２３２Ｃは、対応するリソース要求
（ＲＲ）ベクトルＦｌ，Ｆ２及びＦ３を各々受け取る。

これらのベクトルは、必要なリソースが使用可能なリソ
ースのサブセットであることが分かった場合に対応する
「レディ』信号を発生するためにリソース使用可能（Ｒ
Ａ）ベクトルに対してチェックされる．これらのレディ
信号は、その後に、オアゲート２３４に入力として送ら
れ、その出力は、固定シーケンスを開始するための信号
を表わす。換言すれば、上記構或体は、他の所定の状態
の存在が確認されたときに実行すべき所定の固定シーケ
ンスを設けることによって機能する。いつでも、ルック
アップ動作は、必要なリースが使用できるときに実行さ
れるべき固定待ち行列にロードされる．このように、固
定動作を実行する用意ができたときには、固定シーケン
スを実行するためにシステムマイクロコードが借りられ
る（典型的に１つのみの借りたサイクルについて）．そ
の後、対応する固定待ち行列入力がクリアされ、次に要
求される固定動作につぃて使用可能となる。第５図ない
し第７図の好ましい構成は、一度に３つまでの固定シー
ケンスを考えることのできる３人力の深い固定待ち行列
を有するものとして示されている。更に別の固定シーケ
ンスが必要とされる場合には、システムマイクロコード
を用いて固定シーケンスを別々に実行することができる
。

【図面の簡単な説明】

第１図は、複数のシステムＣＰＵが並列に動作されてシ
ステムのメインメモリを共有するマルチプロセッサシス
テムのブロック図、 第２図は、メインメモリ及びＣＰＵキャッシュのインタ
ーリープされたセグメントの構造上の構成及びこれら２
つをリンクする仕方を示すブロック図、 第３図は、ＣＰＵのキャッシュ状態を維持するためにＳ
ＣＵ内に設けられるグローバルなタグ構造体を示す図、 第４図は、ＣＰＵレベル及びＳＣＵレベルの両方におい
てメモリアクセス要求を処理する際に含まれる順次の手
順を示すフローチャート、そして 第５図ないし第７図は、本発明のキャッシュ一貫性機構
に用いる好ましいハードウェア構成を示す回路図である
。 ＩＯ・・・マルチプロセッサシステム ｌ２・・・ＣＰＵ ｌ４・・・システム制御ユニット ｌ６・・・メインメモリ ｌ８・・・入力／出力（Ｉ／Ｏ）制御器２０・・・イン
ターフェイス ２０Ａ・・・関連Ｉ／Ｏユニット ２２・・・サービスプロセッサ／コンソールユニット（
ＳＰＵ） ２４・・・Ｍユニット ２６・・・Ｉユニット ２８・・・Ｅユニット ３０・・・専用インターフェイス手段

Claims (4)

【特許請求の範囲】
1. （１）少なくとも１つの入力／出力（Ｉ／Ｏ）ユニット
   と組み合わせて並列形態で複数の中央処理ユニット（Ｃ
   ＰＵ）を動作させるためのシステム制御ユニット（ＳＣ
   Ｕ）を有する形式のマルチプロセッサシステムにおいて
   、上記ＣＰＵ及びＩ／Ｏユニットの各々は、ＳＣＵにポ
   ート結合されており、ＳＣＵは、上記ＣＰＵ及びＩ／Ｏ
   ユニットが共通のシステムメモリのアドレスされたセグ
   メントを制御可能にアクセスできるようにし、そして上
   記ＣＰＵの各々は、上記システムメモリからのメモリ位
   置の所定のロック状態を記憶するのに用いられるキャッ
   シュメモリを備えており、上記マルチプロセッサコンピ
   ュータシステムにおいて上記複数のＣＰＵキャッシュメ
   モリとシステムメモリとの間のデータの一貫性を確保す
   る方法が、メモリトランザクション要求が処理されるに
   つれて１組の所定のデータ非一貫性状態の１つが生じる
   ときを検出し、そして データの非一貫性を生じることなくメモリトランザクシ
   ョン要求が実行されるようにデータ非一貫性状態を修正
   するという段階を具備することを特徴とする方法。
2. （２）上記所定のデータ非一貫性状態は、 ｉ）上記ＣＰＵ又はＩ／Ｏユニットの１つから、他のＣ
   ＰＵの１つのキャッシュメモリにも存在するシステムメ
   モリ内の位置へのメモリ書き込み動作の要求と、 ｉｉ）上記ＣＰＵ又はＩ／Ｏユニットの１つによる上記
   システムメモリに対する読み取り動作の要求とを含み、
   ここで読み取られるべき位置は他のＣＰＵの１つのキャ
   ッシュメモリに書き込まれてもよいし或いは既に書き込
   まれている請求項１に記載の方法。
3. （３）上記第１のデータ非一貫性状態は、上記ＣＰＵ又
   はＩ／Ｏユニットによって上記書き込み動作が要求され
   ているメモリ位置をキャッシュメモリが含んでいるよう
   な上記プロセッサユニットがそこに記憶されたデータを
   使用しないように阻止することにより修正され、そして 上記第２のデータ非一貫性状態は、上記他のＣＰＵの上
   記キャッシュメモリに書き込まれているデータを上記要
   求を発しているＣＰＵ又はＩ／Ｏユニットへ返送するこ
   とにより修正される請求項２に記載の方法。
4. （４）上記データ非一貫性状態は、上記ＣＰＵの上記キ
   ャッシュメモリの各々に対してキャッシュディレクトリ
   のコピーを維持するための手段をＳＣＵに設けることに
   よって検出され、上記ディレクトリは、キャッシュ位置
   におけるメモリデータの物理的なアドレスと、上記シス
   テムメモリが更新されずに上記キャッシュにデータが書
   き込まれたかどうかを表わす状態ビットとを含んでおり
   、そして 上記ＳＣＵは、処理されているメモリアクセス要求に伴
   うアドレスデータを上記ＳＣＵディレクトリに記憶され
   た情報と比較して、データ非一貫性状態の存在と、この
   非一貫性状態を修正するに必要な動作とを決定する請求
   項３に記載の方法。