(57)【要約】【課題】大きなコンピューティングおよび通信システムに渡って同期用クロックを維持することは課題である。【解決手段】入力ポートの集まり、出力ポートの集まり、およびスイッチング素子を含む相互接続構造が開示された。データは、特定のデータ入力時間にのみスイッチング素子に入力される。相互接続構造は同期化素子の集まりを含む。パケットの形のデータは非同期式で入力ポートに入力される。データパケットは入力ポートから同期化ユニットに渡される。データは、同期化ユニットを出て、特定のデータ入力時間にスイッチング素子に到達する各パケットと共にスイッチング素子に入力される。【選択図】図２Ａ
2006114028.tif 000002
【特許請求の範囲】
【請求項１】
入力ポートの集まり、出力ポートの集まり、および
特定のデータ入力時間にのみＤＶスイッチング素子にデータが入力されるスイッチング素子ＤＶを含み；
同期化素子の集まりをさらに含む相互接続構造であって、
パケットの形のデータが非同期式で上記入力ポートに入力され；
データパケットが上記入力ポートから同期化ユニットに渡され；
データが上記同期化ユニットを出て、特定のデータ入力時間に上記ＤＶスイッチング素子に到達する各パケットと共に上記ＤＶスイッチング素子に入力されることを特徴とする相互接続構造。
【請求項２】
同期化ユニットがＦＩＦＯを含み、上記ＦＩＦＯの第１の複数のセルが１出力ポートのみを持つパッシブセルであり、
上記ＦＩＦＯの第２の複数のセルが、メッセージパケットが同期化ユニットの中に存在する時間の長さが上記ＦＩＦＯユニットの中のアクティブセルの設定に依存する出力ポートＯＡおよび出力ポートＯＢを含む１より多い出力ポートを持つアクティブセルであることを特徴とする請求項１に記載の相互接続構造。
【請求項３】
上記ＦＩＦＯの上記アクティブセルが論理ユニットＬにより設定されることを特徴とする請求項２に記載の相互接続構造。
【請求項４】
上記論理ユニットＬがクロックからの入力を受信し、パケットがネットワークに入力された時に記録する論理ユニットからの入力も受信する請求項３に記載の相互接続構造。
【請求項５】
与えられた同期化ユニットが、セルＣからのデータが直接スイッチング素子ＤＶに渡されるセルＣを備える上記ＦＩＦＯユニットＦ０を含む複数のＦＩＦＯユニットを含み、上記パケットの第１のビットがセルＣから上記スイッチング素子ＤＶに特定のデータ入力時間にのみ渡されることを特徴とする請求項１に記載の相互接続構造。
【請求項６】
データが上記ＤＶスイッチング素子に入力されるのと同じデータレートで、上記ＦＩＦＯユニットを通ってデータがシフトされることを特徴とする請求項５に記載の相互接続構造。
【請求項７】
合計ＰＮ個のビットを含む全体のパケットが、ＦＩＦＯから上記ＤＶスイッチング素子へ、上記ＤＶスイッチング素子を通るデータレートを決定するＰＮ周期のクロックで転送されることを特徴とする請求項６に記載の相互接続構造。
【請求項８】
複数の同期化ユニットおよびスイッチング素子ＤＶが１つのチップ上にあり、データパケットＰがチップの入力ポートＩＰを通って上記チップに入力され、シリアライゼーション−デシリアライゼーション（ＳＥＲＤＥＳ）モジュールを通って転送され、上記ＳＥＲＤＥＳモジュールから同期化ユニットに転送され、上記同期化ユニットから上記ＤＶスイッチング素子に転送され、上記ＤＶスイッチング素子から出力ＦＩＦＯに渡され、出力ＦＩＦＯからＳＥＲＤＥＳモジュールに転送され、上記ＳＥＲＤＥＳモジュールからチップの出力ポートに転送されることを特徴とする請求項７に記載の相互接続構造。
【請求項９】
上記ＤＶスイッチング素子が複数の階層の最小論理ネットワークであることを特徴とする請求項１に記載の相互接続構造。
【請求項１０】
複数のノードと、上記複数のノードを選択的に結合する相互接続ラインとからなる相互接続構造であって、
上記ノードが複数の階層および角度に配置され、
ａ）別の論理ノードＡ、Ｂ、Ｃ、およびＸを含み、上記論理ノードＡが、上記論理ノードＢまたは上記論理ノードＣに、Ａに入力されるパケットＰを送信でき、ＰのＢまたはＣへの上記送信が、Ｂのヘッダに部分的に基づき、上記ノードＸがＡに制御信号を送信するか否かにも部分的に基づく論理ノードを含み、
ｂ）ＦＩＦＯの複数の上記セルが１出力ポートのみを持つパッシブセルであり；
上記ＦＩＦＯの複数の上記セルが、出力ポートＯＡおよび出力ポートＯＢを含む１より多い出力ポートを持つアクティブセルであり；
メッセージパケットが上記ＦＩＦＯの中に存在する時間の長さが、上記ＦＩＦＯユニットの中の上記アクティブセルの設定に依存することを特徴とする上記ＦＩＦＯの中に配置されたノード
も含む数タイプから成ることを特徴とする相互接続構造。
【請求項１１】
上記ＦＩＦＯの中の上記アクティブノードの上記設定が、上記相互接続構造を通って送信される上記パケットの長さを決定することを特徴とする請求項１０に記載の相互接続構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時間に相関していない複数のパケットを１組の同期受信デバイスに入力する方法と手段に関し、この技術の重要な応用は、組み入れられた特許文献８、特許文献１０、特許文献１１、特許文献１２、特許文献１４、特許文献１６、および特許文献１７に記載されたシステムを含む広範な種類のシステムに複数のパケットを入力する時、組み入れられた特許文献２、特許文献３、特許文献４、特許文献５、特許文献６、および特許文献１３に記載されたタイプのネットワークを使用するシステムのタイミングの要件を緩和することである。１つの実施の形態では、分離したチップへ時間を通信するクロックを持たず、チップ間を渡るタイミング情報もない。
【背景技術】
【０００２】
大きなコンピューティングおよび通信システムは、多くのサブシステムに渡って広がり、多くのラックまたはキャビネットに位置される論理およびメモリコンポーネントを持つ。異なるチップの上のデバイスは、これらのキャビネットの中の複数のボードの上に位置されるかもしれず、並列で動作することを要求されるかもしれない。
【０００３】
開示されたシステムおよび動作方法は、参照によりその全体がここに組み入れられた以下の特許および特許出願の中で開示された事項に関する。
【特許文献１】米国特許第５，９９６，０２０号、“Ａ  Ｍｕｌｔｉｐｌｅ  Ｌｅｖｅｌ  Ｍｉｎｉｍｕｍ  Ｌｏｇｉｃ  Ｎｅｔｗｏｒｋ”、発明者、Ｃｏｋｅ  Ｓ．Ｒｅｅｄ
【特許文献２】米国特許第６，２８９，０２１号、“Ａ  Ｓｃａｌｅａｂｌｅ  Ｌｏｗ  Ｌａｔｅｎｃｙ  Ｓｗｉｔｃｈ  ｆｏｒ  Ｕｓａｇｅ  ｉｎ  ａｎ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｓｔｒｕｃｔｕｒｅ”、発明者、Ｊｏｈｎ  Ｈｅｓｓｅ
【特許文献３】米国特許第６，７５４，２０７号、“Ｍｕｌｔｉｐｌｅ  Ｐａｔｈ  Ｗｏｒｍｈｏｌｅ  Ｉｎｔｅｒｃｏｎｎｅｃｔ”、発明者、Ｊｏｈｎ  Ｈｅｓｓｅ
【特許文献４】米国特許第６，６８７，２５３号、“Ｓｃａｌａｂｌｅ  Ｗｏｒｍｈｏｌｅ−Ｒｏｕｔｉｎｇ  Ｃｏｎｃｅｎｔｒａｔｏｒ”、発明者、Ｊｏｈｎ  ＨｅｓｓｅおよびＣｏｋｅ  Ｒｅｅｄ
【特許文献５】米国特許出願第０９／６９３，６０３号、“Ｓｃａｌｅａｂｌｅ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｓｔｒｕｃｔｕｒｅ  ｆｏｒ  Ｐａｒａｌｌｅｌ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｐａｒａｒｅｌｌ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ”、発明者Ｊｏｈｎ  ＨｅｓｓｅおよびＣｏｋｅ  Ｒｅｅｄ
【特許文献６】米国特許出願第０９／６９３，３５８号、“Ｓｃａｌａｂｌｅ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｓｔｒｕｃｔｕｒｅ  Ｕｔｉｌｉｚｉｎｇ  Ｑｕａｌｉｔｙ−Ｏｆ−Ｓｅｒｖｉｃｅ  Ｈａｎｄｌｉｎｇ”、発明者、Ｃｏｋｅ  ＲｅｅｄおよびＪｏｈｎ  Ｈｅｓｓｅ
【特許文献７】米国特許出願第０９／６９２，０７３号、“Ｓｃａｌａｂｌｅ  Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｉｎｃｒｅａｓｉｎｇ  Ｔｈｒｏｕｇｈｐｕｔ  ｉｎ  Ｍｕｌｔｉｐｌｅ  Ｌｅｖｅｌ  Ｍｉｎｉｍｕｍ  Ｌｏｇｉｃ  Ｎｅｔｗｏｒｋｓ  Ｕｓｉｎｇ  ａ  Ｐｌｕｒａｌｉｔｙ  ｏｆ  Ｃｏｎｔｒｏｌ  Ｌｉｎｅｓ”、発明者、Ｃｏｋｅ  ＲｅｅｄおよびＪｏｈｎ  Ｈｅｓｓｅ
【特許文献８】米国特許出願第０９／９１９，４６２号、“Ｍｅａｎｓ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  ａ  Ｓｃａｌｅａｂｌｅ  Ｃｏｎｇｅｓｔｉｏｎ  Ｆｒｅｅ  Ｓｗｉｔｃｈｉｎｇ  Ｓｙｓｔｅｍ  ｗｉｔｈ  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｃｏｎｔｒｏｌ”、発明者、Ｊｏｈｎ  ＨｅｓｓｅおよびＣｏｋｅ  Ｒｅｅｄ
【特許文献９】米国特許出願第１０／１２３，３８２号、“Ａ  Ｃｏｎｔｒｏｌｌｅｄ  Ｓｈａｒｅｄ  Ｍｅｍｏｒｙ  Ｓｍａｒｔ  Ｓｗｉｔｃｈ  Ｓｙｓｔｅｍ”、発明者、Ｃｏｋｅ  Ｓ．ＲｅｅｄおよびＤａｖｉｄ  Ｍｕｒｐｈｙ
【特許文献１０】米国特許出願第１０／１２３，９０２号、“Ｍｅａｎｓ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  ａ  Ｓｃａｌｅａｂｌｅ  Ｃｏｎｇｅｓｔｉｏｎ  Ｆｒｅｅ  Ｓｗｉｔｃｈｉｎｇ  Ｓｙｓｔｅｍ  ｗｉｔｈ  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｃｏｎｔｒｏｌ  II”、発明者、Ｃｏｋｅ  ＲｅｅｄおよびＤａｖｉｄ  Ｍｕｒｐｈｙ
【特許文献１１】米国特許出願第１０／７９８，５２６号、“Ｍｅａｎｓ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  ａ  Ｓｃａｌａｂｌｅ  Ｎｅｔｗｏｒｋ  ｆｏｒ  Ｕｓｅ  ｉｎ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｄａｔａ  Ｓｔｏｒａｇｅ  Ｍａｎａｇｅｍｅｎｔ”、発明者、Ｃｏｋｅ  ＲｅｅｄおよびＤａｖｉｄ  Ｍｕｒｐｈｙ
【特許文献１２】米国特許出願第１０／８６６，４６１号、“Ｍｅａｎｓ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｓｃａｌａｂｌｅ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐａｒａｌｌｅｌ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ  Ｓｙｓｔｅｍｓ  ｗｉｔｈ  Ｉｎｔｅｒｎｅｔ  Ｒｏｕｔｉｎｇ  Ａｐｐｌｉｃａｔｉｏｎｓ”、発明者Ｃｏｋｅ  ＲｅｅｄおよびＤａｖｉｄ  Ｍｕｒｐｈｙ
【特許文献１３】米国特許出願第１０／５１５，９３７号、“Ｍｅａｎｓ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  ａ  Ｓｅｌｆ−Ｒｅｇｕｌａｔｉｎｇ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｓｔｒｕｃｔｕｒｅ”、発明者、Ｃｏｋｅ  Ｒｅｅｄ
【特許文献１４】米国特許出願第６０／５６１，２３１号、“Ｍｅａｎｓ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｎｇ  Ｍｕｌｔｉｐｌｅ  Ｃｌｕｓｔｅｒｓ  ｏｆ  Ｄｅｖｉｃｅｓ”、発明者、Ｃｏｋｅ  Ｒｅｅｄ
【特許文献１５】米国特許出願第１１／２１４，９８４号、“Ｍｅａｎｓ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  ａ  Ｓｃａｌｅａｂｌｅ  Ｃｏｎｇｅｓｔｉｏｎ  Ｆｒｅｅ  Ｓｗｉｔｃｈｉｎｇ  Ｓｙｓｔｅｍ  ｗｉｔｈ  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｃｏｎｔｒｏｌ  III”、発明者、Ｊｏｈｎ  Ｈｅｓｓｅ、Ｃｏｋｅ  ＲｅｅｄおよびＤａｖｉｄ  Ｍｕｒｐｈｙ
【特許文献１６】米国特許出願第６０／５５１，１１０号、“Ｈｉｇｈｌｙ  Ｐａｒａｌｌｅｌ  Ｓｗｉｔｃｈｉｎｇ  Ｓｙｓｔｅｍｓ  Ｕｔｉｌｉｚｉｎｇ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ”、発明者、Ｃｏｋｅ  ＲｅｅｄおよびＤａｖｉｄ  Ｍｕｒｐｈｙ
【特許文献１７】米国特許出願第１１／０７４，４０６号、“Ｈｉｇｈｌｙ  Ｐａｒａｌｌｅｌ  Ｓｗｉｔｃｈｉｎｇ  Ｓｙｓｔｅｍｓ  Ｕｔｉｌｉｚｉｎｇ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  II”、発明者、Ｃｏｋｅ  ＲｅｅｄおよびＤａｖｉｄ  Ｍｕｒｐｈｙ
【発明の開示】
【発明が解決しようとする課題】
【０００４】
そのようなシステムに渡って同期用クロックを維持することは課題である。
【課題を解決するための手段】
【０００５】
本発明は、全てのサブシステムが同期する要求を緩和する。この緩和はＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチを含むシステムには非常に重要であり、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチは、異なるクロックに基づいて各々動作している広い範囲のデバイスから多数のポートへの入力を同時に（すなわち、内部クロックの同じ周期で）受信する。
【０００６】
Ｄａｔａ  Ｖｏｒｔｅｘ（商標）技術は、１チップ上に配置された数百の入力および出力との相互接続構造の大きなスイッチングを可能にする。Ｄａｔａ  Ｖｏｒｔｅｘ（商標）の動作は、（恐らく異なる出力源からの）メッセージパケットが、同じクロック周期でスイッチに入力される必要がある。これは、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）チップ内では、データメッセージパケットの最初のビットがＤａｔａ  Ｖｏｒｔｅｘ（商標）のデータ入力ノードに入力を許可される時のみの特別なメッセージ入力時間（チップクロック周期）がある。
【０００７】
本発明の第１の形態は、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチを含むチップの入力ポートを、上記チップの上に存在するＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチの入力ポートに接続する相互接続構造の設計である。教えられる構造の中で、１ビットのパケットがチップの入力ポートからＤａｔａ  Ｖｏｒｔｅｘ（商標）サブシステムの入力ポートに移動するのに必要な時間の長さは、異なる時間にチップの入力ポートに到達する複数のパケットが特定のメッセージ入力時間のみＤａｔａ  Ｖｏｒｔｅｘ（商標）サブシステムの入力に到達するように、変化する。前の文で基準とされる時間はオンチップクロックに関する。
【０００８】
Ｄａｔａ  Ｖｏｒｔｅｘ（商標）技術を使用する（組みいれられた特許文献８、特許文献１０、特許文献１１、特許文献１２、特許文献１４、特許文献１６、および特許文献１７に記載されたシステムを含む）多くのシステムは、与えられた入力時間において、「スタック」の中の１つのチップがパケットＰ０、Ｐ１、．．．、ＰＫの集まりを受信し、０＜Ｊ＜Ｋである整数Ｊ、ＰＪおよびＱＪに関して、同じ発生元、同じ行き先、および同じヘッダを持つように「スタック」の中のもう１つのチップがパケットＱ０、Ｑ１、．．．、ＱＫの集まりを受信するという意味では、共に動作するＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチの「スタック」を含む。
【０００９】
本発明の第２の形態は、ＰＪおよびＱＪが同時にそれらの対応するスイッチに到達すべきという条件を、ＰＪおよびＱＪが「ほぼ」同時にそれらの対応するスイッチに到達すべきという条件に緩和する。スイッチチップは離れたボード上に配置される可能性があるので、この緩和により、全システムがより堅固になり、より費用効率のいい方法でつくられる。
【００１０】
本発明の第３の形態は、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチングシステムを備えた並列コンピュータシステムなどのデバイスの既存のシステムのインタフェースをもつネットワークインタフェースカード（ＮＩＣ）の設計と実現を導入する。
【発明を実施するための最良の形態】
【００１１】
動作の構造およぶ方法に関連するシステムおよび関連する技術を図示した実施の形態は以下の説明および添付の図を参照することのより最もよく理解できる。
【００１２】
以下、添付の図を参照して発明の実施の形態を説明する。
【００１３】
同期化ユニット２３０を通してＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ２３４のノードアレイにデータを送信するデバイス２３２を示す図２Ａを参照する。デバイス２３２は、図１Ａに示されているように入出力デバイス１０４であってもよいし、図１ｂに示されているようにコンピューティングまたはデータ記憶デバイス１７０であってもよい。デバイスＤ０、Ｄ１、．．．、ＤＮ−１は互いに同期化される必要はなく、したがって同期化ユニットＳＵ０、ＳＵ１、．．．、ＳＵＮ−１に到達するパケットは、種々の時間に到達する。Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチは、固定長ＰＬからなり、各パケットの先頭ビットが常に１に設定されたデータパケットを受信する。固定されたパケット受信時間があり、したがって、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ２３４のＤａｔａ  Ｖｏｒｔｅｘ（商標）ノードアレイ２２２はパケット受信時間の１つのみでデータパケットの第１のビットを受信せねばならない。同期化ユニットの機能は、データパケット受信時間に、データパケットの第１のビットをＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチのデータ受信ノードに送ることである。好ましい実施の形態では、同期化ユニットおよびＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチは同じチップ上に乗っており、したがって同じチップのクロックを利用する。好ましい実施の形態では、同期化ユニットの数は、受信ノードアレイの中のノードの数に等しく、各同期化ユニットは受信ノードアレイの１つのノードに関連する。
【００１４】
入力ライン２２６を通ってデータを受信し、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチの受信ノードアレイＮＡ２２２のノード２２０にデータを送信する同期化ユニットＳＵ２３０を示す図２Ｂを参照する。図２Ｃは、ノードからの入出力ラインを備えたノードアレイの詳細を示す。同期化ユニット２３０は本発明の重要な形態である。データパケットは、ライン２２６を通って同期化ユニットに連続的に入力され、任意の誤り訂正ユニットＥＣ２６０により処理され、ノード２０２に入力される。第１の実施の形態では、誤り訂正ユニットは、全てのパケットの中の誤りを検出および訂正し；第２の実施の形態では、誤り訂正ユニットは、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）の出力ポートアドレスの中のみの誤りを検出および訂正し；第３の実施の形態では、誤り訂正ユニットは存在しない。ＳＵ２３０の中の再順序付けユニットは、シフトレジスタを構成する１ビット遅延ユニットからなる。選択遅延ユニット（図示されていない）のスイッチは、遅延ユニットのうちいくつを、与えられたメッセージパケットが通過したかを決定する。この方法で、メッセージパケットのビットが通過する遅延ユニットの数は変動し、したがって、シフトレジスタの中で経過する時間の長さは変動する。データパケットの第１ビット（常に１に設定されている）は遅延ユニット２０２に入力される。このビットの存在に応答して、新しいパケットがシステムに入力されたことを示す論理ユニットＬ２１４に信号が送られる。１ビットが入力ノード２２２からＤａｔａ  Ｖｏｒｔｅｘ（商標）受信ノード２２０までの可変長シフトレジスタを通過するのに必要な最短時間（クロック周期）が存在する。この最短時間（最少周期）Ｔｍｉｎは、シフトレジスタの各スイッチング素子が、連続して通過するライン２４０を通過するよりもバイパスライン２５０を通ってデータを通過させた時に得られる。論理素子Ｌ２１４は、ライン２５２経由でチップクロック２２４からクロック信号を送信され、遅延ユニット２０２に到達するパケットがＮＴ＋Ｔｍｉｎシフトレジスタ素子（１ビット遅延ユニット）を通過すると、パケットの第１ビットがスイッチの適切な度データパケット到達時間にノード２２０に到達するように、この信号を使用して周期ＮＴの数を計算する。論理ユニットは、適切な信号を送信してスイッチング素子２０４を設定することにより、正確な数のシフトレジスタ素子を通ってデータを送信できる。
【００１５】
図２Ｂに示されている同期化ユニットＳＵ２３０と似た設計の可変長ＦＩＦＯを図７が示す。図７に示されたＦＩＦＯは、図２Ａに示されているようにＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ２３４の中のＦＩＦＯ遅延ユニットとしても有利に使用できる。そうすることにより、１以上のＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチを含むチップは、複数のパケットの大きさのうち１つをサポートするように構成でき、そのパケットの大きさは、特定のデバイス用途用の設計パラメータとして設定できる。
【００１６】
図２Ａに示されている同期化ユニット２３０の変化形を示す図２Ｄを参照する。この新しい実施の形態の同期化ユニット２３０は、図２Ａの実施の形態にはない１つの追加のバイナリスイッチ２３８を含む。スイッチ２３８の目的は、２つのデータ受信ノードのうち１つ、ノードアレイ２２２の中のノード２２０またはノードアレイ２４４の中のノード２４６で、同期化ユニットに入力されるデータパケットが、循環Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチへの入力に同期できることである。例えば、ノード２２０が、データパケットがデータ送信サイクルの先頭に挿入されるノードであるとし、ノード２４６が、ノード２２０に入力されるデータパケットがデータ送信サイクルを通って途中まで進行するノードであるとし、パケットがＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチの入力レベルリング上に存在するとする。そうすると、論理素子Ｌ２１４は、パケットＭがライン２２６上に到達すると、１）パケットＭが、次のデータ送信サイクルの先頭で同期化されてノード２２０に入力できるか、２）Ｍが現在または次のデータ送信サイクルのいずれかの途中で同期化されてノード２４６入力できるか、２つの状況を検査する。Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチにＭを入力するどちらの方法も、スイッチの中でＭを同期化することに注意する。論理Ｌは、最も早いクロック時間にスイッチにＭを入力するようになり、それ故バイナリスイッチ２３８を設定する方法を選択する。
【００１７】
図２Ａ、図２Ｂおよび図２Ｅを参照する。図２Ａおよび図２Ｂにより示されているシステムは、制御信号がライン２３６上をデバイスＤＫに送られて、次のデータ送信サイクルの間、スイッチ２２８にパケットを入力しないようＤＫに通知すると、ＤＫが制御信号を時間内に受信して、次のパケットの送信を防ぐ役割を担う。しかし、ＤＫが、制御信号を時間内に受信しないで、次の送信サイクルで受け取らない（例えば、速いシステムクロック速度またはスイッチからＤＫの距離のために）と、ＤＫは、制御信号要求を受信する前に、１以上のパケットをスイッチ２２８に送る。図２Ｅは、パケットが直ちにはスイッチに入力不可能であることをライン２３６上の制御信号が示すと、デバイス２３２により送信されるパケットを保持するために使用される図２Ｂの各同期化ユニット２３０へのＦＩＦＯバッファ２４４の追加を示す。Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ２３４が、ライン２３６上で、制御信号をデバイスＤＫに送信すると、この信号のコピーも、対応する同期化ユニットＳＵＫの論理ユニットＬ２１４に送信される。したがって、ＤＫが、制御信号を受信する前に、ＳＵＫに１以上のパケットを送信すると、ＤＫおよびＬは、各々カウンタＶＫおよびＶＬを使用して、いくつのそのようなパケットが送信されたかについて常に知っている。Ｌが、ノードアレイ２２２に直ちには入力されないライン２１２上のパケットの到達を検知すると、ＶＬを１だけインクリメントし、ライン２１６経由でノード２４２に命令を出して、そのパケットをＦＩＦＯバッファ２４４の１つに記憶させる。デバイスＤＫも、ライン２３６上の制御信号がアクティブな送信サイクルの間、パケットを送信したことを決定するたびにＶＫを１だけインクリメントする。
【００１８】
制御信号がアクティブな間にＤＫにより送信される各パケットに関して、ＤＫは、将来のパケット入力時間においてパケットを送信せず、ＶＫを１だけデクリメントする。ＤＫにより使用されるスキームを知ると、論理ユニットＬは、開放された入力時間を使用してノード２４２に命令を出して、ＦＩＦＯバッファの中の最も古いパケットをスイッチに入力し、ＶＬを１だけデクリメントする。この方法で、バッファ２４４は過負荷とならない。このスキームを使用することにより、制御信号がアクティブな間にデバイスにより送信されるパケットは、デバイスＤＫが時間内に制御信号を受信して、パケットの送信を遅らせたか否か、すなわちパケットがデバイスＤＫ内の代わりに同期化ユニット内でバッファリングされるか否かである同じサイクルの間にスイッチにより処理される。他の実施の形態では、データは、最も左の挿入地点または途中の地点とは異なるもう１つの挿入地点のいずれかに挿入可能である。
【００１９】
同期化ユニット内には２つのタイプのシフトレジスタノードが存在する。第１のタイプは、２つの出力ポート、例えばノード２４２、２０４、２０６、および２０８を持つアクティブノードであり、第２のタイプは、１つの出力ポートのみを含むパッシブノードである。論理ユニットＬはライン２１６を通して信号を送信してアクティブノードを設定して、連続して通過するライン２４０にスイッチするか、バイパスライン２５０にスイッチする。アクティブノードは、全てのパケットが通過するまで同じ設定を維持する。論理ユニットは、入力データパケットの第１のビットがデータパケット入力時間にノード２２０に到達するようにアクティブノードを設定する。論理ユニットＬは、ＮＴの値を計算するために、多数の周期（思考時間）を必要とする。論理Ｌに関するノード２０２およびノード２４２の間に十分に多くのシフトレジスタ素子があって、必要な計算をし、シフトレジスタのアクティブな素子を設定する。
【００２０】
Ｅｘ−１、Ｅｘ−２、．．．、Ｅ２、Ｅ１、Ｅ０のラベルの付けられたｘ個のアクティブノード素子がある。図２Ｂでは、ノード２４２はＥｘ−１であり、ノード２０４はＥ２であり、ノード２０６はノードＥ１であり、ノード２０８はノードＥ０である。アクティブ素子ＥＪおよびＥＪ−１の間に２Ｊ−１個のパッシブ素子がある。２Ｊ−１＞ＰＬとなるように整数Ｊが選択される。アクティブ素子を設定する計算は、ＮＴの２進表記に基づいている。ＮＴの２進表記がｂｘ−１、ｂｘ−２、．．．、ｂ２、ｂ１、ｂ０の形式だとすると、アクティブノードＥＪは、ｂｊ＝０の時はバイパスライン２５０を通って、ｂｊ＝１の時は連続して通過するライン２４０経由でデータパケットを送信するように設定される。例えば、ノードＥ０  ２０８は、ｂ０＝０の時はバイパスライン２５０を通って、ｂ０＝１の時は連続して通過するライン２４０経由でパケットを送信するように設定され；ノードＥ１  ２０６は、ｂ１＝０の時はバイパスライン２５０を通って、ｂ１＝１の時は連続して通過するライン２４０経由でパケットを送信するように設定され；ノードＥ２  ２０８は、ｂ２＝０の時はバイパスライン２５０を通って、ｂ２＝１の時は連続して通過するライン２４０経由でパケットを送信するように設定され、最後にノードＥｘ−１  ２４２は、ｂｘ−１＝０の時はバイパスライン２５０を通って、ｂｘ−１＝１の時は連続して通過するライン２４０経由でパケットを送信するように設定される。この方法で、ノード２４２およびノード２１０の間にある｛（２ｘ−１）・（ｂｘ−１）＋（２ｘ−２）・（ｂｘ−２）＋．．．＋（２２）・ｂ２＋（２１）・ｂ１＋（２０）・ｂ０＝ＮＴ個のパッシブノードを通ってデータが送信される。
【００２１】
Ｉ．グローバルクロックを備えたシステム
この開示で前に説明した同期化は、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）を含むチップ上で実行され、パケットまたはパケットの断片の第１のビットが正確なパケット入力時間にＤａｔａ  Ｖｏｒｔｅｘ（商標）に入力されることを保証するオンチップ同期化である。この節で扱われるシステムにおいて、グローバルクロックにより実行される複数のチップの間で同期化が存在する。データスイッチチップのスタック（図１Ａの１３０および図１Ｂの１８５）の中のデータスイッチチップがほぼ同期していることをこのクロックが確かにし、それ故、そのようなスタックに入力されるパケットの断片はほぼ同期している。この同期化により、与えられたパケット入力時間におけるパケットのスケジューリングが可能になる。本発明の重要な形態は、グローバルなシステム同期化がチップ上の同期化よりも正確である必要がないことである。
【００２２】
複数のデータスイッチ１２６を通るデータを送信する入力／出力デバイス１０２を示す図１Ａおよびデータスイッチのスタック１８５を通してデータを送信するコンピュータおよびデータ記憶デバイスＤＫ１７０を示す図１Ｂを参照する。メッセージの形式のデータは、複数のパケットＰ０、Ｐ１、．．．、ＰＵの中に配置され、各パケットＰＪは、多くのパケットの断片ＰＳＪ，０、ＰＳＪ，１、．．．、ＰＳＪ，Ｖ−１に分解される。パケットの断片は誤り訂正ビットを含んでもよい。パケットの断片は、Ｖ個の制御データスイッチＣＳ０、ＣＳ１、．．．ＣＳＶ−１（図３Ａに図示されている）を通して並列に送信される。パケットの断片ＰＳＪ，０、ＰＳＪ，１、．．．、ＰＳＪ，Ｖ−１は、ＣＳＭを通過するＰＳＪ，Ｍを含む送信グループＪに属する。
【００２３】
Ｖ個のバッファユニットＢＵＫ，０、ＢＵＫ，１、．．．、ＢＵＫ，Ｖ−１に接続されたデバイスＤＫを示す図３Ａを参照する。ＤＫは、バッファＢＵＫ，Ｍに送信されるＰＳＪ，Ｍと共に、同時にパケットの断片ＰＳＪ，０、ＰＳＪ，１、．．．ＰＳＪ，Ｖ−１を送信する。それに続いて、ＢＵＫ，Ｍはパケットの断片ＰＳＪ，Ｍを制御スイッチＣＳＭに渡す。ＣＳＭは、デバイスＤ０、Ｄ１、．．．、ＤＫ−１およびデバイスＤＫ＋１、ＤＫ＋２、．．．、ＤＫ−１からもパケットを受信する。デバイスＤＫがバッファＢＵＫ，０、ＢＵＫ，１、．．．、ＢＵＫ，Ｖ−１よりかなり少ないので、バッファに同時に送信されるデータパケットの断片は、バッファに、正確に同時に到着しない可能性がある。さらに、与えられた制御スイッチに同時に送信されるパケットは、正確に同時に、制御スイッチに到着しない可能性がある。しかし、定期的な入力時間を使用するシステムにおいて、制御スイッチの適切な動作にとって重要なのは、同時に制御スイッチを通過するようにスケジューリングされた異なるデバイスからのパケットが、実際に、同時にスイッチノードアレイに入力されることである。本発明の１つの形態は、同じグループ内の制御スイッチを通過するようにスケジューリングされた全てのパケットが、たとえそれらのスイッチングシステムへの到達が時間的にわずかに歪曲していても、制御スイッチを一緒に通過することを保証することである。
【００２４】
ＤＫから制御スイッチＣＳＭへのデータパスを示す図３Ｂを参照する。デバイスＤ０、Ｄ１、．．．、ＤＮ−１は、Ｖ個の制御スイッチを通過するデータをスケジューリングする。各おおよそのメッセージ到達時間Ｊにおいて、複数のデバイスが、制御スイッチのスタックにメッセージパケットの断片を到達させる。おおよその到達時間Ｊに制御スイッチに到達するようにスケジューリングされたメッセージパケットの断片は、グループＪの中のメッセージパケットの断片として参照される。再び図３Ｂを参照すると、デバイスＤＫが、ＢＵＫ，Ｍ個のサブバッファＧＪへの木構造の中の相互接続２２６を通ってＣＳＭに行くパケットの断片のグループＪを送信する。さらに、サブバッファＧＪは、より小さなバッファに分割される。図３Ｂで、４つのバッファ３０８、３１０、３１２、および３１４に再分割される。他の実施の形態では、ＧＪは、４つより多いか少ないバッファに分割されてもよい。サブバッファ３０８が最初にいっぱいになり、次にサブバッファ３１０、続いてサブバッファ３１２、そして最後にサブバッファ３１４が続く。
【００２５】
ＧＪがＳ個のサブバッファＳＢ０、ＳＢ１、．．．、ＳＢＳ−１に再分割される図３Ｃを参照する。サブバッファは、ＳＢ０  ３０８からいっぱいになり、次にＳＢ１  ３１０、ＳＢ２  ３１２と続いて、最後にＳＢＳ−１  ３１６がいっぱいになる。グループＪのパケットの断片がＧＪからＣＳＭに送信されると、データは、受信された順に送信され、ＳＢ０の中のデータが最初に、続いてＳＢ１の中のデータ、さらに続いて、最後にＳＢＳ−１中のデータが送信される。
【００２６】
チップＣＳＭ上のＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチは、グループＪの全てのパケットの断片を同時に受信せねばならない。時間間隔［ａ，ｂ］で同期化ユニットに到達するパケットの断片が整列されて、グループＪの入力時間にＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチに入力されるような時間間隔［ａ，ｂ］が存在する。ＣＳＭが時間ｔにおいてＧＪからのデータを要求すると、時間間隔［ｔ＋δ−ε，ｔ＋δ＋ε］内にＧＪからのデータが同期化ユニットＳＵＫに到達するような正の数εおよびδが存在する。設計パラメータは、間隔［ａ，ｂ］が間隔［ｔ＋δ−ε，ｔ＋δ＋ε］よりも長いように設定する。メッセージパケット入力イベントＪに対応して、制御スタックのスタックの中の各スイッチは、適切な時間にデータを要求して、間隔［ｔ＋δ−ε，ｔ＋δ＋ε］が間隔［ａ，ｂ］の部分集合となるようなおおよその時間ｔ＝（ａ＋ｂ）／２に到達するので、全てのグループＪサブパケットは、スイッチを制御するクロックの同じ周期で、スイッチの入力ポートに到達する。
【００２７】
組み入れられた特許、特許文献８、特許文献１０、特許文献１１、特許文献１２、特許文献１４、および特許文献１７に記載されたシステムのようなシステムでは、各制御スイッチＣＳ０、ＣＳ１、．．．、ＣＳＶ−１は、データを送信先のグループに送信する。Ｔがスイッチのスタックの送信先デバイスだとすると、スイッチＣＳ０、ＣＳ１、．．．、ＣＳＶ−１のスタックの中のスイッチは、Ｔにデータを送信する。データサブパケット送信時間において、送信先Ｔは、スタックの中の各スイッチからデータを受信してもよい。スタックの中のスイッチが完全には同期化される必要はないので、スタックの中のスイッチの１つからＴに到達するデータは、スタックの中のもう１つのスイッチにとはわずかに異なる時間に到達してもよい。この理由のため、第１の実施の形態では、パケットが、重なる時間間隔で到達した時、それらが同じパケットのサブパケットであるように、１つのサブパケット送信時間の終わりと次のサブパケット送信時間の始まりの間に時間間隔を設ける。第２の実施の形態では、グループＪの中の各サブパケットは、それらのサブパケットが正確に１つのパケットに再構成できるように、ヘッダの中に整数Ｊを含む。
【００２８】
遅延ユニットの代わりのＦＩＦＯバッファを使用する同期化ユニットの代わりの実施の形態を示す図４を参照する。図４に示されているように、各同期化ユニットＳＵ２３０は、Ｎがシステム設計パラメータであるＮ個のバッファＢ０、Ｂ１、．．．、ＢＮ−１を含む。各ＦＩＦＯバッファＢＫは、１つのメッセージパケットを保持し、複数のサブバッファから構成される。図示の目的のため、４つのサブバッファが示されている。メッセージパケットＭは、ライン２２６を通って同期化ユニットＳＵ２３０に入力され、（ある実施の形態では）論理ユニットＬ４１４に入力される前に、誤り訂正ユニットＥＣ２６０により処理される。Ｌは、どのバッファにＭを入力するか、ノードアレイ２２２のライン４１８およびノード２２０経由でＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチの中に、各バッファの中のパケットをいつ入力するかを決定する。
【００２９】
システム２２８の中の各同期化ユニットＳＵ２３０は、システムクロック２２４により制御される入力時間に、Ｂ０、Ｂ１、．．．、ＢＮ−１の順に、ＦＩＦＯバッファの組みから、ラウンドロビン方法で、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチの中へメッセージパケットを入力する。メッセージパケットは、以下の方法で、Ｂ０、Ｂ１、．．．、ＢＮ−１の順にＦＩＦＯバッファの中へ入力される。論理ユニットＬが、バッファＢ０からスイッチの中にパケットを入力するために使用されるデータ送信間隔内でメッセージパケットＭを受信すると。ＭはＢＮ−１に入力される。一般的に、バッファＢＫの中のパケットがスイッチに入力される間隔の間に受信されるメッセージパケットは、ＦＩＦＯバッファＢＫ−１の中に配置される。１組のバッファＢＫからスイッチにパケットを送信するために予約された間隔の間にＬにどのパケットも入力されないと、ＢＫ−１は空、すなわち、第１のサブバッファの第１のビットが０になる。与えられた入力間隔の間に１組のデバイスＤ２３２によりシステム２２８に入力される全てのパケットがグループとしてＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチに入力されるのを確かにするために、このスキームが使用される。各ＦＩＦＯバッファが複数のサブバッファに分割される。１つのパケットは複数のサブパケットに分割される。１つのパケットは、各サブパケットがサブバッファにぴったり収まることによりＦＩＦＯバッファにぴったり収まる。したがって、第１のサブバッファに含まれるパケットの一部は、他のバッファが入力データでいっぱいになる前に、前もってスイッチに入力できる。
【００３０】
本特許の技術は、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチを含むシステムを含む多くのシステムに便利に組み入れ可能である。図１Ｃは、組み入れられた特許、特許文献１３の技術と共に本発明の技術を組み入れる方法を示している。図１Ｃに示されているデバイスは、組み入れられた特許、特許文献８、特許文献１０、特許文献１１、特許文献１２、特許文献１４、特許文献１６、および特許文献１７に記載されているシステムを含む多くのシステム内で使用できる。
【００３１】
II．グローバルクロックを持たないシステム
このクラスのシステムはチップレベルの同期化を使用するけれども、チップ間の同期化は設けない。これらのシステムはグローバルクロックを持たない。これらのシステムとグローバルクロックを持つシステムとの重要な違いは、定期的なパケット送信時間がないことである。しかし、パケット送信およびパケット到達の連続順は制御されている。これらのシステムでは、図１Ａのスタック１３０の中のチップ間で同期化は存在せず、図１Ｂのスタック１８５の中のチップ間の同期化も存在しない。
【００３２】
コンピューティングシステムを示す図１Ｂを参照する。デバイスＤＲが、デバイスＤＳからの複数のパケットからなる長いメッセージを受信する場合を考える。デバイスＤＲが、与えられた時間に、ライン１７８を通って制御スイッチスタックＳからＮＭ個のメッセージのみを受信できるように整数ＮＭが存在する。デバイスＤＲは、Ｓを通過するデータのＮＭ個の要求より多くを持つことを許可されていない。ＤＲが、メッセージＭを受信する取得可能なデータパスＤＰ１７８を持つとすぐに、デバイスＤＲが、非制御スイッチＵを通って要求パケットＲＰをＤＳに送信する。ＲＰはデバイスＤＲの入力データパスＤＰを通ってメッセージＭを送信することを要求する。Ｖ個の断片ＳＧＫ，０、ＳＧＫ，１、．．．、ＳＧＫ，Ｖ−１から成る各パケットＰＫと共にＮＰ個のパケット、Ｐ０、Ｐ１、．．．、ＰＮＰ１の中で、送信デバイスＤＳが受信デバイスＤＲにメッセージＭを送信する。各デバイスがＮＭ個の入力データパスを含む実施の形態では、スイッチスタックＳが（ＮＭ・Ｖ）個のスイッチを含む。ＳＷ０，０、ＳＷ０，１、．．．、ＳＷ０，Ｖ−１はデータパス０内でデータを運び；ＳＷ１，０、ＳＷ１，１、．．．、ＳＷ１，Ｖ−１はデータパス１内でデータを運び；などで、ＳＷＮＭ−１，０、ＳＷＮＭ−１，１、．．．、ＳＷＮＭ−１，Ｖ−１はデータパスＮＭ−１内でデータを運ぶ。パケットＰＫは、断片ＳＧＫ，ＬがＳのスイッチＳＷＤＰ，Ｌを通って送信されると共に、スイッチスタックＳを通ってパケットＰＫが送信される。各断片は、データの存在を示す１に設定された先頭ビットを持つヘッダを持ち、Ｒ（ＤＲのアドレス）の２進表現、およびメッセージを受信するＤＲにより使用される入力データパスＤＰ１７８に関する識別子が続く。ヘッダは、送信先アドレスＲの第２のコピー、誤り訂正ビット、メッセージ内のパケットの数、メッセージ識別子、および有用と考えられる他の情報を含む可能性のある他の情報を含んでもよい。要求パケットＲＰの受信に応答して、デバイスＤＳは、Ｄｓが空いているメッセージ送信ライン１７６を持つとすぐにデバイスＤＳがＭを送信する。デバイスＤＳは、スイッチスタック１８５を通ってパケットを送信する。各パケットの断片のヘッダは、Ｒのバイナリアドレスと入力データパスＤＰを示す識別子とを含む。
【００３３】
グローバルクロックを持たないシステムの１つの重要な形態は、制御スイッチが同期していないことである。パケットＫ＋１の断片がスタックＳの異なるスイッチを通過すると、パケットＫの断片はスタックＳのスイッチを同時に通過する。したがって、断片は、メッセージＭのパケットＰＫを再構成するために整列させられる必要がある。この再整列は難しくなく、入力データパスＤＰ上のパケットをＶ個のビンに構成することにより達成される。与えられたデータパケットＰＫのセグメントが連続順に到達する間、与えられたビンに到達する２つの連続した断片の間に時間間隔が存在してもよい。パケットＰ０のＬ番目の断片ＳＧ０，ＬがビンＢＩＮＤＰ，Ｌに到達した時、その断片はＢＩＮＤＰ，ＬのＮＰ−１位置に配置される。
【００３４】
１つのデバイスからもう１つのデバイスに要求パケットが到達する最短時間がＴ１であって、１つのデバイスからもう１つのデバイスにスケジューリングされたパケットが到達する最短時間がＴ２であると、Ｔ３＝Ｔ１＋Ｔ２は、ＤＲが要求を開始した後、パケットの第１のビットがＤＲに到達できる最短時間である。したがって、ＤＲは、ＤＰ上の残りの現在のパケットを受信するのに必要な時間がＴ３未満であると、ＤＰ上で現在データを受信している間、もう１つのパケットが入力パスＩＰに送信されるよう安全に要求できる。ＤＲはこのタイミングプロセスを有利に使用して、バックログにさらにデータ要求がある時に、入力データの使用を最大にする。
【００３５】
デバイスＤＳが、制御スイッチスタックを通ってデバイスＤＲにＮＰ個のパケットからなるメッセージを送信する場合を考える。このタスクを達成するために、デバイスＤＳは、デバイスＤＲがＮＰ個のパケットのメッセージを要求する要求をＤＲに送信する。デバイスＤＲが使用可能な入力データパスＤＰ１７８を持つ時、ＤＲは、メッセージパスＤＰを通して送信されるＭを要求する。次に、この手順は以下の段落で説明されるように実行される。
【００３６】
データスイッチスタック１３０の中のチップ間に同期化が存在せず、メッセージがデータスイッチスタックを通って送信されるスケジューリングされた時間が存在しない通信システムを示す図１Ｄを参照する。パケットが繋がった形のメッセージＭが、入出力デバイスＩＯＤＳのシステムに到達し、Ｍの送信先が入出力デバイスＩＯＤＲである時、ＩＯＤＳは送信要求パケットをＩＯＤＲに送信する。送信要求パケットは、パケットの長さ、パケットの優先度、受信入出力デバイスの位置Ｒ、パケット識別子、および可能ならば他の有用な情報を含んでもよいメッセージパケット情報を含む。ＩＯＤＲは、種々の入出力デバイスから受信した全ての送信要求パケットを記憶する論理ユニット（図示されていない）を持つ。ＩＯＤＲが、パケットを受信するデータスイッチスタック１３０からの空いている入力線を持つ時、（いつメッセージが受信されたかおよびメッセージの優先度を含む多くの要素を考慮するアルゴリズムに基づいて）ＩＯＤＲはＩＯＤＳが空いている入力データパスＤＰを通ってパケットを送信することを要求する。
【００３７】
ネットワークインタフェースカード
各々プロセッサＰＫ５２０およびそれに結合されたメモリＭＫ５３０から成るコンピューティングデバイスとして示されるデバイスの集まりを示す図５を参照する。プロセッサはネットワークインタフェースカード（ＮＩＣ）５１０により相互接続され、スケジューリングされていないＤａｔａ  ＶｏｒｔｅｘスイッチＵ５４０およびスケジューリングされたＤａｔａ  Ｖｏｒｔｅｘスイッチ５５０から成るＤａｔａ  Ｖｏｒｔｅｘ（商標）ネットワークを介して互いに非同期式で通信する。ＮＩＣの責任は、コンピューティングデバイスに透過な方法でこの通信を調整することである。
【００３８】
プロセッサＰＪは、ライン５１４経由で要求パケットをプロセッサに結合されたＮＩＣＪ５１０に送信することにより、もう１つのプロセッサＰＫからのデータを要求する。ＰＪはそのメモリＭＪ５３０の中のどこにデータを記憶するかも指定できる。次に、ＮＩＣＪは要求を適切なフォーマットに変換し、ライン５０６、スケジューリングされていないＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ５４０、およびライン５０８経由で送信する。
【００３９】
第１の実施の形態では、データパケットのスケジューリングが使用されるタイプのＤａｔａ  Ｖｏｒｔｅｘ（商標）システムでは、各ＮＩＣが、結合されたプロセッサの状態を常に知っていて、したがって、Ｉ／Ｏライン、メモリ、およびタイムスロットの入手可能性を知っている。この方法で、ＮＩＣＫは独立してＮＩＣＪと交渉して、要求を満たすタイムスロットおよびパスを選択する。選択された時間の前に、ＮＩＣＫは、ライン５０２、スケジューリングされたＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ５５０、およびライン５０４経由でＮＩＣＪに要求データを送信する。データを受信すると、ＮＩＣＪは、ＰＪと共に独立してあらかじめ決められた時間に、ライン５１２および５１６経由でＭＪにそのデータを送信する；これはＮＩＣＪの中でデータを第１にバッファリングする必要はあってもなくともよい。代わりに、図５に示されているように、ライン５２２経由でプロセッサメモリＭＪにデータを直接送信してもよい。
【００４０】
第２の実施の形態では、データパケットのスケジューリングが使用されず、タイムスロットスケジューリングが使用されず、ＮＩＣＪおよびＮＩＣＫの間のネゴシエーションが発生しないタイプのＤａｔａ  Ｖｏｒｔｅｘ（商標）システムである。代わりに、ＮＩＣＪは、ライン５０６、スケジューリングされていないＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ５４０、およびライン５０８経由でＮＩＣＫに可能な限り早いデータの送信を要求する要求パケットを送信する。要求パケットが、要求されたデータが受信されるかタイムアウト値を超えるまで要求されたデータに予約されるＮＩＣＪに入力ライン５０４も指定する。ＮＩＣＫは、タイムアウトに基づいて同意した値を超えるまで、要求を受信し、その要求を他の要求と共に優先順位をつけ、ライン５０２、スケジューリングされたＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ５５０、および指定されたライン５０４経由でできるだけ早くＮＩＣＪにデータを送信する。前記のように、ＮＩＣＪは、ライン５２２経由で直接的に、またはライン５１２および５１６経由で間接的にＰＪと共に独立してあらかじめ決められた時間に、データをＭＪに送信する。
【００４１】
ＤＡＴＡ  ＶＯＲＴＥＸ（商標）がチップのポート速度とは異なる速度で動作できる代わりの実施の形態
この節で説明されている実施の形態は、階段Ｄａｔａ  Ｖｏｒｔｅｘ（商標）ネットワークを含むチップへと同様に、円形Ｄａｔａ  Ｖｏｒｔｅｘ（商標）ネットワークを含むチップへも応用できる。この実施の形態は、チップへの入力レートがＤａｔａ  Ｖｏｒｔｅｘ（商標）入力ポートへの入力レートと等しくないチップへと同様に、チップへの入力レートがＤａｔａ  Ｖｏｒｔｅｘ（商標）入力ポートへの入力レートと等しいチップにも応用可能である。この実施の形態は、発信元に、発信元が一時的にネットワークチップへの送信を停止する要求する制御メッセージをチップが送信した後で、追加のパケットがネットワークチップに送信できる時間遅延が存在するシステム内で有用である。
【００４２】
Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチングコア６３０を含む通信チップ６２０を示す図６Ａを参照する。通信チップ６２０にデータを送信するよう位置された複数のＩ／Ｏデバイス６１０が存在する。１つのそのようなＩ／Ｏデバイス６１０は図６Ａに示されている。また図６Ａに示されているのは、入力ポートからデータを受信し、上記データを他のチップのコンポーネントに渡すいくつかの実施の形態で使用されるデータ成形モジュール６０２である。モジュール６０２はシリアライゼーション−デシリアライゼーション（ＳＥＲＤＥＳ）モジュールである。データは、データ成形モジュールからライン６１２経由で、複数のデータ整列ユニット６５０を含むデータタイミングおよび記憶モジュール６４０に運ばれる。データは、データ成形ユニット６０２から、枝６１２およびスイッチの頂点６８０を含む木を通ってデータ整列ユニット６５０に渡される。１つの単純な実施の形態では、ラウンドロビンの方法でデータパケットが整列ユニットに送信される方法のような頂点のスイッチである。１つのデータパケットが、整列ユニット６５０の１つから、枝６１８およびスイッチングノード６８０を含むもう１つのツリーを通ってＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチモジュールの入力ポートの１つに渡される。単純な例では、データは、整列ユニットからＤａｔａ  Ｖｏｒｔｅｘ（商標）にラウンドロビンの方法で送られる。ある実施の形態では、ライン６１２を通るデータレートはライン６１８を通るデータレートと等しくない。制御信号がオフにされるまで追加のパケットを送信すべきでないと入力源に知らせる制御信号をチップが使用した後、複数の整列ユニット６５０は、通信チップ６２０に送られる任意の追加のパケットをバッファリングするために使用される。
【００４３】
ライン６１８を通るデータレートがＤａｔａ  Ｖｏｒｔｅｘ（商標）モジュールを通るデータレートに同期化され、ライン６１２内のデータレートがデータ成形ユニットの出力データレートに同期化されるシステムにおける使用に適した図６Ｂを参照する。１つの重要な用途では、ライン６１８を通るデータレートがライン６１２を通るデータレートを超える。図６Ｂは整列ユニット６５０を示す。整列ユニット６５０は、木構造で接続された多くのシフトレジスタからなる。図６Ｂに示されたシステム例では、整列ユニット内のシフトレジスタの数は４つである。データ入力木の中のスイッチノード６８４は、パケットの第１の部分がシフトレジスタ６５２に入力され；パケットの次の部分がシフトレジスタ６５４に入力され；パケットの次の部分がシフトレジスタ６５６に入力され；パケットの最後がシフトレジスタ６５８に入力されるラウンドロビンの方法で、データがシフトレジスタに入力されるように動作する。データは与えられたシフトレジスタから同時に出入りしない。シフトレジスタ６５２がいっぱいの時、パケットの第１のビットはセル６６２に入り、次のステップで、パケットのビットはシフトレジスタ６５４の中へシフトを開始する。ＤＶ６３０の上層部からモジュール６５０へ制御信号データパス（図示されていない）が存在する。与えられたＤＶ入力時間Ｔにおいて停止制御信号がなく、セル６６２の中に１つあると、データはシフトレジスタ６５２からＤＶ６３０にシフトを開始する。シフトレジスタ６５４はシフトレジスタ６５２より短い。シフトレジスタ６５４は、シフトレジスタ６５２からの排出にかかった時間の長さを書き込む。シフトレジスタ６５６は、シフトレジスタ６５４からの排出にかかった時間の長さを書き込む。シフトレジスタ６５８は、シフトレジスタ６５６からの排出にかかった時間の長さを書き込む。したがって、セル６６２の中に１つあり、データがシフトしてＤＶに出されると、パケット全体をチップの入力ポートからＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチモジュールＤＶ６３０に転送することが成功する。図６Ｂに描かれた実施の形態では、シフトレジスタは、データがシフトして入ってくる時はライン６１２のスピードで、データがシフトして出て行く時はライン６１８のスピードで動作する。
【００４４】
図６Ｃに描かれている代わりの実施の形態では、ライン６１２を移動するデータは、ライン６１２のデータレートでシフトされてレジスタ６７２に入っていく。データは、レジスタ６５２からライン６１８のデータレートでシフトされてライン６１８に出て行き、ライン６１２を通るデータレートはライン６１８を通るデータレートと必ずしも等しい必要はない。レジスタ６７２がいっぱいの時、データは、１クロック周期で、ライン６９２経由でシフトレジスタ６５２の中に転送される。
【００４５】
整列ユニット内のシフトレジスタ内での使用に適した可変長ＦＩＦＯを示す図７を参照する。このＦＩＦＯは、図２Ｂで示されたＦＩＦＯと似た構成である。ＦＩＦＯは２つのタイプのセルから構成されている。１データ入力ポートおよび１データ出力ポートを備えた第１のタイプのセルは１ビットシフトレジスタである。第２のタイプのセル（例えば、セル７０１、７０２、７０４）は、１データ入力ポートおよび２データ出力ポートを備えたスイッチセルであり、出力を２つのセルのうちどちらか１つに送信できる単純なスイッチと結合した１ビットシフトレジスタとして動作する。スイッチセルのスイッチは、長さ制御ユニットＬＣ７７２によりスイッチに送信される１ビットにより設定される。ＬＣユニットはペイロード長ＬのワードＷを受信し、Ｌは可変長ＦＩＦＯユニットのスイッチセルの数である。ＬＣは、Ｗの最下位ペイロードビットをセル７０１に、次のビットをセル７０２に、その次のビットをセル７０４に、等、送信する。
【００４６】
各々異なるパケット長を使用する複数のシステムは、図６ＢのＤａｔａ  Ｖｏｒｔｅｘ（商標）の長さおよびシフトレジスタの長さを設定することにより、同じＤａｔａ  Ｖｏｒｔｅｘ（商標）チップを使用できる。これらのシフトレジスタの長さは、ワードＷをＬＣユニットに入力することにより制御される。Ｗが、０に設定された最下位のペイロードビットを持つと、セル７０１はライン７４０を通してデータを送信する。Ｗが、０に設定された最下位のペイロードビットを持つと、セル７０１はライン７０５を通してデータを送信する。ライン７５０を通してデータを送信することにより、ＦＩＦＯ７３０が１ビット短くなる。同様に、１つのデータをセル７０２に送信することにより、ＦＩＦＯが２ビット短くなり、１つのデータをセル７０４に送信することにより、ＦＩＦＯが４ビット短くなる。この方法で、ワードＷは整数Ｉの２進表現であり、Ｉは、シフトレジスタ７３０から削除されたビット数である。したがって利用モジュール７３０は、Ｄａｔａ  Ｖｏｒｔｅｘ（商標）を含むチップを、種々のパケット長をサポートするシステム内で有利に使用できるようにする。
【図面の簡単な説明】
【００４７】
【図１Ａ】組み入れられた特許文献８、特許文献１０、および特許文献１２に記載されたインターネットプロトコルルータを示す概略ブロック図。このルータは、本発明の技術から全て利益を得ることのできる非制御スイッチ１２２、１２４、１４２、および１４６、ならびに制御スイッチ１２６のスタックを利用する。
【図１Ｂ】組み入れられた特許文献１４、特許文献１６、および特許文献１７に記載された並列コンピューティングおよびデータ記憶システムを示す概略ブロック図。このシステムは、本発明の技術から全て利益を得ることのできる非制御スイッチ１６５および制御スイッチ１８５を利用する。
【図１Ｃ】自己制御Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチを示す概略ブロック図。スイッチＤＳ１８６は、同期化ユニットＳＵ１８４の集まりを通って有力論理ユニットＩＬからデータを受信する。同期化ユニットＳＵは本発明の１つの形態である。
【図１Ｄ】入出力デバイス１０２およびデータスイッチスタック１３０の間の同期化を備えず、データスイッチスタックの中の制御データチップ１２６間の同期化も備えないインターネットプロトコルルータを示す概略ブロック図。
【図２Ａ】同期化ユニット２３０を通してＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ２３４にデータを送信するデバイス２３２のグループを示す概略ブロック図。これらの同期化ユニットは本発明の第１の形態を表す。
【図２Ｂ】ライン２２６上の外部信号源からデータを受信し、上位レベルのＤａｔａ  Ｖｏｒｔｅｘ（商標）ノードアレイ２２２の中のノード２２０へデータを送信するよう位置された同期化ユニットを示すブロック図。
【図２Ｃ】ライン２１８上の複数の同期化ユニットからデータを受信し、他のノードアレイからデータを受信し、他のＤａｔａ  Ｖｏｒｔｅｘ（商標）ノードアレイにデータを送信するよう位置されたＤａｔａ  Ｖｏｒｔｅｘ（商標）ノードアレイを示す図。
【図２Ｄ】ライン２２６上の外部信号源からデータパケットを受信し、第１の上位レベルＤａｔａ  Ｖｏｒｔｅｘ（商標）ノードアレイの中のノードｎ１または第２の上位レベルＤａｔａ  Ｖｏｒｔｅｘ（商標）ノードアレイの中のノードｎ２のどちらかに上記パケットを送信するよう位置された同期化ユニット２３０を示すブロック図
【図２Ｅ】スイッチからの遮断制御信号を受信した入力デバイスによりＤａｔａ  Ｖｏｒｔｅｘ（商標）スイッチに送信されたが、時間内には受け取らないデータパケットを保持するために使用される同期化ユニット２３０の中の１組のＦＩＦＯバッファ２４４を示すブロック図。
【図３Ａ】デバイス２３２から制御スイッチシステム２２８の中の同期化ユニットにパケットのグループを送信するために使用されるバッファユニット３０２の使用を示す概略ブロック図。
【図３Ｂ】外部デバイス２３２からデータを受信し、同期化ユニットＳＵ２３０にデータを送信するよう位置されたバッファユニットＢＵ３０２を示すブロック図。
【図３Ｃ】バッファユニットのサブバッファを示すブロック図
【図４】上位レベルのＤａｔａ  Ｖｏｒｔｅｘ（商標）ノードアレイＮＡ２２２の中のノード２２０の中への入力メッセージパケットの入力を同期化するために使用される複数のＦＩＦＯバッファの組４１０を使用する同期化ユニット２３０を示すブロック図。
【図５】デバイスの既存のシステムをＤａｔａ  Ｖｏｒｔｅｘ（商標）ネットワークに接続するネットワークインタフェースカードの使用を示すブロック図。
【図６Ａ】入出力デバイスおよびＤａｔａ  Ｖｏｒｔｅｘ（商標）が異なるクロック速度で動作している時でもＤａｔａ  Ｖｏｒｔｅｘ（商標）にデータパケットを入力する効率的方法を示すブロック図。
【図６Ｂ】木構造で接続された複数のシフトレジスタからなる整列ユニットを示すブロック図。
【図６Ｃ】整列ユニット内の第２のシフトレジスタおよび第１のシフトレジスタにデータを転送する第２のシフトレジスタを示すブロック図。
【図７】図６Ａに示されている整列ユニット内およびＤａｔａ  Ｖｏｒｔｅｘ（商標）ＦＩＦＯ内のシフトレジスタを含む多くの組み入れられたシフトレジスタの代わりとして使用できるシフトレジスタを示すブロック図。
【符号の説明】
【００４８】
１０２  入力／出力デバイス
１０４  入出力デバイス
１２２、１２４  非制御スイッチ
１２６  制御データスイッチ
１３０  データスイッチスタック
１４２、１４６、１６５  非制御スイッチ
１７０  コンピューティングまたはデータ記憶デバイス
１７６  メッセージ送信ライン
１７８  入力データパス
１８４  同期化ユニット
１８５  データスイッチのスタック
１８６  スイッチ
２０２  遅延ユニット（ノード）
２０４  スイッチング素子（ノード）
２０６、２０８、２１０  ノード
２１２  ライン
２１４  論理素子（論理ユニット）
２１６、２１８  ライン
２２０  ノード
２２２  ノードアレイ
２２４  チップクロック（システムクロック）
２２６  ライン
２２８  制御スイッチシステム
２３０  同期化ユニット
２３２  デバイス
２３４  Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ
２３６  ライン
２３８  バイナリスイッチ
２４０  ライン
２４２  ノード
２４４  ＦＩＦＯバッファ
２４６  ノード
２５０  バイパスライン
２５２  ライン
２６０  誤り訂正ユニット
３０２  バッファユニット
３０８、３１０、３１２、３１４、３１６  サブバッファ
４１０  ＦＩＦＯバッファの組
４１４  論理ユニット
４１８、５０２、５０４、５０６、５０８  ライン
５１０  ネットワークインタフェースカード（ＮＩＣ）
５１２、５１４、５１６  ライン
５２０  プロセッサ
５２２  ライン
５３０  メモリ
５５０  Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチ
６０２  データ成形モジュール（データ成形ユニット）
６１０  Ｉ／Ｏデバイス
６１２、６１８  ライン（枝）
６２０  通信チップ
６３０  Ｄａｔａ  Ｖｏｒｔｅｘ（商標）スイッチングコア
６４０  データタイミングおよび記憶モジュール
６５０  データ成形ユニット（整列ユニット）
６５２、６５４、６５６、６５８  シフトレジスタ
６６２  セル
６７２  レジスタ
６８０  スイッチの頂点（スイッチングノード）
６８４  スイッチノード
６９２  ライン
７０１、７０２、７０４  セル
７３０  シフトレジスタ
７４０、７５０  ライン
７７２  長さ制御ユニット
【図１Ａ】
2006114028.tif 000003
【図１Ｂ】
2006114028.tif 000004
【図１Ｃ】
2006114028.tif 000005
【図１Ｄ】
2006114028.tif 000006
【図２Ａ】
2006114028.tif 000007
【図２Ｂ】
2006114028.tif 000008
【図２Ｃ】
2006114028.tif 000009
【図２Ｄ】
2006114028.tif 000010
【図２Ｅ】
2006114028.tif 000011
【図３Ａ】
2006114028.tif 000012
【図３Ｂ】
2006114028.tif 000013
【図３Ｃ】
2006114028.tif 000014
【図４】
2006114028.tif 000015
【図５】
2006114028.tif 000016
【図６Ａ】
2006114028.tif 000017
【図６Ｂ】
2006114028.tif 000018
【図６Ｃ】
2006114028.tif 000019
【図７】
2006114028.tif 000020
【外国語明細書】
2006114028.tif 000021
2006114028.tif 000022
2006114028.tif 000023
2006114028.tif 000024
2006114028.tif 000025
2006114028.tif 000026
2006114028.tif 000027
2006114028.tif 000028
2006114028.tif 000029
2006114028.tif 000030
2006114028.tif 000031
2006114028.tif 000032
2006114028.tif 000033
2006114028.tif 000034
2006114028.tif 000035
2006114028.tif 000036
2006114028.tif 000037
2006114028.tif 000038
2006114028.tif 000039
2006114028.tif 000040
2006114028.tif 000041
2006114028.tif 000042
2006114028.tif 000043
2006114028.tif 000044
2006114028.tif 000045
2006114028.tif 000046
2006114028.tif 000047
2006114028.tif 000048
2006114028.tif 000049
2006114028.tif 000050
2006114028.tif 000051
2006114028.tif 000052
2006114028.tif 000053
2006114028.tif 000054
2006114028.tif 000055
2006114028.tif 000056
2006114028.tif 000057
2006114028.tif 000058
2006114028.tif 000059
2006114028.tif 000060
2006114028.tif 000061
2006114028.tif 000062
2006114028.tif 000063
2006114028.tif 000064
2006114028.tif 000065