JPH0222580B2

JPH0222580B2 -

Info

Publication number: JPH0222580B2
Application number: JP58202472A
Authority: JP
Inventors: Konaado Aren Jeimuzu; Boora Baatoretsuto Uendei; Suchiiunsu Jonson Hooku; Dereku Futsushaa Suchiibun; Oriuaa Raason Richaado; Chaaruzu Petsuku Jon
Original assignee: Tandem Computers Inc
Current assignee: Tandem Computers Inc
Priority date: 1982-10-28
Filing date: 1983-10-28
Publication date: 1990-05-21
Also published as: US4667287A; JPS59132263A

Description

【発明の詳細な説明】本発明はマルチプロセツサ・コンピユータ・シ
ステムに関するものであり、更に詳しくいえば、
１つのシステムからのプロセツサが別のシステム
からのプロセツサと交信する方法およびマイクロ
プロセツサ・コンピユータ・システムのマルチシ
ステム・ネツトワークに関するものである。

別々に管理されるシステムの間で交信する必要
のある用途のような多くの用途においては、２台
またはそれ以上のマルチプロセツサ・システムを
ネツトワークで互いに接続することが望ましい。
また、マルチプロセツサ・システムに含むことが
できるプロセツサの数には実際上の制限がある。
システムのサイズの限界に達すると、処理能力を
更に拡張できる唯一の方法は、２つまたはそれ以
上のマルチプロセツサ・システムをネツトワーク
で互いに接続することである。

マルチプロセツサ・システムをネツトワークで
互いに接続する場合には、各システム中の１台の
プロセツサを通信リンクおよびシステム間通信マ
ネジヤーとして用いることが普通である。この専
用プロセツサはそのネツトワーク中のプロセツサ
間の全ての通信を取扱う。

このやり方によりプロセツサ間のシステム間通
信を行うことができるが、全てのプロセツサの通
信を流す通信リンクとして１台のプロセツサを用
いると、情報伝達の量と速度を制限する隘路が生
ずることになる。どのようなコンピユータ・シス
テムにおいても高速かつ大量の処理能力を有する
ことが常に望ましく、システム間通信を迅速かつ
効率良く行うマルチシステム・ネツトワークが要
望されている。

本発明は、ネツトワークを構成する任意の１つ
のシステム中の任意のプロセツサと、任意のシス
テム中の別のプロセツサとが通信できるようにす
るマルチシステム・ネツトワークを提供するもの
である。各マルチプロセツサ・システム、すなわ
ちクラスタ、には１つのノードが関係づけられて
おり、そのノードを介して前記各クラスタは、他
のマルチプロセツサ・システムに関係する他のノ
ードへ、データ・リンクを経て結合される。

各ノードは、マルチプロセツサ・システムの前
記ノードに関係するローカルプロセツサ間バス
と、ネツトワーク内でシステムを互いに接続する
データ・リンクとの間のインターフエースであ
る。各ノードには回路と、フアームウエア、およ
び情報の転送を管理・指令するためのソフトウエ
ア以外に一途のバツフア記憶場所が設けられてい
る。各記憶場所は複数の情報パケツトを格納する
容量を有し、かつ各記憶場所はネツトワーク内の
ある特定のプロセツサの専用として用いられる。

ネツトワーク内の任意のシステム中の任意のプ
ロセツサが、そのネツトワーク内の他の任意のシ
ステム中の他の任意のプロセツサへ情報を送信し
ようとする場合はいつでも、ネツトワークは送り
側プロセツサからの情報を、ノードの制御の下
に、それに関係しているノード内のバツフア記憶
場所のうち、宛先のプロセツサに対応する１つの
記憶場所へプロセツサ間バスを経て通す。それか
ら、その情報はノードの制御の下にデータ・リン
クを通つてネツトワーク中の隣のノードへ送ら
れ、その次に、そのノードの制御の下に、宛先の
プロセツサに対応するバツフアメモリの一つの記
憶場所に置かれる。

その情報は、受信ノードに関係するマルチプロ
セツサ内のプロセツサへ宛てられているのでその
受信ノードにより情報が確認されるまで、以上説
明したようにして順次各ノードへ送られる。情報
は、それが置かれていたバツフア記憶場所から、
そのノードの制御の下に、ローカルのプロセツサ
間バスを経て宛先のプロセツサへ送られる。

本発明のノードはいくつかのやり方のうちの１
つのやり方で互いに接続できる。それらのやり方
には、開放チエーンによる直線的な接続、星形す
なわちハブおよびスポーク状接続、または冗長接
続グラフのようなあるハイブリツドの組合せ、な
ども含まれる。ネツトワークの誤り許容性を高く
するように冗長路を設けるために、各マルチプロ
セツサ・システムには１つ以上のノードを組合せ
ることができる。

このネツトワークを通る情報の流れを管理する
ために、ノードは隣接するノードと交信してバツ
フア・スペースを利用できるか否かを指示する。
与えられた任意のノードに送つて来られるように
なつている任意の情報パケツトを格納するため
に、そのノード内のある特定の宛先プロセツサに
割当てられているバツフア・スペースを利用でき
ることを確実にするために、スタート・メツセー
ジとストツプ・メツセージが送られる。ある与え
られたプロセツサに宛てられたパケツトには順次
番号をつけることができ、誤りの検出と訂正を行
えるようにFIFOのやり方でバツフアは管理され
る。

本発明のネツトワークの好適な実施例は、各ク
ラスタ自体がマルチプロセツサ・システムである
ような、クラスタのリングで構成される。各クラ
スタは２つのクラスタ・モジユールに接続され、
各クラスタ・モジユールは２つの双方向リンクに
より隣接する他の２つのクラスタ・モジユールに
接続されて、二重の双方向リングを形成する。任
意のクラスタ中の任意のプロセツサは任意のクラ
スタ中の他の任意のプロセツサと通信できるが、
各クラスタ・モジユールは隣接する２つのクラス
タ・モジユールとだけ直接交信できる。

各クラスタ・モジユールは、各クラスタを直列
データ・リンクとローカル・システムのプロセツ
サ間バス（IPB）に接続するためのインタフエー
ス・ノードとして機能する。各インタフエース・
ノードには一連のバツフア記憶場所が含まれる。
各バツフア記憶場所は、複数の情報パケツトを格
納するたの容量を有し、ネツトワーク内の特定の
プロセツサの専用にされる。クラスタ・リングを
回る向きは２つあるから、リングを回る各向き
（左または右）のために別々のバツフア群が設け
られる。ネツトワーク内の任意のプロセツサのた
めのパケツトは１度に１つのクラスタ・モジユー
ルをつぎつぎに通つて、リングの中を与えられた
向きに送られる。各クラスタ・モジユールにおい
てバケツトは、メツセージを受ける宛先プロセツ
サに関係するバツフア内に置かれる。

２つのリングがあり、かつ各リングには２つの
可能な回る向きがあるから、４つの可能なメツセ
ージ経路が存在することになる。システムはメツ
セージを可能な最短経路を通つてメツセージを送
ろうとする。選択した経路に異常があると、シス
テムはメツセージを交替の経路を介して送る。

プロセツサ間の通信の処理を効率良く行うため
に、バツフア・メモリ制御回路はバツフア容量の
上限しきい値と下限しきい値を利用し、それらの
しきい値に達した時には、クラスタ・モジユール
制御器が、その特定の宛先へ宛てられるパケツト
の送信を停止または開始することを、隣接するク
ラスタ・モジユール（およびそれのローカル・プ
ロセツサ間バス）へ知らせることを指令する。あ
る与えられたプロセツサへ送られるパケツトには
順次番号がつけられ、誤りの検出と訂正を行える
ようにするために、FIFOのやり方でそれらのバ
ツフアは管理される。１つのプロセツサまたはプ
ロセツサ群を他のプロセツサまたは他プロセツサ
群よりもとくに使用されるというようなことを避
けるために、ある任意の時刻に送るためにどのプ
ロセツサ間パケツトを選択するためのアルゴリズ
ムが用意される。

本発明の目的は、先行技術の諸欠点を解消した
マルチシステム・マルチプロセツサ・システム相
互通信を行うことである。

本発明の他の目的は、従来可能であつたものよ
りも高い速度で行われるマルチシステム・マルチ
プロセツサ相互通信装置を得ることである。

本発明の別の目的は、マルチシステム・マルチ
プロセツサ相互通信を管理するために１台の専用
プロセツサを使用する必要のない、マルチシステ
ム・マルチプロセツサ相互通信装置を得ることで
ある。

本発明の更に別の目的は、信頼度を高くするた
めにいくつかの冗長経路を利用する環境におい
て、マルチシステム・マルチプロセツサ通信装置
を得ることである。

以下、図面を参照して本発明を詳しく説明す
る。

米国特許第4228496号明細書に開示されている
ような種類のマルチプロセツサ・システムを採用
しているマルチシステム・マルチプロセツサ機に
関連して本発明を用いるために、本発明の好適な
実施例を開示しようとするものであるが、他の構
成のマルチプロセツサ・システムにも本発明を容
易に適用できることは当業者には明らかであろ
う。

第１図は、プロセツサ１０を有するマルチプロ
セツサ・システムのプロセツサ間通信部分とプロ
セツサを示すものである。各プロセツサ１０はＸ
プロセツサ間バス１２とＹプロセツサ間バス１４
に接続される。各プロセツサ間バス１２，１４は
同じプロセツサ間バス制御器（IPB制御器）１６
に接続される。このIPB制御器１６は、米国特許
第4228496号明細書に開示されているやり方で、
データの流れと、プロセツサ１０のその他の動作
を制御する。

第１図から明らかなように、各プロセツサ
（P₀〜P_o）１０はプロセツサ間バス１２または１
４のいずれかを介して互いに通信できる。それら
のバスは、システムの１つの部分の部品が故障し
た時にも、システムが動作を継続できるようにす
るための冗長経路を構成するものである。この好
適な実施例を説明するために、個々の各マルチプ
ロセツサ・システム中のプロセツサの数を16（ｎ
＝16）としたが、異なる数のプロセツサに合わせ
て指令語フイールド長、レジスタ長を少し変更
し、かつその他のハードウエア／スフトウエアに
対して明らかな変更を施すことにより、本発明の
装置は16より多いか、少い数のプロセツサで動作
することが当業者にはわかるであろう。

本発明が開示されるのは第１図に示されている
種類のマルチプロセツサ・システムに関してであ
るが、米国特許第4228496号明細書に開示されて
いる装置における多重経路冗長性を持たないマル
チプロセツサ・システムにも等しく本発明を適用
できることを当業者は認められるであろう。しか
し、そのようなネツトワークは同数の可能なデー
タ経路を有しないことがわかるであろう。

次に第２図を参照する。この図には本発明に従
つて構成されたシステム・ネツトワークの基本的
なビルデイング・ブロツクが示されている。第１
図に示されているのと同様に、第２図のマルチプ
ロセツサ・システムは、Ｘプロセツサ間バス１２
とＹプロセツサ間バス１４をそれぞれ介して通信
する複数のプロセツサ１０を含む。しかし、第１
図に示されている装置とは異なり、第２図に示さ
れているマルチプロセツサ・システムは、それの
Ｘプロセツサ間バス１２とＹプロセツサ間バス１
４のためのインターフエースとして機能するIPB
制御器を有しない。その代りに、ＸとＹの各バス
１２，１４において、本発明において用いられて
いる各マルチプロセツサ・システムはＸクラス
タ・モジユール１８とＹクラスタ・モジユール２
０を介してネツトワークに対するインタフエース
機能を行う。Ｘクラスタ・モジユール１８はＸバ
スに接続され、Ｙクラスタ・モジユール２０はＹ
バスに接続される。Ｘ左直列データ・リンク２２
の一部とＸ右直列データ・リンク２４の一部がＸ
クラスタ・モジユール１８から出ており、Ｙ左直
列データ・リンク２６の一部とＹ右直列データ・
リンク２８の一部がＹクラスタ・モジユール２０
から出ていることが図からわかる。ＸとＹのクラ
スタ・モジユール１８，２０の構造は同じで、二
重リング・ネツトワークの基礎を形成するもので
ある。

第４図を参照するともつと良くわかるように、
ＸとＹのクラスタ・モジユール１８，２０は、Ｘ
とＹのプロセツサ間バス１２または１４と直接イ
ンターフエースするプロセツサ間バス制御器
（IPB制御器）３０を含む。本発明におけるIPB
制御器３０の機能は、下記の３つの面を除き、シ
ステム間ローカル・プロセツサ間バスを制御する
目的で米国特許第4228496号明細書に開示されて
いるプロセツサ間バス制御器について説明されて
いるのと同じである。

その米国特許明細書に開示されているマルチプ
ロセツサ・システムにおいては、いずれかのプロ
セツサ１０が他のプロセツサ１０へ送るべきメツ
セージを有すかどうかを確かめるために、個々の
プロセツサ１０は順次ポールされる。このポーリ
ング動作は、他のプロセツサへ送るべきパケツト
をあるプロセツサか有することを示す信号
SNDREQが、プロセツサ間バスの制御ビツト部
分から受けたIPB制御器により開始される。

本発明においては、SNDRO信号が常に主張さ
れると仮定している。その結果、いずれかのプロ
セツサが同じシステム内の他のプロセツサへ、ま
たはネツトワーク中の他のシステム内のプロセツ
サへ送るべきパケツトを有するかどうかを確認す
るために、プロセツサは絶えずポールされる。
IPB制御器３０とクラスタ・モジユール１８のこ
の面の動作については第４図と第１１図を参照し
て詳しく説明することにする。

また、米国特許第4228496号明細書に開示され
ているシステムにおいて用いられている順次ポー
リングではなくて、非順次式にポーリングするこ
とが好ましいが、本発明においては順次ポーリン
グ動作も行われる。

第３の相違は、後で詳しく説明するように、外
部ソースとの間でパケツトをやりとりする性能が
本発明のIPB制御器に付加されていることであ
る。

本発明のマルチシステム・ネツトワークは、第
２図に示されているシステムがいくつか互いに接
続されて、任意のプロセツサが１メガバイト／秒
というような高速度で他のプロセツサと通信でき
るようにするネツトワークを構成することにより
完成される。本発明のネツトワークではそのよう
な高速通信が可能であるが、従来の通信リンクを
用いると通信速度は僅かに7000バイト／秒と非常
に低い。そのようなネツトワークの構成が第３図
に示されている。

第３図に示されている、いくつかのマルチプロ
セツサ・システムの二重双方向リング状ネツトワ
ークは、インターフエースのＸとＹのクラスタ・
モジユール１８と２０にそれぞれ終端させられて
いるＸとＹのプロセツサ間バス１２，１４に接続
されているプロセツサ１０を備えている。第３図
には、Ｘクラスタ・モジユール１８ａ，１８ｂ，
１８ｃ，１８ｎとＹクラスタ・モジユール２０
ａ，２０ｂ，２０ｃ，２０ｎを介して二重双方向
リング・ネツトワークに形成された４つのそのよ
うなシステムが示されているだけであるが、ここ
で説明している好適な実施例においては、クラス
タ番号０がローカル・プロセツサ間バス転送を示
すために留保され、クラスタ番号１５がクラス
タ・モジユールをモニタおよび制御するために留
保されているから、第３図に示されているのに類
似するリング構造に構成される14台までのマルチ
プロセツサ・システムを設けることができる。本
発明の技術的思想を逸脱することなしにより多く
の、またはより少い数のマルチプロセツサ・シス
テムを使用できる。どのように多数の、またはど
のように少数のマルチプロセツサ・システムで
も、本発明に従つて構成できることを、この明細
書の説明から当業者は容易に理解できるであろ
う。

第３図において、二重リング構造の１つのリン
グがそれのノードとしてＸクラスタ・モジユール
１８を有するものとして示され、他のリングがそ
れのノードとしてＹクラスタ・モジユール２０を
有するものとして示されている。Ｘクラスタ・モ
ジユールはＸ左側リンク２２ａ，２２ｂ，２２
ｃ，２２ｄとＸ右側リンク２４ａ，２４ｂ，２４
ｃ，２４ｄの直列データ・リンクにより互いに接
続される。その名称により示唆されているよう
に、各リンク２２，２４はデータを１つの向きに
だけ転送する。同様に、Ｙクラスタ・モジユール
２０はＹ左側リンク２６ａ，２６ｂ，２６ｃ，２
６ｄとＹ右側リンク２８ａ，２８ｂ，２８ｃ，２
８ｄを介して互いに接続される。したがつて、１
つのクラスタ・モジユールから別のクラスタ・モ
ジユールへ情報を送るためにとることができる経
路はリンク２２，２４，２６，２８の４つあるこ
とがわかる。

データ伝送用のために知られている高速光フア
イバ・ケーブルをリンク２２，２４，２６，２８
に用いることが好ましい。そのような光フアイ
バ・ケーブルは公知の光フアイバ・インタフエー
ス（図示せず）を用いて、ＸとＹのクラスタ・モ
ジユール１８，２０に接続される。リンク２２〜
２８としては光フアイバ・ケーブルの代りに電気
ケーブルも使用できるが、いずれを用いるにして
もこれ以上の説明は不要であることがわかるであ
ろう。

クラスタ間の通信に使用できる多数のハードウ
エア経路のために、設けられているデータ路の冗
長性によりもつと信頼度の高いシステムが可能で
あるばかりでなく、それらのデータ路は独立して
動作でき、かつ同時に使用できるために、１リン
グ経路を使用した時に可能である処理量の４倍ま
で処理することが可能であることがわかるであろ
う。

リングを介してシステム間を伝わる、すなわ
ち、１つのシステム内のプロセツサ１０から別の
システムのプロセツサ１０へ伝えられる情報の管
理と制御は、クラスタ・モジユール１８，２０に
内蔵されているロジツクとインテリジエンスによ
り取扱われる。

本発明に従つて構成されたマルチシステム・ネ
ツトワーク内の各Ｘクラスタ・モジユール１８
は、それに隣接する２つのクラスタ・モジユール
とだけ直接通信する。たとえば、第３図に示され
ているＸクラスタ・モジユール１８ｂは左隣のＸ
クラスタ・モジユール１８ａおよび右隣のＸクラ
スタ・モジユール１８ｃとだけ通信する。同様
に、Ｙクラスタ・モジユール２０ｂは左隣と右隣
のＹクラスタ・モジユール２０ａ，２０ｂとだけ
直接通信する。

ＸとＹのクラスタ・モジユールの構造は同じ
で、同じように機能するから、ネツトワークの動
作についての説明は、Ｘクラスタ・モジユール１
８だけ参照して行うことにするが、その説明はＹ
クラスタ・モジユール・リングをいずれの向きに
送られるパケツトの転送にも等しく適用できるこ
とがわかるであろう。

各クラスタ・モジユール１８は隣接する２つの
クラスタ・モジユールとだけ直接通信できるか
ら、過度に複雑なシステム制御は不要である。ど
のクラスタ・モジユール１８も、左隣り、右隣
り、およびプロセツサ間バス１２に接続されてい
るプロセツサ１０との３つの向きでパケツトを送
受信することによつて通信できる。

たとえば、第３図のクラスタ・モジユール１８
ｂは、Ｘ左側直列データ・リンク２２ｂを介して
クラスタ・モジユール１８ａへ、Ｘ右側直列デー
タ・リンク２４ｃを介してクラスタ・モジユール
１８ｃへ、およびローカルＸプロセツサ間バス１
２ｂを介して任意のプロセツサ１０パケツトを送
ることができる。

プロセツサは他のどのプロセツサとも通信でき
るから、どのノードも任意のプロセツサにより送
ら、および任意のプロセツサへ宛てられるトラフ
イツクを取扱うことができなければならず、か
つ、この情報転送の大きな可能性を効率良く管理
するための何らかの手段を備えなければならな
い。

本発明においては、クラスタ・モジユール１８
ｂ（全てのクラスタ・モジユール１８の例として）
が、内部に設けられているバツフア・メモリを介
て行われるそれらの全てのパケツトの転送を管理
する。全体のリング中の各プロセツサに、一定数
のパケツトを格納するための容量を持つバツフ
ア・メモリ内のあるスペースが割当てられるよう
に、バツフア・メモリは構成される。その容量の
うちの半分が左向きへの転送に使用され、残りの
半分が右向きへの転送に用いられる。与えられた
任意のプロセツサへ宛てられたパケツトが送られ
る順序と同じ順序で届けられるように、各プロセ
ツサに割当てられたスペースはFIFOキユーとし
て配列される。宛先のプロセツサがそれに送られ
た全てのパケツトを受けたことを確認して、誤り
の検出と訂正を行うためにそのプロセツサは単一
シーケンス検査を使用できる。

ここで説明している好適な実施例においては、
リングを回る各向きにおけるネツトワーク内の各
プロセツサのためのバツフア・メモリ・スペース
には16個のパケツトが入るが、当業には容易にわ
かるであろうように、ハードウエアとソフトウエ
アを適切かつ明らかなやり方で変更することによ
り、16個とは異なる数のパケツト容量とすること
ができる。本発明のこの特徴と、以下に行う説明
は第４図を参照することにより容易に理解でき
る。

第４図を参照して、クラスタ・モジユール１８
ｂはIPB制御器３０と、クラスタ・モジユール制
御器３２と、バツフア・メモリ３４と、直列デー
タ・リンク制御器３６との４つの主な機能ブロツ
クで構成される。

IPB制御器３０は、Ｘプロセツサ間バス１２ｂ
上に配置されているプロセツサ間の全てのローカ
ル・パケツト転送（ローカル転送）と、プロセツ
サ間バス１２ｂ上の任意のプロセツサとリングの
間のパケツトの転送とを取扱う。

クラスタ・モジユール３２は、バツフア・メモ
リ３４と共同して、クラスタ・モジユール１８ｂ
を含んでいるノードとの間の全てのパケツト転送
を管理および制御する。クラスタ・モジユール３
２は、プロセツサ間バス１２ｂ上に配置されてい
るプロセツサの範囲をこえるパケツトの転送と、
直列データ・リンク制御器３６を介してのノード
におけるパケツトのやりとり転送とに関するIPB
制御器３０の動作の制御も行う。直列データ・リ
ンク制御器３６はノードと直列データ・リンク２
２，２４との間のパケツトの実際の転送を行う。

クラスタ・モジユール２８ｂの動作は、そのモ
ジユールがパケツトを送信および受信する時の機
能を考えることにより最もよく理解できる。

パケツトをバツフア・メモリ３４からとり出す
時は、それらのパケツトはローカルＸプロセツサ
間バス１２ｂ上のプロセツサと、またはクラス
タ・モジユール１８ａまたは１８ｂ内の隣りのバ
ツフア・メモリ３４とのいずれかの２つの可能な
宛先へ向けられる。

パケツトをバツフア・メモリ３４から隣りのク
ラスタ・モジユール１８ａまたは１８ｃへ送る時
は、直列データ・リンク制御器３６が含まれる。
直列データ・リンク制御器３６はクラスタ・モジ
ユール制御器インターフエース３８と、パケツト
を送受信するための他のハードウエアを含んでい
ることがわかる。

とくに、直列データ・リンク制御器３６は左
OUTQバツフア４０と、右OUTQバツフア４２
と、左並列−直列変換器およびCRC（周期的冗長
性検査）発生器４４と、右並列−直列変換器およ
びCRC発生器４６と、左送信器４８と、右送信
器５０と、左受信器５８と、右受信器６０と、左
直列−並列変換器およびCRC検査器６２と、右
直列−並列変換器およびCRC検査器６４と、左
INQバツフア６６と、右INQバツフア６８とを
含む。CRC発生器は、誤り検出のために、CRC
−16検査語を送られるデータにかぶせて発生す
る。この検査語はデータ・フレームの最後の語と
して送られる。受信器におけるCRC検査器は、
フレーム全体（送られるCRC語を含む）にわた
つてCRC語を計算し、計算された語が零である
ことを確認することにより、受けたフレームに誤
りがないことを検査する。CRC検査技術はこの
技術分野において周知のものである。

直列データ・リンクの左側と右側の部分は同じ
であるから、左側部分だけを説明することにす
る。

直列データ・リンクを介して送られるパケツト
はフレーム内に含まれる。パケツトに加えて、各
フレームは２つの制御語と１つのCRC語を含む。
制御語は流れ制御のため、とくにスタート・メツ
セージとストツプ・メツセージのために用いられ
る。受信器へのフレームの送信中の誤りを検出す
るために、CRC語はフレーム全体にわたつて計
算される。「制御のみ」フレームと呼ばれるもう
１つの種類のフレームがある。その「制御のみ」
フレームは、データ・パケツトの代りに、更に16
語の制御語を含むことができる（全部で18の制御
語と２つのCRC語である）。制御のみフレーム
は、与えられた任意の時刻に隣りへ２語以上の制
御語を送る必要がある場合、任意の制御語を送る
必要があり、送信すべきデータパケツトがない場
合、あるいは全体のネツトワークを更新するため
に周期的に制御語が循環させられる場合に使用で
きる。ある好適な実施例においては、スタート制
御語が失われるおそれがあるために、それに対処
する必要があるためあるいはそうでなくとも制御
のみフレームを10ミリ秒ごとに送られる。

左OUTQバツフアは、左直列データ・リンク
２０を介しての伝送を待つ２つの情報パケツトを
格納する容量を有する二重バツフアとすることが
できる。そのバツフアの１つまたは両方の部分が
空の時は、バツフアはバツフアが一杯になつてい
ないことを示すフラグを発生する。そのフラグは
クラスタ・モジユール制御器３２により読まれ
る。左OUTQバツフア４０の両方の部分が一杯
の時はこのフラグは発生されず。後で詳しく説明
するように、そのバツフアに含まれているパケツ
トは転送される。

しかし、左OUTQバツフア４０がそれのバツ
フアが一杯でないフラグを主張すると、クラス
タ・モジユール制御器３２は、左直列データ・リ
ンクへ送るために、バツフア４０に含ませるパケ
ツトをバツフア・メモリ３４からとり出す。この
目的のために、クラスタ制御器３２は、それの制
御メモリ５０に「レデイ・リスト」で格納されて
いる情報を用いる。このレデイ・リストは、この
分野で知られているように、二重にリンクされた
リストとすることができる。その二重にリンクさ
れたリストにおいては、リスト中の各項目はリス
ト中の先行の項目と次の項目に対する参照アドレ
スを有し、次のようにして機能する。

クラスタ・モジユール１８ｂにパケツトが到達
すると、そのパケツトに割当てられている宛先ク
ラスタ番号の識別と宛先プロセツサ番号の識別を
含むパケツト語をクラスタ・モジユール制御器３
２が調べる。それらの番号は、そのパケツトがリ
ングを回る向きを示すビツトが組合わされてお
り、制御メモリ５２内のレデイ・リストにおける
アドレスとして用いられる。このアドレスには一
連の記憶場所より表がある。その表における１つ
の場所は、FIFOキユーにおける最も古いパケツ
ト（そのキユーの先頭）を示すバツフア・メモ
リ・アドレスである。FIFOキユーの最後尾（そ
こに次のパケツトが置かれる）を指すバツフア・
メモリ・アドレスは、パケツト・カウント（次に
説明する）、モジユロ１６、をキユポインタのヘ
ツドに加え合わせることにより得られる。その表
中の別の場所は、ある特定のクラスタとプロセツ
サに宛てられた、バツフア・メモリ３４に格納さ
れているパケツトの数の記録（パケツト・カウン
ト）を含む。その数は、あるパケツトがバツフ
ア・メモリ内に置かれた時に、クラスタ・モジユ
ール制御器３２により増加させられる。

制御メモリ５２内のレデイ・リスト中の表に含
まれている他の２つの場所は、制御メモリ５２内
のレデイ・リスト上の先の項目と次の項目の制御
メモリ５２におけるアドレスを含む。

制御メモリ５２内の別の場所は、レデイ・リス
ト上の第１の項目のアドレスを指す「第１の項
目」と呼ばれるポインタを保持する。クラスタ・
モジユール制御器がパケツトを左OUTQバツフ
ア４０の中に置くことを要求した時に、そのクラ
スタ・モジユール制御器が働くのがその場所であ
る。

その場所において、クラスタ・モジユール制御
器は送るべきパケツト（キユーポンタの先頭）を
含んでいるバツフア・メモリ３４内のアドレスを
フエツチし、そのアドレスの所へ行き、パケツト
をとり出してそのパケツトを左OUTQバツフア
４０へ転送し、パケツト・カウントを減少させ、
キユーポインタの先頭を調整し、次の項目場所に
おいて見出される値に第１項目のポイントをセツ
トする。減少させられたパケツト・カウントが下
側しきい値を通つたとすると、クラスタ・モジユ
ール制御器３２がスタート・メツセージを発生し
て、そのメツセージをそれの左隣のクラスタ・モ
ジユールへ送り、以下に説明するようにINQ
START表中の適切なビツトをリセツトする。減
少させられたパケツト・カウントが零に達する
と、宛先のクラスタおよびプロセツサが送るべき
ものを何も持たず、システムが無用のポーリング
を避けるから、クラスタ・モジユール制御器はそ
のクラスタおよびプロセツサをレデイ・リストか
ら削除する。

左OUTQ４０は二重バツフアであるから、左
CRC発生器・並列／直変換器４４と左送信器４
８が左OUTQバツフア４０の半分に含まれてい
るパケツトを送つている間に、クラスタ・モジユ
ール制御器３２はその左OUTQバツフア４０の
他の半分にパケツトを入れることができる。左
CRC発生器・並列／直列変換器４４と左送信器
４８は内部送信クロツク（図示せず）により、通
常のやり方でクロツクされる。

入来フレーム中の制御語がクラスタ・モジユー
ル１８のすぐ左隣からのストツプ・メツセージを
含んでいるとすると、そのストツプ語はクラス
タ・モジユール制御器３２により認められ、クラ
スタ・モジユール制御器３２は宛先のクラスタお
よびプロセツサに関連する表を制御メモリ５２か
らフエツチし、レデイ・リストからそれを実効的
に削除する。これは、二重にリンクされているリ
ストから項目を除去する公知のやり方で行われ
る。

クラスタ・モジユール１８ｂは、自身のローカ
ル・プロセツサ間バス１２ｂ上の任意のプロセツ
サへパケツトを送ることもできる。

そのパケツトがバツフア・メモリ３４から検索
されると、そのパケツトは確認されてIPB制御器
３０へ転送され、ローカル・プロセツサ間バス１
２ｂに接続されているある特定のプロセツサに関
連するOUTQバツフア５４内の場所に置かれる。
各OUTQバツフアの場所はローカル・プロセツ
サ間バス１２ｂ上の各プロセツサのための単一パ
ケツト容量を有する。

OUTQバツフア５４にはOUTQ STAT５６
と、OUTQバツフア５４内の各場所のための１
ビツト位置を有するレジスタとが組合わされる。
そのローカル・バス上のプロセツサへパケツトを
送ることをそのクラスタ・モジユール制御器が望
むと、そのクラスタ・モジユール制御器はそのプ
ロセツサに関連するOUTQ STATレジスタ・ビ
ツトの内容をまず調べる。そのビツトがセツトさ
れているということは、対応するOUTQバツフ
アが一杯で、次のパケツトをOUTQバツフア５
４内のその場所に置くことができるようになる前
に、それの現在のパケツトがローカル宛先プロセ
ツサへ転送されるまでクラスタ・モジユール制御
器は待たなければならないことを意味する。
OUTQバツフア５４からローカル宛先プロセツ
サへの転送が行われる時には、それの対応する
OUTQ STATビツトがリセツトされて、ローカ
ル・プロセツサ間バス１２ｂを介してローカル宛
先プロセツサへ転送するための別のパケツトを
OUTQバツフア５４が受ける用意ができている
ことを知らせる。パケツトは左受信器５８または
右受信器６０と、左CRC検査直列／並列変換器
６２，６４とを介してクラスタ・モジユール１８
ｂに達する。到達するパケツトはマンチエスタ型
コードまたは他の公知の自己クロツクコードで様
式化されており、受信器５８または６０を通る間
に自己クロツクさせられる。

並列型にされた入来パケツトはINQバツフア
６６と６８の中に置かれる。INQバツフア６６
は、それの１つの部分がクラスタ・モジユール制
御器３２により空にされている時に、他の部分が
CRC検査器・直列／並列変換器６２により満す
ことがでできるように構成された二重バツフアと
することができる。INQバツフア６８はINQバ
ツフア６６と構造と機能が同じである。

クラスタ・モジユール制御器３２は入来パケツ
トの宛先クラスタおよびプロセツサの番号を読
む。パケツトが別のクラスタ・モジユール１８へ
は宛てられず、ローカル・プロセツサ間バス上の
プロセツサ１０へ宛てられるものとすると（これ
は、パケツトの宛先クラスタ番号をクラスタ・モ
ジユールのクラスタ番号と比較することにより決
定される）、いくつかの事柄が起る。ローカル
IPB状態リストは、プロセツサ番をアドレスとし
て用いて呼出される。ローカルIPB状態リスト
は、各ローカル・プロセツサごとに、１）FIFO
キユー中の最も古いパケツトを示すバツフア・メ
モリ中のアドレス、２）そのキユー中のパケツト
の数のカウント、を含む。パケツトは、ローカル
IPB状態リストから得た表中のアドレスにより指
定されたバツフア・メモリ３４内の場所に格納さ
れ、その表中のパケツト・カウントが増加させら
れる。新しいカウントが上側のしきい値を通つた
とすると、後で説明するように、ストツプ・メツ
セージが発生されて適切な向きへ送られ、INQ
STAT表中の適切なビツトがセツトされる。前
のパケツト・カウントが零であつたとすると、フ
ラグがセツトされて、その特定のプロセツサのた
めのバツフアが送るべき何かを有することを示
す。このフラグは制御メモリ５２内のある語中に
配置させられる。その制御メモリはローカル・プ
ロセツサ間バス１２ｂ上の各プロセツサごとに１
ビツトを有する。どのローカル・プロセツサがク
ラスタ・モジユールから受けられるパケツトを有
するか示すその「ローカル・レデイ」フラグ語
は、バツフア・メモリからのパケツトをある特定
のローカル・プロセツサのためのOUTQへ送る
時刻を決定するために、OUTQ STAT語（先に
述べた）とともに用いられる。あるパケツトがバ
ツフア・メモリからあるCUTQへ転送されるた
びに、ローカルIPB状態リスト中のパケツト・カ
ウント（ここで問題としているローカル・プロセ
ツサのための）が減少させられる。そのパケツ
ト・カウントが零になると、ローカル・レデイ・
フラグ語中のそのプロセツサに対するフラグ・ビ
ツトがリセツトされて、そのローカル・プロセツ
サへ送るべきパケツトがもはやないことを示す。
また、そのカウントが下側のしきい値以下に減少
すると、スタート・メツセージが発生される（直
列リンク上の転送に類似する）。

入来パケツトが別のクラスタ・モジユールへ宛
てられるものとすると、宛先のクラスタおよびプ
ロセツサの番号が、制御メモリ５２内のレデイ・
リスト中の適切な表を呼出すためのアドレスとし
て用いられる。パケツトはレデイ・リスト表にお
いて指定されているバツフア・メモリ３４内のア
ドレス内に置かれ、（その表中の）パケツト・カ
ウントがクラスタ・モジユール制御器３２により
増加させられる。そのバツフア内のパケツトの数
が上側のしきい値をいまこえたとすると、クラス
タ・モジユール３２がストツプ・メツセージを発
生し、そのメツセージをパケツトから来る向きに
送り、以下に説明するように、INQ STAT表中
の適切なビツトをセツトする。バツフア・メモリ
３４中のその場所に格納されているパケツトの前
の数が零であつたとすると、入来パケツトが宛て
られるその宛先クラスタおよびプロセツサがレデ
イ・リスト上にないから、第１の項目を示すポイ
ンタにより指定されている場所のすぐうしろに二
重リンクされているレデイ・リストの中にクラス
タ・モジユール制御器３２がそれを挿入する。し
かし、次にパケツトを送るべきクラスタ・モジユ
ールから送られるストツプ・メツセージがあつた
とすると、レデイ・リストに対してのエントリイ
は行われない。ある特定の宛先プロセツサために
スタート・メツセージが受けられると、そのプロ
セツサは、パケツト・カウントが零でなければ、
それからレデイ・リスト上にのせられる。

リングに沿つて送るために、パケツトはローカ
ル・プロセツサ間バス１２ｂ上にも発生される。
それらのパケツトはIPB制御器３０により最初に
取扱われる。

ポール・サイクル中は、パケツトの最初の語が
プロセツサ間バス１２ｂ上に現われ、IPB制御器
は、宛先クラスタ番号が零でなければ、その最初
の語を外部転送の要求と認める。宛先クラスタお
よびプロセツサ番号は、IPB制御器内に配置され
ているINQ STAT表７０内へのアドレスとして
IPB制御器により用いられる。パケツトのための
所期の休止場所であるバツフア場所に関してスト
ツプ・メツセージが送られたとすると、そのパケ
ツトの最初の語により宛てられたINQ STAT表
７０内のアドレスにビツトがセツトされ、その時
に認められると、そのビツトは転送が行われるこ
とを阻止する。クラスタ・モジユール制御器３２
がINQ STAT表７０をアドレツシングしている
間は、INQバツフア７２へのパケツトの転送を
行うことはできない。

しかし、そのパケツトの宛先のためのストツ
プ・ビツトがINQ STAT表７０においてセツト
されなかつたとすると、IPB制御器はそれのフラ
グを調べることによりINQバツフア７２が一杯
であるかどうかを検討する。そのINQバツフア
が一杯であれば転送は行われず、もし空いておれ
ばパケツトはIPB制御器３０内のINQバツフア７
２へ転送され、INQバツフア一杯フラグがセツ
トされる。このフラグはクラスタ・モジユール制
御器３２により定期的に調べられ、それがセツト
されていることがわかつたら、INQバツフア７
２の内容がバツフア・メモリ３４内の適切な場所
転送され、INQバツフア・フラグがリセツトさ
れる。それから、直列データ・リンク２２または
２４から受けられるパケツトに関して説明したよ
うにして、レデイ・リストが更新される。

IPB制御器３０の動作は状態マシン７４の指揮
の下にある。状態マシン７４については第１１図
を参照して詳しく説明する。状態マシン７４はプ
ロセツサ間バス１２との間のパケツトの転送を指
令する。

ハードウエアとソフトウエアが協働してプロセ
ツサ間のデータ転送を行う仕組を調べることによ
り、本発明の理解を容量にできる。あるプロセツ
サから別のマルチプロセツサ・システムに属する
プロセツサへのデータの転送は、SEND命令によ
るソフトウエアの制御の下に開始され、行われ
る。

以下の説明は、第３図のマルチプロセツサ・シ
ステムａのプロセツサ１０からマルチプロセツ
サ・システムｂのプロセツサへデータ・ブロツク
を送るものと仮定している。

SEND命令においては、第３図のプロセツサ１
０はそれのメモリからデータ・ブロツクを読出
し、それをパケツトに分け（第５図のパケツト・
フオーマツトを参照のこと）、パケツト・チエツ
クサム語を計算し、データ・ブロツクを１度に１
パケツトずつクラスタ・モジユール１８ａまたは
２０ａのいずれかへ送る。SEND命令に供給され
るパラメータはＸクラスタ・モジユール１８ａま
たはＹクラスタ・モジユール２０ａの使用と、ス
タート・パケツトのシーケンス番号と、リングに
沿つてパケツトを送る向きと、受けるクラスタ・
モジユールの同一性と、受信クラスタ・モジユー
ルに接続されているマルチプロセツサ・システム
内の受信プロセツサの同一性と、メモリ内のデー
タ・ブロツクのスタート・アドレスと、データ・
ブロツク中のバイト数と、米国特許第4228496号
の第２図の出力キユ６７を利用できるようになる
まで待つための最初のタイムアウト値とを指定す
る。

異なるクラスタ内のプロセツサへ宛てられるパ
ケツトに対しては、プロセツサ１０における
SEND命令は、第５図に示されているパケツトの
語０の送り側クラスタ・フイールド（ビツト０〜
３）として識別されているフイールドにパケツト
を送る向きの指示を与える。そのパケツトを左へ
送るものとすると、送り側のクラスタ・フイール
ド内に値０が置かれ、パケツトを右へ送るものと
すると、そのフイールド内に値１が置かれる。こ
の値は、パケツトを送る正しい向きを決定するた
めに、クラスタ・モジユールにより使用される。
クラスタ・モジユールによりその向きが決定され
ると、そのパケツトの語０の送り側クラスタ・フ
イールド（ビツト０〜３）が、クラスタ・モジユ
ールに知られている送り側クラスタ・モジユール
により書き換えられる。

パケツトを宛先のプロセツサへ送る好適な向き
は、システムが構成される時に決定される。した
がつて、その好適な向きは一部はネツトワークの
幾何学的構成に依存する。その向きの主な決定要
因が経路の長さであることは明らかである。とい
うのは、パケツトを最短経路で送ることが好まし
いからである。もちろん、種々の経路間でトラフ
イツクの流れを平均化することによりひき起され
る伝送速度の潜在的な低下を設者は避けようとす
るから、その要因はトラフイツク容量を考慮に入
れることにより軽くされる。

たとえば、2n個のクラスタ・モジユールを含
んでいるリング構成においては任意のパケツトが
宛先に到達するまでにｎ個のクラスタ・モジユー
ルより少ないパケツト経路を含む向きをとること
を設計者は望むであろう。双方向リングにおいて
は、ＸとＹの経路間でのトラフイツクを平均させ
るために、ＸとＹの経路を無作為に選択すべきで
ある。

それらの選択された向きは、宛先クラスタに従
つて、各システム中のプロセツサ内の表に置かれ
る。あるパケツトをある特定のクラスタへ送る用
意ができている時は、パケツトを送る向きを割当
てるために送りプロセツサはその表を用いる。希
望によつては、選択された経路を与えられた向き
に変更するため、またはあまりに多くの誤りが経
路の誤動作を示すならば向き自体を変更するため
に、誤り情報の翻訳を使用できる。

全体のブロツクがパケツトに分けられて送られ
た後でSEND命令は終る。したがつて、あるブロ
ツクの送出は、ソフトウエアの観点からは、１つ
の命令の実行であるようにみえる。もつとも、そ
の命令は翻訳可能であるが。

マルチプロセツサ・システム（第３図のｂ）の
プロセツサによるデータの受信はソフトウエアに
より実行されるものではない。その理由は、デー
タ・パケツトの到達時刻とソースを予測できない
からである。データの受信は可能にしなければな
らないが、受信器により開始することはできな
い。

そのプロセツサは、米国特許第4228496号のプ
ロセツサ間制御器５５の行列内部分から受信デー
タ・パケツトをとるバス受信マイクロプログラム
（その米国特許明細書の参照番号115）を実行する
ことにより、Ｘクラスタ・モジユール１８ｂまた
はＹクラスタ・モジユール２０ｂからパケツトを
受け、正しいチエツクサムとシーケンス番号を検
査し、データをメモリ・バツフアに格納する。

受けたパケツトは、メモリ内のバス受信表エン
トリを用いて、ブロツクに再びまとめられる。バ
ス受信表エントリというのはある特定のマルチプ
ロセツサ・システム（第３図のａ）と、そのシス
テム内のプロセツサ（第３図の１２ａ）に対応す
る。バス受信表エントリはメモリ・アドレスと、
カウント語と、予測されるシーケンス番号とを含
む。

各データ・パケツトが受けられるにつれて、バ
ス・マイクロプログラムが作動させられる。この
マイクロプログラムは、送り出しマルチプロセツ
サシステムと、そのシステム内のプロセツサとに
対応するバス受信表エントリを呼出す。受けたパ
ケツトが正しいチエツク・サムを含み、かつそれ
のシーケンス番号が次に受信すべきパケツトの予
測されるシーケンス番号に一致するものとする
と、パケツトのデータ語は指定された領域に格納
され、次のパケツトを順次受けるための用意をす
るために領域のアドレスと、シーケンス番号と、
バス受信表中のバイト・カウントとの調整が行わ
れる。カウントが零に達るか、任意の誤りが検出
されるとソフトウエアの割込みが行われる。

受けたパケツトを処理するこの方法により、デ
ータ・ブロツク全体を送ることによつて伝送プロ
セス中の誤りを回復できる。前の伝送中に正しく
受けられたことがあるパケツトの写しである全て
のパケツトはシーケンスから外れているものと認
められ、メモリ中に格納されない。

マルチプロセツサ・システムのプロセツサ間で
実行されるプロトコルによつて確実なメツセージ
伝送が行われる。誤りを示すことなしに受けられ
る各伝送は、受信プロセツサから送信プロセツサ
への次の伝送により確実に確認応答される。送信
プロセツサにおいてその確認応答を受けることに
よつて、伝送が確かに受けられたことが確認され
る。

送信プロセツサが最初に伝送を行うと、送信プ
ロセツサは、確認応答が受けられるべきであつた
時刻を、指定された時間間隔を基にして決定す
る。所定の時刻までに確認応答が受けられなかつ
たとすると、伝送が行われて、同じ指定された時
間間隔を基にして新しい時刻が決定されることに
なる。このように、送信プロセツサにより確認応
答が受けられるまでは再伝送がくり返えし行われ
る。

伝送は２つのクラスタ・モジユール１８ａと２
０ａのうちのいずれか一方を介して、２つの向き
（左または右）のいずれかの向で送られるから、
データ・ブロツクを受信プロセツサへ送るのに４
つの可能な伝送路を使用できる。送信プロセツサ
が受信プロセツサへのデータ・ブロツクの送信を
開始すると、その送信プロセツサは利用できるあ
る状態情報に従つて４つの可能な経路のうちの１
つを選択する。その状態情報は、ソフトウエアが
作裂される時にそのソフトウエアに組込まれる好
適な向き（左または右）の定義と、以前に各経路
上で生じた誤りの数とを含む。それらの誤りの数
があるしきい値をこえたとすると、その経路は故
障したとみなされてもはや使用されなくなる。経
路の選択においては、トラフイツクをより一様に
分配するためにＸバスとＹバスを無作為に選択さ
れる。

ある時間が経過しても送信プロセツサが受信プ
ロセツサからの確認応答を受けていないと、その
送信プロセツサはシステムのインテリジエンスに
組込まれている規則に従つて伝送用の経路を選択
する。その規則はいくらかは任意のものであつ
て、先の説明で述べた同じ状態情報と、先の伝送
で用いた経路の同一性とを効率よく考慮に入れる
任意のアルゴリズムとすることができる。その規
則は、引続き伝送の試みが全部で４つの経路を、
または１つまたはそれ以上の経路が誤りのために
使用不能となつた時は使用できる全ての経路を切
換えるために用いられる。

ここで説明している実施例においては、データ
が２つのバスの１つにより与えられた向きに送ら
れる。割当られた時間中に確認応答が受けられな
かつたとすると、再送信が試みられる。２回目の
確認応答不存在の後で、データ・ブロツクは他の
バスを経て同じ向きへ送られる。２回の確認応答
不存在の後で、他の向きのバスによる試みが同様
にして行われる。必要があれば、どの経路も機能
しないことが明らかでない限り、この動作はくり
返えされる。

あるデータ・ブロツクの伝送は成功したが、受
信器からの確認応答メツセージの送信器への返送
が成功しない場合には、送信器により開始される
再送信の試みのために受信器においてシーケンス
誤りが発生させられる。その理由は、パケツトが
既にうまく受信されており、バス受信表シーケン
ス番号が更新されているからである。そのシーケ
ンス誤りを検出した受信器は、追加の確認応答パ
ケツトを４つの全ての経路を介して、または誤り
のために１つまたはそれ以上の経路が使用不能の
場合には使用可能な全ての経路を介して送る。

このようにして送信器から受信器までの４つの
経路のうちのいずれか１つ、または受信器から送
信器までの４つの経路のうちのいずれか１つが機
能しておれば、メツセージをうまく送り、確認応
答させることができる。

次に、第６〜第１１図を参照して、制御構造と
ともにクラスタ・モジユールの動作を詳しく説明
する。各クラスタ・モジユール制御器３２は入力
キユーと、出力キユーと、間隔タイマ（図示せ
ず）とをくり返えし調べることにより各クラス
タ・モジユール１８の動作を指令する。各入力キ
ユーが一杯になつた時に、関連する入力キユーか
らのデータをバツフア・メモリ３４へ転送するこ
とによつて、各入力キユーはサービスされる。同
様に、各出力キユーが空になつた時に、データを
バツフア・メモリ３４から関連する出力キユーへ
転送することにより、各出力キユーはサービスさ
れる。タイマ・サービスは、間隔タイマが割込を
トリガした時に、定期的に実行される。

バツフア・メモリ３４はそれぞれ16パケツトの
固定長スペースに分けられる。リング内の可能な
各宛先プロセツサにはそれらのスペースが２つ割
当てられる。その割当は、パケツトが宛先プロセ
ツサ１０のいずれかへ進む２つの向きの１つに１
つのスペースが割当られる、というようにして行
われる。バツフア・メモリ３４内のそれらのスペ
ースは、パケツトを受けた順に送り出すような
FIFOキユーとして取扱われる。バツフア・メモ
リ３４内の介キユー（スペース）は他のどのキユ
ーの状態とは独にクラスタ・モジユールにより管
理される。たとえば、クラスタ・モジユールは、
あるプロセツサまで右の向きに進むパケツトとは
全く独立に、その同じプロセツサまで左の向きへ
進むパケツトを取扱う。

クラスタ・モジユール制御器３２はバツフア・
メモリ３４におけるFIFOキユーの割当と使用を
管理する。それらのキユーを管理するために、ク
ラスタ・モジユール制御器３２は、バツフア・メ
モリ３４内の各キユーごとに情報の表キユー制御
表をそれらの制御メモリ内に保持する。各キユー
制御表は、関連するキユー中に現在あるパケツト
の数のカウント（パケツト・カウント）と、その
キユー中の最も古いパケツトへのポインタ（先頭
ポインタ）と、そのキユー中の最も新しいパケツ
トへのポインタ（最後尾のポインタ）とを含む。
ある特定の宛先プロセツサと向きに割当られたバ
ツフア・メモリ３４内のキユーの場所は、その宛
先および向きのクラスタおよびプロセツサの番号
により決定される。同様に、制御メモリ５２内の
関連するキユー制御表の場所は、その行先および
向きのクラスタとプロセツサの番号により決定さ
れる。絶対アドレスは全く選択の問題であること
が当業者ならわかるであろう。

あるパケツトがクラスタ・モジユールにおいて
受けられると、クラスタ・モジユール制御器３２
が宛先クラスタおよびプロセツサの番号と、パケ
ツトを送る向きとを基にして、適切なキユーをバ
ツフア・メモリ３４の中に置き、適切な行列制御
表を制御メモリ５２の中に置く。パケツトをキユ
ー内に置く前に、クラスタ・モジユール制御器１
２はパケツト・カウントを増加させる。新しいパ
ケツト・カウントが16をこえると、そのパケツト
は捨てられ、制御メモリ５２内のキユー制御表は
変更されない。新しいパケツト・カウントが16よ
り少ないか、16に等しい時は、最後尾のポインタ
が増加させられ、モジユロ１６、その最後尾のポ
インタの新しい値により指示されたキユー内の場
所にそのパケツトは置かれ、キユー制御表中の最
後尾のポインタとパケツト・カウントが新しい値
により更新される。

あるパケツトが送られる時は、クラスタ・モジ
ユール制御器３２は宛先クラスタおよびプロセツ
サの番号と、パケツトを送る向きとを基にして適
切な行列をバツフア・メモリ３４内に置き、適切
なキユー制御表を制御メモリ５２内に置く。それ
から、クラスタ・モジユール制御器３２は、先頭
のポインタにより指示されたキユー中の場所から
パケツトを除去し、先頭のポインタを増加し、モ
ジユロ１６、パケツト・カウントを減少し、制御
メモリ５２内のキユー制御表を新しい値で更新す
る。

そうすると、各キユー制御表の内容は先頭のポ
インタ（そのポインタはその行列中の次のパケツ
トを送ることを指示する）と、最後尾のポインタ
（このポインタは最後のパケツトを、その行列中
に置くことを指示する）と、パケツト・カウント
（このカウントはそのキユー中にどれだけの数の
パケツトが現在含まれているかを示す）との正し
い値を常に含む。

クラスタ・モジユール制御器３２は、送るため
のバツフア・メモリ３４内の次のパケツトを選択
するための効率の良い方法を有しなければならな
い。これは、前記レデイ・リストを非零のパケツ
ト・カウントを有するキユー制御表の二重にリン
クされたリストの形で維持することによつて行う
ことができる。好適な方法は、クラスタ送り用意
完了表と、プロセツサ送り用意完了表との更に、
２種類の情報表を制御メモリ内に保持するもので
ある。

各向きごとに２つのクラスタ送り用意完了表が
ある。制御メモリ５２内のクラスタ送り用意完了
表の場所はパケツトを送る向きにより決定される
が、割当てられる絶対アドレスは全く選択の問題
であることが当業者にはわかるであろう。可能な
各クラスタには各向きに１つずつ、合計２つのプ
ロセツサ送り用意完了表がある。制御メモリ５２
におけるプロセツサ送り用意完了表の場所は、各
クラスタの番号と、パケツトを送る向きとにより
同様に決定される。

各送り用意完了表はパケツト待ちマスクと、流
れ制御マスクと、優先度マスクとの３つの部分で
構成される。各マスク中のビツトとある特定のク
ラスト（またはプロセツサ１０）番号との間に１
対１の関係がある。パケツト待ちマスク中の各ビ
ツトは、そのビツトに関連するクラスタ（または
プロセツサ１０）番号へ送られることを待つてい
るパケツトが、バツフア・メモリ３４内にあるか
どうかを示す。流れ制御マスク中の各ビツトは、
そのビツトに関連するクラスタ（またはプロセツ
サ１０）の流れ制御状態（以下に、説明するよう
に停止またはスタートさせられている状態）を示
す。パケツト待ちマスクと流れマスクとの論理積
（AND）は送り用意完了マスクであつて、送り用
意完了マスク内の各ビツトは、そのビツトに関連
するクラスタ（またはプロセツサ１０）に現在送
ることができるパケツトが、バツフア・メモリ３
４内にあるかどうかを示す。優先度マスクは、ど
のビツトにおいて送り用意完了マスクのサーチを
開始すべきかを示すために、用いられる。優先度
マスクにおいては、パケツトが送られた最後のク
ラスタ（またはプロセツサ１０）と、全ての下位
番号クラスタ（またはプロセツサ１０）とに関連
するビツトがリセツトされ、他の全てのクラスタ
（またはプロセツサ）に関連するビツトがセツト
される。したがつて、送り用意完了マスクと優先
度マスクとの論理積（AND）がマスクを形成す
る。そのマスクにおいては、最後に送られたクラ
スタ（またはプロセツサ１０）よりも上位の番号
のクラスタ（またはプロセツサ）に関連するビツ
トだけを、セツトできる。

あるパケツトが、バツフア・メモリ３４の中に
おかれると、パケツトの宛先プロセツトに関連す
るビツトが、パケツトの宛先と向きに関連するプ
ロセツサ送り用意完了表のパケツト待ちマスク内
に、セツトされる。同様に、パケツトの宛先クラ
スタに関連するビツトが、パケツトを送る向きに
関連するクラスタ送り用意完了表の、パケツト待
ちマスク内にセツトされる。

あるパケツトがバツフア・メモリ３４から除去
されると、キユーのためのパケツト・カウントが
零になつたとすると、パケツトの宛先プロセンサ
に関連するビツトが、パケツトの宛先クラスタと
向きに関連するプロセツサ送り用意完了表のパケ
ツト待ちマスクにおいてリセツトされる。この動
作によりビツトがセツトされていない（そのクラ
スタへ送られるのを待つているそれ以上のパケツ
トがない）パケツト待ちマスクが得られたとする
と、パケツトの宛先クラスタに関連するビツト
が、そのパケツトが送られる向きに関連するクラ
スタ送り用意完了表のパケツト待ちマスクにおい
てリセツトされる。また、プロセツサ送り用意完
了表とクラスタ送り用意完了表中の優先度マスク
がセツトされて、どの宛先プロセツサとクラスタ
へパケツトが送られるかを示す。

送り用意完了表の使用については例を用いて最
もよく説明できる。パケツトの転送を開始するた
めに、クラスタ・モジユール制御器３２は、適切
な向きのためのクラスタ送り用意完了表を制御メ
モリから得る。それから、その制御器３２は、第
１のビツトに対して送り用意完了マスクと優先度
マスクとの論理積を求る。前記第１のビツトはセ
ツトされて、そのために送ることができるパケツ
トがあるクラスタを示す。送り用意完了マスクと
優先度マスクとの論理積を求めてもクラスタが見
出されないとすると、それに対して送るべきクラ
スタを見出すために同様なやり方で送り用意完了
マスクが探索される。クラスタが選択されると、
そのクラスタに関連するプロセツサ送り用意完了
表が制御メモリから得られて、同様なやり方で探
索される。宛先クラスタとプロセツサが選択され
ると、関連するFIFOキユーとキユー制御表が探
され、最後尾のポインタにより示されているパケ
ツトがそのキユーから除去され、キユー制御表と
送り用意完了表が上述のようにして更新される。

この二段階探索動作により、最後に送られるク
ラスタ（およびクラスタ内の最後のプロセツサ）
に次に送るための最低の優先度が常に与えられる
という、効果的な連続優先度スキームが実行され
る。このようにして可能な全てのクラスタ（およ
びクラスタ内のプロセツサ）に利用可能な直列デ
ータ・リンクの帯域幅のかなりな取り分が与えら
れる。

バツフア・メモリ３４内の次に送るパケツトの
好適な選択方法は、クラスタ・モジユール制御器
３２の一部であるハードウエア優先度符号器の効
率の良い探索性能を利用して選択された。前記レ
デイ・リストも機能することを当業者は認めるで
あろう。

与えられた任意の宛先に対するパケツトはクラ
スタ・モジユールを出る時よりも高速でクラス
タ・モジユール到達することがあるから、流れ制
御プロトコルが求められる。流れ制御はストツ
プ・メツセージと、スタート・メツセージと、
INQ STAT 表70とを用いて行われる。バツフ
ア・メモリ３４内のFIFOキユーにはストツプし
きい値およびスタートしきい値と呼ばれる２つの
一定値が組合わされる。あるパケツトがあるキユ
ー中に置かれると、新しいパケツト・カウントが
ストツプ・しきい値と比較される。その新しいパ
ケツト・カウントがストツプしきい値に等しい
か、それより大きい時は、そのキユーは一杯であ
るとみなされて、そのキユー中へのパケツトの流
れを停止させる動作（宛先停止と呼ばれる）がと
られる。ローカル・プロセツサ間バスから行列中
へのパケツトの流れは、その宛に関連するINQ
STAT 表70内のビツトをセツトすることによ
つて停止させられる。直列データ・リンクから行
列内へのパケツトの流れは、適切な隣のクラス
タ・モジユールへストツプメツセージを送ること
によつて停止させられる。ストツプ・メツセージ
は直列リンク・フレームの制御語で通常送られ、
停止させるべき宛先のクラスタおよびプロセツサ
の番号を含む。

バツフア・メモリ３４内のFIFOキユーからあ
るパケツトが除去されると、新しいパケツト・カ
ウント値がスタートしきい値と比較される。その
新しいパケツト・カウントがスタートしきい値に
等しく、宛先が前に停止させられていたとする
と、キユー内へのパケツトの流れをスタートさせ
る動作（宛先をスタートさせる、と呼ばれる）が
行われる。ローカル・プロセツサ間バスからキユ
ー内へのパケツトの流れは、宛先に関連する
INQ STAT 表70内のビツトをリセツトするこ
とによつてスタートさせられる。直列データ・リ
ンクからキユー内へのパケツトの流れは、適切な
隣りのクラスタ・モジユールへスタート・メツセ
ージを送ることによりスタートさせられる。スタ
ート・メツセージは直列リンク・フレームの制御
語で通常送られ、スタートさせるべき宛先のクラ
スタおよびプロセツサ番号を含む。

スタート・メツセージとストツプ・メツセージ
はすぐには送られず、送りのために各直列デー
タ・リンクに関連させられる特殊な、２語、キユ
ーに待たさせられ、その直列データ・リンク上を
送られる次のフレーム中に含まれる。直列デー
タ・リンク上を送られる２つ以上の制御メツセー
ジがあるか、その直列データ・リンク上を送られ
るを待つているパケツトがないものとすると、制
御のみフレームが送られる。制御のみフレームと
いうのは、その中において、対象とする向きにお
ける全ての宛先プロセツサのスタート／ストツプ
状態を表すビツト・マツプによりパケツト・デー
タが置き換えられるようなフレームである。流れ
制御の同期を保つために、制御のみフレームは周
期的な間隔でも送られる。したがつて、直列デー
タ・リンクの過度的な誤りのためにあるスター
ト・メツセージが失われたとすると、次の周期的
な制御のみフレームによりその宛先がスタートさ
せられる。

制御メツセージを送り、隣のクラスタ・モジユ
ールにより作用を受けるにはある時間を要するか
ら、ストツプしきい値はFIFOキユーの実際の寸
法より小さいように選択せねばならない。また、
キユーの利用度を最高にするために、スタートし
きい値は零より大きいように選択される。ここで
説明している実施例においては、たとえば、16個
のパケツト容量を有するFIFOキユーでは、スタ
ートしきい値として６、ストツプしきい値として
８をそれぞれ選択した。

クラスタ・モジユール制御器３２がストツプ制
御メツセージを受けると、その制御器は関連する
プロセツサ送り用意完了表に関連する流れ制御マ
スク中の関連するビツトをリセツトする。その結
果得られた流れ制御マスクが全部零である（これ
は、その宛先内の全てのプロセツサがストツプさ
せられることを示す）とすると、関連するクラス
タ送り用意完了表の流れ制御マスク中の関連する
ビツトがリセツトされる。あるクラスタ・モジユ
ール制御器３２がスタート制御メツセージを受け
ると、その制御器は関連するプロセツサ送り用意
完了表の流れ制御マスク中の関連するビツトと、
関連するクラスタ送り用意完了表の流れ制御マス
ク中の関連するビツトとをセツトする。あるクラ
スタ・モジユール制御器３２は、フレームを受け
ると、その制御器３２は、フレームが来る向きに
関連する全てのプロセツサ送り用意完了表とクラ
スタ送り用意完了表中の流れ制御マスクを更新す
る。

好適な実施例においては、「逸走（runaway）」
パケツトを取扱う機構が存在する。「逸走」パケ
ツトというのはネツトワークを一周し、要求され
ないままであるようなパケツトである。

逸走パケツト機構は次のように機能する。ある
パケツトがローカル・プロセツサ間バス１２から
とり出されると、その宛先クラスタ番号（第５図
参照）が、零に初期設定されているビツト・フイ
ールドで置き換えられる。リング内のクラスタに
おいてパケツトが受けられるたびに、そのビツ
ト・フイールドの値が読取られて、増加させられ
る。読取られた値がそのネツトワーク内のクラス
タの数に等しいか、それより大きいとすると、す
なわち、パケツトが全てのクラスタに行つて、求
められないままであるとすると、そのパケツトは
廃棄される。

ここで第６〜１１図を参照して、クラスタ・モ
ジユールの好適な一連の動作を説明する。システ
ムが始動させられると、レジスタと表を初期設定
し、フラブをクリヤし、全てのプロセツサ制御ス
トラクチヤまたは全てのクラスタ制御ストラクチ
ヤを初期設定する初期設定ルーチン（図示せず）
が、この分野で良く知られている初期設定を行う
ための典型的なやり方で実行される。全ての妥当
な宛先アドレスのためのパケツトを受けるため
に、そのルーチンはIPB制御器３０内のINQ
STAT 表70をセツトする。

まず第６図を参照して、アイドル・ループ１０
２に入る。このアイドル・ループはループ中の各
トリが項目すなわちリソースをくりかえしポール
する。そのリソースに関連するサービスは必要が
あれば実行される。

左直列INQ検査ステツプ１０４において左直
列INQバツフア６６内のフラグが試験されて、
それが一杯で、左直列INQがサービスを必要と
することを示しているかどうかを調べる。もし一
杯であれば左直列サービス・ルーチンがステツプ
１０５において実行され、ループが続けられる。

次に、右直列INQ検査ステツプ１０６におい
て右直列INQバツフア６８が一杯で、右直列
INQがサービスを必要としているかどうかを調
べるために、その右直列INQバツフア６８内の
フラグが検査される。もし一杯であれば、右直列
INQサービス・ルーチンがステツプ１０７にお
いて実行され、ループは継続される。

次に、タイマ時間切れ検査ブロツク１０８にお
いて、内部間隔タイマが零までカウント・ダウン
したかどうかが調べられる。もしそうであれば、
タイマ時間切れサービス・ルーチンがステツプ１
０９において実行される。そのサービス・ルーチ
ンには「制御のみ」フレームをそれらの時間間隔
で送り出すことが含まれる。このステツプでの動
作が終ると、動作はアイドル・ループ１０２に再
び入る。内部間隔タイマが零までカウント・ダウ
ンしなければ、ループは継続される。

次に、ステツプ１１０において左直列OUTQ
バツフア４０のフラグを調べることによりそのバ
ツフア４０が空であるかどうかの検査が行われ、
もし空であればステツプ１１１において左直列
OUTQサービス・ルーチンが実行されてから、
動作はアイドル・ループ１０２へ再び入り、もし
空でなければループは次の判断ブロツクへ進む。

次に、ステツプ１１２において、右直列
OUTQバツフア４２のフラグを調べることによ
り、そのバツフア４２が空かどうかの検査が行わ
れ、もし空であれば、ステツプ１１３において右
直列OUTQサービス・ルーチンが実行されてか
ら、動作はアイドル・ループ１０２へ再び入り、
もし空でなければループはステツプ１１４へ進
む。

ステツプ１１４においては、ローカルINQバ
ツフア７２のフラグを調べることにより、そのバ
ツフア７２が一杯であるかどうかの検査が行わ
れ、もし一杯であれば、ステツプ１１５において
ローカルINQサービス・ルーチンが実行され、
その後でループはアイドル・ループ１０２に再び
入り、もし一杯でなければループは次のステツプ
１１６へ進む。

ステツプ１１６においては、空であるローカル
OUTQバツフア５４を有するある特定のプロセ
ツサのための左向けパケツトがあるかどうかの検
査が行われ、もしあればステツプ１１７において
左ローカルOUTQサービス・ルーチンが実行さ
れその後でループはアイドル・ループ１０２に再
び入り、もしなければループはステツプ１１８へ
進む。

ステツプ１１８においては、空であるローカル
OUTQバツフア５４を有するある特定のプロセ
ツサのための右向けパケツトがあるかどうかの検
査が行われ、もしあれば、ステツプ１１９におい
て右ローカルOUTQサービス・ルーチンが実行
され、それからアイドル・ループ１０２再び入
り、もしなければループは進む。

アイドル・ループ１０２が終るたびにループは
再びアイドル・ループ１０２へ入る。

ただ１つのアイドル・ループ１０２について説
明したが、ここで説明している実施例において
は、ループの初めにおいて検査されるサービス要
求に過度の集中が行われることを避けるために、
いくつかのアイドル・ループが実行される。ある
リソースがサービスされると、元のアイドル・ル
ープ１０２へ入らないで、直列出力キユー１１１
と１１３およびローカル出力キユー１１７，１１
９をサービスするステツプが許される。常に最初
に検査される３つのテスト１０４，１０６，１０
８を除き、同じサービスを異なる順序で実行する
同様なループに入る。これにより、各リソースに
等しい注意を向けるように、各サービスの優先度
を動的に変更するという効果が得られる。

次に第７図を参照する。この図にはローカル
INQサービス・ルーチン１１５のための流れ図
が示されている。

ステツプ２０３においては、特殊な機能を要す
るパケツトについて調べるために、入来パケツト
の特殊機能検査が行われる。その入来パケツトが
特殊機能を要するものである時はサービス・ルー
チンは終り、ステツプ２０２において特殊機能ル
ーチンが実行される。また、入来パケツトが特殊
機能を要しない時は、サービス・ルーチンが継続
され、動作はステツプ２０３へ進む。

ステツプ２０３においては、入来パケツトの格
納オーバラン、すなわち、パケツトのカウントが
16より大きいかどうかについて、宛先プロセツサ
に割当てられたキユー制御表の検査が行われ、パ
ケツト・カウントが16より大きい時は、ステツプ
２０４において格納オーバラン誤りカウントが増
大させられ、バツフア・メモリ３４内のFIFOキ
ユー中に利用できるスペースがないからサービ
ス・ルーチンは終了させられるが、パケツト・カ
ウントが16より大きくない時はサービス・ルーチ
ンは継続されて、動作ステツプ２０５へ進む。

ステツプ２０５においては、パケツト・フレー
ムINQバツフア７２からバツフア・メモリ３４
内のFIFOキユーへ動かされ、動作ステツプ２０
６においてそのパケツトは送り用意完了表に加え
られる。

動作ステツプ２０７においては、キユー制御表
内のパケツト・カウントがストツプしきい値に等
しいか、それより大きいかについての検査が行わ
れ、もしそうであれば動作ステツプ２０８におい
て送りをストツプさせる前記動作が行われる。

これでINQサービス・ルーチンは終了させら
れる。

次に第８図を参照する。この図にはローカル
OUTQサービス・ルーチン１１７（左）または
１１９（右）が示されている。

動作ステツプ２１１においては、空いていて、
係属中のパケツトを有するOUTQを選択するた
めに回転優先度符号器が用いられる。

次に、動作ステツプ２１２において、バツフ
ア・メモリ３４内のFIFOキユーから選択された
適切なOUTQへ適切なパケツトを移動させる。

次に、ステツプ２１３においてパリテイ誤りに
ついて調べられる。もし誤りがあれば、制御メモ
リ５２内のオプシヨンのパリテイ誤りカウント
（診断のために有用である）を動作ステツプ２１
４において増加させることができる。また、パリ
テイ誤りがなければ、ステツプ２１５において、
宛先プロセツサに対応するOUTQ STATレジス
タ５６内のビツトをセツトする。それから、ステ
ツプ２１６において、宛先プロセツサのためのキ
ユー制御表が更新される。

次に、ステツプ２１７において、FIFOキユー
が空いているかどうかについてキユー制御表が調
べられる。もし空いておれば、ステツプ２１８に
おいて、宛先プロセツサ送り用意完了表が前記し
たようにして更新され、ローカルINQサービ
ス・ルーチンは終る。また、FIFOキユーが空で
ないと、このサービス・ルーチンは継続される。

それから、ステツプ２１９において、パケツ
ト・カウントがタートしきい値に等しいかどうか
の検査が行われる。もし等しければ、ステツプ２
２０において、宛先へのパケツトの流れをスター
トさせる動作が行われ、このローカルOUTQサ
ービス・ルーチンは終る。

次に第９図を参照する。この図には直列INQ
サービス・ルーチンが示されている。

ステツプ２２１においては、パケツトが制御の
みフレームであるかどうかの検査が行われ、もし
そうであれば、ステツプ２２３において流れ制御
マスクが更新されて、この直列INQサービス・
ルーチンは終らされる。また、そうでなければス
テツプ２２６において、入来パケツト・カウント
が16より大きいかどうかについて検査が、宛先プ
ロセツサに割当てられたキユー制御表の検査が行
われる。パケツト・カウントが16より大きいと、
ステツプ２２７において、診断に有用なオプシヨ
ナルな格納オーバラン誤りカウントを増大させる
ことができる。それから入来制御語が処理され、
この直列INQサービス・ルーチンが終る。また、
パケツト・カウントが16より小さいと、このサー
ビス・ルーチンはステツプ２２８へ進む。

ステツプ２２８においては、パケツトが10番目
のノードに達したかどうか調べられ、もしそうで
あればそのパケツトは廃棄され、ステツプ２２９
において診断のために有用なオプシヨナルな逸走
パケツト誤りカウントを増大させることができ、
入来制御語が処理されて、この直列INQサービ
ス・ルーチンは終る。パケツトが16番目のノード
に達していなければ、このサービス・ルーチンは
ステツプ２３０へ進む。

ステツプ２３０においては直列INQバツフア
６６または６８からバツフア・メモリ３４内の
FIFOキユーへパケツト・フレームを移動させる。
このステツプ２３０からこのサービス・ルーチン
はステツプ２３５へ進む。

ステツプ２３５においては、キユー制御表が更
新される。

次に、ステツプ２３６において、ストツプしき
い値より多くのパケツトがバツフア領域内でキユ
ーに含まれているかどうかの検査が行われ、もし
含まれておれば、ステツプ２３７において、その
宛先向けのパケツトの流れをストツプさせる前記
動作が行われ、もし含まれていなければ、このサ
ービス・ルーチンはステツプ２３８へ進む。

このステツプにおいては、送り用意完了表にリ
ンクされているパケツトが更新される。

次に、ステツプ２３９において、入来制御語が
処理されて、このサービス・ルーチンは終る。

次に第１０図を参照する。この図には左
OUTQまたは右OUTQのための直列OUTQサー
ビス・ルーチンが示されている。

ステツプ２４１においては、送るべき２つ以上
の制御語があるか、または再同期間隔タイマの時
間が経過したかどうかの判定が行われる。好適な
実施例においては、その時間は10ミリ秒である。
上記の判定結果が肯定であれば、ステツプ２４２
において「制御のみ」フレームが送られ、それか
らこの直列OUTQサービス・ルーチンは終る。
また、上記の判定結果が否定の時は、ステツプ２
４３へこのルーチンは進む。

ステツプ２４３においては、クラスタとプロセ
ツサを選択するために連続優先度スキームが用い
られる。選択すべきクラスタがないか、そのクラ
スタ内で選択すべきプロセツサがないものとする
と、このルーチンは制御語検査ステツプ２４５へ
進み、そこで送るべき制御語が制御語行列中にあ
るかどうかの検査が行われる。もし存在すれば、
ステツプ２４６において、パケツトなしで２つの
制御語が送られる。このステツプ２４６における
動作の後で、このサービス・ルーチンは終る。し
かし、クラスタとプロセツサが選択されたとする
と、このサービス・ルーチンは継続される。

それから、ステツプ２４７において、バツフ
ア・メモリ３４内のFIFOキユーから直列OUTQ
バツフア４０または４２へ選択されたパケツトが
移動させられ、制御語キユーから制御語が付加さ
れ、キユー制御表が更新される。

次に、パケツト２４８において、バツフア・メ
モリのパリテイ誤りが調べられ、誤りが検出され
た時は、ステツプ２４９において、診断に有用な
オプシヨナルなメモリ・パリテイ誤りカウントが
カウントされる。それから、ステツプ２５０にお
いて、２つの制御語がパケツトなしで送られる。
バツフア・メモリのパリテイ誤りがなければ、ス
テツプ２５１においてフレームの送りが行われ
る。

次に、ステツプ２５２において、FIFOキユー
中にパケツトが残つているかの判定が行われ、そ
の判定結果が否定であれば、ステツプ２５３にお
いて、送り用意完了表が更新され、この直列
OUTQサービス・ルーチンは終る。また、判定
結果が肯定の時は、このサービス・ルーチンはス
テツプ２５４へ進む。

ステツプ２５４においては、パケツト・カウン
トがスタートしきい値に等しいか否かの判定が行
われる。もし等しければステツプ２５５におい
て、この宛先向けのパケツトの流れがスタートさ
せられる。

これで直列OUTQサービス・ルーチンは終る。

IPB制御器３０は、ローカル・プロセツサ対の
間と、ローカル・プロセツサとクラスタ・モジユ
ールの間との情報伝送を制御する。IPB制御器３
０はIPBバスにとりつけられ、クラスタ・モジユ
ールに直結される。IPB制御器とローカル・プロ
セツサの間およびIPB制御器とクラスタ・モジユ
ール制御器の間で制御信号を送るために制御線が
用いられる。

１つのローカル・プロセツサから他のローカ
ル・プロセツサへのデータは米国国特許第
4228469号明細書に開示されている方法に非常に
類似する方法で動かされる。パケツトを送るため
にあるプロセツサが選択されると、そのプロセツ
サはそのパケツトの宛先アドレスをIPBに置く。
それから、ローカル宛先プロセツサはIPBからパ
ケツトを受けることを指令される。次に、ローカ
ルソース・プロセツサはパケツトをIPBを介して
ローカル宛先プロセツサへ動かす。

ローカル・プロセツサからクラスタ・モジユー
ルへのデータは、ローカル・ソース・プロセツサ
からIPB制御器のINQバツフア７２へ動かされ
る。INQFULLフラグがセツトされて、パケツト
の用意ができていることをクラスタ・モジユール
に合図する。それから、クラスタ・モジユールは
バツフア・メモリ３４へパケツトを動かし、
INQFULLフラグをリセツトする。

クラスタ・モジユールからローカル・プロセツ
サへはデータは、クラスタ・モジユールにより、
バツフア・メモリ３４からローカル・プロセツサ
の関連するOUTQバツフア５４へ最初に動かさ
れる。OUTQ STATレジスタ５６内の関連する
フラグがセツトされて、パケツトの用意ができて
いることをIPB制御器に合図する。IPBからパケ
ツトを受けることを宛先ローカル・プロセツサは
指令される。そうすると、IPB制御器はパケツト
をIPBを介して宛先ローカル・プロセツサへ動か
す。

バツフア・メモリ３４内のFIFOキユーのあふ
れを阻止するために、ローカル・プロセツサとク
ラスタ・モジユールの間の流れ制御が用いられ
る。どのFIFOキユーがオンまたはオフされるか
をIPB制御器に知らせるために、INQSTATレジ
スタ７０が用いられる。このレジスタ７０内の各
ビツトは宛先プロセツサとネツトワーク内の向き
を指示する。ビツトがセツトされると、IPB制御
器はそのプロセツサに宛てられたパケツトとネツ
トワーク内の向きを拒絶する。

次に、IPB制御器の状態図が示されている第１
１図を参照する。

IPB制御器のための制御ロジツクは６つの状態
を有する状態マシンとして実現されている。それ
らの状態はSTDSEND 300，POLL 302，
OQSEND 304，RCVRSEL 306，OQRCVRSEL
308，SEND2INQ 310と呼ばれる。状態変化がい
つ起るかを指示する14種類の遷移（第１１ｂ図の
Ｔ−１〜Ｔ−14）が定められる。

POLL状態においては、情報の転送は行われな
い。パケツトを送ることを要求し（信号
SNDACK）、かつパケツト（信号RCVACK）を
受ける各ローカル・プロセツサ性能のために、
IPB制御器は各ローカル・プロセツサをポールす
る。IPB制御器はCUTQ STATレジスタ５６内
のローカル・プロセツサの関連するビツトもテス
トする（信号OUTQFULL）。

信号RCVACKとOUTQFULLがともに肯定さ
れたとすると（すなわち、ローカル・プロセツサ
が受信できるクラスタからのパケツトが存在す
る）、OQRCVRSEL状態への遷移Ｔ−10がトリ
ガされる。そうすると、クラスタ・モジユールか
らの転送が開始される。信号RCVACKと
OUTQFULLのいずれかが否定されたとすると
（すなわち、パケツトがない、またはローカル・
プロセツサはそれを受けることができない）、
IPB制御器は信号SNDACKをテストする。

信号SNDACKが肯定されると（すなわち、ロ
ーカル・プロセツサが送るべきパケツトを有す
る）、ローカル・プロセツサはパケツト宛先アド
レスをIPB上で確認する。そして、IPB制御器は
そのアドレスを受け、RCVRSEL状態へＴ−６を
トリガする。そうすると、ローカル・プロセツサ
からの転送が開始される。さもないと、遷移Ｔ−
４がトリガされ、IPB制御器は次のローカル・プ
ロセツサのポール動作を続行する。

OQRCVRSEL状態においては、クラスタ・モ
ジユールからの転送が行われようとしている。
IPB制御器はボールされたローカル・プロセツサ
を選択し、RCVCMDを確認する。ローカル・プ
ロセツサがRCVACKに応答すると、OQSEND
状態への遷移Ｔ−11がトリガされる。さもない
と、POLL状態への遷移Ｔ−９がトリガされる。

OQSEND状態においては、クラスタ・モジユ
ールからローカル・プロセツサへの転送が進行中
である。OUTQバツフアからのデータの16語が
バス上にアサートされ、ローカル・プロセツサに
より受けられる。IPB制御器３０内に設けられて
いるIPBクロツク８８がクロツク信号を発生す
る。そのクロツク信号は遷移Ｔ−４をくり返しト
リガしてこの機能を行う。転送が終ると、POLL
状態への遷移Ｔ−３がトリガされる。

RCVRSEL状態においては、ローカル・プロセ
ツサからの転送が起ろうとしている。IPB制御器
は先に確認された宛先アドレスにおけるクラスタ
の数を調べる。その数が零であると（これはロ
ーカル転送を示す）、IPB制御器が宛先ローカ
ル・プロセツサを選択して、RCVCMDを確認す
る。RCVACK応答において、STDSENDへの遷
移がトリガされる。さもなければ、POLL状態へ
の遷移Ｔ−７がトリガされる。

クラスタ数が零でなければ（これはネツトワー
ク転送を示す）IPB制御器がクラスタ・モジユー
ルに対するパケツトを受けるそれの能力を調べ
（信号INQFULL）、かつ宛先プロセツサに対する
流れ制御状態（信号INQSTAT，INQ STAT
表における関連するフラグ）を調べる。
INQFULLとINQSTATがともに否定されたとす
ると（すなわち、入力バツフアが一杯でなく、ス
トツプ・メツセージが送られていない）、
SEND2INQ状態への遷移Ｔ−12がトリガされる。
INQFULLとINQSTATのいずれかが確認される
と、POLL状態への遷移がトリガされる。

STDSEND状態においては、ローカル・プロ
セツサからローカル・プロセツサへの転送が進行
中である。送るローカル・プロセツサからのデー
タ16語がバス上で肯定され、宛先ローカル・プロ
セツサによつて受けられる。IPB制御器３０内に
設けられているIPBクロツク８８がクロツク信号
を発生する。このクロツク信号は遷移Ｔ−１をく
りかえしトリガしてこの機能を実行する。転送が
終ると、POLL状態への転送Ｔ−２がトリガされ
る。

SEND2INQ状態においては、ローカル・プロ
セツサからクラスタ・モジユールへの転送が進行
中である。送り側のローカル・プロセツサからの
データの16語がバス上で肯定され、INQバツフ
アにより受けられる。IPB制御器３０内に設けら
れているIPBクロツク８８は遷移Ｔ−13をくりか
えしトリガしてこの機能を行う。転送が終ると、
POLL状態への遷移Ｔ−８がトリガされる。

次の表は各状態遷移Ｔ−１〜Ｔ−14をトリガす
る諸条件を示す表である。

T1＝STDSEND・15 T2＝STDSEND・CNT15 T3＝OQSEND・15 T4＝OQSEND・CNT15 T5＝RCVRSEL・RCVACK・ T6＝POLL・SNDACK・（・
OUTQFULL） T7＝RCVRSEL・5・12 T8＝SEND2NQ・CNT15 T9＝OQRCVRSEL・ T10＝POLL・RCVACK・OUTQFULL T11＝OQRCVRSEL・RCVACK T12＝RCVRSEL・XRCVACK・
CLUSTNOTφ T13＝SEND2IND・15 T14＝POLL・6・10 各場合において、論理方程式中の第１項は現在
の状態である。項CNT15は、システムの同期を
保つために、送信中に保持されるパケツト内の語
の数と、パケツトの受け取りを指すものである
（第５図参照）。

【図面の簡単な説明】

第１図は本発明に使用するのに適当な種類のマ
ルチプロセツサ・システムを示し、第２図は本発
明に使用するために変更した第１図に示されてい
るマルチプロセツサ・システムを示し、第３図は
第２図に示されているマルチプロセツサ・システ
ムを用いてリングとして構成されたネツトワーク
を示し、第４図は本発明に使用できるクラスタ・
モジユールのブロツク図、第５図は本発明に使用
できるパケツトのフオーマツトを示す線図、第６
図は本発明の好適な実施例のためのアイドル・ル
ープ・ルーチンの流れ図、第７図はローカル
INQサービス・ルーチンの流れ図、第８図はロ
ーカルOUTQサービス・ルーチンの流れ図、第
９図は直列INQサービス・ルーチンの流れ図、
第１０図は直列OUTQサービス・ルーチンの流
れ図、第１１図はIPB制御器の状態図である。１０……プロセツサ、１２，１４……プロセツ
サ間バス、１６，３０……IPB制御器、１８……
Ｘクラスタ・モジユール、２０……Ｙクラスタ・
モジユール、２２……Ｘ左直列データリンク、２
４……Ｘ右直列データ・リンク、２６……Ｙ左直
列データ・リンク、２８……Ｙ右直列データ・リ
ンク、３２……クラスタ・モジユール制御器、３
６……直列データ・リンク制御器、３８……クラ
スタ・モジユール制御器インタフエース、５２…
…バツフア・メモリ、５４……OUTQバツフア、
７２……INQバツフア、７４……状態マシン。

Claims

【特許請求の範囲】１それぞれプロセツサ間バス１２，１４に接続
された少くとも１つのプロセツサ１０を含む複数
のマルチプロセツサ・システムと；それぞれ上記プロセツサ間バス１２，１４の１
つに接続され、かつデータ・リンク２２，２４，
２６，２８によつて互にリング形に接続された複
数のノード・インターフエース１８，２０と；上記各ノード・インターフエースにそれぞれ設
けられ、それぞれネツトワーク内の上記複数のプ
ロセツサの任意の１つに転送される情報パケツト
を一時的に格納するための複数の格納場所を有
し、上記複数の格納場所はネツトワーク内の上記
複数のプロセツサの特定の１つのプロセツサ、す
なわち群内の格納場所に格納される全ての情報パ
ケツトの宛先プロセツサにそれぞれ対応する複数
の格納場所群に区画されているバツフア・メモリ
３４と；上記各ノード・インターフエースにそれぞれ設
けられ、各インターフエース・ノードをそれに隣
接するインターフエース・ノードに接続するデー
タ・リンク２２，２４，２６，２８から、および
各インターフエース・ノードに接続されたプロセ
ツサ間バス１２，２４から各インターフエース・
ノードにおけるバツフア・メモリ２４への上記情
報パケツトの転送をそれぞれ制御し、かつ上記各
インターフエースのバツフア・メモリ３４から各
インターフエース・ノードをそれに隣接するイン
ターフエース・ノードに接続するデータ・リンク
２２，２４，２６，２８へ、および各インターフ
エース・ノードに接続されたプロセツサ間バス１
２，１４への上記情報パケツトをそれぞれ制御す
る制御手段３２と；上記各制御手段にそれぞれ設けられ、上記各ノ
ード・インターフエースのバツフア・メモリ３４
における特定の宛先プロセツサに対応する格納場
所群が何時充満するかをそれぞれ決定し、上記格
納場所が充満している期間中は上記特定の宛先プ
ロセツサ向けの情報パケツトの転送をそれぞれ停
止させる手段５２と；を備えている、ことを特徴とするマルチプロセツ
サ・システムのネツトワーク。