(57)【要約】  ネットワークオンチップの低レイテンシ化、低コスト化、高信頼化を図る。システム中に複数存在するルータを均一なものから、メインルータ４とサブルータ３の２つにクラス分けを行う。メインルータ４は、複数のサブルータ３を介して次のメインルータか交信先のネットワークインタフェースに至るまでのルーティング計算を一括して行う。サブルータ３ではルーティング計算を行う必要がなくなるため、その論理を省くことが可能になり、パケットがサブルータを通過する際のレイテンシを短縮すると共に低コスト化が図れる。また、メインルータ４を高信頼化し、サブルータ３は故障時に最寄りのメインルータにパケットを送ることによって、故障発生時の対応が可能となり、高信頼化が図れる。
2010137572.tif 000002
【特許請求の範囲】
【請求項１】
複数の情報処理ユニット又は記憶ユニット、インタフェースユニットが１又は複数チップに集積され、前記ユニット間を接続するネットワークであって、ネットワークインタフェース、交信路、ネットワークルータから構成されるネットワークをあわせて１又は複数チップに集積し、
前記ユニット間の情報をパケットにて前記ネットワークを介して交信し情報処理を行う半導体装置において、
ネットワークルータを、メインルータ群と他のルータ群の複数のグループに分け、
前記ルータを通る回数であるホップ数が規定の回数以内に受信先に到着できない場合には、前記メインルータを通り、前記メインルータを通る毎に、ルータを通る回数をリセットし、前記規定回数を満たすようにルーティングを行う、半導体装置。
【請求項２】
前記メインルータは、ルーティングを計算する手段を備え、
前記メインルータと、前記メインルータ又は前記ネットワークインタフェースがルーティングした情報に従ってルーティングを行うサブルータと、
を備えている、請求項１記載の半導体装置。
【請求項３】
前記メインルータは、
パケットから、データの受信先を示すＩＤ又はアドレスから、パケットの前記メインルータからの出力先のルーティングと、前記規定回数以内のサブルータのルーティングを行う手段を備え、
前記サブルータ分のルーティング情報を、パケット中の前記メインルータに到達するためのルート情報を記したフリットを更新して書き込み、対応するルータに対して、パケットを送出し、
前記パケットを受信したサブルータは、前記ルーティング情報に従って、ルーティングを行い、前記ルーティング情報を更新する、請求項１記載の半導体装置。
【請求項４】
前記メインルータは、
規定回数以内の前段に通った別のメインルータ、又は、送信側のネットワークインタフェースによってルーティングを決定されていた場合、自律的にルーティングを行わず、前段のメインルータが指定したルーティングに従ってパケットをルーティングする、請求項１記載の半導体装置。
【請求項５】
前記メインルータは、
前記サブルータのルーティングを行う手段を備え、
サブルーティング情報をフリットに圧縮エンコードして格納し、
前記サブルータは圧縮エンコードした前記情報を伸張して得た情報に従ってルーティングを行う、請求項２記載の半導体装置。
【請求項６】
規定のフリットに圧縮して格納できるルーティング情報によって決定されるホップ数までサブルータで連続してホップすることが許容され、
ルーティング到達場所へ至るルーティングに対する圧縮率によって規定ホップ回数が異なる、請求項５記載の半導体装置。
【請求項７】
あらかじめネットワークの混雑が予想されるＩＰに接続されるルータおよびその近傍に、前記メインルータを、他のネットワークルータの前記メインルータの割合よりも多く配置する、ことを特徴とする請求項１記載の半導体装置。
【請求項８】
前記メインルータは、周囲のリンク、前記サブルータの混雑および故障を把握する手段を備え、混雑ないし故障を回避するように前記サブルータのルーティングを行う、請求項２記載の半導体装置。
【請求項９】
故障が生じた前記サブルータは、前記ルータ内の利用可能なリソースを使用し、到着したパケットを近傍のメインルータに戻す制御を行う請求項２記載の半導体装置。
【請求項１０】
前記メインルータには、冗長論理、エラー検出訂正機能を備え、
リンク又は前記サブルータで発生した故障に対して、パケットが前記メインルータに到着した時点で訂正を行うと共に、メインルータが故障した場合に、前記冗長論理によって回復する、請求項２記載の半導体装置。
【請求項１１】
前記メインルータが行ったルーティング情報を、パケット中の前記メインルータに到達するためのルート上に記したフリットを更新して書き込むと共に、前記書き換え前のフリット情報を、パケットの別の位置に移動、追記することにより、前記パケットの送信元からのルート情報を、パケット中に保持する、請求項１記載の半導体装置。
【請求項１２】
請求項１乃至１１のいずれか１項に記載の半導体装置をオンチップで備えたネットワークオンチップ装置。
【請求項１３】
複数の情報処理ユニット又は記憶ユニット、インタフェースユニットが１又は複数チップに集積され、前記ユニット間を接続するネットワークであって、ネットワークインタフェース、交信路、ネットワークルータから構成されるネットワークをあわせて集積し、
ユニット間の情報をパケットにて前記ネットワークを介して交信し情報処理を行い、
ネットワークルータは、メインルータ群と他のルータ群の複数のグループに分けられ、
ルータを通る回数であるホップ数が規定の回数以内に受信先に到着できない場合には、前記メインルータを通り、
前記メインルータを通る毎に、ルータを通る回数をリセットし、前記規定回数を満たすようにルーティングを行う、ネットワークルーティング方法。
【請求項１４】
前記メインルータは、ルーティングを計算し、
前記メインルータ又は前記ネットワークインタフェースがルーティングした情報に従って、ルーティングを行うサブルータと、
を備えている、請求項１３記載のネットワークルーティング方法。
【請求項１５】
前記メインルータは、
パケットから、データの受信先を示すＩＤ又はアドレスから、パケットの前記メインルータからの出力先のルーティングと、前記規定回数以内のサブルータのルーティングを行い、
前記サブルータ分のルーティング情報を、パケット中の前記メインルータに到達するためのルート情報を記したフリットを更新して書き込み、対応するルータに対して、パケットを送出し、
前記パケットを受信したサブルータは、前記ルーティング情報に従って、ルーティングを行い、前記ルーティング情報を更新する、請求項１３記載のネットワークルーティング方法。
【請求項１６】
前記メインルータは、
規定回数以内の前段に通った別のメインルータ、又は、送信側のネットワークインタフェースによってルーティングを決定されていた場合、自律的にルーティングを行わず、前段のメインルータが指定したルーティングに従ってパケットをルーティングする、請求項１３記載のネットワークルーティング方法。
【請求項１７】
前記メインルータは、
前記サブルータのルーティングを行い、
サブルーティング情報をフリットに圧縮エンコードして格納し、
前記サブルータは圧縮エンコードした前記情報を伸張して得た情報に従ってルーティングを行う、請求項１４記載のネットワークルーティング方法。
【請求項１８】
規定のフリットに圧縮して格納できるルーティング情報によって決定されるホップ数まで前記サブルータで連続してホップすることが許容され、
ルーティング到達場所へ至るルーティングに対する圧縮率によって規定ホップ回数が異なる、請求項１７記載のネットワークルーティング方法。
【請求項１９】
あらかじめネットワークの混雑が予想されるＩＰに接続されるルータおよびその近傍に、前記メインルータを、他のネットワークルータの前記メインルータの割合よりも多く配置する、ことを特徴とする請求項１３記載のネットワークルーティング方法。
【請求項２０】
前記メインルータは、周囲のリンク、前記サブルータの混雑および故障を把握し、混雑ないし故障を回避するように前記サブルータのルーティングを行う、請求項１４記載のネットワークルーティング方法。
【請求項２１】
故障が生じた前記サブルータは、前記ルータ内の利用可能なリソースを使用し、到着したパケットを近傍の前記メインルータに戻す制御を行う請求項１４記載のネットワークルーティング方法。
【請求項２２】
前記メインルータには、冗長論理、エラー検出訂正機能を備え、
リンク又は前記サブルータで発生した故障に対して、パケットが前記メインルータに到着した時点で訂正を行うと共に、前記メインルータが故障した場合に、前記冗長論理によって回復する、請求項１４記載のネットワークルーティング方法。
【請求項２３】
前記メインルータが行ったルーティング情報を、パケット中の前記メインルータに到達するためのルート情報を記したフリットを更新して書き込むと共に、前記書き換え前のフリット情報を、パケットの別の位置に移動、追記することにより、前記パケットの送信元からのルート情報を、パケット中に保持する、請求項１３記載のネットワークルーティング方法。
【請求項２４】
複数の情報処理ユニット又は記憶ユニット、インタフェースユニットのユニット間を接続するネットワークであって、ネットワークインタフェース、交信路、ネットワークルータから構成されるネットワークを備え、前記ユニット間の情報をパケットにて前記ネットワークを介して交信し情報処理を行うネットワークシステムであって、
ネットワークルータを、メインルータ群と他のルータ群の複数のグループに分け、
前記ルータを通る回数であるホップ数が規定の回数以内に受信先に到着できない場合には、前記メインルータを通り、前記メインルータを通る毎に、ルータを通る回数をリセットし、前記規定回数を満たすようにルーティングを行う、ネットワークシステム。
【請求項２５】
前記メインルータは、ルーティングを計算する手段を備え、
前記メインルータと、前記メインルータ又は前記ネットワークインタフェースがルーティングした情報に従ってルーティングを行うサブルータと、
を備えている、請求項２４記載のネットワークシステム。
【請求項２６】
前記メインルータは、
パケットから、データの受信先を示すＩＤ又はアドレスから、パケットの前記メインルータからの出力先のルーティングと、前記規定回数以内のサブルータのルーティングを行う手段を備え、
前記サブルータ分のルーティング情報を、パケット中の前記メインルータに到達するためのルート情報を記したフリットを更新して書き込み、対応するルータに対して、パケットを送出し、
前記パケットを受信したサブルータは、前記ルーティング情報に従って、ルーティングを行い、前記ルーティング情報を更新する、請求項２４記載のネットワークシステム。
【請求項２７】
前記メインルータは、
規定回数以内の前段に通った別のメインルータ、又は、送信側のネットワークインタフェースによってルーティングを決定されていた場合、自律的にルーティングを行わず、前段のメインルータが指定したルーティングに従ってパケットをルーティングする、請求項２４記載のネットワークシステム。
【請求項２８】
前記メインルータは、
前記サブルータのルーティングを行う手段を備え、
サブルーティング情報をフリットに圧縮エンコードして格納し、
前記サブルータは圧縮エンコードした前記情報を伸張して得た情報に従ってルーティングを行う、請求項２５記載のネットワークシステム。
【請求項２９】
規定のフリットに圧縮して格納できるルーティング情報によって決定されるホップ数までサブルータで連続してホップすることが許容され、
ルーティング到達場所へ至るルーティングに対する圧縮率によって規定ホップ回数が異なる、請求項２５記載のネットワークシステム。
【請求項３０】
あらかじめネットワークの混雑が予想されるＩＰに接続されるルータおよびその近傍に、前記メインルータを、他のネットワークルータの前記メインルータの割合よりも多く配置する、ことを特徴とする請求項２４記載のネットワークシステム。
【請求項３１】
前記メインルータは、周囲のリンク、前記サブルータの混雑および故障を把握する手段を備え、混雑ないし故障を回避するように前記サブルータのルーティングを行う、請求項２５記載のネットワークシステム。
【請求項３２】
故障が生じた前記サブルータは、前記ルータ内の利用可能なリソースを使用し、到着したパケットを近傍のメインルータに戻す制御を行う請求項２５記載のネットワークシステム。
【請求項３３】
前記メインルータには、冗長論理、エラー検出訂正機能を備え、
リンク又は前記サブルータで発生した故障に対して、パケットが前記メインルータに到着した時点で訂正を行うと共に、メインルータが故障した場合に、前記冗長論理によって回復する、請求項２５記載のネットワークシステム。
【請求項３４】
前記メインルータが行ったルーティング情報を、パケット中の前記メインルータに到達するためのルート上に記したフリットを更新して書き込むと共に、前記書き換え前のフリット情報を、パケットの別の位置に移動、追記することにより、前記パケットの送信元からのルート情報を、パケット中に保持する、請求項２４記載のネットワークシステム。
【請求項３５】
前記メインルータは、
入力信号を受ける入力ラッチと、
送り先からルートを計算するルート計算部と、
前記ルート計算部でのルート計算の結果に基づいてルーティング・フリットを生成するルーティングフリット生成部と、
前記ルーティングフリット生成部で生成されたルーティング・フリットと前記入力ラッチからの情報との一方を選択するセレクタと、
前記セレクタでの選択結果をそれぞれ蓄える入力ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）と、
クロスバスイッチによる選択結果をそれぞれラッチする出力バッファと、
を含む組を、
各方路と前記メインルータ自身が直接接続しているＩＰ（Ｉｎｔｅｌｌｅｃｔｕａｌ  Ｐｒｏｐｅｒｔｙ）に対応して備え、
入力信号の出力先を調整するアービタと、いずれか方向の前記入力ＦＩＦＯからの出力を選択するセレクタを備えたクロスバスイッチを各方路及びＩＰに対応した複数の前記入力ＦＩＦＯと複数の前記出力バッファとの間に備えている、請求項２４又は２５記載のネットワークシステム。
【請求項３６】
前記サブルータは、
入力信号を入力する入力ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）と、
クロスバスイッチによる選択結果をそれぞれラッチする出力バッファと、
を含む組を、
各方路と前記サブルータ自身が直接接続しているＩＰ（Ｉｎｔｅｌｌｅｃｔｕａｌ  Ｐｒｏｐｅｒｔｙ）に対応して備え、
入力信号の出力先を調整するアービタと、いずれか方向の前記入力ＦＩＦＯからの出力を選択するセレクタと、を備えたクロスバスイッチを、各方路及びＩＰに対応した複数の前記入力ＦＩＦＯと複数の前記出力バッファとの間に備えている、請求項２５記載のネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２００９−１２５５８０号（２００９年  ５月２５日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、半導体集積回路装置とネットワークルーティング方法に関し、特に、複数のＩＰ（Ｉｎｔｅｌｌｅｃｔｕａｌ  Ｐｒｏｐｅｒｔｙ）コアを集積したＬＳＩ集積回路（Ｓｙｓｔｅｍ  Ｏｎ  ａ  Ｃｈｉｐ（ＳｏＣ））における、ＩＰコア間のデータ交信用ネットワークオンチップ（Ｎｅｔｗｏｒｋ  ｏｎ  ａ  Ｃｈｉｐ：  ＮｏＣ）に適用して好適な装置と方法に関する。
【背景技術】
【０００２】
従来、複数のＩＰ（Ｉｎｔｅｌｌｅｃｔｕａｌ  Ｐｒｏｐｅｒｔｙ）コアを集積したＬＳＩ集積回路（ＳｏＣ：Ｓｙｓｔｅｍ  Ｏｎ  ａ  Ｃｈｉｐ）において、ＩＰコア間の接続はバスを用いて行っている。例えば、ＡＲＭ社が提唱するＡＭＢＡ（ＡＲＭ社の登録商標）は、このようなバスの業界標準となっている。このＡＭＢＡは、コア数の増加、チップの複雑化に対応し、ＡＨＢ（Ａｄｖａｎｃｅｄ  Ｈｉｇｈ  ｐｅｒｆｏｒｍａｎｃｅ  Ｂｕｓ）、マルチレイヤＡＨＢ、ＡＸＩ（Ａｄｖａｎｃｅｄ  ｅＸｔｅｎｓｉｂｌｅ  Ｉｎｔｅｒｆａｃｅ）というように進化してきた。【０００３】
しかしながら、バス構成では、配線長が長くなり周波数の向上に対応しづらくなる。また、複数ＩＰからのアクセス競合に対する調停を集中的に行う必要がある。そのため、ＩＰ数の変動に対して、バスを作り直す必要が生じることなどの問題が生じている。【０００４】
これらの問題に対して、現状では、バスを階層的に接続することによって、ローカリティを持たせて対処する方法が、高性能なＳｏＣでは積極的に行われてきた。【０００５】
一方で、データをパケット化して送ることにより、通信のローカリティを有効に活用しつつ、調停を各ルータに分散させることによってスケーラビリティを確保可能なＮｏＣ（Ｎｅｔｗｏｒｋ  ｏｎ  Ｃｈｉｐ）は、米国Ｓｔａｎｆｏｒｄ大学のＤａｌｌｙ，  Ｗ．Ｊ．等の以下の非特許文献１で提案され、近年積極的に研究されてきた。実際のチップに採用された例として、ＴＩＬＥＲＡ社のＴＩＬＥ６４、Ｉｎｔｅｌ社の８０コアチップ、  ＣＥＡ−ＬｅｔｉのＦＡＵＳＴチップ、ＳＴＭｉｃｒｏ社のＳＴＮｏＣ等があげられる。【０００６】
これらは、基本的に、図１５に示すように、ルータ３０２と通信チャネル３０５によってネットワークを構成しており、図１６に示すような複数フリットから構成されたパケットをこれらのネットワークに流すことによって、交信を実現する。【０００７】
ここで、各ルータ３０２は、受け取ったパケットを、送信先のネットワークインタフェース（ＮＩＦ）に送るために適切な出力ポートに送出する。【０００８】
このとき、ルータ３０２内で送信先のアドレスやＩＤを見た上で、ある一定規則に基づき、次のホップに向けた送出先を決定するルーティング・プロトコル方式と、
送信側のネットワークインタフェースにおいて、送信先までのルーティングを全て決定してしまい、ルーティング情報をパケットに含めるソースルーティング方式と、
が存在する。【０００９】
＜ルーティング・プロトコル方式＞
ルーティング・プロトコル方式は、入力チャネルから入ってきたパケットを解析し、アドレスやＩＤを抽出、この情報を基にルータに備えられているテーブルなどサーチし、当該パケットをどの出力チャネルに出力するかを決定し、その後、該出力チャネルに対しての調停を行い、パケットを出力する。【００１０】
従って、出力先の決定に、論理的な動作が数ステップ入ることになる。【００１１】
また、ルーティングを変更する際には、変更に関わる全てのルータにおいてルーティング規則の更新が必要となる。【００１２】
ルーティングに必要となるステップ数を削減する技術としては、ルーティング計算を一つ前のルータで行う「Ｎｅｘｔ  Ｒｏｕｔｉｎｇ  Ｃｏｍｐｕｔａｔｉｏｎ」手法が提案されている。これは、図１７を例にとると、ルータＲ０からルータＲ１を介してルータＲ５に至るパケットがあった場合、ルータＲ１のルーティング計算をルータＲ０で、ルータＲ５のルーティング計算をＲ１で行う手法である。【００１３】
さらに、仮想的にエクスプレス（Ｅｘｐｒｅｓｓ）チャネルを張る方法や、予測ルーティングを行う方法などが提案されている。例えば、以下のような非特許文献２，３などが、その例である。【００１４】
非特許文献２の手法では、図１７に示すように、いくつかの中継ルータによるルーティング計算や調停などをバイパスする仮想チャネルを張ることによって、中継ルータで必要なパイプライン段数を削減する。バイパス時には、２サイクルでルータを通過する。【００１５】
図１７において、ルータ３５１は双方向のチャネル３５２で接続されている。ここで、ルータＲ１からルータＲ１５への交信が多数存在する場合、仮想エクスプレスチャネル３５４を定義する。【００１６】
ルータＲ２、Ｒ７、Ｒ１１では、このチャネルで到着したパケットのルーティング計算、スイッチ調停などを省くことができる。このように、ルータＲ１からルータＲ３へのレイテンシとルータＲ３からＲ１５へのレイテンシを短縮するものである。【００１７】
一方、非特許文献３の手法は、到着したパケットに対して、ルーティング計算を行うのと並行して、ある一定の予測ルールに基づき、投機的にパケットの出力方向を予測し、その方向のスイッチ調停、スイッチ通過を行い、出力してしまうことによって、投機が成功した場合には、ルーティング計算のサイクル分のレイテンシ短縮を図るものである。【００１８】
ルーティング計算の結果、この予測がはずれた場合には、出力ラッチや投機的に出力した方向のルータ内の入力ラッチ、入力データＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）に存在する当該パケットのフリットを取り消し、正しい出力方向に対するスイッチ調停、スイッチ通過を再度行う。【００１９】
＜ソースルーティング方式＞
ソースルーティング方式では、各ルータにおける出力チャネル情報を、送信側のネットワークインタフェースにおいて、あらかじめパケットに埋め込むことにより、各ルータでは、この情報を抽出するだけでルーティングを完了できる。【００２０】
例えば、Ｉｎｔｅｌ社の８０−Ｔｉｌｅ  １．２８ＴＦＬＯＰＳ  Ｎｅｔｗｏｒｋ−ｏｎ−Ｃｈｉｐでは、このソースルーティング方式を採用している（非特許文献４）。図１８は、このチップにおけるパケットのフリット０を示している。図１８に示すように、このチップでは、出力側ネットワークインタフェースでルータ毎に出力先を示したＤＩＤ（Ｄｅｓｔｉｎａｔｉｏｎ  ＩＤｓ）３６１を１０ホップ分生成し、パケット内に定義している。これに従って、ルータは出力ポートを決定する。【００２１】
従って、各ルータは、ＤＩＤの値を抽出するだけで、ルーティングが可能である。このように、ソースルーティング方式は、各ルータの構造を簡単化することができる。【００２２】
ＴＣＰ／ＩＰ（Ｔｒａｎｓｐｏｒｔ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）などのコンピュータ間のＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）などでも、ソースルーティング方式はオプションとしてサポートされている。【００２３】
これは、パケットが経由するネットワークの物理的な位置をＩＰアドレスとしてパケット中に明記しておき、これに従ってパケットをルーティングするものである。これには、ストリクト・ソースルーティング方式とルーズ・ソースルーティング方式の２種類が用意されている。【００２４】
＜ストリクト・ソースルーティング方式＞
ストリクト・ソースルーティング方式は、ホップするすべてのネットワーク地点を、送信側のネットワークインタフェースにおいて、パケット中に明記したものであり、明記されていないネットワーク地点に達したパケットは破棄される。【００２５】
＜ルーズ・ソースルーティング方式＞
一方、ルーズ・ソースルーティング方式は、一部のネットワーク地点のみをパケット中に明記し、その間はルータによって補完したルーティングを許す方式で、明記されたネットワーク地点以外では、ルーティング・プロトコル（ｒｏｕｔｉｎｇ  ｐｒｏｔｏｃｏｌ）方式によって、各ネットワーク地点でルーティングを行い、パケット転送を行う。【００２６】
いずれの場合も、指定できるルータの最大ホップ数は９である。これらは、ルータのテストに用いられることが多い。【００２７】
図１９に、このソースルーティングの場合のパケットフォーマットを示す。図１９において、オプションタイプ３８１が指定のオプションの場合、ソースルーティング方式となり、オプション長で指定されたＩＰアドレス分のソースルーティングが行える。【００２８】
オプション長３８２の後は、オプションポインタ３８３と指定されたオプション長に相当するＩＰアドレス３８４が続く。ｎは最大９であることから、１０以上のＩＰアドレスを指定することはできない。【００２９】
特許文献１には、送信元と送信先との間のホップ数が大きい大規模のアドホックネットワークにおいて、小さな負荷で経路を修復できる経路修復方法が開示されている。送信元ノードAと送信先ノードKとの間に９個の無線ノードB，C…Jを中継する経路が確立されており、経路上では所定のホップ数ごとに管理ノードA，F，Kが配置されている。無線ノードI，J間の経路が消失すると、これを検知した無線ノードIが送信元方向で直近の管理ノードFを宛先としてRERR（経路無効通知）を送信する。このRERRを受信した管理ノードFは、送信先方向で直近の管理ノード（ここでは、送信先ノードK）を宛先とするRepair_REQ（経路修復要求）を送信して局所的な経路修復を実施し、消失した経路をバイパスする新たな経路を２つの管理ノードF，K間に確立する。特許文献２には、複数のモジュール（IP；A-D、M）を接続し、モジュール（IP；A-D、M）間の通信を可能にする相互接続手段（N）を有する電子装置（システム・オン・チップ）が提供され、通信リソースは、利用可能な通信帯域を分割して共有するタイムスロットに基づく時分割多重アクセスに関し、電子装置は、複数のモジュール（IP；A-D、M）のうち少なくとも１つを相互接続手段（N）に結合する少なくとも１つのネットワークインタフェースを更に有し、ネットワークインタフェース（NI）は、少なくとも１つの更なるネットワークインタフェース（NI）に少なくとも１つの接続を確立するように適合され、少なくとも１つの接続は、少なくとも１つのチャネル（a-d）を有する。少なくとも１つのネットワークインタフェース（NI）は、少なくとも１つのチャネル（a-d）のタイムスロットを予約する少なくとも１つのスロットテーブル（ST1-ST11）を有する。タイムスロットは、同じネットワークインタフェース（NI）に関連するチャネル（a-d）間で共有される構成が開示されている。
【先行技術文献】
【特許文献】
【００３０】
【特許文献１】特開２００８−２８３２６０号公報
【特許文献２】特表２００９−５０２０８０号公報
【非特許文献】
【００３１】
【非特許文献１】“Ｒｏｕｔｅ  Ｐａｃｋｅｔｓ，  Ｎｏｔ  Ｗｉｒｅｓ：  Ｏｎ−Ｃｈｉｐ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ  Ｎｅｔｗｏｒｋｓ” Ｄａｌｌｙ，  Ｗ．Ｊ．  Ｔｏｗｌｅｓ，  Ｂ．    Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ，  ２００１．  ｐａｇｅ：  ６８４−  ６８９
【非特許文献２】“  Ｔｏｗａｒｄ  Ｉｄｅａｌ  Ｏｎ−Ｃｈｉｐ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｕｓｉｎｇ  Ｅｘｐｒｅｓｓ  Ｖｉｒｔｕａｌ  Ｃｈａｎｎｅｌｓ”，  Ｋｕｍａｒ，  Ａ．，  Ｌｉ−Ｓｈｉｕａｎ  Ｐｅｈ，  Ｋｕｎｄｕ，  Ｐ．，  Ｊｈａ，  Ｎ．Ｋ．，  Ｍｉｃｒｏ，  ＩＥＥＥ  Ｖｏｌｕｍｅ  ２８，  Ｉｓｓｕｅ  １，  Ｊａｎ．−Ｆｅｂ．  ２００８  Ｐａｇｅ（ｓ）：８０  −  ９０
【非特許文献３】“予測機構を持つルータを用いた低遅延チップ内ネットワークに関する研究”鯉渕道紘  吉永努  村上弘和  松谷宏紀  天野英晴，先進的計算基盤システムシンポジウム  ＳＡＣＳＩＳ’０８  論文集，  ｐｐ．３９３−４０１，  Ｊｕｎ  ２００８
【非特許文献４】Ａｎ  ８０−Ｔｉｌｅ  １．２８ＴＦＬＯＰＳ  Ｎｅｔｗｏｒｋ−ｏｎ−Ｃｈｉｐ  ｉｎ  ６５ｎｍ  ＣＭＯＳ  Ｓｒｉｒａｍ  Ｖａｎｇａｌ，  Ｊａｓｏｎ  Ｈｏｗａｒｄ，  Ｇｒｅｇｏｒｙ  Ｒｕｈｌ，  Ｓａｕｒａｂｈ  Ｄｉｇｈｅ，  Ｈｏｗａｒｄ  Ｗｉｌｓｏｎ，  Ｊａｍｅｓ  Ｔｓｃｈａｎｚ，  Ｄａｖｉｄ  Ｆｉｎａｎ，  Ｐｒｉｙａ  Ｉｙｅｒ，  Ａｒｖｉｎｄ  Ｓｉｎｇｈ，  Ｔｉｊｕ  Ｊａｃｏｂ，  Ｓｈａｉｌｅｎｄｒａ  Ｊａｉｎ，  Ｓｒｉｒａｍ  Ｖｅｎｋａｔａｒａｍａｎ，  Ｙａｔｉｎ  Ｈｏｓｋｏｔｅ，  Ｎｉｔｉｎ  Ｂｏｒｋａｒ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｃｉｒｃｕｉｔ  Ｃｏｎｆｅｒｅｎｃｅ  ２００７，  ｐｐ９８−９９
【発明の概要】
【発明が解決しようとする課題】
【００３２】
上記特許文献１、２及び非特許文献１〜４の全開示内容はその引用をもって本書に繰込み記載する。
以下に本発明による分析を与える。【００３３】
ネットワークオンチップ（ＮｏＣ）は、システムバスをネットワーク構成、パケットベース交信に置き換えることによって、効率化と性能向上を図ることを主眼としている。【００３４】
しかしながら、従来の技術における各ルータがルーティング計算を行う方式によるルーティングでは、ルーティング計算によって、各ルータの遅延や面積が増加する。具体的には、ＩＤやアドレスからネットワーク出力先を決定するためのテーブルや演算論理が必要となる。【００３５】
ＩＤが増えた場合には、テーブルの物量やテーブル引きの電力、遅延が増加する。【００３６】
遅延が増加した場合には、ネットワークの周波数を落としてスループットを落とすか、パイプライン段数を増やす必要が生じる。【００３７】
パイプライン段数の増加は、ルーティング計算中、パケットを格納するためのバッファの要求量が増すという問題が生じる。【００３８】
また、ルーティングのレイテンシの増加を抑える各種提案も、ルータの複雑度を増加させ、物量が増えるという問題が生じる。【００３９】
さらに、これらの方法の場合、障害やネットワーク混雑などの事情でルーティングを変更する場合には、各ルータのテーブル内容、もしくは演算論理を書き換える必要がある。【００４０】
一方、ソースルーティング方式の場合、ルータの簡単化、高速化は可能であるが、送信側から受信側に至るまでに通過するルータのホップ数が一定でないため、パケット内にルーティング情報を格納する領域を可変長で確保する必要が生じる。【００４１】
もしくは固定長にした場合、小ホップ数の交信では無駄なフィールドが増えることや、このフィールドを制限する場合には、ホップ数が限られ、スケーラビリティを阻害する。【００４２】
また、ホップ数が多くなる場合、最初に送信元ネットワークインタフェースでルーティングを計算する計算量が増加し、遅延物量が増加することや、ルート途中で何からの事情が生じた場合に、最初に指定されたルーティングを変更しづらく、動的なルーティングへの適用力が劣る。【００４３】
したがって、本発明の目的はネットワークオンチップの低レイテンシ化、低コスト化、高信頼化を図る方法、装置、システムを提供することにある。
【課題を解決するための手段】
【００４４】
本発明によれば、複数の情報処理ユニット、記憶ユニット、インタフェースユニットが１又は複数チップに集積され、前記ユニット間をネットワークインタフェース、交信路、ネットワークルータから構成されるネットワークをあわせて集積し、ユニット間の情報をパケットで前記ネットワークを介して交信を行い情報処理を行う情報処理半導体素子であって、ネットワークルータは、メインルータ群と他のルータ群の複数のグループに分けられ、ルータを通る回数であるホップ数が規定の回数以内に受信先に到着できない場合には、メインルータを通り、メインルータを通る毎に、ルータを通る回数をリセットし、前記規定回数を満たすようにルーティングを行う、ネットワークルータが提供される。
【発明の効果】
【００４５】
本発明によれば、ネットワークオンチップの低レイテンシ化、低コスト化、高信頼化を図ることができる。
【図面の簡単な説明】
【００４６】
【図１】本発明の一実施形態のオンチップネットワークを用いたマルチコアＳｏＣの全体ブロック図である。
【図２】本発明の一実施形態におけるメインルータのブロック図である。
【図３】本発明の一実施形態におけるサブルータのブロック図である。
【図４】本発明の一実施形態におけるパケットのフォーマットを示す図である。
【図５】本発明の実施の形態におけるＢ３のネットワークインタフェース出力時のフリット０，１のフォーマットを示す図である。
【図６】本発明の実施の形態におけるＥ３のメインルータ出力時のフリット０のフォーマットを示す図である。
【図７】本発明の実施の形態におけるＦ６のメインルータ出力時のフリット０のフォーマットを示す図である。
【図８】本発明の実施の形態におけるパケットのルート情報を格納したフリットのフォーマットを示す図である。
【図９】本発明の実施の形態におけるＢ３のネットワークインタフェース出力時のフリット０のフォーマットを示す図である。
【図１０】本発明の実施の形態におけるオンチップネットワークを用いたマルチコアＳｏＣの全体構成を示す図である。
【図１１】本発明の実施の形態におけるＢ３のネットワークインタフェース出力時のパケットのフォーマットを示す図である。
【図１２】本発明の実施の形態におけるＥ３のメインルータ出力時のパケットのフォーマットを示す図である。
【図１３】本発明の実施の形態におけるＦ６のメインルータ出力時のパケットのフォーマットを示す図である。
【図１４】本発明の実施の形態におけるＧ６のネットワークインタフェースによって生成される応答パケットのフォーマットを示す図である。
【図１５】ネットワークオンチップを採用したＳｏＣのブロック図である。
【図１６】ネットワークオンチップにおけるパケットのフォーマットを示す図である。
【図１７】関連技術のＥｘｐｒｅｓｓ  Ｐａｔｈを説明した概念を示す図である。
【図１８】関連技術のルート情報を示したパケットのフォーマットを示す図である。
【図１９】関連技術のＴＣＰ／ＩＰのソースルーティング時のパケットフォーマット図である。
【発明を実施するための形態】
【００４７】
はじめに、本発明の基本原理を説明し、つづいて具体的な実施例に即して説明する。
【００４８】
本発明においては、ＮｏＣ中に存在するルータをメインルータとサブルータの２種類に分ける。
【００４９】
ネットワークのパケットは、まず、送信元のネットワークインタフェースにおいて、適切なメインルータまで、又は、近接するネットワークインタフェースが送信先の場合には、それまでのルーティングを、一括して、ソースルーティング方式を取る。
【００５０】
メインルータに届いたパケットは、当該メインルータにおいて、同様に、次のメインルータ、又は、送信先のネットワークインタフェースまでのルーティングを、一括して、ソースルーティング方式によってルーティングする。これらの一連の動作によって、サブルータでは、ネットワークインタフェース又はメインルータが行った部分的なルーティング情報に従って、ルーティングを行う。これにより、サブルータが簡単化され、物量とレイテンシ、消費電力削減が可能になる。
【００５１】
一方、メインルータは、ルーティング計算が若干複雑化するが、どちらにしても自ルータからの出力に関するルート計算を行う必要があるので、計算のケースが増えるのみであり、サブルータの削減分ほどの複雑化は生じない。
【００５２】
また、サブルータネットワーク中のメインルータの比率を下げることによって、全体のコストを下げることが可能である。
【００５３】
本発明においては、ＮｏＣルーティングの基本を提案する。
【００５４】
ネットワーク中に、規定ホップ数以内でメインルータから別のメインルータへ到達できるような範囲で、メインルータを配置し、それ以外をサブルータとして配したネットワークトポロジを用意し、パケットは、規定ホップ数以内で、メインルータから次のメインルータまで、又は、受信側ネットワークインタフェースに至る経路を通るように制御されるルーティング方法が提供される。
【００５５】
すなわち、規定ホップ数を超えてメインルータを通らないルーティングは行わないことを意味している。
【００５６】
本発明の第２の側面において、メインルータは、次のメインルータまでの規定ホップ数以内のルーティングを一括して行い、サブルータは、このメインルータが行ったルーティング情報に従って、パケットを処理する。従って、サブルータは、到着したパケットに対して、メインルータが行ったルーティング情報に基づき、ルーティングを行う。サブルータは、主体的に、ルーティングの計算を行う必要はない。
【００５７】
本発明の第３の側面においては、メインルータで行ったサブルータ分のルーティング情報をパケット中の特定フリットに書き込む。サブルータは、この特定フリットを参照することによってルーティングを行う。サブルータも。必要に応じて、この特定フリットのルーティング情報を修正することは可能である。サブルータは、ルーティングの計算を行わない。
【００５８】
本発明の第４の側面においては、後段メインルータのルーティングが、前段のメインルータによってルーティング計算ができる場合には、後段のメインルータは、サブルータと同様に、前段メインルータのルーティング情報を基に、ルーティングを行う。これにより、特にメインルータに接続されるＩＰが受信先の場合に、ルーティングコストを下げることが可能となる。
【００５９】
本発明において、ホップ数の制限は、パケット中の特定フリットの限定されたデータ領域に書き込めるルーティング情報の制約から生じる。
【００６０】
各サブルータのルーティング情報を固定されたビット数の領域でそのまま表現した場合には、ホップ数の制限はこの固定されたビット数の領域をいくつとれるかで一意に決定される。しかしながら、特に、メッシュ構成を採ったオンチップネットワークでは、パケットの直進が最も多いルーティングとなると予想される。
【００６１】
そこで、本発明の第５、第６の側面においては、このルーティング情報に反復回数という概念を加えることにより、ルーティング情報を圧縮し、到達可能なホップ数を増やし、メインルータにホップする回数を減少させる。
【００６２】
このような工夫を加えた場合でも、ホップ回数の規定により、従来ネットワークオンチップと比べ、メインルータにパケットが集中する可能性がある。従って、交信が集中するＩＰ近傍のメインルータでネットワーク混雑により性能が低下する可能性がある。
【００６３】
そこで、本発明の第７の側面においては、これらの問題に対応するために、交信が集中するＩＰ近傍にメインルータを増やしたり、予備のメインルータとして配置したものを状況に応じて、サブルータやメインルータとして用いて負荷を分散させる仕組みが提供される。
【００６４】
本発明の第８−第１０の側面においては、ネットワークの信頼性の向上を図る。本発明におけるオンチップネットワークは、メインルータに、自律的な一定の機能を持たせ、サブルータは、従属的に動作をさせることによって、ネットワーク全体の最適化を図る。
【００６５】
本発明の第８の側面においては、メインルータは、近傍のネットワークの故障状況、混雑状況を把握し、それに応じたルーティングを行う。
【００６６】
また、本発明の第９の側面においては、サブルータ又はリンクの故障を検出した場合には、サブルータは、到着したパケットを、故障検出していない利用可能なチャネルを用いて、パケット内の情報に依らず、メインルータに戻すルーティングを行う。
【００６７】
本発明の第１０の側面においては、メインルータは、故障の状況を把握しており、これに基づき回避ルーティングを行う。
【００６８】
また、本発明の第１１の側面においては、ネットワーク全体の冗長度を上げることなく、メインルータのハードウェア信頼性をサブルータよりも向上させてネットワーク全体の信頼性を保つ。本発明の第１１の側面においては、サブルータに対するルーティング情報を、メインルータを通る毎にパケットにフリットを追加する。これにより、送信側ネットワークインタフェースからパケットが送出される時点では、最初のメインルータに至るまでのルーティング情報のみを保持しているが、受信先ネットワークインタフェースに到達する際には、送信側から受信先までのすべてのルーティング情報を保持することになり、それに応じてパケットのフリット数を増加させるものである。
【００６９】
これにより、故障を検出した場合の再送処理、データ受信の確認処理、データリード要求に対する応答処理の際に、このルーティング情報を基に、送信側にパケットを新たなルーティング計算を行うことなく、戻すことが可能になる。
【００７０】
このようなルーティングは、すべてのパケットに対して行うことも可能であるし、必要性の高い一部のパケットに対してのみ行うことも可能である。
【００７１】
また、送信側にパケットを戻す際には、本発明では、メインルータもサブルータ同様に自律的なルーティングを行わずにパケット転送を行うことになる。
【００７２】
＜実施形態１＞
本発明の一実施形態について図面を参照して詳細に説明する。図１は、本発明の一つの実施形態を適用したマルチコアＳｏＣ全体の構成を示すである。本実施形態では、２次元メッシュ構造のオンチップネットワーク構成を採っている。図１において、マルチコアＳｏＣ１０は、複数のＩＰ（Ｉｎｔｅｌｌｅｃｔｕａｌ  Ｐｒｏｐｅｒｔｙ）コア１を持つ。各々のＩＰコア１は、各々ネットワークインタフェース２を介し、通信チャネル５に接続される。通信チャネル５は、これらのネットワークインタフェース２と、メインルータ４又はサブルータ３との接続、交信を行うためのものである。メインルータ４とサブルータ３はそれぞれ一定の割合でマルチコアＳｏＣ１０上に配置される。
【００７３】
図２は、図１のメインルータ４の構成を示す図である。図２を参照すると、メインルータは、ＮＥＳＷの４方向とメインルータ自身が直接接続しているＩＰ（Ｉｎｔｅｌｌｅｃｔｕａｌ  Ｐｒｏｐｅｒｔｙ）からの入力信号を受ける入力ラッチ２１ｎ、２１ｅ、２１ｓ、２１ｗ、２１ｉと、
送り先からルートを計算するルート計算部２２ｎ、２２ｅ、２２ｓ、２２ｗ、２２ｉと、
ルート計算の結果に基づいてルーティング・フリットを生成するルーティングフリット生成部２３ｎ、２３ｅ、２３ｓ、２３ｗ、２３ｉと、
ルーティングフリット生成部２３ｎ、２３ｅ、２３ｓ、２３ｗ、２３ｉの結果と入力ラッチ２１ｎ、２１ｅ、２１ｓ、２１ｗ、２１ｉからの直接の情報との一方をそれぞれ選択するセレクタ２４ｎ、２４ｅ、２４ｓ、２４ｗ、２４ｉと、
セレクタ２４ｎ、２４ｅ、２４ｓ、２４ｗ、２４ｉでの選択結果をそれぞれ蓄える入力ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  ＯＵＴ：先入れ先出し型記憶装置）２５ｎ、２５ｅ、２５ｓ、２５ｗ、２５ｉと、
各入力信号の出力先をアービタ２７で調停し、各々のセレクタ２８ｎ、２８ｅ、２８ｓ、２８ｗ、２８ｉによって、いずれか方向の入力ＦＩＦＯ２５ｎ、２５ｅ、２５ｓ、２５ｗ、２５ｉからの出力を選択するクロスバスイッチ２６と、
クロスバスイッチ２６のセレクタ２８ｎ、２８ｅ、２８ｓ、２８ｗ、２８ｉによる選択結果をそれぞれラッチする出力バッファ２９ｎ、２９ｅ、２９ｓ、２９ｗ、２９ｉと、
を備え、出力バッファ２９ｎ、２９ｅ、２９ｓ、２９ｗ、２９ｉでのラッチ結果が出力される。
【００７４】
図３は、図１のサブルータ３の構成を示す図である。図３を参照すると、サブルータはルーティングを行う機構を保持していないので、図２のメインルータ４に比して大幅に簡単化される。すなわち、入力データは直接入力ＦＩＦＯ４５ｎ、４５ｅ、４５ｓ、４５ｗ、４５ｉに格納された上で、クロスバスイッチ４６に至る。クロスバスイッチ４６は、各入力信号の出力先をアービタ４７で調停し、各々のセレクタ４８ｎ、４８ｅ、４８ｓ、４８ｗ、４８ｉによって、いずれか方向の入力ＦＩＦＯ４５からの出力を選択する。この選択結果を出力バッファ４９ｎ、４９ｅ、４９ｓ、４９ｗ、４９ｉによってラッチされ、その後出力される。
【００７５】
図４は、本実施形態におけるパケットのフォーマットの一例を示している。図４を参照すると、パケットは、フリット０からフリット６を含む。各フリットは、サイドバンド８２とパケットボディ８６を含む。サイドバンド８２は、パケットボディ８６の属性を示し、有効ビット８３、先頭ビット８４、終端ビット８５を含み、それぞれフリットデータが有効か、パケットの先頭フリットか、終端フリットかを示している。パケットボディ８６は、フリット毎に、データの意味が異なっている。
【００７６】
本実施形態では、フリット０は、ソースルーティングのための複数のルート情報８７（ルート情報１〜４）とそれに関わる制御情報８８を含む。
【００７７】
フリット１は、パケット全体のフリット長８９、ターゲットＩＰの位置情報９０、それらに関わる制御情報９１を含む。
【００７８】
フリット２は、このパケットのアクセス属性９２とアクセスアドレス９３を含む。
【００７９】
フリット３からフリット６は、データ９４が格納されている。
【００８０】
ルート情報８７は、それぞれ、サブルータ５に入ったときに、当該パケットをどの方向に出力するかを指示したものである。
【００８１】
本実施例では、ルート情報１からルート情報４までの４個の情報を格納できることから、メインルータ又は目的地までに通るサブルータのホップ数は最大４となる。
【００８２】
また、複数のルート情報８７のうち、どれを参照すべきかのポインタ情報が制御情報８８に格納されている。
【００８３】
アクセス属性９２は、リード要求、リード応答、ライト要求等の属性があげられる。
【００８４】
以下、パケットの例を時間順に示して、本実施形態の動作を説明する。ここでは、図１のＢ３に位置するＩＰコア１から、Ｇ６に位置するＩＰコア１へパケットを送る場合について説明する。
【００８５】
最初に、Ｂ３側のＩＰに接続されているネットワークインタフェース２は、途中のホップ数４以内で目的地へのルーティング上ふさわしいメインルータまでのルーティングを行う。
【００８６】
本実施例では、４ホップ以内で目的のＩＰコアに到達できないことから、Ｅ３に位置するメインルータ、又は、Ｃ５に位置するメインルータに送ることとなる。ここでは、Ｅ３に送るものとする。その場合、Ｂ３のネットワークインタフェース２出力時点におけるパケットのフリット０、フリット１は、図５に示したようになる。
【００８７】
すなわち、図５において、図４のルート情報１〜４（８７）は、それぞれ１０１〜１０４に格納され、ルート情報１０１〜１０３がＥ方向、ルート情報１０４は有効な値でないため、Ｉｎｖａｌｉｄ（無効）となる。
【００８８】
また、図４の制御情報８８は、１０５で３となり、有効なデータが３個入っており、次にルート情報１０３を参照すべきであるということを示している。
【００８９】
また、ターゲットＩＰの位置が１０７に「Ｇ６」が格納され、フリット長１０６に８が格納されている。
【００９０】
このパケットは、Ｂ３のサブルータ３で、制御情報１０５が３であるため、ルート情報１０３を参照し、Ｅ側、すなわちＣ３側に出力される。この出力時点で、制御情報１０５は、Ｂ３のサブルータ３で１減算され、２とする。
【００９１】
Ｃ３のサブルータでは、同様に制御情報１０５が２であるため、ルート情報１０２を参照、Ｅ側すなわちＤ３に出力され、制御情報１０５はさらに１減算され１となる。
【００９２】
Ｄ３でも同様で、制御情報は０となった上で、Ｅ３に位置するメインルータ４に本パケットは到着する。
【００９３】
Ｅ３に位置するメインルータ４において、ルート計算部２２ｗは、フリット１のターゲット位置情報９０が１０８に示されるように、Ｇ６であることをデコードし、さらにＧ６には、ホップ数４以内で到達できないと判断する。
【００９４】
従って、最も近いＦ６のメインルータまでのルーティングを行う。
【００９５】
この場合、Ｅ３のメインルータ出力はＥ方向、すなわちＦ３となり、その後は。Ｓ方向に３ホップ進むため、パケット０は、図６に示されたように置き換えられる。すなわち、ルート情報１１１〜１１３がＳ方向、ルート情報１１４は有効な値でないため、Ｉｎｖａｌｉｄとなる。
【００９６】
また、制御情報８８（図４参照）は、１１５で３となり、ルート情報１１３をポインタとして示している。このフリットは、ルーティングフリット生成部２３ｗ（図２参照）で生成される。
【００９７】
これにより、先ほどの動作と同じように、Ｆ３、Ｆ４、Ｆ５のサブルータ３を経由して、Ｆ６のメインルータに至る。
【００９８】
Ｆ６に位置するメインルータ４において、ルート計算部２２ｎは、フリット１のターゲット位置情報９０（図４参照）が１０８に示されるようにＧ６であることをデコードし、さらに、Ｇ６にはホップ数４以内で到達できると判断する。
【００９９】
従って、ターゲット位置Ｇ６までのルーティングを行い、この場合、Ｆ６のメインルータ出力はＥ方向、すなわちＧ６となり、パケット０は、図７のように置き換えられる。
【０１００】
すなわち、ルート情報１２１には、ＩＰコアへの取り込みということが示され、ルート情報１２２〜１２４は有効な値でないため、Ｉｎｖａｌｉｄとなる。
【０１０１】
また、制御情報８８（図４参照）は、１２５で１となり、ルート情報１２１をポインタとして示している。このフリットは、ルーティングフリット生成部２３ｎ（図２参照）で生成される。
【０１０２】
これにより、Ｇ６のサブルータ３は取り込んだパケットのルート情報１２１を基に、当該パケットをＧ６のＩＰコア１に送ることができる。以上のようなルーティングによって、Ｂ３からＧ６へのデータの交信が可能になることがわかる。
【０１０３】
このとき、実際のルーティング計算を行ったのは、Ｂ３のネットワークインタフェースとＥ３、Ｆ６のメインルータ４だけであり、Ｂ３、Ｃ３、Ｄ３、Ｆ３、Ｆ４、Ｆ５、Ｇ６のサブルータ３では、フリット０のルート情報８７のみを参照して、ルーティングを行っている。このため、ルータの簡単化とルータを通過する遅延の短縮が可能である。
【０１０４】
メインルータ４におけるルーティング計算は、ターゲットＩＰ位置情報９０からメインルータ４の座標をＸ軸、Ｙ軸それぞれ減算した絶対値を加算する。この加算結果が最短のホップ数となるので、この加算結果が規定値を超えていないかどうかを判断する。該加算結果が規定値を超えていない場合には、この受信先までの各サブルータのルーティング情報をフリット０のルート情報８７に書き込む。
【０１０５】
該加算結果が規定値を超えている場合には、最もその受信先に近いメインルータを到達可能なメインルータ群から一つ選択し、このメインルータまでのサブルータのルーティング情報をフリット０のルート情報８７に書き込むことによって実現される。
【０１０６】
図５から図７の例では、サブルータのルーティング情報のみを、フリット０のルート情報８７のフィールドに書き込んでいるが、メインルータの出力方向も同様に書き込む仕様とすることも可能である。この場合、メインルータから次のメインルータ又は受信先までのルーティング情報が、完全な形でフリット０に残ることになる。
【０１０７】
また、メインルータ４において、パケットが到着した際に、制御情報８８（図４参照）を読み取り、０の値となっていない場合には、前段のメインルータ４で行ったルーティングが終わっていないことを判断できるため、当該メインルータ４において自律的なルーティングを行わないと判断し、フリット０中のルート情報８７を基に、ルーティングを行い、隣接するメインルータ４又はサブルータ３にパケットを転送する。
【０１０８】
この判断論理を加えることにより、オンチップネットワーク中のすべてのメインルータ４で自律的なルーティング計算を行う必要がなくなるため、メインルータ４の負荷を軽減することが可能である。
【０１０９】
しかしながら、メインルータ４は自律的なルーティングを行う能力を備えているため、当該メインルータ４を含んだルーティングが行われており、自律的なルーティングを行う必要がない場合においても、ルート情報８７（図４参照）を破棄し、再度ルーティングを行い、あらたなルート情報８７を書き込んだ上でパケットを送出することも可能である。
【０１１０】
一方で、２次元メッシュやそれに準じたネットワークトポロジを採ったオンチップネットワークでは、パケットは直進する確率が高くなる。このため、その特性を活かして、同一方向への転送回数を反復数としてルート情報に加えることにより、よりホップ数の多いルーティング情報を限られたフリットの領域に記すことが可能である。請求項５、６はこのような考え方に基づいたものである。
【０１１１】
図８に、このような情報を記したフリット０の例を示す。図８において、ルート情報１３７と制御情報１３８は、図４で示したルート情報８７と制御情報８８と同様であり、それぞれルータからどの方向へ出力するかという情報と、現在どの部分のルーティングまで完了しているかのポインタを示すものである。ここに、反復回数情報１３９を加える。
【０１１２】
反復回数情報１３９は、それぞれのルート情報１３７が何回繰り返されるかを示したものである。それぞれ、現在、何回反復したかの情報は、反復回数情報１３９をサブルータで更新してもよいし、制御情報１３８中のポインタに反復回数を含めた情報を持たせることも可能である。
【０１１３】
図９は、図１のＢ３に位置するＩＰコア１から、Ｇ６に位置するＩＰコア１への書き込みのパケットを送る場合に、本発明を適用した場合の、Ｂ３側のＩＰに接続されているネットワークインタフェース２が出力するパケットのフリット０を示したものである。
【０１１４】
本実施例では、図１における、Ｆ６に位置するメインルータ４までのルーティングをＢ３のネットワークインタフェース２が行っており、先に示した例と異なり、Ｅ３に位置するメインルータ４は、請求項４の発明に従ってサブルータと同様で自律的なルーティングを行わないものとしている。
【０１１５】
図９において、フリット０は、Ｂ３を出た後Ｅ方向に４ホップ、Ｓ方向に３ホップ進んでＦ６のメインルータ４に至るとしており、ホップ数の合計７が制御情報１４６に書き込まれている。進む方向はこの２種であるため、ルート情報３、反復情報３の１４４、１４５エントリはそれぞれＩｎｖａｌｉｄとされる。一方、まず、Ｅ方向へ４ホップ進むので、ルート情報２の１４２はＥ、反復情報２の１４３は４とされる。
【０１１６】
これにより、Ｂ３、Ｃ３、Ｄ３、Ｅ３、Ｆ３、Ｆ４、Ｆ５の各ルータは、制御情報１４６を１減算しながら、当該パケットをＦ６のメインルータ４に転送する。
【０１１７】
Ｆ６のメインルータ４は、到着したパケットの制御情報１４６が０であるため、ルーティングを行い、図７と同様のフリット０を生成し、Ｅ方向へパケットを送出する。これによって、パケットを所望のＩＰへ転送することができる。
Ｅ３のメインルータ４通過時に、例えばＦ３のルータやチャネルに故障や混在が生じている場合には、Ｅ３のメインルータ４は新たなルーティング計算を行い、その結果をフリット０に書き込んで別のルートで転送を行っても良いことは勿論である。
【０１１８】
フリットに書き込むルート情報のビットフィールドの制限から、整数の一意の値でホップ数を制限していたが、このようにルート情報に反復回数などの概念を加えると、高い反復回数ではホップ数の制限を緩和することが可能になる。このため、ホップ数の上限を、ある一定のルート情報フィールドおよび反復回数フィールドに入る範囲という状態することもできる。それによっても、ある程度の頻度でメインルータ４を通るルーティングをすることによって、故障、混雑を回避できる性質を残すことができる。
【０１１９】
ここでは、反復数とルート情報フィールドとを明確に分離したが、さらに圧縮率を高めた方法でルート情報を特定フリットに書き込んでもよい。
【０１２０】
本発明における、ルーティング手法を用いた場合には、サブルータ３のハードウェアコストや電力、レイテンシを短縮することが可能になるが、メインルータ４を経由するようなルーティングを行うために、メインルータ４にアクセスが集中しやすくなる傾向が生じる。
【０１２１】
本発明においては、メインルータ４とサブルータ３の配置分けは、ホップ数の上限以内に必ずメインルータ４を配置し、それ以外は、自由に、メインルータ４とサブルータ３を配置できる。従って、トラフィックが集中しそうなＩＰコア１が存在する場合、ＩＰコア１の周辺にメインルータ４を集中的に配置して、特定のメインルータ４へのアクセスを緩和することも可能である。
【０１２２】
図１０は、マルチコアＳｏＣ全体構成を示す図である。図１０のネットワークは、図１と同様であるが、トラフィックの混雑するＩＰコア１５１がＤ２の位置に存在する。そのため、近傍のＢ２、Ｅ３などのメインルータ１５４への負荷が集中する可能性がある。それを回避するために、予備のメインルータ１５６を、Ｂ３、Ｄ４、Ｅ１、Ｆ２に配置している。
【０１２３】
これらの予備のメインルータ１５６は、通常は、サブルータ１５３と同様に動作する。すわなち、予備のメインルータ１５６までのルーティング情報を付加したパケットを、他のメインルータ１５４やネットワークインタフェース１５３は生成しないため、自律的なルーティングを行わないものである。
【０１２４】
しかしながら、Ｄ２に位置するＩＰコア１５１へのアクセスが集中し、Ｂ２、Ｅ３に位置するメインルータ１５４へのチャネル１５５が混雑した場合には、その情報がＢ３、Ｄ４、Ｅ１、Ｆ２に配置している予備のメインルータ１５６に伝えられる。この場合、これらの予備のメインルータ１５６は、通過するパケットを、予備のメインルータ１５６内で再ルーティングして、Ｂ２、Ｅ３に位置するメインルータ４を通らずに、Ｄ２へ至るようにパケットを再ルーティングする。これにより、Ｂ２、Ｅ３のメインルータ４の負荷を軽減することが可能になる。
【０１２５】
このような負荷分散や故障回避の仕組みのために、本発明（請求項８）では、近傍のリンク、サブルータの混雑状況を把握する手段を備える。例えば、メインルータ４はリンクにおけるパケットの通過率、サブルータ３の各出力チャネルのパケット競合率、動作異常時にはその情報などを、各サブルータに最も近いメインルータ４との間の専用信号線やサブルータ３からメインルータ４への制御用パケットを用いて収集する。
【０１２６】
これらの情報を基にメインルータ４は、近傍のパケット混雑状況や故障状況を把握し、混雑を避けるルーティングを、到着したパケットに対して行う。
【０１２７】
また、本発明（請求項４）によって、自律的にルーティングする必要のないパケットがメインルータ４又は予備のメインルータ６に到着した場合でも、このような状況の場合には、ルート情報８７を破棄し、再度故障や混雑を回避したルーティングを行い、あらたなルート情報８７を書き込んだ上でパケットを送出することも可能である。
【０１２８】
また、サブルータ３が故障した場合、自律的なルーティング能力を具備していないため、利用可能なチャネルの中からどこにパケットを送出すればよいかを判断することができない。
【０１２９】
従って、本発明（請求項９）におけるサブルータ３は、故障を検出した際には、利用可能なチャネルの中から、近傍のメインルータ４に最もホップ数が近く到達できるルートを選択し、フリット０の制御情報８８を０として送出する。
【０１３０】
このようなパケットを受け取るルータがメインルータ４の場合には、そのままターゲットＩＰ位置情報９０で再度ルーティングを行う。
【０１３１】
一方、サブルータ３の場合には、前段のサブルータと同様に、利用可能なチャネルの中から、近傍のメインルータ４に最もホップ数が近く到達できるルートを選択し、フリット０の制御情報８８を０として送出する。この処理を繰り返すことによりメインルータ４に到達し、再度正しいルーティング情報によりパケットの伝送を再開可能である。
【０１３２】
これにより、サブルータ３はほとんどハードウェア複雑度を上昇することなく、ネットワークの信頼性を向上させることができる。
【０１３３】
一方で、メインルータ４は自律的な動作を求められるので、第１０発明で記したように、メインルータ４には、エラーに備えた冗長論理、又はエラー訂正検出機能を備えることにより、第９発明と組み合わせて、オンチップネットワーク全体の信頼性を向上させることも可能である。
【０１３４】
最後に本発明（請求項１１）を説明する。今まで説明してきた発明では、ルート情報は、メインルータ４又はネットワークインタフェース２が生成し、メインルータ４は、到着したパケットが保持する、当該メインルータまでのルート情報をフリットから削除し、新たなルート情報を同一のフリット、本実施の形態では、フリット０に書き込んで、パケットの転送を行っていた。
【０１３５】
この方法では、パケット長、すなわち１パケットが持つフリット数が送信元から受信先まで変化せず、ソースルーティング方式の問題の一つであった、ルーティングのホップ数が増加するとパケット長が増えて、また送信側がルーティングを行うコストが大きくなるという問題を解決可能である。
【０１３６】
しかしながら、例えば、リード要求のようなパケットは、送信元のＩＰコアに向けて、要求を受け取ったＩＰコアが、データを応答する必要がある。
【０１３７】
また、それ以外にも受領通知や、エラー発生時に送信元のＩＰコアに向けて応答パケットを送り返す必要が生じることがある。ルート情報を送信元からすべて保持しておけば、応答パケットでは、メインルータ４又はネットワークインタフェース２はルーティング計算を省くことが可能となる。
【０１３８】
本発明（請求項１１）では、メインルータ４でルーティングを行うたびにルート情報が入ったフリットを追加してゆくことにより、送信元からのルート情報をすべてパケット内に維持する方法を提案する。
【０１３９】
図１１は、図１のＢ３に位置するＩＰコア１から、Ｇ６に位置するＩＰコア１へパケットを送る場合の、Ｂ３に位置するネットワークインタフェース２の送出時点でのパケット２０１の構成を示している。ここでは、ルート情報２０７、制御情報２０８などに格納されているデータは、図６と同様である、ネットワークインタフェース２の行う処理は同等である。
【０１４０】
当該パケット２０１が、Ｅ３に位置するメインルータ４に到着した際、同様にルーティングを行うが、図１２に示したように、図１１の時点のフリット０がフリット２に移され、制御情報２１２は図１２に示したように過去のルーティングのログである旨のフラグがセットされる。
【０１４１】
また、パケット２０１のフリット長がのびるため、フリット長ビット２０９は１加算され、８となる。また、新たに追加されるフリット０では、ルート情報に２０７に本メインルータ４からの出力チャネルも書き加えられるため、ＳＥＥＥという値が格納される。
【０１４２】
同様に、Ｆ６に位置するメインルータ４では、図１３に示すように、フリット２がフリット３に、フリット０がフリット２にそれぞれ移動され、新たなフリット０を加える、フリット長２０９はさらに１加算され９となる。
【０１４３】
これにより、当該パケットがＧ６に到達した時点では、Ｂ３までのすべてのルーティング情報がフリットに記載されていることになる。
【０１４４】
その後、Ｇ６からＢ３へ応答パケットを送る場合には、図１４に示したように、受け取ったルーティング情報の方向と順序を逆にして制御情報フィールド２１２をルーティング予告として、折り返す。これにより、応答パケットはルーティング計算を行うことなく、パケットをＢ３に位置するＩＰコア１まで送り返すことが可能になる。
【０１４５】
もちろん、このような、ルート情報をパケットに残すルーティングは特定属性のパケット転送のみに行うことも可能である。
【０１４６】
以下に本実施形態の作用効果を説明する。
【０１４７】
メインルータによって、複数ルータのルーティング計算を一括して行い、他のサブルータはそれに従ってパケット転送を行うことになるので、サブルータの簡単化を図ることができる。全体として、ネットワークレイテンシの短縮と面積コスト、電力コストの削減が可能になる。
【０１４８】
また、ソースルーティング方式の欠点であったスケーラビリティの問題と、ローカルに生じた不具合、混雑への対応が容易にできるようになり、ネットワークの高信頼化を図ることができる。
なお、上記の特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１４９】
１  ＩＰコア
２  ネットワークインタフェース
３  サブルータ
４  メインルータ
５  チャネル
１０  マルチコアＳｏＣ（Ｓｙｓｔｅｍ  ｏｎ  ａ  Ｃｈｉｐ）
２１  入力ラッチ
２２  ルート計算部
２３  ルーティングフリット生成部
２４  セレクタ
２５  入力ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）バッファ
２６  クロスバスイッチ
２７  アービタ
２８  セレクタ
２９  出力バッファ
４５  入力ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）バッファ
４６  クロスバスイッチ
４７  アービタ
４８  セレクタ
４９  出力バッファ
８１  パケット
８２  サイドバンド属性信号
８３  有効ビット
８４  先頭ビット
８５  終端ビット
８６  パケットボディ
８７  ルート情報フィールド
８８  制御情報フィールド
８９  フリット長フィールド
９０  ターゲットＩＰ位置情報フィールド    
９１  制御情報フィールド
９２  アクセス属性フィールド
９３  アクセスアドレスフィールド
９４  データフィールド
１０１  ルート情報フィールド１
１０２  ルート情報フィールド２
１０３  ルート情報フィールド３
１０４  ルート情報フィールド４
１０５  制御情報フィールド
１０６  フリット長フィールド
１０７  ターゲットＩＰ位置情報フィールド
１０８  制御情報フィールド
１１１  ルート情報フィールド１
１１２  ルート情報フィールド２
１１３  ルート情報フィールド３
１１４  ルート情報フィールド４
１１５  制御情報フィールド
１２１  ルート情報フィールド１
１２２  ルート情報フィールド２
１２３  ルート情報フィールド３
１２４  ルート情報フィールド４
１２５  制御情報フィールド
１３７  ルート情報フィールド
１３８  制御情報フィールド
１３９  反復回数フィールド
１４０  ルート情報フィールド
１４１  反復回数フィールド
１４２  ルート情報フィールド
１４３  反復回数フィールド
１４４  ルート情報フィールド
１４５  反復回数フィールド
１４６  制御情報フィールド
１５１  ＩＰコア
１５２  ネットワークインタフェース
１５３  サブルータ
１５４  メインルータ
１５５  チャネル
１５６  予備のメインルータ
１６０  マルチコアＳｏＣ（Ｓｙｓｔｅｍ  ｏｎ  ａ  Ｃｈｉｐ）
２０１  パケット
２０２  サイドバンド属性信号
２０３  有効ビット
２０４  先頭ビット
２０５  終端ビット
２０６  パケットボディ
２０７  ルート情報フィールド
２０８  制御情報フィールド
２０９  フリット長フィールド
２１０  ターゲットＩＰ位置情報フィールド    
２１１  制御情報フィールド
２１２  制御情報フィールド
３０１  マルチコアＳｏＣ（Ｓｙｓｔｅｍ  ｏｎ  ａ  Ｃｈｉｐ）
３０２  ルータ
３０３  ＩＰコア
３０４  ネットワークインタフェース
３０５  チャネル
３２１  パケットボディ信号
３２２  サイドバンド属性信号
３２３  ターゲットＩＰ位置情報
３２４  フリット長
３２５  制御情報
３２６  アクセスアドレス
３２７  アクセス属性など
３２８  データ
３５１  ルータ
３５２  通信チャネル
３５３  交信例に用いられる通信チャネル
３５４  交信例に用いられる仮想Ｅｘｐｒｅｓｓチャネル
３６１  ＤＩＤ（Ｄｅｓｔｉｎａｔｉｏｎ  ＩＤｓ）
３６２  Ｃｈａｉｎｅｄ  Ｈｅａｄｅｒ
３８１  オプションタイプフィールド
３８２  オプション長フィールド
３８３  ポインタフィールド
３８４  ＩＰアドレスフィールド
【図１】
2010137572.tif 000003
【図２】
2010137572.tif 000004
【図３】
2010137572.tif 000005
【図４】
2010137572.tif 000006
【図５】
2010137572.tif 000007
【図６】
2010137572.tif 000008
【図７】
2010137572.tif 000009
【図８】
2010137572.tif 000010
【図９】
2010137572.tif 000011
【図１０】
2010137572.tif 000012
【図１１】
2010137572.tif 000013
【図１２】
2010137572.tif 000014
【図１３】
2010137572.tif 000015
【図１４】
2010137572.tif 000016
【図１５】
2010137572.tif 000017
【図１６】
2010137572.tif 000018
【図１７】
2010137572.tif 000019
【図１８】
2010137572.tif 000020
【図１９】
2010137572.tif 000021
【国際調査報告】
2010137572.tif 000022
2010137572.tif 000023
2010137572.tif 000024
2010137572.tif 000025