JP5661365B2 - クオリティ・オブ・サービスを伴ったネットワークオンチップ - Google Patents

Description

本願発明は、システムオンチップ（ＳｏＣ）に関し、より詳細には、ネットワークオンチップ（ＮｏＣ）におけるデータフロー管理に関する。

図１は、マトリックス（またはメッシュ）トポロジーのネットワークオンチップの一例を示し、それはヨーロッパ特許ＥＰ１７０１２７４に記述されている。

このネットワークは、行に配置された複数のバス（水平バスＢｈ）と、列に配置された複数のバス（垂直バスＢｖ）を備える。ルータＲＴＲは、水平バスと垂直バスの各交差部に配置され、ルータに到達する各（水平および垂直）バスセグメント間にポイント・ツー・ポイントが作られるのを可能にする。さらに、各ルータＲＴＲは、データ生成部またはデータ消費部であることが可能であるローカルリソースＲＳＣに接続されている。

この種のネットワークは、任意のリソースＲＳＣに、任意の他のリソースと通信させるように設計される。互いに通信するリソースおよびその通信がとるパスは、概して事前に決定され、ネットワーク管理ロジックにプログラムされている。

通信はデータパケットでなされることが多い。パケットは、バスの幅をもつワード組であり、ワード組において、パケットに関連する情報、特に宛先を含むヘッダが先にくる。

通信ネットワーク、たとえばＡＴＭにおいて、さまざまな技術が、クオリティ・オブ・サービス（サービスの質）を与えるのに用いられる。これらの技術は一般的に、ネットワーク入力ノードに課せられるスループット制限に基づいている。文献“ネットワーク遅延の計算法、パートＩ：孤立したネットワーク要素”（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）を待機する。デマルチプレクサ１１２は、そのパケットの性質を認識し、それをＦＩＦＯメモリ１１０内に積み重ねる。ＦＩＦＯメモリ１１０におけるそのパケットの到着は、マルチプレクサ１１４に示され、マルチプレクサ１１４は、スループットリミッタ４０によって決定される利用可能なバジェットを考慮して、そのパケットをネットワーク上に再送信する役割を有する。

パケットの性質（“ローカルリソース向けである”あるいは“再送信される”）は、ヘッダ内で運ばれる通信識別子を、ローカルルーティングテーブルと比較することで、認識されることができる。このルーティングテーブルは、ネットワークのすべての通信識別子とそれらの宛先、または、ローカルリソースに対して意図される通信の識別子のみ、を含むことができる。前者の場合、パケットヘッダは、中間ノードへパケットを運ぶパスを含むことのみ必要である。パケットを再送信する際、中間ノードは、パケットの最終宛先へのパスを確立し、そのパスをパケットに挿入することができる。

後者の場合、パケットヘッダは、最終宛先への完全なパスを含み、さらに中間ノードを識別する情報を含む。中間ノードは、そのルーティングテーブルにおいて通信識別子を見つけず、そのパケットは再送信されるべきであると決定する。パケットは再送信され、そのヘッダ内に、最終宛先へ取られるべきパスの残りを含む。

このように再送信されるパケットは次に、ローカルリソース自体を起源とするパケットのように、処理される。

パケットは、各中間ノードにおける２つのルータのＦＩＦＯ、すなわちルータＬのＦＩＦＯ、次に最終宛先を指し示すルータのＦＩＦＯ、を介して通過しなければならないことに気づくことができる。さらに、そのようなパケットは、ローカルリソースに入ってくる通常の通信と重ね合わさることが可能である。このことが引き起こしうる問題を避けるためは、中間ノードは、そのローカルリソースの到来通信が存在しない、または少なくとも低スループットからなるように、選択されるべきである。

この問題を避ける別の解決は、ノードが、そのようなパケットを直接、ＦＩＦＯ１１０に、ルータＬを横断することなく、送信することである。このことは、ノードとローカルリソースとの間に設けられる追加のバスを必要とする。デマルチプレクサ１１２は結果としてもはや必要でない。

各リソースの段階で設けられる図１１のような回路によって、通信分解を実施することが特に容易になる。１つ以上の中間ノードはパケットヘッダにおいて簡単に識別され、その残りを扱うのはこれらの中間ノードである。この動作は、ネットワーク設計者によって手作業で実行されることができ、またはパスの長さを最適化するように図られた設計ツールによって自動化された態様で実施されることができる。

Claims (8)

1. メッシュネットワークにおける通信のスループットを制限する方法であって、
   前記メッシュネットワークにおける複数の送信元ノードと複数の宛先ノード間の可能性ある通信に静的パスを割り当て、複数の静的パスが、隣接するネットワークノード間の同じメッシュセグメントを通過する、ステップと、
   前記静的パスにそれぞれの静的スループット割当量を割り当てて、任意のメッシュセグメントにおいて、前記メッシュセグメントを通過するすべてのパスへそれぞれ割り当てられた静的スループット割当量の総計が、最大で前記メッシュセグメントの公称スループットに等しくなるようにするステップと、
   それぞれの静的パスにおいて、現在の通信のデータユニットを送信するステップと、
   前記通信の送信元ノードで前記現在の通信のスループットを測定し、前記それぞれの静的パスの静的スループット割当量が達せられたとき、前記送信元ノードでの前記現在の通信を一時的に停止するステップと、
   を備えた方法。
2. 各メッシュセグメントの公称スループットは、基準時間区間に渡るデータユニットのバジェットによって表され、各静的スループット割当量は、前記データユニットのバジェットのそれぞれの割当量によって表され、
   前記方法は、
   前記現在の通信のデータユニットを、繰り返しの基準時間区間に渡って送信するステップと、
   各基準時間区間の間、前記現在の通信のデータユニットを計数することによってスループットを計測するステップと、
   前記現在の通信のデータユニットの計数値が、前記それぞれの静的パスに割り当てられた前記静的スループット割当量に達したとき、前記現在の通信を停止するステップと、
   前記現在の通信を、次の基準時間区間で再開するステップと、
   を備えた請求項１に記載の方法。
3. 前記現在の通信の送信元および宛先間の中間ノードの段階で、追加のスループット制限を前記現在の通信に施すステップを備えたことを特徴とする請求項２に記載の方法。
4. 前記追加のスループット制限は、
   前記中間ノードへ接続されたリソースによって前記現在の通信を受信するステップと、
   前記ネットワーク上で前記リソースによって前記現在の通信を再送信するステップと、
   を含むことを特徴とする請求項３に記載の方法。
5. それぞれの静的に割り当てられた静的パスを介して複数の宛先ノードへ通信を開始することが可能であり、隣接するネットワークノード間で複数の静的パスが同じメッシュセグメントを通過する、複数の送信元ノードと、
   前記静的パスの送信元ノードにおいて、動作中、隣接するネットワークノード間の任意のメッシュセグメントにおいて、前記メッシュセグメントを通るすべての静的パスへそれぞれ割り当てられた静的スループット割当量の総計が、最大で前記メッシュセグメントの公称スループットに等しくなるように静的に決定された、前記静的パスに割り当てられた静的スループット割当量に対応する一定値を記憶する、各静的パスに対するメモリーロケーションと、
   前記送信元ノードで開始する静的パスにおける現在の通信のスループットを測定し、前記静的パスに割り当てられた静的スループット割当量が達せられたとき、前記現在の通信を停止するように構成された、各送信元ノードにおけるスループットリミッタと、
   を備えたメッシュネットワーク。
6. 前記スループットリミッタは、
   前記現在の通信によって送信されるデータユニットを計数するカウンタと、
   前記カウンタを周期的に再初期化するように構成されたタイムベースであって、前記タイムベースの周期は、スループットバジェットを表すデータユニットの数の前記メッシュセグメントにおける前記公称スループットでの送信時間に対応する、タイムベースと、
   前記カウンタが前記現在の通信の前記静的パスへ割り当てられた前記静的スループット割当量に対応する値に達したとき、前記現在の通信を停止するように構成された回路と、
   を備えた請求項５に記載のメッシュネットワーク。
7. 宛先ノードは、前記現在の通信の中間受信体としての前記宛先ノードを識別し、前記宛先ノードのスループットリミッタを介して前記メッシュネットワークへ前記現在の通信を再送信するように構成された回路を備えた請求項６に記載のメッシュネットワーク。
8. 前記回路は、前記現在の通信のヘッダデータユニットによって運ばれるノード識別子で動作する請求項７に記載のメッシュネットワーク。

Images