(57)【要約】  本発明は、集積回路上のネットワークに展開することが可能なルータを提供する。ルータは、複数のトラフィッククラスに属する入力データを処理することができる。ルータは、さらに、許容トラフィック下で、全ての入力データが適切に処理および出力されることを、許容可能なコストで保証することができる。本発明は、競合の問題が、２つのより具体的な問題、入力競合および出力競合から成る、という認識に基づいている。ルータに備えられるスイッチが、入力ポートに結合された複数の待ち行列に同時に応対できるように設計されているため、入力競合の問題は、もはや起こらない。優先度の低いトラフィックよりも、優先度の高いトラフィックを継続的に優先させることにより引き起こされる欠乏の問題は、優先度の低いトラフィッククラスからのデータを含む待ち行列が、優先度の高いトラフィッククラスからのデータを含む待ち行列と同時に応対されることを許すことにより解決される。
2007510345.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを備える集積回路であって、
前記ネットワークは、複数のルータを備え、
前記ルータのうちの少なくとも１つは、少なくとも２つのトラフィッククラスに対応する入力データを受信するように構成された複数の入力ポートを備え、
前記ルータは、複数の待ち行列をさらに備え、前記待ち行列は、単一のトラフィッククラスに対応する入力データを記憶するように構成されており、
前記入力ポートは、前記待ち行列のうちの少なくとも２つに結合され、前記ルータは、スイッチをさらに備える、集積回路において、
前記スイッチは、前記複数の待ち行列から同時に入力を受信するように構成されている、
ことを特徴とする集積回路。
【請求項２】
前記待ち行列のうちの第１の選択肢は、優先度の高いトラフィッククラスに対応する入力データを記憶するように構成されており、
前記待ち行列のうちの第２の選択肢は、優先度の低いトラフィッククラスに対応する入力データを記憶するように構成されている、ことを特徴とする請求項１に記載の集積回路。
【請求項３】
前記第１の選択肢は、前記ネットワーク内で保証型の通信サービスを提供するように展開されており、
前記第２の選択肢は、前記ネットワーク内でベストエフォート型の通信サービスを提供するように展開されている、ことを特徴とする請求項２に記載の集積回路。
【請求項４】
前記入力ポートに結合され、かつ前記スイッチに結合されているコントローラをさらに備え、前記コントローラは、複数のアービターを備え、
少なくとも１つの前記トラフィッククラスの前記アービターは、所定のスケジュールを実施する、ことを特徴とする請求項１に記載の集積回路。
【請求項５】
前記スイッチは、複数のマルチプレキサを備え、各マルチプレキサは、出力ポートに結合されており、前記マルチプレキサのそれぞれは、前記待ち行列に記憶された前記入力データを入力として受け入れるように構成されている、ことを特徴とする請求項１に記載の集積回路。
【請求項６】
ネットワークを備える集積回路におけるデータの欠乏を避けるための方法であって、
前記ネットワークは、複数のルータを備え、
前記ルータのうちの少なくとも１つは、少なくとも２つのトラフィッククラスに対応する入力データを受信する複数の入力ポートを備え、
前記ルータは、複数の待ち行列をさらに備え、前記待ち行列は、単一のトラフィッククラスに対応する入力データを記憶し、
前記入力ポートは、待ち行列のうちの少なくとも２つに結合され、前記ルータは、スイッチをさらに備える、方法において、
前記スイッチは、前記複数の待ち行列から同時に入力を受信する、ことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを備える集積回路に関し、ネットワークは、複数のルータを備え、ルータのうちの少なくとも１つは、少なくとも２つのトラフィッククラスに対応する入力データを受信するように構成された複数の入力ポートを備え、ルータは、複数の待ち行列をさらに備え、待ち行列は、単一のトラフィッククラスに対応する入力データを記憶するように構成されており、入力ポートは、待ち行列のうちの少なくとも２つに結合され、ルータは、スイッチをさらに備える。
【０００２】
本発明は、また、ネットワークを備える集積回路におけるデータの欠乏を避けるための方法に関し、ネットワークは、複数のルータを備え、ルータのうちの少なくとも１つは、少なくとも２つのトラフィッククラスに対応する入力データを受信する複数の入力ポートを備え、ルータは、複数の待ち行列をさらに備え、待ち行列は、単一のトラフィッククラスに対応する入力データを記憶し、入力ポートは、待ち行列のうちの少なくとも２つに結合され、ルータは、スイッチをさらに備える。
【背景技術】
【０００３】
システムオンシリコン（Systems on silicon）は、新たな特性または既存の機能の改善を実施する必要性が増え続けることにより、複雑さの継続的な増加を示している。これは、構成要素を集積回路上に集積できる密度の増加により、可能となっている。同時に、回路が作動されるクロック速度も、高速化の傾向にある。より速いクロック速度は、増加された構成要素の密度と組み合わされて、同一のクロック領域内で同期して動作できる面積を減少させてきた。これは、モジュール式のアプローチの必要性を産んだ。このようなアプローチによると、処理システムは、複数の比較的独立した複雑なモジュールを備える。従来の処理システムにおいては、モジュールは、通常、バスを介して互いに通信する。しかしながら、モジュールの数が増加するに連れ、この通信のやり方は、次の理由により、もはや実用的ではない。第一に、多数のモジュールが、高すぎるバス負荷を形成する。第二に、多くのモジュールがバスに結合されるため、クロック周波数が減少する。第三に、１つだけのデバイスがバスにデータを送信可能であることから、バスは、通信ボトルネックを形成する。
【０００４】
通信ネットワークは、これらの不利益を克服する有効なやり方を形成する。このようなネットワークの利点は、２００３年３月７日にミュンヘン（ドイツ）で行なわれた、設計、自動化およびテストに関する欧州会議（Conference on Design, Automation and Test in Europe）にて公開された文献“ネットワークオンチップ向けの保証型およびベストエフォート型の両方のサービスを有するルータの設計におけるトレードオフ（Trade Offs in the Design of a Router with Both Guaranteed and Best-Effort Services for Networks on Chip）”に述べられている。とりわけ、ネットワークは、グローバルな相互接続ワイヤを構成および管理すること、ならびにこのようなワイヤを共有することが可能であり、これにより、ワイヤの数を減らすとともに、その利用性を増大している。
【０００５】
通信ネットワークは、複数の部分的に接続されたノードを備える。モジュールからのリクエストは、ノードにより、１つまたは複数の他のノードに転送される。文献および最新の調査は、これらのネットワークオンチップ（Networks on Chip）が、大きなシステムオンチップ（Systems on Chip）には不可欠となっていることを示している。このようなネットワークは、典型的には、ワイヤなどの物理的な接続により相互接続されるルータを備える。
【０００６】
ネットワークオンチップ（ＮｏＣ）内のルータ向けの既知のアーキテクチャは、入力待ち行列バッファリングアーキテクチャ（input queued buffering architecture）であり、それは、このアーキテクチャが、低コストで妥当な性能を提供するからである。従来の入力待ち行列においては、単一の待ち行列が、ルータの各入力ポートに結合されている。ルータの入力データは、トラフィッククラスに分類されており、トラフィッククラスは、入力データが属するデータのクラスを定義する。従来の入力待ち行列は、異なるトラフィッククラスからの入力データに差をつけることができず、したがって、単一のトラフィッククラスがサポートされている。
【０００７】
複数のトラフィッククラスを必要とするシステムは、複数のネットワークで実施することができるが、これらを単一のネットワークに組み合わせることは、ルータを接続する物理的な接続を共有する利点を有する。したがって、複数のトラフィッククラスをサポートする単一のネットワークを持つことが望ましい。これを達成する標準的なやり方は、ルータの入力待ち行列のスキームを、各入力ポートの複数の待ち行列により拡張することである。通常は、入力ポートに結合される待ち行列の組が、１つのメモリユニット（例えばＲＡＭメモリ）にマッピングされ、その理由は、１つの大きなメモリは、複数の小さなメモリよりも高い面積効率を有するためである。複数のトラフィッククラスをサポートするルータの標準的なアーキテクチャが、図１Ｂに示されている。
【０００８】
ルータは、時間をいわゆる‘スロット’に分割する個別の時点で決定を行う。ルータが、１つのスロットにおいて、複数のデータアイテムを、同一のリンクを介して（すなわち同一の出力に）送ることを試みることができる。この問題は、競合（contention）と呼ばれる。１つのデータアイテムだけを、スロット内のリンクを介して送ることができるので、データアイテム間の選択を行なわなければならない。この処理は、競合解決（contention resolution）と呼ばれる。競合解決は、典型的には、トラフィックをスケジューリングすることによって行なわれる。例えば、スケジューラが、優先度の低いトラフィックに対応するデータアイテムを選択する前に、優先度の高いトラフィックに対応するデータアイテムを選択してもよい。スケジューリングは、通常、１つまたは複数のアービター（arbiter）により実施され、アービターはスロット内のリクエストを許可および拒否することができ、スロットごとに、１つの出力ポートに対して１つのリクエストのみが許可される。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
この標準的なアーキテクチャは、２つの主要な問題を有する。第一の問題は、欠乏が起こり得ることである。欠乏とは、いくつかの入力データ、例えば低い優先度のトラフィッククラスに属するデータが、全く供給されず、よって、入力データがルータ内で‘行き詰まる’ことを意味する。実際には、これは、ネットワーク内でデータがその宛先に到着することがないことを意味する。２種類の欠乏を、区別することができる。第１の種類の欠乏は、主にネットワークによって引き起こされる。それは、出力ポートの帯域幅が許すよりも多くのデータアイテムが、ルータの出力ポートに割り当てられるからである。これらの状況下では、出力ポートへのトラフィックは、‘非許容トラフィック（non-admissible traffic）’と呼ばれる。第２の種類の欠乏は、例えば競合解決が正しく行なわれないために、ルータ自体によって引き起こされる。この場合は、出力ポートへのトラフィックは、‘許容トラフィック（admissible traffic）’と呼ばれる。本発明は、許容トラフィックに対応するデータアイテムに関する。本明細書の残りでは、許容トラフィックのみが検討される。
【００１０】
第２の問題は、出力ポートへのアクセスをスケジュールする必要がある、アービターの設計に関係する。各出力ポートに対し、１つのアービターがある。アービターは、ルータ内の競合解決を行なう必要がある。これらのアービターの設計は、比較的複雑である。
【００１１】
本発明の目的は、集積回路上のネットワーク内に展開することが可能なルータを提供することであり、ルータは、複数のトラフィッククラスに属する入力データを処理し、かつ許容トラフィック下で、全ての入力データが適切に処理および出力されることを、許容可能なコストで保証することができる。この目的は、請求項１の特徴部によって特徴付けられる集積回路を提供することにより達成される。この目的は、また、請求項６の特徴部によって特徴付けられる方法を提供することにより達成される。
【課題を解決するための手段】
【００１２】
本発明は、競合の問題が、２つのより具体的な問題、入力競合および出力競合から成る、という認識に基づいている。入力競合は、入力ポートに結合された複数の待ち行列がデータを含む場合に、入力ポートにおいて起こる。出力競合は、複数の入力ポートが単一の出力ポートに同時に（すなわち１スロット内で）アクセスを試みた場合に起こる。
【００１３】
既知のルータアーキテクチャは、典型的には、１スロット内で入力ポートごとに多くとも１つの待ち行列に応対することを許すマルチプレキサと、スイッチとを備える。本発明は、入力ポートに結合された複数の待ち行列に同時に応対することができるスイッチを設計可能であるため、マルチプレキサは省略可能である、という認識にさらに基づいている。優先度の低いトラフィックよりも、優先度の高いトラフィックを継続的に優先させることにより引き起こされる欠乏の問題は、優先度の低いトラフィッククラスからのデータを含む待ち行列が、優先度の高いトラフィッククラスからのデータを含む待ち行列と同時に応対されることを許すことにより解決される。入力競合の問題がもはや存在しないため、アービターの設計は、簡素化することができる。ルータに備えられているスイッチは、好適な実施形態の記述において説明されるように、入力ポートごとに複数の待ち行列からの同時入力を扱うように構成されなければならない。
【００１４】
集積回路の一実施形態が、請求項２に記載されており、この実施形態では、待ち行列のうちの第１の選択肢は、優先度の高いトラフィッククラスに対応する入力データを記憶するように構成されており、待ち行列のうちの第２の選択肢は、優先度の低いトラフィッククラスに対応する入力データを記憶するように構成されている。この実施形態は、優先度の高いトラフィックおよび優先度の低いトラフィックを、個別にスケジュールすることができる、という利点を有する。請求項３は、さらなる実施形態を定義し、この実施形態では、第１の選択肢は、ネットワーク内で保証型の通信サービスを提供するために使用されている。第２の選択肢は、ネットワーク内でベストエフォート型の通信サービスを提供するために使用することができる。
【００１５】
少なくとも１つのトラフィッククラスのアービター（例えば優先度が高いトラフィッククラスのアービター）が、所定のスケジュールを実施する場合、ネットワーク内のソースと宛先の間で、競合のないトラフィックのトランザクションを達成することができる。この実施形態は、請求項４に記載されている。
【００１６】
請求項５に記載の実施形態は、本発明に係るスイッチの可能な実施を提供する。
【発明を実施するための最良の形態】
【００１７】
本発明は、図面を参照してより詳細に説明される。
【００１８】
図１Ａは、Ｒｘまでを含むルータＲ１，Ｒ２を有するネットワークを備える既知の集積回路ＩＣを示している。Ｒｘまでを含むルータＲ１，Ｒ２は、ネットワークを通じてデータをルーティングするように構成されている。Ｒｘまでを含むルータＲ１，Ｒ２の入力データは、トラフィッククラスに分類され、トラフィッククラスは、入力データが属するデータのクラスを定義する。本発明は、複数のトラフィッククラスに属するデータをルーティングできるルータに関する。当業者に理解されるように、ネットワークを、１つまたは複数の他の集積回路に拡張して、集積回路ＩＣおよび他の集積回路に単一のネットワークを共有させてもよい。この場合、ＮｏＣは、複数のチップに広がる。本発明は、また、このような共有ネットワークにおけるルータに関する。
【００１９】
図１Ｂは、集積回路上のネットワークに備えられるルータのアーキテクチャを示している。この例では、ルータは、コントローラ１００を備え、コントローラ１００は、複数の入力ポート１０２，１０４，１０６と、クロスバースイッチとも呼ばれるスイッチ１２０とに結合されている。代替的なアーキテクチャも可能であることに、留意されたい。入力ポート１０２，１０４，１０６は、複数のトラフィッククラスに属する入力データＩｎｐｕｔ＿１，Ｉｎｐｕｔ＿２，Ｉｎｐｕｔ＿３を受信する。これらの入力データは、待ち行列１０８ａ，１０８ｂ，１１０ａ，１１０ｂ，１１２ａ，１１２ｂに渡される。各待ち行列１０８ａ，１０８ｂ，１１０ａ，１１０ｂ，１１２ａ，１１２ｂは、単一のトラフィッククラスに属する入力データＩｎｐｕｔ＿１，Ｉｎｐｕｔ＿２，Ｉｎｐｕｔ＿３を記憶することができる。よって、各入力ポートは、複数の待ち行列に結合され、待ち行列の数は、いくつのトラフィッククラスがサポートされるかに依存する。提供される実施形態においては、入力ポートごとに２つの待ち行列、例えば入力ポート１０２に対応する待ち行列１０８ａおよび１０８ｂがあり、これは、２つのトラフィッククラスに属する入力データがサポートされることを意味している。他の実施形態も可能であり、サポートされるべきトラフィッククラスの数に応じて、入力ポートごとの待ち行列の数も異なることは明らかである。
【００２０】
ルータは、また、複数のマルチプレキサ１１４，１１６，１１８を備え、これらは、単位時間（スロット）ごとに、入力ポートごとに多くとも１つの待ち行列に応対することを許すものである。一般に、マルチプレキサ１１４，１１６，１１８は、コントローラ１００への接続（図示せず）も有する。コントローラ１００は、スケジューリングスキームを実施する複数のアービター（図示せず）を備え、かつ、例えばスイッチの設定を計算する。
【００２１】
単一の入力ポートにおける複数の待ち行列がデータを含む場合、当該の入力ポートには、入力競合がある。同様に、複数の入力ポートが、単一の出力ポートへのアクセスを試みた場合、出力競合が発生する。このアーキテクチャに使用されるスイッチ１０２は、待ち行列に一時的に記憶される入力データＩｎｐｕｔ＿１，Ｉｎｐｕｔ＿２，Ｉｎｐｕｔ＿３を、１単位時間（スロット）内で入力ポートごとに多くとも１つの待ち行列が応対されるという制約下で、受信するように構成されている。この例では、スイッチ１０２は、多くとも３つの待ち行列から同時にデータを受信できるが、同一の入力ポートに結合された２つの待ち行列から同時にデータを受信することはできない。スイッチ１０２は、次いで、データを、ネットワークによりさらに処理されるべき出力データＯｕｔｐｕｔ＿１，Ｏｕｔｐｕｔ＿２，Ｏｕｔｐｕｔ＿３として供給する。
【００２２】
図２は、図１に示されるようなアーキテクチャにおける複数のトラフィッククラスに属する入力データの欠乏の問題を示している。欠乏は、ネットワークにおける主要な問題である。この例では、入力ポート１０２，１０４，１０６に結合された上位の待ち行列１０８ａ，１１０ａ，１１２ａが、優先度の高いトラフィッククラスに属するデータを含み、入力ポート１０２，１０４，１０６に結合された下位の待ち行列１０８ｂ，１１０ｂ，１１２ｂは、優先度の低いトラフィッククラスに属するデータを含む。図２内の破線の矢印は、スイッチ１２０の特定の出力ポート（図示せず）へのアクセスを得るためのリクエストを表す。換言すれば、待ち行列１０８ｂに一次的に記憶された入力データは、スイッチ１２０の第２の出力ポートに転送され、出力データＯｕｔｐｕｔ＿２として出力される。しかしながら、これは、図３に示されるように、待ち行列１０８ｂからスイッチ１２０の第２の出力ポートへのリクエストが許可され得ない、という結果をもたらす。図３は、待ち行列１０８ａ，１０８ｂ，１１０ａの状態を示している。待ち行列１０８ａおよび１１０ａ（優先度の高いトラフィッククラスに属するデータを含む）が、それぞれ偶数および奇数のスロットの間に出力ポートへのアクセスを許可される一方で、待ち行列１０８ｂは、以下の理由により応対されない。
【００２３】
−マルチプレキサ１１４が、一度に待ち行列１０８ａ，１０８ｂのうちの１つだけに応対できる、という制約を課しているため、待ち行列１０８ｂは、待ち行列１０８ａとは同時に応対され得ず、
−待ち行列１０８ｂがアクセスをリクエストする出力ポートを、待ち行列１１０ａが ‘占有’し、かつ待ち行列１１０ａは、優先度の高いトラフィッククラスからのデータを含むため、待ち行列１０８ｂは、待ち行列１１０ａとは同時に応対され得ない。
【００２４】
偶数および奇数のスロットの間に発生する上述のパターンが、延々と繰り返された場合、
待ち行列１０８ｂが応対されることはなく、データの欠乏が生じる。
【００２５】
この問題を克服するいくつかの試みが、特にアービターにより展開されるアービトレーションスキームの形で、試みられてきたが、それらの全ては、真の解決策をもたらしていない。さらに、これらのスキームは、実施がより難しく、複雑なハードウェア設計をもたらす。典型的には、これらのスキームは、優先度が低いトラフィックのパフォーマンスを悪化させる。
【００２６】
以下、次のアービトレーションスキームを述べる。
−リクエストの取り消し
−リクエストのロッキング
−無作為化アービトレーション
−複数レベルの優先順位付け
【００２７】
第１の既知のアービトレーションスキームは、リクエストの取り消しと呼ばれる方法を使用する。これは、同じ入力ポートからの、または同じ出力ポートへのいずれかのリクエストが起こった場合は、この入力ポートからのデータまたはこの出力ポートへ送られるデータが、優先度の高いトラフィッククラス（優先度の高いリクエストとも呼ぶ）に属することを条件として、優先度の低いトラフィッククラス（優先度の低いリクエストとも呼ぶ）に属する入力データを含む待ち行列からの、出力ポートにアクセスするリクエストが取り消されることを意味する。この方法は、低いハードウェアコストを有するが、優先度の低いアービター（優先度の低いリクエストをスケジュールする）は、優先度の高いアービター（優先度の高いリクエストをスケジュールする）が終了した後にのみ開始できる。これは、長い計算レイテンシーをもたらす。さらに、このアービトレーションスキームは、公平ではなく、単一の待ち行列の優先度の低いリクエストが、反復的に取り消される、という結果をもたらす場合さえある。再び、待ち行列に欠乏が生じ得る。
【００２８】
待ち行列での欠乏を導く反復的な取り消しの例が、図４および図５に示されている。優先度の低いトラフィッククラスに属する第１の入力ポート１０２からの入力データＩｎｐｕｔ＿１は、待ち行列１０８ｂに向けられ、一方で、優先度の高いトラフィッククラスに属する入力データＩｎｐｕｔ＿１は、待ち行列１０８ａに向けられる。待ち行列１１０ｂおよび１１２ｂは、それぞれ入力データＩｎｐｕｔ＿２，Ｉｎｐｕｔ＿３を含み、これらは、優先度の低いトラフィッククラスに属する。図５からは、行列１０８ｂが応対されないことが分かり、その理由は、
−マルチプレキサ１１４が、一度に待ち行列１０８ａ，１０８ｂのうち１つだけに応対できる、という制約を課しているため、待ち行列１０８ｂは、待ち行列１０８ａとは同時に応対され得ず、
−待ち行列１０８ａが同じ入力ポートに対応するため、待ち行列１０８ｂからの優先度の低いリクエストが取り消され、
−スケジューラは、取り消しの後に待ち行列１１０ｂ，１１２ｂに応対することができるが、待ち行列１０８ｂに再び応対する必要がある場合に、再び、待ち行列１０８ａからの優先度の高いリクエストがあり、よって、待ち行列１０８ｂからの優先度の低いリクエストが再び取り消される、等である。
【００２９】
他のアービトレーションスキームは、リクエストのロッキングと呼ばれる方法を使用する。リクエストの取り消しでの、長いレイテンシーを避けるため、かつ反復的な取り消しを避けるために、この方法は、優先度の高いトラフィッククラスおよび低いトラフィッククラスを、出力競合のみを考慮に入れて同時にスケジュールする。特定の入力ポートにおいて、許可された優先度の低いリクエストと優先度の高いリクエストの間に入力競合がある場合、優先度の低いリクエストの許可が無視され、優先度の低いアービターがロックされ、無視された低い優先度を、他の優先度の低いリクエストを許可する前に、先に許可する。このアービトレーションスキームが、図４に示される例において使用された場合、ロッキングは、待ち行列１１０ｂおよび１１２ｂが出力データＯｕｔｐｕｔ＿２を含む出力ポートを以前にアドレスしていた場合には、待ち行列１０８ｂの欠乏に加えて、待ち行列１１０ｂおよび１１２ｂの欠乏をも引き起こす。これは、優先度の低いリクエストが、効率的に応対されず、優先度の低い帯域幅の利用は、最適から程遠いことを意味する。
【００３０】
さらなるアービトレーションスキームは、上述したように、無作為化されたアービターの使用と組み合わされたリクエストの取り消しにより構成される。無作為化されたアービターは、出力ポートごとに、‘競合しているリクエスト’（同じ出力ポートをアドレスするリクエスト）のうちの１つを無作為に許可する。このようにして、反復的な取り消しの問題が、無作為化により解決される。しかしながら、このアービトレーションスキームの不利な点は、無作為化アービターの実施が、比較的高価なことである。
【００３１】
最後に、この明細書の残り部分において複数レベルの優先順位付けと呼ばれる方法を用いるアービトレーションスキームがある。この方法は、優先度の低いトラフィッククラス内での優先度を、上述したようなリクエストの取り消しと組み合わせて提供する。リクエストが取り消された際に、その許可されるチャンスを増やすように、優先度が上げられる。次いで、優先度の低いトラフィッククラスのためのアービターは、優先順位付けされたアービターである必要がある。しかしながら、このアービトレーションスキームも、ハードウェアの複雑さという不利な点を有し、そのコストは、優先順位付けされたアービターおよび優先順位の管理などにより、比較的高くなる。
【００３２】
従来技術から知られているルータは、図６に示されるスイッチ１２０を展開する。この例において、３×３のクロスバースイッチが展開される。スイッチ１２０は、マルチプレキサ１１４，１１６，１１８の出力を表す３つの入力ラインを有する。スイッチ１２０自体は、３つのマルチプレキサ６００，６０２，６０４も備える。データは、アドレスされた出力ポートに応じ、各入力ラインを介してマルチプレキサ６００，６０２，６０４に送られる。マルチプレキサ６００は、出力データＯｕｔｐｕｔ＿１として出力されるべき第１の出力ポートに対するデータを受け入れ、マルチプレキサ６０２は、出力データＯｕｔｐｕｔ＿２として出力されるべき第２の出力ポートに対するデータを受け入れ、マルチプレキサ６０４は、出力データＯｕｔｐｕｔ＿３として出力されるべき第３の出力ポートに対するデータを受け入れる。スイッチは、以下のように動作する。例えば、優先度の高いトラフィッククラスに属する入力データＩｎｐｕｔ＿３は、入力ポート１０６を介して待ち行列１１２ａに向けられる。待ち行列１１２ａが、出力データＯｕｔｐｕｔ＿２により、出力ポートへのアクセスをリクエストしたと仮定する。次いで、マルチプレキサ１１８は、まず、データを多重化し、次いで、データは下位の入力ラインを介してスイッチ１２０に入る。その後、マルチプレキサ６０２が、データを多重化し、最後に、データが出力データＯｕｔｐｕｔ＿２として出力される。
【００３３】
結果として、入力競合がもはや起こらず、スケジューリングスキームが、より複雑でなくなるため、コントローラ１００を簡略化することができる。従来技術のルータは、また、継続的な‘ライン先頭のブロッキング（head-of-line blocking）’の問題を有し、その結果、入力ポートでの待ち行列の先頭でのデータの欠乏が、当該の入力ポートにおける全てのデータの欠乏をもたらす。本発明に係るルータでは、ライン先頭のブロッキングは無限には起こらず、従来技術のルータよりも少なく発生し、これもまた、ルータのパフォーマンスに肯定的な効果を有する。
【００３４】
一実施形態において、優先度の高いトラフィッククラスと、優先度の低いトラフィッククラスの間の差を有利に用いて、一方では保証サービスを、他方ではベストエフォートサービスを提供できるルータを提供することができる。このような組み合わされたルータアーキテクチャは、２００３年３月７日にミュンヘン（ドイツ）で行なわれた、設計、自動化およびテストに関する欧州会議（Conference on Design, Automation and Test in Europe）において公開された文献“ネットワークオンチップ向けの保証型およびベストエフォート型の両方のサービスを有するルータの設計におけるトレードオフ（Trade Offs in the Design of a Router with Both Guaranteed and Best-Effort Services for Networks on Chip）”に述べられている。保証されたスループットよび保証されたレイテンシーなどの転送の要件を有する、ネットワークを通じて転送されるべきデータは、次いで、優先度の高いトラフィックとして分類することができる。優先度の低いトラフィックは、転送がベストエフォートベースでおこなわれるデータにとって、適切なクラスである。静的なスケジューリングと呼ばれる方法、すなわち、所定のアービトレーションスキームが展開された場合、ネットワーク内のソースと宛先の間で、競合のない優先度の高いトランザクションを達成することができる。この場合、接続は、実行時でなくコンパイル時にソースと宛先の間でセットアップされており、これらの接続は、保証サービスを提供するようにセットアップされる。
【００３５】
図７は、本発明に係る集積化された回路上のネットワーク内のルータのアーキテクチャを示している。従来技術からの制約、すなわち入力ポート１０２，１０４，１０６ごとに、待ち行列１０８ａ,１０８ｂ，１１０ａ，１１０ｂ，１１２ａ，１１２ｂのうちの１つだけを一度に使用できるという条件は、取り除かれる。これは、各待ち行列１０８ａ,１０８ｂ、１１０ａ，１１０ｂ，１１２ａ，１１２ｂを、全てスイッチ７００に直接結合することによって達成される。換言すれば、マルチプレキサ１１４，１１６，１１８は、省くことができる。このようにすれば、アーキテクチャは、入力競合の被害をまったく受けない。本発明に係るスイッチ７００は、図８に示すように、これを可能にするように適合されなければならない。スイッチ７００は、６×３のクロスバースイッチであり、（図６の実施形態のように）３つの入力ラインの代わりに、６つの入力ラインからデータを受信することができる。再び、スイッチ７００が、３つのマルチプレキサ８００，８０２，８０４を備える。これらのマルチプレキサ８００，８０２，８０４は、６つの入力ラインからの入力を受信するように構成されており、各入力ラインは、待ち行列１０８ａ,１０８ｂ，１１０ａ，１１０ｂ，１１２ａ，１１２ｂのうちの１つからのデータに対応している。よって、スイッチ７００は、全ての待ち行列１０８ａ,１０８ｂ，１１０ａ，１１０ｂ，１１２ａ，１１２ｂから同時に入力を受信するように構成されている。
【００３６】
本発明の保護の範囲は、ここに記載される実施形態に制限されないことに注意されたい。本発明の保護の範囲は、特許請求の範囲における参照符号にも制限されない。‘備える’という語は、請求項に述べられるもの以外の要素を除外しない。要素に先行する‘１つの’という語は、これらの要素が複数であることを除外しない。本発明の一部を形成する手段は、両方とも、専用のハードウェアの形、またはプログラムされた汎用プロセッサの形で実施することができる。本発明は、それぞれの新たな特性または特性の組み合わせに存する。
【図面の簡単な説明】
【００３７】
【図１Ａ】図１Ａは、ルータを有するネットワークを備える集積回路を示している。
【図１Ｂ】図１Ｂは、集積回路上のネットワークに備えられる既知のルータのアーキテクチャを示している。
【図２】図２は、このようなアーキテクチャ内の複数のトラフィッククラスに属する入力データの欠乏の問題を示している。
【図３】図３は、図２に示されるような欠乏の問題を説明するいくつかの待ち行列の状態を示している。
【図４】図４は、前記アーキテクチャにおける欠乏を引き起こす反復的な取り消しの例を示している。
【図５】図５は、図４に示されるような欠乏の問題を説明するいくつかの待ち行列の状態を示している。
【図６】図６は、このようなアーキテクチャにおけるスイッチの実施を示している。
【図７】図７は、本発明に係る集積回路上のネットワークにおけるルータのアーキテクチャを示している。
【図８】図８は、本発明に係るスイッチの実施を示している。
【図１Ａ】
2007510345.tif 000003
【図１Ｂ】
2007510345.tif 000004
【図２】
2007510345.tif 000005
【図３】
2007510345.tif 000006
【図４】
2007510345.tif 000007
【図５】
2007510345.tif 000008
【図６】
2007510345.tif 000009
【図７】
2007510345.tif 000010
【図８】
2007510345.tif 000011
【国際調査報告】
2007510345.tif 000012
2007510345.tif 000013
2007510345.tif 000014