(57)【要約】【課題】  費用効果の高いスケーラブルなネットワーク装置を提供する。【解決手段】通信装置は、スケジュールドメッセージを通信し、複数個のデバイスに接続する制御スイッチと、アンスケジュールドメッセージを通信し、複数個のデバイスに接続する非制御スイッチとを含む。非制御スイッチは、制御スイッチ内でメッセージをスケジューリングする信号を発生する。【選択図】図１14374.doc
2007532052.tif 000002
【特許請求の範囲】
【請求項１】
複数パケットのメッセージの形式をなすデータをネットワークを経由して出力ポートに通信する方法であって、
アンスケジュールド又はアンマネージド送信により前記出力ポートへの前記データの送信に対する要求を通信する過程と、
前記要求に応えてスケジュールド又マネージド送信により前記出力ポートへデータを配信する過程とを含むことを特徴とする方法。
【請求項２】
前記複数パケットのメッセージを連続した配列で通信する過程を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記複数パケットのメッセージを連続した配列で通信する過程を含むことを特徴とする請求項１に記載の方法。
【請求項４】
通信装置であって、
スケジュールドメッセージの通信及び複数個のデバイスへのインターフェイスが可能な制御スイッチと、
アンスケジュールドメッセージの通信及び複数個のデバイスへのインターフェイスが可能な非制御スイッチとを備え、
前記非制御スイッチは前記制御スイッチ内の前記メッセージをスケジューリングする信号を発生することを特徴とする通信装置。
【請求項５】
前記制御スイッチ及び前記非制御スイッチを含むスイッチに多重接続されるデバイスを更に備えることを特徴とする請求項４に記載の装置。
【請求項６】
前記制御スイッチ及び前記非制御スイッチに連結する複数個の入力及び出力ポートを有するデバイスを更に備え、
前記制御スイッチ及び前記非制御スイッチは前記複数個のポートの内の特定のポートへとメッセージを目標付けすることができることを特徴とする請求項４に記載の装置。
【請求項７】
前記制御スイッチ及び前記非制御スイッチに接続される複数個の入力及び出力ポートを有するデバイスを更に備え、
前記制御スイッチ及び前記非制御スイッチは複数のソースから前記複数個のポートの内の特定のポートへとメッセージを目標付け及び時分割多重化することができることを特徴とする請求項４に記載の装置。
【請求項８】
前記制御スイッチ及び前記非制御スイッチに連結される複数個の入力及び出力ポートを有するデバイスを更に備え、
前記制御スイッチ及び前記非制御スイッチはメッセージを前記特定の目標付けられたポートへジャストインタイムに通信することができることを特徴とする請求項４に記載の装置。
【請求項９】
前記制御スイッチ及び前記非制御スイッチに連結され、メッセージのサービス品質（ＱｏＳ）に関する優先順位を規定するロジックを有するデバイスを更に備えることを特徴とする請求項４に記載の装置。
【請求項１０】
前記制御スイッチ及び前記非制御スイッチに連結される複数個のデバイスを更に備え、
前記複数個のデバイスは、
選択された第１入力ポート及び選択された第２入力ポートを含む複数個の入力ポートを有する要求デバイスと、
前記要求デバイスによって特定され、転送が可能な時に複数個のメッセージパケットを前記第１入力ポートへ送信するよう要求される第１送信デバイスと、
前記要求デバイスによって特定され、転送が可能な時に複数個のメッセージパケットを前記第２入力ポートへ送信するよう要求される第２送信デバイスとを備え、
前記要求デバイスは前記転送が完了するまで前記第１及び前記第２入力ポートを開いた状態に維持することを特徴とする請求項４に記載の装置。
【請求項１１】
前記制御スイッチ及び前記非制御スイッチに連結される複数個のデバイスを更に備え、
前記複数個のデバイスは、
選択された入力ポートを含む複数個の入力ポートを有する要求デバイスと、
前記要求デバイスによって特定され、複数個のメッセージパケットを前記入力ポートへ送信するよう要求される第１送信デバイスと、
前記要求デバイスによって特定され、複数個のメッセージパケットを前記入力ポートへ送信するよう要求される第２送信デバイスとを備え、
前記要求デバイスは前記第１及び前記第２送信デバイスからのメッセージパケットを送信するタイミングを制御してメッセージパケットをインターリーブすることを特徴とする請求項４に記載の装置。
【請求項１２】
前記制御スイッチ及び前記非制御スイッチに連結される複数個のデバイスを更に備え、
前記複数個のデバイスは、
選択された第１入力ポート及び選択された第２入力ポートを含む複数個の入力ポートを有する要求デバイスと、
前記要求デバイスによって特定され、複数個のメッセージパケットを前記第１入力ポートへ送信するよう要求される第１送信デバイスと、
前記要求デバイスによって特定され、複数個のメッセージパケットを前記第２入力ポートへ送信するよう要求される第２送信デバイスと、
前記要求デバイスによって特定される受信デバイスとを備え、
前記要求デバイスは前記第１及び第２送信デバイスによる前記第１及び第２入力ポートそれぞれへの第１及び第２パケットストリームの送信を同期し、前記第１及び第２パケットストリームからのパケットをパケット毎に関数を実行して、関数結果のストリームを前記受信デバイスに送信することを特徴とする請求項４に記載の装置。
【請求項１３】
前記制御スイッチ及び前記非制御スイッチに連結される複数個のデバイスを更に含み、
前記複数個のデバイスは、
要求デバイスと、
複数個の処理デバイスと、
前記要求デバイスによって特定され、複数個のメッセージパケットを前記要求デバイスによって特定される処理デバイスへと送信するよう要求される送信デバイスと、
前記要求デバイスによって特定される受信デバイスとを備え、
前記要求デバイスは前記特定の送信デバイスによって前記特定の処理デバイスそれぞれへの複数個のパケットストリームの送信を同期させ、前記複数個のパケットストリームをパケット毎に関数を実行して、関数結果のストリームを前記受信デバイスへ送信することを特徴とする請求項４に記載の装置。
【請求項１４】
前記制御スイッチ及び前記非制御スイッチに連結される複数個のデバイスを更に含み、
前記複数個のデバイスは、
複数個の入力ポートを有する要求デバイスと、
前記要求デバイスによって特定され、複数個のメッセージパケットを前記複数個の入力ポートの特定のひとつに送信するよう要求される複数個の送信デバイスとを備え、
前記要求デバイスが特定の前記送信デバイスによる特定の前記入力ポートそれぞれへの複数個のパケットストリームの送信を、送信を開始するために利用可能時間を確認するための要求パケットの送信と、前記送信デバイスが受け入れることができる転送時間を確認する前記特定の送信デバイスからの確認の受信と、予定された送信時間を確認する確認パケットの送信とによって同期させることを特徴とする請求項４に記載の装置。
【請求項１５】
前記制御スイッチ及び前記非制御スイッチに連結する複数個のデバイスを更に備え、
前記複数個のデバイスが演算デバイス、データ貯蔵デバイス、演算及び貯蔵を組み合わせたデバイス、接続デバイス、ルータ、ブリッジ、通信ゲートウェイ、インターネットプロトコル（ＩＰ）ポータル、ローカルエリアネットワーク、ワイドエリアネットワーク、他のネットワーク、インターコネクトデバイスからなる群から選ばれることを特徴とする請求項４に記載の装置。
【請求項１６】
前記制御スイッチ及び前記非制御スイッチは、選択された第２デバイスの特定の第２出力ポートから選択された第１デバイスの特定の第１入力ポートにメッセージを同時に流すために互いに協働して動作することを特徴とする請求項４に記載の装置。
【請求項１７】
前記制御スイッチ及び前記非制御スイッチは、全ての要求された通信が完了するまで、複数個のメッセージを特定の入力ポートに連続的に流すために、互いに協働して動作することを特徴とする請求項４に記載の装置。
【請求項１８】
複数のデータ経路を経由するデータ送信を管理する前記制御スイッチ及び前記非制御スイッチに連結するメモリ内処理モジュールを更に備えることを特徴とする請求項４に記載の装置。
【請求項１９】
前記非制御スイッチはフラットレイテンシスイッチであり、前記制御スイッチは階段構造フラットレイテンシスイッチであることを特徴とする請求項４に記載の装置。
【請求項２０】
前記非制御スイッチに連結するデバイスはメッセージパケットを前記非制御スイッチにいずれのメッセージ送信時間にも送ることができ、
前記制御スイッチに連結するデバイスはメッセージを前記制御スイッチに予定された時間に限り挿入することができることを特徴とする請求項４に記載の装置。
【請求項２１】
複数個のデバイスと、
前記複数個のデバイスへとインターフェイスし、スケジュールドメッセージを前記デバイスの選択されたひとつに通信することができる制御スイッチと、
前記複数個のデバイスへとインターフェイスし、アンスケジュールドメッセージを前記デバイスの選択されたひとつに通信することができる非制御スイッチとを備え、
前記非制御スイッチは前記制御スイッチ内の前記メッセージのスケジューリングを行う信号を発生することを特徴とするシステム。
【請求項２２】
前記複数個のデバイスは、演算デバイス、データ貯蔵デバイス、演算及び貯蔵を組み合わせたデバイス、接続デバイス、ルータ、ブリッジ、通信ゲートウェイ、インターネットプロトコル（ＩＰ）ポータル、ローカルエリアネットワーク、ワイドエリアネットワーク、他のネットワーク、インターコネクトデバイスからなる群から選ばれることを特徴とする請求項２１に記載のシステム。
【請求項２３】
前記制御スイッチと前記複数個のデバイスとの間に連結する補助スイッチを更に備えることを特徴とする請求項２１に記載のシステム。
【請求項２４】
前記複数個のデバイスの内のひとつのデバイスから前記非制御スイッチへと連結される少なくとも１本の制御ラインを更に備え、
前記少なくとも１本の制御ラインはメッセージ衝突状態下で前記非制御スイッチにメッセージが入ることを防ぐことができる信号を運ぶことを特徴とする請求項２１に記載のシステム。
【請求項２５】
前記非制御スイッチから前記複数個のデバイスの内のひとつのデバイスに連結される少なくとも１本の制御ラインを更に備え、
前記少なくとも１本の制御ラインは前記デバイスへの情報フローを制御することができる信号を運ぶことを特徴とする請求項２１に記載のシステム。
【請求項２６】
前記複数個のデバイスの内のひとつのデバイスは前記制御スイッチを通過するメッセージトラフィックを、要求パケットを前記非制御スイッチを経由して送ることにより制御することを特徴とする請求項２１に記載のシステム。
【請求項２７】
前記制御スイッチを通過するメッセージトラフィックをスケジューリングすることができる前記制御スイッチに連結されるコンパイラを更に備えることを特徴とする請求項２１に記載のシステム。
【請求項２８】
要求パケットを前記非制御スイッチを経由して送信することによって前記制御スイッチの第１部分を通過するメッセージトラフィックを制御する前記複数個のデバイスの内のひとつのデバイスと、
前記制御スイッチの第２部分を通過するメッセージトラフィックをスケジューリングすることができる前記制御スイッチに連結するコンパイラとを更に備えることを特徴とする請求項２１に記載のシステム。
【請求項２９】
前記補助スイッチは、
少なくとも１個のクロスバースイッチと、
前記少なくとも１個のクロスバースイッチのひとつに連結され、交差点を配設することができる複数個の論理素子と、
前記論理素子と前記クロスバースイッチの間に連結される複数個の遅延先入れ先出し（ＦＩＦＯ）バッファとを更に備え、
前記ＦＩＦＯバッファはメッセージセグメントのクロスバースイッチへのタイミングを同期させることができることを特徴とする請求項２１に記載のシステム。
【請求項３０】
前記補助スイッチは、
少なくとも１個のクロスバースイッチと、
前記少なくとも１個のクロスバースイッチから少なくとも１個のデバイスへの複数本の出力ラインと、
前記少なくとも１個のクロスバースイッチのひとつに連結され、交差点を配置することができる複数個の論理素子と、
前記制御スイッチから対応する前記複数個の論理素子への複数本の入力ラインと、
前記論理素子と前記クロスバースイッチの間に連結される複数個の遅延先入れ先出し（ＦＩＦＯ）バッファとを更に備え、
前記ＦＩＦＯバッファはメッセージセグメントの前記クロスバースイッチへのタイミングを同期させることができ、入力ラインの本数が出力ラインの本数より多いことを特徴とする請求項２１に記載のシステム。
【請求項３１】
前記制御スイッチと前記複数個のデバイスとの間に連結される補助スイッチと、
前記複数個のデバイスと前記補助スイッチとの間にインターフェイスする複数個の制御スイッチとを更に備えることを特徴とする請求項２１に記載のシステム。
【請求項３２】
前記制御スイッチと前記複数個のデバイスとの間に連結される補助スイッチと、
前記複数個のデバイスと前記補助スイッチとの間にインターフェイスする複数個の制御スイッチと、
複数個の入力ポートを有する前記複数個のデバイスの内の要求デバイスと、
前記複数個のデバイスの内の送信デバイスとを更に備え、
前記要求デバイスは、メッセージパケットを受けるために前記複数個の入力ポートの内のひとつの入力ポートを特定し、前記送信デバイスは前記メッセージパケットを運ぶために前記複数個の制御スイッチから前記制御スイッチを特定することを特徴とする請求項２１に記載のシステム。
【請求項３３】
前記複数個のデバイスにインターフェイスする複数個の非制御スイッチを更に備えることを特徴とする請求項２１に記載のシステム。
【請求項３４】
前記複数個のデバイスが、
複数個の入力ポートを有する要求デバイスと、
前記要求デバイスにより特定され、複数個のメッセージパケットを前記要求デバイスに送ることを要求される少なくとも１個の送信デバイスを備え、
前記要求デバイスは前記非制御スイッチを経由して前記少なくとも１個の送信デバイスに要求パケットを送り、前記要求パケットは前記少なくとも１個の送信デバイスから前記要求デバイスへと前記制御スイッチを経由してのデータ転送のスケジューリングを開始することを特徴とする請求項２１に記載のシステム。
【請求項３５】
前記要求デバイス及び前記少なくとも１個の特定された送信デバイスは、前記少なくとも１個の送信デバイスが前記データを送信することができ、かつ前記要求デバイスが前記データを受け取ることができるときに時間間隔を調整し、前記時間間隔は制御スイッチを経由して前記データを送信するために十分なバンド幅を提供することを特徴とする請求項３４に記載のシステム。
【請求項３６】
前記要求デバイスは要求パケットを、送信されるべきデータ及び前記要求デバイスがデータを受け取ることができる時間間隔を確認する前記少なくとも１個の送信デバイスに送ることを特徴とする請求項３４に記載のシステム。
【請求項３７】
前記非制御スイッチが、
前記複数個のデバイスからの複数本の入力ラインに連結する複数個の入力スイッチと、
前記複数個のデバイスへの複数本の出力ラインに連結する複数個の出力スイッチと、
前記複数個の入力スイッチのひとつと前記複数個の出力スイッチのひとつとの間に選択的に連結する複数個の論理素子とを備えることを特徴とする請求項２１に記載のシステム。
【請求項３８】
前記複数個の論理素子の内のひとつの論理素子は、前記非制御スイッチ内の前記論理素子を通過する全てのデータラインの未来の利用可能性を探知し、前記データラインが利用可能かつデータの送信及び受信にデバイスが利用可能である０又はそれ以上の間隔を選択することができ、
前記論理素子は前記選択された間隔に従ってタイミング選択パケットを任意で変更し、
前記論理素子はデータの送信及び受信のために利用可能な前記デバイス間に前記任意に変更されたタイミング選択パケットを通信する、或いは利用可能な時間間隔がない状態では代わりに拒絶パケットを通信することを特徴とする請求項３７に記載のシステム。
【請求項３９】
前記論理素子は利用できる時間間隔がない状態においては代わりのデバイスに前記データを選択的に送信することができることを特徴とする請求項３８に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
インターコネクトネットワーク技術は、スーパーコンピュータ及びグリッドコンピューティングスイッチ、ルータにおける計算及び通信の基本要素である。しかしながら、既存のインターコネクト技術は、技術的にシステムのスケーラビリティにおいて大きく制限されている。
【０００２】
例えば過去１０年のスーパーコンピュータの発展においても、スーパーコンピュータのインターコネクトネットワークのレイテンシは、基礎物理や気候及び環境モデリング、ＤＮＡシークエンシングのパターンマッチングといった分野での計算に必要な強力なデータ転送の要求に見合った費用効果を達成することができていない。
【０００３】
例えば、Ｃｒａｙ  Ｔ３Ｅスーパーコンピュータは、プロセッサは３次元の双方向トーラスによりインターコネクトされる。アーキテクチュアのレイテンシにより、強力なデータ転送を有する演算カーネルにおいても、平均９５％から９８％のプロセッサがデータを待つ間アイドル状態である。更に、アーキテクチュアにおいてコンピュータの約半分のボードはネットワークボードである。その結果、マシンで行う浮動小数点処理は、パーソナルコンピュータで行う浮動小数点処理に対して１００倍コストがかかる。
【０００４】
マイクロプロセッサの計算能力及び並列計算によるコストの両方が増加しているため、並列処理プラットフォームの代替を提供することを目的として高性能ワークステーションのネットワーク化の構想がある。クラスタコンピューティングの費用効果の基本的な解決法として、高バンド幅と低レイテンシを有するスケーラブルインターコネクトネットワークがある。現在、解決法として「Ｍｙｒｉｎｅｔ（商品名）」や「ＱｓＮｅｔ（商品名）」といったものがあり、特定の目的のハードウェアに使用されている。
【０００５】
「Ｍｙｒｉｎｅｔ」や「ＱｓＮｅｔ」を使用する小規模のスイッチングシステムは、高バンド幅及び適度なレイテンシを有するが、コストとレイテンシの観点からスケーラビリティはスーパーコンピュータネットワークに見られる同様の問題に悩まされる。なぜならば両方ともＣｌｏｓネットワークやファットツリー、トーラスのような複数のノード構造に接続される小規模なクロスバー構造に基づくためである。
【０００６】
同様のスケーラビリティの制限は、ＯＣ１９２に対してスピードを上げる場合に最大３２ポートが制限となる現在のインターネットプロトコル（ＩＰ）ルータにも及ぶ。
【０００７】
長年に渡る研究と発展が、多くの工業にわたる次世代のアプリケーションとして増加する要求を満たすスケーラブルなインターコネクトアーキテクチュアに対しての研究に費やされてきた。しかしながら、長年に渡るアーキテクチュアの能力における大きな進化はあったものの、現存するアーキテクチュアは、費用効果における増加する要求を満たすことができていない。
【発明の開示】
【課題を解決するための手段】
【０００８】
多種多様な演算及び情報伝達系において、プロセッサと記憶装置とはネットワークを経由して通信する。参照の特許文献及び同時係属の出願に記載されたインターコネクト構造は、低レイテンシ及び高バンド幅が必要な多数のインターコネクトするデバイスに適用される。実施例のインターコネクトはセルフルーティングと能力を向上させることができる。同時に複数のパケットを特定のネットワークの出力ポートに送信するネットワークの能力もまた役に立つ。
【０００９】
参照文献１，２，３，４，６，７は画期的なインターコネクト構造のトポロジ及びロジック、また様々な使用方法について記載している。これらの構造は参照文献１の「多重レベル最小ロジック（ＭＬＭＬ）」や他の文献で「データボルテックス」として記載されている。参照文献８はルータを含む次世代の通信装置を作り出すためにどのようにデータボルテックスを使用するかについて記載している。複数スレッド複合技術（ＨＴＭＴ）ペタフロップスコンピュータはＭＬＭＬネットワークの光版を使用した。そのアーキテクチュアの中で全てのメッセージパケットは同じ長さを持つ。参照文献５はネットワーク内での並列演算処理及び並列メモリアクセスについて記載している。
【００１０】
インターネットプロトコル（ＩＰ）ルータの仕様は根本的に演算及び記憶域のネットワーク（ＣＡＳＡＮ）の仕様と異なる。ルータの環境では、スイッチに到着したメッセージパケットは出力ポートに目標付けられることから、ネットワークは第一に入力駆動である。入力駆動システムの仕事の１つは同じ出力ポートに目標付けられたメッセージ間の仲裁である。仮に多くのメッセージがシステムの処理量を超えて所定の出力ポートに目標付けられた場合、メッセージのいくつかは破棄される。ルータは優先度の低いメッセージや送信済みの優先度の高いメッセージを破棄することができる。スケーラブルな次世代のルータのための効率の良い仲裁及びネットワークスケジュールの管理は「要求プロセッサ」の使用として参照文献８に記載されている。所定の要求プロセッサは、要求プロセッサにより管理される出力ポートに目標付けられた全てのメッセージ間の仲裁を行う。ＣＡＳＡＮシステムでは、ネットワークは第一に出力駆動であり、所定のネットワークの出力ポートに配置された装置がデータを送るよう要求する。出力駆動ポート装置は処理できる量を超えてデータを要求しないため、データの破棄は避けられる。
【００１１】
実施例となる技術及び構造は、前記の複数のデバイス間をデータの受け渡しを目的としてインターコネクトすることができる。デバイスは、限定するわけではないが以下を含む。（１）ワークステーションのような演算ユニット、（２）スーパーコンピュータ内部のプロセッサ、（３）単一の集積回路上に位置するプロセッサ及びメモリ、（４）ストレージエリアネットワーク内の記憶装置、（５）広域ネットワークやローカルネットワーク及びイーサネットのポータル。技術はさらにインターコネクト構造を経由してのデータの受け渡しの管理にも関する。
【００１２】
上記した特許及び特許出願に開示されたシステムやデバイス及び機能は、スーパーコンピュータやクラスタコンピューティング及びストレージエリアネットワークに使用され得る。本開示は、開示するシステムやデバイス及びその機能を使用した演算やストレージエリアネットワーク（ＣＡＳＡＮ）システムについて記述する。
【００１３】
いくつかの実施形態では、システムはネットワークの出力ポートデバイスから要求された長いメッセージに応答することができ、中断することなく複数のパケット又はレコードを含む長いメッセージを配信することができる。システムの動作は、スケジュールド又はマネージドの出力駆動部分と、アンスケジュールド又はアンマネージドの部分の２つの部分を含む。スケジュールド又はマネージドシステムの動作部分は、出力ポートに設置された要求デバイスへのデータの配信を含む。アンスケジュールド又はアンマネージドの部分は出力ポートにデータを送信する要求を含む。多くのアプリケーションはネットワーク内にアンスケジュールドトラフィックよりも多くのスケジュールドトラフィックを持つ。開示するシステムは、スケジュールド又はアンスケジュールドトラフィックの両方を効率よく扱うために、インターコネクト構造を空間と時間により分割を行っている。
【００１４】
いくつかの実施形態で開示するシステムは、ネットワークからデータを受け取るために設置されたデバイスに複数箇所で接続する。デバイスに目標付けられたデータは、メッセージの再構成を行うことなく、デバイスの選択されたポートに目標付けられる。データはプロセッサにジャストインタイムに（Ｊｕｓｔ  ｉｎ  ｔｉｍｅ）到着する。ジャストインタイム演算モデルは、マルチスレッドマイクロプロセッサアーキテクチュアによって発生する巨大なプロセッサキャッシングやメモリレイテンシの隠蔽の必要をなくす。デバイスの所定のポートへのデータの目標付けにより、メッセージのオペレーションコードを削除又は短縮することができる。例えば、関数Ｆ（ＸＡ，ＸＢ）を実行する目的でソースＡからＸＡを、ソースＢからＸＢを要求するプロセッサはＸＡをポートＰＡに割り振り、ＸＢをポートＰＢに割り振った結果、関数Ｆを実行するための引数の到着は、関数Ｆのアプリケーションのトリガーとなる。データはあるプロセッサのポートに入るようスケジューリングされ、他のプロセッサのポートを出るようにスケジューリングされることができ、その結果円滑で非常に効率のよいデータの受け渡しとなる。ストリーミングの特徴は、線形代数やフーリエ解析、検索、ソート、巨大なデータ移動を含む多数の他の計算タスクにおける計算カーネルを有するアプリケーションに有用である。所定のプロセッサチップが多数のメモリ内処理モジュール（ＰＩＭチップ）を含む場合、異なったデータ経路を経由してシステムの他のモジュールへデータを配送するために異なったデータ経路が形成され得る。ストリームは様々な形態をして来ることができる。例えば、あるアプリケーションではポートＰＡは第１プロセッサからデータを規則正しい時間に受け取り、第２プロセッサから残りの時間に受け取るようにスケジューリングされる。このネットワーク特徴は演算処理をタイムシェアリングすることができる。なぜならば、システムが過負荷になることを防ぐためにデータは受信ポートによってスケジューリングされ、所定のサイクル上のネットワークに入るデータは、未来に決まった周期でネットワークを出るようにスケジューリングされる。
【００１５】
参照の特許及び出願の文献に開示されたネットワークトポロジ及び制御システムの実用性の高い能力は、ソースＳから目的地ＤへのデータストリーミングはＳからＤへの専用経路の構築を行わないことである。実際に他のデータストリームは異なるソースと目的地間で経路を連続的かつ動的に構築と削除を行い、ＳからＤへのデータは経路から経路へと移動する。データネットワークの実例では、ＳからＤへのストリームはネットワークの他のデータから干渉されず、また干渉しない。
【００１６】
開示するシステムはサービス品質（ＱｏＳ）を規定する能力を形成し得る。
【００１７】
様々な実施形態で、開示する発明はスケジュールド又はアンスケジュールドデータの両方を明示した特許や特許出願に記載されたネットワークの変異型であるネットワークを経由して送信する。単純な実施形態では、アンスケジュールドデータ及びスケジュールドデータは分離したネットワークを通過する。ある実施形態では２つのネットワークを含み、第１ネットワークＵは、アンスケジュールドメッセージパケットを運び、第２ネットワークＳはスケジュールドメッセージを運ぶ。提示した参照文献８は、要求及び返信スイッチとして使用されるアンスケジュールドネットワークを開示する。対照的に、データスイッチはスケジュールドネットワークに使用される。アンスケジュールドメッセージネットワークＵは参照文献２に記載された「フラットレイテンシ」もしくは「ダブルダウン」ネットワークである。スケジュールドネットワークＳはデータスイッチとして記載されている型の「階段型」デザインを使用した「フラットレイテンシ又はダブルダウン」ネットワークである。
【００１８】
複数のメッセージがネットワークＵに所定のメッセージパケット挿入時間に挿入され、Ｎ個のメッセージが同じ出力ポートＰに目標付けられ、ネットワークＵから出力ポートＰへのラインがＮ個のデータの数より少ない場合であっても、最大でＮ個のメッセージが１回でネットワークＵから出力ポートＰに送信される。従って、出力ポートＰを１回もしくは数回以上通過した後に、いくつかのメッセージはシリンダ上を回り、出力ポートＰに入る。出力ポートＰの数に一致して、仮に整数Ｐｍａｘ又はそれより少ない個数のメッセージが、所定のメッセージ送信時間に様々な入力ポートから送られるようにネットワークを設計した場合には、メッセージの全ては、適した出力ポートに出るために、１回以上挑戦してシリンダの周りを移動することなくポートＰを出る。Ｐｍａｘ個のメッセージが出力ポートＰから出ることを保証するため、ポートＰはＰｍａｘ個又はそれ以上のネットワークＳへの接続を持つ。
【発明を実施するための最良の形態】
【００１９】
システムは以下のように動作する。アンスケジュールドメッセージネットワークＵに接続したデバイスは、いずれのメッセージ送信時においても自由にメッセージパケットをネットワークＵに送信し、スケジュールドメッセージネットワークＳに接続したデバイスは、予めスケジューリングされた時のみ接続するネットワークＳにメッセージを挿入することができる。ひとつの実施方法は、ネットワークＵとＳの両方を用いた例で以下に示す。
【００２０】
第１実施形態では、デバイスＤＡ及びＤＢはそれぞれ両方ともネットワークＳ及びＵの両方に接続する。デバイスＤＡはパケットＲＰをネットワークＵを経由してデバイスＤＢに送信し、パケットＲＰはデバイスＤＢからの選択されたデータを要求する。データをネットワークＳからデバイスＤＡに運ぶために設計された、ネットワークＳからデバイスＤＡへの複数の接続を有する実施例では、デバイスＤＡはデータを受け取るため選択された入力ポートを指定することができる。要求パケットＲＰもまた送信すべきデータに対する受け入れ時間に関する情報を含む場合がある。デバイスＤＢが要求を遂行することができる場合、送信が所定の期間行われ、データは連続的にデバイスＤＢからデバイスＤＡに送信される。デバイスＤＢが割り当てられた時間内に要求されたデータを送信できない場合は、デバイスは要求を遂行することができない旨と、送信予定を異なる期間に変更すれば可能である旨を含む返答メッセージパケットをデバイスＤＡに送信する。いくつかの場合で、例えば、デバイスＤＢは多数の期間の選択からデータを送信することが可能な場合、デバイスＤＢはデバイスＤＡに返答パケットを送信する。要求は多数のパケットを含むデータセットを指定された時間Ｔまでに送信することである場合がある。仮にそうであるならば、データは要求が完全に遂行されるまで連続したストリーム及び連続した配列で到着する。デバイスＤＢのロジックは、ＱｏＳを利用するシステムのサービス品質（ＱｏＳ）を強化することができる。ＱｏＳは参照文献８に開示される。例えば、デバイスＤｓからトップスイッチに多数のラインが接続されている場合、１もしくはそれ以上のラインが高ＱｏＳメッセージのために予約される。ＱｏＳを実行するシステムの能力は、多くのネットワークアプリケーションにおいて非常に約に立つ。
【００２１】
第２実施形態では、３個のデバイスＤＡ，ＤＢ，ＤＣのそれぞれをネットワークＳ及びＵの両方に接続する。転送が可能な時、デバイスＤＡはデバイスＤＢにパケットＰ０，Ｐ１，Ｐ２，．．．，ＰｋをデバイスＤＡの入力ポートＰＴ０に送信するよう要求し、更にデバイスＤＡはデバイスＤｃにパケットＱ０，Ｑ１，Ｑ２，．．．，ＱｋをデバイスＤＡの入力ポートＰＴ１に送信するよう要求することができる。デバイスＤＡは、最終パケットのトークン又は他の手法や方法による１以上のカウンタの使用により示された完了をもって転送が完了するまで、ポートＰＴ０及びＰＴ１を開いた状態に維持する。デバイスＤＢ及びＤＣのそれぞれは可能であれば転送を開始し、パケットを輸送挿入期間中、Ｋ個の連続するセグメントを連続的な配列として送信する。
【００２２】
より複雑な第３実施形態では、３個のデバイスＤＡ，ＤＢ，ＤＣがネットワークＳ及びＵに第２実施形態で記載したものと同様の方法で接続している。ある時間ＴにデバイスＤＡはデバイスＤＢにパケットＰ０，Ｐ１，Ｐ２，．．．Ｐｋを時間Ｔ＋１００＋２・０，Ｔ＋１００＋２・１，Ｔ＋１００＋２・２，．．．Ｔ＋１００＋２・（Ｋ−１）にデバイスＤＡの入力ポートＰＴ０に送信するよう要求する。デバイスＤＡはまたデバイスＤＣにパケットＱ０，Ｑ１，Ｑ２，．．．，Ｑｋを時間Ｔ＋（１００＋２・０＋１），Ｔ＋（１００＋２・１＋１），Ｔ＋（１００＋２・２＋１），．．．Ｔ＋（１００＋２・Ｋ＋１）にデバイスＤＡの入力ポートＰＴ０に送信するよう要求する。従って、デバイスＤＡは２つの交互配列を受け取る。スケジューリングされたイベントが発生するまでデバイスＤＡ，ＤＢ，ＤＣ間でアンスケジュールドメッセージを送信が可能である。配列の到着は、デバイスＤＡがスケジューリングした関数Ｆ（Ｐ，Ｑ）の他のデバイスＤＸへの送信と一致し、関数の演算中に関数Ｆ（Ｐ，Ｑ）の送信が発生する。従ってデバイスＤＡはメモリを使用せずに、貯蔵されない計算関数を通してのデータストリームにより、データを受け取り、計算し、送信する。
【００２３】
第２及び第３実施形態を組み合わせた第４実施形態は、これまでと同様に３個のデバイスＤＡ，ＤＢ，ＤＣがネットワークＳ及びＵに接続する。ある時間ＴにデバイスＤＡはデバイスＤＢにパケットＰ０，Ｐ１，Ｐ２，．．．Ｐｋを時間Ｔ＋１００，Ｔ＋１００＋１，Ｔ＋１００＋２，．．．Ｔ＋１００＋（Ｋ−１）にデバイスＤＡの入力ポートＰＴ０に送信するよう要求する。デバイスＤＡはまたデバイスＤＣにパケットＱ０，Ｑ１，Ｑ２，．．．，Ｑｋを時間Ｔ＋１００，Ｔ＋１００＋１，Ｔ＋１００＋２，．．．Ｔ＋１００＋（Ｋ−１）にデバイスＤＡの入力ポートＰＴ１に送信するよう要求する。デバイスＤＡは指定した２組のパケットを同時かつ同期して、異なる入力ポートに到着するよう要求する。第３実施形態で言及したように、転送のスケジューリングは最初のパケットの到着時間（Ｔ＋１００）が再び要求されるまでの間、複数のデバイスＤＡ，ＤＢ，ＤＣ間のアンスケジュールドメッセージの通信を通してのみ可能である。デバイスＤＡは、関数Ｆ（Ｐ，Ｑ）を形成するパケットＰ，Ｑを要求し、結果をデバイスＤＸに送る。デバイスＤＡはデバイスＤＡの所定の入力ポートに到着するパケットにより関数Ｆ（Ｐ，Ｑ）を実行し、結果をデバイスＤＸに送る。
【００２４】
関数Ｆ（Ｐ，Ｑ）がパケットを受け取るために経過する時間よりも短い時間で実施される場合には、配列ＰがデバイスＤＡの入力ポートＰＴ０に時間Ｔ＋１００からＴ＋１００＋（Ｋ−１）に連続的に配送され、配列ＱはＰがポートＰＴ０の配送されるのと同時に入力ポートＰＴ１に配送される。同じ期間に、デバイスＤＡは配列Ｆ（Ｐ，Ｑ）を関数の計算結果としてＤＸに配送する。
【００２５】
予め決められたデバイスの予め割り当てられたポートであるデバイスＤｘに同時に到着するようＮ個のストリームをスケジューリングする場合には、よく使用されるひとつの手法は、スケジューリングを要求するデバイスがＮ個の異なるプロセッサに要求パケットを送信する方法である。要求パケットは転送を開始できる時間の情報を含む。要求を受けたそれぞれのプロセッサは、要求パケットに指定された時間を含むプロセッサの利用可能時間を記載したパケットを返信する。利用可能時間は［Ｋ，∞］の形式の半直線の組を含む。半直線で表される共通集合は全ての送信ノードと同じく受信ノードが受けることができる最小の数を有する。スケジューリングデバイスは他に転送が始まるときを示した確認パケットを送る。確認パケットを受け取るまで、元の要求パケットを受け取ったデバイスは、返信パケットに示された時間にデータを送るためにラインを空に維持する。確認パケットを受け取った時、送信デバイスは利用可能時間を含む自己のテーブルを変更する。全てのプロセスは、要求デバイスのＮ個の要求パケットを送信、デバイスからのＮ個の返信パケットの返信、そして最後の要求デバイスからのＮ個の確認パケットを送信である。
【００２６】
文字Ｊで表される例の場合で、仮にある特定数のパケットの受信時間が関数Ｆ（Ｐ，Ｑ）を実行するために使用される場合、Ｊ個のプロセッサそれぞれのデータ受信時間が演算を実行するための時間に一致してタスクが実行されるようにＪ個のプロセッサは割り当てられる。Ｊ個のプロセッサのそれぞれは結果をＤＸに送信し、デバイスＤＸは予め割り当てられた入力ポートを通して一連の流れの結果を受け取る。
【００２７】
実施例はデータ処理システムの能力のいくつかについて示している。当業者にとって他に多くの実施例があることは明らかである。
【００２８】
図１Ａに示すように、システム１００は、ネットワークＵ１１０及びネットワークＳ１２０を含む複数個のネットワークを有し、ネットワークＳ及びＵは複数個のデバイス１３０に接続する。デバイス１３０は、演算が可能なデバイス、データの貯蔵が可能なデバイス、演算とデータの貯蔵が可能なデバイス、インターネットプロトコルポータルに制限されず、ローカル及び広域ネットワークや他のネットワークを含む他のシステムとのゲートウェイを形成するデバイスを含み得る。通常、デバイス１３０はデータの送受信を行うことが可能な全ての型のデバイスを含み得る。
【００２９】
＜＜アンスケジュールド又は非制御スイッチ＞＞
アンスケジュールド又は非制御ネットワークスイッチＵはデータをデバイス１３０からライン１１２を経由して受け取る。スイッチＵはデータをデバイスにライン１１４を経由して送る。スケジュールド又は制御ネットワークスイッチＳ１２０はデータをデバイスからライン１２２を経由して受け取り、外部デバイスへ補助スイッチＡＳ１４０を経由して送る。データはネットワークＳ１２０から補助スイッチ１４０にライン１２４を経由し送られ、データは補助スイッチ１４０からデバイスＤへライン１２６を経由して送られる。
【００３０】
図１Ｂと図２に示すように、ブロック図は、参照文献２に記載された「フラットレイテンシスイッチ」型のノードＮＡ２０２の配列の内部接続を示している。ネットワーク１１０は行と列の形に配置されたノードアレイ２０２を含む。ネットワーク１１０はアンスケジュールドネットワークでの使用によく適合しており、実施形態で使用される。ネットワーク１１０はセルフルーティング機能を有し、複数のメッセージを同時に選択された入力ポートに送ることができる。更に、ネットワーク１１０は高バンド幅と低レイテンシを有し、単一集積回路上に設置することができる。データはネットワーク１１０の外部のデバイスＤ１３０からライン１１２を通してスイッチの単一の列に送られ、スイッチから目標付けられたデバイスにライン１１４を経由して出る。ライン１１４はネットワークＵ１１０からデバイス１３０へと複数の列を経由してデータを持ち出せるよう設置される。データ搬送ラインに加えて、制御ライン１１８はメッセージがネットワークＵ１１０の最上位のノードに入ることを防ぐために使用される。制御ライン１１８は、ネットワークＵ１１０構造の外部からインターコネクト構造に入るメッセージパケットと同時間及び同ノードに入るインターコネクト最上位のメッセージパケットが存在する場合に使用される。インターコネクト構造が一つの集積回路チップに実装された場合には、最上位のノードからネットワークＵ１１０にメッセージを送るデバイス１３０に制御信号１１８が送られる。
【００３１】
実施形態では、制御信号を外部デバイスに運ぶことができるＮピンを使用する。ここで１ピンは１デバイスに相当する。他の実施形態では、制御信号を運ぶためにより多くの又は少ないピンが使用される。
【００３２】
他の実施形態では、図示しないが、Ｎより長く、１ピン又は異なるロジックが使用される場合には２ピンの先入れ先出し方法（ＦＩＦＯ）が制御信号をデバイスＤ０，Ｄ１，．．．，ＤＮ−１に送るために使用される。時間Ｔ０の時にピンは制御信号をデバイスＤ０に運ぶ。時間Ｔ０＋１のときにピンは制御信号をデバイスＤ１に運び、その他、時間Ｔ０＋ｋの時にはピンは制御信号をデバイスＤＮ＋ｋに運ぶ。制御信号は、図示しないが、信号を適したデバイスに搬送する制御信号分配装置に送られる。
【００３３】
第３実施形態では、図示しないが、ライン１１２からネットワークＵ１１０へデータを送るピンが、制御信号をネットワークＵから外部デバイスへと送る。第３実施形態では、、ピンに反対方向にデータを運ぶことを許容するために時間間隔はひとつのメッセージの最終ビットと次のメッセージの最初のビットを分割するようにタイミングを調整する。第２及び第３実施形態によってピンの数は減少する。
【００３４】
ネットワークＵから外部デバイスへの制御信号に加えて、制御信号は外部デバイスからネットワークＵへと送られる。制御信号の目的は、外部デバイスの入力バッファが溢れないように保証することである。バッファがネットワークＵから追加のパケットを受け入れるための容量が十分でない場合に外部デバイス１３０はその状態を示すために信号をライン１１８を経由してネットワークＵに送る。単純な実施形態では、デバイスＤの入力バッファが、ネットワークＵ１１０からデバイスＤ１３０への全てのライン１１４を経由して単一サイクルで受け取る全てのデータを保持するために十分な容量がない時、例えば単一ビットからなる信号が送信される。仮に停止信号が送られた場合に信号は、ライン１１４を通してデータを送信する全てのノードに広がる。ネットワークＵ外の制御信号に対するピンの数を減らすための２つの手法は、ネットワークＵ内への信号に対するピンの数を減らすために使用されている。
【００３５】
＜＜制御スイッチ＞＞
図３に示すブロック図は、制御又はスケジュールドスイッチ又はネットワークＳ１２０を示す。スイッチ１２０は参照文献２に記載された「フラットレイテンシスイッチ」の部分集合であるスイッチ中のインタコネクトノードアレイ２０２を含む。スイッチは全てではないがいくつかは「フラットレイテンシスイッチ」を含む。脱落したノードアレイは、過剰である。なぜならばスイッチへの流れはスケジューリングされているため、モンテカルロシミュレーションによるとメッセージは仮に構造内に残っていても脱落したノードには入らない。このスイッチはスイッチＳ１２０の中心として用いられ、１個もしくはそれ以上のスイッチを用いた実施形態に使用される。
【００３６】
図１Ａ及び図１Ｂに示すように、データはデバイス１３０からスイッチ１２０へライン１２２を経由して単一の列に受け渡され、スイッチ１２０の複数の列からライン１２４を経由して出て、補助スイッチＡＳ１４０に入る。図１Ｃに示すように、補助スイッチ１４０は複数のクロスバースイッチを含む。制御スイッチ１２０からデータを受け取る１個のクロスバースイッチＸＳ１５０を図３に示す。データは補助スイッチ１５０から外部のデバイス１３０へとライン１２６を経由して受け渡される。メッセージはスイッチ１２０の最上位層に折り返さないため、スイッチＳ１２０は制御信号又はスイッチ１２０に入る外部のメッセージとの衝突を警告する信号を用いることなく動作する。同じ理由で、スケジュールドスイッチＳ１２０は、先入れ先出し（ＦＩＦＯ）方式や他のバッファを用いることなく動作する。
【００３７】
スイッチＳ１２０を通過するトラフィックの制御方法の一つは、スイッチＵ１１０を経由して要求パケットを送ることであり、ストレージアレイネットワーク（ＳＡＮ）アプリケーションを含む多くのアプリケーションで効果的な方法とされている。クラスタ演算等の並列演算を含む他のアプリケーションでは、スイッチＳを通過するデータは演算を管理するコンパイラによってスケジューリングされる。システムは柔軟性を持ち、スケジュールドネットワークの一部をネットワークＵ及びコンパイラによって制御することができる。
【００３８】
＜＜補助外部スイッチ＞＞
図４に示すブロック図は、ネットワークＳの外部出力行から補助クロスバースイッチＸＳ１５０を経由しての外部デバイス１３０へのインターコネクトを示している。スイッチＳの外部出力行はノード４２２及び接続４２０を含み、また図５Ａに示すように補助クロスバースイッチＸＳ１５０は複数のより小さなスイッチＸＳ１５０を含む。スイッチＳから目標のデバイスまでの出力接続は、スイッチＵから目標の外部デバイスまでの出力接続よりも複雑である。
【００３９】
図４にクロスバースイッチＸＳの基本的な機能を示す。スイッチは通信ライン４２０上の複数のノード４２２からの６本の入力ライン１２４と、外部デバイスＤ１３０の４個の入力バッファＢ０，Ｂ１，Ｂ２，Ｂ３を有する６ｘ４スイッチとして記載されている。例えばデータ転送いった送信サイクル中で６本の入力ラインの内、４本しか有効でない。それぞれの要求プロセッサが、いずれのサイクルにおいても同じ貯蔵場所に向かう２つのパケットは出力行に到着できないことを保証するため、スイッチＸＳは単純なクロスバースイッチである。それぞれのメッセージパケットは外部デバイス１３０の分離した貯蔵場所に向けられるため、スイッチは衝突を考慮せずに設置することができる。ロジックエレメント４１４は通信路を決定する交差点に設置される。それぞれのエレメントはクロスバースイッチの一つの列を制御するため、ロジックエレメント間の通信は行われない。遅延ＦＩＦＯ４１０はスイッチ内へのセグメントの入場を同期させるために使用される。あるノードから次のノードに移動するためにセグメントのヘッダビットは２個のクロックティックを消費するため、２つのノードは最大の場合１１ノード分離れるため、最も左のノードで２２ティックの遅延ＦＩＦＯが使用される。他のＦＩＦＯの値はスイッチに入る入力ライン上の最終ノードからのノードの距離を反映する。実施形態では、スイッチＵ，Ｓと補助スイッチは、出力列であるレベル０の出力ポートの大きさ及び位置が固定されている。大きさ及び位置の情報は説明のためだけに使用しており、他の大きさのシステムへ大きさにおいて適応できる概念を開示している。
【００４０】
図４に示すように、ノードの底の一列がデバイスＤ１３０に接続される。他の例では、一つの列が複数のデバイスに接続される。また他の例では、複数の列が一つのデバイスに接続される。従って、このシステムは様々な大きさや型のデバイスに対応する。より効率の良い設計は通常、補助スイッチから外部デバイスへのラインよりもネットワークの最下位層のラインから補助スイッチにより多くのラインを含む。設計はネットワークからデータを様々な効率の良い方法で取り除く。その結果メッセージの折り返しは発生しない。
【００４１】
多くの制御アルゴリズムが実施形態のアーキテクチュアに利用可能である。アルゴリズムはハードウェア、ソフトウェア、ハードウェア及びソフトウェアの組み合わせにおいて実施され得る。
【００４２】
＜＜低ピンカウントを目的とした複数スイッチの使用＞＞
図１Ａ，３，４のブロック図は、Ｎ個の外部デバイスＤ１３０と接続するＭＬＭＬネットワーク１２０を示す。図１Ａに示すように、システム１００はデバイスＤからネットワークへと入る１本のラインとネットワークからデバイスＤへと入る４本のラインを有する。多重レベル最小ロジック（ＭＬＭＬ）ネットワークのような同じ集積回路チップの上に補助スイッチＡＳ１４０を有する実施形態では、ネットワークＳ１２０のネットワークチップはＮ個の入力ラインと４Ｎ個の出力ラインを有する。
【００４３】
図５Ａに示すように、ネットワークＳ１４０は４つの集積回路に分けられたそれぞれ独立したネットワークＳ０＊，Ｓ１＊，Ｓ２＊，Ｓ３＊５２０を含む形態である。１個の補助スイッチＡＳ１４０は４つのネットワーク５２０に接続する。図５ＡにＮ個の外部デバイスＤｎを示す。デバイスＤＫに接続する入力と出力を詳細に示す。デバイスＤＫはネットワークＳ０＊，Ｓ１＊，Ｓ２＊，Ｓ３＊５２０のそれぞれにデータを送信するため、４本の出力ラインを有する。実施形態のネットワークチップそれぞれは、デバイスＤＫと接続した補助クロスバースイッチＸＳＫにデータを送るために３本のデータラインを有する。スイッチＸＳＫは１２本の入力ライン１２４及び８本の出力ライン１２６を有する。実施形態で使用されるラインの数は、記載目的のためだけに使用している。実際のデバイスにおいて使用されるラインの数は、任意である。４個のＳ＊ネットワークそれぞれは、Ｎ個の入力ポート及び３Ｎ個の出力ポートを有する。従って、それぞれのネットワークＳ＊は図１から図４に記載したネットワークＳ１４０の出力ポート４Ｎ個に対して３Ｎ個と若干少ない。Ｓ＊ネットワークはＮ＋１階層のダブルダウンＭＬＭＬネットワークである。Ｓ＊ネットワークに接続するデバイスＤ１３０は、ネットワークＳに接続するデバイスと比較して２倍の入力ポートと４倍の出力ポートとを有する。従って、この形態は外部デバイスの入力／出力（Ｉ／Ｏ）容量が増加し、集積回路チップのネットワークのＩ／Ｏが減少している。
【００４４】
通信をスケジューリングするデバイスＤの内、特に受信デバイスは、デバイスＤの入力バッファの利用に関する情報のアクセス権を有する。図５Ａに示すように、受信デバイスＤはスイッチＳ＊からデバイスＤに接続するクロスバースイッチＸＳへのライン１２４の未来の状態に関する情報も利用することができる。要求パケットは入力バッファの利用と状態に関する情報を含む。送信デバイスは、Ｓ＊スイッチの使用について示す返答パケットを返す。データ受信デバイスは、ライン１２４の利用可能性について示す要求パケットを未来に使用のために情報を保持する。従って、要求デバイスはメッセージパケットを受信するための入力バッファと、使用するＳ＊デバイスを指定する送信デバイスとを指定する。データを要求するデバイスは送信デバイスに利用可能なＳ＊スイッチの選択権を与えるため、送信デバイスが空いている出力を発見する確率が増加する。
【００４５】
この設計により、集積回路チップのピンの全数が減少し、外部デバイスの入力ポートと出力ポートの両方の数が増加する。多くの技術でＭＬＭＬネットワーク技術はピンに制限を受ける。特に典型的な設計や集積回路では顕著である。階層の数はシリコンを多く使用することによって倍になり得る。しかしながら、集積回路チップ上のピンの数はパッケージング状態により多くの場合、倍にはできない。複数のＳ＊スイッチの使用により、単一の集積回路チップによって扱うことができるデバイスの数を超えて、デバイスの全数を増やすことができる。ＭＬＭＬチップの出力の大部分は出力ポートで消費されるため、複数の集積回路チップにわたるネットワークの分散は、集積回路チップ設計に依存するピン当たりのエネルギー消費及び熱の発生を減少させる。
【００４６】
図５Ａに示す実施例では、４個の集積回路チップを１個のチップ上に配置する。しかしながら、実施例の技術は一般的で集積回路の数は形態により変更される。この技術は図５Ｂに示すように、デバイスが入力データをＳ＊スイッチの全てに与えることができず、スイッチの一部にのみ与えることができるように展開し得る。この技術により外部デバイス当たりのスイッチのピン数を減らすことができる。この方法によれば、集積回路チップ上のネットワークの大きさを２倍にすることによって、チップ上のピン数を増やすことなく、デバイスの数を２倍にすることができる。
【００４７】
集積回路チップ上に機能的に配置するために複数のスキームが使用される。例えば、複数のクロスバースイッチＸＳは１個のチップの上に配置することで、ＸＳスイッチそれぞれはＳ＊スイッチの全てからデータを受け取ることができる。他の実施形態では、１個のＸＳスイッチを独立したＳ＊チップと同じチップの上に配置することができる。図５Ａとそれに関連する記述は、ピンの数を減らして処理量を増加させるために、単一のＳネットワークを複数のＳ＊ネットワークに置換する方法を示している。ネットワークＵを複数のネットワークＵ＊に置換する技術はより簡単に見え似ているが、既に一般的な従来技術として実施されている。
【００４８】
従来技術のひとつは広範な実施形態で様々なチップに機能を分配して実施している。
【００４９】
＜＜巨大システム構築のための複数ネットワークの接続＞＞
ピン数を減らすために複数のスイッチを使用する開示した技術は、複数の集積回路チップを同様の方法で使用して、それぞれのメッセージパケットが１個のチップだけを通過する非常に巨大なネットワークを構築することができる。
【００５０】
数万もしくは数１０万のホストに対応するネットワークを構築するために、メッセージが１個以上の集積回路チップを通過する他のアーキテクチュアが使用され得る。図６Ａに、非制御ネットワークとスケジュールドネットワークの両方として使用することができる形態のひとつの型を例示する。図６Ａに示すネットワークにおいて、メッセージは２個のスイッチチップを通過する。ひとつの集積回路チップが、２Ｎ個のデバイスとの内部接続が可能な設計の場合には、本設計では２２Ｎ個のデバイスと内部接続するように２Ｎ個のスイッチチップを使用することができる。形態は参照文献２にねじれた立方体アーキテクチュアとして開示されている。図６Ａから図６Ｄに記載する、ねじれた立方体アーキテクチュアのひとつの特徴は、それぞれの最下層スイッチＢＸに対して、最も小さい添字を持つデバイスはライン６１０によってスイッチＴ０と接続され、次に小さい添字を持つデバイスはライン６１０によってスイッチＴ１と接続され、そして最後の最も大きい添字を持つデバイスはライン６１０によってスイッチＴＭ−１と接続される。一般化するとデバイスＤＸＭはスイッチＢＸからデータを受け取るためと、スイッチＴ０にデータを送るため接続される。デバイスＤＸＭ＋１はスイッチＢＸからデータを受け取るためと、スイッチＴ１にデータを送るため接続される。デバイスＤＸＭ＋２はスイッチＢＸからデータを受け取り、スイッチＴ２にデータを送るために接続され、その他、デバイスＤＸＭ＋Ｍ−１はスイッチＢＸからデータを受け取り、スイッチＴＭ−１にデータを送る。
【００５１】
図６Ａに示すネットワークは、図２に示す型のスイッチを用いて不定期なメッセージを運ぶ。図６Ａに制御ラインは記載していない。スケジュールドメッセージは図３に示す型のスイッチを使用する。
【００５２】
図６Ｂに示すアンスケジュールドメッセージを運ぶネットワークは、図６Ａに示すネットワークを通過する他のメッセージのスケジューリングを行う目的を持つ。図６Ｂに示す具体例のネットワークは、図６Ａに記載された型のねじれた立方体ネットワークであるが、論理素子６５０を有する。図６Ｂに示す型のネットワークは、図６Ａに示す型のネットワークのメッセージのスケジューリングを行うために使用される。
【００５３】
図６Ａの設計の中で、第１外部デバイスＤＪから第２外部デバイスＤＫに渡されるメッセージパケットＰはＤＪからデータ搬送ライン６１０を経由して第１もしくは最上位層ＭＬＭＬスイッチＴＸ６２０に送られる。最上位層のスイッチは、Ｎ個の出力ポートから出たメッセージパケットＰを、ライン６１８を経由して目標のデバイスＤＫに接続した最下位層のスイッチＢＹ６３０に送るために、２進法表示の最初のＮビットを使用する。例えば図４に示すＦＩＦＯ方式のような様々な長さのＦＩＦＯシフトレジスタが、サイクルの全てのデータをシフトレジスタから同時に出し、それと同時に最下位層スイッチに入れるために使用されるにも関わらず、最上層のスイッチは、補助スイッチを有さない。非制御の実施形態では、最下位層スイッチは図２に示す方法に沿って外部デバイスに接続される。制御された実施形態では、最下層スイッチは図３に示す方法に沿って外部デバイスに接続される。
【００５４】
以下の考察では、図６Ａに示すスケジュールドネットワークはネットワーク又はスイッチＳとし、図６Ｂに示すアンスケジュールドネットワークはネットワーク又はスイッチＵとする。ネットワークＳを経由して送信デバイスＤＳから受信デバイスＤＲに移動する複数のパケットを含むメッセージをスケジューリングするために、要求パケットＲＰがデバイスＤＲからネットワークＵを経由してデバイスＤＳに送られる。要求パケットはネットワークＳを経由してデバイスＤＳからデバイスＤＲに移動するデータのスケジューリングを開始するために使用される。デバイスＤＳは要求を受けた時に、デバイスＤＳは要求を処理して、返信パケットＡＰをデバイスＤＲに返す。
【００５５】
この方法は、上記した記載に従いつつ、デバイスＤＳが自由にデータを送信し、デバイスＤＲが自由にデータを受信するときに、更にタイムインターバルを調整する。タイムインターバルを調整することにより、デバイスＤＳに接続された最上位層スイッチからデバイスＤＲに接続された最下位層スイッチのバンド幅が十分になる。調整は、適当なデータパス上に設置された論理素子６５０によって制御される。デバイスＤＲは、要求するパケットとＤＲがデータを受けることができる時間を特定する要求パケットをデバイスＤＳに送る。データ受信時間は、１）入力ライン６１６及びデバイスＤＲの入力ポートの未来の使用予定、２）デバイスＤＲの入力バッファの未来のスケジューリング状態により制限される。要求パケットヘッダはデバイスＤＳのアドレスとパケットが論理素子の検査を受けること無く通過できることを示すフラグとを含む。ペイロード情報には、要求するデータのサイズ及びデバイスＤＲへの送信が可能な時間のリストが記載される。
【００５６】
デバイスＤＲからデバイスＤＳへの経路は図６Ｃに示す。デバイスＤＲ及びＤＳの選択は完全に任意であり、図６Ｃに示すデバイスはＲ＝０及びＳ＝Ｍ＋１が割り当てられる。パケットＲＰはライン６１０を経由して、スイッチＴ０と図示される最上位層のスイッチに移動する。単純な実施形態では、複数のラインがデバイスＤＲから最上位層スイッチに延在する。パケットＲＰは最上位層スイッチの点線上を通過し、接続ライン６１２及び論理素子６５０を通過して、デバイスＤＲに接続する最下位層スイッチに入る。要求パケットＲＰはフラグがセットされているため、論理素子Ｌ１に検査されずに通過する。要求パケットＲＰは論理素子の送信時間により論理素子内で遅延され得る。パケットＲＰはスイッチＢ１として図示される最下位層スイッチに向かう下降ライン６１４を通過する。パケットのルーティングに使用されるアドレスビットは、最上位層スイッチにより破棄され、最下位層スイッチを通過するパケットＲＰのルーティングに使用されるビットはルーティングのため適切な位置に存在する。パケットＲＰは点線に沿って最下層スイッチを通過する。パケットＲＰはライン６１６を通過してデバイスＤＳに移動する。
【００５７】
デバイスＤＳのロジックは出力ラインの未来の使用予定に基づいて１以上の時間間隔を決める。デバイスＤＳは送信されるデータに関する情報がなくても機能することができる。デバイスＤＳは選択した時間を示す返信パケットＡＰをデバイスＤＲに送る。仮に要求パケットが指定する時間が利用できない場合は、デバイスＤＳは返信パケットＡＰに拒否メッセージを入れて送る。
【００５８】
要求形式は全体的なシステム運用に依存する。ある例では、要求は時間枠［Ｔ，Ｔ＋Δ］（ここでΔ大なりイコールδ）以内に発生させる長さδの対する時間予約である。要求はデータが単一のストリームで到着することを特定する場合があり、また複数のストリームで到着することやストリーム間の時間間隔を伴って到着することを許容する場合がある。デバイスＤＳは時間枠［Ｔ，Ｔ＋Δ］以内に出力ポートが空いている時間がある限り要求を受ける。参照文献８は、要求及び返信パケットのスケジューリングタイムの変更方法について開示する。単一チップネットワークＳ等で、デバイスＤＳのロジックはＱｏＳシステムを利用したシステムのＱｏＳを強化する。ＱｏＳ方法は参照文献８に記載されている。例えば、デバイスＤＳから最上位層スイッチに複数のライン６１０が延在する場合、１以上のラインが高ＱｏＳメッセージのために予約される。非常に大きなシステムにとｘってＱｏＳを強化するシステムの能力は、通信の効率を向上させる。返信パケットが拒否メッセージを運ぶ場合に、返信パケットＡＰはデータが論理素子によって検査を受けることなく通過することができることを示すフラグを有する。１回以上の時間が利用できる場合には、時間は返信パケットＡＰに示され、パケットが論理素子により検査されるべきであることを示すフラグがセットされる。拒否及び受諾の場合において、デバイスＤＳは返信パケットをＤＲに送る。
【００５９】
図６ＤにデバイスＤＳからデバイスＤＲへの返信パケットの経路を示す。ここではデバイスＤＳはＤＭ＋１、デバイスＤＲはデバイスＤ０として記載する。返信パケットＡＰはデバイスＤＳから最上位層スイッチ６２０にライン６１０を経由して送られ、ヘッダ情報に基づいてＴ１として記載される最上位層スイッチは、返信パケットＡＰのデバイスＤＲにデータを送信するＢ０として記載される最下位層スイッチまでのルーティングを行う。最上位層スイッチから最下位層スイッチまでのラインは、論理素子６５０の選択された論理素子６５２を通過する。スイッチＵ内の最上位層スイッチから最下位層スイッチまでの経路は、１）最上位層スイッチ内の点線と斜線が付された論理素子とを接続するライン６１２と、２）論理素子６５２と、３）斜線が付された論理素子と最下層スイッチ内の点線とを接続するライン６１４とを含む。この経路は図６Ａに示すスイッチＳ内の１本のライン６１８と一致する。
【００６０】
ネットワークＵ内の対応するラインを下るスケジューリングされた全てのデータは、論理素子６５２を通過する返信パケットＡＰを使ってスケジューリングされる。例として、スイッチＴ１の出力ポート０からスイッチＢ０へのライン６１４を使うようにスケジューリングされた全てのデータは、論理素子６５２を通過する返信パケットＡＰを使ってスケジューリングされる。論理素子６５２は、論理素子６５２を通過するスイッチＵ内の全データラインの未来の利用可能性を調査する。それに応じて、論理素子６５２はスイッチＳ内でのデバイスＤＳからデバイスＤＲへのデータ搬送を要求する返信パケット内で特定された利用可能時間の組から１つ又は複数の時間間隔を選択することができる。
【００６１】
仮に返信パケットが、利用可能な時間帯がないことを示す場合には、論理素子は返信パケットが変更されずに通過することを許可する。仮に返信パケットが、論理素子が利用できない時間帯を含むデバイスＤＳの利用可能な時間を含んで論理素子に到着する場合には、論理素子は返信パケットを受諾から拒否へと変更する。要求パケットの利用時間が、論理素子が利用できる時間を含むとき、論理素子はパケットを送信する時間を選択及びスケジューリングし、返信パケットＡＰのスケジューリングタイムを変更する。論理素子は利用可能時間リストからスケジューリングタイムを削除することによって利用可能時間テーブルを書き換え、このスケジューリング手順についての動作を終了する。
【００６２】
デバイスＤＲは変更された返信パケットを、受諾又は拒否を示し受諾の場合にはスケジューリングされた時間帯を示すデバイスＤＳに送る。デバイスＤＳが複数回送信し、その内１回だけ論理素子に受け入れられた場合には、デバイスＤＲが返信パケットを論理素子からデバイスＤＳを経由して受け取るまで、デバイスＤＲは選択された時間帯を割り当てることができない。仮にデバイスＤＳが複数の出力ライン６１０を有する場合、返信パケット内のデバイスＤＲによって送信される時間の組は利用可能時間リストを制限しない。
【００６３】
デバイスＤＳが論理素子６５２からの変更されたパケットを受け取るために待機する場合には、返信パケットが戻って来るまで、デバイスＤ５はメモリの中に１またはそれ以上の要求パケットを保持するかもしれない。論理素子により変更された返信パケットは、他の論理素子によって検査されることなくパケットが通過できることを示すフラグセットを有する。デバイスＤＲは受け取った拒否の返信に対して、少し後に再提起することにより応答し、仮に望むデータが数カ所に存在する場合は、第２の場所にデータを要求する。アンスケジュールドネットワークは、動作を円滑にしてうまく処理をすることができる。アンスケジュールドネットワークのデータラインは、スケジューリングされたデータラインよりも異なるバンド幅で任意に設計することができる。
【００６４】
仮にデータの輸送をスケジューリングできない場合には、データを異なる最下位層スイッチに接続されたデバイスにコピーすることができる。そのデバイスはネットワークの制御を容易にする要求及び返信パケットの貯蔵所にアクセスすることができる。
【００６５】
スイッチＳを通過するトラフィックを制御する一つの方法は、スイッチＵを経由して要求パケットを送ることであり、ＳＡＮアプリケーションを含む巨大なアプリケーションに有用な方法である。クラスタ演算のような並列演算アプリケーションの例で、ネットワークＳを経由して輸送されるデータは、演算を管理するコンパイラによってスケジューリングされる。ネットワークＳは単純に全てのクラスタ演算を行う最下位層スイッチの特定の部位に接続されたデバイスに分配され、同時に他の最下位層スイッチに接続された他のデバイスは他の演算やデータ移送の目的で使用される。
【００６６】
＜＜代替の複数ネットワーク構造＞＞
巨大システムにおけるインターコネクト構造の第２の実施形態では、デバイスを多重アレイに変更する。２次元の場合について最初に述べる。デバイスは、横列及び縦列に配列される。横列内のプロセッサの数は、縦列内のプロセッサの数と異なってもよい。横及び縦列それぞれは、Ｍ個のプロセッサを含む。デバイスＤ（０，０），Ｄ（０，１），．．．，Ｄ（０，Ｍ−１）は第１横列内に有り、Ｄ（１，０），Ｄ（１，１），．．．，Ｄ（１，Ｍ−１）は第２横列に有り、Ｄ（Ｍ−１，０），Ｄ（Ｍ−１，１），．．．，Ｄ（Ｍ−１，Ｍ−１）は最終列内に有る。それぞれのデバイスは２つのアンスケジュールドネットワークと２つのスケジュールドネットワークとに接続される。Ｍ個のアンスケジュールドネットワークそれぞれは、縦列内のＭ個のデバイスに接続する。各横列は、アンスケジュールドネットワーク及びスケジュールドネットワークに接続されたＭ個のデバイスを含む。デバイスとネットワークとの間の２方向性の接続はデータラインと、制御ラインと、スイッチと、ＦＩＦＯとを含む。これらの内部接続は図１Ａから図４に示す接続と同様である。内部接続ラインはデータを搬送するラインと、デバイスからアンスケジュールドネットワークへの制御信号を送るライン１１６とを含む。また、ラインはデータを搬送するライン１１４と、アンスケジュールドネットワークからデバイスへの制御信号１１８とを含む。内部接続はデバイスとスケジュールドネットワークとを間でデータを運ぶ。データはデバイスからスケジュールドネットワークへとライン１２２を経由して移動する。データはスケジュールドネットワークからライン１２４（可能であればＦＩＦＯ４１０を通過して）を経由して補助スイッチ１４０（より小さなスイッチ１５０を含む）に入り、補助スイッチからデバイス１３０へとライン１２６を経由して入る。更に、特定のデバイスでは、データは直接的にひとつのスケジュールドネットワークから他のスケジュールドネットワークへとラインを経由して、外部デバイスを経由せずに移動することができる。スケジュールドネットワーク内の送信スイッチのボトムリング上の異なる縦列からのデータが、スケジュールド受信ネットワークに適したデータ挿入時間に到着するために、データは図４に示す１列に並んだＦＩＦＯ４１０と類似した１列に並んだＦＩＦＯを通過し得る。
【００６７】
２Ｍ個のネットワークのそれぞれが分離したチップ上に存在する場合には、同じ横列内のノード間又は同じ縦列内のノード間を移動するデータは、ひとつのネットワークスイッチのみを経由して移動する。実際にこのようなデータに対しては、システムの動作は基本的な単一チップネットワークシステムの動作と同様である。２個のデバイスが同一の横列又は縦列の接続上にない時、データは２個のチップ間を移動する。横列Ａ及び縦列Ｂ上にあるデバイスＤ（Ａ，Ｂ）から横列Ｘ及び縦列Ｙ上にあるデバイスＤ（Ｘ，Ｙ）にアンスケジュールドメッセージを送る場合で、Ａ≠Ｘ及びＢ≠Ｙの場合とする。このとき、Ｄ（Ａ，Ｂ）はメッセージをＤ（Ａ，Ｙ）又はＤ（Ｘ，Ｂ）のいずれかに送り、そしてそのデバイスにメッセージをＤ（Ｘ，Ｙ）に送るよう要求する。ここでＤ（Ａ，Ｂ）がＤ（Ｘ，Ｂ）にメッセージを送る場合について考察する。実際には、メッセージはＤ（Ａ，Ｂ）からＤ（Ｘ，Ｙ）へ複数回飛び渡るが、それらの内で１回はチップからチップへの移動を含む。アンスケジュールドネットワークでは、仮にＤ（Ｘ，Ｂ）への入力が過負荷で有る場合には、メッセージは、制御信号がメッセージに最初のネットワークから出てデバイスＤ（Ｘ，Ｂ）に入るように許可するまでネットワーク中を１回又は数回移動する場合がある。送信する機会が利用可能な場合にＤ（Ｘ，Ｂ）はＤ（Ｘ，Ｙ）にメッセージを送る。Ｄ（Ｘ，Ｙ）は通過メッセージのＱｏＳを強化するために設置される。アンスケジュールドメッセージは、複数の文節を含む長いメッセージＭをスケジューリングするために要求され得る。その場合、Ｄ（Ａ，Ｂ）はＤ（Ｘ，Ｂ）の受信時間に従う。また、Ｄ（Ｘ，Ｂ）はＤ（Ａ，Ｂ）及びＤ（Ｘ，Ｂ）の両方が受諾可能な時間のセットを含むＤ（Ｘ，Ｙ）の受信可能時間に従う。Ｄ（Ｘ，Ｙ）は送信デバイス及び中間デバイスの両方に受け入れられる時間間隔を選択し、タイミングメッセージＴを調整された時間のバンド幅を予約する中間デバイスを経由して返信する。このタイミングメッセージＴはＤ（Ａ，Ｂ）が受信可能な時間にメッセージＭを送信した後に、Ｄ（Ｘ，Ｂ）からＤ（Ａ，Ｂ）に送られる。このシステムは、送信時間より前に受諾メッセージがＤ（Ａ，Ｂ）に到着する可能性が高くなるように設計されるべきである。仮にそうでなければ、Ｄ（Ａ，Ｂ）はメッセージを送信するために他の時間を調整する。Ｄ（Ａ，Ｂ）が、メッセージをＤ（Ｘ，Ｂ）を経由して送ることについての受諾を受け取らない場合は、Ｄ（Ａ，Ｂ）はＤ（Ａ，Ｙ）に連絡を取ることによってメッセージをスケジューリングしようと試みる。
【００６８】
スケジュールドネットワークでは、Ｄ（Ａ，Ｂ）からＤ（Ｘ，Ｙ）に移動するメッセージは、実際には中間デバイスＤ（Ｘ，Ｂ）を通過せず、横列Ａ上のデバイスに接続するネットワークから縦列Ｙ上のデバイスに接続するネットワークへとインターコネクトを経由してデータは移動する。２つのスケジュールドネットワーク間のインターコネクションは、中間デバイスを経由しない場合がある。スケジュールドネットワークのボトムリング上のノードは、ラインによって接続される場合がある。参照文献２を含む参照文献中に記載されたインターコネクションでは、メッセージは同位のひとつのノードから次のノードへと２クロックティック以内に移動する。従って、左端のノードから出るメッセージは、次の退出可能時間であるメッセージがその２個右のノードから出る時よりも４ティック前に出る。様々な長さのＦＩＦＯは最初のネットワークを出るメッセージパケットを再調整し、受信スイッチの入力縦列上のノードに入るときにメッセージは時間的に整合される。関連する参照文献に記載されているように、データは直ちにライン上の同位のスケジュールド受信スイッチに移動するか、又はライン上の下位レベルへと移動することができる。更に、ＦＩＦＯはスイッチにデータを入力するデバイス１３０から受信スイッチに入るメッセージと他のメッセージとを整列する。便利な実施形態では、デバイスからのメッセージは他のスケジュールドスイッチから直接データを受け取らないノード上の受信スイッチに入る。
【００６９】
本項で記載したシステムは、「低ピンカウントを目的とした複数スイッチの使用」とタイトルを付けた項で記載したシステムと組み合わせることができ、それぞれのネットワークを複数個のチップ上に実現することができる。この場合に、チップの最下位層横列上のノードを出るメッセージは第２のネットワークを形成する異なるチップに入る。
【００７０】
本項の実施形態では、デバイス１３０は２次元アレイとして配列される。デバイスが３次元に配列される実施形態では、各デバイス１３０は６つのネットワークに接続され、各ネットワークは各次元でスケジュールド及びアンスケジュールドネットワークを含む。Ｄ（Ａ，Ｂ，Ｃ）からＤ（Ｘ，Ｙ，Ｚ）に移動するメッセージは６つの経路を有し、Ｄ（Ａ，Ｂ，Ｃ）からＤ（Ａ，Ｙ，Ｃ）、Ｄ（Ａ，Ｙ，Ｚ）、そして最終的にＤ（Ｘ，Ｙ，Ｚ）の経路を含む、それぞれ２回のホップを含む。Ｎ次元アレイ中の外部デバイスを有する例は、各デバイスに対して２Ｎ個のネットワークを持つ。
【００７１】
＜＜単一ネットワーク内でのスケジュールドＳとアンスケジュールドＵの多重化＞＞
図２に示すネットワークは、メッセージグループが同時に同じ縦列に入ったときに、メッセージの最初のビットは、構造を循環するメッセージとして整列された縦列内に留まる特徴を持つ。ネットワークは適した長さのＦＩＦＯシフトレジスタを備えることができ、入ったメッセージの最初のビットはシステム内に既にあるメッセージの最初のビットと共に配列される。それに応じて、ネットワークは複数のメッセージ長さに対応する形態で使用される。長さＬの長いパケットと長さＳの短いパケットとを含む２つのパケットの場合には、ＦＩＦＯ長さは調整されて、挿入される短いメッセージは、既に相互に配列された挿入された長いメッセージから分離して相互に配列される。
【００７２】
この概念は、挿入縦列において反復処理が発生するように拡張することができる。Ｎ個の長いメッセージは一つの短いメッセージに続かれて挿入される。その結果、スケジュールド及びアンスケジュールドメッセージは同じ構造を使用するが、時分割多重方式を用いて分割され、識別される。スケジュールドメッセージのために設計された場合には、長いメッセージはＦＩＦＯ構造に入らない。ＦＩＦＯ構造は短いメッセージのために使用される。短いＦＩＦＯは要求及び返信パケットを入れることができるが、長いメッセージの挿入のために予約された期間中に循環して戻すことはできない。ＦＩＦＯの挙動はデータが論理ノードを有するシステムの特定の部分に再び入ることが可能となるまで短いメッセージを循環して移動させることによって達成される。
【００７３】
＜＜追加ネットワークを使用した実施形態＞＞
図１Ａは、各外部デバイスが２つのネットワークに接続するシステムを示し、そしてデバイスがさらに追加のネットワークに接続される拡張可能な概念を示す。参照文献に記載された技術は、高バンド幅と低レイテンシを有し安価に構築できる構造を画定するため、実用的な拡張が可能である。いくつかの実施形態では、いくつかの要求及び返信パケットのみを扱ういくつかのアンスケジュールドネットワークと、いくつかの要求及び返信パケット以外の型のトラフィックを扱ういくつかのアンスケジュールドネットワークとを有する２以上のアンスケジュールドネットワークを備える。
【００７４】
他の実施形態では、各デバイスは１以上の図６Ａ及び図６Ｂに記載された型のシステムに接続し、付加的に図１Ａに記載された型のネットワークに接続する。その結果、デバイスは１回のネットワーク間のホップを局所的に通過して、或いは複数回の構造間のホップを全体的に通過して通信するボトムスイッチの同一のものに接続する。
【００７５】
＜＜ＰＩＭアーキテクチュアを使用した実施形態＞＞
記載した参照文献の技術は図１Ａ，図２，図３に示す型の構造を使用したプログラム・イン・メモリ（ＰＩＭ）において非常に役立つ。プロセッサを含むＰＩＭアーキテクチュアデバイスは、単一の集積回路チップ上に形成される。デバイスはここで記載された技術を使用した大きなネットワークに接続される。パケットは選択されたピン又は光学的ポート又は選択されたデバイスの他の型のポートに入るようにスケジューリングされ、その結果データはＰＩＭチップ上の特定のプロセッサに目標付けられ、又はチップのメモリエリアに目標付けられる。この技術は大きく演算能力を向上させる潜在能力を持つ。
【００７６】
様々な実施形態についてここでは開示したが、これらの実施形態は例示的なものであり、請求の範囲を制限するものではない。記載された実施形態の様々な変更や修飾、付加、改良が可能である。例えば、当業者がここで開示した構造及び方法を提供するために必要な過程を容易に実施する場合にプロセスパラメータ及び物質、大きさは実施形態のみによって与えられると理解するであろう。請求の範囲内で修飾をして所望の構造を達成するためにパラメータ及び物質、組成、大きさは変更することができる。ここで開示した実施形態の変更及び修飾はまた、従属クレームの範囲内を維持したまま成される。
【００７７】
＜＜参照文献＞＞
１．  U. S. Patent No. 5,996, 020 entitled, "A Multiple Level Minimum Logic Network", naming Coke S. Reed as inventor;
２．  U. S. Patent No. 6,289, 021 entitled, "A Scaleable Low Latency Switch for Usage in an Interconnect Structure", naming John Hesse as inventor;
３．  United States patent application serial no. 09/693,359 entitled, "Multiple Path Wormhole Interconnect", naming John Hesse as inventor; 
４．  United States patent application serial no. 09/693,357entitled,"Scalable Wormhole- Routing Concentrator", naming John Hesse and Coke Reed as inventors;
５．  United States patent application serial no. 09/693,603 entitled, "Scaleable Interconnect 
Structure for Parallel Computing and Parallel Memory Access", naming John Hesse and Coke Reed as inventors;
６．  United States patent application serial no. 09/693,358 entitled, "Scalable Interconnect Structure Utilizing Quality-Of-Service Handling", naming Coke Reed and John Hesse as inventors;
７．  United States patent application serial no. 09/692,073 entitled, "Scalable Method and Apparatus for Increasing Throughput in Multiple Level Minimum Logic Networks Using a Plurality of Control Lines", naming Coke Reed and John Hesse as inventors;
８．  United States patent application serial no．09／919，462entitled，“Means and Apparatus for a Scaleable Congestion Free Switching System with Intelligent Control”，naming John Hesse and Coke Reed as inventors；
９．  United States patent application serial no．10／123，382entitled，“A Controlled Shared Memory Smart Switch System”，naming Coke S．Reed and David Murphy as inventors
【図面の簡単な説明】
【００７８】
【図１Ａ】スケジュールドネットワーク及びアンスケジュールドネットワークの両方に接続する複数の計算及びデータストレージデバイスを示すブロック図である。
【図１Ｂ】図１Ａに示すブロック図にアンスケジュールドスイッチに接続する制御ラインを追加したブロック図である。
【図１Ｃ】図１Ａ及び図１Ｂに示すブロック図にスモールスイッチの組からなる補助スイッチを追加したブロック図である。
【図２】アンスケジュールドトラフィックの通信に適したスイッチを示すブロック図である。
【図３】スケジュールドトラフィックの通信に適したスイッチを示すブロック図である。
【図４】スケジュールドネットワークから外部デバイスへのデータを通信するための接続を示すブロック図である。
【図５Ａ】単一のチップ上にあるスイッチの複数個のチップ上にあるスイッチへの置き換えを示すブロック図である。
【図５Ｂ】単一のチップ上にあるスイッチの複数個のチップ上にあるスイッチへの置き換えを示すブロック図である。
【図６Ａ】ねじれた立方体（ｔｗｉｓｔｅｄ  ｃｕｂｅ）形態の複数個のＭＬＭＬネットワークを備えたシステムを示すブロック図である。
【図６Ｂ】ねじれた立方体（ｔｗｉｓｔｅｄ  ｃｕｂｅ）形態の複数個のＭＬＭＬネットワークを備えたシステムを示すブロック図である。
【図６Ｃ】ねじれた立方体（ｔｗｉｓｔｅｄ  ｃｕｂｅ）形態の複数個のＭＬＭＬネットワークを備えたシステムを示すブロック図である。
【図６Ｄ】ねじれた立方体（ｔｗｉｓｔｅｄ  ｃｕｂｅ）形態の複数個のＭＬＭＬネットワークを備えたシステムを示すブロック図である。
【図１Ａ】
2007532052.tif 000003
【図１Ｂ】
2007532052.tif 000004
【図１Ｃ】
2007532052.tif 000005
【図２】
2007532052.tif 000006
【図３】
2007532052.tif 000007
【図４】
2007532052.tif 000008
【図５Ａ】
2007532052.tif 000009
【図５Ｂ】
2007532052.tif 000010
【図６Ａ】
2007532052.tif 000011
【図６Ｂ】
2007532052.tif 000012
【図６Ｃ】
2007532052.tif 000013
【図６Ｄ】
2007532052.tif 000014
【国際調査報告】
2007532052.tif 000015