(57)【要約】      （修正有）【課題】通信システムの複数のモジュール間の相互接続用バッファ付きクロスバー・スイッチを提供する。【解決手段】データ・モジュール間でのデータ転送を実現する。少なくとも２個のクロスバー・スイッチが使用され、各クロスバー・スイッチの入力ノードおよび出力ノードが、対応するデータ・モジュールに結合される。各クロスバー・スイッチは、各入力ノードにおける入力バッファと、スイッチ・ファブリックの各クロスポイントにおけるクロスポイント・バッファと、各出力ノードにおける出力バッファとを含む。入力バッファは、第１のスケジューリング・アルゴリズムに従って、入力バッファからデータ・パケットを読み取るアービタを有する。アービタは、第２のスケジューリング・アルゴリズムに従って、クロスポイント・バッファ・キューからデータ・パケットを読み取る。【選択図】図１
2010259045.tif 000002
【特許請求の範囲】
【請求項１】
データ・モジュール間でデータを転送する装置であって、前記データ・モジュールのそれぞれが、データ処理モジュールおよびデータ記憶モジュールの少なくとも一方であり、前記装置が、
それぞれの入力ノードおよび出力ノードが、前記データ・モジュールの対応するものに結合された少なくとも１つのクロスバー・スイッチであって、ｉ個目のクロスバー・スイッチが、Ｎｉ−入力ノード×Ｍｉ−出力ノードのスイッチ・ファブリックを有し、ＮｉおよびＭｉはそれぞれ、１よりも大きい正の整数である、少なくとも１つのクロスバー・スイッチを備え、各クロスバー・スイッチが、
第１のスケジューリング・アルゴリズムに従って、各入力バッファからデータ・パケットを読み取るように構成された入力アービタを有する、各入力ノードにおける入力バッファと、
前記スイッチ・ファブリックの各クロスポイントにおけるクロスポイント・バッファであって、キューを備え、前記キューは、第２のスケジューリング・アルゴリズムに従って、前記クロスポイント・バッファ・キューからデータ・パケットを読み取るように構成された出力アービタを有するクロスポイント・バッファと、
１つまたは複数の対応するクロスポイント・バッファから供給されたデータ・パケットのセグメントを受け取るように構成された出力ノードとを備える、装置。
【請求項２】
各出力ノードにおける出力バッファをさらに備え、前記出力バッファが、１つまたは複数の対応するクロスポイント・バッファから供給されたデータ・パケットのセグメントを記憶するように構成される、請求項１に記載の発明。
【請求項３】
各入力ノードにおける前記入力バッファが、先入れ先出し（ＦＩＦＯ）バッファ、仮想出力キュー（ＶＯＱ）、または割込み先出しバッファ（ＰＩＦＯ）のうちの１つを備える、請求項１に記載の発明。
【請求項４】
各クロスポイント・バッファ・キューについて、前記キューの深さが、前記少なくとも１つのクロスバー・スイッチのうちの１つを介したデータ転送の往復時間に従って変動する、請求項１に記載の発明。
【請求項５】
前記第１のスケジューリング・アルゴリズム、および前記第２のスケジューリング・アルゴリズムの少なくとも一方が、ラウンドロビン・スケジューリング・アルゴリズムを使用する、請求項１に記載の発明。
【請求項６】
前記第１のスケジューリング・アルゴリズム、および前記第２のスケジューリング・アルゴリズムの少なくとも一方の前記ラウンドロビン・スケジューリング・アルゴリズムが、１つまたは複数のデータ処理モジュールについて優先配送を行う、請求項５に記載の発明。
【請求項７】
データ記憶モジュールがメモリ内の位置の順次アドレッシングを使用する場合、前記少なくとも１つのクロスバー・スイッチを介して前記データを送る前に、メモリ内の前記位置のアドレスがスクランブルされる、請求項１に記載の発明。
【請求項８】
少なくとも１つのＮｉ−入力ノード×Ｍｉ−出力ノード・スイッチ・ファブリックが、Ｍｉ個の相互結合されたＮｉ−ｔｏ−１マルチプレクサを備える、請求項１に記載の発明。
【請求項９】
前記入力バッファに供給される前記データ・パケットが、同じ長さのセルに分割される、請求項１に記載の発明。
【請求項１０】
前記入力バッファが、先入れ先出し（ＦＩＦＯ）バッファである、請求項９に記載の発明。
【請求項１１】
前記装置が、少なくとも１対のクロスバー・スイッチを備え、第１のクロスバー・スイッチが、Ｎ−入力ノード×Ｍ−出力ノードのスイッチ・ファブリックを有し、第２のクロスバー・スイッチが、Ｍ−入力ノード×Ｎ−出力ノードのスイッチ・ファブリックを有し、ＮおよびＭはそれぞれ、１以上の正の整数である、請求項１に記載の発明。
【請求項１２】
前記第１のクロスバー・スイッチが、第１の群のデータ・モジュールから、第２の群のデータ・モジュールにデータを送り、前記第２のクロスバー・スイッチが、前記第２の群のデータ・モジュールから、前記第１の群のデータ・モジュールにデータを送る、請求項１１に記載の発明。
【請求項１３】
前記第１の群のデータ・モジュールのそれぞれが、データ処理モジュールであり、前記第２の群のデータ・モジュールのそれぞれが、データ記憶モジュールである、請求項１２に記載の発明。
【請求項１４】
前記装置が、モノリシック集積回路チップ内に実装される、請求項１に記載の発明。
【請求項１５】
前記装置が、少なくとも５つのクロスバー・スイッチ、すなわち、データ処理モジュールからデータ記憶モジュールにアドレス・データを転送する第１のクロスバー・スイッチと、前記データ処理モジュールから前記データ記憶モジュールに利用者データを転送する第２のクロスバー・スイッチと、前記データ記憶モジュールから前記データ処理モジュールにアドレス・データを転送する第３のクロスバー・スイッチと、前記データ記憶モジュールから前記データ処理モジュールに利用者データを転送する第４のクロスバー・スイッチと、前記データ記憶モジュールから前記データ処理モジュールに応答を転送する第５のクロスバー・スイッチとを備える、請求項１に記載の発明。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システムの複数のモジュール間の相互接続用バッファ付きクロスバー・スイッチに関する。
【背景技術】
【０００２】
クロスバー・スイッチ（「クロスポイント・スイッチ」または「マトリクス・スイッチ」としても知られる）は、複数の入力ポートと出力ポートとを互いに相互接続する。Ｐ個の入力とＱ個の出力を有するクロスバー・スイッチは、Ｐ×Ｑ個のクロスポイントを備えたスイッチ・ファブリック・マトリクスを有し、これらのクロスポイントで入力ポートと出力ポートとの間の接続が行われる。したがって、入力ポートの１つに到達したパケットを、１つまたは複数の指定された出力ポートに送ることができる。例えば、パケットを、ただ１つの指定された出力ポートに送る（ユニキャスト）、全ての出力ポートに送る（ブロードキャスト）、または複数の指定された出力ポートに送る（マルチキャスト）ことができる。
【０００３】
マルチプロセッサ・コンピュータ・システムでは、プロセッサを、メモリまたは他のサブシステムなどの他のリソース、あるいはインターネット・スイッチまたは他の高性能通信ネットワークとリンクさせるのに、バッファのないクロスバー・スイッチが多用されている。しかし、バッファのないクロスバー・スイッチでは、一般に、スイッチ・ファブリックの高速化が求められ、すなわち、スイッチの内部データ・レートは、リンクのデータ・レートよりも高くなければならないことを意味する。こうしたクロスバー・スイッチでは、典型的には、１００％のスループットを達成するために、並列反復マッチング（Ｐａｒａｌｌｅｌ  Ｉｔｅｒａｔｉｖｅ  Ｍａｔｃｈｉｎｇ）（ＰＩＭ）アルゴリズムおよびｉＳＬＩＰアルゴリズムなど、複雑度の高い集中制御スケジューリング・アルゴリズムが必要となる。
【０００４】
バッファ付きクロスバー・スイッチでは、指定された出力ポートに即座に送ることができないパケット（すなわち、遮断パケット）を一時的に記憶しておくためのバッファが、クロスバー・スイッチ内に含まれている。例えば、バッファは、各入力ポート、各出力ポート、クロスバー・スイッチの各クロスポイント接続部、またはそれらのいくつかの組合せに設けることができる。集中制御スケジューリング・アルゴリズムを用いて、入出力データ・ストリームをスイッチ・ファブリックに効率良くアクセスさせることができる。
【発明の概要】
【課題を解決するための手段】
【０００５】
例示的な実施形態では、本発明は、データ・モジュール間でのデータ転送を実現する。各データ・モジュールは、データ処理モジュールおよびデータ記憶モジュールの少なくとも一方である。少なくとも２個の結合されたクロスバー・スイッチが使用され、それぞれのクロスバー・スイッチの入力ノードおよび出力ノードが、対応するデータ・モジュールに結合される。ｉ個目のクロスバー・スイッチは、Ｎｉ−入力ノード×Ｍｉ−出力ノードのスイッチ・ファブリックを有し、ＮｉおよびＭｉはそれぞれ、１よりも大きい正の整数である。各クロスバー・スイッチは、各入力ノードにおける入力バッファと、スイッチ・ファブリックの各クロスポイントにおけるクロスポイント・バッファと、各出力ノードにおける出力バッファとを含む。入力バッファは、第１のスケジューリング・アルゴリズムに従って、入力バッファからデータ・パケットを読み取る入力アービタを有する。クロスポイント・バッファは、第２のスケジューリング・アルゴリズムに従って、クロスポイント・バッファ・キューからデータ・パケットを読み取る出力アービタを有するキューを備える。出力ノードは、１つまたは複数の対応するクロスポイント・バッファから供給されたデータ・パケットのセグメントを受け取る。
【０００６】
本発明のその他の態様、特徴、および利点は、以下の詳細な説明、添付の特許請求の範囲、および添付の図面からより完全に明らかになるであろう。図面では、同じ参照番号は、類似の、または同一の要素を示す。
【図面の簡単な説明】
【０００７】
【図１】本発明の例示的な実施形態に従って動作するバッファ付きクロスバー・スイッチ・システムのブロック図である。
【図２】本発明の実施形態によるバッファ付きクロスバー・スイッチのブロック図である。
【図３】図２のバッファ付きクロスバー・スイッチの補足的詳細を示す図である。
【図４】本発明の例示的な実施形態に従って動作する別のバッファ付きクロスバー・スイッチ・システムを示す図である。
【図５】本発明の例示的な実施形態に従って動作する別のバッファ付きクロスバー・スイッチ・システムを示す図である。
【発明を実施するための形態】
【０００８】
本発明の実施形態によれば、通信システムの複数のデータ・モジュール間の高スループット相互接続を実現するバッファ付きクロスバー・スイッチ・システムが提供される。例えば、クロスバー・スイッチ内でのバッファリングの分配、およびスケジューリング・アルゴリズムによって、本発明の実施形態を用いて、マルチコア・プロセッサをメモリ・サブシステムと相互接続する並行仮想パイプラインを構築することができる。あるいは、本発明の実施形態は、例えば、クライアント／サーバ・スイッチ、インターネット・ルータ、共有メモリ・システム、またはネットワーク・スイッチとして使用することができる。本発明の実施形態は、高速化することなく１００％のスループットを達成することができる。
【０００９】
図１は、例示的なバッファ付きクロスバー・スイッチ・システム１００のブロック図を示す。図示のように、バッファ付きクロスバー・スイッチ・システム１００は、処理装置１０２、バッファ付きクロスバー・スイッチ１０３および１０４、ならびにメモリ装置１０５を備える。バッファ付きクロスバー・スイッチ１０３および１０４はそれぞれ、処理装置１０２およびメモリ装置１０５と電気通信している。したがって、図示のように、バッファ付きクロスバー・スイッチ１０３および１０４は、処理装置１０２およびメモリ装置１０５内の複数のデータ・モジュール間の高スループット相互接続を実施するように構成することができる。いくつかの実施形態では、バッファ付きクロスバー・スイッチ１０３および１０４は、光ファイバを介して処理装置１０２およびメモリ装置１０５と通信している１つまたは複数のチップ上にあってもよい。
【００１０】
いくつかの実施形態では、処理装置１０２は、マルチコア・プロセッサでよい。例えば、処理装置１０２は、Ｎ個のプロセッサを含むことができ、Ｎは１以上の整数である。図１に示すように、処理装置１０２は、プロセッサ１２０（１）、プロセッサ１２０（２）など、Ｎ個目のプロセッサ１２０（Ｎ）まで含む。プロセッサは、例えば、ＰｏｗｅｒＰＣまたはＡＲＭプロセッサなど、汎用プロセッサとして実装することができ、あるいは、プロセッサは、例えば、デジタル信号処理またはセキュリティ・プロトコル処理など、特殊機能のための加速装置として実装することもできる。処理装置１０２はまた、アービタ１２２（１）、アービタ１２２（２）など、Ｎ個目のアービタ１２２（Ｎ）まで含む。図１に示すように、プロセッサ１２０（１）はアービタ１２２（１）と電気通信しており、プロセッサ１２０（２）はアービタ１２２（２）と電気通信しており、以下、アービタ１２２（Ｎ）と電気通信しているプロセッサ１２０（Ｎ）まで同様である。アービタ１２２（１）から１２２（Ｎ）はそれぞれ、プロセッサ１２０（１）から１２０（Ｎ）とそれぞれに通信するための少なくとも１つの入力ポートと１つの出力ポートを有する。
【００１１】
いくつかの実施形態では、メモリ装置１０５は、メモリとの読取りおよび書込み動作を調整するメモリ制御器を使用することができる。メモリは、例えば、少なくとも１つのＲＡＭバッファを含むことができる。したがって、例示的な実施形態に示すように、メモリ装置１０５は、１つまたは複数のＲＡＭバッファからの情報の読取り、および該バッファへの情報の書込みを調整するＭ個のメモリ制御器を含むことができ、Ｍは１以上の整数である。ＮとＭの値は同じでよいが、必ずしも同じである必要はない。メモリは、ＲＡＭバッファだけに限られるものではなく、フラッシュ・メモリなど、１つまたは複数の他の種類のメモリで実施してもよい。メモリ装置１０５は、メモリ制御器１５２（１）からメモリ制御器１５２（Ｍ）まで含む。メモリ装置１０５はまた、アービタ１５０（１）からアービタ１５０（Ｍ）まで含む。図１に示すように、メモリ制御器１５２（１）はアービタ１５０（１）と電気通信しており、メモリ制御器１５２（２）はアービタ１５０（２）と電気通信しており、以下、アービタ１５０（Ｍ）と電気通信しているメモリ制御器１５２（Ｍ）まで同様である。アービタ１５０（１）から１５０（Ｍ）はそれぞれ、メモリ制御器１５２（１）から１５２（Ｍ）とそれぞれに通信するための少なくとも１つの入力ポートと１つの出力ポートを有する。あるいは、本発明の実施形態は、出力調停用の集中アービタを含んでもよい。本発明の他の実施形態は、局在アービタと集中アービタとの組合せを含んでもよい。
【００１２】
バッファ付きクロスバー・スイッチ１０３および１０４は、スイッチへのいかなる入力も、スイッチの１つまたは複数の任意の出力に転送することが可能なように構成されたスイッチ・ファブリックを含む。例示的な実施形態では、バッファ付きクロスバー・スイッチ１０３は、Ｎ個の入力ポートとＭ個の出力ポートを有し、バッファ付きクロスバー・スイッチ１０４は、Ｍ個の入力ポートとＮ個の出力ポートを有し、Ｎはプロセッサの数であり、Ｍはメモリ制御器の数である。図１に示すように、バッファ付きクロスバー・スイッチ１０３は、１３２（１）から１３２（Ｎ）として示すＮ個の入力ポートと、１３８（１）から１３８（Ｍ）として示すＭ個の出力ポートとを有する。バッファ付きクロスバー・スイッチ１０４は、１４８（１）から１４８（Ｍ）として示すＭ個の入力ポートと、１４２（１）から１４２（Ｎ）として示すＮ個の出力ポートとを有する。図１には２個のバッファ付きクロスバー・スイッチを示しているが、本発明は、それだけに限られるものではなく、したがって、バッファ付きクロスバー・スイッチ・システム１００は、Ｂ個までのバッファ付きクロスバー・スイッチを含むことができ、Ｂは１以上の整数である。
【００１３】
例えば、本発明の例示的な実施形態は、５個のバッファ付きクロスバー・スイッチ、すなわち、処理装置１０２からメモリ装置１０５にアドレスを送る１つのスイッチ（図示せず）、処理装置１０２からメモリ装置１０５にデータを送る１つのスイッチ（バッファ付きクロスバー・スイッチ１０３として示す）、メモリ装置１０５から処理装置１０２にアドレスを送る１つのスイッチ（図示せず）、メモリ装置１０５から処理装置１０２にデータを送る１つのスイッチ（バッファ付きクロスバー・スイッチ１０４として示す）、およびメモリからプロセッサに応答を送る１つのスイッチ（図示せず）を含むことができる。
【００１４】
図１に示すように、バッファ付きクロスバー・スイッチ１０３は、処理装置１０２からメモリ装置１０５に送られるデータを切り換えるように構成され、バッファ付きクロスバー・スイッチ１０４は、メモリ装置１０５から処理装置１０２に送られるデータを切り換えるように構成される。したがって、バッファ付きクロスバー・スイッチ１０３および１０４を用いて、処理装置１０２のＮ個のプロセッサのうちのどれを、メモリ装置１０５のＭ個のメモリ制御器のうちのどれと通信させるかを設定することができる。例えば、処理装置１０２のプロセッサ１２０（１）から供給されたデータを、バッファ付きクロスバー・スイッチ１０３の入力ポート１３２（１）に供給することができる。アービタ１２２（１）は、データ・プロセッサ１２０（１）によって、バッファ付きクロスバー・スイッチ１０３の入力ポート１３２（１）に供給されるデータを制御する。破線矢印１３４によって示すように、バッファ付きクロスバー・スイッチ１０３は、このデータをバッファ付きクロスバー・スイッチ１０３の出力ポート１３８（２）に供給するように構成することができる。アービタ１５０（２）は、どのクロスポイント・バッファが、バッファ付きクロスバー・スイッチ１０３の出力ポート１３８（２）に転送されるかを制御する。したがって、バッファ付きクロスバー・スイッチ１０３は、このデータをメモリ装置１０５のメモリ制御器１５２（２）に供給する。同様に、破線矢印１３５および１３６は、バッファ付きクロスバー・スイッチ１０３の他の例示的なデータ経路の設定を示す。バッファ付きクロスバー・スイッチ１０３はまた、１つの入力ポートからのデータを複数の出力ポートに供給するように設定することもできる。同様に、メモリ装置１０５のメモリ制御器１５２（１）からのデータを、バッファ付きクロスバー・スイッチ１０４の入力ポート１４８（２）に供給することができる。アービタ１５０（１）は、メモリ制御器１５２（１）によって、バッファ付きクロスバー・スイッチ１０４の入力ポート１４８（２）に供給されるデータを制御する。破線矢印１４５によって示すように、バッファ付きクロスバー・スイッチ１０４は、このデータを１つの出力、この例では出力ポート１４２（２）に供給するように設定することができ、この出力ポートは、処理装置１０２のプロセッサ１２０（２）にデータを供給する。アービタ１２２（２）は、どのクロスポイント・バッファが、バッファ付きクロスバー・スイッチ１０４の出力ポート１４２（２）に転送されるかを制御する。同様に、破線矢印１４４および１４６は、バッファ付きクロスバー・スイッチ１０４の他の例示的なデータ経路の設定を示す。
【００１５】
図２は、本発明の実施形態によるバッファ付きクロスバー・スイッチ・システム２００のブロック図を示す。図示のように、バッファ付きクロスバー・スイッチ・システム２００は、バッファ付きクロスバー・スイッチ２２６と、仮想出力キュー（ＶＯＱ）２０２、２０４、および２０６とを含む。バッファ付きクロスバー・スイッチ２２６は、入力ポート２２０、２２２、および２２４として示す３個の入力ポートと、出力ポート２４６、２４８、および２５０として示す３個の出力ポートとを有する。したがって、図２に示すように、Ｎ＝Ｍ＝３である。入力ポート２２０はＶＯＱ２０２と電気通信し、入力ポート２２２はＶＯＱ２０４と電気通信し、入力ポート２２４はＶＯＱ２０６と電気通信している。出力ポート２４６は出力キュー１  ２５２と電気通信し、出力ポート２４８は出力キュー２  ２５４と電気通信し、出力ポート２５０は出力キューＭ２５６と電気通信している。本発明のいくつかの実施形態は、出力キュー２５２、２５４、および２５６を含まなくてもよい。バッファ付きクロスバー・スイッチ２２６は、３×３のスイッチ・マトリクスの各クロスポイントにＦＩＦＯバッファを含む。したがって、例示的な実施形態では、Ｎ×Ｍのスイッチは、Ｎ×Ｍ個のバッファを有することになる。これらのＦＩＦＯバッファを、クロスポイント・キュー２２８、２３０、２３２、２３４、２３６、２３８、２４０、２４２、および２４４として図２に示す。クロスポイント・キューは、それぞれの出力ポートにデータを送る前に、データを一時的に記憶する。クロスポイント・キューによって、このスイッチ・ファブリックは、受取りが遮断されることなく、複数の入力ポートでほぼ同時にデータを受け取ることが可能となる。
【００１６】
ＶＯＱ２０２、２０４、および２０６はそれぞれ、１つまたは複数の仮想先入れ先出し（ＦＩＦＯ）バッファを含むことができる。例えば、ＶＯＱ２０２は、図２にＦＩＦＯ２０２ａ、２０２ｂ、および２０２ｃとして示す３個のＦＩＦＯを含むことができるが、本発明は、それだけに限られるものではなく、より多数の、またはより少数のＦＩＦＯを使用してもよい。各ＶＯＱバッファは、ＶＯＱによるバッファ付きクロスバー・スイッチ２２６のスイッチ・ファブリックへのアクセスをスケジューリングするアービタと電気通信している。図２に示すように、ＶＯＱ２０２はアービタ２１４と電気通信し、ＶＯＱ２０４はアービタ２１６と電気通信し、ＶＯＱ２０６はアービタ２１８と電気通信している。図２ではＶＯＱとして示しているが、本発明の実施形態は、他の種類の入力バッファリングを使用してもよい。
【００１７】
ＶＯＱ２０２、２０４、および２０６に送られたパケットは、パケットの宛先アドレスに従ってＦＩＦＯ内に分類される。パケットは、一般には可変長のものであり、したがって、本発明の実施形態は、パケットをスイッチ・ファブリックに供給する前に、それらのパケットを「セル」に分割する。セルとは、固定数のビットであり、それによって、様々なサイズのパケットをいくつかの固定サイズのセルに分割することができ、必要に応じてパディングが伴う。クロスポイント・キューは、セルを対応する出力キュー（複数可）に転送する前に、データ・セルを一時的に記憶する。各クロスポイント・キューは、クロスポイント・キューによるバッファ付きクロスバー・スイッチ２２６の出力ポートへのアクセスをスケジューリングするアービタと電気通信している。図示のように、クロスポイント・キュー２２８、２３０、および２３２は、アービタ２２５と電気通信し、クロスポイント・キュー２３４、２３６、および２３８は、アービタ２２７と電気通信し、クロスポイント・キュー２４０、２４２、および２４４は、アービタ２２９と電気通信している。図１に戻ると、アービタ２１４、２１６、および２１８は、アービタ１２２（１）から１２２（Ｎ）に対応し、アービタ２２５、２２７、および２２９は、アービタ１５０（１）から１５０（Ｍ）に対応し、ここではＮ＝Ｍ＝３である。
【００１８】
本発明のいくつかの実施形態は、データ・セルをパケットにリアセンブルする出力キュー２５２、２５４、および２５６を含む。パケットをスイッチ・ファブリックに直接送る（すなわち、パケットをセルに分割しない）実施形態では、パケットのリアセンブルが必要でないので、出力キュー２５２、２５４、および２５６は必要でない。
【００１９】
本発明のいくつかの実施形態では、各クロスポイント・キューのサイズ（例えば、キューの深さ）は可変とすることができる。したがって、各クロスポイント・キューの深さは、例えば、図１のバッファ付きクロスバー・スイッチ１０３および１０４を介してデータを転送する往復時間に基づいて変えることができる。例えば、長い往復時間を有するデータ経路では、パケットの往復転送の間データ・セルを記憶しておくために、より大きいクロスポイント・バッファが必要となり得る。したがって、本発明の実施形態は、異なる往復時間を支持する様々な深さのクロスポイント・キューを実現する。
【００２０】
往復時間とは、クレジットが入力アービタに戻るのにかかる時間、およびデータをクロスポイント・バッファに送るのにかかる時間である。最初は、全てのクロスポイント・バッファは空である。バッファ付きクロスバー・スイッチの各入力アービタは、各クロスポイント・バッファについて、何個のクレジットが利用可能か追跡することができる。例えば、クロスポイント・バッファｉ、ｊの各入力ポートｉで利用可能なクレジットの数Ｃは、Ｃ（ｉ，ｊ）で表すことができる。クレジットの数は、最初は、クロスポイント・バッファｉ、ｊの深さと同じでよい。入力ポートｉからクロスポイント・バッファｉ、ｊに各データ・セルが送られるごとに、クレジットの数Ｃは減分される。Ｃ（ｉ，ｊ）がゼロとなったとき、入力ポートｉは、データ・セルを送るのを停止しなければならず、さもないと、クロスポイント・バッファｉ、ｊはオーバーフローすることになる。出力ｊにおける出力アービタがクロスポイント・バッファ（ｉ、ｊ）からセルを取り込むと、Ｃ（ｉ，ｊ）は増分される（「クレジットを返す」）。例えば、入力によってクロスポイント・バッファに書き込まれるのに２サイクルかかり、クレジットを返すのに３サイクルかかるシステムでは、往復時間は５サイクルとなる。より深いクロスポイント・バッファでは、入力は、クロスポイント・バッファに、そのクレジットを使い果たすことなくセルを送り込み続けることができる。本発明の例示的な実施形態では、クロスポイント・バッファの深さは、クレジット返却待ち時間に伴って増大させることができ、したがって、往復時間も増大することになる。
【００２１】
Ｎ個の入力ＦＩＦＯバッファ２０２、２０４、および２０６はそれぞれ、１つのアービタを有するため、入力アービタ２１４、２１６、および２１８は、分配アービタである。入力アービタは、互いに電気通信しておらず、したがって、バッファ付きクロスバー・スイッチ２２６の拡張性が促進され、これは、分配アービタは集中アービタよりも小さい物理的寸法を有し得るからである。同様に、Ｍ個の出力キュー２５２、２５４、および２５６もそれぞれ、１つのアービタを有するため、出力アービタ２２５、２２７、および２２９もやはり、分配アービタである。
【００２２】
例示的な実施形態では、アービタ２１４、２１６、２１８、２２５、２２７、および２２９は、ラウンドロビン・アルゴリズムを実行する「ラウンドロビン」スケジューラとして実装され、このアルゴリズムでは、バッファは、昇順または降順で処理され、その処理は、シーケンスの最後のバッファが処理された後、シーケンスの第１のバッファに戻る。例えば、空でないＶＯＱ２０２ａ、２０２ｂ、および２０２ｃのそれぞれがアービタ２１４によって処理されるとき、その処理されているバッファのデータ・セルは、その時点で処理されているＶＯＱが空になるまで、または、そのＶＯＱの時間枠が終了するまで、スイッチ・ファブリックに供給される。これらのいずれが生じても、アービタ２１４は、シーケンスの次のＶＯＱに進むことになる。アービタ２１４は、空のＶＯＱはスキップして、次の空でないＶＯＱを処理する。アービタ２１６、２１８、２２５、２２７、および２２９は、アービタ２１４と同様に動作する。ラウンドロビン・スケジューリング・アルゴリズムについて説明しているが、本発明はそれだけに限られるものではなく、他のスケジューリング・アルゴリズム、例えば、データを最長時間保持していたキューにスケジューリング優先度が与えられる、最長キュー優先スケジューリングを使用することもできる。さらに、本発明の実施形態は、必ずしも同じスケジューリング・アルゴリズムを使用するというわけではなく、スケジューリング・アルゴリズムの組合せを使用することができる入力アービタおよび出力アービタを実現する。
【００２３】
一般に、調停は上記の通りに実施される。したがって、バッファ付きクロスバー・スイッチ２２６が、同数、すなわちＮ個の入力と出力を有する場合、Ｚ個のセル（但しＺは整数）からなるパケットは、宛先出力キューに到達するのにＮ×Ｚのクロック・サイクルがかかり得る。本発明の例示的な実施形態は、セルの優先順位付けを実現する。例えば、優先順位は、プロセッサ・ベースで割り当てることができ、処理装置１０２内のあるプロセッサに、他のプロセッサよりも高い優先順位を割り当てることができ、したがって、関連するアービタは、Ｚ個のパケット・セル全てをＺサイクルで連続して配送することになる。あるいは、優先順位は、パケット・ベースで割り当てることもでき、例えば、ある種のパケットに、他の種のパケットよりも高い優先順位を割り当てることができる。
【００２４】
バッファ付きクロスバー・スイッチ２２６の特定の出力ポートに繰り返しアクセスすると、不均一な出力が生じる。出力ポートへのアクセスは、出力アービタによって制御されるため、不均一な出力によって、バッファ付きクロスバー・スイッチ２２６の最大スループットが制限されることがある。例えば、図１に示すように、バッファ付きクロスバー・スイッチ２２６の各出力ポートは、メモリ装置１０５内の特定のメモリ制御器と対応している。典型的には、順次アドレスを有するメモリ・ブロックのデータ転送は、１つのメモリ制御器によって管理される。宛先メモリ・アドレスによって、バッファ付きクロスバー・スイッチ２２６のどの出力にアクセスするかが決まる。したがって、順次メモリ・アクセスによって、不均一な出力状態が生じ得、そのため、バッファ付きクロスバー・スイッチ２２６の最大スループットが制限されることがある。本発明のいくつかの実施形態は、バッファ付きクロスバー・スイッチ２２６を介してかかるアドレスにデータを送る前に、メモリ・アドレスをスクランブルする。メモリ・アドレスのスクランブリングによって、順次メモリ・アクセスが、出力ポート・アクセスがより一様に分配されたアクセスに変換される。
【００２５】
図３は、図２のバッファ付きクロスバー・スイッチ・システムの補足的詳細を示す。図３に示すように、バッファ付きクロスバー・スイッチ３０１の例示的な実施形態は、３０２、３０４、および３０６として示すＭ個のマルチプレクサをさらに含み、Ｍはクロスバー・スイッチの出力数である。図３に示すように、Ｎ＝Ｍ＝３である。Ｎ個の入力とＭ個の出力を有するスイッチでは、バッファ付きクロスバー・スイッチ３０１のスイッチ・ファブリックは、Ｍ個の“Ｎ−ｔｏ−１”マルチプレクサを含み得る。図示のように、アービタ２２５、ならびにクロスポイント・キュー２２８、２３０、および２３２は、マルチプレクサ３０２と電気通信している。アービタ２２５は、マルチプレクサ３０２によってどのクロスポイント・キューが出力ポート２４６にアサートされ、したがって出力キュー２５２にアクセスするかを制御する。同様に、クロスポイント・キュー２３４、２３６、および２３８は、マルチプレクサ３０４と電気通信している。アービタ２２７は、マルチプレクサ３０４によってどのクロスポイント・キューが出力ポート２４８にアサートされ、したがって出力キュー２５４にアクセスするかを制御する。クロスポイント・キュー２４０、２４２、および２４４は、マルチプレクサ３０６と電気通信している。アービタ２２９は、マルチプレクサ３０６によってどのクロスポイント・キューが出力ポート２５０にアサートされ、したがって出力キュー２５６にアクセスするかを制御する。
【００２６】
上記ではモノリシック・チップとして実装するとして説明してきたが、本発明はそれだけに限られるものではない。例えば、図４に示すように、各バッファ付きクロスバー・スイッチは、スイッチ・カード４０６（１）から４０６（Ｌ）として示す、それ自体の回路板を占有することができる。複数のスイッチ・カードは、シェルフを占有することができ、シェルフ４０４（１）から４０４（Ｋ）として示す複数のシェルフによって、スイッチ・シャシ４００が形成されている。同様に、プロセッサおよびメモリも、ライン・シャシ４０２上に配置することができる。ライン・シャシ４０２は、シェルフ４０９（１）から４０９（Ｋ）として示す複数のシェルフを含むことができ、各シェルフは、ライン・カード４１０（１）から４１０（Ｌ）として示す複数のライン・カードを含む。各ライン・カードは、メモリまたはプロセッサなどの素子を収容することができ、これらの素子は、スイッチ・カードを介して通信する。ライン・シャシは、典型的には、リンク４１２、４１４、４１６、および４１８として示す電気ケーブルまたは光リンクを介して、スイッチ・シャシと通信する。
【００２７】
図５は、本発明の例示的な実施形態に従って動作する別のバッファ付きクロスバー・スイッチ・システムを示す。図５に示すように、５００として示す１つまたは複数のバッファ付きクロスバー・スイッチを用いて、プロセッサ１０２と記憶モジュール１０５とのチェーンを形成することができ、ここで、記憶モジュールは、２個のプロセッサが互いに通信するためのバッファとして働くことができる。バッファ付きクロスバー・スイッチ５００は、図１に関して説明したように動作する。バッファ付きクロスバー・スイッチ５００はまた、ブリッジ５０２と電気通信しており、したがって、チェーンに沿ってブランチを構築している。ブリッジ５００は、バッファ付きクロスバー・スイッチ５００と通信するための１つの高帯域ポートと、プロセッサ５０４、ならびに記憶モジュール５０６および５０８として示す、より低速のデータ・モジュール、またはレガシー・データ・モジュールと通信するための低帯域ポートとを有することができる。したがって、本発明の実施形態は、より高速のデータ・モジュールに利用できるシステムの帯域幅を制限せずに、より低速のデータ・モジュールを、より高速のデータ・モジュールと通信させる手法を実現する。ブリッジ５０２は、上述のようにバッファ付きクロスバー・スイッチを利用することができ、または、バッファ付きクロスバー・スイッチを使用しない設計を利用してもよい。
【００２８】
本発明の特性を説明するために詳述し、例示してきた諸部品の細部、材料、および配置には、以下の特許請求の範囲に示す本発明の範囲から逸脱することなく、当業者によって様々な変更を行うことができることがさらに理解される。
【００２９】
本明細書で述べる「一実施形態（ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ）」または「ある実施形態（ａｎ  ｅｍｂｏｄｉｍｅｎｔ）」とは、その実施形態に関して説明した特定の特徴、構造、または特性が、本発明の少なくとも１つの実施形態に含まれ得ることを意味する。本明細書の様々な箇所で見られる「一実施形態では」という文言は、必ずしも全て同じ実施形態を指すというわけでも、他の実施形態と必然的に相互に排他的な別個の、または代替の実施形態を指すというわけでもない。同じことが、用語「実装形態（ｉｍｐｌｅｍｅｎｔａｔｉｏｎ）」についても当てはまる。
【００３０】
単一の集積回路、マルチチップ・モジュール、単一のカード、またはマルチカード回路パックとして実施可能な実装形態を含めて、回路プロセスについて本発明の例示的な実施形態を説明してきたが、本発明はそれだけに限られるものではない。当業者には明白なように、回路素子の様々な機能はまた、ソフトウェア・プログラムの処理ブロックとして実装することもできる。かかるソフトウェアは、例えば、デジタル信号プロセッサ、マイクロコントローラ、または汎用コンピュータで使用することができる。
【００３１】
本発明は、こうした方法を実施するための方法および装置の形で実施することができる。本発明はまた、磁気記録媒体、光記録媒体、固体メモリ、フロッピー（登録商標）・ディスケット、ＣＤ−ＲＯＭ、ハード・ドライブ、または他の任意の機械可読記憶媒体などの有形媒体に実装されたプログラム・コードの形で実施することができ、こうしたプログラム・コードが、コンピュータなどの機械にロードされ、実行されるとき、その機械は、本発明を実施する装置となる。本発明はまた、例えば、記憶媒体に記憶されようと、機械にロードされ、かつ／または機械によって実行されようと、あるいは、電気配線またはケーブルを介して、光ファイバを介して、または電磁放射を介してなど、何らかの伝送媒体またはキャリヤを介して伝送されようと、プログラム・コードの形で実施することができ、こうしたプログラム・コードが、コンピュータなどの機械にロードされ、実行されるとき、その機械は、本発明を実施する装置となる。汎用プロセッサで実施する場合、プログラム・コードのセグメントは、プロセッサと組み合わさって、特定の論理回路と同様に動作する独特のデバイスを実現する。本発明はまた、本発明の方法および／または装置を用いて生じた、媒体を介して電気的または光学的に伝送されるビットストリームまたは他の信号値シーケンス、磁気記録媒体に記憶される磁界変化などの形で実施することができる。
【００３２】
本明細書に記載の例示的な方法の諸ステップは、必ずしも記載されている順序で実施する必要はないことを理解されたく、また、かかる方法の諸ステップの順序は、単なる例示にすぎないことを理解されたい。同様に、本発明の様々な実施形態と整合の取れた方法で、かかる方法に追加のステップを含むことができ、また、あるステップを省略したり、または組み合わせたりしてもよい。
【００３３】
要素および規格に関して本明細書で使用する場合、用語「互換性のある（ｃｏｍｐａｔｉｂｌｅ）」は、その要素が、規格によって全体的または部分的に指定された形で他の要素と通信することを意味し、その規格によって指定された形で他の要素と十分通信することが可能として他の要素によって認識されることになる。互換性のある要素は、規格によって指定された形で内部的に動作させる必要はない。
【００３４】
また、本説明では、用語「結合させる」、「結合している」、「結合された」、「電気通信」、「接続させる」、「接続している」、または「接続された」とは、当技術分野で既知の、または後に開発された２つ以上の要素間でエネルギーを伝達することを可能とするいかなる形式も指し、必ずしも必要ではないが、１つまたは複数の追加の要素を介在させることも企図される。逆に、用語「直接結合された」、「直接接続された」などは、かかる追加の要素がないことを意味する。信号、および対応するノードまたはポートは、同じ名前で呼ぶことができ、本明細書では置換え可能である。
【図１】
2010259045.tif 000003
【図２】
2010259045.tif 000004
【図３】
2010259045.tif 000005
【図４】
2010259045.tif 000006
【図５】
2010259045.tif 000007