JPH11282821A - 同時トランザクションを依存性で管理するための低占有度プロトコル - Google Patents
同時トランザクションを依存性で管理するための低占有度プロトコルInfo
- Publication number
- JPH11282821A JPH11282821A JP10340925A JP34092598A JPH11282821A JP H11282821 A JPH11282821 A JP H11282821A JP 10340925 A JP10340925 A JP 10340925A JP 34092598 A JP34092598 A JP 34092598A JP H11282821 A JPH11282821 A JP H11282821A
- Authority
- JP
- Japan
- Prior art keywords
- node
- processor
- data
- packet
- memory
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements 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/46—Multiprogramming arrangements
- G06F9/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
- G06F12/0813—Multiuser, multiprocessor or multiprocessing cache systems with a network or matrix configuration
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
- G06F12/0815—Cache consistency protocols
- G06F12/0817—Cache consistency protocols using directory methods
- G06F12/0828—Cache consistency protocols using directory methods with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Software Systems (AREA)
- Mathematical Physics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
- Multi Processors (AREA)
Abstract
ードがスイッチを経て互いに接続された対称的マルチプ
ロセッサシステム(SMP)。 【解決手段】 大型SMPに使用するアーキテクチャ及
びコヒレンスプロトコルは、多数のマルチプロセッサノ
ードをスイッチに接続して最適な性能で動作できるよう
にするハイアラーキースイッチ構造体を備えている。各
ノードには、同時バッファシステムが設けられ、ノード
の全てのプロセッサが最大性能で動作でき、またメモリ
コヒレンス性を維持する多数の要素、即ちビクティムキ
ャッシュ、ディレクトリ及びトランザクション追跡テー
ブルを含む。ビクティムキャッシュは、リモートノード
のメモリを行先とするビクティムデータを選択的に更新
し、メモリの全性能を改善する。ディレクトリと共に使
用してメモリに書き込まれるビクティムを識別する遅延
書き込みバッファは、メモリ性能を更に改善する。
Description
ータアーキテクチャーの分野に係り、より詳細には、分
散型共用メモリマルチプロセッサシステムに係る。
称型のマルチプロセッサコンピュータは、高性能のアプ
リケーション処理を行うことができる。通常の対称型マ
ルチプロセッサコンピュータシステムは、バスによって
互いに接続された多数のプロセッサを備えている。対称
型マルチプロセッサシステムの1つの特徴は、メモリ空
間が全てのプロセッサ間で共用されることである。1つ
以上のオペレーティングシステムがメモリに記憶され、
種々のプロセッサ間でのプロセッサ又はスレッドの分散
を制御する。異なるプロセッサ又はスレッドが多数の異
なるプロセスを同時に実行できるようにすることによ
り、所与のアプリケーションの実行速度を著しく高める
ことができる。理論的に、システムの性能は、マルチプ
ロセッサシステムにおけるプロセッサの台数を増加する
だけで改善することができる。実際には、ある飽和点を
越えてプロセッサを追加し続けると、単に通信ボトルネ
ックが増えるだけとなり、従って、全システム性能を制
限することになる。
を経て互いに接続された8個のプロセッサを含む典型的
な公知のマルチプロセッサシステム2が示されている。
動作中に、各プロセッサ3a−3hは、共用相互接続バ
ス5を経て互いに他のプロセッサ及び共用メモリ4と通
信する。図1Aの対称型マルチプロセッサ構成は、今日ま
でに構築されたマルチプロセッサについて充分である。
しかしながら、より高速のマイクロプロセッサの出現に
伴い、通常の共用相互接続バスは、接続されたマイクロ
プロセッサの潜在的な全性能を充分に働かせることがで
きない。プロセッサとメモリとの間の唯一の通信リンク
は、共用バスであるから、バスはプロセッサからの要求
で急速に飽和状態となり、各プロセッサがシステムバス
へのアクセスを得るよう試みるときに遅延が増大する。
それ故、プロセッサは、高い速度で動作することができ
るが、性能に関する制限ファクタは、システムバスの使
用可能な帯域である。
ステムの性能において重要なファクタである。帯域巾
は、SMPシステムにおけるノードの対又はサブセット
の間で均一ではないから、業界では、SMPシステムの
通信帯域巾を決定するために「二等分帯域巾」測定を使
用している。二等分帯域巾は、次のように決定される。
システムを等しい計算能力(等しいプロセッサ数)の2
つの部分に区分化する全ての考えられる方法が確かめら
れている。各区分に対し、2つの区分間に維持し得る帯
域巾が決定される。全ての維持し得る帯域巾の最小値
は、相互接続の二等分帯域巾である。2つの区分間の最
小帯域巾は、最悪の通信パターンが存在するときにマル
チプロセッサシステムにより維持できる通信帯域巾を指
示する。従って、大きな二等分帯域巾が望まれる。
ために、多数の相互接続アーキテクチャー即ち「トポロ
ジー」が使用されている。これらのトポロジーは、メッ
シュ、トーラス(円環体)、ハイパーキューブ(超立
体)及び拡張ハイパーキューブを含む。
接続は、図1Bにシステム7として示されている。メッ
シュネットワークの主な利点は、簡単で且つ配線が容易
なことである。各ノードは、少数の他の隣接ノードに接
続される。しかしながら、メッシュ相互接続は、3つの
重大な欠点を有する。第1に、メッセージは、それらの
行先に到達するために平均的に多数のノードを横断しな
ければならず、その結果、通信の待ち時間が長くなる。
第2に、二等分帯域巾は、他のトポロジーに対するもの
であるから、メッシュトポロジーの場合に充分に計測し
ない。最後に、各メッセージはメッシュ内の異なる経路
を進行するので、SMPシステム内には自然の順序付け
ポイントが存在せず、それ故、メッシュトポロジーの実
施を必要とするキャッシュコヒレンスプロトコルがしば
しば非常に複雑なものとなる。
パーキューブトポロジーは、全て、ノードが種々の複雑
な構成、例えば円環体構成又は立体構成で相互接続され
たトポロジーである。トーラス、ハイパーキューブ及び
拡張ハイパーキューブの相互接続は、メッシュ相互接続
よりも複雑であるが、その待ち時間及び帯域巾は、メッ
シュ相互接続よりも優れている。しかしながら、メッシ
ュ相互接続と同様に、トーラス、ハイパーキューブ及び
拡張ハイパーキューブトポロジーは、自然の順序付けポ
イントを与えず、従って、これらのシステムの各々に対
して複雑なキャッシュコヒレンスプロトコルを実施しな
ければならない。共用メモリのマルチプロセッサシステ
ムでは、プロセッサは、通常、将来アクセスされる見込
みが高いと決定されたデータを記憶するために専用キャ
ッシュを使用している。プロセッサは、それらの専用キ
ャッシュからデータを読み取りそしてメモリへ書き戻す
ことなく専用キャッシュにおいてデータを更新するの
で、各プロセッサの専用キャッシュが一貫して即ちコヒ
レントに保持されるよう確保するための機構が必要とな
る。SMPシステムのデータのコヒレンス性を確保する
のに使用される機構は、キャッシュコヒレンスプロトコ
ルと称される。
及び待ち時間に加えて、キャッシュコヒレンスプロトコ
ルの効率も、システム性能の重要なファクタである。キ
ャッシュコヒレンスプロトコルは、待ち時間、ボトルネ
ック、非効率性又は複雑さを多数の仕方で導入する。ロ
ード及び記憶動作の待ち時間は、設計のプロトコルによ
って直接影響されることがしばしばある。例えば、ある
プロトコルでは、全ての無効化メッセージがそれらのタ
ーゲットプロセッサへ送られそして確認メッセージがそ
の元のプロセッサへ完全に返送されるまで記憶動作が完
了したとみなされない。従って、記憶の待ち時間は、無
効化がその行先へ送られるのを元のプロセッサが待機し
なくてよいプロトコルよりも相当に長いものとなる。更
に、確認は、システム帯域巾の相当の部分を消費する。
度によりしばしば生じる。「占有度」とは、コントロー
ラが要求を受け取った後に使用できなくなる時間の長さ
を示す用語である。あるプロトコルでは、直接的なコン
トローラは、メモリ位置に対応する要求を受け取ると、
その前のコマンドに対応するある確認がディレクトリに
到着するまで同じメモリ位置への他の要求に対して使用
できなくなる。コントローラは、平均より高いレートで
競合する要求を受け取る場合に、ボトルネックとなる。
又、キャッシュコヒレンスプロトコルの設計は、ハード
ウェアの複雑さにも影響する。例えば、あるプロトコル
は、停滞及び公正さの問題を招き、これらは、付加的な
機構で対処される。その結果、ハードウェアの複雑さが
増大する。
にし、広い通信帯域巾を与え、コントローラの占有度を
低くし、そして多数のプロセッサへと拡張することので
きる対称的なマルチプロセッサシステムを提供すること
が要望される。
つのプロセッサ及び共用メモリの一部分を含む多数のマ
ルチプロセッサノードがスイッチを経て互いに接続され
た対称的なマルチプロセッサシステムに効果的に使用さ
れる。本発明は、その広い形態において、請求項1、1
9及び20に記載するマルチ処理システム及び方法に係
る。以下に述べるように、マルチプロセッサノードの各
々にはディレクトリが維持される。ディレクトリは、マ
ルチプロセッサノードにおいて共用メモリの一部分の各
ブロックごとにエントリを含み、そしてブロックのコピ
ーを記憶する他のマルチプロセッサノードを指示する。
各マルチプロセッサノードは、少なくとも1つのプロセ
ッサと、マルチプロセッサノードにおけるプロセッサの
数に対応する多数のサブセットに配分されたタグ記憶装
置とを備えている。タグ記憶装置は、対応するプロセッ
サに記憶されたメモリの各ブロックごとに状態情報を記
憶する。各マルチプロセッサノードにおいて各ディレク
トリ及びタグ記憶装置に接続されたバスは、ディレクト
リに関連したデータのブロックへの参照の順序を定義す
るシリアル化ポイントを形成する。各参照は、参照の始
めに一度だけディレクトリを訪れ、データブロックのコ
ピーの位置を決定する。各参照は、ディレクトリにおい
て順序を受け取り、そして各参照は、一度だけディレク
トリをアクセスするので、データの共通ブロックへの多
数の参照が所与の時間周期中に実行される一方、データ
コヒレンス性が維持される。更に、参照がディレクトリ
をアクセスしたときに、それが首尾良く完了するよう保
証するための機構が設けられる。これらの機構を設ける
ことにより、命令の再トライ又は命令の首尾良い完了を
指示する確認を必要としない対称的なマルチ処理システ
ムが提供される。この機構は、ビクティムデータがメモ
リに書き戻されるときにそれを一時的に記憶するために
各マルチプロセッサノードに設けられたビクティムキャ
ッシュを含む。マルチ処理システムにビクティムキャッ
シュを設けることにより、メモリへの書き込みを保留す
るより多くのビクティムを記憶することができ、それ
故、メモリのコヒレンス性を維持するために個々のプロ
セッサに遅延を伴う負担をかけない。参照の首尾良い完
了を確保するのに使用される別の機構は、所与のアドレ
スに対する適当なデータバージョンが返送されるまでそ
のアドレスへの読み取りを遅延するデータ依存性ストー
ル機構である。首尾良い完了を確保しそして同じアドレ
スへの多数のトランザクションを同時に実行できるよう
にするために使用される第3の機構は、マーカー記入機
構である。各要求は、多数の段階のトランザクションを
含み、トランザクションの各段階にはそれら自身のチャ
ンネルが割り当てられる。マーカー記入機構は、要求を
発しているマルチプロセッサノード(又はプロセッサ)
に、読み取りデータに関連したディレクトリを要求がア
クセスしたこと、及びそのプロセスの読み取りデータが
その要求を発しているマルチプロセッサノードへ返送さ
れることを指示するために、1つのチャンネルに送られ
るマーカーパケットを与える。
チ処理システムは、スイッチを経て接続された複数のマ
ルチプロセッサノードを含む。複数のマルチプロセッサ
ノードの各々は、少なくとも1つのプロセッサを更に含
む。マルチプロセッサノードは、複数のブロックへと配
分される共用メモリと、この共用メモリの複数のブロッ
クに個数が対応する複数のエントリを含むディレクトリ
とを含む。ディレクトリの各エントリは、複数のマルチ
プロセッサノードのどれがデータブロックのコピーを記
憶するか識別する。ディレクトリに接続されたバスは、
複数のブロックへのアクセスを順序付けするためのシリ
アル化ポイントを形成し、複数のブロックの1つへの多
数の参照をマルチ処理システムにおいて実質的に同時に
実行できるようにする。
モリの共通ブロックへの多数の参照を同時に実行できる
ようにする方法が提供される。マルチ処理システムは、
スイッチを経て接続された複数のマルチプロセッサノー
ドを備え、複数のマルチプロセッサノードの各々は、少
なくとも1つのプロセッサと、複数のブロックへと配分
された共用メモリの一部分と、シリアル化ユニットとを
含む。シリアル化ユニットは、共用メモリの複数のブロ
ック部分に個数が対応する複数のエントリを含む。上記
方法は、共通ブロックへの全ての参照を、その共通ブロ
ックに関連したマルチプロセッサノードのシリアル化ユ
ニットにそれらが受け取られるときに順序付けする段階
を含み、各参照は実行中に一度だけシリアル化ユニット
を訪れる。更に、上記方法は、行先に記憶された共通ブ
ロックへの参照の完了を、共用メモリのブロックの所望
バージョンが行先に返送されるまで遅延する段階を含
む。
説明から明らから本発明が更に良く理解されよう。本発
明の1つの実施形態によれば、ハイアラーキー式の対称
的マルチプロセッサ(SMP)システムは、高性能スイ
ッチを経て互いに接続された多数のSMPノードを備え
ている。従って、SMPノードの各々は、SMPシステ
ムにおいてビルディングブロックとして働く。以下、1
つのSMPノードビルディングブロックの要素及び動作
を最初に説明し、その後に、SMPシステムの動作を説
明し、それに続いて、大規模のSMPシステムにおいて
メモリのコヒレンス性を維持するために使用されるキャ
ッシュコヒレンスプロトコルを説明する。
つのプロセッサモジュール12a、12b、12c及び
12dを備えている。各プロセッサモジュールは、中央
処理ユニット(CPU)を備えている。好ましい実施形
態では、デジタル・イクイップメント社で製造されたA
lpha(登録商標)21264プロセッサチップが使
用されるが、以下に述べるコヒレンスプロトコルをサポ
ートすることのできるものであれば、他の形式のプロセ
ッサチップも使用できる。マルチプロセッサノード10
は、多数のメモリモジュール13a―13dを含むメモ
リ13を備えている。このメモリは、32ギガバイトの
記憶容量を備え、4つのメモリモジュールの各々が8ギ
ガバイトを記憶する。各メモリモジュールは、多数のメ
モリブロックに分割され、各ブロックは、例えば、64
バイトのデータを含む。データは、一般に、メモリから
ブロックで検索される。
続された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
エントリのタグ記憶装置である。
憶されたデータのコヒレンス性は、デュープリケートタ
グ記憶装置(DRAG)20によって維持される。DT
AG20は、全てのプロセッサ12a―12dにより共
用され、そして4つのバンクに分割される。各バンク
は、関連するプロセッサにより使用されるデータに対応
する状態情報を専用に記憶する。DTAG、メモリ及び
IOPは、ARBバス17と称する論理バスに接続され
る。プロセッサにより発生されるメモリブロック要求
は、ローカルスイッチ15を経てARBバス17にルー
ト指定される。DTAG20及びIOP14は、プロセ
ッサ及びIOPのキャッシュにおけるブロックの状態を
ルックアップし、そしてメモリブロックに対しそれらの
状態を原子的に更新する。ARBバス17は、全てのメ
モリ参照に対してシリアル化ポイントとして働く。メモ
リ要求がARBバスに現れる順序は、プロセッサが要求
の結果を認知する順序である。
モリモジュール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ギガバイトの広い
バス帯域巾を維持しながら、種々のリソースから同時入
力を受け入れることができねばならない。
クションを取り扱うことができる。各トランザクション
は、通常、多数のリソース(メモリバンクや、データ経
路や、待ち行列のような)を使用するので、ローカルス
イッチの制御機能は非常に複雑になる。例えば、あるト
ランザクションは、そのトランザクションの段階0でメ
モリバンクを使用でき、段階1でメモリバンクからプロ
セッサポートへのデータ経路を使用でき、そして段階2
でプロセッサポートからプロセッサへのデータ経路を使
用できることを必要とする。ローカルスイッチアービタ
ー(QSA18のQSA ARB11)は、あるトラン
ザクションが開始されると、各段階でトランザクション
により必要とされるリソースが必要に応じて使用できる
ように要求を裁定する。
要求が、他の要求の進行中に長時間にわたり(潜在的に
不定に)裁定に負けることのないよう確保することによ
り、全ての要求及びプロセッサがリソースに対して公平
なアクセスを得るように保証する。例えば、3つのリソ
ースA、B及びCを要求するトランザクションTについ
て考える。このトランザクションTは、トランザクショ
ンの適当な段階に3つのリソース全部が使用できるよう
保証されるまで裁定に勝てない。リソースが使用可能で
あることのみに基づいてアービターがその判断を行う場
合には、トランザクションTは、A、B又はCの1つを
使用する(他のリソースD、E等と共に)他のトランザ
クションが裁定に勝ち続ける間は、長時間にわたって成
功しないことが考えられる。
ような非常に多数の同時要求を伴うスイッチにおいて公
平な裁定を保証するのは、計算上複雑である上に、高速
データ経路において遅延を増加し勝ちである。ここに示
す装置においては、QSAARB11が、特定のトラン
ザクションをスケジュールする前に、1つのリソース
(メモリバンク)のみについて裁定を行う。プロセッサ
に通じる待ち行列である第2のリソースは、QSA A
RB11により第1のリソースについて裁定を行うとき
に、それが使用可能であるかどうかについてチェックす
る必要がない。というのは、QSDのアーキテクチャー
がそのデータ経路を保証しそして待ち行列に通じる待ち
行列スロットが常に使用できるからである。リソースに
対する公平な裁定は、QSAARB11に著しい複雑さ
を伴うことなく与えられる。
は、対応する行先に通じるバッファに対してアップフロ
ント裁定を必要とせずに全てのリソース(プロセッサ、
メモリ、IOP及びグローバルポート)からの入力を同
時に受け取ることができる。次いで、全てのデータリソ
ースは、データ経路又はスイッチにおける待ち行列スロ
ットへのアクセスを裁定する必要なく、スイッチへデー
タを独立して送信することができる。というのは、QS
Dは、全てのリソースからのデータを実質的に同時に受
信することのできる多数の同時挿入バッファを備えてい
るからである。同時挿入バッファの2つの実施形態を以
下に説明する。
ッサ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へ転送される。
同時挿入バッファ(SIB)25a―25eを含むよう
に詳細に示されている。各SIBは、要求側要素、即ち
プロセッサ12a―12d又はIOPの1つに専用であ
る。各SIBは、それに関連した要求側要素と、ノード
内の他のリソース要素、即ちプロセッサ12a―12
d、メモリ13a―13d、IOP14及び好ましくは
グローバルポートとの間でパケットを転送するためのデ
ータ経路を制御する。グローバルポートは、他のマルチ
プロセッサノードへの相互接続部として働き、以下に詳
細に説明する。SIBは、スイッチへのアクセスに対し
要求側要素間の裁定を必要とせずに、スイッチに接続さ
れたいずれのリソースからでも要求側要素によりパケッ
トを同時に受信できるようにする。
は、スイッチ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からデータを受け
取ることができるので、その関連アービターは、接続さ
れたデータ路にデータを送信する。
ァの使用により、要求側要素とリソースとの間の裁定経
路は、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を経て受け取ら
れ、そしてグローバルポートからの入力は、グローバル
ポートラインを経て受け取られる。マルチプレクサ34
a―34hの各々からの各出力は、バッファ32の8個
のバンクの1つに接続される。各バンクは8個のエント
リを有し、各エントリは、128ビットのデータ及び1
6ビットのECCを記憶する。従って、SIBにより受
信されるデータの各パケットは、バッファ32の同じ行
において4つの異なるバンクに書き込まれる。以下に述
べるように、入力アービター36は、データを記憶する
のに使用できるバッファのバンクを指示するための状態
ビットを維持する。従って、1つ以上のリソースから1
28ビットのパケットデータが受け取られる各サイクル
ごとに、入力アービター36は、バンクの使用状態に基
づいて関連バンク32a―32hへパケットデータのサ
イクルを送信するために、各マルチプレクサ34a―3
4hにおける考えられる9個のリソース入力の1つを選
択する。又、入力アービターは、ライン36bを経てマ
ルチプレクサ30へバイパスデータも与える。入力アー
ビターの状態ビットが、全てのバンク32a―32hが
空であることを指示するときには、9個のリソース入力
の1つが入力アービター36を経て関連する要求側要素
へ直接バイパスされる。
レクサ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つのバンクにわたっ
て分散される。
1つの実施形態では、いずれの要求側要素においても保
留となり得るリソース読み取りの最大数は8であるか
ら、各書き込みサイクルの間に各リソースに対して少な
くとも1つのバンクを使用できることが確保される。そ
れ故、所与の瞬間に、全部で8個の保留の読み取り応答
がスイッチによって受け取られた場合に、バンク32a
―32hの各々を使用して、第1のパケットデータ書き
込みサイクルを受け入れることができ、バンクの選択
は、次の3つの書き込みサイクルについて回転される。
本発明の1つの実施形態では、SIBの各バッファは、
先入れ先出し(FIFO)プロトコルのもとで動作す
る。パケットの2つの部分が同時に受け取られるので、
それらに対しスイッチへ「読み込まれる」順序が選択さ
れる。リソースに対して裁定を行う要求側要素のロジッ
クは、SIBと通信せず、そしてリソースに対して裁定
するための他の要求側要素とも通信しないので、標準的
なルールに従ってデータの完全性を確保する。例えば、
リソースに固定の優先順位番号が指定される場合には、
「低い番号の入力リソースからのデータが、常に、高い
番号の入力リソースからのデータの前にスイッチに書き
込まれる」というようなルールに従う。
形態では、8個のバンクの使用について説明した。とい
うのは、要求側要素が所与の瞬間にもつことのできる保
留メモリ要求の数が8に対応するからである。しかしな
がら、設計上の制約により、それより少数のバンクを設
けることが必要な場合には、インターリーブ又は同様の
技術を使用して多数のデータチャンクを共通のバンクの
異なる位置に同時に書き込みできるように当業者によっ
て容易に設計を変更することができよう。それ故、本発
明は、図4Aに示す特定の実施形態に限定されるもので
はない。上記のように、動作中に、入力アービターは、
リソースからデータを書き込むための適当なバンクを選
択するためにバンクにおける入力の利用性に関する状態
情報を維持する。SIBへの入力を制御するための入力
アービター36の実施形態が図4Bに示されている。上
記では9個の入力リソースについて述べたが、図4Bに
は、明瞭化のために、2つのリソース入力のみの書き込
みを制御するロジックが示されている。入力パケットデ
ータがライン35を経て受け取られるときに、「入力
1」のような指示信号がラッチチェーン40に送られ、
このラッチチェーンは、4個のラッチ、フリップ―フロ
ップ又は同様の状態装置を含む。ラッチチェーン40
は、カウンタ機構として使用される。この例の目的とし
て、4つの次々のデータ転送サイクルにパケットデータ
が受け取られると仮定する。4つのデータ転送サイクル
の間に、入力信号はラッチチェーンを経て伝播する。ラ
ッチチェーンには、オアゲート46が接続される。入力
値がラッチチェーン40を経て伝播するときに、オアゲ
ート46の出力がアサートされる。
48へのシフト信号を与える。シフトレジスタは、SI
Bの各バンクについて1つづつ、8個のビット位置を含
む。シフトレジスタ48は、入力信号サンプルを最初に
受信する際に、バンク選択ロジック44からのビットベ
クトルがロードされる。バンク選択ロジック44から受
け取られたビットベクトルは、1ビットがセットされる
だけであり、ベクトル内のビットの相対的な位置が、パ
ケットデータの書き込みを開始すべきバンクを指示す
る。従って、バンク選択ロジック44は、パケットデー
タの第1サイクルの書き込み行先を制御する。バンク選
択ロジック44は、利用性ベクトル42を入力として受
け取り、利用性ベクトルにおけるビットの相対的な位置
が、書き込みデータを受け取ることのできない関連バッ
ファを指示する。
へビットを与えるときに、シフトレジスタ48の値がデ
マルチプレクサ49に送られる。又、デマルチプレクサ
49は、入力1ソースが接続されるところのマルチプレ
クサ34a―34hの入力の数値表示も入力として受け
取る。例えば、デマルチプレクサ49は、「1」のマル
チプレクサ選択値を用いてマルチプレクサ34aを経て
入力1リソースデータが送られることを指示する「1」
入力値を受け取る。選択されたバンクを指示するシフト
レジスタ内のビットの位置に基づいて、値「1」がMU
X選択<31:0>信号36aの適当な位置へ伝播され
る。各入力ソースに対する各デマルチプレクサは、全て
のMUX選択信号を駆動し、それらの出力は、これらの
信号がマルチプレクサ34a―34hを駆動する前にオ
アされる。
レジスタの内容がオアゲート50によりオアされ、利用
性バンクベクトル42として記憶される。これは、次の
サイクルの間に、どのバンクが到来する書き込みに対し
て使用できるかをバンク選択ロジック44により決定す
るために使用される。ライン46aのシフト信号がアサ
ートされる各サイクルに、シフトレジスタ48のビット
が右へシフトされる。ビットが右へシフトするときに
は、MUX選択信号<31:0>の選択値も右へシフト
され、次の書き込み動作中に入力ソースを次の隣接バン
クへ供給するようにさせる。従って、ローカルQSDス
イッチ内のSIBを使用することにより、多数の同時に
受け取られた入力がそれらの行先である要求側要素へ到
達するように確保できる簡単且つ効率的なスイッチング
機構が設けられる。このような構成では、リソースへの
アクセスに対してソースがいったん裁定されると、ソー
スにより実行されねばならない全ての裁定が完了する。
ソースは、リソースが常にスイッチバッファ32へのア
クセスを得ることができるという事実に依存する。ソー
スアービターが互いに独立して動作してリソースを管理
できることにより、最小限の複雑さで公平な裁定を確保
する機構が設けられる。更に、SIBは、要求側要素の
最大数の保留中読み取りに対してデータを記憶できるの
で、たとえ全てのリソースからデータが同時に受け取ら
れても、バッファ32に対するリソースを裁定する必要
はなく、リソースロジックの全体的な複雑さが低減され
る。
は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つの入力を受け取る。
128ビットエントリを含む。従って、各入力バッファ
は、SIBにおいて次々のサイクル中に4つの128ビ
ット部分で受け取られた1つの512ビット情報パケッ
トを記憶する。各バッファには、4対1のマルチプレク
サ64a―64hが各々接続される。これらのマルチプ
レクサ64a―64hは、関連バッファの4つの入力の
うちの1つを選択して、マルチプレクサ66を経てSI
Bの出力へ供給するのに使用される。図4Aについて上
述したように、本発明の1つの実施形態では、各要求側
要素がいかなる所与の瞬間にも異なるリソースに対して
せいぜい8個の保留中読み取り参照を有するだけである
から、8個のバッファが含まれる。従って、図5には8
個のバッファが示されているが、本発明はこれに限定さ
れるものではない。むしろ、選択されるバッファの数
は、関連するプロセッサ又はIOPデバイスのバッファ
特性に依存する。
入力が受け取られるときに、入力アービター67は、各
マルチプレクサにおける入力ラインの1つを選択し、デ
ータのパケットを空きバッファへ供給する。所与のリソ
ースからのパケット書き込みの時間中に同じバッファが
選択され、パケットの全ての部分が単一のバッファに維
持される。パケットの少なくとも1つの部分がバッファ
に書き込まれると、それがマルチプレクサ66に送ら
れ、関連する要求側要素の準備ができたときにその要求
側要素へ供給される。或いは又、いずれのバッファにも
パケットデータが存在しない場合には、マルチプレクサ
60iを経、マルチプレクサ66を経てパケットデータ
を出力へ直接的に供給することによりバイパス経路を選
択することができる。
デバイス61は、接続されたりソースの各々から実質的
に同時に(即ち、同じデータサイクルに)データを受け
取ることができる。QSDにSIBを使用することによ
り、前記の実施形態の場合のように、SIBへのアクセ
スに対し要求側要素の間に裁定は必要とされない。その
結果、リソースがローカルスイッチを使用する準備がで
きたときにローカルスイッチの利用性が保証される。更
に、本来的に公平な裁定機構が設けられる。というの
は、スイッチに対する裁定の結果としてリソースへの要
求が他のリソースへの他の要求により阻止されないから
である。従って、裁定の複雑さを最小限に抑えながら最
大のバス帯域巾を維持することのできる公平で且つ比較
的簡単な構造体が与えられる。従って、同時挿入バッフ
ァを使用して広いバス帯域巾をサポートするローカルス
イッチを実施することにより処理リソースを最適に使用
するマルチプロセッサノード10が提供される。更に、
ARBバス13において参照の順序がシリアル化される
ので、マルチプロセッサ10のメモリのコヒレンス性を
容易に維持する中央順序付けポイントが設けられる。ロ
ーカルスイッチに接続されるプロセッサモジュールの数
を増加することにより処理能力を高める可能性が存在す
るので、図2の4プロセッサ/ローカルスイッチ構成体
は、待ち時間の短いそしてコストの安い高性能のシステ
ムを提供する。
るプロセッサの数は、2つのファクタにより制限され
る。第1に、ローカルスイッチを経て互いに接続できる
プロセッサの数は、ローカルスイッチを構成するチップ
において使用できるピンの数により制限される。第2
に、単一のモノリシックスイッチによりサポートされる
データ帯域巾が制限される。従って、接続されるプロセ
ッサの数をある点を越えて増加すると、何ら性能利得が
得られないことになる。
ラーキースイッチを経て複数のマルチプロセッサノード
を相互接続することにより大型の対称的なマルチプロセ
ッサシステムを形成することができる。例えば、ハイア
ラーキースイッチを経て8個のマルチプロセッサノード
を接続して、32個のプロセッサモジュール、8個のI
OPデバイス及び256ギガバイトのメモリを含む対称
的なマルチプロセッサ(SMP)システムが形成され
る。説明上、ここでは、少なくとも2つのマルチプロセ
ッサノードを含むSMPを大型SMPと称する。以下に
詳細に述べるように、SMPノードにローカルスイッチ
を用いて少数のプロセッサを接続し、そしてハイアラー
キースイッチを用いて多数のノードを大型のSMPへと
接続することにより、拡張可能な高性能システムを実現
することができる。
スイッチ式ノードへと接続するために、マルチプロセッ
サは、グローバルなポートインターフェイスを含むよう
に拡張される。例えば、図6には、変更されたマルチプ
ロセッサノード100が示されている。図2のマルチプ
ロセッサノードと同様に、ローカルスイッチ110は、
4つのプロセッサモジュール、4つのメモリモジュール
及びIOPモジュールを接続する。図2及び6の同様の
要素は、同じ参照番号を有する。マルチプロセッサノー
ド100のローカルスイッチ110は、図2のポート1
6a―16iと同様に構成された9個のポート116a
―116iを含む10ポートスイッチである。付加的な
ポート116jは、グローバルリンク132を経てグロ
ーバルポート120へ至る全二重のクロック供給データ
リンクを形成する。
ードをハイアラーキースイッチに接続し、大型の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ギガバイト/秒の二等分データ帯域巾をスイッチ
に与える。
サノード100a―100hの各々が全システムメモリ
のアドレス可能な部分を含むか又は物理的メモリの分割
部分を含むような分散型共用メモリシステムである。本
発明の1つの実施形態では、全システムメモリに243個
の物理的アドレス位置が存在する。SMPマルチプロセ
ッサシステム100の1つの実施形態は、「大フォーマ
ット」及び「小フォーマット」と称する2つのアドレス
フォーマットをサポートする。大フォーマットは、各ノ
ードのプロセッサが動作するところの43ビットの物理
的アドレスを、マルチプロセッサシステムに使用するた
めの43ビットの物理的アドレスに直接マップする。大
フォーマットアドレスを使用すると、物理的メモリアド
レスのビット<38:36>をノード識別番号として使
用することができる。アドレスビット38:36は、メ
モリスペースアドレスのホームノードを直接デコード
し、一方、アドレスビット38:36の逆数は、I/O
スペースアドレスのホームノードをデコードし、ここで
「ホーム」とは、メモリスペース又はI/Oスペースに
関連したメモリ及びI/Oデバイスが存在するところの
物理的マルチプロセッサノードを指す。
チプロセッサシステムに4つ以下のノードが存在するこ
とを仮定するものである。小フォーマットは、各ノード
のプロセッサが36ビットの物理的にアドレスされたシ
ステムで動作できるようにする。小フォーマットにおい
て、物理的アドレスのビット34:33は、データ又は
I/Oデバイスのホームノード番号を識別する。しかし
ながら、たとえCPUが36ビットの物理的アドレスを
用いて動作しても、マルチプロセッサシステムは、デー
タ位置を特定するのに43ビットの物理的アドレスを一
貫して使用し、物理的アドレスのビット37:36がデ
ータ又はI/Oデバイスのホームノード番号を識別す
る。従って、CPUにより発生された小フォーマットア
ドレスと、データライン13a―13hを経てハイアラ
ーキースイッチ155へ送信されるものとの間で何らの
変換が実行される。
示す構成は、32個のプロセッサ間に広帯域巾のキャッ
シュコヒレントな共用メモリを与えることができる。本
発明の1つの実施形態による大型SMPの別の実施形態
が図7Bに示されており、ここでは、2つのマルチプロ
セッサノード100a及び100bがハイアラーキース
イッチを使用せずに互いに接続される。むしろ、2つの
マルチプロセッサノードは、それらのグローバルポート
出力を互いに接続することにより直接接続される。図7
Bの2ノード実施形態が使用されるか、図7Aのマルチ
ノード実施形態が使用されるかに拘わりなく、大きなア
ドレススペース及び処理能力をもつマルチプロセッサシ
ステムが得られる。
レススペース及びI/Oアドレススペースは、全てのノ
ード100a−100h間にセグメントで物理的に分配
される。システムの各ノードは、メモリスペースの物理
的アドレスの上位3ビットを使用してアクセスされるメ
インメモリの一部分を含む。従って、各メモリ又はI/
Oアドレスは、1つのノードのみにおける1つの唯一の
メモリ位置又はI/Oデバイスへとマップされる。従っ
て、上位3つのアドレスビットは、メモリ又はI/Oア
ドレスがマップされるノードである「ホーム」ノードを
識別するためのノード番号を与える。各マルチプロセッ
サノードは、それらのホームノード又は他のマルチ処理
ノードに記憶された共用メモリの部分をアクセスするこ
とができる。ホームノードがプロセッサ自身のノードで
あるところの共用メモリブロックにプロセッサがアクセ
ス(ロード又は記憶)するときには、参照は、「ローカ
ル」メモリ参照と称される。ホームノードがプロセッサ
自身のノード以外のノードであるようなブロックを参照
する場合には、参照は、「リモート」又は「グローバ
ル」メモリ参照と称する。ローカルメモリアクセスの待
ち時間は、リモートメモリアクセスの待ち時間と異なる
ので、SMPシステムは、非均一メモリアクセス(NU
MA)アーキテクチャを有すると言える。更に、システ
ムはコヒレントなキャッシュを備えているので、システ
ムは、キャッシュコヒレントなNUMAアーキテクチャ
ーと呼ばれる。
Aアーキテクチャは、高い性能と低い複雑さに寄与する
多数の特徴を含む。設計上の1つの特徴は、メッセージ
間の順序の固執及び利用である。メッセージがある順序
特性に基づいてシステムに流れるよう保証することによ
り、オペレーションの待ち時間を著しく短縮することが
できる。例えば、記憶オペレーションは、記憶が完了し
たとみなされる前に無効メッセージがそれらの最終的な
行先プロセッサに供給されることを必要とせず、むし
ろ、無効メッセージが行先プロセッサへと通じるある順
序付けされた待ち行列に入れられるや否や記憶が完了し
たとみなされる。更に、ある順序が維持されるよう保証
することにより、設計上、確認又は完了メッセージの必
要性が排除される。メッセージは、それらがある待ち行
列に入れられた順序でそれらの行先に到達するように保
証される。従って、メッセージがその行先に到達したと
きに確認を返送する必要性が排除される。これは、シス
テムの帯域巾を改善する。
「ホットポテト」オペレーションを行うのに使用され
る。ある待ち行列に順序を利用することにより、ディレ
クトリ又はDTAGコントローラのようなコントローラ
は、単一ビジットにおいて要求をリタイアすることがで
きる。他の要求との競合により要求を否定的に確認しそ
して再トライする必要はない。「ホットポテト」オペレ
ーションの結果として、公平さ及び欠乏の問題が解消さ
れる。設計に使用される第2の特徴は、仮想チャンネル
である。仮想チャンネルとは、メッセージを「チャンネ
ル」へと分類する構成であって、チャンネルは物理的な
リソースを共用する(従って、「仮想」である)が、各
チャンネルは、他のものとは独立して流れ制御される。
仮想チャンネルは、システムのメッセージ間で流れに依
存しそしてリソースに依存するサイクルを排除すること
により、キャッシュコヒレンスプロトコルにおける停滞
を排除するのに使用される。これは、選択されたメッセ
ージを否定的に確認しそしてそれに対応するコマンドを
再トライすることにより停滞を検出しそして停滞状態を
解消する機構を用いた公知のNUMAマルチプロセッサ
におけるキャッシュコヒレンスプロトコルとは対照的で
ある。
明するが、詳細な説明は後で行う。上述したように、メ
ッセージは、「チャンネル」と称する論理的なデータ路
を用いて大型SMP内をルート指定される。本発明の1
つの実施形態には、以下のチャンネルが含まれる。即
ち、要求側プロセッサから、トランザクションのアドレ
スに対応するホームノードのARBバスへトランザクシ
ョンを搬送するためのQ0チャンネルと、ホームARB
バスから1つ以上のプロセッサ及びIOPへトランザク
ションを搬送するためのQ1チャンネルと、所有者プロ
セッサから要求側プロセッサへデータ記入トランザクシ
ョンを搬送するためのQ2チャンネルとである。変更さ
れたデータを書き込むためにプロセッサからメモリへビ
クティム(Victim)トランザクションを搬送するために
Q0Vicチャンネルを設けることもできる。更に、Q
0Vicチャンネルは、ビクティムトランザクションの
背後に保持しなければならないQ0トランザクションを
搬送するのに使用できる。最後に、プロセッサからIO
PへIOスペーストランザクションを搬送するためにQ
IOチャンネルが設けられる。
ーキーを構成する。 (最低)QIO>Q0Vic>Q0>Q1>Q2(最
高) 以下に述べるように、停滞を回避するために、いずれの
チャンネルのメッセージも、下位チャンネルのメッセー
ジによって決して阻止されてはならない。順序付け特性
及び仮想チャンネルを形成しそして使用する機構の設計
及び実施に関する詳細は、後で述べる。従って、図7A
及び7Bに示すように、大型SMPは、図2のSMPノ
ードを任意の数だけ互いに接続することにより形成する
ことができる。図7A及び7Bに示すような大型SMP
システムのオペレーションは、以下に3つの部分につい
て説明する。第1に、大型SMPに含まれるハードウェ
ア要素について説明する。次いで、SMPのプロセッサ
間にコヒレントなデータ共用を与えるキャッシュコヒレ
ンスプロトコルについて説明する。更に、ハイアラーキ
ースイッチの仮想チャンネルのために設けられたサポー
ト機構を含む仮想チャンネルの実施及び使用について説
明する。
てコヒレントなデータ共用を実施するための多数の要素
が設けられる。図6に戻ると、これらの要素は、ディレ
クトリ140と、DTAG20と、IOPタグ14b
と、グローバルポート120と、ディレクトリ140と
を備えている。更に、シリアル化ポイントのハイアラー
キーは、キャッシュコヒレンスプロトコルを容易にする
ために参照の順序を維持できるようにする。これら要素
の各々について、以下に詳細に述べる。
00を、ハイアラーキースイッチリンク170を経て1
つ以上の同様に構成されたマルチプロセッサノードに直
接接続できるようにする。各ノード100は対称的なマ
ルチプロセッサシステムとして動作するので、システム
により多くのノードが追加されるにつれて、使用可能な
アドレススペース及び処理能力が増加される。図8は、
グローバルポート120の拡張ブロック図である。グロ
ーバルポートは、トランザクション追跡テーブル(TT
T)122と、ビクティムキャッシュ124と、マルチ
プロセッサノードからハイアラーキースイッチへ送られ
るパケットを記憶するためのパケット待ち行列127、
122、123及び125と、ハイアラーキースイッチ
から受け取られるパケットを記憶するためのパケット待
ち行列121とを備えている。グローバルポート120
は、ARBバス130と、ローカルスイッチの2つの専
用ポート即ちGPリンク入力132b及びGPリンク出
力132aとを経てノードの他のロジック(特にQSA
チップ)と通信する。TTTは、マルチプロセッサノー
ドにおいて保留中のトランザクション、即ちノードから
グローバルポートを経て発生されて、他のマルチプロセ
ッサノード又はハイアラーキースイッチからの応答を待
機しているトランザクションを追跡する。グローバルポ
ートにコマンドが送られるたびに、TTTにエントリが
形成される。対応する応答がノードに受け取られたとき
に、TTTエントリがクリアされる。TTTは、2つの
部分、即ちQ0TTT及びQ1TTTで構成され、Q0
及びQ1は、上記のようにQ0及びQ1チャンネルを進
むパケットを指す。エントリーがTTTにいかに割り当
てられるか及びそれがいつリタイアされるかについて
は、以下に詳細に述べる。
ムキャッシュ124を含む。ビクティムキャッシュ12
4は、マルチプロセッサノードの各プロセッサから受け
取られて別のマルチプロセッサノードのメモリに向けら
れるビクティム化データを記憶する。ビクティム化デー
タとは、プロセッサのキャッシュ位置に記憶されてその
プロセッサにより変更されたデータである。変更データ
を記憶するキャッシュ位置に記憶する必要のある新たな
データがプロセッサに受け取られると、変更データは、
ビクティム化されると言われ、ビクティムデータと称さ
れる。ビクティムキャッシュ124は、プロセッサから
リモートマルチプロセッサノードのメモリへ向けられた
ビクティムデータからのビクティムデータの一時的な記
憶装置である。グローバルポートを経て別のノードへビ
クティムデータを送信するための機会があるときには、
マルチプレクサ167は、ビクティムキャッシュ124
からバス170の出力部分にデータを供給するように切
り換えられる。グローバルポートにビクティムキャッシ
ュを設けることにより、個々のプロセッサがグローバル
システムのメモリ書き込み待ち時間を待機せずに、プロ
セッサが各々のビクティムデータバッファを空にするこ
とができる。むしろ、ビクティム書き込みは、使用でき
るデータサイクルがあるときに書き込みが実行されるよ
うにグローバルポートにより制御される。ビクティムキ
ャッシュからデータを解放する適切さに関連した幾つか
の制御の問題があるが、これらは以下に説明する。
含まれるが、これについては以下に詳細に述べる。DT
AG20は、マルチプロセッサノードのプロセッサのキ
ャッシュに記憶されたデータブロック各々に対する状態
情報を記憶する。同様に、IOタグ14aは、IOPに
記憶された各データブロックに対する状態情報を記憶す
る。ディレクトリは、どのマルチプロセッサノードがデ
ータのコピーを記憶するかを識別するおおよその情報を
与えるが、DTAG及びIOタグは、マルチプロセッサ
ノード内のどのプロセッサがデータのコピーを記憶する
かに関する正確な指示を与えるのに使用される。それ
故、DTAG及び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の各々に維
持されたタグ記憶装置と同様である。
ントリは、多数の状態ビットを含む。DTAG状態ビッ
トは、次の4つの状態、即ちInvalid(無効)、
Clean(クリーン)、Dirty Not Pro
bed、及びDirty Probedのうちの1つを
指示する。IOPタグのエントリの状態ビットは、次の
2つの状態、即ちValid(有効)及びDirty
(ダーティ)のうちの1つを指示する。「有効」ビット
は、関連キャッシュの対応エントリに記憶されたデータ
が、メモリに記憶されたデータと一致することを指示す
る。「ダーティ」ビットは、関連キャッシュの対応エン
トリに記憶されたデータが関連プロセッサによって変更
されそしてメモリに記憶されたデータに一致しないこと
を指示する。
イクロプロセッサノード100のARBバスにコマンド
が現れるたびにアクセスされる。「無効」の状態がプロ
セッサ1のDTAGアクセスに応答して返送される場合
には、ノードのプロセッサ1は、メモリアドレスに関連
したデータの有効コピーを記憶しない。「有効」の状態
がIOPタグ14aへのアクセスから返送される場合に
は、IOPキャッシュ14cがデータの有効コピーを記
憶する。「クリーン」状態がプロセッサ1に対するDT
AGアクセスに応答して返送される場合には、これは、
プロセッサ1がメモリアドレスに対応するデータの無変
更コピーを有するが、そのデータを読み取るための他の
プロセッサによる試みがなされていないことを指示す
る。Dirty Not Probedの状態がDTA
Gに応答して返送される場合には、これは、プロセッサ
1がメモリアドレスに対応するデータの変更コピーを有
し、そしてプロセッサが最後にデータを変更して以来、
少なくとも1つのプロセッサがデータを読み取る試みを
していることを指示する。
(ホームノード)におけるメモリの各ブロックの所有権
情報を与えるのに使用され、メモリのブロックは、一般
に、メモリとSMPシステムのプロセッサとの間に転送
される最小量のデータである。例えば、本発明の1つの
実施形態において、ブロックは、パケットのサイズと同
様であり、即ち512ビット(64バイト)のデータで
ある。更に、ディレクトリは、どのマルチプロセッサノ
ードがメモリデータのブロックのコピーを記憶するかを
指示する。従って、読み取り型のコマンドの場合に、デ
ィレクトリは、データの最新バージョンの位置を識別す
る。ビクティム型のコマンドの場合には、データの変更
ブロックがメモリに書き戻される場合に、ディレクトリ
は、データの変更ブロックが現在のものであってメモリ
に書き込まねばならないかどうか決定するために検討さ
れる。それ故、ディレクトリは、参照情報がリモートマ
ルチプロセッサノードのプロセッサにより発生されたも
のであるかローカルマルチプロセッサノードのプロセッ
サにより発生されたものであるかに拘わりなく、関連す
るマルチプロセッサノードのメモリブロックへの参照に
対する第1アクセスポイントである。
おいてメモリ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つ以上のノード存在
ビットがセットされる。
ディレクトリから得られる。このような場合、DTAG
からの状態情報を使用するのが好ましい。というのは、
これは非常に高速で検索されるからである。例えば、メ
モリアドレスの所有者プロセッサがそのアドレスに対し
ホームノードに配置される場合には、所有者IDを供給
するのにDTAGが使用される。性能上の理由でDTA
Gによりサービスされない情報又は参照については、デ
ィレクトリ140は、全てのコヒレンス性判断の焦点で
あり、従って、多数の機能を実行する。ディレクトリ
は、メモリデータブロックの所有者を識別する。所有者
は、プロセッサ又はメモリのいずれかである。ディレク
トリからの所有者情報は、データブロックの最新バージ
ョンのソースを決定するために読み取り型コマンド(例
えば、読み取り、読み取り―変更)により使用される。
又、所有者情報は、以下に詳細に述べるようにビクティ
ム化データをメモリに書き戻さねばならないかどうか決
定するのにも使用される。
タの所有者を識別するのに加えて、ディレクトリは、プ
ロセッサからの「クリーン―ダーティ(Clean-to-Dirt
y)」及び「シェアド―ダーティ(Shared-to-Dirty) 」コ
マンドを分析するのにも使用される。「クリーン―ダー
ティ」コマンドは、プロセッサがそのキャッシュにおい
て現在「クリーン」状態にあるキャッシュラインを変更
するよう希望するときにプロセッサにより発生される。
「シェアド―ダーティ」コマンドは、「ダーティ−シェ
アド」状態にあるキャッシュラインを変更するよう希望
するときに発生される。これらのコマンドは、ホームA
RBバスに送られ、そこで、ディレクトリは、プロセッ
サがキャッシュラインの最新バージョンを有するかどう
か決定する。もしそうであれば、コマンドは成功とな
り、プロセッサは、キャッシュラインを変更することが
許される。さもなくば、コマンドは失敗となり、プロセ
ッサは、最初に、キャッシュラインの最新バージョンを
獲得しなければならない。これらの記憶型オペレーショ
ンは、ディレクトリのノード存在情報を使用して、成功
又は失敗を決定する。
は、記憶型コマンドが発生されたときに各データブロッ
クのコピーでマルチプロセッサノードを識別する。記憶
コマンドは、キャッシュラインの内容が更新されようと
していることを指示する。関連するディレクトリエント
リの存在ビット144を検討することにより、記憶コマ
ンドがディレクトリ140に受け取られたときに、存在
ビットを有するノードを用いて、これらのマルチプロセ
ッサノードをそのノードにおけるキャッシュラインのコ
ピーで識別し、従って、各ノードにおけるキャッシュラ
インを無効化できるようにする。従って、ディレクトリ
及びDTAGは、ローカルマルチプロセッサのメモリに
おける各データブロック及びローカルプロセッサのキャ
ッシュに記憶された各データブロックに対する状態情報
を与えるように協働する。ホームノードのディレクトリ
は、キャッシュブロックのコピーの状態に関するおおよ
その情報を供給する。次いで、無効化コマンドがディレ
クトリにより識別されたノードへと進み、そこで、DT
AGがアクセスされて、コピー情報を更に改善する。従
って、これらノードにおけるDTAGは、各ノードのど
のプロセッサがそれらのキャッシュにラインのコピーを
記憶するか指示する。
ドからの保留中のトランザクション、即ち別のマルチプ
ロセッサノード又はハイアラーキースイッチからの応答
を待機している参照を追跡するのに使用される。保留中
トランザクションに関する情報は、関連メモリアドレス
へのその後のコマンドを処理する際にキャッシュコヒレ
ンスプロトコルにより使用される。図10を参照すれ
ば、TTT122の1つの実施形態は、アドレスフィー
ルド152と、コマンドフィールド154と、コマンダ
IDフィールド156と、ビット158a―158cを
含む多数の状態ビット158とを含むように示されてい
る。アドレスフィールド152は、現在進行中であるト
ランザクションに対するキャッシュラインのアドレスを
記憶し、一方、コマンドフィールドは、現在進行中であ
るトランザクションに対するキャッシュラインに関連し
たコマンドを記憶する。コマンダIDフィールド156
は、コマンドフィールドに記憶されたコマンドを開始し
たプロセッサのプロセッサ番号を記憶する。状態ビット
158は、コマンドが進行中であるときにコマンドの状
態を表わす。或いは又、状態ビット158は、進行中で
あるコマンドの種々の特性をあらわすように使用されて
もよい。
読み取り型コマンドに応答して「記入」データ応答が受
け取られたときに更新される。「シャドー」状態ビット
158bは、グローバルポートを経て発生されたコマン
ドが「シャドー」型コマンド(以下に詳細に述べる)で
ある場合にセットされる。ACK状態ビット158c
は、確認型応答を期待しているメッセージが応答を受信
した場合にセットされる。応答が到着した場合に、この
ビットはクリアされる。TTTに含むことのできる全て
の状態ビットが示されているのではないことに注意され
たい。むしろ、以下の説明に関連のある状態ビットが含
まれている。更に、メモリのコヒレンス性を維持するた
めに必要と考えられれば、他の状態ビットを設けてもよ
く、従って、本発明は、TTTにおける特定のビット指
定に限定されるものではないことが明らかであろう。
タグ及びTTTの各々は、SMPシステムにおけるキャ
ッシュラインのコヒレンス性(以下、キャッシュコヒレ
ンス性と称する)を維持するのに使用される。これら要
素の各々は、ハイアラーキースイッチ155に接続され
たマルチプロセッサノード間にコヒレント通信を与える
ためにグローバルポートとインターフェイスする。シリアル化ポイント :上記要素に加えて、各マルチプロ
セッサノードにシリアル化ポイントを設けることにより
データ共用コヒレンス性が維持される。本発明の1つの
実施形態において、各マルチプロセッサノードにおける
シリアル化ポイントは、ARBバス130である。全て
のQ0参照は、ローカルプロセッサにより発生されたも
のであるかリモートプロセッサにより発生されたもので
あるかに拘わりなく、QSAによりARBバス130を
経てディレクトリ140及びDTAG20へ供給され
る。参照がディレクトリ及び/又はDTAGをアクセス
すると、それにより得られるQ1チャンネルコマンドが
厳密な順序でARBバスに出力され、ここで、順序は参
照のシリアル化順序である。マルチプロセッサノードの
各々にシリアル化ポイントを設けることにより、SMP
において実施されるデータ共用コヒレンスプロトコルが
相当に簡単化される。
化ポイントを設けるのに加えて、ハイアラーキースイッ
チ155は、SMPシステムに第2のシリアル化ポイン
トを与える。以下に詳細に述べるように、ハイアラーキ
ースイッチは、第1のシリアル化ポイントに導入された
コヒレンス性が大型のSMPシステムに維持されるよう
確保するある順序付けルールに適合する。
チインターフェイス:図11は、8個の入力ポート15
5i0―155i7及び8個の出力ポート155o0−
155o7を含むハイアラーキースイッチ155のブロ
ック図である。ハイアラーキースイッチ155の入力ポ
ート155i0―155i7は、接続されたマルチプロ
セッサノード各々のグローバルポートからパケットを受
け取る。ハイアラーキースイッチの出力ポート155o
0−155o7は、接続されたマルチプロセッサノード
各々のグローバルポートへパケットを供給する。本発明
の1つの実施形態において、受信したパケットをバッフ
ァするためのバッファ160a―160hが各入力ポー
トに関連される。図11の実施形態は、各入力に1つの
バッファを示しているが、いかなる数の入力ポート間に
バッファが共用されてもよい。各パケットは、5つのチ
ャンネルのいずれか1つと関連される。本発明の1つの
実施形態では、以下に述べるように、各入力バッファ1
60a―160hの部分が、あるチャンネルのパケット
を専用に記憶するようにされる。従って、グローバルポ
ートからハイアラーキースイッチ155への流れ制御
は、チャンネルベースで実行される。チャンネルベース
でスイッチへのデータの流れを制御しそして入力バッフ
ァの部分を選択されたチャンネルに専用とすることによ
り、スイッチは、SMPシステムにおけるマルチプロセ
ッサノード間で停滞のない通信を行う。
アラーキースイッチ155は、更に、メモリのコヒレン
ス性を確保するためにSMPシステムの順序付け制約を
サポートするように設計される。順序付け制約は、スイ
ッチ155から関連マルチプロセッサノードのグローバ
ルポートへ送出されるパケットの順序を制御することに
より課せられる。いずれかの入力バッファ160a―1
60hからのパケットは、マルチプレクサ182a―1
82hを経ていずれかの出力ポートへ送られる。更に、
以下に述べるように、スイッチ155は、パケットをマ
ルチキャスティングすることができる。従って、1つの
入力バッファからのパケットは、いかなる数の出力ポー
トに送ることもできる。グローバル出力ポートに順序を
強制することにより、マルチプロセッサノード各々に得
られるシリアル化順序を維持して、完全にコヒレントな
データ共用機構をSMPシステムに形成することができ
る。
避 上述したように、図7Aの8個のノードの各々は、ハイ
アラーキースイッチにデータを供給し、全てのノードが
データを同時に供給することもある。パケットは、異な
る仮想チャンネルに供給される多数の異なるチャンネル
形式(Q0、Q0Vic、Q1、Q2及びQIO)に分
割され、ここで、仮想チャンネルとは、本質的に、他の
チャンネルとの共通の相互接続部を共用するがその相互
接続部のいずれかの端において独立してバッファされる
特定形式のパケットに専用のデータ経路である。各ノー
ドのグローバルポートとハイアラーキースイッチとの間
には1つのデータ経路しかないので、異なる仮想チャン
ネルからの全てのパケットは、1つのデータ経路を使用
してハイアラーキースイッチに書き込まれる。
は、ハイアラーキースイッチへデータを送信することが
できるので、全てのメッセージがスイッチにより受信さ
れて、スイッチから適当な順序で供給されるよう適切に
確保するために、ある形式の制御が必要となる。更に、
本発明の1つの目的は、対称的なマルチプロセッサシス
テムに停滞(デッドロック)が生じないよう保証するた
めに上位順序のパケット形式が下位順序のパケット形式
により阻止されないよう確保することである。本発明の
1つの実施形態では、最高順序から最低順序までのパケ
ットの順序は、Q2、Q1、Q0、Q0Vic及びQI
Oである。本発明の1つの特徴によれば、スイッチの入
力ポートに到着するパケットの流れ制御を行うための機
構であって、上記の停滞回避ルールが常に満足されるよ
う確保する機構が提供される。更に、スイッチにおいて
使用できるバッファは最適に利用されねばならず、そし
て最大の帯域巾が維持されねばならない。
ラーキースイッチへのデータの書き込みを制御するため
の制御装置は、パケットの各形式に対し、ハイアラーキ
ースイッチのバッファに専用スロットを設けることによ
り実施される。又、バッファは、任意の形式のパケット
を記憶するのに使用できる多数の一般的なスロットも含
んでいる。ハイアラーキースイッチに専用のバッファス
ロットを設けることにより、上位順序のパケット形式が
常にスイッチを通る経路を使用できるよう保証すること
によって停滞を回避することができる。更に、使用でき
る一般的スロット及び専用スロットの数を監視し、そし
てバッファに記憶されるパケットの異なる形式の数を監
視することにより、ハイアラーキースイッチのバッファ
が容量に達したときにノードがバッファに書き込みする
のを防止するような簡単な流れ制御機構を実施すること
ができる。
共通の行先バッファへの書き込みを制御するのに使用す
るための制御ロジックの一例が示されている。図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つを選択する。
ントレジスタ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形式パケットを専用に記憶する。
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であ
る。
各バッファ160a及び160bに対し、トランシット
カウント164a及び164bを各々含む。トランシッ
トカウントは、各ソースに対して、所与のデータサイク
ル中にトランシット状態であるいずれかの形式の保留中
パケットの数を維持する。所与のデータサイクル中にト
ランシット状態にあるパケットの数は、ハイアラーキー
スイッチとグローバルポートとの間の流れ制御待ち時間
に直接関係している。流れ制御信号は、ハイアラーキー
スイッチからグローバルポートへ送られて、ハイアラー
キースイッチへのデータの送信を停止するようにグロー
バルポートに通知する。流れ制御待ち時間(L)は、ハ
イアラーキースイッチによる流れ制御信号のアサート
と、グローバルポートによるデータ送信の停止との間に
生じるデータ転送サイクルの数として測定される。
ァ168a及び168bの書き込みを制御するための書
き込み制御ロジック166a及び166bも備えてい
る。この書き込み制御ロジックは、ライン168aに
「流れ制御」信号をそしてライン168bに「確認(A
CK)」信号<3:0>をアサートすることにより関連
バッファへのデータの流れを制御する。「流れ制御」及
びACK信号は、各データ転送サイクルに送信される。
上記のように、「流れ制御」信号は、接続されたグロー
バルポートによるパケットデータの送信を停止するのに
使用される。ライン168bのACK信号<3:0>
は、パケットの専用形式の各々に対して1ビットを含
み、そして接続されたグローバルポートに、その形式の
パケットが関連バッファから解放されたことを通知する
のに使用される。従って、ACK信号は、グローバルカ
ウントにより、専用カウンタ136の値を増加するのに
使用される。
可能な全ての一般的エントリが、ハイアラーキースイッ
チへのトランシット状態にある考えられる全てのパケッ
トを受け入れるのに充分でないと決定されたときに、流
れ制御をアサートする。使用可能な一般的スロットの数
は、次の式Iにより決定することができる。 式I: Generic count =(バッファサイズ)−(バッファに
使用される一般的エントリの数)−(非アサートフラグ
の数) 使用可能な一般的エントリの数が決定されると、式II
が真である場合に、流れ制御信号がアサートされる。 式II: Generic Count =(トランシットカウント) *(バッ
ファを使用するノードの数) 従って、書き込み制御ロジック166は、使用中の一般
的及び専用のスロットの数、トランシットカウント及び
全バッファサイズを監視し、「流れ制御」信号をいつア
サートすべきかを決定する。「流れ制御」信号をアサー
トしても、ソースノードのグローバルポートによる全て
の送信は停止されない。グローバルポートは、専用パケ
ット形式に対応する専用スロットがハイアラーキースイ
ッチのバッファに使用できる場合に、専用パケットデー
タをハイアラーキースイッチに常に転送する。従って、
専用カウンタにおけるいずれかの専用カウントの値がゼ
ロに等しい場合には、グローバルポートは、常に、対応
する専用パケット形式のパケットデータを転送すること
ができる。従って、バッファに専用エントリを設けるこ
とにより、ハイアラーキースイッチを通る1つの形式の
パケットの進行が、そのスイッチを通る他のパケットの
進行によって左右されないように効果的に保証される。
一般的なスロットを使用することにより、各パケット形
式ごとに最小数のスロットを指定するだけでよい。トラ
ンシット状態のパケットの数を追跡することにより、流
れ制御を微細な粒度で行うことができる。バッファの利
用性及びバスの帯域巾の両方が最大にされる。例えば、
Xの一般的スロットしか使用できないときには、流れ制
御が1サイクル放棄され、そして次のサイクルに再アサ
ートされる。その結果、Xまでのメッセージを時間周期
内に受け取ることができる。
ータを供給するためにグローバルポートにより使用され
る方法を示すフローチャートである。このプロセスは、
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の関連フラグがアサートされ
る。
は、一般的カウント及びトランシットカウントと共に使
用されて、次のデータサイクルに対する「流れ制御」信
号の状態を決定する。図13には、ハイアラーキースイ
ッチによる「流れ制御」信号のアサートを制御するため
のプロセスの一実施形態が示されている。ステップ17
5において、フラグレジスタ163aが検査されて、ゼ
ロに等しい専用カウントエントリの数が計数される。上
記のように、ゼロの数は、「流れ制御」がアサートされ
た後であってもバッファに接続された各ノードにより送
られる潜在的な専用パケットの数を指示する。従って、
図11の例においていずれのノードについても専用スロ
ットが全く使用されない場合には、フラグレジスタの全
てのエントリがゼロに等しくなり、従って、専用パケッ
トのために指定されねばならないバッファ位置が3つあ
ることを指示する。
後、ステップ176において、使用可能な全一般的スロ
ットが上記式Iを用いて決定される。次いで、ステップ
177において、各ノードのトランシットカウントが決
定される。上述したように、トランシットカウントは、
所与のデータサイクル中にグローバルポートとハイアラ
ーキースイッチとの間でトランシット状態にあるメッセ
ージの数を示す。最悪の場合のトランシットカウント
は、流れ制御の待ち時間LにバッファNを使用するノー
ドの数を乗じたものに等しい。しかしながら、本発明の
1つの実施形態によれば、トランシットカウントの決定
には、「流れ制御」信号が手前のサイクル中にアサート
されたかどうかが考慮される。上記のように、「流れ制
御」信号が手前のサイクルにアサートされた場合には、
グローバルポートとハイアラーキースイッチとの間でト
ランシット状態となるパケットはない。例えば、手前の
J個の周期中に「流れ制御」がゼロであった場合には、
JxN個までのメッセージがトランシット状態となる。
しかしながら、J−1個の手前のデータサイクル中に
「流れ制御」信号がゼロであった場合には、(J―1)
xN個のメッセージのみがトランシット状態となる。
ース(グローバルポート)と行先(ハイアラーキースイ
ッチ)との間の全待ち時間を検査すると共に、手前のデ
ータサイクルにおけるソースと行先との間の相互作用を
検査することにより、トランシット状態のパケットの数
がインテリジェントに決定される。各ノードに対するト
ランシットカウントが決定された後に、ステップ178
において、上記の式IIを用いて保留中の専用パケット
及びトランシット状態のパケットを受け入れるに充分な
使用可能な一般的エントリがバッファにあるかどうかの
判断がなされる。使用可能な一般的パケットの全数が、
トランシット状態にあるパケットの数にバッファを共用
するノードの数を乗じた値より少ない場合には、ステッ
プ178において、「流れ制御」信号がグローバルポー
ト120aにアサートされ、ハイアラーキースイッチ1
55へのデータの供給が阻止される。しかしながら、全
カウントが、潜在的に受け取られるパケットの数をバッ
ファ160aで受け入れできることを指示する場合に
は、「流れ制御」信号がアサートされず、プロセスは、
次のデータサイクルのためにステップ175へ復帰す
る。
ジの数と、流れ制御信号がアサートされた手前のサイク
ルの数とを追跡することにより、流れ制御は、グローバ
ルポートをハイアラーキースイッチに接続するデータリ
ンクの利用性が最大となるよう確保するように微同調さ
れる。 図11ないし13に示すバッファ書き込み制御
ロジック及び方法は、ノードからハイアラーキースイッ
チへのデータの送信に関して説明したが、本発明は、こ
のような構成に限定されるものではないことに注意され
たい。むしろ、本発明の1つの実施形態は、共通の受信
器に信号供給する多数のソースがありそして停滞を回避
する必要があるいかなる環境にも使用できる。
イアラーキースイッチの機構:ハイアラーキースイッチ
からのデータの読み取りは、本質的に、パケットの順序
と、パケット間のデータ依存性との両方が維持されるよ
うに入力バッファから多数の出力ソースへデータを供給
することを含む。上述したように、パケットは種々のチ
ャンネルに供給される。異なるチャンネルにおいてパケ
ットに関連するのは、ある順序付け制約即ち依存性であ
る。本発明の1つの実施形態では、1つの順序付け制約
は、Q1チャンネルの全てのパケットが順序正しく維持
されることである。別のパケット順序付け依存性は、優
先順位の高いチャンネルを進行するパケットが、優先順
位の低いチャンネルを進行するパケットによって阻止さ
れてはならないことであり、チャンネルの優先順位は、
最も高いものから最も低いものへ、Q2、Q1、Q0、
Q0Vic及びQIOである。順序の維持は、以下に述
べる種々の技術を用いてSMP全体にわたり達成され
る。ハイアラーキースイッチにおいては、データ依存性
及びQ1チャンネル順序付けを満足するよう確保するた
めに3つの基本的なガイドラインに従う。これらのガイ
ドラインは、次の通りである。
イッチ入力ポートに受け取られた多数のQ1パケットが
共通の出力ポートをターゲットとする場合には、Q1パ
ケットは、それらが入力ポートに現れたのと同じ順序で
出力ポートに現れる。 ガイドライン2:ハイアラーキースイッチにおいて多数
の入力ポートからのQ1パケットが共通の出力ポートへ
マルチキャスティングされるときには、Q1パケット
は、それらがターゲットとする全ての出力ポートに同じ
順序で現れる。 ガイドライン3:ハイアラーキースイッチの多数の入力
ポートからのQ1パケットの順序付けリストが多数の出
力ポートをターゲットとするときには、Q1パケット
は、全ての到来するQ1パケットの単一の共通の順序付
けに合致するように出力ポートに現れる。各出力ポート
は、共通の順序付けリストにおける幾つかの又は全ての
パケットを送信することができる。
序を維持するのに加えて、スイッチから出力されるパケ
ットを、アドレス及びデータバスの性能が完全に実現さ
れるように順序付けすることも望まれる。例えば、図1
4は、HSリンク170のアドレス及びデータバス構造
の利用を示すタイミング図である。HSリンク170
は、2対の単一方向性アドレス及びデータバスによりマ
ルチプロセッサノード100の各々に接続される。デー
タバスは、512ビットのデータパケットを搬送し、そ
してアドレスバスは、80ビットのアドレスパケットを
搬送する。データパケットの送信は、アドレスパケット
の送信の2倍のサイクル数を必要とする。書き込みコマ
ンドのようなあるコマンドは、アドレス及びデータパケ
ットの両方を含む。例えば、図14において、アドレス
パケット179aは、データパケット179dに対応す
る。各コマンドがアドレス及びデータパケットの両方を
含む場合には、アドレスバスの1つおきのアドレススロ
ットがアイドル状態となる。しかしながら、読み取りコ
マンドのような多数のコマンドは、アドレスパケットし
か含まず、データパケットを転送するためのデータバス
のスロットを必要としない。従って、全体的なシステム
性能を向上するためには、データ部分及びアドレス部分
の両方が「パック」され、即ちHSリンクのアドレス及
びデータ部分の各考えられるタイムスロットにアドレス
及びデータが存在するような順序でバスから送出すべき
パケットを選択するスイッチを有するのが好ましい。ア
ドレス及びデータがHSリンクにおいて「パック」され
るときには、HSリンクが最適に利用される。
データを同時に受け取りそして多数の出力ポートを経て
多数の行先へデータを供給できる一方、データ依存性を
満足し、システム順序を維持し、そしてデータ転送レー
トを最大にすることのできるハイアラーキースイッチを
実施するための種々の実施形態が提供される。これらの
種々の実施形態を、図15ないし18を参照して説明す
る。図15には、上記順序付け制約を実施することので
きるスイッチ181の1つの実施形態が示されている。
図11について述べたように、スイッチ155は、複数
のバッファ160a―160hを含む。入力バッファの
各々は、1書き込みポート/8読み取りポートバッファ
であり、8個の各入力の1つからパケットを受け取るよ
うに接続される。又、スイッチは、8個の出力ポートも
含むが、1つの出力ポート、即ち出力ポート<0>のみ
に対するロジックが示されている。残りの出力ポートに
対するロジックも同様であり、明瞭化のために、ここで
は詳細に述べない。
の各エントリは、バッファのエントリに記憶されるパケ
ットのチャンネルを識別するチャンネルフィールド18
5を含む。更に、各エントリは、一連のリンクインデッ
クス186を含む。各リンクインデックスは、入力バッ
ファ160a―160hのエントリの1つに対するイン
デックスである。これらのリンクインデックスは、パケ
ット順序付け制約に基づきバッファ160aから同じチ
ャンネルを経て次々のパケットをアクセスするためのリ
ンクリストアドレス構造体を形成するのに使用される。
3つのリンクインデックスL1、L2及びL3が各エン
トリと共に含まれ、各リンクインデックスは、3つまで
の順序付けリストの1つにおけるエントリの位置を識別
する。又、各エントリは、依存性フラグ189も含む。
依存性フラグは、チャンネル間の依存性をマークするの
に使用される。依存性フラグF1は、対応するエントリ
のパケットがQ1、QIO又はQ0Vicチャンネルを
進行するパケットである場合にセットされる。依存性フ
ラグF2は、対応するエントリのパケットがQ0又はQ
0Vicチャンネルを進行するパケットである場合にセ
ットされる。依存性フラグは、パケットの処理順序を次
のように維持する上で助けとなる。
ャンネル待ち行列、合成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がアサートされる。チャンネル
の形式及び依存性フラグが検査されて、チャンネル依存
性を満足するように出力すべきバッファの適当なエント
リが選択される。
々の各エントリは、マルチプレクサ182へ送られる。
マルチプレクサ182は、マネージャー180からの選
択信号に応答して入力バッファの1つからパケットの1
つを選択する。マネージャー180は、入力バッファ1
60a―160hの64個の考えられる読み取りポート
からのエントリを関連出力ポートの出力として選択す
る。マネージャー180は、全体的なシステム順序及び
チャンネル依存性が満足されるようにパケットを選択す
る。入力バッファ160a―160hの1つにパケット
が受け取られるときには、エントリのチャンネルフィー
ルドにチャンネル形式が書き込まれ、そしてそのエント
リの関連フラグがフラグフィールド189においてアサ
ートされる。上述したように、入力バッファの各エント
リごとに、3つのリンクインデックスがあり、その各々
は、3つの順序付けされた待ち行列の1つに対応する。
本発明の1つの実施形態では、パケットを3つの異なる
出力ポートにマルチキャスティングするために多数のリ
ンクインデックスが使用される。マルチキャスティング
されるべきパケットが入力バッファに記憶されるときに
は、それが2つ以上のリンクされたリストに入れられ、
リンクされたリストの各々は、異なる出力ポートに対応
する。その結果、異なる出力ポートに関連する出力マネ
ージャーは、各々、異なるリンクリストインデックスを
用いて同じ入力バッファエントリにアクセスすることが
できる。
は、バッファ160a―160hにおいて対応する形式
の次のパケットをアドレスするためのバッファインデッ
クス値である。従って、リンクインデックス値は、対応
する形式のその後のパケットがバッファに書き込まれる
まで書き込まれない。その後のパケットがバッファに書
き込まれるときには、その後のパケットのアドレスが手
前のパケットのリンクインデックスに書き込まれ、これ
により、そのチャンネル形式の次のパケットのインデッ
クスを与える。各エントリは、3つの考えられるリンク
インデックスフィールドを含むので、手前のエントリに
アドレスを書き込むのに加えて、2ビットフィールド
(図示せず)がアドレスと共に記憶され、順序付けリス
トを構成するために3つのリンクインデックスの適当な
1つをエントリで識別できるようにする。
するためにバッファ160a―160hのパケットの1
つを次のように選択する。上述したように、ヘッドポイ
ンタ187a―187eは、各待ち行列の最上部に対応
するバッファインデックスを記憶する。所与のチャンネ
ルに対するパケットを処理するときに、マネージャー
は、対応するヘッドポインタにより指示されたエントリ
を選択する。1つ以上のフラグ189がセットされ、そ
して高い優先順位のチャンネルに関連した待ち行列のパ
ケットが処理されていない場合には、パケットは、その
待ち行列内のより優先順位の高い全ての手前のパケット
が処理されるまで処理されない。例えば、出力マネージ
ャーがQ0形式のパケットを処理する場合に、Q1/Q
IO/Q0Vic及びQ0/Q0Vicヘッドポインタ
で指示されたエントリを検査する。パケットがQ0チャ
ンネルパケットであるが、Q1パケットの処理がまだ完
了していない場合には、エントリは処理されない。パケ
ットの処理は、チャンネルQ1又はQ0パケットが既に
処理されたことを指示する処理フラグ(図示せず)を各
フラグF1及びF2と共に与えることにより指示され
る。高い優先順位のチャンネルを有する待ち行列におけ
る全てのパケットの処理が行われると(処理フラグによ
り指示される)、そのエントリに関連したパケットは自
由に処理される。
と、マネージャーは、そのエントリが存在する待ち行列
に関連したヘッドポインタをバッファインデックスとし
て選択する。バッファインデックスはマルチプレクサ1
82へ送られ、そしてバッファエントリが出力ポートへ
送られる。リンクインデックスはヘッドポインタへ返送
され、そしてヘッドリストポインタがその待ち行列の次
のパケットのバッファインデックスで更新される。従っ
て、図15のスイッチ実施形態は、リンクリストデータ
構造体、順序付けされた待ち行列及びフラグを用いて、
出力ポートへパケットを与え、全体的なシステム順序が
維持されるようにする。更に、多数のリンクインデック
スを含むリンクリストデータ構造体は、マルチキャすと
パケット順序付けルールに固執しながらパケットをマル
チキャスティングするための簡単な機構を形成する。
順序付けされた待ち行列を使用して、チャンネルの順序
が維持されるようにする。図16には、所定の順序依存
性に基づいて出力データを与えることのできるスイッチ
の第2の実施形態が示されている。図16の実施形態で
は、スイッチの各出力ポートに対してバッファ200が
設けられる。バッファ200は、入力パケット受信経路
201を経てバッファ160a―160h(図11)の
各々から入力を受け取るように接続され、入力バッファ
からのパケットは、パケットの行先に基づいて出力ポー
トの適当なバッファへ送られる。本発明の1つの実施形
態では、バッファは、コラップス(collapsing)FIFO
として実施されるが、当業者に知られた他のバッファア
ーキテクチャxを使用することもできる。
るべき種々のパケットを記憶するように示されている。
バッファ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の動作
を容易に説明するために、一般的パケット及び依存性が
与えられる。
チの入力バッファ160a―160hの各々に正しい順
序で受け取られ、そしてそのパケットにより指示された
行先に基づいて、バッファ200のような出力バッファ
に正しい順序で供給される。各出力バッファの各パケッ
トエントリ、例えば、エントリ200aは、パケットの
送信及び受信ノードを指示するソース及び行先フィール
ドと、パケットが送信されるチャンネルを指示するチャ
ンネルフィールドと、一連のビット206a−206e
とを備えている。一連のビット206a―206eは、
ハイアラーキースイッチを経てパケットを供給する各チ
ャンネルごとに1ビットを含む。例えば、図16の実施
形態では、一連のビットは、チャンネルQ0、Q1、Q
2、Q3及びQ4の各々について1ビットを含む。出力
ポートに対して入力パケット受信経路に接続された書き
込み制御ロジック205は、受信パケットのチャンネル
に基づくと共に、図16Aの流れ依存性図に示されたチ
ャンネル間の依存性に基づいて一連のビットの各々の設
定を制御する。又、以下に詳細に述べるように、書き込
み制御ロジックは、静的又は動的に依存性を確認するこ
とによりビットを更新することができる。依存性を静的
に確認するときには、チャンネルに対して定められた依
存性が、バッファ内の他のパケットに拘わりなく適用さ
れる。依存性を動的に確認するときには、チャンネルの
依存性が、バッファ200内の他のパケットのチャンネ
ル及びアドレス行先を考慮して適用される。
エンジン208a―208eが接続される。各サーチエ
ンジンは、ビットの関連列をサーチして、列セットの対
応ビットを有するバッファ200のエントリを選択す
る。選択されたエントリは、各列(又はチャンネル)ご
とに、一連の信号S4―S0により出力バッファマネー
ジャー202へ指示される。チャンネル間の既知のデー
タ依存性に関連してサーチエンジンの各々により受信さ
れた選択信号を用いて、出力バッファマネージャーは、
グローバルポート出力に供給するために出力バッファ2
00からのパケットの1つを選択する。動作中に、入力
パケット受信経路201を経てパケットが受信されると
きに、パケットのチャンネルは、書き込み制御ロジック
205により評価され、そして一連のビット206a―
206eのうちの、そのチャンネルに対応するビットが
アサートされる。図16において、パケットの形式を指
示するためにセットされたビットは、「丸内のX印」で
示され、そしてこれはチャンネル識別子フラグと称す
る。従って、図16では、パケット1がQ3形式のパケ
ットである。図15の実施形態によれば、エントリのチ
ャンネルを指示するビットをアサートするのに加えて、
そのチャンネルのパケットがプッシュするところの各チ
ャンネルに対してビットが付加的にアサートされる。こ
れらビットの各々は、依存性フラグと称され、図16に
「X」で示されている。それ故、Q0チャンネルパケッ
トであるパケット2の場合に、Q3チャンネルパケット
に関連したビットが付加的にアサートされる。というの
は、図16Aの流れ図に示されるように、Q0パケット
がQ3パケットをプッシュするからである。
してそれらの関連する一連のビット206a―206e
がアサートされるときには、ビットの各列に関連したサ
ーチエンジン208a―208eの各々が、ビットセッ
トを有するバッファ内の第1エントリを選択する。それ
故、サーチエンジン208aの選択値は、パケット2を
指し、サーチエンジン208bの選択値は、パケット3
を指し、等々となる。S0―S4信号は、マネージャー
202に送られる。マネージャー202は、サーチエン
ジンによる選択信号のアサートに応答するのに加えて、
システムに存在する依存性に応答して、パケットの1つ
を選択する。例えば、本発明の1つの実施形態によれ
ば、チャンネルQ0にあるパケット2のようなパケット
は、チャンネルQ0のサーチエンジン(208a)及び
チャンネルQ3のサーチエンジン(208d)の両方が
同じパケットを選択しない限り、スイッチから送出され
ない。従って、多数のフラグが所与のパケットに対して
セットされたときに、マネージャー202は、セットさ
れたフラグに対応するサーチエンジンの両方がその所与
のパケットを選択しない限り、出力に対してそのパケッ
トを選択しない。
ンジンが、その依存性フラグがセットされたためにエン
トリを選択した場合に、サーチエンジンは、依存性フラ
グをクリアしそしてバッファを下方に進んで、依存性フ
ラグ又は認識フラグがセットされた次のエントリを選択
することができる。このような構成では、サーチエンジ
ンが他のチャンネルによりストールされて処理を保留に
することがないので、パケットの処理が改善される。依
存性を識別するために多数のフラグをアサートする作用
は、パケットがスイッチを経て伝播するときにパケット
の全体的なシステム順序を維持する上で助けとなる。例
えば、図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を指さ
ない。その結果、所与のチャンネルのパケットによりプ
ッシュされた各パケットごとにビットをアサートするこ
とにより、所与のチャンネルによりプッシュされたパケ
ットが処理されるまでチャンネルが効果的に阻止され
る。その結果、全体的なシステム順序が維持される。
ックは、静的又は動的な依存性を確認するように動作さ
れる。静的な依存性とは、図16Aの流れ図で示された
ような依存性である。動的な依存性は、バッファ内の2
つのパケット間に静的な依存性が実際に存在するかどう
かを決定するためにバッファの内容を評価することによ
り確認される。静的な依存性は、メモリデータがSMP
においてコヒレンス性を失わないよう確保する順序付け
ルールを形成するのに使用される。しかしながら、デー
タのコヒレンス性は、パケットがメモリデータの同じブ
ロックをアクセスする場合にしか影響されない。それ
故、動的な依存性は、バッファに既にあるパケットの行
先アドレスを検査することによってバッファの内容を微
細な粒度で検査して、異なるチャンネルの2つのパケッ
ト間に依存性が実際に存在するかどうか決定する。
動的に確認する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と同じメモリブロ
ックをアクセスする場合だけアサートされる。従って、
依存性を動的に確認することにより、全体的なシステム
性能を向上しながらメモリコヒレンス性を維持すること
ができる。
しながら、多数の入力ソースから受け取ったデータを多
数の出力ソースへ出力する方法の別の実施形態が示され
ている。図18の実施形態は、図16の場合と同様の要
素を含むように示されている。しかしながら、図18の
書き込み制御ロジック209は、パケットの依存性を異
なるやり方で分析することにより一連のビット206a
―206eの各々を更新する。図16の場合のように、
パケットが関連チャンネルのものであることを指示する
ために、一連のビットの1つが各パケットごとにセット
される。しかしながら、チャンネルがプッシュするとこ
ろのチャンネルの全てのパケットに対して付加的なビッ
トをセットするのではなく、そのチャンネルのパケット
をプッシュするところのチャンネルのパケットに対して
ビットがセットされる。
識別フラグをセットするのに加えて、そのパケットによ
りマスク又は阻止された全てのチャンネルに対して付加
的なビットがセットされる。例えば、図18の例におい
て、パケット1は、Q3チャンネルパケットである。Q
3チャンネルのパケットは、図18Aの依存性流れ図に
示すようにQ3パケットが実行されるまで、Q1及びQ
0パケットの実行を阻止する。従って、ビット206
d、206b及び206aがパケット1に対してセット
される。しかしながら、パケット2は、他のパケットの
実行を阻止しないQ0パケットである。その結果、ビッ
ト206bのみがパケット2に対してセットされる。従
って、図18のスイッチ実施形態は、依存性を静的に確
認することによりシステム順序を維持しながら出力ポー
トへデータを供給する別の方法を提供する。図18のバ
ッファ実施形態は、依存性を動的に確認するようには使
用できないことに注意されたい。というのは、そのよう
にするには、データがバッファ200に書き込まれる前
にデータのアドレスを知る必要があるからである。しか
しながら、ここに述べる静的及び動的な方法は、全て、
パケット間の依存性を満足するよう確保するために使用
できる。
ースからデータを同時に受け取りそして多数の出力ポー
トを経て多数の行先へデータを供給できる一方、データ
依存性を満足し、システム順序を維持し、そしてデータ
転送レートを最大にすることのできるスイッチの3つの
実施形態が説明された。1つの実施形態では、フラグを
記憶する多数の待ち行列の使用により順序付け依存性が
達成されそして依存性を識別するように待ち行列が選択
されるリンクリストバッファ機構が説明された。第2お
よび第3の実施形態では、スイッチの入力バッファから
データを正しい順序で受け取る出力バッファが、ある形
式のパケットを阻止するのに使用される一連のビットを
備えていて、データ依存性及びコヒレンス性制約を満足
するように確保する。全ての実施形態において、潜在的
な依存性の競合をマークするためにセットされるフラグ
を含む順序付け待ち行列の使用により、順序付け依存性
が追跡される。フラグの順序付けリストを用いて依存性
を識別することにより、バスの利用性を最大にしながら
順序を維持し且つコヒレンス性を確保するためにマネー
ジャーにより実行されるオペレーションの複雑さが簡単
化される。
プロトコルは、書き込み無効化所有権をベースとするプ
ロトコルである。「書き込み無効化」とは、プロセッサ
がキャッシュラインを変更するときに、他のプロセッサ
キャッシュにおける効力のないコピーを無効化すること
を意味し、新たな値でそれらを更新するのではない。こ
のプロトコルは、システム内のメモリであるかプロセッ
サ又はIOPの1つであるかに拘わりなくキャッシュラ
インに対する識別可能な所有者が常に存在するので、
「所有権プロトコル」と称される。キャッシュラインの
所有者は、必要なときにキャッシュラインの最新の値を
供給する責任がある。プロセッサ/IOPは、キャッシ
ュラインを「独占的に」又は「共用して」所有すること
ができる。プロセッサがキャッシュラインの独占的所有
権を有する場合には、システムに通知せずにそれを更新
することができる。さもなくば、システムに通知し、そ
して他のプロセッサ/IOPキャッシュのコピーを潜在
的に無効化しなければならない。
説明に入る前に、ハイアラーキーネットワークに使用さ
れる全通信手順について最初に説明する。図7Aについ
て述べたように、大型のSMPシステム150は、スイ
ッチ155を経て互いに接続された多数のノードを含
む。各ノードにおける各プロセッサは、メモリのデータ
にアクセスするコマンドを発生する。これらのコマンド
は、ソースノード内で完全に処理することもできるし、
又はアドレス及び要求の形式に基づいてシステムの他の
ノードへ送信することもできる。アドレススペースは、
メモリスペース及びIOスペースに分けられる。プロセ
ッサ及びIOPは、専用キャッシュを使用して、メモリ
スペースアドレスのみに対するデータを記憶し、そして
IOスペースデータは、専用キャッシュには記憶されな
い。従って、キャッシュコヒレンスプロトコルは、メモ
リスペースコマンドのみに関連している。
要素は、ロード及び記憶動作をシリアル化する解決策で
ある。キャッシュコヒレンスプロトコルは、各メモリア
ドレスXへの全てのロード及び記憶に順序を課さねばな
らない。この順序は、Xへの全ての「記憶」が順序付け
されるものであり、即ち、第1記憶、第2記憶、第3記
憶、等々とならねばならない。第i番目の記憶は、(I
―1)番目の記憶により決定されたようにキャッシュラ
インを更新する。更に、各ロードには最新の記憶が関連
され、そこからロードはキャッシュラインの値を得る。
この順序をここでは「ロード―記憶シリアル化順序」と
称する。ここに述べるプロトコルの特性は、アドレスX
に対するホームARBバスが、Xへの全てのロード及び
記憶に対する「シリアル化ポイント」であることであ
る。即ち、Xへの要求がXのホームARBバスに到着す
る順序は、対応するロード及び記憶がシリアル化される
順序である。大型の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の後に現れる。
ドレスへの全ての要求に対し「シリアル化ポイント」と
定義される。各メモリアドレスXに対し、対応する要求
(RdMod又はCTD)がホームARBバスに到着す
る順序で記憶が見掛け上実行される。アドレスXへのロ
ードは、ホームARBにおいて最後にシリアル化された
記憶Xに対応するXのバージョンを得る。 以下に述べ
るキャッシュコヒレンスプロトコルの前書きにおいて、
「システム」という用語は、プロセッサ及びIOPを除
く大型SMPの全ての要素を指す。プロセッサ及びシス
テムは、「コマンドパケット」又は単に「コマンド」を
送信することにより互いに対話する。コマンドは、要
求、調査及び応答の3つの形式に分類される。プロセッ
サによりシステムに発生されるコマンド及びシステムに
よりプロセッサに発生されるコマンドは、所与のプロセ
ッサのメモリシステムインターフェイスに基づく。SM
Pの動作を説明する目的上、デジタル・イクイップメン
ト・コーポレーションからのAlpha(登録商標)シ
ステムインターフェイスの定義に基づいて発生される要
求及びコマンドについて説明するが、他の形式のプロセ
ッサも使用できることを理解されたい。
果として、データのコピーを得なければならないときに
プロセッサにより発生されるコマンドである。又、要求
は、システムからのデータの断片に対して独占的な所有
権を得るのにも使用される。要求は、読み取りコマン
ド、読み取り/変更(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に応答し
て、ダーティキャッシュラインがシステムに返送され、
そしてキャッシュに記憶されたダーティコピーが無効化
される。キャッシュラインを別のプロセッサにより更新
すべきときには、キャッシュラインのコピーをキャッシ
ュに記憶しているプロセッサに、システムにより無効化
コマンドが発生される。
タ又は要求に対応する確認を搬送するシステムからプロ
セッサ/IOPへのコマンドである。読み取り及びRd
Modコマンドの場合に、応答は、各々要求されたデー
タを搬送するFill又はFillModコマンドであ
る。CTDコマンドの場合に、応答は、CTDの成功又
は失敗を指示するCTD成功又はCTD失敗コマンドで
ある。ビクティムコマンドの場合には、応答がビクティ
ム―リリースコマンドである。図19には、要求と要求
との間の関係、及び個々のプロセッサにおける対応キャ
ッシュラインの状態を説明するためのテーブルが示され
ている。又、図19は、キャッシュラインの要求及び状
態の各々に対して得られる調査形式のコマンドも示して
いる。カラム300及び300aは、プロセッサにより
発生される要求を示し、カラム305及び305aは、
システムの他のプロセッサにおけるキャッシュの状態を
示し、そしてカラム320及び320aは、システムに
より発生される調査コマンドを示す。
るプロセッサがシステムに要求を発生することを仮定し
ている。プロセッサAのコマンドは、次いで、プロセッ
サBと称する1つ以上の他のプロセッサと相互作用す
る。プロセッサAによりアドレスされるキャッシュライ
ンが、DTAG及び/又はディレクトリ情報を用いて決
定されたプロセッサBのキャッシュに記憶される場合に
は、プロセッサBのキャッシュ状態が、プロセッサBへ
調査コマンドを発生する必要があるかどうか及びどんな
形式の調査コマンドを発生すべきかを決定する。以下、
コヒレンスプロトコル及び機構について詳細に述べる。
コマンドパケットがとる経路、各コマンド形式に対する
状態情報のソース、及びそれにより生じるアクションが
含まれる。全てのコマンドは、プロセッサ又はIOPか
ら発生され、IOPの発生プロセッサは「ソースプロセ
ッサ」と称する。要求に含まれるアドレスは、「要求ア
ドレス」と称する。アドレスの「ホームノード」は、そ
のアドレススペースが要求アドレスをマップするところ
のノードである。要求は、ソースプロセッサが要求アド
レスのホームノードである場合は「ローカル」と称し、
さもなくば、「グローバル」要求と称する。ホームノー
ドのARBバスは、「ホームARBバス」と称する。
「ホームディレクトリ」は、要求アドレスに対応するデ
ィレクトリである。従って、ホームディレクトリ及びメ
モリは、要求アドレスに対するホームARBバスに接続
される。
リ要求は、先ず、ホームARBバスにルート指定され
る。この要求は、それがローカルである場合にはローカ
ルスイッチを経てルート指定され、それがグローバルで
ある場合にはハイアラーキースイッチを経て送られる。
後者の場合には、ローカルスイッチ及びGPリンクを横
断してGPに達し、次いで、HSリンクを経てハイアラ
ーキースイッチへ至り、次いで、GP及びホームノード
のローカルスイッチを経てホームARBバスへ至る。グ
ローバル要求は、ソースノードのARBバスに最初に現
れず、むしろ、GPリンクを経てHSに直接ルート指定
されることに注意されたい。公知のプロトコルでは、グ
ローバル要求は、それが別のノードへ送出される前にソ
ースノードの状態をアクセスする。本発明は、グローバ
ル要求をHSへ直接発生することによりグローバル要求
の平均待ち時間を短縮する。図20A―20Jは、多数
の基本的なメモリトランザクションを例示するフローチ
ャートである。
ースプロセッサ320からホームARBバスへ要求が送
られる。ディレクトリ322は、どのプロセッサがメモ
リブロックを所有するか決定する。ローカルメモリ32
3が所有者である場合には、「短い記入」コマンドがホ
ームARBバスからソースプロセッサ320へ発生され
る。グローバル読み取り :図20Bにおいて、ノード325
のプロセッサ320が、「ホーム」がノード326にあ
るメモリのキャッシュラインへ読み取りを発生すると仮
定する。(グローバル)読み取りコマンドは、ライン3
27で示された経路を経てスイッチ324を通り「ホー
ム」ARBバス及びディレクトリ321へルート指定さ
れる。ノード326のメモリ330がキャッシュライン
の所有者である場合には、「短い記入応答」を発生する
ノード326によりノード326からノード325へデ
ータが返送される。
Pにより現在所有されている場合には、要求されたキャ
ッシュラインを得るために異なるステップが取られる。
図20Cを参照すれば、プロセッサ320が、「ホー
ム」がノード326にあるメモリのキャッシュラインへ
読み取りを発生する場合には、読み取りは、再び、経路
327を経てホームARBバス及びディレクトリ321
へルート指定される。ディレクトリ321のエントリ
は、上述したように、メモリの各キャッシュラインに対
し、所有者情報を含む14ビットの状態情報を備えてい
る。所有者情報は、この場合に、所有者をノード328
におけるプロセッサ342として識別する。ノード32
8が要求されたキャッシュラインを所有するというディ
レクトリの指示に応答して、2つの事象が生じる。第1
に、「ホーム」ノードであるノード326は、ライン3
29で示すように、所有者プロセッサ342へ「送信読
み取り」調査を発生する。同時に、ホームノード326
は、ライン331で示すように、プロセッサ320へ
「記入マーカー」応答を送信する。「記入マーカー」応
答の役割は、以下で説明する。
342は、「記入」コマンドをプロセッサ320へ発生
し、「記入」コマンドは、当該キャッシュラインを含
む。「読み取り」要求に対するこの形式の応答は、デー
タ返送に対して一連の3つのコマンドを必要とするの
で、「長い記入」と称される。従って、「読み取り」ト
ランザクションは、メモリからの応答である「短い記
入」と、所有者プロセッサからの応答である「長い記
入」の2つの形式に分割することができる。
ば、ローカル読み取り変更トランザクションは、(1)
キャッシュラインの現在バージョンのコピーを得ている
全てのプロセッサに無効化調査が送られ、そして(2)
FRMod及びFillModsが、Frds及びFi
llsに代わって所有者に送られる点を除くと、ローカ
ル読み取りトランザクションと同様に働くことが明らか
である。 図20D図において、ホームノードのディレ
クトリは、ローカルプロセッサ又はメモリがブロックを
所有することを示す。ホームARBバスにおいて、ディ
レクトリ322は、ブロックの現在バージョンを得てい
る全ての外部ノードを識別する。無効化コマンドは、H
S324へ送られ、全ての当該ノードはマルチキャスト
ベクトルで識別される。HSは、ベクトルで識別された
全てのノードへ無効化メッセージをマルチキャストす
る。無効化メッセージは、各ノードにおいてARBバス
へ進み、そこで、DTAGは、それらを更にフィルタ
し、キャッシュラインの現在バージョンを有すると識別
されたプロセッサ又はIOPのみへ無効化調査を送信す
る。
れば、読み取り変更トランザクションは、図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は「無効化」調査も受
け取る。
ッサが所有者である場合には、ホームノードは、「記入
変更マーカー」、「送信読み取り変更」及びゼロ以上の
「無効化」を1つのコマンドとして発生する。スイッチ
において、コマンドは、全ての行先ノードにマルチキャ
ストされる。各行先ノードにおいて、コマンドは、その
要素に分離され、各ノードのグローバルポートは、各ノ
ードにおいてどんなアクションをとるべきかを決定す
る。上記の例では、「送信読み取り変更」がプロセッサ
342により処理され、そして「記入変更マーカー」が
プロセッサ320により処理される。更に、DTAGエ
ントリに基づき、ホームノード、「記入変更マーカー」
を受け取るノード、及び「送信変更」を受け取るノード
において「無効化」が実行される。「送信読み取り変
更」に応答して、ダーティデータが「長い記入変更」コ
マンドを経てプロセッサ342からプロセッサ320へ
送られる。
つ又は3つのノード接続即ち「ホップ」を実行すること
ができる。本発明の1つの実施形態では、読み取り型コ
マンド(「読み取り」及び「読み取り変更」)のみが3
つのホップを生じ、但し、第3のホップは「記入」型コ
マンド(「記入」又は「記入変更」)である。しかしな
がら、本発明は、以下に述べる追加コマンドを仮想チャ
ンネル待ち行列に適当に割り当てることにより3つ以上
のホップを必要とする他のトランザクションも含むよう
に容易に変更できる。
ン―ダーティ(CTD)及び無効化―ダーティ(IT
D)の基本的な流れが示されている。図20Gでは、ク
リーン―ダーティは、ホームノードにおいてプロセッサ
320からディレクトリ321へ発生される。プロセッ
サ320が更新を希望するところのクリーンキャッシュ
ラインが現在のものであるか効力を失ったものであるか
に基づいて、「確認」コマンド(ACK)又は「非確
認」(NACK)コマンドのいずれかがプロセッサ32
0へ返送される。対応的に、CTDは成功又は失敗と言
える。更に、CTDが成功の場合にデータのキャッシュ
ラインのコピーをもつものとしてディレクトリ321の
存在ビットにより指示された全てのノードに「無効化」
が送られる。図20Hに示すように、ITDコマンド
は、CTDと実質的に同様に働く。しかしながら、IT
Dは決して失敗とならない。ACKが常にプロセッサ3
20に送られ、そしてデータのキャッシュラインのコピ
ーを記憶するシステムの他のノードには「無効化」が送
られる。
ム:上記のように、書き込みビクティムコマンドは、ダ
ーティデータをプロセッサのキャッシュから適当なホー
ムメモリへ返送する。図20I及び20Jを参照すれ
ば、書き込みビクティムの流れは、「ホーム」メモリが
書き込みビクティムを発生するプロセッサと同じノード
であるかどうかに基づいて若干異なることが明らかであ
る。図20Iに示すように、「ホーム」ノードがプロセ
ッサのノードである場合には、プロセッサ320が書き
込みビクティムを発生し、そしてデータは、同じノード
のメモリへ直接送られる。
クティムデータがプロセッサとは異なるホームにある場
合には、データが2つの段階で転送される。第1に、ビ
クティムキャッシュラインがプロセッサ320のキャッ
シュ(又はビクティムバッファ)から送出され、そして
プロセッサノードのグローバルポートにおけるビクティ
ムキャッシュ(図6の要素124)に記憶される。ビク
ティムキャッシュは、「ビクティムリリース」信号でプ
ロセッサに応答し、プロセッサがそのビクティムバッフ
ァエントリを再使用できることを指示する。次いで、ス
イッチに使用可能な帯域巾が存在するときには、ビクテ
ィムデータは、「書き込みビクティム」コマンドにより
ビクティムキャッシュからホームプロセッサのメモリへ
送られる。
送られたビクティムデータは、それがメモリに到達する
ときまでに効力を失うことがあることに注意されたい。
このような場合に、ビクティムは、「失敗」と言われ、
ホームメモリは更新されない。このようなケースは、P
がキャッシュラインの所有権を獲得するときと、Pのビ
クティムがホームディレクトリに到着するときとの間の
インターバルに別のプロセッサがキャッシュラインの所
有権を獲得したときに生じる。このような場合には、P
のビクティムがホームARBに到達する前に、キャッシ
ュラインに対する「無効化」又は「FrdMod」調査
をプロセッサPに送信しなければならない。ビクティム
データをメモリに書き込まねばならないかどうか決定す
るために、「書き込みビクティム」コマンドがホームA
RBバスに現れるときに、要求されたアドレスに対する
ディレクトリエントリがルックアップされる。ソースプ
ロセッサが依然としてキャッシュラインの所有者である
ことをディレクトリが指示する場合には、ビクティムが
成功となり、メモリを更新する。さもなくば、失敗とな
り、メモリは更新しない。いずれにせよ、ディレクトリ
321においてビクティムに対して判断がなされると、
「ビクティムACK」コマンドがノード325のグロー
バルポートに返送され、ビクティムキャッシュは関連エ
ントリをクリアすることができる。
を使用して、「書き込みビクティム」コマンドがローカ
ルである場合に「書き込みビクティム」コマンドの成功
又は失敗を判断する。この特定の例(ローカル「書き込
みビクティム」要求の例)では、DTAG及びDIRの
両方が「書き込みビクティム」要求の成功又は失敗を決
定するに必要な情報を与えることができる。DTAG
は、単にDTAGをベースとする機構が小型のSMPノ
ードハードウェアに対して既に設けられているという理
由でDIRに代わって使用される。キャッシュコヒレン
スプロトコルの上記説明では、最も一般的な動作及びコ
マンド形式について述べた。これら機構は、以下に詳細
に説明する。上記のように、本発明の1つの実施形態で
は、2つ以上の関連メッセージパケットを効率化のため
に1つに結合することができる。結合されたパケット
は、次いで、HS又はノードのARBバスにおいてその
成分に分割することができる。例えば、HSへのFrd
Modメッセージは、所有者プロセッサをもつノードへ
のFrdModメッセージと、キャッシュラインのコピ
ーをもつノードへの「無効化」メッセージと、ソースノ
ードへのFillMarkerModメッセージとに分
割される。所有者プロセッサノードへのFrdMod
は、ノードのARBバスにおいて、所有者プロセッサへ
のFrdModメッセージと、ノードの他のプロセッサ
へのゼロ以上の「無効化」メッセージとに更に分割され
る。
遅延書き込みバッファ動作:図20I及び20Jについ
て上述したように、ホームメモリに送られるビクティム
データは、「書き込みビクティム」がホームARBに到
達する前に受け取られるキャッシュラインに対し「無効
化」又はFrdMod調査が介在する結果としてそれが
到着するときまでに効力を失うことがある。ビクティム
データをメモリに書き込まねばならないかどうかを決定
する1つの方法は、各書き込みビクティムコマンドに対
してディレクトリエントリをルックアップすることであ
る。ビクティム書き込みコマンドを発生するプロセッサ
がダーティ所有者であることをディレクトリが指示する
場合には、ビクティムを進めることが許されねばならな
い。さもなくば、失敗となってしまう。この方法が望ま
しい理由は、プロセッサとシリアル化ポイントとの間の
ビクティム書き込みコマンドを、シリアル化ポイントと
プロセッサとの間の調査コマンドと一致させるための複
雑な比較論理構造体の必要性が回避されるからである。
を簡単化するが、メモリ帯域巾が減少するという形態の
性能欠陥を生じさせる。この構成によれば、システムが
ビクティム書き込みコマンドを実行するたびに、先ず、
ディレクトリ状態をアクセスし、次いで、その状態を評
価し、そして最終的に、その状態に基づいて、ビクティ
ムデータのDRAM書き込みを実行しなければならな
い。メモリ及びディレクトリは原子的にアクセスされる
ので、公知の設計方法に基づいてシステムがシステムが
設計された場合に、全ビクティム書き込みサイクルは、
ディレクトリルックアップ時間と、状態評価時間と、D
RAM書き込み時間との和に等しくなる。このようなシ
ステムは、全ビクティムサイクルがDRAM書き込みの
みで構成されるシステムに対して甚だしい性能上の不利
益をこうむる。
ンクに遅延書き込みバッファを設けることにより、この
メモリバンク利用低下問題を克服する。ビクティム書き
込みがメモリシステムへ発生されるたびに、メモリシス
テムは、次の機能を並列に実行することにより応答す
る。即ち、ビクティム書き込みデータをターゲットメモ
リバンクの遅延書き込みバッファに記憶しそしてそのブ
ロックを「非書き込み可能」又は「無効」と表示し、ビ
クティム書き込みに関連したディレクトリ状態をアクセ
スし、そして現在ビクティム書き込みに代わって、「書
き込み可能」又は「有効」と表示された既にバッファさ
れたビクティム書き込みのDRAM書き込みを実行す
る。ディレクトリアクセスが完了したときに、ビクティ
ム書き込みに関連したディレクトリ状態が、ビクティム
書き込みが成功したことを示す場合には、ビクティムが
存在する遅延書き込みバッファが「書き込み可能」又は
「有効」状態へと移行する。遅延書き込みバッファにお
けるデータブロックの「書き込み可能」又は「有効」状
態は、バッファのデータが、DRAMメモリに記憶され
たバージョンよりも最新のキャッシュラインのバージョ
ンであることを指示する。バッファが「書き込み可能」
又は「有効」と表示された場合には、そのデータが、メ
モリシステムへのビクティム書き込みのその後に発生に
よりDRAMへ書き込まれる。既に発生されたビクティ
ム書き込みのDRAM書き込みと並列にディレクトリル
ックアップを実行することにより、この実施形態は、全
ビクティムサイクル時間を単一のDRAM書き込み時間
に減少する。この実施形態は、「書き込み可能」な又は
「有効」なデータブロックを多数のサイクルにわたり遅
延書き込みバッファに保持し、そのサイクル中にバッフ
ァされたブロックへのその後の参照をメモリへ発生する
ことができるので、遅延書き込みバッファは、連想アド
レスレジスタを備えている。ビクティム書き込みブロッ
クのアドレスは、その関連データが遅延書き込みバッフ
ァに記憶されるのと同時に連想アドレスレジスタに記憶
される。その後の参照がメモリシステムへ発生されると
きには、メモリシステムは、アドレスレジスタに対する
アドレス一致により遅延書き込みバッファにおけるアド
レスブロックを識別する。これは、メモリシステムが、
DRAMメモリの効力を失ったデータに代わってバッフ
ァからの最新のデータで遅延書き込みバッファのブロッ
クへの全ての参照にサービスすることを意味する。
動作を与える上記技術は、DTAG状態を直接含まずに
DTAG状態を使用してデータブロックの有効性を決定
するスヌーピーバスをベースとするシステムにも使用で
きる。図21を参照すれば、遅延書き込み動作を与える
メモリ制御システムの1つの実施形態は、ディレクトリ
140からライン140aを経てOwner Matc
h信号を受け取るように接続されたメモリコントローラ
332を含むように示されている。更に、メモリコント
ローラ332は、ディレクトリに入力されるコマンドを
追跡するためにQS ARB11(ディレクトリ140
にも信号供給する)からも入力を受け取る。メモリコン
トローラ332は、遅延書き込みバッファ336を含
む。遅延書き込みバッファ336の各エントリは、デー
タ部分336aと、フラグ部分336bと、アドレス部
分336cとを含む。本発明の1つの実施形態におい
て、設計上の複雑さを最小限にするために、遅延書き込
みバッファは、1つのアドレス、データ及びフラグエン
トリのみを保持するが、本発明は、このような構成に限
定されるものではない。
する。動作中に、コマンド、アドレス及びデータがAR
B BUS130を経て受け取られると、それらはディ
レクトリ140及びメモリコントローラ332へ送られ
る。メモリコントローラ332は、コマンド、アドレス
及びデータを書き込みバッファ336に1トランザクシ
ョン周期中(ここでは18クロックサイクル中)記憶す
る。トランザクション周期中に、ディレクトリ140が
アクセスされ、そしてアクセスの結果がOWNER M
ATCHライン140aにアサートされる。OWNER
MATCHラインは、メモリの更新を求めるプロセッ
サのプロセッサIDが実際にデータのキャッシュライン
の所有者であることをディレクトリエントリが指示する
場合にアサートされる。OWNER MATCH信号
は、遅延書き込みバッファエントリ336のフラグ33
6bをセットするのに使用される。次に続くトランザク
ション周期中に、メモリバスが使用できそしてフラグ3
36bがアサートされた場合には、メモリ334に記憶
データが書き込まれる。本発明の1つの実施形態では、
書き込み動作のみがバッファされ、到来する読み取り動
作は、遅延なくメモリバスをアクセスすることが許され
る。遅延書き込みバッファに記憶されたビクティムデー
タへのその後の読み取り動作は、遅延書き込みバッファ
からサービスされる。
図である。時間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により処理するためにメモリに送ら
れる。
延書き込みバッファのフラグビットをセットするのにD
TAGも使用できることに注意されたい。ローカルメモ
リからのキャッシュラインの1つをローカルノードにお
けるプロセッサのキャッシュの1つに記憶することがで
きる。プロセッサの1つがキャッシュラインをビクティ
ム化しそしてキャッシュラインが遅延書き込みバッファ
に書き込まれたときに、そのキャッシュラインのDTA
Gエントリを検査して、キャッシュラインがプロセッサ
の1つに常駐したかどうか決定することができる。キャ
ッシュラインがプロセッサの1つに常駐した場合には、
DTAGエントリの有効ビットを検査して、プロセッサ
がビクティム化するコピーが有効であることを確保す
る。DTAGにヒットがありそしてキャッシュラインが
有効であった場合には、DTAGが遅延書き込みバッフ
ァのフラグをセットし、キャッシュラインをローカルメ
モリに書き込みさせる。これは、簡単なスヌーピーバス
をベースとする(即ちディレクトリのない)システムが
この同じ簡単なアルゴリズムを適用できるようにする。
読み取り動作を読み取りサイクルにおいて直ちに実行す
ることができそして書き込み動作を各書き込みサイクル
に実行できるようにする(たとえ遅延書き込みであって
も)。その結果、ディレクトリのアクセスにより遅延を
こうむることなくデータの定常流がDRAMに送られ、
そしてコヒレンス性を維持しながら性能が高められる。
遅延書き込みバッファ技術は、ビクティム書き込み動作
に関連して説明したが、メモリ性能を改善するためにコ
ヒレンス状態が集中され且つ一定保持されるようないか
なるシステムにも使用することができる。
レンスプロトコルを実施するために、プロセッサと、デ
ィレクトリと、メモリと、DTAGとの間に多数のメモ
リ参照が送信されることが明らかである。更に、各メモ
リ参照は、多数のトランザクション即ちホップをノード
間に備え、メモリ参照のためのメッセージは、参照全体
が完了する前に転送される。メッセージ間の依存性が参
照を不定に阻止する場合には、マルチプロセッサシステ
ムが停滞(デッドロック)状態となる。 上記で簡単に
述べたように、本発明の1つの実施形態は、仮想チャン
ネル流れ制御を使用することにより、ノード間のトラフ
ィックをマネージしそして停滞を生じることなくデータ
コヒレンス性を維持する。仮想チャンネルは、相互接続
ネットワークに停滞のないルートを形成するために最初
に導入された。本発明の1つの実施形態によれば、仮想
チャンネルは、更に、共用メモリコンピュータシステム
のためのキャッシュコヒレンスプロトコルにおけるリソ
ース停滞を防止するのにも使用できる。
トコルでは、2つの形式の解決策が使用されている。少
数のプロセッサと少数の同時保留中要求とを有するシス
テムの場合には、実行中の任意の点に生じ得る考えられ
る最大数の応答を受け入れるに足る大きさの待ち行列及
びバッファが設けられている。充分な待ち行列及びバッ
ファスペースを設けることにより、メッセージが進行の
ために別のメッセージに決して影響されないよう保証し
ている。多数の保留中要求を伴う大型のシステムでは、
考えられる最大数の応答を受け入れるに足る大きさのバ
ッファ及び待ち行列を設けることは実際的ではない。従
って、停滞検出及び分析機構に接続された2チャンネル
相互接続を使用して問題が解決される。第1に、相互接
続部(プロセッサ及びメモリのようなシステム要素間に
メッセージを移動するのに使用される論理的経路)は、
2つのチャンネル、即ち要求チャンネル(又は下位チャ
ンネル)と、応答チャンネル(又は上位チャンネル)と
を使用する。これらのチャンネルは、一般に、物理的な
ものであり、即ち個別のバッファ及び待ち行列を使用す
る。第2に、潜在的な停滞を検出するために発見的手法
が一般的に実施される。例えば、コントローラは、待ち
行列がいっぱいでありそして待ち行列からある時間中に
メッセージが出力されないときに潜在的な停滞を通知す
る。第3に、選択されたメッセージが否定的に確認され
て、リソースを解放し、他のメッセージを進行できるよ
うにする停滞分析機構が実施される。否定的な確認メッ
セージは、それに対応するコマンドをリタイアさせる。
欠乏の問題及び性能不利益の問題を含む2つの主たる問
題を有している。あるメッセージが否定的に確認される
ので、あるコマンドが長時間完了しない(潜在的に不定
である)ことが考えられる。コマンドが所与の時間周期
内に完了するよう保証されない場合には、そのコマンド
を発生するリソースは、システムデータへの公平なアク
セスを得ることができない。更に、リソースがシステム
データへの公平なアクセスを得ることができないため
に、データに対して欠乏状態となり、潜在的にシステム
の停滞を生じさせる。更に、あるメッセージが否定的に
確認され、従って、それらの行先に到達しないので、無
効化メッセージのようなプロトコルメッセージは、それ
らが行先に首尾良く到達することを指示するための確認
を発生しなければならない。更に、コントローラは、対
応するコマンドが完了したとみなし得る前に全ての確認
が受け取られるまで待機しなければならない。この非決
定論的結果は、キャッシュコヒレンスプロトコルの全性
能を低減するようなメッセージオーバーヘッド及び余計
な待ち時間を生じさせる。
避に対する系統的及び決定論的解決策を採用したキャッ
シュコヒレンスプロトコルが使用される。潜在的な停滞
を検出しそして矯正動作を行うのではなく、停滞が設計
により排除される。従って、停滞検出及び分析機構の必
要性がなくなる。第2に、メッセージは、停滞回避のた
めの否定的確認ではなくなるので、「無効化」のような
プロトコルメッセージに対する確認が不要となり、それ
故、帯域巾及び待ち時間が改善される。仮想チャンネル
の使用を説明する目的で、幾つかの有用な用語について
最初に説明する。 依存性:メッセージM2が進行しな
い限りメッセージM1が進行できない場合に、メッセー
ジM1はメッセージM2に「依存」すると定義する。更
に、依存性は、移行的であるとも定義する。本発明のキ
ャッシュコヒレンスプロトコルを実施する場合に、リソ
ース依存性及び流れ依存性の少なくとも2種類の依存性
がある。M2が待ち行列スロットのようなリソースを解
放するまでM1が進行できない場合に、M1はM2に
「リソース依存」すると定義する。M2が進行するまで
M1が進行しないことをキャッシュコヒレンスプロトコ
ルが必要とする場合には、M1はM2に「流れ依存」す
ると定義する。例えば、キャッシュコヒレンスプロトコ
ルは、ディレクトリがある状態に達するまでM1が阻止
状態であり、そしてディレクトリの状態を所望の値にセ
ットするのがM2であることを要求する。従って、M1
からM2へのリソース又は流れ依存性のチェーンが存在
する場合に、M1はM2に依存すると定義する。
に依存し;M2の進行がM3の進行に依存し;Mk―1
の進行がMkの進行に依存し;そして最終的に、Mkの
進行がM1の進行に依存するときに、1組のメッセージ
M1、MK(≧2)の間に「依存性サイクル」が存在す
ると定義する。メッセージのあるサブセットが依存性サ
イクルを形成するときにメッセージのシステムは停滞状
態になる。M1はMkに依存し、Mkは次いでM1に依
存するので、サイクル内のどのメッセージも進行するこ
とができない。ここに開示する方法及び装置は、仮想チ
ャンネルを使用して、キャッシュコヒレンスプロトコル
における停滞を決定論的に回避する。キャッシュコヒレ
ンスプロトコルの設計において必要とされるハードウェ
ア機構及び従うべき1組のルールについて説明する。
レンスプロトコルは、全てのメモリ動作がせいぜい3段
階で完了すると定める。各段階において、システムの要
素間に1つ以上のメッセージが転送される。それ故、各
段階は、「ホップ」と称される。ホップは、0、1及び
2と番号付けされる。ホップ0では、プロセッサ又はI
Oプロセッサからの要求がホームディレクトリへ送られ
る。ホップ1では、ホームディレクトリにより発生され
たメッセージが1つ以上のプロセッサ又はIOプロセッ
サへ送られる。ホップ2では、メッセージが所有者プロ
セッサからソースプロセッサへ送られる。これらホップ
は、図23に示されている。キャッシュコヒレンスプロ
トコルの顕著な特性は、全ての動作が所定数のホップ内
に完了することである。ここに示す実施形態では、所定
数が3であるが、本発明は、選択される数が比較的小さ
く且つ一貫したものである限り、特定のホップ数に限定
されるものではない。この特性は、停滞を検出しそして
停滞を解消するためのメッセージを失敗して再トライす
る機構を伴わずに、全てのメッセージをそれらの行先に
ルート指定できることを保証するための鍵である。
最大ホップ数が3である。従って、システムは、各々Q
0、Q1及びQ2と示された3つのチャンネルを備えて
いる。これらのチャンネルは、システム相互接続部を通
る論理的に独立したデータ経路である。これらのチャン
ネルは、物理的なものでもよいし、仮想のもの(或いは
一部分物理的で且つ一部分仮想)でもよい。物理的なも
のであるときには、各チャンネルは、システム全体にわ
たり個別の待ち行列及びバッファリソースを有する。仮
想のものであるときには、チャンネルは、待ち行列及び
バッファリソースを共用し、以下に述べる制約及びルー
ルを受ける。3つのチャンネルは、ハイアラーキーを構
成し、Q0は最下位であり、Q1はその次であり、そし
てQ2は最上位のチャンネルである。システムにおける
停滞回避のための重要なルールは、チャンネルQiのメ
ッセージが、Qiより下位のチャンネルのメッセージに
決して依存しないことである。
IOシステムからの応答メッセージと、IOシステムか
らのメモリスペースコマンドとの間の流れ依存性サイク
ルを排除するためにQIOチャンネルが追加される。最
後に、本発明の1つの実施形態では、ビクティムメッセ
ージと、ビクティムメッセージが発生されるがビクティ
ムメッセージが保留中である間に発生されるその後の依
存性メッセージとに対して、Q0Vicチャンネルが使
用される。図20a―20hに関連して上述したよう
に、スイッチへ発生される所与のコマンドメッセージ
は、一連の多数の個別トランザクションを発生する。本
発明の1つの実施形態において、所与のコマンドパケッ
トに対する各個別のトランザクションは、チャンネルに
割り当てられる。チャンネルは、本質的に、所与のコマ
ンドパケットの完了段階及び依存性を定義する順序付け
された構造体を形成する。
いて述べた動作の個別トランザクションにチャンネルを
割り当てるところを示すフローチャートである。個別ト
ランザクションは、次の用語で識別される。即ち、参照
により生じる一連のトランザクションにおける第1トラ
ンザクションは、Q0又はQ0Vicトランザクション
と称し、一連のトランザクションにおける第2トランザ
クションは、Q1トランザクションと称し、そして一連
のトランザクションにおける第3トランザクションは、
Q2トランザクションと称する。Q0又はQ0Vicチ
ャンネルは、まだディレクトリを訪れていないプロセッ
サ及びIOPからの初期コマンドを搬送する。従って、
Q0/Q0Vicパケットの行先は、常に、ディレクト
リである。Q0Vicチャンネルは、「書き込みビクテ
ィム」コマンドに対して特に指定され、一方、Q0チャ
ンネルは、プロセッサ又はIOPにより開始された他の
全ての形式のコマンドを搬送する。
データを得るか又は状態を更新しようと求める。状態
は、常に、データのアドレスに対応するホームディレク
トリで得ることができる。ステップ382において、ホ
ームディレクトリがアクセスされ、そして使用可能なキ
ャッシュラインがホームメモリにより所有される(ディ
レクトリに対して)か、別のプロセッサにより所有され
るかが決定される。いずれの場合にも、応答はQ1チャ
ンネルを経て発生される。ステップ382において、状
態又はデータが第2ノードに得られると決定された場合
には、ステップ384において、Q1チャンネルの応答
が第1ノードへ返送される。Q1形式のトランザクショ
ンは、ShortFill、ShortFillMo
d、VicAck、CTD―ACK/NACK当を含
む。
データを所有せず、データがダーティであって別のプロ
セッサにより所有されると決定された場合には、ステッ
プ386において、「送信読み取り」又は「送信読み取
り変更」のQ1形式のトランザクションがQ1チャンネ
ルを経てリモートノードへ発生される。ダーティへと状
態変化したデータを他のノードが共用することを指示す
るホームノードの状態チェックに応答するか、又は「読
み取り変更」に応答する場合には、ステップ388にお
いて、無効化Q1形式トランザクションがシステムの他
の当該ノードに送られる。従って、Q1チャンネルは、
第2の「ホップ」におけるパケットを搬送するためのも
のであり、第1のホップはディレクトリに対するもので
ある。第2の「ホップ」の行先は、常にプロセッサであ
り、プロセッサは、元のコマンドを開始したノードにあ
るか、又はシステム内の別のリモートノードにある。
い記入変更」トランザクションのいずれかを搬送する。
Q2チャンネルは、第3の「ホップ」による第3ノード
からのデータを、元のコマンドを開始したノードへ返送
する。Q0/Q0Vic、Q1及びQ2形式のコマンド
へのコマンドの割り当ては、SMPシステムにおいて停
滞のないメッセージ送信を確保するために次のように使
用できる。図23のフローチャートは、4つの仮想チャ
ンネル間の対話を示すが、本発明の1つの実施形態で
は、キャッシュコヒレンス性を維持する目的で5つの仮
想チャンネルを使用することができる。その追加チャン
ネルは、QIOチャンネルである。一般に、QIOチャ
ンネルは、制御状態レジスタ(CSR)アクセスを含む
IOアドレススペースへ全ての読み取り及び書き込みを
搬送する。
のコマンドマッピングを例示するリストである。 テーブル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つの実施
形態では、これら技術の組み合わせを使用して、ハード
ウェアの最適な使用がなされる。図24には、2つ以上
の仮想チャンネル間で単一バッファをいかに共用するか
が示されている。バッファ400は、多数の「スロッ
ト」を含むように示されている。各スロットは、1つの
チャンネルのみにより専用に使用される。例えば、スロ
ット402は、Q2型コマンドに専用の多数のバッファ
エントリを含み、スロット404は、Q1型コマンドに
専用の多数のバッファエントリを含み、等々となる。
ネルについても、メッセージにより使用することがで
き、それ故、「共用」又は「一般的」スロットと称され
る。各チャンネルについてビジー信号が与えられる。ビ
ジー信号は、バッファがそれ以上のメッセージを記憶で
きず、それ故、そのバッファに何も送信してはならない
ことを指示する。所与のチャンネルに対する所与のリソ
ースにおいてビジー信号がアサートされるときと、その
リソースにコマンドを発生するデバイスがビジー信号に
応答して発生を停止するときとの間には待ち時間周期が
ある。この待ち時間の間に、1つ以上のコマンドパケッ
トがリソースへ発生されることが考えられ、それ故、リ
ソースは、コマンドが脱落しないように設計されねばな
らない。
サートした後にも、M個のメッセージを受け入れること
ができねばならず、但し、Mは、次の式III で定められ
る。 式III : M=(フレームクロックでの流れ制御待ち時間)/(フ
レームクロックでのパケット長さ) 「M」の値は、ここでは、チャンネル当たりに得られる
専用スロットの数を定義する。図25には、各チャンネ
ルごとに個別のリソースを使用して仮想チャンネルが実
施される例が示されている。2つのノード420及び4
24の部分は、ハイアラーキースイッチ(HS)422
を経て互いに接続されて示されている。
を経てスイッチ422から入力データを受け取り、そし
てバス421bを経てスイッチ422にデータを送信す
るように接続される。同様に、グローバルポート424
は、バス423aを経てスイッチ422にデータを送信
し、そしてバス423bを経てスイッチ422からデー
タを受け取るように接続される。データバス421a、
421b、423a及び423bの各々は、全ての形式
のチャンネルコマンドを送信又は受信する。待ち行列機
構425のような待ち行列機構は、各リソースの各入力
及び出力端子に設けられる。この待ち行列機構は、多数
の個々に制御されるバッファ425a―425eを備
え、各バッファは、1つの形式のチャンネルコマンドの
みを専用に記憶する。バッファ425aは、Q0チャン
ネルコマンドのみを記憶し、バッファ425bは、Q0
Vicチャンネルコマンドのみを記憶し、等々となる。
ェイスに受け取られるときに、コマンドの形式がパーズ
され、そしてパケットは、適当なバッファへ送られる。
コマンドパケットがノードの適当なプロセッサ又はIO
Pへ送られる準備ができると、それらが適当なバッファ
から選択され、そしてARBバス及びQSA(図6)を
経て送られる。各チャンネルごとに1つづつ、5つのサ
ーチエンジンがあり、各チャンネルに対して次のメッセ
ージを探索する。上記機構においては、各チャンネルが
独立して流れ制御され、そしてシステム全体にわたりハ
イアラーキーの最下位チャンネル以外の各チャンネルに
スロットが指定される。これは、チャンネルがリソース
依存性により下位チャンネルによって決して阻止されな
いことを保証する。上位チャンネルメッセージの移動
は、下位チャンネルメッセージによるリソースの占有に
より阻止されない。仮想チャンネル間で物理的バッファ
を共用する上記機構は、簡単なものである。より精巧な
機構については、ハイアラーキースイッチに関して最初
に述べた。
トコル設計のルール コヒレンスプロトコルにおいて停滞のないメッセージ送
信を保証するためにはハードウェア機構のみでは不充分
である。というのは、問題のリソース依存性の部分しか
対処しないからである。全てのリソース及び流れ依存性
サイクルを排除するために、多数の付加的な裁定及びコ
ヒレンスプロトコル設計ルールが適用される。第1に、
メッセージの進行は、下位チャンネルメッセージの進行
に依存してはならず、この場合に、Q2は上位チャンネ
ルであり、そしてQ0は下位チャンネルである。アービ
ターは、各チャンネルの流れ制御を互いに独立して維持
しなければならない。例えば、ビジーの流れ制御信号が
Q1に対してアサートされるが、Q2に対してはアサー
トされない場合には、アービターは、Q2メッセージを
進行させねばならない。保留中のコマンドパケットに対
してリソースをサーチするのに使用される全てのサーチ
エンジンは、同じ特性をサポートしなければならない。
れるいかなるリソースも、下位のチャンネルが阻止され
た場合に上位のチャンネルが進行できるようにするため
に、上位のチャンネルの各々に対してある専用のスロッ
トを含まねばならない。第3に、全てのチャンネルコマ
ンドは、一貫して作用しなければならない。Q0コマン
ドの終了点は、常に、ディレクトリである。Q1コマン
ド及びQ2コマンドの終了点は、常に、プロセッサであ
る。終了点において、トランザクションを継続するため
に、それらを上位チャンネルへ移動しなければならな
い。例えば、Q0メッセージがディレクトリに到達した
ときには、Q0メッセージを発生することができず、Q
1又はQ2メッセージを発生しなければならない。それ
故、メッセージは、下位チャンネルメッセージへと分岐
又は変換することはできない。
の場合には、同じか又は上位のチャンネルのメッセージ
しか形成できない。例えば、「送信読み取り変更」(Q
1メッセージ)がハイアラーキースイッチにおいて「送
信読み取り変更」、「無効化」及び「記入変更マーカ
ー」を形成するときには、これら全てのメッセージがQ
1メッセージとなる。従って、バスをベースとするシス
テム又はスイッチをベースとするシステムのいずれかに
仮想チャンネルを設ける装置及び方法が提供される。仮
想チャンネル及び上記の順序付け制約を使用することに
より、参照は、ディレクトリによっていったんサービス
されると完了することが保証される。その結果、NAC
K(1つのプロセッサが別のプロセッサにプロセスが完
了しないことを指示する)及びリタイアを必要とする公
知の複雑なプロトコルは排除される。
形態を示したが、本発明の1つの実施形態は、所与の数
のチャンネルに限定されず又は対称的なマルチプロセッ
サシステムに限定されないことを理解されたい。むし
ろ、選択されるチャンネルの数は、各チャンネルに固有
の制御及びハードウェアオーバーヘッドが与えられる
と、コヒレントな通信をサポートするに必要な数でなけ
ればならない。従って、仮想チャンネル制御方法及び装
置は、マルチプロセッサシステムにおいて高性能の、停
滞のない通信を行えるようにする。
リの動作:以上に、基本的な通信構成を説明し、そして
SMPのノード間に通信が自由に流れるようにするため
の基本的な制御構造体が提供された。しかしながら、コ
ヒレンス性のための鍵は、自由に流れるコマンドがシス
テム内の各プロセッサにより正しい順序で「取り扱われ
る」ように確保することである。SMPシステム内の全
てのコマンドに対しシリアル化ポイントを与える機構
は、各ノードにおけるディレクトリである。上述したよ
うに、全てのQ0形式コマンドは、先ず、関連メモリア
ドレスのホームディレクトリをアクセスする。いずれの
コマンドに対してもホームディレクトリが最初にアクセ
スされるよう確保することにより各コマンドを共通のソ
ースから正しい順序で検討することができる。本発明の
1つの実施形態では、シリアル化順序は、アドレスXに
対するディレクトリからの裁定に勝った後にXに対する
Q0コマンドがARBバスに現れるという順序である。
「ロード」形式のコマンドは、それに対応する読み取り
コマンドがホームディレクトリにアクセスしたときに順
序付けされる。「記憶」形式のコマンドは、それに対応
する「読み取り変更」コマンドがディレクトリにアクセ
スするか又はそれに対応する「クリーン―ダーティ」コ
マンドがディレクトリにアクセスしてARBバスに現れ
るときに順序付けされる。
ンスが種々のプロセッサ(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を形成する。
る事象の各シーケンスがキャッシュラインXの正しいバ
ージョンを得るように確保する。例えば、コマンド2な
いし4は、バージョン1を得なければならない。プロセ
ッサP1のコマンド5が記憶を行うときには、全てのバ
ージョン1キャッシュライン(プロセッサP2、P3及
びP5における)に「無効化」を送信しなければならな
い。同様に、プロセッサP2のコマンド6がバージョン
3データでXを更新するときには、プロセッサP1のバ
ージョン2データを無効化しなければならない。プロセ
ッサP4、P6及びP7は、バージョン3データを得る
が、これは、プロセッサP8のバージョン4データの記
憶により後で無効化される。共通のアドレスキャッシュ
ラインXに対する多数のロード及び記憶動作は、システ
ムにおいていかなる所与の時間にも進行し得ることを述
べれば充分であろう。システムは、ロード及び記憶がデ
ィレクトリによりシリアル化順序で処理されるようにこ
れらのコマンドを処理する。
付随的にデータのコヒレンス性を維持するのを助けるた
めに多数の技術が使用される。これらの技術は、Q1チ
ャンネルコマンドの厳密な順序付け、CTD明瞭化、
「シャドーコマンド」、「マーカー記入」及び「遅延ビ
クティム書き込みバッファ動作」を含む。各技術につい
て、以下に詳細に説明する。Q1チャンネル順序付け :コヒレンス性を維持するのに
使用される第1の方法は、Q1チャンネル上を進行する
全てのメッセージ、即ちディレクトリから送られる全て
のメッセージが、先入れ先出し順序で進むように確保す
ることである。即ち、ディレクトリから別のプロセッサ
又はIOPへ送られるQ1型メッセージは、コマンドがデ
ィレクトリにおいてシリアル化された順序に基づいて送
られる。
ノード430における第1プロセッサP1(431)が
キャッシュラインXをそのキャッシュ「ダーティ」に記
憶すると仮定する。ノード432におけるプロセッサP
16(433)は、Q0チャンネルに「X読み取り(Rea
d X)」を発生し、これは、ノード436におけるXのホ
ームディレクトリ437へ送られる。又、ノード432
におけるプロセッサP17は、Q0チャンネルに「無効
―ダーティ」コマンドを発生し、これも、ノード436
におけるXのホームディレクトリ437へ送られる。
「X読み取り」の受信に応答して、ディレクトリエント
リに基づき、「送信X読み取り(ForwardedRead X)」が
Q1チャンネルを経てプロセッサP1(431)へ送ら
れる。ITDの受信に応答して、ディレクトリエントリ
の状態に基づき、「無効化」がハイアラーキースイッチ
435へ送られ、これは、Q1チャンネルを経てプロセ
ッサP1及びプロセッサP16へ「無効化」を送る。従
って、同じ時点で、「X無効化」及び「X読み取り供
給」がQ1チャンネルコマンドとしてP1へ送られる。
実行することが許された場合には、「読み取り」の前に
「無効化」が生じることがある。その結果、「読み取
り」のための記入データがプロセッサP16に送られな
いことになり、それ移行の動作の結果が予想し得ないも
のとなる。しかしながら、チャンネルQ1のコマンドを
正しい順序で保つことにより「読み取り」は「無効化」
を受け取る前に処理され、コヒレンス性が維持される。
本発明の1つの実施形態では、チャンネルQ1について
のみFIFO順序が維持され、FIFO順序とは、同じ
メモリアドレスに対応する全てのメッセージがFIFO
順序に留まることを意味する。しかしながら、本発明
は、Q1チャンネルに対する順序を維持することのみに
限定されるものではなく、チャンネルのいかなる組み合
わせに対する順序の維持も含むように拡張することがで
きる。
は、QSAチップ(図6)のQSARB11により実行
される。QS ARBは、全てのQ0トランザクション
をノードのホームメモリスペースに対してシリアル化す
る。その結果、Q1パケットのシリアル流が発生され
て、ノードのローカルプロセッサと、グローバルポート
及びハイアラーキースイッチを経てノードから離れたプ
ロセッサとの両方に向けられる。第1の順序付けルール
を次に説明する。所与のQS ARBにより発生される
全てのQ1パケットは、シリアルな順序で発生される。
所与のQS ARBからの幾つかの又は全てのQ1パケ
ットがターゲットとする全てのプロセッサは、これらの
Q1パケットを、それらがQS ARBにより発生され
た順序で見る。
チップは、ノード内の接続されたプロセッサとやり取り
される全ての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においてシリアル化された
のと同じ順序で見なければならない。図27は、多数の
Q0及びQ1コマンドの順序付けが上記の順序付けガイ
ドラインに基づいてSMPを通して処理されるところを
示すブロック図である。ノード440のプロセッサPx
はコマンドQ0aを発生し、プロセッサPyはコマンド
Q0bを発生し、そしてプロセッサPzはコマンドQ0
cを発生すると仮定する。同じ時間中に、QS ARB
441は、プロセッサPr及びPqからのQ1メッセー
ジをグローバルポート443から受け取る。
けされる。QS ARB441は、Q0a、Q0b及び
Q0cを処理して、Q1a、Q1b及びQ1c応答を発
生する。これらの発生されたQ1コマンドは、到来する
Q1コマンドと合成されて、コマンドの順序付けされた
流れをFIFO442へ供給し、ローカルプロセッサへ
と送る。FIFOコマンドの順序は、QS ARBによ
り処理されたコマンドの順序を反映する。Q1a、Q1
b及びQ1cコマンドは、グローバルポート443へ送
られ、リモートノードへ送信される。グローバルポート
の出力バッファ444は、これらのコマンドを、それら
がQS ARBにより処理されたのと同じ順序で記憶す
る。この順序は、図14―19について上述した方法を
用いてメッセージがリモートCPU454へ送られると
きにハイアラーキースイッチ446により維持される。
いて従う別の順序付けガイドラインを示す。上述したよ
うに、ハイアラーキースイッチは、ハイアラーキースイ
ッチの所与の入力ポートに現れてハイアラーキースイッ
チの共通の出力ポートをターゲットとする多数のパケッ
トが、それらが入力ポートに現れたのと同じ順序で出力
ポートに現れるよう確保することにより、順序を維持す
る。図27Bを参照すれば、上述したように、ハイアラ
ーキースイッチは、入力メッセージをマルチキャスティ
ングする役目も果たし、即ち受け取った1つのQ1パケ
ットを2つ以上の行先ノードに送信するという役目も果
たす。スイッチによりマルチキャスティングされるパケ
ットの一例は、無効化パケットである。ハイアラーキー
スイッチの異なるポートから入力された多数のパケット
が共通の出力ポートにマルチキャスティングされるとき
には、Q1パケットは、全ての出力ポートにおいて同じ
順序で現れねばならない。例えば、パケット1及びパケ
ット2の両方がハイアラーキースイッチ460に受け取
られる場合に、2つのメッセージをプロセッサ464及
び466にマルチキャスティングする1つの許された方
法は、上記のように、メッセージ2がメッセージ1の前
に両プロセッサに到着するようにすることである。別の
許された方法は、メッセージ1のパケットがメッセージ
2のパケットの前に両プロセッサに到着するようにする
ことである。しかしながら、2つのプロセッサは、2つ
のパケットを異なる順序で受け取ってはならない。
い別の順序付けルールは、多数の入力ポートからのQ1
パケットの順序付けされたリストが共通の出力ポートを
ターゲットとするときに、Q1パケットが、全ての到来
するQ1パケットの1つの共通の順序付けに合致する仕
方で出力ポートに現れるように確保することである。例
えば、図27Cにおいて、入力ポート461には、パケ
ット2がパケット4の前に受け取られる。同様に、入力
ポート462には、パケット1がパケット3の前に受け
取られる。停滞を防止するには、これら命令の全体的な
順序を遵守しなければならない。出力パケットを与える
1つの許された方法は、パケット3を最初にノード46
4に送信し、そしてパケット1を最初にノード466に
送信することである。この送信が図27Cに示されてい
る。別の許された出力は、パケット2及び4を受信者の
プロセッサにより最初に受け取ることである。しかしな
がら、1つのプロセッサがパケット3を最初に受け取り
そして別のプロセッサがパケット4を最初に受け取る場
合には、プロセッサがそれらの元のシーケンスの他のパ
ケットの受信を待機してストールするので停滞が生じ得
る。
持されるよう確保するルールが設けられる。本発明の1
つの実施形態では、性能の理由で、Q0及びQ2チャン
ネルパケットを順序ずれして処理するのが望ましい。デ
ータの一貫性を確保するために、多数のコヒレンス性機
構が以下に述べるように設けられる。ダーティへの変更の明瞭化 上述したように、Q1形式のコマンドのみが、ディレク
トリに定義されたシリアル化順序で維持される。本発明
の1つの実施形態では、Q0及びQ2コマンドは順序付
けされない。従って、受け取られるQ0及びQ2コマン
ドの相対的なタイミングの結果としてディレクトリにコ
ヒレンス性の問題が生じないように予防策がとられる。
ィレクトリエントリの構造によるものである。図9に示
すように、各ディレクトリエントリは、所有権フィール
ドと、各ノードに対して1つの存在ビットとを含む。存
在ビットは、関連ノードの4つのプロセッサの1つにデ
ータが存在することを示すおおよそのベクトルである。
4つのプロセッサのいずれかが動作すると、存在ビット
がセットされる。従って、ノードのどのプロセッサが存
在ビットをセットしたかに関してある種の曖昧さが生じ
る。この曖昧さは、ある場合にコヒレンス性の問題を引
き起こす。例えば、図28A及び28Bは、2つのノー
ド470及び472のブロック図である。ノード470
[グローバルシステムのノードID3]は、プロセッサ
P12、P13、P14及びP15を備え、一方、ノー
ド472[グローバルシステムのノードID7]は、ノ
ードP28、P29、P30及びP31を含む。
る所与のキャッシュライン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へ送られる。
プロセッサが、キャッシュライン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よりも最新
のデータバージョンを記憶するからである。
サ14により形成されたキャッシュラインの古いバージ
ョンをまだ記憶しており、そしてプロセッサ14がデー
タの最新のバージョンを無効化するように通知したこと
である。このような状態は、SMPシステムで重大なコ
ヒレンスの問題を生じさせる。上記問題を解消するのに
使用できる幾つかの方法がある。その1つの方法は、シ
ステムの各プロセッサごとに1ビットを与えるようにデ
ィレクトリエントリの存在ビット拡張することである。
従って、分解能がノードレベルからプロセッサレベルへ
変更される。しかしながら、この解決策は、不都合なこ
とに、ディレクトリのサイズを増大する。本発明の1つ
の実施形態は、同じアドレスへの保留中参照がそのノー
ドに対してトランシット状態にあるときにCTDコマン
ドを低速化することにより上記曖昧さの問題を防止する
より簡単な方法を提供する。同じアドレスに対して保留
中の要求がある場合には、その以前の要求がリタイアす
るまでCTDが保持される。所与のノードのトランザク
ション追跡テーブル(TTT)(図10)を使用して、
そのノードに対する保留中のグローバル参照を監視す
る。更に、CTDがTTTに受け取られた後に受け取っ
た要求は、失敗となる。
は、完全に連想式の多機能制御構造体である。TTT
は、2つの一般的なタスクを実行する。これは、その関
連ノードにより発生された全てのリモート参照のアドレ
スを記憶する。従って、TTTは、そのトランザクショ
ンが完了したとみなされるまで、ノードにより発生され
た各リモートアクセスに対して1つの情報エントリを記
憶する。更に、TTTは、ローカルアドレスの要求に応
答して、過渡的なコヒレンス状態に関してコヒレンス情
報を与える。従って、TTTは、アクセスがトランシッ
ト状態にある間にその状態を追跡するためのテーブルで
ある。他の処理システムは、いかなる瞬間にも所与のキ
ャッシュラインへの1つの参照をトランシット状態にす
ることができる。トランシット状態にあるキャッシュラ
インへのその後の参照は、トランシット状態の参照が完
了するまで阻止される。
ドのシリアル化と、チャンネル順序付けルールとによ
り、本発明のSMPは、同じキャッシュラインへの多数
の参照を所与の瞬間に進行させることができる。その結
果、SMPの全性能が改善される。TTT522は、Q
SAチップ535のロジックにより、グローバルポート
に発生されたトランザクションの状態を決定するのに使
用される。グローバルポートへ応答を発生する前に、Q
SAは、先ず、TTTにアクセスして、同じキャッシュ
ラインへのどんな参照が保留中であるかを決定する。参
照は、最後に受け取ったトランザクションに応答してT
TTからリタイアしていない場合には保留中である。
は、コマンドフィールド584に示された参照の形式に
依存する。例えば、TTTに記憶するためにグローバル
ポートへ送られる「X読み取り」参照は、「ここに記
入」588a及び「マーカーをここに記入」588bの
両方の状態ビットを受け取ることを必要とする。(「マ
ーカーの記入」は、いかに詳細に述べる。)CTD又は
ITDのような状態型の参照の場合に、TTTにおいて
ACK/NACKビット588cをセットすれば、その
エントリをリタイアするのに充分である。図29は、T
TTを使用して曖昧なディレクトリエントリを排除する
ところを示すフローチャートである。ステップ500に
おいて、キャッシュラインXは、そのホームノードのメ
モリに記憶され、そしてノード7のプロセッサ30は、
データのコピーを記憶する。ステップ502において、
「ReadModX」がプロセッサ14により発生され
る。その結果、無効化がノード7に送られる。ステップ
504において、プロセッサP31は、「ReadX」
を発生し、これは、ノード7のTTTのエントリを次の
状態で形成する。
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をスイッチへ送ることが防止される。
ドレスXへの保留中の読み取り要求は、TTTにより識
別される。その結果、ステップ508において、CTD
は、「読み取り」がもはや保留中でなくなるまで、オフ
に保たれる。「読み取り」は、「記入」及び「マーカー
記入」の両方がノード7に返送されるまで保留となる。
この時間中に、ステップ502においてReadMod
により発生された無効化がノード7に到達し、各ノード
のDTAGSを更新する。Xの無効化がTTTに到達す
ると、TTTは、TTTに保持されたCTDを失敗と表
示し、これは直ちに解除される。ステップ510におい
て、CTDが依然TTTにある場合には、グローバルポ
ートを経て送信される。従って、TTTを使用して、C
TDコマンドを適当にオフに保持し又は失敗状態とする
ことにより、ディレクトリの存在ビットの曖昧さにより
生じるコヒレンスの問題を排除することができる。
んどの応答は、Q1チャンネルにおけるものであり、従
って、上記のルールによれば、正しい順序が維持され
る。しかしながら、Q2チャンネルで受け取られたメッ
セージは、この順序制約を受けない。Q2型のメッセー
ジは、「記入」及び「記入変更」を含む。Q2型メッセ
ージの到着は、ディレクトリにおいて明らかなように、
シリアル化順序を表わさないので、返送データに潜在的
な曖昧さが生じる。例えば、「無効化」がQ1を進行
し、そして「記入変更」がQ2を進行するので、コヒレ
ンス性を維持するためにどの動作が順序において最初に
生じるべきかを決定する何らかの方法がなければならな
い。
ド520及び532が示されている。説明上必要なノー
ドの部分しか示されていない。プロセッサP2(52
4)及びプロセッサP4(534)がキャッシュライン
Xのコピーを記憶すると仮定する。キャッシュラインX
のホームノードは、ノード532である。以下の説明に
おいて、次のパケットにより使用されるチャンネルは、
異なる線を用いて指示される。Q0コマンドは、単一線
矢印で指示され、Q1コマンドは、二重線矢印で指示さ
れ、そしてQ2コマンドは、破線矢印で指示される。プ
ロセッサP4がキャッシュラインXの独占的所有権を得
るためにCTD Xを発生すると仮定する。これに応答
して、ディレクトリ存在ビット及びDTAG(図示せ
ず)により、ディレクトリ542は、ノード520へ無
効化を発生する。この無効化は、Q1チャンネルを経て
ノード520のDTAGSを更新し、そしてコピーを有
する全てのプロセッサ(ここではプロセッサP2)に無
効化調査を送信する。
ィレクトリ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はまだ無効化されている。
ローバルポートに「マーカー記入」及びトランザクショ
ン追跡テーブル(図10)を使用することによりこの問
題を克服する。「マーカー記入(Fill Marker)」又は
「マーカー記入変更(Fill Marker Mod)」は、ホームノ
ードのメモリに現在記憶されていないデータに対する
「読み取り」又は「読み取り変更」要求に応答して発生
されるパケットである。即ち、「マーカー記入」又は
「マーカー記入変更」は、「送信読み取り(Forwarded R
ead)」又は「送信読み取り変更(Forwarded Read Mod)」
と同時に発生される。従って、「マーカー記入」及び
「マーカー記入変更」は、Q1チャンネルコマンドであ
る。「送信読み取り」又は「送信読み取り変更」コマン
ドは、キャッシュラインを記憶するプロセッサに送られ
るが、「マーカー記入」又は「マーカー記入変更」の行
先は、元の「読み取り」又は「読み取り変更」を供給し
たプロセッサである。
が、ディレクトリに生じるシリアル化順序を決定できる
ようにする。図31を参照すれば、「マーカー記入」の
適用は、上記問題を次のように矯正する。前記したよう
に、プロセッサ53AがXのCTDをXのホームディレ
クトリに発生し、その結果、「無効化」550がQ1チ
ャンネルを経てノード520へ送られると仮定する。プ
ロセッサP1(522)がRead Mod Xをリモ
ートディレクトリに発生すると、その要求に対してTT
Tエントリが発生される。この要求に対するTTTテー
ブルエントリの例が図32に示されている。TTTテー
ブルエントリは、「ここに記入」及び「マーカーをここ
に記入」状態ビットを含むことに注意されたい。これら
ビットの各々は、ノード520のグローバルポートに各
パケットが受け取られるのに応答してセットされる。T
TTエントリは、「記入」及び「マーカー記入」の両方
が返送されるまでクリアされない。
ッサ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状態を更新させる。
する次の命令であると仮定する。TTTは、「送信読み
取り」命令の状態を決定するためにアクセスされる。こ
の点において、TTTエントリは、「ここに記入」ビッ
トをセットするが、「マーカーをここに記入」ビットは
セットされない。従って、TTTは、無効化及びリモー
ト読み取り動作の相対的なタイミングに関する指示を与
える。Q1コマンドのシリアル化のために、無効化は、
プロセッサ522からのRdModXよりも早い時間に
ディレクトリ542に発生されたと推測でき、従って、
Fill Modが新しいバージョンであり、プロセッ
サ522のデータコピーには無効化が適用されない。そ
の結果、プロセッサP1のDTAGエントリは、無効化
されない。
トに存在するものとして示したが、別の実施形態によれ
ば、各ノードの各プロセッサは、ディレクトリへの要求
を監視することにより共通のアドレスへのリモート要求
の状態を追跡することができる。従って、「マーカー記
入」は、単にTTTへ送られるのではなく、ディレクト
リにより関連プロセッサへ送られる。従って、TTT
は、2つの目的を果たすことが明らかである。マルチプ
ロセッサノードから送出されたコマンドの形式を監視す
ることにより、TTTは、同じアドレスへの他のコマン
ドが完了するまで、あるコマンド(CTDのような)の
送信を禁止することができる。更に、要求がQ2チャン
ネル(「マーカー記入」のような)へ移行したときにT
TTに指示する表示機構を設けることにより、TTTを
用いて、異なるチャンネルに返送されるコマンド(即
ち、Q2記入及びQ1コマンド)間の相対的なタイミン
グ指示を与えることができ、従って、メモリを崩壊する
ことのあるコマンドがプロセッサへ送られるのを防止す
ることができる。
常、リモートアクセスよりも相当に早い。従って、性能
に関しては、ローカル及びリモートアクセスの両方がS
MPシステムにおいて同時に生じることが許される。し
かしながら、ローカルアクセスの発生によりリモートア
クセスに対して停滞の問題を生じさせる幾つかの場合が
ある。例えば、図33Aを参照すれば、1つのプロセッ
サ562がキャッシュラインXにRdXを発生すると仮
定する。キャッシュラインXのホームノードは、ノード
560である。ノード560のディレクトリは、プロセ
ッサ582がキャッシュラインを現在所有することを指
示する。従って、Forwarded Read Xが
582に送られる。
がCTD Xを発生すると仮定する。上記のように、キ
ャッシュラインXは、ノード560に対してローカルで
あり、CTDが成功すると、「無効化」をプロセッサP
1に(及び図示のようにプロセッサP5にも)送る。図
33Bを簡単に参照すれば、参考としてここに取り上げ
る本発明と同日に出願されたバンドレン氏等の「分散型
データ依存性ストール機構(Distributed Data Dependen
cy Stall Mechanism)」と題する特許出願に開示された
ように、プロセッサP1のような各プロセッサは、同じ
キャッシュ位置に対する保留中の読み取りがある場合に
キャッシュへの調査をストールするためのロジックを備
えている。上記の例が与えられると、Read Xの作
用は、ミスアドレスファイル(MAF)574にアドレ
スXを記憶することである。MAFの内容は、到来する
調査に対して比較され、そして到来する調査とMAFの
アドレス間に一致があるときに、調査待ち行列がストー
ルされる。
送されるときに調査待ち行列が解除される。しかしなが
ら、同じ形式のトランザクション(即ち、P5がリモー
トRd Yを実行し、次いで、P6がCTD Yを発生
する)がノード580に生じる場合に、プロセッサP5
の調査待ち行列がストールされ、Read Y要求が満
足されるのを保留する。P2により発生された「無効
化」の後にP5からForwarded Read Y
が送られる状態でP1調査待ち行列がストールされるの
と同時に、P6により発生された「無効化」の後にプロ
セッサP1からForwarded Read Xが送
られる状態でP5の調査待ち行列がストールされた場合
には、停滞が生じる。
策が存在する。第1に、全ての参照をリモートとするこ
とができ、即ち全ての参照を(ホームノードからの参照
も)、それらがホームノードに送られる前にスイッチに
送ることができる。全ての参照がリモートにされた場合
には、上述した中央の順序付けルールに基づき、停滞状
態は生じない。第2の解決策は、キャッシュラインへの
いずれかの参照がリモートから送られたときに所与のキ
ャッシュラインへの全ての参照をストールすることであ
る。しかしながら、この解決策は、これまでのローカル
動作の性能に著しく影響し、それ故、好ましいものでは
ない。本発明の1つの実施形態は、コマンドシャドー作
用の使用によるローカル及びリモート参照の混合により
課せられる潜在的な停滞を克服する。キャッシュライン
Xへのローカル参照がリモートプロセッサへ送られる
と、そのキャッシュラインへのその後の全ての参照がハ
イアラーキースイッチへリモートから送られ、キャッシ
ュラインのローカル参照及びその後の全ての参照が完了
するまで、中央で順序付けされる。従って、まだシャド
ー状態であるキャッシュラインへの以前の参照は、キャ
ッシュラインへの現在の参照もシャドー状態にする。
図34及び35を参照して、上記例をシャドーコマンド
の使用と共に説明する。図35は、TTTの内容を例示
している。第1プロセッサP1は、RdXをアービター
に発生する。上述したように、プロセッサP5へのFR
dXを生じ、これはTTTに記録される。その後、プロ
セッサP2は、CTD XをARBに発生する。ARB
は、TTTを検査し、リモートプロセッサへ送られる保
留中のローカル読み取りがあると決定し、そしてグロー
バルポートからプロセッサP5へInvalXを送る。
又、この動作を表わすエントリもTTTに形成され、そ
のシャドービットがセットされる。
連のトランザクションが生じる。プロセッサ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は、行先ノードへ送られるときにその関連する
「無効化」に先行する。
化」を受け取り、その後、「送信読み取り」を受け取
る。例えば、シリアル化順序を用いて、プロセッサP5
の調査待ち行列は、Inval Yによりストールさ
れ、そしてFrd Xがストールされて、記入を保留す
る。しかしながら、この例では、Frd Yは、Inv
alXの後ではなく、従って、P5調査待ち行列を阻止
しないように「記入」データを与えることができる。リ
モート参照のためにデータが返送されるときには、その
参照に対応するTTTエントリがドロップされる。元の
参照をシャドー処理した他の参照がTTTに存在するこ
とがある。これらコマンドがハイアラーキースイッチか
ら受け取られるときには、シャドー処理されたコマンド
の各々に対するTTTエントリもドロップされる。最終
的に、リモートアクセス及びシャドーアクセスが全て完
了し、そしてTTTがもはやキャッシュラインへマップ
するエントリを含まなくなると、そのキャッシュライン
へのその後のローカル参照をシャドー処理する必要がな
くなる。
ローカル及びリモートコマンドの共存から生じるリソー
ス依存性の停滞を、ハードウェアの複雑さを著しく増加
せずに排除することができる。上記の例は、「送信読み
取り」及びCTDの使用を含むが、シャドーコマンド方
法は、他の形式の命令及びマルチプロセッサにも等しく
適用できることに注意されたい。一般に、ローカルアド
レスXへの参照が存在し、そしてローカルアドレスXへ
の以前のメッセージがリモートプロセッサ(TTTによ
り指示された)へ送られるか、又はXへの以前の参照が
まだシャドー処理されるときには、Xへの現在の参照も
シャドー処理される。更に、この方法は、上記の単なる
マルチプロセッサ/スイッチハイアラーキーよりも多数
のハイアラーキーレベルを含む他の形式のアーキテクチ
ャーにも使用できる。例えば、上記方法は、多数のハイ
アラーキーレベルを含み、コマンドがキャッシュライン
への以前の保留中参照のハイアラーキーレベルに基づい
て適当なハイアラーキーレベルに送られるコンピュータ
システムにも使用できる。
ムに使用するためのアーキテクチャ及びコヒレンスプロ
トコルについて説明した。SMPシステムのアーキテク
チャは、多数のマルチプロセッサノードをスイッチに接
続して最適な性能で動作することのできるハイアラーキ
ースイッチ構造体を備えている。各マルチプロセッサノ
ード内には、マルチプロセッサノードの全てのプロセッ
サを最高の性能で動作できるようにする同時バッファシ
ステムが設けられる。メモリはノード間で共用され、マ
ルチプロセッサノードの各々にメモリの一部分が常駐す
る。マルチプロセッサノードの各々は、メモリコヒレン
ス性を維持するための多数の要素、即ちビクティムキャ
ッシュ、ディレクトリ及びトランザクション追跡テーブ
ルを含む。ビクティムキャッシュは、リモートのマルチ
プロセッサノードに記憶されたメモリを行先とするビク
ティムデータを選択的に更新することができ、これによ
り、メモリの全性能が改善される。ディレクトリに関連
して使用されて、メモリに書きこまれるべきビクティム
を識別する遅延書き込みバッファを各メモリに含ませる
ことによりメモリ性能が更に改善される。
たARBバスは、SMPを経て転送される全てのメッセ
ージに対して中央の順序付けポイントとなる。本発明の
1つの実施形態によれば、メッセージは、多数のトラン
ザクションを含み、各トランザクションは、メッセージ
の処理段階に基づいて多数の異なる仮想チャンネルに指
定される。従って、仮想チャンネルの使用は、システム
順序を維持する簡単な方法を与えることによりデータの
コヒレンス性を維持する上で助けとなる。仮想チャンネ
ル及びディレクトリ構造体を使用すると、従来停滞を生
じるキャッシュコヒレンス性の問題を回避することがで
きる。以上、本発明の好ましい実施形態を説明したが、
その概念を組み込んだ他の実施形態も使用できることが
当業者に明らかであろう。それ故、本発明は、上記の実
施形態に限定されるものではなく、特許請求の範囲のみ
によって限定されるものとする。
タシステムのブロック図である。
タシステムのブロック図である。
サコンピュータノードの1つの一実施形態を示すブロッ
ク図である。
チのデータ経路を示すブロック図である。
形態を示すブロック図である。
るためのロジックの一実施形態を示すブロック図であ
る。
形態を示すブロック図である。
ように拡張された図2のマルチプロセッサコンピュータ
ノードのブロック図である。
のノードを使用して実施されたSMPシステムの一実施
形態を示す図である。
のノードを使用して実施されたSMPシステムの別の実
施形態を示す図である。
におけるエントリーを示す図である。
ランザクション追跡テーブル(TTT)を示す図であ
る。
のハイアラーキー式スイッチを示すブロック図である。
の相互接続ロジックの一実施形態を示すブロック図であ
る。
フローチャートである。
るデータを停止する流れ制御を与えるために図12Aの
相互接続ロジックに使用される方法を示すフローチャー
トである。
行われるアドレス及びデータパケットの転送を示すタイ
ミングである。
するためのバッファロジックの一実施形態を示すブロッ
ク図である。
するためのバッファロジックの別の実施形態を示すブロ
ック図である。
る。
方法を示すフローチャートである。
するためのバッファロジックの別の実施形態を示すブロ
ック図である。
る。
ロセッサ命令―ネットワーク命令の変換を示すテーブル
である。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
にパケットを転送するための多数の通信流を示す図であ
る。
用するためのメモリモジュールのレイアウトを示すブロ
ック図である。。
ジュールにより使用される制御ロジックを示すタイミン
グ図である。
コヒレンス性を維持するためにチャンネルに対してマッ
プされる個別のトランザクションの使用を示すフローチ
ャートである。
ネルを取り扱うための共用待ち行列構造体の一実施形態
を示すブロック図である。
ラーキーチャンネルにおける個々のチャンネルバッファ
の一実施形態を示すブロック図である。
れない場合に生じる問題を説明するためのブロック図で
ある。
トな通信を与えるためのQ1チャンネルにおける流れ及
び順序付けの制約を示すブロック図である。
トな通信を与えるためのQ1チャンネルにおける流れ及
び順序付けの制約を示すブロック図である。
トな通信を与えるためのQ1チャンネルにおける流れ及
び順序付けの制約を示すブロック図である。
ントリーにおおよそのベクトル存在ビットがあるために
生じる曖昧さの問題を説明するブロック図である。
ントリーにおおよそのベクトル存在ビットがあるために
生じる曖昧さの問題を説明するブロック図である。
の曖昧さを防止するために使用される方法を示すブロッ
ク図である。
受け取られるために生じるコヒレンス性の問題を示すブ
ロック図である。
ための記入マーカーの使用を示すブロック図である。
表わすTTTのエントリを示す図である。
コマンドの作用を示すブロック図である。
コマンドの作用を示すブロック図である。
シャドーコマンドの使用を示すブロック図である。
を反映するTTTのエントリを示す図である。
付けを示すフローチャートである。
ル 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 ディレクトリ
Claims (34)
- 【請求項1】 スイッチを経て接続された複数のマルチ
プロセッサノードを備え、これら複数のマルチプロセッ
サノードの各々が少なくとも1つのプロセッサを更に含
むようなマルチ処理システムにおいて、 複数のブロックへと配分される共用メモリと、 上記共用メモリの複数のブロックに個数が対応する複数
のエントリを含むディレクトリとを備え、該ディレクト
リの各エントリは、上記複数のマルチプロセッサノード
のどれがデータブロックのコピーを記憶するか識別する
ためのものであり、上記ディレクトリは、上記複数のブ
ロックへのアクセスを順序付けするためのシリアル化ポ
イントに接続されて、複数のブロック各々への多数の参
照をマルチ処理システムにおいて実質的に同時に実行で
きるようにすることを特徴とするマルチ処理システム。 - 【請求項2】 上記複数のブロック各々への多数の参照
は、少なくとも1つのブロックバージョンの異なるもの
に実質的に同時に作用する請求項1に記載のマルチ処理
システム。 - 【請求項3】 少なくとも1つのブロックバージョンの
各々は、ブロックへの書き込み動作の結果を表わす請求
項2に記載のマルチ処理システム。 - 【請求項4】 上記ディレクトリは、複数のブロックの
1つへの各参照に対して一度だけアクセスされる請求項
1に記載のマルチ処理システム。 - 【請求項5】 上記ディレクトリは、参照の完了の際に
メモリの関連ブロックの状態を反映するように参照の完
了の前に原子的にアクセスされる請求項4に記載のマル
チ処理システム。 - 【請求項6】 参照の1つは、メモリのブロックの1つ
を読み取るための調査型参照であり、参照の1つは、メ
モリのブロックにデータを書き込むための更新型動作で
あり、そしてマルチ処理システムの各ノードは、調査型
動作及び更新型動作のシリアル化順序を決定するための
手段を含む請求項5に記載のマルチ処理システム。 - 【請求項7】 所与のブロックへの更新型参照の後にシ
リアル化された所与のブロックへの調査型参照は、更新
型参照に関連したデータが少なくとも1つのプロセッサ
へ返送される前にマルチプロセッサノードの少なくとも
1つのプロセッサに受け取られ、そしてマルチプロセッ
サノードは、既にシリアル化された更新型参照が完了す
るまで調査型参照をストールする手段を備えている請求
項6に記載のマルチ処理システム。 - 【請求項8】 所与のブロックへの調査型参照は、所与
のブロックへの更新型参照の前にシリアル化され、更新
型参照に関連したデータは、調査型参照の実行の前に受
け取られ、そしてマルチプロセッサノードは、更新型参
照に関連したデータを用いて調査型参照を選択的に実行
する手段を備えた請求項6に記載のマルチ処理システ
ム。 - 【請求項9】 ディレクトリを原子的にアクセスした参
照の完了を保証する手段を更に備えた請求項5に記載の
マルチ処理システム。 - 【請求項10】 完了を保証する上記手段は、複数のマ
ルチプロセッサノード各々の少なくとも1つのプロセッ
サ各々にあって、各変更されたブロックが共用メモリに
書き込まれるまで、及びその変更ブロックに関連した更
新型参照の前にシリアル化された変更ブロックへの全て
の調査型参照が完了するまで、共用メモリの変更ブロッ
クのサブセットを一時的に記憶するための手段を更に含
む請求項9に記載のマルチ処理システム。 - 【請求項11】 完了を保証する上記手段は、複数のマ
ルチプロセッサノードの各々にあって、各変更されたブ
ロックが共用メモリに書きこ込まれるまで、及びその変
更ブロックに関連した更新型参照の前にシリアル化され
た変更ブロックへの全ての調査型参照が完了するまで、
共用メモリの変更ブロックのサブセットを一時的に記憶
するための手段を更に含む請求項9に記載のマルチ処理
システム。 - 【請求項12】 各参照は、複数のトランザクションを
含み、各参照の各トランザクションは、マルチ処理シス
テム内の複数のチャンネルの対応する1つに送られ、そ
してシリアル化順序を決定する上記手段は、複数のチャ
ンネルの少なくとも1つにおいて参照のトランザクショ
ンの順序を維持する手段を備えている請求項6に記載の
マルチ処理システム。 - 【請求項13】 複数のチャンネルの順序付けされたチ
ャンネルは、更新型参照及び調査型参照の相対的な動作
状態を示す情報を搬送する請求項12に記載のマルチ処
理システム。 - 【請求項14】 上記保証手段は、更に、 複数のマルチプロセッサノードの各々にあって、共用メ
モリのブロックの所望のバージョンがマルチプロセッサ
ノードへ返送されるまで多数の参照の1つを遅延する手
段を備えた請求項9に記載のマルチ処理システム。 - 【請求項15】 上記保証手段は、更に、 複数のマルチプロセッサノードの各々にあって、共用メ
モリのブロックの所望のバージョンがマルチプロセッサ
ノードへ返送されるまで多数の参照の1つの実行を遅延
する手段を備えた請求項9に記載のマルチ処理システ
ム。 - 【請求項16】 多数の参照の各々は、複数の段階のト
ランザクションを含み、そして上記保証手段は、各参照
のトランザクションの段階を指示する手段を更に含む請
求項9に記載のマルチ処理システム。 - 【請求項17】 トランザクションの各段階は、異なる
チャンネルを経て送られ、そして参照のトランザクショ
ンの段階を指示する上記手段は、トランザクションの段
階に関連したチャンネルを経て、参照の完了を待機して
いるマルチプロセッサノードへパケットを送信する手段
を備えている請求項16に記載のマルチ処理システム。 - 【請求項18】 上記参照は、マルチプロセッサノード
の第1ノードからマルチプロセッサノードの第2ノード
のディレクトリへ送られる読み取り参照であり、そして
上記パケットは、読み取り参照がマルチプロセッサノー
ドの第2ノードのディレクトリをアクセスしたことを指
示するマーカーパケットである請求項17に記載のマル
チ処理システム。 - 【請求項19】 スイッチを経て接続された複数のマル
チプロセッサノードを備えたマルチ処理システムにおい
て、複数のマルチプロセッサノードの各々は、少なくと
も1つのプロセッサと、 複数のブロックへと配分された共用メモリの一部分と、 上記マルチプロセッサノードの共用メモリの複数のブロ
ックの部分に個数が対応する複数のエントリを有するデ
ィレクトリであって、該ディレクトリの各エントリは、
複数のマルチプロセッサノードのどれがデータブロック
のコピーを記憶するか識別するようなディレクトリと、 上記共用メモリの複数のブロックのサブセットが共用メ
モリに書き込まれるまで共用メモリの複数のブロックの
サブセットを一時的に記憶するビクティムキャッシュと
を備え、上記サブセットの複数のブロックの各々は、マ
ルチプロセッサノードの少なくとも1つのプロセッサの
1つにより更新されることを特徴とするマルチ処理シス
テム。 - 【請求項20】 マルチ処理システムにおいて共用メモ
リの共通ブロックへの多数の参照を同時に実行できるよ
うにする方法であって、上記マルチ処理システムは、ス
イッチを経て接続された複数のマルチプロセッサノード
を備え、複数のマルチプロセッサノードの各々は、少な
くとも1つのプロセッサと、複数のブロックへと配分さ
れた共用メモリの一部分と、シリアル化ユニットとを更
に含み、そしてシリアル化ユニットは、共用メモリの部
分の複数のブロックに個数が対応する複数のエントリを
備え、上記方法は、 上記共通ブロックへの全ての参照を、その共通ブロック
に関連したマルチプロセッサノードのシリアル化ユニッ
トにそれらが受け取られるときに順序付けし、各参照は
実行中に一度だけシリアル化ユニットを訪れ、そして行
先に記憶された共通ブロックへの参照の完了を、上記共
用メモリのブロックの所望バージョンが行先に返送され
るまで遅延する、という段階を含むことを特徴とする方
法。 - 【請求項21】 複数のブロック各々への多数の参照
は、少なくとも1つのブロックバージョンの異なるもの
に実質的に同時に作用する請求項20に記載の方法。 - 【請求項22】 少なくとも1つのブロックバージョン
の各々は、ブロックへの書き込み動作の結果を表わす請
求項21に記載の方法。 - 【請求項23】 上記ディレクトリは、複数のブロック
の1つへの各参照に対して一度だけアクセスされる請求
項20に記載の方法。 - 【請求項24】 上記ディレクトリは、参照の完了時に
メモリの関連ブロックの状態を反映するように参照の完
了の前に原子的にアクセスされる請求項23に記載の方
法。 - 【請求項25】 上記参照の1つは、メモリのブロック
の1つを読み取るための調査型参照であり、上記参照の
1つは、メモリのブロックにデータを書き込むための更
新型動作であり、そして上記方法は、マルチ処理ノード
の各々が各ノードにおける調査型動作及び更新型動作の
シリアル化順序を決定する段階を含む請求項24に記載
の方法。 - 【請求項26】 所与のブロックへの更新型参照の後に
シリアル化された所与のブロックへの調査型参照は、更
新型参照に関連したデータが少なくとも1つのプロセッ
サへ返送される前にマルチプロセッサノードの少なくと
も1つのプロセッサに受け取られ、そして上記方法は、
既にシリアル化された更新型参照が完了するまで調査型
参照をストールする段階を含む請求項25に記載の方
法。 - 【請求項27】 所与のブロックへの調査型参照は、所
与のブロックへの更新型参照の前にシリアル化され、更
新型参照に関連したデータは、調査型参照の実行の前に
受け取られ、そして上記方法は、更新型参照に関連した
データを用いて調査型参照を選択的に実行する段階を含
む請求項25に記載の方法。 - 【請求項28】 ディレクトリを原子的にアクセスした
参照の完了を保証する段階を更に含む請求項24に記載
の方法。 - 【請求項29】 完了を保証する上記段階は、 複数のマルチプロセッサノード各々の少なくとも1つの
プロセッサ各々において、各変更されたブロックが共用
メモリに書き込まれるまで、及びその変更ブロックに関
連した更新型参照の前にシリアル化された変更ブロック
への全ての調査型参照が完了するまで、共用メモリの変
更ブロックのサブセットを一時的に記憶する段階を更に
含む請求項28に記載の方法。 - 【請求項30】 完了を保証する上記段階は、 複数のマルチプロセッサノードの各々において、各変更
されたブロックが共用メモリに書きこ込まれるまで、及
びその変更ブロックに関連した更新型参照の前にシリア
ル化された変更ブロックへの全ての調査型参照が完了す
るまで、共用メモリの変更ブロックのサブセットを一時
的に記憶する段階を更に含む請求項28に記載の方法。 - 【請求項31】 複数のマルチプロセッサノードの各々
において、共用メモリの複数のブロックのサブセットが
共用メモリに書き込まれるまで、マルチプロセッサノー
ドの対応する少なくとも1つのプロセッサにより変更さ
れた共用メモリの複数のメモリのサブセットを一時的に
記憶する段階を更に含む請求項28に記載の方法。 - 【請求項32】 上記多数の参照の各々は、複数の段階
のトランザクションを含み、そして上記方法は、各参照
のトランザクションの段階を指示する段階を含む請求項
20に記載の方法。 - 【請求項33】 トランザクションの各段階は、異なる
チャンネルを経て送られ、そして参照のトランザクショ
ンの段階を指示する上記段階は、トランザクションの段
階に関連したチャンネルを経て、参照の完了を待機して
いるマルチプロセッサノードへパケットを送信する段階
を含む請求項32に記載の方法。 - 【請求項34】 上記参照は、マルチプロセッサノード
の第1ノードからマルチプロセッサノードの第2ノード
のシリアル化ユニットへ送られる読み取り参照であり、
そして上記パケットは、読み取り参照がマルチプロセッ
サノードの第2ノードのシリアル化ユニットをアクセス
したことを指示するマーカーパケットである請求項33
に記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/957565 | 1997-10-24 | ||
| US08/957,565 US6154816A (en) | 1997-10-24 | 1997-10-24 | Low occupancy protocol for managing concurrent transactions with dependencies |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH11282821A true JPH11282821A (ja) | 1999-10-15 |
| JPH11282821A5 JPH11282821A5 (ja) | 2005-12-02 |
Family
ID=25499771
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10340925A Pending JPH11282821A (ja) | 1997-10-24 | 1998-10-26 | 同時トランザクションを依存性で管理するための低占有度プロトコル |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US6154816A (ja) |
| EP (1) | EP0911736A1 (ja) |
| JP (1) | JPH11282821A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2007039933A1 (ja) * | 2005-10-04 | 2007-04-12 | Fujitsu Limited | 演算処理装置 |
| JP2010198490A (ja) * | 2009-02-26 | 2010-09-09 | Fujitsu Ltd | キャッシュ制御装置 |
Families Citing this family (62)
| 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 |
| US7076716B1 (en) * | 1998-04-13 | 2006-07-11 | Intel Corporation | Early acknowledgement of primary packets |
| JP2000010860A (ja) * | 1998-06-16 | 2000-01-14 | Hitachi Ltd | キャッシュメモリ制御回路及びプロセッサ及びプロセッサシステム及び並列プロセッサシステム |
| US6330632B1 (en) | 1998-09-30 | 2001-12-11 | Hewlett-Packard Company | System for arbitrating access from multiple requestors to multiple shared resources over a shared communications link and giving preference for accessing idle shared resources |
| GB2344030B (en) * | 1998-11-17 | 2003-06-04 | 3Com Technologies Ltd | Credit-based scheme for high performance communication between devices in a packet-based communication system |
| US6408362B1 (en) | 1999-06-24 | 2002-06-18 | International Business Machines Corporation | Data processing system, cache, and method that select a castout victim in response to the latencies of memory copies of cached data |
| US6442653B1 (en) * | 1999-06-24 | 2002-08-27 | International Business Machines Corporation | Data processing system, cache, and method that utilize a coherency state to indicate the latency of cached data |
| 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 |
| 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 |
| 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 |
| US6460114B1 (en) * | 1999-07-29 | 2002-10-01 | Micron Technology, Inc. | Storing a flushed cache line in a memory buffer of a controller |
| 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 |
| 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 |
| 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 |
| 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 |
| US6684279B1 (en) | 1999-11-08 | 2004-01-27 | International Business Machines Corporation | Method, apparatus, and computer program product for controlling data transfer |
| 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 |
| US6681320B1 (en) * | 1999-12-29 | 2004-01-20 | Intel Corporation | Causality-based memory ordering in a multiprocessing environment |
| GB0002174D0 (en) | 2000-01-31 | 2000-03-22 | Sgs Thomson Microelectronics | Design flow checker |
| US6904465B2 (en) * | 2001-04-26 | 2005-06-07 | Hewlett-Packard Development Company, L.P. | Low latency inter-reference ordering in a multiple processor system employing a multiple-level inter-node switch |
| US6675264B2 (en) * | 2001-05-07 | 2004-01-06 | International Business Machines Corporation | Method and apparatus for improving write performance in a cluster-based file system |
| US6970980B2 (en) * | 2002-06-28 | 2005-11-29 | Sun Microsystems, Inc. | System with multicast invalidations and split ownership and access right coherence mechanism |
| US6973545B2 (en) * | 2002-06-28 | 2005-12-06 | Sun Microsystems, Inc. | System with a directory based coherency protocol and split ownership and access right coherence mechanism |
| US6970979B2 (en) * | 2002-06-28 | 2005-11-29 | Sun Microsystems, Inc. | System with virtual address networks and split ownership and access right coherence mechanism |
| US7000080B2 (en) * | 2002-10-03 | 2006-02-14 | Hewlett-Packard Development Company, L.P. | Channel-based late race resolution mechanism for a computer system |
| US7051163B2 (en) * | 2002-10-03 | 2006-05-23 | Hewlett-Packard Development Company, L.P. | Directory structure permitting efficient write-backs in a shared memory computer system |
| US6990559B2 (en) * | 2002-10-03 | 2006-01-24 | Hewlett-Packard Development Company, L.P. | Mechanism for resolving ambiguous invalidates in a computer system |
| US6892290B2 (en) * | 2002-10-03 | 2005-05-10 | Hewlett-Packard Development Company, L.P. | Linked-list early race resolution mechanism |
| US7003635B2 (en) * | 2002-10-03 | 2006-02-21 | Hewlett-Packard Development Company, L.P. | Generalized active inheritance consistency mechanism having linked writes |
| US6895476B2 (en) * | 2002-10-03 | 2005-05-17 | Hewlett-Packard Development Company, L.P. | Retry-based late race resolution mechanism for a computer system |
| US7024520B2 (en) * | 2002-10-03 | 2006-04-04 | Hewlett-Packard Development Company, L.P. | System and method enabling efficient cache line reuse in a computer system |
| US7269180B2 (en) * | 2002-11-04 | 2007-09-11 | World Wide Packets, Inc. | System and method for prioritizing and queuing traffic |
| US7000089B2 (en) * | 2002-12-20 | 2006-02-14 | International Business Machines Corporation | Address assignment to transaction for serialization |
| US20050108300A1 (en) * | 2003-11-17 | 2005-05-19 | Terrascale Technologies Inc. | Method for the management of local client cache buffers in a clustered computer environment |
| US7324995B2 (en) * | 2003-11-17 | 2008-01-29 | Rackable Systems Inc. | Method for retrieving and modifying data elements on a shared medium |
| US20050289213A1 (en) * | 2004-06-25 | 2005-12-29 | International Business Machines Corporation | Switching between blocking and non-blocking input/output |
| US7809764B2 (en) * | 2004-11-01 | 2010-10-05 | Microsoft Corporation | Method and apparatus for preserving dependancies during data transfer and replication |
| 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 |
| US7487267B2 (en) * | 2006-02-03 | 2009-02-03 | International Business Machines Corporation | Method and apparatus for managing dependencies between split transaction queues |
| US9262326B2 (en) * | 2006-08-14 | 2016-02-16 | Qualcomm Incorporated | Method and apparatus to enable the cooperative signaling of a shared bus interrupt in a multi-rank memory subsystem |
| US8195890B1 (en) * | 2006-08-22 | 2012-06-05 | Sawyer Law Group, P.C. | Method for maintaining cache coherence using a distributed directory with event driven updates |
| US7593279B2 (en) * | 2006-10-11 | 2009-09-22 | Qualcomm Incorporated | Concurrent status register read |
| US20080098178A1 (en) * | 2006-10-23 | 2008-04-24 | Veazey Judson E | Data storage on a switching system coupling multiple processors of a computer system |
| JP2011503710A (ja) * | 2007-11-09 | 2011-01-27 | プルラリティー リミテッド | しっかりと連結されたマルチプロセッサのための共有メモリ・システム |
| US8306809B2 (en) * | 2008-07-17 | 2012-11-06 | International Business Machines Corporation | System and method for suggesting recipients in electronic messages |
| US20130086328A1 (en) * | 2011-06-13 | 2013-04-04 | Paneve, Llc | General Purpose Digital Data Processor, Systems and Methods |
| US9075723B2 (en) * | 2011-06-17 | 2015-07-07 | International Business Machines Corporation | Efficient discard scans |
| US9280468B2 (en) | 2011-10-26 | 2016-03-08 | Qualcomm Technologies, Inc. | Three channel cache-coherency socket protocol |
| FR2989489B1 (fr) | 2012-04-16 | 2015-11-27 | Commissariat Energie Atomique | Systeme et procede de gestion d'une coherence de caches dans un reseau de processeurs munis de memoires caches. |
| US9514069B1 (en) | 2012-05-24 | 2016-12-06 | Schwegman, Lundberg & Woessner, P.A. | Enhanced computer processor and memory management architecture |
| US9561469B2 (en) * | 2014-03-24 | 2017-02-07 | Johnson Matthey Public Limited Company | Catalyst for treating exhaust gas |
| US10642780B2 (en) | 2016-03-07 | 2020-05-05 | Mellanox Technologies, Ltd. | Atomic access to object pool over RDMA transport network |
| GB2548845B (en) | 2016-03-29 | 2019-11-27 | Imagination Tech Ltd | Handling memory requests |
| US10504045B2 (en) * | 2016-10-27 | 2019-12-10 | Sap Se | Audit schedule determination |
| US10846230B2 (en) * | 2016-12-12 | 2020-11-24 | Intel Corporation | Methods and systems for invalidating memory ranges in fabric-based architectures |
| US10552367B2 (en) | 2017-07-26 | 2020-02-04 | Mellanox Technologies, Ltd. | Network data transactions using posted and non-posted operations |
| US10210090B1 (en) * | 2017-10-12 | 2019-02-19 | Texas Instruments Incorporated | Servicing CPU demand requests with inflight prefetchs |
Family Cites Families (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE68924306T2 (de) * | 1988-06-27 | 1996-05-09 | Digital Equipment Corp | Mehrprozessorrechneranordnungen mit gemeinsamem Speicher und privaten Cache-Speichern. |
| CA2047888A1 (en) * | 1990-07-27 | 1992-01-28 | Hirosada Tone | Hierarchical memory control system |
| US5303362A (en) * | 1991-03-20 | 1994-04-12 | Digital Equipment Corporation | Coupled memory multiprocessor computer system including cache coherency management protocols |
| JPH05108473A (ja) * | 1991-03-20 | 1993-04-30 | Hitachi Ltd | デ−タ処理システム |
| 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 |
| US5331673A (en) * | 1992-03-30 | 1994-07-19 | International Business Machines Corporation | Integrity of data objects used to maintain state information for shared data at a local complex |
| 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 |
| US5581729A (en) * | 1995-03-31 | 1996-12-03 | Sun Microsystems, Inc. | Parallelized coherent read and writeback transaction processing system for use in a packet switched cache coherent multiprocessor 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 |
-
1997
- 1997-10-24 US US08/957,565 patent/US6154816A/en not_active Expired - Lifetime
-
1998
- 1998-10-12 EP EP98308284A patent/EP0911736A1/en not_active Ceased
- 1998-10-26 JP JP10340925A patent/JPH11282821A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2007039933A1 (ja) * | 2005-10-04 | 2007-04-12 | Fujitsu Limited | 演算処理装置 |
| JP2007102447A (ja) * | 2005-10-04 | 2007-04-19 | Fujitsu Ltd | 演算処理装置 |
| JP2010198490A (ja) * | 2009-02-26 | 2010-09-09 | Fujitsu Ltd | キャッシュ制御装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| US6154816A (en) | 2000-11-28 |
| EP0911736A1 (en) | 1999-04-28 |
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 | |
| US6094686A (en) | Multi-processor system for transferring data without incurring deadlock using hierarchical virtual channels | |
| US6101420A (en) | Method and apparatus for disambiguating change-to-dirty commands in a switch based multi-processing system with coarse directories | |
| 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 | |
| JP6802287B2 (ja) | キャッシュ・メモリ・アクセス | |
| US5900020A (en) | Method and apparatus for maintaining an order of write operations by processors in a multiprocessor computer to maintain memory consistency | |
| US7120755B2 (en) | Transfer of cache lines on-chip between processing cores in a multi-core system | |
| US6085263A (en) | Method and apparatus for employing commit-signals and prefetching to maintain inter-reference ordering in a high-performance I/O processor | |
| US20070081516A1 (en) | Data processing system, method and interconnect fabric supporting multiple planes of processing nodes | |
| US20030145136A1 (en) | Method and apparatus for implementing a relaxed ordering model in a computer system | |
| JP7419261B2 (ja) | ストリーミングデータ転送のためのフロー圧縮を用いたデータ処理ネットワーク | |
| JP4410967B2 (ja) | デッドロックのないコンピュータシステム動作のためのバーチャルチャネルおよび対応するバッファ割当て | |
| KR100387541B1 (ko) | 멀티프로세서 시스템에서 캐쉬 코히어런시 유지 방법, 멀티프로세서 시스템 및 노드 제어기 | |
| US6266743B1 (en) | Method and system for providing an eviction protocol within a non-uniform memory access system | |
| WO2000036514A1 (en) | Non-uniform memory access (numa) data processing system that speculatively forwards a read request to a remote processing node | |
| JP2000227908A (ja) | 共用介入サポ―トを有する不均等メモリ・アクセス(numa)デ―タ処理システム | |
| JP2005539282A (ja) | 単一のコヒーレントなシステム内の分散コンピュータ・ノードにキャッシュ・コヒーレンスを提供するのにグローバル・スヌープを使用する方法および装置 | |
| US8102855B2 (en) | Data processing system, method and interconnect fabric supporting concurrent operations of varying broadcast scope | |
| US6892283B2 (en) | High speed memory cloner with extended cache coherency protocols and responses | |
| US20040111575A1 (en) | Dynamic data routing mechanism for a high speed memory cloner |
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: 20071218 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20080428 |