(57)【要約】      （修正有）【課題】メッシュネットワークにおける通信のスループットを制限する。【解決手段】固定パスをネットワークで確立されるように通信へ割り当てるステップと、前記通信を、メッシュセグメントを取るように識別するステップと、前記識別された通信にそれぞれのスループット割当量を割り当てて、これらの割当量の総計が、前記セグメントの公称スループット以下になるようにするステップと、前記ネットワークの入力で各通信のスループットを測定し、その割当量が達せられたとき、前記通信を一時的に停止するステップと、を備える。【選択図】図４
2011035906.tif 000002
【特許請求の範囲】
【請求項１】
メッシュネットワークにおける通信のスループットを制限する方法であって、
固定パスを前記ネットワークで確立されるように通信へ割り当てるステップと、
前記通信を、メッシュセグメントを取るように識別するステップと、
前記識別された通信にそれぞれのスループット割当量を割り当てて、これらの割当量の総計が、前記セグメントの公称スループット以下になるようにするステップと、
前記ネットワークの入力で各通信のスループットを測定し、その割当量が達せられたとき、前記通信を一時的に停止するステップと、
を備えた方法。
【請求項２】
前記メッシュセグメントに基準時間区間に渡るデータユニットのバジェットを割り当てるステップと、
前記バジェットの割当量を、前記セグメントを取るように各通信に割り当てるステップと、
現在の基準区間の間、各通信によって前記ネットワークへ挿入された前記データユニットを計数するステップと、
前記通信によって挿入されたデータユニットの計数値が、前記通信に割り当てられた前記割当量に達したとき、通信を停止するステップと、
前記停止した通信を、次の基準区間で再開するステップと、
を備えた請求項１に記載の方法。
【請求項３】
前記通信の送信元および宛先間の中間ノードの段階で、追加のスループット制限を前記通信に施すステップを備えたことを特徴とする請求項２に記載の方法。
【請求項４】
前記追加のスループット制限は、前記通信を受信しそれをネットワーク上で再送信する、前記中間ノードへ接続されたリソースを伴うことを特徴とする請求項３に記載の方法。
【請求項５】
宛先ノードへの固定パスを取る通信を開始することが可能な送信元ノードを備えたメッシュネットワークであって、
各送信元ノードは、
動作中、前記通信に割り当てられたスループット割当量に対応する値を、前記ネットワークの同じセグメントをとるようなすべての通信の前記割当量の総計が、前記セグメントの公称スループット以下になるように記憶する、各通信に対するメモリーと、
通信のスループットを測定し、その割当量が達せられたとき、前記通信を停止する、スループットリミッタと、
を備えたメッシュネットワーク。
【請求項６】
前記スループットリミッタは、
前記通信によって送信されるデータユニットを計数するカウンタと、
前記カウンタを周期的に再初期化するように構成され、前記周期は、スループットバジェットを表すデータユニットの数の前記セグメントにおける公称スループットでの送信時間に対応する、タイムベースと、
前記カウンタが前記割当量に対応する値に達したとき、前記通信を停止する手段と、
を備えた請求項５に記載のメッシュネットワーク。
【請求項７】
前記ノードは、前記ノードが中間受信体であり、前記ノードのスループットリミッタを介して前記ネットワークへ通信を再送信するための、通信を識別する手段を備えた請求項６に記載のメッシュネットワーク。
【請求項８】
前記識別する手段は、前記通信のヘッダによって運ばれる通信識別子で動作する請求項７に記載のメッシュネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、システムオンチップ（ＳｏＣ）に関し、より詳細には、ネットワークオンチップ（ＮｏＣ）におけるデータフロー管理に関する。
【背景技術】
【０００２】
図１は、マトリックス（またはメッシュ）トポロジーのネットワークオンチップの一例を示し、それはヨーロッパ特許ＥＰ１７０１２７４に記述されている。
【０００３】
このネットワークは、行に配置された複数のバス（水平バスＢｈ）と、列に配置された複数のバス（垂直バスＢｖ）を備える。ルータＲＴＲは、水平バスと垂直バスの各交差部に配置され、ルータに到達する各（水平および垂直）バスセグメント間にポイント・ツー・ポイントが作られるのを可能にする。さらに、各ルータＲＴＲは、データ生成部またはデータ消費部であることが可能であるローカルリソースＲＳＣに接続されている。
【０００４】
この種のネットワークは、任意のリソースＲＳＣに、任意の他のリソースと通信させるように設計される。互いに通信するリソースおよびその通信がとるパスは、概して事前に決定され、ネットワーク管理ロジックにプログラムされている。
【０００５】
通信はデータパケットでなされることが多い。パケットは、バスの幅をもつワード組であり、ワード組において、パケットに関連する情報、特に宛先を含むヘッダが先にくる。
【０００６】
通信ネットワーク、たとえばＡＴＭにおいて、さまざまな技術が、クオリティ・オブ・サービス（サービスの質）を与えるのに用いられる。これらの技術は一般的に、ネットワーク入力ノードに課せられるスループット制限に基づいている。文献“ネットワーク遅延の計算法、パートＩ：孤立したネットワーク要素”（Rene L. Cruz著、IEEE情報理論におけるトランザクション、Vol.37,  No1、１９９１年1月）は、これらの技術の一般的な原理を、他のクオリティ・オブ・サービス問題の中で、記述している。
【０００７】
この種のネットワークは、”接続”モードで動作し、すなわち、送信機ノードはパケットを送信することができる前に接続を交渉しなければならない。接続の確立は、さらに固定パスを定義し、その固定パスを介して、パケットは送信元および宛先間を、接続の期間の間、通過する。もし同じ送信元が、接続が遮断された後で同じ宛先に再度パケットを送信しなければならないのなら、異なるパスを割り当てることができる新たな接続が交渉され、このパスはネットワーク混雑条件に応じて動的に計算される。
【０００８】
クオリティ・オブ・サービスを提供するそのようなネットワークにおいて用いられる方法は、大きな利用可能な計算リソースを有するルータによって実行される。それゆえ、ネットワークオンチップでそれらを実施しようとすることは現実的ではなく、ネットワークオンチップではネットワーク実装はシリコン領域の節約のため簡素であるべきである。
【０００９】
ワームホール（worm hole）ルーティングの例に対する簡素なルーティング方法は、それゆえＮｏＣでは好ましい。そのような方法で、パケットヘッダはパケットが取るべき正確なパスを含み、パケットは分割できずすなわちルータはもし以前のパケットが完全に送信されたならばバスセグメントにおける新たなパケットの送信を開始できるのみである。ルータは、セグメントにおける異なるパケットに属するワードを混合することは許されず、“ワーム”は一体（integral）のままである。
【００１０】
図２はこのコンテキストにおいて使用可能なルータを模式的に示している。ルータは５つの方向、すなわち、ノース（Ｎ）、サウス（Ｓ）、イースト（Ｅ）、ウェスト（Ｗ）と呼ばれるバスセグメントに対応する４つの方向と、ローカルリソースに対応する方向Ｌを管理する。
【００１１】
４入力マルチプレクサＭＸは、各出力方向に割り当てられている。これらの４入力は、マルチプレクサの方向に割り当てられていないルータの入力に対応する。たとえば、ノース出力マルチプレクサＭＸＮはルータの入力Ｌ，Ｓ，Ｅ，Ｗを受け取る。すなわち、ルータは、１つの方向を介して入ってくるパケットが、同一方向を介して出て行くのを阻止する。
【００１２】
さらに、各マルチプレクサ入力は、出力されるのを待機するパケットのワードを格納するように設計されたＦＩＦＯキュー２０が、前段に置かれている。
【００１３】
状態マシン（図示されていない）は、マルチプレクサによる発行される選択を制御し、ＦＩＦＯにおける５つの方向を介して入ってくるワードの書き込みを制御する。
【００１４】
ワームホールルーティングの場合に、到来するパケットヘッダは、どの方向を介してパケットが出力されるべきかをルータに示す。状態マシンは、ヘッダを復号し、パケットの一連のワードを、しかるべきＦＩＦＯに書き込む（入力が接続されている４つのＦＩＦＯの内）。
【００１５】
マルチプレクサは一度に１つのパケットを処理するように制御される、すなわち１つのＦＩＦＯのワードは、それらが同じパケットに属する限り、マルチプレクサによって連続して抽出される。パケットの最後のワードがＦＩＦＯから抽出されたとき、マルチプレクサは次のＦＩＦＯを固定優先メカニズムに従って処理する。この優先メカニズムは循環であることが多く（ラウンドロビン）、それは、実行するのが簡単であり、各到来する方向へ等しい機会を与えるからである。
【００１６】
このタイプのルーティングの１つの欠点は、送信元と宛先間に、大きな決定できないレイテンシを確実にもたらすことであり、それは、クオリティ・オブ・サービス（ＱｏＳ）を要求するアプリケーション、特にリアルタイムアプリケーションと当該ルーティングとの適合性を悪くする。
【００１７】
図３Ａは、この欠点が起こりうる状況を示す。ネットワークがメッシュおよびノードによって模式的に示され、ノードがルータ、リソースまたはこれらの両方を指定する。ノードはＮｘｙによって指定され、ｘは行インデックス、ｙは列インデックスである。
【００１８】
この例では、ノードＮ１０、Ｎ０１、Ｎ０２からノードＮ１３への３つの同時の送信通信が存在する。ノードＮ１０、Ｎ０１からの通信は両方ともノードＮ１１、Ｎ１２を横断する。ノードＮ０２からの通信はノードＮ１２を横断する。ノードＮ１２、Ｎ１３間のセグメントが、大いに求められている。
【００１９】
図３Ｂはこれらの通信によって影響されるルータＮ１１，Ｎ１２の要素をあらわす。ノードＮ１２のイーストマルチプレクサＭＸＥのウェストＦＩＦＯ  ＦＷは、２つの通信のパケットを受信する、すなわち、ノードＮ１１のイーストマルチプレクサによって送信される、ノードＮ０１、Ｎ１０からくるものである。このＦＩＦＯは急速にいっぱいになり、それは特にノードＮ０２に接続されたＦＩＦＯを空にするのに忙しいマルチプレクサＭＸＥによっておそらくまだ空にされていないためである。
【００２０】
ＦＩＦＯ  ＦＷがいっぱいになったとき、ＦＩＦＯ  ＦＷはノードＮ１１によって送信されるパケットを部分的に含んでいることが起こりえる。ノードＮ１２は、ノードＮ１１へ、オーバーフロー防止メカニズムによって、これ以上データを受信できないことを示し、それは、ノードＮ１１から続くデータは、ＦＩＦＯ  ＦＷに書き込まれているパケットに必ず属するためである。ノードＮ１１はもはやデータを送ることができないので、そのマルチプレクサＭＸＥのＦＩＦＯは急速にいっぱいになり、ノードＮ１１は同様に、先行するノードに、データを送らないように示す。そのほかもろもろ、ＦＩＦＯが空になり始めるまでである。
【００２１】
とはいえ、重いトラフィックをもつパスをとらない通信Ｎ００−Ｎ０１−Ｎ２１は、ある時間の間ストール（stall）しうる。それは、通信Ｎ０１−Ｎ１３がセグメントＮ１２−Ｎ１３の混雑のためにストールするという事実のためである。この通信のストールはそれ自体、通信Ｎ００−０２を遅延させるかもしれず、その他もろもろありうる。
【００２２】
その状況は、ＦＩＦＯ  ＦＷが空になり始めたとき、瞬時には取り除かれない。実際には、ノードＮ１２がノードＮ１１に、データを再度受信できることを示すのは、ＦＩＦＯ  ＦＷにおけるロケーションが利用可能になったときのみである。これは、遮断されていたノードのそれぞれによる追加のレイテンシをもたらす。
【００２３】
ネットワークをプログラムする際のルーティング選択においてとられる注意にもかかわらずランダムに起こりうるそのような状況は、パケットのルーティングにおける大きな未知のレイテンシにつながりうる。
【００２４】
ＦＩＦＯのサイズを増加することは、そのような問題の発生を先送りにするが、合理的なＦＩＦＯ寸法が用いられても、その問題を完全には克服しない。
【００２５】
その状況を改善するために、このタイプのネットワークに仮想チャネルを導入することが提案された。これは特許EP1701274に開示されている。仮想チャネルを伴ったネットワークにおいて、ルータのマルチプレクサの４つの入力のそれぞれは、仮想チャネルと同数のFIFOを備える。パケットは、ネットワークにおけるのと同じ物理リンクを取り、ルータに到着したとき、しかるべきFIFOに向けられる。FIFOは、パケットヘッダに含まれる仮想チャネル番号によって識別される。
【００２６】
これによって、異なる優先度が仮想チャネルに割り当てられ、たとえばリアルタイム制約をもつ高優先度パケットは、高優先仮想チャネルを介してルーティングされ、各ルータは高優先仮想チャネルを最初に処理する。
【００２７】
この解決は、高優先仮想チャネルが非常に小数の通信によって取られるときは満足のいくものである。高優先仮想チャネルをとる通信の数が増大すると、各仮想チャネルにおいて、上述したのと同じ問題に直面し、低優先チャネルにおけるレイテンシは一層大きくなる。
【００２８】
フィリップス社の“Aetheral” ネットワークのような、時分割多重（TDM: Time Division Multiplex）同期ネットワークはこれらの欠点を提示しないが、それらは著しく複雑であり、パラメータやシリコン技術の変動に非常に敏感であり、不測の事態を許容する困難をともなう。それらはまた、チップのすべての点で同期生を確実にするのに、チップの要素を配置するのに特別な注意を必要とする。
【発明の概要】
【発明が解決しようとする課題】
【００２９】
それ故、クオリティ・オブ・サービスを提供する簡単な構造のネットワークに対する必要が依然として存在する。
【課題を解決するための手段】
【００３０】
この必要性を満足させるため、メッシュネットワークにおける通信のスループットを制限する方法であって、固定パスを前記ネットワークで確立されるように通信へ割り当てるステップと、前記通信を、メッシュセグメントを取るように識別するステップと、前記識別された通信にそれぞれのスループット割当量（throughput quota）を割り当てて、これらの割当量の総計が、前記セグメントの公称スループット以下になるようにするステップと、前記ネットワークの入力で各通信のスループットを測定し、その割当量が達せられたとき、前記通信を一時的に停止するステップと、を備えた方法が提供される。
【００３１】
実施形態によれば、前記方法は、さらに、前記メッシュセグメントに基準時間区間に渡るデータユニットのバジェットを割り当てるステップと、前記バジェットの割当量を、前記セグメントを取るように各通信に割り当てるステップと、現在の基準区間の間、各通信によって前記ネットワークへ挿入された前記データユニットを計数するステップと、前記通信によって挿入されたデータユニットの計数値が前記通信に割り当てられた前記割当量に達したとき通信を停止するステップと、前記停止した通信を次の基準区間で再開するステップと、を備える。
【００３２】
前記ネットワークの最大レイテンシを減少させるため、前記通信は、前記通信の送信元および宛先間の中間ノードの段階で、追加のスループット制限を施されてもよい。
【００３３】
他の利点および特徴は、添付図面によって例示される、典型的な実施形態の以下の記述からより明らかにされる。
【図面の簡単な説明】
【００３４】
【図１】マトリックス（すなわちメッシュ）トポロジーの従来のネットワークオンチップを模式的に示す。
【図２】図１のネットワークのルータの構造を模式的に示す。
【図３Ａ】図１のネットワークのノード間に確立される典型的な通信を示す。
【図３Ｂ】図３Ａの通信に伴われるルータの要素を示す。
【図４】スループットリミッタを組み込んだ図１のタイプのネットワークオンチップを模式的に示す。
【図５】図４のタイプのネットワークにおけるスループット割り当ての例を示す。
【図６】スループットリミッタの関与を示す図４のネットワークのリソースによるパケット送信の例を示す。
【図７】ルータのＦＩＦＯの最小サイズを可能にするテーブルと、スループットリミッタのパラメータの例に対して決定されるルータごとの最大レイテンシを示す。
【図８】スループットリミッタの詳細な実施形態を示す。
【図９Ａ】ルータの処理能力が一時的に超える結果となり得るパケットバースト状況を示す。
【図９Ｂ】ルータの処理能力が一時的に超える結果となり得るパケットバースト状況を示す。
【図９Ｃ】ルータの処理能力が一時的に超える結果となり得るパケットバースト状況を示す。
【図１０】パケットグルーピングの制限を可能にする解決を示す。
【図１１】図１０の解決の効率的な実施を可能にする回路の実施形態を示す。
【発明を実施するための形態】
【００３５】
図４は、改善を組み込んだ図１のタイプのネットワークオンチップを示し、この改善によって、ネットワークの最大レイテンシが、限度があり（bounded）かつ決定可能な値で、確立できる。この図は、図１のネットワークの要素を用い、これらの要素を同じ参照符号によって示す。
【００３６】
図示の実施形態に従って、各リソースRSCのネットワーク境界送信リンク（network bound transmission link）は、スループットリミッタ４０を備える。このスループットリミッタはたとえば、リソースのネットワークインターフェースに組み込まれる。
【００３７】
各スループットリミッタ４０は、テーブルを備え、このテーブルのレコードは、送信スループット割当量を各送信通信に関連づけ、各送信通信は、その対応するリソースによってネットワークの別の要素へ確立されることができる。
【００３８】
最適性能を保証するため、これらの割当量の選択に課せられる制約は、ネットワークセグメントにおける同じ方向に通過するような通信のスループットの総計が、このセグメントの最大送信スループット以下になることである。
【００３９】
割当量を計算するためのこの規則は、すべての通信によって取られるパスが知られていることを前提とする。これは、ネットワークオンチップにおいてどのような困難さも引き起こさず、ネットワークオンチップでは、簡単のため、通信のルーティングは静的であり、事前に定義されている。次に、このルーティング、さらに割当量は、不揮発性メモリに格納され、パワーアップ毎にチップにおいてプログラムされる、設定パラメータの形態を有する。
【００４０】
図５は、図４のタイプのネットワークにおけるスループットの割り当ての例を示す。上述した図３Aと同じノード表記が用いられている。
【００４１】
ノードN00は、送信通信を、ノードN01、N02を横断するノードN13へ確立することができる。
【００４２】
ノードN01は、２つの送信通信、１つはノードN11を横断するノードN10との通信、もう１つはノードN11,N12を横断するノードN13との通信を、確立することができる。
【００４３】
ノードN02は、ノードN12を横断するノードN13との送信通信を確立することができる。
【００４４】
ノードN10は、ノードN11,N12を横断するノードN13との送信通信を確立することができる。
【００４５】
最も求められているセグメントは、セグメントN12-N13であり、このセグメントは同じ方向に３つの通信を見ることができ、セグメントN01-N11およびN11-N12は、両方とも同じ方向における２つの通信を見ることができる。
【００４６】
通信へ割り当てられるスループット割当量の一例は、かっこの中に示されており、最大スループットが、１時間単位あたり、１６データユニットであることを前提としている。したがって、通信N00-N03は最大割当量１６を有しており、それは、この通信が、使用するセグメントにおける唯一の通信であるからである。すべての他の通信は、他の通信と共有されるセグメントを用い、したがって、最大スループットを分かち合わなければならない。８，４，４の割当量は、それぞれ通信N02-N13、N01-N13、N10-N13へ割り当てられ、これらの通信は最も混んでいるセグメントを通過する。このことは、通信N01-N10に対して１２の割当量を残す。
【００４７】
しかしながら、割当量の割り当てに課せられる制約は、多くのケースにおける柔軟性に対する余裕を残しておく。割当量の配分が、次に実行され、それはより大きな割当量を、帯域幅の観点で最も要求している通信に割り当てることによってなされる。
【００４８】
図６は、スループットリミッタ４０の特定の実施形態によって実施されるスループット制限の例を示す。この実施形態において、スループットリミッタは、固定された連続の時間区間（インターバル）で動作し、この固定された連続の時間区間は、以降、基準区間と称される。基準区間は、データユニットのバジェットに対応し、このバジェットは、１基準区間の間にセグメントにおける最大スループットで送信できるデータユニットの数である。通信のスループット割当量は、したがって、基準区間ごとのデータユニットにおいて表現されることができる。
【００４９】
ワームホールルーティングネットワークでは、各パケットは、ノードを介して移動する間、分割できず、そのワームホールルーティングネットワークの場合は、データユニットは、好ましくは、パケットで表現される。他のタイプのネットワークでは、データユニットは、異なる、たとえばワードであってもよい。
【００５０】
基準区間の期間は、好ましくはネットワークの各スループットリミッタ４０に対して同じである。各リミッタのレベルで、各基準区間が同時に開始する必要はないが、それらは好ましくは、同じ頻度でお互いに追随し、したがって、共通時間ベースの頻度で、同期する。
【００５１】
このタイプのネットワークを組み込むチップは、特に大きいことが可能であるため、チップの隔たった点の間で、技術的上の変動（variation）が存在するかもしれない。非同期であるルータの動作スピードは、したがって、地理的に変化することができる。リミッタは、同じ時間ベースで同期するため、基準区間の期間は、厳密に、チップの全体で一定のままである。より遅いルータに対しては、基準区間の期間は、バジェット未満に対応し、最も速いルータに対しては、バジェット越えに対応することができる。
【００５２】
フルスピードで動作する最も速いルータに対しては、最後のパケットの送信は、体系的に、各基準区間の終わりより前に、完了する。このことは、最後のパケットの終わりと区間の終わりの間で利用可能な帯域幅は、活用されないことを意味するが、これは、システムの満足のいく動作に影響を与えない。
【００５３】
フルスピードで動作する最も遅いルータに対しては、現在の区間の最後のパケットの送信は、体系的に、次の区間へあふれ出る。１つの結果は、ルータのFIFOは基準期間の間に完全には空にはならないということである。これは、従来のシステムよりもかなり低い可能性ではあるが、FIFOオーバーフローの危険をもたらし、それ故ノード間の通信ストールの危険をもたらす。
【００５４】
フェイルセーフアプローチにおいて、基準区間の期間は、それ故、最も遅いルータに応じて選択される。しかしながら、確率を評価して、最も速いルータに対応する期間を考慮して選択されてもよい。
【００５５】
バジェットの値は、通信へ割り当てられることができる割当量の粒度(granulartity)を定義する。バジェットが大きいほど、粒度はより細かく（finer）なるが、ネットワークにおける最大レイテンシはより高くなる。このバジェットの選択は、それ故、所望の粒度／レイテンシのトレードオフにしたがって、なされる。
【００５６】
図６において、３つの連続した時間区間が時間ｔ０，ｔ２，ｔ３開始する。リミッタに関連づけられたリソースは、２つの送信通信１，２を確立できる。２，１の各割当量のパケットが、たとえばこれらの通信に割り当てられる。
【００５７】
時間ｔ１において、最初の時間区間の過程において、リソースは２つの通信を開始する。通信１は、送信する５つのパケットを有し、一方、通信２は、送信する２つのパケットを有する。割当量は２および１であるため、リソースは、最初の時間区間の間、通信１の２つのパケットを送信でき、通信２の１つのパケットを送信できるのみである。リソースは、循環優先（circular priority）でパケットを送信すると仮定すると、通信１，２のパケットは、交互に図示のように送信される。
【００５８】
区間において通信がその割当量に達すると、リミッタはリソースに、この通信のための送信を停止するように信号を発する。そのときリソースはパケットをそのローカルメモリに格納し、次の区間で送信を継続するのを待機する。リソースは、待機時間を別のタスクおよび通信に活用することができる。
【００５９】
新たな時間区間が時間ｔ２で開始する。リソースは、通信２の最後のパケットを送信し、次いで、通信１の２つの新たなパケットを送信する。通信１はまだ終了せず、それは送信する１つのパケットをまだ持っているためである。
【００６０】
新たな時間区間が時間ｔ３で開始し、その時間区間の過程において通信１の最後のパケットが送信される。
【００６１】
図７は、ルータのＦＩＦＯの最小（かつ最適）サイズ、およびルータによってもたらされる最大レイテンシが、スループットバジェットが１６に等しい場合に決定されることを可能にするテーブルを示す。
【００６２】
このテーブルは、たとえば図２に表されるような、イーストマルチプレクサおよびそのＦＩＦＯメモリを参照する。
【００６３】
最初の４つの行は、マルチプレクサの４つの入力（Ｎ，Ｌ，Ｗ，Ｓ）のＦＩＦＯメモリのそれぞれに到着するパケットを示す。行ＱＥは、マルチプレクサ出力を表す。行ＦＮ，ＦＬ，ＦＷ，ＦＳは、ＦＩＦＯメモリのそれぞれに格納されているパケットの数を示す。最後の行は、出て行くパケットにより被られる、パケットの数におけるレイテンシを示す。
【００６４】
各列は、パケット送信サイクルに対応する。列の組は、基準時間区間に対応し、基準時間区間では、マルチプレクサは、スループットリミッタのため、最大で、ここでは１６であるバジェットに対応するパケットの数を処理する。この区間で受信されたすべてのパケットは、さらに同じ区間の過程で、出力される。
【００６５】
図示された状況は、入力の処理優先が循環される場合における、ＦＩＦＯレイテンシおよびサイズの最悪ケースの状況である。この状況は、バジェットの１６個のパケットが、２，２，３，９個のパケットが４つの異なる入力に到着して、図示のように、配信され、かつ、優先サイクルが、最も少ないパケットをもつＦＩＦＯが最初に選択されるような状態にたまたまなったときに、起こる。このテーブルは、入力Ｎ，Ｌ，Ｗ，Ｓの順の循環優先の場合に対して作成され、入力Ｎ，Ｌ，Ｗ，Ｓはそれぞれ、２，２，３，９個のパケットを受信する。
【００６６】
サイクル０では、最初の４つのパケットが、４つの各ＦＩＦＯに到着する。ＦＩＦＯ  ＦＮは直ちに処理され、そのパケットＮ０は、マルチプレクサによって送信される。パケットＬ０，Ｗ０，Ｓ０は、ＦＩＦＯ  ＦＬ，ＦＷ，ＦＳに格納される。ＦＩＦＯ  ＦＮ，ＦＬ，ＦＷ，ＦＳはしたがって、それぞれ０，１，１，１個のパケットを含む。
【００６７】
サイクル１では、マルチプレクサは、ＦＩＦＯ  ＦＬに含まれるパケットＬ０を送信し、一方、新たなパケットＮ１，Ｌ１，Ｗ１，Ｓ１が到着し、ＦＩＦＯ  ＦＮ，ＦＬ，ＦＷ，ＦＳに書き込まれる。これらのＦＩＦＯはそれぞれ、１，１，２，２個のパケットを含む。
【００６８】
サイクル２では、マルチプレクサは、ＦＩＦＯに含まれるパケットＷ０を送信し、一方、２つの新たなパケットＷ２，Ｓ２が、ＦＩＦＯ  ＦＷ，ＦＳに到着する。ＦＩＦＯ  ＦＮ，ＦＬ，ＦＷ、ＦＳはそれぞれ、１、１，２，３個のパケットを含む。
【００６９】
サイクル３では、マルチプレクサは、ＦＩＦＯ  ＦＳに含まれるパケットＳ０を送信し、一方、パケットＳ３が、ＦＩＦＩ  ＦＳに到着する。ＦＩＦＯにおけるパケットの数は、前回のサイクルと比較して、変わらない。
【００７０】
次の５回のサイクルのそれぞれで、新たなパケットＳが、ＦＩＦＩ  ＦＳに到着し、一方、ＦＩＦＯは、循環的に、読み出し続けられる。ＦＩＦＯ  ＦＮ，ＦＬ，ＦＷは、最後のパケットＳ８の到着で、すべて空である。１６個のパケットのバジェットがその結果達せられ、次の時間区間間で、マルチプレクサに対し到着するパケットはこれ以上、ない。
【００７１】
７回の残りのサイクルの間、ＦＩＦＯ  ＦＳは各サイクルで読み出され、最後のパケットＳ群を抽出する。
【００７２】
ＦＩＦＯに格納されるパケットの最大数は７であることが理解されることができ、この７は、達せられた最大レイテンシに対応する。レイテンシは、パケットの出力サイクルのインデックスと、パケットの入力サイクルのインデックスとの間の差異である。
【００７３】
したがって、１６のバジェットと、循環優先でスループットリミットを用いることによって、各ルータでもたらされる最大レイテンシは、７パケットである。この値は、あるタイプのルータ（パイプラインルータ）によってもたらされる既知の体系的遅延（systematic delay）によって増加されることができる。ネットワークの最大レイテンシは、その結果、２つのノード間のパス上のルータの最大数に、ルータの最大レイテンシを乗じた値に等しい。
【００７４】
それ故、レイテンシは、限度がありかつ決定可能であり、それによってこの解決は、クオリティ・オブ・サービス（サービスの質）を提供し、リアルタイムアプリケーションに適合性がある。
【００７５】
これ例において最も求められるＦＩＦＯメモリは、７個のパケットの深さをもつ。もし異なるメモリが各ＦＩＦＯに対して用いられるならば、各１つが、７個のパケットの深さをもつ。各マルチプレクサに対して必要な全体メモリサイズは、その結果、２８パケットである。
【００７６】
あるルータ構成では、ＦＩＦＯメモリは、適当な管理状態マシンに関連する単一メモリで実装される。この場合、そのメモリは、すべてのＦＩＦＯに一緒に格納されるパケットの数が最大である状況において、すべてのパケットを含むための十分な空間をもっている。この状況は、パケットバジェットがルータ入力、すなわち図７の例をとるＦＩＦＯごとの４つのパケット（入力）、全体で等しく分配されるときに生じる。そのとき、マルチプレクサに関連するＦＩＦＯはともに最大で１２個のパケットを格納することが確認されることができる。
【００７７】
それ故、４つのＦＩＦＯの機能を実行するように動作する単一メモリは、１２パケットのサイズを有する。このサイズは、すべてのＦＩＦＯによって一緒に格納されるパケットの数がこの状況では合計で７に達するのみであるため、図７の最大レイテンシ状況と適合する。
【００７８】
最大レイテンシの決定が、特定のバジェットおよび優先管理ケースに対してこれまでのべられてきた。この計算を他の状況に適用できるであろう。
【００７９】
図１に関連して述べられたタイプの従来のネットワークオンチップでは、ＦＩＦＯオーバーフロー防止メカニズムが言及され、このメカニズムでは、ルータは、前のルータに対し、そのＦＩＦＯのうちの１つが一杯であるときにもはやデータを受信できないことを表示する（ハンドシェイクメカニズム）。これは、ＦＩＦＯオーバーフローの危険があることを意味する。ここで述べられたスループット制限のおかげで、ＦＩＦＩは、そのサイズがここで述べたように選択され、かつ割当量が適切に割り当てられるならば、決してオーバーフローするようなことはない。すなわち、ネットワークは、ハンドシェイクメカニズムを無くして簡単化されることができる。
【００８０】
システムが述べられてきたように、割当量は、ルーティングを定義する設計者の責任の下、自由に割り当てることができ、すなわち、設計者は、バジェットがあるセグメントにおいて超えられるように、割当量を割り当てることができる。このバジェット超過はさらに、たとえばもし設計者が同じセグメントをとる２つの通信が決して同時ではないことを知っているならば、故意的であることも可能である。誤りの危険を回避するためには、ハンドシェイクメカニズムが好ましい。しかしながら、設計者が、割当量割り当てに従っていることを検証するコンピュータツールを体系的に使用するならば、ハンドシェイクメカニズムは、不必要である。
【００８１】
図８は、通信に関連するスループットリミッタ４０の実施形態を示す。スループットリミッタ４０は、通信割当量が記録されるレジスタ８０を備える。カウンタＣＮＴは、信号ＰＫＴによってクロックされ、信号ＰＫＴは、送信される各パケットに対するパルスを表す。カウンタＣＮＴはさらに信号ＲＴＣによって周期的に再初期化され、その信号ＲＴＣは、システムに共通の時間ベース、たとえばリアルタイムクロックによって確立されるものである。この信号ＲＴＣは、一続きの参照時間区間を決定する。
【００８２】
比較器８２は、カウンタＣＮＴの内容がレジスタ８０に含まれる割当量に等しくなったとき、通信の停止信号ＳＴＯＰを活性化させる。次の時間ベースパルスＲＴＣで、カウンタＣＮＴは再初期化され、信号ＳＴＯＰが非活性化される。
【００８３】
そのようなスループットリミッタは、関連するリソースが確立することができる各送信通信に関連する。リソースによって現在送信される通信は、管理状態マシンによって決定される。管理状態マシンは、送信されるパケットを、関連するルータに方向付け、パケットのカウントを保つ（キープする）。この状態マシンは、パケットＰＫＴのクロックの信号を、現在の通信に対応するリミッタに方向付け、この同じリミッタのＳＴＯＰ信号を考慮（take account of）するように設計される。状態マシンがＳＴＯＰ信号を受け取るとすぐ、現在の通信を停止し、もし存在すれば次の通信へ切り替える。パケットが分割不可の場合、もしＳＴＯＰ信号がパケットの送信の間に受信されると、通信は、そのパケットの最後のワードが送信された後、停止される。
【００８４】
ネットワークの記述が、明確のため、これまでかなり簡単で、最もありそうな状況で、なされてきた。ここで述べられたタイプのネットワークは、実際、ある通信において、局所化されかつ一時的なスループットオーバーシュートへつながるパケットバースト現象に施されることができる。この一時的なスループットオーバーシュートは、この現象に対処するため、伴われるルータのＦＩＦＯメモリのサイズを増大する必要につながる。この現象は、スループットバジェットが８（基準区間あたり８パケット）である簡単な場合の枠組み（frame)において、以下に例示される。
【００８５】
図９Ａは、５の割当量を有する通信の、ウェストからイーストへのパス上の連続するノードを表す。さらに、各ノードは、他の３つの方向のそれぞれで割当量１の通信を受信し、これらの通信のそれぞれは、そのノードのイースト出力へ方向づけられる。表示されるノード間のセグメントのそれぞれは、それゆえ、８の最大容量にある。明確のため、割当量１の通信のそれぞれの、到着される各２番目のノードでの出力方向は、表示されていない。この方向は、ノース、サウス、ローカルのうち、任意の方向でよい。
【００８６】
図９Ｂは、図９Ａの構成で、たとえば図９Ａの１番目のノードのイーストルータの段階で発生することができるパケットバースト現象の始まりを示す。ルータの入力Ｎ，Ｌ，Ｓの任意の１つを介して到着するパケットは、“Ｘ”と表記される。ウェスト入力（Ｗ）を介して到着するパケットは、“ｗ”と表記される。
【００８７】
最初の３つのサイクル０，１，２の間は何も発生しない。サイクル３では、ルータは、その４つの入力のそれぞれでパケットを受信する。続く４つのサイクルのそれぞれでは、入力Ｗがパケットを受信する。バジェットは、この区間の終わりでちょうど費やされる。
【００８８】
５つの新しいパケットが、次の区間のまさに始まり、サイクル８〜１２で、入力Ｗに到着する。他の入力ではパケットは到着しない。この状況は、３番目の区間で繰り返される（完全には表示されていない）。
【００８９】
入力の循環優先処理が入力Ｗで終了する場合、ルータの出力ＱＥは、表示されるとおりである。パケットＸはサイクル３〜５で出力され、パケットｗは、続くサイクルで出力される。サイクル６からのように、出力ＱＥは、１５のグループ化されたパケットｗを与える。これらのパケットはすべて、次のノードのルータＥの入力Ｗに到着する。このルータは特に８個のパケットｗと、できる限り３つの他のパケット、すなわちバジェットを超える３つのパケットを、単一の基準区間の中で、処理しなければならない。
【００９０】
各続くノードで、５つのパケットｗの新たなシーケンスが、このように、以前のシーケンスとグループ化されることができる。これは、特に、図９Ｂに示される状況が、横断する各ノードで繰り返されるときに起こる。
【００９１】
図９Ｃは、図９Ａの２番目および４番目の段階で、起こりうる続くイベントを示す（それぞれテーブルの最初の半分と、２番目の半分）。ルータの入力Ｎ，Ｌ，Ｓ，Ｗは、ノード番号（２，４）によって索引づけられる。
【００９２】
図９Ｂのルータの出力ＱＥによって与えられるパケットｗは、サイクル６から開始する入力Ｗ２に到着する。そのルータの他の入力Ｎ２，Ｌ２，Ｓ２はそれぞれ、サイクル６，８，１６，２４でパケットＸを受信し、それは、まさにパケットｗの到着の開始であり、続く基準区間の各開始である。
【００９３】
入力の循環優先処理が入力Ｗ２で終わる場合、ルータの出力ＱＥは図示されるとおりである。行ＦＷは、各サイクルでのＦＩＦＯＷの満たし状態を示す。満たし状態が、処理されるパケットの数が３だけバジェットを超える基準区間の後、サイクル１８からのように、最大の９に達することが認められる。
【００９４】
４番目のルータに対応する、テーブルの２番目の部分において、入力Ｗ４によって受信されるパケットは、横断する２つのノードの後、図９Ｂのシーケンスに対応し得るシーケンスで到着する。このシーケンスは、サイクル１２で開始する２５個のパケットｗの連続フローを含む。
【００９５】
さらに、サイクル１２で、ルータの他の入力Ｎ４、Ｌ４、Ｓ４はそれぞれパケットＸを受信する。次の区間の開始、すなわちサイクル１６，２４，３２で、ルータはさらに入力Ｎ４，Ｌ４，Ｓ４のそれぞれでパケットＸを受信する。
【００９６】
出力ＱＥは再度、入力Ｗ４が最後に処理されるような優先の場合に対応する。ＦＩＦＯ  Ｗの満たし状態が、パケットの数がバジェットを３だけ超えた２つの連続する基準区間を処理しなければならなくなった少し後、サイクル２６で１２の最大に達することが理解される。
【００９７】
これらの簡単化された例は、ＦＩＦＯのサイズが、通信が横断することができるノードの最大数に応じて、選択されなければならないことを示す。
【００９８】
ここで述べられたスループット制限をもったネットワークは、実際、“（σ、ρ）-規則”をもったネットワークの特定の場合に起こり、その一般的な理論は、たとえば、本願の導入部で述べたRene L. Cruzによる文献に述べられている。用語σは通信の最大バーストサイズを指定し、ρは長期間（long-term）スループットを意味する。
【００９９】
ここで述べられたネットワークに適用されるこの理論は、ＦＩＦＯの最大の満たし状態が、Ｆ＋３ｈに等しいことを明らかにし、ここでＦはバースト現象を考慮しないでＦＩＦＯに対して計算される最大サイズであり（区間あたり１６パケットのバジェットを用いたＦ＝７が見られてきた）、ｈは通信に伴われるノードの最大数である。用語“３”はルータの入力数より１少ないことに対応する。
【０１００】
通信パスが事前に固定されているとすると、通信に伴われる最大ノード数は知られている。さらに、ネットワークによってもたらされる最大レイテンシを決定するＦＩＦＯの最小サイズが、それゆえ、計算されることができる。
【０１０１】
ＦＩＦＯのサイズが、伴われる最初のノードからのように、３パケットだけ上昇することがわかる。これは、図９Ｂに示される事実に起因し、その事実とは、最初の基準区間のバジェットがその区間の終わりでのみ用いられることができ、かつそのバジェットが次の区間の開始で到着するパケットを用いて、最初のノードからのように、グルーピングを起こすことができる、ということである。
【０１０２】
最初に伴われるノードへ関連するこのエッジ効果は、スループットリミッタを次のように構成することで避けることができる。それは、次の区間まで、区間の最後の３つのサイクルで到着するパケットを、３より大きなバジェットの通信のために、先送りにすることである。
【０１０３】
図１０は、ＦＩＦＯの、それゆえネットワークのレイテンシの、最小サイズにおけるかなりの減少を可能にする解決を示す。
【０１０４】
リソース１０１とリソース１０３間の通信は、６個のノードを伴う。このネットワークにおいて通信に伴われるノードの最大数を６と仮定すると、バジェットが区間あたり１６パケットである場合、ＦＩＦＯのサイズは、少なくともＦ＋３×６、すなわち２５に少なくとも等しく、選択される。したがって最大レイテンシは５×２５＝１２５パケットである。
【０１０５】
ＦＩＦＯのサイズを減少させるため、最も長いパスは仮想的により短いパスへ分解（ブレークダウン）される。このため、図１０に示されるように、通信が中間ノードで抜け出るようになされ、この中間ノードは、あたかもこのノードへ到来する通信が存在するかのように、すなわち、そのノードのスループットリミッタを通過する通信が存在するかのように、その通信をネットワークへ再注入する。この場合におけるスループットリミッタは、その通信へ割り当てられた割当量を順守しつつ、いくつかの基準区間にパケットバーストが再度広がることを確実にする。
【０１０６】
したがってＦＩＦＯのサイズは、この分解から生じる最も長いサブパスにしたがって選択される。図１０の例では、もっとも長いサブパスは4個のノードを伴い、その結果、ＦＩＦＯサイズは、７＋３×４＝１９パケットになり、レイテンシは３×１９＝５７パケットになる。
【０１０７】
この“分解”技術は、その通信によって被られる遅延を全体的（グローバル）には上昇させない。中間ノードによって受信される最初のパケットは、グルーピング現象に起因して最大の遅延を被ったパケットであり、実際は、直ちに再送信されるものである。最後のパケットは、最小の遅延を被ったものであり、それらのパケットが後の基準区間で再送信される事実は、単にそれらの遅延を、最初のパケットによって被られた遅延と等しくする。さらに、この通信の割当量はすでにこのパスで保存されており、中間ノードは、この同じパスにおける他の通信の割当量によって許容されるより大きく、通信に影響を与えることができない。
【０１０８】
この分解技術は、中間ノードを横断するいくつかのサブ通信へ通信を論理的に分解することによって、完全にソフトウェアによって実施されてもよい。各中間ノードは、その通信を別のノードに単に再現することによってその通信を処理するタスクを実行する受信体になる。
【０１０９】
しかしながら、そのような実装は、最後の受信体に通信における無視できない遅延をもたらすような処理オーバーヘッドをともなわない。
【０１１０】
図１１は、この分解技術のハードウェア実装を可能にする非常に簡単な回路を模式的に示す。ノードに接続されたリソースＲＳＣは、ネットワーク上に再送信されるパケットを格納するためのＦＩＦＯメモリ１１０を備える。
【０１１１】
ノードのルータＬから来る、到来リンクＬは、デマルチプレクサ１１２に着く。このデマルチプレクサの制御ロジックは、ローカルリソースに対して意図されたパケットを認識するように設計され、その場合、パケットは、ラインＩＮ−Ｌを介してローカルリソースへ送られ、または、ネットワーク上で再送信されるよう意図されたパケットを認識するように設計され、その場合、パケットがＦＩＦＯメモリ１１０に積み重ねられる。
【０１１２】
マルチプレクサ１１４の出力は、スループットリミッタ４０を用いて、ノードの入力Ｌに接続される。マルチプレクサ１１４は、ラインＯＵＴ−Ｌを介してローカルリソースから来るパケットと、ＦＩＦＯメモリ１１０からのパケットとの間での選択を実行する。
【０１１３】
分解通信のパケットには、中間ノード（あるいは複数の中間ノード）を識別するヘッダが設けられる。ワームホールルーティングの場合、ヘッダは、通常、横断ノードごとに、２つのビットを含み、これらのビットは、各ノードの段階での次の方向を示す。各中間ノードに対するこの“次の方向”は、ローカル方向であろう。
【０１１４】
ノードは次に、パケットをそのルータＬへ向かわせ、ルータＬでは、デマルチプレクサ１１２に到着する前から、ルータの対応するＦＩＦＯ（図１０の場合におけるＦＩＦＯ  Ｗ）において、その折り返し（turn）を待機する。デマルチプレクサ１１２は、そのパケットの性質を認識し、それをＦＩＦＯメモリ１１０内に積み重ねる。ＦＩＦＯメモリ１１０におけるそのパケットの到着は、マルチプレクサ１１４に示され、マルチプレクサ１１４は、スループットリミッタ４０によって決定される利用可能なバジェットを考慮して、そのパケットをネットワーク上に再送信する役割を有する。
【０１１５】
パケットの性質（“ローカルリソース向けである”あるいは“再送信される”）は、ヘッダ内で運ばれる通信識別子を、ローカルルーティングテーブルと比較することで、認識されることができる。このルーティングテーブルは、ネットワークのすべての通信識別子とそれらの宛先、または、ローカルリソースに対して意図される通信の識別子のみ、を含むことができる。前者の場合、パケットヘッダは、中間ノードへパケットを運ぶパスを含むことのみ必要である。パケットを再送信する際、中間ノードは、パケットの最終宛先へのパスを確立し、そのパスをパケットに挿入することができる。
【０１１６】
後者の場合、パケットヘッダは、最終宛先への完全なパスを含み、さらに中間ノードを識別する情報を含む。中間ノードは、そのルーティングテーブルにおいて通信識別子を見つけず、そのパケットは再送信されるべきであると決定する。パケットは再送信され、そのヘッダ内に、最終宛先へ取られるべきパスの残りを含む。
【０１１７】
このように再送信されるパケットは次に、ローカルリソース自体を起源とするパケットのように、処理される。
【０１１８】
パケットは、各中間ノードにおける２つのルータのＦＩＦＯ、すなわちルータＬのＦＩＦＯ、次に最終宛先を指し示すルータのＦＩＦＯ、を介して通過しなければならないことに気づくことができる。さらに、そのようなパケットは、ローカルリソースに入ってくる通常の通信と重ね合わさることが可能である。このことが引き起こしうる問題を避けるためは、中間ノードは、そのローカルリソースの到来通信が存在しない、または少なくとも低スループットからなるように、選択されるべきである。
【０１１９】
この問題を避ける別の解決は、ノードが、そのようなパケットを直接、ＦＩＦＯ１１０に、ルータＬを横断することなく、送信することである。このことは、ノードとローカルリソースとの間に設けられる追加のバスを必要とする。デマルチプレクサ１１２は結果としてもはや必要でない。
【０１２０】
各リソースの段階で設けられる図１１のような回路によって、通信分解を実施することが特に容易になる。１つ以上の中間ノードはパケットヘッダにおいて簡単に識別され、その残りを扱うのはこれらの中間ノードである。この動作は、ネットワーク設計者によって手作業で実行されることができ、またはパスの長さを最適化するように図られた設計ツールによって自動化された態様で実施されることができる。
【図１】
2011035906.tif 000003
【図２】
2011035906.tif 000004
【図３Ａ】
2011035906.tif 000005
【図３Ｂ】
2011035906.tif 000006
【図４】
2011035906.tif 000007
【図５】
2011035906.tif 000008
【図６】
2011035906.tif 000009
【図７】
2011035906.tif 000010
【図８】
2011035906.tif 000011
【図９Ａ】
2011035906.tif 000012
【図９Ｂ】
2011035906.tif 000013
【図９Ｃ】
2011035906.tif 000014
【図１０】
2011035906.tif 000015
【図１１】
2011035906.tif 000016