JPH10507015A - 適応性ルーターを使用するネットワーク通信装置 - Google Patents

Abstract

(57)【要約】 パラレルプロセッサーネットワークはそれぞれのノードが多数のI/O ポートを含むプロセッサーを含めた多数のノードおよび、ローカルメモリーで構成される。通信パスは第１アドレスパケットのターゲットノードアドレスをノードのプロセッサーIDと比較することで、ノードを通して設定する。ノードアドレスがターゲットノードアドレスである場合、受信チャンネルは入力ポートに割り当てられ、route#ready コマンドは入力ポートと対となり、出力ポートに送信される。ノードアドレスがターゲットノードアドレスではない場合、第１非割当て出力ポートベクトルから選択され、アドレスパケットは選択された出力ポートの次のノードにフォワードされる。

Description

【発明の詳細な説明】 適応性ルーターを使用するネットワーク通信装置 関連する申請とのクロスリファレンス 係留中の申請番号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 の差のビットポジションを決定するため、第１アドレスパケット内のノードアド レスとノードのプロセッサーＩＤを比較する。比較ロジックは入力ポートにより データバスに置かれたメッセージパケットからｎ＋１ビットから始まる第１の差 のビットポジションに対応するポートナンバーを持つ出力ポートヘ転送させる機 能を持つ（ｎはメッセージを受信したポートのナンバーである）。 上記で参照した出願SN07/589,237で説明されている固定ルーティング設計でフ ォワードでなければ、提供されたソースから提供された目的地までメッセージを 正確にしたルーターを取ることができ、中間ノードを通して経路が設定されるま で使用中のチャンネルから遮断される。決定した経路はディメンション・オーダ ー最小短の経路である。この設計は渋滞がなく、遮断されたり不完全なノード周 囲のメッセージをルートしない。 本発明の目的は並行プロセッサーで遮断されたり、不完全なノード周囲のメッ セージをルートする新しい通信メカニズムを提供するものである。 発明の要約 一言で言うならば、上記の目的は迷路適用性ルーティング(maze adaptive rou ting）メカニズムを整え、本発明を実現することで達成される。ノードＡからノ ードＢへ転送する迷路適応性ルーティング設計で、２個のノード間の全ての最小 短パスは空いている経路を探すために試された、シングル・パケット・スカウト によりサーチされる。 一番浅い（近そうな）パスから始めて、目的地までの空いているパスを順番に 調べていく。空いている最小短パスが発見されない場合、他の（最小短ではない ）パスがサーチされるようになっている。（ソフトウェアがサーチを再開すると か、他のコマンドを実行できるように、中央処理装置の動作は中止される。） 本発明の特徴の一つは、目的地のノードに対するルートを発見して、設定する のに使用されたノードアドレスパケットは他の必須制御ビットおよびパラメータ ーを追加した目的地（ターゲット）ノードアドレスが提供される。 本発明はメカニズムが、遮断されていたり通過不能なノードを自動的に迂回す るというところにその特徴がある。 また迷路ルーター（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：転送が完了した時、バック・トラックはET E-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)はメモリアドレス（memad r）およびメモリーデータバスを通じてメインメモリー（図示しておらず）に接 続する。８個の受信(rcv)チャンネル（12）は８個の送信チャンネル（14）と対 となる。ルーティングレジスターおよびロジックブロック（16）はPortrtとOpse lvを通して送信チャンネルとOpselvを通じて受信チャンネルに接続する。カット スルーアービタ(arbiter)およびシグナル（18）、ルーティングアービタとシグ ナル（20）およびPortcut、CutbおよびPortsrc を通して送信及び受信チャンネ ルに接続する。プロセッサーバス(prb)は中央処理装置（図示しておらず）か ら受信チャンネル、送信チャンネル、ルーティングアービタおよびシグナルブロ ックおよび入力ピン（Ipins）を通じてオフチップに接続する。出力ポートはカ ットスルーアービタとシグナルブロック（18）および出力ピン(Opinｓ)を通じて オフチップに接続される。 受信チャンネル 図２は図１に図示された８個の受信チャンネル（12）の中、一つのブロック図 である。それぞれの受信チャンネルは受信ダイレクトメモリーアクセスレジスタ ーRDMA（50）、受信ステータスレジスターRSTAT（52）、DMA 4ワードバッファー DMABUF（54）および受信ソースベクトルレジスターRSRCVEC(56)を含む。転送デ ータを通して受信チャンネルをカットする入力ポートは受信チャンネルがete-ac kコマンドを復帰させる時、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）は転送がルートされる出力ポート を通じて表示するビットパターンを貯蔵する。ポートベクトルはポートルートPO RTRTバスを使用して、図６に図示されたルーティングロジックに通される。PORT SRC ラインはチャンネルまたはポートが新しいルートを要請することを表示する ように決められる。これが受け入れられる場合、ゼロフィールドから１ベクトル は出力ポート選択OPSEL を通事ルーティングロジックから送信ポート選択SPORTS ELレジスター（74）まで送信される。SPRTSEL レジスターは一つの選択された出 力ポートを表示する。送信チャンネルはアドレスパケットまたはDMABUF（70）か らのデータをカットスルーバス（CUTB）を通じ出力ポートに送信される。カット スルー用出力ポートはポートカットスルー選択バスPORTCUT のポート選択ベクト ルSPORTSEL（74）に配置されることで選択される。 SPORTVECベクトルは反転し、反転したベクトルは代替ポートベクトルレジスタ ーSPORTALTに配置される。全ての選択されたルートがSPORTSELレジスターを使用 して、失敗した場合、SPORTALTレジスターはSPORTSELに伝達され、代替ルート選 択をするように作動する。 入力ポート 図４は図１に示された入力ポートのブロック図である。各入力データレジスタ ーIDAT（78）、入力データバッファーIBUFDAT（80）、入力バッファーコマンドI BUFCMD(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）にロードされる。IP ORTVECはポートルートバス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）、OBAKDA Tレジスター（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 バスの）ポートを超過するビット位置から始まって、必要な場合 （これは「螺旋系」サーチである。）を超過するビット位置０周囲をラップする 。第１‘１’ビットは取られなければならないルートの次のリンクを通した出力 ポートを表示する。フォールディングがこのポート（FOLDEN）用としてイネイブ ルされた場合、これに対応するフォールドした出力ポートはルーティング用に使 用可能となり、FFO の出力ベクトルに出力される。ベクトルはOPORTEN およびOP ALL がマスクされ、OPSELVバスの出力ポート選択ベクトルを形成する。OPSELVが 全部ゼロである場合、ルート選択は失敗し、すなわち次のリンクをルーとするよ うに要求した出力ポートは使用不可能であり、送信チャンネルまたはIOPORTは出 力ポートが使用可能な時までルーティングを再度繰り返す。 迷路ルーティングプロトコールで、PORTRTベクトルはFOLDENレジスターにより 、表示されるとき、あるフォールディングポートに対して、先に増加する。その 次に、FFO が行われる前に、OPALL およびOPORTEN がマスクされる。ワームホー ルの場合に対して、FFO 動作はPORTSRC バスに表示されたものを超過する第１ビ ットの位置から始まって、必要な時(‘螺旋形’サーチ)周囲をラップする。した がって、迷路ルーティングから、PORTRTベクトルからの第１使用可能な出力ポー トは選択され、OPSELVバスに配置される。PORTRTポートが使用する事かできない 場 合、OPSELVはゼロではありえず、ルート選択は失敗する。ルート要請が送信チャ ンネルからである場合、送信チャンネルはETE キューからルート拒絶上t愛を配 置して、CPU をインタラプトする事ができる。ルート要請が入力プロトコールで ある場合、ルート拒絶コマンドは要請する入力ポートと対となる出力ポートを通 じて、パスの移転逆に送受信されうる。 ルーティングアービタおよびシグナル 図１に示されたルーティングアービタおよび信号（20）はファインド・ファー スト・ワン（FFO）チェーンである。選択された最終ポートまたは送信チャンネ ルが求められる。サーチが行われる次の時間、サーチはまず位置の最終位置とラ ウンドロビン型が処理されることのほかにすぐに開始される。ポートまたは送信 チャンネルはXmissionパスに次のリンクを形成するために出力ポートを選択する ことができるルーティングロジック（16）からアクセスを形成するために出力ポ ートを選択できるルーティングロジック（16）からアクセスを得るためにルート 選択を調整する。その次に、カットスルーアービタおよびシグナルロジック（18 ）は呼び出される。 カットスルーアービタおよびシグナル 図１に示されたカットスルーアービタおよびシグナル（18）はファインド・フ ァスト・ワン（FFO）チェーンである。カットスルーポート割当優先は07/587,23 7にて説明したものに類似しているが、ポート割当優先は配線によるものではな い。選択されたチャンネルの最終ポートが求められる。サーチが行なわれた次の 瞬間、サーチの最終ポジションおよびルートロビン型が処理したものの他に正確 に処理される。 迷路ルーティング 図７は８個のプロセッサーネットワークディメンション３ハイパーキューブの 迷路ルーティング例を図示した。ソース(src)ノード(000)は点線で表示されたル ートサーチパスに従ってスカウトパケットは表の“+”で示されたリンクと接 する。001 からソースノード(000)まで反対に直線で表示されている。その次に 、メッセージは太い直線で表示されているように、パスのターゲットノード（11 1）に送信される。 カットスルーハードウェア 多重パスルーティングを維持するために、受信および送信チャンネル（12、14 ）は、ロジックで通信ポート（22）と別になっている。従って、各送信および受 信チャンネルは選択されたポートまたはポートからデータを操作するため、カッ トスルーロジックを必要とする。カットスルーロジックは18ポート、８送信と８ 受信チャンネルのそれぞれ役割をするように模写されたSN07/587,237で説明され たものと類似している。 ルート拒絶ロジック スカウトパケットがパスを捜査する時、これが遮断または使用中チャンネルを 認識し、スカウトパケットパスのノードから各チャンネルを再度調査し、割当ら れていない拒絶パケットと反応しなければならない。エンドトゥエンド肯定応答 （ETE-ack）パケットに使用される同一のバック・トラックパスおよびロジック を使用して、再調査する。 迷路ルート選択および再調査ロジック パスに従うあるノードからのルートはノードIDと共にターゲットノードIDのイ クスクルーシブOR（XOF）を実行することで選択される。これはSN07/587.237に 説明されているように、固定ルーティング用カットスルーポート選択と全く同じ であるが、非割当てられたポートはルーティングロジックにより選択される。割 り当てられたパスからのポート拒絶は、対応するカットスルーセルを無効とし、 次に選択されたポートを試すことになる。効果的なポート選択が残っていない場 合、拒絶メッセージはパスの以前のノードまたは送信チャンネルに逆に通過する 。ターゲットノードに連続的に到着するスカウトは、次に使用可能な受信チャン ネルで操作された後、path#ackメッセージとしてパスを再度調査する。送信チャ ン ネルがpath#ackメッセージを受信した場合、これは選択されたパスに従い、要請 されたメッセージを転送して、開始することができる。全ての潜在的なパスが拒 絶された場合、CPU 動作は阻止され、時間任意待機と再調査はソフトウェアによ って呼び出される。 図８はメッセージ待機時間対ネットワーク転送データのパーセントのグラフで ある。適応性迷路ルーターは実線で表示し、固定性ワーム・ホールルーターは点 線で示した。３個のメッセージミックス；スモール（16パケット）、ミディアム （128パケット）、ラージ（1024パケット）が表示されている。垂直軸は第１パ ケットを伝達するためのパケット時間を表す、メッセージ待機時間である。水平 軸は転送データのネットワークのパーセント、即ちネットワーク帯域幅転送デー タのパーセントである。表１で示されたメッセージミックスは図８のグラフでは 、双ルーティングタイプとしてプロットされている。 図８のグラフに図示されているように、迷路ルーターは大部分の状況で固定さ れたワーム・ホールルートを実行する。 メッセージプロトコール 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”：経路が遮断される時まで“忘れっぽい”ワーム ホール（ワームホールデータの後に、各中間ノードから唯一第１最小パスポート を取る）、その次に遮断されたノードからミスルート及び迷路 パケットタイプ 00＝アドレス 01＝データ 10＝bak-trak routing#command（rt#rej、rcv#rej、fwd#rej、rt#ack、ETE#ac k、ETE#nak） 11＝fwd#message#command（EOM、EOT、flush、reset） コマンド stat cmd --- --- xxxxxx 0000 = packet acknowledge xxxxxx 0001 = route ack(path ack) xxxxxx 0010 = route rejected（blocked）（path rejection） xxxxxx 0011 = reserved xxxxx0 0100 = rcv#channel rejected or hydra#route rejected xxxxx1 0100 = parity#err flushed back xxxxxx 0101 = forwarded route rejected ssssss 0110 = ETE ack（ssssss = rcv#code） ssrrrr 0111 = ETE nack（rrrr = error status; ss = rcv code） xxxxxx 1000 = EOM xxxxx0 1001 = E0T - no ETE requested xxxxx1 1001 = EOT - ETE requested xxxxxx 101x = reserved xxxxxx 1100 = reset#CPU xxxxxx 1101 = reset#node xxxxx1 1110 = parity#err flushed forward xxxxxx 1111 = reserved ノードアドレッシング プロセッサーIDおよびターゲットアドレスはシステムで256K可能なノードのう ち、一つのノードを特定する18ビットユニークバリューである。ターゲットノー ドの18ビット物理ノードアドレスは迷路ルートが設定される時の“スカウト”パ ケット（回路調査）の一部としてメッセージ転送の主位に、アドレスパケット内 に含まれる。新しい転送・送信物理ノードアドレス転換、ノードアドレスチェッ キングとport#vector 演算に対するロジックはシステムソフトウェアにより直接 的に行なわれる。 メッセージルーティング メッセージは上記パケットフォーマット部分のルーティングタイプ型テーブル に表示されたとおり、７つの方式中、あるものにルートされる事ができる。プロ グラマーは“Set#path”または“Send”コマンドのオペランドのルーティング型 フィールドを通した方法を選択する。 忘れっぽいワームホールは“固定された”ルーティング設計である。提供され たソースから提供された目的地までのメッセージは正確に一つの選定されたルー ティングパスを取る。一度取られたパスは最下次数アップヒル最小短パス（lowe st-order uphill minimum-length path）である。メッセージデータによる即時 につながれたノードアドレスであるメッセージはターゲットノード側にこの方式 を差し込み、パスが空いて最小でない場合はわからないが、これが接する時、使 用中のポートに遮断されて、使用中のポートが空いた時、続けられる。 本発明による迷路ルーティングは適応性ルーティング設計である。ノードA か らノードＢまでのメッセージに対して、２個のノードの間の全ての最小短パスは 一つのパケットスカウトにより、同時に一括して調べられ（正確には、第１レッ グが非最小であるパスが任意に調査されうる），最下アップヒルパスを開始して 、ターゲットに対する空いたパスが発見される時まで、最下パスの幅の深さ−第 １螺旋系横断路を行なう。ターゲットからスカウトパケットの成功的な到着はパ スを設定する。その次に、path#acknowledgeパケットが逆に送信機で伝達される 時、確保されたパスはメッセージを転送するのに使用される。しかし、空いたパ スが見つからなければ、阻止されたソースノードに発生し、ソフトウェアは適合 する遅延後のパス調査を再度開始するか、代替ルーティング（または第１レッグ パスの、他のセットを使用する）を使うことができる。 迷路ルーティングプロトコール 迷路ルーターでソース（送信機）ノードからターゲットノードまでの転送は、 パスがソースノードの送信チャンネルからターゲットノードの受信チャンネルま で設定されるまで、達成されない。パスは次のように設定される。 送受信ノードで ソースの送信チャンネルは、それぞれ初期に調査されうるルーティングを通し て、送信機のノードの出力ポートを表示して、送信命令を通してソフトウェアに より提供されるsend#port#vector（SPRTVEC）に関係する。これらのポートは最 小短パスを開始することもしないこともできる。従って、この第１ホップは非最 小にルートすることができ、全てのサブシークエントホップは、最小パスのみを ターゲットに取ることができる。言い換えると迷路ルートはノードセットとター ゲットノードの間に最小パスの徹底したサーチを行い、ソースノードまたは所定 の首位中間アクセス可能な、隣接したノードを含めて設定される。 ターゲットノードのノードアドレスを含むスカウトパケットは、可能な空いて いるソースの選択された出力ポートの１番目に送信されるので、潜在的なパスか らターゲットノードに対する次のノードである、隣接したノードに伝達される。 path#rejection packet が対応する入力ポートに順次的に受信されない限り、送 信チャンネルから選択された出力ポートまでのパスは隠され、ペンディング転送 用として確保される。選択された出力ポートがpath#rejection packet を受信し た場合、次のノードを超過する全てのパスが遮断されるために、使用可能な場合 、send#port#vectorからの新しい出力ポートが選択されることができ、スカウト パケットはポートを送信する。多くのsend#port#vector出力ポートが使用不可能 な時、これらが遮断または拒絶されるために、“all#paths#blocked”状態は各 送信チャンネル用ETE キューにプッシュされ、CPU は阻止され、送信チャンネル は待機状態となり、クリアするためにソフトウェアを待つ。しかし、path#ackno wlege packetが受信される場合、これはサーチおよび今開始されたサブシークエ ント転送用として確保されたサーチおよび選択されたパスの残りを初期化するSe nd#DMA#Channelに逆に通過する。 ターゲットノードで 入力ポート中一つにスカウトパケットを受信するノードは、先にスカウトパケ ットからのターゲットノードアドレスを自分のノードIDと比較する。これらが一 致すれば、スカウトパケットはターゲットノードを発見する。受信チャンネルが 空いている場合、スカウトパケットは受信チャンネルに伝えられ、path#acknowl edge packet は逆に全ての方法を、ソース（送信機）、ノードに送信し、スカウ トパスの成功的なレッグを再び試みることになる。受信チャンネルが使用不可能 な時、“rvc#channel#unavailable”コマンドとしてエンコードされたpath#reje ction packet は設定されたパスを通じ、ソースノードに逆に送信され、入力ポ ートは空く。 中間ノードで 受信ノードのノードIDが、ターゲットアドレスと一致しない時、このノードは 中間ノードであり、スカウトパケットをターゲットノードに対する最小短パスに 従い、隣接するノードに伝達するように試みることができる。これらの間のハミ ング距離である、このノードのノードIDに対するターゲットノードアトルスのXO R は出力ポートが最小短に接続されたことをしめし、カットスルーベクトルとし て、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#mas k でAND される。その次に第２の調査は初期の調査に使用していない、隣接する ノードを通してファインディングからルートが形成される。また代替ルートが失 敗した場合、CPU は通常の方法から阻止される。 全てのルーティングが第１ホップの後に最小化するために、代替送信ポートを 通じた非最小パスは正確に最小よりもより大きい２ホップである。ソース及びタ ーゲットノードがｊディメンションから分離した場合、最小パスの長さはｊホッ プであり、代替パスの距離はｊ＋２ホップである。 特に、代替ルートの調査は一番短いターゲットノードに対する転送用として重 要になり得る。例を挙げれば、全ての他の隣接するものを通してルートを調査す ることで、接続する隣に対してただ一つの最小短パスがあり、代替マスクにより 、説明したようにディメンションｎでの任意の最も近い隣のノードに対するｎ唯 一のパスの集合がある。 単位ノード当たり一つのAlternate#Port#Maskがあるが、代替ルーティングは 単位転送ベーシス（SEND命令のパス設定オペランドでのビット）で可能である。 フォールディング フォールディングは最大の大きさではないシステムでメッセージをルートする のに使用可能な出力ポートの数を増加させる。ロウワー８出力ポートでnearest# neighborノードの対応する入力ポートまでの任意の接続は逆順序に同一のneares t#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およびse nd#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#rd yビットは送信チャンネルに対応して、Send#rdyレジスターの各ビットに１を記 録することでクリアされうる（送信チャンネル状態レジスターを参照）。 遮断されたり中止された送信転送は送信チャンネルに対応する、Send#transmi ssion#rdyレジスターの各ビットに１を記録することで、プッシュされる（送信 チャンネル状態レジスターを参照）。 メッセージがプッシュされる時、flush#cmd パケットは割り当てられたパスを横 切って、この後ろのパスをクリアして非割当する。 End-to-Endキュー ETE（End-to-End）キューである各送信チャンネルに対して、ターゲットノー ドの受信チャンネルからのETE 状態またはroute#rejection またはエラー状態は プッシュされる。状態がETE キューにプッシュされる時、ETE インタラプトが発 生する。キューは２エントリーの深さで、書く送信チャンネル中一つのプロセッ サーレジスターは両エントリーを含む、プログラマーはRDPR命令を通じて、サイ ド効果なく、ETE キューを判読することができる。その後、プログラマーはWRPR 命令（いっしょに判読されても、キュー内の各エントリーは個別に記録される） を通じてゼロをこの正当なビットに記録することで、ETE エントリーをクリアす ることができる。第１エントリーがこの方式からクリア（ポップ）される時、第 ２エントリーは自動的にこの位置にコピーされ、クリアされる。送信チャンネル は新しい転送を開始することができず、ETE キューはみたされる。 送信動作 図１２は送信動作の流れ図である。停止状態から、送信チャンネルはルーティ ング状態(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)の反転バ ージョンと同一に形成される。従って、全て初期に調査されたルートが初期SPOR TVECを使用して失敗した時、反転バージョンは流れがブロック(202)に進行する 時の代替ルート選択トライを提供する。第１非割当て出力ポートは、今、反転さ れた送信ポートベクトル(202)から選択される。ポートが(204)から選択される場 合、流れはブロック(206)に進行する。ポートが（204）から選択されない場合、 流れはブロック(205)に進行する。代替ルーティングは(205)でイネイブルされる が、シークエンスを通じた第１通過(207)が存在しないので、流れはブロック(21 8)に進行する。送信チャンネルは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)で、ポートが選択されない時、入力ポートはこの入力ポート(33 5)と対となっている、出力ポートを通じてroute#rejectコマンドを送信し、新し いアドレスパケット(336)を待つ。 ポートが（31）から選択される場合、アドレスパケットは選択された出力ポー ト(312)を通じて次のノードにフォワードされ、ポートは割り当てられる。この ノードを通じて転送パスは、この瞬間に設定され、入力ポートは到来ルートコマ ンド(413)により、供給されることができるルーティング状態を待つ。ルートコ マンド(316)はルートが拒絶されたり、ルートが準備されたことを表示する事が できる。拒絶された場合、流れはブロック(318)に進行する。準備された場合、 流れはブロック(330)に進行する。 ブロック(318)で、受信チャンネルはポートベクトルで対応するビットをクリ アし、ポート選択をクリアして、ブロック(312)で割り当てられた出力ポートを 非割当てする。入力ポートは次の非割当て出力ポートをルーティングロジックを 通して、ポートベクトル(308)で選択し；流れは上述したのと同じく流れる。 決定ブロック(308)で、ノードIDがアドレスパケットないのアドレスと同一で あったり、このポートが端子である場合、このノードはターゲットノードであり 、流れはブロック(322)に進む。 ブロック（322）で、ポートベクトル(PortVec)は発生し、第１準備受信チャン ネル（324）を選択するのに使われる。チャンネルが(326)で選択された場合、入 力ポートはメッセージ(328)を受信するために、受信チャンネルを割り当てる。 入力ポートはこの入力ポート(330)と対となる出力ポートを通じてルート準備(ro ute#rdy)コマンドを送信し、(322)に到着するため、メッセージデータを待つ。 ブロック(326)で、チャンネルが選択されない場合、入力ポートはこの入力ポ ート(335)と対となった出力ポートを通じて、route#rejectコマンドを転送し、 新しいアドレスパケット(336)を待つ。 エンドトゥエンドリポーティング 図14はエンドトゥエンド肯定応答を図示した。ソースノード(350)で、送信チ ャンネルは出力ポート(352)からのメッセージパケットを入力ポート(354)からメ ッセージを受信する中間ノード(355)に送信する。メッセージは出力ポート(356) からの中間ノード(354)により、送信される。メッセージはターゲットノード(35 8)がメッセージパケットを受信するまで、ノードからノードまで移動する。受信 チャンネルは(362)で割当てられ、ETE#ack メッセージはパス［ポート(361、353 及び351)］の各入力ポートと対となる出力ポートを使用することで、同一パス から逆に送信される。ETE#ack がソースノードから受信され、状態がETE#ack に 復帰する時まで、メッセージパスは維持される。各送信チャンネルで、エンドト ゥエンド(ETE)キューが存在し、ETE 状態はプッシュされる。エンドトゥエンド 状態がETE キューにプッシュされる時、Send#rdy及びETE インタラプトはこの状 態に従って発生する。 図15は遮断されたリンクがない迷路ルートタイミング図である。 図16は遮断されたリンクがあり、バックトラッキングが呼び足した迷路ルート タイミング図である。 発明の詳細な説明の項ではなかった具体的な実施状態、また実施例はどこまでも 本発明の技術内容を明白にするもので、それと同じ具体例でのみ限定され、狭義 に解釈されなければならず、本発明の精神と次に記載する特許請求事項の範囲内 でいくつか変更して実施することができる。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，Ｍ Ｃ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ， ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＭＷ，ＳＤ，ＳＺ，ＵＧ)， ＡＭ，ＡＴ，ＡＵ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，Ｃ Ｈ，ＣＮ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ ，ＧＥ，ＨＵ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ， ＬＫ，ＬＲ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＮ，Ｍ Ｗ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ ，ＳＥ，ＳＩ，ＳＫ，ＴＪ，ＴＴ，ＵＡ，ＵＳ，ＵＺ， ＶＮ

Claims (1)

1. 【特許請求の範囲】 １．唯一のプロセッサー識別番号（ID）がそれぞれ割り当てられたプロセッサー を含む相互に接続されたノードのネットワークで、上記ネットワークのノードを 通じて通信パスを設定する装置において、 多数の入力ポート； 多数の出力ポート； 上記ノードの上記入力ノードのうちの一つで、上記ノードのうち他のノードの 出力ポートから転送された、一番新しいメッセージに関連したアドレスパケット を受信する制御手段 上記の一つの入力ポートおよび上記出力ポートに接続したルーター 上記プロセッサー識別番号（ID）を記録するレジスター手段 パケット内のターゲットノードアドレスを上記レジスター手段に貯蔵した上記 ノードの上記プロセッサーIDと比較するための制御手段、および上記レジスター 手段に接続した比較手段を含み； 上記比較手段は上記IDがターゲットノードアドレスと同一であるものが提供さ れた第１条件およびその代りの上記IDが上記ターゲットノードアドレスと同一で ないものを提供する第２条件を形成する手段を含み； 上記ルーターに接続した多数の受信チャンネル； 上記ノードアドレスが上記ターゲットノードアドレスと同一な上記第１条件の 出現に従い、上記ノードの上記受信チャンネルは上記の一つの入力ノードに割り 当てられるため、上記比較手段および上記受信チャンネルに接続した割当て手段 ；および 上記第１条件の出現に従い、上記入力ポートと対をなす、上記出力ポートを通 じたroute#ready コマンドを送信するために、上記比較手段および上記制御手段 に接続した第１手段を含むものを特徴とするパス設定装置。 ２．第１項において ポートベクトル； 上記ノードアドレスが上記ターゲットノードアドレスと同一でない場合、上記 第２条件の出現に伴い、上記ポートベクトルから第１出力ポートを選択するた め、上記比較手段および上記ルートに接続された第２手段；および 上記アドレスパケットを上記選択された第１非割当て出力ポートを通じ、次の ノードにフォワードするため、上記第２手段および上記入力ポートに接続された 第３手段を含む事を特徴とするパス設定装置。 ３．第１項において 上記第ノードの第３非割当てノードに接続した第１非割当て出力ポートを選択 する手段；および 上記アドレスパケットを上記選択された第１出力ポートを通じた上記第３非割 当てノードにフォワードする手段を含む事を特徴とするパス設定装置。 ４．第２項において 第３ノードに接続された第１非割当て出力ポートを選択する手段；および 上記アドレスパケットを上記選択された第１出力ポートを通じ、上記第３ノー ドにフォワードする手段を含む事を特徴とするパス設定装置。 ５．唯一のプロセッサー識別番号（ID）がそれぞれ割り当てられたプロセッサー 、多数の入力ポートおよび多数の出力ポートをそれぞれ含み、上記入力ポート中 、一つの入力ポートは上記出力ポート中、対応する出力ポートと対となる、相互 接続ノードのネットワークで、上記ネットワークのノードを通じて、通信パスを 設定する方法において、 Ａ．上記ノード中、第１ノードの入力ポートからターゲットノードアドレスを 持つ第１アドレスパケットを受信する段階へ、上記第１アドレスパケットを上記 ノード中、第２ノードの出力ポートから送信された、一番新しいメッセージに関 連して； Ｂ．上記第１ノードで、上記第１アドレスパケット内の上記ターゲットノード アドレスを上記第１ノードのプロセッサーIDと比較する段階； Ｃ．上記プロセッサーIDが上記ターゲットノードアドレスと同一な第１条件の 出力に従って、メッセージを受信するため、上記第１ノードの上記受信チャンネ ルを割り当てる段階；および Ｄ．route#rdy コマンドを上記第１ノードから上記入力ポートと対をなす、上 記出力ポートを通し、上記第２ノードに送信する段階を含む事を特徴とする方 法。 ６．第５項において、 Ｅ．上記第１ノードの第３ノードに接続された第１出力ポートを選択する段階 ；および Ｆ．上記アドレスパケットを上記選択された第１出力ポートを通して上記第３ ノードにフォワードする段階を含む事を特徴とする方法。 ７．第６項において Ｇ．ルートコマンドを受信する段階；および Ｈ．上記入力ポートと対となる上記出力ポートを通した、route#rejectコマン ドを送信する段階を含む事を特徴とする方法。 ８．迷路ルーターメカニズム； 固定されたルーターメカニズム； 上記迷路ルートメカニズム、または上記固定されたルートメカニズム中の一つ を選択する為、上記迷路ルートメカニズムおよび上記固定されたルートメカニズ ムに接続する全ての選択手段；および ファインディングをイネイブルする制御情報を含むノードアドレスパケットを 受信し、ソースノードからターゲットノードに対するルートを設定するため、上 記迷路ルーターメカニズム、および上記固定されたルーターメカニズムに接続す る入力ポートを含む事を特徴とする装置。 ９．メモリーアドレスバス； メモリーデータバス； 上記メモリーアドレスバスおよび上記メモリーデータバスに接続されたダイレ クトメモリーアクセスバッファー及びロジックブロック； 多数の受信チャンネル； 多数の送信チャンネル； 上記送信チャンネルおよび上記受信チャンネルに接続される多数のルーティン グレジスター； 上記多数の受信チャンネルおよび上記多数の送信チャンネルに接続されたカッ トスルーアービタ； 上記多数の送信チャンネルおよび上記ルーティングレジスターに接続するルー ティングアービタ； 中央処理装置で上記受信チャンネル、上記送信チャンネルおよび上記ルーティ ングレジスター及びロジックまで接続するプロセッサーバス； 多数の入力ポート； 多数の入力ピン； 上記多数の入力ポートは上記ルーティングアービタおよび上記入力ピンに接続 され； 多数の出力ポート；および 多数の出力ピンを含んで、 上記多数の出力ポートは上記カットスルーアービタおよび上記出力ピンに接続 され； 上記多数の入力ポート及び上記多数の出力ポートは上記カットスルーアービタ 、上記ルーティングアービタおよび上記送信と受信チャンネルに接続される事を 特徴とする通信装置。 10．第９項において 上記カットスルーアービタまたは上記ルーティングアービタのうち、一つを選 択するために上記カットスルーアービタと上記ルーティングアービタに接続する モード選択手段；および ファインディングをイネイブルする制御情報を含むノードアドレスパケットを 受信し、ソースノードからターゲットノードにルートを設定する手段を含む上記 入力ポート中、一つに入力ポートを含む事を特徴とする通信装置。 11．Ａ．選択された出力ポートを提供するために、送信ポートベクトルから、第 １非割当て出力ポートを選択する段階； Ｂ．上記選択された出力ポートを送信チャンネルに割り当てる段階； Ｃ．上記選択された出力ポートからのアドレスパケットをターゲットポートに 送信する段階； Ｄ．上記送信チャンネルで、上記ターゲットポートから復帰したルーティング 状態を含むルートコマンドを受信する段階に、上記ルート状態は拒絶されたル ートまたは設定されたルート中の一つを言い； Ｅ．上記ルーティング状態が拒絶されたルートである条件で、上記送信ポート ベクトルの、上記選択された出力ポートに対応するビットをクリアする段階； Ｆ．上記送信チャンネルから、上記選択された出力ポートを非割当てする段階 を含む事を特徴とする方法。 12．第11項において、 Ｇ．上記段階Ｅが結果としてゼロに減少した、上記送信ポートベクトルとなる 条件でroute#rej 状態をエンドトゥエンド（ETE）キューにプッシュする段階を 含むことを特徴とする方法。 13．第11項において、上記アドレスパケットはフォワードビットを含み、 Ｇ．ルートが設定された条件でroute#ready 状態を設定する段階； Ｈ．上記フォワードビットが上記アドレスパケットに設定された条件で、フォ ワーディング状態を加入する段階；および Ｉ．上記フォワードビットが上記アドレスパケットに設定されない条件でメッ セージ転送状態を加入する段階を含む事を特徴とする方法。 14．Ａ．入力ポートでアドレスパケットを受信する段階で、上記入力ポートはノ ードIDを持つノード部分であり、上記アドレスパケットはアドレスを含んでおり ； Ｂ．上記アドレスパケットで、上記アドレスのイクスクルーシブORを上記ノー ドIDと比較する段階で、上記イクスクルーシブORの結果はポートベクトルであり 、 Ｃ．上記結果がゼロではない条件では、選択された出力ポートを提供するため 、上記ポートベクトルに書かれた第１非割当てされた出力ポートを選択する段階 ； Ｄ．アドレスパケットを上記選択された出力ポートを通して、次のノードにフ ォワードする段階； Ｅ．上記受信チャンネルから入力ポートを通し、ルーティング状態を受信する 段階で、上記ルーティング状態は、到来ルートコマンドにより、供給され、上記 ルートコマンドはルートが拒絶されたり、上記ルートが準備されたものの中の一 つを表示し； Ｆ．ルートが拒絶されたことを上記ルートコマンドが表示する条件で、上記出 力ポートに対応する上記ポートベクトルのビットをクリアする段階；および Ｇ．上記入力ポートから上記出力ポートを非割当てする段階を含む事を特徴と する方法。 15．第14項において、 Ｉ．ルートが準備されたことを上記ルートコマンドが表示する条件で、上記入 力ポートと対となった出力ポートを通し、route#rdy コマンドを送信する段階を 含むことを特徴とする方法。 16．第14項において Ｉ．選択された出力ポートを提供するため、上記ポートベクトルに書かれた、 第１非割当て出力ポートを選択する寿機段階Ｃが結果として、選択されたポート がないこととなる条件では、上記入力ポートと対となる出力ポートを通してrout e#rejectコマンドを送信する段階を含む事を特徴とする方法。 17．第14項において、 Ｉ．上記結果がゼロである条件で、ポートベクトルを形成する段階； Ｊ．ポート選択ベクトルを提供するために、上記ポートベクトルを使用する第 １準備受信チャンネルを選択する段階； Ｋ．選択された出力ポートを提供するため、上記ポート選択ベクトルに詳述さ れた第１非割当て入力ポートを選択する段階； Ｌ．入力ポートが選択された条件で、メッセージを受信する上記第１準備受信 チャンネルを割り当てる段階；および Ｍ．上記入力ポートと対となる出力ポートを通し、route#rdy コマンドを送信 する段階を含む事を特徴とする方法。 18．第11項において、 Ｇ．上記ルーティング状態が拒絶されたルートである条件で、代替送信ポート ベクトルを提供するため、上記送信ポートベクトルを反転する段階；および Ｈ．上記選択された出力ポートを提供するために、上記代替送信ポートベクト ルから第１非割当て出力ポートを選択するため、上記代替送信ポートベクトルを 使用する段階を含む事を特徴とする方法。 19．ノードを通して、メッセージを転送する方法において、 Ａ．フォールドイネイブルレジスターで、フォールドイネイブルベクトルを貯 蔵する段階で、上記フォールドイネイブルベクトルはポートがフォールドされた ポートであるように選択された識別番号ビットで表示し； Ｂ．上記ノードの入力ｐ−とで、アドレスビットを含むメッセージパケットを 受信する段階； Ｃ．上記アドレスビットを入力ポートコマンドレジスターのアドレスフィール ドにシフトする段階； Ｄ．上記アドレスフィールドを結果として差ベクトルとなる、上記ノードの識 別番号アドレスと比較する段階； Ｅ．上記差ベクトルの識別番号差レジスターにロードする段階； Ｆ．フォールディングイネイブルされた条件で、FOLDENラインを決める段階； Ｇ．上記差ベクトルを上記フォールドされたポートに対応する上記識別番号ビ ットに変更する段階； Ｈ．上記識別番号差レジスターの上記内容を入力ポートベクトルレジスターに ローディングする段階； Ｊ．ルートされるメッセージを通して、次の最小パスポートを確認するため、 上記入力ポートベクトルレジスターの内容を使用する段階； Ｊ．中間ノードで、カットスルーベクトルを計算する段階；および Ｋ．カットスルーに対するポート、送信チャンネル、または受信チャンネルを 表示するポートカットベクトルを貯蔵する段階を含む事を特徴とする方法。 20．多数のノード間のメッセージ転送方法において、 Ａ．各ノードで、多数の入力ポートそれぞれを各ノードの関連した出力ポート と対を成す段階； Ｂ．発信ノードから発信ノード送信チャンネルを割り当てる段階； Ｃ．上記発信ノード送信チャンネルにより選択された発信ノード出力ポートか らのメッセージパケットを上記発信ノード出力ポートに接続する第１中間ノード 入力ポートに送信する段階で、上記発信ノード出力ポートは発信ノード入力ポー トと対をなし； Ｄ．上記第１中間ノード入力ポートから上記メッセージを受信する段階で、上 記第１中間ノード入力ポートは第１中間ノード出力ポートと対を成し； Ｅ．第２中間ノード出力ポートを上記第１中間ノード入力ポートに接続する段 階で、上記第２中間ノード出力ポートは第２中間ノード入力ノードと対となり； Ｆ．上記第１中間ノード入力ポートを上記第２中間ノード出力ノードに接続す る段階； Ｇ．ターゲットノード入力ポートから上記第２中間ノード出力ポートに接続す る上記メッセージを受信する段階で、上記ターゲットノード入力ポートは上記第 ２中間ノード入力ポートに接続されるターゲットノード出力ポートと対となり； Ｈ．上記ターゲットノードで、ターゲットノード受信チャンネルを割り当てる 段階； Ｉ．上記ターゲットノード受信チャンネルで、受信状態を含むend-to-end肯定 応答メッセージを構成する段階；および Ｊ．上記end-to-end肯定応答をメッセージ転送が完了される条件で、上記ター ゲットノード入力ポートと対となった上記ターゲット出力ポートに送信する段階 を含む事を特徴とする方法。 21．第20項において、 Ｋ．上記end-to-end肯定応答メッセージの受信で、上記第１中間ノード入力ポ ートから、上記第２中間ノード出力ポートに非接続する段階を含む事を特徴とす る方法。