(57)【特許請求の範囲】
【請求項１】
送信ノード、一つあるいはそれ以上の中間ノード、および、ターゲット・ノードを含み、各ノードに、固有の識別（ID）が割り当てられたノードのネットワークにおいて、
前記送信ノードが、前記ターゲット・ノードのIDを含むアドレス・パケットを発生し（originating）、
前記一つあるいはそれ以上の中間ノードが、夫々
複数の入力ポートおよび複数の出力ポートであって、当該入力ポートの夫々の１つが、対応する当該出力ポートの１つと対とされ、前記アドレス・パケットが当該入力ポートの１つで受信される、複数の入力ポートおよび複数の出力ポート、
前記アドレス・パケットの前記IDを、前記中間ノードのIDと比較するため、および、前記中間ノードのIDが、前記アドレス・パケットの前記IDと等しくないときに第１状態を生成するための、比較手段、
前記入力ポートを介して前記アドレス・パケットが受信される、前記入力・ポートの１つに、前記中間ノードの前記出力ポートの１つを割り当てるための割当て手段であって、前記出力ポートの１つが、前記入力ポートであって、前記入力ポートを介して前記アドレス・パケットが受信される、前記入力ポートと対にされたものを除外し、当該割当て手段が、前記第１状態の発生に基づいて作動可能である、割当て手段、
を含み、
前記ターゲット・ノードが、
前記アドレス・パケットの前記IDを、前記ターゲット・ノードの前記IDと比較し、前記IDが前記ターゲット・ノード・アドレスと等しいときに第１状態以外の第２状態を生成するための比較手段、
を含み、
各中間ノードが、前記第１の状態の発生に基づいて、前記中間ノードから、前記中間ノードの次の１つへの、或いは、前記ターゲット・ノードへ、のパスを確立し、結果として、前記送信ノードから、前記中間ノードを通じたパスを確立するための手段、を含み、
各中間ノードおよび前記ターゲット・ノードが、応答パケットを、前記送信ノードに返送する手段を含み、当該応答パケットが、前記入力ポートであって、前記入力ポートを介して前記アドレス・パケットが受信される、前記入力ポートと対とされた前記出力ポートを介して送られる、
ことを特徴とする、ノードのネットワーク。
【請求項２】
前記応答パケットは、前ノードに対して、パスが前記中間ノードで確立されていないことを示すパス拒絶状態を戻すように、または、前記送信ノードに対して、前記中間ノードを介した前記ターゲットノードへのパスが確立されていることを示すパス確立状態を戻すように、符号化されていることを特徴とする請求項１に記載のネットワーク。
【請求項３】
前記第２状態の発生により動作して、前記ターゲットノードから前記送信ノードに対して応答パケットを返送する手段を備え、
前記応答パケットは、前記アドレスパケットが受信されたターゲットノード入力ポートと対になったターゲットノード出力ポートより送信され、
前記応答パケットは、前記送信ノードに対して、前記中間ノードを介した前記ターゲットノードへのパスが確立されていることを示すパス確立状態を戻すように、符号化されており、
確立されたパスにおける各中間ノードは、前記アドレスパケットが受信された入力ポートと対になった出力ポートより前ノードに対して前記応答パケットを送信する、ことを特徴とする請求項１に記載のネットワーク。
【請求項４】
ポートベクトルを備え、
前記割当手段は、前記第１状態の発生により該ポートベクトルから第１非割当出力ポートを選択し、
さらに、前記第１非割当出力ポートを介して前記中間ノードの次のノードに対して、或いは、前記ターゲットノードに対して、前記アドレスパケットを転送する転送手段を備えたことを特徴とする請求項１に記載のネットワーク。
【請求項５】
前記中間ノードの次のノード、或いは、前記ターゲットノードへのパスを確立する前記手段は、
前記第１状態の発生に応じて前記ポートベクトルから非割当出力ポートを順次選択する手段と、
前記ポートベクトルから非割当出力ポートを選択した結果、前記中間ノードの次のノード、或いは、前記ターゲットノードへのパスが確立されない場合に、前記アドレスパケットが受信された前記入力ポートと対になった出力ポートを介して前ノードに対してパス拒絶状態を戻すように、前記返送パケットを符号化する手段と、
を備えたことを特徴とする請求項４に記載のネットワーク。
【請求項６】
前記選択された出力ポートが利用可能でない場合に、
前記複数の出力ポートのいずれが、フォールドされた結果として、選択された出力ポートのためのフォールディングパートナーとなりうるかを示すフォールドイネーブルベクトルを備え、前記フォールディングパートナーが、選択された出力ポートの複製接続を有し、メッセージがルートされうる出力ポートであること、
を特徴とする請求項４に記載のネットワーク。
【請求項７】
メッセージ伝送が完了した場合に、メッセージパケットが受信される前記ターゲットノード入力ポートと対になった前記ターゲットノード出力ポートより、エンドトゥエンド肯定応答コマンドを送信することを特徴とする請求項３に記載のネットワーク。
【請求項８】
前記エンドトゥエンド肯定応答コマンドに応答して、前記中間ノード出力ポートと対になった中間ノード入力ポートから、中間ノード出力ポートを切断することを特徴とする請求項７に記載のネットワーク。
【請求項９】
前記送信ノードにおいて複数の送信チャネルを備え、
該送信チャネルのそれぞれは、互いに関連しつつ送信ポートベクトルを有し、
該送信ポートベクトルは、ルーティングを試みるべき前記送信ノードの選択された出力ポートを示し、
さらにスカウトパケットを備え、
該スカウトパケットは、前記送信ノードの前記選択された出力ポートのうち第１出力ポートより送信されることにより中間ノードに伝送され、核中間ノードは、前記ターゲットノードへの潜在的なパスにおける次ノードであり、
さらに、前記送信チャネルから前記送信ノードの前記選択された出力ポートの前記第１出力ポートへのパスをロックして、前記出力ポートをペンディング伝送のために確保する手段と、
パス拒絶パケットが前記第１出力ポートと対になった対応する入力ポートで後に受信される場合に、前記送信チャネルから前記第１出力ポートへの前記パスをロックする手段と、
を備えたことを特徴とする請求項１に記載のネットワーク。
【請求項１０】
ルーティング状態がルート拒絶される場合に、前記送信ポートベクトルを反転させて別の送信ポートベクトルを設ける手段と、
前記別の送信ポートベクトルを用いて該別の送信ポートベクトルから第１非割当出力ポートを選択して、前記選択された出力ポートを設ける、
ことを特徴とする請求項９に記載のネットワーク。
【請求項１１】
パス拒絶パケットが前記第１出力ポートと対になった前記対応する入力ポートで受信された前記場合に、前記送信ポートベクトルから新しい出力ポートを選択する手段と、
該新しい出力ポートより前記スカウトパケットを送信する手段と、
を備えたことを特徴とする請求項９に記載のネットワーク。
【請求項１２】
パス肯定応答パケットが前記第１出力ポートと対になった前記対応する入力ポートにおける前記送信ノードで受信される場合に、前記送信ノードにおける送信チャネルから前記ターゲットノードにおける受信チャネルに対して確立されたパスを介して、前記送信ノードから前記ターゲットノードへの伝送を開始する手段を備えたことを特徴とする請求項３に記載のネットワーク。
【請求項１３】
送信ノード、一つあるいはそれ以上の中間ノード、およびターゲットノードを含む、相互に接続されたノードのネットワークであって、
該ネットワークにおける各ノードは、固有の識別（ID）が割り当てられ、
ターゲットノードアドレスを有するアドレスパケットを発生させる前記送信ノードを備え、前記ターゲットノードのアドレスは、前記ターゲットノードの固有のIDである、
前記ネットワークにおける各ノードは、前記ターゲットノードアドレスを該ノードの前記固有のIDと比較する比較手段を含んだネットワークにおいて、
A.特定のノードの１つの入力ポートにおいて、前記相互接続されたノードの前のノードから送信された前記アドレスパケットを受信する工程であって、当該特定のノードが、前記ターゲットノード、或いは、前記中間ノードの１つであり、当該前のノードが、送信ノード、或いは、前記中間ノードの１つ、である工程と、
Ｂ．前記特定のノードの前記IDが前記ターゲットノードアドレスと等しくない場合に、前記特定のノードが中間ノードであることを示す第１状態を生成し、または、前記特定のノードの前記IDが前記ターゲットノードアドレスと等しい場合に、前記特定のノードが前記ターゲットノードであることを示す第２状態を生成する工程と、
C.前記第１状態の発生により、前記１つの入力ポートに対して、前記特定ノードの前記出力ポートのうち、前記アドレスパケットが受信される入力ポートと対になった出力ポートを除く、１つの出力ポートを割り当てる割当工程であって、前記特定ノードが、該特定ノードにおける前記第１状態の発生により次ノードへのパスを確立することにより、前記送信ノードから前記特定ノードを介した前記次のノードへのパスを確立させる割当工程と、
D.前記アドレスパケットが受信される前記入力ポートと対になった前記出力ポートより、前記特定ノードから前記送信ノードに対して返送パケットを返送する工程と、
を備えたことを特徴とする方法。
【請求項１４】
E.前記前のノードに対して、パスが前記特定ノードで確立されていないことを示すパス拒絶状態を戻すように、または、前記送信ノードに対して、前記特定ノードを介した前記ターゲットノードへのパスが確立されていることを示すパス確立状態を戻すように、前記返送パケットを符号化する工程を更に備えた請求項13に記載の方法。
【請求項１５】
E.前記特定ノードが前記ターゲットノードであることを示す前記第２状態の発生により、前記ターゲットノードから前記送信ノードに対して、返送パケットを、前記アドレスパケットが受信された前記入力ポートと対になった前記出力ポートより、返送する工程と、
F.一つあるいはそれ以上の前記中間ノードを介した前記ターゲットノードへのパスが確立されていることを示すパス確立状態を前記送信ノードへ戻すように、前記返送パケットを符号化する工程と、
G.確立されたパスにおける各中間ノードから前記前のノードに対して、前記返送パケットを、前記メッセージパケットが受信された前記入力ポートと対になった前記出力ポートより送信する工程と、
を更に備えた請求項13に記載の方法。
【請求項１６】
E.ポートベクトルを設ける工程と、
F.前記第１状態の発生により前記ポートベクトルから第１非割当出力ポートを選択する工程と、
G.前記アドレスパケットを前記第１非割当出力ポートを介して前記次ノードに対して転送する工程と、
を備えた請求項13に記載の方法。
【請求項１７】
H.前記第１状態の発生に応じて前記ポートベクトルから非割当出力ポートを順次選択する工程と、
I.前記ポートベクトルから非割当出力ポートを順次選択する工程の結果、前記次ノードへのパスが確立されていない場合に、前ノードに対してパス拒絶状態を戻すように符号化された前記返送パケットを、前記アドレスパケットが受信された前記入力ポートと対になった出力ポートを介して送信する工程と、
を更に備えた請求項16に記載の方法。
【請求項１８】
H.前記複数の出力ポートのいずれが、フォールドされた結果として、前記ポートベクトルから選択された選択された出力ポートのためのフォールディングパートナーとなりうるかを示すフォールドイネーブルベクトルを設ける工程であって、前記フォールディングパートナーは、前記アドレスパケットがルートされうる、選択された前記出力ポートの複製である工程と、
I.前記選択された出力ポートがルーティングに利用可能でないが前記フォールディングパートナーが利用可能である場合に、該フォールディングパートナーを潜在的なルーティング候補として用いる工程と、
を更に備えた請求項16に記載の方法。
【請求項１９】
H.メッセージ伝送が完了した場合に、前記アドレスパケットが受信される前記入力ポートと対になった前記出力ポートより、前記ターゲットノードからのエンドトゥエンド肯定応答コマンドパケットを送信する工程を更に備えた請求項16に記載の方法。
【請求項２０】
I.前記エンドトゥエンド肯定応答メッセージに応答して、前記中間ノード出力ポートと対になった中間ノード入力ポートから、中間ノード出力ポートを切断する工程を備えた請求項19に記載の方法。
【請求項２１】
E.前記送信ノードにおいて複数の送信チャネルを設ける工程であって、前記送信チャネルのそれぞれは、互いに関連しつつ送信ポートベクトルを有し、該送信ポートベクトルは、ルーティングを試みるべき前記送信ノードの選択された出力ポートを示す工程と、
F.前記送信ノードの前記選択された出力ポートの第１出力ポートよりアドレスパケットを送信することにより、中間ノードに前記アドレスパケットを伝送する工程であって、前記中間ノードは、前記ターゲットノードへの潜在的なパスにおける次ノードである工程と、
G.前記送信チャネルから前記送信ノードの前記第１の選択された出力ポートへのパスをロックして、前記出力ポートを保留中の伝送のために確保する工程と、
H.パス拒絶パケットがその後、前記第１出力ポートと対になった対応する入力ポートで受信される場合に、前記送信チャネルから前記第１出力ポートへの前記パスをアンロックする工程と、
を備えた請求項13に記載の方法。
【請求項２２】
I.ルーティング状態がルート拒絶である場合に、前記送信ポートベクトルを反転させて別の送信ポートベクトルを設ける工程と、
J.該別の送信ポートベクトルを用いて該別の送信ポートベクトルから第１非割当出力ポートを選択して、前記選択された出力ポートを設ける工程と、
を備えた請求項21に記載の方法。
【請求項２３】
K.パス拒絶パケットが前記第１出力ポートと対になった前記対応する入力ポートで受信された場合に、前記送信ポートベクトルから新しい出力ポートを選択する工程と、
L.前記アドレスパケットを前記新しい出力ポートより送信する工程と、
を更に備えた請求項21に記載の方法。
【請求項２４】
H.パス肯定応答パケットが前記第１出力ポートと対になった前記対応する入力ポートにおける前記送信ノードで受信された場合に、前記送信ノードにおける送信チャネルから前記ターゲットノードにおける受信チャネルに対して確立されたパスを介して、前記送信ノードから前記ターゲットノードへの伝送を開始する工程を更に備えた請求項21に記載の方法。
【発明の詳細な説明】
関連する申請とのクロスリファレンス
係留中の申請番号07/587.237、タイトル“高性能コンピュータで使用されるネットワークコミュニケーションユニット”（Stephen R.Colley,et al.1990年９月24日提出）
本発明の受託者かつnCUBE Corporationへ委託
発明の背景
発明分野
本発明はデータ処理システム、特に高性能並行処理システムに使われる通信メカニズムに関するものである。
これまでの技術の説明
アメリカ合衆国特許5,113,523はプロセッサーとメモリを含む多数の処理ノード（結合点）から成る、パラレル・プロセッサーについて説いたものである。各プロセッサーには実行構造、プロセッサーをメモリーと連結するメモリーに関係するロジック、それからインターノード（結合点）通信メカニズムがある。インターノード（結合点）通信メカニズムはハイパーキューブ・トポロジーを持つオーダーｎの第１配列を形成するように、ノード（結合点）をつなぐ。ハイパーキューブ・トポロジーに一緒に接続されているノード（結合点）を持つオーダーｎの第２列は第１列と連結されてオーダーｎ＋１列を形成する。並行プロセッサーシステムがどんなナンバーのプロセッサーでも形成されるように、オーダーｎ＋１列はオーダーｎの第１および第２列でつくられる。I/OプロセッサーセットはI/Oチャンネルを使用して、配列のノード（結合点）に接続する。インターノード（結合点）通信は全てのノード（結合点）に共通のクロックにより構成されるシリアルデータチャンネルを含む。
上で参照された係留中である出願SN07/587,237は、固定ルーティング通信システム（fixed−routing communication system）を説いたものである。この固定ルーティング通信システムの中では、アメリカ合衆国特許5,113,523で説明されているネットワークの各プロセッサーはただ１つのプロセッサーIDが割り当てられている。ポートｎを通して、お互いに接続した２個のプロセッサーのプロセッサーIDは、ｎ次ビットでのみ変化する。多数の入力ポートおよび出力ポートはそれぞれのノードで提供される。ノードの入力ポートの一つの入力ポートの制御手段は他のノードの出力ポートからカレントメッセージに関するアドレスパケット受信する。データバスはある１つの入力ポートに受信されたメッセージが、ある他の出力ポートにルートされるように一つのノードの入力・出力ポートに一緒に接続する。比較ロジックは、第１アドレスパケットとノードのプロセッサーIDの差のビットポジションを決定するため、第１アドレスパケット内のノードアドレスとノードのプロセッサーIDを比較する。比較ロジックは入力ポートによりデータバスに置かれたメッセージパケットからｎ＋１ビットから始まる第１の差のビットポジションに対応するポートナンバーを持つ出力ポートへ転送させる機能を持つ（ｎはメッセージを受信したポートのナンバーである）。
上記で参照した出願SN07/589,237で説明されている固定ルーティング設計でフォワードでなければ、提供されたソースから提供された目的地までメッセージを正確にしたルーターを取ることができ、中間ノードを通して経路が設定されるまで使用中のチャンネルから遮断される。決定した経路はディメンション・オーダー最小短の経路である。この設計は渋滞がなく、遮断されたり不完全なノード周囲のメッセージをルートしない。
本発明の目的は並行プロセッサーで遮断されたり、不完全なノード周囲のメッセージをルートする新しい通信メカニズムを提供するものである。
発明の要約
一言で言うならば、上記の目的は迷路適用性ルーティング（maze adaptive routing）メカニズムを整え、本発明を実現することで達成される。ノードＡからノードＢへ転送する迷路適応性ルーティング設計で、２個のノード間の全ての最小短パスは空いている経路を探すために試された、シングル・パケット・スカウトによりサーチされる。
一番浅い（近そうな）パスから始めて、目的地までの空いているパスを順番に調べていく。空いている最小短パスが発見されない場合、他の（最小短ではない）パスがサーチされるようになっている。（ソフトウェアがサーチを再開するとか、他のコマンドを実行できるように、中央処理装置の動作は中止される。）
本発明の特徴の一つは、目的地のノードに対するルートを発見して、設定するのに使用されたノードアドレスパケットは他の必須制御ビットおよびパラメーターを追加した目的地（ターゲット）ノードアドレスが提供される。
本発明はメカニズムが、遮断されていたり通過不能なノードを自動的に迂回するというところにその特徴がある。
また迷路ルーター（maze router）はほとんどのメッセージミックスに、優れた帯域幅制御と待機時間をしめしている。これはルートを探すために、徹底的かつ一つ一つ順序通りに調べていくためである。迷路ルーターは固定したルーティングワームホール設計の妨害を減らし、ルートサーチトラフィックを最小限に維持する。
【図面の簡単な説明】
これまでに説明してきたり、またはこれから解説する、本発明の目的、特徴、長点は、本発明の実行方法についての以下の詳細な記述や別に添付した図面を通してはっきりすることと思う。
図１は本発明が実現される、通信装置の詳細なブロックであり、
図２は図１に示された受信チャンネルのブロック図、
図３は図１に示された送信チャンネルのブロック図、
図４は図１に示された出力ポートのブロック図
図５は図１に示された出力ポートのブロック図
図６は図１に示されたルーティングレジスターおよびロジックのブロック図
図７は８個のポートからネットワークディメンション３ハイパーキューブからの迷路ルーティング例を図示している。
図８は固定された適応性ルーティング用メッセージ待機時間対ネットワーク転送データのパーセントのグラフ
図９はアドレスパケットの図面、
図10データパケットの図面
図11はコマンドパケットの図面
図12は転送動作のルーティング状態の流れ図
図13は入力ポート動作のルーティング状態の流れ図
図14はエンドトゥエンド肯定応答の図示
図15はリンクが遮断しない迷路発送タイミング図
図16はリンクが遮断された迷路ルートタイミング図である。
本件実行の説明
シグナルライン定義
次は図１に使用されるシグナルラインの略語を要約または定義したものである。
CPU:中央処理装置
CUTB:コマンド、アドレスおよびデータがポートやチャンネルの間に通過するカットスルーバス
IPINS:入力ピン
MEMADR:メモリーアドレスバス
MEMDAT:メモリーデータバス
NODEID:ノード識別番号；ノードを他のノードと区別するため、それぞれのノードプロセッサーに該当する唯一のコードナンバー
OPALL:18個のポート及び８個の受信チャンネルそれぞれに対する出力ポート割当
OPBSY:出力ポート使用中;18個の出力ポートおよび８個の受信チャンネルのうち、対応する出力ポートまたはチャンネルが使用中であることを表示する一つのライン
OPINS:出力ピン
OPSELV:出力ポートおよび受信チャンネル選択ベクトル；ルーティングロジックは選択された出力ポートおよびチャンネルを表示する
PORTCUT:カットスルーに対するポート、転送チャンネルまたは受信チャンネルを表示するベクトル
PORTRT:ルートを要請するエージェントからの候補ポートベクトル
PRB:プロセッサーバス；中央処理装置からのデータバス
RMAADR:受信DMAアドレス
RDMADAT:受信DMAデータ
SDMAADR:送信DMAアドレス
SDMADAT:送信DMAデータ
コマンド定義
ETE−ack−End−to−end acknowledge:転送が完了した時、バック・トラックはETE−ackロジックがそのパスの全てのポートを割り当てないようにパスを復帰させ、状態を発信転送チャンネルに伝達する時、転送ルートに従って反対方向に発生する。
BOT:転送開始；転送命令による転送開始を表示する転送チャンネルに発生するシグナル
EOM:メッセージのエンドメッセージのエンドであることを表示するターゲットノードに伝達されたコマンドである。
EOT:転送のエンドはこの転送の最終パケットであることを表示するターゲットノードに伝達されたコマンドである。
ETE♯ack:End−to−end肯定応答は転送がターゲットまでうまく転送されたことを示すものである。これにはレシーバー側にあるソフトウェアによってセットアップされたレシーブコードが含まれている。
ETE♯nack:エンドトゥエンド非肯定応答コマンドはメッセージがターゲットノードに連続的に伝達しないことを表示し、パリティーエラーまたは受信カウントオーバーフローのような状態に復帰させる。
ETE♯en:エンドトゥエンド・イネイブル・シグナル受信チャンネルからターゲットノードのエンドトゥエンド・ロジックが可能であることを表示するため、アドレスパケットに送信される。
Flush♯path:これはターゲットノードに対するパスへの全てのポート及びチャンネルの割り当てを解除し、開放するフラッシュコマンド
Rest♯node:これはノードおよびこのポートおよびチャンネルを初期状態に再設定するコマンドである。
Rest♯CPU:Rest♯CPUはノードからCPUを再設定するが、初期状態からポート及びチャンネルを再設定しないコマンドである。
Rcv♯rej:Receive Rejectionは受信チャンネルがターゲットノードで使用不可能であることを表示する経路拒絶コマンドである。
Rcv♯rdy:Receive Readyは受信チャンネルが転送を受けるための準備が整ったことを示すコマンドである。
Route♯rdy;Route Readyはターゲットノードおよび受信チャンネルが送信チャンネルからの転送用として獲得され、該当する送信チャンネルを表示するコマンドである。
Route♯reject:これはターゲットノードに対する全てチェックした経路が遮断されていることを示す経路拒絶コマンドである。
Rt♯ack:Route acknowledge（ルート肯定応答）はターゲットノードに取られたスカウトパケットが使用可能であり、割当（確保）られたことを示すパス肯定応答コマンドである。
Send♯rdy:Send Readyはメッセージ又は転送開始ができるように準備された送信チャンネルを示すステータスレジスターである。
図１は本発明が実現した通信装置の詳細なブロック図である。ダイレクトメモリーアクセス（DMA）バッファーとロジックブロック（10）はメモリアドレス（memadr）およびメモリーデータバスを通じてメインメモリー（図示しておらず）に接続する。８個の受信（rcv）チャンネル（12）は８個の送信チャンネル（14）と対となる。ルーティングレジスターおよびロジックブロック（16）はPortrtとOpselvを通して送信チャンネルとOpselvを通じて受信チャンネルに接続する。カットスルーアービタ（arbiter）およびシグナルブロック（18）が、送信チャンネルおよび受信チャンネルに接続される。ルーティングアービタおよびシグナルブロック（20）が、送信チャンネル（14）、並びに、ルーティングレジスタおよびロジック（16）に接続される。18個の出力ポート／入力ポートの対が、Portcut、CutおよびPortstrを介して、カットスルーアービタおよびシグナル（18）、ルーティングアービタおよび信号（20）、並びに、送信および受信チャンネルに接続される。プロセッサーバス（prb）は中央処理装置（図示しておらず）から受信チャンネル、送信チャンネル、ルーティングアービタおよびシグナルブロックおよび入力ピン（Ipins）を通じてオフチップに接続する。出力ポートはカットスルーアービタとシグナルブロック（18）および出力ピン（Opins）を通じてオフチップに接続される。
受信チャンネル
図２は図１に図示された８個の受信チャンネル（12）の中、一つのブロック図である。それぞれの受信チャンネルは受信ダイレクトメモリーアクセスレジスターRDMA（50）、受信ステータスレジスターRSTAT（52）、DMA4ワードバッファーDMABUF（54）および受信ソースベクトルレジスターRSRCVEC（56）を含む。転送データを通して受信チャンネルをカットする入力ポートは受信チャンネルがete−ackコマンドを復帰させる時、PORTCUTに配置するRSRCVECレジスターの内容により表示される。
アドレスパケットまたはデータパケットカットスルーCUTBの入力ポートから受信される。データはメモリに記録される前に受信DMAバッファーDMA BUF（54）に受け取る。データを配置するためにメモリーに記述するアドレスおよび長さは受信dmaレジスター（50）に貯蔵される。データを受信する時、これはデータレジスターバスDWBからアドレスDADRおよびワードカウントDCNTと共にメモリコントローラーに伝えられる。受信ソースベクトルレジスターRSRCVCはデータが送信された入力ポートからの表示である。エンドトゥエンド（ETE）状態を持つエンドトゥエンド（ETE）コマンドはRSTATレジスター（52）から送信ポートに逆に送信される。
送信チャンネル
図３は図１に図示された８個の送信チャンネル（14）の中の一つのブロック図である。各送信チャンネルは送信バッファーDMA、SBDMA（58）、送信DMAレジスターSMAD（60）、送信バッファーパスSBPTH（62）、送信パスレジスターSPTH（64）、エンドトゥエンドバッファーETEB（66）、エンドトゥエンドレジスターETE（68）、DMAバッファー（70）、送信ポートベクトルレジスターSPORTVEC（72）、送信ポート選択レジスターSPORTSEL（74）および送信ポート代替レジスターSPORTALT（72）を含む。
SDMAレジスター（60）はアドレスおよび長さがフィールドを貯蔵し、SBDMAレジスター（58）と二重キューになる。SPTHレジスター（64）は目的地（ターゲット）ノードのポートベクトルおよびノードアドレスを貯蔵して、SBPTHレジスターと二重キューとなる。転送の終わりにSBDMAレジスター（58）はSDMAレジスター（60）にポップされ、SBPTHレジスター（62）はSPTHレジスター（64）にポップされる。メッセージの終わりにSBDMAのみがSDMAレジスターにポップされる。
ETEレジスター（68）はエンドトゥエンド（ETE）キューの上部に存在し、ETEBレジスター（66）はエンドトゥエンド（ETE）キューの底部に存在する。エンドトゥエンドETEはCUTBUSを通じて復帰され、ETEBレジスター（66）に貯蔵される。ETEがあいていたり、使えない場合、ETEBはETEにポップされる。
CPU命令はPRBバスを使用してレジスターにアクセスする。SDMAレジスターが使用された場合、情報はバッファーSBDMA（58）に配置される。またSBDMA（58）がいっぱいに詰まっている時には、プラグはCPUに設定され、送信チャンネルが詰まっていることを示す。（SPTHおよびSBPTH用も同一）。
送信ポートベクトルSPORTVEC（72）は分離パスに存在するが、SPTHレジスターは送信チャンネルに存在する。SPORTVEC（72）は転送がルートされる出力ポートを通じて表示するビットパターンを貯蔵する。ポートベクトルはポートルートPORTRTバスを使用して、図６に図示されたルーティングロジックに通される。PORTSRCラインはチャンネルまたはポートが新しいルートを要請することを表示するように決められる。これが受け入れられる場合、ゼロフィールドから１ベクトルは出力ポート選択OPSELを通事ルーティングロジックから送信ポート選択SPORTSELレジスター（74）まで送信される。SPRTSELレジスターは一つの選択された出力ポートを表示する。送信チャンネルはアドレスパケットまたはDMABUF（70）からのデータをカットスルーバス（CUTB）を通じ出力ポートに送信される。カットスルー用出力ポートはポートカットスルー選択バスPORTCUTのポート選択ベクトルSPORTSEL（74）に配置されることで選択される。
SPORTVECベクトルは反転し、反転したベクトルは代替ポートベクトルレジスターSPORTALTに配置される。全ての選択されたルートがSPORTSELレジスターを使用して、失敗した場合、SPORTALTレジスターはSPORTSELに伝達され、代替ルート選択をするように作動する。
入力ポート
図４は図１に示された入力ポートのブロック図である。各入力データレジスターIDAT（78）、入力データバッファーIBUFDAT（80）、入力バッファーコマンドIBUFCMD（81）、入力バック・トラックデータレジスターIBAKDAT（82）、識別番号差レジスターIDDIF（84）、入力ポートソースレジスターIPORTSRC（86）、入力ポートベクトルレジスターIPORTVEC（88）および入力ポート選択レジスターIPORTSEL（90）を含む。
対応するハイパーキューブの隣のノードの出力ポートからシフトしたビット対はIPINSの入力ポートコマンドIBUFCMDレジスター（81）にシフトされる。パケットの前面ではパケットの大きさを表示するパケット型がある。ショートパケットの場合、これはIBUFDATレジスター（80）の中間にシフトする。バック・トラックコマンドである場合、これはノードのアドレスNODEIDと比較される。結果はIDDIFレジスター（84）にロードされた、異なるベクトルである。フォールディングが可能であれば、FOLDENラインが決められ、フォールドされたポートに対応するIDビットは異なるベクトルIDDIFを変更するのに使われる。IDDIFレジスターの内容はルートされるメッセージを通じて次の最小ルートポートを確認させるのに使われた入力ポートベクトルレジスターIPORTVEC（88）にロードされる。IPORTVECはポートルートバスPORTRTを通して図６のルーティングロジックで送信される。同時に、入力ポートはポートルーティングをもったルーティングロジックを通過したPORTSRCの対応するビットを決定する。
ルーティングロジックにより選択された出力ポートはIPORTSELレジスター内に記録されたOPSELVバスに表示される。またPORTSRC値は選択されたOPORTに対応するIPORTで受信された場合、SRCVECはOPORTを選択し、バック・トラックデータが送信される。ある時間データはCUTBバスに表示され、IPORTSELレジスター（90）またはSRCVECレジスターの内容はPORTCUTバスに表示され、データを受信するために出力ポートを選択する。
出力ポート
図５は図１に示された出力ポートのブロック図である。各出力ポートは出力データレジスターODAT（92）、出力データバッファーOBUFDAT（94）、出力バック・トラックデータレジスターOBAKDAT（96）および出力肯定応答データレジスターOACKDAT（98）を含む。
アドレスまたはデータパケットはカットスルーバスCUTBの入力ポートまたは送信チャンネルからつき、出力データODATレジスター（92）内にロードされる。使用中でない場合、ODATレジスターは出力バッファーデータレジスター（94）内にポップされる。ODATがいっぱいに詰まるような場合、出力ポート使用中OPBSYラインは決定される。出力バック・トラックデータOBAKDATレジスター（96）はバック・トラックコマンドを貯蔵する。出力肯定応答データOACKDATレジスター（98）はパケット肯定応答コマンドを貯蔵する。OBUFDATレジスター（94）、OBAKDATレジスター（96）およびOACKDATレジスター（98）はクロック周期当たり、２個のピン（ビット）のクロック周期毎にOPINSからビットをシフトするシフトレジスターである。
ルーティングレジスターおよびロジック
図６は図１に示されたルーティングレジスター及びロジック（16）のブロック図である。ルーティングレジスターはノード識別番号レジスターNODEID（100）、終了レジスターTERMIN（102）、フォールドイネイブルレジスターFOLDEN（104）、出力ポート割当てレジスターOPALL（108）、出力ポート使用中レジスターOPBSY（110）、代替マスクレジスターALTMSK（112）、入力・出力マスクIOMSK（114）、入力・出力選択IOSEL（116）、OPRTEN（118）およびルーティングファインドファーストワン（FFO）ロジック（120）を含む。
NODEIDレジスター（100）はこのプロセッサーのノードアドレスを含む。
端子レジスターTERMIN（102）は入力ポートが端子ポートであることを示す。端子ポートはアドレスパケットをNODEIDと比較せず、このようなポートに到着したあるアドレスパケットはターゲットノードに到着した時に受け取られる。
フォールド・イネイブルレジスターFOLDEN（104）はポートがフォールドされ得ることを示すベクトルを持っている。FOLDENはワームホールルーティングプロトコールを行なう時ルーティングFFO（120）により考慮されるために、第１ポートが私用されていなかったり、迷路ルーティングプロトコールを行なう時、PORTRTポートのフォールディングパートナーは潜在的なルーティング候補として考慮される。
送信チャンネルまたは入力ポートがパスを要請する時、PORTRTバスはXmissionパスから次のリンクを形成するために選択されうるルーティングロジックから全てのOPORTを示すベクトルを持つ。PORTRCは要請を行なうチャンネルを確認するベクトルをもち、OPALLベクトルは出力ポートが既に割り当てられたことを示す。
ワームホールルーティングプロトコールで、ファインド・ファスト・ワン（FFO）はPORTRTベクトルのビットルーティングFFO（120）が行なわれ、要請が満たされた（PORTSRCバスの）ポートを超過するビット位置から始まって、必要な場合（これは「螺旋系」サーチである。）を超過するビット位置０周囲をラップする。第1 ‘1'ビットは取られなければならないルートの次のリンクを通した出力ポートを表示する。フォールディングがこのポート（FOLDEN）用としてイネイブルされた場合、これに対応するフォールドした出力ポートはルーティング用に使用可能となり、FFOの出力ベクトルに出力される。ベクトルはOPORTENおよびOPALLがマスクされ、OPSELVバスの出力ポート選択ベクトルを形成する。OPSELVが全部ゼロである場合、ルート選択は失敗し、すなわち次のリンクをルーとするように要求した出力ポートは使用不可能であり、送信チャンネルまたはIOPORTは出力ポートが使用可能な時までルーティングを再度繰り返す。
迷路ルーティングプロトコールで、PORTRTベクトルはFOLDENレジスターにより、表示されるとき、あるフォールディングポートに対して、先に増加する。その次に、FFOが行われる前に、OPALLおよびOPORTENがマスクされる。ワームホールの場合に対して、FFO動作はPORTSRCバスに表示されたものを超過する第１ビットの位置から始まって、必要な時（‘螺旋形’サーチ）周囲をラップする。したがって、迷路ルーティングから、PORTRTベクトルからの第１使用可能な出力ポートは選択され、OPSELVバスに配置される。PORTRTポートが使用する事ができない場合、OPSELVはゼロではありえず、ルート選択は失敗する。ルート要請が送信チャンネルからである場合、送信チャンネルはETEキューからルート拒絶上ｔ愛を配置して、CPUをインタラプトする事ができる。ルート要請が入力プロトコールである場合、ルート拒絶コマンドは要請する入力ポートと対となる出力ポートを通じて、パスの移転逆に送受信されうる。
ルーティングアービタおよびシグナル
図１に示されたルーティングアービタおよび信号（20）はファインド・ファースト・ワン（FFO）チェーンである。選択された最終ポートまたは送信チャンネルが求められる。サーチが行われる次の時間、サーチはまず位置の最終位置とラウンドロビン型が処理されることのほかにすぐに開始される。ポートまたは送信チャンネルはXmissionパスに次のリンクを形成するために出力ポートを選択することができるルーティングロジック（16）からアクセスを形成するために出力ポートを選択できるルーティングロジック（16）からアクセスを得るためにルート選択を調整する。その次に、カットスルーアービタおよびシグナルロジック（18）は呼び出される。
カットスルーアービタおよびシグナル
図１に示されたカットスルーアービタおよびシグナル（18）はファインド・ファスト・ワン（FFO）チェーンである。カットスルーポート割当優先は07/587,237にて説明したものに類似しているが、ポート割当優先は配線によるものではない。選択されたチャンネルの最終ポートが求められる。サーチが行なわれた次の瞬間、サーチの最終ポジションおよびルートロビン型が処理したものの他に正確に処理される。
迷路ルーティング
図７は８個のプロセッサーネットワークディメンション３ハイパーキューブの迷路ルーティング例を図示した。ソース（src）ノード（000）は点線で表示されたルートサーチパスに従ってスカウトパケットは表の“＋”で示されたリンクと接する。001からソースノード（000）まで反対に直線で表示されている。その次に、メッセージは太い直線で表示されているように、パスのターゲットノード（111）に送信される。
カットスルーハードウェア
多重パスルーティングを維持するために、受信および送信チャンネル（12、14）は、ロジックで通信ポート（22）と別になっている。従って、各送信および受信チャンネルは選択されたポートまたはポートからデータを操作するため、カットスルーロジックを必要とする。カットスルーロジックは18ポート、８送信と８受信チャンネルのそれぞれ役割をするように模写されたSN07/587,237で説明されたものと類似している。
ルート拒絶ロジック
スカウトパケットがパスを捜査する時、これが遮断または使用中チャンネルを認識し、スカウトパケットパスのノードから各チャンネルを再度調査し、割当られていない拒絶パケットと反応しなければならない。エンドトゥエンド肯定応答（ETE−ack）パケットに使用される同一のバック・トラックパスおよびロジックを使用して、再調査する。
迷路ルート選択および再調査ロジック
パスに従うあるノードからのルートはノードIDと共にターゲットノードIDのイクスクルーシブOR（XOF）を実行することで選択される。これはSN07/587.237に説明されているように、固定ルーティング用カットスルーポート選択と全く同じであるが、非割当てられたポートはルーティングロジックにより選択される。割り当てられたパスからのポート拒絶は、対応するカットスルーセルを無効とし、次に選択されたポートを試すことになる。効果的なポート選択が残っていない場合、拒絶メッセージはパスの以前のノードまたは送信チャンネルに逆に通過する。ターゲットノードに連続的に到着するスカウトは、次に使用可能な受信チャンネルで操作された後、path♯ackメッセージとしてパスを再度調査する。送信チャンネルがpath♯ackメッセージを受信した場合、これは選択されたパスに従い、要請されたメッセージを転送して、開始することができる。全ての潜在的なパスが拒絶された場合、CPU動作は阻止され、時間任意待機と再調査はソフトウェアによって呼び出される。
図８はメッセージ待機時間対ネットワーク転送データのパーセントのグラフである。適応性迷路ルーターは実線で表示し、固定性ワーム・ホールルーターは点線で示した。３個のメッセージミックス；スモール（16パケット）、ミディアム（128パケット）、ラージ（1024パケット）が表示されている。垂直軸は第１パケットを伝達するためのパケット時間を表す、メッセージ待機時間である。水平軸は転送データのネットワークのパーセント、即ちネットワーク帯域幅転送データのパーセントである。表１で示されたメッセージミックスは図８のグラフでは、双ルーティングタイプとしてプロットされている。
0003586281.tif 000002
図８のグラフに図示されているように、迷路ルーターは大部分の状況で固定されたワーム・ホールルートを実行する。
メッセージプロトコール
End−to−End Reporting
転送はエンドトゥエンド（ETE）肯定応答がターゲットノードから、ソースノードに逆に受信されるまでパスを任意に維持することができる。ETE−ack、またはETE♯nakは伝達された転送として同一のソースに従って、ターゲットパスに逆に送信されるが、反対方向からはターゲットからソースまで転送される。ソースパスに対してターゲットはバック・トラックルーティングネットワークに従い、他の方向に転送する相手のポートを使用する。
ETE♯nakは“parity♯error"、“rcv♯count♯overflow"、または“flushed"を表示するエラー状態を含む。ETE♯ackは受信機エンドでソフトウェアにより、設定された６ビット状態のフィールドを含む。ETEパケットは相手のパスに従って、他のメッセージ後にキューされないが、バック・トラックルーティングネットワークを使用して、正常メッセージパケットの間に挟み込まれる。ETEパケットはソースノードで、転送を初期化する送信チャンネルに伝えられる。
パケットフォーマット
メッセージは他の形態のパケットを通じて伝えられる。全てのデータ転送は32ビットアドレスパケットで始まり、次に64ビットのデータ、そして８ビットのパケットオーバーヘッドを含む72ビットデータパケットである。メッセージデータはメモリー内に配列されたダブルワードでなければならない。コマンドは18ビットパケットに伝えられ、ハードウェアのみがその実行と停止を行なえる。
図９はアドレス（スカウト）パケット（32ビット）の図面である。
スタートビット            −２
パケットタイプ            −２
ノードアドレス      −18
フォワードビット          −１
ルーティングタイプ  −３
リザーブド                −２
肯定応答            −２
パリティー          −２
図10はデータパケット（72ビット）の図面である。
スタートビット        −２
パケットタイプ        −２
データ                −64
肯定応答        −２
パリティー      −２
図11はコマンドパケット（18ビット）の図面である。
スタートビット        −２
パケットタイプ        −２
コマンド              −４
ステータス      −６
肯定応答        −２
パリティー      −２
ルーティングタイプ：
ビット０は“忘れっぽい”ルーティングを示す。つまり、ある連結ノードでのシングルルートをさす。非適応性
ビット１は“漸次的な”ルーティングを示す。つまり、アドレス後のデータワームホール、回路調査（スカウトパケット）はない。
ビット２は“代替”ルーティングを示す。つまり、遠くのルーティングが、ともかく遮断されている時は、非最小パスに隣接するミスルート
000＝“迷路”ルーティング：回路調査（スカウトパケット）を使用した徹底したバック・トラック
001＝“螺旋系”ルーティング：回路調査を使用して、送信機から探されたｎ最小パスの“忘れっぽい”ルート
010＝リザーブド
011＝忘れっぽいワームホールルーティング（唯一の非適応性rtタイプ）
100＝“alternate♯maze":ソースが完全に遮断されるまで迷路、その次に必要に応じて隣接するノードを通じたルートと迷路
101＝“alternate♯helix":ソースが完全に遮断されるまでは螺旋、その次に非最小パスに従いミスルートおよび螺旋
110＝“hydra":全てのパスが遮断されるまで漸次的に迷路（ワームホール・データの後に各中間ノードから第１使用可能な最小パスポートを取る）、その次に遮断されたノードからミスルートおよび迷路
111＝“oblivious♯hydra":経路が遮断される時まで“忘れっぽい”ワームホール（ワームホールデータの後に、各中間ノードから唯一第１最小パスポートを取る）、その次に遮断されたノードからミスルート及び迷路
0003586281.tif 000003
ノードアドレッシング
プロセッサーIDおよびターゲットアドレスはシステムで256K可能なノードのうち、一つのノードを特定する18ビットユニークバリューである。ターゲットノードの18ビット物理ノードアドレスは迷路ルートが設定される時の“スカウト”パケット（回路調査）の一部としてメッセージ転送の主位に、アドレスパケット内に含まれる。新しい転送・送信物理ノードアドレス転換、ノードアドレスチェッキングとport♯vector演算に対するロジックはシステムソフトウェアにより直接的に行なわれる。
メッセージルーティング
メッセージは上記パケットフォーマット部分のルーティングタイプ型テーブルに表示されたとおり、７つの方式中、あるものにルートされる事ができる。プログラマーは“Set♯path"または“Send"コマンドのオペランドのルーティング型フィールドを通した方法を選択する。
忘れっぽいワームホールは“固定された”ルーティング設計である。提供されたソースから提供された目的地までのメッセージは正確に一つの選定されたルーティングパスを取る。一度取られたパスは最下次数アップヒル最小短パス（lowest−order uphill minimum−length path）である。メッセージデータによる即時につながれたノードアドレスであるメッセージはターゲットノード側にこの方式を差し込み、パスが空いて最小でない場合はわからないが、これが接する時、使用中のポートに遮断されて、使用中のポートが空いた時、続けられる。
本発明による迷路ルーティングは適応性ルーティング設計である。ノードＡからノードＢまでのメッセージに対して、２個のノードの間の全ての最小短パスは一つのパケットスカウトにより、同時に一括して調べられ（正確には、第１レッグが非最小であるパスが任意に調査されうる），最下アップヒルパスを開始して、ターゲットに対する空いたパスが発見される時まで、最下パスの幅の深さ−第１螺旋系横断路を行なう。ターゲットからスカウトパケットの成功的な到着はパスを設定する。その次に、path♯acknowledgeパケットが逆に送信機で伝達される時、確保されたパスはメッセージを転送するのに使用される。しかし、空いたパスが見つからなければ、阻止されたソースノードに発生し、ソフトウェアは適合する遅延後のパス調査を再度開始するか、代替ルーティング（または第１レッグパスの、他のセットを使用する）を使うことができる。
迷路ルーティングプロトコール
迷路ルーターでソース（送信機）ノードからターゲットノードまでの転送は、パスがソースノードの送信チャンネルからターゲットノードの受信チャンネルまで設定されるまで、達成されない。パスは次のように設定される。
送受信ノードで
ソースの送信チャンネルは、それぞれ初期に調査されうるルーティングを通して、送信機のノードの出力ポートを表示して、送信命令を通してソフトウェアにより提供されるsend♯port♯vector（SPRTVEC）に関係する。これらのポートは最小短パスを開始することもしないこともできる。従って、この第１ホップは非最小にルートすることができ、全てのサブシークエントホップは、最小パスのみをターゲットに取ることができる。言い換えると迷路ルートはノードセットとターゲットノードの間に最小パスの徹底したサーチを行い、ソースノードまたは所定の首位中間アクセス可能な、隣接したノードを含めて設定される。
ターゲットノードのノードアドレスを含むスカウトパケットは、可能な空いているソースの選択された出力ポートの１番目に送信されるので、潜在的なパスからターゲットノードに対する次のノードである、隣接したノードに伝達される。path♯rejection packetが対応する入力ポートに順次的に受信されない限り、送信チャンネルから選択された出力ポートまでのパスは隠され、ペンディング転送用として確保される。選択された出力ポートがpath♯rejection packetを受信した場合、次のノードを超過する全てのパスが遮断されるために、使用可能な場合、send♯port♯vectorからの新しい出力ポートが選択されることができ、スカウトパケットはポートを送信する。多くのsend♯port♯vector出力ポートが使用不可能な時、これらが遮断または拒絶されるために、“all♯paths♯blocked"状態は各送信チャンネル用ETEキューにプッシュされ、CPUは阻止され、送信チャンネルは待機状態となり、クリアするためにソフトウェアを待つ。しかし、path♯acknowlege packetが受信される場合、これはサーチおよび今開始されたサブシークエント転送用として確保されたサーチおよび選択されたパスの残りを初期化するSend♯DMA♯Channelに逆に通過する。
ターゲットノードで
入力ポート中一つにスカウトパケットを受信するノードは、先にスカウトパケットからのターゲットノードアドレスを自分のノードIDと比較する。これらが一致すれば、スカウトパケットはターゲットノードを発見する。受信チャンネルが空いている場合、スカウトパケットは受信チャンネルに伝えられ、path♯acknowledge packetは逆に全ての方法を、ソース（送信機）、ノードに送信し、スカウトパスの成功的なレッグを再び試みることになる。受信チャンネルが使用不可能な時、“rvc♯channel♯unavailable"コマンドとしてエンコードされたpath♯rejection packetは設定されたパスを通じ、ソースノードに逆に送信され、入力ポートは空く。
中間ノードで
受信ノードのノードIDが、ターゲットアドレスと一致しない時、このノードは中間ノードであり、スカウトパケットをターゲットノードに対する最小短パスに従い、隣接するノードに伝達するように試みることができる。これらの間のハミング距離である、このノードのノードIDに対するターゲットノードアドレスのXORは出力ポートが最小短に接続されたことをしめし、カットスルーベクトルとして、IPORTVECレジスターにラッチされる。この入力ポートと一対となる出力ポート、即ちせいかくに逆に発生するスカウトからのノードの逆リンクはカットスルーベクトルから反応がないので、非最小ルート（第１ホップで割当てられる）により、発生することができるあるサイクルを予防する。フォールディングが可能な場合、カットスルーベクトルのフォールドされたバートナーに対応するビットが決定する。スカウトパケットはこの入力ポートを超過して始まり、可能となった空いたカットスルー出力ポート中、第１番目に送信される。path♯rejection packetが出力ポートの相手の入力ポートから受信されない限り、受信する時まで入力ポートから選択された出力ポートまでのパスはペンディング転送用に確保される。path♯rejection packetが受信した時、次のノードを初期化する全てのパスは使用可能な場合、遮断され、新しいカットスルーポートは選択されることができ、スカウトパケットはこのポートを送信する。多くのカットスルーポートがこのノードから使用不可能な時、path♯rejection packetはここに獲得されたスカウトパケット中、一つの以前のノードに送信され、入力ポートは空く。しかし、path♯rejection packetが受信された時、設定されたバスとサブシークエント転送用として確保され、選択されたパスの残りを通してソースノードに逆に通過する。
上記プロセッサーはターゲットに対する空いたパスが発生して、選択される時までまたはソースノードからの全ての、願うパスが試され、失敗する時まで繰り返される。
パスcmdパケット
スカウトはpath♯cmd packetを逆に送信することで、path♯rejection状態を以前のノードに復帰させたり、path♯found状態をソースノードに復帰させる。path♯cmdパケットはETEパケットと同一のパスの“状態”ポートを使用してパスに従って逆に送信される。２種類のpath♯cmdパケットがある。スカウトがパスをターゲットノードに設定したことを示す“path♯acknowledge"パケットは全ての方式をソースに逆に伝達してサブシークエントの転送用として設定されたパスを通過する。スカウトが中間ノードで完璧に遮断されたことを示す“path♯reject"パケットはパスの以前のノードに伝達され、この方法に従ってパス（この最終ホップ）をクリアする。このノードからの新しいパスは今試みることができたり、新しいパスがこのノードからオープン残さない場合、“path♯rejection"パケットを先行ノードに順に転送することができる。これが先行ノードを持っていない場合、即ちソースノードである場合、拒絶パケットはETEキューに配置され、送信DMAチャンネルは待機状態となり、CPUは阻止される。
代替送信ポートベクトルを使用するルーティング再調査
ルーティングロジックが提供されるsend♯port♯vectorを使用するパスを発見するのに失敗した場合、パスの代替セットはCPUを阻止する前に任意に試みることができる。
代替ルーティングが可能である時と、初期セットが失敗した後、初期send♯port♯vectorは反転し、新しいsend♯port♯vectorを形成するためにalternate♯port♯maskでANDされる。その次に第２の調査は初期の調査に使用していない、隣接するノードを通してファインディングからルートが形成される。また代替ルートが失敗した場合、CPUは通常の方法から阻止される。
全てのルーティングが第１ホップの後に最小化するために、代替送信ポートを通じた非最小パスは正確に最小よりもより大きい２ホップである。ソース及びターゲットノードがｊディメンションから分離した場合、最小パスの長さはｊホップであり、代替パスの距離はｊ＋２ホップである。
特に、代替ルートの調査は一番短いターゲットノードに対する転送用として重要になり得る。例を挙げれば、全ての他の隣接するものを通してルートを調査することで、接続する隣に対してただ一つの最小短パスがあり、代替マスクにより、説明したようにディメンションｎでの任意の最も近い隣のノードに対するｎ唯一のパスの集合がある。
単位ノード当たり一つのAlternate♯Port♯Maskがあるが、代替ルーティングは単位転送ベーシス（SEND命令のパス設定オペランドでのビット）で可能である。
フォールディング
フォールディングは最大の大きさではないシステムでメッセージをルートするのに使用可能な出力ポートの数を増加させる。ロウワー８出力ポートでnearest♯neighborノードの対応する入力ポートまでの任意の接続は逆順序に同一のnearest♯neighborノードにアッパー８出力ポートをコピーすることができる。言い換えれば、相互接続ネットワークの任意のサブセットは他に使用していないアッパーポートにコピーすることができる。
フォールディングが可能である場合（図６のFOLDEN♯register参照）、ポートベクトル（PORTVEC）は中間ノードで計算され、フォールドされたある選択されたポートはポートベクトルに選択されるように、これらがそれぞれ相対ポートを可能にすることができる。
ワームホールルートのあるホップで、探そうとするディメンションに対するリンクをコピーする２つのフォールドのうち、一つは使用できる。従って、フォールディングはワームホールルートの機会を多い区向上させるこの方法で、最小のターゲットを発見したり、遮断したりしない。
迷路ルートで、フォールディングは各ホップで調査することのできる最小パスリンクの数を増加させることで、オープンパスを発見する機会を増加させる。
フォワーディング
迷路ルートはルートをフォールディングノードで発見し、パスを反転させた後、次のアドレス（メッセージデータから採ってきたもの）をノードに転送し、アドレスはここで新しいノードまで迷路ルートされる。これは新しいアドレスがフォワードされる限り、反復されたり、全体パスが解決され、非割当された場合に、ルートが発見されることがない時まで、“forward♯route♯rejected"コマンドは送信チャンネルETEキューに転送される。一方、最終ターゲットノードに対する経路が設定された場合、メッセージデータはソースからターゲットまで正常的に転送される。
通信ダイレクトメモリーアクセス（DMA）チャンネル
メッセージはダブルワード（64ビット）増加し、送信機の物理メモリーの連続的なブロックから受信機の物理メモリーの連続的なブロックへ転送される。メモリーアクセスおよび転送の両方のエンドでのメッセージおよびパス制御を提供するため、各プロセッサーでの８個の送信DMAチャンネルが存在する。
DMAチャンネルは適合するSENDまたはRECEIVE命令が設定される。また、Set♯DMA命令はSENDまたはRECEIVE命令のDMAオペレンドを設定することを助けるために提供された。SENDまたはRECIEVEオペレンドはDMAチャンネルおよびルーティングロジック用としてパスを制御、メッセージパラメーター、アドレス等を提供する。
DMAメモリーの帯域幅でページモード、ページブレーク制限を減少させるために、各チャンネル、送信または受信はデータの32ビットまでバッファーされる。これは４つの二重ワード（64ビット）メモリーアクセスに対応する。メッセージは二重ワード境界に配置され、大きさは二重ワード倍数である。
送信DMA
各送信チャンネルはパスレジスターに貯蔵されたターゲットノードIDおよびsend♯port♯vectorばかりではなく、DMAレジスターに貯蔵された物理メモリーアドレスおよびメッセージの長さに関係する。送信チャンネルは二重バッファーとなるために、次のメッセージのDMAおよびパス制御記述子（descriptor）を設定することができ、最近のものは転送される。通信ソフトウェアはメッセージオーバーヘッドを隠して、送信チェーニングを効果的に充足させる長点を使用することができる。
送信チャンネルが新しい転送用に設定された後、これはパスをターゲットノードに設定するためにルーティング状態を加入する。漸次的にルーティングする場合、アドレスパケットが出力ポートに転送されるとき、または迷路をルーティングする場合、path♯acknowledge packetがチャンネルに受信される時、パスは設定される。
ノードアドレスがフォワードである場合、送信チャンネルはフォワーディング状態を加入して、最終アドレスパケットがフォワードとして表示されない時までアドレスパケットをメッセージデータに転送する。迷路をルーティングする場合、各アドレスが転送された後、チャンネルはpath♯acknowledgeを待機する。
送信チャンネルがパスをターゲットノードに設定するとき、メモリーからメッセージデータを判読し、パスに従ってターゲットノードに転送しはじめる。メッセージデータがフェッチされるとき、長さのカウンターがゼロに到達する時まで、メモリーアドレスは増加され、メッセージの長さは減少する。送信カウンターがゼロに到達する時、EOM（End−of−Message）またはEOT（End−of−Transmission）パケットはチャンネル設定のEOT可能ビットに従って送信される。
これがEOMである場合、DMAレジスターはクリアされ、新しいものは送信バッファーからポップされる。EOTおよびETEがイネイブルされない場合、DMAおよびパスレジスターは全てクリアされ、送信バッファーにリロードされる。EOTおよびETEがイネイブルな時、送信チャンネルはこの方式にクリアされず、ETEパケットを待つ。ETEパケットが到着する時、これはETEキュー内にプッシュされ、送信チャンネル（両レジスター）はクリアされる。その後、送信チャンネルは準備された場合、次の転送（送信バッファーをポップにする）に直接移動する。送信バッファーがEOMまたはEOT条件により、ポップされる時CPUは空いた送信チャンネルは使用できることを表示するようにインタラプトする。また、ETEはインタラプトがイネイブルである時、インタラプトを発生させる。
また迷路ルーティングである時、ETEキューはルートがターゲットノードに発見されることがない場合の状態情報にプッシュされる。この場合にpath♯rdyビットはクリアされ、ETEインタラプトは高まり、DMAチャンネルはポップされず、クリアされなかったり、リロードされない。プログラマーは対応するDMAレジスターに記録されることで続けて送信チャンネルをクリアすることができる。進行する送信転送はチャンネルDMAレジスターでDMA♯rdyビットをクリアすることで、中止されうる。これは転送を中止するが、転送状態に残るようになる。DMA♯rdyビットは送信チャンネルに対応して、Send♯rdyレジスターの各ビットに１を記録することでクリアされうる（送信チャンネル状態レジスターを参照）。
遮断されたり中止された送信転送は送信チャンネルに対応する、Send♯transmission♯rdyレジスターの各ビットに１を記録することで、プッシュされる（送信チャンネル状態レジスターを参照）。
メッセージがプッシュされる時、flush♯cmdパケットは割り当てられたパスを横切って、この後ろのパスをクリアして非割当する。
End−to−Endキュー
ETE（End−to−End）キューである各送信チャンネルに対して、ターゲットノードの受信チャンネルからのETE状態またはroute♯rejectionまたはエラー状態はプッシュされる。状態がETEキューにプッシュされる時、ETEインタラプトが発生する。キューは２エントリーの深さで、書く送信チャンネル中一つのプロセッサーレジスターは両エントリーを含む、プログラマーはRDPR命令を通じて、サイド効果なく、ETEキューを判読することができる。その後、プログラマーはWRPR命令（いっしょに判読されても、キュー内の各エントリーは個別に記録される）を通じてゼロをこの正当なビットに記録することで、ETEエントリーをクリアすることができる。第１エントリーがこの方式からクリア（ポップ）される時、第２エントリーは自動的にこの位置にコピーされ、クリアされる。送信チャンネルは新しい転送を開始することができず、ETEキューはみたされる。
送信動作
図12は送信動作の流れ図である。停止状態から、送信チャンネルはルーティング状態（200）に入る。第１非割当出力ポートは送信ポートベクトル（202）から選択される。ポートが（204）から選択された場合、流れはブロック（206）に進行する。送信チャンネルは選択されたポートを割当て、選択された出力ポート（208）からアドレスパケットを送信する。その次に送信チャンネルはルートコマンド（210）を通じて復帰されるようにルーティング状態を待つ。
ルートコマンドが到着する時、状態（212）は拒絶されたルートまたは設定されたルート中の一つである。ブロック（212）で状態が拒絶されたルートである場合、送信チャンネルは送信ポートベクトルの対応するビットをクリアし、ポート選択をクリアして、ブロック（206）から割り当てられた出力ポートを非割当てする。送信ポートベクトルが今、０に減少した場合、代替ルーティングは（205）からイネイブルされるが、シークエンスを通じて、第１通過（207）が存在しない場合、送信チャンネルはroute−rej状態をETERキューにプッシュし、インタラプトがイネイブルである場合、送信チャンネルはCPU（218）をインタラプトする。その後、送信チャンネルは停止状態（220）に入る。
ブロック（212）で、ルートが設定された場合、route♯readyは（222）から設定され、フォワードビットは（223）からチェックされる。フォワードビットが設定された場合、フォワーディング状態は（225）に入る。そうでなければ、加入メッセージ転送状態は（224）に入る。メッセージカウントが０である時まで送信チャンネルはデータをターゲットノードに転送する。
ブロック（204）で、ポートが選択されない場合、流れを決定するブロック（205）に進行する。代替ルーティングがイネイブルされ、流れのシークエンス（207）を通じた第１通過である場合、SPORTVECは初期send♯portベクトル（209）の反転バージョンと同一に形成される。従って、全て初期に調査されたルートが初期SPORTVECを使用して失敗した時、反転バージョンは流れがブロック（202）に進行する時の代替ルート選択トライを提供する。第１非割当て出力ポートは、今、反転された送信ポートベクトル（202）から選択される。ポートが（204）から選択される場合、流れはブロック（206）に進行する。ポートが（204）から選択されない場合、流れはブロック（205）に進行する。代替ルーティングは（205）でイネイブルされるが、シークエンスを通じた第１通過（207）が存在しないので、流れはブロック（218）に進行する。送信チャンネルはroute♯rej状態をETEキューにプッシュし、インタラプトがイネイブルな場合、送信チャンネルはCPU（218）をインタラプトする。その次に送信チャンネルは停止状態（220）に入る。
受信DMA
各受信チャンネルはそれぞれのDMAレジスターに貯蔵された物理メモリーアドレスおよびメッセージの長さ（また、受信カウントともいう）に関係する。またこれはエラー状態および受信コードを含むrcv♯statusレジスターを持つ。メッセージがチャンネルを通じて流れる時、長さが是のに到達したり、EOM/EJTパケットが受信する時までアドレスは増加し、メッセージの長さは減少する。
カウンターがゼロに到達する前または、これがゼロに到達した後、受信チャンネルがEOMまたはEOTを受信する場合、メッセージは連続的に完成して、チャンネルは停止状態に復帰させ、dma♯rdyをクリアする。受信エラーが受信時発生しない場合、rcv♯rdyインタラプトは高まる。そうでなければ、rcv♯errインタラプトは高まる。
例を挙げれば、パリティーエラーが転送パスに従って決定された場合、parity♯err flush♯messageは（送信機の送信チャンネルに逆に伝達されるばかりでなく）ターゲットの受信チャンネルにフォワードで伝達される。受信状態フィールドではパリティーエラーまたはフラッシュビットは設定され、ターゲットCPUは受信チャンネルにより、rcv♯errインタラプトされる。受信カウンターがゼロに到達する場合、メッセージは完成し、次のパ毛とはEOMまたはEOTでありうる。そうでない場合、受信状態フィールドでのrcv♯count♯overflowプラグは設定され、またEOMまたはEOTが受信されるまで、全てのパケットは無視、すなわち簡単に忘却にシフトされ、この時点で、rcv♯errインタラプトは形成される。カウンターはラップされ、続けて減少するので（アドレスは増加しない）、プログラマーが氾濫するメッセージを計算する方法を提供する。
プログラマーはチャンネル関連するプロセッサーレジスターを簡単に判読するので、いつでも受信状態、メッセージカウント等を判読することができる。
受信チャンネルでのスキャッター／ギャザー
受信機での早い“集める”機能を促進するため、プログラマーは提供された転送用受信チャンネルで“ignore♯EOM"プラグを任意に設定することができる（受信命令説明を参照）。従って、送信機は個別メッセージとしてデータの解体バンドル（disjoint bundles）を集めることができ、インタラプトを取り、全てのメッセージ後、新しいreceive♯DMAを設定するよりも、ただDMA動作で連続的にバンドルを貯蔵する。
“バラバラにする”機能を行なうために、プログラマーは受信チャンネルから“force♯EOM"プログラムを任意に設定することができる。従って、送信機能は一つのメッセージの連続するデータブロックを伝達することができ、受信機は転送のサブパス用メッセージパスを得るように設定されることができるので、サブブロックのないデータをメモリーの他の領域に散らして置くことになる。受信チャンネルは到来したメッセージよりもっと短い長さに設定され、長さのカウントがゼロに成る時、受信チャンネルはEOMとして扱い、新しいDMAパラメーターがプログラマーに設定されるまで、到来データを遮断する。これは物理メモリーページを解体するように図示される仮想記憶ページ境界を通過するメッセージであるDMA用として使用する。
入力ポートからのルーティング
図13はアドレスパケット入力ポート動作を図示する流れである。入力ポートはアドレスパケット（300）を受信し、このノード（302）のノードIDを持つアドレスパケットないのアドレスのイクスクルーシブORを計算する。結果はID♯diffである。ID♯diffが０であるか、入力ポートが端子として表示される場合、流れはブロック（322）に進む。そうでなければ、流れはブロック（306）に進行する。
ブロック（306）で、ポートベクトル（PortVec）は発生し、第１非割当出力ポート（308）を選択するのに使用される。
ブロック（310）で、ポートが選択されない時、入力ポートはこの入力ポート（335）と対となっている、出力ポートを通じてroute♯rejectコマンドを送信し、新しいアドレスパケット（336）を待つ。
ポートが（31）から選択される場合、アドレスパケットは選択された出力ポート（312）を通じて次のノードにフォワードされ、ポートは割り当てられる。このノードを通じて転送パスは、この瞬間に設定され、入力ポートは到来ルートコマンド（413）により、供給されることができるルーティング状態を待つ。ルートコマンド（316）はルートが拒絶されたり、ルートが準備されたことを表示する事ができる。拒絶された場合、流れはブロック（318）に進行する。準備された場合、流れはブロック（330）に進行する。
ブロック（318）で、受信チャンネルはポートベクトルで対応するビットをクリアし、ポート選択をクリアして、ブロック（312）で割り当てられた出力ポートを非割当てする。入力ポートは次の非割当て出力ポートをルーティングロジックを通して、ポートベクトル（308）で選択し；流れは上述したのと同じく流れる。
決定ブロック（308）で、ノードIDがアドレスパケットないのアドレスと同一であったり、このポートが端子である場合、このノードはターゲットノードであり、流れはブロック（322）に進む。
ブロック（322）で、ポートベクトル（PortVec）は発生し、第１準備受信チャンネル（324）を選択するのに使われる。チャンネルが（326）で選択された場合、入力ポートはメッセージ（328）を受信するために、受信チャンネルを割り当てる。入力ポートはこの入力ポート（330）と対となる出力ポートを通じてルート準備（route♯rdy）コマンドを送信し、（322）に到着するため、メッセージデータを待つ。
ブロック（326）で、チャンネルが選択されない場合、入力ポートはこの入力ポート（335）と対となった出力ポートを通じて、route♯rejectコマンドを転送し、新しいアドレスパケット（336）を待つ。
エンドトゥエンドリポーティング
図14はエンドトゥエンド肯定応答を図示した。ソースノード（350）で、送信チャンネルは出力ポート（352）からのメッセージパケットを入力ポート（354）からメッセージを受信する中間ノード（355）に送信する。メッセージは出力ポート（356）からの中間ノード（354）により、送信される。メッセージはターゲットノード（358）がメッセージパケットを受信するまで、ノードからノードまで移動する。受信チャンネルは（362）で割当てられ、ETE♯ackメッセージはパス［ポート（361、353及び351）］の各入力ポートと対となる出力ポートを使用することで、同一パスから逆に送信される。ETE♯ackがソースノードから受信され、状態がETE♯ackに復帰する時まで、メッセージパスは維持される。各送信チャンネルで、エンドトゥエンド（ETE）キューが存在し、ETE状態はプッシュされる。エンドトゥエンド状態がETEキューにプッシュされる時、Send♯rdy及びETEインタラプトはこの状態に従って発生する。
図15は遮断されたリンクがない迷路ルートタイミング図である。
図16は遮断されたリンクがあり、バックトラッキングが呼び足した迷路ルートタイミング図である。
発明の詳細な説明の項ではなかった具体的な実施状態、また実施例はどこまでも本発明の技術内容を明白にするもので、それと同じ具体例でのみ限定され、狭義に解釈されなければならず、本発明の精神と次に記載する特許請求事項の範囲内でいくつか変更して実施することができる。
【図１】
0003586281.tif 000004
【図２】
0003586281.tif 000005
【図４】
0003586281.tif 000006
【図３】
0003586281.tif 000007
【図５】
0003586281.tif 000008
【図７】
0003586281.tif 000009
【図６】
0003586281.tif 000010
【図８】
0003586281.tif 000011
【図９】
0003586281.tif 000012
【図１０】
0003586281.tif 000013
【図１１】
0003586281.tif 000014
【図１６】
0003586281.tif 000015
【図１２】
0003586281.tif 000016
【図１３】
0003586281.tif 000017
【図１４】
0003586281.tif 000018
【図１５】
0003586281.tif 000019