(57)【特許請求の範囲】
【請求項１】
各々が同じ行に属する２つの他のルータおよび同じ列に属する２つの他のルータに接続されたインフラルータからなるマトリックスと、
各々が同じ行または同じ列に属する他の２つのルータに２つの内部入力によって接続されており、ネットワークにデータを供給する外部入力を備える入出力ルータと、
を備えるトーラスネットワークであって、
前記各入出力ルータは、内部入力用のキューを有さず、且つ、前記入出力ルータに接続されたインフラルータのキューを管理するようにも構成されたアービターにより管理された外部入力に割り当てられたキューを備えることを特徴とするトーラスネットワーク。
【請求項２】
前記アービターは、前記インフラルータのキューと組み合わせて前記入出力ルータのキューを管理するように構成されて、それにより前記２つのルータの組み合わせが６チャネルルータとして振る舞うことを特徴とする請求項１に記載のネットワーク。
【請求項３】
前記各入出力ルータは、２つの入力を持つマルチプレクサを備え、その第１の入力が前記入出力ルータの前記キューの一つからデータを受信し、その第２の入力が前記インフラルータから直接データを受信することを特徴とする請求項１に記載のネットワーク。
【請求項４】
前記アービターは、
データが前記入出力ルータのキューの一つに達すると要求信号を生成し、アクノリッジ信号を受信するとすぐにそのデータの送信を生じさせるように構成された、前記入出力ルータにおける第１の制御回路と、
前記インフラルータのキュー間の優先権を管理するように構成され、前記要求信号を受信するとすぐに前記入出力ルータのキューを優先権管理に含める、前記インフラルータにおける第２の制御回路であって、前記第２の制御回路は前記入出力ルータのキューが優先権を持っていると判定すると、前記アクノリッジ信号を生成する、前記インフラルータにおける第２の制御回路と、
を備えることを特徴とする請求項１に記載のネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オンチップネットワーク（ＮＯＣ）トポロジーに関し、特に、メッシュネットワークにおける入出力ノードの配置に関する。
【背景技術】
【０００２】
図１は、特許文献１に記載されたマトリックス（即ち、メッシュ）ＮＯＣトポロジーの一例を示している。
【０００３】
このネットワークは、行（水平バスＢｈ）及び列（垂直バスＢｖ）をなして配置された複数のバスを備えている。ルータＲＴＲは、水平バスと垂直バスの各交点に置かれており、該ルータに到達する各バスセグメント（水平および垂直）間のポイントツーポイント接続を行う。さらに、各ルータＲＴＲはローカルリソースＲＳＣに接続される。このローカルリソースは、データプロデューサ又はデータコンシューマであり得る。
【０００４】
この種のネットワークは、任意のリソースＲＳＣに他の任意のリソースと通信させるように設計されている。通信は、最終目的地にデータをルーティングする担当のいくつかのルータを横断する。
【０００５】
通信が横断するノードの数を制限するために、ネットワークは環状体（toroidal）であることが好ましい。図示するように、マトリックスの端に置かれたルータは、マトリックスの反対側の端に置かれたルータと接続されている。これにより、マトリックスの端と中央の両方において、同一のルータ構造を用いることが可能となる。
【０００６】
図２は、これに関連して使用可能なルータを概略的に示している。このルータは５つのチャネル、即ち、バスセグメントに対応する４つの方向、つまり北（Ｎ）、南（Ｓ）、東（Ｅ）、西（Ｗ）と、ローカルリソースに対応するリンクＬとを管理する。
【０００７】
４入力マルチプレクサＭＸは、各ルータ出力方向と関連している。これら４つの入力は、マルチプレクサの方向と関連のないルータ入力に対応している。例えば、北側出力マルチプレクサＭＸＮは、ルータ入力Ｌ，Ｓ，Ｅ及びＷを受信する。即ち、このルータは、ある方向経由で入力されたパケットが同じ方向経由で出て行くことを防止する。
【０００８】
また、各マルチプレクサ入力の前には、待機出力データを蓄積することを目的としたＦＩＦＯキュー２０が置かれている。
【０００９】
コントローラ２２は、調停を行い、マルチプレクサによりなされる選択、及び５つのチャネルを介して入力するデータのキュー２０への書き込みを制御する。
【００１０】
図１の種類のネットワークの１つの想定される用途は、並列コンピューティングである。この場合、各リソースＲＳＣはプロセッサクラスターである。よって、そのようなネットワークは、少なくとも計算用データの供給および計算結果の抽出を可能とする入出力周辺装置と関連する。
【００１１】
迅速な解決策は、所要の入出力動作を行うために、リソースＲＳＣのいくつか、好ましくは、チップを外界に接続するコンタクトパッドを用いた接続を容易にするために、マトリックスの端に置かれたリソースを使用することである。
【００１２】
この解決策は、同一のマトリックスの大きさに対して、ＮＯＣの計算能力に損をさせる。ある数のプロセッサクラスターは、プロセッサクラスターが提供可能なものよりもずっと低い計算要求の入出力ユニットに置き換えられる。しかし、この特異性、特に外界との接続を有するという事実は、共用の時間においてさえ、それらの機能をプロセッサクラスターによって満たすことができないということを必然的に伴う。
【００１３】
よって、所定の計算能力を提供するためにマトリックスをある大きさに作った場合、ネットワークの周りに入出力ユニットを追加しなければならないだろう。設計者のなす選択によるが、この追加により、ネットワークの待ち時間（latency）が著しく増加する、及び／又は、チップの表面積が徒に増加するだろう。
【００１４】
所定のマトリックスに入出力ユニットを追加することに対して想定され得る一つの解決策は、マトリックスの周辺にルータからなる２つの列および２つの行を追加し、それに入出力ユニットを接続することにある。従って、ルータマトリックスの大きさはｎ×ｎから（ｎ＋２）×（ｎ＋２）に増大し、このことは、おそらく通信により横断されるノードの数を増加させ、それによりネットワークの待ち時間を増大させるだろう。
【００１５】
もう一つの解決策は、６チャネル周辺ルータを用いることにあるだろう。６番目のチャネルは入出力ユニットを接続する目的に役立つものである。この解決策は、例えば特許文献２に記載されているが、周辺ルータが内部ルータに比べて大きな表面積を有し、そのことがルータの配置・配線問題（place-and-route problems）を引き起こすという欠点がある。設計の簡素化の理由から、全てのルータは同一であり、従って全てが６つのチャネルを有することが好ましい。この場合、内部ルータは、不必要な表面積を占める使わない機能を有することになるだろう。
【００１６】
暗示の目的のために、図２のルータと比較して、６チャネルルータはもう一つのマルチプレクサを備え、各マルチプレクサは対応するＦＩＦＯメモリを持つ５つの入力を有するだろう。
【００１７】
図３は、特許文献３において提案された、これらの欠点を扱う解決策を図示している。図３は図１のそれと同様のトーラスネットワークを示している。「入出力ルータ」としての資格を有する３チャネルルータＩＯＲが、マトリックスの周辺に挿入されている。これらのルータＩＯＲの各々のチャネルのうち２つは、内部としての資格が与えられ、ルータが置かれた行または列の連続性を確保する目的に役立つ。３番目のチャネルは、外部としての資格が与えられ、入出力ユニットＩＯＭによりネットワークからデータを挿入および抽出する目的に役立つ。
【００１８】
「インフラルータ」と呼ばれる内部ルータＲＴＲを違って、行に設置されたルータＩＯＲは同じ列のルータに接続されない。同様に、列に設置されたルータＩＯＲは同じ行のルータに接続されない。
【００１９】
初めのマトリックスがｎ×ｎの大きさを有すると仮定すると、図３によるルータＩＯＲを追加することによって、マトリックスの大きさは（ｎ＋２）×（ｎ＋２）に増大する。従って、図３のネットワークは、図１のネットワークよりも待ち時間が大きくなりそうに思われる。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】ヨーロッパ特許ＥＰ１７０１２７４号公報
【特許文献２】国際公開第８９／０３５６４号パンフレット
【特許文献３】米国特許第５，６８９，６４７号明細書
【発明の概要】
【発明が解決しようとする課題】
【００２１】
したがって、プロセッサクラスターを有するＮＯＣにおいて、ネットワークの待ち時間を実質的に増大させず、またはチップ表面積を不必要に増大させずに入出力ユニットを追加することが望ましい。
【課題を解決するための手段】
【００２２】
この必要性を世話するため、各々が同じ行に属する２つの他のルータおよび同じ列に属する２つの他のルータに接続されたインフラルータからなるマトリックスと、各々が同じ行または同じ列に属する他の２つのルータに２つの内部入力によって接続されており、ネットワークにデータを供給する外部入力を備える入出力ルータと、を備えるトーラスメッシュネットワークが提供される。前記各入出力ルータは、内部入力用のキューを有さず、且つ、前記入出力ルータに接続されたインフラルータのキューを管理するようにも構成されたアービターにより管理された外部入力に割り当てられたキューを備える。
【図面の簡単な説明】
【００２３】
【図１】従来のチップ上のトーラスネットワークを概略的に示す。
【図２】図１のネットワークのルータの構造を概略的に示す。
【図３】入出力ルータを有するトーラスネットワークの実施形態を概略的に示す。
【図４】ルータの実施形態を示す。
【図５】図３のネットワークの最適化を概略的に示す。
【発明を実施するための形態】
【００２４】
他の利点および特徴は、添付図面を用いて説明される以下の典型的な実施形態の説明からより明確になるだろう。
【００２５】
図４は、入出力ルータＩＯＲとインフラルータＲＴＲの組み合わせた実施形態を概略的に示しており、この実施形態は、図３の入出力ルータＩＯＲが待ち時間をもたらさないことを保証するものである。東側のインフラルータＲＴＲの一部、特にマルチプレクサＭＸＥと制御回路２２が表されており、全部表された入出力ルータＩＯＲに接続されている。
【００２６】
ルータＩＯＲは、３チャネルルータであり、２入力マルチプレクサを３つ備える。西側のマルチプレクサｍｘｗは、第１の入力で入出力ユニットＩＯＭから入来するデータを受信し、第２の入力で東側へのルータ（図示せず）から入来するデータを受信する。東側のマルチプレクサｍｘｅは、第１の入力で入出力ユニットＩＯＭから入来するデータを受信し、第２の入力で図示されたルータＲＴＲの東側のマルチプレクサＭＸＥから入来するデータを受信する。
【００２７】
入出力ユニットＩＯＭからのデータは、ＦＩＦＯキュー２４を介してマルチプレクサｍｘｗ及びｍｘｅの対応する入力に達する。
【００２８】
しかしながら、図示のように、ルータＩＯＲのマルチプレクサの他の全ての入力はＦＩＦＯキューを有しない。このように、ルータＩＯＲを横断するデータは待ち時間をなんら経験しない。
【００２９】
ルータＲＴＲとルータＩＯＲ間の連携に関する以下の記述は、図４に表される要素、即ち、ルータＩＯＲとその西側のルータＲＴＲ間のリンクを参照してなされる。ネットワーク内の他のあり得る組み合わせに対する動作は同様である。
【００３０】
ＦＩＦＯキューが無いことに起因してルータＩＯＲを横断するデータが失われるということがないことを保証するために、ルータＩＯＲの制御回路ＣＴＲＬ及びルータＲＴＲの制御回路ＣＴＲＬは、図示されたマルチプレクサＭＸＥとｍｘｅの組み合わせがＦＩＦＯキューを備える５つのチャネルを有する単一のマルチプレクサとして振る舞うように、相互に作用する。これら５つのチャネルは、マルチプレクサＭＸＥの４つの入力と、ＩＯＭユニットに割り当てられたマルチプレクサｍｘｅの入力とによって形成される。換言すれば、入出力ルータとインフラルータの組み合わせが６チャネルルータとして振る舞う。
【００３１】
ＩＯＭユニットがルータＩＯＲの東側の出力に供給すべきデータを有しない場合、マルチプレクサｍｘｅはルータＲＴＲのマルチプレクサＭＸＥの出力を選択するために設置されている。マルチプレクサＭＸＥは従来の方法で制御され、マルチプレクサＭＸＥが供給するデータは、待ち時間なく、ルータＩＯＲの東側の出力に直接送信される。
【００３２】
ＩＯＭユニットがデータの供給を開始すると、そのデータはマルチプレクサｍｘｅのキュー２４にスタックされる。その後、ルータＩＯＲの制御回路２２’はルータＲＴＲの制御回路２２あてに要求信号ＲＱＩＯを有効にする。その後、ルータＲＴＲの制御回路２２は、４つではなく５つのチャネル間の調停モードに切り替わる。５番目のチャネルはマルチプレクサｍｘｅのキュー２４に割り当てられたチャネルである。
【００３３】
アービター（調停者、arbiter）が５番目のチャネルを満足させる（serve）決定をすると、ルータＲＴＲの制御回路はルータＩＯＲの制御回路に対してアクノリッジ信号ＡＱＩＯを有効にする。ルータＩＯＲの制御回路は、マルチプレクサｍｘｅがキュー２４からデータユニット、例えばパケットを出力するようにする。
【００３４】
キュー２４がデータを含む限り、信号ＲＱＩＯはアクティブのままであり、ルータＲＴＲの制御回路は５チャネル間の調停モードのままである。信号ＡＱＩＯは、アービターが５番目のチャネルを満足させる決定をするたびに、パケットごとにアクティブにされる。
【００３５】
原理上、入出力ルータＩＯＲに接続されるインフラルータＲＴＲのみが、今ちょうど説明したメカニズムを実装する必要がある。とは言っても、このメカニズムが必要とするロジックの占める表面積は無視して良いものなので、全ルータが同一になるように、このロジックを全てのインフラルータに設けてもよい。これにより、ネットワーク設計は簡略化される。機能を使用しないルータは、非アクティブの論理レベルに結線された、ＲＱＩＯ信号に関連する入力を有するだろう。
【００３６】
図３に示すようなトーラスネットワークにおいて、２つのＩＯＲルータは、マトリックスの端間のリンクで連続している。従って、これらのルータＩＯＲは信号ＲＱＩＯ及びＡＱＩＯを互いに伝えなければならない。それにもかかわらず、図３は、明確性のため、簡略化した表現に対応している。実際には、マトリックスの端同士を接続するリンクと同じくらい長いリンクは避けることが望ましい。
【００３７】
図５はノード間のリンク長が最適化されたトーラスネットワークを示している。マトリックスの大きさは例として４×４である。インフラルータは細線で示され、入出力ルータは太線で示されている。
【００３８】
インフラルータは行ごとに及び列ごとにインタリーブ（interleave）されている。即ち、列または行におけるランクｎのルータは、ランクｎ＋２のルータと接続されている（周辺のルータは、そのリンクの一つについてはこのルールに従わない）。入出力ルータは、周辺のインフラルータから出るリンクに挿入されている。
【００３９】
この構成ではルータ間の全てのリンクはほぼ同じ長さとなり、入出力ルータの各々は２つのインフラルータ間に設置される。
【符号の説明】
【００４０】
２０，２４  ＦＩＦＯキュー
２２，２２’  コントローラ
【図１】
0005583520.tif 000002
【図２】
0005583520.tif 000003
【図３】
0005583520.tif 000004
【図４】
0005583520.tif 000005
【図５】
0005583520.tif 000006