(57)【特許請求の範囲】
【請求項１】
分散型バスを備える集積回路において、前記分散型バス上の送信ノードから受信ノードに至る伝送経路上に設けられてデータを中継する中継器であって、
前記分散型バスには、前記中継器から前記受信ノードに至る第１経路、および第２経路が存在しており、
データを格納するための複数のデータ格納部を有する入力バッファと、
前記入力バッファに格納された前記データを出力する出力部であって、複数の出力ポートを含む出力部と、
前記データを解析することにより、前記複数の出力ポートの中から、前記データを出力する出力ポートを決定するルーティング処理部と、
前記データを格納した特定のデータ格納部、および前記ルーティング処理部によって決定された前記出力ポート先の中継器の入力バッファに設けられたデータ格納部を対応付けるバッファアロケータと、
前記バッファアロケータの対応付けに基づいて、前記データを転送させるためのスケジュールを決定するスイッチアロケータと、
前記第１経路上の他の中継器、および前記第２経路上の他の中継器に前記データの転送許可の要求を送信し、所定の待機時間が経過するまでの間に前記要求に対する許可が得られたか否かに応じて、前記第１経路および前記第２経路のそれぞれの異常の有無を検出する通知部と
を備えた中継器。
【請求項２】
前記所定の待機時間が経過するまでの間に前記要求に対する許可が得られなかったときは、前記通知部は、前記入力バッファおよび前記出力部の少なくとも一方に対して前記データを廃棄させる、請求項１に記載の中継器。
【請求項３】
前記所定の待機時間が経過するまでの間に前記要求に対する許可が得られたときは、前記通知部は、前記第１経路および前記第２経路のうち、前記許可が得られた方の経路に接続された出力ポートから前記データを伝送させる、請求項１に記載の中継器。
【請求項４】
前記所定の待機時間が経過するまでの間に、前記第１経路の他の中継器および前記第２経路の他の中継器の両方から、前記要求に対する許可が得られたときは、前記通知部は、より早く許可が得られた方の経路に接続された出力ポートから前記データを伝送させる、請求項１に記載の中継器。
【請求項５】
前記分散型バスは、リセット用共通線をさらに有し、前記リセット用共通線には前記第１経路の他の中継器および前記第２経路の他の中継器の少なくとも一方が接続されており、
前記所定の待機時間が経過するまでの間に前記要求に対する許可が得られなかったときは、前記通知部は、前記リセット用共通線を介して、前記第１経路の他の中継器、前記第２経路の他の中継器、前記送信ノード、および前記受信ノードの少なくとも１つに異常を通知する、請求項１または２に記載の中継器。
【請求項６】
前記分散型バスは、リセット用共通線をさらに有し、
前記リセット用共通線を介して伝送経路の異常の通知を受けたときは、前記通知部は、前記入力バッファに格納された前記データを廃棄する、請求項１または２に記載の中継器。
【請求項７】
前記通知部は、前記所定の待機時間として、前記送信ノードから前記受信ノードに至る伝送経路上に存在する中継器の数に応じて定められる時間を設定する、請求項１に記載の中継器。
【請求項８】
前記送信ノードであるバスマスタから、前記受信ノードであるメモリに至る伝送経路上に設けられて前記データを中継する、請求項１から７のいずれかに記載の中継器。
【請求項９】
分散型バスを備える集積回路において、前記分散型バス上の送信ノードから受信ノードに至る伝送経路上に設けられてデータを中継する中継器の制御方法であって、
前記分散型バスには、前記中継器から前記受信ノードに至る第１経路、および第２経路が存在しており、
前記中継器は、
データを格納するための複数のデータ格納部を有する入力バッファと、
前記入力バッファに格納された前記データを出力する出力部であって、複数の出力ポートを含む出力部と、
前記データを解析することにより、前記複数の出力ポートの中から、前記データを出力する出力ポートを決定するルーティング処理部と、
前記データを格納した特定のデータ格納部、および前記ルーティング処理部によって決定された前記出力ポート先の中継器の入力バッファに設けられたデータ格納部を対応付けるバッファアロケータと、
前記バッファアロケータの対応付けに基づいて、前記データを転送させるためのスケジュールを決定するスイッチアロケータと
を有しており、
前記第１経路上の他の中継器、および前記第２経路上の他の中継器に前記データの転送許可の要求を送信するステップと、
所定の待機時間が経過するまでの間に前記要求に対する許可が得られたか否かに応じて、前記第１経路および前記第２経路のそれぞれの異常の有無を検出するステップと
を包含する、中継器の制御方法。
【請求項１０】
分散型バス上の送信ノードから受信ノードに至る伝送経路上に設けられてデータを中継する中継器のシミュレーションを行うためのコンピュータプログラムであって、
前記コンピュータプログラムは、コンピュータに対し、請求項９に記載の中継器の制御方法を実行させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、バスを備えた半導体システムにおける迂回伝送制御方式および、迂回伝送システムに関する。
【背景技術】
【０００２】
バスを備えたデータ伝送システムにおける伝送制御には種々の方式がある。図１（ａ）および（ｂ）は、従来の半導体システムにおける伝送制御方式の例を示す図である。図１（ａ）は、従来の集中型のバス制御の例を示している。図示される集中型のバス制御によれば、複数のバスマスタとメモリとの間が１本のバスで接続され、アービタによって各バスマスタからメモリへのアクセスが調停される。このような構成により、複数のバスマスタとメモリとの間のトラヒック干渉を防ぎながらデータを伝送することができる。しかしながら、集積回路の高機能化およびマルチコア化による回路規模の増大、および伝送路を流れるトラヒックの変動の複雑化が進んでおり、集中型のバス制御による集積回路の設計が困難になってきている。【０００３】
その一方で、近年、並列計算機における接続技術や、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）網などのネットワーク制御技術を取り入れた分散型のバスを有する半導体集積回路の開発が進んでいる。図１（ｂ）は、分散型のバス制御の例を示している。分散型のバスを有する半導体集積回路は、複数の中継器（Ｒ）が複数のバスでメッシュ状に接続された構成を有している。近年、図１（ｂ）に示すような分散型のバスを用いることにより、大規模化した集積回路内のトラヒックを複数のバスに分散して伝送するネットワークオンチップ（Ｎｅｔｗｏｒｋ  ｏｎ  Ｃｈｉｐ；ＮｏＣ）の取り組みが広がっている。【０００４】
図２は、ＮｏＣ、並列計算機、ＡＴＭ網などで利用される中継器の構成例を示す図である。伝送されるデータ（トラヒックデータ）は、パケットやセルの単位に分割され、複数の中継器を経由して宛先のノードまで送信される。図２に示す中継器は、複数の入力ポート０〜３と、複数の入力バッファと、複数の出力ポート０〜３と、各入力バッファおよび各出力ポートを相互に接続するクロスバスイッチとを備えている。図示される中継器は、さらに、データの宛先に応じてクロスバスイッチの接続を切り替える制御を行うアービタを備えている。入力ポート０〜３から中継器に入力されたデータは、一旦入力バッファに蓄えられる。中継器は、アービタによってクロスバスイッチの接続を切り替えることにより、バッファ内に格納されたデータを宛先へと中継する。【０００５】
中継器内では、各バッファでの待ち合わせ、クロスバスイッチでの処理遅延などにより、トラヒックデータの転送処理に遅延が発生することがある。ネットワークの規模が大きくなるほど中継器の数が増加するため、遅延は一層増加し問題となる。緊急性の高いトラヒックデータを取り扱うアプリケーション（例えば、緊急情報の通知のためのアプリケーション）の存在を考慮すると、この遅延を如何に低減させ、遅延を最小限に抑えるかが課題となる。【０００６】
イーサネット（登録商標）回線を用いるような一般のネットワークでは、中継器のバッファでのパケットの溢れに応じて、中継器が自動的にパケットを廃棄する。【０００７】
一方、半導体のバスを用いるＮｏＣでは、一般のネットワークと異なり、中継器はパケットを廃棄しない。その理由は、ネットワークに接続されるバスマスタ等が予め想定され、ネットワーク上を流れるトラヒックデータのデータ量を見込むことができるため、パケットを廃棄しなくてもよいようＮｏＣを設計できるからである。【０００８】
しかしながら、システムの不具合や設計ミスなどでバスが過負荷になることがあり得る。また、ＮｏＣ上に設けた迂回路を活用してパケットを伝送する場合には、事前設計がそもそも困難である。このような場合においても、要求された仕様を全体として満たすようなＮｏＣが必要とされる。【０００９】
特許文献１は、上述したＮｏＣを得るための伝送経路の選択方法を開示している。図３は、当初の伝送経路でデータを伝送できない場合に、他の伝送経路を選択する際の模式図である。図３に示すように、まず、（１）伝送を行った経路で、一定時間内に応答がなければ（タイムアウトが発生すれば）、（２）予め定められたルートの確率分布に従って、複数の予め定められた経路の１つを選択し、パケットの再送を行う。これにより、高い伝送効率を得られやすい伝送路を選択する方法が提案されている。【００１０】
また、特許文献２は、パケットを廃棄する技術に関している。特許文献２は、情報の鮮度を保つために、優先度に応じてパケット廃棄までの待機時間を決定する方法を提案している。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特許第３８１６５３１号明細書
【特許文献２】特開２０００−２８６８９３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上述した従来の技術では、パケットの伝送効率をより高めることが求められていた。【００１３】
本願の、限定的ではない例示的なある実施形態は、たとえば伝送障害が発生しているのかどうかを検出して、効率的なパケット伝送を実現する技術を提供する。
【課題を解決するための手段】
【００１４】
上記課題を解決するために、本発明の一態様は、分散型バスを備える集積回路において、前記分散型バス上の送信ノードから受信ノードに至る伝送経路上に設けられてデータを中継する中継器であって、前記分散型バスには、前記中継器から前記受信ノードに至る第１経路、および第２経路が存在しており、データを格納するための複数のデータ格納部を有する入力バッファと、前記入力バッファに格納された前記データを出力する出力部であって、複数の出力ポートを含む出力部と、前記データを解析することにより、前記複数の出力ポートの中から、前記データを出力する出力ポートを決定するルーティング処理部と、前記データを格納した特定のデータ格納部、および前記ルーティング処理部によって決定された前記出力ポート先の中継器の入力バッファに設けられたデータ格納部を対応付けるバッファアロケータと、前記バッファアロケータの対応付けに基づいて、前記データを転送させるためのスケジュールを決定するスイッチアロケータと、前記第１経路上の他の中継器、および前記第２経路上の他の中継器に前記データの転送許可の要求を送信し、所定の待機時間が経過するまでの間に前記要求に対する許可が得られたか否かに応じて、前記第１経路および前記第２経路のそれぞれの異常の有無を検出する通知部とを備えた中継器を含む。【００１５】
上述の一般的かつ特定の態様は、システム、方法およびコンピュータプログラムを用いて実装され、またはシステム、方法およびコンピュータプログラムの組み合わせを用いて実現され得る。
【発明の効果】
【００１６】
本発明の一実施形態によれば、伝送障害が発生しているのかどうかを検出して、効率的なパケット伝送を実現することが可能である。
【図面の簡単な説明】
【００１７】
【図１】（ａ）および（ｂ）は、従来の半導体システムにおける伝送制御方式の例を示す図である。
【図２】ＮｏＣ、並列計算機、ＡＴＭ網などで利用される中継器の構成例を示す図である。
【図３】当初の伝送経路でデータを伝送できない場合に、他の伝送経路を選択する際の模式図である。
【図４】本発明の例示的な一実施形態による中継器を用いたデータ伝送システムの構成例を示す図である。
【図５】（ａ）および（ｂ）は、本発明の例示的な一実施形態におけるデータ伝送システムの一部を示すブロック図である。
【図６】パケット５００の伝送フォーマットの一例と、パケット５００を複数のフリットに分割した例とを示す図である。
【図７】本発明の例示的な一実施形態における中継器の概略構成を示す図である。
【図８】障害および混雑が存在するデータ伝送システムを示す図である。
【図９】中継器６００ｂの動作を説明するための図である。
【図１０】一般的な中継器の処理の手順を示す図である。
【図１１】（ａ）および（ｂ）は、パケット送信待機時間を説明する図である。
【図１２】パケット送信待機時間を決定するパラメータと、パケット送信待機時間の決定方法の対応関係を示す図である。
【図１３】中継器６００ｂでのパケット廃棄に伴い、他のノードへの通知を説明する図である。
【図１４】（ａ）および（ｂ）は、本発明の例示的な一実施形態による、迂回路を用いた並列伝送への応用例を示す図である。
【図１５】本発明の例示的な一実施形態による迂回処理の概要を説明する図である。
【図１６】迂回路先の中継器１２０２の動作の手順を示す図である。
【図１７】迂回元の中継器１２０１の動作の手順を示す図である。
【図１８】（ａ）はメッシュ型のトポロジの例を示す図であり、（ｂ）はトーラス型のトポロジの例を示す図であり、（ｃ）は階層型のトポロジの例を示す図である。
【図１９】半導体回路上の複数のバスマスタと複数のメモリとを分散型のバスを利用して接続した例を示す図である。
【図２０】ＣＰＵやＧＰＵ，ＤＳＰ等のコアプロセッサの処理能力を向上させるために、複数のコアプロセッサをメッシュ状に配列し、これらを分散バスで接続したマルチコアプロセッサを示す図である。
【発明を実施するための形態】
【００１８】
本願発明者らは、上述した従来の技術の問題を検討した。
【００１９】
従来のＮｏＣ技術では、送信ノードと受信ノード間で伝送路の利用状態を監視して、伝送経路の選択を行うため、トラヒックの急激な変動に対しては追随が難しい。また、トラヒックの要求品質（スループット、伝送遅延など）を加味していないため、要求遅延が厳しいトラヒックを伝送する場合は、伝送処理が間に合わなくなる可能性が生じる。
【００２０】
このための解決策としては、特許文献１で示されているように適切な迂回路を選択する方法が考えられるが、必ずしも、迂回路が事前に用意されていたり、適切な迂回路を選択できるとは限らない。その理由は、迂回により、新たな混雑を引き起こす可能性が生じるからである。また、システムの不具合や設計ミスなどでバスが過負荷の場合には、その状況を生み出す可能性が大きいからである。
【００２１】
また、特許文献２で示されているような、優先度に応じてパケット廃棄までの待機時間を決定する方法では、伝送処理されている全てのパケットの優先度が同一である場合には対処できない。
【００２２】
本発明の一態様の概要は以下のとおりである。
【００２３】
本発明の一態様である中継器は、分散型バスを備える集積回路において、前記分散型バス上の送信ノードから受信ノードに至る伝送経路上に設けられてデータを中継する中継器であって、前記分散型バスには、前記中継器から前記受信ノードに至る第１経路、および第２経路が存在しており、データを格納するための複数のデータ格納部を有する入力バッファと、前記入力バッファに格納された前記データを出力する出力部であって、複数の出力ポートを含む出力部と、前記データを解析することにより、前記複数の出力ポートの中から、前記データを出力する出力ポートを決定するルーティング処理部と、前記データを格納した特定のデータ格納部、および前記ルーティング処理部によって決定された前記出力ポート先の中継器の入力バッファに設けられたデータ格納部を対応付けるバッファアロケータと、前記バッファアロケータの対応付けに基づいて、前記データを転送させるためのスケジュールを決定するスイッチアロケータと、前記第１経路上の他の中継器、および前記第２経路上の他の中継器に前記データの転送許可の要求を送信し、所定の待機時間が経過するまでの間に前記要求に対する許可が得られたか否かに応じて、前記第１経路および前記第２経路のそれぞれの異常の有無を検出する通知部とを備えている。
【００２４】
ある態様において、前記所定の待機時間が経過するまでの間に前記要求に対する許可が得られなかったときは、前記通知部は、前記入力バッファおよび前記出力部の少なくとも一方に対して前記データを廃棄させる。
【００２５】
ある態様において、前記所定の待機時間が経過するまでの間に前記要求に対する許可が得られたときは、前記通知部は、前記第１経路および前記第２経路のうち、前記許可が得られた方の経路に接続された出力ポートから前記データを伝送させる。
【００２６】
ある態様において、前記所定の待機時間が経過するまでの間に、前記第１経路の他の中継器および前記第２経路の他の中継器の両方から、前記要求に対する許可が得られたときは、前記通知部は、より早く許可が得られた方の経路に接続された出力ポートから前記データを伝送させる。
【００２７】
ある態様において、前記分散型バスは、リセット用共通線をさらに有し、前記リセット用共通線には前記第１経路の他の中継器および前記第２経路の他の中継器の少なくとも一方が接続されており、前記所定の待機時間が経過するまでの間に前記要求に対する許可が得られなかったときは、前記通知部は、前記リセット用共通線を介して、前記第１経路の他の中継器、前記第２経路の他の中継器、前記送信ノード、および前記受信ノードの少なくとも１つに異常を通知する。
【００２８】
ある態様において、前記分散型バスは、リセット用共通線をさらに有し、前記リセット用共通線を介して伝送経路の異常の通知を受けたときは、前記通知部は、前記入力バッファに格納された前記データを廃棄する。
【００２９】
ある態様において、前記通知部は、前記所定の待機時間として、前記送信ノードから前記受信ノードに至る伝送経路上に存在する中継器の数に応じて定められる時間を設定する。
【００３０】
ある態様において、前記送信ノードであるバスマスタから、前記受信ノードであるメモリに至る伝送経路上に設けられて前記データを中継する。
【００３１】
本発明の他の一態様である方法は、分散型バスを備える集積回路において、前記分散型バス上の送信ノードから受信ノードに至る伝送経路上に設けられてデータを中継する中継器の制御方法であって、前記分散型バスには、前記中継器から前記受信ノードに至る第１経路、および第２経路が存在しており、前記中継器は、データを格納するための複数のデータ格納部を有する入力バッファと、前記入力バッファに格納された前記データを出力する出力部であって、複数の出力ポートを含む出力部と、前記データを解析することにより、前記複数の出力ポートの中から、前記データを出力する出力ポートを決定するルーティング処理部と、前記データを格納した特定のデータ格納部、および前記ルーティング処理部によって決定された前記出力ポート先の中継器の入力バッファに設けられたデータ格納部を対応付けるバッファアロケータと、前記バッファアロケータの対応付けに基づいて、前記データを転送させるためのスケジュールを決定するスイッチアロケータとを有しており、前記第１経路上の他の中継器、および前記第２経路上の他の中継器に前記データの転送許可の要求を送信するステップと、所定の待機時間が経過するまでの間に前記要求に対する許可が得られたか否かに応じて、前記第１経路および前記第２経路のそれぞれの異常の有無を検出するステップとを包含する。
【００３２】
本発明のさらに他の一態様であるコンピュータプログラムは、分散型バス上の送信ノードから受信ノードに至る伝送経路上に設けられてデータを中継する中継器のシミュレーションを行うためのコンピュータプログラムであって、前記コンピュータプログラムは、コンピュータに対し、上述の中継器の制御方法を実行させる。
【００３３】
第１経路である主経路に転送許可の要求を送信し、最長で前記待機時間が経過するまでの間、主経路の中継器の許可を待ってもよい。転送許可の要求先の中継器は、例えば最隣接となる中継器であってよい。主経路と、第２経路である迂回路の中継器に同時に転送許可の要求を発行してもよい。所定の待機時間の時間以内に、許可が得られた場合は、早く許可が得られた伝送経路の方にデータを伝送する。これにより、より混雑が少ない伝送経路を選択することが可能となり、低遅延化や高スループット化が期待できる。また、主経路と迂回路は、固定的に定まるものではない。マスタ毎やユースケース毎に主経路と迂回路を異なるように定義してもよい。さらに、迂回路は複数個、存在する形態であってもよい。例えば、メッシュ網では１つの主経路に対して、迂回路は３つ定義することができる。また、リングバスにおいては、１つの主経路と１つの迂回路を定義することができる。
【００３４】
以下、添付の図面を参照しながら、本発明の例示的な一実施形態にかかる中継器を説明する。
【００３５】
本実施形態の中継器は、パケットの伝送遅延が発生している場合において伝送効率を高めるための処理を行う。
【００３６】
汎用的な混雑時の伝送パケットの処理方法としては、パケットを待機させるか、パケットの廃棄を行うかの２通りが考えられる。パケット待機は、混雑時でもパケット送信を待機させることでパケットの損失が無くなる。その代わりに、混雑の影響が伝搬する可能性がある。
【００３７】
また、パケット廃棄は、混雑時にパケットを廃棄させることで、混雑の解消は早くなる。その代わりに、損失したパケット回復が必要となる。
【００３８】
パケット待機を行いすぎると混雑を引き起こしやすくなり、伝送品質の劣化の問題が大きくなる。また、パケット廃棄を行いすぎると安定した伝送が行いにくくなり、伝送品質の劣化の問題が生じやすくなる。
【００３９】
本実施形態の中継器は、パケットの待機およびパケットの廃棄の一方を行うのではなく、パケットの待機とパケットの廃棄をバランスさせて実行することで、パケットの伝送効率を高める。
【００４０】
以下、中継器の構成および動作を詳細に説明する。
【００４１】
＜１．システム構成＞
図４は、本実施形態による中継器を用いたデータ伝送システムの構成例を示す図である。図示されるシステムは、送信ノードとして複数のバスマスタ（ＢＭ）１０１を有し、受信ノードとして複数のメモリ１０５を有している。複数のバスマスタ１０１および複数のメモリ１０５は、複数の中継器６００を介してバスで多段に接続されている。このように、図４に示す伝送システムは、多段接続網（Ｍｕｌｔｉｓｔａｇｅ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ  Ｎｅｔｗｏｒｋ：ＭＩＮ）を構成している。本実施形態では、個々のバスマスタ１０１が本開示における第１ノードとして機能し、個々のメモリ１０５が本開示における第２ノードとして機能する。
【００４２】
本実施形態におけるバスマスタ１０１は、例えばプロセッサやＤＳＰなどの、バスを用いてデータの転送制御を行うことができるデバイスである。メモリ１０５は、例えばＤＲＡＭやＳＲＡＭ等の半導体メモリである。なお、本開示の実施形態としては、メモリ１０５を、プロセッサ、ＤＳＰ、Ｉ/Ｏなど、メモリ以外のノードを接続する形態で構成してもよい。中継器６００は、例えば半導体回路であり、複数のバスマスタ１０１および複数のメモリ１０５の間で伝送されるデータを中継する機能を備えている。
【００４３】
図４に示す構成例では、８個のバスマスタ（ＢＭ０〜ＢＭ７）と、１２個の中継器（Ｒ０〜Ｒ１１）と、８個のメモリ（メモリ０〜７）とがバスで接続されている。１２個の中継器は、３つのグループに分類されている。第１のグループ（第１Ｇ）は、８個のバスマスタ１０１に接続される４個の中継器（Ｒ０、Ｒ１、Ｒ２、Ｒ３）を含んでいる。第２のグループ（第２Ｇ）は、第１のグループの後段に接続される４個の中継器（Ｒ４、Ｒ５、Ｒ６、Ｒ７）を含んでいる。第３のグループは、第２のグループの後段に接続され、８個のメモリに接続される４個の中継器（Ｒ８、Ｒ９、Ｒ１０、Ｒ１１）を含んでいる。
【００４４】
バスマスタ１０１からメモリ１０５へのデータ伝送は、パケット交換方式により行われる。各バスマスタは、図４（ａ）に示すように、送信すべきパケットをフリットと呼ばれる最小単位に分割してから隣接の中継器に送信する。１つのパケットを分割した複数のフリットのうち、最初に送信されるフリットは、ヘッダフリットと呼ばれる。ヘッダフリットには、パケットの先頭であることを示すフラグ情報や、パケットの送信先のアドレス情報などが記述されている。本実施形態におけるパケットおよびフリットのデータ構造の詳細は後述する。
【００４５】
図４に示す多段接続網を構成する各中継器は、２入力２出力のクロスバスイッチを備えている。各中継器は、図４（ｂ）に示すように、クロスバスイッチを切り替えることによって入力と出力の組合せを変更することができる。このため、トラヒックの流れを２つの伝送経路（伝送経路１、２）の間で切り替えることができる。出力先の伝送経路が異なっていれば、中継器は２つのトラヒックを各伝送経路に同時に出力することが可能である。このような多段接続網によれば、各中継器でのスイッチの切り替えによって、全バスマスタと全メモリ間で、必ず１つ以上の伝送経路を構築することができる。
【００４６】
一般に、クロスバスイッチによってＮ個のバスマスタとＭ個のメモリの全てを接続するためには、Ｎ×Ｍ個のスイッチが必要となる。ここで、スイッチとは、ある方向に並行する複数の通信路と他の方向に並行する複数の通信路との交点に設けられ、ＯＮ／ＯＦＦの切り替えによって通信路を動的に構築できるものをいう。必要なスイッチの数は、バスマスタやメモリの数が増えるにつれて急激に増加してしまう。これに対し、多段接続網では、入出力数の少ないクロスバスイッチを階層的に接続することにより、少ないスイッチでバスマスタとメモリとの間の接続を切り替えることができる。
【００４７】
図４に示す構成において、例えば、ＢＭ２からメモリ５へとデータが伝送される場合、ＢＭ２は、メモリ５のアドレス（１０１）が送信先アドレスとして記述されたパケットを複数のフリットに分割し、中継器Ｒ１に送信する。分割された複数のフリットは、中継器Ｒ１、Ｒ７、Ｒ１０を経てメモリ５へと送信される。メモリ５は、中継器Ｒ１０から送信された複数のフリットを受け取り、これらのフリットからパケットを再構築する。以上の処理により、ＢＭ２からメモリ５へとデータが伝送される。
【００４８】
なお、本実施形態における中継器は、図４に示すような多段接続網を構成する集積回路に限らず、他のトポロジを有する集積回路であっても同様に適用することが可能である。また、本実施形態では、バスマスタからメモリへのデータ転送は、パケット交換方式により複数の中継器を介して行われるものとして説明するが、データ転送方式は他の方式であってもよい。本実施形態の中継器は、バスマスタからメモリへのデータ伝送に限らず、複数のノード間でデータを伝送するシステムであれば、同様に適用することができる。
【００４９】
図４に示す構成では、第１および第３グループの各中継器（Ｒ０〜Ｒ３、Ｒ８〜Ｒ１１）は、第２グループの各中継器（Ｒ４〜Ｒ７）と同様、１つの機能ブロックとして描かれている。しかし、実際には、第１グループの各中継器とバスマスタとの間、および第３グループの各中継器とメモリとの間には、ＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃｏｎｔｒｏｌｌｅｒ）等の他の機能部が接続される。
【００５０】
図５は、本実施形態におけるデータ伝送システムの一部を示すブロック図である。図５では、簡単のため、１本の伝送経路上に接続された１組のバスマスタ１０１、第１グループの中継器６００ａ、第２グループの中継器６００ｂ、第３グループの中継器６００ｃ、およびメモリ１０５のみを示している。
【００５１】
図５（ａ）に示すように、バスマスタ１０１と第１グループの中継器６００ａとの間には、ＮＩＣ６２０ａが接続される。ＮＩＣ６２０ａは、バスプロトコルの変換処理や、バスマスタ１０１が要求するメモリサイズを確保できるメモリ１０５を複数のメモリの中から選択し、選択したメモリ１０５をバスマスタ１０１に通知する機能を備えている。
【００５２】
一方、第３グループの中継器６００ｃとメモリ１０５との間には、ＮＩＣ６２０ｃおよびメモリコントローラ６３０が接続される。ＮＩＣ６２０ｃは、バスプロトコル変換処理や、データ伝送の往路と復路との対応関係付けを行い、往路に対する復路の応答をＮＩＣ６２０ａへ返信する。ここで、往路とはバスマスタ１０１からメモリ１０５への方向の伝送経路を意味し、復路とはメモリ１０５からバスマスタ１０１への方向の伝送経路を意味する。メモリコントローラ６３０は、ＮＩＣ６２０ｃに接続され、メモリ１０５へのアクセス順序の制御などを行う。
【００５３】
本明細書では、表記を簡略化するために、図５（ｂ）に示すように、ＮＩＣ６２０ａ、６２０ｃ、およびメモリコントローラ６３０の表記を省略する。すなわち、以下の説明においては、バスマスタ１０１などの送信ノードに直接接続された中継器は、ＮＩＣを含んでいるものとする。同様に、メモリ１０５などの受信ノードに直接接続された中継器はＮＩＣおよびメモリコントローラを含んでいるものとする。
【００５４】
なお、記載の簡略化のため、図面には主として伝送経路のみを示しているが、実際には「リセット用共通線」と呼ぶ、異なる配線も設けられている。「リセット用共通線」の詳細は、たとえば図７に関連して説明する。
【００５５】
＜２．パケット、フリットの構成＞
次に、本実施形態におけるパケットおよびフリットの構造を説明する。なお、本実施形態では、パケットまたはフリットを例として説明しているが、伝送に際してパケット化することは設計事項に過ぎない。パケットまたはフリットを一般化して、単に「データ」と呼んでもよい。
【００５６】
図６は、パケット５００の伝送フォーマットの一例と、パケット５００を複数のフリットに分割した例とを示している。パケット５００は、ヘッダフィールド５０１、データフィールド５０２、および制御コードフィールド５０３を有している。
【００５７】
ヘッダフィールド５０１には、例えば、パケットの先頭であることを示すフラグ情報、送信先のアドレス、送信元のアドレス、パケットの優先度を示す情報、およびパケットが送信されてから経過した時間を示す情報（経時情報）が記述される。経時情報の記述方法は任意であり、送信されてから経過した時間を判別できる値であればどのような記述方法であっても良い。例えば、送信された時刻、送信されてから経過した時間、または通過した中継器の数（ホップ数）などが記述される。たとえば、各中継器はパケット５００を中継する度に、ホップ数をインクリメントしてもよいし、予め定められた最大ホップ数を順にデクリメントさせてもよい。ヘッダフィールド５０１には、上記以外の情報が記述されていてもよい。ヘッダフィールド５０１のデータのうち、送信先のアドレスおよび送信元のアドレスに基づいて、パケット５００の中継処理と、受信側での受信処理とが行われる。
【００５８】
データフィールド５０２には、例えば、映像データや音声データなどが記述される。制御コードフィールド５０３には、例えば、予め定められた終了コードが記述される。終了コードによってパケット５００が終了することが判別できる。制御コードフィールド５０３には、終了コード以外の情報が格納されていてもよい。
【００５９】
バスマスタ１０１は、前述のように、パケット５００を、フリットと呼ばれる小さなパケット単位に分解して伝送する。１フリットのサイズは、バスを使って１サイクルで伝送可能なサイズであり、バス幅に応じて決定される。パケット５００は、ヘッダフリット５０４、複数のデータフリット５０５、およびテイルフリット５０５に分割される。ヘッダフリット５０４には、上記のヘッダフィールド５０１に格納されたフラグ情報や送信先アドレス情報などが含まれる。なお、本開示では特別な断りを入れない限り、フリットを含めたデータ列をパケットと表現する。
【００６０】
ヘッダフリット５０４に続く各フリット（データフリット５０５、テイルフリット５０６）には、送信先を特定するアドレス情報は格納されていない。その理由は、ヘッダフリット５０４に続く各フリットは、ヘッダフリット５０４と同じ宛先に送られるためである。ヘッダフリット５０４によって宛先が決まり、そのトラヒックのフリットを出力する出力バッファ６０６が決まると、後に続くフリットは、ヘッダフリット５０４と同じ出力バッファ６０６を利用してヘッダフリット５０４が示す宛先に伝送される。
【００６１】
テイルフリット５０６には、そのフリットがパケットを構成する最後のフリットであることを示すフラグ情報（制御コードフィールド５０３に格納されている終了コード）が付与されている。また、ヘッダフリット５０４とテイルフリット５０６以外の複数のデータフリット５０５は、主にデータを伝送するフリットであり、パケット５００のデータフィールド５０２に対応する。
【００６２】
受信側のメモリ１０５は、テイルフリット５０６に記述されたフラグ情報（終了コード）を検出すると、その終了コードに基づき、伝送された複数のフリットをパケットへ再構築する。
【００６３】
１パケットのサイズは、例えば１２８バイトであり、１フリットのサイズは、例えば３２ビットまたは６４ビットに設定される。ただし、１パケットのサイズおよび１フリットのサイズはアプリケーションによって異なり得るため、上記のサイズは一例に過ぎない。１フリットの長さは、送信先のアドレスや送信元のアドレスなどの制御データを記述できる長さを基準としてもよい。
【００６４】
各中継器は、送られてきたフリットを蓄えるためのバッファを備えている。通常処理（バイパスされない処理）において、フリットは、一旦そのバッファに蓄えられた後、スイッチの切り替えによって宛先のメモリへと続く中継器、または宛先のメモリへ送信される。
【００６５】
＜３．中継器の構成および動作＞
＜３．１．中継器の概略構成＞
次に、中継器の具体的な構成を説明する。図７は、本実施形態における中継器の概略構成を示す図である。以下の説明では、第２グループの中継器６００ｂを例に説明するが、第１および第３グループの中継器についても送信先および受信元が異なるだけで基本的な構成は同様である。以下、第１グループの中継器６００ａを前段の中継器と呼び、第３グループの中継器６００ｃを後段の中継器と呼ぶことがある。また、第１および第３グループの中継器を隣接中継器と呼ぶことがある。中継器６００ｂは、前段の中継器６００ａから後段の中継器６００ｃへの行き先を決定し、トラヒックを中継する。
【００６６】
中継器６００ｂは、複数の入力ポート６１５および出力ポート６１３を備えている。前段の中継器６００ａから入力ポート６１５を経由してフリットを受け取り、出力ポート６１３を経由して後段の中継器６００ｃにフリットを送出する。
【００６７】
また、中継器６００ｂは、バッファ選択部６０３と、バッファ状態通知部６１２とを備えている。
【００６８】
バッファ選択部６０３は、前段の中継器６００ａから送られるフリットを受信し、迂回するか否かを決定する。
【００６９】
バッファ状態通知部６１２（本願明細書では「通知部６１２」とも呼ぶことがある。）は、自中継器の入力バッファ６０４の空き状態を他の中継器に通知する。また通知部６１２は、混雑時には、予め定めた規則にしたがって、パケット送信待機時間だけパケットを待機させる。「混雑時」とは、パケットの転送ができない状況を意味する。パケットの待機中に中継器６００ｂがパケットを送信可能な状態になれば、そのパケットは送信される。一方、パケット送信待機時間だけパケットを待機させても中継器６００ｂがパケットを送信可能な状態にならず、パケットを待機させている時間がパケット送信待機時間を超えた場合には、通知部６１２はパケットの廃棄処理を行う。詳細は後述する。
【００７０】
また、通知部６１２は他中継器へのパケットの転送許可の要求を送り、当該他中継器から送信の許可を得られるか否かによって、パケットを送信する伝送経路に障害があるか否かを判断してもよい。以下、詳しく説明する。なお、パケットの転送許可の要求は、たとえば他中継器の入力バッファ６０４の空き状態を他中継器への問い合わせとして行われ得る。
【００７１】
図８は、障害および混雑が存在するデータ伝送システムを示す。バスマスタ１０１ａからメモリ１０５に至る通信経路に障害が発生しており、バスマスタ１０１ｂからメモリ１０５に至る通信経路は混雑が発生している。
【００７２】
バスマスタ１０１ｃがメモリ１０５にデータのパケットを送信する際、バスマスタ１０１ｃは図の左側の通信経路を主経路として設定し、図の右側の通信経路を迂回路として設定する。バスマスタ１０１ｃは、パケットの伝送開始に先立って、経路上の他中継器にパケットの転送許可の要求を送る。転送の許可が得られれば、バスマスタ１０１ｃは、パケットの転送を開始することができる。
【００７３】
いま、ある時点において、主経路および迂回路のいずれの他中継器からも転送の許可が得られないとする。つまり、主経路および迂回路の両方に関し通信ができない状況が発生したとする。混雑が酷くなることにより、通信ができなくなる状況が発生し得る。
【００７４】
このとき通知部６１２は、たとえば図１２に示す方法によって決定されたパケット送信待機時間だけパケットを待機させる。パケットを待機させている間も、通知部６１２は定期的に、経路上の他中継器へパケットの転送許可の要求を送っている。
【００７５】
パケット送信待機時間だけパケットを待機させても許可が得られない場合は、通知部６１２は、問い合わせ先となる中継器を含む伝送経路では通信ができないと判断し、その結果、対象とする伝送経路が異常であると判断する。「異常」とは、たとえば、ハードウェアやソフトウェアの不具合に起因して生じる障害をいう。伝送経路が異常であると判断した場合、通知部６１２は、送信ノード、受信ノード、および伝送経路上の他の中継器、の少なくとも１つに、伝送経路が異常であること示す通知を発行する。この通知は、パケットを廃棄させる命令として機能する。または、通知部６１２は、この通知とは別に、パケットの廃棄指示を出力してもよい。なお、伝送経路が異常であること示す通知として、以下に説明する「リセット信号」を出力してもよい。
【００７６】
一方、上述したパケット送信待機時間内に許可が得られた場合は、通知部６１２は、その伝送経路に対してデータを伝送する。図８の例のように、混雑のため迂回路が一時的に通信できなかった場合でも、パケット送信待機時間の経過までに混雑が解消し通信が回復することがある。その場合には、通知部６１２は迂回路を利用してパケットを伝送する。
【００７７】
なお、主経路における通信不可の原因が、障害ではなく混雑である場合も考えられる。その場合には、パケット送信待機時間内に、主経路および迂回路の両方の中継器から転送の許可が得られる場合がある。その場合には、通知部６１２は、より早く許可が得られた方の経路を利用してパケットを伝送する。
【００７８】
以上の通知部６１２の処理により、伝送経路の異常と、伝送経路の混雑とを区別することが可能となる。
【００７９】
また、ＮｏＣにリセット用共通線６１０が設けられ、通知部６１２がリセット用共通線６１０に接続されている場合には、通知部６１２は、リセット用共通線６１０にリセット信号を送信し、リセット用共通線６１０からリセット信号を受信することができる。通知部６１２は、パケットの廃棄処理を行った後、リセット信号をリセット用共通線６１０に出力する。一方、通知部６１２は、他の中継器がパケットの廃棄処理を実行したことによって出力されたリセット信号を受信すると、現在自中継器に保持しているパケットを廃棄するよう、入力バッファ６０４および出力バッファ６０６の少なくとも一方に指示する。指示は、データが格納されているバッファに出力されればよい。両方にパケットが格納されている場合には、指示は、入力バッファ６０４および出力バッファ６０６の両方に出力される。これにより、他の中継器がパケットの廃棄処理を実行すると、他の中継器においてもパケットが廃棄されることになる。
【００８０】
また、中継器６００ｂは、入出力の接続を切り替えるクロスバスイッチ６０５と、クロスバスイッチ６０５から出力されたデータを一時的に格納する出力バッファ６０６とを備えている。中継器６００ｂは、さらに、パケットを宛先へと転送するための処理を行うルーティング処理部６０７、バッファアロケータ６０８、およびスイッチアロケータ６０９を備えている。本実施形態では、バッファ選択部６０３は、制約時間内でのパケットの伝送が可能になるように迂回路を選択するか否かを決定し、主経路に対応した入力バッファもしくは、迂回路に対応した入力バッファである入力バッファ６０４へ送出する。
【００８１】
図７に示す例では、中継器６００ｂは、バッファ選択部６０３を２つ、入力バッファ６０４を４つ、出力バッファ６０６を２つ備えているが、本開示はこのような例に限られるものではない。これらのバッファの数はトラヒックの伝送量に応じて適宜設計される。
【００８２】
バッファ選択部６０３は、受信したフリットが迂回を行えるか否かを、ヘッダフリットに記述された情報に基づいて判断する。迂回路へ転送できないと判断した場合、バッファ選択部６０３は、そのフリットが属するトラヒックを主経路の入力バッファ６０４に格納する。迂回を行えると判断した場合、バッファ選択部６０３は、そのトラヒックを迂回路に送出する。迂回路を行えるか否かの判定の詳細は後述する。
【００８３】
フリットに記述された宛先情報からフリットの転送先の出力ポートをルーティング処理部６０７によって決定する。ルーティングのアルゴリズムは、動的に行き先を決定する次元順ルーティングや、設計時に送信元と行き先との関係から一意に決定されている静的ルーティングを用いてもよい。本開示は、特定のルーティングアルゴリズムには限定されない。
【００８４】
また、バッファアロケータ６０８において、ルーティング処理部６０７によって選ばれた出力ポート６１３に接続された出力バッファ６０６の内で、空いている出力バッファ６０６を選び、入力バッファ６０４のバッファキューと出力バッファ６０６（または転送先の中継器の入力バッファ）とを対応付ける。
【００８５】
更に、スイッチアロケータ６０９において、トラヒックデータを伝送するために対応付けが完了している組から１組を選ぶ。スイッチアロケータ６０９は、クロスバスイッチ６０５を介して、出力バッファ６０６へフリットを転送する。出力バッファ６０６から対応する中継器６００ｃへ対応するフリットが転送される。
【００８６】
入力バッファ６０４、および出力バッファ６０６は、複数のバッファ（バッファキュー）を有している。バッファは、仮想チャネル（Virtual Channel）で構成してもよい。仮想チャネルによってバッファを構成する場合、複数の仮想回線が構築されることになる。一般に、仮想回線は、物理的には１本である通信回線について、論理的に複数の通信回線であるとみなされた回線を指す。
【００８７】
なお、本実施形態の中継器６００ｂは、出力バッファ６０６を備えているが、組込用途を想定してメモリ量を抑えるために、出力バッファ６０６を設けない場合もある。すなわち、出力バッファ６０６と転送先の中継器６００ｃの入力バッファとを共用する構成であってもよい。出力バッファ６０６の代わりに、転送先の中継器の入力バッファを用いても、本実施形態と同様の効果を得ることができる。
【００８８】
＜３．２．中継器の動作の概略＞
図９は、中継器６００ｂの動作を説明するための図である。中継器６００ｂのバッファ選択部６０３は、まずステップＳ８０１において、隣接の中継器６００ａからフリットを受信する。そして、ステップＳ８０２において、バッファ選択部６０３は迂回を行えるかどうかを判定する。
【００８９】
バッファ選択部６０３が、受け取ったフリットについて、迂回を行えるフローに属するフリットであると判断した場合は、主経路に対応する入力バッファ６０４と、迂回路に対応する入力バッファ６０４の両方に当該フリットを送る。一方、迂回が行えない場合は、主経路のみに対応する入力バッファ６０４のみに当該フリットを送る。
【００９０】
次に、ステップＳ８０３において、ルーティング処理部６０７でヘッダフリットを解析して出力ポート６１３を決定する。次に、ステップＳ８０４において、バッファアロケータ６０８は、出力ポートと宛先の中継器の入力バッファのバッファキューとの対応付けを行う。続いて、ステップＳ８０５において、スイッチアロケータ６０９は、トラヒックデータを伝送するために対応付けが完了している組から１組を選ぶ。その後、ステップＳ８０６において、対象とするバッファキューからデータを１フリット単位又は、パケット単位で伝送する。最後に、ステップＳ８０７において、バッファ選択部６０３は、迂回を行えると判断していた場合に、伝送が行われなかった主経路又は、迂回路の入力バッファ６０４を削除し、出力ポートと宛先の中継器の入力バッファのバッファキューとの対応付けも削除する。
【００９１】
図１０は、一般的な中継器の処理の手順を示す。一般的な中継器における構成や処理手順は、基本的に前述の迂回を行わない場合における図７の構成や図９の処理手順と同じである。まず、（１）ヘッダフリットを解析して宛先アドレスから出力ポートを決定する（Routing computation；RC）。この処理は、本実施形態では、ルーティング処理部６０７が担当し、Ｓ８０３の処理ステップに対応する。
【００９２】
次に、（２）転送先の隣接中継器の入力バッファのバッファキュー（又は自中継器の出力バッファのバッファキュー）を決定する（Virtual channel allocation；VA）。本実施形態ではバッファアロケータ６０８がこの処理を担当する。この処理は図９のステップＳ８０４に対応する。出力ポートとバッファキューとを対応付ける順序を決定する基準として、ラウンドロビン、パケットの到着順、締切時間順などを用いることができる。
【００９３】
続いて、（３）トラヒックデータを伝送するために対応付けが完了している組から１組を選ぶ（Switch allocation；SA）。このステップでも同様に、対応付けが完了している組から１組を選ぶ選び方を決定する基準として、ラウンドロビン、パケットの到着順、締切時間順などを用いることができる。但し、選択されても、宛先の中継器が受け入れ可能であると判断できた場合のみ、データが伝送される。本実施形態では、スイッチアロケータ６０９がこの処理を担当する。この処理は図９のステップＳ８０５に対応する。
【００９４】
そして、（４）対象とするバッファキューからデータを１フリット単位で伝送する（Switch traversal；ST）。本実施形態では、スイッチアロケータ６０９がこの処理を担当する。この処理は図９のステップＳ８０６に対応する。伝送するデータのサイズは、前述のように、１フリット単位ではなく、パケット単位であってもよい。
【００９５】
＜パケット送信待機時間の決定＞
図１１（ａ）および（ｂ）は、パケット送信待機時間を説明する図である。
【００９６】
図１１（ａ）の例では、迂回路から主経路へトラヒックが流入する例を示している。この例では、迂回路から主経路へトラヒックが流入する場合に、合流する主経路の中継器６００ｃの混雑で、迂回路のトラヒックがパケットの受け取りを拒否されている。その結果、合流する１つ手前の中継器６００ｂはパケットの送信を待機している（パケット送信待機）。
【００９７】
本実施形態では、中継器６００ｂは、予め定めたパケット送信待機時間だけ、迂回路からのパケット送信を待機させる。予め決めたパケット送信待機時間を超えた場合には、図１１（ｂ）に示すように迂回路の中継器６００ｂはパケットを廃棄する（パケット廃棄）。具体的な本開示の応用方法は、図１４以降で説明する。
【００９８】
図１２は、パケット送信待機時間を決定するパラメータと、パケット送信待機時間の決定方法の対応関係を示す。
【００９９】
本実施形態においては、パケット送信待機時間を決定するパラメータとして、下記の３つのパラメータ（指標）を例示する。
（ａ）送信待機する中継器６００ｂ（図１１）の、バスマスタからのホップ数（Ｈ）、
（ｂ）伝送路を共用するトラヒックのフロー数（Ｆ）
（ｃ）評価式（Ｖ）
【０１００】
パケット送信待機時間を決定する指標として、送信待機する中継器６００ｂ（図１１）のバスマスタからのホップ数（Ｈ）を用いる場合は、例えば、送信側のバスマスタからのホップ数が小さいほど待機時間を短くしてパケット廃棄を早く実施する。すなわち、パケットの待機よりも、パケット廃棄を優先して行う。バスマスタからのホップ数が小さいため、パケットの待機よりもパケット再送によるパケットの回復が効果的であると考えられるためである。このような事情から、パケットの廃棄処理を積極的に行うこととした。逆に、ホップ数が大きければパケット廃棄による損失が大きいと考えられるため、待機時間を長くする。
【０１０１】
また、パケット送信待機時間の決定方法として、送信ノードから受信ノード（たとえばバスマスタからメモリ）までの間の伝送経路上に設けられた中継器の数に応じて定まる時間値を、パケット送信待機時間として用いてもよい。例えば、送信元のマスタから送信先であるメモリまで、５つの中継器を介して通信が行われるとする。その場合には、往復で１０回の中継処理を行う必要がある。１つの中継器で３サイクルの処理が必要な場合は、３０（＝５×３×２）サイクルをパケット送信待機時間として与える。中継器の数に比例する時間値をパケット送信待機時間として決定してもよい。
【０１０２】
なお、パケット送信待機時間に、固定的に必要な遅延（例えば、パケット化や脱パケット化の処理遅延や、メモリコントローラでの処理遅延など）を加えて算出される最も悪い伝送遅延をパケット送信待機時間として決定してもよい。最悪の伝送遅延時間を超えても最隣接の中継器から許可が得られない場合は、対象とする伝送路は異常であると判断できる。システムの設計者は、バスの設計時にこれらの値を見積もることができる。また、パケット送信待機時間の値はユースケースに応じて決定できる。伝送経路が異なる場合は、ユースケース毎に独立したパケット送信待機時間を与えてもよい。さらに、パケット送信待機時間の決定に際して、伝送路を共用する共用フロー数（F）を併用してもよい。加えて、パケット送信待機時間の値は、これらの指標に縛られるわけではなく、設計者が経験などから得られる任意の値を設定してもよい。
【０１０３】
具体例として、ホップ数が２以内であれば、パケット送信待機時間を１００サイクルに、ホップ数が２を超える場合は、１０００サイクルに設定する。
【０１０４】
パケット送信待機時間を決定する指標として、伝送路を共用するトラヒックフロー数（Ｆ）を用いる場合は、例えば、システムの不具合のように、急激に中継負荷が増える状況下では、パケットの待機時間を短くしてパケットをより早く廃棄する。パケットの廃棄により、システムの動作をリセットさせて、再起動を行うことでシステムを素早く正常状態に近づける。
【０１０５】
具体例として、フロー数が１０個を超えた場合には、設計時の想定以上のトラヒックフローが伝送されているとして、パケット送信待機時間を短く（例えば、１００サイクルに）設定する。
【０１０６】
パケット送信待機時間を決定する指標として、評価式（Ｖ）を用いる例は、本実施形態では、送信待機する中継器のバスマスタからのホップ数（Ｈ）と、伝送路を共用する共用フロー数（Ｆ）の両方を用いることを意味している。具体的には、Ｖ＝バスマスタからのホップ数×伝送路を共用するフロー数（Ｈ×Ｆ）で、評価式を与えてもよい。ただしこれは一例である。評価式の実装の容易さを加味して乗除加減算のいずれを用いて評価式を用意してもよい。ホップ数（Ｈ）および共用フロー数（Ｆ）の両方の条件を加味することで、システムの異常状態を絞り込みやすくなり、パケット廃棄が頻発することを抑制することが可能となる。
【０１０７】
図１３は、中継器６００ｂでのパケット廃棄に伴い、他のノードへの通知を説明する図である。
【０１０８】
パケットを廃棄すると、中継器６００ｂは、送信元のバスマスタ１０１へパケット廃棄が発生したことを通知する。このとき中継器６００ｂは、送信元のバスマスタ１０１、および、廃棄されたパケットを中継した各中継器（図示せず）に対しても、パケットを廃棄したことを通知する。通知を受けた各中継器は、転送途中の該当パケットを廃棄する。その理由は以下のとおりである。あるトラヒックを構成するパケット群は数珠つなぎになってバス上を伝送されている。トラヒックを構成する一部のパケットが廃棄されると、そのトラヒックに必要なデータが欠落することになり、目的としていたデータを得ることができなくなる。よって、そのトラヒックの他のパケットはもはや役に立たない。そのため、他の中継器が、転送途中のパケットの伝送を廃棄することとした。
【０１０９】
中継器６００ｂが送信元のバスマスタ１０１に廃棄の通知を送ることにより、送信元のバスマスタ１０１はパケットの再送が必要であることを知ることができる。送信元のバスマスタ１０１は、その後パケットを再送する。
【０１１０】
上述の説明では、各中継器が、パケットの廃棄通知を受けてパケットの廃棄を行うとして説明したが、その動作は一例である。他の例として、上述したリセット用共通線６１０（図７）を用いる例が考えられる。パケットを廃棄した中継器６００ｂは、リセット用共通線６１０にリセット信号を出力する。他の中継器はリセット信号の受信に応答して、その時点で保持していたパケットの廃棄処理を強制的に実行する。この例では、リセット信号がパケットの廃棄通知の意味を持つと共に、各中継器の動作をリセットさせる信号としても機能する。
【０１１１】
なお、パケット廃棄処理を実行する中継器は、パケットを廃棄した中継器６００ｂとバスマスタ１０１との間に存在する中継器に限られない。パケットを廃棄した中継器６００ｂとメモリ１０５との間に存在する中継器（たとえば中継器６００ｃ）も廃棄処理を実行してもよい。これらの中継器もまた、もはや役に立たなくなったパケットを保持しているからである。さらにメモリ１０５に到着した先行するパケット（データ）もまた廃棄されてもよい。
【０１１２】
また、送信元のバスマスタ１０１は、廃棄されたパケットに関連するトラヒックを生成したアプリケーションに、パケット廃棄が発生したことを通知する。そしてバスマスタ１０１は、必要に応じてアプリケーションを再起動させたり、既に転送済みのデータの廃棄を行う。
【０１１３】
＜３．３．バッファ選択部の構成および動作＞
図１４は、本実施形態による、迂回路を用いた並列伝送への応用例を示す。図１４（ａ）は、主経路と迂回路の両方でトラヒック伝送が行われている例を示す。マスタＡは主経路を介してＧＷ（ゲートウェイ）にトラヒックを伝送している。また、マスタＣは迂回路（マスタＣに対しては主経路）を介してＧＷにトラヒックを伝送している。図１４（ｂ）は、マスタＡは迂回路の空きを検出して、主経路と迂回路の両方の伝送路を用いてトラヒックの同時伝送を行っている例を示している。これにより、主経路だけを使うよりもマスタＡは高い伝送効率を得ることが可能となる。
【０１１４】
図１５は、本実施形態による迂回処理の概要を説明する図である。
【０１１５】
本実施形態では、パケットを迂回させて伝送するかどうかを中継器が決定する。迂回路へ合流する直前の中継器（迂回路元の中継器１２０１）が、迂回路へ合流した直後の中継器（迂回路先の中継器１２０２）の伝送状態と、迂回させるトラヒックの要求品質に基づき、迂回を行うかどうかを判定する。これにより、トラヒックの要求遅延を加味しながら、主経路と迂回路の両方の伝送効率を高める。
【０１１６】
図１６は、迂回路先の中継器１２０２の動作の手順を示す。
【０１１７】
中継器１２０２の通知部６１２は、自らの入力バッファ状態に基づき、予め決めた通知間隔（Ｔ１）で迂回元の中継器１２０１に受入情報送信する。通知部６１２は、受入情報として、「高優先度トラヒックが転送可能」、「低優先度トラヒックのみ転送可能」、「全てのパケットは受入不可」のいずれかを示す情報を送信する（ステップ１３０１）。
【０１１８】
受入情報の決定方法としては、迂回路先の中継器１２０２の入力バッファで、予め定めた期間、高優先度のトラヒックを中継していない場合には、「高優先度トラヒックの転送が可能」と通知する。また、高優先度トラヒットと低優先度トラヒックのトラヒック量の総量が、予め定めたトラヒック量以下である場合には「低優先度トラヒックのみ転送可能」と通知する。また、トラヒック量の総量が、予め定めたトラヒック量を超える場合には「全てのパケットは受入不可」と通知する。
【０１１９】
次に、迂回元の中継器１２０１から転送許可要求を受信したか否かを判定する（ステップ１３０２）。転送許可要求を受信していない場合には（ステップ１３０２のＮＯ）、処理はステップＳ１３０１に戻る。
【０１２０】
迂回元の中継器１２０１から転送許可要求が送信された場合には（ステップ１３０２のＹＥＳ）、迂回先の中継器１２０２の通知部６１２は、迂回路先の中継器１２０２の入力バッファの状態に基づき、迂回元の中継器１２０１の受入の可否を返信する（ステップ１３０３）。
【０１２１】
具体的には、例えば、迂回元の中継器１２０１から高優先度トラヒックに対する転送許可要求が送信された場合、前述の受入情報の決定方法と同じ基準で、自中継器が高優先度トラヒックを受入可能であれば、受入可能であること迂回元の中継器１２０１に通知する。なお、転送元の中継器に受入情報送信の間隔（Ｔ１）の値は、固定値を用いてもよい。
【０１２２】
図１７は、迂回元の中継器１２０１の動作の手順を示す。
【０１２３】
中継器１２０１のバッファ選択部６０３は、迂回路先の中継器１２０２の受入情報に基づき、送信パケットを選択する（ステップ１４０１）。このとき、中継器１２０１は主経路と迂回路に対応する入力バッファ６０４に同じパケットをコピーする。これにより、主経路と迂回路のそれぞれに転送できる。本明細書では、同じパケットをコピーする上記処理を「転送設定」と呼ぶ。
【０１２４】
図１２で示したパケット送信待機時間の決定方法に従えば、図１５の例は、中継器１２０１が送信元のバスマスタから近い（ホップ数が小さい）距離に存在しているといえるため、パケット廃棄を優先的に行い、パケット再送によるパケットの回復が効果的であるといえる。そこで中継器１２０１は主経路と迂回路のいずれに伝送するかを判定する。中継器１２０１がこの判定に要する時間は十分短いため、処理の遅延の問題は実質的には生じない。判定結果に応じてパケットの送信先が変化するため、主経路や迂回路のいずれの経路でも伝送が行えるように、入力バッファ６０４に同じパケットをコピーして準備しておく。
【０１２５】
具体的には、転送設定としては中継器の各部にて、図９のステップＳ８０３、Ｓ８０４、Ｓ８０５を実行する。例えば、図１２で説明した方法で設定した方法で待機時間の設定（Ｔ２）を行い、中継器の通知部６１２で、待機時間を設定して、迂回路先の中継器１２０２に、送信する予定のトラヒックの優先度の情報とともに転送許可要求を送信する（ステップ１４０２、ステップ１４０３）。さらに、最大Ｔ２の時間だけ迂回路先の中継器からの許可を待つ。迂回路への転送を許可された場合には（ステップ１４０４）、通知部６１２から入力バッファ６０４へ該当パケットを送信するように指示し、迂回路にパケットを伝送する（ステップ１４０５）。図９では、ステップＳ８０６に対応する。
【０１２６】
次に、主経路へ向かう入力バッファの廃棄や出力ポートと宛先の中継器の入力バッファのバッファキューとの対応付けなど、主経路への転送のため設定処理を解除する。図９ではステップＳ８０７に対応する。
【０１２７】
転送許可を得られない、もしくは、待機時間Ｔ２を超えた場合は、主経路へデータを転送する（ステップ１４０６）。具体的には、転送設定としては中継器の各部にて、図９のステップＳ８０３、Ｓ８０４、Ｓ８０５を実行する。また、迂回路へ向かう入力バッファ６０４の廃棄や出力ポートと宛先の中継器の入力バッファのバッファキューとの対応付けなど、迂回路への転送のため設定処理を解除する（ステップ１４０７）。
【０１２８】
＜４．他のトポロジ＞
上記の説明では、集積回路のトポロジが多段接続網の場合（図４）を例に説明したが、本実施形態の中継器６００は、多段接続網での利用に限定されるものではない。例えば、図１８（ａ）に示すような、中継器を格子状に並べたメッシュ型のトポロジ、図１８（ｂ）に示すようなトーラス型のトポロジであってもよいし、図１８（ｃ）に示すような、バスを階層的に接続したトポロジであってもよい。複数のバスマスタを分散型のバスを介して接続したトポロジであれば、同様に本実施形態の中継器の適用が可能である。
【０１２９】
たとえば図１８（ａ）および（ｂ）には、バスマスタからメモリまで、複数の伝送経路を確保することが可能である。すなわち、いずれかの伝送経路を主経路とし、他の伝送経路を迂回路として設定することが可能である。これらの伝送経路に関して、通知部６１２が上述した処理を実行することにより、伝送経路の異常と、伝送経路の混雑とを区別することが可能となる。なお、主経路および迂回路は固定的でなくてよい。バスマスタ毎に主経路および迂回路が異なってもよいし、バスマスタと、データ送信先のメモリとの関係に応じて主経路および迂回路が異なってもよい。
【０１３０】
＜５  利用例＞
＜５．１  半導体回路上のバスマスタとメモリ＞
以下、上記の実施形態による中継器の実際の機器への利用例を説明する。
【０１３１】
図１９は、半導体回路上の複数のバスマスタと複数のメモリとを分散型のバスを利用して接続した例を示している。このような半導体回路は、例えば、携帯電話、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔｓ）、電子書籍リーダーなどの携帯端末や、ＴＶ、ビデオレコーダ、ビデオカメラ、監視カメラ等の機器で用いられ得る。バスマスタは、例えば、ＣＵＰ、ＤＳＰ、伝送処理部、画像処理部などである。
【０１３２】
複数の映像や音楽などの再生、記録、トランスコード、および書籍、写真、地図データ等の閲覧や編集、ゲームのプレイなど、複数のアプリケーションやサービスを同時に利用する場合、各バスマスタからメモリへのアクセスが増える。このため、メモリの数が１つしかない場合、アクセスが１箇所に集中してしまう。これを解決するためには、メモリ側の入出力の伝送帯域を広げる必要があり、コストが高くなってしまう。
【０１３３】
メモリアクセスの集中を回避する方法として、アプリケーションやサービス等の種類によってバスマスタが利用するメモリを物理的に分け、これらのバスマスタとメモリとを分散型のバスで接続させることが有効である。
【０１３４】
しかし、例えば、あるバスマスタが、映像データを保存するためにメモリＡに対して高いレートでデータパケットを送信した場合、伝送経路上のバッファが全てメモリＡ宛のパケットで占有される頻度が多くなる。その結果、他のメモリへデータが流れにくくなり、他のアプリケーションやサービスの性能が低下したり、処理時間が増加してしまう。この問題は、各中継器が送られてきたデータパケットの順序を単純に維持したまま中継することにより発生する。
【０１３５】
これに対し、本開示の中継器を用いた場合には、緊急度や重要度の高いパケットは優先的に伝送されるため、特定のメモリに向うパケットによるバッファの占有が回避される。これにより、アプリケーションやサービスで重要となるデータを締切時刻までに伝送することが可能となる。その結果、アプリケーションやサービスのユーザ応答性の確保や、映像・音声の品質確保などが可能となる。さらに、迂回路への伝送へ本開示を適用した場合には、受入情報を加味して、迂回路の選択の有無を決定することで、優先度の低いデータに対しても、優先度の高いデータとのトラヒックの干渉を抑えることが可能となる。よって、システム全体の伝送効率が改善するとともに、省電力化も期待できる。特に、設計時の想定以上にデータ伝送の遅延が発生した場合に、緊急的に重要なデータを優先的に伝送できるため、システムが想定外に過負荷になった場合の対処方法としても有効である。
【０１３６】
＜５．２．マルチコアプロセッサ＞
次に、上記の各実施形態による中継器のマルチコアプロセッサ（ｍｕｌｔｉ−ｃｏｒｅ  ｐｒｏｃｅｓｓｏｒ）への利用例を説明する。
【０１３７】
図２０は、ＣＰＵやＧＰＵ，ＤＳＰ等のコアプロセッサの処理能力を向上させるために、複数のコアプロセッサをメッシュ状に配列し、これらを分散バスで接続したマルチコアプロセッサを示している。この構成では、各コアプロセッサが本開示における第１ノードとして機能し得るし、第２ノードとしても機能し得る。
【０１３８】
マルチコアプロセッサ上では、各コアプロセッサ間で通信が行われる。例えば、各コアプロセッサには、演算処理に必要なデータを記憶しておくキャッシュメモリが備えられており、コアプロセッサ間で互いのキャッシュメモリの情報をやり取りすることができる。これによって情報の共有が可能となり、処理性能を向上させることができる。
【０１３９】
しかし、マルチコアプロセッサ上で発生するコアプロセッサ間の通信は、それぞれ位置関係や距離（中継ホップ数）、通信頻度が異なる。このため、データパケットの順序を単純に維持したまま中継すると、バッファが全て特定のコアプロセッサ宛のパケットにより占有されパケットデータが流れにくい中継器が発生する。その結果、マルチコアプロセッサの性能の低下や、処理時間の増加を引き起こす。
【０１４０】
これに対し、上記の実施形態による中継器を用いた場合には、緊急度や重要度の高いパケットは優先的に伝送されるため、特定のメモリに向うパケットによるバッファの占有が回避される。そのため、重要なデータを締切時刻までに伝送することが可能となる。同様に、アプリケーションやサービスのユーザ応答性の確保や映像・音声の品質確保などが可能となる。また、迂回路への伝送へ本開示を適用した場合には、受入情報を加味して、迂回路の選択の有無を決定することで、優先度の低いデータ伝送に対しても、トラヒック干渉を抑えることが可能となるため、システム全体の伝送効率の改善が可能となるとともに、省電力化も期待できる。特に、設計時に想定していた以上にデータ伝送で遅延が発生した場合に、緊急的に重要なデータを優先的に伝送できるため、システムが想定外に過負荷になった場合の対処方法としても有効である。
【０１４１】
＜５．３．シミュレーションプログラム＞
上述の実施形態および利用例では、本開示がチップ上で実装された際の構成を説明した。本開示は、チップ上に実装されるだけでなく、チップ上に実装するための設計及び検証を行うシミュレーションプログラムとしても実施され得る。そのようなシミュレーションプログラムは、コンピュータによって実行される。例えば、図７に示される各構成要素は、シミュレーションプログラム上のオブジェクト化されたクラスとして実装される。各クラスは、予め定められたシミュレーションシナリオを読み込むことにより、各構成要素に対応する動作をコンピュータ上で実現する。言い換えると、各構成要素に対応する動作は、コンピュータの処理ステップとして直列的または並列的に実行される。
【０１４２】
中継器として実装されたクラスは、シミュレータで定義されたシミュレーションシナリオを読み込むことにより、優先度閾値等の条件を決定する。また、他の中継器のクラスから送信されるパケットの送信タイミング、送信先、優先度、締切時間等の条件を決定する。
【０１４３】
バイパス配線を備えた中継器として実装されたクラスは、個々のシミュレーションシナリオにおいて、他の中継器のクラスからデータの入力を受け、そのデータがバイパスすべきデータか否かに応じて、バイパス処理および通常処理のいずれかを選択的に実行する。
【０１４４】
中継器として実装されたクラスは、シミュレーションシナリオに記述されたシミュレーションの終了条件が成立する迄の間、動作を行う。動作中のスループットやレイテンシ、バスの流量の変動の様子、動作周波数、消費電力の見積値等を算出しプログラムの利用者に提供する。これらに基づき、プログラムの利用者はトポロジや性能の評価を行い、設計及び検証を行う。
【０１４５】
シミュレーションシナリオの各行には、例えば、送信元ノードのＩＤ、宛先ノードのＩＤ、送信するパケットのサイズ、送信するタイミング等の情報が記述されるのが普通である。また複数のシミュレーションシナリオをバッチ処理的に評価することで、想定した全てのシナリオで所望の性能が保証できているか否かを効率的に検証できる。またバスのトポロジやノード数、送信ノード、中継器、宛先ノードの配置を変化させて性能比較することにより、シミュレーションシナリオに最も適したネットワーク構成を特定することもできる。上記の実施形態のいずれもが本態様の設計及び検証ツールとしても適用可能である。このように、本開示は、設計及び検証ツールとして実施される際にも適用可能である。
【産業上の利用可能性】
【０１４６】
本開示の一態様にかかる中継器は、システムＬＳＩなどのデータ伝送システム上のデータ伝送に利用できる。
【符号の説明】
【０１４７】
１０１  バスマスタ
１０５  メモリ
５００  パケット
５０１  ヘッダフィールド
５０２  データフィールド
５０３  制御コードフィールド
５０４  ヘッダフリット
５０５  データフリット
５０６  テイルフリット
６００、６００ａ、６００ｂ、６００ｃ  中継器
６０３  バッファ選択部
６０４  入力バッファ
６０５  クロスバスイッチ
６０６  出力バッファ
６０７  ルーティング処理部
６０８  バッファアロケータ部
６０９  スイッチアロケータ部
６１０  リセット用共通線
６１３  出力ポート
６１５  入力ポート
６２０ａ、６２０ｃ  ＮＩＣ
６３０  メモリコントローラ
【図１】
0005895202.tif 000002
【図２】
0005895202.tif 000003
【図３】
0005895202.tif 000004
【図４】
0005895202.tif 000005
【図５】
0005895202.tif 000006
【図６】
0005895202.tif 000007
【図７】
0005895202.tif 000008
【図８】
0005895202.tif 000009
【図９】
0005895202.tif 000010
【図１０】
0005895202.tif 000011
【図１１】
0005895202.tif 000012
【図１２】
0005895202.tif 000013
【図１３】
0005895202.tif 000014
【図１４】
0005895202.tif 000015
【図１５】
0005895202.tif 000016
【図１６】
0005895202.tif 000017
【図１７】
0005895202.tif 000018
【図１８】
0005895202.tif 000019
【図１９】
0005895202.tif 000020
【図２０】
0005895202.tif 000021