(57)【要約】データ交換装置は、スループット保証（ＧＴ）およびベスト・エフォート（ＢＥ）型データ用の入力、出力、入力および出力を相互接続するデータ・スイッチ、（ＧＴ）データ・スケジューリングを制御するための（ＧＴ）制御手段、および（ＢＥ）データ・スケジューリングを制御するための（ＢＥ）制御手段を備える。（ＧＴ）および（ＢＥ）制御手段は、（ＢＥ）データ・スケジューリングがコンテンション・フリーの（ＧＴ）スケジューリングに基づくように組み合わせた制御用に配置される。
2006511139.tif 000002
【特許請求の範囲】
【請求項１】
スループット保証およびベスト・エフォート型データのための入力、出力、前記入力および出力を相互接続するデータ・スイッチ、スループット保証型データ・スケジューリングを制御するために結合されているスループット保証型制御手段、およびベスト・エフォート型データ・スケジューリングを制御するために結合されているベスト・エフォート型制御手段を備えるデータ交換装置であって、前記ベスト・エフォート型データ・スケジューリングがコンテンション・フリーのスループット保証型スケジューリングに基づく複合制御が行なわれるように前記スループット保証およびベスト・エフォート型制御手段が配置されることを特徴とするデータ交換装置。
【請求項２】
前記データ交換装置は、少なくとも１つのデータ・スイッチ入力に対し少なくとも１つのスループット保証型入力バッファを備える請求項１に記載のデータ交換装置。
【請求項３】
前記少なくとも１つのスループット保証型入力バッファの深さは１である請求項２に記載のデータ交換装置。
【請求項４】
前記データ交換装置は、スループット保証型とベスト・エフォート型の両方のデータを収集するため全く同一の出力バッファを備える請求項２に記載のデータ交換装置。
【請求項５】
スループット保証およびベスト・エフォート型のデータは、交換に関してスケジューリングされ、前記ベスト・エフォート型データ・スケジューリングは、コンテンション・フリーのスループット保証型データ・スケジューリングに基づくことを特徴とするデータ交換方法。
【請求項６】
前記ベスト・エフォート型スケジューリングは、前記スループット保証型スケジューリングの後に実行されることを特徴とする請求項５に記載の方法。
【請求項７】
前記保証されたデータ・スケジューリングは１ステップであることを特徴とする請求項５に記載の方法。
【請求項８】
前記１ステップは、入力および／または出力の予約を伴うことを特徴とする請求項７に記載の方法。
【請求項９】
前記ベスト・エフォート型データ・スケジューリングは、要求、許諾、受理のステップを含む、３ステップの１つまたはそれ以上の倍数をとる請求項５に記載の方法。
【請求項１０】
前記ベスト・エフォート型データ・スケジューリングのコンテンション解消は、二部グラフ・マッチングに基づく請求項９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スループット保証［guaranteed throughput］型およびベスト・エフォート［best effort］型データのための入力、出力、入力と出力を相互接続するデータ・スイッチ、スループット保証型データ・スケジューリング［guaranteed throughput data scheduling］を制御するために結合されているスループット保証型制御手段、およびベスト・エフォート型データ・スケジューリング［best effort data scheduling］を制御するために結合されているベスト・エフォート型制御手段を備えるデータ交換装置に関する。
【０００２】
本発明は、さらに、データ交換方法にも関する。
【背景技術】
【０００３】
このようなデータ交換装置および方法は、ＵＳ−２００１／００３３５８１  Ａ１から既知である。この既知のデータ交換装置は、最大４種類のサービス品質クラスのデータに対する入力バッファを備える。例えば、いわゆる帯域幅保証−スループット保証（ＧＴ）とも呼ばれる−クラスおよびベスト・エフォート（ＢＥ）クラスに属す入力バッファがある。既知の装置は、さらに、個別にそれぞれのクラス用でもある出力バッファ、それぞれのおよびすべてのクラス用の入力および出力バッファを相互接続するデータ・スイッチ、および入力データ・パケットのＧＴおよびＢＥデータ・スケジューリングをそれぞれ制御するためのＧＴデータ制御手段とＢＥデータ制御手段を備える。既知の装置の一実施形態では、制御手段は、読み取り順序制御のため優先度制御の一形態を実行するのとは別に、少なくともＧＴクラスに属すデータに対しコンテンション制御を実行する。コンテンション制御を実行することも意図されている詳細な実施形態では、ＢＥデータ・スケジューリングは、ＧＴデータ・スケジューリングの後に実行され、それによって、ＢＥデータ・スケジューリングは、帯域幅保証クラスのデータ・パケットのスケジューリングにより選択されていない入力線および出力線に基づく。複数のクラス、優先度、入力があり、また各クラス用の出力バッファが別々にあることで、コンテンションを制御し、回避し、さまざまなクラスのデータをスケジューリングするために必要なソフトウェアおよびプロセッサ制御ハードウェアに非常に大きな負担がかかるという点が、既知のデータ交換装置および方法の欠点である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、必要なソフトウェアおよびハードウェアに対する負担を軽減する、簡素化されたデータ交換装置および方法を提供することである。
【０００５】
それに加えて、本発明による交換装置は、ベスト・エフォート型データ・スケジューリングがコンテンション・フリーのスループット保証型スケジューリングに基づく複合制御が行なわれるようにスループット保証およびベスト・エフォート型制御手段が配置されることを特徴とする。
【０００６】
本発明による交換装置および方法の利点は、スループット保証型データ・スケジュールは、ベスト・エフォート・データ・スケジューリングの基礎としてコンテンション・フリーのスループット保証型データ・スケジュールから始めて、ベスト・エフォート型データ・スケジューリングの境界条件を単に形成するだけであることが判明している点である。この方法で、スループット保証およびベスト・エフォート型スケジューリングは組み合わされる。そのため、境界条件は入力線および出力線の１ステップでの予約しか伴わない。これは、データ交換装置内のハードウェアおよびソフトウェアおよび制御の負担を軽減するが、データ・パケットがデータ交換装置内で費やす時間として定義される、待ち時間も短縮する。さらに、定義され処理されなければならない多少のソフト優先もなく、これは本発明によるデータ交換装置内のソフトウェア、ハードウェア、および関連する制御もなおいっそう軽減する。
【０００７】
本発明によるデータ交換装置の一実施形態においては、データ交換装置は、少なくとも１つのデータ・スイッチ入力に対し少なくとも１つのスループット保証型入力バッファを備える。
【０００８】
この実施形態では、（複数の）データ・スイッチ毎のスループット保証型入力バッファの個数の特定の選択に関して改善された柔軟性を実現している。
【０００９】
本発明によるデータ交換装置の他の実施形態では、少なくとも１つのスループット保証型入力バッファの深さは１である。
【００１０】
スループット保証型データ・スケジューリングは、さらに待機することなくベスト・エフォート・スケジューリングに対し絶対的に優先する固定境界条件として考えることができる。実際、スループット保証型データ交換は、パイプライン型回路に似た挙動を示す。
【００１１】
本発明によるデータ交換装置の他の実施形態では、データ交換装置は、スループット保証型とベスト・エフォート型の両方のデータを収集するため全く同一の出力バッファを備えることができる。
【００１２】
有利なことに、スループット保証型とベスト・エフォート型の両方の関連データに対し別々の入力バッファおよび出力バッファを必要としないが、これら両方のタイプのデータは、別々の経路でデータ・スイッチに送られる。
【００１３】
本発明による方法の他の実施形態では、ベスト・エフォート・スケジューリングは、スループット保証型スケジューリングの後に実行される。
【００１４】
スループット保証およびベスト・エフォートのスケジューリングは、順次実行することができる。
【００１５】
本発明による方法のさらに他の実施形態では、スループット保証型データ・スケジューリングは、１ステップしか必要とせず、有利である。１ステップであるため、なおいっそう単純に、データ・スイッチの入力および出力の予約を伴うだけであると考えられる。
【００１６】
本発明による方法のさらに他の実施形態では、ベスト・エフォート型データ・スケジューリングは、要求、許諾、受理のステップを含む、３ステップの１つ以上の倍数をとる。
【００１７】
３つのステップを一組として、１回または複数回繰り返した場合、改善されデータ・スケジューリングが得られる。
【００１８】
これは、前記ベスト・エフォート型データ・スケジューリングに対するコンテンション解消が例えば二部グラフ・マッチングに基づく場合に好都合である。
【００１９】
今のところ、本発明によるデータ交換装置および方法は、付属の図面を参照しつつ、さらに他の利点とともに説明されるが、ただし類似のコンポーネントは同じ参照番号を使って参照される。
【発明を実施するための最良の形態】
【００２０】
現在のシステムオンチップおよびネットワークオンチップ・アーキテクチャには、数十億個の半導体コンポーネントを含むチップの複雑な設計を管理するという難題がある。主にコストと帯域幅に関する理由から、こうしたアーキテクチャで要求される動的な通信を処理するのに金属線とバスはもはや適さなくなっている。通信サービス、例えば、サービス保証型またはベスト・エフォート（ＢＥ）型サービスなどは、図１（ａ）に示されているようなデータ交換装置１を介して相互接続を実現する。サービス保証型の一実施例として、ＧＴと略記されるスループット保証型があり、これはまた、帯域幅保証型とも呼ばれる。ＧＴサービスは、最悪の場合の通信シナリオに対する資源予約を必要とするが、ＢＥサービスは、あまりクリティカルでないデータ通信に使用することができ、スループットに関する保証はしない。その一方で、ＢＥデータ・トラフィックは、サービス保証型で提供されるデータ・トラフィックと比べて平均通信パフォーマンスに優れる可能性がある。ＧＴおよびＢＥのサービスは両方とも、現在の柔軟なデータ交換装置１において必要である。
【００２１】
図１（ａ）に示されているように、データ交換装置１は、入力バッファ２および３、および出力バッファ４を備える。入力バッファ２は、ＧＴデータを対象とし、入力バッファ３は、ＢＥデータを対象とする。装置（図に示されていない）では、入力データは、ＧＴデータとＢＥデータとに分けることができる。入力バッファ２および３は、概略が示されているＤＥＭＵＸと示されているデマルチプレクサおよびＭＵＸと示されているマルチプレクサとの間に結合されている。データ交換装置１は、さらに、例えば、クロスバー・スイッチ、ルータ・スイッチ、または交換マトリクスとも呼ばれるデータ・スイッチ５を備え、入力バッファ２、３および出力バッファ４を相互接続する。さらに、データ交換装置１は、前記入力バッファ２、３および出力バッファ４およびデータ・スイッチ５に結合されているＣＯＮＴＲＯＬと示されているスケジューリング制御手段６を備える。スケジューリング制御手段の一部は、データ・スイッチ５のＧＴデータ・スケジューリングを制御するためのＧＴ制御手段６−１であり、スケジューリング制御手段の他の部分は、データ・スイッチ５のＢＥデータ・スケジューリングを制御するためのＢＥ制御手段６−２である。毎回スケジューリングにより、入力バッファ２、３または出力バッファ４のいずれかのコンテンションがなくなる。コンテンションとは、複数のデータ項目が同時に同じ入力Ｉ１．．Ｉ４を要求するか（＝入力コンテンション）、またはデータ・スイッチ５の同じ出力Ｏ１．．Ｏ４を要求した（＝出力コンテンション）ときに発生する出来事のことである。
【００２２】
ＧＴスケジューリングの始点は、ＧＴデータ交換スケジュールそれ自体にコンテンションがないと想定されるような時点である。スケジューリングは、通常、後で説明される、３つのフェーズまたはステップ、つまり、要求、許諾および受理のステップを伴うため、これら３つのステップが、３つのＢＥスケジューリング・ステップに先行する１つのＧＴ予約ステップにまとめられるという事実により、コンテンション・フリーのＧＴスケジューリングを利用することができる。したがって、ＢＥスケジューリングが後に続くＧＴスケジューリングでは、４つのステップをひとまとめに実行するだけであり有利である。特に、ＧＴおよびＢＥ制御手段６−１および６−２は、ＢＥデータ・スケジューリングがコンテンション・フリーのＧＴスケジューリングに基づくように組み合わせた制御用に配置される。これは、ハードウェアおよびソフトウェアの両方のスケジューリング制御を軽減する。出力Ｏ１．．Ｏ４および出力バッファでも、ＧＴがコンテンション・フリーであるため、ＧＴおよびＢＥ用のこれらの出力バッファ４は全く同一の出力バッファ４である。ＧＴ入力バッファは、深さ１しかないように選択することができるが、このことも、ハードウェアおよびソフトウェアの両方のスケジューリング制御を軽減し、またＧＴデータの待ち時間も最小にする。
【００２３】
一実施例では、ＧＴおよびＢＥの組み合わせた、または密接に結びつけられているスケジューリングを説明する。この簡単な例の目的に関して図１（ａ）および１（ｂ）により例示されているように、ルータ・スイッチ５のアリティは４である、つまり、スイッチはＩ１．．Ｉ４の番号が付けられた４本の入力およびＯ１．．Ｏ４の番号が付けられた４本の出力を有すると仮定する。このスケジューリングは、ＧＴ制御手段６−１がまず、例えば、図２（ａ）に示されているように、入力Ｉ３と出力Ｏ１との間のＧＴ接続を予約するようなスケジューリングである。クロスしているＢＥ入力バッファ３により示されている状況は、図１（ａ）に概略が示されているように、バッファ３がデータで満たされていることを意味し、この状況より、図１（ｂ）に示されているようにＢＥスケジューリングのいわゆる二部グラフが得られる。例えば、入力バッファ３内の３、２は、入力Ｉ３から出力Ｏ２へのデータ接続が望まれていることを意味する。入力Ｉ１の側で、３つのＢＥ入力バッファ３は、出力Ｏ１、Ｏ２、およびＯ３へのデータ通信を要求する。入力Ｉ１は、要求を何も示さない。入力Ｉ３は、出力Ｏ２およびＯ４へのデータ通信を要求し、入力Ｉ４は、出力Ｏ４へのデータ転送を要求するだけである。（１）で示されているコンテンション・フリーのＧＴスケジューリングされた接続のため、入力Ｉ３から任意の出力へのＢＥ要求は無効にされる。これは、要求ステップで、入力Ｉ３から出力Ｏ２およびＯ４へのＢＥ要求は、無視されるので、ＢＥスケジューリングが簡素化されるが、これは、ＢＥ要求フェーズで考慮しなければならない入力の数が少ないからである。次のステップは、許諾ステップであり、まず、出力Ｏ１から任意の入力へのＢＥ許諾は無効にされて、このこともまた、ＢＥ許諾フェーズでＢＥスケジューリングを考慮しなければならない出力の数を減らすため、これ以降のＢＥスケジューリングを簡素化する。その後の次のステップは、ＢＥ受理ステップであり、ここで、例えば、出力Ｏ２と入力Ｉ１との間のデータ接続が受理される。これ以降、実際のＧＴおよびＢＥデータ通信が行なわれるようにできる。要求、許諾および受理のステップ３つ組みは、これ以上のスケジューリングを改善するため、１回または複数回繰り返すことができる。
【図面の簡単な説明】
【００２４】
【図１】（ａ）は、本発明によるデータ交換装置の関連する部分の概略図であり、（ｂ）は、その例として取り上げられているいわゆる二部グラフにおける図１（ａ）のデータ交換装置に応用されるデータ・スイッチの入力と出力との間の関係を示す図である。
【図２】図１（ｂ）の例として取り上げられている二部グラフのさまざまなフェーズ（ａ）、（ｂ）、（ｃ）、（ｄ）の図である。
【図１】
2006511139.tif 000003
【図２】
2006511139.tif 000004
【国際調査報告】
2006511139.tif 000005
2006511139.tif 000006