JPH11282820A - スイッチをベースとするマルチプロセッサシステムに使用するための順序サポート機構 - Google Patents

スイッチをベースとするマルチプロセッサシステムに使用するための順序サポート機構

Info

Publication number
JPH11282820A
JPH11282820A JP10340924A JP34092498A JPH11282820A JP H11282820 A JPH11282820 A JP H11282820A JP 10340924 A JP10340924 A JP 10340924A JP 34092498 A JP34092498 A JP 34092498A JP H11282820 A JPH11282820 A JP H11282820A
Authority
JP
Japan
Prior art keywords
address
processor
node
data
multiprocessor
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP10340924A
Other languages
English (en)
Other versions
JPH11282820A5 (ja
JP4700773B2 (ja
Inventor
Stephen R Vandoren
アール ヴァンドーレン スティーヴン
Simon C Steely
シー ステイーリイ シモン
Madhumitra Sharma
シャルマ マドハミトラ
David M Fenwick
エム フェンウィック ディヴィッド
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Digital Equipment Corp
Original Assignee
Digital Equipment Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Digital Equipment Corp filed Critical Digital Equipment Corp
Publication of JPH11282820A publication Critical patent/JPH11282820A/ja
Publication of JPH11282820A5 publication Critical patent/JPH11282820A5/ja
Application granted granted Critical
Publication of JP4700773B2 publication Critical patent/JP4700773B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46Multiprogramming arrangements
    • G06F9/52Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Multi Processors (AREA)

Abstract

(57)【要約】 (修正有) 【課題】 共用メモリを含む多数のマルチプロセッサノ
ードがスイッチを経て互いに接続された対称的マルチプ
ロセッサシステム(SMP)。 【解決手段】 大型SMPに使用するアーキテクチャ及
びコヒレンスプロトコルは、多数のマルチプロセッサノ
ードをスイッチに接続して最適な性能で動作できるよう
にするハイアラーキースイッチ構造体を備えている。各
ノードにはバッファシステムが設けられ、ノードのすべ
てのプロセッサが最適な性能で動作でき、またメモリコ
ヒレンス性を維持する多数の要素、即ちビクティムキャ
ッシュ、ディレクトリ及びトランザクション追跡テーブ
ルを含む。ディレクトリの出力に接続された裁定バス
は、SMPを経て送られる全てのメッセージの中央順序
付けポイントを与える。仮想チャンネルの使用は、シス
テム順序を維持する簡単な方法によってデータコヒレン
ス性を維持する。

Description

【発明の詳細な説明】
【0001】
【発明の属する技術分野】本発明は、一般に、コンピュ
ータアーキテクチャーの分野に係り、より詳細には、分
散型共用メモリマルチプロセッサシステムに係る。
【0002】
【従来の技術】この分野で良く知られているように、対
称型のマルチプロセッサコンピュータは、高性能のアプ
リケーション処理を行うことができる。通常の対称型マ
ルチプロセッサコンピュータシステムは、バスによって
互いに接続された多数のプロセッサを備えている。対称
型マルチプロセッサシステムの1つの特徴は、メモリ空
間が全てのプロセッサ間で共用されることである。1つ
以上のオペレーティングシステムがメモリに記憶され、
種々のプロセッサ間でのプロセッサ又はスレッドの分散
を制御する。異なるプロセッサ又はスレッドが多数の異
なるプロセスを同時に実行できるようにすることによ
り、所与のアプリケーションの実行速度を著しく高める
ことができる。理論的に、システムの性能は、マルチプ
ロセッサシステムにおけるプロセッサの台数を増加する
だけで改善することができる。実際には、ある飽和点を
越えてプロセッサを追加し続けると、単に通信ボトルネ
ックが増えるだけとなり、従って、全システム性能を制
限することになる。
【0003】例えば、図1Aには、共通の相互接続バス
を経て互いに接続された8個のプロセッサを含む典型的
な公知のマルチプロセッサシステム2が示されている。
動作中に、各プロセッサ3a−3hは、共用相互接続バ
ス5を経て互いに他のプロセッサ及び共用メモリ4と通
信する。図1Aの対称型マルチプロセッサ構成は、今日ま
でに構築されたマルチプロセッサについて充分である。
しかしながら、より高速のマイクロプロセッサの出現に
伴い、通常の共用相互接続バスは、接続されたマイクロ
プロセッサの潜在的な全性能を充分に働かせることがで
きない。プロセッサとメモリとの間の唯一の通信リンク
は、共用バスであるから、バスはプロセッサからの要求
で急速に飽和状態となり、各プロセッサがシステムバス
へのアクセスを得るよう試みるときに遅延が増大する。
それ故、プロセッサは、高い速度で動作することができ
るが、性能に関する制限ファクタは、システムバスの使
用可能な帯域である。
【0004】通信帯域巾は、SMPシステムの性能にお
いて重要なファクタである。帯域巾は、SMPシステム
におけるノードの対又はサブセットの間で均一ではない
から、業界では、SMPシステムの通信帯域巾を決定す
るために「二等分帯域巾」測定を使用している。二等分
帯域巾は、次のように決定される。システムを等しい計
算能力(等しいプロセッサ数)の2つの部分に区分化す
る全ての考えられる方法が確かめられている。各区分に
対し、2つの区分間に維持し得る帯域巾が決定される。
全ての維持し得る帯域巾の最小値は、相互接続の二等分
帯域巾である。2つの区分間の最小帯域巾は、最悪の通
信パターンが存在するときにマルチプロセッサシステム
により維持できる通信帯域巾を指示する。従って、大き
な二等分帯域巾が望まれる。
【0005】公知技術では、バス飽和の問題を克服する
ために、多数の相互接続アーキテクチャー即ち「トポロ
ジー」が使用されている。これらのトポロジーは、メッ
シュ、トーラス(円環体)、ハイパーキューブ(超立
体)及び拡張ハイパーキューブを含む。
【0006】
【発明が解決しようとする課題】例えば、メッシュ相互
接続は、図1Bにシステム7として示されている。メッ
シュネットワークの主な利点は、簡単で且つ配線が容易
なことである。各ノードは、少数の他の隣接ノードに接
続される。しかしながら、メッシュ相互接続は、3つの
重大な欠点を有する。第1に、メッセージは、それらの
行先に到達するために平均的に多数のノードを横断しな
ければならず、その結果、通信の待ち時間が長くなる。
第2に、二等分帯域巾は、他のトポロジーに対するもの
であるから、メッシュトポロジーの場合に充分に計測し
ない。最後に、各メッセージはメッシュ内の異なる経路
を進行するので、SMPシステム内には自然の順序付け
ポイントが存在せず、それ故、メッシュトポロジーの実
施を必要とするキャッシュコヒレンスプロトコルがしば
しば非常に複雑なものとなる。
【0007】トーラス、ハイパーキューブ及び拡張ハイ
パーキューブトポロジーは、全て、ノードが種々の複雑
な構成、例えば円環体構成又は立体構成で相互接続され
たトポロジーである。トーラス、ハイパーキューブ及び
拡張ハイパーキューブの相互接続は、メッシュ相互接続
よりも複雑であるが、その待ち時間及び帯域巾は、メッ
シュ相互接続よりも優れている。しかしながら、メッシ
ュ相互接続と同様に、トーラス、ハイパーキューブ及び
拡張ハイパーキューブトポロジーは、自然の順序付けポ
イントを与えず、従って、これらのシステムの各々に対
して複雑なキャッシュコヒレンスプロトコルを実施しな
ければならない。共用メモリのマルチプロセッサシステ
ムでは、プロセッサは、通常、将来アクセスされる見込
みが高いと決定されたデータを記憶するために専用キャ
ッシュを使用している。プロセッサは、それらの専用キ
ャッシュからデータを読み取りそしてメモリへ書き戻す
ことなく専用キャッシュにおいてデータを更新するの
で、各プロセッサの専用キャッシュが一貫して即ちコヒ
レントに保持されるよう確保するための機構が必要とな
る。SMPシステムのデータのコヒレンス性を確保する
のに使用される機構は、キャッシュコヒレンスプロトコ
ルと称される。
【0008】物理的な相互接続部のトポロジー、帯域巾
及び待ち時間に加えて、キャッシュコヒレンスプロトコ
ルの効率も、システム性能の重要なファクタである。キ
ャッシュコヒレンスプロトコルは、待ち時間、ボトルネ
ック、非効率性又は複雑さを多数の仕方で導入する。ロ
ード及び記憶動作の待ち時間は、設計のプロトコルによ
って直接影響されることがしばしばある。例えば、ある
プロトコルでは、全ての無効化メッセージがそれらのタ
ーゲットプロセッサへ送られそして確認メッセージがそ
の元のプロセッサへ完全に返送されるまで記憶動作が完
了したとみなされない。従って、記憶の待ち時間は、無
効化がその行先へ送られるのを元のプロセッサが待機し
なくてよいプロトコルよりも相当に長いものとなる。更
に、確認は、システム帯域巾の相当の部分を消費する。
【0009】ボトルネックは、コントローラの高い占有
度によりしばしば生じる。「占有度」とは、コントロー
ラが要求を受け取った後に使用できなくなる時間の長さ
を示す用語である。あるプロトコルでは、直接的なコン
トローラは、メモリ位置に対応する要求を受け取ると、
その前のコマンドに対応するある確認がディレクトリに
到着するまで同じメモリ位置への他の要求に対して使用
できなくなる。コントローラは、平均より高いレートで
競合する要求を受け取る場合に、ボトルネックとなる。
又、キャッシュコヒレンスプロトコルの設計は、ハード
ウェアの複雑さにも影響する。例えば、あるプロトコル
は、停滞及び公正さの問題を招き、これらは、付加的な
機構で対処される。その結果、ハードウェアの複雑さが
増大する。
【0010】そこで、オペレーションの待ち時間を最小
にし、広い通信帯域巾を与え、コントローラの占有度を
低くし、そして多数のプロセッサへと拡張することので
きる対称的なマルチプロセッサシステムを提供すること
が要望される。
【0011】
【課題を解決するための手段】本発明は、少なくとも1
つのプロセッサ及び共用メモリの一部分を含む多数のマ
ルチプロセッサノードがスイッチを経て互いに接続され
た対称的なマルチプロセッサシステムに効果的に使用さ
れる。マルチプロセッサノードの各々にはトランザクシ
ョン追跡(トラッキング)テーブル(TTT)が維持さ
れる。TTTは、ノードをスイッチに接続するノードの
グローバルポートに存在してもよいし、或いはマルチプ
ロセッサノードの少なくとも1つのプロセッサの各々に
存在してもよい。TTTは、マルチプロセッサノードか
ら発生され及びそれにより受け取られる要求の順序を決
定しそしてそれを強制するのに使用される。本発明の1
つの特徴によれば、TTTは、マルチプロセッサノード
へ返送される要求の順序を次のように決定するのに使用
される。各要求は、多数のトランザクションに細分化さ
れ、各トランザクションは、異なる仮想チャンネルを経
て搬送される。少なくとも1つのチャンネルが順序付け
されるが、他のチャンネルの返送データは、ばらばらの
順序で受け取ることができる。コヒレンス性を維持する
ために、共通のアドレスへ発生されるトランザクション
が順序正しく取り扱われるのが望ましい。本発明の1つ
の特徴によれば、マーカーパケットが、順序付けされた
チャンネルを経てTTTへ発生され、アドレスに関連し
たデータが依然処理されていることを指示する。このよ
うな構成では、TTTは、マーカーパケットに続いて受
け取られた上記順序付けされたチャンネルの他の要求を
無視するか、又はデータが受け取られるまで遅延するよ
うに確保する。
【0012】従って、本発明の1つの特徴によれば、各
々少なくとも1つのプロセッサ及び共用メモリの一部分
を含む複数の接続されたマルチプロセッサノードを有す
るコンピュータシステムは、上記複数のマルチプロセッ
サノードの各々における複数のプロセッサに関連した追
跡機構であって、上記複数のマルチプロセッサノードの
1つにおける少なくとも1つのプロセッサの1つにより
発生された共用メモリのリモート部分のアドレスへの要
求の位置を、上記複数の接続されたマルチプロセッサノ
ードにおける少なくとも1つのプロセッサにより上記ア
ドレスへ発生された複数の他の要求に対して識別するた
めの追跡機構を備えている。本発明の更に別の特徴によ
れば、マルチプロセッサコンピュータシステムの共通の
アドレスへ発生される複数の要求間の順序を維持するた
めの方法が提供される。マルチプロセッサコンピュータ
システムは、スイッチを経て接続された複数のマルチプ
ロセッサノードを備え、各マルチプロセッサノードは、
少なくとも1つのプロセッサ及び共用メモリの一部分を
含む。上記方法は、マルチプロセッサノードの各々から
スイッチへ送られる要求のアドレスリストを維持して、
リモートマルチプロセッサノードの共用メモリの一部分
における各アドレスに対して要求の相対的な順序を識別
し、アドレスに関連した要求が満足されるまでアドレス
をリストに維持するという段階を含む。
【0013】
【発明の実施の形態】本発明の上記及び他の特徴は、添
付図面を参照した以下の詳細な説明から明らかとなろ
う。本発明の1つの実施形態によれば、ハイアラーキー
式の対称的マルチプロセッサ(SMP)システムは、高
性能スイッチを経て互いに接続された多数のSMPノー
ドを備えている。従って、SMPノードの各々は、SM
Pシステムにおいてビルディングブロックとして働く。
以下、1つのSMPノードビルディングブロックの要素
及び動作を最初に説明し、その後に、SMPシステムの
動作を説明し、それに続いて、大規模のSMPシステム
においてメモリのコヒレンス性を維持するために使用さ
れるキャッシュコヒレンスプロトコルを説明する。
【0014】SMPノードビルディングブロック 図2を参照すれば、マルチプロセッサノード10は、4
つのプロセッサモジュール12a、12b、12c及び
12dを備えている。各プロセッサモジュールは、中央
処理ユニット(CPU)を備えている。好ましい実施形
態では、デジタル・イクイップメント社で製造されたA
lpha(登録商標)21264プロセッサチップが使
用されるが、以下に述べるコヒレンスプロトコルをサポ
ートすることのできるものであれば、他の形式のプロセ
ッサチップも使用できる。マルチプロセッサノード10
は、多数のメモリモジュール13a−13dを含むメモ
リ13を備えている。このメモリは、32ギガバイトの
記憶容量を備え、4つのメモリモジュールの各々が8ギ
ガバイトを記憶する。各メモリモジュールは、多数のメ
モリブロックに分割され、各ブロックは、例えば、64
バイトのデータを含む。データは、一般に、メモリから
ブロックで検索される。
【0015】更に、マルチプロセッサノード10は、接
続されたI/Oバス14aを経て外部装置(図示せず)
とマルチプロセッサノード10との間で行われるデータ
転送を制御するためのI/Oプロセッサ(IOP)モジ
ュール14を備えている。本発明の1つの実施形態で
は、I/Oバスは、周辺コンピュータ相互接続(PC
I)プロトコルに基づいて動作する。IOP14は、I
OPキャッシュ14c及びIOPタグ記憶装置14bを
含む。IOPキャッシュ14cは、PCIバス14aを
経て外部装置へ転送されるメモリ13からのデータのた
めの一時的な記憶装置である。IOPタグ記憶装置14
bは、外部装置とプロセッサとメモリとの間に移動され
るデータに対するコヒレンス情報を記憶するための64
エントリのタグ記憶装置である。
【0016】マルチプロセッサノードのメモリ13に記
憶されたデータのコヒレンス性は、デュープリケートタ
グ記憶装置(DRAG)20によって維持される。DT
AG20は、全てのプロセッサ12a−12dにより共
用され、そして4つのバンクに分割される。各バンク
は、関連するプロセッサにより使用されるデータに対応
する状態情報を専用に記憶する。DTAG、メモリ及び
IOPは、ARBバス17と称する論理バスに接続され
る。プロセッサにより発生されるメモリブロック要求
は、ローカルスイッチ15を経てARBバス17にルー
ト指定される。DTAG20及びIOP14は、プロセ
ッサ及びIOPのキャッシュにおけるブロックの状態を
ルックアップし、そしてメモリブロックに対しそれらの
状態を原子的に更新する。ARBバス17は、全てのメ
モリ参照に対してシリアル化ポイントとして働く。メモ
リ要求がARBバスに現れる順序は、プロセッサが要求
の結果を認知する順序である。
【0017】プロセッサモジュール12a−12d、メ
モリモジュール13a−13d及びIOPモジュール1
4は、ローカルの9ポートスイッチ15を経て互いに接
続される。インターフェイスモジュール12a−12
d、13a−13d及び14の各々は、同数の両方向性
クロック送信データリンク16a−16iによりローカ
ルスイッチに接続される。1つの実施形態では、データ
リンクの各々は、150MHzのレートで動作するシス
テムクロックの各縁で64ビットのデータ及び8ビット
のエラー修正コード(ECC)を送信する。従って、デ
ータリンク16a−16iの各々のデータ帯域巾は、
2.4ギガバイト/sである。ローカルスイッチ15
は、クオドスイッチアドレス制御チップ(QSAチッ
プ)18及びクオドスイッチデータスライスチップ(Q
SDチップ)19を備えている。QSAチップ18は、
プロセッサモジュールIOPとメモリとの間のアドレス
経路を制御するためのアービター(QS ARB)11
を備えている。更に、QSAチップ18は、以下に述べ
るようにローカルスイッチ15を通るデータの流れを制
御するためにQSDチップ19を制御する。 QSDチ
ップ19は、プロセッサモジュールと、メモリモジュー
ルと、IOPとの間の全てのデータ経路に対するスイッ
チ相互接続を与える。図2には示されていないが、以下
に述べるように、マルチプロセッサノード10がグロー
バルポートを経て他のマルチプロセッサノードに接続さ
れた場合には、QSD及びOSAがグローバルポートに
対するスイッチ相互接続部を付加的に形成する。各プロ
セッサは、メモリデバイス13a−14d、他のプロセ
ッサ12a−12d、IOP14のような使用可能なリ
ソースの1つからデータを要求することもできるし、或
いは他のマルチプロセッサノードのリソースからグロー
バルポートを経てデータを要求することもできる。従っ
て、ローカルスイッチ15は、2.4ギガバイトの広い
バス帯域巾を維持しながら、種々のリソースから同時入
力を受け入れることができねばならない。
【0018】ローカルスイッチは、多数の同時トランザ
クションを取り扱うことができる。各トランザクション
は、通常、多数のリソース(メモリバンクや、データ経
路や、待ち行列のような)を使用するので、ローカルス
イッチの制御機能は非常に複雑になる。例えば、あるト
ランザクションは、そのトランザクションの段階0でメ
モリバンクを使用でき、段階1でメモリバンクからプロ
セッサポートへのデータ経路を使用でき、そして段階2
でプロセッサポートからプロセッサへのデータ経路を使
用できることを必要とする。ローカルスイッチアービタ
ー(QSA18のQSA ARB11)は、あるトラン
ザクションが開始されると、各段階でトランザクション
により必要とされるリソースが必要に応じて使用できる
ように要求を裁定する。
【0019】より重要なことに、アービターは、特定の
要求が、他の要求の進行中に長時間にわたり(潜在的に
不定に)裁定に負けることのないよう確保することによ
り、全ての要求及びプロセッサがリソースに対して公平
なアクセスを得るように保証する。例えば、3つのリソ
ースA、B及びCを要求するトランザクションTについ
て考える。このトランザクションTは、トランザクショ
ンの適当な段階に3つのリソース全部が使用できるよう
保証されるまで裁定に勝てない。リソースが使用可能で
あることのみに基づいてアービターがその判断を行う場
合には、トランザクションTは、A、B又はCの1つを
使用する(他のリソースD、E等と共に)他のトランザ
クションが裁定に勝ち続ける間は、長時間にわたって成
功しないことが考えられる。
【0020】各々が多数のリソースを使用して完了する
ような非常に多数の同時要求を伴うスイッチにおいて公
平な裁定を保証するのは、計算上複雑である上に、高速
データ経路において遅延を増加し勝ちである。ここに示
す装置においては、QSAARB11が、特定のトラン
ザクションをスケジュールする前に、1つのリソース
(メモリバンク)のみについて裁定を行う。プロセッサ
に通じる待ち行列である第2のリソースは、QSA A
RB11により第1のリソースについて裁定を行うとき
に、それが使用可能であるかどうかについてチェックす
る必要がない。というのは、QSDのアーキテクチャー
がそのデータ経路を保証しそして待ち行列に通じる待ち
行列スロットが常に使用できるからである。リソースに
対する公平な裁定は、QSAARB11に著しい複雑さ
を伴うことなく与えられる。
【0021】本発明の1つの実施形態によれば、QSD
は、対応する行先に通じるバッファに対してアップフロ
ント裁定を必要とせずに全てのリソース(プロセッサ、
メモリ、IOP及びグローバルポート)からの入力を同
時に受け取ることができる。次いで、全てのデータリソ
ースは、データ経路又はスイッチにおける待ち行列スロ
ットへのアクセスを裁定する必要なく、スイッチへデー
タを独立して送信することができる。というのは、QS
Dは、全てのリソースからのデータを実質的に同時に受
信することのできる多数の同時挿入バッファを備えてい
るからである。同時挿入バッファの2つの実施形態を以
下に説明する。
【0022】同時挿入バッファスイッチ 上記のように、マルチプロセッサノードにおけるプロセ
ッサ12a−12d、IOP14及びメモリデバイス1
3a−13dの各々は、マルチプロセッサノードのプロ
セッサ及びIOPからの要求を取り扱うためのリソース
として働く。データは、各リソース要素と、要求を発す
る要素との間でパケットの形態で転送される。各パケッ
トは、512ビットのデータと、64ビットのECCと
を含む。上記したように、各データリンクは、64ビッ
トのデータ及び8ビットのECCを150MHzクロッ
クの各縁において搬送する。従って、QSDの外部に
は、パケット当たり8個のデータ転送サイクルがある。
しかしながら、QSDの内部では、クロックの1つの縁
においてのみデータが収集される。従って、QSDの内
部のロジックの各クロックサイクルに対し、潜在的に1
28ビットのデータがデータリンクから受け取られる。
各パケットは、512ビットのデータ及び64ビットの
ECCを含むので、QSDの内部では、各パケットごと
に4つのデータ転送サイクルがあり、各QSDクロック
サイクルに、128ビットのデータ及び16ビットのE
CCがプロセッサ、IOP又はメモリデバイスからQS
Dへ転送される。
【0023】図3を参照すれば、QSD19は、5つの
同時挿入バッファ(SIB)25a−25eを含むよう
に詳細に示されている。各SIBは、要求側要素、即ち
プロセッサ12a−12d又はIOPの1つに専用であ
る。各SIBは、それに関連した要求側要素と、ノード
内の他のリソース要素、即ちプロセッサ12a−12
d、メモリ13a−13d、IOP14及び好ましくは
グローバルポートとの間でパケットを転送するためのデ
ータ経路を制御する。グローバルポートは、他のマルチ
プロセッサノードへの相互接続部として働き、以下に詳
細に説明する。SIBは、スイッチへのアクセスに対し
要求側要素間の裁定を必要とせずに、スイッチに接続さ
れたいずれのリソースからでも要求側要素によりパケッ
トを同時に受信できるようにする。
【0024】既に述べたように、QSA ARB11
は、スイッチ19への制御を与えるように接続される。
QSA ARB11には、メインアービター27が含ま
れる。このメインアービター27は、リソース(IO
P、プロセッサ12a−12d及びメモリ13a−13
d)とスイッチ19との間のデータの移動を管理する。
プロセッサ12a−12d及びIOP14の各々は、ラ
イン28a−28e上のリソースの1つへアクセスする
ための要求を発生し、これらは、メインアービター27
に送られる。次いで、メインアービターは、各リソース
が要求を受信できるときにこれらの要求をその関連リソ
ースへ送る。リソースが要求を受け取るときに、スイッ
チ19の裁定は必要とされない。というのは、SIBの
各々は、全ての入力からの入力を実質的に同時に即ち同
じデータサイクル内に受け取ることができるからであ
る。 又、QSA AEB11には、多数の個々のアー
ビター23a−23dも含まれる。これらアービター2
3a−23dの各々は、プロセッサ12a−12dの関
連する1つと、それに対応するSIB25b−25eと
の間のデータ路を管理するのに使用される。IOP14
とSIB25aとの間のデータ路を管理するために、I
OP14には同様のアービター(図示せず)が含まれ
る。各プロセッサは、その関連SIBからデータを受け
取ることができるので、その関連アービターは、接続さ
れたデータ路にデータを送信する。
【0025】従って、スイッチ19内の同時挿入バッフ
ァの使用により、要求側要素とリソースとの間の裁定経
路は、2つの別々の区分に分割される。即ち、接続され
たりソースからデータを受け取るために要求を発してい
るプロセッサが使用できるかどうかに拘わりなくプロセ
ッサからの要求に応答してメインアービター27がリソ
ースを裁定するところの第1裁定区分と、プロセッサに
関連したアービターがスイッチからのデータを送信する
ためにプロセッサへのアクセスを裁定するところの第2
裁定区分である。このような構成では、裁定が分離され
るために、接続されたりソース各々への公平なアクセス
が与えられるように保証することができる。図4Aを参
照すれば、SIB25aの1つの実施形態が詳細に示さ
れており、これは、ライン36aを経て8個の接続され
たマルチプレクサ34a−34hにMUX選択信号<3
1:0>を与えるように接続された入力アービター36
を備え、MUX選択信号の4つが8個のマルチプレクサ
の各々に送られて、各マルチプレクサの9個の入力の1
つが選択される。SIB25a−25dは全て同様の構
造にされ、従って、その1つについてのみ詳細に説明す
る。上記したように、潜在的に10個のリソースがSI
Bに接続される。10個のリソースの1つは、SIBか
ら出力を受信する要求側デバイスであり、一方、他の9
個のリソースは、SIBに入力を与える。それ故、マル
チプレクサ34a−34hの各々は、SIBに接続され
た9個のリソースから入力を受け取る。接続されたプロ
セッサの3つからの入力は、ラインPx、Py及びPz
を経て受け取られる。第4のプロセッサ(SIBがIO
Pデバイスに関連するとき)又はIOPデバイス(SI
Bが1つのプロセッサに関連するとき)からの別の入力
はラインPW/IOPを経て受け取られる。メモリバン
ク13a−13dからの入力は、各々、ラインmem
0、mem1、mem2及びmem3を経て受け取ら
れ、そしてグローバルポートからの入力は、グローバル
ポートラインを経て受け取られる。
【0026】マルチプレクサ34a−34hの各々から
の各出力は、バッファ32の8個のバンクの1つに接続
される。各バンクは8個のエントリを有し、各エントリ
は、128ビットのデータ及び16ビットのECCを記
憶する。従って、SIBにより受信されるデータの各パ
ケットは、バッファ32の同じ行において4つの異なる
バンクに書き込まれる。以下に述べるように、入力アー
ビター36は、データを記憶するのに使用できるバッフ
ァのバンクを指示するための状態ビットを維持する。従
って、1つ以上のリソースから128ビットのパケット
データが受け取られる各サイクルごとに、入力アービタ
ー36は、バンクの使用状態に基づいて関連バンク32
a−32hへパケットデータのサイクルを送信するため
に、各マルチプレクサ34a−34hにおける考えられ
る9個のリソース入力の1つを選択する。又、入力アー
ビターは、ライン36bを経てマルチプレクサ30へバ
イパスデータも与える。入力アービターの状態ビット
が、全てのバンク32a−32hが空であることを指示
するときには、9個のリソース入力の1つが入力アービ
ター36を経て関連する要求側要素へ直接バイパスされ
る。
【0027】バンク32a−32hの各々は、マルチプ
レクサ30に接続される。マルチプレクサ30は、出力
アービター38により制御される。SIB25aに関連
する要求側要素がSIBからデータを受け取る準備がで
き、そしてパケットの一部分がSIBのエントリに書き
込まれると、出力アービターは、バンク32a−32h
から要求側要素に8個のエントリーの1つを供給する。
或いは又、出力アービターは、いずれのバンクも転送保
留データをもたずそして入力アービターからライン36
bを経てデータが得られる場合には、ライン36bを経
て要求側要素にバイパスデータを供給する。動作中に、
パケットデータの第1の128ビットがSIBに受け取
られたときに、8個のバンクの1つが、パケットデータ
の第1の128ビットを記憶するために選択される。本
発明の1つの実施形態によれば、パケットデータの12
8ビットが受け取られる次の3サイクルの各々の間に、
手前の書き込みを実行するのに使用したバンクに隣接す
るバンクが、パケットデータの次の128ビットを書き
込むのに選択される。例えば、バンク32aが、ソース
mem0からパケットデータの第1サイクルを書き込む
のに使用できるバンクとして選択された場合には、パケ
ットデータの第2サイクルはバンク32bに書き込ま
れ、第3サイクルはバンク32cに書き込まれ、そして
第4サイクルはバンク32dに書き込まれる。従って、
パケットデータのその後のサイクルを書き込むためにど
のバンクを使用すべきかの選択は、入力アービターによ
り選択されたバンクでスタートしそして各次々のパケッ
ト書き込みに対して隣接バンクに続くようにして回転ベ
ースで実行される。その結果、受け取られたパケットが
バッファ32の共通の行における4つのバンクにわたっ
て分散される。
【0028】8個のバンクが設けられ、そして本発明の
1つの実施形態では、いずれの要求側要素においても保
留となり得るリソース読み取りの最大数は8であるか
ら、各書き込みサイクルの間に各リソースに対して少な
くとも1つのバンクを使用できることが確保される。そ
れ故、所与の瞬間に、全部で8個の保留の読み取り応答
がスイッチによって受け取られた場合に、バンク32a
−32hの各々を使用して、第1のパケットデータ書き
込みサイクルを受け入れることができ、バンクの選択
は、次の3つの書き込みサイクルについて回転される。
本発明の1つの実施形態では、SIBの各バッファは、
先入れ先出し(FIFO)プロトコルのもとで動作す
る。パケットの2つの部分が同時に受け取られるので、
それらに対しスイッチへ「読み込まれる」順序が選択さ
れる。リソースに対して裁定を行う要求側要素のロジッ
クは、SIBと通信せず、そしてリソースに対して裁定
するための他の要求側要素とも通信しないので、標準的
なルールに従ってデータの完全性を確保する。例えば、
リソースに固定の優先順位番号が指定される場合には、
「低い番号の入力リソースからのデータが、常に、高い
番号の入力リソースからのデータの前にスイッチに書き
込まれる」というようなルールに従う。
【0029】上記のように、図4Aに示すSIBの実施
形態では、8個のバンクの使用について説明した。とい
うのは、要求側要素が所与の瞬間にもつことのできる保
留メモリ要求の数が8に対応するからである。しかしな
がら、設計上の制約により、それより少数のバンクを設
けることが必要な場合には、インターリーブ又は同様の
技術を使用して多数のデータチャンクを共通のバンクの
異なる位置に同時に書き込みできるように当業者によっ
て容易に設計を変更することができよう。それ故、本発
明は、図4Aに示す特定の実施形態に限定されるもので
はない。上記のように、動作中に、入力アービターは、
リソースからデータを書き込むための適当なバンクを選
択するためにバンクにおける入力の利用性に関する状態
情報を維持する。SIBへの入力を制御するための入力
アービター36の実施形態が図4Bに示されている。上
記では9個の入力リソースについて述べたが、図4Bに
は、明瞭化のために、2つのリソース入力のみの書き込
みを制御するロジックが示されている。入力パケットデ
ータがライン35を経て受け取られるときに、「入力
1」のような指示信号がラッチチェーン40に送られ、
このラッチチェーンは、4個のラッチ、フリップ−フロ
ップ又は同様の状態装置を含む。ラッチチェーン40
は、カウンタ機構として使用される。この例の目的とし
て、4つの次々のデータ転送サイクルにパケットデータ
が受け取られると仮定する。4つのデータ転送サイクル
の間に、入力信号はラッチチェーンを経て伝播する。ラ
ッチチェーンには、オアゲート46が接続される。入力
値がラッチチェーン40を経て伝播するときに、オアゲ
ート46の出力がアサートされる。
【0030】オアゲート46の出力は、シフトレジスタ
48へのシフト信号を与える。シフトレジスタは、SI
Bの各バンクについて1つづつ、8個のビット位置を含
む。シフトレジスタ48は、入力信号サンプルを最初に
受信する際に、バンク選択ロジック44からのビットベ
クトルがロードされる。バンク選択ロジック44から受
け取られたビットベクトルは、1ビットがセットされる
だけであり、ベクトル内のビットの相対的な位置が、パ
ケットデータの書き込みを開始すべきバンクを指示す
る。従って、バンク選択ロジック44は、パケットデー
タの第1サイクルの書き込み行先を制御する。バンク選
択ロジック44は、利用性ベクトル42を入力として受
け取り、利用性ベクトルにおけるビットの相対的な位置
が、書き込みデータを受け取ることのできない関連バッ
ファを指示する。
【0031】バンク選択ロジックがシフトレジスタ48
へビットを与えるときに、シフトレジスタ48の値がデ
マルチプレクサ49に送られる。又、デマルチプレクサ
49は、入力1ソースが接続されるところのマルチプレ
クサ34a−34hの入力の数値表示も入力として受け
取る。例えば、デマルチプレクサ49は、「1」のマル
チプレクサ選択値を用いてマルチプレクサ34aを経て
入力1リソースデータが送られることを指示する「1」
入力値を受け取る。選択されたバンクを指示するシフト
レジスタ内のビットの位置に基づいて、値「1」がMU
X選択<31:0>信号36aの適当な位置へ伝播され
る。各入力ソースに対する各デマルチプレクサは、全て
のMUX選択信号を駆動し、それらの出力は、これらの
信号がマルチプレクサ34a−34hを駆動する前にオ
アされる。
【0032】バンクエントリの書き込みの後に、シフト
レジスタの内容がオアゲート50によりオアされ、利用
性バンクベクトル42として記憶される。これは、次の
サイクルの間に、どのバンクが到来する書き込みに対し
て使用できるかをバンク選択ロジック44により決定す
るために使用される。ライン46aのシフト信号がアサ
ートされる各サイクルに、シフトレジスタ48のビット
が右へシフトされる。ビットが右へシフトするときに
は、MUX選択信号<31:0>の選択値も右へシフト
され、次の書き込み動作中に入力ソースを次の隣接バン
クへ供給するようにさせる。従って、ローカルQSDス
イッチ内のSIBを使用することにより、多数の同時に
受け取られた入力がそれらの行先である要求側要素へ到
達するように確保できる簡単且つ効率的なスイッチング
機構が設けられる。このような構成では、リソースへの
アクセスに対してソースがいったん裁定されると、ソー
スにより実行されねばならない全ての裁定が完了する。
ソースは、リソースが常にスイッチバッファ32へのア
クセスを得ることができるという事実に依存する。ソー
スアービターが互いに独立して動作してリソースを管理
できることにより、最小限の複雑さで公平な裁定を確保
する機構が設けられる。更に、SIBは、要求側要素の
最大数の保留中読み取りに対してデータを記憶できるの
で、たとえ全てのリソースからデータが同時に受け取ら
れても、バッファ32に対するリソースを裁定する必要
はなく、リソースロジックの全体的な複雑さが低減され
る。
【0033】図5には、図3に示すようにプロセッサ又
はIOPデバイス(キャッシュを含む任意の要求側デバ
イス)へ接続することのできる同時挿入バッファ(SI
B)61の第2の実施形態が示されている。SIB61
は、9個のマルチプレクサ60a−60iを含み、その
うちの8個は、8個のバッファ62a−62hの各々に
接続される。第9マルチプレクサ60iは、以下に述べ
るようにバイパス経路を与えるのに使用される。マルチ
プレクサ60a−60iの各々は、接続されたメモリデ
バイスmem0−mem3からの4つの入力、グローバ
ルポートからの1つの入力、接続されたプロセッサから
ラインPx、Py及びPzを経て送られる3つの入力、
そしてIOP(SIBに関連したデバイスがプロセッサ
の場合)又は別のプロセッサ(SIBに関連したデバイ
スがIOPの場合)からラインPW/IOPを経て送ら
れる1つの入力を含む9つの入力を受け取る。
【0034】バッファ62a−62hの各々は、4つの
128ビットエントリを含む。従って、各入力バッファ
は、SIBにおいて次々のサイクル中に4つの128ビ
ット部分で受け取られた1つの512ビット情報パケッ
トを記憶する。各バッファには、4対1のマルチプレク
サ64a−64hが各々接続される。これらのマルチプ
レクサ64a−64hは、関連バッファの4つの入力の
うちの1つを選択して、マルチプレクサ66を経てSI
Bの出力へ供給するのに使用される。図4Aについて上
述したように、本発明の1つの実施形態では、各要求側
要素がいかなる所与の瞬間にも異なるリソースに対して
せいぜい8個の保留中読み取り参照を有するだけである
から、8個のバッファが含まれる。従って、図5には8
個のバッファが示されているが、本発明はこれに限定さ
れるものではない。むしろ、選択されるバッファの数
は、関連するプロセッサ又はIOPデバイスのバッファ
特性に依存する。
【0035】動作中に、接続されたりソースの各々から
入力が受け取られるときに、入力アービター67は、各
マルチプレクサにおける入力ラインの1つを選択し、デ
ータのパケットを空きバッファへ供給する。所与のリソ
ースからのパケット書き込みの時間中に同じバッファが
選択され、パケットの全ての部分が単一のバッファに維
持される。パケットの少なくとも1つの部分がバッファ
に書き込まれると、それがマルチプレクサ66に送ら
れ、関連する要求側要素の準備ができたときにその要求
側要素へ供給される。或いは又、いずれのバッファにも
パケットデータが存在しない場合には、マルチプレクサ
60iを経、マルチプレクサ66を経てパケットデータ
を出力へ直接的に供給することによりバイパス経路を選
択することができる。
【0036】8個のバッファが設けられるので、SIB
デバイス61は、接続されたりソースの各々から実質的
に同時に(即ち、同じデータサイクルに)データを受け
取ることができる。QSDにSIBを使用することによ
り、前記の実施形態の場合のように、SIBへのアクセ
スに対し要求側要素の間に裁定は必要とされない。その
結果、リソースがローカルスイッチを使用する準備がで
きたときにローカルスイッチの利用性が保証される。更
に、本来的に公平な裁定機構が設けられる。というの
は、スイッチに対する裁定の結果としてリソースへの要
求が他のリソースへの他の要求により阻止されないから
である。従って、裁定の複雑さを最小限に抑えながら最
大のバス帯域巾を維持することのできる公平で且つ比較
的簡単な構造体が与えられる。
【0037】従って、同時挿入バッファを使用して広い
バス帯域巾をサポートするローカルスイッチを実施する
ことにより処理リソースを最適に使用するマルチプロセ
ッサノード10が提供される。更に、ARBバス13に
おいて参照の順序がシリアル化されるので、マルチプロ
セッサ10のメモリのコヒレンス性を容易に維持する中
央順序付けポイントが設けられる。ローカルスイッチに
接続されるプロセッサモジュールの数を増加することに
より処理能力を高める可能性が存在するので、図2の4
プロセッサ/ローカルスイッチ構成体は、待ち時間の短
いそしてコストの安い高性能のシステムを提供する。
【0038】大型の対称的マルチプロセッサシステム モノリシックマルチプロセッサノードに含むことのでき
るプロセッサの数は、2つのファクタにより制限され
る。第1に、ローカルスイッチを経て互いに接続できる
プロセッサの数は、ローカルスイッチを構成するチップ
において使用できるピンの数により制限される。第2
に、単一のモノリシックスイッチによりサポートされる
データ帯域巾が制限される。従って、接続されるプロセ
ッサの数をある点を越えて増加すると、何ら性能利得が
得られないことになる。本発明の1つの実施形態によれ
ば、ハイアラーキースイッチを経て複数のマルチプロセ
ッサノードを相互接続することにより大型の対称的なマ
ルチプロセッサシステムを形成することができる。例え
ば、ハイアラーキースイッチを経て8個のマルチプロセ
ッサノードを接続して、32個のプロセッサモジュー
ル、8個のIOPデバイス及び256ギガバイトのメモ
リを含む対称的なマルチプロセッサ(SMP)システム
が形成される。説明上、ここでは、少なくとも2つのマ
ルチプロセッサノードを含むSMPを大型SMPと称す
る。以下に詳細に述べるように、SMPノードにローカ
ルスイッチを用いて少数のプロセッサを接続し、そして
ハイアラーキースイッチを用いて多数のノードを大型の
SMPへと接続することにより、拡張可能な高性能シス
テムを実現することができる。
【0039】マルチプロセッサノードをハイアラーキー
スイッチ式ノードへと接続するために、マルチプロセッ
サは、グローバルなポートインターフェイスを含むよう
に拡張される。例えば、図6には、変更されたマルチプ
ロセッサノード100が示されている。図2のマルチプ
ロセッサノードと同様に、ローカルスイッチ110は、
4つのプロセッサモジュール、4つのメモリモジュール
及びIOPモジュールを接続する。図2及び6の同様の
要素は、同じ参照番号を有する。マルチプロセッサノー
ド100のローカルスイッチ110は、図2のポート1
6a−16iと同様に構成された9個のポート116a
−116iを含む10ポートスイッチである。付加的な
ポート116jは、グローバルリンク132を経てグロ
ーバルポート120へ至る全二重のクロック供給データ
リンクを形成する。
【0040】グローバルポートは、マルチプロセッサノ
ードをハイアラーキースイッチに接続し、大型のSMP
を実現する。例えば、図7Aを参照すれば、本発明の1
つの実施形態において、8x8のハイアラーキースイッ
チ155を経て互いに接続された8個のノード100a
−100hを含む大型のSMPシステム150が示され
ている。これらノード100a−100hの各々は、図
6に示すノード100と実質的に同一である。ノード1
00a−100hの各々は、全二重クロック供給データ
リンク170a−170hの各々によりハイアラーキー
スイッチ155に接続される。1つの実施形態におい
て、データリンク170a−170hは、150MHz
のクロック速度で動作され、従って、スイッチ155と
の間でデータをやり取りするための2.4ギガバイト/
秒のデータ帯域巾をサポートする。これは、最大38.
4ギガバイト/秒の生の相互接続データ帯域巾、及び1
9.2ギガバイト/秒の二等分データ帯域巾をスイッチ
に与える。
【0041】大型のSMPシステムは、マルチプロセッ
サノード100a−100hの各々が全システムメモリ
のアドレス可能な部分を含むか又は物理的メモリの分割
部分を含むような分散型共用メモリシステムである。本
発明の1つの実施形態では、全システムメモリに243
の物理的アドレス位置が存在する。SMPマルチプロセ
ッサシステム100の1つの実施形態は、「大フォーマ
ット」及び「小フォーマット」と称する2つのアドレス
フォーマットをサポートする。大フォーマットは、各ノ
ードのプロセッサが動作するところの43ビットの物理
的アドレスを、マルチプロセッサシステムに使用するた
めの43ビットの物理的アドレスに直接マップする。大
フォーマットアドレスを使用すると、物理的メモリアド
レスのビット<38:36>をノード識別番号として使
用することができる。アドレスビット38:36は、メ
モリスペースアドレスのホームノードを直接デコード
し、一方、アドレスビット38:36の逆数は、I/O
スペースアドレスのホームノードをデコードし、ここで
「ホーム」とは、メモリスペース又はI/Oスペースに
関連したメモリ及びI/Oデバイスが存在するところの
物理的マルチプロセッサノードを指す。
【0042】小フォーマットのアドレスモードは、マル
チプロセッサシステムに4つ以下のノードが存在するこ
とを仮定するものである。小フォーマットは、各ノード
のプロセッサが36ビットの物理的にアドレスされたシ
ステムで動作できるようにする。小フォーマットにおい
て、物理的アドレスのビット34:33は、データ又は
I/Oデバイスのホームノード番号を識別する。しかし
ながら、たとえCPUが36ビットの物理的アドレスを
用いて動作しても、マルチプロセッサシステムは、デー
タ位置を特定するのに43ビットの物理的アドレスを一
貫して使用し、物理的アドレスのビット37:36がデ
ータ又はI/Oデバイスのホームノード番号を識別す
る。従って、CPUにより発生された小フォーマットア
ドレスと、データライン13a−13hを経てハイアラ
ーキースイッチ155へ送信されるものとの間で何らの
変換が実行される。
【0043】マルチプロセッサシステム150のここに
示す構成は、32個のプロセッサ間に広帯域巾のキャッ
シュコヒレントな共用メモリを与えることができる。本
発明の1つの実施形態による大型SMPの別の実施形態
が図7Bに示されており、ここでは、2つのマルチプロ
セッサノード100a及び100bがハイアラーキース
イッチを使用せずに互いに接続される。むしろ、2つの
マルチプロセッサノードは、それらのグローバルポート
出力を互いに接続することにより直接接続される。図7
Bの2ノード実施形態が使用されるか、図7Aのマルチ
ノード実施形態が使用されるかに拘わりなく、大きなア
ドレススペース及び処理能力をもつマルチプロセッサシ
ステムが得られる。
【0044】両実施形態において、システムメモリアド
レススペース及びI/Oアドレススペースは、全てのノ
ード100a−100h間にセグメントで物理的に分配
される。システムの各ノードは、メモリスペースの物理
的アドレスの上位3ビットを使用してアクセスされるメ
インメモリの一部分を含む。従って、各メモリ又はI/
Oアドレスは、1つのノードのみにおける1つの唯一の
メモリ位置又はI/Oデバイスへとマップされる。従っ
て、上位3つのアドレスビットは、メモリ又はI/Oア
ドレスがマップされるノードである「ホーム」ノードを
識別するためのノード番号を与える。各マルチプロセッ
サノードは、それらのホームノード又は他のマルチ処理
ノードに記憶された共用メモリの部分をアクセスするこ
とができる。ホームノードがプロセッサ自身のノードで
あるところの共用メモリブロックにプロセッサがアクセ
ス(ロード又は記憶)するときには、参照は、「ローカ
ル」メモリ参照と称される。ホームノードがプロセッサ
自身のノード以外のノードであるようなブロックを参照
する場合には、参照は、「リモート」又は「グローバ
ル」メモリ参照と称する。ローカルメモリアクセスの待
ち時間は、リモートメモリアクセスの待ち時間と異なる
ので、SMPシステムは、非均一メモリアクセス(NU
MA)アーキテクチャを有すると言える。更に、システ
ムはコヒレントなキャッシュを備えているので、システ
ムは、キャッシュコヒレントなNUMAアーキテクチャ
ーと呼ばれる。
【0045】ここに示すキャッシュコヒレントなNUM
Aアーキテクチャは、高い性能と低い複雑さに寄与する
多数の特徴を含む。設計上の1つの特徴は、メッセージ
間の順序の固執及び利用である。メッセージがある順序
特性に基づいてシステムに流れるよう保証することによ
り、オペレーションの待ち時間を著しく短縮することが
できる。例えば、記憶オペレーションは、記憶が完了し
たとみなされる前に無効メッセージがそれらの最終的な
行先プロセッサに供給されることを必要とせず、むし
ろ、無効メッセージが行先プロセッサへと通じるある順
序付けされた待ち行列に入れられるや否や記憶が完了し
たとみなされる。更に、ある順序が維持されるよう保証
することにより、設計上、確認又は完了メッセージの必
要性が排除される。メッセージは、それらがある待ち行
列に入れられた順序でそれらの行先に到達するように保
証される。従って、メッセージがその行先に到達したと
きに確認を返送する必要性が排除される。これは、シス
テムの帯域巾を改善する。
【0046】更に、事象順序及びメッセージ順序は、
「ホットポテト」オペレーションを行うのに使用され
る。ある待ち行列に順序を利用することにより、ディレ
クトリ又はDTAGコントローラのようなコントローラ
は、単一ビジットにおいて要求をリタイアすることがで
きる。他の要求との競合により要求を否定的に確認しそ
して再トライする必要はない。「ホットポテト」オペレ
ーションの結果として、公平さ及び欠乏の問題が解消さ
れる。設計に使用される第2の特徴は、仮想チャンネル
である。仮想チャンネルとは、メッセージを「チャンネ
ル」へと分類する構成であって、チャンネルは物理的な
リソースを共用する(従って、「仮想」である)が、各
チャンネルは、他のものとは独立して流れ制御される。
仮想チャンネルは、システムのメッセージ間で流れに依
存しそしてリソースに依存するサイクルを排除すること
により、キャッシュコヒレンスプロトコルにおける停滞
を排除するのに使用される。これは、選択されたメッセ
ージを否定的に確認しそしてそれに対応するコマンドを
再トライすることにより停滞を検出しそして停滞状態を
解消する機構を用いた公知のNUMAマルチプロセッサ
におけるキャッシュコヒレンスプロトコルとは対照的で
ある。
【0047】チャンネルの使用について以下に簡単に説
明するが、詳細な説明は後で行う。上述したように、メ
ッセージは、「チャンネル」と称する論理的なデータ路
を用いて大型SMP内をルート指定される。本発明の1
つの実施形態には、以下のチャンネルが含まれる。即
ち、要求側プロセッサから、トランザクションのアドレ
スに対応するホームノードのARBバスへトランザクシ
ョンを搬送するためのQ0チャンネルと、ホームARB
バスから1つ以上のプロセッサ及びIOPへトランザク
ションを搬送するためのQ1チャンネルと、所有者プロ
セッサから要求側プロセッサへデータ記入トランザクシ
ョンを搬送するためのQ2チャンネルとである。変更さ
れたデータを書き込むためにプロセッサからメモリへビ
クティム(Victim)トランザクションを搬送するために
Q0Vicチャンネルを設けることもできる。更に、Q
0Vicチャンネルは、ビクティムトランザクションの
背後に保持しなければならないQ0トランザクションを
搬送するのに使用できる。最後に、プロセッサからIO
PへIOスペーストランザクションを搬送するためにQ
IOチャンネルが設けられる。
【0048】チャンネルは、以下に示すようなハイアラ
ーキーを構成する。 (最低)QIO>Q0Vic>Q0>Q1>Q2(最
高) 以下に述べるように、停滞を回避するために、いずれの
チャンネルのメッセージも、下位チャンネルのメッセー
ジによって決して阻止されてはならない。順序付け特性
及び仮想チャンネルを形成しそして使用する機構の設計
及び実施に関する詳細は、後で述べる。従って、図7A
及び7Bに示すように、大型SMPは、図2のSMPノ
ードを任意の数だけ互いに接続することにより形成する
ことができる。図7A及び7Bに示すような大型SMP
システムのオペレーションは、以下に3つの部分につい
て説明する。第1に、大型SMPに含まれるハードウェ
ア要素について説明する。次いで、SMPのプロセッサ
間にコヒレントなデータ共用を与えるキャッシュコヒレ
ンスプロトコルについて説明する。更に、ハイアラーキ
ースイッチの仮想チャンネルのために設けられたサポー
ト機構を含む仮想チャンネルの実施及び使用について説
明する。
【0049】大型SMPのハードウェア要素 マルチプロセッサノードの各々には、チャンネルを用い
てコヒレントなデータ共用を実施するための多数の要素
が設けられる。図6に戻ると、これらの要素は、ディレ
クトリ140と、DTAG20と、IOPタグ14b
と、グローバルポート120と、ディレクトリ140と
を備えている。更に、シリアル化ポイントのハイアラー
キーは、キャッシュコヒレンスプロトコルを容易にする
ために参照の順序を維持できるようにする。これら要素
の各々について、以下に詳細に述べる。グローバルポート グローバルポート120は、マルチプロセッサノード1
00を、ハイアラーキースイッチリンク170を経て1
つ以上の同様に構成されたマルチプロセッサノードに直
接接続できるようにする。各ノード100は対称的なマ
ルチプロセッサシステムとして動作するので、システム
により多くのノードが追加されるにつれて、使用可能な
アドレススペース及び処理能力が増加される。
【0050】図8は、グローバルポート120の拡張ブ
ロック図である。グローバルポートは、トランザクショ
ン追跡テーブル(TTT)122と、ビクティムキャッ
シュ124と、マルチプロセッサノードからハイアラー
キースイッチへ送られるパケットを記憶するためのパケ
ット待ち行列127、122、123及び125と、ハ
イアラーキースイッチから受け取られるパケットを記憶
するためのパケット待ち行列121とを備えている。グ
ローバルポート120は、ARBバス130と、ローカ
ルスイッチの2つの専用ポート即ちGPリンク入力13
2b及びGPリンク出力132aとを経てノードの他の
ロジック(特にQSAチップ)と通信する。TTTは、
マルチプロセッサノードにおいて保留中のトランザクシ
ョン、即ちノードからグローバルポートを経て発生され
て、他のマルチプロセッサノード又はハイアラーキース
イッチからの応答を待機しているトランザクションを追
跡する。グローバルポートにコマンドが送られるたび
に、TTTにエントリが形成される。対応する応答がノ
ードに受け取られたときに、TTTエントリがクリアさ
れる。TTTは、2つの部分、即ちQ0TTT及びQ1
TTTで構成され、Q0及びQ1は、上記のようにQ0
及びQ1チャンネルを進むパケットを指す。エントリー
がTTTにいかに割り当てられるか及びそれがいつリタ
イアされるかについては、以下に詳細に述べる。
【0051】又、グローバルポート120は、ビクティ
ムキャッシュ124を含む。ビクティムキャッシュ12
4は、マルチプロセッサノードの各プロセッサから受け
取られて別のマルチプロセッサノードのメモリに向けら
れるビクティム化データを記憶する。ビクティム化デー
タとは、プロセッサのキャッシュ位置に記憶されてその
プロセッサにより変更されたデータである。変更データ
を記憶するキャッシュ位置に記憶する必要のある新たな
データがプロセッサに受け取られると、変更データは、
ビクティム化されると言われ、ビクティムデータと称さ
れる。ビクティムキャッシュ124は、プロセッサから
リモートマルチプロセッサノードのメモリへ向けられた
ビクティムデータからのビクティムデータの一時的な記
憶装置である。グローバルポートを経て別のノードへビ
クティムデータを送信するための機会があるときには、
マルチプレクサ167は、ビクティムキャッシュ124
からバス170の出力部分にデータを供給するように切
り換えられる。グローバルポートにビクティムキャッシ
ュを設けることにより、個々のプロセッサがグローバル
システムのメモリ書き込み待ち時間を待機せずに、プロ
セッサが各々のビクティムデータバッファを空にするこ
とができる。むしろ、ビクティム書き込みは、使用でき
るデータサイクルがあるときに書き込みが実行されるよ
うにグローバルポートにより制御される。ビクティムキ
ャッシュからデータを解放する適切さに関連した幾つか
の制御の問題があるが、これらは以下に説明する。
【0052】DTAG及びIOPタグ DTAG及びIOPタグは、小型のSMPシステムにも
含まれるが、これについては以下に詳細に述べる。DT
AG20は、マルチプロセッサノードのプロセッサのキ
ャッシュに記憶されたデータブロック各々に対する状態
情報を記憶する。同様に、IOタグ14aは、IOPに
記憶された各データブロックに対する状態情報を記憶す
る。ディレクトリは、どのマルチプロセッサノードがデ
ータのコピーを記憶するかを識別するおおよその情報を
与えるが、DTAG及びIOタグは、マルチプロセッサ
ノード内のどのプロセッサがデータのコピーを記憶する
かに関する正確な指示を与えるのに使用される。それ
故、DTAG及びIOタグは、参照情報がマルチプロセ
ッサノードに到達したときに、そのノードのどのプロセ
ッサがターゲットとなるべきかを決定するのに使用され
る。
【0053】図6に示すように、DTAG20及びIO
Pタグ14bは、QSAチップ18に接続されたメモリ
領域を参照するアドレスを監視するためにARBバス1
30に接続される。DTAGは、4つのプロセッサ12
a−12dに対応する4つのセグメントに分割される。
各プロセッサは、メモリ13からのデータのサブセット
を一時的に記憶するためのキャッシュ(図示せず)を備
えている。各プロセッサのキャッシュに記憶されたメモ
リのブロックの上位アドレスビット(タグ)を記憶する
ためのタグ記憶装置が各キャッシュに関連される。DT
AG20の各セグメントは、関連プロセッサのキャッシ
ュタグの状態を指示するデータを維持する。処理ユニッ
トの外部のDTAG20にタグのコピーを記憶すること
により、システムは、ARBバスを経て受け取ったコマ
ンドをフィルタし、そしてプロセッサのキャッシュのデ
ータに関連した調査(読み取り)及び無効化コマンドの
みを各プロセッサに供給することができる。IOPタグ
14aは、IOPキャッシュ14cに記憶されたデータ
ブロック各々の上位アドレスビットを記憶する。IOP
タグ記憶装置は、プロセッサ12a−12dの各々に維
持されたタグ記憶装置と同様である。
【0054】DTAG20及びIOPタグ14aの各エ
ントリは、多数の状態ビットを含む。DTAG状態ビッ
トは、次の4つの状態、即ちInvalid(無効)、
Clean(クリーン)、Dirty Not Pro
bed、及びDirty Probedのうちの1つを
指示する。IOPタグのエントリの状態ビットは、次の
2つの状態、即ちValid(有効)及びDirty
(ダーティ)のうちの1つを指示する。「有効」ビット
は、関連キャッシュの対応エントリに記憶されたデータ
が、メモリに記憶されたデータと一致することを指示す
る。「ダーティ」ビットは、関連キャッシュの対応エン
トリに記憶されたデータが関連プロセッサによって変更
されそしてメモリに記憶されたデータに一致しないこと
を指示する。
【0055】DTAG20及びIOPタグ14bは、マ
イクロプロセッサノード100のARBバスにコマンド
が現れるたびにアクセスされる。「無効」の状態がプロ
セッサ1のDTAGアクセスに応答して返送される場合
には、ノードのプロセッサ1は、メモリアドレスに関連
したデータの有効コピーを記憶しない。「有効」の状態
がIOPタグ14aへのアクセスから返送される場合に
は、IOPキャッシュ14cがデータの有効コピーを記
憶する。「クリーン」状態がプロセッサ1に対するDT
AGアクセスに応答して返送される場合には、これは、
プロセッサ1がメモリアドレスに対応するデータの無変
更コピーを有するが、そのデータを読み取るための他の
プロセッサによる試みがなされていないことを指示す
る。Dirty Not Probedの状態がDTA
Gに応答して返送される場合には、これは、プロセッサ
1がメモリアドレスに対応するデータの変更コピーを有
し、そしてプロセッサが最後にデータを変更して以来、
少なくとも1つのプロセッサがデータを読み取る試みを
していることを指示する。
【0056】ディレクトリオペレーション 一般に、ディレクトリは、関連マルチプロセッサノード
(ホームノード)におけるメモリの各ブロックの所有権
情報を与えるのに使用され、メモリのブロックは、一般
に、メモリとSMPシステムのプロセッサとの間に転送
される最小量のデータである。例えば、本発明の1つの
実施形態において、ブロックは、パケットのサイズと同
様であり、即ち512ビット(64バイト)のデータで
ある。更に、ディレクトリは、どのマルチプロセッサノ
ードがメモリデータのブロックのコピーを記憶するかを
指示する。従って、読み取り型のコマンドの場合に、デ
ィレクトリは、データの最新バージョンの位置を識別す
る。ビクティム型のコマンドの場合には、データの変更
ブロックがメモリに書き戻される場合に、ディレクトリ
は、データの変更ブロックが現在のものであってメモリ
に書き込まねばならないかどうか決定するために検討さ
れる。それ故、ディレクトリは、参照情報がリモートマ
ルチプロセッサノードのプロセッサにより発生されたも
のであるかローカルマルチプロセッサノードのプロセッ
サにより発生されたものであるかに拘わりなく、関連す
るマルチプロセッサノードのメモリブロックへの参照に
対する第1アクセスポイントである。
【0057】ディレクトリは、対応するノード100に
おいてメモリ13の各64バイトのデータブロック(以
下、キャッシュラインとも称する)に対して1つの14
ビットエントリを記憶する。メモリ13と同様に、ディ
レクトリは、メモリアドレスがノードNに存在する場合
に、対応するディレクトリエントリもノードNに存在す
るように、システムのノードにわたって物理的に分配さ
れる。図9を参照すれば、ディレクトリエントリ140
aの1つの実施形態は、所有者IDフィールド142及
びノード存在フィールド144を含むように示されてい
る。所有者IDフィールドは、各64バイトブロックに
対する6ビットの所有者情報を含む。所有者IDは、ブ
ロックの現在所有者を特定し、現在所有者は、システム
における32個のプロセッサの1つ、又はシステムにお
ける8個のI/Oプロセッサの1つ、又はメモリのいず
れかである。8ビットのノード存在情報は、システムの
8個のノードのどれがキャッシュラインの現在バージョ
ンを獲得したか指示する。ノード存在ビットは、同じノ
ードにおける4つのプロセッサの累積状態を1ビットで
表わすおおよそのベクトルである。共用データの場合に
は、2つ以上のノードが、情報を記憶する少なくとも1
つのプロセッサを有する場合に、2つ以上のノード存在
ビットがセットされる。
【0058】時々、状態情報のある断片がDTAG又は
ディレクトリから得られる。このような場合、DTAG
からの状態情報を使用するのが好ましい。というのは、
これは非常に高速で検索されるからである。例えば、メ
モリアドレスの所有者プロセッサがそのアドレスに対し
ホームノードに配置される場合には、所有者IDを供給
するのにDTAGが使用される。性能上の理由でDTA
Gによりサービスされない情報又は参照については、デ
ィレクトリ140は、全てのコヒレンス性判断の焦点で
あり、従って、多数の機能を実行する。ディレクトリ
は、メモリデータブロックの所有者を識別する。所有者
は、プロセッサ又はメモリのいずれかである。ディレク
トリからの所有者情報は、データブロックの最新バージ
ョンのソースを決定するために読み取り型コマンド(例
えば、読み取り、読み取り−変更)により使用される。
又、所有者情報は、以下に詳細に述べるようにビクティ
ム化データをメモリに書き戻さねばならないかどうか決
定するのにも使用される。
【0059】全ての読み取り型コマンドに対して、デー
タの所有者を識別するのに加えて、ディレクトリは、プ
ロセッサからの「クリーン−ダーティ(Clean-to-Dirt
y)」及び「シェアド−ダーティ(Shared-to-Dirty)」コ
マンドを分析するのにも使用される。「クリーン−ダー
ティ」コマンドは、プロセッサがそのキャッシュにおい
て現在「クリーン」状態にあるキャッシュラインを変更
するよう希望するときにプロセッサにより発生される。
「シェアド−ダーティ」コマンドは、「ダーティ−シェ
アド」状態にあるキャッシュラインを変更するよう希望
するときに発生される。これらのコマンドは、ホームA
RBバスに送られ、そこで、ディレクトリは、プロセッ
サがキャッシュラインの最新バージョンを有するかどう
か決定する。もしそうであれば、コマンドは成功とな
り、プロセッサは、キャッシュラインを変更することが
許される。さもなくば、コマンドは失敗となり、プロセ
ッサは、最初に、キャッシュラインの最新バージョンを
獲得しなければならない。これらの記憶型オペレーショ
ンは、ディレクトリのノード存在情報を使用して、成功
又は失敗を決定する。
【0060】上記のように、ディレクトリの存在ビット
は、記憶型コマンドが発生されたときに各データブロッ
クのコピーでマルチプロセッサノードを識別する。記憶
コマンドは、キャッシュラインの内容が更新されようと
していることを指示する。関連するディレクトリエント
リの存在ビット144を検討することにより、記憶コマ
ンドがディレクトリ140に受け取られたときに、存在
ビットを有するノードを用いて、これらのマルチプロセ
ッサノードをそのノードにおけるキャッシュラインのコ
ピーで識別し、従って、各ノードにおけるキャッシュラ
インを無効化できるようにする。従って、ディレクトリ
及びDTAGは、ローカルマルチプロセッサのメモリに
おける各データブロック及びローカルプロセッサのキャ
ッシュに記憶された各データブロックに対する状態情報
を与えるように協働する。ホームノードのディレクトリ
は、キャッシュブロックのコピーの状態に関するおおよ
その情報を供給する。次いで、無効化コマンドがディレ
クトリにより識別されたノードへと進み、そこで、DT
AGがアクセスされて、コピー情報を更に改善する。従
って、これらノードにおけるDTAGは、各ノードのど
のプロセッサがそれらのキャッシュにラインのコピーを
記憶するか指示する。
【0061】TTT:TTTは、マルチプロセッサノー
ドからの保留中のトランザクション、即ち別のマルチプ
ロセッサノード又はハイアラーキースイッチからの応答
を待機している参照を追跡するのに使用される。保留中
トランザクションに関する情報は、関連メモリアドレス
へのその後のコマンドを処理する際にキャッシュコヒレ
ンスプロトコルにより使用される。図10を参照すれ
ば、TTT122の1つの実施形態は、アドレスフィー
ルド152と、コマンドフィールド154と、コマンダ
IDフィールド156と、ビット158a−158cを
含む多数の状態ビット158とを含むように示されてい
る。アドレスフィールド152は、現在進行中であるト
ランザクションに対するキャッシュラインのアドレスを
記憶し、一方、コマンドフィールドは、現在進行中であ
るトランザクションに対するキャッシュラインに関連し
たコマンドを記憶する。コマンダIDフィールド156
は、コマンドフィールドに記憶されたコマンドを開始し
たプロセッサのプロセッサ番号を記憶する。状態ビット
158は、コマンドが進行中であるときにコマンドの状
態を表わす。或いは又、状態ビット158は、進行中で
あるコマンドの種々の特性をあらわすように使用されて
もよい。
【0062】例えば、「記入」状態ビット158aは、
読み取り型コマンドに応答して「記入」データ応答が受
け取られたときに更新される。「シャドー」状態ビット
158bは、グローバルポートを経て発生されたコマン
ドが「シャドー」型コマンド(以下に詳細に述べる)で
ある場合にセットされる。ACK状態ビット158c
は、確認型応答を期待しているメッセージが応答を受信
した場合にセットされる。応答が到着した場合に、この
ビットはクリアされる。TTTに含むことのできる全て
の状態ビットが示されているのではないことに注意され
たい。むしろ、以下の説明に関連のある状態ビットが含
まれている。更に、メモリのコヒレンス性を維持するた
めに必要と考えられれば、他の状態ビットを設けてもよ
く、従って、本発明は、TTTにおける特定のビット指
定に限定されるものではないことが明らかであろう。
【0063】従って、ディレクトリ、DTAG、IOP
タグ及びTTTの各々は、SMPシステムにおけるキャ
ッシュラインのコヒレンス性(以下、キャッシュコヒレ
ンス性と称する)を維持するのに使用される。これら要
素の各々は、ハイアラーキースイッチ155に接続され
たマルチプロセッサノード間にコヒレント通信を与える
ためにグローバルポートとインターフェイスする。
【0064】シリアル化ポイント:上記要素に加えて、
各マルチプロセッサノードにシリアル化ポイントを設け
ることによりデータ共用コヒレンス性が維持される。本
発明の1つの実施形態において、各マルチプロセッサノ
ードにおけるシリアル化ポイントは、ARBバス130
である。全てのQ0参照は、ローカルプロセッサにより
発生されたものであるかリモートプロセッサにより発生
されたものであるかに拘わりなく、QSAによりARB
バス130を経てディレクトリ140及びDTAG20
へ供給される。参照がディレクトリ及び/又はDTAG
をアクセスすると、それにより得られるQ1チャンネル
コマンドが厳密な順序でARBバスに出力され、ここ
で、順序は参照のシリアル化順序である。マルチプロセ
ッサノードの各々にシリアル化ポイントを設けることに
より、SMPにおいて実施されるデータ共用コヒレンス
プロトコルが相当に簡単化される。
【0065】マルチプロセッサノードの各々にシリアル
化ポイントを設けるのに加えて、ハイアラーキースイッ
チ155は、SMPシステムに第2のシリアル化ポイン
トを与える。以下に詳細に述べるように、ハイアラーキ
ースイッチは、第1のシリアル化ポイントに導入された
コヒレンス性が大型のSMPシステムに維持されるよう
確保するある順序付けルールに適合する。 グローバルポート/ハイアラーキースイッチインター
フェイス:図11は、8個の入力ポート155i0−1
55i7及び8個の出力ポート155o0−155o7
を含むハイアラーキースイッチ155のブロック図であ
る。ハイアラーキースイッチ155の入力ポート155
i0−155i7は、接続されたマルチプロセッサノー
ド各々のグローバルポートからパケットを受け取る。ハ
イアラーキースイッチの出力ポート155o0−155
o7は、接続されたマルチプロセッサノード各々のグロ
ーバルポートへパケットを供給する。
【0066】本発明の1つの実施形態において、受信し
たパケットをバッファするためのバッファ160a−1
60hが各入力ポートに関連される。図11の実施形態
は、各入力に1つのバッファを示しているが、いかなる
数の入力ポート間にバッファが共用されてもよい。各パ
ケットは、5つのチャンネルのいずれか1つと関連され
る。本発明の1つの実施形態では、以下に述べるよう
に、各入力バッファ160a−160hの部分が、ある
チャンネルのパケットを専用に記憶するようにされる。
従って、グローバルポートからハイアラーキースイッチ
155への流れ制御は、チャンネルベースで実行され
る。チャンネルベースでスイッチへのデータの流れを制
御しそして入力バッファの部分を選択されたチャンネル
に専用とすることにより、スイッチは、SMPシステム
におけるマルチプロセッサノード間で停滞のない通信を
行う。
【0067】停滞のない通信を与えるのに加えて、ハイ
アラーキースイッチ155は、更に、メモリのコヒレン
ス性を確保するためにSMPシステムの順序付け制約を
サポートするように設計される。順序付け制約は、スイ
ッチ155から関連マルチプロセッサノードのグローバ
ルポートへ送出されるパケットの順序を制御することに
より課せられる。いずれかの入力バッファ160a−1
60hからのパケットは、マルチプレクサ182a−1
82hを経ていずれかの出力ポートへ送られる。更に、
以下に述べるように、スイッチ155は、パケットをマ
ルチキャスティングすることができる。従って、1つの
入力バッファからのパケットは、いかなる数の出力ポー
トに送ることもできる。グローバル出力ポートに順序を
強制することにより、マルチプロセッサノード各々に得
られるシリアル化順序を維持して、完全にコヒレントな
データ共用機構をSMPシステムに形成することができ
る。
【0068】ハイアラーキースイッチにおける停滞の回
上述したように、図7Aの8個のノードの各々は、ハイ
アラーキースイッチにデータを供給し、全てのノードが
データを同時に供給することもある。パケットは、異な
る仮想チャンネルに供給される多数の異なるチャンネル
形式(Q0、Q0Vic、Q1、Q2及びQIO)に分
割され、ここで、仮想チャンネルとは、本質的に、他の
チャンネルとの共通の相互接続部を共用するがその相互
接続部のいずれかの端において独立してバッファされる
特定形式のパケットに専用のデータ経路である。各ノー
ドのグローバルポートとハイアラーキースイッチとの間
には1つのデータ経路しかないので、異なる仮想チャン
ネルからの全てのパケットは、1つのデータ経路を使用
してハイアラーキースイッチに書き込まれる。
【0069】8個のノード100a−100hの各々
は、ハイアラーキースイッチへデータを送信することが
できるので、全てのメッセージがスイッチにより受信さ
れて、スイッチから適当な順序で供給されるよう適切に
確保するために、ある形式の制御が必要となる。更に、
本発明の1つの目的は、対称的なマルチプロセッサシス
テムに停滞(デッドロック)が生じないよう保証するた
めに上位順序のパケット形式が下位順序のパケット形式
により阻止されないよう確保することである。本発明の
1つの実施形態では、最高順序から最低順序までのパケ
ットの順序は、Q2、Q1、Q0、Q0Vic及びQI
Oである。本発明の1つの特徴によれば、スイッチの入
力ポートに到着するパケットの流れ制御を行うための機
構であって、上記の停滞回避ルールが常に満足されるよ
う確保する機構が提供される。更に、スイッチにおいて
使用できるバッファは最適に利用されねばならず、そし
て最大の帯域巾が維持されねばならない。
【0070】本発明の1つの実施形態によれば、ハイア
ラーキースイッチへのデータの書き込みを制御するため
の制御装置は、パケットの各形式に対し、ハイアラーキ
ースイッチのバッファに専用スロットを設けることによ
り実施される。又、バッファは、任意の形式のパケット
を記憶するのに使用できる多数の一般的なスロットも含
んでいる。ハイアラーキースイッチに専用のバッファス
ロットを設けることにより、上位順序のパケット形式が
常にスイッチを通る経路を使用できるよう保証すること
によって停滞を回避することができる。更に、使用でき
る一般的スロット及び専用スロットの数を監視し、そし
てバッファに記憶されるパケットの異なる形式の数を監
視することにより、ハイアラーキースイッチのバッファ
が容量に達したときにノードがバッファに書き込みする
のを防止するような簡単な流れ制御機構を実施すること
ができる。
【0071】図12Aには、多数のソースノードによる
共通の行先バッファへの書き込みを制御するのに使用す
るための制御ロジックの一例が示されている。図12A
のブロック図には、2つの異なるノードのグローバルポ
ート120a及び120bが一例として示されている。
図12Aにおいて、ノード100a及び100bのグロ
ーバルポート各々120a及び120bの部分は、ハイ
アラーキースイッチ155へ転送するためにQ0/Q0
Vic、Q1、Q2及び一般形式のパケット(Q0、Q
0Vic、Q1、Q2又はQIOパケットのいずれか)
を各々記憶するためのエントリ135a−135bを含
むバッファ135を備えて詳細に示されている。バッフ
ァ135にはマルチプレクサ167aが接続され、GP
アービター134からの選択信号を使用してリンクを経
てハイアラーキースイッチへ送るためにパケット形式の
1つを選択する。
【0072】更に、各グローバルポートは、専用のカウ
ントレジスタ136を備えている。この専用のカウント
レジスタは、パケットの各Q0/Q0Vic、Q1及び
Q2チャンネル形式に対して、ハイアラーキースイッチ
155において現在保留となっているチャンネル形式の
パケットの数のカウントを記憶する。このカウントは、
各チャンネル形式のパケットがハイアラーキースイッチ
へ転送されるときに増加され、そしてパケットがハイア
ラーキースイッチから転送されるときに減少される。本
発明の1つの実施形態において、ハイアラーキースイッ
チ155は、8個の入力ソースの各々に1つのバッファ
を備えている。図12Aには、2つのグローバルポート
120a及び120bに対応する2つのバッファ160
a及び160bのみが示されている。本発明の1つの実
施形態では、バッファ160a及び160bの各々に少
なくとも(m−1)xn個の専用スロットがあり、但
し、mは、バッファに専用エントリを有する仮想チャン
ネル形式の数に対応し、そしてnは、バッファを共用す
るノードの数に対応する。図12Aの実施形態におい
て、各バッファは、8個のエントリを有する。エントリ
のうちの5つは、一般的エントリであり、グローバルポ
ート135から送られたパケットの形式を記憶すること
ができる。残りの3つのエントリの各々は、特定形式の
パケットを専用に記憶し、即ち1つのエントリは、Q0
/Q0Vicパケットを専用に記憶し、1つのエントリ
は、Q1形式パケットを専用に記憶し、そして1つのエ
ントリは、Q2形式パケットを専用に記憶する。
【0073】専用エントリがバッファ160a及び16
0bの固定位置に存在するものとして示されているが、
実際には、バッファのいずれの位置も専用のバッファ位
置であり、即ちエントリの位置に拘わりなく、パケット
の各特定形式ごとにバッファには常に1つの専用エント
リがある。ハイアラーキースイッチは、更に、各バッフ
ァ160a及び160bに対し、専用カウンタ162a
及び162bと、フラグレジスタ163a及び163b
とを含む。図12Aの実施形態において、専用カウンタ
162aは、4つのエントリを有し、その3つは、バッ
ファ160aに現在記憶されているQ0/Q0Vic、
Q1及びQ2パケットの数を記憶するためのもので、そ
して1つは、バッファに使用される一般的エントリの数
のカウントを記憶するためのものである。フラグレジス
タは、3つのビットを含み、各ビットは、パケットのQ
0/Q0Vic、Q1及びQ2形式の1つに対応し、そ
して関連する専用カウントがゼロであるかどうか(即
ち、その形式のパケットの専用エントリが使用されたか
どうか)を指示する。従って、フラグレジスタの値は、
その形式の少なくとも1つのパケットがバッファに記憶
されたことを指示する1であるか、又はその形式のパケ
ットがバッファに記憶されないことを指示する0であ
る。
【0074】更に、ハイアラーキースイッチ155は、
各バッファ160a及び160bに対し、トランシット
カウント164a及び164bを各々含む。トランシッ
トカウントは、各ソースに対して、所与のデータサイク
ル中にトランシット状態であるいずれかの形式の保留中
パケットの数を維持する。所与のデータサイクル中にト
ランシット状態にあるパケットの数は、ハイアラーキー
スイッチとグローバルポートとの間の流れ制御待ち時間
に直接関係している。流れ制御信号は、ハイアラーキー
スイッチからグローバルポートへ送られて、ハイアラー
キースイッチへのデータの送信を停止するようにグロー
バルポートに通知する。流れ制御待ち時間(L)は、ハ
イアラーキースイッチによる流れ制御信号のアサート
と、グローバルポートによるデータ送信の停止との間に
生じるデータ転送サイクルの数として測定される。
【0075】又、ハイアラーキースイッチは、各バッフ
ァ168a及び168bの書き込みを制御するための書
き込み制御ロジック166a及び166bも備えてい
る。この書き込み制御ロジックは、ライン168aに
「流れ制御」信号をそしてライン168bに「確認(A
CK)」信号<3:0>をアサートすることにより関連
バッファへのデータの流れを制御する。「流れ制御」及
びACK信号は、各データ転送サイクルに送信される。
上記のように、「流れ制御」信号は、接続されたグロー
バルポートによるパケットデータの送信を停止するのに
使用される。ライン168bのACK信号<3:0>
は、パケットの専用形式の各々に対して1ビットを含
み、そして接続されたグローバルポートに、その形式の
パケットが関連バッファから解放されたことを通知する
のに使用される。従って、ACK信号は、グローバルカ
ウントにより、専用カウンタ136の値を増加するのに
使用される。
【0076】書き込み制御ロジックは、バッファの使用
可能な全ての一般的エントリが、ハイアラーキースイッ
チへのトランシット状態にある考えられる全てのパケッ
トを受け入れるのに充分でないと決定されたときに、流
れ制御をアサートする。使用可能な一般的スロットの数
は、次の式Iにより決定することができる。 式I: Generic count=(バッファサイズ)−(バッファに使
用される一般的エントリの数)−(非アサートフラグの
数) 使用可能な一般的エントリの数が決定されると、式II
が真である場合に、流れ制御信号がアサートされる。 式II: Generic Count=(トランシットカウント)*(バッフ
ァを使用するノードの数) 従って、書き込み制御ロジック166は、使用中の一般
的及び専用のスロットの数、トランシットカウント及び
全バッファサイズを監視し、「流れ制御」信号をいつア
サートすべきかを決定する。
【0077】「流れ制御」信号をアサートしても、ソー
スノードのグローバルポートによる全ての送信は停止さ
れない。グローバルポートは、専用パケット形式に対応
する専用スロットがハイアラーキースイッチのバッファ
に使用できる場合に、専用パケットデータをハイアラー
キースイッチに常に転送する。従って、専用カウンタに
おけるいずれかの専用カウントの値がゼロに等しい場合
には、グローバルポートは、常に、対応する専用パケッ
ト形式のパケットデータを転送することができる。従っ
て、バッファに専用エントリを設けることにより、ハイ
アラーキースイッチを通る1つの形式のパケットの進行
が、そのスイッチを通る他のパケットの進行によって左
右されないように効果的に保証される。バッファ160
a及び160bに専用及び一般的なスロットを使用する
ことにより、各パケット形式ごとに最小数のスロットを
指定するだけでよい。トランシット状態のパケットの数
を追跡することにより、流れ制御を微細な粒度で行うこ
とができる。バッファの利用性及びバスの帯域巾の両方
が最大にされる。例えば、Xの一般的スロットしか使用
できないときには、流れ制御が1サイクル放棄され、そ
して次のサイクルに再アサートされる。その結果、Xま
でのメッセージを時間周期内に受け取ることができる。
【0078】図12Bは、ハイアラーキースイッチへデ
ータを供給するためにグローバルポートにより使用され
る方法を示すフローチャートである。このプロセスは、
1つの形式のパケットについて説明するが、他の形式の
パケットにも容易に拡張できる。ステップ169では、
ハイアラーキースイッチ155へ供給すべきパケットが
バッファ135a−135dの1つに存在するかどうか
GSアービター134において決定される。パケットが
ある場合には、ステップ171において、「流れ制御」
信号の状態がアービター134により評価される。「流
れ制御」信号がアサートされる場合には、ステップ17
2において、ハイアラーキースイッチにより送られるべ
きパケットの特定形式に対する専用カウントを検査し
て、それがゼロに等しいかどうか決定される。専用カウ
ントがゼロに等しくない場合には、その形式のパケット
に対するバッファ内の専用エントリが既に使用中であ
り、プロセスはステップ170へ戻り、そのパケット形
式の専用カウントがゼロに等しくなるまで又は流れ制御
信号がデアサートされるまで、ステップ169、171
及び172間をループする。ステップ172において専
用カウントがゼロに等しいと決定された場合には、ステ
ップ173において、GPアービター134は、適当な
選択信号をマルチプレクサ167へアサートし、所望の
パケットをハイアラーキースイッチ155へ送信する。
ステップ174において、パケットの選択された形式に
対応する専用カウントがグローバルポートの専用カウン
トレジスタ134及びハイアラーキースイッチ155の
専用カウントレジスタ162aにおいて増加され、そし
てフラグレジスタ163aの関連フラグがアサートされ
る。
【0079】上記のように、フラグレジスタ163a
は、一般的カウント及びトランシットカウントと共に使
用されて、次のデータサイクルに対する「流れ制御」信
号の状態を決定する。図13には、ハイアラーキースイ
ッチによる「流れ制御」信号のアサートを制御するため
のプロセスの一実施形態が示されている。ステップ17
5において、フラグレジスタ163aが検査されて、ゼ
ロに等しい専用カウントエントリの数が計数される。上
記のように、ゼロの数は、「流れ制御」がアサートされ
た後であってもバッファに接続された各ノードにより送
られる潜在的な専用パケットの数を指示する。従って、
図11の例においていずれのノードについても専用スロ
ットが全く使用されない場合には、フラグレジスタの全
てのエントリがゼロに等しくなり、従って、専用パケッ
トのために指定されねばならないバッファ位置が3つあ
ることを指示する。
【0080】フラグレジスタ163aの値が検査された
後、ステップ176において、使用可能な全一般的スロ
ットが上記式Iを用いて決定される。次いで、ステップ
177において、各ノードのトランシットカウントが決
定される。上述したように、トランシットカウントは、
所与のデータサイクル中にグローバルポートとハイアラ
ーキースイッチとの間でトランシット状態にあるメッセ
ージの数を示す。最悪の場合のトランシットカウント
は、流れ制御の待ち時間LにバッファNを使用するノー
ドの数を乗じたものに等しい。しかしながら、本発明の
1つの実施形態によれば、トランシットカウントの決定
には、「流れ制御」信号が手前のサイクル中にアサート
されたかどうかが考慮される。上記のように、「流れ制
御」信号が手前のサイクルにアサートされた場合には、
グローバルポートとハイアラーキースイッチとの間でト
ランシット状態となるパケットはない。例えば、手前の
J個の周期中に「流れ制御」がゼロであった場合には、
JxN個までのメッセージがトランシット状態となる。
しかしながら、J−1個の手前のデータサイクル中に
「流れ制御」信号がゼロであった場合には、(J−1)
xN個のメッセージのみがトランシット状態となる。
【0081】従って、本発明の1つの実施形態では、ソ
ース(グローバルポート)と行先(ハイアラーキースイ
ッチ)との間の全待ち時間を検査すると共に、手前のデ
ータサイクルにおけるソースと行先との間の相互作用を
検査することにより、トランシット状態のパケットの数
がインテリジェントに決定される。各ノードに対するト
ランシットカウントが決定された後に、ステップ178
において、上記の式IIを用いて保留中の専用パケット
及びトランシット状態のパケットを受け入れるに充分な
使用可能な一般的エントリがバッファにあるかどうかの
判断がなされる。使用可能な一般的パケットの全数が、
トランシット状態にあるパケットの数にバッファを共用
するノードの数を乗じた値より少ない場合には、ステッ
プ178において、「流れ制御」信号がグローバルポー
ト120aにアサートされ、ハイアラーキースイッチ1
55へのデータの供給が阻止される。しかしながら、全
カウントが、潜在的に受け取られるパケットの数をバッ
ファ160aで受け入れできることを指示する場合に
は、「流れ制御」信号がアサートされず、プロセスは、
次のデータサイクルのためにステップ175へ復帰す
る。
【0082】従って、トランシット状態にあるメッセー
ジの数と、流れ制御信号がアサートされた手前のサイク
ルの数とを追跡することにより、流れ制御は、グローバ
ルポートをハイアラーキースイッチに接続するデータリ
ンクの利用性が最大となるよう確保するように微同調さ
れる。 図11ないし13に示すバッファ書き込み制御
ロジック及び方法は、ノードからハイアラーキースイッ
チへのデータの送信に関して説明したが、本発明は、こ
のような構成に限定されるものではないことに注意され
たい。むしろ、本発明の1つの実施形態は、共通の受信
器に信号供給する多数のソースがありそして停滞を回避
する必要があるいかなる環境にも使用できる。
【0083】チャンネル順序付け制約をサポートするハ
イアラーキースイッチの機構:ハイアラーキースイッチ
からのデータの読み取りは、本質的に、パケットの順序
と、パケット間のデータ依存性との両方が維持されるよ
うに入力バッファから多数の出力ソースへデータを供給
することを含む。上述したように、パケットは種々のチ
ャンネルに供給される。異なるチャンネルにおいてパケ
ットに関連するのは、ある順序付け制約即ち依存性であ
る。本発明の1つの実施形態では、1つの順序付け制約
は、Q1チャンネルの全てのパケットが順序正しく維持
されることである。別のパケット順序付け依存性は、優
先順位の高いチャンネルを進行するパケットが、優先順
位の低いチャンネルを進行するパケットによって阻止さ
れてはならないことであり、チャンネルの優先順位は、
最も高いものから最も低いものへ、Q2、Q1、Q0、
Q0Vic及びQIOである。順序の維持は、以下に述
べる種々の技術を用いてSMP全体にわたり達成され
る。ハイアラーキースイッチにおいては、データ依存性
及びQ1チャンネル順序付けを満足するよう確保するた
めに3つの基本的なガイドラインに従う。これらのガイ
ドラインは、次の通りである。
【0084】ガイドライン1:所与のハイアラーキース
イッチ入力ポートに受け取られた多数のQ1パケットが
共通の出力ポートをターゲットとする場合には、Q1パ
ケットは、それらが入力ポートに現れたのと同じ順序で
出力ポートに現れる。 ガイドライン2:ハイアラーキースイッチにおいて多数
の入力ポートからのQ1パケットが共通の出力ポートへ
マルチキャスティングされるときには、Q1パケット
は、それらがターゲットとする全ての出力ポートに同じ
順序で現れる。 ガイドライン3:ハイアラーキースイッチの多数の入力
ポートからのQ1パケットの順序付けリストが多数の出
力ポートをターゲットとするときには、Q1パケット
は、全ての到来するQ1パケットの単一の共通の順序付
けに合致するように出力ポートに現れる。各出力ポート
は、共通の順序付けリストにおける幾つかの又は全ての
パケットを送信することができる。
【0085】コヒレンス性の目的で全体的なシステム順
序を維持するのに加えて、スイッチから出力されるパケ
ットを、アドレス及びデータバスの性能が完全に実現さ
れるように順序付けすることも望まれる。例えば、図1
4は、HSリンク170のアドレス及びデータバス構造
の利用を示すタイミング図である。HSリンク170
は、2対の単一方向性アドレス及びデータバスによりマ
ルチプロセッサノード100の各々に接続される。デー
タバスは、512ビットのデータパケットを搬送し、そ
してアドレスバスは、80ビットのアドレスパケットを
搬送する。データパケットの送信は、アドレスパケット
の送信の2倍のサイクル数を必要とする。書き込みコマ
ンドのようなあるコマンドは、アドレス及びデータパケ
ットの両方を含む。例えば、図14において、アドレス
パケット179aは、データパケット179dに対応す
る。各コマンドがアドレス及びデータパケットの両方を
含む場合には、アドレスバスの1つおきのアドレススロ
ットがアイドル状態となる。しかしながら、読み取りコ
マンドのような多数のコマンドは、アドレスパケットし
か含まず、データパケットを転送するためのデータバス
のスロットを必要としない。従って、全体的なシステム
性能を向上するためには、データ部分及びアドレス部分
の両方が「パック」され、即ちHSリンクのアドレス及
びデータ部分の各考えられるタイムスロットにアドレス
及びデータが存在するような順序でバスから送出すべき
パケットを選択するスイッチを有するのが好ましい。ア
ドレス及びデータがHSリンクにおいて「パック」され
るときには、HSリンクが最適に利用される。
【0086】多数の入力ポートを経て多数のソースから
データを同時に受け取りそして多数の出力ポートを経て
多数の行先へデータを供給できる一方、データ依存性を
満足し、システム順序を維持し、そしてデータ転送レー
トを最大にすることのできるハイアラーキースイッチを
実施するための種々の実施形態が提供される。これらの
種々の実施形態を、図15ないし18を参照して説明す
る。図15には、上記順序付け制約を実施することので
きるスイッチ181の1つの実施形態が示されている。
図11について述べたように、スイッチ155は、複数
のバッファ160a−160hを含む。入力バッファの
各々は、1書き込みポート/8読み取りポートバッファ
であり、8個の各入力の1つからパケットを受け取るよ
うに接続される。又、スイッチは、8個の出力ポートも
含むが、1つの出力ポート、即ち出力ポート<0>のみ
に対するロジックが示されている。残りの出力ポートに
対するロジックも同様であり、明瞭化のために、ここで
は詳細に述べない。
【0087】本発明の1つの実施形態では、各バッファ
の各エントリは、バッファのエントリに記憶されるパケ
ットのチャンネルを識別するチャンネルフィールド18
5を含む。更に、各エントリは、一連のリンクインデッ
クス186を含む。各リンクインデックスは、入力バッ
ファ160a−160hのエントリの1つに対するイン
デックスである。これらのリンクインデックスは、パケ
ット順序付け制約に基づきバッファ160aから同じチ
ャンネルを経て次々のパケットをアクセスするためのリ
ンクリストアドレス構造体を形成するのに使用される。
3つのリンクインデックスL1、L2及びL3が各エン
トリと共に含まれ、各リンクインデックスは、3つまで
の順序付けリストの1つにおけるエントリの位置を識別
する。又、各エントリは、依存性フラグ189も含む。
依存性フラグは、チャンネル間の依存性をマークするの
に使用される。依存性フラグF1は、対応するエントリ
のパケットがQ1、QIO又はQ0Vicチャンネルを
進行するパケットである場合にセットされる。依存性フ
ラグF2は、対応するエントリのパケットがQ0又はQ
0Vicチャンネルを進行するパケットである場合にセ
ットされる。依存性フラグは、パケットの処理順序を次
のように維持する上で助けとなる。
【0088】概念的に、受け取ったパケットは、Q2チ
ャンネル待ち行列、合成Q1/QIO/Q0Vicチャ
ンネル待ち行列、合成Q0/Q0Vicチャンネル待ち
行列、Q0Vicチャンネル待ち行列及びQIO待ち行
列を含む5つの順序付けされた待ち行列に分割される。
従って、パケットは、2つ以上の待ち行列に含まれる。
ヘッドポインタは、各待ち行列ごとに1つのポインタ1
87a−187eを含む。ヘッドポインタは、その待ち
行列に対応するバッファにおける次のパケットを識別す
るバッファ160a−160hのインデックスを与える
のに使用される。従って、ヘッドポインタ187は、Q
2ヘッドポインタ187a、Q1/QIO/Q0Vic
ヘッドポインタ187b、Q0/Q0Vicヘッドポイ
ンタ187c、Q0Vicヘッドポインタ187d及び
QIOヘッドポインタ187eを含む。パケットが入力
バッファに最初に書き込まれるときには、それが1つ以
上の順序付けされた待ち行列に入れられる。1つ以上の
順序付けされた待ち行列に入れられるときには、1つ以
上の依存性フラグ189がアサートされる。チャンネル
の形式及び依存性フラグが検査されて、チャンネル依存
性を満足するように出力すべきバッファの適当なエント
リが選択される。
【0089】8個の入力バッファ160a−160h各
々の各エントリは、マルチプレクサ182へ送られる。
マルチプレクサ182は、マネージャー180からの選
択信号に応答して入力バッファの1つからパケットの1
つを選択する。マネージャー180は、入力バッファ1
60a−160hの64個の考えられる読み取りポート
からのエントリを関連出力ポートの出力として選択す
る。マネージャー180は、全体的なシステム順序及び
チャンネル依存性が満足されるようにパケットを選択す
る。入力バッファ160a−160hの1つにパケット
が受け取られるときには、エントリのチャンネルフィー
ルドにチャンネル形式が書き込まれ、そしてそのエント
リの関連フラグがフラグフィールド189においてアサ
ートされる。上述したように、入力バッファの各エント
リごとに、3つのリンクインデックスがあり、その各々
は、3つの順序付けされた待ち行列の1つに対応する。
本発明の1つの実施形態では、パケットを3つの異なる
出力ポートにマルチキャスティングするために多数のリ
ンクインデックスが使用される。マルチキャスティング
されるべきパケットが入力バッファに記憶されるときに
は、それが2つ以上のリンクされたリストに入れられ、
リンクされたリストの各々は、異なる出力ポートに対応
する。その結果、異なる出力ポートに関連する出力マネ
ージャーは、各々、異なるリンクリストインデックスを
用いて同じ入力バッファエントリにアクセスすることが
できる。
【0090】上述したように、リンクインデックス値
は、バッファ160a−160hにおいて対応する形式
の次のパケットをアドレスするためのバッファインデッ
クス値である。従って、リンクインデックス値は、対応
する形式のその後のパケットがバッファに書き込まれる
まで書き込まれない。その後のパケットがバッファに書
き込まれるときには、その後のパケットのアドレスが手
前のパケットのリンクインデックスに書き込まれ、これ
により、そのチャンネル形式の次のパケットのインデッ
クスを与える。各エントリは、3つの考えられるリンク
インデックスフィールドを含むので、手前のエントリに
アドレスを書き込むのに加えて、2ビットフィールド
(図示せず)がアドレスと共に記憶され、順序付けリス
トを構成するために3つのリンクインデックスの適当な
1つをエントリで識別できるようにする。
【0091】マネージャー180は、出力ポートへ供給
するためにバッファ160a−160hのパケットの1
つを次のように選択する。上述したように、ヘッドポイ
ンタ187a−187eは、各待ち行列の最上部に対応
するバッファインデックスを記憶する。所与のチャンネ
ルに対するパケットを処理するときに、マネージャー
は、対応するヘッドポインタにより指示されたエントリ
を選択する。1つ以上のフラグ189がセットされ、そ
して高い優先順位のチャンネルに関連した待ち行列のパ
ケットが処理されていない場合には、パケットは、その
待ち行列内のより優先順位の高い全ての手前のパケット
が処理されるまで処理されない。例えば、出力マネージ
ャーがQ0形式のパケットを処理する場合に、Q1/Q
IO/Q0Vic及びQ0/Q0Vicヘッドポインタ
で指示されたエントリを検査する。パケットがQ0チャ
ンネルパケットであるが、Q1パケットの処理がまだ完
了していない場合には、エントリは処理されない。パケ
ットの処理は、チャンネルQ1又はQ0パケットが既に
処理されたことを指示する処理フラグ(図示せず)を各
フラグF1及びF2と共に与えることにより指示され
る。高い優先順位のチャンネルを有する待ち行列におけ
る全てのパケットの処理が行われると(処理フラグによ
り指示される)、そのエントリに関連したパケットは自
由に処理される。
【0092】あるエントリが処理のために選択される
と、マネージャーは、そのエントリが存在する待ち行列
に関連したヘッドポインタをバッファインデックスとし
て選択する。バッファインデックスはマルチプレクサ1
82へ送られ、そしてバッファエントリが出力ポートへ
送られる。リンクインデックスはヘッドポインタへ返送
され、そしてヘッドリストポインタがその待ち行列の次
のパケットのバッファインデックスで更新される。従っ
て、図15のスイッチ実施形態は、リンクリストデータ
構造体、順序付けされた待ち行列及びフラグを用いて、
出力ポートへパケットを与え、全体的なシステム順序が
維持されるようにする。更に、多数のリンクインデック
スを含むリンクリストデータ構造体は、マルチキャすと
パケット順序付けルールに固執しながらパケットをマル
チキャスティングするための簡単な機構を形成する。
【0093】従って、図15の実施形態は、フラグ及び
順序付けされた待ち行列を使用して、チャンネルの順序
が維持されるようにする。図16には、所定の順序依存
性に基づいて出力データを与えることのできるスイッチ
の第2の実施形態が示されている。図16の実施形態で
は、スイッチの各出力ポートに対してバッファ200が
設けられる。バッファ200は、入力パケット受信経路
201を経てバッファ160a−160h(図11)の
各々から入力を受け取るように接続され、入力バッファ
からのパケットは、パケットの行先に基づいて出力ポー
トの適当なバッファへ送られる。本発明の1つの実施形
態では、バッファは、コラップス(collapsing)FIFO
として実施されるが、当業者に知られた他のバッファア
ーキテクチャxを使用することもできる。
【0094】バッファ200は、スイッチから送出され
るべき種々のパケットを記憶するように示されている。
バッファ200は、ここでは、5つの異なるチャンネル
Q0、Q1、Q2、Q3及びQ4を経て送信されるパケ
ットを記憶する。チャンネルQ0−Q4は、上記のチャ
ンネルQ0、Q1、Q2、Q0Vic及びQIOと同様
ではない。むしろ、これらは、単にスイッチの出力動作
を示すためにのみ使用される。従って、パケットQ0−
Q4は、異なるチャンネルにおける一般的パケットを表
わし、チャンネルの依存性は、図16Aの流れ図におい
て矢印に基づいて定められる。図16Aにおいて、ある
チャンネルから別のチャンネルへ向けられた矢印は、第
1チャンネルのパケットが出力ポートへ送られず、一
方、第1チャンネルのパケットの前に受け取られた第2
チャンネルのパケットは、スイッチによる処理が保留中
であることを指示する。例えば、図16Aにおいて、チ
ャンネルQ0のパケットは、チャンネルQ3のパケット
の処理に依存するように示されており、従って、チャン
ネルQ0のパケットは、チャンネルQ3のパケットを
「プッシュ」したと言える。図16Aの流れ図に示され
た付加的な依存性は、チャンネルQ1のパケットがチャ
ンネルQ2及びQ3のパケットをプッシュしたことを指
示する。この場合も、図16Aの流れ図で表わされた依
存性は、既に述べたQ0、Q1、Q2、Q0Vic及び
QIOチャンネルの依存性を表わすものではないことに
注意されたい。以下に述べるように、Q0、Q1、Q
2、Q0Vic及びQIOチャンネルにおけるパケット
の依存性は複雑であり、従って、バッファ200の動作
を容易に説明するために、一般的パケット及び依存性が
与えられる。
【0095】上述したように、入力パケットは、スイッ
チの入力バッファ160a−160hの各々に正しい順
序で受け取られ、そしてそのパケットにより指示された
行先に基づいて、バッファ200のような出力バッファ
に正しい順序で供給される。各出力バッファの各パケッ
トエントリ、例えば、エントリ200aは、パケットの
送信及び受信ノードを指示するソース及び行先フィール
ドと、パケットが送信されるチャンネルを指示するチャ
ンネルフィールドと、一連のビット206a−206e
とを備えている。一連のビット206a−206eは、
ハイアラーキースイッチを経てパケットを供給する各チ
ャンネルごとに1ビットを含む。例えば、図16の実施
形態では、一連のビットは、チャンネルQ0、Q1、Q
2、Q3及びQ4の各々について1ビットを含む。
【0096】出力ポートに対して入力パケット受信経路
に接続された書き込み制御ロジック205は、受信パケ
ットのチャンネルに基づくと共に、図16Aの流れ依存
性図に示されたチャンネル間の依存性に基づいて一連の
ビットの各々の設定を制御する。又、以下に詳細に述べ
るように、書き込み制御ロジックは、静的又は動的に依
存性を確認することによりビットを更新することができ
る。依存性を静的に確認するときには、チャンネルに対
して定められた依存性が、バッファ内の他のパケットに
拘わりなく適用される。依存性を動的に確認するときに
は、チャンネルの依存性が、バッファ200内の他のパ
ケットのチャンネル及びアドレス行先を考慮して適用さ
れる。一連のビットの各々には、対応するサーチエンジ
ン208a−208eが接続される。各サーチエンジン
は、ビットの関連列をサーチして、列セットの対応ビッ
トを有するバッファ200のエントリを選択する。選択
されたエントリは、各列(又はチャンネル)ごとに、一
連の信号S4−S0により出力バッファマネージャー2
02へ指示される。チャンネル間の既知のデータ依存性
に関連してサーチエンジンの各々により受信された選択
信号を用いて、出力バッファマネージャーは、グローバ
ルポート出力に供給するために出力バッファ200から
のパケットの1つを選択する。
【0097】動作中に、入力パケット受信経路201を
経てパケットが受信されるときに、パケットのチャンネ
ルは、書き込み制御ロジック205により評価され、そ
して一連のビット206a−206eのうちの、そのチ
ャンネルに対応するビットがアサートされる。図16に
おいて、パケットの形式を指示するためにセットされた
ビットは、「丸内のX印」で示され、そしてこれはチャ
ンネル識別子フラグと称する。従って、図16では、パ
ケット1がQ3形式のパケットである。図15の実施形
態によれば、エントリのチャンネルを指示するビットを
アサートするのに加えて、そのチャンネルのパケットが
プッシュするところの各チャンネルに対してビットが付
加的にアサートされる。これらビットの各々は、依存性
フラグと称され、図16に「X」で示されている。それ
故、Q0チャンネルパケットであるパケット2の場合
に、Q3チャンネルパケットに関連したビットが付加的
にアサートされる。というのは、図16Aの流れ図に示
されるように、Q0パケットがQ3パケットをプッシュ
するからである。
【0098】パケットがバッファ200に記憶され、そ
してそれらの関連する一連のビット206a−206e
がアサートされるときには、ビットの各列に関連したサ
ーチエンジン208a−208eの各々が、ビットセッ
トを有するバッファ内の第1エントリを選択する。それ
故、サーチエンジン208aの選択値は、パケット2を
指し、サーチエンジン208bの選択値は、パケット3
を指し、等々となる。S0−S4信号は、マネージャー
202に送られる。マネージャー202は、サーチエン
ジンによる選択信号のアサートに応答するのに加えて、
システムに存在する依存性に応答して、パケットの1つ
を選択する。例えば、本発明の1つの実施形態によれ
ば、チャンネルQ0にあるパケット2のようなパケット
は、チャンネルQ0のサーチエンジン(208a)及び
チャンネルQ3のサーチエンジン(208d)の両方が
同じパケットを選択しない限り、スイッチから送出され
ない。従って、多数のフラグが所与のパケットに対して
セットされたときに、マネージャー202は、セットさ
れたフラグに対応するサーチエンジンの両方がその所与
のパケットを選択しない限り、出力に対してそのパケッ
トを選択しない。
【0099】本発明の別の実施形態によれば、サーチエ
ンジンが、その依存性フラグがセットされたためにエン
トリを選択した場合に、サーチエンジンは、依存性フラ
グをクリアしそしてバッファを下方に進んで、依存性フ
ラグ又は認識フラグがセットされた次のエントリを選択
することができる。このような構成では、サーチエンジ
ンが他のチャンネルによりストールされて処理を保留に
することがないので、パケットの処理が改善される。依
存性を識別するために多数のフラグをアサートする作用
は、パケットがスイッチを経て伝播するときにパケット
の全体的なシステム順序を維持する上で助けとなる。例
えば、図16において、Q0パケットとQ3パケットと
の間の関係は、Q0チャンネルパケットが実行の前に各
手前のQ3チャンネルパケットをプッシュすることであ
る。従って、Q3チャンネルパケットの後に受け取られ
たQ0チャンネルパケットは、Q3パケットの前に実行
されてはならない。パケット1は、パケット2のQ0チ
ャンネルパケットの前に受け取られるQ3チャンネルパ
ケットである。パケット2に対してビット206dをセ
ットすることにより、パケット2のQ0パケットがパケ
ット1のQ3パケットの前に出力ポートに発生されない
よう確保することができる。というのは、マネージャー
208は、S3及びS0の両方がパケット2への信号を
選択するまでQ0パケットを選択しないからである。S
3値は、パケット1が処理されるまでパケット2を指さ
ない。その結果、所与のチャンネルのパケットによりプ
ッシュされた各パケットごとにビットをアサートするこ
とにより、所与のチャンネルによりプッシュされたパケ
ットが処理されるまでチャンネルが効果的に阻止され
る。その結果、全体的なシステム順序が維持される。
【0100】上記のように、図16のバッファ制御ロジ
ックは、静的又は動的な依存性を確認するように動作さ
れる。静的な依存性とは、図16Aの流れ図で示された
ような依存性である。動的な依存性は、バッファ内の2
つのパケット間に静的な依存性が実際に存在するかどう
かを決定するためにバッファの内容を評価することによ
り確認される。静的な依存性は、メモリデータがSMP
においてコヒレンス性を失わないよう確保する順序付け
ルールを形成するのに使用される。しかしながら、デー
タのコヒレンス性は、パケットがメモリデータの同じブ
ロックをアクセスする場合にしか影響されない。それ
故、動的な依存性は、バッファに既にあるパケットの行
先アドレスを検査することによってバッファの内容を微
細な粒度で検査して、異なるチャンネルの2つのパケッ
ト間に依存性が実際に存在するかどうか決定する。
【0101】バッファ200内のパケット間の依存性を
動的に確認する1つの効果は、バッファ内のパケットを
処理するのに必要な時間を短縮することである。例え
ば、上記のパケット1及びパケット2の動作を使用する
と、Q0パケット2及びQ3パケット1が同じアドレス
にマップしない場合には、何ら問題なく、Q0パケット
をQ3パケットの前に処理することができる。手前のQ
3パケットの処理を待機する際に受ける遅延時間が排除
され、これにより、SMPシステムの全体的な性能が改
善される。例えば、図17は、依存性を動的に確認する
ことによるプロセスへのパケットの選択動作を示すフロ
ーチャートである。ステップ220において、パケット
がバッファ200に受け取られる。ステップ222にお
いて、パケットのチャンネルに対するビットが書き込み
制御ロジック205により一連のビット206において
セットされる。ステップ224において、バッファ20
0に記憶された手前のパケットが検査されて、パケット
がプッシュするところのチャンネルのパケットがメモリ
の同じブロックにあるかどうか決定される。それらがメ
モリの同じブロックにある場合には、ステップ226に
おいて、パケットがプッシュするところのチャンネルに
あり且つ同じメモリブロックに存在するパケットに対応
するビットがアサートされる。従って、パケット2に対
して図16の例を使用すると、パケット形式Q3に対す
るビットは、パケット1がパケット2と同じメモリブロ
ックをアクセスする場合だけアサートされる。従って、
依存性を動的に確認することにより、全体的なシステム
性能を向上しながらメモリコヒレンス性を維持すること
ができる。
【0102】図18には、全体的なシステム順序を維持
しながら、多数の入力ソースから受け取ったデータを多
数の出力ソースへ出力する方法の別の実施形態が示され
ている。図18の実施形態は、図16の場合と同様の要
素を含むように示されている。しかしながら、図18の
書き込み制御ロジック209は、パケットの依存性を異
なるやり方で分析することにより一連のビット206a
−206eの各々を更新する。図16の場合のように、
パケットが関連チャンネルのものであることを指示する
ために、一連のビットの1つが各パケットごとにセット
される。しかしながら、チャンネルがプッシュするとこ
ろのチャンネルの全てのパケットに対して付加的なビッ
トをセットするのではなく、そのチャンネルのパケット
をプッシュするところのチャンネルのパケットに対して
ビットがセットされる。
【0103】従って、図18の実施形態は、チャンネル
識別フラグをセットするのに加えて、そのパケットによ
りマスク又は阻止された全てのチャンネルに対して付加
的なビットがセットされる。例えば、図18の例におい
て、パケット1は、Q3チャンネルパケットである。Q
3チャンネルのパケットは、図18Aの依存性流れ図に
示すようにQ3パケットが実行されるまで、Q1及びQ
0パケットの実行を阻止する。従って、ビット206
d、206b及び206aがパケット1に対してセット
される。しかしながら、パケット2は、他のパケットの
実行を阻止しないQ0パケットである。その結果、ビッ
ト206bのみがパケット2に対してセットされる。従
って、図18のスイッチ実施形態は、依存性を静的に確
認することによりシステム順序を維持しながら出力ポー
トへデータを供給する別の方法を提供する。図18のバ
ッファ実施形態は、依存性を動的に確認するようには使
用できないことに注意されたい。というのは、そのよう
にするには、データがバッファ200に書き込まれる前
にデータのアドレスを知る必要があるからである。しか
しながら、ここに述べる静的及び動的な方法は、全て、
パケット間の依存性を満足するよう確保するために使用
できる。
【0104】従って、多数の入力ポートを経て多数のソ
ースからデータを同時に受け取りそして多数の出力ポー
トを経て多数の行先へデータを供給できる一方、データ
依存性を満足し、システム順序を維持し、そしてデータ
転送レートを最大にすることのできるスイッチの3つの
実施形態が説明された。1つの実施形態では、フラグを
記憶する多数の待ち行列の使用により順序付け依存性が
達成されそして依存性を識別するように待ち行列が選択
されるリンクリストバッファ機構が説明された。第2お
よび第3の実施形態では、スイッチの入力バッファから
データを正しい順序で受け取る出力バッファが、ある形
式のパケットを阻止するのに使用される一連のビットを
備えていて、データ依存性及びコヒレンス性制約を満足
するように確保する。全ての実施形態において、潜在的
な依存性の競合をマークするためにセットされるフラグ
を含む順序付け待ち行列の使用により、順序付け依存性
が追跡される。フラグの順序付けリストを用いて依存性
を識別することにより、バスの利用性を最大にしながら
順序を維持し且つコヒレンス性を確保するためにマネー
ジャーにより実行されるオペレーションの複雑さが簡単
化される。
【0105】キャッシュコヒレンスプロトコル 本発明の1つの実施形態におけるキャッシュコヒレンス
プロトコルは、書き込み無効化所有権をベースとするプ
ロトコルである。「書き込み無効化」とは、プロセッサ
がキャッシュラインを変更するときに、他のプロセッサ
キャッシュにおける効力のないコピーを無効化すること
を意味し、新たな値でそれらを更新するのではない。こ
のプロトコルは、システム内のメモリであるかプロセッ
サ又はIOPの1つであるかに拘わりなくキャッシュラ
インに対する識別可能な所有者が常に存在するので、
「所有権プロトコル」と称される。キャッシュラインの
所有者は、必要なときにキャッシュラインの最新の値を
供給する責任がある。プロセッサ/IOPは、キャッシ
ュラインを「独占的に」又は「共用して」所有すること
ができる。プロセッサがキャッシュラインの独占的所有
権を有する場合には、システムに通知せずにそれを更新
することができる。さもなくば、システムに通知し、そ
して他のプロセッサ/IOPキャッシュのコピーを潜在
的に無効化しなければならない。
【0106】キャッシュコヒレンスプロトコルの詳細な
説明に入る前に、ハイアラーキーネットワークに使用さ
れる全通信手順について最初に説明する。図7Aについ
て述べたように、大型のSMPシステム150は、スイ
ッチ155を経て互いに接続された多数のノードを含
む。各ノードにおける各プロセッサは、メモリのデータ
にアクセスするコマンドを発生する。これらのコマンド
は、ソースノード内で完全に処理することもできるし、
又はアドレス及び要求の形式に基づいてシステムの他の
ノードへ送信することもできる。アドレススペースは、
メモリスペース及びIOスペースに分けられる。プロセ
ッサ及びIOPは、専用キャッシュを使用して、メモリ
スペースアドレスのみに対するデータを記憶し、そして
IOスペースデータは、専用キャッシュには記憶されな
い。従って、キャッシュコヒレンスプロトコルは、メモ
リスペースコマンドのみに関連している。
【0107】キャッシュコヒレンスプロトコルの重要な
要素は、ロード及び記憶動作をシリアル化する解決策で
ある。キャッシュコヒレンスプロトコルは、各メモリア
ドレスXへの全てのロード及び記憶に順序を課さねばな
らない。この順序は、Xへの全ての「記憶」が順序付け
されるものであり、即ち、第1記憶、第2記憶、第3記
憶、等々とならねばならない。第i番目の記憶は、(I
−1)番目の記憶により決定されたようにキャッシュラ
インを更新する。更に、各ロードには最新の記憶が関連
され、そこからロードはキャッシュラインの値を得る。
この順序をここでは「ロード−記憶シリアル化順序」と
称する。ここに述べるプロトコルの特性は、アドレスX
に対するホームARBバスが、Xへの全てのロード及び
記憶に対する「シリアル化ポイント」であることであ
る。即ち、Xへの要求がXのホームARBバスに到着す
る順序は、対応するロード及び記憶がシリアル化される
順序である。大型のSMPシステムに対するほとんどの
公知のプロトコルは、この特性を有しておらず、従っ
て、効率が悪く、複雑である。
【0108】図2に示す小型のSMPノードシステムに
は、1つのARBバスがある。このバスは、小型SMP
における全てのメモリロード及び記憶に対するシリアル
化ポイントである。ARBバスに接続されたDTAG
は、小型SMPのプロトコルに必要とされる全ての状態
を捕獲する。大型のSMPシステムでは、ホームARB
バスのDIRがプロトコルに対するおおよその状態を捕
獲し、TTT及びDTAGは、より微細なレベルにおけ
る状態情報を捕獲する。 要求RがホームARBバスに
到着すると、DIR、DTAG及びTTT状態が検査さ
れ、他のプロセッサへの調査コマンド及び/又はソース
プロセッサへの応答コマンドを発生することができる。
更に、DIR、DTAG及びTTTの状態が要求Rの
「シリアル化」を反映するように自動的に更新される。
従って、要求アドレスがRのアドレスに等しく且つ要求
Rの後にホームARBに到着する要求Qは、ロード−記
憶シリアル化順序においてRの後に現れる。
【0109】その結果、ホームARBバスは、メモリア
ドレスへの全ての要求に対し「シリアル化ポイント」と
定義される。各メモリアドレスXに対し、対応する要求
(RdMod又はCTD)がホームARBバスに到着す
る順序で記憶が見掛け上実行される。アドレスXへのロ
ードは、ホームARBにおいて最後にシリアル化された
記憶Xに対応するXのバージョンを得る。 以下に述べ
るキャッシュコヒレンスプロトコルの前書きにおいて、
「システム」という用語は、プロセッサ及びIOPを除
く大型SMPの全ての要素を指す。プロセッサ及びシス
テムは、「コマンドパケット」又は単に「コマンド」を
送信することにより互いに対話する。コマンドは、要
求、調査及び応答の3つの形式に分類される。プロセッ
サによりシステムに発生されるコマンド及びシステムに
よりプロセッサに発生されるコマンドは、所与のプロセ
ッサのメモリシステムインターフェイスに基づく。SM
Pの動作を説明する目的上、デジタル・イクイップメン
ト・コーポレーションからのAlpha(登録商標)シ
ステムインターフェイスの定義に基づいて発生される要
求及びコマンドについて説明するが、他の形式のプロセ
ッサも使用できることを理解されたい。
【0110】要求は、ロード又は記憶動作を実行する結
果として、データのコピーを得なければならないときに
プロセッサにより発生されるコマンドである。又、要求
は、システムからのデータの断片に対して独占的な所有
権を得るのにも使用される。要求は、読み取りコマン
ド、読み取り/変更(RdMod)コマンド、ダーティ
への変更コマンド、ビクティムコマンド、及びエビクト
(Evict)コマンド(データのキャッシュラインが各キャ
ッシュから除去される場合)を含む。調査(Probe)コマ
ンドは、データ及び/又はキャッシュタグ状態更新を要
求する1つ以上のプロセッサへシステムにより発生され
るコマンドである。調査コマンドは、送信読み取り(For
warded Read)(FRd)コマンド、送信読み取り変更(F
orwarded Read Modify)(FRdMod)コマンド、及
び無効化コマンドを含む。プロセッサPがシステムへの
要求を発生するときには、システムは、1つ以上の調査
コマンドを他のプロセッサへ発生しなければならない。
Pがキャッシュラインのコピーを要求する(読み取り要
求で)場合には、システムは、所有者プロセッサ(もし
あれば)へ調査コマンドを送信する。Pがキャッシュラ
インの独占的所有権を要求する(CTD要求で)場合に
は、システムは、キャッシュラインのコピーをもつ1つ
以上のプロセッサへ無効化調査コマンドを送信する。P
がキャッシュラインのコピー及びキャッシュラインの独
占的所有権の両方を要求する(RdMod要求で)場合
には、システムは、データのキャッシュラインのダーテ
ィコピーを現在記憶しているプロセッサにFRdコマン
ドを送信する。FRdコマンドに応答して、キャッシュ
ラインのダーティコピーがシステムに返送される。又、
送信読み取り変更(FRdMod)コマンドも、キャッ
シュラインのダーティコピーを記憶しているプロセッサ
にシステムにより発生される。FRdModに応答し
て、ダーティキャッシュラインがシステムに返送され、
そしてキャッシュに記憶されたダーティコピーが無効化
される。キャッシュラインを別のプロセッサにより更新
すべきときには、キャッシュラインのコピーをキャッシ
ュに記憶しているプロセッサに、システムにより無効化
コマンドが発生される。
【0111】応答は、プロセッサにより要求されたデー
タ又は要求に対応する確認を搬送するシステムからプロ
セッサ/IOPへのコマンドである。読み取り及びRd
Modコマンドの場合に、応答は、各々要求されたデー
タを搬送するFill又はFillModコマンドであ
る。CTDコマンドの場合に、応答は、CTDの成功又
は失敗を指示するCTD成功又はCTD失敗コマンドで
ある。ビクティムコマンドの場合には、応答がビクティ
ム−リリースコマンドである。図19には、要求と要求
との間の関係、及び個々のプロセッサにおける対応キャ
ッシュラインの状態を説明するためのテーブルが示され
ている。又、図19は、キャッシュラインの要求及び状
態の各々に対して得られる調査形式のコマンドも示して
いる。カラム300及び300aは、プロセッサにより
発生される要求を示し、カラム305及び305aは、
システムの他のプロセッサにおけるキャッシュの状態を
示し、そしてカラム320及び320aは、システムに
より発生される調査コマンドを示す。
【0112】図19のテーブルは、プロセッサAと称す
るプロセッサがシステムに要求を発生することを仮定し
ている。プロセッサAのコマンドは、次いで、プロセッ
サBと称する1つ以上の他のプロセッサと相互作用す
る。プロセッサAによりアドレスされるキャッシュライ
ンが、DTAG及び/又はディレクトリ情報を用いて決
定されたプロセッサBのキャッシュに記憶される場合に
は、プロセッサBのキャッシュ状態が、プロセッサBへ
調査コマンドを発生する必要があるかどうか及びどんな
形式の調査コマンドを発生すべきかを決定する。以下、
コヒレンスプロトコル及び機構について詳細に述べる。
コマンドパケットがとる経路、各コマンド形式に対する
状態情報のソース、及びそれにより生じるアクションが
含まれる。全てのコマンドは、プロセッサ又はIOPか
ら発生され、IOPの発生プロセッサは「ソースプロセ
ッサ」と称する。要求に含まれるアドレスは、「要求ア
ドレス」と称する。アドレスの「ホームノード」は、そ
のアドレススペースが要求アドレスをマップするところ
のノードである。要求は、ソースプロセッサが要求アド
レスのホームノードである場合は「ローカル」と称し、
さもなくば、「グローバル」要求と称する。ホームノー
ドのARBバスは、「ホームARBバス」と称する。
「ホームディレクトリ」は、要求アドレスに対応するデ
ィレクトリである。従って、ホームディレクトリ及びメ
モリは、要求アドレスに対するホームARBバスに接続
される。
【0113】プロセッサ又はIOPから発せられるメモ
リ要求は、先ず、ホームARBバスにルート指定され
る。この要求は、それがローカルである場合にはローカ
ルスイッチを経てルート指定され、それがグローバルで
ある場合にはハイアラーキースイッチを経て送られる。
後者の場合には、ローカルスイッチ及びGPリンクを横
断してGPに達し、次いで、HSリンクを経てハイアラ
ーキースイッチへ至り、次いで、GP及びホームノード
のローカルスイッチを経てホームARBバスへ至る。グ
ローバル要求は、ソースノードのARBバスに最初に現
れず、むしろ、GPリンクを経てHSに直接ルート指定
されることに注意されたい。公知のプロトコルでは、グ
ローバル要求は、それが別のノードへ送出される前にソ
ースノードの状態をアクセスする。本発明は、グローバ
ル要求をHSへ直接発生することによりグローバル要求
の平均待ち時間を短縮する。
【0114】図20A−20Jは、多数の基本的なメモ
リトランザクションを例示するフローチャートである。ローカル読み取り :図20Aにおいて、ソースプロセッ
サ320からホームARBバスへ要求が送られる。ディ
レクトリ322は、どのプロセッサがメモリブロックを
所有するか決定する。ローカルメモリ323が所有者で
ある場合には、「短い記入」コマンドがホームARBバ
スからソースプロセッサ320へ発生される。
【0115】グローバル読み取り:図20Bにおいて、
ノード325のプロセッサ320が、「ホーム」がノー
ド326にあるメモリのキャッシュラインへ読み取りを
発生すると仮定する。(グローバル)読み取りコマンド
は、ライン327で示された経路を経てスイッチ324
を通り「ホーム」ARBバス及びディレクトリ321へ
ルート指定される。ノード326のメモリ330がキャ
ッシュラインの所有者である場合には、「短い記入応
答」を発生するノード326によりノード326からノ
ード325へデータが返送される。キャッシュラインが
別のプロセッサ/IOPにより現在所有されている場合
には、要求されたキャッシュラインを得るために異なる
ステップが取られる。図20Cを参照すれば、プロセッ
サ320が、「ホーム」がノード326にあるメモリの
キャッシュラインへ読み取りを発生する場合には、読み
取りは、再び、経路327を経てホームARBバス及び
ディレクトリ321へルート指定される。ディレクトリ
321のエントリは、上述したように、メモリの各キャ
ッシュラインに対し、所有者情報を含む14ビットの状
態情報を備えている。所有者情報は、この場合に、所有
者をノード328におけるプロセッサ342として識別
する。ノード328が要求されたキャッシュラインを所
有するというディレクトリの指示に応答して、2つの事
象が生じる。第1に、「ホーム」ノードであるノード3
26は、ライン329で示すように、所有者プロセッサ
342へ「送信読み取り」調査を発生する。同時に、ホ
ームノード326は、ライン331で示すように、プロ
セッサ320へ「記入マーカー」応答を送信する。「記
入マーカー」応答の役割は、以下で説明する。
【0116】「送信読み取り」に応答して、プロセッサ
342は、「記入」コマンドをプロセッサ320へ発生
し、「記入」コマンドは、当該キャッシュラインを含
む。「読み取り」要求に対するこの形式の応答は、デー
タ返送に対して一連の3つのコマンドを必要とするの
で、「長い記入」と称される。従って、「読み取り」ト
ランザクションは、メモリからの応答である「短い記
入」と、所有者プロセッサからの応答である「長い記
入」の2つの形式に分割することができる。ローカルRdMod :図20Dを参照すれば、ローカル
読み取り変更トランザクションは、(1)キャッシュラ
インの現在バージョンのコピーを得ている全てのプロセ
ッサに無効化調査が送られ、そして(2)FRMod及
びFillModsが、Frds及びFillsに代わ
って所有者に送られる点を除くと、ローカル読み取りト
ランザクションと同様に働くことが明らかである。 図
20D図において、ホームノードのディレクトリは、ロ
ーカルプロセッサ又はメモリがブロックを所有すること
を示す。ホームARBバスにおいて、ディレクトリ32
2は、ブロックの現在バージョンを得ている全ての外部
ノードを識別する。無効化コマンドは、HS324へ送
られ、全ての当該ノードはマルチキャストベクトルで識
別される。HSは、ベクトルで識別された全てのノード
へ無効化メッセージをマルチキャストする。無効化メッ
セージは、各ノードにおいてARBバスへ進み、そこ
で、DTAGは、それらを更にフィルタし、キャッシュ
ラインの現在バージョンを有すると識別されたプロセッ
サ又はIOPのみへ無効化調査を送信する。
【0117】グローバルRdMod:図20Eを参照す
れば、読み取り変更トランザクションは、図20A及び
20Bについて述べた読み取りトランザクションと同様
に作用することが明らかである。読み取り変更(RdM
od)コマンドは、先ず、プロセッサ320からキャッ
シュラインのホームARB及びホームディレクトリ32
1へルート指定される。ホームノードであるノード32
6のメモリがキャッシュラインを記憶する場合には、要
求されたデータを含む「短い記入変更」コマンドがノー
ド326からプロセッサ320へ送られる。ディレクト
リ321は、このトランザクションの結果として更新さ
れる。「読み取り変更」コマンドは、プロセッサ320
が、キャッシュラインの内容を変更できるようにキャッ
シュラインの独占的所有権を要求することを指示する。
それ故、「短い記入変更」コマンドに加えて、ノード3
26は、キャッシュラインの現在バージョンのコピーを
得ている他の全てのプロセッサに「無効化」コマンドを
発生する。DIRは、1つ以上のプロセッサがキャッシ
ュラインの現在バージョンのコピーを得ているノードを
識別する。DIRの存在ビットは、この情報を含む。D
TAGは、キャッシュラインのコピーを得ている全ての
ホームノードプロセッサを識別する。各々のDIR存在
ビットがセットされた全てのノードに「無効化」が送信
される。「無効化」を受信する各ノードにおいて、DT
AGをアクセスして、どのプロセッサがキャッシュライ
ンのコピーを現在記憶するかを決定する。「無効化」
は、これらのプロセッサのみに送られる。IOPタグ
は、IOPがコピーを有するかどうか決定するのに使用
され、もしそうであれば、IOPは「無効化」調査も受
け取る。
【0118】要求を発しているプロセッサ以外のプロセ
ッサが所有者である場合には、ホームノードは、「記入
変更マーカー」、「送信読み取り変更」及びゼロ以上の
「無効化」を1つのコマンドとして発生する。スイッチ
において、コマンドは、全ての行先ノードにマルチキャ
ストされる。各行先ノードにおいて、コマンドは、その
要素に分離され、各ノードのグローバルポートは、各ノ
ードにおいてどんなアクションをとるべきかを決定す
る。上記の例では、「送信読み取り変更」がプロセッサ
342により処理され、そして「記入変更マーカー」が
プロセッサ320により処理される。更に、DTAGエ
ントリに基づき、ホームノード、「記入変更マーカー」
を受け取るノード、及び「送信変更」を受け取るノード
において「無効化」が実行される。「送信読み取り変
更」に応答して、ダーティデータが「長い記入変更」コ
マンドを経てプロセッサ342からプロセッサ320へ
送られる。
【0119】従って、「読み取り変更」コマンドは、2
つ又は3つのノード接続即ち「ホップ」を実行すること
ができる。本発明の1つの実施形態では、読み取り型コ
マンド(「読み取り」及び「読み取り変更」)のみが3
つのホップを生じ、但し、第3のホップは「記入」型コ
マンド(「記入」又は「記入変更」)である。しかしな
がら、本発明は、以下に述べる追加コマンドを仮想チャ
ンネル待ち行列に適当に割り当てることにより3つ以上
のホップを必要とする他のトランザクションも含むよう
に容易に変更できる。CTD :図20G及び20Hには、クリーン−ダーティ
(CTD)及び無効化−ダーティ(ITD)の基本的な
流れが示されている。図20Gでは、クリーン−ダーテ
ィは、ホームノードにおいてプロセッサ320からディ
レクトリ321へ発生される。プロセッサ320が更新
を希望するところのクリーンキャッシュラインが現在の
ものであるか効力を失ったものであるかに基づいて、
「確認」コマンド(ACK)又は「非確認」(NAC
K)コマンドのいずれかがプロセッサ320へ返送され
る。対応的に、CTDは成功又は失敗と言える。更に、
CTDが成功の場合にデータのキャッシュラインのコピ
ーをもつものとしてディレクトリ321の存在ビットに
より指示された全てのノードに「無効化」が送られる。
【0120】図20Hに示すように、ITDコマンド
は、CTDと実質的に同様に働く。しかしながら、IT
Dは決して失敗とならない。ACKが常にプロセッサ3
20に送られ、そしてデータのキャッシュラインのコピ
ーを記憶するシステムの他のノードには「無効化」が送
られる。ローカル及びグローバル書き込みビクティム :上記のよ
うに、書き込みビクティムコマンドは、ダーティデータ
をプロセッサのキャッシュから適当なホームメモリへ返
送する。図20I及び20Jを参照すれば、書き込みビ
クティムの流れは、「ホーム」メモリが書き込みビクテ
ィムを発生するプロセッサと同じノードであるかどうか
に基づいて若干異なることが明らかである。図20Iに
示すように、「ホーム」ノードがプロセッサのノードで
ある場合には、プロセッサ320が書き込みビクティム
を発生し、そしてデータは、同じノードのメモリへ直接
送られる。
【0121】しかしながら、図20Jに示すように、ビ
クティムデータがプロセッサとは異なるホームにある場
合には、データが2つの段階で転送される。第1に、ビ
クティムキャッシュラインがプロセッサ320のキャッ
シュ(又はビクティムバッファ)から送出され、そして
プロセッサノードのグローバルポートにおけるビクティ
ムキャッシュ(図6の要素124)に記憶される。ビク
ティムキャッシュは、「ビクティムリリース」信号でプ
ロセッサに応答し、プロセッサがそのビクティムバッフ
ァエントリを再使用できることを指示する。次いで、ス
イッチに使用可能な帯域巾が存在するときには、ビクテ
ィムデータは、「書き込みビクティム」コマンドにより
ビクティムキャッシュからホームプロセッサのメモリへ
送られる。
【0122】ソースプロセッサPによりホームメモリに
送られたビクティムデータは、それがメモリに到達する
ときまでに効力を失うことがあることに注意されたい。
このような場合に、ビクティムは、「失敗」と言われ、
ホームメモリは更新されない。このようなケースは、P
がキャッシュラインの所有権を獲得するときと、Pのビ
クティムがホームディレクトリに到着するときとの間の
インターバルに別のプロセッサがキャッシュラインの所
有権を獲得したときに生じる。このような場合には、P
のビクティムがホームARBに到達する前に、キャッシ
ュラインに対する「無効化」又は「FrdMod」調査
をプロセッサPに送信しなければならない。ビクティム
データをメモリに書き込まねばならないかどうか決定す
るために、「書き込みビクティム」コマンドがホームA
RBバスに現れるときに、要求されたアドレスに対する
ディレクトリエントリがルックアップされる。ソースプ
ロセッサが依然としてキャッシュラインの所有者である
ことをディレクトリが指示する場合には、ビクティムが
成功となり、メモリを更新する。さもなくば、失敗とな
り、メモリは更新しない。いずれにせよ、ディレクトリ
321においてビクティムに対して判断がなされると、
「ビクティムACK」コマンドがノード325のグロー
バルポートに返送され、ビクティムキャッシュは関連エ
ントリをクリアすることができる。
【0123】この設計の1つの実施形態では、DTAG
を使用して、「書き込みビクティム」コマンドがローカ
ルである場合に「書き込みビクティム」コマンドの成功
又は失敗を判断する。この特定の例(ローカル「書き込
みビクティム」要求の例)では、DTAG及びDIRの
両方が「書き込みビクティム」要求の成功又は失敗を決
定するに必要な情報を与えることができる。DTAG
は、単にDTAGをベースとする機構が小型のSMPノ
ードハードウェアに対して既に設けられているという理
由でDIRに代わって使用される。キャッシュコヒレン
スプロトコルの上記説明では、最も一般的な動作及びコ
マンド形式について述べた。これら機構は、以下に詳細
に説明する。上記のように、本発明の1つの実施形態で
は、2つ以上の関連メッセージパケットを効率化のため
に1つに結合することができる。結合されたパケット
は、次いで、HS又はノードのARBバスにおいてその
成分に分割することができる。例えば、HSへのFrd
Modメッセージは、所有者プロセッサをもつノードへ
のFrdModメッセージと、キャッシュラインのコピ
ーをもつノードへの「無効化」メッセージと、ソースノ
ードへのFillMarkerModメッセージとに分
割される。所有者プロセッサノードへのFrdMod
は、ノードのARBバスにおいて、所有者プロセッサへ
のFrdModメッセージと、ノードの他のプロセッサ
へのゼロ以上の「無効化」メッセージとに更に分割され
る。
【0124】ビクティムコヒレンス性を維持するための
遅延書き込みバッファ動作:図20I及び20Jについ
て上述したように、ホームメモリに送られるビクティム
データは、「書き込みビクティム」がホームARBに到
達する前に受け取られるキャッシュラインに対し「無効
化」又はFrdMod調査が介在する結果としてそれが
到着するときまでに効力を失うことがある。ビクティム
データをメモリに書き込まねばならないかどうかを決定
する1つの方法は、各書き込みビクティムコマンドに対
してディレクトリエントリをルックアップすることであ
る。ビクティム書き込みコマンドを発生するプロセッサ
がダーティ所有者であることをディレクトリが指示する
場合には、ビクティムを進めることが許されねばならな
い。さもなくば、失敗となってしまう。この方法が望ま
しい理由は、プロセッサとシリアル化ポイントとの間の
ビクティム書き込みコマンドを、シリアル化ポイントと
プロセッサとの間の調査コマンドと一致させるための複
雑な比較論理構造体の必要性が回避されるからである。
【0125】この解決策は、データコヒレンス性の維持
を簡単化するが、メモリ帯域巾が減少するという形態の
性能欠陥を生じさせる。この構成によれば、システムが
ビクティム書き込みコマンドを実行するたびに、先ず、
ディレクトリ状態をアクセスし、次いで、その状態を評
価し、そして最終的に、その状態に基づいて、ビクティ
ムデータのDRAM書き込みを実行しなければならな
い。メモリ及びディレクトリは原子的にアクセスされる
ので、公知の設計方法に基づいてシステムがシステムが
設計された場合に、全ビクティム書き込みサイクルは、
ディレクトリルックアップ時間と、状態評価時間と、D
RAM書き込み時間との和に等しくなる。このようなシ
ステムは、全ビクティムサイクルがDRAM書き込みの
みで構成されるシステムに対して甚だしい性能上の不利
益をこうむる。
【0126】本発明の1つの実施形態は、メモリの各バ
ンクに遅延書き込みバッファを設けることにより、この
メモリバンク利用低下問題を克服する。ビクティム書き
込みがメモリシステムへ発生されるたびに、メモリシス
テムは、次の機能を並列に実行することにより応答す
る。即ち、ビクティム書き込みデータをターゲットメモ
リバンクの遅延書き込みバッファに記憶しそしてそのブ
ロックを「非書き込み可能」又は「無効」と表示し、ビ
クティム書き込みに関連したディレクトリ状態をアクセ
スし、そして現在ビクティム書き込みに代わって、「書
きこみ可能」又は「有効」と表示された既にバッファさ
れたビクティム書き込みのDRAM書き込みを実行す
る。ディレクトリアクセスが完了したときに、ビクティ
ム書き込みに関連したディレクトリ状態が、ビクティム
書き込みが成功したことを示す場合には、ビクティムが
存在する遅延書き込みバッファが「書き込み可能」又は
「有効」状態へと移行する。遅延書き込みバッファにお
けるデータブロックの「書き込み可能」又は「有効」状
態は、バッファのデータが、DRAMメモリに記憶され
たバージョンよりも最新のキャッシュラインのバージョ
ンであることを指示する。バッファが「書き込み可能」
又は「有効」と表示された場合には、そのデータが、メ
モリシステムへのビクティム書き込みのその後に発生に
よりDRAMへ書き込まれる。
【0127】既に発生されたビクティム書き込みのDR
AM書き込みと並列にディレクトリルックアップを実行
することにより、この実施形態は、全ビクティムサイク
ル時間を単一のDRAM書き込み時間に減少する。この
実施形態は、「書き込み可能」な又は「有効」なデータ
ブロックを多数のサイクルにわたり遅延書き込みバッフ
ァに保持し、そのサイクル中にバッファされたブロック
へのその後の参照をメモリへ発生することができるの
で、遅延書き込みバッファは、連想アドレスレジスタを
備えている。ビクティム書き込みブロックのアドレス
は、その関連データが遅延書き込みバッファに記憶され
るのと同時に連想アドレスレジスタに記憶される。その
後の参照がメモリシステムへ発生されるときには、メモ
リシステムは、アドレスレジスタに対するアドレス一致
により遅延書き込みバッファにおけるアドレスブロック
を識別する。これは、メモリシステムが、DRAMメモ
リの効力を失ったデータに代わってバッファからの最新
のデータで遅延書き込みバッファのブロックへの全ての
参照にサービスすることを意味する。
【0128】ビクティムデータの遅延書き込みバッファ
動作を与える上記技術は、DTAG状態を直接含まずに
DTAG状態を使用してデータブロックの有効性を決定
するスヌーピーバスをベースとするシステムにも使用で
きる。図21を参照すれば、遅延書き込み動作を与える
メモリ制御システムの1つの実施形態は、ディレクトリ
140からライン140aを経てOwner Matc
h信号を受け取るように接続されたメモリコントローラ
332を含むように示されている。更に、メモリコント
ローラ332は、ディレクトリに入力されるコマンドを
追跡するためにQS ARB11(ディレクトリ140
にも信号供給する)からも入力を受け取る。メモリコン
トローラ332は、遅延書き込みバッファ336を含
む。遅延書き込みバッファ336の各エントリは、デー
タ部分336aと、フラグ部分336bと、アドレス部
分336cとを含む。本発明の1つの実施形態におい
て、設計上の複雑さを最小限にするために、遅延書き込
みバッファは、1つのアドレス、データ及びフラグエン
トリのみを保持するが、本発明は、このような構成に限
定されるものではない。
【0129】遅延書き込みバッファは、次のように動作
する。動作中に、コマンド、アドレス及びデータがAR
BUS130を経て受け取られると、それらはディ
レクトリ140及びメモリコントローラ332へ送られ
る。メモリコントローラ332は、コマンド、アドレス
及びデータを書き込みバッファ336に1トランザクシ
ョン周期中(ここでは18クロックサイクル中)記憶す
る。トランザクション周期中に、ディレクトリ140が
アクセスされ、そしてアクセスの結果がOWNER
ATCHライン140aにアサートされる。OWNER
MATCHラインは、メモリの更新を求めるプロセッ
サのプロセッサIDが実際にデータのキャッシュライン
の所有者であることをディレクトリエントリが指示する
場合にアサートされる。OWNER MATCH信号
は、遅延書き込みバッファエントリ336のフラグ33
6bをセットするのに使用される。次に続くトランザク
ション周期中に、メモリバスが使用できそしてフラグ3
36bがアサートされた場合には、メモリ334に記憶
データが書き込まれる。本発明の1つの実施形態では、
書き込み動作のみがバッファされ、到来する読み取り動
作は、遅延なくメモリバスをアクセスすることが許され
る。遅延書きこみバッファに記憶されたビクティムデー
タへのその後の読み取り動作は、遅延書きこみバッファ
からサービスされる。
【0130】図22は、遅延書き込み動作のタイミング
図である。時間T0に、読み取り0動作がARB BU
Sに受け取られる。この読み取り動作は、DRAM33
4をアクセスするためにメモリへ直ちに伝播される。時
間T1に、書き込み1動作がARB BUSに受け取ら
れる。このT1サイクル中に、ディレクトリ140がア
クセスされ、そしてT1サイクルの終わりに、書き込み
1アドレスの一致を示すOWNER MATCH信号が
アサートされる。その結果、遅延書き込みバッファエン
トリのフラグ336bがセットされる。時間T2に、読
み取り2動作が受け取られ、書き込み1動作の前にメモ
リへ送られる。時間T3の間に、書き込み1動作に対応
するフラグがアサートされた場合に、次の書き込み3動
作が遅延書き込みバッファに受け取られると、書き込み
1動作がDRAM3により処理するためにメモリに送ら
れる。
【0131】ローカルメモリの読み取りについては、遅
延書き込みバッファのフラグビットをセットするのにD
TAGも使用できることに注意されたい。ローカルメモ
リからのキャッシュラインの1つをローカルノードにお
けるプロセッサのキャッシュの1つに記憶することがで
きる。プロセッサの1つがキャッシュラインをビクティ
ム化しそしてキャッシュラインが遅延書き込みバッファ
に書き込まれたときに、そのキャッシュラインのDTA
Gエントリを検査して、キャッシュラインがプロセッサ
の1つに常駐したかどうか決定することができる。キャ
ッシュラインがプロセッサの1つに常駐した場合には、
DTAGエントリの有効ビットを検査して、プロセッサ
がビクティム化するコピーが有効であることを確保す
る。DTAGにヒットがありそしてキャッシュラインが
有効であった場合には、DTAGが遅延書き込みバッフ
ァのフラグをセットし、キャッシュラインをローカルメ
モリに書き込みさせる。これは、簡単なスヌーピーバス
をベースとする(即ちディレクトリのない)システムが
この同じ簡単なアルゴリズムを適用できるようにする。
【0132】従って、図21のメモリ制御ロジックは、
読み取り動作を読み取りサイクルにおいて直ちに実行す
ることができそして書き込み動作を各書き込みサイクル
に実行できるようにする(たとえ遅延書き込みであって
も)。その結果、ディレクトリのアクセスにより遅延を
こうむることなくデータの定常流がDRAMに送られ、
そしてコヒレンス性を維持しながら性能が高められる。
遅延書き込みバッファ技術は、ビクティム書き込み動作
に関連して説明したが、メモリ性能を改善するためにコ
ヒレンス状態が集中され且つ一定保持されるようないか
なるシステムにも使用することができる。
【0133】仮想チャンネル:従って、キャッシュコヒ
レンスプロトコルを実施するために、プロセッサと、デ
ィレクトリと、メモリと、DTAGとの間に多数のメモ
リ参照が送信されることが明らかである。更に、各メモ
リ参照は、多数のトランザクション即ちホップをノード
間に備え、メモリ参照のためのメッセージは、参照全体
が完了する前に転送される。メッセージ間の依存性が参
照を不定に阻止する場合には、マルチプロセッサシステ
ムが停滞(デッドロック)状態となる。 上記で簡単に
述べたように、本発明の1つの実施形態は、仮想チャン
ネル流れ制御を使用することにより、ノード間のトラフ
ィックをマネージしそして停滞を生じることなくデータ
コヒレンス性を維持する。仮想チャンネルは、相互接続
ネットワークに停滞のないルートを形成するために最初
に導入された。本発明の1つの実施形態によれば、仮想
チャンネルは、更に、共用メモリコンピュータシステム
のためのキャッシュコヒレンスプロトコルにおけるリソ
ース停滞を防止するのにも使用できる。
【0134】公知の関連するキャッシュコヒレンスプロ
トコルでは、2つの形式の解決策が使用されている。少
数のプロセッサと少数の同時保留中要求とを有するシス
テムの場合には、実行中の任意の点に生じ得る考えられ
る最大数の応答を受け入れるに足る大きさの待ち行列及
びバッファが設けられている。充分な待ち行列及びバッ
ファスペースを設けることにより、メッセージが進行の
ために別のメッセージに決して影響されないよう保証し
ている。多数の保留中要求を伴う大型のシステムでは、
考えられる最大数の応答を受け入れるに足る大きさのバ
ッファ及び待ち行列を設けることは実際的ではない。従
って、停滞検出及び分析機構に接続された2チャンネル
相互接続を使用して問題が解決される。第1に、相互接
続部(プロセッサ及びメモリのようなシステム要素間に
メッセージを移動するのに使用される論理的経路)は、
2つのチャンネル、即ち要求チャンネル(又は下位チャ
ンネル)と、応答チャンネル(又は上位チャンネル)と
を使用する。これらのチャンネルは、一般に、物理的な
ものであり、即ち個別のバッファ及び待ち行列を使用す
る。第2に、潜在的な停滞を検出するために発見的手法
が一般的に実施される。例えば、コントローラは、待ち
行列がいっぱいでありそして待ち行列からある時間中に
メッセージが出力されないときに潜在的な停滞を通知す
る。第3に、選択されたメッセージが否定的に確認され
て、リソースを解放し、他のメッセージを進行できるよ
うにする停滞分析機構が実施される。否定的な確認メッ
セージは、それに対応するコマンドをリタイアさせる。
【0135】上記の大型システムの解決策は、公平さ/
欠乏の問題及び性能不利益の問題を含む2つの主たる問
題を有している。あるメッセージが否定的に確認される
ので、あるコマンドが長時間完了しない(潜在的に不定
である)ことが考えられる。コマンドが所与の時間周期
内に完了するよう保証されない場合には、そのコマンド
を発生するリソースは、システムデータへの公平なアク
セスを得ることができない。更に、リソースがシステム
データへの公平なアクセスを得ることができないため
に、データに対して欠乏状態となり、潜在的にシステム
の停滞を生じさせる。更に、あるメッセージが否定的に
確認され、従って、それらの行先に到達しないので、無
効化メッセージのようなプロトコルメッセージは、それ
らが行先に首尾良く到達することを指示するための確認
を発生しなければならない。更に、コントローラは、対
応するコマンドが完了したとみなし得る前に全ての確認
が受け取られるまで待機しなければならない。この非決
定論的結果は、キャッシュコヒレンスプロトコルの全性
能を低減するようなメッセージオーバーヘッド及び余計
な待ち時間を生じさせる。
【0136】本発明の1つの実施形態によれば、停滞回
避に対する系統的及び決定論的解決策を採用したキャッ
シュコヒレンスプロトコルが使用される。潜在的な停滞
を検出しそして矯正動作を行うのではなく、停滞が設計
により排除される。従って、停滞検出及び分析機構の必
要性がなくなる。第2に、メッセージは、停滞回避のた
めの否定的確認ではなくなるので、「無効化」のような
プロトコルメッセージに対する確認が不要となり、それ
故、帯域巾及び待ち時間が改善される。仮想チャンネル
の使用を説明する目的で、幾つかの有用な用語について
最初に説明する。 依存性:メッセージM2が進行しな
い限りメッセージM1が進行できない場合に、メッセー
ジM1はメッセージM2に「依存」すると定義する。更
に、依存性は、移行的であるとも定義する。本発明のキ
ャッシュコヒレンスプロトコルを実施する場合に、リソ
ース依存性及び流れ依存性の少なくとも2種類の依存性
がある。M2が待ち行列スロットのようなリソースを解
放するまでM1が進行できない場合に、M1はM2に
「リソース依存」すると定義する。M2が進行するまで
M1が進行しないことをキャッシュコヒレンスプロトコ
ルが必要とする場合には、M1はM2に「流れ依存」す
ると定義する。例えば、キャッシュコヒレンスプロトコ
ルは、ディレクトリがある状態に達するまでM1が阻止
状態であり、そしてディレクトリの状態を所望の値にセ
ットするのがM2であることを要求する。従って、M1
からM2へのリソース又は流れ依存性のチェーンが存在
する場合に、M1はM2に依存すると定義する。
【0137】依存性サイクル:M1の進行がM2の進行
に依存し;M2の進行がM3の進行に依存し;Mk−1
の進行がMkの進行に依存し;そして最終的に、Mkの
進行がM1の進行に依存するときに、1組のメッセージ
M1、MK(≧2)の間に「依存性サイクル」が存在す
ると定義する。メッセージのあるサブセットが依存性サ
イクルを形成するときにメッセージのシステムは停滞状
態になる。M1はMkに依存し、Mkは次いでM1に依
存するので、サイクル内のどのメッセージも進行するこ
とができない。ここに開示する方法及び装置は、仮想チ
ャンネルを使用して、キャッシュコヒレンスプロトコル
における停滞を決定論的に回避する。キャッシュコヒレ
ンスプロトコルの設計において必要とされるハードウェ
ア機構及び従うべき1組のルールについて説明する。
【0138】1つの実施形態において、キャッシュコヒ
レンスプロトコルは、全てのメモリ動作がせいぜい3段
階で完了すると定める。各段階において、システムの要
素間に1つ以上のメッセージが転送される。それ故、各
段階は、「ホップ」と称される。ホップは、0、1及び
2と番号付けされる。ホップ0では、プロセッサ又はI
Oプロセッサからの要求がホームディレクトリへ送られ
る。ホップ1では、ホームディレクトリにより発生され
たメッセージが1つ以上のプロセッサ又はIOプロセッ
サへ送られる。ホップ2では、メッセージが所有者プロ
セッサからソースプロセッサへ送られる。これらホップ
は、図23に示されている。キャッシュコヒレンスプロ
トコルの顕著な特性は、全ての動作が所定数のホップ内
に完了することである。ここに示す実施形態では、所定
数が3であるが、本発明は、選択される数が比較的小さ
く且つ一貫したものである限り、特定のホップ数に限定
されるものではない。この特性は、停滞を検出しそして
停滞を解消するためのメッセージを失敗して再トライす
る機構を伴わずに、全てのメッセージをそれらの行先に
ルート指定できることを保証するための鍵である。
【0139】上記のように、ここに示す実施形態では、
最大ホップ数が3である。従って、システムは、各々Q
0、Q1及びQ2と示された3つのチャンネルを備えて
いる。これらのチャンネルは、システム相互接続部を通
る論理的に独立したデータ経路である。これらのチャン
ネルは、物理的なものでもよいし、仮想のもの(或いは
一部分物理的で且つ一部分仮想)でもよい。物理的なも
のであるときには、各チャンネルは、システム全体にわ
たり個別の待ち行列及びバッファリソースを有する。仮
想のものであるときには、チャンネルは、待ち行列及び
バッファリソースを共用し、以下に述べる制約及びルー
ルを受ける。3つのチャンネルは、ハイアラーキーを構
成し、Q0は最下位であり、Q1はその次であり、そし
てQ2は最上位のチャンネルである。システムにおける
停滞回避のための重要なルールは、チャンネルQiのメ
ッセージが、Qiより下位のチャンネルのメッセージに
決して依存しないことである。
【0140】更に、本発明の1つの実施形態において、
IOシステムからの応答メッセージと、IOシステムか
らのメモリスペースコマンドとの間の流れ依存性サイク
ルを排除するためにQIOチャンネルが追加される。最
後に、本発明の1つの実施形態では、ビクティムメッセ
ージと、ビクティムメッセージが発生されるがビクティ
ムメッセージが保留中である間に発生されるその後の依
存性メッセージとに対して、Q0Vicチャンネルが使
用される。図20a−20hに関連して上述したよう
に、スイッチへ発生される所与のコマンドメッセージ
は、一連の多数の個別トランザクションを発生する。本
発明の1つの実施形態において、所与のコマンドパケッ
トに対する各個別のトランザクションは、チャンネルに
割り当てられる。チャンネルは、本質的に、所与のコマ
ンドパケットの完了段階及び依存性を定義する順序付け
された構造体を形成する。
【0141】例えば、図23は、図20A−20Jにつ
いて述べた動作の個別トランザクションにチャンネルを
割り当てるところを示すフローチャートである。個別ト
ランザクションは、次の用語で識別される。即ち、参照
により生じる一連のトランザクションにおける第1トラ
ンザクションは、Q0又はQ0Vicトランザクション
と称し、一連のトランザクションにおける第2トランザ
クションは、Q1トランザクションと称し、そして一連
のトランザクションにおける第3トランザクションは、
Q2トランザクションと称する。Q0又はQ0Vicチ
ャンネルは、まだディレクトリを訪れていないプロセッ
サ及びIOPからの初期コマンドを搬送する。従って、
Q0/Q0Vicパケットの行先は、常に、ディレクト
リである。Q0Vicチャンネルは、「書き込みビクテ
ィム」コマンドに対して特に指定され、一方、Q0チャ
ンネルは、プロセッサ又はIOPにより開始された他の
全ての形式のコマンドを搬送する。
【0142】ステップ380で発生されるコマンドは、
データを得るか又は状態を更新しようと求める。状態
は、常に、データのアドレスに対応するホームディレク
トリで得ることができる。ステップ382において、ホ
ームディレクトリがアクセスされ、そして使用可能なキ
ャッシュラインがホームメモリにより所有される(ディ
レクトリに対して)か、別のプロセッサにより所有され
るかが決定される。いずれの場合にも、応答はQ1チャ
ンネルを経て発生される。ステップ382において、状
態又はデータが第2ノードに得られると決定された場合
には、ステップ384において、Q1チャンネルの応答
が第1ノードへ返送される。Q1形式のトランザクショ
ンは、ShortFill、ShortFillMo
d、VicAck、CTD−ACK/NACK当を含
む。
【0143】ステップ382において、ホームノードが
データを所有せず、データがダーティであって別のプロ
セッサにより所有されると決定された場合には、ステッ
プ386において、「送信読み取り」又は「送信読み取
り変更」のQ1形式のトランザクションがQ1チャンネ
ルを経てリモートノードへ発生される。ダーティへと状
態変化したデータを他のノードが共用することを指示す
るホームノードの状態チェックに応答するか、又は「読
み取り変更」に応答する場合には、ステップ388にお
いて、無効化Q1形式トランザクションがシステムの他
の当該ノードに送られる。従って、Q1チャンネルは、
第2の「ホップ」におけるパケットを搬送するためのも
のであり、第1のホップはディレクトリに対するもので
ある。第2の「ホップ」の行先は、常にプロセッサであ
り、プロセッサは、元のコマンドを開始したノードにあ
るか、又はシステム内の別のリモートノードにある。
【0144】Q2チャンネルは、「長い記入」又は「長
い記入変更」トランザクションのいずれかを搬送する。
Q2チャンネルは、第3の「ホップ」による第3ノード
からのデータを、元のコマンドを開始したノードへ返送
する。Q0/Q0Vic、Q1及びQ2形式のコマンド
へのコマンドの割り当ては、SMPシステムにおいて停
滞のないメッセージ送信を確保するために次のように使
用できる。図23のフローチャートは、4つの仮想チャ
ンネル間の対話を示すが、本発明の1つの実施形態で
は、キャッシュコヒレンス性を維持する目的で5つの仮
想チャンネルを使用することができる。その追加チャン
ネルは、QIOチャンネルである。一般に、QIOチャ
ンネルは、制御状態レジスタ(CSR)アクセスを含む
IOアドレススペースへ全ての読み取り及び書き込みを
搬送する。
【0145】以下のテーブルIIは、チャンネル経路へ
のコマンドマッピングを例示するリストである。 テーブルII QIO CPUへの全IOスペース要求 RdByteIO, RdWordIO, WrByteIO, WrWordIO Q0 CPU又はIOPからの全メモリ Rd, RdMod, Fetch, CTD, スペース要求 ITD, Vic, RdVic, RdModVic Q0Vic データを転送するCPU又はIO WrVic, Full Cache Line Pからの全メモリスペース要求 Write, QV Rd, QV RdMod, QV Fetch Q1 全送信コマンド FRd, FrdMod, Ffetch 全シャドーコマンド SFRd, SFRdMod, SFEtch, Sinval, Ssnap 短い記入 SFill, SfillMod マーカー記入の全性質 FM, FMMod, Pseudo-FM, Pseudo-DMMod, FrdMod with FM その他 CTD-ACK, CTD-NACK, ITD-ACK, Vic-ACK, VicRel IOスペース応答 IOFillMarker, IOWriteACK 関連Consig Invi-Ack, LoopComSig Q2 長い記入 Fill, FillMod IOスペース記入 IOFill スイッチをベースとするシステムにおける仮想チャンネ
ルの1つの実施形態は、各チャンネルに対して物理的に
個別の待ち行列、バッファ又は経路を使用することを含
む。或いは又、待ち行列、バッファ又はデータ経路は、
チャンネル間で共用されてもよく、従って、真の「仮
想」であってもよい。本発明の1つの実施形態では、こ
れら技術の組み合わせを使用して、ハードウェアの最適
な使用がなされる。
【0146】図24には、2つ以上の仮想チャンネル間
で単一バッファをいかに共用するかが示されている。バ
ッファ400は、多数の「スロット」を含むように示さ
れている。各スロットは、1つのチャンネルのみにより
専用に使用される。例えば、スロット402は、Q2型
コマンドに専用の多数のバッファエントリを含み、スロ
ット404は、Q1型コマンドに専用の多数のバッファ
エントリを含み、等々となる。残りのスロット410
は、いずれのチャンネルについても、メッセージにより
使用することができ、それ故、「共用」又は「一般的」
スロットと称される。各チャンネルについてビジー信号
が与えられる。ビジー信号は、バッファがそれ以上のメ
ッセージを記憶できず、それ故、そのバッファに何も送
信してはならないことを指示する。
【0147】所与のチャンネルに対する所与のリソース
においてビジー信号がアサートされるときと、そのリソ
ースにコマンドを発生するデバイスがビジー信号に応答
して発生を停止するときとの間には待ち時間周期があ
る。この待ち時間の間に、1つ以上のコマンドパケット
がリソースへ発生されることが考えられ、それ故、リソ
ースは、コマンドが脱落しないように設計されねばなら
ない。それ故、受信器がビジー流れ制御信号をアサート
した後にも、M個のメッセージを受け入れることができ
ねばならず、但し、Mは、次の式III で定められる。 式III : M=(フレームクロックでの流れ制御待ち時間)/(フ
レームクロックでのパケット長さ) 「M」の値は、ここでは、チャンネル当たりに得られる
専用スロットの数を定義する。
【0148】図25には、各チャンネルごとに個別のリ
ソースを使用して仮想チャンネルが実施される例が示さ
れている。2つのノード420及び424の部分は、ハ
イアラーキースイッチ(HS)422を経て互いに接続
されて示されている。グローバルポート420は、バス
421aを経てスイッチ422から入力データを受け取
り、そしてバス421bを経てスイッチ422にデータ
を送信するように接続される。同様に、グローバルポー
ト424は、バス423aを経てスイッチ422にデー
タを送信し、そしてバス423bを経てスイッチ422
からデータを受け取るように接続される。データバス4
21a、421b、423a及び423bの各々は、全
ての形式のチャンネルコマンドを送信又は受信する。待
ち行列機構425のような待ち行列機構は、各リソース
の各入力及び出力端子に設けられる。この待ち行列機構
は、多数の個々に制御されるバッファ425a−425
eを備え、各バッファは、1つの形式のチャンネルコマ
ンドのみを専用に記憶する。バッファ425aは、Q0
チャンネルコマンドのみを記憶し、バッファ425b
は、Q0Vicチャンネルコマンドのみを記憶し、等々
となる。
【0149】コマンドパケットが各リソースインターフ
ェイスに受け取られるときに、コマンドの形式がパーズ
され、そしてパケットは、適当なバッファへ送られる。
コマンドパケットがノードの適当なプロセッサ又はIO
Pへ送られる準備ができると、それらが適当なバッファ
から選択され、そしてARBバス及びQSA(図6)を
経て送られる。各チャンネルごとに1つづつ、5つのサ
ーチエンジンがあり、各チャンネルに対して次のメッセ
ージを探索する。上記機構においては、各チャンネルが
独立して流れ制御され、そしてシステム全体にわたりハ
イアラーキーの最下位チャンネル以外の各チャンネルに
スロットが指定される。これは、チャンネルがリソース
依存性により下位チャンネルによって決して阻止されな
いことを保証する。上位チャンネルメッセージの移動
は、下位チャンネルメッセージによるリソースの占有に
より阻止されない。
【0150】仮想チャンネル間で物理的バッファを共用
する上記機構は、簡単なものである。より精巧な機構に
ついては、ハイアラーキースイッチに関して最初に述べ
た。仮想チャンネル:裁定及びコヒレンスプロトコル設計の
ルール コヒレンスプロトコルにおいて停滞のないメッセージ送
信を保証するためにはハードウェア機構のみでは不充分
である。というのは、問題のリソース依存性の部分しか
対処しないからである。全てのリソース及び流れ依存性
サイクルを排除するために、多数の付加的な裁定及びコ
ヒレンスプロトコル設計ルールが適用される。第1に、
メッセージの進行は、下位チャンネルメッセージの進行
に依存してはならず、この場合に、Q2は上位チャンネ
ルであり、そしてQ0は下位チャンネルである。アービ
ターは、各チャンネルの流れ制御を互いに独立して維持
しなければならない。例えば、ビジーの流れ制御信号が
Q1に対してアサートされるが、Q2に対してはアサー
トされない場合には、アービターは、Q2メッセージを
進行させねばならない。保留中のコマンドパケットに対
してリソースをサーチするのに使用される全てのサーチ
エンジンは、同じ特性をサポートしなければならない。
【0151】第2に、2つ以上のチャンネル間に共用さ
れるいかなるリソースも、下位のチャンネルが阻止され
た場合に上位のチャンネルが進行できるようにするため
に、上位のチャンネルの各々に対してある専用のスロッ
トを含まねばならない。第3に、全てのチャンネルコマ
ンドは、一貫して作用しなければならない。Q0コマン
ドの終了点は、常に、ディレクトリである。Q1コマン
ド及びQ2コマンドの終了点は、常に、プロセッサであ
る。終了点において、トランザクションを継続するため
に、それらを上位チャンネルへ移動しなければならな
い。例えば、Q0メッセージがディレクトリに到達した
ときには、Q0メッセージを発生することができず、Q
1又はQ2メッセージを発生しなければならない。それ
故、メッセージは、下位チャンネルメッセージへと分岐
又は変換することはできない。
【0152】他の点において分岐するトランザクション
の場合には、同じか又は上位のチャンネルのメッセージ
しか形成できない。例えば、「送信読み取り変更」(Q
1メッセージ)がハイアラーキースイッチにおいて「送
信読み取り変更」、「無効化」及び「記入変更マーカ
ー」を形成するときには、これら全てのメッセージがQ
1メッセージとなる。従って、バスをベースとするシス
テム又はスイッチをベースとするシステムのいずれかに
仮想チャンネルを設ける装置及び方法が提供される。仮
想チャンネル及び上記の順序付け制約を使用することに
より、参照は、ディレクトリによっていったんサービス
されると完了することが保証される。その結果、NAC
K(1つのプロセッサが別のプロセッサにプロセスが完
了しないことを指示する)及びリタイアを必要とする公
知の複雑なプロトコルは排除される。
【0153】5つまでの独立したチャンネルを伴う実施
形態を示したが、本発明の1つの実施形態は、所与の数
のチャンネルに限定されず又は対称的なマルチプロセッ
サシステムに限定されないことを理解されたい。むし
ろ、選択されるチャンネルの数は、各チャンネルに固有
の制御及びハードウェアオーバーヘッドが与えられる
と、コヒレントな通信をサポートするに必要な数でなけ
ればならない。従って、仮想チャンネル制御方法及び装
置は、マルチプロセッサシステムにおいて高性能の、停
滞のない通信を行えるようにする。コヒレンス性を維持するためのディレクトリの動作 :以
上に、基本的な通信構成を説明し、そしてSMPのノー
ド間に通信が自由に流れるようにするための基本的な制
御構造体が提供された。しかしながら、コヒレンス性の
ための鍵は、自由に流れるコマンドがシステム内の各プ
ロセッサにより正しい順序で「取り扱われる」ように確
保することである。SMPシステム内の全てのコマンド
に対しシリアル化ポイントを与える機構は、各ノードに
おけるディレクトリである。
【0154】上述したように、全てのQ0形式コマンド
は、先ず、関連メモリアドレスのホームディレクトリを
アクセスする。いずれのコマンドに対してもホームディ
レクトリが最初にアクセスされるよう確保することによ
り各コマンドを共通のソースから正しい順序で検討する
ことができる。本発明の1つの実施形態では、シリアル
化順序は、アドレスXに対するディレクトリからの裁定
に勝った後にXに対するQ0コマンドがARBバスに現
れるという順序である。「ロード」形式のコマンドは、
それに対応する読み取りコマンドがホームディレクトリ
にアクセスしたときに順序付けされる。「記憶」形式の
コマンドは、それに対応する「読み取り変更」コマンド
がディレクトリにアクセスするか又はそれに対応する
「クリーン−ダーティ」コマンドがディレクトリにアク
セスしてARBバスに現れるときに順序付けされる。
【0155】例えば、10個のコマンドの以下のシーケ
ンスが種々のプロセッサ(P#)により共通のホームデ
ィレクトリへ発生されると仮定する。但し、Xi は、キ
ャッシュラインXの一部分である。 テーブルIV: 1 P1:記憶X1 (1) 2 P2:ロードX1 3 P3:ロードX1 4 P5:ロードX1 5 P1:記憶X2 (2) 6 P2:記憶X1 (3) 7 P4:ロードX1 8 P5:ロードX2 9 P6:ロードX1 10 P2:記憶X1 (4) キャッシュラインのバージョンは、各記憶動作の結果と
して更新される。従って、コマンド1はバージョン1を
形成し、コマンド5はバージョン2を形成し、コマンド
6はバージョン3を形成し、そしてコマンド10はバー
ジョン4を形成する。
【0156】シリアル化順序は、ディレクトリに到達す
る事象の各シーケンスがキャッシュラインXの正しいバ
ージョンを得るように確保する。例えば、コマンド2な
いし4は、バージョン1を得なければならない。プロセ
ッサP1のコマンド5が記憶を行うときには、全てのバ
ージョン1キャッシュライン(プロセッサP2、P3及
びP5における)に「無効化」を送信しなければならな
い。同様に、プロセッサP2のコマンド6がバージョン
3データでXを更新するときには、プロセッサP1のバ
ージョン2データを無効化しなければならない。プロセ
ッサP4、P6及びP7は、バージョン3データを得る
が、これは、プロセッサP8のバージョン4データの記
憶により後で無効化される。共通のアドレスキャッシュ
ラインXに対する多数のロード及び記憶動作は、システ
ムにおいていかなる所与の時間にも進行し得ることを述
べれば充分であろう。システムは、ロード及び記憶がデ
ィレクトリによりシリアル化順序で処理されるようにこ
れらのコマンドを処理する。
【0157】システムがシリアル化順序を維持しそして
付随的にデータのコヒレンス性を維持するのを助けるた
めに多数の技術が使用される。これらの技術は、Q1チ
ャンネルコマンドの厳密な順序付け、CTD明瞭化、
「シャドーコマンド」、「マーカー記入」及び「遅延ビ
クティム書き込みバッファ動作」を含む。各技術につい
て、以下に詳細に説明する。
【0158】Q1チャンネル順序付け:コヒレンス性を
維持するのに使用される第1の方法は、Q1チャンネル
上を進行する全てのメッセージ、即ちディレクトリから
送られる全てのメッセージが、先入れ先出し順序で進む
ように確保することである。即ち、ディレクトリから別
のプロセッサ又はIOPへ送られるQ1型メッセージ
は、コマンドがディレクトリにおいてシリアル化された
順序に基づいて送られる。例えば、図26のサブシステ
ムの例では、ノード430における第1プロセッサP1
(431)がキャッシュラインXをそのキャッシュ「ダ
ーティ」に記憶すると仮定する。ノード432における
プロセッサP16(433)は、Q0チャンネルに「X
読み取り(Read X)」を発生し、これは、ノード436に
おけるXのホームディレクトリ437へ送られる。又、
ノード432におけるプロセッサP17は、Q0チャン
ネルに「無効−ダーティ」コマンドを発生し、これも、
ノード436におけるXのホームディレクトリ437へ
送られる。「X読み取り」の受信に応答して、ディレク
トリエントリに基づき、「送信X読み取り(ForwardedRe
ad X)」がQ1チャンネルを経てプロセッサP1(43
1)へ送られる。ITDの受信に応答して、ディレクト
リエントリの状態に基づき、「無効化」がハイアラーキ
ースイッチ435へ送られ、これは、Q1チャンネルを
経てプロセッサP1及びプロセッサP16へ「無効化」
を送る。従って、同じ時点で、「X無効化」及び「X読
み取り供給」がQ1チャンネルコマンドとしてP1へ送
られる。
【0159】Q1チャンネルのコマンドが順序ずれして
実行することが許された場合には、「読み取り」の前に
「無効化」が生じることがある。その結果、「読み取
り」のための記入データがプロセッサP16に送られな
いことになり、それ移行の動作の結果が予想し得ないも
のとなる。しかしながら、チャンネルQ1のコマンドを
正しい順序で保つことにより「読み取り」は「無効化」
を受け取る前に処理され、コヒレンス性が維持される。
【0160】本発明の1つの実施形態では、チャンネル
Q1についてのみFIFO順序が維持され、FIFO順
序とは、同じメモリアドレスに対応する全てのメッセー
ジがFIFO順序に留まることを意味する。しかしなが
ら、本発明は、Q1チャンネルに対する順序を維持する
ことのみに限定されるものではなく、チャンネルのいか
なる組み合わせに対する順序の維持も含むように拡張す
ることができる。上記の順序付け手順を実施する1つの
方法は、QSAチップ(図6)のQSARB11により
実行される。QS ARBは、全てのQ0トランザクシ
ョンをノードのホームメモリスペースに対してシリアル
化する。その結果、Q1パケットのシリアル流が発生さ
れて、ノードのローカルプロセッサと、グローバルポー
ト及びハイアラーキースイッチを経てノードから離れた
プロセッサとの両方に向けられる。第1の順序付けルー
ルを次に説明する。所与のQS ARBにより発生され
る全てのQ1パケットは、シリアルな順序で発生され
る。所与のQS ARBからの幾つかの又は全てのQ1
パケットがターゲットとする全てのプロセッサは、これ
らのQ1パケットを、それらがQS ARBにより発生
された順序で見る。
【0161】このルールをサポートするために、QSA
チップは、ノード内の接続されたプロセッサとやり取り
される全てのQ1パケットに順序を維持する。グローバ
ルポートのロジックは、ハイアラーキースイッチとQS
Aチップとの間に転送される全てのパケットにFIFO
順序を維持する。更に、ハイアラーキースイッチは、所
与の入力から所与の出力へ送られる全てのQ1パケット
にも順序を維持する。このルールは、1つのQS AR
BからのQ1パケットと、別のノードのQSARBから
のQ1パケットとの間に特定の順序を命令するものでは
ないことに注意されたい。他のノードから受け取られた
Q1パケットは、ハイアラーキースイッチを経てホーム
ノードにより発生されたQ1パケットと次のようにシリ
アル化される。リモートノードのプロセッサをターゲッ
トとする全てのQ1パケットは、リモートノードのQS
ARBにより処理される。これらのQ1パケットは、
ハイアラーキースイッチによりリモートノードで発生さ
れたQ1パケットとシリアル化される。所与のQS A
RBからのQ1パケットの全ての受信者は、Q1パケッ
トを、それらがQS ARBにおいてシリアル化された
のと同じ順序で見なければならない。
【0162】図27は、多数のQ0及びQ1コマンドの
順序付けが上記の順序付けガイドラインに基づいてSM
Pを通して処理されるところを示すブロック図である。
ノード440のプロセッサPxはコマンドQ0aを発生
し、プロセッサPyはコマンドQ0bを発生し、そして
プロセッサPzはコマンドQ0cを発生すると仮定す
る。同じ時間中に、QS ARB441は、プロセッサ
Pr及びPqからのQ1メッセージをグローバルポート
443から受け取る。これらのメッセージは、次のよう
に順序付けされる。QS ARB441は、Q0a、Q
0b及びQ0cを処理して、Q1a、Q1b及びQ1c
応答を発生する。これらの発生されたQ1コマンドは、
到来するQ1コマンドと合成されて、コマンドの順序付
けされた流れをFIFO442へ供給し、ローカルプロ
セッサへと送る。FIFOコマンドの順序は、QS A
RBにより処理されたコマンドの順序を反映する。Q1
a、Q1b及びQ1cコマンドは、グローバルポート4
43へ送られ、リモートノードへ送信される。グローバ
ルポートの出力バッファ444は、これらのコマンド
を、それらがQS ARBにより処理されたのと同じ順
序で記憶する。この順序は、図14−19について上述
した方法を用いてメッセージがリモートCPU454へ
送られるときにハイアラーキースイッチ446により維
持される。
【0163】図27Aは、ハイアラーキースイッチにお
いて従う別の順序付けガイドラインを示す。上述したよ
うに、ハイアラーキースイッチは、ハイアラーキースイ
ッチの所与の入力ポートに現れてハイアラーキースイッ
チの共通の出力ポートをターゲットとする多数のパケッ
トが、それらが入力ポートに現れたのと同じ順序で出力
ポートに現れるよう確保することにより、順序を維持す
る。
【0164】図27Bを参照すれば、上述したように、
ハイアラーキースイッチは、入力メッセージをマルチキ
ャスティングする役目も果たし、即ち受け取った1つの
Q1パケットを2つ以上の行先ノードに送信するという
役目も果たす。スイッチによりマルチキャスティングさ
れるパケットの一例は、無効化パケットである。ハイア
ラーキースイッチの異なるポートから入力された多数の
パケットが共通の出力ポートにマルチキャスティングさ
れるときには、Q1パケットは、全ての出力ポートにお
いて同じ順序で現れねばならない。例えば、パケット1
及びパケット2の両方がハイアラーキースイッチ460
に受け取られる場合に、2つのメッセージをプロセッサ
464及び466にマルチキャスティングする1つの許
された方法は、上記のように、メッセージ2がメッセー
ジ1の前に両プロセッサに到着するようにすることであ
る。別の許された方法は、メッセージ1のパケットがメ
ッセージ2のパケットの前に両プロセッサに到着するよ
うにすることである。しかしながら、2つのプロセッサ
は、2つのパケットを異なる順序で受け取ってはならな
い。
【0165】ハイアラーキースイッチが従わねばならな
い別の順序付けルールは、多数の入力ポートからのQ1
パケットの順序付けされたリストが共通の出力ポートを
ターゲットとするときに、Q1パケットが、全ての到来
するQ1パケットの1つの共通の順序付けに合致する仕
方で出力ポートに現れるように確保することである。例
えば、図27Cにおいて、入力ポート461には、パケ
ット2がパケット4の前に受け取られる。同様に、入力
ポート462には、パケット1がパケット3の前に受け
取られる。停滞を防止するには、これら命令の全体的な
順序を遵守しなければならない。出力パケットを与える
1つの許された方法は、パケット3を最初にノード46
4に送信し、そしてパケット1を最初にノード466に
送信することである。この送信が図27Cに示されてい
る。別の許された出力は、パケット2及び4を受信者の
プロセッサにより最初に受け取ることである。しかしな
がら、1つのプロセッサがパケット3を最初に受け取り
そして別のプロセッサがパケット4を最初に受け取る場
合には、プロセッサがそれらの元のシーケンスの他のパ
ケットの受信を待機してストールするので停滞が生じ得
る。それ故、Q1チャンネルにおいて順序が維持される
よう確保するルールが設けられる。本発明の1つの実施
形態では、性能の理由で、Q0及びQ2チャンネルパケ
ットを順序ずれして処理するのが望ましい。データの一
貫性を確保するために、多数のコヒレンス性機構が以下
に述べるように設けられる。
【0166】ダーティへの変更の明瞭化 上述したように、Q1形式のコマンドのみが、ディレク
トリに定義されたシリアル化順序で維持される。本発明
の1つの実施形態では、Q0及びQ2コマンドは順序付
けされない。従って、受け取られるQ0及びQ2コマン
ドの相対的なタイミングの結果としてディレクトリにコ
ヒレンス性の問題が生じないように予防策がとられる。
発生する1つのコヒレンス性の問題は、ディレクトリエ
ントリの構造によるものである。図9に示すように、各
ディレクトリエントリは、所有権フィールドと、各ノー
ドに対して1つの存在ビットとを含む。存在ビットは、
関連ノードの4つのプロセッサの1つにデータが存在す
ることを示すおおよそのベクトルである。4つのプロセ
ッサのいずれかが動作すると、存在ビットがセットされ
る。従って、ノードのどのプロセッサが存在ビットをセ
ットしたかに関してある種の曖昧さが生じる。この曖昧
さは、ある場合にコヒレンス性の問題を引き起こす。
【0167】例えば、図28A及び28Bは、2つのノ
ード470及び472のブロック図である。ノード47
0[グローバルシステムのノードID3]は、プロセッ
サP12、P13、P14及びP15を備え、一方、ノ
ード472[グローバルシステムのノードID7]は、
ノードP28、P29、P30及びP31を含む。
【0168】時間T0−T3の種々の一連の周期におけ
る所与のキャッシュラインXのディレクトリエントリの
状態は、図28Bにおいてディレクトリ状態テーブル4
55に示されている。この例では、キャッシュラインX
のホームノードは、ノード470又は472以外のノー
ドである。時間T0において、キャッシュラインXの所
有者は、所有者ID80で示すようにメモリである。更
に、時間T0において、ノードID7のプロセッサ30
は、キャッシュラインXのクリーンなコピーを記憶す
る。時間T1において、プロセッサ14は、「記憶」コ
マンドを送信し、これは、「読み取りブロック変更X」
に変換され、そしてキャッシュラインXのホームディレ
クトリへ送られる。メモリが所有者であるから、プロセ
ッサP14は、メモリからデータを得ることができ、そ
してキャッシュラインの所有者となる。キャッシュライ
ンXの古いバージョンを無効化するためにノード7に無
効化が送信され、そしてノード7の存在ビットがクリア
される。更に、プロセッサP14は、そのノード存在ビ
ット456(ビット3)をセットする。キャッシュライ
ンXは、変更及び記憶のためにホームメモリからプロセ
ッサP14へ送られる。
【0169】時間T2に、プロセッサ31のような別の
プロセッサが、キャッシュラインXの「読み取り」を発
生する。この「読み取り」は、プロセッサP14から
「記入」を経てデータを得る。従って、時間T2に、デ
ィレクトリは、ノードID3(プロセッサP14)及び
ノードID7(プロセッサP31)の両方が、ノード存
在ビット458及び456で示すように、キャッシュラ
インXのコピーを記憶することを指示する。時間T3
に、プロセッサ30によりCTDが発生される場合に
は、システムの異なるプロセッサから見たキャッシュラ
インXの状態は、次の理由でインコヒレントとなる。C
TDがディレクトリに到達すると、Xのディレクトリエ
ントリを読み取り、そしてそのノード、即ちノードID
7の存在ビット458が既にオンであるかどうか決定す
る。その結果、プロセッサ30は、次いで、CTD要求
において成功したと仮定する。プロセッサ30は、キャ
ッシュラインXのプロセッサ14のコピーを無効化し、
そしてディレクトリの所有者フィールドを更新する。こ
の動作は、予想し得ない結果を招くことがある。という
のは、プロセッサP14がプロセッサP30よりも最新
のデータバージョンを記憶するからである。
【0170】1つの問題は、プロセッサ30がプロセッ
サ14により形成されたキャッシュラインの古いバージ
ョンをまだ記憶しており、そしてプロセッサ14がデー
タの最新のバージョンを無効化するように通知したこと
である。このような状態は、SMPシステムで重大なコ
ヒレンスの問題を生じさせる。上記問題を解消するのに
使用できる幾つかの方法がある。その1つの方法は、シ
ステムの各プロセッサごとに1ビットを与えるようにデ
ィレクトリエントリの存在ビット拡張することである。
従って、分解能がノードレベルからプロセッサレベルへ
変更される。しかしながら、この解決策は、不都合なこ
とに、ディレクトリのサイズを増大する。
【0171】本発明の1つの実施形態は、同じアドレス
への保留中参照がそのノードに対してトランシット状態
にあるときにCTDコマンドを低速化することにより上
記曖昧さの問題を防止するより簡単な方法を提供する。
同じアドレスに対して保留中の要求がある場合には、そ
の以前の要求がリタイアするまでCTDが保持される。
所与のノードのトランザクション追跡テーブル(TT
T)(図10)を使用して、そのノードに対する保留中
のグローバル参照を監視する。更に、CTDがTTTに
受け取られた後に受け取った要求は、失敗となる。図1
0を参照して述べたように、TTTは、完全に連想式の
多機能制御構造体である。TTTは、2つの一般的なタ
スクを実行する。これは、その関連ノードにより発生さ
れた全てのリモート参照のアドレスを記憶する。従っ
て、TTTは、そのトランザクションが完了したとみな
されるまで、ノードにより発生された各リモートアクセ
スに対して1つの情報エントリを記憶する。更に、TT
Tは、ローカルアドレスの要求に応答して、過渡的なコ
ヒレンス状態に関してコヒレンス情報を与える。従っ
て、TTTは、アクセスがトランシット状態にある間に
その状態を追跡するためのテーブルである。他の処理シ
ステムは、いかなる瞬間にも所与のキャッシュラインへ
の1つの参照をトランシット状態にすることができる。
トランシット状態にあるキャッシュラインへのその後の
参照は、トランシット状態の参照が完了するまで阻止さ
れる。
【0172】これに対し、ディレクトリにおけるコマン
ドのシリアル化と、チャンネル順序付けルールとによ
り、本発明のSMPは、同じキャッシュラインへの多数
の参照を所与の瞬間に進行させることができる。その結
果、SMPの全性能が改善される。TTT522は、Q
SAチップ535のロジックにより、グローバルポート
に発生されたトランザクションの状態を決定するのに使
用される。グローバルポートへ応答を発生する前に、Q
SAは、先ず、TTTにアクセスして、同じキャッシュ
ラインへのどんな参照が保留中であるかを決定する。参
照は、最後に受け取ったトランザクションに応答してT
TTからリタイアしていない場合には保留中である。
【0173】参照がTTTからいかにリタイアするか
は、コマンドフィールド584に示された参照の形式に
依存する。例えば、TTTに記憶するためにグローバル
ポートへ送られる「X読み取り」参照は、「ここに記
入」588a 及び「マーカーをここに記入」588b の
両方の状態ビットを受け取ることを必要とする。(「マ
ーカーの記入」は、いかに詳細に述べる。)CTD又は
ITDのような状態型の参照の場合に、TTTにおいて
ACK/NACKビット588c をセットすれば、その
エントリをリタイアするのに充分である。
【0174】図29は、TTTを使用して曖昧なディレ
クトリエントリを排除するところを示すフローチャート
である。ステップ500において、キャッシュラインX
は、そのホームノードのメモリに記憶され、そしてノー
ド7のプロセッサ30は、データのコピーを記憶する。
ステップ502において、「ReadModX」がプロ
セッサ14により発生される。その結果、無効化がノー
ド7に送られる。ステップ504において、プロセッサ
P31は、「ReadX」を発生し、これは、ノード7
のTTTのエントリを次の状態で形成する。
【0175】 アドレス |コマンドID |状態 ~ | |Fill ~ Fmark ~ Shadow ~ ACK/NACK X |Read 31 | ~ ~ ~ ステップ506において、プロセッサP30は、CTD
Xを発生する。QSAチップは、CTD命令のアドレス
を検査し、それがリモートCTDであることを決定し、
そしてTTTへのGPリンクを経てグローバルポートへ
送信する。TTTの内容は、以下に示す通りである。 アドレス |コマンドID |状態 ~ | |Fill ~ Fmark ~ Shadow ~ ACK/NACK X |Read 30 | ~ ~ ~ X |Read 31 | ~ ~ ~ 図6について述べたように、グローバルポートは、TT
Tからの情報を使用して、どのコマンドをハイアラーキ
ースイッチから送出することが許されたかを決定する。
本発明の1つの実施形態では、保留中の「読み取り」が
トランシット状態にあるとTTTが決定した場合に、グ
ローバルポートは、「読み取り」結果が返送されるまで
CTDをスイッチへ送ることが防止される。
【0176】図29のフローチャートに示す例では、ア
ドレスXへの保留中の読み取り要求は、TTTにより識
別される。その結果、ステップ508において、CTD
は、「読み取り」がもはや保留中でなくなるまで、オフ
に保たれる。「読み取り」は、「記入」及び「マーカー
記入」の両方がノード7に返送されるまで保留となる。
この時間中に、ステップ502においてReadMod
により発生された無効化がノード7に到達し、各ノード
のDTAGSを更新する。Xの無効化がTTTに到達す
ると、TTTは、TTTに保持されたCTDを失敗と表
示し、これは直ちに解除される。ステップ510におい
て、CTDが依然TTTにある場合には、グローバルポ
ートを経て送信される。従って、TTTを使用して、C
TDコマンドを適当にオフに保持し又は失敗状態とする
ことにより、ディレクトリの存在ビットの曖昧さにより
生じるコヒレンスの問題を排除することができる。
【0177】マーカーの記入:プロセッサに対するほと
んどの応答は、Q1チャンネルにおけるものであり、従
って、上記のルールによれば、正しい順序が維持され
る。しかしながら、Q2チャンネルで受け取られたメッ
セージは、この順序制約を受けない。Q2型のメッセー
ジは、「記入」及び「記入変更」を含む。Q2型メッセ
ージの到着は、ディレクトリにおいて明らかなように、
シリアル化順序を表わさないので、返送データに潜在的
な曖昧さが生じる。例えば、「無効化」がQ1を進行
し、そして「記入変更」がQ2を進行するので、コヒレ
ンス性を維持するためにどの動作が順序において最初に
生じるべきかを決定する何らかの方法がなければならな
い。
【0178】例えば、図30を参照すれば、2つのノー
ド520及び532が示されている。説明上必要なノー
ドの部分しか示されていない。プロセッサP2(52
4)及びプロセッサP4(534)がキャッシュライン
Xのコピーを記憶すると仮定する。キャッシュラインX
のホームノードは、ノード532である。以下の説明に
おいて、次のパケットにより使用されるチャンネルは、
異なる線を用いて指示される。Q0コマンドは、単一線
矢印で指示され、Q1コマンドは、二重線矢印で指示さ
れ、そしてQ2コマンドは、破線矢印で指示される。プ
ロセッサP4がキャッシュラインXの独占的所有権を得
るためにCTD Xを発生すると仮定する。これに応答
して、ディレクトリ存在ビット及びDTAG(図示せ
ず)により、ディレクトリ542は、ノード520へ無
効化を発生する。この無効化は、Q1チャンネルを経て
ノード520のDTAGSを更新し、そしてコピーを有
する全てのプロセッサ(ここではプロセッサP2)に無
効化調査を送信する。
【0179】次いで、プロセッサP1は、Xのホームデ
ィレクトリ542へReadModXを発生する。上記
のように、Xは、現在プロセッサP4により所有され、
それ故、コヒレンスプロコルによれば、Forward
edReadMod XがプロセッサP4へ送られる。
プロセッサP4は、それに応答して、Q2チャンネルを
経てプロセッサP1へFillModを発生する。Q2
チャンネルの通信は、Q1の通信とシリアル化されない
ので、CTD Xからの「無効化」がノード520に到
達する前にQ2のFillModがプロセッサP1に到
達する可能性が存在する。その結果、P1のキャッシュ
には有効データが書きこまれるが、そのすぐ後で、DT
AGSがノードにおけるXのコピーを無効化するように
セットされ、そしてP2及びP1に「無効化」が送られ
る。しかしながら、「無効化」は、P2のバージョンの
みに対応し、P1におけるバージョンには対応しない。
ここで、システムは、インコヒレントな状態となる。デ
ィレクトリ544は、P1を所有者として記録するが、
P1はまだ無効化されている。
【0180】本発明の1つの実施形態は、各ノードのグ
ローバルポートに「マーカー記入」及びトランザクショ
ン追跡テーブル(図10)を使用することによりこの問
題を克服する。「マーカー記入(Fill Marker) 」又は
「マーカー記入変更(Fill Marker Mod)」は、ホームノ
ードのメモリに現在記憶されていないデータに対する
「読み取り」又は「読み取り変更」要求に応答して発生
されるパケットである。即ち、「マーカー記入」又は
「マーカー記入変更」は、「送信読み取り(Forwarded R
ead)」又は「送信読み取り変更(Forwarded Read Mod)」
と同時に発生される。従って、「マーカー記入」及び
「マーカー記入変更」は、Q1チャンネルコマンドであ
る。「送信読み取り」又は「送信読み取り変更」コマン
ドは、キャッシュラインを記憶するプロセッサに送られ
るが、「マーカー記入」又は「マーカー記入変更」の行
先は、元の「読み取り」又は「読み取り変更」を供給し
たプロセッサである。
【0181】「マーカー記入」は、発生元プロセッサ
が、ディレクトリに生じるシリアル化順序を決定できる
ようにする。図31を参照すれば、「マーカー記入」の
適用は、上記問題を次のように矯正する。前記したよう
に、プロセッサ53AがXのCTDをXのホームディレ
クトリに発生し、その結果、「無効化」550がQ1チ
ャンネルを経てノード520へ送られると仮定する。プ
ロセッサP1(522)がRead Mod Xをリモ
ートディレクトリに発生すると、その要求に対してTT
Tエントリが発生される。この要求に対するTTTテー
ブルエントリの例が図32に示されている。TTTテー
ブルエントリは、「ここに記入」及び「マーカーをここ
に記入」状態ビットを含むことに注意されたい。これら
ビットの各々は、ノード520のグローバルポートに各
パケットが受け取られるのに応答してセットされる。T
TTエントリは、「記入」及び「マーカー記入」の両方
が返送されるまでクリアされない。
【0182】図31に戻ると、上述したように、プロセ
ッサ522からのRead ModXは、プロセッサ5
3AへのFRdModXを生じる。同時に、チャンネル
Q1を経て、Fill Marker Mod X55
2がプロセッサP1に返送される。「無効化」及びFi
ll Mod Markerの両方が同じQ1チャンネ
ルに送られる。チャンネルQ2のFill Mod55
4は、「無効化」の前にノード520に到着すると仮定
する。グローバル参照の「タグ複製」状態は、Fill
Mod又はFill Mod Markerの返送に
応答して更新される。従って、Fill Modは、X
の所有権をプロセッサP1として表わすようにXのDT
AG状態を更新させる。
【0183】「無効化」550が、ノード520に到達
する次の命令であると仮定する。TTTは、「送信読み
取り」命令の状態を決定するためにアクセスされる。こ
の点において、TTTエントリは、「ここに記入」ビッ
トをセットするが、「マーカーをここに記入」ビットは
セットされない。従って、TTTは、無効化及びリモー
ト読み取り動作の相対的なタイミングに関する指示を与
える。Q1コマンドのシリアル化のために、無効化は、
プロセッサ522からのRdModXよりも早い時間に
ディレクトリ542に発生されたと推測でき、従って、
Fill Modが新しいバージョンであり、プロセッ
サ522のデータコピーには無効化が適用されない。そ
の結果、プロセッサP1のDTAGエントリは、無効化
されない。
【0184】上記実施形態は、TTTをグローバルポー
トに存在するものとして示したが、別の実施形態によれ
ば、各ノードの各プロセッサは、ディレクトリへの要求
を監視することにより共通のアドレスへのリモート要求
の状態を追跡することができる。従って、「マーカー記
入」は、単にTTTへ送られるのではなく、ディレクト
リにより関連プロセッサへ送られる。従って、TTT
は、2つの目的を果たすことが明らかである。マルチプ
ロセッサノードから送出されたコマンドの形式を監視す
ることにより、TTTは、同じアドレスへの他のコマン
ドが完了するまで、あるコマンド(CTDのような)の
送信を禁止することができる。更に、要求がQ2チャン
ネル(「マーカー記入」のような)へ移行したときにT
TTに指示する表示機構を設けることにより、TTTを
用いて、異なるチャンネルに返送されるコマンド(即
ち、Q2記入及びQ1コマンド)間の相対的なタイミン
グ指示を与えることができ、従って、メモリを崩壊する
ことのあるコマンドがプロセッサへ送られるのを防止す
ることができる。
【0185】シャドーコマンド 上記説明から明らかなように、ローカルアクセスは、通
常、リモートアクセスよりも相当に早い。従って、性能
に関しては、ローカル及びリモートアクセスの両方がS
MPシステムにおいて同時に生じることが許される。し
かしながら、ローカルアクセスの発生によりリモートア
クセスに対して停滞の問題を生じさせる幾つかの場合が
ある。例えば、図33Aを参照すれば、1つのプロセッ
サ562がキャッシュラインXにRdXを発生すると仮
定する。キャッシュラインXのホームノードは、ノード
560である。ノード560のディレクトリは、プロセ
ッサ582がキャッシュラインを現在所有することを指
示する。従って、Forwarded Read Xが
582に送られる。その後、ノード560のプロセッサ
564がCTD Xを発生すると仮定する。上記のよう
に、キャッシュラインXは、ノード560に対してロー
カルであり、CTDが成功すると、「無効化」をプロセ
ッサP1に(及び図示のようにプロセッサP5にも)送
る。
【0186】図33Bを簡単に参照すれば、参考として
ここに取り上げる本発明と同日に出願されたバンドレン
氏等の「分散型データ依存性ストール機構(Distributed
Data Dependency Stall Mechanism) 」と題する特許出
願に開示されたように、プロセッサP1のような各プロ
セッサは、同じキャッシュ位置に対する保留中の読み取
りがある場合にキャッシュへの調査をストールするため
のロジックを備えている。上記の例が与えられると、R
ead Xの作用は、ミスアドレスファイル(MAF)
574にアドレスXを記憶することである。MAFの内
容は、到来する調査に対して比較され、そして到来する
調査とMAFのアドレス間に一致があるときに、調査待
ち行列がストールされる。
【0187】「記入」データがプロセッサ582から返
送されるときに調査待ち行列が解除される。しかしなが
ら、同じ形式のトランザクション(即ち、P5がリモー
トRd Yを実行し、次いで、P6がCTD Yを発生
する)がノード580に生じる場合に、プロセッサP5
の調査待ち行列がストールされ、Read Y要求が満
足されるのを保留する。P2により発生された「無効
化」の後にP5からForwarded Read Y
が送られる状態でP1調査待ち行列がストールされるの
と同時に、P6により発生された「無効化」の後にプロ
セッサP1からForwarded Read Xが送
られる状態でP5の調査待ち行列がストールされた場合
には、停滞が生じる。
【0188】この停滞問題を防止するための多数の解決
策が存在する。第1に、全ての参照をリモートとするこ
とができ、即ち全ての参照を(ホームノードからの参照
も)、それらがホームノードに送られる前にスイッチに
送ることができる。全ての参照がリモートにされた場合
には、上述した中央の順序付けルールに基づき、停滞状
態は生じない。第2の解決策は、キャッシュラインへの
いずれかの参照がリモートから送られたときに所与のキ
ャッシュラインへの全ての参照をストールすることであ
る。しかしながら、この解決策は、これまでのローカル
動作の性能に著しく影響し、それ故、好ましいものでは
ない。
【0189】本発明の1つの実施形態は、コマンドシャ
ドー作用の使用によるローカル及びリモート参照の混合
により課せられる潜在的な停滞を克服する。キャッシュ
ラインXへのローカル参照がリモートプロセッサへ送ら
れると、そのキャッシュラインへのその後の全ての参照
がハイアラーキースイッチへリモートから送られ、キャ
ッシュラインのローカル参照及びその後の全ての参照が
完了するまで、中央で順序付けされる。従って、まだシ
ャドー状態であるキャッシュラインへの以前の参照は、
キャッシュラインへの現在の参照もシャドー状態にす
る。 図34及び35を参照して、上記例をシャドーコ
マンドの使用と共に説明する。図35は、TTTの内容
を例示している。第1プロセッサP1は、RdXをアー
ビターに発生する。上述したように、プロセッサP5へ
のFRdXを生じ、これはTTTに記録される。その
後、プロセッサP2は、CTD XをARBに発生す
る。ARBは、TTTを検査し、リモートプロセッサへ
送られる保留中のローカル読み取りがあると決定し、そ
してグローバルポートからプロセッサP5へInval
Xを送る。又、この動作を表わすエントリもTTTに形
成され、そのシャドービットがセットされる。
【0190】同時に、ノード580において、同様の一
連のトランザクションが生じる。プロセッサP5は、R
d Yを発生し、これはノード560に送られると共
に、P5アドレスをエントリに含ませることによりTT
Tに記録される。プロセッサP6は、その後、CTD
Yを発生する。ノード580のアービターは、CTDア
ドレスをTTT内の保留中読み取りに対して一致させ、
そしてCTD Yをグローバルポートにわたり「シャド
ー」処理する。そのCTD Yに対してTTTにエント
リが形成され、このエントリは、TTTにおいてそのシ
ャドービットをセットし、CTD Yが、Yへの要求の
適切な順序付けを確保するためにリモート送信されたロ
ーカル参照であることを指示する。上述したように、両
ノードにおいて調査シーケンスで「無効化」の後にFR
dがあるときに問題が生じる。「無効化」は、ここでは
中央で順序付けされるので、両無効化を両方の「送信読
み取り」の前にそれらの調査待ち行列へ送信できないこ
とにはならない。というのは、それらは、共通点即ちハ
イアラーキースイッチにおいてシリアル化されるからで
ある。従って、図36を参照すれば、コマンドの入力シ
ーケンスは、ハイアラーキースイッチ568へ入力され
るように示されている。許容し得る出力シリアル化順序
は、順序a−fとして識別される。上記のQ1チャンネ
ル順序付けルールによれば、ハイアラーキースイッチへ
のパケット入力のシリアル化順序がスイッチ出力に維持
されることに注意されたい。それ故、上記の場合には、
FRdは、行先ノードへ送られるときにその関連する
「無効化」に先行する。
【0191】ノードの1つは、調査待ち行列に「無効
化」を受け取り、その後、「送信読み取り」を受け取
る。例えば、シリアル化順序を用いて、プロセッサP5
の調査待ち行列は、Inval Yによりストールさ
れ、そしてFrd Xがストールされて、記入を保留す
る。しかしながら、この例では、Frd Yは、Inv
alXの後ではなく、従って、P5調査待ち行列を阻止
しないように「記入」データを与えることができる。リ
モート参照のためにデータが返送されるときには、その
参照に対応するTTTエントリがドロップされる。元の
参照をシャドー処理した他の参照がTTTに存在するこ
とがある。これらコマンドがハイアラーキースイッチか
ら受け取られるときには、シャドー処理されたコマンド
の各々に対するTTTエントリもドロップされる。最終
的に、リモートアクセス及びシャドーアクセスが全て完
了し、そしてTTTがもはやキャッシュラインへマップ
するエントリを含まなくなると、そのキャッシュライン
へのその後のローカル参照をシャドー処理する必要がな
くなる。
【0192】従って、シャドーコマンドの使用により、
ローカル及びリモートコマンドの共存から生じるリソー
ス依存性の停滞を、ハードウェアの複雑さを著しく増加
せずに排除することができる。上記の例は、「送信読み
取り」及びCTDの使用を含むが、シャドーコマンド方
法は、他の形式の命令及びマルチプロセッサにも等しく
適用できることに注意されたい。一般に、ローカルアド
レスXへの参照が存在し、そしてローカルアドレスXへ
の以前のメッセージがリモートプロセッサ(TTTによ
り指示された)へ送られるか、又はXへの以前の参照が
まだシャドー処理されるときには、Xへの現在の参照も
シャドー処理される。更に、この方法は、上記の単なる
マルチプロセッサ/スイッチハイアラーキーよりも多数
のハイアラーキーレベルを含む他の形式のアーキテクチ
ャーにも使用できる。例えば、上記方法は、多数のハイ
アラーキーレベルを含み、コマンドがキャッシュライン
への以前の保留中参照のハイアラーキーレベルに基づい
て適当なハイアラーキーレベルに送られるコンピュータ
システムにも使用できる。
【0193】従って、大型のSMPコンピュータシステ
ムに使用するためのアーキテクチャ及びコヒレンスプロ
トコルについて説明した。SMPシステムのアーキテク
チャは、多数のマルチプロセッサノードをスイッチに接
続して最適な性能で動作することのできるハイアラーキ
ースイッチ構造体を備えている。各マルチプロセッサノ
ード内には、マルチプロセッサノードの全てのプロセッ
サを最高の性能で動作できるようにする同時バッファシ
ステムが設けられる。メモリはノード間で共用され、マ
ルチプロセッサノードの各々にメモリの一部分が常駐す
る。マルチプロセッサノードの各々は、メモリコヒレン
ス性を維持するための多数の要素、即ちビクティムキャ
ッシュ、ディレクトリ及びトランザクション追跡テーブ
ルを含む。ビクティムキャッシュは、リモートのマルチ
プロセッサノードに記憶されたメモリを行先とするビク
ティムデータを選択的に更新することができ、これによ
り、メモリの全性能が改善される。ディレクトリに関連
して使用されて、メモリに書きこまれるべきビクティム
を識別する遅延書き込みバッファを各メモリに含ませる
ことによりメモリ性能が更に改善される。
【0194】各ノードのディレクトリの出力に接続され
たARBバスは、SMPを経て転送される全てのメッセ
ージに対して中央の順序付けポイントとなる。本発明の
1つの実施形態によれば、メッセージは、多数のトラン
ザクションを含み、各トランザクションは、メッセージ
の処理段階に基づいて多数の異なる仮想チャンネルに指
定される。従って、仮想チャンネルの使用は、システム
順序を維持する簡単な方法を与えることによりデータの
コヒレンス性を維持する上で助けとなる。仮想チャンネ
ル及びディレクトリ構造体を使用すると、従来停滞を生
じるキャッシュコヒレンス性の問題を回避することがで
きる。以上、本発明の好ましい実施形態を説明したが、
その概念を組み込んだ他の実施形態も使用できることが
当業者に明らかであろう。それ故、本発明は、上記の実
施形態に限定されるものではなく、特許請求の範囲のみ
によって限定されるものとする。
【図面の簡単な説明】
【図1A】公知の対称的なマルチプロセッサコンピュー
タシステムのブロック図である。
【図1B】公知の対称的なマルチプロセッサコンピュー
タシステムのブロック図である。
【図2】スイッチを備えた本発明によるマルチプロセッ
サコンピュータノードの1つの一実施形態を示すブロッ
ク図である。
【図3】多数の同時挿入バッファを備えた図1のスイッ
チのデータ経路を示すブロック図である。
【図4A】図3に示す同時挿入バッファの1つの一実施
形態を示すブロック図である。
【図4B】図4に示す同時挿入バッファの1つを制御す
るためのロジックの一実施形態を示すブロック図であ
る。
【図5】図3に示す同時挿入バッファの1つの別の実施
形態を示すブロック図である。
【図6】同様のノードの大きなネットワークへ接続する
ように拡張された図2のマルチプロセッサコンピュータ
ノードのブロック図である。
【図7A】図6のマルチプロセッサノードと同様の多数
のノードを使用して実施されたSMPシステムの一実施
形態を示す図である。
【図7B】図6のマルチプロセッサノードと同様の多数
のノードを使用して実施されたSMPシステムの別の実
施形態を示す図である。
【図8】図6のグローバルポートのブロック図である。
【図9】図6のマルチプロセッサノードのディレクトリ
におけるエントリーを示す図である。
【図10】図8のグローバルポートに使用するためのト
ランザクション追跡テーブル(TTT)を示す図であ
る。
【図11】図7Aにおいて多数のノードを接続するため
のハイアラーキー式スイッチを示すブロック図である。
【図12A】停滞を排除するハイアラーキースイッチ用
の相互接続ロジックの一実施形態を示すブロック図であ
る。
【図12B】図12Aの相互接続ロジックの動作を示す
フローチャートである。
【図13】マルチプロセッサノードの1つから送信され
るデータを停止する流れ制御を与えるために図12Aの
相互接続ロジックに使用される方法を示すフローチャー
トである。
【図14】ハイアラーキースイッチに対してバスを経て
行われるアドレス及びデータパケットの転送を示すタイ
ミングである。
【図15】ハイアラーキースイッチにおいて順序を維持
するためのバッファロジックの一実施形態を示すブロッ
ク図である。
【図16】ハイアラーキースイッチに対して順序を維持
するためのバッファロジックの別の実施形態を示すブロ
ック図である。
【図16A】チャンネルの依存性を矢印で示す図であ
る。
【図17】図16のバッファロジックを動作する1つの
方法を示すフローチャートである。
【図18】ハイアラーキースイッチにおいて順序を維持
するためのバッファロジックの別の実施形態を示すブロ
ック図である。
【図18A】チャンネルの依存性を矢印で示す図であ
る。
【図19】図7A又は7BのSMPに使用するためのプ
ロセッサ命令−ネットワーク命令の変換を示すテーブル
である。
【図20A】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20B】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20C】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20D】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20E】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20F】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20G】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20H】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20I】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図20J】図7A又は7BのSPMにおいてノード間
にパケットを転送するための多数の通信流を示す図であ
る。
【図21】図2又は6のマルチプロセッサシステムに使
用するためのメモリモジュールのレイアウトを示すブロ
ック図である。。
【図22】遅延書き込み動作のために図21のメモリモ
ジュールにより使用される制御ロジックを示すタイミン
グ図である。
【図23】本発明の1つの実施形態においてキャッシュ
コヒレンス性を維持するためにチャンネルに対してマッ
プされる個別のトランザクションの使用を示すフローチ
ャートである。
【図24】図7A又は7BのSMPにおいて仮想チャン
ネルを取り扱うための共用待ち行列構造体の一実施形態
を示すブロック図である。
【図25】図7A又は7BのSMPのノード及びハイア
ラーキーチャンネルにおける個々のチャンネルバッファ
の一実施形態を示すブロック図である。
【図26】仮想チャンネル間にある程度の順序が維持さ
れない場合に生じる問題を説明するためのブロック図で
ある。
【図27A】図7A又は7BのSMPにおいてコヒレン
トな通信を与えるためのQ1チャンネルにおける流れ及
び順序付けの制約を示すブロック図である。
【図27B】図7A又は7BのSMPにおいてコヒレン
トな通信を与えるためのQ1チャンネルにおける流れ及
び順序付けの制約を示すブロック図である。
【図27C】図7A又は7BのSMPにおいてコヒレン
トな通信を与えるためのQ1チャンネルにおける流れ及
び順序付けの制約を示すブロック図である。
【図28A】図7A及び7BのSMPのディレクトリエ
ントリーにおおよそのベクトル存在ビットがあるために
生じる曖昧さの問題を説明するブロック図である。
【図28B】図7A及び7BのSMPのディレクトリエ
ントリーにおおよそのベクトル存在ビットがあるために
生じる曖昧さの問題を説明するブロック図である。
【図29】図28に示す問題の結果として生じるデータ
の曖昧さを防止するために使用される方法を示すブロッ
ク図である。
【図30】異なるチャンネルのパケットが順序づれして
受け取られるために生じるコヒレンス性の問題を示すブ
ロック図である。
【図31】図29に示すコヒレンス性の問題を防止する
ための記入マーカーの使用を示すブロック図である。
【図32】図31について述べた流れ間の命令の状態を
表わすTTTのエントリを示す図である。
【図33A】SMPシステムにおけるダーティへの変更
コマンドの作用を示すブロック図である。
【図33B】SMPシステムにおけるダーティへの変更
コマンドの作用を示すブロック図である。
【図34】図33について述べた問題を矯正するための
シャドーコマンドの使用を示すブロック図である。
【図35】図34について述べたフロー間の命令の状態
を反映するTTTのエントリを示す図である。
【図36】図35に示す例における許容し得る逐次順序
付けを示すフローチャートである。
【符号の説明】
10 マルチプロセッサノード 11 アービター(QSA ARB) 12a、12b、12c、12d プロセッサモジュー
ル 13 メモリ 13a−13d メモリモジュール 14 I/Oプロセッサ(IOP)モジュール 14a I/Oバス 14b IOPタグ記憶装置 14c IOPキャッシュ 15 ローカルスイッチ 16a−16i データリンク 17 ARBバス 18 QSAチップ 19 QSDチップ 20 デュープリケートタグ記憶装置(DTAG) 25a−25e 同時挿入バッファ(SIB) 27 メインアービター 32 バッファ 34a−34h マルチプレクサ 36 入力アービター 38 出力アービター 122 トランザクション追跡テーブル 124 ビクティムキャッシュ 140 ディレクトリ
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 FI G06F 15/167 G06F 15/167 B (72)発明者 シモン シー ステイーリイ アメリカ合衆国 ニューハンプシャー州 03051 ハドソン アンナ ルイス ドラ イヴ 8 (72)発明者 マドハミトラ シャルマ アメリカ合衆国 マサチューセッツ州 01545 シュローズバリー コモンズ ド ライヴ 55−46 (72)発明者 ディヴィッド エム フェンウィック アメリカ合衆国 マサチューセッツ州 01545 アクトン ブラウン ベア クロ ッシング 297

Claims (32)

    【特許請求の範囲】
  1. 【請求項1】 少なくとも1つのプロセッサ及び共用メ
    モリの一部分を各々含む複数の接続されたマルチプロセ
    ッサノードを備えたコンピュータシステムにおいて、 上記複数のマルチプロセッサノードの各々における複数
    のプロセッサに関連した追跡機構であって、上記複数の
    マルチプロセッサノードの1つにおける少なくとも1つ
    のプロセッサの1つにより発生された共用メモリのリモ
    ート部分のアドレスへの要求の位置を、上記複数の接続
    されたマルチプロセッサノードにおける少なくとも1つ
    のプロセッサにより上記アドレスへ発生された複数の他
    の要求に対して識別するための追跡機構を備えたことを
    特徴とするコンピュータシステム。
  2. 【請求項2】 上記共用メモリの上記部分への要求の初
    期順序をそれに対応するマルチプロセッサノードに与え
    るために上記追跡機構に接続されたシリアル化ポイント
    を上記複数のマルチプロセッサノードの各々に更に備え
    た請求項1に記載のコンピュータシステム。
  3. 【請求項3】 上記複数のマルチプロセッサノード各々
    の少なくとも1つのプロセッサ各々は、各々複数のトラ
    ンザクションを含む複数の要求を発生し、これら複数の
    要求各々の複数のトランザクション各々には複数のチャ
    ンネルの対応する1つが指定され、そして上記チャンネ
    ルのうちの第1チャンネルは、上記シリアル化ポイント
    へトランザクションを搬送するためのものである請求項
    2に記載のコンピュータシステム。
  4. 【請求項4】 上記チャンネルのうちの第2チャンネル
    は、上記シリアル化ポイントから発生されたトランザク
    ションを搬送するためのものであり、そして共通のアド
    レスへのトランザクションは、上記チャンネルの少なく
    とも第2チャンネルにおいて厳密に順序付けされる請求
    項3に記載のコンピュータシステム。
  5. 【請求項5】 上記追跡機構は、少なくとも1つの順序
    付けされたチャンネルにおける関連するトランザクショ
    ンにより指示されて参照情報の順序を識別し、その順序
    は、他のチャンネルにおけるトランザクションに対して
    再構成できる請求項4に記載のコンピュータシステム。
  6. 【請求項6】 第3のトランザクションを含む要求の各
    々に対し、その要求に対応するメモリの共用部分に関連
    したマルチプロセッサノードの追跡機構に、その要求が
    第3のトランザクションを有することを指示するための
    手段を更に備えた請求項5に記載のコンピュータシステ
    ム。
  7. 【請求項7】 上記指示手段は、少なくとも1つの順序
    付けされたチャンネルを経て追跡機構へ発生されるコマ
    ンドを更に含む請求項6に記載のコンピュータシステ
    ム。
  8. 【請求項8】 上記追跡機構は、複数のエントリーを更
    に備え、各エントリーは、別のマルチプロセッサノード
    のメモリ位置をアドレスする参照情報のアドレスを記憶
    するためのものであり、そして各エントリーは、関連す
    る要求の状態を指示するための複数の状態ビットを更に
    含む請求項7に記載のコンピュータシステム。
  9. 【請求項9】 上記状態ビットは、要求が第3のトラン
    ザクションを有することを指示する上記順序付けされた
    チャンネルのコマンドがマルチプロセッサノードに返送
    されたかどうかを示すための第1ビットセットを更に含
    む請求項8に記載のコンピュータシステム。
  10. 【請求項10】 上記状態ビットは、更に、 第3のトランザクションがマルチプロセッサノードに返
    送されたかどうかを指示するための第2ビットセット
    と、 状態ビットセットの第1ビット及び第2ビットの両方を
    有するトランザクションテーブルからエントリーを除去
    する手段と、を含む請求項9に記載のコンピュータシス
    テム。
  11. 【請求項11】 上記追跡機構に記憶されたアドレスへ
    発生される要求であって、上記順序付けされたチャンネ
    ルにおけるコマンドの受信を指示するためにそのアドレ
    スに対応する追跡機構の第1ビットがセットされる前に
    受け取られた要求を無視するための手段を更に備えた請
    求項10に記載のコンピュータシステム。
  12. 【請求項12】 上記無視された要求は、無効の要求で
    ある請求項11に記載のコンピュータシステム。
  13. 【請求項13】 アドレスへ発生された要求を無視する
    上記手段は、その要求を発生したプロセッサが、そのア
    ドレスを追跡機構に入力させたプロセッサに対応する場
    合だけ要求を無視する請求項11に記載のコンピュータ
    システム。
  14. 【請求項14】 上記追跡機構に記憶されたアドレスへ
    発生される参照情報を、上記順序付けされたチャンネル
    のコマンドが受け取られるまで遅延するための手段を更
    に備え、上記参照情報は、そのアドレスに対応する追跡
    機構の第1ビットがセットされる前に受け取られる請求
    項10に記載のコンピュータシステム。
  15. 【請求項15】 上記参照情報は、上記アドレスに関連
    したデータの所望のバージョンがマルチプロセッサノー
    ドに返送されるまで更に遅延される請求項14に記載の
    コンピュータシステム。
  16. 【請求項16】 上記参照情報は、上記アドレスに関連
    したデータの所望のバージョンが、そのアドレスを追跡
    機構に入力させた複数のプロセッサの1つに返送される
    まで、更に遅延される請求項13に記載のコンピュータ
    システム。
  17. 【請求項17】 マルチプロセッサコンピュータシステ
    ムの共通のアドレスへ発生される複数の要求間の順序を
    維持する方法であって、上記マルチプロセッサコンピュ
    ータシステムは、スイッチを経て接続された複数のマル
    チプロセッサノードを備え、マルチプロセッサノードの
    各々は、少なくとも1つのプロセッサ及び共用メモリの
    一部分を含み、上記方法は、 上記マルチプロセッサノードの各々から上記スイッチへ
    送られる要求のアドレスリストを維持して、リモートマ
    ルチプロセッサノードの共用メモリの一部分における各
    アドレスに対して要求の相対的な順序を識別し、アドレ
    スに関連した要求が満足されるまでアドレスをリストに
    維持することを特徴とする方法。
  18. 【請求項18】 上記複数のマルチプロセッサノードの
    各々は、対応するマルチプロセッサノードにおける共用
    メモリの一部分へ要求の初期順序を与えるためのシリア
    ル化ポイントを備えた請求項17に記載の方法。
  19. 【請求項19】 上記複数のマルチプロセッサノード各
    々の少なくとも1つのプロセッサ各々は、各々複数のト
    ランザクションを含む複数の要求を発生し、複数のトラ
    ンザクションの各々は、複数のチャンネルの対応する1
    つを経て転送され、そして上記複数のチャンネルのうち
    の第1チャンネルは、上記シリアル化ポイントへトラン
    ザクションを搬送する請求項18に記載の方法。
  20. 【請求項20】 上記複数のチャンネルのうちの第2チ
    ャンネルは、上記シリアル化ポイントから発生されるト
    ランザクションを搬送し、そして共通のアドレスへのト
    ランザクションは、上記複数のチャンネルのうちの第2
    チャンネルにおいて厳密に順序付けされる請求項19に
    記載の方法。
  21. 【請求項21】 上記要求のアドレスリストは、少なく
    とも1つの順序付けされたチャンネルにおける関連する
    トランザクションにより指示されて参照情報の順序を識
    別し、その順序は、他のチャンネルにおけるトランザク
    ションに対して再構成できる請求項20に記載の方法。
  22. 【請求項22】 第3のトランザクションを含む要求の
    各々に対し、その要求に対応するメモリの共用部分に関
    連したマルチプロセッサノードのアドレスリストに、そ
    の要求が第3のトランザクションを有することを指示す
    る段階を更に含む請求項21に記載の方法。
  23. 【請求項23】 上記指示段階は、更に、上記少なくと
    も1つの順序付けされたチャンネルに発生されたコマン
    ドを上記アドレスリストへ発生する段階を含む請求項2
    2に記載の方法。
  24. 【請求項24】 上記アドレスリストは複数のエントリ
    ーを備え、各エントリーは、別のマルチプロセッサノー
    ドのメモリ位置をアドレスする参照情報のアドレスを記
    憶するためのものであり、そして関連する要求の状態を
    指示するための複数の状態ビットを更に含む請求項23
    に記載の方法。
  25. 【請求項25】 上記状態ビットは、要求が第3のトラ
    ンザクションを有することを指示する上記順序付けされ
    たチャンネルのコマンドがマルチプロセッサノードに返
    送されたかどうかを示すための第1ビットセットを更に
    含む請求項4に記載の方法。
  26. 【請求項26】 上記状態ビットは、更に、第3のトラ
    ンザクションがマルチプロセッサノードに返送されたか
    どうかを指示するための第2ビットセットを含み、そし
    て上記方法は、更に、状態ビットセットの第1ビット及
    び第2ビットの両方を有するトランザクションテーブル
    からエントリーを除去する段階を含む請求項25に記載
    の方法。
  27. 【請求項27】 上記アドレスリストに記憶されたアド
    レスへ発生される要求であって、上記順序付けされたチ
    ャンネルにおけるコマンドの受信を指示するためにその
    アドレスに対応するアドレスリストの第1ビットがセッ
    トされる前に受け取られた要求を無視する段階を更に含
    む請求項26に記載の方法。
  28. 【請求項28】 上記無視される要求は、無効の要求で
    ある請求項27に記載の方法。
  29. 【請求項29】 アドレスへ発生された要求を無視する
    上記段階は、その要求を発生したプロセッサが、そのア
    ドレスをアドレスリストに入力させたプロセッサに対応
    する場合だけ要求を無視する請求項28に記載の方法。
  30. 【請求項30】 上記アドレスリストに記憶されたアド
    レスへ発生される参照情報を、上記順序付けされたチャ
    ンネルのコマンドが受け取られるまで遅延する段階を更
    に含み、上記参照情報は、そのアドレスに対応する追跡
    機構の第1ビットがセットされる前に受け取られる請求
    項29に記載の方法。
  31. 【請求項31】 上記参照情報は、上記アドレスに関連
    したデータの所望のバージョンがマルチプロセッサノー
    ドに返送されるまで更に遅延される請求項30に記載の
    方法。
  32. 【請求項32】 上記参照情報は、上記アドレスに関連
    したデータの所望のバージョンが、そのアドレスをアド
    レスリストに入力させた複数のプロセッサの1つに返送
    されるまで、更に遅延される請求項31に記載の方法。
JP34092498A 1997-10-24 1998-10-26 スイッチをベースとするマルチプロセッサシステムに使用するための順序サポート機構 Expired - Fee Related JP4700773B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/957,298 US6122714A (en) 1997-10-24 1997-10-24 Order supporting mechanisms for use in a switch-based multi-processor system
US08/957298 1997-10-24

Publications (3)

Publication Number Publication Date
JPH11282820A true JPH11282820A (ja) 1999-10-15
JPH11282820A5 JPH11282820A5 (ja) 2005-12-02
JP4700773B2 JP4700773B2 (ja) 2011-06-15

Family

ID=25499385

Family Applications (1)

Application Number Title Priority Date Filing Date
JP34092498A Expired - Fee Related JP4700773B2 (ja) 1997-10-24 1998-10-26 スイッチをベースとするマルチプロセッサシステムに使用するための順序サポート機構

Country Status (4)

Country Link
US (1) US6122714A (ja)
EP (1) EP0911731B1 (ja)
JP (1) JP4700773B2 (ja)
DE (1) DE69832943T2 (ja)

Families Citing this family (38)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6587931B1 (en) * 1997-12-31 2003-07-01 Unisys Corporation Directory-based cache coherency system supporting multiple instruction processor and input/output caches
US6442597B1 (en) 1999-07-08 2002-08-27 International Business Machines Corporation Providing global coherence in SMP systems using response combination block coupled to address switch connecting node controllers to memory
US6467012B1 (en) 1999-07-08 2002-10-15 International Business Machines Corporation Method and apparatus using a distributed system structure to support bus-based cache-coherence protocols for symmetric multiprocessors
US6779036B1 (en) 1999-07-08 2004-08-17 International Business Machines Corporation Method and apparatus for achieving correct order among bus memory transactions in a physically distributed SMP system
US6591348B1 (en) 1999-09-09 2003-07-08 International Business Machines Corporation Method and system for resolution of transaction collisions to achieve global coherence in a distributed symmetric multiprocessor system
US6725307B1 (en) 1999-09-23 2004-04-20 International Business Machines Corporation Method and system for controlling data transfers with physical separation of data functionality from address and control functionality in a distributed multi-bus multiprocessor system
US6587930B1 (en) 1999-09-23 2003-07-01 International Business Machines Corporation Method and system for implementing remstat protocol under inclusion and non-inclusion of L1 data in L2 cache to prevent read-read deadlock
US6457085B1 (en) 1999-11-04 2002-09-24 International Business Machines Corporation Method and system for data bus latency reduction using transfer size prediction for split bus designs
US6684279B1 (en) 1999-11-08 2004-01-27 International Business Machines Corporation Method, apparatus, and computer program product for controlling data transfer
US6523076B1 (en) 1999-11-08 2003-02-18 International Business Machines Corporation Method and apparatus for synchronizing multiple bus arbiters on separate chips to give simultaneous grants for the purpose of breaking livelocks
US6516379B1 (en) 1999-11-08 2003-02-04 International Business Machines Corporation Method and apparatus for transaction pacing to reduce destructive interference between successive transactions in a distributed symmetric multiprocessor system
US6542949B1 (en) 1999-11-08 2003-04-01 International Business Machines Corporation Method and apparatus for increased performance of a parked data bus in the non-parked direction
US7529799B2 (en) 1999-11-08 2009-05-05 International Business Machines Corporation Method and apparatus for transaction tag assignment and maintenance in a distributed symmetric multiprocessor system
US6529990B1 (en) 1999-11-08 2003-03-04 International Business Machines Corporation Method and apparatus to eliminate failed snoops of transactions caused by bus timing conflicts in a distributed symmetric multiprocessor system
US6606676B1 (en) 1999-11-08 2003-08-12 International Business Machines Corporation Method and apparatus to distribute interrupts to multiple interrupt handlers in a distributed symmetric multiprocessor system
DE19956829A1 (de) * 1999-11-25 2001-06-07 Siemens Ag Speichereinrichtung für Prozessorsysteme
US6633960B1 (en) * 2000-08-31 2003-10-14 Hewlett-Packard Development Company, L.P. Scalable directory based cache coherence protocol
US6587920B2 (en) * 2000-11-30 2003-07-01 Mosaid Technologies Incorporated Method and apparatus for reducing latency in a memory system
US6892279B2 (en) 2000-11-30 2005-05-10 Mosaid Technologies Incorporated Method and apparatus for accelerating retrieval of data from a memory system with cache by reducing latency
US6493801B2 (en) 2001-01-26 2002-12-10 Compaq Computer Corporation Adaptive dirty-block purging
US6842830B2 (en) * 2001-03-31 2005-01-11 Intel Corporation Mechanism for handling explicit writeback in a cache coherent multi-node architecture
US7237016B1 (en) * 2001-09-07 2007-06-26 Palau Acquisition Corporation (Delaware) Method and system to manage resource requests utilizing link-list queues within an arbiter associated with an interconnect device
US8189591B2 (en) * 2001-10-30 2012-05-29 Exar Corporation Methods, systems and computer program products for packet ordering for parallel packet transform processing
US6961827B2 (en) * 2001-11-13 2005-11-01 Sun Microsystems, Inc. Victim invalidation
US20030196081A1 (en) * 2002-04-11 2003-10-16 Raymond Savarda Methods, systems, and computer program products for processing a packet-object using multiple pipelined processing modules
US6892290B2 (en) * 2002-10-03 2005-05-10 Hewlett-Packard Development Company, L.P. Linked-list early race resolution mechanism
US8185602B2 (en) 2002-11-05 2012-05-22 Newisys, Inc. Transaction processing using multiple protocol engines in systems having multiple multi-processor clusters
JP2004171209A (ja) * 2002-11-19 2004-06-17 Matsushita Electric Ind Co Ltd 共有メモリデータ転送装置
US7636815B1 (en) 2003-04-09 2009-12-22 Klaiber Alexander C System and method for handling direct memory accesses
US8751753B1 (en) 2003-04-09 2014-06-10 Guillermo J. Rozas Coherence de-coupling buffer
US8117392B2 (en) * 2003-10-22 2012-02-14 Intel Corporation Method and apparatus for efficient ordered stores over an interconnection network
US7856534B2 (en) * 2004-01-15 2010-12-21 Hewlett-Packard Development Company, L.P. Transaction references for requests in a multi-processor network
US7971002B1 (en) 2005-04-07 2011-06-28 Guillermo Rozas Maintaining instruction coherency in a translation-based computer system architecture
US7519778B2 (en) * 2005-08-10 2009-04-14 Faraday Technology Corp. System and method for cache coherence
US7958513B2 (en) * 2005-11-17 2011-06-07 International Business Machines Corporation Method, system and program product for communicating among processes in a symmetric multi-processing cluster environment
JP5076418B2 (ja) * 2006-09-19 2012-11-21 ソニー株式会社 共有メモリ装置
US20080098178A1 (en) * 2006-10-23 2008-04-24 Veazey Judson E Data storage on a switching system coupling multiple processors of a computer system
US9075723B2 (en) * 2011-06-17 2015-07-07 International Business Machines Corporation Efficient discard scans

Family Cites Families (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4891749A (en) * 1983-03-28 1990-01-02 International Business Machines Corporation Multiprocessor storage serialization apparatus
JPS62197858A (ja) * 1986-02-26 1987-09-01 Hitachi Ltd システム間デ−タベ−ス共用方式
DE68924306T2 (de) * 1988-06-27 1996-05-09 Digital Equipment Corp Mehrprozessorrechneranordnungen mit gemeinsamem Speicher und privaten Cache-Speichern.
US5060144A (en) * 1989-03-16 1991-10-22 Unisys Corporation Locking control with validity status indication for a multi-host processor system that utilizes a record lock processor and a cache memory for each host processor
CA2047888A1 (en) * 1990-07-27 1992-01-28 Hirosada Tone Hierarchical memory control system
JPH05108473A (ja) * 1991-03-20 1993-04-30 Hitachi Ltd デ−タ処理システム
US5303362A (en) * 1991-03-20 1994-04-12 Digital Equipment Corporation Coupled memory multiprocessor computer system including cache coherency management protocols
US5490261A (en) * 1991-04-03 1996-02-06 International Business Machines Corporation Interlock for controlling processor ownership of pipelined data for a store in cache
US5313609A (en) * 1991-05-23 1994-05-17 International Business Machines Corporation Optimum write-back strategy for directory-based cache coherence protocols
US5442758A (en) * 1993-07-19 1995-08-15 Sequent Computer Systems, Inc. Apparatus and method for achieving reduced overhead mutual exclusion and maintaining coherency in a multiprocessor system utilizing execution history and thread monitoring
US5530933A (en) * 1994-02-24 1996-06-25 Hewlett-Packard Company Multiprocessor system for maintaining cache coherency by checking the coherency in the order of the transactions being issued on the bus
US5551005A (en) * 1994-02-25 1996-08-27 Intel Corporation Apparatus and method of handling race conditions in mesi-based multiprocessor system with private caches
EP0681240B1 (en) * 1994-05-03 2001-01-10 Hewlett-Packard Company Duplicate cache tag memory system
US5655100A (en) * 1995-03-31 1997-08-05 Sun Microsystems, Inc. Transaction activation processor for controlling memory transaction execution in a packet switched cache coherent multiprocessor system

Also Published As

Publication number Publication date
US6122714A (en) 2000-09-19
DE69832943T2 (de) 2006-06-29
EP0911731A2 (en) 1999-04-28
JP4700773B2 (ja) 2011-06-15
EP0911731B1 (en) 2005-12-28
DE69832943D1 (de) 2006-02-02
EP0911731A3 (en) 2000-08-09

Similar Documents

Publication Publication Date Title
JP4700773B2 (ja) スイッチをベースとするマルチプロセッサシステムに使用するための順序サポート機構
US6085276A (en) Multi-processor computer system having a data switch with simultaneous insertion buffers for eliminating arbitration interdependencies
US6014690A (en) Employing multiple channels for deadlock avoidance in a cache coherency protocol
US6154816A (en) Low occupancy protocol for managing concurrent transactions with dependencies
US6108752A (en) Method and apparatus for delaying victim writes in a switch-based multi-processor system to maintain data coherency
US6101420A (en) Method and apparatus for disambiguating change-to-dirty commands in a switch based multi-processing system with coarse directories
US6094686A (en) Multi-processor system for transferring data without incurring deadlock using hierarchical virtual channels
US6279084B1 (en) Shadow commands to optimize sequencing of requests in a switch-based multi-processor system
US6249520B1 (en) High-performance non-blocking switch with multiple channel ordering constraints
US7818388B2 (en) Data processing system, method and interconnect fabric supporting multiple planes of processing nodes
US5900020A (en) Method and apparatus for maintaining an order of write operations by processors in a multiprocessor computer to maintain memory consistency
EP0817071B1 (en) A multiprocessing system configured to detect and efficiently provide for migratory data access patterns
US7627738B2 (en) Request and combined response broadcasting to processors coupled to other processors within node and coupled to respective processors in another node
US8139592B2 (en) Ticket-based operation tracking
JP4410967B2 (ja) デッドロックのないコンピュータシステム動作のためのバーチャルチャネルおよび対応するバッファ割当て
JP7419261B2 (ja) ストリーミングデータ転送のためのフロー圧縮を用いたデータ処理ネットワーク
US6266743B1 (en) Method and system for providing an eviction protocol within a non-uniform memory access system
JP2000227908A (ja) 共用介入サポ―トを有する不均等メモリ・アクセス(numa)デ―タ処理システム
JP2005539282A (ja) 単一のコヒーレントなシステム内の分散コンピュータ・ノードにキャッシュ・コヒーレンスを提供するのにグローバル・スヌープを使用する方法および装置
US8102855B2 (en) Data processing system, method and interconnect fabric supporting concurrent operations of varying broadcast scope
US6546465B1 (en) Chaining directory reads and writes to reduce DRAM bandwidth in a directory based CC-NUMA protocol
US20080307137A1 (en) Data processing system, method and interconnect fabric for synchronized communication in a data processing system
US20030076831A1 (en) Mechanism for packet component merging and channel assignment, and packet decomposition and channel reassignment in a multiprocessor system
US10437725B2 (en) Master requesting missing segments of a cache line for which the master has coherence ownership
US20190042486A1 (en) Techniques for command arbitation in symmetric multiprocessor systems

Legal Events

Date Code Title Description
A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20051005

A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20051005

A711 Notification of change in applicant

Free format text: JAPANESE INTERMEDIATE CODE: A712

Effective date: 20051005

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20070608

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20070618

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20070918

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20070921

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20071217

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20080428

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20080826

A911 Transfer to examiner for re-examination before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A911

Effective date: 20080902

A912 Re-examination (zenchi) completed and case transferred to appeal board

Free format text: JAPANESE INTERMEDIATE CODE: A912

Effective date: 20081114

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20100728

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20100802

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20110131

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20110307

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140311

Year of fee payment: 3

S111 Request for change of ownership or part of ownership

Free format text: JAPANESE INTERMEDIATE CODE: R313113

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140311

Year of fee payment: 3

R360 Written notification for declining of transfer of rights

Free format text: JAPANESE INTERMEDIATE CODE: R360

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140311

Year of fee payment: 3

R360 Written notification for declining of transfer of rights

Free format text: JAPANESE INTERMEDIATE CODE: R360

R371 Transfer withdrawn

Free format text: JAPANESE INTERMEDIATE CODE: R371

S111 Request for change of ownership or part of ownership

Free format text: JAPANESE INTERMEDIATE CODE: R313113

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140311

Year of fee payment: 3

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

LAPS Cancellation because of no payment of annual fees